Image and Video Processing chapter2

数字图像处理 chapter2-Image Compression

图像为什么可以被压缩？

最主要的一个原因就是冗余，它包含三个方面

• 编码冗余：比如一个图中只有 4 种颜色，对每个颜色却使用 8bit 进行编码
• 空间冗余：比如图中有大量重复部分，对于这部分如果重复存储而不做任何压缩，图片的体积会变得非常大。
• 无关：比如一张纯色图，只有一个值就足够了，但其中却出现了许多类似于噪音的值，这时，这些值纯色图来说就是噪音了。

图像压缩的流程

JPEG 压缩

JPEG 整个压缩过程基本上是遵循这个步骤：

1. 把数据分为“重要部分”和“不重要部分”
2. 滤掉不重要的部分
3. 保存

步骤一：图像分割

JPEG 算法的第一步，图像被分割成大小为 8X8 的小块

步骤二：颜色空间转换 RGB->YCbCr

在 JPEG 压缩算法中，需要把图案转换成为 YCbCr 模型，这里的 Y 表示亮度 (Luminance)，Cb 和 Cr 分别表示绿色和红色的“色差值”。

“色差”这个概念起源于电视行业，最早的电视都是黑白的，那时候传输电视信号只需要传输亮度信号，也就是 Y 信号即可，彩色电视出现之后，人们在 Y 信号之外增加了两条色差信号以传输颜色信息，这么做的目的是为了兼容黑白电视机，因为黑白电视只需要处理信号中的 Y 信号即可。

有损压缩首先要做的事情就是“把重要的信息和不重要的信息分开”，YCbCr 恰好能做到这一点。对于人眼来说，图像中明暗的变化更容易被感知到，这是由于人眼的构造引起的

步骤四：DCT 变换

K-L变换：将能量集中于左上方，效果好，但依赖于图像本身

DCT变换：变换有一个固定的矩阵，有固定的系数，所以是通用的

DCT变换的数学原理

变换用连续的图像表达式 f(x,y) 来解释，我们有一张图像，记之为 f(x,y)，新的变换域记为 T(u,v) （T(u，v)为变换系数）

两个函数 r 和 s ,其中的 r(x,y,u,v)和s(x,y,u,v)也被称作是基函数或者是基图像。理想化情况下r和s会使均方误差极小。对于K-L变换，这些系数r(x,y,u,v)完全依赖于图像，不仅依赖于所取的位置，还依赖于你图像上实际的灰度值。所以我们使用DCT来代替，DCT中 r 和 s 为：

我们是在试着将 n×n 大小的小图像，分解成这些基函数的线性组合。如果是纯色图像，这里的T(u,v) 只要 u和v 的值都为0即可。如果图像中变化频繁，那么就需要一些系数，如T(3,3)。这样，每一个 T(u,v)，都会被描述为有多少这样的部分组成，现在我们已经用此类图像的线性组合来表示 n × n 的图像了。

DCT变换的具体例子

在 JPEG 压缩过程中，经过颜色空间的转换，每一个 8X8 的图像块，在数据上表现为 3 个 8X8 的矩阵，紧接着我们对这三个矩阵做一个二维的 DCT 转换，由于图像本身的连贯性，一个 8X8 的图像中的数值一般不会出现大的跳跃，经过 DCT 转换会有类似的效果，左上角的直流分量保存了一个大的数值，其他分量都接近于 0

可以看到，数据经过 DCT 变化后，被明显分成了直流分量和交流分量两部分，为后面的进一步压缩起到了充分的铺垫作用，可以说是整个 JPEG 中最重要的一步，后面我们会介绍数据量化。

由于已经明确每次进行离散余弦变化的矩阵大小为8*8，故这里不再采用上述方法进行离散余弦变换，而是利用DCT变换矩阵实现DCT变换以降低运算量。

(使用 Image Processing Toolbox™ 软件有两种计算 DCT 的方法。第一种方法是使用 dct2 函数。dct2 使用基于 FFT 的算法对大型输入实现快速计算。第二种方法是使用 DCT 变换矩阵，该矩阵由函数 dctmtx 返回，对于小型方阵输入（如 8×8 或 16×16）可能更高效)

为什么选择离散余弦变换？

第一，其实在一些特定情况下，离散余弦变换完全等同于卡洛南-洛伊变换。这些特例中的图像，其像素排列符合马尔可夫链，即每个像素都以一种特殊的形式，依赖于相邻像素，然后相邻像素也是如此。 这就是所谓的一阶马尔可夫图像源（ Markovian）。如果可以假设一张这样的图像，就可以证明卡洛南-洛伊变换最终就是离散余弦变换

第二，为什么不用傅里叶变换之类的方法呢？ 因为离散傅里叶变换对周期性有一个潜在的假设，假设图像如下图一样在自我重复。这个假设适用于每个方向，以及整个二维平面。也就是说，我们需要一个小块中第一个像素，与下一个小块中的第一个像素（n个之后的像素）完全相同，这就是潜在的假设。但是这种假设存在的可能性很低。

然而，离散余弦变换对周期性所作的假设是不同的，离散余弦变换假设边界处有镜面对称，如下图，即是说图像是在重复，但是翻折了。这个假设是说，假定这里的像素与相邻的这个像素类似，不是说像素与八个像素之后的那一个相同，而是与紧接着它的那个像素相同。这个假设更合理，这就是我们选用离散余弦变换的两个原因。其一是对一类图像而言，进行离散余弦变换就是在进行卡洛南-洛伊变换。其二是周期性，在我们从 n × n 或 8 × 8 小块开始处理图像时，离散余弦变换对周期性的假设更为实用。

步骤五:量化

经过颜色空间转换和离散余弦变换，每一个8X8的图像块都变成了三个8X8的浮点数矩阵，分别表示Y,Cr,Cb数据。 我们的问题是，在可以损失一部分精度的情况下，如何用更少的空间存储这些浮点数？答案是使用量子化（ Quantization ），简称量化

在JPEG中采用的均匀量化的方法，有落在某一区间的数，都可以用这个区间对应的纵坐标来表示，我们之后要开始哈夫曼编码，我们现在把一个区间上的所有点用一个数来代替，就可以增大这个数出现的概率

其中G是我们需要处理的图像矩阵，Q称作量化系数矩阵（Quantization matrices），JPEG算法提供了两张标准的量化系数矩阵，分别用于处理亮度数据Y和色差数据Cr以及Cb。

比如上面数据，以左上角的-415.38为例，对应的量子化系数是16，那么round(-415.38/16)=round(-25.96125)=-26。

矩阵的量化还有最后一步要做，就是把量化后的二维矩阵转变成一个一维数组，以方便后面的霍夫曼压缩，但在做这个顺序转换时，需要按照一个特定的取值顺序。

这么做的目的只有一个，就是尽可能把0放在一起，由于0大部分集中在右下角，所以才去这种由左上角到右下角的顺序。

后面的工作就是对这个数组进行再一次的哈夫曼压缩，已得到最终的压缩数据

无损预测压缩

这么做的目的只有一个，就是尽可能把0放在一起，由于0大部分集中在右下角，所以才去这种由左上角到右下角的顺序。

后面的工作就是对这个数组进行再一次的哈夫曼压缩，已得到最终的压缩数据

感谢以下博客的帮助：

JPEG算法解密（二）

数字图像处理（冈萨雷斯第三版）学习笔记