MOZGÓ KAMERA KÉPÉNEK FELDOLGOZÁSA

MOZGÓ KAMERA KÉPÉNEK FELDOLGOZÁSA TDK dolgozat Pázmány Péter Katolikus Egyetem

Információs Technológiai Kar 2006

Készítette: Karba Krisztián Losteiner Dávid Konzulens: Dr. Szirányi Tamás Külsı konzulens: Havasi László

Tartalomjegyzék

1. Motiváció …………………………………………………………………… 2. 2. Elıtér szegmentálása ……………………………………..……….………… 3. 2.1 Feladat 2.2 Megközelítés 2.3 Valódi statisztikai háttérmodell 3. Periódusdetekció …………………………………………………….…...… 10. 4. Mozgó kamera képeinek összefőzése ……………………………………… 16. 4.1 Bevezetés 4.2 Megközelítés 4.3 Megoldásunk 4.4 Harris sarokdetekció 4.5 Pontok párosítása Lucas-Kanade eljárással 4.6 Homográfia 4.7 A mozaikoló algoritmus vázlata 4.8 Kimenetek 5. Összegzés …………………………………………………………………... 26. 6. Köszönetnyilvánítás ………………………………………………………... 28. 7. Források ………………………………………………………………….…. 29.

1

1. Motiváció Az utóbbi években jelentısen megszaporodtak a megfigyelı kamerák és mivel ezek olcsó és megbízható megoldást nyújtanak, igen komoly rendszereket alakítanak ki belılük. Egy-egy épület vagy akár egy egész városkerület megfigyelése lehetséges akár egyetlen szobából. Ezeknek a kameráknak a hatékonyságát sokszor növelik oly módon, hogy a látószög a lehetı legnagyobb legyen. Ezt akár optikai eszközök (speciális lencsék) vagy mechanikus eszközök (mozgó kamera) útján is el lehet érni. Ezeknek a kiterjesztéseknek azonban némi bonyolultság az eredménye, ezek minimalizálásához szeretnénk megoldással szolgálni. Jelen dolgozatunkban a mozgó kamerák képeivel foglalkozunk, ahol is azt vizsgáljuk, hogy miként lehet automatizálni az ilyen videófolyamok feldolgozását. Ebben három problémával szeretnénk foglalkozni. Az elsı probléma az, hogy hogyan tudjuk elkülöníteni egymástól a mozgó (mozgó autó, gyalogos stb.) és álló objektumokat (közlekedési táblák, házak, parkoló autó stb.). Álló kamera esetében ez viszonylag egyszerő, azonban mozgó kamera esetében az adott képen minden objektum elmozdul az elızı képhez viszonyítva. A második probléma annak megállapítása, hogy mikor történt kezelıi közbeavatkozás, azaz a kamera nem azt a képet mutatja, mint amikor a normál, megszokott mozgását végezné. A harmadik probléma pedig a kamera pozíciójának becslése, hogyan tudjuk megállapítani, hogy a teljes megfigyelt területbıl mit lát aktuálisan a kamera. A problémák megoldását nehezítik a kamera sajátosságai: azaz a képminıség gyenge VHS, a motor szabálytalan mozgása miatt a képek mintavételezése nem mindig ugyanabban a pozícióban történik és gyakran több mozgó objektum jelenik meg egyszerre. Mivel a megfigyelés éjjel-nappal folyamatosan szokott folyni, ezért a fényviszonyok is változnak, ez is nehézséget jelent a megoldásban. Ráadásul fontos kritérium a valós idejő feldolgozás is. Kritériumok:
VHS minıségő adatfolyam (PAL rendszer) valamint 10-20 képkocka/másodperc sebességő videó, amely egy mozgó kamera képeit tartalmazza
mivel ez egy komplex (akár többkamerás) rendszer része, ezért igen rövid futásidı és erıforrásigény
az elıtér-háttér szegmentációja a lehetı legjobb minıségő legyen (további feldolgozás miatt) felismerhetı alakokkal, jármővekkel.
Annak felismerése, hogy csupán a kameramotor mozog vagy történt a vezérlıterembıl beavatkozás történt. A kérdések megoldásához léteznek már jó tudományos eredmények. A háttér szegmentációjához a statisztikai háttérmodellek (Stauffer, Grimson: Adaptive background mixture models for real-time tracking, Butler et al:Real-Time Adaptive Foreground/Background Segmentation, Kim, Harwood, Davis: Real-time foreground–background segmentation using codebook model). Ami a állóképek regisztrációját illeti, arra is született már megoldás: Szeliski, Shum: Creating Full View Panoramic Image Mosaics, Robinson: Collaborative Vision and Interactive Mosaicing). Ezek azonban nem elégítik ki a kritériumban foglaltakat, mivel nem a fent említett céllal készültek, hanem sokkal speciálisabb esetekre (álló kamera, nincs mozgó objektum, stb.). A cél tehát az, hogy egyetlen kamerával a lehetı legnagyobb területet megfigyelhessük, illetve a minket ténylegesen érdeklı információkat kinyerjük. Ezzel csökkenthetıek az ilyen jellegő rendszerek költségei és a megbízhatóságuk is növelhetı.

2

2. Elıtér-háttér szegmentálása: 2.1 Feladat: Egy igen lényeges lépés a videótartalom szőrésére, hogy a videófolyamból kiemeljük a számunkra lényeges részeket, vagyis az elıteret. Az elıtér megközelítése sokféleképpen történhet, amire már igen jól mőködı eljárásokat ismerünk [1]. Azt mondhatjuk, hogy egy jelenetben a háttér az kvázi statikus, tehát egyáltalán nem vagy csak bizonyos szabályok szerint változik (pl. a szél fújja a fa leveleit). Minden, ami ettıl (bizonyos mértékben) eltér, azt elıtérnek tekinthetjük és a továbbiakban ezt a két adathalmazt külön kezelhetjük. 2.2 Megközelítés: A legegyszerőbb megközelítés az lenne, hogy minden elıtér, ami az elızı idıpontban még nem azon a helyen volt, ahol jelenleg. Ezt egyszerő kivonással és küszöböléssel meg is kapjuk, ahol t az adott idıpillanatot jelenti, t-1 pedig az azt megelızıt (mivel a videó diszkrét idıben van):

sgn( I t −1 ( x , y ) − I t ( x , y ) > τ )

(2.1) Ahol a két azonos pozíciójú képpont különbségének nagysága fogja megmondani, hogy elıtér-e vagy sem. A küszöb (τ) itt statikus és mivel minden kamerának kicsit zajos a képe (ezt az optikába bejövı fotonok okozzák, egy szórása ezeknek mindig van) a küszöb értéket nem érdemes túl kicsire venni. A döntés annyiból áll, hogy a függvény 1-et (elıtér) vagy 0-át (háttér) ad vissza. Mivel ez a megoldás nagyon statikus, ezért csak nagyon ritkán lehet alkalmazni, mivel rengeteg zajt kapunk az elıtérben. A másik fontos dolog, hogy szeretnénk a háttérre valamiféle modellt adni. Itt semmilyen információnk nem lesz a háttérrıl, csupán az, hogy az elsı képhez képest nincs nagy változás. A kapott eredményt az 2.1.ábra mutatja. Igyekezzünk tehát a problémát másik oldalról megközelíteni úgy, hogy adjunk becslést a képsorozat hátterére, majd ezt kivonva az aktuális képbıl (és küszöbölve) megkapjuk az elıteret [2]. Ha csak az elsı frame-et vennénk figyelembe (2.2. ábra), akkor a fényviszonyok jelentıs változása esetén újra kéne indítani az egész folyamatot. Itt a hátteret folyamatosan figyeljük és frissítjük a háttérmodellünket (B) úgy, hogy egy rövid idı után megfelelı elég nagy biztonsággal tudjunk dönteni a képi tartalom hovatartozásáról.

sgn( I t ( x, y ) − Bt ( x, y ) > τ )

(2.2) Jelen esetben a küszöb értéket már egy 3×3-as ablakból számoljuk. A lényeg tehát, hogy az eddig beérkezı pixelekrıl egy nagyon egyszerő statisztikát csinálunk és ezzel becsüljük a hátterünket. Ami ettıl a statisztikától bizonyos mértékben eltér, az az elıtér. Ezt a háttérmodellt úgy alakítjuk ki, hogy az azonos helyre beérkezı pixelértékeket egy súlyozással (α) hozzáadom a háttérmodellhez. Az eljárást futó átlaggal (running average) végezzük:

Bt = α I t −1 ( x , y ) + (1 − α ) Bt −1 ( x , y )

(2.3)

ahol 0 < α < 1 Még nem ért véget a folyamat, hiszen ha az adott pixel egy bizonyos mennyiségben már elıtérként szerepelt (ez szintén egy küszöbérték: m), akkor a frissítésnél már a súlyozást elhagyjuk és az Bt = It értékadással a háttérmodellbe helyezzük. Ezáltal a háttérmodellünk módosul. Ennek akkor van értelme, ha például egy autó leparkol a képen és ezáltal a háttérmodell részévé válik egy bizonyos idı múlva. Egy hátránya az eljárásnak, hogy sok a statikus változó, így egy adott kamerához mindig be kell állítani ezeket és amennyiben az algoritmust más forráson is szeretnénk alkalmazni, így azokhoz tartozó paramétereket újra kell keresni. Az eredmény a 2.3. ábrán látható. Az eljárás természetesen annál jobban mőködik, minél több csatornát használunk föl benne és minél nagyobb bitmélységben dolgozunk. Ha egyszerő intenzitásképpel dolgozunk 8 bites színmélységgel, akkor az elıterünk meglehetısen lyukas lesz, hiszen ha egy elıtérben mozgó 3

objektum intenzitásértéke egybeesik a háttérmodellben lévıvel, akkor azt természetesen háttérnek fogjuk tekinteni. Ezen természetesen segíthetünk egyszerő képfeldolgozó eljárásokkal (pl. Medianszőrı), de elképzelhetıek olyan helyzetek, amikor ezek kevésnek bizonyulnak (pl. piros ruhában egy téglafal elıtt).

bemenet elıtér 2.1. ábra: Szimpla kivonás az egymást követı képeken, ahol nem igazán tudjuk kivenni a mozgóalakzatokat és háttérmodellünk sincs*

bemenet

elıtér 2.2. ábra: A háttérmodell csupán az elsı kép alapján*

háttér

bemenet elıtér elıtér 2.3. ábra: A hátteret futó átlaggal becsüljük (kiindulás az elsı frame) ahol α =0.005 volt. A háttérmodellben megjelennek az elıtér objektumok által húzott csíkok* (*) A megvalósítás Pythonban készült, futtatásához az Intel OpenCV -bıl készített wrapper kell.

4

2.3 Valódi statisztikai háttérmodell: Tételezzük fel, hogy a háttérmodell minden egyes képpontja (még ha változik is) leírható statisztikai úton. Ez annyit tesz, hogy a háttérmodellünkben nem csak egyféle értéket engedünk meg, hanem akár többet is, amivel a modellnek egy memóriát adunk. A háttértanulás folyamán ezeket a háttérmodelleket (tehát most már többet) frissítjük és ezek között keressük meg a legvalószínőbbet [3, 4, 5, 6, 7]. Erre a Stauffer-féle módszer azt mondja, hogy tekintsük ezeket Gaussi eloszlásoknak. Minden egyes háttérmodellünket egy Gaussi görbével reprezentálunk. Az ok, amiért több ilyen görbét kell alkalmaznunk az az, hogy a valós videók esetén mind a globális fényviszonyok, mind az egyes felületek pixelértékei is változnak az idıben. Ezekre a szórásokra illesztve egy széles haranggörbét azt addig frissítjük, míg egy stabil várható értéket nem kapunk abban. Ekörül az érték körül egy bizonyos szórással helyezkednek el a feltételezett háttér képpontértékei. Ha a várható érték körül csökkentjük a szórást, akkor egyre szőkebb tartományon tudjuk megmondani, mi is a háttérmodell pixelértéke, ami ezen kívül esik, az vagy egy másik háttérmodellbe tartozik, vagy elıtér. A háttérmodellek száma legyen K, ami egy nem túl nagy szám (szokásosan 2-7), amikben három értékkel írjuk le a lehetséges háttérmodellt: a pixel várhatóérték vektorával (µ), a becsült szórással (σ) és a becsült súllyal (ω). A fentebb említett módon szükség van egy súlyértékre (α) is, amivel majd a frissítés folyamán dolgozni fogunk. Az eredményünk tehát egy valódi statisztika az eddig megfigyelt képsorozat alapján, ahol egy valószínőséget tudunk mondani az adott pixel értékére adott idıpillanatban: K

P ( X t ) = ∑ ω i ,t *η ( X t , µ i ,t , Σ i ,t )

(2.4)

i =1

Itt a fentebb említett paraméterek szerepelnek, ahol a Σi,t az adott i-edik görbe (η) esetén a kovariancia mátrix a t-edik idıpillanatban. A Gaussi valószínőségi sőrőségfüggvényt megkapjuk:

1

η ( X t , µ , Σ) =

n 2

(2π ) Σ 2

1 2

e

1 − ( X t − µ t )T Σ − 1 ( X t − µ t ) 2

(2.5)

A kovariancia mátrixot a Σ k,t =σ k I -ból kapjuk, ahol I az egységmátrix, méghozzá azért, mert feltételezzük, hogy a színértékek varianciája azonos. Ez sima 1 csatornás bemenet esetén csak egy skalárt jelent, míg például RGB-ben mind a 3 színcsatorna varianciáját azonosnak vesszük. A megfigyelt pixelek eloszlását ilyen módon egy ú.n. mixture of Gaussians (Gaussi eloszlások „keveréke”) modellben tároljuk [3]. Ezt a módszert több helyen alkalmazzák a hangfeldolgozásban (pl. beszédfelismeréshez) is. A bemenet pixelértékei tehát ezeket az eloszlásokat (a háttérmodellünket) fogják frissíteni. Amennyiben tekinthetjük úgy ezt a képpont sorozatot, mint egy stacionárius folyamatot, akkor a legegyszerőbb módja a beérkezı értékek közötti hasonlóság maximalizálásának a várt érték maximalizálása [8] (EM = Expectation Maximalization). Ez tulajdonképpen egy maximum likelihood keresést takar. A probléma viszont abban áll, hogy ezt csak egy közelítéssel tudjuk csupán vizsgálni, hiszen a pixelek idıben változnak (új és új objektumok, fényességváltozás), ezért kell folyamatos frissítéssel tanítani a háttérmodellünket ami finomítani fogja azt. A videófolyamból tehát mind Xt pixelértéket összehasonlítunk a modell K eloszlásaival addig, amíg olyat nem találunk amihez illeszkedik. Ez ugye annyit tesz, hogy a sőrőségfüggvény várható értékéhez elég közel van (ez a távolság λ=2.5-3 a zaj függvényében). Ennek az az elınye a állandó küszöböléshez képest, hogy az árnyékban (eltérı fényviszony) könnyen eltőnı mozgó elıtérobjektumok megmaradnak. Amennyiben nincs olyan eloszlás, amihez illeszkedne az Xt akkor az eddig legvalószínőtlenebbet kicseréljük rá valamilyen inicializációval tehát új eloszlás kerül a 5

modellbe. Az eloszlások valószínőségüket tekintve elsıdlegesen egy ω súlyozással vannak reprezentálva, amit a már fentebb tárgyalt módon kapunk:

ω k ,t = (1 − α ) * ω k ,t −1 + α * M k ,t

(2.6) Ahol α a tanulási faktor, Mk,t pedig egy logikai érték, ami 1 ha illeszkedett Xt a k-adik eloszláshoz és 0 ha nem (ekkor csökken a súly). Ezek után még szükség van az eloszlások normalizálására, mivel azok száma fixen K. A tanulási ráta reciproka fogja megmondani, hogy mekkora idı szükséges egy elıtérobjektum pixelének háttérmodellbe illesztéséhez, azaz mekkora sebességgel fognak az eloszlás-paraméterek változni [5]. A súly ωk,t pedig tulajdonképpen egy kauzális átlaga a legutolsó k. eloszlásnak, amihez az Xt illeszkedett az [1,t] idıintervallumban. Az ok, amiért így számolunk fıleg abban keresendı, hogy nem szeretnénk exponenciális ablakolással végigmenni az eddig eltelt idı intervallumon a várhatóérték kiszámítása okán [3]. Az eloszláshoz tartozó többi paraméter is elárul sok mindent az adott háttérmodell megbízhatóságáról. Amit eddig nem tárgyaltunk, az a többi paraméter frissítése:

µ t = (1 − ρ ) * µ t −1 + ρ * X t

(2.7)

σ t 2 = (1 − ρ ) * σ t −1 2 + ρ * ( X t − µ t ) T * ( X t − µ t )

(2.8)

(2.9) ahol ρ = α η ( X t | µ k , σ k ) Ha két modellbe is beleesik a bejövı Xt , akkor nyilván azt választjuk, amihez egyrészt nagyobb a súlya, másrészt kisebb a varianciája („szőkebb” az eloszlása). Az eloszlások sorba rendezését ω/σ alapján vesszük majd. Az itteni tanulási faktort (ρ) közelíthetjük α/ωk,t -val ha illeszkedik az eloszláshoz és 0-val ha nem [5].

