close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Вычитание фона и
сопровождение объектов
Антон Конушин
Система видеонаблюдения
• Камера, наблюдающая некоторую сцену (в закрытом
или открытом пространстве)
• Необходимо выделить «объекты интереса» на
каждом кадре
• Результат:
• Ограничивающий прямоугольник
• Попиксельая маска объекта интереса
Свойства задачи
• Камеру считаем стационарной, не меняющей ракурса
• Фон считаем «стабильным», малоподвижным,
незначительно меняющимся между кадрами
• Вывод – объекты должны отличаться от фона
• Названия - «детектор движения», «вычитание фона»,
«background subtraction»
Смысл
• Нужно построить классификатор, которой для каждого
пикселя нового кадра (или блока, фрагмента,
сегмента) будет определять «объект» или «фон»
• «Порождающий подход» – построение модели фона
• «Дискриминантный подход» – обучение
классификатора по выборке
«Вычитание фона»
-
=
• Построим самый простой метод
• Возьмем «чистое» изображение без объектов – «фон»
(background)
• Вычтем фон из новых изображений с объектами
• Сравним разницу для каждого пикселя с порогом
– Порог – параметр алгоритма
• Если разница больше порога - то считаем пиксель
принадлежащим «переднему плану» (foreground)
• Получаем бинарную маску «переднего плана»
– Фон (0), передний план (1)
Обработка переднего плана
•
•
Бинарная маска переднего плана обычно шумная и пиксели не
связаны между собой
Что нам нужно сделать? :
• Уменьшить шум в изображении (фильтрация)
• Выделить области, потенциально соответствующие объектам
(связанные компоненты)
•
«Блоб» («капля», blob) - связанная компоненты маски переднего
плана, потенциальный объект
Базовый алгоритм
•
•
•
Если объект в сцене может быть только один, то самый крупную
связанную компоненту (блоб) будем считать объектом
Получили «базовый» алгоритм вычитания фона, который
работает в ряде лабораторных задач (отслеживание мышей)
Схема:
•
•
•
•
Попиксельное вычитание изображения фона из текущего кадра
Сравнение попиксельной разницы с порогом
Фильтрация маски
Выделение связанных компонент и выбор самой большой
Если объектов много?
• Случай множества связанных компонент – это
уже задача отслеживания объекта
• Некоторые подходы к ней рассмотрим на
следующей лекции
Проблемы вычитания фона
Плюс камера обычно «шумит»
Моделирование фона
• Реальная статичная сцена:
• «Шум камеры»
• Интенсивность меняется в небольших пределах вокруг
какого-то значения
• Нормальное (Гауссово) распределение
Wren, Christopher R., Ali Azarbayejani, Trevor Darrell, and Alex Pentland. “Pfinder:
Real-Time Tracking of the Human Body,” IEEE PAMI, 1997
Оценка параметров модели
• По чистому видеоролику для каждого пикселя
вычислим параметры фона для модели – нормального
распределения (случай одного канала):
• Вычисляем среднее
• Вычисляем дисперсию
1

N
N
x
i
i 1
N
1
2
2 
(
x


)
 i
N  1 i 1
Вычитание фона
• Вероятность x при вычисленных параметрах модели
фона:
 ( x | , ) 
1
e
 2

( x   )2
2 2
• Проще использовать сравнение с порогом
• Считаем, что все пиксели фона должны попасть в
интервал (u-3σ,u+3σ)
• Если |x-u|>3σ, тогда x – пиксель переднего плана
Пример работы
• Background subtraction output video
Длительное время работы
• Как меняется фон на
длинных периодах времени?
• Может плавно меняться
освещенность сцены
• Что это скажется на работе
алгоритма?
• Что мы можем сделать для
того, чтобы алгоритм мог
работать?
• Нам нужно дополнить
алгоритм этапом обновления
модели фона
Общая схема вычитания фона
- Initialize_background_model()
- For t = 1:N
-
Compute_frame_difference()
Threshold_frame_difference()
Noise_removal()
Update_background_model()
- end
Как обновить модель фона для случая одной
гауссианы?
Обновление параметров модели
Одноканальное изображение (серое)
• Обновление матожидания
t 1  t  (1   ) xt 1
• Обновление дисперсии
 t21   ( t21  ( t1  t )2 )  (1   )( xt1  t 1 ) 2
