Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,737

ТРАССИРОВКА И ПРОГНОЗИРОВАНИЕ ПЕРЕМЕЩЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ В ВИДЕОПОТОКЕ

Шелабин Д. А. 1
1 ФБГОУ ВПО «Санкт-Петербургский государственный университет», факультет прикладной математики – процессов управления
Статья посвящена трассировке передвижений объектов в видеопотоке. Трассировка заключается в от-слеживании перемещений на разных кадрах множества активных областей, в которых непосредственно происходит движение. Осуществляется объединение схожих по характеристикам областей на соседних по времени кадрах в один класс. В результате подобной операции происходит построение траекторий. При классификации активных областей используется оценка принадлежности активной области к траектории. Для получения этой оценки положение и скорость активных областей, составляющих некоторый класс, рассматриваются как временные ряды. Делается прогноз, благодаря которому на каждом шаге появляется возможность вычисления оценки вероятности того, что текущая активная область относится к данному классу. Оценки для активных областей получаются относительно прогноза для конкретного класса.
движущийся объект
трассировка
активная область
классификация
прогноз движения
временные ряды
модель Брауна.
1. Лукашин Ю. П. Адаптивные методы краткосрочного прогнозирования временных рядов. – М.: Финансы и статистика, 2003.
2. Мишулина О. А. Статистический анализ и обработка временных рядов. – М.: МИФИ, 2004. – С. 180.
3. Abrantes A. J., Marques J. S. J., Lemos M. Long term tracking using bayesian networks // Proc. of IEEE Int. Conf. on Image Processing. Rochester. pp. 609–612.
4. Grimson W. E. L., Stauffer C. Learning patterns of activity using real-time tracking // IEEE Trans. PAMI, Vol. 22(8), pp. 747-757, 2000.
5. Jorge P.M., Marques J.S., Abrantes A.J. On-line tracking groups of pedestrians with Bayesian networks. // Proc. Workshop on Performance Evaluation of Tracking and Surveillance, 2004.
6. Wren C. R., Azarbayejani A., Darrell T., Pentland A. P. Pfinder: Real-time tracking of the human body // IEEE Trans. Pattern Anal. Machine Intell., vol. 19, no. 7, July 1997, pp. 780-785.

Введение

Практически во всех системах отслеживания движущихся объектов можно выделить несколько этапов работы. Предполагается, что этот процесс происходит пошагово, в реальном времени при поступлении кадров видеопоследовательности. Вначале применяется алгоритм обнаружения движущихся объектов к кадрам видеопоследовательности, происходят фильтрация и объединение пикселей бинарной маски в отдельные активные области на кадре, где непосредственно происходит движение. Затем выполняется отслеживание перемещений множества найденных групп активных областей на разных кадрах и объединение их в траектории. Для этого используются алгоритмы трассировки. Все активные области, обнаруженные на текущем кадре видеопоследовательности, могут быть классифицированы как принадлежащие к одной из имеющихся к этому моменту траекторий движения объектов. Траектории в данном случае определяются набором областей, отнесённых к ним в ходе работы системы. Сами активные области могут быть классифицированы по многим параметрам: распределению цветов (цветовая гистограмма), по положению в кадре, по размеру области в кадре, по протяжённости области и по смещению области. В данной работе предлагается новый подход к оценке принадлежности активной области к траектории, основанный на использовании информации о положении и перемещении объекта совместно с прогнозом дальнейшего движения. Причем для получения этой оценки скорость активных областей, составляющих некоторый класс, рассматривается как временной ряд, для которого делается прогноз. Благодаря этому на каждом шаге появляется возможность вычисления оценки вероятности того, что данная активная область относится к данному классу относительно текущего прогноза для этого класса.

Построение траекторий

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

