第四章 点云下采样与关键点提取
点云数据量太大，直接处理往往跑不动。这是每个做激光雷达的人都会遇到的第一个坎。我刚开始接触64线激光雷达时，一帧点云几十万个点，算法还没跑起来内存先爆了。后来才明白——不是所有点都值得处理。
这一章我们聊两个核心操作：下采样和关键点提取。前者是为了降数据量，后者是为了找特征点。两者目标不同，但经常配合使用。
核心观点：下采样保留几何轮廓，关键点提取保留几何特征。先降采样再提关键点，是工业级点云管线的标准做法。
4.1 均匀采样（体素下采样）
均匀采样是最简单、最常用的下采样方法。说白了就是把空间切成小立方体，每个立方体里只保留一个点。这个点可以是体素中心，也可以是体素内所有点的重心。
我习惯用体素重心法。为什么？因为重心点更能代表局部几何信息。你想想看，如果体素里正好有噪声点，取中心点可能被带偏，但重心会做平均，鲁棒性更好。
| 方法 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 体素中心 | 取体素几何中心 | 计算快 | 可能偏离实际点分布 |
| 体素重心 | 取体素内所有点均值 | 更准确 | 需要额外计算均值 |
| 体素随机 | 随机选一个点 | 保留原始点 | 随机性大 |
// C++ 体素下采样核心逻辑（PCL 风格）
pcl::VoxelGrid<pcl::PointXYZ> voxel_filter;
voxel_filter.setInputCloud(cloud);
voxel_filter.setLeafSize(0.1f, 0.1f, 0.1f); // 体素边长 10cm
voxel_filter.filter(*cloud_filtered);体素大小怎么选？ 我一般这样定：室内场景 5-10cm，室外道路 10-20cm，远距离点云 20-50cm。体素太小降采样效果不明显，太大则丢失细节。记住一个原则——体素边长不要超过目标物体最小尺寸的 1/3。
4.2 最远点采样（FPS）
均匀采样有个问题——它不管点云密度。密度高的区域采样点多，密度低的区域采样点少。FPS 就不一样了，它保证采样点在整个点云里均匀分布。
FPS 的思路很直接：先随机选一个点，然后每次选离已选点集最远的那个点。重复直到采样数量够。这样做出来的采样点，覆盖范围最大。
我在做三维重建时用过 FPS。当时需要从几十万点中选 1024 个点作为网络输入，均匀采样效果总是不稳定，换成 FPS 后结果稳定多了。不过代价是——FPS 很慢。复杂度 O(n×k)，n 是原始点数，k 是采样点数。点云一大，跑起来让人着急。
// FPS 伪代码
function farthest_point_sampling(points, k):
selected = []
dist = [inf] * len(points)
// 随机选第一个点
idx = random(0, len(points))
selected.append(idx)
for i in range(k - 1):
// 更新距离
for j in range(len(points)):
d = distance(points[j], points[idx])
dist[j] = min(dist[j], d)
// 选最远点
idx = argmax(dist)
selected.append(idx)
return selected避坑提醒：FPS 对离群点非常敏感。我曾经在室外场景用 FPS 采样，结果第一个点选到了远处的孤立噪声点，后续采样全围着它转，采样结果完全偏离了主体。建议先做一次离群点滤波，再做 FPS。
4.3 ISS 关键点
下采样是降数据量，关键点提取是找特征点。ISS（Intrinsic Shape Signatures）就是专门干这个的。
ISS 的核心思想：找那些在各个方向上变化都很大的点。怎么衡量？用协方差矩阵的特征值。如果一个点的三个特征值 λ1 ≥ λ2 ≥ λ3，且 λ2/λ1 和 λ3/λ2 都比较大，说明这个点周围在各个方向上都有明显变化——这就是关键点。
我拿 ISS 做过室内走廊的点云配准。走廊场景特征少，墙面、地面都是平面，ISS 能稳定提取出门框、墙角这些有区分度的点。配准成功率从 60% 提升到了 85%。
// ISS 关键点提取（PCL）
pcl::ISSKeypoint3D<pcl::PointXYZ, pcl::PointXYZ> iss;
iss.setInputCloud(cloud);
iss.setSalientRadius(0.1f); // 搜索半径
iss.setNonMaxRadius(0.05f); // 非极大抑制半径
iss.setThreshold21(0.975f); // λ2/λ1 阈值
iss.setThreshold32(0.975f); // λ3/λ2 阈值
iss.compute(*keypoints);| 参数 | 作用 | 推荐值 |
|---|---|---|
| Salient Radius | 局部邻域搜索半径 | 0.05-0.2m |
| NonMax Radius | 非极大抑制半径 | Salient Radius 的一半 |
| Threshold21 | λ2/λ1 下限 | 0.9-0.99 |
| Threshold32 | λ3/λ2 下限 | 0.9-0.99 |
参数调优经验：阈值设得越高，提取的关键点越少但越稳定。我一般从 0.975 开始调。如果关键点太少（比如不到 10 个），就降到 0.95；如果太多（几百个），就升到 0.99。没有固定值，看场景调。
4.4 Harris3D 关键点
Harris3D 是 2D Harris 角点检测在三维空间的扩展。2D Harris 看的是图像梯度变化，3D Harris 看的是点云局部曲面的变化。
具体做法：对每个点，计算其邻域点集的协方差矩阵，然后构造 Harris 响应函数 R = det(M) - k × trace(M)²。R 值大的点就是关键点。
嗯，这里要注意：Harris3D 对噪声比较敏感。我试过在室外道路场景用 Harris3D，路面上的小坑洼、碎石都会产生大量假关键点。后来我加了两个预处理——先平滑再提取，效果好了很多。
// Harris3D 关键点提取（PCL）
pcl::HarrisKeypoint3D<pcl::PointXYZ, pcl::PointXYZI> harris;
harris.setInputCloud(cloud);
harris.setRadius(0.1f); // 搜索半径
harris.setThreshold(1e-6); // 响应阈值
harris.setNonMaxSupression(true); // 非极大抑制
harris.compute(*keypoints);4.5 四种方法对比与选型
四种方法各有适用场景。我整理了一张对比表，方便你快速选型。
| 方法 | 类型 | 速度 | 适用场景 | 缺点 |
|---|---|---|---|---|
| 均匀采样 | 下采样 | 快 | 通用降采样、预处理 | 密度不均时效果差 |
| FPS | 下采样 | 慢 | 需要均匀覆盖的场景 | 对离群点敏感 |
| ISS | 关键点 | 中 | 室内、结构化场景 | 参数调起来麻烦 |
| Harris3D | 关键点 | 中 | 有丰富几何特征的场景 | 对噪声敏感 |
我的推荐管线：
- 先做离群点滤波（统计滤波或半径滤波）
- 用均匀采样降采样到合适密度（比如体素 10cm）
- 再用 ISS 或 Harris3D 提取关键点
- 如果对覆盖均匀性有要求，把均匀采样换成 FPS
这套管线我在三个项目里验证过，稳定可靠。
4.6 性能优化要点
点云处理绕不开性能问题。我踩过不少坑，分享几个优化经验。
- 体素下采样用哈希表：不要用暴力遍历找体素归属，用哈希映射把三维坐标映射到一维索引。速度能快 5-10 倍。
- FPS 用 KD-Tree 加速：每次找最远点时，用 KD-Tree 做最近邻查询，复杂度从 O(n×k) 降到 O(n×log n + k×log n)。
- ISS 和 Harris3D 先降采样：在降采样后的点云上提取关键点，速度提升明显，关键点质量几乎不受影响。
- 多线程并行：体素划分、邻域搜索都可以并行。OpenMP 一把梭，简单有效。
// 哈希体素索引示例
inline int64_t voxelHash(int x, int y, int z) {
return (static_cast<int64_t>(x) << 42) |
(static_cast<int64_t>(y) << 21) |
static_cast<int64_t>(z);
}
// 用 unordered_map 做体素聚合，比遍历快很多性能陷阱：我曾经在嵌入式设备上直接跑 FPS，一帧 10 万点的点云跑了 3 秒多。后来发现是距离计算用了 double 类型，改成 float 后降到 1.2 秒。再配合 KD-Tree 加速，最终稳定在 200ms 以内。细节决定性能。
好了，这一章的内容就是这些。下采样和关键点提取是点云处理的基石，掌握了它们，后面的配准、分割、识别才能站得住脚。代码我已经贴出来了，建议你拿自己的数据跑一跑，看看不同参数的效果差异。实践出真知。