Separable Convolution

Problem

Apply a 1D kernel along the rows and then along the columns in valid mode.

First compute row[i][j] = sum_m image[i][j + m] * kernel[m], then out[i][j] = sum_m row[i + m][j] * kernel[m]. The final shape is (H - k + 1) x (W - k + 1) where k = len(kernel).

Hint

Do one horizontal pass into a temporary image, then a vertical pass.

Test cases

case 1

in: [[[1,2,3,4],[5,6,7,8],[9,10,11,12]],[1,2,1]]

expected: [[96,112]]

case 2

in: [[[1,1,1],[1,1,1],[1,1,1]],[1,1,1]]

expected: [[9]]

case 3

in: [[[1,2,3],[4,5,6]],[1,1]]

expected: [[12,16]]

case 4

in: [[[1,2,3],[4,5,6],[7,8,9]],[1,-1]]

expected: [[0,0],[0,0]]

Starter codePython

def separable_convolve(image, kernel):
    # Your code here
    pass

4 test cases · run your code against them in the editor