融合高斯核及指数函数聚类的点云目标物提取

doi:10.3969/j.issn.0255-8297.2022.03.005

摘要/Abstract

摘要： 针对聚类算法的聚类中心重复性和无法对点云聚类的问题，提出了融合高斯核及指数函数的聚类中心均匀化的点云聚类方法，以优化聚类中心的均匀化分布，实现点云的均匀化聚类。首先，根据高斯核函数及密度指数函数确定局部密度，再依据局部密度的大小确定距离参数。其次，依据局部密度和距离参数的乘积确定聚类中心，同时消除聚类中心的邻近化，使得聚类中心更加均匀分布于整个数据集中。最后，利用数据点到聚类中心距离逐个确定每个数据的聚类归属，并合并邻近聚类实现点云目标物的提取。将该算法与常规的基于密度峰值的聚类算法（clustering function based on density peak,CFDP）、K-means聚类算法、具有噪声的基于密度的聚类方法（density-based spatial clustering of applications with noise,DBSCAN）进行比较，该文所提方法可以对教室内3排椅子实现100%的提取。与相对密度关系的峰值聚类（density peak clustering,DPC）算法及深度学习方法相比，所提方法对不同分辨率目标物点云的提取精度均为96.7%，在计算效率和精度方面均优于其他两种方法。

关键词: 目标提取, 分类, 分割, 密度聚类

Abstract: In view of problems of repeatability of cluster center and disability of conducting point cloud clustering, a point cloud clustering method of clustering center homogenization combining Gaussian kernel and exponential function is proposed to optimize homogenization distribution of cluster centers and achieve the homogeneous clustering of point cloud. Firstly, local density is determined according to the Gaussian kernel function and density exponential function, and distance parameters are determined according to the size of local density. Then cluster centers are determined according to the product of the local density and distance parameters, and the proximity of the cluster centers is eliminated, so that the cluster centers are more evenly distributed in the entire data set. Finally, the distances between the data point and the cluster centers are used to determine the cluster attribution of each data, and the neighboring clusters are combined to achieve the extraction of the point cloud target. This algorithm is compared with the clustering function based on density peak (CFDP), K-means clustering algorithm, DBSCAN (density-based spatial clustering of applications with noise) algorithm, and the advantages of clustering algorithm in this paper are confirmed. Compared with the DPC algorithm and the deep learning method, the accuracy of objects point cloud extraction with different resolutions is 96.7%. The proposed method is prior than the other two methods in terms of computational efficiency and precision.

Key words: object extraction, classify, segmentation, density-based clustering

中图分类号:

TP201

陈西江, 安庆, 班亚, 王德欣, 李坤, 刘海鹏. 融合高斯核及指数函数聚类的点云目标物提取[J]. 应用科学学报, 2022, 40(3): 411-422.

CHEN Xijiang, AN Qing, BAN Ya, WANG Dexin, LI Kun, LIU Haipeng. Point Cloud Object Extraction Based on Gaussian Kernel Function and Exponential Function Clustering[J]. Journal of Applied Sciences, 2022, 40(3): 411-422.

参考文献

