Introduction to Convolution and Deconvolution
引入
我们知道全连接网络 (Fully Connected Network, FCN) 是一种由输入层、一个或多个隐藏层以及输出层组成人工神经网络，其中每一层的神经元都会对前一层的所有神经元的输出进行加权求和，并通过激活函数进行非线性变换。
当我们使用 FCN 处理图像这样的高维数据时，输入图片上的所有像素点会被展平 (flattern) 成一个向量再输入网络。这样往往会存在如下两个问题：
- 输入数据的空间信息被丢失。空间上相邻的像素点往往具有相似的 RGB 值，RGB 的各个通道间的数据通常密切相关，但是转化成的向量并无法表征这些信息。
- 模型参数过多，容易发生过拟合。由于每个像素点都要跟所有输出的神经元相连接。当图片尺寸变大时，输入神经元的个数会按图片尺寸的平方增大，导致模型参数过多，容易发生过拟合。对于一幅 $1000×1000$ 的输入图像而言，如果下一个隐含层的神经元数目为 $10^6$ 个，那么将会有 $1000×1000×10^6=10^{12}$ 个权重参数，可以想象，拥有如此庞大参数量的网络很难训练。
我们引入卷积 (Convolution) 来对输入的图像进行特征提取。卷积的计算范围是在像素点的空间邻域内进行的，因此可以利用输入图像的空间信息；此外，由于卷积具有局部连接、权重共享等特性，卷积核参数的数目也远小于全连接层。
卷积运算
- Kernel / Stride / Feature map
卷积的运算操作其实就是对卷积核 (kernel) 中的元素与输入矩阵上对应位置的元素进行逐像素的乘积并求和 (矩阵内积，inner product)。然后使用卷积核在输入矩阵上根据设置的步长 (stride) 滑动，直到遍历完输入矩阵的所有位置。卷积滤波结果在卷积神经网络中被称为特征图 (feature map)。
- Padding
当 stride 不为 1 时，可能存在卷积核在边缘像素点处部分滑出了输入矩阵的情况，这时我们进行填充 (padding) 操作，即在超出的部分补值。一般在边缘像素点周围填充 $0$ (即 0-padding)，使得输入图像的边缘像素也可以参与卷积计算。
- Receptive field
卷积所得结果中，每个特征图像素点取值依赖于输入图像中的某个区域，该区域被称为感受野 (receptive field)。在卷积神经网络中，感受野是特征图上的点对应输入图像上的区域。感受野内每个元素数值的变动，都会影响输出点的数值变化。
- Shared weight
卷积计算实际上是使用一组卷积核在图片上进行滑动，对于同一个卷积核而言，在与图像计算的过程中，它的权重是共享的。这其实就大大降低了网络的训练难度。在上边的例子中，对于一幅 $1000×1000$ 的输入图像，下一个隐含层的神经元数目为 $10^6$ 个，隐含层中的每个神经元与大小为 $10×10$ 的局部区域相连，因此有 $10×10$ 个权重参数。将这 $10×10$ 个权重参数共享给其他位置对应的神经元，也就是 $10^6$ 个神经元的权重参数保持一致，那么最终需要训练的参数就只有这 $10×10$ 个权重参数了。
对于实际上有 RGB 三个通道的彩色图片来说也同理，只不过每一张图片都对应三个输入矩阵，每一个卷积核也对应三个矩阵，feature map 中的每一个值是都三组矩阵内积的和。
图像卷积计算实质上是对图像进行了下采样 (down sampling) 操作。对卷积得到的图像结果不断卷积滤波，则原始图像就会被层层抽象、层层约减。
转置卷积运算
图像经过多层的卷积运算后，输出图像的尺寸会变得很小。而对于某些特定的任务 (图像分割、GAN 等)，我们需要将图像恢复到原来的尺寸再进行进一步的计算。这个恢复图像尺寸，实现图像由小分辨率到大分辨率映射 (mapping) 的操作称为上采样 (up sampling)。
上采样有多种方式，常见的包括最近邻插值 (Nearest neighbor interpolation)、双线性插值 (Bi-Linear interpolation) 等，但是这些上采样方法都是基于人们的先验经验来设计的，对于很多场景效果并不理想。因此，我们引入转置卷积 (Transpose Convolution) ，有时也被称为反卷积 (Deconvolution) 的方法来让神经网络自己学习如何更好地进行插值。
我们通过卷积核将输入图片中的一个区域中的一些值映射到 feature map 中的一个值，也就是说，我们可以认为卷积操作实际上建立了一个多对一的关系。而对于转置卷积，我们实际上是想建立一个卷积逆向操作，即建立一个一对多的关系。
推导
定义 $4\times 4$ 的输入矩阵 $input$ 为:
$$ input= \left[ \begin{matrix} x_1 & x_2 & x_3 & x_4 \\ x_5 & x_6 & x_7 & x_8 \\ x_9 & x_{10} & x_{11} & x_{12} \\ x_{13} & x_{14} & x_{15} & x_{16} \\ \end{matrix} \right] $$定义 $3\times 3$ 的卷积核 $kernal$ 为:
$$ kernel= \left[ \begin{matrix} w_{0,0} & w_{0,1} & w_{0,2} \\ w_{1,0} & w_{1,1} & w_{1,2} \\ w_{2,0} & w_{2,1} & w_{2,2} \\ \end{matrix} \right] $$- $stride=1$ 时
令$stride=1$，$padding=0$，我们可以得到 $2\times 2$ 的输出矩阵 $output$:
$$ output= \left[ \begin{matrix} y_0 & y_1 \\ y_2 & y_3 \end{matrix} \right] $$将 $input$ 和 $output$ 展开成列向量 $\mathbf{X}$ 和列向量 $\mathbf{Y}$:
$$ \mathbf{X}= \left[ \begin{matrix} x_1 \\ x_2 \\ x_3 \\ \dots \\ x_{16} \end{matrix} \right],\quad \mathbf{Y}= \left[ \begin{matrix} y_1 \\ y_2 \\ y_3 \\ y_4 \end{matrix} \right] $$我们用矩阵运算 $\mathbf{Y}=C\mathbf{X}$ 来描述卷积运算，经过推导可以得到这个稀疏矩阵 $C$:
$$ C= \left[ \begin{matrix} w_{0,0} & w_{0,1} & w_{0,2} & 0 & w_{1,0} & w_{1,1} & w_{1,2} & 0 & w_{2,0} & w_{2,1} & w_{2,2} & 0 & 0 & 0 & 0 & 0 \\ 0 & w_{0,0} & w_{0,1} & w_{0,2} & 0 & w_{1,0} & w_{1,1} & w_{1,2} & 0 & w_{2,0} & w_{2,1} & w_{2,2} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & w_{0,0} & w_{0,1} & w_{0,2} & 0 & w_{1,0} & w_{1,1} & w_{1,2} & 0 & w_{2,0} & w_{2,1} & w_{2,2} & 0 \\ 0 & 0 & 0 & 0 & 0 & w_{0,0} & w_{0,1} & w_{0,2} & 0 & w_{1,0} & w_{1,1} & w_{1,2} & 0 & w_{2,0} & w_{2,1} & w_{2,2} \end{matrix} \right] $$而转置卷积其实就是要对这个过程进行逆运算，即 $\mathbf{X}=C^T\mathbf{Y}$。然后对 $\mathbf{X}$ 进行重新排序即可得到 $X$。代入后可得:
$$ X= \left[ \begin{matrix} w_{0,0} y_{0} & w_{0,1} y_{0} + w_{0,0} y_{1} & w_{0,2} y_{0} + w_{0,1} y_{1} & w_{0,2} y_{1} \\ w_{1,0} y_{0} + w_{0,0} y_{2} & w_{1,1} y_{0} + w_{1,0} y_{2} + w_{0,0} y_{3} & w_{1,2} y_{0} + w_{1,1} y_{1} & w_{1,2} y_{1} + w_{0,2} y_{3} \\ w_{2,0} y_{0} & w_{2,1} y_{0} + w_{2,0} y_{2} & w_{2,2} y_{0} + w_{2,1} y_{1} + w_{1,1} y_{3} & w_{2,2} y_{1} + w_{1,2} y_{3} \\ w_{2,0} y_{2} & w_{2,1} y_{2} + w_{2,0} y_{3} & w_{2,2} y_{2} + w_{2,1} y_{3} & w_{2,2} y_{3} \end{matrix} \right] $$我们可以发现这样的过程等价于对输出矩阵作 $padding=2$ ($padding=k-1$, $k$ 为卷积核的尺寸)的填充，并将其作为输入矩阵:
$$ input^{\prime}= \left[ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & y_0 & y_1 & 0 & 0 \\ 0 & 0 & y_2 & y_3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{matrix} \right] $$将原先的卷积核进行翻转 (注意这里不是转置，而是行与列全部颠倒顺序) 作为卷积核:
$$ kernel^{\prime}= \left[ \begin{matrix} w_{2,2} & w_{2,1} & w_{2,0} \\ w_{1,2} & w_{1,1} & w_{1,0} \\ w_{0,2} & w_{0,1} & w_{0,0} \\ \end{matrix} \right] $$进行 $stride=1$ 的卷积的结果。
- $stride > 1$ 时
我们令输入矩阵尺寸为 $5×5$，卷积核的设置同上，$stride=2$，$padding=0$，标准卷积运算后，输出矩阵尺寸为 $2×2$。
同理用矩阵运算 $\mathbf{Y}=C\mathbf{X}$ 来描述卷积运算，转换的稀疏矩阵 $C$ 尺寸变为25×4，由于矩阵太大这里不展开进行罗列。
转置卷积的结果通过 $\mathbf{X}=C^T\mathbf{Y}$ 以及变形可得:
$$ X= \left[ \begin{matrix} w_{0,0} y_{0} & w_{0,1} y_{0} & w_{0,2} y_{0} + w_{0,0} y_{1} & w_{0,2} y_{1} \\ w_{1,0} y_{0} & w_{1,1} y_{0} & w_{1,2} y_{0} + w_{1,0} y_{1} & w_{1,2} y_{1} \\ w_{2,0} y_{0} + w_{0,0} y_{2} & w_{2,1} y_{0} + w_{0,1} y_{2} & w_{2,2} y_{0} + w_{2,0} y_{1} + w_{0,2} y_{2} + w_{0,0} y_{3} & w_{2,2} y_{1} + w_{2,1} y_{1} + w_{0,1} y_{3} \\ w_{1,0} y_{2} & w_{1,1} y_{2} & w_{1,2} y_{2} + w_{1,0} y_{3} & w_{1,2} y_{3} \\ w_{2,0} y_{2} & w_{2,1} y_{2} & w_{2,2} y_{2} + w_{2,0} y_{3} & w_{2,2} y_{3} \end{matrix} \right] $$等价于对输出矩阵同时作相邻元素间添加 $1$ ($stride-1$) 个空洞的操作和 $padding=2$ ($padding=k-1$, $k$ 为卷积核的尺寸)的填充操作:
$$ input^{\prime}= \left[ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & y_0 & 0 & y_1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & y_2 & 0 & y_3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{matrix} \right] $$将原先的卷积核进行翻转 (同上) 作为卷积核:
$$ kernel^{\prime}= \left[ \begin{matrix} w_{2,2} & w_{2,1} & w_{2,0} \\ w_{1,2} & w_{1,1} & w_{1,0} \\ w_{0,2} & w_{0,1} & w_{0,0} \\ \end{matrix} \right] $$进行 $stride=1$ 的卷积的结果。
