当前位置：首页 > news >正文

3D点云数据处理中的聚类算法总结

news 来源：原创 2025/8/9 19:20:13

1.欧式聚类：

基于点的空间距离（欧几里得距离）来分割点云，将距离较近的点归为同一簇。
欧式聚类需要的参数：邻域半径R,簇的最小点阈值minPts，最大点数阈值maxPts。
实现效率：
O(n * log n)
实现步骤：
（1）从未访问点开始探索：对于点云中的每一个未访问的点，进行以下步骤：
（2）区域查询：使用空间索引（如KD树）查找在以当前点为中心、半径为R的邻域内的所有点。如果邻域内的点数量大于或等于最小点阈值minPts，则将该点标记为一个新的聚类中心。
（3）扩展聚类：从这个聚类中心出发，继续探索邻域内的点，如果发现这些邻域内的点也是聚类的一部分，继续进行区域查询，将这些点也加入到聚类中，并对新发现的点进行同样的操作。如果邻域内的点不够，意味着这个聚类已经识别完毕。如果聚类簇的点数大于最大点阈值maxPts，进行丢弃。
（4）标记与输出：将识别到的聚类标记为不同的ID，直到点云中的所有点都被访问。输出结果为每个点对应的聚类标签。

2.条件欧式聚类：

条件欧式聚类在传统欧式聚类（仅依赖距离阈值）的基础上，增加了条件函数，用于判断两个邻近点是否属于同一簇。条件函数可以由用户自定义，结合点的空间距离和其他属性（如法向量角度、颜色差异等），从而实现更灵活和精确的分割。
实现效率：
O(n * log n)
实现步骤：
略（在欧式聚类的基础上增加额外条件限制）

3.区域生长聚类：

区域生长聚类是一种基于种子点的点云聚类方法，尤其是在需要利用点云几何信息（如表面连续性）的场景中。
区域生长聚类需要的参数：k个近邻或邻域半径r，角度阈值θth，曲率阈值Cth。
实现效率：
O(n * log n)
实现步骤：
（1）初始化，从点云中选择一个种子点，PCL默认按照曲率大小排序，选择曲率最小的作为第一个种子点（曲率小的点通常位于平滑区域）；并创建空的簇集合以及种子队列。
（2）生长过程，
·邻域搜索，找到当前种子点的k近邻，或指定半径内的邻近点。
·条件检查，计算当前种子点法向量Ns与邻近点Ni的夹角，若arccos(Ns·Ni)<θth（角度阈值）且邻近点的曲率<Cth，则认为邻近点与种子点属于同一个簇。
·簇扩展，将满足角度条件的邻近点加入当前簇，并将其添加到种子队列。
·种子更新，从队列中移除当前种子点，处理下一个种子点，直到队列为空。
（3）新簇生成，当前簇生长完成后，从剩余未分配的点中选择新的种子点（仍选择曲率小的点），重复生长过程。
（4）终止条件，当所有点都被分配到簇或标记为不可生长（孤立点）时，算法结束。输出多个簇的集合。

4.Min-Cut聚类：

Min-Cut聚类是一种基于图割（Graph Cut）的点云分割方法，主要用于二值分割，即将点云分为前景和背景两个部分。这种方法适用于从点云中提取特定目标（如物体）的情况。
将点云分割为两类：
·前景点: 属于目标物体的点。
·背景点: 不属于目标物体的点。
实现效率：
O(n²) 或更高
实现步骤：
（1）构建图结构，将点云中每个点视为图的一个顶点。额外添加两个虚拟顶点：源点和汇点。源点代表前景点，汇点代表背景。
边的连接方式：每个顶点与源点和汇点相连（分别表示前景和背景的归属可能性）；每个顶点与它的k近邻点相连。
（2）分配权重，图中的每条边都被赋予权重，表示割段这条边的代价，权重分为三类：
前景权重：点与源点之间的边权重，由用户指定一个常数，反映点属于前景的先验倾向。
背景权重：点与汇点之间的边权重，根据点到目标中心的距离计算，公式为：
在这里插入图片描述

其中d为点到目标中心的水平距离，σ是用户设置的高斯核函数，控制距离衰减速度。当点超过用户定义的半径时，权重趋近于0，表示更可能是背景。
平滑权重：点与近邻点之间的边权重，基于两点的欧式距离dij：
在这里插入图片描述

距离越远，权重越小，割断的可能性越大。
（3）最小割计算，使用最大流-最小割算法计算图的最小割，最小割是将图分为两个子集（源点侧和汇点侧）的边集合，其总权重之和最小。源点侧的点被标记为前景，汇点侧的点被标记为背景。
（4）输出结果，索引为0的为背景点，索引为1的为前景点。

