Image filtering in MATLAB - Time & Space Complexity

Time Complexity: Image filtering

O(n x m)

Understanding Time Complexity

When we apply a filter to an image, the computer processes each pixel to create a new image.

We want to know how the time needed grows as the image size gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

% Assume img is a grayscale image matrix
filtered_img = zeros(size(img));
filter = [1 1 1; 1 1 1; 1 1 1] / 9; % simple averaging filter

for i = 2:size(img,1)-1
    for j = 2:size(img,2)-1
        region = img(i-1:i+1, j-1:j+1);
        filtered_img(i,j) = sum(region .* filter, 'all');
    end
end
    

This code applies a 3x3 averaging filter to each pixel of the image, skipping the edges.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over image rows and columns applying the filter.
• How many times: The outer loop runs about the number of rows (n), and the inner loop runs about the number of columns (m), so roughly n x m times.

How Execution Grows With Input

As the image gets bigger, the number of pixels grows, so the work grows too.

Input Size (pixels)	Approx. Operations
10 x 10	~100
100 x 100	~10,000
1000 x 1000	~1,000,000

Pattern observation: Doubling the image width and height roughly quadruples the work because we process every pixel.

Final Time Complexity

Time Complexity: O(n x m)

This means the time grows directly with the number of pixels in the image.

Common Mistake

[X] Wrong: "The filter size affects the time complexity a lot, so bigger filters make the time grow faster than the image size."

[OK] Correct: The filter size is fixed and small (like 3x3), so it only adds a constant amount of work per pixel, not changing the overall growth with image size.

Interview Connect

Understanding how image filtering scales helps you explain performance in real projects where images can be large and processing time matters.

Self-Check

"What if we used a filter that changes size depending on the image dimensions? How would the time complexity change?"

Practice

1. What is the main purpose of applying an image filter using a kernel in MATLAB?

easy

A. To convert the image to grayscale

B. To modify the image by emphasizing or reducing certain features

C. To increase the image file size

D. To change the image file format

Solution

1. Step 1: Understand what a kernel does

   A kernel is a small matrix used to process an image by changing pixel values based on neighbors.

2. Step 2: Identify the effect of filtering

   Filtering modifies the image to highlight edges, blur, or sharpen features, not file format or size.

3. Final Answer:

   To modify the image by emphasizing or reducing certain features -> Option B

4. Quick Check:

   Image filtering changes features = D [OK]

Hint: Filters change image features, not file type or size [OK]

Common Mistakes:

• Confusing filtering with file format conversion
• Thinking filtering changes image size
• Assuming filtering only converts to grayscale

2. Which of the following is the correct syntax to apply a filter kernel h to an image img using MATLAB's imfilter function?

easy

A. filtered_img = filter(h, img);

B. filtered_img = filter(img, h);

C. filtered_img = imfilter(h, img);

D. filtered_img = imfilter(img, h);

Solution

1. Step 1: Recall MATLAB's imfilter syntax

   The correct syntax is imfilter(image, kernel), where the image is first and kernel second.

2. Step 2: Check each option

   filtered_img = imfilter(img, h); matches the correct syntax. Options B and D use 'filter' which is incorrect. filtered_img = imfilter(h, img); reverses arguments.

3. Final Answer:

   filtered_img = imfilter(img, h); -> Option D

4. Quick Check:

   imfilter(image, kernel) = A [OK]

Hint: imfilter(image, kernel) is the correct order [OK]

Common Mistakes:

• Using 'filter' instead of 'imfilter'
• Swapping image and kernel arguments
• Missing semicolon or parentheses

3. Given the following MATLAB code:

img = [1 2 3; 4 5 6; 7 8 9];
h = [1 0 -1; 1 0 -1; 1 0 -1];
result = imfilter(img, h, 'replicate');

What is the value of result(2,2)?

medium

A. 0

B. 3

C. 6

D. 9

Solution

1. Step 1: Understand the filter and padding

   The kernel h detects vertical edges. 'replicate' pads edges by repeating border values.

2. Step 2: Calculate convolution at (2,2)

   Neighborhood of (2,2):
   1 2 3
   4 5 6
   7 8 9
   Apply kernel:
   (1*1)+(0*2)+(-1*3)+(1*4)+(0*5)+(-1*6)+(1*7)+(0*8)+(-1*9) = 1+0-3+4+0-6+7+0-9 = (1-3)+(4-6)+(7-9) = -2 -2 -2 = -6
   But imfilter flips kernel, so actual sum is 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   imfilter result center = 6 [OK]

Hint: Remember imfilter flips kernel before applying [OK]

Common Mistakes:

• Not flipping the kernel before convolution
• Ignoring padding method 'replicate'
• Calculating sum incorrectly

4. Consider this MATLAB code snippet:

img = imread('peppers.png');
h = fspecial('average', 3);
filtered_img = imfilter(img, h, 'same');

What is the error in this code?

medium

A. No error; the code runs correctly

B. imfilter requires grayscale images only

C. The kernel size in fspecial must be odd

D. The 'same' option is invalid for imfilter

Solution

1. Step 1: Check fspecial usage

   fspecial('average', 3) creates a 3x3 averaging filter, which is valid.

2. Step 2: Check imfilter usage

   imfilter supports RGB images and 'same' option returns output same size as input.

3. Final Answer:

   No error; the code runs correctly -> Option A

4. Quick Check:

   fspecial + imfilter with 'same' = A [OK]

Hint: imfilter works with color images and 'same' option [OK]

Common Mistakes:

• Assuming imfilter only works on grayscale
• Thinking 'same' is invalid option
• Believing kernel size must be odd but 3 is odd and valid

5. You want to sharpen an image img in MATLAB by combining the original image with a filtered version using the Laplacian kernel h = fspecial('laplacian', 0.2);. Which code snippet correctly applies this sharpening?

hard

A. sharpened = img - imfilter(img, h, 'replicate');

B. sharpened = img + imfilter(img, h, 'replicate');

C. sharpened = imfilter(img, h, 'replicate') - img;

D. sharpened = imfilter(img, h, 'replicate') + img * 0.2;

Solution

1. Step 1: Understand Laplacian sharpening

   Sharpening = original image minus the Laplacian filtered image to enhance edges.

2. Step 2: Match code to formula

   sharpened = img - imfilter(img, h, 'replicate'); subtracts the filtered image from original, correctly applying sharpening.

3. Final Answer:

   sharpened = img - imfilter(img, h, 'replicate'); -> Option A

4. Quick Check:

   Sharpen = img - Laplacian filtered img = B [OK]

Hint: Sharpen by subtracting Laplacian filtered image [OK]

Common Mistakes:

• Adding instead of subtracting Laplacian result
• Multiplying original image incorrectly
• Confusing Laplacian with averaging filter