三维点云处理（十四）：谱聚类 (Spectral Clustering)
在点云聚类任务中，K-Means 和 GMM 等传统方法均建立在欧氏距离的几何假设之上，只能有效分割“凸集（球形或椭球形簇）”。当面对双环（Concentric Rings）、双月形（Two Moons）或交错的复杂三维流形曲面时，欧氏距离方法会彻底失效。
谱聚类（Spectral Clustering） 引入图论（Graph Theory）与代数谱分析，将点云转化为图切分问题。本章将避开繁琐复杂的线性代数推导，通过几何直觉、流程图与图片例示深入浅出地解释谱聚类的核心原理。
一、 核心直觉：为何需要谱聚类？
1.1 欧氏距离的局限 vs 图连通性 (Connectivity)
- 欧氏距离缺陷：如在同心双环数据中，内环上的点与外环上的点在欧氏空间中的直线距离可能比内环直径还要短，导致 K-Means 沿直线直接“斩断”双环；
- 图连通性思想：谱聚类不关心点与点之间的绝对直线距离，而是关注点与点在流形表面是否连通。只要沿着拓扑结构逐步传递，内环点与内环点高度连通，而与外环点无直接连通。
1.2 工程实战：谱聚类在三维非凸点云中的“降维打击”
在实际的三维工程项目中，物体往往不是完美的球形（凸集），而是存在严重的**非凸（Non-convex）**特征：
- 盘绕的线缆或弹簧：几何上互相交错穿插，空间直线距离极近，但物理连通路径极长。
- 相互咬合的机械齿轮：不同齿轮的轮齿在欧氏空间中紧密咬合重叠。
- 包含孔洞的墙面与门框。
如果使用 K-Means（基于欧氏距离），它会粗暴地划定一个空间球形边界，导致弹簧被从中切断，或者咬合的两个齿轮被左右劈开。 而谱聚类基于拉普拉斯矩阵的特征分解，能够完美提取出这些非凸流形的内蕴连通性（Intrinsic Connectivity）。它顺藤摸瓜地沿着表面连通图进行聚类，从而干净利落地剥离出相互缠绕的复杂物体。
二、 图的构建与矩阵表达 (Graph Construction)
谱聚类的第一步是将点云 抽象为一个加权无向图 ：
- 顶点 ：点云中的每个点 代表一个节点；
- 边 与权重矩阵 ：节点 与 之间的边权重 表示它们的相似程度（如高斯相似度核 ）。
2.1 三种建图方式
- -邻域图 (-Neighborhood Graph)：若距离 ，则建立连边，权重设为 1；
- -近邻图 (KNN Graph)：若 在 的 KNN 邻域内则建边，保证了不同点云密度区域的自适应性；
- 全连接图 (Fully Connected Graph)：任意两点间均连边，权重随距离指数衰减。
2.2 图拉普拉斯矩阵 (Graph Laplacian)
定义度矩阵 为对角阵，主对角元素为节点 相连的所有边权重之和 。
核心矩阵图拉普拉斯矩阵 定义为：
- 归一化拉普拉斯矩阵（随机游走型）：
三、 图切分视角与谱空间映射 (Spectral Projection)
3.1 从 Min-Cut 到 RatioCut / NormalizedCut
图切分的目标是寻找一种切法，使得被切断的边权重和最小（）。
- 朴素 Min-Cut 缺陷：倾向于切下一个孤立噪点（因为切断 1 个孤立点只需切断极少的边）。
- 修正切图方案：
- RatioCut：约束分割出的簇包含类似数量的节点数 ：
- NormalizedCut (Ncut)：约束分割出的簇包含类似的总边权和（密度）：
3.2 降维与谱空间映射的“魔法”直觉
直接求解离散的 RatioCut / Ncut 是 NP-Hard 困难问题。谱聚类通过连续松弛，将其转化为求解拉普拉斯矩阵 的前 个最小特征值及对应的特征向量 。
谱映射几何直觉： 特征向量就像是一台“拓扑解开器”。它把原始高维、弯曲缠绕的非凸流形点云，非线性投影变换到一个全新的低维**“谱空间 (Spectral Domain)”中。 在这个新谱空间中，原本复杂纠缠的非凸双环结构被“拉直”，聚拢重组为互相离散、线性可分的球形点集**！
四、 特征值间隙 (Eigengap) 与自动簇数确定
谱聚类的一个突出优势是可以根据矩阵代数特征自动推导估计最佳簇数 ：
- 将拉普拉斯矩阵的特征值从小到大排序：；
- 计算相邻特征值之间的间隙（Eigengap）：
- 判定准则：寻找使 达到最大跳跃突变的值 。特征值跳跃最剧烈的位置，代表了图连通分量之间最稳定的划分粒度。
五、 谱聚类完整算法步骤总结
六、 算法优缺点与选型对比
| 维度 | 特性总结 |
|---|---|
| 计算复杂度 | （特征值分解开销，可利用稀疏矩阵求解器降至 ） |
| 算法优点 | 1. 不假设簇的几何形状，完美支持非凸流形与复杂拓扑分割； 2. 建立在图论与谱分析之上，对噪声具有极佳鲁棒性； 3. 可结合特征值间隙（Eigengap）启发式估算簇数 。 |
| 算法缺点 | 1. 稠密矩阵下 计算与内存开销大，大规模点云需构建稀疏图； 2. 建图参数（如 KNN 的 或高斯核的 ）对结果较敏感。 |