7 May 2012 Rapid three-dimensional surface mesh segmentation based on region dilation
Author Affiliations +
Three-dimensional laser scanned surface segmentation is an important step for computer-aided broken objection patching. Current methods still have high time consuming problem in practical applications. In order to solve this problem, we propose the rapid three-dimensional (3-D) surface segmentation based on region dilation. The procedure includes three steps of point cloud meshing, candidate region generating, and insignificant region eliminating. Some experiments are implemented on the 3-D surface with a Roland LPX-250 3-D laser scanner to testify the feasibility and performance of the proposed algorithm compared with other methods.



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,3 watershed,4 hierarchical clustering,5 feature points,6 skeleton-based segmentation.7 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.



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.


Step 1: Point Cloud Meshing

The surface data of the object are the 3-D point clouds through 3-D laser scanning system. Three-dimensional point clouds did not describe the topology of the object. Three-dimensional point clouds are converted into polygon mesh. The point cloud meshing functions are provided for most 3-D laser scanners. In this paper, we implement 3-D point cloud meshing with software package of laser scanner.


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={p1,p2,,pN}, the normal vectors set PN={pn1,pn2,,pnN} and the areas set A={a1,a2,,aN}, the region dilation implemented through dilating certain polygons with similar normal vectors. As shown in Fig. 2, pni and pnj are the normal vectors of two triangular mesh pi and pj, respectively. If pni and pnj have similar normal vectors, pi and pj 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 N(Rl) denotes the normal vector of region Rl, and A(Rl) denotes the area of region Rl. If a polygon pi is border on Rl, and pnj·N(Rl)EN, then pi is belongs to this region. The normal vector of the new region and area is updated with N(Rl)=(N(Rl)·A(Rl)+pnj·aj)/(N(Rl)·A(Rl)+pnj·aj), A(Rl)=A(Rl)+ai, where V=V·V denotes the length of vector V·EN 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 pnj·N(Rl)EN, otherwise a new region is formed.

Fig. 1

Flow of proposed 3-D surface segmentation.


Fig. 2

Illustration of region dilation strategy.



Step 3: Eliminating Insignificant Regions

In the region dilation, small regions may be created within larger ones using a very high region dilation threshold or a bumpy surface. Eliminating the insignificant regions is implemented through iteratively assigning the polygons of regions Rl whose area A(Rl) is smaller than EA. The parameter EA is the minimum area threshold, where EA is the percentage of regions in the area of model surface.



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 EN=0.8 and EA=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 EN=0.9 and EA=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,3 watershed,4 hierarchical clustering,5 feature points,6 and skeleton-based segmentation.7 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).

MethodsRegion growing3Watershed4Hierarchical clustering5Skeleton7Proposed method
3-D Mesh (Fig. 4)24.62330.18926.35719.34616.536
3-D Mesh ( Fig. 4)27.34533.98828.34721.46718.467



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.


1. H. G. KaganamiS. K. AliB. Zou, “Optimal approach for texture analysis and classification based on wavelet transform and neural network,” J. Inf. Hiding Multimedia Signal Process. 2(1), 33–40 (2011). Google Scholar

2. Kh. Manglem Singh, “Fuzzy rule based median filter for gray-scale images,” J. Inf. Hiding Multimedia Signal Process. 2(2), 108–122 (2011). Google Scholar

3. G. LavouF. DupontA. Baskurt, “Curvature tensor based triangle mesh segmentation with boundary rectification,” IEEE Comput. Graph. Int. 1, 10–17 (2004). Google Scholar

4. A. P. ManganR. T. Whitaker, “Partitioning 3D surface meshes using watershed segmentation,” IEEE Trans. Vis. Comput. Graph. 5(4), 308–321 (1999).1077-2626 http://dx.doi.org/10.1109/2945.817348 Google Scholar

5. M. AtteneB. FalcidienoM. Spagnuolo, “Hierarchical mesh segmentation based on fitting primitives,” Vis. Comput. 22(3), 181–193 (2006).VICOE50178-2789 http://dx.doi.org/10.1007/s00371-006-0375-x Google Scholar

6. V. Natarajanet al., “Segmenting molecular surfaces,” Comput. Aided Geomet. Des. 23(6), 495–509 (2006).0167-8396 http://dx.doi.org/10.1016/j.cagd.2006.02.003 Google Scholar

7. J. M. LienJ. KeyserN. M. Amato, “Simultaneous shape decomposition and skeletonization,” Proc. ACM Solid Phys. Model. Symp., Association for Computing Machinery, Wales, United kingdom, 219–228 (2006). Google Scholar

© 2012 Society of Photo-Optical Instrumentation Engineers (SPIE)
Jun-Bao Li, Jun-Bao Li, Meng Li, Meng Li, "Rapid three-dimensional surface mesh segmentation based on region dilation," Optical Engineering 51(5), 050502 (7 May 2012). https://doi.org/10.1117/1.OE.51.5.050502 . Submission:


Back to Top