二维离散卷积转换为矩阵相乘——卷积与反卷积

假设我们需要将矩阵 \mathbf{X} = \begin{bmatrix} x_1 & x_2 & x_3 \\ x_4 & x_5 & x_6 \\ x_7 & x_8 & x_9\end{bmatrix}\mathbf{H}=\begin{bmatrix} h_1 & h_2 \\ h_3 & h_4 \end{bmatrix} 为卷积核做卷积操作,普通操作是用卷积核在矩阵上进行滚动相乘相加,但是这样不利于 GPU 等硬件加速运算,一般而言,矩阵的卷积会先转换为稀疏矩阵的乘法,再通过 BLAS 等已经极度优化过的线性代数计算库来计算,效率可以得到提升。

下面说明一下转换的方法:对于原来的矩阵,我们展开成一个列向量

\mathbf{X}= \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \\ x_8 \\ x_9\end{bmatrix}

(说明:以下卷积操作没有对卷积核进行旋转操作,但道理类似)
之后我们对卷积核进行循环展开,展开成为这样的矩阵:

\mathbf{H} = \begin{bmatrix} h_1 & h_2 & 0 & h_3 & h_4 & 0 & 0 & 0 & 0 \\
0 & h_1 & h_2 & 0 & h_3 & h_4 & 0 & 0 & 0 \\
0 & 0 & 0 & h_1 & h_2 & 0 & h_3 & h_4 & 0 \\
0 & 0 & 0 & 0 & h_1 & h_2 & 0 & h_3 & h_4 \\
\end{bmatrix}

最后计算两个矩阵的乘积 \mathbf{HX} 就得到了:

\begin{bmatrix} h_1x_1+h_2x_2+h_3x_4+h_4x_5 \\
h_1x_2+h_2x_3+h_3x_5+h_4x_6 \\
h_1x_4+h_2x_5+h_3x_7+h_4x_8 \\
h_1x_5+h_2x_6+h_3x_8+h_4x_9 \\\end{bmatrix}

最后对这个列向量进行 reshape 操作就得到:

\begin{bmatrix} h_1x_1+h_2x_2+h_3x_4+h_4x_5 &
h_1x_2+h_2x_3+h_3x_5+h_4x_6 \\
h_1x_4+h_2x_5+h_3x_7+h_4x_8 &
h_1x_5+h_2x_6+h_3x_8+h_4x_9 \\\end{bmatrix}

正是卷积的结果。

那么通用的做法是什么呢?假设输入矩阵 \mathbf{X} 维数为 m_1 \times n_1,卷积核 \mathbf{H} 维数为 m_2 \times n_2,输出尺寸则为 (m_1+m_2-1) \times (n_1+n_2-1)

首先将卷积核向右上补零为输出结果的尺寸(举例为 4 \times 4):

\mathbf{H}=\begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ h_1 & h_2 & 0 & 0 \\ h_3 & h_4 & 0 & 0 \end{bmatrix}

从下到上将每一行展开成列数为 n_1Toeplitz 矩阵

\mathbf{F_0} = \begin{bmatrix} h_3 & 0 & 0 \\
h_4 & h_3 & 0 \\
0 & h_4 & h_3 \\
0 & 0 & h_4
\end{bmatrix}
\mathbf{F_1} = \begin{bmatrix} h_1 & 0 & 0 \\
h_2 & h_1 & 0 \\
0 & h_2 & h_1 \\
0 & 0 & h_2
\end{bmatrix}
\mathbf{F_3} = \mathbf{F_2} = \begin{bmatrix} 0 & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{bmatrix}

再将这些矩阵组合成 Doubly Blocked Toeplitz 矩阵,此时列数为 $m_1$:

\mathbf{D} = \begin{bmatrix} \mathbf{F_0} & \mathbf{0} & \mathbf{0} \\
\mathbf{F_1} & \mathbf{F_0} & \mathbf{0} \\
\mathbf{F_2} & \mathbf{F_1} & \mathbf{F_0} \\
\mathbf{F_3} & \mathbf{F_2} & \mathbf{F_1} \\
\end{bmatrix}

然后我们同样展开 \mathbf{X} 为列向量,不过要从下到上展开:

\mathbf{X}= \begin{bmatrix} x_7 \\ x_8 \\ x_9 \\ x_4 \\ x_5 \\ x_6 \\ x_1 \\ x_2 \\ x_3\end{bmatrix}

然后计算 \mathbf{D}\mathbf{X} 即可,计算完毕的结果同样进行 reshape,然后上下翻转就得到了我们想要的结果。

反卷积

pytorch 中,反卷积也叫 TransposedConvolution,这是为什么呢,我们看到文章前半段提到的矩阵乘法:

\mathbf{X}= \begin{bmatrix} x_1 \\\\ x_2 \\\\ x_3 \\\\ x_4 \\\\ x_5 \\\\ x_6 \\\\ x_7 \\\\ x_8 \\\\ x_9\end{bmatrix}
\mathbf{H} = \begin{bmatrix}  h_1 & h_2 & 0 & h_3 & h_4 & 0 & 0 & 0 & 0 \\\\
                   0 & h_1 & h_2 & 0 & h_3 & h_4 & 0 & 0 &  0 \\\\
                   0 & 0 & 0 & h_1 & h_2 & 0 & h_3 & h_4 & 0 \\\\
                   0 & 0 & 0 & 0 & h_1 & h_2 & 0 & h_3 & h_4  \\\\ 
\end{bmatrix}

\mathbf{X} 是一个 9\times1 的矩阵,而 \mathbf{H} 是一个 4\times9 的矩阵,因此 \mathbf{HX} 就是一个 4\times1 的矩阵,reshape 之后得到的是 2\times2 的矩阵。

假设我们现在有一张 2\times2 的特征图,要怎么反卷积得到一张上采样之后的图呢?看到这里你已经明白了,方法意外地简单,只需要把这个特征图也展开成列向量,然后用上面的卷积矩阵的转置进行左乘,就得到我们想要的结果!

展开成列向量的特征图尺寸是 4\times1\mathbf{H}^{\sf T} 的尺寸是 9\times4,左乘之后得到 9\times1 的矩阵,进行 reshape 得到了 3\times3 的原始图!

当然,在实际中,卷积与反卷积的权重不一定需要一样,尺寸也可以不一样。

参考资料:

https://stackoverflow.com/questions/16798888/2-d-convolution-as-a-matrix-matrix-multiplication