# Feature Extraction from 3D Point Cloud Data Based on Discrete Curves

Authors: Yi An; Zhuohan Li; Cheng Shao
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Reliable feature extraction from 3D point cloud data is an important problem in many application domains, such as reverse engineering, object recognition, industrial inspection, and autonomous navigation. In this paper, a novel method is proposed for extracting the geometric features from 3D point cloud data based on discrete curves. We extract the discrete curves from 3D point cloud data and research the behaviors of chord lengths, angle variations, and principal curvatures at the geometric features in the discrete curves. Then, the corresponding similarity indicators are defined. Based on the similarity indicators, the geometric features can be extracted from the discrete curves, which are also the geometric features of 3D point cloud data. The threshold values of the similarity indicators are taken from[0,1], which characterize the relative relationship and make the threshold setting easier and more reasonable. The experimental results demonstrate that the proposed method is efficient and reliable.


---

## Body

## 1. Introduction

Rapid developments in 3D rangefinder technology allow us to accurately and conveniently digitize the shape and surface of physical objects [1, 2]. The 3D point cloud data acquired by 3D rangefinders, such as laser scanners, provide the geometric information of the sampling points on the surfaces of physical objects. Nowadays, 3D point cloud data processing techniques have been applied to various domains, including object recognition, industrial inspection, reverse engineering, and autonomous navigation. The geometric features in 3D point cloud data, such as ridges and corners which are composed of the geometric discontinuities, contain the important information of physical objects which frequently require special attention to achieve high accuracy and reliability. Therefore, feature extraction is essential to 3D point cloud data processing, especially to segmentation, reconstruction, and registration.According to differential geometry, the geometric features in 3D point cloud data can be categorized into three types:C0 discontinuities, C1 discontinuities, and C2 discontinuities. At the C0 discontinuities, the positions are discontinuous; at the C1 discontinuities, the positions are continuous, while the normals are discontinuous; at the C2 discontinuities, the positions and normals are continuous, while the curvatures are discontinuous. Due to the importance of the geometric features, many researchers have devoted themselves to developing methods to identify discontinuities and extract geometric features from 3D point cloud data for different purposes in the past 30 years. Fan et al. [3] showed the behaviors of curvatures in jump boundaries (C0), folds (C1), and ridge lines (C2) and used the zero crossings and extrema of curvatures to extract these geometric features from 3D point cloud data. In [4], a curvature consistency algorithm is proposed to improve the estimates of Darboux frames. Then, the orientation discontinuities (C1) are smoothed into local maxima or minima along one of the principal directions, and the depth discontinuities (C0) are identified by considering the angle between the surface normal and the view vector. Similarly, Milroy et al. [5] developed a method to extract the discontinuous points (edge points) from orthogonal cross-section models for segmentation. In order to segment point cloud data, Yang and Lee [6] used a parametric quadric surface approximation to estimate the local surface curvature properties and identified the edge points by a two-step process. Huang and Menq [7] reconstructed a triangle mesh structure from unorganized 3D point cloud data and used the curvature-based border detection to extract the C1 and C2 borders from the triangle meshes. Similar to the method proposed by Huang and Menq [7], Baker [8] and Jiao and Bayyana [9], respectively, proposed their methods to identify the geometric features and the C1, C2 discontinuities from triangle meshes by using the geometric and topological information, such as the dihedral angle, turning angle, angle defect, and ridge valence. Recently, Várady et al. [10] developed a novel method for automatic extraction of surface structures based on discrete Morse theory, which can extract features similar to the C2 discontinuities from triangle meshes.In the most above-mentioned methods, the thresholds of geometric indicators (such as normal vectors and principal curvatures) or error indicators (e.g., the average errors obtained on plane and surface fitting) need to be set for the whole point cloud region to identify the discontinuities and extract the geometric features. Setting good threshold values may be fairly easy, if the user is experienced and has reconstructed several objects with similar shapes from similar data earlier. However, it is a difficult task to find appropriate threshold values for an unfamiliar object with unknown dimensions and noise distribution, and several iterations may be needed until the proper values are found [11]. This is because these indicators have no explicit ranges for the whole point cloud region of an unfamiliar object. To avoid this problem, a new method is proposed to extract the geometric features from the structured 3D point cloud data, which are generated by regular sampling on a certain grid, based on discrete curves in this paper. It differs from the existing methods in that we extract the discrete curves from the structured 3D point cloud data firstly. Then, the chord lengths, angle variations, and curvatures are estimated from the discrete curves, and the corresponding similarity indicators are calculated. Based on the similarity indicators, the geometric features can be extracted from the discrete curves, which are also the geometric features of 3D point cloud data. The threshold value of the similarity indicator is taken from [0,1], which characterizes the relative relationship and makes the threshold setting easier and more reasonable.


## 2. Geometric Properties Estimation from Discrete Curves

In this section, we introduce our method for estimating the geometric properties from discrete curves based on derivative estimation [12]. We develop derivative estimation by defining the derivative of a discrete function at a point, which will be called the discrete derivative, based on the previous research [13–15]. By using the discrete derivatives, classical differential geometry is discretized, and the geometric properties are estimated from discrete curves.


### 2.1. Derivatives of a Discrete Function

