在第（3）實現了地面點與障礙物的分離，此部分要實現的是聚類，聚類是指把不同物體的點云分別組合聚集起來, 從而能讓你跟蹤汽車, 行人等多個目標. 其中一種對點云數據進行分組和聚類的方法稱為歐氏聚類。

歐式聚類是指將距離緊密度高的點云聚合起來. 為了有效地進行最近鄰搜索, 可以使用 KD-Tree 數據結構, 這種結構平均可以加快從 o (n)到 o (log (n))的查找時間. ?這是因為Kd-Tree允許你更好地分割你的搜索空間. ?通過將點分組到 KD-Tree 中的區域中, 您可以避免計算可能有數千個點的距離, 因為你知道它們不會被考慮在一個緊鄰的區域中.

作者羅列了兩種方式的歐式聚類第一種是自己重寫了歐式聚類跟k-dtree，第二種是直接調用PCL庫里邊的歐式聚類。以下是兩種方式的記錄便于學習。

第一種：Manual Euclidean clustering

除此之外我們也可以直接使用KD-Tree進行歐氏聚類.
在此我們首先對KD-Tree的原理進行介紹. KD-Tree是一個數據結構, 由二進制樹表示, 在不同維度之間對插入的點的數值進行交替比較, 通過分割區域來分割空間, 如在3D數據中, 需要交替在X,Y,Z不同軸上比較. 這樣會使最近鄰搜索可以快得多.
首先我們在試著二維空間上建立KD-Tree, 并講述歐氏聚類的整個在二維空間上的實現過程, 最終我們將擴展到三維空間.

在KD-Tree中插入點(這是將點云輸入到樹中創建和構建KD-Tree的步驟)
假設我們需要在KD-Tree中插入４個點(-6.3, 8.4), (-6.2, 7), (-5.2, 7.1), (-5.7, 6.3)
首先我們得確定一個根點(-6.2, 7), 第0層為x軸, 需要插入的點為(-6.3, 8.4), ?(-5.2, 7.1), 因為-6.3<-6.2,(-6.3, 8.4)劃分為左子節點, 而-5.2>-6.2, (-5.2, 7.1)劃分為右子節點. (-5.7, 6.3)中x軸-5.7>-6.2,所以放在(-5.2, 7.1)節點下, 接下來第1層使用y軸, 6.3<7.1, 因此放在(-5.2, 7.1)的左子節點. 同理, 如果我們想插入第五個點(7.2, 6.1), 你可以交替對比x,y軸數值, (7.2>-6.2)->(6.1<7.1)->(7.2>-5.7), 第五點應插入到(-5.7, 6.3)的右子節點C.
下圖是KD-Tree的結構.
?

?

第二種：PCL Euclidean clustering

首先我們使用PCL內置的歐式聚類函數. 點云聚類的具體細節推薦查看PCL的官網文檔。

歐氏聚類對象 ec 具有距離容忍度. ?在這個距離之內的任何點都將被組合在一起. ?它還有用于表示集群的點數的 min 和 max 參數. ?如果一個集群真的很小, 它可能只是噪音, min參數會限制使用這個集群. ?而max參數允許我們更好地分解非常大的集群, ?如果一個集群非常大, 可能只是許多其他集群重疊, 最大容差可以幫助我們更好地解決對象檢測. ?歐式聚類的最后一個參數是 Kd-Tree. ?Kd-Tree是使用輸入點云創建和構建的, 這些輸入點云是初始點云過濾分割后得到障礙物點云.

聚類結果可視化顯示：

?

