A self-adaptive segmentation method for a point cloud

Abstract

The segmentation of a point cloud is one of the key technologies for three-dimensional reconstruction, and the segmentation from three-dimensional views can facilitate reverse engineering. In this paper, we propose a self-adaptive segmentation algorithm, which can address challenges related to the region-growing algorithm, such as inconsistent or excessive segmentation. Our algorithm consists of two main steps: automatic selection of seed points according to extracted features and segmentation of the points using an improved region-growing algorithm. The benefits of our approach are the ability to select seed points without user intervention and the reduction of the influence of noise. We demonstrate the robustness and effectiveness of our algorithm on different point cloud models and the results show that the segmentation accuracy rate achieves 96%.

1 Introduction

With the increasing use of computer graphics technology in conjunction with agricultural knowledge, research on the morphological structure and physiological function of objects is entering a digital and visual stage. Digital content creation using real-world data has gained a great deal of attention over the past decades [1]. Segmentation is necessary in reverse engineering, where models are reconstructed from points acquired on the surface of the object by laser scanners. Additionally, agricultural and forestry plants have different structures with respect to their leaves, branches, and fruits. Thus, different parts of the models need to adopt different modeling methods to guarantee the precision and effectivity of the reconstruction. Segmenting the point cloud of different structures effectively is one of the key technologies for high-precision reconstruction of reverse engineering and is also useful in other applications, such as three-dimensional (3D) city modeling, feature recognition, geometry compression, and industrial site modeling [10]. We propose an algorithm for segmenting an unorganized set of points of a 3D object and dividing the points into several proper subsets with similar attributes, which mainly include distance, density, normal, and curvature.

2 Related work

In current reverse engineering, a point cloud is typically divided into regions with similar topological structures to facilitate surface reconstruction. Existing segmentation methods mainly include edge-based segmentation, surface-based segmentation, and a combination of these two methods.

In edge-based segmentation, the boundary line connected by boundary points is the fundamental base for the segmentation. Wang et al. [24] proposed a segmentation algorithm for point cloud models of buildings. Their algorithm extracts buildings according to the boundary of the point cloud models. The boundary corresponds to discontinuities in depth or height, and therefore distinguishes one building from other buildings and objects on the ground. However, this method is very sensitive to noise. Dai et al. [7] developed a segmentation method for a point cloud distributed in the principal direction of tree models. The algorithm calculates the principal curvature and direction of the points from the tree point cloud models and uses this information to define an energy function. It then determines the segmentation of the leaves and branches according to the defined energy function and obtains the final segmentation results by separating the leaves and branches. The algorithm has a high operating efficiency, but its application is limited to tree models. Guillaume et al. [13] calculated the curvature tensor-based triangle mesh and used it to segment points into surface patches. Then, they adjusted the boundaries to obtain the segmentation of patch edges.

Surface-based segmentation uses local surface attributes as a similarity measure and merges the points with similar attributes [21]. It can also provide information with abstract expressions, which is useful for expression and analysis [17]. This method usually performs better than edge-based segmentation. Richtsfeld et al. [22] proposed a segmentation method using radial reflection to estimate model shapes. The algorithm mainly extracts the model shapes of surfaces. Rabbani et al. [21] proposed a constraint-based segmentation algorithm that can extract smooth regions in point cloud models. However, its segmentation results depend heavily on the parameter settings. Yamauchi et al. [25] proposed mesh segmentation with a mean shift algorithm. It is based on normal clustering using an adaptive mean shift algorithm and performs segmentation using the region-growing algorithm. The authors algorithm was originally proposed for the segmentation of images [6].

