OpenCV + Python Edge detection and Hough transform

728x90

Hello. This is codingwalks.

Accurately detecting the boundaries of objects is utilized in various applications and is one of the core processes of image understanding. Edge detection is a representative method of boundary detection technology, and the technique used to find geometric shapes through the detected boundaries is Hough transform. Edge detection is the process of finding sudden changes in pixel intensity in an image, that is, boundaries between objects and backgrounds or changes in internal structures. Various edge detection techniques such as Sobel, Laplacian, and Canny are used, and each method provides appropriate results depending on the characteristics of the image. The boundaries detected through edge detection become an important basis for subsequent analysis. Hough transform is a technique that finds specific geometric shapes such as straight lines or circles based on this edge information, and can robustly detect even partially disconnected straight lines or circular boundaries in an image. In this article, we will examine the process of detecting shapes such as lines and circles in an image by linking edge detection and Hough transform, and explain its principles and mathematical foundations.

1. Edge Detection

1.1. Simple Edge Detection Kernel

Edge detection is done through convolution using a specific kernel. For basic edge detection, horizontal and vertical kernels can be applied.

Horizontal Edge Detection Kernel: This kernel detects horizontal edges by emphasizing the intensity change (gradient) between adjacent rows.

\[ K_x = \begin{bmatrix}
-1 & -2 & -1 \\
0 & 0 & 0 \\
1 & 2 & 1
\end{bmatrix} \]

Vertical Edge Detection Kernel: This kernel is used to detect changes in the vertical direction.

\[ K_y = \begin{bmatrix}
-1 & 0 & 1 \\
-2 & 0 & 2 \\
-1 & 0 & 1
\end{bmatrix} \]

1.2. Sobel Operator

The Sobel operator approximates the differentiation of the image in the horizontal and vertical directions using two 3x3 filters. The Sobel operator also includes a smoothing step to reduce the sensitivity to noise in the image.

The Sobel operator's differential kernel:

\( G_x = \begin{bmatrix}
-1 & 0 & 1 \\
-2 & 0 & 2 \\
-1 & 0 & 1
\end{bmatrix} \) and \( G_y = \begin{bmatrix}
-1 & -2 & -1 \\
0 & 0 & 0 \\
1 & 2 & 1
\end{bmatrix} \)

The magnitude of the gradient can be computed as:

\[G = \sqrt{G_x^2 + G_y^2}\]

This represents the magnitude of the change, and the direction of the edge is as follows:

\[\theta = \text{atan2}(G_y, G_x)\]

1.3. Laplacian Operator

The Laplacian operator is used to detect edges by detecting abrupt changes in brightness within an image. The Laplacian operator is an operator that computes the second derivative (i.e., approximates the second derivative) to detect edges simultaneously in all directions of the image. The cv2.Laplacian() function in OpenCV performs this Laplacian operation to generate an edge image.

\[ \Delta I = \begin{bmatrix}
0 & 1 & 0 \\
1 & -4 & 1 \\
0 & 1 & 0
\end{bmatrix} \]

This operator detects abrupt changes in intensity in both horizontal and vertical directions simultaneously. Unlike the Sobel operator, the Laplacian operator does not provide any information about the direction of the edge.

1.4. Canny Edge Detection

Canny Edge Detection is one of the most widely used edge detection algorithms in image processing. OpenCV's cv2.Canny() function provides a simple way to use this algorithm, but implementing it yourself will help you understand the internal workings of the algorithm better.

Canny Edge Detection Process:

Noise Removal (Gaussian Blur): Apply a Gaussian filter to remove noise.
Gradient Computation: Calculate the gradient in the x and y directions using the Sobel operator, and find the magnitude ((G)) and direction \(\theta\) of the gradient.
Non-maximum Suppression (NMS): Compare the neighboring pixels in the direction where the gradient magnitude is the largest, and leave only the local maximum.
Double thresholding: Classify strong, weak, and non-edge edges using high and low thresholds
\[ \text{Edge} =
\begin{cases}
\text{Strong edge} & \text{if } G > T_{high} \\
\text{Weak edge} & \text{if } T_{low} < G \leq T_{high} \\
\text{Non-edge} & \text{if } G \leq T_{low}
\end{cases} \]
Edge tracking by hysteresis: Create a complete edge by connecting weak edges starting from a strong edge.

