Page 1

Наукові праці ДонНТУ

Випуск 148

127

УДК 004.932.2

Ю.В. Ладиженський, А.О. Середа

Донецький національний технічний університет, м.Донецьк

кафедра прикладної математики і інформатики

E-mail: ly@cs.donntu.ru, aas11@bk.ru

ВІДСТЕЖУВАННЯ ОБ'ЄКТІВ У ВІДЕОПОТОЦІ

НА ОСНОВІ ВІДСТЕЖУВАННЯ ПЕРЕМІЩЕННЯ ФРАГМЕНТІВ ОБ'ЄКТІВ

Abstract

Ladyzhenskyy Y., Sereda A. Object tracking in video stream based on a tracking of object frag-

ments. The new method and algorithm for object tracing was proposed. An object is considered as

a set of its moving fragments. It allows a reliable tracking of partially occluded objects. The soft-

ware realization of proposed algorithm with real-time performance was created.

Keywords: object tracking, object fragment, partial occlusion, trajectory, background subtraction.

Анотація

Ладиженський Ю.В., Середа А.О. Відстежування об'єктів у відеопотоці на основі відстежу-

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

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

траєкторіям фрагментів. Це дозволяє надійно відстежувати частково перекриті об'єкти. Ство-

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

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

днімання фону.

Аннотация

Ладыженский Ю.В., Середа А.А. Отслеживание объектов в видеопотоке на основе от-

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

отслеживания объектов. Объект рассматривается как множество движущихся фрагмен-

тов. Траектория объекта строится по траекториям фрагментов. Это позволяет надежно

отслеживать частично перекрытые объекты. Создана программная реализация алгоритма

для отслеживания объектов в реальном времени.

Ключевые слова: отслеживание объектов, фрагмент объекта, частичное перекрытие,

траектория, вычитание фона.

Вступ

Необхідність відстежування об'єктів у відеопотоці виникає в багатьох областях, наприклад, у

системах безпеки, системах контролю теологічних процесів, при організації людино-машинного ін-

терфейсу, при створенні систем автоматизованого аналізу спортивних змагань. Під відстежуванням

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

Основними проблемами при відстежуванні руху множини об'єктів у відеопотоці є надійне

відстежування об'єктів, частково або повністю перекритих іншими об'єктами; об'єктів, форма яких

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

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

1) Не виконувати відстежування об'єкту безпосередньо під час перекриття, а запам'ятати

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

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

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

Наукові праці ДонНТУ

Випуск 148

128

2) Виконувати відстежування переміщення об'єктів при їх частковому перекритті.

Оскільки ціле зображення об'єкту неможливо відстежити, необхідно відстежувати перемі-

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

чити меншу кількість помилок при відстежуванні. При цьому не виключається використання

додатково методів, використовуваних в першому підході.

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

відстежуванню. Цей вибір має вирішальне значення для побудови алгоритму відстежування.

Деякі з існуючих підходів:

1) Відстежування однорідних регіонів. У [1] виконується одночасне відстежування і

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

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

2) Відстежування переміщень точкових особливостей. У роботі [2] виконується від-

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

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

ну зображень об'єктів.

3) Відстежування контурів. У роботі [3] виявляються випадки перекриття об'єктів і

робиться спроба відтворити невидимі частини контурів об'єктів.

4) Відстежування частин зображення цілого об'єкту, не перекритих іншими об'-

єктами. У роботі [4] виконується відстежування переміщення зображення всього об'-

єкту. Для цього використовується модель, що постійно оновлюється. У разі перетину

об'єктів створюється маска, що показує, які частини об'єкту перекриті іншими об'єк-

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

У якості відстежуваних частин зображень об'єктів можуть бути використані фрагмен-

ти зображення довільної форми.

Розроблені алгоритми відстежування переміщення фрагментів зображення, стійкі до

викривлень фрагментів [5], які можуть забезпечити відстежування з малим числом помилок і

збоїв. При кодуванні відео, зокрема, за стандартами MPEG-2 і MPEG-4, використовується

відстежування переміщення прямокутних фрагментів зображення. Розроблені швидкі алго-

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

фрагментів [6], які можуть бути модифіковані і використані при відстежуванні переміщення

