Q16Digital Image Processing

Huffman coding is a lossless, variable-length coding technique that removes coding redundancy by assigning shorter codewords to intensity levels that occur more frequently, and longer codewords to rare ones, while guaranteeing that no codeword is a prefix of another (instantaneously decodable).

Algorithm

• Compute the probability (relative frequency) of each gray level from the image histogram.
• List the symbols in decreasing order of probability as leaf nodes.
• Repeatedly combine the two nodes with the lowest probabilities into a new node whose probability is their sum, until a single root node remains, forming a binary tree.
• Assign 0 and 1 to the two branches at every merge point; the codeword for each symbol is the sequence of bits read from the root to that leaf.

Worked Example

Consider four gray levels with probabilities $a_1=0.4,a_2=0.3,a_3=0.2,a_4=0.1$. Merging the two lowest ($a_3,a_4$) gives a node of probability 0.3; merging that with $a_2$ (0.3) gives 0.6; merging with $a_1$ (0.4) gives the root (1.0). Backtracking assigns codes: $a_1=1$ (1 bit), $a_2=01$, $a_3=001$, $a_4=000$ (each 2-3 bits), giving an average length of $0.4(1)+0.3(2)+0.2(3)+0.1(3)=1.9$ bits/pixel versus 2 bits/pixel for fixed-length coding, close to the entropy of about 1.85 bits, demonstrating near-optimal compression.

In real images, the Huffman table itself must be transmitted alongside the compressed data (or a standard table, as in baseline JPEG, must be agreed upon in advance), since the decoder needs the same code assignments to reconstruct the original symbols. This overhead is negligible for large images but can be significant for small images with many distinct symbols. Huffman coding is also the entropy-coding stage that follows quantization in JPEG compression, where it losslessly compresses the already-quantized DCT coefficients, showing how Huffman coding functions as a general-purpose final stage layered on top of other, lossy compression techniques rather than a compression method used in isolation.