What is Huffman Coding?

Huffman coding is a lossless data compression technique based on the frequency (probability) of occurrence
of symbols. It generates variable-length codes: shorter codes for more frequent symbols and longer codes for
less frequent ones.
In digital image processing, Huffman coding is often used in image compression (as the final step after image
transformation or quantization).

Why Huffman Coding in Image Processing?

• Images typically have redundant pixel values.
• Huffman coding reduces the number of bits required to store these values without losing any
information.
• It is commonly used after predictive coding, quantization, DCT (JPEG), or wavelet transform
(JPEG2000).

• Huffman Tree Construction:

A binary tree, known as the Huffman tree, is built based on these frequencies. The process starts by treating
each symbol as a leaf node with its corresponding frequency. The two nodes with the lowest frequencies are
then combined into a new parent node, whose frequency is the sum of its children's frequencies. This process
repeats until only one node (the root) remains.
• Code Assignment:
Binary codes are assigned to each symbol by traversing the Huffman tree from the root to the leaf
nodes. Typically, a '0' is assigned for a left branch and a '1' for a right branch (or vice versa). The path from the
root to a leaf node defines the Huffman code for that symbol.

Example: Small 4-symbol set

Symbol Probability
A 0.4
B 0.3
C 0.2
D 0.1
Huffman tree produces codes:
• A=0
• B = 10
• C = 110
• D = 111

Compression Performance
The average code length is:
Lavg=∑pi⋅li
Where:
• pi = probability of symbol i
• li = length of Huffman code for symbol i
Efficiency:
η=H/Lavg
Where H is the entropy:
H=−∑pilog 2pi

Applications in DIP
• JPEG: After quantization, Huffman coding is applied to DCT coefficients.
• Medical Imaging: CT, MRI images use lossless compression.
• Remote Sensing: Huffman is used to compress satellite images.

Advantages
• Simple and effective for lossless compression
 • JPEG: After quantization, Huffman coding is applied to DCT coefficients.
• Medical Imaging: CT, MRI images use lossless compression.
• Remote Sensing: Huffman is used to compress satellite images.

Advantages
• Simple and effective for lossless compression
• Near-optimal coding when symbol probabilities are known.
Limitations
• Requires prior knowledge of symbol frequencies
• Not efficient if symbol probabilities are uniform
• Slightly less efficient than arithmetic coding in some cases.

Textbook Exercise

Encoded string 010100111100

Decoded message to be a3 a1 a2 a2 a6
Arithmetic Coding
Arithmetic Coding
Encoding Sequence

Example 2
 Example 2

LZW Coding

LZW (Lempel-Ziv-Welch) coding is a lossless data compression algorithm widely used in digital image
processing, notably in formats like GIF and TIFF. It functions by building a dictionary of repeating sequences of
data within an image and then replacing these sequences with shorter codes.

How LZW Coding Works in Image Processing:

• Initialization:
A dictionary is initialized with single-character entries representing all possible pixel values (e.g., 0-255 for an
8-bit grayscale image).
• Encoding:
The algorithm scans the image data, identifying sequences of pixels. If a sequence is found in the dictionary, it
is extended with the next pixel. If the extended sequence is not in the dictionary, the code for the shorter,
already-known sequence is output, and the new, longer sequence is added to the dictionary with a new
code. The process then restarts with the last pixel of the newly added sequence.
• Decoding:
The decoder reconstructs the image by using the received codes to look up the corresponding pixel sequences
in its own dynamically built dictionary, which mirrors the encoder's dictionary.

Problems and Limitations of LZW Coding in Image Processing:

• Ineffectiveness on Non-Repetitive Data:
LZW relies on finding repeated patterns for effective compression. Images with high levels of randomness,
noise, or fine details (e.g., natural images with gradients and shadows) offer fewer opportunities for
repetition, leading to less efficient compression or even file size increase in extreme cases.
• Memory Requirements:
The dynamic dictionary building can consume significant memory, especially for large images or those with
diverse patterns that lead to a rapidly growing dictionary.
• Speed for Large Files:
While generally fast, the dictionary management and lookup processes can become a bottleneck for very large
image files, impacting compression and decompression speed.
 noise, or fine details (e.g., natural images with gradients and shadows) offer fewer opportunities for
repetition, leading to less efficient compression or even file size increase in extreme cases.
• Memory Requirements:
The dynamic dictionary building can consume significant memory, especially for large images or those with
diverse patterns that lead to a rapidly growing dictionary.
• Speed for Large Files:
While generally fast, the dictionary management and lookup processes can become a bottleneck for very large
image files, impacting compression and decompression speed.

Encode the Input String

ABABABBABABAB

Initial Dictionary
The dictionary initially contains all individual symbols:
Code Entry
1 A
2 B

Final Dictionary
Code Entry
1 A
2 B
3 AB
4 BA
Final Dictionary
Code Entry
1 A
2 B
3 AB
4 BA
5 ABA
6 ABB
7 BAB
8 BABA

