POLITECHNIKA WROCŠAWSKA

WYDZIAŠ ELEKTRONIKI

Kierunek:

Automatyka i Robotyka (AiR)

Specjalno±¢:

Robotyka (ARR)

PRACA DYPLOMOWA

MAGISTERSKA

Lokalizacja i klasykacja obiektów

poruszaj¡cych si¦ w znany sposób

Localization and classication of objects

moving in a known way

Autor:

Maciej Sªomka

Prowadz¡cy prac¦:

dr in». Marek Wnuk, I-6

Opiekun:

dr in». Marek Wnuk, I-6

Ocena pracy:

WROCŠAW 2007

Rozdziaª 1

Wst¦p

1.1 Ogólna koncepcja

Rozwój technologiczny sprawiª, »e w ostatnich latach coraz ±mielej my±li si¦ o budowie

tak zwanych robotów spoªecznych. Maj¡ to by¢ inteligentne maszyny realizuj¡ce zadania

w otoczeniu ludzi. Bardzo wa»n¡ cech¡ tych robotów b¦dzie mo»liwo±¢ skutecznego loka-

lizowania ludzi, a tak»e (mi¦dzy innymi ze wzgl¦dów spoªecznych) bardziej wyranowane

zadania, takie jak rozpoznawanie nastroju czªowieka na podstawie wygl¡du lub mimiki

jego twarzy.

Wszystko wskazuje na to, »e zadania te b¦d¡ realizowane przez system wizyjny robota.

Istotne jest mo»liwie szybkie dziaªanie obsªuguj¡cych go algorytmów, gdy» robot musi

dziaªa¢ w czasie rzeczywistym w szybkozmiennym ±rodowisku. Z powodu dziaªania w

otoczeniu ludzi, »adne pomyªki ani opó¹nienia nie s¡ wskazane.

Znaczna cz¦±¢ algorytmów sªu»¡cych do lokalizowania oraz klasykowania obiektów wi-

docznych na obrazach opiera si¦ na tzw. dopasowywaniu wzorca (ang. template matching

lub pattern matching). Polegaj¡ one na wyszukiwaniu na obrazie fragmentów podobnych

ksztaªtem do wzorca (lub jednego z wzorców) zapisanego w przygotowanej wcze±niej bazie

danych. Takie podej±cie wymaga sporych nakªadów obliczeniowych. Niezb¦dne jest stwo-

rzenie wspomnianej bazy zawieraj¡cej wzorce przedstawiaj¡ce interesuj¡ce nas obiekty.

W celu znalezienia ich na danym obrazie, poszukuje si¦ obszaru podobnego do wzorca

pod wzgl¦dem koloru, ksztaªtu, itp. poprzez przykªadanie wzorca do ka»dego miejsca na

obrazie (z pewn¡ dokªadno±ci¡) i okre±laniu podobie«stwa. Je±li przyjmiemy, »e obiekt

mo»e wyst¦powa¢ w ró»nej skali lub poªo»ony w innej orientacji ni» wzorzec w bazie da-

nych, wymagania obliczeniowe oka»¡ si¦ spore. Dodatkowo mo»e si¦ zdarzy¢, »e tªo nie

sprzyja poszukiwaniom (mo»e by¢ na przykªad podobnego koloru jak poszukiwany obiekt

lub mie¢ skomplikowan¡ struktur¦). Czasem znalezienie obiektu na obrazie przy pomocy

dopasowania wzorca mo»e by¢ wr¦cz niemo»liwe.

Problemy takie s¡ do±¢ cz¦sto spotykane w rzeczywistych aplikacjach i konieczne jest

znalezienie skutecznego sposobu na ich rozwi¡zanie.

Je±li przetwarzane nie s¡ pojedy«cze obrazy, lecz caªe ich sekwencje, a szukane obiekty

poruszaj¡ si¦ w znany sposób, mo»emy wykorzysta¢ t¡ dodatkow¡ informacj¦. Dzi¦ki niej

mo»emy, na przykªad, zmniejszy¢ przeszukiwany obszar obrazu. Przyspieszy to dziaªanie

algorytmu lub umo»liwi dokªadniejsze przeszukiwanie wydzielonej cz¦±ci obrazu bez utraty

szybko±ci przetwarzania.

W pewnych przypadkach mo»e si¦ wr¦cz okaza¢, »e pewna wiedza dotycz¡ca sposobu

poruszania si¦ obiektu mo»e by¢ wystarczaj¡ca do poprawnego jego zlokalizowania na

obrazie i/lub przydzielenia do odpowiedniej klasy.

2

Wst¦p

Mobilno±¢ robota implikuje znaczne zmiany tªa w czasie pracy algorytmów, a tak»e

ograniczenia dotycz¡ce masy oraz poboru energii sprz¦tu (w tym jednostki obliczenio-

wej). Konieczne jest wi¦c opracowanie mo»liwie prostych oraz skutecznych algorytmów

obsªuguj¡cych jego system wizyjny.

Coraz cz¦±ciej spotykane s¡ algorytmy do wykrywania ludzi na sekwencjach obrazów

oparte na wiedzy o sposobie ich poruszania si¦. Przewa»nie nie wymagaj¡ one budowania

obszernej bazy danych ze wzorcami. Dodatkowo oparte s¡ na podstawowych operacjach

z dziedziny przetwarzania obrazów, które nie wymagaj¡ znacznych nakªadów obliczenio-

wych, za to cz¦sto mo»na je wykona¢ na poziomie sprz¦tu. Wiedza dotycz¡ca ruchu

czªowieka pozwala równie» na skuteczne znalezienie go nawet na szybkozmiennym i skom-

plikowanym tle.

Poza robotyk¡ s¡ równie» inne dziedziny, w których mo»na wykorzysta¢ algorytmy

lokalizacji i klasykacji ludzi na podstawie sposobu poruszania si¦.

Spore zainteresowanie budz¡ one w±ród producentów samochodów. Najwi¦ksze rmy

motoryzacyjne, takie jak Daimler-Benz (patrz. [2]) pracuj¡ w swoich laboratoriach nad

algorytmami umo»liwiaj¡cymi wykrywanie pieszych przechodz¡cych przed mask¡ samo-

chodu. Istniej¡ bowiem plany budowy systemu wspieraj¡cego kierowc¦ opartego na sys-

temie wizyjnym, którego celem b¦dzie ostrzeganie kierowcy w razie wykrycia czªowieka

przed samochodem i tym samym zmniejszenie liczby wypadków z udziaªem pieszych.

Inn¡ dziedzin¡ s¡ inteligentne systemy nadzoru. Okre±lenie inteligentne oznacza

wi¦ksz¡ funkcjonalno±¢ ni» zwykªa detekcja ruchu, czego przykªadem ma by¢ mniejsza

podatno±¢ na faªszywe alarmy powodowane na przykªad przez ruch li±ci drzew czy prze-

latuj¡ce przed kamer¡ ptaki.

Jednym z zastosowa« omawianych algorytmów w tej dziedzinie miaªoby by¢ wykrywa-

nie obecno±ci ludzi na scenie oraz skuteczna ich lokalizacja na obrazie i próby identykacji

osób (np. rozpoznawanie twarzy).

System taki mógªby równie» dziaªa¢ w oparciu o rozpoznawanie podejrzanych akcji wy-

konywanych przez obiekt na scenie, wszczynaj¡c alarm po wykryciu czªowieka chodz¡cego

po parkingu i zagl¡daj¡cego do samochodów.

1.2 Cel pracy

Celem pracy jest dokonanie przegl¡du istniej¡cych algorytmów pozwalaj¡cych na lokaliza-

cj¦ i klasykacj¦ pieszych oraz podejmowanych przez nich akcji na sekwencjach obrazów

z wykorzystaniem informacji o ich sposobie poruszania si¦. Nast¦pnym etapem b¦dzie

wybranie jednego z algorytmów lub zaproponowanie wªasnego oraz jego implementacja

wraz z ocen¡ skuteczno±ci dziaªania.

Rozdziaª 2

Przegl¡d istniej¡cych algorytmów

2.1 Podziaª algorytmów

Badania nad wykorzystywaniem informacji dotycz¡cej ruchu czªowieka do jego skutecznej

lokalizacji i/lub identykacji maj¡ sw¡ histori¦. Ju» w 1973 roku psycholog G. Johansson

przeprowadziª eksperymenty w tej materii [9]. Grupie ludzi przyczepiane byªy w ró»nych

miejscach ciaªa i w ró»nych ilo±ciach ±wiec¡ce znaczniki (MLD- Moving Light Display).

Zadaniem drugiej grupy-obserwatorów, byªo rozpoznanie, co oni robi¡. Okazaªo si¦, »e

ludziom wystarczy widok jedynie kilku znaczników, by zidentykowa¢ wykonywan¡ przez

czªowieka akcj¦. Pojawiªy si¦ wi¦c pytania: Czy do skutecznej identykacji czªowieka

lub wykonywanych przez niego czynno±ci niezb¦dna jest wiedza o ruchu poszczególnych

cz¦±ci jego ciaªa? Czy wystarczaj¡c¡ ilo±¢ informacji mo»na pozyska¢ wprost z ogólnych

(niskopoziomowych) danych o jego ruchu?

Podobne badania maj¡ miejsce od pewnego czasu w dziedzinie rozpoznawania rucho-

mych obiektów z wykorzystaniem systemu wizyjnego. Okazuje si¦, »e wiedza o sposobie

poruszania si¦ czªowieka jest wystarczaj¡ca do skutecznego zlokalizowania go na scenie

oraz rozpoznawania wykonywanych przez niego czynno±ci. Dodatkowo wykorzystanie ni-

skopoziomowych cech opisuj¡cych jego ruch pozwala upro±ci¢ i przyspieszy¢ dziaªanie

wykorzystywanych algorytmów.

Pozyskiwanie caªego modelu ciaªa czªowieka (przewa»nie w postaci tzw. stick-gure,

patrz rysunek 2.3) jest najcz¦±ciej wykorzystywane przy analizie jego ruchu. Tematyka ta

jednak wykracza poza zakres niniejszej pracy.

Algorytmy do rozpoznawania ludzi na podstawie sposobu ich poruszania si¦ s¡ bardzo

ró»norodne. W tabeli 2.1 zebrano kilka z nich z uwzgl¦dnieniem ich najwa»niejszych

cech, a w kolejnych podrozdziaªach opisano par¦ przykªadowych podej±¢ do omawianego

zagadnienia w celu pokazania ich ró»norodno±ci.

W wi¦kszo±ci algorytmy do wykrywania pieszych charakteryzuj¡ si¦ niewra»liwo±ci¡

na zmian¦ skali oraz z góry zakªadaj¡, »e ruch przechodz¡cego czªowieka obserwowany

jest z okre±lonego k¡ta. Przewa»nie pieszy porusza si¦ prostopadle do osi kamery. Jest

to przypadek najcz¦±ciej spotykany w praktyce, a zarazem najªatwiejszy do rozpatrzenia.

Ruch czªowieka charakteryzuje si¦ bowiem wyra¹n¡ okresowo±ci¡, któr¡ najªatwiej zaob-

serwowa¢ patrz¡c na niego z boku (ten fakt wykorzystuje znaczna wi¦kszo±¢ algorytmów).

W zale»no±ci od planowanego zastosowania, omawiane algorytmy mog¡ by¢ wra»liwe

lub nie na zmiany tªa oraz statyczno±¢ kamery. Zaªo»enie o statycznym poªo»eniu kamery

b¦dzie w przybli»eniu prawdziwe np. dla systemu nadzoru, lecz bª¦dne w przypadku

zastosowania w systemie wizyjnym robota mobilnego lub innego pojazdu.

4

Przegl¡d istniej¡cych algorytmów

Tablic

a

2.1:

Zesta

wienie

niektóryc

h

algorytmó

w

do

wykryw

ania

ludzi

na

po

dsta

wie

sp

osobu

ic

h

poruszania

si

¦

Algorytm

Tªo

K

olor

Poªo»enie kamery

W

ra»li

w

o±¢

na

sk

al¦

W

ydziel

enie

sylw

etki

Ilo±¢ osób

Mo

del

Klasyk

ator

Zastoso

w

anie

Guo, Xu,T

suji[

7]

S

NIE

Prostopadle do

ruc

hu

NIE

odejmo

w

anie

tªa

jedna

TAK

sie¢

neuro-

no

w

a

rozp

ozna

w

anie

ak

cji

Little, Bo

yd[10]

S

NIE

Prostopadle do

ruc

hu

NIE

pole

ruc

hu

jedna

NIE

klasteryzacja

rozp

ozna

w

anie

osób

Viola, Jones, Sno

w[12]

S

NIE

Prostopadle do

ruc

hu

NIE

ltro

w

anie

jedna

NIE

kask

ado

wy

detek

cja

pie-

szyc

h

Heisele, W

ohler[2]

Z

TAK

Prostopadle do

ruc

hu

NIE

klasteryzacja

wiele

NIE

sie¢

neuro-

no

w

a

detek

cja

pie-

szyc

h

Polana, Nelson[13]

S

NIE

Prostopadle do

ruc

hu

NIE

pole

ruc

hu

jedna

NIE

klasteryzacja

rozp

ozna

w

anie

ak

cji

Tªo

:

S-

stat

yczne,

Z-

zmienne;

K

olor

:

potrzeba

kol

or

ow

ego

obraz

u;

Ilo±¢

osób

:

ile

osób

(ruc

hom

yc

h

obiektó

w)

mo»e

by¢

ob

ecn

yc

h

na

scenie;

Mo

del

:

czy

w

yk

orzystano

mo

del

ciaªa

czªo

wiek

a;

Klasyk

ator

:

w

jaki

sp

osób

dok

on

uje

si¦

klasyk

acji

wykryt

yc

h

obiektó

w

2.2 Klasteryzacja i sieci neuronowe