The mixed method involves combining methods based on edges and surfaces. Zhang et al. [28] used a statistical method to extract feature lines; however, it is affected by noise and sampling quality. Lari [16] proposed a segmentation algorithm that can quickly extract linear features in the point cloud data instead of segmenting the entire point cloud data, which leads to some limitations regarding the segmentation result. Zhana et al. [27] proposed a segmentation algorithm based on a color model to segment buildings, but this algorithm cannot be applied to point cloud models that do not contain color information, thereby greatly limiting its application potential. Dorninger et al. [9] proposed a point cloud segmentation algorithm based on parametric space. The algorithm clusters point cloud data in the space defined by the parameterization of the point cloud. However, this method is difficult to apply to unorganized point cloud data models. Gomes et al. [12] used 3D moving fovea to process parts of a scene using different levels of resolution. This approach can be used to identify objects in a point cloud. Gelfand et al. [11] presented shape segmentation using local slippage analysis. The shapes are defined as symmetric, which includes cylinders, planes, spheres, and surfaces of revolution. The method merges initial surfaces and is sensitive to the size of patches. In [18], Marshall et al. proposed an improved least-squares fitting algorithm, which can segment the primitives (cylinders, spheres, and cones) from range data. In [17], Li et al. presented an improved algorithm to fit primitives using global relations, which can be obtained through constrained minimization. Pu et al. [20] performed building segmentation and extracted features using surface growing according to direction and size derived from convex hulls. Ochmann et al. [19] filtered out clutter outside the building, which was caused by mirrors and windows. This method obtains point labeling of a buildings room and is also homogeneous within each room. Kaick et al. [15] proposed a shape segmentation algorithm, which can optimize decomposition based on characterization according to the expected geometry of a shape. Demir et al. [8] used similarities to segment and detect the shape of a point cloud.

Table 1 Comparison on number of parameters with current state of art

2.1 Overview and contributions

The aforementioned point cloud segmentation methods are mostly used for point cloud models or 2.5-dimensional depth images in specific application scenarios. Many of the methods involve a large number of parameters that have a substantial influence on the final segmentation result. We compare number of parameters in Table 1. These segmentation algorithms encounter many limitations when applied to unorganized 3D point cloud data. 3D scanners capture unorganized point cloud data, which makes it difficult to determine the topological relationship between points. The feature information corresponding to different parts is vastly different, and it is difficult for these algorithms to obtain an ideal segmentation result.

To address the aforementioned issues, we propose a self-adaptive point cloud segmentation algorithm to effectively segment different unordered point cloud data and lay a foundation for the 3D high-precision reconstruction.

The complete segmentation algorithm is provided in Algorithm 1. It is mainly divided into two steps: select seed points and segment the points. The first step mainly consists of the calculation of representativeness and diversity values. The second step mainly consists of the calculation of constraints. The calculations are described in detail in Sects. 3 and 4, respectively.

To summarize, our contributions are as follows:

• Our point cloud segmentation algorithm automatically selects seed points without user intervention, thereby suitably expressing similarity and guaranteeing the consistency of the segmentation results.

• The algorithm can confirm the number of seed points automatically instead of requiring user interaction. Our algorithm enhances its adaptability by using an automatic calculation.

• The algorithm can also rearrange the location of a noised point, thereby reducing the effect of noise.

• We consider the connectivity of points and use a semiautomatic region-growing algorithm by reducing the number of parameters, thereby balancing between the degree of under- and over-segmentation.

Fig. 1

Point mp has the total minimum distance

Fig. 2

Neighbors of a point

Fig. 3

Identify seed points and illustrate their location in datasets: a the decision of seed points in the aggregation dataset, colored points represent the seed points; b identify the location of seed points in the aggregation dataset; c present the seed points in the flame dataset; d the location of seed points in the flame dataset

3 Seed point calculation

In reverse engineering, mass research is a bottom-up method, which starts from the seed points and uses the region-growing algorithm. One problem for this method is the difficulty of selecting seed points. Thus, we present an algorithm that can automatically select seed points, which have a high density compared to its surrounding neighbors with lower density and a large diversity with other seed points [23].

Fig. 4

Results of normal estimation: a a sphere model with noise, b adjusted result of noise, c PCA normal estimation, d nonlinear least-squares normal estimation

3.1 Feature calculation

3.1.1 Representativeness values calculation

Representativeness can be measured by a point that has a higher density than its neighbors. There has been extensive research on density calculation, but most works require artificial parameters to set the radius. To reduce user intervention and enhance adaptability, the implementation of an automatic process is necessary.

The input is an unorganized set of points $U=\mathop {\left\{ {{p_i}}\right\} }\nolimits _{i\in I}\subset {R^3}$. A bounding box that has the minimal area and encloses all the points can be constructed. Then, we can obtain the initial neighborhood size as follows:

$$\begin{aligned} \alpha _0= \frac{{\hbox {dist}_d}}{{\root 3 \of {{ N }}}} \end{aligned}$$

(1)

where $\hbox {dist}_d$ is the diagonal length of the input U’s bounding box and N is the number of points in U. Additionally, it is necessary to compute a point $\hbox {mp} \in U$ (see Fig. 1), which has the total minimum distance to a set of points. It can be obtained as follows:

$$\begin{aligned} \hbox {mp} = \arg \min \sum \limits _{i \in I} \,||\hbox {mp} - {p_i}|| \end{aligned}$$

(2)

According to the initial neighborhood size and point mp, the neighborhood size can be computed automatically. It is adapted during iteration processing and can be described as follows:

$$\begin{aligned} \begin{aligned}&{\alpha _i} = \alpha _{i - 1} + \Delta L\\&\Delta L = \frac{1}{K}\frac{{\sum \nolimits _{p_i \in \hbox {Nhbd}_\mathrm{mp}} {\theta ||\hbox {mp} - p_i||\varphi (\mathbf {n}_\mathrm{mp},\mathbf {n}_{p_i})\mathbf {n}_{p_i}} }}{{\sum \nolimits _{p_i \in \hbox {Nhbd}_\mathrm{mp}} {\theta ||\hbox {mp} - p_i||\varphi (\mathbf {n}_\mathrm{mp},\mathbf {n}_{p_i})} }} \end{aligned} \end{aligned}$$

(3)

where $|| \cdot ||$ is the $L_2$-norm, $\mathbf {n}$ is the normal vector of a point, K is the number of points in Nhbd, and $\hbox {Nhbd}_\mathrm{mp} = \{ p_i|p_i \in U \wedge ||\hbox {mp} - p_i|| < \alpha _i\}$ under a neighborhood size $\alpha _i$; that is, the points can be obtained from fixed distance neighbors (FDNs). For a given point and the neighborhood size $\alpha _i$, the FDNs select all the points within the area (Fig. 2). For an FDN search, the number of neighbors K changes according to the density. The weight and spatial functions are defined by

$$\begin{aligned} \theta \left( r \right) = {\hbox {e}^{ - {r^2}/{{(\alpha /2)}^2}}},\quad \varphi (\mathbf {n},\mathbf {n}_i) = {\hbox {e}^{ - \left( \frac{{1 - {\mathbf {n}^T}\mathbf {n}_i)}}{{1 - \cos ({\mathbf {n}^T}\mathbf {n}_i)}}\right) }}. \end{aligned}$$

Equation (3) is calculated by iterating until the value of K is constant. The computation of the radius is suitable for different models and enhances adaptability.

Fig. 5

Extended evaluation of our method on different objects

Fig. 6

Results obtained by the different methods of segmenting a single object: a segmentation of [21]; b segmentation of [23]; c our method: eight seed points are selected, the representativeness and diversity values are shown in (d); d the decision of seed points in two dimension, the color of seed point corresponds to the color of seed area in (c)

Fig. 7

Comparison of the plant model segmentation results using the three algorithms: a segmentation of [21]; b segmentation of [23]; c our method: five seed points are selected; d the decision of seed points in two dimension

After neighborhood size $\alpha$ has been obtained, the representativeness value, that is, the density of each point in U, is defined as

$$\begin{aligned} {\rho _i^\mathrm{Rep}} = 1 + \sum \limits _{j \in I\backslash \{ i\} } {\theta \left( ||p_i - p_j||\right) } \end{aligned}$$

(4)

To avoid excessive segmentation, we sort all the data points in descending order according to density.

3.1.2 Diversity values calculation

To ensure the diversity of the seed points, the diversity can be measured by computing the minimum distance between point $p_i$ and other points with densities that are higher than that of point $p_i$ [23]. We define the diverse distance as follows:

$$\begin{aligned} {\delta _i^\mathrm{Div} = {\mathop {\min }\nolimits _{\mathrm{{j}} < i} ||{p_{i}} - {p_{j}}||}} \end{aligned}$$

(5)

For the point with the highest density, it can be noted that

$$\begin{aligned} {\delta _i^\mathrm{Div} = \mathop {\max }\limits _{i \ne j} ||p_i - p_j||} \end{aligned}$$

