Jpeg哈夫曼编码过程

Question

JPEG 标准中的霍夫曼表是通过两个步骤从统计数据集合中生成的。步骤之一是实现该图给出的功能/方法：（该图在 JPEG 标准的附件 K 中给出）：

问题就在这里。之前在标准（附录C）中说了这样一句话：

霍夫曼表以 16 字节列表 (BITS) 的形式指定，给出从 1 到 16 的每个代码长度的代码数量。后面是 8 位符号值 (HUFFVAL) 列表，每个符号值是分配一个霍夫曼代码。

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

以下是 JPEG 标准对图片的描述： 图 K.3给出了调整 BITS 列表的过程，以便没有代码长于 16 位。由于符号是针对最长的霍夫曼码配对的，因此每次从该长度类别中删除两个符号。该对的前缀（短一位）被分配给该对中的一个；然后（跳过该前缀长度的 BITS 条目）来自下一个最短非零 BITS 条目的码字被转换为长一位的两个码字的前缀。在 BITS 列表减少到最大代码长度 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 解码器不支持算术编码。