4 ms·

How the Hough Transform Was Invented (2009) [pdf]

61 points by espeed 10y ago

spacehacker 10y ago
Is the Hough transform basically a maximum likelihood estimate?
- theoh 10y ago
  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 http://www.bmva.org/bmvc/1990/bmvc-90-012.pdf
stevenhuang 10y ago
For those interested, here's a little toy Hough transform visualizer: https://liquiddandruff.github.io/hough-transform-visualizer/ https://liquiddandruff.github.io/hough-transform-visualizer/
ansgri 10y ago
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 http://visillect.com/en/avc [1] pdf http://www.scs-europe.net/dlib/2015/ecms2015acceptedpapers/0521-is_ECMS2015_0089.pdf http://www.scs-europe.net/dlib/2015/ecms2015acceptedpapers/0... [2] http://docs.opencv.org/3.1.0/d9/d29/namespacecv_1_1ximgproc.html#a401697bbdcf6c4a4c7d385beda75e849 http://docs.opencv.org/3.1.0/d9/d29/namespacecv_1_1ximgproc.... [3] https://www.researchgate.net/publication/228573007_Hough_Transform_Underestimated_Tool_In_The_Computer_Vision_Field https://www.researchgate.net/publication/228573007_Hough_Tra...
endymi0n 10y ago
Anyone with domain knowledge cares to TL;DR the significance of the Hough Transform and its applications? Never heard of it before...
- MrQuincle 10y ago
  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.
- ansgri 10y ago
  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.%20Krokhina%20V.%20Blinov%20S.%20Gladilin%20I.%20Tarhanov%20V.%20Postnikov%20Fast%20roadway%20detection%20using%20car%20cabin%20video%20camera.pdf http://iitp.ru/upload/publications/7226/2015_ICMV_D.%20Krokh...
markovbling 10y ago
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 https://github.com/alexanderconway/Hough-Circle-Detection
- amelius 10y ago
  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?
  - frumiousirc 10y ago
    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.
  - _0ffh 10y ago
    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).
  - ansgri 10y ago
    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/Ballard.pdf https://web.eecs.umich.edu/~silvio/teaching/EECS598/papers/B... [1] pdf http://www.scs-europe.net/dlib/2016/ecms2016acceptedpapers/0227-is_ECMS_0075.pdf http://www.scs-europe.net/dlib/2016/ecms2016acceptedpapers/0...
henryw 10y ago
Here's a slide on it https://s3.amazonaws.com/content.udacity-data.com/courses/ud810/slides/Unit-2/2B-L1.pdf https://s3.amazonaws.com/content.udacity-data.com/courses/ud... Basically, it's used to find parameters to a model with sample data.

61 points by espeed 10y ago

spacehacker 10y ago

Is the Hough transform basically a maximum likelihood estimate?

theoh 10y ago
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 http://www.bmva.org/bmvc/1990/bmvc-90-012.pdf

stevenhuang 10y ago

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

ansgri 10y ago

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 http://visillect.com/en/avc [1] pdf http://www.scs-europe.net/dlib/2015/ecms2015acceptedpapers/0521-is_ECMS2015_0089.pdf http://www.scs-europe.net/dlib/2015/ecms2015acceptedpapers/0... [2] http://docs.opencv.org/3.1.0/d9/d29/namespacecv_1_1ximgproc.html#a401697bbdcf6c4a4c7d385beda75e849 http://docs.opencv.org/3.1.0/d9/d29/namespacecv_1_1ximgproc.... [3] https://www.researchgate.net/publication/228573007_Hough_Transform_Underestimated_Tool_In_The_Computer_Vision_Field https://www.researchgate.net/publication/228573007_Hough_Tra...

endymi0n 10y ago

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

MrQuincle 10y ago
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.
ansgri 10y ago
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.%20Krokhina%20V.%20Blinov%20S.%20Gladilin%20I.%20Tarhanov%20V.%20Postnikov%20Fast%20roadway%20detection%20using%20car%20cabin%20video%20camera.pdf http://iitp.ru/upload/publications/7226/2015_ICMV_D.%20Krokh...

markovbling 10y ago

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 https://github.com/alexanderconway/Hough-Circle-Detection

amelius 10y ago
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?
- frumiousirc 10y ago
  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.
- _0ffh 10y ago
  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).
- ansgri 10y ago
  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/Ballard.pdf https://web.eecs.umich.edu/~silvio/teaching/EECS598/papers/B... [1] pdf http://www.scs-europe.net/dlib/2016/ecms2016acceptedpapers/0227-is_ECMS_0075.pdf http://www.scs-europe.net/dlib/2016/ecms2016acceptedpapers/0...

henryw 10y ago

Here's a slide on it https://s3.amazonaws.com/content.udacity-data.com/courses/ud810/slides/Unit-2/2B-L1.pdf https://s3.amazonaws.com/content.udacity-data.com/courses/ud... Basically, it's used to find parameters to a model with sample data.