In mathematics, a function that is defined only for a set of numbers is called adiscrete function. Generally, a discrete function is denoted by
(1)yi=fd(xi),xi∈{x1,x2,…,xn},
like a series of points {(x1,y1),(x2,y2),…,(xn,yn)}.In calculus, the derivative of a continuous functiony=f(x) at a point equals the slope of the tangent line to the graph of the function at that point. Similarly, the derivative of a discrete function yi=fd(xi) at a given point pk=(xk,yk)(1≤k≤n) can also be thought of as the slope of the tangent line to the graph of the discrete function at pk, which is called the discrete tangent line. We define the discrete tangent line at pk as the straight line y=ax+b which simultaneously meets two requirements: (1) the straight line y=ax+b passes through the point pk=(xk,yk); (2) the sum of the squares of the distances between the straight line y=ax+b and the neighboring points {pj=(xj,yj)∣k-m1≤j≤k+m1} of pk along y-axis is minimal. As shown in Figure 1, if the discrete function yi=fd(xi) is a sampling of a continuous differentiable function y=f(x), the discrete tangent line will approximate to the tangent line at pk when xk-m1, xk-m1+1, …, xk+m1-1, and xk+m1 are very close.Figure 1
Discrete tangent line.According to the definition, the discrete tangent line atpk=(xk,yk) can be obtained by
(2)minf(a,b)=∑j=k-m1k+m1‍(yj-axj-b)2,subjectiontoyk=axk+b.Therefore, the slopea of the discrete tangent line at pk can be solved as
(3)a=∑j=k-m1k+m1(xj-xk)(yj-yk)∑j=k-m1k+m1(xj-xk)2.Definition 1.
Letyi=fd(xi) be a discrete function. The value yk′=fd′(xk) given by
(4)yk′=fd′(xk)=∑j=k-m1k+m1(xj-xk)(yj-yk)∑j=k-m1k+m1(xj-xk)2
is called the derivative of the discrete function yi=fd(xi) at the point pk=(xk,yk)(1≤k≤n), which we will call the discrete derivative for short.If we calculate the discrete derivative at each point on the discrete functionyi=fd(xi), then a new discrete function yi′=fd′(xi), xi∈{x1,x2,…,xn} called the first order discrete derivative function is produced. Its derivative at pk is called the second order discrete derivative of yi=fd(xi) at pk and is given in the same way of Definition 1 as follows:
(5)yk′′=fd′′(xk)=∑j=k-m2k+m2(xj-xk)(yj′-yk′)∑j=k-m2k+m2(xj-xk)2.
By parity of reasoning, the nth order discrete derivative yk(n)=fd(n)(xk) at pk can also be defined.


### 2.2. Geometric Properties of the Discrete Curve

Adiscrete curveαd is composed of a series of discrete points {pi=(xi,yi,zi)∣1≤i≤n}, as shown in Figure 2. In order to estimate the geometric properties from a discrete curve, we must parametrize the discrete curve at first. In our research, the location parameters are assigned by the chord length parametrization method [16]. In this case, the cumulative chord length parameter ti at each point pi is defined as
(6)ti=∑j=1i-1|pj+1-pj|∑j=1n-1|pj+1-pj|(2≤i≤n)
with t1=0. Then, the discrete curve can be thought of as a mapping αd:Id→Rd3 where Id={ti∣1≤i≤n} and Rd3={pi=(xi,yi,zi)∣1≤i≤n}, that is,
(7)pi=αd(ti)=(xd(ti),yd(ti),zd(ti)),ti∈{t1,t2,…,tn},
where the coordinate functions xi=xd(ti), yi=yd(ti), and zi=zd(ti) are regarded as the discrete functions of the chord length parameter ti. Naturally, the definitions of the discrete derivatives can be used for αd(ti), for example, αd′(ti)=(xd′(ti),yd′(ti),zd′(ti)).Figure 2
Discrete curve.In differential geometry, most geometric properties are defined by using the curveα(s) parametrized by arc length s, such as the unit tangent vectort(s)=α˙(s), curvatureκ(s)=|t˙(s)|, and principal normal vectorβ(s)=t˙(s)/κ(s) [17]. (In order to distinguish the derivatives with respect to different parameters, the derivative with respect to the arc length parameter s is denoted by f˙(s), and that with respect to a general parameter t is denoted by f′(t).)  However, these definitions can not be directly used for a discrete curve αd(ti), because it is impossible for the discrete curve to be parametrized by arc length s. In order to apply the geometric properties of the parametrized differential curve to the discrete curve αd(ti), we must deduce the geometric properties of the curve α(t) which is parametrized by a general parameter t at first. Let α(t) be a curve parametrized by a general parameter t. By geometric derivation [12], the geometric properties of the curve α(t), such as the unit tangent vectort(t), curvatureκ(t), and principal normal vectorβ(t), can be calculated by
(8)t(t)=α′(t)|α′(t)|,κ(t)=|t′(t)||α′(t)|,β(t)=t′(t)|α′(t)|κ(t).
Based on the geometric properties (8) of α(t), we give the definition of the geometric properties of the discrete curve αd(ti) by using the discrete derivatives.Definition 2.
Letαd(ti) be a discrete curve parametrized by chord length. We say that (1)
td(ti)=αd′(ti)/|αd′(ti)|is the unit tangent vector of the discrete curveαd(ti);(2)
κd(ti)=|td′(ti)|/|αd′(ti)|is the curvature of the discrete curveαd(ti);(3)
βd(ti)=td′(ti)/(|αd′(ti)|κd(ti))is the principal normal vector of the discrete curveαd(ti).The derivativeαd′(ti) of the discrete vector function αd(ti) is calculated by Definition 1, that is, αd′(ti)=(xd′(ti),yd′(ti),zd′(ti)). Similar to the second order discrete derivative, td′(ti) is then calculated. These geometric properties of the discrete curve are the reliable estimates of the geometric properties of the underlying continuous curve. Therefore, Definition 2 provides a simple and reliable method to estimate the geometric properties from discrete curves. Figure 3 presents the results of the geometric properties estimation from the three discrete spatial curves: the discrete clelia curve, the discrete elliptic helix, and the discrete toric solenoid. As can be observed, our method has very good estimation performance.Geometric properties estimation from three discrete spatial curves. The color bars indicate the curvatures, and the blue and red vectors denote the unit tangent vectors and principal normal vectors, respectively.
(a)
Discrete clelia curve
(b)
Discrete elliptic helix
(c)
Discrete toric solenoid


