Elektrotehniški vestnik 80(5): 258-265, 2013 Izvirni znanstveni članek
Hierarhična kompozicionalna arhitektura za detekcijo in razpoznavanje aktivnosti
Janez Perš1, Matej Kristan1'2, Rok Mandeljc1, Stanislav Kovačič1, Aleš Leonardis2'3
1	Univerza v Ljubljani, Fakulteta za elektrotehniko, Tržaška 25, 1000 Ljubljana, Slovenija
2	Univerza v Ljubljani, Fakulteta za računalništvo in informatiko, Tržaška 25, 1000 Ljubljana, Slovenija
3	University of Birmingham, School of Computer Science and Centre for Computational Neuroscience and Cognitive Robotics, Birmingham B15 2TT, United Kingdom
E-pošta: janez.pers@fe.uni-lj.si
Povzetek. Vecina algoritmov za detekcijo in razpoznavanje aktivnosti temelji na ucenju kakovostnih casovno-prostorskih opisnikov. Ti opisniki hitro postanejo prekompleksni, ob tem pa poleg gibanja zajamejo tudi obliko in teksturo, in to na nekontroliran in nepredvidljiv nacin. Čeprav taksni pristopi v praksi omogočajo visoko uspešnost razpoznavanja, je inferenca počasna, razlage, kako algoritem pride do določenega rezultata, pa vecinoma ni mogoce dobiti. V tem clanku predstavljamo alternativni pristop, ki temelji na preprostih nizkonivojskih znacilnicah, ki zajemajo le gibanje, zaznano v posnetku. Te znacilnice s pomocjo hierarhicne kompozicionalne sheme v postopku ucenja na enem samem kratkem posnetku sestavljamo v vzorce gibanja, t. i. kompozicije. V postopku inference te vzorce poišcemo v analiziranih posnetkih, in jih vzorcimo v "vreco kompozicij". Za razvršcanje uporabljamo razvršcevalnik SVM z jedrom x2. Postopek je racunsko ucšinkovit in primeren za izvedbo na masovno-vzporednih arhitekturah. zaradi kompozicionalne narave je vzorce gibanja mogoce ucinkovito zapisati, ucimo pa jih lahko postopoma, sloj za slojem. Postopek omogoca hitro inferenco, koncni vektorji znacilnic pa so razmeroma nizkodimenzionalni, s cimer dosezemo tudi hitro ucenje razvršcevalnika. Predstavljena metoda dosega na standardni bazi UČF Sports najboljše rezultate med metodami, ki temeljijo zgolj na gibanju.
Ključne besede: racunalniški vid, razpoznavanje aktivnosti, kompozicionalni modeli
Hierarchical Compositional Architecture for Activity Detection and Recognition
Many activity detection and recognition approaches focus on designing or learning high-quality, low-level spatiotemporal descriptors. These low-level descriptors may become overly complex, encoding motion, shape and texture in uncontrolled and unpredictable ways. While such complexity helps increasing recognition rates, it slows down the process of inference and obscures the reasoning behind the learned descriptors. We present an alternative approach, which is based on primitive features that encode pure motion. These are coupled with a hierarchical scheme to learn motion patterns (compositions) from a single short video. During the inference process, these learned patterns are extracted from the analyzed videos and used with x2 SVM classifier in a "bag of compositions" approach. The process is computationally efficient and the method is well-suited for implementation on massively parallel architectures. Due to their compositional nature, motion patterns can be trained incrementally (layer by layer) and stored efficiently. Inference is fast and the final feature vectors are of relatively low dimension, thus enabling fast SVM training. On the standard UCF Sports Action Dataset, the presented method outperforms state-of-the art approaches based on pure-motion.
1 Uvod
V tem clanku je predstavljena hierarhična kompozicionalna shema za detekcijo in razpoznavanje aktivnosti. Kar zadeva razpoznavanje aktivnosti, je gibanje najpomembnejši kanal vizualne informacije, zato predstavljena shema temelji izkljucno na gibanju. Predstavljeno delo naslavlja tri pomembne izzive pri analizi gibanja. Prvi izziv je kolicšina informacije, saj imamo pri analizi gibanja obicajno opravka z zaporedji slik. To pomeni, da je za obdelavo v realnem cšasu treba obdelati do nekaj deset slik na sekundo. Zato izziv ni le, kako zaznati in razpoznati aktivnosti, ampak predvsem, kako to izvesti cim hitreje. Naslednji izziv je, kako razvezati gibanje od drugih vizualnih kanalov (oblike, prostorskega vida in barve) in kljub temu obdrzati uporabno informacijo. Takšna zasnova ima dve prednosti: omogoca ucšinkovitejsši zapis, kar zmanjsša nevarnost kombina-toricšne eksplozije zaradi prekompleksnih znacšilnic, ter olajša razlago, kako je sistem prišel do dolocenega zakljucka. To je pomembna prednost v sistemih, ki naj bi izkazovali cšloveku podobno inteligenco (npr. inteligentni roboti in robotski pomocšniki). Po drugi strani pa niso vsi kanali vizualne informacije enako pomembni za vse naloge racšunalnisškega vida (tipicšen primer je analiza aktivnosti, kjer je nacšeloma gibanje najpomembnejsši vir
informacij), vendar za dobro razpoznavanje potrebujemo podatke iz vec kanalov. Če informacijo zdruZujemo Ze v zgodnjih stopnjah obdelave, je to lahko manj učinkovito, kot če to počnemo pozneje [14].
Predstavljena metoda naslavlja te izzive s paradigmo kompozicionalne hierarhičnosti, biološko navdihnjenega koncepta načrtovanja algoritmov [9], ki je bil ze uspešno uporabljen pri zasnovi najboljših algoritmov za kategorizacijo objektov [15], [3], [20], [8], [2]. V primerjavi s konkurencšnimi pristopi ponujajo kompozi-cionalne hierarhije učinkovitejšo izrabo obstoječih virov. To dosezejo s pomočjo večkratne uporabe elementov slovarja in tudi ze izvedenih izračunov, s tem pa omogočajo tudi učinkovit prenos znanja. Predstavljen pristop sicer v številnih vidikih sledi konceptom, ki so jih predstavili Fidler in drugi [3], [2], vendar pa deluje na gibanju, ne na obliki, in naslavlja problem detekcije in razpoznavanja aktivnosti namesto kategorizacije objektov. Opazovanje le gibanja sicer ne more popolnoma resšiti problema razpoznavanja aktivnosti, vendar lahko, če se osredinimo izključno na gibanje v zgodnji fazi obdelave, zdruzevanje informacij izvedemo pozneje, na učinkovitejši način [14]. S takšnim pristopom tudi ne podvajamo obdelave informacije, ki jo dobro zajamejo ze razvite metode, ki naslavljajo druge vizualne kanale, recimo razpoznavanje oblike [3], [2]. Poleg tega, daje to učinkovitejše[14], pa je takšen koncept, torej pozno zdruzevanje, opaziti tudi v bioloških vidnih sistemih [9].
Predlagano shemo prikazujeta sliki 1 in 2. Razumeti je treba, da ob omejitvi zgolj na gibanje v posnetkih ne moremo pričakovati izboljšanja glede na najboljše algoritme, ki vključujejo vse vidne kanale, vključno z obliko in teksturo. Vendar pa je, kot je bilo ze omenjeno, ločitev kanalov vidne informacije pomembna pri nadaljnjem razvoju skalabilnih metod razpoznavanja. Čeprav predstavljena metoda uporablja samo gibanje, vseeno dosega presenetljivo dobre rezultate, hkrati pa dosega boljše rezultate kot nekatere metode, ki se zanašajo samo na gibanje brez drugih modalitet.
Preostanek članka je strukturiran, kot sledi. V poglavju 2 so predstavljeni najpomembnejsši sorodni pristopi, v poglavju 3 pa podrobnejši opis predlaganega pristopa. V poglavju 4 so navedene izvedbene podrobnosti metode, v poglavju 5 eksperimenti in rezultati, poglavje 6 pa zaključuje članek.
2 Sorodne raziskave
Raziskovalci so se problema detekcije in razpoznavanja aktivnosti lotevali na različne načine. Večina pristopov temelji na določanju tako imenovanih časovno-prostorskih točk zanimanja (angl. space-time interest points, STIP). Sekvenca slik je v teh primerih obdelana kot tridimenzionalni volumen I(x,y,t), v katerem metode iščejo točke STIP. V okolici teh izračunajo časovnoprostorske opisnike, ki jih potem s procesom rojenja zdruzijo v manjše število vizualnih besed.
Znacilnice so v tem primeru histogrami sopojavljanja teh vizualnih besed, za razvrščanje posnetkov pa je ponavadi uporabljena metoda podpornih vektorjev (angl. support vector machine, SVM).
V	[12] so avtorji predlagali tovrstno metodo, ki zajema dve vrsti opisnikov: prva zajame dinamiko scene (torej gibanje), druga pa ozadje (torej staticne elemente prizora). V [10] je koncept razširjen z avtomatskim izracunom optimalnih opisnikov za dani ucni niz posnetkov. Opisnike dobijo s pomocjo globokih nevronskih mrez (angl. deep belief networks). Tako dobijo opisnike, ki opišejo tako casovne kot prostorske spremembe v 3D casovnoprostorskem volumnu.
Se en primer uporabe mešanih modalnosti za analizo aktivnosti [6], kjer je predstavljena hierarhicna mreza, enot, obcutljivih na gibanje. Metoda izvede zaporedje konvolucij in poišce maksimalen odziv na rezultatih konvolucije. Na vrhu hierarhije je uporabljena metoda SVM za izbiro najbolj diskriminativnih znacilnic.
V	[7] je predstavljena metoda, ki zakodira lokalno gibanje v shemi, podobni lokalnim binarnim vzorcem. Tako dobi krpice gibanja (angl. motion patches), ki jih uporabi v shemi vrece besed. Tudi [19] uporablja vreco besed, s tem da identificira majhne atomicne dogodke iz premikajocih se slikovnih elementov in jih zdruzi v atomarne aktivnosti. Konceptualno podobna rešitev je [17]. Uporablja gost opticni tok ter tako zgradi zapis zaporedij slik s pomocjo gostih trajektorij, ki ga pretvori v opisnike s pomocjo posebnega opisnika (Motion Boundary Histograms, MBH). Metoda dosega odlicne rezultate na standardnih zbirkah podatkov, še boljše rezultate pa dosega, ce je kombinirana z informacijo o obliki. Izvedba, ki uporablja izkljucno MBH na gostih trajektorijah, je ena redkih metod, ki temelji izkljucno na uporabi informacije o gibanju.
Metode poskušajo izboljšati delovanje na razlicne nacine. Tako recimo [5] razširi prostorski model vrece besed z diskriminativno razsširitvijo, ki omogocša socšasno segmentacijo in lokalizacijo dogodkov. V [1] je predlagano še bolj intenzivno mešanje modalitet za lokalizacijo aktivnosti - sliko zakodira kot polje casovnoprostorskih opisnikov in poisšcše cšasovnoprostorski podgraf, ki maksimira odziv naucenih razvršcevalnikov.
V	nasprotju z vecino pristopov [16] ugotavlja, da aktivnost ni nujno povezana s kontekstom in je mogocše dobiti boljše rezultate, ce jo obravnavamo loceno. Morda najbolj soroden pristop k predlaganemu v tem cšlanku je [4]. Metoda zazna Harrisove znacilne tocke loceno v prostorskih in cšasovnoprostorskih ravninah na razlicšnih skalah. S pomocjo enostavnega prostorskega kodiranja hierarhicno gradi predstavitve, tako da se najpogostejši vzorci prenašajo na naslednji sloj. Metoda doseze odlicne rezultate na standardnih bazah posnetkov, vendar pa gre, ceprav avtorji namigujejo drugace, tudi tu za primer mešanja modalitet - predstavitev, ki jo zgradi takšna metoda, zajame tako gibanje kot obliko in ni nikakrsšnega zadrzška, da ob ustreznih ucšnih podatkih ne
bi zgradila hierarhije, ki bi bila popolnoma oprta samo na obliko in teksturo.
3 Struktura kompozicionalnega
HIERARHIČNEGA MODELA
Predlagani model za analizo gibanja je sestavljen iz treh stopenj obdelave podatkov, kot to prikazuje slika 1. Namen najnizje stopnje, sestavljene iz slojev L0 in L1, je določanje najpreprostejših značilnič gibanja kvanti-ziranih vektorjev optičnega toka. Srednja stopnja predstavlja hierarhicšno kompozicionalno strukturo in je sestavljena iz več slojev, od L2 do LN. Večslojna struktura zmanjšuje kompleksnost učenja zaradi omejenega zaznavnega polja, v katerem opazujemo sosede vsakega zaznanega elementa, saj izvajamo učenje le na enem sloju hkrati. Takšna shema odpravlja potrebo po sočasni očeni velikega števila parametrov v fazi učenja - najprej izvedemo učenje na najnizjem sloju, potem pa nadaljujemo s slojem nad njim. Najvišja stopnja modela vsebuje diskriminativno komponento - razvrščevalnik SVM. Vsak sloj L® ima svoj slovar, A®. A1 je določen vnaprej, medtem ko slovarje višjih slojev pridobimo v postopku učenja.
3.1	Izračun gibanja, sloja L0 in L1
Prva stopnja obdelave poskrbi za izračšun preprostih elementov gibanja iz posnetkov. L0 zgradi Gaussovo piramido vsake slike ter izračuna razliko Gaussov, podobno kot [11]. Tako nastanejo slike tistih področij, kjer je gibanje mogoče dobro zaznati (robovi, oglišča), in to na večš skalah. Po postopku dusšenja nemaksimalnih vrednosti (angl. non-maxima suppression, NMS) je vsako od teh področij predstavljeno z eno samo točko. Velikost okna, v katerem izvajamo dušenje, in minimalna vrednost prezšivelega maksimuma sta parametra sloja L0.
Sloj L1 primerja detektirane točke na dveh zaporednih slikah in očenjuje lokalno gibanje s pomočjo iskanja najblizšjega soseda v lokalni okoliči. Koraki na slojih L0 in L1 so ponovljeni na vseh skalah piramide, s tem pa lahko metoda zazna gibanje v velikem razponu magnitud. Kot končšni korak obdelave na L1 so vektorji gibanja kvantizirani glede na njihovo smer in magnitudo - števili mogočih amplitud in smeri predstavljata parametra sloja L1. Kvantizačija je izvedena tako, da so vektorji z dolzino nič izločeni iz nadaljnje obdelave. Stevilo mogočših smeri in magnitud določša velikost slovarja na sloju L1 - v našem primeru osmih mogočih smeri in treh mogočih magnitud je velikost slovarja 8 x 3 = 24. Od te stopnje naprej se vsa obdelava izvaja na kvantiziranih vektorjih gibanja. Rezultati slojev L0 in L1 so prikazani na sliki 2, skupaj s 24 osnovnimi elementi fiksnega slovarja sloja L1 .
3.2	Dušenje nezaželene vizualne informacije
Posebnost prve stopnje predlagane strukture je dušenje kakršnekoli druge vizualne informačije razen
gibanja. Z dušenjem nemaksimalnih vrednosti na sliki razlike Gaussov učinkovito odstranimo vso informacijo v okolici ohranjene točke, tako da algoritem ne zajame nikakršnih informacij o obliki ali teksturi. Tako v nasprotju z nekaterimi drugimi pristopi, na primer [4], [10], preprecšimo, da bi kompozicionalna struktura na drugi stopnji obdelave gradila kakrsšnekoli modele oblike.
3.2.1 Grajenje hierarhičnih kompozicij - sloji L2-Ln: Kompozicionalna hierarhična struktura je sestavljena iz N identicno strukturiranih slojev, pri cemer je N parameter strukture. Vhodni podatki v strukturo so kvantizirani in labelirani vektorji gibanja. Vsak vektor V je dolocen s svojimi tremi casovnoprostorskimi koordinatami in svojo oznako l, V = V(x,y,t,l). Izhod vsakega sloja L® v kompozicionalni strukturi predstavljajo kompozicije parov elementov nižjega sloja L(®-1). Vsaka od kompozicij predstavlja nov element P, P = P(x, y, t, l), in predstavlja naceloma enega od vhodnih elementov višjega sloja. Vhodne elemente v najnizji kompozicionalni sloj L2 predstavljajo kar kvantizirani vektorji, zato zanje velja P1 = V(x,y,t,l1), kjer oznaka elementa l1 zavzema eno od mogocših vrednosti iz slovarja A1, dolocenih s kvantizacijo na L1, l1 g A1. Slovarje višjih slojev, A®, i > 1 pridobimo s postopkom ucenja.
Kompozicije na vseh slojih L®, i > 1 so definirane kot pari tesno sopojavljenih elementov iz nizjega sloja, torej velja za element j iz sloja L® naslednje:
pi = p i-1 y p
i-1
(1)
pri cemer sta m in n indeksa dveh elementov iz nizjega sloja, ki tvorita element P®. Casovnoprostorske koordinate kompozicije so definirane kot centroidi lokacij obeh elementov, ki sestavljata kompozicijo:
1 I	1
xm + xn
2

yi-1 + yi-1
y m 1 ¿m 2
ti
ti-1 + ti-1 2 '
(2)
medtem ko je oznaka l® dolocena skozi dvodimenzionalno indeksno tabelo ^®-1®:

/ i— 1,i ( Ti— 1 Ji— 1 \
-1 fi-1-1
(3)
ki indeksira pare oznak iz sloja L®-1 v oznake na sloju L®. Nicle v indeksni tabeli ^®-1'® oznacujejo tiste kompozicije, ki jih v indeksiranju iz sloja v sloj zavrzemo.
Tesna sopojavitev dveh elementov je dolocena s pomocjo dveh pragov,	, na prostorski evklidski
razdalji med obema elementoma Pm-1 in P^-1, in R na njuni razdalji vzdolzš cšasovne osi:
rft
ex-1 - xn-1)2 + (y-1 - y-1)2 < RifXy. (4)
i-1 i-1 i lm Ln < Rrft.
x
j
Slika 1: Tri stopnje obdelave v predlaganem kompozicionalnem hierarhičnem modelu. Prva stopnja je sestavljena iz L0 in L1, druga iz (N-1) slojev L2 - Ln, v tretji stopnji pa sta vzorčenje (vreča kompozicij) in razvrščevalnik SVM.
Oba pragova	in Rrft odražata velikost cilin-
drično oblikovanega lokalnega zaznavnega polja in tako predstavljata parametra vsakega od kompozičionalnih slojev L®. V kompozičionalni shemi naj bi velikost zaznavnega polja povečevali iz sloja na sloj, s čimer lahko shema gradi vedno kompleksnejše predstavitve vhodnih podatkov - v našem primeru gibanja. Upoštevati je treba, da predlagana shema ne kodira časovnoprostorskih odnosov med zaznanima elementoma (prej, pozneje, spodaj, zgoraj), zato ne modelira ničesar drugega kot enostavno blizino dveh elementov. Zato ima omejeno moč predstavljanja kompleksnih struktur, kot bi načšeloma bila oblika na podlagi gibanja (angl. shape from motion).
3.2.2 Ucenje strukture v slojih L2-LN: Za učenje sloja L® potrebujemo izhod nizjega sloja L®-1, ki je lahko kompozičionalen (L®, i > 1) ali pa ne (L1). Učenje modela na sloju L® je izvedeno s pomočjo optimizačije indeksne tabele ^®-1® glede na naslednja dva kriterija:
1)	Pokritost: Čim več osnovnih elementov iz sloja L1 (z dna kompozičionalne strukture) naj prezšivi v prehodu iz sloja L®-1 v sloj L®. Ta kriterij zagotavlja, da potenčialno uporabna informačija, ki vstopa v kompozičionalno strukturo, ni po nepotrebnem zavrzšena.
2)	Slovar sloja, ki ga učimo, L®, A® naj je čim manjši.
Omenjena kriterija sta v nasprotju in tezšita k slovarju, ki je kompromis med najboljšo rekonstručijo vhodne
informačije in najkrajšim naborom simbolov. Učenje je izvedeno kot nelinearna optimizačija naslednje kriterij-ske funkčije:
f(x) = -C1 + a|A®|,	(6)
kjer je C1 pokritost (razmerje števila osnovnih elementov iz sloja L1, katerih kompozičije na sloju L® bi prezšivele ob trenutnem slovarju, in sštevila vseh elementov, ki iz L1 vstopajo v kompozičionalno strukturo), | A® | is je število elementov slovarja, a pa je utez, s katero nadzorujemo intenzivnost regularizačije, torej točško kompromisa med nasprotujočima si kriterijema. Domena x so vse mogoče kombinačije ničelnih in neničelnih elementov v indeksni tabeli |A®|. S pomočjo optimizačije v bistvu določimo takšen slovar A®, da velja:
A® = argmin f (x).	(7)
x
Očitno je, da bi v najslabšem primeru popolnoma naključšnih vhodnih podatkov sštevilo kompzičionalnih elementov v slovarju |A®| raslo s kvadratom i, vendar pa se izkaze, da pri realističnih podatkih raste počasneje. Da pospešimo postopek optimizačije in bistveno zmanjšamo prostor iskanja optimalnega slovarja, lahko ze pred postopkom optimizačije odstranimo delez mogočih kompo-zičij, ki vstopajo v optimizačijski pročes. To izvedemo le za učenje sloja L3 (in višjih), kjer tako odstranimo 1% mogočih kompozičij, ki se v podatkih pojavljajo najredkeje.
Slika 2: Znacilnice gibanja na primeru posnetka iz kategorije "Diving", zbirke podatkov UCF Sports Action Dataset [13]. (a) Izhod sloja L0, kvadratki označujejo lokalne maksimume razlike Gaussov. Vecji kvadratek pomeni bolj grobo skalo. Crte označujejo vektorje gibanja. (b) Izhod sloja L1 in fiksen slovar tega sloja. Radiji krogov ustrezajo amplitudi zaznanega gibanja, puščice pa kazejo smer, oboje ze po postopku kvantizacije.
3.2.3 Inferenca na slojih L2-LN: Inferenca je izvedena kot zaporedje indeksiranj skozi indeksne tabele	Trenutno metoda ne upošteva drugih casovnoprostorskih odnosov med elementi, razen tega da dolocšen element lezši znotraj (cšasovnoprostorskega) zaznavnega polja nekega drugega elementa. Zato je indeksiranje s stalisšcša racšunske zahtevnosti izjemno hitra operacija, takoj ko potrdimo sopojavitev dveh elementov. Iskanje sopojavitev je nacšeloma racšunsko potratna operacija, vendar pa je zaradi pocšasne (manj kot kvadraticne) rasti velikosti slovarjev |A'| skozi sloje inferenca še ucinkovitejša, ce išcemo sopojavitve samo tistih elementov, ki bi prezšiveli indeksiranje skozi dano indeksno tabelo A'.
3.3 Zajem znacilnic in razvrščanje
Osnovni elementi, ki jih zaznamo pri obdelavi zaporedja slik skozi sloja L0 in L1, predstavljajo osnovne gradnike gibanja, ki pa zrastejo v vedno kompleksnejše gradnike skozi višje sloje. Pojavljanje elementov skozi hierarhicno strukturo je mogoce vzorciti na razlicne nacine. Predlagana metoda zgradi vreco kompozicij tako, da izracšuna histograme pojavljanja vseh elementov na vseh slojih in jih sestavi v en sam vektor znacšilnic. Ta postopek je na vrhu predlagane kompozicionalne piramide, kot jo prikazuje slika 1.
Pristop z vreco kompozicij naredi predlagano metodo povsem invariantno na cšasovni odmik aktivnosti
znotraj zaporedja slik. Da se ta ucinek zmanjša, so podatki najprej razdeljeni vzdolz casovne osi v M locenih, enako dolgih odsekov in zajeti v M histogramov, ki so na koncu sestavljeni v en sam daljši vektor znacilk. Za razvršcanje tako pridobljenih vektorjev znacilk je bila uporabljena javno dostopna izvedba razvršcevalnika [10], katere struktura je opisana v [18], temelji pa na metodi podpornih vektorjev z jedrom x2.
3.4 Velikost naučenega modela
V predstavljeni arhitekturi je znanje zgošceno v hierarhiji indeksnih tabel |A'|, ki omogocajo prevedbo oznak elementov na sloju li-1 v oznake na sloju l'. Tako za slovarje z do 256 elementi potrebujemo le polje osembitnih števil z maksimalno dimenzijo 256 x 256, da shranimo eno indeksno tabelo, pa še v tej tabeli ima velik del elementov vrednost nic. Ce je kot zadnja stopnja razpoznavanja uporabljen razvrsšcševalnik SVM, je treba shraniti še njegov model, podobno kot pri drugih pristopih z vreco besed, kot sta [10] in [18].
4 Izvedba predlagane metode
Predlagana shema izraza najpomembnejši prednosti kompozicionalnih hierahicnih arhitektur - hitro infe-renco in kompakten zapis znanja. Toda, ceprav so kom-pozicionalne arhitekture znane kot hitre in ucšinkovite pri obdelavi posameznih slik, se pri obdelavi posnetkov
soočamo s problemom, katerega računska zahtevnost je za nekaj razredov velikosti večja. Shema je bila načrtovana z namenom vzporedne izvedbe, predvsem na modernih splošnonamenskih grafičnih procesorjih (angl. (General Purpose) Graphič Pročessing Unit, GPU). Vsi najpomembnejši sestavni deli predlagane metode se tako zlahka preslikajo na masivno vzporedno računsko arhitekturo, kot je to prikazano v nadaljevanju.
4.1	Sloja L° in L1
(Čeprav je mogoče Gaussovo glajenje zlahka izvesti na grafičnem pročesorju, le-to ni glavno ozko grlo. Pomembnejše je, da sta tako dušenje nemaksimalnih vrednosti in izračun vektorjev gibanja (iskanje kore-spondenč) izvedena na masivno vzporedni arhitekturi, s pomočjo orodja Jačket za Matlab* in njegovega programskega bloka gfor. Za boljši izkoristek grafičnega pročesorja slike obdelujemo v paketih po 20 slik.
4.2	Sloji L2 in višji
(Čeprav hierarhična shema omogoča učinkovito iskanje s tem, da iščemo samo tiste kompozičije, ki bodo prezšivele indeksiranje, je mogočše vse razdalje med elementi hitro izračunati ze vnaprej z uporabo grafičnega pročesorja. Tako se pročes bistveno pospesši. Po drugi strani pa so tudi vektorji značilnič razmeroma nizkodi-menzionalni, kar omogoča hitro učenje razvrščevalnika SVM in hitro razpoznavanje.
4.3	Ucenje
Računsko najbolj kompleksen del algoritma je op-timizačija kriterijske funkčije (6) v postopku učenja posameznega sloja. Upoštevati je treba, da zahteva izračun pokritosti C v vsaki iteračiji na relativno velikih količinah vhodnih podatkov. Za optimizačijo je trenutno uporabljen genetski algoritem, ki se dobro skalira na večjedrnih pročesorjih osebnih računalnikov.
5 Eksperimenti in rezultati
Predstavljeno shemo smo očenjevali po treh kriterijih: uspešnost razpoznavanja in detekčije, učinkovitost računanja in velikost modela. Vsi eksperimenti so bili izvedeni na osebnem računalniku s štirijedrnim proče-sorjem Intel Xeon E5-1620 s taktom 3.60 GHz. Kot grafični pročesor je bila uporabljena grafična kartiča Nvidia Quadro 2000 z 1 GB videopomnilnika. Uporabili smo Matlab 2011a na Linuxu (distribučija Fedora 18) in Jačket 2.2 za obdelavo na grafičnem pročesorju. Za nelinearno optimizačijo smo uporabili genetski algoritem iz Matlabove orodjarne. V eksperimentih smo parametre algoritma nastavili na naslednje vrednosti: velikost okna za dušenje nemaksimalnih vrednosti je bila 7 slikovnih elementov, velikost zaznavnega polja je bila nastavljena na R-lfxy = 3.5 in Rfxy = 7 slikovnih elementov, Rr ft pa je bil nastavljen na 0 za vse sloje; s tem je
* http://wiki.aččelereyes.čom/wiki/index.php?title=Main_Page
bila hierarhija prisiljena v ucenje kompozicij samo v prostorski (XY) ravnini. Parameter a je bil nastavljen na 0.6. Parametri so bili določeni eksperimentalno — pazili smo, da sta sloja L0 in L1 v sliki detektirala dovolj osnovnih elementov gibanja, da je bila gradnja kompozicij sploh mogoča, in da je bilo učenje izvedeno v razumnem času ter z razumno porabo pomnilnika.
Za učenje kompozicionalne strukture smo uporabili samo en video z dolzino 480 slik. Video ni nikakor povezan z nobeno od testnih baz in zajema 24 odsekov otroške risanke s po 20 slikami. Slika 3 prikazuje tri tipične slike iz učnega posnetka.
Testiranje je bilo izvedeno na dveh standardnih in široko uporabljanih zbirkah posnetkov: UCF Sports Action Dataset [13] Holywood2 Dataset [12], [18]. Prva vsebuje 10 kategorij športnih aktivnosti, medtem ko druga vsebuje 12 kategorij vsakodnevnih aktivnosti, pridobljenih iz zbirke znanih holywoodskih filmov. Ker je učni video imel 384x288 slikovnih elementov, smo vse testne posnetke prevzorčili na vertikalno ločljivost 288 slikovnih elementov in ohranili razmerje med visšino ter širino slike. Tako smo ločljivost vseh posnetkov iz prve zbirke in večine posnetkov iz druge zbirke zmanjšali, vendar pa je zaradi velikih razlik v ločšljivosti posnetkov iz baze Holywood2 prišlo do tega, da se je ločljivost nekaterih posnetkov s tem povečšala.
Uspešnost razpoznavanja smo ovrednotili po metodologijah, ki sta predpisani za vsako od zbirk. V skladu s tem za UCF Sports Action Dataset navajamo povprečno točšnost, za Holywood2 pa povprečšno natančšnost.
5.1 Uspešnost razpoznavanja
Uspesšnost razpoznavanja navajamo glede na sštevilo uporabljenih kompozičionalnih slojev. Zaradi nepristranske primerjave navajamo tudi rezultate, ki smo jih dobili z neposrednim zajemom sloja L1 brez kompozicionalne arhitekture. Rezultati za UCF Sports Action Dataset so prikazani v tabeli 1. Učinkovitost naše sheme se ni povečala z dodajanjem tretjega sloja, zato smo se omejili samo na strukturo s slojema L1 in L2.
Naša metoda (zajeti sloji)	Povp. točnost
L1	73.3%
L1+L2	80.0%
Najboljši objavljeni rezultati	
(kombinacija značilnic) [17]	88.2%
(samo gibanje) [17]	75.2%
Tabela 1: Rezultati na zbirki UCF Sports Action dataset, primerjani z najboljšimi objavljenimi rezultati. Predlagana metoda je boljša od [17] - izvedbe, ki upošteva samo trajektorije gibanja, brez drugih vizualnih informacij.
Vidimo, da tudi v konfiguraciji L1 + L2 naša metoda deluje bolje kot najboljša objavljena metoda [17]. Upoštevati je treba, da so metode, ki upoštevajo izključno gibanje, sorazmerno redke, in da veliko avtorjev
svoje metode uvršča v to kategorijo, čeprav upoštevajo tudi druge kanale vizualne informacije (npr. teksturo in obliko). Glede na to, da UCF Sports Action Dataset vsebuje veliko lepo strukturiranega gibanja, rezultati niso presenetljivi. Rezultati za zbirko Holywood2 so prikazani v tabeli 2.
Naša metoda (zajeti sloji)	Povp. natančnost
L1	28.9%
L1+L2	32.3%
L1+L2+L3	33.1%
Najboljši objavljeni rezultati	
(kombinačija značilk) [17]	58.3%
(samo gibanje) [17]	47.7%
SIFT+HoG+HoF (2009) [12]	32.6%
Tabela 2: Rezultati na zbirki posnetkov Holywood2 dataset in primerjava z najboljšimi objavljenimi rezultati ter rezultati, ki so jih dobili avtorji zbirke Holywood2.
Rezultati na bazi Holywood2 so slabši, čeprav so primerljivi z rezultati, ki so jih dobili avtorji zbirke Holywood2 [12].
5.2 Računska učinkovitost
Tabela 3 prikazuje porabljen čas na sliko, ki ga je porabila predlagana metoda v vsaki od stopenj obdelave podatkov med obdelavo najdaljšega posnetka iz zbirke Holywood2.
so predstavljale vstopne podatke za metodo podpornih vektorjev (SVM).
Tabela 4: Priblizšni čšasi, ki jih je porabil genetski algoritem za optimizacijo med učenjem (480 slik), časi, potrebni za učenje in testiranje po metodi podpornih vektorjev (SVM) za čelotno zbirko Holywood2, ter dimenzionalnost značšilnič, na katerih deluje SVM. Opravila, označena z zvezdičo (*), so tekla na vseh sštirih jedrih pročesorja vzporedno.
5.3 Učinkovitost zapisa znanja
Navajamo še količino pomnilnika, potrebno za zapis naučene kompozičionalne hierarhije. Struktura je shranjena v eni ali več indeksnih tabelah,	Tabele vsebujejo veliko ničšel iz dveh razlogov: nekatere sičer mogoče kompozičije se nikoli ne pojavijo v učnih podatkih, ali pa jih zavrze postopek optimizačije. Za preizkus smo v datoteko zapisali vsebino tabel v obliki 8- ali 16-bitnih podatkov, in jih učinkovito kodirali s pomočjo orodja gzip. Rezultate prikazuje tabela 5.
Opravilo	Skupni čas	Dimenzionalnost
*Optimizačija, L2	8 min	/
*Optimizačija, L3	45 min	/
SVM, L1	2.9s	120
SVM, L1 + L2	8.8s	740
SVM, L1 + L2 + L3	43.2s	5686
SVM, [10]	31.9s	3000
Opravilo	Cas/sliko
*Razlika Gaussov	28 ms
*NMS	158 ms
*Očena vektorjev gibanja	12 ms
Kvantizačija	1 ms
*Inferenča sloj-sloj	22 ms
Tabela	Dimenzije	Bajtov	Bajtov, gzip
V-1'2 V2'3	24 x 24, 8 bit 74x74, 16 bit	576 10 952	166 1112
Tabela 5: Dimenzije indeksnih tabel in njihova velikost pred učinkovitim zapisom s pomočjo orodja gzip in po njem.
Tabela 3: Cš as, porabljen v vsaki od stopenj obdelave, na sliko. Testirano na najdaljšem posnetku iz baze Holywood2, ki vsebuje 2958 slik. Opravila, označena z zvezdičo (*), so tekla na grafičnem pročesorju.
Tabela 4 prikazuje čas, potreben za optimizačijo v fazi učenja, ter čas, potreben za evalvačijo z metodo podpornih vektorjev (učenje razvrščevalnika in testiranje). Casi so prikazani za čeloten učšni posnetek in čelotno zbirko podatkov. Navajamo tudi dimenzionalnost značšilnič, ki
6 SKLEP
Rezultati predlagane metode so obetavni, čeprav je jasno, da gibanje ne vsebuje vseh potrebnih informačij za najboljsše razpoznavanje aktivnosti. Odličšni rezultati na zbirki posnetkov UCF Sports Ačtion Dataset kazejo, da se metoda odrezše tam, kjer opazovana aktivnost dominira v prizoru, gibanje v prizoru pa je za aktivnost značilno. Slabši rezultati na zbirki posnetkov Holy-wood2 imajo večš razlogov: aktivnosti v zbirki so močšno
odvisne od konteksta, gibanje samo pa v vecšini primerov iz te zbirke ne ponuja dovolj informacije za dobro razpoznavo aktivnosti. Zato imajo metode, ki zajamejo širok spekter vidne informacije, ceprav nenadzorovano, na tej zbirki prednost. Ugotovimo lahko tudi, da nobena od teh zbirk ne vsebuje zelo kompleksnih vzorcev gibanja, zato je za razpoznavanje potrebnih le malo število slojev kompozicionalne hierarhije. Predstavljena metoda sicer ne izkorišca moznosti masivno vzporednega racunanja tako ucinkovito kot metode, ki uporabljajo konvolu-cijo za detekcijo znacilnih tock v casovnoprostorskih volumnih posnetkov, vendar je mogocše na vzporednih racšunskih arhitekturah izvesti tako rekocš vse cšasovno potratne korake, ob tem pa izkoristiti tudi prednosti, ki jih prinasša hierarhicšno-kompozicionalna zasnova. V nadaljnjem delu bomo predstavljeno metodo zdruzšili s sorodnimi kompozicionalnimi pristopi za detekcijo oblik in tako še izboljšali uspešnost razpoznavanja.
Zahvala
To delo je nastalo v okviru raziskovalnega projekta J2-4284, raziskovalnih programov P2-0095, P2-0214 in P2-0098, ter pogodbe o financiranju št. 1000-10-310118, ki jih je vse financirala Javna agencija za raziskovalno dejavnost Republike Slovenije.
Literatura
[1]	C.-Y. Chen in K. Grauman. Efficient activity detection with max-subgraph search. V CVPR, str. 1274-1281. IEEE, 2012.
[2]	S. Fidler, M. Boben, in A. Leonardis. Evaluating multi-class learning strategies in a hierarchical framework for object detection.
V	Neural Inf. Proc. Systems, 2009.
[3]	S. Fidler in A. Leonardis. Towards scalable representations of object categories: Learning a hierarchy of parts. V CVPR, str. 1-8, 2007.
[4]	A. Gilbert, J. Illingworth, in R. Bowden. Action recognition using mined hierarchical compound features. TPAMI, 33(5):883-897, 2011.
[5]	M. Hoai, Z.-Z. Lan, in F. De la Torre. Joint segmentation and classification of human actions in video. V CVPR, str. 32653272. IEEE, 2011.
[6]	H. Jhuang, T. Serre, L. Wolf, in T. Poggio. A biologically inspired system for action recognition. V ICCV, str. 1-8, 2007.
[7]	O. Kliper-Gross, Y. Gurovich, T. Hassner, in L. Wolf. Motion interchange patterns for action recognition in unconstrained videos. V ECCV, str. 256-269. Springer, 2012.
[8]	I. Kokkinos in A. Yuille. Inference and learning with hierarchical shape models. Int. J. Comput. Vision, 93(3):1-25, 2011.
[9]	N. Kruger, P. Janssen, S. Kalkan, M. Lappe, A. Leonardis, J. Piater, A. Rodriguez-Sanchez, in L. Wiskott. Deep hierarchies in the primate visual cortex: What can we learn for computer vision? TPAMI, PP(99):1-1, 2012.
[10]	Q. Le, W. Zou, S. Yeung, in A. Ng. Learning hierarchical invariant spatio-temporal features for action recognition with independent subspace analysis. V CVPR, str. 3361-3368, 2011.
[11]	D. G. Lowe. Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vision, 60(2):91-110, 2004.
[12]	M. Marszalek, I. Laptev, in C. Schmid. Actions in context. V CVPR, str. 2929-2936, 2009.
[13]	M. Rodriguez, J. Ahmed, in M. Shah. Action mach a spatiotemporal maximum average correlation height filter for action recognition. V CVPR, str. 1-8, 2008.
[14]	K. F. Shahbaz, R. Anwer, J. van de Weijer, A. Bagdanov, M. Vanrell, in A. Lopez. Color attributes for object detection.
V	Comp. vis. patt. recognition, 2011.
[15]	S. Todorovic in N. Ahuja. Learning subcategory relevances for category recognition. V CVPR, str. 1-8, 2008.
[16]	E. Vig, M. Dorr, in D. Cox. Space-variant descriptor sampling for action recognition based on saliency and eye movements. V ECCV, volume 7578 of Lecture Notes in Computer Science, str. 84-97. 2012.
[17]	H. Wang, A. Klaser, C. Schmid, in C.-L. Liu. Action recognition by dense trajectories. V CVPR, str. 3169-3176. IEEE, 2011.
[18]	H. Wang, M. M. Ullah, A. Klaser, I. Laptev, in C. Schmid. Evaluation of local spatio-temporal features for action recognition. V Proc. British Machine Vision Conference, str. 127, sep 2009.
[19]	G. Zen in E. Ricci. Earth mover's prototypes: A convex learning approach for discovering activity patterns in dynamic scenes. V CVPR, str. 3225-3232. IEEE, 2011.
[20]	L. L. Zhu, Y. Chen, A. Torralba, W. Freeman, in A. Yuille. Part and appearance sharing: Recursive compositional models for multi-view multi-object detection. V CVPR, 2010.
Janez Perš je doktoriral leta 2004 na Fakulteti za elektrotehniko Univerze v Ljubljani. Trenutno je docent na Fakulteti za elektrotehniko. Raziskovalno deluje v okviru Laboratorija za strojni vid, ukvarja pa se s področjem računalniškega vida in analize zaporedij slik, sledenjem objektov, analizo človeškega gibanja, dinamično biometrijo ter z avtonomnimi in porazdeljenimi sistemi.
Matej Kristan je leta 2008 prejel naziv doktor znanosti s področja elektrotehnike na Fakulteti za elektrotehniko Univerze v Ljubljani. Trenutno je docent na Fakulteti za računalništvo in informatiko ter na Fakulteti za elektrotehniko na isti univerzi. Njegovo raziskovalno področje obsega verjetnostne metode računalniškega vida in strojnega učenja s poudarkom na vizualnem sledenju, verjetnostnih dinamičnih modelih, sprotnem učenju in mobilni robotiki.
Rok Mandeljc je diplomiral leta 2010 na Fakulteti za Elektrotehniko v Ljubljani, kjer je trenutno zaposlen kot mladi raziskovalec v Laboratoriju za strojni vid. Njegovo glavno raziskovalno področje zajema metode računalniškega vida, obdelave slik ter zlivanja informacije z različnih senzorjev za potrebe detekcije, lokalizacije in sledenja oseb v prostoru.
Stanislav Kovacic je redni profesor na Fakulteti za elektrotehniko Univerze v Ljubljani in predstojnik Laboratorija za strojni vid. Kot gostujoci raziskovalec je deloval v laboratoriju GRASP na University of Pennsylvania, Technische Fakultat der Friedrich-Alexander-Universitat v Erlangu in na Fakulteti za elektrotehniko in racunalništvo Univerze v Zagrebu. Njegovo raziskovalno delo zajema razlicne vidike analize slik in videa z aplikacijami v medicini, industriji in šsportu.
Aleš Leonardis je profesor na University of Birmingham in so-direktor centra Centre for Computational Neuroscience and Cognitive Robotics na isti univerzi. Prav tako je profesor na Fakulteti za Računalništvo in informatiko Univerze v Ljubljani in pridruženi profesor na Fakulteti za racunalništvo in informatiko Tehniške univerze v Gradcu. Njegovo raziskovalno podrocje obsega robustne in adaptivne metode racunalniškega vida, kategorizacijo objektov in scen, statisticne metode vizualnega ucenja, modeliranje 3D objektov in biološko motivirani vid. Je clan zdruzenja IAPR ter IEEE in IEEE Computer Society.