（电路与系统专业论文）整数小波变换快速算法及图像实时无损压缩系统设计[电路与系统专业优秀论文].pdf

摘要 压缩机制引入数字图像实时传输系统可以极大地降低传输带 宽，缓解大数据量高速传输的系统负担。整数小波变换作为数字图 像压缩重要手段已经广泛应用于各种通用或专业图像非实时压缩领 域。但是，传统整数小波变换需要在编码前对象素做两个方向的处 理，无法消除象素编码前的盲等状态，难以达到实时传输的速度要 求。本文通过对整数小波变换统计特性以及区域压缩特性的研究， 发现整数小波变换通过聚类的方式将图像分解成高低频区域，高频 部分编码输出后，平均码长将会有显著缩短，但是该区域下一级变 换后压缩效果不显著，而低频部分虽然编码长度下降不明显，却对 下一级变换依旧存在较高的压缩潜力。因此特点，本文提出快速小 波变换算法，将计算集中于高效率的低频区域，高频部分只需经过 一次运算操作，得到的高频数值不带入下一级运算。这样，消除了 象素在第两个方向变换过程中的编码盲等状态，使并行操作和数据 流编码成为可能，极大地提高了算法的处理速度。进一步的，本文 结合无损熵编码的理论，设计了半自适应的编码方法以配合快速小 波变换后的并行处理。半自适应编码方法大大简化了码表生成的步 骤，可以得到和静态编码相当的压缩率，却在速度上和实现结构上 体现出极大的优势。“快速变换一半自适应编码”系统比传统整数小 波变换压缩系统理论上速度提高7 0 左右，可达到3 m b s 以上，在 数字图像实时无损压缩领域发挥突出的作用。 关键字：整数小波变换；快速算法；压缩效率；半自适应编码 中国科学技术大学 a b s t r a c t c o m p r e s s i o no f r e a lt i m ei m a g et r a n s m i s s i o nc a ng r e a t l yd e c r e a s et h e b a n d w i d t h h o w e v e r , i n t e g e rw a v e l e tt r a n s f o r m ( 1 w t ) n e e d sa l l t h e p i x e l st o d o2d i r e c t i o n s c a l c u l a t i o nb e f o r ec o d i n g t h ep i x e l sw i l l a l w a y se x i tw a s t ew a i t i n gt i m e s ot h es p e e do fo r i g i n a li w tm e t h o d d o e s n ts u i tf o rr e a lt i m ei m a g ec o m p r e s s i o n t h ea u t h o rd i dr e s e a r c h i n s t a t i s t i c sc h a r a c t e r i s t i ca n da r e ac o m p r e s s i o nc h a r a c t e r i s t i co fi w t a n df o u n d ：i w ts e p a r a t e st h ei m a g ep i x e l st oh i i g hf r e q u e n c ya r e a ( h a r e a ) a n dl o wf r e q u e n c ya r e a ( la r e a ) ：a f t e rc o d i n gha r e a ，t h e a v e r a g ec o d el e n g t hc a n b ed e c r e a s e dal o t ，b u tt h en e x tl e v e lt r a n s f o r m o ft h i sa r e ac a nb r i n gl i t t l ea f f e c t h o w e v e r , la r e a sc o d ei sj u s tt h e o p p o s i t e a c c o r d i n gt ot h i s ，t h ea u t h o rm e n t i o n e df a s ti w t ( f i w t ) m e t h o d ，w h i c hf i x e st h eo p e r a t i o no nh i g he f f i c i e n c ya r e a t oo m i tt h e , w a s t ew a i t i n gt i m eo fp i x e l s ，ha r e ao n l yn e e d st ob eo p e r a t e do n c e ，s o t h es p e e dr e a c h e sr e a lt i m e sr e q u e s t b a s e do nt h i s ，t h ea u t h o rg a v ea h a l fa u t oa d a p t e d ( h a a ) c o d i n ga l g o r i t h mt of i tf o rf i w tt od o p a r a l l e lw o r k so np i x e l s i tg r e a t l yp r e d i g e s t st h ec r e a t i o no fp i x e l c o d e f o r mw i t ht h es i m i l a rc o m p r e s s i n gr a t eo fs t a t i ca l g o r i t h m b u tt h es p e e d o fh a af i t sf o r h i g hs p e e da p p l i c a t i o n m u c hm o r e a f t e ra l l 。 “f i w t - h a a ”s y s t e mc a nl i f tt h es p e e do fd i g i t a li m a g ec o m p r e s s i o n t w i c ea n d h a sg r e a tu s a g ei ni m a g el i v e l yl o s s l e s sc o m p r e s s i o n k e y w o r d s ：i w t ；f i w t ；c o m p r e s s i n ge f f i c i e n c y ； l a 2 中国科学技术大学 1 1 数字图像压缩简介 第一章引言 社会的信息化进程带动了数字技术的高速发展，使得图像、声音等信息变得 易于保存和传输。随着日常生活中对于信息质量要求的增加，信息源的编码量 也随之呈现级数增长，造成保存介质容量需求的增大和传输成本的提升。数字 图像作为视觉信息的最重要载体，其数据载体容量和传输带宽消耗的增加尤为 显著，因此图像数据的压缩一直都是该领域科研的一个重要课题。上世纪7 0 年 代，研究者将文本压缩的基本理论发展到数字图像领域提出了包括字典编码、 游程编码等比较直观的压缩手段。到了上世纪9 0 年代，数字图像压缩技术迎来 了飞速发展的阶段。在这个时期，滤、预测、去相关等手段都得到了深入研究， 在这些研究的基础上，诞生了以j p e g 系列和。m p e g 系列为代表的图像压缩标准。 而随着人们对压缩保真度要求的提高，图像的无损压缩研究也进入了一个黄金 时期。1 9 9 7 年诞生的j p e gl s 协议和之后的j p e g 2 0 0 0 协议都是针对无损压缩 的。 1 2 整数小波变换的诞生 二维离散小波变换技术被引入图像处理领域使得图像压缩的可控制性和可 分析性得到了质的飞跃，但是由于其数值计算落在浮点数空间，在软硬件实现 上不可避免的会出现量化误差。对于某些特殊的应用领域，比如医学图像、地 理图像等而言，产生误差是会影响到后端的图像分析的。1 9 9 4 年s w e l d e n s 提 出了基于分裂预测更新的第二代小波变换理论，使得小波变换可以完全在整数 域中进行计算，避免了预处理时的量化误差。s w e l d e n s 在论文中提到：“提升 ( 1 i f t i n g ) 的方法可以将小波变换完全定义在整数到整数的区间当中；可以有效 提高设备的压缩速度；可以采用类似快速傅立叶变换( f f t ) 的计算结构来简化 小波变化的流程：并且易于采用非线形的滤波结构和多尺度的滤波函数。” 其后两三年，在此基础上发展起来的整数小波变换理论( 1 w t ) 在图像处理 中国科学技术大学 尤其是无损压缩领域的应用被广泛研究。d e w i t t e 采用单提升( s i n g l e l i 衔n 曲和双 提升( d o u b l e 一1 m i n g ) 的方法【2 】比预测编码( p r e d i c t o r ) ) 1h a a r 小波的无损压缩比 提高了1 0 。d a v i d bh 提出- 进制系数整数小波变换口j ，避免乘法运算，大大 减少了处理的计算量，并为硬件实现变换系统提供理论基础。 此后相当多的研究者将整数小波变换移植到了f p g a 4 , 5 或者d s p 6 ，7 1 系统 以及为无损压缩开发的专用芯片，1 0 】。使得整数小波变换在航空、遥感、医学 等图像处理领域得到了广泛的应用 1 1 , 1 2 , 1 3 1 。 1 3 实时压缩的需要 随着远距离信息共享和实时信息处理应用的深入发展，数字图像压缩技术 除了关心压缩比、信噪比之外压缩速度、压缩效率也成为关注的焦点。图像压 缩算法的处理速度将赢接影响到这一技术能否应用于实时的传输系统以减轻传 输带宽的压力。i ：u r r i z a 等人设计的专用于医学图像无损压缩的硬件系统【1 4 】已经 可以达到l m b s 以上的处理速度，但距离实时处理的要求还有一定差距。以每 秒3 0 帧采样，2 5 6 2 5 6 灰度图像为例，实时处理需要达到2 m b s 以上的处理 速度。可见，实时无损压缩需要进一步提高压缩算法的速度。 1 4 本论文的结构 本文的研究是针对数字图像无损实时压缩的。第3 章首先定量分析了整数 小波变换的特征参数，进而定性得到其变换的基本特点。在此基础上，第4 章 利用小波变换单一方向上的独立性与平行性【1 1 提出了整数小波变换快速算法。 在变换完成后，第5 章比较了几种无损熵编码方法的速度和效率，设计了效率 更高，速度更快的半自适应算术编码方法。最后在第6 章提出了“快速算法一 半自适应编码”的数字图像实时无损压缩系统。 中国科学技术大学 2 1 压缩 第二章图像压缩基本理论 数字图像根据源图像和恢复图像的误差可以分为有损压缩( 1 0 s s y c o m p r e s s i o n ) 和无损压缩( 1 0 s s l e s sc o m p r e s s i o n ) 。 2 1 1 有损压缩 有损压缩是指经过压缩后的图像解压后与原图像相比，存在一定程度的失 真，即丢失了部分信息数据量【l5 1 。有损压缩的主要手段是预测和变换： 1 ) 预测的基本思路是根据某一模型，利用前趋的数据样本进行预测，减少 图像数据在时间和空间熵的相关性，以达到压缩图像数据的目的； 2 ) 变换的基本原理是将空间域上原来相关性高的图像数据通过某种数学变 换，映射到新的域上进行描述。 在预处理的基础上，有损压缩编码方法再根据新的图像象素描述方式的数 学特点进行有针对性的编码，以达到去除数据信息描述冗余量的最终目的。 在编码阶段，由于有损压缩可以忽略部分细节象素信息造成的图像象素奇 异点，因此编码时候的匹配模型可以尽量做到适合于简单数学公式描述，或者 采用逐次逼近的方法，将特殊细节点的信息数据只做区间分配而不采取具体计 数的方法，从而使有损压缩的压缩比达到4 0 ：1 或者更高而依然可以被人眼识 别。有损压缩的目标就是在做到视觉无损或近无损的情况下达到最高的压缩比。 基于d c t 变换的j p e g 方法、e z w 零树小波编码、s p i t h 算法等都是典型的 有损压缩方法。由于其高压缩比和低视觉失真，有损压缩已经广泛应用于数字 媒体的各个领域。 2 1 2 无损压缩 无损图像压缩是指解压后的图像与原来图像完全相同，没有任何信息的损 失。 早期的无损压缩方法产生自文本压缩方法，较为典型的有：字典编码，概 中国科学技术大学 率统计编码等等。 随着s w e l d e n s 提出了基于整数域的第二代小波变换理论之后，原先使用在 有损编码领域的预测变换方法也被引入到图像无损压缩的领域。 在整数小波变换理论成熟之前，对于图像所做的二维变换都是在浮点数域 的。因此在计算过程中，由于软硬件存储位数的限制，必然会存在计算值的存 储误差，恢复后的图像或多或少都存在一定程度的失真。而整数小波变换则使 得初始象素值、计算中间值、映射象素值都成为定长的整数，从而有效的避免 了变换过程中的存储误差。在这种去除相关性的变换基础上，再实施无损的熵 编码，诸如h u f f m a n 编码、算术编码、就比单纯的采用此类无损熵编码更能够 获得高压缩比。 由于无损压缩要求恢复图像和原始图像完全的匹配，象素中的细节都必须 完整无缺的在新的描述空问中得到体现，因此无损压缩可以去除的信息冗余量 比有损压缩小得多，一般只能达到2 ：1 5 ：l 的压缩比【i ”。在某些特殊的应用领 域，比如医学图像、地理图像等，细节特征是不可以被忽略的，压缩的无损性 就成为一个迫切的要求。“如美国政府已颁布法律规定，在医疗处理中不再使用 有损压缩，因为由于图像的不清晰而导致的医生误诊已经带来很多社会问题， 而且医疗成像设备如c t ，m r i 等价格极其昂贵，图像的获取代价高昂，因此这 些图像最好采取无损压缩。”旧 目前无损压缩的最主要方法便是在没有量化误差的预处理基础上，采用绝 对无损的熵编码。 2 2 整数小波变换 二维小波变换在图像分析领域有着非常广泛的应用，1 9 8 8 年m a l l a t 将此前 的所有正交小波基的构造法统一起来，给出了正交小波的构造方法以及正交小 波变换的快速算法。s w e l d e n 又在此基础上将m a l l a t 整理的离散小波变换方法 应用到整数域，形成了整数小波变换的基本理论。 2 2 1 离散小波变换 19 8 8 年，m a l l a t 提出了多分辨率分析( m u l t i r e s o l u t i o n a n a l y s i s ) 的概念， 运用线性空问形象的说明了小波的多分辨率分析特性，并给出了正交小波变换 中国科学技术大学 的快速算法，即m a l l a t 算法： m a r 由满足如下条件的嵌套线。n 空- f n c e c v o 匕kc 组成 嵌套空间的并集在平方可积函数空间中稠密 嵌套空间的交集只包含零向量 如果f ( t ) c k ，那么f ( 2 t ) c 圪反之亦然 存在函数( 即尺度函数) 曲御使得，砂( t - k ) ：k i n t e g e r ) 是的基，而庐例被定义为 满足下列条件的函数： 1 ) f 。( k ( t ) d t = 1 2 ) ) | | 2 = f j t ) 1 2 d t = 1 3 ) = a ( n ) ( 2 1 ) ( 2 2 ) ( 2 3 ) 则存在c ( 竹) ，n = o ，- + 1 ，2 ，使得庐( 2 “f ) = c ( n ) 0 ( 2 - ( k - 1 ) t - n ) ，说明 圪c k _ 1 ，即构成了一个m r a 。形象的说，所有子空间的并集( k 。) 在r ( r ) 中 稠密，说明k 。能够逼近任意信号( f ) r ( r ) 。若令五( f ) 为厂( f ) 在予空间k 上 的f 交投影，有五( f ) = a ( k ，n 渺( 2 “卜n ) ，k = o ，l ，2 。进一步可以得到 a ( k ，n ) = a ( k功z ) 掣。 假设少( f ) 是k r i 白q 函数，且满足 1 ) tv ( t ) 衍= 0 2 1 f j ( t ) 1 2 以= 1 3 ) = a ( n ) 4 ) = 0 ( 2 4 ) ( 2 - 5 ) ( 2 - 6 ) ( 2 7 ) 中国科学技术大学 则俐就是与上述m r a 对应的d w t 需要的小波。令是以，矿r f 一脚? n i n t e g e r 为基的线性向量空间则k 一，= o 哆，那么吃= o ，于是 j = k j = 。 正。( ，) = 6 ( ，z ) ( 2 “卜m 同样，可以导出6 ( t 一) = 萎n ( k - 1 , m ) 旦竺；型。 a ( k ， ) = a ( k 一1 ，m ) h ( 2 n m ) b ( k ，n ) = a ( k 一1 ，m ) g ( 2 n m ) ( 2 - 8 ) ( 2 9 ) 这可以看作以阮圳、6 r 疋一是由矗限，圳经过滤波器h ( n ) 滤波后抽样得到的。 f _ i _ 。j 、彳i 飞臣瓣z 曩i i 霸 a ( k _ lz j ) j _ ，；、h ( 罐搿。：a蠢i j 翁贰! ，! ) i 爹i 一l i i 薹i 反麓露 a r k n ) ，+ ! 醺i 兰。蔓_ 、遵爹7、蓦y 隧；| | | 鲴a ( k - l , n ) 曩j i 、辱j i 墨曩嚣翮 吣4 ，瀚，縻鬻i 辫晰) v “t “j | ，k 。v ”_ ! i ”、1 1 1 7 鼍72 掣2 鼍 。 综合滤波器 图2 - 1 一维小波变换 如果从频率域考虑，令日( ) = ( 咖”“，则有j 圩( 口) 1 2 + 1 日+ 石) 1 2 = l 也就是说h 是一个正交镜像滤波器( q m f ) 。通过多分辨率分析，可以将小波 的求解转化为对数字滤波器的设计问题。 目前广泛应用的二维小波变换都是基于二维可分的情况，计算二维离散小 波变换的过程可以分解为两步，首先进行按行的一维小波变换，然后再按列进 行小波变换。 聆一 g = g 一厅 = 盟： = g 盟： 1 1 令故 则 鼷一 蓊一 蜃巨分 堡燮堂 行 输入图像 j 曩i 。r 烈，1 譬i _ _ 艮 ，j 一i 习列； 雹塑薹惹翌鏊笋伊 i 一。= 尊通擎攀抽学j 剥 ! l 型 。愿蘩蘩羚阻 愿蚕 i ；罩孽曩i 暑翮“ 箧錾鐾鬻麟眵一睦j 兰。二羔童；三羔鎏堑茎f 匿焉霹季琴焉曩墨1k 遴憋鞫秒。隧羹i 鎏塞：曼萋f 2 图2 - 2 图像的二维分解示意图 二维离散小波变换系数的递推公式为： 略。莩莩。孑1 吮- 2 i , l - 2 ：莩瑰一莩a 孑1 岛哪 q m 一, d 2 莩莩7 l g 曼z 哪2 莩酿”莩口g i _ z 其中，d = 1 ，2 ，3 ，1 2 = d 是d 的二进制编码 ( 2 - 1 0 ) ( 2 1 1 ) 2 2 2 整毅小坡变换 1 9 9 4 年s w e l d e n s 提出了基于提升方法的第二代小波变换理论，即整数小 波变换，整数小波变换可以分为分裂、预测、更新三个步骤1 1 。 ( 1 ) 分裂 此过程是将信号一分裂成为互相不相交的子集0 一和d 。，最简单的做法是 将一个数列按奇偶序数进行分裂，即： 妒f ，( ) = ( e v e n j o d 扎) = ( s jit 一，)( 2 1 2 ) ( 2 ) 预测 针对数据间的相关性，可用s ji 去预测哆故可采用一个与数据集结构无 关的预测算子只使得哆一；2 p ( s ji ) ，这样就可以用新的数据子集- i 代替原始 的数据集s ，。若用子集嘭与预测值p ( s 川) 的差值去代替d 。，则此差值反映 了两者的逼近程度。如果预_ ；! 贝是合理的，则差值数据集所包含的信息比原始子 鬯 中国科学技术大学 集哆，包含的信息要少得多。最简单的p ( _ 一) 是去两个相邻的子集点的平均。 这样预测的过程可以表示为： p ( 5 h ) 2 ( 女+ s j , s k + 2 ) 2 ( 2 - 1 3 ) d j = s j , 2 k + l - p ( s ji ) ( 3 ) 更新 经过以上两个步骤产生得系数子集s 。的某些整体性质并不和原始数据中 的性质一致，因此需要采用更新过程。其目的是通过算子u 产生一个更好的子 数据集0 一使之保持原数据集0 的一些特性。最简单的算子u 是取预测后相 邻的两个d 之间的差，即下式： s j - l , t = t + ( 哆 + 哆“n ) ( 2 1 4 ) 对于数据子集j i 。( 其中l q 表示第n 阶的变换) 进行反复的分裂预测和更新， 就可以将图像数据分解成为各级的高频和低频分量，其中s ? 是低频分量，彬是 高频分量。 式1 1 5 给出了整数小波变换的通用公式，其中s 表示低频分量，d 表示 高频分量： 粥厂s j 引r s j 川 s 川= s 川+ 彰? ，2 ( 2 1 5 ) d j ，= d + 口】( s j 。h s j 一】) + g o ( 邑吐，_ l s j ，) + ( s j l l ，一s j ) 一 ，f l l l 。h j ( 一i ) 1 ，+ l 重构的公式如下： s ji = s j1 一u ( d j 】) d j i = d j 一1 + p ( s 。) ( 2 1 6 ) s j2m e r g e ( s j l ，d j 一1 ) s w e l d e n s 已经证明在提升的基础上可以进行整数集到整数集的小波变换， 也就是说，一个整数集合通过小波变换得到的仍然是整数集合。其中最简单的 整数小波变换是s 变换。它是h a a r 变换的整数形式： 中国科学技术大学 典型的整数小波变换公式( 行方向) 如下： ( 1 ) a ( 2 ，2 ) 变换 一，j = x i 1 一 1 2 ( x 啦t ，+ t ，+ 2 ) + 1 2 s 。= 。啦_ + 【l 4 ( 西，j l + d u ) + 1 2 1 ( 2 ) a ( 4 ，2 ) 变换 吐，j = x 啦。+ l 一 9 1 6 ( x 啦+ j + x j 2 + ，+ 【) 一! 1 6 ( x i ，2 t j + 2 + 葺2 十4 ) + 1 2 1 s u = 。啦。+ 1 4 ( d u 、+ z ，j ) + 1 2 1 ( 3 ) a ( 2 ，4 ) 变换 d i ，j = 一 2 - 】一 1 2 ( x 嵋q - x i f ，+ 2 ) + 1 2 s u = 一2 + 1 9 6 4 ( d , 卜1 + 一，j ) 一3 6 4 ( 4 _ 2 + 一j 一1 ) + 1 2 ( 4 ) a ( 6 ，2 ) 变换 d l ，= x i , 2 。j + i 一 7 5 1 2 8 ( ，2 u + t j + 2 ) 一2 5 2 5 6 ( x i j 一2 + t j + 4 ) + 3 2 5 6 ( x ，。2 + ，一4 + 一，2 + 6 ) + 1 2 s u = t ，2 + j + 1 4 ( d j ，一i + d j ) + 1 2 ( 5 ) a ( 2 + 2 ，2 ) 燹抉 = x i 川7 - 1 2 ( x 。+ x 啦”2 ) + 1 1 2 t 。= x 啦_ + 【1 4 ( d i 一】+ d i ) + 1 2 1 d i 。j = 威一i 一 1 1 6 ( s 。+ s j j s j , j + 、一s s , j + 2 ) + i 2 1 ( 6 ) s ( 1 1 ) 变换 d i ，j2x i , 2 * j + 1 一x i , 2 lf s j = x ? pj + 、 2 d i f ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) ( 2 2 1 ) ( 2 - 2 2 ) ( 2 2 3 ) ( 7 ) s + p 变换 j = _ ，+ l 一一j s ，= x ，2 ，+ 1 2 d 7 , ， ( 2 2 4 ) 珥，j = j 十【2 8 ( s ul s i , j ) + 3 8 ( i ，一s i , j + 1 ) + 2 8 d i + 1 2 2 2 3 整数小波变换的运算流程结构 整数小波变换的运算首先将输入信号按一一定的规则分裂为两部分，通常的 分裂规则为奇偶分裂，然后使用提升因子p ，反复交替提升分裂基，最后对 2 j汜 刁 勘 + 州 0 = | | 啦 中国科学技术大学 分解出来的高频因子和低频因子作归一化处理，统一尺度。具体的象素操作流 程如下： y 一暖习愿 d ( 0 ) ，i 奄 。- ”zr q m ：卜? i _ 一 | i ) 图2 - 3 整数小波变换分解结构 2 2 4 整数小波变换用于图像压缩 二维整数小波变换可以应用在图像分析和图像数据压缩领域，和二维离散 小波变换类似，经过二维整数小波变换处理后的图像被分解成为若干个高低频 区域，下图是经过l e v e l 2 二维整数小波变换之后的图像象素聚合空间： 图2 4 整数小波变换区域分解图 不同区域的象素之间的空间相关性经过整数小波变换已经充分减小，在此 基础上对图像象素进行分快编码就可以达到压缩的目的。 例，对8 位2 5 6 2 5 6 象素的标准测试图像l e n n a 作l e v e l 2 的二维整数小 波变换： 溺 中国科学技术大学 图2 - 5i ，e n n a 滤波函数采用s ( 1 ，1 ) 小波，变换公式如下： 区间 l l ll l hl i - i ll h hl hh lh h ， 码长 7 3 54 8 94 1 l4 4 14 4 93 7 84 0 6 表2 - 1 各区间平均码长 在对图像进行二维整数小波变换后，像素位会出现负数，利用一个和分块 区域大小相同的子矩阵来存放每一个像素的符号位，这样在非l l l 区域，每一 分区都需要增加x y 的数据量( 相当对平均码长+ 1 ) 。由此，计算出采用l e v e l 2 的整数小波变换后进行编码的图像平均码长为5 3 2 ，而直接采用h u f f m a n 编码 的l e n n a 图像平均码长为7 4 7 。司见经过整数小波变换后的图像有着更高的压 缩效果。 针对同一副图像l e n n a ，整数小波变换方法同w l n r a r 和w i n z i p 两个传统 文本压缩方 整数小波变换 6 6 5 w i n r a r7 0 8 w l n z i p 8 7 7 表2 2 与经典压缩方法的比较 经过l e v e l 2 的整数小波变换后的图像压缩率要高于直接的文本压缩。如果 ， 吐 1 h + 州 即一t = | | d i 中国科学技术大学 应用的背景是允许一定程度图像失真的低精度场合，压缩比还可以达到更高的 数量级。j p e g 标准在视觉可认知的前提下数字图像的压缩比可达数十比一。但 压缩是有损的，故不赘述。可见，整数小波变换无论在数字图像有损压缩还是 在无损压缩领域都有着其不可替代的应用价值。 中国科学技术大学 第三章整数小波变换数值分析 3 1 各整数小波函数压缩性能比较 选择标准测试图像b a g u e s 做z2 2 节列举的七种整数小波变换，然后采用 h u f f m a n 方法进行编码，统计它的压缩效果 图3 一lb a g u e s 统计所得结果如下，其中参数c o m r a t e l 表示做列方向变换后的平均码字长， c o m r a t e 2 表示做了行列变换后的压缩效果，e n l 和e n 2 分别是两次变换后的信 息熵也就是最大压缩码长。l l ，l h ，h l ，h h 分别是各子区间的平均编码长度。( 图 像原来的单位像素码氏为8 ，用平均码长就可以表示出压缩效果) 变换h h 数 c o m r a t e l ：e n l c 0 i n r a t e 2e n 21 ll h h 1 3 5 7 a ( 2 ，2 ) 4 6 64 6 24 1 84 1 65 1 43 7 54 2 7 2 6 6 a ( 4 ，2 ) 4 5 64 5 33 9 83 9 45 2 33 7 54 0 8 3 9 2 a ( 6 ，2 ) 4 7 44 7 84 5 54 5 15 4 34 2 44 6 0 3 5 8 a ( 2 ，4 ) 4 6 l4 6 54 1 64 1 35 0 73 8 04 3 9 3 9 1 a ( 2 + 2 ，2 ) 4 8 14 7 84 4 84 4 45 1 34 - 2 44 6 5 3 9 6 s ( 1 ，1 ) 4 ，8 04 7 64 3 94 3 65 2 63 9 34 4 3 中国科学救术大学 表0 一lb a g u e s 压缩效果分析 觚上表哥隧看穗，屁穆不嗣熬整数小波交换在效莱上的麓蓬并不大。对于b a g u e s 图来说，a ( 6 ，2 ) 小波所纳入计算的相关点数要多于a ( 4 ，2 ) ，但是效聚不见得一 定比a ( 4 ，2 ) 好。s + p 因为要保留的边界比技厚，所以熬体压缩的效果并不理想。 s ( 1 ，1 ) 篷效暴处予中游，爨建诗雾麓蕈，棼誊逶台硬箨癸蕊。 3 2 特征参数提取与分擀 文献“”和文献。”对整数小波变换后数字图像的像素点做了统计分析。两篇 论文都统计了熬数小波变换前后各级予区闽的能量分密，零系数的比列以及系 敷翡均僮、方麓、单位疆静互稿关蓬，褥列了蔽下结涂： ( 1 ) 小波变换后的图像能蹩主要集中在低频系数区域。 ( 2 ) 高频区域的系数平均值接近于零。 ( 3 ) 图缳豹压缩懿效莱稻零系数静跪铡成正魄，篷麓楚零系数麓多，筮缩率 越大。 对于以上两篇论文的结论本文的解读为：高频系数作为象素预测产生的值， 囊然会落东运零送蠛，平均系数必然接近零。瑟低频系数律舞提秀嚣又蔓赣遗 的值，虽然和原象素对应点数值上会有一些差别，但怒必然接近原象素值，故 瑚原象素的能凝集中在低频区间，可以说越是低频的区域，象素值能量越高。 零系鼗魏毙铡抟璐了曩、波交换对子裹鞠关涎象素去穗必惹戆聚类效聚。零系数 比例越高，说明图像象紊聚类的效果越好，编码后的平均码长越小。 为了进步探询图像经过小波变换后统计特性对于图像压缩的影响，本文 选取旗蠡攘潮试图豫，分剿采集它们在变换翦，交软中，交换嚣瓣数学统计 参数。统计参数选取：平均像素值( e ) ，像索均方差( m s e ) ，像素绝对整( m a d ) ， 避零系数比例( z e r ) ，信息熵( e n ) 和一阶相关系数( r ) 。近零系数指图像区域 中数摆绝对傻低于2 豹象索点。此岁 ，m s e ，m a d 和r 戆诗算公式懿下： m s e = 晰，) 一e 2 ( 3 1 ) i = 1 j l hm i m a d = x ( ，) 一x ( i ，歹+ 1 ) ，( 掰4 ) ( 3 2 ) 中国科学技术大学 r ( 1 ，0 ) r ( 0 ，1 ) = i ( 誓，一e ) ( x 。，一e ) l ( x i , j - - e ) 2 i ( x 。一e ) ( 一，+ 。- e ) l ( _ ，- e ) 2 滤波函数选取的是s ( 11 ) 小波，变换公式如下： c l i j2 蕾，2 ，+ l 一一，2 + ， 矗，= x ，2 + + 1 2 d , ( 3 3 ) ( 3 4 ) 固，_ _薯囊圈_ 洲啊 b a g u e s 4 7 0 54 6 8 1 j 47 6 9o 4 55 0 2 0 9 5 2 8 4 0 9 5 3 2 3 p e p p e r s 1 2 0 1 52 8 8 27 9 2 r 时，将重复前面的过程；若n 一( r - 1 ) s = r 时，结束编码； 4 ) 从结束处沿授编码符号的路线向前返回，依次写出字符对应的码符 号序列，这就是h u f f m a n 编码； 5 ) 若n ( r - 1 ) s r 时，这种情况表明，合并了s 次后，信源缩减的符号 个数已经小于码符号集肖： 爿，z 。，墨) 的符号个数了，为了使短 码得到充分利用，在原信源a 中增加m = r i n - ( r 一1 ) s 个概率为o 的 虚信源符号，重新按( 1 ) 的步骤起进行编码。 h u f f m a n 编码的码字结构实际上是树型数据结构，所有的信源符号都分配 一个叶子节点，根到叶子的路径就是该节点所对应的信源符号的编码。应用最 广泛的是二进制h u f f m a l 编码，其拓扑结构是一棵二叉树。如下图： 兰 8 ，1 4 西。 、 4 ， 州2 1 1 4 掣1 4 少 0 0 响 0 b 们 i 1 9 1 1 s 7馥 剥娅 仰 1 姒 国3 。 图5 1h u f f n a n 二叉树 h u f f m a n 编码需要扫描两次信源样本。第一次扫描统计原始信源中各符号 中国科学技术大学 的统计概率，进而建立h u f f m a n 树；第二次则是根据已经形成的h u f f m a n 编码 表对各个信息字进行编码。h u f l m a n 编码的码表生成速度不快，但是结构简单 清晰，并且编码效率很高吲。 ：_o。5l-1么o。3。5-_11；：o。30。6。2，5。-_j7i一、。0。，3。0。6。2。5j11d。，io：,。3。03，t。18。5。-11i 中国科学技术大学 5 2 位分裂与码表生成 5 2 1 固定编码匹配 对于一组拍摄图像，因为不同时段图像的差异，不可能用固定的编码方案 来进行压缩，如下述两图，为一次胃镜中两个不同时间采样到的灰度图： 图5 - 3m e d l b m p图5 4 m e d 2 b m p 对两副原始图像做象素统计，结果如下表： m e d l前五象素1 6 41 5 31 5 61 5 41 5 2 编码长度 统计比例1 6 3 4 2 1 5 8 2 3 1 5 5 9 4 1 5 0 1 5 1 4 2 2 l 6 8 4 m e d 2前五象素9 49 59 29 39 0编码长度 统计比例1 6 5 5 6 1 6 4 0 3 1 6 2 0 5 1 6 0 0 6 l ，5 7 4 7 6 8 3 表5 - 1 同源异时胃溃疡图像象素统计比较表 图5 - 5m e d1 b m p 灰度分布 图5 - 6m e d 2 b m p 灰度分布 两图直接做h u f f m a n 编码后的平均码长相当。但是，两副图像中具体象素 的分布特点却大相径庭。对于m e d l 而言，象素聚合度最高的5 个都在1 5 0 - - 1 6 0 中国利学技术大学 段，而m e d 2 同样的象素值却落在9 0 1 0 0 段。可见，如果用根据m e d l 生成 的码表去给m e d 2 编码，编码的压缩效果将非常不理想。 在经过小波变换之后，象素经过聚类，集中体现边界特征的高频部分象素 有一个共同的特点，就是近0 象素密度大。是否可以用统一的码表对所有不同 时段图像的高频区域进行编码昵? 下两表l 恢集了经过快速小波变换后m e d l 和 m e d 2 的高频区域的象素统计分布 m e d l 前五象素 l o23 4 编码长度 h 区域统计比例3 4 7 5 0 2 9 2 5 1 1 7 5 0 5 8 2 9 4 7 3 7 1 7 0 2 5 1 m e d 2 前五象素 ol234 编码长度 h 区域 统计比例6 2 7 9 3 1 7 6 9 7 9 2 4 9 9 4 8 8 2 8 2 4 5 6 7 1 7 9 表5 2 同源异时胃溃疡图像h 区域象素前五统计比较 m e d l 后五象素 4 7 5 0 5 3 5 8 6 4 编码长度 h 区域 统计比例00 0 3 1 0 0 0 3 l 0 0 0 3 1 0 0 0 3 1 0 0 0 3 1 2 5 l m e d 2后五象素 1 21 3 1 41 62 3编码长度 h 区域 统计比例00 1 5 3 0 0 1 2 2 0 0 0 9 2 0 0 0 6 1 0 ：0 0 3 l 1 7 9 表5 3 同源异时胃溃疡图像h 区域象素后五统计比较 可以发现高频区域高密度象素值的分布大体相当，都集中在0 附近。可是， 低密度象素的分布却表现出很大的差异。这在编码过程中会造成，中低密度码 表生成出现很大的区别，如果用种统一的码表来给不同时段高频部分编码， 会造成编码效率低下。虽然高频部分编码效率的下降相较于低频部分来说，要 小一些，但是也足以影响压缩比数值。大约会使编码平均长度增加1 ，2 个b i t 。 这也是压缩系统无法忍受的。 由此可见，要提高对于图像组的压缩效果，必须使码表有一种实时的适应 性。那么，最直观的想法就是每次都生成一组针对该帧图像的匹配码表。 5 2 2h u f f m a n 编码生成时问 以h u f f m a n 编码为例，分析生成一个2 5 6 象素空间的h u f f m a n 码表需要多 少时间： h u f f m a n 码表生成的主要思想就是按照信源符号的统计概率排序，将概率 最低的两个合并，作为层次最深的叶子；然后，将新概率分布的信源字符排序， 合并此时的最低概率两字符；直到合并完所有信源符号为止。因此，h u f f m a n 中围科学披术大学 编码的生成过程中，占到主导地位的就是排序的处理。 以典型的冒泡排序法为例。首先2 5 6 2 5 6 的图像要统计出各象素的出现概 率，需要遍历一次图像。由4 3 2 节可知，计数加减1 的时间量化值为l 。那么 遍历一次获得象紊统计分布需要2 5 6 2 5 6 1 = 6 5 5 3 6 单位量化时间。 然后，n 个信源符号需要排序得到概率最低的两个符号。长度为n 的序列 排序的算法复杂度为n ( n 一1 ) 2 ，在每个循环单元中，如果前后两元素顺序不符合 要求，则交换它们的位置。比较( c m p ) 的量化时间为1 ，交换( x c h ) 的量 化时间为3 。在排序的过程中，不会出现每个循环单元都需要交换的情况。为 此，取一个比较符合通常情况的中间值，交换的情况取其中的1 3 ，得到完成长 度为n 序列的排序计算量化时间为：f ( n ) - n ( n 1 ) 。 完成一次排序后，信源的符号数变成n 一1 ，此时需要多这n 一1 个信源符 号进行新的排序，以确定次深度的两个节点。完成这欢计算需要的时间为f ( n 一1 ) 。 直到完成了f ( 3 ) ，h u f f m a n 树就生成了。此时的总量化时间可以表示为： h f ( n ) = y ：m ( m 1 ) ( 5 - - 2 ) m - 3 信源符号数为1 1 的空间，完成h u r i n a a 二叉树的量化时间由式4 2 给出。对于 2 5 6 级灰度图来说，这段量化h , i 问为5 5 9 2 3 1 8 单位量化时问。 生成h u f f m a n 树之后要得到码表，则续遍历h u f f m a n 树。假设经过每一根 树枝的量化时间为1 ，参考次读的时间，那么遍历叶子为2 5 6 片的h u f f m a n 树的量化时间为5 1 0 。 总的生成h u f f m a n 码表得时间为5 5 9 2 8 2 8 单位量化时间。 5 2 3 位分裂 由上节的分析可知，完成一张2 5 6 级的h u f f m a n 码表要消耗的时间远大于 完成一副2 5 6 2 5 68 位象素灰度图的整数小波变换，因此如果采用直接的方法 对每幅待处理的图像都生成一组完全针对的码表时间成本过高。本节讨论一种 减小h u f f m a n 码空问，降低h u f f m a n 二叉树深度的方法，即位分裂的方法【2 引。 8 位灰度的图像经过整数小波变换之后象素空间由原来的2 5 6 级拓展到 f 一2 5 5 ，2 5 5 1 5 1 1 级别，也就是需要9 b i t 的数据长度来存储。在第三章的分析中， 简化模型，将符号位另外保留，单独为后8 位象素编码，得出一组压缩参数加 上符号拓展的1 位，作为最终的压缩后编码长度。但是8 位象素的h u f f m a n 编 中田科举技术大学 码计算步骤过多，不适合高速系统。位分裂的方法就是将这9 位象素位分裂成 高5 位和低4 位分别进行编码。 高5 位b低4 位a ff 原始像索值9 位x 图57 位分裂操作 原始象素映射值x = b 4 十a 。对 0 ，1 5 和 o ，3 1 象素空间分别进行编码， h u f f m a n 码表生成的最大时间为 0 ，3 1 码表空间的生成。由式5 2 可知，生成 h u f f m a n 二叉树所需要的时间为1 0 9 1 0 单位量化时间。遍历3 2 片叶子的全二叉 树需要