TMCnet News

A Surface Reconstruction Algorithm Based on 3D Point Cloud Stratified Sliced [Sensors & Transducers (Canada)]
[July 17, 2014]

A Surface Reconstruction Algorithm Based on 3D Point Cloud Stratified Sliced [Sensors & Transducers (Canada)]


(Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: This paper presents a novel surface reconstruction algorithm based on 3D point cloud sliced by a series of planes vertical to Z-axis. First, the density and distribution of point cloud is analyzed in vertical direction Z-axis and a stratified point cloud model is put forward to present an object feature, in which point cloud is sliced with irregular intervals. An approach of stratified point cloud projected on plane is proposed. The algorithm based on Delaunay triangulation technique in two dimensions gain quickly the local topological connection relationships between points. Further, the planar triangular mesh is mapped into 3D-TIN. Finally, the object surface model is composed of the stratified 3D-TINs with consistent edges. Two tests are implemented to demonstrate that the algorithm is very simple, robust and suitable to reconstruct the object surface based on complex shaped and irregular 3D point cloud. Copyright © 2014 IFSA Publishing, S. L.



Keywords: Plane slicing, Point cloud, Stratified point cloud model, 3D-TIN, Surface reconstruction.

(ProQuest: ... denotes formulae omitted.) With the rapid development of digital technology, the demand for the original information of real-world is increasing, 3D laser scanning technology is one of the technologies, which can use laser pulses to scan object's surface features and to obtain information. With the emergence of high precision 3D laser scanner, it makes for a complex composed of point cloud surfaces model more easily. In recent years, the use of 3D point cloud to express the surface of the object has become a hot topic for many scholars [1-4], and developed many ways, such as the triangulation method, the level set method and the implicit function surface interpolation.


Level set method was first proposed by Osher and Sethian [5] in 1988, Whitaker and Zhao [6-7], who applied this method to the surface reconstruction, the basic idea is to define a multispeed function after time evolution of the zero level set close to the surface until a given point cloud model. The biggest advantage of the level set method is due to its representation is implicit, especially for complex topologies surface reconstruction, but its ability to represent the details of the limited efficiency of the algorithm is relatively low, requires a lot of computing time and enough memory space. Implicit surface interpolation function is a function of the surface equation set represents zero value measured surface, its main advantage is that only one equation to represent complex interpolated surface, but the drawback is difficult to find a suitable set of basis functions to represent implicit function. For this reason, many scholars have developed many ways. More representative is based on radial basis function (RBF) implicit function method [8], cloud data model which use zero linear combination of radial basis function for interpolation or approximation to the input set point, but RBFs have global support set of equations is a linear system fused, so the technique can not contain tens of thousands of data from the implicit surface reconstruction [9]. Carr [10] and some one else tried to use a multi-stage approach RBF fast computing technology to improve the traditional RBF deficiencies, but this method requires complex mathematical algorithms and computational huge linear system matrix, thus implement is more complex. Kojekine [11] construct a smooth surface by using compactly supported radial basis functions based on point cloud data, then the matrix is sparse linear systems, computing is more efficient. But this time the radius of support set is global, so the method for highly non-uniform scattered data set is not robust. Delaunay triangulation -based 3D point cloud surface reconstruction method by establishing a triangular mesh interpolation all or most points. Although the Delaunay triangulation method has been applied in the two-dimensional plane area is very mature, but automatically generate threedimensional triangulated irregular network (3D-TIN) there are many difficulties can not be resolved, based on the maximumminimum angle diagonal exchange mies is not established, based on circum circle judge mies Delaunay triangulation is difficult to obtain high quality meshes [12]. Therefore, many scholars have improved Delaunay triangulation algorithm so that it is applied to generate a three-dimensional surface model, Hoppe proposed algorithm to restore the surface and volume data from surface data [13], but the irregular three-dimensional discrete point set boundaries and sharp feature area can not be processed automatically. Edelsbrunner [14] proposed an algorithm for uniform data set, the algorithm is very effective, but for scattered data points, and sometimes difficult to select the appropriate value.

In summary, the current three-dimensional surface reconstmction algorithm based on scattered points mainly two aspects: 1, algorithm complexity, massive point cloud data for surface models, time efficiency and space efficiency are relatively low. 2, universality poor, each algorithm is the most effective for specific types of point cloud data, best in the reconstruction, there is no point in a threedimensional scattered surface reconstruction algorithm based on good adaptability. To solve these problems, this paper presents a three-dimensional point cloud layered cut surface reconstruction algorithm is essentially a Delaunay triangulation method based on reconstruction.

1. Principle of the Algorithm Assuming that a given scattered 3D data points on the surface is S={V^i=\,2,...,n), where in Vi is (xi, yi, zi), 'n' is the number of points. Goal of this paper is to establish a triangular interpolation 'S' manifold meshes [15]. Due to the two-dimensional point set Delaunay triangulation has been very mature, triangulation points more than the three-dimensional data simple and convenient. Therefore, you can use the appropriate manner set S sub-blocks, each block and then were projected onto a suitable set of points of the plane, respectively, two-dimensional triangulation, get connected to the relationship between points, and then those connections relational mapping is returned to the three-dimensional space, thus forming a space for each local point clouds triangulation, two-dimensional plane triangulation mapped into a triangulated irregular network (3D-TIN), shown in Fig. 1. Finally, build a good adjustment of each local triangular mesh stitching got triangle interpolation 'S' manifold meshes.

Based on this idea, the proposed threedimensional point cloud surface reconstruction method for cutting layered as follows: (1) A hierarchical set of points: a series of plane perpendicular to the Z axis direction and the Z axis at a certain height, the data set S stratified, each layer does not necessarily require a high degree of consistency, this point set 'S' plane cutting into LI, L2, such as point clouds. (2) Point clouds projected onto the cylindrical surface: processing point clouds 'Li', according to the coordinates of the point cloud layer range, to generate a completely parallel to the layer comprising the bus to the Z axis of the cylindrical surface, the center of the cylindrical surface of the layer located on the center, the radius of the point set should ensure that the entire layer is contained within the cylinder, the cylinder height and highly consistent layer. For the three-dimensional point 'Vi', according to its z value, determine which is located parallel to the bottom surface of the cylinder of circular cross section, connecting the center of the circular cross-section and 'Vi' and extend the connection to the cylindrical surface intersect at one point, assuming 'vi' point, the point 'vi' is the point of the projection surface of 'Vi', as shown in Fig. 2, vl ~ v3 point is the point in space VI ~ V3 cylindrical projection. Likewise, the rest of the layer three points are projected onto the cylindrical surface. (3) Cylindrical surface of the point set is converted into planar point set: a bus along the cylindrical surface cut, spread on a flat surface, so 3D point set in the point clouds the 'Li' is converted into a two-dimensional planar point set. (4) Two-dimensional to three-dimensional mapping of triangulation: the projection of the point set after the two-dimensional plane Delaunay triangulation, has been connecting the dots between relationship, the connection between these three-dimensional space is mapped to return to, thus generating a threedimensional point clouds Li triangulated irregular network (3D-TIN). (5) Similarly, the cloud point of the rest of the processing sequence, repeat steps (2)-(4), after splicing adjusted to obtain a triangular interpolation S manifold mesh.

The flowchart of the algorithm shown in Fig. 3.

1) Point set layering principle: This article is based on Z axis direction and a certain height to layering, you can also press the X-axis or Y-axis direction tiered, depending on a given surface point cloud model shape. The overall principle is to avoid hierarchical set of points in different areas of the layer of surface area projected onto the same cylinder, local changes in the relative position of the dots between, to avoid or reduce overlapping or staggered triangulation. Secondly, the position of the cutting plane should be located in a threedimensional point cloud curvature is relatively small, relatively flat area of change, it's better with the other point clouds mosaic effect. Finally, the surface should be such that the density of the point cloud is relatively large, relatively large changes in the curvature of the region located in the same layer, this area should not be separated. For example, the head of the point cloud model used in our experiments behind the mouth parts of the point cloud density compared to other areas should be large, then the entire mouth area should be divided in the layer.