2.4. ábra: A Gaussi eloszlásgörbék külön-külön. Kezdetben még alacsony súly és nagy variancia (piros), majd a legvalószínőbb (kék)

Mindezek után az adott eloszlások alapján döntünk, hogy melyek a legvalószínőbb eloszlások, amik a tényleges háttér meghatározásánál szerepet játszanak. Ehhez egy küszöbérték megadása (T) még szükséges, ami azt mondja meg, hogy mekkora elıfordulási súllyal kell a az eloszlást a tényleges háttérmodell részeként tekinteni:

6

b

B = arg min ( ∑ ω k > T ) b

(2.10)

k =1

Így az sem jelent problémát, hogy ha multimodális a hátterünk (mozognak a falevelek), hiszen a T nagyobbra vételével azok az értékek, amiket felvehet az adott helyen a Xt mind benne lehetnek a modellben, így az elıtér szegmentációjánál nem tőnnek fel. A GMM tehát megfelelınek bizonyul a továbbiakban tárgyalt feladatokhoz, feltéve persze egy nagyon fontos dolgot, nevezetesen hogy az illesztéseknek a képek között elég pontosnak kell ahhoz lenni, hogy a háttérmodellt fel tudjuk belıle építeni. A mozgó kameránál ugyanis az a gond merül fel, hogy a nem megfelelı illesztés miatt nem tud annyira stabil helyzetbe kerülni a GMM, hogy folyamatosan on-line szegmentációval jó eredményt adjon. 2.4 Megjegyzések: Természetesen az elıtér-háttér szegmentációjára számtalan más megoldás is született már. Ezek közül van, ami a Stauffer-féle módszer idıbeli ablakolásával (L-recent window) igyekszik javítani a kimenetet/futásidıt [4] és vannak ettıl teljesen eltérı megoldások is. Ezek részletezésére jelen dolgozatban nem térünk ki, de a teljesség igénye nélkül pár kulcsszó az alkalmazott metódusokról: optical-flow [9], kernel denisity estimation [10]. Ezek egy része teljesen független a GMM-tıl (Gaussian Mixture Models) egy másik része pedig felhasználja bizonyos egyéb technikák mellett. 2.5 Eredmények álló kamerán: A fent említett GMM-t elıállító algoritmust megvalósítottuk C++-ban. Mint az alábbi ábrákon is jól látszik nagyon jó szegmentáció végezhetı vele. Ami valóban elınye, hogy akár szürkeárnyalatos bemeneten is jól mőködik, tehát a 3 csatorna (2.5.ábra) ellenében egyetlen csatornán kell csak végigfutni az algoritmusnak (2.6-2.7. ábra), így jóval gyorsabb lett és a kimenet minısége is megfelelı maradt. Maga a háttérszegmentáló modul teljesen GNU C++-ban készült, semmilyen külsı függvénykönyvtárat sem alkalmaztunk. A bemenet kezeléséhez (fájl vagy kamera) az Intel OpenCV könyvtárát használtuk, mivel ez platformfüggetlen és a késıbbiekben szükség lehet a beépített függvényeire. Az inicializációs értékeket az [5]-ben megjelöltel (ık végeztek egy tesztet, hogy mely paraméterek a legmegfelelıbbek általánosan) összhangban a következıképpen vettük fel (2.1. táblázat) Paraméter Érték

K λ α T ωkezdı 3 2.5 0.005 0.7 0.05 2.1. táblázat: a használt paraméterek a megvalósítás során

σkezdı 30

Sikerült elérni, hogy az algoritmus fusson 320×240-es 1 csatornás bemeneti képeken online, ami annyit tesz, hogy max 15ms alatt lefutott egy asztali számítógépen (2.8. ábra). A teszteket elsısorban a PETS 2001-es képsorain hajtottuk végre, de használtunk valódi megfigyelıkamerákat is Budapestrıl valamint különbözı USB-s webkamerákkal. A függelékben található weboldalról letölthetı egy futtatható próbaváltozat.

7

bemenet

valóban mozgó objektumok (piros)

elıtér háttér 2.5. ábra: RGB háttérmodell, semmilyen utólagos szőrést sem használtunk

bemenet háttér elıtér 2.6. ábra: Egycsatornás háttérmodell, láthatóan csak pár pixel esetén hibázott a rendszer

bemenet (piros mozog) elıtér háttér 2.7. ábra: Szintén egycsatornás bemenet Budapestrıl

8

2.8. ábra: Egy sebességteszt a ctime.h-val. A 320×240-es felbontáson (fekete) még láthatóan real-time (0-15ms) idıbe kerül a frissítés A Gauss eloszlások paramétereinek változási sebessége (2.9. ábra) egy adott pontban mutatja, hogy mi történik a háttér adaptálódásakor. A bemeneten az éppen aktuális háttérmodellt felváltja egy másik, mivel egy autó leparkolt oda (PETS 2001/1 – [168, 146] képpont). Itt lehet látni, hogy a súly ill. a többi eloszlás paraméter miként változik az idıben és hogyan áll be egy stabil pontba. A súlygörbe (piros) láthatóan letörik amikor beáll az autó, majd ezt követıen az új várható érték jelenik meg (kék). Közben a szórás nem változik, tehát mikor a háttér részévé válik egy objektum, addigra a szórása a súly csökkenése miatt eléggé lecsökken (zöld). Ennek magyarázata a paraméterek futó átlagának súlyozásából adódik (ld. fentebb).

2.9. ábra: A legvalószínőbb eloszlás paramétereinek változása az idıben. Látható, hogy mikor áll be az autó és hogy mikor válik a háttér részévé. (mu=várható érték, sigma=szórás, weight=súly)

9

3 Periódusdetekció Ahogy korábban is említettük, a videófolyam feldolgozása során két fontos problémával is szembesülnünk kellett: meg kell állapítani, hogy mikor történt kezelıi közbeavatkozás illetve be kell azonosítani az aktuálisan bejövı képkockát. Ezen problémák megoldásához szükséges a periódusdetekció, azaz meg kell találnunk a kamera körbefordulási periódusának hosszát, illetve ez alapján a bejövı képekbıl össze kell állítani egy teljes periódust. Mindez azért fontos, hogy a háttér szegmentáció pontosan mőködjön a következı lépés során. A legkézenfekvıbb megoldás az lenne, hogyha a bejövı képet összehasonlítanánk egy, már korábban regisztrált képkockával és ebbıl számítanánk a periódus hosszát. Ez a megoldás viszont nem mőködik az oda-vissza pásztázó kamerák esetében, mivel ha az elsı képet a közvetlenül a kamera holtpontja elıtt regisztráljuk, a másodikat pedig a fordulási pont után, akkor a periódushosszra nem pontos végeredményt kapunk. Egy másik lehetséges megoldás szerint több egymás utáni képet hasonlíthatnák a már elızıekben regisztrált képsorozathoz. Ez sem bizonyult hatékonynak, mivel a kamera nem mindig azonos pozícióban készíti a képeket, ezért a az egyes képek közötti hibákból számolt hiba még nagyobb is lehet, mintha csak egyetlen képet vizsgáltunk volna. A megoldáshoz ugyanúgy a képek közötti hasonlóságot (image similarity) használjuk fel. Ilyen irányú eljárásokat többen is használták [14], [16], [11], általában statikus kamerára és elkülönített objektumok (pl. gyalogosok) felismerésére és analízisére (követésére) adtak megoldási javaslatot. Mi a a kamera periódusának detekciójához nem különítettünk el objektumokat, a kamera sem statikus, de a Cutler és Davis által is használt korrelációs mátrix [11] hatékonynak bizonyult. A képeket egy bizonyos ideig folyamatosan regisztráljuk, amíg elegendı számú, N darab kép összegyőlik. Tapasztalatok szerint N értéke körülbelül a feltételezett periódushossznak 2-3-szorosa, mi tipikusan 800-1000 képet vettünk figyelembe. A regisztrált képekbıl egy N×N mérető korrelációs mátrixot készítettünk. A korrelációs mátrixot a következı képlettel számoltuk:

K ij = Ii , I j =

∑ I (x, y) − I (x, y) i

j

(3.1)

(x,y)

i, j ∈ [1...N] azaz két kép pixelértékeinek (x,y) különbségét abszolútértékben összegezzük. A korrelációs mátrixot értékeit lenormálva a bemeneti képek magasságának és szélességének szorzatával egy N×N mérető képet – Similarity Plot – készítünk (S), ez az 3.1. ábrán látható. Természetesen, a [12]ben közölt képletek és megfogalmazások itt is érvényesek:

1. S(t1 , t 2 ) = 0 2. S(t1 , t 2 )=S(t 2 , t1 ) kp + t1 ) ≈ 0 2 kp 4. S(t1 , − t1 ) ≈ 0 2 ahol t1 , t 2 ∈ [1...N], p a periódus hossza, k ∈ ℕ

