JPEG编码过程中的霍夫曼编码

JPEG编码过程中的霍夫曼编码

jpeg文件中的霍夫曼编码分两个部分对DC系数编码和对AC系数的编码。

DC系数的编码

编码过程

DC系数的编码由两部分组成, huffman 编码的bitlen + additional bits。

通过上面的定义获取y的bitlen，通过jpeg提供的DC 霍夫曼编码树获得bitlen的编码。bitlen就把DC系数值分成12个type（8bit精度），实际值不用霍夫曼编码而直接用二进制的编码。

DC霍夫曼码表

霍夫曼码表的提供方式是，前16个字节，每个字节的值表示可以分别用1bit~16bit长度的码字表示的符号的数目。后边的字节串表示每一个符号。
下面是jpeg提供的亮度DC系数的霍夫曼码表

const BYTE STD_HUFTAB_LUMIN_DC[] =
{
    0x00, 0x01, 0x05, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b,
};

 0x00, //表示使用1bit表示的码字数量为0 
 0x01, //使用2bits表示的码字数量为1 
 0x05, //使用3bits表示的码字数量为5
 0x01, //使用4bits表示的码字数量为1
 0x01, 
 0x01, 
 0x01, 
 0x01, 
 0x01, 
 0x00, 
 0x00, 
 0x00, 
 0x00, 
 0x00, 
 0x00, 
 0x00, //总共有12个符号

12个符号值为0~11

 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b,

由给出的霍夫曼表获得霍夫曼树过程参考DIGITAL COMPRESSION AND CODINGOF CONTINUOUS-TONE STILL IMAGES –REQUIREMENTS AND GUIDELINES（Annex C）,它的matlab代码如下：

function [ ehufco, ehufsi ] = dedht( dht)
%dedht creat huffman code list
%   dht define huffman table

bits = dht(1:16);
huffval = dht(17:end);
n = 0;
for  j=1:16
    n = n + bits(j);
end
huffsize = zeros(1,n);
huffcode = zeros(1,n);
k = 0;
j = 1;
for i=1:16
    for j = 1:bits(i)
        huffsize(k+1)=i;
        k = k+ 1;
    end
end

huffsize(k+1) = 0;
lastk = k;

code = 0;
k=1;
% si code bit size 
si= huffsize(1);
while huffsize(k) > 0
    huffcode(k) = code;
    code = code + 1;
    k= k+ 1;
    while huffsize(k) == si
        huffcode(k)=code;
        code = code + 1;
        k = k+ 1;
    end
    if huffsize(k) == 0
        break;
    end
    code = code * 2;
    si = si + 1;
    while huffsize(k)~=si
        code = code *2;
        si = si + 1;
    end
end

for k=1:lastk
    i = huffval(k);
    ehufco(i +1) = uint32(huffcode(k));
    ehufsi(i+1) = uint32(huffsize(k));
end
end

C代码

/* 类型定义 */
/* 编码表项类型定义 */

#define MAX_HUFFMAN_CODE_LEN  16

typedef struct
{
    int symbol; /* 符号 */
    int freq;   /* 频率 */
    int group;  /* 分组 */
    int depth;  /* 码长 */
    int code;   /* 码字 */
} HUFCODEITEM;
/* 编码器类型定义 */
typedef struct
{
    BYTE         huftab[MAX_HUFFMAN_CODE_LEN + 256]; /* 哈夫曼表 */
    int          first [MAX_HUFFMAN_CODE_LEN];       /* first   */
    int          index [MAX_HUFFMAN_CODE_LEN];       /* index   */
    HUFCODEITEM  codelist[256];/* 编码表 */
    void        *input;        /* input bit stream  */
    void        *output;       /* output bit stream */
} HUFCODEC;

static void huffman_encode_init_from_huftab(HUFCODEC *phc)
{
    int  i, j, k;
    int  symbol;
    int  code;
    BYTE hufsize[256];
    int  hufcode[256];
    int  tabsize;

    k    = 0;
    code = 0x00;
    for (i=0; i<MAX_HUFFMAN_CODE_LEN; i++) {
        for (j=0; j<phc->huftab[i]; j++) {
            hufsize[k] = i + 1;
            hufcode[k] = code;
            code++; k++;
        }
        code <<= 1;
    }
    tabsize = k;

    for (i=0; i<tabsize; i++) {
        symbol = phc->huftab[MAX_HUFFMAN_CODE_LEN + i];
        phc->codelist[symbol].depth = hufsize[i];
        phc->codelist[symbol].code  = hufcode[i];
    }
}

输入上面的标准亮度DC huffman table获得的霍夫曼树如下：

{ 2,0x0000}, /*               00 */

{ 3,0x0002}, /*              010 */ 

{ 3,0x0003}, /*              011 */ 

{ 3,0x0004}, /*              100 */ 

{ 3,0x0005}, /*              101 */ 

{ 3, 0x0006},/*              110 */ 

{ 4,0x000e}, /*            1110 */ 

{ 5,0x001e}, /*          11110 */ 

{ 6,0x003e}, /*         111110 */ 

{ 7,0x007e}, /*        1111110*/ 

{ 8,0x00fe}, /*       11111110 */ 

{ 9,0x01fe}  /*    111111110 */

AC系数的编码

ZZ表示经过zig-zag 排序的DCT系数。AC 系数ZZ(1)~ZZ(63)被表示为一个8bit复合数RS，这个数被叫做Run length code(行程编码）

• 0的长度有时会超过16，RRRRSSSS=0xf0 表示连续16个0.
• block的结尾EOB被表示为 RRRRSSSS = 0x00，表示后边所有的数据都为0
  

AC霍夫曼码表

AC霍夫曼编码表的格式跟DC霍夫曼编码表的格式相同，前16个byte表示使用各个bits表示的符号数，后边的huffman value是行程编码的值。
从霍夫曼编码表中获得霍夫曼树的方式跟DC霍夫曼码表相同。
获得的AC霍夫曼树例子

const BYTE STD_HUFTAB_LUMIN_AC[] =
{
    0x00, 0x02, 0x01, 0x03, 0x03, 0x02, 0x04, 0x03, 0x05, 0x05, 0x04, 0x04, 0x00, 0x00, 0x01, 0x7d,
    0x01, 0x02, 0x03, 0x00, 0x04, 0x11, 0x05, 0x12, 0x21, 0x31, 0x41, 0x06, 0x13, 0x51, 0x61, 0x07,
    0x22, 0x71, 0x14, 0x32, 0x81, 0x91, 0xa1, 0x08, 0x23, 0x42, 0xb1, 0xc1, 0x15, 0x52, 0xd1, 0xf0,
    0x24, 0x33, 0x62, 0x72, 0x82, 0x09, 0x0a, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x25, 0x26, 0x27, 0x28,
    0x29, 0x2a, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49,
    0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69,
    0x6a, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89,
    0x8a, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
    0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3, 0xc4, 0xc5,
    0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xe1, 0xe2,
    0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8,
    0xf9, 0xfa,
};

参考