1. 色彩模型
JPEG 的图片使用的是 YCrCb 颜色模型, 而不是计算机上最常用的 RGB. 关于色彩模型, 这里不多阐述. 只是说明, YCrCb 模型更适合图形压缩. 因为人眼对图片上的亮度 Y 的变化远比色度 C 的变化敏感. 我们完全可以每个点保存一个 8bit 的亮度值, 每 2x2 个点保存一个 Cr Cb 值, 而图象在肉眼中的感觉不会起太大的变化. 所以, 原来用 RGB 模型, 4 个点需要 4x3=12 字节. 而现在仅需要 4+2=6 字节; 平均每个点占 12bit. 当然 JPEG 格式里允许每个点的 C 值都记录下来; 不过 MPEG 里都是按 12bit 一个点来存放的, 我们简写为 YUV12.
[R G B] -> [Y Cb Cr] 转换
-------------------------
(R,G,B 都是 8bit unsigned)
| Y | | 0.299 0.587 0.114 | | R | | 0 |
| Cb | = |- 0.1687 - 0.3313 0.5 | * | G | + |128|
| Cr | | 0.5 - 0.4187 - 0.0813| | B | |128|
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
[Y,Cb,Cr] -> [R,G,B] 转换
-------------------------
R = Y + 1.402 *(Cr-128)
G = Y - 0.34414*(Cb-128) - 0.71414*(Cr-128)
B = Y + 1.772 *(Cb-128)
一般, C 值 (包括 Cb Cr) 应该是一个有符号的数字, 但这里被处理过了, 方法
是加上了 128. JPEG 里的数据都是无符号 8bit 的.
2. DCT (离散余弦变换)
JPEG 里, 要对数据压缩, 先要做一次 DCT 变换. DCT 变换的原理, 涉及到数学知识, 这里我们不必深究. 反正和傅立叶变换(学过高数的都知道) 是差不多了. 经过这个变换, 就把图片里点和点间的规律呈现出来了, 更方便压缩.JPEG 里是对每 8x8 个点为一个单位处理的. 所以如果原始图片的长宽不是 8 的倍数, 都需要先补成 8 的倍数, 好一块块的处理. 另外, 记得刚才我说的 Cr Cb 都是 2x2 记录一次吗? 所以大多数情况, 是要补成 16x16 的整数块.按从左到右, 从上到下的次序排列 (和我们写字的次序一样). JPEG 里是对 Y Cr Cb 分别做 DCT 变换的. 这里进行 DCT 变换的 Y, Cr, Cb 值的范围都是 -128~127. (Y 被减去 128)
JPEG 编码时使用的是 Forward DCT (FDCT) 解码时使用的 Inverse DCT (IDCT)
下面给出公式:
FDCT:
7 7 2*x+1 2*y+1
F(u,v) = alpha(u)*alpha(v)* sum sum f(x,y) * cos (------- *u*PI)* cos (------ *v*PI)
x=0 y=0 16 16
u,v = 0,1,...,7
{ 1/sqrt(8) (u==0)
alpha(u) = {
{ 1/2 (u!=0)
IDCT:
7 7 2*x+1 2*y+1
f(x,y) = sum sum alpha(u)*alpha(v)*F(u,v)*cos (------- *u*PI)* cos (------ *v*PI)
u=0 v=0 16 16
x,y=0,1...7
这个步骤很花时间, 另外有种 AA&N 优化算法, 大家可以去 inet 自己找一下. 在Intel 主页上可以找到 AA&N IDCT 的 MMX 优化代码. ( Intel 主页上的代码, 输入数据为12.4 的定点数, 输入矩阵需要转置 90 度)
3. 重排列 DCT 结果
DCT 将一个 8x8 的数组变换成另一个 8x8 的数组. 但是内存里所有数据都是线形存放的, 如果我们一行行的存放这 64 个数字, 每行的结尾的点和下行开始的点就 没有什么关系, 所以 JPEG 规定按如下次序整理 64 个数字.
0, 1, 5, 6,14,15,27,28,
2, 4, 7,13,16,26,29,42,
3, 8,12,17,25,30,41,43,
9,11,18,24,31,40,44,53,
10,19,23,32,39,45,52,54,
20,22,33,38,46,51,55,60,
21,34,37,47,50,56,59,61,
35,36,48,49,57,58,62,63
这样数列里的相邻点在图片上也是相邻的了.
4. 量化
对于前面得到的 64 个空间频率振幅值, 我们将对它们作幅度分层量化操作.方法就是分别除以量化表里对应值并四舍五入.
for (i = 0 ; i<=63; i++ )
vector[i] = (int) (vector[i] / quantization_table[i] + 0.5)
下面有张 JPEG 标准量化表. (按上面同样的弯曲次序排列)
16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 62
18 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
这张表依据心理视觉阀制作, 对 8bit 的亮度和色度的图象的处理效果不错.当然我们可以使用任意的量化表. 量化表是定义在 jpeg 的 DQT 标记后. 一般为 Y 值定义一个, 为 C 值定义一个.
量化表是控制 JPEG 压缩比的关键. 这个步骤除掉了一些高频量, 损失了很高细节. 但事实上人眼对高空间频率远没有低频敏感.所以处理后的视觉损失很小.另一个重要原因是所有的图片的点与点之间会有一个色彩过渡的过程. 大量的图象信息被包含在低空间频率中. 经过量化处理后, 在高空间频率段, 将出现大量连续的零.
注意, 量化后的数据有可能超过 2 byte 有符号整数的处理范围.
5. 0 RLE 编码
现在我们矢量中有许多连续的 0. 我们可以使用 RLE 来压缩掉这些 0. 这里我们将跳过第一个矢量 (后面将解释为什么) 因为它的编码比较特别. 假设有一组矢量(64 个的后 63 个) 是
57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0, 0 , 0 ,0 , 0,..,0
经过 RLE 压缩后就是
(0,57) ; (0,45) ; (4,23) ; (1,-30) ; (0,-16) ; (2,1) ; EOB
EOB 是一个结束标记, 表示后面都是 0 了. 实际上, 我们用 (0,0) 表示 EOB,
但是, 如果这组数字不以 0 结束, 那么就不需要 EOB.
另外需要注意的是, 由于后面 huffman 编码的要求, 每组数字前一个表示 0 的
数量的必须是 4 bit, 就是说, 只能是 0~15, 所以, 如果有这么一组数字:
57, 十八个0, 3, 0, 0, 0, 0, 2, 三十三个0, 895, EOB
我们实际这样编码:
(0,57) ; (15,0) (2,3) ; (4,2) ; (15,0) (15,0) (1,895) , (0,0)
注意 (15,0) 表示了 16 个连续的 0.
6. 范式 Huffman 编码
为了提高储存效率, JPEG 里并不直接保存数值, 而是将数值按位数分成 16 组:
数值 组 实际保存值
0 0 -
-1,1 1 0,1
-3,-2,2,3 2 00,01,10,11
-7,-6,-5,-4,4,5,6,7 3 000,001,010,011,100,101,110,111
-15,..,-8,8,..,15 4 0000,..,0111,1000,..,1111
-31,..,-16,16,..,31 5 00000,..,01111,10000,..,11111
-63,..,-32,32,..,63 6 .
-127,..,-64,64,..,127 7 .
-255,..,-128,128,..,255 8 .
-511,..,-256,256,..,511 9 .
-1023,..,-512,512,..,1023 10 .
-2047,..,-1024,1024,..,2047 11 .
-4095,..,-2048,2048,..,4095 12 .
-8191,..,-4096,4096,..,8191 13 .
-16383,..,-8192,8192,..,16383 14 .
-32767,..,-16384,16384,..,32767 15 .
还是来看前面的例子:
(0,57) ; (0,45) ; (4,23) ; (1,-30) ; (0,-8) ; (2,1) ; (0,0)
只处理每对数右边的那个:
57 是第 6 组的, 实际保存值为 111001 , 所以被编码为 (6,111001)
45 , 同样的操作, 编码为 (6,101101)
23 -> (5,10111)
-30 -> (5,00001)
-8 -> (4,0111)
1 -> (1,1)
前面的那串数字就变成了:
(0,6), 111001 ; (0,6), 101101 ; (4,5), 10111; (1,5), 00001; (0,4) , 0111 ;
(2,1), 1 ; (0,0)
括号里的数值正好合成一个字节. 后面被编码的数字表示范围是 -32767..32767.合成的字节里, 高 4 位是前续 0 的个数, 低 4 位描述了后面数字的位数.
继续刚才的例子, 如果 06 的 huffman 编码为 111000 ( 06 对应 111000 为查表所得. jpeg 文件里保存了压缩时所产生的 huffman 表, 将 0~255 这 256 个 8 bits 定长数字, 对应成 1~16 bits 的不定长数值. 出现频率高的数字小于 8bits, 频率低的大于8bits,从而使整个的数据长度降低, jpeg 实际使用的是范式 Huffman 编码(Canonical Huffman Code)关于范式 huffman 编码的详细介绍, 请查阅相关资料 )
69 = (4,5) --- 1111111110011001 ( 注: 69=4*16+5=0x45 )
21 = (1,5) --- 11111110110
4 = (0,4) --- 1011
33 = (2,1) --- 11011
0 = EOB = (0,0) --- 1010
那么最后对于前面的例子表示的 63 个系数 (记得我们将第一个跳过了吗?) 按位流
写入 JPG 文件中就是这样的:
111000 111001 111000 101101 1111111110011001 10111 11111110110 00001
1011 0111 11011 1 1010
7. DC 的编码
记得刚才我们跳过了每组 64 个数据的第一个吧, DC 就是指的这个数字 (后面 63 个简称 AC) 代入前面的 FDCT 公式可以得到
c(0,0) 7 7
DC = F(0,0) = --------- * sum sum f(x,y) * cos 0 * cos 0 其中 c(0,0) = 1/2
4 x=0 y=0
1 7 7
= --- * sum sum f(x,y)
8 x=0 y=0
即一块图象样本的平均值. 就是说, 它包含了原始 8x8 图象块里的很多能量. (通常会得到一个很大的数值)
JPEG 的作者指出连续块的 DC 率之间有很紧密的联系, 因此他们决定对 8x8 块的DC 值的差别进行编码. (Y, Cb, Cr 分别有自己的 DC)
Diff = DC(i) - DC(i-1)
所以这一块的 DC(i) 就是: DC(i) = DC(i-1) + Diff
JPG 从 0 开始对 DC 编码, 所以 DC(0)=0. 然后再将当前 Diff 值加在上一个值上得到当前值.
下面再来看看上面那个例子: (记住我们保存的 DC 是和上一块 DC 的差值 Diff)
例如上面例子中, Diff 是 -511, 就编码成
(9, 000000000)
如果 9 的 Huffman 编码是 1111110 (在 JPG 文件中, 一般有两个 Huffman 表, 一个是 DC 用, 一个是 AC 用) 那么在 JPG 文件中, DC 的 2 进制表示为
1111110 000000000
它将放在 63 个 AC 的前面, 上面上个例子的最终 BIT 流如下:
1111110 000000000 111000 111001 111000 101101 1111111110011001 10111
11111110110 00001 1011 0111 11011 1 1010
二、解码过程简述
8. 一个数据单元 Y 的解码 (其余类同)
在整个图片解码的开始, 你需要先初始化 DC 值为 0.
1) 先解码 DC:
a) 取得一个 Huffman 码 (使用 Huffman DC 表)
b) Huffman解码, 看看后面的数据位数 N
c) 取得 N 位, 计算 Diff 值
d) DC + = Diff
e) 写入 DC 值: " vector[0]=DC "
2) 解码 63 个 AC:
------- 循环处理每个 AC 直到 EOB 或者处理到 64 个 AC
a) 取得一个 Huffman 码 (使用 Huffman AC 表)
b) Huffman 解码, 得到 (前面 0 数量, 组号)
[记住: 如果是(0,0) 就是 EOB 了]
c) 取得 N 位(组号) 计算 AC
d) 写入相应数量的 0
e) 接下来写入 AC