sztochasztikus módszerekkel

Képaf 2011, Szeged, Magyarország

´ uletek ¨ Ep e´ s v´altoz´asaik detekci´oja sztochasztikus m´odszerekkel⋆ Benedek Csaba12 , Xavier Descombes2 , Josiane Zerubia2 1

2

Elosztott Esem´enyek Elemz´ese Kutat´ocsoport, MTA SZTAKI, 1111 Budapest, Kende utca 13-17 [email protected] Ariana Project Team (INRIA/CNRS/UNSA), 2004 route des Lucioles, BP 93, 06902 SOPHIA ANTIPOLIS Cedex - FRANCE [email protected]

Absztrakt. Cikk¨unkben l´egi- e´ s m˝uholdk´epek feldolgoz´as´at v´egz˝o val´osz´ın˝us´egi m´odszert mutatunk be. A modell egy¨uttesen c´elozza meg e´ p¨uletek kinyer´es´et e´ s v´altoz´asaik detekt´al´as´at t¨obbidej˝u, jelent˝os id˝ok¨ul¨onbs´eggel k´esz¨ult k´epi bemeneteteket felt´etelezve. Glob´alis optimaliz´aci´os folyamat tal´alja meg az e´ p¨uletek megfelel˝o konfigur´aci´oj´at, figyelembe v´eve a megfigyelt k´epi adatot, prior inform´aci´ot e´ s a szomsz´edos e´ p¨uletszegmensek k¨oz¨otti interakci´ot. A m´odszer pontoss´ag´at Bayesi verifik´aci´os folyamat biztos´ıtja, m´ıg a sz´am´ıt´asi id˝o jelent˝osen ler¨ovid¨ul egy u´ j sztochasztikus objektum sz¨ulet´esi folyamat seg´ıts´eg´evel, mely alacsony k´epi jellemz˝ok alapj´an nagy val´osz´ın˝us´eggel javasol relev´ans objektumokat.

1. Bevezet´es Be´ep´ıtett ter¨uletek v´altoz´asainak monitoroz´asa k¨ozponti feladat nagy felbont´as´u l´egi- e´ s m˝uholdk´epek vizsg´alatakor. Sz´amos m´odszer v´egez e´ p¨uletdetekci´ot k¨ul¨on´all´o k´epeken [5, 7, 9]. Ez a folyamat jelent˝osen megk¨onny´ıthet˝o DEM/DSM adat-bemenetek felhaszn´al´as´aval [3, 7], melyek sztereo k´epp´arokb´ol vagy speci´alis szenzoradatokb´ol nyerhet˝ok ki: ekkor a h´azak elk¨ul¨on´ıthet˝ok a f¨oldfelsz´ınt˝ol a becs¨ult magass´agi adatok alapj´an. T¨obb n´ezeti inform´aci´o hi´any´aban azonban az e´ p¨uletek azonos´ıt´asa komoly kih´ıv´ass´a v´alik [8]. Az e´ p¨uletv´altoz´asok e´ szlel´es´et v´egz˝o sz´amos kor´abbi m´odszer [3] felt´etelezi, hogy a kor´abbi id˝opontr´ol topografikus e´ p¨ulet adatb´azis a´ ll rendelkez´esre, ´ıgy a folyamat sz´etv´alaszthat´o k´et r´eszre: a kor´abbi e´ p¨uletek ellen˝orz´es´ere e´ s az u´ j e´ p¨uletek felder´ıt´es´ere. Ugyanakkor sok k´epi adatb´azis nem tartalmaz kieg´esz´ıt˝o adatokat, ez´ert sz¨uks´egess´e v´alik mindk´et id˝or´etegen az automatikus e´ p¨uletkinyer´es. A t´av´erz´ekel´esben kor´abban sz´amos alacsonyszint˝u v´altoz´asdetekci´os m´odszert ismertettek [2], melyek statisztikailag kiugr´o k¨ul¨onbs´egeket keresnek a k´epeken konkr´et ⋆

A cikk eredm´enyei az al´abbi publik´aci´oban jelentek meg: C. Benedek, X. Descombes, and J. Zerubia. Building extraction and change detection in multitemporal remotely sensed images with multiple birth and death dynamics. In IEEE Workshop on Applications of Computer Vision (WACV), pages 100–105, 2009.

Képaf 2011, Szeged, Magyarország

´ uletek e´ s v´altoz´asaik detekci´oja Ep¨

15

