Hough transform
The Hough transform is a feature extraction technique used in image analysis, computer vision, pattern recognition, and digital image processing. The purpose of the technique is to find imperfect instances of objects within a certain class of shapes by a voting procedure. This voting procedure is carried out in a parameter space, from which object candidates are obtained as local maxima in a so-called accumulator space that is explicitly constructed by the algorithm for computing the Hough transform. Mathematically it is simply the Radon transform in the plane, known since at least 1917, but the Hough transform refers to its use in image analysis.
The classical Hough transform was concerned with the identification of lines in the image, but later the Hough transform has been extended to identifying positions of arbitrary shapes, most commonly circles or ellipses. The Hough transform as it is universally used today was invented by Richard Duda and Peter Hart in 1972, who called it a "generalized Hough transform" after the related 1962 patent of Paul Hough. The transform was popularized in the computer vision community by Dana H. Ballard through a 1981 journal article titled "Generalizing the Hough transform to detect arbitrary shapes".
History
It was initially invented for machine analysis of bubble chamber photographs.The Hough transform was patented as in 1962 and assigned to the U.S. Atomic Energy Commission with the name "Method and Means for Recognizing Complex Patterns". This patent uses a slope-intercept parametrization for straight lines, which awkwardly leads to an unbounded transform space, since the slope can go to infinity.
The rho–theta parametrization universally used today was first described in
although it was already standard for the Radon transform since at least the 1930s.
O'Gorman and Clowes' variation is described in
The story of how the modern form of the Hough transform was invented is given in
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.Detecting lines
The simplest case of Hough transform is detecting straight lines. In general, the straight line can be represented as a point 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 proposed the use of the Hesse normal formwhere is the distance from the origin to the closest point on the straight line, and is the angle between the 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 to the line segment of length that comes from the origin. The intersection point of the function line and the perpendicular line that comes from the origin is at. So, for any point on the line, the vector must be orthogonal to the vector. This enforces. Therefore,. So, we get. Yet, as, we get the final form of.
It is therefore possible to associate with each line of the image a pair. The 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.
Given a single point in the plane, the set of all straight lines going through that point corresponds to a sinusoidal curve in the 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 for that line. Thus, the problem of detecting collinear points can be converted to the problem of finding concurrent curves.
Probabilistic interpretation
Given a shape parametrized by, taking values in the set 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, and interpret shape detection as maximum likelihood estimation.Explicitly, the Hough transform performs an approximate 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.
Implementation
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. 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 and in the pair. For each pixel at 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 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 geometric definitions read off. 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 similar to the accumulator—one dimension of this matrix is the quantized angle, and the other dimension is the quantized distance. 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. So the element with the highest value indicates the straight line that is most represented in the input image.
Examples
Example 1
Consider three data points, shown here as black dots.- For each data point, a number of lines are plotted going through it, all at different angles. These are shown here in different colours.
- The Hough transform accumulates contributions from all pixels in the detected edge. To each line, a support line exists which is perpendicular to it and which intersects the origin. In each case, one of these is shown as an arrow.
- The length and angle of each support line is calculated. Lengths and angles are tabulated below the diagrams.
Hence, it is understood that the corresponding lines are very similar.
One can thus assume that all points lie close to the blue line.
Example 2
The following is a different example showing the results of a Hough transform on a raster image containing two thick lines.The results of this transform were stored in a matrix. Cell value represents the number of curves through any point. Higher cell values are rendered brighter. The two distinctly bright spots are the Hough parameters of the two lines. From these spots' positions, angle and distance from image center of the two lines in the input image can be determined.