步骤五:哈弗曼编码


        JPEG压缩的最后一步是对数据进行哈弗曼编码(Huffman coding),哈弗曼几乎是所有压缩算法的基础,它的基本原理是根据数据中元素的使用频率,调整元素的编码长度,以得到更高的压缩比。
        举个例子,比如下面这段数据

“AABCBABBCDBBDDBAABDBBDABBBBDDEDBD”

        这段数据里面包含了33个字符,每种字符出现的次数统计如下

字符 A B C D E
次数 6 15 2 9 1

        如果我们用我们常见的定长编码,每个字符都是3个bit。

字符 A B C D E
编码 001 010 011 100 101

        那么这段文字共需要3*33 = 99个bit来保存,但如果我们根据字符出现的概率,使用如下的编码

字符 A B C D E
编码 110 0 1110 10 1111

        那么这段文字共需要3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63个bit来保存,压缩比为63%,哈弗曼编码一般都是使用二叉树来生成的,这样得到的编码符合前缀规则,也就是较短的编码不能够是较长编码的前缀,比如上面这个编码,就是由下面的这颗二叉树生成的。

        我们回到JPEG压缩上,回顾上一节的内容,经过数据量化,我们现在要处理的数据是一串一维数组,举例如下:

①原始数据
35,7,0,0,0,-6,-2,0,0,-9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,…,0

        在实际的压缩过程中,数据中的0出现的概率非常高,所以首先要做的事情,是对其中的0进行处理,把数据中的非零的数据,以及数据前面0的个数作为一个处理单元。

①原始数据
35,7,0,0,0,-6,-2,0,0,-9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,…,0
②RLE编码 35 7 0,0,0,-6 -2 0,0,-9 0,0,…,0,8 0,0,…,0

        如果其中某个单元的0的个数超过16,则需要分成每16个一组,如果最后一个单元全都是0,则使用特殊字符“EOB”表示,EOB意思就是“后面的数据全都是0”,

①原始数据
35,7,0,0,0,-6,-2,0,0,-9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,…,0
②RLE编码 35 7 0,0,0,-6 -2 0,0,-9 0,0,…,0,8 0,0,…,0
35 7 0,0,0,-6 -2 0,0,-9 0,0,…,0 0,0,8 0,0,…,0
(0,35) (0,7) (3,-6) (0,-2) (2,-9) (15,0) (2,8) EOB

        其中(15,0)表示16个0,接下来我们要处理的是括号里右面的数字,这个数字的取值范围在-2047~2047之间,JPEG提供了一张标准的码表用于对这些数字编码:

Value Size Bits
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 0 0000,…,0 1111 1 0000,…,1 1111
-63,…,-32 32,…,63 6 00 0000,… …,11 1111
-127,…,-64 64,…,127 7 000 0000,… …,111 1111
-255,…,-128 128,…,255 8 0000 0000,… …,1111 1111
-511,…,-256 256,…,511 9 0 0000 0000,… …,1 1111 1111
-1023,…,-512 512,…,1023 10 00 0000 0000,… …,11 1111 1111
-2047,…,-1024 1024,…,2047 11 000 0000 0000,… …,111 1111 1111

        举例来说,第一个单元中的“35”这个数字,在表中的位置是长度为6的那组,所对应的bit码是“100011”,而“-6”的编码是”001″,由于这种编码附带长度信息,所以我们的数据变成了如下的格式。

①原始数据
35,7,0,0,0,-6,-2,0,0,-9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,…,0
②RLE编码 35 7 0,0,0,-6 -2 0,0,-9 0,0,…,0,8 0,0,…,0
35 7 0,0,0,-6 -2 0,0,-9 0,0,…,0 0,0,8 0,0,…,0
(0,35) (0,7) (3,-6) (0,-2) (2,-9) (15,0) (2,8) EOB
③BIT编码 (0,6, 100011) (0,3, 111) (3,3, 001) (0,2, 01) (2,4, 0110) (15,-) (2,4, 1000) EOB

        括号中前两个数字分都在0~15之间,所以这两个数可以合并成一个byte,高四位是前面0的个数,后四位是后面数字的位数。

①原始数据
35,7,0,0,0,-6,-2,0,0,-9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,…,0
②RLE编码 35 7 0,0,0,-6 -2 0,0,-9 0,0,…,0,8 0,0,…,0
35 7 0,0,0,-6 -2 0,0,-9 0,0,…,0 0,0,8 0,0,…,0
(0,35) (0,7) (3,-6) (0,-2) (2,-9) (15,0) (2,8) EOB
③BIT编码 (0,6, 100011) (0,3, 111) (3,3, 001) (0,2, 01) (2,4, 0110) (15,-) (2,4, 1000) EOB
(0x6,100011) (0x3,111) (0x33,001) (0x2,01) (0x24,0110) (0xF0,-) (0x24,1000) EOB

        对于括号前面的数字的编码,就要使用到我们提到的哈弗曼编码了,比如下面这张表,就是一张针对数据中的第一个单元,也就是直流(DC)部分的哈弗曼表,由于直流部分没有前置的0,所以取值范围在0~15之间。

