JPEG算法概述及实现
本文将简单介绍下JPEG算法的实现流程，包括图像分割、颜色空间转换、DCT、Quantization、Huffman coding等。
JPEG概述
图像压缩很重要。有这么几种压缩算法：
- JPEG（非常基本的算法，以DCT和quantization为基础，在25比1的压缩比情况下非图像专家很难发现区别）
- JPEG-LS（无损压缩算法，以预测技术为基础，视频的压缩也参照了预测技术）
- JPEG-2000（最新的标准，采用wavelet算法）
JPEG步骤
概述
- 图像分割。分割成8*8的小块
- 颜色空间转换。从RGB到Y,Cb,Cr。
- DCT(Discrete cosine transform)
- Quantization(数据量化，压缩很大一部分是在这里的)
- Huffman coding(对数据进行编码，进一步压缩)
下面，将以我们可爱的高圆圆的照片，来看一下压缩算法。
图像分割
首先，将图像分成8*8的小块，分成这么大是有原因的：
- 太大的话进行矩阵操作复杂度上升
- 太小的话包含的信息太少，在DCT中不能实现很好地压缩
下面，以高圆圆图片左上角为例，取8*8的元素
看，就是这么一小块啦！
颜色空间转换
首先，简单介绍下颜色空间，其就是表达颜色的数学模型。比如最普通的RGB，高圆圆图片的RGB分解如下：
不同的颜色空间有不同的应用场景，RGB颜色空间适合像显示器这样的自发光图案。然而在JPEG压缩算法中，通常转换成YCbCr空间，这里Y表示亮度，Cb和Cr分别表示绿色和红色的色差值。
“色差”这个概念起源于电视行业，最早的电视都是黑白的，那时候传输电视信号只需要传输亮度信号，也就是Y信号即可，彩色电视出现之后，人们在Y信号之外增加了两条色差信号以传输颜色信息，这么做的目的是为了兼容黑白电视机，因为黑白电视只需要处理信号中的Y信号即可。 对于人眼来说，图像中明暗的变化更容易被感知到，这是由于人眼的构造引起的。视网膜上有两种感光细胞，能够感知亮度变化的视杆细胞，以及能够感知颜色的视锥细胞，由于视杆细胞在数量上远大于视锥细胞，所以我们更容易感知到明暗细节。比如说下面这张图 ——摘自参考文献
其转换公式为：
转换后的图像是：
容易看到，RGB颜色空间中，每个颜色尺度上图像的信息都是差不多的。但是在YCbCr中，Y中包含的信息（也就是图形细节）更多，因此后面就可以根据信息的丰富程度做不同的数据压缩处理。比如对Y分量压缩地少，对另外两个分量压缩地多。
DCT
前文中，我们已经得到了8*8的小方块，接着需要对小方块进行DCT变换，DCT变换的实质就是将原来的8*8小块投影到新的空间（也就是下面的图片）。
经过DCT变换后，杂乱的数据变得工整了（这里可以类别矩阵的EIG、SVD分解等）。举个极端的例子，如果每个元素都一样，那么只有左上角（也就是位置（1，1））的方格有值，其他都是零。
DCT变换的公式是： 元素公式：
矩阵公式：
下面还是以前文中的8*8小方块为例（只看Y分量）：
s_y =
118 118 120 122 122 121 125 128
117 118 120 122 123 123 128 132
121 121 121 121 121 121 125 130
124 123 120 118 116 117 122 126
124 122 118 114 113 116 123 127
130 127 122 117 114 117 124 128
138 135 129 122 117 119 123 126
141 138 133 125 120 121 124 126
>> dct2(s_y)
ans =
984.6250 2.7093 24.9920 -8.0736 1.1250 0.8013 -0.7458 0.3843
-12.6773 -25.9635 -12.8348 -0.9374 3.6024 -0.5894 -0.7880 0.6604
15.0671 5.2086 -4.9383 0.0106 0.0280 0.3999 0.5152 0.2320
-8.2712 -3.4118 2.7730 0.3084 -0.1410 0.7677 -0.4452 0.1033
-3.3750 3.0430 -0.1633 0.4712 -0.3750 0.2268 -0.0676 0.1702
0.5963 5.7983 -0.2067 0.0606 0.2430 0.0231 0.0559 -0.5708
0.1181 0.0674 0.0152 -0.0561 0.3943 0.0299 0.1883 0.1514
-0.5753 -0.0467 0.0542 0.2484 -0.0791 -0.3391 0.2906 0.1321
>> idct2(dct2(s_y))
ans =
118.0000 118.0000 120.0000 122.0000 122.0000 121.0000 125.0000 128.0000
117.0000 118.0000 120.0000 122.0000 123.0000 123.0000 128.0000 132.0000
121.0000 121.0000 121.0000 121.0000 121.0000 121.0000 125.0000 130.0000
124.0000 123.0000 120.0000 118.0000 116.0000 117.0000 122.0000 126.0000
124.0000 122.0000 118.0000 114.0000 113.0000 116.0000 123.0000 127.0000
130.0000 127.0000 122.0000 117.0000 114.0000 117.0000 124.0000 128.0000
138.0000 135.0000 129.0000 122.0000 117.0000 119.0000 123.0000 126.0000
141.0000 138.0000 133.0000 125.0000 120.0000 121.0000 124.0000 126.0000可以看到，转换后能量集中于左上角的直流分量（因为这么小的图像一般不会出现大的数值上的跳跃）。
Quantization
前面的变换都是可逆的，也就是数据的信息并没有丢失。 数据的大部分压缩都是在量化这里，有时候保存图片的时候软件会提示你选择保存的精度，其实就是改变量化的程度，或者改变量化系数矩阵乘的倍数。
标准亮度量化表和标准色差量化表见下图：
对于每个单独元素量化的规则是：
T^(u,v)=⌊T(u,v)Q⌋∗Q
\hat{T}(u,v) =\lfloor \frac{T(u,v)}{Q} \rfloor *Q 这么量化的原因是：
有损压缩就是把数据中重要的数据和不重要的数据分开，然后分别处理。DCT系数矩阵中的不同位置的值代表了图像数据中不同频率的分量，这两张表中的数据时人们根据人眼对不不同频率的敏感程度的差别所积累下的经验制定的，一般来说人眼对于低频的分量必高频分量更加敏感，所以两张量化系数矩阵左上角的数值明显小于右下角区域。在实际的压缩过程中，还可以根据需要在这些系数的基础上再乘以一个系数，以使更多或更少的数据变成0。
将原来的8*8小块，根据QY进行量化后，得到的结果是
s_y_dct =
984.6250 2.7093 24.9920 -8.0736 1.1250 0.8013 -0.7458 0.3843
-12.6773 -25.9635 -12.8348 -0.9374 3.6024 -0.5894 -0.7880 0.6604
15.0671 5.2086 -4.9383 0.0106 0.0280 0.3999 0.5152 0.2320
-8.2712 -3.4118 2.7730 0.3084 -0.1410 0.7677 -0.4452 0.1033
-3.3750 3.0430 -0.1633 0.4712 -0.3750 0.2268 -0.0676 0.1702
0.5963 5.7983 -0.2067 0.0606 0.2430 0.0231 0.0559 -0.5708
0.1181 0.0674 0.0152 -0.0561 0.3943 0.0299 0.1883 0.1514
-0.5753 -0.0467 0.0542 0.2484 -0.0791 -0.3391 0.2906 0.1321
uint8(floor(double(s_y_dct)./QY).*QY)
ans =
255 0 20 0 0 0 0 0
0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0可以看到，大部分元素都变成了0。
Huffman coding
哈弗曼几乎是所有压缩算法的基础，它的基本原理是根据元素的使用频率，调整元素的编码长度，以获得更高的压缩比。
原理可以用下面两张图简单介绍：
可以看到，出现概率越高的符号通过哈弗曼编码用的bit位越少，以便实现更好的数据压缩。
通过Huffman coding，在不丢失信息的前提下，我们实现了数据压缩。
JPEG-LS
上面这张图片简单概述了无损压缩的步骤，无损压缩建立在以下的基础上：
- 每个像素之间差别不大，最朴素的方法可以用前一个像素的值来预测后一个像素的值。
- 假设图片有256个像素，分别是0——255。那么只需要记录下第一个值0以及增长率1（并且这种特殊情况下增长率都是1，所以可以极大地减少空间）。
- 同样地，对于普通的一张图片，因为相邻的像素差别不大，所以对增长率进行编码的话效率更高些，这就是JPEG-LS的核心思想——预测增长率。
同样地，对于视频，背景一般不变，所以也可以用类似的思想（MPEG就是用的这种思想方法）实现对视频的压缩。