Fast searching algorithm for vector quantisation based on features of vector and subvector

Access Full Text

Fast searching algorithm for vector quantisation based on features of vector and subvector

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Image Processing — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Published

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.

Inspec keywords: image coding; data compression; search problems; vector quantisation; computational complexity; Hadamard transforms

Other keywords: fast searching algorithm; image encoding; full search algorithm; vector quantisation; Hadamard transform; data compression; four-step eliminating algorithm; equal-variance equal-norm nearest neighbour search algorithm; equal-average search algorithm; VQ encoding; computational complexity; data retrieval

Subjects: Computer vision and image processing techniques; Combinatorial mathematics; Computational complexity; Signal processing theory; Integral transforms; Image and video coding; Integral transforms

References

    1. 1)
      • Z.B. Pan , K. Kotani , T. Ohmi . Fast encoding method for image vector quantisation based on multiple appropriate features to estimate euclidean distance. Opt. Rev. , 3 , 161 - 169
    2. 2)
      • S.E. Qian . Fast vector quantisation algorithms based on nearest partition set search. IEEE Trans. Image Process. , 8 , 2422 - 2430
    3. 3)
      • S.W. Ra , J.K. Kim . Fast mean-distance-ordered partial codebook search algorithm for image vector quantisation. IEEE Trans. Circuits Syst. II , 9 , 576 - 579
    4. 4)
      • B.C. Song , J.B. Ra . Fast exhaustive multi-resolution search algorithm based on clustering for efficient image retrieval. J. Vis. Commun. Image R. , 98 - 106
    5. 5)
      • C.H. Lee , L.H. Chen . Fast closest codeword search algorithm for vector quantisation. IEE Proc Vis. Image Signal Process. , 3 , 143 - 148
    6. 6)
      • B.C. Song , J.B. Ra . A fast algorithm for vector quantisation using L2-norm pyramid of codeword. IEEE Trans. Image Process. , 1 , 10 - 15
    7. 7)
      • W.J. Hwang , S.S. Jeng , M.R. Leou . Fast codeword search technique for the encoding of variable-rate vector quantisers. IEE Proc. Vis. Image Signal Process. , 2 , 103 - 108
    8. 8)
      • J.S. Pan , Z.M. Lu , S.H. Sun . An efficient encoding algorithm for vector quantisation based on subvector technique. IEEE Trans. Image Process. , 3 , 265 - 270
    9. 9)
      • Y. Linde , A. Buzo , R.M. Gray . An algorithm for vector quantiser design. IEEE Trans. Commun. , 1 , 84 - 95
    10. 10)
      • Z.B. Pan , K. Kotani , T. Ohmi . Subvector-based fast encoding method for vector quantisation without using two partial variances. Opt. Rev. , 6 , 410 - 416
    11. 11)
      • S.C. Chu , Z.M. Lu , J.S. Pan . Hadamard transform based fast codeword search algorithm for high-dimensional VQ encoding. Inf. Sci. , 3 , 734 - 746
    12. 12)
      • K.S. Wu , J.C. Lin . Fast VQ encoding by an efficient kick-out condition. IEEE Trans. Circuits Syst. Video Technol. , 1 , 59 - 62
    13. 13)
      • C.C. Chang , C.C. Chen . Full-searching-equivalent vector quantisation method using two-bounds triangle inequality. Fundam. Inform. , 25 - 37
    14. 14)
      • S.J. Baek , B.K. Jeon , K.M. Sung . A fast encoding algorithm for vector quantisation. IEEE Signal Process. Lett. , 12 , 325 - 327
    15. 15)
      • Z.M. Lu , S.H. Sun . Equal-average equal-variance equal-norm nearest neighbor search algorithm for vector quantisation. IEICE Trans. Inf. Syst. , 660 - 663
    16. 16)
      • Z.M. Lu , S.C. Chu , K.C. Huang . Equal-average equal-variance equal-norm nearest neighbor codeword search algorithm based on ordered Hadamard transform. Int. J. Innov. Comput., Inf. Control. , 1 , 35 - 41
    17. 17)
      • C.H. Lee , L.H. Chen . High-speed closest codeword search algorithms for vector quantisation. Signal Process. , 323 - 331
    18. 18)
      • C.D. Bei , R.M. Gray . An improvement of the minimum distortion encoding algorithm for vector quantisation. IEEE Trans. Commun. , 10 , 1132 - 1133
    19. 19)
      • C. Zhu , Y. Hua . Image vector quantisation with minimax L∞ distortion. IEEE Signal Process. Lett. , 2 , 25 - 27
    20. 20)
      • J.Z.C. Lai , Y.C. Liaw . Fast-searching algorithm for vector quantisation using projection and triangular inequality. IEEE Trans. Image Process. , 12 , 1554 - 1558
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ipr_20070153
Loading

Related content

content/journals/10.1049/iet-ipr_20070153
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading