Farthest Point Sampling (FPS) 的算法过程
arthest Point Sampling (FPS) 的算法过程可以通过以下示例进行说明:
假设我们有一个包含 7 个点的 2D 点云,用二维平面上的坐标表示:{(0, 0), (2, 0), (4, 0), (1, 3), (3, 3), (5, 3), (3, 6)}。现在,我们想使用 FPS 将点云下采样到包含 3 个点的集合。
- 选择起始点:从点云中随机选择一个起始点,例如 (0, 0)。
- 计算距离:计算所有其他点到选定起始点的距离。对于这个例子,与 (0, 0) 的距离分别为:2, 4, 3.162, 4.242, 5.831, 和 6.708。
- 选择最远点:从剩余点中找到距离最远的点,将其添加到下采样的点集中。在这个例子中,点 (3, 6) 距离最远,因此将其添加到下采样点集中。
- 更新距离:对于剩余的点,找到它们到新选择的点((3, 6))的距离。现在,我们要找到每个剩余点到下采样点集((0, 0) 和 (3, 6))中最近点的距离。这些距离分别为:2, 4, 3.162, 3, 3 和 3.606。
- 重复步骤 3 和 4,直到我们选择了足够数量的点(在本例中为 3 个点)。下一个最远的点是 (4, 0)。因此,最终下采样的点集包括:(0, 0), (3, 6) 和 (4, 0)。
通过 FPS 算法,我们选择了分布较广的三个点,这有助于保留原始点云的几何特征。需要注意的是,实际应用中的点云通常是三维的,但这个示例说明了 FPS 的基本原理。