Talk:Hough transform

Line from a single point??

I understand almost everything about this article, but one big hangup that I'm not finding an explanation for is that the text currently says "For each pixel and its neighborhood, the Hough transform algorithm determines if there is enough evidence of an edge at that pixel. If so, it will calculate the parameters of that line, and then look for the accumulator's bin that the parameters fall into, and increase the value of that bin." But it seems to skip the step between identifying an edge point and calculating the parameters of a line. I'm brand new at this, but for me, I'm searching for edge points by comparing each pixel with it's right, lower, and right-lower corner neighbors looking for significant changes. This only identifies a single point, but no direction of the edge.

Now, later in the article, an improvement of the algorithm is mentioned taking gradient direction into account, so if this is the reference, it seems out of order.

Also, I could imaging that "For each pixel and its neighborhood" could be referring to neighboring pixels within a distance, and calculating line parameters between each pair of nearby points, but such neighbor-searching seems wasteful and against the apparent non-locality benefits of the method.

Also, more discussion on "finding concurrent curves" would be helpful.

Also, the "Rendering of Transform Results" image deserves more discussion. I've been staring at it for a while and fail to understand the visual relationship between it and the original image.

Something incorrect

I think the "Big-O(Am - 2), where A is the image space and m is the number of parameters. (Shapiro and Stockman, 310)" is incorrect, it should be "Big-O(Am + 2)", since the complexity increases with the number of parameters.

---

—Preceding unsigned comment added by 129.187.41.30 (talk) 15:09, 24 June 2008 (UTC)

The following sentence isn't 100% correct "The parameter r represents the smallest distance between the line and the .." In order to represent all the possible lines ,r can be negative as well as positive, therefore it can't be the distance, as distance is always non-negative. (Note : a few sentences later it is written that r belongs to R, therfore can be negative)

Probably it can be fixed by some other term like, 'signed distance' or something alike

Oh, and while were at it, the term "smallest distance" is also incorrect. Distance between a line and a point is the smallest possible by it's definition! The 'smallest' is relevant whenever you define the distance in the following way:

Distance(Point,Line) = Min { D(Point,q) | q belongs to Line}

It seems that nobody wants to add my proposed change. I've changed it

---

Hough's 1962 patent teaches a transform that uses the slope-intercept parametrization of straight lines. This is computationally very unwieldy-- the transform space is unbounded because the slope can go to infinity.

Azriel Rosenfeld, in his 1969 text Picture Processing by Computer (Academic Press, New York, 1969), noted this disadvantage and suggested possibly computing every transform twice, with X- and Y-axes interchanged.

In 1972 Richard Duda and I proposed instead using the rho-theta parametrization of straight lines. This now-universally-used new transform has the great advantage of leading to a bounded transform space.

See

Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp 1-15 (January, 1972)

and also

Duda, R. O. and P. E. Hart, Pattern Classification and Scene Analysis, pp 335 - 337 (John Wiley & Sons, New York, NY, 1973)

As a matter of further historical interest, this same rho-theta parametrization is used in the specialized field of integral geometry for analyzing the probability of 'random' geometric events, such as "What's the probability that a line thrown on a plane 'at random' will intersect a unit circle?"

---

NOTE: the link to Peter Hart links to a historian; it appears the target of the link has changed.

There are three flavors of Hough transform. The first (original) was used to detect straight lines in bubble chamber images. The technique parameterizes pattern space, then projects all points of interest (typically edges found via Canny edge detection) into the parameter space. Each point votes for every possible shape parameterization it could belong to. The resulting accumulator array is then thresholded and non-maxima suppressed, keeping only local minima. Indices of the bins in the accumulator correspond to shape parameterizations. By looking at bins still populated after thresholding and non-maxima suppression, it is possible to extract the parameters of all shapes of a given type in an image.

Chadman8000 (talk) 02:27, 5 March 2009 (UTC) chad miller

A note on revisions

When rewriting an article, I think that it is a good rule to keep what is good in a previous version. I must say that I like the new figure, which is illustrative. After the most recent changes in the text, however, I'm sorry to say that the article has lost quite a bit of expressing the ideas and properties of a Hough transform for an unfamiliar reader. Tpl 16:56, 11 March 2007 (UTC)

But what is the Hough transform?

I have read this article and I am none the wiser. It needs a mathematical definition of the transform as well as the waffle about what it is used for. Given an image (say a function on the plane) I presume the Hough transform is a function in Hough space. What function is it? Also what are concurrent curves? Billlion 11:47, 15 June 2007 (UTC).

The theory section reads like a bad answer scribbled in haste to an exam question. 5/10 ! Can someone who knows what a Hough transform is and can write clear mathematical prose please clean it up.Billlion (talk) 12:29, 25 November 2007 (UTC)

Agreed. I had to read through it repeatedly for hours, and I still don't get it.202.188.138.63 (talk) 14:58, 25 November 2007 (UTC)