#include <iostream>
#include <pcl/io/io.h>
#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
#include <pcl/visualization/cloud_viewer.h>
#include <pcl/segmentation/sac_segmentation.h>
#include <pcl/segmentation/extract_clusters.h>
#include <pcl/kdtree/kdtree.h>
#include <pcl/common/common.h>
#include <unordered_set>using namespace std;
using namespace pcl;int main()
{pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);pcl::PCDReader reader;reader.read("F:\\SFND_Lidar_Obstacle_Detection\\SFND_Lidar_Obstacle_Detection\\data\\pcd\\pcd\\out_plane.pcd", *cloud);pcl::PointCloud<pcl::PointXYZ>::Ptr obstCloud(new pcl::PointCloud<pcl::PointXYZ>);pcl::PCDReader reader2;reader2.read("F:\\SFND_Lidar_Obstacle_Detection\\SFND_Lidar_Obstacle_Detection\\data\\pcd\\pcd\\obstCloud.pcd", *obstCloud);pcl::search::KdTree<pcl::PointXYZ>::Ptr tree(new pcl::search::KdTree<pcl::PointXYZ>);//tree->setInputCloud(cloud);tree->setInputCloud(obstCloud);std::vector<pcl::PointCloud<pcl::PointXYZ>> clusters;//保存分割后的所有類 每一類為一個點云( //創建點云索引向量，用于存儲實際的點云信息)// 歐式聚類對檢測到的障礙物進行分組float clusterTolerance = 0.5;int minsize = 10;int maxsize = 140;std::vector<pcl::PointIndices> clusterIndices;// 創建索引類型對象pcl::EuclideanClusterExtraction<pcl::PointXYZ> ec; // 歐式聚類對象ec.setClusterTolerance(clusterTolerance);//設置近鄰搜索半徑ec.setMinClusterSize(minsize);//設置一個類需要的最小的點數ec.setMaxClusterSize(maxsize);//設置一個類需要的最大的點數ec.setSearchMethod(tree);//設置搜索方法//ec.setInputCloud(cloud); // feed point cloudec.setInputCloud(obstCloud);//輸入的點云不同，聚類的結果不同ec.extract(clusterIndices); // 得到所有類別的索引 clusterIndices  11類// 將得到的所有類的索引分別在點云中找到，即每一個索引形成了一個類for (pcl::PointIndices getIndices : clusterIndices){pcl::PointCloud<pcl::PointXYZ> cloudCluster;//PtCdtr<PointT> cloudCluster(new pcl::PointCloud<PointT>);// For each point indice in each clusterfor (int index : getIndices.indices){cloudCluster.push_back(cloud->points[index]);//cloudCluster.push_back(obstCloud->points[index]);}cloudCluster.width = cloudCluster.size();cloudCluster.height = 1;cloudCluster.is_dense = true;clusters.push_back(cloudCluster);}/*為了從點云索引向量中分割出每個聚類，必須迭代訪問點云索引，每次創建一個新的點云數據集，并且將所有當前聚類的點寫入到點云數據集中。*///迭代訪問點云索引clusterIndices，直到分割出所有聚類int j = 0;for (std::vector<pcl::PointIndices>::const_iterator it = clusterIndices.begin(); it != clusterIndices.end(); ++it){pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_cluster(new pcl::PointCloud<pcl::PointXYZ>);//創建新的點云數據集cloud_cluster，將所有當前聚類寫入到點云數據集中for (std::vector<int>::const_iterator pit = it->indices.begin(); pit != it->indices.end(); ++pit)//cloud_cluster->points.push_back(cloud->points[*pit]); //查找的是定義的cloud里邊對應的點云cloud_cluster->points.push_back(obstCloud->points[*pit]); //查找的是定義的obstCloud里邊對應的點云cloud_cluster->width = cloud_cluster->points.size();cloud_cluster->height = 1;cloud_cluster->is_dense = true;std::cout << "PointCloud representing the Cluster: " << cloud_cluster->points.size() << " data points." << std::endl;std::stringstream ss;ss << "F:\\SFND_Lidar_Obstacle_Detection\\SFND_Lidar_Obstacle_Detection\\data\\pcd\\pcd\\cluster\\" << j << ".pcd";pcl::PCDWriter writer;//保存提取的點云文件writer.write<pcl::PointXYZ>(ss.str(), *cloud_cluster, false); //*j++;}int clusterId = 0;pcl::visualization::PCLVisualizer::Ptr viewer(new pcl::visualization::PCLVisualizer("3D Viewer"));//viewer->addPointCloud<pcl::PointXYZ>(obstCloud, "obstCLoud" ); for (pcl::PointCloud<pcl::PointXYZ> cluster : clusters){//viewer->addPointCloud<pcl::PointXYZ>(cloud, "obstCLoud" + std::to_string(clusterId));//cloud可視化顯示的是平面的聚類viewer->addPointCloud<pcl::PointXYZ>(obstCloud, "obstCLoud" + std::to_string(clusterId));//obstCloud可視化顯示的是車的聚類viewer->setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 1, "obstCLoud" + std::to_string(clusterId));viewer->setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_COLOR, 0, 0, 1, "obstCLoud" + std::to_string(clusterId));++clusterId;}viewer->resetCamera();		//相機點重置viewer->spin();cout << clusters.size() << endl;system("pause");return 0;
}

給聚類結果畫框：

結果展示：