objektum modellek haszn´alata n´elk¨ul. B´ar ezeket a m´odszereket a´ ltal´aban csak el˝ofeldolgoz´o l´ep´eseknek tekintik a szakirodalomban, viszonylag kev´es olyan kutat´asi eredm´enyt tettek k¨ozz´e, amely felhaszn´alhat´os´agukat bizony´ıtan´a objektum szint˝u vizsg´alatokban. Ezt a hi´anyoss´agot p´otolva, m´odszer¨unk kombin´alja az objektumfelismer´est lok´alis alacsonyszint˝u hasonl´os´ag vizsg´alattal, melyek egy egyes´ıtett val´osz´ın˝us´egi modellben m˝uk¨odnek. Bemutatjuk, hogy k¨ul¨onb¨oz˝o alapvet˝o t´enyez˝ok egy¨uttesen haszn´alhat´ok ki, u´ gy mint e´ p¨uletv´altoz´asok a text´ura szinten is megv´altozott ter¨uleteken tal´alhat´ok, m´ıg a v´altozatlan objektumokr´ol rendelkez´es¨unkre a´ ll´o t¨obb n´ezet˝u inform´aci´o pontos´ıtja a felismer´est. A m´odszerek m´asik fontos csoportos´ıt´asi szempontja az objektumok modellez´es´en alapul. A direkt m´odszerek [5] az e´ p¨uleteket primit´ıv elemekb˝ol e´ p´ıtik fel; a leggyakrabban haszn´alt primit´ıvek a tet˝o blokkok, e´ l r´eszletek vagy sarokpontok. B´ar ezek az elj´ar´asok a´ ltal´aban gyorsak, hib´aznak, ha a k´epeken a primit´ıveket nem siker¨ul megb´ızhat´oan kinyerni. Egy m´asik jelent˝os m´odszertani csoportba tartoznak az inverz modellek [4], melyek fitnesz e´ rt´eket rendelnek a k¨ul¨onb¨oz˝o lehets´eges objektumkonfigur´aci´okhoz, e´ s egy optimaliz´aci´os folyamattal keresik a legval´osz´ın˝ubb popul´aci´ot. ´ıgy rugalmas objektummodellek e´ p´ıthet˝ok, e´ s k¨onnyen vehet¨unk figyelembe prior alaki inform´aci´okat e´ s objektum interakci´okat. Ugyanakkor, nagy sz´am´ıt´asi ig´eny sz¨uks´eges a magas dimenzi´oj´u popul´aci´ot´erben t¨ort´en˝o keres´eshez, mialatt a fitnesz f¨uggv´eny lok´alis maximumai f´elrevezethetik az optimaliz´aci´ot. M´odszer¨unkben egyar´ant kihaszn´aljuk az alacsony e´ s az objektumszint˝u megk¨ozel´ıt´esek el˝onyeit. Az felhaszn´alt t¨obbsz¨or¨os sz¨ulet´es e´ s hal´al (Multiple Birth and Death, MBD) optimaliz´aci´o [4] az e´ p¨uletek popul´aci´oj´at objektumgener´al´as (sz¨ulet´es) e´ s eldob´as (hal´al) l´ep´esek iter´aci´oival fejleszti l´ep´esr˝ol l´ep´esre, szimul´alt leh˝ut´es keretrendszerbe a´ gyazva. A felder´ıt´es f´azist alacsony szint˝u k´epi le´ır´ok vez´erlik, m´ıg az objektum verifik´aci´o a robosztus inverz megk¨ozel´ıt´est k¨oveti.

2. Probl´ema defin´ıci´o A bemutat´asra ker¨ul˝o m´odszer bemenete k´et egym´ashoz regisztr´alt l´egi- vagy m˝uholdk´ep, melyeket ugyanarr´ol a f¨oldrajzi ter¨uletr˝ol k´esz´ıtettek t¨obb h´onapos vagy e´ ves id˝ok¨ul¨onbs´eggel. B´ar figyelembe vessz¨uk, hogy az elt´er˝o n´ezetekb˝ol ad´od´oan k´epregisztr´aci´os hib´ak lehetnek jelen, felt´etelezz¨uk, hogy ezek csak n´eh´any pixelnyi torz´ıt´ast okoznak. Az e´ p¨uleteket fel¨uln´ezetb˝ol t´eglalap alak´u szegmensek egy¨uttes´enek tekintj¨uk, ´ıgy a k¨ovetkez˝okben csak ezekre a szegmensekre koncentr´alunk. Jel¨olj¨uk S-sel a k´epek k¨oz¨os pixelr´acs´at, e´ s s ∈ S-sel egy adott pixelt. Legyen u egy t´eglalap alak´u e´ p¨ulet szegmens jel¨olt. Az´ert hogy egy¨utt kezelhess¨unk k´et id˝or´eteget, u-hoz egy k´epindex attrib´utumot is rendel¨unk ξ(u) ∈ {1, 2, ∗}, ahol ‘∗’ v´altozatlan e´ p¨uletet jel¨ol, m´ıg ‘1’ illetve ‘2’ olyan szegmensekhez tartozik, melyek csak az els˝o illetve m´asodik k´epen szerepelnek. Legyen Ru ⊂ S az u-hoz tartoz´o a pixelek halmaza. Ru -t o¨ t t´eglalap-param´eter ´ırja le: cx e´ s cy k¨oz´epponti koordin´at´ak, eL , el oldal hosszak e´ s θ ∈ [−90◦, +90◦ ] orient´aci´os sz¨og (1. a´ bra).

Képaf 2011, Szeged, Magyarország

16

Benedek Csaba, Xavier Descombes, Josiane Zerubia

3. Jellemz˝ov´alaszt´as M´odszer¨unkben alacsonyszint˝u e´ s objektumszint˝u jellemz˝oket haszn´alunk egy¨uttesen. Az alacsony szint˝u jellemz˝oket a pixelek k¨ornyezet´eb˝ol nyerj¨uk ki, ilyenek lehetnek tipikus sz´ınek, text´ur´ak e´ s lok´alis hasonl´os´ag a r´etegek k¨oz¨ott. E jellemz˝oket a felder´ıt´es folyamat haszn´alja fel annak becsl´es´ere, hogy az e´ p¨uletek hol helyezkednek el nagy val´osz´ın˝us´eggel, illetve milyen lehet a geometriai megjelen´es¨uk: a sz¨ulet´es l´ep´es az objektumokat a becs¨ult be´ep´ıtett ter¨uleteken nagyobb val´osz´ın˝us´eggel gener´alja. M´asfel˝ol, az objektum szint˝u jellemz˝ok egy adott u e´ p¨uletjel¨oltet ´ırnak le, e´ s felhaszn´alhat´ok a gener´alt t´eglalapok fitnesz e´ rt´ek´enek meghat´aroz´as´ahoz. Mivel az e´ p¨uletek verifik´aci´oja ez ut´obbi jellemz˝ok¨on alapul, a pontoss´aguk kritikus. Mivel a hasonl´os´ag le´ır´on k´ıv¨ul a k¨ovetkez˝o jellemz˝ok sz´am´ıt´asa a k´et k´epen f¨uggetlen¨ul t¨ort´enik, gyakran nem hangs´ulyozzuk ki az aktu´alis k´epindexet ebben a fejezetben.

