Fast searching algorithm for vector quantisation based on features of vector and subvector |
| |
Authors: | Chen SX Li FW Zhu WL |
| |
Affiliation: | Electronic Engineering College, University of Electronic Science and Technology of China, Chengdu 610054, People?s Republic of China E-mail: chee420@163.com, Communication and Information Engineering College, ChongQing University of Posts and Telecommunications, ChongQing 400065, People?s Republic of China E-mail: chee420@163.com; |
| |
Abstract: | Vector quantisation (VQ) is an efficient technique for data compression and retrieval. But its encoding requires expensive computation that greatly limits its practical use. A fast algorithm for VQ encoding on the basis of features of vectors and subvectors is presented. Making use of three characteristics of a vector: the sum, the partial sum and the partial variance, a four-step eliminating algorithm is introduced. The proposed algorithm can reject a lot of codewords, while holding the same quality of encoded images as the full search algorithm (FSA). Experimental results show that the proposed algorithm needs only a little computational complexity and distortion calculation against the FSA. Compared with the equal-average equal-variance equal-norm nearest neighbour search algorithm based on the ordered Hadamard transform, the proposed algorithm reduces the number of distortion calculations by 8 to 61%. The average number of operations of the proposed algorithm is ,79% of that of Zhibin?s method for all test images. The proposed algorithm outperforms most of existing algorithms. |
| |
Keywords: | |
|
|