а – скорость обновления (обучения)
Многоканальное изображение
• Можно рассчитать полную матрицу ковариации K
• Обновлять полную матрицу сложно
• Обновление только среднего, с сохранением
ковариации
t 1  t  (1   ) xt 1
Как настраивать модель?
• Если есть размеченные данные:
• Оценка точности и полноты
(precision/recall) на наборе
видеороликов
• Выбор параметров, оптимизирующих
желаемую точность
• Если нет размеченных данных
• Можно взять видео без объектов
• Настроить параметры таким образом,
чтобы получить заданное количество
ложных обнаружений
• Минимальные пороги для достижения
заданной «чувствительности»
Более сложный пример
Распределение интенсивности красного
и зеленого каналов
Как моделировать фон в таких, более сложных,
случаях?
Более сложные модели
P( xt )
«Многомодальное
распределение» значения могут
группироваться в
несколько кластеров
Смесь Гауссиан
Мы полагаем, что
сигнал порождён
несколькими
независимыми
моделями
P( xt )
Пример №1:
• Вода
• Блик на воде
K
P( xt )   i ,t N (xt , i ,t ,  i ,t )
i 1
Пример №2:
• Небо
• Листья на дереве
Смесь Гауссиан

Плотность вероятности яркости пикселя x при
модели смести из K нормальных распределений
K
P( xt )   i ,t N (xt , i ,t ,  i ,t )
i 1
i ,t
•
- вес компоненты I в момент t
Вычисление смеси требует сложного EМ
(Expectation-Maximization) алгоритма (не в реальном
времени), поэтому был предложен приближенный
алгоритм
W.E.L.Grimson, C.Stauffer. Adaptive background mixture models for real-time
tracking. CVPR 1999
Обучение смеси на лету
• Пусть N – количество компонент в смеси
• Инициализируем 1ую компоненту по первому
изображению, вес = 1, вес остальных – 0
• Сравниваем пиксель с каждой компонентой, пока
не найдем совпадения
• Обновляем матожидание и дисперсию совпавшей
компоненты
• Если совпадения не найдено, то заменяем
компоненту с наименьшим весом
• Обновляем веса
K

