A Complete Guide on Hough Transform

This article was published as a part of the Data Science Blogathon.

Introduction

The Hough transform (HT) is a feature extraction approach in image analysis, computer vision, and digital image processing [1]. It uses a voting mechanism to identify bad examples of objects inside a given class of forms. This voting mechanism is carried out in parameter space. Object candidates are produced as local maxima in an accumulator space using the HT algorithm.

The HT is a method for separating features of a certain shape inside a picture. The classical HT is most typically employed to detect regular curves such as lines, circles, ellipses, etc. It needs the required features to be provided in some parametric form. A generalized HT can be used when a brief analytic description of a feature(s) is not attainable. We will limit our study to the traditional HT due to the computational difficulty of the extended Hough algorithm. Despite its domain limitations, the classical HT has many applications. Most manufactured parts (as well as many anatomical parts investigated in medical imagery) have feature boundaries that standard curves can describe. The real benefit of the HT approach is that it is unaffected by picture noise and is tolerant of gaps in feature boundary descriptions.

This article will provide you with in-depth knowledge about Hough transform. It will give you a basic introduction to hough transform how exactly it works and what is the maths behind it. It also enlists merits and demerits of hough transforms with its various applications.

History

It was first developed for the automated examination of bubble chamber pictures (Hough, 1959). In 1962, the Hough transform was patented as U.S. Patent 3069654 and assigned Atomic Energy Commission to the United States as a “Method and Means for Recognizing Complex Patterns.” Because the slope might go to infinity, this invention employs a slope-intercept parameterization for straight lines, which results in infinite transform space.

Duda, R. O., and P. E. Hart, “Use of the HT to Detect Lines and Curves in Pictures,” Comm. ACM, Vol. 15, pp. 11–15 (January 1972), although it had been standard for the Radon transformation since the 1930s. In Frank O’Gorman, MB Clowes: Finding Picture Edges through Collinearity of Feature Points, O’Gorman and Clowes discuss their version. IEEE Transactions on Computers, vol. 25, no. 4, pp. 449-456. (1976) Hart, P. E., “How the HT was invented,” IEEE Signal Processing Magazine, Vol 26, Issue 6, pages 18 – 22 (November 2009) tells the tale of how the contemporary form of the HT was invented.

What is Hough Transform?

Hough Transform is a computer vision technique to detect shapes like lines and circles in an image. It converts these shapes into mathematical representations in a parameter space, making it easier to identify them even if they’re broken or obscured. This method is valuable for image analysis, pattern recognition, and object detection.

The HT is a feature extraction method in image analysis, computer vision, and digital image processing [3]. It uses a voting mechanism to identify bad examples of objects inside a given class of forms. This voting mechanism is carried out in parameter space. First, object candidates are produced as local maxima in an accumulator space, using the HT algorithm.
The traditional HT was concerned with detecting lines in an image, but it was subsequently expanded to identifying locations of arbitrary shapes, most often circles or ellipses. Richard Duda and Peter Hart devised the HT as we knew it today in 1972, calling it a “generalized HT”[4] after Paul Hough’s related 1962 patent[5]. Dana H. Ballard popularized the transformation in the computer vision field with his 1981 journal paper “Generalizing the HT to identify arbitrary forms.”

Why is it Needed?

In many circumstances, an edge detector can be used as a pre-processing stage to get picture points or pixels on the required curve in the image space. However, there may be missing points or pixels on the required curves due to flaws in either the image data or the edge detector and
spatial variations between the ideal line/circle/ellipse and the noisy edge points acquired by the edge detector. As a result, grouping the extracted edge characteristics into an appropriate collection of lines, circles, or ellipses is frequently difficult.

                                                   
1. Original image of Lane

Figure 2: Image after applying edge detection technique. Red circles show that the line is breaking there.

How Does it Work?

The Hough approach is effective for computing a global description of a feature(s) from (potentially noisy) where the number of solution classes does not need to be provided before. For example, the Hough approach for line identification is motivated by the assumption that each input measurement reflects its contribution to a globally consistent solution (e.g., the physical line which gave rise to that image point).

A line can be described analytically in a variety of ways. One of the line equations uses the parametric or normal notion: xcosθ+ysinθ=r. where r is the length of a normal from the origin to this line and θ is the orientation as given in Figure 5.

