Матированием (matting) называется отделение объекта переднего плана от фона на изображении. При этом требуется восстановить альфа-канал, т.е. получить точные значения прозрачности для полупрозрачных пикселей. Затем извлеченный объект можно наложить на другой фон или применить к нему какую-либо обработку, например, цветокоррекцию.

Постановка задачи

Задача: разложить изображение на фон (background), объект (foreground) и альфа-канал. При смешивании полученного фона с изображением объекта по альфа-каналу должно получиться исходное изображение.

Считаем, что смешивание осуществляется по следующей формуле [1]:

           (1)

где C - цвет пикселя исходного изображения, F - цвет пикселя объекта, B - цвет пикселя фона, α - коэффициент смешивания (0 ≤ α ≤ 1). Для изображений в градациях серого C, F, B - интенсивности, для цветных - векторы из компонент R, G, B.

Задача заключается в нахождении изображений F, B, α для данного изображения C. Затем выделенный объект можно наложить на новый фон, используя формулу смешивания (1).

Далее будем рассматривать только цветные изображения в формате RGB:

Векторное уравнение (1) соответствует системе из 3-х уравнений с 7-ю неизвестными (α, F_r, F_g, F_b, B_r, B_g, B_b). Задача является недоопределенной, поэтому требуются дополнительные ограничения, например:

• Цвет фона должен быть известен
• Пользователь помечает некоторые области, как относящиеся к фону или к объекту (см. раздел «Разметка»).

Система уравнений (1) и вышеприведенные ограничения задают условия для каждого пикселя независимо.

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

• Некоторые предположения о зависимости значений F, B от распределения цветов в окрестности пикселя ([11], [15], [17])
• Гладкость альфа-канала ([17])
• Гладкость F- и B-изображений ([16], [19])

Если стали известны два значения из набора F, B, α, то третий находится однозначно, кроме вырожденных случаев.

Входные данные

Большинство современных алгоритмов матирования работают со следующими входными данными:

• Исходное изображение
• Разметка (делается вручную или получается автоматически с помощью других алгоритмов машинного зрения)
• Известный фон (known background) - не обязателен, но некоторые алгоритмы позволяют уточнить результат, задав изображение фона без выделяемого объекта

Разметка

Разметка применяется (как уже говорилось выше) для «доопределения» задачи (уменьшения количества неизвестных). Указывая для части изображения значения a мы снижаем уровень неопределенности с которым придется справиться алгоритму. Обычно изображение разбивается на три области:

• Foreground - объект (α = 1)
• Background - фон (α = 0)
• Unknown - область, в которой α неизвестна (к этой области и будем применять алгоритм)

Изображение, задающее такую разметку, называется trimap.

Фактически для некоторых пикселей указывается, что в них α известна и равна 0 или 1. Некоторые алгоритмы позволяют также задать произвольные значения α от 0 до 1.

Разметка может иметь различную точность, которая определяется относительными размерами unknown-области. Пример:

а)	б)	в)
Рис. 2: Разметки различной точности: а) изображение, б) более точная разметка, в) менее точная разметка. Белый и черный цвета разметки обозначают области объекта и фона соответственно, серый цвет обозначает unknown-область.

Алгоритмы

Chroma Keying (Color Keying, Blue Screen Matting)

Это довольно старый метод, активно применяющийся в кинематографии. Требует съёмки объекта на однородном фоне определённого цвета (называемого ключевым - key color), при этом данный цвет должен отсутствовать в изображении объекта. Изначально Chroma Keying осуществлялся без помощи компьютера путём многократной пересъёмки киноплёнки с различными светофильтрами. Наиболее часто используется синий фон, отсюда название Blue Screen Matting. Второй по популярности фон - зелёный.

Существует несколько различных алгоритмов Chroma Keying'а. Разметка в таких алгоритмах не требуется - они работают только с изображением и заданным цветом фона. Они обрабатывают пиксели изображения независимо и основываются на эмпирических формулах, выражающих α через C. Простейшим примером такой зависимости является линейная комбинация цветовых каналов (для синего фона):

α = (r + g) / 2 - b

Результат отсекается по отрезку [0, 1]. Предполагается, что значения R, G, B также задаются на отрезке [0, 1]. Подобные методы накладывают ограничение не только на цвет фона, но и на цвет объекта: он не должен совпадать с цветом фона и, возможно, с каким-либо цветом, для которого используемый метод определяет значение α неверно (например, приведенная формула классифицирует все оттенки серого как фон).

