About furthest point sampling

[LZDSJTU]

I want to learn about the algorithm furthest point sampling which is used in your paper. Do you have any recommended reference?

[LZDSJTU]

Also, I want to ask why the FPS is written in C++ instead of python directly. Thank you!

[ChunyangYe]

was there any problem with the implementation of the farthest point sampling algorithm in the file th_ops/sampling/tf_sampling_g.cu ?
we should sort the rest of points by the sum of the distances between the candidate point and ALL the points that have already been selected, and then choose the farthest one.
in the code, as I see, it might sort the rest points by the distance between the candidate point and the latest point. is there any problem?

[masotrix]

@LZDSJTU The FPS implemented in tf_sampling_g.cu is in C++ CUDA because it is used by PointNet++ Set Abstraction layers as a Tensorflow custom operation (https://medium.com/@taxfromdk/writing-a-new-tensorflow-operation-including-c-cuda-forward-gradient-and-grad-check-3c46708351e7), the ones must be implemented in C++/C++ CUDA (using CUDA you could take advantage of GPU parallelization, as FPS implemented in tf_sampling_g.cu does).

@ChunyangYe At first it can be thought that it only uses the latest point instead of ALL the points that have already been selected, but the key is in the "temp" array (not very descriptive name) the one keeps the distance from the selected points set to every other point. As you can see, the variable "d2" is equal to the minimum between the stored distance from the selected point set and the candidate point (in "temp"), and the distance from the last point selected and the candidate point (variable "d"). In case the latter is less, the stored distance in "temp" is updated with the distance in "d2" (already equal to "d"), Note that this is made for every point, even for the ones already in the selected point set, making "temp" to have many of its elements be 0. This makes this implementation be O(mN/k), where m is the number of points to be selected, N the total number of points, and k the number of GPU threads assigned to a given example. This implementation (which can be found in sequential python in function getGreedyPerm() from https://gist.github.com/ctralie/128cc07da67f1d2e10ea470ee2d23fe8) can be slow when dealing with many points, for example in case of a point cloud of size 10^8, which can be the case for 3D segmentation if one uses Block Merging (explained in https://arxiv.org/abs/1711.08588 and commonly used for S3DIS dataset segmentation).

I have found papers on Fast Marching Farthest Point Sampling (https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-562.pdf), but have not fount an implementation yet. I am starting to thing that I will have to make it myself.

[yiakwy]

Furthest Point Sampling is not sampling algorithm. @ChunyangYe @LZDSJTU please refer to KMeans++ about "the algorithm to give high possibility to sample the points with hightest distance to already selected points"

I also implemented it in last year in c++, javascript for arbitrary sampling. Definitely "the GPU implementation of FS" increases complexities and is not a real "sampling algorithms" which means this breaks generalisation of the whole algorithm.

[pratibhashinde]

Hi,

Can we use .py files for FPS? why are we going for c++?

Thanks in advance.