Understanding and Implementing Canny Edge Detection in Native Python

Introduction

Edge detection plays a fundamental role in the field of computer vision, enabling machines to perceive the boundaries and structures within images, much like the way our eyes detect the outlines of objects. It serves as a crucial preprocessing step for a wide range of computer vision tasks, such as object recognition, image segmentation, and scene analysis.

Among the myriad edge detection techniques at our disposal, one name stands out for its effectiveness and widespread adoption — Canny edge detection. Named after its creator, John F. Canny, this method has become a cornerstone in image processing and computer vision. Its popularity stems from its ability to not only pinpoint edges with exceptional accuracy but also suppress noise and maintain edge continuity, making it an indispensable tool for extracting meaningful information from images.

In this article, we will delve into the inner workings of the Canny edge detection algorithm, explore its essential components, and provide a practical implementation in native Python, without relying on external libraries for the core functionality. By the end of this journey, you will not only have a comprehensive understanding of Canny edge detection but also the skills to apply it in your own computer vision projects while maintaining a Python-native approach.

The Canny Edge Detection Algorithm

Canny edge detection is a multi-stage process designed to identify edges in images accurately. Its effectiveness arises from the combination of several key steps, each with a specific purpose.

1. Gaussian Smoothing:

• Noise, in the form of unwanted high-frequency variations, can be a pervasive issue in digital images. When it comes to identifying edges, these variations can lead to false positives, making the detection less accurate and reliable. Edges, which are abrupt transitions in pixel intensity, are particularly susceptible to noise interference.
• Before identifying edges, it is essential to filter out the unwanted high-frequency noise that might exist in the image. To achieve this, the algorithm applies Gaussian smoothing. This step involves convolving the image with a Gaussian kernel, which blurs the image and creates a smoother version of it. The result is an image with less noise and subtle variations. Below is a native python code to apply the gaussian blurring.

def apply_gaussian_blur(image, kernel_size):
    def gaussian_kernel(size, sigma):
        kernel = np.fromfunction(
            lambda x, y: (1/ (2 * np.pi * sigma ** 2)) * 
                          np.exp(- ((x - (size-1)/2) ** 2 + (y - (size-1)/2) ** 2) / (2 * sigma ** 2)),
            (size, size)
        )
        return kernel / np.sum(kernel)

    # Ensure the kernel size is odd for symmetry
    if kernel_size % 2 == 0:
        kernel_size += 1

    # Generate the Gaussian kernel
    kernel = gaussian_kernel(kernel_size, sigma=1.0)

    # Get the dimensions of the image
    rows, cols = image.shape

    # Get the half-size of the kernel for padding
    k_half = kernel_size // 2

    # Create an output image with the same dimensions as the input
    output = np.zeros_like(image) 

    # Apply the Gaussian blur by convolving the image with the kernel
    for i in range(k_half, rows - k_half):
        for j in range(k_half, cols - k_half):
            output[i, j] = np.sum(image[i - k_half: i + k_half + 1, j - k_half: j + k_half + 1] * kernel)

    # get the image without the padding
    return output[k_half:rows-k_half, k_half:cols-k_half]

• The result :

before applying gaussian blurring

After applying gaussin blurring (kernel size = 5)

2. Gradient Calculation:

• Edges in images correspond to rapid changes in pixel intensity. The next step in the Canny algorithm is to compute the gradient of the image, which reveals these intensity changes. To achieve this, the algorithm applies Sobel operators in both horizontal and vertical directions. The magnitude and direction of these gradients provide critical information about the locations and orientations of edges. Below is a native python code to do compute gradient magnitues and orientations.

def compute_gradient_magnitude_and_orientation(image, sobel_kernel_size):

    if sobel_kernel_size == 3:
        # Define Sobel kernels (3x3)
        sobel_x = np.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]])
        sobel_y = np.array([[-1, -2, -1], [0, 0, 0], [1, 2, 1]])

    elif sobel_kernel_size == 5:
        sobel_x = np.array([[-1, -2, 0, 2, 1], [-2, -3, 0, 3, 2], [-3, -5, 0, 5, 3], [-2, -3, 0, 3, 2], [-1, -2, 0, 2, 1]])
        sobel_y = np.array([[-1, -2, -3, -2, -1], [-2, -3, -5, -3, -2], [0, 0, 0, 0, 0], [2, 3, 5, 3, 2], [1, 2, 3, 2, 1]])
    else:
        sys.exit("Sobel kernel size should be 3 or 5!")

    # Get the dimensions of the image
    rows, cols = image.shape

    # Initialize arrays for gradient magnitude and orientation
    gradient_x = np.zeros_like(image, dtype=np.float64)
    gradient_y = np.zeros_like(image, dtype=np.float64)

    # Compute gradient using Sobel operators
    half_size = sobel_kernel_size // 2
    for i in range(half_size, rows - half_size):
        for j in range(half_size, cols - half_size):
            window = image[i - half_size:i + half_size + 1, j - half_size:j + half_size + 1]
            gradient_x[i, j] = np.sum(window * sobel_x)
            gradient_y[i, j] = np.sum(window * sobel_y)

    # Compute gradient magnitude and orientation
    magnitude = np.sqrt(gradient_x ** 2 + gradient_y ** 2)
    save_image(magnitude, "3-gradient_magnitude.jpg")
    orientation = np.arctan2(gradient_y, gradient_x)

    return magnitude, orientation