上述四种算法在点云的PCL处理库（c++或python）中有比较成熟的实现，可直接调用。下面的几种算法在Python中也有成熟的实现。

5.DBSCAN：

DBSCAN 是一种经典的密度聚类算法，它的核心思想是通过点的密度连通性来识别簇，能够发现任意形状的簇并有效处理噪声。
DBSCAN 需要两个参数：邻域半径ε和形成密集区域所需的最小点数minPts。
点类型定义：
核心点：某个点的ε邻域内包含至少minPts个点（包括自身）。
边界点：非核心点，但落在某个核心点的邻域内。
噪声点：既不是核心点，也不是边界点的点。
密度传播关系定义：
直接密度可达：若点q在核心点p的ε邻域内，则q从p直接密度可达。
密度可达：若存在点序列 p1,p2,...,pn，其中p1=p，pn=q，且pi+1从pi直接密度可达，则q从p密度可达。
密度连通：若存在核心点o，使得点p和q都从o密度可达，则p和q密度连通。密度连通的点形成一个簇。
实现效率：
时间复杂度O(nlogn)。

DBSCAN 的实现是一个迭代过程，通过标记点并扩展簇来完成聚类。
实现步骤：
（1）输入数据集，包含n个点，设置邻域半径ε和定义最小点数minPts；
（2）初始化，将所以点标记为“未访问”，创建空的簇集合和噪声集合；
（3）主循环，随机选择一个“未访问”点p，将p标记为“已访问”，计算点p的ε邻域内的点数Nε§，包括p点自身。
若 |Nε(p)| < minPts：
将p标记为“噪声”，暂不分配簇；
继续下一轮循环。
若 |Nε(p)| ≥ minPts：
p是核心点，创建新簇C；
将p加入C。
（4）簇扩展，
种子集合：将Nε§中的所有未访问点加入种子集合S。
迭代扩展：
从S中取出一个点q。
若q未访问：
标记q为“已访问”；
查询q的邻域Nε(q)；
若 |Nε(q)| ≥ minPts（q是核心点）：
将Nε(q)中的未访问点加入S。
将q加入当前簇C。
重复直到S为空。
（5）重复，返回步骤（3），选择下一个未访问点，直到所有点都被访问。
（6）输出，簇集合：每个簇包含密度连通的核心点和边界点；噪声集合：未分配到任何簇的点。
在这里插入图片描述

如图所示，设置minPts = 4。点 A 和其他红点是核心点，因为在ε邻域内，这些点周围的区域至少包含 4 个点 (包括点本身)。因为它们彼此之间都可以访问，形成了一个单独的集群。点 B 和点 C 不是核心点，但是可以从 A (通过其他核心点) 到达，因此也属于集群。点 N 是一个噪声点，它既不是核心点，也不是直接可达的。

6.层次聚类：

层次聚类分为两种：
凝聚聚类：从每个数据点开始，每个点是一个簇，逐步合并最近的簇，直到所有点在一个簇中。
分裂聚类：从所有点在一个簇开始，逐步分割，直到每个点为单独簇。分裂聚类较少用，但适合特定场景。
链接准则：
合并时使用链接准则决定簇间距离，使用不同准则可能导致不同的聚类结果：
单链接：两个簇间的最小点间距离。
完全链接：两个簇间的最大点间距离。
平均链接：两个簇所有点对距离的平均值。
中心链接：两个簇中心间的距离。
实现效率：
层次聚类的计算复杂度通常为 O(n3)，适合中小型数据集（数百到千个点）。对于大型数据集效率较低，可能需优化。
实现步骤（以凝聚聚类为例）：
（1）初始化：每个数据点视为一个单独的簇。若有n个点，初始有n个簇。
（2）距离计算：计算每对簇间的距离，常用欧式距离。距离定义依赖链接准则。
（3）合并簇：找到距离最近的两簇，合并为一个新簇，簇数减 1。
（4）更新距离：合并后，更新距离矩阵，计算新簇与其他簇的距离。
（5）迭代：重复上述步骤，直到所有点在一个簇中，或达到预定簇数。
实现示例：
假设数据集 S={A(0,0),B(1,1),C(5,5),D(6,6)}，使用单链接，欧式距离：
初始簇：{A},{B},{C},{D}
距离矩阵：
在这里插入图片描述
第一次合并：
最近对：A-B 距离1.4，合并为{A,B}；
更新矩阵：

