ANALIZA VIŠINSKIH NAPAK PRI POENOSTAVLJANJU POVRŠIN
ANALYSIS OF ERRORS IN ELEVATION FOR SIMPLIFIED SURFACES
Dr. Gregor Petkovšek, univ. dipl. inž. grad.
CGS plus, Brnčičeva 13, Ljubljana gregor.petkovsek@mail.com
Znanstveni članek
UDK: 528.1:528.7/.8:624.1
Povzetek l Pri načrtovanju v nizkogradnji se kot vir podatkov vse bolj uveljavljajo oblaki točk, iz katerih ustvarimo model obstoječega površja. Površine je nato možno uporabljati za 3D-načrtovanje ali pa se v primeru linijskih objektov na površine projicirajo prečni in vzdolžni profili, ki jih načrtovalci nato obdelujejo. Zaradi velikega števila točk je tovrstno delo pogosto obremenjujoče za strojno in programsko opremo in lahko povzroča motnje v procesu načrtovanja. Ena od možnosti, kako zaobiti to težavo, je poenostavljanje površin z izločanjem točk, ki ne prispevajo bistvene topografske informacije. Prispevek podaja oceno napak v višinah, ki nastanejo pri poenostavljanju površin, za ravninski in hribovski primer površine. Pri LIDAR-skih posnetkih z resolucijo 1 točke na m2 je mogoče izločiti okrog 90 % točk, da je povprečna absolutna napaka manjša od 2 cm, pri čemer je stopnja dovoljene poenostavitve odvisna od tipa terena. Raven teren je manj občutljiv za odstranjevanje točk.
Summary l In infrastructure design, point clouds are increasingly used to obtain models of existing ground. These surfaces can then be used for 3D design. Alternatively, longitudinal and cross axes can be draped to the surface to obtain sections for further processing. Manipulating large number of points can, however, significantly increase computational cost and affect processing speed. One of the options to overcome these problems is to simplify surfaces by removing points. The points that do not add significantly to the topographic information can safely be removed. The paper presents an analysis of elevation errors, that result from surface simplification. Two types of surfaces are considered: flat and hilly terrain. When LIDAR data with 1 point per m2 data is used, around 90 % of points can be removed to remain within the 2 cm tolerance. There was a difference between the two types of terrain, the flat terrain being less sensitive to point removal.
1«UVOD
Pri načrtovanju v nizkogradnji kot izhodiščno stanje pogosto uporabljamo model površine. Površine lahko za načrtovanje pravih 3D-objektov uporabimo neposredno. Pri linijskih objektih lahko iz površine dobimo projekcije vzdolžnih in prečnih osi, tj. vzdolžne in prečne profile, ki jih nato uporabimo pri načrtovanju.
LIDAR-ski posnetki zagotavljajo razmeroma natančen posnetek terena, vendar je število točk pogosto zelo veliko. To pomeni znatno obremenitev za strojno in programsko opremo in posledično možne motnje v delovnem procesu. Eden od možnih pristopov k problemu je poenostavljanje površin. Poeno-
stavitev površine pomeni zmanjšanje števila točk, robov in ploskev, ki tvorijo površino. S tem dosežemo hitrejše in udobnejše delo s površino, vendar se poenostavljena površina nekoliko razlikuje od originalne površine. V prispevku predstavljamo analizo napak višin, ki nastanejo pri poenostavljanju. Napako opredelimo s tremi parametri na površini kot celoti. V nizkogradnji nas pri načrtovanju pogosto zanimajo profili. Zato smo izvedli analizo napak tudi na posameznih profilih.
2 • METODA
Za potrebe študije smo uporabili metodo Edge contraction, ki temelji na krčenju robov v
točke. Rob lahko v splošnem skrčimo v katerokoli točko na robu. Običajno pa upoštevamo
pogoj, da morajo biti točke, ki tvorijo poenostavljeno površino, podmnožica točk originalne površine [Andersson, 2006]. V tem primeru rob skrčimo v eno od obeh krajišč. Tako lahko operacijo pojmujemo tudi kot izločanje točk. Za točke oziroma robove, ki
jih izločamo, se odločamo na podlagi analize spremembe površine, ki pri tem nastane. Ker so te operacije računsko zahtevne, se običajno uporablja katera od poenostavitev [Garland, 1997]. Postopek krčenja je prikazan na naslednji sliki:
Metoda je podrobneje opisana v različnih člankih [npr. Yan in sod., 2004; Hoppe 1996; Hoppe in sod. 1993]. Metodo lahko uporabimo za dvodimenzijsko ali tridimenzijsko triangulacijo. Podoben postopek se uporablja tudi v teoriji grafov [Wolle in Bodlaender, 2004]. V našem primeru smo za poenostavljanje uporabili znani program za načrtovanje v nizkogradnji AutoCAD Civil 3D [Autodesk, 2011].
Napako, ki pri tem nastane, smo analizirali z dvema pristopoma. Pri prvem (1) smo analizirali napake na površini kot celoti, pri drugem (2) pa smo na površino projicirali niz profilov in napake izvrednotili v profilih. Napako smo vrednotili s tremi kriteriji:
a)	koren iz srednje kvadratne napake (root mean square error, RMSE)
b)	srednja absolutna napaka (mean absolute error, MAE)
c)	srednja napaka (mean error, ME)
Za izvrednotenje smo uporabili zvezne (integralne) oblike: - na površini:
flHf.7fl= ^ !| ' ■ '.¿¡'HA	(1)
amt-^L-*uim	(2)
«HF-iJfc	(3)
Slika 1 • Krčenje roba AB v točko A
- na profilu:
-K—	(4)
RUSE = j, ^ O J^di
=	(5)
(6)
kjer je:
A ... skupna površina L ... dolžina profila z ... višina na poenostavljeni površini zo... višina na originalni površini
Površine, uporabljene za analizo, so bile dobljene s pomočjo nepravilne trikotniške triangulacije. V tem primeru lahko razliko površin razdelimo na množico ravnih elementov, ki so presečišča elementov originalne in poenostavljene površine. Potem lahko enačbo (1)
zapišemo kot vsoto kvadratov napake (SE) po elementih:
j«.» . (7)
In podobno za enačbi (2) in (3). Profile razdelimo na odseke med posameznimi točkami, tako da lahko enačbe (4)-(6) zapišemo kot vsote po odsekih i (Zje razlika višin med površinama):

