Modified Search Order Coding for Vector Quantization Indexes

Chun-Yang Ho; Chaur-Heh Hsieh; Chung-Woei Chao

doi:10.6180/jase.1999.2.3.04

Modified Search Order Coding for Vector Quantization Indexes

Computer Science and Information Engineering

Chun-Yang Ho¹, Chaur-Heh Hsieh², Chung-Woei Chao³

¹Kuang-Wu Institute of Technology and Commerce Peito, 112, Taipei, Taiwan, R. O. C.
²Department of Information Engineering, I-Shou University Kaohsiung, 840, Taiwan, R.O.C.
³Ministry of National Defense Taipei, Taiwan, R. O. C.

Received: March 1, 1999
Accepted: June 17, 1999
Publication Date: September 1, 1999

Download Citation: ||https://doi.org/10.6180/jase.1999.2.3.04

ABSTRACT

Recently, vector quantization (VQ) has been received great attention for image compression. In VQ, each image block is encoded into a quantization index. Search-order coding (SOC) is an efficient compression technique for the VQ indexes. This paper presents a modification of SOC that exploits the correlation of vector-quantized indexes efficiently. For an input index, a novel searching scheme is employed to find out the matched index from the previous indexes and then the corresponding search order of the matched index is sent to the decoder. The search order is encoded with a simple and efficient variable-length code. Experimental results show that the proposed scheme significantly reduces the bit rate without extra coding error. Moreover, the extra computation introduced is negligible.

Keywords: Image compression, Vector quantization, Codevector

REFERENCES

[1] Aravind, A. and Gersho, A., “Image compression based on vector quantization with finite memory,” Opt. Eng., Vol. 26, pp. 570-580, July (1987).
[2] Bezdek, J. C., Fuzzy mathematics in pattern classification, Ph.D Thesis, Cornell University, (1973).
[3] Chen, W. T., Chang, R. F. and Wang, J. S., “Image sequence coding using adaptive finite-state vector quantization,” IEEE Trans. on Circuits and Systems for Video Technolo., Vol. 2, No. 1, pp. 15-24, Mar. (1992).
[4] Foster, J., Gray, R. M. and Dunham, M. O., “Finite-state vector quantization for waveform coding,” IEEE Trans. Inform. Theory, Vol. IT-31, pp. 348-359, May (1985).
[5] Gray, R. M. and Gersho, A., Vector quantization and signal compression, Kluwer Academic Publishers, (1992).
[6] Hsieh, C. H. and Shue, J. S., “Frame adaptive Finite-state vector quantization for image sequence coding,” Signal Processing: Image Commun., Vol.7, pp. 13-26, (1995).
[7] Hsieh, C. H., Tsai, J. C., “Lossless compression of VQ index with search-order coding,” IEEE Trans. Image Processing, Vol. 5, No. 11, pp. 1579-1582, Nov. (1996).
[8] Hsieh, C. H., Tsai, J. C. and Lu, P. C., “Lossless coding of VQ index using index grouping,” IEEE Trans. Commun., Vol. 44, No. 12, pp. 1643-1648, Dec. (1996).
[9] Kim, T., “Side match and overlap match vector quantizers for images,” IEEE Trans. On Image Processing, Vol. 1, No. 2, pp.170-185, April (1992).
[10] Lee, S. J., Yang, K. H., Kim, C. W. and Lee, C. W., “Efficient lossless coding scheme for VQ using dynamic index mapping,” Electronics Letters, Vol. 31, No.17, pp. 1426-1427, Aug. (1995).
[11] Nasrabadi, N. M. and Rizvi, S. A., “Next-state function for Finite-State vector quantization,” IEEE Trans. Image Processing, Vol. 4, No. 12, pp. 1592-1601, Dec. (1995).
[12] Nasrabadi, N. M., Choo, C. Y. and Feng, Y., “Dynamic finite-state vector quantization,” IEEE Trans. Commun., Vol. COM-42, pp. 2145-2154, May 1994.
[13] Nasrabadi, N. M. and Rizvi, S. A., “Next-state functions for finite-state vector quantization,” IEEE Trans. on image processing, Vol. 4, No. 12, pp. 1592-1601, Dec. (1995).
[14] Nasrabadi, N. M. and Feng, Y., “Image compression using address vector quantization,” IEEE Trans. Commun., Vol. 38, pp. 2166-2173, Dec. (1990).
[15] Nasrabadi, N. M., Choo, C. Y. and Feng, Y., “Image compression using address-vector quantization,|” IEEE Trans. Commun., Vol. 38, pp. 2166-2173, Dec. (1990).
[16] Nasrabadi, N. M., Choo, C. Y. and Roy, J. U., “Interframe hierarchical address-vector quantization,” IEEE Journal on Selection Areas in Commun., Vol. 10, No. 5, pp. 960-967, June (1992).