(6)

The diversity values are similar to those obtained using the maximum marginal relevance algorithm [2], which is used to remove points that are similar to those already selected. The maximum marginal relevance algorithm compares a point with selected points, whereas we compare a point with all other points, thus our algorithm has higher global diversity.

3.2 Automatic selection of seed points

As mentioned previously, the seed point is characterized by a higher density than its neighbors and by a relatively large distance from points with other higher densities to ensure the stability of this process. Therefore, we determine it using the following formula:

$$\begin{aligned} {{\hbox {sp}_i^\mathrm{Att}} = {\log \rho _i^\mathrm{Rep}} + \log {\delta _i^\mathrm{Div}} } \end{aligned}$$

(7)

We use the aggregation and flame datasets to evaluate the performance of selecting seed points in two dimensions, as shown in Fig. 3. Clearly, the algorithm tends to find seed points that are both dense and a large distance from other seed points. Next, we sort the points in descending order according to the value of sp. Then we generate the set of seed points $S_L$.

For the region-growing process, we select one point in $S_L$ as a seed point in the sequence. Until the seed point operation is complete, the subsequent points are selected as seed points individually. Our algorithm can thus adaptively select seed points and automatically set the number of seed points. It can address the problem of inconsistent segmentation results caused by the random selection of seed points.

4 Segmentation

After seed point selection, a semiautomatic region-growing algorithm is used for segmentation. The region-growing algorithm is a surface-based method and involves clustering points with similar attributes into the same region with respect to the seed points.

In the region-growing process, another difficulty is determining whether the point should be added in a given region because the decision is susceptible to noise. To address this difficulty, we consider the connectivity of points and use an improved normal as a constraint.

Fig. 8

Results obtained by the different methods when segmenting a single object from multiple objects: a–c [21, 23], and our method, respectively: six seed points are selected; d the decision of seed points in two dimension

Table 2 Results of segmentation

Table 3 The detail of point cloud model

Fig. 9

Segmented the models with different levels of Gaussian Noise. a 0.3% noise; b 0.6% noise; c, d are the segmentation results with noise

4.1 Estimation of normal

Traditionally, the normal is equivalent to the normal of the least-squares plane of the point and its neighborhood. Using principal component analysis (PCA) [9] to estimate the normal produces poor approximations because of the existence of surface discontinuities and noise. Surface discontinuities are mainly caused by equally weighting the incorrect contributions of points [3]. Thus, we use an improved constrained nonlinear least-squares algorithm to adaptively determine the weight of each point contribution, which can be expressed as follows:

$$\begin{aligned} \begin{aligned}&\mathop {\arg \min }\limits _\mathbf {n} \frac{1}{2}\sum \limits _{k = 1}^K {{\hbox {e}^{ - \lambda {{(o_k^T\mathbf {n} )}^2}}}} {(o_k^T \mathbf {\mathbf {n}} )^2}\\&\hbox {s.t.}||\mathbf {n} |{|_2} = 1\\&\lambda = \frac{{K}}{{N}} \end{aligned} \end{aligned}$$

(8)

where $o_k=p_k-p$, $p_k$ is the neighbors of point p, $\mathbf {n}$ represents the normal vector and weighting $\hbox {e}^{- \lambda {{(o_k^T\mathbf {n} )}}}$ can adaptively deflate the contribution of the high orthogonality mismatch defined by $\lambda$.

If the input point cloud has severe noise, we rearrange the location of the noised point. We use the following to obtain the location of adjustment:

$$\begin{aligned} \begin{aligned} \mathop {\arg \min }\limits _{\tilde{p},\mathbf {n} } \frac{1}{2}\sum \limits _{i = 1}^k {{\hbox {e}^{ - \lambda {{({{({p_{^k}} - {\tilde{p}})}^T}\mathbf {n} )}^2}}}} {\left( {\left( {p_{^k}} - {\tilde{p}}\right) ^T}\mathbf {n} \right) ^2} \end{aligned} \end{aligned}$$

(9)

where ${\tilde{p}}$ is the adjusted location. Figure 4a, b shows the adjustment of noise by which we can reduce the influence of noise. We apply PCA and Eq. (9) to the mimosa model, which is provided in [14]. The results are shown in Fig. 4. Comparing Fig. 4c, d, we observe the improvement of the algorithm in the estimation of the normal.

