Full-Searching-Equivalent Vector Quantization Method Using Two-Bounds Triangle Inequality

• Autorzy: Chang C-C. , Chen C-C.
• Języki publikacji: EN

Abstrakty

EN

The encoding process of vector quantization (VQ) is indeed computational complex and time consuming. Compared with actual Euclidean distance computation, some inequalities can generate estimations with less computation to filter out the impossible codevectors as well as to reduce the computation time. In this paper, we introduce a new estimation for the Euclidean distance using two-bounds triangle inequality. The experimental results show that our proposed scheme can reduce Euclidean distance computation by 71% to 94% for full search. Having been proved, our proposed scheme can reduce the computing time by 42% to 51%.

Słowa kluczowe

EN

full-searching-equivalent; triangle inequality; vector quantisation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 1-2
• Strony: 25--37
• Opis fizyczny: bibliogr. 17 poz., fot., tab.

Twórcy

autor

Chang C-C.

autor

Chen C-C.

• Department of Information Engineering and Computer Science Feng Chia University 100 Wenhwa Rd., Seatwen, Taichung 40724, Taiwan, R.O.C.,

Bibliografia

• [1] N. M. Nasarabadi and R. A. King, "Image coding using vector quantization: A review," IEEE Transactions on Communications, Vol. 36, pp. 957-971, Aug. 1988.
• [2] Y. Linde, A. Buzo, and R. M. Gray, "An algorithm for vector quantizer design," IEEE Transactions on Communications, Vol. 28, pp. 84-95, Jan. 1980.
• [3] C. C. Chang and Y. C. Hu, "A fast LBG codebook training algorithm for vector quantization," IEEE Transactions on Consumer Electronics, Vol. 44, Issue: 4, pp. 1201-1208, Nov. 1998.
• [4] C. M. Huang, Q. Bi, G. S. Stiles, and R. W. Harris, "Fast full search equivalent encoding algorithm for image compression using vector quantization," IEEE Trans. Image Processing, Vol. 1, pp. 413-416, July 1992.
• [5] S. J. Baek, B. K. Jeon, and K. M. Sung, "A fast encoding algorithm for vector quantization," IEEE Signal Processing Letters, Vol. 4, pp. 325-327, Dec. 1997.
• [6] J. Mielikainen, "A novel full-search vector quantization algorithm based on the law of cosines," IEEE Signal Processing Letters, Vol. 9, No. 6, pp. 175-176, June 2002.
• [7] Z. Pan, K. Kotani, and T. Ohmi, "An improved full-search-equivalent vector quantization method using the law of cosines," IEEE Signal Processing Letters, Vol. 11, Issue: 2, pp. 247-250, Feb. 2004.
• [8] Z. Pan, K. Kotani, and T. Ohmi, "A unified projection method for fast search of vector quantization," IEEE Signal Processing Letters, Vol. 11, Issue: 7, pp. 637-640, July 2004.
• [9] C. C. Chang and I. C. Lin, "Novel full-search schemes for speeding up image coding using vector quantization," Real-Time Imaging, Vol. 10, Issue: 2, pp. 95-102, April 2004.
• [10] L. Guan and M. Kamel, "Equal-average hyperplane partitioning method for vector quantization of image data," Pattern Recognition Letters, Vol. 13, Issue: 10, pp. 693-699, Oct. 1992.
• [11] J. Z. C. Lai and Yi-Ching Liaw, "Fast-searching algorithm for vector quantization using projection and triangular inequality," IEEE Transactions on Image Processing, Vol. 13, Issue: 12, pp. 1554-1558, Dec. 2004.
• [12] R. F. Chang, W. T. Chen, and J. S. Wang, "Image sequence coding adaptive tree structure vector quantization with multipath searching" IEE Proceedings on Communications, Speech and Vision, Vol. 1, pp. 9-14, 1992.
• [13] C. C. Chang and T. S. Chen, "New tree-structured vector quantization with closest-coupled multipath searching method" Optical Engineering, Vol. 36, No. 6, pp. 1713-1720, 1997.
• [14] C. D. Bei and R. Gray, "An Improvement of the Minimum Distortion Encoding Algorithm for Vector Quantization," IEEE Transactions on Communications, Vol. 33, Issue: 10, pp. 1132-1133, Oct. 1985.
• [15] K. K. Paliwal and V. Ramasubramanian, "Effect of Ordering the Codebook on the Efficiency of the Partial Distance Search Algorithm for Vector Quantization," IEEE Transactions on Communications, Vol. 37, No. 5, pp. 538-540, MAY 1989.
• [16] C. C. Chang, J. S. Chou, and T. S. Chen, "An efficient computation of Euclidean distances using approximated look-up table," IEEE Transactions on Circuits and Systems for Video Technology, Vol. 10, No. 4, pp. 594-599, June 2000.
• [17] Howard W. Eves, A Survey of Geometry, Vol. 2, Allyn and Bacon, Boston, U.S.A., 1963.