об'єктів, що може забезпечити високу швидкодію.

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

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

Загальний опис методу

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

мент є областю кадру довільного розміру і форми, що містить частину об'єкту або цілий об'-

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

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

2) Побудова траєкторій руху об'єктів на основі результатів відстежування переміщен-

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

нуються в об'єкти.

Запропонований підхід дозволяє:

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

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

єкторії цього фрагмента можливо відтворити траєкторію всього об'єкту.

2) Виконувати відстежування множини об'єктів, які протягом всього часу свого існу-

вання є частково перекритими і утворюють одну “пляму”. Таку група об'єктів може бути се-

гментовано на окремі об'єкти за траєкторіями руху їх частин.

Наукові праці ДонНТУ

Випуск 148

129

3) Виконувати відстежування об'єктів, що сильно змінюють свою форму. Для цього достат-

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

стежена.

4) Створити ефективну реалізацію на багатопроцесорних обчислювальних системах.

5) Створити ефективну апаратну реалізацію, яка може забезпечити високу швидкодію.

Знаходження об'єктів і їх координат на основі траєкторій фрагментів можна виконати один

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

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

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

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

динати за останні window

T

секунд. З кожним новим кадром відбувається отримання нових координат

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

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

Дії, що відбуваються при аналізі одного кадру (загальний крок алгоритму), представлені на

рис. 1. Овалами показані дані, прямокутниками — виконувані дії, стрілками — потоки даних.

Рисунок 1 — Загальний крок алгоритму відстежування об'єктів

Віднімання фону і моделювання фону

Віднімання фону, побудова і оновлення моделі фону є поширеним підходом до виді-

лення рухомих об'єктів у відеопотоці [1]. Це дозволяє виділити в кожному кадрі пікселі, які

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

Пошук і розпізнавання об'єктів

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

об'єкти довільного виду. Тому пошук і розпізнавання об'єктів в кадрах не є обов'язковим. Для угру-

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

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

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

Визначення фрагмента і об'єкту

Відстежуваний фрагмент kf характеризується наступними властивостями:

1)

k

Width ,

k

Height — ширина і висота прямокутника, що містить фрагмент.

Віднімання

фону

Дані для

моменту часу

T-1

Пікселі

об'єктів

Оновлення

моделі

фону

Відстежування

фрагментів

Створення нових

відстежуваних

фрагментів

Встановлення

відповідності

між фрагмента-

ми і об'єктами

Пошук і розпі-

знавання об'-

єктів

Дані для

моменту часу T

Корекція поми-

лок на рівні об'-

єктів

Модель

фону

Список

фрагментів

Список

об'єктів

Кадр

Модель

фону

Список

фрагментів

Список

об'єктів

Наукові праці ДонНТУ

Випуск 148

130

2) kI — матриця розміром

k

k Width

Height ×

, що містить пікселі фрагмента. Значення

пікселів, що не відносяться до фрагмента, можуть бути довільними.

3) k

M — матриця розміром

k

k

Width

Height ×

, яка показує, які пікселі з kI і з якою

впевненістю відносяться до даного фрагменту,

[ ]1,0

∈

kij

m

.

4) [

]max

min

, k

k

T

T

— проміжок часу, в якому відомі координати даного фрагмента, тобто

його час існування.

5)

( )

tXk

,

( )

tYk

— координати лівого верхнього кута фрагмента у момент часу

[

]max

min

, k

k

T

Tt

∈

.

6) k

Id — дорівнює унікальному ідентифікатору об'єкту, до якого відноситься даний фраг-

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

Різні фрагменти можуть перетинатися. Більшість пікселів об'єктів відносяться як мі-

німум до одного фрагмента.

В процесі відстежування відбувається оновлення матриць I і M .

Представлення за допомогою матриць I і M аналогічно використовуваному в [4], але

множина фрагментів дозволяє краще відстежувати об'єкти із змінною формою, ніж викорис-

товувана в [4] одна модель для всього об'єкту.

Об'єкт k

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

1) [

]max

min

,

k

k

OT

OT

— проміжок часу існування об'єкту.

2)

( )t

OXk

,

( )t

OYk