1. a´ bra: A t´eglalap geometriai param´eterei

3.1. Alacsony szintu˝ jellemz˝ok a be´ep´ıt´esek felismer´es´ehez Az els˝o jellemz˝o azt a t´enyt haszn´alja ki, hogy az e´ p¨uleteket tartalmaz´o k´epr´eszletek hangs´ulyos e´ s egym´asra mer˝oleges e´ leket tartalmaznak. Ezt a tulajdons´agot robosztusan jellemezhetj¨uk lok´alis gradiens orient´aci´os hisztogramokkal [6]. Jel¨olje ∇gs az s pixelhez tartoz´o intenzit´as gradiens vektort, ||∇gs || abszol´ut e´ rt´ekkel e´ s ϑs sz¨oggel. Legyen Wl (s) a n´egyzet alak´u l × l m´eret˝u ablak s k¨or¨ul, ahol l-t u´ gy v´alasztjuk, hogy Wl (s) sz˝uken lefedjen egy a´ tlagos e´ p¨uletet. Minden s pixel Wl (s) k¨ornyezet´eben kisz´am´ıtjuk a s´ulyozott ϑs s˝ur˝us´eget:   1 X 1 ϑ − ϑr λs (ϑ) = · ||∇gr || · k Ns h h r∈Wl (s)

P

ahol Ns = r∈Wl (s) ||∇gr || e´ s h a kernel s´avsz´eless´ege. A gyors sz´am´ıt´ashoz uniform kerneleket haszn´altunk. Ha Wl (s) lefed egy e´ p¨uletet, a λs (ϑ) f¨uggv´eny k´et jellemz˝o cs´uccsal rendelkezik, melyek 90◦ t´avols´agban tal´alhat´ok a ϑ-t´erben (2. a´ bra). Ezt a tulajdons´agot m´erhetj¨uk a λs (ϑ) f¨uggv´eny e´ s egy megfelel˝oen illesztett k´etm´odus´u Gaussi kever´ek f¨uggv´eny korrel´aci´oj´aval: Z α(s, m) = λs (ϑ)η2 (ϑ, m, dλ ) dϑ

Képaf 2011, Szeged, Magyarország

´ uletek e´ s v´altoz´asaik detekci´oja Ep¨

17

Wl(r) r

Wll(s) s

λs(ϑ)

λr(ϑ)

90

90

Gradient orient. KDEs λ (ϑ), λ (ϑ) s

r

Bimodal MGM estimate

−90

−60

−30

0

30 60 ϑ (degree)

90−90

−60

−30

0

30 60 ϑ (degree)

90

2. a´ bra: K´et v´alasztott pixel k¨ornyezet´ehez tartoz´o lok´alis gradiens orient´aci´os hisztogramok: s e´ p¨ulet k¨oz´eppont, r u¨ res ter¨ulet r´esze.

ahol η2 (.) k´et Gauss f¨uggv´eny kever´eke m illetve m+90◦ v´arhat´o e´ rt´ekkel e´ s azonos dλ sz´or´assal (dλ a folyamat param´etere). A maxim´alis korrel´aci´ohoz tartoz´o eltol´as (ms ) korrel´aci´os e´ rt´ek (αs ) ´ıgy megkaphat´o a k¨ovetkez˝ok´eppen:  ms = argmaxm∈[−90◦ ,0] α(s, m) αs = α(s, ms )

Nagy αs e´ rt´ekkel rendelkez˝o pixelek nagyobb val´osz´ın˝us´eggel lehetnek e´ p¨ulet k¨oP z´eppontok, amit az α-sz¨ulet´es-t´erk´epen k´odolhatunk: Pbα (s) = αs / r∈S αr . Az elnevez´es onnan ered, hogy az s pixelben a lok´alis Pb (s) sz¨ulet´esi e´ rt´ekkel ar´anyos frekvenci´aval fogunk gener´alni objektumokat az elj´ar´as sor´an. M´asr´eszr˝ol az ms eltol´as e´ rt´eke becsl´est ad a domin´ans gradiens ir´anyra Wl (s)ben. Ez´ert ha s k¨oz´epponttal gener´alunk egy u objektumot, az orient´aci´oj´at θ(u) = ms + ηs -k´ent modellezz¨uk, ahol ηs z´er´o v´arhat´o e´ rt´ek˝u Gaussi val´osz´ın˝us´egi v´altoz´o kis σθ sz´or´as param´eterrel. K´ıs´erleteinkben megfigyelt¨uk, hogy az αs -gradiens jellemz˝o a´ ltal´aban k´epes a bee´ p´ıtett ter¨uletek durva becsl´es´ere. Ugyanakkor, sz´amos esetben a detekci´o finom´ıthat´o tov´abbi jellemz˝ok figyelembev´etel´evel, p´eld´aul tet˝osz´ın e´ s a´ rny´ekok modellez´es´evel [9]. A tet˝osz´ınek egy r´esze j´ol elk¨ul¨on´ıthet˝o megvil´ag´ıt´as invari´ans sz´ınreprezent´acio´ kban, mint a HSV sz´ınt´er ‘hue’ csatorn´aja. Tegy¨uk fel, hogy ki tudunk nyerni egy µc (s) ∈ {0, 1} indik´ator maszkot, ahol µc (s) = 1 tartozik P a tet˝osz´ın˝u s pixelhez. Ekkor s sz´ınle´ır´oj´at a k¨ovetkez˝ok´eppen sz´amoljuk: Γs = µ (r) e´ s a sz´ın alap´u Pr∈Wl (s) c sz¨ulet´es t´erk´epet szint´en meghat´arozzuk: Pbc (s) = Γs / r∈S Γr . Jegyezz¨uk meg, hogy ez a jellemz˝o nyilv´anval´oan nem haszn´alhat´o sz¨urke´arnyalat´u k´epekre, illetve sz´ınes felv´etelek eset´en is a´ ltal´aban csak a tet˝ok egy r´esz´et azonos´ıtja, melyek p´eld´aul tipikus ‘piros’ sz´ın˝uek ([9] e´ s 5(b) a´ bra). Az e´ p¨uletek jelenl´et´ere vetett a´ rny´ekaikon kereszt¨ul is tehet¨unk becsl´est [5, 9]. Kihaszn´alva, hogy az a´ rny´ekok s¨ot´ets´ege e´ s ir´anya glob´alis k´epi jellemz˝ok, gyakran kinyerhet¨unk egy (zajos) µsh (s) a´ rny´ek maszkot, p´eld´aul a s¨ot´et-k´ek sz´ıntartom´anyba es˝o pixelek kisz˝ur´es´evel [9]. Ezut´an az e´ p¨uleteket tartalmaz´o ter¨uletek azonos´ıthat´ok azon

