从JPEG开始学习的图像处理

JPEG常用的简化编码格式为JFIF(JPEG File Interchange Format)，在编码时，它的流程一般为：

1. 颜色空间变换 $ RGB \rightarrow Y’C_BC_R $
2. 对色度降采样
3. 分块进行离散余弦变换DCT
4. 量化减少高频信息
5. 熵编码

颜色空间变换

$Y’C_BC_R$（256 level）空间中，$Y’$表示像素的亮度，$C_B$和$C_R$分别表示红色和蓝色分量，这种表示方法常用于数据彩色电视和DVD中。

具体从RGB向该空间的转换方式(ITU-R BT.601)如下：

$$\begin{equation}\begin{aligned} Y &= 0.299 R + 0.587 G + 0.114 B \\ Cb &= - 0.1687 R - 0.3313 G + 0.5 B + 128 \\ Cr &= 0.5 R - 0.4187 G - 0.0813 B + 128 \end{aligned}\end{equation}$$

反向转换方式如下：

$$\begin{equation}\begin{aligned} R &= Y + 1.402 (Cr-128) \\ G &= Y - 0.34414 (Cb-128) - 0.71414 (Cr-128) \\ B &= Y + 1.772 (Cb-128) \end{aligned}\end{equation}$$

降采样

我们使用该YCbCr系统的原因是人眼对色度的敏感度不及对亮度的敏感度，在压缩影像中，以4:2:2 $Y’CbCr$作例，它只需$R’G’B’$（4:4:4）三分之二的带宽。带宽的减少在肉眼上几乎没有影像上差别。

具体来说4:2:2 $Y’CbCr$中Y信号的采样频率为13.5MHz，而其他两个信号的采样频率为6.75MHz，缺失的色度信息通过内插值或复制前一色度来补全。

这里的比例（以J:a:b为例）更具体的解释如下：

• 在一个可见区域内有J个像素宽且高为2个像素
• a：在第一行J个像素中色度采样次数。
• b：在第一行与第二行之间色度采样变化的次数（4:4:1和4:2:1不符合该规则）。
• Alpha：偶尔会出现，一般与J相等。

降采样示例，容易看出4:4:4没有降采样

分块离散余弦变换

每个通道都会被分块，分块后的最小单位称为Minimum Coded Unit(MCU，在视频压缩中也被称作macroblock)，具体来说各比例与分块方法的对应关系如下：

• 4:4:4 —— 8 x 8
• 4:2:2 —— 16 x 8
• 4:2:0 —— 16 x 16

如果出现了非整数倍的大小，需要向残缺的最小单元填充元素，通常填充与边缘元素相同的元素，很显然这样并不能完全消除瑕疵。

接下来对每个最小单元进行离散余弦变换，我们使用normalized, two-dimensional type-II discrete cosine transform（逆变换为type-III DCT），以下面的8 x 8 8-bit 矩阵为例：

首先将整个矩阵中心化，让中值变为0，在如上的8-bit图中，即把每个数减去128：

再计算离散余弦系数，8 x 8矩阵的计算公式如下：

$$\begin{equation} G_{u,v}= \frac{1}{4}\alpha(u)\alpha(v)\sum_{x=0}^7\sum_{y=0}^7g_{x,y}\cos[\frac{(2x+1)u\pi}{16}]\cos[\frac{(2y+1)v\pi}{16}] \end{equation}$$

上式中，

• $u,v$分别为水平、竖直方向的空间频率，范围为$[0, 8)$。
• $\begin{aligned}\alpha(u)=\begin{cases}\frac{1}{\sqrt{2}} &if\;u=0 \\ 1 &otherwise \end{cases}\end{aligned}$，用于将变换正交化。
• $g_{x,y}$为该坐标的像素值。
• $G_{u,v}$即该坐标的DCT系数。

