| 1 |
""" |
| 2 |
.. _farthest_point_sampling_example: |
| 3 |
|
| 4 |
Farthest Point Sampling |
| 5 |
~~~~~~~~~~~~~~~~~~~~~~~ |
| 6 |
|
| 7 |
Subsample a point cloud so the kept points stay spaced apart instead of |
| 8 |
clumping in dense regions. |
| 9 |
|
| 10 |
Farthest point sampling (FPS) starts from a random seed and repeatedly picks |
| 11 |
the point that is farthest from the current sample set. Compared to a |
| 12 |
uniform random draw, it gives a much more even covering of the input cloud. |
| 13 |
|
| 14 |
References |
| 15 |
---------- |
| 16 |
Y. Eldar et al., "The farthest point strategy for progressive image sampling," |
| 17 |
*Proc. 12th IAPR Int. Conf. on Pattern Recognition*, Vol. 2, 1994, pp. 93-97, |
| 18 |
`doi:10.1109/ICPR.1994.577129 <https://doi.org/10.1109/ICPR.1994.577129>`_. |
| 19 |
|
| 20 |
""" |
| 21 |
|
| 22 |
# sphinx_gallery_thumbnail_number = 1 |
| 23 |
import numpy as np |
| 24 |
import pyvista as pv |
| 25 |
from pyvista import examples |
| 26 |
|
| 27 |
# %% |
| 28 |
# Load a point cloud |
| 29 |
# ~~~~~~~~~~~~~~~~~~ |
| 30 |
# :func:`~pyvista.examples.downloads.download_horse_points` returns a scanned |
| 31 |
# horse with uneven point density. |
| 32 |
|
| 33 |
cloud = examples.download_horse_points() |
| 34 |
cloud |
| 35 |
|
| 36 |
|
| 37 |
# %% |
| 38 |
# Implement farthest point sampling |
| 39 |
# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 40 |
# Each iteration tracks the distance from every input point to its closest |
| 41 |
# already-sampled neighbor and picks the point with the largest such |
| 42 |
# distance as the next sample. |
| 43 |
|
| 44 |
rng = np.random.default_rng(seed=0) |
| 45 |
|
| 46 |
|
| 47 |
def farthest_point_sampling(points, n_samples): |
| 48 |
"""Return indices of ``n_samples`` farthest-spaced points.""" |
| 49 |
sampled = np.empty(n_samples, dtype=int) |
| 50 |
sampled[0] = rng.integers(points.shape[0]) |
| 51 |
distances = np.full(points.shape[0], np.inf) |
| 52 |
for i in range(1, n_samples): |
| 53 |
last = points[sampled[i - 1]] |
| 54 |
distances = np.minimum(distances, np.linalg.norm(points - last, axis=1)) |
| 55 |
sampled[i] = np.argmax(distances) |
| 56 |
return sampled |
| 57 |
|
| 58 |
|
| 59 |
n_samples = 400 |
| 60 |
fps_ids = farthest_point_sampling(cloud.points, n_samples) |
| 61 |
random_ids = rng.choice(cloud.n_points, size=n_samples, replace=False) |
| 62 |
|
| 63 |
fps_cloud = pv.PolyData(cloud.points[fps_ids]) |
| 64 |
random_cloud = pv.PolyData(cloud.points[random_ids]) |
| 65 |
|
| 66 |
|
| 67 |
# %% |
| 68 |
# Compare with a uniform random draw |
| 69 |
# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 70 |
# The random subsample (left, red) leaves visible gaps and clumps. The |
| 71 |
# farthest-point subsample (right, blue) lays the points down in a more |
| 72 |
# uniform pattern over the surface. |
| 73 |
|
| 74 |
cpos = pv.CameraPosition( |
| 75 |
position=(0.4, -0.5, 0.25), |
| 76 |
focal_point=cloud.center, |
| 77 |
viewup=(0, 0, 1), |
| 78 |
) |
| 79 |
|
| 80 |
pl = pv.Plotter(shape=(1, 2)) |
| 81 |
pl.subplot(0, 0) |
| 82 |
pl.add_points( |
| 83 |
cloud, |
| 84 |
color='lightgray', |
| 85 |
point_size=2, |
| 86 |
render_points_as_spheres=True, |
| 87 |
opacity=0.4, |
| 88 |
) |
| 89 |
pl.add_points( |
| 90 |
random_cloud, |
| 91 |
color='tomato', |
| 92 |
point_size=10, |
| 93 |
render_points_as_spheres=True, |
| 94 |
) |
| 95 |
pl.camera_position = cpos |
| 96 |
|
| 97 |
pl.subplot(0, 1) |
| 98 |
pl.add_points( |
| 99 |
cloud, |
| 100 |
color='lightgray', |
| 101 |
point_size=2, |
| 102 |
render_points_as_spheres=True, |
| 103 |
opacity=0.4, |
| 104 |
) |
| 105 |
pl.add_points( |
| 106 |
fps_cloud, |
| 107 |
color='royalblue', |
| 108 |
point_size=10, |
| 109 |
render_points_as_spheres=True, |
| 110 |
) |
| 111 |
pl.camera_position = cpos |
| 112 |
pl.link_views() |
| 113 |
pl.show() |
| 114 |
|
| 115 |
|
| 116 |
# %% |
| 117 |
# Quantify the coverage gap |
| 118 |
# ~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 119 |
# For each input point, find the distance to its closest sample and report |
| 120 |
# the worst case. Lower is better. |
| 121 |
|
| 122 |
random_max_gap = max( |
| 123 |
np.linalg.norm(p - random_cloud.points[random_cloud.find_closest_point(p)]) |
| 124 |
for p in cloud.points |
| 125 |
) |
| 126 |
fps_max_gap = max( |
| 127 |
np.linalg.norm(p - fps_cloud.points[fps_cloud.find_closest_point(p)]) |
| 128 |
for p in cloud.points |
| 129 |
) |
| 130 |
random_max_gap, fps_max_gap |
| 131 |
# %% |
| 132 |
# .. tags:: filter |