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

• Резюме
• Біографія

Алгоритми відстежування об'єктів у відеопотоках на паралельних обчислювальних системах

• Вступ
• Цілі
• Дослідження в ДонНТУ
• Дослідження в світі
• Методи відстеження об'єктів
• Висновки
• Література

Вступ

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

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

Головним завданням даних систем є відстеження об'єктів у відео. Під відстеженням об'єктів у відеопотоці розуміється отримання набору видимих ​​об'єктів і їх координат у кожному кадрі.

Відстеження об'єктів у відео має велику обчислювальну складність. Забезпечення швидкодії, необхідного для відстеження великої кількості об'єктів у реальному часі, вимагає розробки методів і алгоритмів відстеження для паралельних комп'ютерних систем.

Основна проблема відстеження багатьох об'єктів у відео — об'єкти, частково перекриті іншими об'єктами. Найбільш поширений підхід до вирішення цієї проблеми — відстеження цілого об'єкта як сукупності його частин, який дозволяє відтворювати траєкторію об'єкта під час перекриття на основі траєкторій його не перекритих частин. У той же час, даний підхід буде малоефективним, якщо кілька об'єктів перетинаються велику частину часу.

Увага, що приділяється проблемі відстеження об'єктів у відео, а також наявність невирішених завдань, дозволяє говорити про те, що тема дослідження є актуальною.

Цілі

Аналіз методів відстеження об'єктів показав, що в даний час гостро стоїть проблема забезпечення нерозривної відстеження одного або кількох об'єктів у системах автоматичного аналізу спортивних змагань, відеоспостереження та системах безпеки [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 р., тому повний текст роботи, а також матеріали за темою можуть бути отримані у автора або його керівника тільки після зазначеної дати.