WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

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

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

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

Специальность 05.13.11 – математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание учёной степени

кандидата физико-математических наук

Москва – 2013

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

Апробация работы Результаты работы докладывались и обсуждались на • 17-ой международной конференции по компьютерной графике и машинному зрению «Graphicon’2007», Россия, Москва, • 18-ой международной конференции по компьютерной графике и машинному зрению «Graphicon’2008», Россия, Москва, • 19-ой международной конференции по компьютерной графике и машинному зрению «Graphicon’2009», Россия, Москва, • 16-й международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009»

• 5-й летней школе Microsoft для аспирантов (Microsoft Research PhD Summer School), Великобритания, г. Кембридж, • семинаре группы компьютерного зрения Microsoft Research, 23 июля 2010), Великобритания, г. Кембридж, • 22-ой международной конференции по компьютерной графике и машинному зрению «Graphicon’2012», Россия, Москва, • Семинаре по компьютерной графике и машинному зрению Ю.М. Баяковского (ф-т ВМК МГУ) • Семинаре направления «Программирование» им. М. Р. Шура-Бура в ИПМ им. М. В. Келдыша РАН Публикации По теме диссертации автором опубликовано 7 научных работ, в т.ч. 2 в журналах ВАК [6], [7]. Статья, посвященная предложенному алгоритму матирования видеопоследовательностей, была принята на ведущую международную конференцию ACCV-2012 и опубликована в журнале Lecture Notes in Computer Science издательства Springer [7].

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

Содержание работы Во введении описывается задача матирования изображений и видео.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Chuang Y., Curless B., Salesin D., Szeliski R. A Bayesian Approach to Digital Matting // In proc. of CVPR.

2001. P. 264– Levin A., Lischinski D., Weiss Y. A Closed Form Solution to Natural Image Matting // In proc. of CVPR.

2006. P. 61– Vezhnevets V., Konouchine V. Grow-Cut – Interactive Multi-Label N-D Image Segmentation by Cellular Automata // In proc. of Graphicon. 2005. P. 150– Тестовая база: Rhemann C., Rother C., 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. Иллюстрация идеи алгоритма: (а, б) первый и последний кадры фрагмента, (в) маски, соответствующие этим кадрам, (г) контур в первом кадре, (д) два способа переноса контура на последний кадр – в предположении, что контур лежит на поверхности, и в предположении, что контур является видимой границей объекта, (е) результат алгоритма SnapCut5 – видно, что данный алгоритм предполагает принадлежность контура поверхности, что неверно.

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

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

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

Затем после матирования он уточняется за счет использования альфа-канала.

RGB каналы также используются в качестве регуляризации, но с меньшим весом.

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

где M – бинарная маска перекрытий, – условие разреженности маски перекрытий, J – целевой функционал матирования для каждого кадра, Bai X., Wang J., Simons D., Sapiro G. Video SnapCut: robust video object cutout using localized classifiers // In proc. of SIGGRAPH. 2009. P. 1– – производная вдоль вектора потока V.

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

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

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

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

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

Предложены два новых алгоритма – более быстрый двухкадровый и более точный траекторный. За основу взята вариационная формулировка задачи оптического потока, заключающаяся в минимизации функционала энергии 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– Помимо непрерывных методов также существуют дискретные, основанные на переборе вектора сдвига (u, v) по множеству {–M, …, M}2, где M – максимальный сдвиг.

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

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

Каждое из слагаемых само по себе эффективно минимизируется предназначенным для него алгоритмом.

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

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

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

где wRGB – вес цветовых каналов.

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– Рисунок 7. (а) Полный перебор (M возможных векторов в каждом пикселе).

(Б) Перебор методом PatchMatch – вектор потока выбирается из 5 кандидатов при прямом проходе (текущий пиксел и 4 ранее обработанных пиксела). (В) шаблон обратного прохода.

