## Jiaxing Wei* , Maolin Xu* and Hongling Xiu*## |

Data | Numbers of original point clouds | Threshold (m) | Numbers of thinned point clouds | Rate (%) | Time (s) |
---|---|---|---|---|---|

Rabbit | 35,947 | [TeX:] $$d_{s}=0.05, d_{h}=0.1$$ | 6,557 | 82 | 0.173 |

Mine | 92,583 | [TeX:] $$d_{s}=0.5, d_{h}=0.8$$ | 28,199 | 70 | 0.265 |

Residential area | 683,204 | [TeX:] $$d_{s}=1.5, d_{h}=0.5$$ | 308,865 | 55 | 0.448 |

In general, the thinning rate can judge the efficiency of point clouds thinning, and the thinning time has ability to describe the complexity of the algorithm. The most important thing is whether the thinned point clouds have an influence on the later application. To further illustrated, the 3D view of point clouds after thinning is shown in Fig. 3.

From Fig. 3 we can find that the original contours of three datasets are retained, and the curvature characteristics of original point clouds are well preserved. Due to the large number of point clouds in residential areas, the point clouds after thinning is not obvious on the display of Stanford rabbits. It’s more representative for open-pit mine, because the original point clouds are dense. The number of point clouds in the part of few point clouds remains unchanged, which makes the characteristics of point clouds be well preserved. Since the open-pit mine point clouds perform the best visualization and with large enough area, we only adopt the open-pit mine point clouds as the test object for the comparison with other algorithms.

In order to test the stability of our proposed algorithm, the octree-based region growing algorithm is adopted to compare with the fast thinning algorithm [6]. The octree-based region growing algorithm is demonstrated to be a robust method with accurate thinning results, and this method is cited by many other studies. It should be also emphasized that consider the scale and characteristics of original point clouds, the open-pit mine is involved for the further analysis. Although the threshold setting of our proposed algorithm is different from the contrast one, the height difference threshold of fast thinning method can be approximately regarded as the height of closed minimum cube in octree-based region growing algorithm. Thereafter, the size threshold of the minimum voxel used in octree method can be regarded as the distance difference threshold of the fast thinning method. Therefore, following the above rules, we have enough reasons to compare two different algorithms. Specifically, the octree-based region growing algorithm taking the segmented nodes as index, but the principle of the segmented node is similar to that of the sample points in the fast thinning algorithm. By means of the above threshold setting, the point clouds of open-pit mine are thinned by our proposed method and octree-based region growing algorithm, respectively. The comparison of point clouds thinning by above two algorithms are shown in Table 2.

Table 2.

Algorithm | Original point clouds numbers | Thinned point clouds numbers | Rate(%) | Time(s) | Operation times | Memory profiler (%) |
---|---|---|---|---|---|---|

Octree-based region growing | 92,583 | 34,083 | 63 | 17.3 | [TeX:] $$t \leq 2^{*} n$$ | 33 |

Fast thinning | 92,583 | 37,923 | 61 | 0.3 | [TeX:] $$t \leq 8 * n$$ | 26 |

From Table 2 we can learn that the fast thinning algorithm proposed in this paper is superior to the octree-based region growing algorithm in thinning time. Meanwhile, the thinning rate of fast thinning method is similar to octree-based region growing algorithm. The advantage in thinning time is mainly reflected in the simple index and less computing times. In addition, the memory profiler of octree-based region growing occupies 33%, and our proposed algorithm is 26%. This lies in the method of spatial index established and the times of index traversed, this also demonstrates the simplicity of our fast thinning algorithm. It can be seen that the advantage of octree-based region growing algorithm lies in the construction of spatial index (see Fig. 4). In terms of visualization, octree-based region growing algorithm has a more compact organization, while fast thinning algorithm behaves more chaotic than former. Point clouds are ultimately used in model reconstruction and other applications, so we will further validate the visualization of point clouds model.

In order to avoid the subjectivities in point clouds visualization, we model the two kinds of thinned point clouds, respectively. The cubic method with interpolation function is adopted for point clouds modelling [19,20]. The visualization of modelled point clouds by above two algorithms are presented in Fig. 5. There is no significant difference in the point clouds model and the contour of entire target. Although the point clouds visualization in Fig. 4 is different, the model reconstruction result is basically similar.

