2D és 3D bináris objektumok lineáris

KÉPAF 2013 – a Képfeldolgozók és Alakfelismerők Társaságának 9. országos konferenciája

2D ´ es 3D bin´ aris objektumok line´ aris deform´ aci´ o-becsl´ es´ enek numerikus megold´ asi lehet˝ os´ egei Tan´ acs Attila1 , Joakim Lindblad2 , Nataˇsa Sladoje3 , Kató Zoltán1 1

Képfeldolgoz´ as és Sz´ am´ıt´ ogépes Grafika Tanszék Szegedi Tudom´ anyegyetem {tanacs,kato}@inf.u-szeged.hu 2 Centre for Image Analysis Swedish University of Agricultural Sciences, Uppsala, Sweden [email protected] 3 Faculty of Technical Sciences University of Novi Sad, Serbia [email protected]

Absztrakt. A képregisztr´ aci´ o a képfeldolgoz´ as egy alapfeladata, amelyet k¨ ul¨ onb¨ oz˝ o id˝ opontokban és/vagy néz˝ opontokb´ ol kész´ıtett felvételek k¨ oz¨ otti geometriai viszony meghat´ aroz´ as´ ara haszn´ alnak. Jelen cikk¨ unkben egy a ´ltal´ anos keretrendszert adunk meg, amely tetsz˝ oleges n-dimenzi´ os bin´ aris képek/objektumok k¨ oz¨ otti line´ aris regisztr´ aci´ os problém´ at képes megoldani megfeleltetések létes´ıtése nélk¨ ul. A megk¨ ozel´ıtés¨ unk polinomi´ alis egyenletrendszerek gener´ al´ as´ an és megold´ as´ an alapul. Szintetikus teszteken kereszt¨ ul a polinom egyenletrendszer k¨ ul¨ onféle numerikus megold´ asi lehet˝ oségeit vizsg´ aljuk, analitikus, iterat´ıv legkisebb négyzetes és kombin´ alt m´ odszereket vesz¨ unk figyelembe. A tesztjeink alapj´ an az iterat´ıv és a kombin´ alt megk¨ ozel´ıtés biztos´ıtja a legpontosabb eredményt. A tesztek megmutatj´ ak azt is, hogy képpont lefedettségi inform´ aci´ o felhaszn´ al´ as´ aval pontosabb objektum k¨ orvonal le´ır´ as kaphat´ o, ami a regisztr´ aci´ o pontoss´ ag´ at n¨ oveli. Mivel az egyenletrendszer megalkot´ as´ ahoz csak egyszer kell a képeket bej´ arnunk, ezért m´ odszereink alkalmasak nagy méret˝ u regisztr´ aci´ os problém´ ak gyors megold´ as´ ara, f¨ uggetlen¨ ul a deform´ aci´ o mértékét˝ ol.

1.

Bevezet´ es

A képregisztr´ aci´ o a képfeldolgozás egy fontos ter¨ ulete, célja képek közötti geometriai viszonyok meghat´ arozása. Az utóbbi évtizedekben számos megközel´ıtés sz¨ uletett problém´ ak széles skálájára [1]. 2D-ben a szegment´ alt alakzatok illesztése egy fontos regisztrációs probléma. Ilyen feladatokn´ al jellemz˝ oen két lépésb˝ol áll az illesztés: El˝oször egy szegmentáló algoritmus el˝ o´ all´ıtja az alakzatokat, majd ezután történik meg ezek illesztése. Ez a megk¨ ozel´ıtés k¨ ul¨ on¨ osen akkor hasznos, amikor a kép intenzitásértékei er˝os nemline´ aris torz´ıt´ asnak vannak kitéve, amely modellezése nehéz, pl. a röntgen

526


képalkot´ as bizonyos eseteiben. Amennyiben könnyen detektálható objektumok tal´ alhat´ ok a képen (pl. csontok vagy implantátumok röntgen vagy CT képen), ak´ ar egy egyszer˝ u szegment´ aló módszer is alkalmazható. Parametrikus transzformációbecsl˝o módszert javasoltak Haege és munkatársai sz¨ urke´ arnyalatos képekre [2, 3], ahol az intenzitásértékek felhasználásával lineáris egyenletrendszert kaphatunk. A helyes m˝ uködéshez elvárás, hogy ne legyen jelen a képen nemline´ aris intenzitás-torz´ıtás, valamint a háttért˝ol eltér˝o intenzit´ asérték˝ u objektumok egymásnak minél pontosabban megfeleltethet˝ok legyenek. Ha képek k¨ oz¨ ott az ´ atfedés nem teljes, akkor meg kell határozni egy átfed˝o ter¨ uletet, ami nem trivi´ alis feladat. Ha feltételezz¨ uk, hogy egymásnak megfeleltethet˝ o alakzatok/objektumok egyszer˝ uen szegmentálhatók a képeken, és nem feltételezz¨ uk az intenzit´ astartomány állandóságát, bináris objektumok illesztésére vezethetj¨ uk vissza a problémát. Ilyen esetekre polinomiális egyenletrendszerre vezet˝ o megold´ ast Domokos és munkatársa javasolt [4]. Korábbi publikációkban ezen m´ odszer k¨ ul¨ onb¨ oz˝ o variánsai összehasonl´ıtásra ker¨ ultek más szakirodalmi m´ odszerekkel [5, 6]. A 3D képalkot´ as orvosi és ipari alkalmazásokban manapság általánosan elterjedt. Bin´ aris objektumok j¨ ohetnek létre például a képalkotás eredményeként (pl. diszkrét tomogr´ afia), gener´ alódhatnak geometriai le´ırásokból (pl. CAD modell), vagy egym´ asnak megfeleltethet˝o ter¨ uletek szegmentálásával. A 3D regisztrációs problém´ at a klasszikus m´ odszerek általában vagy geometriai jellemz˝ok kinyerésével, vagy a képpontintenzitások közvetlen felhasználásával oldják meg. Az adatok k¨ oz¨ otti megfeleltetéseket rendszerint iterat´ıv keresés seg´ıtségével próbálják meghat´ arozni. A leggyakrabban alkalmazott geometriai jellemz˝ok közé a pontok, felsz´ınek [7], v´ azak [8], vagy ponthalmazok [9] tartoznak. Képpontok hasonl´ os´ ag´ an alapul´ o m´ odszerek jellemz˝oen nem-bináris képek esetén ker¨ ulnek alkalmaz´ asra, de bin´ aris esetben is felhasználhatók [1]. Mivel az iterat´ıv keresés ezen m´ odszerek esetében minden lépésben felhasználja a képjellemz˝o/intenzitás adatokat, emiatt nagy méret˝ u képi adatok esetében a megoldás id˝oigénye jelent˝ osen megn˝ o. Fontos d¨ ontés, hogy milyen geometriai transzformáció tételezhet¨ unk fel az objektumok k¨ oz¨ ott? Nemlineáris transzformációk alkalmazásával lehet˝oség van pl. sz¨ ovetek lok´ alis alakv´ altozásainak detektálására. Ilyen megközel´ıtés esetén viszont figyelembe kell venni a k¨ ulönböz˝o szövetek eltér˝o deformációs jellemz˝oit, ami nagyon nehézzé és alkalmazás-specifikussá teheti a megoldást. Sok esetben elegend˝ o glob´ alis line´ aris transzformációt alkalmazni, k¨ ulönösen ha a gyors sz´ am´ıt´ asi id˝ o elv´ ar´ as. Kor´ abbi publik´ aci´ oinkra ép´ıtve jelen cikk¨ unkben egy egységes keretrendszert vezet¨ unk be, amely tetsz˝ oleges n-dimenzióban használható. Ez a megközel´ıtés polinom egyenletrendszerek generálásán és megoldásán alapul és a szegmentáláson t´ ul nem igényli megfeleltetések keresését. Az egyenletrendszer a képek egyszeri bej´ ar´ as´ aval el˝ o´ all´ıthat´ o, annak megoldása már f¨ uggetlen a képek méretét˝ol. Ez k¨ ul¨ on¨ osen alkalmass´ a teszi a módszer¨ unket nagy méret˝ u, globális lineáris regisztr´ aci´ os problém´ ak hatékony megoldására. A digitális képtér csak korlátozott pontoss´ agot képes biztos´ıtani, ´ıgy az (5)-(9) egyenletekben szerepl˝o integrálok

