2D Cross-Correlation (Valid)

Problem

Compute the valid-mode 2D cross-correlation of an image with a kernel.

out[i][j] = sum over (a, b) of image[i + a][j + b] * kernel[a][b]. The output shape is (H - kh + 1) x (W - kw + 1). Cross-correlation does not flip the kernel.

Hint

Slide the kernel over every valid top-left position and multiply elementwise.

Test cases

case 1

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

expected: [[37,47],[67,77]]

case 2

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

expected: [[5]]

case 3

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

expected: [[12,16]]

case 4

in: [[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]],[[1,0],[0,1]]]

expected: [[7,9,11],[15,17,19],[23,25,27]]

Starter codePython

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

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