## 2.1. Derivatives of a Discrete Function

In mathematics, a function that is defined only for a set of numbers is called adiscrete function. Generally, a discrete function is denoted by
(1)yi=fd(xi),xi∈{x1,x2,…,xn},
like a series of points {(x1,y1),(x2,y2),…,(xn,yn)}.In calculus, the derivative of a continuous functiony=f(x) at a point equals the slope of the tangent line to the graph of the function at that point. Similarly, the derivative of a discrete function yi=fd(xi) at a given point pk=(xk,yk)(1≤k≤n) can also be thought of as the slope of the tangent line to the graph of the discrete function at pk, which is called the discrete tangent line. We define the discrete tangent line at pk as the straight line y=ax+b which simultaneously meets two requirements: (1) the straight line y=ax+b passes through the point pk=(xk,yk); (2) the sum of the squares of the distances between the straight line y=ax+b and the neighboring points {pj=(xj,yj)∣k-m1≤j≤k+m1} of pk along y-axis is minimal. As shown in Figure 1, if the discrete function yi=fd(xi) is a sampling of a continuous differentiable function y=f(x), the discrete tangent line will approximate to the tangent line at pk when xk-m1, xk-m1+1, …, xk+m1-1, and xk+m1 are very close.Figure 1
Discrete tangent line.According to the definition, the discrete tangent line atpk=(xk,yk) can be obtained by
(2)minf(a,b)=∑j=k-m1k+m1‍(yj-axj-b)2,subjectiontoyk=axk+b.Therefore, the slopea of the discrete tangent line at pk can be solved as
(3)a=∑j=k-m1k+m1(xj-xk)(yj-yk)∑j=k-m1k+m1(xj-xk)2.Definition 1.
Letyi=fd(xi) be a discrete function. The value yk′=fd′(xk) given by
(4)yk′=fd′(xk)=∑j=k-m1k+m1(xj-xk)(yj-yk)∑j=k-m1k+m1(xj-xk)2
is called the derivative of the discrete function yi=fd(xi) at the point pk=(xk,yk)(1≤k≤n), which we will call the discrete derivative for short.If we calculate the discrete derivative at each point on the discrete functionyi=fd(xi), then a new discrete function yi′=fd′(xi), xi∈{x1,x2,…,xn} called the first order discrete derivative function is produced. Its derivative at pk is called the second order discrete derivative of yi=fd(xi) at pk and is given in the same way of Definition 1 as follows:
(5)yk′′=fd′′(xk)=∑j=k-m2k+m2(xj-xk)(yj′-yk′)∑j=k-m2k+m2(xj-xk)2.
By parity of reasoning, the nth order discrete derivative yk(n)=fd(n)(xk) at pk can also be defined.


## 2.2. Geometric Properties of the Discrete Curve

