ERK'2020, Portorož, 189-195 189 Samorazvijajoˇ ca se segmentacija globinske slike stereo kamere za notranja strukturirana okolja Miloˇ s Anti´ c, Andrej Zdeˇ sar, Igor ˇ Skrjanc Univerza v Ljubljani, Fakulteta za elektrotehniko, Trˇ zaˇ ska cesta 25, 1000 Ljubljana, Slovenija E-poˇ sta:fmilos.antic, andrej.zdesar, igor.skrjancg@fe.uni-lj.si Evolving segmentation of a stereo-camera depth map for structured indoor environments In this paper, we present an adaptive approach to point cloud segmentation based on the EPCC (Evolving Princi- pal Component Clustering) method. The method exploits the properties of the ordered data and their neighbor re- lations, which are the result of the way the data of cer- tain sensors are captured. Adaptability refers to the use of a recursive estimate of the parameters of linear proto- types, which are used to describe clusters of similar data. The main contribution of this work is the extension and application of the EPCC method in 3D space for recur- sive and real-time prototype detection, such as lines and planes describing similar clusters. The developed algo- rithm was compared with known methods for point cloud segmentation, such as RANSAC and region growing. 1 Uvod Na podroˇ cju 3D-segmentacije oblakov toˇ ck je bil doseˇ zen velik napredek. Eden glavnih dejavnikov hitrega razvoja tega podroˇ cja je dostopnost nizkocenovnih senzorjev, kot so laserski merilniki razdalje, stereo kamere itd. Pojavila se je visoka potreba po 3D-razumevanju okolja, oz. re- konstrukciji in klasifikaciji tridimenzionalnih nizov toˇ ck v robotiki, za namene lokalizacije robotskih ali mobilnih sistemov in avtonomne gradnje zemljevidov oz. SLAM [1], [2], ki je lahko podlaga za planiranje poti ali slede- nju trajektorijam [3], [4] . Velik pomen ima tudi 3D- modeliranje objektov in klasifikacija le-teh, kar je lahko uporabno v aplikacijah kot so manipulacija objektov z robotskimi rokami [5] in hoja ˇ cetveronoˇ znega robota po stopnicah [6]. Veliko truda je bilo vloˇ zenega v razvoj algoritmov za detekcijo ravnin v oblaku toˇ ck. Z detekcijo in predstavi- tvijo oblaka toˇ ck z modeli ravnin ali planarnimi obmoˇ cji doseˇ zemo bolj kompaktno predstavitev tridimenzional- nega prostora (slika 1). Predlagana je bila 3D-segmenta- cija v zunanjih [7] in notranjih okoljih [8]. Notranja oko- lja so posebej prikladna za planarno segmentacijo ob- laka toˇ ck, saj se v takih okoljih nahaja ogromno predme- tov in povrˇ sin, ki jih je naredil ˇ clovek in so primerna za planarno rekonstrukcijo. Notranji prostori, katere lahko opiˇ semo z ravninami ali pa z obmoˇ cji toˇ ck, ki jih prido- bimo s pomoˇ cjo modelov prototipa ravnin, so torej bolj Slika 1: Prikaz oblaka toˇ ck (a). Z metodo EPCC naredimo se- gmentacijo oblaka na daljice (b), kar uporabimo v naslednjem koraku pri doloˇ cevanju ravnih povrˇ sin (c). Rekonstrukcija pri- zora z ravnimi povrˇ sinami (d). strukturirani. Grilli in drugi so v [9] naredili analizo metod in pri- stopov, ki se uporabljajo pri segmentaciji oblaka toˇ ck. Iz- postavili so, da je 3D-segmentacija oblaka toˇ ck zahtevna naloga, saj imajo oblaki toˇ ck obiˇ cajno neenakomerno go- stoto vzorˇ cenja toˇ ck, so pogosto neurejeni in vsebujejo veliko ˇ suma. Ena izmed prednosti naˇ sega sistema za ob- delavo oblaka toˇ ck je v naravi pridobivanja podatkov z globinskega senzorja, ki na izhodu vraˇ ca matriko ureje- nih toˇ ck, kar omogoˇ ca bolj intuitivno, laˇ zjo in hitrejˇ so implementacijo algoritma za ekstrakcijo ravnin oz. pla- narnih obmoˇ cij oblaka toˇ ck. ˇ Se vedno pa ostaja problem neenakomerne gostote toˇ ck in prisotnosti ˇ suma, ki se pri meritvi globine veˇ ca z razdaljo. Evolucijsko raˇ cunanje pridobiva, na podroˇ cju raˇ cunal- niˇ ske inteligence in strojnega uˇ cenja, na pomenu, saj iz- kazuje velik potencial za uporabo v stvarnem ˇ casu in sis- temih ter okoljih, ki se skozi ˇ cas spreminjajo [10]. Veliko metod na omenjem podroˇ cju temelji na predpostavki, da imamo na voljo velik nabor zgodovinskih podatkov, ki jih uporabijo za generacijo modelov pri regresiji ali identifi- kaciji. Avtorji v [10] so izpostavili, da je ta predpostavka v realnih aplikacijah omajana, saj je v teh sistemih nabor prejˇ snjih podatkov lahko nezadosten, pri ˇ cemer imamo obiˇ cajno opravka z dinamiˇ cnem okoljem ali sistemom. Poudarili so tudi neuˇ cinkovitost iterativnih algoritmov pri obdelavi naraˇ sˇ cajoˇ cih podatkov, saj obiˇ cajno zahtevajo 190 veˇ c prehodov ˇ cez enake dele podatkov. Opisano proble- matiko naslavlja podroˇ cje samorazvijajoˇ cega se modeli- ranja [11–14], ki se je pokazalo za nov okvir, kjer ob- delavo podatkov iz pretoka podatkov reˇ suje s pristopom samorazvoja (angl. self-adaption), uˇ cenjem z enim pre- hodom ˇ cez podatke in evolucijo, kot tudi kontrakcijo, pa- rametrov modelov na zahtevo in spotoma. V tem prispevku predstavljamo razˇ siritev metode EP- CC [15] v 3D-prostor za detekcijo ravnih povrˇ sin v obla- ku toˇ ck. Segmentacija poteka na podatkih z globinske kamere, kjer smo 3D-predstavitev okolja pridobili s trian- gulacijo razdalj. Modificirana rekurzivna metoda EPCC ekstrahira daljice s prototipi premic, kjer je glavni pou- darek na rekurzivni oceni parametrov le-teh, s ˇ cimer po- hitrimo algoritem. Algoritem je dodatno pohitren z is- kanjem daljic v 2D-projekcijah oblaka toˇ ck z eliminacijo ene izmed koordinat. Daljice uporabimo za ekstrakcijo planarnih obmoˇ cij oz. prototipov ravnin. Ker je oblak toˇ ck urejen, smo omenjeni metodi implementirali v al- goritem tako, da sproti odkriva daljice in ekstrahira pro- totipe ravnin. To pomeni, da lahko niz podatkov obde- lamo v enem koraku. Prednost uporabljenega algoritma je tudi moˇ znost upoˇ stevanja urejenosti podatkov oblaka toˇ ck, kar pohitri in olajˇ sa razvoj metode za segmentacijo. Preostanek prispevka ima naslednjo strukturo. Po- glavje 2 podaja kratek pregled sorodnih del. Poglavje 3 opisuje ozadje planarne segmentacije z metodo EPCC. V poglavju 5 so prikazani rezultati eksperimentov na bazi podatkov, ki so prikazani v poglavju 4. V poglavju 6 so predstavljeni zakljuˇ cki ob diskusiji rezultatov. 2 Sorodna dela Prispevek [9] opisuje metodologije, ki se uporabljajo za segmentacijo oblaka toˇ ck. V naˇ sem prispevku smo se osredotoˇ cili na literaturo, ki je povezana z naˇ sim delom in izpostavili tri pogosto uporabljene metode za detekcijo ravnin v oblaku toˇ ck, in sicer pristope, ki temeljijo na metodi RANSAC (angl. RANdom SAmple Consensus), metodi rastoˇ cega obmoˇ cja (angl. region growing) in Ho- ughovi transformaciji. 2.1 Pristopi z metodo RANSAC Metodo RANSAC sta predstavila Fischler in Bolles v [16] za gradnjo modela oz. oceno parametrov le-tega iz eks- perimentalnih podatkov. Xu in drugi so v [8] predstavili planarno segmenta- cijo, kjer so z nauˇ cenimi SVM-modeli ter SVM-predikci- jami klasificirali toˇ cke oblaka v razliˇ cne ravninske povrˇ si- ne in rezultate primerjali z navadno in NDT-RANSAC metodo. Poz in Ywata sta v [17] predstavila adaptivni pristop k segmentaciji streh zgradb, ki vkljuˇ cuje tako predproce- siranje oblaka toˇ ck za loˇ cevanje toˇ ck pripadajoˇ cim zgrad- bam, kot tudi segmentacijo ravnin z metodo RANSAC in postopek agregacije nadsegmentiranih obmoˇ cij. Nguyen in drugi so v [18] predstavili segmentacijo delno urejenih MLS-oblakov toˇ ck, kjer najprej segmenti- rajo profile skeniranja z laserskim merilnikom na podlagi smernih vektorjev, nato te profile grupirajo in detektirajo ravnine glede na planarne vrednosti razliˇ cnih sosedskih profilov skeniranja. 2.2 Pristopi s Houghovo transformacijo Houghova transformacija, ki jo je prviˇ c predstavil Hough v [19], je poleg metode RANSAC standardna metoda za detekcijo parametrov modelov ravnin ali krivulj v 2D- ali 3D-prostoru. Vera in drugi so v [20] predstavili detekcijo ravnin v globinskih slikah za delovanje v realnem ˇ casu, ki upora- blja implicitno ’quadtree’ drevesno strukturo za identifi- kacijo rojev pribliˇ zno koplanarnih toˇ ck v 2,5-D prostoru. Khanh in drugi so v [21] predstavili izboljˇ savo se- gmentacije tal v oblaku toˇ ck za mobilne robote, ki temelji na metodi RHT (angl. Randomized Hough Transform) v kombinaciji z omejitvami razdalj ter kotov in jo primer- jali z metodo RANSAC. Tian in drugi so v [7] predstavila novo metodo za se- gmentacijo planarnih lastnosti v neurejenih oblakih toˇ ck na podlagi ekstrahiranih daljic z uporabo 2D Houghove transformacije in drevesne strukture (angl. octree). 2.3 Pristopi z metodo rastoˇ cega obmoˇ cja Prednost metode rastoˇ cega obmoˇ cja je, da izkoriˇ sˇ ca la- stnosti urejenih oblakov toˇ ck in sosedske strukture toˇ ck. Dong in drugi so v [22] predstavili novo hibridno me- todo rastoˇ cega obmoˇ cja, kjer so problem segmentacije oblaka toˇ ck predstavili kot robustno globalno energijsko optimizacijo. Konvergenco algoritma oz. energijske fun- kcije so zagotovili s pristopom simuliranega ohlajanja. Wu in drugi so v [23] predstavili planarno segmen- tacijo TLS-oblakov toˇ ck z metodo MSTVM za boljˇ so doloˇ citev toˇ cke, ki predstavlja seme algoritma. Predsta- vili so novo lastnost — t. i. indikator planarne jako- sti (angl. plane strength indicator) — za bolj intuitivno doloˇ citev toˇ cke semena. Huang in drugi so v [24] predstavili algoritem EVBS (angl. encoding voxel-based segmentation), ki temelji na metodi rastoˇ cega obmoˇ cja s preiskovanjem strukture kva- drov (angl. voxels) in upoˇ stevanju omejitev zveznosti ter gladkosti. 3 Detekcija daljic Slika 2 prikazuje naˇ cin pojavljanja podatkov v oblaku toˇ ck oz. globinski sliki. Algoritem za detekcijo daljic izkoriˇ sˇ ca vzorec zaporednosti toˇ ck in naravo rekurzivne obdelave podatkov metode EPCC. Struktura podatkov in narava zajemanja toˇ ck prostora znotraj (stoˇ zˇ castega) vi- dnega kota kamere omogoˇ ca ekstrakcijo daljic v 2D-pro- jekcijah oblaka toˇ ck oz. podatkovnih matrikahX. Pro- stor iskanja daljic je razdeljen na tri dele (osrednje obmoˇ cje in dva zunanja) glede na horizontalni vidni kot globin- ske kamere, ki znaˇ sa pribliˇ zno 90 . Pri delitvi prostora upoˇ stevamo koordinatni sistem kamere, kjer osz kaˇ ze iz kamere, x-os je v horizontalni smeri in y-os je v verti- kalni smeri. 3D-toˇ cke matrikeZ, ki se nahajajo v osre- dnjem obmoˇ cju oz. za na intervalu -30 30 , projici- ramo nayz-ravnino. Toˇ cke, ki se nahajajo v zunanjema 191 Slika 2: Globinska slika (a) in pripadajoˇ c oblak toˇ ck (b). Pod (c) je prikazana matrika globinske slike, kjer so toˇ cke po posameznih stolpcih urejene po zaporedju od prve do zadnje vrstice. Prikaz toˇ ck oznaˇ cenega stolpca 3D-matrike oz. oblaka toˇ ck (d). obmoˇ cjema oz. za kote, ki so po absolutni vrednosti veˇ cji od 30 , pa projiciramo naxy-ravnino. V vsaki projekciji poteka rojenje toˇ ck z rekurzivno oceno statistiˇ cnih lastnosti 2D-podatkov in parametrov modelov premic, ki so doloˇ ceni direktno iz kovarianˇ cne matrike podatkov j . j-ti model premice opisuje nor- malni oz. lastni vektor p j , ki pripada najmanjˇ si lastni vrednosti matrike j j =p T j j p j (1) Lastni vektorj-tega roja je doloˇ cen iz j kot p T j = h 1 p 2 1 +1 1 p 2 1 +1 i (2) kjer je 1 = 12 11 (3) in kjer so io ;i;o2f1; 2g elementi matrike j . Psevdo- koda detekcije daljic je predstavljena v Algoritmu 1. Na zaˇ cetku algoritma je potrebno nastaviti parametrek min , init inn buf .k min pomeni minimalno ˇ stevilo toˇ ck, ki jih potrebujemo za zanesljivo gradnjo novega prototipa roja, init pa zaˇ cetna varianca razdalje roja. S parametrom n buf nastavimo najveˇ cje ˇ stevilo toˇ ck, ki jih ˇ se obravna- vamo v postopku odkrivanja rojev. Algoritem roji po- datke po stolpcih podatkovne matrikeZ tako, da inicia- lizira nov roj in ga postavi na aktivni seznam ter ga ˇ siri glede na doloˇ cen kriterij. ˇ Sirjenje roja je ustavljeno, ko podatek ne izpolnjuje kriterija in je odstranjen z aktiv- nega seznama. Tako ˇ sirimo vedno tiste roje, ki so bili nazadnje odkriti. Kriterij za dodajanje v aktivni oz. j-ti roj je odvisen od ortogonalne razdalje doj-tega modela premice d j (k) =j(z(k) j ) T p j j (4) Algoritem 1 Odkrivanje daljic z metodo EPCC 1: Definicija parametrovk min ,k max ,n buf =3k min , init ,n (ˇ stevilo podatkov matrikeZ). 2:fork = 1 :n 3: switchstate 4: case 0 5: z(k) shranjujemo v medpomnilnikbuf. 6: if length(buf)>=k min 7: Poiˇ sˇ cemo kandidata za nov roj vbuf in ocenimo j , j ,p j ind j naslednje to- ˇ cke vbuf ter postavimo j = init . 8: ifd j =n buf 13: Odstranimo najstarejˇ si podatek izbuf. 14: end 15: case 1 16: Izraˇ cunamod j (k) vzorcaz(k). 17: ifd j (k)<=k max p j 18: Dodamoz(k) vj-ti roj in posodobimo j , j ,p j in j . 19: else 20: z(k) damo vbuf in postavimostate = 0 21: end 22: end 23:end kjer jez(k) toˇ cka novega vzorca in j povpreˇ cjej-tega roja. V zajetih podatkih je prisoten ˇ sum, ki se veˇ ca s kva- dratom razdalje. Da omogoˇ cimo robustno rojenje podat- 192 kov, je potrebno upoˇ stevati prisotnost ˇ suma. V ta namen vpeljemo v kriterij rojenja (5) definicijo variance ortogo- nalnih razdalj vseh toˇ ck vj-tem roju j d j (k)