Метод відстежування об’єктів у відеопотоці та його реалізація на паралельних комп’ютерних системах

19

Размещено на http://www.allbest.ru/

[Введите текст]

Державний вищий навчальний заклад

«Донецький національний технічний університет»

УДК 004.932.2: 004.272.2

Автореферат

дисертації на здобуття наукового ступеню

кандидата технічних наук

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

Спеціальність 05.13.05 - комп'ютерні системи та компоненти

СЕРЕДА Андрій Олександрович

Донецьк - 2011

Дисертацією є рукопис

Робота виконана в Державному вищому навчальному закладі “Донецький національний технічний університет” Міністерства освіти і науки, молоді та спорту України

Науковий керівник:кандидат технічних наук, доцент

Ладиженський Юрій Валентинович,

ДВНЗ “Донецький національний технічний університет” Міністерства освіти і науки, молоді та спорту України, доцент кафедри “Прикладна математика і інформатика”;

Офіційні опоненти:доктор технічних наук, професор

Скобцов Юрій Олександрович,

ДВНЗ “Донецький національний технічний університет” Міністерства освіти і науки, молоді та спорту України, завідувач кафедри “Автоматизовані системи управління”;

доктор технічних наук, доцент

Гороховатський Володимир Олексійович,

Харківський національний університету радіоелектроніки Міністерства освіти і науки, молоді та спорту України, професор кафедри “Інформатика”.

Захист відбудеться 19 травня 2011р. о 14 годині на засіданні спеціалізованої вченої ради Д11.052.03 Державного вищого навчального закладу “Донецький національний технічний університет” за адресою:

83001, м. Донецьк, вул. Артема, 58, навч. корпус 8, ауд. 704.

З дисертацією можна ознайомитися в бібліотеці Донецького національного технічного університету за адресою:

83001, м. Донецьк, вул. Артема, 58, навч. корпус 2.

Автореферат розісланий «18» квітня 2011р.

Вчений секретар

спеціалізованої вченої

ради Д11.052.03Г.В. Мокрий

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми

Під відстежуванням об'єктів у відеопотоці розуміється отримання множини видимих об'єктів (наприклад, людей чи автомобілів) та їх координат в кожному кадрі. Ця задача виникає в комп'ютерних системах безпеки, автоматизованого аналізу спортивних змагань, моніторингу дорожнього руху, при організації людино-машинного інтерфейсу та кодуванні відео, її розв'язанню присвячено багато наукових робіт.

Відстежування об'єктів у відео має велику обчислювальну складність. Проблемою є забезпечення швидкодії, необхідної для відстежування великої кількості об'єктів у реальному часі, що потребує розробки методів і алгоритмів відстежування для паралельних комп'ютерних систем. Паралельним методам та обчислювальним архітектурам для аналізу зображень та відео присвячені роботи В.П. Боюна, Б.В. Кострова, В.Н Ручкіна, K. Fu, S.-C. Cheng, S.Y. Yap.

Однією з основних проблем відстежування множини об'єктів у відео є відстежування об'єктів, які частково перекриті іншими об'єктами. В останні роки набуває поширення підхід до відстежування цілого об'єкту як сукупності його частин, зокрема, у роботах F. Tang, А. Cavallaro, P.S. Kumar, який дозволяє відтворювати траєкторію об'єкта під час перекриття на основі траєкторій його не перекритих частин. Представлення об'єкта як сукупності частин також використовується при структурному та синтаксичному розпізнаванні зображень у роботах В.О. Гороховатського, Є.П. Путятіна, М.І. Шлезінгера. Невирішеними залишаються задачі забезпечення швидкодії для відстежування множини об'єктів у реальному часі та відстежування множини об'єктів, зображення яких перетинаються більшу частину часу.

Відстежувати частини об'єктів можливо за допомогою шаблону, який динамічно оновлюється, як у роботах R. Cucchiara, C. Grana та методів пошуку блоків зображення в кадрі, які звичайно використовуються при кодуванні відео, розроблених R. Li, W.I. Choi, M. Rehan. Проблемами підходу є забезпечення високої швидкодії та оцінювання правильності пошуку.

Найпоширенішим методом виявлення та виділення об'єктів у відео є метод віднімання фону, який базується на побудові моделі фону, що не містить рухомих об'єктів. Однією з головних проблем методу є автоматична ініціалізація та оновлення моделі фону за наявності великої кількості об'єктів у кадрі. У роботах A.Colombari, A. Fusiello, D. Gutchess, E. Cohen-Solal розроблені методи автоматичної ініціалізації моделі фону за наявності об'єктів в кадрі, проте, невирішеною залишаться задача зниження кількості помилок при оновленні моделі фону в реальному часі.

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

Зв'язок роботи з науковими програмами, планами, темами

Основні дослідження по темі дисертації проводилися на кафедрі прикладної математики та інформатики ДВНЗ “Донецький національний технічний університет” в рамках науково-дослідних робот з держбюджетних тем № Д-1-08 “Розвиток теорії синтезу і розподіленого моделювання високопродуктивних проблемно-орієнтованих обчислювальних систем з програмованими НВІС” (№ держреєстрації 0108U001959) і № Н-39-05 “Методи та алгоритми організації обчислювальних процесів у високопродуктивних обчислювальних, інтелектуальних та моделюючих системах”, в яких здобувач приймав участь як виконавець.