• The gradient magnitude output:

Gradient magnitude output of the blurred image

3. Non-Maximum Suppression:

• While the gradient image highlights the regions of intensity change, it may also introduce some ambiguity in edge detection. Non-maximum suppression is employed to mitigate this issue. In this step, the algorithm analyzes the local gradient directions and retains only the most prominent edge pixels, discarding the rest. This results in a thinner edge map where only the strongest edge pixels are preserved.

def apply_non_max_suppression(magnitude, orientation):
    # Apply non-maximum suppression to the gradient magnitude
    # This will thin the edges by keeping only the local maxima
    suppressed_magnitude = np.copy(magnitude)
    rows, cols = magnitude.shape
    
    for i in range(1, rows - 1):
        for j in range(1, cols - 1):
            angle = orientation[i][j]
            q = [0, 0]
            if (-np.pi/8 <= angle < np.pi/8) or (7*np.pi/8 <= angle):
                q[0] = magnitude[i][j+1]
                q[1] = magnitude[i][j-1]
            elif (np.pi/8 <= angle < 3*np.pi/8):
                q[0] = magnitude[i+1][j+1]
                q[1] = magnitude[i-1][j-1]
            elif (3*np.pi/8 <= angle < 5*np.pi/8):
                q[0] = magnitude[i+1][j]
                q[1] = magnitude[i-1][j]
            else:
                q[0] = magnitude[i-1][j+1]
                q[1] = magnitude[i+1][j-1]
            
            if magnitude[i][j] < max(q[0], q[1]):
                suppressed_magnitude[i][j] = 0
    
    return suppressed_magnitude

• result:

Non-max suppressed output

4. Edge Tracking by Hysteresis:

• In the final stage, Canny edge detection handles the problem of faint and fragmented edges. Some edges may not be robust enough to stand on their own, yet they are still valuable information. To address this, the algorithm performs edge tracking by hysteresis. It establishes two thresholds, a high threshold and a low threshold. Pixels with gradient magnitudes above the high threshold are confidently marked as edges, while those below the low threshold are unequivocally discarded. However, pixels with magnitudes between the two thresholds are subject to a decision process that considers their connectivity to strong edge pixels. If a weak edge pixel is connected to strong edge pixels, it is also marked as an edge pixel, ensuring the continuity of edges.

def apply_edge_tracking_by_hysteresis(magnitude, low_threshold, high_threshold):
    # Apply edge tracking by hysteresis to detect strong and weak edges
    rows, cols = magnitude.shape
    edge_map = np.zeros((rows, cols), dtype=np.uint8)
    
    strong_edge_i, strong_edge_j = np.where(magnitude >= high_threshold)
    weak_edge_i, weak_edge_j = np.where((magnitude >= low_threshold) & (magnitude < high_threshold))
    
    # mark strong edges as white (255)
    edge_map[strong_edge_i, strong_edge_j] = 255

    # mark weak edges as white if they are connected to strong edges
    for i, j in zip(weak_edge_i, weak_edge_j):
        if (edge_map[i-1:i+2, j-1:j+2] == 255).any():
            edge_map[i, j] = 255
    
    return edge_map

• Output with low_threshold=30, high_threshold=100:

Final output after applying the edge tracking by hysteresis

Conclusion

In conclusion, this article has provided a comprehensive exploration of the Canny edge detection algorithm and its practical implementation in native Python. We’ve delved into each crucial component, from Gaussian smoothing to edge tracking by hysteresis, highlighting the importance of parameter selection. The Canny algorithm’s effectiveness in detecting edges with precision, while mitigating noise, has been underscored throughout. Its applications in computer vision and image processing are diverse, encompassing object recognition, scene analysis, and image segmentation.

Thank you for taking the time to read this article. I hope you’ve gained valuable insights into the world of edge detection and are now equipped to apply the Canny edge detection technique in your own Python projects.

• The full version of the code can be accessible in this GitHub repo: pasan-SK/Canny-edge-detection-implementation (github.com)