The above comparison is presented in a 2D view, and it’s difficult to observe the detail changes in local contours. Consequently, we extract the contours of thinned point clouds, which is shown in Fig. 6. The contours are defined by x and y coordinates, and points with the same elevation are connected into a curve. That means contours have advantage in the expression of variations in different height layers. The contours variation in high region is basically identical, and there is a small deviation in the central region. The bottom contours produced by fast thinning algorithm is smoother than octree algorithm, and octree algorithm has obvious turbulence and low divergence. The main difference lies in the existence of holes at the bottom of open-pit mine in fast thinning algorithm, which causes the area become smoothed when contours are established. The reason can be interpreted by the difference of initial setting in distance and height difference thresholds.

The above comparisons of point clouds and corresponding model belong to qualitative analysis, and the deviation of point clouds to model is used as the quantitative analysis method for the comparison of two algorithms. The initial model adopted to overlay analysis is built by the original point clouds, which is not thinned. At the same time, the cubic interpolation is still adopted to model construction. The thinned point clouds are overlaid to the model, the interval and weight of deviation distance are taken as the indicators for quantitative comparison. This method can directly determine the influence of point clouds thinning algorithm on model construction, because the cubic interpolation applied to two thinned point clouds has never changed. Therefore, if a local point is lost, the interpolation algorithm will automatically match another point to draw a triangle. This may indirectly affect the shape of the entire model [21].

The deviation interval and weight of point clouds to model superimposed by two algorithms are presented in Fig. 7. It is not difficult to find that the deviation interval in point clouds to model is mainly distributed at -1.5 mm to 1.5 mm. When the deviation is 1.5 mm, two kinds of weights are located at 3% to 5%. When the deviation is 1.0 mm, these two weights are occupied at 40% to 42%. And when the deviation is 1.0 mm, the weights are located at 38% to 40%. When the deviation is 1.5 mm, both two weights are located at 3% to 5%. Through the superposition analysis of point clouds to model, we conclude that although the fast thinning algorithm is slightly different from the octree algorithm in point clouds and model visualization, these differences are not significant to affect the quality of model construction. As a result, the above validation further illustrates the robust of our proposed algorithm.

This paper proposes a point clouds fast thinning algorithm, to overcome the shortcomings of complex classification index and long-time consuming in existing point clouds thinning algorithms. Compared with the octree-based region growing algorithm, our proposed algorithm has disadvantages in the visu¬alization of point clouds and model. However, we obtain certain advantages in the thinning and modeling time, and the thinning rate has reached a level of octree-based region growing algorithm. The algorithm used in this paper illustrates the rapidity and stability of point clouds thinning, which would be useful for small and medium-sized users.

The algorithm proposed in this paper is similar to most existing algorithms, which always needs to set the thresholds in advance. In theory, the threshold problem is unavoidable in current point clouds thinning domain, because the users need to thin their point clouds in their different applications. Therefore, our future work will focus the threshold reduction. Besides, we will consider the application of our proposed algorithm, it will be useful for the fast feature extraction, fast model construction and related aspects.

