Elektrotehniški vestnik 74(1-2): 19-24, 2007 Electrotechnical Review, Ljubljana, Slovenija Sledenje več igralcev v športnih igrah na podlagi vizualne informacije Matej Kristan, Matej Perše, Stanislav Kovačič, Janez Perš Univerza v Ljubljani, Fakulteta za elektrotehniko, Tržaška 25, 1000 Ljubljana, Slovenija E-pošta: matej.kristan@fe.uni-lj.si Povzetek. V članku je predstavljen sledilnik za sledenje več igralcev v dvoranskih športnih igrah, kot sta rokomet in košarka, na podlagi vizualne informacije, pridobljene s kamero, nameščeno nad igriščem. Sledenje posameznega igralca je postavljeno v kontekst Bayesovega filtriranja za rekurzivno ocenjevanje a posteriori porazdelitve stanja tarče in temelji na metodah filtrov z delci. V članku sta obdelana dva glavna dela sledilnika: sledilnik za sledenje posameznega igralca in mehanizem za sledenje več vizualno podobnih igralcev. V okviru slednjega mehanizma predlagamo originalno rešitev, kjer sliko v vsakem časovnem koraku razdelimo v take neprekrivajoče se regije, da vsaka vsebuje le po enega igralca, ter tako dosežemo poenostavitev problema sledenja več tarč, kadar med vizualno podobnimi tarčami prihaja do trkov. Predlagani sledilnik smo primerjali z nerobustnim sledilnikom, ki ni vseboval mehanizma za obvladovanje situacij, ko med tarčami prihaja do trkov. Ugotovili smo, da predlagani mehanizem zmanjša število potrebnih intervencij operaterja in tako omogoča robustno in hitro obdelavo velike količine videopodatkov. Ključne besede: sledenje več tarč, športne igre, Kalmanov filter, Monte Carlo, filtri z delci Tracking multiple players in sport games using the visual information Extended abstract. In this paper we deal with the problem of tracking multiple players in indoor sports using the visual information obtained by the camera overlooking the court. In particular, we are interested in tracking multiple visually-identical targets as they interact. We propose a tracker based on a recursive estimator (Eqs. 1,2) of the posterior over the target's state, i.e., the player's position, which is implemented in the form of the well known particle fiter [1], namely, the Condensation algorithm [2]. Our tracker uses the probabilistic model of the player's appearance as well as the player's dynamical model (section 3). The player's appearance is modelled by an elliptical region, within which a color histogram, describing the texture, is sampled. A mask function is employed to make the appearance model robust to the clutter and an autoregressive scheme is used to update the model to the local changes in the appearance. The player's dynamical model is based on the assumption that the player cannot abruptly change his/hers velocity due to the effects of inertia. Section 4 deals with the problem of tracking multiple players through collisions and interactions. In particular, the collisions among the visually-similar players pose a threat of losing the correct identities of the colliding players. We propose a novel method (Algorithm 1) for solving the problem of the identity ambiguities, where at each time-step, the players are visually separated by constructing a Voronoi diagram [3] among their estimated positions (Fig. 3), such that each cell of the diagram Prejet 28. julij, 2006 Odobren 25. november, 2006 contains only one player. This results in a simplification of tracking, since each player can then be tracked efficiently by an independent single-player tracker. Experiments were conducted on a demanding data-set to evaluate the performance of the proposed multiple-player tracking scheme. The results (Tab. 1) showed that the proposed scheme increased the performance of the tracker by a few orders in terms of a lower failure rate. Key words: multiple target tracking, sports, Kalman filter, Monte Carlo, particle filters 1 Uvod Sledenje igralcev in pridobivanje njihovih položajev med športno igro obsega široko področje uporabe. Raziskovalci na področju športa lahko na podlagi gibanja igralcev analizirajo lastnosti športnikov, ki ločujejo zmagovalce od poražencev. Spričo tega znanja lahko trenerji načrtujejo individualne treninge posameznih igralcev in učinkovitejše taktike za doseganje vrhunskih rezultatov. Športni zdravniki lahko na podlagi podatkov o gibanju igralcev med tekmo ugotavljajo povezave med dinamiko gibanja ter obrabo sklepov, utrujanjem in nastajanjem poškodb. V zabavni industriji lahko medijske hiše izboljšajo videoprenose tekem z dodajanjem grafičnih vsebin, kot so npr. oznake na trenutnih položajih igralcev ali podatki o statistikah gibanja. V zadnjem času se pri sledenju igralcev uveljavljajo sistemi, ki temeljijo na vizualni informaciji. Kot primer omenimo sistema za sledenje igralcev rokometa [4; 5] in squasha [6], ki sta bila uporabljena v številnih raziskavah gibanja igralcev med tekmo (glej, npr. [7; 8]). Prvi razlog za popularnost takih sistemov je nizka cena strojne opreme, saj v osnovni obliki potrebujejo le kamero, zapisovalnik videovsebine, npr. DVD snemalnik, in osebni računalnik. Drugi razlog je, da so ti sistemi neinvazivni in ne zahtevajo pripenjanja posebnih identifikacijskih kartic na igralce, kakor to zahtevajo precej dražji sistemi, ki temeljijo na radiofrekvenčni tehnologiji. V preteklosti se je veliko raziskovalcev ukvarjalo s problematiko sledenja in analize gibanja na podlagi vizualne informacije, o čemer pričajo obsežni pregledi literature s tega področja [9; 10]. Eden od dejavnikov, ki močno vpliva na uspešnost sledenja, so vizualne značilnice, s katerimi tarčo zapišemo. Vendar pa je treba zaradi neeksaktne narave vizualne informacije upoštevati tudi lastnosti dinamike gibanja tarče. Klasični pristop k upoštevanju dinamike je uporaba Kalmanovega filtra [11]. Ta temelji na predpostavkah, da sta proces merjenja in dinamika tarče linearna Gausova procesa, kar pa je pogosto preveč idealizirana predpostavka za realne primere. Zato so se v zadnjem času uveljavile bolj splošne metode, imenovane filtri z delci (angl. particle filters) [1], ki ne predpostavljajo gausovosti in linearnosti procesov merjenja in dinamike. Te metode so se v računalniškem vidu prvič pojavile v obliki algoritma Condensation [2] in temeljijo na sekvenčnem vzorčenju Monte Carlo, zato se lahko spopadajo z bolj realnimi procesi in porazdelitvami kot Kalmanov filter. Pri sledenju več tarč je zelo pomemben mehanizem za ohranjanje pravilne identitete posamezne tarče. Ta še posebej vpliva na uspešnost sledenja v moštvenih športnih igrah, saj so igralci v moštvih tako rekoč identični na razdalji, s katere jih opazuje kamera. Kadar torej pride do trkov ali stikov med temi igralci, je zelo težko ohraniti njihove pravilne identitete. Zato se nekateri avtorji, npr. [12], lotevajo problema ohranjanja pravilne identitete tako, da poskušajo sočasno ocenjevati, katere meritve so generirale katere tarče, kar pa pri več kot treh tarčah pogosto pripelje do računsko neučinkovitih rešitev. Alternativen pristop je sicer sledenje vsake tarče s svojim sledilnikom neodvisno od preostalih, vendar pa je ta rešitev naivna. Razlog je v tem, da sledilnik za eno tarčo temelji na iskanju tiste tarče, ki je najbolj podobna nekemu referenčnemu vizualnemu modelu. Zato se pri trkih med več podobnimi tarčami pogosto zgodi, da po trku vsi sledilniki sledijo isto tarčo. V tem članku je predstavljen sledilnik za sledenje igralcev v dvoranskih športih, kot so rokomet, košarka itd. na podlagi vizualne informacije, pridobljene s kamero, nameščeno nad igriščem (slika 1). Sledilnik temelji na verjetnostnem principu filtrov z delci, ki uporablja statistični model vizualne predstavitve, kot tudi model gibanja igralca. Originalni prispevek tega članka je metoda za ohranjanje pravilnih identitet vizualno podobnih igralcev, kadar med njimi prihaja do trkov. Metoda temelji na razgradnji slike s pomočjo Voronoijevega diagrama, vpetega med trenutne ocenjene položaje igralcev na igrišču, tako da vsaka celica diagrama vsebuje le po enega igralca. Problem sledenja se s tem poenostavi, saj metoda omogoča učinkovito sledenje vsakega igralca z ločenim sledilnikom. Učinkovitost algoritma je demonstrirana na zahtevnem testnem posnetku rokometne tekme. H$|9R * ¡1111] Slika 1. Postavitev kamere in primer zajete slike Fig. 1. Camera setting and an image obtained by the camera Struktura članka je naslednja. V 2. poglavju predstavimo koncepte sledenja s filtri z delci. V 3. poglavju je opisan sledilnik za sledenje enega igralca, v 4. poglavju pa je predstavljen originalni mehanizem za ohranjanje identitet več vizualno podobnih tarč. Poskusi so opisani v 5. poglavju, v 6. poglavju pa predstavimo sklepe. 2 Filtriranje z delci Ker sledilnik, ki je predstavljen v tem članku, temelji na filtru z delci, bomo na tem mestu predstavili le glavne koncepte in oznake, bralec pa si lahko več o tem prebere v [1]. Naj bo X£_i stanje (npr. položaj, velikost) sledenega objekta ob času t — 1, yt-i naj bo meritev ob tem času in naj yi:t-i označuje sekvenco vseh meritev do trenutka t — 1. Sklicujoč se na Bayesovo teorijo se vsa zanimiva informacija o stanju tarče nahaja v njegovi a posteriori porazdelitvi |yi:i_i). Sledenje se tako prevede na rekurzivno ocenjevanje te porazdelitve spričo novih meritev yt. Ta proces lahko opišemo kot predikcijo (En. 1) in adaptacijo (En. 2). p(*t\yi:t-l) = / p(xi|x£-l)p(x£-l |yi:t-l) (1) p(xt|yi:t) j?}iLi-Nazadnje vsakemu delcu pripišemo utež glede na funkcijo verjetja wf* oc p(y^|x^) in uteži normiramo tako, da je njihova vsota ena. A posteriori porazdelitev ob času t je aproksimirana z novim uteženim naborom delcev p(x-t\yi:t) « Trenutno stanje tarče xt lahko potem ocenimo po minimalni srednjekvadratični napaki (angl. minimum-mean-square error) (MMSE) prek porazdelitve p(~xt\yi:t) (b) Slika 2. Leva slika prikazuje igralca na igrišču, katerega oblika je aproksimirana z elipso. Srednja slika prikazuje masko za zajem histograma, desna pa prikazuje barvni histogram igralca Fig. 2. Left image shows a player whose shape is approximated by an ellipse. The middle image shows the mask function and the right image shows the color histogram of the player Večino časa med tekmo je igralčev namen gibati se nepredvidljivo ter s tem zmesti nasprotnika. Vendar pa igralčevo gibanje ni povsem naključno, saj je njegova dinamika omejena z njegovo nalogo ter s fizikalnimi zakoni; t.j. igralčeva naloga je prepotovati pot od točke A do točke B, med tekom pa igralec ne more povsem nenadoma spremeniti svoje hitrosti zaradi vpliva inercije, zato sledilnik za enega igralca vsebuje dinamični model, ki modelira to inercijo z lokalnim glajenjem [13] in s tem poveča natančnost in robustnost sledenja. 4 Sledenje več igralcev Za zdaj predpostavimo, da poznamo trenutne položaje {^s}^^ vseh igralcev Np na igrišču. Ker športno igro opazujemo prek kamere, postavljene visoko nad igriščem (slika 1), lahko predpostavimo, da je mogoče v nekem trenutku igrišče razdeliti na taka neprekrivajoča se območja, da vsako vsebuje natanko enega igralca. Eden od pristopov k doseganju take razdelitve je graditev Voronoijevega diagrama [3], ki je popolnoma definiran z naborom semen S = {^s}^ in generira po pravilu najbližji sosed nabor A^-tih konveksnih območji \t = tako da vsako vsebuje le po eno seme. Primer Voronoijevega diagrama, vpetega med igralce rokometa, prikazuje slika 3. Slika 3. Voronoijev diagram, vpet med semeni/položaji sedmih igralcev rokometa Fig. 3. Voronoi diagram constructed among the positions of seven handball players Naj bo X^ trenutno skupno stanje igralcev, tj. stanje, sestavljeno iz trenutnih stanj vseh igralcev Cilj sledenja je torej ocenjevati a posteriori porazdelitev p(Kt\yi:t) tega skupnega stanja skozi čas. Ce poznamo trenutno razdelitev Vt, potem stanja postanejo medsebojno pogojno neodvisna pri danem \t in lahko pišemo Np p(Xt |yi:t, Vt) = np(wxt|yi:t, Vt), (5) 3 = 1 kjer je p(^^t\yi:t^t) a posteriori porazdelitev j-tega igralca pogojena z razdelitvijo V^. To pa pomeni, da lahko pri znani razdelitvi sledimo vsakega igralca z lastnim sledilnikom znotraj pripadajočega območja. Omejevanje j-tega sledilnika na območje (J)V lahko dosežemo z dodatno masko ki jo definiramo kot / i 1 • u G V «My( u)= : ' , (6) I 0 ; sicer kjer je u slikovni element na območju (^V. To pomeni, da pri sledenju j-tega igralca upoštevamo le tiste slikovne elemente, ki so vidni skozi masko «Mv(-). Pred iteracijo sledenja pravi položaji igralcev niso znani, zato izračun a posteriori porazdelitve prek skupnega stanja vključuje integracijo prek prostora Vt vseh mogočih Voronoijevih konfiguracij , np p(xt\y1:t)= / p(Vt\yi:t)l[p(U)xt\yi:uVt). (7) JVt j=1 Sicer bi v principu zgornji integral lahko aproksimirali z integracijo Monte Carlo, vendar bi to zaradi kompleksnosti tega problema pripeljalo do računske zahtevnosti, ki bi bila prevelika za praktično uporabo. Kot alternativo predlagamo podoptimalno metodo. Najprej vsakemu igralcu pripišemo utež 7rt-i na podlagi podobnosti med njegovim trenutnim in referenčnim histogramom. Tako dobijo igralci z bolje ocenjenim stanjem večje uteži kot tisti s slabše ocenjenim. Voronoijeva semena inicializiramo tako, da za vsakega igralca izračunamo predikcijo njegovega položaja. Izberemo igralca z največjo utežjo 7rt-i in izvršimo njegovo iteracijo sledenja z upoštevanjem ocenjene Voronoijeve razdelitve. Izračunamo novo stanje za tega igralca ter z njim posodobimo Voronoijevo razdelitev. Nato izberemo igralca z drugo največjo utežjo 7rt-i in postopek nadaljujemo, dokler ne izvedemo iteracij sledenja vseh igralcev. Natančnejši opis postopka za sledenje več igralcev je podan v Algoritmu 1. 5 Rezultati Predlagan algoritem za sledenje več igralcev iz 4. poglavja, označimo ga s Tmuit, smo primerjali s tako imenovano naivno različico algoritma, ki ni upoštevala Voronoijevega diagrama in je bila torej ekvivalentna naboru ločenih sledilnikov za vsakega igralca posebej; slednjo različico označimo s Tnaiv. V filtru z delci pri obeh sledilnikih smo uporabili 25 delcev na igralca. Oba sledilnika, Tmuit in Tnaiv, smo primerjali na 1257 slik dolgem posnetku rokometne tekme, kar je pri frekvenci zajema 25 slik na sekundo pomenilo 50 sekund tekme. Velikost slik v posnetku je bila 348x288 slikovnih elementov, igralci pa so bili veliki približno 9x9 slikovnih elementov. V posnetku smo sledili dve moštvi, sestavljeni iz šestih igralcev. Eno moštvo je bilo oblečeno v svetle drese, drugo pa v temne. Igrišče je bilo večinoma rumene in modre barve z nekaj reklamnimi nalepkami in je zaradi odbojnih lastnosti močno vplivalo na videz igralcev: na rumenem delu igrišča so bili svetli igralci videti rumene barve, na modrem pa modrikaste. Poleg tega je rokomet šport, kjer pogosto prihaja do trkov in fizičnih interakcij med igralci, zato je posnetek predstavljal zahtevno okolje za primerjanje sledilnikov. Tipičen testni posnetek prikazuje slika 4. Igralce smo pred začetkom sledenja označili ročno in jih sledili skozi celotno sekvenco slik. Ko je Algorithm 1 Algoritem za sledenje več igralcev. Algorithm 1 Multiple-player tracking algorithm. • Izračunaj sliko ozadja, npr. za vsak slikovni element z medianinim filtrom vzdolž časovne osi. • Inicializiraj sledilnik, npr. ročno. • Za t = 1, 2, 3 ... : 1. Vsakemu igralcu pripiši utež irt-i na podlagi podobnosti med trenutnim in referenčnim histogramom, ter igralce uredi po padajočih vrednostih uteži. 2. Inicializiraj semena prek predikcij stanj igralcev: S = {sj}^J=ii sj 3. Za j = 1 : Np (a) Zgradi nabor Voronoijevih področji V* = V}^^ prek nabora trenutnih semen S. (b) Zgradi Voronoijevo masko ^Mv(-)- (c) Izvedi iteracijo sledilnika iz 3. poglavja za j-tega igralca znotraj maske ^Mv(-)- (d) Posodobi j-to Voronoijevo seme z novo ocenjenim stanjem j-tega igralca. 4. Konec Za j Slika 4. Tipična slika iz testnega posnetka Fig. 4. Typical image from the test recording Tabela 1. Povprečno število odpovedi sledilnikov pri sledenju dvanajstih igralcev. Oznaki Fr/(50s) in Fr/(lmin) označujeta pričakovani števili odpovedi za 50 sekund in eno minuto. Tab. 1. Average number of failures encountered while tracking twelve players. Fr/(50s) and Fr/(lmin) denote the expected number of failures for 50 seconds and one minute, respectively. sledilnik Fr/(50s) Fr/ (1 min) T -1- naiv 39.0 46.5 Tmult 10.0 11.9 sledilnik izgubil enega od igralcev, smo sledenje ustavili, sledilnik ročno reinicializirali za tega igralca in nadaljevali sledenje. Ta postopek smo ponovili petkrat z obema sledilnikoma in izračunali povprečno število odpovedi na sekvenco. Odpoved sledenja smo obravnavali kot dogodek, ko je sledilnik očitno izgubil igralca in napake sam ni mogel odpraviti. Rezultati so podani v tabeli 1, iz katere sledi, da pričakujemo pri sledenju dvanajstih igralcev rokometa v eni minuti okoli 50 odpovedi, če sledimo s Tnaiv, pri uporabi predlaganega sledilnika Tmuit pa le 12 odpovedi. Se zgovornejši je podatek o številu intervencij/vnosov operaterja pri sledenju igralcev skozi vso tekmo, ki traja približno eno uro. Klasične metode za pridobivanje položajev igralcev na igrišču, ki so še vedno v uporabi, temeljijo na ročnem označevanju igralcev v vsaki sliki videoposnetka tekme. Pri 25 slikah na sekundo in pri dvanajstih igralcih na igrišču je tako potrebnih približno 106 vnosov operaterja. Četudi operater igralce označi le vsako sekundo, kar je ponavadi neuporabno za analizo hitrosti in pospeškov igralcev, je potrebnih približno 2 • 105 vnosov. Sledenje vseh igralcev pri 25 slikah na sekundo z uporabo Tnaiv zmanjša število potrebnih vnosov na 2820, pri sledenju s Tmuit pa je potrebnih le še približno 720 vnosov. Torej sledenje s Tmuit zmanjša število potrebnih vnosov operaterja za faktor 1500 v primerjavi s klasičnim ročnim vnašanjem. V primerjavi s Tnaiv pa Tmuit zmanjša število intervencij za štirikrat, kar nakazuje na učinkovito obvladovanje interakcij med igralci. 6 Sklep Predstavili smo sledilnik za sledenje več igralcev v dvoranskih športih. Sledenje je bilo formulirano v kontekstu verjetnostnega ocenjevanja s filtri z delci na podlagi vizualne informacije, pridobljene s kamero nad igriščem. Obdelali smo dva glavna dela sledilnika: sledilnik za sledenje posameznega igralca in mehanizem za ohranjanje pravilnih identitet vizualno podobnih igralcev med trki. Originalni prispevek tega članka je metoda za ohranjanje identitet igralcev, ki temelji na gradnji Voronoijevega diagrama med ocenjenimi položaji igralcev, z namenom razgradnje slike na regije, kjer se znotraj vsake regije nahaja le po en igralec. Tak pristop močno poenostavi sledenje, saj omogoča robustno sledenje vsakega igralca posebej. Predlagani sledilnik smo primerjali s sledilnikom, ki ni upošteval Voronoijevih regij na zahtevnem, približno minuto dolgem posnetku rokometne tekme. Rezultati so pokazali, da se sledenje izboljša v smislu zmanjšanja števila odpovedi, ko uporabimo predlagani mehanizem z Voronoijevimi regijami. References [1] M. Arulampalam, S. Maskell, N. Gordon, T. Clapp, A tutorial on particle filters for online nonlinear/non-gaussian Bayesian tracking, IEEE Trans. Signal Proc. 50 (2) (2002) 174-188. [2] M. Isard, A. Blake, Condensation -conditional density propagation for visual tracking, Int. J. Comput. Vision 29 (1) (1998) 5-28. [3] R. O. Duda, P. E. Hart, D. G. Stork, Pattern Classification, 2nd Edition, Wiley-Interscience Publication, 2000, Ch. Nonparametric Techniques, pp. 177-178. [4] J. Perš, S. Kovačič, A system for tracking players in sports games by computer vision, Electrotechnical Review 67 (5) (2000) 281-288. [5] J. Perš, M. Bon, S. Kovačič, M. Šibila, B. Dežman, Observation and analysis of large-scale human motion, Human Movement Science 21 (2) (2002) 295-311. [6] J. Perš, G. Vučkovič, S. Kovačič, B. Dežman, A low-cost real-time tracker of live sport events, in: Proc. Int. Symp. Image and Signal Processing and Analysis, 2001, pp. 362-365. [7] G. Vučkovič, B. Dežman, F. Erčulj, S. Kovačič, P. J., Differences between the winning and the losing players in a squash game in terms of distance covered, in: Science and racket sports III: Int. Table Tennis Federation Sports, 2004, pp. 202-207. [8] P. Pori, S. Kovačič, M. Bon, M. Dolenec, M. Sibila, Various age category-related differences in the volume and intensity of the large-scale cyclic movements of male players in team handball, Acta Universitatis Palackianae Olomucensis Gymnica 35 (2) (2005) 119-126. [9] J. K. Aggarwal, Q. Cai, Human motion analysis: A review, Comp. Vis. Image Understanding 73 (3) (1999) 428-440. [10] D. M. Gavrila, The visual analysis of human movement: A survey, Comp. Vis. Image Understanding 73 (1) (1999) 82-98. [11] R. E. Kalman, A new approach to linear filtering and prediction problems, Trans. ASME, J. Basic Engineering 82 (1960) 34-45. [12] D. Schulz, W. Burgard, D. Fox, A. Cremers, Tracking multiple moving targets with a mobile robot using particle filters and statistical data association, in: Proc. IEEE Int. Conf. Robotics and Automation, Vol. 1, 2001, pp. 665-670. [13] M. Kristan, J. Perš, M. Perše, S. Kovačič, Towards fast and efficient methods for tracking players in sports, in: ECCV Workshop on Computer Vision Based Analysis in Sport Environments, 2006, pp. 14-25. [14] K. Nummiaro, E. Koller-Meier, L. Van Gool, Color features for tracking non-rigid objects, Chinese J. Automation 29 (3) (2003) 345-355. Matej Kristan je leta 2005 magistriral na Fakulteti za elektrotehniko Univerze v Ljubljani. Trenutno je študent podiplomskega študija na isti fakulteti. Njegovo raziskovalno področje zajema postopke statističnega modeliranja v računalniškem vidu s poudarkom na sledenju in razpoznavanju. Matej Perše je leta 2004 diplomiral na Fakulteti za elektrotehniko Univerze v Ljubljani. Trenutno je mladi raziskovalec v Laboratoriju za slikovne tehnologije na isti fakulteti. Njegovo raziskovalno področje sta razpoznavanje aktivnosti v moštvenih športih, ter računalniško podprta taktična analiza. Stanislav Kovačič je profesor na Fakulteti za elektrotehniko Univerze v Ljubljani ter vodja Laboratorija za slikovne tehnologije na isti fakulteti. Njegovo področje raziskav zajema obdelavo biomedicinskih slik, industrijski vid ter postopke sledenja in razpoznavanja. Janez Perš je leta 2004 doktoriral na Fakulteti za elektrotehniko Univerze v Ljubljani. Trenutno je zaposlen v Laboratoriju za slikovne tehnologije na isti fakulteti. Njegovo področje raziskav so sledenje in analiza v športu, termovizija in dinamična biometrija.