i ,t
i 1
N (xt , i ,t , i ,t )
Обновление весов
K
Обновление весов:
P( xt )   i ,t N (xt , i ,t ,  i ,t )
i 1
i,t  (1  a )i ,t 1  aM i ,t
M i ,t
= 1, если интенсивность пикселя
удовлетворяет i-ой компоненте
После обновления всех весов, они нормализуются
Моделирование фона
• Упорядочим все компоненты по критерию
i / 
• Чем «стабильнее» компонента, тем выше
• Чем больше вес (чаще встречается, тем тоже выше)
• Определим порог T - какая доля выборки для
каждого пикселя должна соответствовать фону
• Тогда фон для каждого пикселя:
b
B  arg min (  i  T )
b
i 1
• Все остальные компоненты - объекты
Иллюстрация работы
(1)
(2)
(3)
(4)
1. Текущий кадр видео (момент t)
2. Старшая гауссиана для каждого пиксела (модель
фона)
3. Вторая гауссиана для каждого пиксела (модель
движущегося объекта)
4. Маска переднего плана для текущего кадра
Пример визуализации фона
Ещё посложнее пример
Камера наблюдения в лесу у кормушки для птиц
График яркости одного из пикселов
Как сработают алгоритмы и почему?
Как быть?
Будем анализировать окрестность каждого пиксела
Статистики по окрестностям
Ko, T.[Teresa], Soatto, S.[Stefano], Estrin, D.[Deborah], Background Subtraction
on Distributions, ECCV 2008
Схема алгоритма
•
Посчитаем статистику (гистограмму) по 3D окрестности пикселя
(фон):
•
Посчитаем статистику по 2д окрестности пикселя на текущем
кадре:
•
Вычислим разницу:
•
Обновление модели:
Результаты работы
Получение фона
• Как быть, если невозможно получить обучающий ролик
без объектов?
• Задача весьма сложная, есть много методов
• Простейший вариант – взять медиану всех кадров
Пример медианного фона
-
=
Получение фона
• В сложных случаях медиана не помогает
• Предлагаются разные идеи – поиск наиболее
стабильных кластеров, пространственная связанность и
т.д.
Данные
• На пути создания общедоступных тестовых баз
два препятствия:
• Приватность
• Сложность разметки данных
• PETS Performance Evaluation of Tracking and
Surveillance
• http://www.cvg.rdg.ac.uk/PETS2009/a.html
Пример
Пример слежения с реальной
системы видеонаблюдения
Развитие методов
• Другие признаки изображения
• Более сложные модели фона (параметрические,
непараметрические)
• Работа с окрестностями
• Дискриминантный подход - обучение специальных
классификаторов фон / объект
• Подавление теней и отражений
• Обработка внештатных ситуаций (резкое изменение
освещения)
• Ускорение вычислений (иерархические методы,
параллельные реализации, GPU и т.д.)
Резюме вычитания фона
• Вычитание фона – очень эффективный
инструмент выделения объектов при условии
стационарности камеры
• Почти вся видеоаналитика в современных
системах основана на вычитании фона
• Есть множество методов вычитания фона,
несколько из которых мы рассмотрели
• Точное вычитание фона в реальном времени для
HD разрешений сделать крайне сложно
Сопровождение объектов
• Есть последовательность кадров (или поток)
• Объект уже выделен на первом кадре («рамкой»?) - X(0)
• Нужно определить его положение на всех последующих
кадрах
• Результат – след (track)
• X(1), X(2), X(3),…,X(N)
• «Object tracking» (сопровождение объектов, отслеживание
объектов, слежение за объектами)
Сложность оценки результата
•
•
Для оценки качества работы алгоритмов слежения и настройки
параметров требуются размеченные эталонные данные
Подготовить эталонные данные для видео существенно
сложнее, чем для изображений
• Один эталонный пример для выделения объектов – 1 изображение
• Один эталонный пример для отслеживания объектов - 1 видео
Сложность задачи
• Масштабируемость
• Видео гораздо больше одного
изображения, гораздо выше
вычислительная нагрузка
• Изменение по времени
• Вид объекта меняется от кадра к
кадру из-за ракурса, изменения
освещения, внутренних изменений
(скейтбордист)
• Несколько объектов
• В сцене могут быть несколько
объектов, которые могут быть похожи
друг на друга, перекрывать друг друга
и т.д.
Множество объектов
• Задача «выделения и сопровождения множества
объектов»
• Нужно найти все объекты на всех кадрах
• Определить сколько у нас разных «экземпляров» объектов
• Найти на каких кадрах виден каждый экземпляр и где он именно
• Обобщение задачи «выделение объектов на
изображении» на случай видео
• Мы только немного затронем задачу сопровождения
множества объектов
Методы к рассмотрению
• Сопровождение одного объекта
• Сопоставление шаблонов
– Кросс-корелляция
– На основе карт краёв
• «Стая точек»
• Сдвиг среднего
• Адаптация на лету
• Сопровождение множества объектов
• Ассоциация обнаружений между кадрами
Сопровождение объектов
• Можем ли мы на каждом кадре выделить объект?
•
•
•
•
Фон динамический (нельзя вычитать фон)
Вычислительно тяжело
Может быть много ошибок (изменчивость объектов)
Может не быть детектора для объектов
• Придётся строить какую-то упрощенную модель
объекта, и искать на следующем кадре похожий
объект в окрестности предыдущего положения
Схема слежения
Выбор
пространства
признаков
Инициализация
модели
…
Текущий
кадр
…
Представление
модели в
выбранном
пространстве
Схема слежения
Поиск в
окрестности в
следующем
кадре
Старт с
текущей
позиции
Выбор
положения,
максимизирую
щего сходство
Повторение
процедуры
для
следующего
кадра
Модель
…
Текущий
кадр
Кандидат
…
Представление объектов
• Как будем описывать объект («модель объекта») ?
• Шаблон
• Набор точек
• Признаки объекта
Сопоставление шаблонов
• Фиксируем изображение объекта
(шаблон – pattern)
• Будем искать положение шаблона в
новом кадре
• Например, в окрестности предыдущего
положения
• Попиксельно будем сравнивать
шаблон и фрагмент нового кадра с
помощью какой-нибудь метрики
• Например, SSD или NCC
(NCC) Normalized cross correlation
Пример: пульт ТВ
Шаблон (слева), изображение (в центре), карта нормализованной
корреляции (справа)
• Пик яркости (максимум корреляции) соответствует положению
руки (искомого шаблона)
•
Пример: пульт ТВ
Пример: пульт ТВ
Пример: пульт ТВ
Пример: пульт ТВ
Края для сопоставления шаблонов
Мы знаем, что в края – очень информативный признак, и они
устойчивы к измненеию освещения
• Попробуем использовать только края для поиска / отслеживания
объекта
• Как эффективно сопоставлять карты краев?
• Попиксельно явно нельзя!
•
Метрики
•
Сhamfer Distance
Для каждого пикселя a края шаблона A вычисляем
расстояние до ближайшего пикселя b края
изображения B
•
r (a, B)  min a  b
bB
Суммируем все найденные расстояния
•
ChDist ( A, B )   min a  b
aA
•
bB
Hausdorff Distance
Почти то же самое, но берём не сумму, а
максимальное расстояния
•
HausDist ( A, B )  max min a  b
a A
bB
Какую метрику использовать заранее сказать нельзя, нужна
экспериментальная проверка
Поиск ближайших пикселей края
Вопрос: как найти ближайший пиксель края на
изображении?
Distance Transform
«Дистантное преобразование»
Для каждого пикселя вычисляется расстояние до
ближайшего пикселя края
•
•
Многопроходный алгоритм (пометить соседей, потом их
соседей и т.д.)
Двухпроходный алгоритм
Применение DT
 Совмещаем шаблон и карту DT
 Вычисляем ошибку, суммирую все значения в пикселях
