Implement Farthest Point Sampling for Point Clouds

[kunaltyagi]

EDIT: #3715 (comment)

BTW: One thing that we definitely need is Farthest Point Sampling.

Random Sample exists

---

Ignore below

There is at most one point per each voxel. Naturally, some voxels will be empty because the pointcloud is not covering the entire 3D space of the voxel grid

Yes, my apologies, a silly mistake on my part, that method wouldn't work, and random downsampling would indeed be the best way to proceed. @taketwo Just as a side note, I do think it would be useful to have a function implemented for random downsampling, since it's a pretty common use case. I personally have defaulted to using cloudCompare when i want to downsample something on the fly. @zubair1502 glad you managed to fix it.

Originally posted by @haritha-j in #3620 (comment)

[haritha-j]

I'd be happy to take this on @kunaltyagi

[haritha-j]

@kunaltyagi Where should such a feature be implemented? As a method in an existing class? If so which class would be appropriate? I was thinking perhaps it would fit in inside common/io?

[SergioRAgostinho]

Where should such a feature be implemented? As a method in an existing class?

As a class. Have a look at the classes in inside filters. Explore the API, see which classes we have, what to they do and make an informed proposal.

I was thinking perhaps it would fit in inside common/io?

Definitely in filters. But please present the arguments behind your reasoning.

[haritha-j]

I was thinking of common just because of the simplicity of this method, since some of the simpler and basic features like computing the centroid were implemented there, and personally I've always done downsampling right after loading the cloud.

But you're right filters makes much more sense. So I would be following the standard format used by filter classes yeah?
Basically, from the user's perspective the process would be
instantiate new RandomDownsample class
set input cloud
set numberOfPoints
apply filter specifying the output cloud

As far as I can see the number of points is the only required parameter, since this is a very simple method. Please let me know if I'm overlooking soomething.

[taketwo]

I was thinking of common just because of the simplicity of this method,

On one hand, downsampling sounds simple enough. Set the input cloud, set the desired number of points, go! This can be a standalone function. On the other hand, to make it useful in a wide range of scenarios, we need a more complex interface. What if the user wants random but reproducible downsampling? Then we need a way to specify the seed for random number generator. What if the user wants to get the indices of kept points, not the points themselves? Then we need a way to provide access to sampled indices. And so on.

Naturally, we cannot foresee all possibilities, so PCL tries to strike a balance between simplicity and generality.

But you're right filters makes much more sense.

Not only because it's logically a filter, but also because there is a certain filter API that (experienced) PCL users expect.

I had a look into the filters module and actually there is RandomSample class which implements exactly what we are discussing. So when I wrote in the other thread "I don't think we have a ready-made solution in PCL", I was wrong. Sorry for the confusion! I've been involved with PCL for about 8 years now, but still don't know each and every class "in-person" 😄

[haritha-j]

Yes, so there is :) I just had a look.

Sorry for the confusion! I've been involved with PCL for about 8 years now, but still don't know each and every class "in-person"

No worries, Appreciate all the work you guys put into maintaining PCL.

Out of personal curiosity, is there a theoretical/practical max number of points that PCL supports? The reason I'm asking is because the filter you mentioned is restricted by RAND_MAX, which is generally 2147483647. So this function won't be "random" for any cloud with over 2 billion points right? Personally I haven't had to deal with anything bigger than a few hundred million, but I figure some people might.

[SergioRAgostinho]

Out of personal curiosity, is there a theoretical/practical max number of points that PCL supports? The reason I'm asking is because the filter you mentioned is restricted by RAND_MAX, which is generally 2147483647. So this function won't be "random" for any cloud with over 2 billion points right? Personally I haven't had to deal with anything bigger than a few hundred million, but I figure some people might.

We currently have some nasty limitations with index support due to the chosen type (int at the moment) which probably guided the reasoning behind that limit. @kunaltyagi is starting to address this. You can read more about the general idea at these two places.

https://github.com/PointCloudLibrary/pcl/wiki/PCL-RFC-0002:-Better-type-for-indices
#3651

[SergioRAgostinho]

BTW: One thing that we definitely need is Farthest Point Sampling.

[haritha-j]

that's pretty interesting, I've never had the need to use it myself. If I understand it correctly, the idea is to select points in such a way that creates a sort of 3D voronoi diagram like representation, with the input parameter being the number of points to sample?

I'd like to give it a try, one question I have is whether some sort of optimization would be required? As I understand it, a naive algorithm would be O(n^2).

[SergioRAgostinho]

that's pretty interesting, I've never had the need to use it myself. If I understand it correctly, the idea is to select points in such a way that creates a sort of 3D voronoi diagram like representation, with the input parameter being the number of points to sample?

Exactly, but I believe we need to implement 2 versions of the method. A naive one, which overlooks the implicit surface embedding a point cloud might have and uses euclidean distance between points and a second one which takes that surface into account and considers geodesic distance.
The distinction between both is important because the latter will potentially be slower and susceptible to surface reconstruction artefacts.

some sort of optimization would be required? As I understand it, a naive algorithm would be O(n^2).

Don't worry about it too much at this point. I rather have you present a naive proposal early on in a draft PR, we first focus on the interface part and unit tests, and then we can discuss and evaluate possible accelerations.

NB: the original intent of this issue was completely hijacked and we should probably either rename it or start a new one.

[haritha-j]

yes, that certainly makes sense. I'll do some research and see how the implementation should go. thanks for the advice.

[haritha-j]

I only implemented euclidean distance based sampling in this draft, It's my first PR here, so I'm sure I've overlooked some obvious stuff. Appreciate it if you could take a look.

[stale]

Marking this as stale due to 30 days of inactivity. It will be closed in 7 days if no further activity occurs.