Мета та завдання досліджень

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

Для досягнення цієї мети необхідно вирішити наступні основні задачі:

- дослідити існуючі методи виявлення і відстежування об'єктів у відеопотоці та визначити напрямки підвищення швидкості та точності виявлення та відстежування множини об'єктів;

- на базі існуючих методів відстежування об'єктів розробити новий метод, що дозволяє відстежувати у відеопотоці частково перекриті об'єкти;

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

- підвищити точність методів моделювання фону за наявності великої кількості об'єктів у кадрі;

- відобразити новий метод відстежування на паралельну архітектуру MIMD, за рахунок чого забезпечити швидкодію, необхідну для відстежування об'єктів у реальному часі;

- прискорити пошук фрагментів об'єктів в кадрі за рахунок розробки ефективних паралельних алгоритмів пошуку для архітектури SIMD;

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

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

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

Методи досліджень. Розробка і обґрунтування нового методу відстежування об'єктів базувалися на використанні методів теорії комп'ютерного зору, обчислювальної геометрії, теорії множин, нечіткої логіки. При розробці методу підвищення точності моделюванні фону використовувалися методи теорії ймовірностей. При реалізації алгоритмів використовувалися методи об'єктно-орієнтованого програмування. При дослідженні властивостей розроблених алгоритмів використовувалися методи теорії алгоритмів, теорії паралельних обчислень, математичної статистики та комп'ютерне моделювання із використанням багатопроцесорних комп'ютерів, кластеру та багатопотокових графічних процесорів. Достовірність результатів гарантується коректністю постановки задачі, системним підходом при викладі наукових положень, коректним використовуванням математичного апарату і комп'ютерного моделювання, а також збігу практичних результатів з основними теоретичними положеннями. об'єкт відеопотік моделювання фон

Наукова новизна отриманих результатів полягає в наступному:

1. Розроблено новий метод автоматичного виявлення і відстежування множини об'єктів у відеопотоці “DSOFT” (Dynamic Set of Fragments Tracking), який відрізняться представленням об'єкта як множини рухомих фрагментів, способом побудови траєкторії об'єкта на основі траєкторій його фрагментів і знаходженням відповідностей між об'єктами і їх фрагментами, що дозволяє відстежувати частково перекриті об'єкти.

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

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

4. Вперше розроблене відображення методу DSOFT на паралельні комп'ютерні системи з архітектурами MIMD UMA і кластер, яке використовує асинхронний обмін даними та асиметричне статичне балансування навантаження. Визначено оптимальне балансування навантаження для систем з різними характеристиками.

5. Розроблено нові ефективні апаратно-орієнтовані алгоритми пошуку в кадрі фрагмента зображення довільної форми для багатопотокових графічних процесорів з архітектурою CUDA, засновані на попіксельному порівнянні кадру з шаблоном, які можуть бути використані для прискорення відстежування за методом DSOFT.

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

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

Запропонований метод підвищення точності моделювання фону може бути використано в комп'ютерних системах, що використовують виявлення об'єктів у відео.

Результати дисертаційного дослідження використано у науково-виробничому підприємстві ТОВ “АМІ” (м. Донецьк) при розробці цифрової системи безпеки для реалізації автоматичного виявлення підозрілих рухомих об'єктів у відео; в науково-дослідницький темі Донецького національного технічного університету “Розвиток теорії синтезу і розподіленого моделювання високопродуктивних проблемно-орієнтованих обчислювальних систем з програмованими НВІС”; у навчальному процесі при читанні лекцій з курсів “Комп'ютерний синтез та обробка зображень”, “Теорія та організація розподіленої обробки даних в комп'ютерних мережах”, “Архітектура комп'ютера” та в науково-дослідних роботах студентів і магістрантів.

Особистий внесок здобувача. Всі основні положення і результати дисертаційної роботи, що виносяться на захист, отримані автором самостійно.

Апробація результатів роботи. Основні положення і результати дисертаційної роботи були оприлюднені і отримали позитивну оцінку на наступних конференціях та конкурсах: “Моделювання і комп'ютерна графіка” (м. Донецьк, 10-12 жовтня 2007 р.), “Інформатика та комп'ютерні технології” (м. Донецьк, 25-27 листопада 2008 р.), “Комп'ютерний моніторинг та інформаційні технології” (м. Донецьк, 11-15 травня 2009 р.), “Сучасна інформаційна Україна: інформатика, економіка, філософія” (м. Донецьк, 14-15 травня 2009 р.), “Моделювання та комп'ютерна графіка” (м. Донецьк, 10-12 жовтня 2009 р.), “Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій” (м. Запоріжжя, 22-24 вересня 2010 р.), конкурс CUDA для розробників компанії Юстар (15 лютого - 14 травня 2010 р.).

Публікації. Основні результати дисертаційної роботи опубліковані в 10 наукових працях, з них 4 статті у виданнях, включених до переліку ВАК України, 6 публікацій у працях конференцій.

Структура і обсяг дисертаційної роботи. Дисертація складається із вступу, п'яти розділів, висновків, списку використаних джерел із 135 найменувань на 17-ти сторінках, та 4 додатків. Повний обсяг дисертації складає 179 сторінок друкарського тексту, з них 149 сторінок основного тексту, містить 77 рисунків і 6 таблиць.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У першому розділі “Методи та обчислювальні засоби виявлення і відстежування об'єктів у відеопотоці” виконано аналіз існуючих методів виявлення та відстежування множини об'єктів у відео зі стаціонарної камери. Виявлені їх недоліки та перспективні підходи до відстежування. Основними невирішеними проблеми є відстежування об'єктів, частково перекритих іншими об'єктами, та моделювання фона за наявності великої кількості рухомих об'єктів у кадрі.

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

На основі виконаного аналізу сформульовані мета та задачі дослідження, а також обмеження на область застосування досліджуваних методів відстежування.

У другому розділі “Розробка методів і алгоритмів виявлення і відстежування об'єктів у відеопотоці” запропоновано і обґрунтовано метод автоматичного виявлення та відстежування об'єктів у відео DSOFT. Кожен об'єкт розглядається як множина рухомих фрагментів. Виявлення та відстежування об'єктів зводиться до:

1. Виявлення та відстежування множини рухомих фрагментів у відеопотоці.

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

3. Побудови траєкторій об'єктів на основі траєкторій їх фрагментів.

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

Метод дозволяє:

1. Відстежувати об'єкти, які частково перекриті іншими об'єктами.

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

3. Надавати результат як у реальному часі після аналізу кожного кадру, так і ретроспективно уточнений результат з заданою затримкою.

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

Фрагмент об'єкту представлено шаблоном, який складається з зображення частини об'єкту розміром та матриці приналежності . Елемент показує ймовірність того, що піксель відноситься до шаблону. Нехай - зображення кадру, а

(1)

- міра різниці між кадром та шаблоном, лівий верхній кут якого співпадає з пікселем кадру . Нехай - множина всіх можливих координат лівого верхнього пікселя шаблона в СК кадру, де x₀, y₀, H, W - константи.

Найкращу позицію шаблону, який шукають, визначимо як

(2)

(3)

У роботі використовуються методи пошуку фрагмента у кадрі за шаблоном, засновані на попіксельному порівнянні шаблона і кадру (англ. Block Matching Algorithms).

З метою відсівання фрагментів, положення яких було визначено невірно, запропоновано модифікації методів пошуку фрагментів зображення в кадрі, зокрема, пошуку повним перебором та швидких алгоритмів Three Step Search і Diamond Search.

Обчислимо коефіцієнти впевненості у правильності пошуку фрагмента:

1. Знайдений фрагмент кадру повинен бути достатньо схожий на фрагмент, який шукається:

, (4)

де D_min і D_max - константи.

2. Інші фрагменти з області пошуку повинні бути достатньо несхожі на фрагмент, що шукається. Для цього знайдемо кращу з позицій шаблона, які не входять до околиці найкращої позиції:

; (5)

; (6)

, (7)

де s_alt, k_{alt_min} і k_{alt_max} - константи.

3. Значна частина фрагмента повинна не відноситися до фону:

(8)

де s_{for_min}, s_{for_max} - константи, а показує ймовірність того, що піксель кадру не відноситься до фону.

Коефіцієнт надійності пошуку фрагмента в кадрі обчислюється як .

Розроблено алгоритм порівняння траєкторій пари об'єктів чи фрагментів, результат якого представлено у нечіткому вигляді:

а) коефіцієнт схожості , який показує, чи можуть два фрагменти або об'єкти відноситися до одного фізичного об'єкту;

б) коефіцієнт упевненості K_conf , який показує, наскільки обґрунтованим є значення K_like. При значення K_like не визначено.

Назвемо фрагмент, який не відноситься до об'єкту, вільним.

Розроблено набір правил, які визначають необхідність виконання дій над об'єктами та фрагментами:

1. Визначаються помилкові об'єкти, які не відповідають фізичним об'єктам.

2. Вільний фрагмент f відноситься до існуючого об'єкту o якщо

та не існує іншого об'єкта o' такого, що

,

де залежить від того, чи вважається o' помилковим.

3. Новий об'єкт створюється із вільного фрагмента, якщо час існування фрагмента перевищує задану константу. До щойно створеного об'єкту додаються інші вільні фрагменти, які задовольняють правилу 2.

4. Фрагмент f відділяється від об'єкту o якщо (це правило також включає випадок розділення об'єкту на два об'єкти).

5. Об'єкти o₁ і o₂ об'єднуються в один об'єкт якщо

та .

Об'єднання відбувається в порядку зменшення K_like.

6. Втрачений об'єкт і нещодавно створений (знайдений) об'єкт об'єднуються в один, якщо вони не розташовані на границях кадру і немає інших об'єктів, з якими вони можуть об'єднатися.

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

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

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

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

(9)

