Adaptive dimensionality reduction techniques for tree-structured vector quantization

It is well-known that the exorbitant complexity of vector quantization´s codebook design and encoding process have hindered the vector quantization based coding systems for real-time implementations. Tree-structured vector quantization (TSVQ) is one of the most efficient techniques to solve these problems. However, the encoder´s memory requirement has increased as compared with the conventional full search vector quantization. To tackle this drawback and further reduce the searching complexity of TSVQ, new multisubspace tree-structured vector quantization design and encoding techniques are proposed in this paper. During the tree codebook generation process, each nonterminal node of the tree is associated with a partition (or region) and the child nodes are generated by further partitioning of these regions individually. Thus, different distortion measures can be used in different partitions for the node splitting. Based on this idea, the proposed multisubspace TSVQ design algorithms perform the vector quantization in spatial domain while using specially designed subspace distortions in transform domain as cost functions in the optimization process. Due to the energy compaction property of orthonormal transforms, dimensionality reduction is permitted by disregarding the components of minimal energy. The conventional Euclidean distortion is, therefore, adaptively replaced by dimension reduced transform domain subspace distortions based on the local statistics of the partition. Experimental results show that exceptionally low subspace dimension can be used in multisubspace TSVQ based on a fixed transform domain to obtain a similar performance as the conventional TSVQ or single subspace TSVQ. For example, a 256-level and 4×4 image multisubspace TSVQ using binary tree and 1-dimensional subspace distortions achieved almost 63 times computational reduction and 5 times storage reduction when compared with conventional full search vector quantization. In addition, the proposed generalized multisubspace TSVQ design algorithm is a general TSVQ design algorithm and which can also be utilized as a fast codebook design algorithm