Software & Systems

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

Предположим, что исходное изображение C является смесью изображений F и B (объект переднего плана и фон соответственно) с каналом прозрачности a. В каждом пикселе должно удовлетворяться следующее условие:

C=aF+(1-a)B,                                                         (1)

где C, F и B – трехмерные векторы в цветовом пространстве RGB, 0£a£1. Задача состоит в получении a, F и иногда B по заданному исходному изображению C с использованием какого-либо дополнительного ввода со стороны пользователя.

Алгоритмы матирования получают на вход исходное изображение с разметкой. Обычно используется тернарная разметка – заданная пользователем сегментация изображения на три региона: объект переднего плана, фон и неизвестная (переходная) область. Первые две дают некую информацию об объекте, который необходимо извлечь, а последняя определяет регион применения алгоритма. Результатом алгоритма являются слой переднего плана с известным цветом и прозрачностью для каждого пикселя, а также слой фона. При смешивании эти слои должны в точности давать исходное изображение.

Разметка задает области с a=0 (B=C), a=1 (F=C) и неизвестными F, B, a. Следует заметить, что если два из трех этих значений известны, то третье может быть однозначно посчитано. Задача является сильно недоопределенной, так как для каждого цвета исходного изображения C существует бесконечное число комбинаций цветов объекта и фона. Чтобы сделать ее решаемой, требуется некоторая регуляризация.

Байесовский подход

Данный подход является одним из основных методов регуляризации. Применительно к задаче матирования он был впервые предложен в статье [1]. Пиксели обрабатываются начиная с границ регионов объекта/фона, шаг за шагом сужая неизвестную область. Пиксели, обработанные на предыдущих шагах, также учитываются в выборках объекта и фона в дополнение к пикселям из известных областей. В качестве цветовой модели используется множество ориентированных гауссиан. Алгоритм использует схему Байеса для максимизации правдоподобия значений F, B и a. Условная вероятность для F, B и a по наблюдаемому цвету C может быть переписана с помощью формулы Байеса:

,  (2)

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

Рассмотрим байесово матирование более подробно.

Взяв логарифм от (2) и опуская члены, не влияющие на параметры, которые нужно найти, получаем:

,  (3)

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

Авторы [1] используют следующие оценки для L(C|F, B, a), L(F), L(B):

(sC настраивается пользователем),

,

где  и SF являются математическим ожиданием и ковариационной матрицей гауссиана объекта переднего плана; L(B) аналогично L(F).

Взаимное расположение цветов F, B и a и соответствующих распределений проиллюстрированы на рисунке 1.

В случае нескольких пар кластеров объекта/ фона оптимальные F, B и a вычисляются для каждой пары и выбирается пара, дающая наибольшую величину правдоподобия L(F, B, a½ C).

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

Для константной a выводится следующая линейная относительно F и B система линейных алгебраических уравнений размером 6 на 6:

(4)

Для константных F и B результат для a является проекцией C на отрезок FB:

.                                           (5)

Вычисление F, B и a поочередным применением формул (4) и (5) продолжается до наступления сходимости.

Гладкость канала прозрачности

Байесов алгоритм матирования очень чувствителен к перекрытиям цветовых моделей объекта и фона. В исходном алгоритме это делает вычис- ление a нестабильным и часто приводит к су- щественному шуму в получаемом канале прозрачности. Использование простого размытия или медианного фильтра может улучшить канал прозрачности, но при этом маленькие детали объекта могут быть потеряны. Поэтому авторы предлагают в байесову схему добавить член, отвечающий за гладкость канала прозрачности [2].

Моделируем гладкость одномерным гауссианом с математическим ожиданием a0, равным среднему значению прозрачности по ранее обработанным пикселям, то есть тем же значением, что используется в качестве начального приближения для a при решении системы (4). Этот член, отвечающий за гладкость, вводится в (2) как P(a).

Используем следующее выражение для L(a):

.                                        (6)

Таким образом, максимизируем логарифмическое правдоподобие:

                         (7)

Приравнивая частные производные (7) по a нулю, получаем следующее выражение для a:

.                  (8)

Формула (8) заменяет формулу (5) в процессе минимизации.

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

                               (9)