Having just read a few papers and it transpires that the Hough transform in its simplest form is simply the discretized Radon transform of a binary image. This is usually thresholded so that the largest values in the sinogram are taken to indicate lines in the original image. That is the points that map into high value pixels (or groups of nearby pixels) in the sinogram space are considered to line on straight lines. In some sense it is not really a transform in the sense of a Radon transform or Fourier transform, it is a method of using the Radon transform to identify lines in the image. Unless anyone feels like having a go before I get around to it I suggest editing the section to reflect this point of view. This editorial raises the issue of disageement over if it is really a transform [1] for example. While I am at it, we need to get rid of the high-school style y=mx+c line parameterization! Billlion (talk) 16:45, 25 November 2007 (UTC)

After the first comments by user Billion, I have made a quick rewrite of the the article in order to hopefully make it more readable. As user Billion points out, there are close similarities to the Radon transform. The Hough transform however has a long history of being used in image processing, image analysis and computer vision, and I would therefore not advice to smash this article into a specific instance of the Radon transform -- this would make readers from the image processing, image analysis and computer vision communities complete lost unless they already know about the Radon transform and its relations to the Hough transform. Moreover, the Radon transform does not capture the detection of circles or ellipses, which are also very common applications of the Hough transform. Although the Wikipedia article on the Hough transform is (or at least was) not very well written, it (at least roghly) reflects the notions of how the Hough transform is taught in image processing courses. Although I have not personally written about the specific topics of circle and ellipse detection, I say that it would be valuable to extend this article with these notions. Tpl (talk) 17:52, 25 November 2007 (UTC)

Did our edits cross over? You seem to have reverted some of my edits to the the high school maths including inconsistent use of math markup, and the spurious (m,c) parameterization. I agree that it should be accessable to the image processing community but that is no reason to make it sound obscure and amateurish to the general but mathematically literate audience.Billlion (talk) 19:16, 25 November 2007 (UTC)

Possibly, our changes did cross over (sorry if I did note these). Concerning the style of presentation, have no aims to make things sound obscure or amateurish, rather contrary. Concerning the math description, I did actually make an attempt to clean it up a long time (a year?) ago, but I was overruled by what I perceived as more energetic people who made the text too talkative according to my taste. However, I find it important to not make the explanation more complicated than it needs to be, and according to my belief you don't need to introduce the Radon transform as a prerequisite to describing how the Hough transform is used in the image processing community for detecting lines, circles or ellipses. Tpl (talk) 07:36, 26 November 2007 (UTC)

I think its just the old stuff accidentally left in by our edit cross that is obscure. I will look over it and see if I can weave in my improvements taking note of what you say. I wonder if the mx+c notation should be included later as it is largely of historical interest now, having introduced the sinogram coordinates and explained what the Radon transfor is. Billlion (talk) 09:10, 26 November 2007 (UTC)

I think it is much easier for someone to understand how the Hough transform works in its simplest and original form using the y=mx+c parameterization and then build upon that to explain r-theta and possibly make the connection with the Radon transform. Having a solid mathematical foundation for the hough transform (or any other transform) is a good thing but please do not forget that wikipedia is not only for the academia. —Preceding unsigned comment added by 217.154.24.242 (talk) 14:43, 1 April 2009 (UTC)

On Illustration

I'm no Hough Transform expert, but it seems that the way the algorithm discussed here works is basically equivalent to the well known gemoetric property: Given a point X and a line L, all circles having a diameter with one end at X and the other end on L will intersect L again at the point of L nearest to X. This perhaps says nothing new about the algorithm, and the circles may still need to be transformed into sine curves in the angle,radius space -- the high accumulation points can be located without doing this last step, but perhaps there are computational or accuracy reasons for doing so?

My point is, though, that perhaps the intersecting circles explanation is easier to grasp than jumping straight to the intersecting sine waves. The fact of the intersections and their location and relation to the line in question seems immediate, and may suggest limitations or extensions of the algorithm. KRD —Preceding unsigned comment added by 75.109.202.185 (talk) 23:04, 22 June 2009 (UTC)

Rename it: Duda-Hart-Hough Transform

I would like to propose that we rename the title, and usage within the page, to be the Duda-Hart-Hough Transform, and that we encourage the community to adopt this name.

The rationale is that Duda and Hart made a seminal contribution and deserve co-authorship. The original formulation by Hough had a defect; Duda and Hart fixed the defect, and as the article notes, their formulation is now the one that is universally used.

There is certainly precedent for this kind of naming, e.g. the Cocke-Kasami-Younger algorithm for parsing.

Anyone who knows it by the name of Hough Transform will instantly recognize the referent, so it should not cause any confusion. —Preceding unsigned comment added by Gordonnovak (talk • contribs) 21:16, 8 January 2010 (UTC)