Budapesti Műszaki Főiskola Neumann János Informatikai Kar Informatikai Automatizált Rendszerek Szakirány
MOBOT (Map-maker rOBOT)
I. Irodalomkutatás 2008. október 31.
A projekt tagjai: Marton Attila Tandari János Urbán András
2
Tartalomjegyzék
Célmegfogalmazás ................................................................................................ 3 Megoldandó feladatok ........................................................................................... 3 Kontúr detektálása ................................................................................................. 3 Stereo képek összeillesztése .................................................................................. 4 Ikonikus memória alapon irányított panoramikus navigáció ................................... 5 XNA...................................................................................................................... 6 HLSL .................................................................................................................... 6 Sarokpont detektálás.............................................................................................. 7 Irodalomjegyzék.................................................................................................... 8
3
Célmegfogalmazás Projektünk célja egy olyan robot elkészítése, mely bejárva egy területet térképet készít arról, az akadályokat számon tartja egy felülnézeti térkép formájában. A robot rendelkezni fog 360 fokban körbelátó kamerával, mely mind a térképezést, mind a navigációt megkönnyíti. A robot elkészítéséhez szükséges technikák, módszerek megismeréséhez a szakirodalomhoz fordultunk, nagy részt az IEEE Transactions on Pattern Analysis and Machine Intelligence folyóiratra támaszkodva dolgoztunk.
Megoldandó feladatok A rendszer elkészítéséhez elsősorban a következő problémánkra kell megoldásokat keresnünk: Objektumok 3D-s adatainak, kontúrainak számítása Térkép ábrázolási technikák (akadályok nyilvántartása) Útkeresés ismert és ismeretlen terepen, térképinformációk és a szenzorok információi alapján A robot vezérlése, elmozdulásainak pontos becslése A következőkben mostani irodalomkutatásunk alkalmával talált általunk felhasználhatónak ítélt módszereket ismertetjük.
Kontúr detektálása Feladatunkban az objektumoknak kulcs szerepe van, így azok felismerése létfontosságú a további elemzésekhez. Az alakfelismerésnek egy nagyon jó módja, ha az elemeket körvonalaik alapján elkülönítjük a környezetétől, vagyis él-detektálást végzünk, így olyan objektumokra tehetünk szert, amelyek rendelkeznek az általunk ismert paraméterekkel, így összehasonlíthatóakká válnak korábbi méréseinkkel. Ennek a feladatnak az elvégzéséhez szükséges minden olyan lehetőséget megragadnunk, amely nem csak a tökéletesen objektumot tudja a kontúrja alapján egy felismerhető objektummá konvertálni, hanem annak egy módosított változatával is el tud boldogulni. Fontos, hogy ilyen esetekre is fel legyen készítve a rendszer, mert nagy valószínűséggel kétszer nem fogjuk tudni ugyan azt az eredményt előállítani a kamera képekből és ez sok problémát okozhatna. A kontúrok módosítását okozhatja légköri, látási viszonyok változása, vagy egyszerűen a képzaj is. Ennek a problémának a megoldása során a kontúr detektálásra a [A1] cikkben a szerzők megoldásokat keresve három lehetőséget is feltártak. Ez a három módszer a következő volt: bölcs-szegmentálás módszere (Segment-Wise), elzárásos/levágásos/elhagyásos módszer (Occluded), véletlenszerűen elhagyott pixelek módszere (Randomly Removed). A legtöbb módszer során egy-egy kontúr él leírásának az alapja a környezeti összefüggéseken és távolságokon alapul. Az összefüggéseket egy objektumnál az adott kontúr leírásához logaritmus alapú koordináta rendszerben meghatározott hisztogramokkal valósítják meg, amely hatására megkapják a pont egy meghatározott környezetében fellelhetően kapcsolatban álló pontokat, amely hatására a kontúr előáll és az objektum leírhatóvá válik. Az alakfelismerést, ha azt egy sablon alapján szeretnénk azonosítani, akkor nem könnyű a megállapítás menete és pontossága a formák változatossága miatt. Egy egyszerű példát nézve, ha veszünk egy bögrét, akkor annak is van rengeteg kivitele, amely leírása alapján sok máshoz is hasonlíthat. Ha az a bögre hosszú törzzsel és egy nagy füllel rendelkezik, akkor azt a kontúr alapján egy más távolságból akár felismerhetjük egy sörös korsónak, vagy egy teás kancsónak is, márpedig a két dolog nem egyezik meg.
4 A megoldások során a kontúr felismeréshez, ha a levágásos módszert alkalmaznánk, abban az esetben különösen mérsékelt lenne a felismerések arányának sikeressége, hisz a levágott rész és a felismert rész határai meglehetősen különbözőek az alak leírásától. A legjobb módszernek a véletlen pixel elhagyásos módszer, amely során a kontúrok 40%-ban megtalálhatóak és ez mellett 5%-ot tart meg a későbbi feldolgozáshoz. Abban az esetben, ha a bölcs szegmentálás és az elhagyásos módszert vizsgáljuk, a távolság méréses módszer jelentősen hatékonyabban teljesít, mint a forma leírásos eset, ha a megtartott pixelek számát vizsgáljuk. A bölcs szegmentálás módszerére vonatkozó kutatási eredmények azt mutatják, hogy az egymástól mért távolságos kontúr meghatározás során a 10%-át felismerjük, és ha nem is ismerjük fel, de 20%-át megtartjuk további pontosításhoz. Ha ugyan ezt a feladatot végezzük el egy forma leírásos módszer alkalmazásával, akkor már a 20%-ot elsőre felismerjük és 40%-ot tartunk meg további elemzéshez. Az objektum felismerésnek van egy olyan hátrányos tulajdonsága, hogy a felismerhető alakok halmaza olyan tág, hogy nem lenne ésszerű pontosan azonosítani egy-egy objektumot. Ha pedig nem pontosan határozzuk meg az objektumokat, akkor a keresési terünk, amiben megfeleltetést fogunk keresni sokkal kisebb lesz, így hatékonyabbá válik a rendszerünk, legfőképpen, ha már tudjuk, hogy mit is kell keresnünk. A hatékonyságot befolyásoló tényező még az objektum kontúrjainak száma is, amely a hatékonyságot lineárisan rontja le. Feladatunkban az objektumok felismeréséhez egy jól használható módszert alkalmaz, amely a kamerákból érkező képeken a kontúr detektálás segítségével az objektumok beazonosíthatóak lesznek és azok reprezentálása egy virtuális térben lehetővé válnak. Ez lehetőséget ad a későbbi helyzetváltozások felismerésére is. Esetünkben, miután egy objektum leírással fog rendelkezni a tárgyakkal való első találkozás után, így annak a visszakeresése hatékonyabb lesz több szempontból is. Egy területen tudjuk majd, hogy mit keressünk az információ halmazunkból, amely hatására a felismerés és azonosítás lényeges hatékonyságjavulást fog eredményezni.
Stereo képek összeillesztése Feladatunkban lényeges szerepet tölt be a két darab körbelátó kamera. A két kamera a roboton mindig egy irányba néz, így a Stereo Vision egy kibővített módszerét alkalmazzuk. A két kép összeillesztése és a közös pontok által meghatározott viszonyítások során számos akadályba ütközik a módszer. A két képből, amikor egyetlen, letisztult és információ gazdag képet szeretnénk kapni, azonban a két kamerának két különböző pozíciója van, ami nehezíti a dolgot az egyes tárgyak más szögből való nézete miatt. Szükség van ezért a két kép szinkronba hozatalára, hogy a többlet információt értékelhető eredményekben tudjuk alkalmazni. Több módszer is létezik ennek a feladatnak a megoldására, de kevés olyan van, amely nem-, vagy lényegesen kis hasznos részletek vesztéssel járna. Minél több részlettel rendelkezünk, annál könnyebben és annál több régió válik detektálhatóvá. Az egyik módszer, amely megoldást kínál, az az úgynevezett terület alapú Super Vision, amely a szomszédos azonos pixeleket keresi meg annak érdekében, hogy az élesebb képet elkészíthessük. Ez a módszer azonban csak a betekintő ablakon (window size) belül ad biztos eredményt és ezen betekintő ablakon kívül eső területekkel még mindig kritikus a helyzet. Általában a kisebb ablakokat célszerű alkalmazni, mert így jobban elkerülhetőbbek a nem kívánatos kép simítások. Az optimális betekintő ablak erősen függ a textúrától és a pixelek változatosságától is. A kevésbé részletes képek, vagy nem nagyon változatos pixelértékek arra kényszerítenek minket, hogy nagyobb betekintő ablakot válasszunk annak érdekében, hogy végrehajtható legyen a keresés. Természetesen a legegyszerűbb eset az lenne, ha előre tudjuk a két kamera eltérésének szögét és távolságát, mert akkor ezek a
5 kalibrációs műveletek elhagyhatóak lennének, és előre el tudnánk forgatni a képeket. Ezeknek a módszereknek azonban alapvető problémája, hogy az eredményeinek eredményessége csak helyileg jó, globálisan nem. Globális megoldást keresve Lawrence Zitnic és Takeo Kanade [A2] arra jutottak, hogy új szempontokat kell megállapítani a két kép párosítása során. Ezek az új szempontok azok voltak, hogy a képpontokat erősen szűrni kell az a szempont szerint, hogy mennyire egyediek és hogy mennyire folytonos egyenlőtlen az eloszlásuk a teljes képen. Az egyediség vizsgálata azért bizonyult fontosnak, mert a kevésbé sűrűn előforduló pontokat, ha figyelmen kívül hagyjuk, akkor kisebb lesz a tér, amiben válogatnunk kell. Így az algoritmus számára a nagy számban előforduló pixeleket engedjük felhasználni. Ezek alapján már a két képet könnyebben tudjuk összepárosítani akár kontúr alapú eljárással, akár bal-jobb, majd jobb-bal képeken keresett hasonlóságok alapján. Végeredményünk egy olyan 3 dimenziós tömb lesz, amely tartalmazza sor, az oszlop és egy egyenlőtlenség értéket. Ebbe a tömbbe addig gyűjtöttük az eredményeket, amíg az konvergált. Külön még eltároljuk a maximális találatokat is, hogy tudjunk küszöbértékekkel is összehasonlítani. Ennek két kimenete lehetséges. Egyik esetben, ha meghaladja a maximális érték a küszöb értéket, akkor az egyenlőtlenség mértéke kerül a kimenetre, ha pedig alatta van, akkor levágásra kerül. Esetünkben, ugyan a két kamerát nem mozgatjuk el egymáshoz képest a működés során, azonban figyelembe véve, hogy egy helyzetét megváltoztatni képes roboton lesz rajta, a kisebb elmozdulásokkal számolnunk kell.
Ikonikus memória alapon irányított panoramikus navigáció Ez a megoldás egy 360 fokban körbelátni képes kamerával felszerelt robot navigálására képes, akár nagyobb területen is [A3]. Az irányt a sorozatban kapott, horizontról készült körkép-sorozatból nyeri ki, amelyet a cél megközelítése során készít. Folyamatosan, ahogy a robot halad az útvonal mentén, a bemenet összehasonlításra kerül a tárolt tér-idő irány mintával, melyhez kettős aktív kontúr modellt és a pontos robot pozíciókat használja, az irányt az aktív kontúr modell (ACM) alakzataiból becsüli meg, az érzékeltekhez rendeli a megfelelő műveleteket. Feltételezi az eljárás, hogy a robotunkban van olyan műszer, mely pontosan méri a robot elmozdulását. A metódus külön előnye, hogy változó környezetben is alkalmazható, akár a robotot körülvevő, mozgó tárgyak esetén is. Az ikonikus memória úgy készül, hogy a körbelátó kamera képének a horizontját használja fel, ami a bemeneti kép sugarak egymás mellé helyezésével történő kiterítése után, a kapott képen egy vízszintes egyenes sáv lesz. Az így kapott sávokat időrendben egymás után fűzi, feldolgozáskor ezeken a sávokon keres azonos mintákat. Ez egyben azt is jelenti, hogy viszonylag nagy táv megtétele esetén is igen memória hatékony a módszer, mivel a képekből csak a horizontot tárolja. A robot irányát, pozícióját az aktuális nézőpont, az ikonikus memória és a megjegyzett út információiból a kettősség elve alapján becsüli meg. A pozícióbecslés hibája a mért és publikált adatok szerint 0,64 cm-től 2,16 cm-ig terjedt. Az aktív kontúr modellt képszegmentálásra használják [A4]. Az általános képszegmentálás módszerekkel ellentétben az ACM zajos kép esetén is működik. A célunk, hogy olyan algoritmust találjunk, mely általánosan jó minden alakzat megtalálására, és a zárt kontúrvonalainak meghatározására. A módszer minden alakzatot egy paraméteres görbeként ábrázol. A görbékhez energiafüggvényt rendel, ily módon a kontúrdetektálás problémája egy energia minimalizációs problémává zsugorodik. A kontúrdetektálás menetének első lépése, hogy egy folyamat, vagy a felhasználó inicializál egy görbét, közel a test határaihoz (durva kontúr), ezt hívjuk snakenek. Az energia komponensek változtatásával a snake elkezd deformálódni, elmozdulni az objektum határa felé amíg ki nem alakul a kívánt görbe.
6 A talaj egyenetlenségéből adódó hibás pozícióbecslést kiküszöböléséhez kihasználták, hogy az általuk használt hiperboloid felületű tükör vetületének egy középpontja van. Ebből a tulajdonságából adódóan a bemeneti képet transzformálják egy tetszőlegesen dönthető kamera képére, és ebből és a bemeneti képből állapítják meg a pozíció pontosságát, amennyiben a dőlésszög nem nagyobb, mint 4 fok. A gyakorlati tapasztalatok azt mutatták, hogy az ebből fakadó kis kalibrálási hibák nem okoztak nagy gondot a robotnak a navigációban. A módszer tervezői által publikáltak szerint a robot feldolgozási ideje 200ms/frame volt, ami beltéri navigációra elegendő. Egy, körülbelül 110 cm-es úton 4 cm eltéréssel érte el a célt.
XNA Az XNA keretrendszer egy játékok fejlesztésére kifejlesztett rendszer. Ennek segítségével könnyen készíthetőek játékok, és egyéb directx-es alkalmazások. Projektünkben az XNA keretrendszeren keresztül használjuk a videokártya shadereit a kamerák képének előfeldolgozása felgyorsítására. [5]
HLSL A HLSL (High Level Shading Language) egy C-hez hasonló nyelv, amellyel directx alatt lehet a gpu shadereibe programot írni. A HLSL nyelvet arra fejlesztették ki, hogy directx alatt a videokártyát közvetlenül lehessen programozni. Ez elsősorban a játékokban látható effektek kibővítésére született, hogy ne csak a beépített effekteket lehessen használni, hanem saját effekteket is lehessen készíteni. A shadereknek 4 generációja létezik. Ennek eredményeképpen a programok egyre több utasításból állhatnak. A videokártyákon vertex shader, geometry shader, és pixel shader található. Ezekből számunkra a pixel shader fontos, ez ugyanis a kép minden pixelén végighaladva végez műveleteket. [6]
1. ábra [7]
7
Sarokpont detektálás Projektünkben több feladat megvalósításánál is fontos lehet a sarkok, vagy a képen látható jellegzetes pontok megkeresése és azonosítása. Erre a problémára több megoldás is létezik. Moravec sarok detektálás : Ez az egyik legelső ilyen algoritmus, amely a képen minden egyes pixelt megvizsgál, hogy egy adott környezetében, a többi pixel mennyire tér el tőle. Ezt az intenzitások négyzetes különbségével számolja. Ez minél kisebb, annál hasonlóbbak. Harris & Stephens / Plessey algoritmus : Ez az algoritmus a Moravec sarok detektálás továbbfejlesztésével született. Lényege, hogy megadott irányban keresi a hasonló pixeleket. Kanade-Tomasi arok detektálás: Ez az algoritmus a Harris sarok detektáláson alapszik. Az a különbség, hogy más módon határozza meg, hogy mikor sarok egy adott pixel. FAST feature detector: Ennek az algoritmusnak a lényege, hogy a vizsgált pixel körüli Bresenham kört vizsgálja. Ha adott számú pixelek folyamatosan világosabbak, vagy sötétebbek a vizsgált pontnál, akkor az algoritmus megjelöli jellegzetes pontként. [8]
8
Irodalomjegyzék: [1] A.Ghosh, N.Petkov: Robustness of Shape Desctiptors to Incomplete Contour Representations, IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, No. 11, Vol. 27., November 2005, (pp 1793-1803) [2] C.L.Zitnick, T.Kanade: A Cooperative Algorithm for Stereo Matching and Occlusion Detection IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE No. 7, Vol. 22., July 2000, (pp 675-684) [3] Y. Yagi, K. Imai, K. Tsuji, M. Yachida: Iconic MemoryBased Omnidirectional Route Panorama Navigation, IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, No. 1, Vol. 27, January 2005, (pp 7888). [4] Amyn Poonawala: Active Contour Models (snakes), http://www.cse.ucsc.edu/classes/ee264/Winter02/amyn.ppt, 2008. 10. 25. [5] Microsoft, Microsoft, XNA Game Studio 2.0, http://msdn.microsoft.com/en-us/library/bb200104.aspx, 2008. 10. 30 [6] Microsoft, HLSL, http://msdn.microsoft.com/en-us/library/bb509561.aspx, 2008. 10. 30 [7] Microsoft, Pipeline Stages (Direct3D 10), http://msdn.microsoft.com/en-us/library/bb205123.aspx, 2008. 10. 30 [8] Wikipédia, Corner Detection, http://en.wikipedia.org/wiki/Corner_detection, 2008.10.30
