Full Te ms & Condi ions o access and use can be ound a
h p://www. and online.com/ac ion/jou nalIn o ma ion?jou nalCode= ej 20
Eu opean Jou nal o Remo e Sensing
ISSN: (P in ) 2279-7254 (Online) Jou nal homepage: h p://www. and online.com/loi/ ej 20
Au oma ic lane ma king ex ac ion om poin
cloud in o polygon map laye
Da id P ochazka, Jana P ochazko a & Ja omi Landa
To ci e his a icle: Da id P ochazka, Jana P ochazko a & Ja omi Landa (2018): Au oma ic lane
ma king ex ac ion om poin cloud in o polygon map laye , Eu opean Jou nal o Remo e Sensing,
DOI: 10.1080/22797254.2018.1535837
To link o his a icle: h ps://doi.o g/10.1080/22797254.2018.1535837
© 2018 The Au ho (s). Published by In o ma
UK Limi ed, ading as Taylo & F ancis
G oup.
Published online: 29 Oc 2018.
Submi you a icle o his jou nal
A icle iews: 122
View C ossma k da a
Au oma ic lane ma king ex ac ion om poin cloud in o polygon map laye
Da id P ochazka
a
, Jana P ochazko a
b
and Ja omi Landa
a
a
Depa men o In o ma ics, Mendel Uni e si y in B no, B no, Czech Republic;
b
Ins i u e o Ma hema ics, Facul y o Mechanical
Enginee ing, B no Uni e si y o Technology, B no, Czech Republic
ABSTRACT
Op imiza ion o oad ne wo ks is a common conce n wo ldwide, p ima ily o sa e y pu poses.
Because he ex en o hese ne wo ks is subs an ial, au oma ion o hei in en o y is highly
desi able. This pape concen a es on he oad in en o y p ocess ha is necessa y o egula
main enance. The key pa o ou oad ma king de ec ion and econs uc ion is based on
spanning ee usage. The spanning ees a e ob ained om alpha shapes o he de ec ed
oad ma kings. The spanning ees applica ion enables he eliable iden i ica ion o he oad
ma kings and p ecise econs uc ion o hei con ou s e en wi h noisy da a. Ou me hod
p ocesses he poin cloud da a ob ained om LiDAR measu emen s, and p o ides a common
ec o laye wi h oad lane polygons. Such a ec o laye is s o ed in a common ile o ma
suppo ed by he majo i y o geog aphical in o ma ion sys ems, hus p oducing an ou pu
ha can be con enien ly used o decision-making based on he oad in en o y p ocess.
ARTICLE HISTORY
Recei ed 3 No embe 2017
Re ised 5 Oc obe 2018
Accep ed 10 Oc obe 2018
KEYWORDS
LiDAR; mobile lase scanning;
poin cloud; oad su ace
ma king de ec ion; shape
econs uc ion; oad
in en o y
In oduc ion
Remo e sensing and mobile mapping p o ide spa ial
da a i ems ha a e he basis o he decision-making
p ocess in a ious applica ions. Pa icula ly, de ec ion
o objec s on he oads and in hei icini y, is one o
he impo an a eas in he las yea s. We can see a
gene al e o o op imize he oad ne wo k, especially
he e o o make i sa e . The Eu opean Union
ini ia i es can be aken as an example. The commu-
nica ion Towa ds a Eu opean Road Sa e y A ea
(COM, 2010) mo ed he a ge da e o hal ing he
numbe o a al oad acciden s o wa d o 2020 and
se he yea 2050 as he a ge da e o mo ing close
o ha ing ze o a ali ies.
Conce ning oad sa e y, he e a e wo key elemen s:
ca s and he oad i sel . The imp o emen o he ca s is
ocused especially on a ious eal- ime secu i y sys-
ems: lane guidance, collision wa ning, e c. The
In elligen T anspo Sys ems heme and he ela ed
eSa e y ini ia i e
1
a e ocused on his issue. I is possi-
ble o see a subs an ially ising amoun and quali y o
hese sys ems in con empo a y ca s.
On he o he hand, he e is an imp o emen in he
oad in as uc u e. In elligen Roads, Sus ainable
Su ace T anspo and simila EU p ojec s a e ocused
on he oad capaci y inc ease, imp o emen o oad
main enance and sa e y. Fo he implemen a ion o
he p oposed imp o emen s, we mus ha e s a e-o -a
in o ma ion abou he oads. I is c ucial o be amilia
wi h he s a e o a ic signs, oad su ace ma kings,
zeb a c ossings (A ias, Ri ei o, Soilán, Díaz-Vila ino, &
Ma ínez-Sánchez, 2015) and e en objec s along he
oads, o example poles o ees (Elhinney, Kuma ,
Cahalane, & McCa hy, 2010; Gonzalez-Jo ge, Puen e,
Ri ei o, Ma inez-Sanchez, & A ias, 2013;Pu,
Ru zinge , Vosselman, & Elbe ink, 2011).
This p ocess o oad in en o y comp ises a subs an-
ial amoun o manual wo k. The human ope a o s
measu e objec s in he ield, p ocess la ge amoun s o ,
o example ae ial images o LiDAR poin clouds and
p epa e ec o ep esen a ion o equi ed objec s. This
p ocess is ime consuming and he e o e slow and
expensi e. The e can be ound many p ojec s aimed a
au oma ic iden i ica ion o objec s ela ed o oads (e.g.
abo e-men ioned a ic signs o oad ma kings). Thei
e iew is p o ided below. A subs an ial numbe o hem
a e op imized o eal- ime ca sa e y sys ems.
Ou p ojec is ocused on he in en o y p ocess
issue. The goal is o p o ide an exac ec o ep e-
sen a ion s o ed in a o ma ha can be p ocessed in
common geog aphical in o ma ion sys ems (e.g. ESRI
ShapeFile map laye ). The p oposed me hod is no
sui able o eal- ime applica ions such as ca sa e y
sys ems men ioned. I can p oduce map laye s ha
can be e o lessly used o di e en spa ial analyses.
We p oposed a h ee phased applica ion ha au o-
ma ically p ocess poin cloud da a. Fi s ly, we make he
g ound poin de ec ion using ou published algo i hm in
Landa, P ochazka and S as ny (2013). The algo i hm is
based on a dynamic bounding box p inciple. The second
s ep is he lane ma king iden i ica ion ha consis s o he
CONTACT Jana P ochazko a [email p o ec ed] B no Uni e si y o Technology, Technicka 2, 616 69 B no, Czech Republic
1
h p://ec.eu opa.eu/ anspo / oad_sa e y/index_en.h m.
EUROPEAN JOURNAL OF REMOTE SENSING
h ps://doi.o g/10.1080/22797254.2018.1535837
© 2018 The Au ho (s). Published by In o ma UK Limi ed, ading as Taylo & F ancis G oup.
This is an Open Access a icle dis ibu ed unde he e ms o he C ea i e Commons A ibu ion-NonComme cial License (h p://c ea i ecommons.o g/licenses/by-nc/4.0/),
which pe mi s un es ic ed non-comme cial use, dis ibu ion, and ep oduc ion in any medium, p o ided he o iginal wo k is p ope ly ci ed.
successi e applica ion o he alpha shape me hod and
spanning ee. In he las s ep, we p esen a no el geo-
me ic me hod ha is able o econs uc a bi a y shape
o he lane ma king in ec o o m. I can p ocess he
inpu k-a y spanning ee, whe e k¼1;2;3;4.
In hispape weco e heissueo au oma ic oadline
de ec ion, iden i ica ion o i s kind, econs uc ion o i s
co ec shape and expo o heESRIShapeFilemaplaye .
Li e a u e o e iew
Ou me hod, as well as me hods used in simila p ojec s,
is based on he p ocessing o poin clouds p o ided by
ae ial o g ound ehicles equipped wi h LiDAR.
Ai bo ne lase scanning is equen ly used o
la ge a eas. The ai bo ne lase scanning da a is used
o digi al ele a ion models (Si hole & Vosselman,
2005; Susaki, 2012) and applica ions such as moni o -
ing o a mosphe ic ae osols in ecology (Bada ina h,
Kha ol, & Sha ma, 2009), s uc u al mapping in geol-
ogy (G ebby, Cunningham, Naden, & Tansey, 2012.
On he o he hand, he mobile lase scanning (MLS)
is used o u ban a eas mapping (G aham, 2010)
because i usually p o ides be e esul s due o a
highe poin cloud densi y.
Wi hin he u ban a eas, a e y common goal is
de ec ion o di e en s ee objec s (buildings, oad
su ace ma kings, s ee ligh s e c.). These de ec ed
objec s a e hen ep esen ed as 3D models (La a ge &
Malle , 2011) o map laye s ha a e used o spa ial
analyses (Landa & Ond ousek, 2016). The au ho s
(Yang, Dong, e al. 2017) p esen s a obus me hod
o oad acili ies ecogni ion based on mul iple
agg ega ion le els compu a ion and designing a se ies
o con ex ual ea u es o imp o e he ecogni ion
pe o mance. Ou a icle is ocused pa icula ly on
de ec ion o he oad su ace ma kings; he e o e, we
p esen p ima ily pape s ocused on his p oblem.
The p ocess o de ec ion o common s ee objec s
om LiDAR da a usually s a s wi h he classi ica ion
o he e ain poin s (Chen e al., 2009). The classi i-
ca ion o e ain poin s is used ei he o he isola ion
o objec s on he g ound, o o he elimina ion o
poin s ha a e no necessa y o he compu a ions. I
he a ge o he de ec ion is an objec wi h high
e lec ance p ope y, hen he poin s wi h high e lec-
ance a e isola ed (Yang, Fang, Li, & Li, 2012).
Subsequen ope a ions a e he oad ma king posi-
ion de ec ion and iden i ica ion o i s kind, o exam-
ple ull o b oken line (Chen e al., 2009; Yang e al.,
2012). The las pa o he p ocess can be he econ-
s uc ion o oad ma king shape. Howe e , his pa
is usually no used in me hods simila o he one
p esen ed in his pape . The p ocess commonly
ends wi h he iden i ica ion o he ma king ype.
Te ain poin classi ica ion
Te ain poin classi ica ion me hods can be di ided in o
wo g oups. The i s possibili y is o de ec di ec ly he
e ain poin s (e.g. he oad poin s), he o he is o
de ec he adjacen oad cu bs. This second app oach
has an ob ious limi a ion. I is no sui able o oads
ha a e no su ounded by de ec able bo de s.
A nai e di ec de ec ion app oach akes a gi en pe -
cen age o lowes poin s in he poin cloud and classi ies
hem as he g ound poin s (Babahajiani e al. 2014). The
disad an age o his me hod is again clea ly isible –
only oad segmen s wi h negligible ele a ion di e ence
can be p ocessed. None heless, mo e complex me hods
a e used in he p ac ically o ien ed p ojec s. In he a icle
by Bel on and Bae (2010), oad poin s a e de ined as he
lowes ho izon al poin s on a smoo h su ace. The
app oach desc ibed by Yang and Dong (2013)usesa
shape-based segmen a ion me hod. The segmen s o he
poin cloud a e hen classi ied using Suppo Vec o
Machines. The algo i hm can de ec lines o plana
and sphe ical pa ches; he e o e, i can be easily used
o g ound poin de ec ion. Ano he inno a i e me hod
p esen s he applica ion o Hough ans o ma ion on
Millime e Wa e Rada da a o ob ain oad edges (K.Y.
Guo, Hoa e, Jas eh, Sheng, & Gashino a, 2015).
As men ioned, he o he possibili y how o de ec a
oad is o ex ac i s oad cu bs. The oad cu bs c ea e a
bounda y o he oad because o hei highe ele a ion
abo e he oad su ace. Fo example, he me hod o
(Yang, Fang, & Li, 2013) desc ibes oad c oss-sec ions
wi h window ope a o s ha il e ou non-g ound
poin s. The window ope a o s wo k wi h h ee c i e ia:
ele a ion jump, poin densi y and slope change. Guan
e al. (2014) also uses he same c i e ia bu o a p e-
p ocessing o he aw poin cloud. The cloud is pa i-
ioned in o a se o ho izon al segmen s (so-called p o-
iles) acco ding o he ehicle ajec o y.
Road lane ma king de ec ion and iden i ica ion
om poin clouds
T a ic sign de ec ion, as well as oad su ace ma king
de ec ion, wo ks wi h he high e lec ance in ensi y
(highe e o e lec i e p ope y) o he special sign
pain . A ans o ma ion o he poin cloud in o 2D
images is commonly used.
In he a icle (Chen e al., 2009), he au ho s il e he
poin cloud on he basis o he poin e lec ance.
Consequen ly, hey gene a e a 2D bina y image. The
alue o each pixel is one i i co esponds o a su ace
ma king and ze o o he wise. The Hough ans o m is
hen applied o de ec he lines on he oad su ace.
Finally, hey iden i y he oad lanes using a bounding
box and RANSAC.
2
2
Random Sample Consensus.
2D. PROCHAZKA ET AL.
Ano he use o 2D images can be seen in Guan
e al. (2014). The au ho s gene a e 2D geo e e enced
in ensi y images using an ex ended in e se-dis ance-
weigh ed (IDW) app oach. Fu he , hey segmen
hese images in o oad ma king candida es wi h a
poin densi y-dependen me hod.
Fu he mo e, he au ho s in Yang e al. (2012) use
2D images o de ec oad ma kings. They gene a e a
geo e e enced image o he poin cloud. This image is
il e ed on he basis o poin e lec ance and heigh .
The inal s ep is labelling o he oad ma king egions
acco ding o hei shape and a angemen . The
me hod inco po a es ela ed seman ic knowledge
(e.g. shape, pa e n) o he oad ma king. A simila
example o he oad ma king de ec ion using 2D
images can be ound in Thuy and Leon (2010).
Ano he possibili y is o p ocess he LiDAR in ensi y
and ange a ibu es as used in Kuma , Elhinney, Lexis,
and McCa hy (2014). The desc ibed algo i hm gene -
a es 2D in ensi y as e su aces om he LiDAR da a.
Acco ding o he au ho s, he algo i hm can de ec 88%
o oad ma king poin s. Na u ally, he poin cloud da a
can be also combined wi h common RGB images o
de ec lane ma kings. Examples can be ound in Huang
e al. (2013), Li, Chen, Li, Shaw and Nuch e (2014).
Road lane ma king shape econs uc ion
The oad lane ma king shape (en elope) is equen ly
equi ed du ing he lane iden i ica ion p ocess. One
o he mos equen ly used ep esen a ions is a com-
mon bounding box. Howe e , such ep esen a ion
has wo majo limi a ions: (a) I can be used solely
o he s aigh lanes. (b) I can be used only in
si ua ions whe e he lane ma kings do no ouch o
c oss each o he (e.g. no on oad in e sec ions).
Ano he equen ly used ep esen a ion is he con-
ca e o con ex hull (Mo ei a & San os, 2007). The
hull quali y di ec ly depends on he amoun o noise
and complexi y o he shape. A solu ion p oposed by
Schindle , Maie and Janda (2012) uses ci cula a c
splines. Ne e heless, his app oach is no sui able o
line in e sec ions (see Figu e 1).
The oad lane ma king is i s ly ep esen ed by a
bounding box in Chen e al. (2009). Fu he he e is
applied he RANSAC cu e i ing algo i hm pub-
lished in Fischle and Bolles (1981) o localize each
lane ma king accu a ely. Finally, a poin is selec ed
e e y 10 cm along a i ed cu e. The inal coo dina e
o he poin is an a e age o poin s wi hin a 10 by
10 cm ec angula box su ounding he gi en selec ed
poin . The au ho s, howe e , do no econs uc he
ep esen a ion o ob ain he ma king en elope shape,
hey a e ocused only on i s de ec ion.
The shape ep esen a ions desc ibed abo e can
ha e insu icien quali y. The e o e, we ocus on a
me hod ha allows o eliably de ec and co ec ly
econs uc he lane ma king shape in his a icle.
Implemen a ion
This sec ion desc ibes ou app oach owa ds lane
ma king de ec ion, iden i ica ion and econs uc ion.
P ima ily, we ocus on he iden i ica ion o ull and
b oken oad lane ma kings. A key issue is o ind a
p ecise polygon ep esen a ion o each de ec ed
ma king and s o e his ep esen a ion in o a common
polygon map laye .
The de ec ion p ocess is he applica ion o ou
me hod p oposed in Landa e al. (2013). The ollow-
ing phase is he classic segmen a ion o he s anda d
well-known me hod. We p oposed a new wo-s ep
iden i ica ion phase ha consis s o he alpha shape
and spanning ee. The econs uc ion also p esen s a
no el geome ic me hod how o compu e he accu-
a e shape o he lane ma kings. The en i e p ocess is
b ie ly ou lined in Figu e 2.
G ound poin classi ica ion and lane ma king
de ec ion
Road ma king de ec ion me hods a e closely con-
nec ed wi h he poin e lec ance as desc ibed in he
p e ious sec ion. Ou me hod is based on such a
common app oach whe e he poin s wi h he e lec-
ance highe han a gi en h eshold a e chosen. In
his se o poin s wi h high e lec ance alues, he
g ound poin s a e hen classi ied. The g ound poin
classi ica ion is pe o med solely on his se o poin s
wi h high e lec ance o minimize he compu a ion
needs. The e lec ance alue depends on he ype o
he scanning de ice and i is se expe imen ally.
Fo g ound poin de ec ion, we use he algo i hm
p oposed in Landa e al. (2013). The algo i hm is
Figu e 1. Examples o possible oad lane ma king combina ions. Le : solid and dashed lane. Righ : examples o oad lane c ossings.
EUROPEAN JOURNAL OF REMOTE SENSING 3
based on a dynamic bounding box p inciple. The
inpu poin cloud is di ided in o sepa a e columns
and in each column he lowes poin s a e ex ac ed.
The ex ac ed g ound poin s a e u he segmen ed
on he basis o he Euclidean dis ance. The poin s
sa is ying empi ically he de e mined limi o max-
imal dis ance be ween wo poin s a e conside ed as
belonging in o a single segmen Figu e 3.
The esul o he Euclidean-based segmen a ion con-
ains also a subs an ial amoun o noise segmen s, o
example building pa s, cu bs e c. The elimina ion o
hese alse-posi i e segmen s is based on mul i- h esh-
old c i e ia. We de e mined hese condi ions:
● he minimal numbe o poin s in he segmen
● he maximal numbe o poin s in he segmen
● he maximal size o en elope ec angle in xo y
di ec ion,
● he minimal pe cen age o plana poin s using
RANSAC algo i hm (usual alue is 95 %).
The abo e-men ioned c i e ia c ea e he esul isible
in Figu e 3.
Lane ma king iden i ica ion
The esul o he g ound poin ex ac ion and segmen-
a ion desc ibed in he p e ious sec ion is a segmen ed
poin cloud whe e each segmen ep esen s a possible
oad ma king. Howe e , i is impo an o men ion
ha in spi e o he p e ious elimina ion o alse posi-
i e esul s, i s ill con ains some segmen s ha do no
ep esen oad ma kings (e.g. pa emen ).
In his pa , we desc ibe he iden i ica ion o a
pa icula line ype ( ull, b oken). The iden i ica ion
p ocess consis s o ou s eps:
(1) The 3D poin cloud is ans o med in o a 2D
poin cloud.
(2) The alpha shapes o ep esen ed objec s a e
compu ed.
(3) Thei spanning ees a e de e mined.
(4) The oad lane ma king segmen s a e iden i ied.
The i s s ep is he poin cloud ans o ma ion om a
geospa ial coo dina e sys em o a local coo dina e sys em.
This s ep simpli ies he compu a ions. Subsequen ly, he
conca e hull is equen ly compu ed as a shape ep esen-
a ion in some wo ks. None heless, such a conca e hull is
ambiguous (see Figu e 4); he e o e, we compu e he
alpha shape which is unambiguous. The alpha shape
compu a ion algo i hm is desc ibed in Edelsb unne ,
Ki kpa ick and Seidel (1983).
The alpha shape is a gene aliza ion o a con ex hull.
The gene al de ini ion in Edelsb unne , Ki kpa ick and
Seidel (1983) says ha alpha-hull o se Sis he in e sec-
ion o all closed discs wi h adius 1=α(αis a su icien ly
small bu o he wise a bi a y posi i e eal numbe ) ha
con ain all he poin s o S.Inou case, heDelaunay
iangula ion is used o cons uc a TIN (T iangula ed
Figu e 2. O e iew o he p oposed oad lane ma king de ec ion, iden i ica ion and econs uc ion p ocess. This p ocess is able o c ea e
a common polygon map laye om a gi en poin cloud.
Figu e 3. Le : Inpu poin cloud. Righ : Resul o segmen a ion based on mul i- h eshold c i e ia: segmen s iden i ied as
possible lane ma kings (posi i e) a e labelled in black, he o he segmen s (nega i e) a e labelled in ed.
4D. PROCHAZKA ET AL.

I egula Ne wo k) and he alpha shape is hen c ea ed
on he basis o C i e ion 1.
C i e ion 1: The leng h o he iangle is a leas
wo imes smalle han he median o he leng h o all
inne iangles.
This allows us o ob ain a hull ha is unambiguous
in con as o he conca e hull. The esul o he alpha
shape compu a ion is a ec o polygon ep esen ing
he ough shape o he lane ma king (Figu e 5).
Howe e , his shape canno be used as a oad lane
ep esen a ion. I ep esen s he en elope o he oad
lane poin cloud. The ac ual shape o he lane ma k-
ing is di e en . Fo his eason, he spanning ee o
he g aph ha is based on he alpha shape is con-
s uc ed. This p ocess o a spanning ee cons uc ion
is composed o (1) hinning o he alpha shape, (2)
ex ac ion o he spanning ee, (3) smoo hing and
il a ion o he spanning ee segmen s.
The hinning p oduces he simpli ied ep esen a-
ion o he image which is opologically iden ical wi h
he o iginal alpha shape image. The Guo-Hall hin-
ning algo i hm which was published in he a icle
(Guo & Hall, 1989) is chosen. To pe o m hinning,
he alpha shape is ans o med o a 2D image. The
hinning algo i hm p oduces an image wi h a se o
pixels ha la e c ea es a spanning ee. A ee is a
connec ed acyclic simple g aph and he spanning ee
is a spanning subg aph ha is also he ee. Le k-a y
ee be a oo ed ee in which each in e nal e ex has
no mo e han kchild en. A 1-a y ee is jus a pa h. A
2-a y ee is also called a bina y ee. The examples o
di e en k-a y spanning ees a e in Figu e 6.
The subsequen ex ac ion o he spanning ee
om he image is p o ided by he well-known ecu -
si e egion g owing algo i hm (Gonzalez & Woods,
2001). The algo i hm sea ches in he neighbou hood
o a s a pixel ( i s whi e pixel) o non-p ocessed
pixels. I one non-p ocessed pixel is de ec ed, i is
added o he esul s uc u e and his poin is labelled
as p ocessed. I wo o mo e non-p ocessed pixels a e
de ec ed, each pixel is labelled as he s a pixel o a
new pa o he lane ma king segmen . In he case
ha he algo i hm does no de ec any non-p ocessed
poin , he sea ch is inished and he spanning ee o
he g aph is aken as a esul . The smoo hing and
il a ion o segmen s is pe o med by he Rame -
Douglas-Peucke algo i hm (Douglas & Peucke ,
1973; Rame , 1972).
Finally, he poin s o he spanning ee a e ans-
o med om he local coo dina e sys em back o he
o iginal geospa ial coo dina e sys em. All h ee
Figu e 4. Di e en ypes o co ec conca e hulls on a se o
poin s. These wo examples p esen he ambigui y o a con-
ca e hull.
Figu e 5. Conca e hull de e mined by he alpha shape c i e -
ion. Le : Examples o poin clouds ha ep esen lines a e
segmen a ion. Righ : alpha shape esul .
Figu e 6. Possible a ian s o spanning ees ha can be cons uc ed om he poin cloud: k-a y spanning ee ( om le o
igh : k= 1,2,3,4).
EUROPEAN JOURNAL OF REMOTE SENSING 5
desc ibed s eps a e p esen ed in Figu e 7. The esul s
p ojec ed on an ae ial map a e in Figu e 8.
The esul o his p ocess is a se o spanning ees
which ep esen objec s on a oad o in i s icini y.
We ocus p ima ily on he iden i ica ion o ull and
b oken lane ma kings. Ou iden i ica ion p ocess is
used o iden i y ull and b oken lanes and he seg-
men s hey a e composed o . We p oposed a modi i-
ca ion o he egion g owing algo i hm (Figu e 9) o
his pu pose.
Any spanning ee ha con ains a leas one node
wi h he mul iplici y highe han 3 is elimina ed as
oo complex. Such spanning ees ep esen nei he
b oken no ull lane. The spanning ees a e hen
di ided in o wo ca ego ies acco ding o hei leng hs
(possible b oken and ull lane ma king segmen s).
This di ision is done o simpli y he compu a ions
and o ensu e ha he spanning ees ep esen ing
di e en oad lane ma kings a e no connec ed inco -
ec ly. Inside each ca ego y, he i s spanning ee is
selec ed and i s end e ices a e connec ed o all end
e ices o all unp ocessed spanning ees (see
Figu e 9(a)). The bes possible spanning ee (wi h
he lowes dis ance and angle) is chosen o be con-
nec ed o he o iginal ee (Figu e 9(b)). The esul is
a new spanning ee which connec s bo h he o iginal
and he selec ed spanning ee (Figu e 9(c)). This
p ocess con inues un il all possible spanning ees
ha c ea e a se o lane ma kings a e connec ed
(Figu e 9(d)). The p ocess ends when all spanning
ees a e p ocessed.
Lane ma king ep esen a ion
We ocus on he ma hema ical cons uc ion o he
ec o oad lane ma king ep esen a ion om he
spanning ee in his sec ion. As men ioned, he
goal is o ob ain a common ec o map laye such
as ESRI ShapeFile. Such a ep esen a ion is sui able
o any u he analy ic p ocess in equen ly used
geog aphical in o ma ion sys ems.
We choose he solu ion wi h ega d o he inpu
k-a y spanning ee, whe e k¼1;2;3;4.
Le Hi
g
label he inpu e ices and Ti
g
be a se
o he compu ed poin s, d he gi en dis ance o he
en elope poin s.
1-A y ee
Le Hi¼hi
1;hi
2

be he e ex wi h mul iplici y one
(see Figu e 10). Then he esul poin s Ti
1,Ti
2can be
simply exp essed as:
x¼hi
1d
u
jj
u1
y¼hi
2d
u
jj
u2
(1)
whe e he ec o u¼u1;u2
ðÞis he no mal ec o o
he edge Hi;Hiþ1and d he gi en dis ance.
2-A y ee
Le Hibe a e ex wi h mul iplici y wo and Hi1,
Hiþ1 e ices on he adjacen edges (see Figu e 11).
The compu ed poin s Ti
1sa is ies:
d¼Ti
1Q¼
jj
Ti
1P



and
Ti
1P?Hiþ1Hi;Ti
1Q?Hi1Hi!ΔHiTi
1PffiΔHiTi
1Q
We can de i e:
HiP¼
jj
HiQ
jj
¼d
an ffHi1HiHiþ1
jj
2
(2)
Figu e 7. The c ea ion o he spanning ee. Le : alpha
shape; Cen e: alpha shape a e hinning; Righ : esul span-
ning ee (blue line).
Figu e 8. The spanning ee o he g aphs p ojec ed on he
o hopho o. The g een colou ep esen s de ec ed possible lane
segmen s. The yellow colou ep esen s he noise in da a.
6D. PROCHAZKA ET AL.
Hence, he coo dina es o he poin s P,Qcan be
exp essed using Equa ion (1). The esul poin Ti
1
can be w i en as he in e sec ion o wo lines p;q
pe pendicula o he edges Hi1Hi,Hiþ1Hiin poin s
P¼p1;p2
½,Q¼q1;q2
½:
p:nP
1xþnP
2yp1nP
1p2nP
2¼0 (3)
q:nQ
1xþnQ
2yq1nQ
1q2nQ
2¼0 (4)
whe e nP,nQa e no mal ec o s o lines p;q.
Fu he mo e, he symme y poin Ti
2can be simply
de i ed by cen al in e sion wi h he cen e Hi.
3,4-A y ee
Suppose ha he e ex Hiis connec ed wi h he
e ices Hiþ1,Hiþ2,Hiþ3(and Hiþ4 o mul iplici y
ou ). Fi s , he o de o edges has o be de e mined.
Wi hou loss o gene ali y, assume ha HiHiþ1is he
Figu e 10. The de i a ion o he poin s o 1-a y ee.
Figu e 9. The p ocess o lane ype iden i ica ion: (a) i s spanning ee is selec ed and connec ed o all o he s, (b) spanning ee
wi h he lowes angle and dis ance o i s one is ound, (c) wo spanning ees om he p e ious s ep a e connec ed and he
p ocess con inues, (d) all ela ed spanning ees a e connec ed.
EUROPEAN JOURNAL OF REMOTE SENSING 7
ini ial edge. The angle ∢H
i
H
i+1
H
k
can be com-
pu ed by:
cos αðÞ¼ u; ðÞ
u
jj
:
jj (5)
cos αk
ðÞ¼
HiHiþ1;HiHk
ðÞ
HiHiþ1
jj
HiHk
jj
;k
¼iþ2;iþ3; esp:iþ4:(6)
Because o he cosine unc ion p ope ies, edges can
be o de ed in dependence on he size and he sign o
esul s in Equa ion (6). Th ee di e en si ua ions can
be dis inguished (see Figu e 12).
Thus, he p oblem is ans o med o he e alua ion
o h ee (o ou ) couples o edges as in he case o a
2-a y ee (see Equa ions (2, 3, 4)). In he inal s ep,
he poin s a e o de ed and s o ed in a common ile
o ma . The esul map laye p esen ed abo e ae ial
image y is in Figu e 13.
Map laye s’c ea ion
Two map laye s a e c ea ed a e he shape en elope
econs uc ion. The i s laye (polyline ype) con ains
all iden i ied oad lane ma kings whe e each line p o-
ides in o ma ion abou i s ype ( ull o b oken). This
polyline ile is sui able especially o analy ical pu poses.
I p o ides in o ma ion abou he ype and posi ion o
hema kings; he e o e,i canbeused, o exampe o
oad sa e y analysis. The second c ea ed laye con ains
polygons o all econs uc ed lane ma kings. This
polygon ile is use ul mainly o he men ioned in en o y
p ocess. Fo ins ance, i allows o calcula e an app ox-
ima e amoun o pain equi ed o he oad ma king
main enance and o he ela ed asks. We ha e chosen he
ESRI ShapeFile o polygon and polyline s o age; how-
e e , any polygon o polyline o ma can be used. Bo h
iles a e c ea ed using he Shape C Lib a y.
3
Resul s
The e alua ion is based on h ee di e en accu acy
me ics: p ecision, ecall and quali y (Boyko &
Funkhouse , 2011). The g ound u h da a pieces o
he ma ices a e ob ained wi h isual con ol o
images aken du ing he p ocess o poin cloud cap-
u ing. The ma ices a e de ined:
P ecision:
p¼TP
TP þFP
Recall:
¼TP
TP þFN
Quali y:
q¼TP
TP þFN þFP
whe e TP is he numbe o ue posi i es; FP is he
numbe o alse posi i es and FN is he numbe o
alse nega i e esul s.
Figu e 11. The de i a ion o he poin s o 2-a y ee.
3
h p://shapelib.map ools.o g.
8D. PROCHAZKA ET AL.