�ݺ�ߣ

Некоторые методы
сегментации видео
Сергей Матюнин
Video Group
CS MSU Graphics & Media Lab

CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Only for
Maxus 
Содержание
 Введение
 Общие подходы
 Сегментация на основе траекторий
 Online Dense Segmentation
 Заключение
2

Only for
Maxus 
Сегментация изображений
3
S. Brutzer, B. Hoferlin, and G. Heidemann, “Evaluation
of background subtraction techniques for video surveillance,” IEEE
CVPR, 2011
 Сегментация – задача разбиения изображения
на несколько множеств пикселей
(суперпикселей) так, чтобы разбиение
удовлетворяло заданным условиям
 Кластеризация – задача разбиения заданной
выборки объектов на подмножества (кластеры)
так, чтобы
 каждое подмножество состояло из схожих объектов
 объекты разных кластеров существенно отличались

Only for
Maxus 
Примеры (1/2)
4Matthias Grundmann, Vivek Kwatra, Mei Han, Irfan Essa, “Efficient
Hierarchical Graph-Based Video Segmentation,” CVPR 2010
Исходное
изображение
Результат
сегментации
Исходное
изображение
Результат
сегментации
Разными цветами отмечены различные кластеры

Only for
Maxus 
Примеры (2/2)
5Matthias Grundmann, Vivek Kwatra, Mei Han, Irfan Essa, “Efficient
Hierarchical Graph-Based Video Segmentation,” CVPR 2010
Исходный кадр Результат сегментации

Only for
Maxus 
Сегментация видео
Пример
6F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation,” IEEE CVPR, 2009
Кадры последовательности
Результаты сегментации

Only for
Maxus 
Применение
Depth Propagation
7
Последовательность «Parrots»
Исходное видео Распространенная
глубина

Only for
Maxus 
Применение
Depth from Motion
8
Видео из фильма «Люди Икс. Первый класс»

Only for
Maxus 
9

Only for
Maxus 
Сегментация объектов
Применение в видеонаблюдении (1/2)
10
S. Brutzer, B. Hoferlin, and G. Heidemann, “Evaluation
of background subtraction techniques for video surveillance,” IEEE
CVPR, 2011
Типичный процесс выделения объектов

Only for
Maxus 
Сегментация объектов
Применение в видеонаблюдении (2/2)
11
A. Griesser et al., “GPU-Based Foreground-Background
Segmentation using an Extended Colinearity Criterion,” Vision,
Modeling, and Visualization, 2005
 Камера неподвижна
 Объекты малы
 Точность часто не критична
Кадр без объектов Кадр с объектами Маска объектов

Only for
Maxus 
Общие подходы
Вычитание фона
Метод для неподвижной камеры
1. Находим фон усреднением или медианой
большого количества кадров
2. Вычитаем из исходного кадра
3. То, что осталось – объекты
12R. Tron and R. Vidal, “A Benchmark for the Comparison of 3-D
Motion Segmentation Algorithms,” IEEE CVPR, 2007

Only for
Maxus 
Глобальное движение
 Оцениваем глобальное движение
 Считаем объектами области, где движение
не совпадает с глобальным
 Остальные области – фон

Only for
Maxus 
RANdom SAmple Consensus (RANSAC)
Сегментируем пространство координат точек
на нескольких последовательных кадрах
1. Применяем RANSAC к исходному множеству.
Находим подпространство из inliers. Остальные
точки – outliers
2. Применяем шаг 1 к множеству outliers, пока
не найдем все подпространства
3. Для каждого подпространства inliers применяем
метод главных компонент, чтобы найти
наилучший базис для каждого подпространства
4. Выбираем для каждой точки ближайшее
подпространство

Only for
Maxus 
Смесь гауссиан
15F. Liu and M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation,” IEEE CVPR, 2009
 Пытаемся
представить
множество точек
видео как смесь
гауссиан в некотором
пространстве
 Выделяем
компоненты, которые
соответствуют
объекту или фону

Only for
Maxus 
Спектральная кластеризация

16T. Brox and J. Malik, “Object segmentation by long term
analysis of point trajectories,” ECCV, 2010
Матрица схожести точек

