Image smoothing (Gaussian blur) in Signal Processing - Time & Space Complexity

Time Complexity: Image smoothing (Gaussian blur)

O(n * k^2)

Understanding Time Complexity

We want to understand how the time to smooth an image changes as the image size grows.

How does the number of operations increase when we apply Gaussian blur to bigger images?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for y in range(height):
    for x in range(width):
        sum = 0
        for ky in range(kernel_size):
            for kx in range(kernel_size):
                pixel = image[y + ky - offset][x + kx - offset]
                weight = kernel[ky][kx]
                sum += pixel * weight
        output[y][x] = sum
    

This code applies a Gaussian blur by sliding a kernel over each pixel and computing a weighted sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over image pixels and kernel elements.
• How many times: Outer loops run once per pixel (height x width), inner loops run once per kernel element (kernel_size²).

How Execution Grows With Input

As the image gets bigger, the number of pixels grows, so the work grows too. The kernel size stays the same.

Input Size (n = total pixels)	Approx. Operations
10 x 10 = 100	100 x kernel_size²
100 x 100 = 10,000	10,000 x kernel_size²
1000 x 1000 = 1,000,000	1,000,000 x kernel_size²

Pattern observation: Operations grow roughly in direct proportion to the number of pixels.

Final Time Complexity

Time Complexity: O(n * k^2)

This means the time to smooth the image grows linearly with the number of pixels and quadratically with the kernel size.

Common Mistake

[X] Wrong: "The time grows with the square of the image size because of nested loops."

[OK] Correct: The nested loops over pixels are two loops, but together they cover each pixel once, so total work is proportional to the number of pixels, not its square.

Interview Connect

Understanding how image processing scales helps you explain efficiency clearly and shows you can think about real data sizes.

Self-Check

"What if the kernel size also grew with the image size? How would the time complexity change?"

Practice

1. What is the main purpose of applying a Gaussian blur to an image?

easy

A. To smooth the image by averaging pixels with a weighted filter

B. To increase the image resolution

C. To convert the image to grayscale

D. To detect edges in the image

Solution

1. Step 1: Understand Gaussian blur function

   Gaussian blur smooths images by averaging pixels using a weighted filter based on a Gaussian function.

2. Step 2: Identify the main effect on the image

   This process reduces noise and smooths details, not increasing resolution or changing color or detecting edges.

3. Final Answer:

   To smooth the image by averaging pixels with a weighted filter -> Option A

4. Quick Check:

   Gaussian blur = smoothing with weighted average [OK]

Hint: Gaussian blur smooths images by weighted averaging [OK]

Common Mistakes:

• Confusing blur with edge detection
• Thinking blur increases resolution
• Assuming blur changes image color

2. Which of the following is the correct Python syntax to apply a Gaussian blur using OpenCV with kernel size 5x5 and sigma 1.0 on image img?

easy

A. cv2.GaussianBlur(img, (5), 1.0)

B. cv2.gaussian_blur(img, 5, 1.0)

C. cv2.GaussianBlur(img, 5, 1.0)

D. cv2.GaussianBlur(img, (5, 5), 1.0)

Solution

1. Step 1: Recall OpenCV GaussianBlur syntax

   The function requires the image, kernel size as a tuple (width, height), and sigma value.

2. Step 2: Check each option's syntax

   cv2.GaussianBlur(img, (5, 5), 1.0) uses correct function name and parameters: cv2.GaussianBlur(img, (5, 5), 1.0). Others have wrong function names or kernel size format.

3. Final Answer:

   cv2.GaussianBlur(img, (5, 5), 1.0) -> Option D

4. Quick Check:

   Correct syntax uses tuple kernel size [OK]

Hint: Kernel size must be a tuple like (5, 5) in OpenCV [OK]

Common Mistakes:

• Using kernel size as single integer instead of tuple
• Wrong function name capitalization
• Passing kernel size without parentheses

3. Given the following Python code using OpenCV, what will be the shape of the output image after applying Gaussian blur?

import cv2
img = cv2.imread('photo.jpg')
blurred = cv2.GaussianBlur(img, (7, 7), 2)
print(blurred.shape)

medium

A. Larger than original image shape

B. Smaller than original image shape

C. Same as original image shape

D. Returns a single number, not shape

Solution

1. Step 1: Understand GaussianBlur effect on image size

   Gaussian blur smooths the image but does not change its dimensions.

2. Step 2: Check output shape behavior

   The output image has the same height, width, and channels as the input image.

3. Final Answer:

   Same as original image shape -> Option C

4. Quick Check:

   Gaussian blur keeps image size unchanged [OK]

Hint: Gaussian blur smooths but keeps image size same [OK]

Common Mistakes:

• Assuming blur crops or resizes image
• Expecting output to be a single value
• Confusing blur with image scaling

4. Identify the error in this code snippet applying Gaussian blur:

import cv2
img = cv2.imread('image.png')
blur = cv2.GaussianBlur(img, 5, 1.5)
cv2.imshow('Blurred', blur)
cv2.waitKey(0)

medium

A. cv2.imshow requires image path, not image array

B. Kernel size should be a tuple, not an integer

C. Sigma value must be an integer, not float

D. cv2.waitKey needs a parameter greater than 1000

Solution

1. Step 1: Check GaussianBlur parameters

   The kernel size must be a tuple like (5, 5), not a single integer.

2. Step 2: Verify other function calls

   Sigma can be float, cv2.imshow accepts image arrays, and cv2.waitKey(0) is valid for waiting indefinitely.

3. Final Answer:

   Kernel size should be a tuple, not an integer -> Option B

4. Quick Check:

   Kernel size = tuple (width, height) [OK]

Hint: Kernel size must be tuple like (5, 5) in GaussianBlur [OK]

Common Mistakes:

• Passing kernel size as single integer
• Misunderstanding cv2.imshow input
• Incorrect sigma type assumptions

5. You want to reduce noise in a grayscale image but keep edges sharp. Which Gaussian blur parameters should you choose to balance smoothing and edge preservation?

hard

A. Small kernel size (3x3) and low sigma (0.5)

B. Large kernel size (15x15) and high sigma (5.0)

C. Kernel size (7x7) and sigma 0 (automatic calculation)

D. Kernel size (1x1) and sigma 10

Solution

1. Step 1: Understand effect of kernel size and sigma

   Small kernel and low sigma cause mild smoothing, preserving edges better.

2. Step 2: Analyze options for noise reduction and edge preservation

   Large kernel and high sigma cause heavy blur, losing edges. Sigma 0 lets OpenCV choose, which may be too strong. Kernel 1x1 means no blur.

3. Final Answer:

   Small kernel size (3x3) and low sigma (0.5) -> Option A

4. Quick Check:

   Small kernel + low sigma = smooth noise, keep edges [OK]

Hint: Use small kernel and low sigma to keep edges sharp [OK]

Common Mistakes:

• Choosing too large kernel causing edge loss
• Using sigma 0 without understanding automatic effect
• Using kernel 1x1 which applies no blur