де і - ймовірність того, що відрізок часу, який містить фон чи об'єкти відповідно, має довжину t.

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

У третьому розділі “Дослідження методів і алгоритмів виявлення і відстежування об'єктів у відеопотоці” виконано експериментальну оцінку ефективності запропонованих алгоритмів.

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

Виконано автоматичну оптимізацію параметрів алгоритмів оцінки правильності пошуку фрагментів та оновлення шаблонів.

Показано, що використання запропонованих коефіцієнтів v_like (4), v_alt (7) і v_imp (8), порівняно із використанням тільки коефіцієнту v_like, дозволяє знизити середнє число кадрів, в яких фрагменти зображень футболістів відстежуються з помилкою, в 1.2-2 рази при незмінному середньому числі кадрів, у яких фрагменти відстежено без помилок.

Експериментально досліджено якість відстежування частково перекритих зображень футболістів за методом DSOFT при аналізі у реальному часі тестового відео футбольного матчу VS-PETS'2003 (камера №3). В залежності від долі площини об'єкту, що було перекрито, підраховано кількість ситуацій, в яких усі об'єкти було відстежено вірно, та ситуацій, де хоча б один об'єкт не було відстежено вірно (рис. 1). При долі перекриття від 61% до 100% ретроспективно уточнення результату скоротило кількість помилок з 12 до 10.

Рис. 1. Якість відстежування частково перекритих об'єктів

Експериментально досліджено запропонований метод підвищення точності моделювання фону при використанні моделі фону із незмінною інтенсивністю (кольорове зображення фону), що оновлюється зваженим підсумовуванням із кадром. При моделюванні фону та виділенні пікселів зображень пішоходів на людній вулиці запропонований метод дозволив знизити кількість помилкових спрацювань у 2.1-2.6 разів при незмінній чутливості класифікатора (рис. 2). При цьому швидкодія знизилася у 2.5 рази і залишилася достатньою для аналізу відео у реальному часі.

Рис. 2. Характеристичні криві класифікації пікселів методом віднімання фону

