（系统分析与集成专业论文）基于小波变换的图像压缩方法研究.pdf

摘要 随着信息时代的到来，特别是互联网的普及，多媒体技术的广泛应用，在享受信息 社会“数字化”便利的同时，图像的海量数据给通信带宽和存储介质带来了巨大的负担。 因此，对各种数据进行适当的压缩编码，以便于数据更有效的存储和传输，一直是信息 处理技术研究的热点。 本文主要论述了图像压缩编码研究的背景及意义，包括小波变换与图像压缩编码的 研究现状；介绍了小波变换的理论与图像压缩编码的基本方法；研究了小波变换在图像 压缩编码中的应用，并提出了一种基于整数小波变换的d a u b e c h i e s 9 7 提升改进算法。 该算法综合了小波提升方法和小波多分辨分析的优点，与传统小波变换方法相比，计算 复杂度低，运算量小，算法具有普遍性，重构图像质量高，取得了令人满意的效果。 关键词：图像压缩；小波变换；多分辨分析；提升方法； ，a b s t r a c t w i t ht h ei n f o r m a t i o nt i m e sc o m i n g , e s p e c i a l l yi n t c m e th a sb e c o m em o r ea n dm o r e p o p u l a ra n dm u l t i m e d i at e c h n o l o g yi se x t e n s i v e l ya p p l i e di nm a n yf i e l d s w h e nw ee n j o y c o n v e n i e n c eo fd i g i t a li n f o r m a t i o ns o c i e t y , an u m b e ro ft h ei m a g ed a t eb r i n gh e a v yb u r d e nf o r b a n dw i d t ho fc o m m u n i c a t i o na n ds t o r i n gm a t e r i a l t h e r e f o r e ，g i v i n ge v e r yk i n d so fd a t a n e c e s s a r yc o m p r e s sa n dc o d i n gi no r d e rt os t o r ea n ds e n dd a t am o r ec o n v e n i e n t l yh a sa l w a y s b e e nt h eh o ts p o ti nt h ef i l e do fi n f o r m a t i o np r o c e s s i n gt e c h n o l o g y t h ep a p e rm a i n l yf o c u s e so nt h er e s e a r c ho fb a c k g r o u n da n di m p o r t a n c eo fi m a g e c o m p r e s sa n dc o d i n g , w h i c hi n c l u d es t u d ys t a t eo fw a v e l e tt r a n s f o r ma n di m a g ec o m p r e s sa n d c o d i n g t h et h e o r yo ft h ew a v e l e tt r a n s f o r ma n dt h eb a s i cm e t h o do ft h ei m a g ec o m p r e s sa n d c o d i n ga r ei n t r o d u c e d t h e nw a v e l e tt r a n s f o r mu s e di ni m a g ec o m p r e s sa n dc o d i n gi s r e s e a r c h e d ，a n dad a u b e c h i e s 9 7i m p r o v i n gl i f ta l g o r i t h mb a s e do ni n t e g r a lw a v e l e tt r a n s f o r m i sg i v e n t h i sa l g o r i t h mi n c l u d e st h ea d v a n t a g e so fw a v e l e tt i f fm e t h o da n dm u l t i d i f f e r e n t i a t e a n a l y z e ，c o m p a r i n gw i t ht r a d i t i o n a lw a v e l e tt r a n s f o r m ，i th a v el o w e rc o m p u t i n gc o m p l i c a t i o n a n ds h o r t e rc o m p u t i n gt i m e ，i th a sb e t t e ru n i v e r s a l i t ya n dh i g h e rr e b u i l di m a g eq u a l i t y ，a n d t h i sa l g o r i t h mh a ss a t i s f i e dr e s u l tu s e di ni m a g ec o m p r e s sa n dc o d i n g k e y w o r d s ：i m a g ec o m p r e s s ：w a v e l e tt r a n s f o r m ；m u l t i - d i f f e r e n t i a t ea n a l y z e ； l i f tm e t h o d ； 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 论文作者签名：毒j i 司乏 日期：妇7 年6 月争e t 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的e i 局u 本和电子版本；学校有权保存学位论文的 印刷本和电子版，并提供目录检索与阅览服务；学校可以允许采用影印、缩印、数 字化或其它复制手段保存学位论文；在不以赢利为目的的前提下，学校可以公丌学 位论文的部分或全部内容。( 保密论文在解密后遵守此规定) 作者签名：毒lt 竭忍 指导教师签名：参1 j 式 日期：7 ， 日期：j 娜7 白【l 。 1 绪论 1 绪论 1 1 图像压缩编码研究的背景及意义 二十世纪末，人类社会开始进入到数字化时代，数字图像技术作为数字技术的重要 组成部分，将人们带入了崭新的多媒体世界。随着科学的发展，社会的进步，人们对图 像信息的需求也越来越大。在多媒体计算机系统、电子出版、视频会议、数字化图书馆 等许多领域，数字图像都有着广泛的应用。然而，用以表示这些图像的数据量很大，使 得存储成本很高，尤其不能满足现今网络环境下进行多媒体通信的需求。由此，图像编 码理论应运而生，并且迅速发展起来。 图像编码，即图像压缩，就是在保证一定重构质量的前提下，去除图像中的各种冗 余，以尽量少的比特数来表征图像信息。传统的图像编码是以香农信息论为出发点，用 统计概率模型来描述信源。编码实体是像素或像素块，以消除数据相关冗余为目的，由 此产生的 p e g 、m p e g - 1 、m p e g - 2 、h 2 6 1 及h 2 6 3 等编码国际标准已经获得了很大的成 功。新一代基于内容的图像编码方法，充分考虑了信息接收者的主观特性、图像信息的 具体含义和重要程度，以消除图像内容冗余为目的，是目前一个较为活跃的研究领域。 小波分析是傅立叶分析和调和分析发展史上的一个里程碑，被誉为“数学显微镜”。 作为一种多分辨率分析方法，也非常有利于图像时频局部化特性，特别适合按照人眼视 觉特性设计图像编码方法，也非常有利于图像信号的渐进传输1 1 1 。在实际应用中，基于 小波变换的提出，为小波图像编码注入了新的活力。提升小波变换的提出，为小波图像 编码又一次注入了新的活力，与传统的小波变换相比，它不依赖于傅立叶变换，计算简 单，时间、空间复杂度低，易于实现，被称为第二代小波变换。而且，随着各种高效的 小波系数量化方法的提出，基于不同小波的图像编码方法的发展越来越迅速，并取得了 非常好的效果。所以，在新的国际编码标准j p e g 2 0 0 0 和m p e g - 4 中都采用了基于小波变 换的图像编码方法1 2 0 1 1 2 1 j 【捌。 图像编码技术的发展，使数字图像的广泛应用成为可能，从家庭中迅速普及的v c d 、 d v d 等数字影像产品，到医学领域的c t 、远程会诊和彩色b 超，从遥感领域的遥感图像 传输存储，到多媒体通信领域的视频点播、远程会议，这些都与图像编码技术密切相关。 随着数字图像技术的发展和广泛应用，对图像编码技术性能的要求将越来越高，特别是 二十世纪九十年代以来，多媒体通信技术大量引入，迫使人们采用高压缩比的编码技术， 湖北大学硕士学位论文 这又给图像编码技术的发展注入了新的活力。此外，其它领域，如神经网络、分形和数 字形态学等新理论新方法的发展，也为图像编码提供了新的方向。数字图像编码技术作 为图像处理的关键技术，其发展必将促进数字图像及其相关技术的发展。因此，研究开 发高效的图像编码方法具有重大的理论和现实意义。 1 2 小波变换与图像压缩编码的研究现状 二十世纪八十年代以来，小波变换因其特有的多分辨率分析能力及方向选择特性， 而被广泛应用于图像编码领域，取得了很大的成功。 一般而言，小波图像编解码具有如图卜i 所示的统一结构框架。 原始图像伍垂 卜臣匠 虹亟j 一 重构图像巫垂丑圃一 图i - i 小波编解码框图 比特流输出 比特流输入 熵编码主要有游程编码、霍夫曼编码和算术编码等，而量化为小波编码的核心，其 目的是为了更好的组织图像经小波变换后的系数，以实现高效压缩。图像经小波变换后， 并没有实现压缩，只是对整幅图像的能量进行了重新分配。事实上，变换后的图像具有 更宽的范围，但是宽范围的大数据被集中在一个小区域内，而在很大的区域中数据的动 态范围很小。小波变换编码就是在小波变换的基础上，利用小波变换的这些特性，采用 适当的方法组织变换后的小波系数，实现图像的高效压缩。 从小波变换的数学理论来说，它是继傅立叶变换之后纯粹数学和应用数学完美结合 的又一光辉典范，享有“数学显微镜”的美称。从纯数学角度来说，小波变换是调和分 析( 包括函数空间、广义函数、傅立叶分析和抽象调和分析等) 这一重要学科大半个世 纪以来的工作结晶；从应用科学和技术科学的角度来说，小波变换又是计算机应用，信 号处理、图像分析、非线性科学和工程技术近几年来在方法上的重大突破f 4 】。同时小波 变换在它的产生、发展、完善和应用的整个过程中都离不开计算机科学、信号和图像处 理科学、应用数学和纯粹数学、物理科学和地球科学等众多研究领域和工程技术应用领 域的专家、学者和工程师的共同努力，现在小波变换已经成为科学研究和工程技术应用 中涉及面极其广泛的一个热门话题。 小波变换是继1 8 2 2 年法国人傅立叶提出傅立叶变换之后又一里程碑式的发展，解 2 1 绪论 决了很多傅立叶变换不能解决的困难问题。傅立叶变换虽然已经广泛地应用于信号处理 领域，较好地描述了信号的频率特性，取得了很多重要的成果，但傅立叶变换不能较好 地解决突变信号与非平稳信号的问题。小波变换可以被看作是傅立叶变换的发展，即它 是空间( 时间) 和频率的局部变换，能更加有效地取信号和分析局部信号1 1 1 l 。 小波变换用于图像压缩是小波变换应用的一个重要方面。在图像压缩技术中，小波 变换与k l 变换、d c t 变换等隶属于变换编码技术。所谓变换编码技术是将时域图像( 空 间) 变换到系数域( 频域) 上再进行处理的一种方法。在空间上具有强相关的信号，反 映在频域上是在某些特定的区域中能量集中在一起，或者是系数矩阵的分布具有某种规 律性，利用这些规律对频域平面量化器进行合理的( 非均匀) 比特分布，高能量区给以 高的比特数，低能量区给以低的比特数，就达到了压缩的目的。小波变换相比其他变换 编码技术来说，压缩比高，压缩速度快，压缩后能保持图像的特征基本不变，且在传递 过程中可以抗干扰。 1 3 本论文所做工作介绍 图像压缩这一研究课题，难度大，实用性强，而研究小波变换压缩技术是图像压缩 技术中的热点之一，本论文对基于小波变换的图像压缩编码技术作了一些有益的研究， 主要工作如下： 第一部分论述了图像压缩编码研究的背景及意义，包括小波变换与图像压缩编码 的研究现状； 第二部分介绍了小波变换的理论； 第三部分阐明了图像压缩编码的基本方法； 第四部分研究了小波变换在图像压缩编码中的应用，并提出了一种基于整数提升 小波变换的改进算法； 第五部分结束语。 3 湖北大学硕士学位论文 2 1 小波变换 2 小波变换的理论 小波变换( w a v e l e t ) 是由法国数学家m o r l e t 于1 9 8 0 年提出的，他与法国物理学家 6 r o s s m a n n 共同提出连续小波变换的几何体系，基础是平移和伸缩下的不变性。本节介 绍小波、连续小波变换与离散小波变换的基本概念与性质。 2 1 1 小波( w a v ele t ) 的定义 定义2 1 ：小波( w a v e l e t ) 的定义：设妒o ) 为一平方可积函数，即妒o ) 僻) ，若其 傅里叶变换妒( ) 满足条件 掣2 咖c * ( 2 - 1 ) 则称妒o ) 为一个小波或小波母函数，并称式( 2 1 ) 为小波母函数的“可容许性条件” ( a d m i s s i b l ec o n d i t i o n ) 。 由小波定义可知，小波一般具有如下特点： 1 紧支性一小波在时域都具有紧支集( 函数紧支集即函数定义域( 非零域) 有限) 或 近似紧支集。 2 波动性一由于小波满足“可容许性条件”，则必有妒酬。一0 ，即直流分量为零。 由此可断定小波具有正负交替的波动性。 定义2 2 将小波母函数妒o ) 进行伸缩和平移，设其伸缩因子( 又称尺度因子) 为a ， 平移因子为f ，称如下形式的函数 妒。，( f ) 口( 丝) ，a o , t ：e r ( 2 - 2 ) 妒。( f ) - 口2 妒( = 二) ， () 为由小波母函数妒o ) 生成的依赖于参数口，f 的连续小波基函数。 设小波母函数妒o ) 的窗口宽度为t ，窗口中一6 , 为t o ，则可求得连续小波 妒。，( f ) 一n 1 妒( 字) 的窗口中心为 4 窗口宽度为 乞j - a t o + f a t 。一a a t ( 2 - 3 ) ( 2 - 4 ) 设为掣( ) 为妒o ) 的傅立叶变换( 其中1 l ，( ) 一丘。“妒( f ) 出，其频域窗口中心为， 窗口宽度为a ，设妒。，o ) 的傅立叶变换为妒。， ) ，则有 ! 咒，( 叻- a2 e 1 。v 0 ) ， ( 2 - 5 ) 则可求得其频域窗口中心为 1 ，二n ，o( 2 6 ) 窗口宽度为 a m o 。一- - * a o 口( 2 - 7 ) 由上可知连续小波妒。，o ) 的时、频域窗口中心及宽度均随尺度口变化而伸缩。由于 a t 。，n ，- 4 f 二ia t a o 口( 2 - 8 ) 如果称出a 为窗口函数的窗口面积，则由上可知连续小波函数的窗口面积不随参 数4 f 而变。这正符合海森堡测不准原理：a t a 的大小相互制约，乘积址珊i 1 窖 且只有当妒o ) 为g a u s s i a n 函数族 ， ， 妒( f ) - ：每e “，4 ，0 时，等式才成立。 0 v 册 由此还可得到如下三点结论： l 尺度的倒数兰a 生在一定意义上对应于频率珊，即尺度越小，对应频率越高，尺度 越大，对应频率越低。 2 在任何f 值上，小波的时、频窗口的大小厶f 和a 埘都随频率( 或者三) 的变化而 a 变化。 3 由于小波母函数在频率具有带通特性，其伸缩和平移系列就可以看作是一组带通 滤波器。这与人类感觉( 包括视觉、听觉) 的生理过程机制有类似之处。 5 湖北大学硕士学位论文 2 1 2 连续小波变换 定义2 3 将任意l 2 ( r ) 空间中的函数f ( t ) 在连续小波基下进行展开，称为f ( t ) 的 连续小波变换( c o n t i n u ew a v e l e tt r a n s f o r m ，简记为c w t ) ，其表达式为 w t f ( a , r ) 一t ，o 脚。卜一n 了一，( f 渺( 等沙( 2 - 9 ) 从数学意义上来看，连续小波变换将函数在小波基下展开，意味着将一个时间函数 投影到二维的时间一尺度相平面上。从时频分析的角度看，小波变换是一种变分辨率的 时频联合分析方法：当分析低频( 对应大尺度) ，其时间窗很大，而当分析高频时( 对应小 尺度) 信号时，其时间窗减小，这恰恰符合实际问题中高频信号的持续时间短、低频信 号的持续时间长的规律，因此，小波变换在时频分析领域里具有不可比拟的优点。 尺度和位移均连续变化的连续小波基函数形成了一组非正交的过度完全基，这说明 其任意函数的小波展开系数之间有一个相关关系。因此c 1 f i 系数具有很大的冗余性，从 计算量来说，这是它的缺点之一，但我们也可以利用这一点实现去噪和数据恢复。 定理2 1 令妒是一个小波基函数，它定义了一个连续小波变换聊，缸，f ) 那么 鸭) 匾砑】窘加q cf , g ，( 2 - 1 0 ) 对于所硐f ，g l ( 脚成立，而且对十任伺f l ，有 ，国d i 。耐d a 。【蚂以，f 渺。，( f 渺 2 一1 1 ) 其中，q 正丝警坚d o j 0 0 ，( f ) 的可允许性条件( a d m i s s i b l e c o n d i t i o n ) 连续小波变换具有以下重要性质： 1 线性变换性：一个多分量信号的小波变换等于各个分量的小波变换之和： 2 平移不变性：若f ( t ) 的c w t 为w t f ( a ，f ) ，则f ( t t 。) 的c w t 为w t i ( 口，v - t o ) ： 3 伸缩共变性：若f ( t ) 的c w t 为啊。，f ) ，贝l j f ( a t ) 的c w t 为击啊( 知，a f ) 4 自相似件：对商不同足彦参数口和不同平移参藿蕾f 的c w t 乡闻帚自相似的： 6 2 小波变换的理论 5 冗余性：c w t 中存在信息表述的冗余度( r e d u n d a n c y ) 。 小波变换的冗余性事实上也是白相似性的直接反映，它主要表现在以下两个方面： ( 1 ) 由连续小波变换恢复原信号的重构分式不是唯一的。也就是说，信号f ( t ) 的小波 变换与小波重构不存在一一对应关系，而傅立叶变换与傅立叶反变换是一一对应的。 ( 2 ) 小波变换的核函数即小波函数妒。，o ) 存在许多可能的选择( 例如，它们可以是非 正交小波、正交小波、双正交小波，甚至允许是彼此线性相关的) 。 小波变换在不同的( 口，f ) 之间的相关性增加了分析和解释小波变换结果的困难，因 此，小波变换的冗余度应尽可能减小，它是小波分析中的主要问题之一。 2 1 3 禹散小渡变换 在计算机上实现时，连续小波变换( c w t ) i i , f 1 0 ，f ) 必须离散化。这一离散化是针对 连续尺度参数4 和连续平移参数f 的，而不是针对时间变量t 的。 定义2 4 当由小波妒( f ) 经伸缩和位移引出函数族： 妒 ( f ) - 口o 。j 妒( a o - j t 一七t ) j ，k e z ( 2 1 2 ) 具有下述性质时： a i i i i l 2 阿，妒肚，1 2 s b i i i i l 2 ，o t 爿t 口c m ( 2 - 1 3 ) 称切肚( f ) l 皿构成一5 - j 、波框架。i i j ：( 2 1 3 ) 为d 、波框架条件，其频域表示为 口s 荟p ( 2 珊) 1 2s 卢，o t 口c 卢c ( 2 - 1 4 ) 定义2 5 任意函数f ( t ) 的离散小波变换为 w t ，( j ，七) 。正，o ) 。妒似( f 矽 ( 2 1 5 ) 定理2 2 若离散小波序列扣”l 皿构成一个小波框架，其上、下界分别为a 和b ， 则当a = b 时( 紧框架) ，离散小波变换的逆变换为 ，( f ) 。善，妒矿张o ) 。j 1 靠i v i ， ( 2 3 2 ) 称为f ( t ) 在分辨率2 。的离散逼近。 d 。可以表示为： d ，o ) 。荟，( f ) ，妒肛( f ) 妒， ( f ) ：( 2 - 3 3 ) 离散信号 d ；，o ) 一tf q ) ，妒肚o 卜 ( 2 3 4 ) 称为f ( t ) 在分辨率2 - j 的离散细节信号。 将公式( 2 2 7 ) 对时间进行伸缩和平移，有 1 1 湖北大学硕士学位论文 妒( 2 1 一七) 一 ) 丸抽( 2 7 t - k ) 2 2 弦( 2 ( 2 1 一k ) - 厅) 2 2 o 弦( 2 小1 卜2 k 一玎) 令m = 2 k + n ，则有 妒( 2 。f 一七) - 2 i l 伽一勉( 2 7 “t - m ) ( 2 - 3 5 ) 将公式( 2 - 3 5 ) 代入公式( 2 - 3 2 ) ，得 可，o ) - c ，( f ) ，办j o ) ，一i l ( 所一2 k ) t ，( f ) ，办舢( f ) ， 2 | i l 劬一勉烨。，( f ) ( 2 3 6 ) 由公式( 2 3 6 ) 可知，譬，( f ) 可由。厂( f ) 导出。 同理，d ；，( f ) 也可直接由哗。，o ) 导出，并可得 d ；，o ) = e g ( m 一放) 鼍i f ( t ) ( 2 3 7 ) 一 其中 g ( 开) 一( 一1 ) ”h ( 1 一开)( 2 3 8 ) 上述讨论了信号的分解过程，信号的重建过程的推导如下： 设函数，( f ) 。，则 ，( f ) 一雌- f ( t ) d j 一耻( f ) ( 2 3 9 ) 又 ，o ) 。；彳，( f ) 办，( f ) + 摹d ；，( f 渺肼o ) ( 2 - 4 0 ) 将公式( 2 - 2 9 ) 、公式( 2 3 0 ) 代入公式( 2 4 0 ) ，得 ，( f ) 。军彤，( f ) 军 o 协一。m + 一( f ) + ；d j ，o ) ；g o 渺h ”+ 。( f ) 在上式中令m = 2 k + n ，且两边对妒j - l m o ) 进行内积，再与公式( 2 3 9 ) 比较可得 掣，o ) 。；彤j i l 一致) + 乏d ；g 一放) ( 2 - 4 1 ) 因此，一维m a l l a t 分解与重构算法可总结为图2 一l 所示。 m a l l a t 算法的实质是不需要知道尺度函数妒( f ) 与小波函数妒( f ) 的具体结构，只由系 数就可以实现f ( t ) 的分解与重构，因此它被誉为快速小波变换( f w t ) 。 2 小波变换的理论 只s 孓：珍。，+ 、。 d ，+ ：v 。，+ ：y 。+ l 只+ ，一只+ 一_ 。1 设e 匕为l 2 ( r ) 中的一个多分辨分析，相应的尺度函数为妒 ) 定义j 尺度下的 忆k 为二维l 2 ( r 2 ) 空间的多分辨分析。 e 。- 巧。o 一。( o 矸0 ) ( e y j ) 记呒一曰。瞬。曰，其中曰一o v j ，砰- v j o ，曰一o ， 嘭为e 一，中e 正交补空间，对任意的，如果，一，有影上形，且空间蟛、 由办，( d - 2 二24 6 ( 2 - 1 x - n ) 是的标准正交基可得，协，( z ) c j 。( ) ，) l 。一定是哆的 标准正交基。将曰，砰，曰称之为二维小波空间，显然，移加o ) 办，( ) ，) t 。是砑的 标准正交基，协，o ) l f ，加( ) ，) l 一是曰的标准正交基，切加。即胁( ) ，) l 橱是曰的标准 枷舢( x ) c j ，( ) ，) n 协， 渺加( ) ，) n 协，o ) 办，( y ) 境。 湖北大学硕士学位论文 构成谚空间的标准正交基。 对l 2 ( r 2 ) 空间中的任意函数，o ，y ) 唬在二维正交小波基下展开，可得( 2 4 3 ) 如下： ，o ，y ) 。套荔【口：。 f ，加o m 。( ) ，) + 雕，办，o 渺朋( ) ，) + y ：胁 一y ) 】+ 荟s ：办。o 协， 其中 口厶一强：， ，y 砂抽o ) j i 渤( 2 - 4 4 ) 如- 儿：f ( x ，y 批 厩两叻 ( 2 4 5 ) y 0 一f f ：，o ，) ，渺加。厩了；汹 ( 2 4 6 ) s 缸。肌：f ( x ，y ) c s 。 ) 办。o ) 如妙 ( 2 4 7 ) 上标表示j 尺度，下标表示两个方向的位移，口二，成，r 二为分别对应于 砑，霹，彬的小波展开系数，j 二为对应于尺度空间e 的尺度展开系数。 ( 2 4 4 ) ( 2 4 7 ) 为二维正交小波变换的分解公式。 假定s ：f 为0 尺度空问的尺度系数序列，h ( n ) 和g ( n ) 分别为小波函数的低通和高通 滤波器，二维小波分解的m a l l a t 算法是 口二一三g 一劲似一2 ，磁 ( 2 4 8 ) 础一 ( 七一2 i ) g ( m 一卫弦最 ( 2 4 9 ) r 二- 艺g ( 七一复) g 伽一型弦名 ( 2 5 0 ) j 矗- 矗 一五) j l ( 嘶一甜沁嚣 ( 2 5 1 ) 二维小波合成的m a l l a t 算法是 s t t - 一1 。善5 加( 七一五冲伽一刀) + 善口二g 一复冲伽一复) + 善础_ j l 一互) g 似一刃) + 艺y 拈 一轨细一2 0 ( 2 5 2 ) 2 3 基于提升方法的小波变换 传统的小波变换是在频率域进行的，其基本的变换工具是傅立叶变换，又称为第一 代小波变换。其变换过程主要是对图像行列分别滤波，进行卷积运算，其过程复杂，运 1 4 2 小波变换的理论 算量大，不利于硬件和实时实现。此外，原始图像的整数数据经过传统小波变换后，得 到的是浮点数。从计算机有舍入误差的角度来看，通常这样的小波变换不能无失真地重 构，因此不能用于无损图像编码。而且，在对变换后的系数编码压缩时需要先进行量化， 量化的结果损失了一定的数据信息，无法完全重构。提升方法则摆脱了传统的滤波器和 傅立叶频域的概念，可以直接利用时域信号，从预测和更新的角度来设计算法。对提升 算法稍加改进，就可以实现整数到整数的变换，从而实现图像的无损压缩。所以，基于 提升方法的小波变换被称为第二代小波变换。 2 3 1 提升方法 小波变换的基本思想是利用信号问存在的相关性，建立一种信号的稀疏表示。传统 的小波变换即第一代小波变换是通过傅立叶变换建立时频分析，小波变换的提升方法则 通过欧几里德算法来寻找低通、高通滤波器两者的最大公因子，最大限度地挖掘两者之 间的计算冗余，大大降低m a u a t 算法的计算复杂度。其通过基本的多项式插值来获取信 号的高频分量，之后通过构建尺度函数来获取信号的低频分量，基本思想就是通过一个 基本小波( 1 a z y w a v e l e t ) j 丕步构建出一个具有更加良好性质的新的小波，完全在信号的空 间域，对信号实施分裂、预测和更新三大步骤，完成对信号的频率分解。 由提升方法构造的小波变换包含三个步骤：分裂( s p l i o 、预测( p r e a i c t ) 和更新( u p d a t e ) ， 如图2 2 所示。九 图2 - 2 提升方法的实现步骤 设有数据序列九，由于数据之间有某种相关性，可以将它用更紧凑的形式来表示， 也就是说，寻找原数据序列的一个子集，使它能够表示原始信号所包含的信息。 ( 1 ) 分裂：将数据序列九分裂成为两个小的子集和r 一。理论上我们可以将信号任 意划分，但考虑到实际中信号的相邻数据之间的相关性比较强，可将信号按其数据的奇 偶序号对数据序列进行间隔采样，即： 湖北大学硕士学位论文 九m = 九” k z ( 2 - 5 3 ) y m = 九+ 1 k z 这就是前面提到的基本小波。它只是将信号简单地分为两个部分，并没有做其它的 操作，所以不能改进对信号的描述，但分裂得到的两部分具有高度的相关性，可以通过 气，。来预测。 ( 2 ) 预测：设一个与数据无关的预测函数p ，使得： r 。1p ( 九，) ( 2 - 5 4 ) 那么，我们可以用t 。来表示原始的数据，称y 。为小波系数，我们可以用y 一。和它的 预测值之间的差值来代替y 。如果使用合理的预测，那么差值将包含比原来y 一。少得多 的信息，记为： y l i y 一1 一p ( a 1 ) ( 2 5 5 ) 则此时的小波系数y 。，表明了由预测函数p 引入的误差。这样，就可以用较小的 数据序列l 和小波系数y 。来代替原始的数据。如果有一个好的预测，那么两个子集 h ，y 。 将产生比原来的序列九更为紧凑的形式。 ( 3 ) 更新：经过分裂和预测两个步骤并不能在予集数据中维持原始数据序列的某些楚 体性质，如均值等。为此，必须采用更新过程。更新的思想就是找出一个更好的子集九。 使之保持原始数据的一些尺度特性，即对于某一个度量标准q ( ) ，a 。和九有相同的值： q ( a 。) iq ( 九)( 2 5 6 ) 用已计算出的小波系数y 。，来更新九，从而使a 一。保持上述性质，构造一个更新操 作u 并对a 一，进行如下更新： - 九。+ u ( r 1 )( 2 5 7 ) 重复上述步骤，经过一定次数的迭代之后，我们就可以得到原始数据序列的一个多 级分解，从而得到基于提升方法的小波变换公式为： 2 小波变换的理论 仨 ” m 8 ， y i 。y | n h 其中一，t j 日一1 。 从上式不难看出提升方法的一个十分突出的优点就是，将小波变换分解成几个非常 简单的基本步骤，一旦我们得到小波的正变换，就能轻而易举的写出逆变换过程，只需 要按式( 2 5 8 ) 的相反步骤进行，并将式中的加号变成减号，减号变成加号，便得到提升 小波逆变换公式： f o r j _ n t o 1 f a i 一_ u ( r j ) l _ y ，+ - p ( x ，) ( 2 一o o ) 【- 机乃加( 由此，我们得到了提升方法的有效实现步骤，如图2 - 2 所示。即任何有限长滤波器 都可以从基本小波开始，通过有限数目的预测和更新步骤得到。实现提升方法的关键是 寻找合理的预测函数和更新函数，在实际应用中，通常从小波滤波器系数出发，采样插 值细分的方法，构造预测函数和更新函数。 1 7 湖北大学硕士学位论文 n k y - r 1 k甄 a ) 正变换 y - n k 一 耳亭 b ) 逆变换 图2 - 3 提升方法的变换步骤 由此，可以看出，基于提升方法的第二代小波变换较传统的小波变换有如下优点： ( 1 ) 易理解，易实现； ( 2 ) 效率高，减少了浮点数运算量，速度提升近两倍，正、逆变换简单； ( 3 ) 原位操作，不需要辅助存储空间，所有的计算均可在原位执行，节省大 量内存： ( 4 ) 并行性，无论预测还是更新，操作都是多读单写，一个提升步骤中所有操作都是 并行的，而多个提升步骤间是串行的。 这些优点不仅利于软件编程实现，更利于硬件实现。 2 3 2 整数小波变换 在许多图像处理的应用中，输入的数据都是整数，而且对于存储和编码而言，整数 都比浮点数来得容易。然而在传统的小波变换中，由于小波滤波器的系数都是浮点数， 在执行滤波操作时，即使输入的是整数，得到的结果也是浮点数。然而对于无损压缩来 说，希望将输出的结果重新变成整数。如果直接将所得结果取整，必然造成信息量的损 失，原始数据得不到精确重构，这不符合无损压缩的原则。如果采用按比例放大的方法， 2 小波变换的理论 虽然也能得到整数结果，但数据的动态范围被无形中扩大了，不符合数据压缩的思想， 而且可能造成数值溢出。利用上节的提升方法，稍加改进即可得到整数到整数的小波变 换“1 w li n t e g e r - t o i n t e g e r w a v e l e t t r a n s f o r m ) ，而且原始数据可以完全重构，由于不需要 对变换系数进行量化，因此可实现基于整数加和移位运算的快速算法，也使实现图像无 损压缩成为可能。提升方法根据不同的预测函数和更新函数实现不同的灵活的小波变 换，在其三个步骤中，第一步分裂将数据分为两个部分，不会造成数据由整数变为浮点 数，第二步预测和第三步更新才是造成数据由整数变成浮点数的主要原因。所以，实现 整数小波变换的方法就是在变换过程中对产生的浮点数进行取整，即在预测和更新操作 后各加入取整运算，将生成的浮点数结果重新变成整数。这里的取整操作相当于对原来 的小波滤波器系数做了很小的改动，但这种改动不会影响小波变换的特性，只是使得变 换变为非线性的了。而且，与前面提到的将计算结果直接量化取整后造成信息损失的操 作不同，在提升方法加入取整步骤并不会造成原始数据的无法精确重构，因为取整操作 并没有改变原来的计算结果。也就是说，形如c = a + 【b 】的操作只是使得c 的值为整数， 并没有改变b 的值，只要b 的值不变，就可以通过反变换。a = 叫- b 】，将数据a 再恢复过 来，不会造成信息的损失。 基于提升方法的从整数到整数的小波变换公式为： f o r j = 一1 t o - n 厂讧，y ， 一印胁( a m ) i 弋 r 厂一【p o ，) 】 ( 2 6 1 ) l l + - 【u ( r 川 逆变换公式为： f o r j = - n t o 1 r “u ( r j ) 】 1 jr + f f i p ( , l 川 ( 2 6 2 ) l l 机j o i n ( a j ，r ) 式中，【】为取整运算，其作用是忽略预测和更新操作引入的浮点数，得到整数运算 结果。 1 9 湖北大学硕士学位论文 2 3 3d a u b e c h i e s 9 7 双正交小波滤波器用作提升方法 输入x 图2 - 4d a u b e c h i e s 9 7 双正交小波滤波器提升方法 其中，口一一1 5 8 6 1 3 4 3 4 2 ，芦一- 0 ，0 5 2 9 8 0 1 1 8 ，y 一0 8 8 2 9 1 1 0 7 3 ， 6 - 0 4 4 3 5 0 6 8 5 2 ，k - 1 2 3 0 1 7 4 1 0 6 具体的实现步骤如下所示： s t c p l ：r ( 2 n + 1 ) 一x 。( 2 n + 1 ) + a ( x 。( 2 n ) + x 。( 2 n + 2 ”； ( 2 6 3 ) f o 一3 s2 n + 1 i l + 3 s t e p 2 ：l ，( 2 n ) 一z 。( 2 行) + p o ( 2 n 一1 j + r ( e n + 1 ) ) ；i o 一2 羞2 n j + 2 ( 2 6 4 ) s t e p 3 ：y - ( 2 n + 1 ) 4 y ( 2 n + 1 ) + y ( 1 ，( 2 以) + y ( 2 n + 2 ) ) ；i o 一1 墨2 n + 1 s + 1 ( 2 6 5 ) s t e p 4 ：y ( 2 ，1 ) 一y ( 2 n ) + 6 ( y ( 2 n 一1 ) + y ( 2 n + 1 ) ) ；如一2 s2 n s s t e p 5 ：y ( 2 n + 1 ) 一- k y ( 2 n4 - 1 ) ，i os2 n 4 - 1 f 1 ( 2 - 6 6 ) ( 2 6 7 ) s t e p 6 ：y ( 2 n ) 一y ( 2 n ) k ，i o 2 n i 1 ( 2 6 8 ) 至此我们可以看出，提升算法就是通过预测和更新两个提升环节实现信号的高低频 分离，由于信号有局部相关性，某一点的信号值可以通过其相邻的信号的值，凭借适当 的预测算子预测出来，同时预测出来的误差就是高频的信息，这个过程就是预测环节。 预测环节作用后得到的高频信息又通过更新算子来调整信号的下抽样，借此得到低频信 息，这个过程就是更新环节，在整个的提升算法中，更新环节叫做提于| - ( p r i m a r yl i f t i n g ) ， 而预测环节叫做双提升( d u a ll i f t i n g ) 1 3 1 。由此可知，与第一代小波变换的构造方法不同， 第二代小波变换完全在空域上构造，不像第一代小波变换那样非常依赖于傅立叶变换。 2 0 2 小波变换的理论 提升方式的主要特点有： ( 1 ) 继承了第一代小波的多分辨率的特性； ( 2 ) 不依赖傅立叶变换； ( 3 ) 不占用系统内存； ( 4 ) 反变换很容易从正变换得到，只是改变了数据流的方向和正负号； 对工程应用而一言，提升方案有如下显著的运算优点： ( 1 ) 在位计算：所有的计算均可以在位执行，即计算所得到的结果可以赋给原值，这 样就能在计算时节省大量的内存。 ( 2 ) 高效性：预测部分使用表达式p ，更新部分使用表达式u ，这为编程实现提供了便 利性：而且对反变换而言，只需要将正变换的表达式u 、p 前的符号改为与原来的相反即 可，这样编程时可将正、反过程合并为一个模块来处理，而无需分别编写相应的程序。 湖北大学硕士学位论文 3 图像压缩编码概述 图像压缩编码就是在保证一定重构质量的前提下，以尽量少的比特数来表示图像信 息。第一代图像编码技术是以香农信息论为出发点，用统计概率模型来描述信源，编码 实体是像素或像素块，以消除图像数据相关冗余为目的，以显示器为图像系统的最后环 节。静止图像压缩标准j p e g 的制定及其对多媒体产业的巨大影响有力的证明了第一代 图像压缩编码技术的巨大成功。但是，第一代图像压缩编码技术并未考虑到信息接收者 的主观特性、图像信息的具体含义和重要程度等，只是力图去除数据冗余，这是一种低 层次的编码技术。第二代编码技术则以去除图像内容冗余为目的，考虑人眼作为信息接 收者的特性，是目前一个比较活跃的研究领域1 1 5 】。 本章主要对图像压缩编码进行概述，讨论了图像压缩编码的必要性、可行性和压缩 编码性能评价方法，主要介绍目前广泛应用的图像压缩编码技术，以及一些流行的图像 编码标准。 3 1 图像压缩编码的必要性和可行性 近十几年来，随着多媒体系统和i n t e r n e t 的迅速发展，人们对多媒体业务的需求在 不断增加，对服务质量的要求也越来越高，而其中的图像信息数据量庞大，如果不进行 有效地编码，根本无法满足现有存储和传输的条件和要求。 例如，存储一幅中等大小的图像，5 1 2 x 5 1 2 像素，2 4 位真彩色，需要o 7 5 m b 的 空间，而视频信号通常要每秒钟3 0 帧；一幅标准的分辨率为1 跏m 的3 5 m m 的数字照 片需要1 8 m b 的空间；一秒钟的n t s c 彩色视频需要2 3 m b 的空间。由此可见，无论从 经济还是技术的角度，图像压缩编码都是必要的，可以节省存储空间、c p u 时间和传输 时间。 虽然表示图像需要大量的数据，但这些数据往往都是高度相关的，这些相关性会引 起信息的冗余，因此可以通过去除冗余信息来实现对图像