Fakulta stavební Kateřina Turková

ˇ ´ 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á. Pr˚ uzkum souˇcasného stavu v automatizaci vyhodnocen´ı mraˇcen ˇ e vysoké uˇcen´ı techbod˚ u z pozemn´ıho prostorového skenován´ı budov. Praha: Cesk´ nické v Praze. Fakulta Stavebn´ı. Katedra speciáln´ı geodézie, 2010. Diplomová práce, poˇcet stran 51 s., poˇcet stran pˇr´ıloh 25 s. Vedouc´ı diplomové práce byl Ing. Bronislav Koska, Ph.D.

´ SEN ˇ Í PROHLA Prohlaˇsuji, ˇze jsem svou diplomovou práci na téma Pr˚ uzkum souˇcasného stavu v automatizaci vyhodnocen´ı mraˇcen bod˚ u z pozemn´ıho prostorového skenován´ı budov vypracovala samostatnˇe s vyuˇzit´ım konzultac´ı u vedouc´ıho diplomové práce a pouˇzit´ım odborné 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áda podˇekovala vedouc´ımu své diplomové práce, panu Ing. Bronislavu Koskovi, Ph.D. za odborné veden´ı a pomoc v pr˚ ubˇehu zpracován´ı a panu ˇ Ing. Janu Rezn´ ıˇckovi za poskytnut´ı vlastn´ıch skript˚ u a za dobré rady pro práci s programem Matlab. Podˇekován´ı patˇr´ı také mé rodinˇe a bl´ızk´ ym za podporu ve studiu.

Abstrakt Diplomová práce se zab´ yvá problematikou vyhodnocován´ı prostorov´ ych dat z´ıskan´ ych metodou laserového skenován´ı. Zamˇeˇrena je konkrétnˇe na ˇcást zpracován´ı, a to segmentaci. V souˇcasné dobˇe je snaha maximálˇe automatizovat zpracován´ı namˇeˇren´ ych dat, zejména fázi segmentace a následnou klasifikaci. Nejprve je struˇcnˇe popsán princip metody laserového skenován´ı. Následuje pˇredstaven´ı r˚ uzn´ ych moˇznost´ı a postup˚ u automatické segmentace. Praktická ˇcást se vˇenuje za prvé tvorbˇe a pouˇzit´ı vlastn´ıch skript˚ u na segmentaci mraˇcna bod˚ u a zadruhé procesu segmentace v komerˇcn´ım softwaru Geomagic Studio 10.

Kl´ıˇ cov´ a slova Vyhodnocen´ı mraˇcna bod˚ u Segmentace fasády 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ého skenován´ı . . . . . . . . . . . . . . . . . . . . . . .

6

2.2

Zpracován´ı dat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3 Segmentace

9

3.1

Pattern based method - shluková anal´ yza . . . . . . . . . . . . . . . . 11

3.2

Detekce hran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.3

Proximity graph based segmentation . . . . . . . . . . . . . . . . . . 12

3.4

Region growing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.5

Prot´ınán´ı profil˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.6

Segmentace podle parametr˚ u roviny na základˇ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ál rovin pro kaˇzd´ y pixel (bod) . . . . 25

4.1.3

Pˇriˇrazen´ı pixel˚ u k plochám podle jejich parametr˚ u . . . . . . . 29

4.1.4

Porovnán´ı 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á ˇca´st . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Seznam obrázk˚ u

3

Seznam obr´ azk˚ u 3.1

Sobel˚ uv filtr (operátor): vlevo pro detekci svisl´ ych hran, vpravo pro detekci vodorovn´ ych hran. . . . . . . . . . . . . . . . . . . . . . . . . 12

3.2

Aplikace Sobelova oparátoru: P˚ uvodn´ı obrázek (vlevo), detekce horizontáln´ıch hran (uprostˇred), detekce vertikáln´ıch hran (vpravo). . . . 12

3.3

Proximity graph based segmentation. . . . . . . . . . . . . . . . . . . 13

3.4

Segmentace v profilech pomoc´ı Delaunayovy triangulace (vlevo) a na základˇe prokládán´ı kˇrivkou (vpravo). . . . . . . . . . . . . . . . . 15

3.5

Pˇr´ıklad segmentace dvou rovnobˇeˇzn´ ych rovin pomoc´ı prot´ınán´ı 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é mraˇcno. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.2

Range image celé fasády. . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.3

Pˇrevod bodu P do rastru range image. . . . . . . . . . . . . . . . . . 21

4.4

V´ yˇrez z range image fasády p˚ uvodn´ı a po odstranˇen´ı ˇsumu. . . . . . . 23

4.5

V´ yˇrez z range image fasády 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ány v radianech, hodnoty rastru Rho v metrech. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.7

V´ ypoˇcet rozd´ılového u ´hlu ∆φ z gradientu z´ıskaného 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é metodou podle Bena Gorteho. Hodnoty u ´hl˚ u prvn´ıch dvou rastr˚ u jsou udány v radianech, hodnoty rastru Rho v metrech. . . . . . . . . . . 30

Seznam obrázk˚ u

4

4.10 Rozr˚ ustán´ı homogenn´ıch oblast´ı v algoritmu region growing. . . . . . 31 4.11 Vizualizace seznamu segmentovan´ ych souˇradnic; barvy náleˇ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é algoritmem RANSAC; barvy náleˇz´ı ˇc´ısl˚ um segment˚ u. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.1

Namˇeˇrená data naˇctená do programu Geomagic Studio 10. . . . . . . 38

5.2

Posuny bod˚ u pˇri aplikaci filtru Reduce noice, udáno 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é segmentace (vlevo) a jeho ruˇcn´ı editace (vpravo). 43

5.7

Pouˇzit´ı funkce Remove islands.

5.8

Vygenerován´ı kˇrivek z oblast´ı separátor˚ 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áno v metrech. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.11 CADovsk´ y model generovan´ y ve Fashion Phase (vlevo) a v Shape Phase (vpravo). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.1

Testované 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é postupem Segmentace I. . . . . . . . . . 73

6.5

Mraˇcno bod˚ u segmentované postupem Segmentace II. . . . . . . . . . 74

6.6

Mraˇcno bod˚ u segmentované postupem SegmentaceRNS. . . . . . . . . 75

6.7

