Image Encoding | Sahithyan's Notes

Image encoding assigns a codeword to each grey level. Codeword lengths decide how many bits per pixel the coded image needs.

For grey level $k$ with probability $P(k) = r_k / N$ and codeword length $l(k)$ :

L_{ave} = \sum_{k=0}^{L-1} l(k) P(k)

$L_{ave}$ is the average number of bits per pixel of the coded image. It is bounded below by the entropy $B_{ave}$ .

L_{ave} \geq B_{ave}

\text{Coding redundancy} = L_{ave} - B_{ave}

The smallest $L_{ave}$ is achieved by assigning the shortest codeword to the most probable grey level.

Fixed Length Coding

All grey levels are assigned codewords of the same length.

l(k) = \lceil \log_2 L \rceil

Here:

$L$ : number of grey levels
$l(k)$ : codeword length of grey level $k$
$L_{ave} = l(k)$ for every image, regardless of the grey level probabilities
$L_{ave} = B_{ave}$ only when all grey levels are equiprobable and $L$ is a power of 2
Simple to encode and decode, and allows random access to any pixel
Contains coding redundancy whenever the grey levels are not equiprobable

Examples:

8bpp image, $L = 256$ , $l(k) = 8$ bits
3 grey level image, $L = 3$ , $l(k) = 2$ bits

Variable Length Coding

Grey levels are assigned codewords of different lengths. More probable grey levels get shorter codewords.

Achieves $L_{ave}$ close to the entropy $B_{ave}$ , with $L_{ave} = B_{ave}$ only when every $P(k)$ is a power of $\frac{1}{2}$
Must remain uniquely decodable
A prefix code satisfies this, since no codeword is a prefix of another codeword

Example:

For the 3 grey level image in the entropy example:

Grey level	$P(k)$	Fixed code	Variable code
White	0.5	00	0
Grey	0.25	01	10
Black	0.25	10	11

Fixed length code:

L_{ave} = 2 \text{ bits}

Variable length code:

L_{ave} = 1(0.5) + 2(0.25) + 2(0.25) = 1.5 \text{ bits}

CR = \frac{2}{1.5} \approx 1.33

The variable length $L_{ave}$ equals $B_{ave}$ , so no coding redundancy remains.

Huffman Coding

Produces the optimal variable length codeword allocation while preserving decodability. Reduces the source by merging the least probable grey levels, then assigns codes back through the reductions.

Example:

An image has 4 grey levels with probabilities 0.4, 0.3, 0.2, 0.1.

1 / 6

List the sources in descending order of probability. The last 2 have the lowest probabilities and are merged first.

Add the 2 lowest probabilities, 0.2 and 0.1, into 0.3. Place 0.3 in column 1 so the column stays in descending order. The other sources carry over.

Add the 2 lowest probabilities, 0.3 and 0.3, into 0.6. Place 0.6 in column 2 so the column stays in descending order. The other sources carry over. 2 sources remain, so the reduction stops.

Start from the last column. Assign 0 to the upper source and 1 to the lower source.

In column 1, the 0.6 source with code 0 splits into 0.3 and 0.3. Append 0 to the code of the upper source and 1 to the lower source. The other sources keep their codes.

In column 0, the 0.3 source with code 01 splits into 0.2 and 0.1. Append 0 to the code of the upper source and 1 to the lower source. The other sources keep their codes. These are the final codewords. Average length is 1.9 bits per pixel.

/* Without script nothing can step, so show the finished table and every note in sequence. Unscoped, so each rule keeps the .huffman prefix. */ .huffman .table .off { opacity: 1; } .huffman .table .cell.current rect { fill: transparent; } .huffman .bar, .huffman .foot { display: none; } .huffman .stack { display: block; } .huffman .stack > .step { opacity: 1; visibility: visible; margin-top: 16px; }

Codewords:

Grey level	$P$	Codeword	$l$
$a_1$	0.4	1	1
$a_2$	0.3	00	2
$a_3$	0.2	010	3
$a_4$	0.1	011	3

L_{ave} = 0.4(1) + 0.3(2) + 0.2(3) + 0.1(3) = 1.9 \text{ bits}

B_{ave} \approx 1.85 \text{ bits}

CR = \frac{2}{1.9} \approx 1.05

A fixed length code needs 2 bits per pixel for 4 grey levels.

Decodability

Code

A code assigns a codeword to each grey level. A codeword is a finite sequence of bits.

Encoded stream
Concatenation of the codewords of all pixels in order, with no separators.
Codebook
The mapping between grey levels and codewords.

Example:

For the variable code above, the pixels white, grey, black give the stream 01011.

Unique Decodability

A fixed length code is always uniquely decodable.

A variable length code is uniquely decodable iff every bit stream can be split into codewords in exactly 1 way.

The stream has no fixed boundaries, so the decoder must find where each codeword ends. A codeword that is a prefix of another makes this ambiguous.

Example:

For the code $a = 0$ , $b = 01$ , $c = 1$ , the stream 01 decodes as $b$ , or as $a$ followed by $c$ .

Prefix Code

A code is a prefix code iff no codeword is a prefix of another codeword.

Codewords sit only at the leaves of the code tree
A codeword is recognised as soon as its last bit is read, with no lookahead
Every prefix code is uniquely decodable
Huffman codes are prefix codes

Decoding a prefix code:

Read bits until they match a codeword
Output the grey level and clear the bits read
Repeat from the next bit

Example:

For the variable code in the table above, the stream 010110 splits as 0, 10, 11, 0. It decodes to white, grey, black, white.