赵工的个人空间

JPEG(joint photographic experts group)是一个由ISO和IEC两个组织机构联合组成的一个专家组，负责制定静态的数字图像压缩编码标准，这个专家组开发的算法称为JPEG算法。

1. JPEG算法的基本步骤：

基本JPEG算法操作分成三个步骤：
⑴使用离散余弦变换把空间域表示的图像变换成频率域表示的图。是把8x8像素矩阵变成8x8的频率矩阵
⑵使用量化表对以DCT系数进行量化。量化表是根据人的视觉和压缩图像类型的特点进行优化的量化系数矩阵，滤掉那些总体上对图像不重要的部分。这一步是JPEG的有损压缩，量化矩阵的值越高，从图像中丢失的信息就越多，从而压缩率越高，同时图像的质量就越差。在JPEG压缩时，可以选择一个量化因子，这个因子的值决定了量化矩阵中的数值。理想的量化因子要在压缩率和图像质量间达到平衡，所以对不同的图像要选择不同的量化因子。
⑶对量化后的频率矩阵使用无损压缩编码。先使用差分脉冲编码调制DPCM对直流系数进行编码，使用行程长度编码RLE对交流系数进行编码，对这些编码采用霍夫曼可变字长编码器进行编码。
解压缩的过程与压缩过程相反。

2. JPEG压缩过程分析：

JPEG压缩算法的过程有：色彩系统变换，离散余弦变换、量化、Z字形编码、游程编码、Huffman编码。

1）色彩系统变换：
JPEG使用的是YCrCb颜色模型。YCrCb模型中，Y代表明度，Cr、Cb代表色调，每个点保存8bit的Y值，2x2个点保存一个CrCb值，平均每个点占12bit，而RGB模型的每个点需要3个字节共24bit，未编码就具有50%压缩率，所以YCrCb颜色模型更适合图像压缩。常用的YCrCb模型有YUV422和YUV411两种，使用YUV422有33%压缩率。
YCrCb模型分量可以直接用8bit表示的RGB分量计算得到：

一般情况下，Cb、Cr应为一个有符号的数字，这里加上了128。
从YCrCb模型转换成RGB算法为：

2）离散余弦变换：
离散余弦变换DCT是将一组光强数据转化为频率数据。JPEG将整个图像分成8x8的图像块，然后对YCrCb分量分别做DCT变换，如果原始图像的长宽不是8的倍数需要补成8的倍数，因为Cr、Cb都是2x2记录一次，所以大多数情况下要补成16x16的块。图像块按从左到右、从上到下次序排列。
把8x8的图像作为两维离散余弦变换DCT的输入，输出为8x8变换系数，这些系数都有明确的物理意义。u代表水平像素号，v代表垂直像素号，当u=0、v=0时，F(0,0)是原64个样值的平均，相当于直流分量；随着u、v值增加，相应系数分别代表逐步增加的水平空间频率分量和垂直空间频率分量的大小。在8x8图像块中，像素值一般变化较平缓，因此具有较低的空间频率。使用二维8x8离散余弦变换可以将图像块的能量集中在极少数几个系数上，其他系数的值与这些系数相比，绝对值要小得多，便于后续压缩处理。
DCT变换使用公式：

逆变换公式：

公式中，i、j代表图像数据矩阵内某个数值的坐标；f(i,j)代表图像数据矩阵内的(i,j)位置上的像素值；u、v代表DCT变换后矩阵内某个数值的坐标位置；F(u,v)代表矩阵内的(u,v)位置上DCT变换后的频率系数。u=0且v=0时，c(u)c(v)=1/1.414，u>0或v>0时，c(u)c(v)=1。
经过DCT变换后的矩阵数据为频率系数，这些系数以F(0,0)的值最大，称为DC，其余的63个频率系数则多半是一些接近0的正负浮点数，都称为AC。经DCT变换后，系数大多数集中在左上角，即低频分量区。

