Sk´ al´ azottan mer˝ oleges kamera optim´ alis kalibr´ aci´ oja Hajder Levente MTA SZTAKI Geometria Modellez´es ´es Sz´ am´ıt´ og´epes L´ at´ as Laborat´ orium
[email protected] Absztrakt. A kamera kalibr´ aci´ o a h´ aromdimenzi´ os sz´ am´ıt´ og´epes l´ at´ as egyik fontos alapprobl´em´ aja, hiszen pontosan kalibr´ alt kamer´ ak n´elk¨ ul pontos h´ aromdimenzi´ os becsl´eseket sem lehet v´egezni. Kamerakalibr´ aci´ ora sz´ amtalan j´ ol m˝ uk¨ od˝ o algoritmus l´etezik, ezek t¨ obbs´ege perspekt´ıv kamer´ akkal foglalkozik, ´es kezdeti becsl´es ut´ an numerikus optimaliz´ al´ assal jav´ıtj´ ak a kalibr´ aci´ o min˝ os´eg´et. Sajnos nem bizony´ıthat´ o, hogy ezek az algoritmusok megtal´ alj´ ak az optimumot. Ebben a tanulm´ anyban azt mutatjuk meg, hogy kor´ abban kifejlesztett, gyeng´en perspekt´ıv kamerakalibr´ aci´ os algoritmusunk seg´ıts´eg´evel az optim´ alis megold´ as el´erhet˝ o.
1.
Bevezet´ es
Optim´ alis algoritmusok kifejleszt´ese sokn´ez˝opontos rekonstrukci´okhoz [5] kih´ıv´ asokkal teli feladat. Ez a cikk a sz´am´ıt´og´epes l´at´as egyik alapprobl´em´ aj´ aval, a kamerakalibr´ al´ assal foglalkozik. A t´ema nem u ´j, a 80-as ´evekt˝ol sz´amos kiv´ al´ o kutat´ o publik´alt kalibr´ al´o m´odszereket. Perspekt´ıv kamer´ ara sz´amtalan j´ol m˝ uk¨ od˝o algoritmust [4, 16] javasoltak. Ezek a m´odszerek el˝osz¨ or egy k¨ozel´ıt˝o megold´ast becs¨ ulnek, majd numerikus optimaliz´ al´assal [9, 10] jav´ıtj´ak a kapott k¨ozel´ıt´est. Sajnos az algoritmusok nem garant´ alj´ak, hogy megtal´alj´ak a glob´alis optimumot. Abban az esetben, ha a kamera bels˝o param´eterei m´ar ismertek, konvex optimaliz´ al´ as seg´ıts´eg´evel a k¨ uls˝ o param´etereket meg lehet optim´ alisan tal´ alni, ahogyan azt Olsson ´es mtsai. [12] megmutatt´ak. Sokkal egyszer˝ ubb a helyzet, ha affin kamer´ akat alkalmazunk, hiszen ebben az esetben a probl´ema line´aris [14]. Gyeng´en perspekt´ıv [2] ´es paraperspekt´ıv [6] kamer´ ak kalibr´ aci´ oj´ aval is foglalkoztak, azonban ezek a m´odszerek sem optim´ alisak, mert arra f´okusz´ alnak, hogyan lehet a val´odi perspekt´ıv ´es az egyszer˝ us´ıtett kameramodellek k¨oz¨otti ´atj´ar´ast megval´os´ıtani. Ezek a tanulm´anyok az optimalit´ assal nem foglalkoznak. Jelen cikk szerz˝ oje szint´en foglalkozott kamerakalibr´ aci´ oval. 2010-ben siker¨ ult megmutatni, hogy a gyeng´en perspekt´ıv kamera optim´ alis kalibr´aci´ oja [3] egy tizedfok´ u polinom seg´ıts´eg´evel megoldhat´o. Kor´abban javasoltunk rekonstrukci´os m´odszert sk´ al´ azottan ortonorm´alt kamer´ ara [13] is. Ebben a tanulm´anyban azt mutatjuk be, hogy a rekonstrukci´o sor´an alkalmazott ¨otlet seg´ıts´eg´evel a kamera kalibr´ aci´ oj´ at el lehet v´egezni, ´es az ´ıgy kapott iterat´ıv kalibr´ al´o algoritmus legkisebb n´egyzetes ´ertelemben optim´ alis megold´ast ad.
Optim´ alis kamerakalibr´ aci´ o
2.
343
A feladat megfogalmaz´ asa
Amennyiben adott egy t´erbeli pont, ´es a 2D-s vet¨ ulete a k´epen, a kalibr´ aci´ os algoritmusok c´elja a 3D → 2D vet´ıt´es param´etereinek megtal´al´asa. A kalibr´ al´o t´ argyunk i-edik pontj´ anak koordin´at´ait Xi , Yi ´es Zi jel¨oli, a vet´ıt´es ut´ani koordin´ at´akat pedig ui ´es vi . Perspekt´ıv kamera eset´en a vet´ıt´est a j´ol ismert ¨osszef¨ ugg´es seg´ıts´eg´evel kapjuk meg: Xi ui Yi vi ∼ C[R|T ] , (1) Zi 1 1 ahol R az ortonorm´alt forgat´ asi m´atrix, T az eltol´ asi vektor a kamera f´okuszpontja ´es a vil´ ag koordin´atarendszer´enek k¨oz´eppontja k¨oz¨ott. (R-et ´es T t a kamera k¨ uls˝ o param´etereinek szok´ as h´ıvni.) A ”∼” jel azt jelenti, hogy az egyenl˝ os´eg teljes¨ ul´es´ehez az egyik oldalt egy skal´arral meg kell szorozni. A kamera bels˝o param´eterei a C-vel jel¨olt fels˝o h´ aromsz¨ og m´atrixban tal´ alhat´oak. [4]. A gyeng´en perspekt´ıv kamera akkor alkalmazhat´o, ha a t´ argy m´elys´ege j´oval kisebb, mint a f´ okuszpont ´es a t´ argy pontjainak a t´ avols´aga. Ebben az esetben a perspekt´ıv vet´ıt´est az al´ abbi ¨osszef¨ ugg´essel k¨ozel´ıthetj¨ uk: Xi Yi ui (2) = [M |t] Zi , vi 1 ahol M -et mozg´ asi m´atrixnak h´ıvj´ ak, t a k´etdimenzi´os eltol´ asi vektor. Az eltol´ asi vektor a vil´ ag koordin´ atarendszer´enek vet¨ ulet´et adja meg a k´epen. M mozg´ asi m´atrix k´et sora h´ aromdimenzi´ os sorvektorokat tartalmaz, melyeket mT1 T tal ´es m2 -tal jel¨ ol¨ unk. Gyeng´en perspekt´ıv kamera eset´en ez a k´et sor mer˝oleges al´azottan ortonorm´alt kamer´ aval egym´ asra: mT1 m2 = 0. Ebben a cikkben sk´ foglalkozunk. Ez a gyeng´en perspekt´ıv kamer´ anak egy speci´ alis esete: nemcsak mer˝oleges a k´et sorvektor, hanem a hosszuk is megegyezik: mT1 m1 = mT2 m2 . A kamerakalibr´ aci´ o sor´an a c´elunk az ¨osszes pontra a k¨ovetkez˝ok´eppen fel´ırhat´ o visszavet´ıt´esi hib´ at minimaliz´alni: ||W − M S||2 ,
(3)
ahol || · ||2 az u ´n. Frobenius-norma n´egyzet´et (m´ atrix elemeinek n´egyzet¨osszeg´et) jel¨ oli, S m´atrix tartalmazza a h´ aromdimezi´ os pontokat, W m´atrix pedig a megfelel˝o vet¨ uletek k´etdimenzi´os koordin´at´ait: X1 X2 . . . XP S = Y1 Y2 . . . YP , (4) Z1 Z2 . . . ZP u1 u2 . . . uP . (5) W = v1 v2 . . . vP (P -vel jel¨ olj¨ uk a pontok sz´ am´ at.)
344
3.
Hajder Levente
Sk´ al´ azottan ortonorm´ alt kamera kalibr´ aci´ oja
Ahogyan azt megmutattuk [3], a gyeng´en perspekt´ıv kalibr´ aci´ o Lagrangemultiplik´ atoros optimaliz´ al´ assal egy tizedfok´ u polinom z´erushelyeinek keres´es´ere vezethet˝o vissza. Sk´ al´ azottan ortonorm´alt kalibr´ aci´ o eset´en ez a megold´as sajnos nem vezet eredm´enyre, hiszen k´et megk¨ ot´es¨ unk is van, szemben a gyenge perspekt´ıva egy megk¨ ot´es´evel. A m´atrixinverzi´ok miatt a behelyettes´ıt´es ´ıgy lehetetlenn´e v´alik. Ez´ert alkalmazzuk a k¨ovetkez˝o tr¨ ukk¨ot, ahogyan azt m´ar kor´abban is javasoltuk [13]: eg´esz´ıts¨ uk ki a k´etdimenzi´os koordin´at´akat ´es az M mozg´asi m´atrixot egy harmadik sorral: T m1 M = mT2 . (6) mT3
Ez a harmadik sorvektor legyen az els˝o k´et vektorra mer˝oleges, hossza pedig azonos az els˝o kett˝ o´evel. Ebben az esetben az M mozg´asm´atrixot fel tudjuk ´ırni egy ortonorm´alt R m´atrix ´es egy q val´os sz´am szorzatak´ent: M = qR. Ha az M mozg´ asm´atrix m´ar ki lett eg´esz´ıtve a harmadik sorral, a W m´er´esi m´atrixot is ki lehet eg´esz´ıteni: T w1 W = w2T , (7) w3T
T ahol w1T = [u1 u2 . . . uF ]T ´es ww = [u1 u2 . . . uF ]T . A harmadik sort, ha m´ar kieg´esz´ıtett¨ uk M -et, k¨onnyen ki lehet sz´amolni: w3T = mT3 S. A kalibr´ al´ o algoritmusunk sor´an a c´el kisz´ amolni R ortonorm´alt m´atrixot ´es q val´ os sz´ ammal ´ abr´ azolt sk´ al´az´ast, ha ismerj¨ uk S ´es W m´atrixot, m´as sz´oval van egy referernciaobjektumunk pontokkal, ´es ismerj¨ uk annak vet¨ uleteit is. Az optim´ alis kalibr´ al´ o algoritmus egy iter´aci´ o, aminek a v´az´at az 1. algoritmuson l´athatjuk. Az iter´ aci´ o mind¨ossze k´et l´ep´est tartalmaz, az els˝o kieg´esz´ıti az M ´es W m´atrixokat, a m´asik l´ep´es pedig egy 3D→3D regisztr´aci´ ot alkalmaz. Az´ert nevezz¨ uk regiszt´ aci´ onak, mert kieg´esz´ıtett W m´er´esi m´atrix eset´en az S strukt´ ura m´atrixban ´es W -ben ugyanannak a pontnak a h´ aromdimenzi´ os koordin´ at´ai vannak, egym´ ashoz k´epest sk´ al´azva ´es elforgatva. Ha a sk´ al´az´ast nem vessz¨ uk figyelembe, a probl´ema a 3D-s elforgat´ as megtal´al´asa. Ezt h´ıvj´ ak a geometri´ aban ponthalmazok regiszt´ aci´ oj´ anak. A regiszt´ aci´ os probl´ema optim´alisan megoldhat´o, a t¨ ok´eletes megold´ast t¨ obb elt´er˝o m´odszerrel meg lehet tal´ alni [1, 7, 8]. Ahogyan azt megmutattuk kor´abban [13], az elforgat´ as f¨ uggetlen a sk´ al´ az´ast´ ol. Ha pedig az elforgat´ as m´ar ismert, a sk´ al´az´as maga line´aris becsl´essel meghat´arozhat´o [13]. Ha pontos´ıtottuk a regiszt´ aci´ os l´ep´essel a q sk´ al´az´ast ´es az R ortonorm´alt m´atrixot, a W m´er´esi m´atrix kieg´esz´ıt´es´et u ´jra ´es u ´jra el kell v´egezni. A visszavet´ıt´esi hib´ at mind a regisztr´aci´ os, mind a kieg´esz´ıt˝o l´ep´es cs¨okkenti, vagy legal´ abbis nem n¨ oveli. Mivel a visszavet´ıt´esi hiba nemnegat´ıv, ´es csak cs¨okkenni tud, ez´ert biztosak lehet¨ unk abban, hogy az elj´ar´as konverg´ al.
Optim´ alis kamerakalibr´ aci´ o
345
Algorithm 1 A sk´ al´ azottan ortonorm´alt kamera kalibr´ aci´ oj´ anak v´aza. repeat w3 ← Kieg´esz´ıt´es(R,t,S,q) R,t,q ← Regisztr´ aci´ o(S,w1 ,w2 ,w3 ) until konvergencia.
4.
A lok´ alis optimum probl´ em´ aja
Ahogyan azt m´ar kor´ abban eml´ıtett¨ uk, az el˝oz˝o fejezetben ismertetett kalibr´ aci´ os algoritmus a glob´alis optimumot megtal´alja. Ebben a fejezetben azt mutatjuk meg, hogy a m´odszer t¨ orv´enyszer˝ uen a glob´alis optimumhoz konverg´ al, hiszen lok´alis minimum nem l´etezik. A bizony´ıt´ ast el˝ osz¨ or egyszer˝ us´ıt´essel v´egezz¨ uk el: ha a 3D→2D vet´ıt´es helyett 2D→1D vet´ıt´essel k´epzelj¨ uk el a probl´em´ at, minden igaz marad, azt lesz´am´ıtva, hogy a mozg´ asm´atrix csak egy sort tartalmaz, kieg´esz´ıtve kett˝ ot. A bizony´ıt´as ebben az esetben k¨onnyebben meg´erthet˝ o, mivel k´etdimenzi´oban a forgat´ asi m´atrix le´ırhat´ o egy param´eter (p´eld´ aul a forgat´ asi sz¨og) seg´ıts´eg´evel. 4.1.
2D → 1D vet´ıt´ es
Ez egyszer˝ us´ıtett esetben a visszavet´ıt´esi hiba ´ıgy n´ez ki: 2 N X
ui − m2D Xi ,
Yi
(8)
i=1
ahol m2D = qr1T egy sorvektor, amelyiket ki lehet eg´esz´ıteni az r2 vektorral. r2 mer˝oleges r1 -re, mindkett˝ o egys´egvektor. A m´ert ui koordin´at´at szint´en ki lehet eg´esz´ıteni a m´asodik koordin´ at´aval: vi = qr2 [Xi , Yi ]T . Az optim´ alis regiszt´ aci´ o p´eld´ aul Arun ´es mtsai. m´odszer´evel [1] k´etdimenzi´oban is meghat´arozhat´o optim´alisan. Mint ahogyan azt m´ar l´athattuk, k´et ¨onmag´ aban optim´ alis l´ep´esb˝ ol ´all a kalibr´ al´ o algoritmus. A ”csal´ as” ott l´ep be, hogy a W m´er´esi m´atrixot kieg´esz´ıtj¨ uk u ´j (m´ asodik) koordin´at´akkal, amit a regiszt´aci´ o sor´an pontosan ugyan´ ugy vesz¨ unk figyelembe, mint a m´ert ui koordin´at´akat. Att´ol tartunk, hogy ez a kieg´esz´ıt´es elt´er´ıti a j´o megold´ast´ ol az algoritmust. Ez abban az esetben lehets´eges, ha a forgat´ as/sk´al´az´as eset´en az els˝o sor n´egyzetes hib´aj´ anak a deriv´altja abszolut´ert´ekben ksiebb, mint a m´asodik sor´e, azaz azt a javul´ast, amit az els˝o sor okoz, a m´asodik sor k´epes visszah´ uzni. K¨onny˝ u bel´atni, hogy a sk´ al´ az´as ezt nem befoly´ asolja, hiszen mindk´et sor ugyan´ ugy meg van szorozva q-val. Az elforgat´ as k´erd´ese m´ar bonyolultabb. Szerencs´ere tudjuk, hogy a m´odszer¨ unk konverg´ al valahova. Amikor m´ar nagyon-nagyon k¨ozel j´ar a minimumhoz, tudjuk, hogy nagyon pici sz¨oggel is fel´ırhatjuk a forgat´ ast. A forgat´ asi m´atrix ´ıgy ´ırhat´ o fel alapesetben: cos ∆α sin ∆α R= . (9) − sin ∆α cos ∆α
346
Hajder Levente r2
Térbeli pont
∆α
Új kiegészített érték ε(τ)
Régi kiegészített érték
Régi becslés r1 δ(τ−1)
∆α
Új becslés δ(τ) Mérés
1. ´ abra: A regisztr´ aci´ o ´es a kieg´esz´ıt´es hib´ aj´ anak v´ altoz´ asa szomsz´edos iter´ aci´ ok k¨ oz¨ ott
Ez nagyon kicsi ∆α eset´en a j´ ol ismert sz¨ogf¨ uggv´enyes k¨ozel´ıt´esekkel ´at´ırhat´ o:
R≈
1 ∆α . −∆α 1
(10)
A kieg´esz´ıt´es akkor ´ all´ıtja meg a konvergenci´at lok´alis minimumban, ha a regiszt´ aci´ o javul´as´ anak a deriv´altja abszolut´ert´ekben kisebb, mint a kieg´esz´ıt´es roml´ asa. (A kieg´esz´ıt´es mindenk´eppen romlik, hiszen minden egyes kieg´esz´ıt˝o l´ep´es null´ ara cs¨ okkenti a hib´ at a kieg´esz´ıtett (harmadik) koordin´at´akban.) Az 1. ´ abr´ an l´athatjuk az iter´aci´ o k´et l´ep´ese k¨oz¨otti v´altoz´ ast, ha ∆α-val v´altozik meg a sz¨ og. Az R m´atrix k´et sora adja meg a koordin´atatenglyeket, ezek forognak a regisztr´ aci´ os l´ep´es sor´an Az aktu´alis iter´aci´o sz´am´ at τ -val jel¨ ult¨ uk az ´abr´ an. Jel¨olj¨ uk ǫi -vel a regiszt´ aci´ o javul´as´at, δi -vel a kieg´esz´ıt´es hib´aj´ anak n¨ oveked´es´et a regisztr´ aci´ o ut´an.
Optim´ alis kamerakalibr´ aci´ o
347
A regisztr´ al´ o l´ep´esben a kapott forgat´ asb´ ol j¨ov˝ o koordin´atav´altoz´ as k¨onnyen kifejezhet˝o: 1 ∆α Xi Xi − (11) −∆α 1 Yi Yi 0 ∆α Xi = (12) −∆α 0 Yi Yi . (13) = ∆α −Xi A regisztr´ aci´ o hib´ aja az elforgatott koordin´ata ´es a m´ert ´ert´ek k¨ ul¨onbs´ege: Xi = ui − Xi − ∆αYi , (14) ǫi = ui − 1 ∆α Yi a kieg´esz´ıt´esb˝ ol sz´ armaz´o hiba pedig a 13. ¨osszef¨ ugg´es m´asodik koordin´at´aja: δi = −∆αXi . Az algoritmus akkor ragad benne a rossz poz´ıci´oban, ha a sz¨ogv´altoz´ as szerinti deriv´alt abszulut´ert´eke nagyobb a keg´esz´ıt´es hib´aj´ ara, mint a regisztr´aci´ o javul´as´ ara n´ezve: P ∂ N e2 ∂ PN δ 2 i=1 i i=1 i (15) < . ∂∆α ∂∆α is igaz, hogy
PN
2 i=1 δi ∂∆α P 2 ∂ N i=1 ei >0 ∂∆α
Tudjuk, hogy
∂
→ 0 ha ∆α → 0, hiszen
∂δi2 ∂∆α
= ∆αXi2 . M´ asr´eszr˝ol az
minden esetben, kiv´eve, amikor ui − Xi = 0 ∀i, mivel
∂ǫ2i ∂∆α
= 2(ui − Xi − ∆αYi )Yi . Ez azt jelenti, hogy a regiszt´ aci´ o jav´ıt´o hat´asa minden esetben er˝ osebb, mint a kieg´esz´ıt´es koordin´at´aj´ aban okozott hiba, kiv´eve, ha ui − Xi = 0 ∀i. Ez ut´obbi eset azonban azt jelenti, hogy a regiszt´ aci´ o t¨ ok´eletes, m´ar kor´ abban el´ert¨ uk a minimumot. (R´aad´asul ez csak abban a kiv´eteles esetben lehets´eges, ha az [ui , vi ]T koordin´at´akban semmi zaj nincsen, nulla hib´aval regiszt´ alni kalibr´ alni lehet a kamer´ at, Ilyen gyakorlatilag sosem fordul el˝o.) Teh´at nem tud az algoritmus lok´alis minimumba futni, ak´ arhonnan ind´ıtjuk, ugyanazt a megold´ast kapjuk. 4.2.
3D → 2D vet´ıt´ es
Ebben az esetben is felt´etelezhetj¨ uk, hogy m´ar k¨ozel vagyunk a megold´ashoz. Kis v´altoz´ as eset´en a forgat´ asi m´atrix h´ aromdimenzi´ oban is le´ırhat´ o kis sz¨og ´es egy tengely seg´ıts´eg´evel. (A forgat´ asi m´atrixnak h´ arom szabads´agi foka van, a tengely kett˝ ot, a sz¨ og egyet ad.) Tegy¨ uk fel, hogy a forgat´ as a Z tengely k¨or¨ ul t¨ ort´enik. Ebben az esetben a kis ∆α sz¨oggel forgat´ as ´ıgy ´ırhat´ o le: 1 ∆α 0 R′ ≈ −∆α 1 0 . (16) 0 0 1
348
Hajder Levente
´ Altal´ anos esetben nem igaz, hogy a Z tengely k¨or¨ ul forgatunk, ez´ert az eredeti koordin´ atarendszerb˝ol el kell u ´gy forgatnunk a pontokat, hogy ez igaz legyen. Ehhez egy Q = [q1 , q2 , q3 ]T h´ aromdimenzi´ os transzform´ aci´ ot vezet¨ unk be u ´ gy, hogy igaz legyen: R = QR′ . A regiszt´ aci´ os l´ep´esre a 2D→1D esethez hasonl´ oan igaznak kell lennie, hogy a regiszt´ aci´ o javul´as´at nem k´epes elrontani a kieg´esz´ıtett koordin´ at´akb´ ol sz´ armaz´o hiba. Az i. pontra jut´o kieg´esz´ıt´esi hib´at jel¨olj¨ uk tov´abbra is δi -vel. ´Igy tudjuk meghat´arozni:
1 ∆α 0 Xi δi = q3T −∆α 1 0 − I3x3 Yi Zi 0 0 1 Yi = ∆αq3T −Xi . Zi
(17)
(18)
A regiszt´ aci´ os hiba k´et koordin´ata javul´as´ab´ol ad´odik. Az els˝o koordin´at´a´e ´ıgy n´ez ki: 1 ∆α 0 Xi ǫi = ui − q1T −∆α 1 0 Yi Zi 0 0 1 Yi Xi = ui − q1T Yi − ∆αq1T −Xi . Zi Zi
A m´asodik koordin´ ata ´ertelemszer˝ uen hasonl´ o: Xi Yi γi = vi − q2T Yi − ∆αq2T −Xi . Zi Zi
(19)
(20)
(21)
A lok´alis minimum abba az esetben ker¨ ulhet˝o el, ha mindig igaz, hogy P PN 2 PN 2 ∂ N e2 ∂ ∂ i=1 δi i=1 i i=1 γi + < . ∂∆α ∂∆α ∂∆α
(22)
Xi Xi Ez pedig igaz, kiv´eve ha ui = q1T Yi , ´es vi = q2T Yi minden i-re . Zi Zi Ez pedig csak akkor igaz, ha m´ar t¨ ok´eletesen egym´ ashoz vannak regisztr´alva a ponthalmazok, azaz m´ar a glob´alis minimumban vagyunk. Teh´at kijelenthetj¨ uk, hogy a kalibr´ aci´ os algoritmus mindig ugyanoda, a glob´ alis minimumhoz konverg´ al.
Optim´ alis kamerakalibr´ aci´ o
5.
349
Eredm´ enyek
Gyeng´en perspekt´ıv kamerakalibr´ aci´ ot ¨onmag´ aban ritk´ an szoktak alkalmazni, mivel r¨ogz´ıtett kamer´ ak eset´en c´elszer˝ ubb a val´os´agot jobban k¨ozel´ıt˝o perspekt´ıv kalibr´ aci´ ot haszn´alni. Mozg´ o t´ argyak rekonstrukci´oj´ an´al azonban nagyon hasznos a gyeng´en perspekt´ıv kamera. Mi is az´ert fejlesztett¨ uk ki a jelen tanulm´anyban ismertetett optim´ alis kalibr´ aci´ os algoritmust, hogy mozg´o t´ argyak k¨ovetett pontjainak h´ aromdimenzi´ os rekonstrukci´oj´ at v´egezz¨ uk. Ez akkor lehets´eges, ha k¨ozben mag´anak a kamer´ anak a param´etereit is kisz´ am´ıtjuk. (Ezt a folyamatot nevezik a kamera autokalibr´ aci´ onak). Ez´ert ebben a cikkben tesztel´esi eredm´enynek rekonstrukci´os eredm´enyeket mutatunk, noha a kalibr´ al´ o m´odszer¨ unk optimaliz´ as´at szintetikus adatokon kipr´ ob´altuk: ugyanarra a mesters´egesen gener´alt 3D-s ´es 2D-s megfeleltetett ponthalmazra k¨ ul¨onb¨ oz˝o indul´o param´eterekkel lefuttattuk az algoritmust. Kiv´etel n´elk¨ ul ugyanahhoz az eredm´enyhez konverg´ alt a m´odszer. Ha zajmentes adatokkal futtattuk, szint´en kiv´etel n´elk¨ ul a helyes megold´ashoz konverg´ alt a m´odszer, ak´ arhonnan is ind´ıtottuk. Mivel a javasolt rekonstrukci´os m´odszer megegyezik a kor´abban publik´ alt algoritmusunkkal [13], itt csak val´os k´epsorozatokon futtatott rekonstrukci´ os eredm´enyeket mutatunk meg. Szintetikus eredm´enyeket ´es konkurrens m´odszerekkel val´ o¨ osszehasonl´ıt´asokat a kor´abbi publik´aci´ onkban [13] tal´ alhatja meg a kedves Olvas´ o. ”Arc” tesztsorozat. Els˝o val´os teszt¨ unk egy mereven tartott arc rekonstrukci´ oja. A kiindul´ asi k´epeket a 2. ´abr´ an l´athatjuk. A k´epeken automatikusan k¨ovett¨ uk a pontokat az AAM [11] (Active Appearance Model) seg´ıts´eg´evel. Sz´amszer˝ uen 44 pontot k¨ovett¨ unk 331 k´epkock´an kereszt¨ ul. A rekonstrukci´o eredm´enye a 3. ´ abr´ an l´athat´o. A rekonstrukci´os eredm´enyt 1 m´asodperc alatt sz´ am´ıtotta ki a Core4Quad processzoros (2.33GHz, 4GByte RAM) g´ep¨ unk.
2. ´ abra: 4 tesztk´ep az ”Arc” sorozatb´ ol
”D´ın´ o” tesztsorozat A forg´ o m˝ uanyag dinoszaurusz k¨ovetet pontjai az Oxford Egyetem honlapj´ ar´ ol1 t¨ olt¨ ott¨ uk le. A rekustr´aland´o t´ argyr´ol k´epek az 5. ´abr´ an l´athat´oak. ¨ ¨ Osszesen 319 pontot ´es 36 k´epet tartalmaz a k¨ovetett pontok list´ aja. Ontakar´ as miatt nem mindegyik pont l´atszik, de ez nem okoz probl´em´ at a rekonstrukci´os 1
http://www.robots.ox.ac.uk/∼amb/
350
Hajder Levente
3. ´ abra: Az arc rekonstr´ alt modellje
4. ´ abra: A ”Macska” tesztsorozat n´eh´ any k´epe, ´es a hozz´ ajuk tartoz´ o maszkok.
algoritmusnak, amely 36 m´asodperces fut´as ut´an adta a 6. ´abr´ an l´athat´o eredm´enyt.
5. ´ abra: 4 tesztk´ep a ”D´ın´ o” sorozatb´ ol
”Macska” tesztsorozat Az utols´ o tesztsorozatot magunk k´esz´ıtett¨ uk. Egy macsk´ at ´ abr´ azol´o szobrot megforgattuk az asztalon, ¨osszesen 92 f´enyk´epet k´esz´ıtve. A h´ atteret ´es a macsk´at saj´at m´odszer¨ unk seg´ıts´eg´evel elv´alasztottuk, ahogyan az a 4. ´ abr´ an l´atszik. Ezek ut´an KLT algoritmus [15] seg´ıts´eg´evel pontokat v´alasztottunk ki, ´es k¨ovett¨ uk ˝oket. Amennyiben egy pont k¨ozel ker¨ ult a ¨ h´ att´erhez, eldobtuk. Osszesen 2290 pontot k¨ovett¨ unk. A rekonstrukci´o, amely 199 m´asodperces fut´as eredm´enyek´eppen keletkezett, a 7. ´abr´ an tekinthet˝ o meg.
Optim´ alis kamerakalibr´ aci´ o
6. ´ abra: A ”D´ın´ o” sorozat rekonstru´ alt h´ aromdimenzi´ os pontjai
7. ´ abra: A ”Macska” sorozat rekonstru´ alt h´ aromdimenzi´ os pontjai
351
352
Hajder Levente
6.
¨ Osszefoglal´ as
Ebben a cikkben megmutattuk, hogy a sk´ al´azottan ortonorm´alt kamer´ at hogyan kell iterat´ıv algoritmus seg´ıts´eg´evel kalibr´ alni. Bebizony´ıtottuk, hogy a kidolgozott algoritmus a kalibr´ aci´ o visszavet´ıt´esi hib´aj´ at legkisebb n´egyzetes ´ertelemben minimaliz´ alja, ´es a minimum minden esetben glob´alis. Rekonstrukci´os p´eld´ an kereszt¨ ul igazoltuk, hogy az itt ismertetett algoritmus gyakorlati alkalmaz´asokba is be´ep´ıthet˝ o.
K¨ osz¨ onetnyilv´ an´ıt´ as A szerz˝ o ez´ uton szeretne k¨osz¨ onetet mondani Kaz´o Csab´ anak, Csetverikov Dmitrijnek ´es Tak´ acs D´anielnek, hogy seg´ıtettek az eredm´enyek elk´esz´ıt´es´ehez n´elk¨ ul¨ozhetetlen pontk¨ ovet´esek ´es el˝ot´er-h´att´er sz´etv´alaszt´o m´odszerek elk´esz´ıt´es´eben. A munka az NKTH-OTKA CK 78409 p´ aly´azat keret´eben k´esz¨ ult.
Irodalom 1. K. S. Arun, T. S. Huang, and S. D. Blostein. Least-squares fitting of two 3-D point sets. IEEE Trans. on PAMI, 9(5):698–700, 1987. 2. Daniel F. DeMenthon and Larry S. Davis. Model-based object pose in 25 lines of code. International Journal of Computer Vision, 15:123–141, 1995. 3. L. Hajder. L2 -Optimal Weak-Perspective Camera Calibration. In Fifth Hungarian Conference on Computer Graphics and Geometrics, pages 89–96, 2010. 4. R. I. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision. Cambridge University Press, 2000. 5. Richard Hartley and Fredrik Kahl. Optimal algorithms in multiview geometry. In Proceedings of the Asian Conf. Computer Vision, pages 13–34, 2007. 6. Radu Horaud, Fadi Dornaika, Bart Lamiroy, and St´ephane Christy. Object pose: The link between weak perspective, paraperspective and full perspective. International Journal of Computer Vision, 22(2):173–189, 1997. 7. B.K.P. Horn. Closed-form Solution of Absolute Orientation using Unit Quaternions. Journal of the Optical Society of America, 4:629–642, 1987. 8. B.K.P. Horn, H.M. Hilden, and S. Negahdaripourt. Closed-form Solution of Absolute Orientation Using Orthonormal Matrices. Journal of the Optical Society of America, 5(7):1127–1135, 1988. 9. K. Levenberg. A method for the solution of certain problems in least squares. Quart. Appl. Math., 2:164–168, 1944. 10. D. Marquardt. An algorithm for least-squares estimation of nonlinear parameters. SIAM J. Appl. Math., 11:431–441, 1963. 11. Iain Matthews and Simon Baker. Active appearance models revisited. International Journal of Computer Vision, 60:135–164, 2003. 12. Carl Olsson, Fredrik Kahl, and Magnus Oskarsson. Optimal estimation of perspective camera pose. In ICPR ’06: Proceedings of the 18th International Conference on Pattern Recognition, pages 5–8, 2006.
Optim´ alis kamerakalibr´ aci´ o
353
´ Pernek, L. Hajder, and Cs. Kaz´ 13. A. o. Metric Reconstruction with Missing Data under Weak-Perspective. In British Machine Vision Conference, pages 109–116, 2008. 14. Heung-Yeung Shum, Katsushi Ikeuchi, and Raj Reddy. Principal component analysis with missing data and its application to polyhedral object modeling. IEEE Trans. Pattern Anal. Mach. Intell., 17(9):854–867, 1995. 15. Tomasi, C. and Shi, J. Good Features to Track. In IEEE Conf. Computer Vision and Pattern Recognition, pages 593–600, 1994. 16. Z. Zhang. A flexible new technique for camera calibration. IEEE Trans. on PAMI, 22(11):1330–1334, 2000.