Преобразование видеопоследовательностей, содержащих объекты с полупрозрачными границами, в стереоскопический формат тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Ерофеев, Михаил Викторович

• Ерофеев, Михаил Викторович
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Ерофеев, Михаил Викторович

Оглавление

Стр.

Введение

Глава 1. Алгоритм матирования видео с использованием фона

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

1.2 Обзор существующих алгоритмов

1.3 Описание предложенного алгоритма

1.3.1 Восстановление фрагментов фона

1.3.2 Базовый алгоритм матирования изображений

1.3.3 Использование восстановленного фона

1.3.4 Обеспечение стабильности результата во времени

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

1.5 Экспертная оценка

1.6 Программная реализация

1.7 Заключение

Глава 2. Методика сравнения алгоритмов матирования видео

2.1 Введение

2.2 Обзор существующих методов сравнения алгоритмов матирования

2.3 Набор тестовых видео

2.3.1 Цветовая электронная рирпроекция

2.3.2 Кукольная мультипликация

2.4 Экспертная оценка

2.5 Выбор метрики качества

2.6 Объективное сравнение

2.6.1 Открытое онлайн сравнение

2.7 Заключение

Стр.

Глава 3. Алгоритм построения стереоскопических ракурсов с

помощью многослойного матирования

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

3.2 Обзор существующих алгоритмов

3.3 Описание предложенного алгоритма

3.3.1 Построение маски областей, подлежащих обработке

3.3.2 Построение многослойной карты диспарантности

3.3.3 Вычисление изображений слоев

3.3.4 Заполнение областей открытия

3.3.5 Сдвиг слоев и построение изображения ракурса

3.4 Программная реализация

3.5 Анализ результатов работы предложенного алгоритма

3.6 Заключение

Заключение

Список литературы

Список рисунков

Список таблиц

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

Введение

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

Как правило, стереоскопический фильм производится одним из четырех способов:

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

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

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

- Смешанный способ: комбинация материалов, полученных несколькими из вышеописанных способов

Важно отметить, что, несмотря на улучшение технических характеристик стерео-камер, доступных на рынке, самым широко применяемым способом производства стереоскопических фильмов остается конвертация из моноскопического формата. Например, из 36 стереоскопических фильмов, вышедших на экраны кинотеатров в 2016 году, 24 были получены путем конвертации из моноскопического формата.

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

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

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

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

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

Все вышеперечисленные задачи активно исследуются учеными (например, [1—5]). Данная диссертационная работа посвящена исследованию и разработке новых способов решения задачи обработки полупрозрачных границ для преобразования видео в стереоскопический формат. Данная задача, несмотря на внимание ученых, все еще не имела удовлетворительного решения на момент проведения исследования. В частности, как показано в главе 3 диссертации, существовавшие на тот момент методы были не в состоянии обработать области пересечения трех и более объектов.

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

жения или видео на передний план, фон и карту прозрачности. Такая задача часто возникает в процессе обработки изображений и видео. Корректное решение данной задачи позволяет заменять фон позади объекта или применять эффект только к фону или только к переднему плану (например, имитировать съемку с малой глубиной резкости). Актуальность данных приемов монтажа для современного кинематографа, насыщенного спецэффектами, сложно переоценить. Различными авторами было предложено множество алгоритмов как матирования изображений, так и матирования видео [6]. Несмотря на это, как можно видеть из открытого сравнения алгоритмов матирования изображений [7], существующие на момент проведения исследования алгоритмы не способны корректно обработать все тестовые примеры, что дополнительно подтверждает актуальность темы данной диссертации.

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

Для достижения поставленной цели были решены следующие задачи:

1. Разработка новых алгоритмов декомпозиции исходной видеопоследовательности на два и более слоев и их карты прозрачности.

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

Основные положения, выносимые на защиту:

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

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

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

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

Научная новизна:

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

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

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

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

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

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

Предложенная методика получения эталонных карт прозрачности для видеопоследовательностей и методика сравнения последовательностей карт прозрачности с эталоном легли в основу открытого для новых участников сравнения алгоритмов матирования видео, доступного в сети Интернет по адресу http: //videomatting.com. Данное сравнение позволило упорядочить результаты исследований авторов алгоритмов матирования и выявить их сильные и слабые стороны. Сравнение продолжает наполняться результатами анализа новых алгоритмов матирования (в 2016 году три автора прислали результаты работы своих алгоритмов для анализа). Предложенное сравнение упоминается в 4 научных работах независимых авторов.

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

