Сегментация движущихся объектов в видеопотоке

Авторы:
Виктор Гаганов
Антон Конушин

Нахождение и отслеживание движущихся объектов в видеопотоке является важной задачей для таких приложений, как охранные системы, системы анализа потока машин на автомагистрали, smart room и т.д. Часто первым шагом к решению этих задач является выделение переднего плана. В данной статье будет рассмотрено несколько методов вычитания фона (background subtraction), применяемых для решения этой задачи.

Введение

Нахождение и отслеживание движущихся объектов в видеопотоке является важной задачей для таких приложений, как охранные системы, системы анализа потока машин на автомагистрали, smart room и т.д. Часто первым шагом к решению этих задач является выделение переднего плана. В данной статье будет рассмотрено несколько методов вычитания фона (background subtraction), применяемых для решения этой задачи. Методы вычитания фона - это методы, которые строят модель заднего плана сцены и на каждом кадре производят попиксельное сравнение текущего значения в каждом пикселе с моделью и в соответствии с результатами сравнения принимают решение, принадлежит пиксель к заднему плану или к переднему. Также в статье будут описаны основные проблемы, с которыми эти методы сталкиваются, и будут рассмотрены решения некоторых из них.

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

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

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

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

Рис 1. Пример сегментации кадра видеопоследовательности.

Простейший алгоритм и его проблемы

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

1) Сохраняем первое изображение видеопоследовательности. Обозначим его B.

2) Для каждого следующего кадра (обозначим текущий кадр C), w и h это ширина и высота картинки соответственно, то пиксель [i][j] считается переднеплановым, иначе он считается заднеплановым.

3) Для устранения шума к полученному бинарному изображению можно применить медианный фильтр или операции мат. морфологии.

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

Изменения заднего плана

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

Рис 2. Проблема изменения заднего плана. Сверху первый кадр последовательности. Обратите внимание на коробку на столе. Снизу кадр и результаты сегментации, после того, как коробку со стола убрали.

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

Изменение освещения

Изменения освещения практически полностью меняют цветовые характеристики сцены. В итоге из-за сильного изменения освещения алгоритм будет сегментировать в передний план большую часть сцены, что разумеется совершенно неприемлемо. Стоит разбить изменения освещения на 2 группы: быстрые (такие, например, как включение света в комнате) и медленные (например изменение освещения в течении дня). С медленными и быстрыми изменениями освещения можно бороться по разному.

Движущиеся тени

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

Динамический задний план

Изложенный алгоритм не в состоянии также справиться с проблемой динамического заднего плана. Запомнив первый кадр видеопоследовательности алгоритм в дальнейшем будет сегментировать такие <неинтересные> движения, как например движение листьев на дереве или движение воды в передний план.

Шум камеры

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

Алгоритмы, основанные на вероятностных моделях

Вышеперечисленные проблемы делают алгоритм с неадаптивным порогом практически неприемлемым на практике и теперь самое время перейти к более сложным алгоритмам, которые эти проблемы решают.

Нормальное распределение

Начнем с алгоритма использующего нормальное распределение. Опять будем считать, что с камеры поступают полутоновые изображения. Данный алгоритм моделирует каждый пиксель заднего плана с помощью одномерной нормально распределенной сл. величины т.е. Первые n кадров (когда камере виден только задний план) для каждого пикселя алгоритм производит оценку параметров модели используя аппарат мат. статистики а потом, после того как обучение закончено, попиксельно использует вероятностный порог для того, чтобы определить принадлежит ли значение пикселя заднему плану или переднему. Итак:

1) Обучение модели заднего плана по первым n кадрам. Для оценки параметров модели для каждого пикселя можно применять выборочное среднее и среднее квадратичное отклонение значений в данном пикселе - значения в пикселе по первым n кадрам.

2) Далее для каждого след. кадра и для каждого пикселя. Обозначим за с значение в текущем кадре для (i,j) пикселя.

3) Для устранения шума к полученному бинарному изображению можно применить медианный фильтр или операции мат. морфологии

Число a есть ни что иное как вероятность того, что отклонение вызванное шумом камеры попадет в указанную выше e-окрестность. Очень часто пользуются e = 3 (т.н. Mahalanobis distance) которому соответствует значение 0.98. Данный алгоритм решает проблему шума камеры т.к. имеет адаптивный вероятностный порог, но все остальные проблемы остаются в силе. Заметим, что данный алгоритм допускает реализации не только для полутоновых но и, например, для RGB изображений, что улучшает качество работы алгоритма. При реализации в RGB следует использовать 3х мерное нормальное распределение вместо одномерного и построить вероятностный порог для 3х мерной сл. величины.

Смесь нормальных распределений

