Data Compression Lec #17

Bintrees
Instead of partitioning the image into quadrants, it can be recursively split in halves. This is the principle of the bintree method. Figure 4.151a–e shows the 8×8 image of Figure 4.148a and the first four steps in its bintree partitioning. Figure 4.151f shows part of the resulting bintree.

It is easy to see how the bintree method alternates between vertical and horizontal splits, and how the subimages being generated include all those produced by a quadtree plus other ones. As a compression method, bintree partitioning is less efficient than quadtree, but it may be useful in cases where many subimages are needed. A case in point is the WFA (weighted finite automata) method of Section 4.34. The original method uses a quadtree to partition an image into nonoverlapping subsquares, and compresses the image by matching a subsquare with a linear combination of other (possibly bigger) subsquares. An extension of WFA (page 509) uses bintrees to obtain more subimages and therefore better compression.