На правах рукописи

Шелабин Дмитрий Алексеевич

ПРОЕКТИРОВАНИЕ СИСТЕМЫ ОТСЛЕЖИВАНИЯ

И ПРОГНОЗИРОВАНИЯ ДВИЖЕНИЯ ОБЪЕКТОВ В ВИДЕОПОТОКЕ

05.13.18 – «Математическое моделирование, численные методы

и комплексы программ»

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Петрозаводск – 2013

Работа выполнена на кафедре технологии программирования факультета прикладной математики – процессов управления ФГБОУ ВПО «СанктПетербургский государственный университет»

Научный руководитель: кандидат физико-математических наук, доцент Сергеев Сергей Львович

Официальные оппоненты: доктор технических наук, профессор, заведующий кафедрой теории вероятностей и анализа данных Петрозаводского государственного университета Рогов Александр Александрович кандидат физико-математических наук, доцент, заместитель заведующего кафедрой управления государственными информационными системами Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики Пашкевич Василий Эрикович

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

Защита состоится «11» ноября 2013 г. в 16 часов 00 минут на заседании диссертационного совета Д 212.190.03, на базе ФГБОУ ВПО «Петрозаводский государственный университет» по адресу: 185910, Республика Карелия, г. Петрозаводск, просп. Ленина, 33.

С диссертацией можно ознакомиться в научной библиотеке Петрозаводского государственного университета.

Автореферат разослан « » октября 2013 года.

Ученый секретарь диссертационного совета Д 212.190.03 Воронов Р.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

Подобрать и модернизировать необходимые методы обработки изображений.

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

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

Произвести анализ и сравнение предложенных и существующих подходов.

Разработать архитектуру приложения для прототипа системы, реализовать эту архитектуру в приложении, исследовать работу прототипа.

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

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

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

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

Впервые используются модели адаптивного прогнозирования временных рядов при трассировке (построении траекторий).

Произведены разработка и описание архитектуры приложения прототипа системы. Созданное приложение оптимальным образом реализует описанные в работе методы таким образом, что их можно легко тестировать независимо друг от друга, используя различные наборы данных.

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

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

Достоверность научных результатов обусловлена применением общепринятых математических методов и подтверждается результатами экспериментов на ЭВМ, проведённых над созданным прототипом системы и над различными его модулями.

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы реализованы в прототипе системы отслеживания и прогнозирования движения объектов, созданного в рамках диссертационной работы. Прототип системы зарегистрирован в государственном реестре программ для ЭВМ. Результаты работы, использованы в качестве основы при планировании разработки и при проектировании программного обеспечения для автоматизированной системы мониторинга, разрабатываемой ООО «Envion Software».

Личный вклад. Все выносимые на защиту научные положения, методы и алгоритмы, а также разработка прототипа, содержащего внедренные теоретические положения работы, выполнена автором лично.

На защиту выносятся:

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

Метод классификации активных областей с учетом цветового распределения активных областей и с учетом скорости и положения классифицируемых активных областей.

Предлагаемый алгоритм трассировки движущихся объектов.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на 40 и 41 конференции студентов и аспирантов «Процессы управления и устойчивость», на семинаре кафедры технологии программирования факультета ПМ-ПУ и на семинаре в институте прикладных математических исследований Карельского научного центра РАН.

Публикации. По теме диссертации опубликовано 5 печатных работ, в том числе 2 – в издании, рекомендованном ВАК РФ.

Структура и объем диссертации. Диссертация состоит из введения, глав, заключения, списка литературы из 68 наименований. Работа изложена на 121 странице (основной текст занимает 115 страниц), содержит 32 рисунка и таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

На третьем этапе происходит отслеживание перемещений множества найденных связных областей на разных кадрах. Осуществляется объединение схожих по характеристикам областей на соседних по времени кадрах в один класс.

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

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

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

