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:
“Freud was a hero. He descended to the “Underworld” and met there stark terrors. He carried with him his theory as a Medusa’s head which turned these terrors to stone.”
—R.D. (Ronald David)
“Won’t this whole instinct matter bear revision?
Won’t almost any theory bear revision?
To err is human, not to, animal.”
—Robert Frost (1874–1963)
“We commonly say that the rich man can speak the truth, can afford honesty, can afford independence of opinion and action;—and that is the theory of nobility. But it is the rich man in a true sense, that is to say, not the man of large income and large expenditure, but solely the man whose outlay is less than his income and is steadily kept so.”
—Ralph Waldo Emerson (1803–1882)