基于小波变换的静止图像压缩编码算法研究
|
摘要
随着多媒体技术和Internet应用的不断扩展，图像的传输和存储对图像压缩技术提出了更高的要求。新一代静态图像压缩标准JPEG2000的制定推动了图像压缩算法的研究和应用，基于小波变换的图像压缩技术已经成为当前研究的热点。
本课题为天津市自然科学基金资助项目“可用于数码相机的高速图像压缩技术研究”。内存和计算复杂度问题是图像压缩系统的重要因素。本文的算法研究和系统设计不仅可应用于数码相机，也适用于其它对算法复杂度和内存需求敏感的应用场合，具有较大的理论意义和应用价值。
本文在研究了JPEG2000的算法原理及其参考软件JASPER的基础上，设计了上位机主控模块、编码模块和解码模块，同时将本文算法和JPEG2000编、解码器集成在统一的软件框架内，以面向对象的方式设计了图像压缩系统的总体结构。
为实现快速静止图像压缩，本文采用DSP作为压缩系统的硬件平台，发挥其在数字信号处理上的优势。针对DSP内存有限的特点，在基于行的小波变换的基础上，提出了基于行的自适应二进制算术编码器的改进方案，以移位替代乘法进行概率估算，降低了算法的复杂度，提高了运行速度；针对基于行的小波变换的特点进行上下文构建，滚动使用缓冲区，节省了内存。在此基础上，研究了在低内存、低复杂度条件下的位平面编码和率失真优化，将位平面分为有效性通道、幅度细化通道和清除通道，对三个通道分别编码。应用查表的方式计算每个通道位流的失真值，按质量级的要求产生截断码流，在减少算法对内存需求的同时，可以获得较高的压缩效率和图像质量可分级的压缩码流。
With the development of Internet and multimedia technology, it is imperative for image compression technology to have better performance to meet the requirement of the image storage and transmission. The JPEG2000 standardization process promotes the research on image compression algorithm and wavelet image compression has already been an active research field.
The work of this thesis belongs to the project, “the research on high-speed image compression used in digital camera”, supported by Tianjin Natural Science Foundation. Memory efficiency and complexity are of major importance on algorithm development. Therefore, the research and system design in this work have theoretical significance and practicability, which can be used in digital camera and other applications with limited memory.
Based on JPEG2000 and its software implementation - JASPER, an overall software frame including main control module, encoder module and decoder module has been designed in object-oriented way, which integrates JASPER with the implementation of this algorithm as a whole.
In order to perform high-speed still image compression, DSP is selected as hardware platform for its superiority in digital signal processing. An improved adaptive binary arithmetic coder adapted to line-based wavelet image compression is proposed, which runs fast, but is very sample because of the multiply-free operation and the line-based context formation. Following the algorithm above, the bit-planes coding and rate distortion optimizations under low memory and complexity are researched. Bit-planes can be classified into three coding passes, i.e. significant pass, magnitude refinement pass and cleanup pass, and these three coding passes are coded respectively. By calculating the rate distortion values of bit streams in each coding pass according to table lookup, generated code streams are quality scalable. The algorithm in this thesis reduces the memory requirement of wavelet image coding greatly while achieving acceptable compression efficiency and image quality.
本课题为天津市自然科学基金资助项目“可用于数码相机的高速图像压缩技术研究”。内存和计算复杂度问题是图像压缩系统的重要因素。本文的算法研究和系统设计不仅可应用于数码相机，也适用于其它对算法复杂度和内存需求敏感的应用场合，具有较大的理论意义和应用价值。
本文在研究了JPEG2000的算法原理及其参考软件JASPER的基础上，设计了上位机主控模块、编码模块和解码模块，同时将本文算法和JPEG2000编、解码器集成在统一的软件框架内，以面向对象的方式设计了图像压缩系统的总体结构。
为实现快速静止图像压缩，本文采用DSP作为压缩系统的硬件平台，发挥其在数字信号处理上的优势。针对DSP内存有限的特点，在基于行的小波变换的基础上，提出了基于行的自适应二进制算术编码器的改进方案，以移位替代乘法进行概率估算，降低了算法的复杂度，提高了运行速度；针对基于行的小波变换的特点进行上下文构建，滚动使用缓冲区，节省了内存。在此基础上，研究了在低内存、低复杂度条件下的位平面编码和率失真优化，将位平面分为有效性通道、幅度细化通道和清除通道，对三个通道分别编码。应用查表的方式计算每个通道位流的失真值，按质量级的要求产生截断码流，在减少算法对内存需求的同时，可以获得较高的压缩效率和图像质量可分级的压缩码流。
With the development of Internet and multimedia technology, it is imperative for image compression technology to have better performance to meet the requirement of the image storage and transmission. The JPEG2000 standardization process promotes the research on image compression algorithm and wavelet image compression has already been an active research field.
The work of this thesis belongs to the project, “the research on high-speed image compression used in digital camera”, supported by Tianjin Natural Science Foundation. Memory efficiency and complexity are of major importance on algorithm development. Therefore, the research and system design in this work have theoretical significance and practicability, which can be used in digital camera and other applications with limited memory.
Based on JPEG2000 and its software implementation - JASPER, an overall software frame including main control module, encoder module and decoder module has been designed in object-oriented way, which integrates JASPER with the implementation of this algorithm as a whole.
In order to perform high-speed still image compression, DSP is selected as hardware platform for its superiority in digital signal processing. An improved adaptive binary arithmetic coder adapted to line-based wavelet image compression is proposed, which runs fast, but is very sample because of the multiply-free operation and the line-based context formation. Following the algorithm above, the bit-planes coding and rate distortion optimizations under low memory and complexity are researched. Bit-planes can be classified into three coding passes, i.e. significant pass, magnitude refinement pass and cleanup pass, and these three coding passes are coded respectively. By calculating the rate distortion values of bit streams in each coding pass according to table lookup, generated code streams are quality scalable. The algorithm in this thesis reduces the memory requirement of wavelet image coding greatly while achieving acceptable compression efficiency and image quality.
引文
[1] 余松煜，张文军，孙军，现代图像信息压缩技术，北京：科学出版社，1998
[2] Kenneth.R.Castleman著，数字图像处理（朱志刚等译），北京：电子工业出版社，1998
[3] 王汇源，数字图像通信原理与技术，北京：国防工业出版社，2000
[4] 夏良正，数字图像处理，南京：东南大学出版社，1999
[5] 毕厚杰，多媒体信息的传输与处理，北京：人民邮电出版社，1999
[6] M.Antonini，M.Barlaud，P.Mathieu，Image coding using wavelet transform，IEEE Trans. Image Processing，1992，1(2)：205～220
[7] Barlaud.M，Sole P，Gaidon T，Pyramidal lattice vector quantization for multiscale image coding， IEEE Trans. Image Processing, 1994, 3(4): 367～381
[8] Senoo.T, Girod.B, Vector quantization for entropy coding of image subbands, IEEE Trans. Image Processing, 1992, 1(4): 526～533
[9] Da.Silva，E.Sampson，D.G.Ghanbari，A successive approximation vector quantizer for wavelet transform image coding, IEEE Trans. Image Processing, 1996, 5(2): 299～310
[10]J.Shapiro, Embedded image coding using zerotrees of wavelet coefficients, IEEE Trans, Signal Processing, 1993，41(3)：445～462
[11]A. Said and W. Pearlman, A new, fast, and efficient image codec based on set partitioning in hierarchical trees, IEEE Trans. Circuits syst. Video Technol， 1996，6(3)：243～250
[12]Zixiang Xiong, Ramchandran.K, Orchard.M.T, Space-frequency quantization for wavelet image coding, IEEE Trans. Image Processing, 1997, 6(5): 677～693
[13]夏勇，田捷，戴汝为，一种改进的零树小波图像压缩算法，软件学报，1999，10(6)，626～630
[14]柳斌，田金文，柳捷，一种基于零树量化的小波变换图像压缩方法，华中理工大学学报，2000，28（3），68～70
[15]闫敬文，沈贵明，张世卓，基于小波变换和对块零树编码压缩方法，厦门大学学报（自然科学版），2001，40（5）：1167～1169
[16]W.Pennebaker, J.Mitchell, JPEG Still Image Data Compression Standard, Van Nostrand Reinhold, 1994
[17]ITU-T.81, Information Technology Digital Compression and Coding of Continuous-Tone Still Images Requirements and Guidelines, Recommendation T.81.ITU, 1992
[18]张虹，张小飞，图像压缩算法的研究，小型微型计算机系统，2000,21(6)：638～640
[19]JPEG2000 Part I Final Committee Version1.0，http:// www.jpeg.org/ FCD 15444-1.htm
[20]张晓娣，刘贵忠，曾召华，胡波，新一代静止图像压缩标准JPEG2000,电信科学，2001,17(5)，20～23
[21]李斌，JPEG2000标准的分析与评价，数字电视与数字视频，2001,(10)；22～25
[22]Charilaos.C, Athanassios.S, Touradj.E, The JPEG2000 still image coding system: an overview, IEEE Trans. Consumer Electronics, 2000,46(4): 1103～1127
[23]Christos Chrysafis, Wavelet image compression rate distortion optimizations and complexity reductions, A dissertation of the requirements for the Degree Doctor of Philosophy, University of Southern California, March 2000
[24]杨勇涛，詹湘淋，ADV－JP2000及其在数码相机中的应用，国外电子元器件，2003.4，14～16
[25]杨福生，小波变换的工程分析与应用，北京：科学出版社，1999
[26]彭玉华，小波变换与工程应用，北京：科学出版社，1999
[27]程正兴，小波分析算法与应用，西安：西安交通大学出版社，1998
[28]黄应清，季向琦，张智诠，图像小波系数的分布规律及其对图像质量的影响，红外与激光工程，2000，29(3)：15～18
[29]Christos Chrysafis, Antonio Ortega, An Algorithm for Low Memory Wavelet Image Compression，IEEE，1999，3：354～358;
[30]Christos Chrysafis, Antonio Ortega, Line Based, Reduced Memory, Wavelet Image Compression，IEEE Trans，Image Processing，Data Compression Comference，DCC'98，1998：398～407
[31]Chrysafis.C, Ortega.A, Line-based, reduced memory, wavelet image compression, IEEE Trans. Image Processing, 2000, 9(3): 378～389
[32]Ingrid Daubechies, Wim Sweldens, Factoring Wavelet Transforms Into Lifting Steps, J Fourier Anal Appl，1998，4(3)：247～269
[33]曾剑芬、马争鸣， Lifting Scheme及其在小波图像编码中的应用，中国图象图形学报，2001，6(11)：1111～1117
[34]曾剑芬、马争鸣，提升格式与JPEG2000，中山大学学报：自然科学版，2002，41(1)：32～34
[35]Wim Sweldens, The Lifting Scheme：a construction of second generation wavelets，SIAM J Math Anal，1997，29(2)：511～546
[36]周炯磐，丁晓明，信源编码原理，北京：人民邮电出版社，1996
[37]吴乐南，数据压缩的原理与应用，北京：电子工业出版社，1995
[38]高文，多媒体数据压缩技术，北京：电子工业出版社，1994
[39]Witten.I.H, R.M.Neal, J.G.Cleary, Arithmetic coding for data compression, Communications of the ACM, 1987,30(6): 520～540
[40]Moffat.A, R.M.Neal, I.H.Witten, Arithmetic coding revisited, ACM Transactions on Information Systems, 1998, 16(3): 256～294
[41]Langdon.G.G, J.Rissanen, A simple general binary source code, IEEE Trans. Information Theory, 1982, 27(1): 800～803
[42]J.Rissanen, Langdon.G.G, Universal modeling and coding, IEEE Trans. Information Theory, 1981, 27(1): 12～23
[43]陆堪，陈华东，高速数字信号处理器（DSP）的研究应用，浙江工程学院学报，2000,17(1)：47～50
[44]李刚，数字信号微处理器的原理及其开发应用，天津：天津大学出版社，2000
[45]G.Sharma, J.Trussull, Digital color imaging, IEEE Trans. Image Processing, 1997,6(7): 901～932
[46]C.Chrysafis, A.Ortega, Efficient context-based entropy coding for lossy wavelet image compression, IEEE Data Compression Conference, Snowbird, Utah, 1997: 241～250
[47]W.B.Pennebaker, J.L.Mitchell, G.G.Langdon, An overview of the basic principles of the Q-Coder adaptive binary arithmetic coder, IBM J. Res. Develop. 1988, 32(6): 717～726
[48]W.B.Pennebaker, J.L.Mitchell, Probability estimation for the Q-Coder, IBM J. Res. Develop, 1988, 32(8): 737～752
[49]J.L.Mitchell, W.B.Pennebaker, Optimal hardware and software arithmetic coding procedures for the Q-Coder, IBM J. Res. Develop, 1988, 32(7): 727～736
[50]J.L.Mitchell, W.B.Pennebaker, Software implementations of the Q-Coder, IBM J. Res. Develop, 1988, 32(9): 753～774
[51]罗钧，张国彬，JPEG2000中的二进制算术编码及其DSP实现，重庆大学学报，2003，26(4)：34～37
[52]张国彬，罗钧，罗泽文，基于位平面自适应算术编码的小波图像压缩技术，光电工程，2002，30(2)：68～71
[53]Xiaolin Wu, Lossless compression of continuous-tone images via context selection, quantization, and modeling, IEEE Trans. Image Processing, 1997, 6(5): 656～664
[54]周荫清，信息理论基础，北京：北京航空航天大学出版社，2002
[55]Taubman.D, High performance scalable image compression with EBCOT, IEEE Trans. Image Processing, 2000, 9(7): 1158～1170
[56]Ordentlich.E, Taubman.D, Weinberger.M, Memory-efficient scalable line-based image coding, IEEE Data Compression Conference, 1999: 218～227
[57]Michael.D.Adams, JasPer Software A implementation of the codec of ISO/IEC15444-1, http://www.ece.uvic.ca/mdadams/jasper/
[58]T.Denk, K.Parhi, Architectures for lattice structure based orthonormal discrete wavelet transforms, IEEE Trans. Circuits Syst, 1997, 44(2): 129～132
[2] Kenneth.R.Castleman著，数字图像处理（朱志刚等译），北京：电子工业出版社，1998
[3] 王汇源，数字图像通信原理与技术，北京：国防工业出版社，2000
[4] 夏良正，数字图像处理，南京：东南大学出版社，1999
[5] 毕厚杰，多媒体信息的传输与处理，北京：人民邮电出版社，1999
[6] M.Antonini，M.Barlaud，P.Mathieu，Image coding using wavelet transform，IEEE Trans. Image Processing，1992，1(2)：205～220
[7] Barlaud.M，Sole P，Gaidon T，Pyramidal lattice vector quantization for multiscale image coding， IEEE Trans. Image Processing, 1994, 3(4): 367～381
[8] Senoo.T, Girod.B, Vector quantization for entropy coding of image subbands, IEEE Trans. Image Processing, 1992, 1(4): 526～533
[9] Da.Silva，E.Sampson，D.G.Ghanbari，A successive approximation vector quantizer for wavelet transform image coding, IEEE Trans. Image Processing, 1996, 5(2): 299～310
[10]J.Shapiro, Embedded image coding using zerotrees of wavelet coefficients, IEEE Trans, Signal Processing, 1993，41(3)：445～462
[11]A. Said and W. Pearlman, A new, fast, and efficient image codec based on set partitioning in hierarchical trees, IEEE Trans. Circuits syst. Video Technol， 1996，6(3)：243～250
[12]Zixiang Xiong, Ramchandran.K, Orchard.M.T, Space-frequency quantization for wavelet image coding, IEEE Trans. Image Processing, 1997, 6(5): 677～693
[13]夏勇，田捷，戴汝为，一种改进的零树小波图像压缩算法，软件学报，1999，10(6)，626～630
[14]柳斌，田金文，柳捷，一种基于零树量化的小波变换图像压缩方法，华中理工大学学报，2000，28（3），68～70
[15]闫敬文，沈贵明，张世卓，基于小波变换和对块零树编码压缩方法，厦门大学学报（自然科学版），2001，40（5）：1167～1169
[16]W.Pennebaker, J.Mitchell, JPEG Still Image Data Compression Standard, Van Nostrand Reinhold, 1994
[17]ITU-T.81, Information Technology Digital Compression and Coding of Continuous-Tone Still Images Requirements and Guidelines, Recommendation T.81.ITU, 1992
[18]张虹，张小飞，图像压缩算法的研究，小型微型计算机系统，2000,21(6)：638～640
[19]JPEG2000 Part I Final Committee Version1.0，http:// www.jpeg.org/ FCD 15444-1.htm
[20]张晓娣，刘贵忠，曾召华，胡波，新一代静止图像压缩标准JPEG2000,电信科学，2001,17(5)，20～23
[21]李斌，JPEG2000标准的分析与评价，数字电视与数字视频，2001,(10)；22～25
[22]Charilaos.C, Athanassios.S, Touradj.E, The JPEG2000 still image coding system: an overview, IEEE Trans. Consumer Electronics, 2000,46(4): 1103～1127
[23]Christos Chrysafis, Wavelet image compression rate distortion optimizations and complexity reductions, A dissertation of the requirements for the Degree Doctor of Philosophy, University of Southern California, March 2000
[24]杨勇涛，詹湘淋，ADV－JP2000及其在数码相机中的应用，国外电子元器件，2003.4，14～16
[25]杨福生，小波变换的工程分析与应用，北京：科学出版社，1999
[26]彭玉华，小波变换与工程应用，北京：科学出版社，1999
[27]程正兴，小波分析算法与应用，西安：西安交通大学出版社，1998
[28]黄应清，季向琦，张智诠，图像小波系数的分布规律及其对图像质量的影响，红外与激光工程，2000，29(3)：15～18
[29]Christos Chrysafis, Antonio Ortega, An Algorithm for Low Memory Wavelet Image Compression，IEEE，1999，3：354～358;
[30]Christos Chrysafis, Antonio Ortega, Line Based, Reduced Memory, Wavelet Image Compression，IEEE Trans，Image Processing，Data Compression Comference，DCC'98，1998：398～407
[31]Chrysafis.C, Ortega.A, Line-based, reduced memory, wavelet image compression, IEEE Trans. Image Processing, 2000, 9(3): 378～389
[32]Ingrid Daubechies, Wim Sweldens, Factoring Wavelet Transforms Into Lifting Steps, J Fourier Anal Appl，1998，4(3)：247～269
[33]曾剑芬、马争鸣， Lifting Scheme及其在小波图像编码中的应用，中国图象图形学报，2001，6(11)：1111～1117
[34]曾剑芬、马争鸣，提升格式与JPEG2000，中山大学学报：自然科学版，2002，41(1)：32～34
[35]Wim Sweldens, The Lifting Scheme：a construction of second generation wavelets，SIAM J Math Anal，1997，29(2)：511～546
[36]周炯磐，丁晓明，信源编码原理，北京：人民邮电出版社，1996
[37]吴乐南，数据压缩的原理与应用，北京：电子工业出版社，1995
[38]高文，多媒体数据压缩技术，北京：电子工业出版社，1994
[39]Witten.I.H, R.M.Neal, J.G.Cleary, Arithmetic coding for data compression, Communications of the ACM, 1987,30(6): 520～540
[40]Moffat.A, R.M.Neal, I.H.Witten, Arithmetic coding revisited, ACM Transactions on Information Systems, 1998, 16(3): 256～294
[41]Langdon.G.G, J.Rissanen, A simple general binary source code, IEEE Trans. Information Theory, 1982, 27(1): 800～803
[42]J.Rissanen, Langdon.G.G, Universal modeling and coding, IEEE Trans. Information Theory, 1981, 27(1): 12～23
[43]陆堪，陈华东，高速数字信号处理器（DSP）的研究应用，浙江工程学院学报，2000,17(1)：47～50
[44]李刚，数字信号微处理器的原理及其开发应用，天津：天津大学出版社，2000
[45]G.Sharma, J.Trussull, Digital color imaging, IEEE Trans. Image Processing, 1997,6(7): 901～932
[46]C.Chrysafis, A.Ortega, Efficient context-based entropy coding for lossy wavelet image compression, IEEE Data Compression Conference, Snowbird, Utah, 1997: 241～250
[47]W.B.Pennebaker, J.L.Mitchell, G.G.Langdon, An overview of the basic principles of the Q-Coder adaptive binary arithmetic coder, IBM J. Res. Develop. 1988, 32(6): 717～726
[48]W.B.Pennebaker, J.L.Mitchell, Probability estimation for the Q-Coder, IBM J. Res. Develop, 1988, 32(8): 737～752
[49]J.L.Mitchell, W.B.Pennebaker, Optimal hardware and software arithmetic coding procedures for the Q-Coder, IBM J. Res. Develop, 1988, 32(7): 727～736
[50]J.L.Mitchell, W.B.Pennebaker, Software implementations of the Q-Coder, IBM J. Res. Develop, 1988, 32(9): 753～774
[51]罗钧，张国彬，JPEG2000中的二进制算术编码及其DSP实现，重庆大学学报，2003，26(4)：34～37
[52]张国彬，罗钧，罗泽文，基于位平面自适应算术编码的小波图像压缩技术，光电工程，2002，30(2)：68～71
[53]Xiaolin Wu, Lossless compression of continuous-tone images via context selection, quantization, and modeling, IEEE Trans. Image Processing, 1997, 6(5): 656～664
[54]周荫清，信息理论基础，北京：北京航空航天大学出版社，2002
[55]Taubman.D, High performance scalable image compression with EBCOT, IEEE Trans. Image Processing, 2000, 9(7): 1158～1170
[56]Ordentlich.E, Taubman.D, Weinberger.M, Memory-efficient scalable line-based image coding, IEEE Data Compression Conference, 1999: 218～227
[57]Michael.D.Adams, JasPer Software A implementation of the codec of ISO/IEC15444-1, http://www.ece.uvic.ca/mdadams/jasper/
[58]T.Denk, K.Parhi, Architectures for lattice structure based orthonormal discrete wavelet transforms, IEEE Trans. Circuits Syst, 1997, 44(2): 129～132