L- 'V".. ' '' i ^ ^ <■	\
U- ..... Kml + Bj
' =u.——1fc»-*1
(8) (9) (10)
3*REZULTATI IN DISKUSIJA
Analizirali smo parametre napake na dveh površinah in enem nizu profilov. Z originalno površino smo primerjali površine, iz katerih smo odstranili 50 %, 75 %, 85 %, 90 %, 95 %, 98 % in 99 % točk.
Obe površini sta narejeni iz LIDAR-skega posnetka z resolucijo 1 m. Prva površina vsebuje 51255 točk, pokriva površino 508 ha in je ravninskega tipa, druga pa vsebuje 4455 točk, pokriva površino 457,56 ha in je hribovitega tipa. Površini sta prikazani na sliki 2. Primerjali smo srednje absolutne napake in srednje napake za obe površini. Rezultati so podani v preglednici 1.
Slika 2 • Posnetka terena: ravninski (LIDAR 1, levo) in hribovit (LIDAR 2, desno)
Zmanjšanje točk na površini (%)	LIDAR 1 MAE (m)	LIDAR 1 ME (m)	LIDAR 2 MAE (m)	LIDAR 2 ME (m)
50	0,004	-0,0001	0,006	0,0000
75	0,008	-0,0002	0,014	0,0000
85	0,011	-0,0002	0,021	0,0000
90	0,013	-0,0003	0,027	0,0002
95	0,019	-0,0004	0,042	0,0004
98	0,029	-0,0005	0,077	0,0006
99	0,039	-0,0011	0,116	0,0017
Preglednica 1 • Primerjava srednje absolutne napake (MAE) in srednje I napake (ME) za obe površini
Niz profilov vsebuje vodotok in nasip. Primer profila je prikazan na sliki 3. Originalna površina vsebuje 12.768 točk. Profili, dobljeni iz originalne površine, vsebujejo 92 do 128 točk. Dolžina profilov je 50 m, razdalja med njimi pa 20 m.
Slika 4 • Primer profila, uporabljanega za analizo
Slike 4-6 prikazujejo povečevanje napake pri poenostavljanju površin za izbrane profile.
Slika 4 • Koren srednje kvadratne napake (RMSE) v odvisnosti od stopnje poenostavitve površine
Slika 5 • Srednja absolutna napaka (MAE) v odvisnosti od stopnje poenostavitve površine
Slika 7 • Zmanjšanje števila točk v profilih v odvisnosti od zmanjšanja točk na površini
								
0-04 0-0 i								
								
								
								
0								
								
								
								
								
■006								_v
								