Значения пикселей изображений чаще всего описываются тремя цветовыми составляющими, т.е. изменения в пикселе фона можно описывать с помощью трёхмерной случайной величины. Этот случайный вектор можно задать с помощью трёхмерного нормального распределения. Опишем модификацию алгоритма, использующего смесь нормальных значений и строящего вероятностную модель снимаемой сцены. Подобные алгоритмы встречаются под названием MGM (Multiple Gaussian Model). Первыми алгоритм использующий смесь распределений предложили Stauffer C. и Grimson W. в работе «Learning patterns of activity using real-time tracking». Предложенный в упомянутой работе алгоритм имеет достаточно не плохие результаты среди других алгоритмов обнаружения движения, основанных на модели фона. Но так как в реальных условиях алгоритм должен устойчиво работать с видеопотоком, который может содержать множество ситуаций усложняющих обнаружение, то целесообразно произвести улучшение стандартного алгоритма предложенного Stauffer и Grimson. В предлагаемой модификации, в отличие от стандартного алгоритма, использованы многомерные нормальные распределения, вместо одномерных распределений, что позволяет более точно представлять цветовую информацию.

Также при адаптации модели используется ещё одно пороговое значение, что позволяет улучшить результат и увеличить стабильность работы алгоритма.

В начале работы алгоритма обнаружения выбираются начальный вектор средних значений и матрица ковариаций для первого распределения каждого пикселя моделируемого фона. Каждый пиксель моделируемого фона описывается несколькими «конкурирующими» распределениями, которые активируются в ходе работы алгоритма и постоянно обновляются. Каждому распределению приписывается вес, который тоже изменяется в ходе работы алгоритма. Модель фона или просто фон имеет такой же размер, что и кадры. Фон является динамическим, значение каждого пикселя фона совпадает с текущим значением вектора средних значений распределения с наибольшим весом. Модель фона строится таким образом, чтобы в неё не попадали движущиеся объекты. Пиксели поступающих кадров сравниваются с соответствующими пикселями в модели фона, и оцениваются как принадлежащие фону или принадлежащие движущемуся объекту. Этот алгоритм хорошо работает при изменяемом заднем плане и даже при наличии циклических движений на нём (например, дрожание листвы).

Также обнаружению движущихся объектов посвящены некоторые работы таких авторов как Абдулин Ю.Э., Лукьяница А.А., Шишкин А.Г., Гаганов В., Канушин А., Wren C. R., Azarbayejani A., Darrell T., Nascimento J., Marques J.S..

Каждый пиксель фонового кадра моделируется с использованием смеси распределений S, состоящей из k штук трёхмерных нормальных распределений:

S = N,. Каждое распределение описывается парой: вектором математических ожиданий (средних значений) 3x1 и матрицей ковариаций 3x3, которые задают нормальное распределение конкретной формы (далее просто – гауссиан). Также, каждой такой паре у каждого из пикселей, приписывается вес w [0,1], характеризующий частоту появлений пикселей, соответствующих распределению с номером p. Таким образом, пиксель фона может быть описан набором нормальных распределений с сопоставленными весами.

Нормальным распределениям соответствуют функции плотности:

ности трёхмерного нормального распределения с вектором математических ожиданий и матрицей ковариаций. В каждый момент времени пиксель кадра будет отнесен к фону, если его значение с достаточно большой вероятностью принадлежит хотя бы одному из k гауссианов с весом больше некоторого порога. Обозначим I (x, y) – цветовую составляющую R пикселя с координатами x, y кадра полученного на шаге t, I (x, y) = (I (x, y) I (x, y) I (x, y)) – вектор цветовых составляющих. Координаты пикселя x = 1, W, y = 1, H – два натуральных числа, где W – ширина, а H – высота кадра. Обозначим, (x, y),, (x, y), w, (x, y) – вектор средних значений, матрицу ковариаций и вес, соответственно, для гауссиана с номером p взятого в момент времени t для пикселя модели фона с координатами x, y. Время t – дискретное и ассоциировано с номером обрабатываемого кадра. Вначале происходит инициализация модели фона. Происходит инициализация первого гауссиана для всех пикселей фона:

Оставшиеся гауссианы активируются постепенно, по мере необходимости, поэтому для остальных гауссианов:, = 0, = 2,. Далее на каждом шаге работу алгоритма можно разделить на 2 этапа: классификация пикселей и обновление модели фона.