Example code using OpenCV edge detection:

import cv2
import numpy as np
import matplotlib.pyplot as plt

image = cv2.imread('resources/lena.bmp', cv2.IMREAD_GRAYSCALE)

# 1.1. Simple edge detection kernel
# Defining horizontal and vertical kernels
horizontal_kernel = np.array([[-1, -2, -1], [0, 0, 0], [1, 2, 1]])
vertical_kernel = np.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]])

# Apply convolution
horizontal_edges = cv2.filter2D(image, -1, horizontal_kernel)
vertical_edges = cv2.filter2D(image, -1, vertical_kernel)

# 1.2. Sobel operator
sobel_x = cv2.Sobel(image, cv2.CV_64F, 1, 0, ksize=3)
sobel_y = cv2.Sobel(image, cv2.CV_64F, 0, 1, ksize=3)
sobel_magnitude = np.sqrt(sobel_x**2 + sobel_y**2)

# 1.3. Laplacian operator
laplacian = cv2.Laplacian(image, cv2.CV_64F)

# 1.4. Canny edge detection
canny_edges = cv2.Canny(image, 100, 200)

titles = ['Original', 'Horizontal Edges', 'Vertical Edges', 
          'Sobel Operator', 'Laplacian Operator', 'Canny Edges']
images = [image, horizontal_edges, vertical_edges, sobel_magnitude, laplacian, canny_edges]

plt.figure(figsize=(10, 10))
for i in range(6):
    plt.subplot(2, 3, i+1), plt.imshow(images[i], cmap='gray')
    plt.title(titles[i])
    plt.xticks([]), plt.yticks([])

plt.show()

2. Hough Transformation

Hough Transformation is a technique for detecting geometric shapes such as straight lines and circles in an image. It basically shows strong performance in finding linear or circular patterns even in noisy environments, and is often used in computer vision for straight line detection or circle detection. The core concept of Hough Transform is to find patterns in the “feature space”.

To understand Hough Transform, we must first understand the equation of a straight line. The equation of a straight line can be expressed in two ways that we are familiar with.

2.1. Hough Line Detection

The most common way to express a straight line is the following equation.

\[y = mx + b\]

Here, m is the slope and b is the y-intercept. However, this equation is difficult to calculate because the slope m becomes infinite in the case of a vertical line. To solve this, the Hough transform uses polar coordinates to represent a line as follows:

\[\rho = x \cdot \cos\theta + y \cdot \sin\theta\]

Where:

\(\rho\) is the vertical distance from the origin to the line.
\(\theta\) is the angle between the line and the x-axis.

The Hough transform computes \(\rho\) for multiple values of \(\theta\) for each edge pixel in image space, and constructs a cumulative histogram that votes on them. The values (\(\rho\), \(\theta\)) that get high votes in the cumulative histogram are the points where the corresponding line intersects the image the most, and therefore are lines detected in the image.

The Hough line detection algorithm works as follows:

Edge detection: First, edges are extracted from the image using a Sobel or Canny edge detector. Cumulative space
voting: Compute (\(\rho\), \(\theta\)) values for each edge pixel and vote on the cumulative histogram.
Maximum detection: Convert the most voted (\(\rho\), \(\theta\)) values in the cumulative space into a line to detect the line.

Example code using cv2.HoughLines()

This function takes an image as input and detects lines in polar coordinates. The detected lines are returned as \(\rho\) and \(\theta\) values.

import cv2
import numpy as np

image = cv2.imread('resources/building.jpg')
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
edges = cv2.Canny(img, 50, 150)

# Line detection using Hough transform
lines = cv2.HoughLines(edges, 1, np.pi / 180, 270)

# Draw the detected straight line
results = cv2.cvtColor(edges, cv2.COLOR_GRAY2BGR)
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(results, (x1, y1), (x2, y2), (0, 0, 255), 2)

cv2.imshow('Hough Lines', results)
cv2.waitKey(0)
cv2.destroyAllWindows()