Mraˇcno bod˚ u segmentované pomoc´ı nástroje automatické 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é skenován´ı (LS). Vyv´ıj´ı se terpve v 90. letech 20. stolet´ı a postupnˇe se ve svˇetˇe stává v´ıce obl´ıben´ ym a vyuˇz´ıvan´ ym. Velkou pˇrednost´ı LS je mnohonásobnˇe rychlejˇs´ı z´ıskáván´ı dat v terénu, neˇz jak´ ymikoli jin´ ymi metodami. Také 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án´ı je ale naopak slabinou laserového skenován´ı. Neobejde se bez pomoci vysoce v´ ykonné v´ ypoˇcetn´ı techniky a i tak je velmi problematické a ˇcasovˇe nesm´ırnˇe nároˇcné. Na jeho automatizaci se stále pracuje. Tato práce se zab´ yvá asi nejv´ıce komplikovanou ˇca´st´ı zpracován´ı namˇeˇren´ ych dat ˇ e republice se doposud problemaLS (tzv. mraˇcna bod˚ u), a to segmentac´ı. V Cesk´ tice automatické segmentace mraˇcen bod˚ u z pozemn´ıho laserového skenován´ı nikdo c´ılenˇe nevˇenoval, a nelze tak naj´ıt jedinou ˇcesky psanou literaturu. Publikace, z nichˇz bylo pro tuto práci ˇcerpáno, byly vˇetˇsinou vˇedecké ˇclánky, vydané na zahraniˇcn´ıch univerzitách, pˇredevˇs´ım v Nizozem´ı a Nˇemecku. V souˇcasné dobˇe existuje jen nˇekolik program˚ u pro zpracován´ı dat LS, jeˇz obsahuj´ı nástroje pro segmentaci mraˇcen bod˚ u. V kapitole 2 Laserové skenován´ı je tato metoda pˇredstavena, struˇcnˇe je popsán jej´ı princip a postup pˇri zpracován´ı. Kapitola 3 Segmentace popisuje r˚ uzné pˇr´ıstupy této ˇca´sti zpracován´ı dat laserového skenován´ı. Praktická ˇca´st diplomové práce (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ády budovy Arcibiskupského semináˇre v Praze 6, Dejvic´ıch. Po pouˇzit´ı vlastn´ıho skriptu byla segmentace mraˇcna provedena také v komerˇcn´ım softwaru Geomagic Studio 10. V´ ysledky vˇsech pouˇzit´ ych metod segmentace byly na závˇer porovnány.

2. Laserové skenován´ı

6

2 Laserov´ e skenov´ an´ı 2.1

Princip laserov´ eho skenov´ an´ı

Laserové skenován´ı spoˇc´ıvá v neselektivn´ı urˇcován´ı souˇradnic bod˚ u na povrchu objekt˚ u. Podle typu nosiˇce rozliˇsujeme letecké laserové skenován´ı (Airborne laser scanning) a pozemn´ı laserové skenován´ı (Terrestrial laser scanning). Letecké laserové skenován´ı se vyuˇz´ıvá napˇr´ıklad pro vytvoˇren´ı digitáln´ıho modelu terénu (DTM), digitáln´ıho modelu reliéfu (DSM), zjiˇst’ován´ı pr˚ ubˇehu veden´ı nadzemn´ıch inˇzen´ yrsk´ ych s´ıt´ı, digitáln´ıch model˚ u mˇest, zjiˇst’ován´ı v´ yˇsky vegetace atd. Do jisté m´ıry j´ım lze nahradit fotogrammetrii a dálkov´ 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án´ı a zpracován´ı mˇeˇren´ı. Pozemn´ı skenován´ı slouˇz´ı k tvorbˇe model˚ u stavebn´ıch konstrukc´ı a budov (interiéru a exteriéru), zamˇeˇrován´ı podzemn´ıch prostor˚ u (tunely, jeskynˇe) atd. Pˇri vˇsech tˇechto ˇcinnostech je v´ yhodou velké rozliˇsen´ı metody LS a rychlost sbˇeru znaˇcného objemu dat. Sbˇer dat se prován´ı pomoc´ı laserového skeneru, ˇr´ızeného nejˇcastˇeji pˇrenosn´ ym poˇc´ıtaˇcem, v nˇemˇz zadáváme parametry mˇeˇren´ı, jako napˇr. u ´hel skenován´ı vymezuj´ıc´ı zájmovou oblast, rozliˇsen´ı skenován´ı a pod. K následnému zpracován´ı a zobrazen´ı dat (mraˇcna bod˚ u) se vyuˇz´ıvá kompatibiln´ı software. Celé zaˇr´ızen´ı potˇrebné k provozu této metody se naz´ yvá laserov´ y skenovac´ı systém (LSS). Souˇradnice bod˚ u mraˇcna jsou urˇcovány bud’ polárn´ı metodou - mˇeˇren´ım vertikáln´ıho a horizontáln´ıho u ´hlu a ˇsikmé vzdálenosti (polárn´ı skenery) nebo prot´ınán´ım z u ´hl˚ u ze známé základny (skenery se základnou).

Zpracován´ı dat

2.2

7

Zpracov´ an´ı dat

Zpracován´ı namˇeˇren´ ych dat je tou problematiˇctˇejˇs´ı ˇcást´ı metody laserového skenován´ı. Provád´ı se ˇcasto poloautomaticky pomoc´ı speciáln´ıch softwar˚ u, avˇsak i zpracován´ı mˇeˇren´ı menˇs´ıho rozsahu m˚ uˇze zabrat mnohonásobnˇe v´ıce ˇcasu, neˇz samotné mˇeˇren´ı v terénu. Zpracován´ı lze rozdˇelit na nˇekolik ˇca´st´ı: ˇ 1. Registrace mraˇ cen bod˚ u – Casto se provád´ı mˇeˇren´ı z v´ıce neˇz jednoho stanoviska. Mraˇcna bod˚ u ze vˇsech stanovisek se registrac´ı transformuj´ı do spoleˇcné souˇradnicové soustavy. Za poˇcátek se vol´ı jedno ze stanovisek. Transformace z m´ıstn´ıho souˇradnicového systému do nˇekterého ze závazn´ ych národn´ıch systém˚ u se vˇetˇsinou neprovád´ı. 2. Odstranˇ en´ı ˇ sumu, filtrace – Z mraˇcna se v grafickém rozhran´ı ruˇcnˇe nebo automaticky odstran´ı shluky bod˚ u, které nenáleˇz´ı objektu zájmu (naskenované okoln´ı objekty, vegetace, kolemjdouc´ı chodci, auta), dále se pouˇz´ıvaj´ı filtry na zˇredˇen´ı mraˇcna bod˚ u v rovinn´ ych ˇca´stech objekt˚ u. To je v´ yhodné zvláˇstˇe pˇri generován´ı troj´ uheln´ıkové s´ıtˇe, pˇredstavuj´ıc´ı povrch objektu. 3. Segmentace – Spoˇc´ıvá v rozdˇelen´ı mraˇcna na homogenn´ı oblasti - segmenty, jeˇz odpov´ıdaj´ı jednomu objektu ˇci jeho ˇcásti. Kaˇzd´ ym t´ımto segmentem se dá proloˇzit geometrické primitivum, nejˇcastˇeji rovina. 4. Klasifikace – Tato fáze 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ého 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án´ım se nejˇcastˇeji z´ıská model skenovaného objektu. Pˇri vytváˇren´ı DTM u leteckého skenován´ı, ˇci u pozemn´ıho skenován´ı objekt˚ u, jeˇz nelze rozloˇzit na geometrická primitiva (sochy ap.) se vytvoˇr´ı 3D model pomoc´ı troj´ uheln´ıkové s´ıtˇe.

Zpracován´ı dat

8

Nepracnˇejˇs´ımi a nejzdlouhavˇejˇs´ımi fázemi celého procesu jsou segmentace a následná klasifikace. Proto je snaha tyto ˇcásti zpracován´ı plnˇe automatizovat a zkrátit tak dobu vyhodnocen´ı na minimum. Tato práce se vˇenuje pˇredevˇs´ım zp˚ usob˚ um a moˇznostem segmentace mraˇcen bod˚ u, at’ uˇz z leteckého, ˇci pozemn´ıho laserového skenován´ı. Praktická ˇca´st je vzhledem k dostupnosti poˇzadovaného softwaru zamˇeˇrena pouze na segmentaci mraˇcna bod˚ u pozemn´ıho skenován´ı.

3. Segmentace

9

3 Segmentace Tento krok ve vyhodnocován´ı dat laserového skenován´ı slouˇz´ı k rozpoznán´ı homogenn´ıch oblast´ı v mraˇcnu bod˚ u. Oddˇelené oblasti - segmenty - mohou b´ yt dále podle známého obsahu mraˇcna a podle parametr˚ u, jako je napˇr´ıklad jejich velikost, tvar a poloha v mraˇcnu, klasifikovány na jednotlivé objekty a ˇca´sti objekt˚ u. Ruˇcn´ı segmentace spoˇc´ıvá v oˇrezán´ı mraˇcna, postupném v´ ybˇeru ˇcást´ı, jejich oznaˇcen´ı za homogenn´ı oblast a proloˇzen´ı nˇejak´ ym geometrick´ ym primitivem. Nejˇcastˇeji b´ yvá t´ımto primitivem rovina. M˚ uˇze to b´ yt také válcová plocha, koule (nezbytná pˇri pouˇzit´ı kulov´ ych terˇc˚ u jako vl´ıcovac´ıch bod˚ u) a i jiné sloˇzité, pˇredem nadefinované plochy a tvary, které nab´ız´ı pouˇz´ıvan´ y software (ˇca´sti potrub´ı apod.). V pˇr´ıpadˇe, ˇze v´ ysledkem má b´ yt 3D model nˇejakého objektu, je nezbytné z mraˇcna bod˚ u z´ıskat d˚ uleˇzité hrany objektu, eventuálnˇe jejich pr˚ useˇc´ıky, a provést jejich export do souboru, kter´ y lze v jiném grafickém programu dále zpracovat. Hrany drátového modelu z´ıskáme v´ ypoˇctem pr˚ useˇcnic proloˇzen´ ych geometrick´ ych primitiv. Ruˇcn´ı segmentace je tedy velmi pracná a zdlouhavá, a to i pˇri pouˇzit´ı v´ ykonné v´ ypoˇcetn´ı techniky. Pouze nˇekolik softwar˚ u pro zpracován´ı dat LS obsahuje nástroje pro segmentaci mraˇcen bod˚ u. Nejˇcastˇeji funguj´ı na základˇe vytvoˇren´ı troj´ uhelkové s´ıtˇe a sledován´ı a porovnáván´ı jednotliv´ ych hran mezi troj´ uheln´ıky. V automatické segmentaci vˇsak existuje pomˇernˇe mnoho r˚ uzn´ ych algoritm˚ u. Pouˇzit´ı závis´ı na typu dat, která se maj´ı segmentovat.

Over-segmentation a under-segmentation V ideáln´ım pˇr´ıpadˇe by byl v´ ysledkem procesu segmentace stav, kdy jeden segment odpov´ıdá jednomu objektu ˇci jedné jeho ˇca´sti. Pˇri segmentaci málokdy doc´ıl´ıme pˇresného rozpoznán´ı 1 objekt = 1 segment. Rozliˇsujeme tedy dva pˇr´ıpady segmentace:

3. Segmentace

10

over-segmentation - Jednomu objetu (popˇr. ˇcásti objektu) je pˇriˇrazeno v´ıce segment˚ u. Ty se dále mus´ı spojit do jednoho segmentu, kter´ y bude pˇredstavovat objekt/ˇca´st objektu. under-segmentation - V´ıce objekt˚ u je znázornˇeno jako jeden segment. V tomto pˇr´ıpadˇe nelze rozeznat jednotlivé 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éri´ı: • podle typu laserov´ ych dat : leteck´ e LS – Pˇredevˇs´ım tvorba DTM; vyuˇz´ıvá v´ıce zpracován´ı troj´ uheln´ıkovou s´ıt´ı. pozemn´ı LS – Zamˇeˇrován´ı fasád, podzemn´ıch prostor; pouˇz´ıvá pˇreváˇznˇe prokládán´ı 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ázej´ı 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áván´ım hran troj´ uheln´ık˚ u, ˇcili vzdálenost´ı mezi jednotliv´ ymi body, se posuzuje homogenita oblasti. Dalˇs´ı moˇznost´ı m˚ uˇze b´ yt prokládán´ı primitiv algoritmem RANSAC. 2.5D prostor – Pracuje se pouze s daty namˇeˇren´ ymi z jednoho stanoviska. Prostorové mraˇcno bod˚ u se pˇrevád´ı do 2D obrazu, pˇriˇcemˇz informace o tˇret´ım rozmˇeru je obsaˇzena v hodnotˇe pixelu. Zpracován´ı tohoto rastru, tzv. range image, se velmi podobá zpracován´ı obrazov´ ych dat, jak ho známe z obor˚ u dálkového pr˚ uzkumu Zemˇe a fotogrammetrie. 2D prostor – Zpracován´ı 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á anal´ yza

11

profil se vyhodnot´ı zváˇst’ - pomoc´ı troj´ uheln´ıkové s´ıtˇe, aproximac´ı kˇrivkami ˇci prostorov´ ymi filtry [1]. • podle zp˚ usobu vytv´ aˇ ren´ı homogenn´ıch oblast´ı : region growing – Zaloˇzené na náhodném vybrán´ı základn´ıho bodu oblasti (seed) a jej´ım postupném nar˚ ustán´ı v okol´ı tohoto bodu podle stanoven´ ych podm´ınek. region merging – Spoˇc´ıvá ve spojován´ı menˇs´ıch homogenn´ıch oblast´ı ve vˇetˇs´ı na základˇ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é veliˇciny namˇeˇrené v r˚ uzn´ ych pásmech, je nyn´ı aplikovaná 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ály roviny, v n´ıˇz bod leˇz´ı a odrazivost. Roviny se prokládáj´ı vˇzdy nˇekolika body v okol´ı urˇcovaného 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áˇseny do n-rozmˇerného prostoru (feature space), kde vytváˇrej´ı shluky (clusters). Body jednoho shluku tvoˇr´ı jeden segment. Vymezen´ı pˇr´ıznakového prostoru se provád´ı 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á mez nejsou oznaˇceny za samostatn´ y segment, ale vymazány, nebo pˇriˇrazeny k jinému shluku. Segmenty náleˇzej´ıc´ı jednomu objektu/ˇcásti objektu jsou spojeny v jeden. Existuje nˇekolik algoritm˚ u (Jain and Hoffman, 1987; Filin, 2002) otestovan´ ych pro letecké laserové skenován´ı. Tato metoda se vˇsak pouˇz´ıvá pˇredevˇs´ım pro segmentaci dat pozemn´ıho laserového skenován´ı, kdy se vyuˇz´ıvá právˇ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á o postupy zpracován´ı obrazov´ ych dat. Mraˇcno se pˇrevád´ı na 2.5D rastr a ten je analyzován pomoc´ı filtr˚ u. Pˇri segmentaci pomoc´ı detekce hran vycház´ıme z pˇredpokladu, ˇze kaˇzd´ y segment je pevnˇe ohraniˇcen a body spadaj´ıc´ı do uzavˇreného sledu hran náleˇz´ı jednomu segmentu. Pˇri zobrazen´ı mraˇcna do rastru lze hrany a segmenty vizuálnˇe rozeznat. Hrana je na obraze m´ıstem, kde se skokem mˇen´ı hodnoty radiometrick´ ych veliˇcin,

Obrázek

3.1:

Sobel˚ uv

filtr

(operátor): vlevo pro detekci svisl´ ych hran, vpravo pro detekci vodorovn´ ych hran.

pˇredstavuj´ıc´ıch napˇr´ıklad v´ yˇsku terénu u leteckého skenován´ı nebo vzdálenost od skeneru u pozemn´ıho skenován´ı. Pomoc´ı klasick´ ych filtr˚ u (Sobel˚ uv operátor, Roberts˚ uv operátor, Prewit˚ uv) se daj´ı detekovat zmˇeny v digitáln´ıch hodnotách pixel˚ u jak v horizontáln´ım tak vertikáln´ım smˇeru. Cannyho algoritmus detekce hran nav´ıc pouˇz´ıvá filtr detekuj´ıc´ı hrany v diagonáln´ım smˇeru.

Obrázek 3.2: Aplikace Sobelova oparátoru: P˚ uvodn´ı obrázek (vlevo), detekce horizontáln´ıch hran (uprostˇred), detekce vertikáln´ıch hran (vpravo).

3.3

Proximity graph based segmentation

Tato metoda pracuj´ıc´ı ve 3D prostoru je zaloˇzena na mˇeˇren´ı vzdálenost´ı mezi bl´ızk´ ymi body a pˇredpokládá, ˇze sousedn´ı body náleˇzej´ıc´ı jednomu segmentu maj´ı

Region growing

13

mezi sebou menˇs´ı Euklidovskou délku neˇz body náleˇ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áván´ım. Bl´ızké body v mraˇcnu se pospojuj´ı a vznikne tak graf, jemuˇz hledáme minimáln´ı kostru. Vahami v tomto grafu jsou Euklidovské vzdálenosti mezi body. Po nalezen´ı minimáln´ı kostry grafu - stromu (spanning tree), porovnáváme velikosti hran mezi body (vrcholy grafu). Hrany, jejichˇz váha pˇrevyˇsuje stanovenou mez, se odstran´ı. Podle parametr˚ u skenován´ı lze odhadnout vzdálenosti sousedn´ıch bod˚ u náleˇz´ıc´ıch jedné homogenn´ı oblasti a nastavit tak tuto mezn´ı vzdálenost. V´ ysledkem je skupina spojit´ ych graf˚ u, z nichˇz kaˇzd´ y pˇredstavuje jeden segment. Algoritmus byl navrˇzen pro zpracován´ı leteck´ ych dat, lze jej vˇsak pouˇz´ıt i pro data pozemn´ıho skenován´ı.

Obrázek 3.3: Proximity graph based segmentation.

3.4

Region growing

V tˇechto algoritmech je v mraˇcnu náhodnˇe vybrán 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é ji definuj´ı). Tento prvek je postupnˇe spojován s dalˇs´ımi bl´ızk´ ymi body na základˇe veliˇcin, jako jsou parametry normály, sklon, kˇrivost, atd. Urˇcován´ı bl´ızkosti bod˚ u a jejich sousedstv´ı se provád´ı r˚ uzn´ ymi zp˚ usoby. Jedn´ım

