37 点云基础
Part VIII 关心的是怎样把现实世界变成三维数据：激光三角（章节 33）、结构光、相移、聚焦堆栈——它们各有各的物理原理，但最终交付的产物是同一类东西，一堆带有 \((x,y,z)\) 坐标的三维点。章节 30 把这一整条采集链路串了起来。从本章开始的 Part IX，主题切换为如何处理这些已经到手的三维数据：去噪、配准、测量、拟合。而所有这些处理的对象，绝大多数时候就是点云（point cloud）。
点云是三维世界里的”像素”，但它比二维图像难对付得多。二维图像是规则网格，每个像素的邻居在哪、有几个，都由行列下标直接决定；点云却是一袋无序（unordered）的点，谁和谁相邻完全不写在数据结构里，得自己算。它稀疏（sparse），表面之外的空间没有任何记录。它带噪（noisy），每个点都沿测量方向抖动。它还有离群点（outlier），弧光、反光、多路径会凭空造出一批悬在空中的”飞点（flyer）“。本章用一幅合成场景把这四个性质都摆出来（图 37.1、图 37.2），并围绕它讲清楚三件最基础的事：三维数据有哪几种表示形态、怎样在无序点集上快速找最近邻、怎样把飞点清理掉。
整幅场景共 20200 个点：地面 11000 点、立方体顶面 2600 点、四个竖直侧面 3600 点、球冠 2800 点，外加 200 个离群飞点。所有表面点都沿各自法向叠加了 \(\sigma=0.10\) mm 的高斯测量噪声，高度范围 \(z\in[-0.43,\ 43.92]\) mm（表面本身只到 18 mm，更高的部分全是飞点）。这套数据由 code/point_cloud_basics/ 的工程用固定随机种子确定性地生成，本章后面所有数字都来自它的真实运行。
37.1 三维数据的形态
同样一个三维物体，可以用三种本质不同的数据结构来记录，工程上必须分清。
第一种是点云，即上面说的无序点集 \(\{\mathbf p_i=(x_i,y_i,z_i)\}\)，可选地每个点再带上颜色或法向。它是最通用的形态，能表示任意拓扑的表面，多视角拼接、自由曲面都不在话下；代价是无序、不规则，任何”找邻居”的操作都得借助额外的空间索引（下一节的主题）。
第二种是距离图（range image），也叫深度图或 2.5D 图。它是一张规则二维网格，每个网格单元 \((u,v)\) 存一个高度值 \(z\)——本质上是”把 \(z\) 当灰度的图像”。它的最大好处是规则：邻居关系由网格下标直接给出，二维图像的所有滤波、形态学算子（章节 6）可以原封不动搬过来用，存储也紧凑。
第三种是网格（mesh），用顶点加三角面片显式记录表面的连接关系，主要服务于渲染、有限元、碰撞检测，工业测量里用得相对少，本章不展开。
“2.5D”这个叫法点出了距离图的尴尬位置：它有完整的 \(x,y\) 平面和一个 \(z\)，看似三维，却规定了每个 \((x,y)\) 只能有一个 \(z\)。真正的 3D 表面在竖直壁、倒扣面、空腔处会让同一条视线穿过多个 \(z\)，这正是距离图表达不了的——它只能记录”从某个固定视角看过去最近（或最高）的那一层”。
点云和距离图之间可以互相转换，但这个转换不是无损的。从距离图到点云很简单，每个有效网格单元按其下标和高度还原一个三维点即可。反过来，从点云生成距离图，要先选定一个投影方向（这里取俯视，沿 \(-z\) 看），把 \(XY\) 平面分箱成规则网格，每个箱子里只保留一个代表性的 \(z\)。问题就出在这”只保留一个”上。
我把这 20200 个点按 \(200\times200\) 的俯视网格分箱，每个箱子取落入点的最高 \(z\)，结果如 图 37.3：网格化痕迹清晰可见，地面被量化成了马赛克，球冠还在，立方体顶面也在——但立方体的竖直侧壁完全消失了，立方体正下方和球冠正下方被遮挡的那部分地面也没了。统计上，原始 20200 个点，回投后只剩 12585 个箱子存活，丢失了 7615 个点（37.7%）。这些丢失的点不是噪声，是真实表面的真实采样，它们之所以消失，纯粹是因为和别的点共享了同一个 \((x,y)\) 而 \(z\) 不是最高——侧壁点被顶面点盖掉，被遮挡的地面点被上方的物体盖掉。
这个 37.7% 不是随便挑的数字，它是一堂关于”单视角本质”的课。章节 33 里激光三角法直接产出的就是距离图，那时它天然只看得见从激光视角能照到的表面，背面、侧壁、空腔本来就在阴影里——距离图的 2.5D 局限和采集方式的单视角局限，是同一件事的两种说法。要拿到完整的 3D，要么多视角扫描再配准（章节 39），要么干脆全程用点云、不要塌缩成距离图。所以一条实用的工程准则是：能用点云就别过早转距离图；只有当你确信单视角足够、且想借用二维图像的成熟算子时，距离图的规则性才值得用那 37.7% 的信息去换。
在 SciVision 里，这两种形态分别对应 SciPointCloud（点 + 可选颜色 + 可选法向，支持 PLY/PCD/OBJ 读写）和 SciRangeImage（ushort 高度数据加上 resolutionX/Y/Z 与 offsetZ，存成 16 位 PNG）。本章场景装进 SciPointCloud 后 Length=20200，存出的 cloud_raw.ply 带逐点高度颜色，可直接用任意点云查看器打开。
37.2 空间索引：KdTree
点云无序，带来的第一个、也是最根本的工程问题是：给定一个查询点，怎么找到它最近的若干个邻居？这个”最近邻（nearest neighbor）查询”是几乎所有三维算法的地基——配准要靠它建立点对（章节 39），滤波要靠它定义邻域，法向估计、特征描述、表面重建无一例外。最朴素的办法是暴力扫描：对每个查询点，算它到全部 \(N\) 个点的距离再排序，单次查询 \(O(N)\)，做 \(M\) 次就是 \(O(MN)\)。\(N\) 上万、\(M\) 上万时，这是百亿次距离计算，慢得无法接受。
kd 树（kd-tree）把这件事降到对数复杂度。它的思想是递归地用与坐标轴垂直的超平面把空间二分：在根节点按 \(x\) 坐标取中位数，小的归左子树、大的归右子树；下一层换 \(y\) 轴，再下一层换 \(z\) 轴，如此轴轮换地切下去，直到每个叶子只剩很少的点。建好后，单次最近邻查询先下降到查询点所在的叶子（这一路只需 \(O(\log N)\) 次比较），拿到一批候选邻居，再回溯向上：在每个分裂节点处检查”查询点到分裂超平面的距离”是否比当前已知的第 \(k\) 近还小——如果不小，超平面那一侧的整棵子树都不可能含有更近的点，整片剪掉，不必进去。正是这个剪枝让平均查询复杂度降到 \(O(\log N)\)。\(k\) 近邻查询用一个大小为 \(k\) 的最大堆维护当前最近的 \(k\) 个；半径搜索（radius search）则收集所有落在给定半径内的点，回溯时的剪枝判据从”第 \(k\) 近距离”换成”半径”。
kd 树的对数复杂度有个前提：维度不能太高。当维度升到几十、上百时，“到超平面的距离几乎总是小于到最近点的距离”，剪枝几乎全部失效，kd 树退化回近似暴力——这就是维度灾难（curse of dimensionality）。所幸三维点云只有 3 维，kd 树在这里如鱼得水。高维特征匹配则改用近似最近邻或局部敏感哈希。
本章工程实现了一棵隐式数组型的 kd 树（用 std::nth_element 做中位分裂，轴 \(x/y/z\) 轮换），并和暴力法做了对照计时。对这 20200 个点做 10000 次 8 近邻查询，kd 树耗时约 60 ms，暴力法约 870 ms，加速约 14.5 倍；而且两者结果逐位一致——kd 树不是近似、不丢精度，它返回的就是精确的最近邻，只是聪明地避开了不可能的区域。这 14.5 倍在单次查询上看不出什么，但放进一个要反复查最近邻的迭代算法里（比如 ICP 每轮都要为几万个点找对应点），就是几分钟和几十毫秒的差别——\(\log N\) 相对 \(N\) 的工程价值，正是在这种”被调用千万次”的内循环里兑现的。
37.3 噪声与离群点
三维数据里的”脏”，要分成本质不同的两类，混为一谈就会用错工具。
第一类是测量噪声：每个真实表面点都沿测量方向（通常是表面法向）有一个小幅的随机抖动，本章合成数据里是 \(\sigma=0.10\) mm 的高斯噪声。它的特征是幅度小、零均值、贴着表面，邻域内的点你挤着我我挤着你，密度均匀。这类噪声靠平滑滤波处理（Part IX 后续章节），不该靠”删点”来对付。
第二类是离群点，也就是飞点：弧光、镜面反射、多路径、传感器伪影会凭空造出一批根本不在任何真实表面上的点，它们悬在空中，远离所有正常结构。本章的 200 个飞点就是这样撒在 \(z\in[6,44]\) mm 的空域里。它的特征恰好相反，远离表面、邻域空旷——一个飞点周围几乎没有别的点，它和最近邻之间隔着很大的空隙。
这个”邻域空旷”的特征，正好可以用来把飞点揪出来，这就是统计离群剔除（statistical outlier removal，SOR）。算法朴素得近乎直白：对每个点，用 kd 树找它的 \(k\) 个最近邻，算出它到这 \(k\) 个邻居的平均距离 \(d_i\)；正常表面点挤在一起，\(d_i\) 小，飞点孤悬空中，\(d_i\) 大。把全体点的 \(\{d_i\}\) 看成一个分布，求其均值 \(\mu\) 和标准差 \(\sigma\)，凡是 \(d_i>\mu+t\sigma\) 的点判为离群、剔除。这其实就是 章节 2 讲过的 \(3\sigma\) 准则用在了”邻域平均距离”这个量上，也和 章节 26 的统计判异同源——不预设固定的距离门槛，而是让数据自己的分布来定阈值。
为什么阈值要按分布定、而不是拍一个固定的毫米数？因为”多远算远”完全取决于点云的密度。同样 0.5 mm 的邻均距，在一个稠密扫描里是离群，在一个稀疏扫描里却是正常。\(\mu+t\sigma\) 把尺度交给数据本身，换一份点云不必重调参数——这正是统计阈值相对硬阈值的稳健之处。
本章取 \(k=8\)、\(t=2\)。在这份数据上，邻均距的 \(\mu+2\sigma=3.23\) mm，据此剔除了 190 个点，其中 190 个全部命中真飞点（召回 95%，对 200 个飞点而言），并且 0 个误删——没有一个真实表面点被冤枉。图 37.4 把被剔除的 190 个点用红色菱形标了出来，它们整齐地落在空域里，正是那些悬空飞点。
那漏掉的 10 个飞点哪去了？它们没被剔除，是因为运气不好（或者说运气太好）地随机落在了某个真实表面附近——一个飞点如果恰好飘到地面或立方体上方很近的地方，它的 8 个最近邻里就混进了真实表面点，邻均距被拉小到阈值以下，于是逃过了统计。这不是算法的 bug，而是统计方法的固有边界：SOR 判的是”邻域密度异常”，一个伪装成正常密度的离群点，它判不出来。诚实地讲清楚这 10 个漏网点，比报一个 100% 的召回更可信——下游算法（比如稳健拟合、ICP）本来就该对残余的少量离群点有抵抗力，而不是指望预处理一次清干净。
37.4 SciVision 实现
数据形态的 I/O 用 SciPointCloud 完成，但这里有一个必须如实写下的坑。SciPointCloud 接受 SciVector3dArray 作为点集，而 SciVector3dArray(float*, size) 这个看似方便的”从连续数组一把构造”的构造函数，在本机是惰性的——构造完 Length() 仍是 0，点根本没进去。可靠的办法是逐点 Append：
SciVector3dArray pts;
for (int i = 0; i < n; ++i) {
SciVector3d v(xyz[3*i], xyz[3*i+1], xyz[3*i+2]);
pts.Append(v); // 逐点追加；float* 构造器在本机不填充
}
pc.SetPoints(pts); // pc.Length() 此后 = n最近邻查询，SDK 的 Sci3DKdTree 是可用的，且与手写 kd 树结果一致：
SCIMV::Sci3DKdTree kt;
long rc = kt.CreateKdTree(pc);
SciVector3d q(xyz[0], xyz[1], xyz[2]);
int num = 0; SciVector3dArray pos; SciIntArray ind; SciFloatArray dist;
kt.FindKNearestNeighbors(q, 8, &num, &pos, &ind, &dist);
// dist 前四项 = 0.000 / 0.516 / 0.802 / 0.999，与手写 kd 树逐位相同第一个邻居距离 0.000（查询点找到了自己），其余与手写实现完全吻合，这给了我们一个交叉验证：本章的计时和 SOR 都基于手写 kd 树（为了确定性和可计时性），SDK 的 Sci3DKdTree 作为旁证印证了正确性。
数据转换 SciSv3DDataConvert：正向的 ConvertPointCloudToRangeImage（点云转距离图）可用，但反向的 ConvertRangeImageToPointCloud 在本机是惰性的（存活点数为 0），所以 小节 37.1 的 2.5D 丢失实验用手写分箱完成，确定性可控。
至于 SOR，SDK 的 SciSv3DClean 的 SORFILTER 特征在本机崩溃（实测退出码随堆布局漂移，见过 0xC0000005 访问违例与 0xC0000409 栈保护两种）。因此本章用一个独立子进程探针去触碰它（崩溃也不会拖垮主流程），而真正的 SOR 用手写实现：
// 手写 SOR：每点到 k 邻域的平均距离，μ+2σ 阈值剔除
for (int i = 0; i < N; ++i) {
kd.knn(&xyz[3*i], K+1, &nb); // K+1：含自身
double sd = 0; int c = 0;
for (auto& p : nb) { // 跳过自身，累加到 K 个邻居的距离
if (p.second == i) continue;
sd += std::sqrt(p.first);
if (++c == K) break;
}
meanD[i] = sd / c; // 邻均距 d_i
}
double mu = /* mean(meanD) */, sigma = /* std(meanD) */;
double thr = mu + 2.0 * sigma; // = 3.23 mm
for (int i = 0; i < N; ++i)
if (meanD[i] > thr) removed.push_back(i); // 剔除 190 点这种”SDK 作 I/O 与交叉验证、核心算法手写”的分工，是 Part IX 3D 模块的常态：点云类算法（kd 树、SOR、ICP、PCA）多数自包含、易手写，手写版还能保证确定性和可计时性，而 SDK 在本机的 3D 模块成熟度参差，能用则用、崩则隔离。完整可运行工程见 code/point_cloud_basics/。
工业案例：激光扫描点云的飞点风暴
焊缝的激光扫描是飞点的重灾区。弧光、飞溅与母材镜面反光使传感器充满虚假回波，飞点密布，若直接拿这样的点云去测焊缝余高或咬边深度，飞点会把测量基准整体拉偏。正确的流程是先做 SOR 清理、再测量，清理后焊缝轮廓立刻稳定下来。但 SOR 是一把双刃剑：阈值设得过严，它会连真实的薄边缘、尖锐特征一起误删——焊缝的毛刺尖端、咬边的最深点本身就是邻域稀疏的”孤点”，在统计上和飞点长得很像，过度清理会把真正要测的缺陷信号一并抹掉。阈值要按点云自己的噪声分布来定（\(\mu+t\sigma\) 而非固定毫米数）。准则：宁可欠清理、把抗离群的担子交给下游的稳健算法，也别过清理、把真实信号当噪声丢掉。
37.5 小结
- 三维数据有三种形态，点云最通用、距离图最规则、网格管连接：点云是无序点集，能表示任意拓扑但需额外索引；距离图是规则 2.5D 网格，可直接复用二维算子，但每个 \((x,y)\) 只存一个 \(z\)。
- 点云转距离图是有损的，损失正比于场景的”竖直度”：本章 20200 点回投 \(200\times200\) 网格只剩 12585 个（丢失 37.7%），竖直侧壁与被遮挡区整片消失——这是单视角 2.5D 的本质局限，呼应激光三角的单视角采集。能用点云就别过早塌缩成距离图。
- kd 树把无序点云的最近邻查询从 \(O(N)\) 降到 \(O(\log N)\)：轴轮换中位分裂建树、回溯时按”到超平面距离”剪枝。本章 10000 次 8-NN 查询 kd 树约 60 ms、暴力约 870 ms，加速 14.5 倍且结果逐位精确——这是一切迭代式 3D 算法（配准、滤波、特征）的地基。
- 三维的”脏”分两类，对策不同：测量噪声幅度小、零均值、贴表面，靠平滑处理；离群飞点远离表面、邻域空旷，靠统计离群剔除（SOR）删点。两者别混为一谈。
- SOR 用”邻域平均距离”的 \(\mu+t\sigma\) 阈值揪飞点，阈值随分布走：本章 \(k=8\)、\(\mu+2\sigma=3.23\) mm 剔除 190 点、命中真飞点 95%、0 误删。漏网的 10 个落在表面附近、伪装成正常密度——统计方法的固有边界，下游应保有抗残余离群的稳健性。
关于点云数据结构、空间索引与三维滤波更系统的论述，可进一步阅读 Steger 等人的著作 (Steger, Ulrich, 和 Wiedemann 2018)；三维几何与距离图处理在视觉语境下的速查可参阅 (Szeliski 2022)。kd 树这一空间索引的原始出处是 Bentley 提出多维二叉搜索树的经典论文 (Bentley 1975)，它把本章的最近邻查询从 \(O(N)\) 降到对数级；而本章及后续各章用到的体素降采样、统计离群剔除、法向估计等点云算子，工程上多以点云库（PCL）为参考实现，其总览见 Rusu 与 Cousins 的文章 (Rusu 和 Cousins 2011)。后续 章节 38 与 章节 39 将分别展开三维滤波/下采样与点云配准。