— координати центру об'єкту у момент часу

[

]max

min

,

k

k

OT

OT

t ∈

.

3)

k

OId — унікальний ідентифікатор даного об'єкту.

Позначимо через

( )o

Fragments

множину всіх фрагментів, що відносяться до

об'єкту o . Значущістю об'єкту назвемо сумарний час існування всіх його фрагментів. Нехай

( )

(

) (

)

(

)min

min

max

max

,

max

,

min,0

max

,

j

i

j

i

j

i

T

T

T

T

ff

CommonTime

−

=

Позначимо через

( )

tf

Scale ,

відношення розміру зображення об'єкту в пікселях до розміру того ж самого об'єкту в метрах

у точці кадру, в якій знаходиться фрагмент f у момент часу t . Аналогічно визначимо

CommonTime і Scale для об'єктів.

Відстежування переміщення фрагментів

Для відстежування переміщення фрагментів можна застосовувати швидкі алгоритми

пошуку прямокутних фрагментів, розроблені для кодування відео [6]. Відстежування пере-

міщень фрагментів при відстежуванні об'єктів має дві особливості:

1) Фрагмент може мати довільну форму.

2) Необхідно оцінювати надійність відстежування (ймовірність того, що відстеження

переміщення даного фрагменту відбулося вірно).

Нехай V — область пошуку фрагмента kf у кадрі A.

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

фрагментом kf і областю кадру A за формулою

(

)

∑

∑

−

=

−

=

+

+

=

1

0

1

0

,,

,

,

),(

k

k

Width

dx

Height

dy

dydxk

dyydxx i

aF

yxD

і

визначають координати фрагменту кадру A, найбільш схожого на фрагмент kf

як

(

)

( )

( )

yxD

y

x

Vyx

,

min

arg

,

,

min

min

∈

=

, де F — деяка функція (наприклад, модуль різниці яскравос-

тей). Такі алгоритми можуть бути легко модифіковані для відстежування фрагментів довіль-

ної форми:

(

)

∑

∑

−

=

−

=

+

+

=

1

0

1

0

,,

,,

,

,

),(

k

k

Width

dx

Height

dy

dy

dxk

dy

dxk

dy

ydxx

m

i

aF

yxD

.

Наукові праці ДонНТУ

Випуск 148

131

Для визначення надійності відстежування фрагмента використовуються наступні критерії:

1) Вибраний фрагмент повинен бути достатньо схожий на фрагмент

kf :

(

) max

min

min,

D

y

xD

≤

.

2) Усі інші фрагменти з області пошуку V повинні бути достатньо несхожі на шука-

ний фрагмент kf :

( )

( ) (

)

( )

yxD

D

r

y

xyxVyx

,

min

min

min ,

,,,

,

min

≥

∈

=

,

(

)

min

min

min

, y

xsD

D

≥

(1)

де max

D

, r і s — константи.

Назвемо коефіцієнтом упевненості у відстеженні величину

(

)

(

)

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

−

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

−

=

1

,

,1

,

,1

min,0

max

min

min

min

2

min

min

max

1

y

xsD

D

k

y

xD

D

k

Kconf

,

(2)

де

0

,21 >

kk

— константи. Фрагмент вважається відстеженим, якщо

0

>

conf

K

.

Для перевірки умови (1) необхідно виконати порівняння всіх фрагментів з області

пошуку V з фрагментом kf . При цьому відбуваються практично ті ж самі дії, що і при по-

шуку фрагмента методом повного перебору всіх його можливих положень, що має велику

часову складність. Доцільно виконувати перевірку (1) один раз в декілька кадрів.

Передбачення найбільш вірогідного положення фрагмента і області, в якій він може

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

належить, а також заданих максимальної швидкості та прискорення.

Відстежування фрагмента припиняється, якщо його не вдалося знайти в fragment

T

по-

слідовних кадрів. Якщо фрагмент був втрачений, а потім знайдений, його невідомі координа-

ти інтерполюються по відомих.

Створення нових відстежуваних фрагментів

Один раз в декілька кадрів виконується пошук всіх пікселів, які не відносяться ні до

фону, ні до наявних фрагментів. Створюються нові відстежувані фрагменти, що покривають

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

