Farthest Point Sampling 及其 CUDA 实现
目录概述
在深度学习中，在mesh模型（网格模型）上直接学习并预测是一个相当复杂的任务，一方面在于没有高效的模型，另一方面在于现实中难以直接获取性质良好的mesh模型。所以我们常会通过采样和扫描的形式将mesh模型或者现实中的物体转化为point cloud（点云），对于一个点云，其定义为一个\(N\times C\)的张量，\(N\)表示有多少个点，\(C\)表示每个点的信息。对于一个三维的点云，一般\(C=3\)，以表示\((x,y,z)\)。如果点云还携带了更多的信息例如反射强度等，则\(C=3+C^\prime\)。而评价这个点云质量的好坏，就是评价这个点云是否尽可能保留了mesh模型中的几何特征。
现在假设我们拥有一个mesh模型，其渲染效果如下图所示：
但是我们的模型不能直接处理这个mesh模型，因此我们通过扫描或者采样的方式得到了一组\(4096\times 3\)的点云：
如果我们凭借肉眼观察，可见这组点云较好地保留了mesh的几何特征，因此这组点云可以称得上是“质量不错”。
但是我们需要把这组\(4096\times 3\)点云输入到一个输入为固定大小\(256\times 3\)的模型中，我们就必须通过下采样将点云采样为\(256\times 3\)。
均匀随机采样
首先我们想到的一种最为朴素的下采样方法就是均匀随机采样（uniform random sampling），这种下采样方法在python中可以被简单实现：
# 所有的点（1 x 4096 x 3）
total_point = ...
# 进行均匀随机采样
num_samples = 256
indices = torch.randint(0, total_point.size(1), (num_samples,))
sampled_points = total_point[0, indices]
# 可视化
plot_pointcloud(sampled_points, title="uniform random sampling")
plt.show()
我们得到采样结果为：
显然这组点云的采样效果并不能称得上“质量不错”，如下图所示，经过采样之后的点并不能很好地保留原始的几何特征，显然均匀随机采样得到的点在分布上却并不均匀。
经过分析，这是因为虽然点在每个mesh平面上的分布是均匀的，但是mesh平面在空间上本身分布就不均匀。也就是说点的先验分布并不保证“空间均匀”，所以经过随机采样得到的自然也就不能保证“空间均匀”。我们需要一种“空间均匀”的均匀随机采样，而非“平面均匀”。
Farthest Point Sampling（待完成）
Farthest Point Sampling (FPS)最早被引入深度学习领域应该是Charles R. Qi等人的文章PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space，FPS算法在其中作为PointNet++特征提取的中心点采样层使用。
其基本思想是从点云中选择一个起始点，然后在剩余的点中选择与已选点距离最远的点作为下一个选定点。这个过程迭代进行，直到达到所需数量的采样点为止。通过这种方式，FPS确保了选定的点在整个点云中分布均匀，从而能够较好地表示点云的特征。
FPS的关键步骤包括：
- 选择起始点： 从点云中随机选择一个点作为起始点。
- 计算距离： 计算剩余点与已选点之间的距离。
- 选择最远点： 选择距离已选点最远的点作为下一个选定点。
- 重复步骤2和步骤3： 重复计算距离和选择最远点的过程，直到达到所需数量的采样点。
如下图所示，我们可以通过迭代的形式来理解FPS算法。假设我们拥有已采样的点集（图中红点），以及尚未被采样的点集（图中绿点），那么红点将构成一个密度场（图中虚线），那么我们可以通过点到达该点集的最短距离以估算出点所在位置的空间密度大小。显然这个距离最大的点所处的位置就是当前已采样的点集中密度最小的地方，按照“空间均匀”的原则，我们将该点加入采样集合使得空间密度方差的下降最大，因此我们将该点加入已采样的点集，完成一次迭代。
