Hough transform opencv | TheAILearner

In the previous blog, we discuss how the Hough transform can be used to detect lines in an image. Now, in this blog, let’s extend our knowledge of Hough transform to detect circles. This is also known as Hough Circle Transform. So, let’s get started.

We know that a circle can be represented as (x-a)² + (y-b)² = r² where a, b represents the circle center and r is the radius. So, we require 3 parameters (a,b,r) to completely describe the circle.

Recall from the previous blog, a line requires a 2D accumulator array as a line was defined by two parameters (r,θ). So, for a circle, we would require a 3D accumulator array. Now, let’s discuss how to fill this accumulator array.

Let’s take a simple case, where the radius r is known to us. In that case, the 3D accumulator array [a,b,r] will become 2D [a,b]. And each point in the (x, y) space will be equivalent to a circle in the (a, b) space as shown below.

Now, similar to what we did in the Hough line transform, we will first draw the circles in the ab space corresponding to each edge point. Then we will find the point of intersection (actually the local maxima in the accumulator array) which will correspond to the original circle center. Now, let’s understand this with the help of image taken from Wikipedia.

Here, for each white point in the left image, we draw the corresponding circles in the ab space (Assume that the radius is known to us). Then we find the intersection point (local maxima), see the red point in the right image. This will be the original circle center. This 2D accumulator corresponds to one row of the 3D accumulator array.

Here, we assumed that the radius is known to us. In practice, we take different radius values and repeat the above procedure. Corresponding to each r value, we will fill the 3D accumulator array. A simple question, what is the maximum plausible value that the radius can take? Obviously, for images, this can’t be greater than the diagonal length of the image.

Below is the pseudo-code for the Hough Circle Transform.

Algorithm

Initialize the accumulator (H[a,b,r]) to all zeros
Find the edge image using any edge detector
For r= 0 to diagonal image length
- For each edge pixel (x,y) in the image
  - For Θ = 0 to 360
    - a = x – r*cosΘ
    - b = y – r*sinΘ
    - H[a,b,r] = H[a,b,r] +1
Find the [a,b,r] value(s), where H[a,b,r] is above a suitable threshold value

Problem

As you might have guessed, the above algorithm is inefficient since it involves dealing with 3D parameter space. Also, we may face a sparsity problem because only a few accumulator cells would be filled. So, to overcome this, OpenCV uses a slightly trickier method known as the Hough gradient method. So, let’s understand how that works.

OpenCV Hough Gradient Method

As is clear from the name, this method takes into account the gradient information. Earlier for each edge point, we were drawing the corresponding circles in the parameter space and thereby incrementing the accumulator cells. But now instead of drawing the full circle, we only increment the accumulator cells in the gradient direction of each edge pixel.

This algorithm consists of 2 steps:

First, you find all the plausible candidates for the circle centers
Then for each candidate center, we find the best radius

Let’s understand each step in detail. You can find the OpenCV code here.

First, the edge image is calculated using the Canny edge detector. Then the gradient information is computed using the Sobel operator for each edge pixel. Now, for each edge pixel, we increment the accumulator cells that lie in both directions of the gradient. Then you select all those accumulator cells that are both local maxima and above a certain threshold. All these accumulator cells are plausible candidates for circle centers.

Once you obtained the center candidates, now the task is to find the best radius for each candidate. Obviously, the parameter space is now reduced to 1D. To fill this 1D accumulator array, for each candidate center just calculate its distance from all edge pixels(this is exactly what radius is) and increment the corresponding accumulator cell. The best radius will be the one that is best supported (voted) by the edge pixels. Repeat this for each candidate center. Discard those centers that don’t have enough support and that are close to the previously selected center. This is what the Hough Gradient method does coarsely.

Now, let’s discuss how to perform the Hough Circle transform using OpenCV-Python.

OpenCV

OpenCV provides a built-in cv2.HoughCircles() function that finds circles in a grayscale image using the Hough transform. Below is the syntax

circles	= cv2.HoughCircles(image, method, dp, minDist[, param1[, param2[, minRadius[, maxRadius]]]]])

1 2	circles = cv2.HoughCircles(image, method, dp, minDist[, param1[, param2[, minRadius[, maxRadius]]]]])

Below are the parameters explained in detail

