Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Irányítástechnika és Informatika Tanszék
Sári András Lajos
OSZLOPOK DETEKTÁLÁSA 3D LIDAR PONTFELHŐKBEN Önálló laboratórium beszámoló
KONZULENS
Dr. Benedek Csaba BUDAPEST, 2016
Tartalom Bevezetés – Lidar rendszerek ......................................................................................... 3 A feladat specifikálása ................................................................................................... 4 Megvalósítás................................................................................................................... 4 Talajdetekció RANSAC algoritmussal .......................................................................... 5 Fák lombkoronájának detektálása .................................................................................. 6 Klaszterezés .................................................................................................................... 7 A megfelelő objektumok kiválasztása............................................................................ 8 Továbblépési lehetőségek .............................................................................................. 9 Források ........................................................................................................................ 10
2
Bevezetés – Lidar rendszerek
A Lidar egy távérzékelési rendszer, használata széles körben elterjedt például a meteorológiában, térképészetben és a geológiában. A Lidar (Light Detection and Ranging) elnevezés a radar (Radio Detection And Ranging) szóból származtatott angol mozaikszó. A kettő között a különbség a távolságméréshez használt elektromágneses hullámok frekvenciájában rejlik. A radar rádióhullám tartományban sugároz, míg a Lidar az infravöröstől az ultraibolyáig terjedő frekvenciatartományban. A távolságmérés úgy történik, hogy a Lidar egység kibocsát egy energiaimpulzust, mely visszaverődik a mérni kívánt tárgyról és újra a Lidar egységbe jut. A jel által megtett út számítható az adás és a vétel időpontjából, ha az átviteli közeg törésmutatója ismert. Ahhoz, hogy több mérési pontból tudjuk végezni a térképezést, szükség van a mérési pont pozíciójára, ezért a Lidar készülékeket általában ellátják pozíció-meghatározáshoz szükséges eszközökkel (GPS, IMU) is. A
Lidar
rendszereknek
felhasználás
szempontjából
különböző
csoportokba
sorolhatjuk. A topológiában használt Lidar rendszereket többnyire repülőgépekre szerelik és így térképezik fel a domborzatot. A hidrografikus rendszereket a tengerfenék feltérképezésére használják. Az ilyen típusú berendezések két különböző frekvenciájú nyalábbal működnek. A földi Lidar rendszereket járműre vagy talajra szerelik és általában városképek modellezésére, épületek külső vagy belső térképezésére használják, de képesek mozgó objektumok azonosítására is. Az önálló laboratórium során felhasznált adatok egy Riegl VZ 400-as Lidarral készültek. A mérés során az egységet a földre rögzítik. Másodpercenként 122000 pontot képes rögzíteni, 100°-os vertikális látószögben. A rendszer ezen kívül fel van szerelve egy kamerával is, így lehetőség nyílik a távolságon és az intenzitáson kívül RGB adatokat is hozzárendelni a pontokhoz. Az önálló laboratórium folyamán, csak a pontok pozíció (XYZ) adatait használtam fel, az RGB és intenzitásadatokat figyelmen kívül hagytam. 1
3
1. ábra: Velodyne Lidar által készített kép2
2. ábra: Riegl VZ 400 által készített kép
A feladat specifikálása A feladatom az önálló laboratórium során különböző, oszlopok detektálása volt, melyet később felhasználhatunk akár közúti táblák pozíciójának meghatározására. Az önálló laboratórium folyamán felhasznált
mintákat
a
SZTAKI
bocsátotta
rendelkezésemre. A kapott pontfelhők több mérési pozícióból lettek felvéve, majd a BKK Közút Zrt. Közúti Adatgyűjtő REndSzer projektjének keretében, lettek egyesítve a mért adatok. Az pontfelhők, amiken
dolgoztam a Fővám tér és a Gellért tér méréseiből származtak. A
pontfelhők
feldolgozására
a
szabad
forráskódú Point Cloud Library3-t használtam fel 3. ábra: Detektálni kívánt oszlop a Fővám téren
mely a pointclouds.org által van karbantartva. Így lehetőségem volt magas szinten (C++ nyelven) dolgozni.
Megvalósítás Az oszlopok azonosítására a stratégiám a következő volt: Először meghatározom a talajt reprezentáló ponthalmazt és kivonom az összes pontot tartalmazó ponthalmazból. Ezzel a pontfelhő különböző objektumokra esik szét. Ezek után kivonom a fák lombkoronáját 4
tartalmazó felhőket, így lehetőség nyílik a fák által benőtt oszlopok detektálására is. Legvégül egy klaszterező algoritmussal azonosítom az objektumokat és különböző tulajdonságaik alapján szétválogatom őket.
Talajdetekció RANSAC algoritmussal A RANSAC4 (Random Sample Consensus)
algoritmus
segítségével
könnyedén detektálható a legtöbb pontból álló
egyenes
háromdimenziós
vagy
sík
két
illetve
ponthalmazban.
A
RANSAC egy iteratív módszeren alapul, ami addig próbál javítani a talált síkon 4. ábra: talaj detektálása RANSAC algoritmussal a Szent Gelért téren
(vagy egyenesen), amíg el nem éri a paraméterben
megadott
maximális
iterációk számát. Sík detektálásánál az első lépésként véletlenszerűen választ három pontot, amiből kiszámolja a pontokra illesztett sík paramétereit, majd megnézi, hogy a ponthalmaz többi pontja közül mennyi esik bele ebbe a síkba. Mivel a keresett pontok nem alkotnak matematikailag tökéletes síkot, ezért szükséges egy hiba paraméter megadása, mely szemléletesen a detektált sík „vastagságát” jelenti. Ezek után az algoritmus összeveti az így talált síkot az eddig talált legjobb síkkal, és ha ezt jobbnak ítéli, akkor ez lesz az új legjobb sík, ha nem akkor ezt a síkot eldobja. A ciklusnak akkor van vége, ha elértük az előre megadott iterációk számát. Az algoritmus működéséből adódik, hogy az iterációk számának a növelésével, nagyobb valószínűséggel kapunk az adathalmazra jól illeszkedő síkot.
5. ábra: Fővám tér talajdetekciója
6. ábra: RANSAC algoritmus hibája szintkülönbségeknél
5
Sajnos mivel a RANSAC a legnagyobb síkot találja meg, működése nem megfelelő olyan talajdetekciónál, melynél a talaj nem modellezhető egy síkkal (például szintkülönbségeket tartalmazó talaj). A hiba paramétert 30cm-re választottam meg, mivel azt tapasztaltam, hogyha a paraméter túl kicsi, nem lesz összefüggő a detektált talaj, viszont ha túl nagyra választom, akkor az egyéb talaj feletti részeket is a talajhoz sorolja. Mivel az oszlopok detektálása volt a cél, a szükségesnél kicsit nagyobb paraméter megengedhető, hiszen az oszlopok talpazata az oszlopfelismerésben nem kritikus.
Fák lombkoronájának detektálása A következő lépés a fák lombkoronájának
detektálása
volt. Ehhez azt a stratégiát választottam, minden
hogy
a
pontjára
legközelebbi
a
felhő 10
szomszédja
alapján számolom a kovariancia mátrix
sajátértékeit,
amiből
később a görbületet meg tudom határozni. Úgy véltem, hogy a
7. ábra: Fák lombkoronájának detektálása
fa
lombkoronája
nagy
görbületet fog mutatni, mivel a lombkorona terét a pontok közel egyenletesen töltik ki. A legközelebbi pontok kereséséhez a pontfelhőt KdTree5 struktúrába rendeztem, mely lehetővé teszi, hogy a legközelebbi k pontot megtalálása gyorsan történjen. Ezt úgy teszi, hogy a teret a koordinátatengelyekkel párhuzamosan optimálisan partícionálja. Erre azért van szükség, mert a Lidar pontfelhő nem egyenletes eloszlású a térben, ezért érdemes a felbontást csak azokon a területeken megnövelni, ahol a pontok többsége található. A sajátértékeket számítását a Point Cloud Library-be beépített PCA (Principal Component Analysis) segítségével végeztem. A PCA által szolgáltatott adatokból a görbületet a nulladik sajátérték és a sajátértékek hányadosaként számítottam.
6
A kapott pontokat a görbület szerint három csoportba soroltam. Pirossal jelöltem azokat a pontokat, amelyeknél a görbület 0.005-nél kisebb. Ezek a síkfelületeknek felelnek meg. A 0.005-től 0.03-ig terjedő intervallumban zölddel színeztem a pontokat, és a maradék pontokat kékre színeztem, melyek a lombkoronának vélt pontokat jelentik. A képek alapján jól látható, hogy ez az algoritmus is képes (kisebb módosításokkal) a talaj detektálására, esetenként jobban működik, mint a RANSAC, azonban mivel a program futása rendkívül lassú, így végül nem ezt választottam. Sajnos a fák lombkoronájának detektálása is lassúnak bizonyult, így végül ezt a módszert nem implementáltam a végső algoritmusban.
8. ábra: Sík felületek és fák lombkoronájának detektálása
Klaszterezés Az objektumok szétválasztását az euklideszi klaszterező algoritmussal végeztem. Ez az eljárás tulajdonképpen a több komponensből álló gráfokra implementált BFS bejárás duálisa. Az algoritmus működése a következő: először kiválaszt egy pontot, majd megkeresi azokat a pontokat, amik a ponttól egy előre megadott távolságon belül vannak és hozzáadja őket a ponthoz tartozó listához. Ezek után kiválasztja a következő pontot a listán és ennek a környezetében lévő pontokat is hozzáadja a lista végéhez, ha azok még nem voltak rajta a listán. Ha a lista végére ért, akkor egy cluster készen van, új pontot választ és innen újraindítja 7
a keresést. Ha az összes pont elfogyott a klaszterezés véget ért. Mivel itt is a legközelebbi pontok kereséséről van szó (csak itt nem a legközelebbi k pontot, hanem az r sugárnál közelebb található pontokat keressük), itt is KdTree-t használtam a keresés gyorsítása végett.
9. ábra: Fővám tér a talaj eltávolítása után
A megfelelő objektumok kiválasztása Ezek után, már csak az a feladat maradt, hogy eldöntsük az egyes clusterekről, hogy oszlopok-e. Ezt a következő módszerrel csináltam: megkerestem a cluster legnagyobb és legalacsonyabb z koordinátájú pontját, a z koordinátájuk különbségét egy height változóban tároltam. Ezt követően, úgy gondoltam, hogy azok az objektumok tekinthetők oszlopnak, amik magasak (height érték magasabb, mint 2,5 méter), és a magasságuk 25%-tól 75%-ig terjedő intervallumában keskenyek, azaz nem szélesebbek 3 méternél. Azért választottam viszonylag nagy értéket, mert a rajtuk lévő esetleges reklámtábláknak még bele kell férni, és ez a paraméter inkább az épülethomlokzattól való megkülönböztetésre szolgál. Ahhoz, hogy a szélességüket mérni tudjam megkerestem az ezen z tartományban 25%-75%-ig terjedő intervallumban az x és y koordináta szerinti szélsőértékeket is, és úgy határoztam, hogy se az x se az y irányú szélesség ne legyen nagyobb a megengedettnél. (Így orientációtól függően a határérték akár 20.5 –szerese is megengedett.)
8
A kívánt eredményt így nem sikerült megvalósítani, mivel az egyik oszlopról a lelógó vezetékek miatt a szélességre adott kritérium nem teljesült. A szélesség kritérium eltörlésével azonban mindkét oszlopot képesek voltunk detektálni.
10. ábra: Az algoritmus által (feltételek enyhítése után) detektált oszlopok
Továbblépési lehetőségek Lehetséges továbblépési lehetőség az oszlopok különböző csoportokba sorolása, mely segítségével, akár a közúti táblák is felismerhetőek. Ehhez például felhasználhatjuk a lombkorona detektálásához használt algoritmust, mely segítségével az oszlopon lévő síkfelületeket érzékelhetnénk. Mivel a közúti tábláknak jól definiált méretei vannak, ezek szűrése viszonylag szigorú paraméterezés is alkalmazható. Másik lehetséges előrelépési lehetőség a RANSAC algoritmus lecserélése egy olyan algoritmusra, mely lehetőséget nyújt a nem sík talaj detektálására.
9
Források 1
Demkó Bence: Mozgó elemek által generált zaj detektálása 3D Lidar pontfelhőkben 2015. 1-2. 2
Ábra: http://velodynelidar.com/hdl-64e.html
3
Rusu, R.B.; Cousins, S., "3D is here: Point Cloud Library (PCL)," Robotics and Automation (ICRA), 2011 IEEE International Conference on , vol., no., pp.1,4, 9-13 May 2011 4
Martin A. Fischler and Robert C. Bolles (June 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography". Comm. of the ACM 24 (6): 381–395. 5
Szirmay-Kalos László, Antal György, Csonka Ferenc: Háromdimenziós grafika, animáció és játékfejlesztés ComputerBooks, 2003. 181-184.
10