Prot´ınán´ı 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é s´ıtˇe a okol´ı bodu vymezuj´ı hrany Voronoyova diagramu. Nároˇcnost na v´ ypoˇcet troj´ uheln´ıkové s´ıtˇe je natolik vysoká, ˇze se radˇeji vol´ı jiné ménˇe nároˇcné metody. Tou je napˇr´ıklad hledán´ı soused˚ u pomoc´ı koule o daném polomˇeru, kterou op´ıˇseme kaˇzdému bodu. Body, které do koule padnou povaˇzujeme za sousedy stˇredového 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álenost bod˚ u, ale také jejich rozloˇzen´ı, tud´ıˇz dalˇs´ım kriteriem se stává symetrie. Zavád´ı se pojem medianové sousedstv´ı ( nearist centroid/median ” neighborhood“). Jin´ y postup v kategorii region growing vycház´ı ze skuteˇcnosti, ˇze data jsou poˇrizována postupnˇe podél skenovac´ıch lini´ı. Nejprve jsou tedy body tˇechto lini´ı proloˇzeny polynomickou funkc´ı a poté se porovnává bl´ızkost jednotliv´ ych kˇrivek. Jde tedy o sekvenˇcn´ı region growing, a to nejdˇr´ıve ve smˇeru skenu, následnˇe napˇr´ıˇc skeny. Tento algoritmus navrˇzen´ y v roce 1994 pro zpracován´ı dat leteckého skenován´ı stále nacház´ı své uplatnˇen´ı a ve srovnán´ı s ostatn´ımi algoritmy dosahuje uspokojiv´ ych v´ ysledk˚ u. Metodu region growing je moˇzné pouˇz´ıt také 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án´ı profil˚ u, zpracovan´ ych ve 2D. Metoda je vyvinutá pro zpracovnán´ı dat leteckého laserového skenován´ı [1]. Postupuje se v tˇechto kroc´ıch: 1. Mraˇcno bod˚ u je rozˇrezáno“ na profilové pásy o urˇcité ˇs´ıˇrce s r˚ uznou orientac´ı. ” 2. Body jsou v rámci pás˚ u spojovány bud’ na základˇe aproximace pˇredem definovanou kˇrivkou nebo na základˇe porovnáván´ı vzdálenost´ı mezi body s danou mezn´ı délkou (obrázek 3.4). Skupiny bod˚ u splˇ nuj´ıc´ı daná kritéria (mezn´ı vzájemnou vzdálenost nebo mezn´ı vzdálenost od proloˇzené kˇrivky ) jsou spojeny lomen´ ymi ˇcarami. V kaˇzdém profilu tak vznikne mnoˇzina lomen´ ych ˇcar,

Prot´ınán´ı profil˚ u

15

kdy kaˇzdá tato ˇca´ra bude náleˇzet jednomu segmentu. 3. Totoˇzná 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áleˇzej´ıc´ı jedné homogenn´ı ploˇse (obrázek 3.5).

Obrázek 3.4: Segmentace v profilech pomoc´ı Delaunayovy triangulace (vlevo) a na základˇe prokládán´ı kˇrivkou (vpravo).

Obrázek 3.5: Pˇr´ıklad segmentace dvou rovnobˇeˇzn´ ych rovin pomoc´ı prot´ınán´ı profil˚ u ve tˇrech r˚ uzn´ ych orientac´ıch.

Segmentace podle parametr˚ u roviny na základˇ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ále Gradient based method, publikována v ˇclánku Bena Gorteho [4], pracuje s mraˇcnem ve 2.5D prostoru. Metoda je podrobnˇe popsána 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ásleduj´ı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áˇst’ ve smˇeru ˇrádk˚ u a sloupc˚ u. 3. V´ ypoˇcet horizontáln´ıch a vertikáln´ıch u ´hl˚ u normál rovin, jimˇz pixely náleˇz´ı. 4. V´ ypoˇcet tˇret´ıho parametru rovin - vzdálenosti ρ od poˇca´tku (vzorec odvozen z Houghovy transformace). 5. Pˇriˇrazen´ı pixel˚ u k plochám podle tˇechto tˇr´ı parametr˚ u metodou region merging (spojován´ı list˚ u quad-tree). Ve vlastn´ım skriptu metoda region merging pouˇzita nebyla. Spoˇc´ıvá ve spojován´ı 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á vzdálenost pixel˚ u v pˇr´ıznakovém prostoru (feature space) a rozd´ıly mezi diagonáln´ımi prvky kovarianˇcn´ıch matic segment˚ u nepˇresáhnou stanovenou mez. Tato metoda je navrˇzena pro segmentaci dat pozemn´ıho skenován´ı.

3.7

RANSAC

Algoritmus RANSAC (RANdom SAmple Concensus, [5]) je iteraˇcn´ı robustn´ı metoda na zjiˇst’ován´ı parametr˚ u matematického modelu mˇeˇren´ ych dat. Pˇredpokládá, ˇze data obsahuj´ı nejen správné“ hodnoty (inliers), ale i velk´ y poˇcet hodnot odlehl´ ych ” (outliers). V´ ysledn´ y model obsahuje pouze data správná“. ”

RANSAC

17

Obrázek 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áhodnˇe prokládá matematick´ y model, v naˇsem pˇr´ıpadˇe rovina, a posléze se zjiˇst’uje porovnán´ım se stanovenou mezn´ı odchylkou, kolik dat je oznaˇceno jako inliars a kolik jako outliers. Náhodné prokládán´ı se provád´ı opakovanˇe a u kaˇzdé nové iterace se hodnot´ı poˇcet inliars. Rovina, jeˇz jich ˇc´ıtá nejv´ıce, je ta správná. 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é iteraci se náhodnˇe vybere n správn´ ych dat (vol´ı se),

w

je pod´ıl dat správn´ ych a celého 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é hodnoty. Algoritmus prob´ıhá v tˇechto kroc´ıch:

RANSAC

18

1. Náhodnˇe se vyberou 3 body, z nichˇz se vypoˇc´ıtaj´ı parametry modelu, v tomto pˇr´ıpadˇe 4 parametry normály roviny. 2. Nyn´ı se vypoˇc´ıtává vzdálenost kaˇzdého bodu od roviny a porovnává se se stanovenou mez´ı. Body s vˇetˇs´ı vzdálenost´ı jsou oznaˇceny jako outliers. 3. Zaznamenaj´ı se parametry roviny, poˇcet správn´ ych dat a opakuje se se bod 1. a 2. Pokud je poˇcet správn´ ych dat vˇetˇs´ı pˇri druhé a kaˇzdé dalˇs´ı iteraci, bere se nov´ y model za správn´ y a hodnoty modelov´ ych parametr˚ u pˇredeˇslé 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ávn´ 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á ˇcást 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á ˇcást diplomové práce se zab´ yvá vyuˇzit´ım nˇekter´ ych algoritm˚ u a postup˚ u zm´ınˇen´ ych v pˇredeˇslé kapitole v praxi. Testované mraˇcno bylo segmentováno pomoc´ı vlastn´ıch skript˚ u v programu Matlab a dále v komerˇcn´ım software Geomagic (Kapitola 5), urˇcenému ke zpracován´ı dat LS. Test prob´ıhal na datech poˇr´ızen´ ych ze zamˇeˇren´ı fasády budovy Arcibiskupského semináˇre v Praze 6, Dejvic´ıch. K testován´ı byla pouˇzita pouze ˇca´st mraˇcna bod˚ u namˇeˇreného z jednoho stanoviska - v´ yˇrez jednoho okna fasády zobrazen´ y na obrázku 4.1. Toto mraˇcno ˇc´ıtalo 182 017 bod˚ u. Do segmentace vstupovaly pouze pravo´ uhlé souˇradnice objektu, radiometrické veliˇciny bod˚ u nebyly vyuˇzity. Na závˇer bylo vybranou metodou segmentováno celé mraˇcno bod˚ u. Mraˇcna bod˚ u byla uloˇzena jako

Obrázek 4.1: Testované mraˇcno.

seznamy souˇradnic x, y, z ve dvou souborech okno.xyz a fasada.xyz. Pouˇzité skripty a funkce jsou uvedené v pˇr´ıloze a uloˇzené na disku v adresáˇri FUNKCE jako soubory ∗ .m.

Segmentace ve 2.5D prostoru

4.1

20


Prvn´ı testovaná metoda prob´ıhala ve 2.5D prostoru. Bylo nutné naˇctené body o souˇradnic´ıch x, y, z s poˇca´tkem ve stanovisku pˇrevést na tzv. range image.

4.1.1

Range image

Obrázek 4.2: Range image celé fasády.

Range image je rastr, kde po sloupc´ıch zleva doprava nar˚ ustá horizontáln´ı u ´hel sn´ımán´ı o konstantn´ı u ´hel ∆α a po ˇrádc´ıch zdola nahoru nar˚ ustá vertikáln´ı u ´hel o konstantn´ı u ´hel ∆β. Hodnoty pixel˚ u znamenaj´ı vzdálenost objektu od centra sn´ımán´ı. Velikost ∆α a ∆β závis´ı na hustotˇe sn´ımán´ı, v tomto pˇr´ıpadˇe ∆α = ∆β = 0, 00035 rad = 72, 200 . Pˇrevod mraˇcna bod˚ u z 3D do 2.5D prob´ıhá pomoc´ı vlastn´ı funkce range image (skript uveden v pˇr´ıloze na stranˇe 53). Postup, ˇcásteˇcnˇe pˇrevzat´ y ze skriptu pana ˇ Ing. Jana Rezn´ ıˇcka, je následovn´ y: 1. Pravo´ uhlé souˇradnice xyz byly pˇrevedeny na sférické 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ána na soustavu souˇradnic α, β a R, jej´ıˇz poˇca´tek je v levém horn´ım rohu rastru, souˇradnice α nar˚ ustá po sloupc´ıch a β ve smˇeru pˇrib´ yván´ı ˇrádk˚ u. Hodnoty vzdálenost´ı od poˇca´tku R se nemˇen´ı.


21

Z obrázku 4.3 je patrné odvozen´ı transformace ze sférick´ 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átek soustavy na stˇred pixelu.

Obrázek 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ávn´ y ten s vˇetˇs´ı vzdálenost´ı. T´ım se pˇredejde moˇznému ˇsumu, zp˚ usobenému napˇr´ıklad náhodn´ ymi chodci a jin´ ymi objekty, které mohly doˇcasnˇe zast´ınit objekt zájmu. Body nevyuˇzité 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


22

