Jpeg huffman编码程序 [英] Jpeg huffman coding procedure
问题描述
JPEG标准中的霍夫曼表格是从两个步骤的统计信息集合中生成的。其中一个步骤是实现这张照片给出的功能/方法：（这张照片在JPEG标准的附件K中给出）：
A Huffman table, in JPEG standard, is generated from a collection of statistics in two steps. One of the steps is implementing function/method given by this picture: (This picture is given in Annex K of JPEG standard):
问题出在这里。以前在标准（附件C）中说这句话：
Problem is here. Previously in standard (Annex C) says this sentence:
霍夫曼表是按照16字节列表（BITS）来指定的，每个代码长度从
1到16.之后是8位符号值（HUFFVAL）的列表，每个符号值分配了一个霍夫曼代码。
显然 BITS 是16个元素的列表。但是在上图中， i 首先设置为32（ i = 32 ），然后我们要访问 BITS [I] 。可能我误解了一些东西，所以请让某人给我一个答案。
Obviously BITS is list of 16 elements. But in picture above, i is first set to 32 (i=32) then we want to access BITS[i]. Probably I misunderstood something, so please let someone gives me an answer.
这里是图片的JPEG标准描述：
3 给出了调整BITS列表的过程，使得没有代码长于16位。由于符号与最长霍夫曼代码配对
，所以符号每次从这个长度类别2中删除。对
（稍短一个）的前缀被分配给该对中的一个;然后（从该前缀长度跳过BITS条目），来自下一个最短非零BITS条目的码字
被转换为一位长一个的两个码字的前缀。在将BITS
列表减少到16位的最大代码长度之后，最后一步将从代码长度
计数中删除保留的代码点。
Here is JPEG standard description of picture: Figure K.3 gives the procedure for adjusting the BITS list so that no code is longer than 16 bits. Since symbols are paired for the longest Huffman code, the symbols are removed from this length category two at a time. The prefix for the pair (which is one bit shorter) is allocated to one of the pair; then (skipping the BITS entry for that prefix length) a code word from the next shortest non-zero BITS entry is converted into a prefix for two code words one bit longer. After the BITS list is reduced to a maximum code length of 16 bits, the last step removes the reserved code point from the code length count.
以下是上图的代码：
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;
}
}
}
推荐答案
此代码仅适用于要生成自己的自定义霍夫曼表的编码器。大多数JPEG编码器只是使用固定的表格，它们是大多数图像统计信息的合理近似值。在这种特殊情况下，为AC系数生成霍夫曼表的第一步产生长达32个条目（位）的表。由于只有256个唯一的符号进行编码（跳过/长度对），所以不应该有超过32位来指定所有的霍夫曼码。在第一遍产生一组代码（长达32位）之后，第二次通过采用最不频繁（最长）的代码，并将它们移动到较短的长度时隙，以使最大代码长度为16位。在理想的霍夫曼表中，频率分布对应于码长。在这种情况下，通过将最长的代码压缩到为较短代码保留的时隙中，使表适合。这可以做到，因为14/15/16位长的霍夫曼代码对于更多位的置换具有空间，并且可以适合更长的代码。
This code is only for encoders that want to generate their own custom Huffman tables. The majority of JPEG encoders just use fixed tables that are reasonable approximations of the statistics of most images. In this particular case, the first step in generating a Huffman table for the AC coefficients produces a table up to 32 entries (bits) long. Since there are only 256 unique symbols to encode (skip/length pairs), there should never be more than 32 bits needed to specify all of the Huffman codes. After the first pass has produced a set of codes (up to 32-bits in length), the second pass takes the least frequent (longest) codes and "moves" them into shorter length slots so that the maximum code length is 16-bits. In an ideal Huffman table, the frequency distributions correspond to the code lengths. In this case, the table is being made to fit by squeezing the longest codes into slots reserved for shorter codes. This can be done because the 14/15/16 bit length Huffman codes have "room" for more permutations of bits and can "fit" the longer codes in them.
更新：
优化JPEG中的霍夫曼表是有限的。大部分压缩是由于像素的量化和DCT变换而发生的。切换到算术编码具有可衡量的优势（约10％的大小减少），但是限制了观众，因为大多数JPEG解码器由于过去的专利问题而不支持算术编码。
Update: There is limited benefit to "optimizing" the Huffman tables in JPEG. Most of the compression occurs because of the quantization and DCT transform of the pixels. Switching to arithmetic coding has a measurable benefit (~10% size reduction), but then it limits the audience since most JPEG decoders don't support arithmetic coding due to past patent issues.
这篇关于Jpeg huffman编码程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