Апробация работы. Основные результаты работы докладывались на:

- 26th British Machine Vision Conference (Суонси, Великобритания, 2015 год)

- 2016 International Conference on 3D Imaging (Льеж, Бельгия, 2016 год). Представленная работа была отмечена наградой за лучшую статью конференции «Best Paper Award / Lumiere Award Europe»

- Семинаре Института Макса Планка (Саарбрюкен, Германия, 2016 год)

- XXII Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2015» (Москва, Россия, 13-17 апреля 2015)

- XXIII Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2016» (Москва, Россия, 11-15 апреля 2016)

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

В работах [8—13] Д.С. Ватолину принадлежит постановка задачи и обсуждение результатов её решения. В работе [13] вклад А.А. Зачесова состоит в разработке алгоритма выбора вектора движения. В работах [9; 12] вклад Ю.А. Гитмана и А.А. Федорова состоит в помощи в подготовке экспериментальной установки для фотографирования полупрозрачного объекта и в анализе собранных данных с помощью алгоритмов, предложенных автором. В работе [12] вклад Джу Ванга состоит в обсуждении полученных результатов.

Результаты научных исследований, представленных в диссертации, были получены в рамках гранта РФФИ № 15-01-08632.

Публикации. Основные результаты по теме диссертации изложены в 8 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ВАК [9— 11], 1 входит в международную базу цитирования Web of Science [8], 2 — в тезисах докладов [14; 15].

Объем и структура работы. Диссертация состоит из введения, трех глав и заключения. Полный объём диссертации составляет 101 страницу, включая 23 рисунка и 2 таблицы. Список литературы содержит 63 наименования.

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

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

Решению задачи матирования видео посвящено множество научных работ, обзор которых представлен в разделе 1.2. А в разделе 1.3 предложен новый алгоритм матирования видео, который, как показано в разделах 1.4 и 1.5, превосходит существующие аналоги. Предложенный алгоритм является обобщением алгоритма матирования изображений Learning Based Matting [16]. Обобщенный алгоритм использует дополнительные входные изображения и их карты прозрачности в качестве опорных данных. В роли опорных изображений были использованы восстановленный фон и соседние кадры, что позволило как уменьшить пространственную ошибку, так и повысить темпоральную стабильность результата.

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

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

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

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

Глава 1. Алгоритм матирования видео с использованием фона

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

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

Формальная постановка задачи матирования имеет следующий вид: разделить данное изображение I на изображение объекта переднего плана Г, изображение заднего плана В и карту прозрачности переднего плана а таким образом, чтобы было верно следующее уравнение:

I = аГ + (1 - а)В

(1.1)

(а) Исходное (г) Карта

(б) Фон (в) Передний план

изображение прозрачности

Рисунок 1.1 — Пример решения задачи матирования: исходное изображение (а) было разделено на фон (б), передний план (в) и карту прозрачности (г)

Так как в такой постановке задача матирования имеет множество решений, включая тривиальные (а =1, F = I, B — любое), для поиска единственного решения требуется сделать некоторые предположения о природе входных данных и расширить перечень входных данных. Как правило, в качестве дополнительных входных данных авторы алгоритмов матирования изображений и видео применяют так называемую тернарную маску — маску, содержащую три типа меток: передний план, фон, неопределенная область (пример тернарной маски изображен на рисунке 1.2).

Задача матирования видео является обобщением задачи матирования изображений на видеопоследовательности. Такое обобщение порождает дополнительные требования к алгоритмам матирования видео:

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

- Алгоритм должен иметь адекватную объемам видеоданных вычислительную сложность

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

Для решения поставленной задачи предлагается алгоритм матирования видеопоследовательностей, в основу которого положен алгоритм матирования изображений на основе обучения (Learning Based Matting [16]). Отличительной особенностью предложенного алгоритма является использование изображений фона, содержащих фрагменты, скрытые объектом переднего плана на исходной видеопоследовательности, в качестве дополнительных входных данных. Для построения таких изображений фона применяется алгоритм, описанный в [13], выполняющий восстановление фрагментов фона, скрытых на данном кадре, путем копирования этих же фрагментов с других кадров видеопоследовательности, где они являлись видимыми. Предлагаемый алгоритм также выполняет два последовательных прохода по видеопоследовательности с целью обеспечения большей стабиль-

