1

I have a cloud of 3D points. I want to find the centroid of the "densest region", meaning I want to find a close approximation to the location of the maximum value of the convolution of the point cloud with a spherical Gaussian of scale σ (where σ is chosen appropriately so that there is only one clear global maximum in the convolution, corresponding to some intuitive notion of "densest region" and centrality, relative to the distribution of points).

I assume I can estimate the solution using something like RANSAC applied to a centroid calculation, to discard outliers? Or is there a better or more robust or efficient way to find the centroid of the point cloud, in a way that is insensitive to outliers?

Luke Hutchison
  • 8,186
  • 2
  • 45
  • 40
  • this [Finding holes in 2d point sets?](https://stackoverflow.com/a/21884021/2521214) might help you with searching for the highest density region in your PCL fast. So your fitting is more bounded and has good start point already. You need just first 3 bullets in that answer and port them to 3D ... – Spektre Oct 10 '20 at 08:03
  • Been trying to think of how to handle this in a gravity like way (think black holes collapsing points). Issue I keep coming across is distance vs density cutoff. Given two or more clusters, it's not clear under what situation you should merge the clusters vs discard one of them. It's easy enough if the clusters have vastly different density, but when they have similar density it's harder to say. – Nuclearman Oct 11 '20 at 08:19
  • @Nuclearman that's not a bad idea. I experimented with some point cloud data recently for a different problem, where I was trying to get a fuzzy point cloud to snap to clear surfaces -- so I repeatedly moved each point to the centroid of its k nearest neighbors. It didn't make the data set turn into surfaces, but rather into wispy strings -- very similar to how galaxies are distributed in the universe -- and then ultimately the strings collapsed into separate clusters of many coincident points (sort of like how supermassive galaxies and black holes are formed). Maybe I could use this... – Luke Hutchison Oct 12 '20 at 20:46
  • Very interesting, k nearest neighbors mostly solves the issue with density and distance. Might be interesting to precompute the K-nearest neighbors for each point, calculate the volume, and collapse them based on smallest to largest volume. I was thinking about a possibility of doing something like that using triangles (2D version of the problem). Moving each point to the center is interesting as well, as it acts as weighting (though it would probably be performant to just store the number of points at that point). – Nuclearman Oct 13 '20 at 00:11
  • 1
    I have asked a similar question here : https://stats.stackexchange.com/q/513247/78741 – Anis LOUNIS aka AnixPasBesoin Mar 10 '21 at 17:42
  • 1
    @AnisLOUNIS yes, this is pretty much the same problem. I think the answer is to do a Gaussian smoothing on a discrete sampling of the space, then find the global maximum. Then the covariance (magnitude of axes) of the Gaussian is the only set of parameters. However, the discretization step can be costly for large spaces, and/or high dimensions. – Luke Hutchison Mar 12 '21 at 02:27

0 Answers0