computer vision笔记：图像金字塔与高斯滤波器

在computer-vision笔记：HOG特征一文中，我曾提及了Image Pyramid。那么，这个图像金字塔究竟是一个什么名胜古迹呢？

References：

电子文献：
https://www.cnblogs.com/ronny/p/3886013.html
https://www.cnblogs.com/wynlfd/p/9704770.html
https://www.cnblogs.com/herenzhiming/articles/5276106.html
https://www.jianshu.com/p/73e6ccbd8f3f
https://baike.baidu.com/item/%E9%AB%98%E6%96%AF%E6%BB%A4%E6%B3%A2/9032353?fr=aladdin
https://blog.csdn.net/lvquanye9483/article/details/81592574
https://zhuanlan.zhihu.com/p/94014493

---

原因

当用一个机器视觉系统分析未知场景时，计算机没有办法预先知识图像中物体尺度，因此，我们需要同时考虑图像在多尺度下的描述，获知感兴趣物体的最佳尺度。在很多时候，我们会将图像构建为一系列不同尺度的图像集，在不同的尺度中去检测我们感兴趣的特征。比如：在Haar特征检测人脸的时候，因为我们并不知道图像中人脸的尺寸，所以需要生成一个不同大小的图像组成的“金字塔”，扫描其中每一幅图像来寻找可能的人脸。

---

图像金字塔

我们可以这样得到一个图像金字塔：首先，图像经过一个低通滤波器进行平滑处理（这个步骤会使图像变模糊，类似远处的物体没有近处的清晰），然后，对这个平滑处理后的图像进行抽样（一般抽样比例在水平和竖直方向上都为1/2），从而得到一系列缩小的图像。

假设高斯金字塔的第$l$层图像为$G_{l}$，则有：

$$G_{l}\left ( i,j \right )=\sum_{m=-2}^{2}\sum_{n=-2}^{2}\omega \left ( m,n \right )G_{l-1}\left ( 2i+m,2j+n \right )$$ $$\left ( 1\leq l\leq N,0\leq i\leq R_{l},0\leq j\leq C_{l} \right )$$

其中，$N$为高斯金字塔的层数，$R_{l}$和$C_{l}$分别为高斯金字塔第$l$层的行数和列数，$\omega \left ( m,n \right )$是一个二位可拆的5x5窗口函数，其表达式为：

$$\omega =\frac{1}{256}\begin{bmatrix} 1 & 4 & 6 & 4 & 1\\ 4 & 16 & 24 & 16 & 4\\ 6 & 24 & 36 & 24 & 6\\ 4 & 16 & 24 & 16 & 4\\ 1 & 4 & 6 & 4 & 1 \end{bmatrix}=\frac{1}{16}\begin{bmatrix} 1 & 4 & 6 & 4 & 1 \end{bmatrix}\times \frac{1}{16}\begin{bmatrix} 1\\ 4\\ 6\\ 4\\ 1 \end{bmatrix}$$

上式说明，2维窗口的卷积算子，可以写成两个方向上的1维卷积核的乘积。上面卷积形式的公式实际上完成了两个功能：（1）高斯模糊；（2）降维。
按上述步骤生成的$G_{0}$，$G_{1}$，…，$G_{N}$就构成了图像的高斯金字塔，其中$G_{N}$为金字塔的底层（与原图像相同），$G_{N}$为金字塔的顶层。可见高斯金字塔的当前层图像是对其前一层图像进行高斯低通滤波、然后做隔行和隔列的降采样（去除偶数行与偶数列）生成的。其中每一层都是前一层图像大小的1/4。

---

高斯滤波器

本文讨论图像金字塔，怎么说着说着就变成高斯金字塔了呢。事实上，上面所提到的$\omega$其实是一个整数值的高斯核函数，进行了高斯滤波的平滑处理。

高斯滤波

这里先引入两个问题：

1. 为什么要对图像滤波？
   主要有两个目的：（1）消除图像在数字化过程中产生或者混入的噪声；（2）提取图片对象的特征作为图像识别的特征模式。
2. 如何理解滤波器？
   这与电路中的滤波器类似但又不同，在图像处理中，滤波器可以想象成一个包含加权系数的窗口，当使用滤波器去处理图像时，输出就相当于通过这个窗口去看这个图像。

