Theory
In automated analysis of digital images, a subproblem often arises of detecting simple shapes, such as straight lines, circles or ellipses. In many cases an 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).
The simplest case of Hough transform is the linear transform for detecting straight lines. In the image space, the straight line can be described as y = mx + b and can be graphically plotted for each pair of image points (x, y). In the Hough transform, a main idea is to consider the characteristics of the straight line not as image points (x1, y1), (x2, y2), etc., but instead, in terms of its parameters, i.e., the slope parameter m and the intercept parameter b. Based on that fact, the straight line y = mx + b can be represented as a point (b, m) in the parameter space. However, one faces the problem that vertical lines give rise to unbounded values of the parameters m and b. For computational reasons, it is therefore better to use a different pair of parameters, denoted and (theta), for the lines in the Hough transform. These are the Polar Coordinates.
The parameter represents the distance between the line and the origin, while is the angle of the vector from the origin to this closest point (see Coordinates). Using this parameterization, the equation of the line can be written as
which can be rearranged to (Shapiro and Stockman, 304).
It is therefore possible to associate with each line of the image a pair (r,θ) which is unique if )
For an arbitrary point on the image plane with coordinates, e.g., (x0, y0), the lines that go through it are the pairs (r,θ) with
,
where (the distance between the line and the origin) is determined by θ.
This corresponds to a sinusoidal curve in the (r,θ) plane, which is unique to that point. If the curves corresponding to two points are superimposed, the location (in the Hough space) where they cross corresponds to a line (in the original image space) that passes through both points. More generally, a set of points that form a straight line will produce sinusoids which cross at the parameters for that line. Thus, the problem of detecting collinear points can be converted to the problem of finding concurrent curves.
Read more about this topic: Hough Transform
Famous quotes containing the word theory:
“A theory of the middle class: that it is not to be determined by its financial situation but rather by its relation to government. That is, one could shade down from an actual ruling or governing class to a class hopelessly out of relation to government, thinking of gov’t as beyond its control, of itself as wholly controlled by gov’t. Somewhere in between and in gradations is the group that has the sense that gov’t exists for it, and shapes its consciousness accordingly.”
—Lionel Trilling (1905–1975)
“By the “mud-sill” theory it is assumed that labor and education are incompatible; and any practical combination of them impossible. According to that theory, a blind horse upon a tread-mill, is a perfect illustration of what a laborer should be—all the better for being blind, that he could not tread out of place, or kick understandingly.... Free labor insists on universal education.”
—Abraham Lincoln (1809–1865)
“It makes no sense to say what the objects of a theory are,
beyond saying how to interpret or reinterpret that theory in another.”
—Willard Van Orman Quine (b. 1908)