Rendhagy´ o optikai ´ araml´ as detekci´ oja rejtett ? markov modellekkel 1 ´ Utasi Akos , Cz´ uni L´aszl´o2 1
MTA SZTAKI 1111 Budapest, Kende u. 13-17. Tel.: +3612796000/7300, Fax: +3612796292,
[email protected] 2 VIRT, Pannon Egyetem 8200 Veszpr´em, Egyetem u. 10. Tel.: +3688624800,
[email protected]
Absztrakt. Mivel az olcs´ o, k¨ ult´eri megfigyel˝ o rendszerek vide´ oin gyenge min˝ os´eg˝ u optikai ´ araml´ as m´erhet˝ o, de a mozg´ asmint´ ak meglehet˝ osen komplexek lehetnek, u ´j robusztus k´epfeldolgoz´ asi m´ odszerekre van sz¨ uks´eg, hogy megb´ızhat´ o, magas szint˝ u inform´ aci´ ot tudjunk a vide´ okb´ ol kinyerni. Dolgozatunkban olyan u ´j Markov modelleket mutatunk be, ahol nincs sz¨ uks´eg klasszikus objektum k¨ ovet´esi elj´ ar´ asokra, hogy rendhagy´ o mozg´ asmint´ akat tudjunk automatikusan ´eszrevenni. S˝ ur˝ u optikai a ´raml´ as sz´ am´ıt´ as´ at ´es kevert Gauss modellez´est alkalmazunk egy, vagy t¨ obbszint˝ u modellekben.
1.
Bevezet´ es
A vizu´alis megfigyel´es sokf´ele k¨ozleked´esi alkalmaz´asban fontos, mint pl. a monitoroz´as, anom´alia detekci´o, forgalmi dug´o detekci´o, tervez´es vagy el˝orejelz´es. A legt¨obb esetben val´os idej˝ u, robusztus m´odszerekre van sz¨ uks´eg, mivel igen sokf´ele zajhat´assal kell sz´amolni (elektromos zaj, optikai torz´ıt´as, r´azk´od´as, vill´odz´as, automatikus feh´er egyens´ uly, alulmintav´etelez´es, t¨om¨or´ıt´esi hib´ak) ill. a k¨or¨ ulm´enyek is zavar´oak lehetnek (es˝o, sz´el, ´ejszaka, naps¨ ut´es, csillog´asok, reflektorok, takar´asok, dinamikus alakok, ´arny´ekok, stb.). Mivel mindezeket nem lehet kik¨ usz¨ob¨olni, a feldolgoz´o elj´ar´asoknak kell megfelel˝oen kihaszn´alni a t´erbeli vagy id˝obeli hasonl´os´agokat a vide´ofolyamban. Cikk¨ unkben u ´j, robusztus rejtett Markov modell alap´ u (RMM) technik´akat mutatunk be, hogy megb´ırkozzunk ezzel a kih´ıv´assal. Az ´altalunk itt bemutatott m´odszereket legink´abb az k¨ ul¨onb¨ozteti meg a legt¨obb hasonl´o c´el´ u elj´ar´ast´ol, hogy nincs sz¨ uks´eg objektum k¨ovet´esre, ami zajos ´es bonyolult mozg´asmint´ak eset´en nehezen j´arhat´o u ´t. A javasolt m´odszerek tan´ıt´asi f´azis ut´an lesznek k´epesek a rendhagy´o esem´enyek detekci´oj´ara. Tipikus alkalmaz´asi ter¨ ulet a k¨ ult´eri felv´etelek elemz´es, mint pl. k¨ozleked´esi csom´opontok forgalm´anak monitoroz´asa. ´ A cikk eredm´enyei az al´ abbi publik´ aci´ oban jelentek meg: Akos Utasi and L´ aszl´ o Cz´ uni: ”Detection of unusual optical flow patterns by multilevel hidden Markov models”, Opt. Eng. 49, 017201 (Jan 19, 2010) ?
´ Cz´ Utasi A., uni L.
2
2.
Hasonl´ o munk´ ak
Alapvet˝oen k´etf´ele megk¨ozel´ıt´es van a vide´omegfigyel´es alkalmaz´asokban: specifikus mozg´asmint´akat ill. objektumokat keres¨ unk, vagy apriori tud´as n´elk¨ ul tetsz˝oleges rendhagy´o mozg´asok detekci´oj´at v´arjuk el. A legt¨obb m´odszer objektumk¨ovet´est alkalmaz (pl. [4], [20]) vagy k¨ ul¨onb¨oz˝o mozg´asok egy¨ uttes el˝ofordul´as´at keresi (pl. [9]). Azonban az objektumk¨ovet˝o m´odszerek nagy zaj eset´en nagy hib´aval dolgoznak, ahogy azt t¨obb cikkben is eml´ıtik (pl. [2]), jelent˝os elt´er´es van a gyakorlat ´es a laborat´oriumi k¨or¨ ulm´enyek k¨oz¨ott. J´o ´attekint´est ny´ ujt a probl´em´ar´ol az [1] cikk. RMM alap´ u m´odszerekkel gyakran tal´alkozhatunk a vide´oelemz´esben, ilyen pl. [19] ahol f´elig fel¨ ugyelt RMM-et alkalmaznak. A le´ırt m´odszer h´atr´anya a statikus h´att´erk´ep k´epz´es, ill. nem ismerj¨ uk teljes´ıtm´eny´et zajos k¨or¨ ulm´enyek k¨oz¨ott. A [20]-ban klaszterez´est haszn´alnak a norm´al ´es rendhagy´o mozg´astrajekt´ori´ak elk¨ ul¨on´ıt´es´ere, majd RMM-et tan´ıtanak a csoportokra. Ebben az esetben a trajekt´ori´ak meghat´aroz´asa lehet gond a zajok ´es takar´asok miatt. [6]-ben gyalogosforgalom optikai ´araml´as´at vizsg´alj´ak. A k´epet blokkokra bontj´ak ´es minden blokkhoz k¨ ul¨on modellt haszn´alnak. Sajnos csak belt´eri felv´eteleken v´egeztek ki´ert´ekel´est, ´es az ´altaluk haszn´alt f˝okomponens anal´ızis fontos, de ritka, rendhagy´o inform´aci´o elveszt´es´evel j´arhat. [7] szint´en RMM elemz´est haszn´al emberek mozg´as´anak modellez´es´ere belt´erben. Egyszer˝ u h´att´erk´epz´esi m´odszer¨ uk mindenk´eppen alkalmatlan k¨ ult´eri k´epek eset´en, b´ar a hib´as detekci´ok sz´am´at ´ıgy is t´ ul magasnak ´ert´ekelt´ek. Terjedelmi okokb´ol t¨obb ´erdekes cikk ([3], [5], [9], [17], [18], [21]) bemutat´as´at k´enytelenek vagyunk elhagyni, ezekr˝ol r¨ovid ´ert´ekel´est itt olvashat [23]. A fenti cikkek elemz´ese sor´an azt tal´altuk, hogy a legt¨obb m´odszer k¨ovet´est, azon alapul´o trajekt´ori´akat haszn´al, ill. f˝oleg belt´eri k´epeken tesztelt´ek ˝oket. N´eh´any cikk f˝okomponens anal´ızist alkalmaz dimenzi´o cs¨okkent´esre, ennek az a vesz´elye, hogy pont a rendhagy´o, ritka esetek fognak ´aldozatul esni az adatkompresszi´onak. A saj´at modelleink tesztel´es´ere gyenge min˝os´eg˝ u k¨ ult´eri vide´okat haszn´altunk, ill. ezek felhaszn´al´asval gener´altunk rendhagy´o esem´enyeket tartalmaz´o fotorealisztikus felv´eteleket. T¨obb ezer k´epkock´at haszn´altunk az egyes m´odszerek kvantitat´ıv vizsg´alat´ara.
3.
Javasolt megk¨ ozel´ıt´ es¨ unk
Az ´altalunk javasolt modellekben a k¨ovetkez˝o feltev´eseket, c´elkit˝ uz´eseket tessz¨ uk: – Az´ert, hogy elker¨ ulj¨ uk a k¨ovet´esen alap´ u probl´em´akat nem alkalmazunk k¨ovet´est. Helyette s˝ ur˝ u optikai ´araml´ast haszn´alunk az RMM l´etrehoz´as´ara. A f´elre´ert´esek elker¨ ul´ese v´egett kihangs´ ulyozzuk, hogy a trad´ıcion´alis k¨ovet˝o m´odszerek minimum folt, de ink´abb objektum alap´ u megfeleltet´est v´egeznek a k´epkock´ak k¨oz¨ott. Azaz ezeket a k´epter¨ uleteket kock´ank´ent meg kell c´ımk´ezni¨ uk ´es tulajdons´agokkal kell jellemezni¨ uk. A mi eset¨ unkben nincs sz¨ uks´eg a k´epkock´ak tartalma k¨oz¨ott ilyen megfeleltet´est keresni.
Rendhagy´ o optikai ´ araml´ as detekci´ oja rejtett markov modellekkel
3
– Azt felt´etelezz¨ uk, hogy el˝ofordulhat, hogy a vide´o r´ata sem stabil, ez´ert a mozg´asvektoroknak csak az ir´any´at fogjuk felhaszn´alni. Ugyanis ha az FPS nem konstans, a mozg´asok becs¨ ult sebess´eg´enek ´ert´eke megb´ızhatatlan. u modelleket haszn´alunk: egyr´eszt r´egi´okhoz k¨ot¨ott folytonos el– K´etszint˝ oszl´as´ u RMM-et haszn´alunk, m´asr´eszt ezekb˝ol hierarchikus reprezent´aci´ot hozunk l´etre, ´ıgy t´avolabbi ter¨ uletek mozg´asmint´aj´anak egy¨ uttes´et is modellbe tudjuk foglalni. – Fel¨ ugyelet n´elk¨ uli tan´ıt´ o f´azis sor´an param´eterezz¨ uk fel a modelljeinket. Az elj´ar´as k¨ ul¨onb¨oz˝o l´ep´eseit a k¨ovetkez˝o fejezetekben t´argyaljuk, az ´altal´anos archiket´ ur´at az 1. ´abra mutatja. A tan´ıt´asi f´azisban el˝osz¨or az optikai mozg´ast sz´am´ıtjuk ki ´es sz˝ urj¨ uk, majd ezt haszn´aljuk a r´egi´ok meghat´aroz´as´ahoz. Ezeken a r´egi´okon sz´am´ıtjuk ki az RMM param´etereket. V´eg¨ ul a lok´alis r´egi´okat ¨osszevonva diszkr´et ´allapot´ u RMM-et tan´ıtunk. A detekci´os f´azisban a kiv´alasztott r´egi´o (ROI - Region of Interest) mozg´asvektorai ´es a r´egi´ot reprezent´al´o RMM ´allapota hat´arozza meg a k¨ovetkez˝o ´allapotot ´es a l´atott esem´eny val´osz´ın˝ us´eg´et. V´eg¨ ul t¨obb r´egi´o egy¨ uttes ´allapot´at elemzi ki a fels˝o szint˝ u RMM.
ROIs
Optical Flow
Pixel-based motion statistics
Motion detection
MeanShift segmentation
ROI 1
HMM 2
Observations State/Probability
High-level HMM
HMM 1
Optical flow filtering
Observations
State/Probability
ROI 2
ROI K
HMM K
Optical flow estimation
Observations State/Probability
Observation
State/Probability
1. ´abra:: A javasolt rendszer ´altal´anos architekt´ ur´aja. A szaggatott vonal a tan´ıt´asi f´azist jel¨oli.
4
3.1.
´ Cz´ Utasi A., uni L.
Az optikai ´ araml´ as sz´ am´ıt´ asa
Hogy elker¨ ulj¨ uk a felesleges sz´am´ıt´asokat kevert Gauss modell (KGM) alap´ u v´altoz´asdetekci´ot haszn´alunk a nem v´altoz´o ter¨ uletek kiz´ar´as´ara. A [12]-ban ismertetett elj´ar´as j´ol m˝ uk¨odik k¨ ult´eri alkalmaz´asokban, mivel a v´altakoz´o objektumok sz´ın´et j´ol meg tudja tanulni (pl. f´ak, v´ız, es˝o, ´arny´ekok). A mozg´asvektorok sz´am´ıt´as´ahoz a Bergen [10] ´es a Lucas ´es Kanade [11] m´odszereket egyar´ant hat´ekonynak tapasztaltuk. Tov´abbi zajsz˝ ur´esre egyszer˝ u m´odszereket alkalmaztunk: a nagym´eret˝ u (k´epm´eret 30%-n´al nagyobb) ill. a nagyon kicsi (1 pixeln´el kisebb) vektorokat egyszer˝ uen nem vett¨ uk figyelembe. 3.2.
A k´ ep r´ egi´ okra bont´ asa
A k´epet a mozg´asnak megfelel˝on dinamikusan szegment´aljuk z´on´akra a [22]ban ismertetett m´odszerrel. A szegment´al´as c´elja, hogy a nagyon elt´er˝o mozg´asstatisztik´aval b´ır´o ter¨ uleteket k¨ ul¨on tudjuk modellezni. A tan´ıt´o f´azisban 8ir´any´ u mozg´asir´any hisztogrammokat k´esz´ıtett¨ unk a pixelekhez, amik a 8 f˝o ´ ´ ´ ir´anynak felelnek meg (Dir ∈{E,K,D,Ny, EK,DK,DNy, ENy}), majd az adatokat az un. MeanShift technik´aval szegment´altuk [13]. A 2. ´abra a bemeneti k´epet, a mozg´asir´any statisztik´at ´es a szegment´alt eredm´enyt mutatja (a sz´ınez´es pontos defin´ıci´oja a [22] cikkben olvashat´o).
2. ´abra:: Bemeneti k´epkocka; mozg´asir´any statisztik´ak [22]; MeanShift szegment´alt statisztik´ak; mozg´o ¨osszef¨ ugg˝o foltok (a kiv´alasztott r´egi´o pirossal kijel¨olve)
4.
Alacsony szint˝ u RMM
Ha a forgalom id˝obeli lefoly´as´at, ritmus´at szeretn´enk meg´erteni, akkor vektorok eloszl´as´ahoz id˝obeli ´allapotokat kell rendeln¨ unk az egyes r´egi´okban. Ha valamilyen anom´alia fog el˝ofordulni, akkor ebben a ritmusban kell valamilyen szokatlan v´altoz´ast ´eszrevenn¨ unk, pl. nem a megszokott ´allapot´atmenetet tapasztaljuk, vagy nem a szok´asos mozg´asir´anyok fordulnak el˝o egy ter¨ uleten. El˝osz¨or teh´at a lok´alis mint´akat fogjuk vizsg´alni, majd az ´ıgy kapott ´allapotokat fogjuk a k¨ovetkez˝o magasabb szinten figyelembe venni (5. fejezet). Kiv´alasztunk egy ROI-t, majd minden mozg´o foltj´aban (ezeket a mozg´asdetekci´o maszkj´ab´ol kapjuk meg, mint ¨osszef¨ ugg˝o ter¨ uleteket) megm´erj¨ uk az
Rendhagy´ o optikai ´ araml´ as detekci´ oja rejtett markov modellekkel
5
optikai ´araml´ast. Ezek ut´an ahelyett, hogy a foltok mozg´as´at k¨ovetn´enk, a foltok ter¨ ulet´ere egy 3D-s (x, y, sz¨ og) KGM-et illeszt¨ unk az un. Expectation– Maximization [14] m´odszerrel. A KGM-ek v´arhat´o ´ert´ek´et egy adott ROI-ban tekintj¨ uk ezek ut´an a RMM-ek megfigyel´es´enek. Ennek a m´odszernek az az el˝onye, hogy kicsi (pl. gyalogos) ´es nagy objektumok (pl. egy aut´obusz), ill. foltok eset´en is j´ol reprezent´alja a mozg´ast. Ct jel¨olje a foltok sz´am´at a ROI-ban t pillanatban, ´es Mtc jel¨olje a v´arhat´o ´ert´ekek halmaz´at, amely a c-dik komponensre lett illesztve (1 ≤ c ≤ Ct ). Megfigyelj¨ uk h´at a v´arhat´o´ert´ekek u ´ni´oj´at: Ot =
Ct [
Mtc .
(1)
c=1
Ugyanakkor a megfigyel´es defini´alhat´o az 1. egyenletben a k¨ovetkez˝o form´aban Ot = {ot,1 , ot,2 , . . . , ot,Kt }, ahol Kt = |Ot | jel¨oli a v´arhat´o´ert´ekek sz´am´at adott megfigyel´es eset´en. 4.1.
Jel¨ ol´ esek ´ es defin´ıci´ ok
Alapvet˝oen a [15] cikkben tal´alhat´o ”klasszikus” λ = {π, A, B} jel¨ol´est haszn´aljuk az RMM-ek defini´al´as´ara, N az ´allapotok sz´ama. Egy T hossz´ u megfigyel´esi szekvencia ´ıgy jel¨ol¨ unk O = O1 , O2 , . . . , OT . Eset¨ unkben minden megfigyel´es a sorozatban egy list´aja a lokaliz´alt ir´anyoknak (x, y, ´es sz¨og), ahogy kor´abban megadtuk (3.2. fejezet). M Gauss kever´ek´et haszn´aljuk a kibocs´at´asi val´osz´ın˝ us´egek modellez´es´ere: bi (Ot ) =
Kt Y k=1
bi (ot,k ) =
Kt X M Y
wi,l bi,l (ot,k ) ,
(2)
k=1 l=1
ahol bi,l (ot,k ) = N (ot,k |µi,l , Σi,l ). A k¨ovetkez˝o indexel´est haszn´aljuk: i ´es j jelenti az ´allapotokat (1 ≤ i, j ≤ N ); t adja meg az id˝ot az ´allapotok ´es megfigyel´esek sor´an (1 ≤ t ≤ T ); k egy megfigyel´esi mint´at jel¨ol; l pedig egy Gauss-t a KGM-ben (1 ≤ l ≤ M ). A k¨ovetkez˝o val´osz´ın˝ us´egi v´altoz´ok a szok´asos m´odon haszn´alatosak αt (i), βt (i), γt (i), ξt (i, j), ugyanakkor: γt (k, i, l) = γt (i)
wi,l bi,l (ot,k ) bi (ot,k )
(3)
annak val´osz´ın˝ us´ege, hogy a t-dik megfigyel´esnek a k -dik mint´aj´at az i -dik a´llapotnak az l -dik Gauss komponense gener´alta. (Mindezen alapfogalmakr´ol b˝ovebben a [15] cikkben lehet olvasni.) 4.2.
RMM param´ etereinek becsl´ ese
Egy kiv´alasztott ROI eset´eben kigy˝ ujt¨ott¨ uk azokat a k´epkock´akat, ahol t¨ort´ent mozg´as, majd ezt a k´epszekvenci´at E v´eletlen (5-10) hossz´ us´ag´ u r´eszre bontottuk, majd a Baum-Welch elj´ar´ast haszn´altuk [15] az RMM tan´ıt´as´ara. Sz¨ uks´eg
6
´ Cz´ Utasi A., uni L.
volt egy sk´al´az´asi m´odszert bevezetni, hogy elker¨ ulj¨ uk a kicsi sz´amok elveszt´es´eb˝ol ad´od´o sz´am´ıt´asi-´abr´azol´asi hib´at. Elvileg lehetett volna logaritmussal is sz´amolni a Baum-Welch elj´ar´as forward-backward sz´am´ıt´asai sor´an, ekkor azonban a tan´ıt´as jelent˝osen lelassult volna. Ezzel szemben egy gyors sk´al´az´asi technik´at vezett¨ unk be. 4.3.
Relat´ıv emisszi´ ok bevezet´ ese sk´ al´ az´ assal
A pontoss´agi probl´em´at a kibocs´at´asi val´osz´ın˝ us´egek defin´ıci´oja okozza a 2. egyenletben, ahol val´osz´ın˝ us´egek szorzat´at haszn´altuk bi (ot,k ). Ezek ´ert´ekei a KGM-ekt˝ol f¨ uggenek, de tipikusan igen kicsi ´ert´ekek (¿ 1), ´es a tan´ıt´as sor´an t¨obbsz¨or kell ˝oket iterat´ıv m´odon megbecs¨ ulni. Amennyiben a tan´ıt´asi sorozat megfigyel´esei er˝osen zajosak (ez igen tipikus eset) a Gauss-ok kovarianci´aja relat´ıv nagy lesz, hogy egyez´est ´erj¨ unk el. Ennek azonban az lesz a k¨ovetkezm´enye, hogy a kibocs´at´asi val´osz´ın˝ us´egn´el a szorzat (l´asd 2. egyenlet) exponenci´alisan 0-hoz fog tartani. 64 bites ´abr´azol´as eset´en a hat´ar 2−1022 (2.23×10−308 ), amib˝ol az k¨ovetkezik, hogy csak kev´es sz´am´ u mint´aval tudunk dolgozni m´eg QCIF ill. CIF felbont´asn´al is. Ez´ert kellett egy u ´j sk´al´az´ast bevezetni, aminek az lett a k¨ovetkezm´enye, hogy nagyobb sz´am´ u vektor feldolgoz´asa v´alt lehet˝ov´e. A relat´ıv kibocs´at´as teh´at: Kt Y b (o ) ˜bi (Ot ) = i . hP i t,k (4) N b (o ) k=1 j=1 j t,k hP i−1 N A sk´al´az´asi egy¨ utthat´o jel¨ol´ese et,k = b (o ) . j t,k j=1 Ezt a sk´al´az´ast be lehet vezetni a Rabiner f´ele [15] sk´al´az´asba is, ahol mindegyik αt (i) sk´al´azva lett az ¨osszes αt (i) ¨osszege ´altal. Bizony´ıthat´o, hogy az eredeti u ´jrabecsl˝o folyamatok (l´asd [23]) tov´abbra is haszn´alhat´oak maradnak, ha a relat´ıv kibocs´at´asi val´osz´ın˝ us´egeket haszn´aljuk. Egyed¨ ul a logaritmikus val´osz´ın˝ us´egi f¨ uggv´enyen kell v´altoztatni, ami az u ´jrabecsl˝o folyamat konvergenci´aj´at vizsg´alja: log P (O|λ) = −
T X τ =1
log (ˆ cτ ) −
Kτ T X X
log (et,k )
(5)
τ =1 k=1
ahol cˆτ jelenti a sk´al´az´asi egy¨ utthat´ok, de a relat´ıv emisszi´okkal sz´amolva. Ahhoz, hogy megkapjuk a megfigyel´esi sorozatot, a Viterbi u ´t sz´am´ıt´as´asra van sz¨ uks´eg [16], ahol a kibocs´at´asi val´osz´ın˝ us´eg ill. a forward-backward v´altoz´ok logaritmus´ara van sz¨ uks´eg. Ez esetben a kibocs´at´asi szorzat ¨osszead´ass´a alakul, ´ıgy itt nincs sz¨ uks´eg a relat´ıv val´osz´ın˝ us´egek bevezet´es´ere. A m´odszer¨ unk illusztr´al´as´ara egy olyan vide´o adatait mutatjuk be, ahol 5 ´allapotot ´es 6 Gauss f¨ uggv´enyt haszn´altunk az RMM-ben (N = 5 ´es M = 6). Kiv´alasztottunk egy v´eletlen megfigyel´est (Or ), ami 9 mint´at tartalmazott (Kr = 9). R¨ogz´ıtett¨ uk a kibocs´at´asi val´osz´ın˝ us´egek sz´am´ıt´ast bi (Or ) ill. a relat´ıv kibocs´at´asokat ˜bi (Or ) a Baum-Welch folyamat sor´an. V´eg¨ ul megkaptuk az RMM param´etereit ´es a legval´osz´ın˝ ubb ´allapotot, ami kibocs´athatta a v´eletlenszer˝ uen
Rendhagy´ o optikai ´ araml´ as detekci´ oja rejtett markov modellekkel
7
3. ´abra:: K´et megfigyel´es val´osz´ın˝ us´egei a mint´ak sz´am´anak f¨ uggv´eny´eben. Mindk´et (jobb ´es bal) esetben l´athat´o a sokkal lassabb konvergenci´aja a javasolt m´odszernek. Az eredeti kibocs´at´asokat (2. egyenlet) k´ekkel az u ´j m´odszert feket´evel jel¨olt¨ uk.
kiv´alasztott megfigyel´est Or -t. A 3. ´abra bal r´esze mutatja az eredeti (k´ek) ´es a relat´ıv ´ert´ekek (fekete) ¨osszehasonl´ıt´as´at. A f¨ ugg˝oleges tengelyen a szorzat logaritmus´at, a v´ızszintesen a felhaszn´alt mint´ak sz´am´at l´athatjuk. Ahogy a mint´ak sz´ama n˝o, a szorzat exponenci´alisan cs¨okken. M´ıg az eredeti m´odszerrel kb. 50 vektort, addig az u ´j m´odszerrel mintegy 200-400 vektort tudunk feldolgozni a ROI-n bel¨ ul. (A grafikonok a Baum-Welch algoritmus h´arom ´allapot´at is mutatj´ak: kezdeti l´ep´est, els˝o iter´aci´ot, ill a v´egs˝o ´allapotot. Az ´abra jobb oldala egy m´asik k´ıs´erletet mutat be, ahol Kr = 12, N = 4 ´es M = 12.) 4.4.
Rendhagy´ o mozg´ asok detekci´ oja
Miut´an megbecs¨ ult¨ uk az RMM param´etereit, a Viterbi algoritmus ´altal meg´allap´ıthatjuk a legval´osz´ın˝ ubb ´allapotokat. A mi eset¨ unkben ez alapvet˝oen a forgalom ritmus´at jelentheti egy forgalmas keresztez˝od´esben, amit a k¨ozleked´esi l´amp´ak hat´aroznak meg. Ennek illusztr´aci´oj´ara szolg´al a 4. ´abra. Az ´allapotokat Gauss-ok kever´eke jelenti adott ´atlaggal, kovarianci´aval ´es s´ ullyal. Az ´atlag az ir´anyt jel¨oli a ROI-n bel¨ ul, a s´ uly pedig az el˝ofordul´as gyakoris´ag´at mutatja. Ezeket k¨ ul¨onb¨oz˝o sz´ınnel (´atlag) ´es oszlopmagass´aggal (s´ uly) mutatja a grafikon. Val´os felv´etelekb˝ol egy val´os´agh˝ u vide´ot szerkesztett¨ unk, ahol egy aut´o a megszokott´ol elt´er˝oen a t¨obbi j´arm˝ u k¨oz¨ott rohan ´at (l´asd az 5. ´abr´at) ´es a betan´ıtott RMM-et haszn´altuk, hogy jelezze ezt az esem´enyt. Az Ot megfigyel´es val´osz´ın˝ us´eg´et az Si ´allapotban, az el˝oz˝o qt−1 ´allapot f¨ uggv´eny´eben ´ıgy adjuk meg: ½ aqt−1 ,i bi (Ot ) qt−1 6= −1 P (Ot , qt = Si |qt−1 ) = (6) πi bi (Ot ) qt−1 = −1 ahol qt−1 = −1 ismeretlen ´allapotot jel¨ol. A legval´osz´ın˝ ubb S? ´allapotot v´alasztjuk ki ´es annak a val´osz´ın˝ us´ege, hogy norm´alis jelens´egr˝ol van sz´o a k¨ovetkez˝o: v u Kt uY Kt P (Ot ) = aqt−1 ,? × t b? (ot,k ) . (7) k=1
8
´ Cz´ Utasi A., uni L.
(a)
(b)
(c)
(d)
(e)
4. ´abra:: Fent: p´elda a n´egy detekt´alt ´allapotra. Lent: a kijel¨olt ROI ´allapotsorozata, ahol a sz´ınek a mozg´as ir´any´aval vannak ¨osszef¨ ugg´esben. J´ol l´athat´o a forgalom ritmusa.
V´egeredm´eny¨ ul a − log P (Ot ) ´ert´eknek a sim´ıtott verzi´oj´at gener´aljuk, ezt mutatja az 5. ´abra. H´arom kock´at tal´altunk, ahol kiugr´oan alacsony az ´ıgy kapott val´osz´ın˝ us´eg. Az els˝o p´eld´ahoz hasonl´oan egy m´asik k´ıs´erletben egy m´asik j´arm˝ u v´ag ´at a keresztez˝od´esen szokatlan m´odon. Az eredm´enyt a 6. ´abra szeml´elteti a detekt´alt k´epkock´akkal ´es val´osz´ın˝ us´egi ´ert´ekekkel.
5.
Magas szint˝ u RMM
Mivel sok alkalmaz´asn´al nem el´eg a t´er egy relat´ıv kicsi r´esz´et szeml´elni, ez´ert sz¨ uks´eg lehet olyan modellre, ahol t¨obb kisebb ter¨ ulet ´allapot´anak egy¨ uttes´et vizsg´aljuk. 5.1.
Magas szint˝ u RMM bevezet´ ese
Jel¨olje© az alacsony szint˝ ª u RMM-ek sz´am´at L, az l. RMM ´allapotainak halmaz´at l S l = S1l , S2l , . . . , SN . Bevezet¨ unk egy u ´jabb S0 ´allapotot, amikor nincs mozg´as l ª © 0 l . A magas szint˝ u diszkr´et RMM λh egy ROI-ban, ´ıgy S l = S0l , S1l , S2l , . . . , SN l abc-j´et az alacsony szint˝ u RMM-ek ´allapotainak ¨osszes kombin´aci´oja adja ki: ©£ ¤ª Vh = Si11 , Si22 , . . . , SiLL 0 ≤ il ≤ Nl ; 1 ≤ l ≤ L . (8) QL ´ıgy az abc m´erete l=1 (Nl + 1) (a +1 a nem mozg´o ´allapotot jelenti). Ha vessz¨ uk a Viterbi u ´t ´altal adott ´allapot-sorozatokat ´es mozg´as n´elk¨ uli ´allapotokat, megkonstru´alhatjuk a magas szint˝ u RMM ´allapot-sorozat´at egysze-
Rendhagy´ o optikai ´ araml´ as detekci´ oja rejtett markov modellekkel
(a)
(b)
9
(c)
(d)
5. ´abra:: Els˝o k´ıs´erlet. Fent: az alacsony szint˝ u detektor ´altal jelzett k´epkock´ak. A rendellenes mozg´as´ u j´arm˝ u s´arg´aval van jel¨olve. Lent: a ROI-hoz tartoz´o val´osz´ın˝ us´egek. Az alacsony szint˝ u detektor a 2695. kock´at jelzi mint a rendellenes mozg´as kezdet´et. r˝ uen az L ´allapotsorozatok egy¨ uttes fel´ır´as´aval: £ ¤ £ ¤ £ ¤ Oh = q11 , q12 , . . . , q1L , q21 , q22 , . . . , q2L , . . . , qT1 , qT2 , . . . , qTL | {z } | {z } | {z } O1h
O2h
(9)
h OT
0
ahol qtl ∈ S l ´es Oth ∈ Vh . Cikk¨ unkben illusztr´aci´ok´ent 2 ROI-t v´alasztottunk ki, L = 2. A diszkr´et magas-szint˝ u RMM tan´ıt´asa a [15] cikk szerint t¨ort´ent. 5.2.
Rendhagy´ o mozg´ asok detekci´ oja
A demonstr´aci´oban ugyanazt a vide´ot haszn´aljuk, mint kor´abban a 4.4. fejezetben, k´et ROI alkotja az alacsony szintet. A modelltan´ıt´asok ut´an 7 ´allapotot kaptunk, amint a 7. ´abra illusztr´al. A detekci´ora a kor´abban m´ar ismertetett m´odszert haszn´altuk (4.4.). Minden t id˝oben kisz´amoltuk a legval´osz´ın˝ ubb S? ´allapotot az adott Oth megfigyel´eshez a 6. egyenlet szerint, majd defini´altuk Oth val´osz´ın˝ us´eg´et a szok´asos m´odon: ¡ h¢ ¡ h¢ Ph Ot = aqt−1 ,? × b? Ot . (10) Ebben a p´eld´aban azt tal´altuk, hogy a ROI szint˝ u RMM-ek nem jeleztek, de a hierarchikus detektor jelz´est adott, amint azt a 8. ´abra mutatja a h´arom alacsony val´osz´ın˝ us´eg˝ u k´epkock´aval. Ennek a m´odszernek el˝onye, hogy a rendhagy´o mozg´ast n´eh´any kock´aval kor´abban jelezte mint a kor´abbi modell (amikor a k¨oz´eps˝o ROI-t haszn´altuk).
10
´ Cz´ Utasi A., uni L.
(a)
(b)
(c)
(d)
6. ´abra:: M´asodik k´ıs´erlet. Fent: az alacsony szint˝ u detektor ´altal jelzett k´epkock´ak. A rendellenes mozg´as´ u j´arm˝ u pirossal van jel¨olve. Lent: a ROI-hoz tartoz´o val´osz´ın˝ us´egek. Az alacsony szint˝ u detektor az 1681. kock´at jelzi mint a rendellenes mozg´as kezdet´et.
6.
A teljes´ıtm´ eny vizsg´ alata, korl´ atoz´ asok
A p´eld´akban a tesztvide´ok felbont´asa 320x240 volt. 4800 db fel´ere kicsiny´ıtett kock´an vizsg´altunk a 4. fejezetben bemutatott m´odszert. A program egy 3GHzes Intel Xeon PC-n egysz´alas m´odban futott, a program k¨ ul¨onb¨oz˝o f´azisaiban m´ert¨ uk a sebess´eget: 1. F´azis - El˝ofeldolgoz´as: KGM v´altoz´asdetekci´o, optikai vektorok sz´am´ıt´asa ´es sz˝ ur´ese, foltok meghat´aroz´asa; 2. F´azis - Megfigyel´esek gener´al´asa: KGM illeszt´ese a vektor mint´akra a foltokon bel¨ ul; 3. F´azis - Anom´alia detekci´o: a 6. egyenlet ki´ert´ekel´ese. A tesztek szerint az els˝o f´azis 51.9 msec/frame, a m´asodik 17.24 msec/frame ¨ a harmadik 6.14 msec/frame sebess´eggel futott. Osszess´ eg´eben ez kb. 13FPS-t jelent. Ahogy a p´eld´ak mutatt´ak a detekci´os m´odszerek v´arosi k¨ozleked´esi alkalmaz´asokban haszn´alhat´oak. Term´eszetesen a m´odszernek korl´atai vannak: a kamer´aknak megfelel˝oen magasb´ol kell l´atni a forgalmat, ellenkez˝o esetben t´ ul sok lenne a takar´as (valamennyi takar´ast a m´odszer toler´al); megfelel˝o betan´ıt´as sz¨ uks´eges, amikor nem lehetnek rendhagy´o esem´enyek. Elvileg k´esz´ıthet˝o olyan alkalmaz´as, amikor az adatgy˝ ujt´es, tanul´as a detekci´oval p´arhuzamban fut, ill. a napszakok szerint v´alt adatb´azist a rendszer.
Rendhagy´ o optikai ´ araml´ as detekci´ oja rejtett markov modellekkel
11
7. ´abra:: A 7 megtanult ´allapot illusztr´aci´oi. A f˝o ir´anyokat s´arga vektorokkal jel¨olt¨ uk, a k¨or a mozg´as hi´any´at jelk´epezi.
7.
¨ Osszefoglal´ as
Az objektumok k¨ovet´es´en alapul´o elemz˝o m´odszerek sok neh´ezs´eggel kell szembes¨ uljenek zajos k¨ ult´eri felv´etelek eset´en, k¨ ul¨on¨osen ha sok objektum v´egez komplex mozg´ast. Cikk¨ unkben alternat´ıv megold´ast v´azoltunk fel, ahol val´os id˝oben, a s˝ ur˝ u optikai ´araml´as elemz´ese sor´an jutottunk el oda, hogy k´epesek vagyunk a mozg´as rejtett mint´azat´at megtanulni ´es az att´ol elt´er˝o viselked´est detekt´alni an´elk¨ ul, hogy a k´epkock´ak tartalma k¨ozt k¨ozvetlen megfeleltet´est tett¨ nk volna. A kibocs´at´asi val´osz´ın˝ us´egek relat´ıv sk´al´az´asa lehet˝ov´e tette, hogy jelent˝os sz´am´ u mint´at dolgozzunk fel, hi´aba is kicsiny azoknak az egy¨ uttes val´osz´ın˝ us´ege. A k´epet automatikusan szegment´altuk a mozg´asinform´aci´ok alapj´an ´es az egyes szegmensekre k¨ ul¨on-k¨ ul¨on ill. egy¨ uttesen is ´ep´ıtett¨ unk RMM modelleket, amelyek k´epesek a rendhagy´o mozg´asok felfed´es´ere. Term´eszetesen a modellek param´etereit az id˝o f¨ uggv´eny´eben lehet friss´ıteni, ´ıgy a m´odszerek adapt´al´odhatnak a megfigyelt ter¨ ulet v´altoz´ asaihoz, azonban ennek a k´erd´esk¨ornek a vizsg´alata t´ ulmutat a dolgozat korl´atain.
Irodalom 1. Hu, W. and Tan, T. and Wang, L. and Maybank, S.: A survey on visual surveillance of object motion and behaviors. IEEE Transactions on Systems, Man and Cybernetics, Vol 34, 2004, 334-352 2. Dick, A. R. and Brooks, M. J.: Issues in Automated Visual Surveillance. Proc. of the 7th International Conference on Digital Image Computing: Techniques and Applications, 2003, 195-204
12
´ Cz´ Utasi A., uni L.
(a)
(b)
(c)
(d)
8. ´abra:: Fent: p´elda a magas-szint˝ u RMM detekci´oj´ara. A rendellenesen mozg´o j´arm˝ uvet s´arg´aval jel¨olt¨ uk. Lent: a szokatlan mozg´asok val´osz´ın˝ us´ege. A t´enyleges szokatlan esem´eny a 2681. kock´an´al kezd˝odik.
3. Vaswani, N. and Chowdhury, A. R.: Activity recognition using the dynamics of the configuration of interacting objects. Proc. of the IEEE Conference on Computer Vision and Pattern Recognition, 2003, 633-640 4. Hongeng, S. and Nevatia, R. and Bremond, F.: Video-based event recognition: activity representation and probabilistic recognition methods. Computer Vision and Image Understanding, Vol 96, Num 2, 2004, 129-162 5. Boiman, O. and Irani, M.: Detecting Irregularities in Images and in Video. International Journal of Computer Vision, Vol 74, num 1, 2007, 17–31 6. Andrade, E. L. and Blunsden, S. and Fisher, R. B.: Performance Analysis of Event Detection Models in Crowded Scenes. Proc. of Visual Information Engineering, 2006, 427–432 7. Nair, V. and Clark, J. J.: Automated visual surveillance using hidden Markov models. Proc. of the 15th International Conference on Vision Interface, 2002, 8894, 8. Brand, M. and Kettnaker, V.: Discovery and Segmentation of Activities in Video. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 22, Num 8, 2000, 844-851 9. Zhong, H. and Shi, J. and Visontai, M.: Detecting Unusual Activity in Video. Proc. of Computer Vision and Pattern Recognition, Vol 2, 2004, 819-826 10. Bergen, J. R. and Hingorani, R.: Hierarchical Motion-Based Frame Rate Conversion. David Sarnoff Research Center Princeton NJ 08540, 1990 11. Bouguet, J.-Y.: Pyramidal Implementation of the Lucas-Kanade Feature Tracker. Intel Corp., Microprocessor Research Labs, 2000 12. Stauffer, C. and Grimson, W. E. L.: Adaptive background mixture models for realtime tracking. Computer Vision and Pattern Recognition, IEEE Computer Society Conference on., Vol 2, 1999, 246-252
Rendhagy´ o optikai ´ araml´ as detekci´ oja rejtett markov modellekkel
13
13. Georgescu, B. and Shimshoni, I. and Meer, P.: Mean shift based clustering in high dimensions: A texture classification example. Proc. 9th International Conference on Computer Vision, 2003, 456-463 14. Dempster, A. P. and Laird, N. M. and Rubin, D. B.: Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society. Series B (Methodological), Vol 39, Num 1, 1977, 1-38 15. Rabiner, L. R.: A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, Num 2, Vol 77, 1999, 257-286 16. Forney, G. D.: The viterbi algorithm. Proceedings of the IEEE, Num 3, Vol 61, 1973, 268-278 17. Beleznai, C. and Fr¨ uhst¨ uck, B. and Bischof, H.: Human tracking by mode seeking. Proceedings of the 4th International Symposium on Image and Signal Processing and Analysis, 2005, 1-6 18. Moeslund, T. B. and Hilton, A. and Kr¨ uger, V.: A survey of advances in visionbased human motion capture and analysis. Computer Vision and Image Understanding, Num 2-3, Vol 104, 2006, 90-126 19. Zhang, D. and Gatica-Perez, D. and Bengio, S. and McCowan, I.: Semi-Supervised Adapted HMMs for Unusual Event Detection. Proceedings of the Conference on Computer Vision and Pattern Recognition, 2005, 611-618 20. Jiang, F. and Wu, Y. and Katsaggelos, A. K.: Abnormal Event Detection from Surveillance Video by Dynamic Hierarchical Clustering. Proceedings of the International Conference on Image Processing, 2007, 145-148 21. Moeslund, B. T. and Granum, E.: A survey of advances in vision-based human motion capture. Computer Vision and Image Understanding, Vol 81, Num 3, 2001, 231-268 ´ and Cz´ 22. Utasi, A. uni, L.: Anomaly Detection with Low-level Processes in Videos, Proceedings of the International Conference on Computer Vision Theory and Applications. 2008, 678-681 ´ and Cz´ 23. Utasi, A. uni, L.: Detection of unusual optical flow patterns by multilevel hidden Markov models. Optical Engineering, 2010