滤波的方式有很多种，而高斯滤波是一种线性平滑滤波，适用于消除高斯噪声。
在图像处理中，高斯滤波一般有两种实现方式，一是用离散化窗口滑窗卷积，另一种通过傅里叶变换。最常见的就是第一种滑窗实现，只有当离散化的窗口非常大，用滑窗计算量非常大（尽管用了可分离滤波器依旧大）的情况下，可能会考虑基于傅里叶变化的实现方法。本文介绍的是滑窗卷积法。

高斯噪声

首先，噪声在图像中常表现为一引起较强视觉效果的孤立像素点或像素块。
而高斯噪声，就是噪声的概率密度函数服从正态分布。

高斯函数

我们首先回顾一下概率论中的高斯函数。
一维高斯分布：$G\left ( x \right )=\frac{1}{\sqrt{2\pi }\sigma }e^{-\frac{x^{2}}{2\sigma ^{2}}}$。

二维高斯分布：$G\left ( x,y \right )=\frac{1}{\sqrt{2\pi }\sigma ^{2}}e^{-\frac{x^{2}+y^{2}}{2\sigma ^{2}}}$

注：$\sigma$越大，高斯函数的高度越小，宽度越大。

如上图所示，正态分布是一种钟形曲线，越接近中心，取值越大，越远离中心，取值越小。
我们只需要将“中心点”作为原点，其他点按照其在正态曲线上的位置，分配权重，就可以得到一个加权平均值。这也是高斯核函数的构造原理。
理论上，高斯分布在所有定义域上都有非负值，这就需要一个无限大的卷积核。实际上，仅需要取均值周围3倍标准差内的值（$3\sigma$准则），以外的部分可以直接去掉。

这里取$\sigma=1.5$，注意，由于要对这9个点计算加权平均，因此必须让它们的权重之和等于1，上图是最终所得的高斯模板。

高斯模糊

模糊处理的过程其实就是卷积的过程，使用上面的高斯模板，对图像的每一个像素进行卷积，就能使图像产生模糊平滑的效果。

上图最左边是原图9个像素点的灰度值，最右边是输出的结果。要注意的是，一次这样的操作实际上只得到了中心点的输出，即所求的加权平均结果为中心点的高斯滤波输出值。

可分离滤波器

如上面图像金字塔一节所述，2维窗口的卷积算子，可以写成两个方向上的1维卷积核的乘积。由于高斯函数可以写成可分离的形式，因此可以采用可分离滤波器实现来加速。所谓的可分离滤波器，就是可以把多维的卷积化成多个一维卷积。具体到二维的高斯滤波，就是指先对行做一维卷积，再对列做一维卷积。这样就可以将计算时间复杂度从$O\left ( M\ast M\ast N\ast N \right )$降到$O\left ( 2\ast M\ast M\ast N \right )$，这里的$M$和$N$分别是图像和滤波器的窗口大小。

性质

1. 旋转对称性

   二维高斯函数具有旋转对称性，即滤波器在各个方向上的平滑程度是相同的。一般一幅图像的边缘方向事先是不知道的，因此，在滤波前是无法确定一个方向上比另一方向上需要更多的平滑。而旋转对称性意味着高斯平滑滤波器在后续边缘检测中不会偏向任一方向。

2. 平滑程度易调

   高斯滤波器宽度（决定着平滑程度）是由参数$\sigma$表征的，而且$\sigma$和平滑程度的关系是非常简单的。$\sigma$越大，高斯滤波器的频带就越宽，平滑程度就越好。通过调节平滑程度参数$\sigma$，可在图像特征过分模糊（过平滑）与平滑图像中由于噪声和细纹理所引起的过多的不希望突变量（欠平滑）之间取得balance。
   此外，高斯函数是单值函数。这表明，高斯滤波器用像素邻域的加权均值来代替该点的像素值，而每一邻域像素点权值是随该点与中心点的距离单调增减的。这一性质很重要，因为边缘是一种图像局部特征，如果平滑运算对离算子中心很远的像素点仍然有很大作用，则平滑运算会使图像失真。

3. 平滑可以层叠

   由性质：两个高斯核的卷积等同于另外一个不同核参数的高斯核卷积。可以推得：不同的高斯核对图像的平滑是连续的。 $$g\left ( \mu ,\sigma _{1} \right )\ast g\left ( \mu ,\sigma _{2} \right )=g\left ( \mu ,\sqrt{\sigma _{1}^{2}+\sigma _{2}^{2}} \right )$$