image: 8-bit, single-channel, grayscale input image
method: HOUGH_GRADIENT and HOUGH_GRADIENT_ALT
dp: The inverse ratio of accumulator resolution and image resolution
minDist: Minimum distance between the centers of the detected circles. All the candidates below this distance are neglected as explained above
param1: it is the higher threshold of the two passed to the Canny edge detector (the lower canny threshold is twice smaller)
param2: it is the accumulator threshold for the circle centers at the detection stage as discussed above.
minRadius: minimum radius that you expect. If unknown, put zero as default.
maxRadius: if -ve, only circle centers are returned without radius search. If unknown, put zero as default.

Image Smoothing will help in this, unless the image is already soft. Let’s take an image and see how to implement this.

Steps

Read an image and blur it to reduce the noise
Apply the Hough Circle Transform
Display the detected circles

import numpy as np
import cv2

# Read image
img = cv2.imread('D:/downloads/opencv_logo1.PNG')
# Smooth it
img = cv2.medianBlur(img,3)
img_copy = img.copy()
# Convert to greyscale
img_gray = cv2.cvtColor(img_copy,cv2.COLOR_BGR2GRAY)
# Apply Hough transform to greyscale image
circles = cv2.HoughCircles(img_gray,cv2.HOUGH_GRADIENT,1,20,
                     param1=60,param2=40,minRadius=0,maxRadius=0)
circles = np.uint16(np.around(circles))
# Draw the circles
for i in circles[0,:]:
    # draw the outer circle
    cv2.circle(img,(i[0],i[1]),i[2],(0,255,0),2)
    # draw the center of the circle
    cv2.circle(img,(i[0],i[1]),2,(0,0,255),3)
cv2.imshow('detected circles',img)
cv2.waitKey(0)
cv2.destroyAllWindows()

import numpy as np

import cv2

# Read image

img = cv2.imread('D:/downloads/opencv_logo1.PNG')

# Smooth it

img = cv2.medianBlur(img,3)

img_copy = img.copy()

# Convert to greyscale

img_gray = cv2.cvtColor(img_copy,cv2.COLOR_BGR2GRAY)

# Apply Hough transform to greyscale image

circles = cv2.HoughCircles(img_gray,cv2.HOUGH_GRADIENT,1,20,

param1=60,param2=40,minRadius=0,maxRadius=0)

circles = np.uint16(np.around(circles))

# Draw the circles

for i in circles[0,:]:

# draw the outer circle

cv2.circle(img,(i[0],i[1]),i[2],(0,255,0),2)

# draw the center of the circle

cv2.circle(img,(i[0],i[1]),2,(0,0,255),3)

cv2.imshow('detected circles',img)

cv2.waitKey(0)

cv2.destroyAllWindows()

Play with the parameters in order to understand them better. That’s all for this blog. In the next blog, we will discuss the Probabilistic Hough Transform that is an optimization of the Hough Transform. Hope you enjoy reading.

If you have any doubts/suggestions please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Shape detection is an important area in the field of image processing. In the previous blog, we discussed how we can perform simple shape detection using contours. Since edge detection was used as a pre-processing step, so that approach was more susceptible to noise and missing edge points. To overcome this, in this blog, we will discuss Hough Transform, a popular method for detecting simple shapes that give robust shape detection under noise and partial occlusion. So, in this blog, let’s take an example of line detection and see how can we use the Hough transform to detect lines in an image. This method of line detection is also known as Hough Line Transform. So, let’s get started.

Hough Line Transform

Before going into detail, let’s first refresh some high school maths concepts that will be useful for understanding this.

We know that a line corresponds to a point in the parameter space as shown below. Why? because a line has a fixed slope and intercept value.

So, how this will help? Clearly, by changing the space, we reduced the line (consisting of many points) to a single point thus reducing storage and further computation.

Similarly, a point corresponds to a line in the parameter space as shown below. Why? because there can be infinite lines that can pass through a point and for each line we have a point in the parameter space.

Now, let’s combine the above two. Suppose you are given 2 points so can you find out where the line joining these 2 points map in the parameter space. Obviously, this would be equivalent to the intersection point as shown below.

This is what the Hough transform does. For each edge point, we draw the lines in the parameter space and then find their point of intersection (if any). The intersection points will give us the parameters (slope and intercept) of the line.

Problem

But there is one big problem with this parameter space representation. As you might have guessed that we can’t represent the vertical lines as this would require infinite m.

Solution

We use the polar or normal form of a line

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

Here, r is the perpendicular distance from the origin to the line and Θ is the angle formed by this perpendicular line with the origin as shown below.

You might ask isn’t r unbounded as this can take value from 0 to ∞. But since images are of finite size, thus r can take value from 0 to diagonal length of the image. Both r and Θ are finite and thus the above problem is resolved.