Only for
Maxus 
Спектральная кластеризация
Пример
17
D. Hamad, P. Biela, “Introduction to spectral clustering,” in IEEE
Information and Communication Technologies: From Theory to
Applications, 2008
Матрица расстояний в графе
Матрица Кирхгофа

Only for
Maxus 
18

Only for
Maxus 
Траектории точек
 Вместо покадрового OF используем длинные
траектории
 Траектории строим на основе трекера [Sundaram
et al., ECCV 2010]. Трекер основан на OF
19T. Brox and J. Malik, “Object Segmentation by Long Term Analysis
of Point Trajectories,” ECCV, 2010
Оптический поток Результат трекинга

Only for
Maxus 
Преимущества использования
длинных траекторий
Кадр 0 Кадр 30 Кадр 50 Кадр 80
Кадры из фильма «Miss Marple: Murder at the vicarage»

Only for
Maxus 
Пример данных трекера
Кадр 0
Выбранные точки
Кадр 211
Результат трекинга
Кадр 400
Результат трекинга
Точки распределяются равномерно в контрастных областях
При необходимости добавляются новые в области открытия
Цвета от новых к старым: синий, зеленый, желтый, красный,
розовый

Only for
Maxus 
Мера расстояния между траекториями
 Определяем меру расстояния между
траекториями:
 Максимум считаем по тем кадрам, где
присутствуют обе траектории
 Можем разделять сегменты даже на тех
кадрах, где они движутся одинаково

Only for
Maxus 
Мера расстояния между точками


Only for
Maxus 
Схожесть траекторий
 От расстояния переходим к мере схожести:
 Составляем квадратную матрицу схожести
Близость траекторий объекта, которые не пересекаются
по времени, учитывается за счет транзитивности расстояния
 Можем кластеризовать траектории, используя
разложение по собственным векторам

Only for
Maxus 
Кластеризация


Only for
Maxus 
Пример кластеризации
Чрезмерная
сегментация
После слияния После учета
похожести движения

Only for
Maxus 
Пример работы
Кадр 1 Кадр 110 Кадр 135 Кадр 170 Кадр 250
Видео
Сегментация
Эталон

Only for
Maxus 
Сравнение с другими методами (1/2)
Скорость работы
Качество сегментации

Only for
Maxus 
Сравнение с другими методами (2/2)
Исходный
кадр
Предложенный
метод
Rao et al., 2009RANSAC

Only for
Maxus 
Плотная разметка
 Разреженные траектории берутся из-за
ограничений по производительности
 Предлагается распространить метки на все
точки изображения после сегментации
От тех же авторов есть статья, но метод
медленный

Only for
Maxus 
31

Only for
Maxus 
Online Dense Segmentation
Характеристика
Цель: разделить объект и фон
 Работает для случая нестационарной камеры
 Может обрабатывать длинные видео «online»
 Использует долгосрочные траектории (long
term trajectories)
 Подходит для движения нежестких объектов
 Обрабатывает частичные перекрытия
32A. Elqursh and A.M. Elgammal, “Online Moving Camera
Background Subtraction,” ECCV, 2012

Only for
Maxus 
Краткое описание алгоритма
1. Инициализация для первого кадра
Для каждого последующего кадра:
2. Трекинг точек с предыдущего кадра
3. Продолжение траектории с предыдущего
кадра
4. Инкрементная кластеризация
5. Обновление меток (BG/FG) для кластеров
6. Оценка движения для всех пикселей объектов
и фона
7. Построение восстановленного фона

Only for
Maxus 
Кластеризация траекторий


Only for
Maxus 
Понижение размерности
 При помощи статистических
методов понижаем размерность
данных
 В подпространстве меньшей
размерности траектории
моделируем смесью гауссиан
(GMM)
 Получаем кластеризованные
данные
Кластеры на исходном
кадре
Пример
кластеризации
траекторий

Only for
Maxus 
Разметка объект/фон
 Помечаем кластеры как объект или фон
в зависимости от значения нескольких признаков
 Вводим функционал энергии
 Ищем разметку
