一种基于邻域扩展聚类的去噪算法

doi:10.16182/j.issn1004731x.joss.201711010

摘要/Abstract

摘要： 针对基于二维图像重建出的带有离群点和噪声的三维点云模型,提出了一种基于邻域扩展聚类的去噪算法。通过数据点之间的欧氏距离以及相邻位置关系的可传递性,搜索每个数据点的邻域,然后对所有点进行聚类划分,从而检测和滤除点云模型中的离群点。重点讨论了点云邻域扩展聚类的概念和方法、如何利用基于动态网格划分法快速搜索点的邻域。解决了点云模型周围孤立及密集分布的离群点检测和滤除问题,提高了传统k-近邻等算法对于点云数据的去噪效率。仿真实验结果表明,该算法可有效滤除点云模型中孤立和密集分布的离群点。

关键词: 邻域扩展, 离群点, 去噪, k-近邻, 欧氏距离

Abstract: Aimed at the three dimensional point clouds model with outliers and noises which is reconstructed based on 2D images, a new denoising algorithm based on neighborhood expansion clustering is proposed. The search for other neighboring points of each data point is conducted by using the Euclidean distance between data points and the transitive property of the neighborhood location relation. All points are processed for cluster partition, which detects and filters the outliers in the point clouds model. The concept of neighborhood expansion clustering and the fast search algorithm based on dynamic grids division are discussed. It solves the problem of detecting and filtering the outliers distributed in isolation or densely around the point clouds model, which improves the efficiency of traditional k-nearest neighbor algorithm to denoise the point clouds data. Simulation results show that the proposed algorithm can effectively filter the outliers distributed in isolation or densely around the point clouds model.

Key words: neighborhood expansion, outliers, denoising, k-nearest neighbor, Euclidean distance

中图分类号:

TP391.72

李幸刚, 张亚萍, 杨雨薇. 一种基于邻域扩展聚类的去噪算法[J]. 系统仿真学报, 2017, 29(11): 2663-2670.

Li Xinggang, Zhang Yaping, Yang Yuwei. Denoising Algorithm Based on Neighborhood Expansion Clustering[J]. Journal of System Simulation, 2017, 29(11): 2663-2670.

参考文献

[1] Jaehoon J, Sungchul H, Sanghyun Y, et al. Automated 3D Wireframe Modeling of Indoor Structures from Point Clouds Using Constrained Least-Squares Adjustment for As-Built BIM[J/OL]. December, 23, 2015. Journal of Computing in Civil Engineering(S1943-5487), doi: 10.1061/(ASCE)CP.1943-5487.0000556.
[2] Diwakar M, Kumar M.CT Image Noise Reduction Based on Adaptive Wiener Filtering with Wavelet Packet Thresholding[C]// International Conference on Parallel, Distributed and Grid Computing. IEEE, Jaypee university of Information Technology, Solan, India, 2014.
[3] Mazhari M, Hasanzadeh RPR. Suppression of Noise in SEM Images Using Weighted Local Hysteresis Smoothing Filter[J/OL]. FEB, 18, 2016. Scanning (S1932-8745). DOI: 10.1002/sca.21311.
[4] Colding T, Minicozzi W I, Pedersen E.Mean Curvature Flow[J]. Bulletin of the American Mathematical Society(S0273-0979), 2015, 52(9): 4551-4587.
[5] Rodriguez-Cuenca B, Garcia-Cortes S, A study of the roughness and curvature in 3D point clouds to extract vertical and horizontal surfaces[C]// 2015 IEEE International Geoscience and Remote Sensing Symposium (S2153-6996). IEEE. Milan, 2015: 4602-4605.
[6] Angiulli F, Basta S, Lodi S, et al.GPU Strategies for Distance-based Outlier Detection[J]. IEEE Transactions on Parallel and Distributed Systems (S1045-9219), 2016 (99): 1.
[7] Plessis MCD, Shiino H, Sugiyama M.Online direct density-ratio estimation applied to inlier-based outlier detection[J]. Neural Computation(S0899-7667), 2015, 27(9): 1899-1914.
[8] Ramaswamy S, Rastogi R, Shim K.Efficient Algorithms for Mining Outliers from Large Data Sets[J]. Acm Sigmod Record(S0163-5808), 2000, 29(2): 427-438.
[9] Petrovskiy M, Convolution Kernels for Outliers Detection in Relational Data[J]. Intelligent Data Engineering and Automated Learning(S0302-9743). 2003, 2690: 661-668.
[10] Liu L, Peng F Y, Zhao K, et al.Simplified SIFT Algorithm for Fast Image Matching[J]. Infrared & Laser Engineering(S1007-2276), 2008, 37(1): 181-184.
[11] Psyllos A P, Kayafas E.Vehicle Logo Recognition Using a SIFT-Based Enhanced Matching Scheme[J]. IEEE Transactions on Intelligent Transportation Systems (S1524-9050), 2010, 11(2): 322-328.
[12] Crandall D J, Owens A, Snavely N, et al.SfM with MRFs: Discrete-Continuous Optimization for Large-Scale Structure from Motion[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence (S0162-8828), 2013, 35(12): 2841-2853.
[13] Ullman S.The Interpretation of Structure from Motion[M]//The Interpretation of Visual Motion. MIT Press, 1979: 133-175.
[14] Mandelbrot B B, Passoja D E, Paul lay A J. The Fractal Character of Fracture Surface of Metals[J]. Nature (S0028-0836), 1984, 308(19): 721-722.
[15] Schnabel R, Wahl R, Klein R.Efficient RANSAC for Point-Cloud Shape Detection[C]// Computer Graphics Forum, 2007: 214-226.
[16] Schnabel R, Wahl R, Klein R.Efficient RANSAC for Point-Cloud Shape Detection[C]// Computer Graphics Forum, 2007: 214-226.
[17] 张毅, 刘旭敏, 隋颖, 等. 基于K-近邻点云去噪算法的研究与改进[J]. 计算机应用, 2009, 29(4): 1011-1014.
Zhang Yi, Liu Xumin, Sui Ying, et al.Research and improvement of denoising method based on K-neighbors[J]. Journal of Computer Applications, 2009, 29(4): 1011-1014.
[18] 李明磊, 李广云, 宗文鹏. 激光扫描点云准确快速去噪方法[J]. 测绘通报, 2015(12): 27-29.
Li Minglei, Li Guangyun, Zong Wenpeng.Accurate and Fast Denoising Method of Laser-Scanned Point Clouds[J]. Bulletin of Surveying and Mapping, 2015(12): 27-29.
[19] 罗月童, 石放放, 张伟, 等. 结合K-D树和Shell的快速动态等值面光线跟踪法[J]. 中国图象图形学报, 2015, 20(2):193-201.
LuoYuetong, Shi Fangfang, Zhang wei, et al. Fast isosurface ray tracing method by combining K-D tree and Shell[J]. Journal of Image and Graphics, 2015, 20(2): 193-201.
[20] 马骊溟, 徐毅, 李泽湘. 基于动态网格划分的散乱点k邻近快速搜索算法[J]. 计算机工程, 2008, 34(8): 10-11.
Ma Liming, Xu Yi, LiZexiang. Fast k-nearest Neighbors Searching Algorithm for Scattered PointsBased on Dynamic Grid Decomposition[J]. Computer Engineering, 2008, 34(8): 10-11.
[21] Bo S, Du J, Tian G.Study on the Improvement of K-Nearest-Neighbor Algorithm[C]// Artificial Intelligence and Computational Intelligence, International Conference on. IEEE, University of Louisville, Louisville, USA, 2009: 390-393.