JPEG算法解密（四）

Posted on by jinchao

步骤五：哈弗曼编码

        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算法解密（四）”

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

    回复

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

      回复

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

    回复

  6. 你给的亮度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

    回复

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

    回复

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

      回复

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

      回复

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

        回复

  10. 请问下，第二个数组是被编码的值，那第一个数组是干嘛用的？

    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 };

    回复

  11. 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 指的是什么情况？？？？

    回复

  12. 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.