bod do pomocného 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é. Pro vytvoˇren´ı rangeimage nebyly pouˇzity 1 684 body, které jsou zapsány ve vektoru link a podlehnou tak segmentaci také. V´ ysledn´ y rastr range image obsahuje 2 vrstvy. V prvn´ı vrstvˇe je vlastn´ı range image s hodnotami vzdálenost´ı od poˇcátku R, zat´ımco druhá vrstva podává informaci o rozloˇzen´ı objektu v range image a pomoc´ı jedniˇcek a nul rozliˇsuje prázdné pixely (0) a pixely objekt obsahuj´ıc´ı (1). Zobrazen´ı prvn´ı vrstvy rastru je v obrazové ˇca´sti pˇr´ılohy. Vstupn´ımi parametry funkce range image jsou: seznam souˇradnic ve formátu xyz a rozliˇsen´ı range image (rozliˇsen´ı skenován´ı 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é v range image, vektor posun˚ u sférick´ ych souˇradnic pˇri transformaci (vyuˇzije se pˇri zobrazen´ı range image), seznam p˚ uvodn´ıch sférick´ ych souˇradnic. Vznikl´ y rastr range image je tˇreba dále oˇcistit od ˇsumu, popˇr´ıpadˇe interpolovat prázdné pixely. K tomu slouˇz´ı vlastn´ı funkce cisteni a interpolace. Odstranˇ en´ı ˇ sumu Po vytvoˇren´ı range image, je nezbytné rastr oˇcistit o ˇsum - shluky bod˚ u (v tomto pˇr´ıpadˇe pixel˚ u), které objektu nenáleˇzej´ı. Tyto pixely jsou v rastru bud’ mimo objekt, a nebo jsou obklopeny pixely objektu, ale maj´ı v´ yraznˇe menˇs´ı hodnotu vzdálenosti 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é shluky bod˚ u pomoc´ı pohyblivého okna, které prob´ıhá po druhé vrstvˇe rastru a porovnává prázdné a zaplnˇené pixely. Pokud jsou vˇsechny okrajové pixely prázdné 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ách na nulu. Pokud jsou okrajové pixely kernelu nenulové, spoˇc´ıtá se z prvn´ı vrstvy range image jejich medián a porovná s mediánem vnitˇrn´ıch pixel˚ u. V pˇr´ıpadˇe, ˇze rozd´ıl


23

Obrázek 4.4: V´ yˇrez z range image fasády p˚ uvodn´ı a po odstranˇen´ı ˇsumu.

obou medián˚ u pˇresáhne danou mez, jsou vnitˇrn´ı pixely povaˇzované za ˇsum a dojde k jejich vymazán´ı. Nastavená 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án˚ 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ává, ˇze i pˇres vhodné nastaven´ı rozliˇsen´ı do nˇekterého z pixel˚ u padne v´ıce bod˚ u a do nˇekterého pixelu ˇza´dn´ y, aˇckoli je zˇrejmé, ˇze pixel mˇeˇrenému objektu náleˇz´ı. V tomto pˇr´ıpadˇe je nutná interpolace tˇecho prázdn´ ych pixel˚ u. Prob´ıhá iteraˇcnˇe a to tak, ˇze pro kaˇzd´ y prázdn´ y pixel se vyˇsetˇruje okol´ı (ˇctvercová matice o rozmˇeru 3x3, 5x5 ˇci 7x7 pixel˚ u) a pˇri nalezen´ı


24

urˇcitého poˇctu nenulov´ ych pixel˚ u se hodnota stˇredového nastav´ı na median okol´ı. Hodnota v druhé vrstˇe se pˇrep´ıˇse z 0 na 1. Poˇcet nutn´ ych nenulov´ ych pixel˚ u n záleˇz´ı na hustotˇe skenovan´ ych bod˚ u a stanov´ı se na základˇ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ávˇ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ány pouze vnitˇrn´ı pixely a nedocházelo k pˇrir˚ ustán´ı nenulov´ ych pixel˚ u na okraj´ıch objektu. Pˇri zpracován´ı dat o jiné hustotˇe bod˚ u vˇsak nemus´ı vyhovovat ˇzádn´ y z tˇechto dvou vzorc˚ u.

Obrázek 4.5: V´ yˇrez z range image fasády pˇred a po interpolaci. K interpolaci nedocház´ı, pokud se hodnoty spadaj´ıc´ı do kernelu v´ yraznˇe liˇs´ı.


25

M˚ uˇze se totiˇz jednat o neodstranˇen´ y ˇsum nebo o skuteˇcnost, ˇze pixel náleˇz´ı nˇejaké hranˇe. Pouˇzit´ı interpolace je vhodné 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é pixely. Ve v´ ysledném gradientovém rastru by se proto bez interpolace prázdn´ ych pixel˚ u vyskytovaly v jejich okol´ı velké 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ého pixelu pro proveden´ı interpolace a poˇcet opakován´ı interpolace na celém 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ásleduj´ıc´ı segmentaˇcn´ı metody spoˇc´ıvaj´ı ve stanoven´ı parametr˚ u rovin, kter´ ym náleˇz´ı jednotlivé body reprezentované pixely. Tyto parametry budou dále slouˇzit k rozliˇsen´ı homogenn´ıch oblast´ı mraˇcna (rastru). Parametry byly zjiˇstˇeny nezávisle pomoc´ı dvou metod, a to prokládán´ım rovin na malém okol´ı bodu (pixelu) a na základˇe v´ ypoˇctu gradientu pixelu z jeho okol´ı. Pro kaˇzd´ y pixel range image jsou tak stanoveny 3 parametry normály definuj´ıc´ı rovinu, v n´ıˇz pixel (bod) leˇz´ı. Jsou to horizontáln´ı u ´hel θ, vertikáln´ı u ´hel φ a vzdálenost od poˇcátku ρ. Z jednoho rastru range image byly tedy z´ıskány 3 rastry, podle nichˇz lze provést posledn´ı fázi segmentace pˇriˇrazen´ı pixel˚ u k plochám. Prokl´ ad´ an´ı rovin V této 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ály proloˇzen´ım roviny v bl´ızkém okol´ı, jeˇz pˇredstavuje matice 3x3, event. 5x5 pixel˚ u. Pro stˇredov´ y pixel matice se tak vypoˇctou parametry normály ze souˇradnic bod˚ u, které spadaj´ı do pixel˚ u této pohyblivé matice. Do v´ ypoˇctu nebyly zahrnuty body, které se ˇ nevyuˇzily pˇri tvorbˇe range image. V´ ypoˇcet metodou nejmenˇs´ıch ˇctverc˚ u (MNC)


26

na základˇe momentu bod˚ u s vyuˇzit´ım singulárn´ı dekompozice [3] urˇcil pro kaˇzd´ y pixel range image parametry normály θ, φ a ρ. Postupuje se takto: Ze souˇradnic bod˚ u spadaj´ıc´ıch do pohyblivého okna matice se vypoˇc´ıtaj´ı pr˚ umˇerné 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árn´ı dekompozice svd() matice M, obsahuj´ıc´ı smˇerodatné odchylky souˇradnic bod˚ u spadaj´ıc´ıch do kernelu, z´ıskáme 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ávˇe parametry a, b, c hledané normály roviny. Ctvrt´ y parametr d z´ıskáme dosazen´ım do obecné rovnice pro rovinu.

ax + by + cz + d = 0

(4.9)

Pravo´ uhlé souˇradnice a, b, c normál byly dále pˇrevedeny na sférické θ a φ a vzdálenost od poˇcátku soustavy d odpov´ıdá parametru ρ . Tyto tˇri parametry normál rovin kaˇzdého pixelu byly zobrazeny do rastr˚ u Theta, Phi a Rho (viz obrázek 4.6). V´ ypoˇcet prokládán´ım rovin na okol´ı pixelu provád´ı 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ádané rovinou. V´ ystupn´ımi parametry jsou rasty Theta, Phi a Rho.


27

Obrázek 4.6: Rastry Theta (vlevo), Phi (uprostˇred) a Rho (vpravo). Hodnoty u ´hl˚ u prvn´ıch dvou rastr˚ u jsou udány v radianech, hodnoty rastru Rho v metrech.

V´ ypoˇ cet na z´ akladˇ e gradientu Tato metoda, uvedena v publikaci [4], spoˇc´ıvá v urˇcen´ı gradientu na okol´ı pixelu zvláˇst’ v horizontálan´ım a vertikáln´ım smˇeru. Podle vztah˚ u odvozen´ ych z obrázku 4.7 se vypoˇc´ıtaj´ı u ´hly normál θ 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áln´ı a vertikáln´ı u ´hly skenován´ı, jeˇz známe pro kaˇzd´ y bod, tedy i pixel o souˇradnic´ıch i, j. Rozd´ılové u ´hly ∆θij a ∆φij vypoˇc´ıtáme funkc´ı arctan z troj´ uheln´ıku o odvˇesnách ∆R (gradient) a δ. Prvn´ı odvˇesna, gradient range image, je zmˇena vzdálenosti od centra sn´ımán´ı ∆R pˇri pˇrechodu z jednoho pixelu na druh´ y. Horizontáln´ı gradient se poˇc´ıtá ve smˇeru zprava doleva, vertikáln´ı gradient zdola nahoru. Podle toho jsou sestaveny filtry na v´ ypoˇcet obou gradient˚ u (obrázek 3.1 a 4.8). Druhá odvˇesna troj´ uheln´ıku δ je délka oblouku vymezeného u ´hlem ∆α (v hori-


28

Obrázek 4.7: V´ ypoˇcet rozd´ılového u ´hlu ∆φ z gradientu z´ıskaného z range image.

zontáln´ım smˇeru) nebo ∆β (ve vertikáln´ım smˇeru) o polomˇeru R. ∆α a ∆β je u ´hlové rozliˇsen´ı rastru range image, jeˇz nastavujeme pˇri jeho vytvoˇren´ı podle rozliˇsen´ı pˇri skenován´ı. 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


29

Podle vztahu ρij = x · cos θij · cos φij + y · sin θij · cos φij + z · sin φij ,

(4.13)

odvozeného z Houghovy prostorové transformace se vypoˇc´ıtá tˇret´ı parametr normály - vzdálenost od poˇca´tku ρ. V´ ypoˇcet gradientu lze provést pomoc´ı Sobelova filtru 3x3 viz obrázek 3.1 nebo pomoc´ı filtru 5x5 navrˇzeného autorem publikace [4] Benem Gortem viz obrázek 4.8.

Obrázek 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érick´ 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ávˇereˇcné fáze 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ákladˇe gradientu je urˇcen´ı tohoto parametru ze vzorce 4.13 naprosto nepˇresné a zkresluj´ıc´ı. Hodnoty pixel˚ u naleˇzej´ıc´ıch jedné rovinˇe, jak je vidˇet na obrázku 4.9 se pohybuj´ı v rozmez´ı 10 m! Pro pˇriˇrazován´ı pixel˚ u k plochám byla zvolena metoda region growing. Region growing Metoda je obdobou hladového algoritmu. Na zaˇcátku se zvol´ı náhodn´ y pixel Pi,j , jehoˇz okol´ı (opˇet matice 3x3 pixely) se prohledává. Pokud sousedn´ı pixel Pi±1,j±1


30

Obrázek 4.9: Rastry Theta (vlevo), Phi (uprostˇred) a Rho (vpravo), z´ıskané metodou podle Bena Gorteho. Hodnoty u ´hl˚ u prvn´ıch dvou rastr˚ u jsou udány 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é meze, pˇriˇrad´ı se ke stejné ploˇse jako pixel Pi,j . Pokud rozd´ıly ∆θ a ∆φ meze pˇresáhnou, oznaˇc´ı se pixel jako pixel jiné“ plochy (hraniˇcn´ı). Pˇri do” saˇzen´ı urˇcitého 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á okol´ı vˇsech pixel˚ u náleˇzej´ıc´ıch jedné ploˇse. Kdyˇz je plocha uzavˇrena hraniˇcn´ımi pixely, oznaˇc´ı se tyto jako neprohledané a opˇet se zvol´ı dalˇs´ı náhodn´ y, zat´ım neprohledan´ y pixel. Pokraˇcuje se, dokud nejsou vˇsechny pixely pˇriˇrazené k nˇejaké ploˇse. Pixely tvoˇr´ıc´ı plochu o menˇs´ım poˇctu pixel˚ u, neˇz je stanovená mez, jsou vyhodnoceny jako ˇsum. Vstupn´ımi parametry funkce region growing (Pˇr´ıloha, str. 58), jeˇz v´ ypoˇcet provád´ı, jsou: rastr Theta, rastr Phi, mezn´ı rozd´ıl hodnot parametru θ, mezn´ı rozd´ıl hodnot parametru φ, minimáln´ı poˇcet pixel˚ u v segmentu. V´ ystupem funkce je rastr obsahuj´ıc´ı pixely s ˇc´ıslem segmentu, jemuˇz náleˇz´ı.


31

Obrázek 4.10: Rozr˚ ustán´ı homogenn´ıch oblast´ı v algoritmu region growing.

Seznam souˇ radnic segmentovan´ ych bod˚ u Informaci o náleˇzitosti k homogenn´ım plochám je nyn´ı nutné pˇrenést 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é body, k jejichˇz souˇradnic´ım x, y, z pˇriˇrad´ı ˇc´ısla segment˚ u. K propojen´ı segmentovaného 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á k index˚ um nepouˇzit´ ych bod˚ u pro range image udává indexy bod˚ u, jeˇz je nahrazuj´ı. A tak je bod˚ um, které padly do stejného pixelu, pˇriˇrazená stejná 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éto 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.


32

Obrázek 4.11: Vizualizace seznamu segmentovan´ ych souˇradnic; barvy náleˇ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é zpracován´ı mraˇcna, od naˇcten´ı souˇradnic bod˚ u po nalezen´ı homogenn´ıch oblast´ı a vytvoˇren´ı nového segmentovaného seznamu souˇradnic, prob´ıhá pomoc´ı spouˇstˇec´ıho souboru. Vzhledem k dvˇema metodám pouˇzit´ ym pro zjiˇstˇen´ı paramer˚ u normál rovin byly vytvoˇreny dva tyto soubory. SegmentaceI.m vytvoˇr´ı ze seznamu souˇradnic rastr range image. Ten se dále oˇcist´ı od ˇsumu a metodou prokládán´ı rovin v okol´ı zjist´ı parametry normály roviny kaˇzdého pixelu. Vzniklé 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-


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án´ı parametr˚ u normál. V tomto pˇr´ıpadˇe se parametry zjiˇst’uj´ı na základˇe v´ ypoˇctu gradientu v range image. Proto je v´ yhodné po ˇcistˇen´ı ˇsumu jeˇstˇe prázdné hodnoty rastru range image interpolovat. Uspokojiv´ ych v´ ysledk˚ u segmentace lze dosáhnout 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ázek 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ál rovin, v nichˇz pixel (bod mraˇcna) leˇz´ı, a podle nich dále urˇcuje metodou region growing homogenn´ı oblasti rastru. Liˇs´ı se právˇe ve zp˚ usobu urˇcován´ı parametr˚ u pixelu. Segmentace I vyuˇz´ıvá prokládán´ı roviny na okol´ı pixelu, zat´ımco Segmentace II zjiˇst’uje parametry roviny pˇres v´ ypoˇcet horizontáln´ıho a vertikáln´ıho gradientu rastru range image. SegmentaceI je ˇcasovˇe nároˇcnˇejˇs´ı na v´ ypoˇcet, avˇsak vykazuje kvalitnˇejˇs´ı v´ ysledné rastry Theta, Phi a Rho. Na obrázku 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án´ı sloupc˚ u u rastru Theta a stejn´ yu ´kaz ve smˇeru nar˚ ustán´ı ˇra´dk˚ u u rastru Phi. Tuto neˇza´douc´ı zmˇenu barvy lze pˇrisuzovat bud’ zp˚ usobu pˇriˇc´ıtán´ı rozd´ıl˚ uu ´hl˚ u θ a φ v gradientové“ metodˇe, nebo chybˇe ve v´ ypoˇctu. ” Systematickou chybu se ale nepodaˇrilo ve skriptu odhalit. Na v´ ysledné segmentaci vˇsak nemá tento nedostatek vliv, jelikoˇz algoritmus region growin nevytváˇr´ı homogenn´ı oblasti na základˇe absolutn´ıch hodnot parametr˚ u v pixelu, ale jejich rozd´ıl˚ u, ˇcili relativn´ıch hodnot. Porovnává totiˇz parametry pixel˚ u na malém okol´ı jednoho segmentu. Pokud se vˇsak tento algoritmus pouˇzije pˇri zpracován´ı mnohonásobnˇe vˇetˇs´ıch mraˇcen s velk´ ymi homogenn´ımi oblastmi, algoritmus ˇca´steˇcnˇe selhává a v jedné homogenn´ı ploˇse vytváˇr´ı s nar˚ ustaj´ıc´ımi sloupci a ˇra´dky nové segmenty. Na závˇer bylo zpracováno vˇetˇs´ı mraˇcno fasády poˇr´ızené z jednoho stanoviska, ale s menˇs´ım rozliˇsen´ım (α = 2, 76 ’), neˇz mraˇcno testované. Pouˇzita byla SegmentaceI. V´ ysledn´ y segmentovan´ y rastr je volnˇe pˇriloˇzen v deskách diplomové práce ve formátu A3. ´ V´ ystupy segmentac´ı jsou uloˇzeny na pˇriloˇzeném datovém CD v adresáˇri VYSLEDKY v souborech SegmentaceI.mat, SegmentaceII.mat a fasada.mat).

