Skip to content
Advanced Machine Learning

1.3 Edge Detectors

1. Prewitt and Sobel Kernels

Edge detection is a fundamental operation in image processing that identifies significant intensity changes in an image, which typically correspond to object boundaries. Two popular methods for edge detection are the Prewitt and Sobel operators, which are both based on convolution with specific kernels designed to highlight edges in different directions.

1.1 Prewitt Operator

The Prewitt operator is a simpler method for detecting edges. It uses two 3x3 convolution kernels to approximate the first derivative of the image intensity in the horizontal and vertical directions.

  • Prewitt Kernel for Horizontal Edges ():

  • Prewitt Kernel for Vertical Edges ():

1.2 Sobel Operator

The Sobel operator is similar to the Prewitt operator but includes a smoothing effect by incorporating a weight of 2 in the center row/column. This makes it more robust to noise and gives it a better edge response.

  • Sobel Kernel for Horizontal Edges ():

  • Sobel Kernel for Vertical Edges ():

1.3 Edge Detection Process

  1. Apply Convolution:

    • Convolve the image with to detect horizontal edges.
    • Convolve the image with to detect vertical edges.

  2. Compute Gradient Magnitude:

    • After obtaining and , the gradient magnitude at each pixel is calculated as:
    • Alternatively, a faster but less precise approximation can be used:
    • The magnitude represents the strength of the edge.

  3. Thresholding (Optional):

    • To highlight significant edges, a threshold can be applied to the gradient magnitude. Pixels with above a certain threshold are considered part of an edge.

1.4 Usage

Here’s how you can implement edge detection using both the Prewitt and Sobel operators in Python:

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


# Load the image in grayscale
img = cv2.imread('path_to_your_image.jpg', cv2.IMREAD_GRAYSCALE)


# Define Prewitt kernels
prewitt_kernel_x = np.array([[ -1, 0, 1],
                             [ -1, 0, 1],
                             [ -1, 0, 1]])
prewitt_kernel_y = np.array([[ -1, -1, -1],
                             [  0,  0,  0],
                             [  1,  1,  1]])


# Apply Prewitt operator
prewitt_x = cv2.filter2D(img, -1, prewitt_kernel_x)
prewitt_y = cv2.filter2D(img, -1, prewitt_kernel_y)
prewitt = cv2.magnitude(prewitt_x, prewitt_y)


# Apply Sobel operator using OpenCV built-in functions
sobel_x = cv2.Sobel(img, cv2.CV_64F, 1, 0, ksize=3)
sobel_y = cv2.Sobel(img, cv2.CV_64F, 0, 1, ksize=3)
sobel = cv2.magnitude(sobel_x, sobel_y)


# Display the results
plt.figure(figsize=(12, 6))
plt.subplot(1, 3, 1), plt.imshow(img, cmap='gray'), plt.title('Original Image')
plt.subplot(1, 3, 2), plt.imshow(prewitt, cmap='gray'), plt.title('Prewitt Edge Detection')
plt.subplot(1, 3, 3), plt.imshow(sobel, cmap='gray'), plt.title('Sobel Edge Detection')
plt.show()

1.5 Key Points

  • Prewitt Operator:

    • Simpler and computationally less expensive.
    • Less robust to noise compared to the Sobel operator.

  • Sobel Operator:

    • Adds smoothing, making it more effective at detecting edges in noisy images.
    • Widely used due to its balance between simplicity and performance.

{:.block-tip}

IMPORTANT

Both Prewitt and Sobel operators are fundamental tools for detecting edges in an image. The choice between them often depends on the specific requirements of the task, with Sobel being preferred in most practical applications due to its enhanced noise resistance and edge-detection capability.

2. Canny Edge Detection

Canny Edge Detection is a popular and widely used algorithm for detecting edges in an image. Developed by John F. Canny in 1986, the algorithm is designed to be an optimal edge detector, providing good detection, accurate localization, and minimal response to noise. The Canny edge detection algorithm is more complex than simpler edge detectors like Prewitt and Sobel, but it produces more accurate and reliable results.

