Box Blur algorithm

Question

This is a challenge from CodeSignal.

For

image = [[1, 1, 1], 
         [1, 7, 1], 
         [1, 1, 1]]

the output should be boxBlur(image) = [[1]].

To get the value of the middle pixel in the input 3 × 3 square: (1 + 1 + 1 + 1 + 7 + 1 + 1 + 1 + 1) = 15 / 9 = 1.66666 = 1. The border pixels are cropped from the final result.

For

image = [[7, 4, 0, 1], 
         [5, 6, 2, 2], 
         [6, 10, 7, 8], 
         [1, 4, 2, 0]]

the output should be

boxBlur(image) = [[5, 4], 
                  [4, 4]]

There are four 3 × 3 squares in the input image, so there should be four integers in the blurred output. To get the first value: (7 + 4 + 0 + 5 + 6 + 2 + 6 + 10 + 7) = 47 / 9 = 5.2222 = 5. The other three integers are obtained the same way, then the surrounding integers are cropped from the final result.

Here's my code:

function boxBlur(image) {  
    const SQUARE = 3
    const outerArr = []

    for (let i = 0; i < image.length; i++) {
        const innerArr = []
        
        for (let j = 0; j < image[0].length; j++) {
            if (image[i][j] !== undefined && image[i][j+2] !== undefined && image[i+2]) {
                let sum = 0
                
                for (let k = 0; k < SQUARE; k++) {
                    for (let y = 0; y < SQUARE; y++) {
                        sum += image[i+k][j+y]    
                    }
                }
                innerArr.push(Math.floor(sum/9))                
            }
        }
        if (innerArr.length) outerArr.push(innerArr)
    }
    return outerArr
}
```

Answer 1

Some suggestions on coding style:

• Your choice in variables is somewhat confusing i, j? For an algorithm operating on a 2D image, the names x and y would be better. And dx, dy for the offsets in the inner loop.

• You defined the width of your kernel as SQUARE, yet you hardcode 2 in the expression image[i][j+2].

• Your boundary checks can be more efficient. Why check for undefined if you know the exact size of the image? You can loop i from 0 to image.length - SQUARE, and loop j from 0 to image[0].length - SQUARE and remove the if statement:

for (let i = 0; i < image.length - SQUARE; i++) {
    for (let j = 0; j < image[0].length - SQUARE; j++) {
        // no if-statement needed anymore
        ...
    }
}

Note that the naive algorithm works fine for small kernels, but can be done more efficient using a summation map where you first calculate the total sum of all preceding values in a preprocessing step, and then calculate the sum of the pixels in the square using the summation map of the 4 corner points. That way, the algorithm speed becomes independent of the size SQUARE of your kernel.

Answer 2

The code in general is pretty good, so I don't have a lot to suggest, just a handful of pointers.

• As already mentioned, variable naming could be a little better. For example, I'm not sure why your two most inner loops use the variables "k" and "y". "SQUARE" would probably be better named as "SQUARE_SIZE". outerArr and innerArr could be newImage and newRow. etc.
• Four nested loops is quite a lot. You could easily extract the two most inner loops into its own "calcBlurValueAtCoord()" function.
• When checking for out-of-bounds, the image[i][j] !== undefined check is doing nothing - image[i][j] will never be undefined. In fact, that whole if() could be simplified to this: if (image[i+2]?.[j+2] !== undefined)

Once you've applied those bullet points, I think your code would be pretty solid.

If you additionally wanted to make the code a little more functional and less procedural (not that you should or shouldn't, it's just a different style), you could replace the for loops with functions such as .map() and break out more helper functions.

In the below example, you'll notice that the boxBlur() function is really high-level - just by reading it, you can get an overview of how a box-blur is done: "With each coordinate in the grid, calculate a blur value, then trim the margins". What does it mean to "calculate a blur value"? Just look at that function definition (for blurValueAtCoord()): "Take the average of the surrounding coordinates and floor it" - you get the idea.

const boxBlur = grid => trimMargins(
  coordsInGrid(grid)
    .map(coord => blurValueAtCoord(grid, coord))
)

const average = array => array.reduce((a, b) => a + b) / array.length

const coordsInGrid = grid => grid.flatMap((row, y) => row.map((_, x) => [x, y]))

const blurValueAtCoord = (grid, coord) => Math.floor(average(getSurroundingValues(grid, coord)))

const trimMargins = grid => grid.slice(1, -1).map(row => row.slice(1, -1))

const getSurroundingValues = (grid, [y, x]) => [
  grid[y-1]?.[x-1], grid[y]?.[x-1], grid[y+1]?.[x-1],
  grid[y-1]?.[x],   grid[y]?.[x],   grid[y+1]?.[x],
  grid[y-1]?.[x+1], grid[y]?.[x+1], grid[y+1]?.[x+1],
].map(x => x ?? 0)

Answer 3

Here is a solution without an if statement as suggested by Jason

I removed the if statement, I used dx dy to represent the offset of x and y respectively

I didn't see the need to initiate Square variable to 3, hence I -1 so I can trim the borders

Hope this helps someone

function boxBlur(image){

    let blur = [];

    for (let x = 1; x < image.length - 1; x++){
      Let line = [];

      for (let y = 1; x < image[0].length - 1; y++){
         let sum = 0;

            
           //slicing off the borders of the image

           for (let dx = -1; dx <= 1; dx++){
             for (let dy = -1; dx <= 1; dy++){
                sum+= image[x + dx][y + dy]
             }
           }
           line.push(Math.floor(sum/9));
       }
       blur.push(line);
    }
    return blur
}