Editing Hough transform (section)

==<span lang="en" dir="ltr">Implementation</span>==

The linear Hough transform [[algorithm]] estimates the two parameters that define a straight line. The transform space has two dimensions, and every point in the transform space is used as an accumulator to detect or identify a line described by <math>r = x \cos \theta + y\sin \theta</math>. Every point in the detected edges in the image contributes to the accumulators.

The [[dimension]] of the accumulator equals the number of unknown parameters, i.e., two, considering quantized values of <math>r</math> and <math>\theta</math> in the pair <math>(r, \theta)</math>. For each pixel at <math>(x, y)</math> and its neighborhood, the Hough transform algorithm determines whether there is enough evidence of a straight line at that pixel. If so, it will calculate the parameters <math>(r, \theta)</math> of that line, then look for the accumulator's bin that the parameters fall into, and increment the value of that bin.

By finding the bins with the highest values, typically by looking for local maxima in the accumulator space, the most likely lines can be extracted, and their (approximate) geometric definitions read off (Shapiro and Stockman, 304). The simplest way of finding these ''peaks'' is by applying some form of threshold, but other techniques may yield better results in different circumstances – determining which lines are found, as well as how many. Since the lines returned do not contain any length information, it is often necessary, in the next step, to find which parts of the image match up with which lines. Moreover, due to imperfection errors in the edge-detection step, there will usually be errors in the accumulator space, which may make it non-trivial to find the appropriate peaks, and thus the appropriate lines.

The final result of the linear Hough transform is a two-dimensional array (matrix) similar to the accumulator—one dimension of this matrix is the quantized angle <math>\theta</math>, and the other dimension is the quantized distance <math>r</math>. Each element of the matrix has a value equal to the sum of the points or pixels that are positioned on the line represented by quantized parameters <math>(r, \theta)</math>. So the element with the highest value indicates the straight line that is most represented in the input image.<ref name="Jeppe Jensen 2007">{{cite web |last=Jensen |first=Jeppe |title=Hough Transform for Straight Lines |url=http://www.cvmt.dk/education/teaching/e07/MED3/IP/hough_lines.pdf |access-date=16 December 2011 |url-status=dead |archive-url=https://web.archive.org/web/20120426054222/http://www.cvmt.dk/education/teaching/e07/MED3/IP/hough_lines.pdf |archive-date=26 April 2012}}</ref>