661. Image Smoother

Problem Description

The task is to write an algorithm for an "image smoother," which is a filter operation applied to each cell of a grayscale image. The image is represented as a 2D integer matrix, where each cell contains a grayscale value. The smoother considers the value of a cell and the values of the eight surrounding cells to calculate an average. This average is then rounded down and placed into the corresponding cell in the resulting image. When cells on the edges or corners of the image do not have eight surrounding cells, the smoother only averages over the existing neighbouring cells. The challenge is to apply this filter correctly, ensuring that boundary conditions are handled and only valid neighbours are included in the average calculation.

Intuition

The solution approach involves a nested loop to traverse each cell in the image. For each cell, a sub-loop considers the surrounding cells within a distance of 1 cell in all directions. To manage cells at the edges and corners that have fewer neighbours, the algorithm checks if each potential neighbouring cell is within the image boundaries before including it in the average calculation.

The steps are:

1. Loop over each cell in the input image.
2. Initialize sum (s) and count (cnt) variables for each cell. The sum will hold the total grayscale value sum of the neighbours, and count will keep track of the number of valid neighbours considered.
3. Use a nested loop to go through each of the surrounding cells, including the cell itself.
4. Check if the neighbouring cell is within the image boundaries (its indexes are neither less than 0 nor exceeding the image dimensions).
5. If the cell is within bounds, add its value to the sum and increment the count.
6. After considering all valid neighbours, calculate the average by dividing the sum by the count.
7. Assign the rounded down average to the corresponding cell in the output image matrix.
8. Return the resulting image matrix after the smoother has been applied to all cells.

The solution effectively handles the averaging with the correct denominator for each cell, taking image boundary conditions into account.

Solution Approach

The implementation of the image smoother involves tackling the problem with a brute-force approach, where each cell's value is updated based on its neighbours.

Here's a detailed breakdown of the solution approach:

1. The algorithm starts by determining the dimensions of the image matrix, which are stored in variables m and n, representing the number of rows and columns, respectively.

2. An output matrix ans of the same dimensions as the input (img) is created to store the smoothed values. This is initialized to zero for all cells.

3. A nested for loop is used to traverse through each cell of the image matrix img using row index i and column index j.

4. For each cell (i,j), we initialize s and cnt to zero. Here s will accumulate the sum of the grayscale values of the current cell and its valid neighbours, while cnt will count the number of valid neighbouring cells considered in the smoothing operation (including the cell itself).

5. Another nested for loop iterates over the cells in the 3x3 block centered at (i, j). The ranges of these loops are i-1 to i+1 and j-1 to j+1, attempting to cover all nine cells in the block including the center cell.

6. For every neighbouring cell, the algorithm checks if its coordinates (x, y) are within the image's boundaries using 0 <= x < m and 0 <= y < n. This ensures we do not attempt to access cells outside the array, which would result in an 'index out of range' error.

7. Only valid neighbours are included in the average calculation by adding their values to the s and incrementing the cnt.

8. Once all valid neighbours are considered, the algorithm computes the average value by dividing s by cnt. Integer division is used (// in Python), which gives us a rounded down result as required.

9. The calculated average is then assigned to the corresponding cell in the ans matrix.

10. After the completion of both nested loops, the matrix ans is fully populated with the smoothed values and is returned as the final result.

The simplicity of the brute-force approach makes it an uncomplicated solution that is easy to understand and implement. However, it does have a time complexity of O(m x n x k), where k is the number of neighbouring cells to consider (in this case, 9), because we are visiting each cell surrounding every cell in the matrix. Using brute force is acceptable here because the size of the smoothing filter is fixed and small.

Example Walkthrough

Let's illustrate the solution approach using a small example. Imagine we have the following 3x3 grayscale image matrix:

1[ [100, 200, 100],
2  [200, 300, 200],
3  [100, 200, 100] ]

This matrix represents the grayscale values for a 3x3 image. Now, let's walk through the steps to apply the image smoother for the central cell (1,1) with the value 300.

1. We determine the dimensions of the image, which here are m = 3 and n = 3.

2. We create an output matrix ans with the same dimensions, all initialized to zero:

1[ [0, 0, 0],
2  [0, 0, 0],
3  [0, 0, 0] ]

3. Using a nested for loop, we traverse each cell. We'll focus on the central cell (i=1, j=1).

4. Initially, let s = 0 and cnt = 0.

5. The nested for loop runs over the neighbours of the central cell. The loop ranges from i-1 to i+1 and j-1 to j+1, meaning it covers all nine cells in the block.

6. We check each cell in this range to see if they are within the boundaries.

7. As all cells are within the boundary for the central cell, we add each cell's value to s and increment cnt for each cell. So we end up with:

1   s = 100+200+100+200+300+200+100+200+100 = 1500
2   cnt = 9 (including the central cell itself)

8. We calculate the average grayscale value by integer division of s by cnt, which is 1500 // 9 = 166.

9. We place the average value in the central cell of the output:

1[ [0,  0, 0],
2  [0, 166, 0],
3  [0,  0, 0] ]

10. After repeating steps 3-9 for all other cells and adjusting the boundary cases accordingly, the final smoothed image matrix becomes:

1[ [150, 183, 150],
2  [183, 166, 183],
3  [150, 183, 150] ]

Here's how the boundary cases are averaged for top-left corner cell (i=0, j=0):

• s = 100+200+200+300, as only 4 cells (including itself) are valid neighbors.
• cnt = 4.
• The average is then 600 // 4 = 150.
• The value 150 is placed in the top-left cell of the output matrix.

The same approach is repeated for other edge cells, considering the valid neighbors. Once all cells are processed, ans matrix is returned as the result of the smoothed image.

Solution Implementation

Time and Space Complexity

Time Complexity

The given code iterates through every cell of the img matrix, represented by dimensions m x n, where m is the number of rows and n is the number of columns. For each cell (i, j), it considers up to 9 neighboring cells (including the cell itself) in a 3x3 grid. This nested iteration contributes a constant factor of 9 for each cell, because the innermost two loops (over x and y) run at most 3 times each.

Thus, the total time complexity is O(m * n * 9), which simplifies to O(m * n) since 9 is a constant factor and does not affect the asymptotic complexity.

Space Complexity

The space complexity comes from the additional matrix ans that is created to store the smoothed values. It's the same size as the input matrix img, so the space complexity is O(m * n).

No additional space is used that grows with the size of the input, as the variables s (sum of the neighbor values) and cnt (the count of neighbors considered) use constant space. Therefore, the total space complexity remains O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.