Table of contents
1.
Introduction
2.
What is Hough Transform?
3.
Line detection using Hough Transform
3.1.
Hough Transform with parametric form of line equation 
4.
Algorithm
4.1.
Implementation
5.
Advantages of Hough Transform
6.
Disadvantages of Hough Transform
7.
Applications
8.
FAQs
9.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Hough Transform

Author Arun Nawani
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

In 2016, Apple introduced a new camera feature in its Flagship Iphone called ‘The portrait mode.’ This feature blew up as soon as it was announced and was loved by enthusiasts and casual users alike. Not to anyone’s surprise, every other leading smartphone brand followed suit. Most of you must have used the feature yourself by now. The idea was to detect the subject of focus in the image and blur out everything else. Have you ever wondered how exactly the AI carried out the process? While there are various algorithms to do so, for the sake of this blog, we’ll focus on one such algorithm - The Hough Transform. 

What is Hough Transform?

Hough Transform is basically a feature extraction method. It can detect simple shapes like circles, lines, etc in an image. 

A simple shape can be explained as a shape that can be represented with only a few parameters. Consider a line; it can be represented with only 2 parameters. Hough transforms being immune to occlusions does an excellent job in the detection of shapes like these in images. 

Line detection using Hough Transform

A line is the simplest of shapes other than a single point. Any line can be represented with the help of an equation consisting of two parameters, slope, and intercept. 

Source - link

y=mx + b

Where m = slope of the line

b = intercept 

The line can be drawn in a coordinate plane if we have the values of slope and intercept. This is known as the image space. 

We know there can be an infinite number of lines passing through a single point. However, there is one and only one line passing through a pair of points.  

Consider we have 2 points falling on the line (x1 , y1) & (x2 , y2). Individually, there can be infinite lines passing through each of the two points. But there can only be one line passing through both the points. 

Try to think of an inverse situation of this. Just like how there can be infinite lines passing through a single point, there can be infinite points coinciding with a single line.

y1=m.x1 + b for point (x1 , y1)
y2=m.x2 + b for point (x2 , y2)

 

Now, let us try to find m and b using the inverse of this. The m and b plane is called the parameter space. Equation of which is given by-

b= -x.m+y 
b= -x1.m+y1 for point (x1 , y1)
b= -x2.m+y2 for point (x2 , y2) 

 

The point of intersection gives us the parameters, m and b. 

Hough Transform with parametric form of line equation 

There is a major problem associated with using hough transform with the regular line equation y=mx + b. The algorithm wouldn’t be able to detect lines parallel to the y axis because the slope would be infinity. To solve this problem, we use the parametric equation of line.

  Source - link

Here ρ = perpendicular distance of the line from the origin(length of normal from origin)

        Θ = Angle of normal with the X-axis 

Source - link

So, instead of an m - b plane, we now have a ρ - Θ plane. The mapping of edge points now generates a cosine curve in parameter space and not a straight line. 

This was done for line detection. We can use the algorithm for other shapes as well, like circles using the parametric equation of circle x2 + y2 = r2 is x = rcosθ, y = rsinθ

Algorithm

Extract edges of the image How ? using Canny
1- initialize parameter space rs, thetas
2- Create accumulator array and initialize to zero
3- for each edge pixel     
4-     for each theta
5-         calculate r = x cos(theta) + y sin(theta)
6-         Increment accumulator at r, theta
7- Find Maximum values in accumulator (lines)
Extract related r, theta

Implementation

import numpy as np
import matplotlib.pyplot as plt

def houghLine(image):
  ''' Basic Hough line transform that builds the accumulator array
  Input : image : edge image (canny)
  Output : accumulator : the accumulator of hough space
            thetas : values of theta (-90 : 90)
            rs : values of radius (-max distance : max distance)
  '''
  Ny = image.shape[0]
  Nx = image.shape[1]

  #Max diatance is diagonal one
  Maxdist = int(np.round(np.sqrt(Nx**2 + Ny ** 2)))
  thetas = np.deg2rad(np.arange(-90, 90))
  #Range of radius
  rs = np.linspace(-Maxdist, Maxdist, 2*Maxdist)
  accumulator = np.zeros((2 * Maxdist, len(thetas)))
  for y in range(Ny):
    for x in range(Nx):
        # Check if it is an edge pixel
        #  NB: y -> rows , x -> columns
        if image[y,x] > 0:
            for k in range(len(thetas)):
              r = x*np.cos(thetas[k]) + y * np.sin(thetas[k])
              accumulator[int(r) + Maxdist,k] += 1
  return accumulator, thetas, rs

image = np.zeros((150,150))
image[:, :] = np.eye(150)
accumulator, thetas, rhos = houghLine(image)
plt.figure('Original Image')
plt.imshow(image)
plt.set_cmap('gray')
plt.figure('hough space')
plt.imshow(accumulator)
plt.set_cmap('gray')
plt.show()

 

ORIGINAL IMAGE:

HOUGH TRANSFORM:

There is one intersection point in the hough space. Hence there is only one line in the image space.

Let’s also calculate the values of rho and theta. 

idx = np.argmax(accumulator)
rho = int(rhos[int(idx / accumulator.shape[1])])
theta = thetas[int(idx % accumulator.shape[1])]
print("rho={0:.0f}, theta={1:.0f}".format(rho, np.rad2deg(theta)))

 

rho=0, theta=-45

Advantages of Hough Transform

One salient feature of the Hough Transform and is its resistance to noise in the image and its tolerance towards holes in the boundary line. The images below compare the Hough transform of a plain straight line with a dotted one. As can be seen there is almost no difference in the results. 

Hough Transform for a regular straight line 

Hough Transform for a dotted line 

Disadvantages of Hough Transform

Hough transform is kind of a brute force technique. This makes its computation extremely complex. It has 2 major limitations - 

  • It has a large memory requirement
  • It is slow

 

For accurately computing the plane parameters, the parameter space must be divided finely in all three directions with an accumulator assigned to each block. Also, it takes a lot of time to fill the accumulators when there are so many.

Also, the hough transform may recognise many similar lines instead of the correct one. And since it doesn’t provide the starting and ending point of the line, other post-processing algorithms have to be incorporated. 

Applications

  • Hough transform is commonly used in Astronomical data analysis. It allows for the development of auto-adaptive and fast algorithms for the detection of Echelle order and automated arc line identification. 
  • It is used in digital image analysis for identifying locations and certain features in digital images which give satisfactory results and can be employed to isolate features of specific shape within an image. 
  • Hough transform also has geophysical applications. It is used for mapping lineaments and circular structures such as the geophysical response from kimberlite pipes and meteorite impact craters. 
    Also read, Sampling and Quantization

FAQs

  1. Briefly explain Hough transform. 
    Hough transform is a feature extraction technique from images. It works by detecting different shapes in the image given its parameters
     
  2. State limitations of Hough Transform. 
    The complexity of Hough Transform increases at a rate of O(Am-2) with every additional parameter. Here A is the size of the image space and m is the total parameters. So it may be extremely computationally expensive for more complex shapes with more number of parameters.
     
  3. State some of the applications of Hough transform. 
  • It is widely used in traffic and transportation. Hough transform is used to detect lane lines. 
  • Hough transform is used in biometrics to identify fingerprints. 
  • Hough transform is used for object recognition. 

Key Takeaways

The hough transform is a popular feature extraction technique and the blog gives a brief introduction of the same. The blog goes through the line detection using Hough transform, its practical applications as well as limitations. If you want to deep dive into machine learning and deep learning, check out our industry-oriented Machine learning course curated by Stanford University alumni and industry experts. 

Live masterclass