(а) Исходное изображение (а) Тернарная маска

Рисунок 1.2 — Пример тернарной маски: (а) исходное изображение, (б)

тернарная маска.

ности во времени результата в сравнении с результатом независимого применения алгоритма [16] к кадрам видеопоследовательности. Подробное описание предложенного алгоритма содержится в разделе 1.3.

1.2 Обзор существующих алгоритмов

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

Первый из известных алгоритмов матирования видео был предложен в 2001 году [17]. В основе метода лежит алгоритм матирования изображений, описанный в работе [18]. В качестве дополнительных входных данных алгоритм использует набор тернарных масок (карт, задающих три области: гарантированный передний план, гарантированный задний план и неизвестная область, для которой требуется решить задачу матирования) для ключевых кадров, выбранных пользователем. Алгоритм выполняет распространение тернарной разметки ключевых кадров на остальные кадры видеопоследовательности с использованием метода оценки оптического потока. Затем алгоритм матирования изображений [18] независимо применяется к каждому кадру видеопоследовательности. С целью повышения качества итоговой карты прозрачности авторы предложили применять простой алгоритм восстановления неизвестных фрагментов фона и в дальнейшем использовать эти фрагменты в качестве источника дополнительных образцов пикселов фона для алгоритма матирования изображений. Серьезным недостатком метода восстановления фона, использованного в работе, является требование принадлежности всех объектов фона одной плоскости, что существенно ограничивает его применимость на практике. Также к недостаткам работы следует отнести независимое применение алгоритма матирования к кадрам видеопоследовательности, что неизбежно приводит к нестабильности результата во времени, и отсутствие данных об оценке результатов работы алгоритма с помощью объективных методов.

Работа 2004 года [19] развивает идею предыдущей работы. Авторы применили методы машинного обучения к эталонным данным для построения модели функции плотности совместного распределения градиента исходной видеопоследовательности и последовательности карт прозрачности. Полученная модель легла в основу нового слагаемого в функции стоимости, оптимизируемой алгоритмом матирования изображений [18]. Ввиду того, что вектор градиента вычислялся в пространственно-временном домене, новое слагаемое повысило стабильность результата во времени. Несмотря на элегантность идеи, следует отметить, что новое слагаемое никак не учитывает движение объектов, что ограничивает приме-

нимость метода видеопоследовательностями с медленным равномерным движением. Работа также не содержит результатов объективной оценки качества.

Авторы работы 2008 года [20] предложили обобщение алгоритма сегментации изображений Grab^t [21] для обработки видеопоследовательностей. В моделях переднего плана и фона, которые в исходном методе определяли вероятность принадлежности пиксела заданного цвета к переднему плану или фону соответственно, цвет пиксела был заменен следующим вектором признаков: цвет пиксела, вектор оптического потока между текущим и предыдущим кадром, вектор оптического потока между текущим и следующим кадром. Алгоритм последовательно производит сегментацию видеопоследовательности с использованием текущих моделей переднего плана и фона, а затем уточняет модели с помощью полученной сегментации на протяжении 10 итераций. Для инициализации моделей используется грубая маска переднего плана, предоставляемая пользователем, или же данная маска строится автоматически путем анализа поля векторов движения. Очевидным достоинством метода является возможность полностью автономной работы без дополнительного ввода со стороны пользователя. К недостаткам метода следует отнести низкое визуальное качество примеров работы метода, продемонстрированных в статье, и отсутствие данных об объективном сравнении метода с аналогами.

Алгоритм матирования видеопоследовательностей [22], предложенный в 2009 году, благодаря высокому визуальному качеству результатов его работы, был включен в профессиональный программный продукт для обработки видеопоследовательностей Adobe After Effects в виде инструмента Roto Brush. На первом шаге алгоритм выполняет бинарную сегментацию исходной видеопоследовательности с использованием множества локальных классификаторов, независимо примененных к небольшим перекрывающимся окнам вдоль границы объекта. Параметры обученных классификаторов переносятся на следующий кадр с помощью векторов оптического потока для обеспечения стабильности во времени результата сегментации. Затем для каждого кадра вычисляется карта прозрачности путем применения модифицированного алгоритма матирования изображений, предло-

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

