小波变换在图像编码压缩领域中的研究与应用
|
摘要
小波分析自20世纪80年代诞生以来发展迅速。特别是紧支撑的正交小波构建理论、多分辨率分析理论和快速小波变换算法提出后,在随后的这十多年中,有关小波的研究不断取得重大突破。由于小波分析可以对信号中感兴趣的部分进行多分辨分析,所以被誉为信号的显微镜。小波分析已经成为目前发展最快和最引人注目的学科之一,几乎涉及或者应用到信息领域的所有学科。
图像压缩在多媒体技术中具有重要地位,传统图像编码压缩方法和标准虽得到广泛应用,但仍存在诸如编码效率低、压缩率低等诸多问题。小波用于图像编码压缩具有天然的优势,具有压缩率高、很好地渐进传输[1]、可伸缩的质量控制等优点。其原理是根据图像统计特征和人眼的生理特性[2],把图像分解为高频部分和低频部分,低频部分表示图像概貌,而高频部分表示图像细节。而图像能量主要集中在低频分量上,通过适当的编码算法达到数据压缩的目的。
目前已经产生了多种有影响的小波系数编解码算法,如嵌入式零树算法(Embedded Zero-tree Wavelet),SPIHT算法(Set Partitioning In Hierarchical Trees)、EBCOT算法(Embedded Block Coding with Optimized Truncation)等,其中以EBCOT算法为核心之一的图像编码技术已经被采纳为新一代图像编码压缩标准JPEG2000,大有取代JPEG的趋势。而1996年Said和Pearlman提出了SPIHT算法,也是一种很有效的零树编码方法,其优点是零树编码结束后,即使不经过熵编码(例如算术编码)也能获得较高的压缩比,和EBCOT算法相比,压缩率几乎差不多,但压缩速度快,算法简单。
本文兼顾小波分析的原理及其图像编码压缩中的应用,内容环环相扣,渐次推进,提出一种基于十进量化的SPIHT改进算法。该算法较经典SPIHT的最大优点是:在不改变SPIHT算法比特面编码和支持渐进传输特性的前提下,编解码次数大幅度降低,时间消耗和PSNR和标准SPIHT算法相当。最后给出MATLAB实现程序证明该改进算法的合理性。
Since the birth of wavelet analysis in the 1980s of the 20th century, it is developing rapidly. Especially after the theories of construction of compactly-supported orthogonal wavelet, multi-resolution wavelet analysis and fast wavelet transform were proposed, the research concerning the wavelet continues to make major breakthroughs during the subsequent 10 years. As wavelet analysis can make multi-resolution analysis for the interesting part of the signal, known as signal microscope. Wavelet analysis has become one of the fastest and most spectacular subjects almost all the subjects, and Involved in or applied to all the fields of information.
Image compression plays an important role in multimedia technology, although the traditional image coding standard or compression methods are widely used, but several problems had not solved, such as low coding efficiency and low compression ratio etc. Image compression using wavelet has natural advantages such as high compression ratio, good progressive transmission and scalable quality control. Its principle is based on image features and the physiological characteristics of human vision, raw image is decomposed of high-frequency part and low-frequency part, low-frequency part represent profile of image, accordingly high-frequency part represent image details. Because the energy of image is concentrated mainly in the low-frequency part, through adopting of appropriate data encoding algorithm to compression the raw image.
Nowadays, several influential codec algorithms of the wavelet coefficients has been proposed, such as EZW algorithm (Embedded Zero-tree Wavelet), SPIHT algorithm (Set Partitioning In Hierarchical Trees) and EBCOT algorithm (Embedded Block Coding with Optimized Truncation) etc. and the EBCOT algorithm as one of the core for image coding technologies have been adopted for the new generation image compression standard JPEG200, much of the trend to replace JPEG. In 1996, Said and Pearlman proposed the SPIHT algorithm, which is another effective method base on the Zero-Tree, the advantage is even without entropy coding (such as arithmetic coding) after Zero-tree encoding higher compression ratio can obtain. Comparing with the EBCOT algorithm, compression rate is almost similar, meanwhile the SPIHT algorithm has faster compression speed and the algorithm is simpler.
This paper balance between the wavelet analysis theory and it’s application in image compression, all contents are cross-linked together and gradually advancing, and propose an improved SPIHT algorithm which is based on denary quantization. Comparing with the classical SPIHT algorithm, the improved SPIHT algorithm is better for its lower codec times, comparative time consumption and PSNR under the premise of unchanging bits surface encoding and progressive transmission feature of classical SPIHT. Finally, a MATLAB program is proposed to prove the rationality of the improved SPIHT algorithm.
图像压缩在多媒体技术中具有重要地位,传统图像编码压缩方法和标准虽得到广泛应用,但仍存在诸如编码效率低、压缩率低等诸多问题。小波用于图像编码压缩具有天然的优势,具有压缩率高、很好地渐进传输[1]、可伸缩的质量控制等优点。其原理是根据图像统计特征和人眼的生理特性[2],把图像分解为高频部分和低频部分,低频部分表示图像概貌,而高频部分表示图像细节。而图像能量主要集中在低频分量上,通过适当的编码算法达到数据压缩的目的。
目前已经产生了多种有影响的小波系数编解码算法,如嵌入式零树算法(Embedded Zero-tree Wavelet),SPIHT算法(Set Partitioning In Hierarchical Trees)、EBCOT算法(Embedded Block Coding with Optimized Truncation)等,其中以EBCOT算法为核心之一的图像编码技术已经被采纳为新一代图像编码压缩标准JPEG2000,大有取代JPEG的趋势。而1996年Said和Pearlman提出了SPIHT算法,也是一种很有效的零树编码方法,其优点是零树编码结束后,即使不经过熵编码(例如算术编码)也能获得较高的压缩比,和EBCOT算法相比,压缩率几乎差不多,但压缩速度快,算法简单。
本文兼顾小波分析的原理及其图像编码压缩中的应用,内容环环相扣,渐次推进,提出一种基于十进量化的SPIHT改进算法。该算法较经典SPIHT的最大优点是:在不改变SPIHT算法比特面编码和支持渐进传输特性的前提下,编解码次数大幅度降低,时间消耗和PSNR和标准SPIHT算法相当。最后给出MATLAB实现程序证明该改进算法的合理性。
Since the birth of wavelet analysis in the 1980s of the 20th century, it is developing rapidly. Especially after the theories of construction of compactly-supported orthogonal wavelet, multi-resolution wavelet analysis and fast wavelet transform were proposed, the research concerning the wavelet continues to make major breakthroughs during the subsequent 10 years. As wavelet analysis can make multi-resolution analysis for the interesting part of the signal, known as signal microscope. Wavelet analysis has become one of the fastest and most spectacular subjects almost all the subjects, and Involved in or applied to all the fields of information.
Image compression plays an important role in multimedia technology, although the traditional image coding standard or compression methods are widely used, but several problems had not solved, such as low coding efficiency and low compression ratio etc. Image compression using wavelet has natural advantages such as high compression ratio, good progressive transmission and scalable quality control. Its principle is based on image features and the physiological characteristics of human vision, raw image is decomposed of high-frequency part and low-frequency part, low-frequency part represent profile of image, accordingly high-frequency part represent image details. Because the energy of image is concentrated mainly in the low-frequency part, through adopting of appropriate data encoding algorithm to compression the raw image.
Nowadays, several influential codec algorithms of the wavelet coefficients has been proposed, such as EZW algorithm (Embedded Zero-tree Wavelet), SPIHT algorithm (Set Partitioning In Hierarchical Trees) and EBCOT algorithm (Embedded Block Coding with Optimized Truncation) etc. and the EBCOT algorithm as one of the core for image coding technologies have been adopted for the new generation image compression standard JPEG200, much of the trend to replace JPEG. In 1996, Said and Pearlman proposed the SPIHT algorithm, which is another effective method base on the Zero-Tree, the advantage is even without entropy coding (such as arithmetic coding) after Zero-tree encoding higher compression ratio can obtain. Comparing with the EBCOT algorithm, compression rate is almost similar, meanwhile the SPIHT algorithm has faster compression speed and the algorithm is simpler.
This paper balance between the wavelet analysis theory and it’s application in image compression, all contents are cross-linked together and gradually advancing, and propose an improved SPIHT algorithm which is based on denary quantization. Comparing with the classical SPIHT algorithm, the improved SPIHT algorithm is better for its lower codec times, comparative time consumption and PSNR under the premise of unchanging bits surface encoding and progressive transmission feature of classical SPIHT. Finally, a MATLAB program is proposed to prove the rationality of the improved SPIHT algorithm.
引文
[1]、求是科技 苏彦华等.Visual C++数字图像识别技术典型案例[M] .北京:人民邮电出版社,2004年,第 181~183 页.
[2]、郭梁.非线性编辑系统的压缩与存储技术[J] 西部广播电视 2002 年 05 期
[3]、赵荣椿等.数字图像处理导论[M] .西安:西北工业大学出版社,2000 年,第 151 页.
[4]、Mandelbrot B B. The Fractal Geometry of Nature[M]. San Francisco Freeman 1998.
[5] 、 Mallat S. A Theory for Multiresolution Signal Decomposition:The Wavelet Representation[J].IEEE Transaction PAMI,I,1989,11(7):674-693.
[6]、马晨光,郭雷.基于 3 维 SPIHT 编码的超光谱图像压缩[J] .量子电子学报,2005,Vol.22 No.5
[7]、黄普明,曹圣群,于伟,鞠德航.基于 SPIHT 算法的遥感图像高速实现方案[J] .宇航学报,2003,Vol.24 No.3
[8]、胡学龙,陆峰,郭振民,李云.基于 SPIHT 算法的医学图像无失真压缩[J] .电子工程师,2003,No.4
[9]、张宝文.一种改进的 SPIHT 图像压缩算法[J] .中国科技信息 2006 年(5).
[10] 、 Frederick W W,William A P.SPIHT image comparession without lists[A].Acoustics,Speech,and Signal Processing,2000[C].[s1]:[sn],2000,6,5-9
[11]、王晓东 刘文耀 朱昊 梁春永.无链表 SPIHT 图像提升小波编码的硬件算法[J] .西南交通大学学报,Vol40,No4.
[12]、Lin W K, Burgress N.Listless zerotree coding for color image[A].32nd Asilomar Conference on Signals, Systems and Computer[C]. Monrerey, CA, 1998.231~235.
[13]、Lin W K, Burgress N.Low memory color image zerotree coding[J]. Information, Decision and Control,1999,(2):91~95.
[14]、余汉成,王成华,夏永君.一种改进的无表 SPIHT 算法[J] .数据采集与处理,2005,Vol.20 No.4.
[15]、唐强,孙发鱼,于敏.一种改进的无链表小波零树编码算法[J] .计算机与数字工程,2006,第 5 期
[16]、杨淑莹.VC++图像处理程序设计(第二版)[M] .北京:清华大学出版社,北方交通大学出版社,2005 年,第 327 页.
[17]、唐朝京.信息论与编码基础[M] .长沙:国防科技大学出版社,2002 年,第 76 页.
[18]、傅祖芸.信息论-基础理论与应用[M] .北京:电子工业出版社,2001 年,第 162 页,第 168 页,第 176 页,第 183 页.
[19]、张旭东等.图像编码基础和小波压缩技术-原理、算法和标准[M] .北京:清华大学出版社,2004 年,第 26 页,第 75 页.
[20]、何东键,耿楠等.数字图像处理[M] .西安:西安电子科技大学出版社,2003 年,第 242页.
[21]、曾文曲等.分形小波与图像压缩[M] .沈阳:东北大学出版社,2002 年,第 83 页.
[22]、Pennebaker W B, Mitchell J L.JPEG Still Image Data Compression Standard[M].New York Van Nostrand Reinhold,1993.
[23]、刘涛等.实用小波分析入门[M] .北京:国防工业出版社,2006 年,第 23 页,第 40~41页,第 27 页,第 41 页,第 31 页.
[24]、童裕孙 编著.泛函分析教程[M] .上海:复旦大学出版社,2003 年.
[25]、胡广书.现代信号处理教程[M] .北京:清华大学出版社,2004 年,第 3~6 页.
[26]、王大凯,彭进业.小波分析及其在信号处理中的应用[M] .北京:电子工业出版社,2006年,第 22 页.
[27]、Mathworks Inc. Matlab help family[CP/DK]. Natick,Massachusetts,2002~2006
[28]、李世雄.小波变换及其应用[M] .北京:高等教育出版社,1997 年,第 20 页.
[29]、【法】Stephae Mallat 著 杨力华等译.信号处理的小波导引[M] .北京:机械工业出版社,2002 年,第 94 页.
[30]、【美】崔锦泰著,程正兴译.小波分析导论[M] .西安:西安交通大学出版社,1997 年,第 161~170 页.
[31]、Y. 迈耶 著,尤众译.小波与算子(第一卷)[M] .北京:世界图书出版公司,1992 年,第 29 页.
[32]、罗军辉 冯平等.MATLAB7.0 在图像处理中的应用[M] .北京:机械工业出版社,2005年,第 74~80 页.
[33]、冯象初等.数值泛函与小波理论[M] .西安:西安电子科技大学出版社,2003 年,第 83页.
[34]、[美]Ingrid Daubechies 著 李建平 杨万年译.小波十讲(Ten Lectures on Wavelets) [M] .北京:国防工业出版社,2004,第 239 页,第 245 页.
[35]、成礼智,郭汉伟等.小波与离散变换理论及工程实践[M] .北京:清华大学出版社,2005年,第 66 页,第 67~74 页.
[36]、孙延奎.小波分析及其应用[M] .北京:机械工业出版社,2005 年,第 152 页,第 143页,第 73 页,第 100~107 页.
[37]、陈佩.关于提升的小波变换.上海:上海交大博士毕业论文,2002
[38]、SHAPIRO JM. Embedded image coding using zerotrees of wavelet coefficients[J]. IEEE Transactions on Signal Processing 1993,41(12):3445-3462
[39]、殷人昆 陶永雷 谢若阳 盛绚华.数据结构(用面向对象方法与 C++描述)[M] .北京:清华大学出版社,1999 年,第 194 页.
[40]、ISO/IEC JTC1/SC29 WG1.JPEG2000 image coding system[S]
[41]、TaubmanD,OrdentlichE,WeinbergerM,ScroussiG,UenoI and OnoF. Embedded Block Coding in JPEG2000[J]. Proc.IEEE International Conference on Image Processing,2000,12,33-36.
[42]、Chung-JrLian,Kuan-FuChen,Hong-HuiChenandLiang-Gee Chen Analysis and architecture design of block-coding engine for EBCOT in JPEG2000[J].IEEE Transactionson Circuits and Systems for video technology,2003,13(3):219-230.
[43]、余敏,林争辉,林涛.JPEG2000 编码中 EBCOT 编码器的设计[J] .桂林电子工业学院学报,2004,Vol24,No6.
[44]、刘凯 李云松 吴成柯.高性能的 EBCOT 编码及其 VLSI 结构[J] .软件学报,2006,Vol.17,No7.
[45]、Said A,Pearlman W A. A new, fast and efficient image code based on set partitioning in hierarchial trees[J].IEEE Transanctions on Circuits and Systems for Video Technology,1996,6(3):243-250
[46]、何小海等.图像通信[M] .西安:西安电子科技大学出版社,2005 年,第 221 页,第 15页.
[47]、杜会斌.SPIHT 静止图像压缩技术研究[J] .无线电工程,2006,No2
[48]、陈杨,陈荣娟等.MATLAB6.X 图形编程与图像处理[M] .西安:西安电子科技大学出版社,2002 年.
[2]、郭梁.非线性编辑系统的压缩与存储技术[J] 西部广播电视 2002 年 05 期
[3]、赵荣椿等.数字图像处理导论[M] .西安:西北工业大学出版社,2000 年,第 151 页.
[4]、Mandelbrot B B. The Fractal Geometry of Nature[M]. San Francisco Freeman 1998.
[5] 、 Mallat S. A Theory for Multiresolution Signal Decomposition:The Wavelet Representation[J].IEEE Transaction PAMI,I,1989,11(7):674-693.
[6]、马晨光,郭雷.基于 3 维 SPIHT 编码的超光谱图像压缩[J] .量子电子学报,2005,Vol.22 No.5
[7]、黄普明,曹圣群,于伟,鞠德航.基于 SPIHT 算法的遥感图像高速实现方案[J] .宇航学报,2003,Vol.24 No.3
[8]、胡学龙,陆峰,郭振民,李云.基于 SPIHT 算法的医学图像无失真压缩[J] .电子工程师,2003,No.4
[9]、张宝文.一种改进的 SPIHT 图像压缩算法[J] .中国科技信息 2006 年(5).
[10] 、 Frederick W W,William A P.SPIHT image comparession without lists[A].Acoustics,Speech,and Signal Processing,2000[C].[s1]:[sn],2000,6,5-9
[11]、王晓东 刘文耀 朱昊 梁春永.无链表 SPIHT 图像提升小波编码的硬件算法[J] .西南交通大学学报,Vol40,No4.
[12]、Lin W K, Burgress N.Listless zerotree coding for color image[A].32nd Asilomar Conference on Signals, Systems and Computer[C]. Monrerey, CA, 1998.231~235.
[13]、Lin W K, Burgress N.Low memory color image zerotree coding[J]. Information, Decision and Control,1999,(2):91~95.
[14]、余汉成,王成华,夏永君.一种改进的无表 SPIHT 算法[J] .数据采集与处理,2005,Vol.20 No.4.
[15]、唐强,孙发鱼,于敏.一种改进的无链表小波零树编码算法[J] .计算机与数字工程,2006,第 5 期
[16]、杨淑莹.VC++图像处理程序设计(第二版)[M] .北京:清华大学出版社,北方交通大学出版社,2005 年,第 327 页.
[17]、唐朝京.信息论与编码基础[M] .长沙:国防科技大学出版社,2002 年,第 76 页.
[18]、傅祖芸.信息论-基础理论与应用[M] .北京:电子工业出版社,2001 年,第 162 页,第 168 页,第 176 页,第 183 页.
[19]、张旭东等.图像编码基础和小波压缩技术-原理、算法和标准[M] .北京:清华大学出版社,2004 年,第 26 页,第 75 页.
[20]、何东键,耿楠等.数字图像处理[M] .西安:西安电子科技大学出版社,2003 年,第 242页.
[21]、曾文曲等.分形小波与图像压缩[M] .沈阳:东北大学出版社,2002 年,第 83 页.
[22]、Pennebaker W B, Mitchell J L.JPEG Still Image Data Compression Standard[M].New York Van Nostrand Reinhold,1993.
[23]、刘涛等.实用小波分析入门[M] .北京:国防工业出版社,2006 年,第 23 页,第 40~41页,第 27 页,第 41 页,第 31 页.
[24]、童裕孙 编著.泛函分析教程[M] .上海:复旦大学出版社,2003 年.
[25]、胡广书.现代信号处理教程[M] .北京:清华大学出版社,2004 年,第 3~6 页.
[26]、王大凯,彭进业.小波分析及其在信号处理中的应用[M] .北京:电子工业出版社,2006年,第 22 页.
[27]、Mathworks Inc. Matlab help family[CP/DK]. Natick,Massachusetts,2002~2006
[28]、李世雄.小波变换及其应用[M] .北京:高等教育出版社,1997 年,第 20 页.
[29]、【法】Stephae Mallat 著 杨力华等译.信号处理的小波导引[M] .北京:机械工业出版社,2002 年,第 94 页.
[30]、【美】崔锦泰著,程正兴译.小波分析导论[M] .西安:西安交通大学出版社,1997 年,第 161~170 页.
[31]、Y. 迈耶 著,尤众译.小波与算子(第一卷)[M] .北京:世界图书出版公司,1992 年,第 29 页.
[32]、罗军辉 冯平等.MATLAB7.0 在图像处理中的应用[M] .北京:机械工业出版社,2005年,第 74~80 页.
[33]、冯象初等.数值泛函与小波理论[M] .西安:西安电子科技大学出版社,2003 年,第 83页.
[34]、[美]Ingrid Daubechies 著 李建平 杨万年译.小波十讲(Ten Lectures on Wavelets) [M] .北京:国防工业出版社,2004,第 239 页,第 245 页.
[35]、成礼智,郭汉伟等.小波与离散变换理论及工程实践[M] .北京:清华大学出版社,2005年,第 66 页,第 67~74 页.
[36]、孙延奎.小波分析及其应用[M] .北京:机械工业出版社,2005 年,第 152 页,第 143页,第 73 页,第 100~107 页.
[37]、陈佩.关于提升的小波变换.上海:上海交大博士毕业论文,2002
[38]、SHAPIRO JM. Embedded image coding using zerotrees of wavelet coefficients[J]. IEEE Transactions on Signal Processing 1993,41(12):3445-3462
[39]、殷人昆 陶永雷 谢若阳 盛绚华.数据结构(用面向对象方法与 C++描述)[M] .北京:清华大学出版社,1999 年,第 194 页.
[40]、ISO/IEC JTC1/SC29 WG1.JPEG2000 image coding system[S]
[41]、TaubmanD,OrdentlichE,WeinbergerM,ScroussiG,UenoI and OnoF. Embedded Block Coding in JPEG2000[J]. Proc.IEEE International Conference on Image Processing,2000,12,33-36.
[42]、Chung-JrLian,Kuan-FuChen,Hong-HuiChenandLiang-Gee Chen Analysis and architecture design of block-coding engine for EBCOT in JPEG2000[J].IEEE Transactionson Circuits and Systems for video technology,2003,13(3):219-230.
[43]、余敏,林争辉,林涛.JPEG2000 编码中 EBCOT 编码器的设计[J] .桂林电子工业学院学报,2004,Vol24,No6.
[44]、刘凯 李云松 吴成柯.高性能的 EBCOT 编码及其 VLSI 结构[J] .软件学报,2006,Vol.17,No7.
[45]、Said A,Pearlman W A. A new, fast and efficient image code based on set partitioning in hierarchial trees[J].IEEE Transanctions on Circuits and Systems for Video Technology,1996,6(3):243-250
[46]、何小海等.图像通信[M] .西安:西安电子科技大学出版社,2005 年,第 221 页,第 15页.
[47]、杜会斌.SPIHT 静止图像压缩技术研究[J] .无线电工程,2006,No2
[48]、陈杨,陈荣娟等.MATLAB6.X 图形编程与图像处理[M] .西安:西安电子科技大学出版社,2002 年.