第二次合并：
最近对：C-D距离1.4，合并为{C,D}:
更新矩阵：

第三次合并：
合并{A,B}和{C,D}簇为{A,B,C,D}，结束。

7.k-means聚类：

K-Means 聚类的目标是将n个数据点划分为k个簇，使得每个点属于距离其最近的簇中心，并最小化簇内点的总方差。其核心思想基于以下假设：
①数据点围绕若干中心（质心）分布，簇是球形或紧凑的。
②通过迭代优化簇中心的位置，逐步收敛到局部最优解。
K-Means 是一种硬聚类方法，每个点严格属于一个簇，不支持模糊分配。
实现效率：
O(nkdt)，n个点，k个中心，d维，t次迭代。
实现步骤：
（1）输入：
数据集D={x1,x2,...,xn}包含n个点，每个点是d维向量。簇数k，需要预先指定。距离度量，通常使用欧式距离。
（2）初始化：随机选择k个点作为初始簇中心{μ1，μ2,...,μk}。
（K-Means++中对初始簇中心的选择方法进行了改进，先随机选择一个中心，后续中心选择概率与已有中心的最小距离平方成正比，重复直到选出k个中心。）
（3）分配阶段：
对每个数据点xi：计算其与所有簇中心μi的距离。将xi分配到距离最近的簇中心所属的簇Cj。
（4）更新阶段：
对每个簇Cj：计算簇内所有点的均值，更新簇中心μj：
在这里插入图片描述

其中∣Cj∣是簇Cj的点数。
（5）迭代：
重复上述步骤（3）、（4），直到满足终止条件：
①簇中心不再变化（收敛）；②达到最大迭代次数；③目标函数变化小于阈值。
（6）输出：
k个簇{C1，C2，...，Ck}，及其中心{μ1，μ2，...，μk}。

8.体素聚类：

通过将点云划分到三维体素网格（Voxel Grid）中，利用体素之间的连通性或特征进行聚类。
体素聚类需要的参数：体素大小vs。
实现效率：
体素化O(n)；聚类O(mlogm)，（其中m为体素个数，通常远小于n）
实现步骤：
（1）体素化，计算点云的边界，根据设置的体素大小，将空间划分为Nx *Ny *Nz的网格。
在这里插入图片描述
如对于点p=(x,y,z)，体素索引为：

将点分配到对应体素。

（2）计算体素特征（可选，若仅连通性聚类，则不需要计算）：
统计点数：遍历每个非空体素V(i,j,k)，记录其包含的点数Nijk；
计算质心：对体素V(i,j,k)中的点{p1,p2,...,pn},计算中心坐标，用于体素的代表点，用于后续聚类；
标记空体素：若Nijk=0，标记V(i,j,k)为空，也可设置最小点数阈值，过滤噪声体素。
（3）连通性聚类：
①定义邻接规则：
6-邻域：仅考虑上下左右前后6个方向的邻居；
26-邻域：考虑3*3*3立方体内的所有26个邻居。
②初始化：
创建一个空的簇集合{C1,C2,...}和访问标记数组（标记体素是否已经处理过），选择未访问的非空体素V(i,j,k)作为种子。
③连通性遍历：
将种子体素加入C以及队列，弹出队列头部元素，检测其邻居，若邻居非空且未访问，加入C和队列，重复直到队列为空。
重复：
从剩余未访问的非空体素中选择新种子，重复步骤③，直到所有体素被处理。
（4）点簇提取：
将体素簇映射为原点云，生成最终的点云簇。

9.OPTICS：

OPTICS（Ordering Points To Identify the Clustering Structure）是一种基于密度的聚类算法，克服DBSCAN对单一密度阈值ε依赖的局限性。OPTICS 通过对点云数据进行有序排序，生成一个层次化的聚类结构，支持提取任意密度的聚类结果。
需要的参数：邻域半径ε，最小点数minPts，陡度阈值ξ用于簇提取（0~1之间）。
概念定义：
核心距离：对于点x和参数minPts，核心距离dcore(x)是x到其第minPts个最近邻的距离。若x的邻居数|Nε(x)|<minPts，则dcore(x)=∞。核心距离表示点x是否为核心点，核心点能生成簇。
可达距离：对于点x和其邻近点o，可达距离为：

