Fast Search Method for Vector Quantization by Simultaneously Using Two Subvectors

摘要

Encoding speed is one of the key issues in vector quantization (VQ). In order to effectively reduce computational complexity, before actually computing the expensive real Euclidean distance in VQ, it is possible to estimate the Euclidean distance first by using the statistical features of sum and variance of a k-D vector. The IEENNS method has been proposed to reject most unlikely candidate codewords for the input vector. Furthermore, by partitioning a k-D vector in half to construct its two (k/2)-D subvectors and then apply IEENNS method again to each of the two subvectors separately, SIEENNS method has been reported as well. The SIEENNS method is the most essential subvector-based search method for VQ but it failed to deal with the two subvectors at the same time, which degrades the search performance obviously. This paper aims at generalizing and enhancing state-of-the-art SIEENNS method by means of simultaneously instead of separately using the two subvectors so as to reject more unlikely candidate codewords for the input vector. Mathematical analysis and experimental results confirmed that the proposed method in this paper can significantly improve the search efficiency to 68.3%～82.2% compared to the SIEENNS method.