Editing Hough transform (section)

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