Farthest Point Sampling

又称: FPS, furthest point sampling
类别: Sensing › Perception outputs
标签: point-cloud, sampling, 3d-perception, preprocessing, deep-learning

一种从点云中选取固定数量的点、使它们均匀分布在形状上的贪心方法，做法是反复选择离已选点最远的点。

定义

最远点采样（Farthest point sampling，FPS）从 N 个点的集合中选出由 M 个点组成的子集。它从一个点开始（随机选取或固定），每一步加入一个点，该点到离它最近的已选点的距离最大。实现时，会为每个输入点记录它到最近已选点的距离，并在每次加入新点后更新该值，因此计算量随 N 乘以 M 增长。无论原始采样的密度如何，结果都能均匀地覆盖整个形状。同样的贪心规则也是 k 中心聚类问题的经典 2 倍近似算法，由 Gonzalez 于 1985 年提出。

在点云深度学习中，FPS 因 PointNet++ 而广为人知：PointNet++ 在每一层用它选择局部邻域的中心，而后来的许多网络在推理前用它把输入点云下采样到固定大小。随机采样跟随输入的密度，可能漏掉细薄或观测稀疏的部分；与之相比，FPS 能保持对整个物体的覆盖。与体素网格下采样相比，它返回的点数是精确的，这正是输入大小固定的网络所需要的。

FPS 有其权衡。它会刻意偏向离群点：一个孤立的噪声点远离其他所有点，会被很早选中，因此通常要先对点云进行滤波。该过程是顺序执行的，这使它在非常大的点云上很慢；GPU 实现会在每一步内并行化距离更新，而近似变体则在空间划分上运行。输出取决于起始点；在网格上，测地线变体沿表面而不是沿直线测量距离。

为何重要

点云网络需要固定大小的输入，而深度传感器产生的点远多于网络能处理的数量。覆盖均匀意味着把手、边缘和壶嘴等虽小但重要的部分能在下采样中保留下来，这对抓取和可供性预测很重要。

主要应用

为神经网络把点云预处理为固定大小
在层次化点网络中选择邻域中心
在计算 Chamfer 距离或推土机距离（Earth mover's distance）之前对点云下采样
选出分布开的候选抓取点或接触点
为覆盖挑选多样化的关键点或样本

实际应用

工作台上方的一台深度相机每帧产生几十万个点。处理流程先裁剪出工作区域，去除统计离群点，用体素下采样减少计算量，然后运行 FPS，得到与网络训练时完全相同数量的点，例如 2048 个。团队在训练和机器人上使用同样的采样过程，因为用 FPS 采样的点云训练的网络，与用随机样本训练的网络看到的点分布不同。

常见误解

FPS 给出的是均匀随机样本 — 起始点一旦固定，它就是确定性的，并且是在空间中均匀分布点，而不是随机采样
FPS 对噪声鲁棒 — 离群点远离其他所有点，会被很早选中，因此通常要先对点云进行滤波
FPS 保留了扫描的密度信息 — 它刻意把密度拉平，这有助于覆盖，但去除了传感器在哪里看到更多点这一线索

谁需要了解

3D 感知工程师
研究点云网络的机器学习研究人员
使用点云策略的操作工程师

维基百科

最远优先遍历

Open Source Robotics