автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование и разработка алгоритмов матирования видеопоследовательности

На правах рукописи

Синдеев Михаил Сергеевич

Исследование и разработка алгоритмов матирования видеопоследовательности

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

ооьиээ—

1 г , и

Москва - 2013

005059407

Работа выполнена в Институте прикладной математики им. М.В.Келдыша РАН.

Научный руководитель:

кандидат физико-математических наук, доцент Баяковский Юрий Матвеевич, доцент, ф-т ВМиК Московского государственного университета им. М.В.Ломоносова

Официальные оппоненты:

Соколов Сергей Михайлович. Профессор, д. ф.-м. н., зав. сектором. Институт прикладной математики им. М. В. Келдыша РАН.

Сафонов Илья Витальевич, доцент, к. т. н., Московский инженерно-физический институт.

Ведущая организация:

Московский государственный технический университет им. Н. Э. Баумана

Защита состоится «21 » мая 2013 г. в 11 часов на заседании диссертационного совета Д 002.024.01, созданного на базе Института прикладной математики имени М.В.Келдыша РАН по адресу: 125047, Москва, Миусская пл., 4.

С диссертацией можно ознакомиться в библиотеке Института прикладной математики им. М.В.Келдыша РАН.

Автореферат разослан «у* »апреля 2013 г.

Учёный секретарь диссертационного совета, д.ф.-м.н.

с/

[олилова Т. А.

Общая характеристика работы

Объект исследования и актуальность работы

В работе рассматривается задача матирования - выделения объектов в изображении или видеопоследовательности с целью монтажа, т.е. последующего наложения объекта на новый фон. Решение задачи матирования заключается в вычислении маски прозрачности, называемой «альфа-каналом», и цвета каждого пиксела объекта. Критерием качества матирования является незаметность монтажа для зрителя.

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

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

Матирование занимает важное место в профессиональной обработке видео и кинопроизводстве и применяется для замены/модификации фона, цветокоррекции отдельных объектов, а также для преобразования видео в стереоскопический (ЗБ) формат.

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

На рис. 1 показан пример кадра из видеопоследовательности, альфа-канал (маска прозрачности) и результат наложения на новый фон.

Рисунок 1. Пример матирования кадра из видеопоследовательности

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

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

Цель диссертационной работы

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

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

Научная новизна работы

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

Практическая значимость и реализация

В рамках работы были реализованы программные модули, которые могут быть использованы как независимо, так и в комплексе. Алгоритм матирования

изображений на основе байесовского подхода реализован в виде подключаемого модуля «GrowCut 3.0» к программе Adobe Photoshop. Данный модуль позволяет в интерактивном режиме строить и уточнять канал прозрачности для выделения объекта на изображении. Также реализованы модули вычисления оптического потока, сегментации и матирования видеопоследовательности.

На основе данных модулей реализована программная система для матирования видеопоследовательности на языках Matlab и С++. Предложенный алгоритм разрабатывался в рамках проекта с компанией «Microsoft Research Cambridge».

Апробация работы

Результаты работы докладывались и обсуждались на

• 17-ой международной конференции по компьютерной графике и машинному

зрению «Graphicon'2007», Россия, Москва, 2007

• 18-ой международной конференции по компьютерной графике и машинному зрению «Graphicon'2008», Россия, Москва, 2008

• 19-ой международной конференции по компьютерной графике и машинному зрению «Graphicon'2009», Россия, Москва, 2009

• 16-й международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009»

• 5-й летней школе Microsoft для аспирантов (Microsoft Research PhD Summer School), Великобритания, г. Кембридж, 2010

• семинаре группы компьютерного зрения Microsoft Research, 23 июля 2010), Великобритания, г. Кембридж, 2010

• 22-ой международной конференции по компьютерной графике и машинному зрению «Graphicon'2012», Россия, Москва, 2012

• Семинаре по компьютерной графике и машинному зрению Ю.М. Баяковско-го (ф-т ВМК МГУ)