Final Encoded Output

Codes:
1, 2, 1, 3, 3, 4, 7, 1

Encoding Steps
We scan the string left to right, building a dictionary of new sequences as we go.

Step-by-step
1. Start with 'A'
○ Output code for 'A' → 1
○ Next symbol: 'B'
○ Add 'AB' to dictionary with next code 3
2. Now 'B'
○ Output code for 'B' → 2
○ Next symbol: 'A'
○ Add 'BA' to dictionary with next code 4
3. Next 'A'
○ Output code for 'A' → 1
○ Next symbol: 'B'
○ 'AB' already in dictionary (code 3), so continue reading.
4. 'AB' found (code 3)
○ Next symbol: 'A'
○ Add 'ABA' to dictionary with code 5
○ Output code for 'AB' → 3
5. Next sequence starts at 'A'
○ 'A' + 'B' = 'AB' (exists)
○ 'AB' + 'B' = 'ABB' (new)
○ Add 'ABB' to dictionary with code 6
○ Output code for 'AB' → 3
6. Continue
○ 'B' (remaining after 'AB') + 'A' = 'BA' (exists)
○ 'BA' + 'B' = 'BAB' (new)
○ Add 'BAB' to dictionary with code 7
○ Output code for 'BA' → 4
7. Continue
○ Next is 'B' (after 'BA')
○ 'B' + 'A' = 'BA' (exists)
○ 'BA' + 'B' = 'BAB' (exists, code 7)
○ 'BAB' + 'A' = 'BABA' (new)
○ Add 'BABA' to dictionary with code 8
○ Output code for 'BAB' → 7
8. Remaining 'A'
○ Output code for 'A' → 1

Decoding
The decoder uses the same logic: starts with the initial dictionary and reconstructs entries as new codes arrive.
 8. Remaining 'A'
○ Output code for 'A' → 1

Decoding
The decoder uses the same logic: starts with the initial dictionary and reconstructs entries as new codes arrive.

What is Bit-Plane Coding?

Bit-plane coding is a lossless/lossy image compression technique where an image is represented as a set of
binary images (bit-planes).
Each pixel value (for example, 8-bit grayscale: 0–255) can be broken into bits:
Pixel value=b7b6b5b4b3b2b1b0Pixel value=b7b6b5b4b3b2b1b0
• b7 → Most Significant Bit (MSB)
• b0 → Least Significant Bit (LSB)
So the original image can be separated into 8 binary images (planes).

Why Use Bit-Plane Coding?

• Higher bit-planes (MSB) carry most of the visually significant information.
• Lower bit-planes (LSB) carry finer details and noise.
• By compressing or discarding lower planes, storage can be reduced.

Steps in Bit-Plane Coding

1. Decompose the image
For an 8-bit grayscale image, split each pixel into 8 separate bit images (planes).
2. Store/Transmit planes
○ High-order planes can be encoded with lossless methods.
○ Lower-order planes can be encoded with lossy methods or discarded.

Applications
1. Compression – Only store the most significant planes.
2. Watermarking – Hide data in the lower planes.
3. Edge detection / Image analysis – High planes highlight structure.

Advantages
• Simple to implement.
• Useful for progressive transmission (important bits sent first).
Limitations
• Lower planes contribute little to visual quality, so removing them may cause loss.

Problem
Consider a 2×2 grayscale image with the following pixel values (8-bit, 0–255):

Pixel values:
150 151
75 76
Perform bit-plane decomposition and write down the bit-plane 7 (MSB) and bit-plane 0 (LSB).

Step 1: Convert to 8-bit binary

• 150 → 10010110
• 151 → 10010111
• 75 → 01001011
• 76 → 01001100

Step 2: Extract Bit-Planes

Each bit position forms a separate binary image.

Bit-plane 7 (MSB) = most significant bit (leftmost bit)

Take the first bit from each binary value:
• 150 → 1
 • 76 → 01001100

Step 2: Extract Bit-Planes

Each bit position forms a separate binary image.

Bit-plane 7 (MSB) = most significant bit (leftmost bit)

Take the first bit from each binary value:
• 150 → 1
• 151 → 1
• 75 → 0
• 76 → 0

Bit-plane 7 image:
11
00

Bit-plane 0 (LSB) = least significant bit (rightmost bit)

Take the last bit from each binary value:
• 150 → 0
• 151 → 1
• 75 → 1
• 76 → 0

Bit-plane 0 image:
01
10

Answer
Bit-plane 7:
11
00

Bit-plane 0:
01
10
The same process can be done for bit-planes 6, 5, … 1.

Encoding techniques used after bit-plane coding

1. Run-Length Encoding (RLE):
Works well when a plane has long runs of zeros or ones.
2. Huffman Coding / Arithmetic Coding:
Removes statistical redundancy.
3. Context-based coding:
(e.g., JPEG2000) – uses context modeling plus arithmetic coding for even better compression.