Второй предложенный алгоритм – траекторный поток – является более точным, чем первый, но более медленным. Основная идея алгоритма заключается в использовании нескольких кадров сразу для нахождения перекрытий и уточнения слагаемого данных. В данном алгоритме рассматривается T = 2K + кадров с номерами –K, …, K. Финальным результатом является оптический поток из кадра I0 в I1 и обратный поток из I0 в I–1, но при этом в качестве промежуточного результата находятся 2K потоков из I0 в остальные кадры. В каждом пикселе кадра I0 эти потоки образуют траекторию.

Т.к. потоки вычисляются относительно кадра I0, их можно считать одним «траекторным» потоком, где каждому пикселу сопоставлен 4K-мерный (или, что то же самое, 2(T – 1)-мерный) вектор потока Такое векторное представление позволяет использовать любые известные функционалы гладкости, определенные для двухмерного потока, которые могут быть сформулированы в терминах векторной алгебры, а также многие алгоритмы минимизации данных функционалов. Исключением будут алгоритмы, явно использующие факт двухмерности, а также алгоритмы, несовместимые с членом данных ED (однако их часто можно адаптировать для данной задачи, либо использовать методы раздельной оптимизации, используя другой алгоритм для члена данных). Кроме того, стохастические и переборные алгоритмы могут потерять свою эффективность из-за увеличения пространства поиска. Метод траекторного потока использует следующий функционал энергии:

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

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

ES (V ) = при этом норма градиента является инвариантной к повороту при =0,5, что в двухмерном случае записывается как причем в суммирование по t также производится под знаком радикала. Это означает, что в случае разрывности решения разрыв потока в некоторой точке происходит одновременно в горизонтальной и вертикальной компонентах потока и сразу во всех кадрах. Таким образом, траектории в двух соседних пикселах не могут разойтись, а через несколько кадров слиться в единый объект.

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

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

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

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

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

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

CVPR, 2007.

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

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

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

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

Экспериментальная оценка метода проводилась на тестовой базе Middlebury. Примеры приведены на рис. 11.

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

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

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

• средний цвет µ, дисперсию • начало t1, длительность.

Каждый пиксел суперпиксела хранит:

• цвет относительно µ • координату x(t), y(t).

Тогда, используя принцип минимальной длины описания, можно потребовать от разбиения видеообъема на суперпикселы минимальность их общей энтропии где Hµ – число битов для хранения среднего цвета и дисперсии (константа), 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. Иллюстрация разбиения на суперпикселы: (а) кадр видеопоследовательности, (б) длины траекторий (в кадрах), проходящих через пикселы этого кадра.

Hp – число битов для кодирования координат одного пиксела (x(t), y(t)) – также константа, Hc – число битов для хранения отклонения цвета пиксела от среднего цвета µ в предположении, что это отклонение подчиняется нормальному распределению с дисперсией 2.

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

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

На рис. 13 проиллюстрировано разбиение видеообъема на суперпикселы.

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

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

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

A(t ) = ( x, y, t ) – площадь объекта, A (t ) = * ( x, y, t ) – площадь объекта в эталонной разметке, A(t ) = kA(t ) + b Lucas B., Kanade T. An iterative image registration technique with an application to stereo vision // Proceedings of Imaging Understanding Workshop. 1981. P. 121 – 1 dA dA* Нормализация площади объекта гарантирует инвариантность метрики к неточностям в эталонной разметке (наиболее типичная ситуация – маска объекта морфологически расширена или сжата на 1-3 пиксела).

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

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

Таблица 1. Численное сравнение алгоритмов [Tsai 2010] В заключении перечислены основные результаты работы.

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

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

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

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

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

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

Публикации по теме диссертации 1. Sindeyev M., Konushin V., Vezhnevets V. Improvements of Bayesian Matting // Proc. of Graphicon. 2007, P. 88– 2. Sindeyev M., Konushin V. A Novel Interactive Image Matting Framework // Proc.

