1.

Introduction

Structured light based three-dimensional (3-D) measuring technique has its advantage on acquisition speed, cost, and stability. It has been widely applied in measuring surfaces and molds, prosthesis design, rapid prototyping, and reverse engineering. Compact and portable 3-D laser scanner has been integrated in optical and microelectronic technologies. The structural information is achieved with 3-D mesh segmentation. Mesh segmentation of 3-D surface has become a necessary gradient in geometric modeling, computer graphics and their applications. Accordingly, other relative research fruits are achieved in previous works.^1,2 In previous works, many mesh segmentation methods are proposed for 3-D surface segmentation. Mesh segmentation has been studied by many research scientists, and many segmentation methods are proposed in various application contexts. Comprehensive studies are implemented in different criteria and methods of mesh segmentation. In the previous works, researchers proposed region growing,³ watershed,⁴ hierarchical clustering,⁵ feature points,⁶ skeleton-based segmentation.⁷ Good performances on segmentation accuracy were reported, but these methods still endure the computation consuming problems in practical applications. Time consuming limits mesh segmentation in the practical applications. In order to solve the computation consuming problem, we propose a rapid surface segmentation for 3-D laser scanning data based on region dilation strategy.

2.

Method

Figure 1 describes the flow of proposed 3-D surface segmentation. The proposed algorithm has three steps including point cloud meshing, candidate regions generating, and insignificant regions eliminating.

2.2.

Step 2: Candidate Regions Generating

The normal vectors and areas are computed for every polygon, and the region dilation is employed to generate candidate regions. Supposed that 3-D polygon mesh model $P=\{p_1,p_2,\cdots ,p_N\}$, the normal vectors set $PN=\{\overrightarrow{p{n}_1},\overrightarrow{p{n}_2},\cdots ,\overrightarrow{p{n}_N}\}$ and the areas set $A=\{a_1,a_2,\cdots ,a_N\}$, the region dilation implemented through dilating certain polygons with similar normal vectors. As shown in Fig. 2, $\overrightarrow{p{n}_i}$ and $\overrightarrow{p{n}_j}$ are the normal vectors of two triangular mesh $p_i$ and $p_j$, respectively. If $\overrightarrow{p{n}_i}$ and $\overrightarrow{p{n}_j}$ have similar normal vectors, $p_i$ and $p_j$ are considered to be in the same region, and these two triangular meshes are merged into a new region which is to be dilated with other triangular meshes. Let $\overrightarrow{N}(R_l)$ denotes the normal vector of region $R_l$, and $A(R_l)$ denotes the area of region $R_l$. If a polygon $p_i$ is border on $R_l$, and $\overrightarrow{p{n}_j}·\overrightarrow{N}(R_l)\le E_N$, then $p_i$ is belongs to this region. The normal vector of the new region and area is updated with $\overrightarrow{N}(R_l)=(\overrightarrow{N}(R_l)·A(R_l)+\overrightarrow{p{n}_j}·a_j)/\Vert (\overrightarrow{N}(R_l)·A(R_l)+\overrightarrow{p{n}_j}·a_j)\Vert$, $A(R_l)=A(R_l)+a_i$, where $\Vert V\Vert =\sqrt{\overrightarrow{V}·\overrightarrow{V}}$ denotes the length of vector $\overrightarrow{V}·E_N$ is the region dilation threshold with respect to the maximum curvature of a mesh facet. The maximum curvature defines the maximum allowed angle between the normal vectors of two polygons in the same region. The region dilation starts from an arbitrary polygon. The border polygons is dilated into the same region where $\overrightarrow{p{n}_j}·\overrightarrow{N}(R_l)\le E_N$, otherwise a new region is formed.

Fig. 1

Flow of proposed 3-D surface segmentation.

Fig. 2

Illustration of region dilation strategy.

3.

Experiments

Many evaluations are implemented on real 3-D laser scanning data. In the experiments, we Roland LPX-250 3-D laser scanner to collect the 3-D cloud point data of the objects. The LPX-250 3-D laser scanner offers good scanning capability with non-contact 3-D laser scanning. It has a large scanning area [up to 406.4 mm (16 in.) high × 254 mm (10 in.) in diameter].

Firstly, we evaluate the proposed method on segmentation accuracy. The experimental results are shown in Figs. 3 and 4. In the each figure, the first column figure is the photo of the object as shown in Figs. 3(a) and 4(a), and the second one is 3-D laser scanning point clouds data as shown in Figs. 3(b) and 4(b), and the third one is the polygon mesh with point cloud meshing as shown in Figs. 3(c) and 4(c), and fourth column is the segmented 3-D surface as shown in Figs. 3(d) and 4(d). The object in Fig. 3 has round surface and indistinct edge, where $E_N=0.8$ and $E_A=9\%$. In Fig. 4, the object has a coarse and bumpy surface, and the curvature of the region located in the left-up is great variety, and $E_N=0.9$ and $E_A=5\%$ are determined. The results show that the proposed algorithm performs well on 3-D laser scanning data segmentation.

Fig. 3

Experimental results I.

Fig. 4

Experimental results II.

Second, we evaluate the computation efficiency compared with other current segmentation methods. The relative methods are implemented on MATLAB platform, and the time consuming of 3-D surface segmentation implementation is to evaluate the computation efficiency. For the comparison, we implement other algorithms including region growing,³ watershed,⁴ hierarchical clustering,⁵ feature points,⁶ and skeleton-based segmentation.⁷ These methods are 3-D mesh segmentation methods, while our method is to solve the 3-D surface cloud data. So we only calculate the time consuming of 3-D segmentation not considering the procedure of 3-D cloud point meshing. The results are shown in Table 1. The proposed method performs best compared with other methods.

Table 1

Computation consuming of different segmentation methods (in s).

4.

Conclusion

In this letter, we present a novel rapid automatic surface segmentation method for 3-D laser scanning data. The time consuming of the proposed method is evaluated with comparing other traditional methods in the real 3-D laser scanned data. Three-dimensional surface mesh segmentation has its wide applications in geometric modeling, computer graphics.