Детектирование объектов переднего плана в видео

Детектирование объектов
переднего плана в видео
Александр Новиков
Video Group
CS MSU Graphics & Media Lab
Only for
Maxus 
Содержание






Введение
Обработка пространственно-временных срезов
Проверка условий 3D-геометрии сцены
Распространение пространственной и цветовой
информации
Использование информации о смене цветов
на областях открытия
Заключение
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/
Выделенный объект
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
3
Only for
Maxus 
Применения




Редактирование видео
Слежение за объектами
Удаление объектов
Конвертация 2D видео в 3D
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
4
Only for
Maxus 
Содержание






Введение
Обработка пространственно-временных
срезов
Проверка условий 3D-геометрии сцены
Распространение пространственной и цветовой
информации
Использование информации о смене цветов
на областях открытия
Заключение
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
5
Only for
Maxus 


Пространственновременные срезы (1)
Пространственно-временные
срезы — это изображения,
получаемые при перемещении
в (x,t) [(y,t)] измерениях
при фиксированном y [x]
Срезы разделяются на


H yi ( x, t ) — горизонтальные,
фиксирован y=i
Vx j ( y, t ) — вертикальные,
фиксирован x=j
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
t
Горизонтальный срез видео
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
6
Only for
Maxus 
Пространственновременные срезы (2)
t
Структура
пространственновременных срезов
позволяет определить
вид и направление
движения камеры
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
7
Only for
Maxus 
Идея метода
1)
Разбиение видео на участки с однородным
движением камеры и классификация:




2)
3)
Отсутствие движения
Панорамирование
Приближение/отдаление
Сложное движение
Восстановление фона сцены
Background subtraction и выделение движущихся
объектов
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
8
Only for
Maxus 
Алгоритм
Локальная структура срезов
Структура среза H в точке представляется
матрицей Г
J xx 
J xx
Г
 J xt
J xt 
J tt 
J xt 
J tt 
ˆ  (G  H) , H
ˆ  (G  H)
H
x
t
x
t
w
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
 Hˆ
2
x
( x  x, t  t )
 Hˆ
x
ˆ ( x  x, t  t )
( x  x, t  t ) H
t
x,t w
x,t w
 Hˆ ( x  x, t  t )
x,t w
t
— частные производные срезов,
__сглаженных фильтром Гаусса
— окно 3x3 с центром в некотором пикселе
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
9
Only for
Maxus 
Алгоритм
Локальная направленность

Вычисляется локальная ориентация ϕ в окне w
 
  2 ,   0
  
 
    , 
 2 2
   , otherwise

2

1
2
  tan 1
2 J xt
J tt  J xx
c — мера того, насколько точно
ϕ оценивает локальную
ориентацию,
с = 1 — точная направленность
(J xx  J tt ) 2  4 J 2xt
c
, c  [0,1]
2
(J xx  J tt )
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
10
Only for
Maxus 
Алгоритм
Гистограмма направленностей

Строится двумерная гистограмма локальных
направленностей

c( x, t ) y i ,  ( x, t ) y i  ˆ


M (ˆ, t )   i x
otherwise

0,

На кадрах [k,k+N] выделяется доминирующая
траектория {ϕ}, если для них выполняется
kN
 p(t )
kN
t k
 M ( , t )
p(t ) 
T
N, T

M( , t )
 / 2  / 2
max
— константы, в статье 15 и 0.6
t k
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
11
Only for
Maxus 
Алгоритм
Классификация движения камеры
t


Неподвижная камера
y
 [a , a ] a  0

2
Панорамирование
ϕ
  a ,   a

Отдаление/приближение
M ( , t )

t  0
1
 M ( , t )
t


CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
2
t
y

2
 0
Иначе — сложное
движение

ϕ


2
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
12
Only for
Maxus 
Алгоритм
Выделение фона на срезах

Дискретизация гистограммы
1  [90,45)
N( k ) 

M( , t )



i  k
i
t
 2  [45,25)
 3  [25,5)
 4  [5,5]
 5  (5,25]
 6  (25,45]
 7  (45,90]
Выделение на срезах пикселей с движением
близким к основному (LoS — layer of support)
ˆ  arg 

N( k )
max

 k

ˆ
 