• Семинаре направления «Программирование» им. М. Р. Шура-Бура в ИПМ им. М. В. Келдыша РАН

Публикации

По теме диссертации автором опубликовано 7 научных работ, в т.ч. 2 в журналах ВАК [6], [7]. Статья, посвященная предложенному алгоритму матирования видеопоследовательностей, была принята на ведущую международную конференцию ACCV-2012 и опубликована в журнале Lecture Notes in Computer Science издательства Springer [7].

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Содержание работы изложено на 116 страницах. Список литературы включает 84 наименования. В работе содержится 43 рисунка и 3 таблицы.

Содержание работы

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

Рассмотрены ограничения на исходные данные. Предполагается, что на вход алгоритма подается видеопоследовательность длиной примерно до 10 секунд в цветовом формате RGB. В ней должен присутствовать явный объект переднего плана, т.е. предполагается, что сцена снята оператором (человеком), который может контролировать процесс съемки с учетом того, что затем потребуется выделять объект из видео. Объект должен быть виден на протяжении всей видеопоследовательности. В кадре не должно быть резких движений, изменений освещенности и резкой смены видимого изображения объекта. Разрешение до 1280x720, частота кадров - 24-25. Обрабатываемый видеофрагмент должен быть доступно целиком, т.е. работа в реальном времени не осуществляется.

В

I a F

Рисунок 2. Уравнение смешивания.

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

Для видеопоследовательностей с объектом переднего плана справедлива модель формирования изображения на основе уравнения смешивания С = аР+(1-ог)В. Формулируется задача восстановления канала прозрачности а и изображений Б, В, если известно только изображение С. Уравнение смешивания проиллюстрировано на рис. 2.

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

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

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

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

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

Рисунок 3. Схематичное изображение видеопоследовательности с двумя ключевыми кадрами

В первой главе рассматривается задача матирования изображений. Это требуется для матирования ключевых кадров, а также как основа алгоритма матирования видеопоследовательности. Формулируется понятие тернарной разметки как формата пользовательского ввода для уточнения задачи (см. рис. 4).

Рисунок 4. Пример тернарной разметки для изображения.

Затем рассматривается предложенный автором модифицированный алгоритм матирования, основанный на байесовском подходе1:

píf в g i а - Р(С 1F'в'

р(с)

Р(а) моделируется нормальным распределением с мат. ожиданием, вычисленным по соседним уже обработанным пикселам и дисперсией, вычисленной как мера близости распределений P(F) и Р(В). Для вычисления мат. ожидания Р(а) предложена сортировка пикселов по цветовой близости с уже обработанными пикселами.

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

Для ускорения вычислений применен иерархический подход с использованием идеи метода аналитического матирования" для ускорения вычислений.

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

Проведена количественная оценка4 точности предложенного метода и продемонстрированы преимущества предложенного метода по сравнению с исходным вариантом байесовского алгоритма. Описана реализация алгоритма в виде подключаемого модуля к программе Adobe Photoshop.

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

1 Chuang Y., Curless В., Salesin D„ Szeliski R. A Bayesian Approach to Digital Matting // In proc. of CVPR. 2001. P. 264-271

2 Levin A., Lischinski D„ Weiss Y. A Closed Form Solution to Natural Image Matting // In proc. of CVPR. 2006. P. 61-68

3 Vezhnevets V., Konouchine V. Grow-Cut - Interactive Multi-Label N-D Image Segmentation by Cellular Automata // In proc. of Graphicon. 2005. P. 150-156

4 Тестовая база: Rhemann С., Rother С., Wang J., Gelautz M„ Kohli P., Rott P. A Perceptually Motivated Online Benchmark for Image Matting// In proc. of CVPR. 2009. P. 1826-1833. http://www.alphamatting.com/

(а) (б) (в) (г) (д) (е)

Рисунок 5. Иллюстрация идеи алгоритма: (а, б) первый и последний кадры фрагмента, (в) маски, соответствующие этим кадрам, (г) контур в первом кадре, (д) два способа переноса контура на последний кадр - в предположении, что контур лежит на поверхности, и в предположении, что контур является видимой границей объекта, (е) результат алгоритма SnapCut3 - видно, что данный алгоритм предполагает принадлежность контура поверхности, что неверно.

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

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

• использованием обычного оптического потока с небольшим весом

• использованием алгоритма матирования изображений, обобщенного на видеопоследовательность с учетом перекрытий (этот подход изложен в четвертой главе)

Схема алгоритма приведена на рис. 6. Алгоритм использует обычный оптический поток в цветовых каналах RGB в качестве начального приближения. Затем после матирования он уточняется за счет использования альфа-канала. RGB каналы также используются в качестве регуляризации, но с меньшим весом.

В главе предлагается следующая формулировка целевого функционала задачи матирования:

где М - бинарная маска перекрытий,

р - условие разреженности маски перекрытий,

] - целевой функционал матирования для каждого кадра,

