基于内容的嵌入式小波图像编码算法研究
|
摘要
多媒体技术的发展使图像信息逐渐成为交互的主要内容之一,解决图像存储与传输问题的压缩编码技术一直以来是国内外研究的热点,从JPEG、MPEG-1到JPEG2000、MPEG-4反映了图像压缩编码技术的飞速发展。目前基于小波分析的图像嵌入式编码技术已经占据了主导地位,如EZW、SPIHT、EBCOT和LZC等。基于内容的嵌入式小波图像编码算法的主要研究问题集中在以下方面:如何准确地描述图像内容、有效地提取图像特征;如何高效组织系数模型,提高编码效率;如何采取合理的量化策略,既可利用上下文系数相关性又可使图像恢复质量符合HVS特性等。
本文首先介绍了图像压缩理论、嵌入式编码的几种方法及静态、动态图像编码的国际标准;研究了基于形状、颜色、纹理和空间关系的图像特征描述方法,针对图像内容的核心特征,采用基于最优阈值的边界矩算法对形状特征提取,实验证明该方法较好地保持了形状的一致性,完整地描述图像形状分布信息。
通过学习图像的小波变换理论,给出了多分辨率分析概念及小波分解和重构的快速算法--Mallat算法,结合适用于嵌入式图像压缩的提升小波变换,进一步分析了小波图像的系数分布特点、灰度直方图特点以及小波变换后图像自身特点,得到适合编码的小波基。
重点研究了JPEG2000核心编码算法--EBCOT算法的原理、编码过程;并针对JPEG2000的算法复杂度较大、编解码时间长等不足,通过预存行状态去除带间相关性,提出基于单窗口的上下文逻辑编码,并优先计算比特平面状态值,实现一次扫描完成比特平面及平面内三个通道的并行编码。
最后,通过分析EZW、SPIHT、EBCOT算法及3D-EZW、3D-SPIHT、3D-ESCOT嵌入式编码模型,本文综合利用小波系数不同子带间的自相似性、偏序性和同子带内相邻系数的相关性,提出了一种新的三维小波嵌入编码上下文模型3D-EVCM,实验结果表明,利用这种模型获得的PSNR高于3D-ESCOT模型,同时具有了3D-ESCOT模型的优良特性。
With the development of multimedia technology, image information gradually becomes one of the main measures of communication. How to resolve the problems of images transmission and storage is the focus in image compression. From JPEG, MPEG-1 to JPEG-2000, MPEG-4, technologies of image compression have been developing rapidly. At present, embedded image coding algorithms based on wavelet analysis are dominant, such as EZW, SPIHT, EBCOT and LZC. Research on content-based embedded image wavelet coding algorithms concentrates on the following aspects: how to describe image content correctly and extract shape feature efficiently; how to organize coefficients to improve the efficiency of coding; how to quantitate coefficients to utilize context relativity and make quality of images accorded with HVS etc.
In this thesis, firstly, the theory of image compressing is introduced. The methods of embedded coding and international standard of image, video coding are also be listed. The thesis researched the measures of image content description based on the feature of color, texture, shape and space. Considering the key feature of image content, an invariant moment based on threshold optimization method is used to extract the shape feature. The experiment results demonstrate that the method hold the shape consistency of image well, it also describe the shape information of image completely.
Secondly, the thesis introduces the theory of image wavelet transform, the concept of multi-resolution analysis and the Mallat arithmetic by which the signal is fast composed and decomposed. Combined with the wavelet lifting scheme which fit embedded image compression, the characteristics of the wavelet transformed image coefficient distribution, gray level histogram and the image itself are further analyzed, and the reasonable wavelet bases for image compression are obtained.
In addition, the principle and coding course of EBCOT algorithmic have been studied, which is the core coding algorithmic of JPEG2000 standard. In order to resolve the algorithmic complexity and reduce the time of coding and decoding, a measure which saving row-status in advance to separate the relationship of strip and encoding logic contexts based on single window and computing bit-plane status in priority, a parallel EBCOT encoding algorithm is proposed to encode bit-plane and its three passes in one time scanning.
Finally, the typical embedded coding algorithms and schemes are analyzed, such as EZW, SPIHT, EBCOT, 3D-EZW, 3D-SPIHT and 3D-ESCOT. A new context model of wavelet coefficients is proposed, which make use of partial order, self-similarity between subbands of wavelet coefficients and the correlation of neighboring wavelet coefficients. Experimental results show that the model achieves higher PSNR than 3D-ESCOT while keeping all the advantages of 3D-ESCOT.
本文首先介绍了图像压缩理论、嵌入式编码的几种方法及静态、动态图像编码的国际标准;研究了基于形状、颜色、纹理和空间关系的图像特征描述方法,针对图像内容的核心特征,采用基于最优阈值的边界矩算法对形状特征提取,实验证明该方法较好地保持了形状的一致性,完整地描述图像形状分布信息。
通过学习图像的小波变换理论,给出了多分辨率分析概念及小波分解和重构的快速算法--Mallat算法,结合适用于嵌入式图像压缩的提升小波变换,进一步分析了小波图像的系数分布特点、灰度直方图特点以及小波变换后图像自身特点,得到适合编码的小波基。
重点研究了JPEG2000核心编码算法--EBCOT算法的原理、编码过程;并针对JPEG2000的算法复杂度较大、编解码时间长等不足,通过预存行状态去除带间相关性,提出基于单窗口的上下文逻辑编码,并优先计算比特平面状态值,实现一次扫描完成比特平面及平面内三个通道的并行编码。
最后,通过分析EZW、SPIHT、EBCOT算法及3D-EZW、3D-SPIHT、3D-ESCOT嵌入式编码模型,本文综合利用小波系数不同子带间的自相似性、偏序性和同子带内相邻系数的相关性,提出了一种新的三维小波嵌入编码上下文模型3D-EVCM,实验结果表明,利用这种模型获得的PSNR高于3D-ESCOT模型,同时具有了3D-ESCOT模型的优良特性。
With the development of multimedia technology, image information gradually becomes one of the main measures of communication. How to resolve the problems of images transmission and storage is the focus in image compression. From JPEG, MPEG-1 to JPEG-2000, MPEG-4, technologies of image compression have been developing rapidly. At present, embedded image coding algorithms based on wavelet analysis are dominant, such as EZW, SPIHT, EBCOT and LZC. Research on content-based embedded image wavelet coding algorithms concentrates on the following aspects: how to describe image content correctly and extract shape feature efficiently; how to organize coefficients to improve the efficiency of coding; how to quantitate coefficients to utilize context relativity and make quality of images accorded with HVS etc.
In this thesis, firstly, the theory of image compressing is introduced. The methods of embedded coding and international standard of image, video coding are also be listed. The thesis researched the measures of image content description based on the feature of color, texture, shape and space. Considering the key feature of image content, an invariant moment based on threshold optimization method is used to extract the shape feature. The experiment results demonstrate that the method hold the shape consistency of image well, it also describe the shape information of image completely.
Secondly, the thesis introduces the theory of image wavelet transform, the concept of multi-resolution analysis and the Mallat arithmetic by which the signal is fast composed and decomposed. Combined with the wavelet lifting scheme which fit embedded image compression, the characteristics of the wavelet transformed image coefficient distribution, gray level histogram and the image itself are further analyzed, and the reasonable wavelet bases for image compression are obtained.
In addition, the principle and coding course of EBCOT algorithmic have been studied, which is the core coding algorithmic of JPEG2000 standard. In order to resolve the algorithmic complexity and reduce the time of coding and decoding, a measure which saving row-status in advance to separate the relationship of strip and encoding logic contexts based on single window and computing bit-plane status in priority, a parallel EBCOT encoding algorithm is proposed to encode bit-plane and its three passes in one time scanning.
Finally, the typical embedded coding algorithms and schemes are analyzed, such as EZW, SPIHT, EBCOT, 3D-EZW, 3D-SPIHT and 3D-ESCOT. A new context model of wavelet coefficients is proposed, which make use of partial order, self-similarity between subbands of wavelet coefficients and the correlation of neighboring wavelet coefficients. Experimental results show that the model achieves higher PSNR than 3D-ESCOT while keeping all the advantages of 3D-ESCOT.
引文
[1] ISO/IEC FCD15444-1. JPEG 2000 Part I Final Committee Draft Version 1.0[S].
[2] JTCI/SC29/WG11/N2802, ISO/IEC. Information technology-Generic coding of audiovisual objects– Part2:Visual, ISO/IEC 14496-2, MPEG Vancouver meeting. 99.7
[3] David Taubman,High Performance Scalable Image Compression with EBCOT[J].IEEE Trans. On Image Processing,2000,6(9):1158-1170
[4] Wallace, G. K. The JPEG Still Picture Compression Standard, Comm. ACM[J]. 1991,4(34): 30-44.
[5] H. Schwarz, D.Marpe, and T. Wiegand. Scalable Extension of H.264/AVC, ISO/IEC/JCT1/SC29/WG11/M10596/S03
[6] Michael Horowitz, Anthony Joch, Faouzi Kossentini and Antti Hallapuro. H.264/AVC Baseline Profile Decoder Complexity Analysis[J]. IEEE Transaction on Circuits and Systems for Video Technology, 2003,3(7):704-716
[7]徐飞,施晓红.MATLAB应用图像处理[M].西安:西安电子科技大学出版社,2002
[8] D.S. Taubman, M.W.Marcellin, JPEG2000 Image Compression Fundamentals, Standards and Practice, Klumer Academic inc. 2002:231~235
[9] R.C. Gonzalez, R.E. Woods, Digital Image Processing, Second version, Prentice Hall inc.北京:电子工业出版社,2002
[10] Mohammed Ghanbari. Video coding-an introduction to standard codecs. Institution of Electrical Engineers, 1999.12
[11]张旭东,卢国栋,冯健.图象编码基础和压缩技术-原理、算法和标准[M].北京:清华大学出版社,2004:14～68
[12]姚庆栋,毕厚杰,王兆华,徐孟侠.图象编码基础[M].北京:清华大学出版社,2006:146～180
[13] Ahmed, N.T. Natarajan, and K.R.Rao.Discretecosine transform[J]. IEEE Trans. Computer, 1974(23):90-93
[14] M.Boliek, C. Christopoulos and E. Majani(editor), JPEGE2000 Part I Final Committee Draft Version 1.0, ISO/IEC JTC/SC29/WG1 N1646R, March 2000.
[15]沈兰荪,卓力.小波编码与网络视频传输[M].北京:科学出版社,2005:97-116
[16] A.S.Lewis and G.K.Nowles. Image compression using the 2-D wavelet transform[J], IEEE Transactions on Signal Processing, 1992,1(2):244-250
[17] I.Daubechies, W.Sweldens. Factoring Wavelet and Subband Transforms into Lifting Steps[C]. Comm Pure Appl Math.1996(45):71-78
[18] W.A.Pearlman, A.Islam, N.Nagaraj and A.Said. Efficient, low-complexity image coding with a set-partitioning embedded block coder,http://www.cipr.rpi.edu/~pearlman/papers/cevt02_pins.pdf,2004
[19]边文奎,徐梦苏.二值图像压缩标准——JBIG2[J].计算机工程与应用.2002,38(13),233-237
[20] ISO/IEC JTC1/SC29/WG1 WG1N1696, Motion-JPEG2000 Requirements and Profiles ver2.0[S].
[21] Said A. Pearlman WA. A new, fast, and efficient image codec based on set partitioning in hierarchical trees[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(3):243～250
[22] K.Andra, C.Chakrabarti, and T.Acharya, A High-performance JPEG2000 Architecture[J]. IEEE Trans. On Circuits and Systems for Video Technology, 2003(13): 209-218, 19-21
[23]王崇骏,杨育彬,陈世福.基于高层语义的检索算法.软件学报.2004(5): 1461-1469
[24] Wandell B A. The synthesis and analysis of color image[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence,1987,9(1): 2-13
[25] M Stricker, M Orengo. Similarity of color images[C]. SPIE Storage and Retrieval for Image and Video Databases 1995(3):381-392
[26] Kimia B. Shape representation for image retrieval[C]. In: Image Databases_Search and Retrieval of Digital Imagery. Castelli V, Bergman L D,eds. John Wiley& Sons, Inc.Ch.2002(13):345-372
[27] Bimbo. A Visual Information Retrieval[J]. Morgan Kaufmann Publishers 1999.31(12): 689-704
[28] A Vailaya, A K Jain, H J Zhang. On Image Classification; City Image vs Land- scapes [J]. Pattern Recognition, 1998,32(12):1921-1936
[29] X.Yang and K.Ramchandram.“Scalable wavelet video coding using alisasing-reduced hierachical motion compensation”[J].IEEE Trans on Image Processing,2000,9(5): 778-791
[30] M K Hu. Visual pattern recognition by moment invariants[C]. In: J K Aggarwal, R O duda and A rosenfeld. Computer Methods in Image analysis. Los Angeles, CA: IEEE computer Society, 1977(26):357-370
[31]沈会良,李志能.基于知和滤波变换的数字\字母字符识别研究[J].中国图象图形学报.Vol.5, No.3, 2000:249-252.
[32]程正兴.小波分析算法和应用[M] .西安:西安交通大学出版社.2001:108～121
[33]林福宗.《小波与小波变换》.清华大学计算机科学与技术系智能技术与系统国家重点实验室.2001:436-469
[34] W.Sweldens, The Lifting Scheme: Construction of Second-generation Wavelets[J], SIAM J.Math. 1998,29(2):411-446
[35] I.Daubechies, W.Sweldens. Factoring Wavelet Transforms into Lifting Steps. CommPure Appl Math. 1998,4(3):244-267
[36]李建平.小波分析与信号处理—理论、应用及软件实现[M].重庆:重庆出版社,1997,147～149
[37] David S.Taubman, Michael W.Marcellin,”JPEG2000:Standard for Interactive Imaging”[J]. Proc. IEEE . 2002.8(90): 1336～1357
[38] A. Cohen,I. Daubechies,J. C. Feauveau,Biorthogonal bases of compactly support wavelets[J]. Commune. Pure. Appl. Math. June 1992:485～560
[39]孙亚明,杨春玲.JPEG2000编码算法上下文关系的改进[J].计算机应用与软件2005.22(12): 215-221
[40] J.A. Garcia, Rosa Rodriguez-Sanchez, J. Fdez-Valdivia, J. Martinez-Baena. Rate control optimization in embedded wavelet coding[J]. Pattern Recognition Letters, 2003(24): 1469-1487
[41]刘凯、李云松、吴成柯.高性能的EBCOT编码及其VLSI结构[J].软件学报2006.17(7): 69-74
[42] G. Karlsson and M. Vetterli, Subband coding of video signals for packet switched networks[J]. Proc. Visual Commun. Image Process. 1987.8(45), 446-456
[43] S.-J. Choi and J. W. Woods, Motion-compensated 3-D subband coding of video[J]. IEEE Transactions on Image Processing. 1999.8(2):155-167
[44] Jizheng Xu,Zixiang Xiong, Shipeng Li and Ya-Qin Zhang. Three-Dimensional Embedded Subband Coding with Optimized Truncation (3-D ESCOT)[J]. Applied and Computational Harmonic Analysis. 2001.10(3): 290-315
[45] J M.Shapiro. Embedded image coding using zerotree of wavelet coefficients[J]. IEEE Trans. Signal Processing. 1993.41(12): 3445-3462
[2] JTCI/SC29/WG11/N2802, ISO/IEC. Information technology-Generic coding of audiovisual objects– Part2:Visual, ISO/IEC 14496-2, MPEG Vancouver meeting. 99.7
[3] David Taubman,High Performance Scalable Image Compression with EBCOT[J].IEEE Trans. On Image Processing,2000,6(9):1158-1170
[4] Wallace, G. K. The JPEG Still Picture Compression Standard, Comm. ACM[J]. 1991,4(34): 30-44.
[5] H. Schwarz, D.Marpe, and T. Wiegand. Scalable Extension of H.264/AVC, ISO/IEC/JCT1/SC29/WG11/M10596/S03
[6] Michael Horowitz, Anthony Joch, Faouzi Kossentini and Antti Hallapuro. H.264/AVC Baseline Profile Decoder Complexity Analysis[J]. IEEE Transaction on Circuits and Systems for Video Technology, 2003,3(7):704-716
[7]徐飞,施晓红.MATLAB应用图像处理[M].西安:西安电子科技大学出版社,2002
[8] D.S. Taubman, M.W.Marcellin, JPEG2000 Image Compression Fundamentals, Standards and Practice, Klumer Academic inc. 2002:231~235
[9] R.C. Gonzalez, R.E. Woods, Digital Image Processing, Second version, Prentice Hall inc.北京:电子工业出版社,2002
[10] Mohammed Ghanbari. Video coding-an introduction to standard codecs. Institution of Electrical Engineers, 1999.12
[11]张旭东,卢国栋,冯健.图象编码基础和压缩技术-原理、算法和标准[M].北京:清华大学出版社,2004:14～68
[12]姚庆栋,毕厚杰,王兆华,徐孟侠.图象编码基础[M].北京:清华大学出版社,2006:146～180
[13] Ahmed, N.T. Natarajan, and K.R.Rao.Discretecosine transform[J]. IEEE Trans. Computer, 1974(23):90-93
[14] M.Boliek, C. Christopoulos and E. Majani(editor), JPEGE2000 Part I Final Committee Draft Version 1.0, ISO/IEC JTC/SC29/WG1 N1646R, March 2000.
[15]沈兰荪,卓力.小波编码与网络视频传输[M].北京:科学出版社,2005:97-116
[16] A.S.Lewis and G.K.Nowles. Image compression using the 2-D wavelet transform[J], IEEE Transactions on Signal Processing, 1992,1(2):244-250
[17] I.Daubechies, W.Sweldens. Factoring Wavelet and Subband Transforms into Lifting Steps[C]. Comm Pure Appl Math.1996(45):71-78
[18] W.A.Pearlman, A.Islam, N.Nagaraj and A.Said. Efficient, low-complexity image coding with a set-partitioning embedded block coder,http://www.cipr.rpi.edu/~pearlman/papers/cevt02_pins.pdf,2004
[19]边文奎,徐梦苏.二值图像压缩标准——JBIG2[J].计算机工程与应用.2002,38(13),233-237
[20] ISO/IEC JTC1/SC29/WG1 WG1N1696, Motion-JPEG2000 Requirements and Profiles ver2.0[S].
[21] Said A. Pearlman WA. A new, fast, and efficient image codec based on set partitioning in hierarchical trees[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(3):243～250
[22] K.Andra, C.Chakrabarti, and T.Acharya, A High-performance JPEG2000 Architecture[J]. IEEE Trans. On Circuits and Systems for Video Technology, 2003(13): 209-218, 19-21
[23]王崇骏,杨育彬,陈世福.基于高层语义的检索算法.软件学报.2004(5): 1461-1469
[24] Wandell B A. The synthesis and analysis of color image[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence,1987,9(1): 2-13
[25] M Stricker, M Orengo. Similarity of color images[C]. SPIE Storage and Retrieval for Image and Video Databases 1995(3):381-392
[26] Kimia B. Shape representation for image retrieval[C]. In: Image Databases_Search and Retrieval of Digital Imagery. Castelli V, Bergman L D,eds. John Wiley& Sons, Inc.Ch.2002(13):345-372
[27] Bimbo. A Visual Information Retrieval[J]. Morgan Kaufmann Publishers 1999.31(12): 689-704
[28] A Vailaya, A K Jain, H J Zhang. On Image Classification; City Image vs Land- scapes [J]. Pattern Recognition, 1998,32(12):1921-1936
[29] X.Yang and K.Ramchandram.“Scalable wavelet video coding using alisasing-reduced hierachical motion compensation”[J].IEEE Trans on Image Processing,2000,9(5): 778-791
[30] M K Hu. Visual pattern recognition by moment invariants[C]. In: J K Aggarwal, R O duda and A rosenfeld. Computer Methods in Image analysis. Los Angeles, CA: IEEE computer Society, 1977(26):357-370
[31]沈会良,李志能.基于知和滤波变换的数字\字母字符识别研究[J].中国图象图形学报.Vol.5, No.3, 2000:249-252.
[32]程正兴.小波分析算法和应用[M] .西安:西安交通大学出版社.2001:108～121
[33]林福宗.《小波与小波变换》.清华大学计算机科学与技术系智能技术与系统国家重点实验室.2001:436-469
[34] W.Sweldens, The Lifting Scheme: Construction of Second-generation Wavelets[J], SIAM J.Math. 1998,29(2):411-446
[35] I.Daubechies, W.Sweldens. Factoring Wavelet Transforms into Lifting Steps. CommPure Appl Math. 1998,4(3):244-267
[36]李建平.小波分析与信号处理—理论、应用及软件实现[M].重庆:重庆出版社,1997,147～149
[37] David S.Taubman, Michael W.Marcellin,”JPEG2000:Standard for Interactive Imaging”[J]. Proc. IEEE . 2002.8(90): 1336～1357
[38] A. Cohen,I. Daubechies,J. C. Feauveau,Biorthogonal bases of compactly support wavelets[J]. Commune. Pure. Appl. Math. June 1992:485～560
[39]孙亚明,杨春玲.JPEG2000编码算法上下文关系的改进[J].计算机应用与软件2005.22(12): 215-221
[40] J.A. Garcia, Rosa Rodriguez-Sanchez, J. Fdez-Valdivia, J. Martinez-Baena. Rate control optimization in embedded wavelet coding[J]. Pattern Recognition Letters, 2003(24): 1469-1487
[41]刘凯、李云松、吴成柯.高性能的EBCOT编码及其VLSI结构[J].软件学报2006.17(7): 69-74
[42] G. Karlsson and M. Vetterli, Subband coding of video signals for packet switched networks[J]. Proc. Visual Commun. Image Process. 1987.8(45), 446-456
[43] S.-J. Choi and J. W. Woods, Motion-compensated 3-D subband coding of video[J]. IEEE Transactions on Image Processing. 1999.8(2):155-167
[44] Jizheng Xu,Zixiang Xiong, Shipeng Li and Ya-Qin Zhang. Three-Dimensional Embedded Subband Coding with Optimized Truncation (3-D ESCOT)[J]. Applied and Computational Harmonic Analysis. 2001.10(3): 290-315
[45] J M.Shapiro. Embedded image coding using zerotree of wavelet coefficients[J]. IEEE Trans. Signal Processing. 1993.41(12): 3445-3462