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):

enter image description here

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.

  • $\begingroup$ A simpler question: how would you go about detecting line segments in a two dimensional data? $\endgroup$ – charles.y.zheng Mar 12 '11 at 20:09
  • $\begingroup$ "..like the ones in the examples"? What examples? Can you add a link? $\endgroup$ – onestop Mar 12 '11 at 20:35
  • $\begingroup$ The Hough transform is the obvious choice. It should work well. $\endgroup$ – whuber Mar 12 '11 at 20:38
  • $\begingroup$ I just got enough reputation meanwhile to add the image example I was referring to. $\endgroup$ – cjauvin Mar 12 '11 at 20:40
  • 3
    $\begingroup$ This is not a clustering problem. In statistics, "clusters" consist of sets of objects that are mutually closer to one another than other objects. Closeness does not capture circularity: that's why neither K-means nor any other clustering algorithm will work. For this reason, this question probably fits better in the image processing or GIS sites, where you might find some experts on this issue. $\endgroup$ – whuber Mar 12 '11 at 22:33

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.

  • $\begingroup$ I would try combining all the approaches suggested: first cluster based on distance alone, as the original poster discussed, which will give you clusters that may consist of multiple circles. Then use Hough to detect planar subsets within each cluster. Then within each planar subset again use Hough to find circles. If this last step is expensive, you might be able to do effective short-circuiting: try a few triples, guess a circle, and see if a substantial fraction of the points in your subset lies very close to that circle. If so, record that circle and remove all those points, then continue. $\endgroup$ – Erik P. Mar 13 '11 at 1:55
  • 3
    $\begingroup$ This latter idea is called RANSAC and could probably be used by itself, especially if the number of circles per image is small. $\endgroup$ – SheldonCooper Mar 13 '11 at 2:58
  • $\begingroup$ Thanks for the illuminating ideas! The multi-step Hough transform seems to me the most powerful and general solution, but RANSAC really looks easier to implement, and may be just enough in my context. One problem I rapidly noticed with it though is the case where you have patterns of unbalanced sizes, which obviously biases the sampling toward bigger objects. Any thoughts about this problem? $\endgroup$ – cjauvin Mar 13 '11 at 19:08
  • $\begingroup$ Once you detect the larger circle, remove all points that belong to it from sampling. $\endgroup$ – SheldonCooper Mar 13 '11 at 21:06

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.