5 Bai X., Wang J., Simons D„ Sapiro G. Video SnapCut: robust video object cutout using localized classifiers // Inproc. of SIGGRAPH. 2009. P. 1-11

—- производная вдоль вектора потока V.

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

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

Рисунок 6. Схема предложенного алгоритма матирования видео

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

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

Оптическим потоком называется векторное поле видимого движения пикселей между кадрами. Задача его поиска формулируется так: по данной паре изображений 1ь 12 построить оптический поток (и, у), совмещающий эти изображения:

А (*> у) ~ к (х + и(х, у), у + у{х, у)).

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

6 Alvarez L„ Esclarin J., Lefebure M„ Sanchez J., A PDE model for computing the optical flow // In proc. of XVI Congreso de Ecuaciones Diferenciales y Aplicaciones. 1999. P. 1349-1356

w)=Я

dxdy.

Помимо непрерывных методов также существуют дискретные, основанные на переборе вектора сдвига (и, у) по множеству {-М, ..., М}2, где М - максимальный сдвиг.

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

dx dy.

Устремляя параметр 0 к бесконечности, получим минимум данной энергии, в котором и = V, и достигается совместный минимум слагаемых данных и гладкости. Минимизация производится итерационно с увеличением параметра 0. Каждое из слагаемых само по себе эффективно минимизируется предназначенным для него алгоритмом.

Слагаемое данных минимизируется переборным алгоритмом на основе алгоритма Ра1сНМа1:сЬ7. Вместо фрагментов изображения используются единичные пикселы, т.к. за пространственную когерентность отвечает слагаемое гладкости потока. Основная идея метода - оптимизация процедуры перебора гипотез векторов оптического потока. Пусть область поиска имеет размер МхМ. Тогда вместо перебора М" значений в каждом пикселе осуществляется выбор одного случайного значения в каждом пикселе, а затем используется двухпроходное распространение решения на соседние пиксели. Ввиду пространственной когерентности (обусловленной как структурой естественных изображений, так и непосредственно слагаемым гладкости) многие связные области пикселов имеют почти одинаковые значения потока, поэтому если оптимальный вектор найден хотя бы в одном пикселе области, он распространится на всю область. Шаблон обработки пикселов показан на рис. 7.

Поток в канале прозрачности получается заменой I на а: •ц2

елп=JJ

dxdy.

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

■||2

где Wrgb - вес цветовых каналов.

dxdy,

1 Barnes C„ Shechtman E., Finkelstein A., Goldman D. PatchMatch: A randomized correspondence algorithm for structural image editing // Communications of the ACM. 2011. V 54, N 11. P. 103-110

(а) ^ (б) (в)

Рисунок 7. (а) Полный перебор (М2 возможных векторов в каждом пикселе). (Б) Перебор методом Ра^ЬМа^Ь - вектор потока выбирается из 5 кандидатов при прямом проходе (текущий пиксел и 4 ранее обработанных пиксела). (В) шаблон обратного прохода.

