Трансформация цвета: поиски в прореженном столе

Это обзор функциональности, появившейся в Pillow 5.4: применение трехмерных таблиц поиска (3D lookup tables, 3D LUT) для трансформации цвета. Эта техника широко распространена в обработке видео и 3D-играх, однако мало графических библиотек могли похвастаться их поддержкой до этого.

Трехмерные таблицы поиска дают большую гибкость в описании цветовых трансформаций, но самое главное трансформации выполняются за одинаковое время, какими бы сложными они не были.

from PIL import Image, ImageFilter

def washout(r, g, b):
    h, s, v = _rgb_to_hsv(r, g, b)
    if 0.3 < h < 0.7:
        s = 0
    return _hsv_to_rgb(h, s, v)

im = Image.open('./Puffins.jpg')
im = im.filter(ImageFilter.Color3DLUT.generate(17, washout))

Функция, полностью написанная на Пайтоне, применяется к 16,6-мегапиксельной картинке за 75ms.


c8vx4rtwofnxhnkippjdt2oomkw.jpeg

Работа с изображениями и так ресурсоемка, поэтому я обожаю алгоритмы, которые позволяют убрать сложность от входных параметров. Пять лет назад я реализовал в Pillow гауссово размытие, работающее за одинаковое время для любого радиуса. Не так давно я рассказал как можно уменьшить изображение за константное время с минимальной потерей качества. Сегодня я покажу для каких задач можно применять 3D LUT, какие у нее ограничения и похвастаюсь достигнутой производительностью в Pillow-SIMD.


Нормально делай — нормально не будет

Хорошо известные факты: растровые изображения состоят из пикселей, пиксели состоят из каналов. Каждый канал ответственен за какую-то конкретную характеристику цвета, каждый канал в пикселе имеет конкретное значение (чаще всего в диапазоне от 0 до 255). Например, в цветовой модели HSV первый канал, Hue, отвечает за цветовое смещение, второй, Saturation, за насыщенность цвета, третий, Value, за яркость пикселя. Пройдя по всему изображению и прибавив, например, к каналу Saturation какое-то значение, можно увеличить насыщенность всего изображения. Собственно это и есть трансформация цвета.

Что если нужно реализовать изменение насыщенности в своем приложении? Можно написать довольно быструю функцию, которая будет делать то, что нужно. Причем желательно писать на чем-то близком к железу, например, на Си. Придумали API, написали, отладили, оптимизировали, написали документацию. Неплохо.

Для каждой нужной трансформации можно написать, отладить, оптимизировать новую функцию. Проблема только в том, что если нужно одновременно поменять у изображения несколько параметров, придется пройтись по изображению два раза, что ухудшит скорость. Еще больше скорость ухудшится, если для трансформаций понадобятся более тяжелые вычисления: тригонометрия, переход в другие цветовые пространства, ветвления, не дай бог. Да и писать все новые функции и раздувать API для бесконечного количества цветовых трансформаций — чистое безумие.


Да кто такие эти таблицы

Тут-то на помощь и приходят таблицы поиска. Это своего рода кеш, но подготовленный заранее. Вместо того, чтобы вычислять новое значение для каждого пикселя изображения, мы можем заранее вычислить результат для всех возможных пикселей исходного изображения, положить их в таблицу и для каждого пикселя доставать уже готовый ответ из таблицы. В таком подходе без разницы, насколько сложными были вычисления и сколько цветовых трансформаций мы совершили, ответ-то мы все равно достаем готовый!

Таблицы получаются трехмерными, потому что цветовых каналов в изображении чаще всего три. Каждый канал становится одной из координат в этой таблице. Если, например, пиксель имеет в RGB цвет #e51288, то из таблицы для него будет использовано значение с координатами [229, 18, 136]. В ячейках этой таблицы хранится результат — то есть значения конечных пикселей, которые тоже могут быть RGB-цветом. Получается такой красивый цветовой куб:


yla1huj0xfiyc6qym1dwolrmedm.png

Есть только одна маааленькая проблема. Размеры такой таблицы для трехканального изображения должен быть 256³, то есть 16 миллионов ячеек, что для трех каналов результата дает размер таблицы 48 мегабайт. 48 мегабайт — это дофига. Это значительно больше, чем кеш L3 современных процессоров, поиск по такой таблице будет работать очень медленно. Кроме того, 16 миллионов ячеек означает, что только для подготовки такой таблицы уже нужно будет выполнить трансформацию 16 миллионов пикселей, а большинство изображений, которые будут трансформироваться, могут быть меньше этого размера. Какая же это оптимизация?

На самом деле трехмерные таблицы поиска никто не использует в сыром виде, это действительно очень затратно. Вместо этого используются прореженные трехмерные таблицы поиска, в которых находятся не все-все-все возможные результаты для всех возможных пикселей, а лишь некоторые опорные. Например, можно взять только каждое шестнадцатое значение по каждому каналу и, таким образом, получить таблицу из 16³ значений. Размер такой таблицы будет 12 килобайт, что уже не только в L3, но и в L1 влезет на всех современных процессорах.


zc1g8zvyww89ssbaekzy72bwlh0.png

Но где тогда взять промежуточные значения? Очень просто — интерполировать. Чтобы получить значение конечного пикселя, нужно выяснить в какое место трехмерной таблицы попадает его цвет, найти восемь соседних точек из таблицы и с помощью трилинейной интерполяции (то есть линейной интерполяции в трехмерном пространстве) посчитать нужное значение.

Таким образом, получается, что параметром операции становится функция трансформации. Вместо того, чтобы реализовывать бессчетное множество цветовых трансформаций, понадобилось написать, протестировать и оптимизировать ровно одну. А саму таблицу можно уже генерировать как угодно, хоть на Пайтоне.


Где применять 3D LUT трансформации

Трехмерные таблицы поиска подходят для любых трансформаций, результат которых зависит только от значения одного пикселя и которые дают более-менее непрерывный результат. Сюда входит изменение всех основных характеристик изображения: яркость, гамма, контрастность, насыщенность, теплота. Можно высветлять отдельно тени или затемнять светлые участки. Можно сконвертировать пиксели в другое цветовое пространство. Можно даже перевести в другое цветовое пространство, поменять там что-то, вернуться обратно. Собственно это и показано в примере в самом начале статьи.

И вишенка на торте: можно даже не знать, что делает функция трансформации, но если её можно вызвать, то из нее можно получить куб и использовать уже его для трансформации. Таким образом, с некоторыми ухищрениями, я смог достаточно достоверно реконструировать фильтры Инстаграма.

Что нельзя сделать с помощью трехмерных таблиц поиска, так это любые эффекты, которым нужен доступ к соседним пикселям. Никакие блюры, шарпы, свертки, эмбосы. Вы можете хоть виртуальную машину запускать для вычисления каждого пикселя в таблице поиска, но никакие пиксели кроме текущего вы рассматривать не вправе. С другой стороны, можно, например, заранее посчитать какую-то статистику по изображению (получить гистограмму, найти процент темных участков) и уже с учетом этой информации сделать функцию трансформации.


А как применять?

Довольно теории, теперь наконец расскажу как работать с цветовыми трансформации в Pillow. API таблиц поиска содержится в классе Color3DLUT модуля PIL.ImageFilter. Можно создать новую таблицу, если у вас есть готовые значения:

from PIL.ImageFilter import Color3DLUT

table = [(0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 1, 0),
         (0, 0, 1), (1, 0, 1), (0, 1, 1), (1, 1, 1)]
lut = Color3DLUT(2, table)

Первый параметр — размер таблицы в каждом измерении. Если размер по всем измерениям одинаков, можно передать просто число. После этого готовую таблицу можно применить к изображению:

