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

¡МША

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

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

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

05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

Автореферат

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

1 7 ОКТ 2013

005534906

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

005534906

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

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

доцент

Сергеев Сергей Львович

Официальные оппоненты: доктор технических наук, профессор,

заведующий кафедрой теории вероятностей и анализа данных Петрозаводского государственного университета Рогов Александр Александрович

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

Пашкевич Василий Эрикович

Ведущая организация: Институт прикладных математических

исследований Карельского научного центра РАН

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

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

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

Ученый секретарь

диссертационного совета Д 212.190.03 ронов Р.В.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В начале работы алгоритма обнаружения выбираются начальный вектор средних значений и матрица ковариаций для первого распределения каждого пикселя моделируемого фона. Каждый пиксель моделируемого фона описывается несколькими «конкурирующими» распределениями, которые активируются в ходе работы алгоритма и постоянно обновляются. Каждому распределению приписывается вес, который тоже изменяется в ходе работы алгоритма. Модель фона или просто фон имеет такой же размер, что и кадры. Фон является динамическим, значение каждого пикселя фона совпадает с текущим значением вектора средних значений распределения с наибольшим весом. Модель фона строится таким образом, чтобы в неё не попадали движущиеся объекты. Пиксели поступающих кадров сравниваются с соответствующими пикселями в модели фона, и оцениваются как принадлежащие фону или принадлежащие движущемуся объекту. Этот алгоритм хорошо работает при изменяемом заднем плане и даже при наличии циклических движений на нём (например, дрожание листвы). Также обнаружению движущихся объектов посвящены некоторые работы таких авторов как Абдулин Ю.Э., Лукьяница A.A., Шишкин А.Г., Гаганов В., Ка-нушин A., Wren С. R., Azarbayejani A., Darrell Т., Nascimento J., Marques J.S..

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

S = {N(|ip,Zp)} Каждое распределение описывается парой: вектором математических ожиданий (средних значений) Цр 3x1 и матрицей ковариаций Ер 3x3, которые задают нормальное распределение конкретной формы (далее просто - гауссиан). Также, каждой такой паре у каждого из пикселей, приписывается вес wp е [ОД], характеризующий частоту появлений пикселей, соответствующих распределению с номером р. Таким образом, пиксель фона может быть описан набором нормальных распределений с сопоставленными весами. Нормальным распределениям соответствуют функции плотности: С -»к г (х-ц)т£~'(х-Ю

