Are DC and AC coefficient magnitude not huffman compressed in JPEG?

1
votes

According to what I have read:

  1. DC coefficient per block, we create a byte storing difference magnitude category as shown in Annex F Table F.1 of ITU-T T.81. The actual DC coefficient which stores a difference is stored in raw bits following this huffman coded magnitude category information byte.

Similarly for AC coefficients,

  1. AC coefficients are first encoded to contain zero-run-lengths. Then, we huffman encode these bytes where upper 4 bits are zero-run-length and lower 4 bits are the AC coefficient magnitude category as shown in Annex F Table F.2 of ITU-T T.81. The huffman encoded byte that contains zero-length and magnitude category data is followed by raw bits that contain the actual AC coefficient magnitude.

My question is fundamentally this, in both cases, why do we store unencoded-uncompressed raw bits for the coefficients but the magnitude category information is huffman encoded? WHY? This makes no sense.

3
jpeghuffman-codeimage-compression
By storing the magnitude category followed by the "raw bits", it takes up less space than always storing 16-bits of data for each coefficient. E.g. the very common quantized values of 1 and -1 take a single bit to store the "raw bits" and the zero-length+mag-category combinations have short Huffman code lengths. – BitBank

3 Answers

2
votes

Here's another way of looking at it. When you compress bit values of variable length you need to encode the number of bits and the bits themselves. The coefficient lengths have a relatively small range of values while the coefficients have a wide range of values.

If you were to Huffman encode the coefficient values, the code lengths could be quite large and the tables hard to manageable.

JPEG then Huffman encodes the length part of the coefficients but not the coefficients themselves. Half the data gets compressed at this stage.

1
votes

It does make sense to store raw bits in these situations.

When the data you're trying to compress are close enough to 'random' (a flat/uniform probability distribution), then entropy coding will not give you much coding gain. This is particularly true for simple entropy coding method such as Huffman encoder. In this case, skipping entropy coding will give you similar compression ratios, and will reduce the time complexity.

0
votes

The way I see it, classifying the DC difference magnitudes into these "buckets", splits these values into a byte that will always be compressed into at most 4 bits (DC Huffman coding tables encode 12 possible values at most), followed by string of at most 11 bits where its length has a uniform probability distribution.

The other alternative could've been to use Huffman encoding directly on the full DC coefficient difference. If the values are unlikely to repeat, doing this would produce a different Huffman code for each one, which wouldn't produce much compression gains.

My guess is that people writing the spec did experimental testing on some image data set and concluded 12 magnitude categories yielded good enough compression. They probably also tested what you say about being agnostic to the data format and came to the conclusion their method compressed images better. So far, I haven't read the papers backing up the specification, but maybe this experimental data can be found there.

Note: When using 12 bit sample precision, there would be 16 magnitude categories, but they can still be encoded with at most 4 bits using Huffman coding.