(3.2)

3. S(t1 ,

10

Mivel minden kép korrelál önmagával (1), ezért kapjuk a „fıátlóban” a fekete vonalat, azaz a különbség ezek között 0. A (2) a korrelációs mátrix szimmetrikusságából következik A (3) és (4) az elsı kettı egyenlet egyenes következménye: a fıátlóval párhuzamos vonalak jelképezik a következı periódusokat, míg a a fıátlóra merıleges vonalak a kamera visszafele mozgásából adódnak.

3.1. ábra: Similarity Plot

A gyakorlatban azonban nincs szükség ekkora mérető mátrixra, ehelyett egy M×N-es mátrixot használtunk, ahol M<
a similarity plot

A távolság kiszámítására több lehetıség adódhat: 1. Megkeressük a négyzetrács csomópontjait, és a szomszédos csomópontok távolságát vesszük. Ez a megoldás nem éppen robosztus, mivel a csomópontok kiválasztásához bináris képre van szükség, ehhez egy küszöböt kell beállítani. Minden képre megfelelı küszöbértéket kiválasztani nem minden esetben lehetséges: ha túl alacsony értéket választunk, akkor csak a fıátló marad meg a képen, magasabb érték esetén olyan pontok is megmaradhatnak, ami nem a kamera holtpontját jelzik.

3.2. ábra: A similarity plot binarizált képe A 3.2. ábrán a similarity plot binarizált képét ábrázoltuk. Látható, hogy egyes csomópontok eltőntek, míg az átlók egyes helyein vastagabb vonalak maradtak meg. Ezeken a helyeken a 11

kamera lassabban mozog, így az egymás után regisztrált képek között kicsi a különbség, azaz a korreláció nagy. Ezt a csomópontok detektálásakor figyelembe kellene venni, de az olyan képeken, ahol nagyobb küszöbértéket alkalmazunk, már nem lehet megmondani, hogy a képen mi az ami valóban csomópont és mi az ami csak a lassabb mozgásból származik. A szélesebb csomópontokhoz való viszonyítás hibás periódushosszt jelezhet, ami tapasztalatunk szerint 10-15 képkockányi eltérés is lehet a valódi periódushosszhoz képest. Ez a mértékő eltérés viszont már a háttértanulási folyamathoz elégtelen becslés. Ezért ez a fajta megoldás, igaz gyors lenne, de nem megbízható. 2. A vonalakat Hough-transzformációval is ki lehet szőrni. Ez viszont akkor nem mőködik, amikor az eredetileg egyenes vonalak a kamera szabálytalan mozgása miatt (pl. gyorsabban mozog) már görbékké fajulnak 3. A harmadik, általunk használt megoldás a projekció alapú távolságszámolás. Ehhez, a similarity plotot egy 45 fokos egyenesre projektáljuk, de elıtte küszöböljük a jobb eredmény érdekében. A projekciót ábrázolva ezeket az eredményeket kapjuk:

3.3. ábra: A similarity plot projekciója, binarizált esetben

3.4. ábra: A similarity plot projekciója nem binarizált esetben A projekción a csúcsok jelzik a similarity ploton található átlókat. Látható, hogy amikor a similarity plotot elızıleg binarizáltuk, akkor jobban szegmentálhatóak a maximális csúcsok, így pontosabban lehet majd a periódushosszt becsülni. A következı lépés a valóban lokális maximumok megtalálása a projekción belül. 1. elsı lépésként beállítunk egy minimális küszöbértéket, amelynél a csúcsnak nagyobb értékőnek kell lennie, ennek optimális értékét heurisztikus módon, tesztelés közben találtuk meg 2. ezután lokális maximum keresést hajtottunk végre a projekción, de csak azokat a csúcsokat vettük figyelembe, amelyeknek a magassága a beállított küszöb felett volt.

12

A maximumkeresést nem átfedı ablakokban végeztük, majd utána egy eltolt ablakkal megismételtük, mindezt azért, hogyha az elızı keresésnél találtunk egy lokális maximumot, de annak közelében van nála nagyobb csúcs, akkor azt vesszük inkább figyelembe. Így elérhetı, hogy valóban csak a piros függıleges vonalak által jelzett csúcsokat találjuk meg. A képeken a globális maximum jelenti a fıátlót, a tıle távolabbi lokális maximumok a vele párhuzamos átlókat. Így a globális maximumtól jobbra lévı csúcsok távolsága jellemzi a következı pár periódus hosszát. Ebbıl már az x-tengely irányú távolságszámolással megkaphatjuk a becsült periódushosszt, ami eléggé pontosan közelíti a valódi periódushosszt. A tesztek során maximum 1-2 képkockányi eltérést tapasztaltunk, nagyobb eltérést is csak olyan esetekben, mikor az egymás utáni képek között a kamera alig mozdult el, ilyenkor nehéz volt kiválasztani, melyik képkocka jelenti a periódus végét. Ahogy már az elızıekben is említettük, kisebb mérető korrelációs mátrixot használunk a periódushossz becslésére. Mivel mi azt a képet keressük, ami a legelsı bejövı képkockához illik a legjobban, ezért nincs szükség a következı periódus további képeire, fıleg olyan esetekben nem, amikor a következı periódusban rendellenes kameramozgás következett be (pl. a kamera felgyorsul, 3.5. ábra), ilyenkor a projekció csúcsainak pozíciói is eltolódnak balra, ezáltal hibásan becsülve a periódushosszt

3.5. ábra: A nyíllal jelölt helyen a kamera mozgása felgyorsult

Kisebb mérető korrelációs mátrix esetében ez nem okozott gondot, a periódushossz becslése hiba nélkül vagy kisebb hibákkal történt. Amikor a similarity ploton nem használtunk küszöbölést, akkor felgyorsult kameramozgás esetén 10-15 képkockányi eltérést tapasztaltunk a becsült és a valódi periódushossz között. Az eredményeket az 1. táblázat mutatja két különbözı kamera esetén:

13

Valódi periódushossz Becsült periódushossz

1. periódus 217 216 6. periódus 197 195

2. periódus 236 234 7. periódus 199 198

3. periódus 211 208 8. periódus 216 220

4. periódus 165 162 9. periódus 212 209

2. kamera Valódi periódushossz Becsült periódushossz

1. periódus 387 381

2. periódus 385 382

3. periódus 472 476

4. periódus(*) 772 774

1. kamera Valódi periódushossz Becsült periódushossz

5. periódus 165 165 10. periódus 225 223

3.1 táblázat: Két kamera esetén hogyan alakulnak a periódushosszok. Megjegyzések: (*) Ebben a periódusban a kezelı megállította a kamerát, ezért ilyen magas a periódushossz

Miután megállapítottuk a periódushosszt, már összeállíthatjuk a bejövı képekbıl az aktuális periódust. Ezt az eljárást természetesen folyamatosan el kell végezni a bejövı képeken, hogy a háttértanulás megfelelıen mőködjön. A következı lépés annak észlelése, ha esetleg a kamera nem szabályosan mozgott: az összegyőjtött képeket meg kell vizsgálni, hogy történt-e beavatkozás a kezelı által. Ennek több célja is van: 1. mivel ilyen esetekben a kamera pozíciója véletlenszerően változik, ezért a háttértanulás nem folyik 2. a késıbbiekben, ezekbıl a képekbıl statisztikai módszerekkel ki kellene nyerni azokat az információkat, hogy mi volt az az ok, ami a közbeavatkozást kiváltotta Ennek alapjául egy eléggé elterjedt módszert használtunk fel: az optikai folyamot (optical flow). Ennek az az elınye, hogy real-time végezhetı a vizsgálat. Az egymás utáni képeken megvizsgáljuk, hogy a jellegzetes pontok mennyit mozdulnak el. Beállítottunk két küszöbértéket (melyeket ugyancsak heurisztikusan találtunk meg, a tesztelések során). Az optikai folyam számolásakor kapott értéktıl függıen három esetet különböztettünk meg:

1. az elsı esetben, ha a számolt érték az elsı (kisebb) küszöbérték alatt volt, akkor azt kapjuk, hogy a kamera elmozdulása viszonylag kicsi illetve egy helyben áll. Ez olyankor lehetséges, ha a kezelı megállította a kamerát, hogy egy területet jobban megfigyelhessen, tehát közbeavatkozás történt. Sajnos olyankor is kicsi az elmozdulás, amikor a kamera a fordulási holtpontjára ér, ilyenkor a kamera elmozdulása egy kis ideig ugyancsak nulla. Azonban ez nem jelent igazi problémát, mert a késıbbi statisztikai elemzésnél ezeket az eseteket figyelmen kívül lehet hagyni 2. amikor a számolt érték a két küszöbérték közé esik, akkor a kamera a szokásos, periodikus mozgását végzi

14

3. a számolt érték nagyobb, mint a második beállított küszöb. Ebben az esetben a kamera pozíciója hirtelen megváltozott, a kezelı új pozícióba állította a kamerát, mert valószínőleg valamilyen esemény felkeltette a figyelmét. Tapasztalatunk szerint a hirtelen megjelenı objektumok (pl. gyorsabban mozgó gépkocsik) nem jeleztek beavatkozást, azért mivel nem igazán tartalmaznak a jellegzetes pontokat. A kamerapozíciójának becsléséhez (ami ugyancsak szükséges a háttértanuláshoz), egy elég egyszerő mozaikképet készítettünk, ami semmi más feladatot nem lát el, mindössze az aktuális kép pozícióját ez alapján becsüljük. A két kép közti 2D-s transzlációt Kuglin és Hines [13] módszerével számoljuk:

F1 (η, ξ) ⋅ F2* (η, ξ)(η, ξ) j2 π (x 0 η+ y0 ξ ) CPS(η, ξ) = = e F1 (η, ξ) ⋅ F2* (η, ξ)(η, ξ)

(3.3)

ahol F1 és F2 a két kép Fourier-transzformáltja. Ebbıl inverz Fourier-transzformációval (ICPS) és maximumkereséssel

arg max ICPS(x, y) (x,y)

(3.4)

megkapjuk a kívánt x és y-irányú elmozdulást. Ez alapján már összeállítható egy kezdetleges mozaikkép, amelynek nem muszáj pontosnak lennie, viszont a bejövı képkocka helyét (a kamera pozícióját) ebbıl kell becsülnünk.

3.6. ábra: A mozaikkép a fenti módszerrel egy belvárosi kamera képébıl.

3.7. ábra: Kerettel az aktuálisan regisztrált képkocka helyét látjuk a mozaikban egy másik kamera esetén.

15

4. Mozgó kamera képeinek összefőzése 4.1 Bevezetés: A mozgó kamera képei egy adott régiót mutatnak, mi azt szeretnénk azonban hogy legyen képünk a teljes megfigyelt területrıl. Természetesen a teljes kép egy része frissül csak automatikusan, de nekünk tudnunk kell ennek pontos helyét. Ez a probléma elég sok helyen felvetıdik a földmérésektıl kezdve (légi felvételek) a robot irányításon át egészen a térfigyelésig és fotófeldolgozásig. Azt szeretnénk tehát, ha egy teljes képünk lenne és tudjuk is, hogy éppen hol tartunk rajta. Speciális optikákkal akár egész nagy panorámakép is készíthetı, de persze itt kameramozgás nincs (4.1. ábra). Ezt a viszonylag egyszerőnek tőnı problémát a kilencvenes évek óta sokféleképpen megközelítették már. Sajnos a mai napig nem született általános érvényő eljárás arra, hogy több képet miképpen lehet összefőzni (pontosan) eggyé. Rengeteg probléma merül fel a fényviszonyok, a zajos bemenet és a mozgó objektumok miatt. Amit eddig sikerült megoldani, az fıleg állókép felvételek összefőzése egy panorámaképbe automatikusan. Itt (mivel nem on-line dolgozunk) van idı az egyes képek elemzésére és pontos összeillesztésére, mindezek persze komoly elı- és utófeldolgozást jelentenek. A kereskedelemben eddig elıforduló termékek tulajdonképpen ezt a célt tőzték ki, tehát több fotó összeillesztését. Ez a mi esetünkben nem elég, mivel egy kamera egyrészt folyamatosan mozog (robot, térfigyelı) másrészt mozgó objektumok tőnnek fel, amik nem magának a kameramozgásnak (ego motion) a részei.

4.1. ábra: Visegrád, http://panoramas.hu

4.2 Megközelítés: Alapvetıen kétféle eljárás létezik jelenleg a valós idejő képösszefőzésre (mosaicing): a teljes képet feldolgozó (direct observations) és csak bizonyos pontokra (feature based) fókuszáló megoldások [17]. Értelemszerően a direkt metódusok a teljes kép valamely tulajdonságát használják fel, mint a gradienskép. A másik megközelítés pedig a számunkra érdekes pontok (interesting points) megkeresésével kezdıdik és ezekkel dolgozunk tovább. Mind a kettınek vannak elınyei és hátrányai, nevezetesen ha az egész képen dolgozunk, akkor a megbízhatóság hatalmas számítási igényt igényel(het), míg a csak bizonyos pontok feldolgozásánál azokat elıször meg is kell találni, de jóval kevesebb adattal dolgozunk utána. Mi jelen dolgozatunkban a tulajdonságok kinyerésén alapuló megoldással dolgozunk, mivel az utóbbi idıben ezek kerültek elıtérbe számításigényük miatt. Elıször tehát megkeresünk bizonyos pontokat az egyes képeken, majd ezeket igyekszünk összeegyeztetni (matching) a képek között. Célunk, hogy valós idıben egy videó forrásból tudjunk mozaikot készíteni és ezen az aktuális képkocka helyét meghatározni további feldolgozás céljából. A képek összeillesztése tulajdonképpen azt jelenti, hogy az összeegyeztetett pontok alapján számolunk egy homográfiát és ezzel transzformáljuk az aktuális bejövı képet a többihez. Mindez egy videófolyamból történik, ami megszorítást jelent az idıben (legalább 2-5 kép/mp). 16

4.3 Megoldásunk: Az általunk vizsgálni kívánt bemenetek jórészt igen rossz minıségőek és arra sem tudunk becslést adni, hogy miként mozdulnak el egymáshoz képest. Ehhez budapesti térfigyelı kamerák képét is felhasználtuk, ahol semmilyen visszajelzés nincs arra vonatkozóan, hogy a kamera éppen mennyit mozdult el. Pusztán a vizuális bemenetbıl kell tehát kiszámolni azt, hogy merre mozog a kamera. A számunkra a továbbiakban fontos pontokat egy már régóta létezı megoldással keressük: a Harris detektorral [18]. Az így megtalált pontokat egyeztetjük össze a képeken (Pyramidal LucasKanade Optical Flow) és ezáltal keressük a homográfiát (H). Az így transzformált képet illesztjük be a mozaikba, ami frissíti azt. Sajnos a mozgó objektumok ill. a rossz minıség megnehezíti a folyamatot.

4.4 Harris sarok- és éldetekció: Az alapötlet abból jön, hogy keressünk egy képen valódi sarkokat (4.2.ábra). Ezek száma feltehetıleg elég kevés ahhoz hogy a további feldolgozást segítsék, és elég sok a homográfia számolásához. Az így megtalált pontokat egyeztetjük össze a képeken.

felület

él 4.2. ábra: A Harris sarokdetekció alapötlete [19]

sarok

Jelen esetben tehát azokat a pontokat kívánjuk megtalálni, amik egymásra merıleges irányokból is kellıen nagy „éleket” (sarkokat) mutatnak. Itt szintén ablakokban vizsgáljuk, hogy ez a feltételezés fent áll-e vagy sem. Az ablakokat úgy vizsgáljuk, hogy az eltolt intenzitáskép változását átlagoljuk az ablakokban. Az eltolás mértéke itt (u, v).

E (u , v ) = ∑ w( x, y ) * [ I ( x + u , y + v) − I ( x, y ) ]

2

(4.1)

x, y

Ahol az E(u,v) a fent említett „ablak-átlag”. A w(x,y) az az ablakfüggvény, amivel végigfutunk a képen (ez lehet négyszög- vagy gaussi ablak) és az I(x,y) pedig az intenzitásérték ill. annak (u,v) eltoltja. Ezt az E(u,v)-t közelíthetjük mint bilineáris függvényt a következı képpen:

E (u, v) ≅ [u v ] M [u v ]

T

(4.2)

Ahol M az intenzitásképek deriváltjából: 17

 I x2 M = w( x, y )*  I I  x y

IxI y   I y 2 

(4.3)

Ezen M mátrix sajátértékeinek (λ1, λ2) kell elég nagynak lenniük egy sarokban. Ahol ezek kellıen nagyok (egymáshoz képest persze), ott egy sarokpontnak kell lennie (4.3. ábra). Ezt jelenti, hogy a merıleges élek kellıen nagyok.

felület

él

sarok

4.3. ábra: Ha a M sajátértékei λ1, λ2 elég nagyok, akkor ott sarok van [19] Ez az eljárás tehát minden egyes ablakban egy értéket ad vissza, amit válasznak nevezünk (response = R).

R = det( M ) − k *(λ1 +λ2 ) 2

(4.4)

Ahol det(M)= λ1* λ2 és a k pedig egy konstans 0.04-0.06. Az így kinyert pontokkal dolgozunk tehát tovább és ezeknek a változását, hogy a másik képen hová került, fogjuk követni. A kritérium annyi, hogy a válasz (R) nagyobb legyen egy küszöbnél. Az így összepárosított pontokat perspektivikus transzformációval lehet összeilleszteni, amihez legalább 4 de inkább több pontot kell megfeleltetni egymásnak. Az alábbi példából látható, hogy kézzel kiválasztott pontok esetén, ami jelen esetben 6 volt, már egész szép illesztést kaphatunk. Természetesen a pontok helyét Harris sarokdetekcióval kaptuk meg és Matlab alatt illesztettük (4.4. ábra). A Harris detektor tulajdonságairól meg kell jegyeznünk pár dolgot. Az éldetektor forgatás invariáns, tehát a sarok bármely szögben is áll, akkor az sarokként megtalálható. Intenzitás változásra sem érzékeny, mivel a pixelintenzitás növekedésével/csökkenésével az összes pixel értéke változik, de mi egymáshoz viszonyítjuk ıket, tehát ez nem probléma. Gond egyedül csak a méretbıl fakad. Ez abból adódik, hogy ha egy görbületet távolról szemlélünk, akkor azt akár sarokként is detektálhatjuk, közelrıl nézve viszont nincs meg a megfelelı válasz (R) a sarok detekcióhoz. Mi ezzel jelen esetben nem foglalkozunk, de erre is született megoldás. Ehhez egy kernel függvénnyel kell transzformálni a képet (amitıl az eddigi tulajdonságok megmaradnak), Harris esetén ez Laplace függvény szokott lenni [20].

18

második frame

elsı frame

4.4. ábra: Két kép összeillesztése kézzel kiválasztott pontok homográfiája alapján A Harris sarokdetekció mellett mindenképpen érdemes megemlíteni a SIFT (Scale Invariant Feature Transform) eljárást [21]. Ez egy sokkal komplexebb megoldás, viszont remek leíróként szolgál mozaikolásos feladatokhoz. A tulajdonságpontok kinyerésének analízisérıl bıvebben több összehasonlító cikk is ír [22].

4.5 Pontok párosítása Lucas-Kanade eljárással A Harris-sarokdetekcióval megkeresett pontokat meg kell találnunk a mozaikhoz hozzáillesztendı képen is, mivel ez alapján tudunk homográfiát számolni. Egy lehetséges megoldás, hogy megkeressük a másik képen is a sarkokat és a többi jellegzetes pontot, majd valamilyen eljárással a két kép közötti pontokat egymáshoz társítjuk (4.5 ábra)

19

4.5 ábra: A megfelelı pontok összepárosítása (csak néhány, hogy látható legyen)

A homográfia annál pontosabb, minél több jó pontpárt találunk, viszont: 1. nem biztos, hogy minden, az elsı képen megtalált pont megjelenik a második képen és fordítva 2. minden pont egymáshoz társítása nem végezhetı real-time módon Mi a megoldásunkban egy gyorsabb és hatékonyabb eljárást használtunk, a piramidális Lucas-Kanade-féle optikai folyamot. Ez az eljárás [23] egy vektormezıt ad végeredményül, azaz megadja minden egyes kijelölt pont vízszintes és függıleges irányú elmozdulását. A probléma: adott két bemeneti kép I és J. Vegyünk egy pontot I képen: u = [ux, uy ]T. Célunk egy olyan d= [dx, dy ]T vektor meghatározása, melyre I(u) és J(u+d) képek „hasonlóak” egy adott ωx × ωy ablakban, azaz az

ε(d) = ε(d x ,d y ) =

u x +ωx

u y +ωy

∑ ∑

(I(x, y) − J(x + d x , y + d y )) 2

x = u x −ωx y = u y −ωy

(4.5)

maradéktag minimális. Az eljárásnak robosztusnak és pontosnak kell lennie. A pontosság teljesítéséhez kis mérető ablakot kellene használni (maradjanak meg a részletek), viszont a robosztusság (pl. a fényviszonyok változása, nagyobb léptékő mozgások) nagyobb mérető ablak használatát indokolná. A piramidális Lucas-Kanade-féle optikai folyam kis mérető ablakokkal, hatékonyan teljesíti a két feltételt.

Definíció: egy I bemeneti kép L. szintő Gaussi piramisa, rekurzívan 1 1 IL (x,y) = IL−1(2x,2y) + (IL−1(2x −1,2y) + IL−1(2x +1,2y) + IL−1(2x,2y −1) + IL−1(2x,2y +1)) + 4 8 (4.6) 1 L−1 L−1 L−1 L−1 (I (2x −1,2y −1) + I (2x +1,2y +1) + I (2x −1,2y +1) + I (2x +1,2y −1)) 16 ahol L a piramis szintje, I0 a bemeneti kép. Ilyenkor az Lm lépés w h után a piramis szélessége és magassága Lm illetve Lm , ahol 2 2 w és h a bemeneti kép szélessége és magassága

Az eljárás lényege nagyvonalakban, hogy az elmozdulást a piramis legfelsı szintjén (Lm) számítja, majd egy szinttel lejjebb (Lm-1) a környezı pontok megkapják az elızı szinten számított elmozdulás értékének kétszeresét, ez finomítjuk, majd ezen a szinten is kiszámítjuk a folyamot, amely lefelé propagál a következı szintre, egészen az L0ig, azaz az eredeti kép szintjére. Általánosságban az L+1. és L. szint között: L. szinten van egy kezdeti elmozdulás értékünk g L = g xL

T

g Ly  , amelyet a piramis legfelsı szintjétıl Lm – L+1-ig már kiszámoltunk. Ekkor az L.

20

T

szinten az elmozdulás, a d L = d Lx , d Ly  vektor, melyre a következı maradéktag a minimális:

ε (d ) = ε (d , d ) = L

L

L

L x

L y

u Lx +ωx

∑

u Ly +ωy

∑

(I L (x, y) − J L (x + g Lx + d Lx , y + g Ly + d Ly )) 2 (4.7)

x = u Lx −ωx y = u Ly −ωy

Ha ismerjük az L. szinten az elmozdulást, akkor az L-1. szinten a kezdeti elmozdulásnak a következı értéket adjuk: g L −1 = 2(g L − d L ) , és a fenti optimumkeresést addig folytatjuk iteratívan, amíg a piramis aljáig (L=0) nem érünk, ezáltal a két bemeneti kép közötti optikai folyamot kiszámítottuk, ekkor a végleges elmozdulás d=g0+d0.

4.5.1

A standard Lucas-Kanade-féle eljárás

A cél, hogy a piramis minden L szintjén meghatározzuk azt a dL vektort, mely minimalizálja (4.7)-t. Ehhez vezessük be a következı jelöléseket: ∀(x, y) ∈ [ p x − ωx − 1, p x + ωx + 1] ×  p y − ωy − 1, p y + ωy + 1

(4.8)

A(x, y) ≐ I L (x, y)

∀(x, y) ∈ [ p x − ωx , p x + ωx ] ×  p y − ωy , p y + ωy 

(4.9)

B(x, y) ≐ J L (x + g Lx , y + g Ly ) T

T

és definiáljuk p =  p x , p y  = u L ill. ν = ν x , ν y  = d L Ekkor az optimalizálási probléma a következı alakban írható fel: ε( ν ) = ε( ν x , ν y ) =

p x +ωx

p y +ωy

∑ ∑

(A(x, y) − B(x +ν x , y + ν y )) 2

(4.10)

x = p x −ωx y = p y −ωy

Optimális vektor esetében a hibatag ν szerinti deriváltja 0, így (4.10) deriválva p +ω

p x +ωx y y  ∂B ∂B  ∂ε(ν ) = −2 ∑ ∑ (A(x, y) − B(x +ν x , y + ν y ))   ∂ν x = p x −ωx y = p y −ωy  ∂x ∂y 

(4.11)

Ha B(x,y)-t Taylor-sorba fejtjük a [0 0]T pont körül (ez a piramidális jelleg miatt elég jó közelítés), akkor a fenti formula közelíthetı p y +ωy p x +ωx  ∂B ∂B   ∂B ∂B  ∂ε(ν ) ≈ −2 ∑ ∑ (A(x, y) − B(x, y) −   ν )  ∂x ∂y  (4.12) ∂ν ∂ x ∂ y x = p x −ωx y = p y −ωy     Az A(x,y)-B(x,y) kifejezés nem más, mint a kép idıbeli deriváltja az adott (x,y) pontban, δI(x, y) ≐ A(x, y) − B(x, y)

(4.13)

a

 I x   ∂B ∂B   ∂B ∂B   ∂x ∂y  vektor pedig I gradiense, így ∇I=  I  =  ∂x ∂y      y  ahol 21

T

(4.14)

∀(x, y) ∈ [ p x − ωx , p x + ωx ] ×  p y − ωy , p y + ωy  ∂A(x, y) A(x + 1, y) − A(x − 1, y) = 2 ∂x ∂A(x, y) A(x, y + 1) − A(x, y − 1) I y (x, y) = = ∂y 2 A gradienst Scharr-operátorral felírva (4.12) így alakul: p −ω 1 ∂ε(ν ) px +ωx y y ≈ ∑ ∑ (∇IT ν − δI)∇IT 2 ∂ν x = p x −ωx y = p y −ωy I x (x, y) =

T p y −ωy p x +ωx  I 2x 1  ∂ε(ν )  ( ≈ ∑ ∑ I I 2  ∂ν  x = p x −ωx y = p y −ωy  x y

Ix Iy  δI I x  ν - ) 2  I y  δI I y 

A (4.15)-ben szereplı szummát felbontva két részre a következı jelölésekkel p x +ωx p y +ωy  2 p x +ωx p y +ωy Ix Ix I y  δI I x  G≐ ∑ ∑  és b ≐ ∑ ∑   2  x=p x −ωx y=p y −ωy  x=p x −ωx y=p y −ωy  δI I y   I x I y I y 

(4.15)

(4.16)

(4.17)

T

1  ∂ε(ν )  ≈ Gν − b 2  ∂ν 

(4.18)

Ezt rendezve követtkezik, hogy az optimális elmozdulásvektor νopt = G −1b (4.19) feltéve ha a G mátrix invertálható, azaz az A mátrix vízszintes és függıleges irányban is hordoz gradiensinformációt a p pont környezetérıl A fenti levezetés az standard Lucas-Kanade optikai folyam számítására vonatkozik, amely csak akkor érvényes, ha a pixelszintő elmozdulás kicsi (a Taylor sorfejtés miatt). A pontos eredményhez a fenti eljárást iterálni kell. A cél ν megtalálása, amely minimalizálja (4.10)-et

4.5.1 Az iteráció Legyen k az aktuális iteráció száma, tételezzük fel, hogy 1,…k-1-ig rendelkezésünkre állnak a T

kiszámított elmozdulásvektorok ν k −1 = ν kx −1 ν ky −1  . Legyen Bk ebben az iterációban számított kép:

∀(x, y) ∈ [ p x − ωx , p x + ωx ] ×  p y − ωy , p y + ωy  Bk (x, y) ≐ B(x + ν kx −1 , y + ν ky −1 ) Ekkor a cél ηk = ηkx

ε (η ) = k

k

(4.20)

ηky  meghatározása, amely minimalizálja p x +ωx

p y +ωy

∑ ∑

(A(x, y) − Bk (x + ηkx , y + ηky ))2

x = p x −ωx x = p y −ωy

Ez megoldható az egylépéses Lucas-Kanade féle algoritmussal (4.19) alapján

ηk = G −1 b k , ahol

22

(4.21)

bk =

δI k (x, y)I x (x, y)    x = p x −ωx x = p y −ωy  δI k (x, y)I y (x, y)  p y +ωy

p x +ωx

∑ ∑

(4.22)

∀(x, y) ∈ [ p x − ωx , p x + ωx ] ×  p y − ωy , p y + ωy  δI k (x, y) = A(x, y) − Bk (x, y)

(4.23)

Mivel az x- és y irányú deriváltakat csak egyszer kell kiszámolni, így a 2x2-es G mátrix állandó és minden egyes lépésben csak a b vektort kell számítani (tulajdonképpen ν k -t)

ν k = ν k −1 + ηk

(4.24)

Az iterációt addig folytatjuk, amíg el nem érjük az elıírt lépésszámot vagy amíg ηk egy bizonyos küszöb alá nem csökken. Ha K a szükséges lépésszám, akkor az optikai folyam: K

ν = d L = ν K = ∑ ηi

(4.25)

i =1

Ekkor a fenti vektor minimalizálja (6)-t az L. szinten. Ez az érték továbbterjed az L-1. szintre, ahol elvégezzük a fenti iteratív eljárást, egészen az L=0 szintig.

4.6 Homográfia Miután megtaláltuk a két képen a megfelelı pontokat, a pontok koordinátáit átalakítjuk homogén koordinátákká, ezáltal biztosítjuk, hogy nem lineáris mőveleteket is elvégezhetünk a koordinátákkal x x     →  y  y 1   Ezután keressük azt a H homográfia mátrixot, melyre I és J két bemeneti kép esetén ∀(x, y) ∈ I és ∀(x ', y ') ∈ J, w ∈ ℝ  wx '   x   h0       wy '  ∼ H  y  =  h 3  w        1   h6

h1 h4 h7

h 2  x    h 5  y   1  1  

(4.26)

Azaz wx ' = h 0 x + h1 y + h 2 wy ' = h 3 x + h 4 y + h 5

(4.27)

w = h6x + h7 y +1 Ezt átírhatjuk a következı alakba h 0 x + h1 y + h 2 h6x + h7 y +1 h x + h 4 y + h5 y' = 3 h6x + h7 y + 1 x' =

23

(4.28) (4.29)

Átrendezve: x ' = h 0 x + h1 y + h 2 − x ' h 6 x − x ' h 7 y y ' = h 3x + h 4 y + h 5 − y ' h 6 x − y ' h 7 y

(4.30)

Mivel a H mátrixnak 8 szabad paramétere van, ezért minimum 4 pontpár szükséges számolásához, amely a következı egyenletrendszer megoldását jelenti:  x1'   x1 − x1x1' − y1x1'   h 0  y1 1 0 0 0  '    − x1 y1' − y1 y1'   h1  0 0 x1 y1 1  y1   0  x '2   x 2 − x 2 y'2 − y 2 y '2   h 2  y2 1 0 0 0  '     − x 2 y '2 − y 2 y '2   h 3  0 0 x2 y2 1  y2  =  0 (4.31) ' '   x'   x  h − − y 1 0 0 0 x x y x 4 3 3 3 3 3  3'   3   ' ' h − − y 0 0 0 x y 1 x y y  3  3 3 3 3 3 y3   5   x'   x  − x 4 x '4 − y 4 x '4   h 6  y4 1 0 0 0  4  4    y'   0 − x 4 y '4 − y 4 y '4   h 7  0 0 x4 y4 1  4  Természetesen minél több pontunk van, a homográfia annál pontosabb lehet, erre Szeliski és Shum [24] ad jó módszert.

4.7 A mozaikoló algoritmus vázlata ÚjKépHozzáadása( kép_be ): Kép1 ← Kép2 Kép2 ← kép_be ÉlekErısítése( Kép2 ) Pontok1 ← Harris_Sarokdetekció(Kép1) Pontok2 ← LucasKanadePyramis_OpticalFlow(Kép1, Kép2, Pontok1) H ← Homográfia(Pontok1, Pontok2) TransfKép ← PerspektívikusTranszform(Kép2, H) Eltolás ← EltolásFinomítása(H, Kép1, Kép2) Panorama ← PanorámábaIlleszt(TransfKép)

Mint az a vázlatból is kitőnik az algoritmus csak az új bejövı képkockát kapja meg és jelenleg még csak az elızı képhez igazítja és számol homográfiát. Ez természetesen nem tökéletes illesztést ad, de horizontális mozgatás esetén szép eredményeket ad (4.7 ábra). A képek panorámába illesztésének módja (image blending) többféle lehet. Mi három féle illesztést próbáltunk ki: szimpla átlagolás a mozaikkal, bilineáris súlyozás és Gaussi súlyozás (4.6 ábra). Természetesen futásidıben a legelsı bizonyult a legjobbnak, míg a súlyozott elmosások esetén nem annyira feltőnıek az esetleges törések az egyes képkockák illesztési határán (a 4.7-4.10 ábrákon függıleges vonalak).

24

(a) Bilineáris

(b) Gaussi

4.6 ábra: A beillesztésnél használható súlyfüggvények szemléletesen

4.8 Kimenetek

4.7 ábra: Egy panorámakép amit egy USB-s Sony videokamerával készítettünk

4.8 ábra: A Pázmány aulája egy nagyon gyenge minıségő webkamerával, átlagolásos illesztéssel

25

4.9 ábra: Egy belvárosi kamera képe több mozgó objektum ellenére is egész jó eredményt adott

4.10 ábra: Szintén Budapestrıl készült képsor.

5. Összegzés: Igyekeztünk a dolgozatban vázolt minden eljárásra egy natív verziót elkészíteni. Az egyes problémaköröket külön-külön modulban valósítottuk meg C++ alatt. Ehhez segítségül hívtuk az OpenCV függvénykönyvtárban megvalósított kép- és videófájl kezelı eljárásokat és a beépített feldolgozó függvényeket is [25]. A modulokat aztán igyekeztük fuzionálni (természetesen amik összetartoznak) oly módon, hogy a lehetı legkevesebb adatcserével érjük el, hogy mozgó kamerára mőködjenek. Az elsıdleges kérdés az aktuálisan bejövı kép helye a mozaikban. Ezt a fentebb leírt mozaikoló algoritmusból számoltuk, majd a pozíciót átadtuk az elıtér-háttér szegmentáló eljárásnak. A nagyobb áttekinthetıség és könnyebb kezelhetıség érdekében objektum-orientáltan terveztük meg a demonstrációs rendszert. Már egy gyenge minıségő kamera esetén is mőködik a kiemelés (5.1 ábra). A tárgyalt technikákkal elérhetı, hogy az egész kép vizsgálata helyett csak bizonyos pontok segítségével tudjunk akár nagy területet is megfigyelni és azon tartalomszőrést végezni és mindezt akár egy asztali gép segítségével is megtehetjük.

5.1 ábra: Mozgó kamerával történı elıtér-szegmentáció az egyetem aulájában. 26

Az elkészített program persze közel sem tökéletes még, aminek több oka is van. Az viszont elmondható, hogy horizontálisan mozgó kamera képét sikeresen összeilleszti és a Stauffer-féle szegmentációval sikerült kiemelnünk a mozgó alakzatokat. Az egyes demonstrációs programok (grafikus felülettel) és a teszt videók egy része elérhetıek a forrásoknál megjelölt honlapokon (5.2 ábra). Amit érdemes lesz még a késıbbiekben vizsgálni, mivel azt reméljük hogy így javul az eljárás minısége, az például a megtalált pontok intelligens menedzselése és valamint a beillesztésnél a mozaikból több információ kinyerése. A futásidı mozaikolás esetén 47-60ms volt a tesztkonfiguráción, amit lassít a statisztikai háttér szegmentáció. További sebesség növekedést elérhetünk, ha a szegmentálási számításoknál nem tömbben, hanem képfájlban tároljuk az egyes paramétereket, mivel az Intelnek léteznek erre vonatkozóan hardverspecifikus függvénykönyvtárai. Ezzel a jelen dolgozatban nem tudtunk foglalkozni. Az is további vizsgálódást igényel, hogy miként javíthatjuk a szegmentáció kimenetét például a már számolt optical-flow segítségével.

mozaikolás+szegmentáció

elıtér szegmentáció

periódus detekció

5.2 ábra: A megvalósított program felhasználói felületei.

5.1 Felhasznált külsı programrészek: Az implementálás folyamán természetesen nem valósítottunk meg minden tárgyalt eljárást, hanem amihez találtunk létezı függvényt, azt felhasználtuk. Ezek az OpenCV környezetben létezı megoldások: a Harris sarokdetekció, a Lucas-Kanade optikai folyam (maga a cikk is a függvénykönyvtárhoz jelent meg [23]), a Homográfia számolása valamint a primitív képfeldolgozó és algebrai eljárások. Ezek tehát nem a mi munkák eredménye a demonstrációs programban, mivel feltehetıleg sebesség és megbízhatóság szempontjából jóval kiforrottabbak, mintha mi készítettük volna és nem utolsó sorban ingyenesen hozzáférhetıek az interneten [25]. Az elıtér-háttér szegmentációhoz nem használtunk a GNU C++ könyvtárakon kívül mást, a periódus detekciójánál is csak alapfüggvényeket hívtunk segítségül és maga a mozaikolásos modult is mi készítettük.

27

6. Köszönetnyilvánítás: Szeretnénk köszönetet mondani az elmúlt hónapokban kapott segítségért és útmutatásokért Szirányi Tamás Professzor Úrnak, valamint az MTA Számítástechnikai és Automatizálási Kutató Intézetébıl Havasi Lászlónak. Ezen kívül köszönjük a lehetıséget, hogy az Országos Tudományos Kutatási Alapprogramok keretében a SZTAKI Elosztott Események Elemzése Kutatócsoportjánál nyári gyakorlatként bekapcsolódhattunk az ottani munkába és amiért a csoport tagjai elláttak minket szakirodalommal valamint valódi teszt videókkal.

28

7. Források: [1] A. McIvor, Background subtraction techniques, In Proc. of Image and Vision Computing, Auckland, New Zealand, 2000. [2] J. Heikkila and O. Silven: A real-time system for monitoring of cyclists and pedestrians In: Second IEEE Workshop on Visual Surveillance Fort Collins, Colorado (Jun.1999) pp. 74{81. [3] C. Stauffer and W. E. L. Grimson. Adaptive background mixture models for real-time tracking. In Computer Vision Pattern Recognition, pages 246--252, Ft. Collins, CO, 1999. [4] KaewTraKulPong P, Bowden R, An Improved Adaptive Background Mixture Model for Real-time Tracking with Shadow Detection, Computer Vision and Distributed Processing, Kluwer Academic Publishers. [5] P. Wayne Power Johann A. Schoonees, Understanding Background Mixture Models for Foreground Segmentation, Proceedings Image and Vision Computing New Zealand 2002 [6] Z.Zivkovic, Improved adaptive Gausian mixture model for background subtraction , International Conference Pattern Recognition, Vol.2, pages: 28-31 , 2004 [7] Kyungnam Kim, Thanarat H. Chalidabhongse, David Harwood, Larry S. Davis: Background modeling and subtraction by codebook construction, ICIP 2004: 3061-3064 [8] A Dempster, N. Laird, and D. Rubin. “Maximum likelihood from incomplete data via the EMalgorithm,” Journal of the Royal Statistical Society, 39 (Series B):1-38, 1977. [9] Arno Lepisk, The use of Optic Flow within Background Subtraction, Master’s Degree projekt Stockholm, Sweden 2005 [10] A. Mittal and N. Paragios, Motion-based background subtraction using adaptive kernel density estimation, Computer Vision and Pattern Recognition, June 2000. [11] Cutler, R. and Davis, L. “Robust Real-Time Periodic Motion Detection, Analysis, and Applications,” IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), Vol. 22 No. 8, pp. 781-796, August 2000 [12] C. BenAbdelkader, R. Cutler, L. Davis. Eigengait: Motion-based recognition of people using image selfsimilarity. AVBPA, 2001 [13] C. Kuglin and D. Hines. The Phase Correlation Image alignment method IEEE Int. Conf. on Cybernetics and Society, 1975 New York, pp 163-165 [14] Steven M. Seitz and Charles R. Dyer. View-invariant Analysis of Cyclic Motion, International Journal of Computer Vision, 25, 1-23, 1975 [15] R. Cutler and L. Davis. View-based Detection and Analysis of Periodic Motion, 14th Int. Conference on Pattern Recognition, August 16-20, 1998, Brisbane, Australia [16] R. Polana and R. Nelson, "Detection and recognition of periodic, non-rigid motion," International Journal of Computer Vision 23(3), pp. 261--282, 1997. [17] X.-T. Dai, L. Lu, and G. Hager. Real-time video mosaicing with adaptive parameterized warping. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2001. [18] C. Harris and M. Stephens , A combined corner and edge detector. Proceedings of the 4th Alvey Vision Conference, pages 147--151. (1988) [19] Darya Frolova, Denis Simakov (The Weizmann Institute of Science) March 2004 http://www.wisdom.weizmann.ac.il/~deniss/vision_spring04/files/InvariantFeatures.ppt [20] K.Mikolajczyk, C.Schmid. “Indexing Based on Scale Invariant Interest Points”. ICCV 2001 [21] D.Lowe. “Distinctive Image Features from Scale-Invariant Keypoints”. IJCV 2004

29

[22] K. Mikolajczyk, C. Schmid: A performance evaluation of local descriptors, num. 10. vol. 27. pages 1615—1630 (2005) [23] Jean-Yves Bouguet. Pyramidal Implementation of the Lucas Kanade Feature Tracker Description of the algorithm. OpenCV [24] Richard Szeliski and Heung-Yeung Shum. Creating Full View Panoramic Image Mosaics and Environment Maps. Computer graphics proceedings, annual conference series, pp. 251-258, 1997. [25] Intel Open Source Computer Vision Library: http://www.intel.com/technology/computing/opencv/index.htm

Demók/próbavideók: http://digitus.itk.ppke.hu/~karkr/dip/ http://digitus.itk.ppke.hu/~losda/camera.html http://i21www.ira.uka.de/image_sequences/ http://peipa.essex.ac.uk/ipa/pix/pets/PETS2001/

Tesztkonfiguráció: Intel P4 Prescott E 2.8GHz 1MB cache 2×256MB RAM 400DDR DualChannel Samsung SP1213C SATA 120GB ATI Radeon 9250 (128MB DDR) Windows XP SP2 OpenCV 1.0

30