of Graphicon. 2008, P. 41– 3. Sindeyev M., Konushin V. A Novel Approach to Video Matting using Optical Flow // Proc. of GraphiCon. 2009, P. 340– 4. Синдеев М., Конушин В. Матирование видео на основе оптического потока // Сборник тезисов XVI Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009», секция «Вычислительная математика и кибернетика». 2009. С. 5. Синдеев М., Конушин А., Ротер К. Многокадровый оптический поток на основе траекторий. Труды конференции Графикон. 2012. С. 288– 6. Синдеев М., Конушин В. Интерактивное байесовское матирование изображений // Программные продукты и системы. 2012. N 4. С. 167– 7. Sindeev M., Rother C., 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– Личный вклад автора Все результаты, составляющие основное содержание диссертации, получены автором самостоятельно. В работах [1, 2, 6] автору принадлежат идеи условия гладкости прозрачности в байесовской модели, упорядоченной обработки пикселов по цветовой близости, иерархической обработки, инструмента построения тернарной разметки на основе алгоритма Дейкстры и инструментов редактирования канала прозрачности с пересчетом цветовых каналов. В работах [3, 4] автором предложен новый алгоритм совместного вычисления оптического потока и канала прозрачности по одному ключевому кадру. В работе [5] автором предложен новый алгоритм вычисления оптического потока. В работе [7] автором предложен новый алгоритм совместного вычисления оптического потока и канала прозрачности по двум ключевым кадрам, а также алгоритм сегментации видеопоследовательности на временные суперпикселы и алгоритм быстрого вычисления оптического потока на основе раздельной оптимизации.





Похожие работы:

«Мельников Андрей Владимирович АНАЛИЗ РИСКОВ ЭКСПЛУАТАЦИИ ОБЪЕКТОВ ДОБЫЧИ И ПОДГОТОВКИ ГАЗА НА МЕСТОРОЖДЕНИЯХ КРАЙНЕГО СЕВЕРА (НА ПРИМЕРЕ БОВАНЕНКОВСКОГО НГКМ) Специальность 05.26.02 Безопасность в чрезвычайных ситуациях в нефтяной и газовой промышленности Автореферат диссертации на соискание ученой степени кандидата технических наук Москва - 2009 Работа выполнена в Обществе с ограниченной ответственностью Научноисследовательский институт природных газов и газовых технологий –...»

«МУРАТХАНОВА Ольга Вячеславовна Художественное своеобразие рассказов У.Фолкнера: формирование новеллистического цикла в прозе 1930-х годов Специальность 10.01.03 – литература народов стран зарубежья (литература США) Автореферат диссертации на соискание ученой степени кандидата филологических наук Казань – 2006 4 Общая характеристика работы Имя лауреата Нобелевской премии по литературе, выдающегося американского писателя Уильяма Фолкнера (William Faulkner, 1897 – 1962) по...»

«ТАРАБУХИНА Надежда Константиновна МЕТОДЫ ИЗВЛЕЧЕНИЯ БИЗНЕС-ЛОГИКИ НА ОСНОВЕ СЕМАНТИЧЕСКИХ СВОЙСТВ ПРОГРАММ Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Новосибирск 2010 Работа выполнена в...»

«Егорова Ирина Алексеевна ЭФФЕКТИВНОСТЬ СКРЕЩИВАНИЯ ЦИГАЙСКИХ МАТОК С БАРАНАМИ ВОСТОЧНО-ФРИЗСКОЙ ПОРОДЫ В УСЛОВИЯХ САРАТОВСКОГО ЗАВОЛЖЬЯ 06.02.04 – частная зоотехния, технология производства продуктов животноводства АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата сельскохозяйственных наук Черкесск – 2008 1 Работа выполнена на кафедре технологии производства продуктов животноводства и племенного дела ФГОУ ВПО Саратовский государственный аграрный университет имени...»

«ЭКСПРЕССИЯ НАТИВНОГО И МОДИФИЦИРОВАННОГО ГЕНОВ ИММУННОГО ИНТЕРФЕРОНА БЫКА В КЛЕТКАХ ДРОЖЖЕЙ SACCHAROMYCES CEREVISIAE И PICHIA PASTORIS 03.03.04 – клеточная биология, цитология, гистология АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата биологических наук Санкт-Петербург 2010 Работа выполнена в Санкт-Петербургском государственном университете в лаборатории биохимической генетики...»

