In e na ional Jou nal o
Geo-In o ma ion
A icle
Sha p Fea u e De ec ion as a Use ul Tool in
Sma Manu ac u ing
Jana P ochazko a 1,* , Da id P ocházka 2and Ja omí Landa 2
1Facul y o Mechanical Enginee ing, B no Uni e si y o Technology, 616 69 B no, Czech Republic
2Facul y o Business and Economics, Mendel Uni e si y in B no, 613 00 B no, Czech Republic;
[email p o ec ed] (D.P.); ja omi [email p o ec ed] (J.L.)
*Co espondence: p [email p o ec ed].cz
Recei ed: 12 May 2020; Accep ed: 27 June 2020; Published: 30 June 2020


Abs ac :
Indus y 4.0 comp ises a wide spec um o de elopmen al p ocesses wi hin he
managemen o manu ac u ing and chain p oduc ion. P esen ly, he e is a huge e o o au oma e
manu ac u ing and ha e au oma ic con ol o he p oduc ion. This in en ion leads o he inc eased
need o high-quali y me hods o digi iza ion and objec econs uc ion, especially in he a ea o
e e se enginee ing. Commonly used scanning so wa e based on well-known algo i hms can
co ec ly p ocess smoo h objec s. Ne e heless, hey a e usually no applicable o complex-shaped
models wi h sha p ea u es. The numbe o he poin s on he edges is ex emely limi ed due o he
p inciple o lase scanning and some imes also low scanning esolu ion. The e o e, a co ec edge
econs uc ion p oblem occu s. The same p oblem appea s in many o he lase scanning applica ions,
i.e., in he ep esen a ion o he buildings om ai bo ne lase scans o 3D ci y models. We ocus on a
me hod o p ese a ion and econs uc ion o sha p ea u es. We p o ide a de ailed desc ip ion o all
h ee key s eps: poin cloud segmen a ion, edge de ec ion, and co ec B-spline edge ep esen a ion.
The ea u e de ec ion algo i hm is based on he con en ional egion-g owing me hod and we de i e
he op imal inpu alue o cu a u e h eshold using loga i hmic leas squa e eg ession. Subsequen
edge ep esen a ion s ands on he i e a i e algo i hm o B-spline app oxima ion whe e we compu e
he weigh ed asymme ic e o using he golden a io. The se ies o examples indica es ha ou
me hod gi es be e o compa able esul s o o he me hods.
Keywo ds:
edge de ec ion; poin cloud; e e se enginee ing; spline; indus y 4.0; 3D scanning;
3D model
MSC: 65D10
1. In oduc ion
Indus y 4.0 is he end owa ds au oma ion and da a exchange in manu ac u ing echnologies
and p ocesses. Indus y 4.0 ac o ies ha e machines which a e augmen ed wi h wi eless connec i i y
and senso s, connec ed o a sys em ha can isualize he en i e p oduc ion line and make decisions on
i s own. Sma manu ac u ing is a b oad ca ego y o manu ac u ing ha employs compu e -in eg a ed
manu ac u ing, high le els o adap abili y and apid design changes, digi al in o ma ion echnology,
and mo e lexible echnical wo k o ce aining [1,2].
Ou wo k co e s he pa o au oma ion in manu ac u ing and e e se enginee ing o design
changes. The widesp ead a ailabili y o cheap comme cial dep h senso s o mul i-came a se ups leads
o hei common usage in manu ac u ing enginee ing, especially in apid p oduc de elopmen [
3
].
The e o e, he poin cloud has become he egula ype o he ep esen a ion used e.g., in e e se
ISPRS In . J. Geo-In . 2020,9, 422; doi:10.3390/ijgi9070422 www.mdpi.com/jou nal/ijgi
ISPRS In . J. Geo-In . 2020,9, 422 2 o 18
enginee ing (RE) and apid p o o yping (RP). The p ecision, scanning speed and a ie y o p ocessing
algo i hms c ea e sui able condi ions o i s common usage.
A key p oblem in he RE/RP in eg a ion, as men ioned in [
4
], is he ans o ma ion o a se o
dense poin s ob ained in he RE p ocess o a i ing model ha can be used. In Figu e 1, he e e se
enginee ing p ocess is desc ibed.
Figu e 1. Re e se enginee ing p ocess.
Usually, 3D scanne s a e p o ided wi h so wa e ha c ea es a physical objec in he wo-phase
se up: econs uc ing CAD model om he scanned poin da a, and subsequen STL model ou pu .
Howe e , he implemen ed me hods a e usually su icien only o simple and smoo h objec s.
Mo e complex objec s wi h holes, sha p edges o co ne s o en equi e p io knowledge o how
o edi he scanned da a. The da a pos -p ocessing is ime-consuming and can po en ially lead o
e o s. We p esen an algo i hm ha au oma ically de ec s sha p ea u es in a bi a y poin cloud da a.
Ou algo i hm is based on a modi ied egion-g owing me hod. The inpu alue o he algo i hm is only
one pa ame e — he no mal ec o h eshold
θN
(op imal s a alue and he desc ip ion is p esen ed
in Sec ion 2.1). Region-g owing algo i hm elimina es he plana poin s and he emaining poin s a e
p obably edge poin s.
Be o e he inal manu ac u ing p ocess o 3D p in ing, a co ec model is essen ial o STL
gene a ion [
5
] and subsequen slicing [
4
,
6
]. Figu e 2shows he common p oblema ic pa (jagged and
inaccu a e bo de s) ha occu s equen ly. To sol e his p oblem, in Sec ion 3.2 we p opose he no el
edge ep esen a ion based on B-spline app oxima ion. The asymme ic e o e alua ion is based on
bell unc ion wi h weigh ing using golden a io [
7
] o imp o e he edge ep esen a ion o he models.
Mo eo e , ou B-spline app oxima ion is also su icien o di ec STL slicing om poin clouds
ha ex ac s he sec ional con ou s (cu es) di ec ly wi hou model econs uc ion. The o e iew o
hese me hods is e.g., in [
8
]. The p esen ed B-spline app oxima ion can be used wi hou limi a ions in
his slicing p ocedu e because i ob iously i e a i ely minimizes he shape-e o o he laye cu es.
Figu e 2. P oblema ic pa s on he edges.
P io Wo k
Poin cloud segmen a ion and classi ica ion plays a key ole in poin cloud p ocessing in RE/RP
usage. Segmen a ion is he p ocess o g ouping poin clouds in o mul iple homogeneous egions wi h
simila p ope ies whe eas classi ica ion is he s ep ha labels hese egions. Segmen a ion me hods a e
di ided in o many ca ego ies and he choice o he me hods depends on he a ea o in e es , sampling
ISPRS In . J. Geo-In . 2020,9, 422 3 o 18
densi y, da a quali y and explici s uc u e o poin cloud. We can use he ca ego iza ion desc ibed
in [9,10]: egion-g owing, edge-based me hods, model i ing, and hyb id me hods.
Mos o he me hods s a wi h egion g owing ha was pu posed by Besl [11] o segmen a ion
o images. The egion-g owing algo i hm was la e expanded in o 3D in wo di e en e sions:
unseeded [
12
] and seeded [
13
]. Region g owing is applied in plen y o di e en applica ions,
e.g., ex ac ing ea u es and plana su aces om 3D ou c op poin clouds [
14
], su ace segmen a ion,
and edge ea u e lines ex ac ion om ac u ed agmen s o elics [
15
] o u ban en i onmen
modelling [16] and also 3D ci y modelling (li e a u e su ey e.g., in [17]).
Region g owing is equen ly imp o ed. Fo example, Dema is e al. [
18
] de ec he closed sha p
edges using he egion g owing wi h no mals gi en by building a local mesh and leas -squa es planes
h ough he nea es neighbo hood poin s. The co ec edge de ec ion in p o ided by g aph heo y
(minimum spanning ee). In [
16
], egion-g owing s ep is pe o med on an oc ee-based oxelized
inpu poin cloud ep esen a ion o ex ac majo segmen s.
The edge-based me hods a e usually used wi h poin clouds ans o med in o he ange
images [
19
]. Using he high-le el ea u es (scan line g ouping echnique) as segmen a ion p imi i es
ins ead o indi idual pixels ensu e he high compu a ional speed. Howe e , his edge de ec ion is no
applicable o noisy da a.
Model i ing me hods assume ha a su ace can be desc ibed as a composi ion o simple,
canonical geome ic shapes (wa e igh econs uc ion). Elemen a y me hods use RANSAC o obus ly
ind planes, sphe es, cylinde s, cones, and o ii [
20
]. Howe e , he e occu s a p oblem wi h noise,
any ine-g ained de ails a e likely o be ea ed as noise wi h he p imi i e p io , i hey a e unable o
be ep esen ed as a union o smalle p imi i es (a su ey is desc ibed in [
21
]). The pa ial solu ion is
hyb id me hods ha employ p imi i es wi h o he p io [22].
Region-g owing, edge-based me hods and model i ing do no need p e-p ocessing, bu he e
exis o he segmen a ion me hods based on p e-p ocessing. These algo i hms a e capable o
econs uc ing da a incomple eness [
23
,
24
] o cons uc a iangula mesh o gi en poin cloud
[25–27].
A e wa ds, he o med mesh can be p ocessed using e.g., he disc e e di e en ial geome y whe e
local ex eme o he su ace de ec he edge lines [
25
] o algeb aic me hods based on bi a ia e
polynomials [
27
]. We mus no e ha some o hese me hods wo k wi h he machine lea ning
me hods [28].
A e he poin cloud segmen a ion and classi ica ion, we need a co ec model ep esen a ion and
essella ion (usually STL) wi h subsequen slicing o ex ac laye -based addi i e manu ac u ing [
29
].
The e exis a ious app oaches ha combine di e en echnologies. T adi ional STL app oach is
desc ibed e.g., in [
30
]. B-spline o NURBS su aces a e used equen ly, e.g., au ho s in [
31
,
32
] p esen s
di ec slicing om NURBS wi hou STL. Also, B-Rep model composed o planes, sphe es, cylinde s and
cones om a 3D mesh is i ing o slicing [
33
,
34
]. Some o he au ho s omi he model econs uc ion
and make he di ec gene a ion o sec ional con ou . Fo example, au ho s in [
35
] employ he cu e
skele on o he model o slice h ough he su ace mesh edges. B-spline cu e i ing o he laye s
whe e he cu e cu a u e is de e mined by a ci cle i ing p ocedu e is p esen ed in [8].
The de elopmen o neu al ne wo ks and deep lea ning also ouches he esea ch in poin cloud
analysis. Some me hods a e p omising bu he e is s ill no one-size- i s-all app oach. Re iews o he
me hods a e co e ed e.g., in [36–38].
P esen li e a u e con ains mos o he ecen ly known p inciples. Main scien i ic con ibu ion is
in hei imp o emen s and applica ions. Fo example, wo k [
39
] (published 2020) uses B-spline
ep esen a ion and no mal compu a ion using no mal cu a u e di ec ly compu ed by pa ial
de i a i es o he su ace. The omi ing o he p e-de ined h eshold alue is he main idea in [
40
]
(published 2019). The au ho s sugges he composi ion o spa ial FFT-based il e ing and bounda y
de ec ion, which oge he allow o di ec gene a ion o low noise essella ed su aces om poin cloud
da a. Re [
41
] p esen s he ea u e sensi i e poin cloud simpli ica ion ha is based on insensi i e
suppo ec o eg ession.
ISPRS In . J. Geo-In . 2020,9, 422 4 o 18
The ad an ages o he well-known me hods ( egion-g owing o PCA) a e ob ious— obus ness,
compu ed easiness, s able algo i hms. Because o ha , we chose hese classical me hods and ou main
idea was (1) he simpli ica ion and au oma ic se ing o inpu alues (desc ibed in Sec ion 2.1) (2) ind
op imal e o e alua ion in B-spline ep esen a ion ha is sui able o enginee ing objec s. The p oblem
o e o compu a ion is desc ibed in Sec ion 2.2 and we p oposed asymme ic weigh ing based on
golden a ion.
2. Me hods and Ma e ials
The common indus ial enginee ing componen s consis o la , smoo h o cu ed su aces.
A measu able di e ence in su ace no mals o cu a u e is ela i ely small on mos o he model
su aces. Con a y o ha , in he neighbo hood o a sha p ea u e, such as a sha p edge o co ne ,
he e is a signi ican change in he su ace no mal and cu a u e. Thus, i we emo e all poin s o he
la , smoo h o cu ed su aces, he emaining ones a e he poin s on he sha p ea u es. Wi h his idea
in mind, we build ou me hod, simila ly o [
42
], on he analysis o he eigen alues o he co a iance
ma ix o e e y poin ’s
k
-nea es neighbo . We use egion g owing no o ind plana su aces o
egula models [43] bu o emo e he poin s wi h low cu a u e (Sec ion 2.1).
The impo an inpu alues o egion g owing a e no mal and cu a u e h esholds. Thei se ing
subs an ially changes he segmen a ion esul s, bu hei choice is unin ui i e and di icul especially
o beginne s. We ind he geome ic co ela ion be ween hese wo alues and we compu e he
op imal ini ial alue ha is applicable in he case o egula enginee ing objec s. This is desc ibed
in he ollowing subsec ions. This app oach is obus o he noise and is sui able o subsequen
B-spline app oxima ion.
The B-spline app oxima ion was chosen due o i s good p ope ies and well-known compu a ion.
The i e a i e p ocess ensu es su icien quali y. The e o compu a ion is based on he asymme ically
weigh ed dis ance (asymme ic dis ance is p esen ed in [
44
]) bu in ou case, he weigh is desc ibed
wi h he golden a io. The asymme ic measu emen eplaces he ou lie s and p o ec s he cu e om
he zig-zag e ec . This app oach is desc ibed in Sec ion 2.2. Compu ed B-spline cu e can ep esen
edges in poin clouds. Mo eo e , desc ibed B-spline app oxima ion is also possible o use in he
me hods o di ec slicing.
2.1. Edge Poin s De ec ion
The p ocessing o a gi en poin cloud s a s wi h he egion-g owing segmen a ion.
Su ace no mal compu a ion is based on P incipal Componen Analysis (PCA) [
45
] ha uses an
o hogonal ans o ma ion o con e a se o obse a ions o possibly co ela ed a iables in o a se o
alues o linea ly unco ela ed a iables. The desc ip ion is in Sec ion 2.1.1.
Edges can be also classi ied by Gauss mapping [
42
,
46
,
47
]. The poin no mal ec o s a e p ojec ed
on he Gauss sphe e and subsequen clus e ing dis inguish he poin ype (co ne , edge, plana ).
This me hod is ime-consuming so ha we use he egion g owing.
2.1.1. PCA—No mal Es ima ion
The i s s ep in he PCA algo i hm is he compu a ion o he co a iance ma ix
C
o each poin
P
in he poin cloud.
C=1
k
k
∑
i=1
(Pi−¯
P)·(Pi−¯
P)T, (1)
whe e
¯
P
is he cen oid o
k
-nea es neighbo hood poin s
Pi
,
i=
1, 2,
. . . k
o a poin
P
. Eigen alues
(
λ0
,
λ1
,
λ2
) and eigen ec o s (
~
1
,
~
2
,
~
3
) o his ma ix de ines he co a iance ellipsoid. We dis inguish
be ween hese h ee cases:
1. (λ0≤λ1≤λ2)∧(λ1≈λ2)
2. (λ0≤λ1≤λ2)∧(λ0≈λ1)
ISPRS In . J. Geo-In . 2020,9, 422 5 o 18
3. (λ0≤λ1≤λ2)∧(λ0≈λ1≈λ2).
These ypes o co a iance ellipsoids de ine he neighbo hood o he gi en poin (Figu e 3a–c).
In he case o an obla e ellipsoid (
(λ0≤λ1≤λ2)∧(λ1≈λ2)
), he poin is ob iously on an almos
plana a ea and he eigen ec o co esponding wi h he smalles eigen alue is poin no mal.
λ0
λ1
λ2
(a)
λ2
λ0λ1
(b)
λ2
λ0
λ1
(c)
Figu e 3. Types o he co a iance ellipsoid (a) obla e (b) p ola e (c) simila o a sphe e.
2.1.2. Region G owing—Ini ial No mal Th eshold Value h θN
Region-g owing segmen a ion algo i hm usually equi es inpu pa ame e s: minimal and
maximal clus e size,
k
-nea es neighbo poin s, no mal h eshold
h θN
and cu a u e h eshold
h θC
. Value
θN
is he angle be ween wo-poin no mals and
θC
is cu a u e. They s ongly a ec he
segmen a ion esul s and geome ically, hey a e igh ly connec ed. The se ing o he ini ial alues is
unin ui i e and no use - iendly so ha we ocus on he op imal au oma ic es ima ion o θN.
Figu e 4a shows he de ini ion o he cu a u e
θ
o he cu e
l
a he poin
P1
. In he limi as
∆ →0, we ob ain:
θ=lim
∆ →0
∆α
∆ (2)
In he case o a poin cloud, we conside he pa ame e
∆
as he minimal dis ance
dmin
o he line
be ween wo adjacen poin s (Figu e 4b). The cu a u e θCis compu ed by
θC=θN
dmin
. (3)
l
Δα
Δα
Δ
P1
n1n2
2
1
P2
(a)
dmin
θN
θN
P1
n1n2
2
1
P2
(b)
Figu e 4. (a) Cu a u e o he cu e, (b) cu a u e es ima ion in a poin cloud.
The e o e, he egion-g owing segmen a ion can be con olled only by one pa ame e — he no mal
ec o h eshold h θN. The ollowing pa desc ibes he p ocess o he ideal ini ial alue o h θN.
We p epa ed a se o es ing poin clouds
Mi
,
i=
1, 2,
. . .
, 6 o co e he spec um o di e en
shapes om simple one o he complex ones (Figu e 5). These poin cloud da a we e acqui ed by ATOS