5

Dodatkowo algorytmy mog¡ zakªada¢ ró»ne parametry obrazu implikuj¡c tym samym

niezb¦dny sprz¦t (np. kolorowa kamera, podczerwie«, itp). Mog¡ równie» wykorzystywa¢

dodatkow¡ wiedz¦ o ksztaªcie poszukiwanych obiektów w celu zwi¦kszenia skuteczno±ci

ich wykrywania.

Do samej klasykacji obiektów (w tym przypadku najcz¦±ciej jako pieszy/inny ru-

chomy obiekt) wykorzystywane s¡ ró»ne klasykatory. Najcz¦±ciej spotykane s¡ sieci neu-

ronowe, klasykatory kaskadowe oraz algorytmy klasteryzacji.

2.2 Klasteryzacja i sieci neuronowe

W pracy [2] przedstawiono metod¦ wykrywania pieszych na podstawie charakterystyki

ich ruchu na sekwencjach kolorowych obrazów pozyskanych z ruchomej kamery.

Typowym zastosowaniem tego algorytmu ma by¢ system wizyjny wspomagaj¡cy kie-

rowc¦ podczas jazdy w mie±cie.

Technika oparta jest na segmentacji obrazów na klastry. Ka»dy spo±ród n pikseli

opisany jest wektorem cech

f

n

= (R

n

, G

n

, B

n

, x

n

, y

n

) ,

(2.1)

gdzie:

• R

n

, G

n

, B

n

to skªadowe koloru w notacji RGB n-tego piksela,

• x

n

, y

n

- poªo»enie n-tego piksela na obrazie.

Metoda zakªada, »e punkty na obrazie o podobnym kolorze oraz poªo»one w niewielkiej

odlegªo±ci od siebie przedstawiaj¡ ten sam zyczny obiekt.

Klasteryzacja sprowadza si¦ do wydzielenia zadanej liczby R wzorców p

r

minimalizu-

j¡cych bª¡d:

E =

X

n

||f

n

− p

r(n)

||

2

,

(2.2)

gdzie: p

r(n)

- wzorzec najbli»szy n-temu pikselowi w przestrzeni kolor/poªo»enie (RGBxy).

W pierwszym kroku wydzielane s¡ klastry. W kolejnych etapach stosowany jest al-

gorytm równolegªej klasteryzacji k-najbli»szych s¡siadów pozwalaj¡cy na ±ledzenie zmian

poªo»enia i rozmiaru klastrów w czasie. Na rysunku 2.1 przedstawiono przykªadowy obraz

z zaznaczonymi klastrami.

Dane wej±ciowe dla klasykatora stanowi¡ zmiany szeroko±ci prostok¡tów opisanych na

klastrach w czasie. Zakªadaj¡c, »e nogi pieszego zostan¡ wydzielone jako jeden odr¦bny

klaster, mo»liwe jest wydzielenie klastrów potencjalnie zawieraj¡cych fragment id¡cego

czªowieka.

Do wst¦pnej klasykacji wykorzystany zostaª szybki, wielomianowy klasykator. Te-

sty przeprowadzone przez autorów pracy pokazaªy, i» skuteczno±¢ wykrycia pieszego na

danym obrazie wynosi okoªo 84%. Bior¡c pod uwag¦, »e pieszy wyst¦puje na wielu klat-

kach lmu, odsetek ten jest wystarczaj¡co du»y. Problem stanowi jednak du»a liczba

faªszywych alarmów si¦gaj¡ca 7% z ilo±ci wydzielonych klastrów na danym obrazie.

Ostatecznej klasykacji dokonuje si¦ za pomoc¡ sieci neuronowej. Jako dane wej±ciowe

dla niej podawane s¡ informacje dotycz¡ce klastrów podejrzanych o zawieranie nóg pie-

szego wskazanych w procesie wst¦pnej klasykacji. Autorzy proponuj¡ zastosowanie sieci

TDNN (Time Delay Neural Network). Szczegóªy dotycz¡ce tej metody zawiera praca [2]

oraz wskazane w niej referencje.

6

Przegl¡d istniej¡cych algorytmów

Rysunek 2.1: Przykªad obrazu po klasteryzacji [2]

2.3 Ukryte modele Markowa

Caªkiem inny, globalny sposób wykorzystania znajomo±ci ruchu czªowieka do jego loka-

lizacji i identykacji przedstawiono w pracach [3], [4], [5]. Jest on stosowany w takich

miejscach, jak szpitale, muzea, biura i domy towarowe. Wykorzystywany jest najcz¦±ciej

do lokalizacji osób w otoczeniu robota mobilnego poruszaj¡cego si¦ na danym obszarze.

Kiedy ludzie wykonuj¡ swoje codzienne czynno±ci, nie poruszaj¡ si¦ w sposób ci¡gªy.

Zazwyczaj zatrzymuj¡ si¦ w pewnych miejscach na jaki± czas, w zale»no±ci od wykony-

wanego zadania. Ta cecha ruchu czªowieka stanowi podstaw¦ do jego lokalizacji oraz

identykacji.

Do zbudowania bazy wzorców ruchu ludzi mo»na wykorzysta¢ system zªo»ony ze ska-

nerów laserowych i kamer umieszczonych w odpowiednich, kluczowych miejscach obser-

wowanego obszaru. W przypadku wykrycia przez dalmierz obecno±ci czªowieka w danym

miejscu, system wizyjny podejmuje prób¦ jego zidentykowania. Wszystkie dane przesy-

ªane s¡ do scentralizowanej bazy. Otrzymamy pewien zbiór ±cie»ek, na podstawie których

zbudowane zostan¡ wzorce ruchu odpowiadaj¡ce konkretnym zachowaniom.

I tak na wej±cie omawianego algorytmu podawany jest zbiór trajektorii d = {d

1

...d

n

}

pomi¦dzy miejscami zatrzyma«. Na jego podstawie w oparciu o ukryte modele Mar-

kowa budowane s¡ wzorce zachowa« reprezentuj¡ce zmiany poªo»e« ludzi w zale»no±ci od

2.4 Wykorzystanie modelu

7

wykonywanego zadania.

Robot mobilny posiadaj¡cy tak zamodelowan¡ wiedz¦ o sposobie poruszania si¦ ludzi

w jego otoczeniu mo»e, z pewnym prawdopodobie«stwem, stwierdzi¢, gdzie znajduje si¦

interesuj¡ca go osoba nawet wtedy, gdy jej nie widzi. Gdy robot spotyka kogo± na swojej

trasie, dokonuje jego identykacji oraz modykuje posiadan¡ wiedz¦ uwzgl¦dniaj¡c jego

aktualne poªo»enie.

Rysunek 2.2: Przykªad dziaªania algorytmu z wykorzystaniem ukrytych modeli Mar-

kowa [3]

Ilustruj¡cy to przykªad zamieszczono na rysunku 2.2. Robot pocz¡tkowo nie widzi

danej osoby. Posiadana wiedza dotycz¡ca jej codziennych czynno±ci pozwala mu przy-

puszcza¢, »e mo»e ona znajdowa¢ si¦ w miejscu zatrzymania oznaczonym jako '7' (z

prawdopodobie«stwem wynosz¡cym p = 0.39),w miejscu '3' (p = 0.04), w miejscu '6'

(p = 0.01) lub w drodze mi¦dzy punktami (p = 1 − (0.39 + 0.04 + 0.01) = 0.56). W pew-

nej chwili dostrzega czªowieka przechodz¡cego przed sob¡. Modykuje wi¦c posiadan¡

wiedz¦ oraz wykorzystuje otrzyman¡ wªa±nie informacj¦ w dalszym procesie szacowania

jego poªo»enia.

2.4 Wykorzystanie modelu

W pracy [7] przedstawiony zostaª algorytm rozpoznawania akcji wykonywanych przez

obserwowanego czªowieka z wykorzystaniem modelu jego ciaªa. Ma on klasykowa¢ ruch

pieszego jako chód, bieg, lub inne. Jego autorzy przyjmuj¡, »e:

•

Ruch poszczególnych cz¦±ci ciaªa czªowieka mo»e by¢ w przybli»eniu traktowany

jako ruch planarny. Ruch rozpatruje si¦ wi¦c jako dwuwymiarowy.

•

Obserwowana osoba porusza si¦ na stacjonarnym tle. Mo»liwe jest wi¦c wydzielenie

jej sylwetki na danej klatce poprzez odj¦cie od niej klatki z tªem.

8

Przegl¡d istniej¡cych algorytmów

•

Na scenie jest co najwy»ej jeden ruchomy obiekt (czªowiek).

•

Czªowiek porusza si¦ w pªaszczy¹nie prostopadªej do osi kamery.

Rysunek 2.3: Przykªad dwuwymiarowego modelu ciaªa czªowieka [7]

Model ciaªa reprezentowany jest przez szkielet (ang. stick-gure) przedstawiony na ry-

sunku 2.3. Skªada si¦ on z dziesi¦ciu odcinków poª¡czonych sze±cioma przegubami. Jego

stan mo»na opisa¢ w zwarty sposób za pomoc¡ wektora parametrów:

S = (x

0

, y

0

, d

m

, h

t

, h

a

, h

l

, h

n

, α

0

, α

1

, . . . , α

9

)

.

Ich znaczenie jest nast¦puj¡ce:

• (x

0

, y

0

)

- poªo»enie ±rodka gªowy

• d

m

- kierunek ruchu (

0

1

0

-w lewo,

0

− 1

0

-w prawo)

• h

t

- dªugo±¢ linii tuªowia

• h

a

- dªugo±¢ linii ramion

• h

l

- dªugo±¢ linii nóg

2.5 Momenty geometryczne

9

• h

n

- dªugo±¢ linii gªowy

• α

0

- k¡t mi¦dzy lini¡ tuªowia, a osi¡ y

• α

1

. . . α

9

- k¡ty mi¦dzy s¡siaduj¡cymi liniami

Linie poª¡czone s¡ ze sob¡ przegubami. Zakªada si¦, »e mog¡ one obraca¢ si¦ w ogra-

niczonym zakresie (na przykªad kolana i ªokcie mog¡ wygina¢ si¦ tylko w jedn¡ stron¦).

Algorytm skªada si¦ z nast¦puj¡cych etapów:

1. Wydzielenie sylwetki czªowieka poprzez odj¦cie tªa od danej ramki

2. Binaryzacja uzyskanego obrazu

3. Wyznaczenie szkieletu sylwetki

4. Dopasowanie uzyskanego szkieletu do modelu, wyznaczenie warto±ci parametrów

skªadowych wektora S

W wyniku jego dziaªania uzyskamy sekwencj¦ S(n) opisuj¡c¡ ruch obserwowanego

czªowieka. Nast¦pnie wydzielany jest jeden okres jej zmian i podawany na wej±cie sieci

neuronowej wyuczonej do rozró»niania chodu, biegu oraz innych czynno±ci.

2.5 Momenty geometryczne

2.5.1 Wst¦p

W pracy [10] przedstawiono algorytm pozwalaj¡cy na rozpoznawanie osób na podstawie

ich chodu. ‘ledzi on zmiany parametrów, które s¡ ±ci±le zwi¡zane z momentami geo-

metrycznymi ksztaªtu sylwetki czªowieka wydzielonej z kolejnych klatek sekwencji przed-

stawiaj¡cej jego ruch. Algorytm nie jest wra»liwy na skal¦ i nie wymaga wykrywania

»adnych punktów charakterystycznych ciaªa czªowieka (takich jak stawy, dªonie, stopy,

gªowa). Dziaªa on na obrazach przedstawiaj¡cych pojedynczych pieszych przechodz¡cych

w pªaszczy¹nie prostopadªej do osi statycznej kamery.

2.5.2 Ogólny opis metody

Na rysunku 2.4 przedstawiono schemat dziaªania algorytmu z wydzieleniem jego etapów.

Danymi wej±ciowymi jest zestaw n+1 obrazów przedstawiaj¡cych czªowieka przechodz¡-

cego w pªaszczy¹nie prostopadªej do kamery. Na bazie ka»dych dwóch s¡siaduj¡cych

ramek wyliczane jest n obrazów przedstawiaj¡cych pole ruchu obiektu.

Kolejnym etapem jest wyliczenie m parametrów (warto±ci skalarne) dla ka»dej z wy-

dzielonych na podstawie pola ruchu sylwetek, aby nast¦pnie utworzy¢ dla ka»dego z nich

przebieg zmian w czasie.

Sposób poruszania si¦ czªowieka charakteryzuje si¦ cykliczno±ci¡ zmian parametrów.

Przebieg ka»dego z nich b¦dzie równy dokªadnie cz¦stotliwo±ci podstawowej ruchu lub

stanowi¢ b¦dzie jego caªkowit¡ wielokrotno±¢. Wyst¦puj¡ jednak ró»nice w ich fazie.

Aby móc porówna¢ ró»ne sekwencje ruchu, musimy jeden z parametrów potraktowa¢

jako faz¦ odniesienia: φ

m

. Wektorem cech charakteryzuj¡cym ka»d¡ sekwencj¦ b¦dzie

F = (F

1

, ..., F

m−1

)

, gdzie F

i

= φ

i

− φ

m

.

10

Przegl¡d istniej¡cych algorytmów

Rysunek 2.4: Schemat dziaªania algorytmu Shape of Motion [10]

2.5.3 Szczegóªowy opis metody

Pole ruchu
Autorzy pracy wyznaczaj¡ pole ruchu poprzez minimalizacj¦ bª¦du ±redniokwadratowego

pomi¦dzy poszczególnymi plamami na s¡siednich klatkach lmu.

Algorytm dla ka»dego piksela poszukuje przemieszczenia (u(x, y), v(x, y)) które mi-

nimalizuje sum¦ warto±ci bezwzgl¦dnych ró»nic pomi¦dzy warto±ciami jasno±ci danego