«Абдрашитов Андрей Владимирович СТРУКТУРНЫЕ ИЗМЕНЕНИЯ ПЛАЗМЕННО-ПЫЛЕВЫХ КРИСТАЛЛОВ В ПОЛЯХ РАЗЛИЧНОЙ КОНФИГУРАЦИИ Специальности: 01.04.07 – физика конденсированного состояния 01.04.02 – теоретическая физика АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Томск – 2011 Работа выполнена в Учреждении Российской академии наук Институте физики прочности и материаловедения Сибирского отделения РАН Научные руководители: доктор...»

«Чунаев Петр Владимирович Аппроксимация наипростейшими дробями и их модификациями 01.01.01 — Вещественный, комплексный и функциональный анализ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Казань 2013 2 Работа выполнена на кафедре функционального анализа и его приложений ФГБОУ ВПО Владимирский государственный университет имени А. Г. и Н. Г. Столетовых. Научный руководитель : Данченко Владимир Ильич, доктор физико–математических наук,...»

«Калекина Анна Викторовна Влияние профессиональной культуры на удовлетворенность трудом инженеров-конструкторов промышленных предприятий Специальность 19.00.03 – Психология труда, инженерная психология, эргономика (психологические наук и) Автореферат диссертации на соискание учёной степени кандидата психологических наук Москва – 2009 Работа выполнена на кафедре психологии труда и инженерной психологии факультета психологии Московского государственного университета имени М.В....»

«ФАЛАЛЕЕВА МАРИНА ВИТАЛЬЕВНА Чувствительное и специфическое определение редких молекул РНК 03.00.03 – Молекулярная биология Автореферат диссертации на соискание ученой степени кандидата биологических наук Москва - 2009 Работа выполнена в Институте белка РАН Научный руководитель : член-корреспондент РАН, доктор биологических наук Четверин Александр Борисович Официальные оппоненты : член-корреспондент РАН, доктор биологических наук, профессор Разин Сергей Владимирович кандидат...»

«Зачиняев Ярослав Васильевич Экологические проблемы современного животноводства (на примере коневодства) 03.02.08 – Экология 06.02.10 – Частная зоотехния, технология производства продуктов животноводства Автореферат диссертации на соискание учёной степени доктора биологических наук Петрозаводск - 2012 1 Работа выполнена в Санкт-Петербургском государственном университете сервиса и экономики Научный консультант : доктор сельскохозяйственных наук, Сергиенко Сергей Семёнович...»

«Кучакшоев Холикназар Соибназарович ОБ ОДНОМ КЛАССЕ КВАЗИЛИНЕЙНЫХ ЭВОЛЮЦИОННЫХ УРАВНЕНИЙ И ИХ ПРИЛОЖЕНИЯ 01.01.02 - Дифференциальные уравнения, динамические системы и оптимальное управление АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук ДУШАНБЕ-2012 Работа выполнена в Российско-Таджикском(Славянском) университете Научный руководитель : доктор физико–математических наук, академик АН РТ, профессор Илолов Мамадшо Илолович Официальные...»

«БОВА Ирина Анатольевна ФИНАНСОВО-ПРАВОВЫЕ ОСНОВЫ ИНСТИТУТА БАНКОВСКОЙ ТАЙНЫ В РОССИЙСКОЙ ФЕДЕРАЦИИ: ПРОБЛЕМЫ ТЕОРИИ И ПРАКТИКИ 12.00.04 – финансовое право; налоговое право; бюджетное право АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата юридических наук Саратов – 2013 2 Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Саратовская государственная юридическая академия. Научный руководитель...»

«Зимина Людмила Олеговна Принцип экономии в современной рекламе Специальность 10.02.01 – русский язык АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата филологических наук Томск – 2007 2 Работа выполнена на кафедре общего и исторического языкознания ГОУ ВПО Новосибирский государственный педагогический университет Научный руководитель – доктор филологических наук, профессор Юрий Викторович Фоменко Официальные оппоненты – доктор филологических наук, профессор Лариса...»

