欧式聚类详解（点云数据处理）
欧式聚类是一种基于欧氏距离度量的聚类算法。基于KD-Tree的近邻查询算法是加速欧式聚类算法的重要预处理方法。

KD-Tree最近邻搜索

Kd-树是K-dimension tree的缩写，是对数据点在k维空间中划分的一种数据结构；Kd-树是一种平衡二叉树。为了能有效的找到最近邻，Kd-树采用分而治之的思想，即将整个空间划分为几个小部分。k-d树算法的应用可以分为两方面，一方面是有关k-d树本身这种数据结构建立的算法，另一方面是在建立的k-d树上如何进行最邻近查找的算法。
k-d tree是每个节点均为k维数值点的二叉树，其上的每个节点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为d，其左子树上所有点在d维的坐标值均小于当前值，右子树上所有点在d维的坐标值均大于等于当前值，本定义对其任意子节点均成立。
构建开始前，对比数据点在各维度的分布情况，数据点在某一维度坐标值的方差越大分布越分散，方差越小分布越集中。从方差大的维度开始切分可以取得很好的切分效果及平衡性。

KD-Tree构建原理
常规的k-d tree的构建过程为：循环依序取数据点的各维度来作为切分维度，取数据点在该维度的中值作为切分超平面，将中值左侧的数据点挂在其左子树，将中值右侧的数据点挂在其右子树。递归处理其子树，直至所有数据点挂载完毕。

KD-Tree近邻查询
给定点p，查询数据集中与其距离最近点的过程即为最近邻搜索

图中对于给定的查询数据点m，须从KD-Tree的根结点开始进行比较，其中m(k)为当前结点划分维度k上数据点m对应的值，d为当前结点划分的阈值。若 m(k)小于d，则访问左子树；否则访问右子树，直至到达叶子结点Q。此时Q就是当m前最近邻点，而m与Q之间的距离就是当前最小距离Dmin 。随后沿着原搜索路径回退至根结点，若此过程中发现和m之间距离小于 Dmin的点，则须将未曾访问过的子节点均纳入搜索范畴，并及时更新最近邻点，直至所有的搜索路径都为空，整个基于KD-Tree结构的最近邻点查询过程便告完成。

欧式聚类

对于欧式聚类来说，距离判断准则为前文提到的欧氏距离。对于空间某点P，通过KD-Tree近邻搜索算法找到k个离p点最近的点，这些点中距离小于设定阈值的便聚类到集合Q中。如果Q中元素的数目不在增加，整个聚类过程便结束；否则须在集合Q中选取p点以外的点，重复上述过程，直到Q中元素的数目不在增加为止。

原文链接：https://blog.csdn.net/JAT0929/article/details/104258461

　　pcl::EuclideanClusterExtraction是基于欧式距离提取集群的方法，仅依据距离，将小于距离阈值的点云作为一个集群。
　　具体的实现方法大致是：
　　(1) 找到空间中某点p10，由kdTree找到离他最近的n个点，判断这n个点到p的距离；
　　(2) 将距离小于阈值r的点p12、p13、p14…放在类Q里；
　　(3) 在 Q\p10 里找到一点p12，重复1；
　　(4) 在 Q\p10、p12 找到一点，重复1，找到p22、p23、p24…全部放进Q里；
　　(5) 当 Q 再也不能有新点加入了，则完成搜索了。

后面有自定义代码：

https://blog.csdn.net/fei_12138/article/details/109718785

官方教程，结果和下面的代码不一样，下次再试一下：

https://www.pclcn.org/study/shownews.php?id=57
点云欧式聚类算法流程
（1）点云读入；
（2）体素化下采样（方便处理）；
（3）去离散点；
（4）RANSAC算法检测平面，并剔除平面点云；
（5）欧式聚类；
（6）结果的输出和可视化；

python代码：

https://zhuanlan.zhihu.com/p/75117664

from paper_1_v0.my_ransac import my_ransac_v5
import numpy as np



img_id = 1  #  这里读入你的kitti 雷达数据即可
path = r'D:\KITTI\Object\training\velodyne\%06d.bin' % img_id  ## Path ## need to be changed
points = np.fromfile(path, dtype=np.float32).reshape(-1, 4)

index_ground, index_obj, best_model, alpha = my_ransac_v5(points)   # 去除地面，用pcl 的代码也可以，不做也可以


print('points  shape', points[index_obj, :3].shape)


s = time.time()
cloud = pcl.PointCloud(points[index_obj, :3])

tree = cloud.make_kdtree()

ec = cloud.make_EuclideanClusterExtraction()
# ec.set_ClusterTolerance(0.02)
ec.set_ClusterTolerance(0.62)  # 三个参数设置
ec.set_MinClusterSize(100)
ec.set_MaxClusterSize(15000)
ec.set_SearchMethod(tree)
cluster_indices = ec.Extract()

print('time:', time.time() - s)

print('cluster_indices : ' + str( len(cluster_indices)) + "  .")

cluster_points = points[index_obj,:].copy()
cluster_points[:,3] = 1000  # 基础颜色

for j, indices in enumerate(cluster_indices):
    print('indices = ' + str(len(indices)))
    cluster_points[indices,3] = (j+10) * 4000   # 设置每个类的颜色

color_cloud = pcl.PointCloud_PointXYZRGB(cluster_points)
visual = pcl.pcl_visualization.CloudViewing()
visual.ShowColorCloud(color_cloud, b'cloud')

flag = True
while flag:
    flag != visual.WasStopped()

体素化下采样：

1.体素滤波
PCL实现的VoxelGrid类通过输入的点云数据创建一个三维体素栅格（可把体素栅格想象为微小的空间三维立方体的集合），然后在每个体素（即，三维立方体）内，用体素中所有点的重心来近似显示体素中其他点，这样该体素就内所有点就用一个重心点最终表示，对于所有体素处理后得到过滤后的点云。
c++代码：

#include <pcl/io/pcd_io.h>  //文件输入输出
#include <pcl/point_types.h>  //点类型相关定义
#include <pcl/visualization/cloud_viewer.h>  //点云可视化相关定义
#include <pcl/filters/voxel_grid.h>  //体素滤波相关
#include <pcl/common/common.h>  

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    //1.读取点云
    pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);
    if (pcl::io::loadPCDFile<pcl::PointXYZ>("data\\demo.pcd", *cloud) == -1)
    {
        PCL_ERROR("Cloudn't read file!");
        return -1;
    }
    cout << "there are " << cloud->points.size() << " points before filtering." << endl;

    //2.体素栅格滤波
    pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_filter(new pcl::PointCloud<pcl::PointXYZ>);
    pcl::VoxelGrid<pcl::PointXYZ> sor;
    sor.setInputCloud(cloud);
    sor.setLeafSize(0.3f, 0.3f, 0.3f);//体素大小设置为30*30*30cm
    sor.filter(*cloud_filter);

    //3.滤波结果保存
    pcl::io::savePCDFile<pcl::PointXYZ>("data\\demo_filter.pcd", *cloud_filter);
    cout << "there are " << cloud_filter->points.size() << " points after filtering." << endl;

    system("pause");
    return 0;
}

原文链接：https://blog.csdn.net/qq_22170875/article/details/84980996