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

Zhibin PAN  Koji KOTANI  Tadahiro OHMI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.9   pp.2218-2222
Publication Date: 2005/09/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.9.2218
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Image Processing and Video Processing
Keyword: 
encoding performance,  fast search,  vector quantization,  statistical features,  EEENNS method,  IEENNS method,  

Full Text: PDF(682.5KB)
>>Buy this Article


Summary: 
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 L2 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 L2 norm feature anymore in fast VQ encoding if the mean and the variance are used simultaneously as proposed in IEENNS method. In other words, L2 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 L2 norm feature so that it confirmed the correctness of the mathematical analysis.