В 2010 году был предложен алгоритм матирования видеопоследовательностей [24], обобщающий алгоритм матирования изображений [25]. Дополнительными входными данными алгоритма являются тернарные маски для ключевых кадров, которые затем переносятся на остальные кадры видеопоследовательности с использованием алгоритма вычисления оптического потока. Затем к каждому кадру применяется алгоритм матирования изображений [25], на последнем этапе которого матирующий лапласиан с окнами размером 3 х 3 пиксела, принадлежащими текущему кадру, заменен пространственно-временным матирующим лапласианом с окнами 3 х 3 х 3 пиксела, захватывающими два соседних кадра. Тем не менее, алгоритм формирования данных способен учесть лишь малое движение объектов в видеопоследовательности. Также в работе были представлены результаты объективного сравнения предложенного метода с результатами работы алгоритма матирования изображений, примененного независимо к каждому кадру видеопоследовательности. В качестве набора тестовых данных авторы использовали одну синтетическую видеопоследовательность, полученную методами компьютерной графики, с известной эталонной картой прозрачности. Критериями сравнения являлись: Ь2 расстояние результата до эталона и отношение модуля производной карты прозрачности по времени к модулю производной видеопоследовательности

Список литературы диссертационного исследования кандидат наук Ерофеев, Михаил Викторович, 2017 год

Список литературы

1. Lie W.N., Chen C. Y., Chen W. C. 2D to 3D video conversion with key-frame depth propagation and trilateral filtering // Electronics Letters. — 2011. — Март. — Т. 47, № 5. — С. 319—321. —DOI: 10.1049/el.2010.2912.

2. Tolstaya E., Pohl P., Rychagov M. Depth propagation for semi-automatic 2D to 3D conversion // IS&T/SPIE Electronic Imaging. — International Society for Optics, Photonics. 2015. — С. 939303—939303.

3. Eigen D., Puhrsch C., Fergus R. Depth map prediction from a single image using a multi-scale deep network // Advances in neural information processing systems. — 2014. — С. 2366—2374.

4. Video Inpainting of Complex Scenes / A. Newson [и др.] // SIAM Journal on Imaging Sciences. — 2014. — Янв. — Т. 7, № 4. — С. 1993—2019. — DOI: 10.1137/140954933.

5. Kodera N., Fukushima N., Ishibashi Y. Filter based alpha matting for depth image based rendering // Visual Communications and Image Processing (VCIP), 2013. — IEEE. 2013. — С. 1—6.

6. Image and video matting: a survey / J. Wang, M. F. Cohen [и др.] // Foundations and Trends® in Computer Graphics and Vision. — 2008. — Т. 3, № 2. — С. 97— 175.

7. A Perceptually Motivated Online Benchmark for Image Matting / C. Rhemann [и др.] // Computer Vision Pattern Recognition (CVPR). — 2009. — С. 1826— 1833. — DOI: 10.1109/CVPR.2009.5206503.

8. Erofeev M., Vatolin D. Multilayer semitransparent-edge processing for depth-image-based rendering // 2016 International Conference on 3D Imaging (IC3D). — Liege, 2016.—P. 1-7.—DOI: 10.1109/IC3D.2016.7823459.

9. Методика объективного сравнения алгоритмов матирования видео / М. В. Ерофеев [и др.] // Цифровая обработка сигналов. — 2015. — № 3. — С. 53—59.

10. Ерофеев М. В., ВатолинД. С. Матирование видеопоследовательностей с использованием восстановленного фона // Цифровая обработка сигналов. — 2016. — №3. — С. 19—25.

11. Ерофеев М. В., Ватолин Д. С. Многослойное решение проблемы полупрозрачных границ при построении стереоскопических изображений // International Journal of Open Information Technologies. — Москва, 2016. — Т. 4, № 8.

12. Perceptually Motivated Benchmark for Video Matting / M. Erofeev [и др.] // Proceedings of the British Machine Vision Conference (BMVC). — BMVA Press, 09.2015. — С. 99.1—99.12. — DOI: 10.5244/C.29.99.