1,
LoS ( x, t ) y i  
0, otherwise
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
t
y
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
13
Only for
Maxus 
Алгоритм
Восстановление панорамы фона

Пиксели с LoS = 1 считаются принадлежащими фону

Для каждого кадра t выбирается сдвиг
ˆ ( x, t )  H
ˆ ( x  d , t  1) },
d (t )  arg min{med H
y i
y i
d
x
ˆ — выбранный для кадра t срез с наибольшим
где H
yi
количеством текстурной информации


C
(
t
)

C
(
t

1
)


y

i
y

i
ˆ
H  arg max 

H
n
(
t
)

n
(
t

1
)

1


y i
y i


y i
С (t ) y i   c( x, t ) y i LoS ( x, t ) y i
x
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
n(t ) y i   LoS ( x, t ) y i
x
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
14
Only for
Maxus 
Алгоритм
Color back-projection



По LoS для фона инвертированием вычисляется LoS
для переднего плана
Строится дискретизованная гистограмма C цветов
пикселей со значениями LoS переднего плана = 1
Передний план F вычисляется по формуле:
1 ˆ
ˆ ( X , t ))  Image( X , t )
F( X , t )  (С( Image( X , t ))  R
2
Rˆ ( X , t ) — нормализованная карта разницы |Image-Background|
Сˆ — нормализованная гистограмма C
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
15
Only for
Maxus 
Результаты (1)
Background subtraction
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
16
Only for
Maxus 
Результаты (2)
Color back-projection
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
17
Only for
Maxus 
Выводы
Достоинства:


Скорость работы
Восстановление фона
Недостатки:


Отсутствие временной целостности
Недостаточно точная сегментация
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis
and Segmentation Through Spatio-Temporal Slices Processing”,
IEEE ToIP, 2003
18
Only for
Maxus 
Содержание






Введение
Обработка пространственно-временных срезов
Проверка условий 3D-геометрии сцены
Распространение пространственной и цветовой
информации
Использование информации о смене цветов
на областях открытия
Заключение
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
19
Only for
Maxus 
Схема работы алгоритма
Восстановление структуры сцены по движению
Оценка движения и глубины
1)
2)


При фиксированной сегментации оцениваются движение
и области открытия
Строится карта глубины и карта ошибок геометрии
3)
Выделение фона и переднего плана
4)
Повторение второго и третьего шагов k (2-3) раз
5)
Matting границ выделенных объектов
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
20
Only for
Maxus 
Алгоритм
Structure From Motion


Выполняется поиск 3D-feature points
Для каждого кадра вычисляются матрицы камеры
u tX  K t ( Rt X  T t )
u tX — проекция 3D-точки X на кадр t
K t , R t , T t — матрицы камеры для кадра t
Вставленные объекты демонстрируют определенную геометрию сцены
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
G. Zhang, X. Qin, W. Hua, T.-T. Wong, P.-A. Heng, H. Bao,
“Robust metric reconstruction from challenging video sequences”,
IEEE CVPR, 2007
21
Only for
Maxus 
Алгоритм
Оценка движения (1)
Оценка движения и поиск областей закрытия
выполняется решением задачи минимизации
n 1
arg min  ( E t ,t 1 (d , o)  E t 1,t (d , o))
d ,o
t 1
E t ,t 1 (d , o)  [mt ,t 1 (i)   s t ,t 1 (i, j )]  Qt ,t 1 ( D)
i f t
jN i
d t ,t 1 (i)
oit ,t 1 (i)
— motion-вектор пикселя i при переходе с кадра t к t+1
— индикатор принадлежности пикселя i области открытия
\\\при переходе от кадра t к t+1
N i — множество 8 пикселей, соседних с i-м
mt ,t 1 (i), s t ,t 1 (i, j ), — условия соответствия данных, гладкости поля motion\\\векторов и соответствия 3D-feature points
t ,t 1
Q
( D)
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
22
Only for
Maxus 
Алгоритм
Оценка движения (2)
E t ,t 1 (d , o)  [mt,t 1 (i)   s t ,t 1 (i, j )]  Qt ,t 1 ( D)
i f t
jN i
Условие соответствия данных:
  dt ,t 1 (i ),
oit ,t 1  0,  it   it1

