多媒体技术讲座之小波图像编码.ppt

多媒体技术基础(第3版)第8章小波图像编码,林福宗清华大学计算机科学与技术系linfz2008年9月,2019年11月21日,第8章小波图像编码,2/50,第8章小波图像编码目录,8.1从子带编码到小波编码8.1.1子带编码8.1.2多分辨率分析8.1.3滤波器组与多分辨率8.1.4子带编码与小波编码8.1.5小波分解图像方法8.2PSNR失真度量法8.3EZW编码8.3.1介绍8.3.2算法8.3.3算法举例,8.4SPIHT编码8.4.1介绍8.4.2渐进图像的传输8.4.3分集排序算法8.4.4类型和变量8.4.5算法8.4.6算法举例8.5EBCOT编码简介8.5.1介绍8.5.2质量层的概念8.6JPEG2000简介8.6.1JPEG2000是什么8.6.2JPEG2000的基本结构8.6.3JPEG2000的主要功能8.6.4JPEG2000标准的文档,2019年11月21日,第8章小波图像编码,3/50,8.1从子带编码到小波编码,子带编码子带编码(subbandcoding，SBC)的基本思想把信号的频率分成几个子带，对每个子带分别进行编码根据每个子带的重要性分配不同的位数来表示数据子带编码的应用20世纪70年代，开始用于语音编码20世纪80年代，开始用于图像编码子带分割方法1986年Woods,J.W.等人曾经使用一维正交镜像滤波器(QMF)把信号的频带分解成4个相等的子带，如图8-1所示图8-1(a)表示分解方法，图8-1(b)表示其相应的频谱符号：2表示频带降低1/2，HH表示频率最高的子带，LL表示频率最低的子带这个过程可以重复，直到符合应用要求为止滤波器组称为分解滤波器树(decompositionfiltertrees),2019年11月21日,第8章小波图像编码,4/50,8.1从子带编码到小波编码(续1),图8-1Lena图的子带编码,2019年11月21日,第8章小波图像编码,5/50,8.1从子带编码到小波编码(续2),多分辨率分析S.Mallat于1988年在构造正交小波基时提出了多分辨率分析(multiresolutionanalysis)的概念，从空间上形象地说明了小波的多分辨率的特性，提出了正交小波的构造方法和快速算法，称为Mallat算法。根据Mallat和Meyer等科学家的理论，使用一级小波分解方法得到的图像如图8-2所示,图8-3Lena的多分辨率分析图像,2019年11月21日,第8章小波图像编码,6/50,8.1从子带编码到小波编码(续3),一级分解后继续分解的过程叫做多分辨率分析，即多级小波分解的概念。使用多级小波分解可得到分辨率不同的图像，这些图像被称为多分辨率图像(multiresolutionimages)图8-3表示Lena的多分辨率图像。其中，粗糙图像1的分辨率是原始图像的1/4，粗糙图像2的分辨率是粗糙图像1的1/4,图8-3Lena的多分辨率分析图像,2019年11月21日,第8章小波图像编码,7/50,8.1从子带编码到小波编码(续4),小波分解图像方法使用小波变换把图像分解成各种子带的方法有很多种。例如，均匀分解(uniformdecomposition)非均匀分解(non-uniformdecomposition)八带分解(octave-banddecomposition)小波包分解(wavelet-packetdecomposition)根据不同类型的图像选择不同小波的自适应小波分解(adaptivewaveletdecomposition)等八带分解是使用最广泛的一种分解方法属于非均匀频带分割方法，它把低频部分分解成比较窄的频带，而对每一级分解的高频部分不再进一步分解图8-4表示Lena图像的数据分解,2019年11月21日,第8章小波图像编码,8/50,8.1从子带编码到小波编码(续5),图8-4Lena图像的数据分解,2019年11月21日,第8章小波图像编码,9/50,Standardtestimage,LennaSoderberg(neSjblom)TheFirstLadyoftheInternetSize：512512pixelsColors：24bits/pixelLena24.bmp:768KB,/cnspci/misc/lenna/,In1972,2019年11月21日,第8章小波图像编码,10/50,Standardtestimage(contd1),LennaSoderberg(Sjblom)andJeffSeidemanInMay1997atIS&Ts(ImagingScienceandTechnology)50thAnniversaryconference,/cnspci/misc/lenna/,2019年11月21日,第8章小波图像编码,11/50,Standardtestimage(contd2),Girl(Tiffany)Size512512pixelsColor24bits/pixeltiffany24.bmp768KB,/database/,2019年11月21日,第8章小波图像编码,12/50,Standardtestimage(contd3),Mandrill(a.k.a.Baboon)Size512512pixels,Color24bits/pixelmandrill24.bmp768KB,/database/,2019年11月21日,第8章小波图像编码,13/50,Standardtestimage(contd4),PeppersSize512x512pixelsColor24bits/pixelpeppers24.bmp768KB,/database/,2019年11月21日,第8章小波图像编码,14/50,Standardtestimage(contd5),ElaineSize512512pixelsGrayscale8bits/pixelElaine8.bmp256KB,/database/,2019年11月21日,第8章小波图像编码,15/50,Standardtestimage(contd6),BarbaraSize512512pixelsGrayscale8bits/pixelbarbara8.bmp256KB,2019年11月21日,第8章小波图像编码,16/50,Standardtestimage(contd7),GoldhillSize512512pixelsGrayscale8bits/pixelgoldhill8.bmp256KB,2019年11月21日,第8章小波图像编码,17/50,8.2图像失真度量法,峰值信号噪声比(PSNR)在图像编码系统中，常用峰值信号噪声比(peaksignaltonoiseratio,PSNR)来衡量最大像素值的平方与均方差(meansquareerror，MSE)之比5,对8位二进制图像：,其中，,为原始图像的像素值,为解压缩之后的像素值,2019年11月21日,第8章小波图像编码,18/50,8.2图像失真度量法(续),其他方法规格化均方差(normalizedmeansquareerror，NMSE),信号噪声比(signaltonoiseratio，SNR),平均绝对误差(meanabsoluteerror，MAE),2019年11月21日,第8章小波图像编码,19/50,EntropyCodingofWaveletCoefficients,EZWShapiro-1993EmbeddedZerotreeCodingofWaveletCoefficientsSPIHTSaid-Pearlman-1996SetPartitioninginHierarchicalTreesEBCOTTaubman-1998EmbeddedBlockCodingwithOptimalTruncationAdoptedbyJPEG2000,2019年11月21日,第8章小波图像编码,20/50,8.3EZW编码,EZW是什么embeddedzerotreewavelet的缩写EZW是多分辨率图像编码算法Lewis，A.S.和Knowles,G.于1992年介绍了表示小波变换系数的一种树形数据结构6；Shapiro,J.M.于1993年将这种树形数据结构称为“零树(zerotree)”，并开发了称为嵌入式零树小波(embeddedzerotreewavelet，EZW)的图像编码算法7，用于熵编码,图8-5EZW算法结构,2019年11月21日,第8章小波图像编码,21/50,8.3EZW编码(续1),EZW(嵌入式零树小波)图像编码概要“小波”表示该算法以离散小波变换为基础，以变换后的大系数比小系数更重要以及高频子带中的小系数可以忽略为背景“零树”表示小波变换系数之间的数据结构，用同一方向和相同空间位置上的所有小波系数构成一棵树，如果树根及其子孙的小波系数的绝对值小于某个给定域值，则这棵树就称为零树“嵌入”表示一幅图像可以分解成一幅低分辨率图像和分辨率由低到高的许多子图像按用户对图像分辨率的不同要求，EZW编码器进行多次编码，每进行一次编码，域值降低1/2，水平和垂直方向的图像分辨率分别提高1倍,2019年11月21日,第8章小波图像编码,22/50,8.3EZW编码(续2),编码从最低分辨率图像开始幅度大于域值的正系数用符号P表示幅度小于域值的负系数用符号N表示树根节点上的系数幅度小于域值而树枝中有大于域值的非零树用符号Z表示零树用符号T表示编码输出符号集P，N，T，Z，0，1中的一系列符号对整幅图像编码一次，生成一种分辨率图像在扫描过程中需维护两种表小波系数的符号表量化表,2019年11月21日,第8章小波图像编码,23/50,8.3EZW编码(续3),标记小波变换后的系数、名称和符号，以三级小波分解为例，见图8-6图中的数字1、2和3表示分解的级数编号LL3表示第3级的低频子图像HL3表示第3级分解在水平方向上的子图像LH3表示第3级分解在垂直方向上的子图像HH3表示第3级分解在对角线方向上的子图像其他的组合符号依此类推,图8-6Lena三级分解图像,2019年11月21日,第8章小波图像编码,24/50,8.3EZW编码(续4),系数树各级子图像中的系数之间的关系可用树的形式描述，见图8-7(a)最低频率的子图像在左上角，最高频率的在右下角由同一方向和相同空间位置上的所有小波系数组成一棵树例如，从第三级子图像HH3、第二级子图像HH2到第一级子图像HH1的相应位置上的所有系数构成一棵下降树,构造方法,图8-7EZW编码树的构造,2019年11月21日,第8章小波图像编码,25/50,8.3EZW编码(续5),按箭头所指的方向，各级系数的名称分别用祖系数、父系数、子系数和孙系数来称呼例如，LL3的系数为63,HH2和HH1的系数分别为3和4,6,3,-2,由这些系数构成的树见图8-7(b)。如果把63指定为父系数，3就称为子系数，而4,6,3,-2中的4个系数就称为孙系数图中有两棵树图8-8(a)：非零树图8-8(b)：零树,(b)小波系数举例,图8-7EZW编码树的构造,2019年11月21日,第8章小波图像编码,26/50,8.3EZW编码(续6),零树假设编码开始时的阈值为T0=32，由于63比32大，这样的树称为非零树，见图8-8(a)假设下次编码时的阈值为T1=16，把-13当作父系数，它的幅度比16小，而它的所有4个子系数的幅度都比16小，这种树称为零树，见图8-8(b)，系数-13称为零树根定义零树的目的可用一个预先定义的符号表示，从而可提高压缩比,2019年11月21日,第8章小波图像编码,27/50,8.3EZW编码(续7),扫描方法对小波系数进行编码的次序叫做扫描，两种方法光栅扫描(rasterscan)，见图8-9(a)迂回扫描(mortonscan)，见图8-9(b),(a)光栅扫描(b)迂回扫描图8-9小波变换系数扫描方法,2019年11月21日,第8章小波图像编码,28/50,8.3EZW编码(续8),算法阈值T的选择初始阈值：,其中,表示其值为等于或小于x的最大整数(x),MAX(.)表示最大的系数值，,表示小波变换分解到第i级时的系数,以后每扫描一次，阈值减少一半,2019年11月21日,第8章小波图像编码,29/50,8.3EZW编码(续9),给系数分配符号每一次扫描需执行两种扫描并产生两种输出符号主扫描(dominantpass)：将小波系数与阈值进行比较，指定表8-1中的4个系数符号之一。产生系数符号序列辅扫描(subordinatepass)：把主扫描取出的带符号P或N的系数进行量化，产生对应量化值的量化符号“0”或“1”,2019年11月21日,第8章小波图像编码,30/50,8.3EZW编码(续10),表8-1EZW系数符号集,2019年11月21日,第8章小波图像编码,31/50,8.3EZW编码(续11),(1)主扫描：扫描每一个系数以产生系数符号如果系数幅度大于阈值(T)且为正，输出符号P(positive)，如果系数幅度的绝对值大于阈值(T)且为负，输出符号N(negative)如果系数是零树根，输出T(zerotree)如果系数幅度小于阈值但树中有大于阈值的子孙系数，输出孤立零符号Z(isolatedzero),2019年11月21日,第8章小波图像编码,32/50,8.3EZW编码(续12),(2)辅扫描：量化带符号P和N的系数在量化系数之前要构造量化器量化器的输入间隔为Ti-1,2Ti-1)，该间隔被1.5Ti-1分成两个部分：Ti-1，1.5Ti-1)和1.5Ti-1,2Ti-1)，量化间隔为0.5Ti-1,其中i为第i次编码量化器的输出为量化符号“0”和“1”，“0”对应量化值为(1.5-0.25)Ti-1,“1”对应量化值为(1.5+0.25)Ti-1例如，第一次扫描时的阈值T0=32，量化器的间隔就为32，64)，该间隔32，64)被48分成两个相等的部分：32，48)和48，64)，量化间隔为16。对系数进行量化时，如果幅度在32，48)的范围里，该系数的量化值为“0”，对应的量化值为(1.5-0.25)T0=40；如果幅度在48，64)的范围里，该系数的量化符号为“1”，它的量化值为(1.5+0.25)T0=56，详见图8-13。,2019年11月21日,第8章小波图像编码,33/50,8.3EZW编码算法举例,实例假设有一幅88的图像，经过3级分解的小波图像系数见图8-10(a)，扫描方式见8-10(b),(a)小波图像数据(b)迂回扫描图8-1088小波变换图像,2019年11月21日,第8章小波图像编码,34/50,8.3EZW编码算法举例(续1),树结构图8-10(a)中最低分辨率子图像(即第3级)中的每一个系数在高一级分辨率子图像(即第2级)中有3个子系数，它们之间构成的树见图8-11(b),(a)88子图像小波变换系数(b)最低频带小波变换系数树图8-11编码树的结构(1),2019年11月21日,第8章小波图像编码,35/50,8.3EZW编码算法举例(续2),在其他子图像中，任何一个系数在高一级分辨率子图像中都有4个子系数与它有关，它们之间构成的树见图8-12(b)，图中只表示了一部分的树,(a)88子图像系数(b)2级子图像部分系数树图8-12编码树的结构(2),2019年11月21日,第8章小波图像编码,36/50,8.3EZW编码算法举例(续3),第1次扫描步骤1:最大的系数为63，因此选择T0=32步骤2:指定系数的符号存放系数符号的缓存为D1每个系数与阈值32比较。当系数为符号T时，其所有子孙系数就不再扫描，并用“”表示，比较结果见图8-13(a)D1中的系数符号:PNTTPTTZTTTTTTTPTT,(a)系数符号和标记(b)系数量化图8-13第一次主扫描,2019年11月21日,第8章小波图像编码,37/50,8.3EZW编码算法举例(续4),步骤3:对带符号P/N的系数进行量化存放量化符号的缓存为S1阈值T0=32，大于32的4个系数为63，34，49，47用48把间隔32，64)分成两部分，见图8-13(b)。幅度在32，48)中的系数指定其符号为“0”,幅度在48，64)中的系数指定其符号为“1”，这4个系数的量化符号见表8-2由于解码器重构的系数幅度按(1.5+0.25)T进行计算，因此重构数据的绝对误差在17之间，即小于0.25T系数63-P,34-N,49-P,47-P在S1中的量化符号：1010,表8-2第一次辅扫描量化表,2019年11月21日,第8章小波图像编码,38/50,8.3EZW编码算法举例(续5),步骤4：重新排列带P/N符号的数据。为便于设置第二次扫描时所用的量化间隔，以提高解码的系数精度。把系数集63-P,34-N,49-P,47-P排列成63-P,49-P,34-N,47-P步骤5：输出编码信息编码器输出两类信息，一类是给解码器的系数符号系列等信息，另一类是用于下一次扫描的阈值和大于阈值的系数值等信息。用于给解码器的系数符号系列等信息包含三种：HEADER(即T0=32),D1:PNTTPTTZTTTTTTTPTT“AND”S1:1010用于下次扫描的阈值和大于阈值的系数值等信息包含三种：T0=32,63-P,49-P,34-N,47-P“AND”子带图像第2次扫描（略）,2019年11月21日,第8章小波图像编码,39/50,8.3EZW编码算法举例(续6),解码EZW的解码过程是EZW编码的逆过程，编码时扫描多少次，解码时也可以解多少次解码过程大致分为三个步骤解码器设置阈值构造逆量化器开始解读位流中包含的位置和小波系数值注意解码时用的逆量化器与编码时用的量化器相同，因此简称为量化器像编码时那样，每次解码都需要构造量化器,2019年11月21日,第8章小波图像编码,40/50,8.3EZW编码算法举例(续7),第1次解码解码器开始时的阈值T0=32，接收到来自编码器第一次扫描输出的系数符号为PNTTPTTZTTTTTTTPTT/1010量化符号与系数符号之间有如下的对应关系,2019年11月21日,第8章小波图像编码,41/50,8.3EZW编码算法举例(续8),按照编码时的扫描和量化方法进行解码。第1个系数符号是P，对应的量化符号位是“1”，因此第1个系数是56第2个系数符号是N，对应的量化符号位是“0，因此第2个系数是-40第3个系数符号是T，在相应的图像系数位置上用“0”表示它的系数第一次解码的结果见图8-16用“0”表示的系数已经扫描过，它们对应符号T或者Z用“”表示的系数不需要扫描，是零树根的子孙,2019年11月21日,第8章小波图像编码,42/50,8.3EZW编码算法举例(续9),在第一次解码之后，解码器需要判断是否要进一步重构比较精细的图像如果不需要，则退出解码如果需要则进入第二次解码,图8-16第一次解码,2019年11月21日,第8章小波图像编码,43/50,8.3EZW编码算法举例(续10),第二次解码分两步提高第一次解码时得到的系数精度求解未解码的系数使用编码器生成的第二次编码时的信息D2:NPTTTTTTTTTTTTTTTS2：100110解码结果见图8-17下一步确定是否继续进行解码以得到更精细的图像。如果要退出，则把两次解码的结果合成之后就可退出如果继续，则进入第三次解码,2019年11月21日,第8章小波图像编码,44/50,8.3EZW编码算法举例(续11),图8-17第二次解码,2019年11月21日,第8章小波图像编码,45/50,8.4SPIHT编码,SPIHT简介setpartitioninginhierarchicaltrees的缩写AmirSaid和WilliamPearlman于1996年对EZW的改进算法10，称为“层树分集”算法具有人们所期望的特性，例如，图像的渐进传输；比较高的PSNR；复杂度比较低；计算量比较少；位速率容易控制等算法依据经过小波变换后，图像的大部分能量都集中在低频子带编码方法最先传送幅度大的系数，解码器即使在低速率应用环境下也可得到图像的大部分信息编码树的结构与EZW算法的结构类似，每一个节点要么没有子节点，要么有4个子节点在编码过程中用三个变量列表存储重要系数和不重要系数算法和举例请看教材8.4,2019年11月21日,第8章小波图像编码,46/50,8.5EBCOT编码,EBCOT介绍embeddedblockcodingwithoptimizedtruncation的缩写，可译成“最佳截断嵌入码块编码”；DavidTaubman在1999年发表的编码算法12对小波变换后的子带系数进行量化和编码的方法。把每一个子带的小波变换系数分成独立编码的码块(code-block)，并且对所有的码块使用完全相同的编码算法见图8-21：图(a)表示使用小波变换进行三级分解之后的图像子带；图(b)表示经过这种变换之后各个子带的Lena图像每个码块的编码只用码块自身的信息产生单独的嵌入位流(bitstream)每个码块的嵌入位流可被“截断”成长度不等的位流，生成不同的位速率,2019年11月21日,第8章小波图像编码,47/50,“最佳”截断：给定目标位速率，每个码块的嵌入位流应使重构图像的失真程度最小,(a)图像子带划分法(b)Lena图像子带图8-21独立编码的码块,2019年11月21日,第8章小波图像编码,48/50,第8章小波图像编码(参考文献),参考文献和站点Daubechies,I.,OrthonormalBasesofCompactlySupportedWavelets,Comm.PureandAppliedMath.,vol.41,Nov.1988,pp.909-996A.Cohen,I.DaubechiesandJ.C.Feauveau.Biorthogonalbasesofcompactlysupportedwavelets.CommunicationsonPureandAppliedMathematics,45(5)：485-560,June1992WimSweldens，TheConstructionandApplicationofWaveletsinNumericalAnalysis，May18,1995Sweldens,W.TheLiftingScheme:AConstructionOfSecondGenerationWavelets.SiamJ.Math.Anal,Vol.29,No.2,1997A.K.Jain,FundamentalsofDigitalImageProcessing,Prentice-Hall,EnglewoodCliffs,NewJersey,1989.Lewis,A.S.andKnowles,G.ImageCompressionUsingthe2-DWaveletTransform,IEEETrans.IP,vol.1,no.2,April1992,pp.244-250.Shapiro,J.M.EmbeddedImageCodingUsingZerotreesofWaveletCoefficients,IEEETrans.SP,vol.41,no.12,Dec.1993,pp.3445-3462ClemensValenshomepage,http:/perso.wanadoo.fr/polyvalens/clemens/clemens.htmlGhassanAl-Regib,EmbeddedZerotreeWaveletEncoding(EZW)BasedonShariposPaper,04/05/2000,GeorgiaInstituteofTechnology,Atlanta,GA,2019年11月21日,第8章小波图像编码,49/50,第8章小波图像编码(参考文献续),参考文献和站点(续)A.SaidandW.Pearlman,Anew