encoding - jpeg哈夫曼编码程序

Question

JPEG 标准中的霍夫曼表是分两步从一组统计数据中生成的。其中一个步骤是实现此图片给出的功能/方法:(此图片在 JPEG 标准的附件 K 中给出):

问题就在这里。以前在标准(Annex C)中是这样说的:

霍夫曼表是根据 16 字节列表 (BITS) 指定的，给出每个代码长度的代码数量 1 到 16。接下来是 8 位符号值 (HUFFVAL) 的列表，每个符号值都分配了一个霍夫曼代码。

显然 BITS 是 16 个元素的列表。但在上图中，i 首先设置为 32 (i=32) 然后我们要访问 BITS[i]。可能我误解了什么，所以请有人给我答案。

这里是图片的JPEG标准描述: 图 K.3 给出了调整 BITS 列表以使代码不超过 16 位的过程。由于符号是成对的 对于最长的霍夫曼码，符号一次从该长度类别中删除两个。对的前缀 (短一点)分配给一对中的一个；然后(跳过该前缀长度的 BITS 条目)一个代码字 从下一个最短的非零 BITS 条目转换为两个长一位的代码字的前缀。在 BITS 之后 list 被缩减为最大 16 位的代码长度，最后一步从代码长度中删除保留的代码点 数数。

这是上图的代码:

void adjustBitLengthTo16Bits(vector<char>&BITS){
    int i=32,j=0;
    while(1){
        if(BITS[i]>0){
            j=i-1;
            j--;
            while(BITS[j]<=0)
                j--;
            BITS[i]=BITS[i]-2;
            BITS[i-1]=BITS[i-1]+1;
            BITS[j+1]=BITS[j+1]+2;
            BITS[j]=BITS[j]-1;
            continue;
        }
        else{
            i--;
            if(i!=16)
                continue;

            while(BITS[i]==0)
                i--;
            BITS[i]--;
            return;
        }
    }
}

Answer 1

此代码仅适用于想要生成自己的自定义霍夫曼表的编码器。大多数 JPEG 编码器只使用固定表格，这些表格是大多数图像统计数据的合理近似值。在这种特殊情况下，为 AC 系数生成霍夫曼表的第一步会生成一个长达 32 个条目(位)的表。由于只有 256 个唯一符号要编码(跳过/长度对)，因此指定所有霍夫曼代码所需的位永远不会超过 32 位。在第一遍生成一组代码(长度最多 32 位)后，第二遍采用频率最低(最长)的代码并将它们“移动”到较短长度的槽中，以便最大代码长度为 16 位.在理想的霍夫曼表中，频率分布对应于代码长度。在这种情况下，通过将最长的代码压缩到为较短的代码保留的插槽中，可以使表格适合。之所以能够做到这一点，是因为 14/15/16 位长度的霍夫曼代码具有用于更多位排列的“空间”，并且可以“容纳”其中更长的代码。

更新: “优化”JPEG 中的霍夫曼表的好处有限。大多数压缩是由于像素的量化和 DCT 变换而发生的。切换到算术编码具有可衡量的好处(大小减少约 10%)，但由于过去的专利问题，大多数 JPEG 解码器不支持算术编码，因此它限制了受众。