2) The point cloud projected onto the cylindrical surface: assume its corresponding cylinder radius of cloud point 'L' is 'r', XY coordinate for alignment circle center 'O' is 0(x" yc). For any point, with Oz(xz, yz, z) as the pole, x-axis being the polar coordinates polar axle in its polar angle (in radians) is calculated as follows: First, order, dx=xz-xc, dy=yzyc and angle for 'OZV' and x-axis is angle=atm(\dy/dx\), which is not greater than the angle of 90°. Then calculate the polar angle polarangle, which have four cases: ... (1) ... (2) ... (3) ... (4) 3) Expand the cylindrical surface into a flat, converted into a three-dimensional planar point set point set: Suppose 'z' coordinates of the point cloud 'L' range is 'zl ~ z2', polar angle of the bus along the cut cylinder 0, the plane into a rectangular tile , the rectangular lower perimeter lengths is z = z = zl and z2 of the two planes, respectively, after cutting the two cylindrical surfaces of circular cross section, respectively, the left and right sides and a polar angle of 0 bus length z2-zl. Then, the establishment of a plane coordinate system shown in Fig. 4, Y-axis coincident with the polar angle 0 of the bus. Cloud point has assumed as V (x, y, z), polar angle in the plane 'Z = z' is b, the plane passing through the coordinate transformation is x=r0, y=z. In particular, all points which the polar angle is zero on the bus just falls on cutting bus, point 'VI ~ V3' as shown by the angle of the pole at 'vl ~ v3' corresponding point on the cylinder is the same on the three-point bus; At the point cloud 'L', also correspond to the same threedimensional point, projected onto the cylinder after the bus fell on the cutting. Thus the resulting triangle mesh is mapped to the space plane, the relative position of the bus at the incision between points does not change, which is connected relationship will not change.

4) The triangle in two-dimensional mapping into three-dimensional space: first set of points within the rectangle planar Delauany triangulation, article-bypoint insertion method. Get the point set by the external boundary (four sides of the rectangle falls), according to the boundary and internal points, in accordance with the principle of generating the maximum angle of the triangular mesh, get connected to the relationship between points, and map it to a three-dimensional space to form a space triangulation.