Другой вариант, предложенный в [2] (для фона, являющегося линейной комбинацией синего и зелёного):

α = 1 - a₁(b - a₂g)

F_b = min(b, a₂g)

Здесь параметры a₁, a₂ настраиваются вручную. Синяя компонента цвета объекта (b_F) отсекается, остальные без изменения берутся из исходного изображения, т.е. F_r = r, F_g = g. Наиболее распространенные формулы, применяемые в коммерческих программах для Chroma Keying'а, приведены в статьях [3], [4].

Существуют и другие алгоритмы Chroma Keying'а. Некоторые из них, в отличие от приведенных, используют цветовое пространство HSV, как, например, High Quality Chroma Key [5].

а)	б)
Рис. 3: Пример Chroma Keying'а: а) исходное изображение, б) результат, наложенный на новый фон. Кадр из фильма "2 Fast 2 Furious".

Преимущество Chroma Keying'а заключается в возможности его работы в реальном времени, а также в возможности качественного извлечения теней, бликов и полупрозрачных объектов. Существуют аппаратные реализации алгоритмов Chroma Keying'а, работающие в реальном времени с видеосигналом (например, [6]).

Подобные эмпирические формулы используются в программах Ultimatte [6], Keylight [7].

Следует заметить, что если есть возможность сфотографировать объект два раза на фоне различного, но известного цвета, то задача перестает быть недоопределенной и её можно решить методом триангуляции [8]. На практике такой вариант применяется редко, но его используют для получения достоверных (ground truth) изображений альфа-канала для оценки качества результатов других методов.

Mishima [9]

Этот метод также применяется для Chroma Keying'а. Вместо задания явного цвета фона или числовых параметров, алгоритм получает на вход выборку цветов объекта и фона. Для выборки цветов фона строится описанный 48-гранник, а для выборки цветов объекта - вписанный и целиком содержащий многогранник фона.

Если цвет обрабатываемого пикселя лежит внутри многогранника фона или вне многогранника объекта, то α = 0 или 1 соответственно. В противном случае цвет проецируется на оба многогранника из точки, определяемой усредненным цветом фона. Точки проекций задают цвета F, B (см. рис. 4).

Идея этого алгоритма использована в программе Primatte [10].

Рис. 4. Иллюстрация работы алгоритма Mishima

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

Knockout

Для этого алгоритма требуется достаточно точная разметка. В идеале, его unknown-область должна содержать только пиксели, в которых 0 < α < 1. В алгоритме Knockout сначала вычисляются средние значения цвета по выборке цветов вдоль границы unknown-области (в окрестности обрабатываемого пикселя) - F и B’. Затем цвет B вычисляется как проекция цвета пикселя C на плоскость, проходящую через B’ перпендикулярно прямой FB’. Вычисляются 3 значения a для каждой из цветовых компонент в уравнении (1):

(2)

Это проиллюстрировано на рис. 5 в проекции на плоскость rg.

Итоговое значение α вычисляется как их взвешенная сумма с весами, равными знаменателю в формуле (2). Этот алгоритм реализован в программе Corel Knockout (также существует в виде плагина для Adobe Photoshop) и в самом Adobe Photoshop'е, начиная с версии 5.5, под названием Extract.

Рис. 5. Иллюстрация работы алгоритма Knockout

Время работы алгоритма - около 0.9 секунд для изображения 640x480 на процессоре 1500 MHz.

а)	б)
Рис. 6: Пример результата работы алгоритма Knockout на изображении рис. 1а: а) разметка, б) результат

Ruzon-Tomasi [11]

В этом алгоритме unkown-область разбивается на фрагменты. Вокруг каждого фрагмента строится прямоугольник, содержащий пиксели областей объекта и фона. Эти пиксели задают выборку для цветовой статистики. Выборки цветов объекта и фона разбиваются на кластеры, например с помощью алгоритма [12]. Каждый кластер представляет собой неориентированный гауссиан, т.е. описывается нормальным распределением с осями, параллельными осям координат (см. [13]). Распределение цветов объекта и фона представляется смесью данных гауссианов (см. [14]).

