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

假设我们需要将矩阵 $\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_1$ 的 Toeplitz 矩阵

$$
\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