Adiscrete curveαd is composed of a series of discrete points {pi=(xi,yi,zi)∣1≤i≤n}, as shown in Figure 2. In order to estimate the geometric properties from a discrete curve, we must parametrize the discrete curve at first. In our research, the location parameters are assigned by the chord length parametrization method [16]. In this case, the cumulative chord length parameter ti at each point pi is defined as
(6)ti=∑j=1i-1|pj+1-pj|∑j=1n-1|pj+1-pj|(2≤i≤n)
with t1=0. Then, the discrete curve can be thought of as a mapping αd:Id→Rd3 where Id={ti∣1≤i≤n} and Rd3={pi=(xi,yi,zi)∣1≤i≤n}, that is,
(7)pi=αd(ti)=(xd(ti),yd(ti),zd(ti)),ti∈{t1,t2,…,tn},
where the coordinate functions xi=xd(ti), yi=yd(ti), and zi=zd(ti) are regarded as the discrete functions of the chord length parameter ti. Naturally, the definitions of the discrete derivatives can be used for αd(ti), for example, αd′(ti)=(xd′(ti),yd′(ti),zd′(ti)).Figure 2
Discrete curve.In differential geometry, most geometric properties are defined by using the curveα(s) parametrized by arc length s, such as the unit tangent vectort(s)=α˙(s), curvatureκ(s)=|t˙(s)|, and principal normal vectorβ(s)=t˙(s)/κ(s) [17]. (In order to distinguish the derivatives with respect to different parameters, the derivative with respect to the arc length parameter s is denoted by f˙(s), and that with respect to a general parameter t is denoted by f′(t).)  However, these definitions can not be directly used for a discrete curve αd(ti), because it is impossible for the discrete curve to be parametrized by arc length s. In order to apply the geometric properties of the parametrized differential curve to the discrete curve αd(ti), we must deduce the geometric properties of the curve α(t) which is parametrized by a general parameter t at first. Let α(t) be a curve parametrized by a general parameter t. By geometric derivation [12], the geometric properties of the curve α(t), such as the unit tangent vectort(t), curvatureκ(t), and principal normal vectorβ(t), can be calculated by
(8)t(t)=α′(t)|α′(t)|,κ(t)=|t′(t)||α′(t)|,β(t)=t′(t)|α′(t)|κ(t).
Based on the geometric properties (8) of α(t), we give the definition of the geometric properties of the discrete curve αd(ti) by using the discrete derivatives.Definition 2.
Letαd(ti) be a discrete curve parametrized by chord length. We say that (1)
td(ti)=αd′(ti)/|αd′(ti)|is the unit tangent vector of the discrete curveαd(ti);(2)
κd(ti)=|td′(ti)|/|αd′(ti)|is the curvature of the discrete curveαd(ti);(3)
βd(ti)=td′(ti)/(|αd′(ti)|κd(ti))is the principal normal vector of the discrete curveαd(ti).The derivativeαd′(ti) of the discrete vector function αd(ti) is calculated by Definition 1, that is, αd′(ti)=(xd′(ti),yd′(ti),zd′(ti)). Similar to the second order discrete derivative, td′(ti) is then calculated. These geometric properties of the discrete curve are the reliable estimates of the geometric properties of the underlying continuous curve. Therefore, Definition 2 provides a simple and reliable method to estimate the geometric properties from discrete curves. Figure 3 presents the results of the geometric properties estimation from the three discrete spatial curves: the discrete clelia curve, the discrete elliptic helix, and the discrete toric solenoid. As can be observed, our method has very good estimation performance.Geometric properties estimation from three discrete spatial curves. The color bars indicate the curvatures, and the blue and red vectors denote the unit tangent vectors and principal normal vectors, respectively.
(a)
Discrete clelia curve
(b)
Discrete elliptic helix
(c)
Discrete toric solenoid


## 3. Behaviors of the Geometric Properties at the Geometric Discontinuities

According to differential geometry, the geometric discontinuities of continuous curves can be categorized into three types:C0, C1, and C2 discontinuities. At the C0 discontinuity, the position is discontinuous; at the C1 discontinuity, the position is continuous, while the tangent vector is discontinuous; at the C2 discontinuity, the position and tangent vector are continuous, while the curvature is discontinuous. As we know, the discrete curve can be thought of as the sampling of a continuous curve. Therefore, the discrete curve also includes the geometric discontinuities sometimes. Now, we will study the behaviors of the geometric properties of the discrete curve at the geometric discontinuities, such as the chord length Δt=|ti+1-ti|, the angle variation of the unit tangent vector Δtd=arccos(td(ti+1)·td(ti)), and the curvature κd.Figure4 shows the chord length, angle variation, and curvature estimated by our method at the C0 discontinuity without noise. As can be observed, the chord length exhibits an isolated extremum, and the angle variation and curvature both exhibit two extrema. In order to study the C0 discontinuity further, the zero-mean Gaussian noise N(0,σ2) is added to all position coordinates. The standard derivation σ is set to 50%  dav where dav is the average distance between two neighboring points. Figure 5 shows the chord length, angle variation, and curvature at the C0 discontinuity with noise. As can be observed, the geometric properties exhibit the similar behaviors as those without noise, and the chord length is the least affected by noise, since the chord length is the lowest order geometric property.C
0 discontinuity without noise.
(a)
C
0 discontinuity
(b)
Chord length atC0 discontinuity
(c)
Angle variation atC0 discontinuity
(d)
Curvature atC0 discontinuityC
0 discontinuity with noise.
(a)
C
0 discontinuity
(b)
Chord length atC0 discontinuity
(c)
Angle variation atC0 discontinuity
(d)
Curvature atC0 discontinuityFigures6, 7, 8, 9, 10, and 11 show the chord lengths, angle variations, and curvatures estimated by our method at the three types of C1 discontinuities, which are formed by two straight lines (Type I, as shown in Figures 6 and 7), two convex curves (Type II, as shown in Figures 8 and 9), and two concave curves (Type III, as shown in Figures 10 and 11), respectively, without and with noise. As can be observed, the chord lengths change gradually and do not have the sudden change. That is because the position is continuous at the C1 discontinuity. From the experimental results, we can also find that the angle variations and curvatures both undergo an isolated extremum. The noise has some effect on the angle variations and curvatures, but the angle variations and curvatures still have an obvious change which can be detected.C
1 discontinuity (Type I) without noise.
(a)
C
1 discontinuity
(b)
Chord length atC1 discontinuity
(c)
Angle variation atC1 discontinuity
(d)
Curvature atC1 discontinuityC
1 discontinuity (Type I) with noise.
(a)
C
1 discontinuity
(b)
Chord length atC1 discontinuity
(c)
Angle variation atC1 discontinuity
(d)
Curvature atC1 discontinuityC
1 discontinuity (Type II) without noise.
(a)
C
1 discontinuity
(b)
Chord length atC1 discontinuity
(c)
Angle variation atC1 discontinuity
(d)
Curvature atC1 discontinuityC
1 discontinuity (Type II) with noise.
(a)
C
1 discontinuity
(b)
Chord length atC1 discontinuity
(c)
Angle variation atC1 discontinuity
(d)
Curvature atC1 discontinuityC
1 discontinuity (Type III) without noise.
(a)
C
1 discontinuity
(b)
Chord length atC1 discontinuity
(c)
Angle variation atC1 discontinuity
(d)
Curvature atC1 discontinuityC
1 discontinuity (Type III) with noise.
(a)
C
1 discontinuity
(b)
Chord length atC1 discontinuity
(c)
Angle variation atC1 discontinuity
(d)
Curvature atC1 discontinuityFigure12 shows the chord length, angle variation, and curvature estimated by our method at the C2 discontinuity without noise. As can be observed, the chord length and angle variation change gradually, while the curvature undergoes a jump. That is because the position and tangent vector are continuous, while the curvature is discontinuous at the C2 discontinuity. Figure 13 shows the chord length, angle variation, and curvature estimated by our method at the C2 discontinuity with noise. From the experimental results, we can find that the C2 discontinuity has been drowned out by noise, and the curvature variation at the C2 discontinuity can not be detected. That is because the curvature is the second order geometric property, which is affected by noise more easily.C
2 discontinuity without noise.
(a)
C
2 discontinuity
(b)
Chord length atC2 discontinuity
(c)
Angle variation atC2 discontinuity
(d)
Curvature atC2 discontinuityC
2 discontinuity with noise.
(a)
C
2 discontinuity
(b)
Chord length atC2 discontinuity
(c)
Angle variation atC2 discontinuity
(d)
Curvature atC2 discontinuityFrom the above-mentioned analysis, we can conclude that at theC0 discontinuity, the chord length has the obvious change and exhibits an isolated extremum; at the C1 discontinuity, the angle variation of the unit tangent vector has the obvious change and exhibits an isolated extremum; at the C2 discontinuity, the curvature has the obvious change and exhibits a jump. These behaviors of the geometric properties will enable us to identify the C0, C1, and C2 discontinuities from the discrete curves effectively and reliably.


