2-D卷积作为矩阵乘法

Question

我知道，在一维情况下，向量a与b的卷积可以通过conv(a, b)或者是对应的Toeplitz矩阵T_a和b的乘积来计算。

但是这个方法可以扩展到二维吗？

如果给定a = [5 1 3; 1 1 2; 2 1 3]和b=[4 3; 1 2]，是否可以将a转换为Toeplitz矩阵，并像在一维情况下那样计算T_a和b的矩阵乘积呢？

- no_name

---

请参阅如何将卷积操作实现为矩阵-向量乘法？。 - nbro

我投票关闭此问题，因为它与[帮助中]定义的编程不相关，而是涉及ML理论和/或方法 - 请参见deep-learning [标签信息]（https://stackoverflow.com/tags/deep-learning/info）中的介绍和注意事项。 - desertnaut

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输入的示例。

*

这是用向量构建的矩阵：

这等价于 。

如果在 x 上使用大小为 k 的滑动窗口，也会得到同样的结果。

- Salvador Dali

---

最后需要进行一些重塑，对吗？那个最后的向量是4 x 1，但卷积的结果将是2 x 2。 - jvans

@jvans 是的，最终您应该重新塑造您的向量。这里写着：将结果向量（其大小为(n-m+1)^2 X 1）转换为一个n-m+1的方阵。 - Salvador Dali

你的例子不是托普利茨矩阵。所以你的答案只部分正确，对吗？ - user2682877

“Also let's assume that k is already flipped” 的意思是什么？这是因为我们想要执行相关操作而不是卷积操作吗？在NumPy操作中，“flipped”是什么意思？ - mrgloom

那么具体细节是什么？k 应该如何展开成稀疏矩阵？ - user76284

Answer 2

1- 定义输入和滤波器

设I为输入信号，F为滤波器或卷积核。

2- 计算最终输出尺寸

如果 I 是 m1 x n1，F 是 m2 x n2，则输出的尺寸将为：

3- 将滤波器矩阵填充为零

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

4- 为每一行零填充滤波器创建托普利茨矩阵

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

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

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

7- 将双重阻塞托普利茨矩阵与向量化输入信号相乘

这个乘积给出了卷积结果。

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

欲了解更多细节和Python代码，请查看我的GitHub存储库：

使用Toeplitz矩阵实现的矩阵乘法作为2D卷积的逐步说明

- Ali Salehi

---

我认为有一个错误。结果的第一个元素应该是100 + 200 + 300 +401 = 40。位置2,2的元素应该是110 + 220 + 430 + 540 = 370。我认为你的结果对于矩阵F等于[40 30; 20 10]是正确的，这正好是F翻转了行和列。因此，过程中存在错误。 - Luca

它正在执行卷积（数学卷积，而不是交叉相关），因此如果您手动执行它，则需要垂直和水平翻转滤波器。 您可以在我的GitHub存储库中找到更多信息。 - Ali Salehi

这是一个关于二维卷积作为矩阵运算的很好的解释。有没有一种方法也表示“mode ='same'”呢？（即保持输出形状与图像相同）？ - ajl123

@ajl123 我认为应该是这样的。如果我有时间，我会处理它。如果你得到了答案，请随时挖掘代码和数学，并在Github上向我发送一个pull请求。 - Ali Salehi

生成的矩阵的维度不应该会减少吗？ - gevaraweb

有没有一种方法可以重写操作，使得两个参数在操作方面对称？目前，您将过滤器转换为双重阻塞Toeplitz矩阵，并将图像转换为向量。是否有一种更对称的方法（因为卷积毕竟是可交换的），使得两个参数都经历完全相同的操作？ - lightxbulb

Answer 3

如果将k展开成一个m^2维的向量，同时展开X，你会得到：

- 一个大小为m^2的向量k - 一个大小为((n-m)^2, m^2)的矩阵unrolled_X

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

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

Unrolling 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

- Geoffrey Negiar

Answer 4

上面显示的代码没有生成正确尺寸的展开矩阵。尺寸应为(n-k+1)*(m-k+1)，(k)(k)。k：过滤器维度，n：输入矩阵中的行数，m：列数。

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/

- user8697906