3）量化：
DCT本身并不能进行压缩，64个样值仍然得到64个系数。而且经DCT变换后，比特数增加了，直流分量的最大值是256的64/8倍，范围为0~2047，交流分量范围是-1024~1023。量化，是对经过DCT变换后的频率系数进行量化，使其按比例缩小，并取最接近的整数值，作用是在保证一定质量前提下丢弃图像中对视觉效果影响不大的信息。这一步是图像质量下降的最主要原因。
JPEG标准中采用线性均匀量化器，对64个DCT系数除以量化步长并四舍五入取整，量化步长由量化表决定。量化表为8x8矩阵，与DCT变换系数一一对应，亮度分量和彩色分量使用不同的量化表。量化表一般由用户规定，JPEG标准给出了参考值，其中的元素为1到255之间的整数，其值为对应DCT系数的量化步长。DCT变换系数除以量化表中对应位置的量化步长并舍入小数部分后，多数变为0，从而达到压缩的目的。
按人眼的生理特性设置的量化表，对低频分量采用较细的量化，对高频分量使用更粗的量化，这会使大多数高频分量的系数变为零。JPEG使用均匀量化器。
    
上述的亮度和色度量化表的数值对CCIR601标准电视图像已经是最佳的。也可以用自定义的量化表替换它们，量化表可以在JPEG文件的DQT标记之后定义，一般Y值定义一个，C值定义一个。量化表是控制JPEG压缩比的关键，这个步骤除掉了一些高频分量，损失了细节，因为人眼对高空间频率远没有低频敏感，所以处理后的视觉损失很小。

4）Z字形编码：
量化后的系数要重新编排，目的是为了增加连续的0系数的个数，也就是0的游程长度。

量化后系数的读取顺序按Z字形排列，这样读出后出现连续0的机会比较多，尤其在最后。如果都是0，在读到最后一个数后只要给出块结束EOB码就可以结束输出，节省了很多码率。读出后，8x8矩阵变成1x64的矢量，频率较低的系数放在矢量的顶部。

5）游程编码：
64个变换数经量化后，最上角系数是直流分量DC系数，也即空间域中64个图像采样值的均值。相邻8x8块之间的DC系数之间一般有很强的相关性，JPEG标准对DC系数采用DPCM编码，即对相邻像素块之间的系数差值进行编码。其余63个交流分量AC系数使用游程编码，从左上角开始沿对角线方向，以Z字形进行扫描，直至结束。
①直流系数的编码：
使用差分脉冲编码调制DPCM对直流系数DC进行编码。8x8图像块经过DCT变换之后，得到的DC直流系数数值比较大，而且相邻8x8图像块的DC系数值变化不大。根据这个特点，JPEG使用了DPCM技术，对相邻图像块之间量化DC系数的差值进行编码。
②交流系数的编码：
使用游程编码RLE对交流系数AC进行编码。量化AC系数的特点是1x64矢量中包含有许多0系数，并且很多0是连续的，因此使用简单的游程编码。JPEG使用了一个字节的高4位表示连续的0个数，而使用它的低4位来表示编码下一个非0系数所需要的位数，跟在它后面的是量化AC系数的数值。跳过第一个DC矢量，假设其后的63个数值为：

经过RLE压缩后为：

EOB是一个结束标记，表示后面都是0了，实际上用(0,0)表示EOB。但是，如果这组数据不以0结束，就不能使用EOB。比如，用(15,0)表示16个连续的0。

6）霍夫曼编码：
Huffman编码器可以使用简单的查找表方法进行编码。压缩数据符号时，霍夫曼编码器对出现频度比较高的符号分配比较短的代码，而对出现频度较低的符号分配比较长的代码。这种可变长度的霍夫曼码表可以事先进行定义。
编码时，每个矩阵数据的DC值与63个AC值，将分别使用不同的霍夫曼编码表，而亮度与色度也需要不同的霍夫曼码表，所以需要4个编码表。
①DC编码：
JPEG指出连续块的DC率之间有紧密联系，因此对8x8块的DC值的差别进行编码，Y、Cb、Cr分别有自己的DC值。Diff=DC(i)-DC(i-1)。
DC是采用差值编码，也就是在同一个图像分量中取得每个DC值与前一个DC值的差值来编码。DC采用DPCM编码的原因是由于在连续色调的图像中，其差值多半比原值小，对差值进行编码所需的位数会比对原值进行编码所需的位数少很多。如果差值为负值，就使用补码表示。差值所需位数与差值内容对照表为：