К области обнаружения и трассировки движущихся объектов относятся работы Jorge P. M., Abrantes A. J., Marques J. S., Wren C. R. [3–6]. Предлагаемый в работе способ трассировки основан на пошаговой классификации обнаруженных активных областей с использованием прогнозирования движения объектов. Пусть на момент времени существует классов активных областей . Время t представляется натуральным числом и совпадает с номером кадра. Каждому классу приписывается свойство, называемое активностью. В процессе классификации участвуют только активные классы. Класс, помеченный как не активный, является завершенным, и его состав и характеристики не изменяются, т.е. к нему не добавляются новые активные области. Изначально, при формировании, каждый класс является активным, но в ходе работы может быть помечен как не активный. По-сути, это свойство является булевой меткой: “активен” или “не активен”. Это происходит, если в течение некоторого отрезка времени в класс не добавляются новые активные области или появляется другая необходимость завершить этот класс. Подобное происходит в конфликтных ситуациях, когда невозможно принять однозначное решение об отнесении активной области в класс. Например, в моменты слияния или разделения движущихся объектов в снимаемой сцене. Обозначим количество областей в классе как . Другими словами, класс с номером в момент времени содержит активных областей. Обозначим:

– множество всех классов в момент времени ,

– множество всех активных классов в момент времени ,

– множество всех не активных классов в момент времени ,

, .

Класс – множество активных областей, где – активная область из класса с номером . Номер присваивается согласно порядку добавления области в класс. – множество активных областей обнаруженных в момент времени (на кадре с номером ), – количество областей обнаруженных в момент времени .

У активной области можно выделить такие характеристики, как, например, положение на кадре, размер и гистограмму цветового распределения. Все эти характеристики используются для классификации. Пусть – вектор координат области (положение центрального пикселя области на кадре).

У активной области , добавленной в класс , можно выделить следующие наиболее важные характеристики:

· – момент времени, в который область была обнаружена и добавлена в класс .

· – вектор скоростей области, полученный относительно предыдущей области класса.

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

· – активность класса.

· – время старта траектории.

· – время завершения траектории.

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

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

Прогноз движения и оценка принадлежности активной области к траектории

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

Функционал получим, прологарифмировав следующую вероятность:

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

и

.

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

Следует отметить важную особенность введённых обозначений. В некоторые моменты времени в активный класс может не добавляться ни одна область, т.е. могут не поступать новые данные. Поэтому количество активных областей в классе чаще всего значительно меньше . Пусть в момент времени в класс была добавлена активная область , и только в момент времени была добавлена активная область , т.е. и . Максимальное значение ограничено параметром . Пусть такое, что: и . Тогда, согласно введённым обозначениям, в общем случае (если координаты активных областей с индексами и разные): и , но при . Аналогично происходит для временного ряда .

Следует задать начальное значение времени для класса (траектории). Класс активных областей формируется в момент времени . Поэтому будем рассматривать для и для . В эти моменты времени класс можно считать пустым, т.е. можно доопределить временные ряды: , . С учётом всего вышесказанного имеем:

 (1)

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

 

 

  (2)

Здесь – это скорость адаптации, также называемая коэффициентом сглаживания, прогноз для значения скорости , – отклонение прогноза от истинного значения. Начальные значения для и :

 

 

 

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

Пусть в момент времени были сделаны прогнозы для класса для момента времени : , и в момент времени поступило несколько активных областей, среди которых есть активная область . Чтобы оценить степень соответствия этой активной области классу , считаем, что распределение вероятности значения скорости области класса является: – двумерное нормальное распределение. Также будем считать, что это значение скорости активной области класса задаёт некоторый случайный вектор . В качестве параметров этого распределения используются . Функция плотности двумерного нормального распределения обозначим как:

.

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

где .

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

В описанном случае, когда , модель Брауна работает достаточно хорошо. Также эту модель можно использовать и при , но только если не значительно больше единицы. Также для прогнозирования можно применять и другие модели, например, модель Хольта, которая уже способна учитывать линейный тренд.

Рецензенты:

Андрианов Сергей Николаевич, доктор физико-математических наук, профессор, заведующий кафедрой компьютерного моделирования и многопроцессорных систем факультета ПМ-ПУ СПбГУ, г. Санкт-Петербург.

Печников Андрей Анатольевич, доктор технических наук, доцент, ведущий научный сотрудник Института прикладных математических исследований Карельского научного центра Российской академии наук, г. Петрозаводск.


Библиографическая ссылка

Шелабин Д. А. ТРАССИРОВКА И ПРОГНОЗИРОВАНИЕ ПЕРЕМЕЩЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ В ВИДЕОПОТОКЕ // Современные проблемы науки и образования. – 2013. – № 2.;
URL: http://science-education.ru/ru/article/view?id=9107 (дата обращения: 25.08.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252