（通信与信息系统专业论文）spiht算法的工程应用.pdf

摘要 在图像编码领域，更高性能的压缩算法一直是人们不懈追求的目标。一个图 像压缩系统的性能优劣，主要取决于以下几个指标： 1 ，压缩后图像的恢复质量，包括主观质量和客观质量； 2 ，比特率，表示原始图像的一个像素可以由几个压缩后的比特恢复，体现了编码 效率； 3 ，复杂度，一般以完成压缩算法所需要的运算量和存储单元数目来衡量。 本文埘图像编码理论进行了系统深入的研究，重点对s p i h t 编码算法进行了 细致的理论分析和算法研究。本文的主要创新性成果包括： 1 ，改进了无链表的s p i h t 算法，去掉了原来算法中用来存储系数和集合坐标的三 个链表。通过这种改进，提高了图像压缩的实时性； 2 ，采用了r s ( 2 5 5 ，2 4 3 ) 信道编码，并且利用图像压缩码流的特点，定义了一种适 合传输的数据流格式，提高了数据传输的准确性。 关键词：图像压缩s p | h t 算法小波变换r s 纠错码 a bs t r a c t i n i m a g ec o d i n gf i e l d ，e f f i c i e n c y i st h ep r i m ea i mo ft h er e s e a r c h e r s t h e p e r f o r m a n c eo fi m a g es y s t e m si sj u d g e di nt h ef o l l o w i n gp a r a m e t e r s ： 1 ，t h eq u a l i t yo ft h er e c o v e r e di m a g e ，i n c l u d i n go b j e c t i v ep a r a m e t e r sa n ds u b j e c t i v e p a r a m e t e r s ； 2 ，t h ec o m p r e s s i o nr a t e ，w h i c hi sr e p r e s e n t e db yt h en u m b e ro fb i t st h a tu s e dt or e s t o r e ap i x e lo ft h ei m a g e ； 3 ，t h ec o m p l e x i t y , w h i c hi sc a l c u l a t e db yt h ea m o u n to fc o m p u t a t i o na n dm e m o r i e si n t h ei m p l e m e n t a t i o no ft h ea l g o r i t h m i nt h i sp a p e r , t h es p i h ta l g o r i t h mi s c a r e f u l l ya n a l y z e df r o mp r i n c i p l e s t o a p p l i c a t i o n si ne n g i n e e r i n g t h eo r i g i n a lw o r kd o n ei nt h i sp a p e r i sa sf o l l o w s ： 1 ，t h i sp a p e rp r o p o s e da ni m p r o v e m e n tt ot h es p i h ta l g o r i t h mw i t h o u tl i s t s t h i s i m p r o v e m e n tc u to ft h et h r e el i s t sw h i c ha r eu s e dt os t o r et h ec o e f f i c i e n t sa n dt h e c o o r d i n a t e so fs e t si nt h ef o r m e ra l g o r i t h m w i t ht h i si m p r o v e m e n t ，t h ee f f i c i e n c y o fi m a g e c o m p r e s s i o nh a sb e e ni m p r o v e d 2 ，t h i sp a p e ra d o p t e dar sc h a n n e lc o d i n g f u r t h e rm o r e ，a c c o r d i n gt ot h ec h a r a c t e r so f t h ei m a g ec o m p r e s s i o nb i n a r yb i t ss t r e a m ，ad a t af o r m a ti sp r o p o s e dt oi m p r o v et h e r o b u s t n e s so ft h ei m a g et r a n s m i s s i o n k e y w o r d ：i m a g ec o m p r e s s i o n s p i h tw a v e l e tt r a n s f o r m sr s 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研究成果。尽 我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其它人已经发表 或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志所做的任何贡献均已在论文中做了明确的说明并表示了谢 意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读 学位期间论文工作的知 。f l 产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或 使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件， 允许查阅和借阅论文：学校可以公布论文的全部或部分内容，可以允许采用影印、缩印、或 其它复制手段保存论文。 本人签名： 导师签名 第一章绪论 第一章绪论 ，1 1 引言 物质，能量和信息是构成世界的三维。当今的世界更是信息爆炸的时代，尽 管随着通信技术的迅速发展，通信带宽呈级数增长，但在海量信息面前，信道的 通信容量总不能满足人们对速度的要求。数据压缩伴随着通信的发展，一直是人 们关注的蕈点。从信息论的角度来讲，数据压缩又称为“信源编码”。数据压缩是 把输入数据流转变成另一种较少的数据流的过程。数据压缩针对不同的数据类型， 使用针对性的方法，有不同的结果。但原理都是一样的，都是通过减少数据之问 的冗余以达到压缩的目的。 图像是信息的一种蕈要载体，它在现代通信技术中所承担的作用己远远超过 其它载体。有资料表明，人类通过视觉获取的信息量约占总信息量的8 0 ，图像 通信与其他通信方式相比，具有更好的直观性、确切性和生动性。对图像压缩的 研究是一项必要而且具有蕈要实际意义的工作。 从上世纪四十年代末开始，图像编码技术已走过了近半个世纪的发展历程。 许多思想和方法都相继提出。9 0 年代以后，国际上致力于标准化的工作，先后制 定了一系列静止和视频图像编码标准，不仅极大地推动了数据压缩技术的实用化、 产业化，同时也在一定意义上刺激了信源理论研究的进一步拓展，其部分标准如 表1 1 所示。进入2 1 世纪，计算机工业和信息产业的不断融合和迅速发展，为图 像通信的研究和应用不断提出新的要求和课题。新的图像业务如视频点播( v i d e o o nd e m a n d ，v o d ) 、可视电话及视频会议的需求增长越来越快，新的通信技术如 高速光纤网( f d d i ) 、宽带综合业务数字网( b i s d n ) 、a t m 技术层出不穷。伴 随着机遇和挑战，在经典压缩方法的基础上，新的算法也不断涌现出来，并在工 程实践中逐步得到应用。 2 s p i h t 算法的t 程应用 表1 1 静止图像编码国际建议和标准 标准名称( 时问) 应用领域特点 c c i t tt 4 三类传真机文件压缩采用一维m h 和二维m r 编码 ( 1 9 8 0 ，1 9 8 4 ，1 9 8 8 ) c c i t ft 6 ( 1 9 9 2 )四类传真机文件爪缩无噪声编码，采用m m r 编码 j p e gt 8 1 彩色或灰度静止图像压采用d c t 块变换、自适应量化、游长编码和 i s o1 0 9 1 8 ( 1 9 9 1 1 缩熵编码；基于d p c m 预测的无失真压缩 j b i gt 8 2 二值和灰度图像( 比特无失真压缩，多分辨率结构和自适应顶测， i s o11 5 4 4 ( 1 9 9 2 ) 面) 和传真文件压缩乐缩比高_ 丁t 4 和t 6 ：适应累进压缩 j p e g l s 连续色调静止图像无损复杂度低，能提供高无损压缩率。不提供支 i s o 14 4 9 5 i t u t 8 7 接近无损压缩标准持扩缩，误差恢复等功能 j p e g 2 0 0 0 彩色或灰度静止图像小波变换，e b c o t 内嵌编码，支持图像的渐 ( 2 0 0 0 ) 压缩进传输和随机访问，是目前静止图像压缩的 最新因际标准 1 2 静止图像压缩的简介和研究进展 计算机处理的图像是数字图像。数字图像实质是一个二元数组，这个二元数 组中的每一个样本值称为像素。每个样本值的横纵坐标表示对应的像素在一幅图 像中的位置。样本值的大小表示像素的强度。根据样本取值的不同，数字图像通 常分为二值，灰度和彩色图像。本文主要讨论灰度图像的压缩，对于灰度图像， 每个像素值一般用8 个比特表示，其取值范围为0 、2 5 5 。 我们前面提到数据压缩的原理是去除数据间的冗余。静止图像之所以可以压 缩，是凶为原始图像中存在着大量的信息冗余，包括空间冗余、信息熵冗余、谱 间冗余、几何结构冗余、视觉冗余和知识冗余等等。从信息保持的角度看，又可 分为无失真编码和有损编码两大类，前者要求原始图像可以从压缩数据中准确无 误地恢复，而后者允许重构图像与原始图像之间存在一定的差别。本文主要讨论 有损压缩。 静止图像压缩编码过程包括变换，量化，系数编码和熵编码。典型结构如图 1 1 所示 第一章绪论 3 图1 1 静止图像压缩系统典型结构图 变换的目的在于对原始图像进行处理，减少量化器和熵编码器的工作。对于 一幅自然图像，既有长时间低频成分，如变化缓慢的背景，天空，湖的表面，又 有短暂的高频分量，如边界。低频能量要比高频能量大的多。我们可以想到，将 相关性强的像素，通过变换得到一种去相关的表示方式，将图像的能量集中到有 限的几个系数。常用的变换方法有离散余弦变换( d c t ) 和小波变换，j p e g 标准 采用d c t 变换，但由于d c t 存在严重的边界效应，后来的j p e g 2 0 0 0 标准采取 了小波变换，本文讨论的s p i h t 算法也采用了小波变换，会在后面的部分详细讨 论。 量化是压缩系统产生失真的原因，无损压缩没有量化部分。对于一般情况下 的图像应用，一定的信息损失是可以接受的，人类视觉系统可以容忍很大的信息 损失而不妨碍对场景的感知，这里的有损体现在对像素值的统计计算，人眼是感 觉不到图像损失的。在满足视觉系统感知能力的条件下，量化为图像压缩提供了 广阔的空间，采用设计良好的量化方法可以获得很好的压缩性能。量化分为标量 量化和矢量量化。本文将要讨论的s p i h t 算法采用了标量量化方法。 熵是香农提出的信源统计概念，用来描述信源输出所需的平均位数的的下界， 通过不同的编码方法，任意逼近这个下界是可能的。在实际应用中，一些编码算 法可以非常接近熵的平均比特率。常见的熵编码算法有可变长度编码和算术编码。 4 s p i h t 算法的工程应用 1 3 本文的研究内容 在图像压缩编码领域，更高性能的压缩算法一直是人们不懈追求的目标。一 般用图像恢复质量，压缩l t , i h 算法复杂度来评价压缩编码算法的性能。图像恢复 质量指的是解码后图像的恢复质量，包括主观质量和客观质量。客观质量的衡量 参数一般选用峰值信噪比( p s n r ) 。压缩比，体现了编码效率高低。算法复杂度指 编码算法的信号处理在硬件实现过程中的计算需求，一般以所需运算量和存储量 来衡量。 本文首先讨论了小波变换，详细阐述了小波变换的原理，小波基的生成和选 择原则，并讨论了小波变换的实际实现。然后，以e z w 和s p i h t 为例对目前的 图像编码进行了理论分析和算法研究，在s p i h t 算法的基础上对零树编码进行了 进一步的讨论，提出了一种便于实际实现的改进方法。改进方法继承了原始算法 码率固定、恢复图像质量高的特点，又改进了集合分割与排序策略，获得了更快 的编解码速度。最后，结合实际工程应用的需求，讨论了纠错码选用的原则和压 缩码流的组织形式。 第二章小波变换 第二章小波变换 2 1 概述 一般的函数可以通过一组特殊函数的线性组合来描述。函数厂( f ) 在空间s 上 的线性表示为： ，( f ) = y 如) ( 2 1 ) f 这里， y f ( f ) ) 妇在s 空间是完备的，( f ) 称作空间s 上的基。 令( f ) 为三角函数集，就得到函数的f o u r i e r 级数： 肌) = ( 口fc o s i x + b s i n n x ) ( 2 2 ) i 现在，构造两个特殊函数，伊( f ) 和( f ) ，定义如下 缈 ，= 二：盖三茎? 主。，矽。，= 。1 , ，0 p 括 p t 1 则信号厂( f ) 可以表示为： 厂( f ) = q o ( t - k ) + d m 缈( 2 t - k ) ( 2 3 ) k = - - 一 t = 一j = o 我们称缈( f ) 为h a r r 小波，称妒( f ) 为h a r t 小波的尺度函数，厂( f ) 用矿( f ) 和矽( f ) 表 不的过程( 即式2 3 ) ，就是h a r t 变换。 将h a r r 小波推广，可以得到一般小波变换的函数基： 小波函数基是由满足j r 叭x ) d x = 0 的函数叭z ) 通过平移和缩放而产生的一个 函数族， 虬。6 ( 工) = 圹i 彪妖型) ，口，易r 口o ( 2 4 ) a j c ，。j ( 工) 称作连续小波，这里，a 被称作伸缩因子，b 为平移因子。 函数f ( t ) 小波变换如下 帅川= 二邝，打c 半m 5 ) 代入沙。出( x ) ，w ( a ，6 ) 也可以写成如下表达式， 6 s p i h t 算法的工程应用 w ( 口，易) = 二，( f ) y 础( x ) d t ( 2 - 6 ) 同样，小波逆变换如下， 厂= 吉二二晶秒( 口，6 渺啪d 口d 易 ( 2 - 7 ) 其中， c = 二上兰萨国，甲c 妫= 仁y c r ，e 廊出 ( 2 8 ) 小波及小波变换数学上的严格定义如下： 定义l 设p ( 尺) 是一个可测的、平方可积的一维函数矢量空问，刀为实数集。 小波是由满足l y ( 工) d x = o 的函数y ( x ) 通过平移和缩放而产生的一个函数族 y 。6 ( x ) ： ( 加纩陀纵等) 口易足口o ( 2 - 9 ) y 础( 工) 称作分析小波或连续小波，当且仅当母小波函数沙( 工) 的f o u r i e r 变换纵国) 满足以下可容性条件： c y = 群 阻埘 这里，a 被称作伸缩因子，b 为平移因子。 定义2 在定义1 的基础上，函数厂( z ) 在r ( r ) 上的连续小波变换定义如下： ( 可( 砌( 啪) - ( 似加“x ) ) = 扩7 2 + ，o om m 等) 出 ( 2 - 1 1 ) 从小波的可容性条件可知，母小波函数沙( x ) 是一个振荡且能量有限的函数， 并且在时域上是快速衰减的。容易推出耖( o ) ：0 ，即母小波的f o u r i e r 变换文缈) 经 过原点，这表明y ( x ) 在时域的均值为零。 在实际应用中，尤其是数字信号处理领域，为了计算上的方便，需要使用离 散小波变换进行分解，也就是将厂( x ) 的积分形式展开为离散和形式。所谓离散小 波就是将缈础( 工) 的参数a 和6 离散化。参数昂和b 离散为 第二章小波变换 7 口= 口孑， b = n b o a o ，m ，n z ( 2 - 1 2 ) 这时，离散小波可表示为 ，。( 工) = 坨g ( 口i “工一，z ) ，m ，l z ( 2 - 1 3 ) 特殊地，当= 2 _ r b o = 1 ，可以得到如下二进小波 。( 工) = 2 - m 1 2 9 ( 2 一x - n ) ，m ，t i ez ( 2 1 4 ) 厂( 工) 在正交小波基上的展开式即为小波级数，其数学定义如下： 定义3 一个函数沙r ( 尺) 称为一个正交小波，如果公式( 2 一1 0 ) 中所生成的 函数族帆。) 构成r ( r ) 的一个规范正交基，即 ( j j , k , y 。，。) = 万加以，。j , k ，m , ne z ( 2 1 5 ) 则，对于任意，( x ) l 2 ( r ) 都能写成 厂( x ) = c 。m ，。( x ) 其中c m = ( 厂，。) 。公式( 2 一1 1 ) 称为厂( x ) 的小波级数展开式。 ( 2 - 1 6 ) 在此基础上，提出框架的概念，它是规范正交基的推广。 定义4 满足如下条件的离散小波称为框架： a 0 ，( z ) 1 1 2 k 厂( z ) ，。 ) ) 1 2 b if ( x ) 1 2 ，( o 1 ，则称为松框架，其数据表示具有冗余度且线性依赖，但重建时对噪 声的鲁棒性较好。 小波变换的实质在于将口( 尺) 空间中的任意函数厂( x ) 表示成为在g 。士( 石) 的不 同伸缩和平移因子上的投影的叠加，小波变换的结果就是在不同的频率点和不同 时刻，f ( x ) 与小波的匹配程度。显然，匹配质量取决于小波的选择。下一节将具 体讨论小波基的构造和选择。 s p i h t 算法的工程应用 2 2 小波基的特性和构造 我们知道，图像信源的最大特点是非平稳特性，也就是不能用一种确定的数 学模型来描述，而小波的多分辨率分析特性使之既可高效地描述图像的平坦区域， 又可有效地表示图像信号的局部突变，它在空域和频域良好的局部性，使之能够 聚焦到图像的任意细节，相当于一个具有放大缩小和平移功能的“数学显微镜”。 因此，小波非常适合于进行图像处理。 小波在图像处理中的一个直接应用便是小波图像编码，其出发点在于多尺度 信号分析和基于小波正交基族的信号分解。研究表明，大脑皮层单细胞接受的视 觉信号具有方向性，从视网膜进入大脑皮层的信息处理具有方向滤波环节。小波 变换从多个侧面体现了人眼感知特性，其空间一尺度分层结构与人的视觉系统特性 相似，其多方向梯度提取的特点较为符合视觉生理结构，因此，基于小波的编码 方法可以得到与h v s 相一致的编码质量，为所谓的“感知压缩”提供了客观依据。 在小波理论应用于图像编码之前，变换编码完全由d c t 占统治地位，尤其是 基于d c t 的压缩编码体制已经形成了以j p e g 和h 2 6 1 为主体的国际标准u 建 议，并广泛应用于图像压缩和视频处理的各个领域。基于8 8 方块的d c t 变换 能够很大程度上去除块内的数据冗余，但是难以消除图像整体的结构冗余，在低 比特率下，明显的方块效应是其主要缺点。另外，强制的分块不利于综合考虑人 的视觉特性。对比于传统的d c t 块变换，小波变换具有以下优点： 1 ，小波变换具有熵保持特性，能够有效地改变图像的能量分布，同时不损伤原 始图像所包含的信息； 2 小波分解后大部分能量集中在低频子图的少量系数上；而大量的高频子图系 数值普遍较小，且存在明显的相关性，有利于获得较高的编码增益； 3 小波变换作用于图像的整体，既能够去除图像的全局相关性，又可将量化误 差分散到整个图像内，避免了方块效应的产生； 4 多级分解后形成的不同分辨率和频率特征的子带信号，便于在失真编码中综 合考虑视觉特性，同时有利于图像的逐渐浮现传输； 在本节中，我们将首先讨论小波变换的小波基的数学特性，然后构造适合图 像压缩的小波基。 1 ， 小波具有以下时一频特性： 1 正交性，描述了数据的小波表示的冗余程度，在多分辨率分析下，酉变换在 不同子空间上的投影是l 2 ( r ) 意义的最佳逼近。严格的规范正交特性有利于小波分 解系数的精确重构。 2 光滑性，由小波存在的导数决定，用正则度( r e g u l a r i t y ) 来描述，函数的局 第二章小波变换 9 部正则度和一致正则度的定义如下： 对函数o ( x ) r ( 尺) ，若变量y 工一，x + 】，任意小，满足 l o ( x ) - o ( y ) i 0( 2 1 8 ) 则称函数矽( 工) 在x 处局部正则度名。名的高低描述了函数矽( 工) 正则度的强弱，光滑 程度高的小波在频域局部特性较好。 3 对称性，小波的对称性可以保持原始信号的线性相位，在图像分析与编码中 尤为蕈要。消失矩阶数曰描述了小波函数妙( 工) 相对于尺度函数矽( x ) 的振荡性质， 定义如下：小波函数沙( 工) r ( 尺) ，满足 rx - r g ( x ) d x = 0 ， r = o ，r 一1( 2 一1 9 ) 称函数y ( 工) 具有刀阶消失矩。随着消失矩阶数厅的上升，小波函数y ( 工) 振荡加剧。 对于光滑函数f r 而言，小波函数的消失矩越高，小波分解系数将具有更紧凑 的表示。 4 紧支集，如果尺度函数和小波是紧支撑的，则对应的h 、g 滤波器是f i r 滤波器，信号在分解和重构快速算法中的运算量是有限的。该特性也决定了小波 的时一频局部化性质，尤其在估计局部正则度和检测信号奇异性方面特别有用。 5 能量紧缩测度，该测度由香农率一失真定理导出。 酉变换能量紧缩测度g 陀定义为： = 可豆一 ( 2 珈) ( n 砰) “肼 置= l 其中，以、吼、1 7 分别为输入信号、低通滤波器、高通滤波器的方差。g 亿测 度反映了在给定信源模型下不同子带间的能量集中特性，对于相关性强的信源 g 弼测度越高越有利得到高效率的编码。 最常见的小波基是d a u b e c h i e s 紧支集规范正交小波基，这一类小波基及 其对应的滤波器组具有两两正交、精确重构、有限支集和具有一定正则性等优良 数学特性。该类小波函数的正则度较好，对应滤波器组的幅频响应旁瓣较低，有 利于图像处理。但是，此类小波基是非对称的，在有损编码中会引起重构信号的 1 0 s p i h t 算法的工程应用 相位失真。在限定失真编码的情况下，恢复图像侧重于保留原始图像中的边缘和 轮廓信息，对遥感图像来说更注重保留点、线等小目标的形状和位置信息，因为 它们往往是一幅遥感图像的重要价值所在，因此，保持线性相位特性对于图像重 构是非常重要的。但是，具有精确蕈构性质的线性相位f i r 的正交小波分解滤波 器已经证明是不存在的，于是c o h e n 和d a u b e c h i e s 等放宽了小波基的规范正交性 要求，引入了双正交小波基。对称的双正交小波基可以满足图象处理中比较严格 的线性相位特性要求，不仅可以减少或消除重建图象的边缘失真，而且在级联的 塔型结构中无需相位补偿，同时支集较短便于快速实现和进行边界处理，因此在 图像编码领域得到广泛的应用。 2 ，小波基的构造 构造紧支撑正交小波要解决的问题是，对于庇= h o ，啊，h i ，j z l ，吃满 足怎样的条件，才能使尺度方程矽( f ) = 2 魂矽( 2 f 一足) 存在解矽( f ) l 2 ( r ) ，并且 乒( 动：n 丛学收敛，并且收敛于r ( 尺) 中某个正交函数的f o u t i e r 函数。 j = l n 二 小波函数及其尺度函数必须满足下列必要条件 ( f ) = 压亿矽( 2 f 一尼) 七 衲= 压五t ( 2 f 一七) k 杪( f ) = 压g t 杪( 2 卜足) 正 痧( t ) = q t 2 z g 。汐( 复一七) 七 根据前面讨论的小波基的特点，可以得到 吃= 压 k h 萨压 k g 。= 0 k ；。= o k 妒( 动：1 - v ih ( w 2 7 ) 矽( 动= f l h ( w ，2 i ) 妒( 动= f lh ( c o 2 i ) 矽( 动= f lf f f t o ，2 j ) 第二章小波变换 有限滤波器五，h ，；，g ，使得尺度函数矛，矽和对偶函数痧，沙存在的必要条件是： 吃噍+ ：。= 磊，。 t |z2。=万1kk y 二 五zt=万1kk y 二 g 。= ( 一1 ) “ g 。= ( - 1 ) ”h i 一一 根据以上讨论，我们可以得到几个满足前面讨论的是和图像压缩的小波基 1 ，5 3 小波滤波器的系数 设kt=h-2,h-,ho,h,兄濮帆群-1-t厩i,-2-旷-f2,h扭1-h h o 啊 i 以= 2 ，吼= 2 吃 篇葛。j i 1 匿，丽1 ，丽3 ，丽1 ，一硒1 ) 2 见二1 【吲一1 1 1 q o 12 4 24 22 4 2 ) = 【 2 ，9 7 小波滤波器的系数 设j 忍= 庇- 4 ，庇一3 矗_ 2 ，庇1 。，玩，办2 , h 3 , h 4 ) ，其中， 【h = 垃：，垃。，h o ，啊，| z 2 ) p o2 l z p 2 一仇 l p l2 i p 3 - p 3 = q 2 案 4 q ，- 4 - 1 p 2 = 4 ( 。4 竖q 3 一- 1 ) 1 留，2 互一q 3 4 一搪 气正拼矩 引卢 以 ， ， l记k 砑 = = = _ 庇庇 以 1 2 s p i h t 算法的工程应用 2 3 小波变换的实现 1 多分辨率分析( m u l t i - r e s o l u t i o na n a l y s i s ，m r a ) m r a 的概念最早是由m e y e r 和m a l l a t 引入的，后来又由m a l l a t 将m r a 理 论用于小波分解与重构的算法构造上。 首先引入m r a 的定义： 定义5 平方可积空间l 2 ( r ) 中的一系列闭子空间 l j z 称为l 2 ( r ) 的一个多 分辨率分析，满足如下条件： ( 1 ) 一致单调性：c 一，_ z ( 2 ) 渐进完全性：ny f = 0 ) ，u y ，= r ( r ) ，e 二，z ( 3 ) 伸缩不变性：厂( z ) 巧f ( 2 x ) + l ，歹z ( 4 ) 平移不变性：厂( x ) l f ( x 一尼) v j ，j ，k z ( 5 ) r e i s z 基存在性：存在矽( x ) v o ，使得 矽( x 一忌) ) 。z 是的r e i s z 基。即 v o = s p a n d ) ( x 一足) ，k z ) ( 2 2 1 ) 并存在0 a b - , y、 叫一。、 名 n 0 。 l 一 t l 、，、 l 一 图3 1 小波变换后的子带结构图3 2 空问方向树的继承关系 图像经过小波变化后，l h ，h l ，h h 子带系数之间所呈现出强烈的带间 相关性，能量几乎集中在最低频的子图像上，其余能量从低频到高频递减分布。 直观上表现为，数值从低频子带向高频子带递减。进一步观察，可以发现如果某 个结点系数的值很小，那么其对应的孩子结点系数一般不会超过该系数的大小。 特别的，如果某个系数为o ，则它所有的孩子结点的系数也都为0 ，这样，由不同 频带、代表同一空间位置的系数构成了一种树型结构，并且高频部分存在大量的 零，所以称为零树结构，或者叫做空间方向树。如图1 说示，我们称儿3 子带中 的系数是h l 2 ，吐2 和h h 2 子带中系数的父亲结点，每个父亲结点有4 个孩子 s p i h t 算法的工程应用 结点。反过来，h l 2 ，儿2 和h h 2 子带中的系数结点叫做比3 子带中系数结点的 孩子结点。图2 表明了节点的父子关系，除了儿频带的根节点具有3 个子节点以 外，其它父节点具有在更高子带中的4 个子节点，其数学描述如下式所示： i ( i ，歹) ) ； t r e e ( i ，_ ，疗) = t r e e ( 2 i ，2 j ，以一1 ) u t r e e ( 2 i + l ，2 j ，z - 1 ) ( 3 1 ) i u t r e e ( 2 i ，2 j + l ，n 一1 ) u t r e e ( 2 i + l ，2 j + 1 ，n - 1 ) 其中，表示系数图像中的坐标，n 表示小波级数。 2 ，e z w 的算法概述 e z w 的最初提出是用于解决两个问题： 1 ，如何从给定的压缩码流中，解出可能得到的最好质量的图像； 2 ，如何构造嵌入式码流，也就是说，随着压缩码流长度的增加，恢复图像的 质量逐渐变好。 e z w 算法的基本思想和之前的算法一样： l ，对系数进行分类，指定优先级，也就是标记系数的重要性； 2 ，在编码过程中，标记优先级和编码状态。 e z w 算法将系数分成4 类：零树根t ( z t r ，z e r o t r e er o o t ) ，孤立零点 z ( i z ，i s o l a t ez e r o ) ，正重要系数p ( p o s i t i v e ) 和负重要系数n ( n e g a t i v e ) 。对一个给 定的阈值丁，如果系数x 本身和它所有的子孙皆小于丁，则该点就称为零树根； 如果系数本身小于丁，但其子孙至少有一个大于或等于丁，则该点就称为孤立零 点。当编码到最高分辨率层的系数时，由于它们没有子孙，零树根不再存在，只 需两种符号即可。 在编( 译) 码过程中，始终保持着两个分离的列表：主表和辅表。主表对应 于编码中的不重要的集合或像素，其输出信息起到了恢复各重要值的空间位置结 构的作用，而辅表是编码的有效信息，输出为各晕要像素的二进制值。编码分为 主、辅两个过程：在主过程中，设定阈值为正，按上述原理对主表进行扫描编码， 若是重要系数，则将其幅值加入辅表中，然后将该系数在数组中置为零，这样当 阈值减小时，该系数不会影响新零树的出现；在辅过程中，对辅表中的重要系数 进行细化，细化过程类似于比特平面编码。对阈值z 来说，重要系数的所在区间 为 互，2 7 ；) ，若辅表中的重要系数位于 i ，3 t 2 ；) ，则用符号。表示，否则用符号 1 表示。 第i 章压缩算法 2 1 e z w 算法的流程如图3 3 所示： 图3 3e z w 算法的流程图 s p i h t 算法的工程应用 3 2 原始s p i h t 算法 前一节提到的零树结构最早由j e r o m em s h a p i r o 在e z w 算法中提出，a s a i d 和w a p e a r l m a n 根据s h a p i r o 零树编码的基本思想，提出了一种新的并胃性能更 优的实现方法，即基于分层树集合分割排序( s p i h t ，s e tp a r t i t i o n i n gi nh i e r a r c h i c a l t r e e s ) 的编码算法。s p i h t 算法是一种非常实用有效的