最远点采样（FarthestPointSampling）介绍汉堡英语单词
最远点采样(Farthest Point Sampling)是⼀种⾮常常⽤的采样算法，由于能够保证对样本的均匀采样，被⼴泛使⽤，像3D点云深度学习框架中的对样本点进⾏FPS采样再聚类作为感受野，3D⽬标检测⽹络对投票得到的散乱点进⾏FPS采样再进⾏聚类，6D位姿估计算法中⽤于选择物体的8个特征点进⾏投票并计算位姿。
对于FPS算法的原理，两篇博⽂：，以及
已经介绍的⾮常详细了，⼀句话概括就是不断迭代地选择距离已有采样点集合的最远点。这⾥再介绍⼀遍，并实测分析⼀下；
FPS算法原理：
1. 输⼊点云有N个点，从点云中选取⼀个点P0作为起始点，得到采样点集合S={P0}；
2. 计算所有点到P0的距离，构成N维数组L，从中选择最⼤值对应的点作为P1，更新采样点集合S={P0，P1}；
3. 计算所有点到P1的距离，对于每⼀个点Pi，其距离P1的距离如果⼩于L[i]，则更新L[i] = d(Pi, P1)，因此，数组L中存储的⼀直是每
⼀个点到采样点集合S的最近距离；
4. 选取L中最⼤值对应的点作为P2，更新采样点集合S={P0，P1，P2}；
5. 重复2-4步，⼀直采样到N’个⽬标采样点为⽌。
有两个问题，⼀个是初始点选择，⼀个是采⽤的距离度量；
初始点选择：
随机选择⼀个点，每次结果不同；
选择距离点云重⼼的最远点，每次结果相同，⼀般位于局部极值点，具有刻画能⼒；
距离度量
欧⽒距离：主要对于点云，在3D体空间均匀采样；关键成功因素法
测地距离：主要对于三⾓⽹格，在三⾓⽹格⾯上进⾏均匀采样；
下⾯给出测试样例，也来⾃上⾯两篇博⽂：
from __future__ import print_function
import torch
from torch.autograd import Variable
def farthest_point_sample(xyz, npoint):
"""
Input:
xyz: pointcloud data, [B, N, 3]
npoint: number of samples
Return:
centroids: sampled pointcloud index, [B, npoint]
"""
xyz = anspo(2,1)
device = xyz.device
B, N, C = xyz.shape
centroids = s(B, npoint, dtype=torch.long).to(device)# 采样点矩阵（B, npoint）
第十二英语怎么写
distance = s(B, N).to(device)*1e10# 采样点到所有点距离（B, N）
batch_indices = torch.arange(B, dtype=torch.long).to(device)# batch_size 数组
娥皇女英是什么意思#farthest = torch.randint(0, N, (B,), dtype=torch.long).to(device) # 初始时随机选择⼀点
barycenter = torch.sum((xyz),1)#计算重⼼坐标及距离重⼼最远的点
barycenter = barycenter/xyz.shape[1]
barycenter = barycenter.view(B,1,3)
dist = torch.sum((xyz - barycenter)**2,-1)
farthest = torch.max(dist,1)[1]#将距离重⼼最远的点作为第⼀个点
for i in range(npoint):
print("-------------------------------------------------------")
print("The %d farthest pts %s "%(i, farthest))
centroids[:, i]= farthest # 更新第i个最远点
centroid = xyz[batch_indices, farthest,:].view(B,1,3)# 取出这个最远点的xyz坐标
dist = torch.sum((xyz - centroid)**2,-1)# 计算点集中的所有点到这个最远点的欧式距离
print("dist : ", dist)
mask = dist < distance
print("mask %i : %s"%(i,mask))
distance[mask]= dist[mask]# 更新distance，记录样本中每个点距离所有已出现的采样点的最⼩距离print("distance: ", distance)为什么怀不上孩子
farthest = torch.max(distance,-1)[1]# 返回最远点索引
return centroids
if __name__ =='__main__':苟活于世
东南亚旅游胜地
sim_data = Variable(torch.rand(1,3,8))
print(sim_data)
centroids = farthest_point_sample(sim_data,4)
print("Sampled pts: ", centroids)
输出结果如下，可以看到得到的mask只有True的情况下，才会⽤当前计算的dist替换distance，这样distance中存储的⼀直是每⼀个点到采样点集合的最近距离，从中选择最⼤值就找到了下⼀个采样点。
tensor([[[0.4442,0.7545,0.8402,0.1476,0.6654,0.1622,0.1818,0.3758],
[0.0328,0.3010,0.0910,0.4768,0.6825,0.3810,0.1923,0.4230],
[0.5849,0.4576,0.5159,0.0993,0.3962,0.1519,0.0429,0.3123]]])
-------------------------------------------------------炒地瓜叶
The 0 farthest pts tensor([2])
dist : tensor([[0.1649,0.0548,0.0000,0.8021,0.3947,0.6762,0.6675,0.3673]]) mask 0: tensor([[True,True,True,True,True,True,True,True]])
distance: tensor([[0.1649,0.0548,0.0000,0.8021,0.3947,0.6762,0.6675,0.3673]]) -------------------------------------------------------
The 1 farthest pts tensor([3])
dist : tensor([[0.5210,0.5276,0.8021,0.0000,0.3985,0.0122,0.0853,0.1003]]) mask 1: tensor([[Fal,Fal,Fal,True,Fal,True,True,True]]) distance: tensor([[0.1649,0.0548,0.0000,0.0000,0.3947,0.0122,0.0853,0.1003]]) -------------------------------------------------------
The 2 farthest pts tensor([4])
dist : tensor([[0.5067,0.1572,0.3947,0.3985,0.0000,0.4038,0.5989,0.1583]]) mask 2: tensor([[Fal,Fal,Fal,Fal,True,Fal,Fal,Fal]]) distance: tensor([[0.1649,0.0548,0.0000,0.0000,0.0000,0.0122,0.0853,0.1003]]) -------------------------------------------------------
The 3 farthest pts tensor([0])
dist : tensor([[0.0000,0.1844,0.1649,0.5210,0.5067,0.3882,0.3881,0.2312]]) mask 3: tensor([[True,Fal,Fal,Fal,Fal,Fal,Fal,Fal]]) distance: tensor([[0.0000,0.0548,0.0000,0.0000,0.0000,0.0122,0.0853,0.1003]]) Sampled pts: tensor([[2,3,4,0]])