4.2 Point connectivity

To measure connectivity, the adjacency matrix is constructed, which is obtained from the surface curvature estimation that describes the connectivity for the unorganized set of points.

Based on FDN information and the curvature, an adjacency matrix $\mathbf {SA}$ is built, and the matrix is symmetric. If $p_i$, $p_j$ are connected, ${\mathbf {SA}_{i,j}} = 1$, otherwise ${\mathbf {SA}_{i,j}} = 0$. Considering connectivity, we assume that if points $p_i$, $p_j$ are FDNs of each other and the curvature is less than the mean curvature in FDNs, then ${\mathbf {SA}_{i,j}} = 1$.

We now consider computing the curvature using the method of moment-based surface analysis, which is robust to noise [5]. For a surface M and neighborhood ball B with neighborhood size $\alpha$, the zero moment of point p can be defined as

$$\begin{aligned} M_\alpha ^0 (p): = \int _{{B_\alpha }(p) \cap M} {pdp} \end{aligned}$$

(10)

and the first moments as

$$\begin{aligned} M_\alpha ^1(p)&: = \displaystyle \int _{{B_\alpha }(p) \cap M} {\left( p - M_\alpha ^1(p)\right) } \otimes \left( p - M_\alpha ^0(p)\right) \hbox {d}p \nonumber \\&= \displaystyle \int _{{B_\alpha }(p) \cap M} p \otimes pdp - M_\alpha ^0(p) \otimes M_\alpha ^0(p) \end{aligned}$$

(11)

where $q \otimes w := {({q_i}{w_j})_{i,j = 1,2,3}}$. Because of the definition of a moment-based surface via local integration, these moments are robust to noise. Additionally, the curvature at point p can be computed using the zero and first moments shift:

$$\begin{aligned} \varsigma = G\left( \frac{{||{M_\alpha ^0(p) - p }||{\lambda _{\min }}}}{{\alpha {\lambda _{\max }}}}\right) \end{aligned}$$

(12)

where $\varsigma$ is the curvature, $\lambda _{\min }$ and $\lambda _{\max }$ are the eigenvalues at point p in the first moment M, $G = \frac{1}{{\alpha + {K^2}}}$ with neighborhood size $\alpha$ obtained from Eq. (3), and K is the number of neighbors.

4.3 Region growing

The basic purpose of the segmentation algorithm is to subdivide the points into meaningful subsets with high similarity, while avoiding over- and under-segmentation. The details of the segmentation steps are provided in Algorithm 2, and the implementation process is further described below.

We denote the current seed region by Sc, and the global segment list by $R_L$. A seed is chosen from the set of seed points $S_L$.

Fig. 10

Segmented the point cloud using different strengths $\sigma$. a $\sigma =0.02$, b $\sigma =0.1159$, c $\sigma =0.4$, d $\sigma =0.04$, e $\sigma =0.146$, f $\sigma =0.32$

Fig. 11

Segmented indoor scene with multiple models

The implementation process is as follows:

• 1. Select the first data point $\hbox {seed}_1$ in $S_L$ as the initial current seed point and insert it into the current seed region Sc.

• 2. Obtain the neighbors of the current seed point that satisfy $\cos (|\langle {{{{\beta _{{p_l}}}}, {{\beta _{\mathrm{seed}}}} }} \rangle |) < {\sigma }$. The neighbor will be added to the current region Rc. $\sigma$ represents the threshold of the normal. As $\sigma \rightarrow$ 1, we have fewer segments, and in the extreme case, all the points belong to one segment. Similarly, as $\sigma \rightarrow$ 0, we have more segments, and in the extreme case, each point belongs to one segment. Thus, $\sigma$ provides a balance between over- and under-segmentation.

• 3. If the points are connected, add the neighbor to the current seed region Sc and remove it from $S_L$.

• 4. Delete the current seed point in seed region Sc and remove the data point from U.

• 5. Select the next data point in the current seed region Sc as the current seed point, return to Step (2), and execute until the seed region Sc is null.

