ˇ ´ vysoke ´ uc ˇen´ı technicke ´ v Praze Cesk e Fakulta stavebn´ı
´ PRACE ´ DIPLOMOVA
2010
Kateˇ rina Turkov´ a
ˇ ´ vysoke ´ uc ˇen´ı technicke ´ v Praze Cesk e Fakulta stavebn´ı ´ ln´ı geode ´zie Katedra specia
´ PRACE ´ DIPLOMOVA
Vedouc´ı pr´ ace:
Autor pr´ ace:
Ing. Bronislav Koska, Ph.D.
Praha 2010
Kateˇ rina Turkov´ a
Kateˇrina Turkov´a. Pr˚ uzkum souˇcasn´eho stavu v automatizaci vyhodnocen´ı mraˇcen ˇ e vysok´e uˇcen´ı techbod˚ u z pozemn´ıho prostorov´eho skenov´an´ı budov. Praha: Cesk´ nick´e v Praze. Fakulta Stavebn´ı. Katedra speci´aln´ı geod´ezie, 2010. Diplomov´a pr´ace, poˇcet stran 51 s., poˇcet stran pˇr´ıloh 25 s. Vedouc´ı diplomov´e pr´ace byl Ing. Bronislav Koska, Ph.D.
´ SEN ˇ ´I PROHLA Prohlaˇsuji, ˇze jsem svou diplomovou pr´aci na t´ema Pr˚ uzkum souˇcasn´eho stavu v automatizaci vyhodnocen´ı mraˇcen bod˚ u z pozemn´ıho prostorov´eho skenov´an´ı budov vypracovala samostatnˇe s vyuˇzit´ım konzultac´ı u vedouc´ıho diplomov´e pr´ace a pouˇzit´ım odborn´e literatury a dalˇs´ıch informaˇcn´ıch zdroj˚ u, uveden´ ych v seznamu literatury.
V Praze dne . . . . . . . . . . . . . .
........................... (podpis autora)
Na tomto m´ıstˇe bych r´ada podˇekovala vedouc´ımu sv´e diplomov´e pr´ace, panu Ing. Bronislavu Koskovi, Ph.D. za odborn´e veden´ı a pomoc v pr˚ ubˇehu zpracov´an´ı a panu ˇ Ing. Janu Rezn´ ıˇckovi za poskytnut´ı vlastn´ıch skript˚ u a za dobr´e rady pro pr´aci s programem Matlab. Podˇekov´an´ı patˇr´ı tak´e m´e rodinˇe a bl´ızk´ ym za podporu ve studiu.
Abstrakt Diplomov´a pr´ace se zab´ yv´a problematikou vyhodnocov´an´ı prostorov´ ych dat z´ıskan´ ych metodou laserov´eho skenov´an´ı. Zamˇeˇrena je konkr´etnˇe na ˇc´ast zpracov´an´ı, a to segmentaci. V souˇcasn´e dobˇe je snaha maxim´alˇe automatizovat zpracov´an´ı namˇeˇren´ ych dat, zejm´ena f´azi segmentace a n´aslednou klasifikaci. Nejprve je struˇcnˇe pops´an princip metody laserov´eho skenov´an´ı. N´asleduje pˇredstaven´ı r˚ uzn´ ych moˇznost´ı a postup˚ u automatick´e segmentace. Praktick´a ˇc´ast se vˇenuje za prv´e tvorbˇe a pouˇzit´ı vlastn´ıch skript˚ u na segmentaci mraˇcna bod˚ u a zadruh´e procesu segmentace v komerˇcn´ım softwaru Geomagic Studio 10.
Kl´ıˇ cov´ a slova Vyhodnocen´ı mraˇcna bod˚ u Segmentace fas´ady objektu Matlab Region growing RANSAC Geomagic Studio 10
Abstract This diploma thesis is focused on problematics in laser scanning spatial data processing, particularly on a segmentation of a point cloud. Recently lot of efforts are put into automatization of processing part of laser scanning data, especially in segmentation and sequential classification. At first the laser scanning method is briefly introduced. Then the description of opportunities and different approaches to automatic segmentation follows. The practical part of the thesis is devoted firstly to own study and elaboration of scripts for a point cloud segmentation and secondly to a segmentation process via the commercial software Geomagic Studio 10.
Keywords Processing of a point cloud Segmentation of a building facade Matlab Region growing RANSAC Geomagic Studio 10
Obsah
1
Obsah ´ 1 Uvod
5
2 Laserov´ e skenov´ an´ı
6
2.1
Princip laserov´eho skenov´an´ı . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
Zpracov´an´ı dat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3 Segmentace
9
3.1
Pattern based method - shlukov´a anal´ yza . . . . . . . . . . . . . . . . 11
3.2
Detekce hran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3
Proximity graph based segmentation . . . . . . . . . . . . . . . . . . 12
3.4
Region growing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5
Prot´ın´an´ı profil˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.6
Segmentace podle parametr˚ u roviny na z´akladˇe v´ ypoˇctu gradientu v range image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.7
RANSAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Praktick´ aˇ c´ ast I - segmentace v programu Matlab pomoc´ı vlastn´ıch skript˚ u 4.1
4.2
19
Segmentace ve 2.5D prostoru . . . . . . . . . . . . . . . . . . . . . . . 20 4.1.1
Range image
. . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.1.2
Zjiˇstˇen´ı parametr˚ u norm´al rovin pro kaˇzd´ y pixel (bod) . . . . 25
4.1.3
Pˇriˇrazen´ı pixel˚ u k ploch´am podle jejich parametr˚ u . . . . . . . 29
4.1.4
Porovn´an´ı v´ ysledk˚ u . . . . . . . . . . . . . . . . . . . . . . . . 32
Segmenatace ve 3D prostoru: RANSAC . . . . . . . . . . . . . . . . . 34
5 Praktick´ aˇ c´ ast II - segmentace v programu Geomagic Studio 10
37
5.1
Point Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2
Polygon Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Obsah
2
5.3
Fashion & Shape Phase . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6 Z´ avˇ er
48
Literatura
51
Pˇ r´ılohy
52
Pˇrehled funkc´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Range image.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Cisteni.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Interpolace.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Prokladani rovin.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Region growing.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Segmenty2seznam.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Grad based.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 RNS.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Model rovina.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Vzdalenost.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 SegmentaceRNS.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 SegmentaceI.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 SegmentaceII.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Obrazov´a ˇca´st . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Seznam obr´azk˚ u
3
Seznam obr´ azk˚ u 3.1
Sobel˚ uv filtr (oper´ator): vlevo pro detekci svisl´ ych hran, vpravo pro detekci vodorovn´ ych hran. . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2
Aplikace Sobelova opar´atoru: P˚ uvodn´ı obr´azek (vlevo), detekce horizont´aln´ıch hran (uprostˇred), detekce vertik´aln´ıch hran (vpravo). . . . 12
3.3
Proximity graph based segmentation. . . . . . . . . . . . . . . . . . . 13
3.4
Segmentace v profilech pomoc´ı Delaunayovy triangulace (vlevo) a na z´akladˇe prokl´ad´an´ı kˇrivkou (vpravo). . . . . . . . . . . . . . . . . 15
3.5
Pˇr´ıklad segmentace dvou rovnobˇeˇzn´ ych rovin pomoc´ı prot´ın´an´ı profil˚ u ve tˇrech r˚ uzn´ ych orientac´ıch.
3.6
. . . . . . . . . . . . . . . . . . . . . . 15
Matematick´ y model mˇeˇren´ ych dat ve 2D: Proloˇzen´ı pˇr´ımky klasickou metodou nejmenˇs´ıch ˇctverc˚ u (vlevo) a proloˇzen´ı pˇr´ımky robustn´ı metodou RANSAC (vpravo).
. . . . . . . . . . . . . . . . . . . . . . 17
4.1
Testovan´e mraˇcno. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2
Range image cel´e fas´ady. . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3
Pˇrevod bodu P do rastru range image. . . . . . . . . . . . . . . . . . 21
4.4
V´ yˇrez z range image fas´ady p˚ uvodn´ı a po odstranˇen´ı ˇsumu. . . . . . . 23
4.5
V´ yˇrez z range image fas´ady pˇred a po interpolaci. . . . . . . . . . . . 24
4.6
Rastry Theta (vlevo), Phi (uprostˇred) a Rho (vpravo). Hodnoty u ´hl˚ u prvn´ıch dvou rastr˚ u jsou ud´any v radianech, hodnoty rastru Rho v metrech. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.7
V´ ypoˇcet rozd´ılov´eho u ´hlu ∆φ z gradientu z´ıskan´eho z range image. . 28
4.8
Filtr na v´ ypoˇcet gradientu pro metodu podle Bena Gorteho. . . . . . 29
4.9
Rastry Theta (vlevo), Phi (uprostˇred) a Rho (vpravo), z´ıskan´e metodou podle Bena Gorteho. Hodnoty u ´hl˚ u prvn´ıch dvou rastr˚ u jsou ud´any v radianech, hodnoty rastru Rho v metrech. . . . . . . . . . . 30
Seznam obr´azk˚ u
4
4.10 Rozr˚ ust´an´ı homogenn´ıch oblast´ı v algoritmu region growing. . . . . . 31 4.11 Vizualizace seznamu segmentovan´ ych souˇradnic; barvy n´aleˇz´ı ˇc´ısl˚ um segment˚ u. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.12 V´ ysledky testu Segmentace I (vlevo) a Segmentace II(vpravo). . . . . 33 4.13 Mraˇcno bod˚ u segmentovan´e algoritmem RANSAC; barvy n´aleˇz´ı ˇc´ısl˚ um segment˚ u. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.1
Namˇeˇren´a data naˇcten´a do programu Geomagic Studio 10. . . . . . . 38
5.2
Posuny bod˚ u pˇri aplikaci filtru Reduce noice, ud´ano v metrech. . . . . 39
5.3
Aplikace filtru Uniform sample. . . . . . . . . . . . . . . . . . . . . . 40
5.4
Ruˇcn´ı vyhlazen´ı pomoc´ı kurzoru ve funkci Sandpaper.
5.5
Decimate polygons: Redukce poˇctu troj´ uheln´ık˚ u v rovinn´ ych oblas-
. . . . . . . . 41
tech s´ıtˇe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.6
V´ ysledek automatick´e segmentace (vlevo) a jeho ruˇcn´ı editace (vpravo). 43
5.7
Pouˇzit´ı funkce Remove islands.
5.8
Vygenerov´an´ı kˇrivek z oblast´ı separ´ator˚ u. . . . . . . . . . . . . . . . . 45
5.9
Dialog Classify. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
. . . . . . . . . . . . . . . . . . . . . 44
5.10 Odchylky od p˚ uvodn´ı s´ıtˇe pˇri proloˇzen´ı vˇsech segment˚ u rovinami, ud´ano v metrech. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.11 CADovsk´ y model generovan´ y ve Fashion Phase (vlevo) a v Shape Phase (vpravo). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.1
Testovan´e mraˇcno bod˚ u. . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.2
Rastr range image. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.3
Rastr range image po ˇciˇstˇen´ı a interpolaci. . . . . . . . . . . . . . . . 72
6.4
Mraˇcno bod˚ u segmentovan´e postupem Segmentace I. . . . . . . . . . 73
6.5
Mraˇcno bod˚ u segmentovan´e postupem Segmentace II. . . . . . . . . . 74
6.6
Mraˇcno bod˚ u segmentovan´e postupem SegmentaceRNS. . . . . . . . . 75
6.7
Mraˇcno bod˚ u segmentovan´e pomoc´ı n´astroje automatick´e segmentace v programu Geomagic Studio 10. . . . . . . . . . . . . . . . . . . . . 76
´ 1. Uvod
5
´ 1 Uvod Jednou z nejnovˇejˇs´ıch metod sbˇeru prostorov´ ych dat je laserov´e skenov´an´ı (LS). Vyv´ıj´ı se terpve v 90. letech 20. stolet´ı a postupnˇe se ve svˇetˇe st´av´a v´ıce obl´ıben´ ym a vyuˇz´ıvan´ ym. Velkou pˇrednost´ı LS je mnohon´asobnˇe rychlejˇs´ı z´ısk´av´an´ı dat v ter´enu, neˇz jak´ ymikoli jin´ ymi metodami. Tak´e mnoˇzstv´ı z´ıskan´ ych dat daleko pˇresahuje moˇznosti klasick´ ych, ˇci jin´ ych modern´ıch zp˚ usob˚ u mˇeˇren´ı. Jejich zpracov´an´ı je ale naopak slabinou laserov´eho skenov´an´ı. Neobejde se bez pomoci vysoce v´ ykonn´e v´ ypoˇcetn´ı techniky a i tak je velmi problematick´e a ˇcasovˇe nesm´ırnˇe n´aroˇcn´e. Na jeho automatizaci se st´ale pracuje. Tato pr´ace se zab´ yv´a asi nejv´ıce komplikovanou ˇca´st´ı zpracov´an´ı namˇeˇren´ ych dat ˇ e republice se doposud problemaLS (tzv. mraˇcna bod˚ u), a to segmentac´ı. V Cesk´ tice automatick´e segmentace mraˇcen bod˚ u z pozemn´ıho laserov´eho skenov´an´ı nikdo c´ılenˇe nevˇenoval, a nelze tak naj´ıt jedinou ˇcesky psanou literaturu. Publikace, z nichˇz bylo pro tuto pr´aci ˇcerp´ano, byly vˇetˇsinou vˇedeck´e ˇcl´anky, vydan´e na zahraniˇcn´ıch univerzit´ach, pˇredevˇs´ım v Nizozem´ı a Nˇemecku. V souˇcasn´e dobˇe existuje jen nˇekolik program˚ u pro zpracov´an´ı dat LS, jeˇz obsahuj´ı n´astroje pro segmentaci mraˇcen bod˚ u. V kapitole 2 Laserov´e skenov´an´ı je tato metoda pˇredstavena, struˇcnˇe je pops´an jej´ı princip a postup pˇri zpracov´an´ı. Kapitola 3 Segmentace popisuje r˚ uzn´e pˇr´ıstupy t´eto ˇca´sti zpracov´an´ı dat laserov´eho skenov´an´ı. Praktick´a ˇca´st diplomov´e pr´ace (kapitoly 4 a 5) zahrnuje vytvoˇren´ıch skript˚ u v programu Matlab k segmentaci dat LS a jeho aplikace na mraˇcno bod˚ u fas´ady budovy Arcibiskupsk´eho semin´aˇre v Praze 6, Dejvic´ıch. Po pouˇzit´ı vlastn´ıho skriptu byla segmentace mraˇcna provedena tak´e v komerˇcn´ım softwaru Geomagic Studio 10. V´ ysledky vˇsech pouˇzit´ ych metod segmentace byly na z´avˇer porovn´any.
2. Laserov´e skenov´an´ı
6
2 Laserov´ e skenov´ an´ı 2.1
Princip laserov´ eho skenov´ an´ı
Laserov´e skenov´an´ı spoˇc´ıv´a v neselektivn´ı urˇcov´an´ı souˇradnic bod˚ u na povrchu objekt˚ u. Podle typu nosiˇce rozliˇsujeme leteck´e laserov´e skenov´an´ı (Airborne laser scanning) a pozemn´ı laserov´e skenov´an´ı (Terrestrial laser scanning). Leteck´e laserov´e skenov´an´ı se vyuˇz´ıv´a napˇr´ıklad pro vytvoˇren´ı digit´aln´ıho modelu ter´enu (DTM), digit´aln´ıho modelu reli´efu (DSM), zjiˇst’ov´an´ı pr˚ ubˇehu veden´ı nadzemn´ıch inˇzen´ yrsk´ ych s´ıt´ı, digit´aln´ıch model˚ u mˇest, zjiˇst’ov´an´ı v´ yˇsky vegetace atd. Do jist´e m´ıry j´ım lze nahradit fotogrammetrii a d´alkov´ y pr˚ uzkum zemˇe. S obˇema tˇemito metodami je LS pomˇernˇe u ´zce spjato, at’ uˇz pˇr´ıstupem ke sbˇeru dat (neselektivn´ı), ˇci zp˚ usobem vyhodnocov´an´ı a zpracov´an´ı mˇeˇren´ı. Pozemn´ı skenov´an´ı slouˇz´ı k tvorbˇe model˚ u stavebn´ıch konstrukc´ı a budov (interi´eru a exteri´eru), zamˇeˇrov´an´ı podzemn´ıch prostor˚ u (tunely, jeskynˇe) atd. Pˇri vˇsech tˇechto ˇcinnostech je v´ yhodou velk´e rozliˇsen´ı metody LS a rychlost sbˇeru znaˇcn´eho objemu dat. Sbˇer dat se prov´an´ı pomoc´ı laserov´eho skeneru, ˇr´ızen´eho nejˇcastˇeji pˇrenosn´ ym poˇc´ıtaˇcem, v nˇemˇz zad´av´ame parametry mˇeˇren´ı, jako napˇr. u ´hel skenov´an´ı vymezuj´ıc´ı z´ajmovou oblast, rozliˇsen´ı skenov´an´ı a pod. K n´asledn´emu zpracov´an´ı a zobrazen´ı dat (mraˇcna bod˚ u) se vyuˇz´ıv´a kompatibiln´ı software. Cel´e zaˇr´ızen´ı potˇrebn´e k provozu t´eto metody se naz´ yv´a laserov´ y skenovac´ı syst´em (LSS). Souˇradnice bod˚ u mraˇcna jsou urˇcov´any bud’ pol´arn´ı metodou - mˇeˇren´ım vertik´aln´ıho a horizont´aln´ıho u ´hlu a ˇsikm´e vzd´alenosti (pol´arn´ı skenery) nebo prot´ın´an´ım z u ´hl˚ u ze zn´am´e z´akladny (skenery se z´akladnou).
Zpracov´an´ı dat
2.2
7
Zpracov´ an´ı dat
Zpracov´an´ı namˇeˇren´ ych dat je tou problematiˇctˇejˇs´ı ˇc´ast´ı metody laserov´eho skenov´an´ı. Prov´ad´ı se ˇcasto poloautomaticky pomoc´ı speci´aln´ıch softwar˚ u, avˇsak i zpracov´an´ı mˇeˇren´ı menˇs´ıho rozsahu m˚ uˇze zabrat mnohon´asobnˇe v´ıce ˇcasu, neˇz samotn´e mˇeˇren´ı v ter´enu. Zpracov´an´ı lze rozdˇelit na nˇekolik ˇca´st´ı: ˇ 1. Registrace mraˇ cen bod˚ u – Casto se prov´ad´ı mˇeˇren´ı z v´ıce neˇz jednoho stanoviska. Mraˇcna bod˚ u ze vˇsech stanovisek se registrac´ı transformuj´ı do spoleˇcn´e souˇradnicov´e soustavy. Za poˇc´atek se vol´ı jedno ze stanovisek. Transformace z m´ıstn´ıho souˇradnicov´eho syst´emu do nˇekter´eho ze z´avazn´ ych n´arodn´ıch syst´em˚ u se vˇetˇsinou neprov´ad´ı. 2. Odstranˇ en´ı ˇ sumu, filtrace – Z mraˇcna se v grafick´em rozhran´ı ruˇcnˇe nebo automaticky odstran´ı shluky bod˚ u, kter´e nen´aleˇz´ı objektu z´ajmu (naskenovan´e okoln´ı objekty, vegetace, kolemjdouc´ı chodci, auta), d´ale se pouˇz´ıvaj´ı filtry na zˇredˇen´ı mraˇcna bod˚ u v rovinn´ ych ˇca´stech objekt˚ u. To je v´ yhodn´e zvl´aˇstˇe pˇri generov´an´ı troj´ uheln´ıkov´e s´ıtˇe, pˇredstavuj´ıc´ı povrch objektu. 3. Segmentace – Spoˇc´ıv´a v rozdˇelen´ı mraˇcna na homogenn´ı oblasti - segmenty, jeˇz odpov´ıdaj´ı jednomu objektu ˇci jeho ˇc´asti. Kaˇzd´ ym t´ımto segmentem se d´a proloˇzit geometrick´e primitivum, nejˇcastˇeji rovina. 4. Klasifikace – Tato f´aze navazuje na segmentaci, kdy se podle tvaru, velikosti a dalˇs´ıch vlastnost´ı segmentu urˇcuje, co tento segment ve skuteˇcnosti pˇredstavuje (napˇr. stˇrechy budov, silnice, vegetace u leteck´eho LS; dveˇre, okna, ark´ yˇre u pozemn´ıho LS) 5. Vytvoˇ ren´ı 3D modelu – Proloˇzen´ım geometrick´ ych primitiv segmenty a jejich pˇr´ıpadn´ ym prot´ın´an´ım se nejˇcastˇeji z´ısk´a model skenovan´eho objektu. Pˇri vytv´aˇren´ı DTM u leteck´eho skenov´an´ı, ˇci u pozemn´ıho skenov´an´ı objekt˚ u, jeˇz nelze rozloˇzit na geometrick´a primitiva (sochy ap.) se vytvoˇr´ı 3D model pomoc´ı troj´ uheln´ıkov´e s´ıtˇe.
Zpracov´an´ı dat
8
Nepracnˇejˇs´ımi a nejzdlouhavˇejˇs´ımi f´azemi cel´eho procesu jsou segmentace a n´asledn´a klasifikace. Proto je snaha tyto ˇc´asti zpracov´an´ı plnˇe automatizovat a zkr´atit tak dobu vyhodnocen´ı na minimum. Tato pr´ace se vˇenuje pˇredevˇs´ım zp˚ usob˚ um a moˇznostem segmentace mraˇcen bod˚ u, at’ uˇz z leteck´eho, ˇci pozemn´ıho laserov´eho skenov´an´ı. Praktick´a ˇca´st je vzhledem k dostupnosti poˇzadovan´eho softwaru zamˇeˇrena pouze na segmentaci mraˇcna bod˚ u pozemn´ıho skenov´an´ı.
3. Segmentace
9
3 Segmentace Tento krok ve vyhodnocov´an´ı dat laserov´eho skenov´an´ı slouˇz´ı k rozpozn´an´ı homogenn´ıch oblast´ı v mraˇcnu bod˚ u. Oddˇelen´e oblasti - segmenty - mohou b´ yt d´ale podle zn´am´eho obsahu mraˇcna a podle parametr˚ u, jako je napˇr´ıklad jejich velikost, tvar a poloha v mraˇcnu, klasifikov´any na jednotliv´e objekty a ˇca´sti objekt˚ u. Ruˇcn´ı segmentace spoˇc´ıv´a v oˇrez´an´ı mraˇcna, postupn´em v´ ybˇeru ˇc´ast´ı, jejich oznaˇcen´ı za homogenn´ı oblast a proloˇzen´ı nˇejak´ ym geometrick´ ym primitivem. Nejˇcastˇeji b´ yv´a t´ımto primitivem rovina. M˚ uˇze to b´ yt tak´e v´alcov´a plocha, koule (nezbytn´a pˇri pouˇzit´ı kulov´ ych terˇc˚ u jako vl´ıcovac´ıch bod˚ u) a i jin´e sloˇzit´e, pˇredem nadefinovan´e plochy a tvary, kter´e nab´ız´ı pouˇz´ıvan´ y software (ˇca´sti potrub´ı apod.). V pˇr´ıpadˇe, ˇze v´ ysledkem m´a b´ yt 3D model nˇejak´eho objektu, je nezbytn´e z mraˇcna bod˚ u z´ıskat d˚ uleˇzit´e hrany objektu, eventu´alnˇe jejich pr˚ useˇc´ıky, a prov´est jejich export do souboru, kter´ y lze v jin´em grafick´em programu d´ale zpracovat. Hrany dr´atov´eho modelu z´ısk´ame v´ ypoˇctem pr˚ useˇcnic proloˇzen´ ych geometrick´ ych primitiv. Ruˇcn´ı segmentace je tedy velmi pracn´a a zdlouhav´a, a to i pˇri pouˇzit´ı v´ ykonn´e v´ ypoˇcetn´ı techniky. Pouze nˇekolik softwar˚ u pro zpracov´an´ı dat LS obsahuje n´astroje pro segmentaci mraˇcen bod˚ u. Nejˇcastˇeji funguj´ı na z´akladˇe vytvoˇren´ı troj´ uhelkov´e s´ıtˇe a sledov´an´ı a porovn´av´an´ı jednotliv´ ych hran mezi troj´ uheln´ıky. V automatick´e segmentaci vˇsak existuje pomˇernˇe mnoho r˚ uzn´ ych algoritm˚ u. Pouˇzit´ı z´avis´ı na typu dat, kter´a se maj´ı segmentovat.
Over-segmentation a under-segmentation V ide´aln´ım pˇr´ıpadˇe by byl v´ ysledkem procesu segmentace stav, kdy jeden segment odpov´ıd´a jednomu objektu ˇci jedn´e jeho ˇca´sti. Pˇri segmentaci m´alokdy doc´ıl´ıme pˇresn´eho rozpozn´an´ı 1 objekt = 1 segment. Rozliˇsujeme tedy dva pˇr´ıpady segmentace:
3. Segmentace
10
over-segmentation - Jednomu objetu (popˇr. ˇc´asti objektu) je pˇriˇrazeno v´ıce segment˚ u. Ty se d´ale mus´ı spojit do jednoho segmentu, kter´ y bude pˇredstavovat objekt/ˇca´st objektu. under-segmentation - V´ıce objekt˚ u je zn´azornˇeno jako jeden segment. V tomto pˇr´ıpadˇe nelze rozeznat jednotliv´e objekty v segmentu. Mus´ıme tedy proces opakovat a nastavit parametry segmentace tak, aby doˇslo k over-segmentation.
Rozdˇ elen´ı segmentac´ı Zp˚ usob˚ u, jak urˇcit hommogenn´ı oblasti v mraˇcnˇe bod˚ u, je v´ıce. Lze je dˇelit do skupin podle r˚ uzn´ ych krit´eri´ı: • podle typu laserov´ ych dat : leteck´ e LS – Pˇredevˇs´ım tvorba DTM; vyuˇz´ıv´a v´ıce zpracov´an´ı troj´ uheln´ıkovou s´ıt´ı. pozemn´ı LS – Zamˇeˇrov´an´ı fas´ad, podzemn´ıch prostor; pouˇz´ıv´a pˇrev´aˇznˇe prokl´ad´an´ı rovin a jin´ ych geometrick´ ych primitiv. • podle prostoru, v nˇ emˇ z doch´ az´ı k segmentaci : 3D prostor – K mraˇcnu bod˚ u se pˇristupuje jako k tˇelesu v prostoru. V´ ypoˇcty vych´azej´ı ze souˇradnic bod˚ u mraˇcna. Pracuje se s cel´ ym mraˇcnem, kter´ ym lze proloˇzit prostorovou troj´ uheln´ıkovou s´ıt’, pˇriˇcemˇz vrcholy troj´ uheln´ık˚ u jsou body mraˇcna. Porovn´av´an´ım hran troj´ uheln´ık˚ u, ˇcili vzd´alenost´ı mezi jednotliv´ ymi body, se posuzuje homogenita oblasti. Dalˇs´ı moˇznost´ı m˚ uˇze b´ yt prokl´ad´an´ı primitiv algoritmem RANSAC. 2.5D prostor – Pracuje se pouze s daty namˇeˇren´ ymi z jednoho stanoviska. Prostorov´e mraˇcno bod˚ u se pˇrev´ad´ı do 2D obrazu, pˇriˇcemˇz informace o tˇret´ım rozmˇeru je obsaˇzena v hodnotˇe pixelu. Zpracov´an´ı tohoto rastru, tzv. range image, se velmi podob´a zpracov´an´ı obrazov´ ych dat, jak ho zn´ame z obor˚ u d´alkov´eho pr˚ uzkumu Zemˇe a fotogrammetrie. 2D prostor – Zpracov´an´ı ve 3D si zjednoduˇsˇs´ıme vytvoˇren´ım profil˚ u v konstantn´ıch ˇci vhodnˇe zvolen´ ych intervalech a v r˚ uzn´ ych smˇerech. Kaˇzd´ y
Pattern based method - shlukov´a anal´ yza
11
profil se vyhodnot´ı zv´aˇst’ - pomoc´ı troj´ uheln´ıkov´e s´ıtˇe, aproximac´ı kˇrivkami ˇci prostorov´ ymi filtry [1]. • podle zp˚ usobu vytv´ aˇ ren´ı homogenn´ıch oblast´ı : region growing – Zaloˇzen´e na n´ahodn´em vybr´an´ı z´akladn´ıho bodu oblasti (seed) a jej´ım postupn´em nar˚ ust´an´ı v okol´ı tohoto bodu podle stanoven´ ych podm´ınek. region merging – Spoˇc´ıv´a ve spojov´an´ı menˇs´ıch homogenn´ıch oblast´ı ve vˇetˇs´ı na z´akladˇe stanoven´ ych parametr˚ u.
3.1
Pattern based method - shlukov´ a anal´ yza
P˚ uvodn´ı metoda pro klasifikaci obrazov´ ych dat z DPZ, kdy byl pro kaˇzd´ y pixel sestaven vektor obsahuj´ıc´ı radiometrick´e veliˇciny namˇeˇren´e v r˚ uzn´ ych p´asmech, je nyn´ı aplikovan´a na body v mraˇcnu. Pro kaˇzd´ y bod je vytvoˇren n-rozmˇern´ y pˇr´ıznakov´ y vektor (feature vector), kter´ y obsahuje napˇr´ıklad souˇradnice bodu, parametry norm´aly roviny, v n´ıˇz bod leˇz´ı a odrazivost. Roviny se prokl´ad´aj´ı vˇzdy nˇekolika body v okol´ı urˇcovan´eho bodu metodou nejmenˇs´ıch ˇctverc˚ u (v´ıce viz 4.1.2). Veliˇciny pˇr´ıznakov´ ych vektor˚ u pro kaˇzd´ y bod jsou vyn´aˇseny do n-rozmˇern´eho prostoru (feature space), kde vytv´aˇrej´ı shluky (clusters). Body jednoho shluku tvoˇr´ı jeden segment. Vymezen´ı pˇr´ıznakov´eho prostoru se prov´ad´ı pomoc´ı metody Maximum likelyhood a KNN (k-t´ y nejbliˇzˇs´ı soused). Shluky s poˇctem bod˚ u menˇs´ım neˇz stanoven´a mez nejsou oznaˇceny za samostatn´ y segment, ale vymaz´any, nebo pˇriˇrazeny k jin´emu shluku. Segmenty n´aleˇzej´ıc´ı jednomu objektu/ˇc´asti objektu jsou spojeny v jeden. Existuje nˇekolik algoritm˚ u (Jain and Hoffman, 1987; Filin, 2002) otestovan´ ych pro leteck´e laserov´e skenov´an´ı. Tato metoda se vˇsak pouˇz´ıv´a pˇredevˇs´ım pro segmentaci dat pozemn´ıho laserov´eho skenov´an´ı, kdy se vyuˇz´ıv´a pr´avˇe range image a pracuje se tedy v 2.5D prostoru.
Detekce hran
3.2
12
Detekce hran
Tato metoda se opˇet op´ır´a o postupy zpracov´an´ı obrazov´ ych dat. Mraˇcno se pˇrev´ad´ı na 2.5D rastr a ten je analyzov´an pomoc´ı filtr˚ u. Pˇri segmentaci pomoc´ı detekce hran vych´az´ıme z pˇredpokladu, ˇze kaˇzd´ y segment je pevnˇe ohraniˇcen a body spadaj´ıc´ı do uzavˇren´eho sledu hran n´aleˇz´ı jednomu segmentu. Pˇri zobrazen´ı mraˇcna do rastru lze hrany a segmenty vizu´alnˇe rozeznat. Hrana je na obraze m´ıstem, kde se skokem mˇen´ı hodnoty radiometrick´ ych veliˇcin,
Obr´azek
3.1:
Sobel˚ uv
filtr
(oper´ator): vlevo pro detekci svisl´ ych hran, vpravo pro detekci vodorovn´ ych hran.
pˇredstavuj´ıc´ıch napˇr´ıklad v´ yˇsku ter´enu u leteck´eho skenov´an´ı nebo vzd´alenost od skeneru u pozemn´ıho skenov´an´ı. Pomoc´ı klasick´ ych filtr˚ u (Sobel˚ uv oper´ator, Roberts˚ uv oper´ator, Prewit˚ uv) se daj´ı detekovat zmˇeny v digit´aln´ıch hodnot´ach pixel˚ u jak v horizont´aln´ım tak vertik´aln´ım smˇeru. Cannyho algoritmus detekce hran nav´ıc pouˇz´ıv´a filtr detekuj´ıc´ı hrany v diagon´aln´ım smˇeru.
Obr´azek 3.2: Aplikace Sobelova opar´atoru: P˚ uvodn´ı obr´azek (vlevo), detekce horizont´aln´ıch hran (uprostˇred), detekce vertik´aln´ıch hran (vpravo).
3.3
Proximity graph based segmentation
Tato metoda pracuj´ıc´ı ve 3D prostoru je zaloˇzena na mˇeˇren´ı vzd´alenost´ı mezi bl´ızk´ ymi body a pˇredpokl´ad´a, ˇze sousedn´ı body n´aleˇzej´ıc´ı jednomu segmentu maj´ı
Region growing
13
mezi sebou menˇs´ı Euklidovskou d´elku neˇz body n´aleˇzej´ıc´ı dvˇema r˚ uzn´ ym segment˚ um. Zjiˇstit sousedstv´ı bod˚ u lze pomoc´ı Delaunayovy triangulace ˇci uloˇzen´ım bod˚ u mraˇcna do struktury octree a jeho prohled´av´an´ım. Bl´ızk´e body v mraˇcnu se pospojuj´ı a vznikne tak graf, jemuˇz hled´ame minim´aln´ı kostru. Vahami v tomto grafu jsou Euklidovsk´e vzd´alenosti mezi body. Po nalezen´ı minim´aln´ı kostry grafu - stromu (spanning tree), porovn´av´ame velikosti hran mezi body (vrcholy grafu). Hrany, jejichˇz v´aha pˇrevyˇsuje stanovenou mez, se odstran´ı. Podle parametr˚ u skenov´an´ı lze odhadnout vzd´alenosti sousedn´ıch bod˚ u n´aleˇz´ıc´ıch jedn´e homogenn´ı oblasti a nastavit tak tuto mezn´ı vzd´alenost. V´ ysledkem je skupina spojit´ ych graf˚ u, z nichˇz kaˇzd´ y pˇredstavuje jeden segment. Algoritmus byl navrˇzen pro zpracov´an´ı leteck´ ych dat, lze jej vˇsak pouˇz´ıt i pro data pozemn´ıho skenov´an´ı.
Obr´azek 3.3: Proximity graph based segmentation.
3.4
Region growing
V tˇechto algoritmech je v mraˇcnu n´ahodnˇe vybr´an rovinn´ y ˇci nerovinn´ y prvek, tvoˇren´ y nezbytn´ ym poˇctem sousedn´ıch bod˚ u (u roviny jsou to tˇri body, kter´e ji definuj´ı). Tento prvek je postupnˇe spojov´an s dalˇs´ımi bl´ızk´ ymi body na z´akladˇe veliˇcin, jako jsou parametry norm´aly, sklon, kˇrivost, atd. Urˇcov´an´ı bl´ızkosti bod˚ u a jejich sousedstv´ı se prov´ad´ı r˚ uzn´ ymi zp˚ usoby. Jedn´ım
Prot´ın´an´ı profil˚ u
14
z nich je Delaunayova triangulace, j´ıˇz lze pouˇz´ıt jak ve 2D, tak i ve 3D prostoru [2]. Sousedstv´ı bod˚ u urˇcuj´ı hrany troj´ uheln´ıkov´e s´ıtˇe a okol´ı bodu vymezuj´ı hrany Voronoyova diagramu. N´aroˇcnost na v´ ypoˇcet troj´ uheln´ıkov´e s´ıtˇe je natolik vysok´a, ˇze se radˇeji vol´ı jin´e m´enˇe n´aroˇcn´e metody. Tou je napˇr´ıklad hled´an´ı soused˚ u pomoc´ı koule o dan´em polomˇeru, kterou op´ıˇseme kaˇzd´emu bodu. Body, kter´e do koule padnou povaˇzujeme za sousedy stˇredov´eho bodu. Dalˇs´ı metodou je volba nejbliˇzˇs´ıch k soused˚ u. U tˇechto postup˚ u se bere v u ´vahu nejen vzd´alenost bod˚ u, ale tak´e jejich rozloˇzen´ı, tud´ıˇz dalˇs´ım kriteriem se st´av´a symetrie. Zav´ad´ı se pojem medianov´e sousedstv´ı ( nearist centroid/median ” neighborhood“). Jin´ y postup v kategorii region growing vych´az´ı ze skuteˇcnosti, ˇze data jsou poˇrizov´ana postupnˇe pod´el skenovac´ıch lini´ı. Nejprve jsou tedy body tˇechto lini´ı proloˇzeny polynomickou funkc´ı a pot´e se porovn´av´a bl´ızkost jednotliv´ ych kˇrivek. Jde tedy o sekvenˇcn´ı region growing, a to nejdˇr´ıve ve smˇeru skenu, n´aslednˇe napˇr´ıˇc skeny. Tento algoritmus navrˇzen´ y v roce 1994 pro zpracov´an´ı dat leteck´eho skenov´an´ı st´ale nach´az´ı sv´e uplatnˇen´ı a ve srovn´an´ı s ostatn´ımi algoritmy dosahuje uspokojiv´ ych v´ ysledk˚ u. Metodu region growing je moˇzn´e pouˇz´ıt tak´e ve 2.5D prostoru pro segmentaci pixel˚ u v rastru (viz 4.1.3, Region growing)
3.5
Prot´ın´ an´ı profil˚ u
Dalˇs´ı algoritmus je zaloˇzen na prot´ın´an´ı profil˚ u, zpracovan´ ych ve 2D. Metoda je vyvinut´a pro zpracovn´an´ı dat leteck´eho laserov´eho skenov´an´ı [1]. Postupuje se v tˇechto kroc´ıch: 1. Mraˇcno bod˚ u je rozˇrez´ano“ na profilov´e p´asy o urˇcit´e ˇs´ıˇrce s r˚ uznou orientac´ı. ” 2. Body jsou v r´amci p´as˚ u spojov´any bud’ na z´akladˇe aproximace pˇredem definovanou kˇrivkou nebo na z´akladˇe porovn´av´an´ı vzd´alenost´ı mezi body s danou mezn´ı d´elkou (obr´azek 3.4). Skupiny bod˚ u splˇ nuj´ıc´ı dan´a krit´eria (mezn´ı vz´ajemnou vzd´alenost nebo mezn´ı vzd´alenost od proloˇzen´e kˇrivky ) jsou spojeny lomen´ ymi ˇcarami. V kaˇzd´em profilu tak vznikne mnoˇzina lomen´ ych ˇcar,
Prot´ın´an´ı profil˚ u
15
kdy kaˇzd´a tato ˇca´ra bude n´aleˇzet jednomu segmentu. 3. Totoˇzn´a mraˇcna s r˚ uznou orientac´ı profil˚ u se pˇrekryj´ı do jednoho obrazu, a tak vznikne s´ıt’ lomen´ ych ˇcar - graf˚ u - s pr˚ useˇc´ıky v nˇekter´ ych bodech mraˇcna. Kaˇzd´ y spojit´ y graf je jedn´ım segmentem a jeho vrcholy jsou body mraˇcna, n´aleˇzej´ıc´ı jedn´e homogenn´ı ploˇse (obr´azek 3.5).
Obr´azek 3.4: Segmentace v profilech pomoc´ı Delaunayovy triangulace (vlevo) a na z´akladˇe prokl´ad´an´ı kˇrivkou (vpravo).
Obr´azek 3.5: Pˇr´ıklad segmentace dvou rovnobˇeˇzn´ ych rovin pomoc´ı prot´ın´an´ı profil˚ u ve tˇrech r˚ uzn´ ych orientac´ıch.
Segmentace podle parametr˚ u roviny na z´akladˇe v´ ypoˇctu gradientu v range image16
3.6
Segmentace podle parametr˚ u roviny na z´ akladˇ e v´ ypoˇ ctu gradientu v range image
V origin´ale Gradient based method, publikov´ana v ˇcl´anku Bena Gorteho [4], pracuje s mraˇcnem ve 2.5D prostoru. Metoda je podrobnˇe pops´ana v podkapitole 4.1, Segmentace ve 2.5D prostoru, jelikoˇz ˇca´st algoritmu byla pouˇzita ve vlastn´ım skriptu. Struˇcn´ y postup je n´asleduj´ıc´ı: 1. Pˇrevod mraˇcna bod˚ u do rastru range image. 2. V´ ypoˇcet gradientu v range image pro kaˇzd´ y pixel, zvl´aˇst’ ve smˇeru ˇr´adk˚ u a sloupc˚ u. 3. V´ ypoˇcet horizont´aln´ıch a vertik´aln´ıch u ´hl˚ u norm´al rovin, jimˇz pixely n´aleˇz´ı. 4. V´ ypoˇcet tˇret´ıho parametru rovin - vzd´alenosti ρ od poˇca´tku (vzorec odvozen z Houghovy transformace). 5. Pˇriˇrazen´ı pixel˚ u k ploch´am podle tˇechto tˇr´ı parametr˚ u metodou region merging (spojov´an´ı list˚ u quad-tree). Ve vlastn´ım skriptu metoda region merging pouˇzita nebyla. Spoˇc´ıv´a ve spojov´an´ı list˚ u struktury quad-tree, do n´ıˇz jsou pixely uloˇzeny. Pixely (listy) se postupnˇe spojuj´ı do vˇetˇs´ıch a vˇetˇs´ıch skupin (segment˚ u), dokud eukleidovsk´a vzd´alenost pixel˚ u v pˇr´ıznakov´em prostoru (feature space) a rozd´ıly mezi diagon´aln´ımi prvky kovarianˇcn´ıch matic segment˚ u nepˇres´ahnou stanovenou mez. Tato metoda je navrˇzena pro segmentaci dat pozemn´ıho skenov´an´ı.
3.7
RANSAC
Algoritmus RANSAC (RANdom SAmple Concensus, [5]) je iteraˇcn´ı robustn´ı metoda na zjiˇst’ov´an´ı parametr˚ u matematick´eho modelu mˇeˇren´ ych dat. Pˇredpokl´ad´a, ˇze data obsahuj´ı nejen spr´avn´e“ hodnoty (inliers), ale i velk´ y poˇcet hodnot odlehl´ ych ” (outliers). V´ ysledn´ y model obsahuje pouze data spr´avn´a“. ”
RANSAC
17
Obr´azek 3.6: Matematick´ y model mˇeˇren´ ych dat ve 2D: Proloˇzen´ı pˇr´ımky klasickou metodou nejmenˇs´ıch ˇctverc˚ u (vlevo) a proloˇzen´ı pˇr´ımky robustn´ı metodou RANSAC (vpravo).
Namˇeˇren´ ymi daty se n´ahodnˇe prokl´ad´a matematick´ y model, v naˇsem pˇr´ıpadˇe rovina, a posl´eze se zjiˇst’uje porovn´an´ım se stanovenou mezn´ı odchylkou, kolik dat je oznaˇceno jako inliars a kolik jako outliers. N´ahodn´e prokl´ad´an´ı se prov´ad´ı opakovanˇe a u kaˇzd´e nov´e iterace se hodnot´ı poˇcet inliars. Rovina, jeˇz jich ˇc´ıt´a nejv´ıce, je ta spr´avn´a. Vhodn´ y poˇcet iterac´ı k se stanov´ı takto:
k =
log(1 − p) , log(1 − wn )
(3.1)
kde n
je poˇcet bod˚ u nutn´ ych pro stanoven´ı parametru modelu, v tomto pˇr´ıpadˇe 3 body,
p
je pravdˇepodobnost, ˇze v jedn´e iteraci se n´ahodnˇe vybere n spr´avn´ ych dat (vol´ı se),
w
je pod´ıl dat spr´avn´ ych a cel´eho souboru dat. Do v´ ypoˇctu vstupuje seznam bod˚ u o souˇradnic´ıch xyz a nastavuj´ı se parametry:
poˇcet iterac´ı, poˇcet bod˚ u nutn´ ych pro v´ ypoˇcet modelu a mez urˇcuj´ıc´ı jiˇz odlehl´e hodnoty. Algoritmus prob´ıh´a v tˇechto kroc´ıch:
RANSAC
18
1. N´ahodnˇe se vyberou 3 body, z nichˇz se vypoˇc´ıtaj´ı parametry modelu, v tomto pˇr´ıpadˇe 4 parametry norm´aly roviny. 2. Nyn´ı se vypoˇc´ıt´av´a vzd´alenost kaˇzd´eho bodu od roviny a porovn´av´a se se stanovenou mez´ı. Body s vˇetˇs´ı vzd´alenost´ı jsou oznaˇceny jako outliers. 3. Zaznamenaj´ı se parametry roviny, poˇcet spr´avn´ ych dat a opakuje se se bod 1. a 2. Pokud je poˇcet spr´avn´ ych dat vˇetˇs´ı pˇri druh´e a kaˇzd´e dalˇs´ı iteraci, bere se nov´ y model za spr´avn´ y a hodnoty modelov´ ych parametr˚ u pˇredeˇsl´e iterace se pˇrep´ıˇs´ı nov´ ymi hodnotami. 4. Po posledn´ı iteraci se pˇrepoˇc´ıtaj´ı parametry modelu metodou nejmenˇs´ıch ˇctverc˚ u se vˇsemi spr´avn´ ymi hodnotami. Algoritmus RANSAC lze vyuˇz´ıt k segmentaci mraˇcna bod˚ u pˇr´ımo ve 3D prostoru [6]. Bl´ıˇze se mu vˇenuje kapitola 4.2.
4. Praktick´a ˇc´ast I - segmentace v programu Matlab pomoc´ı vlastn´ıch skript˚ u
19
4 Praktick´ aˇ c´ ast I - segmentace v programu Matlab pomoc´ı vlastn´ıch skript˚ u Praktick´a ˇc´ast diplomov´e pr´ace se zab´ yv´a vyuˇzit´ım nˇekter´ ych algoritm˚ u a postup˚ u zm´ınˇen´ ych v pˇredeˇsl´e kapitole v praxi. Testovan´e mraˇcno bylo segmentov´ano pomoc´ı vlastn´ıch skript˚ u v programu Matlab a d´ale v komerˇcn´ım software Geomagic (Kapitola 5), urˇcen´emu ke zpracov´an´ı dat LS. Test prob´ıhal na datech poˇr´ızen´ ych ze zamˇeˇren´ı fas´ady budovy Arcibiskupsk´eho semin´aˇre v Praze 6, Dejvic´ıch. K testov´an´ı byla pouˇzita pouze ˇca´st mraˇcna bod˚ u namˇeˇren´eho z jednoho stanoviska - v´ yˇrez jednoho okna fas´ady zobrazen´ y na obr´azku 4.1. Toto mraˇcno ˇc´ıtalo 182 017 bod˚ u. Do segmentace vstupovaly pouze pravo´ uhl´e souˇradnice objektu, radiometrick´e veliˇciny bod˚ u nebyly vyuˇzity. Na z´avˇer bylo vybranou metodou segmentov´ano cel´e mraˇcno bod˚ u. Mraˇcna bod˚ u byla uloˇzena jako
Obr´azek 4.1: Testovan´e mraˇcno.
seznamy souˇradnic x, y, z ve dvou souborech okno.xyz a fasada.xyz. Pouˇzit´e skripty a funkce jsou uveden´e v pˇr´ıloze a uloˇzen´e na disku v adres´aˇri FUNKCE jako soubory ∗ .m.
Segmentace ve 2.5D prostoru
4.1
20
Segmentace ve 2.5D prostoru
Prvn´ı testovan´a metoda prob´ıhala ve 2.5D prostoru. Bylo nutn´e naˇcten´e body o souˇradnic´ıch x, y, z s poˇca´tkem ve stanovisku pˇrev´est na tzv. range image.
4.1.1
Range image
Obr´azek 4.2: Range image cel´e fas´ady.
Range image je rastr, kde po sloupc´ıch zleva doprava nar˚ ust´a horizont´aln´ı u ´hel sn´ım´an´ı o konstantn´ı u ´hel ∆α a po ˇr´adc´ıch zdola nahoru nar˚ ust´a vertik´aln´ı u ´hel o konstantn´ı u ´hel ∆β. Hodnoty pixel˚ u znamenaj´ı vzd´alenost objektu od centra sn´ım´an´ı. Velikost ∆α a ∆β z´avis´ı na hustotˇe sn´ım´an´ı, v tomto pˇr´ıpadˇe ∆α = ∆β = 0, 00035 rad = 72, 200 . Pˇrevod mraˇcna bod˚ u z 3D do 2.5D prob´ıh´a pomoc´ı vlastn´ı funkce range image (skript uveden v pˇr´ıloze na stranˇe 53). Postup, ˇc´asteˇcnˇe pˇrevzat´ y ze skriptu pana ˇ Ing. Jana Rezn´ ıˇcka, je n´asledovn´ y: 1. Pravo´ uhl´e souˇradnice xyz byly pˇrevedeny na sf´erick´e souˇradnice λ, φ a ρ. 2. Poˇca´tek soustavy souˇradnic (λ = 0 a φ = 0) byl posunut do bodu se souˇradnicemi λmax a φmax . 3. Tato soustava byla transformov´ana na soustavu souˇradnic α, β a R, jej´ıˇz poˇca´tek je v lev´em horn´ım rohu rastru, souˇradnice α nar˚ ust´a po sloupc´ıch a β ve smˇeru pˇrib´ yv´an´ı ˇr´adk˚ u. Hodnoty vzd´alenost´ı od poˇca´tku R se nemˇen´ı.
Segmentace ve 2.5D prostoru
21
Z obr´azku 4.3 je patrn´e odvozen´ı transformace ze sf´erick´ ych souˇradnic λ a φ na souˇradnice rastru α a β:
αP = λmax − λP βP
(4.1)
= φmax − φP
4. Pro naplnˇen´ı rastru o m ˇra´dc´ıch a n sloupc´ıch je tˇreba trasformovat souˇradnice α a β na souˇradnice pixel˚ u v rastru r =< 1; m >, c =< 1; n >; r, c ∈ N . Plat´ı vztahy: . r = . c =
βP ∆β
+ 0.5
αP ∆α
+ 0.5
(4.2)
kde konstanta 0.5 posune poˇc´atek soustavy na stˇred pixelu.
Obr´azek 4.3: Pˇrevod bodu P do rastru range image.
Naplnˇen´ı rastru range image se ˇr´ıd´ı pravidlem, ˇze pokud dva body odpov´ıdaj´ı jednomu pixelu, bere se za spr´avn´ y ten s vˇetˇs´ı vzd´alenost´ı. T´ım se pˇredejde moˇzn´emu ˇsumu, zp˚ usoben´emu napˇr´ıklad n´ahodn´ ymi chodci a jin´ ymi objekty, kter´e mohly doˇcasnˇe zast´ınit objekt z´ajmu. Body nevyuˇzit´e pˇri naplnˇen´ı rastru se vˇsak neztrat´ı. Pokud rozd´ıl jejich hodnoty Rx a Rrangeimage splˇ nuje danou mez, zap´ıˇse se tento
Segmentace ve 2.5D prostoru
22
bod do pomocn´eho vektoru link. Ten podle index˚ u odkazuje na m´ıstech vyˇrazen´ ych bod˚ u na body m´ısto nich v range image pouˇzit´e. Pro vytvoˇren´ı rangeimage nebyly pouˇzity 1 684 body, kter´e jsou zaps´any ve vektoru link a podlehnou tak segmentaci tak´e. V´ ysledn´ y rastr range image obsahuje 2 vrstvy. V prvn´ı vrstvˇe je vlastn´ı range image s hodnotami vzd´alenost´ı od poˇc´atku R, zat´ımco druh´a vrstva pod´av´a informaci o rozloˇzen´ı objektu v range image a pomoc´ı jedniˇcek a nul rozliˇsuje pr´azdn´e pixely (0) a pixely objekt obsahuj´ıc´ı (1). Zobrazen´ı prvn´ı vrstvy rastru je v obrazov´e ˇca´sti pˇr´ılohy. Vstupn´ımi parametry funkce range image jsou: seznam souˇradnic ve form´atu xyz a rozliˇsen´ı range image (rozliˇsen´ı skenov´an´ı v rad). V´ ystupn´ımi parametry jsou: upraven´ y seznam souˇradnic s indexy bod˚ u, rastr range image, rastr index˚ u bod˚ u ze seznamu souˇradnic, vektor link obsahuj´ıc´ı u nevyuˇzit´ ych bod˚ u odkazy na body pouˇzit´e v range image, vektor posun˚ u sf´erick´ ych souˇradnic pˇri transformaci (vyuˇzije se pˇri zobrazen´ı range image), seznam p˚ uvodn´ıch sf´erick´ ych souˇradnic. Vznikl´ y rastr range image je tˇreba d´ale oˇcistit od ˇsumu, popˇr´ıpadˇe interpolovat pr´azdn´e pixely. K tomu slouˇz´ı vlastn´ı funkce cisteni a interpolace. Odstranˇ en´ı ˇ sumu Po vytvoˇren´ı range image, je nezbytn´e rastr oˇcistit o ˇsum - shluky bod˚ u (v tomto pˇr´ıpadˇe pixel˚ u), kter´e objektu nen´aleˇzej´ı. Tyto pixely jsou v rastru bud’ mimo objekt, a nebo jsou obklopeny pixely objektu, ale maj´ı v´ yraznˇe menˇs´ı hodnotu vzd´alenosti od poˇca´tku (R). K odstranˇen´ı ˇsumu slouˇz´ı funkce cisteni (Pˇr´ıloha, str. 54). Pˇri jej´ı aplikaci se odstran´ı vˇsechny osamˇel´e shluky bod˚ u pomoc´ı pohybliv´eho okna, kter´e prob´ıh´a po druh´e vrstvˇe rastru a porovn´av´a pr´azdn´e a zaplnˇen´e pixely. Pokud jsou vˇsechny okrajov´e pixely pr´azdn´e a hodnota nˇekter´ ych vnitˇrn´ıch pixel˚ u je jedna, povaˇzuj´ı se tyto pixely za ˇsum a vymaˇzou se nastaven´ım hodnot v obou vrstv´ach na nulu. Pokud jsou okrajov´e pixely kernelu nenulov´e, spoˇc´ıt´a se z prvn´ı vrstvy range image jejich medi´an a porovn´a s medi´anem vnitˇrn´ıch pixel˚ u. V pˇr´ıpadˇe, ˇze rozd´ıl
Segmentace ve 2.5D prostoru
23
Obr´azek 4.4: V´ yˇrez z range image fas´ady p˚ uvodn´ı a po odstranˇen´ı ˇsumu.
obou medi´an˚ u pˇres´ahne danou mez, jsou vnitˇrn´ı pixely povaˇzovan´e za ˇsum a dojde k jejich vymaz´an´ı. Nastaven´a poˇca´teˇcn´ı velikost kernelu se postupnˇe sniˇzuje aˇz na velikost 3x3 pixely. T´ım se zaruˇc´ı odstranˇen´ı ˇsumu i v otvorech objekt˚ u (oknech ap.). Vstupn´ımi parametry funkce jsou: rastr range image, velikost kernelu a hodnota mezn´ıho rozd´ılu medi´an˚ u vniˇrn´ıch a okrajov´ ych pixel˚ u. V´ ystupn´ım parametrem je oˇciˇstˇen´ y rastr range image. Interpolace Pˇri plnˇen´ı rastru range image se st´av´a, ˇze i pˇres vhodn´e nastaven´ı rozliˇsen´ı do nˇekter´eho z pixel˚ u padne v´ıce bod˚ u a do nˇekter´eho pixelu ˇza´dn´ y, aˇckoli je zˇrejm´e, ˇze pixel mˇeˇren´emu objektu n´aleˇz´ı. V tomto pˇr´ıpadˇe je nutn´a interpolace tˇecho pr´azdn´ ych pixel˚ u. Prob´ıh´a iteraˇcnˇe a to tak, ˇze pro kaˇzd´ y pr´azdn´ y pixel se vyˇsetˇruje okol´ı (ˇctvercov´a matice o rozmˇeru 3x3, 5x5 ˇci 7x7 pixel˚ u) a pˇri nalezen´ı
Segmentace ve 2.5D prostoru
24
urˇcit´eho poˇctu nenulov´ ych pixel˚ u se hodnota stˇredov´eho nastav´ı na median okol´ı. Hodnota v druh´e vrstˇe se pˇrep´ıˇse z 0 na 1. Poˇcet nutn´ ych nenulov´ ych pixel˚ u n z´aleˇz´ı na hustotˇe skenovan´ ych bod˚ u a stanov´ı se na z´akladˇe velikosti kernelu. Pro data s hustotou 10 mm (okno.xyz ) byl vytvoˇren vzorec n5 = mw2 − 2mw + 4,
(4.3)
kde mw je rozmˇer kernelu. Plat´ı pr´avˇe pro matice o velikosti 3x3, 5x5 ˇci 7x7 pixel˚ u. Pro data s hustotou 20 mm (fasada.xyz ) byl vzorec upraven : n20 = mw2 − 2mw + 3.
(4.4)
Vzorce byly navrˇzeny tak, aby v obou pˇr´ıpadech byly interpolov´any pouze vnitˇrn´ı pixely a nedoch´azelo k pˇrir˚ ust´an´ı nenulov´ ych pixel˚ u na okraj´ıch objektu. Pˇri zpracov´an´ı dat o jin´e hustotˇe bod˚ u vˇsak nemus´ı vyhovovat ˇz´adn´ y z tˇechto dvou vzorc˚ u.
Obr´azek 4.5: V´ yˇrez z range image fas´ady pˇred a po interpolaci. K interpolaci nedoch´az´ı, pokud se hodnoty spadaj´ıc´ı do kernelu v´ yraznˇe liˇs´ı.
Segmentace ve 2.5D prostoru
25
M˚ uˇze se totiˇz jednat o neodstranˇen´ y ˇsum nebo o skuteˇcnost, ˇze pixel n´aleˇz´ı nˇejak´e hranˇe. Pouˇzit´ı interpolace je vhodn´e v pˇr´ıpadˇe dalˇs´ıho postupu metodou zaloˇzenou na v´ ypoˇctu gradientu v range image. Poˇc´ıtaj´ı se v n´ı rozd´ıly sousedn´ıch pixel˚ u v prvn´ı vrstvˇe rastru bez ohledu na to, zda pixel bod obsahuje, ˇci ne. Do v´ ypoˇctu tak vstupuj´ı i nulov´e pixely. Ve v´ ysledn´em gradientov´em rastru by se proto bez interpolace pr´azdn´ ych pixel˚ u vyskytovaly v jejich okol´ı velk´e hodnoty gradientu. Vstupn´ımi parametry funkce interpolace (Pˇr´ıloha, str. 55) jsou: rastr range image, velikost kernelu, mezn´ı rozd´ıl dvou hodnot range image v okol´ı interpolovan´eho pixelu pro proveden´ı interpolace a poˇcet opakov´an´ı interpolace na cel´em rastru. V´ ystupn´ım parametrem je interpolovan´ y rastr range image.
4.1.2
Zjiˇ stˇ en´ı parametr˚ u norm´ al rovin pro kaˇ zd´ y pixel (bod)
N´asleduj´ıc´ı segmentaˇcn´ı metody spoˇc´ıvaj´ı ve stanoven´ı parametr˚ u rovin, kter´ ym n´aleˇz´ı jednotliv´e body reprezentovan´e pixely. Tyto parametry budou d´ale slouˇzit k rozliˇsen´ı homogenn´ıch oblast´ı mraˇcna (rastru). Parametry byly zjiˇstˇeny nez´avisle pomoc´ı dvou metod, a to prokl´ad´an´ım rovin na mal´em okol´ı bodu (pixelu) a na z´akladˇe v´ ypoˇctu gradientu pixelu z jeho okol´ı. Pro kaˇzd´ y pixel range image jsou tak stanoveny 3 parametry norm´aly definuj´ıc´ı rovinu, v n´ıˇz pixel (bod) leˇz´ı. Jsou to horizont´aln´ı u ´hel θ, vertik´aln´ı u ´hel φ a vzd´alenost od poˇc´atku ρ. Z jednoho rastru range image byly tedy z´ısk´any 3 rastry, podle nichˇz lze prov´est posledn´ı f´azi segmentace pˇriˇrazen´ı pixel˚ u k ploch´am. Prokl´ ad´ an´ı rovin V t´eto metodˇe vyuˇzijeme range image jako informaˇcn´ı zdroj o poloze jednotliv´ ych bod˚ u a jejich sousednosti. Pro kaˇzd´ y bod zjist´ıme parametry norm´aly proloˇzen´ım roviny v bl´ızk´em okol´ı, jeˇz pˇredstavuje matice 3x3, event. 5x5 pixel˚ u. Pro stˇredov´ y pixel matice se tak vypoˇctou parametry norm´aly ze souˇradnic bod˚ u, kter´e spadaj´ı do pixel˚ u t´eto pohybliv´e matice. Do v´ ypoˇctu nebyly zahrnuty body, kter´e se ˇ nevyuˇzily pˇri tvorbˇe range image. V´ ypoˇcet metodou nejmenˇs´ıch ˇctverc˚ u (MNC)
Segmentace ve 2.5D prostoru
26
na z´akladˇe momentu bod˚ u s vyuˇzit´ım singul´arn´ı dekompozice [3] urˇcil pro kaˇzd´ y pixel range image parametry norm´aly θ, φ a ρ. Postupuje se takto: Ze souˇradnic bod˚ u spadaj´ıc´ıch do pohybliv´eho okna matice se vypoˇc´ıtaj´ı pr˚ umˇern´e hodnoty souˇradnic a jejich odchylky od pr˚ umˇeru.
x=
Mxx =
n 1X xi n i
n X
1 n
y=
(x − xi )2
Pn i
yi
Pn
2 i (y − yi )
Myy =
z=
Mzz =
n 1X zi n i
n X
(z − zi )2
(4.5)
(4.6)
i
i
Mxy =
Pn
Myz =
Pn i
[(y − yi )(z − zi )]
Mxz =
Pn
[(x − xi )(z − zi )]
i
i
[(x − xi )(y − yi )]
M=
(4.7)
Mxx Mxy Mxz
Mxy Myy Myz Mxz Myz Mzz
(4.8)
Pomoc´ı funkce singul´arn´ı dekompozice svd() matice M, obsahuj´ıc´ı smˇerodatn´e odchylky souˇradnic bod˚ u spadaj´ıc´ıch do kernelu, z´ısk´ame 3 matice, z nichˇz ta tˇret´ı ˇ obsahuje v posledn´ım sloupci vektor s nejvˇetˇs´ım momentem tˇechto bod˚ u. Cleny ˇ vektoru jsou pr´avˇe parametry a, b, c hledan´e norm´aly roviny. Ctvrt´ y parametr d z´ısk´ame dosazen´ım do obecn´e rovnice pro rovinu.
ax + by + cz + d = 0
(4.9)
Pravo´ uhl´e souˇradnice a, b, c norm´al byly d´ale pˇrevedeny na sf´erick´e θ a φ a vzd´alenost od poˇc´atku soustavy d odpov´ıd´a parametru ρ . Tyto tˇri parametry norm´al rovin kaˇzd´eho pixelu byly zobrazeny do rastr˚ u Theta, Phi a Rho (viz obr´azek 4.6). V´ ypoˇcet prokl´ad´an´ım rovin na okol´ı pixelu prov´ad´ı funkce prokladani rovin (Pˇr´ıloha, str. 56). Jej´ımi vstupn´ımi parametry jsou: oˇciˇstˇen´ y neinterpolovan´ y rastr range image, seznam souˇradnic s indexy, rastr index˚ u bod˚ u ze seznamu souˇradnic, velikost kernelu definuj´ıc´ı okol´ı prokl´adan´e rovinou. V´ ystupn´ımi parametry jsou rasty Theta, Phi a Rho.
Segmentace ve 2.5D prostoru
27
Obr´azek 4.6: Rastry Theta (vlevo), Phi (uprostˇred) a Rho (vpravo). Hodnoty u ´hl˚ u prvn´ıch dvou rastr˚ u jsou ud´any v radianech, hodnoty rastru Rho v metrech.
V´ ypoˇ cet na z´ akladˇ e gradientu Tato metoda, uvedena v publikaci [4], spoˇc´ıv´a v urˇcen´ı gradientu na okol´ı pixelu zvl´aˇst’ v horizont´alan´ım a vertik´aln´ım smˇeru. Podle vztah˚ u odvozen´ ych z obr´azku 4.7 se vypoˇc´ıtaj´ı u ´hly norm´al θ a φ pro kaˇzd´ y pixel pomoc´ı funkce grad based (Pˇr´ıloha, str. 62). Plat´ı: θij = αij − ∆θij
(4.10)
φij = βij − ∆φij , kde αij a βij jsou horizont´aln´ı a vertik´aln´ı u ´hly skenov´an´ı, jeˇz zn´ame pro kaˇzd´ y bod, tedy i pixel o souˇradnic´ıch i, j. Rozd´ılov´e u ´hly ∆θij a ∆φij vypoˇc´ıt´ame funkc´ı arctan z troj´ uheln´ıku o odvˇesn´ach ∆R (gradient) a δ. Prvn´ı odvˇesna, gradient range image, je zmˇena vzd´alenosti od centra sn´ım´an´ı ∆R pˇri pˇrechodu z jednoho pixelu na druh´ y. Horizont´aln´ı gradient se poˇc´ıt´a ve smˇeru zprava doleva, vertik´aln´ı gradient zdola nahoru. Podle toho jsou sestaveny filtry na v´ ypoˇcet obou gradient˚ u (obr´azek 3.1 a 4.8). Druh´a odvˇesna troj´ uheln´ıku δ je d´elka oblouku vymezen´eho u ´hlem ∆α (v hori-
Segmentace ve 2.5D prostoru
28
Obr´azek 4.7: V´ ypoˇcet rozd´ılov´eho u ´hlu ∆φ z gradientu z´ıskan´eho z range image.
zont´aln´ım smˇeru) nebo ∆β (ve vertik´aln´ım smˇeru) o polomˇeru R. ∆α a ∆β je u ´hlov´e rozliˇsen´ı rastru range image, jeˇz nastavujeme pˇri jeho vytvoˇren´ı podle rozliˇsen´ı pˇri skenov´an´ı. V naˇsem pˇr´ıpadˇe se tyto u ´hly rovnaj´ı. δijhoriz = Rij · ∆α (4.11) δijvert
= Rij · ∆β
ij ij ∆θij = arctan ∆R = arctan R∆R δ vert ij ·∆α ij
(4.12) ij ij ∆φij = arctan δ∆R = arctan R∆R horiz ij ·∆β ij
Segmentace ve 2.5D prostoru
29
Podle vztahu ρij = x · cos θij · cos φij + y · sin θij · cos φij + z · sin φij ,
(4.13)
odvozen´eho z Houghovy prostorov´e transformace se vypoˇc´ıt´a tˇret´ı parametr norm´aly - vzd´alenost od poˇca´tku ρ. V´ ypoˇcet gradientu lze prov´est pomoc´ı Sobelova filtru 3x3 viz obr´azek 3.1 nebo pomoc´ı filtru 5x5 navrˇzen´eho autorem publikace [4] Benem Gortem viz obr´azek 4.8.
Obr´azek 4.8: Filtr na v´ ypoˇcet gradientu pro metodu podle Bena Gorteho.
Vstupn´ımi parametry funkce grad based jsou: oˇciˇstˇen´ y interpolovan´ y rastr range image, velikost filtru (3 - Sobel, 5 - Gorte), rozliˇsen´ı range image v rad, seznam souˇradnic s indexy, seznam p˚ uvodn´ıch sf´erick´ ych souˇradnic, rastr index˚ u bod˚ u ze seznamu souˇradnic. V´ ystupn´ımi parametry jsou opˇet 3 rastry - Theta, Phi a Rho.
4.1.3
Pˇ riˇ razen´ı pixel˚ u k ploch´ am podle jejich parametr˚ u
Do z´avˇereˇcn´e f´aze segmentace vstupuj´ı z tˇech pˇredchoz´ıch pouze 2 rastry - rastr Theta a rastr Phi. D˚ uvodem je nadmˇern´ y ˇsum rastru Rho. V pˇr´ıpadˇe v´ ypoˇctu parametr˚ u roviny na z´akladˇe gradientu je urˇcen´ı tohoto parametru ze vzorce 4.13 naprosto nepˇresn´e a zkresluj´ıc´ı. Hodnoty pixel˚ u naleˇzej´ıc´ıch jedn´e rovinˇe, jak je vidˇet na obr´azku 4.9 se pohybuj´ı v rozmez´ı 10 m! Pro pˇriˇrazov´an´ı pixel˚ u k ploch´am byla zvolena metoda region growing. Region growing Metoda je obdobou hladov´eho algoritmu. Na zaˇc´atku se zvol´ı n´ahodn´ y pixel Pi,j , jehoˇz okol´ı (opˇet matice 3x3 pixely) se prohled´av´a. Pokud sousedn´ı pixel Pi±1,j±1
Segmentace ve 2.5D prostoru
30
Obr´azek 4.9: Rastry Theta (vlevo), Phi (uprostˇred) a Rho (vpravo), z´ıskan´e metodou podle Bena Gorteho. Hodnoty u ´hl˚ u prvn´ıch dvou rastr˚ u jsou ud´any v radianech, hodnoty rastru Rho v metrech.
splˇ nuje podm´ınku, tj. rozd´ıly ∆θ = θ(Pi,j ) − θ(Pi±1,i±1 ) a ∆φ = φ(Pi,j ) − φ(Pi±1,i±1 ) nepˇresahuj´ı stanoven´e meze, pˇriˇrad´ı se ke stejn´e ploˇse jako pixel Pi,j . Pokud rozd´ıly ∆θ a ∆φ meze pˇres´ahnou, oznaˇc´ı se pixel jako pixel jin´e“ plochy (hraniˇcn´ı). Pˇri do” saˇzen´ı urˇcit´eho poˇctu pixel˚ u v segmentu (nastaveno na 100) se jako ∆θ a ∆φ poˇc´ıtaj´ı rozd´ıly nov´ ych pixel˚ u a pr˚ umˇern´ ych hodnot parametr˚ u tohoto vzorku. Takto se prohled´a okol´ı vˇsech pixel˚ u n´aleˇzej´ıc´ıch jedn´e ploˇse. Kdyˇz je plocha uzavˇrena hraniˇcn´ımi pixely, oznaˇc´ı se tyto jako neprohledan´e a opˇet se zvol´ı dalˇs´ı n´ahodn´ y, zat´ım neprohledan´ y pixel. Pokraˇcuje se, dokud nejsou vˇsechny pixely pˇriˇrazen´e k nˇejak´e ploˇse. Pixely tvoˇr´ıc´ı plochu o menˇs´ım poˇctu pixel˚ u, neˇz je stanoven´a mez, jsou vyhodnoceny jako ˇsum. Vstupn´ımi parametry funkce region growing (Pˇr´ıloha, str. 58), jeˇz v´ ypoˇcet prov´ad´ı, jsou: rastr Theta, rastr Phi, mezn´ı rozd´ıl hodnot parametru θ, mezn´ı rozd´ıl hodnot parametru φ, minim´aln´ı poˇcet pixel˚ u v segmentu. V´ ystupem funkce je rastr obsahuj´ıc´ı pixely s ˇc´ıslem segmentu, jemuˇz n´aleˇz´ı.
Segmentace ve 2.5D prostoru
31
Obr´azek 4.10: Rozr˚ ust´an´ı homogenn´ıch oblast´ı v algoritmu region growing.
Seznam souˇ radnic segmentovan´ ych bod˚ u Informaci o n´aleˇzitosti k homogenn´ım ploch´am je nyn´ı nutn´e pˇren´est z 2D rastru na p˚ uvodn´ı data. Dalˇs´ı funkce segmenty2seznam (Pˇr´ıloha, str. 61) z p˚ uvodn´ıho seznamu souˇradnic vytvoˇr´ı nov´ y, obsahuj´ıc´ı pouze segmentovan´e body, k jejichˇz souˇradnic´ım x, y, z pˇriˇrad´ı ˇc´ısla segment˚ u. K propojen´ı segmentovan´eho rastru se seznamem souˇradnic slouˇz´ı rastr index, kter´ y vznikl pˇri tvorbˇe range image a obsahuje indexy bod˚ u ze seznamu souˇradnic. Do seznamu se uvedou i body, jeˇz nebyly pouˇzity pˇri tvorbˇe range image, jelikoˇz padly do pixelu, v nˇemˇz byly nahrazeny jin´ ym bl´ızk´ ym bodem. Informace o tˇechto bodech je v matici link, kter´a k index˚ um nepouˇzit´ ych bod˚ u pro range image ud´av´a indexy bod˚ u, jeˇz je nahrazuj´ı. A tak je bod˚ um, kter´e padly do stejn´eho pixelu, pˇriˇrazen´a stejn´a hodnota segmentu. Vstupn´ımi parametry funkce segmenty2seznam jsou: rastr obsahuj´ıc´ı segmenty, seznam souˇradnic s indexy, rastr index˚ u bod˚ u ze seznamu souˇradnic, vektor link s odkazy na ˇc´ısla bod˚ u u bod˚ u odstranˇen´ ych pˇri tvorbˇe range image. V´ ysledky t´eto funkce jsou: seznam segmentovan´ ych bod˚ u se souˇradnicemi xyz a s ˇc´ıslem segmentu, seznam segment˚ u s poˇctem pˇriˇrazen´ ych bod˚ u.
Segmentace ve 2.5D prostoru
32
Obr´azek 4.11: Vizualizace seznamu segmentovan´ ych souˇradnic; barvy n´aleˇz´ı ˇc´ısl˚ um segment˚ u.
4.1.4
Porovn´ an´ı v´ ysledk˚ u
Kombinac´ı tˇechto zm´ınˇen´ ych funkc´ı s r˚ uzn´ ym nastaven´ım jejich parametr˚ u bylo provedeno v´ıce testovac´ıch segmentac´ı. Celkov´e zpracov´an´ı mraˇcna, od naˇcten´ı souˇradnic bod˚ u po nalezen´ı homogenn´ıch oblast´ı a vytvoˇren´ı nov´eho segmentovan´eho seznamu souˇradnic, prob´ıh´a pomoc´ı spouˇstˇec´ıho souboru. Vzhledem k dvˇema metod´am pouˇzit´ ym pro zjiˇstˇen´ı paramer˚ u norm´al rovin byly vytvoˇreny dva tyto soubory. SegmentaceI.m vytvoˇr´ı ze seznamu souˇradnic rastr range image. Ten se d´ale oˇcist´ı od ˇsumu a metodou prokl´ad´an´ı rovin v okol´ı zjist´ı parametry norm´aly roviny kaˇzd´eho pixelu. Vznikl´e rastry Theta a Phi slouˇz´ı jako vstupn´ı parametry pro vlastn´ı segmentaci metodou region growing. Po nalezen´ı homogenn´ıch oblast´ı v rastru je informace o pˇr´ısluˇsnosti pixel˚ u segment˚ um pˇrevedena k jednotliv´ ym bod˚ um do se-
Segmentace ve 2.5D prostoru
33
znamu souˇradnic. S nastaven´ım uveden´ ym v pˇr´ıloze (str. 66) bylo v mraˇcnu urˇceno 53 segment˚ u a k nim pˇriˇrazeno 149 525 bod˚ u. SegmentaceII.m se liˇs´ı od SegmentaceI.m v metodˇe zjiˇst’ov´an´ı parametr˚ u norm´al. V tomto pˇr´ıpadˇe se parametry zjiˇst’uj´ı na z´akladˇe v´ ypoˇctu gradientu v range image. Proto je v´ yhodn´e po ˇcistˇen´ı ˇsumu jeˇstˇe pr´azdn´e hodnoty rastru range image interpolovat. Uspokojiv´ ych v´ ysledk˚ u segmentace lze dos´ahnout nastaven´ım uveden´ ym v pˇr´ıloze (str. 67). Bylo urˇceno celkem 53 homogenn´ıch oblast´ı s 149 759 pˇriˇrazen´ ymi body.
Obr´azek 4.12: V´ ysledky testu Segmentace I (vlevo) a Segmentace II(vpravo).
Oba dva segmentaˇcn´ı procesy prob´ıhaj´ı ve 2.5D prostoru a vyuˇz´ıvaj´ı zobrazen´ı mraˇcna do range image. Pro kaˇzd´ y pixel zjiˇst’uj´ı parametry norm´al rovin, v nichˇz pixel (bod mraˇcna) leˇz´ı, a podle nich d´ale urˇcuje metodou region growing homogenn´ı oblasti rastru. Liˇs´ı se pr´avˇe ve zp˚ usobu urˇcov´an´ı parametr˚ u pixelu. Segmentace I vyuˇz´ıv´a prokl´ad´an´ı roviny na okol´ı pixelu, zat´ımco Segmentace II zjiˇst’uje parametry roviny pˇres v´ ypoˇcet horizont´aln´ıho a vertik´aln´ıho gradientu rastru range image. SegmentaceI je ˇcasovˇe n´aroˇcnˇejˇs´ı na v´ ypoˇcet, avˇsak vykazuje kvalitnˇejˇs´ı v´ ysledn´e rastry Theta, Phi a Rho. Na obr´azku 4.9, v´ ystupu ze SegmentaceII, lze pozorovat pozvolnou zmˇenu barvy
Segmenatace ve 3D prostoru: RANSAC
34
homogenn´ıch ploch ve smˇeru nar˚ ust´an´ı sloupc˚ u u rastru Theta a stejn´ yu ´kaz ve smˇeru nar˚ ust´an´ı ˇra´dk˚ u u rastru Phi. Tuto neˇza´douc´ı zmˇenu barvy lze pˇrisuzovat bud’ zp˚ usobu pˇriˇc´ıt´an´ı rozd´ıl˚ uu ´hl˚ u θ a φ v gradientov´e“ metodˇe, nebo chybˇe ve v´ ypoˇctu. ” Systematickou chybu se ale nepodaˇrilo ve skriptu odhalit. Na v´ ysledn´e segmentaci vˇsak nem´a tento nedostatek vliv, jelikoˇz algoritmus region growin nevytv´aˇr´ı homogenn´ı oblasti na z´akladˇe absolutn´ıch hodnot parametr˚ u v pixelu, ale jejich rozd´ıl˚ u, ˇcili relativn´ıch hodnot. Porovn´av´a totiˇz parametry pixel˚ u na mal´em okol´ı jednoho segmentu. Pokud se vˇsak tento algoritmus pouˇzije pˇri zpracov´an´ı mnohon´asobnˇe vˇetˇs´ıch mraˇcen s velk´ ymi homogenn´ımi oblastmi, algoritmus ˇca´steˇcnˇe selh´av´a a v jedn´e homogenn´ı ploˇse vytv´aˇr´ı s nar˚ ustaj´ıc´ımi sloupci a ˇra´dky nov´e segmenty. Na z´avˇer bylo zpracov´ano vˇetˇs´ı mraˇcno fas´ady poˇr´ızen´e z jednoho stanoviska, ale s menˇs´ım rozliˇsen´ım (α = 2, 76 ’), neˇz mraˇcno testovan´e. Pouˇzita byla SegmentaceI. V´ ysledn´ y segmentovan´ y rastr je volnˇe pˇriloˇzen v desk´ach diplomov´e pr´ace ve form´atu A3. ´ V´ ystupy segmentac´ı jsou uloˇzeny na pˇriloˇzen´em datov´em CD v adres´aˇri VYSLEDKY v souborech SegmentaceI.mat, SegmentaceII.mat a fasada.mat).
4.2
Segmenatace ve 3D prostoru: RANSAC
Robustn´ı algoritmus RANSAC lze vyuˇz´ıt k segmentaci dat LS pˇr´ımo ve 3D prostoru. Algoritmus se aplikuje na cel´e mraˇcno bod˚ u a zjist´ı se parametry roviny, kter´a proch´az´ı nejvˇetˇs´ı plochou zamˇeˇrenou v souboru dat (zde jde o z´akladn´ı rovinu fas´ady). Po jej´ım nalezen´ı se v´ ypoˇcet provede opˇet. Nyn´ı vˇsak jen na datech, kter´a byla v pˇredchoz´ım v´ ypoˇctu oznaˇcena jako outliars, ˇc´ımˇz se zamez´ı opˇetovn´emu pouˇzit´ı jiˇz segmentovan´ ych bod˚ u. Zjist´ı se parametry dalˇs´ı nejvˇetˇs´ı roviny v mraˇcnu a postup se takto opakuje, aˇz ze souboru mˇeˇren´ ych dat zbyde pouze mal´e mnoˇzstv´ı bod˚ u, kter´e jsou povaˇzov´any za ˇsum. Ten se pˇredem stanov´ı podle ˇclenitosti objektu a kvality mˇeˇren´ ych dat. Ud´av´a se v procentech z cel´eho mraˇcna. Pro segmentaci v programu Matlab byla pouˇzita speci´aln´ı knihovna RANSAC. Fukce RANSAC, obsaˇzena v tomto bal´ıˇcku, vˇsak musela b´ yt m´ırnˇe upravena podle algoritmu z [5] tak, jak je pops´an v kapitole 3.7 a byla uloˇzena pod n´azvem RNS (Pˇr´ıloha, str. 63).
Segmenatace ve 3D prostoru: RANSAC
35
Vstupn´ımi parametry t´eto funkce jsou: namˇeˇren´a data - seznam souˇradnic xyz, odkaz na funkci poˇc´ıtaj´ıc´ı parametry roviny, poˇcet nutn´ ych bod˚ u k v´ ypoˇctu modelu, odkaz na funkci poˇc´ıtaj´ıc´ı odchylky bod˚ u od modelu, poˇcet iterac´ı algoritmu a mezn´ı hodnota odchylky bodu inliar“. ” D´ale tedy bylo nutn´e vytvoˇrit skript na v´ ypoˇcet parametr˚ u roviny (model rovina.m - Pˇr´ıloha, str. 64) a skript na v´ ypoˇcet odchylek bod˚ u od proloˇzen´e roviny (vzdalenost.m - Pˇr´ıloha, str.65). Funkce model roviny.m zjiˇst’uje parametry rovin pr´avˇe pˇres v´ ypoˇcet momentu (viz 4.1.2 Prokl´ad´an´ı rovin). V´ ystupy funkce RNS jsou: vektor oznaˇcuj´ıc´ı inliars (1) a outliars (0), a vektor obsahuj´ıc´ı parametry roviny.
Obr´azek 4.13: Mraˇcno bod˚ u segmentovan´e algoritmem RANSAC; barvy n´aleˇz´ı ˇc´ısl˚ um segment˚ u.
Test byl spuˇstˇen pomoc´ı souboru SegmentaceRNS.m, jehoˇz nastaven´ı je uvedeno v pˇr´ıloze na stranˇe 65. Poˇcet iterac´ı byl stanoven podle vzorce 3.1. Pˇri nastaven´ı pravdˇepodobnosti p = 95%, poˇctu nutn´ ych bod˚ u n = 3 a pomˇeru inliers/outliers w = 1/4) to je pˇribliˇznˇe 200 iterac´ı. Mezn´ı vzd´alenost pro body ”inliars”byla nasta-
Segmenatace ve 3D prostoru: RANSAC
36
vena na 0.008 m. D´ale je nutn´e zkontrolovat ˇci upravit v inicializaˇcn´ı ˇca´sti souboru Segmentaˇ ceRNS.m hodnotu ˇsumu mraˇcna. Sum byl v tomto pˇr´ıpadˇe nastaven na 0.15 (15%). Celkem bylo urˇceno 13 segment˚ u s 15 488 pˇriˇrazen´ ymi body. Veˇsker´e v´ ystupy z v´ y´ poˇctu jsou uloˇzeny v adres´aˇri VYSLEDKY v souboru SegmentaceRNS.mat. Metodu segmentace s pouˇzit´ım algoritmu RANSAC je vhodn´e vyuˇz´ıt sp´ıˇse v pˇr´ıpadˇe m´alo ˇclenit´ ych jednoduˇsˇs´ıch objekt˚ u, obsahuj´ıc´ıch pouze rovnobˇeˇzn´e ˇci kolm´e plochy. V opaˇcn´em pˇr´ıpadˇe doch´az´ı pˇri posuzov´an´ı inliars/outliars jedn´e plochy k oznaˇcen´ı bod˚ u, n´aleˇzej´ıc´ıch jin´e ploˇse v m´ıstˇe pr˚ useˇcnice proloˇzen´ ych rovin. Z obr´azku 4.13 je patrn´e chybn´e urˇcen´ı ˇsikm´eho prvku suprafenestry, jehoˇz ˇca´sti jsou pˇriˇrazeny r˚ uzn´ ym segment˚ um svisl´ ych ploch a pilastr˚ u fas´ady. Viditelnˇe si tak´e algoritmus nedok´aˇze poradit s ˇclenit´ ymi prvky kolem oken (ˇsambr´anou). Dalˇs´ım, ne tak z´avaˇzn´ ym probl´emem jsou plochy n´aleˇzej´ıc´ı sice jedn´e rovinˇe, avˇsak fyzicky oddˇelen´e. Pro jejich spr´avnou segmentaci je potˇreba dalˇs´ıho algoritmu, kter´ y by je oddˇelil a vytvoˇril z kaˇzd´eho samostatn´ y segment. Aˇckoli je tato metoda segmentace pomˇernˇe rychl´a ve srovn´an´ı s dvˇema pˇredchoz´ımi, jej´ı u ´ˇcinnost nen´ı zdaleka tak vysok´a.
5. Praktick´a ˇc´ast II - segmentace v programu Geomagic Studio 10
37
5 Praktick´ aˇ c´ ast II - segmentace v programu Geomagic Studio 10 V ˇsirok´e nab´ıdce program˚ u na zpracov´an´ı dat LS, kter´e jsou dostupn´e na trhu, jen m´alokter´e umoˇzn ˇuj´ı automatickou segmentaci mraˇcna. Jedn´ım z tˇechto softwar˚ u je Geomagic Studio 10. Program pracuje s namˇeˇren´ ymi daty v nˇekolika r˚ uzn´ ych reˇzimech (f´az´ıch), kter´e na sebe navz´ajem navazuj´ı. Jsou to tzv. Point Phase – pracuje se s namˇeˇren´ ym mraˇcnem bod˚ u; v´ ysledkem je troj´ uheln´ıkov´a s´ıt’ vytvoˇren´a z oˇrezan´eho a upraven´eho mraˇcna Wrap Phase – pouˇz´ıv´a se pouze v pˇr´ıpadˇe objekt˚ u s objemem, jejichˇz povrch m´a troj´ uheln´ıkov´a s´ıt’ pokr´ yvat, v´ ysledek se d´ale zpracov´av´a v n´asleduj´ıc´ı f´azi Polygon Phase – u ´prava vygenerovan´e troj´ uheln´ıkov´e s´ıtˇe Shape Phase – s troj´ uheln´ıkovou s´ıt´ı se pracuje jako s objektem, jehoˇz strukturu lze d´ale analyzovat; moˇznost segmentace a pˇrevodu na CAD model. Fashion Phase – s troj´ uheln´ıkovou s´ıt´ı pracuje jako s objektem, umoˇzn ˇuje pr´aci s jednotliv´ ymi ˇca´stmi (plochami) objektu; moˇznost segmentace, klasifikace segment˚ u a pˇrevodu na CAD model. Testovan´e mraˇcno bod˚ u bylo postupnˇe zpracov´ano v Point Phase, Polygon Phase a Fasion Phase. Pr´avˇe v posledn´ım reˇzimu, Fashion Phase, lze objekt automaticky i manu´alnˇe segmentovat, d´ale klasifikovat, tzn. pˇriˇrazovat segment˚ um jednoduch´e matematicky definovan´e plochy (rovina, v´alcov´a plocha, kulov´a plocha a podobnˇe), a segmenty tˇemito plochami prokl´adat. Automatick´a segmentace byla provedena tak´e v reˇzimu Shape Phase. V´ ysledky obou automatick´ ych segmentac´ı jsou stejn´e, mezi reˇzimy lze libovolnˇe pˇrep´ınat a aktivovat tak r˚ uzn´e funkce.
Point Phase
38
V n´asleduj´ıc´ıch kapitol´ach bude struˇcnˇe pops´an postup zpracov´an´ı v programu Geomagic Studio 10 od poˇca´teˇcn´ı Point Phase aˇz po koneˇcnou f´azi Fashion Phase, v n´ıˇz pr´avˇe segmentace prob´ıh´a. Pro dosaˇzen´ı uspokojiv´ ych v´ ysledk˚ u nelze vˇsak za´ eˇsnost segmentace znaˇcnˇe z´avis´ı na vhodnedbat zpracov´an´ı v pˇredchoz´ıch f´az´ıch! Uspˇ n´e u ´pravˇe a selekci mraˇcna bod˚ u a na uspoˇr´ad´an´ı vygenerovan´e troj´ uheln´ıkov´e s´ıtˇe.
5.1
Point Phase
Point Phase, neboli f´aze bod˚ u, pracuje s namˇeˇren´ ymi body povrchu objekt˚ u.
Obr´azek 5.1: Namˇeˇren´a data naˇcten´a do programu Geomagic Studio 10.
Nejprve bylo do programu Geomagic Studio 10 naˇcteno mraˇcno bod˚ u uloˇzen´e jako seznam souˇradnic v souboru okno.xyz (File → Open). Ruˇcnˇe byly oˇrez´any odlehl´e shluky bod˚ u a d´ale se aplikovaly tyto funkce (pozn´amky v z´avork´ach ud´ avaj´ı nastaven´ı pouˇzit´e na testovan´em mraˇcnu bod˚ u): Select disconnected Automatick´e vyhled´av´an´ın´ı odlehl´ ych nespojit´ ych shluk˚ u bod˚ u. Nastavuje se stupeˇ n odlehlosti (Separation: low ) a procentu´aln´ı zastoupen´ı odlehl´ ych shluk˚ u (Size: 5.0 % )
Point Phase
39
Select outliars Automatick´e vyhled´av´an´ı odlehl´ ych bod˚ u - outliars. Nastavuje se stupeˇ n citlivosti ve ˇsk´ale 0 - 100 (Senzitivity: 10 ). Reduce noise Tato funkce posunuje vybran´e body tak, aby doˇslo ke sn´ıˇzen´ı ˇsumu na povrchu zamˇeˇren´eho objektu. V z´aloˇzce Parametrs se zvol´ı typ povrchu (Prismatic shapes (conservative)), stupeˇ n vyhlazen´ı 0 - 4 (Smoothness Level: 1 ), poˇcet iterac´ı (Iterations: 1 ) a maxim´aln´ı vzd´alenost, o n´ıˇz m˚ uˇze b´ yt bod posunut (Deviation limit: 0.005 m). V z´aloˇzce Outliars se nastav´ı mezn´ı vzd´alenost, kdy body jiˇz nejsou klasifikovan´e jako ˇsum a neposunuj´ı se (Treshold: 0.01 m), a zvol´ı se, zda budou tyto body pouze oznaˇceny, nebo se rovnou odstran´ı (Delete). Z´aloˇzka Display Deviation umoˇzn ˇuje vizu´aln´ı kontrolu posun˚ u bod˚ u (viz Obr´azek 5.2).
Obr´azek 5.2: Posuny bod˚ u pˇri aplikaci filtru Reduce noice, ud´ano v metrech.
V z´aloˇzce Statistics lze zjistit pr˚ umˇer posun˚ u vˇsech bod˚ u od ide´aln´ıho povrchu (Average distance: 0.0013 m) a smˇerodatnou odchylku posun˚ u (Standard deviation 0.0010 m). Zm´aˇcknut´ım tlaˇc´ıtka Crease info se lze informovat o hodnotˇe tzv. Crease ” angle“, kter´a ud´av´a, zda je takto upraven´e mraˇcno vhodn´e pro vytvoˇren´ı troj´ uheln´ıkov´e s´ıtˇe. Tato hodnota by nemˇela b´ yt vˇetˇs´ı neˇz 10. Pˇri sn´ıˇzov´an´ı ˇsumu testovan´eho mraˇcna bylo dosaˇzeno hodnoty 9.29.
Polygon Phase
40
Uniform sample Ke sn´ıˇzen´ı hustoty bod˚ u v rovinn´ ych homogenn´ıch oblastech slouˇz´ı pr´avˇe funkce Uniform sample. Zad´an´ım koneˇcn´eho poˇctu bod˚ u ˇci v´ ysledn´e vzd´alenosti mezi nimi v z´aloˇzce Input lze redukovat poˇcet bod˚ u cel´eho mraˇcna (Absolute → Spacing: 0.02 m). Hustotu bod˚ u na hran´ach lze ˇc´asteˇcnˇe, ˇci plnˇe zachovat nastaven´ım stupnˇe d˚ uleˇzitosti zakˇriven´ı v rozmez´ı 0 - 10 v z´aloˇzce Optimize (Curvature priority: 10 ). V´ yˇrez mraˇcna po
Obr´azek 5.3: Aplikace filtru Uniform sample.
aplikaci filtru je na Obr´azku 5.3.
Wrap Funkc´ı Wrap z´ısk´ame z mraˇcna bod˚ u troj´ uheln´ıkovou s´ıt’, kterou lze d´ale zpracov´avat v reˇzimu Wrap Phase ˇci Polygon Phase. V z´aloˇzce Wrap Type se vybere, zda jde o rovinn´ y objekt ˇci objekt s objemem (v tomto pˇr´ıpadˇe bylo zaˇskrtnuto Surface). V z´aloˇzce Advanced Option je moˇzn´e nastavit u ´roveˇ n dalˇs´ıho sn´ıˇzen´ı ˇsumu (Noise Reduction: Medium), popˇr´ıpadˇe v´ ysledn´ y poˇcet troj´ uheln´ık˚ u s´ıtˇe a hustotu prostorov´e mˇr´ıˇzky, do jej´ıˇz kaˇzd´e buˇ nky m´a pˇripadnout nejv´ıˇse 1 bod. Tyto dvˇe hodnoty vˇsak nastaveny nebyly.
5.2
Polygon Phase
Reˇzim Polygon Phase slouˇz´ı k u ´pravˇe vygenerovan´e troj´ uheln´ıkov´e s´ıtˇe a vytvoˇren´ı vyhlazen´eho souvisl´eho modelu povrchu bez dˇer.
Polygon Phase
41
Flip normals Nejprve se urˇc´ı rub a l´ıc vytvoˇren´e s´ıtˇe u ´pravou smˇeru norm´al troj´ uheln´ık˚ u. Funkce Flip normals prohod´ı smˇer norm´al cel´e s´ıtˇe, nebo jen vybran´ ych ˇca´st´ı. Fill holes Druhou aplikovanou funkc´ı je vyplnˇen´ı neˇz´adouc´ıch otvor˚ u (dˇer) v s´ıti. V nab´ıdce t´eto funkce je nˇekolik metod vyplnˇen´ı (celkov´e a ˇc´asteˇcn´e vyplnˇen´ı, vytvoˇren´ı most˚ u atd.). D´ıry je moˇzn´e vyplnit automaticky, ˇci proch´azet jednu po druh´e a vyb´ırat zp˚ usob vyplnˇen´ı. Sandpaper Pomoc´ı tohoto filtru lze pˇrej´ıˇzdˇen´ım kurzoru po troj´ uheln´ıkov´e s´ıti povrchu objektu ruˇcnˇe vyhladit jej´ı nerovnosti (viz Obr´azek 5.4). Volbou Relax se vyhlad´ı st´avaj´ıc´ı s´ıt’, zat´ımco volbou Clean se v oznaˇcen´e oblasti p˚ uvodn´ı troj´ uheln´ıky odstran´ı a vytvoˇr´ı se nov´a upraven´a s´ıt’. V z´aloˇzce Strenght se vol´ı m´ıra vyhlazen´ı.
Obr´azek 5.4: Ruˇcn´ı vyhlazen´ı pomoc´ı kurzoru ve funkci Sandpaper.
Decimate polygons Tato funkce sniˇzuje poˇcet troj´ uheln´ık˚ u s´ıtˇe jejich nahrazov´an´ım troj´ uheln´ıky o delˇs´ıch stran´ach.V z´aloˇzce Settings se nab´ızej´ı reˇzimy nastaven´ı redukce. Dˇeje se tak bud’ nastaven´ım mezn´ı vzd´alenosti mezi polohou vrcholu p˚ uvodn´ıho troj´ uheln´ıku a polohou nov´e s´ıtˇe, nebo ud´an´ım v´ ysledn´eho poˇctu troj´ uheln´ık˚ u (zvoleno Reduction
Polygon Phase
42
mode: Triangle count → Target triangle count: 20% ). V z´aloˇzce Advanced byla nastavena d˚ uleˇzitost pravidelnosti s´ıtˇe na maximum (Mesh Priority). Z Obr´azku 5.5 je zˇrejm´e, na kter´e ˇca´sti modelu byla tako funkce pouˇzita.
Obr´azek 5.5: Decimate polygons: Redukce poˇctu troj´ uheln´ık˚ u v rovinn´ ych oblastech s´ıtˇe.
Open manifold Tato funkce slouˇz´ı k vyˇciˇstˇen´ı troj´ uheln´ıkov´e s´ıtˇe a odstranˇen´ı nˇekter´ ych troj´ uheln´ık˚ u tak, aby s´ıt’ byla spojit´a, tzn. kaˇzd´ y vnitˇrn´ı troj´ uheln´ık bude z kaˇzd´e sv´e strany sousedit pr´avˇe s jedn´ım troj´ uheln´ıkem. Repair intersection Pokud se v s´ıti vyskytuj´ı troj´ uheln´ıky, kter´e se navz´ajem prot´ınaj´ı, lze je vyhledat pr´avˇe funkc´ı Repair intersection. V z´aloˇzce Mode se pot´e zvol´ı, jak se tyto troj´ uheln´ıky oprav´ı. Byla zaˇskrtnuta moˇznost Select Only a po ukonˇcen´ı funkce byly vybran´e oblasti z ˇca´sti smaz´any a dotvoˇreny funkc´ı Fill Holes (viz v´ yˇse). Tato u ´prava je nezbytn´a pro pokraˇcov´an´ı v daˇs´ıch reˇzimech Shape Phase nebo Fashion Phase.
Fashion & Shape Phase
5.3
43
Fashion & Shape Phase
V tˇechto dvou reˇzimech je moˇzn´e prov´adˇet automatickou a poloautomatickou segmentaci mraˇcna, jeˇz je v pˇredeˇsl´ ych dvou f´az´ıch upraveno a z nˇehoˇz je vytvoˇrena troj´ uheln´ıkov´a s´ıt’. Fashion Phase a Shape Phase se od sebe liˇs´ı dalˇs´ım zpracov´an´ım segment˚ u. Zat´ımco Shape Phase pˇristupuje ke vˇsem segment˚ um jako k obecn´ ym ploch´am, pl´at˚ um, v reˇzimu Fashion Phase lze segmenty n´aslednˇe klasifikovat jako jednoduch´e matematick´e plochy (rovina, v´alcov´a, kuˇzelov´a a kulov´a plocha atd..). Detect contours Ve funkci Detect contours, jeˇz je aktivn´ı v obou reˇzimech, prob´ıh´a automatick´a segmentace troj´ uheln´ıkov´e s´ıtˇe. Parametry rozpozn´av´an´ı homogenn´ıch oblast´ı se nach´az´ı v z´aloˇzce Regions. Nastavuje se zde citlivost k zakˇriven´ı 0 - 100% (Curvature senzitivity: 98% ), tlouˇst’ka oddˇelovac´ıch p´as˚ u mezi homogenn´ımi oblastmi 0 - 100% (Separator Senzitivity: 5% ) a velikost nejmenˇs´ıho moˇzn´eho segmentu (Minimum area: 0.01m2 ). Po spuˇstˇen´ı segmentace (tlaˇc´ıtko Compute regions) se zobraz´ı troj´ uheln´ıkov´a s´ıt’ rozdˇelen´a na homogenn´ı oblasti odliˇsen´e barvami a ohraniˇcen´e tzv. separ´atory (Obr´azek 5.6, vlevo).
Obr´azek 5.6: V´ ysledek automatick´e segmentace (vlevo) a jeho ruˇcn´ı editace (vpravo).
Fashion & Shape Phase
44
Separ´atory jsou ˇcervenˇe vyznaˇcen´e oblasti s velkou m´ırou zakˇriven´ı. Jedn´a se tedy o hrany oddˇeluj´ıc´ı jednotliv´e segmenty (plochy).
Obr´azek 5.7: Pouˇzit´ı funkce Remove islands.
Automaticky vyhodnocenn´e segmenty lze d´ale upravovat funkcemi, jeˇz nab´ız´ı z´aloˇzka Edit. Funkce Remove islands odstran´ı separ´atory, v pˇr´ıpadˇe, ˇze neodˇeluj´ı dva segmenty, ale vyskytuj´ı se uprostˇred jednoho segmentu (viz Obr´azek 5.7). D´ale je moˇzn´e odstranit pˇr´ıliˇs mal´e segmenty (Remove Small Regions) a vytv´aˇret ˇci odstraˇ novat oblasti separ´ator˚ u pomoc´ı kurzoru (lev´ ym tlaˇc´ıtkem myˇsi lze oznaˇcit troj´ uheln´ık s´ıtˇe za separ´ator, Ctrl + lev´e tlaˇc´ıtko myˇsi oznaˇcen´ı separ´atoru zruˇs´ı). Na Obr´azku 5.6 je v´ ysledek automatick´eho vyhodnocen´ı a n´asledn´a ruˇcn´ı editace segmentovan´eho objektu. Po vˇsech u ´prav´ach lze tak´e vygenerovat kˇrivky pˇredstavuj´ıc´ı hrany objektu, a to stisknut´ım tlaˇc´ıtka Extract v z´aloˇzce Contours. Kˇrivky jsou vytvoˇreny v m´ıstech oznaˇcen´ ych jako separ´atory (viz Obr´azek 5.8). Tyto kˇrivky lze propojovat (tlaˇc´ıtko Contract), avˇsak po ukonˇcen´ı funkce Detect contours je nelze jiˇz d´ale upravovat. Extract Untrimmed surfaces Zat´ımco ˇreˇzim Shape Phase pracuje s obecn´ ymmi plochami (funkce nab´ıdky Patches), funkc´ı Extract Untrimmed surfaces v reˇzimu Fashion Phase lze segmenty klasifikovat jako r˚ uzn´a matematick´a primitiva, tyto plochy jimi proloˇzit a vygene-
Fashion & Shape Phase
45
Obr´azek 5.8: Vygenerov´an´ı kˇrivek z oblast´ı separ´ator˚ u.
rovat model kompatibiln´ı s CADovsk´ ymi programy. Pracuje se pouze se segmenty generovan´ ymi ve funkci Detect contours, tud´ıˇz nen´ı tˇreba v pˇredeˇsl´e funkci extrahovat hrany. Z´aloˇzka Operations nab´ız´ı nˇekolik funkc´ı, jimiˇz postupnˇe proch´az´ıme. Prvn´ı z nich je Classify (viz Obr´azek 5.9), kter´a umoˇzn ˇuje urˇcen´ı matematick´e plochy, jeˇz segment pˇredstavuje. Urˇcen´ı prob´ıh´a bud’ automaticky, nebo ruˇcnˇe v´ ybˇerem z nab´ızen´ ych definovan´ ych ploch (rovina, v´alcov´a, kuˇzelov´a
Obr´azek 5.9: Dialog Classify.
a kulov´a plocha, architektonick´ y v´ ystupek, rotaˇcn´ı plocha a obecn´a plocha). Po klasifikaci n´asleduje proloˇzen´ı klasifikovan´ ych segment˚ u pˇriˇrazen´ ymi plochami (Fit). Pomoc´ı funkce Analyze je moˇzn´e zobrazit odchylky p˚ uvodn´ı troj´ uheln´ıkov´e s´ıtˇe od proloˇzen´e plochy a statistick´e u ´daje o proloˇzen´ı (viz Obr´azek 5.10). Proloˇzen´ım segment˚ u z´ısk´ame z t´eto funkce reˇzimu Fashion Phase CADovsk´ y model. Stejnˇe tak ho z´ısk´ame v reˇzimu Shape Phase, avˇsak sloˇzitˇejˇs´ı, sloˇzen´ y pouze z obecn´ ych pl´at˚ u a kˇrivek (Obr´azek 5.11).
Fashion & Shape Phase
46
Obr´azek 5.10: Odchylky od p˚ uvodn´ı s´ıtˇe pˇri proloˇzen´ı vˇsech segment˚ u rovinami, ud´ano v metrech.
V porovn´an´ı s automatickou segmentac´ı pomoc´ı vlastn´ıch skript˚ u v prostˇred´ı v´ ypoˇcetn´ıho programu Matlab se jev´ı pr´ace v softwaru Geomagic Studio 10 na prvn´ı pohled snazˇs´ı a pohodlnˇejˇs´ı d´ıky pˇr´ıjemn´emu grafick´emu rozhran´ı. Zpracov´an´ı mraˇcna v tomto softwaru je ale ˇcasovˇe mnohem n´aroˇcnˇejˇs´ı vzhledem k znaˇcn´ ym u ´prav´am a aplikac´ım mnoha filtr˚ u. Samotn´a automatick´a segmentace je pouze souˇca´st´ı funkce slouˇz´ıc´ı k detekci hran. Rozpozn´av´an´ı hran zˇrejmˇe prob´ıh´a na z´akladˇe zmˇeny sklonu troj´ uheln´ık˚ u v troj´ uheln´ıkov´e s´ıti, jej´ıˇz vytvoˇren´ı je k proveden´ı segmentace nezbytn´e. Z obr´azku 5.6 je patrn´a menˇs´ı citlivost v rozezn´av´an´ı hran drobnˇejˇs´ıch segment˚ u. Dalˇs´ı ruˇcn´ı u ´prava segmentovan´e s´ıtˇe je moˇzn´a, avˇsak opˇet ˇcasovˇe velmi n´aroˇcn´a.
Fashion & Shape Phase
47
Obr´azek 5.11: CADovsk´ y model generovan´ y ve Fashion Phase (vlevo) a v Shape Phase (vpravo).
6. Z´avˇer
48
6 Z´ avˇ er C´ılem pr´ace bylo prostudov´an´ı souˇcasn´ ych trend˚ u v automatick´em zpracov´an´ı dat laserov´eho skenov´an´ı (leteck´eho i pozemn´ıho), d´ale aplikace nˇekter´ ych metod ve vlastn´ım skriptu ve v´ ypoˇcetn´ım programu Matlab a zpracov´an´ı dat v nˇekter´em z komerˇcn´ıch softwar˚ u. Teoretick´a ˇc´ast diplomov´e pr´ace se vˇenuje nˇekolika metod´am automatick´eho zpracov´an´ı dat, konkr´etnˇe jeho ˇc´asti - segmentaci mraˇcna bod˚ u. Problematice segmentace se v souˇcasn´e dobˇe vˇenuj´ı hlavnˇe v zahraniˇc´ı. Pr´ace ˇcerp´a pˇredevˇs´ım z publikac´ı vydan´ ych na univerzit´ach v Nˇemecku a Nizozem´ı. Ke zpracov´an´ı prostorov´ ych dat, poˇr´ızen´ ych jak pˇri leteck´em, tak pozemn´ım skenov´an´ı, lze pˇristupovat r˚ uznˇe. Jednou z moˇznost´ı je jejich pˇreveden´ı do 2.5D prostoru, kde u ´pln´ yu ´daj o poloze ud´av´a poloha pixelu ve 2D obrazu a jeho hodnota. Dalˇs´ı postupy jsou v´ıce m´enˇe shodn´e s postupy zpracov´an´ı obrazov´ ych dat DPZ a fotogrammetrie. Homogenn´ı oblasti - segmenty - lze tak urˇcovat napˇr. detekc´ı hran, shlukovou anal´ yzou a metodou region growing. Pro zpracov´an´ı ve 3D lze aplikovat napˇr. algoritmus RANSAC, jenˇz n´ahodnˇe a opakovanˇe prokl´ad´a mraˇcnem bod˚ u roviny, hledaj´ıc tak nejvˇetˇs´ı homogenn´ı plochu. Dalˇs´ı moˇznost´ı je propojit body mraˇcna pomoc´ı Delaunayovy triangulace, porovn´avat d´elky hran (bl´ızkost bod˚ u), a tak vytv´aˇret segmenty. Rozdˇelen´ım mraˇcna na soustavy profilov´ ych p´as˚ u v r˚ uzn´ ych smˇerech zjednoduˇs´ıme u ´lohu ve 3D na u ´lohu v ploˇse. Propojov´an´ım bl´ızk´ ych bod˚ u v r´amci kaˇzd´eho p´asu a zpˇetn´ ym propojen´ım vˇsech profil˚ u vznikne soubor spojit´ ych graf˚ u, jeˇz pˇredstavuj´ı segmenty. Moˇznost´ı a algoritm˚ u vyuˇziteln´ ych v automatick´e segmentaci je velk´e mnoˇzstv´ı, kaˇzd´ y m´a sv´e v´ yhody a nev´ yhody. Pr´ace ve 3D je napˇr´ıklad v´ ypoˇcetnˇe n´aroˇcnˇejˇs´ı, ale umoˇzn ˇuje zpracov´an´ı v´ıce registrovan´ ych mraˇcen najednou narozd´ıl od zpracov´an´ı ve 2.5D, kdy se do plochy pˇrev´ad´ı pouze data mˇeˇren´a z jednoho stanoviska.
6. Z´avˇer
49
V praktick´e ˇc´asti pr´ace je pops´ana aplikace vytvoˇren´ ych vlastn´ıch skript˚ u na mraˇcno bod˚ u budovy Arcibiskupsk´eho semin´aˇre v Praze, Dejvic´ıch. Pro segmentaci byly zvoleny metody: region growing podle parametr˚ u roviny, j´ıˇz pixel n´aleˇz´ı (parametry byly zjiˇstˇeny na z´akladˇe v´ ypoˇctu gradientu a nebo prokl´ad´an´ım roviny na okol´ı pixelu), a segmentace pomoc´ı algoritmu RANSAC. Pro metodu region growing byly parametry, podle nichˇz se urˇcovaly homogenn´ı oblasti, vytvoˇreny dvˇema zp˚ usoby, a proto testov´an´ı prob´ıhalo pro oba pˇr´ıpady zvl´aˇst’. Obˇe metody, avˇsak pˇri pouˇzit´ı r˚ uzn´eho nastaven´ı algoritmu region growing, vykazuj´ı obdobn´e v´ ysledky. Metoda vyuˇz´ıvaj´ıc´ı algoritmu RANSAC je velmi rychl´a, ale m´a jist´e nedostatky. Pokud dojde k jejich odstranˇen´ı, tato metoda m˚ uˇze zauj´ımat prvn´ı m´ısto v automatizaci zpracov´an´ı dat LS. Pro zpracov´an´ı mraˇcna bod˚ u v komerˇcn´ım software byl k dispozici byl pouze jedin´ y program, a to na zpracov´an´ı dat pozemn´ıho prostorov´eho skenov´an´ı - Geomagic Studio 10. Nebylo tak moˇzn´e vyzkouˇset pr´aci se softwarem na zpracov´an´ı dat leteck´eho skenov´an´ı, ˇci porovnat pr´aci s v´ıce softwary. Geomagic Studio 10 je jedin´ ym dostupn´ ym programem na stavebn´ı fakultˇe, kter´ y zpracov´av´a data pozemn´ıho laserov´eho skenov´an´ı a z´aroveˇ n obsahuje n´astroje na segmentaci mraˇcna bod˚ u. Pr´ace s t´ımto softwarem je pˇr´ıjemn´a d´ıky grafick´emu rozhran´ı, ale ˇcasovˇe je zpracov´an´ı dat daleko n´aroˇcnˇejˇs´ı. Mraˇcno bod˚ u se mus´ı nejprve ruˇcnˇe oˇcistit a upravit mnoha funkcemi, jejichˇz spr´avn´e nastaven´ı mus´ı m´enˇe zkuˇsen´ y uˇzivatel ˇcasto pouze odhadovat a nal´ezt jej ˇcetn´ ymi pokusy. Mraˇcno bod˚ u proch´az´ı nejm´enˇe tˇremi pracovn´ımi f´azemi programu, pˇriˇcemˇz aˇz v posledn´ı f´azi je moˇzn´e segmentaci prov´est. Hranice homogenn´ıch oblast´ı urˇcen´ ych automatickou segmentac´ı lze d´ale ruˇcnˇe upravit. Automatick´a segmentace v tomto programu tˇeˇzko rozezn´a menˇs´ı segmenty a segmenty, mezi nimiˇz je niˇzˇs´ı kˇrivost. Pro vyhodnocen´ı detail˚ u, jako byly pr´avˇe prvky kolem okna budovy Arcibiskupsk´eho semin´aˇre, nen´ı automatick´a segmentace v programu Geomagic zcela vyhovuj´ıc´ı. V´ ysledkem praktick´e ˇca´sti proveden´e ve v´ ypoˇcetn´ım programu Matlab je mraˇcno bod˚ u rozdˇelen´e na homogenn´ı oblasti. Je uloˇzeno jako seznam souˇradnic, k nimˇz jsou pˇriˇrazeny ˇc´ısla segment˚ u. Na z´avˇer byl jeden z postup˚ u segmentace aplikov´an na mraˇcno bod˚ u budovy Arci-
6. Z´avˇer
50
biskupsk´eho semin´aˇre poˇr´ızen´e z jednoho stanoviska. Vizualizace segmentace ve 2.D rastru je vytiˇstˇenana na pap´ır form´atu A3 a pˇriloˇzena v desk´ach diplomov´e pr´ace. Vytvoˇren´e skripty, funkce a v´ ystupy vˇsech proveden´ ych segmentac´ı jsou uloˇzeny na pˇriloˇzen´em datov´em CD. Na cel´ y segmentaˇcn´ı proces by bylo vhodn´e nav´azat dalˇs´ımi funkcemi a skripty, kter´e by skupinami bod˚ u, pˇriˇrazen´ ych jednotliv´ ym segment˚ um, automaticky prokl´adaly rovinu, zjiˇst’ovaly pr˚ useˇc´ıky sousedn´ıch rovin a sestavily tak dr´atov´ y model objektu, d´ale zpracovateln´ y v nˇekter´em CADovsk´em programu. Vytvoˇren´ı takov´ehoto souboru navazuj´ıc´ıch funkc´ı, do nˇehoˇz by uˇzivatel minim´alnˇe zasahoval nastaven´ım jen nˇekolika parametr˚ u, by pˇrispˇelo k rozvoji mlad´e, st´ale se vyv´ıjej´ıc´ı metody mˇeˇren´ı - laserov´eho skenov´an´ı.
Literatura
51
Literatura [1] SITHOLE, George. Segmentation and Classification of Airborne Laser Scanner Data . [s.l.] : [s.n.], 2005. 185 s. [2] LEE, Impyeong. SCHENK, Toni. 3D Perceptual Organization of Laser Altimetry Data. IAPRS 2001, volume XXXIV-3/W4, s. 57-65. [3] AHN, Sung Joon. Least-Squares Orthogonal Distance Fitting of Curves and Surfaces in Space. LNCS 3151, Berlin, 2004. Least-Squares Orthogonal Distance Fitting, s. 17-34. Dizertaˇcn´ı pr´ace. University of St¨ uttgart. [4] GORTE, Ben. Planar feature extraction in terrestrial laser scanning using gradient based rangeimage segmentation. IAPRS 2007, volume XXXVI-3/W52, s. 173-177. [5] FISCHLER, Martin. BOLLES, Robert. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Communication of ACM 1981, volume 24-6 , s. 381–395. [6] BOULAASSAL, Hakim. Automatic segmentation of building facades using terrestrial laser data. IAPRS 2007, volume XXXVI-3/W52, s. 65-70.
Pˇr´ılohy
52
Pˇ r´ıloha Pˇ rehled vlastn´ıch funkc´ı Funkce
Vstupn´ı parametry
V´ ystupn´ı parametry
range image
seznam, pixsize
xyz, rangeimage, index, link, T, polar orig
cisteni
img, mw, treshold
img
interpolace
img , treshold, iterace, mw
img
prokladani rovin
rangeim cist, xyz, index,
Theta, Phi, Rho
mw grad based
rangeim cist int, filtr, pixsize,
Theta, Phi, Rho
xyz,polar orig, index region growing
Phi, Theta, tresholdP, tresholdT,
rastr segmenty
min pix segmenty2seznam
rastr, xyz, index, link
xyz seg, seg body
RNS
mData, ModelFunc, nSampLen,
vMask, Model
ResidFunc, nIter, dThreshold model rovina
data
plane
vzdalenost
data, plane
D
Pˇr´ılohy
53
Range image.m function [xyz,rangeimage,index,link,T,polar_orig] = range_image(seznam,pixsize) % RANGE_IMAGE - funkce pˇ rev´ ad´ ı seznam souˇ radnic mraˇ cna bod˚ u o souˇ radnic´ ıch % xyz do 2.5D range image % % seznam - seznam souˇ radnic bod˚ u, ´ udaje o bodu v ˇ r´ adku (x,y,z) % pixsize - velikost pixelu range image (v rad) podle hustoty skenov´ an´ ı % % [xyz] - nov´ y seznam souˇ radnic, ´ udaje o bod˚ u ve sloupci (x,y,z,1,id) % [rangeimage] - rastr range image % [index] - matice o velikosti range image s indexy bod˚ u ze seznamu % souˇ radnic % [link] - vektor s odkazy na ˇ cı ´sla bod˚ u u bod˚ u, kter´ e byly odstranˇ eny % pˇ ri transformaci do range image % [T] - posuny lamda, phi a R pˇ ri transformaci na obrazov´ e souˇ radnice % (vyuˇ zije se pˇ ri dalˇ s´ ıch vizualizac´ ıch) % [polar orig] - seznam p˚ uvodn´ ıch sf´ erick´ ych souˇ radnic (lambda, phi, R) xyz = (seznam(:,1:3))’; xyz(4,:) = 1; xyz(5,:) = find(xyz(1,:));
%%
====
P O L A R
C O O R D I N A T E S
=====
[lambda,phi,rho] = cart2sph(xyz(1,:),xyz(2,:),xyz(3,:)); polar_orig = [lambda;phi;rho]; polar_orig(4,:) = 1; polar_orig(5,:) = xyz(5,:);
% [rad,rad,m]
% translation T = [max(lambda), max(phi), min(rho)]; % transformation to matrix coord. polar = [-1 0 0 T(1) 0; 0 -1 0 T(2) 0; 0 0 1 0 0; 0 0 0 1 0; 0 0 0 0 1]*polar_orig; % transf to pixel polar = round([1/pixsize 0 0 0.5 0; 0 1/pixsize 0 0.5 0; 0 0 1000 0 0; 0 0 0 1 0; 0 0 0 0 1]*polar); % Rho_red = hist/(max(polar(3,:))-min(polar(3,:))); % [DH]/[m] size_img = max(polar,[],2)’; dim = size(polar,2);
%%
====
R A N G E
I M A G E
====
rangeimage = zeros(size_img(2),size_img(1),2,’uint32’); % matice indexu index = zeros(size_img(2),size_img(1)); link = zeros(1,dim); for i=1:dim if polar(3,i) > rangeimage(polar(2,i),polar(1,i)) rangeimage(polar(2,i),polar(1,i),1) = polar(3,i); rangeimage(polar(2,i),polar(1,i),2) = 1; if index(polar(2,i),polar(1,i))~= 0 if (rangeimage(polar(2,i),polar(1,i))- polar(3,i)) < 10 link(index(polar(2,i),polar(1,i)))= polar(5,i); end end index(polar(2,i),polar(1,i)) = polar(5,i); else end end
%
[DH]
Pˇr´ılohy %%
====
54 V I Z U A L I Z A C E
====
Rmin = T(3); rangeim_fig = (rangeimage(:,:,1)-1000*Rmin.*rangeimage(:,:,2)); figure(1); subplot(1,2,1) plot3(xyz(1,:),xyz(2,:),xyz(3,:),’.’,’MarkerSize’,1) xlabel(’X’);ylabel(’Y’);zlabel(’Z’) title(’Mraˇ cno bod˚ u’); grid on view(-110,6); subplot(1,2,2) colormap(’jet’); axis equal; subplot(1,2,2) imagesc(rangeim_fig); title(’Vizualizace range image’); return
Cisteni.m function [img] = cisteni(img,mw,treshold) % % % % %
CISTENI - funkce odstraˇ nuje z range image odlehl´ e body a jejich shluky img - range image mw - velikost poˇ c´ ateˇ cn´ ıho kernelu ˇ ciˇ stˇ en´ ı treshold - maxim´ aln´ ı rozd´ ıl vzd´ alenosti bodu a okoln´ ıho mraˇ cna [mm]
orig_img = img; [a,b,c] = size(img);
while(mw>=3) centr = (mw+1)/2; okraj = (mw-1)/2; for i = centr:(a-okraj) for j = centr:(b-okraj) if ((sum(orig_img(i-okraj,(j-okraj):(j+okraj),2))==0)&&... (sum(orig_img(i+okraj,(j-okraj):(j+okraj),2))==0)&&... (sum(orig_img((i-okraj+1):(i+okraj-1),(j-okraj),2))==0)&&... (sum(orig_img((i-okraj+1):(i+okraj-1),(j+okraj),2))==0)) img((i-okraj+1):(i+okraj-1),(j-okraj+1):(j+okraj-1),1) = 0; img((i-okraj+1):(i+okraj-1),(j-okraj+1):(j+okraj-1),2) = 0; elseif ((sum(orig_img(i-okraj,(j-okraj):(j+okraj),2))== mw)&&... (sum(orig_img(i+okraj,(j-okraj):(j+okraj),2))==mw)&&... (sum(orig_img((i-okraj+1):(i+okraj-1),(j-okraj),2))==(mw-2))&&... (sum(orig_img((i-okraj+1):(i+okraj-1),(j+okraj),2))==(mw-2))) med1 med2 med3 med4
= = = =
median(orig_img(i-okraj,(j-okraj):(j+okraj),1)); median(orig_img(i+okraj,(j-okraj):(j+okraj),1)); median(orig_img((i-okraj+1):(i+okraj-1),(j-okraj),1)); median(orig_img((i-okraj+1):(i+okraj-1),(j+okraj),1));
med = median([med1,med2,med3,med4]);
Pˇr´ılohy
55 for u = (1-okraj):(okraj-1) for v = (1-okraj):(okraj-1) if(abs(med-orig_img(i+u,j+v))>treshold) img(i+u,j+v,1)=0; img(i+u,j+v,2)=0; end end end end
end end orig_img = img; mw2 = (mw+1)/2; if(rem(mw2,2) == 1) mw = mw2; else mw = (mw-1)/2; end end return
Interpolace.m function [img] = interpolace(img,treshold,iterace,mw) % INTERPOLACE - funkce interpoluje pr´ azdn´ e pixely v range image % % img - rangeimage % iterace - pocet opakovani interpolace % treshold - maxim´ aln´ ı rozd´ ıl hodnot pixel˚ u v kernelu (rozdil vzdalenosti) % pro proveden´ ı interpolace [mm] % mw - velikost kernelu pouze 3x3 nebo 5x5
if ((mw == 3)||(mw == 5)||(mw == 7)) podminka = 1; else podminka = 0; disp(’Neplatna velikost kernelu v interpolaci’); end orig_img = img; [a,b,c] = size(img); if(podminka == 1) while(mw>=3) centr = (mw+1)/2; okraj = (mw-1)/2; suma = mw^2-2*mw+3; for it = 1:iterace for i = centr:(a-okraj) for j = centr:(b-okraj) if(orig_img(i,j,2)==0) if(sum(sum(orig_img(i-okraj:i+okraj,j-okraj:j+okraj,2))) >= suma) pocet=0; for u = -okraj:okraj
Pˇr´ılohy
56 for v = -okraj:okraj if (orig_img(i+u,j+v,2)==1) pocet = pocet+1; vec(pocet)= orig_img(i+u,j+v,1); end end end diff = (max(vec)-min(vec)); if(diff< treshold*mw) med = median(vec); img(i,j,1) = med; img(i,j,2) = 1; end end end end end
orig_img = img; end mw = mw-2; orig_img = img; end end return
Prokladani rovin.m function [Theta, Phi, Rho] = prokladani_rovin(rangeim_cist,xyz,index,mw) % PROKLADANI_ROVIN - pro kaˇ zd´ y pixel rastru range image funkce zjiˇ st’uje % parametry norm´ aly roviny, v n´ ıˇ z pixel leˇ z´ ı, prokl´ ad´ an´ ım % roviny v okol´ ı pixelu % % rangeim_cist - range image, nejl´ epe oˇ ciˇ stˇ ena od ˇ sumu (neinterpolov´ ana!!!) % xyz - seznam souˇ radnic, ´ udaje o bod˚ u ve sloupci (x,y,z,1,id) % index - matice o velikosti range image s indexy bod˚ u ze seznamu % souˇ radnic % mw - velikost kernelu definuj´ ıc´ ı okol´ ı, j´ ımˇ z se rovina prokl´ ad´ a % % [Theta] - rastr o velikosti range image s hodnotami parametru theta % (horizont´ aln´ ıho ´ uhlu) proloˇ zen´ ych rovin % [Phi] - rastr o velikosti range image s hodnotami parametru phi % (vertik´ aln´ ıho u ´hlu) proloˇ zen´ ych rovin % [Rho] - rastr o velikosti range image s hodnotami parametru rho % (vzd´ alenosti od poˇ ca ´tku) proloˇ zen´ ych rovin
centr = (mw+1)/2; okraj = (mw-1)/2; [a,b]=size(rangeim_cist(:,:,1)); %% ==== V Y T V O ˇ R E N ´ I M A T I C E M O M E N T U === bod = 0; for i = centr: (a-okraj) for j = centr: (b-okraj) if((rangeim_cist(i,j,2)~=0)&&(index(i,j)~=0)) bod = bod+1; p=0; xp=0; yp=0; zp=0; for ii = -okraj:okraj for jj = -okraj:okraj if(index(i+ii,j+jj)~=0) p = p + 1; seznam(p,1) = xyz(1,index(i+ii,j+jj));
Pˇr´ılohy
57 seznam(p,2) = xyz(2,index(i+ii,j+jj)); seznam(p,3) = xyz(3,index(i+ii,j+jj)); seznam(p,4) = index(i+ii,j+jj); end end end % pr˚ umˇ ery souˇ radnic xp = mean(seznam(:,1)); yp = mean(seznam(:,2)); zp = mean(seznam(:,3)); M = zeros(3); rozdily = 0; % rozd´ ıly souˇ radnic a pr˚ umˇ er˚ u for k = 1:p rozdily(k,1) = seznam(k,1)-xp; rozdily(k,2) = seznam(k,2)-yp; rozdily(k,3) = seznam(k,3)-zp; end M(1,1) M(2,2) M(3,3) M(1,2) M(1,3) M(2,3)
= = = = = =
sum(rozdily(:,1).^2); sum(rozdily(:,2).^2); sum(rozdily(:,3).^2); sum(rozdily(:,1).*rozdily(:,2)); sum(rozdily(:,1).*rozdily(:,3)); sum(rozdily(:,2).*rozdily(:,3));
M(2,1)=M(1,2); M(3,1)=M(1,3); M(3,2)=M(2,3); % singul´ arn´ ı dekompozice [U,S,V] = svd(M);
% koeficienty rovnice roviny a0 = V(1,3); b0 = V(2,3); c0 = V(3,3); d0 = -a0*xp-b0*yp-c0*zp; n = abs(norm([a0,b0,c0])); if (d0>0) a0=-a0; b0=-b0;c0=-c0;d0=-d0; end rovnice(bod,1:4) = [a0,b0,c0,d0]./n; rovnice(bod,5) = index(i,j); end clear seznam; end end
%%
= P ˇ R E V O D
P R A V.
S O U ˇ R.
N O R M ´ A L
N A
S F ´ E R I C K ´ E =
[theta,phi,R]=cart2sph(rovnice(:,1),rovnice(:,2),rovnice(:,3)); Theta = zeros(a,b); Phi = zeros(a,b); Rho = zeros(a,b);
%% == N A P L N ˇ E N ´ I R A S T R ˚ U P A R A M E T R Y for i = 1:a for j = 1:b if (index(i,j)~=0) for l = 1:size(rovnice,1) if(rovnice(l,5)==index(i,j)) Theta(i,j)=abs(theta(l,1)); Phi(i,j)=abs(phi(l,1));
N O R M ´ A L ==
Pˇr´ılohy
58 Rho(i,j)=abs(rovnice(l,4)); break end end
end end end Phi(:,:,2)= rangeim_cist(:,:,2); Theta(:,:,2)= rangeim_cist(:,:,2); Rho(:,:,2) = rangeim_cist(:,:,2);
return
Region growing.m function [rastr_segmenty] = region_growing(Phi, Theta, tresholdP, tresholdT, min_pix)
% REGION_GROWING - funkce proch´ az´ ı rastry Phi a Theta a podle jejich hodnot % pˇ riˇ razuje pixely jednotliv´ ym segment˚ um metodou region growing % (prohled´ av´ an´ ım okol´ ı n´ ahodnˇ e vybran´ ych pixel˚ u % % Phi - rastr s vertik´ aln´ ımi u ´hly norm´ al % Theta - rastr s horizont´ aln´ ımmi ´ uhly norm´ al % tresholdP - mezn´ ı hodnota rozd´ ılu hodnot Phi_pixelu a Phi_segmentu % pro zaˇ razen´ ı pixelu do segmentu % tresholdT - mezn´ ı hodnota rozd´ ılu hodnot Theta_pixelu a Theta_segmentu % pro zaˇ razen´ ı pixelu do segmentu % min_pix - minim´ aln´ ı poˇ cet pixel˚ u pro utvoˇ ren´ ı jednoho segmentu
%%
==== I N I C I A L I Z A C E ====
[a,b]=size(Theta(:,:,1)); rastr_segmenty = zeros(a,b); patri = -1; seg = 1; nepatri = -2; outlier = -3; okoli = 100; % vektor nahodnych pixelu z matice img vec_orig = randperm(a*b);
%% ==== V E K T O R
N ´ A H O D N ´ Y C H
pocet = size(vec_orig,2); pp=0; poradi_vec = zeros(a,b); for h = 1:pocet id = vec_orig(h); col = rem(id,b); if (col==0) col = b; end row = ((id-col)/b)+1;
P I X E L ˚ U
(ROW,COL) ====
% matice poradi pixelu ve vektoru vec
Pˇr´ılohy
59
if((Theta(row,col,2) == 1)) pp = pp+1; vec(pp,1) = vec_orig(h); vec(pp,2) = row; vec(pp,3) = col; poradi_vec(row,col)=pp; end end vec = [vec,zeros(pp,1)]; pocet = pp;
%%
==== P R O H L E D ´ A V ´ A N ´ I
R A S T R ˚ U ====
podminka = 1 while(podminka == 1) podminka = 0; for h = 1:pocet if(vec(h,4)==0) r = vec(h,2); c = vec(h,3); naselse = 1; seedT = Theta(r,c,1); seedP = Phi(r,c,1); sT = seedT; sP = seedP; s = 1; while (naselse ==1) naselse = 0; if ((r>1)&&(r
1)&&(c
end rastr_segmenty(r,c) = seg; vec(poradi_vec(r,c),4) = seg; if(s == okoli) seedT = sT/okoli; seedP = sP/okoli; s = okoli+1; end
if(naselse == 1) r = dalsii; c = dalsij;
Pˇr´ılohy
60 elseif(naselse == 0) for ii = 1:a for jj = 1:b if(rastr_segmenty(ii,jj) == patri) naselse = 1; r = ii; c = jj; break break end end end end % % % %
% animace :-)----------+ figure(2) imagesc(rastr_segmenty); %----------------------+
end s = 0; for i = 1:a for j = 1:b if (rastr_segmenty(i,j) == nepatri) rastr_segmenty(i,j) = 0; elseif (rastr_segmenty(i,j) == seg) s = s+1; end end end
delete = 0; if(s < min_pix) delete = 1; for e = 1:size(vec,1) if(vec(e,4)==seg) vec(e,4) = outlier; rastr_segmenty(vec(e,2),vec(e,3)) = outlier; end end end if (delete ==0) seg =seg+1; end end end for t = 1:pocet if(vec(t,4)==0) podminka = 1; break end end end ˇ E P I S O U T L I A R S %% ==== P R N A for i = 1:a for j = 1:b if(rastr_segmenty(i,j)== outlier) rastr_segmenty(i,j) = 0; end end end return
0 ====
Pˇr´ılohy
61
Segmenty2seznam.m function [xyz_seg,seg_body] = segmenty2seznam(rastr,xyz,index,link) % SEGMENTY2SEZNAM - funkce pˇ rev´ an´ ı ´ udaje o segmentaci z rastru do p˚ uvodn´ ıho % seznamu souˇ radnic % % % % % % % % %
rastr - rastr, v nˇ emˇ z probˇ ehla segmentace xyz - seznam souˇ radnic (matice 5 x poˇ cet bod˚ u) index - matice o velikosti range image s indexy bod˚ u ze seznamu souˇ radnic link - vektor s odkazy na ˇ c´ ısla bod˚ u u bod˚ u, kter´ e byly odstranˇ eny pˇ ri transformaci do range image [xyz_seg] - nov´ y seznam souˇ radnic bod˚ u, jeˇ z byly pˇ riˇ razeny segmentu, ve sloupc´ ıch u ´daje o bodu (x,y,z,ˇ c´ ıslo segmentu) [seg_body] - seznam segment˚ u s poˇ ctem pˇ riˇ razen´ ych bod˚ u
%% == V Y T V O ˇ R E N ´ I
B O D ˚ U
S E Z N A M U
S E
S E G M E N T Y ==
body = size(xyz,2); list = zeros(size(link)); [a,b]=size(rastr(:,:,1)); for i = 1:a for j = 1:b if (index(i,j)~=0) list(index(i,j))= rastr(i,j); end end end m = max(list);
% vkladani cisla segmentu do seznamu
% maximalni pocet segmentu
%% === DOPLNˇ EN´ I BOD˚ U VYˇ RAZEN´ YCH Pˇ RI TVORBˇ E RANGEIMAGE === for i = 1:body if(list(i)==0) if(link(i)~=0) list(i)= list(link(i)); end end end ´ %% === N O V Y S E Z N A M % bez neklasifikovanych bodu
B O D ˚ U ===
poc = 0; for i = 1:body if (list(i)~=0) poc = poc + 1; xyz_seg(poc,1:3)= xyz(1:3,i)’; xyz_seg(poc,4) = list(i); end end
%% = S E G M E N T Y
S
seg_body = zeros(2,m); for k = 1:m p = 0; for i = 1:size(list,2) if(list(i)==k) p = p+1; end
P O ˇ C T E M
P ˇ R I ˇ R A Z E N ´ Y C H
B O D ˚ U =
Pˇr´ılohy
62
end seg_body(1,k)= p; seg_body(2,k)= k; end return
Grad based.m function[Theta, Phi, Rho] = grad_based(rangeim_cist_int,filtr,pixsize,xyz,polar_orig,index) % GRAD BASED - funkce vypoˇ c´ ıt´ a z rastru rangeimage pro kaˇ zd´ y jej´ ı pixel % 3 parametry norm´ aly roviny, v n´ ıˇ z pixel (bod) leˇ zı ´, % na z´ akladˇ e v´ ypoˇ ctu gradientu range image % % % rangeim_cist_int - range image oˇ ciˇ sen´ a od s ˇumu a interpolovan´ a % filtr - "3" - na v´ ypoˇ cet gradientu se pouˇ zije sobel˚ uv filtr 3x3 % "5" - na v´ ypoˇ cet gradientu pouˇ zije se filtr podle B. Gorteho 5x5 % pixsize - velikost pixelu range image (v rad) podle hustoty skenov´ an´ ı % (hodnota pouˇ zita jiˇ z pˇ ri tvorbˇ e range image) % xyz - seznam souˇ radnic, ´ udaje o bod˚ u ve sloupci (x,y,z,1,id) % polar_orig - seznam p˚ uvodn´ ıch sf´ erick´ ych souˇ radnic (lambda, phi, R) % index - matice o velikosti range image s indexy bod˚ u ze seznamu % souˇ radnic % % % [Theta] - rastr o velikosti range image s hodnotami parametru theta % (horizont´ aln´ ıho ´ uhlu) proloˇ zen´ ych rovin % [Phi] - rastr o velikosti range image s hodnotami parametru phi % (vertik´ aln´ ıho u ´hlu) proloˇ zen´ ych rovin % [Rho] - rastr o velikosti range image s hodnotami parametru rho % (vzd´ alenosti od poˇ ca ´tku) proloˇ zen´ ych rovin %%
====
F I L T R Y
====
if(filtr == 3) mv_horiz = [1 0 -1; 2 0 -2; 1 0 -1]; mv_vert = [1 2 1; 0 0 0; -1 -2 -1]; elseif(filtr == 5) mv_horiz = [1 2 0 -2 -1; 2 3 0 -3 -2; 3 4 0 -4 -3; 2 3 0 -3 -2; 1 2 0 -2 -1]; mv_vert = [1 2 3 2 1; 2 3 4 3 2; 0 0 0 0 0; -2 -3 -4 -3 -2; -1 -2 -3 -2 -1]; else disp(’Chybn´ a velikost filtru’) end delitel = sum(sum(abs(mv_horiz)))/2; %% === V ´ Y P O ˇ C E T
G R A D I E N T U
V
O B O U
S M ˇ E R E C H
===
grad_horiz = filter2(mv_horiz,rangeim_cist_int(:,:,1)); grad_horiz(:,:,2) = rangeim_cist_int(:,:,2); grad_vert = filter2(mv_vert,rangeim_cist_int(:,:,1)); grad_vert(:,:,2) = rangeim_cist_int(:,:,2);
%%
====
V ´ Y P O ˇ C E T
N O R M ´ A L
R O V I N
====
dBeta = pixsize;
% = dAlpha [rad]
R =
% [mm]
double(rangeim_cist_int(:,:,1));
dR_vert = double(grad_vert(:,:,1))./delitel; dR_horiz = double(grad_horiz(:,:,1))./delitel;
% [mm]= [DH]/([DH]/[m]) % "
Pˇr´ılohy delta = R.*dBeta;
63 % [mm]
dPhi = atan2(dR_vert,delta); dPhi(:,:,2) = rangeim_cist_int(:,:,2); dTheta = atan2(dR_horiz,delta); dTheta(:,:,2) = rangeim_cist_int(:,:,2);
% [rad] % [1,0] % [rad] % [1,0]
[a, b, c] = size(dPhi);
% = size(dTheta1)
%%
rastry ´ uhl˚ u Phi a Theta norm´ al rovin
Phi = zeros(a,b,2); Theta = Phi; for i = 1:a for j = 1:b if((dPhi(i,j,2)==1)&&(index(i,j)~= 0)) Phi(i,j,1) = abs(polar_orig(2,index(i,j))-dPhi(i,j,1)); Theta(i,j,1) = polar_orig(1,index(i,j))-dTheta(i,j,1); if(Theta(i,j,1)<0) Theta(i,j,1)=Theta(i,j,1)+pi; end Phi(i,j,2) = 1; Theta(i,j,2) = 1; end end end
%%
rastr vzd´ alenost´ ı Rho norm´ al rovin
Rho = zeros(a,b,2); for i = 1:a for j = 1:b if (Theta(i,j,2)==1) Rho(i,j,1) = abs(xyz(1,index(i,j))*cos(Theta(i,j,1))*cos(Phi(i,j,1)) + ... xyz(2,index(i,j))*sin(Theta(i,j,1))*cos(Phi(i,j,1)) + ... xyz(3,index(i,j))*sin(Phi(i,j,1))); Rho(i,j,2) = 1; end end end
return
RNS.m function [vMask, Model] = RNS( mData, ModelFunc, nSampLen, ResidFunc, nIter, dThreshold ) % % % % % % % % % % % %
RNS - funkce zjiˇ st’uje parametry matematick´ eho modelu namˇ eˇ ren´ ych dat pomoc´ ı algoritmu RANSAC mData - namˇ eˇ ren´ a data, souˇ radnice xyz 1 ModelFunc - odkaz na funkci, pomoc´ ı n´ ıˇ z nSampLen - minim´ aln´ ı poˇ cet bod˚ u nutn´ ych ResidFunc - odkaz na funkci, jeˇ z poˇ c´ ıt´ a nIter - poˇ cet iterac´ ı algoritmu RANSAC dThreshold - mezn´ ı hodnota odchylky pro
bodu odpov´ ıd´ a 1 sloupci matice se spoˇ cı ´t´ a matematick´ y model k v´ ypoˇ ctu modelu odchylky bod˚ u od modelu stanoven´ ı outliars
[vMask] - vektor oznaˇ cuj´ ıc´ ı inliers (1) a outliars (0) [Model] - parametry modelu
if length(size(mData)) ~=2 error(’Data must be organized in column-vecotors massive’); end
Pˇr´ılohy
64
nDataLen = size(mData, 2); Model = NaN; vMask = zeros([1 nDataLen]); nMaxInlyerCount = -1;
for i = 1:nIter % 1. Sampling SampleMask = zeros([1 nDataLen]); % Takes nSampleLen different points while sum( SampleMask ) ~= nSampLen ind = ceil(nDataLen .* rand(1, nSampLen - sum(SampleMask))); SampleMask(ind) = 1; end Sample = find( SampleMask );
% 2. Creating model ModelSet = feval(ModelFunc, mData(:, Sample)); for iModel = 1:size(ModelSet, 3) CurModel = ModelSet(:, :, iModel); % 3. Model estimation CurMask = ( abs( feval(ResidFunc, CurModel, mData)) < dThreshold ); nCurInlyerCount = sum(CurMask); % 4. The best is selected if nCurInlyerCount > nMaxInlyerCount % Save some parameters nMaxInlyerCount = nCurInlyerCount; vMask = CurMask; end end end vSample = find(vMask); Model = feval(ModelFunc, mData(:, vSample)); return;
Model rovina.m function plane = model_rovina(data) % % % % % %
MODEL_ROVINA - funkce prokl´ ad´ a vstupn´ ımi daty rovinu metodou nejmenˇ sı ´ch ˇ ctverc˚ u data - vstupn´ ı data, 1 bod odpov´ ıd´ a 1 sloupci [plane] - parametry roviny if any( size(data) == 0) plane = [0, 0, 0, 0]; return; end X = data(1, :); Y = data(2, :); Z = data(3, :); pocet = size(X,2);
Pˇr´ılohy
65
% prumer xp yp zp
souradnic = mean(X); = mean(Y); = mean(Z);
% rozdlily souradnic a prumeru diffX = X-xp; diffY = Y-yp; diffZ = Z-zp; % matice momentu M = zeros(3); M(1,1) M(2,2) M(3,3) M(1,2) M(1,3) M(2,3)
= = = = = =
sum(diffX.^2); sum(diffY.^2); sum(diffZ.^2); sum(diffX.*diffY); sum(diffX.*diffZ); sum(diffY.*diffZ);
M(2,1)=M(1,2); M(3,1)=M(1,3); M(3,2)=M(2,3); % singularni dekompozice [U,S,V] = svd(M); a0 = V(1,3); b0 = V(2,3); c0 = V(3,3); d0 = -a0*xp-b0*yp-c0*zp; n = abs(norm([a0,b0,c0])); if (d0>0) a0=-a0; b0=-b0;c0=-c0;d0=-d0; end plane = [a0,b0,c0,d0]./n;
% koeficienty rovnice roviny
return
Vzdalenost.m function D = vzdalenost(plane,data) % VZD´ ALENOST - funkce poˇ cı ´t´ a vzd´ alenosti bod˚ u od modelu roviny D = abs(plane * [data; ones([1 size(data, 2)])]); return
SegmentaceRNS.m %%
====
INICIALIZACE
====
xyz = (load(’okno.xyz’))’; shum = 0.05; % ˇ sum /.100 procent data = xyz; data_orig = data; s = size(data,2); data(4,:) = 1:s; % indexy seg = 0; limit = s*shum; C = zeros(1,s);
Pˇr´ılohy
%%
====
66
P O S T U P N ´ E
P R O K L ´ A D ´ A N ´ I
R O V I N ====
while (s>limit) seg = seg+1; [in_out, model] = RNS(data(1:3,:),@model_rovina,3,@vzdalenost,200,0.01); for i = 1:s C(data(4,i)) = C(data(4,i)) + seg*uint8(in_out(i)); end data_new = zeros(4,sum(in_out)); p = 0; for i = 1:s if (in_out(i)== 0) p = p+1; data_new(:,p) = data(:,i); end end data = data_new; s = p; end figure(2) scatter3(data_orig(1,:),data_orig(2,:),data_orig(3,:),0.3,C,’filled’); xlabel(’X’);ylabel(’Y’);zlabel(’Z’); grid on view(-80,6);
SegmentaceI.m %%
=== S E G M E N T A C E
%%
i n p u t
I ===
seznam_souradnic = load(’okno.xyz’); %% == R A N G E I M A G E == [xyz,rangeimage,index,link,Rmin] = range_image(seznam_souradnic,0.00035);
%%
== ˇ C I ˇ S T ˇ E N ´ I ==
rangeim_cist = cisteni(rangeimage,9,500);
%%
v i z u a l i z a c e
rangeim_cist_fig = rangeim_cist(:,:,1)-1000*Rmin.*rangeim_cist(:,:,2); figure(2); colormap(’jet2’); axis equal; imagesc(rangeim_cist_fig); title(’Range image pˇ red interpolac´ ı’);
%%
==
P R O K L ´ A D ´ A N ´ I
R O V I N A M I ==
kernel = 5; % velikost kernelu, j´ ımˇ z bude rovina proloˇ zena [Theta, Phi, Rho] = prokladani_rovin(rangeim_cist,xyz,index,kernel);
%%
v i z u a l i z a c e
Pˇr´ılohy
67
figure(3) subplot(1,3,1) colormap(’jet’); imagesc(Theta(:,:,1)) title(’Theta norm´ alov´ ych vektor˚ u rovin’); subplot(1,3,2) colormap(’jet2’); imagesc(Phi(:,:,1)) title(’Phi norm´ alov´ ych vektor˚ u rovin’); subplot(1,3,3) colormap(’jet2’); imagesc(Rho(:,:,1)) title(’vzd´ alenost rovin od poˇ c´ atku’);
%%
== S E G M E N T A C E
-
R E G I O N
G R O W I N G ==
min_size = 300; % minim´ aln´ ı poˇ cet pixel˚ u pro vytvoˇ ren´ ı jednoho segmentu tresholdP = 0.25; tresholdT = 0.25; segmentace = region_growing(Phi,Theta,tresholdP,tresholdT,min_size); %% = S E Z N A M
S O U ˇ R A D N I C
S E G M E N T O V A N ´ Y C H
B O D ˚ U =
[novy_ss,prirazeni] = segmenty2seznam(segmentace,xyz,index,link);
%% v i z u a l i z a c e map = colorcube(max(max(segmentace))); map(1,:)=1; map(end,:)= 0.92; figure(4) imagesc(segmentace) colormap(map) figure(5) scatter3(novy_ss(:,1),novy_ss(:,2),novy_ss(:,3),0.5,novy_ss(:,4),’filled’); colormap(’jet’); grid on view(-80,6);
SegmentaceII.m %% %%
=== S E G M E N T A C E
II ===
i n p u t
seznam_souradnic = load(’okno.xyz’); %% == R A N G E I M A G E == rozliseni = 0.00035; [xyz,rangeimage,index,link,Rmin,polar_orig] = range_image(seznam_souradnic,rozliseni);
%%
== ˇ C I ˇ S T ˇ E N ´ I ==
rangeim_cist = cisteni(rangeimage,9,500);
%%
== I N T E R P O L A C E ==
rangeim_cist_int = interpolace(rangeim_cist,300,4,3);
%%
v i z u a l i z a c e
Pˇr´ılohy
68
rangeim_cist_fig = rangeim_cist(:,:,1)-1000*Rmin(1,3).*rangeim_cist(:,:,2); rangeim_cist_int_fig = (rangeim_cist_int(:,:,1)-1000*Rmin(1,3).*rangeim_cist_int(:,:,2)); figure(2); colormap(’jet2’); axis equal; subplot(1,2,1) imagesc(rangeim_cist_fig); title(’Range image pˇ red interpolac´ ı’); subplot(1,2,2) imagesc(rangeim_cist_int_fig); title(’Range image po interpolaci’);
%%
==
N O R M ´ A L Y
P O M O C ´ I
G R A D I E N T U
==
filtr = 5; % velikost kernelu, j´ ımˇ z bude rovina proloˇ zena [Theta, Phi, Rho] = grad_based(rangeim_cist_int,filtr,rozliseni,xyz,polar_orig,index);
%%
v i z u a l i z a c e
figure(3) subplot(1,3,1) colormap(’jet2’); imagesc(Theta(:,:,1)) title(’Theta norm´ alov´ ych vektor˚ u rovin’); subplot(1,3,2) colormap(’jet2’); imagesc(Phi(:,:,1)) title(’Phi norm´ alov´ ych vektor˚ u rovin’); subplot(1,3,3) colormap(’jet2’); imagesc(Rho(:,:,1)) title(’vzd´ alenost rovin od poˇ c´ atku’);
figure(3) subplot(1,3,1) colormap(’jet2’); imagesc(Theta(:,:,1)) title(’Theta norm´ alov´ ych vektor˚ u rovin’); subplot(1,3,2) colormap(’jet2’); imagesc(Phi(:,:,1)) title(’Phi norm´ alov´ ych vektor˚ u rovin’); subplot(1,3,3) colormap(’jet2’); imagesc(Rho(:,:,1)) title(’vzd´ alenost rovin od poˇ c´ atku’); %%
== S E G M E N T A C E
-
R E G I O N
G R O W I N G ==
min_size = 300; % minim´ aln´ ı poˇ cet pixel˚ u pro vytvoˇ ren´ ı jednoho segmentu tresholdP = 0.5; tresholdT = 0.5; segmentace = region_growing(Phi,Theta,tresholdP,tresholdT,min_size); %% = S E Z N A M
S O U ˇ R A D N I C
S E G M E N T O V A N ´ Y C H
[novy_ss,prirazeni] = segmenty2seznam(segmentace,xyz,index,link);
%% v i z u a l i z a c e map = colorcube(max(max(segmentace)));
B O D ˚ U =
Pˇr´ılohy map(1,:)=1; map(end,:)= 0.92; figure(4) imagesc(segmentace) colormap(map) figure(5) scatter3(novy_ss(:,1),novy_ss(:,2),novy_ss(:,3),0.5,novy_ss(:,4),’filled’); colormap(’jet’); grid on view(-80,6);
69
Pˇr´ılohy
70
Obr´ azov´ aˇ c´ ast
Obr´azek 6.1: Testovan´e mraˇcno bod˚ u.
Pˇr´ılohy
71
Obr´azek 6.2: Rastr range image.
Pˇr´ılohy
72
Obr´azek 6.3: Rastr range image po ˇciˇstˇen´ı a interpolaci.
Pˇr´ılohy
73
Obr´azek 6.4: Mraˇcno bod˚ u segmentovan´e postupem Segmentace I.
Pˇr´ılohy
74
Obr´azek 6.5: Mraˇcno bod˚ u segmentovan´e postupem Segmentace II.
Pˇr´ılohy
Obr´azek 6.6: Mraˇcno bod˚ u segmentovan´e postupem SegmentaceRNS.
75
Pˇr´ılohy
76
Obr´azek 6.7: Mraˇcno bod˚ u segmentovan´e pomoc´ı n´astroje automatick´e segmentace v programu Geomagic Studio 10.