obszaru na jednym obrazie i odpowiadaj¡cego mu obszaru na drugim obrazie. W ten spo-

sób dla ka»dej plamy klatki lmu znajduje najlepsze dopasowanie plamy na kolejnej klatce.

Nast¦pnie algorytm przetwarza oba obrazy zamieniaj¡c ich role (dla ka»dego obszaru na

drugiej klatce szuka najlepszego dopasowania na klatce pierwszej). Je±li dopasowanie byªo

dobre, wyniki powinny by¢ takie same.

W kolejnym kroku algorytm sprawdza wyniki dopasowania dla ka»dego piksela obrazu.

Tylko te obszary, których wyniki w przybli»eniu zgadzaj¡ si¦ na obu obrazach (suma

przemieszcze« powinna by¢ bliska zeru) s¡ brane pod uwag¦.

Przykªadowe rozkªady |(u, v)| dla kilku kolejnych klatek lmu przedstawione s¡ na

rysunku 2.5a.

Zakªada si¦, »e przemieszczenie mo»e przyj¡¢ tylko warto±ci caªkowite (wyra»one w

pikselach). Punkty, dla których jego warto±¢ wynosi co najmniej 1 nazywamy punktami

ruchomymi. Niech:

T (u, v) =

(

1,

je±li |(u, v)| ≥ 1

0,

w przeciwnym razie

(2.3)

Przykªadowe rozkªady T (u, v) dla kilku kolejnych klatek lmu przedstawione s¡ na

2.5 Momenty geometryczne

11

rysunku 2.5b. Za pomoc¡ T (u, v) wydzielamy ruchome punkty. Otrzymujemy zestaw

a)

b)

Rysunek 2.5: a) Przykªadowy rozkªad warto±ci (|(u, v)|) dla sze±ciu klatek lmu;

b) Przykªadowy rozkªad warto±ci T (u, v) dla sze±ciu klatek lmu. [10]

obrazów binarnych, na których punkty ruchome maj¡ warto±¢ 1, natomiast pozostaªe-0.

Parametry
Do dalszej analizy ruchu wydzielonego obiektu wykorzystane zostan¡ zarówno warto±ci

binarne T (u, v), jak i wa»one przez warto±ci przesuni¦cia poszczególnych punktów w osi

poziomej (|u|T (u, v)), pionowej (|v|T (u, v)) oraz przesuni¦cia caªkowitego (|(u, v)|T (u, v)).

Podstawowymi parametrami charakteryzuj¡cymi ruch s¡ ±rodki ci¦»ko±ci rozkªadu

(T (u, v)) oraz (|(u, v)|T (u, v)). Dodatkowo bierze si¦ pod uwag¦ rozkªady |u|T (u, v) i
|v|T (u, v)

, czyli skªadowe poziome i pionowe pola ruchu.

Do cech charakterystycznych dla ruchu czªowieka zalicza si¦ równie» momenty bez-

wªadno±ci sylwetki wzdªu» osi gªównej sylwetki oraz wzdªu» osi do niej prostopadªej.

Moment bezwªadno±ci przyjmuje warto±¢ minimaln¡, gdy jest liczony wzdªu» osi gªównej

oraz maksymaln¡ wzdªu» osi do niej prostopadªej.

Do wizualizacji momentów bezwªadno±ci sylwetki cz¦sto wykorzystuje si¦ elips¦. Ry-

suje si¦ j¡ w ten sposób, »e:

1. ‘rodek elipsy le»y w ±rodku masy sylwetki

2. O± du»a elipsy le»y wzdªu» osi gªównej sylwetki i przyjmuje warto±¢ zale»n¡ od

maksymalnego momentu bezwªadno±ci sylwetki (liczonego wzdªu» osi prostopadªej

do osi gªównej sylwetki)

3. O± maªa le»y prostopadle do osi gªównej sylwetki i przyjmuje warto±¢ zale»n¡ od mi-

nimalnego momentu bezwªadno±ci sylwetki (liczonego wzdªu» osi gªównej sylwetki)

Na rysunku 2.6 przedstawiono przykªadowe klatki z lmu z wyrysowanymi wg powy»szych

zasad elipsami. Kwadratem i elips¡ ci¡gª¡ zobrazowane s¡ parametry odpowiadaj¡ce

12

Przegl¡d istniej¡cych algorytmów

rozkªadowi binarnemu (T (u, v)), natomiast krzy»ykiem i lini¡ przerywan¡- |(u, v)|T (u, v).

Stosunek dªugo±ci osi elipsy stanowi niezale»ny od skali parametr sylwetki. Jego zmiany

Rysunek 2.6: Wizualizacja momentów sylwetek za pomoc¡ elips [10]

odzwierciedlaj¡ zarówno poªo»enie jak i pr¦dko±¢ poruszaj¡cych si¦ punktów.

Ksztaªt ruchu, poj¦cie wprowadzone przez autorów pracy [10], opisuje zmiany pola

ruchu poruszaj¡cego si¦ obiektu za pomoc¡ zestawu parametrów okre±laj¡cych jego stan

w danej chwili.

Do cech opisuj¡cych ruch czªowieka autorzy pracy [10] polecaj¡ doda¢ stosunki

λ

max

λ

min

dla sylwetek T (u, v) i |(u, v)|T (u, v), gdzie λ

min

i λ

max

to kolejno minimalna i maksymalna

warto±¢ wªasna macierzy drugich momentów danego rozkªadu.

Peªny zestaw parametrów, którego wykorzystanie sugeruj¡ autorzy pracy [10] zamiesz-

czono w tabeli 2.2.

2.5 Momenty geometryczne

13

Tablic

a

2.2:

Zesta

w

parametró

w

sylw

etki,

wg

autoró

w

algorytm

u

Shap

e

Of

Motion

l.p.

Opis

Sym

bol

W

zór

1.

W

sp

óªrz¦dna

x

rozkªadu

T

(u,

v

)

x

c

P

xT

/

P

T

2.

W

sp

óªrz¦dna

x

rozkªadu

|(

u,

v

)|

T

(u,

v

)

x

ω

c

P

x

|(

u,

v

)|

T

/

P

|(

u,

v

)|

T

3.

W

sp

óªrz¦dna

y

rozkªadu

|(

u,

v

)|

T

(u,

v

)

y

ω

c

P

y

|(

u,

v

)|

T

/

P

|(

u,

v

)|

T

4.

Pozioma

ró»nica

poªo»e«

±ro

dk

ów

x

d

x

ω

c

−

x

c

5.

Piono

w

a

ró»nica

poªo»e«

±ro

dk

ów

y

d

y

ω

c

−

y

c

6.

W

sp

óªczynnik

wydªu»enia

elipsy

rozkªadu

T

(u,

v

)

a

c

λ

max

/λ

min

,

gdzie

λ-

w

arto±¢

wªa-

sna

macierzy

drugic

h

momen

tó

w

syl-

w

etki

7.

W

sp

óªczynnik

wydªu»enia

elipsy

rozkªadu

|(

u,

v

)|

T

(u,

v

)

a

ω

c

jak

a

c

8.

Ró»nica

wsp

óªczynnik

ów

wydªu»enia

obu

elips

a

d

a

c

−

a

ω

c

9.

W

sp

óªrz¦dna

x

rozkªadu

|u

|T

(u,

v

)

x

uω

c

P

x

|u

|T

/

P

|u

|T

10.

W

sp

óªrz¦dna

y

rozkªadu

|u

|T

(u,

v

)

y

uω

c

P

y

|u

|T

/

P

|u

|T

11.

W

sp

óªrz¦dna

x

rozkªadu

|v

|T

(u,

v

)

x

v

ω

c

P

x

|v

|T

/

P

|v

|T

12.

W

sp

óªrz¦dna

y

rozkªadu

|v

|T

(u,

v

)

y

v

ω

c

P

y

|v

|T

/

P

|v

|T

13.

W

sp

óªrz¦dna

y

rozkªadu

T

(u,

v

)

y

c

P

y

T

/

P

T

14

Przegl¡d istniej¡cych algorytmów

Ka»dy obraz I

j

nale»¡cy do badanej sekwencji ruchu generuje zestaw m = 13 ska-

larnych warto±ci parametrów, s

ij

, gdzie i = 1...m oraz j = 1..n. W nast¦pnym kroku

skªadamy zale»ne od czasu warto±ci ka»dej cechy w przebiegi czasowe (wektory S

i

).

Okre±lenie cz¦stotliwo±ci i fazy
Charakterystyczne dla sposobu poruszania si¦ id¡cego czªowieka jest posiadanie jednej,

gªównej cz¦stotliwo±ci. Mog¡ wyst¡pi¢ dodatkowo caªkowite jej wielokrotno±ci. Wynika

to z konieczno±ci koordynacji ruchu poszczególnych cz¦±ci jego ciaªa. Wyprowadzone

parametry, b¦d¡ce w zasadzie sum¡ ruchów cz¦±ci ciaªa czªowieka musz¡ mie¢ t¡ sam¡

wªa±ciwo±¢.

Pomimo wspólnej cz¦stotliwo±ci, przebiegi zmian parametrów ró»ni¢ si¦ b¦d¡ przesu-

ni¦ciem fazowym. Musimy wi¦c znale¹¢ podstawow¡ cz¦stotliwo±¢, a nast¦pnie ró»nice w

fazie poszczególnych sygnaªów.

Autorzy pracy uznali, »e klasyczna metoda wyznaczania parametrów z wykorzysta-

niem transformacji Fouriera b¦dzie niedostatecznie precyzyjna. Próbki sygnaªów zawie-

raj¡ tylko kilka przebiegów i niemo»liwe jest precyzyjne okre±lenie cz¦stotliwo±ci i fazy. W

zamian u»yli metody opartej na zasadzie maksimum entropii (maximum entropy spectrum

estimation). Z racji jej zªo»ono±ci po szczegóªy odsyªam do pracy [10] oraz cytowanych w

niej ¹ródeª.

Klasykacja
Autorzy przeprowadzili szerok¡ dyskusj¦ na temat otrzymanych wyników oraz mo»liwo±ci

ich interpretacji. Analiza statystyczna pokazaªa, »e najbardziej mo»na polega¢ na cechach

sygnaªów y

ωc

, y

d

oraz a

d

. Na rysunku 2.7 przedstawiªem wykres cech uzyskanych na pod-

stawie sygnaªów y

d

i a

d

dla sze±ciu ró»nych osób. Wida¢ wyra¹n¡ tendencj¦ do grupowania

si¦ wyników sugeruj¡c¡ mo»liwo±¢ wykorzystania jednej z technik klasteryzacji.

I tak autorzy wypróbowali m.in. metody: jeden najbli»szy s¡siad oraz k najbli»szych

s¡siadów. Z wykorzystaniem peªnego wektora cech uzyskali skuteczno±¢ poprawnej identy-

kacji na poziomie 90.5%. Zmniejszenie wektora do kilku wybranych skªadowych pozwala

zwi¦kszy¢ ten odsetek do 95%.

2.5 Momenty geometryczne

15

Rysunek 2.7: Poªo»enia punktów reprezentuj¡cych warto±ci wektora (y

d

,a

d

) dla 42 próbek

charakteryzuj¡cych chód 6 osób [10]

16

Przegl¡d istniej¡cych algorytmów

Rozdziaª 3

Opis implementacji

Do implementacji zdecydowaªem si¦ wybra¢ algorytm Shape Of Motion opisany w pracy [10].

Krótkie jego omówienie znajduje si¦ w rozdziale 2.5 niniejszej pracy. Jest to algorytm

wykorzystuj¡cy niskopoziomowe cechy poruszaj¡cego si¦ obiektu. Nie wymaga wi¦c two-

rzenia wzorca opisuj¡cego ksztaªt czªowieka, wyznaczania odpowiadaj¡cych mu cech na

obrazie (na przykªad szkieletu sylwetki), ani ich pó¹niejszego dopasowywania.

Wykorzystanie jedynie kilku podstawowych oraz nieskomplikowanych operacji z dzie-

dziny przetwarzania obrazów sprawia, »e metoda ta jest ªatwa do zrozumienia, implemen-

tacji oraz, co za tym idzie, wprowadzania ewentualnych ulepsze«. Z racji swojej prostoty

istnieje szansa, »e b¦dzie on w stanie dziaªa¢ w czasie rzeczywistym w trybie online na

dost¦pnym sprz¦cie (patrz rozdziaª 3.1.1).

Dodatkowo ilo±¢ zaproponowanych parametrów oraz dyskusja na temat wyników dzia-

ªania algorytmu oraz wnioski z niej wyci¡gni¦te przez autorów wspomnianej pracy wska-

zuj¡ na du»y potencjaª metody. Zmniejszenie rozmiaru wektora cech poprzez wybranie

najpewniejszych (daj¡cych najlepsze wska¹niki poprawnej klasykacji) oraz ewentualnie

zaproponowanie dodatkowych parametrów pozwoli na zaprojektowanie algorytmu zbilan-

sowanego pod wzgl¦dem skuteczno±ci oraz szybko±ci dziaªania.

Implementowany algorytm sªu»y do identykowania konkretnych osób na podstawie

charakterystyki cz¦stotlio±ciowej ich chodu. Postanowiªem zmniejszy¢ wymagania i po-

przesta¢ na lokalizacji id¡cych ludzi na sekwencjach obrazów. Praca [10] ma charakter

±ci±le badawczy i dla jej autorów pr¦dko±¢ dziaªania algorytmu, ani mo»liwo±¢ jego pracy

w czasie rzeczywistym na komputerze osobistym nie miaªa wi¦kszego znaczenia. Co wi¦-

cej, nie proponuj¡ oni konkretnej, zwartej implementacji rozwa»anej metody. Do analizy