The known variables (i.e., x_i,y_i) in the Image are constants in the parametric line equation, whereas r and are the unknown variables we seek. Points in cartesian image space correspond to curves (i.e., sinusoids) in the polar Hough parameter space if we plot the potential (r, θ) values specified by each. The Hough transformation for straight lines is this point-to-curve transformation. Collinear spots in the cartesian image space become clearly obvious when examined in the Hough parameter space because they provide curves that overlap at a single (r, θ) point.

Where a and b are the circle’s center coordinates, and r is the radius. Because we now have three coordinates in the
parameter space and a 3-D accumulator, the algorithm’s computing complexity increases. (In general, the number of parameters increases the calculation and the size of the accumulator array polynomially.) As a result, the fundamental Hough approach described here is only applicable to straight lines.

Algorithm

1. Determine the range of ρ and θ. Typically, the range of θ is [0, 180] degrees and ρ is [-d, d], where d is the diagonal length of the edge. Therefore, it’s crucial to quantify the range of ρ and θ, which means there should only be a finite number of potential values.
2. Create a 2D array called the accumulator with the dimensions (num rhos, num thetas) to represent the Hough Space and set all its values to zero.
3. Use the original Image to do edge detection (ED). You can do this with whatever ED technique you like.
4. Check each pixel on the edge picture to see if it is an edge pixel. If the pixel is on edge, loop over all possible values of θ, compute the corresponding ρ, locate the θ and ρ index in the accumulator, then increase the accumulator base on those index pairs.
5. Iterate over the accumulator’s values. Retrieve the ρ and θ index, and get the value of ρ and θ from the index pair, which may then be transformed back to the form of y = ax + b if the value is greater than a specified threshold.

Sum of Hough Transform

Problem: Given set of points, use Hough transform to join these points. A(1,4), B(2,3) ,C(3,1) ,D(4,1) ,E(5,0)

Solution:

Lets think about equation of line that is y=ax+b.

Now, if we rewrite the same line equation by keeping b in LHS, then we get

b=-ax+y. So if we write the same equation for point A(1,4), then consider x=1 and y=4 so that we will get

b=-a+4. The following table shows all the equations for a given point

Now take x-0 and find corresponding y value for above given five equations

Let us plot the new point on the graph as given below in figure 6.

We can see that almost all line crosses each other at a point (-1,5). So here now a=-1 and b =5.

Now let’s put these values in the y=ax+b equation so we get y=-1x+5 so y=-x+5 is the line equation that will link all the edges.

Advantages

The HT benefits from not requiring all pixels on a single line to be contiguous. As a result, it can be quite effective when identifying lines with small gaps due to noise or when objects are partially occluded.

Disadvantages

The HT has the following drawbacks:
• It can produce deceptive results when objects align by accident;
• Rather than finite lines with definite ends, detected lines are infinite lines defined by their (m,c) values.

Application

The HT has been widely employed in numerous applications because of the benefits, such as noise immunity. 3D applications, object and form detection, lane and traffic sign recognition, industrial and medical applications, pipe and cable inspection, and underwater tracking are just a few examples [6]. Below are some examples of these applications. [7] Proposes the hierarchical additive Hough transform (HAHT) for detecting lane lines. The HAHT that is recommended accumulates the votes at various hierarchical levels. Line segmentation into multiple blocks also minimizes the computational load. [7] proposes a lane detection strategy in which the HT is merged with the joint photographic experts’ group (JPEG) compression. However, only simulations are used to test the method.

Biometric and Man-machine Interaction

A generalized hand detection model with articulated degrees of freedom is shown in [6]. It makes use of geometric feature correspondences between points and lines. The lines are recognized by the PHT. Following that, they are matched with a model. The GHT can identify Turkish finger-spelling in [6]. To produce interest zones, the scale-invariant features transform is applied (SIFT). The superfluous interest zones are eliminated using skin color reduction. [6] also suggests using hand gestures and tracking to create a real-time human-robot interaction system. In this procedure, the linked component labeling (CCL) and the HT are integrated. By sensing the skin tone, it can extract the hand’s center, orientations, and fingertip positions of all outstretched fingers.