[/n(,p.ip)|p=1 > где /n(h,q(X) = 7Щ!Ще г ,х е R3 - функция плотности трёхмерного нормального распределения с вектором математических ожиданий цр и матрицей ковариаций Ер. В каждый момент времени пиксель кадра будет отнесен к фону, если его значение с достаточно большой вероятностью принадлежит хотя бы одному из к гауссианов с весом больше некоторого порога. Обозначим lf(x,y) - цветовую составляющую R пикселя с координатами х, у кадра полученного на шаге t, It(x,y) = 0t4x,y) if (х, у) if (х, у))т -вектор цветовых составляющих. Координаты пикселя х = 1, W, у = 1, H — два натуральных числа, где W - ширина, а H - высота кадра. Обозначим (it p(x, у), Xtp(x,y), wt p(x,y) - вектор средних значений, матрицу ковариаций и вес, соответственно, для гауссиана с номером р взятого в момент времени t для пикселя модели фона с координатами х, у. Время t - дискретное и ассоциировано с номером обрабатываемого кадра. Вначале происходит инициализация мо-

дели фона. Происходит инициализация первого гауссиана для всех пикселей фона:

/°i,i 0 0 \

W1.1(x,y) = l, n1.1(x,y) = (I1R(x,y) if'Cx.y) lf(x,y))T , £1Д(х,у) = о а2.2 0 .

V 0 0 а3,з/

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

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

( It(x.y) - 1ЧР(х,у)) St,p(x,y)_1 ( It(x,y) - Ht,p<Xy)) < Th2ight,wt,p > w6, (1)

где Wg 6 (0,1), - порог, обычно 0.5. Первому соотношению в (1) будут удовлетворять значения It, задающие область трёхмерного пространства, лежащую внутри эллипсоида, заданного ntiP, Et p и Thlgtlt. Если ни одно соотношение не выполняется, то пиксель считается переднеплановым, т.е. пикселем, принадлежащим движущемуся объекту. Таким образом, на выходе получается бинарная маска движения. Часто параметр T^ight выбирается не меньше Зх. Смысл первого соотношения в (1) в том, что оно задаёт такие значения It, которые с достаточно большой вероятностью принадлежат трёхмерному нормальному распределению с параметрами pt р и Et р, эти значения образуют область трёхмерного пространства D, лежащую внутри эллипсоида. Вероятность того, что некоторый случайный вектор распределённый нормально по закону примет значе-

ния из D равна ///0 În(jiX)0Q и будет стремится к 1 при возрастании Thight.

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

T,ow ^ ( It(x,y) - Ht,p(x,y))TStp(x,y)-1 ( It(x,y) - Ht,p(x,y)) < Th2ight, (2) где TIow < Thjght - параметры (например, 1 и 3). Тогда происходит обновление модели фона для этого пикселя. Двойному неравенству (2) будут соответствовать значения It, образующие область трёхмерного пространства, лежащую внутри эллипсоида заданного |itp, Stp ,Thight и снаружи эллипсоида заданного |it piEt p,T]oW. В этой ситуации обновляется вектор математических ожиданий и ковариационная матрица того гауссиана, к которому было отнесено значение пикселя. Если значение пикселя было отнесено к нескольким гауссианам для данного пикселя модели фона (т.е. (2) выполнялось для нескольких р при фиксированных х, у и t), то для обновления выбирается гауссиан с наибольшим весом wt р. Также обновляются веса всех гауссианов соответствующих этому пикселю.

Обновление происходит по формулам:

Ш+1.р(х.У) = С1 - У1)(ЧР(х.У) + УЛ(х,у) , (3.1)

24+1,р(х,у) = (1 - у2)24,р(х,у) + у2 ( 1с(х,у) -^р(х,у)) ( 1((х,у) - цЬр(х,у))Т, (3.2)

Wt+l,i(x, у) = (1 - Уз)™и(х,у) + УзМ(Р. 0,1 = !7к, (3.3)

где у±, у2, Уз 6 [ОД] - скорости адаптации, р - номер гауссиана, к которому

был отнесен пиксель, МО, р) = р ^ | •

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

Т,2ош > (их,у) - ^р(х,у))\р(х,уГ1(1[(х,у) - ЦГр(х,у)). (4)

Тогда просто происходит обновление весов гауссианов модели фона для этого пикселя. Этому неравенству будут соответствовать значения I,., образующие область трёхмерного пространства, лежащую внутри эллипсоида заданного Ц[р, Если значение пикселя было отнесено к нескольким гауссианам

для данного пикселя модели фона, то для обновления выбирается гауссиан с наибольшим весом ш£р. Веса обновляются по формуле (3.3).

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

/ ст1д 0 0 \

\У,р(х,у) = 0, ц,р(х,у) = (1[К(х,у) 1?(х,у) 1'3(х,у))т,Е,р(х,у) = ( 0 а2,2 0 1, (5)

V 0 0 °з.з/

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

Описанная модификация алгоритма работает лучше, так как при адаптации модели используется ещё одно пороговое значение Т|о1У, что позволяет улучшить результат и увеличить стабильность работы алгоритма. Следует описать, за счёт чего это происходит. В процессе работы, вектора средних значений и матрицы ковариаций адаптируются к изменениям в фоне. Если изменения значений пикселя фона колеблются около некоторого значения, то элементы вектора средних значений и матрицы ковариации "стабилизируются" около некоторых значений. Параметр Тыеы задаёт область, попадая в которую значение пикселя считается принадлежащим нормальному распределению (с текущим вектором средних значений и матрицей ковариации). Параметр Т]0ДЛГ задаёт более узкую область внутри первой. Если значение пикселя попадает в неё, то он считается в наибольшей степени характерным для данного распределения, т.е. не несущим новой информации. И поэтому значение такого пикселя не используется для обновления вектора средних значений и матрицы ковариаций для соответствующего пикселя моделируемого фона. Это делается для того чтобы матрица ковариации не изменялась настолько, что бы область задаваемая Т^ы

получилась слишком "узкой". Это бы привело к тому, что незначительные скачки интенсивности света в фоне привели к большим искажениям.

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

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

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

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

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

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

движущихся объектов в снимаемой сцене. Пусть класс q(t) с номером і в момент времени t содержит 1с. (t) активных областей.

Обозначим:

C(t) = {Ci(t)}^ - множество всех классов в момент времени t, A(t) = {ai(t)}^t'> - множество всех активных классов в момент времени t, F(t) éz {fiCt)}^^ - множество всех не активных классов в момент времени t, где k(t) £ ki(t) + k2(t), cet) ZÊ: A(t) U F(t).

Юіасс CjСО =: {o^fc® - множество активных областей, где OjC. - активная область из класса Сі с номером]. Номері присваивается согласно порядку добавления области в класс. Q(t) êz {орд}^ - множество активных областей

обнаруженных в момент времени t (на кадре с номером t), r(t) - количество областей обнаруженных в момент времени t.

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

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

• T(oj с.) Є N - момент времени, в который область была обнаружена и добавлена в класс с,.

• V(ojc.) = Х(°' е')~Х(0'~1<:') є R2, j = 2, lc,(t), і = 1, k(t) - вектор скоростей области, полученный относительно предыдущей области класса.

.. r -iir-OO

В свою очередь, у класса q(t) = (Oj Cj, являющегося множеством активных областей, также можно ввести несколько важных характеристик. Среди них, например, траектория. Пусть TrackCj(t) = {x(oj c.)}.^i - траектория объекта движения представленного классом q(t), т.е. множество векторов координат активных областей, принадлежащих классу q(t) на момент времени t,

і = 1, k(t). Траектория Trackc.(t) = {Trackc. (j, t)}^'® представляет собой временной ряд.

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

• A(t, Cj) Є {true, false} - активность класса.

• S(q) = T(o1>c.) Є N - время старта траектории.

• F(t, Cj) = T(oic (t) с,) Є N - время завершения траектории.

Процедуру добавления активных областей в классы можно описать как перераспределение областей из множества Q(t) по классам областей из A(t). Предположим, что в момент времени t — 1 был сформирован набор классов A(t — 1) = {aj(t — l)}f^t_1) и в момент времени t поступает набор активных

областей Q(t) éz {o^}™, которые нужно распределить по этому набору классов. Класс представляет собой множество активных областей: a¡(t— 1) А {oj>a.}'^t = 1,kt(t — 1). После того, как активные области из множества Q

будут распределены по классам А, считаем, что состояние множества классов А и каждого класса изменяется с t — 1 на t. Для выполнения подобного распределения строится таблица релевантностей размерности r(t) xk^t- 1), в которой располагаются значения для выбранного функционала, оценивающего степень сходства класса и области: p(a¡(t — 1), ор t) £ R, i = l,ki(t — 1),р = l,r(t). Этот функционал р(с*, ô) е (—оо, 0) разбит на два слагаемых: р(с*, о) = Pi (с*, ô) + р2(с*, о). Здесь с* - некоторый класс из С, ô - некоторая активная область, р! - функционал оценивающий сходство класса и активной области на основе их цветового распределения, р2 - функционал оценивающий сходство класса и активной области на основе положения области и на основе траектории класса. Чем больше значение р, тем больше степень сходства. Выбору функционалов р1 и р2 посвящены два параграфа второй главы диссертации. Максимизируя значение функционала р по его аргументам, можно решать задачу классификации и принимать решение о добавлении активной области в тот или иной класс. В результате классификации будут строиться траектории, соответствующие классам активных областей. Для краткости, будем писать: Pt(i,р) вместо p(a¡(t— l),Opit), a¡ вместо a¡(t— 1), ор вместо opt. Значения pt(i, р) расположенные в таблице релевантностей формируют матрицу: Т = Ípt0»p)}fp=i в каждый момент времени.

Алгоритм классификации и распределения активных областей состоит из двух шагов, которые осуществляются в каждый момент времени после получения Т. Выбираются два порога threshold! G (—со, 0) и threshold2 £ (ОД). Первый порог служит для фильтрации слишком малых значений, второй служит для выбора наиболее подходящих значений. Эти пороги выбираются опытным путем и не меняются в процессе работы системы. На первом шаге ищутся минимумы по строчкам и столбцам и формируются две матрицы, основанные на Т:

Тс = {Тр^^р^ = {ptap)/mini í^:,, T^ÎTp^^fptO-rt/minpÇ^,

где min¡ = min({pt(i,p) }p=1 .thresholdi) - минимум по столбцу i, minp = min({pt(i,p) iJ^j, threshold!) - минимум по строчке р. При этом, если в Т для некоторого столбца i выполнялось: max¡ < threshold!, то в Тс и в Тг все элементы столбца i приравниваются к 1: VpTpi = 1, Tp¡ = l|max¡ < threshold!. Тем самым класс с номером i помечается как наименее соответствующий и исключается из текущего процесса классификации. Здесь maxj = max({pt(i,p) }p=i) - максимум по столбцу i. А если в Т для некоторой строчки р выполнялось: maxp < threshold-^ то в Тг и Тс все элементы строчки

р также приравниваются к 1: Vi Tpi = 1,Трд = l|maxp < threshold!. Тем самым активная область р помечается как наименее соответствующая и исключается из текущего процесса классификации. Здесь maxp = max({pt(i, р) ifijJ - максимум по строчке р. В результате описанной процедуры будут получены две матрицы Тс и Тг, элементы которых будут находиться в интервале от 0 до 1. Чем сильнее будет соответствовать класс данной активной области, тем ближе к 0 будет соответствующие значение в Тг. Чем сильнее соответствует активная область данному классу, тем ближе к 0 будет соответствующие значение в Тс.

На первом шаге в момент, когда происходит исключение строки р (т.е. когда соответствующие элементы строки приравниваются 1), то соответствующая область Орд формирует новый активный класс. То есть область считается принадлежащей неизвестному классу, т.к. ей не соответствует ни один активный класс, и, следовательно, эта область должна инициировать создание нового класса (траектории). Если t текущий момент и ор t - некоторая активная область, которая не была отнесена ни к одному классу, то она порождает (инициализирует) новый класс (траекторию): aq = {op t}, k(t— 1) < q. Подобным образом могут порождаться несколько классов за раз, при наличии нескольких исключённых строк.

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

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

lkl,r тр = [1. (Tpc,i + Tp i)/2 < threshold,, РД Ь - (Tpc,i + Tp i)/2 > thresholds

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

Если единичное значение Трл стоит в строке р и в столбце i, где остальные элементы равны нулю, то между классом и областью ор устанавливается однозначное соответствие. Если в текущий момент t активному классу a;: A(t, а;) = true 11 < t однозначно соответствует некоторая активная область ор t, то данная область классифицируется в этот класс. То есть область добавляется в класс а^ at(t) = {a^t - 1),орД}, о,а.а) а. = opt, ЦОО = laj(t- 1) + 1. Характе-

-та;

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

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

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

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

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

•Активная область орЬ соответствующая строчке р, порождает новый класс ач = {°рд}> — 1) < <7, если новый класс для этой области ещё не создавал-

15

ся (в текущий момент времени). Если этой областью уже был инициализирован новый класс, то он и используется. •Активный класс a;(t — 1), соответствующий столбцу i, завершается: A(t,а;) = false 11 > t. Если этот класс был уже завершён для предыдущего элемента таблицы, то ничего не происходит. •Добавляется связь между новым классом (траекторией) aq и завершенным классом (траекторией) aj(t — 1). Осуществляется переход к следующему единичному элементу матрицы TF.

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

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

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

16

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

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

Функционал р2 получается логарифмированием вероятности: р2(а*(0,б) = 1пР(о, а*00) = 1пР(о|а*00)Р(а*(0) > здесь Р(о|а*(0) - вероятность появления активной области о в классе а*(0> Р(а*(^) - вероятность появления области из класса а*. Для вычисления оценки Р(а1(0) вероятности

Р(а|00) можно использовать формулу: Рс(а;*С0) = ГкТвд"^—■ Для получения

£¡=1 Цм

оценки вероятности Р(о|а*(1:)) используется понятие временных рядов.

Положение и скорость активных областей, составляющих класс а* (0 = г Л* (О

1°),а" | _1 > можно рассматриваются как временные ряды

Тгаска.(0 ± {Тгаска.0-,О};-« а (Х^^.)}^ и

Уе1оа1уа.(1) £ [УеЮсПу.-О.^Й0 - Мо,*.)}^-

Затем делается прогноз на следующий шаг или несколько шагов. Дополнительно оценивая ошибку прогноза, представляемую дисперсией или ковариационной матрицей, которая также считается временным рядом. Благодаря этому на каждом шаге появляется возможность вычисления вероятности отнесения активной области к данному классу относительно текущего прогноза для класса. Обозначим последние значения (отсчёты) временных рядов как Тгаска- = Тгаска'Оа'СО.Ои Уе1осйуа-М = Уе1оа1уа«(/а>(г), С), соответственно. Для каждой обнаруженной области вычисляются скорости относительно всех классов. Выполняется сравнение прогнозируемых скоростей и вычисленных.

Следует отметить важную особенность введённых обозначений. В некоторые моменты времени в активный класс может не добавляться ни одна область, т.е. могут не поступать новые данные. Поэтому количество активных областей в классе а*: 1а' (В) чаще всего значительно меньше С. Пусть в момент времени в класс а* была добавлена активная область Оуа-, и только в момент времени Ь2 = ^ + г,г Е {1,2,...} была добавлена активная область о;+1а*, т.е. Т(о; а-) =

ti и T(oJ+l a-) = t2 . Максимальное значение z ограничено параметром d . Пусть t такое что: t2 < t и j + 1 < la-(t)- Тогда, согласно введённым обозначениям, в общем случае (если координаты активных областей с индексами j и j + 1 разные): Tracka-(y, t) Ф Tracka- 0' + 1,0 и Tracka.[tx] * Tracka-[t2], но Tracka.[ti] = Tracka.[t3], Vt3: tx < t3 < t2 . Аналогично происходит для временного ряда Velocity.

Следует оговорить начальное значение времени для класса (траектории). Класс активных областей а* формируется в момент времени S(a*) = Т(о1а-). Поэтому нет смысла рассматривать t < 5(а*) для Tracka-[t] и t < T{o2i3*) для Velocitya-[t], В эти моменты времени класс можно считать пустым, т.е. можно доопределить временные ряды: Tracka-[t] = О, t < S(a*), Velocitya* [t] = О, t < Т(о2 а«). С учётом всего вышесказанного имеем: Tracka-М = X(oia,(t)>a.), t > Т(о1Х),

Velocity a- [t] = V(oi (t),a.J = —-г-—-г, t > Г(о2,а.).

4°la-(tU') - r(oia.(t)_lia.)

Рассмотрим простой случай: d = 1 для временного ряда Velocitya< [t] = -^(°ia.(t),a') — -^(°ia.(t)-i,a')> строящегося по классу а*. (Последнее равенство следует из (6) с учётом того что при d = 1 выполняется 7,(o(a,(t)a-) — Г(о;а,(1)_1а.) = 1) Прогноз Velocitya<[t + 1] для значения Velocityа* [t + 1] будет строиться на основе известных отсчётов на момент времени t : Velocitya- [t], Т(о2а-) < i <t. Для построения прогноза будет использована модель Брауна, основанная на экспоненциальном скользящем среднем. Это довольно простая модель, которая годится для данного случая. Главные недостатки модели Брауна в том, что она, во-первых, работает на небольшом горизонте прогнозирования, т.е. прогноз, сделанный в момент времени t, будет относительно точен только для моментов времени t + d, где d мало. И, во-вторых, модель Брауна не учитывает тренд. Параллельно будет строиться прогноз для матрицы ковариации, т.е. по-сути будут фиксироваться отклонения прогноза Velocitya* [t + 1] от самого значения Velocityа* [t + 1]. А так как Velocity это вектор координат х и у, то это отклонение фиксируется не в виде дисперсии, а в виде матрицы ковариации. Таким образом, для модели Брауна имеем: Velocitya-[t + 1] = (1 - y)Velocitya.[t] + yVelocitya<[i], Еа. [t + 1] = (1 - у)Еа- [t] + у£а- [t]T£a- [t], (7)

t > T(0l,a.)-

Здесь у £ (0,1) — это скорость адаптации, так же называемая, коэффициентом сглаживания, Velocitya. [t + 1] прогноз для значения скорости Velocitya.[t + 1], £a*[t] = Velocitya-[t] — Velocitya* [t] - отклонение прогноза от истинного значения. Начальные значения для Velocityа> и 2а- [t]:

v rtl_/(2wi)2 0 \

t = ГК aO + !•

Здесь Wi и hi размеры области о1а-. Таким образом, для каждого момента времени t > Т(о2 а-) будет строиться прогноз скорости и возможной ошибки: Velocityas Еа» для следующего момента времени t + 1. Эти значения, с другой стороны, представляют собой вектор средних значений и матрицу ковариации для некоторого распределения значения скорости активной области принадлежащей классу а*. На каждом шаге это распределение будет менять свои параметры из-за обновления прогнозов и поступления новых данных. Для получения степени соответствия новой активной области со сделанным прогнозом, предполагается, что параметры распределения Velocityа», £а> являются параметрами двумерного нормального распределения.

Пусть в момент времени t — 1 были сделаны прогнозы для класса а* для момента времени t: Velocitya- [t], Sa- [t] и в момент времени t поступило несколько активных областей, среди которых есть активная область о*. Чтобы оценить степень соответствия этой активной области о* классу а*, считаем, что распределение вероятности значения скорости области класса, является: N2 (Velocityа', Еа<) - двумерное нормальное распределение. Так же будем считать, что это значение скорости активной области класса а* задаёт некоторый случайный вектор V. В качестве параметров этого распределения используются Velocity а<,Еа> . Функция плотности двумерного нормального распределения М2 (Velocitya',Ea-) обозначим как:

1 (y-VelocIt)0TZ~1(V-Velocity)

* , V е R2.

Под вероятностью P(V = V*) того, что случайный вектор V примет значение V* будем понимать вероятность попадания случайного вектора в квадрат с центром в точке V* и с длиной ребра равной S. Значения координат и, следовательно, скоростей, фактически являются координатами пикселей кадра, т.е. целыми числами, поэтому 5=1. На практике, удобно высчитывать приближённую вероятность как: P(V = V*) = S2 • fNг (Veloclty £)(V*) « P(V = V*). Это упрощение позволяет избежать вычисления интеграла по квадрату. Таким образом, приближённое значение вероятности того, что область б принадлежит классу а*, может быть оценено как: P(o|a*(t - 1)) « /Н2 (velocity,.[t],za.[t])(V(°))'

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

1. Шелабин Д.А. Трассировка и прогнозирование перемещения движущихся объектов в видеопотоке // Современные проблемы науки и образования. — 2013. — №2; URL: www.science-education.ru/108-9107 (дата обращения: 19.05.2013).

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

3. Шелабин Д.А., Сергеев C.JI. Процесс трассировки движущихся объектов в видеопотоке // Актуальные проблемы гуманитарных и естественных наук. Москва. -2013.-№7.-С. 71-77

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

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

Подписано в печать 26.09.13 Формат 60х84'/16 Цифровая Печ. л. 1.0 _Тираж 120_Заказ 19/09_печать_

Отпечатано в типографии «Фалкон Принт» (197101, г. Санкт-Петербург, ул. Большая Пушкарская, д. 54, офис 2)

Санкт-Петербургский государственный университет Факультет прикладной математики - процессов управления Кафедра технологии программирования

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

04201363308

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

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

Специальность

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

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

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

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

Санкт-Петербург - 2013

Оглавление

Введение.......................................................................................................................3

Актуальность, новизна и цели работы...................................................................3

Общая архитектура...................................................................................................6

Глава 1. Обнаружение движения в видео потоке..............................................10

§1.1 Обзор существующих подходов...................................................................10

§1.2 Алгоритм на основе смеси нормальных распределений............................13

§1.2.1 Простая вероятностная модель фона снимаемой сцены......................13

§ 1.2.2 МвМ-алгоритм.........................................................................................20

§ 1.3 Адаптация и прогнозирование параметров модели фона..........................27

§1.4 Пространственная обработка, переход к связным областям.....................33

§1.4.1 Фильтрация...............................................................................................34

§ 1.4.2 Связные области.......................................................................................44

Глава 2. Трассировка движущихся объектов....................................................48

§2.1 Обзор существующих подходов...................................................................48

§2.2 Классификация связных областей, классы областей и построение траекторий...............................................................................................................50

§2.2.1 Сравнение областей связности и классов по гистограмме цветового распределения......................................................................................................55

§2.2.2 Сравнение областей связности и классов по положению и скорости, прогнозирование движения................................................................................70

§2.2.3 Распределение областей по классам, процесс классификации............80

Глава 3. Прототип системы, практическая реализация................................100

§3.1 Архитектура..................................................................................................100

§3.2 Результаты работы........................................................................................111

Заключение.............................................................................................................116

Литература и ссылки............................................................................................117

Введение

Актуальность, новизна и цели работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общая архитектура

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

Практически во всех системах отслеживания движущихся объектов можно выделить несколько этапов работы. Первый этап работы подобной системы - это применение алгоритма обнаружения движущихся объектов к входной видео последовательности [1, 2]. Цель этого алгоритма обнаружения найти в кадре активные регионы, где непосредственно происходит движение. Принцип работы большинства подобных алгоритмов заключается в постепенном накапливании информации и построении модели заднего плана снимаемой сцены. При поступлении очередного кадра - его пиксели сравниваются с соответствующими пикселями модели фона, после чего алгоритм определяет: является ли данный пиксель кадра фоновым или же этот пиксель принадлежит движущемуся объекту. Затем уже пиксели этого кадра служат для обновления модели фона. Таким образом, резуль-

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

Исходная видео последовательность

в* кадр Ж

Обнаружение движения

Связывание пикселей

Связанные области

г ч Трассировка

Е 1 ■ движущимся ■ а

Набор движущихся объектов и их характеристик

Рис. 1. Общая структура процесса

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

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

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

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

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

кадр - растровое изображение, поступившее с камеры в некоторый момент времени;

видеопоток - последовательность кадров, полученная от цифровой видеокамеры или полученная из видео файла;

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

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

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

движущийся объект - класс связных областей расположенных на соседних по времени кадрах и объединённых по сходству некоторых своих характеристик, интерпретируются как "образ" физического движущегося объекта в некоторые моменты времени;

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

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

Глава 1. Обнаружение движения в видео потоке

В этой главе речь пойдёт о первых двух этапах работы системы отслеживания. Между этими этапами трудно провести четкую границу, поэтому они описываются вместе. Глава состоит из четырех параграфов. В первом делается обзор существующих алгоритмов, во втором описывается модификация алгоритма обнаружения движения основанного на смеси распределений [1, 4]. В третьем параграфе дается анализ использованного способа адаптации значений модели. В четвертом параграфе описаны методы, относящиеся ко второму этапу работы системы: фильтрация теней, морфологические операции и построение связных областей.

§1.1 Обзор существующих подходов

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