ISPRS In . J. Geo-In . 2020,9, 422 6 o 18
Compac Scan 2M.We se a es ing ange o maximal alues o no mal ec o h eshold
h θN=
1,
. . .
, 15.
I means ha he segmen a ion emo es all poin s in clus e s whe e he no mal ec o h eshold is
lowe han
h θN
. Le
nou
be a numbe o he emo ed poin s and
nin
be se e al poin s in a poin cloud.
We applied he egion-g owing algo i hm on ou da a-se s wi h pa ame e s
h θN
and we
compu ed he numbe o emo ed poin s nou . The pe cen age o emaining poin s is de ined as:
pe cN=nou
nin
·100. (4)
We no ice ha he dependence be ween
h θN
and
pe cN
has loga i hmic p og ess, he loga i hmic
eg ession is he bes choice o compu e he dependence:
h θN=b1ln(pe cN) + b0,b0,b1∈R. (5)
The g aphs and inal esul s a e in Sec ion 3.1.
(
a
) (
b
) (
c
) (
d
) (
e
)
( )
Figu e 5. Tes ing poin clouds: (a)M l, (b)M2, (c)M3, (d)M4, (e)M5, ( )M6.
2.2. B-Spline Edge Rep esen a ion
B-spline i ing belongs o he a o i e ools o p ocessing o a se o uno ganized, possibly noisy
da a poin s in compu e g aphics, compu e ision and CAD/CAM. The main ad an age o B-spline
app oxima ion is based on he well-known o mula ion o B-spline [48]:
C(u) =
n
∑
i=0
Bi,p(u)Pi, (6)
whe e
Bi,p(u)
is he B-spline basis unc ion o deg ee
p
wi h con ol poin s
Pi
. The pa ame e
u
is
om he nonpe iodic and nonuni o m kno in e al
u=<u0
,
u1
,
. . .
,
un+p+1>
. We se
u0=
0 and
un+p+1=1.
Le
{Qk}m
k=0
be he se o inpu poin s. The i ing algo i hm sea ch o con ol poin s
Pi
,
kno ec o
u
o he spline cu e de ined in Equa ion
(6)
and also he pa ame e s
b
u={b
uk}m
k=0
ha sa is ied he equa ion:
Qk=
n
∑
i=0
Bi,p(b
uk)Pi(7)
and C(u0) = C(0) = Q0,C(un+p+1) = C(1) = Qm.
Fi s , we compu e he ini ial cu e shape. The au ho s in [
44
] wo k wi h he ini ial ci cle (cen e
o he ci cle is a he mean o he poin cloud, he adius o he maximal dis ance o a poin o cen e )
o an ellipse which he main axes a e compu ed by PCA. We s a wi h equen ly used cho dal and
cen ipe al me hod. The cho dal me hod compu es he pa ame e s as:
b
u0=0; b
um=1; b
uk=b
uk−1+|Qk−Qk−1|
d(8)
whe e
d=∑m
k=1|Qk−Qk−1|
. Cen ipe al me hod is simila , we only add squa e oo o he line leng h.
Cen ipe al me hod is mo e ele an in case ha he da a akes sha p u ns.
ISPRS In . J. Geo-In . 2020,9, 422 7 o 18
Secondly, we se he kno ec o
u
wi h condi ion ha e e y kno span con ains a leas one
b
uk
.
The in e nal kno spans a e de ined by [49]:
i= loo (jd),α=jd −i,
up+j= (1−α)b
ui−1+αb
ui,j=1, . . . , n−p(9)
and unc ion loo is he la ges in ege such i≤jd.
Subsequen ly, coo dina es o he con ol poin s
Pi
a e app oxima ed by he s anda d echnique o
linea leas -squa es i ing [48]. We minimize he unc ion:
=|
m−1
∑
k=1
Qk−C(b
uk)|2(10)
We can desc ibe he solu ion in ma ix o m ( he sys em o n−1×n−1 equa ions) as:
(BTB)P=R(11)
whe e ma ix
B
B ep esen s he B-spline unc ion o deg ee
p
e alua ed o all
b
uk
,
k=
1,
. . .
,
n−
1.
Ma ix Pa e wan ed con ol poin s and ec o Ris he ec o o n−1 poin s:
R=


