A tree-structured locally optimal vector quantizer

A tree-structured VQ (vector quantizer) that performs the nearest-neighbor encoding based on a locally optimal codebook generated by the LBG (Y. Linde, A. Buzo, R.M. Gray, 1980) algorithm is proposed. A design method is given to organize the code words by a quasi-voronoi tree. This tree structure allows the nearest-neighbor encoding without an exhaustive search. For a codebook of size K, encoding an input vector takes an expected number of O(log K) distortion evaluations for dimensionalities below eight; that time complexity is O(K^1/2) in practice for higher dimensionalities. The tree-structured VQ achieves a good compromise between the optimality and encoding speed.