DESIGN AND PERFORMANCE OF TREE-STRUCTURED VECTOR QUANTIZERS

The design of vector quantizers (VQ) involves the partitioning of a mu ltidimensional space into a finite number of regions. It is desired bu t generally difficult to find the partition that minimizes the expecte d distortion subject to a cost constraint. Tree-structured vector quan tization (TSVQ) reduces the complexity by imposing a hierarchical stru cture on the partitioning. We study the design of optimal tree-structu red vector quantizers that minimize the expected distortion subject to cost functions related to storage cost, encoding rate, or quantizatio n time. The optimal design problem is shown to be intractable in most cases, and heuristic techniques have to be used. We analyze the perfor mance of a general design heuristic based on successive partitioning, and propose a recursively descend optimization criterion for the algor ithm. Experimental results in image compression show the new criterion performs favorably compared with existing ones.