∑m−1
k=1B1,p(b
uk)Rk
.
.
.
∑m−1
k=1Bn−1,p(b
uk)Rk


(12)
and
Rk=Qk−B0,p(b
uk)Q0−Bn,p(b
uk)Qm,k=1, . . . , m−1. (13)
The Equa ion
(11)
can be sol ed by Gaussian elimina ion because he ma ix
BTB
is posi i e
de ini e and well-condi ioned.
We mus deal wi h he main p oblem h oughou he i e a ion p ocess: a choice o he dis ance
measu e o e o de e mina ion. The o mula ion o he p oblem is simple, we ha e uno ganized
da a poin s (in ou case possible edge poin s) wi h non-uni o m dis ibu ion wi h conside able noise.
This p oblem can be o mula ed as a nonlinea op imiza ion p oblem. Gi en inpu poin s
{Qk}m
k=0
,
we wan o compu e con ol poin s Pi ha minimize a gene al objec i e unc ion [44]:
=1
2
n
∑
k=1
d2(P(u),Qk) + λ s(14)
d2(P(u)
,
Qk)
is he dis ance o poin
Qk
o he cu e
P( )
,
s
is egula iza ion e m o ensu e a smoo h
cu e,
λ
is weigh o
s
. In ou algo i hm, we wo k wi h he asymme ic weigh ed poin dis ance
measu e. We in oduce a no el e o e m in Equa ion
(15)
ha is based on golden a ion. I ensu es
ha he inne poin s (on he same side as a no mal ec o ) ha e lesse in luence han he ou e . This
ad an age elimina es he p oblema ic ou lie s and imp o es he shape o he cu e (Figu e 6).
ou lie s
Figu e 6. The example o he ou lie s.
ISPRS In . J. Geo-In . 2020,9, 422 8 o 18
The dis ance
dk
is he signed dis ance o he poin
Qk
and he closes poin on he compu ed
B-spline cu e.
dk
is posi i e i he poin
Qk
is on he same side as no mal
nk
—see Figu e 7a. This e o
e m is:
wϕ(dk) =









