二维卷积作为矩阵 - 矩阵乘法

Question

我知道，在一维情况下，两个矢量a和b之间的卷积可以计算为conv(a, b)，但也可以计算为T_a和b之间的乘积，其中T_a是a的相应Toeplitz矩阵。

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

给定a = [5 1 3; 1 1 2; 2 1 3]和b=[4 3; 1 2]，是否有可能在Toeplitz矩阵中转换a并计算T_a和b之间的矩阵 - 矩阵乘积，如1-D案例？

Answer 1

是的，这是可能的，您还应该使用双块循环矩阵（这是Toeplitz矩阵的特例）。我将给你一个小内核和输入的例子，但是可以为任何内核构造Toeplitz矩阵。所以你有一个2d输入x和2d内核k你想要计算卷积x * k。另外我们假设k已经被翻转了。让我们假设x的大小为n×n，k是m×m。

因此，您将k展开为大小为(n-m+1)^2 × n^2的稀疏矩阵，并将x展开为长矢量n^2 × 1。您计算此稀疏矩阵与向量的乘法，并将得到的向量（其大小为(n-m+1)^2 × 1）转换为n-m+1方阵。

我很确定这只是从阅读中难以理解。所以这是一个2×2内核和3×3输入的例子。

*

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

这相当于。

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

Answer 2

1-定义输入和过滤器

让我成为输入信号，F是滤波器或内核。

2-计算最终输出大小

如果I是m1 x n1而F是m2 x n2，则输出的大小为：

3-对填充矩阵进行零填充

零填充滤波器使其与输出的大小相同。

4-为零填充滤波器的每一行创建Toeplitz矩阵

5-创建一个双重阻塞的Toeplitz矩阵

现在所有这些小的Toeplitz矩阵都应该安排在一个大的双重阻塞的Toeplitz矩阵中。

6-将输入矩阵转换为列向量

7-用矢量化输入信号乘以双重阻塞的toeplitz矩阵

该乘法给出了卷积结果。

8-最后一步：将结果重新整形为矩阵形式

有关更多详细信息和python代码，请查看我的github存储库：

Step by step explanation of 2D convolution implemented as matrix multiplication using toeplitz matrices in python

Answer 3

如果你将k解释为m ^ 2向量并展开X，那么你将获得：

• 一个m**2 vectork
• ((n-m)**2, m**2)的unrolled_X矩阵

其中unrolled_X可以通过以下Python代码获得：

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

展开X而不是k允许比每个X的相反方式更紧凑的表示（更小的矩阵） - 但是你需要展开每个X.你可能更喜欢展开k取决于你想要做什么。

在这里，unrolled_X不是稀疏的，而unrolled_k将是稀疏的，但大小((n-m+1)^2,n^2)，如@Salvador Dali提到的。

展开k可以这样做：

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

Answer 4

上面显示的代码不会生成正确尺寸的展开矩阵。尺寸应为（n-k + 1）*（m-k + 1），（k）（k）。 k：过滤器维度，n：输入矩阵中的num行，m：num列。

def unfold_matrix(X, k):
    n, m = X.shape[0:2]
    xx = zeros(((n - k + 1) * (m - k + 1), k**2))
    row_num = 0
    def make_row(x):
        return x.flatten()

    for i in range(n- k+ 1):
        for j in range(m - k + 1):
            #collect block of m*m elements and convert to row
            xx[row_num,:] = make_row(X[i:i+k, j:j+k])
            row_num = row_num + 1

    return xx

有关详细信息，请参阅我的博文：

http://www.telesens.co/2018/04/09/initializing-weights-for-the-convolutional-and-fully-connected-layers/