from PIL import Image
Image.open('in.jpg').filter(lut).save('out.jpg')

В данном случае это единичная таблица, то есть её применение не приведет к изменению изображения. Но если вы поменяете местами какие-то элементы, то поменяются местами или инвертируются каналы изображения:

9ukso9kvfmfsjke56m2b4pnst3o.jpeg

Составлять таблицу — дело муторное и легко можно где-то ошибиться, поэтому у класса есть метод generate, который позволяет очень удобно работать с цветом. Метод принимает колбэк, которому передается цвет. Это напоминает пиксельные шейдеры в 3D-графике.

def transform(r, g, b):
    r, g, b = (max(r, g, b), g, min(r, g, b))
    avg_v = r * 0.2126 + g * 0.7152 + b * 0.0722
    r += (r - avg_v) * 0.6
    g += (g - avg_v) * 0.6
    b += (b - avg_v) * 0.6
    return r, g, b

lut = Color3DLUT.generate(17, transform)
Image.open('in.jpg').filter(lut).save('out.jpg')

-elgs566siqrqmtq_jyux8115fw.jpegby4xsfb38tvlvkrxu9cldttubgu.jpeg

В данном случае функция каким-то образом выбирает каналы, потом увеличивает насыщенность изображения. И тут возникает вопрос: неужели чтобы поменять какие-то базовые свойства изображения, нужно понимать как это все работает и возиться с формулами. Ну, на самом деле нет. Для таких случаев я написал вспомогательную библиотеку Pillow-lut. В частности там есть функция rgb_color_enhance, которая уже умеет создавать таблицы для изменения известных характеристик цвета:

from pillow_lut import rgb_color_enhance
lut = rgb_color_enhance(
    11, exposure=1, contrast=0.3, vibrance=-0.2, warmth=0.3)
Image.open('in.jpg').filter(lut).save('out.jpg')

-elgs566siqrqmtq_jyux8115fw.jpegb6wuvoxy2-frofcc_af1h5vyrq0.jpeg

Но, а если у вас уже есть готовая таблица трансформации, то как её хранить, не в коде же? Есть два распространенных формата: в .cube файлах (текстовые файлы, описывающие характеристики таблицы и содержащие десятичное представление значений) и hald-изображения — представление трехмерного куба, развернутое на двумерное пространство.


zdhzi6uf8ivnifryt9td3lz0kxw.png

И для обоих представлений в библиотеке Pillow-lut есть лоадеры.

from pillow_lut import load_hald_image 
lut = load_hald_image('hald.6.hefe.png')
Image.open('in.jpg').filter(lut).save('out.jpg')

-elgs566siqrqmtq_jyux8115fw.jpegyhaos73u0roagg46mtuykrebdjy.jpeg

Еще одно полезное свойство таблиц поиска — их элементы являются значениями пикселей, а так как с помощью таблиц поиска можно трансформировать значения пикселей, то с помощью одной таблицы можно трансформировать другую! То есть несколько операций, которые уже переведены в таблицы, можно сложить в одну. Та же функция rgb_color_enhance первым аргументом может принимать не только размеры для новой таблицы, но и другую, уже существующую таблицу:

lut = load_hald_image('hald.6.hefe.png')
lut = rgb_color_enhance(
    lut, exposure=1, contrast=0.3, vibrance=-0.2, warmth=0.3)
Image.open('in.jpg').filter(lut).save('out.jpg')

-elgs566siqrqmtq_jyux8115fw.jpeglkaafnt3qr9d3hrzcwgt5g-gira.jpeg

Таким образом, мы применяем к изображению обе трансформации за один раз. Но складывать таблицы можно не только с помощью rgb_color_enhance. В общем случае можно воспользоваться функцией transform_lut, которая принимает исходную и трансформирующую таблицы.