2.2. Probabilistic Hough Line Transform

The basic Hough transform requires a lot of computation because it is calculated for all edge pixels in the image. To improve this, probabilistic Hough line detection is introduced. This method can significantly reduce the computational amount because it randomly samples only a portion of the entire edge pixels to detect lines.

The probabilistic Hough line detection algorithm works as follows:

Edge Detection: Same as the basic Hough transform, edge detection is performed first.
Line Extraction: Line detection is performed for edge pixels randomly selected from the image.
Cumulative Space Analysis: Only lines that have received sufficient votes are extracted from the cumulative histogram.
Line Segmentation: The line is not detected as a whole, but is expressed by segmenting the line based on the start and end points.

Example code using cv2.HoughLinesP()

This function is similar to cv2.HoughLines(), but it detects lines more efficiently by using the probabilistic Hough transform. Here we directly return the start point (x1, y1) and end point (x2, y2) of the line.

import cv2
import numpy as np
import matplotlib.pyplot as plt

img = cv2.imread('resources/building.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
edges = cv2.Canny(gray, 50, 150)

# Probabilistic Hough Line Detection
linesP = cv2.HoughLinesP(edges, 1, np.pi / 180, 160, None, 50, 5)

# Draw a straight line
results = cv2.cvtColor(edges, cv2.COLOR_GRAY2BGR)
if linesP is not None:
    for line in linesP:
        x1, y1, x2, y2 = line[0]
        cv2.line(results, (x1, y1), (x2, y2), (0, 0, 255), 2)

cv2.imshow('Probabilistic Hough Lines', results)
cv2.waitKey(0)
cv2.destroyAllWindows()

2.3. Hough Circle Detection (Hough Circle Transform)

There is also a method to detect circles using the Hough transform. A circle is defined by three parameters:

(\(x_c\), \(y_c\)) : the center coordinate of the circle
\(r\) : the radius

This method generates a cumulative histogram of possible center coordinates and radii at each edge pixel in the image, and recognizes the coordinate and radius with the most votes as a circle.

The equation of a circle is as follows:

\[(x - x_c)^2 + (y - y_c)^2 = r^2\]

Hough circle detection uses this equation to estimate the center and radius for each edge pixel.

The Hough circle detection algorithm works as follows:

Edge detection: Perform edge detection on the image to detect circles.
Cumulative space calculation: Votes are made on possible center coordinates and radii for each edge pixel.
Circle Detection: Detects the most voted (\(x_c\), \(y_c\), \(r\)) values in the cumulative histogram as circles.

Example code using cv2.HoughCircles()

This function is used to detect circles in an image. It uses the Hough transform to compute the center and radius of the circle.

import cv2
import numpy as np

img = cv2.imread('resources/circle.jpg')

gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
blur = cv2.GaussianBlur(gray, (0,0), 1)

# Circle detection using Hough transform
circles = cv2.HoughCircles(blur, cv2.HOUGH_GRADIENT, 1, 100, None, 150, 40, 20, 80)

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 center of the circle
    cv2.circle(img, (i[0], i[1]), 2, (0, 0, 255), 3)

cv2.imshow('Hough Circles', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

3. Conclusion

Edge detection and Hough transform are very important techniques in computer vision, and are widely used to analyze the structural characteristics of images and recognize objects. Edge detection detects changes in pixel intensity in an image to find boundaries, and Hough transform detects geometric shapes such as lines or circles based on this boundary information. Hough transform can effectively detect various types of objects, from straight line detection to circle detection, and provides robust performance, especially in noisy environments.

These techniques are the basic steps of image processing and analysis, and play an important role in various fields such as more complex object recognition and tracking, 3D restoration, and computer vision-based automated systems. Appropriate use of edge detection and Hough transform can extract important information from images and build higher-level vision systems.

If you found this post useful, please like and subscribe below. ^^

[Codingwalks]에게 송금하기 - AQR

aq.gy

★ All contents are referenced from the link below. ★

OpenCV: OpenCV-Python Tutorials

Core Operations In this section you will learn basic operations on image like pixel editing, geometric transformations, code optimization, some mathematical tools etc.

docs.opencv.org