点云欧式聚类快速了解

点云处理算法快速了解专栏------------点云欧式聚类

一、欧式聚类核心简介

1. 一种基于欧氏距离度量的聚类算法
2. 基于KD-Tree的近邻查询算法是加速欧式聚类算法的重要预处理方法

二、KDTree核心简介

1. KD-Tree是由二分搜索树演变而来的用于大规模高维度数据查找场景当中的索引结构，主要用于最近邻查找和近似最近邻查找。
2. 将整个空间划分为二叉树的形式，方便有效找到最近邻

三、KDTree的搭建

原因：对于激光雷达产生的三维数据，普通的二分树已经无法满足存储需求，此时须利用KDTree的数据结构。KDTree本质上依然是一种二分搜索树，每一次对点云数据空间的划分均建立在某一个维度的基础上，划分完成后的左右子空间数据量应尽可能保证数目相等。 搭建过程： 计算K维数据集合中每一维度的方差，并从中选取具有最大方差的维度k,用下式： 将维度k上的数据从小到大排列，得到数据集合，计算中值m 按照中值m分割为两个集合，并创建一个用于存储的树节点 对步骤4得到的两个子集合，重复步骤4，直到所有的子集合不能再进行划分为止；保存到叶子节点。 加快的原因: 在建立KDTree 数据结构后，一般情况下只须在其子节点和父节点中查找邻近点，即可大大减少搜索邻近点所带来的额外计算量

四、KDTree最近邻查询流程

 

五、欧式聚类流程

 

对于欧式聚类来说，距离判断准则为前文提到的欧式距离 。对于空间某点P ，通过近邻搜索算法找到 k个离P点最近的点，这些点中距离小于设定阈值的便聚类到集合Q中 如果

Q中元素的数目不再增加，整个聚类过程便结束;否则在集合Q中选取除P点以外的点，重复上述过程，直到Q中元素的数目不再增加为止

六、基于欧式距离和KDTree的欧式聚类算法代码

1. PCL对欧式聚类有着 很好的封装
2. 代码如下：

   //被分割出来的点云团（标号队列）
    
   std::vectorcluster_indices;
    
   //欧式分割器
    
   pcl::EuclideanClusterExtractionec;
    
   ec.setClusterTolerance(0.02); //2cm
    
   ec.setMinClusterSize(100);
    
   ec.setMaxClusterSize(25000);
    
   //搜索策略树
    
   ec.setSearchMethod(tree);
    
   ec.setInputCloud(cloud_filtered);
    
   ec.extract(cluster_indices);
   

---

总结

点云处理算法库PCL，是比较重要的，在后续会继续学习，然后发出更优质的文章。