Алгоритм создает попиксельную модель сцены используя смесь нормальных распределений и с поступлением каждого нового кадра обновляет модель и классифицирует каждый пиксель как принадлежащий к заднему или к переднему плану. Таким образом каждому слагаемому в сумме соответствует процесс в пикселе сцены, который характеризуется параметрами нормального распределения (мат. ожиданием и дисперсией) и коэффициентом, который называется весом и является показателем того, насколько часто данный процесс в данном пикселе попадал в поле зрения камеры. Параметр(максимальное кол-во гауссианов) выбирается в соответствии с ресурсами компьютера, обычно берут значения от 3 до 5. Используя и обучая такую модель можно создать алгоритм, который справляется практически со всеми перечисленными выше проблемами (кроме движущихся теней). Предлагаемый читателю алгоритм является модификацией стандартного алгоритма смеси нормальных распределений, о котором можно прочитать в [1]. Опять таки будем считать, что с камеры поступают полутоновые изображения. Итак:

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

2) Для каждого следующего кадра и для каждого пикселя:

1. Поиск процесса, которому удовлетворяет значение данного пикселя c. Для каждого процесса в модели применяется порог. Если текущее значение с для некоторого процесса удовлетворяет порогу то данный процесс помечается как текущий и переходим к пункту 3. Если порог не выполнился ни для одного процесса то переходим к пункту 2.

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

3. Обновление статистики текущего процесса. Оценки мат. ожидания и дисперсии обновляются с помощью низкочастотного фильтра рекурсивного сглаживания.

4. Обновление весов процессов.

5. Классификация пикселя. Алгоритм классификации очень прост: применение порога к весу текущего процесса. Если значение веса текущего процесса больше чем значение порога, то пиксель классифицируется как заднеплановый, иначе он классифицируется как переднеплановый. Порог следует выбирать из интервала.

Метод, используемый для классификации пикселей (пункт 2.5) очевидно допускает принадлежность к заднему плану сразу нескольких процессов. Именно по этом при наличии динамического заднего плана алгоритм через некоторое время адаптируется к его повторяющимся движениям. Более того, алгоритм способен адаптироваться к таким движениям сцены как дождь или снег. Также алгоритм способен адаптироваться к изменениям заднего плана т.к. через некоторое время после изменения вес созданного при изменении процесса превысит порог и он начнет сегментироваться в задний план. К медленным изменениям освещения алгоритм способен адаптироваться благодаря системе оценки параметров, т.к. по мере плавного изменения цвета пикселей заднего плана алгоритм будет переобучаться на новые значения. К быстрым изменениям освещения алгоритм адаптируется также, как он адаптируется к изменениям заднего плана.

Обнаружение теней

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

Рассмотрим некоторую точку сцена и пусть она имеет цвет, тогда после падения на эту точку тени она будет иметь цвет, где коэффициент определяет то, насколько упала освещенность в точке. Оказывается, что этого факта вполне достаточно, чтобы построить неплохую систему подавления теней. Алгоритм тенеподавления будет изложен для RGB реализации алгоритма с одним нормальным распределением, но по аналогии данную систему тенеподавления можно интегрировать в алгоритм с порогом и алгоритм с смесью нормальных распределений. Пусть цвет заднего плана в некотором пикселе (т.е. оценка мат. ожидания 3х мерной случайной величины, моделирующей задний план в данном пикселе) а текущее значение в этом пикселе. Сперва перейдем в цветовое пространство YUV. В YUV компонента Y определяет интенсивность а компоненты U,V определяют цветность. Таким образом при падении тени на объект значение Y должно серьезно уменьшится, а значения U,V практически не поменяются. Таким образом текшее значение в пикселе классифицируется как тень - значения порогов определяющие чувствительность системы тенеподавления. На рис. 4 показана пример работы системы обнаружения теней для RGB реализации алгоритма со смесью нормальных распределений. Стоит заметить что это не единственный метод подавления теней использующий их локальные свойства. В [3] можно прочитать про похожую систему, которая использует HSV вместо YUV.

Рис 4. Подавление теней. Тени отмечены серым цветом.

Литература

[1] Chris Stauffer, W. Eric L. Grimson "Learning Patterns of Activity Using Real-Time Tracking", 2000

[2] Omar Javed, Khurram Shafique, Mubarak Shah "A Hierarchical Approach to Robust Background Subtraction using Color and Gradient Information", 2002

[3] Andrea Prati, Ivana Miki?c, Costantino Grana and Mohan M. Trivedi "Shadow Detection Algorithms for Traffic Flow Analysis: a Comparative Study", 2002

[4] Dirk Focken, R. Stiefelhagen "Towards Vision-based 3-D People Tracking in a Smart Room", 2002

[5] Alexandre R.J. Francois and Gerard G. Medioni "Adaptive Color Background Modeling for Real-Time Segmentation of Video Streams", 2001