Now, let’s see what the line and point corresponds to in the (r,Θ) space.

A line in the (x,y) space still corresponds to a point in the (r, Θ) space. But a point in the (x,y) space is now equivalent to a sinusoidal curve in the (r, Θ) space as shown below.

Thus now for each edge pixel, we draw the sinusoidal curves in the (r, Θ) space and then find their point of intersection (if any).

Implementation

To find the point of intersection, Hough transform uses a voting method. In this, first, the parameter space (r, Θ) is discretized into bins as shown below. We call this an accumulator. Then for each edge pixel, we calculate the r value corresponding to each Θ value. And corresponding to each (r, Θ) value obtained, we increase the count of that (r, Θ) accumulator cell. Then find the bins with the highest value. Below is the pseudo-code of the Hough line transform algorithm.

Algorithm

Initialize the accumulator (H) to all zeros
For each edge pixel (x,y) in the image
- For Θ = 0 to 180
  - Calculate r (r = x*cosΘ + y*sinΘ)
  - H(Θ,r) = H(Θ,r) +1
- endFor
endFor
Find the (Θ,r) value(s), where H(Θ,r) is above a suitable threshold value.

OpenCV

OpenCV provides a built-in function cv2.HoughLines(), that finds the lines in a binary image using the above algorithm. This takes as input the binary image, the size of the accumulator, the threshold value and outputs the array of (r, Θ) values. The syntax is given below.

lines = cv2.HoughLines(image, rho, theta, threshold)

# image: 8-bit, single-channel binary source image
# rho: Distance resolution of the accumulator in pixels.
# theta: Angle resolution of the accumulator in radians.
# threshold: Only those lines are returned that get enough votes

lines = cv2.HoughLines(image, rho, theta, threshold)

# image: 8-bit, single-channel binary source image

# rho: Distance resolution of the accumulator in pixels.

# theta: Angle resolution of the accumulator in radians.

# threshold: Only those lines are returned that get enough votes

Below is the code for this.

import cv2

# Read the image
img_orig = cv2.imread('D:/downloads/accumlator.JPG')
img = img_orig.copy()

# Convert to grayscale
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
# Find the edges using Canny detector
edges = cv2.Canny(gray,50,200)
# Apply the hough transform
lines = cv2.HoughLines(edges,1,np.pi/180,200)
# Draw the lines
for line in lines:
    rho,theta = line[0]
    a = np.cos(theta)
    b = np.sin(theta)
    x0 = a*rho
    y0 = b*rho
    x1 = int(x0 + 1000*(-b))
    y1 = int(y0 + 1000*(a))
    x2 = int(x0 - 1000*(-b))
    y2 = int(y0 - 1000*(a))
    cv2.line(img,(x1,y1),(x2,y2),(0,0,255),2)
cv2.imshow('a', img)
cv2.waitKey(0)

import cv2

# Read the image

img_orig = cv2.imread('D:/downloads/accumlator.JPG')

img = img_orig.copy()

# Convert to grayscale

gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

# Find the edges using Canny detector

edges = cv2.Canny(gray,50,200)

# Apply the hough transform

lines = cv2.HoughLines(edges,1,np.pi/180,200)

# Draw the lines

for line in lines:

rho,theta = line[0]

a = np.cos(theta)

b = np.sin(theta)

x0 = a*rho

y0 = b*rho

x1 = int(x0 + 1000*(-b))

y1 = int(y0 + 1000*(a))

x2 = int(x0 - 1000*(-b))

y2 = int(y0 - 1000*(a))

cv2.line(img,(x1,y1),(x2,y2),(0,0,255),2)

cv2.imshow('a', img)

cv2.waitKey(0)

Below is the result.

Limitations

Choosing a good accumulator size is difficult.
- Too coarse: different lines will fall to a single bin
- Too fine: votes will fall to the neighboring bins for points which are not exactly collinear
Time complexity increases exponentially wrt. parameters

That’s all for this blog. In the next blog, we will discuss how to detect some other shapes such as circle, ellipse, etc. Hope you enjoy reading.

If you have any doubts/suggestions please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

TheAILearner

Mastering Artificial Intelligence

Tag Archives: Hough transform opencv

Hough Circle Transform

Algorithm

Problem

OpenCV Hough Gradient Method

OpenCV

Steps

Hough Line Transform

Hough Line Transform

Problem

Solution

Implementation

Algorithm

OpenCV

Limitations