Image as 2D signal in Signal Processing - Time & Space Complexity

Time Complexity: Image as 2D signal

O(n^2)

Understanding Time Complexity

When working with images as 2D signals, we want to know how processing time changes as the image size grows.

We ask: How does the number of operations grow when the image gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for row in range(height):
    for col in range(width):
        pixel_value = image[row][col]
        processed_value = pixel_value * 2  # simple operation
        output_image[row][col] = processed_value

This code doubles each pixel value in a 2D image array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and processing each pixel in the 2D image.
• How many times: Once for every pixel, so height x width times.

How Execution Grows With Input

As the image size grows, the number of pixels grows with the area (height x width).

Input Size (height x width)	Approx. Operations
10 x 10 = 100	100
100 x 100 = 10,000	10,000
1000 x 1000 = 1,000,000	1,000,000

Pattern observation: Doubling the height and width makes the operations grow by about four times.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to process the image grows with the square of the image dimension size.

Common Mistake

[X] Wrong: "Processing each pixel once means time grows linearly with image size."

[OK] Correct: The image size is two-dimensional, so total pixels grow with height times width, not just one dimension.

Interview Connect

Understanding how image size affects processing time helps you explain efficiency in real tasks like filtering or transforming images.

Self-Check

"What if we only processed every other pixel in each row and column? How would the time complexity change?"

Practice

1. What does it mean to say an image is a 2D signal?

easy

A. It is a sound wave recorded over time.

B. It is made of pixels arranged in rows and columns.

C. It is a list of numbers without any order.

D. It is a single value representing brightness.

Solution

1. Step 1: Understand the structure of an image

   An image consists of pixels arranged in a grid with rows and columns.

2. Step 2: Define 2D signal in context

   A 2D signal means data varies in two dimensions, matching the rows and columns of pixels.

3. Final Answer:

   It is made of pixels arranged in rows and columns. -> Option B

4. Quick Check:

   Image = 2D pixel grid [OK]

Hint: Remember: images have width and height as 2D grids [OK]

Common Mistakes:

• Confusing image with 1D signals like audio
• Thinking image is just one brightness value
• Ignoring the grid arrangement of pixels

2. Which of the following is the correct way to represent a grayscale image in Python using a 2D list?

easy

A. image = (0, 255, 128, 64)

B. image = [0, 255, 128, 64]

C. image = {0:255, 1:128}

D. image = [[0, 255], [128, 64]]

Solution

1. Step 1: Identify 2D structure for image

   A grayscale image is a 2D array where each element is a pixel value.

2. Step 2: Check each option's structure

   image = [[0, 255], [128, 64]] uses a list of lists, representing rows and columns correctly.

3. Final Answer:

   image = [[0, 255], [128, 64]] -> Option D

4. Quick Check:

   2D list = correct image format [OK]

Hint: Use nested lists for rows and columns [OK]

Common Mistakes:

• Using 1D list instead of 2D
• Using dictionary which is unordered
• Using tuple which is immutable but not 2D

3. Given the Python code:

image = [[10, 20], [30, 40]]
brightness_sum = sum(sum(row) for row in image)
print(brightness_sum)

What is the output?

medium

A. 100

B. 40

C. None

D. TypeError

Solution

1. Step 1: Calculate sum of each row

   First row sum: 10 + 20 = 30; second row sum: 30 + 40 = 70.

2. Step 2: Sum the row sums

   Total sum = 30 + 70 = 100.

3. Final Answer:

   100 -> Option A

4. Quick Check:

   Sum of all pixels = 100 [OK]

Hint: Sum rows first, then sum those results [OK]

Common Mistakes:

• Summing only one row
• Confusing nested sums
• Expecting print to show None

4. Find the error in this code snippet that tries to access the pixel at row 1, column 2:

image = [[5, 10, 15], [20, 25, 30]]
pixel = image[1][2]
print(pixel)

medium

A. IndexError because column 2 does not exist

B. SyntaxError due to wrong brackets

C. No error; output is 30

D. TypeError because image is not a list

Solution

1. Step 1: Check image dimensions

   Image has 2 rows and 3 columns (indices 0 to 2).

2. Step 2: Access pixel at row 1, column 2

   image[1][2] accesses second row, third column, which is 30.

3. Final Answer:

   No error; output is 30 -> Option C

4. Quick Check:

   Valid index access = 30 [OK]

Hint: Remember indexing starts at 0 in Python [OK]

Common Mistakes:

• Thinking index 2 is out of range
• Confusing row and column order
• Assuming syntax error with brackets

5. You want to increase the brightness of a grayscale image by adding 50 to each pixel value without exceeding 255. Which Python code correctly does this for a 2D list image?

hard

A. bright_image = [[min(pixel + 50, 255) for pixel in row] for row in image]

B. bright_image = [pixel + 50 if pixel < 255 else 255 for pixel in image]

C. bright_image = [[pixel + 50 for pixel in row] for row in image]

D. bright_image = [[max(pixel + 50, 255) for pixel in row] for row in image]

Solution

1. Step 1: Understand brightness increase with limit

   We add 50 to each pixel but cap values at 255 to avoid overflow.

2. Step 2: Analyze each option

   bright_image = [[min(pixel + 50, 255) for pixel in row] for row in image]

   uses min(pixel + 50, 255) to cap values correctly.

   bright_image = [pixel + 50 if pixel < 255 else 255 for pixel in image]

   is wrong because it treats image as 1D.

   bright_image = [[pixel + 50 for pixel in row] for row in image]

   can exceed 255.

   bright_image = [[max(pixel + 50, 255) for pixel in row] for row in image]

   uses max which increases values beyond 255.

3. Final Answer:

   bright_image = [[min(pixel + 50, 255) for pixel in row] for row in image] -> Option A

4. Quick Check:

   Use min to cap brightness at 255 [OK]

Hint: Use min(pixel+50, 255) to avoid overflow [OK]

Common Mistakes:

• Not capping pixel values at 255
• Treating 2D image as 1D list
• Using max instead of min for capping