У четвертому розділі “Реалізація методу відстежування об'єктів у відеопотоці на паралельних комп'ютерних системах” проаналізовано підходи до паралельного відстежування об'єктів за методом DSOFT. Для прискорення аналізу одного відеопотоку в реальному часі доцільно розпаралелити аналіз кадру на комп'ютерній системі типу MIMD, а окремі ресурсоємні операції (зокрема, пошук фрагментів об'єктів) виконувати на співпроцесорах типу SIMD.

Розроблено відображення методу DSOFT на архітектуру MIMD (рис. 3). Паралельно виконується моделювання та віднімання фону, розпізнавання об'єктів та пошуку фрагментів об'єктів; решта операцій виконується послідовно на одному процесорі. Для етапів, що виконуються паралельно, використовується асиметричне балансування навантаження. Для мінімізації простою через очікування даних, результати, необхідні іншим процесорам, асинхронно відправляються одразу після їх обчислення, а синхронне отримання даних від інших процесорів відкладається до тих пір, поки вони не знадобляться на даному процесорі.

Розроблено нові ефективні апаратно-орієнтовані алгоритми пошуку в кадрі фрагмента зображення довільної форми за шаблоном на багатопотокових графічних процесорах з архітектурою CUDA.

19

Размещено на http://www.allbest.ru/

[Введите текст]

Рис. 3. UML діаграма діяльності паралельного аналізу кадру на системі типу MIMD

Використовується кешування шаблону по частинам у спільній (shared) пам'яті мультипроцесора, області кадру - у текстурному кеші, а проміжних результатів - у пам'яті пристрою (device memory). Позначимо через B кількість потоків, div - операцію цілочисельного ділення, mod - остачу від ділення, - цілу частину x, - мінімальне ціле число, що є не меншим за x.

На архітектуру CUDA відображено пошук повним перебором позицій шаблону.

1. Розіб'ємо шаблон по рядках на мінімальну кількість частин n, кожна з яких вміщується в спільну пам'ять. Нехай p-та частина містить рядки з номерами , а

. (10)

2. Для p від 1 до n в спільну пам'ять завантажуються рядки шаблону . Кожний t-й потік обробляє множину позицій шаблона

:

2.1. Для всіх обчислює і зберігає в пам'яті пристрою часткові суми

, де .

2.2. При обчислює і зберігає в регістрах значення

і .

3. Визначається потік із номером

,

який записує в змінні в спільній пам'яті значення

, , .

4. Кожен потік обчислює

, де ,

використовуючи раніше збережені в пам'яті пристрою значення .

5. вибирається з так само, з на кроці 3.

Розроблено швидкий алгоритм пошуку фрагмента зображення на CUDA, що використовує порівняння шаблону з кадром у вузлах сітки та уточнення рішення перебором позицій шаблону в околицях обраних вузлів.

1. Шаблон розбивається на n частин як в попередньому алгоритмі.

2. Для p від n до 1 в спільну пам'ять завантажуються рядки шаблону . Кожний t-й потік обробляє множину позицій шаблона для

, де , , , , s_y

і s_x - шаг сітки по вертикалі і горизонталі відповідно:

2.1. Для всіх обчислює і зберігає в пам'яті пристрою часткові суми

, де .

2.2. При обчислює і зберігає в регістрі

.

3. Визначаться

.

4. Нехай , де

(11)

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

(12)

де - константи. Нехай обрано m вузлів із координатами .

5. Для p від 1 до n у спільну пам'ять завантажуються рядки шаблону (окрім рядків , що залишилися у кеші після кроку 2). Нехай площина околиці дорівнює L . Кожний t-й потік для

обчислює

і обробляє позиції , які входять до околиць позицій ,

де ,

, :

5.1. Обчислює і зберігає в пам'яті пристрою часткові суми

, де .

5.2. При визначає і зберігає у регістрах два мінімальних значення серед обчислених та відповідні пари координат з .

6. Серед найменших значень повних сум, набутих у регістрах, визначаються , , , .

Прискорення пошуку множини шаблонів досягається за рахунок одночасного пошуку різних шаблонів на різних мультипроцесорах та одночасної перевірки різних позицій одного шаблона різними потоками. Відсутні uncooalesced запити до пам'яті. Визначені параметри алгоритмів, які забезпечують максимальне завантаження процесорів. Отримані оцінки часової складності пошуку повним перебором (13) і швидкого алгоритму пошуку (14) при практично використовуваних значеннях параметрів:

;(13)

; (14)

де - площина фрагмента; - кількість можливих позицій фрагмента; - кількість вузлів сітки на кроці 2 швидкого алгоритму; n - середня кількість вузлів сітки, які задовольняють умові (12); K_s - коефіцієнт, який дорівнює відношенню кількості потоків B до реального прискорення при виконанні алгоритму у B потоків порівняно з одним потоком.

У п'ятому розділі “Дослідження методу відстежування об'єктів у відеопотоці на паралельних комп'ютерних системах” виконано моделювання та оцінка ефективності розроблених паралельних методів та алгоритмів.

На рис. 3 додамо відмітки часу проходження окремих етапів від початку аналізу кадру на основному та додаткових процесорах.

На рис. 4 отримана аналітична оцінка часу паралельного аналізу кадру (досягнення відмітки M₉) на багатопроцесорному комп'ютері та кластері за методом DSOFT як функція від:

1. Часу виконання послідовних етапів алгоритму T_C1,...,T_C7.

2. Об'єму даних в ОЗП: кадру S_farme, результату віднімання фона S_back, фрагментів S_frag, областей, що розпізнаються S_rec.

3. Характеристик паралельної системи: кількості процесорів N, кількості процесорів на одному обчислювальному вузлі N_l, часу передавання одного байта мережею K_n, упакування та розпакування одного байта для передачі K_l. K_bc відображає властивості широкомовного розсилання; у реалізації MPI MPICH2 при N_l=2 та N?7 .

4. Параметрів балансування навантаження A₁, A₃, A₅ - доля обчислень відповідно етапів 1, 3 та 5 алгоритму на рис. 3, які виконуються на усіх додаткових процесорах.

O₁ = 0 + (K_l + K_n K_bc + K_l) S_frame + T_C1 A₁/(N-1);

M₁ = 0 + K_l S_frame + T_C4;

M₂ = M₁ + K_l S_frag A₅ + T_C1 (1-A₁);

M₃ = max(M₂ + K_l S_back A₁ (N-2)/(N-1), O₁ + K_l S_back A₁/(N-1) +

K_n S_back A₁ (N-N_l)/(N-1)) + K_l S_back A₁/(N-1);

O₂ = max(M₃ + K_l S_back + K_bc K_n S_back, O₁ + K_l S_back A₁/(N-1)) + K_l S_back;

M₄ = M₃ + K_l S_back + T_C2;

M₅ = M₄ + K_l S_rec A₃ + T_C5 (1-A₅);

M₆ = max(M₅ + K_l S_frag (N-2)/(N-1), O₃ + K_l S_frag A₅/(N-1) +

K_n S_frag A₅ (N-N_l)/(N-1)) + K_l S_frag A₅ /(N-1);

O₄ = max(M₄ + K_l S_rec A₃ N_l/(N-1) + K_n S_rec A₃ (N-N_l)/(N-1), O₃ +

K_l S_frag A₅ /(N-1)) + K_l S_rec A₃ (N-1);

M₇ = M₆ + T_C6 + T_C3 (1-A₃);

O₅ = O₄ + T_C3 A₃/(N-1);

M₈ = max(M₇ + K_l S_rec (N-2)/(N-1), O₅ + K_l S_rec A₃/(N-1) +

K_n S_rec A₃ (N-N_l)/(N-1)) + K_l S_rec A₃ /(N-1);

M₉ = M₈ + T_C7.

Рис. 4. Аналітична оцінка часу паралельного аналізу кадру на системі MIMD

Шляхом мінімізації оцінки часу на рис. 4 отримана теоретична оцінка оптимального балансування навантаження для паралельних систем із різними характеристиками.

Виконано моделювання на кластері ДонНТУ із використанням технології MPI та ПЗ Microsoft Compute Cluster Pack, а також із виконанням алгоритму на багатопроцесорному комп'ютері як багатопотокової програми.

Оцінки середнього часу аналізу кадру футбольного матчу роздільною здатністю 674Ч368 на системах із процесорами Intel Core 2 Duo 6320 показано на рис. 5. Доцільно виконувати аналіз одного відеопотоку на комп'ютері з кількістю ядер від 2 до 4. Подальше зростання прискорення стримується наявністю етапів алгоритму, які виконуються послідовно.

Рис. 5. Оцінка часу аналізу кадру для систем із різними характеристиками

Виконано моделювання пошуку фрагментів зображень футболістів на багатопотокових графічних процесорах із архітектурою CUDA. На GPU початкового рівня GeForce GTS 250 E-Green отримано прискорення пошуку множини фрагментів зображення повним перебором до 40 разів (рис. 6а) і прискорення швидкого пошуку до 11 разів (рис. 6б) порівняно з одним ядром CPU Athlon X2 5400. При цьому швидкий алгоритм пошуку на CUDA GPU забезпечує не меншу точність пошуку порівняно зі швидким алгоритмом на CPU. Найбільше прискорення досягається при розмірі сторони фрагмента, області пошуку і кількості фрагментів не менше 32.

а) пошук повним перебором позицій

