Hacker News Reader

Comment by markovbling | Hacker News Reader

Very concise explanation!

Posted this before - had to implement Hough circle detection from scratch in JavaScript in case anyone is interested:

https://github.com/alexanderconway/Hough-Circle-Detection

I'm wondering if the Hough transform can also be used to detect shapes that look like circles (but are not necessarily circles). And if so, what are the limits, i.e., what is the worst "circular" shape still detected?

Also, can it be used to detect circular arcs?

There will be a certain resolution. An oval that is HT'ed will turn into a smeared oblong point in Hough space. There can also be biases in the result.

Circular arcs can be detected but how well depends on how long they are and depending on the amount and shapes of whatever other features exist in the image.

Hough can be thought of as a convolution of an image with a kernel that is a delta function in the parameter space. Peaks in the parameter space are then interpreted as being representative of features in the real space and with the strength of the representation being that of the height of the peak.

No, not really. But I'm confident you could derive an analogous transformation for circles/arcs. But instead of mapping into a 2d space you'd probably have to map into a 3d space (2d for the center and 1d for radius).

It is called Generalised Hough Transform [0] (google and wiki also know it), the problem is, even circle space is 3-dimensional (x, y, r), and therefore cannot be computed faster than O(n³). Even that cannot be achieved without some magic since the circle perimeter is O(n), making a naïve solution O(n⁴). So we can hope for something like O(n³log²n).

Our lab has done some research on fast GHT using general-purpose computation scheme optimisation, but I cannot find any publications in English from that distant period. For 3D Hough transform, there's an efficient solution for finding the argmax (3d line), also by my colleagues [1]

[0] pdf https://web.eecs.umich.edu/~silvio/teaching/EECS598/papers/B...

[1] pdf http://www.scs-europe.net/dlib/2016/ecms2016acceptedpapers/0...

It is possible to pick three distinct points, which uniquely identify a circle, and map this to a Hough space.

It is called the randomized Hough transform.

https://en.wikipedia.org/wiki/Randomized_Hough_transform

Circular arcs is stretching it. :-) Do you need to find the endpoints of the arc? That would be two more dimensions to search over. If that's the case I would just use a maximum likelihood approach. You have to be careful in that case, if you have a circle the distance of points on the inside of the circle and points on the outside of the circle meshes up any naive fitting method.

Kinda hacky but I believe if you tinker with the accumulator cutoff parameter, you can detect circular arcs just using the Hough circle transform but I think it'd be specific to the problem and being able to tune the cutoff parameter reliably :)

Reply on news.ycombinator.com