statystycznej otrzymanych wyników wykorzystali komercyjne oprogramowanie (StatView

4.5 ). Nie podali równie» konguracji sprz¦towej, na której przeprowadzane byªy badania,

ani czy osi¡gni¦to zadowalaj¡c¡ pr¦dko±¢ dziaªania.

Reasumuj¡c, zaimplementowaªem algorytm sªu»¡cy do lokalizacji id¡cych ludzi na

sekwencjach obrazów, oparty na zaproponowanej w pracy [10] metodzie wykorzystuj¡cej

momenty geometryczne sylwetki ruchomego obiektu. Dodatkowo zakªadam, »e:

•

Na scenie znajduje si¦ tylko jeden ruchomy obiekt.

•

Kamera ustawiona jest w osi prostopadªej do pªaszczyzny ruchu obiektu.

•

Kamera jest statyczna, a tªo si¦ nie zmienia.

Dodatkowym celem b¦dzie próba uzyskania pªynno±ci pracy algorytmu w czasie rze-

czywistym na posiadanym sprz¦cie (patrz 3.1.1).

18

Opis implementacji

3.1 Wykorzystane narz¦dzia

3.1.1 Sprz¦t

Do implementacji algorytmu oraz badania jego skuteczno±ci i pr¦dko±ci dziaªania wyko-

rzystaªem komputery w konguracjach wymienionych w tabeli 3.1.

Tablica 3.1: Komputery wykorzystane do testowania algorytmu

Nazwa

Procesor

RAM

Chili

Pentium III, 650MHz

128MB

Frytka

Athlon 2000XP+, 1700MHz

256MB

Enterprise Pentium IV, 3000MHz HT

1GB Dual-Channel

Klocek

T7400, 2160MHz Intel Core 2 Duo 1GB

3.1.2 System operacyjny

Program pisany jest z my±l¡ o pracy w systemie operacyjnym GNU Linux. Jest to system

darmowy oraz gwarantuj¡cy stabilno±¢ dziaªania. Coraz cz¦±ciej jest wykorzystywany

w zastosowaniach przemysªowych. Dodatkowo dost¦pnych jest wiele wygodnych, a za-

razem darmowych narz¦dzi do tworzenia oprogramowania (kompilatory, biblioteki, itp).

Wyst¦puj¡ one równie» w wersjach dla innych systemów operacyjnych, wi¦c ewentualne

przeniesienie na inny system operacyjny powinno by¢ mo»liwe.

3.1.3 Kompilator

Do kompilacji u»ywaªem g++- kompilatora j¦zyka C++ wchodz¡cego w skªad zestawu

GCC (GNU Compiler Collection) w wersji 4.1.2. Jest on dost¦pny na wszystkie popu-

larne platformy sprz¦towe (w tym: x86, x86-64, ARM, PowerPC, Motorola M68000 ) oraz

wiele systemów operacyjnych (m.in. GNU Linux, *BSD, Windows, MacOS X, SunOS).

Kolekcja GCC jest rozpowszechniana na licencji GPL[6].

3.1.4 Przetwarzanie obrazów

Do pozyskiwania oraz przetwarzania obrazów wykorzystaªem bibliotek¦ OpenCV (Open

Source Computer Vision Library) rmy Intel w wersji 1.0.0. Zawiera ona zestaw okoªo
300

funkcji w j¦zyku C oraz kilka klas w C++ implementuj¡cych wiele popularnych

algorytmów z dziedziny komputerowej wizji oraz przetwarzania obrazów. Umo»liwia tak»e

tworzenie prostych interfejsów u»ytkownika.

Jest ona darmowa zarówno do wykorzystania w niekomercyjnych, jak i komercyjnych

aplikacjach.

3.1.5 Algorytmy numeryczne

Do wykonywania skomplikowanych oblicze« matematyczcnych u»yªem funkcji wchodz¡-

cych w skªad biblioteki GSL(GNU Scientic Library) w wersji 1.8. Zawiera ona zestaw

gotowych algorytmów do wykonywania oblicze« numerycznych. Jest rozpowszechniana

na licencji GPL[6].

3.2 Wyznaczenie parametrów chodu czªowieka

19

3.1.6 Dane wej±ciowe

Do przeprowadzania bada« skuteczno±ci dziaªania implementowanego algorytmu wyko-

rzystaªem sekwencje z bazy danych CASIA Gait Database [8] zebranej przez Instytut

Automatyzacji Chi«skiej Akademii Nauk (Institute of Automation, Chinese Academy of

Sciences). Zawiera ona lmy z przechodz¡cymi przed kamer¡ pieszymi. Kamera usta-

wiona jest pod ró»nymi k¡tami (11 pozycji, od 0 do 180 stopni). W sumie jest to okoªo
15000

lmów.

Poza wspomnianymi sekwencjami w bazie zawarte s¡ równie» parametry pieszych,

takie jak wzrost czy masa, oraz poszczególne klatki wydobyte z lmów, tak»e w postaci

binarnej, z wydzielon¡ sylwetk¡ pieszego.

Jest to wspaniaªy materiaª dla ka»dego, kto chciaªby si¦ zaj¡¢ badaniem mo»liwo±ci

wykorzystania systemu wizyjnego do lokalizacji lub identykacji pieszych na podstawie

sposobu, w jaki chodz¡.

3.2 Wyznaczenie parametrów chodu czªowieka

Na rysunku 3.1 przedstawiªem ogólny schemat dziaªania implementowanego algorytmu.

Pierwsza wersja ma za zadanie pokaza¢, czy mo»liwe b¦dzie pozyskanie parametrów syl-

wetki id¡cego czªowieka oraz zaobserwowanie i wyznaczenie cz¦stotliwo±ci ich zmian z

u»yciem narz¦dzi opisanych w rozdziale 3.1.

3.2.1 Wydzielenie sylwetki

Cech¡ charakterystyczn¡ sekwencji wchodz¡cych w skªad bazy danych CASIA jest to, »e

na pierwszych klatkach nie jest widoczny pieszy. Mo»na wi¦c pobra¢ pierwszy obraz i

traktowa¢ jako staªe, niezmienne tªo.

Dzi¦ki temu mo»liwe jest wydzielenie sylwetki poruszaj¡cego si¦ czªowieka poprzez

odejmowanie od poszczególnych klatek tªa (ang. background subtraction) oraz dokonanie

operacji progowania na otrzymanym obrazie.

W swojej implementacji zamiast odejmowa¢, dziel¦ klatki przez model tªa. Metoda ta

zapobiega powstawaniu pikseli o ujemnej warto±ci jasno±ci pikseli na obrazie wynikowym,

a tak»e zmniejsza wpªyw nierównomierno±ci o±wietlenia sceny.

Dany piksel (x, y) jest uznany za nale»¡cy do poruszaj¡cego si¦ obiektu, je±li:

I(x, y)

B(x, y)

> T,

(3.1)

gdzie:

• (x, y)

- poªo»enie piksela na obrazie

• I(x, y)

- warto±¢ jasno±ci piksela (x, y) na danej klatce

• B(x, y)

- warto±¢ jasno±ci piksela (x, y) na klatce tªa

• T

- próg

Na rysunkach 3.2d-3.2f przedstawiªem kilka przykªadowych klatek z wydzielon¡ syl-

wetk¡ id¡cego czªowieka.

20

Opis implementacji

Rysunek 3.1: Schemat dziaªania pierwszej wersji zaimplementowanego algorytmu

3.2.2 Pole ruchu

Do wyliczenia pola ruchu poruszaj¡cego si¦ obiektu u»yªem funkcji CalcOpticalFlowLK

zaimplementowanej w bibliotece OpenCV. Wykorzystuje ona algorytm Lucasa i Kanade

opisany w pracy [11]. Mimo swojej prostoty, metoda ta daªa satysfakcjonuj¡ce wyniki.

3.2 Wyznaczenie parametrów chodu czªowieka

21

a)

b)

c)

d)

e)

f)

g)

h)

i)

j)

k)

l)

Rysunek 3.2: Trzy przykªadowe klatki z lmu z id¡cym pieszym (a-c), wydzielone z

nich obrazy binarne (d-f), pola ruchu (g-i), oraz ich iloczyny (j-l). Dla celów niniejszej

wizualizacji histogramy obrazów d-l zostaªy znormalizowane. W innym razie byªyby one

maªo czytelne.

Funkcja CalcOpticalFlowLK pozwala na uzyskanie dwóch obrazów. Na jednym ja-

sno±¢ piksela ma warto±¢ równ¡ skªadowej poziomej przesuni¦cia odpowiadaj¡cego mu

obszaru mi¦dzy dwoma obrazami, a na drugim- skªadowej pionowej. Obraz reprezentu-

j¡cy przesuni¦cie caªkowite uzyskaªem poprzez zsumowanie warto±ci bezwzgl¦dnych obu

obrazów. Otrzymaªem wi¦c przesuni¦cie w normie Manhattan.

Przykªadowe obrazy reprezentuj¡ce caªkowite przesuni¦cie widoczne s¡ na rysunkach

22

Opis implementacji

3.2g-3.2i. Wida¢, »e poza obszarem sylwetki algorytm równie» wykryª ruch (ja±niejsze

plamy). Z tego powodu niemo»liwe byªoby wydzielenie sylwetki ruchomego obiektu po-

przez segmentacj¦ obszaru ruchomego.

Aby otrzyma¢ pole ruchu jedynie dla cz¦±ci obrazu zawieraj¡cej pieszego, mno»¦ obraz

przez binarn¡ sylwetk¦ uzyskan¡ poprzez odejmowanie tªa. Kilka klatek z wydzielonym

polem ruchu id¡cego czªowieka zaprezentowaªem na rysunkach 3.2j-3.2l. Warto±ci jasno±ci

s¡ dosy¢ maªe, wi¦c na potrzeby wizualizacji dokonaªem normalizacji histogramu.

Algorytm Lucasa i Kanade
Problem przesuni¦cia obiektu na obrazach mo»na przedstawi¢ w nast¦puj¡cy sposób:

Mamy dane funkcje F (x) oraz G(x) reprezentuj¡ce warto±ci wszystkich pikseli na dwóch

obrazach (x jest wektorem). Poszukujemy przesuni¦cia h, które minimalizuje pewne kry-

terium jako±ci reprezentuj¡ce ró»nic¦ mi¦dzy F (x + h) a G(x). Typowymi, najcz¦±ciej

spotykanymi miarami s¡:

• L

1

=

P

x

|F (x + h) − G(x)|

• L

2

=

pP

x

(F (x + h) − G(x))

2

Norma L

1

stanowi przybli»enie normy L

2

oraz ma zdecydowanie mniejsz¡ zªo»ono±¢

obliczeniow¡.

Dziaªanie algorytmu Lucasa i Kanade najªatwiej wytªumaczy¢ dla przypadku jedno-

wymiarowego, a nast¦pnie dokona¢ generalizacji na wiele wymiarów.

W przypadku jednowymiarowym poszukujemy poziomej ró»nicy h mi¦dzy krzywymi

F (x)

oraz G(x) = F (x + h). Opieramy si¦ na przybli»eniu liniowym F (x) w otoczeniu x.

Dla maªych warto±ci h mamy:

F

0

(x) ≈

F (x + h) − F (x)

h

=

G(x) − F (x)

h

,

(3.2)

st¡d:

h(x) ≈

G(x) − F (x)

F

0

(x)

.

(3.3)

U±redniamy h wzgl¦dem x:

h(x) ≈

P

x

G(x)−F (x)

F

0

(x)

P

x

1

.

(3.4)

Aby polepszy¢ wynik, wprowadzamy wagi. B¦d¡ one miaªy du»e warto±ci dla liniowych

fragmentów F (x) (maªe |F

00

(x)|

), czyli tych miejsc, gdzie najlepiej mo»emy j¡ przybli»y¢

wzorem (3.2):

w(x) =

1

|G

0

(x) − F

0

(x)|

,

(3.5)

wtedy:

h(x) ≈

P

x

w(x)[G(x)−F (x)]

F

0

(x)

P

x

w(x)

.

(3.6)

Rozwi¡zania poszukujemy przesuwaj¡c F (x) o przybli»enie h, korzystaj¡c z iteracji:

h

0

= 0,

(3.7)

h

k+1

= h

k

+

P

x

w(x)[G(x) − F (x + h

k

)]

P

x

w(x)

.

(3.8)

3.2 Wyznaczenie parametrów chodu czªowieka

23

Powy»sze wyprowadzenie bardzo dobrze tªumaczy metod¦, lecz nie nadaje si¦ do ªa-

twego uogólnienia dla przypadku wielowymiarowego. Dodatkowo warto±¢ (3.3) jest nie-

okre±lona dla poziomych fragmentów funkcji F (x), gdy» F

0

(x) = 0

. Linearyzujemy wi¦c

funkcj¦ F (x) w nast¦puj¡cy sposób:

F (x + h) ≈ F (x) + hF

0

(x).

(3.9)

Szukamy h minimalizuj¡cego norm¦ L

2

, a co za tym idzie funkcj¦:

E(h) =

X

x

[F (x + h) − G(x)]

2

.

(3.10)

Minimum funkcji E(h) szukamy poprzez ró»niczkowanie wzgl¦dem h:

0 =

∂E

∂h

(3.11)

≈

∂

∂h

X

x

[F (x + h) − G(x)]

2

(3.12)

=

X

x

2F

0

(x)[F (x) + hF

0

(x) − G(x)].

(3.13)

St¡d otrzymujemy:

h(x) ≈

P

x

F

0

(x)[G(x) − F (x)]

P

x

[F

0

(x)]

2

(3.14)

=

P

x

[F

0

(x)]

2

[G(x)−F (x)]

F

0

(x)

P

x

[F

0

(x)]

2

.

(3.15)

Jak ªatwo zauwa»y¢, otrzymali±my rozwi¡zanie analogiczne do (3.6), lecz z funkcj¡