Далее рассматриваются все возможные пары гауссианов объекта и фона. Большинство таких пар отбрасывается на основе их взаимного расположения в цветовом пространстве.

Предполагается, что распределение цвета C также является смесью гауссианов, в которой каждый гауссиан лежит на отрезке, соединяющем центры гауссианов объекта и фона (рис. 7). Ковариационная матрица этого распределения тоже интерполируется между соответствующими матрицами гауссианов объекта и фона.

Рис. 7. Иллюстрация работы алгоритма Ruzon-Tomasi

Итоговым значением α считается то, при котором плотность вероятности P(C) в этом интерполированном распределении максимальна в точке C.

Итоговые цвета F и B вычисляются как взвешенные суммы центров кластеров объекта и фона, после чего они корректируются так, чтобы выполнялось соотношение (1).

а)	б)	в)
Рис. 8: Пример работы алгоритма Ruzon-Tomasi: а) исходное изображение, б) разметка, в) результат, наложенный на новый фон

 

а)	б)	в)
Рис. 9: Пример плохой работы алгоритма Ruzon-Tomasi на изображении рис. 1а c разметкой рис. 6а: а) результат алгоритма Ruzon-Tomasi, б) увеличенный фрагмент, в) фрагмент результата алгоритма Bayesian Matting (для сравнения)

Bayesian Matting [15]

Этот подход является развитием метода Ruzon-Tomasi, разметка также должна быть достаточно точной. Здесь цветовые выборки строятся отдельно для каждого пикселя. На каждом шаге обрабатываются пиксели вдоль границы unknown-области и эта область постепенно сжимается. В качестве выборки цветов объекта и фона используются данные из уже посчитанных на предыдущих шагах пикселей в окрестности обрабатываемого пикселя.

Рис. 10. Иллюстрация работы алгоритма Bayesian Matting

Цветовые выборки собираются по окрестности обрабатываемого пикселя и кластеризуются (авторы используют алгоритм [12], как и в методе Ruzon-Tomasi). Далее для каждой пары цветовых гауссианов объекта и фона вычисляются оптимальные значения F, B, α. В отличие от Ruzon-Tomasi, в качестве F и B выбираются не центры гауссианов, а точки, максимизирующие условную вероятность P(F,B,α|C). Таким образом, здесь используется метод максимального правдоподобия. Для оценки этой вероятности используется формула Байеса:

, (3)

где P(C|F,B,α) оценивается через расстояние между цветом C и смесью F, B с коэффициентом α по формуле (1),

P(F), P(B) оцениваются через плотность вероятности для гауссианов цветов объекта и фона,

P(α) игнорируется,

P(C) - константа относительно параметров максимизации.

Логарифмируя формулу (3) и убирая слагаемые, не влияющие на искомые параметры, получаем

,

где L(×) = log P(×).

Используются следующие оценки для L(C|F,B,α), L(F), L(B):

(параметр задается вручную),

,

где , - мат. ожидание и ковариационная матрица F-гауссиана,

L(B) - аналогично.

Если пар кластеров объекта и фона несколько, оптимальные параметры F, B и α вычисляются для каждой их пары, затем выбирается пара с максимальным значением правдоподобия (см. рис. 10).

Время работы - около 7 секунд для изображения 640x480 на процессоре 1500 MHz.

Пример работы алгоритма приведен на рис. 1 (для разметки с рис. 6а).

А)	б)	в)
Рис. 11: Пример плохой работы алгоритма Bayesian Matting: а) исходное изображение, б) разметка, в) результат + увеличенный фрагмент

Poisson Matting [16]

Взяв градиент уравнения (1) получаем:

∇C = (F - B)∇α + α∇F + (1  - α)∇B,

где - градиент.

Предполагая, что изображения фона и объекта являются гладкими, считаем величину

α∇F + (1 - α)∇B

пренебрежимо малой. Тогда

∇α ∼ ∇C / (F - B) (4)

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

Таким образом, необходимо лишь как-то оценить величину F - B в каждом пикселе изображения. Для этого в предложенном методе используются ближайшие пиксели из областей объекта и фона в разметке. Строится изображение, состоящее из значений F - B, которое затем размывается фильтром Гаусса. Для нахождения α решается вариационная задача

,

где Ω - unknown-область изображения.

Её решение сводится к решению задачи Пуассона

,

(где - оператор Лапласа, а - дивергенция)