527


csak k¨ ozel´ıthet˝ ok diszkrét o¨sszegként. A digitális adatábrázolás lehet˝oségeinek jobb kihaszn´ al´ asa érdekében korábbi publikációinkban az objektumok képpont lefedettségi reprezent´ aci´ oj´ anak felhasználását javasoltuk [13, 11] ahol a képpontok sz´ amértéke ar´ anyos a képpont térrészének a valós objektum által történ˝o lefedettségével. Bizony´ıt´ asra ker¨ ult, hogy egyez˝o térbeli felbontás esetén a bináris reprezent´ aci´ ohoz képest egy ilyen fuzzy reprezentáció nagyobb pontosságot biztos´ıt egyes képjellemz˝ ok becslésében [12]. Jelen cikk¨ unk u ´j eredménye a regisztrációs eljárás során el˝oálló polinomiális egyenletrendszerek gyors és hatékony megoldási lehet˝oségeinek részletes tárgyal´ asa. Megvizsg´ aljuk a t´ ulhatározott egyenletrendszer esetén alkalmazható legkisebb négyzetes megold´ ast, a nem-szinguláris esetben használható közvetlen analitikus megold´ ast, valamint ezek egy¨ uttes alkalmazásával el˝oálló kombinált m´ odszer tulajdons´ agait.

2.

Regisztr´ aci´ os keretrendszer

R¨ oviden ´ attekintj¨ uk a cikk¨ unkben felhasznált, korábban publikált 2D affin regisztr´ aci´ os m´ odszert [10] és kiterjesztj¨ uk tetsz˝oleges n dimenzióra. Jelölj¨ uk a sablon és a megfigyelés képek objektumpont-koordinátáit x, y ∈ Pn -el a projekt´ıv térben. A projekt´ıv tér használata lehet˝ové teszi az affin transzformációk egyszer˝ u jel¨ olésm´ od´ u megadását az u ń. homogén koordináták alkalmazásával. Mivel az affin transzform´ ació nem változtatja meg a pontok utolsó (homogén) koordin´ ata-értékét, vagyis az mindig 1 érték˝ u lesz, ´ıgy a további jelölésekben esetenként az Euklideszi teret is felhasználjuk, mindig az egyszer˝ ubb jelölésmódot alkalmazva. Jel¨ olje A az ismeretlen, meghatározásra váró affin transzformációt. Az egyenl˝ oség rel´ aci´ ot az al´ abbi m´ odon definiáljuk: Ax = y

⇔

x = A−1 y.

A fenti egyenletek akkor is fennállnak, ha megfelel˝oen választott ω : Pn → Pn f¨ uggvényeket alkalmazunk mindkét oldalra [4]: ω(Ax) = ω(y)

⇔

ω(x) = ω(A−1 y).

(1)

Bin´ aris képek nem tartalmaznak radiometrikus információt, ezért reprezent´ alhat´ ok a 1 : Pn → {0, 1} karakterisztikus f¨ uggvény¨ ukkel, ahol 0 és 1 értékek ker¨ ulnek hozz´ arendelésre a háttér és az objektum pontjaihoz. Jelölje 1t a sablon, 1o a megfigyelés karakterisztikus f¨ uggvényét. A pontmegfeleltetések elker¨ ulése végett integr´ aljunk az Ft = {x ∈ Pn |1t (x) = 1} és Fo = {y ∈ Pn |1o (y) = 1} objektumpont-tartom´ anyok felett: Z Z |A| ω(x) dx = ω(A−1 y) dy , és (2) Ft Fo Z Z 1 ω(y) dy . (3) ω(Ax) dx = |A| Fo Ft

528


A transzform´ aci´ o Jacobi determinánsa (|A|) meghatározható: R |A| = RFo

dy

dx Ft

.

(4)

A javasolt m´ odszer alap¨ otlete az, hogy elegend˝o szám´ u lineárisan f¨ uggetlen egyenletet gener´ aljunk az (1)-(3) képletek alkalmazásával. Legalább annyi egyenletre van sz¨ ukség¨ unk, amennyi az n-dimenziós affin transzformáció szabadsági foka. Ez 2D-ben 6, 3D-ben pedig 12. Mivel az ω-f¨ uggvények az ismeretlenekre is hatnak, nem kaphatunk lineáris egyenletrendszert. Ha közvetlen analitikus megold´ ast szeretnénk, az egyik legjobb választás a polinomok használata. (k)

Ennek elérésére a ω(x)p1 ,...,pn = xp11 . . . xpnn formulát használjuk, amely a transzform´ alt pont k-adik koordinátáját adja, ahol p1 , . . . , pn ∈ N0 . Például a Eq. (2) egyenletb˝ ol ezek a f¨ uggvények az alábbi polinomiális egyenleteket gener´ alj´ ak (harmadfokig bezárólag): Z

Z

|A|

1 dx = Ft

Z |A|

xa dx = Ft

Z |A|

n+1 X

xa xb dx =

(5)

Z qai

yi dy ,

n+1 X X n+1

Z qai qbj

xa xb xc dx = Ft

yi yj dy ,

(7)

Fo

i=1 j=1

Z

(6)

Fo

i=1

Ft

|A|

1 dy , Fo

n+1 X n+1 X n+1 X

Z yi yj yk dy ,

qai qbj qck

(8)

Fo

i=1 j=1 k=1

ahol 1 ≤ a, b, c ≤ n, a ≤ b ≤ c, és qij jelöli az A−1 inverz transzformáció elemeit. Magasabb foksz´ am´ u polinomok formalizmusa analóg módon megkapható. ´ Altal´ aban ezek a f¨ uggvények vegyes momentumokat vezetnek be az egyenletek mindkét oldal´ an, ´ıgy egy koordinátánként nem szétválasztható egyenletrendszert kapunk. A gyakorlatban ez nem okoz problémát az iterat´ıv megoldókn´ al, de analitikus m´ odszerrel ezek nem oldhatók meg hatékonyan (a megoldási m´ odszereket a k¨ ovetkez˝ o fejezetben tárgyaljuk). Szétválasztható egyenletrendszert kaphatunk az ω f¨ uggvények további korlátozásával: a pi paraméterek köz¨ ul csak az egyik lehet nem nulla. Ebben az esetben a k-adik szeparált egyenletrendszer kompaktabb form´ aban is fel´ırható: Z |A| Ft p−i1 qk1

