Hough Transform
A comprehensive guide to edge detection with Hough transform with code
Hough transform is a feature extraction method used in image analysis. Hough transform can be used to isolate features of any regular curve like lines, circles, ellipses, etc. Hough transform in its simplest from can be used to detect straight lines in an image. A generalized Hough transform can be used in applications where simple analytic description of features is not possible. Due to the computational complexity of the algorithm, people generally refrain from using it. Moreover learning based methods can extract complex features from the image or a video that better suit the problem we are trying to solve.
Algorithm
A straight line is the simplest boundary we can recognize in an image. Multiple straight lines can form a much complex boundary.
We transform the image space into hough space. By doing this we convert a line in image space to a point on hough space.
The equation of the line in the image space is of the form y = mx + c where m is the slope and c is the y-intercept of the line. This line will be transformed to a point of the form (m, c) in the hough space. But in this representation m goes to infinity for vertical lines. So let us use the polar coordinates instead.
The line is represented by the length of that segment ρ , and the angle θ it makes with the x-axis. This line will be transformed to a point of the form (ρ,θ) in the hough space.
The Hough transform constructs a histogram array representing the parameter space (i.e., an M x N matrix, for M different values of the radius ρ and N different values of angle θ). For each parameter combination,ρ and θ we then find the number of non-zero pixels in the input image that would fall close to the corresponding line, and increment the array at position (ρ,θ) appropriately.
Intuition for line detection
The intersection of multiple lines in image space represent corresponding multiple points in hough space.
Similarly the reverse i.e lines intersecting at a point (m, c) in hough space can be transformed to a line y = mx + c in image space.
If we have a line made up of many segments or points close to the same line equation in the image space, that turns into many intersecting lines in hough space.
So, consider a line in the image space which is an edge detected and has small discontinuities. To find the continous line in an image we can transform this dicontinous line in image space to hough space and look for intersection points in hough space. This intersection point in hough space will represent the continous line in image space.
Code
import numpy as np
import matplotlib.pyplot as plt
import cv2%matplotlib inline# Read in the image
image = cv2.imread('images/phone.jpg')# Change color to RGB (from BGR)
image = cv2.cvtColor(image, cv2.COLOR_BGR2RGB)plt.imshow(image)
Performing Edge detection
# Convert image to grayscale
gray = cv2.cvtColor(image, cv2.COLOR_RGB2GRAY)# Define our parameters for Canny
low_threshold = 50
high_threshold = 100
edges = cv2.Canny(gray, low_threshold, high_threshold)plt.imshow(edges, cmap='gray')
Find lines using Hough transform
# Define the Hough transform parameters
# Make a blank the same size as our image to draw on
rho = 1
theta = np.pi/180
threshold = 60
min_line_length = 50
max_line_gap = 5line_image = np.copy(image) #creating an image copy to draw lines on# Run Hough on the edge-detected image
lines = cv2.HoughLinesP(edges, rho, theta, threshold, np.array([]),
min_line_length, max_line_gap)# Iterate over the output "lines" and draw lines on the image copy
for line in lines:
for x1,y1,x2,y2 in line:
cv2.line(line_image,(x1,y1),(x2,y2),(255,0,0),5)
plt.imshow(line_image)