с граничным условием Дирихле, требующим выполнения равенств α = 0 или α = 1 на границе unknown-области с областями фона и объекта соответственно.

Данный алгоритм является итерационным: после нахождения a изображение F - B уточняется с использованием пикселей, в которых α > 0.95 или α < 0.05.

В случаях, где слагаемым α∇F + (1 - α)∇B пренебречь нельзя, применяется Local Poisson Matting: это слагаемое моделируется операторами с настраиваемыми параметрами. Пользователь указывает небольшие области, в которых пересчитывается результат.

Приближение F - B распространением цвета с границ накладывает требование высокой точности разметки, аналогичной точности, требуемой для Knockout, Ruzon-Tomasi и Bayesian Matting.

Время работы алгоритма - 1.3 секунды на изображении 640x480 на процессоре 1500 MHz.

Рис. 12: Результат работы алгоритма Poisson Matting на изображении рис. 11а с разметкой рис. 11б - альфа-канал + увеличенный фрагмент

Belief Propagation [17]

Преимуществом данного алгоритма является возможность получения хороших результатов даже для разметок низкой точности - достаточно нескольких мазков, помечающих объект и фон. Бо́льшая часть изображения может являться unknown-областью.

Возможные значения α дискретизируются, например α¹ = 0, …, α²⁵ = 1. Используется цветовая статистика, аналогичная применяемой в алгоритме Bayesian Matting. Задача формулируется в виде минимизации энергии, определяемой формулой



где α_p - значение α в пикселе p, V_d - соответствие цветовой статистике, V_s - гладкость альфа-канала, p и q во втором слагаемом - соседние пиксели. Гладкость определяется как



с настраиваемым параметром σ_s.

Для решения задачи используется метод распространения доверия (belief propagation, см. [18]). Алгоритм итерационный - после нахождения F, B, a цветовая статистика уточняется, и шаг оптимизации применяется снова.

В каком-то смысле метод Belief Propagation эквивалентен Bayesian Matting с глобальным сглаживанием и цветовой статистикой, собираемой не по ранее обработанным пикселям, а по всей окрестности пикселя.

В исходном варианте алгоритм работает очень медленно (15-20 минут для изображения 640x480 на процессоре 1500 MHz), но авторы разработали иерархический вариант, работающий в 50 раз быстрее. Время указано для разметки низкой точности. При точных разметках алгоритм работает значительно быстрее.

Этот алгоритм (или его аналог, точной информации нет) реализован в плагине для Adobe Photoshop'а EZ Mask (www.digitalfilmtools.com/ezmask/)

Рис. 13: Результат работы алгоритма Belief Propagation: а) изображение с наложенной разметкой, б) результат

Closed Form Solution [19]

Этот алгоритм, аналогично алгоритму Belief Propagation, работает с разметкой низкой точности. Цветовая статистика не используется - альфа напрямую ищется из изображения.

Идея алгоритма основана на предположении, что цвета пикселей в малых фрагментах изображений F и B лежат примерно на одной прямой в пространстве RGB (являются линейной комбинацией двух цветов). Тогда a можно считать линейно зависящей от цвета в малом фрагменте изображения:

α_p ∼ αC_p + b (5)

Здесь p - любой пиксель рассматриваемого фрагмента, а значения a и b фиксированы для всего фрагмента. Для цветного изображения a - вектор, для изображения в градациях серого - число. Во втором случае

a = 1 / (F - B),

b = -B / (F - B).

В случае цветного изображения a, b также можно выразить через F и B. В качестве фрагментов изображения в алгоритме рассматриваются все окна размером 3x3 пикселя, принадлежащие изображению. Для нахождения α минимизируется функция



где ε - константа, определяющая сглаженность альфа-канала, w_j - окно 3x3 с центром в пикселе j.

В [19] показано, как можно при минимизации J(α, a, b) исключить a, b (выразив их через α) и свести задачу к решению системы линейных уравнений (при наборе условий α = 0, 1 в областях фона и объекта соответственно).

Для цветных изображений задача решается аналогичным образом. После нахождения α требуется найти F и B. На основе подобных рассуждений эта задача также сводится к решению линейной системы.

Для выполнения соотношения (5) для изображения в градациях серого требуется гладкость изображений F и B. В случае RGB-изображения это условие ослабляется - достаточно, чтобы в малых окнах цвета F лежали примерно на одной прямой и цвета B лежали примерно на одной прямой.

