An Improved Tree-Structured Vector Quantizer
Tree-structured vector quantization (TSVQ) is an important alternative to full-search vector quantization since it reduces the encoding search complexity from O ( N ) to O(log(N)) , where N is the decoder codebook size, while incurring some additional distortion. Typically, the methods for designing trees are greedy, growing the trees outward from the root, node-by-node, by minimizing a suitable cost function at each node. The optimization at each non-leaf node does not, in general, reflect the node’s eventual role as a discriminant function, partitioning the input space in order to minimize the distortion incurred at the descendent leaves. In the splitting algorithm [l], for example, the test vectors at a non-leaf node are chosen to minimize the distortion incurred ut the given node, instead of minimizing the distortion at the leaves. The resulting tree may be improved simply by modifying individual nodes of the tree in order to achieve better agreement with nearest neighbor classification at the leaves. As an example, consider the TSVQ solutions of Figure 1. The sub-optimal solution of Figure l a was achieved