б) алгоритм швидкого пошуку

Рис. 6. Залежність прискорення на CUDA GPU порівняно з CPU від розміру шаблону та кількості його можливих позицій

ВИСНОВКИ

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

1. Розроблено новий метод автоматичного виявлення і відстежування множини об'єктів у відеопотоці “DSOFT” (Dynamic Set of Fragments Tracking), який відрізняється представленням об'єкта як множини рухомих фрагментів, способом побудови траєкторії об'єкта на основі траєкторій його фрагментів і знаходженням відповідностей між об'єктами і їх фрагментами, що дозволяє:

- відстежувати частково перекриті об'єкти;

- сегментувати групу об'єктів, зображення яких перетинаються, на окремі об'єкти, на основі траєкторій фрагментів об'єктів;

- надавати результат як у реальному часі з малою затримкою, так і ретроспективно уточнений результат з будь-якою заданою затримкою.

Експериментально досліджено якість відстежування частково перекритих об'єктів за методом DSOFT на тестових відеозаписах руху футболістів VS-PETS'2003, а також пішоходів і автомобілів на вулиці VS-PETS'2000. При відстежуванні у реальному часі футболістів на типовому відео футбольного матчу при долі перекриття до 60% проаналізовано без помилок 97.6% ситуацій; при долі перекриття від 61% до 100% проаналізовано без помилок 52% ситуацій. Ретроспективне уточнення результату дозволило при долі перекриття від 61% до 100% проаналізовані без помилок 60% ситуацій.

2. Розроблені модифікації методів пошуку фрагментів зображення у кадрі, заснованих на попіксельному порівнянні кадру з шаблоном (зокрема, пошук повним перебором та швидкі алгоритми Diamond Search і Threee-Step Search), які дозволяють оцінювати упевненість у правильності пошуку.

Запропоновані модифікації дозволили знизити середнє число кадрів, в яких фрагменти зображення футболістів відстежуються невірно, в 1.2-2 рази.

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

При використанні сумісно з моделлю фону з незмінною інтенсивністю, що оновляється зваженим підсумовуванням з кадром, метод дозволив знизити кількість помилок першого роду при виділенні пікселів пішоходів на людній вулиці в 2.1-2.6 раз. При цьому швидкодія знизилася в 2.5 рази і залишилася достатньою для аналізу відео у реальному часі.

4. Розроблене та досліджене відображення методу DSOFT на паралельні комп'ютерні системи з архітектурами MIMD UMA і кластер, яке використовує асинхронний обмін даними та асиметричне статичне балансування навантаження. Визначено оптимальне балансування навантаження для систем з різними характеристиками. Доцільно виконувати аналіз одного відеопотоку за методом DSOFT у реальному часі на системі типу UMA з числом процесорів від 2 до 4.

Практично отримане прискорення 1.57 раз при аналізі типового відео футбольного матчу на двох процесорах і теоретична оцінка прискорення 2.6 раз для чотирипроцесорних систем.

5. Розроблені та досліджені нові ефективні апаратно-орієнтовані алгоритми пошуку в кадрі фрагментів зображення довільної форми для багатопотокових графічних процесорів з архітектурою CUDA, включаючи пошук повним перебором позицій шаблону та алгоритм швидкого пошуку, заснований на попіксельному порівнянні кадру з шаблоном, які можуть бути використані для прискорення відстежування за методом DSOFT. Отримані оцінки часової складності розроблених паралельних алгоритмів.

Практично на GPU GeForce GTS 250 E-Green досягнуто прискорення до 40 разів в порівнянні з одним ядром CPU Athlon 64 X2 5400 для пошуку повним перебором і до 11 разів для швидкого алгоритму пошуку.

