Detect circular patterns in point cloud data For some volume reconstruction algorithm I'm working on, I need to detect an arbitrary number of circular patterns in 3d point data (coming from a LIDAR device). The patterns can be arbitrarily oriented in space, and be assumed to lie (although not perfectly) in thin 2d planes. Here is an example with two circles in the same plane (although remember this is a 3d space):

I tried many approaches.. the simplest (but the one working best so far) is clustering based on disjoint sets of the nearest neighbor graph. This works reasonably well when the patterns are far apart, but less so with circles like the ones in the example, really close to each other.
I tried K-means, but it doesn't do well: I suspect the circular point arrangement might not be well suited for it. Plus I have the additional problem of not knowing in advance the value of K.
I tried more complicated approaches, based on the detection of cycles in the nearest neighbor graph, but what I got was either too fragile or computationally expensive.
I also read about a lot of related topics (Hough transform, etc) but nothing seems to apply perfectly in this specific context. Any idea or inspiration would be appreciated.
 A: A generalized Hough transform is exactly what you want.  The difficulty is to do it efficiently, because the space of circles in 3D has six dimensions (three for the center, two to orient the plane, one for the radius).  This seems to rule out a direct calculation.
One possibility is to sneak up on the result through a sequence of simpler Hough transforms.  For instance, you could start with the (usual) Hough transform to detect planar subsets: those require only a 3D grid for the computation.  For each planar subset detected, slice the original points along that plane and perform a generalized Hough transform for circle detection.  This should work well provided the original image does not have a lot of coplanar points (other than the ones formed by the circles) that could drown out the signal generated by the circles.
If the circle sizes have a predetermined upper bound you can potentially save a lot of computation: rather than looking at all pairs or triples of points in the original image, you can focus on pairs or triples within a bounded neighborhood of each point.
A: Well, if the goal is to simply detect the $\textit{number}$ of circular patterns, and you have enough data, maybe try deep convolutional neural networks. Truly, one would need all that data labeled, yet DCNs can be used as a complementary method to the ones suggested above.
