Farthest Point Sampling

Repeatedly picks the point farthest from the already-selected set, downsampling a point cloud evenly to a fixed number of points.

Farthest point sampling is a point-cloud downsampling algorithm: starting from one chosen point, it repeatedly picks the remaining point whose distance to the nearest already-selected point is the largest, until the desired number of points is reached. Compared with random sampling, it covers an entire object or scene more evenly with the same number of points, and is less likely to lose structure in sparse regions; the drawback is that it requires point-by-point iteration, making it slower than random sampling or voxel downsampling on large point clouds, and its result depends on the starting point. PointNet++ (NeurIPS 2017) uses it to pick the center point of each local region at every layer, and many later point-cloud networks have followed this practice. When a robot policy takes a point cloud as input, the table and background are usually cropped out first, and then farthest point sampling brings the count down to a few hundred to a few thousand points to control compute.

ExampleThe 3D Diffusion Policy DP3 (RSS 2024) first crops the point cloud produced by a depth camera, then uses farthest point sampling to bring it down to 512 or 1,024 points, which the authors say is enough for both simulated and real-robot tasks.

Also called

FPS, Furthest Point Sampling

Related

Point Cloud · PointNet / PointNet++ · Point Cloud Filtering & Voxel Downsampling · 3D Diffusion Policy · Point Cloud Encoder · Depth Camera

Sources

PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space
3D Diffusion Policy (DP3)