Szegedi Tudom´ anyegyetem Informatika Doktori Iskola
Bin´ aris k´ epek geometriai ´ es vizu´ alis helyre´ all´ıt´ asa
PhD ´ertekez´es t´ezisei
N´ emeth J´ ozsef
T´emavezet˝ ok: Dr. Csirik J´ anos Dr. Kat´ o Zolt´ an
Szeged 2015
Bevezet´ es A bin´ aris k´epek, melyeken csak k´et k¨ ul¨ onb¨ oz˝ o intenzit´ as´ert´ek szerepel, fontos szerepet j´ atszanak a k´epfeldolgoz´ as ter¨ ulet´en, mivel 1. sok objektum k´epe alapj´ aban v´eve bin´ aris, pl. dokumentum k´epek, kresz t´ abl´ ak, csontok vagy implant´ atumok a r¨ ontgen-felv´eteleken, 2. a legt¨ obb k´epfeldolgoz´ asi elj´ ar´ as sor´ an keletkeznek bin´ aris k´epek, szegment´ al´ as u ´tj´ an. Sok esetben az az inform´ aci´ o, hogy a k´ep amellyel dolgozunk bin´ aris seg´ıthet a pontosabb eredm´eny el´er´es´eben, hisz lesz˝ uk´ıti a lehets´eges megold´ asok halmaz´ at. P´eld´ aul, az u ´gynevezett line´ aris inverz probl´em´ ak, mint amilyen a tomogr´ afia vagy a dekonvol´ uci´ o, a legt¨ obb esetben aluldefini´ altak, ´ıgy t¨ obb lehets´eges megold´ asuk van. Ha tudjuk, hogy a keresett megold´ as bin´ aris, lesz˝ uk´ıthetj¨ uk a keres´esi teret, ez´ert p´eld´ aul tomogr´ afia eset´en a bin´ aris k´epek ´ altal´ aban kevesebb vet¨ uletb˝ ol is helyre´ all´ıthat´ oak. Sok esetben azonban az text´ ur´ azotts´ ag hi´ anya neh´ezz´e is teheti a bin´ aris k´epekkel val´ o munk´ at. Az ´ altal´ anos regisztr´ aci´ os m´ odszerek p´eld´ aul gyakran pont-megfeleltet´esekb˝ ol dolgoznak, ´es ezeket a pontp´ arokat ´ altal´ aban a pontok k¨ or¨ ul jellemz˝ o intenzit´ as´ert´ek mint´ azatok alapj´ an nyerik ki. Bin´ aris k´epek eset´en ezek a m´ odszerek ´ altal´ aban nem tudnak megfelel˝ o sz´ am´ u pont-megfeleltet´est el˝ o´ all´ıtani. M´ asr´eszr˝ ol azonban bin´ aris k´epek eset´en a k´epek k¨ oz¨ otti intenzit´ as´ert´ek v´ altoz´ as nem l´ep fel zavar´ o t´enyez˝ ok´ent. ´Igy t¨ obb m´ odszert is kidolgoztak bin´ aris k´epek regisztr´ al´ as´ ara, melyek csak az alakzatok pont-koordin´ at´ ait, ´es azokb´ ol sz´ amolt statisztik´ akat haszn´ alj´ ak a k´epek illeszt´es´ehez. Ez a t´ezis o ¨sszefoglalja a szerz˝ o bin´ aris k´epek geometriai ´es vizu´ alis helyre´ all´ıt´ as´ aval kapcsolatos eredm´enyeit. A 1. t´ abl´ azat mutatja az egyes t´ezispontok ´es a publik´ aci´ ok kapcsolat´ at. A III. t´ezispont s´ıkhomogr´ afi´ ara vonatkoz´ o eredm´enyei a [13] munk´ aban is be lettek mutatva.
I. II. III. IV.
[9] •
[10]
[12]
[11]
[4]
•
•
•
[8]
• •
1. t´ abl´ azat: A t´ezispontok ´es a publik´ aci´ ok kapcsolata.
I. Diszkr´ et tomogr´ afia ismeretlen intenzit´ as ´ ert´ ekekkel Bemutatunk egy bin´ aris tomogr´ afiai m´ odszert, amely magasabb fok´ u statisztik´ an alapul´ o n diszkretiz´ aci´ os tagot haszn´ al. A h × w m´eret˝ u digit´ alis k´epet az x ∈ {c1 , c2 } oszlopvek1
torral reprezent´ aljuk, ahol n = hw a pixelek sz´ ama, c1 ´es c2 pedig az el˝ ot´erhez (objektumhoz) ´es a h´ att´erhez tartoz´ o intenzit´ as´ert´ekek. Tegy¨ uk fel, hogy a vet¨ uleteket k k¨ ul¨ onb¨ oz˝ o sz¨ ogb˝ ol k´epezz¨ uk, ´es legyen li a m´ert vet¨ ulet´ert´ekek sz´ ama az i. ir´ anyban. Az o ¨sszes P uleti ´ert´ekek vet¨ uleti ´ert´eket a p ∈ Rm oszlopvektor reprezent´ alja, ahol m = ki=1 li vet¨ sz´ ama. A vet¨ uletk´epz´esi elj´ ar´ as le´ırhat´ o a k¨ ovetkez˝ o line´ aris egyenletrendszerrel: Wx = p,
(1)
ahol a W ∈ Rm×n m´ atrix ´ırja le a vet¨ uleti geometri´ at. A leggyakrabban haszn´ alt geometria t´ıpusok a tomogr´ afi´ aban ´es a bin´ aris tomogr´ afi´ aban a p´ arhuzamos-nyal´ ab, a legyez˝ o-nyal´ ab ´es a k´ up-nyal´ ab. A probl´ema folytonos v´ altozat´ at tekintj¨ uk. A rekonstrukci´ ot az al´ abbi c´elf¨ uggv´eny minimaliz´ al´ as´ aval v´egezz¨ uk: E(x, α, µ) = F (x) + λS(x) + µD(x, α),
(2)
amely h´ arom elv´ ar´ ast fejez ki a megold´ assal kapcsolatban. Az els˝ o, u ´gynevezett adatmegfelel´esi tag azt fejezi ki, hogy a megold´ asnak ki kell el´eg´ıtenie a vet¨ uleteket: F (x) =
1 kWx − pk22 . 2
(3)
Ezt a tagot gyakran haszn´ alj´ ak a diszkr´et tomogr´ afi´ aban, hogy kifejezz´ek, hogy a megold´ as vet¨ uleteinek nem szabad nagyon elt´erni¨ uk a bemeneti p vet¨ uletekt˝ ol. Mint ´ altal´ aban a line´ aris inverz probl´em´ ak eset´en, a (3) f¨ uggv´eny minimaliz´ al´ asa elfajult megold´ asokhoz vezetne a zajos vet¨ uletek miatt. Ez´ert regulariz´ aci´ ora van sz¨ uks´eg. Ezen c´elb´ ol a c´elf¨ uggv´eny tartalmaz egy simas´ agi tagot: 1 S(x) = kLxk22 , (4) 2 ahol L a Laplace regulariz´ aci´ os m´ atrix, azaz Lx ugyanazt az eredm´enyt adja, mint a 2dimenzi´ os konvol´ uci´ o a Laplace-sz˝ ur˝ ovel. Ez a tag b¨ unteti a t´ ul nagy m´ asodik deriv´ altakkal rendelkez˝ o megold´ asokat, de megengedi az ´elek kialakul´ as´ at. Ennek λ param´eter´et nagyobbra ´ all´ıtva kik´enyszer´ıthetj¨ uk, hogy a megold´ ason ¨ osszef¨ ugg˝ o ter¨ uletek alakuljanak ki, akkor is, ha a bemeneti vet¨ uletek zajosak. Csak az adat-megfelel´esi ´es a simas´ agi tagokat haszn´ alva a c´elf¨ uggv´eny F (x) + λS(x) konvex, ´es megold´ asa egy folytonos rekonstrukci´ ot ny´ ujt. A bin´ aris megold´ asokat a diszkretiz´ aci´ os tag ´ırja el˝ o: D(x, α) = n
kx − α1n k44 − 1, (kx − α1n k22 )2
(5)
ahol α a diszkretiz´ aci´ os param´eter, 1n jel¨ oli az n-hossz´ u oszlopvektort melynek minden Pn p 1/p eleme 1, ´es kxkp = x jel¨ o li az ´ a ltal´ a nos vektor norm´ at. Ezt a f¨ uggv´enyt olyan i=1 i bin´ aris k´epek minimaliz´ alj´ ak, melyeken a k´et intenzit´ as´ert´ek ´ atlaga α, azaz l´etezik d, amelyre |xi −α| = d, minden i = 1, . . . n-re. Ilyen esetekben az ´ert´eke 0, m´ıg a maximum´ at, melynek 2
i=0 i = 75 i = 98 i = 119 i = 174 i = 224 µ=0 µ ≈ 414.8 µ ≈ 1.3×103 µ ≈ 3.7×103 µ ≈ 5.5×104 µ ≈ 6×105 α ˆ = 0.4205 α ˆ = 0.5239 α ˆ = 0.4667 α ˆ = 0.4706 α ˆ = 0.4869 α ˆ = 0.4970 D(ˆ x, α) ˆ = 1.11 D(ˆ x, α) ˆ = 0.74 D(ˆ x, α) ˆ = 0.31 D(ˆ x, α) ˆ = 0.15 D(ˆ x, α) ˆ = 0.03 D(ˆ x, α) ˆ = 0.00
1. ´ abra: A javasolt m´ odszer illusztr´ al´ asa. Az ´ abra oszlopai k¨ ul¨ onb¨ oz˝ o iter´ aci´ osz´ am ut´ ani megold´ asokat mutatnak, 5 vet¨ uletet haszn´ alva. Az els˝ o sorban a megold´ as 3-dimenzi´ os ´ abr´ azol´ asa l´ athat´ o, amelyen v´ızszintes s´ık jelzi a becs¨ ult α ˆ k¨ oz´epszintet. A m´ asodik ´es harmadik sorok a megold´ asokat ´es azok α-k¨ ˆ usz¨ ob¨ olt v´ altozatait mutatj´ ak. A k´epek alatt a megfelel˝ o µ diszkretiz´ aci´ os s´ ulyok α ˆ k¨ oz´epszintek ´es D(ˆ x, α) ˆ diszkretiz´ aci´ os ´ert´ekek tal´ alhat´ oak. ´ert´eke n − 1, akkor veszi fel, ha a k´epen egy kiv´etellel minden pixel ´ert´eke α. ´Igy ez egy korl´ atos f¨ uggv´eny, ´es k´etszer folytonosan differenci´ alhat´ o, kiv´eve x = α1n -ben, ´ıgy standard gradiens alap´ u optimaliz´ aci´ os m´ odszerek k¨ ozvetlen¨ ul alkalmazhat´ oak a minimaliz´ al´ as´ ara. D(x, α) l´enyeg´eben egy standardiz´ alt momentum (kurt´ ozis), azzal a k¨ ul¨ onbs´eggel, hogy a m´ asod-, ´es negyedfok´ u tagokat α-val normaliz´ aljuk, az elemek ´ atlaga helyett. A diszkretiz´ aci´ os tag s´ uly´ anak el´eg nagy ´ert´eket v´ alasztva l´enyeg´eben csak bin´ aris megold´ asokat enged´elyez¨ unk. A k¨ ovetkez˝ o t´etel kimondja, hogy tetsz˝ oleges ξ > 0-hoz l´etezik egy megfelel˝ oen nagy µ u ´gy, hogy a diszkretiz´ aci´ os szint (azaz a diszkretiz´ aci´ os tag ´ert´eke) maximum ξ a c´elf¨ uggv´eny minimumhely´en. 1. T´ etel. B´ armely ξ > 0 eset´en l´etezik µ(ξ) ∈ R u ´gy, hogy ha µ ≥ µ(ξ) ´es (ˆ x, α) ˆ = arg min E(x, α, µ), akkor D(ˆ x, α) ˆ ≤ ξ. x,α
´Igy a rekonstrukci´ os probl´ema adott ξ > 0 ´es µ ˆ ≥ µ(ξ) eset´en a k¨ ovetkez˝ ok´eppen defini´ alhat´ o: (ˆ x, α) ˆ = arg min E(x, α, µ ˆ).
(6)
x,α
Bin´ aris dekonvol´ uci´ o eset´ere kor´ abban javasolt´ ak [6], hogy a k¨ oz´ep´ert´eket ´es a megold´ ast egyszerre, ugyanabban a gradiens alap´ u optimaliz´ al´ o elj´ ar´ asban hat´ arozz´ ak meg. 3
2. ´ abra: Els˝ o oszlop: A g´ aznyom´ as szab´ alyoz´ o homog´en r´esz´enek n´egy vet¨ ulete a 18b´ ol. T¨ obbi oszlop: A bemutatott m´ odszer rekontrukci´ os eredm´enyei. A bemutatott eredm´enyeken szerepl˝ o szeletek elhelyezked´es´et az els˝ o vet¨ uleti k´epen jel¨ olt¨ uk. Mi u ´gy tal´ altuk, hogy a javasolt m´ odszer eset´en hat´ekonyabb, ha a k¨ oz´ep´ert´eket minden iter´ aci´ os l´ep´esben k¨ ozvetlen¨ ul hat´ arozzuk meg az aktu´ alis megold´ ashoz, a diszkretiz´ aci´ os f¨ uggv´eny minimumhely´enek meghat´ aroz´ as´ aval. Ez´ert a k¨ ovetkez˝ o fokozatos optimaliz´ al´ asi m´ odszert javasoljuk. Kiindulva egy kezdeti folytonos rekonstrukci´ ob´ ol, melyet a c´elf¨ uggv´eny diszkretiz´ aci´ os tag n´elk¨ uli minimaliz´ al´ as´ aval kapunk, minden iter´ aci´ os l´ep´esben ˆ megold´ 1. Meghat´ arozzuk az α ˆ k¨ oz´epszintet az aktu´ alis x ashoz. 2. N¨ ovelj¨ uk a µ diszkretiz´ aci´ os s´ ulyt. ˆ megold´ 3. Finom´ıtjuk az x ast, azaz lok´ alisan minimaliz´ aljuk a c´elf¨ uggv´enyt az u ´j α ˆ ´es µ param´eterekkel. A m´ odszer fokozatosan k´enyszer´ıti ki a bin´ aris megold´ asokat, m´ıg iterat´ıvan k¨ ozel´ıti a k¨ oz´epszintet (l´ asd 1. ´ abra). Fontos megjegyezni, hogy a m´ odszer nem ´ıg´enyli a h´ att´er ´es az objektum intenzit´ as ´ert´ekeinek becsl´es´et, sem a k¨ ozb¨ uls˝ o megold´ asok k¨ usz¨ ob¨ ol´es´et. Megmutattuk, hogy a c´elf¨ uggv´eny Lipschitz-folytonos, ez´ert hat´ekonyan minimaliz´ alhat´ o gradiens alap´ u optimaliz´ al´ o m´ odszerekkel. Bemutattuk, hogy a m´ odszert lehet u ´gy implement´ alni, hogy a rekonstrukci´ os eredm´eny f¨ uggetlen legyen a k´epen l´ev˝ o intenzit´ as´ert´ekekt˝ ol. A bemutatott m´ odszer tesztelve lett egy szintetikus adathalmazon. A vizsg´ alatok meg¨ mutatt´ ak, hogy az algoritmus robusztus a vet¨ uleti zaj er˝ oss´eg´evel szemben. Osszehasonl´ ıtva a PDM-DART m´ odszerrel [15], az algoritmusunk versenyk´epesnek bizonyult, m´ıg egy m´ asik, konvex-programoz´ asi m´ odszert egy´ertelm˝ uen fel¨ ulm´ ult. A m´ odszert sikeresen alkalmaztuk val´ os adatokon, egy g´ aznyom´ as-szab´ alyoz´ o homog´en r´eszenek helyre´ all´ıt´ as´ ara 18 vet¨ uletb˝ ol (l´ asd 2. ´ abra). 4
A szerz˝ o hozz´ aj´ arul´ asa az eredm´ enyekhez A szerz˝ o kidolgozott egy u ´j, magasabb fok´ u statisztik´ at haszn´ al´ o bin´ aris tomogr´ afiai technik´ at, amely azokban az esetekben is alkalmazat´ o, amikor a k´epek intenzit´ as´ert´ekei ismeretlenek. Egy olyan c´elf¨ uggv´enyt javasol, amelyben egy diszkretiz´ aci´ os tag ´ırja el˝ o a bin´ aris megold´ asokat. A c´elf¨ uggv´eny minimaliz´ al´ as´ ahoz egy fokozatos optimaliz´ al´ asi strat´egi´ at mutat be, amelyben a diszkretiz´ aci´ os tag s´ ulya n¨ ovekszik, ´ıgy fokozatosan k´enyszer´ıti ki a bin´ aris megold´ asokat. Az intenizt´ as´ert´ekek k¨ oz´epszintj´enek becsl´ese a diszkretiz´ aci´ os tag minimaliz´ al´ as´ aval t¨ ort´enik. A szerz˝ o megvizsg´ alta a m´ odszer konvergencia-tulajdons´ agait ´es megmutatja hogy az algoritmus viselked´ese f¨ uggetlen az intenzit´ as´ert´ekekt˝ ol. Bemutatja a m´ odszer robosztuss´ ag´ at a k¨ ul¨ onb¨ oz˝ o m´ert´ek˝ u vet¨ uleti zajokkal szemben. A m´ odszert o ¨sszehasonl´ıtotta m´ as korszer˝ u m´ odszerekkel ´es megmutatta, hogy az algoritmus j´ o alternat´ıv´ at jelent. Sikeresen haszn´ alta a m´ odszert val´ os adatokon.
II. Bin´ aris alakzatok dekonvol´ uci´ oja diszkr´ et tomogr´ afia seg´ıts´ eg´ evel C´elunk helyre´ all´ıtani egy bin´ aris f ∈ Ru×v k´epet, az elmos´ odott ´es zajos g ∈ Ru×v bin´ aris k´epb˝ ol. Az elmos´ od´ ast a k´ep ´es az elmos´ od´ ast le´ır´ o f¨ uggv´eny (point spread function - PSF) konvol´ uci´ oja adja, teh´ at: g = h ∗ ∗f + n,
(7)
ahol h ∈ Rp×q a PSF, ∗∗ jel¨ oli a 2-dimenzi´ os konvol´ uci´ ot ´es n ∈ Ru×v a zaj. Felt´etelezz¨ uk, hogy az elmos´ od´ ast le´ır´ o h f¨ uggv´eny ismert. C´elunk az eredeti bin´ aris k´ep meghat´ aroz´ asa b ∈ {0, 1}u×v alakban. Mivel azonban az intenzit´ as´ert´ekek nagys´ agrendje ismeretlen ez´ert bevezet¨ unk egy ismeretlen s sk´ al´ az´ asi egy¨ utthat´ ot a modellbe, teh´ at f = sb. θ ˇ anyb´ ol k´epzett vet¨ ulete. Kihaszn´ aljuk, hogy ha g = h ∗ ∗f Legyen f az f k´ep θ ir´ ˇ ∗ fˇ, ahol ∗ jel¨ akkor gˇ = h oli az 1-dimenzi´ os konvol´ uci´ ot. ´Igy az o ¨sszef¨ ugg´es az eredeti ´es a megfigyelt k´ep vet¨ uletei k¨ oz¨ ott a k¨ ovetkez˝ ok´eppen fejezhet˝ o ki: ˇ ∗ fˇ + n gˇ = h ˇ.
(8)
Egy Ω = {θi |i = 1, . . . , k} ir´ anyhalmaz eset´en a javasolt m´ odszer el˝ osz¨ or helyre´ all´ıtja a fˇθi vet¨ uleteket a gˇθi vet¨ uletekb˝ ol, majd a m´ asodik l´ep´esben rekonstru´ alja az f k´epet a helyre´ all´ıtott vet¨ uletekb˝ ol (l´ asd 3. ´ abra). A konvol´ uci´ o egy line´ aris m˝ uvelet, teh´ at a (8) egyenlet a k¨ ovetkez˝ ok´eppen ´ırhat´ o: gˇ = H fˇ + n ˇ,
(9)
ˇ sz˝ ahol a H m´ atrix ´ırja le a h ur˝ ovel v´egrehajtott konvol´ uci´ ot. Mivel n ˇ ismeretlen, az egyenletrendszer megold´ asa regulariz´ aci´ ot ig´enyel. A Tikhonov-regulariz´ aci´ o standard form´ aja a k¨ ovetkez˝ o: (10) fˇλ = arg minkH fˇ − gˇk22 + λ2 kfˇk22 , fˇ
5
⇒
⇒ ⇑
⇓
3. ´ abra: A bemutatott m´ odszer alapelemei. Els˝ o h´ arom oszlop: az eredeti k´ep, az elmos´ odott k´ep ´es az elmosott-zajos k´ep ´es ezek vet¨ uletei. Negyedik oszlop: a m´ odszer helyre´ all´ıtja a vet¨ uleteket ´es rekonstru´ alja az alakzatot. ahol λ egy pozit´ıv konstans a regulariz´ aci´ os param´eter amely a megold´ as simas´ ag´ at szab´ alyozza. Adott λ eset´en a k¨ ozvetlen megold´ ast a fˇλ = (H T H + λ2 I)−1 H T gˇ
(11)
k´eplet adja, ahol I jel¨ oli a megfelel˝ o m´eret˝ u egys´egm´ atrixot. A regulariz´ aci´ os param´eter megfelel˝ o ´ert´ek´enek meghat´ aroz´ as´ ahoz az L-curve m´ odszert haszn´ altuk, amely a maradv´ any-norm´ aj´ anak ´es a megold´ as-norm´ aj´ anak log-log f¨ uggv´eny´et tekinti k¨ ul¨ onb¨ oz˝ o regulariz´ aci´ os param´eterekre: L = {(log2 kH fˇλ − gˇk22 , log2 kfˇλ k22 ), λ ≥ 0}.
(12)
∗
Az optim´ alis regulariz´ aci´ os param´etert az a λ adja, melyre az L g¨ orbe g¨ orb¨ ulete a maxim´ alis. A megold´ asban jelentkez˝ o esetleges negat´ıv elemek kik¨ usz¨ ob¨ ol´es´ere egy tov´ abbi, ´ altal´ anos Tikhonov regulariz´ aci´ on alapul´ o iterat´ıv elj´ ar´ ast haszn´ altunk, mely fokozatosan elimin´ alja a negat´ıv ´ert´ekeket. aris vet¨ uletekre van sz¨ uks´eg. A diszkr´et tomogr´ afiai rekonstrukci´ ohoz a ˇbθi = fˇθi /s bin´ Az s sk´ alafaktort nem lehet k¨ ozvetlen¨ ul kisz´ am´ıtani, azonban ennek als´ o ´es fels˝ o korl´ atja k¨ onnyen meghat´ arozhat´ o, ´ıgy defini´ alhatjuk a lehets´eges ´ert´ekeinek egy S halmaz´ at. Minden aris k´ep s ∈ S sk´ alafaktorhoz vessz¨ uk a ˇbθi = fˇθi /s vektorokat, mint az ismeretlen b bin´ vet¨ uleteinek becsl´es´et. A v´ızszintes ´es f¨ ugg˝ oleges ˇb0 ´es ˇbπ/2 vet¨ uletekb˝ ol val´ o rekonstrukci´ oval foglalkoztunk. K¨ ozismert, hogy k´et vet¨ ulet legt¨ obbsz¨ or nem elegend˝ o a bin´ aris k´epek helyre´ all´ıt´ as´ ahoz, azaz, adott vet¨ ulet-p´ arnak ´ altal´ aban t¨ obb k´ep is megfelelhet, m´ıg bizonyos esetekben egy k´ep sem el´eg´ıti ki a vet¨ uleteket. Defini´ aljuk a tomogr´ afiai-ekvivalencia halmazt: U = U (ˇb0 , ˇbπ/2 ) = {z ∈ {0, 1}u×v : zˇ0 = ˇb0 , zˇπ/2 = ˇbπ/2 }. 6
(13)
4. ´ abra: Helyre´ all´ıt´ asi eredm´enyek elmos´ odott dokumentum k´epekb˝ ol kinyert karaktereken. Az eredeti k´epek az els˝ o, m´ıg a helyre´ all´ıtott k´epek a m´ asodik sorban l´ athat´ oak.
Hab´ ar ´ altal´ anos esetben |U | > 1, minket az a megold´ as ´erdekel, mely a legjobban hasonl´ıt az eredeti bemeneti k´ephez, mint modellhez. Egy adott modell k´epnek legink´ abb megfelel˝ o megold´ as m´ ar egy´ertelm˝ uen meghat´ arozott. Az m modell k´epet a bemeneti g k´epb˝ ol hozzuk l´etre u ´gy, hogy a zaj sz´ or´ as´ anak (amely a vet¨ uletek helyre´ all´ıt´ asa ut´ an meghat´ arozhat´ o) megfelel˝ o mennyis´eg˝ u zajt t´ avol´ıtunk el. Az az elv´ ar´ as, hogy a zs megold´ asnak hasonl´ıtania kell a modell k´ephez az jelenti, hogy azokon az (x, y) poz´ıci´ okon, ahol z(x, y) = 1 a modellk´epen magas intenzit´ as´ert´ek helyezkedik el. Ez a k¨ ovetkez˝ o minimaliz´ al´ asi probl´emak´ent ´ırhat´ o fel: ! zs = arg min − z∈U
X
z(x, y)m(x, y) .
(14)
x,y
´Igy a rekonstrukci´ os probl´ema visszavezethet˝ o a minim´ alis-k¨ olts´eg˝ u maxim´ alis-folyam probl´em´ ara [1]. Ebben a h´ al´ ozatban a ell´ at´ o (supply) ´es az ig´enyl˝ o (demand) pontok a vet¨ uletek ´ert´ekeit reprezent´ alj´ ak, az ´elek pedig a pixeleket. Minden egyes (x, y) pixelhez tartoz´ o Sx → Ty ´el kapacit´ asa 1, m´ıg k¨ olts´ege −m(x, y). A minim´ alis-k¨ olts´eg˝ u maxim´ alis-folyam polinomi´ alis id˝ oben meghat´ arozhat´ o [14] ´es megadja a zs megold´ as´ at a rekonstrukci´ os probl´em´ anak. A zs (x, y) pixel akkor, ´es csakis akkor kap 1-es ´ert´eket, ha a folyam ´ athalad az Sx → Ty ´elen. A k¨ ul¨ onb¨ oz˝ o s ∈ S sk´ alafaktorokhoz a m´ odszer meghat´ arozza a k¨ ul¨ onb¨ oz˝ o zs rekonstrukci´ okat. Az optim´ alis z megold´ as meghat´ aroz´ as´ ahoz o ¨sszehasonl´ıtunk minden egyes zs megold´ ast a g bemeneti k´eppel ´es kiv´ alasztjuk a legkisebb-n´egyzetes ´ertelemben vett legk¨ ozelebbit. A m´ odszer vizsg´ alat´ ahoz egy szintetikus k´epi adatb´ azist hoztunk l´etre, amely 62 alfanumerikus karakterb˝ ol (59 × 59 pixel m´eretben) ´es azok 1550 eltorz´ıtott v´ altozat´ ab´ ol ´ allt. Minden k´epet k¨ ul¨ onb¨ oz˝ o er˝ oss´eg˝ u Gauss-sz˝ ur˝ ovel sim´ıtottunk ´es k¨ ul¨ onb¨ oz˝ o er˝ oss´eg˝ u ¨ feh´er-zajt adtunk hozz´ ajuk. Osszehasonl´ıt´ o teszt mutatja, hogy a m´ odszer sok esetben jobb eredm´enyeket ´er el mint a sz´eles k¨ orben haszn´ alt Lucy-Richardson elj´ ar´ as. A m´ odszert tesztelt¨ uk val´ os kamer´ aval k´esz´ıtett, ´eletlen karakterk´epeken, n´eh´ any eredm´eny megtal´ alhat´ oa 4. ´ abr´ an. 7
A szerz˝ o hozz´ aj´ arul´ asa az eredm´ enyekhez A szerz˝ o egy bin´ aris tomogr´ afia alap´ u bin´ aris k´ephelyre´ all´ıt´ asi m´ odszert javasol. Az elmos´ odott k´epek vet¨ uleteit Tikhonov regulariz´ aci´ o seg´ıts´eg´evel ´ all´ıtja helyre. A megfelel˝ o regulariz´ aci´ os param´eter kiv´ alaszt´ as´ ahoz az L-curve m´ odszert javasolja. A helyre´ all´ıtott vet¨ uletekb˝ ol egy maximum-folyam-alap´ u bin´ aris tomogr´ afiai m´ odszerrel rekonstru´ alja az ¨ alakzatot. Osszehasonl´ ıt´ o teszt mutatja, hogy a m´ odszer sok esetben jobb eredm´enyeket ´er el mint egy m´ asik, sz´elesk¨ orben haszn´ alt m´ odszer. A szerz˝ o bemutat val´ os kamer´ aval k´esz´ıtett, elmos´ odott k´epeken el´ert eredm´enyeket is.
III. Bin´ aris alakzatok nemline´ aris regisztr´ aci´ oja Bemutatunk egy ´ altal´ anos bin´ aris regisztr´ aci´ os m´ odszert. Legyen ϕ : R2 → R2 egy tetsz˝ oleges diffeomorfizmus, azaz egy differenci´ alhat´ o ´es invert´ alhat´ o transzform´ aci´ o, melynek az inverze is differenci´ alhat´ o. C´elunk meghat´ arozni egy ilyen transzform´ aci´ o param´etereit, mely fed´esbe hozza a bemeneti bin´ aris alakzatokat. Legyenek x = [x1 , x2 ]T ∈ R2 ´es y = [y1 , y2 ]T ∈ R2 egym´ asnak megfelel˝ o pontp´ arok a sablon ´es a megfigyel´es k´epeken. Ekkor y = ϕ(x) ⇔ x = ϕ−1 (y), (15) Ez az o ¨sszef¨ ugg´es ´erv´enyben marad, ha mindk´et oldalon hat egy ω : R2 → Rn f¨ uggv´eny [3, 12, 11]: ω(y) = ω(ϕ(x)) ⇔ ω(x) = ω(ϕ−1 (y)). (16) Mindk´et oldalon integr´ alva a k¨ ovetkez˝ o egyenlethez jutunk: Z Z ω(y)dy = ω(ϕ(x)) |Jϕ (x)| dx. Fo
(17)
Ft
ahol Ft ´es Fo az objektum r´egi´ ok a sablon ´es a megfigyelt alakzatokon, m´ıg |Jϕ | : R2 → R jel¨ oli a transzform´ aci´ o Jacobi-determin´ ans´ at: ∂ϕ1 ∂ϕ1 ∂x1 ∂x2 (18) |Jϕ (x)| = . ∂ϕ2 ∂ϕ2 ∂x ∂x 1
2
A javasolt m´ odszer alap¨ otlete a regisztr´ aci´ os probl´ema visszavezet´ese megfelel˝ o sz´ am´ u f¨ uggetlen ω f¨ uggv´eny seg´ıts´eg´evel megkonstru´ alt egyenletrendszerre. Mivel egy ω : R2 → Rn (n > 1) f¨ uggv´eny seg´ıts´eg´evel l´etrehozott egyenlet felbonthat´ o n k¨ ul¨ onb¨ oz˝ o egyenletre, minden megszor´ıt´ as n´elk¨ ul feltehetj¨ uk, hogy n = 1. Tegy¨ uk fel, hogy a ϕ transzform´ aci´ onak k param´etere van ´es legyen ωi : R2 → R, (i = 1, . . . , `) a felhaszn´ alt f¨ uggv´enyek halmaza. Az o ¨sszes ismeretlen meghat´ aroz´ as´ ahoz legal´ abb k egyenletre van sz¨ uks´eg¨ unk, teh´ at ` ≥ k. ´Igy a k¨ ovetkez˝ o egyenletrendszerhez jutunk: Z Z ωi (y)dy = ωi ϕ(x) |Jϕ (x)| dx, i = 1, . . . , `, (19) Fo
Ft
8
amelyhez minden egyes ωi f¨ uggv´eny egy egyenlettel j´ arul hozz´ a. Az ωi f¨ uggv´enyek az alakzatok egy-egy sz´ınez´es´enek tekinthet˝ oek, az integr´ alok pedig az ωi f¨ uggv´enyek alakzatok f¨ ol¨ otti t´erfogat´ at adj´ ak. Az egyenletek teh´ at ezen t´erfogatokat hasonl´ıtj´ ak o ¨ssze. Minden egyenlet u ´jabb megszor´ıt´ ast ad, ´es az egyenletrendszer megold´ asa szolg´ altatja a transzform´ aci´ o param´ereinek becsl´es´et. A k¨ ovetkez˝ o transzform´ aci´ os oszt´ alyokat vizsg´ altuk: 1. A s´ıkhomogr´ afia egy projekt´ıv transzform´ aci´ o ugyanannak a s´ıkbeli objektumnak a k´epei k¨ oz¨ ott. Fontos szerepet j´ atszik a sz´ am´ıt´ og´epes l´ at´ as ter¨ ulet´en. 2. A polinom transzform´ aci´ okat gyakran haszn´ alj´ ak m´ as transzform´ aci´ os modellek k¨ ozel´ıt´es´esre. 3. A thin plate spline (TPS) modellt gyakran alkalmazz´ ak ´ altal´ anos deform´ aci´ ok k¨ ozel´ıt´es´ere. A kiugr´ o numerikus ´ert´ekek elker¨ ul´ese ´erdek´eben normaliz´ aci´ ot hajtunk v´egre mind a pixel koordin´ at´ akon, mind a ωi f¨ ugg´enyeken. Ezen c´elb´ ol egyr´eszt mindk´et alakzat koordin´ at´ ait normaliz´ aljuk a [−0.5, 0.5] × [−0.5, 0.5] egys´egn´egyzetbe, m´ asr´esz olyan ωi f¨ uggv´enyeket alkalmazunk, melyek ´ert´ekk´eszlete korl´ atos (p´eld´ aul [−1, 1]). A normaliz´ al´ asok ellen´ere az ωi f¨ ugg´enyek elt´er˝ o karakterisztik´ aja miatt a k¨ ul¨ onb¨ oz˝ o egyenletek k¨ ul¨ onb¨ oz˝ o m´ert´ekben j´ arulhatnak hozz´ a a c´elf¨ ugg´enyhez az egyenletrendszer megold´ asakor. Ez´ert tov´ abbi normaliz´ aci´ ok´ent minden egyenletet√leosztunk egy megfelel˝ o u k¨ or f¨ ol¨ otti inkonstanssal, amit az adott egyenletn´el alkalmazott ωi f¨ uggv´eny 22 sugar´ tegr´ alja ad: Z Ni =
√
|ωi (x)|dx,
(20)
kxk≤ 22
´es ´ıgy a (19) egyenletrendszer normaliz´ alt v´ altozata: R R ω ϕ(x) |Jϕ (x)| dx ω (y)dy Ft i Fo i = , Ni Ni
i = 1, . . . , `.
(21)
A (21) egyenletrendszert folytonosan vezett¨ uk le, a gyakorlatban azonban v´eges felbont´ as´ u digit´ alis k´epekkel dolgozunk. Ez´ert az integr´ alokat k¨ ozel´ıten¨ unk kell v´eges o ¨sszegekkel az el˝ ot´erpixelek felett. Jel¨ olje az Ft and Fo folytonos halmazokhoz tartoz´ o v´eges pixel halmazokat Ft ´es Fo . Ekkor a (21) k¨ ozel´ıhet˝ o a k¨ ovetkez˝ o egyenletrendszerrel: 1 X 1 X ωi (y) = ωi ϕ(x) |Jϕ (x)| , Ni y∈F Ni x∈F o
i = 1, . . . , `.
(22)
t
A keresett transzform´ aci´ os param´etereket az egyenletrendszer megold´ asa adja. B´ ar az egyenletek nemline´ arisak, ahogy az eredm´enyek mutatj´ ak, hogy az egyenletrendszer hat´ekonyan megoldhat´ o a Levenberg-Marquardt algoritmussal [7]. S´ıkhomogr´ afia eset´eben az egyenletek tov´ abbi h´ arom form´ aban is fel´ırhat´ oak az inverz transzform´ aci´ o seg´ıts´eg´evel. 9
5. ´ abra: Regisztr´ aci´ os eredm´enyek be´ep´ıt´esi jeleken. A fels˝ o sorban a sablon k´epk´ent, az als´ o sorban a megfigyel´es k´epk´ent haszn´ alt felv´etelek l´ athat´ oak. A bal oldali k´epp´ ar a m´ asodik oszlopban szerepl˝ o k´epek szegment´ alt v´ altozatai. A regisztr´ alt k´epek kont´ urjait r´ avet´ıtettem a megfigyel´es k´epekre. (A k´epeket a ContiTech Fluid Automotive Hung´ aria Kft. bocs´ ajtotta rendelkez´esemre.)
Ezek az egyenletek tov´ abbi megszor´ıt´ asokat jelentenek, ´ıgy seg´ıtve az optimum megtal´ al´ as´ at. A m´ odszer hat´ekonys´ ag´ at megvizsg´ altuk k¨ ul¨ onb¨ oz˝ o {ωi } f¨ uggv´eny halmazok alkalmaz´ asa eset´en. Tesztelt¨ unk p´eld´ aul hatv´ any, polinom ´es trigonometrikus f¨ uggv´eny halmazokat. Az eredm´enyek alapj´ an alacsony fok´ u polinom f¨ uggv´enyeket javaslunk, melyek sz´ am´ıt´ asi hat´ekonys´ ag szempontj´ ab´ ol is el˝ ony¨ osek. A s´ıkhomogr´ afia eset´eben megmutattuk, hogy az algoritmus hat´ekonys´ aga jav´ıthat´ o, ha a transzform´ aci´ o Taylor sorba fejtett v´ altozat´ an alkalmazzuk a keretrendszert. A javasolt m´ odszer hat´ekonys´ ag´ at nagy, szintetikus k´epi adatb´ azison tesztelt¨ uk mindegyik transzform´ aci´ os modell eset´en. Az eredm´enyeket o ¨sszehasonl´ıtottuk a Shape Context [2] m´ odszer ´ altal el´ert eredm´enyekkel, m´ odszer¨ unkkel pontosabb eredm´enyeket ´ert¨ unk el. Vizsg´ altuk a m´ odszer robosztuss´ ag´ at 4 k¨ ul¨ onb¨ oz˝ o t´ıpus´ u szegment´ al´ asi hib´ aval szemben a s´ıkhomogr´ afia transzform´ aci´ o eset´en. Az eredm´enyek alapj´ an a javasolt m´ odszer robosztus azokban az esetekben, amikor a szegment´ al´ asi hib´ ak egyenletesen oszlanak el az alakzatokon. Azokban az esetekben amikor a szegment´ al´ asi hiba nagy, o ¨sszef¨ ugg˝ o r´egi´ ob´ ol ´ allt, a m´ odszer kev´esb´e pontos eredm´enyeket ad a Shape Context eredm´enyeihez k´epest. A bemutatott m´ odszert alkalmaztuk k¨ ul¨ onb¨ oz˝ o val´ os alkalmaz´ asi ter¨ uleteken, mint p´eld´ aul k´ezzel ´ırott karakterek (TPS modell) vagy KRESZ t´ abl´ ak regisztr´ aci´ oj´ ara (s´ıkhomogr´ afia), ´es egy ipari min˝ os´eg ellen˝ orz´esi probl´em´ ara (probl´ema specifikus transzform´ aci´ os modell, l´ asd 5. ´ abra).
A szerz˝ o hozz´ aj´ arul´ asa az eredm´ enyekhez A szerz˝ o bin´ aris alakzatok nemline´ aris regisztr´ aci´ oj´ aval foglalkozik. Egy ´ altal´ anos regisztr´ aci´ os keretrendszert haszn´ al, amely a regisztr´ aci´ os probl´em´ at egy egyenletrend10
szer megold´ as´ ara vezeti vissza. A keretrendszert k¨ ul¨ onb¨ oz˝ o nemline´ aris transzform´ aci´ os oszt´ alyok eset´eben is alkalmazza, mint p´eld´ aul s´ıkhomogr´ afia, polinomi´ alis transzform´ aci´ ok ´es thin-plate-spline transzform´ aci´ o. Bemutatja az implement´ aci´ os r´eszleteket ´es azt, hogy az egyenletek oda-vissza t¨ ort´en˝ o fel´ır´ as´ aval hogyan lehet jav´ıtani a m´ odszer eredm´enyein. A s´ıkhomogr´ afia eset´eben megmutatja, hogy az algoritmus hat´ekonys´ aga jav´ıthat´ o, ha a transzform´ aci´ o Taylor sorba fejtett v´ altozat´ an alkalmazzuk a keretrendszert. K¨ ul¨ onb¨ oz˝ o ω f¨ uggv´eny halmazokat vizsg´ al az egyenletrendszer fel´ır´ as´ ahoz, ´es o ¨sszehasonl´ıtja o ˝ket. A szerz˝ o az egyenletek normaliz´ al´ as´ aval ´eri el, hogy azok azonos m´ odon j´ aruljanak hozz´ a a c´elf¨ uggv´enyhez. A szerz˝ oo ¨sszehasonl´ıtja a m´ odszert m´ as korszer˝ u technik´ akkal szintetikus adatokon ´es megvizsg´ alja a javasolt algoritmus robosztuss´ ag´ at a szegment´ al´ asi hib´ akkal szemben. A szerz˝ o bemutatja a m´ odszer eredm´enyeit t¨ obb val´ os probl´ema eset´en, mint p´eld´ aul r¨ ontgenk´epek vagy KRESZ t´ abl´ ak illeszt´ese.
IV. Bin´ aris seg´ıts´ eg´ evel
alakzatok
projekt´ıv
regisztr´ aci´ oja
affin
invari´ ansok
Bemutatunk egy k´et l´ep´eses m´ odszert bin´ aris k´epek k¨ oz¨ otti s´ıkhomogr´ afia transzform´ aci´ o meghat´ aroz´ as´ ara. Az ilyen transzform´ aci´ o param´eterei a 3 × 3-as H m´ atrix Hij elemei (H33 = 1 r¨ ogz´ıtett). A H31 ´es H32 param´eterek a perspekt´ıv torzul´ ast ´ırj´ ak le, m´ıg a t¨ obbiek az affin transzform´ aci´ o param´eterei. A transzform´ aci´ o a k¨ ovetkez˝ ok´eppen bonthat´ o fel: h = ha ◦ hp (23) ahol hp : R2 → R2 , hp (x) = [hp1 (x), hp2 (x)]T egy nemline´ aris transzform´ aci´ o: hp1 (x)
=
hp2 (x)
=
x1 p1 x1 + p2 x2 + 1 x2 , p1 x1 + p2 x2 + 1
(24)
mely perspekt´ıv torzul´ ast eredm´enyez, m´ıg ha : R2 → R2 , ha (x) = [ha1 (x), ha2 (x)]T egy affin transzform´ aci´ o: ha1 (x)
=
a11 x1 + a12 x2 + a13
ha2 (x)
=
a21 x1 + a22 x2 + a23 .
(25)
´Igy a sablon (template) ´es a megfigyel´es (observation) alakzatok k¨ oz¨ otti o ¨sszef¨ ugg´es a k¨ ovetkez˝ ok´eppen ´ırhat´ o fel: Ft = (ha ◦ hp )(Fo ) = ha (hp (Fo ))
(26)
A javasolt m´ odszer a perspekt´ıv hp komponens pi param´etereit, ´es az affin ha komponens ai param´ereit k´et k¨ ul¨ on l´ep´esben hat´ arozza meg (l´ asd 6. ´ abra), v´eg¨ ul a (23) egyenlet alapj´ an megkapjuk a h transzform´ aci´ o Hij param´etereit. 11
Sablon
Megfigyel´es
1. l´ep´es
2. l´ep´es
6. ´ abra: A regisztr´ aci´ os folyamat: Az els˝ o l´ep´es csak a perspekt´ıv torzul´ ast ´ all´ıtja helyre a megfigyelt k´epen, m´ıg a m´ asodik l´ep´es meghat´ arozza az affin transzform´ aci´ ot ´ıgy megkapjuk az eredeti sablon k´epet. Ha a (26) egyenelet teljes¨ ul, akkor b´ armely affin invari´ ans I : R2 → R f¨ uggv´enyre: I(Ft ) = I(hp (Fo )).
(27)
Egy f¨ uggetlen affin invari´ ans Ii : R2 → R, i = 1 . . . n f¨ uggv´enyhalmazt v´eve a k¨ ovetkez˝ o egyenletrendszert kapjuk: Ii (Ft ) = Ii (hp (Fo )).
(28)
A perspekt´ıv torzul´ as hp param´etereit ezen egyenletrendszer megold´ asak´ent kapjuk. B´ ar k¨ onnyen l´ athat´ o, hogy ennek egyenletrendszernek nincs k¨ ozvetlen meghat´ arozhat´ o megold´ asa, az eredm´enyek mutatj´ ak, hogy az ´ altalunk haszn´ alt ´ altal´ anos nemline´ aris optimliz´ aci´ os m´ odszerrel hat´ekonyan megolhat´ o. A javasolt m´ odszert u ´gynevezett Affin Momentum Invari´ ansok (Affine Moment Invariants, AMIs [5]) eset´ere dolgoztuk ki, mivel haszn´ alatukkal hat´ekonyan sz´ am´ıthat´ o egyenletekhez jutunk. A (28) egyenletrendszer bal oldalai nem f¨ uggnek a hp param´eterekt˝ ol, teh´ at k¨ ozvetlen¨ ul sz´ am´ıthat´ oak a sablon alakzat pontkoordin´ at´ ai seg´ıts´eg´evel. Az F alakzat (r + s) rend˝ u mrs geometriai momentuma: Z mrs (F) = xr1 xs2 dx. (29) F
Az affine momentum invari´ ansok a centr´ alis momentumokon alapszanak: Z µrs (F) = (x1 − c1 )r (x2 − c2 )s dx
(30)
F
ahol az alakzat s´ ulypontjait a k¨ ovetkez˝ ok´eppen sz´ amoljuk: c1 = m10 (F)/m00 (F)
and
c2 = m01 (F)/m00 (F).
(31)
P´eld´ aul, az els˝ o kett˝ o affin momentum invari´ ans: I1 = (µ20 µ02 − µ211 )/µ400 I2 = (−µ230 µ203 +6µ30 µ21 µ12 µ03 −4µ30 µ312 −4µ321 µ03 +3µ221 µ212 )/µ10 00 . 12
(32)
Most megmutatjuk, hogy adott hp param´eterek eset´en a (28) egyenletrendszer jobb oldalai hogyan sz´ am´ıthat´ oak an´elk¨ ul, hogy t´enylegesen el˝ o´ all´ıtan´ ank a hp (Fo ) alakzatot. Ehhez a hp transzform´ aci´ o |Jhp | Jacobi determin´ ans´ at haszn´ aljuk. Egy hp transzform´ aci´ oval eltranszform´ alt F alakzat geometriai momentuma a k¨ ovetkez˝ ok´eppen sz´ am´ıthat´ o: Z mrs (hp (F)) = [hp1 (x)]r [hp2 (x)]s |Jhp (x)|dx (33) F
ahol a perspect´ıv transzform´ aci´ o Jacobi determin´ ansa: |Jhp (x)| =
1 , (p1 x1 + p2 x2 + 1)3
Egy perspekt´ıven torz´ıtott hp (F) alakzat centr´ alis momentumait a k¨ ovetkez˝ ok´eppen sz´ am´ıthatjuk: Z µrs (hp (F)) = [hp1 (x) − c1 ]r [hp2 (x) − c2 ]s |Jhp (x)|dx, (34) F
ahol c1 = m10 (hp (F))/m00 (hp (F)) and c2 = m01 (hp (F))/m00 (hp (F)).
(35) p
Adott p1 ´es p2 param´eterek eset´en a (28) egyenletrendszer jobboldalain l´ev˝ o I(h (F )) affin momentum invari´ ansok a (34) egyenletben le´ırt centr´ alis momentumok seg´ıts´eg´evel sz´ am´ıthat´ ok. ´Igy a momentumok sz´ am´ıt´ as´ ahoz elker¨ ulhet˝ o az eltranszform´ alt hp (F) alakzat t´enyleges el˝ o´ all´ıt´ asa, ami nagyon id˝ o´ıg´enyes feladat lenne. Miut´ an a perspekt´ıv param´etereket meghat´ aroztuk, a k¨ ovetkez˝ o l´ep´esben az Ft ´es p a h (Fo ) alakzatok k¨ oz¨ otti h transzform´ aci´ ot kell megbecs¨ uln¨ unk. Ezen c´elb´ ol a [3] m´ odszert haszn´ aljuk, melyet u ´gy m´ odos´ıtottunk, hogy a |Jhp | determin´ ans haszn´ alat´ aval elker¨ ulj¨ uk a hp (Fo ) alakzat el˝ o´ all´ıt´ as´ at. Az aij affin param´eterekre a k¨ ovetkez˝ o egyneletrendszer ´ırhat´ o fel: ! ! i Z Z n X n X i n−i i−j j n ak1 ak2 ak3 yk dy = |Jha | hp1 (x)n−i hp2 (x)i−j |Jhp (x)|dx, (36) i j=0 j Ft Fo i=1 ahol n = 1, 2, 3 ´es k = 1, 2. Ez az egyenletrendszer 6 darab 3-ad fok´ u polinom egyenletb˝ ol ´ all amely ´ıgy megoldhat´ o a 6 ismeretlenre. Az affin transzform´ aci´ o Jacobi determin´ ansa ´ alland´ o az eg´esz s´ıkon, ´es k¨ onnyen sz´ am´ıthat´ o az alakzatok ter¨ uleteinek ar´ anyak´ent: R dy Ft (37) |Jha | = R p |J h (x)|dx Fo B´ ar a (36) egyenletrendszernek t¨ obb megold´ asa lehet, k¨ oz¨ ul¨ uk k¨ onnyen kiv´ alaszthatjuk azt a val´ os gy¨ ok¨ ot, amellyel a (37) egyenletben meghat´ arozott determin´ anshoz tartozik. Megjegyezz¨ uk, hogy a megold´ as nem egy´ertelm˝ u, ha az alakzat affin-szimmetrikus. ¨ Osszet´ eve a hp pespekt´ıv ´es a ha affin transzform´ aci´ okat megkapjuk a keresett h s´ıkhomogr´ afi´ at. Vizsg´ alataink sor´ an a I3 , I4 , I5 , I6 invari´ ansokat haszn´ altuk ´es a (28) 13
7. ´ abra: Regisztr´ aci´ os eredm´enyek KRESZ t´ abl´ akon. A megfigyel´es k´epek az els˝ o sorban, alattuk pedig a megfelel˝ o sablon k´epek tal´ alhat´ oak. A regiszt´ aci´ os eredm´enyek kont´ urjait r´ avet´ıtett¨ uk a sablon k´epekre. egyenletrendszer megold´ as´ ahoz az u ´gynevezett differenci´ al evol´ uci´ o m´ odszert haszn´ altuk. Szintetikus adatb´ azison futtatott tesztek megmutatt´ ak, hogy a javasolt m´ odszer jobb eredm´enyeket ad az el˝ oz˝ o pontban bemutatott algoritmushoz k´epest, amely nem k´epes kezelni azokat a helyzeteket, amikor az alakzatok k¨ oz¨ ott 90 fokn´ al nagyobb m´ert´ek˝ u elforgat´ as van. Mivel az affin momentum invari´ ansok ´erz´ekenyek a szegment´ al´ asi hib´ ara, a m´ odszer robusztuss´ ag´ at ezen hib´ akkal szemben tesztelni kell a k´es˝ obbiekben. Mindazon´ altal siker¨ ult j´ o eredm´enyeket el´ern¨ unk t¨ obb val´ os KRESZ t´ abl´ akat ´ abr´ azol´ o k´epp´ aron is (l´ asd 7. ´ abra).
A szerz˝ o hozz´ aj´ arul´ asa az eredm´ enyekhez A szerz˝ o egy affin momentum invari´ ansokon alapul´ o m´ odszert dolgozott ki bin´ aris alakzatok k¨ oz¨ otti s´ıkhomogr´ afia transzform´ aci´ o param´etereinek becsl´es´ere. Megmutatja, hogyan lehet felbontani a transzform´ aci´ ot egy perspekt´ıv ´es egy affin o ¨sszetev˝ ore. A param´eterek meghat´ aroz´ asa k´et, egym´ ast k¨ ovet˝ o l´ep´esben t¨ ort´enik. Az els˝ o l´ep´es csak a perspekt´ıv torzul´ ast ´ all´ıtja helyre a megfigyelt k´epen, m´ıg a m´ asodik l´ep´es meghat´ arozza az affin transzform´ aci´ ot ´ıgy megkapjuk az eredeti sablon k´epet. A szerz˝ oo ¨sszehasonl´ıtja m´ odszert az el˝ oz˝ o pontban bemutatott technik´ aval ´es bemutat val´ os k´epeken el´ert eredm´enyeket is.
Hivatkoz´ asok [1] Kees Joost Batenburg. A network flow algorithm for reconstructing binary images from discrete x-rays. Journal of Mathematical Imaging and Vision, 27(2):175–191, 2007. [2] Serge Belongie, Jitendra Malik, and Jan Puzicha. Shape matching and object recog14
nition using shape context. Transaction on Pattern Analysis and Machine Intelligence, 24(4):509–522, April 2002. [3] Csaba Domokos and Zoltan Kato. Parametric estimation of affine deformations of planar shapes. Pattern Recognition, 43:569–578, March 2010. [4] Csaba Domokos, Jozsef Nemeth, and Zoltan Kato. Nonlinear shape registration without correspondences. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(5):943–958, May 2012. [5] Jan Flusser, Tom´ as Suk, and Barbara Zitov´ a. Moments and Moment Invariants in Pattern Recognition. Wiley & Sons, October 2009. [6] Jeongtae Kim and Soohyun Jang. High order statistics based blind deconvolution of bi-level images with unknown intensity values. Optics Express, 18(12):12872–12889, June 2010. [7] Donald W. Marquardt. An algorithm for least-squares estimation of nonlinear parameters. SIAM Journal on Applied Mathematics, 11(2):431–441, 1963. [8] Jozsef Nemeth. Recovering projective transformations between binary shapes. In Proceedings of Advanced Concepts for Intelligent Vision Systems, volume 7517, pages 374–383, Brno, Czech Republic, 2012. [9] Jozsef Nemeth. Discrete tomography with unknown intensity levels using higher-order statistics. Journal of Mathematical Imaging and Vision, 2015. Online first, DOI: 10.1007/s10851-015-0581-0. [10] Jozsef Nemeth and Peter Balazs. Restoration of blurred binary images using discrete tomography. In Proceedings of Advanced Concepts for Intelligent Vision Systems, volume 8192, pages 80–90, Poznan, Poland, 2013. [11] Jozsef Nemeth, Csaba Domokos, and Zoltan Kato. Nonlinear registration of binary shapes. In Proceedings of International Conference on Image Processing, pages 1101– 1104, Cairo, Egypt, November 2009. IEEE. [12] Jozsef Nemeth, Csaba Domokos, and Zoltan Kato. Recovering planar homographies between 2D shapes. In Proceedings of International Conference on Computer Vision, pages 2170–2176, Kyoto, Japan, September 2009. IEEE. [13] J´ ozsef N´emeth. S´ıkhomogr´ afia param´etereinek becsl´ese bin´ aris k´epeken. In Proceedings of National Scientific Students’ Associations Conference, April 2009. Supervisors: Zolt´ an Kat´ o and Csaba Domokos. Note: in Hungarian. 15
[14] James B. Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’96, pages 474–481, Philadelphia, PA, USA, 1996. SIAM. [15] Wim van Aarle, Kees Joost Batenburg, and Jan Sijbers. Automatic parameter estimation for the discrete algebraic reconstruction technique (DART). IEEE Transactions on Image Processing, 21(11):4608–4621, 2012.
16
