Title :
Fast search method for vector quantization by simultaneously using two subvectors
Author :
Pan, Zhibin ; Kotani, Koji ; Ohmi, Tadahiro
Author_Institution :
Sch. of Electron. & Inf. Eng., Xian Jiaotong Univ., Xi´´an
fDate :
June 23 2008-April 26 2008
Abstract :
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.
Keywords :
mathematical analysis; search problems; vector quantisation; SIEENNS method; fast search method; improved equal-average equal-variance nearest neighbor search method; k-D vector; mathematical analysis; vector quantization; Computational complexity; Degradation; Electronics industry; Encoding; Euclidean distance; Image coding; Industrial electronics; Nearest neighbor searches; Search methods; Vector quantization; Fast search; subvectors; vector quantization;
Conference_Titel :
Multimedia and Expo, 2008 IEEE International Conference on
Conference_Location :
Hannover
Print_ISBN :
978-1-4244-2570-9
Electronic_ISBN :
978-1-4244-2571-6
DOI :
10.1109/ICME.2008.4607538