4.2


Robustn´ı algoritmus RANSAC lze vyuˇz´ıt k segmentaci dat LS pˇr´ımo ve 3D prostoru. Algoritmus se aplikuje na celé mraˇcno bod˚ u a zjist´ı se parametry roviny, která procház´ı nejvˇetˇs´ı plochou zamˇeˇrenou v souboru dat (zde jde o základn´ı rovinu fasády). Po jej´ım nalezen´ı se v´ ypoˇcet provede opˇet. Nyn´ı vˇsak jen na datech, která byla v pˇredchoz´ım v´ ypoˇctu oznaˇcena jako outliars, ˇc´ımˇz se zamez´ı opˇetovnému 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é mnoˇzstv´ı bod˚ u, které jsou povaˇzovány za ˇsum. Ten se pˇredem stanov´ı podle ˇclenitosti objektu a kvality mˇeˇren´ ych dat. Udává se v procentech z celého mraˇcna. Pro segmentaci v programu Matlab byla pouˇzita speciáln´ı 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án v kapitole 3.7 a byla uloˇzena pod názvem RNS (Pˇr´ıloha, str. 63).


35

Vstupn´ımi parametry této funkce jsou: namˇeˇrená 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ále tedy bylo nutné 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é roviny (vzdalenost.m - Pˇr´ıloha, str.65). Funkce model roviny.m zjiˇst’uje parametry rovin právˇe pˇres v´ ypoˇcet momentu (viz 4.1.2 Prokládán´ı rovin). V´ ystupy funkce RNS jsou: vektor oznaˇcuj´ıc´ı inliars (1) a outliars (0), a vektor obsahuj´ıc´ı parametry roviny.

Obrázek 4.13: Mraˇcno bod˚ u segmentované algoritmem RANSAC; barvy náleˇ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álenost pro body ”inliars”byla nasta-


36

vena na 0.008 m. Dále je nutné 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é v´ ystupy z v´ y´ poˇctu jsou uloˇzeny v adresáˇri VYSLEDKY v souboru SegmentaceRNS.mat. Metodu segmentace s pouˇzit´ım algoritmu RANSAC je vhodné vyuˇz´ıt sp´ıˇse v pˇr´ıpadˇe málo ˇclenit´ ych jednoduˇsˇs´ıch objekt˚ u, obsahuj´ıc´ıch pouze rovnobˇeˇzné ˇci kolmé plochy. V opaˇcném pˇr´ıpadˇe docház´ı pˇri posuzován´ı inliars/outliars jedné plochy k oznaˇcen´ı bod˚ u, náleˇzej´ıc´ıch jiné ploˇse v m´ıstˇe pr˚ useˇcnice proloˇzen´ ych rovin. Z obrázku 4.13 je patrné chybné urˇcen´ı ˇsikmého prvku suprafenestry, jehoˇz ˇca´sti jsou pˇriˇrazeny r˚ uzn´ ym segment˚ um svisl´ ych ploch a pilastr˚ u fasády. Viditelnˇe si také algoritmus nedokáˇze poradit s ˇclenit´ ymi prvky kolem oken (ˇsambránou). Dalˇs´ım, ne tak závaˇzn´ ym problémem jsou plochy náleˇzej´ıc´ı sice jedné rovinˇe, avˇsak fyzicky oddˇelené. Pro jejich správnou segmentaci je potˇreba dalˇs´ıho algoritmu, kter´ y by je oddˇelil a vytvoˇril z kaˇzdého samostatn´ y segment. Aˇckoli je tato metoda segmentace pomˇernˇe rychlá ve srovnán´ı s dvˇema pˇredchoz´ımi, jej´ı u ´ˇcinnost nen´ı zdaleka tak vysoká.

5. Praktická ˇcást II - segmentace v programu Geomagic Studio 10

37

5 Praktick´ aˇ c´ ast II - segmentace v programu Geomagic Studio 10 V ˇsiroké nab´ıdce program˚ u na zpracován´ı dat LS, které jsou dostupné na trhu, jen málokteré 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áz´ıch), které na sebe navzájem navazuj´ı. Jsou to tzv. Point Phase – pracuje se s namˇeˇren´ ym mraˇcnem bod˚ u; v´ ysledkem je troj´ uheln´ıková s´ıt’ vytvoˇrená z oˇrezaného a upraveného mraˇcna Wrap Phase – pouˇz´ıvá se pouze v pˇr´ıpadˇe objekt˚ u s objemem, jejichˇz povrch má troj´ uheln´ıková s´ıt’ pokr´ yvat, v´ ysledek se dále zpracovává v následuj´ıc´ı fázi Polygon Phase – u ´prava vygenerované troj´ uheln´ıkové s´ıtˇe Shape Phase – s troj´ uheln´ıkovou s´ıt´ı se pracuje jako s objektem, jehoˇz strukturu lze dále 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áci s jednotliv´ ymi ˇca´stmi (plochami) objektu; moˇznost segmentace, klasifikace segment˚ u a pˇrevodu na CAD model. Testované mraˇcno bod˚ u bylo postupnˇe zpracováno v Point Phase, Polygon Phase a Fasion Phase. Právˇe v posledn´ım reˇzimu, Fashion Phase, lze objekt automaticky i manuálnˇe segmentovat, dále klasifikovat, tzn. pˇriˇrazovat segment˚ um jednoduché matematicky definované plochy (rovina, válcová plocha, kulová plocha a podobnˇe), a segmenty tˇemito plochami prokládat. Automatická segmentace byla provedena také v reˇzimu Shape Phase. V´ ysledky obou automatick´ ych segmentac´ı jsou stejné, mezi reˇzimy lze libovolnˇe pˇrep´ınat a aktivovat tak r˚ uzné funkce.

Point Phase

38

V následuj´ıc´ıch kapitolách bude struˇcnˇe popsán postup zpracován´ı v programu Geomagic Studio 10 od poˇca´teˇcn´ı Point Phase aˇz po koneˇcnou fázi Fashion Phase, v n´ıˇz právˇe segmentace prob´ıhá. Pro dosaˇzen´ı uspokojiv´ ych v´ ysledk˚ u nelze vˇsak za´ eˇsnost segmentace znaˇcnˇe závis´ı na vhodnedbat zpracován´ı v pˇredchoz´ıch fáz´ıch! Uspˇ né u ´pravˇe a selekci mraˇcna bod˚ u a na uspoˇrádán´ı vygenerované troj´ uheln´ıkové s´ıtˇe.

5.1

Point Phase

Point Phase, neboli fáze bod˚ u, pracuje s namˇeˇren´ ymi body povrchu objekt˚ u.

Obrázek 5.1: Namˇeˇrená data naˇctená do programu Geomagic Studio 10.

Nejprve bylo do programu Geomagic Studio 10 naˇcteno mraˇcno bod˚ u uloˇzené jako seznam souˇradnic v souboru okno.xyz (File → Open). Ruˇcnˇe byly oˇrezány odlehlé shluky bod˚ u a dále se aplikovaly tyto funkce (poznámky v závorkách ud´ avaj´ı nastaven´ı pouˇzité na testovaném mraˇcnu bod˚ u): Select disconnected Automatické vyhledáván´ın´ı odlehl´ ych nespojit´ ych shluk˚ u bod˚ u. Nastavuje se stupeˇ n odlehlosti (Separation: low ) a procentuáln´ı zastoupen´ı odlehl´ ych shluk˚ u (Size: 5.0 % )

Point Phase

39

Select outliars Automatické vyhledáván´ı odlehl´ ych bod˚ u - outliars. Nastavuje se stupeˇ n citlivosti ve ˇskále 0 - 100 (Senzitivity: 10 ). Reduce noise Tato funkce posunuje vybrané body tak, aby doˇslo ke sn´ıˇzen´ı ˇsumu na povrchu zamˇeˇreného objektu. V záloˇzce Parametrs se zvol´ı typ povrchu (Prismatic shapes (conservative)), stupeˇ n vyhlazen´ı 0 - 4 (Smoothness Level: 1 ), poˇcet iterac´ı (Iterations: 1 ) a maximáln´ı vzdálenost, o n´ıˇz m˚ uˇze b´ yt bod posunut (Deviation limit: 0.005 m). V záloˇzce Outliars se nastav´ı mezn´ı vzdálenost, kdy body jiˇz nejsou klasifikované 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áloˇzka Display Deviation umoˇzn ˇuje vizuáln´ı kontrolu posun˚ u bod˚ u (viz Obrázek 5.2).