2.1 Steps in the Canny Edge Detection Algorithm:

The Canny Edge Detection algorithm consists of the following steps:

1. Noise Reduction:

  • The first step is to reduce noise in the image, as noise can cause false edge detection. This is typically done using a Gaussian filter, which smooths the image by averaging pixel values with their neighbors.
  • The Gaussian kernel is applied to the image using convolution:
  • The parameter controls the amount of smoothing.

2. Gradient Calculation:

  • The algorithm computes the intensity gradient of the smoothed image using a method such as the Sobel operator. This produces two gradient images, and , representing the gradient in the and directions, respectively.
  • The gradient magnitude and direction are then calculated:

3. Non-Maximum Suppression:

  • Non-maximum suppression is applied to thin out the edges. It suppresses any pixel that is not considered to be part of an edge, leaving only the local maxima in the gradient direction.
  • For each pixel, the algorithm checks whether it is a local maximum by comparing it with its neighbors in the gradient direction. If it is not the maximum, it is set to zero.

4. Double Thresholding:

  • After non-maximum suppression, the algorithm applies a double threshold to classify pixels as strong, weak, or non-relevant edges:
    • Strong edges: Pixels with a gradient magnitude greater than the high threshold.
    • Weak edges: Pixels with a gradient magnitude between the low and high thresholds.
    • Non-relevant: Pixels with a gradient magnitude below the low threshold are suppressed.
  • This step helps to distinguish between true edges and noise.

5. Edge Tracking by Hysteresis:

  • In the final step, weak edges are either included in the final edge map or discarded based on their connectivity to strong edges.
  • A weak edge pixel is retained if it is connected to a strong edge pixel; otherwise, it is suppressed. This helps to ensure that only valid edges are preserved.

2.2 Usage

import cv2
import matplotlib.pyplot as plt


# Load the image in grayscale
img = cv2.imread('path_to_your_image.jpg', cv2.IMREAD_GRAYSCALE)


# Apply Canny edge detection
edges = cv2.Canny(img, threshold1=100, threshold2=200)


# Display the results
plt.figure(figsize=(8, 6))
plt.subplot(1, 2, 1), plt.imshow(img, cmap='gray'), plt.title('Original Image')
plt.subplot(1, 2, 2), plt.imshow(edges, cmap='gray'), plt.title('Canny Edge Detection')
plt.show()
  • threshold1 and threshold2: These are the low and high thresholds used in the double thresholding step. Edges with gradient values above threshold2 are considered strong edges, while those between threshold1 and threshold2 are considered weak edges.
  • The choice of these thresholds significantly affects the output; a lower threshold results in more detected edges, while a higher threshold reduces the number of detected edges.

2.3 Keypoints

  • Canny Edge Detection: A multi-step process that provides a more accurate and reliable method for detecting edges in images.
  • Steps: Includes noise reduction, gradient calculation, non-maximum suppression, double thresholding, and edge tracking by hysteresis.
  • Applications: Widely used in various computer vision tasks, such as object detection, image segmentation, and feature extraction.
  • Canny Edge Detection is known for its robustness and is commonly used in real-world applications due to its ability to detect edges even in noisy images while minimizing false detections.

3 Hough Transform Line Detector

The Hough Transform is a powerful technique used in computer vision and image processing to detect lines, circles, or other parametric shapes in an image. The method is particularly robust for detecting features in noisy images or where the shapes are only partially visible.

3.1 Concept of Hough Transform for Line Detection:

The basic idea behind the Hough Transform for line detection is to transform the points in the image space into a parameter space, where a line can be represented by a point. The transform accumulates evidence for all possible lines that could pass through each point in the image.

