Budapesti M˝ uszaki ´es Gazdas´agtudom´anyi Egyetem Ir´any´ıt´astechnika ´es Informatika Tansz´ek
Proh´ aszka Zolt´ an ´ ˝ geometriai me ´rte ´keken e ´s Ujszer u ´pjellemzo ˝ ko ¨ n alapulo ´ mozga ´ ssztereo ´ ke ´ sokhoz mobilis robotikai alkalmaza Ph. D. ´ertekez´es t´ezisei
Motion stereo for mobile robot applications based on novel geometric measures and image features Ph. D. Thesis Summary
Konzulens: Prof. Dr. Lantos B´ ela
Budapest, 2010. december 14.
2
3
1.
Bevezet˝ o´ es motiv´ aci´ o
A termel´esben alkalmazott ipari robotok t¨obbs´ege csup´an 6 csukl´oszenzor seg´ıts´eg´evel l´atja el feladat´at. Ez csak akkor lehets´eges, ha a robotnak mindig pontos inform´aci´oja van a k¨ornyezet pillanatnyi a´llapot´ar´ol. Egyre nagyobb teret kapnak viszont azok az alkalmaz´asok, amikor a robotnak ’intelligens’ m´odszerekkel kell a k¨ornyezet le´ır´as´ab´ol hi´anyz´o elemeket meghat´aroznia. K¨ ul¨on¨osen ´ıgy van ez olyan feladatok eset´eben, amikor a robot helyv´altoztat´asa sz¨ uks´eges, hiszen egy ilyen mobilis robot k¨ornyezete sokkal t¨obb, el˝ore nem specifik´alhat´o elemet tartalmazhat. Erre a c´elra a vizu´alis ´erz´ekel´es kiv´al´oan alkalmas: • T´avoli ´erz´ekel´est tesz lehet˝ov´e, a k¨ornyezetet nem v´altoztatja meg a m´er´es. • Az egyes ´erz´ekel˝ocell´ak igen alacsony k¨olts´eg˝ uek, hiszen egy eszk¨ozben t¨obb milli´o is lehet. • A jelek ´erz´ekel´ese ´es azok feldolgoz´asa j´ol ismert geometriai viszonyok mellett, illetve o¨sszef¨ ugg´esek alapj´an zajlik, ´ıgy geometriailag helyes kimenetet lehet el˝oa´ll´ıtani. Nem v´eletlen, hogy az emberi termel˝o tev´ekenys´eg sor´an is domin´al a vizu´alis ´erz´ekel´es felhaszn´al´asa [2]. A sz´am´ıt´og´epes k´epfeldolgoz´as fejl˝od´ese sz´etv´alaszthatatlan a sz´am´ıt´og´epek fejl˝od´es´et˝ol. Ahogy a g´epek mem´oria- ´es sz´am´ıt´asi kapacit´asa n¨ovekszik, u ´gy v´alik lehet˝ov´e az egyes, ak´ar ´evek o´ta ismert o¨tletek, elm´eleti eredm´enyek gyakorlati ellen˝orz´ese ´es m´odos´ıt´asa. A k´epfeldolgoz´as tiszt´an elm´eleti erdem´enyei ez´ert mindig megel˝ozik a gyakorlatban bev´alt m´odszereket, melyek csak akkor alkalmazhat´ok a robotik´aban, ha megb´ızhat´o m˝ uk¨od´es¨ uk ki lett dolgozva. Ez ut´obbi ter¨ uletet nevezik (angolul) Robot Vision-nek, az ezen a ter¨ uleten el´ert eredm´enyeket a´ltal´aban robotikai konferenci´akon ´es foly´oiratokban teszik k¨ozz´e. A sz´am´ıt´og´epes l´at´as (Computer Vision) ´es a ’Robot Vision’ ter¨ uletek k¨oz¨ott nem egyir´anny´ u az inform´aci´oa´raml´as, az egyes m´odszerek ´eles robotikai feladatokban val´o alkalmazhat´os´aga megmutatja az elm´eleti ir´anyzatok ´eletk´epess´eg´et. Az ilyen alkalmaz´asok perd¨ont˝ok lehetnek az egym´assal verseng˝o m´odszerek j¨ov˝obeni alkalmaz´asa szempontj´ab´ol. Mivel a robotok a 3-dimenzi´os t´erben fejtik ki tev´ekenys´eg¨ uket, ez´ert a 3-dimenzi´os k¨ornyezet modellj´enek k´etdimenzi´os vet¨ uletekb˝ol t¨ort´en˝o el˝oa´ll´ıt´as´ara koncentr´alunk. Egy ilyen folyamat elemi l´ep´ese k´et k´ep viszony´anak a meghat´aroz´asa. Amennyiben el˝ozetes inform´ac´o nem ´all rendelkez´esre a k´et k´ep viszony´ar´ol, akkor ez a k¨ovetkez˝o l´ep´esekre bonthat´o: • A fontos k´epr´eszletek elhelyezked´es´enek meg´allap´ıt´asa (kulcster¨ ulet lokaliz´aci´o). • Az ezen r´eszletek ´altal tartalmazott k´epi inform´aci´ot reprezent´al´o le´ır´ovektorok kinyer´ese (le´ır´ovektor gener´al´as).
˝ MOTIVACI ´ O ´ 1 BEVEZETO,
4
• Kulcster¨ uletek p´aros´ıt´asa a le´ır´ok hasonl´os´aga ´es geometriai elhelyezed´es¨ uk alapj´an. K¨ovetelm´eny, hogy a p´aros´ıt´asok o¨sszess´ege ¨osszhangban legyen valamilyen transzform´aci´os modellel. Ez a transzform´aci´os modell teh´at a l´ep´es sor´an el˝oa´ll. A kapott, ´es m´as k´epp´aros´ıt´asokb´ol ered˝o transzform´aci´os modellek m´ar t´erbeli inform´aci´okat hordoznak, a rekonstrukci´os folyamat tov´abbi l´ep´eseiben ezek kombin´al´asa sz¨ uks´eges, hogy a k¨ornyezet min´el pontosabb t´erbeli modellje a´lljon el˝o. Ennek a l´ep´esnek a komplexit´asa igen v´altoz´o lehet, az ´ertekez´es ezeket nem t´argyalja r´eszletesen. A k´epp´aros´ıt´asi feladat megold´as´at az ezredfordul´o el˝ott geometriai k´epjellemz˝ok alapj´an v´egezt´ek, m´ıg D. Lowe gyakorlatias m´odszer´enek (SIFT, azaz Scale Invariant Feature Transform [8]) hat´as´ara az ezredforul´o ut´an a momentum, illetve gradiens-histogramm alapj´an m˝ uk¨od˝o m´odszerek domin´altak. A m´odszer k´et l´enyeges l´ep´ese a stabilan reproduk´alhat´o kulcster¨ uletek meghat´aroz´asa (lokaliz´aci´oja), illetve a megtal´alt ter¨ uletek tartalm´anak t¨om¨or´ıt´ese k´epr´eszlet-le´ır´o vektorokba. A felhaszn´alt elm´eleti eredm´enyeket (DoGSS) m´ar a kilencvenes ´evekben ismert´ek [6, 7], de a SIFT detektor olyan m´odos´ıt´asokat adott ezekhez, melyek a gyakorlatban is bizony´ıtott´ak a kutat´asi ir´anyvonal ´eletk´epess´eg´et. Az u ´j ir´anyvonal igen sok konkurrens megold´ast hozott, t¨obbek k¨oz¨ott a PCA-SIFT [5] , GLOH [12], SURF [1], Harris-Affine [11], MSER [10] m´odszereket. A t¨obb kamerak´epen alapul´o 3-dimenzi´os rekonstrukci´o alapvet˝o geometria ¨osszef¨ ugg´eseit ´es algebrai m´odszereit az 1980-as, 1990-es ´evekben dolgozt´ak ki. Ezeket szeml´eletesen ´es t¨om¨oren mutatja be Hartley ´es Zisserman k¨onyve [4].
1.1.
Az ´ ertekez´ esben megoldott feladatok
Az ´ertekez´es a fenti feladatok egyes r´eszfeladataira ad u ´j megold´asokat, ezeket k´et megk¨ozel´ıt´esben mutatja be. Az affin Lucas-Kanade (LK) detektor [9] szingul´aris eseteinek vizsg´alat´ab´ol ad´od´o eredm´enyek a´ltal´anosan haszn´alhat´ok. A kidolgozott eredm´enyek o¨sszek¨otik az irodalomban eddig k¨ ul¨on t´argyalt geometriai k´epjellemz˝okre ´es a kulcster¨ uletek tartalm´anak reprezent´al´as´ara haszn´alt le´ır´o-vektorokra alapozott megk¨ozel´ıt´eseket. A tansz´eken fejlesztett n´egyrotoros auton´om belt´eri helikopter poz´ıci´oj´anak ´es orient´aci´oj´anak meghat´aroz´as´ahoz kidolgozott eredm´enyek a fent v´azolt feldolgoz´asi folyamat egy´eb l´ep´eseit is ´erintik. A kutat´omunka elej´en, a klasszikus m´odszerek tanulm´anyoz´asakor felt˝ unt, hogy am´ıg a standard Lucas-Kanade detektor szingul´aris eseteinek analiz´al´asa azonos a Harris Corner detektor [3] formalizmus´aval, addig az affin LK detektor szingul´aris eseteinek vizsg´alata ¨ nincs kidolgozva. Ez vezetett az Onaffin K´epjellemz˝o (Self Affine Feature Transform, SAFT) kidolgoz´as´ahoz. A kutat´as ehhez kapcsol´od´o r´eszfeladata ezut´an arra koncentr´alt, hogy a szingul´aris esetek vizsg´alata kapcs´an felt´art ¨osszef¨ ugg´eseket min´el alaposabban formaliz´aljam, ´es gyakorlati alkalmazhat´os´agukat kidolgozzam. A felfedezett o¨sszef¨ ugg´esek
1.1 Kutat´asi feladatok
5
hamar egy´ertelm˝ uv´e tett´ek, hogy a m´odszer kiv´al´oan haszn´alhat´o (affin invari´ans) geometriai inform´aci´ok kinyer´es´ere. Er˝os volt a sejt´es, hogy a kinyert inform´aci´ok haszn´alhat´ok le´ır´ovektor-alap´ u p´aros´ıt´asra is, mivel a bizony´ıtottan j´ol m˝ uk¨od˝o m´odszerekhez hasonl´oan a gradiensek eloszl´as´at k´odolj´ak. Siker¨ ult a kidolgozott m´odszer egy olyan param´eterez´es´et megtal´alni, ami ennek a kutat´asi ir´anynak a folytat´as´ara buzd´ıtott. A tov´abbiakban az optim´alis param´eterez´es meghat´aroz´asa kimer´ıt˝o keres´es seg´ıts´eg´evel t¨ort´ent. Nem v´art eredm´enyk´ent f´eny der¨ ult arra, hogy a kidolgozott formalizmus a kulcshelyzetek lokaliz´aci´oj´anak elv´egz´ese k¨ozben is haszn´alhat´o. Ez a kutat´asi ir´any nem tekinthet˝o befejezettnek.
1. ´abra. A tansz´eken fejlesztett n´egyrotoros helikopterek protot´ıpusa. Az Ir´any´ıt´astechnika ´es Robotika csoport egy belt´eri n´egyrotoros auton´om helikoptert fejleszt a Budapesti M˝ uszaki Egyetem Ir´any´ıt´astechnika ´es Informatika Tansz´ek´en (BME IIT). Kutat´asi projekt¨ unk 2006 tavasz´an kezd˝od¨ott, az MTA SZTAKI ´es a BME IIT kooper´aci´oja keret´eben. A robot-helikopterek protot´ıpusainak kutat´as´ahoz elengedhetetlen egy megb´ızhat´o ´es gyors helyzetmeghat´aroz´o megold´as. Ezt a feladatot k´epfeldolgoz´assal k´ıv´antuk megoldani, mivel a felmer¨ ul˝o egy´eb m´odszerek mellett ez az u ´t t˝ unt a legink´abb j´arhat´onak. K´et, alapvet˝oen elt´er˝o konstrukci´o j¨ott sz´oba: • Az els˝o v´altozat helikopterre szerelt markereket, k¨ uls˝o kamer´akat ´es f¨oldi feldolgoz´oegys´eget haszn´al. A sz´am´ıtott helyzetet r´adi´okapcsolaton lehet elk¨ uldeni a 6szabads´agfok´ u mobilis robotnak. Emiatt ez a megold´as er˝osen helyhez k¨ot¨ott (ami belt´eri m˝ uk¨od´es eset´en mell´ekes), viszont k¨onnyebben realiz´alhat´o. • A m´asodik elrendez´esben mind a kamer´ak, mind a feldolgoz´orendszer a helikopteren lehet. Belt´eri helikopterek eset´eben OpenGL ES 2.0-s szabv´anynak megfelel˝o ’Handheld-PC’ szint˝ u sz´am´ıt´og´epek j¨ohetnek sz´oba k´epfeldolgoz´o egys´egk´ent, ez esetben ´erdemes a laborat´oriumba telep´ıtett markerekkel cs¨okkenteni a sz´am´ıt´asig´enyt. K¨ ult´eri (n´emileg er˝osebb) helikopterek eset´eben OpenCL 1.1 kompatibilis mobilis
˝ MOTIVACI ´ O ´ 1 BEVEZETO,
6
sz´am´ıt´og´epek sz´am´ıt´asi teljes´ıtm´enye sz¨ uks´eges, mivel a k¨ornyezetr˝ol nem k´ıv´anunk semmit sem felt´etelezni. A projekt el˝orehalad´asa ´erdek´eben az els˝o v´altozatot kellett z´aros hat´arid˝on bel¨ ul elk´esz´ıteni, a m´asodik elrendez´es j¨ov˝obeni kutat´asokat alapoz meg. A SAFT detektorral ´es a robothelikopterrel kapcsolatos k´et kutat´asi feladat nem szepar´alt, mindk´et ter¨ uleten el´ert eredm´enyek felhaszn´alhat´ok, illetve sz¨ uks´egesek egy k¨ ult´eri helikopter fed´elzet´en v´egzett vizu´alis navig´aci´ohoz.
1.2.
Kutat´ asi m´ odszerek
Az elm´eleti kutat´ast, levezet´eseket kezdetben pap´ıron v´egeztem. Egy-k´et hiba igen sok´aig rejtve maradt, ez´ert kipr´ob´altam a sz´am´ıt´og´epes levezet´es k´epess´egeit. A MATLAB szimbolikus toolbox ´allt a rendelkez´esemre, ami gyakorlatilag a Maple szolg´altat´asait haszn´alja. A toolbox k´epess´egei vegyesek, egyszer˝ ubb kifejez´eseket igen hat´ekonyan egyszer˝ us´ıt, de egy ¨osszetett azonoss´ag k´et oldal´anak k¨ ul¨onbs´eg´et ritk´an k´epes null´ara reduk´alni. Hamar kider¨ ult, hogy sokkal haszn´alhat´obb a levezet´esek ellen˝orz´es´ere, mint azok elv´egz´es´ere. Sajnos m´atrixokkal kapcsolatos o¨sszef¨ogg´eseket nem ismer (vagy nem alkalmazza azokat hat´ekonyan). A toolbox integr´al´asi k´epess´egei j´ol haszn´alhat´ok voltak. A levezet´esek alapj´an ad´od´o m´odszerek a´ltal´aban m´atrixokat tartalmaztak. Ezeket legink´abb az´ert el˝ony˝os MATLAB alatt kipr´ob´alni, mert l´ep´esenk´enti futtat´as eset´en az interpreterben b´armely haszn´alt m´atrix saj´at, illetve szingul´aris ´ert´ekeit le lehet k´erdezni. M´ern¨oki szempontb´ol egy ´altal´anos (pl. 6 × 6-os) m´atrix elemeinek list´aja alig mond valamit, a saj´atvektor-saj´at´ert´ek felbont´asa viszont m´ar elegend˝o t´ampontot ny´ ujt hibakeres´es k¨ozben. A MATLAB interpreter jellege viszont komoly h´atr´any a fut´asi id˝ok tekintet´eben. MATLAB-on bel¨ ul k´et lehet˝os´eg van a gyors´ıt´asra: A ciklusok m´atrixm˝ uveletekk´e val´o konvert´al´as´aval, illetve C f¨ uggv´enyek .mex-´allom´anny´a val´o ford´ıt´as´aval. El˝obbi eset´eben a k´od olvashat´os´aga, ut´obbi esetben a rendelkez´esre a´ll´o m´atrixm˝ uveletek ´es a hibakeres´es lehet˝os´ege esik ´aldozatul. A gyakorlati kutat´asi munk´ahoz MS Visual Studio-t haszn´altam C++ programok fejleszt´es´ere. Ebben a k¨ornyezetben teszteltem az egyes template funkci´ok megval´os´ıthat´os´ag´at. Az egyes, operator overloaddal kapcsolatos megold´asok o¨sszehasonl´ıt´as´ahoz a ford´ıtott ´es optimaliz´alt k´odot vizsg´altam (’show disassembly’ opci´o). Szint´en ezt a fejleszt˝ok¨ornyezetet haszn´altam a grafikus processzorok (GPUk) k´epfeldolgoz´asban haszn´alhat´o k´epess´egeinek vizsg´alat´ahoz, tov´abb´a az elk´esz¨ ult f¨ uggv´enyk¨onyvt´ar ´es a n´egyrotoros helikopter vizu´alis navig´aci´oj´at megval´os´ıt´o alkalmaz´as implement´al´as´ahoz. A m´atrixokat intenz´ıven haszn´al´o 3-dimenzi´os rekonstrukci´os f¨ uggv´enyek tesztel´ese p´arhuzamos debuggol´assal t¨ort´ent. A m´ar m˝ uk¨od˝o, de lass´ u MATLAB k´od ´es annak C++ v´altozata
1.2 Kutat´asi m´odszerek
7
egyszerre futott l´ep´esenk´ent a k´et rendszerben. Mivel egyes numerikus feladatok megold´asa nem egy´ertelm˝ u (SVD, roots), a k´et k¨ornyezet akkor is elt´er˝o r´eszeredm´enyeket adott ugyanarra a bemenetre, ha mindkett˝o helyesen m˝ uk¨od¨ott. Ezt a probl´em´at az ilyen eredm´enyek o¨sszevet´es´ere ´es m´odos´ıt´as´ara l´etrehozott f¨ uggv´enyek haszn´alata oldotta meg.
´ EREDMENYEK ´ 2 UJ
8
2.
Az u ´ j tudom´ anyos erdem´ enyek ¨ osszefoglal´ asa
2.1.
A ’Self Affine Feature Transform’ geometriai k´ epess´ egei
Az affin Lucas-Kanade (LK) feladat bizonyos bemenetek eset´en egy szingul´aris m´atrix invert´al´as´ahoz vezet. Az adott m´atrix nulla saj´at´et´ek´ehez (´ert´ekeihez) tartoz´o saj´atvektor(ok) az adott k´epr´eszlet fontos geometriai tulajdons´agait reprezent´alj´ak. A kifejlesztett ’Self Affine Feature Transform’ (SAFT) detektor m˝ uk¨od´ese sor´an a vizsg´alt k´epet vezetj¨ uk az affin LK detektor mindk´et bemenet´ere, ´es a k¨ozb¨ uls˝o l´ep´esk´ent kiad´od´o 6 × 6-os m´atrixot vezetj¨ uk a kimenetre. A sz´am´ıt´asi szab´alyt a k¨ovetkez˝o k´eplet adja meg: M=
Z
(pH ⊗ g)(pH ⊗ g)T wdA,
(1)
ahol g a k´epen m´ert gradiens, pH a homog´en poz´ıci´o, w az ablakoz´o f¨ uggv´eny ´es M a kiad´od´o SAFT m´atrix. Ennek a m´atrixnak 18 f¨ uggetlen eleme van, val´oj´aban ez egy 2 · 2 × 3 · 3-as szimmetrikus tenzor. A kisz´am´ıt´ashoz haszn´alt koordin´atarendszer transzform´aci´oit´ol val´o f¨ ugg´es ezt j´ol mutatja. A m´odszer seg´ıts´eg´evel a k¨ovetkez˝o feladatok oldhat´ok meg: • V´altozatos gemoetriai mennyis´egek meghat´aroz´asa (z´art kifejez´esek haszn´alat´aval): – K¨or(´ıv) k¨oz´eppontja, sugara. – K´ upszeletek param´eterei. ¨ – Osszetar´ o egyenesek metsz´espontja, ak´ar a vizsg´alati ablakon k´ıv¨ ul is. – Elliptikus spir´alok emelked´ese, egy´eb param´eterei. • Alakzatok oszt´alyoz´asa a le´ır´oba foglalt inform´aci´o alapj´an. • Alakzatok affin normaliz´al´asa. A m´odszer kiterjeszthet˝o homog´en, t´erbeli es projekt´ıv esetre is, r´aad´asul a t´erbeli kiterjeszt´essel a m´asik kett˝o kombin´alhat´o. A homog´en kiterjeszt´esnek k´epp´aros´ıt´es eset´en van gyakorlati jelent˝os´ege, m´ıg a t´erbeli kiterjeszt´es speci´alis eseteit r´eg´ota ismerik ´es haszn´alj´ak 3-dimenzi´os t´argyak m´ern¨oki visszafejt´es´ere. 1. T´ eziscsoport. Az Affin Lucas-Kanade detektor szingul´aris bemeneteinek a vizsg´alata ¨ alapj´an kifejlesztettem a Self Affine Feature Transform m´odszert (Onaffin K´epjellemz˝o Transzform´aci´ot), amely m´odszer t¨obbf´ele gemoetriai inform´aci´ot k´epes robusztus m´odon kinyerni a vizsg´alt k´epr´eszletekb˝ol. Kapcsol´od´o publik´aci´ok: [S7, S11, S5]
2.1 A SAFT detektor
9
2. ´abra. Tipikus k´epek, amelyek analiz´al´as´ahoz az 1. t´eziscsoportban bemutatott m´odszerek j´ol alkalmazhat´ok. 1.1. T´ ezis. Kidolgoztam a Self Affine Feature Transform m´odszer formalizmus´at ´es koordin´ata-transzform´aci´os szab´alyait. A m´odszerrel kinyert le´ır´o (m´atrix) a k´epr´eszletek affin transzform´aci´okkal szemben mutatott ´erz´ekenys´eg´et tartalmazza kompakt form´aban. Szab´ alyt adtam a sz´am´ıt´asok k¨ozben haszn´aland´o koordin´atarendszer optim´alis megv´alaszt´as´ara a feldolgoz´asi ablak alakj´anak f¨ uggv´eny´eben. Kidolgoztam a m´odszer 3-dimenzi´os, illetve projekt´ıv kiterjeszt´eseit, ´es bemutattam alkalmazhat´os´agukat. ´ 1.2. T´ ezis. Araml´ as- ´es alakzat-oszt´alyoz´o m´odszereket dolgoztam ki, melyek a 6 × 6-os SAFT m´atrix vizsg´alat´an alapulnak. Korl´atozott diagonaliz´aci´ot alkalmaztam az algebrai diagonaliz´aci´o numerikusan ´erz´ekeny eseteinek elker¨ ul´es´ere. 1.3. T´ ezis. M´odszereket fejlesztettem, melyek k´epesek v´altozatos geometriai inform´aci´ okat kinyerni a SAFT le´ır´o m´atrix´ab´ol. Mind oszt´alyf¨ ugg˝o, mind ´altal´anos esetben alkalmazhat´ o m´odszereket adtam. Az alakzat oszt´alyt´ol f¨ ugg˝o m´odszerek finoman viselkednek az adott oszt´alyon k´ıv¨ uli bemenetek eset´eben is, k´epesek kisz´am´ıtani annak a folytonos m´ert´ek´et, hogy mennyire teljes¨ ul az adott oszt´alyhoz tartoz´as hipot´ezise.
´ EREDMENYEK ´ 2 UJ
10
(a)
(b)
(c)
(d)
3. a´bra. A bemutatott m´odszerek ´altal detekt´alt geometriai mennyis´egek a k´epekre rajzolva j´ol mutatj´ak a SAFT detektor egyes k´epess´egeit. (a): K´et invari´ans a´raml´ast eredm´enyez˝o k´ upszeletek egyenletei z´art alakban megkaphat´ok. (b): A forgat´as, illetve a sk´al´az´as k¨oz´eppontja m´eg az ide´alist´ol t´avol es˝o bemenetekre is meghat´arozhat´o. (c): Az egys´egnyi hib´at ad´o a´raml´asok akkumul´alt sebess´eg-eloszl´as´anak minimuma a k´ep egyik legkarakterisztikusabb pontja. (d): Az akkumul´alt sebess´eg-eloszl´as oszt´alyf¨ uggetlen normaliz´al´asra is alkalmazhat´o.
2.2 K´epr´eszlet p´aros´ıt´as
2.2.
11
A ’Self Affine Feature Transform’ haszn´ alata hasonl´ o k´ epr´ eszletek p´ aros´ıt´ as´ ahoz
A SAFT detektor alkalmas k´epr´eszletek hasonl´os´ag´anak meg´allap´ıt´as´ara, ha t¨obb k´epfrekvenci´at is figyelembe vesz¨ unk. A gyakorlatban h´arom s´av haszn´alata elegend˝onek bizonyult, ez 54 dimenzi´os le´ır´ovektort eredm´enyez. Egy s´av kisz´am´ıt´as´anak t´ag ´ertelemben v´eve 5 param´etere van, ezek k¨oz¨ ul a h´arom legjelent˝osebb hat´as´at vizsg´altam. A lehets´eges ut´ofeldolgoz´asok 36-f´ele kombin´aci´oj´at vizsg´altam. A m´odszer vizsg´alat´ahoz sz¨ uks´eg van egy kulcshelyzet-lokaliz´al´o elj´ar´asra. Erre a c´elra a SIFT m´odszer vonatkoz´o r´eszeit haszn´altam. A SIFT m´odszer p´aros´ıt´asi k´epess´egeit referenciak´ent haszn´altam az u ´j le´ır´o teljes´ıtm´eny´enek meg´allap´ıt´as´ahoz, illetve az optim´alis param´eterez´es meghat´aroz´as´ahoz. Az els˝o t´eziscsoportban felhaszn´alt ¨osszef¨ ugg´esek a k´epp´aros´ıt´asi folyamat sz´amos egy´eb r´eszfeladata eset´eben is felhaszn´alhat´ok. Mivel ez el˝ore prognosztiz´alhat´o volt, ez´ert az ilyen k´epess´egek plusz motiv´aci´ot jelentettek a k´epr´eszlet-p´aros´ıt´asi k´epess´egek vizsg´alatakor. A legfontosabb ilyen k´epess´eg, hogy a SAFT le´ır´o haszn´alat´aval lehet˝os´eg ny´ılik megmondani, hogy k´et k´epr´eszlet p´aros´ıt´asa milyen dimenzi´okban mennyire k¨oti meg a haszn´alt transzform´aci´os modell param´etereit. Ha a SAFT (illetve a Harris) detektort v´egtelen (> 2.5σ) kiterjed´es˝ u Gauss-ablakon ´ert´ekelj¨ uk ki, akkor a k´odolt inform´aci´o le´ırja a Harris detektornak az integr´al´asi ablakt´ol val´o f¨ ugg´es´et. Ez az eredm´eny a m´odszert a kulcshelyzetek meghat´aroz´as´aval is kapcsolatba hozza. 2. T´ eziscsoport. Megmutattam, hogy az ´altalam kifejlesztett Self Affine Feature Transform alkalmazhat´o hasonl´o k´epr´eszletek p´aros´ıt´asi feladat´ahoz, amennyiben t¨obb k´epfrekvenci´ at is felhaszn´alunk. A k´epr´eszletet le´ır´o vektorok kinyer´ese ´es ut´ofeldolgoz´asa sor´an haszn´ alt param´eterek optim´alis ´ert´ekeinek meghat´aroz´asa ´erdek´eben r´eszletes ´es kimer´ıt˝o keres´est v´egeztem. Megmutattam, hogy a SAFT jellemz˝o analitikus volta olyan k´epess´egeket eredm´enyez, amelyek j´ol haszn´alhat´ok a k´epp´aros´ıt´asi folyamat sz´amos r´eszfeladat´ anak megold´asakor. Le´ırtam a SAFT k´epjellemz˝o koordin´ata-transzform´aci´okt´ol, illetve az integr´al´asi s´ ulyf¨ uggv´eny alakj´at´ol val´o f¨ ugg´es´et. Ezeknek az ¨osszef¨ ugg´eseknek a lineariz´ al´ asa megmutatta a SAFT m´odszer kapcsolat´at a Harris detektoron alapul´o Affin Adapt´aci´oval. Kapcsol´od´o publik´aci´ok: [S8, S9, S4] 2.1. T´ ezis. Bebizony´ıtottam, hogy az ´altalam kidolgozott Self Affine Feature Transform alkalmazhat´o hasonl´o k´epr´eszletek p´aros´ıt´asi feladat´ahoz, amennyiben t¨obb k´epfrekvenci´ at is felhaszn´alunk. R´eszletesen bemutatattam, hogy a k´epjellemz˝o-sz´am´ıt´as param´eterei hogyan v´alasztand´ok meg az egyes esetekben. Megmutattam, hogy a h´arom s´avot haszn´ al´ o 54-dimenzi´os SAFT-54 le´ır´ovektor teljes´ıtm´enye meghaladhatja a 128-dimenzi´os SIFT m´odszer´et.
´ EREDMENYEK ´ 2 UJ
12
(a)
(b)
4. ´abra. A k´epp´aros´ıt´asi k´epess´egek tesztel´es´ere haszn´alt tipikus k´epsorozatok 2.2. T´ ezis. Megmutattam, hogy a SAFT jellemz˝o analitikus volta olyan k´epess´egeket eredm´enyez, amelyek j´ol haszn´alhat´ok a k´epp´aros´ıt´asi folyamat egyes r´eszfeladatainak megold´asakor: • A k´epjellemz˝o sz´am´ıthat´o konvol´ uci´o seg´ıts´eg´evel, felhaszn´alva annak tiszt´an integr´alis term´eszet´et, mely pl. anizotr´op ablakoz´as eset´eben el˝ony¨os. • K´et k´epr´eszlet k¨oz¨ott meghat´arozhat´o a minim´alis n´egyzetes pixeldifferenci´at ad´o elforgat´as. • K´epes olyan k´epr´eszletek detekt´al´as´ara ´es ¨osszehasonl´ıt´as´ara, amelyek tartalma invari´ans valamilyen transzform´aci´ora (tipikusan ´elek ´es g¨orb´ek lehetnek ilyenek, az ilyen r´eszleteket t¨obb elterjedt m´oszer nem k´epes felhaszn´alni) • A SAFT m´odszer seg´ıts´eg´evel meghat´arozhat´o a kapott transzform´aci´os modellek n´egyzetes pixeldiferencia ´ertelm´eben vett hib´aja. A vizsg´alt k´epr´eszletek tartalm´at fi-
2.2 K´epr´eszlet p´aros´ıt´as
13
gyelembe v´eve z´art alakban megadja a kulcster¨ ulet-p´aros´ıt´asok okozta hib´aknak a transzform´aci´o param´etereit˝ol val´o m´asodfok´ u f¨ ugg´es´et. 2.3. T´ ezis. A Gauss-f¨ uggv´eny speci´alis tulajdons´agait ´es a SAFT k´epjellemz˝o ut´olagos koordin´ata-transzform´alhat´os´ag´at felhaszn´alva megmutattam, hogy a SAFT m´odszer formalizmusa ekvivalens a Harris detektort haszn´al´o Affin Adapt´aci´o lineariz´alt v´altozat´aval. Ez u ´j k¨ozel´ıt˝o m´odszerek haszn´alat´at teszi lehet˝ov´e mindk´et m´odszer ki´ert´ekel´ese eset´eben. 2.4. T´ ezis. M´odszert dolgoztam ki k´epjellemz˝o-vektorok n´egyzetes pixeldifferencia ´ertelm´eben vett optim´alis line´aris s´ ulyoz´as´anak meghat´aroz´as´ara. A kapott eredm´enyeket a SAFT le´ır´ora alkalmazva analitikus kifejez´est adtam, amely a haszn´alt Gauss-ablak kiterjed´es´enek f¨ uggv´eny´eben megadja a s´ ulyoz´om´atrix elemeinek optim´alis m´ert´ek´et.
(a)
(b)
(c)
(d)
5. a´bra. A SAFT-54 k´epr´eszlet-le´ır´o seg´ıts´eg´evel tal´alt hasonl´o r´eszletek. A nyilak az a´tlagos s´ıkhoz k´epesti diszparit´ast, azaz a projekt´ıv m´elys´eget jel¨olik
´ EREDMENYEK ´ 2 UJ
14
2.3.
N´ egyrotoros, auton´ om belt´ eri helikopter vizu´ alis navig´ aci´ oja
A tansz´eken ´ep´ıtett belt´eri helikopter ir´any´ıt´asi k´erd´eseinek vizsg´alat´ahoz sz¨ uks´egess´e v´alt egy abszol´ ut m´er´esi eredm´enyeket szolg´altatni k´epes vizu´alis navig´aci´os rendszer kifejleszt´ese. A realiz´aci´o sor´an sz´amos olyan probl´ema mer¨ ult fel, melyek megold´asa tudom´anyos megk¨ozel´ıt´est ig´enyelt, s amelyek megold´asa n´elk¨ ul a tudom´anyos kutat´omunka nem lenne elv´egezhet˝o a val´osidej˝ u felt´etelek ´es belt´eri k¨or¨ ulm´enyek mellett. Ezeket az eredm´enyeket mutatja be a harmadik t´eziscsoport. A h´aromdimenzi´os helyzet le´ır´asa mag´aban foglalja a t´erbeli orient´aci´o kezel´es´et. A robotikai, k´epfeldolgoz´asi ´es grafikai alkalmaz´asok vonatkoz´o r´eszeiben meg kell oldani az inverz Rodrigues feladatot. Az elterjedt algebrai m´odszerekn´el pontosabb, illetve biztons´agosabb, geometriai szeml´elet˝ u m´odszert adtam a feladat megold´as´ara. A k´epp´aros´ıt´asi feladat sor´an legt¨obbsz¨or epipol´aris viszonyoknak megfelel˝o modell illeszkedik a m´er´esekre. A m´er´esi eredm´enyekb˝ol el˝o´all´ıtott esszenci´alis m´atrix dekompoz´ıci´oja sz¨ uks´eges a t´erbeli elrendez´es kisz´am´ıt´as´ahoz. Az irodalomban elterjedt algebrai megold´as jelent˝os hib´akat okozott, ez´ert ezeket egy geometriai szeml´elet˝ u megold´assal kellett megsz¨ untetni. A t´ezicsoport tov´abbi r´esz´eben a helikopter vizu´alis navig´aci´oj´anak val´osidej˝ u m˝ uk¨od´es´ehez sz¨ uks´eges eredm´enyeket mutatom be. A kutat´as alatt fejlesztett k´epfeldolgoz´o f¨ uggv´enyk¨onyvt´ar sz´amos olyan u ´jszer˝ u elemet tartalmaz, amelyek alkalmaz´asa n¨oveli az egyes implement´aci´ok min˝os´eg´et ´es cs¨okkenti a fut´asid˝ot. A fut´asid˝o cs¨okken´ese az´ert is jelent˝os, mert sok m´as modellilleszt´esi feladatban haszn´alhat´o a robusztuss´ag n¨ovel´es´ere. A kifejlesztett f¨ uggv´enyk¨onyvt´ar k´et f˝o komponense a k´epek manipul´al´as´at grafikus proceszszorokon v´egz˝o ´es a m´atrixokkal kapcsolatos szolg´altat´asokat ny´ ujt´o modulokb´ol a´ll.
6. a´bra. A robothelikopter felkapcsolt markerekkel. (A sz´ınek be´eg´es´enek elker¨ul´es´ehez a z´arid˝ot le kell venni, emiatt zajos a k´ep)
2.3 Robothelikpter navig´aci´oja
15
´ algoritmusokat ´es val´osidej˝ 3. T´ eziscsoport. Uj u m´odszereket dolgoztam ki belt´eri auton´ om n´egyrotoros helikopterek vizu´alis navig´aci´oj´anak megval´os´ıt´as´ahoz. A gyakorlatban sz´eles k¨orben elterjedt algoritmusokat korrig´altam, hogy elker¨ uljem ezek nem megfelel˝o m˝ uk¨od´es´et a pontoss´ag ´es a biztons´ag n¨ovel´ese ´erdek´eben. Egyes kifejlesztett m´odszereket grafikus proceszszorokra u ¨ltettem ´at, hogy lehet˝ov´e v´aljon belt´eri l´egi robotok poz´ıci´oj´anak ´es orient´aci´oj´ anak val´osidej˝ u sz´am´ıt´asa, ak´ar 100 fps (k´epkocka/m´asodperc) sebess´eggel is. Kapcsol´od´o publik´aci´ok : [S6, S2, S3, S10, S1] 3.1. T´ ezis. Geometriai megold´ast adtam az inverz Rodrigues feladat olyan szingularit´asainak a kezel´es´ere, amelyek ´eles alkalmaz´asokban kritikus hib´akat okozn´anak. A kifejlesztett algoritmus egyszer˝ ubb, mint m´as megold´asok. Bizony´ıtottam, hogy a m´odszer a helyes kimenetet szolg´altatja b´armilyen bemenet mellett. ´ megold´ast dolgoztam ki a sztere´o k´epfeldolgoz´asban haszn´alt esszenci´ 3.2. T´ ezis. Uj alis m´atrix dekompoc´ıci´oja pontoss´ag´anak n¨ovel´es´ere. A m´odszer mind az esszenci´alis m´ atrix ´altal hordozott inform´aci´ot, mind pedig a pont-pont megfeleltet´eseket felhaszn´alja, m´ıg a szokv´anyos megold´asok az ut´obbi adatokra nem t´amaszkodnak. Egy egzakt ´es egy lineariz´ alt megold´ast is kidolgoztam. 3.3. T´ ezis. Tudom´anyos ig´enyek megfogalmaz´asa seg´ıts´eg´evel u ´jszer˝ u val´osidej˝ u megold´asokat fejlesztettem ki, melyek auton´om n´egyrotoros belt´eri robot-helikopterek ir´any´ıt´asi ´es navig´aci´os k´erd´eseinek kutat´as´ahoz alkalmazhat´ok. Ezen megold´asok seg´ıts´eg´evel olyan m´er´esek, illetve k´ıs´erletek is elv´egezhet˝ok, amelyekre kor´abban nem volt lehet˝ os´eg a fenn´all´o val´osidej˝ u korl´atoz´asok ´es belt´eri peremfelt´etelek mellett. Egyes kifejlesztett m´odszereket grafikus processzorokon val´os´ıtottam meg, melynek eredm´enyek´eppen a belt´eri l´egi robotok poz´ıci´oja ´es orient´aci´oja ak´ar n´egy kamera egy¨ uttes k´epfriss´ıt´es´enek u ¨tem´eben is sz´amolhat´o. Az el´ert fut´asi id˝o j´ol illeszkedik az inerci´alis m´er˝oegys´eg mintav´etelez´es´ehez ´es az ir´any´ıt´asi algoritmus id˝oz´ıt´es´ehez.
(a)
(b)
7. ´abra. Az el˝ofeldolgoz´as k¨ozben kiad´od´o k´epek r´eszletei
´ 3 ALKALMAZAS
16
3.
Alkalmaz´ as
Az els˝o t´eziscsoport elm´eleti eredm´enyeinek alkalmaz´as´ara keretrendszert fejlesztettem, mely az egyes k´epr´eszletekb˝ol kinyert geometriai mennyis´egeket felrajzolja a k´epekre. Ennek seg´ıts´eg´evel vizsg´alhat´ok az adott m´odszer k´epess´egei, illetve robusztuss´aga. A m´asodik t´eziscsoport (k´epp´aros´ıt´asi k´epess´egek) eredm´enyei r´eszben elm´eleti, r´eszben gyakorlati jelleg˝ uek. Az ilyen m´odszerek ellen˝orz´ese kiz´ar´olag a gyakorlati teljes´ıtm´eny¨ uk alapj´an m´erhet˝o, ez´ert a kutat´omunka egyik fontos r´esze volt, hogy egy m˝ uk¨od˝o k´epp´aros´ıt´asi rendszer le´ır´o-gener´al´o kompnenseit lecser´eltem a SAFT detektorra. A rendszert sz´amos egy´eb helyen kellett m´odos´ıtani, hogy a param´eterek automatikus tesztel´ese lehet˝ov´e v´aljon. Az ´ıgy el˝oa´llt rendszerben statikus t´erbeli jelenetekr˝ol k´esz¨ ult k´epek k¨oz¨otti geometriai viszony emberi beavatkoz´as n´elk¨ ul meghat´arozhat´o a SAFT detektor haszn´alat´aval. A radi´alis torz´ıt´as korrekci´oja m´eg nem automatikus, az optik´at off-line kalibr´alni kell a haszn´alt ny´ıl´assz¨og f¨ uggv´eny´eben. A bemutatott eredm´enyek a Budapesti M˝ uszaki Egyetem Ir´any´ıt´astechnika ´es Informatika Tansz´ek´en v´egzett OTKA K71762 (2008-2012) ”Auton´om f¨oldi, l´egi ´es vizi robotok korszer˝ u ir´any´ıt´aselm´elete ´es mesters´eges intelligencia eszk¨ozei” kutat´asi projekt keret´eben r´eszben alkalmaz´asra ker¨ ultek, illetve ezen kutat´asi projekt szempontjai alapj´an lettek kifejlesztve. Az OTKA K71762 t´amogat´as´ert ez´ uton is szeretn´em kifejezni k¨osz¨onetemet. Az elk´esz¨ ult robothelikopter-protot´ıpus ir´any´ıt´as´anak fejleszt´ese, illetve kutat´asa jelenleg is az itt bemutatott vizu´alis navig´aci´os megold´asok haszn´alat´aval t¨ort´enik. A rendszer p´ar millim´eteres pontoss´aggal, illetve 100 fps sebess´eggel detekt´alja a helikopter helyzet´et. A helikopteren 9 marker van elhelyezve, b´armelyik kitakar´asa eset´en is helyes eredm´enyt ad a rendszer. A rendszer m´ar t¨obb rep¨ ul´esi o´r´at abszolv´alt, a k´epfeldolgoz´as eseti hib´ai mindig abb´ol ad´odtak, ha t´ ul sok marker v´alt a kamera ´altal l´athatatlann´a. Jelenleg a rendszer egy kamera k´epe ´es t¨obb felsz´all´as el˝ott felvett k´ep alapj´an m˝ uk¨odik. L´enyeges kiemelni, hogy a j¨ov˝oben fom´aci´oban halad´o j´arm˝ uegy¨ uttesek k´epfeldolgoz´asi feladatainak val´osidej˝ u ell´at´as´at kell a rendszernek megval´os´ıtania, az eddig elk´esz¨ ult r´eszek ennek szem el˝ott tart´as´aval k´esz¨ ultek. A munka szakmai tartalma kapcsol´odik a ”Min˝os´egorient´alt, ¨osszehangolt oktat´asi ´es K+F+I strat´egia, valamint m˝ uk¨od´esi modell kidolgoz´asa a M˝ uegyetemen” c. projekt szak´ ´ mai c´elkit˝ uz´eseinek megval´os´ıt´as´ahoz. A projekt megval´os´ıt´as´at az UMFT TAMOP-4.2.1/B09/1/KMR-2010-0002 programja t´amogatja. A kutat´asi eredm´enyek nemzetk¨ozi ´es hazai idegennyelv˝ u foly´oiratcikkek ´es nemzetk¨ozi konferenciacikkek r´ev´en v´altak ismertt´e a tudom´anyos ´eletben.
´ PUBLIKACI ´ OK ´ SAJAT
17
Saj´ at publik´ aci´ ok [S1] P. Fodor and Z. Proh´aszka. M´atrixm˝ uveletek integr´al´asa a gpcv++ k´epfeldolgoz´asi k¨onyvt´ar fejleszt´ese sor´an. In Proceedings of: 7th Conference of Hungarian Association ´ for Image Processing and Pattern Recognition (KEPAF2009), pp. 1–8, 2009. [S2] L. Kis, Z. Proh´aszka, and G. Regula. Calibration and testing issues of the vision, inertial measurement and control of an autonomous indoor quadrotor helicopter. In Proceedings of: RAAD 17th International Workshop on Robotics in Alpe-Adria-Danube Region, pp. 1–10, 2008. [S3] L. Kis, Z. Proh´aszka, and G. Regula. Calibration and testing issues of the vision, inertial measurement and control system of an autonomous indoor quadrotor helicopter. International Journal of Mechanics and Control, 1(10):29–38, 2009. [S4] Z. Proh´aszka. Connection of the harris detector-based affine adaptation and the self affine feature transform Accepted to: 8th Conference of Hungarian Association for Image ´ Processing and Pattern Recognition (KEPAF-2011). [S5] Z. Proh´aszka. Formulation of 3d and projective extensions of the self affine feature transform Accepted to: 8th Conference of Hungarian Association for Image Processing ´ and Pattern Recognition (KEPAF-2011). [S6] Z. Proh´aszka. Qnx-based realization of the control system of a puma-like robot. In Proceedings of: RAAD 11th International Workshop on Robotics in Alpe-Adria-Danube Region, pp. 399–404, 2002. [S7] Z. Proh´aszka. Affine invariant features from self-flow. In Proceedings of: RAAD 17th International Workshop on Robotics in Alpe-Adria-Danube Region, pp. 1–10, 2008. [S8] Z. Proh´aszka. Fine tuning of quasi linear feature descriptors. In Proceedings of: 7th Conference of Hungarian Association for Image Processing and Pattern Recognition ´ (KEPAF2009), pp. 1–8, 2009. [S9] Z. Proh´aszka. Matching image details with the self affine feature transform. In Proceedings of: V. Magyar Sz´am´ıt´og´epes Grafika ´es Geometria Konferencia, pp. 206–213, 2010. [S10] Z. Proh´aszka and A. Kerti. Development of the gpu based gpcv++ image processing library. In Proceedings of: IV. Magyar Sz´am´ıt´og´epes Grafika ´es Geometria Konferencia, pp. 102–107, 2007.
18
´ PUBLIKACI ´ OK ´ SAJAT
[S11] Z. Proh´aszka and B. Lantos. Extracting geometric information from images with the novel self affine feature transform. Accepted to: Periodica Polytechnica, Electrical Engineering, 2010. Accepted:2010 Feb.
´ IRODALOMJEGYZEK
19
Irodalomjegyz´ ek [1] H. Bay, A. Ess, T. Tuytelaars, and L. Van Gool. Surf: Speeded up robust features. Computer Vision and Image Understanding (CVIU), 110(3):346–359, 2008. [2] R. Blake and R. Sekuler. Perception. McGraw-Hill, 5 edition, 2005. [3] C. Harris and M. Stephens. A combined corner and edge detector. In 4th Alvey Vision Conference, pages 147–151, 1988. [4] R. I. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision. Cambridge University Press, ISBN: 0521540518, second edition, 2004. [5] Y. Ke and R. Sukthanar. Representation for local image descriptors. In Proc. Conf. Computer Vision and Pattern Recognition, pages 511–517, 2004. [6] Tony Lindeberg. Detecting salient blob-like image structures and their scales with a scale-space primal sketch:a method for focus-of-attention. International Journal of Computer Vision, 11(3):283–318, 1993. [7] Tony Lindeberg. Scale-space theory: A basic tool for analysing structures at different scales. Journal of Applied Statistics, 21(2):225–270, 1994. [8] D. Lowe. Object recognition from local scale-invariant features. In Int’l Conference on Computer Vision, pages 1150–1157, 1999. [9] B. D. Lucas and Takeo Kanade. An iterative image registration technique with an application to stereo vision. In Imaging Understanding Workshop, pages 121–130, 1981. [10] J. Matas, O. Chum, M. Urban, and T. Pajdla. Robust wide-baseline stereo from maximally stable extremal regions. In Proc. of BMVC-02, pages 384–393, 2002. [11] Krystian Mikolajczyk and Cordelia Schmid. An affine invariant interest point detector. In Proceedings of the 7th European Conference on Computer Vision, pages 128–142. Springer, 2002. Copenhagen. [12] Krystian Mikolajczyk and Cordelia Schmid. A performance evaluation of local descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(27):1615– 1630, 2005.