Obrázek 5.2: Posuny bod˚ u pˇri aplikaci filtru Reduce noice, udáno v metrech.

V záloˇzce Statistics lze zjistit pr˚ umˇer posun˚ u vˇsech bod˚ u od ideáln´ıho povrchu (Average distance: 0.0013 m) a smˇerodatnou odchylku posun˚ u (Standard deviation 0.0010 m). Zmáˇcknut´ım tlaˇc´ıtka Crease info se lze informovat o hodnotˇe tzv. Crease ” angle“, která udává, zda je takto upravené mraˇcno vhodné pro vytvoˇren´ı troj´ uheln´ıkové s´ıtˇe. Tato hodnota by nemˇela b´ yt vˇetˇs´ı neˇz 10. Pˇri sn´ıˇzován´ı ˇsumu testovaného 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ávˇe funkce Uniform sample. Zadán´ım koneˇcného poˇctu bod˚ u ˇci v´ ysledné vzdálenosti mezi nimi v záloˇzce Input lze redukovat poˇcet bod˚ u celého mraˇcna (Absolute → Spacing: 0.02 m). Hustotu bod˚ u na hranách lze ˇcásteˇcnˇe, ˇci plnˇe zachovat nastaven´ım stupnˇe d˚ uleˇzitosti zakˇriven´ı v rozmez´ı 0 - 10 v záloˇzce Optimize (Curvature priority: 10 ). V´ yˇrez mraˇcna po

Obrázek 5.3: Aplikace filtru Uniform sample.

aplikaci filtru je na Obrázku 5.3.

Wrap Funkc´ı Wrap z´ıskáme z mraˇcna bod˚ u troj´ uheln´ıkovou s´ıt’, kterou lze dále zpracovávat v reˇzimu Wrap Phase ˇci Polygon Phase. V záloˇ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áloˇzce Advanced Option je moˇzné 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é mˇr´ıˇzky, do jej´ıˇz kaˇzdé buˇ nky má 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é troj´ uheln´ıkové s´ıtˇe a vytvoˇren´ı vyhlazeného souvislého modelu povrchu bez dˇer.

Polygon Phase

41

Flip normals Nejprve se urˇc´ı rub a l´ıc vytvoˇrené s´ıtˇe u ´pravou smˇeru normál troj´ uheln´ık˚ u. Funkce Flip normals prohod´ı smˇer normál celé s´ıtˇe, nebo jen vybran´ ych ˇca´st´ı. Fill holes Druhou aplikovanou funkc´ı je vyplnˇen´ı neˇzádouc´ıch otvor˚ u (dˇer) v s´ıti. V nab´ıdce této funkce je nˇekolik metod vyplnˇen´ı (celkové a ˇcásteˇcné vyplnˇen´ı, vytvoˇren´ı most˚ u atd.). D´ıry je moˇzné vyplnit automaticky, ˇci procházet jednu po druhé a vyb´ırat zp˚ usob vyplnˇen´ı. Sandpaper Pomoc´ı tohoto filtru lze pˇrej´ıˇzdˇen´ım kurzoru po troj´ uheln´ıkové s´ıti povrchu objektu ruˇcnˇe vyhladit jej´ı nerovnosti (viz Obrázek 5.4). Volbou Relax se vyhlad´ı stávaj´ıc´ı s´ıt’, zat´ımco volbou Clean se v oznaˇcené oblasti p˚ uvodn´ı troj´ uheln´ıky odstran´ı a vytvoˇr´ı se nová upravená s´ıt’. V záloˇzce Strenght se vol´ı m´ıra vyhlazen´ı.

Obrázek 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án´ım troj´ uheln´ıky o delˇs´ıch stranách.V záloˇzce Settings se nab´ızej´ı reˇzimy nastaven´ı redukce. Dˇeje se tak bud’ nastaven´ım mezn´ı vzdálenosti mezi polohou vrcholu p˚ uvodn´ıho troj´ uheln´ıku a polohou nové s´ıtˇe, nebo udán´ım v´ ysledného poˇctu troj´ uheln´ık˚ u (zvoleno Reduction

Polygon Phase

42

mode: Triangle count → Target triangle count: 20% ). V záloˇzce Advanced byla nastavena d˚ uleˇzitost pravidelnosti s´ıtˇe na maximum (Mesh Priority). Z Obrázku 5.5 je zˇrejmé, na které ˇca´sti modelu byla tako funkce pouˇzita.

Obrázek 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é s´ıtˇe a odstranˇen´ı nˇekter´ ych troj´ uheln´ık˚ u tak, aby s´ıt’ byla spojitá, tzn. kaˇzd´ y vnitˇrn´ı troj´ uheln´ık bude z kaˇzdé své strany sousedit právˇe s jedn´ım troj´ uheln´ıkem. Repair intersection Pokud se v s´ıti vyskytuj´ı troj´ uheln´ıky, které se navzájem prot´ınaj´ı, lze je vyhledat právˇe funkc´ı Repair intersection. V záloˇzce Mode se poté zvol´ı, jak se tyto troj´ uheln´ıky oprav´ı. Byla zaˇskrtnuta moˇznost Select Only a po ukonˇcen´ı funkce byly vybrané oblasti z ˇca´sti smazány a dotvoˇreny funkc´ı Fill Holes (viz v´ yˇse). Tato u ´prava je nezbytná pro pokraˇcován´ı v daˇs´ıch reˇzimech Shape Phase nebo Fashion Phase.

Fashion & Shape Phase

5.3

43


V tˇechto dvou reˇzimech je moˇzné provádˇet automatickou a poloautomatickou segmentaci mraˇcna, jeˇz je v pˇredeˇsl´ ych dvou fáz´ıch upraveno a z nˇehoˇz je vytvoˇrena troj´ uheln´ıková s´ıt’. Fashion Phase a Shape Phase se od sebe liˇs´ı dalˇs´ım zpracován´ım segment˚ u. Zat´ımco Shape Phase pˇristupuje ke vˇsem segment˚ um jako k obecn´ ym plochám, plát˚ um, v reˇzimu Fashion Phase lze segmenty následnˇe klasifikovat jako jednoduché matematické plochy (rovina, válcová, kuˇzelová a kulová plocha atd..). Detect contours Ve funkci Detect contours, jeˇz je aktivn´ı v obou reˇzimech, prob´ıhá automatická segmentace troj´ uheln´ıkové s´ıtˇe. Parametry rozpoznáván´ı homogenn´ıch oblast´ı se nacház´ı v záloˇzce Regions. Nastavuje se zde citlivost k zakˇriven´ı 0 - 100% (Curvature senzitivity: 98% ), tlouˇst’ka oddˇelovac´ıch pás˚ u mezi homogenn´ımi oblastmi 0 - 100% (Separator Senzitivity: 5% ) a velikost nejmenˇs´ıho moˇzného segmentu (Minimum area: 0.01m2 ). Po spuˇstˇen´ı segmentace (tlaˇc´ıtko Compute regions) se zobraz´ı troj´ uheln´ıková s´ıt’ rozdˇelená na homogenn´ı oblasti odliˇsené barvami a ohraniˇcené tzv. separátory (Obrázek 5.6, vlevo).

Obrázek 5.6: V´ ysledek automatické segmentace (vlevo) a jeho ruˇcn´ı editace (vpravo).


44

Separátory jsou ˇcervenˇe vyznaˇcené oblasti s velkou m´ırou zakˇriven´ı. Jedná se tedy o hrany oddˇeluj´ıc´ı jednotlivé segmenty (plochy).

Obrázek 5.7: Pouˇzit´ı funkce Remove islands.

Automaticky vyhodnocenné segmenty lze dále upravovat funkcemi, jeˇz nab´ız´ı záloˇzka Edit. Funkce Remove islands odstran´ı separátory, v pˇr´ıpadˇe, ˇze neodˇeluj´ı dva segmenty, ale vyskytuj´ı se uprostˇred jednoho segmentu (viz Obrázek 5.7). Dále je moˇzné odstranit pˇr´ıliˇs malé segmenty (Remove Small Regions) a vytváˇret ˇci odstraˇ novat oblasti separátor˚ u pomoc´ı kurzoru (lev´ ym tlaˇc´ıtkem myˇsi lze oznaˇcit troj´ uheln´ık s´ıtˇe za separátor, Ctrl + levé tlaˇc´ıtko myˇsi oznaˇcen´ı separátoru zruˇs´ı). Na Obrázku 5.6 je v´ ysledek automatického vyhodnocen´ı a následná ruˇcn´ı editace segmentovaného objektu. Po vˇsech u ´pravách lze také vygenerovat kˇrivky pˇredstavuj´ıc´ı hrany objektu, a to stisknut´ım tlaˇc´ıtka Extract v záloˇzce Contours. Kˇrivky jsou vytvoˇreny v m´ıstech oznaˇcen´ ych jako separátory (viz Obrázek 5.8). Tyto kˇrivky lze propojovat (tlaˇc´ıtko Contract), avˇsak po ukonˇcen´ı funkce Detect contours je nelze jiˇz dále 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á matematická primitiva, tyto plochy jimi proloˇzit a vygene-


45

Obrázek 5.8: Vygenerován´ı kˇrivek z oblast´ı separátor˚ 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é funkci extrahovat hrany. Záloˇzka Operations nab´ız´ı nˇekolik funkc´ı, jimiˇz postupnˇe procház´ıme. Prvn´ı z nich je Classify (viz Obrázek 5.9), která umoˇzn ˇuje urˇcen´ı matematické plochy, jeˇz segment pˇredstavuje. Urˇcen´ı prob´ıhá bud’ automaticky, nebo ruˇcnˇe v´ ybˇerem z nab´ızen´ ych definovan´ ych ploch (rovina, válcová, kuˇzelová

Obrázek 5.9: Dialog Classify.

a kulová plocha, architektonick´ y v´ ystupek, rotaˇcn´ı plocha a obecná plocha). Po klasifikaci následuje proloˇzen´ı klasifikovan´ ych segment˚ u pˇriˇrazen´ ymi plochami (Fit). Pomoc´ı funkce Analyze je moˇzné zobrazit odchylky p˚ uvodn´ı troj´ uheln´ıkové s´ıtˇe od proloˇzené plochy a statistické u ´daje o proloˇzen´ı (viz Obrázek 5.10). Proloˇzen´ım segment˚ u z´ıskáme z této funkce reˇzimu Fashion Phase CADovsk´ y model. Stejnˇe tak ho z´ıskáme v reˇzimu Shape Phase, avˇsak sloˇzitˇejˇs´ı, sloˇzen´ y pouze z obecn´ ych plát˚ u a kˇrivek (Obrázek 5.11).


