Performance comparison between equal-average equal-variance equal-norm nearest neighbor search (EEENNS) method and improved equal-average equal-variance nearest neighbor search (IEENNS) method for fast encoding of vector quantization

The encoding process of vector quantization (VQ) is a time bottleneck preventing its practical applications. In order to speed up VQ encoding, it is very effective to use lower dimensional features of a vector to estimate how large the Euclidean distance between the input vector and a candidate codeword could be so as to reject most unlikely codewords. The three popular statistical features of the average or the mean, the variance, and L-2 norm of a vector have already been adopted in the previous works individually. Recently, these three statistical features were combined together to derive a sequential EEENNS search method in [6], which is very efficient but still has obvious computational redundancy. This Letter aims at giving a mathematical analysis on the results of EEENNS method further and pointing out that it is actually unnecessary to use L-2 norm feature anymore in fast VQ encoding if the mean and the variance are used simultaneously as proposed in IEENNS method. In other words, L-2 norm feature is redundant for a rejection test in fast VQ encoding. Experimental results demonstrated an approximate 10-20% reduction of the total computational cost for various detailed images in the case of not using L-2 norm feature so that it confirmed the correctness of the mathematical analysis.