Hough transform
[1][2] The purpose of the technique is to find imperfect instances of objects within a certain class of shapes by a voting procedure.
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.
O'Gorman and Clowes' variation is described in The story of how the modern form of the Hough transform was invented is given in In automated analysis of digital images, a subproblem often arises of detecting simple shapes, such as straight lines, circles or ellipses.
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).
They would give rise to unbounded values of the slope parameter m. Thus, for computational reasons, Duda and Hart[6] proposed the use of the Hesse normal form where
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.
and its neighborhood, the Hough transform algorithm determines whether there is enough evidence of a straight line at that pixel.
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.
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
An improvement suggested by O'Gorman and Clowes can be used to detect lines if one takes into account that the local gradient of the image intensity will necessarily be orthogonal to the edge.
(Shapiro and Stockman, 305) The gradient direction can be estimated to within 20°, which shortens the sinusoid trace from the full 180° to roughly 45°.
Fernandes and Oliveira [10] suggested an improved voting scheme for the Hough transform that allows a software implementation to achieve real-time performance even on relatively large images (e.g., 1280×960).
The approach not only significantly improves the performance of the voting scheme, but also produces a much cleaner accumulator and makes the transform more robust to the detection of spurious lines.
Limberger and Oliveira[11] suggested a deterministic technique for plane detection in unorganized point clouds whose cost is
It is based on a fast Hough-transform voting strategy for planar regions, inspired by the Kernel-based Hough transform (KHT).
The approach is several orders of magnitude faster than existing (non-deterministic) techniques for plane detection in point clouds, such as RHT and RANSAC, and scales better with the size of the datasets.
A circle, for instance, can be transformed into a set of three parameters, representing its center and radius, so that the Hough space becomes three dimensional.
Arbitrary ellipses and curves can also be found this way, as can any shape easily expressed as a set of parameters.
The generalization of the Hough transform for detecting analytical shapes in spaces having any dimensionality was proposed by Fernandes and Oliveira.
Also, it guarantees that the intended shapes are represented with the smallest possible number of parameters, and it allows the concurrent detection of different kinds of shapes that best fit an input set of entries with different dimensionalities and different geometric definitions (e.g., the concurrent detection of planes and spheres that best fit a set of points, straight lines and circles).
This extension suffers from the same problems as its 2D counterpart i.e., near horizontal planes can be reliably detected, while the performance deteriorates as planar direction becomes vertical (big values of
A high-dimensional parameter space for the Hough transform is not only slow, but if implemented without forethought can easily overrun the available memory.
Yonghong Xie and Qiang Ji give an efficient way of implementing the Hough transform for ellipse detection by overcoming the memory issues.
[18] As discussed in the algorithm (on page 2 of the paper), this approach uses only a one-dimensional accumulator (for the minor axis) in order to detect ellipses in the image.
(Shapiro and Stockman, 310) Thus, the Hough transform must be used with great care to detect anything other than lines or circles.
Use of the Hough transform on noisy images is a very delicate matter and generally, a denoising stage must be used before.