Length Value Bits
3 bits 04
05
03
02
06
01
00 (EOB)
000
001
010
011
100
101
110
4 bits 07 1110
5 bits 08 1111 0
6 bits 09 1111 10
7 bits 0A 1111 110
8 bits 0B 1111 1110

        举例来说,示例中的DC部分的数据是0x06,对应的二进制编码是“100”,而对于后面的交流部分,取值范围在0~255之间,所以对应的哈弗曼表会更大一些

Length Value Bits
2 bits 01
02
00
01
3 bits 03 100
4 bits 00 (EOB)
04
11
1010
1011
1100
5 bits 05
12
21
1101 0
1101 1
1110 0
6 bits 31
41
1110 10
1110 11
12 bits 24
33
62
72
1111 1111 0100
1111 1111 0101
1111 1111 0110
1111 1111 0111
15 bits 82 1111 1111 1000 000
16 bits 09

FA
1111 1111 1000 0010

1111 1111 1111 1110

        这样经过哈弗曼编码,并且序列化后,最终数据成为如下形式

①原始数据
35,7,0,0,0,-6,-2,0,0,-9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,…,0
②RLE编码 35 7 0,0,0,-6 -2 0,0,-9 0,0,…,0,8 0,0,…,0
35 7 0,0,0,-6 -2 0,0,-9 0,0,…,0 0,0,8 0,0,…,0
(0,35) (0,7) (3,-6) (0,-2) (2,-9) (15,0) (2,8) EOB
③BIT编码 (0,6, 100011) (0,3, 111) (3,3, 001) (0,2, 01) (2,4, 0110) (15,-) (2,4, 1000) EOB
(0x6,100011) (0x3,111) (0x33,001) (0x2,01) (0x24,0110) 0xF0 (0x24,1000) EOB
④哈弗曼编码 100 100011 100 111 1111 1111 0101 001 01 01 1111 1111 0100 0110 1111 1111 001 1111 1111 0100 1000 1010
⑤序列化
100100011100111111111110101001010111111111010001101111111100111111111010010001010
91 CF FE A5 7F D1 BF CF FA 45

        最终我们使用了10个字节的空间保存了原本长度为64的数组,至此JPEG的主要压缩算法结束,这些数据就是保存在jpg文件中的最终数据。

24 thoughts on “JPEG算法解密(四)

  1. 资料写得相当详细,谢谢知识分享。
    这里我有一个问题,就是文章《JPEG算法解密(四)》中最后序列化的数据不可能都恰好是整字节数的,其后解码会怎么处理呢?
    能用邮件回复我就最好了。

    1. 最终的序列,在接收端如何确定开始和结束?当DC分量和AC分量的前缀一样时,怎样区分。

  2. 您好,我看了一下源码,有一个地方不太理解:在doHuffmanEncoding函数里面,dc分量的编码为什么要减去前一项prevDC ?

  3. 你给的亮度dc是标准推荐的huffman编码表吗? 跟标准里面的不一样。

    ISO/IEC 10918-1 : 1993(E) 中的表如下:

    Table K.3 – Table for luminance DC coefficient differences

    Category Code length Code word
    0 2 00
    1 3 010
    2 3 011
    3 3 100
    4 3 101
    5 3 110
    6 4 1110
    7 5 11110
    8 6 111110
    9 7 1111110
    10 8 11111110
    11 9 111111110

  4. 请问一下在为各个数据进行哈夫曼编码的时候,怎么判断是直流还是交流?是通过前置0的数量吗?但是根据最后你列的情况看,35的前面没有前置的0,但是7和-2也没有前置的0,结果是35用的直流的哈夫曼表,7与-2用的是交流的,我想知道一下判断的依据。

    1. 直流表和交流表的判别根据位置来的,每块单元的第一块就是直流,用直流表去解析它,后面的是交流,然后看看是亮度还是色度

    2. 大神我想问一下,这个dc霍夫曼编码表,和jpeg中的编码不对应,您是怎么得出这和dc_nrcode 的,我毕业设计研究这个,求解?

      1. 这个码表是根据概率及时算出来的,不是JPEG的标准码表。JPEG编码可以不用标准码表

  5. 请问下,第二个数组是被编码的值,那第一个数组是干嘛用的?

    static const char Standard_DC_Luminance_NRCodes[] = { 0, 0, 7, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 };
    static const unsigned char Standard_DC_Luminance_Values[] = { 4, 5, 3, 2, 6, 1, 0, 7, 8, 9, 10, 11 };

  6. if (*newBytePos < 0) {
    // Write to stream
    _write_byte_((unsigned char) (*newByte), data);
    if (*newByte == 0xFF) {
    // Handle special case
    _write_byte_((unsigned char) (0x00), data);
    }
    // Reinitialize
    *newBytePos = 7;
    *newByte = 0;
    }

    // Handle special case 指的是什么情况????

  7. 100100011100111111111110101001010111111111010001101111111100111111111010010001010
    91 CF FE A5 7F D1 BF CF FA 45
    请问下,只存这一串字符,也重建不出来原图叭?看不出来哪些字符对应图像的哪部分吖。

发表评论

邮箱地址不会被公开。

This site uses Akismet to reduce spam. Learn how your comment data is processed.