An enhanced fast encoding method for vector quantization by constructing new feature based on the variances of subvectors

The encoding process of vector quantization (VQ) is a time bottleneck to its practical applications due to it performing a lot of k-dimensional Euclidean distance computations. In order to speed up the process of VQ encoding, it is most important to avoid unnecessary exact Euclidean distance computations as many as possible. This purpose can be realized by first estimating how large Euclidean distance is with just a lighter computation, which requires the estimation for Euclidean distance must be less or equal to Euclidean distance itself. Then, if this estimation is sufficiently large, it can lead to a rejection to current candidate codeword. In order to make an estimation for Euclidean distance, appropriate features of vectors are necessary. By using famous statistical features (i.e. the sum and the variance) of a k-dimensional vector and its two corresponding (k/2)-dimensional subvectors to estimate Euclidean distance first, it is possible to reject most of unlikely codewords for a certain input vector as proposed in the previous works. Under the consideration of using the sum and the variance information as features of vectors, a new feature based on the variances of two subvectors is constructed in this paper to set up a new estimation for Euclidean distance. Meanwhile, a memory-efficiency data structure is proposed for storing all features of a vector to avoid any extra memory requirement compared to the latest previous work. Experimental results confirmed that the proposed search method in this paper is more search efficient.