Research On Laser Point Cloud Clustering Algorithm Based On Harmony Search Optimization

In the environmental perception system of intelligent ships,LiDAR,as an active,non-contact sensing technology,has the advantages of high sensitivity,high resolution,wide detection range,strong anti-interference ability and work around the clock,which provides safety guarantee for ship’s autonomous cruise.Compared with the two-dimensional plane images,the three-dimensional laser point cloud images are less affected by illumination,provide rich spatial information,and have gradually become the mainstream.However,the original images collected by LiDAR are massive,sparse,and disordered set of points,also contain a large number of noise and abnormal points.In order realize the detection,recognition and tracking of the surrounding targets,extracting different objects effectively through point cloud segmentation is an important research field of point cloud data processing.At present,there are many types of point cloud segmentation methods.Among them,the technology based on clustering is relatively stable and commonly used,since it is not limited by the spatial relationship.As an unsupervised learning method,clustering divides the data set into different clusters according to a specific criterion under the condition of lack of labels,so that the similarity of samples within the same cluster and the dissimilarity of samples between different clusters can be maximized as possible.For the variety clustering algorithms,K-means and DBSCAN(Density-Based Spatial Clustering of Application with Noise)are the two most classical and widely used ways.However,both K-means and DBSCAN have different degrees of limitations while giving full paly to their clustering advantages.How to efectively solve their drawbacks and improve the clustering performance is of great research value to the realization of point cloud segmentation.Generally,clustering can be attributed to a form of combinatorial optimization problem,and heuristic optimization algorithms with good performance provide solutions for improving clustering analysis,which have achieved some effectiveness.The Harmony Search(HS)optimization algorithm generated by mimicking the principle of music performance has been widely studied and applied at present,due to its simple concept,easy implementation as well as high optimization efficiency.However,the existing harmony search methods still need to improve the optimization performance in numerical solutions.Therefore,in this thesis,taking the laser point cloud segmentation of ships as the research background,aiming to improve the clustering performance of K-means and DBSCAN as the research goal,taking the harmony search optimization as the research approach,and put forward new clustering schemes respectively.The specific research works are summarized as follows:(1)Aiming at the low optimization accuracy,premature convergence and weak stability of the HS algorithm,by analyzing the working principle of it,three important factors that affecting the performance of the algorithm are discussed,including pitch adjustment,random selection and memory consideration.The improved differential-based harmony search algorithm with linear dynamic domain(ID-HS-LDD)is proposed by the improved strategies.A comprehensive comparison experiment is carried out using the benchmark functions,and the test results not only show the effectiveness of the improved strategies,but also the ID-HS-LDD performs better than other optimization methods.(2)Aiming at the problem that the partition clustering algorithms including K-means require to predetermining the suitable number of clusters,an automatic clustering algorithm based on dynamic parameter harmony search,i.e.AC-DPHS,is proposed by combining improved HS and K-means.Firstly,based on the previous research of HS,in order to reduce manual settings and enhance the adaptability of the algorithm,the dynamic parameter harmony search(DPHS)is generated by adjusting the forms of main parameters.Secondly,taking the harmony vectors in DPHS as the cluster centers,an appropriate cluster evaluation index is selected as its fitness function,the optimal number of clusters and cluster center points can be automatically obtained.Thus,the division of clusters can be realized according to the principle of the nearest distance.Numerical experiments showed that the clustering results of AC-DPHS are closer to the ground truth than other automatic clustering schemes.Using the AC-DPHS for laser point cloud clustering,different ships are automatically segmented and have a high degree of discrimination.(3)Aiming at the problems that DBSCAN cannot determine the clustering parameters well and the clustering efficiency is relatively low,combined with the grid models,a new clustering scheme named dual grid-based DBSCAN,i.e.DG-DBSCAN,is proposed.In DG-DBSCAN,the inner grid model is used to divide the data set and create a set of grid cells.According to the information statistics of these grid cells,the appropriate clustering parameter values can be obtained.The outer grid model is used to limit the range when searching neighborhood points,so as to reduce the amount of calculation and reducing the clustering time.Numerical experiments show that DG-DBSCAN can get satisfactory clustering results and improve the clustering efficiency.Using the DG-DBSCAN for laser point cloud clustering,the algorithm can segment different ships when there are relatively few noise points.(4)Under the condition that the number of clusters K is specified in advance,in order to find clusters of arbitrary shapes and identify noise points or outliers,by combining the improved HS and DBSCAN,the K-DBSCAN clustering is proposed.Firstly,based on the previous research of HS,to improve the optimization efficiency,the novel harmony search(Novel-HS)is generated by adjusting the structure form.Secondly,take the harmony vectors in Novel-HS as the clustering parameters,and according to a designed multi-objective optimization function,the optimal clustering parameter values can be got.Finally,the number of K arbitrary shape clusters can be found by DBSCAN.Numerical experiments show that K-DBSCAN has better clustering results compared with other methods.Using K-DBSCAN for laser point cloud clustering,different ships are successfully segmented and low-density noise points can be effectively identified.The research in this thesis not only improves the optimization ability of HS,but also uses the improved HS for clustering which can obtain better performance and effectively realize the LiDAR point cloud segmentation.In addition,the thesis also provides new ideas for future clustering research based on heurisitic optimization algorithms.