Farthest Point Sampling - D-FPS vs F-FPS

The advantage of the farthest point sampling FPS (Farthest Point Sampling) method of the point cloud is that it can cover all the point clouds as much as possible, but it needs to calculate the entire distance multiple times, so it is more complex and time-consumingsampling method.

1 Farthest point sampling (FPS) sampling step

The FPS sampling steps are:
(1) Select an initial point: it can be selected randomly or according to certain rules.If randomly selected, the results obtained each time are different, otherwise the results obtained each time are the same.

(2) Calculate the distance between all points and the midpoint of (1), and select the value with the largest distance as the new initial point.

(3) Repeat the first two steps until the number of selected points meets the requirements.

Since each selected distance in (2) is the largest, the maximum distance in the iterative process will gradually decrease.This is the basis for the mask selection in the following code.If this limit is added, the point will be repeatedly selected back and forth.

2 Samples from the farthest point (D-FPS)

The farthest point sampling above is sampled by calculating the distance between points.Sampling of the farthest point refers to calculating the coordinate distance between points, usually taking three coordinates of xyz.

# -*- coding: utf-8 -*-"""Lele Perception School Public [email protected]: https://blog.csdn.net/suiyingyReference: https://github.com/yanx27/Pointnet_Pointnet2_pytorch"""import numpy as npdef farthest_point_sample(point, npoint):"""Input:xyz: pointcloud data, [N, D]npoint: number of samplesReturn:centroids: sampled pointcloud index, [npoint, D]"""N, D = point.shapexyz = point[:,:3]centroids = np.zeros((npoint,))distance = np.ones((N,)) * 1e10farthest = np.random.randint(0, N)for i in range(npoint):centroids[i] = farthestcentroid = xyz[farthest, :]dist = np.sum((xyz - centroid) ** 2, -1)mask = dist < distancedistance[mask] = dist[mask]farthest = np.argmax(distance, -1)point = point[centroids.astype(np.int32)]return point

3 Feature farthest point sampling (F-FPS)

The farthest point sampling above is sampled by calculating the distance between points.Feature farthest point sampling refers to calculating the distance between features of points.Assume that the coordinates of each point are xyz 3 dimensions, and the input features are M dimensions.When calculating the distance from the farthest point of the feature, the xyz coordinates and the feature are often spliced ​​as a new feature, and then the distance between the features is calculated for the farthest point sampling.

# -*- coding: utf-8 -*-"""Lele Perception School Public [email protected]: https://blog.csdn.net/suiyingyReference: https://github.com/yanx27/Pointnet_Pointnet2_pytorch"""import numpy as npdef farthest_point_sample(point, npoint):"""Input:xyz: pointcloud data, [N, D]npoint: number of samplesReturn:centroids: sampled pointcloud index, [npoint, D]"""N, D = point.shapexyz = pointcentroids = np.zeros((npoint,))distance = np.ones((N,)) * 1e10farthest = np.random.randint(0, N)for i in range(npoint):centroids[i] = farthestcentroid = xyz[farthest, :]dist = np.sum((xyz - centroid) ** 2, -1)mask = dist < distancedistance[mask] = dist[mask]farthest = np.argmax(distance, -1)point = point[centroids.astype(np.int32)]return point

4 [python 3D deep learning] python 3D point cloud from basic to deep learning_Coding's blog-CSDN blog_python 3D point cloud