5) Stitching layered three-dimensional grid: Suppose triangle meshes 'Ml' and 'M2' are adjacent upper and lower layers of local triangulation at 'Z = z' cross-section of the phase, the goal is to integrate them into a triangle mesh. First, 'M2' triangle unconditionally added to the collection of 'Ml' , the merged into a grid, denoted by 'M', and then determine and adjust the 'Ml', 'M2', triangle stitching at the edges and remove illegal triangle. Since the set of points for the upper and lower sections there were , therefore 'Ml', 'M2', stitching the edge of the triangle , they have an edge is composed of two adjacent sections of dots. Specifically, the edge of the triangle can be adjusted with reference by Fig. 5. Assuming 'PI', 'P2' are two points on the adjacent section, triangular 'AP1P2' in 'Ml', triangular 'BP1P2' in 'M2', according to the characteristics of the empty circumcircle Delaunay triangulation to determine the need for exchange of diagonal. Be determined by the same method adjustment of the other edge triangle. Then, to further discrimination and remove illegal triangle triangle mesh. Let 'P' be the vertices of a triangle 'M', the triangle set denoted by 'TP' which vertex is 'P', aims to identify and delete 'TP' illegal triangle, making 'M' still meet the definition of a two-dimensional manifold at 'P'. Specifically refer to Fig. 6 the following ways: 1) If one side of the triangle to a network as one of the vertices 'P', another vertex denoted 'Q', only up to the edge two triangles are common, if the edge is three or four common triangles, delete have one or two sides of the triangle 'PQ', 'PQ' such that the two triangles are common side, and the two triangles overlap or not interleaved with other triangles in 'TP' Fig. 6 (a) and (b).

2) When 'PQ' common triangle edge is a case of three or more does not exist, if there is a 'PQ' in the 'TP' to the other side of the triangle or triangles staggered overlap remove the triangle, so that no other triangle triangle while maintaining the interleaved or overlapping full network, as shown in Fig. 6 (c) and (d).

2. Experiment and Analysis Computing time for layered 3D point cloud surface reconstruction algorithm includes two parts of the point cloud Delaunay triangulation hierarchical and stratified local triangular mesh stitching. The time complexity of the hierarchical point cloud Delaunay triangulation is about O (nlgn), layered triangular mesh stitching local time complexity is linear, so the total time complexity of the algorithm is O (nlgn), where n midpoint indicates the number of cloud point. Typical Delaunay triangulation based surface reconstruction algorithms are generally required to calculate the point of focus for each point approximation vectors, required by the K-nearest neighbor rule on the point cloud block, as well as a complex mosaic of local triangular mesh process, so the algorithm has obvious speed advantage.

In order to verify the effectiveness and time efficiency of the algorithm, this paper designed a number of experiments. Experiments using Visual Studio 2008 for C + + development environment, the 202CPU clocked at 2.0 GHz, 1 G memory of the PC up to achieve reconstruction algorithm, and compared with principal component analysis of the surface reconstruction algorithm [16], the calculation results shown in Fig. 7-9.

