Image filtering (gaussian_filter) in SciPy - Time & Space Complexity

Time Complexity: Image filtering (gaussian_filter)

O(n^2)

Understanding Time Complexity

We want to understand how the time to apply a Gaussian filter changes as the image size grows.

How does the filtering cost grow when the image gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.ndimage import gaussian_filter

image = np.random.rand(512, 512)
filtered_image = gaussian_filter(image, sigma=1)
    

This code applies a Gaussian blur to a 2D image array using scipy's gaussian_filter function.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Applying the Gaussian kernel to each pixel by combining neighboring pixels.
• How many times: Once for every pixel in the image, involving a small fixed neighborhood around it.

How Execution Grows With Input

The time grows roughly in proportion to the number of pixels in the image.

Input Size (n x n)	Approx. Operations
10 x 10	About 100 times a small fixed cost
100 x 100	About 10,000 times a small fixed cost
1000 x 1000	About 1,000,000 times a small fixed cost

Pattern observation: Doubling the image width and height roughly quadruples the work because the total pixels increase by the square.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to filter grows proportionally to the total number of pixels in the image.

Common Mistake

[X] Wrong: "The time depends on the size of the Gaussian kernel only, not the image size."

[OK] Correct: The kernel size is fixed and small, but the filter must be applied to every pixel, so the image size dominates the time.

Interview Connect

Understanding how image size affects filtering time helps you reason about performance in real projects and shows you can analyze common data science operations.

Self-Check

"What if we applied gaussian_filter to a 3D image (like a color image)? How would the time complexity change?"

Practice

1. What is the main purpose of using gaussian_filter in image processing?

easy

A. To detect edges in the image

B. To smooth the image by reducing noise

C. To convert the image to grayscale

D. To increase the image resolution

Solution

1. Step 1: Understand the function's role

   gaussian_filter applies a blur effect that smooths the image by averaging nearby pixels weighted by a Gaussian curve.

2. Step 2: Identify the effect on image quality

   This smoothing reduces noise and small details, making the image less sharp but cleaner.

3. Final Answer:

   To smooth the image by reducing noise -> Option B

4. Quick Check:

   Gaussian blur = noise reduction [OK]

Hint: Gaussian filter smooths images by blurring noise away [OK]

Common Mistakes:

• Thinking it increases resolution
• Confusing it with edge detection
• Assuming it changes color format

2. Which of the following is the correct way to import and apply a Gaussian filter with sigma=2 to a 2D numpy array named image?

easy

A. from scipy.ndimage import gaussian_filter
filtered = gaussian_filter(image, sigma=2)

B. import scipy
filtered = scipy.gaussian_filter(image, 2)

C. from scipy import gaussian_filter
filtered = gaussian_filter(image, 2)

D. import gaussian_filter from scipy.ndimage
filtered = gaussian_filter(image, sigma=2)

Solution

1. Step 1: Check the correct import statement

   The Gaussian filter is in scipy.ndimage, so import it with from scipy.ndimage import gaussian_filter.

2. Step 2: Verify function usage

   Apply it by calling gaussian_filter(image, sigma=2) to blur with sigma 2.

3. Final Answer:

   from scipy.ndimage import gaussian_filter filtered = gaussian_filter(image, sigma=2) -> Option A

4. Quick Check:

   Correct import and sigma usage = from scipy.ndimage import gaussian_filter filtered = gaussian_filter(image, sigma=2) [OK]

Hint: Import from scipy.ndimage, use sigma as keyword [OK]

Common Mistakes:

• Wrong import path for gaussian_filter
• Passing sigma as positional without keyword
• Using incorrect import syntax

3. Given the code below, what will be the output array after applying the Gaussian filter?

import numpy as np
from scipy.ndimage import gaussian_filter

image = np.array([[0, 0, 0],
                  [0, 10, 0],
                  [0, 0, 0]])
filtered = gaussian_filter(image, sigma=1)
print(np.round(filtered, 2))

medium

A. [[0.46 1.23 0.46]
[1.23 2.99 1.23]
[0.46 1.23 0.46]]

B. [[0 0 0]
[0 10 0]
[0 0 0]]

C. [[2.5 2.5 2.5]
[2.5 2.5 2.5]
[2.5 2.5 2.5]]

D. [[0.1 0.1 0.1]
[0.1 10 0.1]
[0.1 0.1 0.1]]

Solution

1. Step 1: Understand Gaussian filter effect on sparse image

   The single bright pixel (10) will blur into neighbors, spreading intensity smoothly.

2. Step 2: Calculate approximate blurred values

   Using sigma=1, the center pixel reduces from 10 to about 3, neighbors get values around 1.2 to 0.46.

3. Final Answer:

   [[0.46 1.23 0.46] [1.23 2.99 1.23] [0.46 1.23 0.46]] -> Option A

4. Quick Check:

   Blur spreads intensity smoothly = [[0.46 1.23 0.46] [1.23 2.99 1.23] [0.46 1.23 0.46]] [OK]

Hint: Gaussian blur spreads bright pixels softly to neighbors [OK]

Common Mistakes:

• Expecting no change in array
• Assuming uniform average instead of weighted blur
• Misreading sigma effect as sharpening

4. Identify the error in the following code snippet that applies a Gaussian filter:

import numpy as np
from scipy.ndimage import gaussian_filter

image = np.ones((5,5))
filtered = gaussian_filter(image, sigma='2')
print(filtered)

medium

A. gaussian_filter cannot be applied to numpy arrays

B. The array shape is invalid for gaussian_filter

C. Missing import for numpy

D. sigma should be a number, not a string

Solution

1. Step 1: Check parameter types

   The sigma parameter must be a numeric value (int or float), not a string.

2. Step 2: Identify the cause of error

   Passing '2' as a string causes a type error when the filter tries to compute the blur.

3. Final Answer:

   sigma should be a number, not a string -> Option D

4. Quick Check:

   Numeric sigma required, string causes error [OK]

Hint: Use numeric sigma, not string, to avoid errors [OK]

Common Mistakes:

• Passing sigma as string
• Assuming gaussian_filter needs special array types
• Ignoring import errors

5. You have a noisy grayscale image stored as a 2D numpy array. You want to smooth the image but keep edges relatively sharp. Which approach using gaussian_filter and its parameters is best?

hard

A. Apply gaussian_filter multiple times with sigma=3

B. Use a large sigma value like 5 to blur the image heavily

C. Use a small sigma value like 0.5 to reduce noise but preserve edges

D. Do not use gaussian_filter; use median filter instead

Solution

1. Step 1: Understand sigma effect on smoothing

   Small sigma values cause light blur, preserving edges better than large sigma which blurs heavily.

2. Step 2: Choose best sigma for noise reduction and edge preservation

   Using sigma=0.5 smooths noise but keeps edges sharper than larger sigma values or repeated blurring.

3. Final Answer:

   Use a small sigma value like 0.5 to reduce noise but preserve edges -> Option C

4. Quick Check:

   Small sigma = smooth noise + keep edges [OK]

Hint: Small sigma blurs less, preserving edges better [OK]

Common Mistakes:

• Using large sigma blurs edges too much
• Applying filter multiple times causes over-blur
• Confusing gaussian_filter with median filter