2-D convolution as matrix-matrix multiplication

Question

I know that in the 1-D case the convolution between the two vectors a,b can be calculated as conv(a,b) , but also as the product between T_a and b , where T_a is the corresponding Toeplitz matrix for a .

Can this idea be extended to 2-D?

Given a=[5 1 3;1 1 2;2 1 3] and b=[4 3;1 2] , is it possible to convert a to the Toeplitz matrix and calculate the matrix-matrix product between T_a and b as in the 1-D case ?

Answer 1

Yes, it is possible, and you should also use a two-cylinder circulant matrix (which is a special case of Toeplitz ). I will give you an example with a small kernel and input size, but you can build a Toeplitz matrix for any kernel. So, you have the 2d input x and 2d kernel k , and you want to compute the convolution x * k . Also suppose that k already upside down. Suppose also that x has size nxn and k is mxm .

So, you expand k into a sparse matrix of size (n-m+1)^2 X n^2 and expand x into a long vector n^2 X 1 . You calculate the multiplication of this sparse matrix by a vector and convert the resulting vector (which will be of size (n-m+1)^2 X 1 ) into a square matrix n-m+1 .

I am sure it’s hard to understand just by reading. So, here is an example for input 2x2 and 3x3.

*

Here is the constructed matrix with a vector:

which is equal .

And this is the same result you would get by running a sliding window k on top of x .

Answer 2

If you solve k to a vector m ^ 2 and expand X, you get:

• a m**2 vector k
• a ((nm)**2, m**2) for unrolled_X

where unrolled_X can be obtained with the following Python code:

 from numpy import zeros def unroll_matrix(X, m): flat_X = X.flatten() n = X.shape[0] unrolled_X = zeros(((n - m) ** 2, m**2)) skipped = 0 for i in range(n ** 2): if (i % n) < n - m and ((i / n) % n) < n - m: for j in range(m): for l in range(m): unrolled_X[i - skipped, j * m + l] = flat_X[i + j * n + l] else: skipped += 1 return unrolled_X 

Deploying X and not k allows for a more compact representation (smaller matrices) than vice versa for each X, but you need to expand each X. You may prefer to expand k depending on what you want to do.

Here unrolled_X not sparse, while unrolled_k will be sparse, but in size ((n-m+1)^2,n^2) , as mentioned by @Salvador Dali.

Scan k can be performed as follows:

 from scipy.sparse import lil_matrix from numpy import zeros import scipy def unroll_kernel(kernel, n, sparse=True): m = kernel.shape[0] if sparse: unrolled_K = lil_matrix(((n - m)**2, n**2)) else: unrolled_K = zeros(((n - m)**2, n**2)) skipped = 0 for i in range(n ** 2): if (i % n) < n - m and((i / n) % n) < n - m: for j in range(m): for l in range(m): unrolled_K[i - skipped, i + j * n + l] = kernel[j, l] else: skipped += 1 return unrolled_K