Leetcode – Image Smoother Solution in Python

Spread the love

Introduction

Image processing is a domain that intersects computer science and mathematics, particularly matrix operations. One of the essential operations in image processing is smoothing or blurring an image, which is typically achieved by averaging the pixels of the image. The “Image Smoother” problem on Leetcode addresses this fundamental concept. In this article, we will discuss this problem in detail, explain different approaches for solving it, and present Python code for each solution.

Problem Statement

Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has fewer than 8 surrounding cells, then use as many as you can.

Example:

Input:

[[1,1,1],
 [1,0,1],
 [1,1,1]]

Output:

[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

Explanation: For the point (0, 0), among the surrounding cells (0, 1), (1, 0), and (1, 1), the average gray scale is (1 + 1 + 1 + 1) / 4 = 1.

Note:

  • The value in the given matrix is in the range of [0, 255].
  • The length and width of the given matrix are in the range of [1, 150].

Solution

1. Brute Force Solution

A brute-force solution involves going through each cell in the image and averaging its value with its surrounding cells.

  1. Create an empty output matrix of the same size as the input matrix.
  2. Iterate through each cell in the input matrix.
  3. For each cell, iterate through its neighbors and itself.
  4. Calculate the sum of the values of the neighbors and itself.
  5. Store the average value in the corresponding cell in the output matrix.
def image_smoother(M):
    if not M or not M[0]:
        return []
    
    rows, cols = len(M), len(M[0])
    result = [[0 for _ in range(cols)] for _ in range(rows)]
    
    directions = [(0, 0), (-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    
    for i in range(rows):
        for j in range(cols):
            total, count = 0, 0
            for d in directions:
                ni, nj = i + d[0], j + d[1]
                if 0 <= ni < rows and 0 <= nj < cols:
                    total += M[ni][nj]
                    count += 1
            result[i][j] = total // count
    
    return result

Time Complexity:

  • O(m * n), where m and n are the dimensions of the matrix.

Space Complexity:

  • O(m * n), as we are creating a new matrix to store the results.

2. Using Convolution (Advanced)

In image processing, convolution is a technique that can be used to apply a filter (like a smoother) to an image. This can be performed using various libraries like OpenCV or SciPy.

Here we are showing how to perform the smoothing using convolution with the SciPy library.

  1. Define a 3×3 kernel where all the values are 1. This kernel will be used for averaging.
  2. Use the convolve2d function from the SciPy library to apply the kernel to the image matrix.
from scipy.signal import convolve2d

def image_smoother(M):
    kernel = [[1, 1, 1],
              [1, 1, 1],
              [1, 1, 1]]
    
    conv_result = convolve2d(M, kernel, mode='same')
    
    rows, cols = len(M), len(M[0])
    result = [[0 for _ in range(cols)] for _ in range(rows)]
    
    for i in range(rows):
        for j in range(cols):
            neighbors = 9
            if i == 0 or i == rows-1:
                neighbors -= 3
            if j == 0 or j == cols-1:
                neighbors -= 3
            if (i == 0 or i == rows-1) and (j == 0 or j == cols-1):
                neighbors += 1
            result[i][j] = conv_result[i][j] // neighbors
    
    return result

Time Complexity:

  • This method is generally faster but depends on the implementation of the convolution function.

Space Complexity:

  • O(m * n), as we are creating a new matrix to store the results.

Conclusion

In this article, we explored the “Image Smoother” problem from Leetcode and presented two different approaches to solve it using Python. The first approach uses a simple brute-force method to iterate through each cell and calculate the average. The second approach utilizes a more advanced image processing technique called convolution.

Leave a Reply