1
ϕ+ϕ−d2
k
σ2 o dk<0
1 o dk≥0
(15)
k=
0, 1, 2
. . .
,
m
, whe e
σ
de ines he wid h o he ansi ion o he weigh ing unc ion wi h espec o
he signed dis ance. The alue ϕis he golden a io 1.61803398875. The objec i e unc ion has a o m:
ϕ=
m
∑
k=0
wϕ(dk)d2
k, (16)
The weigh ing unc ion wϕ(dk)and objec i e unc ion ϕa e modelled in Figu e 7b.
C(k)
nk
Qk
(a)
-1.5 -1 -0.5 0 0.5 1
d
0
0.5
1
1.5
2
(b)
Figu e 7.
(
a
) No mal ec o is on he opposi e side o he poin
Qk
, dis ance
dk
is nega i e, (
b
) he
g aphs o he unc ions wϕ( ed line) and ϕ(blue line).
The asymme ic e o de ec s he pa s whe e he cu e accu acy is insu icien . The imp o emen
is done by local kno inse ion. We know he pa ame e
uk
o he nea es cu e poin
C(uk)
o e e y
Qk
. The e o e, we inse all kno s
uk
in he insu icien pa s and ecompu e he cu e using kno
inse ion scheme. I uk∈<uk,uk+1), hen he new con ol poin s Pia e:
Pi=βiPi+ (1−βi)Pi−1(17)
whe e
βi=