Классификация. Пиксель кадра с координатами x, y и интенсивностью I (x, y) на шаге t считается фоновым, если хотя бы для одного из гауссианов (например, с номером p) в модели фона выполняются соотношения:

где w (0,1), – порог, обычно 0.5. Первому соотношению в (1) будут удовлетворять значения I, задающие область трёхмерного пространства, лежащую внутри эллипсоида, заданного,,, и T. Если ни одно соотношение не выполняется, то пиксель считается переднеплановым, т.е. пикселем, принадлежащим движущемуся объекту. Таким образом, на выходе получается бинарная маска движения. Часто параметр T выбирается не меньше 3х. Смысл первого соотношения в (1) в том, что оно задаёт такие значения I, которые с достаточно большой вероятностью принадлежат трёхмерному нормальному распределению с параметрами, и,, эти значения образуют область трёхмерного пространства D, лежащую внутри эллипсоида. Вероятность того, что некоторый случайный вектор распределённый нормально по закону (, ) примет значения из D равна (, )( ) и будет стремится к 1 при возрастании T.

Обновление модели фона. Возможно несколько ситуаций. Первая ситуация.

Значение пикселя текущего кадра было отнесено хотя бы к одному гауссиану, и выполнялось:

Тогда просто происходит обновление весов гауссианов модели фона для этого пикселя. Этому неравенству будут соответствовать значения I, образующие область трёхмерного пространства, лежащую внутри эллипсоида заданного,,,,T. Если значение пикселя было отнесено к нескольким гауссианам для данного пикселя модели фона, то для обновления выбирается гауссиан с наибольшим весом w,. Веса обновляются по формуле (3.3).

Третья ситуация. Значение пикселя текущего кадра, не отнесено ни к одному гауссиану, т.е. не выполнялось ни (2), ни (4). Тогда если у данного пикселя модели фона ещё остались не инициализированные гауссианы (т.е. те у которых вес равен нулю), то инициализируется следующий гауссиан:

где p – номер следующего не активного гауссиана. Веса обновляются по формуле (3.3). Если у данного пикселя модели фона не осталось не инициализированных гауссианов, то производится переинициализация гауссиана с наименьшим весом w,. Используются (5) и (3.3). Выполняется переход к следующему кадру.

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

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

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

способа классификации активных областей с использованием их цветового распределения;

способа классификации активных областей использующего прогноз для траекторий и скорость/положение текущих активных областей;

алгоритма трассировки и алгоритма разметки траекторий.

Следует упомянуть работы Jorge P.M., Abrantes A.J., Marques J.S., Wren C.R., Darrell T., Pentland A.P., относящиеся к этой области. Как и большинство существующих подходов, используемых для трассировки движущихся объектов, описываемый подход предназначен для работы в режиме реального времени. Сама трассировка основывается на постепенном построении траекторий движения объектов. Каждая траектория соответствует классу активных (связных) областей. При построении оценивается вероятность того, что текущий объект (активная область) принадлежит к конкретному классу, существующему на данный момент. Для оценки вероятности используется байесовский подход. Описываемый способ трассировки основан на пошаговой классификации обнаруженных активных областей с использованием гистограммы цветового распределения областей и с использованием прогнозирования движения объектов. Использованный подход ориентирован на то что, в снимаемой сцене могут происходить слияния и разделения объектов, т.е. отдельные объекты могут сливаться в групповой объект, и наоборот. Может происходить перекрытие объектов объектами фона и множество других негативных явлений. Эти сложности приводят к тому, что простейшие способы трассировки плохо работают.

Пусть на момент времени t существует k классов активных областей {c (t)}. Время t представляется натуральным числом и совпадает с номером кадра. Каждому классу приписывается свойство называемое активностью. В процессе классификации участвуют только активные классы. Класс, помеченный как не активный, является завершенным и его состав и характеристики не изменяются, т.е. к нему не добавляются новые активные области. Изначально, при формировании, каждый класс является активным, но в ходе работы может быть помечен как не активный. Это происходит, если в течение некоторого отрезка времени в класс не добавляются новые активные области или появляется другая необходимость завершить этот класс. Подобное происходит в конфликтных ситуациях, когда невозможно принять однозначное решение об отнесении активной области в класс. Например, в моменты слияния или разделения движущихся объектов в снимаемой сцене. Пусть класс c (t) с номером i в момент времени t содержит l (t) активных областей.