在差值前端另外加入一些差值的霍夫曼值，例如亮度差值为5(101)的位数为3，则霍夫曼码值应为100，二者连在一起为100101。下面的表格分别是亮度和色度DC差值的编码表：

色度差值的霍夫曼编码表：

根据上述表格的内容，即可为DC差值加上霍夫曼码值，完成DC的编码。JPEG从0开始对DC编码，所以DC(0)=0，然后再将当前Diff值加在上一个值上得到当前值。如果Y矩阵的8x8块DC=10，二进制为1010，码长为4，查亮度表得到Huffman识别长度为3，识别码为101，则其霍夫曼编码为1011010。负数的编码是取其绝对值的反码进行编码，如DC=-10，则其绝对值为10，二进制码为1010，反码为0101，霍夫曼编码为1010101。
②AC编码：
AC编码前，首先要将63个AC值按Z字形排序，将AC系数转换成中间符号，中间符号表示为RRRR/SSSS，其中RRRR是指第非零的AC之前，其值为0的AC个数，SSSS是指AC值所需的位数，AC系数的范围与SSSS的对应关系与DC差值位数与差值内容对照表相似。
如果连续0的AC个数大于15，则用15/0来表示连续的16个0，15/0称为ZRL(zero num length)，而(0/0)称为EOB(end of block)用来表示其后所剩余的AC系数皆为0。以中间符号值作为索引值，从相应的AC编码表中找出适当的霍夫曼码值，再与AC值相连即可。
为了提高存储效率，JPEG并不直接保存数值，而是将数值按实际值所需要的位数分成16组：

符号SSS用于表达实际值所需要的位数。例如有色度信号：

只处理每对数右边的那个数：
·31：实际值所需要的位数5，实际保存值为11111，所以编码为(5,11111)
·45：编码为(6,101101)
·23：编码为(5,10111)
·-30：编码为(5,00001)
·-8：编码为(4,0111)
·1：编码为(1,1)
色度数码然后就变成：

括号中的数值正好合成一个字节RRRR/SSSS，后面被编码的数字表示范围是-32767~32767。合成的字节里，前4位是前续0的个数，低4位描述了后面数字实际值所需要的位数。例如某一组亮度的中间符为5/3，AC值为4，首先以5/3为索引值，从亮度AC的霍夫曼编码表中找到1111111110011110码值，附加上原来的AC值4(100)，就得到用来取[5,4]的霍夫曼编码1111111110011110100，[5,4]表示AC值为4的前面有5个零。然后对每一对RRRR/SSSS查找色度AC系数的霍夫曼表。
·0/5：霍夫曼编码为11001
·0/6：霍夫曼编码为111000
·4/5：霍夫曼编码为1111111110011001
·1/5：霍夫曼编码为11111110110
·0/4：霍夫曼编码为1011
·2/1：霍夫曼编码为11011
·0/0EOB：霍夫曼编码为00
最后写入JPEG文件中数值为：11001 11111 111000 101101 1111111110011001 10111 11111110110 00001 1011 0111 11011 1 00
在JPEG文件中，一般有两个DC差分霍夫曼编码表，一个是亮度DC差分的霍夫曼编码表，一个是色度DC差分的霍夫曼编码表；有两个AC系数霍夫曼编码表，一个是亮度AC系数霍夫曼编码表，一个是色度AC系数霍夫曼编码表。
如果色度DC和上一块DC的差值Diff是-511，就编码成(9,000000000)，查找色度DC差分的霍夫曼编码表，9的色度DC差分霍夫曼编码表是111111110，那么JPEG文件中DC的二进制表示为111111110000000000，它将放在63个AC的前面，最终位流为：111111110 000000000 11001 11111 111000 101101 1111111110011001 10111 11111110110 00001 1011 0111 11011 1 00
按上述步骤，就完成一幅图像的JPEG压缩。

3. JPEG解压过程：

解压缩过程与压缩编码过程相反。