xpk dx =

p X i1 X p i1

i1

i1 =0

in−1 −in in . . . qkn qk,n+1

Z Fo

529

i2 =0

i2

y1p−i1 y2i1 −i2

in−1

...

X in−1 in i =0 n

. . . ynin−1 −in

dy .

(9)


3.

Numerikus megold´ as

S´ıkbeli és térbeli esetre is kétféle megoldási stratégiát vizsgálunk: az egyenletrendszer k¨ ozvetlen, analitikus megoldását, valamint az iterat´ıv, legkisebb négyzetes értelemben optim´ alis keres˝ot. Mindkét megközel´ıtés rendelkezik el˝onyös és h´ atr´ anyos tulajdons´ agokkal. – Az analitikus megold´ as esetén az n-dimenziós affin transzformáció szabad paramétereinek megfelel˝o szám´ u egyenletet tudunk használni, m´ıg az iterat´ıv esetben dolgozhatunk t´ ulhatározott egyenletrendszerrel is, amely nagyobb stabilit´ ast adhat.1 – Gyors és hatékony analitikus megoldhatósághoz sz¨ ukséges, hogy az egyenletrendszer koordin´ at´ anként szétválasztható legyen. Az iterat´ıv technikánál nincs ilyen elv´ ar´ as. – Az analitikus m´ odszerek több száz, vagy akár több ezer lehetséges megoldást is adhatnak, ezek k¨ oz¨ ul sok, de akár az összes is komplex lehet. Ezek között tal´ alhat´ o a glob´ alis megoldás is, f¨ uggetlen¨ ul a transzformáció magnit´ udójától. Sz¨ ukség van egy megoldás kiválasztó sémára, amely ezek alapján egy valós megold´ ast biztos´ıt. Az iterat´ıv megközel´ıtés egy valós eredményt ad, viszont a keresés elakadhat lokális minimumokban. Ezen lokális minimumok elker¨ uléséhez ¨ osszetetett keresési stratégiára van sz¨ ukség. A megoldás szám´ıt´ asi ideje jobban megbecs¨ ulhet˝o az analitikus megoldás esetén, az iterat´ıv technik´ an´ al nagyobb k¨ ulönbségek is kialakulhatnak. – Az analitikus megold´ ast hatékonyan affin esetre tudjuk megadni, az iterat´ıvn´ al megszor´ıt´ asokat vezethet¨ unk be a transzformáció fokszámára vonatkoz´ oan. Val´ os képregisztrációs problémáknál a t¨ ukrözés ker¨ ulend˝o, mindkét megk¨ ozel´ıtés alkalmas az ilyen megoldások kisz˝ urésére. A numerikus stabilit´ as érdekében az objektumpont-koordinátákat a [−0.5, 0.5] tartom´ anyba normaliz´ altuk a Nt és No transzformációkkal, amelyek eltolást és sk´ al´ az´ ast tartalmaznak. Vegy¨ uk észre, hogy az (5)-(9) egyenletrendszerek minden ismeretlenje az integr´ alokon k´ıv¨ ul található, ´ıgy azokat elegend˝o egyszer kiértékelni. Id˝ obonyolults´ aga O(N ), ahol N az objektumpontok számát jelöli, mivel minden ¨ osszegzés a képek egyszeri bejárásával el˝oáll´ıtható. A k¨ ovetkez˝ o részben a két megoldási megközel´ıtést tárgyaljuk alaposabban. 3.1.

Iterat´ıv legkisebb n´ egyzetes megold´ as

A legkisebb négyzetes megoldás t´ ulhatározott egyenletrendszerek esetén haszn´ alatos. A koordin´ at´ ankénti szétválaszthatóság nem feltétel, használhatjuk a 1

Megjegyezz¨ uk, hogy természetesen egy t´ ulhat´ arozott egyenletrendszer esetén is lehetséges n·(n+1) egyenletb˝ ol a ´ll´ o rendszert gener´ alni a transzform´ aci´ o paraméterei szerint vett parci´ alis deriv´ altak alkalmaz´ as´ aval. Ekkor viszont m´ ar koordin´ at´ anként nem lesz szétv´ alaszthat´ o az egyenletrendszer n darab f¨ uggetlen részre, ami olyan magas polinom foksz´ amhoz vezethet, amelyet hatékonyan m´ ar nem tudunk analitikus m´ odszerrel megoldani.

530


(6)-(9) egyenletrendszert. Ez 2D-ben 2 + 3 + 4 = 9, m´ıg 3D-ben 3 + 6 + 10 = 19 egyenletet gener´ al. A numerikus stabilitás érdekében u ´jabb 9, illetve 19 egyenletet vesz¨ unk még a Eq. (3)-nek megfelel˝oen, ami a két ponthalmaz szerepének felcserélését jelenti. Megjegyezz¨ uk, hogy ez a lépés nem vezet be u ´j ismeretleneket, mivel a A transzform´ aci´ o paramétereit nem-szinguláris esetben egyértelm˝ uen meghat´ arozz´ ak a qij elemek. Így egy maximálisan harmadfok´ u, t´ ulhatározott egyenletrendszerhez jutunk. Ez az egyenletrendszer legkisebb négyzetes értelemben megoldhat´ o pl. a Levenberg-Marquardt (L-M) módszerrel. Azt tal´ altuk, hogy a kezdeti forgatási paraméter értékek er˝osen befolyásolják a regisztr´ aci´ os eredményt. Olyan gyakorlati alkalmazásokban, amelyekben ismert, hogy a forgat´ asbeli k¨ ulönbségek kicsik az objektumok között (pl. a képalkot´ as protokollja garant´ alja), vagy jól becs¨ ulhet˝ok, az iterációt elegend˝o egy kezd˝o paraméter´ all´ asb´ ol ind´ıtani. Ha a fenti feltétel nem garantálható, akkor az optimaliz´ al´ ast t¨ obb kezd˝ opontb´ ol is elind´ıthatjuk, és a megoldások köz¨ ul a legkisebb hib´ at ad´ ot v´ alasztjuk. 2D-ben 4, 3D-ben 27 k¨ ulönböz˝o kezd˝o paraméterállást haszn´ altunk fel, szisztematikusan az origó kör¨ uli 90◦ -os, valamint a tengelyek ◦ k¨ or¨ uli 120 -os elforgat´ asoknak megfelel˝oen. A skálázó, ny´ıró és eltolási paraméterek az identikus értékeiket kapták. Az ¨ osszes keresési ir´ any teljes kiértékelése id˝oigényes, és az esetek egy részében nem is sz¨ ukséges. Amennyiben a keresést az optimum közeléb˝ol ind´ıtjuk, az algebrai hiba gyors cs¨ okkenést mutat, vagyis kevés iterációszám alatt is az optimum k¨ ozelébe ér¨ unk. Ezért el˝oször kevés iterációszámmal ind´ıtjuk a keresést és a legkisebb hib´ at ad´ ot v´ alasztjuk ki, és azzal folytatjuk tovább a teljes keresést. 2D-ben 50, 3D-ben 20 iter´ aciót engedélyez¨ unk az els˝o körben. Egy másik alkalmazott heurisztik´ ank szerint, ha a kezdeti alacsony iterációszám´ u szisztematikus keresés esetén az algebrai hiba egy megadott k¨ uszöbérték alá esik, akkor nincs sz¨ ukség tov´ abbi jel¨ oltek keresésre, ezzel folytathatjuk a teljes keresést. Ez a 3D esetben fontos, ahol a k¨ usz¨ obértéket 100-ra áll´ıtottuk. 2D-ben csak négy keresési ir´ any van, ezek mindegyikét tesztelj¨ uk. Ezeket a paramétereket tapasztalati u ´ton határoztuk meg. További heurisztik´ ak is bevezethet˝ ok lennének. Például ne csak egy potenciális jelöltet, hanem t¨ obbet is megtartsunk, mindegyikb˝ol ind´ıtsunk teljes keresést, és a legjobbat v´ alasszuk. V´ arhat´ oan ez tov´ abbi, igaz kis mérték˝ u, javulást hozhatna. Ez igazából r´ avil´ ag´ıt az iterat´ıv technika gyenge pontjára: egyens´ ulyoznunk kell a szám´ıtási id˝ o és stabilit´ as k¨ oz¨ ott egy ¨ osszetett keresési stratégia paramétereinek finomhangol´ as´ aval. A keresés k¨ ozben megszor´ıtásokat alkalmazhatunk az A transzformációra. Egy ´ altal´ anos A transzformáció t¨ ukrözéseket is tartalmazhat, amely nem k´ıv´ anatos a legt¨ obb gyakorlati alkalmazásban. Ezt elker¨ ulend˝o, magas algebrai hib´ at rendel¨ unk azokhoz az esetekhez, ahol |A| < 0, vagyis t¨ ukrözés is jelen van. Mivel az A m´ atrix seg´ıtségével az affinnál alacsonyabb szabadsági fok´ u transzform´ aci´ okat is le tudunk ´ırni, könnyen át tudjuk alak´ıtani a keresést merev-test vagy hasonl´ os´ agi transzformációt igényl˝o problémák megoldására. Ehhez az algebrai hiba sz´ am´ıt´ asakor a kisebb szabadsági fok´ u transzformáció paramétereib˝ol meg tudjuk hat´ arozni az A affin mátrix elemeit, amit felhasználhatunk változat-