13. Зачесов А. А., Ерофеев М. В., Ватолин Д. С. Использование карт глубины при восстановлении фона в видеопоследовательностях // Новые информационные технологии в автоматизированных системах: материалы научно-практического семинара. — М.: МИЭМ НИУ ВШЭ, 04.2015. — С. 31—41.

14. Ерофеев М. В. Выбор метрики для оценки качества алгоритмов матирования видео // XXII Международная конференция студентов, аспирантов и молодых ученых Ломоносов-2015. — Издательский отдел факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова Москва, 2015.— С. 14—17.

15. Ерофеев М. В. Матирование видеопоследовательностей с использованием восстановленного фона // XXIII Международная конференция студентов, аспирантов и молодых учёных Ломоносов. Т. 1. — Москва : Москва, 2016. — С. 13—16.

16. Zheng Y, Kambhamettu C. Learning based Digital Matting // International Conference on Computer Vision (ICCV). — 2009. — C. 889—896. — DOI: 10.1109/ICCV.2009.5459326.

17. Video Matting of Complex Scenes / Y.-Y. Chuang [h gp.] // ACM Transactions on Graphics (TOG). — 2002. — T. 21, № 3. — C. 243—248. — DOI: 10.1145/ 566570.566572.

18. A Bayesian Approach to Digital Matting / Y.-Y. Chuang [h gp.] // Computer Vision Pattern Recognition (CVPR). T. 2. — 2001. — C. 11-264—11-271. — DOI: 10. 1109/CVPR.2001.990970.

19. Apostoloff N., Fitzgibbon A. Bayesian Video Matting using Learnt Image Priors // Computer Vision Pattern Recognition (CVPR). T. 1. — 2004. — C. I-407—I-414.—DOI: 10.1109/CVPR.2004.1315061.

20. Corrigan D., Robinson S., Kokaram A. Video Matting using Motion Extended Grabcut // European Conference on Visual Media Production (CVMP). — 2008. — 3—3(1). — DOI: 10.1049/cp:20081076.

21. Rother C., Kolmogorov V., Blake A. Grabcut: Interactive foreground extraction using iterated graph cuts // ACM transactions on graphics (TOG). T. 23. — ACM. 2004. — C. 309—314.

22. Video Snapcut: Robust Video Object Cutout using Localized Classifiers / X. Bai [h gp.] // ACM Transactions on Graphics (TOG). — 2009. — T. 28, № 3. — 70:1—70:11. — DOI: 10.1145/1531326.1531376.

23. Levin A., Lischinski D., Weiss Y. A Closed-form Solution to Natural Image Matting // IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI). — 2008. — T. 30, № 2. — C. 228—242. — DOI: 10.1109/TPAMI. 2007.1177.

24. Lee S.-Y., Yoon J.-C., Lee I.-K. Temporally Coherent Video Matting // Graphical Models. —2010. — T. 72, № 3. — C. 25—33. — DOI: 10.1016/j.gmod.2010. 03.001.

25. Wang J., Cohen M. F. Optimized Color Sampling for Robust Matting // Computer Vision Pattern Recognition (CVPR). — 2007. — C. 1—8. — DOI: 10.1109/ CVPR.2007.383006.

26. Bai X., Wang J., Simons D. Towards Temporally-coherent Video Matting // International Conference on Computer Vision (ICCV). — 2011. — C. 63—74. — DOI: 10.1007/978-3-642-24136-9_6.

27. Linear time Euclidean distance transform algorithms / H. Breu [h gp.] // Pattern Analysis and Machine Intelligence, IEEE Transactions on. — 1995. — T. 17, №5. — C. 529—533.

28. Video Matting via Opacity Propagation / Z. Tang [h gp.] // The Visual Computer — 2012. — T. 28, № 1. — C. 47—61. — DOI: 10.1007/s00371-011-0598-3.

29. Spatio-temporally Coherent Interactive Video Object Segmentation via Efficient Filtering / N. Brosch [h gp.] // Pattern Recognition. T. 7476. — 2012. — C. 418— 427. — DOI: 10.1007/978-3-642-32717-9_42.

30. He K., Sun J., Tang X. Guided Image Filtering // European Conference on Computer Vision (ECCV). — 2010. — C. 1—14.

