Hacker News new | past | comments | ask | show | jobs | submit login
How the Hough Transform Was Invented (2009) [pdf] (umontreal.ca)
61 points by espeed on Dec 10, 2016 | hide | past | favorite | 15 comments

Yet still no mention of the Fast Hough Transform. Not the randomized approximate one, but fast as in FFT, n²log n fast. We've been using it a lot in, e.g. the automatic vehicle classifier [0, 1]. It has been recently contributed to OpenCV [2] by my colleagues.

The title of the paper (by my company's CTO) "Hough Transform: Underestimated Tool In The Computer Vision Field" [3] still holds true. It describes the FHT algorithm rather well.

[0] http://visillect.com/en/avc

[1] pdf http://www.scs-europe.net/dlib/2015/ecms2015acceptedpapers/0...

[2] http://docs.opencv.org/3.1.0/d9/d29/namespacecv_1_1ximgproc....

[3] https://www.researchgate.net/publication/228573007_Hough_Tra...

For those interested, here's a little toy Hough transform visualizer: https://liquiddandruff.github.io/hough-transform-visualizer/

Anyone with domain knowledge cares to TL;DR the significance of the Hough Transform and its applications? Never heard of it before...

The Hough transform is used in computer vision (2d and 3d) for the recognition of edges and lines as one stage in a large processing pipeline.

Its competitor is RANSAC.

Compared to linear or orthogonal regression it has the advantage that it has quite a natural way to cope with multiple lines. Each line is represented by a high value in the Hough space. The next line can be found by removing the current maximum.

It is generalizable to more abstract shapes, but the Hough space becomes high dimensional. It is nontrivial to represent hierarchical objects, for example line segments AND the square it forms.

As MrQuincle replied, its main competitor is RANSAC, and FHT is one of the best tools in finding straight lines on images: it is indifferent to dashed lines, intersections, etc. Also, compared to RANSAC it's deterministic and doesn't involve any binarisation (for RANSAC you need a set of points, not a continuous image).

There's also a neat trick of finding vanishing points via double Hough transform.

See also [0] for an example of HT application to road markup recognition.

[0] pdf http://iitp.ru/upload/publications/7226/2015_ICMV_D.%20Krokh...

Here's a slide on it https://s3.amazonaws.com/content.udacity-data.com/courses/ud...

Basically, it's used to find parameters to a model with sample data.

Very concise explanation!

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


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?

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...

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.

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.


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

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

Is the Hough transform basically a maximum likelihood estimate?

There is a "strong relationship" between the two concepts:

R S Stephens, A Probabilistic Approach to the Hough Transform http://www.bmva.org/bmvc/1990/bmvc-90-012.pdf

Applications are open for YC Winter 2022

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact