Fast Codevector Search Algorithm for 3-D Vector Quantized Codebook
This paper presents a very simple and efficient
algorithm for codebook search, which reduces a great deal of
computation as compared to the full codebook search. The algorithm
is based on sorting and centroid technique for search. The results
table shows the effectiveness of the proposed algorithm in terms of
computational complexity. In this paper we also introduce a new
performance parameter named as Average fractional change in pixel
value as we feel that it gives better understanding of the closeness of
the image since it is related to the perception. This new performance
parameter takes into consideration the average fractional change in
each pixel value.
[1] Jeng-Shyang Pan, Zhe-Ming Lu, and Sheng-He Sun.: ÔÇÿAn Efficient
Encoding Algorithm for Vector Quantization Based on Subvector
Technique-, IEEE Transactions on image processing, vol 12 No. 3
March 2003.
[2] R. M. Gray.: ÔÇÿVector quantization-, IEEE ASSP Marg, Apr. 1984, pp. 4-
29.
[3] Y. Linde, A. Buzo, and R. M. Gray.: ÔÇÿAn algorithm for vector quantizer
design," IEEE Trans. Commun.-, vol. COM-28, no. 1, 1980, pp. 84-95.
[4] A. Gersho, R.M. Gray.: ÔÇÿVector Quantization and Signal Compressio-,
Kluwer Academic Publishers, Boston, MA, 1991.
[5] C. D. Bei and R. M. Gray.: ÔÇÿAn improvement of the minimum distortion
encoding algorithm for vector quantization-, IEEE Trans. Commun.,vol.
33, no. 10, pp. 1132-1133, Oct. 1985.
[6] Momotaz Begum, Nurun Nahar, Kaneez Fatimah, M. K. Hasan, and M.
A. Rahaman: ÔÇÿAn Efficient Algorithm for Codebook Design in
Transform Vector Quantization-, WSCG-2003, February 3-7, 2003.
[7] Robert Li and Jung Kim: ÔÇÿImage Compression Using Fast Transformed
Vector Quantization-, IEEE Applied Imagery Pattern Recognition
Workshop, 2000 Proceedings 29th Volume , Issue , 2000 Page(s):141 -
145.
[8] Zhibin Pan; Kotani, K.; Ohmi, T., ÔÇÿEnhanced fast encoding method for
vector quantization by finding an optimally-ordered Walsh transform
kernel-, ICIP 2005, IEEE International Conference, Volume 1, Issue,
11-14, Page(s): I - 573-6, Sept. 2005.
[9] Guan, L., and Kamel, M. : ÔÇÿEqual-average hyperplane partitioning
method for vector quantization of image data-, Patt. Recognit. Lett.,
1992, pp. 693-699.
[10] Lee, H., and Chen, L. H. : ÔÇÿFast closest codevector search algorithms for
vector quantization-, Signal Process., 1995, 43, pp. 323-331.
[11] Z. Li, and Z.- M. Lu. : ÔÇÿFast codevector search scheme for 3D mesh
model vector quantization-, Electron. Lett., 2008, 44, pp. 104-105.
[12] Princeton University, "3D model search engine",
http://shape.cs.princeton.edu
[13] Chin-Chen Chang, Wen-Chuan Wu, " Fast Planar-Oriented Ripple
Search Algorithm for Hyperspace VQ Codebook", IEEE Transaction on
image processing, vol 16, no. 6, June 2007.
[14] C. C. Chang and T. S. Chen, "New tree-structured vector quantization
with closest-coupled multipath searching method," Opt. Eng., vol. 36,
no. 6, pp. 1713-1720, Jun. 1997.
[15] C. C. Chang and I. C. Lin, "Fast search algorithm for vector quantization
without extra look-up table using declustered subcodebooks," IEE Proc.
Vis., Image, Signal Process., vol. 152, no. 5, pp. 513-519, Oct.2005.
[16] C. C. Chang, D. C. Lin, and T. S. Chen, "An improved VQ codebook
search algorithm using principal component analysis," J. Vis. Commun.
Image Represent., vol. 8, no. 1, pp. 27-37, Mar. 1997.
[17] C. C. Chang, F. J. Shiue, and T. S. Chen, "Tree structured vector
quantization with dynamic path search," in Proc. Int. Workshop on
Multimedia Network Systems, Aizu, Japan, pp. 536 -541, Sep. 1999.
[18] R. M. Gray and Y. Linde, "Vector quantization and predictive quantizers
for gauss-markov sources," IEEE Trans. Commun., vol. 30, no. 2, pp.
381-389, Feb. 1982.
[19] C. M. Huang, Q. Bi, G. S. Stiles, and R. W. Harris, "Fast full-search
equivalent encoding algorithms for image compression using vector
quantization," IEEE Trans. Image Process., vol. 1, no. 3, pp. 413-416,
Jul. 1992.
[20] Y. C. Hu and C. C. Chang, "An effective codebook search algorithm for
vector quantization", Imag. Sci. J., vol. 51, no. 4, pp. 221-234, Dec.
2003.
[21] C. H. Lee and L. H. Chen, "High-speed closest codeword search
algorithm for vector quantization," Signal Process., vol. 43, no. 3,
pp.323-331, May 1995.
[22] L. Torres and J. Huguet, "An improvement on codebook search for
vector quantisation", IEEE Trans. Commun., vol. 42, no. 2, pp. 208-210,
Feb. 1994.
[23] S. J. Wang and C. H. Yang, "Hierarchy-oriented searching algorithms
using alternative duplicate codewords for vector quantization
mechanism," Appl. Math. Comput., vol. 162, no. 234, pp. 559-576, Mar.
2005.
[24] S. C. Tai, C. C. Lai, and Y. C. Lin, "Two fast nearest neighbor searching
algorithms for image vector quantization," IEEE Trans. Commun., vol.
44, no. 12, pp. 1623-1628, Dec. 1996.
[25] C. Bei, R.M. Gray, ÔÇÿÔÇÿAn improvement of the minimum distortion
encoding algorithm for vector quantization--, IEEE Trans. Commun.33,
1985, pp. 1132-1133.
[26] S.H. Huang, S.H. Chen, ÔÇÿÔÇÿFast encoding algorithm for VQ-based image
coding--, Electron. Lett. Vol. 26, issue 19, 1990, pp. 1618-1619.
[27] W. Li, E. Salari, ÔÇÿÔÇÿA fast vector quantization encoding method for image
compression--, IEEE Trans. Circ. Syst. Vid. Vol 5, 1995, pp. 119-123.
[28] C.H. Hsieh, Y.J. Liu, ÔÇÿÔÇÿFast search algorithms for vector quantization of
images using multiple triangle inequalities and wavelet transform--,
IEEE Trans. Image Process. Vol. 9, issue 3, 2000, pp. 321-328.
[29] S.W. Ra, J.K. Kim, ÔÇÿÔÇÿA fast mean-distance-ordered partial codebook
search algorithm for image vector quantization--, IEEE Trans. Circuits-
II, vol. 40, issue 9, 1993, pp. 576-579.
[30] K.S. Wu, J.C. Lin, ÔÇÿÔÇÿFast VQ encoding by an efficient kick-out
condition--, IEEE Trans. Circ. Syst. Vid., vol.10, issue 1, 2000, pp. 59-
62.
[31] J.S. Pan, Z.M. Lu, S.H. Sun, ÔÇÿÔÇÿAn efficient encoding algorithm for
vector quantization based on subvector technique--, IEEE Trans. Image
Process. Vol 12, issue 3, 2003, pp. 265-270.
[32] B.C. Song, J.B. Ra, ÔÇÿÔÇÿA fast algorithm for vector quantization using L2-
norm pyramid of codewords--, IEEE Trans. Image Process. Vol. 4, issue
12, 2002, pp. 325-327.
[33] Z. Pan, K. Kotani, T. Ohmi, ÔÇÿÔÇÿFast encoding method for vector
quantization using modified L2-norm pyramid--, IEEE Signal Process.
Lett. Vol. 12, issue 9, 2005, pp. 609-612.
[34] Y. Chen, B. Hwang, C. Chiang, "Fast VQ codebook search algorithm for
grayscale image coding", Image and Vision Compu. 26, 2008, pp. 657-
666.
[35] Dr. H. B. Kekre, Ms. Tanuja K. Sarode, "Binary Tree Based Fast Search
Algorithm for Closest Codevector in the Codebook for Vector
Quantization", SPIT-IEEE Colloquium 2007, SPCE, Mumbai, 4th - 5th
February 2007.
[36] Shu-Chuan Chu, Zhe-Ming Lu, Jeng-Shyang Pan, "Hadamard transform
based fast codeword search algorithm for high-dimensional VQ
encoding", Information Sciences, 177, 2007, pp. 734-746.
[37] Jim Z.C. Lai, Yi-Ching Liaw, and Julie Liu, "A fast VQ codebook
generation algorithm using codeword displacement" , Pattern Recogn.
vol. 41, no. 1, pp 315-319, 2008.
[38] Y.C. Liaw, J.Z.C. Lai, W. Lo, Image restoration of compressed image
using classified vector quantization, Pattern Recogn. vol. 35, No. 2, pp
181-192, 2002.
[39] N.M. Nasrabadi, Y. Feng, Image compression using address vector
quantization, IEEE Trans. Commun. vol. 38 No. 12, pp. 2166-2173,
1990.
[40] J. Foster, R.M. Gray, M.O. Dunham, Finite state vector quantization for
waveform coding, IEEE Trans. Inf. Theory vol. 31, No. 3, pp. 348-359,
1985.
[41] T. Kim, Side match and overlap match vector quantizers for images,
IEEE Trans. Image Process. vol. 1, No. 2, pp. 170-185, 1992.
[42] J.Z.C. Lai, Y.C. Liaw, W. Lo, Artifact reduction of JPEG coded images
using mean-removed classified vector quantization, Signal Process. vol.
82, No. 10, pp. 1375-1388, 2002.
[43] K.N. Ngan, H.C. Koh, Predictive classified vector quantization, IEEE
Trans. Image Process. vol. 1, No. 3, pp. 269-280, 1992.
[44] C.H. Hsieh, J.C. Tsai, Lossless compression of VQ index with search
order coding, IEEE Trans. Image Process. vol. 5, No. 11, pp. 1579-
1582, 1996.
[45] J.Z.C. Lai, J.Y. Yen, Inverse error-diffusion using classified vector
quantization, IEEE Trans. Image Process. vol. 7, No. 12, pp. 1753-
1758, 1998.
[46] P.C. Chang, C.S. Yu, T.H. Lee, "Hybrid LMS-MMSE inverse halftoning
technique", IEEE Trans. Image Process. vol. 10, No. 1, pp. 95-103,
2001.
[47] C. Garcia and G. Tziritas, "Face detection using quantized skin color
regions merging and wavelet packet analysis," IEEE Trans. Multimedia,
vol. 1, no. 3, pp. 264-277, Sep. 1999.
[48] H. Y. M. Liao, D. Y. Chen, C. W. Su, and H. R. Tyan, "Real-time event
detection and its applications to surveillance systems," in Proc. IEEE
Int. Symp. Circuits and Systems, Kos, Greece, pp. 509-512, May 2006.
[49] J. Zheng and M. Hu, "An anomaly intrusion detection system based on
vector quantization," IEICE Trans. Inf. Syst., vol. E89-D, no. 1, pp. 201-
210, Jan. 2006.
[50] Ahmed A. Abdelwahab, Nora S. Muharram, "A Fast Codebook Design
Algorithm Based on a Fuzzy Clustering Methodology", International
Journal of Image and Graphics, vol. 7, no. 2 pp. 291-302, 2007.
[1] Jeng-Shyang Pan, Zhe-Ming Lu, and Sheng-He Sun.: ÔÇÿAn Efficient
Encoding Algorithm for Vector Quantization Based on Subvector
Technique-, IEEE Transactions on image processing, vol 12 No. 3
March 2003.
[2] R. M. Gray.: ÔÇÿVector quantization-, IEEE ASSP Marg, Apr. 1984, pp. 4-
29.
[3] Y. Linde, A. Buzo, and R. M. Gray.: ÔÇÿAn algorithm for vector quantizer
design," IEEE Trans. Commun.-, vol. COM-28, no. 1, 1980, pp. 84-95.
[4] A. Gersho, R.M. Gray.: ÔÇÿVector Quantization and Signal Compressio-,
Kluwer Academic Publishers, Boston, MA, 1991.
[5] C. D. Bei and R. M. Gray.: ÔÇÿAn improvement of the minimum distortion
encoding algorithm for vector quantization-, IEEE Trans. Commun.,vol.
33, no. 10, pp. 1132-1133, Oct. 1985.
[6] Momotaz Begum, Nurun Nahar, Kaneez Fatimah, M. K. Hasan, and M.
A. Rahaman: ÔÇÿAn Efficient Algorithm for Codebook Design in
Transform Vector Quantization-, WSCG-2003, February 3-7, 2003.
[7] Robert Li and Jung Kim: ÔÇÿImage Compression Using Fast Transformed
Vector Quantization-, IEEE Applied Imagery Pattern Recognition
Workshop, 2000 Proceedings 29th Volume , Issue , 2000 Page(s):141 -
145.
[8] Zhibin Pan; Kotani, K.; Ohmi, T., ÔÇÿEnhanced fast encoding method for
vector quantization by finding an optimally-ordered Walsh transform
kernel-, ICIP 2005, IEEE International Conference, Volume 1, Issue,
11-14, Page(s): I - 573-6, Sept. 2005.
[9] Guan, L., and Kamel, M. : ÔÇÿEqual-average hyperplane partitioning
method for vector quantization of image data-, Patt. Recognit. Lett.,
1992, pp. 693-699.
[10] Lee, H., and Chen, L. H. : ÔÇÿFast closest codevector search algorithms for
vector quantization-, Signal Process., 1995, 43, pp. 323-331.
[11] Z. Li, and Z.- M. Lu. : ÔÇÿFast codevector search scheme for 3D mesh
model vector quantization-, Electron. Lett., 2008, 44, pp. 104-105.
[12] Princeton University, "3D model search engine",
http://shape.cs.princeton.edu
[13] Chin-Chen Chang, Wen-Chuan Wu, " Fast Planar-Oriented Ripple
Search Algorithm for Hyperspace VQ Codebook", IEEE Transaction on
image processing, vol 16, no. 6, June 2007.
[14] C. C. Chang and T. S. Chen, "New tree-structured vector quantization
with closest-coupled multipath searching method," Opt. Eng., vol. 36,
no. 6, pp. 1713-1720, Jun. 1997.
[15] C. C. Chang and I. C. Lin, "Fast search algorithm for vector quantization
without extra look-up table using declustered subcodebooks," IEE Proc.
Vis., Image, Signal Process., vol. 152, no. 5, pp. 513-519, Oct.2005.
[16] C. C. Chang, D. C. Lin, and T. S. Chen, "An improved VQ codebook
search algorithm using principal component analysis," J. Vis. Commun.
Image Represent., vol. 8, no. 1, pp. 27-37, Mar. 1997.
[17] C. C. Chang, F. J. Shiue, and T. S. Chen, "Tree structured vector
quantization with dynamic path search," in Proc. Int. Workshop on
Multimedia Network Systems, Aizu, Japan, pp. 536 -541, Sep. 1999.
[18] R. M. Gray and Y. Linde, "Vector quantization and predictive quantizers
for gauss-markov sources," IEEE Trans. Commun., vol. 30, no. 2, pp.
381-389, Feb. 1982.
[19] C. M. Huang, Q. Bi, G. S. Stiles, and R. W. Harris, "Fast full-search
equivalent encoding algorithms for image compression using vector
quantization," IEEE Trans. Image Process., vol. 1, no. 3, pp. 413-416,
Jul. 1992.
[20] Y. C. Hu and C. C. Chang, "An effective codebook search algorithm for
vector quantization", Imag. Sci. J., vol. 51, no. 4, pp. 221-234, Dec.
2003.
[21] C. H. Lee and L. H. Chen, "High-speed closest codeword search
algorithm for vector quantization," Signal Process., vol. 43, no. 3,
pp.323-331, May 1995.
[22] L. Torres and J. Huguet, "An improvement on codebook search for
vector quantisation", IEEE Trans. Commun., vol. 42, no. 2, pp. 208-210,
Feb. 1994.
[23] S. J. Wang and C. H. Yang, "Hierarchy-oriented searching algorithms
using alternative duplicate codewords for vector quantization
mechanism," Appl. Math. Comput., vol. 162, no. 234, pp. 559-576, Mar.
2005.
[24] S. C. Tai, C. C. Lai, and Y. C. Lin, "Two fast nearest neighbor searching
algorithms for image vector quantization," IEEE Trans. Commun., vol.
44, no. 12, pp. 1623-1628, Dec. 1996.
[25] C. Bei, R.M. Gray, ÔÇÿÔÇÿAn improvement of the minimum distortion
encoding algorithm for vector quantization--, IEEE Trans. Commun.33,
1985, pp. 1132-1133.
[26] S.H. Huang, S.H. Chen, ÔÇÿÔÇÿFast encoding algorithm for VQ-based image
coding--, Electron. Lett. Vol. 26, issue 19, 1990, pp. 1618-1619.
[27] W. Li, E. Salari, ÔÇÿÔÇÿA fast vector quantization encoding method for image
compression--, IEEE Trans. Circ. Syst. Vid. Vol 5, 1995, pp. 119-123.
[28] C.H. Hsieh, Y.J. Liu, ÔÇÿÔÇÿFast search algorithms for vector quantization of
images using multiple triangle inequalities and wavelet transform--,
IEEE Trans. Image Process. Vol. 9, issue 3, 2000, pp. 321-328.
[29] S.W. Ra, J.K. Kim, ÔÇÿÔÇÿA fast mean-distance-ordered partial codebook
search algorithm for image vector quantization--, IEEE Trans. Circuits-
II, vol. 40, issue 9, 1993, pp. 576-579.
[30] K.S. Wu, J.C. Lin, ÔÇÿÔÇÿFast VQ encoding by an efficient kick-out
condition--, IEEE Trans. Circ. Syst. Vid., vol.10, issue 1, 2000, pp. 59-
62.
[31] J.S. Pan, Z.M. Lu, S.H. Sun, ÔÇÿÔÇÿAn efficient encoding algorithm for
vector quantization based on subvector technique--, IEEE Trans. Image
Process. Vol 12, issue 3, 2003, pp. 265-270.
[32] B.C. Song, J.B. Ra, ÔÇÿÔÇÿA fast algorithm for vector quantization using L2-
norm pyramid of codewords--, IEEE Trans. Image Process. Vol. 4, issue
12, 2002, pp. 325-327.
[33] Z. Pan, K. Kotani, T. Ohmi, ÔÇÿÔÇÿFast encoding method for vector
quantization using modified L2-norm pyramid--, IEEE Signal Process.
Lett. Vol. 12, issue 9, 2005, pp. 609-612.
[34] Y. Chen, B. Hwang, C. Chiang, "Fast VQ codebook search algorithm for
grayscale image coding", Image and Vision Compu. 26, 2008, pp. 657-
666.
[35] Dr. H. B. Kekre, Ms. Tanuja K. Sarode, "Binary Tree Based Fast Search
Algorithm for Closest Codevector in the Codebook for Vector
Quantization", SPIT-IEEE Colloquium 2007, SPCE, Mumbai, 4th - 5th
February 2007.
[36] Shu-Chuan Chu, Zhe-Ming Lu, Jeng-Shyang Pan, "Hadamard transform
based fast codeword search algorithm for high-dimensional VQ
encoding", Information Sciences, 177, 2007, pp. 734-746.
[37] Jim Z.C. Lai, Yi-Ching Liaw, and Julie Liu, "A fast VQ codebook
generation algorithm using codeword displacement" , Pattern Recogn.
vol. 41, no. 1, pp 315-319, 2008.
[38] Y.C. Liaw, J.Z.C. Lai, W. Lo, Image restoration of compressed image
using classified vector quantization, Pattern Recogn. vol. 35, No. 2, pp
181-192, 2002.
[39] N.M. Nasrabadi, Y. Feng, Image compression using address vector
quantization, IEEE Trans. Commun. vol. 38 No. 12, pp. 2166-2173,
1990.
[40] J. Foster, R.M. Gray, M.O. Dunham, Finite state vector quantization for
waveform coding, IEEE Trans. Inf. Theory vol. 31, No. 3, pp. 348-359,
1985.
[41] T. Kim, Side match and overlap match vector quantizers for images,
IEEE Trans. Image Process. vol. 1, No. 2, pp. 170-185, 1992.
[42] J.Z.C. Lai, Y.C. Liaw, W. Lo, Artifact reduction of JPEG coded images
using mean-removed classified vector quantization, Signal Process. vol.
82, No. 10, pp. 1375-1388, 2002.
[43] K.N. Ngan, H.C. Koh, Predictive classified vector quantization, IEEE
Trans. Image Process. vol. 1, No. 3, pp. 269-280, 1992.
[44] C.H. Hsieh, J.C. Tsai, Lossless compression of VQ index with search
order coding, IEEE Trans. Image Process. vol. 5, No. 11, pp. 1579-
1582, 1996.
[45] J.Z.C. Lai, J.Y. Yen, Inverse error-diffusion using classified vector
quantization, IEEE Trans. Image Process. vol. 7, No. 12, pp. 1753-
1758, 1998.
[46] P.C. Chang, C.S. Yu, T.H. Lee, "Hybrid LMS-MMSE inverse halftoning
technique", IEEE Trans. Image Process. vol. 10, No. 1, pp. 95-103,
2001.
[47] C. Garcia and G. Tziritas, "Face detection using quantized skin color
regions merging and wavelet packet analysis," IEEE Trans. Multimedia,
vol. 1, no. 3, pp. 264-277, Sep. 1999.
[48] H. Y. M. Liao, D. Y. Chen, C. W. Su, and H. R. Tyan, "Real-time event
detection and its applications to surveillance systems," in Proc. IEEE
Int. Symp. Circuits and Systems, Kos, Greece, pp. 509-512, May 2006.
[49] J. Zheng and M. Hu, "An anomaly intrusion detection system based on
vector quantization," IEICE Trans. Inf. Syst., vol. E89-D, no. 1, pp. 201-
210, Jan. 2006.
[50] Ahmed A. Abdelwahab, Nora S. Muharram, "A Fast Codebook Design
Algorithm Based on a Fuzzy Clustering Methodology", International
Journal of Image and Graphics, vol. 7, no. 2 pp. 291-302, 2007.
@article{"International Journal of Information, Control and Computer Sciences:56209", author = "H. B. Kekre and Tanuja K. Sarode", title = "Fast Codevector Search Algorithm for 3-D Vector Quantized Codebook", abstract = "This paper presents a very simple and efficient
algorithm for codebook search, which reduces a great deal of
computation as compared to the full codebook search. The algorithm
is based on sorting and centroid technique for search. The results
table shows the effectiveness of the proposed algorithm in terms of
computational complexity. In this paper we also introduce a new
performance parameter named as Average fractional change in pixel
value as we feel that it gives better understanding of the closeness of
the image since it is related to the perception. This new performance
parameter takes into consideration the average fractional change in
each pixel value.", keywords = "Vector Quantization, Data Compression, Encoding,Searching.", volume = "3", number = "2", pages = "362-5", }