wagow¡ postaci [F

0

(x)]

2

.

Forma iteracyjna ma posta¢:

h

0

= 0

(3.16)

h

1

= h

k

+

P

x

w(x)F

0

(x + h

k

)[G(x) − F (x + h

k

)]

P

x

w(x)F

0

(x + h

k

)

2

,

(3.17)

gdzie w(x) dane jest wzorem (3.5).

Mo»emy teraz dokona¢ uogólnienia algorytmu dla przypadku wielowymiarowego. Mi-

nimalizujemy wi¦c bª¡d:

E(h) =

X

x

[F (x + h) − G(x)]

2

,

(3.18)

gdzie x oraz h to n-wymiarowe wektory.

Dokonujemy przybli»enia liniowego analogicznego do (3.9):

F (x + h) = F (x) + h

T

∂

∂x

F (x),

(3.19)

gdzie

∂

∂x

to operator gradientu wzgl¦dem x:

∂

∂x

= [

∂

∂x

1

,

∂

∂x

2

, . . . ,

∂

∂x

n

]

T

(3.20)

24

Opis implementacji

Minimalizujemy funkcj¦ bª¦du:

0 =

∂

∂h

E

(3.21)

=

∂

∂h

X

x

[F (x) + h

T

∂F

∂x

− G(x)]

2

(3.22)

=

X

x

2

∂F

∂x

[F (x) + h

T

∂F

∂x

− G(x)],

(3.23)

st¡d:

h ≈

"

X

x

(

∂F

∂x

)

T

[G(x) − F (x)]

# "

X

x

(

∂F

∂x

)

T

(

∂F

∂x

)

#

−1

.

(3.24)

Forma iteracyjna ma posta¢ analogiczn¡, jak dla przypadku jednowymiarowego.

3.2.3 Parametry sylwetki

Zaproponowane w pracy [10] oraz zebrane w tabeli 2.2 parametry wyliczane s¡ na bazie

momentów geometrycznych wydzielonych sylwetek (sylwetki binarnej, pola ruchu oraz

jego skªadowych: poziomej i pionowej). Do ich wyznaczenia wykorzystaªem funkcje za-

implementowane w bibliotece OpenCV :

•

cvMoments- wyznacza momenty od zerowego do trzeciego rz¦du dla wskazanej syl-

wetki i zapisuje ich warto±ci w strukturze typu CvMoments (równie» zdeniowanej

w OpenCV

•

cvGetSpatialMoment- zwraca warto±¢ wybranego momentu zachowanego we wska-

zanej strukturze typu CvMoments

•

cvGetCentralMoment- zwraca warto±¢ wybranego momentu centralnego zachowa-

nego we wskazanej strukturze typu CvMoments

Momenty geometryczne
Momenty geometryczne sªu»¡ do parametryzacji ksztaªtu sylwetki. I tak moment rz¦du
p + q

zdeniowany jest jako:

m

p,q

=

Z

x

Z

y

x

p

y

q

I(x, y)dxdy,

(3.25)

lub dla przypadku dyskretnego:

m

p,q

=

X

x

X

y

x

p

y

q

I(x, y),

(3.26)

gdzie:

• (x, y)

- poªo»enie danego piksela,

• I(x, y)

- przyjmuje

0

1

0

lub

0

0

0

w zale»no±ci od tego, czy piksel (x, y) nale»y do sylwetki

czy te» nie(dla obrazu binarnego) lub warto±¢ jasno±ci piksela poªo»onego w punkcie
(x, y)

(dla obrazu w skali szaro±ci).

3.2 Wyznaczenie parametrów chodu czªowieka

25

Šatwo zauwa»y¢, »e moment rz¦du zerowego:

m

0,0

=

X

x

X

y

I(x, y)

(3.27)

dla obrazu binarnego przyjmuje warto±¢ równ¡ powierzchni zajmowanej przez sylwetk¦

wyra»on¡ w pikselach.

Momenty rz¦du pierwszego natomiast, w poª¡czeniu z momentem rz¦du zerowego,

pozwalaj¡ na wyliczenie ±rodka ci¦»ko±ci u

s

sylwetki:

u

s

= (x

s

, y

s

),

(3.28)

gdzie:

x

s

=

m

1,0

m

0,0

,

(3.29)

y

s

=

m

0,1

m

0,0

.

(3.30)

Momenty rz¦du pierwszego ªatwo wyznaczy¢ na podstawie wzoru (3.25) jako:

m

1,0

=

Z

x

Z

y

xI(x, y)dxdy,

(3.31)

m

0,1

=

Z

x

Z

y

yI(x, y)dxdy,

(3.32)

lub dla przypadku dyskretnego, ze wzoru (3.26):

m

1,0

=

X

x

X

y

xI(x, y),

(3.33)

m

0,1

=

X

x

X

y

yI(x, y).

(3.34)

Momenty centralne
Wa»ne informacje z punktu widzenia dziaªania implementowanego algorytmu nios¡ ze

sob¡ równie» momenty centralne. Ich warto±ci s¡ niezale»ne od poªo»enia sylwetki na

obrazie i s¡ wykorzystywane do okre±lenia orientacji sylwetki. Zdeniowane s¡ jako:

µ

p,q

=

Z

x

Z

y

(x − x

s

)

p

(y − y

s

)

q

I(x, y)dxdy,

(3.35)

lub w wersji dla przypadku dyskretnego:

µ

p,q

=

X

x

X

y

(x − x

s

)

p

(y − y

s

)

q

I(x, y),

(3.36)

gdzie (x

s

, y

s

)

- wspóªrz¦dne ±rodka sylwetki.

Z pomoc¡ momentów centralnych mo»na ªatwo wyliczy¢ moment bezwªadno±ci syl-

wetki wzgl¦dem zadanej prostej [15]:

µ

θ

= µ

2,0

sin

2

θ − 2µ

1,1

cos θ sin θ + µ

0,2

cos

2

θ,

(3.37)

gdzie:

26

Opis implementacji

• µ

θ

- moment bezwªadno±ci sylwetki wzgl¦dem prostej nachylonej pod k¡tem θ do

osi x,

• µ

0,2

, µ

2,0

, µ

1,1

- momenty centralne drugiego rz¦du (do wyliczenia na podstawie

wzoru (3.35) lub (3.36)).

Minimalizuj¡c warto±¢ µ

θ

poprzez zró»niczkowanie jej wzgl¦dem θ i przyrównanie

otrzymanego wyniku do zera, otrzymamy wzór na k¡t nachylenia osi gªównej sylwetki

(prosta, wzgl¦dem której sylwetka ma najmniejszy moment bezwªadno±ci) [15]:

θ =

1

2

arctan

2µ

1,1

µ

2,0

− µ

0,2

.

(3.38)

3.2.4 Wektor cech

Na podstawie momentów geometrycznych oraz momentów centralnych wyliczany jest wek-

tor cech charakteryzuj¡cych wydzielone sylwetki (binarn¡, skªadow¡ poziom¡ oraz pio-

now¡ pola ruchu, caªkowite pole ruchu). Jego skªadowe maj¡ charakter analogiczny do

parametrów zaproponowanych przez autorów pracy [10], zebranych w tabeli 2.2:

• x

c

- wspóªrz¦dna ±rodka sylwetki binarnej, skªadowa pozioma

• y

c

- wspóªrz¦dna ±rodka sylwetki binarnej, skªadowa pionowa

• x

wc

- wspóªrz¦dna ±rodka sylwetki pola ruchu, skªadowa pozioma

• y

wc

- wspóªrz¦dna ±rodka sylwetki pola ruchu, skªadowa pionowa

• x

d

- ró»nica x

wc

− x

c

• y

d

- ró»nica y

wc

− y

c

• a

c

- stosunek momentu minimalnego do maksymalnego sylwetki binarnej

• a

wc

- stosunek momentu minimalnego do maksymalnego pola ruchu

• a

d

- ró»nica a

c

− a

wc

• x

uwc

- wspóªrz¦dna ±rodka skªadowej poziomej pola ruchu, skªadowa pozioma

• y

uwc

- wspóªrz¦dna ±rodka skªadowej poziomej pola ruchu, skªadowa pionowa

• x

vwc

- wspóªrz¦dna ±rodka skªadowej pionowej pola ruchu, skªadowa pozioma

• y

vwc

- wspóªrz¦dna ±rodka skªadowej pionowej pola ruchu, skªadowa pionowa

W sensie implementacyjnym, ka»dy z wymienionych elementów ma posta¢ tablicy liczb

typu double. W ka»dym kroku (dla ka»dej klatki sekwencji) wyliczane s¡ warto±ci ka»dej

cechy i dopisywane na kolejne miejsce tablicy. Otrzymujemy wi¦c przebiegi ich zmian w

czasie.

3.2 Wyznaczenie parametrów chodu czªowieka

27

a)

b)

Rysunek 3.3: Przebieg zmian parametru x

uwc

uzyskany bezpo±rednio z przykªadowej se-

kwencji (a) oraz przebieg uzyskany po odj¦ciu od niego skªadowej liniowej (b).

3.2.5 Zmiany parametrów poªo»enia poziomego

Jak ªatwo zauwa»y¢ (rysunek 3.3a), parametry zwi¡zane ze zmianami skªadowej pozio-

mej poªo»enia jednej z sylwetek (x

c

, x

wc

, x

uwc

oraz x

vwc

) maj¡ du»¡ skªadow¡ liniow¡

zwi¡zan¡ z poruszaniem si¦ czªowieka po scenie. Musimy j¡ uwzgl¦dni¢, aby wyznaczy¢

cz¦stotliwo±¢ zmian sygnaªu.

Do wyznaczenia parametrów liniowego tªa wykorzystaªem regresj¦ liniow¡ [1]. Me-

toda ta pozwala mi¦dzy innymi na znalezienie prostej opisanej wzorem y = ax + b, jak

najlepiej dopasowanej do zbioru punktów (x

1

, y

1

) . . . (x

N

, y

N

)

, pod k¡tem zadanego kry-

terium. Najcz¦±ciej wykorzystywana jest metoda najmniejszych kwadratów, dlatego te»

zdecydowaªem si¦ na jej u»ycie.

Regresja liniowa z u»yciem metody najmniejszych kwadratów

Poszukujemy funkcji f(x) = ax + b najlepiej przybli»aj¡c¡ zadane punkty. Niech funkcj¡

bª¦du b¦dzie:

χ

2

(a, b) =

n

X

i=1

(y

i

− ax

i

− b)

2

,

(3.39)

gdzie:

• (x

i

, y

i

)

- wspóªrz¦dne i-tego punktu

• a

, b- wspóªczynniki poszukiwanej funkcji liniowej postaci f(x) = ax + b

Poszukujemy minimum funkcji bª¦du poprzez przyrównanie jej pochodnej do zera:

∂χ

2

∂b

= −2

n

X

i=1

(y

i

− ax

i

− b) = 0

(3.40)

∂χ

2

∂a

= −2

n

X

i=1

x

i

(y

i

− ax

i

− b) = 0

(3.41)

28

Opis implementacji

Te same równania mo»na przepisa¢ w wygodniejszej do wyliczenia postaci. Zdeniujmy

nast¦puj¡ce zmienne:

S

=

n

X

i=1

1,

(3.42)

S

x

=

n

X

i=1

x

i

,

(3.43)

S

y

=

n

X

i=1

y

i

,

(3.44)

S

xx

=

n

X

i=1

x

2
i

,

(3.45)

S

xy

=

n

X

i=1

x

i

y

i

.

(3.46)

Z ich pomoc¡ mo»emy zapisa¢ równania (3.40)-(3.41) jako:

aS

x

+ bS

= S

y

,

(3.47)

aS

xx

+ bS

x

= S

xy

.

(3.48)

Po ich rozwi¡zaniu otrzymamy wspóªczynniki poszukiwanej funkcji:

a =

S

x

S

y

− SS

xy

∆

,

(3.49)

b =

S

x

S

xy

− S

xx

S

y

∆

,

(3.50)

gdzie:

∆ = S

2

x

− SS

xx

.

(3.51)

Po odj¦ciu liniowego tªa od wspomnianych sygnaªów, uzyskaªem okresowe przebiegi ich

zmian. Przykªadowy wynik takiej operacji przedstawiªem na rysunku 3.3b.

3.2.6 Obliczanie cz¦stotliwo±ci

Jak wspomniaªem wcze±niej, implementowany algorytm ma sªu»y¢ jedynie do lokalizacji

pieszych (a nie identykacji konkretnych osób) na podstawie parametrów ruchu obiektów

widocznych na sekwencji obrazów. Jako zmienn¡ decyzyjn¡ postanowiªem wybra¢ cz¦sto-

tliwo±¢ zmian poszczególnych cech sylwetki. Jako »e szczególna precyzja nie jest konieczna

(nie jest interesuj¡ce przesuni¦cie fazowe sygnaªów), do jej wyliczenia postanowiªem u»y¢

transformacji Fouriera.

Transformacja Fouriera
Transformacja Fouriera jest liniowym operatorem przeksztaªcaj¡cym funkcj¦ ci¡gª¡ w inn¡

funkcj¦ ci¡gª¡. Pozwala ona na przeksztaªcenie przebiegu czasowego na ci¡gªe widmo jego

skªadowych cz¦stotliwo±ci, czyli na transformacj¦ funkcji z dziedziny czasu do dziedziny

cz¦stotliwo±ci.

3.2 Wyznaczenie parametrów chodu czªowieka

29

Transformata (wynik transformacji) Fouriera zapisywana jest jako:

ˆ

f (ω) =

1

√

2π

Z

∞

−∞

f (t)e

−iωt

dt,

(3.52)

gdzie:

• ω

- cz¦sto±¢ koªowa,

• ˆ

f (ω)

- transformata Fouriera,

• f (t)

- funkcja bazowa,

• i

