Точное выделение границ объектов

Точное выделение границ
объектов
Михаил Ерофеев
Video Group
CS MSU Graphics & Media Lab
Only for
Maxus 
Содержание



Введение
Robust Matting
Video SnapCut
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
2
Only for
Maxus 
Введение
Постановка задачи

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
3
Only for
Maxus 
Введение
Некорректно поставленная задача
Три неизвестных (F, B, α), одна известная (I).
Чтобы решить задачу нужны дополнительные
условия.
Возможные дополнительные условия:
 информация от пользователя
 изображения с разных камер
 освещение объектов вспышкой
 данные о движении
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
4
Only for
Maxus 
Содержание



Введение
Robust Matting
Video SnapCut
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
5
Only for
Maxus 
Robust Matting
Описание метода
Метод с использованием входного
изображения и trimap строит α-маску.
Основная идея: использовать
для определения коэффициента
прозрачности не все точки фона и объекта
в окрестности, а лишь наиболее «надежные»
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
6
Only for
Maxus 
Robust Matting
Выбор точек
Для пары точек фона и объекта
из окрестности неизвестной точки найдем:


Предполагаемый коэффициент прозрачности
Разница между наблюдаемым цветом и
предсказанным
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
7
Only for
Maxus 
Robust Matting
Выбор точек (2)

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
8
Only for
Maxus 
Robust Matting
Пояснение смысла надежности

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
9
Only for
Maxus 
Robust Matting
Карты надежности и прозрачности



Для каждой неопределенной точки
выберем три пары точек фона и объекта с
наибольшей надежностью
Усредним надежность и прозрачность этих
пар
Занесем полученные значения в карту
прозрачности и надежности
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
10
Only for
Maxus 
Robust Matting
Карты надежности и прозрачности
Исходное
изображение и
надежность пар точек
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Карта
прозрачности
Карта
надежности
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
11
Only for
Maxus 
Robust Matting
Форма окрестности
Традиционная
окрестность
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Предложенная
окрестность
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
12
Only for
Maxus 
Robust Matting
Оптимизация маски
Рассмотрим граф.
Множество вершин – все
точки изображения и две
специальных вершины
фон B и объект F. Каждая
вершина соединена
со своими соседями и
специальными
вершинами
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
13
Only for
Maxus 
Robust Matting
Оптимизация маски
Веса ребер:
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
14
Only for
Maxus 
Robust Matting
Построение конечной маски
К построенному графу применим метод
Random Walk, т.е. найдем вероятность
прийти из вершины F в каждую точку
изображения. Составим из этих вероятностей
конечную маску.
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
15
Only for
Maxus 
Robust Matting
Примеры работы и сравнение
Объективное сравнение алгоритмов
на основе среднеквадратичной ошибки
Ground-truth:



Три изображения на основе blue screen matting
Три на основе подмены фона
Два натуральных изображения
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
16
Only for
Maxus 
Robust Matting
Примеры работы и сравнение (2)
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
17
Only for
Maxus 
Robust Matting
Примеры работы и сравнение (3)
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
18
Only for
Maxus 
Robust Matting
Примеры работы и сравнение (4)
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
19
Only for
Maxus 
Robust Matting
Примеры работы и сравнение (5)
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
20
Only for
Maxus 
Robust Matting
Анализ метода

Достоинства



Лучший результат в сравнительном тесте
Мало деградирует при снижении качества
trimap
Недостатки

Уступает методам, основанным на
распространении маски, при сравнении на
грубых масках
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
WANG, J., AND COHEN, M. 2007.
Optimized color sampling for robust matting.
In Proc. of IEEE CVPR, 2007
21
Only for
Maxus 
Содержание



Введение
Robust Matting
Video SnapCut
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
22
Only for
Maxus 
Video SnapCut
Описание метода
В качестве дополнительных данных используется
грубая маска объектов для ключевых кадров.
Основная идея: решать задачу в маленьких окнах,
расположенных вдоль границы объекта и
перемещать их вслед за объектом.
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
23
Only for
Maxus 
Video SnapCut
Схема работы метода
1.
2.
3.
4.
5.
Для первого кадра получить грубую маску
Расположить вдоль границы объекта
небольшие перекрывающие друг друга
окна
Инициализировать модель цвета и формы
внутри каждого окна
Построить бинарную маску
Построить α-маску
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
24
Only for
Maxus 
Video SnapCut
Схема работы метода (2)
6.
7.
8.
9.
10.
Перейти к следующему кадру
На основе данных optical flow переместить
окна и обновить маску
Обновить модель цвета и формы внутри
каждого окна
Построить бинарную и α-маску
Перейти к шагу 6
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
25
Only for
Maxus 
Video SnapCut
Инициализация окон

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
26
Only for
Maxus 
Video SnapCut
Модель цвета
Распределение цвета моделируется с
помощью Gaussian mixture model (GMM)
Алгоритм инициализации:
 Выбрать внутри окна точки фона на
