Connecting Dots: Exploring the Hough Transform for Image Analysis
In the realm of Artificial Intelligence, the field of computer vision has gained exponential significance in recent times. From autonomous vehicles navigating through busy streets to medical imaging diagnostics aiding in early disease detection, the ability of machines to interpret and understand visual information has opened up a world of possibilities.
At the heart of this fascinating domain lies the Hough Transform, an ingenious algorithm that has revolutionized image analysis. In this blog series, ‘Connecting Dots,’ we deep dive into the depths of the Hough Transform algorithm, unraveling its inner workings and exploring its vast applications in the realm of image analysis. So, let’s dive in and witness the magic of connecting dots, where patterns, shapes, and hidden relationships come to life before our very eyes.
In this blog, we will understand the use of hough transform in detecting straight lines and implement the same in Python.
★★ — Surprise — ★★
An interesting use case of hough transform is waiting for you at the end of this blog.
Introduction
Indeed, implementing the hough transform using Python is very exciting but understanding the intuition and concept behind the hough transform is no less.
So, before jumping to the implementation of hough transform in Python, let’s understand what is hough transform and the mathematical intuition behind it.
What is Hough Transform?
First introduced by Paul Hough in the early 1960s, the Hough Transform is a powerful image-processing technique used to detect and extract geometric shapes and patterns within images. The primary goal of the Hough Transform is to identify specific shapes, such as lines, circles, or ellipses, by converting them from their Cartesian representation (x, y coordinates) into a parameter space.
This transformation allows the algorithm to efficiently locate these shapes, even in the presence of noise and partial occlusions i.e. if the edges in the image are broken or separated. The Hough Transform has proven to be an invaluable tool in a wide range of applications, including object recognition, lane detection in autonomous vehicles, and medical image analysis, making it a cornerstone in the field of computer vision.
Mathematical Understanding
With no further ado, let’s understand the intuition behind hough transform.
Before diving deep into the intuition, it becomes very important to understand what we all might know, the cartesian space and the parametric space, and how lines are defined in both of these spaces.
Lines in Cartesian Space/Image Space
As you might recollect, any line in a cartesian space can be defined by the equation y = mx + c, where
m = slope of the line
c = the y intercept, where the line cuts the y-axis, and
(y,x) = any coordinate in the cartesian plane that the line passes through.
This is what we call cartesian space/image space.
Now, let’s understand how this line is transformed from a cartesian space/ image space to a parametric space or (m,c) space.
Lines in Parametric Space
(m,c) space
Suppose, we have a line y=mx+c which passes through the point x_i and y_i, then the equation of the line can be written as the one on the L.H.S. below
Now, we can rewrite the same equation as the one on the R.H.S. Since, x_i and y_i are known, the equation on the R.H.S. gives us the equation of the line in the (m,c) space.
So, now the point (x_i,y_i) in the image space can be transformed and represented in the (m,c) parameter space. This can be represented as below;
As we can see in the above image, each point in the cartesian space can be represented by a line in the mc space. Also, points along each line in mc space correspond to lines that pass through that point in the cartesian space.
Note: The point where lines intersect in the mc space (denoted by (m,c) in the above image) corresponds to the line that passes through each point in the cartesian space.
One interesting thing is that, a point in cartesian space maps to a line in mc space, and a line in cartesian space maps to a point in the mc space and vice versa.
Note: For vertical and horizontal lines, m i.e. slope of a line can range from -∞ to +∞ respectively
(𝜌, 𝜃) space
As we move further, there is one more parametric representation of line in the (𝜌, 𝜃) space also called the polar coordinate system. Let’s deep dive to understand this.
Let’s now represent the line with another equation using 𝜌 and 𝜃 as the parameters in the polar coordinate system. The new equation of the line becomes x*sin(𝜃) — y*cos(𝜃) + 𝜌 = 0, where
(x,y) = coordinates of a point that lies on the line
𝜌 = distance of the line from the origin
𝜃 = orientation of the line with the x-axis
Unlike the mc space, a point in the polar coordinate system corresponds to a sinusoid in the (𝜌,𝜃) space. This can be shown below.
Interesting right? Let’s do a small experiment and try implementing it in Python.
Let’s draw some points in an image and see what each point maps to in the hough space i.e. (𝜌,𝜃) space.
fig, axes = plt.subplots(1,2, figsize=(10, 5))
#create an image of size (150,150)
image = np.zeros((150,150))
#create white dots by setting the pixel values as 255
image[75, 75] = 255
image[25, 25] = 255
image[50, 50] = 255
image[100, 100] = 255
image[125, 125] = 255
#calculate the accumulator and the theta and rho values
accumulator, thetas, rhos = hough_line(image)
#plot the original image
axes[0].imshow(image)
axes[0].set_title('Original Image')
axes[0].axis('off')
#plot the hough space accumulator
axes[1].imshow(accumulator, cmap='hot')
axes[1].set_title('Hough Space')
axes[1].axis('off')
As we can clearly see in the above image, each point in the polar coordinate system corresponds to a sinusoid in the hough space or the (𝜌,𝜃) space. Also, the intersection point maps to the line that passes through all the points in the polar coordinate system.
Note: Hough transform, by default, uses the polar coordinate system to detect lines in an image due to the infinite range of slope of a line in the cartesian system leading to high computation usage.
Also, Hough space is also called the accumulator and the intersecting points map to the line in the polar coordinate system.
Working of Hough Transform Algorithm
Once we have understood how we map the intersection points to lines in the image space or the polar coordinate system, it becomes easy to understand the working of the Hough transform algorithm.
- Edge Detection: Perform edge detection on the input image using an edge detection algorithm like the Canny edge detector. The goal is to obtain a binary image where the edges are represented by white pixels and the background is black.
- Parameter Space Initialisation: Create an accumulator space (parameter space) to store the votes for potential lines. The parameter space typically consists of two axes representing the parameters of the lines (e.g., Rho, 𝜌 and Theta, 𝜃).
- Voting: For each edge point in the binary image, calculate all possible lines (defined by the parameters 𝜌 and 𝜃) that could pass through that point. Increment the corresponding cells in the accumulator space to vote for these lines.
- Thresholding: After the voting process, the accumulator space will have peaks that correspond to the most likely lines. Apply a threshold to the accumulator space to select the most prominent lines. The threshold helps eliminate noise and less significant lines.
- Line Extraction: Identify the peaks in the accumulator space that exceed the threshold. Each peak represents a potential line in the image.
- Convert Parameters to Image Space: Convert the parameters of the detected lines from the accumulator space back to the image space to obtain the actual lines in the image.
- Draw Detected Lines: Draw the detected lines on the original image using the parameters obtained in the previous step.
below is the pseudo code to understand this better,
Types of Hough Transform
Now, since we have a decent idea of what hough transform is and how it works, let’s try to implement different types of hough line transform in Python.
Standard Hough Line Transform
Thanks to the skimage library in Python, only a few lines of code can help detect straight lines in an image.
import matplotlib.pyplot as plt
import numpy as np
from skimage.io import imread
from skimage.feature import canny
from skimage.transform import hough_line, hough_line_peaks
def plot_image_with_lines(image, lines):
fig, axes = plt.subplots(1, 2, figsize=(12, 6))
# Plot the original image
axes[0].imshow(image, cmap='gray')
axes[0].set_title('Original Image')
axes[0].axis('off')
# Plot the image with detected lines
axes[1].imshow(image, cmap='gray')
for _, angle, dist in zip(*lines):
y0 = (dist - 0 * np.cos(angle)) / np.sin(angle)
y1 = (dist - image.shape[1] * np.cos(angle)) / np.sin(angle)
axes[1].plot((0, image.shape[1]), (y0, y1), 'r')
axes[1].set_xlim((0, image.shape[1]))
axes[1].set_ylim((image.shape[0], 0))
axes[1].set_title('Image with Detected Lines')
axes[1].axis('off')
plt.show()
# Load the image
image_path = 'data/images/sudoku.jpeg' # Replace with the actual path to your image
image = imread(image_path, as_gray=True)
# Apply edge detection (Canny)
edges = canny(image, sigma=2, low_threshold=0.1, high_threshold=0.3)
# Apply Standard Hough Transform
h, theta, d = hough_line(edges)
# Find the most prominent lines
lines = hough_line_peaks(h, theta, d)
# Plot the original image and the image with detected lines
plot_image_with_lines(image, lines)
As you can see in the output, the lines detected by the standard hough transform range from one end of the image to the other. Also, it sometimes captures the noise while detecting the straight lines in an image.
Probabilistic Hough Line Transform
Since the standard Hough transform uses all the points in an image to detect straight lines, it became computationally heavy. The probabilistic Hough Line Transform is an improvement over the standard method. Instead of considering all points in the image, it randomly selects a subset of points and then applies the Hough Transform only to those points. By using random sampling, the algorithm focuses only on the points belonging to the longer, more prominent lines in the image, effectively reducing the computational cost and eliminating the need to consider all points. This approach is especially useful for detecting long and continuous lines, as it avoids detecting many small and noisy segments.
import matplotlib.pyplot as plt
import numpy as np
from skimage.io import imread
from skimage.feature import canny
from skimage.transform import probabilistic_hough_line
def plot_image_with_lines(image, lines):
fig, axes = plt.subplots(1, 2, figsize=(12, 6))
# Plot the original image
axes[0].imshow(image, cmap='gray')
axes[0].set_title('Original Image')
axes[0].axis('off')
# Plot the image with detected lines
axes[1].imshow(image, cmap='gray')
for line in lines:
p0, p1 = line
axes[1].plot((p0[0], p1[0]), (p0[1], p1[1]), 'g')
axes[1].set_title('Image with Detected Lines')
axes[1].axis('off')
plt.show()
# Load the image
image_path = 'data/images/sudoku.jpeg' # Replace with the actual path to your image
image = imread(image_path, as_gray=True)
# Apply edge detection (Canny)
edges = canny(image, sigma=2, low_threshold=0.1, high_threshold=0.3)
# Apply Probabilistic Hough Transform
min_line_length = 75
max_line_gap = 5
lines = probabilistic_hough_line(edges, threshold=10, line_length=min_line_length, line_gap=max_line_gap)
# Plot the original image and the image with detected lines
plot_image_with_lines(image, lines)
As we can clearly see, the probabilistic Hough transform detects clean and clear straight lines compared to the standard Hough transform.
This brings us to the end of this blog…. but wait…..!!! I guess we missed something.
The surprise right?
So, last but not least, let’s discuss one interesting use case of the Hough transform technique. Surprisingly, the hough transform works perfectly with text documents. One prominent use case is the alignment correction of the documents. This can be easily achieved by applying the Hough transform on the desired documents.
Results of the same can be seen in the image below:
This brings us to the end of this blog. I have tried to be as detailed as possible to make this blog more understandable to you. Still, if you feel any need to visit the code, feel free to click on the below GIT repo link.
Repo: https://github.com/mayank1903/hough-transform
Also, you can read more of my interesting articles/blogs. Some of the links are added below;
- Neural Machine Translation from scratch with Attention — https://medium.com/farmart-blog/mastering-languages-unveiling-the-power-of-neural-machine-translation-with-attention-981fb88d3a78
- Anomaly detection in Images — Using feature descriptors: https://medium.com/farmart-blog/anomaly-detection-in-images-using-feature-descriptors-c7124669bdfb
- Profiling — Key to Python code Optimisation: https://medium.com/farmart-blog/profiling-key-to-python-code-optimisation-ff635679d185
I will be back with more such interesting blogs and to help the community at large, until then,
Happy Reading ;)
