Median and uniform filters in SciPy - Time & Space Complexity

Time Complexity: Median and uniform filters

O(n * k)

Understanding Time Complexity

When using median and uniform filters, it is important to know how the time to process data grows as the data size increases.

We want to understand how the filtering time changes when the input array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.ndimage import median_filter, uniform_filter

arr = np.random.rand(1000)
filtered_median = median_filter(arr, size=3)
filtered_uniform = uniform_filter(arr, size=3)
    

This code applies median and uniform filters of size 3 to a 1D array of 1000 elements.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each element, the filter looks at a small window of neighbors and computes either the median or the average.
• How many times: This operation repeats once for every element in the input array.

How Execution Grows With Input

As the input array size grows, the filter must process more elements, each requiring a small fixed number of operations.

Input Size (n)	Approx. Operations
10	About 10 times the window size operations
100	About 100 times the window size operations
1000	About 1000 times the window size operations

Pattern observation: The total work grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n * k) where k is the window size

This means the time to filter grows linearly with the number of elements in the input array and the window size.

Common Mistake

[X] Wrong: "Median filtering takes much longer than uniform filtering because it sorts the window every time."

[OK] Correct: Although median filtering does more work per element, both filters still process each element once, so their time grows linearly with input size. The difference is in constant factors, not the overall growth pattern.

Interview Connect

Understanding how filtering operations scale helps you explain performance in data processing tasks clearly and confidently.

Self-Check

What if we increased the filter size from 3 to 7? How would the time complexity change?

Practice

1. What is the main purpose of applying a median filter to a dataset?

easy

A. To find the maximum value in the dataset

B. To calculate the average of all values in the dataset

C. To remove noise by replacing each value with the middle value in its neighborhood

D. To sort the dataset in ascending order

Solution

1. Step 1: Understand median filter function

   A median filter replaces each data point with the median (middle) value of its neighbors, reducing spikes and noise.

2. Step 2: Compare options with median filter purpose

   Only To remove noise by replacing each value with the middle value in its neighborhood describes replacing values with the middle value in a neighborhood, which matches the median filter's role.

3. Final Answer:

   To remove noise by replacing each value with the middle value in its neighborhood -> Option C

4. Quick Check:

   Median filter = middle value replacement [OK]

Hint: Median filter picks middle value to reduce spikes [OK]

Common Mistakes:

• Confusing median filter with averaging
• Thinking median filter sorts entire dataset
• Assuming median filter finds max or min values

2. Which of the following is the correct way to import the median filter function from scipy?

easy

A. from scipy.ndimage import median_filter

B. import scipy.median_filter

C. from scipy import median_filter

D. import median_filter from scipy

Solution

1. Step 1: Recall scipy median filter import syntax

   The median_filter function is in scipy.ndimage module, so it is imported as from scipy.ndimage import median_filter.

2. Step 2: Check each option's correctness

   from scipy.ndimage import median_filter matches the correct syntax. The other options are invalid Python import statements.

3. Final Answer:

   from scipy.ndimage import median_filter -> Option A

4. Quick Check:

   Correct import = from scipy.ndimage import median_filter [OK]

Hint: Import median_filter from scipy.ndimage module [OK]

Common Mistakes:

• Trying to import median_filter directly from scipy
• Using invalid import syntax
• Confusing module names

3. What is the output of this code snippet?

import numpy as np
from scipy.ndimage import uniform_filter

arr = np.array([1, 2, 3, 4, 5])
result = uniform_filter(arr, size=3)
print(result)

medium

A. [1 2 3 4 5]

B. [1.66666667 2. 3. 4. 4.33333333]

C. [1 2 3 3 3 3]

D. [1 2 2 3 4]

Solution

1. Step 1: Understand uniform_filter with size=3

   The uniform_filter computes the average over a sliding window of size 3. For edges, it uses 'reflect' mode by default.

2. Step 2: Calculate each element in result

   Using reflect padding:
   - index 0: [2, 1, 2] avg = 1.66666667
   - index 1: [1, 2, 3] avg = 2.0
   - index 2: [2, 3, 4] avg = 3.0
   - index 3: [3, 4, 5] avg = 4.0
   - index 4: [4, 5, 4] avg = 4.33333333
   print(result) shows [1.66666667 2. 3. 4. 4.33333333]

3. Final Answer:

   [1.66666667 2. 3. 4. 4.33333333] -> Option B

4. Quick Check:

   Uniform filter smooths values with reflect padding [OK]

Hint: Uniform filter averages neighbors in window size [OK]

Common Mistakes:

• Confusing median_filter output with uniform_filter
• Ignoring edge effects in uniform_filter
• Expecting original array unchanged

4. Identify the error in this code that applies a median filter:

import numpy as np
from scipy.ndimage import median_filter

arr = np.array([1, 2, 100, 4, 5])
filtered = median_filter(arr, size=0)
print(filtered)

medium

A. missing import for numpy

B. median_filter requires 2D arrays only

C. numpy array must be float type

D. size parameter cannot be zero

Solution

1. Step 1: Check median_filter size parameter

   The size parameter defines the window size and must be a positive integer. Zero is invalid and causes an error.

2. Step 2: Verify other code parts

   Array is 1D which is allowed. numpy is imported. Data type can be int. So only size=0 is wrong.

3. Final Answer:

   size parameter cannot be zero -> Option D

4. Quick Check:

   Window size > 0 for median_filter [OK]

Hint: Window size must be positive integer [OK]

Common Mistakes:

• Using zero or negative size values
• Assuming median_filter only works on 2D arrays
• Forgetting to import numpy

5. You have a noisy 2D image array with salt-and-pepper noise. Which filter and parameters would best reduce noise while preserving edges?

import numpy as np
from scipy.ndimage import median_filter, uniform_filter

image = np.array([[10, 10, 10, 10],
                  [10, 255, 10, 10],
                  [10, 10, 10, 10],
                  [10, 10, 10, 10]])

hard

A. Use median_filter with size=3 to remove salt-and-pepper noise

B. Use uniform_filter with size=3 to blur the image

C. Use median_filter with size=1 to keep image unchanged

D. Use uniform_filter with size=1 to sharpen edges

Solution

1. Step 1: Understand noise type and filter effects

   Salt-and-pepper noise is best removed by median filters because they replace each pixel with the median of neighbors, preserving edges.

2. Step 2: Evaluate filter choices and parameters

   Median_filter with size=3 covers neighbors and removes noise spikes. Uniform_filter averages and blurs edges, not ideal here. Size=1 means no change.

3. Final Answer:

   Use median_filter with size=3 to remove salt-and-pepper noise -> Option A

4. Quick Check:

   Median filter + size=3 removes salt-and-pepper noise [OK]

Hint: Median filter removes salt-and-pepper noise best [OK]

Common Mistakes:

• Using uniform filter which blurs edges
• Using size=1 which does nothing
• Confusing noise types and filter effects