31. Sindeev M., Konushin A., Rother C. Alpha-flow for video matting // Computer Vision-ACCV 2012. — Springer, 2012. — C. 438—452.

32. Choi I., Lee M., Tai Y.-W Video Matting using Multi-frame Nonlocal Matting Laplacian // European Conference on Computer Vision (ECCV). — 2012. — C. 540—553.—DOI: 10.1007/978-3-642-33783-3_39.

33. Temporally Coherent and Spatially Accurate Video Matting / E. Shahrian [h gp.] // Computer Graphics Forum. — 2014. — T. 33, № 2. — C. 381—390. — DOI: 10.1111/cgf.12297.

34. Gastal E. S., Oliveira M. M. Shared Sampling for Real-time Alpha Matting // Computer Graphics Forum. — 2010. — T. 29, № 2. — C. 575—584. — DOI: 10.1111/j.1467-8659.2009.01627.x.

35. Video Matting via Sparse and Low-Rank Representation / D. Zou [и др.] // Proceedings of the IEEE International Conference on Computer Vision. — 2015. — С. 1564—1572.

36. Chen Q., LiD., Tang C.-K. KNN Matting // IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI). — 2013. — Т. 35, № 9. — С. 2175—2188. — DOI: 10.1109/CVPR.2012.6247760.

37. Fast video super-resolution via classification / K. Simonyan [и др.] // International Conference on Image Processing (ICIP). — 2008. — С. 349—352. — DOI: 10. 1109/ICIP.2008.4711763.

38. Bradley R. A., Terry M. E. Rank analysis of incomplete block designs: I. The method of paired comparisons // Biometrika. — 1952. — Т. 39, № 3/4. — С. 324—345.

39. Deep Image Matting / N. Xu [и др.]. — 2017. — 10 марта. — arXiv: 1703. 03872v1 [cs.CV].

40. Improving Image Matting using Comprehensive Sampling Sets / E. Shahrian [и др.] // Computer Vision Pattern Recognition (CVPR). — 2013. — С. 636— 643.—DOI: 10.1109/CVPR.2013.88.

41. Roto Brush & Refine Edge tools. — URL: https://helpx.adobe.com/after-effects/ using/roto-brush-refine-edge.html (дата обр. 10.03.2017).

42. Lee P, Wu Y. Nonlocal Matting // Computer Vision Pattern Recognition (CVPR). — 2011. — С. 2193—2200. — DOI: 10.1109/CVPR.2011.5995665.

43. Levin A., Rav Acha A., Lischinski D. Spectral Matting // IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI). — 2008. — Окт. — Т. 30, №10.— С. 1699—1712. —DOI: 10.1109/TPAMI.2008.168.

44. Eigenv3 /G. Guennebaud,B. Jacob [и др.]. — 2010. — http://eigen.tuxfamily.org.

45. Agarwal S., Mierle K. [и др.] Ceres Solver. — http://ceres-solver.org.

46. Sindeev M., Konushin A., Rother C. Alpha-flow for Video Matting // Asian Conference on Computer Vision (ACCV). — 2013. — С. 438—452. — DOI: 10.1007/978-3-642-37431-9_34.

47. Hollywood Camera Work. — URL: http://www.hollywoodcamerawork.com/ greenscreenplates.html (дата обр. 03.01.2015).

48. Keylight. — URL: http://help.thefoundry.co.uk/nuke/content/reference_guide/ keyer_nodes/keylight.html (дата обр. 03.01.2015).

49. Shahrian E., Rajan D. Weighted Color and Texture Sample Selection for Image Matting // Computer Vision Pattern Recognition (CVPR). — 2012. — С. 718— 725. —DOI: 10.1109/CVPR.2012.6247741.

50. Johnson J., Rajan D., Cholakkal H. Sparse codes as Alpha Matte // British Machine Vision Conference (BMVA). Т. 32. — 2014. — С. 245—253.

51. Li D., Chen Q., Tang C.-K. Motion-Aware KNN Laplacian for Video Matting // 2013 IEEE International Conference on Computer Vision. — Institute of Electrical, Electronics Engineers (IEEE), 12.2013. — DOI: 10 . 1109/ iccv . 2013.447.