«НУРАЛИЕВА Анна Борисовна О ДИНАМИКЕ ТРОСА КОСМИЧЕСКОГО ЛИФТА 01.02.01 – теоретическая механика АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2012 год 1 Работа выполнена в Институте прикладной математики им. М.В. Келдыша РАН Научный руководитель : доктор физико-математических наук, профессор Садов Юрий Андреевич Официальные оппоненты : доктор физико-математических наук, профессор Самсонов Виталий Александрович, главный...»

«ЛАРИОНОВ Виктор Михайлович МЕХАНИЗМЫ И УСЛОВИЯ ВОЗБУЖДЕНИЯ АВТОКОЛЕБАНИЙ ГАЗА В УСТАНОВКАХ С ГОРЕНИЕМ 05.07.05 – Тепловые, электроракетные двигатели и энергоустановки летательных аппаратов АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук Казань – 2004 Работа выполнена в Казанском государственном университете им. В.И. Ульянова–Ленина Официальные оппоненты : доктор технических наук, профессор Костерин Валентин Александрович доктор технических наук,...»

«Биглова Юлия Николаевна ФУЛЛЕРЕН С60 В РЕАКЦИИ РАДИКАЛЬНОЙ СОПОЛИМЕРИЗАЦИИ АЛЛИЛОВЫХ И ВИНИЛОВЫХ МОНОМЕРОВ 02.00.06 Высокомолекулярные соединения АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата химических наук Уфа 2008 www.sp-department.ru 2 Работа выполнена в Институте органической химии Уфимского научного центра Российской академии наук и ГОУ ВПО “Башкирском государственном университете”. Научный руководитель : академик РАН Монаков Юрий Борисович Официальные...»

«ЛИХОЛЕТОВ АЛЕКСАНДР АЛЕКСАНДРОВИЧ УГОЛОВНО-ПРАВОВЫЕ И КРИМИНОЛОГИЧЕСКИЕ ПРОБЛЕМЫ ПРОТИВОДЕЙСТВИЯ НЕЗАКОННОМУ ИГОРНОМУ БИЗНЕСУ 12.00.08 – уголовное право и криминология; уголовно-исполнительное право Автореферат диссертации на соискание ученой степени кандидата юридических наук Саратов – 2013 Работа выполнена в федеральном государственном казенном образовательном учреждении высшего профессионального образования Волгоградская академия Министерства внутренних дел Российской...»

«ШАРИФУЛЛИН ВАДИМ РИФОВИЧ ЧАСТНО-ПРАВОВОЕ РЕГУЛИРОВАНИЕ Специальность 12. 00. 01 – теория и история права и государства; история учений о праве и государстве Автореферат диссертации на соискание ученой степени кандидата юридических наук Казань - 2006 Работа выполнена на кафедре теории и истории государства и права Государственного образовательного учреждения высшего профессионального образования Казанский государственный университет им. В.И. Ульянова-Ленина Научный...»

«ПЕТРИНА ВАЛЕНТИНА СЕРГЕЕВНА ФРАЗЕОЛОГИЧЕСКИЙ ПОТЕНЦИАЛ СЛОВ JOUER – JEU/ ИГРАТЬ – ИГРА И ИХ ДЕРИВАТОВ ВО ФРАНЦУЗСКОМ И РУССКОМ ЯЗЫКАХ специальность 10.02.05 — романские языки 10.02.20 — сравнительно-историческое, типологическое и сопоставительное языкознание                          Автореферат диссертации на соискание учёной степени кандидата филологических наук Москва — 2012 Работа выполнена на кафедре французского языкознания филологического факультета Московского...»

«БРЫКСИН ВИТАЛИЙ МИХАЙЛОВИЧ РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ И ПРОГРАММНЫХ СРЕДСТВ ОЦЕНКИ УРОЖАЙНОСТИ ЗЕРНОВЫХ КУЛЬТУР В УСЛОВИЯХ ЗАПАДНОЙ СИБИРИ 05.13.18 – Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата технических наук Барнаул – 2009 Работа выполнена в лаборатории сетевых информационных технологий Автономного учреждения Ханты-Мансийского автономного округа – Югры Югорский...»








 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.