Matrix Convolution

Implement convolution of a matrix.

Convolution is the process of adding each element of the image to its local neighbors, weighted by the kernel. In other words, this is an element-wise product by the kernel on the sub-matrix, followed by a summation.

Complexity: O(k1*k2*m1*m2) time where k are the dimensions of the kernel and m are the dimensions of the matrix.

import numpy as np

# kernel (2n+1) by (2n+1) for all natural numbers
# that does not exceed dimensions of matrix
def convolution(matrix, kernel):
    m_rows = matrix.shape[0]
    m_cols = matrix.shape[1]

    k_rows = kernel.shape[0]
    k_cols = kernel.shape[1]

    assert (k_rows <= m_rows and k_cols <= m_cols)
    assert (k_rows % 2 != 0 and k_cols % 2 != 0)

    convolution = np.zeros((m_rows - int(k_rows / 2) - 1,
                           m_cols - int(k_cols / 2) - 1))

    for i in range(0, len(convolution)):
        for j in range(0, len(convolution[0])):
            submatrix = matrix[i:k_rows + i, j:k_cols + j]
            element_wise_mult = np.multiply(submatrix, kernel)
            convolution[i][j] = round(np.sum(element_wise_mult))

    return convolution


matrix = np.matrix('35 40 41 45 50; 40 40 42 46 52; 42 46 50 55 55; 48 52 56 58 60; 56 60 65 70 75')
kernel = np.matrix('0 1 0; 0 0 0; 0 0 0')
print(convolution(matrix, kernel))

matrix = np.matrix('17 24 1 8 15; 23 5 7 14 16; 4 6 13 20 22; 10 12 19 21 3; 11 18 25 2 9')
kernel = np.matrix('8 1 6; 3 5 7; 4 9 2]')
print(convolution(matrix, kernel))