4. 可分离性

   根据上文分析，由于高斯函数的可分离性，大高斯滤波器可以高效地实现。二维高斯函数卷积可以分两步来进行，首先将图像与一维高斯核进行卷积，然后将卷积结果与方向垂直且函数形式相同一维高斯核再进行卷积。如此，二维高斯滤波的计算量随滤波模板宽度$N$成线性增长而不是成平方增长。

值得一提的是，在Young对生理学的研究中发现，哺乳动物的视网膜和视觉皮层的感受区域可以很好地用4阶以内的高斯微分来建模。

---

拉普拉斯金字塔

由于高斯金字塔用于图片下采样（即减小图片的尺寸），是从金字塔的底层到上层自下而上的。而高斯滤波构造的图像金字塔具有局部极值递性，即图像的特征是在减少的。
那么我们自然而然会想到，需不需要一个自上而下的金字塔用于上采样，和高斯金字塔配合使用。
这里就引入了拉普拉斯金字塔，它可以认为是一个残差金字塔，用来存储下采样后图片与原始图片的差异。其每一层的图像为同一层高斯金字塔的图像减去上一层的图像进行上采样并高斯模糊的结果。

注意，高斯金字塔的下采样是不可逆的，可以这样理解：下采样过程丢失的信息不能通过上采样来完全恢复，即高斯金字塔中任意一张图$G_{i}$先进行下采样得到图$Down(G_{i})$，再进行上采样得到图$Up(Down(G_{i}))$，此时的$Up(Down(G_{i}))$与原本的$G_{i}$是存在差异的。而拉普拉斯金字塔的作用，就是记录高斯金字塔每一层下采样后再上采样得到的结果与下采样前的原图之间差异，其目的是为了能够完整的恢复出每一层的下采样前图像。可以用下面这个公式来简单表述：

$$L_{i}=G_{i}-Up\left ( Down\left ( G_{i} \right ) \right )$$

若将第$i+1$层的高斯金字塔从顶层开始依次加上第$i$层拉普拉斯金子塔，那么就几乎可以复原原来图像（有点绕，建议结合上图体会）。
拉普拉斯的具体构造过程如下：

1. 内插

   将$G_{l}$进行内插（这里是用与降维时相同的滤波核而不是双线性插值），得到放大的图像$G_{l}^{\ast }$，使$G_{l}^{\ast }$的尺寸与$G_{l-1}$的尺寸相同，表示为： $$G_{l}^{\ast }\left ( i,j \right )=4\sum_{m=-2}^{2}\sum_{n=-2}^{2}\omega \left ( m,n \right )G_{l}\left ( \frac{i+m}{2},\frac{j+n}{2} \right )$$ $$\left ( 1\leq l\leq N,0\leq i\leq R_{l},0\leq j\leq C_{l} \right )$$ $$G_{l}\left ( \frac{i+m}{2},\frac{j+n}{2} \right )=\left\{\begin{matrix} G_{l}\left ( \frac{i+m}{2},\frac{j+n}{2} \right ),when\,\frac{i+m}{2},\frac{j+n}{2}\,are\,integers\\ 0,others \end{matrix}\right.$$ 这边的参数就不说明了，与上文相同。需要注意的是，这里的系数取$4$，是因为每次能参与加权的项的权值之和为4/256，这与$\omega$的选取有关。

2. 相减

   原理上文已经说了，接下来我们自上而下构造拉普拉斯金字塔。 $$\left\{\begin{matrix} L_{l}=G_{l}-G_{l+1}^{\ast },when\,0\leq l< N\\ L_{N}=G_{N},when\,l=N \end{matrix}\right.$$

如下图所示，此为文章前面小猫的图像金字塔所生成的拉普拉斯金字塔。不要以为这张图搞错了，细看的话就会发现，除了顶层的图片之外，下面的图片（大尺寸的）中仅有一些零散的点（不是屏幕上的灰尘）和淡淡的线，也就是残差。可以通过Gamma校正使这些残差特征更加清晰。

关于Gamma校正，可以看一看上一篇文章computer-vision笔记：HOG特征，关于图像金字塔和高斯滤波器就说到这里了。