DBSCAN point cloud clustering

1、DBSCAN Algorithm principle

DBSCAN It is a clustering method based on density , It divides points into core points and non core points , In the future, similar regional growth methods will be adopted . The following figure for DBSCAN Clustering results , It can be seen that it can cluster any kind of data , There is no need to define the number of categories .

DBSCAN Cluster description

DBSCAN The clustering process is as follows ：
1、 First ,DBSCAN The algorithm will take any starting data point that has not been accessed as the core , And expand the core point . Then we give a radius / distance ε, Any distance from the core point is less than ε The points of are all its adjacent points .
2、 If there are enough points near the core , Then start clustering , And the selected core point will become the first point of the cluster . If there are not enough points nearby , The algorithm will mark it as noise （ Then the noise may become part of the cluster ）. In both cases , The selected points will be marked “ Visited ”.
3、 Once clustering starts , Adjacent points of the core , Or all density connected data points starting from this point （ Notice that the density is connected ） Will be divided into the same cluster . Then we take these new points as the core , Expand around ε, And the qualified points will continue to be included in this cluster .
4、 Repeat step 2 and 3, Until there are no data points nearby that can be expanded , Namely clustered ε All points in the neighborhood have been marked “ Visited ”.
5、 Once we finish the cluster , The algorithm will start to retrieve the points that have not been visited , And find more clustering and noise . Once the data is retrieved , Each point is marked as belonging to a cluster or noise .
Compared with other clustering algorithms ,DBSCAN There are some great advantages . First , It does not need to input the number of clusters to be divided . secondly , Even if the data points are very different , It will also include them in clustering ,DBSCAN Can recognize outliers as noise , This means that it can input noise filtering parameters when necessary . Third , It has no bias on the shape of clustering , You can find clusters of any size and shape .
DBSCAN The main drawback of , When the density of clustering is different ,DBSCAN Its performance will be inferior to other algorithms . This is because when the density changes , The distance threshold used to identify adjacent points ε And core points will change with clustering . And this will be particularly obvious in high-dimensional data , Because it will be difficult for us to estimate ε.

From the existing clustering effect , Define some points as noise points , No clustering . Therefore, it can also be understood as ： First, denoise the points , Then use distance clustering （ Such as Euclidean clustering ） Realize the clustering of points .
The clustering results of 3D point cloud data are as follows ：

2、 Source download

be based on C++ Write the source code download address ：
https://download.csdn.net/download/qq_32867925/86246799
Just load three header files into the project

DBSCAN Core code ：

	DBSCANKdtreeCluster<pcl::PointXYZ> ec;
	ec.setCorePointMinPts(10);

	// test 4. uncomment the following line to test the EuclideanClusterExtraction
	// pcl::EuclideanClusterExtraction<pcl::PointXYZ> ec;
	pcl::search::KdTree<pcl::PointXYZ>::Ptr tree(new pcl::search::KdTree<pcl::PointXYZ>);
	tree->setInputCloud(cloud);
	std::vector<pcl::PointIndices> cluster_indices;

	ec.setClusterTolerance(0.1);// Search the radius of the nearest neighbor 
	ec.setMinClusterSize(100);// Minimum cluster number requirements 
	ec.setMaxClusterSize(5000000);// Maximum cluster number limit 
	ec.setSearchMethod(tree);
	ec.setInputCloud(cloud);
	ec.extract(cluster_indices);

	clock_t end_ms = clock();
	std::cout << "cluster time cost:" << double(end_ms - start_ms) / CLOCKS_PER_SEC << " s" << std::endl;
	pcl::PointCloud<pcl::PointXYZI>::Ptr cloud_clustered(new pcl::PointCloud<pcl::PointXYZI>);
	int j = 0;
	// visualization, use indensity to show different color for each cluster.
	for (std::vector<pcl::PointIndices>::const_iterator it = cluster_indices.begin(); it != cluster_indices.end(); it++, j++) {
    
		for (std::vector<int>::const_iterator pit = it->indices.begin(); pit != it->indices.end(); ++pit) {
    
			pcl::PointXYZI tmp;
			tmp.x = cloud->points[*pit].x;
			tmp.y = cloud->points[*pit].y;
			tmp.z = cloud->points[*pit].z;
			tmp.intensity = j % 8;
			cloud_clustered->points.push_back(tmp);
		}
	}

2、 Clustering effect

From another point of view ,DBSCAN Is another form of distance clustering , Compared with conventional distance clustering , More core point discrimination process .