где  и l настраиваются пользователем (в своих экспериментах авторы использовали , а  является расстоянием между двумя распределениями (авторы использовали расстояния между центрами гауссиан).

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

Чтобы сделать сглаживание менее равномерным и более согласованным с цветовыми изменениями, используем взвешенное среднее для a0 в пикселе q:

                                                (10)

где суммирование происходит по уже обработанным (или известным) пикселям в окрестности пикселя q со следующими весами (W является суммой всех wp для пикселя q):

.                                     (11)

Значение 0,2 для sw подбиралось эмпирически. Это же значение a0 используется в качестве изначального приближения для a в уравнении (4). Использование члена, отвечающего за гладкость, почти не влияет на время работы алгоритма.

Пример работы алгоритма с изображением приведен на рисунке 2.

Иерархический подход

Другим улучшением является иерархическое байесово матирование. Главной задачей этого улучшения было уменьшение времени работы алгоритма без потери качества матирования. Самым простым способом было бы применить байесово матирование к уменьшенному изображению, после чего увеличить изображение до исходного разрешения и выполнить байесово матирование еще раз, но со значительно меньшим радиусом выборки. Однако есть более эффективный способ: применяя иерархический подход Closed Form Solution [3] к результату байесова матирования, можно вычислить коэффициенты линейного приближения прозрачности значениями цвета для уменьшенного изображения и использовать их, чтобы увеличить канал прозрачности до исходного разрешения. Линейное приближение определяется коэффициентами a и b в следующем соотношении:

                                                       (12)

где p – пиксель в окне (размером, например, 3´3); a и b – фиксированные по окну коэффициенты. Для изображений в градациях серого коэффициенты a и b могут быть вычислены по следующим формулам:

a=1/(F–B), b=–B/(F–B).                                       (13)

Для цветных изображений их можно выразить через F и B (в данном случае a является трехмерным вектором):

                                                (14)

где k – индекс цветовой компоненты.

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

Получаем уменьшенное изображение билинейной интерполяцией. При вычислении уменьшенной разметки пиксель считается принадлежащим объекту/фону, если все соответствующие пиксели разметки исходного разрешения принадлежат объекту/фону, в противном случае пиксель помечается как неизвестный. Значения параметров байесова матирования, таких как сигма, используемая для пространственного взвешивания выборки, тоже уменьшаются. Байесово матирование выполняется на уменьшенном изображении/раз­метке и выдает изображения a, F и B. Эти изображения нужно увеличить до исходного разрешения. Для канала прозрачности a и для каждого канала изображений F и B (но будем обозначать обрабатываемый канал как a) применим следующую процедуру.

1.     Вычислить коэффициенты a и b для каждого пикселя уменьшенного изображения с помощью метода наименьших квадратов по окну 3 на 3, как в уравнении (3).

2.     Увеличить карты коэффициентов, используя билинейную интерполяцию.

3.     Вычислить увеличенное изображение a (исходного разрешения), применяя уравнение (3) к исходному изображению C и коэффициентам a и b из увеличенных изображений коэффициентов, полученных на шаге 2.

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

Применение байесова матирования к изображениям меньшего разрешения дает нелинейное ускорение, поскольку уменьшается не только число обрабатываемых пикселей, но и области поиска образцов цветов F, B. При небольших коэффициентах масштабирования (≤4) качество матирования практически не изменяется.

Интерактивное матирование изображений

Выше был описан алгоритм вычисления канала прозрачности на основе исходного изображения и тернарной разметки. Теперь рассмотрим процедуру создания такой разметки пользователем [4].

Вначале пользователю предлагается построить жесткую (бинарную) разметку, используя мазки кистями объекта и фона. Для этого используется алгоритм GrowCut. Целью данного шага является построение точной сегментации четких контуров и приближенной сегментации мягких областей.

Затем генерируется переходная область тернарной разметки морфологическим сжатием областей объекта и фона. Радиус сжатия выбирается пользователем и может быть изменен в реальном времени. Задача пользователя – настроить ширину переходной области так, чтобы были покрыты все четкие края с учетом их средней размытости.

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

1.     Пользователь рисует фрагмент границы нечеткой области внутри объекта или фона.

2.     Концы границы соединяются с существующей переходной областью. Для поиска кратчайшего соединяющего пути в изображении используется алгоритм Дейкстры.

3.     Концы найденных путей соединяются между собой, чтобы образовать замкнутую область. Для этого ищется путь от одного конца до другого внутри неизвестной области. Если он не найден (такое возможно, если неизвестная область не является односвязной), действие отменяется.

4.     Полученная область, состоящая из пользовательской траектории, двух соединений и внутреннего соединения, помечается как переходная.

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

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

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

Численное сравнение

Данный метод использовался на 27 изображениях из тестовой базы [5], в которой для каждого изображения есть две тернарные разметки (Trimap1 и Trimap2) – более точная и менее точная (с большей толщиной неизвестной области). Улучшенный алгоритм сравнивался с исходным алгоритмом байесового матирования [1]. Результаты сравнения приведены в таблице.

Из таблицы видно, что наибольшее улучшение достигается на наборе с менее точной разметкой. В этом случае сложнее найти границу объекта, пользуясь только цветовой информацией, поэтому условие гладкости альфа-канала улучшает результат (пример численного сравнения приведен на рисунке 3).

Алгоритм матирования и интерактивный процесс (включающий создание разметки и редактирование результата) реализованы авторами в программе GrowCut, которая является подключаемым модулем к программе Adobe Photoshop.

В заключение отметим, что в данной статье предложен новый алгоритм интерактивного матирования изображений. Алгоритм основан на байесовом методе матирования, но с добавлением условия гладкости результирующего канала прозрачности a. Интерактивная процедура матирования изображений упрощает и ускоряет процесс извлечения объекта переднего плана на изображении, комбинируя бинарную сегментацию (для более точного поиска жестких границ) и мягкое матирование со сглаживанием.

Литература

1.     Chuang Y.-Y., Curless B., Salesin D., Szeliski R. A Bayesian Approach to Digital Matting. Proc. of IEEE CVPR, 2001, pp. 264–271.

2.     Sindeev M., Konushin V., Vezhnevets V. Improvements of Bayesian Matting. Proc. of Graphicon, 2007, pp. 88–95.

3.     Levin A., Lischinski D., Weiss Y. A Closed Form Solution to Natural Image Matting., Proc. of IEEE CVPR, 2006, pp. 61–68.

4.     Sindeev M., Konushin V. A Novel Interactive Image Matting Framework. Proc. of Graphicon, 2008, pp. 41–44.

5.     Rhemann C., Rother C., Wang J., Gelautz M., Kohli P., Rott P. A Perceptually Motivated Online Benchmark for Image Matting. Proc. of IEEE CVPR, 2009, pp. 1826–1833.