• 6. Save Rc in the segment list $R_L$. Select the next data point in $S_L$ as the current seed point, return to Step (1), and end the segmentation when all the points are segmented.

5 Results and analysis

We conducted experiments on various models. Figure 5 presents segmentation results of models in [15] and [4]. It is noted that the algorithm is robust when applied to these models and preserves the connectivity of the point cloud.

5.1 Results comparison

To evaluate the segmented results of our proposed algorithm, we conduct three experiments to compare it with the segmentation algorithms of Rabbani et al. [21] and Rodriguez et al. [23].

Fig. 12

Comparison with WCSeg [15] on Princeton Segmentation Benchmark [4]. a WCSeg [15] versus our method, b WCSeg [15] versus our method, c Rand index, d Hamming distance, e Consistency error, f Cut discrepancy

The segmented results are shown in Figs. 6, 7 and 8. Table 2 compares segmented results obtained by three methods. In Figs. 6, 7 and 8, it can be seen that [21] and [23] excessively segmented single leaves and insufficiently segmented the connection parts of the stems and leaves. In Figs. 6, 7 and 8c, we can observe that each part of the model has a seed point, which has a higher density and is far from the other seed points. Moreover, the algorithm effectively distinguished between stems and leaves. It obtained accurate segmentation results and avoided over- and under-segmentation problems. Figures 6, 7 and 8d show that the seed points have a high density and an obvious division from the other seed points. The result demonstrates that the seed points are reasonable and effective.

In [21], three parameters need to be set: the number of neighbors K, curvature threshold $\varsigma$, and normal threshold $\sigma$. In [23], two parameters need to be set: cutoff distance $d_\mathrm{c}$ and cluster number Num. In our method, only one parameter needs to be set: normal threshold $\sigma$. For the experiments, Table 3 provides the necessary data.

5.2 Robust test

We added different levels of Gaussian noise to the models to evaluate the robustness of our approach. Noise of 0.3% and 0.6% were added to the models. The resulting segments are shown in Fig. 9.

We segmented the point cloud using different strengths. Figure 10 illustrates the effect of $\sigma$. The results are ordered by over-segmentation, segment well, and under-segmentation, respectively. It is clear that $\sigma$ provides a balance between over- and under-segmentation.

Although the focus of our algorithm is the segmentation of a single point cloud model into meaningful subsets, we also show in Fig. 11 a test that applied our algorithm to scenes with multiple models. In the test, we segmented an indoor scene. We can observe that if the model has obvious differences in parts and structures, our method can segment it effectively.

5.3 Quantitative evaluation

We quantitatively evaluate our algorithm with the well-known Princeton Segmentation Benchmark of Chen et al. [4].

In Fig. 12, we compare to the approximate convex analysis (WCSeg) algorithm [15], which can characterize a part as a collection of weakly convex components. As shown in Fig. 12a, compared with WCSeg, our algorithm has more segments in wings, as our algorithm determines the weight of each point contribution while computing normal. In Fig. 12b, our algorithm has fewer segments on the body of the Dinosaur model, as we consider the connectivity of points.

To use the benchmark, we transform the meshes into point cloud and map the segmentation results back to the meshes. Figures 12c–f show a comparison of the algorithms according to the various measures of the benchmark, which reveal the corresponding properties of our method in different aspects, including fewer decomposition parts (d), good segment consistency (e), and similar cut boundaries (f). In Fig. 12c, the Rand index measures a likelihood assessment on state-of-the-art methods. The Rand index of our algorithm is low, WCSeg is better than ours, since these semantic segments labeled by humans are generally convex, the WCSeg is more suitable for decomposing models semantically.

6 Conclusion and limitation

• (1) Our self-adaptive point cloud segmentation algorithm automatically selects seed points and guarantees the consistency of the segmentation results. The algorithm reduces both the setting of parameters and the effect of noise, which can enhance the adaptability of the algorithm. The only user-specified parameter required by our method provides a balance between over- and under-segmentation. According to the test results, our algorithm effectively segmented the point cloud and achieved a segmentation rate of up to 96%.

• (2) However, the algorithm demonstrated better segmentation results for models with obvious differences in parts and structures, and exhibited a certain limitation for models with similar structures; the limitation can be seen in Fig. 13.

Fig. 13

Segmented point cloud with a limitation