{% assign url_arr = “https://www.youtube.com/embed/XRBc_xkZREg” | append: "" | split: '' %} {% include custom/video.html id=“hough_transform” urls=url_arr %}

1. Equation of a Line

In the image space (Cartesian coordinates), a line can be represented as:

where is the slope and is the y-intercept.

However, this representation is not ideal for the Hough Transform because vertical lines would require infinite slope. Instead, the Hough Transform uses the polar representation of a line:

where:

  • is the perpendicular distance from the origin to the line.
  • is the angle of the perpendicular from the origin to the line.

2. Hough Space (Accumulator Array)

In the Hough Transform, each point in the image corresponds to a sinusoidal curve in the parameter space. Every point on this curve represents a potential line passing through .

  • Voting in Hough Space: Each point in the image votes for all the possible lines () that could pass through it. The votes are accumulated in an array known as the accumulator.
  • The dimension of the accumulator array corresponds to the range of possible values of and .

3. Detecting Lines

After all points in the image have voted, peaks in the accumulator array indicate the presence of lines. These peaks correspond to the and values of the lines in the image.

3.2 Usage

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


# Load the image in grayscale
img = cv2.imread('path_to_your_image.jpg', cv2.IMREAD_GRAYSCALE)


# Apply Canny Edge Detection
edges = cv2.Canny(img, 50, 150, apertureSize=3)


# Perform Hough Line Transform
lines = cv2.HoughLines(edges, 1, np.pi/180, 200)


# Draw the lines on the image
output_img = 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(output_img, (x1, y1), (x2, y2), (0, 0, 255), 2)


# Display the results
plt.figure(figsize=(8, 6))
plt.subplot(1, 2, 1), plt.imshow(img, cmap='gray'), plt.title('Original Image')
plt.subplot(1, 2, 2), plt.imshow(output_img), plt.title('Hough Line Detection')
plt.show()
  • cv2.HoughLines(): This function performs the Hough Line Transform. The parameters are:
    • edges: The output from the Canny edge detector.
    • 1: The resolution of the parameter in pixels.
    • np.pi/180: The resolution of the parameter in radians.
    • 200: The threshold parameter. Only lines with votes greater than this value are considered.
  • Drawing Lines: The detected lines are drawn on the image using the calculated and values.

3.3 Variations of the Hough Transform:

  1. Standard Hough Transform:

    • Works well for detecting lines but can be computationally expensive due to the size of the accumulator array.

  2. Probabilistic Hough Transform:

    • A more efficient variant that randomly samples points to reduce computational load.
    • Implemented in OpenCV as cv2.HoughLinesP(). It returns the start and end points of the detected lines, making it faster and more suitable for real-time applications.

Example of Probabilistic Hough Transform:

# Perform Probabilistic Hough Line Transform
lines = cv2.HoughLinesP(edges, 1, np.pi/180, threshold=100, minLineLength=50, maxLineGap=10)


# Draw the lines on the image
output_img = cv2.cvtColor(edges, cv2.COLOR_GRAY2BGR)
for line in lines:
    x1, y1, x2, y2 = line[0]
    cv2.line(output_img, (x1, y1), (x2, y2), (0, 255, 0), 2)


# Display the results
plt.figure(figsize=(8, 6))
plt.imshow(output_img)
plt.title('Probabilistic Hough Line Detection')
plt.show()
  • cv2.HoughLinesP(): The probabilistic variant, which returns the endpoints of line segments.
  • minLineLength: The minimum length of a line segment to be detected.
  • maxLineGap: The maximum allowed gap between points on the same line to link them together.

3.4 Keypoints

  • Hough Transform: A technique for detecting lines in an image by transforming points in the image space to the parameter space and finding peaks in the accumulator array.
  • Standard Hough Transform: Detects all lines in an image but is computationally intensive.
  • Probabilistic Hough Transform: A more efficient variant that detects line segments and is faster.
  • Applications: Widely used in applications like lane detection in autonomous vehicles, detecting lines in documents, and more.
  • The Hough Transform is robust and versatile, making it a fundamental tool in many computer vision and image processing tasks.