Hough Transform: Unveiling the Magic of Hough Transform in Computer Vision

By Fouad Sabry

What is Hough Transform

The Hough transform is a feature extraction technique used in image analysis, computer vision, 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.

How you will benefit

(I) Insights, and validations about the following topics:

Chapter 1: Hough transform

Chapter 2: Generalised Hough transform

Chapter 3: Randomized Hough transform

Chapter 4: Circle Hough Transform

Chapter 5: Line detection

Chapter 6: 3D projection

Chapter 7: Parametric equation

Chapter 8: Equation

Chapter 9: Ellipse

Chapter 10: Cissoid

(II) Answering the public top questions about hough transform.

(III) Real world examples for the usage of hough transform in many fields.

Who this book is for

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of Hough Transform.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: Apr 28, 2024

Book preview

Chapter 1: Hough transform

The Hough transform is a common feature extraction method in the fields of digital image processing, computer vision, and image analysis. The method uses a voting system to identify imperfect instances of objects belonging to a specific class of forms. The Hough transform computation algorithm does this voting in a parameter space, where object candidates are found as local maxima in a so-called accumulator space.

Although the original Hough transform focused on finding straight lines in a picture, it has since been expanded to include finding the center of nonrectangular forms like circles and ellipses. In 1972, Richard Duda and Peter Hart developed the generalized Hough transform that is now widely utilized. In a 1981 journal article titled Generalizing the Hough transform to detect arbitrary shapes, Dana H. Ballard introduced the transform to the field of computer vision.

It was first developed for use in automated bubble chamber image analysis (Hough, 1959).

U.S. Patent 3,069,654, titled Method and Means for Recognizing Complex Patterns, was issued to the U.S. Atomic Energy Commission in 1962 and describes the Hough transform. The patent's peculiar use of slope-intercept parametrization for lines results in an unbounded transform space because the slope can be infinite.

The initial description of the rho-theta parametrization, which is now used everywhere, may be found in.

Duda, R.O.; Hart, P. E. (January 1972). Use of the Hough Transformation to Detect Lines and Curves in Pictures. Comm. ACM. 15: 11–15. doi:10.1145/361237.361242. S2CID 1105637.

Despite the fact that it wasn't until the 1930s that it became the norm for the Radon transform,.

A description of the O'Gorman–Clowes variant may be found in

O'Gorman, Frank; Clowes, MB (1976). Finding Picture Edges Through Collinearity of Feature Points. IEEE Trans. Comput. 25 (4): 449–456. doi:10.1109/TC.1976.1674627. S2CID 10851078.

How the current Hough transform was developed is described in.

Hart, P. E. (November 2009). How the Hough Transform was Invented (PDF). IEEE Signal Processing Magazine. 26 (6): 18–22. doi:10.1109/msp.2009.934181. S2CID 16245096. Archived from the original (PDF) on 2018-05-16.

The detection of elementary shapes like lines, circles, and ellipses presents a common challenge in the automated analysis of digital images. When searching for picture points or pixels that lie on the desired curve in image space, an edge detector can be employed as a preliminary step. However, there may be missing points or pixels on the required curves and spatial variations between the ideal line/circle/ellipse and the noisy edge points as they are acquired from the edge detector because of flaws in either the image data or the edge detector. Because of this, it can be challenging to properly categorize the extracted edge features as a collection of straight lines, curved lines, or ellipses. To solve this issue, the Hough transform uses an explicit voting mechanism across a set of parameterized picture objects to categorize pairs of adjacent edge points into object candidates (Shapiro and Stockman, 304).

Hough transform is most easily applied to the detection of straight lines. The point (b, m) in the parameter space represents the straight line y = mx + b. However, issues arise with vertical lines. They would result in m, the slope parameter, having infinite value. Therefore, Duda and Hart proposed the Hesse normal form for efficiency in computing.

{\displaystyle r=x\cos \theta +y\sin \theta ,}

where r is the distance from the origin to the closest point on the straight line, and \theta is the angle between the x axis and the line connecting the origin with that closest point.

This shape's intuitiveness, in the same way as the plane equation, is that every vector on the line must be perpendicular (orthogonal) to the straight line of length r that comes from the origin.

It is easy to see that the intersection point of the function line and the perpendicular line that comes from the origin is at {\displaystyle P_{0}=(r\cos \theta ,r\sin \theta )} .

So, for any point P on the line, the vector {\displaystyle P-P_{0}} must be orthogonal to the vector {\displaystyle P_{0}-0=P_{0}} .

Therefore, we get that for any point {\displaystyle P=(x,y)} on the function line, the equation {\displaystyle (P-P_{0})\cdot P_{0}=0} must be satisfied.

Therefore, {\displaystyle P\cdot P_{0}=P_{0}\cdot P_{0}} .

Since {\displaystyle P=(x,y)} and {\displaystyle P_{0}=(r\cos \theta ,r\sin \theta )} , we get

{\displaystyle r(x\cos \theta +y\sin \theta )=r^{2}(\cos ^{2}\theta +\sin ^{2}\theta )}

.

Since {\displaystyle \cos ^{2}\theta +\sin ^{2}\theta =1} , we get the final form of {\displaystyle x\cos \theta +y\sin \theta =r} .

It is therefore possible to associate with each line of the image a pair (r,\theta ) .

The (r,\theta ) plane is sometimes referred to as Hough space for the set of straight lines in two dimensions.

The Hough transform is conceptually close to the two-dimensional Radon transform thanks to its depiction.

In fact, Radon and Hough transforms are mathematically equal, However, there are distinct computational meanings associated with the two transformations.

With only one plane point to work with, a sinusoidal curve in the (r, t) coordinate system is the collection of straight lines that pass through that location, θ) plane, which is, at the time, singular.

If you take a collection of points and arrange them in a straight line, you'll have sinusoids that meet at the (r, θ) for that line.

Thus, Identifying collinear locations can be restated as a search for contemporaneous curves.

Given a shape parametrized by {\displaystyle (a_{1},...,a_{t})} , taking values in the set S 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 S , as a form of maximum likelihood estimate for shape detection.

The Hough transform is essentially a naive Bayes approximation made explicit. First, we establish a shape-space uniform prior. To identify obscured objects, we focus on the positive evidence while disregarding