краев (для Chamfer distance)
Пример поиска с помощью DT
Сопровождение
• Карта краёв шаблона используется для дальнейшего сравнения
• Вычисляется метрика Хаусдорфа на основании DT
• Шаблон обновляется как набор краёв, ближайших к краям шаблона
предыдущего кадра
• HUTTENLOCHER, D., NOH, J., AND RUCKLIDGE, W.. Tracking nonrigid objects
in complex scenes. ICCV 1993
Пример работы
Множество точек
• Мы умеем вычислять движение отдельных
точек с помощью локального метода
оценки оптического потока Lucas-Kanade
• Но каждая точка в отдельности может
быстро сбиться из-за ошибок в
вычислении оптического потока и его
несоответствия движению точек сцены
• Решение – использование «стаи точек»
(«flock of features»)
Пример: отслеживание руки
• Стая – множество контрольных точек,
удовлетворяющих 2м условиям:
• Никакие две контрольные точки не совпадают (порог на
близость)
• Никакая контрольные точки не уходят далеко от
медианного центра (порог на удаление)
Пример: отслеживание руки
• Шаг 1: инициализация
• Находим 100 контрольных точек с помощью метода поиска
локальных особенностей (Harris corners) в рамке руки
• Вычисляем медиану
• Вычисляем цветовую статистику в окрестности центра
– Одна гауссиана (или гистограмма)
– Это модель кожи
• Разметить в рамке руки все пиксели, похожие на кожу
Пример: отслеживание руки
• Шаг 2: слежение
• Отслеживаем контрольные точки
• Если точка нарушает условия стаи, её удаляем
• Шаг 3: инициализация новых контрольных точек
• Ищем особенности (Harris corners)
• Если точка не на коже, то отбрасываем её
Пример работы
Мean-Shift («Cдвиг среднего»)
Инициализация
объекта
слежения
Модель =
распределение
признаков в
объекте
Выбор
пространства
признаков
0.35
0.3
Probability
Квантованная
цветовая
модель
0.25
0.2
0.15
0.1
0.05
0
1
2
3
.
.
.
color
• Вместо жесткого шаблона вычислим вектор-признак по области объекта
• Например, гистограмму распределения цветов
m
Слежение сдвигом среднего
Модель
(центр в 0)
Кандидат
(центр в y)
0.35
0 .3
0.3
0.2 5
Probab ility
Probabilit y
0.25
0.2
0.15
0.1
0 .2
0.1 5
0 .1
0.0 5
0.05
0
0
1
2
3
.
.
.
m
1
2
color

q  qu u 1.. m
3
.
.
.
m
color
m
q
u
u 1
Сходство:
1
 
f  y   f  q , p  y  

p  y    pu  y u1..m
m
p
u
u 1
Будем сравнивать гистограммы опорной модели и положенийкандидатов на новом кадре
1
Слежение сдвигом среднего
Сходство:


f  y   f  p  y  , q 
f y
• Методы сопоставления шаблонов страдают от проблемы
негладкости целевой функции
• Небольшие смещения могут привести к резким скачкам ошибки
сопоставления
• Поэтому мы не можем использовать, например, метод
градиентного спуска для поиска оптимального положения
• Как мы решали эту проблему при сопоставлении точек?
• Mean-Shift – развитие идеи для сопровождения
Dorin Comaniciu, Visvanathan Ramesh, Peter Meer, Kernel-Based Object Tracking, PAMI 2003
Слежение сдвигом среднего