uk−ui
ui+p−ui o k−p+1≤i≤k
1 o i≤k−p
0 o i≥k+1
(18)
In he pa s, whe e he e o is high, we add he new kno in he alue o he nea es cu e poin .
We es ed he p oposed imp o emen on he se o poin clouds
C1
,
C2
,
C3
,
C4
and
C5
. The es esul s
and ho ough compa ison a e in Sec ion 3.
3. Resul s and Discussion
This sec ion con ains wo main pa s: Es ima ion o no mal h eshold pa ame e and B-spline
i ing wi h a no el asymme ic e o . In he i s pa , we made a se ies o es ing objec s— om
almos plana ones o he complex ones wi h holes. We p oceeded hese models wi h egion-g owing
ISPRS In . J. Geo-In . 2020,9, 422 9 o 18
algo i hm and using ou p oposed me hod (Sec ion 2.1.2) we es ima e he op imal alue o he no mal
h eshold. This alue can be se as a uni e sal inpu h eshold alue. The inexpe ienced end-use s o
he edge de ec ion algo i hm do no need any complex manual on how o con ol he esul s.
The second s ep con ains a B-spline i ing algo i hm o he edge ep esen a ion. The inpu o his
pa a e poin s de ec ed in he i s s ep. The asymme ic e o wi h he golden a io (Equa ion
(15)
)
is used in he i e a ion p ocess as desc ibed in he p e ious sec ion. On he se o di e en cu es
(smoo h, complex) we show he esul s and we make a compa ison wi h me hod [44].
Fea u e de ec ion algo i hm was implemen ed in Mic oso Visual S udio C++ wi h Poin Cloud
Lib a y 1.8.0. The B-spline app oxima ion was p og ammed in MATLAB R2018a. The poin cloud
da a-se s we e ob ained by ATOS Compac Scan 2M. Tes ing was p o ided on he MacBook P o,
2.6 GHz In el Co e i7, 16 GB 1600 MHz DDR3, NVIDIA GeFo ce GT 750M 2048 MB, SSD.
3.1. Es ima ion o No mal Th eshold h θN
The i s analyses examines he impac o pa ame e
h θN
. The se o es ing poin clouds
Mi,i∈ h1, 6iis in Figu e 5. Le sin be se e al poin s in he gi en poin cloud (Table 1).
Table 1. The poin clouds wi h numbe o poin s sin.
Model M1M2M3M4M5M6
sin 87,848 67,394 195,815 123,112 103,534 90,209
We applied he egion-g owing algo i hm on ou da a-se s wi h he ini ial pa ame e s
h θN∈N
,
h θN=
1,
. . .
, 15 and we ind he numbe o emo ed poin s
nou
. The pe cen age o emaining poin s
is compu ed by:
pe cN=nou
nin
·100. (19)
Table A1 p o ides he esul s ob ained by he analysis o di e en alues
h θN
. We can see ha
he alue o pe cNis igh ly ela ed o he complexi y o he model.
Table A2 (middle column) p esen s poin cha s o he alues
h θN
and
pe cN
. We can see ha
independen ly on he model complexi y, i has he loga i hmic p og ess. The e o e, he dependence
be ween
h θN
and
pe cN
can be gene ally desc ibed wi h loga i hmic eg ession using Equa ion
(5)
.
The inal equa ions and g aphs a e in Table A2 (las column).
We wan o de e mine he bes possible inpu alue
h θN
ha is applicable o common poin
clouds o he enginee ing models. We s a wi h he a e age eg ession equa ion ( he a e age o he
equa ions in Table A2):
θST ≈R(x) = −2.45 ·ln(x) + 6.06. (20)
The op imal alue o
pe c
is se empi ically as 1–6%. The e o e, he alues o
h θN
a e in in e al
hR(1),R(6)i. Ob iously, we ge :
R(1) = −2.45 ·ln(1) + 6.06 ≤θST ≤ −2.45 ·ln(6) + 6.06 =R(6)
6.06 ≤θST ≤1.67. (21)
The a i hme ic mean o
R(
1
)
and
R(
6
)
is
θop =
3.86 is se as a de aul ini ial alue in he p oposed
ea u e de ec ion algo i hm. In he case o insu icien esul s, his alue can be changed inc emen ally.
Table 2shows he segmen a ion esul s o models
Mi
,
i=
1, 2,
. . .
, 6 using he de aul ini ial alue
θop =
3.86. I is ob ious ha he esul s a e su icien and his alue helps inexpe ienced use s o
s a segmen a ion wi hou any p io knowledge o cu a u e o no mal h eshold. By applying he
inc emen al change o his alue, he esul s a e imp o ed o ob ain su icien quali y o ac ual use.
ISPRS In . J. Geo-In . 2020,9, 422 16 o 18
Table A3.
Compa ison o B-spline cu e app oxima ion o es ing clouds, CP is numbe o con ol
poin s, wϕis a e age weigh ed e o .
C1
CP 4 10 20
wϕ[mm] 2.35 1.15 0.83
C2
CP 4 10 20 40 80
wϕ[mm] 14.01 5.54 2.02 1.25 0.99
C3
CP 20 40 80
wϕ[mm] 3.96 0.96 0.85
C4
CP 80 100 160
wϕ[mm] 0.41 0.37 0.27
C5
CP 10 40 80
wϕ[mm] 2.19 0.67 0.33
Re e ences
1.
Da is, J.; Edga , T.; Po e , J.; Be naden, J.; Sa li, M. Sma manu ac u ing, manu ac u ing in elligence and
demand-dynamic pe o mance. Compu . Chem. Eng. 2012,47, 145–156. [C ossRe ]
2. Vaidya, S.; Ambad, P.; Bhosle, S. Indus y 4.0—A Glimpse. P ocedia Manu . 2018,20, 233–238. [C ossRe ]
3.
Chua, C.K.; Leong, K.F.; Lim, C.S. Rapid P o o yping: P inciples and Applica ions. In Rapid P o o yping:
P inciples and Applica ionse; Wo ld Scien i ic Publishing: Singapo e, 2010.
4.
Qiu, Y.; Zhou, X.; Qian, X. Di ec slicing o cloud da a wi h gua an eed opology o apid p o o yping. In . J.
Ad . Manu . Technol. 2011,53, 255–265. [C ossRe ]
5.
Li esu, M.; Elle o, S.; Ma inez, J.; Le eb e, S.; A ene, M. F om 3D models o 3D p in s: an o e iew o he
p ocessing pipeline. Compu . G aph. Fo um 2017,36, 1–24. [C ossRe ]
6. Choi, S.-H.; Sama edam, S. Modelling and op imisa ion o apid p o o yping. Compu . Ind. 2002,47, 39–53.
[C ossRe ]
7.
Sen, S.K.; Aga wal, R.P. Golden a io in science, as andom sequence sou ce, i s compu a ion and beyond.
J. Compu . Ma h. Appl. 2008,56, 469–498. [C ossRe ]
8.
Ja id ad, R.; Pou moayed, A.R. Con ou cu e econs uc ion om cloud da a o apid p o o yping.
Robo . Compu . In eg . Manu . 2011,27, 397–404. [C ossRe ]