#include <iostream>
#include <pcl/io/io.h>
#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
#include <pcl/visualization/cloud_viewer.h>
#include <pcl/segmentation/sac_segmentation.h>
#include <pcl/segmentation/extract_clusters.h>
#include <pcl/kdtree/kdtree.h>
#include <pcl/common/common.h>
#include <unordered_set>
using namespace std;
using namespace pcl;
struct Box
{float x_min;float y_min;float z_min;float x_max;float y_max;float z_max;
};
int main()
{pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);pcl::PCDReader reader;reader.read("D:\\SFND_Lidar_Obstacle_Detection\\SFND_Lidar_Obstacle_Detection代碼分解\\out_plane.pcd", *cloud);pcl::PointCloud<pcl::PointXYZ>::Ptr all_cloud(new pcl::PointCloud<pcl::PointXYZ>);pcl::PCDReader reader2;reader2.read("D:\\SFND_Lidar_Obstacle_Detection\\SFND_Lidar_Obstacle_Detection代碼分解\\cloudRegion.pcd", *all_cloud);pcl::search::KdTree<pcl::PointXYZ>::Ptr tree(new pcl::search::KdTree<pcl::PointXYZ>);tree->setInputCloud(cloud);std::vector<pcl::PointCloud<pcl::PointXYZ>> clusters;//保存分割后的所有類 每一類為一個點云// 歐式聚類對檢測到的障礙物進行分組float clusterTolerance = 0.5;int minsize = 10;int maxsize = 140;std::vector<pcl::PointIndices> clusterIndices;// 創建索引類型對象pcl::EuclideanClusterExtraction<pcl::PointXYZ> ec; // 歐式聚類對象ec.setClusterTolerance(clusterTolerance);//設置近鄰搜索半徑ec.setMinClusterSize(minsize);//設置一個類需要的最小的點數ec.setMaxClusterSize(maxsize);//設置一個類需要的最大的點數ec.setSearchMethod(tree);//設置搜索方法ec.setInputCloud(cloud); // feed point cloudec.extract(clusterIndices); // 得到所有類別的索引 clusterIndices  11類// 將得到的所有類的索引分別在點云中找到，即每一個索引形成了一個類for (pcl::PointIndices getIndices : clusterIndices){pcl::PointCloud<pcl::PointXYZ> cloudCluster;//PtCdtr<PointT> cloudCluster(new pcl::PointCloud<PointT>);// For each point indice in each clusterfor (int index : getIndices.indices) {cloudCluster.push_back(cloud->points[index]);}cloudCluster.width = cloudCluster.size();cloudCluster.height = 1;cloudCluster.is_dense = true;clusters.push_back(cloudCluster);}int clusterId = 0;pcl::visualization::PCLVisualizer::Ptr viewer(new pcl::visualization::PCLVisualizer("3D Viewer"));//viewer->addPointCloud<pcl::PointXYZ>(all_cloud, "obstCLoud" ); //整個點云for (pcl::PointCloud<pcl::PointXYZ> cluster : clusters){viewer->addPointCloud<pcl::PointXYZ>(cloud, "obstCLoud" + std::to_string(clusterId));viewer->setPointCloudRenderingProperties( pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 1, "obstCLoud" + std::to_string(clusterId) );viewer->setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_COLOR, 0, 0, 1, "obstCLoud" + std::to_string(clusterId));pcl::PointXYZ minPoint, maxPoint;pcl::getMinMax3D(cluster, minPoint, maxPoint);//想得到它x,y,z三個軸上的最大值和最小值Box box;box.x_min = minPoint.x;box.y_min = minPoint.y;box.z_min = minPoint.z;box.x_max = maxPoint.x;box.y_max = maxPoint.y;box.z_max = maxPoint.z;std::string cube = "box" + std::to_string(clusterId);viewer->addCube(box.x_min, box.x_max, box.y_min, box.y_max, box.z_min, box.z_max,  1, 0, 0, cube);viewer->setShapeRenderingProperties(pcl::visualization::PCL_VISUALIZER_REPRESENTATION, pcl::visualization::PCL_VISUALIZER_REPRESENTATION_WIREFRAME, cube); //只顯示線框++clusterId;}viewer->resetCamera();		//相機點重置viewer->spin();cout << clusters.size() << endl;system("pause");return 0;}

?

總結

以上是生活随笔為你收集整理的读自动驾驶激光雷达物体检测技术（Lidar Obstacle Detection）（4）：Clustering（欧式聚类）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。