рів і форми створюваних фрагментів вимагає подальших досліджень.

Встановлення відповідності між фрагментами і об'єктами

Алгоритм встановлення відповідності між фрагментами і об'єктами складається я з

наступних кроків, які дозволяють обробляти всі ситуації, пов'язані з виникненням, зникнен-

ням, злиттям і розділенням видимих об'єктів:

1) Відділення фрагментів від об'єктів (включаючи розділення об'єктів), якщо їх рух

не узгоджений.

2) Віднесення фрагментів до існуючих об'єктів, з якими їх рух є узгодженим.

3) Злиття об'єктів, рух яких є узгодженим.

4) Видалення об'єктів, у яких не залишилося відстежуваних фрагментів.

5) Створення нових об'єктів із фрагментів, що не відносяться до існуючих об'єктів.

Критерії узгодженості руху

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

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

Нехай

if

і

jf

— два фрагменти, причому

(

)min

min

min

,

max

j

i

T

T

T

=

,

(

)max

max

max

,

min

j

i

T

T

T

=

і

min

max

T

T

≥

. Нехай

(

)

( )

( )

(

)

tf

Scale

tf

Scale

tjiCS

j

i

,

,,

min

,, 2 =

.

Запропоновано наступні критерії узгодженості руху фрагментів if і jf :

Впродовж всього руху фрагменти повинні знаходитися достатньо близько:

[

]

max

min ,T

Tt

∈

∀

:

Наукові праці ДонНТУ

Випуск 148

132

( )

( )

(

)

( ) ( )

(

)

(

)

tjiCS

idth

MaxObjectW

tXtX

Width

tX

Width

tX

j

i

j

j

i

i

,,

,

min

,

max

⋅

≤

−

+

+

,

( )

( )

(

)

( ) ( )

(

)

(

)

tjiCS

idth

MaxObjectW

tXtX

Width

tX

Width

tX

j

i

j

j

i

i

,,

,

min

,

max

⋅

≤

−

+

+

.

1) Взаємне розташування фрагментів не повинне сильно змінюватися:

[

]:

,

,

max

min

21

T

T

tt ∈

∀

( )

( )

(

)

( )

( )

(

)

( )

( )

(

)

( )

( )

(

)

1

2

2

2

2

2

2

1

1

1

1

1

1

,,

,

,,

,

,,

,

,,

D

tjiCS

tY

tY

tjiCS

tX

tX

tjiCS

tYtY

tjiCS

tX

tX

j

i

j

i

j

i

j

i

≤

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

−

−

⎟

⎟

⎠

⎞

⎜

⎜

⎝

⎛

−

−

.

2) Швидкість

фрагментів

не

повинна

сильно

відрізнятися:

[

]:'

, max

min

t

T

Tt

−

∈

∀

( )

( ) ( ) ( )

(

) ( )

( ) ( ) ( )

(

)

(

)

tjiCS

D

tYttYtXttXtYttYtXttXj

j

j

j

i

i

i

i

,,

'

,

'

,

'

,

'

2 ⋅

≤

−

+

−

+

−

+

−

+

, де 't — константа.

Позначимо через

( )j

iff

Matched , виконання трьох приведених критеріїв для фрагментів if

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

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

D і 2

D .

Всі запропоновані критерії є обов'язковими, але не достатніми.

Побудова траєкторії руху об'єкту

Траєкторія руху будується на базі траєкторій фрагментів, що відносяться до об'єкту, а

також положень об'єкту в окремих кадрах, де він був розпізнаний.

Введемо наступні позначення:

( )

( )

( ) ( ) ( )

(

) [

]

( ) [

]

⎪

⎩

⎪

⎨

⎧

+

∉

+

∈

−

−

−

−

=

max

min

max

min

,1

,0,0

,1

,1

,1

,

i

i

i

i

i

i

i

i

i

T

Tt

T

Tt

tYtY

tXtX

tfnt

Displaceme

;

( )

tonts

GoodFragme

,

—

підмножина

фрагментів

з

( )

( ) ( )

{

}

0,0

,

&

:

≠

∈

tfnt

Displaceme

o

Fragments

ff

i

i

i

, що мають високі коефіцієнти упевненості

