Binary tree coding

Because it has proven a successful representation for lossless image compression, the binary pyramid is a natural starting point for a general purpose scheme intended for both lossless and lossy coding. The crucial modification for lossy coding is quantization. Experience with lossy schemes such as the DCT and wavelet pyramids shows that many quantized data attain values of zero, and blocking of zeros using runlength coding, end-of-block codewords or trees results in good compression.

As discussed earlier, quadtree schemes block zeros together using leaf codewords. When a leaf codeword appears, all its children are flagged as zeros. This suggests a similar strategy for the binary pyramid. Indeed, because leaf codewords in a binary tree can apply to 2, 4, 8, 16, 32, 64 children, there is good reason to believe they will be more efficient than leaf codewords in a quadtree which can apply only to 4, 16 or 64 children.

All that is required to turn the binary pyramid into a tree is to associate single-pel parents in level H(n) with pairs of children in level H(n-1). This is done as follows:
For n even, each pel in level H(n) has one child n/2 rows above in the same column, and one child n/2 columns to the left in the same row.

For n odd, if a pel's parent is below it , then its children are (n-1)/2 rows below it and (n-1)/2 columns to its left and right.

For n odd, if a pel's parent is to its right, then its children are (n-1)/2 rows below it, one is (n-1)/2 columns to its right, and the other is 3(n-1)/2 columns to its right.

This ordering scheme ensures that a pel's descendants form a square or a 2:1 rectangle. For example, if the tree termination codeword were received for the H4 in the center of this block (same as used earlier):

L4 H1 H3 H1 L4

H1 H2 H1 H2 H1

H3 H1 H4 H1 H3

H1 H2 H1 H2 H1

L4 H1 H3 H1 L4

the decoder would determine that:

The H4 value is zero.
The value of its two children are zero. That is, the H3 in the top row and the H3 in the left hand column are zero.
The children of the H3 in the top row are zero. That is, the two H2's in the second row are zero.
The children of the H3 in the left-hand column are zero. That is, the two H2's in the fourth row are zero.
The children of the H2's are zero. That is, the first two H1's in each row are zero.

In this way, the whole 4 x 4 square would be zeroed.

To confirm that the binary tree representation makes for efficient representation of blocks of zeros, the test images were coded (using the predictor and quantizers described later) with and without leaf codewords. In addition, simple runlength coding of strings of zeros was implemented and tested. The same trend was observed for all the test images: the tree representation with leaf codewords provides most efficient coding.

BTPC 2 also uses the leaf codeword for left siblings on the finest (H1) band to indicate that both siblings are zero. This gives a small compression benefit in coding of the final band.

Next (BTPC 1 predictor) | Previous (Binary pyramids) | Top (BTPC)