52. Real 3D or Fake 3D. — URL: http://realorfake3d.com/ (дата обр. 23.05.2016).

53. ВатолинД. С., Боков А. А., Федоров А. А. Тенденции изменения технического качества стереокино - 5 лет после «Аватара» // Мир техники кино. — 2015. — Т. 37, № 3. — С. 17—28.

54. Akimov D., Vatolin D., Smirnov M. Single-Image Depth Map Estimation Using Blur Information // Proceedings of the 21st International Conference on Computer Graphics and Vision GraphiCon'2011. — Moscow, Russia, 2011. — P. 12-15. — (GraphiCon).

55. Furnace. — URL: https: //www.thefoundry .co.uk/products/plugins/furnace/ (дата обр. 23.05.2016).

56. Ahn Y., Hong J. Application of DIBR algorithm in real-time image // Proceedings of the 2012 ACM Research in Applied Computation Symposium. — ACM. 2012. — C. 169—171.

57. High-quality video view interpolation using a layered representation / C. L. Zitnick [h gp.] // ACM Transactions on Graphics (TOG). T. 23. — ACM. 2004. — C. 600—608.

58. Lie W.-N., Yeh C.-C., Lin G.-S. Improving DIBR technique to resolve foreground color/depth edge misalignment // Multimedia & Expo Workshops (ICMEW), 2015 IEEE International Conference on. — IEEE. 2015. — C. 1—5.

59. Comparison between blur transfer and blur re-generation in depth image based rendering /N. Fukushima [h gp.] // 3DTV-Conference: The True Vision-Capture, Transmission and Display of 3D Video (3DTV-CON), 2014. — IEEE. 2014. — C. 1—4.

60. Layered depth images / J. Shade [h gp.] // Proceedings of the 25th annual conference on Computer graphics and interactive techniques. — ACM. 1998. — C. 231—242.

61. MATLAB version 7.10.0 (R2010a). — Natick, Massachusetts : The MathWorks Inc., 2010.

62. Davis T. A. Algorithm 849: A Concise Sparse Cholesky Factorization Package // ACM Trans. Math. Softw. — New York, NY, USA, 2005. — £eK. — T. 31, № 4. -C. 587—591. — DOI: 10.1145/1114268.1114277.—URL: http://doi.acm.org/ 10.1145/1114268.1114277.

63. Pairwise ranking aggregation in a crowdsourced setting / X. Chen [h gp.] // Proceedings of the sixth ACM international conference on Web search and data mining - WSDM '13. — Association for Computing Machinery (ACM), 2013. — DOI: 10.1145/2433396.2433420.

Список рисунков

1.1 Пример решения задачи матирования: исходное изображение (а)

было разделено на фон (б), передний план (в) и карту прозрачности (г) 12

1.2 Пример тернарной маски: (а) исходное изображение, (б) тернарная

маска...................................... 14

1.3 Сравнение предложенного алгоритма с алгоритмом, описанным в [35], на 8 тестовых видеопоследовательностях с использованием Ь2 расстояния до эталона (а) и MESSDdt (б). Меньшие значения соответствуют лучшим результатам согласно выбранному способу сравнения...................................38

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

2.1 Карты прозрачности, полученные с использованием методов

цветовой электронной рирпроекции и кукольной мультипликации. Карта, полученная с использованием кукольной мультипликации, имеет существенно большую детализацию................. 44

2.3 Фотография экспериментальной установки для получения эталонных карт прозрачности...............................47

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

2.5 Результаты анализа данных, собранных в ходе эксперимента по экспертной оценке 12 алгоритмов матирования..............58

2.6 Сравнение коэффициентов корреляции различных метрик качества с результатами экспертной оценки....................... 59

2.7 Зависимость коэффициентов корреляции различных метрик качества

от характера движения в видеопоследовательности............59

2.8 Результаты сравнения 12 алгоритмов матирования, примененных к 10 тестовым последовательностям, с использованием метрик качества MESSDdt и SSD................................60

2.9 Анализ зависимости значения метрики качества MESSDdt от ширины неизвестной области тернарной маски для различных алгоритмов матирования, примененных к тестовой

последовательности «АГет».........................61