Второй предложенный алгоритм - траекторный поток - является более точным, чем первый, но более медленным. Основная идея алгоритма заключается в использовании нескольких кадров сразу для нахождения перекрытий и уточнения слагаемого данных. В данном алгоритме рассматривается Т = 2К + 1 кадров с номерами -К, ..., К. Финальным результатом является оптический поток из кадра 1о в 1[ и обратный поток из 10 в 1_ь но при этом в качестве промежуточного результата находятся 2К потоков из 10 в остальные кадры. В каждом пикселе кадра 1о эти потоки образуют траекторию.

Т.к. потоки вычисляются относительно кадра 10, их можно считать одним «траекторным» потоком, где каждому пикселу сопоставлен 4К-мерный (или, что то же самое, 2(Т - 1)-мерный) вектор потока

V = (и_к, у_к..„ и_„ У_1, ир V,, ..., ,ик, V,.).

Такое векторное представление позволяет использовать любые известные функционалы гладкости, определенные для двухмерного потока, которые могут быть сформулированы в терминах векторной алгебры, а также многие алгоритмы минимизации данных функционалов. Исключением будут алгоритмы, явно использующие факт двухмерности, а также алгоритмы, несовместимые с членом данных Ев (однако их часто можно адаптировать для данной задачи, либо использовать методы раздельной оптимизации, используя другой алгоритм для члена данных). Кроме того, стохастические и переборные алгоритмы могут потерять свою эффективность из-за увеличения пространства поиска. Метод тра-екторного потока использует следующий функционал энергии: Е(Г,р)= е0(у,р)+ ле,(у) + мегС) + ие,0>).

в котором слагаемое данных определено с учетом видимости:

^(Ф.уУФ+ипУ+у,)?'

к Л У

1*0

слагаемое пространственной гладкости уравнивает разброс значений по разным кадрам, путем деления на |1|:

при этом норма градиента является инвариантной к повороту при 7=0,5, что в двухмерном случае записывается как

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

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

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

Для минимизации функционала энергии используется метод глобальной оптимизации ОРВО8 со структурой графа, показанной на рис. 9. Данный метод является бинарным и «склеивает» решения-кандидаты. В работе предложено несколько эвристик для генерации такого решения. Часть из них заключается в небольшом возмущении текущего решения (например, сдвиг на 1 пиксел по оси х), другая часть осуществляет локальную оптимизацию неполного функционала энергии (включающего не все слагаемые).

В частности, предложено применение метода Ра1сЬМа1сЬ непосредственно к траекториям. Также предложено усовершенствование этого метода: вместо выбора наилучшего кандидата V по шаблону из 5 пикселов предлагается строить новое решение, вообще говоря не совпадающее с этими 5 кандидатами (но совпадающее с одним из них в каждом кадре). Для этого используется алгоритм динамического программирования. Метод проиллюстрирован на рис. 10.

8 C. Rother, V. Kolmogorov, V. Lempitsky, M. Szummer. Optimizing binary MRFs via extended roof duality.

1 x у 1

На маску видимости также наложено условие гладкости:

еМ=Т.Т.Ы*.у)У>

cvpr, 2007.

Рисунок 8. Искусственные одномерные примеры траекторного потока. Показаны исходные одномерные видеопоследовательности (Т = 9 кадров, по вертикали - ось времени) и найденные траектории. Толстые части траекторий - диапазоны видимости.

У(х.у).Е,

Рисунок 9. Структура графа для совместной минимизации V и р методом

Орво.

Риуснок 10. Обобщение алгоритма Ра^ЬМагсЬ для траекторий: (а) оптический поток - выбор наилучшего вектора из 5 кандидатов; (б) траекторный : - синтез новой траектории на основе 5 кандидатов.

поток

Риуснок 11. Результаты на тестовой базе 1Шск11еЬигу. (а-г) изображения и полученный оптический поток, (д) цветовой ключ визуализации потока.

Экспериментальная оценка метода проводилась на тестовой базе ]УЫс11е-Ьигу9. Примеры приведены на рис. 11.