可以看到左上角的低频分量、尤其是直流分量（坐标（0，0））相较右下角的高频分量的DCT系数大很多，这意味着大部分信息其实为低频信息，我们将会在量化步骤中除去人眼难以察觉的高频分量。

此外，DCT计算会暂时性地增大数据存储空间，因为原本的8-bit信息被扩张为表示浮点数的11或更多bit（通常为16-bit）。这一点通常不被重视，因为在同一时间内通常只有图片的一小部分被进行DCT。

离散余弦变换的拓展理解

离散傅里叶变换(DFT)系数的一维公式：
$$ \begin{aligned} \hat{x}[k] =\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N}nk} =\sum_{n=0}^{N-1}x[n]\cos(\frac{2\pi}{N}nk)-j\sin(\frac{2\pi}{N}nk) \end{aligned} $$

DCT的一维公式：
$$ F_k=\sum_{n=0}^{N-1}f_n\cos(\frac{\pi k(z+\frac{1}{2})}{N}) \
f_n = \sum_{n=0}^{N-1}x[n]\cos(\frac{\pi k(z+\frac{1}{2})}{N})$$

通过比较公式我们可以发现，DCT的信号周期约为DFT的两倍，且经过了半整数的采样位移，并且默认源函数为实偶函数，因此结果中只有余弦项。

量化

在图像处理领域，量化是一种将一定范围的值压缩成单个离散值的有损压缩技巧，用这种方法通常能减少需要表示的符号。

常见的压缩应用有：

• 颜色量化——减少用来表示图片的颜色数量
• 灰度量化——减少灰度等级数，计算公式：

  

  其中$Q(x)$是量化后的值，x是原始值，$\delta$是量化区间的大小，此处用区间的中间值表示该区间的所有量化值。
• 图像压缩中的频率量化，我们在下面主要介绍这种量化方式。

我们使用量化矩阵来控制DCT处理后的矩阵中的每个值，许多编码器允许自定义量化矩阵，在JPEG标准中常用的50%质量量化矩阵如下图：

接着进行如下计算：

$$\begin{equation} B_{j,k}=round(\frac{G_{j,k}}{Q_{j,k}}) for\;j=0,1,2,...,7; k=0,1,2,...,7 \end{equation}$$

可以注意到结果中高频分量大部分都被量化为0，这一部分是因为高频分量幅值小，另一部分原因是量化矩阵对高频分量的削减更狠，这是因为人眼对亮度的高频分量的强度差异感受较弱。

增加或减少量化阶段使用的除数可以改变最终的压缩率，在存储精度足够高的情况下，量化是JFIF中唯一有损的步骤。

熵编码

JPEG的熵编码采用“之字形”(zigzag)顺序、游程编码(run-length encoding,RLE)算法和哈夫曼编码。JPEG也可以使用压缩率稍好的算术编码(arithmetic coding)来替代哈夫曼编码，但前者编解码时间更长、使用需要专利费且压缩体积通常只比后者小5-7%。

编码时，坐标为(0,0)的量化DC系数被编码为与上一个块相同坐标的系数的差，且与下面的游程编码方式不同，DC编码通常不含RUNLENGTH，其余坐标则不使用这种差分预测。

使用了之字形排列的实例

这种编码方式称为基线顺序(sequential)编码，它一次对单个块的系数进行编码（以锯齿状方式），JPEG 标准提供了通用的 Huffman 表；编码器还可以选择生成针对正在编码的图像中的实际频率分布进行优化的 Huffman 表。

游程编码的工作原理是检查每个非零 AC 系数x，并确定前一个 AC 系数之前有多少个零。利用此信息，可以创建两个符号：

符号1	符号2
(RUNLENGTH, SIZE)	AMPLITUDE