у відстежуванні у момент часу t (2) і великий час існування;

(

)

( )

( )

∑

∑

=

∈

=

2

1

,

21

,

,,

t

tt

tonts

GoodFragme

f

i

i

tfnt

Displaceme

ttont

Displaceme

.

Нехай невідомі координати об'єкту io у момент часу t .

1) Якщо відомі координати об'єкту io у момент часу tt

<

1

, але не відомі в подальші

моменти, то

( )

( )

(

)

( )

( )

(

)

(

)t

tont

Displaceme

tOY

t

OX

tOYt

OX

i

i

i

i

i

,1,

,

,

1

1

1

+

+

=

.

2) Якщо відомі координати об'єкту io у момент часу tt>

2

, але не відомі в попередні

моменти, то

( )

( )

(

)

( )

( )

(

)

(

)2

2

2

,1,

,

,

t

tont

Displaceme

tOY

t

OX

tOYt

OX

i

i

i

i

i

+

−

=

.

3) Якщо відомі координати об'єкту i

o у моменти часу tt

<

1

і tt<

2

то

( ) ( )

(

)

( ) ( )

(

)

(

)

( ) ( )

(

)

(

)

(

)2

1

2

2

1

2

1

1

1

1

1

2

2

,1

,

,

,1

,

,

,

t

tont

Displaceme

t

OY

t

OX

tt

tt

t

tont

Displaceme

t

OY

t

OX

tt

tt

t

OYt

OX

i

i

i

i

i

i

i

i

+

−

−

−

+

+

+

−

−

=

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

ного будь-якого моменту із прямокутника, що обмежує фрагменти даного об'єкту, а для реш-

ти моментів часу визначаються згідно з пунктами 1 і 2.

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

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

Відділення фрагментів від об'єкту

Якщо для деякого об'єкту o існує такий фрагмент

( )o

Fragments

f ∈

, що

( )

of

Matched ,

¬

,

то фрагмент f відділяється від об'єкту o і перестає відноситься до жодного об'єкту.

Якщо в деякий момент часу від об'єкту відділилася група фрагментів, відношення сумарної

площі яких до сумарної площі фрагментів, що залишилися, перевищує порогове значення, то вони

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

Наукові праці ДонНТУ

Випуск 148

133

Віднесення фрагмента до існуючого об'єкту

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

1) Якщо існують такі фрагмент if і об'єкт o , що

None

Idi =

,

(

) min

,Tof

CommonTime i

≥

і

(

)

of

Matched i, , то відбувається віднесення фрагмента if до об'єкту o . min

T

— порогове значення.

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

до об'єкту з максимальною значущістю.

2) При успішному розпізнаванні об'єкту до нього відносяться всі фрагменти, які перетина-

ються з його зображенням і не перетинаються із зображеннями інших об'єктів.

Злиття двох об'єктів

Два об'єкти 1

o і 2

o повинні бути об'єднані в один коли виконуються наступні умови:

1) Інтервали часу їх існування перетинаються.

2) Якщо

o

—

об'єкт,

утворений

з

множини

фрагментів

( )

( )2

1

o

Fragments

o

Fragments

F

∪

=

то Ff

∈

∀

виконується

( )

of

Matched , .

Траєкторія об'єкту o обчислюється на основі траєкторій фрагментів так само, як і для

будь-якого іншого об'єкту.

Створення нового об'єкту

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

об'єктів, в двох випадках:

1) Якщо

None

Idi =

і

threshold

i

i

T

T

T

≥

− min

max

, то на основі фрагмента if створюється

новий об'єкт. Після цього робиться спроба віднести до нового об'єкту всі інші фрагменти, що

не відносяться до об'єктів.

2) Якщо в деякому місці кадру було знайдене і розпізнане зображення об'єкту задано-

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

єктів, то з цих фрагментів створюється новий об'єкт.

Корекція помилок на рівні об'єктів

Корекція помилок на рівні об'єктів може містити ряд правил, що використовують фо-

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

редніх етапах. Реалізовано 2 правила:

1) Якщо деякий об'єкт не вдалося відстежити, а поряд з місцем його останнього розташу-

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

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