1)JPEG信息组织方式：
JPEG组织在制定规范时，规定了各种标记符来识别图像压缩数据信息，文件格式使用Motorola格式而不是Intel格式，也就是对一个字，高字节在前低字节在后。
JPEG文件是由一个个段segments构成的，每个段长度小于等于65535。每个段从一个标记开始，标记字都是以0xff开头，以非0字节和0xff结束。每个标记都有特定意义，这是第2个字节指明，如SOS指明开始解码，DQT指明后面是64字节量化表。在处理JPEG时，如果碰到0xff，它后面的字节不是0，并且这个字节没有意义，那么遇到的0xff字节必须被忽略，常常用作填充使用。如果在霍夫曼编码时，生成了0xff，那么就必须用0xff 0x00代替，也就是在JPEG图像界面时遇到FF00就当作FF处理。另外，在霍夫曼编码区域结束时，碰到几个位没有用时，应该使用1去填充，然后后面跟FF。
常见的JPEG标记码为：

JPEG图像文件标记码结构为：
SOI(图像开始)
  DQT(定义量化表)
    SOFn(帧标记)
      DHT(定义霍夫曼表)
        SOS(扫描开始)
EOI(图像结束)

2）JPEG文件示例：
下面是一个JPEG文件数据流：
FF D8(SOI标记)FF E0(APP0标记)00 10(APP的参数长度)4A 46 49 46 00(JFIF标记码，4A 46 49 46表示JFIF，00表示字符串结束)01 02(JFIF版本号)00(Xdensity和Ydensity的单位，00表示为指定单位)00 01(Xdensity，水平点密度值)00 01(Ydensity，垂直点密度值)00(水平点数)00(垂直点数)FF DB(DQT，定义量化表)00 43(DQT参数长度)00(第1个0表示量化表的值为8位，1时表示16位，第2个值表示量化表的编号，可为1~3)08 06 07 06 05 08 07 07 07 09 09 09 08 0A 0C 14 0D 0C 0B 0B 0C 19 12 13 0F 14 1D 1A 1C 1C 20 24 2E 27 20 22 2C 23 1C 1C 28 37 29 2C 30 31 34 34 34 1F 27 39 3D 38 32 3C 2E 33 34 32(量化表0的数据，共64位)FF DB 00 43 01(1表示量化表1)09 09 09 0C 0B 0C 18 0D 0D 18 32 21 1C 21 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32(量化表1的数据，共64位)FF C0(SOF0标记)00 11(参数长度)08(每个像素为8位)00 10(图像宽度)00 10(图像高度)03(在frame中的成分个数Nf=1~255)01(在frame中的成分编号为1)22(水平和垂直的数据取样比例为2:2)00(量化表0)02 11 01(成分编号2,1:1，量化表1)03 11 01(成分编号3,1:1，量化表1)FF C4(DHT，定义霍夫曼表)00 1F(DHT的参数长度)00((Tc,Th)Tc=0表示DC所使用的表格，Tc=1表示AC所使用的表格，Th=1~3，Th表示第Th个霍夫曼表，此处表示DC，Table0)00 01 05 01 01 01 01 01 01 00 00 00 00 0 00 00(矩阵iBits[])00 02 01 03 03 02 04 03 05 05 04 04 00 00 01 7D 01 02 03 00 04 11 05 12 21 31 41 06 13 51 61 07 22 71 14 32 81 91 A1 08 23 42 B1 C1 15 52 D1 F0 24 33 62 72 82 09 0A 16 17 16 18 1A 25 26 27 28 29 2A 34 35 36 37 38 39 3A 43 44 45 46 47 48 4A 53 54 55 56 57 58 59 5A 63 64 65 66 67 68 69 6A 73 74 75 76 77 78 79 7A 83 84 85 86 87 88 89 8A 92 94 95 96 97 98 99 9A A2 A3 A4 A5 A6 A7 A8 A9 AA B2 B3 B4 B5 B6 B7 B8 B9 BA C2 C3 C4 C5 C6 C7 C8 C9 CA D2 D3 D4 D5 D6 D7 D8 D9 DA E1 E2 E3 E4 E5 E6 E7 E8 E9 EA F1 F2 F3 F4 F5 F6 F7 F8 F9 FA(以上可导出AC0)FF C4 00 1F 01(此处表示DC1)FF C4 00 B5 11(此处表示AC1)00 02 01 02 04 04 03 04 07 05 04 04 00 01 02 77 00 01 02 03 11 04 05 21 31 06 12 41 51 07 61 71 13 22 32 81 08 14 42 91 A1 B1 C1 09 23 33 52 F0 15 62 72 D1 0A 16 24 34 E1 25 F1 17 18 19 1A 26 27 28 29 2A 35 36 37 38 39 3A 43 44 45 46 47 48 49 4A 53 54 55 56 57 58 59 5A 63 64 65 66 67 68 69 6A 73 74 75 76 77 78 79 7A 82 83 84 85 86 87 88 89 8A 92 93 94 95 96 97 98 99 9A A2 A3 A4 A5 A6 A7 A8 A9 AA B2 B3 B4 B5 B6 B7 B8 B9 BA C2 C3 C4 C5 C6 C7 C8 C9 CA D2 D3 D4 D5 D6 D7 D8 D9 DA E2 E3 E4 E5 E6 E7 E8 E9 EA F2 F3 F4 F5 F6 F7 F8 F9 FA(以上可导出AC1)FF DA(SOS标记，开始扫描)00 0C(SOS参数长度)03(成分个数，Ns=1~4)01(在scan中的成分编号，此处为1)00(DC和AC的编码表编号，此处表示DC0，AC1)02 11(成分编号2，DC1，AC1)03 11(成分编号3，DC1，AC1)00(Ss，起始频率选择)3F(Se，终止频谱选择，在baseline中，Ss=0，Se=63)00((Ah,Al)，在baseline中Ah=0，Al=0)(以下为扫描数据)F7 EA 28 A2 80 3F FF D9(EOI标志，图像结束)