Ну и последнее, таблицу можно «усилить». Что это значит? Вот есть единичная таблица. Не в смысле, что все её элементы равны 1, а в смысле, что она ведет себя как единица — при трансформации ею изображение не меняется. Можно найти разницу между любой другой таблицей и единичной и эту разницу усилить. Этим занимается функция amplify_lut:

from pillow_lut import load_hald_image, amplify_lut
lut = load_hald_image('hald.6.hefe.png')
lut = amplify_lut(lut, scale=3.0)
Image.open('in.jpg').filter(lut).save('out.jpg')

-elgs566siqrqmtq_jyux8115fw.jpegzukyuhyb_2nvlap9fy7zn34kpp0.jpeg


Бенчмарки

Я повторю сказанное ранее: цветовые трансформации с помощью таблиц поиска применяются к любому изображению за постоянное время, какими сложными бы эти трансформации не были. Но тут возникает вопрос, насколько применение таблиц поиска вообще эффективно? Вдруг эта пресловутая постоянная скорость настолько низкая, что самый медленный код на Си для самой сложной трансформации все равно работал бы быстрее (я не беру в расчет Пайтон. Давайте будем реалистами: ничего не может работать медленнее обхода изображения по пикселям на Пайтоне).

Итак, в Pillow 5.4 была реализована трилинейная интерполяция между целочисленными 16-битными ячейками таблицы поиска (сейчас поясню каждое слово). Несмотря на распространенное заблуждение, целочисленная арифметика в современных процессорах все еще работает заметно быстрее арифметики с плавающей точкой. 16-битные значения позволили не терять точность.

Что касается трилинейной интерполяции, то она состоит из 7 линейных интерполяций для каждого канала пикселя. Это дает минимум 21 арифметическую операцию на канал пикселя. Существуют и другие виды интерполяции, например тетраэдрическая интерполяция, работающая в трехмерном пространстве. Её преимущество в том, что она требует меньше арифметических операций (от 6 на канал при специальной подготовке данных таблицы), но зато требует в среднем 2,5 ветвления на каждый пиксель и, по сути, является аппроксимацией. Я выбрал для реализации именно трилинейную интерполяцию, потому что она лучше векторизуется для SIMD-инструкций.

Реализаций трансформации цвета трехмерными таблицами поиска в других библиотеках я наскреб полторы штуки. Такая реализация точно есть в ImageMagick и GraphicsMagick. Еще один конкурент — LittleCMS — библиотека для чтения цветовых icc-профилей и применения их к изображениям. Она точно использует трехмерные таблицы поиска с тетраэдрической интерполяцией, но когда именно, не очень понятно. Я нашел цветовой профиль, при применении которого в топ perf, вышла функция PrelinEval8, по виду очень напоминающая то, что нужно.


qn80a3t3uv2rrpbqwyrtqo2eor8.png

Результаты на одном ядре процессора Intel Core i5–8279U.

Pillow-SIMD — это форк Pillow, в котором применяются векторные расширения x86 процессоров для существенного ускорения обработки графики. Форк является 100% совместимой заменой Pillow одинаковых версий. Вы, наверное, заметили, что Pillow я взял 5.4, а Pillow-SIMD версии 7.0. Это потому что сами таблицы поиска я сделал в Pillow довольно давно, а ускорение я доделал совсем недавно. Собственно поэтому статья немного задержалась.


Выводы

Как видно из результатов тестирования, трансформация цвета в Pillow работает быстрее, чем существующие решения, а с применением SIMD-инструкций улетает в космос. Надо сказать, что это все равно может быть медленнее, чем хорошо оптимизированная реализация довольно большого числа трансформаций, которые можно было бы написать на Си. Но на стороне таблиц поиска универсальность, простота и стабильное время вне зависимости от числа и сложности трансформаций. Простой API позволяет очень быстро начать пользоваться цветовыми трансформациями, а специальная библиотека Pillow-lut позволяет еще больше облегчить работу.

© Habrahabr.ru