Képaf 2011, Szeged, Magyarország

18

Benedek Csaba, Xavier Descombes, Josiane Zerubia

k´epr´eszletekk´ent, amelyek az a´ rny´ek foltok mellett nap ir´anyban fekszenek (6. a´ bra). Konstans Pbsh (s) = psh ulet´esi e´ rt´eket haszn´altunk a kinyert be´ep´ıtett ter¨uleteken 0 sz¨ bel¨ul, m´ıg l´enyegesen kisebb ǫsh ul. 0 konstanst k´ıv¨ Mivel a kombin´alt sz¨ulet´est´erk´ep c´elja az, hogy valamennyi lehets´eges be´ep´ıtett ter¨uletre r´air´any´ıtsa a figyelmet, a jellemz˝o t´erk´e pekb˝ol a maximum oper´atorral sz´ar maztatjuk: Pb (s) = max Pbα (s), Pbc (s), Pbsh (s) ∀s ∈ S. Olyan k´epi bemenetekre, melyek nem tartalmaznak sz´ın- vagy a´ rny´ekinform´aci´ot, egyszer˝uen el kell hagyni a megfelel˝o komponenst. Ism´et megjegyezz¨uk, hogy a sz¨ulet´esi e´ s orient´aci´os t´erk´epeket mindk´et k´epre k¨ul¨on gener´aljuk, sz¨uks´eg eset´en az id˝of¨ugg´est az al´abbi m´odon jel¨olj¨uk: (i) (i) Pb (s), ms , i ∈ {1, 2}.

Wl(r) Wsl(s)

Wl(r)

r

Wl(s)

s

−90

−60

r

s

−30

0

ϑ

30

60

λ1s(ϑ)

λ1r(ϑ)

λ2s(ϑ)

λ2r(ϑ)

90

−90

−60

−30

0

ϑ

30

60

90

3. a´ bra: A λ(.) f¨uggv´enyek o¨ sszehasonl´ıt´asa a k´et k¨ul¨onb¨oz˝o idej˝u k´epen k´et v´alasztott pixel k¨ornyezet´eben. Az s pixel v´altozatlan r´egi´o eleme, m´ıg r pixel k¨or¨ul egy u´ j megjelen˝o e´ p¨ulet figyelhet˝o meg.

3.2. Alacsony szintu˝ hasonl´os´agvizsg´alat A gradiens orient´aci´os statisztika hat´ekony eszk¨ozt biztos´ıt r´egi´ok alacsony szint˝u o¨ sszevet´es´ere is. A λ1s (.) e´ s λ2s (.) f¨uggv´enyek illeszt´ese felfoghat´o az s k¨or¨uli ter¨uletek o¨ sszehasonl´ıt´asak´ent, e´ p¨uletspecifikus text´ura jellemz˝ok alapj´an (3. a´ bra). Mi t¨obb, ezek a le´ır´ok f¨uggetlenek a megvil´ag´ıt´ast´ol e´ s feh´eregyens´ulyt´ol, valamint robosztusak a parallaxis e´ s regisztr´aci´os hib´akra. A text´ur´alis k¨ul¨onbs´egeket az eloszl´asok Bhattacharyya t´avols´ag´aval m´erj¨uk: Z p b(s) = − log λ1s (ϑ) · λ2s (ϑ)dϑ A bin´aris hasonl´os´agt´erk´ep B a k¨ovetkez˝o m´odon sz´am´ıthat´o: B(s) = 1 akkor e´ s csak akkor ha b(s) < b0 , egy´ebk´ent B(s) = 0.

Képaf 2011, Szeged, Magyarország

´ uletek e´ s v´altoz´asaik detekci´oja Ep¨

(a) Objektum jel¨olt

(b) Gradiens t´erk´ep

19

(c) Maszkolt grad. t´erk´ep

4. a´ bra: A gradiens jellemz˝o bemutat´asa

(a) Piros tet˝o

(b) Sz´ın maszk

5. a´ bra: A tet˝osz´ın jellemz˝o bemutat´asa

3.3. Objektum szintu˝ jellemz˝ok Ebben a fejezetben k¨ul¨onb¨oz˝o objektum szint˝u jellemz˝oket mutatunk be. Felhaszn´alva ezeket, ϕ(i) (u) energia tagokat defini´alunk, melyek ki´ert´ekelik az u e´ p¨ulet-hipot´ezist az i-edik k´epen (k´es˝obb ism´et elhagyjuk az i indexet). ϕ(u) negat´ıv fitnesz e´ rt´ekk´ent e´ rtelmezhet˝o, m´ıg egy t´eglalapot ϕ(u) < 0 e´ rt´ekkel attrakt´ıv objektumnak h´ıvunk. Mivel a popul´aci´o b˝ov´ıt´ese attrakt´ıv objektumokkal cs¨okkentheti a glob´alis konfigur´aci´os energi´at [4], ezek az alakzatok hat´ekony e´ p¨ulet-jel¨oltek. A vizsg´alatokat a gradienst´erk´ep anal´ızis´evel kezdj¨uk ism´et. Egy relev´ans t´eglalapjel¨olt Ru hat´arai alatt elv´arhatjuk, hogy a k´epen a gradiens e´ rt´ekek magasak legyenek, e´ s a gradiens ir´any legyen mer˝oleges az Ru legk¨ozelebbi oldal´ara (4. a´ bra). A Λu jellemz˝ot a k¨ovetkez˝ok´eppen sz´am´ıtjuk: Λu =

