Morphological operations (erosion, dilation) in SciPy - Time & Space Complexity

Time Complexity: Morphological operations (erosion, dilation)

O(n²)

Understanding Time Complexity

We want to understand how the time needed to perform morphological operations changes as the image size grows.

How does the processing time increase when the input image gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.ndimage import binary_erosion, binary_dilation

image = np.random.randint(0, 2, (n, n), dtype=bool)
structure = np.ones((3, 3), dtype=bool)
eroded = binary_erosion(image, structure=structure)
dilated = binary_dilation(image, structure=structure)
    

This code applies erosion and dilation on a binary image using a 3x3 structuring element.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each pixel in the image is visited and compared with its neighbors defined by the structuring element.
• How many times: Once for each pixel in the image, so n × n times for an n by n image.

How Execution Grows With Input

As the image size grows, the number of pixels to process grows too.

Input Size (n)	Approx. Operations
10	100 (10×10)
100	10,000 (100×100)
1000	1,000,000 (1000×1000)

Pattern observation: The operations grow roughly with the square of the image dimension because each pixel is processed once.

Final Time Complexity

Time Complexity: O(n²)

This means the time to complete erosion or dilation grows proportionally to the total number of pixels in the image.

Common Mistake

[X] Wrong: "Morphological operations take constant time regardless of image size because they just look at neighbors."

[OK] Correct: Even though each pixel looks at neighbors, every pixel must be processed, so the total work grows with the number of pixels.

Interview Connect

Understanding how image size affects processing time helps you explain performance in real projects involving image analysis or computer vision.

Self-Check

"What if we used a larger structuring element, like 5x5 instead of 3x3? How would the time complexity change?"

Practice

1. What does the erosion operation do to a binary image in morphological processing?

easy

A. It inverts the colors of the image.

B. It enlarges the white regions by adding pixels to edges.

C. It shrinks the white regions by removing edge pixels.

D. It blurs the image to reduce noise.

Solution

1. Step 1: Understand erosion effect

   Erosion removes pixels on object boundaries, making white regions smaller.

2. Step 2: Compare with other operations

   Dilation adds pixels, inversion changes colors, blurring smooths image; none match erosion.

3. Final Answer:

   It shrinks the white regions by removing edge pixels. -> Option C

4. Quick Check:

   Erosion = Shrink white regions [OK]

Hint: Erosion shrinks shapes by cutting edges [OK]

Common Mistakes:

• Confusing erosion with dilation
• Thinking erosion adds pixels
• Mixing erosion with color inversion

2. Which of the following is the correct way to import the erosion function from scipy's ndimage module?

easy

A. from scipy.ndimage import erosion

B. from scipy.ndimage import binary_erosion

C. import scipy.ndimage.erosion

D. from scipy import erosion

Solution

1. Step 1: Identify correct function name

   The function for erosion on binary images is named binary_erosion in scipy.ndimage.

2. Step 2: Check import syntax

   Correct import is from scipy.ndimage import binary_erosion. Other options are invalid or incorrect names.

3. Final Answer:

   from scipy.ndimage import binary_erosion -> Option B

4. Quick Check:

   Correct import = binary_erosion [OK]

Hint: Use binary_erosion for erosion in scipy.ndimage [OK]

Common Mistakes:

• Using wrong function name 'erosion'
• Incorrect import syntax
• Trying to import from scipy root

3. Given the following code, what will be the output array after applying dilation?

import numpy as np
from scipy.ndimage import binary_dilation

image = np.array([[0, 0, 0, 0, 0],
                  [0, 1, 1, 0, 0],
                  [0, 1, 0, 0, 0],
                  [0, 0, 0, 0, 0]])

result = binary_dilation(image).astype(int)
print(result)

medium

A. [[0 0 0 0 0]
[0 0 1 0 0]
[0 1 0 0 0]
[0 0 0 0 0]]

B. [[0 0 0 0 0]
[0 1 1 0 0]
[0 1 0 0 0]
[0 0 0 0 0]]

C. [[1 1 1 0 0]
[1 1 1 1 0]
[1 1 1 1 0]
[0 1 1 0 0]]

D. [[0 1 1 0 0]
[1 1 1 1 0]
[1 1 1 0 0]
[0 1 0 0 0]]

Solution

1. Step 1: Understand binary_dilation effect

   Dilation adds pixels to the edges of white regions (1s), expanding them by one pixel in all directions.

2. Step 2: Apply dilation to given image

   Original white pixels at (1,1),(1,2),(2,1). After dilation, neighbors become 1, resulting in the array in [[0 1 1 0 0] [1 1 1 1 0] [1 1 1 0 0] [0 1 0 0 0]].

3. Final Answer:

   [[0 1 1 0 0] [1 1 1 1 0] [1 1 1 0 0] [0 1 0 0 0]] -> Option D

4. Quick Check:

   Dilation = expand edges [OK]

Hint: Dilation grows white pixels by one layer [OK]

Common Mistakes:

• Confusing dilation with erosion
• Not converting boolean to int for print
• Misreading array indices

4. The following code is intended to perform erosion on a binary image, but it raises an error. What is the problem?

import numpy as np
from scipy.ndimage import erosion

image = np.array([[1, 1, 0],
                  [1, 0, 0],
                  [0, 0, 1]])

result = erosion(image)
print(result)

medium

A. The function 'erosion' does not exist in scipy.ndimage; use 'binary_erosion' instead.

B. The input image must be float type, not int.

C. The image array shape is invalid for erosion.

D. The print statement syntax is incorrect.

Solution

1. Step 1: Check function availability

   Scipy.ndimage does not have a function named 'erosion'; the correct function is 'binary_erosion'.

2. Step 2: Correct the import and usage

   Replace 'from scipy.ndimage import erosion' with 'from scipy.ndimage import binary_erosion' and call 'binary_erosion(image)'.

3. Final Answer:

   The function 'erosion' does not exist in scipy.ndimage; use 'binary_erosion' instead. -> Option A

4. Quick Check:

   Use binary_erosion, not erosion [OK]

Hint: Use binary_erosion, not erosion function [OK]

Common Mistakes:

• Trying to import non-existent 'erosion'
• Ignoring error messages
• Assuming all morphological functions have simple names

5. You have a noisy binary image with small white dots scattered outside the main object. Which sequence of morphological operations using scipy.ndimage would best remove these small dots but keep the main shape mostly intact?

hard

A. Apply erosion followed by dilation (opening) to remove small objects.

B. Apply dilation followed by erosion (closing) to fill small holes.

C. Apply only dilation to enlarge all white areas.

D. Apply only erosion to shrink all white areas drastically.

Solution

1. Step 1: Understand noise removal goal

   Small white dots are noise; we want to remove them without changing main shape much.

2. Step 2: Choose correct morphological sequence

   Opening (erosion then dilation) removes small objects but keeps main shape. Closing fills holes, not remove dots.

3. Final Answer:

   Apply erosion followed by dilation (opening) to remove small objects. -> Option A

4. Quick Check:

   Opening = erosion + dilation removes noise [OK]

Hint: Use opening (erosion then dilation) to remove small noise [OK]

Common Mistakes:

• Using closing instead of opening for noise removal
• Applying only dilation or erosion alone
• Confusing noise removal with hole filling