4、点云聚类算法（上）：欧几里得聚类、DBSCAN聚类原理、KD-Tree加速、参数调优经验

点云聚类，说白了就是把一堆乱七八糟的点，按照空间分布“物以类聚”。你想想看，激光雷达扫出来的点云，少则几万，多则上百万个点。如果不做聚类，你根本不知道哪个点是车、哪个点是行人、哪个点是路边的垃圾桶。

我个人习惯把聚类看作是感知系统的“第一道筛子”。筛得好，后面的目标跟踪、轨迹预测都轻松；筛不好，后面全是坑。今天咱们就聊聊两种最常用的聚类方法：欧几里得聚类和DBSCAN，顺便把KD-Tree加速和参数调优的经验也一并交代了。

4.1 欧几里得聚类：最直观的“邻居抱团”

欧几里得聚类的思想特别简单：如果两个点之间的距离小于某个阈值，它们就属于同一个簇。然后不断往外扩散，直到把所有连通的点都找出来。

我在项目中遇到过一个问题：用欧几里得聚类处理高速公路场景，结果一辆大卡车被分成了七八块。为什么？因为卡车侧面太平了，点与点之间的距离稍微大一点，算法就认为它们“不连通”了。后来我把距离阈值调大了一点，才把卡车完整地聚出来。

核心步骤：

从点云中任选一个未处理的点作为种子
用KD-Tree搜索该点半径r内的所有邻居
将邻居加入当前簇，并标记为已处理
对簇内每个新点重复步骤2-3，直到没有新点加入
如果簇内点数大于最小点数阈值，保留该簇；否则视为噪声丢弃

说白了，这就是一个广度优先搜索（BFS）的过程。你想想看，每个点都在“拉帮结派”，距离近的就成一伙。

4.2 DBSCAN：密度说了算

DBSCAN和欧几里得聚类最大的区别在于：它不只看距离，还看密度。一个点周围如果足够“热闹”（邻居多），它就是核心点；如果只是偶尔有几个邻居，那就是边界点；如果孤零零的，那就是噪声点。

我记得有一次做园区低速场景的聚类，欧几里得聚类怎么调都搞不定稀疏的行人点云。换DBSCAN一试，效果立竿见影。为什么？因为行人点云稀疏但密度相对均匀，DBSCAN对这种场景天生友好。

DBSCAN的三个关键概念：

核心点：在半径Eps内至少有MinPts个点
边界点：在半径Eps内少于MinPts个点，但属于某个核心点的邻居
噪声点：既不是核心点也不是边界点

DBSCAN的好处是不用预先指定聚类数量，而且能自动识别噪声。但它的缺点也很明显——对参数敏感。Eps和MinPts稍微变一变，结果可能天差地别。

4.3 KD-Tree加速：别让搜索拖后腿

你想想看，如果不用KD-Tree，每次找邻居都要遍历所有点，复杂度是O(N²)。对于10万个点的点云，那就是100亿次距离计算——你的CPU会哭的。

KD-Tree的原理很简单：把三维空间用二叉树的形式分割。每次找邻居时，只需要搜索树的一部分分支，复杂度降到O(N log N)。

我曾经在一个项目里踩过坑：直接用暴力搜索做欧几里得聚类，点云只有2万个点，结果一帧处理了3秒钟。换成KD-Tree之后，同样的数据只用了50毫秒。嗯，这里要注意，KD-Tree的构建本身也有开销，但对于静态场景或者帧间变化不大的情况，可以复用上一帧的树结构。

// 伪代码：KD-Tree加速的欧几里得聚类
function euclideanCluster(points, radius, minPoints):
    kdTree = buildKDTree(points)  // 构建KD-Tree
    visited = [false] * len(points)
    clusters = []
    
    for i in range(len(points)):
        if visited[i]: continue
        queue = [i]
        cluster = []
        visited[i] = true
        
        while queue:
            idx = queue.pop(0)
            cluster.append(idx)
            // KD-Tree快速搜索半径内的邻居
            neighbors = kdTree.radiusSearch(points[idx], radius)
            for n in neighbors:
                if not visited[n]:
                    visited[n] = true
                    queue.append(n)
        
        if len(cluster) >= minPoints:
            clusters.append(cluster)
    
    return clusters

4.4 参数调优经验：纸上得来终觉浅

参数调优这件事，说实话没有银弹。但我可以分享一些实战中总结出来的经验。

参数	典型范围	调优建议
欧几里得距离阈值	0.3m - 1.5m	高速场景偏大(0.8-1.2m)，低速场景偏小(0.3-0.6m)
DBSCAN的Eps	0.2m - 1.0m	用k-distance图找拐点，我一般取排序后第MinPts个距离的均值
DBSCAN的MinPts	3 - 10	点云密度高取大值，密度低取小值。行人场景我常用4-5
最小聚类点数	3 - 20	用于过滤噪声，太小会保留孤立点，太大会漏掉小目标

避坑指南：

我曾经在雨雪天气吃过亏。雨滴和雪花在点云中形成大量稀疏的噪声点，如果不做预处理直接聚类，DBSCAN会把它们当成小目标。后来我加了一步“体素滤波+离群点移除”，才把这个问题解决掉。

另外，我个人习惯在调参时先做可视化。把聚类结果用不同颜色画出来，一眼就能看出参数合不合理。别光盯着数字看，视觉反馈往往更直观。

还有一个技巧：对于不同距离的物体，可以用不同的距离阈值。比如近处用0.5m，远处用1.0m。因为激光雷达的点云密度是随距离衰减的，远处点更稀疏，阈值自然要大一些。

我的调参流程：

先用默认参数跑一遍，看聚类效果
观察过分割（一个物体被分成多块）还是欠分割（多个物体被合成一块）
过分割就增大距离阈值或Eps，欠分割就减小
反复迭代3-5次，基本能找到一个不错的平衡点

好了，关于欧几里得聚类、DBSCAN和KD-Tree加速的核心内容就这些。下一节我们会聊到更高级的聚类方法，比如基于图割的聚类和基于深度学习的点云分割。但今天讲的这些基础方法，在实际工程中依然是最常用的——别小看它们。