50 75 85 30 95 93 93
H odstranjenih
Slika 6* Srednja napaka (ME) v odvisnosti od stopnje poenostavitve površine
Zmanjšanje števila točk na površini (%)	Zmanjšanje števila točk v profilih (%)	Zmanjšanje št. točk v profilih - preračun na površino (%)	RMSE (m)	MAE (m)
50	21	38	0,007	0,005
75	40	64	0,015	0,011
85	51	76	0,020	0,015
90	57	81	0,025	0,018
95	64	87	0,039	0,025
98	71	91	0,050	0,037
99	71	91	0,069	0,051
Preglednica 2 • Povprečne vrednosti za vseh enajst profilov in povprečno zmanjšanje števila točk I v profilih
Slika 8* Primerjava profila P4 (levo, majhne napake) in P9 (desno, večje napake), projiciranega na originalno površino (črno), na površino z odstranjenih 85 % točk (modro) in 98 % točk (rdeče). Vertikalno merilo je povečano s količnikom 10
Povprečne vrednosti za vseh enajst profilov in povprečno zmanjšanje števila točk v profilih so podani v preglednici 2. Rezultati kažejo, da lahko ob privzeti toleranci 2 cm iz površin odstranimo 95 % (pretežno ravninski teren) oziroma 85 % (pretežno hribovit teren) točk. V obravnavanih profilih lahko ob enaki omejitvi odstranimo 85-90 % točk. Z izločanjem večjega števila točk se napaka znatno poveča. Poveča se tudi velikost (predznačene) srednje napake, kar vodi do napak pri računih količin izkopa in nasipa. Pri obravnavanih profilih širine 50 m in razdalje 20 m pomeni 1 cm srednje napake 10 m3 napake v računu količin. Vendar se predznak napake spreminja (slika 6), tako da se pri računu odseka z več profili ta napaka zaradi seštevanja različno predznačenih napak zmanjšuje.
Napaka je odvisna od kompleksnosti profilov, kar je lepo razvidno s slike 8. Profil P4, ki vsebuje manjše število lomov, je možno bolj natančno opisati z manjšim številom točk, medtem ko ima profil P9 večje število lomov, zato je napaka večja.
Ugotovimo lahko tudi, da je število ohranjenih točk v profilih večje kot na površini, tudi če delež profilnih točk »pretvorimo« iz linijskih v površinske deleže (tj. kvadriramo). To je ugodna lastnost metode in je posledica podaljševanja trikotnikov v smeri značilnih potez površja (vodotok, nasip - slika 9), kar ohranja točke na profilih.
4•SKLEP
Pri delu s površinami, ki jih ustvarimo iz LIDAR-skih posnetkov, so lahko časi procesiranja in izračunavanja zaradi velikega števila točk dolgi, kar zmanjšuje udobnost načrtovalskega dela. V ta namen lahko površine poenostavimo.
Pri poenostavljanju površin se izkaže, da lahko z odstranitvijo znatnega števila točk še vedno obdržimo za načrtovanje zadovoljivo točnost, zlasti glede na točnost snemanja. Če privzamemo, da je sprejemljiva srednja
absolutna napaka 2 cm, lahko iz obravnavanih površin odstranimo 95 % (pretežno ravninski teren) oziroma 85 % (pretežno hribovit teren) točk. V obravnavanih profilih lahko ob enaki omejitvi odstranimo 85-90 % točk. Pri večjem poenostavljanju so lahko napake v nekaterih profilih tudi precej večje.
5 * ZAHVALA
Prispevek je nastal v okviru projekta »Inter- podporo interventnemu ukrepanju«. Projekt nih projektov »ZNANJE ZA VARNOST aktivna vizualizacija poplavnih območij za je bil financiran v okviru ciljnih raziskoval- 2006-2010« pod številko M2-0135.
6 * LITERATURA
Autodesk 2011. AutoCAD Civil 3D 2012 Users Guide, 2011.
Garland, M., Heckbert, P., Surface Simplification Using Quadric Error Metrics, Zbornik SIGGRAPH '97, pp 209-216, Los Angeles, ZDA, avg. 1997. Yan, J., Shi, P., Zhang, D., Mesh Simplification with Hierarchical Shape Analysis and Iterative Edge Contraction, Transactions on the Visualisation
and Computer Graphics, 10/2, pp 142-151, IEEE 2004. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W., Mesh Optimization, Zbornik SIGGRAPH '93, pp 19-26, Anaheim, ZDA, avg. 1993. Hoppe, H., Progressive Meshes, Zbornik SIGGRAPH '96, pp 99-108, New Orleans, ZDA, avg. 1996.
Andersson, M., Gudmundsson, J., Levcopoulos, Ch., Restricted Mesh Simplification Using Edge Contractions, Zbornik COCOON 2006, pp 196-204. Taipei, Tajvan, 2006.
Wolle, T., Bodlaender, H. L., A Note on Edge Contraction, Institute of information and computing sciences, Utrecht university, technical report UU-CS-2004-028, 2004.