2) Якщо деякий об'єкт, що має вік не менше del

t , в кожному кадрі знаходився на від-

стані не більше ніж del

r від об'єкту, значущість якого перевищує значущість даного об'єкту в

del

k

раз, то даний об'єкт видаляється. Це правило дозволяє видаляти помилкові об'єкти, ви-

кликані помилками при відстежуванні фрагментів.

Практичні результати

Описаний алгоритм було реалізовано програмно.

Експерименти показали, що розроблений алгоритм може відстежувати об'єкти в умо-

вах часткового перекриття. На рис. 2 приведені фрагменти трьох проаналізованих кадрів з

відеозапису футбольного матчу, що містить таки ситуації.

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

Наукові праці ДонНТУ

Випуск 148

134

Середній час повного аналізу одного кадру відеозапису дозволом 670x367 пік-

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

Athlon 64 X2 5400+ із задіяним одним ядром, за умови, що в кожному другому кадрі

виконується тільки відстежування фрагментів, дорівнює 31 мс. З них в середньому 18

мс витрачається на відстежування фрагментів і 10 мс витрачається на пошук і розпі-

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

реальному часі.

Висновки

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

стежувати переміщення їх частин. У якості відстежуваної частини об'єкту може бути вико-

ристаний фрагмент зображення довільної форми.

Одержані наступні основні результати:

1) Розроблено новий метод і алгоритм відстежування об'єктів. Його головне достоїнс-

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

крема в умовах постійного перекриття.

2) Розроблено програмну модель запропонованого алгоритму.

3) Показано, що запропонований алгоритм має достатню швидкодію для відстежу-

вання об'єктів у реальному часі на персональному комп'ютері.

Однією з сфер застосування розробленого алгоритму є автоматизований аналіз спор-

тивних змагань.

Запропонований алгоритм може бути ефективно реалізований на багатопроцесорних

комп'ютерах. Також можливе застосування спеціалізованих процесорів, розроблених для ко-

дування відео.

Література

1. A. Cavallaro, O. Steiger, T. Ebrahimi. Tracking video objects in cluttered background. IEEE

Transactions on Circuits and Systems for Video Technology, Vol. 15, Issue 4, April 2005.

URL: http://lts1pc19.epfl.ch/repository/Cavallaro2004_865.pdf

2. P. S. Kumar, P. Guha A. Mukerjee. Colour and Feature Based Multiple Object Tracking Under

Heavy

Occlusions.

Computer

Vision

Group,

IIT

Kanpur.URL:

http://www.cse.iitk.ac.in/research/pdfs/ddmtech/sateesh-guha-mukerjee-icapr07_colour-feature-

multi-obj-tracking-occlusion.pdf

3. Alper Yilmaz, Xin Li, Mubarak Shah. Contour-Based Object Tracking with Occlusion Han-

dling in Video Acquired Using Mobile Cameras. IEEE Transactions on Pattern Analysis and

Machine Intelligence. Volume 26, Issue 11 (November 2004)

URL: http://www.cs.ucf.edu/~vision/papers/yilmaz_pami_2004.pdf

4. R. Cucchiara, C. Grana, G. Tardini. Track-based and object-based occlusion for people tracking

refinement in indoor surveillance. Proceedings of the ACM 2nd international workshop on Vid-

eo surveillance & sensor networks 2004, New York, NY, USA, October 15, 2004.

URL: http://doi.acm.org/10.1145/1026799.1026814

5. D. Comaniciu, V, Ramesh, P. Meer. Kernel-Based Object Tracking. IEEE Transactions on Pat-

tern Analysis and Machine Intelligence Volume 25, Issue 5 (May 2003).

URL: http://portal.acm.org/citation.cfm?id=776799&dl=

6. Adaptive Motion Estimation Processor for Autonomous Video Devices. T. Dias, S. Momcilovic, N.

Roma, L. Sousa. EURASIP Journal on Embedded Systems, vol. 2007, Article ID 57234, 10 pages,

2007. URL: http://www.hindawi.com/GetArticle.aspx?doi=10.1155/2007/57234

Здано в редакцію:

Рекомендовано до друку:

12.03.2009р.

д.т.н, проф. Башков Є.О.