3.1 Проекции точки сцены р на исходное изображение и изображения ракурсов: Р0 — камера, которой получено исходное изображение; РЪ/2, Р-ь/2 — левая и правая камеры; р0, рЪ/2, р-ъ/2 — проекции точки

р на картинные плоскости этих камер.................... 62

3.2 Примеры двух основных проблем, возникающих при построении новых ракурсов: (а) заполнение областей (обозначены шахматной клеткой), которые были скрыты на исходном ракурсе, но стали видны на новом; (б) обработка полупрозрачных границ, некорректное выполнение которой может привести к излишне резким или

размытым краям на новом ракурсе.....................65

3.3 Пример входных данных предлагаемого алгоритма: (а) исходного изображения и (б) карты глубины. На первом шаге своей работы алгоритм на основании карты глубины строит маску (в) областей вблизи границ карты глубины (для удобства восприятия маска наложена красным цветом поверх карты глубины).............69

3.4 Пример многослойной карты диспарантности для одной строки изображения, где верхняя часть рисунка — это изображение, на котором красным выделена строка, а нижняя часть рисунка — слои карты прозрачности для данной строки изображения. Каждая строка нижнего рисунка соответствует одному слою карты прозрачности (нижняя строка — самому ближнему к зрителю слою). Белые точки — непрозрачные пикселы; черные — невидимые. На карте легко угадываются голова с полупрозрачными пикселами на волосах,

стебли растений слева и справа, темный фон на заднем плане......70

3.5 Заполнение областей открытия методом линейной интерполяции на примере одной строки исходного изображения: (а) исходная многослойная карта диспарантности; (б) маска (изображена красным) областей, скрытых объектами переднего плана; (в) результат применения алгоритма заполнения неизвестных областей с помощью линейной интерполяции.....................72

3.6 Иллюстрация механизма возникновения трещин: (а) строка многослойной карты диспарантности, полученной на основе карты диспарантности, содержащей изменение значения диспарантности всего на одну градацию; после выполнения сдвига (б) в ходе построения левого ракурса на карте диспарантности образуется трещина в виде одного полупрозрачного пиксела.............79

3.7 Пример результата работы алгоритма восстановления фона видеопоследовательности..........................82

3.8 Заполнение областей открытия путем копирования информации из кадра, содержащего недостающие фрагменты фона на примере одной строки: (а) исходная многослойная карта диспарантности и маска (изображена красным) областей, скрытых объектами переднего плана; (б) многослойная карта диспарантности недостающих фрагментов фона, построенная на основании дополнительных данных, предоставленных пользователем; (в) результат объединения

двух карт с помощью предложенного алгоритма. ............ 83

3.9 Примеры результатов работы предложенного алгоритма и двух альтернативных подходов. При рассмотрении рисунков особое внимание следует обратить на (сверху вниз): левый край ножки

бокала, контур волос, контур лица справа, границы каната........85

3.10 Экспертные оценки, вычисленные с помощью модифицированного алгоритма Брэдли-Терри по результатам попарного сравнения предложенного алгоритма с альтернативными подходами. Результаты работы алгоритмов для 12 тестовых изображений были сравнены 56 участниками..................................86

Список таблиц

1 Результаты сравнения предложенного алгоритма с 11 аналогами на 10 тестовых видеопоследовательностях из набора, описанного в главе 2. Для каждой видеопоследовательности были вычислены Ь2 расстояния между результатами работы алгоритмов и эталоном (приведены в столбцах 3-12). Затем методы были упорядочены по близости результата к эталону (надстрочные числа в столбцах 3-12). Для каждого метода было вычислено среднее место во всех тестах (второй столбец). Меньшие значения соответствуют более высоким местам в рейтинге...............................36

2 Результаты сравнения предложенного алгоритма с 11 аналогами на 10 тестовых видеопоследовательностях из набора, описанного в главе 2. Для каждой видеопоследовательности были вычислены значения квазиметрики MESSDdt (в главе 2 показана высокая корреляция данного способа оценки с результатами экспертной оценки) между результатами работы алгоритмов и эталоном (приведены в столбцах 3-12). Затем методы были упорядочены по близости результата к эталону (надстрочные числа в столбцах 3-12). Для каждого метода было вычислено среднее место во всех тестах (второй столбец). Меньшие значения соответствуют более высоким местам в рейтинге. . 37