2.1. Experiment 1 This experiment adopts a head point cloud model, which has total 12,772 3D points. Coordinates (coordinates Instruments) range as follows: Xmin=78.85, Xmax=99.01, Ymin=-221.40, Ymax=27.39, Zmin=21.88, Zmax=305.35, as shown in Fig. 7(a). Analysis the point cloud picture in Fig. 7(a) can be found in the mouth of the head model, nose, eyes and ears point cloud density was significantly larger, so try not to make a layered across the two layers of the same organ. Taking into account the coordinates of the point cloud layering principle and scope of the model is divided into LI - L6 layer according to the Z-axis direction, the Z coordinate of the layers corresponding to each range: 21.88-68, 68-74, 74-135, 135-210, 210-270, 270-305.55, which is located on the L3 layer of the mouth, nose, eyes and ears located L4 layer. The layers were treated after the algorithm, after splicing adjusted removing illegal triangle whose calculation results are shown in Fig. 7 (b), (c).

2.2. Experiment 2 Right ventricle point cloud data was chosen in the experiment, a total number of 3D points is 13,845. Coordinates (coordinates Instruments) range as follows: Xmin=14.96, Xmax= 106.65, Ymin=33.43, Ymax=125.11, Zmin=0, Zmax=44, as shown in Fig. 8 (a). Analysis of the spatial distribution of point cloud can be found in the Z direction point cloud hierarchical display, each interval 0.5mm, the model Z direction divided by 'LI - L3' layers, each layer corresponding Z coordinates are:0~15, 15-30, 30-44. The layers were treated after the algorithm, after splicing adjusted removing illegal triangle whose calculation results are shown in Fig. 8 (b), 8 (c).

2.3. Experiment 3 This experiments using skull point cloud model, totaling 20,001 3D points. Coordinates (coordinates Instruments) range as follows: Xmin=-5.4, Xmax=9.5, Ymin=-11.2, Ymax=8.5, Zmin=-10.6, Zmax=7.5, as shown in Fig. 9(a). Considering the eyes, ears, cheekbones point cloud density is relatively large, they are classified in the same layer, the hierarchical principle considered cloud point, the model is divided into L1-L4 layer in the Z direction, the Z coordinate range corresponding to each layer are: -10.6-3, -3-1, 1-4, 4-7.5. The layers were treated after the algorithm, after splicing adjusted removing illegal triangle whose calculation results are shown in Fig. 9 (b), (c).

2.4. Result Analysis As shown in Fig. 7, 8, 9, in the absence of additional information of the normal vector of point cloud, point clouds were stratified according to certain way, and projected onto a cylinder, can effectively construct a triangular surface mesh. Compared to surface reconstruction algorithm of principal component analysis, the paper less hierarchical algorithm number, the number of illegal triangles generated little stitching simple, with obvious speed advantage, running time comparing the results of two algorithms shown in Table 1.

It can be seen from Table 1, as more illegal and new triangular is generated by principal component analysis of the surface reconstruction algorithm than cutting surface reconstruction algorithm, the splicing is more complex, and more time-consuming operation. As the principal component analysis algorithm requires a method known data points vector information. Principal component analysis algorithm total time statistics do not include the normal vector computation time in Table 1, so the algorithm is much higher efficiency than the algorithm time principal component analysis.

3. Conclusions This paper presents a surface reconstruction algorithm based on 3D scattered data set, along the Z-axis direction and a certain height to hierarchical data set. After projection, plane triangle map to the triangular space, finally joining together constitute the whole surface of the 3D triangular mesh. Through experimental comparison and illustration, this paper found that the proposed algorithm compared to other triangulation-based reconstruction algorithm has the following advantages: 1) Minority block (layer), does not require a lot of experiments to determine the appropriate block parameter or threshold 2) Stitching simple, the number of illegal triangles is small, and run faster.

It should be noted that algorithms of point cloud surface shape model has certain requirements, suitable for processing the overall shape is close to columnar point cloud model, so when point cloud projection onto the corresponding cylinder, the local topological position will not change. For other shapes of the point cloud, the algorithm can be used in combination with other surface reconstruction methods. Therefore, in practice, adapt to the conditions of the proposed algorithm in this paper need to be further in-depth research.