Время работы - около минуты для изображения 640x480 с разметкой низкой точности на процессоре 1500 MHz.

а)	б)	в)	г)
Рис. 14: Пример работы алгоритма Closed Form Solution: а) изображение с наложенной разметкой, б) результат, в) изображение с наложенной разметкой, г) результат

Выводы

Так как явных метрик для оценки алгоритмов матирования нет, сравнения обычно являются субъективными («на глаз»). Серьезные тестирования данных алгоритмов, по нашей информации, не проводились.

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

Так, алгоритмы, не использующие цветовую статистику (Poisson Matting, Closed Form Solution) хорошо подходят для изображений, в которых ни объект, ни фон не являются сильно текстурированными, то есть содержат малое количество различных цветов и плавные переходы между ними. Если цвета сильно варьируются, то более эффективными могут оказаться алгоритмы, использующие цветовую статистику (Bayesian Matting, Belief Propagation). Однако такие алгоритмы могут выдавать неверные края объекта, если цветовые статистики для объекта и фона перекрываются. В алгоритмах Knockout и Ruzon-Tomasi главной целью является быстродействие, поэтому используемая там цветовая статистика неоптимальна.

Алгоритмы Poisson Matting, Belief Propagation и Closed Form Solution в явной или неявной форме используют граничное условие - значения альфа-канала около границы unknown-области мало отличаются от заданных в разметке значений (α = 0 или 1) вдоль этой границы.

Belief Propagation можно рассматривать как улучшение Bayesian Matting. В обоих алгоритмах используется похожая цветовая статистика, но в Bayesian Matting цветовой выборкой являются уже обработанные пиксели, а в Belief Propagation (за счет итераций) - вся окрестность обрабатываемого пикселя.

Аналогично, Poisson Matting имеет некоторое сходство с Closed Form Solution, только в первом алгоритме значения F - B находятся приближенно в предположении их глобальной гладкости, в то время как в Closed Form Solution они входят в задачу как неизвестные, и их гладкость должна соблюдаться лишь в малых окрестностях.

Литература

1. T. Porter and T. Duff, "Compositing Digital Images", Computer Graphics Volume 18, Number 3 July 1984 pp 253-259.
2. P. Vlahos, "Electronic Composite Photography", U. S. Patent 3,595,987, July 27, 1971. Expired.
3. P. Vlahos, "Comprehensive Electronic Compositing System", U. S. Patent 4,100,569, July 11, 1978. Expired.
4. A. Dadourian, "Method and Apparatus for Compositing Video Images", U. S. Patent 5,343,252, August 30, 1994.
5. M. Ashihkmin, "High Quality Chroma Key", CS 294 Project Final Report
6. http://www.ultimatte.com/
7. http://www.thefoundry.co.uk/
8. A. Smith, J. Blinn, "Blue Screen Matting", In Proceedings of SIGGRAPH 96, pages 259-268, August 1996.
9. Y. Mishima, "Soft edge chroma-key generation based upon hexoctahedral color space", U.S. Patent 5,355,174, 1993.
10. http://www.primatte.com/
11. M. Ruzon and C. Tomasi, "Alpha estimation in natural images", in CVPR 2000, pages 18-25, June 2000.
12. M. T. Orchard and C. A. Bouman, "Color Quantization of Images", IEEE Transactions on Signal Processing, 39(12):2677-2690, December 1991.
13. http://ru.wikipedia.org/w iki/Многомерное_нормальное_распределение
14. http://en.wikipedia.org/wiki/Mixture_model
15. Y. Chuang, B. Curless, D. Salesin and R. Szeliski, "A Bayesian Approach to Digital Matting", Proc. of IEEE CVPR, pp. 264-271, 2001.
16. J. Sun, J. Jia, C.-K. Tang, and H.-Y. Shum. Poisson matting. ACM Trans. Graph., 23(3):315-321, 2004.
17. J. Wang and M. F. Cohen, An iterative optimization approach for unified image segmentation and matting, Int'l Conf. on Computer Vision, Beijing, Oct. 2005.
18. http://en.wikipedia.org/wiki/Belief_propaga tion
19. A. Levin, D. Lischinski,Y. Weiss, A Closed Form Solution to Natural Image Matting, IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), June 2006, New York