3D Applications

A detector for 3D lines, boxes, and blocks is proposed in [6]. This approach decreases the computing cost by using 2D Hough space for parallel line detection. In addition, the 3D HT is used to extract planar faces from point clouds that are unevenly dispersed.

Object Recognition

It describes a method for detecting objects utilizing the GHT and color similarity between homogeneous portions of the item. It takes as input already segmented areas of homogenous hue. According to this research, it is resistant to changes in light, occlusion, and distortion of the segmentation output. It can distinguish items that have been rotated, scaled, and even moved around in a complicated environment.

Object Tracking

It uses a blend of uniform and Gaussian Hough transforms to conduct shape-based tracking. While the camera moves, this method can find and follow objects even against difficult backdrops like a dense forest.

Underwater Application

It provides a technique for detecting geometrical forms in underwater robot images. The recognition problem is transformed into a bounded error estimation problem, as opposed to the traditional GHT. On an autonomous underwater vehicle, [6] creates an underwater system for visually directed operations (AUV). Underwater pipelines are identified using the HT. Their orientations are then determined using binary morphology.

Industrial and Commercial Application

The HT and its various versions have various industrial and commercial uses. In, an uncrewed aerial vehicle (UAV) surveillance and inspection system are used to propose a knowledge-based power line identification approach. Before applying the LHT, a pulse-coupled neural network (PCNN) filter is constructed to eliminate background noise from picture frames. The findings are refined using knowledge-based line clustering.

Medical Application

It uses a warped frequency transform (WFT) to adjust for the dispersive behavior of ultrasonic guided waves, followed by a Wigner-Ville time-frequency analysis and the HT to increase fault localization accuracy. The locations and boundaries of vertebrae are recognized automatically. The HT is used in conjunction with the GA to determine the migrating vertebrae.

Unconventional Application

This section shows unexpected usage to demonstrate the HT’s adaptability and ever-expanding nature. It proposes a data mining technique for locating arbitrarily oriented subspace clusters. This is done by mapping the data space to the parameter space, which defines the collection of arbitrarily oriented subspaces that may be created. The clustering method works by locating clusters that may hold many database objects. Even if subspace clusters of differing dimensions are sparse or crossed by other clusters in a noisy environment, the method can discover them.

Implementation

code for Line detection using hough transform
Python Code:

Circle Detection Using Hough Transform

# Read image as gray-scale
 img = cv2.imread('/content/drive/MyDrive/Colab Notebooks/circle_hough.jpg', cv2.IMREAD_COLOR)
 # Convert to gray-scale
 print("Original Image")
 cv2_imshow(img)
 gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
 # Blur the image to reduce noise
 img_blur = cv2.medianBlur(gray, 5)
 # Apply hough transform on the image
 circles = cv2.HoughCircles(img_blur, cv2.HOUGH_GRADIENT, 1, 40, param1=100, param2=30, minRadius=1, maxRadius=40)
 # Draw detected circles
 if circles is not None:
     circles = np.uint16(np.around(circles))
     for i in circles[0, :]:
         # Draw outer circle
         cv2.circle(img, (i[0], i[1]), i[2], (0, 255, 0), 2)
         # Draw inner circle
         cv2.circle(img, (i[0], i[1]), 2, (0, 0, 255), 5)
 # Show result
 print("Circle Detection using Hough Transform")
 cv2_imshow(img)

Output

Conclusion

Over the years, the Hough transform has gained a lot of scientific attention. The noise immunity, capacity to deal with occlusion and expandability of the transform are the major motivators for such interest. It has developed into many different forms. They span the whole form detecting range, from lines to irregular shapes. New variants are predicted to emerge, bringing the transformation closer to recognizing more complicated things. The transform and its derivatives have mostly been used on binary images.

The Hough transform is now used in a wide range of applications, including traffic, biometrics, object detection, and tracking, medical applications, and industrial and commercial applications, and there is yet opportunity for more. In the future, we expect parallel computing, particularly on GPUs, to aid the development of more time-critical applications. This article will help all beginners to start with the Hough transform and will also lead to future enhancements and applications of it.

The media shown in this article is not owned by Analytics Vidhya and is used at the Author’s discretion.

Dulari Bhatt 18 Aug 2023