531


lan form´ aban a kereséshez. Az 1. algoritmus összegzi a javasolt iterációs technika lépéseit.

Algorithm 1: Iterat´ıv megoldási stratégia Bemenet: Sablon és megfigyelés képek. Kimenet: Transzform´ aci´ os paraméterek (A). Step 1 Objektumpont koordin´ at´ ak normaliz´ al´ asa az Nt , No transzform´ aci´ okkal Step 2 Konstru´ aljuk meg az egyenletrendszert (Eq. (5)–(8) képletek) Step 3 Legkisebb négyzetes megold´ as • Az LM keres˝ o inicializ´ al´ asa (orient´ aci´ ok, kezdeti iter´ aci´ osz´ am) • Minden iter´ aci´ oban sz´ am´ıtsuk ki az E algebrai hib´ at Ha sz¨ ukséges alkalmazzuk a megszor´ıt´ asokat a paraméterekre Opcion´ alis: Ha E értéke elegend˝ oen alacsony, akkor a tov´ abbi orient´ aci´ ok kihagy´ asa • A∗ = A legjobb orient´ aci´ ob´ ol ind´ıtott teljes kereséssel eredménye ∗ Step 4 Normaliz´ al´ as inverze: A = N−1 o · A · Nt

3.2.

Analitikus megold´ as

A k¨ ozvetlen analitikus megoldáshoz pontosan annyi egyenletre van sz¨ ukség¨ unk, amekkora a szabads´ agi foka az n-dimenziós affin transzformációnak, vagyis 2Dben 6, 3D-ben 12. Mivel a hatékony megoldhatósághoz fontos, hogy koordinát´ anként szétv´ alaszthat´ o egyenletrendszert kapjunk, ezért (9) alapján választunk ω-f¨ uggvényeket. Így 2D-ben harmadfok´ u, 3D-ben negyedfok´ u polinomiális egyenletrendszerhez jutunk. Az el˝ o´ all´ o t¨ obb sz´ az, vagy akár több ezer valós és/vagy komplex megoldás k¨ oz¨ ul ki kell v´ alasztanunk a legjobbnak t˝ un˝o megoldást. Erre k¨ ulönféle kiválaszt´ asi sém´ akat haszn´ alhatunk. (a) Csak a val´ os megold´ asok figyelembe vétele, a komplexek elhagyásával. A potenci´ alis jel¨ oltek k¨ oz¨ ul azt válasszuk, amelyikre a transzformáció Jacobi determin´ ansa és a képpontok száma alapján szám´ıtott közel´ıt˝o érték a legközelebb van egym´ ashoz. A korábbi publikációinkban ez a módszer ker¨ ult alkalmaz´ asra [4, 13, 10], és mint kider¨ ult, a csupa komplex megoldást szolgáltató esetek miatt ´ allt el˝ o az ott tapasztalt 5%-os megoldhatatlansági arány. Erre a sém´ ara RealDet néven hivatkozunk a szintetikus tesztekben. (b) A val´ os megold´ asok mellett a komplexeket is vegy¨ uk figyelembe, azok valós részeinek haszn´ alat´ aval. Mivel a komplex megoldások a komplex konjugált p´ arjaikkal jelennek meg, a komplex megoldások felét eleve elvethetj¨ uk. Ezután a kiv´ alaszt´ as ugyan´ ugy megy, mint az (a) esetben. Ez a megoldás mindig garant´ alja a megoldhat´ oságot (amennyiben van legalább 1 olyan, amely nem tartalmaz t¨ ukr¨ ozést). Erre a sémára CplxDet néven hivatkozunk a tesztek

532


sor´ an. Ezt a megk¨ ozel´ıtést az motiválja, hogy az egyébként valós megoldások komplexszé v´ alhatnak zaj vagy diszkretizálási hiba hatására. (c) Hasonl´ o (b)-hez, viszont, a megoldás kiválasztásakor a Jacobi determináns helyett azt vizsg´ aljuk, hogy melyik megoldás adja a legkisebb hibát egy m´ asik, t´ ulhat´ arozott egyenletrendszerbe behelyettes´ıtve. Az egyszer˝ uség kedvéért erre a célra azt a t´ ulhatározott egyenletrendszert használjuk, amelyet a legkisebb négyzetes megoldásnál is. A séma c´ımkéje EqsSel a tesztekben. Megjegyezz¨ uk, hogy mindhárom eljárás képes kisz˝ urni a nemk´ıvánatos t¨ ukröz˝ o transzform´ aci´ okat, amelyek esetében a forgató almátrix determinánsa negat´ıv. Ebb˝ ol k¨ ovetkezik, hogy a (b) és (c) sémák csak akkor nem szolgáltatnak eredményt, ha minden megold´ as tartalmaz t¨ ukrözést. Ilyen eset viszont nem fordult el˝ o a szintetikus tesztjeinkben. A 4. részben megmutatjuk, hogy általában a (c) séma adja a legjobb megoldást, használata 3D-ben elengedhetetlen. A 2. algoritmus ¨ osszegzi az analitikus módszer lépéseit. Algorithm 2: Analitikus megoldási stratégia Bemenet: Sablon és megfigyelés képek. Output: Transzform´ aci´ os paraméterek (A). Step Step Step Step

