Fast Searching Algorithm for Vector Quantization Based on Subvector Technique

ShanXue CHEN  FangWei LI  WeiLe ZHU  TianQi ZHANG  

IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.7   pp.2035-2040
Publication Date: 2008/07/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.7.2035
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Image Processing and Video Processing
encoding,  computational complexity,  vector quantization,  data compression,  image processing,  

Full Text: PDF>>
Buy this Article

A fast algorithm to speed up the search process of vector quantization encoding is presented. Using the sum and the partial norms of a vector, some eliminating inequalities are constructeded. First the inequality based on the sum is used for determining the bounds of searching candidate codeword. Then, using an inequality based on subvector norm and another inequality combining the partial distance with subvector norm, more unnecessary codewords are eliminated without the full distance calculation. The proposed algorithm can reject a lot of codewords, while introducing no extra distortion compared to the conventional full search algorithm. Experimental results show that the proposed algorithm outperforms the existing state-of-the-art search algorithms in reducing the computational complexity and the number of distortion calculation.