## 4. Similarity Indicator

In order to extract the discontinuities more effectively, we will study the variations of the geometric properties in the different neighborhoods further. Letp0 be a given point on the discrete curve αd, as shown in Figure 14. V1={pj∣-n1≤j≤n1} and V2={pj∣-n2≤j≤n2} are two neighborhoods of p0 on αd, where V2 is larger than V1, that is, n2>n1. The cumulative chord length tj, unit tangent vector tdj, and curvature κdj at the point pj can be calculated by our method. The variations Δt1 and Δt2 of the cumulative chord length t in V1 and V2 are, respectively, calculated by
(9)Δt1=∑j=-n1n1-1‍|tj+1-tj|,Δt2=∑j=-n2n2-1‍|tj+1-tj|.
The variations Δtd1 and Δtd2 of the unit tangent vector td in V1 and V2 are, respectively, calculated by
(10)Δtd1=∑j=-n1n1-1‍arccos(tdj+1·tdj),Δtd2=∑j=-n2n2-1‍arccos(tdj+1·tdj).
The variations Δκd1 and Δκd2 of the curvature κd in V1 and V2 are, respectively, calculated by
(11)Δκd1=∑j=-n1n1-1‍|κdj+1-κdj|,Δκd2=∑j=-n2n2-1‍|κdj+1-κdj|.Figure 14
Similarity indicator definition.Based on (9)–(11), the similarity indicators of the cumulative chord length t, unit tangent vector td, and curvature κd at p0 are defined as follows.Definition 3.
Letp0 be a given point on the discrete curve αd. We say that (1)
sc=Δt1/Δt2 is the similarity indicator of the cumulative chord length t at p0;(2)
sa=Δtd1/Δtd2 is the similarity indicator of the unit tangent vector td at p0;(3)
sκ=Δκd1/Δκd2 is the similarity indicator of the curvature κd at p0.At a point far away from theC0 discontinuity, the cumulative chord length t changes gradually, since the point has the continuous position. Therefore, we can think that the variation |tj+1-tj| between two neighboring points is a constant c, which makes sc=Δt1/Δt2≈2n1c/2n2c≈n1/n2. At a point near the C0 discontinuity, the cumulative chord length t changes suddenly, and Δt1 becomes larger, which makes sc=Δt1/Δt2≫n1/n2. Figure 15 shows the similarity indicator sc of the cumulative chord length t at the C0 discontinuity without noise, where n1=2 and n2=8. As can be observed, the similarity indicator sc at the point far away from the C0 discontinuity is approximately equal to n1/n2=0.25(sc≈0.25), while the similarity indicator sc at the point near the C0 discontinuity is much greater than n1/n2=0.25 (sc≫0.25), which is in accord with our theoretical analysis. Figure 16 shows the similarity indicator sc at the C0 discontinuity with noise. As can be observed, the similarity indicator sc exhibits the same behavior as that without noise. From the experimental result, we can also find that the similarity indicator sc is robust to noise.Similarity indicatorsc of the cumulative chord length at the C0 discontinuity without noise.
(a)
C
0 discontinuity
(b)
Similarity indicator:scSimilarity indicatorsc of the cumulative chord length at the C0 discontinuity with noise.
(a)
C
0 discontinuity
(b)
Similarity indicator:scSimilarly, at a point far away from theC1 discontinuity, the unit tangent vector td changes gradually, which makes sa=Δtd1/Δtd2≈2n1c/2n2c≈n1/n2. At a point near the C1 discontinuity, the unit tangent vector td changes suddenly, and Δtd1 becomes larger, which makes sa=Δtd1/Δtd2≫n1/n2. Figures 17 and 18 show the similarity indicators sa of the unit tangent vector td at the C1 discontinuities without and with noise, where n1=2 and n2=8. As can be observed, far away from the C1 discontinuity sa≈0.25, while near the C1 discontinuity sa≫0.25.Similarity indicatorsa of the unit tangent vector at the C1 discontinuity without noise.
(a)
C
1 discontinuity
(b)
Similarity indicator:saSimilarity indicatorsa of the unit tangent vector at the C1 discontinuity with noise.
(a)
C
1 discontinuity
(b)
Similarity indicator:saIn the same principal, at a point far away from theC2 discontinuity, the curvature κd changes gradually, since the point has the continuous curvature, which makes sκ=Δκd1/Δκd2≈2n1c/2n2c≈n1/n2. At a point near the C2 discontinuity, the curvature κd changes suddenly, and Δκd1 becomes larger, which makes sκ=Δκd1/Δκd2≫n1/n2. Figure 19 shows the similarity indicator sκ of the curvature κd at the C2 discontinuity without noise, where n1=2 and n2=8. As can be observed, far away from the C2 discontinuity sκ≈0.25, while near the C2 discontinuity sκ≫0.25. Figure 20 shows the similarity indicator sκ at the C2 discontinuity with noise. From the experimental result, we can find that the similarity indicator sκ is sensitive to noise, which makes it difficult for us to detect the C2 discontinuity.Similarity indicatorsκ of the curvature at the C2 discontinuity without noise.
(a)
C
2 discontinuity
(b)
Similarity indicator:sκSimilarity indicatorsκ of the curvature at the C2 discontinuity with noise.
(a)
C
2 discontinuity
(b)
Similarity indicator:sκFrom the above-mentioned analysis, we can find that the similarity indicatorssc, sa, and sκ are approximately equal to n1/n2 at the points far away from the C0, C1, and C2 discontinuities, while the similarity indicators sc, sa, and sκ are much greater than n1/n2 at the points near the C0, C1, and C2 discontinuities. This conduces to identify the areas near the discontinuities. Another advantage of the similarity indicators is that their thresholds are taken from [0,1], because Δt1≤Δt2, Δtd1≤Δtd2, and Δκd1≤Δκd2, which characterises the relative relationship and makes the threshold setting easier and more reasonable.


