0%

根据距离的降采样

1. Furthest Point Sampling

用处:给点云或者密集点降采样,使点云达到空间中的均匀分布

Above:从正态分布到均匀分布

输入:N个点,想要的最终点数M(<N)

输出:index

思想:不停迭代离其他点最远的,直到选出M个点。

算法:

  1. 维护两个set,sampled和remain
  2. 对于每个remain中的点,在sampled找最近的,保存距离
  3. 找到remain中最近距离最远的,移动到sampled中

2. Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import numpy as np
import matplotlib.pyplot as plt
def fps(points, n_samples):
points = np.array(points)
# Represent the points by their indices in points
points_left = np.arange(len(points)) # [P]

# Initialise an array for the sampled indices
sample_inds = np.zeros(n_samples, dtype='int') # [S]

# Initialise distances to inf
dists = np.ones_like(points_left) * float('inf') # [P]

# Select a point from points by its index, save it
selected = 0
sample_inds[0] = points_left[selected]
# Delete selected
points_left = np.delete(points_left, selected) # [P - 1]
# Iteratively select points for a maximum of n_samples
for i in range(1, n_samples):
# Find the distance to the last added point in selected
# and all the others
last_added = sample_inds[i-1]

dist_to_last_added_point = (
(points[last_added] - points[points_left])**2).sum(-1) # [P - i]

# If closer, updated distances
dists[points_left] = np.minimum(dist_to_last_added_point,
dists[points_left]) # [P - i]

# We want to pick the one that has the largest nearest neighbour
# distance to the sampled points
selected = np.argmax(dists[points_left])
sample_inds[i] = points_left[selected]

# Update points_left
points_left = np.delete(points_left, selected)

return points[sample_inds]

num,dim = 300,2
x=np.random.randn(num,dim)
ds=fps(x,30)
print(x.shape)
plt.figure()
plt.subplot(1,2,1)
plt.scatter(x[:,0],x[:,1])
plt.title('Normal Dist')
plt.subplot(1,2,2)
plt.scatter(ds[:,0],ds[:,1])
plt.title('FPS Dist')
plt.show()

image-20220413162421627

3. Ref

https://minibatchai.com/ai/2021/08/07/FPS.html