其中d(x,o)是点x和点o的欧式距离。可达距离表示从核心点x到点o的密度连接成本。
处理顺序：OPTICS按照可达距离从小到大的顺序处理点，优先扩展密度较高的区域。
输出结构：生成一个点序列，每个点带有其核心距离和可达距离，可视化为“可达性图”。
实现效率：
O(nlogn)
实现步骤：
（1）初始化，输入点云P={p1,p2,...,pn}，设置邻域半径阈值ε、最小邻居数minPts。创建两个集合，分别存储已处理点（初始为空）和未处理点（初始为所有点）。创建一个优先队列用于排序可达距离。创建输出序列Order和对应的dcore，dreach列表，初始为空。
（2）选择种子点，从未处理的点中随机选择一个点x作为初始起点（或按特点策略选择），将x标记为已处理，加入输出序列Order。
（3）计算核心距离，找到x的ε-邻域内的点集Nε(x)，若Nε(x)的个数≥minPts，则按距离排序，取第minPts个点的距离作为dcore(x)；若Nε(x)的个数＜minPts，则dcore(x)=∞（非核心点）。
（4）扩展簇，若dcore(x)≠∞，则x是核心点，对于Nε(x)中的每个未处理点o，计算dreach(o,x)=max{dcore(x),d(x,o)}，将(o,dreach(o,x))加入优先队列（若o不在队列中，进行添加；若o已在队列中，且可达距离比之前存储的值更小，则进行更新；若可达距离不比之前更小，则不更新）。从优先队列中取出可达距离最小的点o’，将其标记为已处理，并加入Order，记录dreach(o’)、dcore(o’)，若o’是核心点，重复扩展过程。
（5）重复，若优先队列为空，从未处理点中选择新种子点，重复步骤（2）-步骤（4），直到所有点被处理。
（6）输出，返回点序列Order和每个点的dreach，dcore。
（7）簇提取，
需要用到的数据：
点序列Order = [p1,p2,...,pn]；
可达距离L_dreach=[r1,r2,...,rn];
参数ξ，ξ越大，提取的簇越粗，ξ越小，提取更多细小的簇。
提取步骤：
①初始化，创建簇集合与噪声集合，初始都为空。创建临时簇Ctemp，用于收集潜在簇点。
②检测簇开始，逐点分析可达距离，检查前一点和当前点，若dreach(i)值大（为∞或大于dreach(i+1)），且dreach(i+1)<(1-ξ)·dreach(i)，表示pi为簇的起点，则清空Ctemp，添加pi点。
③扩展簇，继续遍历后续点pj(j>i)，若dreach(j)满足dreach(j)≤(1+ξ)·dreach(j-1)，则添加pj到Ctemp。
④簇结束，若dreach(k)＞(1+ξ)·dreach(k-1)，表示pk-1是簇的终点。检查Ctemp，若Ctemp的个数≥minPts，则保存到簇集合，否则保存为噪声集合。
⑤处理剩余点，若dreach(i)=∞或未形成有效簇，则为噪声，重复直到序列结束。

10.HDBSCAN：

HDBSCAN结合层次聚类和密度估计，是对DBSCAN的改进版本，且不需要指定邻域半径ε。能够自动识别不同密度和形状的簇，并显式区分噪声点。
实现步骤：
（1）计算核心距离，对输入点云P={p1,p2,...,pn}，计算点pi的k个最近邻，dcore(pi)=第k个邻居距离。输出核心距离集合[dcore(p1),dcore(p2),...,dcore(pn)]。
（2）构建互达距离图，对每对点(pi,pj)，计算互达距离：
dmreach(pi,pj)=max{dcore(pi),dcore(pj),d(pi,pj)}
（同OPTICS算法的可达距离有区别，需注意）
根据互达距离，形成加权图。
（3）构建最小生成树MST，使用kruskal算法从互达距离图中提取最小联通结构，按dmreach从小到大加边，避免环，MST示意图如下图所示：
在这里插入图片描述
加粗部分为最小生成树（顶点为点云坐标，数字为权值-即互达距离）
（4）层次聚类，从单一簇MST开始，通过逐步移除（剪枝）较长的边（即互达距离较大的边），将数据分裂成多个子图。随着边被移除，子图的数量逐渐增加，形成一个层次结构，这个过程会持续进行，直到所有的边都被移除。
（5）簇提取，
变量含义：λbirth指一个簇诞生时的密度阈值，λdeath指一个簇结束时的密度阈值，其中λ的计算方式：
λ = 1/dmreach(pi,pj)
每次剪枝时，记录新形成的子图（簇）的λbirth，当这个子图进一步分裂或消失时，记录它的λdeath。
稳定性计算：

簇提取的目标，从所有可能的簇中，选择一组互不重叠的簇，使得稳定性最大化，通过EOM（Excess of Mass）策略实现。