A Google Lunar XPRIZE egyik feladata nagyfelbontású panorámaképek készítése és visszaküldése a Földre. Ez a Holdon illetve a Holdról nézve talán nem is olyan egyszerű.
Pőcze Zsolt Pulink személyes beszámolója kihívásokról, véletlenekről, megoldásokról. Vigyázat: hosszú, és meglehetősen "kockás" részek is vannak benne. Cserébe élvezetes!
Köszönjük, Zsolt!
Szerencsés véletlenek
2015-ben figyeltem fel először a Puli Space Technologies-ra, talán egy online újságban. A GLXP versenyről már a korábbi években hallottam, így pl. a Moon Express nem volt ismeretlen számomra. 2016 elején láttam meg a Puli által meghirdetett álláslehetőséget, és arra gondoltam, hogy érdemes lenne bekapcsolódnom a projektbe. Szoftverfejlesztőként mindig arról álmodtam, hogy egyszer az űrkutatásban fogok dolgozni, ezért nem hagyhattam ki egy ilyen lehetőséget.
Kiderült, hogy a holdjáró és a földi irányító szoftver fejlesztéséhez ugyanazokat a Java technológiákat alkalmazzák, amelyre a saját vállalkozásom szoftvertermékei is épülnek. Ennek a szerencsés véletlennek köszönhetően nagyon gyorsan, 2 hét alatt be tudtam kapcsolódni a projekt fejlesztésébe, így kimaradt a más cégeknél tapasztalt – sokszor idegtépően hosszú – betanulási idő. Ez annak is köszönhető, hogy
a Puli olyan elterjedt és élvonalbeli technológiákat használ, amelyekkel gyorsan lehet könnyen érthető szoftvert alkotni.
Ezzel nem ért véget a szerencsés véletlenek sorozata. Első feladatként rögtön egy érdekes és látványos eredményekkel kecsegtető képfeldolgozási probléma megoldását kaptam. A GLXP verseny – amelyre a Puli nevezett – egyik célja egy 360 fokos teljes panoráma készítése a Hold felszínén. A feladatom a Puli rover által készített fotók panorámaképpé történő összeillesztése és a kész gömbpanoráma megjelenítése volt.
Egy izgalmas feladat
Az informatika egyik leglátványosabb ága a képfeldolgozás és képmegjelenítés. Egy képszerkesztő program, mint pl. a Photoshop vagy az általam kedvelt GIMP korlátozott funkciókkal rendelkezik. Egy képfeldolgozási eljárásokat ismerő programozónak azonban szinte korlátlan lehetőségei vannak. Csak a fantázia és bizonyos matematikai korlátok szabnak határt annak, hogy mit lehet kihozni egy képből. Arról nem is beszélve, hogy az informatika teljes tárházát be lehet vetni, a gráfelméleti eljárásoktól a neurális hálózatokon át a mesterséges intelligenciáig.
Panorámaképek készítésére rengeteg megoldás készült. Kutatást végeztem, hogy kiderítsem, létezik-e olyan kész modul, amelyet beilleszthetünk a rendszerbe, akár a képillesztés vagy a képmegjelenítés oldalán. Egy komplex rendszert – a hibalehetőségek minimalizálása és a hibakeresés egyszerűsítése érdekében - célszerű egyfajta technológiára építeni, ezért elsősorban Java alapú megoldásokat kerestem, azon belül is ingyenesen használható, nyílt forráskódú modulokat.
Meglepő módon nem találtam olyan nyílt forráskódú, Java programozási nyelven írt panoráma modult, amelyet asztali alkalmazásba lehetett volna építeni és elég általános lett volna ahhoz, hogy a holdjáró szoftverében alkalmazhattuk volna.
A talált megoldások mind webes vagy Windows platformra készültek, kifejezetten földi alkalmazásra, és egyik sem volt nyílt forráskódú. Nem maradt más lehetőség, mint egy saját készítésű panorámakészítő és -megjelenítő szoftver kifejlesztése.
Kutatásom következő lépése a panorámakészítés elméleti hátterének alapos megismerése és dokumentálása volt, amely talán az egyik – szakmailag – legérdekesebb része volt a feladatnak. Ehhez újra elő kellett vennem régi egyetemi könyveimet és átismételni a már feledés homályába merült tananyagokat.
A feladat annyira szerteágazónak bizonyult, hogy a matematikai tanulmányaim majdnem teljes szélességét lefedte, megcáfolva azt az elterjedt vélekedést, mi szerint az egyetemen tanított elméleti tudás nem hasznosítható.
Részekből egész
A panorámát sok, különböző irányban készített képből kell összerakni. A kamerákból származó képek a lencsék tökéletlensége miatt torzultak. Torz képeket azonban nem lehet jól összeilleszteni, ezért az első lépésként torzítás-mentesíteni kell őket. Ez úgy történik, hogy megmérjük a lencsék görbületi jellemzőit, modellezzük a torzítást és megfordítjuk a dolgot: a torzítás fordítottját hajtjuk végre a képen. A torzítási paraméterek meghatározására találtam egy BoofCV nevű kész függvénykönyvtárat, amelyet be tudtam építeni anélkül, hogy bele kellett volna merülnöm a lencsehibák matematikai modellezésébe.
A torzításmentes képek közelítőleg megfelelnek a tökéletes lyukkamerával készített képeknek, azaz gnomonikus vetületként ábrázolják a teret. Ha a teret egy gömbfelületen képzeljük el, és a gömb pontjait a gömb középpontjából egy síkra vetítjük, gnomonikus vetületet kapunk. A gnomonikus vetület egyik fő jellemzője, hogy a kép szélei felé haladva egyre jobban megnyúlik a kép, ahogy a vetítési sugarak beesési szöge csökken. Éppen ez az oka, hogy a gnomonikus képeket nem lehet összeilleszteni. Az illesztési pontok a kép széle felé és a horizonttól távolodva egyre távolabb kerülnek egymástól. Hamar nyilvánvalóvá vált számomra, hogy illesztésnél a gnomonikus vetület helyett gömb- vagy hengervetületet kell alkalmazni, mert ott a képek nem torzulnak a kép középontjától távolodva, így egymásra illeszthetők.
A panorámaképet más szempontokból is célszerű 2 dimenziós hengervetületként elkészíteni. Egyrészt a szoftverplatformok alapból a 2D képkezelést támogatják, másrészt a hengervetület alkalmas a teljes, 360 fokos gömb panoráma tárolására úgy hogy a vízszintes tengely a 0-tól 360 fokig terjedő vízszintes szögtartományt jelenti, a függőleges tengely pedig a -90 foktól a +90 fokig terjedő függőleges szögtartományt. Továbbá a hengervetület azért is jó választás, mert a koordinátái egy az egyben megfeleltethetők a gömbfelület koordinátáival. A gömbvetületből pedig bármely más vetület elkészíthető.
A viszonyítás alapjai
A képek alakjának és illeszkedésének a méréséhez is szükség volt egy módszerre, amely képes olyan speciális képpontok automatikus kijelölésére, amelyek a torzított, átalakított képeken is jól beazonosíthatóak. A kézzel végzett képillesztés esetén az ember feladata, hogy olyan jellegzetes sarokpontokat találjon, amelyek forgatást, torzulást követően is jól felismerhetőek maradnak az átfedő képek mindegyikén. Majd ezekből a referenciapontokból pontpárokat kell alkotni, amelyek a két összeillesztendő képen a környezet azonos pontját jelölik. Az általam használt BoofCV képfeldolgozó csomag ehhez is támogatást nyújtott.
De itt is akadt probléma: a program néha nem összeillő pontokat is összekapcsolt. A probléma alapvetően az volt, hogy a használt algoritmus csak a pontok kis környezetét vizsgálta, nem nézte, hogy egymáshoz képest hol helyezkednek el. Erre kitaláltam egy megoldást: sorra vettem az egyik képen a pontokat és megnéztem, hogy a környezetükben található pontok a másik képen is ugyanúgy a környezetükben találhatók-e. Ha nem, a pontot és a párját töröltem a referenciapontok halmazából. Tulajdonképpen hasonlóan oldottam meg, ahogy az ember is teszi a kézi illesztésnél.
A képekhez rendelt referenciapont-halmazok egy olyan eszközt adtak a kezembe, amelyet később sok hasznos dologra fel tudtam használni:
- mérhettem két kép illeszkedésének pontosságát
- megmérhettem két kép relatív elfordulását
- meghatározhattam a képek közötti transzformációk paramétereit
Külön utakon
A perspektivikus forrásképek és a panoráma hengervetülete között nem egyszerű az összefüggés és ez alaposan megnehezítette a dolgomat. A gnomonikus vetület → hengervetület átalakításhoz ugyanis ismerni kell a kamera:
- fókusztávolságát
- szögfelbontását
- függőleges dőlési szögét
- vízszintes elfordulását
- optikai tengely körüli elfordulását
A kutatásaim során számos publikációt olvastam át a témában, és mindig ugyanabba a problémába ütköztem: csak analitikus megoldásokat találtam, és minden publikált módszer – ahogy a létező panorámakészítő programok is – megkövetelte a kamera fókusztávolságának és szögfelbontásának pontos ismeretét. Csakhogy egy amatőr fotóstól nem várható el, hogy ismerje a kamerája paramétereit. Ezeket az értékeket még a termékleírásokban sem szokták közölni, a hagyományos fotók esetén ismeretlenek.
A holdjáró kameráinak szöge és szögfelbontása pontosan meghatározható, de mindenképpen olyan általános megoldást kerestem, amelyhez nem kell ismerni a képekhez tartozó kameraszögeket. Meg akartam hagyni a Pulinak azt a lehetőséget, hogy később önálló, fotósok számára is hasznos termékké fejlessze a panoráma modult. Nem találtam olyan analitikus megoldást, amely extra információk nélkül készített volna panorámát, ezért úgy döntöttem, hogy a hagyományos módszerek helyett numerikus módon fogom megoldani a problémát.
Ehhez ki kellett találnom egy új módszert, amely a kamera paramétereitől függetlenül működik.
A trükk
Az ötletem az volt, hogy az illesztés referenciapontok távolságából számolt pontosságát és egyéb jellemzőit használom fel a paraméterek kiszámítására. Feltételeztem, hogy az illeszkedés pontossága a kamera dőlési szögének a pontosságától is függ, és azzal arányos. A méréseim azt mutatták, hogy valóban így van. A legkisebb illesztési hibát a valós dőlési szögnél lehetett mérni, attól távolodva a hiba lineárisan növekedett, ahogy a lenti ábrán is látszik.
A további mérések sajnos azt mutatták, hogy rosszabb minőségű képek és kevesebb referenciapont esetén a görbe már nem ilyen szép sima, több minimummal is rendelkezhet, ezért a módszer nem elég megbízható. Ki kellett találnom egy jobb megoldást.
Észrevettem, hogy ha a forrásképeket próbálom illeszteni, a horizonttól távolodva növekszik a két kép által bezárt szög. Úgy tűnt, a pontatlan illesztéssel meghatározott szög kiszámítható a képek vízszintes szögtávolságának függvényében. A képletet levezettem a gnomonikus vetület és a gömbvetület közötti összefüggésből. Ez szintén megbízhatatlanul működött. Bizonyos képeknél jó eredményt adott, másoknál nem.
Tehát adott volt sok megbízhatatlan eredmény és ezt kellett egy megbízható egésszé összegyúrni.
Ehhez kellett egy kis méréselméleti ismeret. Kihasználtam azt az elvet, hogy az értékek átlagolásával a hiba kiátlagolódik és pontosabb eredményt kapunk. A konkrét problémára vonatkoztatva ez azt jelenti, hogy a képpárok relatív elfordulásait átlagolva megbízhatóan meghatározható, hogy a teljes panoráma függőleges dőlési szöge mennyire jó. Minél kisebb ez az átlag, annál jobb a dőlési szög. A képek felbontásának meghatározására hasonló módszert alkalmaztam. A kísérletek azt mutatták, hogy az illesztés pontossága (a referenciapont-párok átlagos távolsága), a képfelbontás értékének pontosságától függ. Ezért átlagoltam az összes képpár illeszkedésének a mértékét.
A paraméterek optimalizálását két részre tudtam osztani: a képpárok relatív paramétereit és a teljes kép globális paramétereit egymástól függetlenül tudtam kezelni. Felismertem, hogy két nézőpont tökéletesen kiegészítheti egymást. Például két átfedő kép egymáshoz viszonyított elhelyezkedését a referenciapontok eltolódásából pontosan lehet mérni, míg az összes képpár átlagos elfordulásának minimalizálásával jól beállítható a teljes kép függőleges pozíciója.
A paraméteroptimalizálás a fentiek szerint a következő független szálakra bomlott:
- Lokális paraméterek optimalizálása:
- Relatív függőleges eltolódás
- Relatív vízszintes eltolódás
- Relatív szögfelbontás
- Globális paraméterek optimalizálása:
- Globális függőleges eltolódás
- Globális vízszintes eltolódás
- Globális szögfelbontás
A módszerem lényege, hogy iterációnként meghatározom a szomszédos képek relatív helyzetét és méretét, és a relatív értékek továbbterjednek a kapcsolati hálón. Minden iterációban minden képre átlagolom a szomszédos képek relatív helyzetét és abból kiszámítom a kép következő helyzetét. Az értékek egy egyensúlyi pont irányába konvergálnak. Közben a teljes panoráma pozícióját is optimalizálom úgy, hogy mindig abba az irányba mozdítom az az összes képet, amerre az illesztési hibák globális átlagai csökkennek.
A végeredmény a képek optimális illeszkedése.
Egy kis gráfelmélet
A panoráma készítésének egyik fontos lépése a kapcsolati háló elkészítése a képek referenciapontjai alapján. Az algoritmus sorra összehasonlítja a képeket, és ha két kép referenciapont halmaza nagyrészt egyezik (van átfedés a képek között), akkor összekapcsolja őket, és a képekből egy vagy több gráfot készít, amelyben a gráf csúcsait a képek, az éleit pedig a képek közötti átfedések alkotják. Érdekessé tette a munkát, hogy több gráfelméleti problémába is belefutottam. Elidőztem egy kicsit gráfok egyszerre rejtvényes és vizuális világában.
Az egyik legnagyobb gondot a teljes, 360 fokos panoráma gráfja jelentette, mert a háló egy kört alkotott, amelyben a paraméteroptimalizáló algoritmus a visszacsatolás miatt csődöt mondott és minden értéket lenullázott. Egy bizonyos függőleges egyenes mentén szét kellett vágni a gráfot. Erre egy gráf festési módszert alkalmaztam. Egy pontból kiindulva ellenkező irányokban más színre festettem a gráf csúcsait. Ahol a színek összeértek, ott a szomszédos képek vízszintes eltolódását invertáltam, azaz széthúztam a gráfot 360 fokos szélességűre. Ez a módszer csak az esetek egy részében működik, még tökéletesíteni kell az algoritmust.
Az első éles terepteszt rávilágított egy másik problémára: a módszer néha egészen távoli, nem átfedő képeket is összekapcsol. Egy ilyen hiba az egész panorámát képes eltorzítani. Mivel a rover kameráival készített képek esetén pontosan lehet majd tudni, hogy milyen irányban készültek, így viszonylag könnyen ki lehet szűrni azokat a képeket, amelyek szögtávolsága olyan nagy, hogy nem lehet átfedés közöttük. Ha a képek iránya ismeretlen, már sokkal nehezebb dolgunk van és a hibás átkötések felderítéséhez a gráf szerkezetének elemzésére van szükség.
Villámgyors képóriások
A kész panoráma akkor az igazi, ha van hozzá egy interaktív megjelenítő, amely forgathatóvá, nagyíthatóvá teszi a képet, és több perspektívát is támogat. Mi kell hozzá? Egy nagy képtároló és nagyon gyors képtranszformáció. A kész panorámakép ugyanis több tízezer pixel magas és széles lehet. Tömörítésről itt szó sem lehet, mert nagyon gyorsan kell hozzáférni a képpontokhoz. A tömörítetlen kép pedig több milliárd byte adatot jelenthet. Az elvárás: nagyon gyorsan kell nagyon nagy mennyiségű adathoz hozzáférni. Ez azért nehéz feladat, mert a gyors hozzáféréshez a számítógép munkamemóriáját kell használni, a teljes kép viszont csak a háttértáron fér el. (Pár év múlva akkora memóriával lesznek ellátva a gépek, hogy ez nem lesz probléma, de jelenleg még igen.)
A kulcs a bufferelésnek nevezett módszer: a képnek mindig csak a szükséges részeit töltjük be a munkamemóriába, a nem használt részeket pedig kivesszük a munkamemóriából, így amire szükségünk van, ahhoz gyorsan hozzáférünk, de nem használunk sok munkamemóriát. Sok időt töltöttem létező megoldások keresésével, de mindenütt a képdarabolásos módszerbe botlottam: ennek a lényege, hogy a nagy képet sok kis csempére vágjuk, majd a megjelenítéskor a csempéket összeillesztjük. Azon kívül, hogy szakmailag nem találtam túl elegáns megoldásnak, programozási szempontból egy rémálom lett volna. A megérzéseim azt súgták, hogy ezt az egészet el kell rejteni egy alacsonyabb szinten. A pixelblokkok kezelése tipikusan egy alacsony szintű feladat, amit lehetőleg fájl szinten kell megoldani.
Erre a problémára sikerült kifejlesztenem egy nagyon hatékony módszert, kihasználva a Java alaprendszerben rejlő kiskaput. Ennek az a lényege, hogy a rendszert, amely a képek tartalmát a memóriában tárolja, kicseréltem egy másikra, amely egy gyors fájl buffert tartalmaz. Ami nagyszerű az egészben, hogy közben a Java eredeti képkezelő rendszerét változatlanul lehet használni, mert csak az alatta található réteget cseréltem ki. Így egységesen lehet kezelni az egész panorámaképet, anélkül, hogy betelne a memória.
Hengervetület képzésekor csak a kép mérete változhat. Más típusú vetületek viszont csak számításigényes trigonometrikus egyenletekkel állíthatók elő. A matematikai alapműveletek gyorsítására alapvetően két módszer és annak variációi léteznek. Az egyik a táblázat használata, ahol a függvényértékeket egy táblázatból olvassul ki, a másik a polinomokkal való közelítés módszere. A kettőt lehet kombinálni úgy, hogy a táblázat értékei közötti értékeket interpolációval számoljuk ki, azaz a táblázat pontjait egyenesekkel vagy más közelítő függvényekkel kötjük össze. Egy kis kutatással sikerült olyan Java csomagot (Jafama) találnom, amely gyors, de elég pontos trigonometrikus függvénytárat biztosított a számomra. Az általam kifejlesztett panorámamegjelenítőben két nézet: a hengervetület és a gnomonikus vetület közül lehet választani. A hengervetület egy torzításmentes képet biztosít, a gnomonikus vetület pedig a kamerák képét idézi. Azért választottam ezt a két vetületet, mert ezekkel találkozunk a leggyakrabban.
Összeáll a kép
Eddig csak a panoráma modul legalapvetőbb funkcióit valósítottam meg, mégis visszatekintve milyen sok matematikai szakterületet érintettem:
| Szakterület | Alkalmazás |
|---|---|
| Statisztika | Forrásképek elemzése |
| Analízis | Forrásképek elemzése |
| Numerikus analízis | Paraméteroptimalizálás |
| Gráfelmélet | Képek kapcsolatainak elemzése |
| Geometria | Optika modellezése, koordinátatranszformációk. |
A továbbfejlesztési lehetőségek tárháza szinte végtelen. Jelenleg is dolgozom az algoritmus töléletesítésén és a képminőség javításán.
A panorámaképeket összekapcsolva pedig egyszer eljuthatunk a StreetView holdi változatához.
Pőcze Zsolt, Team Puli
Kövesd a Pulit honlapunkon és csatlakozz online közösségeinkhez a Google+on és Facebook-on!
Szeretnél hozzájárulni ahhoz, hogy Magyarország is eljusson a Holdra?
Told meg Te is!
Egynek minden nehéz; soknak semmi sem lehetetlen.
Gróf Széchenyi István