Image sharpening in Signal Processing - Time & Space Complexity

Time Complexity: Image sharpening

O(n)

Understanding Time Complexity

When sharpening an image, we apply a filter to every pixel to enhance details.

We want to know how the time to sharpen grows as the image size grows.

Scenario Under Consideration

Analyze the time complexity of the following image sharpening code snippet.

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

This code applies a 3x3 sharpening kernel to each pixel of the image.

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 9 times per pixel (3x3 kernel).

How Execution Grows With Input

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

Input Size (pixels)	Approx. Operations
10x10 = 100	100 x 9 = 900
100x100 = 10,000	10,000 x 9 = 90,000
1000x1000 = 1,000,000	1,000,000 x 9 = 9,000,000

Pattern observation: Operations grow roughly proportional to the number of pixels.

Final Time Complexity

Time Complexity: O(n)

This means the time to sharpen grows linearly with the number of pixels in the image.

Common Mistake

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

[OK] Correct: The nested loops over the kernel are fixed size (3x3), so they do not grow with image size. Only the loops over pixels grow.

Interview Connect

Understanding how image filters scale helps you explain performance in real projects and shows you can analyze nested loops clearly.

Self-Check

"What if we used a larger kernel, like 5x5? How would the time complexity change?"

Practice

1. What is the main purpose of image sharpening in signal processing?

easy

A. To reduce the image size

B. To highlight edges and make the image clearer

C. To blur the image for artistic effect

D. To convert the image to grayscale

Solution

1. Step 1: Understand image sharpening

   Image sharpening enhances edges and details to make images clearer.

2. Step 2: Compare options

   Only To highlight edges and make the image clearer describes highlighting edges and clarity, which is the goal of sharpening.

3. Final Answer:

   To highlight edges and make the image clearer -> Option B

4. Quick Check:

   Image sharpening = highlight edges [OK]

Hint: Sharpening means making edges clearer, not blurring [OK]

Common Mistakes:

• Confusing sharpening with blurring
• Thinking sharpening changes image size
• Assuming sharpening converts color formats

2. Which of the following is the correct Python syntax to apply a simple sharpening kernel using convolution with OpenCV?

easy

A. cv2.sharpen(image, kernel)

B. cv2.convolve(image, kernel)

C. cv2.filter2D(image, -1, kernel)

D. cv2.applySharpen(image, kernel)

Solution

1. Step 1: Recall OpenCV function for convolution

   OpenCV uses cv2.filter2D() to apply kernels for filtering images.

2. Step 2: Check options

   Only cv2.filter2D(image, -1, kernel) uses cv2.filter2D with correct parameters; others are invalid functions.

3. Final Answer:

   cv2.filter2D(image, -1, kernel) -> Option C

4. Quick Check:

   OpenCV convolution = filter2D [OK]

Hint: Use cv2.filter2D for custom kernel convolution [OK]

Common Mistakes:

• Using non-existent OpenCV functions
• Confusing convolution with sharpening function names
• Incorrect parameter order

3. Given the following Python code using OpenCV, what will be the output type of sharpened?

import cv2
import numpy as np
image = cv2.imread('photo.jpg')
kernel = np.array([[0, -1, 0], [-1, 5, -1], [0, -1, 0]])
sharpened = cv2.filter2D(image, -1, kernel)

medium

A. A sharpened image as a NumPy array

B. An error due to kernel shape

C. A grayscale image

D. A blurred image

Solution

1. Step 1: Understand filter2D output

   cv2.filter2D returns an image as a NumPy array after applying the kernel.

2. Step 2: Analyze kernel and output

   The kernel is a sharpening kernel, so output is sharpened image, still in color and array form.

3. Final Answer:

   A sharpened image as a NumPy array -> Option A

4. Quick Check:

   filter2D output = NumPy array image [OK]

Hint: filter2D returns image array, not blurred or grayscale [OK]

Common Mistakes:

• Assuming output is blurred instead of sharpened
• Thinking output is grayscale without conversion
• Believing kernel shape causes error

4. Identify the error in this Python code snippet for image sharpening:

import cv2
import numpy as np
image = cv2.imread('img.png')
kernel = np.array([[0, -1, 0], [-1, 5, -1], [0, -1, 0]])
sharpened = cv2.filter2D(image, 1, kernel)
cv2.imshow('Sharpened', sharpened)
cv2.waitKey(0)
cv2.destroyAllWindows()

medium

A. The ddepth parameter should be -1, not 1

B. The kernel shape is invalid

C. cv2.imshow cannot display color images

D. cv2.waitKey is missing argument

Solution

1. Step 1: Check ddepth parameter in filter2D

   ddepth=-1 means output image has same depth as input; 1 is invalid and may cause errors.

2. Step 2: Validate other code parts

   Kernel shape is valid, cv2.imshow supports color, waitKey(0) is correct usage.

3. Final Answer:

   The ddepth parameter should be -1, not 1 -> Option A

4. Quick Check:

   ddepth=-1 for same depth [OK]

Hint: Use ddepth=-1 in filter2D to keep image depth [OK]

Common Mistakes:

• Using wrong ddepth value causing errors
• Thinking kernel shape is wrong
• Misunderstanding cv2.imshow capabilities

5. You want to sharpen an image using unsharp masking. Which sequence of steps correctly applies this method?

hard

A. Directly apply a sharpening kernel without blurring

B. Add noise to the image, then apply a sharpening kernel

C. Convert image to grayscale, then apply a sharpening kernel

D. Blur the image, subtract the blurred from original, then add result back to original

Solution

1. Step 1: Understand unsharp masking process

   Unsharp masking involves blurring the image, subtracting this blur from original to get edges, then adding edges back.

2. Step 2: Evaluate options

   Only Blur the image, subtract the blurred from original, then add result back to original correctly describes this sequence; others miss key steps or add unrelated actions.

3. Final Answer:

   Blur the image, subtract the blurred from original, then add result back to original -> Option D

4. Quick Check:

   Unsharp masking = blur, subtract, add [OK]

Hint: Unsharp masking = blur, subtract, add back edges [OK]

Common Mistakes:

• Skipping the blur step
• Adding noise instead of subtracting blur
• Applying sharpening kernel directly without unsharp steps