mt ,t 1 (i )  min{  dt ,t 1 (i ),o }, oit ,t 1  0,  it   it1
t ,t 1
 ,
o
1
i
 o
 dt ,t 1 (i) 
f t (i )  f t 1 (i)
 d  f (i)  f
t
t 1
2
(i)
2
i — пиксель кадра t +1 соответствующий i-тому по dt,t+1
f t (i) — цвет пикселя i кадра t
 it (i) — индикатор принадлежности пикселя i кадра t переднему
o ,d
\\\плану
— константы, в статье 0.5 и 400 соответственно
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
23
Only for
Maxus 
Алгоритм
Оценка движения (3)
E t ,t 1 (d , o)  [mt,t 1 (i)   s t ,t 1 (i, j )]  Qt ,t 1 ( D)
i f t
jN i
Условие гладкости поля motion-векторов:
s t ,t 1 (i, j )   s  st ,t 1 (i, j )  o oit ,t 1  otj,t 1   w oit ,t 1  Wi t ,t 1
2
t
t 1
t ,t 1
t ,t 1




min{
d
(
i
)

d
(
j
)
,

}

i
j
s
 st ,t 1 (i, j )  
t
t 1



i
j

0,
Wi t ,t 1 — 1, если для пикселя f t(i) нет соответствующего по dt+1,t
///пикселя в f t+1, 0 — иначе
 st ,t 1 (i, j ) — мера сонаправленности векторов dt,t+1(i) и dt,t+1(j)
 s ,  o ,  w — балансирующие коэффициенты, 0.1, 0.21 и 0.6 в статье
 s — ограничение сверху, 4 в статье
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
24
Only for
Maxus 
Алгоритм
Оценка движения (4)
E t ,t 1 (d , o)  [mt,t 1 (i)   s t ,t 1 (i, j )]  Qt ,t 1 ( D)
jN i
i f t
Условие соответствия 3D-feature points:
Q
t ,t 1
 D 
 d
t ,t 1
X D f t , f t 1 ( X )
(u )  (u
t
X
t 1
X
u )
t
X
2
D — множество всех 3D-feature points
u tX — проекция 3D-точки X на кадр t
 (X ) — множество кадров, на которых X имеет
D
\\\соответствующую feature point
— коэффициент, берется большим, в статье равен 100
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
25
Only for
Maxus 
Алгоритм
Карта глубины и карта ошибок (1)


Трек — последовательность пикселей видео,
связанных по векторам движения
Связь между пикселями i и i′ разрывается, если:
Хотя бы один из них отмечен как область открытия
t ,t 1
t ,t 1
t 1,t
 Ошибка согласованности optical flow e
(
i
)

d
(
i
)

d
(i)
flow
выше некоторого предела (2.0 в статье)

Красные стрелки —
motion-векторы
Синим отмечены
пиксели трека
Кадр 1
Кадр 2
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Кадр 3
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
27
Only for
Maxus 
Алгоритм
Карта глубины и карта ошибок (2)

Все пиксели
3D-точке Xp
x tp трека p от кадра fl до fr должны соответствовать одной
xtp  K t ( Rt X p  T t )

Xp оценивается минимизацией среднеквадратического отклонения (RMSE)
r
1
t
t
t
t
arg min
x

K
(R
X

T
)

p
p
Xp
r  l  1 t l

2
Карта глубины для кадров берется из z координат точек треков,
для всех пикселей записывается RMSE в карту ошибок  t
[ xtp , y tp , z tp ]  R t X p  Tt
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
28
Only for
Maxus 
Алгоритм
Результаты (1)


