Adaptive simplification of point cloud using k-means clustering

3D scanning devices usually produce huge amounts of dense points, which require excessively large storage space and long post-processing times. This paper presents a new adaptive simplification method to reduce the number of the scanned dense points. An automatic recursive subdivision scheme is designed to pick out representative points and remove redundant points. It employs the k-means clustering algorithm to gather similar points together in the spatial domain and uses the maximum normal vector deviation as a measure of cluster scatter to partition the gathered point sets into a series of sub-clusters in the feature field. To maintain the integrity of the original boundary, a special boundary detection algorithm is developed, which is run before the recursive subdivision procedure. To avoid the final distribution of the simplified points to become locally greedy and unbalanced, a refinement algorithm is put forward, which is run after the recursive subdivision procedure. The proposed method may generate uniformly distributed sparse sampling points in the flat areas and necessary higher density in the high curvature regions. The effectiveness and performance of the novel simplification method is validated and illustrated through experimental results and comparison with other point sampling methods. (C) 2011 Elsevier Ltd. All rights reserved.