X
1 · ||∇gs || · cos ϑs − Θus qu ˜ u s∈∂R

˜ u az Ru dilat´alt e´ l maszkja, Θs ∈ {θ(u), θ(u) + 90◦ } az Ru e´ l orient´aci´oja ahol ∂R u ˜ ˜ u pixeleinek sz´ama. Az adat-energia tagot az al´abbi m´odon s ∈ ∂Ru k¨or¨ul, e´ s qu a ∂R sz´am´ıtjuk: ϕΛ (u) = Q(Λu , dΛ , DΛ ) ahol a k¨ovetkez˝o nemline´aris Q a´ tviteli f¨uggv´enyt haszn´aljuk [4]:  ( 1 − dx0 ha x < d0 Q(x, d0 , D) =
x−d0 exp − D − 1 ha x ≥ d0

Képaf 2011, Szeged, Magyarország

20

Benedek Csaba, Xavier Descombes, Josiane Zerubia

A tet˝osz´ın jellemz˝o sz´am´ıt´as´at az 5. a´ bra szeml´ P elteti. Defini´aljuk a Tu objektum 1 1 k¨ornyezetet e´ s kisz´am´ıtjuk a CR (u) = #R · o e´ s Co (u) = #T · s∈Ru µc (s) bels˝ u u   P 1−µ (s) k¨ u ls˝ o kit¨ o lt´ e si t´ e nyez˝ o ket (# pixelekben m´ e rt ter¨ u letet jel¨ o l). V´ e g¨ u l c s∈Tu   C C C C sz´armaztatjuk az energiatagot: ϕC (u) = max Q(CR (u), dR , DR ), Q(Co (u), do , Do )

6. a´ bra: Az a´ rny´ek jellemz˝o bemutat´asa

Az a´ rny´ek t´enyez˝ot a sz´ın´evel anal´og m´odon defini´aljuk, de a vizsg´alt objektum k¨ornyezetet, Tush -t az a´ rny´ek ir´anyban helyezz¨uk elP (6. a´ bra).  Ezut´an a bels˝o illetve 1 k¨uls˝o kit¨olt´esi t´enyez˝oket sz´am´ıtjuk χR (u) = #R ´ s χo (u) = s∈Ru 1 − µsh (s) e u P 1 µ (s), m´ ı g a ϕ (u) energiatag meghat´ a roz´ a sa azonos m´ o don t¨ort´enik, χ s∈Tush sh #Tush mint a ϕC (u) eset´en. Megjegyezz¨uk, hogy k´ıs´erleteinkben a ϕχ (u) tag akkor is robosztusnak bizonyult, amikor az a´ rny´ekos ter¨uletek m´erete er˝osen k¨ul¨onb¨oz˝o volt az e´ p¨uletek magass´againak v´altozatoss´ag´ab´ol ad´od´oan.

Td Tr 0

object candidate

estimated symmetry

0.2

0.4

0.6

0.8

1

dark side histogram bright side histogram

7. a´ bra: A tet˝o homogenit´as jellemz˝o bemutat´asa

Sz¨urke´arnyalatos m˝uhold k´epeken a tet˝o homogenit´asa szint´en hasznos jellemz˝ot ad. A 7. a´ bra bemutat egy p´eld´at k´et komponens˝u homog´en tet˝ok le´ır´as´ara. Miut´an kinyert¨uk az u objektum jel¨olt f˝o szimmetria tengely´et, a vil´agos e´ s s¨ot´et tet˝or´eszlet hisztogramjainak cs´ucsoss´ag´at a κd (u) illetve κb (u) kurt´ozisukkal jellemezz¨uk. Vegy¨uk e´ szre azonban (8. a´ bra), hogy a kurt´ozis maximuma alapj´an gyakran t¨ored´ek-tet˝okh¨oz juthatunk (homog´en tet˝o r´esze is homog´en), ez´ert a tet˝o teljess´eg´et is m´erni kell egyidej˝uleg. Ez´ert l´etrehozzuk u el´araszt´as-maszkj´at (floodfill mask), Fu -t, ami az Ru

Képaf 2011, Szeged, Magyarország

´ uletek e´ s v´altoz´asaik detekci´oja Ep¨

21

8. a´ bra: El´araszt´as alap´u tet˝o teljess´eg jellemz˝o

belsej´eb˝ol a bemeneti k´epen el´araszt´as m˝uvelettel el´erhet˝o pixeleket tartalmazza. Ha a homog´en tet˝o jel¨olt teljes, Fu alacsony a´ tlapol´od´asi e´ rt´ekkel rendelkezik az Ru horizont´alis (NH u ) valamint vertik´alis (NV u ) szomsz´edoss´agi ter¨uleteivel (8. a´ bra). V´eg¨ul, a ϕκ (u) energiatagot a kurt´ozis e´ s teljess´eg jellemz˝okb˝ol az el˝oz˝okben ismertetett m´odon hozzuk l´etre. A keretrendszer lehet˝ov´e teszi a jellemz˝ok rugalmas integr´aci´oj´at a bemeneti k´epek tulajdons´agait´ol f¨ugg˝oen. Minden e´ p¨ulet protot´ıpushoz el˝o´ırhatunk egy vagy t¨obb jellemz˝o k´enyszert, melyek ϕ energiatagjait a max oper´atorral csatoljuk o¨ ssze a protot´ıpus o¨ sszes´ıtett energiatagj´aban (logikai e´ S m˝uvelet a negat´ıv fitnesz e´ rt´ekek ter´eben). Egy adott k´epp´aron t¨obb protot´ıpust detekt´alhatunk p´arhuzamosan, ha a k¨ul¨onb¨oz˝o protot´ıpusok energiatagjait a min (logikai vagy) oper´atorral csatoljuk. P´eld´aul, a Budapest k´epp´aron (11. a´ bra) k´et protot´ıpus haszn´alunk: az els˝o el˝o´ırja az e´ lekre e´ s az a´ rny´ekokra vonatkoz´o k´enyszert, m´ıg a m´asik kiz´ar´olag a tet˝o sz´ınre vonatkoz´ot. ´ıgy a teljes energiatag az al´abbi m´odon sz´am´ıthat´o:  ϕ(u) = min max {ϕΛ (u), ϕχ (u)}, ϕc (u) .

4. Jel¨olt pontfolyamat modell Jel¨olj¨uk H-val az u objektumok ter´et. Defini´aljunk egy H ∈ H Borel halmazt, e´ s az Ω konfigur´aci´os teret az al´abbi m´odon hat´arozzuk meg [4]: Ω=

∞ [

Ωn ,

n=0

 Ωn = {u1 , . . . , un } ∈ H n

Jel¨olj¨on ω egy tetsz˝oleges objektum konfigur´aci´ot {u1 , . . . , un } ∈ Ω. Defini´aljuk ezenfel¨ul a ∼ szomsz´edoss´agi rel´aci´ot H-ban: u ∼ v ha a t´eglalapjaik, Ru e´ s Rv metszik egym´ast. Bevezet¨unk egy nem stacion´arius adatf¨ugg˝o Gibbs eloszl´ast a konfigur´aci´os t´eren: PD (ω) = 1/Z · exp [−ΦD (ω)], ahol Z normaliz´al´o konstans, e´ s ΦD (ω) =

X

u∈ω

AD (u) + γ ·

X

u,v∈ω u∼v

I(u, v)

(1)

Képaf 2011, Szeged, Magyarország

22

Benedek Csaba, Xavier Descombes, Josiane Zerubia

AD (u) e´ s I (u, v) az adatf¨ugg˝o szingleton, illetve a prior interakci´os potenci´alok e´ s γ s´ulyoz´o t´enyez˝o a k´et energiatag k¨oz¨ott. A legval´osz´ın˝ubb, Maximum Likelihood (ML) konfigur´aci´o PD (ω) alapj´an becs¨ulhet˝o:   ωML = arg min ΦD (ω) ω∈Ω

A szingleton potenci´alok egy adott u = {cx , cy , eL , el , θ, ξ} e´ p¨ulet szegmens jel¨oltet jellemeznek a k¨ornyezetbeli k´epi adat f¨uggv´eny´eben, azonban f¨uggetlen¨ul a popul´aci´o t¨obbi objektum´at´ol: AD (u) = I[ξ(u)∈{1,∗}] · ϕ(1) (u) + I[ξ(u)∈{2,∗}] · ϕ(2) (u)+ ( ) X X
γξ + I[ξ(u)=∗] 1 − B(s) + I[ξ(u)∈{1,2}] B(s) #Ru s∈Ru

s∈Ru

ahol I[E] ∈ {0, 1} az E esem´eny indik´ator f¨uggv´enye, e´ s ahogy kor´abban defini´altuk, ϕ(1) (u) e´ s ϕ(2) (u) e´ p¨ulet illeszked´esi energi´ak az els˝o, illetve m´asodik k´epen (3.3. fejezet). B(.) az alacsony szint˝u hasonl´os´agi maszk a k´et id˝or´eteg k¨oz¨ott (3.2. fejezet). Az utols´o tag b¨unteti a popul´aci´oban tal´alhat´o v´altozatlannak jel¨olt objektumokat (ξ(u) = ∗) melyek nagy text´urav´altoz´ast jelz˝o ter¨uleteken helyezkednek el, illetve u´ jnak/leromboltnak jelzett e´ p¨uleteket (ξ(u) ∈ {1, 2}) a v´altozatlan ter¨uleteken. Az interakci´os potenci´alok prior geometriai k´enyszereket ´ırnak le: b¨untetik az azonos id˝or´eteget oszt´o objektum t´eglalapok nagy m´ert´ek˝u a´ tlapol´od´as´at (4.. a´ bra): I(u, v) = I[ξ(u)≃ξ(v)] ·

#(Ru ∩ Rv ) #(Ru ∪ Rv )

ahol ξ(u) ≃ ξ(v) fenn´all, ha ξ(u) = ξ(v), vagy ξ(u) = ∗, or ξ(v) = ∗.

9. a´ bra: Interakci´os jellemz˝o

5. Optimaliz´aci´o Az optim´alis objektum konfigur´aci´ot a t¨obbsz¨or¨os sz¨ulet´es e´ s hal´al (Multiple Birth and Death) algoritmussal [4] becs¨ulj¨uk, mely a k¨ovetkez˝o l´ep´eseket tartalmazza:

Képaf 2011, Szeged, Magyarország

´ uletek e´ s v´altoz´asaik detekci´oja Ep¨ (i)

23

(i)

Inicializ´aci´o: hat´arozzuk meg a Pb (s) e´ s ms (i ∈ {1, 2}) sz¨ulet´esi t´erk´epeket, e´ s induljunk ki u¨ res popul´aci´ob´ol ω = ∅. F˝o program: a´ ll´ıtsuk be a kezdeti inverz h˝om´ers´eklet param´etert β = β0 e´ s a diszkretiz´aci´os l´epcs˝ot δ = δ0 , ezut´an altern´aljuk a sz¨ulet´es e´ s hal´al l´ep´eseket. 1. Sz¨ulet´es: sorban vizsg´aljuk meg az s ∈ S pixeleket, e´ s ha nincs s k¨oz´eppont´u objektum a jelenlegi ω konfigur´aci´oban, vegy¨unk fel v´eletlenszer˝uen egy ξ ∈ {1, 2, ∗} (ξ) (1) (2) e´ rt´eket, legyen Pbb = Pb (s) ha ξ ∈ {1, 2}, Pbb = max {Pb (s), Pb (s)} ha ξ = ∗; e´ s futtassuk a sz¨ulet´es folyamatot s-ben δ Pbb val´osz´ın˝us´eggel. Sz¨ulet´es folyamat s-ben: gener´aljunk egy u´ j u objektumot s k¨oz´epponttal, ξ id˝oindexszel, a´ ll´ıtsuk be a eL (u), el (u) oldalhossz e´ rt´ekeket v´eletlenszer˝uen el˝ore meghat´arozott maxim´alis e´ s minim´alis oldalhosszak k¨oz¨ott, e´ s a´ ll´ıtsuk be a θ(u) (ξ) orient´aci´ot η(., ms , σθ ) Gaussi s˝ur˝us´egf¨uggv´eny˝u v´eletlen v´altoz´o alapj´an, ahogy azt a 3.1. fejezetben le´ırtuk. V´eg¨ul, adjuk u-t az aktu´alis ω konfigur´aci´ohoz. 2. Hal´al: tekints¨uk az aktu´alis ω = {u1 , . . . , un } objektum konfigur´aci´ot e´ s rendezz¨uk az objektumokat AD (u) alapj´an, cs¨okken˝o ir´anyban. Az objektumokat vizsg´aljunk meg ebben a sorrendben, e´ s minden egyes u-ra sz´am´ıtsuk ki az al´abbi e´ rt´eket ∆Φω (u) = ΦD (ω/{u}) − ΦD (ω), amely az u t¨orl´es´evel l´etrej¨ov˝o potenci´alis energia v´altoz´ast hat´arozza meg. A hal´aloz´asi ar´any ´ıgy: δaω (u) , ahol aω (u) = e−β·∆Φω (u) 1 + δaω (u) Ezut´an t¨or¨olj¨uk u-t ω-b´ol dω (u) val´osz´ın˝us´eggel. dω (u) =

Konvergencia teszt: am´ıg a folyamat nem konverg´al, n¨ovelj¨uk a β inverz h˝om´ers´ekletet, cs¨okkents¨uk a diszkretiz´aci´os l´epcs˝ot δ geometriai s´em´aval, e´ s l´epj¨unk vissza a sz¨ulet´es l´ep´esre. A konvergencia t´eny´et akkor a´ llap´ıthatjuk meg, ha minden olyan objektum, melyet az aktu´alis sz¨ulet´es l´ep´es gener´alt, e´ s csak azok t˝unnek el a k¨ovetkez˝o hal´al l´ep´esben. 1. t´abl´azat: A tesztadatok f˝o jellemz˝oi. Adathalmaz B UDAPEST B EIJING S ZADA A BIDJAN

T´ıpus l´egi QBird l´egi Ikonos

Sz´ın igen nem igen nem

a´ rny´ek igen igen nem nem

Gradiens j´o gyenge gyenge e´ les

Kurt´ozis r´eszben r´eszben nem igen

6. K´ıs´erletek M´odszer¨unket n´egy jelent˝osen k¨ul¨onb¨oz˝o adathalmazon e´ rt´ekelt¨uk ki1 , melyek f˝o jellemz˝oit az 1. t´abl´azat tartalmazza. Kvalitat´ıv eredm´enyek a 10–12 a´ br´akon l´athat´ok. 1

A szerz˝ok k¨osz¨onetet mondanak az adatszolg´altat´oknak: G¨or¨og Andr´as, Budapest, Francia V´edelmi Hivatal (DGA) e´ s Liama Laborat´orium, K´ına

Képaf 2011, Szeged, Magyarország

24

Benedek Csaba, Xavier Descombes, Josiane Zerubia

Az´ert, hogy al´at´amasszuk az objetumdetekci´o e´ s a v´altoz´asfelismer´es egy¨uttes kezel´es´enek el˝onyeit, a javasolt modellt (egy¨uttes detekci´o, ED) o¨ sszehasonl´ıtottuk egy konvencion´alis megold´assal, ahol az e´ p¨uleteket k¨ul¨on nyerj¨uk ki az egyes k´epeken, a v´altoz´asinform´aci´ot pedig ut´olag becs¨ulj¨uk a kinyert objektumok elhelyezked´es´enek e´ s geometriai param´etereinek o¨ sszevet´es´evel (szekvenci´alis detekci´o, SD). A 12. a´ br´an l´athat´o, hogy a SD m´odszer hamis riaszt´asokat okoz, mivel alacsony kontraszt´u ter¨uleteken egy-egy objektum hi´anyozhat valamelyik id˝or´etegen, valamint zaj miatt hamis tal´alatok is gyakrabban megjelennek a kev´esb´e robosztus egyn´ezet˝u inform´aci´ora val´o hagyatkoz´assal. A t¨obb jellemz˝ot egy¨uttesen kihaszn´al´o e´ p¨uletle´ır´o modell hat´ekonys´ag´at o¨ sszeha´ Verifik´aci´o, EV). ´ ´ m´odszerben sonl´ıtjuk egy f˝ok´ent e´ leken alapul´o m´odszerrel (El Az EV hasonl´oan [9]-hez, az a´ rny´ek e´ s tet˝osz´ın inform´aci´ot csak a be´ep´ıtett ter¨uletek hozz´avet˝oleges becsl´es´ehez haszn´aljuk, m´ıg az objektum verifik´aci´o kiz´ar´olag az e´ lk´ep illeszt´es´en alapul. Kvantitat´ıv tesztjeinkben a hi´anyz´o (HO) e´ s hamisan (FO) detekt´alt objektumainkat valamint a hi´anyz´o (HV) e´ s hamis (FV) v´altoz´asokat sz´amoltuk meg, ezenfel¨ul a detekci´o pixel szint˝u pontoss´ag´at (DP) is megadtuk. A DP sz´am´ıt´as´ahoz o¨ sszehasonl´ıtottuk az eredm´eny¨ul kapott e´ p¨ulet alaprajz maszkjainkat a k´ezzel k´esz´ıtett referencia (ground truth) maszkhoz, e´ s meghat´aroztuk a detekci´o F-m´ert´ek´et (a precizit´as e´ s visszah´ıv´asi ar´any harmonikus k¨ozepe). A 2. t´abl´azatban tal´alhat´o eredm´enyek meger˝os´ıtik a javasolt ED modell a´ ltal´anoss´ag´at e´ s el˝onyeit az SD e´ s e´ V m´odszerekhez k´epest (alacsonyabb objektum szint˝u hib´ak, magasabb DP t´enyez˝o). A ki´ert´ekel´es tov´abbi r´eszletei a szerz˝ok kutat´asi riportj´aban olvashat´ok [1].

10. a´ bra: Eredm´enyek k´et k´epr´eszleten a S ZADA adathalmazb´ol. A k´ek t´eglalapok v´altozatlan objektumokat jel¨olnek, a piros t´eglalapok v´altozottakat (´uj, lerombolt vagy a´ t´ep´ıtett).

Képaf 2011, Szeged, Magyarország

´ uletek e´ s v´altoz´asaik detekci´oja Ep¨

25

11. a´ bra: Az ismertetett m´odszer eredm´enyei k´et k´epp´aron. Fenn: B UDAPEST k´epr´eszlet (forr´as: c c G¨or¨og Andr´as ). Lenn: B EIJING (Liama Laborat´orium CAS K´ına). A v´altozatlan (k´ek) e´ s a megv´altozott (piros) e´ p¨uleteket megk¨ul¨onb¨oztetj¨uk.

c 12. a´ bra: Eredm´enyek az A BIDJAN k´epeken (DGA Franciaorsz´ag). Fenn: szekvenci´alis detekci´o (SD), valamennyi jelzett v´altoz´as hamis riaszt´as. Lenn: az ismertetett egy¨uttes detekci´os (ED) modell.

Képaf 2011, Szeged, Magyarország

26

Benedek Csaba, Xavier Descombes, Josiane Zerubia

2. t´abl´azat: Kvantitat´ıv eredm´enyek. #VT and #VN a v´altozatlan e´ s v´altozott e´ p¨uletek sz´am´at ´ referenciam´odszerek jel¨oli az adott teszthalmazban. ED a saj´at m´odszer, m´ıg az SD e´ s EV valamint a HO, FO, HV, FV e´ s DP ki´ert´ekel´esi t´enyez˝ok a 6. fejezetben ker¨ulnek r´eszletes bemutat´asra.

Adathalmaz #VT B UDAPEST 20 B EIJING 13 S ZADA 31 A BIDJAN 0

#VN 21 4 6 21

HO ´ SD ED EV 3 3 1 0 1 0 4 3 1 1 2 0

FO ´ SD ED EV 8 8 2 5 2 1 1 0 1 0 2 0

HV ´ SD RD EV 3 1 1 0 0 0 3 3 2 0 0 0

FV ´ SD ED EV 5 11 1 2 3 0 2 3 0 0 4 0

´ EV 0.73 0.48 0.78 0.84

DP SD 0.70 0.77 0.74 0.78

ED 0.78 0.85 0.83 0.91

Irodalom 1. C. Benedek, X. Descombes, and J. Zerubia. Building extraction and change detection in multitemporal aerial and satellite images in a joint stochastic approach. Research Report 7143, INRIA, Sophia Antipolis, December 2009. 2. F. Bovolo. A multilevel parcel-based approach to change detection in very high resolution multitemporal images. IEEE GRS Letters, 6(1):33–37, 2009. 3. Nicolas Champion, Leena Matikainen, Xinlian Liang, Juha Hyyppa, and Franz Rottensteiner. A test of 2D building change detection methods: Comparison, evaluation and perspectives. In ISPRS Congress, pages 297–304, Beijing, China, 2008. 4. X. Descombes, R. Minlos, and E. Zhizhina. Object extraction using a stochastic birth-anddeath dynamics in continuum. J. of Math. Imaging and Vision, 33(3):347–359, 2009. 5. A. Katartzis and H. Sahli. A stochastic framework for the identification of building rooftops using a single remote sensing image. IEEE Trans. GRS, 46(1):259–271, 2008. 6. Sanjiv Kumar and Martial Hebert. Man-made structure detection in natural images using a causal multiscale random field. In CVPR, volume 1, pages 119–126, 2003. 7. F. Lafarge, X. Descombes, J. Zerubia, and M. Pierrot-Deseilligny. Structural approach for building reconstruction from a single DSM. IEEE Trans. PAMI, 2009. in press. 8. J.A. Shufelt. Performance evaluation and analysis of monocular building extraction from aerial imagery. IEEE Trans. PAMI, 21(4):311–326, 1999. 9. B. Sirmacek and C. Unsalan. Building detection from aerial imagery using invariant color features and shadow information. In IEEE ISCIS, Istanbul, Turkey, 2008.