Сходство: f  y   f  p  y  , q 
Изотропное ядро:
f  y
• Покроем цель изотропным ядром. Веса на границе цели близки к
нулю
• Теперь небольшие смещения приводят к небольшим изменениям
ошибки сопоставления
• Ошибка сопоставления становится гладкой (по сдвигу от
оптимального положения
• Теперь мы можем не перебирать все положения в окрестности, а
воспользоваться методом градиентного спуска
Иллюстрация сдвига среднего
Для определенных ядер можно показать, что метод градиентного
спуска превращается в «сдвиг среднего» :
n
Взвешенная
сумма точек
xw
i
y1 
i 1
n
w
i 1
i
Расчёт весов
i
Слежение сдвигом среднего
Проблема :
Размер
цели
меняется
Размер (h)
ядра
должен
меняться
Решение:
Прогоняем
поиск 3 раза с
разными h
Выбираем h,
на котором
достигается
максимум
Пример работы
Адаптация на лету
•
•
•
Внешний вид объекта, фон и условия освещения могут меняться в
процессе слежения
Важное направление – адаптация алгоритма на лету к изменяющимся
условиям
Например, объект может становится лучше или хуже различим в
разных цветовых каналах
COLLINS, R. AND LIU, Y.. On-line selection of discriminative tracking features. ICCV 2003
Виды каналов
• Построим 49 признаков, как линейные комбинации
цветовых каналов:
Идея оценки каналов
• Мы оцениваем, насколько хорошо по каналу
отличается объект и фон.
• Отберём несколько наилучших каналов
• На следующих кадрах мы можем изменить каналы!
Примеры оценки каналов
Сравнение методов
Один фиксированный канал (MeanShift)
Выбор каналов на лету
Методы к рассмотрению
• Сопровождение одного объекта
• Сопоставление шаблонов
– Кросс-корелляция
– На основе карт краёв
• «Стая точек»
• Сдвиг среднего
• Адаптация на лету
• Сопровождение множества объектов
• Ассоциация обнаружений между кадрами
Выделение и ассоциация объектов
«Tracking by detection»
Шаг 1: выделение
объектов
• Вычитание фона
• Детекторы
объектов
Шаг 2: ассоциация
объектов
Обсуждение
• Смысл – распределить обнаружения между
траекториями (какие обнаружения соответствуют
какому объекту)
• Много разных ситуаций:





Появление нового объекта в поле зрения
Сопоставление объекту I
Пропадание объекта из поле зрения
Ложное обнаружение
Пропуск объекта (ошибка детектора)
Обсуждение
• Что лучше – «трекер» или «детектор»?
• Детектор – надежнее, медленнее
• Трекер – быстрее, ненадёжный
• Как часто можем применять детектор?
• Хотелось бы к каждому кадру
• На практике только к отдельным («ключевым») кадрам
• Выход – ищем компромисс между скоростью и
надежностью
• Трекер можно использовать для предсказания движения
объектов
Детерминированное слежение

Алгоритм установления соответствий между
объектами, найденными на соседних кадрах с учетом
ограничений

Детектирование – вычитание фона
Гипотезы сопоставлений – на основе любых признаков

Простейшая стратегия
Сопоставим ближайшее наблюдение следу
Простейшая стратегия в более сложных случаях не срабатывает,
поэтому исследовались разные ограничения
Примеры других ограничений
•
•
•
•
•
(а) близость
(b) максимальная скорость
(c) малое изменение вектора скорости
(d) общее движение
(e) «жесткость»
Алгоритмы ассоциации
Двухкадровые
Многокадровые
Подходы к установлению соответствий:
•
•
Перебор разных вариантов
Энергетическая (или статистическая) формулировка:
• Для каждого ограничения сформулируем «штраф»
• Составим функцию «энергии» сопоставления
• Будем оптимизировать энергию с помощью какого-нибудь
метода оптимизации
Пример работы
Пример современного алгоритма
B Benfold and I D Reid Stable Multi-Target Tracking in Real-Time
Surveillance Video. CVPR 2011
Резюме сопровождения объектов

Что рассмотрели:


Сопровождение одного объекта

Сопоставление шаблонов

Стая точек

Сдвиг среднего

Адаптация на лету
Сопровождение множества объектов

Сопровождение через сопоставление
1/--страниц
Пожаловаться на содержимое документа