Farthest Point Sampling
- Also called: FPS, furthest point sampling
- Category: Sensing › Perception outputs
- Tags: point-cloud, sampling, 3d-perception, preprocessing, deep-learning
A greedy method for picking a fixed number of points from a point cloud so they spread evenly over the shape, by repeatedly choosing the point farthest from those already chosen.
Definition
Farthest point sampling (FPS) selects a subset of M points from a set of N. It starts from one point, chosen at random or fixed, and at each step adds the point whose distance to its nearest already-selected point is largest. An implementation keeps, for every input point, its distance to the nearest selected point and updates that value after each addition, so the cost grows with N times M. The result covers the whole shape evenly, whatever the density of the original sampling. The same greedy rule is the classic 2-approximation for the k-center clustering problem, given by Gonzalez in 1985.
In point cloud deep learning, FPS became prominent through PointNet++, which uses it to choose the centers of local neighborhoods at each layer, and many later networks use it to downsample input clouds to a fixed size before inference. Compared with random sampling, which follows the density of the input and can miss thin or sparsely observed parts, FPS keeps coverage of the whole object. Compared with voxel-grid downsampling, it returns an exact number of points, which networks with fixed input sizes need.
FPS has trade-offs. It deliberately favors outliers: an isolated noise point is far from everything else and is picked early, so clouds are normally filtered first. The procedure is sequential, which makes it slow on very large clouds; GPU implementations parallelize the distance updates within each step, and approximate variants work on spatial partitions. The output depends on the starting point, and on meshes, geodesic variants measure distance along the surface instead of in straight lines.
Why it matters
Point cloud networks need fixed-size inputs, and depth sensors produce far more points than they can process. Even coverage means that small but important parts, such as handles, rims and spouts, survive downsampling, which matters for grasp and affordance prediction.
Key applications
- Preprocessing point clouds to a fixed size for neural networks
- Choosing neighborhood centers in hierarchical point networks
- Downsampling clouds before computing Chamfer or Earth mover's distance
- Selecting a spread of candidate grasp or contact points
- Picking diverse keypoints or samples for coverage
In practice
A depth camera over a workbench produces several hundred thousand points per frame. The pipeline crops the workspace, removes statistical outliers, voxel-downsamples to cut the work, and then runs FPS to get exactly the number of points the network was trained with, such as 2048. The team uses the same sampling procedure in training and on the robot, because a network trained on FPS-sampled clouds sees a different point distribution from one trained on random samples.
Common misconceptions
- FPS gives a uniform random sample — it is deterministic once the start point is fixed, and spreads points evenly in space rather than sampling at random
- FPS is robust to noise — outliers are far from everything else and get selected early, so clouds are normally filtered first
- FPS keeps the density information of the scan — it deliberately evens out density, which helps coverage but removes the cue of where the sensor saw more points
Who should know this
- 3D perception engineers
- Machine learning researchers working on point cloud networks
- Manipulation engineers using point cloud policies
Related technologies
- PointNet++
- Voxel Grid Downsampling
- Random Sampling
- k-Center Clustering
- Poisson Disk Sampling
- Open3D
Related terms
Related projects
- Open3D: Modern library for 3D point cloud processing, mesh operations, and 3D machine learning
- PCL: Industry-standard C++ library for point cloud processing in robotics perception
- OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
- pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
- LeGO-LOAM: Classic lightweight, ground-optimized lidar odometry and mapping baseline (IROS 2018)
- libpointmatcher: Modular ICP library for 2D/3D point cloud registration and mapping