Objektumpont koordin´ at´ ak normaliz´ al´ asa az Nt , No transzform´ aci´ okkal Konstru´ aljuk meg az egyenletrendszert (Eq. (9) képlet) Oldjuk meg az egyenletrendszereket V´ alasszuk ki a legjobbnak t˝ un˝ o megold´ ast (A∗ ) (a), (b) vagy (c) séma alkalmaz´ as´ aval ∗ Step 5 Normaliz´ al´ as inverze: A = N−1 o · A · Nt

3.3.

1 2 3 4

Kombin´ alt megk¨ ozel´ıt´ es

Ahogyan a szintetikus teszteknél látni fogjuk (4. fejezet), az analitikus megoldás altal´ ´ aban a glob´ alis optimumhoz közeli megoldást szolgáltat a transzformáció magnit´ ud´ oj´ at´ ol f¨ uggetlen¨ ul, de az iterat´ıv technika t´ ulszárnyalja regisztrációs pontoss´ agban. Mivel ez ut´ obbit a globális optimum közeléb˝ol célszer˝ u ind´ıtani, ezért bonyolult, és zajjal terhelt esetben id˝oigényesebb keresési stratégiát igényel. (Ne feledj¨ uk, hogy a két esetben más egyenletrendszerek ker¨ ulnek megoldásra!) Egy kombin´ alt megk¨ ozel´ıtéssel kihasználhatjuk mindkét módszer el˝onyös tulajdons´ agait: az analitikus megoldásával inicializálhatjuk az iterat´ıv keres˝ot, kiv´ altva ezzel annak ¨ osszetett heurisztikus keresési stratégiáját. Erre a módszerre Combined néven hivatkozunk.

4.

Szintetikus tesztek

Egy bin´ aris képekb˝ ol ´ all´ o adatbázis seg´ıtségével szintetikus teszteken kereszt¨ ul vizsg´ aljuk az egyes megold´ asi stratégiákat és a fuzzy határvonal reprezentáció hat´ as´ at. A képp´ arok ismert affin transzformációk alkalmazásával álltak el˝o.

533


Algorithm 3: Kombin´ alt megoldási stratégia Bemenet: Sablon és megfigyelés képek. Output: Transzform´ aci´ os paraméterek (A). Step Step Step Step

1 2 3 4

Objektumpont koordin´ at´ ak normaliz´ al´ asa az Nt , No transzform´ aci´ okkal Konstru´ aljuk meg az egyenletrendszert (Eq. (9) képlet) Oldjuk meg az egyenletrendszereket V´ alasszuk ki a legjobbnak t˝ un˝ o megold´ ast (A∗ ) (a), (b) vagy (c) séma alkalmaz´ as´ aval Step 5 Konstru´ aljuk meg az u ´jabb egyenletrendszert (Eq. (5)–(8) képletek) Step 6 Legkisebb négyzetes megold´ as A∗∗ = Az optim´ alis transzform´ aci´ o paraméterei az A∗ -b´ ol ind´ıtott teljes kereséssel ad´ odnak ∗∗ Step 7 Normaliz´ al´ as inverze: A = N−1 · Nt o ·A

Az eredmények mérése kétféle hibamértéket vezet¨ unk be. Az -hiba az átlagos t´ avols´ agot jelenti a sablon kép képpontjainak az ismert transzformációval vett (Ap), valamint a regisztr´ ació eredményeként kapott transzformációval el˝oálló b helye (Ap) k¨ oz¨ ott. Ezt a mértéket a szintetikus teszteknél használhatjuk, mivel ott ismert az alkalmazott transzformáció. Gyakorlati problémáknál nem ez a helyzet. A δ-hiba a két alakzat közötti átfedés mértékét jellemzi. =

1 X b kAp − Apk, |T | p∈T

és

δ=

|R 4 O| · 100%, |R| + |O|

ahol 4 a szimmetrikus k¨ ul¨ onbség, m´ıg T , R és O a sablon, a regisztrált és a megfigyelés alakzatot jel¨ oli. Megjegyezz¨ uk, hogy a hibaszám´ıtások el˝ott a fuzzy reprezent´ aci´ ot bin´ ariss´ a alak´ıtjuk egy alfa-vágással α = 0.5 értékkel (a fuzzy tags´ agi f¨ uggvény k¨ usz¨ ob¨ olésével). 4.1.

Kvantitat´ıv ki´ ert´ ekel´ es 2D-ben

A 2D teszthez 56 k¨ ul¨ onb¨ oz˝ o alakzatot és transzformált változataikat, összesen 2240 képp´ art haszn´ altunk fel. Mivel módszer¨ unk jellegéb˝ol adódóan nagyméret˝ u képek esetén m˝ uk¨ odik legjobban, a korábbi cikk¨ unkben ilyen képekkel dolgoztunk, a képek szélessége és magassága 500 és 100 pixel közötti volt. Szintén feltételezt¨ uk, hogy a fuzzy határvonal reprezentáció alacsonyabb képfelbontás mellett is haszn´ alhat´ ov´ a teszi a módszer¨ unket [13]. Emiatt a jelenlegi teszt¨ unkben a képméreteket nyolcad´ ara csökkentett¨ uk az egyes irányok mentén. A transzform´ aci´ os paramétereket egyenletes eloszlással, véletlenszer˝ uen gener´ altuk. A forgat´ asi érték tetsz˝oleges lehetett. A skálázási tényez˝ot az [1, 2] tartom´ anyb´ ol v´ alasztottuk (maximálisan kétszeres nagy´ıtás), de az esetek felében ennek reciprok´ at véve kicsiny´ıtést hajtottunk végre. A ny´ırási paraméter tartom´ anya [−1, 1] volt, m´ıg az eltolás maximuma 150 képpont. A sablonok bináris képek voltak, vagyis 0 vagy 1 fuzzy-tagsági értékkel rendelkeztek. A fuzzy határvonal reprezent´ aci´ ot 16×16 méret˝ u t´ ulmintavételezéssel közel´ıtett¨ uk, összegezve

534


milyen ar´ anyban tal´ alhat´ o h´ attér és objektum pont ezen a rácson. A fuzzy-tagság értékeket kvant´ altuk k-bites egész értékekre ((k = 1, . . . , 8)), ´ıgy el˝oáll´ıtva a k¨ ul¨ onb¨ oz˝ o fuzzy reprezent´ aciós szinteket. Néhány sablon és megfigyelés képpár l´ athat´ o az 1. ´ abr´ an.

1. ´ abra: Péld´ ak a 2D adatb´ azisb´ ol: Sablon (fels˝ o sor) és megfigyelés képek (als´ o sor)

