Locally optimal codebook design for quadtree-based vector quantization

The optimal design of quadtree-based vector quantizers is addressed. Until now, work in this area has focused on optimizing the quadtree structure for a given set of leaf quantizers with little attention spent on the design of the quantizers themselves. In cases where the leaf quantizers were considered, codebooks were optimized without regard to the ultimate quadtree segmentation. However, it is not sufficient to consider each problem independently, as separate optimization leads to an overall suboptimal solution. Rather, joint design of the quadtree structure and the leaf codebooks must be considered for overall optimality. The method we suggest is a “quadtree” constrained version of the entropy-constrained vector quantization design method. To this end, a centroid condition for the leaf codebooks is derived that represents a necessary optimality condition for variable-rate quadtree coding. This condition, when iterated with the optimal quadtree segmentation strategy of Sullivan and Baker (see IEEE Trans. on Image Processing, vol.3, p.327-331, May 1994) results in a monotonically descending rate-distortion cost function, and consequently, an (at least locally) optimal quadtree solution