## 5. Discontinuity Identification from the Discrete Curves

In order to extract the geometric features from 3D point cloud data, we will identify theC0, C1, and C2 discontinuities (the C0, C1, and C2 discontinuous points) from the discrete curves, respectively, by using a two-step method. The first step is to identify the points near the C0, C1, and C2 discontinuities, which are called the candidate points. Then, the C0, C1, and C2 discontinuous points are extracted from the candidate points, respectively, in the second step.


### 5.1. Identifying theC0 Discontinuous Points

As mentioned in Section4, the similarity indicators sc at the points near the C0 discontinuity are much larger. Therefore, the candidate points of the C0 discontinuous points are identified as the points at which the similarity indicators sc are larger than a threshold value. In this paper, the threshold value of the similarity indicator sc is set to 0.5. Then, we will extract the C0 discontinuous points from their candidate points. As analyzed in Section 3, the chord length exhibits an isolated extremum at the C0 discontinuity. Therefore, the C0 discontinuous points are identified as the candidate points whose chord lengths Δt are the isolated extrema.The above-mentioned method can identify theC0 discontinuous points reliably in most of the time, but sometimes the discrete curves will be seriously polluted by noise, which will make some points have small extrema of chord lengths. Obviously, these small extrema of chord lengths are caused by noise, and the corresponding points are not the real C0 discontinuous points. Therefore, in order to reduce the noise influence and improve the identification reliability, we will remove these points by using the statistical method. First, the distribution of the chord lengths Δt is calculated by the statistical histogram for the whole discrete curve. As we know, the number of the C0 continuous points is much greater than that of the C0 discontinuous points. Therefore, if the small extrema of chord lengths have higher frequencies, the corresponding points are the C0 continuous points and will be removed. Figure 21 shows the candidate points (green points) and the C0 discontinuous points (blue points) identified by our method.C
0 discontinuous point identification.
(a)
C
0 discontinuity without noise
(b)
C
0 discontinuity with noise


### 5.2. Identifying theC1 Discontinuous Points