В четвертой главе описывается алгоритм матирования видеообъема. За основу взят алгоритм аналитического матирования изображения и предложено его обобщение на произвольный граф. Предложено разбиение видеообъема на временные суперпикселы как способ построения такого графа по видеопоследовательности и оптическому потоку (см. рис. 12). Данный подход учитывает возможные перекрытия, т.е. неявным образом задает функционал р(М, I, V) в энергии Е(У, а, М).

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

Для построения суперпикселов предложен жадный алгоритм минимизации энтропии. Каждый суперпиксел хранит:

• средний цвет ц, дисперсию сГ

• начало 11, длительность т. Каждый пиксел суперпиксела хранит:

• цвет относительно ц

• координату х(1), у(1).

Тогда, используя принцип минимальной длины описания, можно потребовать от разбиения видеообъема на суперпикселы минимальность их общей энтропии Н = Н/, + т-Нр + т-Нс,

где Нц - число битов для хранения среднего цвета и дисперсии (константа),

9 S. Baker, D. Scharstein. J. Lewis, S. Roth, M. Black. R. Szeliski. A Database and Evaluation Methodology for Optical Flow. International Journal of Computer Vision. Volume 92, Number 1. 2011.

Рисунок 12. Построение временных суперпикселов, (а) Одномерное видео. Голубым показаны неиспользованные векторы потока, синим - суперпикселы (в т.ч. вырожденные), (б) иллюстрация случая двухмерного видео. Лапласиан видеообъема строится на основе показанных связей и двухмерных связей соседних пикселов в каждом кадре.

(а) (б)

Рисунок 13. Иллюстрация разбиения на суперпикселы: (а) кадр видеопоследовательности, (б) длины траекторий (в кадрах), проходящих через пикселы этого кадра.

Нр - число битов для кодирования координат одного пиксела (х(1), у(^) - также константа,

Нс - число битов для хранения отклонения цвета пиксела от среднего цвета ц в предположении, что это отклонение подчиняется нормальному распределению с дисперсией а".

Энтропия нормального распределения определяется как Нс. (сг) = — 1п (2 лест2).

пиапга щаикдд ддд

Рисунок 14. Результаты работы алгоритма. Вверху: ключевые кадры и промежуточный кадр. Внизу: результат для промежуточного кадра.

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

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

За счет совместного использования предложенного метода поиска оптического потока, суперпикселов для поиска перекрытий, а также ключевых кадров, можно обрабатывать видеопоследовательности с межкадровым движением около 15-20 пикселов (при разрешении 640x480), что в 3-4 раза превосходит соответствующую оценку для метода Лукаса-Канаде10, равную 5 пикселов на кадр.

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

= >>,*) - площадь объекта,

Х>У