6. Результати дисертаційного дослідження використано у науково-виробничому підприємстві ТОВ “АМІ” (м. Донецьк) при розробці цифрової системи безпеки для реалізації автоматичного виявлення підозрілих рухомих об'єктів у відео; в науково-дослідницький темі Донецького національного технічного університету “Розвиток теорії синтезу і розподіленого моделювання високопродуктивних проблемно-орієнтованих обчислювальних систем з програмованими НВІС”; у навчальному процесі при читанні лекцій та в науково-дослідних роботах студентів і магістрантів.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Ладиженський Ю.В. Відстежування об'єктів у відеопотоці на основі відстежування переміщення фрагментів об'єктів [Текст] / Ю.В. Ладиженський, А.О. Середа // Наукові праці Донецького національного технічного університету. Серія: “Обчислювальна техніка та автоматизація”. - Донецьк: ДонНТУ, 2009. - № 17 (148). - С. 127-134.

2. Ладиженський Ю.В. Моделирование статичного фона в видеопотоке с большим числом движущихся объектов [Текст] // Ю.В. Ладиженський, А.О. Середа // Наукові праці Донецького національного технічного університету. Серія: “Обчислювальна техніка та автоматизація”. - Донецьк: ДонНТУ, 2009. - № 16 (147). - С. 152-160.

3. Ладиженський Ю.В. Організація паралельних обчислень при відстежуванні об'єктів у відеопотоці [Текст] / Ю.В. Ладиженський, А.О. Середа // Наукові праці Донецького національного технічного університету. Серія: “Інформатика, кібернетика та обчислювальна техніка”. - Донецьк: ДонНТУ, 2010. - № 11 (164). - С. 47-55.

4. Ладиженський Ю.В. Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA [Текст] / Ю.В. Ладиженський, А.О. Середа // Научно-теоретический журнал "Искусственный интеллект". - 2010. - №4 (2010) . - С. 236-244.

5. Ладыженский Ю.В. Специализированные параллельные процессоры для отслеживания перемещений объектов в видеопотоке [Текст] / Ю.В. Ладыженский, А.А. Середа // Моделирование и компьютерная графика: II междунар. науч.-тех. конф., 10-12 жовтня 2007 р.: тезисы докл. - Донецьк, 2007. - С. 322-325.

6. Середа А.А. Отслеживание объектов в видеопотоке как совокупности движущихся объектов [Текст] / А.А. Середа, Ю.В. Ладыженский // Інформатика та комп'ютерні технології: IV міжнар. науч. конф., 25-27 листопада 2008 р.: тези доп. - Донецьк, 2008. - С. 254-256.

7. Ладыженский Ю.В. Моделирование статичного фона в видеопотоке с большим числом движущихся объектов [Текст] / Ю.В. Ладыженский, А.А. Середа // Комп'ютерний моніторинг та інформаційні технології: V міжнар. наук.-техн. конф. студентів, аспірантів та молодих вчених, 11-15 травня 2009 р.: тези доп. - Донецьк, 2009. - С. 234-235.

8. Середа А.О. Моделювання статичного фону у відеопотоці з великим числом рухомих об'єктів [Текст] / А.О. Середа, Ю.В. Ладиженський // Сучасна інформаційна Україна: інформатика, економіка, філософія: IІІ міжнар. наук.-техн. конф. молодих учених, аспірантів, студентів, 14-15 травня 2009 р.: тези доп. - Донецьк, 2009. - С. 348-351.

9. Середа А.А. Параллельная вычислительная система для отслеживания объектов в видеопотоке [Текст] / А.А. Середа, Ю.В. Ладыженский // Моделирование и компьютерная графика: II междунар. науч.-тех. конф., 10-12 жовтня 2009 р.: тезисы докл. - Донецьк, 2009. - С. 117-121.

10. Ладиженський Ю.В. Швидкі алгоритми пошуку фрагментів зображень довільної форми за шаблоном на паралельній архітектурі CUDA [Текст] / Ю.В. Ладиженський, А.О. Середа // Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій: II междунар. наук.-практ. конф., 22-24 вересня 2010 р.: тези доп. - Запоріжжя, 2010. - С. 177-178.

У роботах, які опубліковані в співавторстві, дисертантові належать:

[1, 6] - розробка і реалізація алгоритму відстежування об'єктів, проведення експериментів;

[2, 7, 8] - обґрунтування оцінок ймовірності, розробка і реалізація алгоритму створення і підтримки множини моделей фону у області кадру, проведення експериментів;

[3, 9] - оптимізація порядку виконання операцій, оцінка швидкодії і оптимального балансування навантаження, реалізація алгоритмів, проведення експериментів;

[4, 10] - розробка і реалізація паралельних алгоритмів, оцінка часової складності, проведення експериментів;

[5] - аналіз спеціалізованих обчислювальних структур для пошуку фрагмента зображення довільної форми в кадрі.

АНОТАЦІЯ

Середа А.А. Метод відстежування об'єктів у відеопотоці та його реалізація на паралельних комп'ютерних системах. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - Комп'ютерні системи і компоненти. - ДВНЗ “Донецький національний технічний університет”, Донецьк, 2011.

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