In order to facilitate theC1 discontinuity identification, we remove the identified C0 discontinuous points from the discrete curve, and then the discrete curve is segmented into several sections by the removed points. As shown in Figure 21, the discrete curve is divided into two sections by the C0 discontinuous points. Every section of discrete curve has its own geometrical characteristic. Therefore, we should identify the C1 discontinuous points from each section of discrete curve individually.As shown in Figures17 and 18, the similarity indicators sa at the points near the C1 discontinuity are much larger. Therefore, the candidate points of the C1 discontinuous points are identified as the points at which the similarity indicators sa are larger than a threshold value. In this paper, the threshold value of the similarity indicator sa is set to 0.5. As analyzed in Section 3, the angle variation of the unit tangent vector exhibits an isolated extremum at the C1 discontinuity. Therefore, the C1 discontinuous points are identified as the candidate points whose angle variations Δtd are the isolated extrema. Similar to the C0 discontinuity identification, we also use the statistical method to remove the points, which have the small extrema of angle variations caused by noise, from the identified C1 discontinuous points to improve the identification reliability. Figure 22 shows the candidate points (green points) and the C1 discontinuous points (blue points) identified by our method.C
1 discontinuous point identification.
(a)
C
1 discontinuity without noise
(b)
C
1 discontinuity with noise


### 5.3. Identifying theC2 Discontinuous Points

In order to facilitate theC2 discontinuity identification, we will remove the identified C1 discontinuous points from the discrete curve successively. Then, the discrete curve will be segmented into more small sections by the removed C1 discontinuous points, and we will identify the C2 discontinuous points from each small section of discrete curve individually.As shown in Figures19 and 20, the similarity indicators sκ at the points near the C2 discontinuity are much larger. Therefore, the candidate points of the C2 discontinuous points are identified as the points at which the similarity indicators sκ are larger than a threshold value. In this paper, the threshold value of the similarity indicator sκ is set to 0.5. As analyzed in Section 3, the curvature exhibits a jump at the C2 discontinuity; that is, the curvature variation Δκd=|κd(ti+1)-κd(ti)| exhibits an isolated extremum at the C2 discontinuity. Therefore, the C2 discontinuous points are identified as the candidate points whose curvature variations Δκd are the isolated extrema. Similar to the C0 and C1 discontinuity identification, we also use the statistical method to remove the points, which have the small extrema of curvature variations caused by noise, from the identified C2 discontinuous points to improve the identification reliability. Figure 23 shows the candidate points (green points) and the C2 discontinuous points (blue points) identified by our method.C
2 discontinuous point identification.
(a)
C
2 discontinuity without noise
(b)
C
2 discontinuity with noise


## 5.1. Identifying theC0 Discontinuous Points

As mentioned in Section4, the similarity indicators sc at the points near the C0 discontinuity are much larger. Therefore, the candidate points of the C0 discontinuous points are identified as the points at which the similarity indicators sc are larger than a threshold value. In this paper, the threshold value of the similarity indicator sc is set to 0.5. Then, we will extract the C0 discontinuous points from their candidate points. As analyzed in Section 3, the chord length exhibits an isolated extremum at the C0 discontinuity. Therefore, the C0 discontinuous points are identified as the candidate points whose chord lengths Δt are the isolated extrema.The above-mentioned method can identify theC0 discontinuous points reliably in most of the time, but sometimes the discrete curves will be seriously polluted by noise, which will make some points have small extrema of chord lengths. Obviously, these small extrema of chord lengths are caused by noise, and the corresponding points are not the real C0 discontinuous points. Therefore, in order to reduce the noise influence and improve the identification reliability, we will remove these points by using the statistical method. First, the distribution of the chord lengths Δt is calculated by the statistical histogram for the whole discrete curve. As we know, the number of the C0 continuous points is much greater than that of the C0 discontinuous points. Therefore, if the small extrema of chord lengths have higher frequencies, the corresponding points are the C0 continuous points and will be removed. Figure 21 shows the candidate points (green points) and the C0 discontinuous points (blue points) identified by our method.C
0 discontinuous point identification.
(a)
C
0 discontinuity without noise
(b)
C
0 discontinuity with noise


## 5.2. Identifying theC1 Discontinuous Points

In order to facilitate theC1 discontinuity identification, we remove the identified C0 discontinuous points from the discrete curve, and then the discrete curve is segmented into several sections by the removed points. As shown in Figure 21, the discrete curve is divided into two sections by the C0 discontinuous points. Every section of discrete curve has its own geometrical characteristic. Therefore, we should identify the C1 discontinuous points from each section of discrete curve individually.As shown in Figures17 and 18, the similarity indicators sa at the points near the C1 discontinuity are much larger. Therefore, the candidate points of the C1 discontinuous points are identified as the points at which the similarity indicators sa are larger than a threshold value. In this paper, the threshold value of the similarity indicator sa is set to 0.5. As analyzed in Section 3, the angle variation of the unit tangent vector exhibits an isolated extremum at the C1 discontinuity. Therefore, the C1 discontinuous points are identified as the candidate points whose angle variations Δtd are the isolated extrema. Similar to the C0 discontinuity identification, we also use the statistical method to remove the points, which have the small extrema of angle variations caused by noise, from the identified C1 discontinuous points to improve the identification reliability. Figure 22 shows the candidate points (green points) and the C1 discontinuous points (blue points) identified by our method.C
1 discontinuous point identification.
(a)
C
1 discontinuity without noise
(b)
C
1 discontinuity with noise


## 5.3. Identifying theC2 Discontinuous Points

