二维卷积作为矩阵-矩阵乘法 [英] 2-D convolution as a matrix-matrix multiplication

问题描述

我知道，在一维情况下，两个向量之间的卷积，a 和 b，可以计算为 conv(a, b)，也可以作为T_a和b的乘积，其中T_a是a对应的托普利兹矩阵代码>.

是否可以将这个想法扩展到 2D?

给定 a = [5 1 3;1 1 2;2 1 3] 和 b=[4 3;1 2]，是否可以将a转换成Toeplitz矩阵并计算T_a和b之间的矩阵乘积和一维情况一样?

解决方案

是的，这是可能的，您还应该使用双块循环矩阵(这是 *

这是一个带有向量的构造矩阵:

等于 .

这与在 x 上做 k 的滑动窗口得到的结果相同.

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

Is it possible to extend this idea to 2D?

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

解决方案

Yes, it is possible and you should also use a doubly block circulant matrix (which is a special case of Toeplitz matrix). I will give you an example with a small size of kernel and the input, but it is possible to construct Toeplitz matrix for any kernel. So you have a 2d input x and 2d kernel k and you want to calculate the convolution x * k. Also let's assume that k is already flipped. Let's also assume that x is of size n×n and k is m×m.

So you unroll k into a sparse matrix of size (n-m+1)^2 × n^2, and unroll x into a long vector n^2 × 1. You compute a multiplication of this sparse matrix with a vector and convert the resulting vector (which will have a size (n-m+1)^2 × 1) into a n-m+1 square matrix.

I am pretty sure this is hard to understand just from reading. So here is an example for 2×2 kernel and 3×3 input.

*

Here is a constructed matrix with a vector:

which is equal to .

And this is the same result you would have got by doing a sliding window of k over x.

这篇关于二维卷积作为矩阵-矩阵乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！