ДонНТУ
Портал магистров ДонНТУ

• Резюме
• Биография
• Библиотека
• Ссылки
• Отчет о поиске
• Индивидуальный раздел

Алгоритмы отслеживания объектов в видеопотоках на параллельных вычислительных системах

• Введение
• Цели и задачи
• Исследования в ДонНТУ
• Исследования в мире
• Методы отслеживания объектов
• Выводы
• Литература

Введение

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

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

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

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

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

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

Цели и задачи

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

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

Для отслеживания частей объектов будет использоваться поиск по шаблону, для выявления и выделения объектов в видео — метод вычитания фона[2].

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

Исходя из этого, принятые допущения и ограничения:

1. Основными отслеживаемыми объектами являются фигуры людей в вертикальном положении.
2. Признаки объектов, по которым их можно однозначно идентифицировать, такие как лица людей или номера на форме игроков, не учитываются.
3. Объекты движутся в плоскости земли, известны их максимальная скорость и ускорение.
4. Камера неподвижна, направлена под углом не менее 30º к плоскости земли, известно ее положение в пространстве.
5. Видео является цветным и имеет частоту не менее 10 FPS.

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

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

Исследования в ДонНТУ

В ДонНТУ данной тематикой занимался Середа А.А., защитивший в 2011 году кандидатскую диссертацию по теме отслеживания объектов в видеопотоках. Исследованиями методов отслеживания объектов в распределенной системе видеонаблюдения занимается Ларин Б.И.

Исследования в мире

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

Методы отслеживания объектов

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

Специалисты выделяют два общих подхода к построению методов автоматического определения и отслеживания множества объектов в видео:

1. Независимое выявление и выделение объектов в каждом кадре и определение соответствий между объектами, которые найдены в разных кадрах.
2. Выявление и выделение объектов в одном или некоторых кадрах инициализирует процесс отслеживания найденных объектов.

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

Самым распространенным методом выявления объектов в кадре, является отслеживание «пузырей» (англ. blob) [4]. Под этим понятием понимается множество связанных или близко расположенных точек кадра, выделенных некоторым алгоритмом сегментации изображения, например, вычитанием фона. Отслеживание «пузырей» является относительно простым в реализации, имеет низкую вычислительную сложность и позволяет надежно отслеживать изолированные объекты, в частности, те, которые сильно меняют свою форму.

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

• Частичного пересечения изображений объектов.
• Динамического фона сцены, который может быть классифицирован как объект.

Для предположения области, в которой может находиться объект в следующем кадре, его вероятного положения, или оценки вероятности перемещения объекта в заданное положение, используется модель движения объекта [5].

Классификация существующих методов обнаружения и выделения объектов в видеопотоке приведена на рис. 2.

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

Для выделения объектов применяется выявление различий между кадрами. Используется предположение: если существует разница между пикселями двух соседних кадров, то там происходит движение и эти пиксели принадлежат к движущимся объектам, иначе - к фону[6]. Достоинства метода: он прост в реализации и не требует априорной информации о виде отслеживаемых объектов. Недостатки метода:

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

Наиболее распространенным методом выделения объектов является метод вычитания фона (англ. Background Subtraction [7]). Он основан на построении модели фона, представляющей статическую часть кадра, которая не содержит движущихся объектов (рис. 3).

Для повышения качества и скорости выделения объектов, можно использовать комбинацию нескольких методов, например, сравнение с фоном [8] и предыдущим кадром.

Нахождение объектов и их траекторий можно выполнить один раз после завершения анализа всей видеозаписи (ретроспективное отслеживание, англ. off-line tracking) или выполнять в каждом кадре после его обработки (англ. on-line tracking). В первом случае, имея больше информации (при анализе кадра доступна информация не только о прошлых кадрах, но и о будущих), можно допустить меньше ошибок[9]. Однако, во многих случаях необходимо получение координат объектов в реальном времени. Несмотря на значительные усилия по повышению качества отслеживания объектов в видео, ни один из приведенных выше методов не обеспечивает безошибочного отслеживания, при наличии множества движущихся объектов в кадре.

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

Выводы

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

Литература

1. Середа А. А. , Ладыженский Ю. В. . «Разработка автоматизированной системы анализа видеозаписей спортивных соревнований.» Доклад на региональной студенческой научно-технической конференции «Інформатика та комп'ютерні технології», ДонНТУ, Донецк, 2005.
2. Ладиженський Ю.В. А.О. Середа «Відстежування об’єктів у відеопотоці на основі відстежування переміщення фрагментів об’єктів», Наукові праці Донецького національного технічного університету. Серія: «Обчислювальна техніка та автоматизація». Випуск 17 (148). – Донецьк : ДонНТУ, 2009. – 127-134 сс.
3. Avidan, Shai. Ensemble Tracking / S. Avidan // IEEE Transactions on Pattern Analysis And Machine Intellignence. – 2007. – Volume 29, № 2. – c. 261-271.
4. Osama, Masoud. Tracking and Analysis of Articulated Motion with an Application to Human Motion / M. Osama // A Thesis Submitted to the Faculty of the Graduate School of the University of Minnesota in Partial Fulfillment of the Requirements for the Degree of Doctr of Philosophy. – 2000. – 75 c.
5. Xu. M. Partial Observation vs. Blind Tracking through Occlusion / M. Xu, T. Ellis // Information Engineering Centre City University, London. – 10 c.
6. Khan S. Tracking People in Presence of Occlusion / S. Khan, M. Shah // Asian Conference on Computer Vision. – 2000. – c. 1132-1137.
7. Doshi, Anup. People Counting and Tracking for Surveillance/A. Doshi// CSE 252C Project Report Draft. – 2005. – 5 c.
8. Kim J.W. Robust real-time people tracking system for security / J.W. Kim, K.S. Choi, W.S. Park та ін. // Department of Electronics Engineering, Korea University, Anam-dong, Sungbuk-ku, Seoul, Korea. – 6 c.
9. Cucchiara R. Track-based and object-based occlusion for people tracking refinement in indoor surveillance / R. Cucchiara, C. Grana, G. Tardini // Proceedings of the ACM 2nd international workshop on Video surveillance & sensor networks. – New York, NY, USA, 2004. – c. 81-87.
10. NVIDIA CUDA Programming Guide Version 2.3 / NVIDIA Corporation // 2009. – 147 c. – Режим доступа: http://developer.download. nvidia.com/compute/cuda/2_3/toolkit/docs/NVIDIA_CUDA_Programming_Guide_2.3.pdf.

Примечание

При написании данного автореферата магистерская работа еще не завершена. Окончательное завершение – декабрь 2011 г. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.