Маслий Р.В., Барченко К.В.

Винницкий национальный технический университет, Украина

Применение метода Монте-Карло для отслеживания объектов в видео последовательностях

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

Рассмотрим подход, использующий пространство состояний динамической системы.

Пусть – вектор состояния объекта в момент времени t, а это история состояний объекта до момента времени t. Пусть – вектор наблюдения в момент времени t, а – это история наблюдений до момента времени t.

Проблема отслеживания объектов в видео последовательностях, используя терминологию распознавания образов, заключается в оценке состояния объекта x_t в момент времени t, используя набор наблюдений y_t из последовательности видеокадров.

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

• : Функция плотности вероятности изменения состояния, которая описывает изменение состояния объекта во времени, от t-1 до t.

• : Функция плотности вероятности наблюдения, которая описывает условную вероятность наблюдения текущего состояния объекта.

• : Априорная вероятность состояния в момент времени t = 0.

Используя функции плотности вероятности изменения состояния и плотности вероятности наблюдения апостериорная плотность вероятности рекурсивно оценивается с помощью теоремы Байеса:

(1)

В формуле (1) все составляющие, или определены или могут быть вычислены с апостериорной вероятности на предыдущих временных шагах. Проблема заключается в том, что эти вычисления (в том числе интегральные) могут не иметь аналитического представления. Для практического решения проблемы отслеживания объектов при использовании рекурсивной Байесовской фильтрации может быть применен метод Монте-Карло [1-3].

В методе используется N образцов с соответствующими весами для аппроксимации апостериорной плотности вероятности . Каждый образец состоит из вектора состояния x и веса w. При этом , а Набор является взвешенным набором образцов, представляющих апостериорную плотность в момент времени t, и оцениваются рекурсивно из набора .

Метод Монте-Карло последовательно генерирует из используя следующие четыре этапа:

Этап 1. Так как невозможно прямо отобрать образцы с апостериорной плотности, используется специальное распределение для аппроксимации апостериорной плотности . Основываясь на распределении метод Монте-Карло случайным образом, независимо от других образцов, выбирает i-й образец с для (i = 1,2, ..., N) и вычисляет его вес , используя формулу:

. (2)

Этап 2. Затем осуществляется нормализация весов:

, (3)

где i =1, 2,…, N.

Этап 3. Таким образом, апостериорная плотность может быть аппроксимирована как:

, (4)

где – дельта функция Дирака с центром в .

Этап 4. Оценка функции f(x_t) вектора состояния может быть вычислена как:

(5)

Последовательность операций в алгоритме, описанном выше, выполняется для получения апостериорной плотности на каждом временном интервале. Основной проблемой этого алгоритма является то, что после нескольких временных интервалов все значения весов, за исключением нескольких, будут стремиться к нулю. Эти веса будут оставаться равными нулю для всех последующих интервалов времени, и не будут вносить вклад в оценку . Такая деградация весов является нежелательной, так как приводит к пустой трате вычислительных ресурсов. Этой деградации можно избежать при введении этапа выбора, в котором осуществлять копирование образцов с большими весами и удаление образцов с малыми весами. Самый популярный способ для реализации этапа выбора [2] отбирает N образцов из набора с вероятностями пропорциональными весам для получения нового набора N образцов . На следующей итерации используется этот новый набор .

Решающее значение для производительности Байесовской фильтрации, является выбор функции . В идеале, эта функция должна быть наиболее близкой к функции апостериорной плотности.

Популярным решением этой проблемы является использование функции плотности вероятности изменения состояния в качестве функции . В этом случае значения весов задаются как:

(6)

Другие варианты включают в себя использование разумно построений приближений к апостериорной плотности [4].

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

Литература

1. B. Ristic Beyond the Kalman filter: Particle filters for tracking applications / B. Ristic, S. Arulampalam, N. Gordon // Artech House. – 2004.

2. N. Gordon “Novel approach to non-linear/non-Gaussian Bayesian state estimation / N.Gordon, D.Salmon, and A.Smith // Proc. Inst. Elect. Eng. F, Radar Signal Process., vol.140. – 1993. – pp.107–113

3. M. Isard CONDENSATION – Conditional Density Propagation for Visual Tracking / M. Isard, A. Blake // Intl. Journal of Computer Vision, Vol. 29. No. 1. – 1998. – pp. 5–28.

4. A. Doucet “On sequential simulation-based methods for Bayesian filtering”/ A. Doucet // Tech. Rep., Dept. Eng., Univ.Cambridge,Cambridge, U.K. – 1998.