- jednostka urojona.

Dyskretna transformacja Fouriera jest wersj¡ transformacji Fouriera dla sygnaªu dys-

kretnego (próbkowanego). Przeksztaªca sko«czony ci¡g próbek (a

0

, a

1

, . . . , a

N −1

)

, a

i

∈ R

w ci¡g harmonicznych (A

0

, A

1

, . . . , A

N

− 1)

, A

i

∈ C

w nast¦puj¡cy sposób:

A

n

=

N −1

X

k=0

a

k

ω

−kn

N

,

(3.53)

gdzie:

• 0 ≤ n ≤ N − 1

,

• ω

N

= e

i

2π

N

,

• i

- jednostka urojona,

• n

- numer harmonicznej,

• k

- numer próbki sygnaªu,

• a

k

- warto±¢ próbki sygnaªu,

• N

- liczba próbek.

Wzór (3.53) mo»na zapisa¢ w sposób macierzowy:

A = M a,

(3.54)

gdzie:

A =








A

0

A

1

...

A

N −1








,

(3.55)

M

=








ω

−0·0

N

ω

−1·0

N

. . .

ω

−(N −1)·0

N

ω

−0·1

N

ω

−1·1

N

. . .

ω

−(N −1)·1

N

...

...

...

...

ω

−0·(N −1)

N

ω

−1·(N −1)

N

. . .

ω

−(N −1)·(N −1)

N








,

(3.56)

a =








a

0

a

1

...

a

N −1








.

(3.57)

30

Opis implementacji

Jak ªatwo dowie±¢, wyliczenie transformaty w tej formie (mno»enie macierzy przez

wektor) ma zªo»ono±¢ obliczeniow¡ O(N

2

)

. Dzi¦ki zastosowaniu pewnej sztuczki algoryt-

micznej w postaci techniki rekurencyjnej dziel i zwyci¦»aj mo»liwe jest przyspieszenie jej

wyliczania do zªo»ono±ci O(NlogN) [14].

Do obliczania transformaty Fouriera wykorzystaªem funkcje z biblioteki GNU Scien-

tic Library [14]. Wynikiem transformacji Fouriera dla sygnaªu rzeczywistego o dªugo±ci
N

jest tablica

N

2

liczb zespolonych reprezentuj¡ca kolejne cz¦stotliwo±ci.

W celu znalezienia cz¦stotliwo±ci dominuj¡cej szukamy tej, która ma najwi¦ksz¡ moc

wyra»on¡ wzorem:

P (c) = Re(c)

2

+ Im(c)

2

.

(3.58)

3.3 Badania algorytmu

3.3.1 Badania skuteczno±ci dziaªania

Badania polegaªy na uruchomieniu programu podaj¡c jako dane wej±ciowe kolejne lmy

z bazy danych CASIA Gait Database. Program zapisywaª w ka»dym kroku (dla ka»dej

klatki sekwencji) do jednego pliku aktualne warto±ci poszczególnych parametrów sylwetek

oraz do drugiego- warto±ci cz¦stotliwo±ci ich zmian wyliczone na podstawie posiadanej

ilo±ci próbek.

W pierwszym etapie przebadane zostaªo ponad 1200 sekwencji przedstawiaj¡cych ludzi

przechodz¡cych w pªaszczy¹nie prostopadªej do statycznej kamery.

Na rysunku 3.4 przedstawiªem zestaw przebiegów zmian parametrów sylwetek id¡cego

czªowieka. Pochodz¡ one z losowo wybranej spo±ród przebadanych sekwencji z czªowie-

kiem id¡cym w pªaszczy¹nie prostopadªej do osi kamery. Dodatkowo, nad ka»dym wy-

kresem znajduje si¦ warto±¢ cz¦stotliwo±ci zmian parametrów wyliczonych w programie z

u»yciem DFT.

Ju» na podstawie obserwacji tych przebiegów wida¢, »e nie wszystkie parametry b¦d¡

odpowiednie do wyznaczania cz¦stotliwo±ci id¡cego czªowieka. Wi¦kszo±¢ parametrów

jednak daªo dobry, powtarzalny wynik (okoªo 2Hz) oraz wykazuj¡ ewidentn¡ okresowo±¢

zmian.

Niesatysfakcjonuj¡cy okazaª si¦ przebieg parametru x

c

(skªadowa pozioma poªo»enia

±rodka ci¦»ko±ci sylwetki binarnej). Nie do±¢, »e cz¦stotliwo±¢ jego zmian wyliczona przez

program (0.42Hz) odbiega od cz¦stotliwo±ci wi¦kszo±ci parametrów, to wyra¹nie wida¢,

»e przebieg nie jest okresowy. Widoczny jest jednak ksztaªt, który zdaje si¦ powtarza¢

równie» na innych wykresach skªadowych poziomych ±rodków ci¦»ko±ci sylwetek (x

wc

,

x

uwc

, x

vwc

). Tam jest jednak sªabiej dostrzegalny z powodu silnych okresowych zmian

sygnaªu o cz¦stotliwo±ci 2Hz. Pojawienie si¦ takiego ksztaªtu mo»e by¢ spowodowane

wyst¦powaniem dodatkowej cz¦stotliwo±ci b¦d¡cej wynikiem aliasingu ramek.

1

Niesatysfakcjonuj¡cy okazaª si¦ tak»e przebieg parametru a

d

. Jego warto±¢ stanowi

ró»nica a

c

− a

wc

. Obie skªadowe ró»nicy daªy dobry wynik. Po odj¦ciu najwyra¹niej

zredukowana zostaªa najsilniejsza skªadowa i/lub wzmocniªa si¦ cz¦stotliwo±¢ dwukrot-

nie wi¦ksza. Wizualnie przebieg wydaje si¦ by¢ bardzo zaszumiony i nie wykazuje tak

wyra¹nej okresowo±ci, jak inne parametry.

1

Oprócz cz¦stotliwo±ci chodu czªowieka, ustalonej eksperymentalnie na okoªo 2Hz, wyst¦puje równie»

cz¦stotliwo±¢ zwi¡zana z dyskretn¡ natur¡ lmu (25 ramek na sekund¦, czyli 0.04Hz). Nakªadanie si¦

tych cz¦stotliwo±ci powoduje wªa±nie aliasing.

3.3 Badania algorytmu

31

a) x

c

, f = 0.42Hz

b) y

c

, f = 2.11Hz

c) x

wc

, f = 2.11Hz

d) y

wc

, f = 2.11Hz

e) x

d

, f = 2.11Hz

f) y

d

, f = 2.11Hz

g) a

c

, f = 2.11Hz

h) a

wc

, f = 2.11Hz

i) a

d

, f = 3.38Hz

j) x

uwc

, f = 2.11Hz

k) y

uwc

, f = 2.11Hz

l) x

vwc

, f = 2.11Hz

m) y

vwc

, f = 2.11Hz

Rysunek 3.4: Przebiegi zmian parametrów sylwetek wraz z wyznaczon¡ za pomoc¡ szyb-

kiej transformacji Fouriera cz¦stotliwo±ci¡ dla przykªadowej sekwencji z id¡cym czªowie-

kiem.

32

Opis implementacji

Pozostaªe jedena±cie parametrów daªo jednakowy wynik cz¦stotliwo±ci: 2.11Hz. Taka

zbie»no±¢ wyników nie jest niczym dziwnym i wynika z dyskretnego charakteru przebie-

gów.

Dodatkowo na podstawie wykresów mo»na zauwa»y¢ ró»nice w fazie niektóryuch sy-

gnaªów. Przypomn¦, »e w oryginalnej wersji algorytmu, zaprezentowanej w pracy [10],

ich warto±ci stanowiªy podstaw¦ do identykacji osób. I tak, na przykªad, na pocz¡tku

przykªadowej sekwencji, sygnaªy x

wc

czy y

wc

maj¡ warto±¢ maksymaln¡, x

d

- prawie mini-

maln¡, a y

c

znajduje si¦ w okolicach ±rodka zbocza.

Mo»na równie» zaobserwowa¢ ró»nice w ksztaªcie przebiegów poszczególnych parame-

trów: y

c

jest dosy¢ gªadkie, a

c

jest do±¢ gªadkie w okolicach miniumum i ma wyra¹ne

szpice dla warto±ci maksymalnych, a y

uwc

ma szpilki dla warto±ci najmniejszych i po-

szarpane, lecz do±¢ dªugie grzbiety dla najwi¦kszych. Te wªasno±ci nie miaªy bezpo±red-

niego znaczenia dla algorytmu rozpoznawania, lecz uwa»am, »e ich analiza dla konkretnej

osoby mo»e pozwoli¢ na wykrywanie pewnych cech charakterystycznych (na przykªad wad

ruchu). Wykracza to jednak poza zakres niniejszej pracy.

Na rysunku 3.5 przedstawiªem histogramy oraz podstawowe wªasno±ci statystyczne

rozkªadów cz¦stotliwo±ci badanych parametrów dla caªej serii sekwencji wej±ciowych (po-

nad 1200 lmów). Na ich podstawie mo»na wybra¢ najbardziej wiarygodne cechy.

Histogram cz¦stotliwo±ci x

c

potwierdziª wniosek o maªej przydatno±ci tego parametru.

Warto±¢ ±rednia oraz maksimum przypadªo dla cz¦stotliwo±ci okoªo 0.5Hz. Sk¡d taka

warto±¢? Wynika ona ze sposobu wyliczania cz¦stotliwo±ci przy u»yciu DF T . Metoda ta

zakªada bowiem, »e badany fragment sygnaªu (okno) stanowi cz¦±¢ przebiegu skªadaj¡cego

si¦ z jego ci¡gªych powtórze«. Je±li wi¦c nie zostanie wykryta wi¦ksza cz¦stotliwo±¢, to

wynikiem b¦dzie f =

1

t

, gdzie t- czas trwania badanego fragmentu przebiegu (szeroko±¢

okna). Badane sekwencje miaªy dªugo±¢ okoªo 50 klatek, czyli (dla 25 ramek na sekund¦)

2 sekund. Je±li nie wyst¡piªa wi¦ksza cz¦stotliwo±¢, to wynikiem byªo:

1

2s

= 0.5Hz

. I

tak byªo w przypadku x

c

. Nie wykazaª on charakteru okresowego. Parametr ten jednak

przydaª si¦ do wyeliminowania cz¦stotliwo±ci zwi¡zanej z aliasingiem ramek z sygnaªu x

d

,

który stanowi ró»nic¦ x

wc

− x

c

.

Równie» drugi wskazany wcze±niej parametr, a

d

okazaª si¦ nie do±¢ dobry. Podobnie,

jak na przykªad dla y

uwc

i x

uwc

otrzymaªem rozkªad wielomodalny. W niektórych przypad-

kach dla tych parametrów silniejsze okazaªy si¦ cz¦stotliwo±ci dwukrotnie wi¦ksze (okoªo
4Hz

) lub dwukrotnie mniejsze (okoªo 1Hz) ni» oczekiwana (okoªo 2Hz). Nie mo»na wi¦c

na nich w peªni polega¢.

Najlepsze wyniki daª parametr x

d

. Z warto±ci¡ ±redni¡ 2.02Hz, odchyleniem standar-

sowym wynosz¡cym 0.21Hz i spójn¡ struktur¡ histogramu stanowiª bardzo dobr¡ cech¦

do obliczania cz¦stotliwo±ci poruszaj¡cego si¦ obiektu. Je±li ustaliliby±my warunek na
x

d

∈ [1.5Hz; 2.5Hz]

, to uzyskaliby±my niemal 100% skuteczno±¢ wykrywania czªowieka

na badanych sekwencjach.

Niewiele gorsze okazaªy si¦ parametry a

c

(warto±¢ ±rednia: 1.99Hz, odchylenie stan-

dardowe: 0.29Hz) oraz a

wc

(warto±¢ ±rednia: 1.99Hz, odchylenie standardowe: 0.33Hz).

Tylko dla niewielkiej liczby przypadków ich cz¦stotliwo±¢ wyniosªa okoªo 0.5Hz (nie wy-

kazaªy charakteru okresowego). S¡ to bardzo cenne parametry z punktu widzenia popraw-

nego rozpoznawania poruszaj¡cego si¦ obiektu jako id¡cego czªowieka. Poza informacj¡

o cz¦stotliwo±ci nios¡ ze sob¡ równie» wiedz¦ o ksztaªcie obiektu (jego proporcje), któr¡

mogliby±my z nich pozyska¢, na przykªad jako warto±¢ ±redni¡ sygnaªu. Pozwoliªoby

to wyeliminowa¢ obiekty o innych proporcjach ksztaªtu ni» czªowiek (np. odbijaj¡ca si¦

piªka).

Reasumuj¡c, na podstawie analizy wyników przeprowadzonych bada« stwierdzam, »e

3.3 Badania algorytmu

33

a) x

c

, m = 0.47, s = 0.20

b) y

c

, m = 1.86, s = 0.52

c) x

wc

, m = 1.83, s = 0.59

d) y

wc

, m = 2.34, s = 0.92,

e) x

d

, m = 2.02, s = 0.21

f) y

d

, m = 2.30, s = 0.98

g) a

c

, m = 1.99, s = 0.29

h) a

wc

, m = 1.99, s = 0.33

i) a

d

, m = 2.98, s = 1.70

j) x

uwc

, m = 1.94, s = 0.47

k) y

uwc

, m = 2.07, s = 1.26

l) x

vwc

, m = 1.64, s = 0.66

m) y

vwc

, m = 2.28, s = 0.80

Rysunek 3.5: Histogramy wyst¡pie« danych cz¦stotliwo±ci dla wszystkich parametrów

oraz ich podstawowe wªasno±ci statystyczne: m- warto±¢ ±rednia, s- odchylenie standar-

dowe.

34

Opis implementacji