ISPRS In . J. Geo-In . 2020,9, 422 17 o 18
9.
G illi, E.; Menna, F.; Remondino, F. A e iew o poin clouds segmen a ion and classi ica ion algo i hms.
In . A ch. Pho og amm. Remo e Sens. Spa . In . Sci. 2017,XLII-2/W3, 339–344. [C ossRe ]
10.
Nguyen, A.; Le, B. 3D poin cloud segmen a ion: A su ey. In P oceedings o he 6 h IEEE Con e ence on
Robo ics, Au oma ion and Mecha onics (RAM), Manila, Philippine, 12–15 No embe 2013; pp. 225–230.
11.
Besl, P.J.; Jain, R.C. Segmen a ion h ough Va iable-O de Su ace Fi ing. IEEE T ans. Pa e n Anal. Mach.
In ell. A ch. 1988,10, 167–192. [C ossRe ]
12.
Naha , M.; Ali Sujan Rahman, M. Imp o emen o Single Seeded Region G owing Algo i hm on Image
Segmen a ion. Glob. J. Compu . Sci. Technol. 2018,18, 15–22.
13.
Adams, R.; Bischo , L. Seeded Region G owing. IEEE T ans. Pa e n Anal. Mach. In ell. A ch.
1994
,6, 641–647.
[C ossRe ]
14. Wang, X.; Zoua, L.; Shena, X.; Rena, Y.; Qina, Y. A egion-g owing app oach o au oma ic ou c op ac u e
ex ac ion om a h ee-dimensional poin cloud. Compu . Geosci. 2017,99, 100–106. [C ossRe ]
15.
Xu, J.; Zhou, M.; Wu, Z.; Shui, W.; Ali, S. Robus su ace segmen a ion and edge ea u e lines ex ac ion om
ac u ed agmen s o elics. J. Compu . Des. Eng. 2015,2, 79–87. [C ossRe ]
16.
Vo, A.V.; T uong-Hong, L.; Lae e , D.F.; Be olo o, M. Oc ee-based egion g owing o poin cloud
segmen a ion. ISPRS J. Pho og amm. Remo e Sens. 2015,104, 88–100. [C ossRe ]
17.
Ni, H.; Lin, X.; Ning, X.; Zhang, J. Edge De ec ion and Fea u e Line T acing in 3D-Poin Clouds by Analyzing
Geome ic P ope ies. Remo e Sens. 2016,8, 710. [C ossRe ]
18.
Dema is, K.; Vande s ae en, D.; Volodine, T.; Roose, D. De ec ion o closed sha p edges in poin clouds
using no mal es ima ion and g aph heo y. Compu . Aided Des. 2007,39, 267–283.
19.
Jiang, X.Y.; Bunke, H.; Meie , U. Fas ange image segmen a ion using high-le el segmen a ion p imi i es.
In P oceedings o he Thi d IEEE Wo kshop on Applica ions o Compu e Vision, Sa aso a, FL, USA,
2–4 Decembe 1996; pp. 83–88.
20.
Schnabel, R.; Wahl, R.; Klein, R. E icen Ransac o poin cloud shape de ec ion. Compu . G aph. Fo um
2007
,
26, 214–226. [C ossRe ]
21.
Be ge , M.; Tagliasacchi, A.; Se e sky, L.M.; Alliez, P.; Guennebaud, G.; Le ine, J.A.; Sil a, C.T. A Su ey o
Su ace Recons uc ion om Poin Clouds. Compu . G aph Fo um 2016,36, 301–329. [C ossRe ]
22.
La a ge, F.; Alliez, P. Su ace econs uc ion h ough poin se s uc u ing. In Compu e G aphics Fo um;
Benes, B., Chen, M., Eds.; Wiley: New Yo k, NY, USA, 2013; pp. 225–234.
23.
Wang, M.; Ju, M.; Fan, Y.; Guo, S.; Liao, M.; Yang, H.; Komu a, T. 3D Incomple e Poin Cloud Su aces
Recons uc ion Wi h Segmen a ion and Fea u e-Enhancemen . IEEE Access
2019
,7, 15272–15281. [C ossRe ]
24.
Yin, K.; Huang, H.; Zhang, H.; Gong, M.; Cohen-O , D.; Chen, B. Mo i : in e ac i e su ace econs uc ion
om incomple e poin clouds wi h cu e-d i en opology and geome y con ol. ACM T ans. G aph.
2014
,
33, 202. [C ossRe ]
25.
Hildeb and , K.; Pol hie , K.; Wa de zky, M. Smoo h ea u es lines on su ace meshes. In Eu og aphics
Symposium on Geome y P ocessing; Desb un, M., Po mann, H., Eds.; Eu og aphics Associa ion: Ai e-la-Ville,
Swi ze land, 2005; pp. 85–90.
26.
Oh ake, Y.; Belyae , A. Au oma ic de ec ion o geodesic idges and a ines on polygonal su ace. J. Th ee
Dimens. Images 2001,15, 127–132.
27.
S ylianou, G.; Fa in, G. C es lines ex ac ion om 3D iangula ed meshes. In Hie a chical and Geome ical
Me hods in Scien i ic Visualiza ion; Fa in, G., Hamann, B., Hagen, H., Eds.; Sp inge : Be lin, Ge many, 2003;
pp. 69–81.
28.
Too ooni, S.; Dsouza, A.; Dono an, R.; Rao, P.K.; Kong, Z.; Bo gesen, P. Classi ying he Dimensional Va ia ion
in Addi i e Manu ac u ed Pa s F om Lase -Scanned Th ee-Dimensional Poin Cloud Da a Using Machine
Lea ning App oaches. J. Manu . Sci. Eng. 2017,139, 142–149.
29.
Benie e, R.; Subsol, G.; Gesqui e, G.; Le B e on, F.; Puech, W. A comp ehensi e p ocess o e e se enginee ing
om 3D meshes o CAD models. Compu . Aided Des. 2013,45, 1382–1393. [C ossRe ]
30.
Zhang, Z.; Sanjay, J. An imp o ed slicing algo i hm wi h e icien con ou cons uc ion using STL iles. In . J.
Ad . Manu . Technol. 2015,80, 1347–1362. [C ossRe ]
31.
Ma, W.; Bu , W.C.; He, P. NURBS-based adap i e slicing o e icien apid p o o yping. Compu . Aided Des.
2004,36, 1309–1325. [C ossRe ]
32.
O opallo, W.; Piegl Les, A.; Rosen, P.; Rajab, K. Gene a ing poin clouds o slicing ee- o m objec s o 3-D
p in ing. Compu . Aided Des. Appl. 2017,14, 242–249. [C ossRe ]
ISPRS In . J. Geo-In . 2020,9, 422 18 o 18
33.
Shi, K.; Cai, C.; Wu, Z.; Yong, J. Slicing and suppo s uc u e gene a ion o 3D p in ing di ec ly on B- ep
models. Vis. Compu . Ind. Biomed. A 2019,2, 3. [C ossRe ]
34.
Zhao, G.; Ma, G.; Feng, J.; Xiao, W. Nonplana slicing and pa h gene a ion me hods o obo ic addi i e
manu ac u ing. In . J. Ad . Manu . Technol. 2018,96, 3149. [C ossRe ]
35.
K esslein, J.; Haghighi, P.; Jaejong, P.; Ramna h, S.; Su adha , A.; Shah, J.J. Au oma ed c oss-sec ional shape
eco e y o 3D b anching s uc u es om poin cloud. J. Compu . Des. Eng. 2018,5, 368–378. [C ossRe ]
36.
Liu, W.; Sun, J.; Li, W.; Hu, T.; Wang, P. Deep Lea ning on Poin Clouds and I s Applica ion: A Su ey.
Senso s 2019,19, 4188. [C ossRe ] [PubMed]
37.
G i i hs, D.; Boehm, J. A Re iew on Deep Lea ning Techniques o 3D Sensed Da a Classi ica ion. Remo e Sens.
2019,11, 1499. [C ossRe ]
38.
Guo, Y.; Wang, H.; Hu, Q.; Liu, H.; Liu, L.; Bennamoun, M. Deep Lea ning o 3D Poin Clouds: A Su ey.
a Xi 2019, a Xi :abs/1912.12033.
39.
Lee, D.; Quan, I.; Wu, C.; Wu, J.; Tami , D.; Rishe, N. Op imizing B-Spline Su ace Recons uc ion o Sha p
Fea u e P ese a ion. In P oceedings o he 10 h Annual Compu ing and Communica ion Wo kshop and
Con e ence (CCWC), Las Vegas, NV, USA, 6–8 Janua y 2020; pp. 359–364.
40.
Mineo, C.; Pie ce, S.G.; Summan, R. No el algo i hms o 3D su ace poin cloud bounda y de ec ion and
edge econs uc ion. J. Compu . Des. Eng. 2019,6, 81–91. [C ossRe ]
41.
Ma ko ic, V.; Jako ije ic, Z.; Miljko ic, Z. Fea u e sensi i e h ee-dimensional poin cloud simpli ica ion
using suppo ec o eg ession. Tech. Gaz. 2019,27, 985–994.
42.
Bazazian, D.; Casas, J.R.; Ruiz-Hidalgo, J. Fas and Robus Edge Ex ac ion in Uno ganized Poin Clouds.
In P oceedings o he In e na ional Con e ence on Digi al Image Compu ing: Techniques and Applica ions
(DICTA), Adelaide, Aus alia, 23–25 No embe 2015; pp. 1–8.
43.
Wang, Y.X.; Wang, J.; Chen, X.; Chu, T.; Liu, M.; Yang, T. Fea u e Su ace Ex ac ion and Recons uc ion
om Indus ial Componen s Using Mul is ep Segmen a ion and Op imiza ion. Remo e Sens.
2018
,10, 1073.
[C ossRe ]
44.
Mö wald, T.; Balze , J.; Vincze, V. Modeling connec ed egions in a bi a y plana poin clouds by obus
B-spline app oxima ion. Robo . Au on. Sys . 2008,76, 141–151. [C ossRe ]
45. Jolli e, I.T. P incipal Componen Analysis; Sp inge : New Yo k, NY, USA, 1986; p. 487.
46.
Bancho , T.; Ga ney, T.; McC o y, C. Cups o he Gauss Map. In Resea ch No es in Ma hema ics;
Pi man: London, UK, 1982.
47.
Webe , C.; Hahmann, S.; Hagen, H. Me hods o ea u e de ec ion in poin cloud. In Visualiza ion
o La ge and Uns uc u ed Da a Se s–IRTG Wo kshop; Middel, A., Schele , I., Hagen, H., Eds.;
Schloss Dags uhl–Leibniz-Zen um ue In o ma ik: Bodega Bay, CA, USA, 2010; pp. 90–99.
48. Piegl, L.; Tille , W. The NURBS Book; Sp inge : New Yo k, NY, USA, 1997.
49. de Boo , C. A P ac ical Guide o Splines; Sp inge : New Yo k, NY, USA, 2001.
50. Blake, A.; Isa d, M. The Ac i e Con ou s; Sp inge : New Yo k, NY, USA, 1998.
51.
Wang, W.; Po mann, H.; Liu, Y. Fi ing B-spline cu es o poin clouds by cu a u e-based squa ed dis ance
minimiza ion. ACM T ans. G aph. 2006,25, 214–238. [C ossRe ]
c
2020 by he au ho s. Licensee MDPI, Basel, Swi ze land. This a icle is an open access
a icle dis ibu ed unde he e ms and condi ions o he C ea i e Commons A ibu ion
(CC BY) license (h p://c ea i ecommons.o g/licenses/by/4.0/).