- 1 X. Yang, L. W. Clements, M. Luo, S. Narasimhan, R. C. Thompson, B. M. Dawant, M. I. Miga, "Stereovision-based integrated system for point cloud reconstruction and simulated brain shift validation,"
*Journal of Medical Imaging*, vol. 4, no. 3, 2017.custom:[[[-]]] - 2 P. Grussenmeyer, O. Al Khalil, "From metric image archives to point cloud reconstruction: case study of the Great Mosque of Aleppo in Syria," in
*Proceedings of International Archives of the Photogrammetry*, Remote Sensing & Spatial Information Sciences, Ottawa, Canada, 2017;pp. 295-301. custom:[[[-]]] - 3 A. K. Patil, P. Holi, S. K. Lee, Y. H. Chai, "An adaptive approach for the reconstruction and modeling of as-built 3D pipelines from point clouds,"
*Automation in Construction*, vol. 75, pp. 65-78, 2017.custom:[[[-]]] - 4 E. El-Sayed, R. F. Abdel-Kader, H. Nashaat, M. Marei, "Plane detection in 3D point cloud using octree-balanced density down-sampling and iterative adaptive plane extraction,"
*IET Image Processing*, vol. 12, no. 9, pp. 1595-1605, 2018.doi:[[[10.1049/iet-ipr.2017.1076]]] - 5 M. Pauly, M. Gross, L. P. Kobbelt, "Efficient simplification of point-sampled surfaces," in
*Proceedings of IEEE Visualization*, Boston, MA, 2002;pp. 163-170. custom:[[[-]]] - 6 A. V. Vo, L. Truong-Hong, D. F. Laefer, M. Bertolotto, "Octree-based region growing for point cloud segmentation,"
*ISPRS Journal of Photogrammetry and Remote Sensing*, vol. 104, pp. 88-100, 2015.custom:[[[-]]] - 7 S. Pamela, "A data density reduction algorithm for Post-processed airborne lidar bathymetric survey data,"
*Ph.D. dissertationUniversity of Florida, FL*, 2000.custom:[[[-]]] - 8 H. Woo, E. Kang, S. Wang, K. H. Lee, "A new segmentation method for point cloud data,"
*International Journal of Machine Tools and Manufacture*, vol. 42, no. 2, pp. 167-178, 2002.custom:[[[-]]] - 9 T. Liu, Z. Xu, C. M. Sha, J. T. Zhao, "Curvature estimation of scattered-point cloud data based on bounding box method,"
*Science Technology and Engineering*, vol. 9, no. 12, pp. 3333-3336, 2009.custom:[[[-]]] - 10 P. Burger, H. J. Wuensche, "Fast multi-pass 3D point segmentation based on a structured mesh graph for ground vehicles," in
*Proceedings of 2018 IEEE Intelligent V ehicles Symposium (IV)*, Changshu, China, 2018;pp. 2150-2156. custom:[[[-]]] - 11 L. Pagani, P. J. Scott, "Curvature based sampling of curves and surfaces,"
*Computer Aided Geometric Designviol. 59*, pp. 32-48, 2018.doi:[[[10.1016/j.cagd.2017.11.004]]] - 12 Y. Wang, Y. Ma, A. X. Zhu, H. Zhao, L. Liao, "Accurate facade feature extraction method for buildings from three-dimensional point cloud data considering structural information,"
*ISPRS Journal of Photo-grammetry and Remote Sensing*, vol. 139, pp. 146-153, 2018.custom:[[[-]]] - 13 R. Schnabel, R. Wahl, R. Klein, "Efficient RANSAC for point-cloud shape detection,"
*Computer Graphics Forum*, vol. 26, no. 2, pp. 214-226, 2007.doi:[[[10.1111/j.1467-8659.2007.01016.x]]] - 14 R. Schnabel, R. Klein, "Octree-based point-cloud compression," in
*Proceedings of 3rd Eurographics/ IEEE VGTC Conference on Point-Based Graphics*, Boston, MA, 2009;pp. 111-120. custom:[[[-]]] - 15 H. Song, H. Y. Feng, "A global clustering approach to point cloud simplification with a specified data reduction ratio,"
*Computer-Aided Design*, vol. 40, no. 3, pp. 281-292, 2008.doi:[[[10.1016/j.cad.2007.10.013]]] - 16 H. Han, X. Han, F. Sun, C. Huang, "Point cloud simplification with preserved edge based on normal vector,"
*Optik-International Journal for Light and Electron Optics*, vol. 126, no. 19, pp. 2157-2162, 2015.custom:[[[-]]] - 17 X. Yang, K. Matsuyama, K. Konno, Y. Tokuyama, "Feature-preserving simplification of point cloud by using clustering approach based on mean curvature,"
*The Society for Art and Science*, vol. 14, no. 4, pp. 117-128, 2015.custom:[[[-]]] - 18 T. Whelan, L. Ma, E. Bondarev, P. H. N. de With, J. McDonald, "Incremental and batch planar simplification of dense point cloud maps,"
*Robotics and Autonomous Systems*, vol. 69, pp. 3-14, 2015.doi:[[[10.1016/j.robot.2014.08.019]]] - 19 F. N. Fritsch, R. E. Carlson, "Monotone piecewise cubic interpolation,"
*SIAM Journal on Numerical Analysis*, vol. 17, no. 2, pp. 238-246, 1980.custom:[[[-]]] - 20 H. T. Huynh, "Accurate monotone cubic interpolation,"
*SIAM Journal on Numerical Analysis*, vol. 30, no. 1, pp. 57-100, 1993.custom:[[[-]]] - 21 K. W. Brodlie, S. Butt, "Preserving convexity using piecewise cubic interpolation,"
*Computers & Graphics*, vol. 15, no. 1, pp. 15-23, 1991.doi:[[[10.1016/0097-8493(91)90026-E]]]