符号1通常占一个字节，其中符号1中的两个元素各占4位信息。高位表示该系数前零的数量，低位表示对x的值进行编码所需的位数。符号2即x的位表示。JPEG定义了两个特殊的霍夫曼码字。一个用于在剩余系数为零时提前结束序列（称为“块结束”或“EOB”）即(0, 0)，另一个用于在零的运行超过 15 个之前达到非零 AC 系数。在这种情况下，在给定的非零 AC 系数之前遇到 16 个零，符号 1被“特殊”编码为：(15, 0)(0)。

因此，前面的序列会被编码成：
(0, 2)(-3); (1, 2)(-3); (0, 2)(-2); (0, 3)(-6); (0, 2)(2); (0, 3)(-4); (0, 1)(1); (0, 2)(-3); (0, 1)(1); (0, 1)(1);
(0, 3)(5); (0, 1)(1); (0, 2)(2); (0, 1)(-1); (0, 1)(1); (0, 1)(-1); (0, 2)(2); (5, 1)(-1); (0, 1)(-1); (0, 0);

上面各项的符号1可以通过查表得到唯一的哈夫曼编码表示（标准JPEG表如下图所示，亮度和色度分量有不同的表，DC系数与AC系数的表也不同），重复的符号1则在查表结果的基础上加上重复次数；符号2（幅值）则直接以二进制格式接在符号1的哈夫曼编码后。示例：

符号1：(run_length=2, size=3) → Huffman码字 1101（假设）。
符号2：幅值5 → 二进制 101（3位）。
完整编码：1101 101。

亮度的DC系数表

亮度的AC系数表（节选）

此外baseline JPEG还可以支持渐进(progressive)编码，渐进编码一次性对所有块中位置相似的一批系数进行编码（称为扫描），然后对下一批所有块的系数进行编码，依此类推。例如，如果将图像分成 N 个 8×8 块$B_0,B_1,…,B_{N-1}$，然后在第一次扫描中采用 3 扫描逐行编码对直流分量$B_i(0,0)$进行编码，在第二次扫描中可以对更多AC分量进行编码，如$B_i(0,1)$到$B_i(1,1)$，则编码顺序为：$B_0(0,1),B_0(1,0),B_0(1,1),B_1(0,1),B_1(1,0),…,B_{N-1}(2,0),B_{N-1}(1,1)$，接着继续后面的扫描。基线渐进式JPEG 编码通常比基线顺序式JPEG 提供更好的压缩率，因为它能够在每次“扫描”或“通过”（包括相似位置的系数）时使用针对不同频率量身定制的不同霍夫曼表，尽管差异不是太大。

关于哈夫曼编码的拓展知识

根据香农的信源编码理论，给定分布的香农熵就是理论上表示该分布中所有符号的最少bit数，在下面的表中可以看出哈夫曼编码的bit期望非常接近其香农熵。JPEG中哈夫曼编码表构建的具体细节可看专利书，内容有点复杂，看不懂了(Q w Q)。

哈夫曼编码的实例，主要关注它与信息论的联系

解码

1. 还原DC系数（即$S_{00}$）
2. 逐元素乘以量化矩阵（还原不了编码时的精度了）
3. 逆离散余弦变换： $$f_{x,y}=\frac{1}{4}\sum_{u=0}^7\sum_{v=0}^7\alpha(u)\alpha(v)F_{u,v}\cos[\frac{(2x+1)u\pi}{16}]\cos[\frac{(2y+1)v\pi}{16}]$$ 符号解释：
   • $x, y$分别是还原后像素的坐标；
   • $\alpha(u)$与DCT相同；
   • $F_{u,v}$是逆变换前矩阵的有损DCT系数；
   • $f_{x,y}$即逆变换后的值；
     再将逆变换后的值约到整数后加128，对于超出$[0,255]$范围的值则要做修剪处理；

为了比较压缩前后的质量，可以计算残差矩阵（$original - uncompressed$），也可以用平均绝对值残差来衡量压缩还原后的图片质量。

更多信息如已实现JPEG的库、其他JPEG版本等请见英文wiki。