Foundation Information Project of the National 863 programs (No: 05013323).

References [1]. Lee, I, K, Curve reconstruction from unorganized points, Computer Aided Geometric Design, Vol. 17, Issue 2,2000, pp. 161-177.

[2]. Pauly, M., Gross, M. and Kobbelt, L, Efficient simplification of point-sampled surfaces, in Proceedings of IEEE Visualization, February 2003, pp. 163-170.

[3]. Kobbelt L., Botsch M., A survey of point-based techniques in computer graphics, Computer and Graphics, Vol. 28, Issue 6,2004, pp. 801-814.

[4]. Azariadis P., Parameterization of clouds of unorganized points using dynamic base surfaces, Computer-Aided Design, Vol. 36, Issue 7, 2004, pp. 607-623.

[5]. Osher S., Sethian J. A., Fronts propagating with curvature dependent speed: algorthims based on Hamilton-Jacobi formulation, Journal of Computer Physics, Vol. 79, Issue 1, 1988, pp. 12-49.

[6]. Whitaker R., A level-set approach to 3D reconstruction from range data, International Journal of Computer Vision, Vol. 29, Issue 3, 1988, pp. 203-231.

[7]. Zhao H., Implicit and nonparametric shape reconstruction from unorganized data using a variation level set method, Computer Vision and Image Understanding, Vol. 80, Issue 3, 2001, pp. 295-314.

[8]. Franke R, Scattered Data Interpolation: Test of Some Methods, Math Compute, Vol. 38, Issue 3, 1982, pp. 181-200.

[9]. Xinwei Du, Xiaoyin Xiao, Xuezhang Liang, Implicitly using radial basis function fitting point cloud data, Journal of Jilin University (Science Edition), Vol. 48, Issue 2,2010, pp. 157-162.

[10]. Carr J., C, Beatson, Mitchell T. J, Fright W. R., McCallum B. C., Reconstruction and representation of 3D objects with radial basis functions, in Proceedings of SIGGRAPH, 2001, pp. 67-76.

[11]. Kojekine N., Hagiwara I., Savchenko V., Software tools using CSRBFs for processing scattered data, Computer and Graphics, Vol. 27, Issue 2, 2003, pp. 311-319.

[12]. Joe B., Delaunay Versus Max 2m in Solid Angle Triangulations for Three-dimensional Mesh Generation, Number Methods Eng, Vol. 31, Issue 2, 1991, pp. 987-997.

[13]. Zheng S. Y., Zhang Z. Q., Zhang Z. X., A Flexible and Automatic 3D Reconstruction Method, in Proceedings of the ISPRS Congress, Istanbul, Turkey, 2004, pp. 67-76.

[15]. Zhen Yan, Hui Zhao, Three-Dimensional Imaging System of Dairy Cow Based on Virtual Instrument, Sensors & Transducers, Vol. 163, Issue 1, 2014, pp. 121-127.

[16]. Huang Yunbao, Research on key technologies of surface reconstruction from measured points, Huazhong University of Science and Technology, Vol. 1, Issue 1,2004, pp. 10-15.

[17]. He Zhang, Jinling Yang, Xiange Cao, Based on point cloud data to reconstruct surface of the principal component analysis algorithm is proposed, Journal of Heilongjiang Institute of Engineering (Natural Science Edition), Vol. 24, Issue 1, 2010, pp. 39-42.

[18]. Qing Wang, Rongqin Wang, Hujun Bao, The increment quick surface reconstruction algorithm of scattered data points, Journal of Software, Vol. 24, Issue 1,2010, pp. 39-42.

[19]. Chayakom Netramai, Hubert Roth, Anatoly Sachenko, Real-Time 3D Path and Map Estimation Using a Multi-Camera System and a FastSLAM Algorithm, Sensors & Transducers, Vol. 24, Special Issue, 2013, pp. 58-66.

1 Weifeng XIAO,1 Min DENG,2 Chaokui LI, 1 School of Geosciences and Info-Physics, Central South University, 932 South LushanNan Road, Changsha 410083, China 2 Department of Surveying-Engineering, Hunan University of Science and Technology Taoyuan, Xiangtan, 411201, China 1 Tel.: +8613786226874, fax: 13786226874 E-mail: [email protected] Received: 15 May 2014 /Accepted: 16 June 2014 /Published: 30 June 2014 (c) 2014 IFSA Publishing, S.L.

[ Back To TMCnet.com's Homepage ]