najlepszymi parametrami do rozpoznawania pieszych na podstawie sposobu, w jaki si¦

poruszaj¡, s¡: x

d

, a

c

oraz a

wc

.

3.3.2 Wpªyw k¡ta osi kamery wzgl¦dem pªaszczyzny ruchu

Na rysunku 3.7 przedstawiªem zestaw histogramów wyników cz¦stotliwo±ci trzech wybra-

nych parametrów (x

d

, a

c

, a

wc

) dla sekwencji kr¦conych pod k¡tem 72 stopni oraz 108

stopni (patrz. rysunek 3.6). Dla porównania zamie±ciªem równie» histogramy wyliczone

wcze±niej dla k¡ta 90 stopni.

Rysunek 3.6: Wizualizacja sceny u»ytej do przeprowadzania eksperymentu.

Šatwo zauwa»y¢, »e wyniki uzyskane dla k¡ta 72 stopni nie tylko si¦ nie pogorszyªy, lecz

wr¦cz s¡ nieco lepsze ni» dla 90 stopni. Co prawda ±rednia nieco si¦ podniosªa, a odchylenie

standardowe nieznacznie si¦ powi¦kszyªo (patrz. tabela 3.2); na podstawie histogramów

stwierdzam, »e nie tyle s¡ one szersze, ile zmieniª si¦ rozkªad masy wewn¡trz nich- wyszªo

wi¦cej wyników na ich brzegach), lecz niemal caªkowicie wyeliminowane zostaªy sytuacje,

gdy parametry (szczególnie a

c

i a

wc

) nie wykazywaªy charakteru okresowego.

Dla k¡ta 108 stopni warto±ci ±rednie byªy podobne jak dla 72 stopni. Mimo mniej-

szego odchylenia standardowego, wi¦cejsekwencji daªo niepoprawny wynik cz¦stotliwo±ci

parametrów a

c

i a

wc

.

Wyniki uzyskane dla sekwencji kr¦conych z k¡ta 72 stopni i 108 stopni (18-stopniowe

odchylenie) s¡ satysfakcjonuj¡ce. Zarówno wygl¡d histogramu, jak i wªasno±ci staty-

styczne otrzymanych rezultatów nie odbiegaj¡ od uzyskanych dla lmów z czªowiekiem

przechodz¡cym w pªaszczy¹nie prostopadªej do osi kamery.

Na rysunku 3.8 przedstawiªem histogramy przedstawiaj¡ce wyniki uzyskane dla wy-

branych wcze±niej parametrów na podstawie sekwencji kr¦conych pod k¡tem 54 i 126

stopni oraz 90 stopni (dla porównania).

3.3 Badania algorytmu

35

Bardzo wyra¹ne s¡ wysokie sªupki na cz¦stotliwo±ci 12.5Hz. Jest to maksymalna cz¦-

stotliwo±¢, jak¡ mogªaby wykry¢ transformacja Fouriera dla przebadanych próbek (po-

ªowa cz¦stotliwo±ci próbkowania sygnaªu wynosz¡cej 25Hz). Najprawdopodobniej jest

ona zwi¡zana z niedoskonaªo±ci¡ pobierania obrazów (szybkie zmiany mi¦dzy kolejnymi

ramkami). Zmiany te, dla sekwencji kr¦conych z 36-stopniowym odchyleniem najwyra¹-

niej s¡ bardziej znacz¡ce, ni» cz¦stotliwo±¢ ruchu czªowieka.

Dodatkowo, szczególnie dla odchylenia 54 stopni, wida¢ znaczn¡ ilo±¢ maªych sªupków

poza przedziaªem [1.5Hz; 2.5Hz]. W wyniku tego nast¡piª znaczny spadek skuteczno±ci

algorytmu.

a) x

d

, k¡t: 90

◦

b) a

c

, k¡t: 90

◦

c) a

wc

, k¡t: 90

◦

d) x

d

, k¡t: 72

◦

e) a

c

, k¡t: 72

◦

f) a

wc

, k¡t: 72

◦

g) x

d

, k¡t: 108

◦

h) a

c

, k¡t: 108

◦

i) a

wc

, k¡t: 108

◦

Rysunek 3.7: Histogramy wyst¡pie« danych cz¦stotliwo±ci dla sekwencji kr¦conych pod

k¡tem 90(a-c), 72(d-f) oraz 108(g-i) stopni, dla trzech wybranych parametrów oraz ich

podstawowe wªasno±ci statystyczne: m- warto±¢ ±rednia, s- odchylenie standardowe.

3.3.3 Badanie pr¦dko±ci dziaªania algorytmu

Do bada« nad pr¦dko±ci¡ dziaªania zaimplementowanego algorytmu wykorzystaªem cztery

komputery w konguracji sprz¦towej przedstawionej w tabeli 3.1, pracuj¡ce pod systemem

36

Opis implementacji

a) x

d

, k¡t: 90

◦

b) a

c

, k¡t: 90

◦

c) a

wc

, k¡t: 90

◦

d) x

d

, k¡t: 54

◦

e) a

c

, k¡t: 54

◦

f) a

wc

, k¡t: 54

◦

g) x

d

, k¡t: 126

◦

h) a

c

, k¡t: 126

◦

i) a

wc

, k¡t: 126

◦

Rysunek 3.8: Histogramy wyst¡pie« danych cz¦stotliwo±ci dla sekwencji kr¦conych pod

k¡tem 90(a-c), 54(d-f) oraz 126(g-i) stopni, dla trzech wybranych parametrów oraz ich

podstawowe wªasno±ci statystyczne: m- warto±¢ ±rednia, s- odchylenie standardowe.

Tablica 3.2: Zestawienie wªasno±ci statystycznych wybranych parametrów dla sekwencji

nakr¦conych z ró»nych k¡tów, m- warto±¢ ±rednia, s- odchylenie standardowe.

k¡t

x

d

a

c

a

wc

m [Hz] s [Hz] m [Hz] s [Hz] m [Hz] s [Hz]

90 stopni

2.02

0.21

1.99

0.29

1.99

0.33

72 stopni

2.06

0.42

2.07

0.40

2.09

0.37

108 stopni

2.11

0.24

2.07

0.24

2.08

0.26

54 stopni

2.94

3.07

2.95

3.17

2.88

3.05

126 stopni

2.26

1.36

2.21

1.37

2.19

1.45

3.3 Badania algorytmu

37

operacyjnym Debian Etch. Na potrzeby testów napisaªem cztery ró»ne wersje algorytmu:

1. Wersja bez zmian (n). Liczone jest wszystkie 13 parametrów oraz cz¦stotliwo±ci ich

zmian.

2. Wersja bez zmian z wizualizacj¡ (nw). Liczone jest wszystkie 13 parametrów oraz

cz¦stotliwo±ci ich zmian. Dodatkowo w ka»dym kroku wy±wietlana jest klatka z

sylwetk¡ binarn¡.

3. Wersja przyspieszona (p). Liczy tylko niezb¦dne parametry oraz cz¦stotliwo±ci ich

zmian.

4. Wersja przyspieszona z wizualizacj¡(pw). Liczy tylko niezb¦dne parametry oraz

cz¦stotliwo±ci ich zmian. Dodatkowo w ka»dym kroku wy±wietlana jest klatka z

sylwetk¡ binarn¡.

Na ka»dym z czterech komputerów, ka»dy z wymienionych algorytmów testowany

byª z wykorzystaniem jako danych wej±ciowych pi¦ciu ró»nych sekwencji. Ka»da próba

powtarzana byªa dziesi¦ciokrotnie. Nast¦pnie odrzucone zostaªy wyniki minimalne oraz

maksymalne, a z pozostaªych o±miu wyliczony zostaª czas ±redni. Wyniki testów zamiesz-

czone zostaªy w tabeli 3.3.

Dla ka»dej sekwencji wej±ciowej, oprócz jej dªugo±ci, zamieszczony zostaª czas obecno-

±ci czªowieka na scenie, liczony od momentu, gdy sylwetka binarna oderwie si¦ od jednej

kraw¦dzi ramki lmu, do chwili gdy dotknie kraw¦dzi przeciwlegªej. Jest to czas o tyle

istotny, »e tylko wtedy liczone s¡ wszystkie parametry sylwetek.

Bardzo sªabe wyniki algorytm osi¡gn¡ª na komputerze Chili. Czas dziaªania byª okoªo

pi¦ciokrotnie dªu»szy, ni» czas badanej sekwencji. Z moich obserwacji wynika, »e pro-

blem ten jest skutkiem przede wszystkim zbyt du»ych wymaga« programu co do pami¦ci.

Komputer ma do wykorzystania jedynie 128MB RAM. W czasie pracy algorytmu zakres

ten byª przekraczany

2

. Niezb¦dne wi¦c byªo skªadowanie cz¦±ci danych na dysk twardy,

do partycji wymiany (swap). Powodowaªo to znaczne spowolnienie pracy programu.

O wiele lepsze wyniki osi¡gni¦te zostaªy ju» na komputerze Frytka. Dla tej kongu-

racji sprz¦towej czasy pracy algorytmu byªy o okoªo 0.5s dªu»sze od dªugo±ci badanych

sekwencji.

Na komputerze Enterprise czas pracy programu byª ju» o okoªo 0.5s, a na komputerze

Klocek o okoªo 1.5s krótszy, ni» dªugo±¢ sekwencji. Na tych komputerach metoda mogªaby

dziaªa¢ w czasie rzeczywistym (nawet z wizualizacj¡ pracy algorytmu).

Na podstawie uzyskanych wyników wida¢ wyra¹nie, »e wizualizacja pracy algorytmu

wyra¹nie spowalnia jego prac¦. Wyj¡tkiem od tej reguªy jest przyspieszona wersja me-

tody na komputerze Klocek. W tym przypadku nie jest to widoczne, a nawet wersja z

wizualizacj¡ daªa lepsze wyniki.

Interesuj¡ce jest równie» stosunkowo maªe przyspieszenie algorytmu. Najbardziej cza-

sochªonne jest wyliczanie sylwetek, a nie samych ich parametrów. W przyspieszonej wersji

konieczne jest wyliczenie wszystkich czterech. Aby uzyska¢ wi¦ksz¡ akceleracj¦ nale»a-

ªoby wybra¢ tylko jeden parametr. Najlepszy zdaje si¦ by¢ a

c

, gdy» wymaga on policzenia

tylko jednej sylwetki (binarnej).

Nale»y zwróci¢ uwag¦ na orientacyjny charakter uzyskanych wyników. Dla ka»dego

przypadku ró»nice w uzyskanych czasach byªy do±¢ du»e. Zdarzaªy si¦ bowiem wyniki

2

Nie zapominajmy, »e testy byªy przeprowadzane na zwykªych komputerach u»ywanych na codzie«

jako komputery biurkowe. Pracowaªy wi¦c na nich ró»ne programy oraz demony niezb¦dne w codziennej

pracy (system X-Window. ftpd i wiele innych).

38

Opis implementacji

znacznie odbiegaj¡ce od pozostaªych. Zastosowana metoda liczenia ±redniej po odrzuceniu

warto±ci minimalnej oraz maksymalnej tylko cz¦±ciowo rekompensuje te niedokªadno±ci.

3.3 Badania algorytmu

39

Tablic

a

3.3:

Zesta

wienie

cz

asó

w

dz

iaªania

ró»n

yc

h

w

ersji

algorytm

u

na

ró»n

yc

h

konguracjac

h

sprz¦to

wyc

h

komputera.

W

szystkie

czasy

w

sekundac

h.

L.p.

Dªugo±¢ lm

u

Czas ob

ecno±ci

Chili

Frytk

a

En

terprise

Klo

cek

n

nw

p

pw

n

nw

p

pw

n

nw

p

pw

n

nw

p

pw

1.

6.44

2.52

28.83

37.04

27.62

32.73

7.09

8.04

7.09

7.32

5.86

6.01

5.86

5.94

4.89

5.28

4.89

4.77

2.

5.64

2.20

26.19

30.33

24.85

27.97

6.20

7.02

6.20

6.44

5.02

5.25

5.07

5.20

4.26

4.61

4.27

4.22

3.

4.92

2.36

21.87

27.25

20.22

23.95

5.41

6.10

5.41

5.65

4.41

4.59

4.43

4.53

3.71

4.04

3.72

3.69

4.

5.84

2.40

24.34

31.67

23.83

29.63

6.42

7.21

6.42

6.66

5.19

5.46

5.30

5.38

4.41

4.79

4.43

4.35

5.

4.24

1.92

18.20

24.42

18.36

23.04

4.72

5.29

4.66

4.89

3.75

3.94

3.80

3.91

3.19

3.49

3.19

3.19

Odmiana

algorytm

u:

n-normalna,

nw

-normalna

z

wizualizacj¡,

p-przyspieszona,

pw

-przyspieszona

z

wizualizacj¡.

Czas

ob

ecno±ci

-

czas,

przez

jaki

obiekt

jest

wido

czn

y

w

caªo±ci

na

scenie.

40

Opis implementacji

Rozdziaª 4

Podsumowanie

Post¦p, jaki dokonaª si¦ ostatnimi czasy w dziedzinie sprz¦tu komputerowego spowodowaª,

»e realne staªo si¦ szybkie przetwarzanie danych. Wynikiem tego jest rozwój dziedziny

komputerowej wizji, szczególnie jej cz¦±ci zajmuj¡cej si¦ przetwarzaniem sekwencji obra-

zów. Ju» teraz mo»liwe jest tworzenie algorytmów realizuj¡cych nawet caªkiem skompli-

kowane operacje na obrazach, które s¡ w stanie dziaªa¢ w czasie rzeczywistym na sprz¦cie

komputerowym dost¦pnym dla ka»dego.

Tym bardziej nic nie stoi na przeszkodzie, aby systemy wizyjne pojawiaªy si¦ coraz