расстоянии не менее пяти пикселей от
границы
 Построить GMM из трех компонент
 Повторить аналогичные действия для
объектов
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
27
Only for
Maxus 
Video SnapCut
Gaussian mixture model (GMM)
Вектор z принадлежит объекту с вероятностью
Вектор z принадлежит фону с вероятностью
Плотность многомерного распределения Гаусса
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
28
Only for
Maxus 
Video SnapCut
Построение GMM
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
29
Only for
Maxus 
Video SnapCut
Надежность цветовой модели

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
30
Only for
Maxus 
Video SnapCut
Модель формы

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
31
Only for
Maxus 
Video SnapCut
Построение бинарной маски

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
32
Only for
Maxus 
Video SnapCut
Построение бинарной маски (2)




Построим на основе вероятностей функцию
энергии и применим Graph Cut, получим
маску
Обновим модель цвета и формы в каждом
окне
Построим новую маску
Будем повторять, пока маска не перестанет
меняться
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
33
Only for
Maxus 
Video SnapCut
Построение α-маски
Построим trimap, применив к бинарной маске
последовательно сужение и расширение
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
34
Only for
Maxus 
Video SnapCut
Построение α-маски (2)

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
35
Only for
Maxus 
Video SnapCut
Построение α-маски (3)

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
36
Only for
Maxus 
Video SnapCut
Построение α-маски (4)

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
37
Only for
Maxus 
Video SnapCut
Построение α-маски (5)
Получение α-маски теперь сводится к
решению СЛАУ.
Исходный фрагмент
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
α-маска
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
38
Only for
Maxus 
Video SnapCut
Перемещение окон




Найдем особые точки внутри объекта для
пары кадров
Найдем аффинное преобразование между
этими кадрами
Между новым кадром и преобразованным
найдем optical flow
Сдвинем окно на среднее значение
векторов optical flow в этом окне
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
39
Only for
Maxus 
Video SnapCut
Обновление моделей


Модель формы обновляется на основании
новой маски
Модель цвета
Две модели
Историческую – модель с прошлого кадра
 Текущую – модель, составленную из модели
для данного кадра и исторической
Если использование исторической модели
приводит к уменьшению области фона – возьмем
текущую модель.

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
40
Only for
Maxus 
Video SnapCut
Изменение топологии объекта
Форма объекта может существенно
изменяться, необходимо удалять окна и
добавлять новые:
 Сместим центры окон на границу объекта
 Удалим окно, если плотность окон
в окрестности высока
 Добавим окно, если есть точки, не
покрытые ни одним окном
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
41
Only for
Maxus 
Video SnapCut
Изменение топологии объекта (2)
Пример добавления новых окон
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
42
Only for
Maxus 
Video SnapCut
Распространение в двух направлениях

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
43
Only for
Maxus 
Video SnapCut
Пример работы
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
44
Only for
Maxus 
Video SnapCut
Пример работы (2)
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
45
Only for
Maxus 
Video SnapCut
Сравнение с другими методами
Цветом выделена дополнительная
информация, которую вносил пользователь
для получения желаемого результата
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
46
Only for
Maxus 
Video SnapCut
Сравнение с другими методами (2)
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
47
Only for
Maxus 
Video SnapCut
Анализ метода

Достоинства



Алгоритм включен в состав Adobe After Effects CS5
Локальность окон позволяет вносить небольшие
правки без повторной обработки всего видео
Недостатки


Не обрабатывает появление новых цветов
на границе объекта
Не обрабатывает объекты неопределенной формы
(огонь, дым)
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut:
robust video object cutout using localized classifiers. ACM
Transactions on Graphics, 2009
48
Only for
Maxus 
Литература
1.
2.
3.
WANG, J., AND COHEN, M. 2007. Optimized color sampling for robust
matting. In Proc. of IEEE CVPR, 2007
LEVIN, A., LISCHINSKI, D., AND WEISS, Y. 2008. A closedform solution
to natural image matting. IEEE Trans. Pattern Analysis and Machine
Intelligence, 2008
X. Bai, J. Wang, D. Simons, and G. Sapiro. Video SnapCut: robust video
object cutout using localized classifiers. ACM Transactions on Graphics,
2009
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
49