A k¨ ul¨ onféle fuzzy reprezentációs szintekhez és kiválasztási sémákhoz tartoz´ o hibaeloszl´ ast és sz´ am´ıt´ asi id˝oigényt mutat a 2. ábra, valamint és δ-hibák medi´ anjait a 1. t´ abl´ azat. Megfigyelhetj¨ uk, hogy a tapasztalat alátámasztja az elméleti eredményeket, vagyis a fuzzy reprezent´ aci´ o jelent˝osen jav´ıtja a regisztrációt. A kor´ abbi cikkekben egyed¨ uliként alkalmazott RealDet sémát jól láthatóan t´ ulteljes´ıti az ¨ osszes javasolt u ´j módszer. Az L-M megoldás az egyértelm˝ uen legjobb a bin´ aris esetben. Ez a módszer 8-bites fuzzy szinten is a kisebb medián hib´ at okoz, mint az analitikus módszerek, de figyelj¨ uk meg, hogy az EqsSel m´ odszer 4 és 8-bites esetben jobb elfogadható hibaarányt szolgáltat. 8-bites reprezent´ aci´ on´ al a kombin´ alt módszer a legjobb, de érdemes megfigyelni, hogy a bin´ aris esetben elmarad az iterat´ıvtól. Ez azt sugallja, hogy amennyiben az objektum reprezentáció szinte tökéletes, az analitikus m´ odszer jobb kezd˝opoz´ıciót szolgáltat az iterat´ıv kereséshez, mint az ahhoz javasolt keresési stratégia. Amikor viszont a reprezentációs hiba magasabb, az analitikus m´ odszer rosszabb eredményt ad. Így a gyakorlati, hibára hajlamos alkalmaz´ asokn´ al az iterat´ıv technika választása jobbnak t˝ unik. A RealDet séma teljes´ıtménye gyenge, az eredmények ≈20–30%-a nem elfogadható, amiben benne van a 6–7%-nyi megoldhatatlan eset is. Ez az arány jóval kisebb a legjobb analitikus (0.4–7.4%), iterat´ıv (1.3–3.9%) és kombinált (0.4–7.0%) m´ odszerek esetében, amelyek ráadásul mindig szolgáltattak eredményt. Az analitikus m´ odszerek esetén azok kiválasztási hatékonyságát is vizsgáltuk. Mivel pontosan ismerj¨ uk az alakzatok közötti geometriai transzformációt, minden lehetséges megold´ asra ki tudjuk értékelni az -hibát és meghatározhatjuk ezek minimum´ at – ez az elméleti optimum, amit a kiválasztási sémáink el tudnak érni. Azon esetek ar´ anya, amikor a séma által adott megoldáshoz és az optim´ alishoz tartoz´ o -hib´ ak távolsága nagyobb, mint 1, 6.52% volt a bináris, és 0.36% a 8-bites reprezentáció esetén. Megállap´ıthatjuk, hogy a bináris esetben egyik séma sem k¨ ozel´ıti meg az optimálisan elérhet˝ot, de 8-bites fuzzy reprezent´ aci´ oval az EqsSel már összemérhet˝o vele.

535


1. t´ abl´ azat: Medi´ an hib´ ak k¨ ul¨ onb¨ oz˝ o fuzzy reprezent´ aci´ os szintekhez. Az esetek sz´ azaléka, ahol az -hiba 1 alatti (≈ kit˝ un˝ o) és 5 alatti (≈ vizu´ alisan elfogadhat´ o) szintén felt¨ untetésre ker¨ ult. A vastag´ıtott sz´ amok a kateg´ ori´ an bel¨ uli legjobb eredményeket mutatj´ ak.

k (pxls.) 1 0.58 2 0.25 4 0.09 8 0.05

RealDet kiv´ alaszt´ asi séma δ (%) > 1 (%) > 5 (%) Nem reg. (%) 3.65 43.4 29.2 6.5 1.44 31.3 23.7 6.3 0.61 26.4 21.0 6.3 0.34 24.5 20.5 7.1

k (pxls.) 1 0.47 2 0.19 4 0.06 8 0.04

CplxDet kiv´ alaszt´ asi séma δ (%) > 1 (%) > 5 (%) Nem 2.49 34.6 17.3 0.96 19.4 9.3 0.41 11.8 4.2 0.23 7.0 2.5

reg. (%) 0 0 0 0

EqsSel kiv´ alaszt´ asi séma k (pxls.) δ (%) > 1 (%) > 5 (%) Nem 1 0.39 1.89 25.8 7.3 2 0.17 0.88 13.3 3.2 0.36 7.5 1.1 4 0.06 8 0.03 0.20 3.9 0.4

reg. (%) 0 0 0 0

L-M megold´ as k (pxls.) 1 0.17 2 0.07 4 0.02 8 0.01

δ (%) > 1 (%) > 5 (%) Nem reg. (%) 0.76 12.2 3.9 0 0.32 6.4 2.2 0 0.13 3.3 1.4 0 0.08 2.5 1.3 0

n (pxls.) 1 0.18 2 0.07 4 0.02 8 0.01

Combined kiv´ alaszt´ asi séma δ (%) > 1 (%) > 5 (%) Nem 0.79 14.6 7.0 0.32 7.0 3.0 0.13 3.0 1.0 0.08 1.6 0.4

reg. (%) 0 0 0 0

Az algoritmusokat Matlab-ban implementáltuk. Az analitikus megoldásokhoz a solve, az iterat´ıv technik´ ahoz az fsolve f¨ uggvényt használtuk fel. A teszteket egy 2.4 GHz-es Intel Core2 Duo processzorral rendelkez˝o laptopon futtatuk. Az atlagos sz´ ´ am´ıt´ asi id˝ o 1 m´ asodperc alatti, kivéve a kombinált módszert, ahol ez 1.3 m´ asodperc k¨ or¨ ul alakult. Az analitikus megoldók id˝oigénye konstansnak tekinthet˝ o. Az iterat´ıv technikánál nagyobb k¨ ulönbségek is kialakulhatnak. A fuzzy reprezent´ aci´ os szint nem befolyásolja egyik módszer id˝oigényét sem.

536


5 4.5 4 3.5 3 2.5 2 1.5 1 0.5 0

RealDet 1‐bit CplxDet 1‐bit EqsSel 1‐bit L‐M 1‐bit RealDet 8‐bit CplxDet 8‐bit EqsSel 8‐bit L‐M 8‐bit

2101

1951

1801

1651

1501

1351

1201

901

1051

751

601

451

301

1

Combined 1‐bit

151

Epszzilon hiba

Megoldási módszerek és fuzzy reprezentáció 2D‐ben

Combined 8‐bit

Számítási idő 2D‐ben 6

Id dő (mp)

5 RealDet

4

CplxDet

3

EqsSel 2

L‐M

1

Combined

0

2. ´ abra: Hiba és sz´ am´ıt´ asi id˝ o eloszl´ asok a 2240 esetre. Az értékek a legjobbt´ ol a legrosszabbig lexikografikusan rendezésre ker¨ ultek.

4.2.

Kvantitat´ıv ki´ ert´ ekel´ es 3D-ben

