Binary Image Erosion

easyFREEMorphological OperationsComputer Vision 2

Implement a morphological operation to apply erosion to a given binary image using a structuring element. The goal is to produce a new binary image where each pixel is 1 only if all corresponding pixels in the image covered by the structuring element are also 1.

The concept of erosion is fundamental in morphological operations, which are used to manipulate and analyze the shape and structure of objects in images. Erosion is a process that shrinks or reduces the size of objects in an image by removing pixels from the object boundaries. This is achieved by applying a structuring element, a small binary image, to the original image. The structuring element is used to probe the image, and for each pixel, it checks if all the pixels covered by the structuring element are 1.

To perform erosion, the following steps are taken:

Center the structuring element at each pixel in the image.
Check if all the image pixels under the 1-entries of the structuring element are 1. Entries where the structuring element is 0 are ignored, and any position that falls outside the image counts as 0.
If all the pixels are 1, the corresponding pixel in the output image is set to 1; otherwise, it is set to 0.

f(x, y) = \min_{(s, t) \in S} g(x + s, y + t)

This technique is widely used in image processing and computer vision applications to remove noise and extract features from images.

Example

Input

image = [[0,0,0,0,0],[0,1,1,1,0],[0,1,1,1,0],[0,1,1,1,0],[0,0,0,0,0]]
se = [[0,1,0],[1,1,1],[0,1,0]]

Output

[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

Reasoning

image is a $5 \times 5$ image with a $3 \times 3$ square of 1s (rows 1–3, columns 1–3) on 0s. se is a $3 \times 3$ cross: centre plus the four direct neighbours are 1; its 0 corners play no part.
Centre the cross on a pixel: the output there is 1 only if the pixel and its four direct neighbours are all 1, i.e. $f(x,y) = \min$ of those five values.
Centre pixel $(2, 2)$ : itself, $(1,2)$ , $(3,2)$ , $(2,1)$ and $(2,3)$ are all 1, so the minimum is 1.
Edge pixel $(1, 2)$ : its upper neighbour $(0, 2)$ is 0, so the minimum is 0. Corner $(1, 1)$ fails twice, via $(0,1)$ and $(1,0)$ .
Result: [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]. Notice the 9-pixel square shrank to a single pixel: erosion peels away every pixel touching the background. Positions beyond the image border count as 0, so an all-1s image still loses its outer ring.

Constraints

image is a 2D binary list (0 or 1)
se (structuring element) is a 2D binary list with odd dimensions
Return eroded binary image (same size as input)

Learn this in

Image ProcessingCV Study Plan

More from Computer Vision 2

1D Bilateral Filterhard Image Sharpening with Unsharp Maskmedium Gaussian Blurmedium Gaussian Kernel Generationeasy 2D Image Convolutioneasy

Concept primer

Background Knowledge

Morphological operations are a set of image processing techniques used to analyze and manipulate the shape and structure of objects in an image. Erosion is one such operation, which shrinks or reduces the size of objects in an image by removing pixels from the object boundaries. The erosion operation is performed using a structuring element, also known as a kernel, which is a small matrix that slides over the entire image, comparing the corresponding pixels.

The key concept in erosion is the idea of a "hit" or a match between the structuring element and the image. A pixel in the output image is set to 1 only if all the positions where the structuring element has a 1, the corresponding image pixels are also 1. This means that the erosion operation is sensitive to the shape and size of the structuring element. The choice of structuring element determines the amount of erosion that occurs and the types of features that are preserved or removed.

In the context of binary images, erosion can be used to remove noise, separate touching objects, or extract the skeleton of an object. The mathematical representation of erosion can be expressed as: $E = I \ominus S$ where $E$ is the eroded image, $I$ is the input image, $S$ is the structuring element, and $\ominus$ denotes the erosion operation. The erosion operation can be defined as: $E(x, y) = \begin{cases} 1, & \text{if } I(x + i, y + j) = 1 \text{ for all } (i, j) \in S \\ 0, & \text{otherwise} \end{cases}$ where $(x, y)$ is the center of the structuring element.

Algorithm/Approach

The general approach to solving this problem involves iterating over each pixel in the input image and applying the erosion operation using the given structuring element. This can be achieved by using nested loops to slide the structuring element over the entire image, comparing the corresponding pixels, and setting the output pixel to 1 only if all positions where the structuring element has a 1, the corresponding image pixels are also 1.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an output image with the same dimensions as the input image, filled with zeros.
Iterate over each pixel in the input image, considering the center of the structuring element at each position.
For each pixel, slide the structuring element over the corresponding region of the input image, comparing the pixels.
Check if all positions where the structuring element has a 1, the corresponding image pixels are also 1. If so, set the output pixel to 1.
Handle out-of-bounds pixels by treating them as zeros (zero-padding).
Return the output image after applying the erosion operation to all pixels.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Incorrect handling of out-of-bounds pixels, which can lead to incorrect results.
Failure to center the structuring element correctly, which can affect the erosion operation.
Inefficient iteration over the image pixels, which can impact performance.

Time & Space Complexity

The expected time complexity of the solution is O(n * m * k * l), where n and m are the dimensions of the input image, and k and l are the dimensions of the structuring element. This is because we need to iterate over each pixel in the input image and compare it with the structuring element. The space complexity is O(n * m), which is the size of the output image.

solution.py

Python 3.13

Test results