Обозначим:

C(t) {c (t)} – множество всех классов в момент времени t, A(t) {a (t)} – множество всех активных классов в момент времени t, F(t) {f (t)} – множество всех не активных классов в момент времени t, где k(t) k (t) + k (t), C(t) A(t) F(t).

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

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

У активной области o,, j = 1, l (t), i = 1, k(t), добавленной в класс c, можно выделить следующие наиболее важные характеристики:

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

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

В свою очередь, у класса c (t) = o,, являющегося множеством активных областей, также можно ввести несколько важных характеристик. Среди них, например, траектория. Пусть Track (t) X o, – траектория объекта движения представленного классом c (t), т.е. множество векторов координат активных областей, принадлежащих классу c (t) на момент времени t, i = 1, k(t). Траектория Track (t) Track (j, t) представляет собой временной ряд.

Дополнительно у класса c (t) можно выделить несколько вспомогательных характеристик:

A(t, c ) {true, false} – активность класса.

S(c ) T(o, ) N – время старта траектории.

F(t, c ) T(o ( ), ) N – время завершения траектории.

Процедуру добавления активных областей в классы можно описать как перераспределение областей из множества Q(t) по классам областей из A(t).

Предположим, что в момент времени t 1 был сформирован набор классов A(t 1) {a (t 1)} и в момент времени t поступает набор активных областей Q(t) o, которые нужно распределить по этому набору классов. Класс представляет собой множество активных областей: a (t 1) будут распределены по классам A, считаем, что состояние множества классов A и каждого класса изменяется с t 1 на t. Для выполнения подобного распределения строится таблица релевантностей размерности r(t) k (t 1), в которой располагаются значения для выбранного функционала, оценивающего степень сходства класса и области: a (t 1), o, R, i = 1, k (t 1), p = 1, r(t). Этот функционал (с, o) (, 0) разбит на два слагаемых: (с, o) = (с, o) + (с, o). Здесь с – некоторый класс из C, o – некоторая активная область, – функционал оценивающий сходство класса и активной области на основе их цветового распределения, – функционал оценивающий сходство класса и активной области на основе положения области и на основе траектории класса. Чем больше значение, тем больше степень сходства. Выбору функционалов и посвящены два параграфа второй главы диссертации.

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

(i, p) вместо a (t 1), o,, a вместо a (t 1), o вместо o,. Значения (i, p) расположенные в таблице релевантностей формируют матрицу: T = { (i, p)},, в каждый момент времени.

Алгоритм классификации и распределения активных областей состоит из двух шагов, которые осуществляются в каждый момент времени после получения T. Выбираются два порога threshold (, 0) и threshold (0,1). Первый порог служит для фильтрации слишком малых значений, второй служит для выбора наиболее подходящих значений. Эти пороги выбираются опытным путем и не меняются в процессе работы системы. На первом шаге ищутся минимумы по строчкам и столбцам и формируются две матрицы, основанные на min { (i, p) }, threshold – минимум по строчке p. При этом, если в T для некоторого столбца i выполнялось: max < threshold, то в T и в T все элементы столбца i приравниваются к 1: p T, = 1, T, = 1|max < threshold.

Тем самым класс с номером i помечается как наименее соответствующий и исключается из текущего процесса классификации. Здесь max = max { (i, p) } – максимум по столбцу i. А если в T для некоторой строчки p выполнялось: max < threshold, то в T и T все элементы строчки p также приравниваются к 1: i T, = 1, T, = 1 max < threshold. Тем самым активная область p помечается как наименее соответствующая и исключается из текущего процесса классификации. Здесь max = max { (i, p) } – максимум по строчке p. В результате описанной процедуры будут получены две матрицы T и T, элементы которых будут находиться в интервале от 0 до 1.

Чем сильнее будет соответствовать класс данной активной области, тем ближе к 0 будет соответствующие значение в T. Чем сильнее соответствует активная область данному классу, тем ближе к 0 будет соответствующие значение в Tс.