A megold´ asi lehet˝ oségeket 3D objektumokon is tesztelt¨ uk. 15 objektum összesen 1500 transzform´ alt v´ altozatát használtuk. A sablon objektumok 200 ezer és 2 milli´ o k¨ oz¨ otti képpontsz´ am´ uak voltak. A transzformáció paraméterek az alábbi tartom´ anyokb´ ol ker¨ ultek ki véletlenszer˝ uen: elforgatás [0, 2π); skálázás [0.5, 1.5]; ny´ır´ as [−1, 1]; eltol´ as [0, 1] (nagyobb eltolásnak az alkalmazott normalizálás miatt nincs szerepe). Minden sablonra 100 véletlenszer˝ u transzformációt hajtottunk végre, amelyek k¨ oz¨ ul 25 merev-test, 25 nem-uniform skálázó, és 50 teljes affin volt. Az 3. ´ abr´ an l´ athatunk néhány példát az adatbázisból. A fuzzy reprezent´ aci´ ohoz n × n × n (n ∈ {1, 2, 4, 8}) méret˝ u fel¨ ulmintavételezést alkalmaztunk képpontonként, a hozzá tartozó fedettségi értékek a rácson vett objektum és h´ attérpontok számának arányával ker¨ ult közel´ıtésre2 . A δ-hiba sz´ am´ıt´ asa el˝ ott az objektumokat binarizáltuk. A regisztrációs pontosságokat a 2. t´ abl´ azat, az -hib´ ak és a szám´ıtási id˝o eloszlását a 4. ábra mutatja. 2

Megjegyezz¨ uk, hogy ez a fuzzy reprezent´ aci´ o eltér a 2D-ben alkalmazott´ ol, mivel a 3D eset – nagy méretének k¨ ovetkeztében – m´ as kezelést k´ıv´ ant.

537


3. ´ abra: Péld´ ak a 3D adatb´ azisb´ ol: sablon (fels˝ o sor) és deform´ alt verzi´ oi (als´ o sor) 2. t´ abl´ azat: Medi´ an hiba értékek k¨ ul¨ onb¨ oz˝ o fuzzy reprezent´ aci´ os szintekre. Az esetek sz´ azaléka, ahol a δ-hiba 1 alatti (≈ kit˝ un˝ o) és 10 alatti (≈ vizu´ alisan elfogadhat´ o) szintén felt¨ untetésre ker¨ ult. A vastag´ıtott sz´ amok a kateg´ ori´ an bel¨ uli legjobb eredményeket mutatj´ ak.

n 1 2 4 8

EqsSel kiv´ alaszt´ asi séma δ δ > 1% δ > 10% Id˝ o (mp) 0.2681 1.0613 52.3% 0.87% 2.15 0.1164 0.5569 28.1% 0.07% 2.14 0.1034 0.5106 19.1% 0.00% 2.15 0.1060 0.5351 18.96% 0.00% 2.14 L-M megold´ as

n 1 2 4 8

0.0361 0.0108 0.0069 0.0065

δ 0.1555 0.0627 0.0470 0.0402

δ > 1% 10.67% 3.13% 2.47% 2.47%

δ > 10% Id˝ o (mp) 2.13% 1.54 2.27% 1.56 2.20% 1.54 2.20% 1.52

n 1 2 4 8

Combined kiv´ alaszt´ asi séma δ δ > 1% δ > 10% Id˝ o (mp) 0.0359 0.1546 8.95% 0.00% 2.32 0.0108 0.0624 1.07% 0.07% 2.42 0.0069 0.0469 0.33% 0.00% 2.23 0.0065 0.0402 0.27%. 0.00% 2.31

Az eredmények mutatj´ ak, hogy már a bináris reprezentáció is képes kiváló eredményt adni. Viszont már az alacsonyabb fuzzy reprezentációs szintek is tiszt´ an l´ athat´ o javul´ ast hoznak, k¨ ulönösen a kiváló regisztrációs eredmények sz´ am´ aban. Az analitikus megold´ as CplxDet sémával nagyon gyengén teljes´ıt, 44-54% k¨ oz¨ otti a nem elfogadhat´ o regisztrációs eredmények aránya a k¨ ulönböz˝o fuzzy szintekre. A RealDet sémát nem is tesztelt¨ uk. Az iterat´ıv L-M módszer alacsonyabb medi´ an hib´ at ad, mint a legjobb analitikus módszer, de az elfogadhat´ o regisztr´ aci´ os eredmények számában megel˝ozi az EqsSel séma. A 2D esettel ellentétben a kombin´ alt módszer jól láthatóan a legjobb választás minden fuzzy reprezent´ aci´ os szinten, beleértve a bináris esetet is. A felt¨ untetett szám´ıtási

538


5 4.5 4 3.5 3 2.5 2 1.5 1 0.5 0

CplxDet 1‐bit EqsSel 1‐bit L‐M 1‐bit Combined 1‐bit CplxDet 8‐bit EqSel 8‐bit L‐M 8‐bit Combined 8‐bit

1 101 201 301 401 501 601 701 801 901 1001 1101 1201 1301 1401

Epszzilon hiba

Megoldási módszerek és fuzzy reprezentáció 3D‐ben

CplxDet EqsSel L‐M

1401

1301

1201

1101

901

1001

801

701

601

501

401

301

201

1

Combined

101

Idő (mp)

Számítási idő 3D‐ben 10 9 8 7 6 5 4 3 2 1 0

4. ´ abra: Hiba és sz´ am´ıt´ asi id˝ o eloszl´ asok a 3D adatb´ azis esetén

id˝ ok nem tartalmazz´ ak az egyenletrendszer generálásnak idejét, ami átlagosan 1 tizedm´ asodperc. Az iterat´ıv módszert a Matlab fsolve f¨ uggvényével valós´ıtottuk meg. Az analitikus megold´ ashoz a PHCPack csomagot [14] használtuk, mivel a Matlab nem volt képes a negyedfok´ u polinomiális egyenletrendszer megoldására. 4.3.

Robusztuss´ ag vizsg´ alat 3D-ben

A gyakorlatban a képp´ arokon, objektumokon többféle degradáció is megjelenik, ilyenek péld´ aul a hi´ anyz´ o adatok, szegmentációs hibák. A módszer¨ unk robusztuss´ ag´ anak tesztelésére h´ arom féle degradációt´ıpust modellezt¨ unk a bináris képeinken (5. ´ abra). A hi´ anyzó képpontok tesztelésére adott százaléknyi képpont ker¨ ult az objektumb´ ol véletlenszer˝ uen törlésre. A szegmentációs hiba modellezésére az objektum k¨ orvonala mentén véletlenszer˝ uen kis méret˝ u régiókat távol´ıtottunk el az objektumból vagy adtunk hozzá az objektumhoz. A hiányzó térfogatrészek vizsg´ alat´ ahoz egy véletlenszer˝ uen kiválasztott objektumpont környezetéb˝ ol t´ avol´ıtottunk el adott mennyiség˝ u objektumpontot. Terjedelmi okokb´ ol itt csak az eredmények értékelését közölj¨ uk, részletes táblázatok és grafikonok nélk¨ ul. Az egyenletesen elt´ avol´ıtott objektumpontok általában nem okoznak problém´ at egyik megold´ asi m´ odszer esetén sem, akár 90% eltávol´ıtása után is elfo-

539