[1] Jain A K, Murty M N, Flynn P J. Data clustering:a review[J]. ACM Computing Surveys, 1999, 31(3):264-323.
[2] Han J W. Data mining:concepts and techniques[M]. San Francisco:Morgan Kaufmann Publishers Inc., 2005.
[3] 贺一波,陈冉丽,吴侃,等.基于K-means聚类的点云精简方法[J].激光与光电子学进展, 2019, 56(9):96-99. He Y B, Chen R L, Wu K, et al. Point cloud simplification method based on K-means clustering[J]. Laser&Optoelectronics Progress, 2019, 56(9):96-99.(in Chinese)
[4] Park H S, Jun C H. A simple and fast algorithm for K-medoids clustering[J]. Expert Systems with Applications, 2009, 36(2):3336-3341.
[5] Ng R T, Han J. CLARANS:a method for clustering objects for spatial data mining[J]. IEEE Transactions on Knowledge&Data Engineering, 2002, 14(5):1003-1016.
[6] Zhang T, Ramakrishnan R, Livny M. BIRCH:an efficient data clustering method for very large databases[C]//Proceedings of ACM SIGMOD International Conference on Management of Data, 1996:103-114.
[7] 范小辉,许国良,李万林,等.基于深度图的三维激光雷达点云目标分割方法[J].中国激光, 2019, 46(7):292-299. Fan X H, Xu G L, Li W L, et al. Target segmentation method for three-dimensional LiDAR point cloud based on depth image[J]. Chinese Journal of Lasers, 2019, 46(7):292-299.(in Chinese)
[8] D'urso P, Massari R. Fuzzy clustering of mixed data[J]. Information Sciences, 2019, 505:513-534.
[9] 张帆.一种基于数据场改进的CLARA聚类算法[C]//2004计算机应用技术交流会议, 2004:265-267.
[10] 李玉鹏.基于分布式平台的聚类算法研究[D].哈尔滨:哈尔滨工程大学, 2014.[1] Jain A K, Murty M N, Flynn P J. Data clustering:a review[J]. ACM Computing Surveys, 1999, 31(3):264-323.
[2] Han J W. Data mining:concepts and techniques[M]. San Francisco:Morgan Kaufmann Publishers Inc., 2005.
[3] 贺一波,陈冉丽,吴侃,等.基于K-means聚类的点云精简方法[J].激光与光电子学进展, 2019, 56(9):96-99. He Y B, Chen R L, Wu K, et al. Point cloud simplification method based on K-means clustering[J]. Laser&Optoelectronics Progress, 2019, 56(9):96-99.(in Chinese)
[4] Park H S, Jun C H. A simple and fast algorithm for K-medoids clustering[J]. Expert Systems with Applications, 2009, 36(2):3336-3341.
[5] Ng R T, Han J. CLARANS:a method for clustering objects for spatial data mining[J]. IEEE Transactions on Knowledge&Data Engineering, 2002, 14(5):1003-1016.
[6] Zhang T, Ramakrishnan R, Livny M. BIRCH:an efficient data clustering method for very large databases[C]//Proceedings of ACM SIGMOD International Conference on Management of Data, 1996:103-114.
[7] 范小辉,许国良,李万林,等.基于深度图的三维激光雷达点云目标分割方法[J].中国激光, 2019, 46(7):292-299. Fan X H, Xu G L, Li W L, et al. Target segmentation method for three-dimensional LiDAR point cloud based on depth image[J]. Chinese Journal of Lasers, 2019, 46(7):292-299.(in Chinese)
[8] D'urso P, Massari R. Fuzzy clustering of mixed data[J]. Information Sciences, 2019, 505:513-534.
[9] 张帆.一种基于数据场改进的CLARA聚类算法[C]//2004计算机应用技术交流会议, 2004:265-267.
[10] 李玉鹏.基于分布式平台的聚类算法研究[D].哈尔滨:哈尔滨工程大学, 2014. 422应用科学学报第40卷
[11] Zheng Z, Gong M, Ma J, et al. Unsupervised evolutionary clustering algorithm for mixed type data[C]//Proceedings of IEEE Congress on Evolutionary Computation, 2010.
[12] 成卫青,卢艳红.一种基于最大最小距离和SSE的自适应聚类算法[J].南京邮电大学学报(自然科学版), 2015, 35(2):102-107. Cheng W Q, Lu Y H. Adaptive clustering algorithm based on maximum and minimum distance, and SSE[J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2015, 35(2):102-107.(in Chinese)
[13] 胡伟.改进的层次K均值聚类算法[J].计算机工程与应用, 2013, 49(2):157-159. Hu W. Improved hierarchical K-means clustering algorithm[J]. Computer Engineering and Applications, 2013, 49(2):157-159.(in Chinese)
[14] 谢娟英,屈亚楠.密度峰值优化初始中心的K-medoids聚类算法[J].计算机科学与探索, 2016, 10(2):230-247. Xie J Y, Qu Y N. K-medoids clustering algorithms with optimized initial seeds by density peaks[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(2):230-247.(in Chinese)
[15] Zhang T, Ramakrishnan R, Livny M. BIRCH:an efficient data clustering method for very large databases[C]//Proceedings of ACM SIGMOD International Conference on Management of Data, 1996, 25:103-114.
[16] Guha S, Rastogi R, Shim K. Cure:an efficient clustering algorithm for large databases[J]. Information Systems, 2001, 26(1):35-58.
[17] Ester M, Kriegel H P, Sander J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, 1996:226-231.
[18] Sander J, Ester M, Kriegel H P, et al. Density-based clustering in spatial databases:the algorithm GDBSCAN and its applications[J]. Data Mining and Knowledge Discovery, 1998, 2(2):169-194.
[19] Birant D, Kut A. ST-DBSCAN an algorithm for clustering spatial-temp oral data[J]. Data&Knowledge Engineering, 2007, 60(1):208-221.
[20] He Y, Tan H, Luo W, et al. MR-DBSCAN:an efficient parallel density-based clustering algorithm using mapreduce[C]//The 17th IEEE International Conference on Parallel and Distributed Systems (ICPADS), 2011:473-480.
[21] Ankerst M, Breunig M, Kriegel H P, et al. OPTICS:ordering points to identify the clustering structure[C]//Proceedings of 1999 ACM SIGMOD, 1999:49-60.
[22] Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492-1496.
[23] Chang H, Yeung D Y. Robust path-based spectral clustering[J]. Pattern Recognition, 2008, 41(1):191-203.
[24] Gionis A, Mannila H, Tsaparas P. Clustering aggregation[J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2007, 1(1):1-30.
[25] 陈西江,章光,花向红.于法向量夹角信息熵的点云简化算法[J].中国激光, 2015, 42(8):336-344. Chen X J, Zhang G, Hua X H. Point cloud simplification based on the information entropy of normal vector angle[J]. Chinese Journal of Lasers, 2015, 42(8):336-344.(in Chinese)
[26] Sun Y, Zhu Q M, Chen Z X. An iterative initial-points refinement algorithm for categorical data clustering[J]. Pattern Recognition, 2002, 23(7):875-884.
[27] Landrieu L, Boussaha M. Point cloud over segmentation with graph-structured deep metric learning[C]//2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019:7432-7441.
[28] Hou J, Aihua Z, Naiming Q. Density peak clustering based on relative density relationship[J]. Pattern Recognition, 2020, 108(107554):1-16.