收稿日期:2006-04-29作者简介:秦琴(1983-),女,2005级硕士研究生,主要研究方向为图像编码与图像处理.E -mail :qingqing -634@ 通讯作者:罗代升.E -mail :dshl uo @hotmail .com文章编号:　0490-6756(2007)03-0525-06一种改进的SPIH T 图像编码算法秦　琴,滕奇志,罗代升,余艳梅,吴晓红(四川大学电子信息学院图像信息研究所,成都610064)摘　要:在研究图像小波分解系数特点和SPIH T 算法的基础上,提出了一种改进的SPIHT 图像编码压缩算法.针对SPIH T 算法没有利用同一子带相邻重要系数的相似性及在阈值为4、2、1这三层的大编码量,提出了在这三层编码用邻域内重要系数的绝对值均值代替各重要系数的绝对值来进行编解码;并且加深对大系数的重视程度,在前几个阈值时,对首次发现的重要系数进行三位二进制位的精细化.实验表明,在中、高压缩比情况下,本算法的重构图像峰值信噪比(PSNR )要优于原算法,并且视觉质量更好.关键词:图像编码压缩;小波分解;零树编码;EZW 算法;SPIH T 算法中图分类号:TN957.52 文献标识码:AAn improved image coding algorithm based on SPIHTQIN Qin ,TENG Qi -zhi ,LUO Dai -sheng ,YU Y an -mei ,WU Xiao -hong(Image I nformation Institute ,College of Electronics and Information Engineering ,Sichuan University ,Cheng du 610064,China )A bstract :After the studying of image w avelet decomposing coefficients and SPTHT ,an improved image cod -ing algorithm is introduced based on SPTH T .It aims at the g reat coding amount in the scanning process of threshold 4,2and 1,and proposes that ,in those processes ,average absolute value of adjacent domain 's im -po rtant coefficients is coded instead of each important coefficient of that adjacent domain ,utilizing the similar -ity of adjacent important coefficients in the same sub -band .The improved algo rithm also attaches much value to bigger coefficients .In the scanning process of bigger thresholds ,it employs three bits for the refinement of the important coefficients ,w hich are detected to be important for the first time .The experimental results show that the Peak Signal -to -Noise Ratio (PSN R )of the reconstructed image of the improved algo rithm is better than that of the original algo rithm ,also w ith a better visual quality .Key words :image com pression ,w avelet transform ,zero tree coding ,EZW ,SPIH T1　引　言若按照对小波系数数据结构的利用方式进行划分,基于小波的图像编码主要分为两种类型[1]:一类是以嵌入式零树小波EZW [2]编码和多级树集合划分SPIH T [3]算法为代表;另一类是形态学小波编码[4].本文是关于第一类编码的改进.EZW 编码算法很好地利用了小波系数的特性,使得输出码流具有嵌入特性,它的重要性排序和分级量化思想被许多算法所采用.但由于采用了逐次逼近的量化方法(SAQ )[2],对每一个阈值都要进行零树扫描,而且在每一个阈值处理时,都要扫描多棵零树,所以整个编码过程要多次扫描图象,且形成多棵零树,造成效率很低.另外,一棵零树即2007年6月　第44卷第3期四川大学学报(自然科学版)Journal of Sichuan University (Natural Science Edition )　Jun .2007Vol .44　No .3是一组非重要系数的集合,那么如果在一棵零树中,包含更多的元素,就意味着包含了更多的非重要系数,也就包含了更多的数据,这样就更有利于数据压缩,而EZW算法在这点上还存在一定的树间冗余,例如,在小波系数中,如果有个树结构的树根是重要的,但除了树根外的其它系数都是不重要的,对于这种情况,EZW算法中的零树就不能有效地表示[5,6],而SPIH T算法就进一步利用了这种树间冗余,提出了空间方向树(SO T)[3]的概念,把一棵树分得更细,改进了EZW对重要图的表示方法.但是SPIHT算法也存在一些不足:对所有子带进行同样的编码规则,没有充分利用小波变换系数的特点以及视觉对不同频带图像的敏感度不同的特性;虽然充分利用了不同子带间同一方向的非重要系数的相关性,但是并没有充分利用同一子带(特别是高频子带)中相邻重要系数间的相关性.针对这些不足,我们在SPIHT算法的基础上,利用小波系数同一子带相邻重要系数的相关性,并考虑了视觉特性,对小波系数的合理组织和重要系数的量化方法进行改进,提出一种嵌入式小波零树编码的改进算法.2　SPIHT算法[3]SPIH T算法继承了EZW算法的三个主要思想:1)把小波系数按照幅值排序编码传输,同时解码器也按同样的算法,以实现从执行中复制编码的排序信息;2)细化重要系数的位平面传输;3)利用小波系数不同尺度同一方向的系数间的自相似性[3].SPIH T算法同样利用了树的结构,并且对重要的树集合进行进一步的分割,目的是使更多不重要系数包含在同一个集合里,从而提高压缩效率.在SPIHT算法中,使用了如下的集合定义:图1　SPIHT算法的集合定义F ig.1　The definition of sets in SPIHT其中Z(i,j)为系数x(i,j)及其所有后代节点的集合,D(i,j)是系数x(i,j)的所有后代节点的集合,O(i,j)是系数x(i,j)的直接后代节点的集合,L(i,j)是系数x(i,j)除去直接后代的其它所有后代节点的集合.集合分割策略为:Z(i,j)=x(i,j)+D(i,j)(1)D(i,j)=O(i,j)+L(i,j)(2)L(i,j)=∑k,l D(k,l),(k,l)∈O(i,j)(3)SPIH T算法通过初始化、分类扫描、细化扫描和阈值更新四个子过程来完成图像的编码,过程中使用了三个链表来记录相关信息:不重要系数链表(LIP)、不重要集合链表(LIS)以及重要系数链表(LSP).初始化就是把整个系数矩阵分成了树头节点x(i,j)(放入LIP表)和剩余集合D(i,j)(放入LIS表).分类扫描就是从以上的所有x(i,j)和D(i,j)中找出重要系数并放入LSP表中,以供细化处理,在这个过程中就用到了集合分割策略,不断地对重要集合进行分割,直到找出所有的重要系数,并放入LSP表中.细化扫描,就是对LSP表中的每一项(除了在当前阈值进入LSP表的系数),在阈值为2n时,输出它的第n个位平面的值.阈值更新,就是将n减1,即阈值减半,然后又重复进行分类扫描和细化扫描,直到编码结束,或达到目标码率,停止编码.3　改进的SPIH T算法3.1　算法描述SPIH T算法充分利用了不同子带间同一方向526四川大学学报(自然科学版)第44卷的非重要系数的相关性,但是并没有利用同一子带中相邻重要系数间的相关性,而且它通过比较系数与变化的阈值来确定重要系数并编码,当阈值T 较大时,重要系数的数量很小,阈值T较小时,得到的重要系数急剧增加,致使编码量也骤然猛增. SPIH T算法的压缩编码量75%以上是阈值为4, 2,1这3轮扫描所产生的,因此,这3轮编码的处理对最终编码量的压缩起着至关重要的作用[7].本文算法就是对这三层的处理采用一种改进的方式,在这种改进方式中,就利用了同一子带相邻重要系数的相关性.另外,在改进算法中,对大系数的重视程度得到了提升,这表现在对发现的重要系数进行多位精细化.改进算法是在原算法的基础上,把对三个表的处理方式分成了两种,即在阈值大于4时,有一种处理方式,在阈值小于或等于4时,用另一种处理方式进行处理.我们不妨称其为方式一和方式二.方式一与原算法的处理原理基本相同,只是在处理LSP表时,对首次发现的重要系数,原算法不进行处理,在新算法中却进行了三位二进制位的细化处理.如果k是在阈值为T x时进入LSP表的系数,那么在阈值为T x这层扫描LSP表时,对k的细化处理如下: 如果T x≤k<1.125T x 细化编码输出000;解码为1.0625T x 如果1.125T x≤k<1.25T x细化编码输出001;解码为1.1875T x 如果1.25T x≤k<1.375T x细化编码输出010;解码为1.3125T x 如果1.375T x≤k<1.5T x细化编码输出011;解码为1.4375T x 如果1.5T x≤k<1.625T x细化编码输出100;解码为1.5625T x 如果1.625T x≤k<1.75T x细化编码输出101;解码为1.6875T x 如果1.75T x≤k<1.875T x细化编码输出110;解码为1.8125T x 如果1.875T x≤k<2T x细化编码输出111;解码为1.9375T x 上述处理过程也可以这样理解:在阈值为2m 时处理LSP表,对在本轮阈值中扫描发现的重要系数,用它们的n=m-1、m-2和m-3这三个位平面的值来进行细化.而对于在本轮扫描以前就进入LSP表的系数,就用一位二进制位,即它们的n=m-3这个位平面的值,来进行细化.按照这样处理,当方式一处理完时,LSP表中的系数都已完成编码,这时进行一个对LSP表的清除操作.方式二也分为对三个表的分别处理,依先后顺序仍然是LIP、LIS以及LSP表,相对于原算法的改进主要体现在以下几个方面:(1)对LIP表的处理就是在原算法的基础上,改为以四邻域为一个单元,对重要系数进行扫描,即以单元为索引来进行扫描,对一个四邻域单元内的重要系数,编码他们的绝对值均值,且只编码这一个值,这样就进一步达到了压缩的目的,如果这个四邻域里只发现一个重要系数,当然就编码它本身.(2)对LIS表的处理,改进算法相对于原算法只是在对D类集合的处理上有所改变,即当这个D 类集合重要并编码它的四个孩子节点时,也以四邻域为单元进行处理,即用所发现的重要系数的绝对值均值来代替各个重要系数放入LSP表中,已待进行量化编码;对于非重要的系数,仍然标志为一个邻域单元,放入LIP表中,以方便在以后扫描LIP表时,以单元为索引对它们进行处理.(3)对LSP表的处理,原理同原算法一样,只是这时LSP表中的元素不一定是系数本身,有可能是几个重要系数的绝对值均值,这时的重要系数最多有三个位平面,就用原来的一位二进制位细化就可以了.3.2　算法实现具体程序设计时,主要是几个表中元素的结构设计.原算法中,LIP表用象素坐标就可以了,在改进算法中,为了标志邻域,新增了一个标志位,也把它作为在方式二处理时的索引.LIS表的结构与原来一样,就是各集合的类型标志和位置标志.LSP 表在编码和解码时有所区别,在编码时,结构与原算法一样,就是象素的绝对值(原算法也可以用坐标值),只是在方式二处理时,它有可能表示几个象素的均值的绝对值,不方便用坐标值进行对应,所以选择象素的绝对值.但LSP表在解码时,由于一个细化编码值可能同时对应一个邻域中的几个系数,为了分别给一个邻域的几个重要系数赋值,要明确知道这几个重要系数的坐标,所以在解码的方式二处理中,当发现系数重要时,不管是单独的一527第3期秦琴等:一种改进的SPIH T图像编码算法　个,或是一个邻域中的几个,都要放入LSP表中,只是对同一邻域的几个系数,也要用一标志位表明,并且用该标志作为扫描LSP表的索引,这样是为了让编码和解码对应.即,当用方式二处理LSP 表时,如果编码和解码同时进行,那么同一时刻,编码方的LSP表的长度和解码方的LSP表的长度不一样,但是和解码方以邻域标志作为索引的长度一样.以下是编码程序的流程图,解码与之相对应.图2　改进算法编码流程Fig.2　T he coding flo w of the improved algorithm 初始化工作时,阈值T的赋值与SPIH T一样,是T=2n(4)n=[log2(max(i,j){C i,j})](5)初始化LIP表时,用最低子带的系数坐标以及每个系数的标志位,由于这里的系数是最低子带的,我们不对它们进行邻域处理,所以每个系数的标志位都设置的不一样;LIS表初始化时放的是最低子带中有后代的系数坐标,并标志为类型D集合;LSP表初始化为空.对于每个处理流程,都是按照前面描述的处理方法进行.从第一个处理块开始的以后每一步中,都可以检查编码量,当达到目标要求时,也可以停止编码.这里列出的是基于阈值控制的一个完整的编码过程.4　结果与分析根据本文提出的改进算法,对512×512的8bpp的标准灰度图像Lena进行了编解码实验,在相同压缩比下,从恢复图像的峰值信噪比(PSN R)方面与SPIH T算法进行了对比,实验结果如表1.实验中采用Daubechies的D6小波基对图像进行5级小波分解.图3为Lena原图,图4至图7为改进后的算法和原算法重建图像的视觉质量比较.表1　不同压缩比下的PSN R比较(*表示备注)T ab.1　T he compare of PSN R inseveral compression ratio压缩比(Lena)PSN RSPIHT本文算法3(*)41.8772dB41.6800dB440.1029dB40.2161dB635.9760dB37.0987dB835.4338dB36.1097dB10(*)34.5238dB33.4539dB1231.4114dB33.0714dB1431.2667dB32.5312dB1631.0251dB31.6481dB从表中的数据可以看出:在低压缩比的情况下(这里压缩比为3时),原算法比改进算法的PSNR稍好,这是不难理解的.这里,压缩比为3时,原算法的解码器此时正在扫描最后一次LSP表,而改进算法的解码器此时刚开始它的最后一次LSP表的扫描,实际上这时它们都已经接近完全编码了, 528四川大学学报(自然科学版)第44卷图3　LENA 原图F ig .3　O riginal L ENA图4　压缩比为16的LENA 重构图(原算法)F ig .4　Reconstructed LENA (original al -gorithm )(compressio n ratio =16)图5　压缩比为16的LENA 重构图(改进算法)F ig .5　Reconstructed LENA (improved al -gorithm )(compressio n ratio =16)图6　压缩比为12的LENA 重构图(原算法)Fig .6　Reconstructed L EN A (orig inal al -go rithm )(compression ratio =12)图7　压缩比为12的LENA 重构图(改进算法)Fig .7　Reconstructed LENA (impro ved al -go rithm )(compression ratio =12)因为改进算法在低阈值时用的邻域内各重要系数的绝对值均值代替各重要系数本身来编码,所以在接近完全编码的情况下,改进算法相比原算法就没有优势了.在压缩比大于4的情况下,我们所提算法的解码重构图的PSNR 比原算法有所提高,但是发现在压缩比等于10的时候(备注2),本算法的PSNR 比原算法低,通过实验发现:原算法在阈值为4的这一层的解码这个时候已经完成了,并且正在进行阈值为2的解码;而改进算法这个时候还在进行阈值为4的解码.开始的时候(压缩比较大的时候),改进算法较原算法的优势源于它对大系数的重视程度,即在阈值为4的时候,以前发现的重要系数(即大于8的系数)此时已经完全精细化了,而原算529第3期秦琴等:一种改进的SPIH T 图像编码算法　法此时已经完成了阈值为4的解码,那些大于4的系数虽然还没有被完全精细,但也已相当精细,并完全浮现出来了;大于2的系数一部分也浮现出来了;相比之下,改进算法这时大于4的系数都还没有完全浮现出来,大于2的系数就一个都还没有发现.这个结果说明:大系数的稍粗略重构,加上部分小系数的粗略重构在一定程度上比大系数的完全重构的重要性更高.虽然改进算法在相同压缩比时比原算法的PSN R只高一点,但是从重构图来看,其优势就比较明显,因为在中高压缩比时,原算法可见一些小块,如图4和图6;而在同样压缩比下的改进算法就没有,如图5和图7,这说明改进算法在视觉效应上有其优势.5　结　语在分析了SPIHT算法的基础上,提出一种改进算法,改进算法在两方面对原算法进行了改进.首先,针对原算法没有利用同一子带相邻重要系数的相似性这点,在阈值为4,2,1这三层,用邻域内重要系数的绝对值均值代替各重要系数的绝对值来进行量化编码,因为阈值为4,2,1的这三层是产生编码量最多的三层,也是高频子带的重要系数出现机率最大的几层,高频子带的重要系数大多数值很小,其重要性就相对较弱,且相邻系数的相似性比低频子带的更大,所以在这三层的改进算法相当于对高频小系数进行一种均值编码.其次,对低频子带的大系数的重视程度加深,在前几层阈值精细化重要系数时,对于首次进入LSP表的重要系数进行3位二进制细化.这两方面都体现了一个思想:对大系数重视和对小系数的轻视.实验结果表明,本文算法在中、高压缩比下比原SPIH T算法有一定优势,特别是在视觉上的优势比较明显.参考文献:[1]　张宗平,刘贵忠,杨一文.嵌入分层聚类的小波零树图像编码[J].计算机学报,2002,25(11):1189. [2]　Shapiro J M.Embedded imag e coding using zerotrees ofw avelet coefficients[J].I EEE T ransactio ns on Sig nalP rocessing,1993,41(12):3445.[3]　Said A,Pearlman W A.A new,fast,and efficient imagecodec based on se t partitioning in hierarchical trees[J].I EEE T ransactio ns on Circuits and Sy stems for V ideoTechnology,1996,6(3):243.[4]　Servetto S D,Ramchandran K.Image co ding based o n amorpholog ical representation of wavelet data[J].IEEETr ans Image P ro cessing,1999,8(9):1161.[5]　毛立强.嵌入式零树小波编码算法研究[J].微机发展,2004,14(7):109.[6]　娄莉.基于零树小波编码的改进算法研究[J].电讯技术,2004(5):73.[7]　闰肃,解成俊,杨钦,等.阈值走势及小波变换尺度对SPIHT编码性能影响的研究[J].北华大学学报:自然科学版,2005,6(5):469.530四川大学学报(自然科学版)第44卷。