Компактность
(Compactness)
Границы в
подпространстве
(Borders)
Вложенность
(Surroundedness)
Схожесть по
движению
(Affinity)

Only for
Maxus 
Оценка компактности


Only for
Maxus 
Оценка схожести движения
 Поощряем одинаковое движение для фона
 Штрафуем одинаковое движение
у объекта и у фона
характеристика меры близости кластеров
в пространстве уменьшенной размерности
–

Only for
Maxus 
Оценка границ
Штрафуем:
 Отдаленные кластеры, помеченные как фон
 Близкие кластеры, помеченные как объект и
фон
Расстояние между кластерами

Only for
Maxus 
Оценка вложенности


Only for
Maxus 
Распространение разметки
 Распространяем метки на все точки кадра
 Используем байесовский подход и марковские
цепи
Метки FG/BG Яркость
кадра
Произведение по всем
точкам
Произведение по всем
парам соседних точек
Гауссиан Поощряем одинаковые метки
Описание Feature points

Only for
Maxus 
Оценка вероятности метки
43
Скомпенсированный
пиксель
Средний вектор
движения
Оценивается по движению
особых точек
Цвет (яркость)
пикселя
Описание особых точек
Известно с предыдущего кадра
A. Elqursh and A.M. Elgammal, “Online Moving Camera

Only for
Maxus 
Пример работы
Sheikh et al., 2009
Proposed

Only for
Maxus 
Восстановление фона
Последовательность Tennis

Only for
Maxus 
Сравнение с конкурентом
Последовательность Tennis

Only for
Maxus 
Последовательность Drive1

Only for
Maxus 
Последовательность Marple

Only for
Maxus 
49

Only for
Maxus 
Заключение
 Очень популярны статистические и вероятностные методы
 Что привело к успеху: сама модель или правильно подобранные
картинки и параметры?
 Часто очень медленные
 Стоит использовать информацию о движении
с нескольких кадров (траектории)
 Нужно объединять сразу много признаков
 Возможно распространение разметки
с надежных точек на ненадежные
 Полезно понижать размерность данных
 Если задача позволяет, можно использовать глобальную
сегментацию
50

Only for
Maxus 
Литература
1. R. Tron and R. Vidal, “A Benchmark for the Comparison of 3-D Motion Segmentation
Algorithms,” in IEEE International Conference on Computer Vision and Pattern
Recognition, 2007, pp. 1–8.
2. T. Brox and J. Malik, “Object Segmentation by Long Term Analysis of Point
Trajectories,” in European Conference on Computer Vision, 2010, pp. 282–295.
3. A. Griesser, S. Roeck, A. Neubeck, and L. V. Gool, “GPU-Based Foreground-
Background Segmentation Using an Extended Colinearity Criterion,” in Vision,
Modeling, and Visualization, 2005, pp. 319–326.
4. S. Brutzer, B. Hoferlin, and G. Heidemann, “Evaluation of Background Subtraction
Techniques for Video Surveillance,” in IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2011, pp. 1937–1944.
5. Y. Sheikh, O. Javed, and T. Kanade, “Background Subtraction for Freely Moving
Cameras,” in IEEE International Conference on Computer Vision, 2009,
pp. 1219–1225.
6. A. Elqursh and A.M. Elgammal, “Online Moving Camera Background Subtraction,” in
European Conference on Computer Vision (ECCV), 2012, pp. 228–241.
7. D. Hamad, P. Biela, “Introduction to spectral clustering,” in IEEE Information and
Communication Technologies: From Theory to Applications, 2008, pp. 1–6.
51

Only for
Maxus 
Лаборатория компьютерной
графики и мультимедиа
Видеогруппа — это:
 Выпускники в аспирантурах
Англии, Франции, Швейцарии
(в России в МГУ и ИПМ им. Келдыша)
 Выпускниками защищены 5 диссертаций
 Наиболее популярные в мире сравнения
видеокодеков
 Более 3 миллионов скачанных фильтров
обработки видео
52

�ݺ�ߣ

Некоторые методы сегментации видео

More Related Content

Некоторые методы сегментации видео