Большое значение ошибки — пиксель находится
на объекте переднего плана
Проблема — карта ошибок зашумлена на границах
объектов
Кадр
Полученная карта глубины
Ярче — дальше
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Карта ошибок
Ярче — больше
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
29
Only for
Maxus 
Алгоритм
Результаты (2)
В случае слежения камеры за объектом строится
неверная карта глубины, и по карте ошибок нельзя
выделить объект
Кадр
Полученная карта глубины
Ярче — дальше
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Карта ошибок
Ярче — больше
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
30
Only for
Maxus 
Алгоритм
3D-warping
Выполняется 3D-warping кадров 2l
соседних кадров на текущий с
использованием карты глубины
Различия между полученными
кадрами и текущим позволяют
выявить движущиеся объекты
Красным отмечены точки, не имеющие проекции
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
31
Only for
Maxus 
Алгоритм
Сегментация
Разделение на фон и передний план выполняется
минимизацией функции энергии по α:
n
EB ( )    ( Lt (i)  T GTt (i)  S  GSt (i, j ))
t 1 i f t
Lt
jN i
— функция правдоподобия данных
GTt — условие временной гладкости
GSt — условие пространственной гладкости
N i — множество 8 соседних с i-м пикселей
T , S — балансирующие коэффициенты
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
34
Only for
Maxus 
Результаты (1)
Кадр последовательности
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Выделенный объект переднего плана
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
37
Only for
Maxus 
Результаты (2)
Кадр последовательности
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Выделенный объект переднего плана
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
38
Only for
Maxus 
Выводы
Достоинства:


Высокая точность сегментации
Восстановление фона за объектами
Недостатки:


Очень низкая скорость работы
Основан на Structure From Motion
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao,
“Moving object extraction with a hand-held camera”, IEEE ICCV,
2007
39
Only for
Maxus 
Содержание






Введение
Обработка пространственно-временных срезов
Проверка условий 3D-геометрии сцены
Распространение пространственной
и цветовой информации
Использование информации о смене цветов
на областях открытия
Заключение
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
40
Only for
Maxus 
Идея метода



Выделить кадры со значительными областями
с движением, отличным от глобального
Выделить на них двигающиеся части объектов
переднего плана (подобъекты)
Собрав информацию о цвете и расположении
подобъектов, распространить их во времени
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
41
Only for
Maxus 
Алгоритм
Motion cues
Motion cue – разница между локальным движением
и глобальным смещением камеры
 Оценка движения



Глобального (ищутся feature points алгоритмом SIFT,
устанавливаются соответствия и строится
преобразование) — mo(x,y)
Локального (optical flow) — mg(x,y)
Вычисление motion cues
mc( x, y)  mo ( x, y)  mg ( x, y)
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
2
2
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
42
Only for
Maxus 
Алгоритм
Выделение ключевых кадров
Ключевым называется кадр, на котором объект, либо
его часть совершает заметное движение, отличное
от глобального
Критерии:

Большое количество пикселей с движением, отличным
от глобального
 (mc( x, y)   )  minArea

Их компактное расположение
Var(( x, y) | mc( x, y)   )  maxSpan
maxSpan, minArea, 
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
— константы
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
43
Only for
Maxus 
Алгоритм
Выделение движущихся подобъектов (1)
Для каждого кадра строится функция правдоподобия
для произвольного распределения меток “фон”
и “движущийся объект”
На основании информации о цвете:
p(li | i  1,, M ) 
  ψ(l , l )
i
i{1,, M } jN i
j
ψ(li , l j )  exp(
li l j
(  d(i, j ))
)
li — метка i-го пикселя (-1 — движущийся объект, 1 — фон)
N i — множество 8 пикселей, соседних с i-м
d(i, j )
,
— разница по цвету между пикселями i и j
— константы
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
44
Only for
Maxus 
Алгоритм
Выделение движущихся подобъектов (2)
На основании информации о движении:
p(I | {li , i  1,, M }) 
p
m
i{1,, M }
(mci , li )
p m (mci | li )  exp(li (mci   m ))
М — количество пикселей в изображении
li — метка i-го пикселя (-1 — движущийся объект, 1 — фон)
N i — множество 8 пикселей, соседних с i-м
 m — константа
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
45
Only for
Maxus 
Алгоритм
Выделение движущихся подобъектов (3)

Объединяя информацию о цвете и движении, получим
функцию правдоподобия
P(L | I)   p m (mci | li ) ψ(li , l j )
iI
iI jN i
L — множество всех меток
I


— множество всех пикселей кадра
Для каждого ключевого кадра находится набор меток
li, её максимизирующий
Выделяются подобъекты — движущиеся на конкретном
ключевом кадре части объектов
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
46
Only for
Maxus 
Алгоритм
Ключевые кадры и motion cues
Key frames
Motion cues
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
47
Only for
Maxus 
Алгоритм
Ключевые кадры и подобъекты
Key frames
Moving sub-objects
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
48
Only for
Maxus 
Алгоритм
Близость по цвету

