快速搜索算法VQ图像压缩解码电路系统的研究
|
摘要
矢量量化(VQ)是近年来图像压缩研究中的重要技术，广泛应用于语音编码、音视频压缩和远程会议等系统中。在该技术中，减少运算复杂度、降低平均编码比特率、提高恢复图像的质量和便于硬件实现等方面是当前研究的主要方向。
本文首先利用图像内部的空间相关性，提出一种旨在降低平均编码时间的超前预测相关矢量量化快速算法，并对其进行测试。测试结果表明该算法在减少平均编码时间的同时，也降低了平均编码比特率。其次，为减少每个矢量的编码时间，提出一种基于均值排序码书的快速搜索算法，测试结果显示，该算法编码速度是穷尽搜索算法的二十多倍，但是恢复图像的质量大大地降低了。为了弥补这个缺陷，在保持该算法编码速度快这个优点的基础上，从结构并行性和码书排序结构两方面对其改进，得到一种既提高了恢复图像质量，又适合VLSI硬件实
西安理工大学硕士学位论文
现的编码算法。最后结合各个算法的优点，综合考虑各方面性能，给
出一个折衷的快速搜索算法，并且设计出与算法对应的编码电路系统。
该编码电路的FPGA实现及FPGA验证结果表明，本文提出的快速算
法大大地减少了编码时间、有效地提高了恢复图像质量，同时也降低
了硬件实现的难度。
Vector Quantization (VQ) is an important technology in the field of image compression, which is widely used in various applications such as speech coding, audio and video compression, and teleconferencing systems. The current researches include how to cut down the computation complexity, how to reduce the average coding bit rate, how to improve the quality of reconstructed image, and which algorithm to be suitable to VLSI implementation.
In this paper, firstly, based on image spatial correlation, a fast algorithm named advance predictive correlation VQ ( APCVQ) is presented, which aims at reducing the average coding time. The simulation results show that the algorithm have not only cut down the average coding time, but also reduced the average coding bit rate. Then, in order to reduce the coding time of each image vector, a fast algorithm based on
Mean-Order-Search is proposed. The simulation results of this algorithm show that its coding speed is twenty times faster than that of Full Search algorithm (FS), but its reconstructed image is badly ruined. For overcoming this disadvantage and keeping its advantage of short coding time, we improve the algorithm on the two aspects of structure parallelism and codebook order structure, to gain a better coding algorithm, which meets the requirement of reconstructed image and VLSI implementation. Finally, considering the advantages and disadvantages of these algorithms, a trade-off algorithm is proposed. A corresponding VLSI coding circuit system is designed and verified with FPGA. The FPGA post simulation results prove that the trade-off algorithm is an effective fast search algorithm of VQ coding on the three aspects of reducing the coding time, improving the reconstructed image quality, and lowering the difficulty of VLSI implementation.
本文首先利用图像内部的空间相关性，提出一种旨在降低平均编码时间的超前预测相关矢量量化快速算法，并对其进行测试。测试结果表明该算法在减少平均编码时间的同时，也降低了平均编码比特率。其次，为减少每个矢量的编码时间，提出一种基于均值排序码书的快速搜索算法，测试结果显示，该算法编码速度是穷尽搜索算法的二十多倍，但是恢复图像的质量大大地降低了。为了弥补这个缺陷，在保持该算法编码速度快这个优点的基础上，从结构并行性和码书排序结构两方面对其改进，得到一种既提高了恢复图像质量，又适合VLSI硬件实
西安理工大学硕士学位论文
现的编码算法。最后结合各个算法的优点，综合考虑各方面性能，给
出一个折衷的快速搜索算法，并且设计出与算法对应的编码电路系统。
该编码电路的FPGA实现及FPGA验证结果表明，本文提出的快速算
法大大地减少了编码时间、有效地提高了恢复图像质量，同时也降低
了硬件实现的难度。
Vector Quantization (VQ) is an important technology in the field of image compression, which is widely used in various applications such as speech coding, audio and video compression, and teleconferencing systems. The current researches include how to cut down the computation complexity, how to reduce the average coding bit rate, how to improve the quality of reconstructed image, and which algorithm to be suitable to VLSI implementation.
In this paper, firstly, based on image spatial correlation, a fast algorithm named advance predictive correlation VQ ( APCVQ) is presented, which aims at reducing the average coding time. The simulation results show that the algorithm have not only cut down the average coding time, but also reduced the average coding bit rate. Then, in order to reduce the coding time of each image vector, a fast algorithm based on
Mean-Order-Search is proposed. The simulation results of this algorithm show that its coding speed is twenty times faster than that of Full Search algorithm (FS), but its reconstructed image is badly ruined. For overcoming this disadvantage and keeping its advantage of short coding time, we improve the algorithm on the two aspects of structure parallelism and codebook order structure, to gain a better coding algorithm, which meets the requirement of reconstructed image and VLSI implementation. Finally, considering the advantages and disadvantages of these algorithms, a trade-off algorithm is proposed. A corresponding VLSI coding circuit system is designed and verified with FPGA. The FPGA post simulation results prove that the trade-off algorithm is an effective fast search algorithm of VQ coding on the three aspects of reducing the coding time, improving the reconstructed image quality, and lowering the difficulty of VLSI implementation.
引文
【1】 冈萨雷斯．数字图像处理(第二版)．北京：电子工业出版社，2003：pp327-334．
【2】 Lu Guojun. Advances in Digital Image Compression Techniques. Computer Communications, 16(4), 1993:pp202-214.
【3】 B.G. Haskell, P. g. Howard et al.. Image and Video coding-emerging standards and beyond, IEEE, Trans. On CSVT, Vol.8, No.7, Nov. 1998, pp.814.
【4】 ISO/IEC JTC1/SC29 10918-1: JPEG.
【5】 CCITT Recommendation H.263(draft). Vedio codec for audio visual services at P~*64kbit/s, 1999.
【6】 ITU-T Recommendation H.263(draft). Video coding for low bit rate communication, 1997.
【7】 ISO/IEC JTC1/SC29 11172-2: MPEGI, International standard for coding of moving pictures and associated audio for digital storage media at up to about 1.5Mbit/s, 1991.
【8】 ISO/IEC JTC 1/SC29 13818-2: MPEG2, International standard for coding of moving pictures and associated audio information: Video, 1996.
【9】 C.E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J., Vol.27, 1948, pp379-423,623-656.
【10】 B. Jerabek, E Schneider. A. Uhi Comparison of Lossy Image Compression Methods applied to Photorealistic and Graphical Image using Public Domain Sources. http://citeseer.nj.nes.com, April 1998.
【11】 V. Cuperman, A. Gersho. Vector predictive coding of speech at 16kbit/s. IEEE Trans. on Commun., Vol. Com-33, July 1985, pp685-696.
【12】 M.J. Sabin, R. M. Gray. Product code vector quantizers for waveform and voice coding. IEEE Trans. on Acoust., Speech, Signal Processing, Vol.32, June 1984, pp474-488.
【13】 R C. Cosma, K. L. Ochler, E. A. Riskin, R. M. Gray. Using Vector Quantization for Image Processing. Proceeding for IEEE Vol.81, No.9, 1993, pp1326-1341.
【14】 R D. Alessandro, R. Lancini. Video coding scheme using DCT-pyramid Vector Quantization. IEEE Trans. on Image Processing, Vol.4, Mar. 1995, pp309-319.
【15】 Eduardo A. B.da Silva, D. G. Sampson, A successive approximation vector quantizer for wavelet transform image coding. IEEE Trans. on Image Processing, Vol.5, No.2, Feb. 1996, pp299-310.
【16】 Grant A. Davison, Peter R. Cappello, Allen Gersho. Systolic Architecture for Vector Quantization. IEEE Trans. on Acoustics, Speech, and Signal Processing, Oct. 1988, Vol.36, No. 10.
【17】 Kazutoshi Kobayashi. A Study of the Functional Memory Type Parallel Processor.
【18】 Aysegul Cuhadar, Demetrios Sampson, Andy Downton. A scalable parallel approach to vector quantization.
【19】 A. Gersho, R. M. Gray. Vector Quantization and Signal Compression. Boston: Kluwer Academic Publishers, 1992.
【20】 孙圣和，陆哲明．矢量量化技术与应用．北京：科学出版社，2002．
【21】 J.R. Deller, J. G. Proakis, J. H. L. Discrete-Time Processing of Speech Signals. Macmillan Publishing Company, 1993.
【22】 M.R. Soleymani, and S.D. Morgera. An efficient nearest neighbor search method. IEEE Trans. Commun., 1987, 35(4):677-679.
【23】 S.W. Ra and J.K. Kim. A fast mean distant ordered partial codebook
search algorithm for vector quantization. IEEE Tans. Circuit and Systems Ⅱ, 1993,40(9):576-579.
【24】 Xilinx公司. Xilinx Application Note, XAPP119, July 20, 1998.
【2】 Lu Guojun. Advances in Digital Image Compression Techniques. Computer Communications, 16(4), 1993:pp202-214.
【3】 B.G. Haskell, P. g. Howard et al.. Image and Video coding-emerging standards and beyond, IEEE, Trans. On CSVT, Vol.8, No.7, Nov. 1998, pp.814.
【4】 ISO/IEC JTC1/SC29 10918-1: JPEG.
【5】 CCITT Recommendation H.263(draft). Vedio codec for audio visual services at P~*64kbit/s, 1999.
【6】 ITU-T Recommendation H.263(draft). Video coding for low bit rate communication, 1997.
【7】 ISO/IEC JTC1/SC29 11172-2: MPEGI, International standard for coding of moving pictures and associated audio for digital storage media at up to about 1.5Mbit/s, 1991.
【8】 ISO/IEC JTC 1/SC29 13818-2: MPEG2, International standard for coding of moving pictures and associated audio information: Video, 1996.
【9】 C.E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J., Vol.27, 1948, pp379-423,623-656.
【10】 B. Jerabek, E Schneider. A. Uhi Comparison of Lossy Image Compression Methods applied to Photorealistic and Graphical Image using Public Domain Sources. http://citeseer.nj.nes.com, April 1998.
【11】 V. Cuperman, A. Gersho. Vector predictive coding of speech at 16kbit/s. IEEE Trans. on Commun., Vol. Com-33, July 1985, pp685-696.
【12】 M.J. Sabin, R. M. Gray. Product code vector quantizers for waveform and voice coding. IEEE Trans. on Acoust., Speech, Signal Processing, Vol.32, June 1984, pp474-488.
【13】 R C. Cosma, K. L. Ochler, E. A. Riskin, R. M. Gray. Using Vector Quantization for Image Processing. Proceeding for IEEE Vol.81, No.9, 1993, pp1326-1341.
【14】 R D. Alessandro, R. Lancini. Video coding scheme using DCT-pyramid Vector Quantization. IEEE Trans. on Image Processing, Vol.4, Mar. 1995, pp309-319.
【15】 Eduardo A. B.da Silva, D. G. Sampson, A successive approximation vector quantizer for wavelet transform image coding. IEEE Trans. on Image Processing, Vol.5, No.2, Feb. 1996, pp299-310.
【16】 Grant A. Davison, Peter R. Cappello, Allen Gersho. Systolic Architecture for Vector Quantization. IEEE Trans. on Acoustics, Speech, and Signal Processing, Oct. 1988, Vol.36, No. 10.
【17】 Kazutoshi Kobayashi. A Study of the Functional Memory Type Parallel Processor.
【18】 Aysegul Cuhadar, Demetrios Sampson, Andy Downton. A scalable parallel approach to vector quantization.
【19】 A. Gersho, R. M. Gray. Vector Quantization and Signal Compression. Boston: Kluwer Academic Publishers, 1992.
【20】 孙圣和，陆哲明．矢量量化技术与应用．北京：科学出版社，2002．
【21】 J.R. Deller, J. G. Proakis, J. H. L. Discrete-Time Processing of Speech Signals. Macmillan Publishing Company, 1993.
【22】 M.R. Soleymani, and S.D. Morgera. An efficient nearest neighbor search method. IEEE Trans. Commun., 1987, 35(4):677-679.
【23】 S.W. Ra and J.K. Kim. A fast mean distant ordered partial codebook
search algorithm for vector quantization. IEEE Tans. Circuit and Systems Ⅱ, 1993,40(9):576-579.
【24】 Xilinx公司. Xilinx Application Note, XAPP119, July 20, 1998.