In order to facilitate theC2 discontinuity identification, we will remove the identified C1 discontinuous points from the discrete curve successively. Then, the discrete curve will be segmented into more small sections by the removed C1 discontinuous points, and we will identify the C2 discontinuous points from each small section of discrete curve individually.As shown in Figures19 and 20, the similarity indicators sκ at the points near the C2 discontinuity are much larger. Therefore, the candidate points of the C2 discontinuous points are identified as the points at which the similarity indicators sκ are larger than a threshold value. In this paper, the threshold value of the similarity indicator sκ is set to 0.5. As analyzed in Section 3, the curvature exhibits a jump at the C2 discontinuity; that is, the curvature variation Δκd=|κd(ti+1)-κd(ti)| exhibits an isolated extremum at the C2 discontinuity. Therefore, the C2 discontinuous points are identified as the candidate points whose curvature variations Δκd are the isolated extrema. Similar to the C0 and C1 discontinuity identification, we also use the statistical method to remove the points, which have the small extrema of curvature variations caused by noise, from the identified C2 discontinuous points to improve the identification reliability. Figure 23 shows the candidate points (green points) and the C2 discontinuous points (blue points) identified by our method.C
2 discontinuous point identification.
(a)
C
2 discontinuity without noise
(b)
C
2 discontinuity with noise


## 6. Feature Extraction from 3D Point Cloud Data

As we know, the geometric features can be categorized into three types:C0, C1, and C2 discontinuities according to the differential geometry. In general, the discontinuities for object surfaces are composed of piecewise smooth curves. However, for 3D point cloud data, the discontinuities are composed of discrete data points, that is, the C0, C1, and C2 discontinuous points.From the structured 3D point cloud data, which are obtained by regular sampling on a certain grid, four groups of discrete curves: the horizontal discrete curvesαdh(ti) (purple), the vertical discrete curves αdv(ti) (blue), the down-sloping discrete curves αdd(ti) (brown), and the up-sloping discrete curves αdu(ti) (green) can be extracted along four directions, as shown in Figure 24. In order to extract the discontinuous points from the structured 3D point cloud data, the C0, C1, and C2 discontinuous points should be extracted from each group of discrete curves by using our method at first. Then, four groups of identified C0, C1, and C2 discontinuous points are merged together according to the type of geometric discontinuity by logical OR operation. These merged C0, C1, and C2 discontinuous points are exactly the different types of discontinuous points of the 3D point cloud data, that is, the geometric features of the 3D point cloud data.Figure 24
Discrete curves extracted from the 3D point cloud data of a human face model: (a) 3D point cloud data of a human face model; (b) four groups of discrete curves: the horizontal discrete curvesαdh(ti) (purple), the vertical discrete curves αdv(ti) (blue), the down-sloping discrete curves αdd(ti) (brown), and the up-sloping discrete curves αdu(ti) (green).


## 7. Experimental Results

In order to show the performance of our method, we experiment with both synthetic and real 3D point cloud data. The synthetic 3D point cloud data used for the experiments are generated by regular sampling a geometrical model which includesC0, C1, and C2 discontinuities, as shown in Figure 25(a). Figures 25(c)–25(f) shows the discontinuous points extracted from four groups of discrete curves: the horizontal discrete curves (Figure 25(c)), the vertical discrete curves (Figure 25(d)), the down-sloping discrete curves (Figure 25(e)), and the up-sloping discrete curves (Figure 25(f)) along four directions. Figure 25(b) shows the merging result. As can be observed, the geometric features (the C0, C1, and C2 discontinuous points) are accurately extracted from the 3D point cloud data of the model. The real 3D point cloud data used for the experiments are acquired by scanning the mouse (70mm×60mm×130mm), blade (65mm×40mm×130mm), terracotta warrior model (55mm×25mm×65mm), and gear (60mm×25mm×45mm) with the 3D laser scanner. Figure 26 shows the feature extraction results from the 3D point cloud data of the mouse (Figure 26(a)), blade (Figure 26(b)), terracotta warrior (Figure 26(c)), and gear (Figure 26(d)). As can be observed, the geometric features are reliably extracted from the real 3D point cloud data. From the experiments, we can find that the extraction results obtained by our method are consistent with the actual situation, which demonstrates that our method is efficient and reliable.Extracting the discontinuous points from four groups of discrete curves. The blue, red, and green points indicate theC0, C1, and C2 discontinuous points, respectively.
(a)
3D point could data of a model
(b)
Extracted discontinuous points
(c)
Horizontal discontinuous points
(d)
Vertical discontinuous points
(e)
Down-sloping discontinuous points
(f)
Up-sloping discontinuous pointsMerging and thinning results.
(a)
Mouse
(b)
Blade
(c)
Terracotta warrior
(d)
Gear


## 8. Conclusion

In this paper, we propose a novel method for extracting the geometric features (theC0, C1, and C2 discontinuities) from 3D point cloud data based on discrete curves. By using the discrete curves extracted from 3D point cloud data, the chord lengths, angle variations, curvatures, and similarity indicators are calculated, and the discontinuous points are identified from the discrete curves. After the merging process, we can get the geometric features for 3D point cloud data. In this method, the similarity indicators make the threshold setting easier and more reasonable and improve the performance of feature extraction. From the experimental results, we can conclude that the proposed feature extraction method is efficient and reliable.



---

*Source: 290740-2013-04-03.xml*