Editing Hough transform (section)

==Theory==

In automated analysis of [[digital image]]s, a subproblem often arises of detecting simple shapes, such as straight lines, circles or ellipses. In many cases an [[edge detection|edge detector]] can be used as a pre-processing stage to obtain image points or image pixels that are on the desired curve in the image space. Due to imperfections in either the image data or the edge detector, however, there may be missing points or pixels on the desired curves as well as spatial deviations between the ideal line/circle/ellipse and the noisy edge points as they are obtained from the edge detector. For these reasons, it is often non-trivial to group the extracted edge features to an appropriate set of lines, circles or ellipses. The purpose of the Hough transform is to address this problem by making it possible to perform groupings of edge points into object candidates by performing an explicit voting procedure over a set of parameterized image objects (Shapiro and Stockman, 304).

=== Detecting lines ===
The simplest case of Hough transform is detecting straight lines. In general, the straight line {{nobr|''y'' {{=}} ''mx'' + ''b''}} can be represented as a point (''b'',&nbsp;''m'') in the parameter space. However, vertical lines pose a problem. They would give rise to unbounded values of the slope parameter ''m''. Thus, for computational reasons, Duda and Hart<ref>{{cite web |url=http://www.ai.sri.com/pubs/files/tn036-duda71.pdf  |title=Use of the Hough Transformation to Detect Lines and Curves in Pictures |author1=[[Richard O. Duda]] |author2=[[Peter E. Hart]] |publisher=[[Artificial Intelligence Center]] |date=April 1971}}</ref> proposed the use of the [[Hesse normal form]]

: <math>r = x \cos\theta + y \sin\theta,</math>

where <math>r</math> is the distance from the [[Origin (mathematics)|origin]] to the closest point on the straight line, and <math>\theta</math> is the angle between the <math>x</math> axis and the line connecting the origin with that closest point.

The intuition for this form, similarly to the plane equation, is that every vector on the line must be perpendicular (orthogonal) to the straight line of length <math>r</math> that comes from the origin. It can be seen that the intersection point of the function line and the perpendicular line that comes from the origin is at <math>P_0 = (r \cos \theta, r \sin \theta)</math>. So, for any point <math>P</math> on the line, the vector <math>P - P_0</math> must be orthogonal to the vector <math>P_0 - 0 = P_0</math>. Therefore, we get that for any point <math>P = (x, y)</math> on the function line, the equation <math>(P - P_0) \cdot P_0 = 0</math> must be satisfied. Therefore, <math>P \cdot P_0 = P_0 \cdot P_0</math>. Since <math>P = (x, y)</math> and <math>P_0 = (r \cos \theta, r \sin \theta)</math>, we get <math>r(x \cos \theta + y \sin \theta) = r^2 (\cos^2 \theta + \sin^2 \theta)</math>. Since <math>\cos^2 \theta + \sin^2 \theta = 1</math>, we get the final form of <math>x \cos \theta + y \sin \theta = r</math>.

[[File:R theta line.GIF|213px|left]]
It is therefore possible to associate with each line of the image a pair <math>(r, \theta)</math>. The <math>(r, \theta)</math> plane is sometimes referred to as ''Hough space'' for the set of straight lines in two dimensions. This representation makes the Hough transform conceptually very close to the two-dimensional [[Radon transform]]. In fact, the Hough transform is mathematically equivalent to the Radon transform, but the two transformations have different computational interpretations traditionally associated with them.<ref>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.9419 A short introduction to the Radon and Hough transforms and how they relate to each other<!-- Bot generated title -->]. CiteSeerX.</ref>

Given a ''single point'' in the plane, the set of ''all'' straight lines going through that point corresponds to a [[Sine wave|sinusoidal curve]] in the (''r'',&nbsp;''θ'') plane, which is unique to that point. A set of two or more points that form a straight line will produce sinusoids crossing at the (''r'',&nbsp;''θ'') for that line. Thus, the problem of detecting [[Line (geometry)#Collinear points|collinear points]] can be converted to the problem of finding [[Concurrent lines|concurrent curves]].

=== Probabilistic interpretation ===
Given a shape parametrized by <math>(a_1, ..., a_t)</math>, taking values in the set <math>S</math> called the shape space, one can interpret the Hough transform as the inverse transform of a [[probability distribution]] on the image space to the shape space <math>S</math>, and interpret shape detection as [[maximum likelihood estimation]].

Explicitly, the Hough transform performs an approximate [[Naive Bayes classifier|naive Bayes]] inference. We start with a uniform prior on the shape space. We consider only the positive evidence, and ignore all negative evidence, so that we can detect partially occluded shapes. 

We add up the [[log-likelihood]] in the shape space up to an additive constant. The assumption of ''naive Bayes'' means that all pixels in the image space provide independent evidence, so that their likelihoods multiply, that is, their log-likelihoods add. The freedom in additive constant allows us to perform no operation on the "background pixels" in shape space.

Finally, we perform maximum likelihood estimation by picking out the peaks in the log-likelihood on the shape space.<ref>{{Cite book |last=Stephens |first=R. S. |chapter=A probabilistic approach to the Hough Transform |title=Procedings of the British Machine Vision Conference 1990 |date=1990 |chapter-url=http://dx.doi.org/10.5244/c.4.12 |pages=12.1–12.6 |publisher=British Machine Vision Association |doi=10.5244/c.4.12}}</ref>