Содержание к диссертации
Введение
Глава 1. Анализ проблемы отслеживания объектов и распознавания ситуаций на множестве движущихся объектов 14
1.1. Введение 14
1.2. Ситуации на множестве движущихся объектов и их распознавание 14
1.3. Аналитический обзор существующих методов отслеживания дви жущихся объектов в видеопотоке 16
1.4. Аналитический обзор существующих методов распознавания си туаций на множестве движущихся объектов 21
1.5. Постановка задачи исследования 35
1.6. Определения общих терминов 36
1.7. Общая схема системы распознавания ситуаций 36
1.8. Выводы по Главе 1 38
Глава 2. Моделирование ситуаций на множестве движущихся объектов 39
2.1. Введение 39
2.2. Пример ситуации на множестве движущихся объектов 39
2.3. Задача оптимального управления 42
2.4. Метод решения задачи оптимального управления 45
2.5. Применение метода оптимального управления для моделирования ситуации 46
2.6. Обобщение метода оптимального управления для задач распозна вания 50
2.7. Выводы по Главе 2 з
Глава 3. Захват и отслеживание объектов в видеопотоке 54
3.1. Введение 54
3.2. Определения терминов 54
3.3. Захват объекта в кадре видеопотока 55
3.4. Отслеживание объектов в видеопотоке 74
3.5. Выводы по Главе 3 84
Глава 4. Оптимальное отслеживание движущихся объектов 85
4.1. Введение 85
4.2. Отслеживание движущихся объектов обобщенным методом оптимального управления 85
4.3. Случай взаимного перекрытия объектов 93
4.4. Выводы по Главе 4 94
Глава 5. Представление ситуаций на множестве движущихся объектов 96
5.1. Введение 96
5.2. Экспертное представление ситуаций 97
5.3. Автоматическое представление ситуации 105
5.4. Непосредственное использование эталонной модели ситуации для распознавания 110
5.5. Выводы по Главе 5 114
Глава 6. Распознавание ситуаций на множестве движущихся объектов 115
6.1. Введение 115
6.2. Преобразование эталонной модели ситуации 115 Стр.
6.3. Распознавание ситуации обобщенным методом оптимального управления 118
6.4. Пример распознавания ситуации 122
6.5. Критерий распознавания ситуации 126
6.6. Выводы по Главе 6 128
Глава 7. Экспериментальное апробирование методов 129
7.1. Введение 129
7.2. Испытания методов на реальных видеопотоках 129
7.3. Испытания методов на искусственных видеопотоках 138
7.4. Выводы по Главе 7 141
Общие выводы и заключение 142
Список литературы
- Аналитический обзор существующих методов отслеживания дви жущихся объектов в видеопотоке
- Пример ситуации на множестве движущихся объектов
- Отслеживание объектов в видеопотоке
- Автоматическое представление ситуации
Аналитический обзор существующих методов отслеживания дви жущихся объектов в видеопотоке
Рассмотрим известные методы извлечения траекторий движения объектов из видеопотока, проанализируем их достоинства и недостатки.
Работа [2] посвящена извлечению траектории движения теннисного мяча из видеопотока. Предложенный метод рассчитан на видеопоток низкого разрешения. Определение позиции мяча на первом кадре фрагмента видеопотока осуществляется путем классификации блобов, найденных вычитанием фона. Движение теннисного мяча описывается линейной динамической моделью. Для извлечения траектории движения мяча предлагается использовать фильтр частиц в сочетании с методом Монте-Карло.
К достоинства метода можно отнести устойчивость метода в условиях шумов даже при невысоком разрешении кадров видеопотока. К недостаткам работы можно отнести невозможность восстановления траектории движения объекта в трехмерном пространстве. Кроме того, метод основан на фильтре частиц с экспоненциальной оценкой вычислительной сложности. Для отыскания траектории за конечное время используется метод Монте-Карло, который дает субоптимальное решение.
Работа [3] посвящена отслеживанию людей в условиях взаимного перекрытия с использованием нескольких видеокамер. Для решения задачи выполняется построение трех моделей: цветовой модели человека в виде цилиндра, вероятностной модели присутствия человека и модель размещения людей в плане (POM — Probabalistic Occupancy Map). Каждый пиксель кадра одной камеры относится к фону или к объекту. с использованием вероятностной модели присутствия человека и цветовой модели человека из условия максимальной апостериорной вероятности. Данные, полученные с нескольких видеокамер, используются для оценки положения людей в плане с помощью законов эпиполярной геометрии. Отслеживание перемещений человека в плане производится с применением фильтра Калмана.
К достоинствам работы можно отнести высокую стабильность метода в условиях взаимного перекрытия объектов, а также возможность получения траекторий движения объектов в трехмерном пространстве. К недостаткам работы можно отнести необходимость использования нескольких видеокамер.
Работа [4] посвящена извлечению траекторий движения автомобилей на перекрестке по видеопотоку, снятому в сложных метеоусловиях. На нижнем уровне обработки осуществляется вычитание фона, выделение блобов и расчет ориентированных охватывающих рамок для блобов. На среднем уровне обработки осуществляется отслеживание перемещений блобов на основе перекрытия их охватывающих рамок на последовательных кадрах видеопотока. На верхнем уровне обработки блобы интерпретируются как движущиеся объекты. Форма объектов оценивается с помощью стандартного дискретного фильтра Калмана. Положение объектов оценивается с помощью расширенного фильтра Калмана. Также реализована процедура обнаружения взаимного перекрытия объектов на основе сопоставления текущего размера блоба с размером движущегося объекта по оценке фильтра Калмана.
К достоинствам работы можно отнести устойчивость метода в условиях шумов и взаимного перекрытия объектов за счет использования фильтра Калмана. К недостаткам работы можно отнести невозможность восстановления траекторий движения объектов в трехмерном пространстве. Кроме того, фильтр Калмана дает оптимальную траекторию только при условии известных статистических характеристик модели, достоверные оценки которых сложно получить на практике.
Работа [5] является развитием работы [3] по отслеживанию людей в условиях взаимного перекрытия с использованием нескольких видеокамер. Плоская поверхность пола накрывается дискретной сеткой возможных позиций человека, фигура человека моделируется в виде прямоугольника в кадре. Поиск траекторий осуществляется из условия максимизации апостериорной вероятности, равной произведению вероятностей соответствия положения объекта в кадре цветовой модели объекта, модели присутствия объекта и модели движения объекта. Для отыскания оптимальных траекторий используется алгоритм Витерби в сочетании с оригинальной эвристикой для избежания комбинаторного взрыва при решении задачи максимизации апостериорной вероятности.
К достоинствам работы можно отнести устойчивость метода в условиях взаимного перекрытия объектов, а также возможность получения траекторий движения блобов в трехмерном пространстве. К недостаткам работы можно отнести тот факт, что использование эвристики дает лишь субоптимальное решение при поиске максимума апостериорной вероятности.
Работа [6] посвящена извлечению траекторий движения автомобилей из видеопотока дорожного движения на автомагистрали в условиях взаимного перекрытия и малых размеров автомобилей в кадре видеопотока. Сначала блобы автомобилей выделяются с помощью алгоритма вычитания фона на основе смеси гауссианов. С помощью детектора SIFT [7] на блобах выделяются характерные точки, которые отслеживаются в последовательности кадров с учетом проективного преобразования. Затем блобы, слившиеся друг с другом вследствие взаимного перекрытия, разбиваются на части с применением преобразования водораздела (Watershed Transform). Для определения участков, относящихся к разным автомобилям, производится кластеризация участков по скоростям движения и последующей группировке участков, относящихся к разным кластерам.
Пример ситуации на множестве движущихся объектов
Конечной целью настоящей работы является создание системы автоматического распознавания ситуаций на множестве движущихся объектов. Исходными данными для распознавания ситуации является экспертное описание ситуации и видеопоток с камеры наблюдения. Предлагается общая схема системы распознавания ситуаций, приведенная на Рис. 1.1. Кратко разберем назначение каждого программного модуля системы, реализующего отдельный этап обработки видеопотока.
Обработка видеопотока начинается с модуля захвата движущихся объектов. Под захватом объекта в кадре видеопотока будем понимать обнаружение объекта в кадре видеопотока.
В модуле захвата движущихся объектов происходит фиксация момента времени появления нового объекта в поле зрения камеры в результате захвата Общая схема системы распознавания ситуаций объекта, а также фиксация момента времени выхода объекта из поля зрения камеры. Фрагмент видеопотока, заключенный между этими моментами времени, представляет поведение отдельного объекта. Выделенный фрагмент передается на этап вычитания фона для последующего анализа.
В модуле вычитания фона из фрагмента видеопотока выделяется альфа-канал. Альфа-канал — это изображение, пиксели которого принимают значения «единица» или «ноль». В первом случае пиксель относится к объекту, во втором случае — к фону. Фактически, альфа-канал содержит силуэты движущихся объектов.
В модуле отслеживания движущихся объектов по силуэту объекта оценивается положение объекта в трехмерном пространстве и формируются тренды признаков объекта во времени. В модуле распознавания ситуации происходит обработка трендов призна 38 ков нескольких объектов, одновременно присутствующих в кадре, на эталонной модели ситуации. В результате обработки вычисляется количественный показатель соответствия трендов признаков эталонной модели и принимается решение об успешном или не успешном распознавании ситуации.
Модуль представления ситуации необходим для предварительного построения эталонной модели ситуации по экспертному описанию ситуации.
Модуль моделирования ситуаций служит для формирования видеопотоков и трендов признаков объектов для ситуаций, которые редко происходят в реальности и которые трудно воспроизвести в рамках натурного эксперимента. Моделирование также позволяет тестировать отдельные этапы распознавания ситуации независимо друг от друга, что облегчает предварительную настройку системы.
В модуле вычитания фона используется известный метод на основе смеси гауссианов [21], реализованный в рамках открытой библиотеки OpenCV [64].
Методы реализации остальных модулей системы распознавания ситуаций оригинальны. Их содержание изложено по главам настоящей диссертации.
Проведен аналитический обзор существующих методов отслеживания движущихся объектов в видеопотоке и распознавания ситуаций на множестве движущихся объектов, выделены достоинства и недостатки существующих методов. Поставлена задача разработки новых методов отслеживания движущихся объектов в видеопотоке и распознавания ситуаций на множестве движущихся объектов, позволяющих свести задачу распознавания к поиску оптимального пути в графе. Предложена общая схема системы распознавания ситуаций, каждому модулю которой посвящена отдельная глава настоящей диссертации. Глава 2. Моделирование ситуаций на множестве движущихся объектов
Настоящая глава посвящена математическому моделированию ситуаций на множестве движущихся объектов. Математическое моделирование представляет собой мощный инструмент для воспроизведения ситуаций, которые редко происходят в реальности и которые трудно воспроизвести в рамках натурного эксперимента. Так, например, натурное воспроизведение ситуации столкновения двух автомобилей требует больших материальных затрат. При математическом моделировании затраты минимальны.
В настоящей главе рассматривается метод моделирования ситуаций дорожных конфликтов. Исходными данными для моделирования являются математические уравнения, которые задают интересующую ситуацию. В результате моделирования необходимо получить тренды признаков объектов, движущихся в соответствии с заданной ситуацией. Рассмотрение метода моделирования ситуаций помогает глубже понять структуру рассматриваемых ситуаций и перейти к решению задачи распознавания ситуаций.
Рассмотрим ситуацию проезда перекрестка двумя автомобилями A и B (Рис. 2.1). В данной ситуации имеет место конфликт интересов. С одной стороны, водители автомобилей стремятся возможно быстрее проехать перекресток. С другой стороны, они стремятся не допустить столкновения своих автомобилей.
Свяжем с перекрестком прямоугольную систему координат x1Ox2 (Рис. 2.2). Тогда текущее положение автомобилей можно представить в виде точки X с координатами (x1, x2) на координатной плоскости. Абсцисса x1 определяет положение автомобиля A, ордината x2 определяет положение автомобиля B. Для указания желательных и нежелательных положений автомобилей введем терминальную и запрещенную области (Рис. 2.3). Если точка X попала в терминальную область, значит, автомобили успешно проехали перекресток. Если же точка X попала в запрещенную область, значит, автомобили столкнулись.
Отслеживание объектов в видеопотоке
Популярными моделями для обобщающих методов [71] являются: модель случайного поля, модель неявной формы, модель констелляции. В модели случайного поля кадр видеопотока разбивают на небольшие участки. Каждому участку приписывается метка, которая представляет его смысловое значение, например: «вода», «небо», «земля», «объект». Кроме того, оцениваются вероятности смежного размещения двух разных меток. Совокупность назначенных меток и их вероятностей составляет случайное поле. При этом метки подбира 57 ются таким образом, чтобы получилось наиболее правдоподобное случайное поле.
Модель неявной формы использует преобразование Хафа [58]. В процессе обучения на изображении объекта выделяют характерные точки. Для каждой точки определяют радиус-вектор, который соединяет ее с геометрическим центром объекта. При обнаружении характерной точки на исследуемом кадре соответствующий радиус-вектор указывает ожидаемую позицию центра объекта. Пикселю, расположенному в этой позиции, добавляют один голос. Пиксель, набравший наибольшее количество голосов после сканирования всего кадра, будет соответствовать наиболее вероятному положению центра объекта.
Модель констелляции рассматривает объект в виде совокупности элементов. На исследуемом кадре выделяют характерные участки и ставят их в соответствие элементам объекта или фона. Затем с помощью перебора отыскивают наиболее правдоподобное соответствие. Характеристики методов Капура-Винна [72], Феррари [73] и Фергюса-Пероны [74], использующих модели случайного поля, неявной формы и констелляции соответственно, представлены в Таблице 2.
Рассмотрим отдельные методы захвата объекта подробнее. Различающий метод Виолы-Джонса [68] использует каскад из нескольких классификаторов, последовательно применяемых к кадру видеопотока. Каждый классификатор включает набор характерных признаков Хаара [75], имеющих фиксированное взаимное расположение. Подавляющее большинство негативных кадров отсеивается первым классификатором каскада. Это обеспечивает высокое быстродействие метода.
Метод применялся для захвата человеческого лица в видеопотоке. Для обучения использовалось 4916 позитивных изображений и 9500 негативных изображений, собранных в сети Интернет. Тестирование метода проводилось на наборе MIT+CMU test set, содержащем 149 лиц на 23 изображениях. Точность захвата области интересов Obk(X, Y) в кадре Ik(w, h) составила 77,8 %. Время обработки изображения размером 384 288 пикселей на процессоре Intel Pentium III (700 МГц) составляет 67 миллисекунд. Верхняя оценка вычислительной сложности данного метода равна O(kdN), где d — количество используемых характерных признаков Хаара, k — количество используемых масштабов признаков, N = w h — количество пикселей изображения Ik(w, h) [76].
Обобщающий метод Капура-Винна [72] использует комбинацию модели случайного поля и модели констелляции. Искомый объект раскладывается на элементы и при назначении меток участкам случайного поля уточняется, какому элементу объекта принадлежит участок.
Для обучения метода использовалось 35 изображений из набора TU Darmstadt car dataset. Тестирование проводилось на 170 изображениях автомобилей из набора UIUC car dataset [77]. Точность захвата области интересов Obk(X,Y) в кадре Ik(w,h) составила 94,0 %. Среднее время обработки одного изображения размером 75 100 пикселей на стандартном персональном компьютере (3 ГГц) составила 3 секунды. Верхняя оценка вычислительной сложности метода равна O(mn2), где m — количество элементов объекта, n — количество участков изображения [71].
Обобщающий метод Феррари [73] использует модель неявной формы. Для повышения точности в нем также применяется модель деформаций, обученная на характерных признаках заданной области интересов Obk(X,Y).
Тестирование метода проводилось на открытых наборах изображений ETHZ shape classes [78] и INRIA horses [79]. Первый набор содержит изображения пяти типов объектов: логотип фирмы Apple, бутылка, жираф, кружка и лебедь. Для обучения модели деформации на каждом типе использовалась половина доступных изображений (всего было доступно 40, 48, 87, 48, 32 изображения соответственно). Тестирование проводилось на остальных изображениях набора. Второй набор содержит 170 изображений лошадей и 170 изображений без лошадей. Обучение проводилось на 50 позитивных изобра 59 жениях, тестирование — на остальных 290 изображениях. При этом средняя точность захвата области интересов Obk(X, Y) в кадре Ik(w, h) составила 78,1 %. Верхняя оценка вычислительной сложности метода равна O(AN), где N = wh – количество пикселей кадра Ik(w, h); A — количество различимых вариантов перемещения объекта за время, прошедшее между моментами поступления кадров Ik(w, h) и Ik+1(w, h).
Сравнение методов захвата. Различающие методы сосредоточены на различиях между позитивными и негативными изображениями конкретной обучающей выборки, тогда как обобщающие методы пытаются воссоздать структуру самого объекта по его изображениям. Поэтому при обучении обобщающих методов негативные изображения не требуются, а необходимое количество позитивных изображений существенно меньше, чем при обучении различающих методов (см. Таблицу 2). Таким образом, для упрощенного обучения следует использовать подход обобщающих методов.
При выборе модели обобщающего метода, будем руководствоваться следующими замечаниями. Модель случайного поля требует больших вычислительных затрат, что неприемлемо для обработки видеопотока в реальном времени. Учет возможных вариаций формы объекта в модели неявной формы требует значительного увеличения количества обучающих изображений. Модель констелляции изначально представляет объект в виде совокупности отдельных элементов. Именно в этой модели проще учитывать различные искажения геометрической формы объекта за счет изменения взаимного положения его элементов.
Автоматическое представление ситуации
В настоящем разделе рассматривается метод представления ситуаций с участием движущихся объектов в виде иерархии нечетких конечных автоматов по экспертному описанию. Следуя данному методу, эксперт задает признаки, лингвистические переменные, отношения между объектами и последовательности изменения этих отношений, характерные для интересующей ситуации. В результате представления ситуации получается эталонная модель ситуации, которая затем может использоваться для распознавания похожих ситуаций без участия эксперта. Эталонная модель ситуации — это формализованное представление ситуации в виде иерархии нечетких конечных автоматов.
Теоретические основы предложенного метода представления ситуаций в виде иерархии нечетких конечных автоматов подробно изложены в работе [66]. В качестве примера рассмотрим применение данного метода для представления опасной ситуации, возникающей при встрече двух автомобилей на перекрестке.
Рассмотрим следующую опасную ситуацию. Пусть имеется прямоугольный автодорожный перекресток. Автомобиль A двигается по дороге в сторону перекрестка и приостанавливается, немного не доехав до него. Автомобиль B двигается в сторону перекрестка по перпендикулярной дороге. Когда автомобиль B подъезжает к перекрестку, автомобиль A неожиданно набирает скорость и сталкивается с автомобилем B.
Для описания поведения автомобилей в рассматриваемой ситуации прежде всего требуется выбрать необходимые признаки. Пусть автомобили A и B выезжают на перекресток, двигаясь по взаимно перпендикулярным прямым линиям, пересекающимся в точке O (Рис. 5.1).
Свяжем с перекрестком прямоугольную декартову систему координат xOy так, чтобы ось Ox совпала с линией движения автомобиля A, а ось Oy с линией движения автомобиля B (см. Рис. 5.1). Для простоты представим каждый автомобиль в виде прямоугольника и будем считать, что координаты местоположения автомобиля совпадают с геометрическим центром соответствующего прямоугольника. Поскольку автомобили двигаются строго вдоль координатных осей, для определения текущего местоположения автомобилей на k–ом отсчете времени достаточно соответственно координат ys(kA) и ys(kB), отсчитываемых от начала координат O по соответствующим осям. Координаты местоположения ys(kA) и ys(kB) являются первыми признаками. Вторыми признаками являются соответственно скорости движения автомобилей yv(kA) и yv(kB). Тогда вектор признаков в данном случае будет иметь вид:
После определения измеряемых признаков необходимо задать свойства данных признаков, характерные для рассматриваемой ситуации. Эксперту легче всего описать ситуацию словесно на естественном языке, давая качественную характеристику происходящим событиям: «автомобиль A находится далеко от перекрестка», «автомобиль B двигается с большой скоростью» и т. п. Для автоматической обработки такого описания на вычислительной технике каждой качественной характеристике эксперт должен сопоставить диапазон значений соответствующего количественного признака. Между качественными характеристиками «большая скорость» и «маленькая скорость» трудно провести четкую границу значения скорости. На практике адекватным решением является использование нечетких множеств с размытыми границами. Аппарат лингвистических переменных позволяет перевести словесное описание ситуации в требования принадлежности количественных признаков объектов заданным нечетким множествам.
Для описания движения автомобилей A и B соответственно введем пары лингвистических переменных место(kA), скорость(kA), место(kB) и скорость(kB). Лингвистические переменные место(kA) и место(kB) характеризуют местоположение соответствующих автомобилей относительно перекрестка и принимают лингвистические значения далеко(X), близко(X) и содержится(X). Лингвистические переменные скорость(kA) и скорость(kB) характеризуют величину скорости соответствующих автомобилей и принимают лингвистические значения высокая(X) и низкая(X).
Нечеткие множества, соответствующие лингвистическим значениям далеко(X), близко(X), содержится(X), высокая(X) и низкая(X) показаны на Рис. 5.2 и 5.3 соответственно. Указанные нечеткие множества используются для построения нечетких автоматов Mместо(kX), Mскорость(kA) и Mскорость(kB) 1-го уровня, характеризующих местоположение и скорости автомобилей.
Автомат Mместо(kX), представленный графом на Рис. 5.4, задает последовательность лингвистических значений [далеко(X), близко(X), содержится(X)] лингвистической переменной место(kX). Основу графа автомата составляет цепочка разрешенных состояний s11-s12-s13, соответствующих лингвистическим значениям задаваемой последовательности. Здесь s11 — начальное состояние автомата (помечено входящей стрелкой на Рис. 5.4), s13 — конечное состояние автомата (помечено выходящей стрелкой на Рис. 5.4). Условия переходов между состояниями автомата задаются следующим образом. При поступлении на вход автомата лингвистического значения, соответствующего текущему состоянию, автомат остается в данном состоянии. При поступлении на вход автомата лингвистического значения, соответствующего следующему по цепочке состоянию автомат переходит в следующее состояние. При поступлении на вход автомата лингвистического значения, не соответствующего заданной последовательности, автомат переходит в запрещенное состояние s14. Однажды попав в запрещенное состояние, автомат остается в данном состоянии при любых значениях на входе.