Л*(') = - площадь объекта в эталонной разметке,

Х>У

А(г) = кА{{)+ Ь - нормализованная площадь объекта путем оптимизации

10 Lucas B., Kanade T. An iterative image registration technique with an application to stereo vision // Proceedings of Imaging Understanding Workshop. 1981. P. 121 - 130

£ (3(<) ■- A" (t)J min по к, b

7J

1 о

— - финальная метрика стабильности.

dt dt

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

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

Таблица 1. Численное сравнение алгоритмов

Алгоритм Оценка дрожания Квадратичная ошибка

Предложенный алгоритм 232,9 1418,7

Алгоритм отслеживания [Tsai 2010] 481,5 2068,1

Video SnapCut 614,9 8201,1

Объемный алгоритм CFS 1051,7 25612,7

Video Object Cut&Paste 1719,4 14060,3

В заключении перечислены основные результаты работы.

Основные результаты работы

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

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

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

3. Разработаны и реализованы новые алгоритмы вычисления оптического потока, позволяющие ускорить и повысить качество матирования видео.

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

5. Разработана метрика и реализован модуль для оценки качества матирования.

Публикации по теме диссертации

1. Sindeyev M., Konushin V., Vezhnevets V. Improvements of Bayesian Matting // Proc. of Graphicon. 2007, P. 88-95

2. Sindeyev M., Konushin V. A Novel Interactive Image Matting Framework // Proc. of Graphicon. 2008, P. 41^4

3. Sindeyev M., Konushin V. A Novel Approach to Video Matting using Optical Flow // Proc. of GraphiCon. 2009, P. 340-343

4. Синдеев M., Конушин В. Матирование видео на основе оптического потока // Сборник тезисов XVI Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009», секция «Вычислительная математика и кибернетика». 2009. С. 75

5. Синдеев М., Конушин А., Ротер К. Многокадровый оптический поток на основе траекторий. Труды конференции Графикон. 2012. С. 288-291

6. Синдеев М., Конушин В. Интерактивное байесовское матирование изображений // Программные продукты и системы. 2012. N 4. С. 167-171

7. Sindeev M., Rother С., Konushin A. Alpha-Flow for Video Matting // Asian Conference on Computer Vision (ACCV) 2012, Part III, Lecture Notes in Computer Science, 2013, Volume 7726, P. 438^152

Личный вклад автора

Все результаты, составляющие основное содержание диссертации, получены автором самостоятельно. В работах [1, 2, 6] автору принадлежат идеи условия гладкости прозрачности в байесовской модели, упорядоченной обработки пикселов по цветовой близости, иерархической обработки, инструмента построения тернарной разметки на основе алгоритма Дейкстры и инструментов редактирования канала прозрачности с пересчетом цветовых каналов. В работах [3, 4] автором предложен новый алгоритм совместного вычисления оптического потока и канала прозрачности по одному ключевому кадру. В работе [5] автором предложен новый алгоритм вычисления оптического потока. В работе [7] автором предложен новый алгоритм совместного вычисления оптического потока и канала прозрачности по двум ключевым кадрам, а также алгоритм сегментации видеопоследовательности на временные суперпикселы и алгоритм быстрого вычисления оптического потока на основе раздельной оптимизации.

Подписано в печать 16.04.2013. Формат 60x90/16. Усл. печ. л. 1,0. Тираж 70 экз. Заказ А-04. ИПМ им.М.В.Келдыша РАН. 125047, Москва, Миусская пл., 4

Институт прикладной математики имени М. В. Келдыша Российской академии наук

04201356356

На правах рукописи

Синдеев Михаил Сергеевич

Исследование и разработка алгоритмов матирования

видеопоследовательности

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание учёной степени кандидата физико-математических наук

Москва-2013

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ...................................................................................................2

ВВЕДЕНИЕ.........................................................................................................5

СОДЕРЖАНИЕ РАБОТЫ ПО ГЛАВАМ..........................................................15

1. Алгоритм матирования изображений..........................................................................................16

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

1.2. Алгоритм аналитического матирования................................................................................20

1.3. Предлагаемый алгоритм.........................................................................................................23

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

1.5. Сортировка пикселов по цветовой близости........................................................................26

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

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

1.8. Численное сравнение..............................................................................................................33

1.9. Программная реализация........................................................................................................34

1.10. Заключение..............................................................................................................................35

2. Матирование видео по ключевым кадрам..................................................................................36

2.1. Существующие подходы........................................................................................................37

2.2. Основные проблемы существующих методов......................................................................42

2.3. Общая идея предлагаемого алгоритма..................................................................................44

2.4. Функционал энергии...............................................................................................................49

2.5. Заключение..............................................................................................................................51

3. Вычисление оптического потока...................................................................................................52

3.1. Основные подходы к вычислению оптического потока......................................................53

3.2. Предлагаемый двухкадровый алгоритм................................................................................58

3.2.1 Ограничения на входные данные.....................................................................................60

3.2.2 Экспериментальная оценка...............................................................................................61

3.2.3 Время работы.....................................................................................................................62

3.3. Предлагаемый траекторный алгоритм...................................................................................64

3.3.1 Минимизация.....................................................................................................................67

3.3.2 Начальное приближение...................................................................................................68

3.3.3 Решения-кандидаты...........................................................................................................69

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

3.3.5 Результаты..........................................................................................................................72

3.3.6 Возможное упрощение......................................................................................................73

4. Матирование видеообъема с учетом перекрытий......................................................................75

4.1. Принцип минимальной длины описания..............................................................................78

4.2. Временные суперпикселы.......................................................................................................80

4.3. Матирование на основе суперпикселов.................................................................................89

4.3.1 Граничные условия............................................................................................................91

4.3.2 Сравнение с другими методами сегментации.................................................................91

4.4. Фильтр разреженности............................................................................................................92

4.5. Программная реализация........................................................................................................93

4.6. Результаты................................................................................................................................95

4.6.1 Вклад отдельных слагаемых.............................................................................................95

4.7. Сравнение.................................................................................................................................97

4.7.1 Численное сравнение.........................................................................................................98

4.7.2 Метрика сравнения............................................................................................................98

4.7.3 Устойчивость к ошибкам в ключевых кадрах...............................................................101

ЗАКЛЮЧЕНИЕ................................................................................................103

СПИСОК РИСУНКОВ.....................................................................................104

ЛИТЕРАТУРА.................................................................................................110

Данная работа посвящена задаче матирования - выделения объектов в изображении или видеопоследовательности с целью монтажа, т.е. последующего наложения объекта на новый фон. Решение задачи матирования заключается в вычислении маски прозрачности, называемой «альфа-каналом», и цвета каждого пиксела объекта. Критерием качества матирования является незаметность монтажа для зрителя.

В настоящее время для выделения объектов в видеопоследовательности используется процедура «ротоскопирования» ([22], [61], [83], [84]), требующая ручного построения контура объекта. Предлагается новый метод вычисления оптического потока в альфа-канале для автоматизации задачи матирования. Метод основан на совместном нахождении оптического потока и маски прозрачности итерационной оптимизацией. Предложен алгоритм быстрого вычисления оптического потока и алгоритм матирования видео при фиксированном потоке с учетом перекрытий. Для сегментации ключевых кадров предложен алгоритм вычисления прозрачности на основе байесовского подхода.

ВВЕДЕНИЕ

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

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

I = aF+(\-a)B, (1)

где /, F и В - трехмерные векторы в цветовом пространстве RGB, 0 < а < 1. Задача состоит в получении a, F и иногда В по заданному исходному изображению / с использованием какого-либо дополнительного ввода со стороны пользователя (без этого невозможно определить, какой объект требуется выделить). На рис. 1 показан пример такого разложения.

Следует заметить, что если два из трех значений (F, В, а) известны, то третье может быть однозначно посчитано. Задача является сильно недоопре-деленной, т.к. для каждого цвета исходного изображения / существует бесконечное число комбинаций цветов объекта и фона. Для того, чтобы сделать её решаемой, требуется некоторая регуляризация.

1 к = П X + й X

~ ш " * L 1 ■ 1 ■ ■nib

«1

I a F 1 - а В

Рисунок 1. Уравнение смешивания

Задача матирования возникла в художественной фотографии довольно давно, и долгое время решалась трудоемкими аналоговыми методами. Широкое применение матирование нашло в кино: неподвижные или подвижные (покадровые) маски («маты») объекта переднего плана рисовались на стеклянных панелях и предотвращали экспонирование фона на пленку, куда затем отдельным проходом экспонировался новый фон на основе инвертированной маски. Сведение слоев могло также осуществляться оптическими способами [25], например, проецированием через полупрозрачное зеркало.

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

Матирование занимает важное место в профессиональной обработке видео и кинопроизводстве и применяется для замены/модификации фона (см. рис. 2), цветокоррекции отдельных объектов, а также для преобразования видео в стереоскопический (ЗБ) формат.

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

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

Рисунок 2. Пример матирования кадра из видеопоследовательности

• естественная прозрачность объекта (стекло, тонкая ткань)

• особенности пространственной дискретизации (размытие краев объектов)

• особенности временной дискретизации (размытие движения).

В настоящее время задача матирования частично решена для некоторых случаев: выделение объекта на фоне константного цвета, выделение объектов с размытыми краями при известной функции рассеяния точки [42], построение мягкой границы для объекта, заданного бинарной маской и тернарной разметкой (для выделения мелких деталей, волос и т.д.) [33], [44].

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

ле и в конце), что совпадает с изначальной постановкой задачи, т.е. такой случай не надо обрабатывать отдельно.

Чтобы сделать задачу решаемой и ввести объективные критерии качества, сузим класс рассматриваемых видеопоследовательностей. Пусть исходное видео представляет собой непрерывную сцену длиной до 10 секунд с разрешением от 320x240 до 1280x720'. И хотя длительность не является абсолютной величиной (т.к. зависит от частоты кадров), уменьшать частоту кадров исходного видеоматериала не рекомендуется, т.к. это понизит точность вычисления оптического потока. Предпочтительнее уменьшать разрешение, а затем переносить результат (канал прозрачности) на исходное разрешение покадрово с помощью алгоритма [33]. Предполагается, что частота кадров находится в диапазоне 15-25 кадров в секунду (что соответствует веб-камере и телевизионному стандарту PAL соответственно).

Освещение в сцене должно быть стабильным, как и другие параметры, которые могут резко изменить изображение (выдержка, фокус). Должно отсутствовать резкое движение объекта/камеры2. Объект не должен сильно изменять форму в процессе движения. Последнее требование позволяет работать строго с двумя полными ключевыми кадрами.

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

Целью работы является исследование и разработка методов и алгоритмов выделения объекта переднего плана от фона в видеопоследовательности,

1 Ограничения на длительность и разрешение видео обусловлены в основном объемом памяти компьютера и приведены для типичной конфигурации (2-4 ГБ ОЗУ).

2 Ограничения на скорость движения обусловлены алгоритмом вычисления оптического потока и описаны в разделе 3.2.1

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

Существующие подходы

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

Выделение по цвету (chroma-keying) - довольно старый метод, активно применяющийся в кинематографии. Он требует съёмки объекта на однородном фоне («заднике») определённого цвета (называемого ключевым - key color), при этом данный цвет должен отсутствовать в изображении объекта. Изначально chroma-keying осуществлялся без помощи компьютера путём многократной пересъёмки киноплёнки с различными светофильтрами. Наиболее часто используется синий или зелёный фон.

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

a = (r + g)/2-b (2)

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

зуемый метод определяет значение а неверно (например, приведенная формула классифицирует все оттенки серого как фон).

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

а= 1-a,(b-a2g) ^

Fb = min(b, a2g)

Здесь параметры аь а2 настраиваются вручную. Синяя компонента цвета объекта (Ьр) отсекается, остальные без изменения берутся из исходного изображения, т.е. Fr = г, Fg = g. Наиболее распространенные формулы, применяемые в коммерческих программах выделения по цвету, приведены в [66], [19]. Некоторые алгоритмы, в отличие от приведенных, используют цветовое пространство HSV, как, например, [7].

Подобные эмпирические формулы используются в программах Ultimatte [82], Keylight [79]. Алгоритм Primatte [81] использует образцы цвета из исходного изображения и строит по ним цветовую модель фона. Примеры практического применения выделения по цвету показаны на рис. 3.

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

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

Рисунок 3. Пример использования выделения по цвету в кино и на телевидении

Также существуют методы, полагающиеся на специальные условия съемки [57], [58], [59], [39], [40], [72] в том числе с использованием нескольких синхронизированных камер [29].

Ротоскопирование

В случае, когда возможность снять объект на фоне константного цвета отсутствует, применяется ротоскопирование ([83], [84]) - ручное создание маски объекта. Невозможность обеспечить одноцветный фон для автоматической обработки может быть вызвана разными причинами, например:

• архивные и другие видеоматериалы, при съемке которых матирование не планировалось

• слишком большая сцена, которую проблематично покрыть одноцветным задником

• невозможность добиться равномерного освещения задника

• необходимость взаимодействия переднего и заднего плана (например, актер берет какой-то предмет, который до этого был задним планом) - в частности, когда стоит задача не заменить фон, а лишь дополнить/видоизменить име