46

Obrázek 5.10: Odchylky od p˚ uvodn´ı s´ıtˇe pˇri proloˇzen´ı vˇsech segment˚ u rovinami, udáno v metrech.

V porovnán´ı s automatickou segmentac´ı pomoc´ı vlastn´ıch skript˚ u v prostˇred´ı v´ ypoˇcetn´ıho programu Matlab se jev´ı práce v softwaru Geomagic Studio 10 na prvn´ı pohled snazˇs´ı a pohodlnˇejˇs´ı d´ıky pˇr´ıjemnému grafickému rozhran´ı. Zpracován´ı mraˇcna v tomto softwaru je ale ˇcasovˇe mnohem nároˇcnˇejˇs´ı vzhledem k znaˇcn´ ym u ´pravám a aplikac´ım mnoha filtr˚ u. Samotná automatická segmentace je pouze souˇca´st´ı funkce slouˇz´ıc´ı k detekci hran. Rozpoznáván´ı hran zˇrejmˇe prob´ıhá na základˇe zmˇeny sklonu troj´ uheln´ık˚ u v troj´ uheln´ıkové s´ıti, jej´ıˇz vytvoˇren´ı je k proveden´ı segmentace nezbytné. Z obrázku 5.6 je patrná menˇs´ı citlivost v rozeznáván´ı hran drobnˇejˇs´ıch segment˚ u. Dalˇs´ı ruˇcn´ı u ´prava segmentované s´ıtˇe je moˇzná, avˇsak opˇet ˇcasovˇe velmi nároˇcná.


47

Obrázek 5.11: CADovsk´ y model generovan´ y ve Fashion Phase (vlevo) a v Shape Phase (vpravo).

6. Závˇer

48

6 Z´ avˇ er C´ılem práce bylo prostudován´ı souˇcasn´ ych trend˚ u v automatickém zpracován´ı dat laserového skenován´ı (leteckého i pozemn´ıho), dále aplikace nˇekter´ ych metod ve vlastn´ım skriptu ve v´ ypoˇcetn´ım programu Matlab a zpracován´ı dat v nˇekterém z komerˇcn´ıch softwar˚ u. Teoretická ˇcást diplomové práce se vˇenuje nˇekolika metodám automatického zpracován´ı dat, konkrétnˇe jeho ˇcásti - segmentaci mraˇcna bod˚ u. Problematice segmentace se v souˇcasné dobˇe vˇenuj´ı hlavnˇe v zahraniˇc´ı. Práce ˇcerpá pˇredevˇs´ım z publikac´ı vydan´ ych na univerzitách v Nˇemecku a Nizozem´ı. Ke zpracován´ı prostorov´ ych dat, poˇr´ızen´ ych jak pˇri leteckém, tak pozemn´ım skenován´ı, 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ává poloha pixelu ve 2D obrazu a jeho hodnota. Dalˇs´ı postupy jsou v´ıce ménˇe shodné s postupy zpracován´ı 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án´ı ve 3D lze aplikovat napˇr. algoritmus RANSAC, jenˇz náhodnˇe a opakovanˇe prokládá 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ávat délky hran (bl´ızkost bod˚ u), a tak vytváˇret segmenty. Rozdˇelen´ım mraˇcna na soustavy profilov´ ych pás˚ u v r˚ uzn´ ych smˇerech zjednoduˇs´ıme u ´lohu ve 3D na u ´lohu v ploˇse. Propojován´ım bl´ızk´ ych bod˚ u v rámci kaˇzdého pásu 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é segmentaci je velké mnoˇzstv´ı, kaˇzd´ y má své v´ yhody a nev´ yhody. Práce ve 3D je napˇr´ıklad v´ ypoˇcetnˇe nároˇcnˇejˇs´ı, ale umoˇzn ˇuje zpracován´ı v´ıce registrovan´ ych mraˇcen najednou narozd´ıl od zpracován´ı ve 2.5D, kdy se do plochy pˇrevád´ı pouze data mˇeˇrená z jednoho stanoviska.

6. Závˇer

49

V praktické ˇcásti práce je popsána aplikace vytvoˇren´ ych vlastn´ıch skript˚ u na mraˇcno bod˚ u budovy Arcibiskupského semináˇre v Praze, Dejvic´ıch. Pro segmentaci byly zvoleny metody: region growing podle parametr˚ u roviny, j´ıˇz pixel náleˇz´ı (parametry byly zjiˇstˇeny na základˇe v´ ypoˇctu gradientu a nebo prokládán´ı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án´ı prob´ıhalo pro oba pˇr´ıpady zvláˇst’. Obˇe metody, avˇsak pˇri pouˇzit´ı r˚ uzného nastaven´ı algoritmu region growing, vykazuj´ı obdobné v´ ysledky. Metoda vyuˇz´ıvaj´ıc´ı algoritmu RANSAC je velmi rychlá, ale má jisté nedostatky. Pokud dojde k jejich odstranˇen´ı, tato metoda m˚ uˇze zauj´ımat prvn´ı m´ısto v automatizaci zpracován´ı dat LS. Pro zpracován´ı mraˇcna bod˚ u v komerˇcn´ım software byl k dispozici byl pouze jedin´ y program, a to na zpracován´ı dat pozemn´ıho prostorového skenován´ı - Geomagic Studio 10. Nebylo tak moˇzné vyzkouˇset práci se softwarem na zpracován´ı dat leteckého skenován´ı, ˇci porovnat práci s v´ıce softwary. Geomagic Studio 10 je jedin´ ym dostupn´ ym programem na stavebn´ı fakultˇe, kter´ y zpracovává data pozemn´ıho laserového skenován´ı a zároveˇ n obsahuje nástroje na segmentaci mraˇcna bod˚ u. Práce s t´ımto softwarem je pˇr´ıjemná d´ıky grafickému rozhran´ı, ale ˇcasovˇe je zpracován´ı dat daleko nároˇcnˇejˇs´ı. Mraˇcno bod˚ u se mus´ı nejprve ruˇcnˇe oˇcistit a upravit mnoha funkcemi, jejichˇz správné nastaven´ı mus´ı ménˇe zkuˇsen´ y uˇzivatel ˇcasto pouze odhadovat a nalézt jej ˇcetn´ ymi pokusy. Mraˇcno bod˚ u procház´ı nejménˇe tˇremi pracovn´ımi fázemi programu, pˇriˇcemˇz aˇz v posledn´ı fázi je moˇzné segmentaci provést. Hranice homogenn´ıch oblast´ı urˇcen´ ych automatickou segmentac´ı lze dále ruˇcnˇe upravit. Automatická segmentace v tomto programu tˇeˇzko rozezná menˇs´ı segmenty a segmenty, mezi nimiˇz je niˇzˇs´ı kˇrivost. Pro vyhodnocen´ı detail˚ u, jako byly právˇe prvky kolem okna budovy Arcibiskupského semináˇre, nen´ı automatická segmentace v programu Geomagic zcela vyhovuj´ıc´ı. V´ ysledkem praktické ˇca´sti provedené ve v´ ypoˇcetn´ım programu Matlab je mraˇcno bod˚ u rozdˇelené na homogenn´ı oblasti. Je uloˇzeno jako seznam souˇradnic, k nimˇz jsou pˇriˇrazeny ˇc´ısla segment˚ u. Na závˇer byl jeden z postup˚ u segmentace aplikován na mraˇcno bod˚ u budovy Arci-

6. Závˇer

50

biskupského semináˇre poˇr´ızené z jednoho stanoviska. Vizualizace segmentace ve 2.D rastru je vytiˇstˇenana na pap´ır formátu A3 a pˇriloˇzena v deskách diplomové práce. Vytvoˇrené skripty, funkce a v´ ystupy vˇsech proveden´ ych segmentac´ı jsou uloˇzeny na pˇriloˇzeném datovém CD. Na cel´ y segmentaˇcn´ı proces by bylo vhodné navázat dalˇs´ımi funkcemi a skripty, které by skupinami bod˚ u, pˇriˇrazen´ ych jednotliv´ ym segment˚ um, automaticky prokládaly rovinu, zjiˇst’ovaly pr˚ useˇc´ıky sousedn´ıch rovin a sestavily tak drátov´ y model objektu, dále zpracovateln´ y v nˇekterém CADovském programu. Vytvoˇren´ı takovéhoto souboru navazuj´ıc´ıch funkc´ı, do nˇehoˇz by uˇzivatel minimálnˇe zasahoval nastaven´ım jen nˇekolika parametr˚ u, by pˇrispˇelo k rozvoji mladé, stále se vyv´ıjej´ıc´ı metody mˇeˇren´ı - laserového skenován´ı.

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áce. 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)&&(r1)&&(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ı ćh ˇ 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);

%%


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);

%%


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);

%%


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ázek 6.1: Testované mraˇcno bod˚ u.

Pˇr´ılohy

71

Obrázek 6.2: Rastr range image.

Pˇr´ılohy

72

Obrázek 6.3: Rastr range image po ˇciˇstˇen´ı a interpolaci.

Pˇr´ılohy

73

Obrázek 6.4: Mraˇcno bod˚ u segmentované postupem Segmentace I.

Pˇr´ılohy

74

Obrázek 6.5: Mraˇcno bod˚ u segmentované postupem Segmentace II.

Pˇr´ılohy

Obrázek 6.6: Mraˇcno bod˚ u segmentované postupem SegmentaceRNS.

75

Pˇr´ılohy

76

Obrázek 6.7: Mraˇcno bod˚ u segmentované pomoc´ı nástroje automatické segmentace v programu Geomagic Studio 10.

Fakulta stavební Kateřina Turková

Recommend Documents