# 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 simpler question: how would you go about detecting line segments in a two dimensional data? – charles.y.zheng Mar 12 '11 at 20:09
• "..like the ones in the examples"? What examples? Can you add a link? – onestop Mar 12 '11 at 20:35
• The Hough transform is the obvious choice. It should work well. – whuber Mar 12 '11 at 20:38
• I just got enough reputation meanwhile to add the image example I was referring to. – cjauvin Mar 12 '11 at 20:40
• 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. – whuber Mar 12 '11 at 22:33

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.