Debian Codegraph @

examples/01-filter/farthest_point_sampling.py

raw
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