3）解码过程：
在第一个DHT标记中，其结构中的Ln(以矩阵iBits[]来表示)和Vt(以矩阵iHuffVal[]来表示)的值如下：

t=iBits[1]+iBits[2]+...+iBits[16]=12

首先，将iBits[n]中的非零值依其所对应的霍夫曼码的长度n依次展开（以矩阵iHuffSize[]）表示：

iHuffSize[t]的含义见亮度DC差值的霍夫曼编码表。
以iHuffSize[]为基准，产生霍夫曼码（以icode表示）：
⑴icode=0
⑵在霍夫曼码的长度未变时，icode++
⑶若长度改变，icode左移一位，再重复⑵步骤
经过处理，可得DHT标记所提供的霍夫曼表：

在解压缩过程中，除了要有以上4个矩阵外，还要建立iValPtr[]、iMinCode[]、iMaxCode[]3个矩阵，才有足够信息进行解码。iValPtr[n]表示长度为n的霍夫曼码在iHuffVal[]的起始位置，而iMinCode[n]和iMaxCode[]分别是指长度为n的霍夫曼码的最大和最小值。

然后可以进行解压缩操作，示例代码中压缩数据为“F7 EA ...”变为二进制11110111和11101010。解码过程为：
⑴从压缩数据读取1位，1>iMaxCode[1]，此时码长n=1
⑵从压缩数据再读取1位，11>iMaxCode[2]，此时码长n=2
⑶从压缩数据再读取1位，111>iMaxCode[3]，此时码长n=3
⑷从压缩数据再读取1位，1111>iMaxCode[4]，此时码长n=4
⑸从压缩数据再读取1位，1111>iMaxCode[5]，此时码长n=5
⑹11110-iMinCode[5]=0，表示此码(11110)是从n=5的码中，第一个码的位置开始，向后移0个位置的码
⑺所以iValPtr[5]+0=7，而此码(11110)所对应的霍夫曼值SSSS=7
⑻得11110后7位为VVVV=1111110
以上是对DC的处理。解压缩过程为：
①解码开始，需要初始化DC值为0，先解码DC
使用DC霍夫曼表取得一个霍夫曼码；霍夫曼解码，得到后面的数据位数N；取得N位，计算Diff值；DC+=Diff；写入DC值，vector[0]=DC
②解码63个AC：循环处理每个AC直到EOB或者处理到64个AC
使用AC霍夫曼表取得一个霍夫曼码；霍夫曼解码，得到(前面0数量，组号)；取得N位组号计算AC；写入相应数量的0；然后写入AC
③从得到的64个矢量接着解码：
反量化64个矢量，for(i=0;i<=63;i++) vector[i]*=quant[i]；重新排列64个矢量到8x8的块中；对8x8块作IDCT
④重复以上操作，获得所有8x8块的(Y,Cb,Cr)；将所有的8位数加上128；转换YCbCr到RGB色彩模型。