5. ´ abra: Péld´ ak képdegrad´ aci´ okra egy 3D objektum 2D szeletén: Képpontok 90%nak véletlenszer˝ u elt´ avol´ıt´ asa (balr´ ol), képpontok 10%-nak m´ odos´ıt´ asa a hat´ ar mentén kis méret˝ u régi´ okban (k¨ ozépen), és a 5%-nak elt´ avol´ıt´ asa egy képpontb´ ol kiindulva (jobbr´ ol).

gadhat´ ok az eredmények. A szegmentációs hiba esetében 25%-os degradációs szintnél az esetek 70%-ban az objektumok illeszkedése elfogadható. Mint általában a ter¨ ulet-alap´ u m´ odszerek, a mi megközel´ıtés¨ unk is érzékeny a hiányzó térfogatrészekre. 1 − 2%-os degrad´ aciós szint felett az eredmények megb´ızhatatlanná v´ alnak. Azt tapasztaltuk, hogy az analitikus megoldás önmagában nem versenyképes az iterat´ıv technik´ aval. A kombinált megközel´ıtés fel¨ ulm´ ulja az iterat´ıvat kis mérték˝ u degrad´ aci´ ok esetén. A degradáció mértékének növekedésével ez az el˝ony ´ viszont elt˝ unik. Eszrevehetj¨ uk azt is, hogy mivel az algebrai hiba magasabb degrad´ aci´ os szint esetén jelent˝ osen növekedhet, több kezd˝o orientáció vizsgálatára ¨ van sz¨ ukség, ami megn¨ oveli a szám´ıtási id˝ot. Osszefoglal´ asként elmondhatjuk, hogy a m´ odszer¨ unk rendszerint jól teljes´ıt, am´ıg az objektumunk geometriai momentumai nem v´ altoznak meg nagymértékben a degradáció hatására.

5.

¨ Osszegz´ es

Cikk¨ unkben egy egyes´ıtett regisztrációs keretrendszert mutattunk be amely képes 2D és 3D bin´ aris objektumok között többféle lineáris deformáció becslésére. A regisztr´ aci´ os probléma megoldását egy polinom egyenletrendszer generálása ´ eredmény¨ és megold´ asa adja. Uj unk a regisztrációs eljárás során el˝oálló polinomi´ alis egyenletrendszerek gyors és hatékony megoldási lehet˝oségeinek részletes t´ argyal´ asa. Azt tapasztaltuk, hogy az iterat´ıv legkisebb négyzetes megoldás szisztematikus keres˝ o elj´ ar´ assal kombinálva a legjobb választás 2D problémákra, m´ıg 3D-ben az analitikus és az iterat´ıv technikák kombinációját célszer˝ u választani. Tesztjeinkben vizsgáltuk a korábbi publikációinkban bevezetett fuzzy reprezent´ aci´ ot, amely a diszkrét objektumok képpont lefedettségi információját jelenti, és kimutattuk ennek el˝onyeit.

K¨ osz¨ onetnyilv´ an´ıt´ as A szegedi szerz˝ ok munk´ aj´ at az OTKA K75637 szám´ u pályázat és a futurICT.hu ´ nev˝ u, TAMOP-4.2.2.C-11/1/KONV-2012-0013 azonos´ıtószám´ u projekt támogatta az Eur´ opai Uni´ o és az Európai Szociális Alap társfinansz´ırozása mellett.

540


N. Sladoje és J. Lindblad munkáját anyagilag támogatta a Szerb Köztársaság Tudom´ anyos Minisztériuma az ON144018 és ON144029 projekteken kereszt¨ ul.3 K¨ osz¨ onetet mondunk Niku Corneának, aki a szintetikus képek egy részét biztos´ıtotta sz´ amunkra.

Irodalom 1. B. Zitov´ a and J. Flusser, “Image registration methods: A survey,” Image and Vision Computing, vol. 21, no. 11, pp. 977–1000, October 2003. 2. R. Hagege and J.M. Francos, “Linear estimation of sequences of multi-dimensional affine transformations,” in Proc. of International Conference on Acoustics, Speech and Signal Processing, Toulouse, France, May 2006, IEEE, vol. 2, pp. 785–788. 3. R. Hagege and J.M. Francos, “Parametric estimation of affine transformations: An exact linear solution,” Journal of Mathematical Imaging and Vision, vol. 37, no. 1, pp. 1–16, 2010. 4. C. Domokos, Z. Kato, and J.M. Francos, “Parametric estimation of affine deformations of binary images,” in Proc. of International Conference on Acoustics, Speech and Signal Processing, Las Vegas, Nevada, USA, April 2008, IEEE, pp. 889–892. 5. J. Kannala, E. Rahtu, J. Heikkil¨ a, and M. Salo, “A new method for affine registration of images and point sets,” in Proc. of the 14th Scandinavian Conference on Image Analysis (SCIA). 2005, LNCS, pp. 224–234, Springer. 6. T. Suk and J. Flusser, “Affine normalization of symmetric objects,” in Proc. of the 7th International Conference on Advanced Concepts for Intelligent Vision Systems (ACIVS). 2005, LNCS, pp. 100–107, Springer. 7. J. Zhang, Y. Ge, S.H. Ong, C.K. Chui, S.H. Teoh, and C.H. Yan, “Rapid surface registration of 3D volumes using a neural network approach,” Image Vision Comput., vol. 26, no. 2, pp. 201–210, 2008. 8. N.D. Cornea, M.F. Demirci, D. Silver, A. Shokoufandeh, S.J. Dickinson, and P.B. Kantor, “3D object retrieval using many-to-many matching of curve skeletons,” Int. Conf. on Shape Modeling and Appl., pp. 368–373, 2005. ´ c, and N. Sladoje, “On set distances and their application to 9. J. Lindblad, V. Curi´ image registration,” in Proc. of the 6th International Symposium on Image and Signal Processing and Analysis (ISPA). 2009, pp. 449–454, IEEE. 10. C. Domokos and Z. Kato, “Parametric estimation of affine deformations of planar shapes,” Pattern Recognition, vol. 43, no. 3, pp. 569–578, 2010. 11. A. Tan´ acs, J. Lindblad, N. Sladoje, and Z. Kato, “Estimation of linear deformations of 3D objects,” in Proc. of International Conference on Image Processing (ICIP). 2010, pp. 153–156, IEEE. 12. N. Sladoje and J. Lindblad, “Pixel coverage segmentation for improved feature estimation,” in Proc. of ICIAP. 2009, vol. 5716 of LNCS, pp. 929–938, Springer. 13. A. Tan´ acs, C. Domokos, N. Sladoje, J. Lindblad, and Z. Kato, “Recovering affine deformations of fuzzy shapes,” in Proc. of SCIA. 2009, vol. 5575 of LNCS, pp. 735–744, Springer. 14. J. Verschelde, “Algorithm 795: Phcpack: a general-purpose solver for polynomial systems by homotopy continuation,” ACM Trans. Math. Softw., vol. 25, no. 2, pp. 251–276, 1999. 3

N. Sladoje and J. Lindblad are financially supported by the Ministry of Science of the Republic of Serbia through Projects ON144018 and ON144029 of MI-SANU.

541

2D és 3D bináris objektumok lineáris

Recommend Documents