Розроблено метод автоматичного виявлення і відстежування об'єктів у відеопотоці “DSOFT”, заснований на представленні об'єкту як множини рухомих фрагментів, заданих шаблонами. Фрагменти зі схожими траєкторіями об'єднуються в об'єкти. Траєкторії об'єктів будуються на основі траєкторій їх фрагментів. Це дозволяє відстежувати об'єкти, частково перекриті іншими об'єктами; сегментувати групи об'єктів, зображення яких перетинаються, на окремі об'єкти; надавати результат як у реальному часі, так і ретроспективно уточнений результат із заданою затримкою.

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

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

Розроблено відображення методу DSOFT на паралельні комп'ютерні системи з архітектурами MIMD UMA і кластер. Одержана оцінка продуктивності і визначене оптимальне балансування навантаження для систем з різними характеристиками.

Розроблені ефективні апаратно-орієнтовані алгоритми пошуку в кадрі фрагмента зображення довільної форми на багатопотокових графічних процесорах із архітектурою CUDA, засновані на попіксельному порівнянні кадра з шаблоном.

Ключові слова: відстежування об'єктів, відео, шаблон, перекриття, віднімання фону, паралельні обчислення, MIMD, CUDA

АННОТАЦИЯ

Середа А.А. Метод отслеживания объектов в видеопотоке и его реализация на параллельных компьютерных системах. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты. - ГВУЗ “Донецкий национальный технический университет”, Донецк, 2011.

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

Разработан метод автоматического выявления и отслеживания объектов в видеопотоке “DSOFT”, основанный на представлении объекта как множества движущихся фрагментов, заданных шаблонами. Близко расположенные фрагменты с похожими траекториями объединяются в объекты. Траектории объектов строятся по траекториям их фрагментов. При обработке новых кадров могут пересматриваться ранее найденные соответствия между фрагментами и объектами, а также координаты объектов. Это позволяет отслеживать объекты, частично перекрытые другими объектами; сегментировать группы движущихся объектов, изображения которых пересекаются, на отдельные объекты; предоставлять результат как в реальном времени, так и ретроспективно уточненный результат с заданной задержкой. При отслеживании в реальном времени футболистов на типичном видео футбольного матча при степени перекрытия объектов до 60% проанализировано без ошибок 97.6% ситуаций; при степени перекрытия от 61% до 100% проанализировано без ошибок 52% ситуаций. С ретроспективным уточнением результата при степени перекрытия от 61% до 100% проанализировано без ошибок 60% ситуаций.

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

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

Разработано отображение метода DSOFT на параллельные компьютерные системы с архитектурами MIMD UMA и кластер. Используется статическая ассиметричная балансировка нагрузки и асинхронный обмен данными. Получена аналитическая и экспериментальная оценка производительности. Определена оптимальная балансировка нагрузки для систем с различными характеристиками. Практически получено ускорение 1.57 раз при анализе типичного видео футбольного матча на двух процессорах и теоретическая оценка ускорении 2.6 раз для четырехпроцессорных систем.

Разработаны эффективные аппаратно-ориентированные алгоритмы поиска в кадре фрагмента изображения произвольной формы для многопоточных графических процессоров с архитектурой CUDA, основанные на попиксельном сравнении кадра с шаблоном, включая отображение на CUDA поиска полным перебором позиций фрагмента и быстрый алгоритм, использующий сравнение фрагмента с кадром в узлах сетки и уточнение решения полным перебором в окрестностях выбранных узлов. Практически на GPU GeForce GTS 250 E-Green по сравнению с одним ядром CPU Athlon X2 5400 получено ускорение поиска фрагментов полным перебором до 40 раз и поиска быстрым алгоритмом до 11 раз.

Ключевые слова: отслеживание объектов, видео, шаблон, перекрытие, вычитание фона, параллельные вычисления, MIMD, CUDA

ANNOTATION

Sereda A.A. Method of object tracking in video and its implementation on parallel computer systems. - Manuscript.

Thesis in search of Ph.D. degree on speciality 05.13.05 - Computing systems and components. - SHEE “Donetsk National Technical University”, Donetsk, 2011.

The thesis is devoted to developing method for detecting and tracking of objects in video able to track partially occluded objects, as well as its implementation on parallel computer systems.

The method DSOFT (Dynamic Set of Fragments Tracking) for automatic detection and tracking of objects in video is developed. The method is based on a representation of object as a set of moving fragments presented by templates. Fragments with similar trajectories are merged into objects. Trajectories of objects are constructed from trajectories of fragments. This allows tracking of partially occluded objects, segmenting of a group of objects with overlapped images into individual objects, providing results in real time and retrospectively refined results with a specified lag.

The modifications of block matching algorithms which allow estimation of search result confidence are proposed.

New method to reduce errors in initialization and updating of background model caused by presence of objects in frames is proposed. The method is based on creating and supporting of a set of different background models in each area of frame and estimating of models adequacy probabilities.

The implementation of the DSOFT method on parallel computing architectures MIMD UMA and cluster is proposed. Estimations of performance and optimal load balancing for systems with different characteristics are obtained.

New efficient hardware-oriented algorithms for search of arbitrary shape image fragments in a frame on CUDA architecture, based on per-pixel comparison of frame and template, are developed.

...