cz¦±ciej w dziedzinach bliskich czªowiekowi. Chodzi tu nie tylko o dziedziny zawsze uwa-

»ane za niedost¦pne dla przeci¦tnych ludzi (do których wci¡» nale»y, niestety, robotyka),

lecz równie» bardziej pospolite, jak motoryzacja czy systemy alarmowe.

Przedstawione w niniejszej pracy przykªadowe algorytmy do lokalizacji pieszych na

podstawie sposobu, w jaki si¦ poruszaj¡ pokazuj¡, »e naukowcy pracuj¡ ju» nad tym,aby

wkrótce mo»liwe byªo wprowadzenie zaawansowanych technologii do powszechnego u»ytku.

Aby mogªo to szybko nast¡pi¢, nie nale»y tylko oczekiwa¢ bezczynnie na rozwój

sprz¦tu, aby w ko«cu mo»liwe byªo dziaªanie znanych rozwi¡za« w czasie rzeczywistym.

Trzeba d¡»y¢ równie» do przyspieszenia algorytmów. Algorytm nigdy nie jest za szybki.

Jedn¡ z mo»liwo±ci, je±li chodzi o algorytmy do lokalizowania na sekwencjach obrazów

obiektów poruszaj¡cych si¦ w znany sposób (w tym id¡cych ludzi) jest wykorzystanie

informacji o ruchu. Pozwala to nie tylko na przyspieszenie algorytmu, lecz równie» unie-

zale»nia od wygl¡du obiektu. Przestaje by¢ istotne, czy pojawi si¦ on w innym kolorze,

ni» przypuszczali±my (czªowiek w innym kolorze swetra), b¦dzie miaª inny ksztaªt (pieszy

z plecakiem) lub rozmiar (przejdzie bli»ej lub dalej od kamery). Skupiamy si¦ tylko na

cechach najlepiej charakteryzuj¡cych poszukiwane obiekty.

W pracy zaproponowano implementacj¦ jednego ze znalezionych w literaturze algoryt-

mów. Pozwala ona na lokalizacj¦ id¡cych ludzi na sekwencjach obrazów z wykorzystaniem

charakterystycznego, okresowego sposobu poruszania si¦ czªowieka. Zrealizowana zostaªa

z u»yciem darmowych narz¦dzi programistycznych oraz zamieszczona na zaª¡czonej do

pracy pªycie CD. Bardziej szczegóªowe informacje znajduj¡ si¦ w dodatku.

Jak pokazaªy eksperymenty, program jest w stanie skutecznie lokalizowa¢ pieszych w

czasie rzeczywistym na sprz¦cie dost¦pnym dla ka»dego. Istniej¡ dodatkowo spore mo»-

liwo±ci dalszego przyspieszania algorytmu. Mo»na chocia»by zmniejszy¢ jeszcze bardziej

liczb¦ badanych parametrów i zostawi¢ nawet tylko jeden.

Badania przeprowadzone w warunkach rzeczywistych, z wykorzystaniem sekwencji po-

bieranych przy pomocy kamery cyfrowej pokazuj¡, »e w metodzie kryje si¦ spory poten-

cjaª badawczy. Do gªównych zada« i problemów do rozwi¡zania zaliczyªbym poprawienie

metody wydzielania obiektu ruchomego na obrazie (np. poprzez u»ycie stereowizji) oraz

42

Podsumowanie

eliminacj¦ zakªóce« wynikaj¡cych zarówno z niedoskonaªo±ci kamery, jak i powodowanych

przez czynniki zewn¦trzne. Nie bez znaczenia byªoby równie» poszerzenie mo»liwo±ci al-

gorytmu, na przykªad o mo»liwo±¢ pracy z wieloma ruchomymi obiektami na scenie.

Dodatek A

Zawarto±¢ pªyty doª¡czonej do pracy

Do niniejszej pracy zaª¡czona zostaªa pªyta CD. Znajduj¡ si¦ na niej nast¦puj¡ce katalogi:

•

Tekst- tekst pracy dyplomowej

•

ShapeOfMotion- implementacja opisanego w pracy algorytmu

 src- ¹ródªa programu
 contrib- biblioteki niezb¦dne do kompilacji programu
 SampleVideos- przykªadowe pliki wej±ciowe dla programu

W celu kompilacji programu nale»y upewni¢ si¦, »e na komputerze zainstalowane s¡

niezb¦dne biblioteki, czyli OpenCV w wersji 1.0.0 oraz GSL w wersji 1.8. Nast¦pnie

nale»y wej±¢ do katalogu ShapeOfMotion/src/ oraz wywoªa¢ 'make' z linii komend. Je±li

wszystko pójdzie dobrze, pojawi si¦ plik wykonywalny o nazwie som.

Aby uruchomi¢ program, nale»y wywoªa¢ go z parametrem b¦d¡cym nazw¡ pliku

wej±ciowego, np: './som ../SampleVideos/zrodlo.avi'. Po zako«czeniu pracy program

wypisze na standardowym wyj±ciu wyznaczone cz¦stotliwo±ci parametrów, a tak»e zapisze

do plików w katalogu, w którym znajduje si¦ plik wej±ciowy zmiany parametrów oraz

zmiany warto±ci cz¦stotliwo±ci ich przebiegów. Dla powy»szego przykªadu b¦d¡ to kolejno:

zrodlo_val.dat oraz zrodlo_freq.dat w katalogu ../SampleVideos/.

44

Zawarto±¢ pªyty doª¡czonej do pracy

Bibliograa

[1] Metoda najmniejszych kwadratów [online]. Wikipedia: Wolna Encyklopedia, 2007.

Dost¦pny w Internecie: http://pl.wikipedia.org/wiki/Fullpagename?oldid=6852741.

[2] C. Wohler B. Heisele. Motion-based recognition of pedestrians. Technical report,

Daimler-Benz AG, Research and Technology, P.O. Box 2360, 89013 Ulm, Germany,

1998.

[3] M. Bennewitz, W. Burgard, and G. Cielniak. Utilizing learned motion patterns to

robustly track persons. In Proc. of the Joint IEEE International Workshop on Visual

Surveillance and Performance Evaluation of Tracking and Surveillance (VS-PETS),

2003.

[4] G. Cielniak, M. Bennewitz, and W. Burgard. Robust localization of persons based

on learned motion patterns. In Proc. of the European Conference on Mobile Robots

(ECMR), 2003.

[5] G. Cielniak, M. Bennewitz, and W. Burgard. Where is...? learning and utilizing

motion patterns of persons with mobile robots. In Proc. of the International Joint

Conference on Articial Intelligence (IJCAI), 2003.

[6] Free

Software

Foundation.

GNU

General

Public

License.

http://www.gnu.org/copyleft/gpl.html, 1991.

[7] Y. Guo, G. Xu, and S. Tsuji. Understanding human motion patterns. Technical

report, National University of Singapore and Osaka University, 1994.

[8] Chinese Academy of Sciences Institute of Automation. CASIA Gait Database.

http://www.sinobiometrics.com.

[9] G. Johansson. Visual perception of biological motion and a model for its analysis.

Perception & Psychopsychics, 1973.

[10] J. J. Little and J. E. Boyd. Recognizing people by their gait: The shape of motion.

Videre: Journal of Computer Vision Research, 1(2), 1998.

[11] B. D. Lucas and T. Kanade. An iterative image registration technique with an appli-

cation to stereo vision. In Proc. of 7th International Joint Conference on Articial

Intelligence (IJCAI), 1981.

[12] M. Jones P. Viola and D. Snow. Detecting pedestrians using patterns of motion

and apperance. Technical report, Mitsubishi Electric Research Laboratories, 201

Broadway, Cambridge, Massachusetts, 2003.

46

BIBLIOGRAFIA

[13] R. Polana and R. Nelson. Low level recognition of human motion. IEEE Workshop

on Motion of Non-Rigid and Articulated Objects, 1994.

[14] The GSL Team.

GNU Scientic Library  Reference Manual.

http://www.gnu.org/software/gsl/manual/html_node/index.html, 2007.

[15] M. Wnuk. Wykªad 12. In Notatki do wykªadu z przedmiotu 'Systemy Wizyjne'.

Instytut Informatyki, Automatyki i Robotyki Politechniki Wrocªawskiej.

Spis tre±ci

1 Wst¦p

1

1.1 Ogólna koncepcja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Cel pracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

2 Przegl¡d istniej¡cych algorytmów

3

2.1 Podziaª algorytmów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.2 Klasteryzacja i sieci neuronowe . . . . . . . . . . . . . . . . . . . . . . . .

5

2.3 Ukryte modele Markowa . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.4 Wykorzystanie modelu . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.5 Momenty geometryczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.5.1 Wst¦p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.5.2 Ogólny opis metody . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.5.3 Szczegóªowy opis metody . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Opis implementacji

17

3.1 Wykorzystane narz¦dzia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1.1 Sprz¦t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1.2 System operacyjny . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1.3 Kompilator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1.4 Przetwarzanie obrazów . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1.5 Algorytmy numeryczne . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1.6 Dane wej±ciowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 Wyznaczenie parametrów chodu czªowieka . . . . . . . . . . . . . . . . . . 19

3.2.1 Wydzielenie sylwetki . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2.2 Pole ruchu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2.3 Parametry sylwetki . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2.4 Wektor cech . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.2.5 Zmiany parametrów poªo»enia poziomego . . . . . . . . . . . . . . . 27

3.2.6 Obliczanie cz¦stotliwo±ci . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3 Badania algorytmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3.1 Badania skuteczno±ci dziaªania . . . . . . . . . . . . . . . . . . . . 30

3.3.2 Wpªyw k¡ta osi kamery wzgl¦dem pªaszczyzny ruchu . . . . . . . . 34

3.3.3 Badanie pr¦dko±ci dziaªania algorytmu . . . . . . . . . . . . . . . . 35

4 Podsumowanie

41

A Zawarto±¢ pªyty doª¡czonej do pracy

43

ii

SPIS TRE‘CI

Spis rysunków

2.1 Przykªad obrazu po klasteryzacji [2] . . . . . . . . . . . . . . . . . . . . . .

6

2.2 Przykªad dziaªania algorytmu z wykorzystaniem ukrytych modeli Markowa [3] 7

2.3 Przykªad dwuwymiarowego modelu ciaªa czªowieka [7] . . . . . . . . . . . .

8

2.4 Schemat dziaªania algorytmu Shape of Motion [10] . . . . . . . . . . . . . . 10

2.5 a) Przykªadowy rozkªad warto±ci (|(u, v)|) dla sze±ciu klatek lmu; b) Przykªadowy

rozkªad warto±ci T (u, v) dla sze±ciu klatek lmu. [10] . . . . . . . . . . . . 11

2.6 Wizualizacja momentów sylwetek za pomoc¡ elips [10] . . . . . . . . . . . 12

2.7 Poªo»enia punktów reprezentuj¡cych warto±ci wektora (y

d

,a

d

) dla 42 próbek

charakteryzuj¡cych chód 6 osób [10] . . . . . . . . . . . . . . . . . . . . . . 15

3.1 Schemat dziaªania pierwszej wersji zaimplementowanego algorytmu . . . . 20

3.2 Trzy przykªadowe klatki z lmu z id¡cym pieszym (a-c), wydzielone z nich

obrazy binarne (d-f), pola ruchu (g-i), oraz ich iloczyny (j-l). Dla celów

niniejszej wizualizacji histogramy obrazów d-l zostaªy znormalizowane. W

innym razie byªyby one maªo czytelne. . . . . . . . . . . . . . . . . . . . . 21

3.3 Przebieg zmian parametru x

uwc

uzyskany bezpo±rednio z przykªadowej se-

kwencji (a) oraz przebieg uzyskany po odj¦ciu od niego skªadowej liniowej

(b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.4 Przebiegi zmian parametrów sylwetek wraz z wyznaczon¡ za pomoc¡ szyb-

kiej transformacji Fouriera cz¦stotliwo±ci¡ dla przykªadowej sekwencji z

id¡cym czªowiekiem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.5 Histogramy wyst¡pie« danych cz¦stotliwo±ci dla wszystkich parametrów

oraz ich podstawowe wªasno±ci statystyczne: m- warto±¢ ±rednia, s- odchy-

lenie standardowe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.6 Wizualizacja sceny u»ytej do przeprowadzania eksperymentu. . . . . . . . . 34

3.7 Histogramy wyst¡pie« danych cz¦stotliwo±ci dla sekwencji kr¦conych pod

k¡tem 90(a-c), 72(d-f) oraz 108(g-i) stopni, dla trzech wybranych parame-

trów oraz ich podstawowe wªasno±ci statystyczne: m- warto±¢ ±rednia, s-

odchylenie standardowe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.8 Histogramy wyst¡pie« danych cz¦stotliwo±ci dla sekwencji kr¦conych pod

k¡tem 90(a-c), 54(d-f) oraz 126(g-i) stopni, dla trzech wybranych parame-

trów oraz ich podstawowe wªasno±ci statystyczne: m- warto±¢ ±rednia, s-

odchylenie standardowe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

iv

SPIS RYSUNKÓW

Spis tablic

2.1 Zestawienie niektórych algorytmów do wykrywania ludzi na podstawie spo-

sobu ich poruszania si¦ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.2 Zestaw parametrów sylwetki, wg autorów algorytmu Shape Of Motion . . . 13

3.1 Komputery wykorzystane do testowania algorytmu . . . . . . . . . . . . . 18

3.2 Zestawienie wªasno±ci statystycznych wybranych parametrów dla sekwencji

nakr¦conych z ró»nych k¡tów, m- warto±¢ ±rednia, s- odchylenie standardowe. 36

3.3 Zestawienie czasów dziaªania ró»nych wersji algorytmu na ró»nych kon-

guracjach sprz¦towych komputera. Wszystkie czasy w sekundach. . . . . . 39