Huffman coding for $8\times 8$ blocks of an image

Question

I have a question regarding the Huffman coding in Image processing. In order to compress the signal, we usually operate on $8\times 8$ pixels (blocks) on which we perform DCT, zig-Zag scan, quantization then construct the alphabets using run-length encoding (RLE). After all of that, we do Huffman coding.

My question is: Do we have to compute and store the Huffman tree/table for each block separately and augment it to the bit stream of the block or we compute the frequency of the alphabets in all the blocks jointly and do Huffman coding only once at the end (this saves the memory needed to store different table/tree for each block).

In other words, isn't it almost useless to use Huffman coding on only $64$ coefficients ($1$ block) and save the table with data stream (which consumes memory)?

Answer 1

Huffman coding, as an example of statistical entropy coding, is used as the last step of still image compression to further reduce any statistical redundancy (possibly) present at the output representation of quantized DCT coeffcients of a given block of N by N pixels (usually N = 8)

When the statistical behaviour of those DCT coefficients are analysed throughout the whole image, it will be seen (for naturally generated images) that certain symbols occur more frequently to the extend that using a variable length code (VLC) will become benefical instead of a fixed length one.

Thus to utilize this further possibility of statistical compression, VLC is employed via Huffman code tables for each of the AC, DC, Gray and Color channel coefficients separately according to their respective statistical symbol frequency distributions.

Now, the proper way of generating a statistically optimized Huffman table per block, actually necessitates a per-block optimized huffman table as you outlined in your question. However due to several reasons, one of which is again mentioned as the complaint in your question, such a method would oppose the initial purpose of image compression; to reduce its size.

Mainly: 1- inlcusion of per block optimized huffman tables into each block will reduce benefits of compression (it can even increase the block size for high quality compression where there will be so many symbolls and the table will include as many data as the block itself)

2- The loss of the benefit from discarding a per-block optimized Huffman table utilization will be mostly insignificant (i.e. A single whole image optimized Huffman table will perform almost as good as a per-block optimized one - even when excluding the effect of the table storage per block)

3- It will be more robust to create the table from an ensamble of blocks rather than a single one. (However note that due to statitical nonstationarity of typical images, the statistical behaviour from one block to an adjacent one other will change and hence the ensamble is not always a qualified source of data for table optimization)

4- Nevertheless, the approach taken is to use a single Huffman table for the whole image and store this inside the image file headers.

5- Now this single Huffman table can be defined in one of two ways: as either a pre-defined standard table or as an image specific optimized table. Most often the former approach is taken as the benefit from using specific image optimized Huffman table is attenuated by the table processing time and the complexity of programming required for per-frame Huffman table optimization.