3D objektumok line´ aris deform´ aci´ oinak becsl´ ese⋆ Tan´acs Attila1 , Joakim Lindblad2 , Nataˇsa Sladoje3 , Kat´o Zolt´an1 1
K´epfeldolgoz´ as ´es Sz´ am´ıt´ og´epes Grafika Tansz´ek 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 cikkben egy olyan regisztr´ aci´ os m´ odszert ismertet¨ unk, amely 3D objektumok ´es affin deform´ altjaik k¨ oz¨ otti geometriai elt´er´eseket hat´ arozza meg. A megold´ ashoz egy t´ ulhat´ arozott polinomi´ alis egyenletrendszer ker¨ ul fel´ep´ıt´esre ´es megold´ asra. K´eppont lefedetts´egi 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. Az iterat´ıv egyenletrendszer megold´ as alkalmaz´ as´ aval lehet˝ os´eg ny´ılik alacsonyabb szabads´ agi fokkal rendelkez˝ o, pl. merev-test vagy hasonl´ os´ agi transzform´ aci´ ok meghat´ aroz´ as´ ara is. Szintetikus tesztek seg´ıts´eg´evel bemutatjuk a k´eppont lefedetts´egi inform´ aci´ o alkalmaz´ asnak el˝ onyeit, valamint r´ avil´ ag´ıtunk a m´ odszer¨ unk robusztuss´ ag´ ara t¨ obbf´ele szegment´ al´ asi hiba t´ıpus eset´en. A m´ odszer¨ unket val´ os CT k´epeken is tesztelt¨ uk.
1.
Bevezet´ es
A 3D k´epalkot´as orvosi ´es ipari alkalmaz´asokban manaps´ag ´altal´ anosan elterjedt. Ugyanarr´ ol vagy hasonl´ o objektumr´ ol k¨ ul¨onb¨ oz˝o id˝opontokban k´esz¨ ult k´epek felvetik a k´epregisztr´ aci´ o probl´em´ aj´ at, vagyis a k´epek k¨oz¨otti geometriai megfeleltet´esek meghat´aroz´as´ at. Az ut´obbi ´evtizedekben sz´amos regisztr´aci´ os m´odszer ker¨ ult publik´al´ asra igen sz´eles alkalmaz´asi k¨orben [1]. A regisztr´ aci´ os probl´em´ at a klasszikus m´odszerek ´altal´ aban vagy geometriai jellemz˝ ok kinyer´es´evel, vagy a k´eppontintenzit´ asok k¨ozvetlen felhaszn´al´as´aval oldj´ ak meg. Az adatok k¨oz¨otti megfeleltet´eseket rendszerint iterat´ıv keres´es seg´ıts´eg´evel pr´ob´alj´ ak meghat´arozni. A leggyakrabban alkalmazott geometriai jellemz˝ ok k¨oz´e a pontok, felsz´ınek [2], v´azak tartoznak. A m´odszer sebess´ege szint´en fontos t´enyez˝o; k¨ozel val´ os idej˝ u megold´as sz¨ uks´eges pl. m˝ ut´etek k¨ozben a m˝ ut´et ⋆
A cikk eredm´enyei az al´ abbi publik´ aci´ oban jelentek meg: A. Tan´ acs, J. Lindblad, N. Sladoje, and Z. Kato. “Estimation of Linear Deformations of 3D Objects,” in Proceedings of 2010 IEEE 17th International Conference on Image Processing. 2010, pp. 153–156.
472
Tan´ acs Attila ´es mtsai
el˝ otti ´es k¨ozbeni vizsg´alatok illeszt´es´ere. Zhang ´es munkat´arsai ´attekint´est adtak a felsz´ın-alap´ u illeszt˝o technik´akr´ol, ´es egy olyan u ´j elj´ar´ast javasoltak, amely 15-sz¨ or gyorsabb a klasszikus ICP (Iterative Closest Point – iterat´ıv legk¨ ozelebbi pont) m´odszern´el [2]. Azonban m´eg ´ıgy is kb. 1 percet vesz ig´enybe egy nagy felbont´ as´ u CT k´epb˝ol kinyert csigolya objektum illeszt´ese. K´eppontok hasonl´ os´ ag´an alapul´ o m´odszerek jellemz˝ oen nem-bin´aris k´epek eset´en ker¨ ulnek alkalmaz´asra, de bin´ aris esetben is felhaszn´alhat´ok [3]. Mivel az iterat´ıv keres´es ezen m´odszerek eset´eben minden l´ep´esben felhaszn´alja a k´epjellemz˝ o/intenzit´ as adatokat, emiatt nagy m´eret˝ u k´epi adatok eset´eben a megold´as id˝oig´enye jelent˝ osen megn˝o. Burel ´es munkat´arsai egy direkt m´odszert javasoltak, amely a 3D objektum felsz´ın´enek szf´erikus harmonikus felbont´ as´ab´ol nyeri ki az orient´ aci´ os elt´er´eseket, ezzel gyors megold´ast szolg´ altatva merev-test probl´em´ akra [4]. Ez a m´odszer viszont affin elt´er´esekre k¨ozvetlen¨ ul nem haszn´alhat´o. Jelen cikk¨ unkben egy kor´ abbi 2D affin m´odszer¨ unket [5] terjesztj¨ uk ki 3D esetre. A kiterjeszt´es nem trivi´alis; 3D esetben c´elszer˝ u t´ ulhat´arozott egyenletrendszert fel´ırni, amelynek ´altal´ anos esetben nincs megold´asa. A legkisebb n´egyzetes ´ertelemben optim´ alis megold´ast a Levenberg-Marquardt m´odszerrel hat´ arozzuk meg. Az egyenletrendszer meghat´aroz´as´ahoz elegend˝o egyszer v´egigj´arni a k´eppontokat, nincs sz¨ uks´eg megfeleltet´esek keres´es´ere, emiatt a megold´as id˝oig´enye m´eg nagy m´eret˝ u k´epek eset´en is alacsony. Amennyiben rendelkez´esre ´all, a k´eppont lefedetts´egi inform´aci´ o felhaszn´al´as´aval a regisztr´aci´ o pontoss´aga tov´abb n¨ ovelhet˝ o.
2.
Regisztr´ aci´ os keretrendszer
Jel¨olje x, y ∈ P3 a sablon ´es a megfigyel´es objektumpontjait a projekt´ıv t´erben. Jel¨olje A a meghat´arozand´o ismeretlen, nemszingul´ aris affin transzform´ aci´ o4×4 m´eret˝ u homog´en m´atrix´at. A sablon ´es a megfigyel´es k¨oz¨ott ez az al´abbi kapcsolatot adja: Ax = y ⇔ x = A−1 y. (1) A fenti egyeneletek akkor is ´erv´enyben maradnak, ha megfelel˝oen megv´ alasztott ω : P3 → P3 f¨ uggv´enyeket alkalmazunk mindk´et oldalon [6]: ω(Ax) = ω(y)
⇔
ω(x) = ω(A−1 y).
(2)
A pontmegfeleltet´esek elker¨ ul´ese ´erdek´eben a sablon ´es megfigyel´es objektumok Ft ´es Fo el˝ ot´er tartom´ any´an integr´alunk [6]: Z Z ω(A−1 y) dy , ´es (3) ω(x) dx = |A| Fo F Z Z t 1 ω(y) dy. (4) ω(Ax) dx = |A| Fo Ft A transzform´ aci´ o Jakobi m´atrixa megkaphat´o az al´abbi alakban: R dy |A| = RFo . dx Ft
3D objektumok line´ aris deform´ aci´ oinak becsl´ese
473
A m´odszer¨ unk alap¨otlete az, hogy a sz¨ uks´eges sz´am´ u, line´arisan f¨ uggetlen egyenletet a (3)–(4) rel´aci´ ok seg´ıts´eg´evel el˝oa´ll´ıtsunk. Egy 3D affin transzform´ aci´ o szabad param´etereinek sz´ ama 12, ´ıgy legal´ abb ennyi egyenletre van sz¨ uks´eg¨ unk. A c´el el´er´ese ´erdek´eben olyan ω f¨ uggv´enyeket v´alasztunk, amelyek a pontok k(k) adik koordin´ at´aj´ ara az al´ abbi alakot ¨olti: ω(x)f,g,h = xf1 ·xg2 ·xh3 , ahol f, g, h ∈ N, f + g + h = d, ´es d ∈ {1, 2, 3}. A (3)-b´ol ezek az al´abbi polinomi´alis egyenleteket gener´ alj´ ak: |A|
Z
xa dx =
Ft
|A|
|A|
Z
Z
Ft
xa xb dx = Ft
xa xb xc dx =
4 X
qai
Z
Fo i=1 4 4 XX
qai qbj
i=1 j=1
4 X 4 X 4 X i=1 j=1 k=1
(5)
yi dy , Z
yi yj dy ,
(6)
Fo
qai qbj qck
Z
yi yj yk dy
(7)
Fo
ahol 1 ≤ a, b, c ≤ 3, a ≤ b ≤ c, ´es qij jel¨oli az inverz A−1 transzform´ aci´ o ismeretlen elemeit. Ez ¨ osszesen 3 + 6 + 10 = 19 egyenletet jelent. A numerikus stabilit´as n¨ ovel´ese ´erdek´eben u ´jabb 19 egyenletet nyerhet¨ unk (4) alkalmaz´as´aval, vagyis az x ´es y ponthalmazok felcser´el´es´evel. Megjegyezz¨ uk, hogy ez a l´ep´es nem vezet be u ´j ismeretleneket, mivel a nemszingul´ aris esetben az A m´atrix elemei egy´ertelm˝ uen meghat´arozottak a qij param´eterek ismeret´eben. Az ´ıgy el˝oa´ll´ıtott egyenletrendszer harmadfok´ u ´es t´ ulhat´arozott. 2.1.
K´ eppont lefedetts´ egen alapul´ o objektum reprezent´ aci´ o
A digit´ alis k´ept´er csak korl´atozott pontoss´agot k´epes biztos´ıtani, ´ıgy az (5)– (7) egyenletekben szerepl˝ o integr´alok csak k¨ozel´ıthet˝ok diszkr´et ¨osszegk´ent. A digit´ alis adat´ abr´ azol´as lehet˝ os´egeinek jobb kihaszn´ al´al´asa ´erdek´eben az objektumok k´eppont lefedetts´egi reprezent´ aci´ oj´ anak felhaszn´al´as´at javasoljuk, ahol a k´eppontok sz´ am´ert´eke ar´ anyos a k´eppont t´err´esz´enek a val´os objektum ´altal t¨ ort´en˝o lefedetts´eg´evel. Bizony´ıt´asra ker¨ ult, hogy egyez˝o t´erbeli felbont´ as eset´en a bin´ aris reprezent´ aci´ ohoz k´epest egy ilyen reprezent´ aci´ o nagyobb pontoss´agot biztos´ıt egyes k´epjellemz˝ ok becsl´es´eben [8]. A kor´ abbi [5] cikk¨ unkben t´ argyaltakhoz hasonl´ oan most is a geometriai momentumok nagy pontoss´ ag´ u becsl´ese a fontos sz´amunkra, figyelembe v´eve hogy az (5)–(7) egyenletek egy¨ utthat´oi a sablon ´es a megfigyel´es k´epek (folytonos) geometriai momentumai. Egy folytonos 3D objektum i + j + k rend˝ u folytonos momentumai, vagyis az (5)–(7) egyenletek integr´aljai k¨ozel´ıthet˝ok az al´abbi m´odon [7]: Z X (8) µt (x) xi1 xj2 xk3 , xi1 xj2 xk3 dx ≈ Ft x∈Xt ahol µt (x) jel¨ oli a k´eppont lefedetts´eg´enek m´ert´ek´et a sablon k´epen. Hasonl´o m´odon adhat´o k¨ozel´ıt´es Fo tartom´anyra, µo lefedetts´eggel. A Jakobi m´atrix az
474
Tan´ acs Attila ´es mtsai
al´ abbi m´odon k¨ozel´ıthet˝ o:
P y∈Xo µo (y) |A| = P . (9) x∈Xt µt (x) ahol Xt ´es Xo jel¨ oli a sablon ´es a megfigyelt k´ep diszkr´et tartom´anyait. A k¨ozel´ıt˝o diszkr´et polinom´ alis egyenletrendszer ezek ut´an el˝oa´ll´ıthat´o a k¨ozel´ıt´esek (5)–(7) egyenletekbe t¨ ort´en˝o beilleszt´es´evel. A µ lefedetts´egi ´ert´ekek k¨ozel´ıt´ese kinyerhet˝o megfelel˝o szegment´ al´o m´odszerek eredm´eny´eb˝ol, ilyen lehet p´eld´ aul egy kor´abbi szegment´ al´o m´odszer¨ unk [8] 3D kiterjeszt´ese.
3.
Numerikus megold´ as
Az (5)–(7) polinomi´alis egyenletrendszer legkisebb n´egyzetes ´ertelemben optim´alis megold´asa megkaphat´o a klasszikus Levenberg-Marquardt (LM) m´odszer alkalmaz´as´ aval. Az iterat´ıv LM m´odszer h´ atr´ anya a direkt megold´asokhoz k´epest az, hogy a keres´es elakadhat lok´alis optimumokban, valamint a keres´es fut´asideje nagyobb lehet. M´ asr´eszr˝ ol viszont el˝onye, hogy akkor is szolg´ altat egy k¨ozel´ıt˝o eredm´enyt, amennyiben az egyenletrendszer algebrai hib´aja nagy, ami a direkt megold´ast megakad´alyozn´ a. A numerikus stabilit´as n¨ ovel´ese ´erdek´eben az objektumpontok koordin´at´ait a [−0.5, 0.5] intervallumba sk´ al´azzuk egy el˝ok´esz´ıt˝o l´ep´esben az Nt ´es No (eltol´ asi ´es sk´ al´ az´o) transzform´ aci´ ok alkalmaz´as´aval. Vegy¨ uk ´eszre, hogy az (5)–(7) egyenletekben az ¨ osszes ismeretlen az integr´alokon k´ıv¨ ul tal´alhat´o, ´ıgy az integr´alokat elegend˝o egyszer kisz´ am´ıtani. Ennek id˝okomplexit´ asa O(N ), ahol N az objektumpontok sz´ ama, mivel az ¨osszegz´esek elv´egz´es´ehez elegend˝o egyszer bej´ arni a k´epek objektumpontjait. Azt tapasztaltuk, hogy a kiindul´ asi elforgat´ asi param´eterek nagym´ert´ekben befoly´ asolj´ ak a regisztr´ aci´ os eredm´enyt. A lok´alis optimumba fut´as es´ely´enek cs¨ okkent´es´ere a keres´est 27 k¨ ul¨onb¨ oz˝o orient´ aci´ ob´ol ind´ıtjuk, a 3 t´erbeli tengely k¨or¨ uli 120◦-os elforgat´ asoknak megfelel˝oen. A sk´ al´az´asi, ny´ır´ asi ´es eltol´ asi param´eterek be´ all´ıt´ asa az identikus transzform´ aci´ o megfelel˝o param´eter´ert´ekeinek megfelel˝oen t¨ ort´ent. Ha egy optimumhoz k¨ozeli poz´ıci´ob´ol ind´ıtjuk a keres´est, az algebrai hiba gyors cs¨ okken´est mutat. Ez lehet˝ov´e teszi az egyes keres´esek le´ all´ıt´ as´ at n´eh´any iter´ aci´ os l´ep´es (eset¨ unben ezt 20 iter´aci´ ora ´all´ıtottuk be) ut´an. Ezek ut´an a legkisebb hib´ at eredm´enyez˝o keres´esi ´agban egy teljes keres´es ind´ıtunk. Amennyiben b´ armely kezd˝o poz´ıci´o eset´en 20 iter´aci´ o ut´an az algebrai hiba egy konstans ´ert´ek alatti (eset¨ unkben ez az ´ert´ek 100 volt), u ´ gy vessz¨ uk, hogy ez elegend˝oen k¨ozel tal´ alhat´o az optimumhoz ´es a tov´abbi kezd˝opoz´ıci´ok vizsg´alat´at kihagyjuk. A fenti konstans param´eterek meghat´aroz´asa tapasztalati u ´ton t¨ ort´ent. Egy ´ altal´ anos A transzform´ aci´ os m´atrix t¨ ukr¨oz´eseket is tartalmazhat, ami t¨ obb val´ os alkalmaz´as eset´eben nem k´ıv´ anatos. A t¨ ukr¨oz´esek elker¨ ul´ese ´erdek´eben megszor´ıt´ asokat alkalmazhatunk a transzform´ aci´ os param´eterekre a keres´es k¨ozben: amennyiben |A| < 0, vagyis tartalmaz t¨ ukr¨oz´est is, algebrai hibak´ent egy nagy konstans ´ert´eket adunk vissza (eset¨ unkben ez 1050 volt).
3D objektumok line´ aris deform´ aci´ oinak becsl´ese
475
Mivel az A m´atrix seg´ıts´eg´evel alacsonyabb szabads´agi fok´ u transzform´ aci´ ok megad´ as´ ara is lehet˝ os´eg van, a m´odszer¨ unket k¨onnyen ´atalak´ıthatjuk ilyen, pl. merev-test vagy hasonl´ os´ agi transzform´ aci´ o keres´es´ere is. Az algebrai hiba meghat´ aroz´asakor az alacsonyabb szabads´ag´ u fok´ u transzform´ aci´ o param´etereib˝ol kisz´ am´ıtjuk az A m´atrixot, vagyis megkapjuk az adott transzform´ aci´ ot le´ır´ o 12 affin param´eter ´ert´eket. Ezek alapj´an az algebrai hiba az affinnal egyez˝o m´odon kisz´ am´ıthat´ o. Az 1. algoritmus ¨ osszefoglalja a javasolt m´odszer¨ unk l´ep´eseit. Algorithm 1: 3D objektumok affin regisztr´aci´ oja Bement: Sablon ´es megfigyel´es 3D k´epek. Kimenet: Transzform´ aci´ os param´eterek A m´ atrixa. 1. l´ ep´ es Objektum k´eppontok kinyer´ese ´es Nt , No normaliz´ al´ o transzform´ aci´ ok alkalmaz´ asa 2. l´ ep´ es (8)–(9) alapj´ an polinomi´ alis egyenletrendszer k´esz´ıt´ese 3. l´ ep´ es Legkisebb n´egyzetes megold´ as • LM megold´ o inicializ´ al´ asa (27 orient´ aci´ o, egyenk´ent 20 iter´ aci´ o) • Minden iter´ aci´ os l´ep´esben az E algebrai hiba sz´ am´ıt´ asa Megszor´ıt´ asok alkalmaz´ asa a param´eterekre, ha sz¨ uks´eges Ha E < 100, a tov´ abbi poz´ıci´ ok figyelmen k´ıv¨ ul hagy´ asa • A∗ = A legjobb poz´ıci´ ob´ ol ind´ıtott teljes keres´es eredm´enye ∗ 4. l´ ep´ es Normaliz´ al´ as inverz´enek alkalmaz´ asa: A = N−1 o · A · Nt
4.
Szintetikus ´ es val´ os tesztek
A javasolt m´odszer¨ unk hat´ekonys´ ag´anak ki´ert´ekel´es´et egy 3D objektumokat tartalmaz´ o adatb´azison v´egezt¨ uk. Az adatb´azisunk 15 k¨ ul¨onb¨ oz˝o 3D objektumot ´es annak objektumonk´ent 100 transzform´ alt k´ep´et tartalmazta. Az objektumok k´eppontjainak sz´ ama 200000–2 milli´ o k¨oz¨ott v´altozott. A transzform´ aci´ o param´eterei v´eletlenszer˝ uen ker¨ ultek meghat´aroz´asra az al´abbi intervallumokb´ol: forgat´ asi sz¨ ogek: [0, 2π); sk´ al´ az´asi param´eterek: [0.5, 1.5] (egyenl˝ o m´ert´ekben kicsiny´ıt´es ´es nagy´ıt´ as); ny´ır´ as: [−1, 1]; eltol´ as: [0, 1] (a normaliz´al´o l´ep´es miatt nagyobb m´ert´ek˝ u eltol´ asok irrelev´ansak). Minden sablon objektumra 100 transzform´ aci´ ot alkalmaztunk, ezek k¨oz¨ ul 25 volt merev-test, 25 merev-test kieg´esz´ıtve nem-uniform sk´ al´az´assal, valamint 50 teljes affin. Az 1. ´ abra mutat n´eh´any p´eld´ at az adatb´azisb´ol. Az eredm´enyek sz´ amszer˝ u ki´ert´ekel´es´ehez az al´abbi k´et hibam´ert´eket haszn´altuk: ǫ=
1 X b k(A − A)pk, |T | p∈T
and
δ=
|R △ O| · 100%, |R| + |O|
ahol △ jel¨ oli a szimmetrikus k¨ ul¨onbs´eget, m´ıg T , R ´es O jel¨olik a sablon, a regisztr´ alt ´es a megfigyelt objektum k´eppontjainak halmaz´at. A m´odszer¨ unket
476
Tan´ acs Attila ´es mtsai
Matlab 7.7 alatt implement´ altuk, ´es egy 2.4 GHz-es Intel Core2 Duo processzorral rendelkez˝o asztali sz´ am´ıt´ og´epen futtattuk.
1. ´ abra: P´eld´ ak a k´epi adatb´ azisb´ ol: sablon objektumok (fel¨ ul) ´es affin m´ odon deform´ alt megfigyelt k´epeik (alul).
4.1.
K´ eppont lefedetts´ egi szintek hat´ asa
A megfigyelt objektumok k´eppont lefedetts´egi reprezent´ aci´ oj´ anak elk´esz´ıt´ese a k´eppontok t´erfogat´anak n × n × n m´eret˝ u fel¨ ulmintav´etelez´es´evel t¨ ort´ent, a lefedetts´eg az objektumon bel¨ ulre es˝o elemeknek a teljeshez viszony´ıtott ar´any´aval ker¨ ult k¨ozel´ıt´esre. A δ hiba ki´ert´ekel´ese el˝ott az objektumok binariz´al´asra ker¨ ultek. A regisztr´ aci´ os m´odszer pontoss´ag´at k¨ ul¨onb¨ oz˝o lefedetts´egi felbont´ asok eset´ere az 1. t´ abl´ azat mutatja. 1. t´ abl´ azat: Medi´ an hiba ´ert´ekek k¨ ul¨ onb¨ oz˝ o n fel¨ ulmintav´etelez´esi szintekre. A regisztr´ aci´ os eredm´enyek azon sz´ azal´eka, amelyekre δ > 1, valamint δ > 10 szint´en felt¨ untet´esre ker¨ ult (0 < δ < 1 kit˝ un˝ o eredm´eny, 1 < δ < 10 j´ o ´es elfogadhat´ o eredm´eny, 10 < δ t´ ul nagy hiba). n 1 2 4 8
ǫ 0.0361 0.0108 0.0069 0.0065
δ δ > 1% δ > 10% Id˝ o (mp.) 0.1555 10.67 2.13 1.54 0.0627 3.13 2.27 1.56 0.0470 2.47 2.20 1.54 0.0402 2.47 2.20 1.52
A sz´ am´ıt´ asi id˝o nem tartalmazza az egyenletrendszer fel´ep´ıt´es´enek idej´et, amihez a jelenlegi, nem optimaliz´ alt implement´ aci´ oban 1.5–2 m´asodperc sz¨ uks´eges. Ez jelent˝ osen gyors´ıthat´o lenne. Az eredm´enyek azt mutatj´ ak, hogy m´ar a bin´ aris reprezent´ aci´ o is kiv´ al´o eredm´enyeket szolg´ altat. Azonban ak´ ar a legalacsonyabb k´eppont fedetts´egi reprezent´ aci´ o is j´ol l´athat´o javul´ast okoz. n = 4
3D objektumok line´ aris deform´ aci´ oinak becsl´ese
477
szint felett a javul´as m´ert´eke m´ar nem sz´amottev˝o. A sz´am´ıt´asi id˝o f¨ uggetlen n ´ert´ek´et˝ol. 4.2.
Robusztuss´ agi tesztek
A gyakorlatban a k´epp´arokon, objektumokon t¨ obbf´ele degrad´ aci´ o is megjelenik, ilyenek p´eld´ aul a hi´anyz´ o adatok, szegment´ aci´ os hib´ak. A m´odszer¨ unk robusztuss´ag´anak tesztel´es´ere h´ arom f´ele degrad´ aci´ ot´ıpust modellezt¨ unk a bin´aris k´epeinken. A hi´anyz´ o k´eppontok tesztel´es´ere adott sz´azal´eknyi k´eppont ker¨ ult az objektumb´ ol v´eletlenszer˝ uen t¨ orl´esre. A szegment´ aci´os hiba modellez´es´ere az objektum k¨orvonala ment´en v´eletlenszer˝ uen kis m´eret˝ u r´egi´ okat t´ avol´ıtottunk el az objektumb´ ol vagy adtunk hozz´ a az objektumhoz. A hi´anyz´ o t´erfogatr´eszek vizsg´alat´ahoz egy v´eletlenszer˝ uen kiv´ alasztott objektumpont k¨ornyezet´eb˝ol t´ avol´ıtottunk el adott mennyis´eg˝ u objektumpontot. A k¨ ul¨onb¨ oz˝o degrad´ aci´ o t´ıpusokra mutat p´eld´ at a 2. ´ abra. Az ´ıgy kapott regisztr´aci´ os eredm´enyeket a 2. t´ abl´ azat mutatja.
2. ´ abra: P´eld´ ak k´epdegrad´ aci´ okra egy 3D objektum 2D szelet´en: K´eppontok 90%nak v´eletlenszer˝ u elt´ avol´ıt´ asa (balr´ ol), k´eppontok 10%-nak m´ odos´ıt´ asa a hat´ ar ment´en kis m´eret˝ u r´egi´ okban (k¨ oz´epen), ´es a 5%-nak elt´ avol´ıt´ asa egy k´eppontb´ ol kiindulva (jobbr´ ol).
2. t´ abl´ azat: K´epi degrad´ aci´ ok ´ altal okozott regisztr´ aci´ os hib´ ak Hi´ anyz´ o 50% ǫ (k´eppont) 0.22 0.83 δ (%) δ > 5% 7.3% δ > 10% 3.3% Id˝ o (mp.) 2.0
k´eppontok 90% 0.65 2.20 25% 7.6% 3.4
Szegment´ aci´ os hiba 5% 25% 0.30 1.79 1.15 5.76 7.4% 61% 2.8% 28% 3.7 6.6
Hi´ anyz´ o t´erfogatr´esz 1% 2% 1.77 3.82 5.22 9.92 53% 84% 23% 49% 5.3 5.8
Az egyenletesen elt´ avol´ıtott objektumpontok ´altal´ aban nem okoznak probl´em´at, ak´ ar 90% elt´ avol´ıt´ asa ut´an is elfogadhat´ ok az eredm´enyek. A szegment´ aci´ os hiba eset´eben 25%-os degrad´ aci´ os szintn´el az esetek 70%-ban az objektumok
478
Tan´ acs Attila ´es mtsai
illeszked´ese elfogadhat´ o. Mint ´altal´ aban a ter¨ ulet-alap´ u m´odszerek, a mi megk¨ozel´ıt´es¨ unk is ´erz´ekeny a hi´anyz´ o t´erfogatr´eszekre. 1 − 2%-os degrad´ aci´ os szint ´ felett az eredm´enyek megb´ızhatatlann´ a v´alnak. Eszrevehetj¨ uk azt is, hogy mivel az algebrai hiba magasabb degrad´ aci´ os szint eset´en jelent˝ osen n¨ ovekedhet, t¨ obb ¨ kezd˝ o orient´ aci´ o vizsg´alat´ara van sz¨ uks´eg, ami megn¨oveli a sz´am´ıt´asi id˝ot. Osszefoglal´ ask´ent elmondhatjuk, hogy a m´odszer¨ unk rendszerint j´ol teljes´ıt, am´ıg az objektumunk geometriai momentumai nem v´altoznak meg nagym´ert´ekben a degrad´ aci´ o hat´ as´ ara. 4.3.
¨ Osszehasonl´ ıt´ as a k¨ olcs¨ on¨ os inform´ aci´ otartalmon alapul´ o m´ odszerrel
Az eredm´enyeinket ¨ osszehasonl´ıtottuk egy klasszikus k´epponthasonl´os´agon alapul´ o m´odszer´evel, amely a k´epek k¨olcs¨on¨os inform´aci´ otartalm´an (mutual information – MI) alapul ´es egy t¨ obbfelbont´ as´ u piramis reprezent´aci´ ot haszn´al fel [3]. Mivel az MI m´odszer ´ altal´ aban megk¨ oveteli a keres´es optimumhoz k¨ozeli ind´ıt´ as´ at, a legalacsonyabb piramis szinten ugyanazt a 27 kezd˝o poz´ıci´ot haszn´ altuk, amit a mi m´odszer¨ unk eset´en is. Az ´ıgy kapott optim´ alis eredm´eny ker¨ ult tov´abbad´ asra a magasabb piramis szintekre, ott m´ar nem t¨ ort´ent keres´es t¨ obb ir´ anyb´ ol. 200 merev-test regisztr´aci´ os probl´em´ at figyelembe v´eve a m´odszer¨ unk egy´ertelm˝ uen fel¨ ulm´ ulja az MI m´odszert. Az MI m´odszer ´atlagos sz´am´ıt´asi ideje 2 perc k¨or¨ uli, ¨ osszehasonl´ıtva a mi m´odszer¨ unk p´ ar m´asodperces id˝oig´eny´evel. A δ hiba medi´ anja 0.42 az MI m´odszer eset´en, m´ıg 0.05 a mi m´odszer¨ unkn´el. Tov´abb´a, az esetek 40%-ban az MI m´odszer elfogadhatatlanul nagy regisztr´aci´ os hib´ at produk´ alt (vagyis δ > 10%), m´ıg a mi m´odszer¨ unk minden esetben kiv´ al´o eredm´enyt ´ert el (a maxim´ alis δ hiba ´ert´eke 1.14% volt). 4.4.
Tesztel´ es val´ os CT k´ epeken
M´ odszer¨ unket val´ os orvosi k´epekb˝ ol kinyert objektumokon is tesztelt¨ uk, amelyhez ugyanazon szem´elyr˝ ol k¨ ul¨onb¨ oz˝o id˝opontokban k´esz¨ ult medence-k¨ orny´eki CT k´epeket haszn´altunk fel. A CT k´epek t´erbeli felbont´ asa 0.8×0.8×5 mm volt, az ´ıgy szegment´ alt objektumok 400–500 ezer k´eppontot tartalmaztak. A csont r´egi´ ok k¨ usz¨ ob¨ol´essel, majd a sz¨ uks´egtelen r´eszek (pl. b´elrendszerben l´athat´o kontrasztanyagot tartalmaz´ o ter¨ uletek) elt´ avol´ıt´as´aval ker¨ ultek meghat´aroz´asra. Nagy kih´ıv´ ast jelentett a gyenge t´erbeli felbont´ as, a nagym´ert´ek˝ u szegment´ al´ asi hib´ ak jelenl´ete, valamint a combcsont fels˝o r´esz´enek medencecsonthoz viszony´ıtott elt´er˝ o poz´ıci´oja. A CT k´epalkot´as biztos´ıtja, hogy a szegment´ alt objektumok orient´ aci´ oj´ aban nagy elt´er´es nincs, ´ıgy elegend˝o volt csak egyetlen keres´esi kezd˝ opoz´ıci´ot (az identikus transzform´ aci´ onak megfelel˝ot) figyelembe venni. A csontok alakja ´es m´erete a vizsg´alatok ideje alatt nem v´altozik, emiatt a m´odszer¨ unkben a merev-test megszor´ıt´ast alkalmaztuk. Az egyenletrendszer elk´esz´ıt´ese f´el m´asodpercet, a megold´asa 0.2 m´asodpercet ig´enyelt. Vizu´alis ellen˝ orz´es alapj´ an a kapott regisztr´aci´ os erem´eny megfelel˝o volt (l´asd a 3. ´abr´ at).
3D objektumok line´ aris deform´ aci´ oinak becsl´ese
479
3. ´ abra: Val´ os CT adatb´ ol sz´ armaz´ o objektumok illeszt´ese: egym´ asra helyezett csontfelsz´ın-modellek (bal oldal), ´es a regisztr´ alt sablon objektum s´ arga sz´ınnel jel¨ olt csont k¨ orvonala a megfigyelt k´epre vet´ıtve (jobb oldal).
5.
¨ Osszegz´ es
Ebben a cikkben egy olyan regisztr´aci´ os m´odszert javasoltunk, amely k´epes 3D objektumok k¨oz¨ott t¨ obbf´ele t´ıpus´ u line´aris deform´ aci´ o becsl´es´ere. A megold´ast egy polinom egyenletrendszer megold´as´aval kapjuk meg. Az egyenletrendszer fel´ep´ıt´es´enek id˝okomplexit´ asa line´aris. A legkisebb n´egyzetes ´ertelemben optim´alis megold´as a kezdeti param´eterek megfelel˝o v´alaszt´as´aval kontroll´alhat´o, id˝oig´enye f¨ uggetlen az adat m´eret´et˝ol, ´ıgy nagy m´eret˝ u adatok regisztr´aci´ os probl´em´ aja gyorsan ´es hat´ekonyan oldhat´ o meg az alkalmaz´as´aval. A m´odszer¨ unk megfelel˝o m´ert´ekben robusztusnak bizonyult t¨ obbf´ele hib´aval szemben. A szintetikus ki´ert´ekel´es meger˝os´ıtette a k´eppont lefedetts´egi adatok felhaszn´al´as´aval kapcsolatos elm´eleti eredm´enyeket, vagyis ezen inform´aci´ o felhaszn´al´as´aval a regisztr´ aci´ o pontoss´ aga n¨ ovelhet˝o.
K¨ osz¨ onetnyilv´ an´ıt´ as A szegedi szerz˝ ok munk´ aj´ at az OTKA K75637 sz´am´ u p´ aly´azat t´ amogatta. A ¨ ´ munk´ at r´eszben t´ amogatta a Magyar Nemzeti Fejleszt´esi Ugyn¨ oks´eg TAMOP4.2.2/08/1/2008-0008 programja. N. Sladoje ´es J. Lindblad munk´ aj´ at anyagilag t´ amogatta a Szerb K¨ozt´ arsas´ag Tudom´anyos Miniszt´eriuma az ON144018 ´es ON144029 projekteken kereszt¨ ul. K¨ osz¨ onetet mondunk Niku Corne´anak, aki a szintetikus k´epek egy r´esz´et ´ amnak ´es Dr. Palk´o Andr´ biztos´ıtotta sz´ amunkra, valamint Dr. Per´enyi Ad´ as professzor u ´rnak a CT vizsg´alatok ¨osszegy˝ ujt´es´e´ert.
480
Tan´ acs Attila ´es mtsai
Irodalom 1. B. Zitov´ a and J. Flusser, “Image registration methods: A survey,” Image Vision Comput., vol. 21, no. 11, pp. 977–1000, 2003. 2. 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. 3. J.P.W. Pluim, J.B.A. Maintz, and M.A. Viergever, “Mutual-information-based registration of medical images: a survey,” Medical Imaging, vol. 22, no. 8, pp. 986–1004, 2003. 4. G. Burel, H. Henocq, and J.-Y. Catros, “Registration of 3D objects using linear algebra,” in CVRMed, 1995, pp. 252–256. 5. A. Tan´ acs, C. Domokos, N. Sladoje, J. Lindblad, and Z. Kato, “Recovering affine deformations of fuzzy shapes,” in Proceedings of SCIA. 2009, vol. 5575 of LNCS, pp. 735–744, Springer. 6. C. Domokos and Z. Kato, “Parametric estimation of affine deformations of planar shapes,” Pattern Recognition, vol. 43, no. 3, pp. 569–578, 2010. 7. N. Sladoje and J. Lindblad, “Estimation of moments of digitized objects with fuzzy borders,” in Proceedings of ICIAP. 2005, vol. 3617 of LNCS, pp. 188–195, Springer. 8. N. Sladoje and J. Lindblad, “Pixel coverage segmentation for improved feature estimation,” in Proceedings of ICIAP. 2009, vol. 5716 of LNCS, pp. 929–938, Springer.