Строится распределение цветов в виде Gaussian Mixture Model (GMM)
G f  gi , i  1,, n

Функция близости пикселя с цветом
c к цветовой модели
affi c (c)  max g j (c)
g j G f

Функция правдоподобия
сегментации с точки зрения
цветовой модели
pc (ci | li )  exp(li (log(affi c (ci ))   c )
 с — константа
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Распределение
цветов объектов
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
49
Only for
Maxus 
Алгоритм
Удаление фоновых компонент из GMM



Из-за ошибок выделения
подобъектов в GMM могли
появиться компоненты gi,
связанные с фоном
Вычисляется мера близости
компоненты GMM к фону
сцены
Из GMM исключаются все gi
со значениями близости,
превышающими порог
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
50
Only for
Maxus 
Алгоритм
Пространственная близость

Вводится мера пространственной близости точки к выделенным
подобъектам и пространственная функция правдоподобия сегментации
affi ts ( xi ) 
1
max exp( 
( xi  x j )T ( xi  x j )
2
2
pts ( xi | li )  exp(li (log(affi ts ( xi ))   s )
2
jF
2
)
F — движущийся объект
 ,  s — константы

Вводится обновлённая функция правдоподобия, и еще раз выполняется
сегментация ключевых кадров
logp t ( f i | li )  logp tm (mci | li )  c logp tc (ci | li )  s logp ts ( xi | li )
s , c — балансирующие коэффициенты
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
51
Алгоритм
Only for
Maxus 
Распространение пространственной
информации
Для каждого ключевого кадра k:
 Распространить пространственную информацию
на кадры k+1, k+2, … следующим образом:
1.
2.
3.
4.

Инициализировать пространственную функцию
правдоподобия на кадре t+1 функцией кадра t
Выделить движущиеся объекты обновленной функцией
правдоподобия
По выделенным объектам обновить пространственную
информацию и функцию правдоподобия кадра t+1
Если кадр t+1 ключевой и выделенные на шаге 2 объекты
покрывают выделенные ранее, удалить кадр из ключевых
Аналогично распространить на кадры k-1, k-2, …
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
52
Only for
Maxus 
Результаты (1)
Кадры последовательности
Результаты сегментации
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
53
Only for
Maxus 
Результаты (2)
Кадры последовательности
Результаты сегментации
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
F. Liu, M. Gleicher, “Learning color and locality cues for moving
object detection and segmentation”, IEEE CVPR, 2009
54
Only for
Maxus 
Выводы
Достоинства:


Качество сегментации
Временная целостность выделенных объектов
Недостатки:


Время работы
Проблемы при близости объектов к фону по цвету
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
55
Only for
Maxus 
Содержание






Введение
Обработка пространственно-временных срезов
Проверка условий 3D-геометрии сцены
Распространение пространственной и цветовой
информации
Использование информации о смене
цветов на областях открытия
Заключение
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
56
Only for
Maxus 
T-Junctions
T-Junction — это фигура из двух отрезков,
формирующих букву T, расположенная на местах
резкой смены градиентов на изображении
y
t
Пример выделенных T-Junctions. Заметим, что красные отрезки лежат на фоне
сцены, зеленые — на движущихся объектах
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
N. Apostoloff, A. W. Fitzgibbon, “Learning spatiotemporal Tjunctions for occlusion detection”, IEEE CVPR, 2005
57
Only for
Maxus 
Алгоритм
Поиск T-Junctions


Первым шагом выполняется поиск T-Junctions,
которые выступают как индикаторы областей
открытия
Таким образом получены спаренные пробы
пикселей из переднего плана и фона
y
t
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
N. Apostoloff, A. Fitzgibbon, “Automatic video segmentation using
spatiotemporal T-junctions”, BMVC, 2007
58
Only for
Maxus 
Алгоритм
Использование цветовой информации
По выделенным T-Junctions строятся GMM-модели


Распределения цветов фона и переднего плана сцены
Смены цвета на областях открытия
Модель областей закрытия: каждый
столбец соответствует одному варианту
смены цвета
Кадры последовательности
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
N. Apostoloff, A. Fitzgibbon, “Automatic video segmentation using
spatiotemporal T-junctions”, BMVC, 2007
59
Only for
Maxus 
Алгоритм
Сегментация
Разделение на фон и передний план происходит
минимизацией для каждого кадра функции энергии:
E  U W V
U
— отвечает за близость выделенных объектов по цвету
///к цветовой модели
W
— условие соответствия модели смены цветов пикселей
///на областях открытия
V
— условие пространственной гладкости
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
N. Apostoloff, A. Fitzgibbon, “Automatic video segmentation using
spatiotemporal T-junctions”, BMVC, 2007
60
Only for
Maxus 
Результаты (1)
Кадр последовательности
Сегментация без условия
смены цветов
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Сегментация с использованием
всех условий
N. Apostoloff, A. Fitzgibbon, “Automatic video segmentation using
spatiotemporal T-junctions”, BMVC, 2007
61
Only for
Maxus 
Результаты (2)
Исходное видео
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
Результат сегментации
N. Apostoloff, A. Fitzgibbon, “Automatic video segmentation using
spatiotemporal T-junctions”, BMVC, 2007
62
Only for
Maxus 
Результаты (3)
Исходное видео
Результат сегментации
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
N. Apostoloff, A. Fitzgibbon, “Automatic video segmentation using
spatiotemporal T-junctions”, BMVC, 2007
63
Only for
Maxus 
Выводы
Достоинство:


Скорость работы
Интересная идея решения задачи
Недостатки:


Основное движение должно быть горизонтальным
Проблемы с временной целостностью
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
64
Only for
Maxus 
Содержание






Введение
Обработка пространственно-временных срезов
Проверка условий 3D-геометрии сцены
Распространение пространственной и цветовой
информации
Использование информации о смене цветов
на областях открытия
Заключение
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
65
Only for
Maxus 
Дальнейшие планы (1)
Алгоритм:
1.
2.
3.
4.
Оценка движения
Построение гистограммы векторов ME
Кластеризация гистограммы (Mean-shift)
Наибольший кластер — фон, остальные — движущиеся объекты
Визуализация гистограммы (высоты соответствуют Ортогональная проекция гистограммы
количеству векторов с направлением)
(белые – векторы движения фона,
синие – переднего плана)
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
66
Only for
Maxus 
Дальнейшие планы (2)
Результаты сегментации
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
67
Only for
Maxus 
Дальнейшие планы (3)
Решить проблемы:
 Разбиения на чрезмерно большое количество
кластеров (пространственным объединением
кластеров)
 Отсутствия временной целостности
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
68
Only for
Maxus 
Литература
1.
2.
3.
4.
5.
6.
7.
Ch.-W. Ngo, T.-Ch. Pong, H.-J. Zhang, “Motion Analysis and Segmentation
Through Spatio-Temporal Slices Processing”, IEEETransactions on Image
Processing, vol. 2, 2003
G. Zhang, X. Qin, W. Hua, T.-T. Wong, P.-A. Heng, H. Bao, “Robust metric
reconstruction from challenging video sequences”, IEEE CVPR, 2007
G. Zhang, J. Jia, W. Xiong, T.-T. Wong, P.-A. Heng, H. Bao, “Moving object
extraction with a hand-held camera”, IEEE ICCV, 2007
F. Liu, M. Gleicher, “Learning color and locality cues for moving object detection
and segmentation”, IEEE CVPR, 2009
N. Apostoloff, A. Fitzgibbon, “Automatic video segmentation using spatiotemporal
T-junctions”, BMVC, 2007
N. Apostoloff, A. W. Fitzgibbon, “Learning spatiotemporal T-junctions for
occlusion detection”, IEEE CVPR, 2005
V. Kolmogorov, R. Zabih, “What energy functions can be minimized via graph
cuts”, IEEE ECCV, 2002
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
69
Only for
Maxus 
Лаборатория компьютерной
графики и мультимедиа
Видеогруппа — это:
 Выпускники в аспирантурах Англии,
Франции, Швейцарии (в России в МГУ и
ИПМ им. Келдыша)
 Выпускниками защищено 5 диссертаций
 Наиболее популярные в мире сравнения
видеокодеков
 Более 3 миллионов скачанных фильтров
обработки видео
CS MSU Graphics & Media Lab (Video Group)
www.compression.ru/video/
70