На первом шаге в момент, когда происходит исключение строки p (т.е. когда соответствующие элементы строки приравниваются 1), то соответствующая область o, формирует новый активный класс. То есть область считается принадлежащей неизвестному классу, т.к. ей не соответствует ни один активный класс, и, следовательно, эта область должна инициировать создание нового класса (траектории). Если t текущий момент и o, – некоторая активная область, которая не была отнесена ни к одному классу, то она порождает (инициализирует) новый класс (траекторию): a = o,, k(t 1) <. Подобным образом могут порождаться несколько классов за раз, при наличии нескольких исключённых строк.

Когда происходит исключение столбца i (т.е. когда соответствующие элементы столбца приравниваются 1), то в соответствующий класс a (t 1) на данном этапе не добавляется активная область. Если в текущий момент t в активный класс a : A(t, a ) = true | t t 1 не добавляется активная область в течении d раз (моментов времени), то данный класс помечается как не активный (завершенный) и больше не участвует в дальнейшем процессе классификации и траектория завершается. То есть если для класса a выполняется t F(t, a ) d, где d – натуральное число, то A(t, a ) = false| t t. Так как класс c завершен, то он перемещается из подмножества A(t) множества C(t) в подмножество F(t) при t t. Этот класс больше не участвует в дальнейшем процессе классификации.

На втором шаге алгоритма происходит объединение T и T, применяется порог threshold и формируется окончательная матрица T :

Единицы в этой таблице будут расположены в строках и столбцах, которым соответствуют наиболее близкие друг другу активные области и классы.

Затем T просматривается поэлементно, ищутся и анализируются значения T, равные единице.

Если единичное значение T, стоит в строке p и в столбце i, где остальные элементы равны нулю, то между классом и областью o устанавливается однозначное соответствие. Если в текущий момент t активному классу a : A(t, a ) = true | t t однозначно соответствует некоторая активная область o,, то данная область классифицируется в этот класс. То есть область добавляется в класс a : a (t) = a (t 1), o,, o ( ), = o,, l (t) = l (t 1) + 1. Характеристики класса, прогнозы и все необходимые параметры обновляются. А так как единичное значение T, в строке p и в столбце i только одно, то больше в текущий момент времени область o, не может быть добавлена к другим классам, а в класс a больше не может быть добавлено других областей.

Если единичное значение T, стоит в строке p, где есть другие единичные значения в столбцах с номерами из множества = {i }, то активная область o, соответствует сразу нескольким классам. Такая ситуация при классификации соответствует “слиянию” движущихся объектов в снимаемой сцене. В результате активные классы, соответствующие столбцам с номерами из, завершаются, а активная область o, порождает (инициализирует) новый класс. При этом добавляются связи между старыми классами и новым классом. Фактически под добавлением связи понимается получение компьютером ссылки на один объект типа “класс областей” и передача этой ссылки другому объекту или другим объектам такого же типа. Это нужно для того, чтобы связывать траектории, относящиеся к одним объектам. Такая ситуация может происходить, например, когда в снимаемой сцене два движущихся объекта сближаются на столько, что в результате образуют одну слившуюся активную область в сцене, движение которой следует отслеживать как отдельную траекторию.

Если единичное значение T, стоит в столбце i, где есть другие единичные вует сразу несколько активных областей. Такая ситуация при классификации соответствует “разделению” движущихся объектов в снимаемой сцене. В результате активный класс a завершается, а активные области, соответствующие строкам с номерами из, порождают (инициализируют) новые классы. При этом добавляются связи между старым классом и новыми классами. Такая ситуация может происходить, например, когда в снимаемой сцене два движущихся слишком близко объекта отдаляются друг от друга настолько, что в результате образуют два движущихся объекта в снимаемой сцене. Движение этих объектов уже следует отслеживать раздельно.

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

Матрица T просматривается поэлементно, если встречается значение T, равное единице, то оно обрабатывается. Если и в строчке, и в столбце с этим элементом нет других единичных элементов, то это однозначное соответствие, которое обрабатывается так, как это было описано выше. Если же в строчке p и/или в столбце i с элементом T, присутствуют другие единичные элементы, то для этого элемента выполняется:

Активная область o,, соответствующая строчке p, порождает новый класс a = o,, k(t 1) <, если новый класс для этой области ещё не создавался (в текущий момент времени). Если этой областью уже был инициализирован новый класс, то он и используется.

Активный класс a (t 1), соответствующий столбцу i, завершается: A(t, a ) = false | t t. Если этот класс был уже завершён для предыдущего элемента таблицы, то ничего не происходит.

Добавляется связь между новым классом (траекторией) a и завершенным классом (траекторией) a (t 1).

Осуществляется переход к следующему единичному элементу матрицы T.

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

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

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

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

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

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

(a(t), o) ln P o, a (t) = ln P(o|a (t))P a (t), здесь P(o|a (t)) – вероятность появления активной области o в классе a (t), P a (t) – вероятность появления области из класса a. Для вычисления оценки P a (t) вероятности оценки вероятности P(o|a(t)) используется понятие временных рядов.

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

Выполняется сравнение прогнозируемых скоростей и вычисленных.

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

Пусть такое что: < и + 1 < ( ). Тогда, согласно введённым обозначениям, в общем случае (если координаты активных областей с индексами и Track [ ] = Track [ ], : < <. Аналогично происходит для временного ряда Velocity.

Следует оговорить начальное значение времени для класса (траектории).

Класс активных областей a формируется в момент времени (a ) (, ).

Поэтому нет смысла рассматривать < (a ) для Track [ ] и < (, ) для Velocity [ ]. В эти моменты времени класс можно считать пустым, т.е. можно доопределить временные ряды: Track [ ] =, < (a), Velocity [ ] =, < (, ). С учётом всего вышесказанного имеем:

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

Velocty [ + 1] = (1 )Velocty [ ] + Velocity [ ], Здесь (0,1) – это скорость адаптации, так же называемая, коэффициентом сглаживания, Velocty [ + 1] прогноз для значения скорости Velocity [ + 1], [ ] = Velocity [ ] Velocty [ ] – отклонение прогноза от истинного значения. Начальные значения для Velocty и [ ]:

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

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

Пусть в момент времени 1 были сделаны прогнозы для класса a для момента времени : Velocty [ ], [ ] и в момент времени поступило несколько активных областей, среди которых есть активная область. Чтобы оценить степень соответствия этой активной области классу a, считаем, что распределение вероятности значения скорости области класса, является:

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

В диссертационной работе получены следующие основные результаты:

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

Произведён анализ процесса адаптации модели фона в алгоритме обнаружения движения.

Обобщены и проанализированы методы для обработки изображений, которые должны использоваться в системе совместно с алгоритмами обнаружением движения.

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

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

Произведено описание архитектуры созданного приложения прототипа системы.

НАУЧНЫЕ РАБОТЫ, ОПУБЛИКОВАННЫЕ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Шелабин Д.А. Трассировка и прогнозирование перемещения движущихся объектов в видеопотоке // Современные проблемы науки и образования. – 2013. – №2;

URL: www.science-education.ru/108-9107 (дата обращения: 19.05.2013).

2. Шелабин Д.А. Классификация объектов движения с использованием байесовских сетей // Вестник Санкт-Петербургского государственного университета. Серия 10. Выпуск 1. Санкт-Петербург. 2012.

3. Шелабин Д.А., Сергеев С.Л. Процесс трассировки движущихся объектов в видеопотоке // Актуальные проблемы гуманитарных и естественных наук. Москва. – 2013. – № 7. – С. 71- 4. Шелабин Д.А., Севрюков С.Ю. Разработка прототипа системы обнаружения подвижных объектов в видео-потоках // Процессы управления и устойчивость: Труды 40-й научной конференции аспирантов и студентов / Под ред. Н.В. Смирнова, Г.Ш. Тамасяна. – СПб.: Изд-во СПбГУ, 2009. С. 536–541.

5. Шелабин Д.А. SGM алгоритм обнаружения объектов в видеопотоке // Процессы управления и устойчивость: Труды 41-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2010. С. 516–522.