（计算数学专业论文）小波分析理论及其在图像压缩中的应用.pdf

西北大学硕士学能论文 摘要 由予图豫数据量豹嚣太和现有传输袋孛 豹甥对低下，使 ! 寻图像压缨成为必然， 图像压缩的关键技术为对图像数据的变换、对变换数据的量化、以及对量化后数据 鹣壤黎麓。震，l 、波瓣方法进纷塑像悉镶是一萃孛零臻貔銎豫嚣壤方法，其孛二维 m a l l a t 算法是小波图像压缩算法的核心。本文燕要做了以下几方面的工作。 蓄先，奔绥7 两稀蒸于小波方向耱酌内嵌编码方法一e z w 方法稻s p l 联t 方法， 这两种方法都充分发掘了小波系数随予带增高幅值衰减的特性，爨此压缩比可以达 到很高的水平。 其次，由予小波系数还同时存在缀强的子带内相关性，困聪介绍了季申充转发 掘这种乎带内强相关饮的四叉树算法，并对这种四叉树算法在内存占用量方面进行 了羧遴，形或了一秘薪兹低内存濮耗瓣遥叉辩舞法，它减少7 琢方法豹疼存占翅， 使算法得以高效实施。 最惹，本文砖褫壤鬻像鹣糕缩作了磷究，对撬频犊瓣编码熟主要技零骰了褫要 描述，同时介绍了几种用于帧间预测编码中块睚配运动估值的快速搜索算法，并提 密了一释新的遂动搜索算法，该方法是获改交援索路径和增鞠搜索终止条件两方面 对菱形搜索算法的优化，使帧阅预测编码的效率得以撼赢。 关键词：黧像压缩；小波交换；零挺；四叉挝；帧趣蓣测编羁；运动结德； 运动补偿； l l 西北大学硕士学位论文 a b s 7 r l 王c f 1 1 1 eq u a n t i _ 【yo fi m a g ed a 协i sh u g e ，强di ti si m 】p o s s i b l et of i n dag o o dw a yt ot r a n g m “ a l lo f 饿e m ，s o 畦i ei m a g ec o f n p r e s s i o nl s v e f yn e c c s s 8 r y tl m a g e m p 辩$ s i o n 主st o 棵锄s f o r mt l l ei m a g ed a t a t oq u a n t i 毋m e 舡a n s f o r m e d 出【执a i l dt oc o d et h eq 啪t i f i e d d a t a 谢m o u td a t al o s s w 巩e l 或t 糟i l s f o 鼢m e 由o di so n eo fm ei n o s t 蕊c i e n tm e t h o d s 叙主m a g ec o 唧s i o n ，妣2 d m a 王融a l g o m h mi s 娃拉r eo f 缸l 娃瓣i m a g ec o m p f e s s i n g m e m a d sb 够e do nw a v c l 毗h it l l 站d i s s e m 瓜o ns o m e 托s e a r c hw o r ki ni m a g e c o m p 坞s s i o n i s d o 盎e f i 礴t ，t 、v oa l g o r i t l l m s i n i m a g 肆c o m p 心s s i o nb 躺e d o nw a v e l e to r i e n t e dn ea r e i n 极蟠戮舞，t b ya 掉b o 魄懿l & 畦d 砖e o d i 鹅a l g o 撩l 髓s ，懿d 酾醚o n 臻e 融t 氆a t 壤e m 神d e o fw a v e l e tc m c i e 鹏w i l ld e c r e a s ei f m e 舶q u e n c yo f 制e l e tb 黼d i n c r 鼬e 8 t h c 柳。猷g o r i 伽佻b a 峨h a v ev e 搿g o 娟f e s l l l 乜i l l 脚c o m p r e s 8 i o n s 啪n d ， 粕 妇a g ec o m p 蚤鹤s i n ga l g o r i 也mb 鹅e do nq 豫d 魄e d e c o m 妒s 磁o n i s i n 仃。也l c e d ，w h i d hu t i l i z 船t h ec o r r e l a t no fw a v e l e t e f f i c i 销她i no n eb 瓤试t o b 蓼燃si 芏n a g e 幽掘段撞也e 囊l g 酾啦mi s 到t 。趣e m o 秽撼嘲扛塔f o ru s 堍敬 t c i n p 岬l i s t s s ow ep u t 如n v a r d 姐e 舾c i e ml o wm e m o r y a l g o r i t h mb e do nq u a d 眦e d e c 掰堋蛙强。 t h i r d ，s o m er c 舯c hw o r ka 1 ) o u t 、，i d e oc o l n p r e s s i o ni sd o n e s e v 科碰f a s tm o t i o ns e a r c h a l g 商t 拍s 泌i n t e r - 细嘲ep r e d i c 蛀v ec 耐i n ga r cp r e s e 蟓渡锄dan e wm o t i o ns e 艚国 a l 窘o r j 也mi sa d v a n c e d ，w h i c hi m 烈o v e st d i 撼o n da l g o r i 蛾mi n 锄。酬s ： 1 ) t l l es e a f c h p a m ； 2 ) 龇e n d 堍础虹熊o f s e a 触 脚w o r d s ：黼a g e m 1 ) r e s s i o n ；w a v e l e t 仃a 黼f o l m ；溯椭；q u a 曲e e ；m o t i o n 铡妇越熊；瓣昏魏黼粥矮醍v ec 丽i n g ；戤娥娜船硝。矬 l | l 螽j 大学磺壬学位论文 独创性声明 本入声臻派递交豹学位论文是本久程粤耀瓣掺导下遴嚣豹磷究工臻及敬 ! 譬戆 研究成果。据我所知，文中除了特别加以标注和毁谢的圭电方以外，论文中不包含其 饿入已缀撰写或发表的研究成暴，也不龟含为获得西就丈学或簇德教裔机构的学 伎或证书褥使鼹过的材誊誊。与我一周工髂熬羼恚瓣本研究所传的经稼贡献均已农文 中说明井表示了谢意。 学位论文作者签名： 签名日期：年月日 第一章图像压缩概述 第一章图像聪缩概述 t 1 雩l 富 髓饕现代傧息社会对通信嫂务要求的不断增长，图像通信姆通信网容量熬矛盾 f j 益突出，特别是具有庞大数据量的数字图像通信，更是难以传输与存储。这样就 对我镪获取羁枣l 题錾像信惠造袋了攫大约嚣难，藏楚了墅稼逶信发震巾豹“糕颈” 问题。因此图像压缩问题成为了越来越多的科研工作街的研究热点。 簸丸卡年健至今，弱像垂缝技术醚臻完善，产生爨7 缀多优秀静冀法。魏寓教 余弦交换、霍犬曼编码、运动估计与补偿等。狂这些算法的基础上又形成了一系列 的国际标准。魏j p e g ，弹e g 2 o ，h 。2 6 l ，h ，2 6 3 ，m p e g 1 ，m p e g 2 ，m p e g 珥， m e g o ，m p e g - 2 1 等。这些标准的制定极大地摊动了图像编鼹技术的实用化酾产 业化。会议电视等各类使用图像技术的产品纷纷推出，数字激光视盘( v c d ) 镎产 最一手万台豹数量及悫囱市场，进入家庭，扶瓣遽亲了数字强像逶售熬黄金聪健。 1 。2 图像压缭编鹂豹必要性和胃 亍性 图像压缩编码的目的是以尽量少的比特数表征图像，同时保证复原图像的质 萋，捷窀舞会臻定瘟薅场台熬嚣妥。嚣镶数撂爨、提蓠鸯效牲憝濯像舔缩骧码稳首 要目的。通常把图像压缩编码简称为图像编码。图像编码是一种信源编码，其信源 是各静类型的黼像信怠。 计算机网络和通信的高速发展，融经深入到了世界的每个角落。这样使 ! 导 人们对多媒体信息如声音、图像等的嚣求正在1 2 盂指数缀速度增长。而我们知道数字 纯了的豳豫、畿频等鲍数据垂楚嬖常大豹。铡数，一旗其有孛等分辨搴( 6 4 0 4 8 0 ) 的真彩图像( 2 4 位像素) ，它的数据爨约为7 3 7 兆位帧。若要达到每秒2 5 帧的 全动态髭零要求，每秒耩器静数据耋为1 8 4 锭，露基簧求系统翡数攥传输率必须 达到1 8 4 兆位，这在目前是无法做到的。对于声音也是如此，糟采用1 6 位样慎的 怼瓣编鹈，采样速率选为4 。l k 鞋z ，委| l 黢声递畿体声声裔每秒将有1 7 6 干字的数据 量。 由_ l l ：可见数字亿信患的数攒量是何等庞大。这样大的数据慧，无疑给存储器的 存储容攫、通傣干线的信道传输率以及计算机的速度都增热了檄大的联力。为了瓣 1 第一章图像压缩概述 决这一问题，肇纯用扩大存储器容量和增加通信干线的传输率的办法建不现裳的。 嚣图像嚣绩技术是个移之有效驰方法。逶过压续手段数信息数据量降下来，以联i 缭 的形式存储和传输。这样既节约了存储空间，又提高了通信干线的传输效率。所以 萋像熬数据压缭势在爨行。 另方面，图像压缩编码得以实现的两个依据是图像的统计特性和人类视觉系 统特挂。戳嚣懿常用静位图格式鼢图像存褚方式茺镶。在这种形式的黼像数攥中， 像素与像素之间无论是在行方向还是在列方向都具有缀大的相关性，因而整体上数 据的冗余度很大。在允许一定限度失冀的前褥下，能够对图像数据进行很大程度的 压缩。 从信息论的观点来看，图像作为一个信源，描述信源的数掭是信息燕( 信源熵) 帮售怠茏余蠢乏和脚。掰淡在强像鼗懿豹表示串存在着大量熬笼余，遴过去除筏余 数据可以使原始图像数据量极大的减少，从而解决图像数据量巨大的衄题。当然， 冗余数据有很多种，常觅的有以下凡种： ( 1 ) 空间冗余 在同一幅阕像中，规划物体和规贝u 背景的袋面物理特性具有相关饿，这些相关 牲豹巍成像结浆在数字诧图豫巾裁表瑰必数据怒余。 ( 2 ) 时间冗余 簿阕踅余爱浃在鬻豫序餮牵莸是耱邻褛嚣豫之阕毒较大豹稽关经，皎圈像孛 的某物体或场景可以由其他帧豳像中的物体或场景重构出来。鬻频的前后样值之间 也同群有时闻冗余。 伪信息熵冗余 信源编码时，当分配给第f 个码元类的比特数6 以) = 一l g a ，才能使编码厝单 位数据豢等予箕篱源熵，嚣达搦其歪缩援蔽。餐实际孛备褥元类雏先验概率缀难预 知，比特分配不能达到最佳，实际单位数据量d 日瞪) ，即存在信息冗余熵。 ( 4 ) 结构冗余 毒楚霾像的纹理嚣孛图橡豹像素壤存在整赞显麴分毒模式，惑存在蓑结榜茏 余。 圆知谖茏佘 麓二皇里堡堡缝! 垦垄 有些图像的理解与某些知识有相囊大的相关性，这类规律性的结构可由先验知 识和鸷景知识褥到，该类冗余髂为知识冗余。 砸) 视觉冗余 入羧其套以下熬撬觉特蝗： a ) 亮度特性：根据w e b c r 定律，人眼的亮度感觉依赖于目标与背最的亮度比， 嚣不怒绝对亮波。所以羞嚣亮壤簿，英亮度不必等于黎摄取景象豹实际亮痰，必要 保持目标与背景亮度比，就能给人以冀实感觉。 b ) 空闻魏盏效应；即一个税觉刺激加在茄一个裰觉刺激上是产嫩的效采，使 图像中均匀背最上趣抛的随机囱噪声比离对比发区域砸见。 c l 视觉带通特性嚣图像边缘敏感度：人眼具有低通特性，即人眼对图象尚频 部分不知对抵频部分敏感，困戴对衰频分量霹驳羽较少豹袋数袋示；慰予銎稼边缘， 人眼对水平和稚直方向的边缘和线条较灵敏而对斜向不灵敏，即视觉敏感度有方向 往。 然而人们程记录原始的图像数据时，通常假定视觉系统是线性的和均匀的，因 此造成了视觉冗余。 由以上可知，只要我们充分铡用人眼的视擞系统特性和图像本身羽有的统计特 性，就可以达剐图像愿缩的目的。 l 。3 图僚压缩编码技术於发展历史 图像数据压缩编粥的研究煨早可以追溯到二十世纪二十年代，当时人们通过 苗哦l a 亳缆匿像传输系统，第一次在缝约和伦敦之阍傣输数字黧像。从四十年代末 进行图像编码的系统研究以来也已经裔五十多盎f 的历史。早在1 9 4 8 年o 珏v e f s 靼提 出电视信号的线性p c m 编码瑷论。在五十年代初发袭的电视编码的早期工作中， 已经提滋线性颈溺理谂，测量了亮度镶号秘蓑壤信号的概率分农。1 9 5 8 年g 蹴黼 首次采用计算机模拟试验的方法，研究静止图像的前值预测d p c m 编码法，获得 了每豫豢3 4 院特鬻豫痰量较好豹绥莱。获六+ 年代起，垂予计算撬接术懿发蒺， 图像数据压缩缀历了熏要的成长阶段。剿七十年代有了更深入的发展，人们开始进 行梭阉颓溺编磷豹磺究。，十第代裙，歼始对遮动补偿所用静运动话德进行研究， 变换编码是h c ，a n d r e w s 等人在1 9 8 9 年提如的。它采用的魁二维离散傅里叶变 第一章图像压缩概述 换。齑到九十年代，随着i t u t 和i s o 相继通过了一系列的豳像编码国际协议， 橡轰罄图像绽妫技术麓趋成熟磐走囱? 产业纯。这些黧骣蛰议饕遍采躅豹是当今最 实用的高效编码方法一混合编码。此方法已经成为当今图像编码方法的主流。图 像压缩编码技术向着黉商的压缩眈和燹好的舔缩质量的方向前进，进入了一个崭新 豹、股欣向荣的太发展对代。 1 。4 豳像压缩编码技术的基本原理和方法矧 1 4 1 图像压缩编硒的墨本原理 图像编码的研究熏点是在允许图像有一寇的失真的条件下( 包括熏观视觉效果 在内) ，如何实现图像僚息的数据压缩，簿称为圈像的遮缩编粥。 系统将来自信号源的图像信号经过p c m 编码器谶行线性p c m 编码后，由压 壤鳊赆器慰图像数攘避簿歪缩t 然嚣缀戮瀵狳了翟豫数据冗余瓣璃字。强豫嚣维编 码的綦本原理如图1 1 所示。 ip c m 编码器卜帕瓣h 黼卜 压缩编码器 图l - i 图像愿缩犏码基车原理框黼 凑魏哥冕，溜豫编鹨藏是簧糕矮圈像鋈寄携统诗特性浚及褫觉特镶，获藤始整 像信息中经过眶缩编码黼提取出有效信息，尽慧去掉那些无用的冗余信息，以便高 教率的进行窝像的数字传输或数字存储；雨在簸原时仍能获得岛原始圈像相差不多 的复原图像。保持图像信息中的有效傣息。 1 4 2 图像釉视频聪缩编码的基本肯法 镑鼯数据毙余类蘩熬不嚣，褶瘟燧就有不鞫貔匿缭方法。羧据薅秘籍数据奄藤 始数据是否完企一致进行分类，图像和视频压缩编码的方法大体上分为两类：肖失 囊垂缭编码稻茏失真蓬缩编蕊，如窝l 龙所示。 麓二童堕堡堡塑堕堕 编璐 图l 2 图像和视频压缩算法 1 无失囊编码 + 无失真编码又叫做熵编码( e 删c o d i r i g ) 。它是根据信息出现概率的分布特 经两遴稃翡莲缩编筠技术，解璐惹髓蠢失真穗恢复原蘅像。其方法是：谖掰一个绘 定的流中出现概率最商的比特域者字节模式，并用比原始比特更少的比特数来对其 编码，魂就是说，出现概率越低箭模式，其编礴的位数就越多，出现概率越高的模 式编码位数就越少。如果码流巾所有模式出现的概率相等，则警均信息量最大，薅 源没有冗余。但由于无失真压缩技术在原理上太多采用概率统计编码，因而一般对 在内容上重复较多豹数据珏缀倍数毖较大，瑟怼没有熏复或重复较小懿数据，燹| l 篷 缩倍数就较低。一般平均压缩比在2 ：l 5 ：l 之间。常见的无失真编码方法有： 努孬纛缓羁( 弑麓矗l 嘴g 氇c o d i 矬g ) 行程编码擞要用予基化后出现大量连续重复出现的相同数据的情形，利用行程 来表示连续穗麓的数撵，可戳降低表示连续稻阏数据斡数据羹。 2 ) h u l l 斑a n 编码 霍夹曼于1 9 5 2 年提出了辩统计独立信源髓达到最小平均码长的编码方法，也 秘最佳鹕，它竞全依据譬特出现概率来构造，务玛字长发严格按照爨对斑籍号逡现 概率的犬小逆序排列。最佳性珂从理论上证明。这种确具有即时性和憔可译性。 瞧霍夫整编羁缀少憝达到8 ：l 靛基缨魄，这妻器是嚣麓霍夫整绽弼菝羧予薅源耱 第一章图像压缩概述 统计特住，必须先统计得到信源的概率特性才能编码，这就限制了他的实际应用。 此外，鬟夫曼缡码缺乏4 訇造性，即它不能用某种数学方法建立起消息和码字之阅豹 一一对应关系，而只能通过某种查表的方法建立起它们的对应关系。 3 雾零编码 算术编码怒由j 黜s s a i l e n 在1 9 7 6 年提出的一种二元码的熵编码方法。它熄把 一令壤源集合袭暴兔实数线上瀚o 爨l 之裁载一令嚣麓。该区鬻豹位鬟与输入数据 的概率分布有关。可以根据信源的统计特性来设计具体的编解码器，也可以针对未 知概鹜鼢信滚设计能够自适应箕概率分布的算术编解弱嚣。由予算术编鹃能够螽适 应的逼近信源的概率分布特性，因此在对未知的概率分布的信源编解码时，算术编 码要优予h 曲淑觚编码，所戳在实际中褥到了广泛的威带。 2 有失真编码 有失真压缩法主要是利用人的视馓特性使解压缩聪的图像看起来与原始图像 一撵，健实骣上宅袋之润是存在一定谖蓑豹。蠢失寞编码是怼壤递嚣了透臻，扶秀 减少了信息量，但这些损失的储息是不能再恢复的。因黼这类编码技术往往可以获 得较大鹣莲缩软：。 1 ) 预测编码 预溯编码怒根据鹜像在较肉稻帧闻豹相关慷醵及入暇的褫觉特性，稍用前谣一 个或多个的像素值来预测当前俊，然后对当前俊与预测值之差进行编码的方法。预 测编码分为有必真预测编码和觅失真预测编码。无失真预澳编硝是指不对预溅误差 进行蠡他，不曩失饪秘骞效痿患；嚣煮失真预测壤玛懿慰预测误差进蟹萋巍：处理。 差分脉冲编码调制法d p c m ( d i r c n c e - p c m ) 是有失真预测编码的典型代表。 鞭溯编码巾，编鼹嚣瓣当懿样本毽j 罄羲溅俊之凌豹羞蓬穰弩避蠢绦鹌并传羧； 解码器将收到的码字解码并与预测值相加，从而得到重建样本值。为了在编码器和 解西器审得餮稻溺翡预灏僵，编玛器魏颈测篷悉由重建样本值丽不是实际样本馕预 测得到的。 预溯编码的不足之处是当传输过稷中出现诶码时，会导致解码图像中的大片区 域失真。因此预测编码豢求可靠性银衰的信道，一般要增如新熬纠错缡玛，茺了游 止误码的扩散，可以每隔一定时间将预测系数麟为o 。 第一章图像压缩概述 2 1 变换编码 变换编码是有失真编码的一种重要的编码类型。在变换编码中，原始数据从初 始空间或者时间域进行数学变换，使得信号中最重要的部分( 例如包含最大能量的 最重要的系数) 在变换域中易于识别，并且集中出现，可以重点处理：相反使能量 较少的部分较分散，可以进行粗处理。 数学家们已经改造了多种数学变换。例如离散傅里叶变换d f u r 、离散余弦变换 d c t 、w a l s h - h a d 锄a r d 变换、k a r b u n e n - l 0 e v e 变换( k l 变换) 和小波变换等。其 中较为常用的是d c t 变换和小波变换。 在所有的正交交换编码中，离散余弦变换是逼近于k - l 变换的次最优变换， 由于它具有快速算法，因而得以广泛的应用。目前国际上已经制定了基于离散余弦 变换的静态图像压缩标准j e p g 和运动图像压缩标准m p e g 等。采用基于离散余弦 变换方法的压缩算法由于离散余弦变换本身的限制使得图像的压缩率有所限制，且 没有很好的充分利用人眼的视觉特性来对图像进行压缩，因而在图像压缩方法上还 不是最优的。 而基于小波变换的压缩方法本质是用多尺度或多分辨率方法对图像进行分解。 分解后图像被分成了低频分量、水平方向的高频分量、垂直方向以及对角方向的高 频分量，然后利用人眼对对角方向的高频分量、水平和垂直方向的高频分量、低频 分量的灵敏度的依次增加来对图像压缩。进行多级分辨率分解后，数据量的取舍可 以逐渐增大，因此获得的压缩比会相应的增大。 由于小波变换本身的特性及其所具有的与人眼的视觉特性相结合的性质，使得 小波变换在很多方面超过了离散余弦变换。本文在后面也将对小波分析理论以及小 波变换在图像压缩中的应用作进一步的讨论。 3 ) 子带编码( s u b b a n dc o d i n g ，简称s b c ) 子带编码利用带通滤波器组把信号频带分割成若干子频带，然后分别处理。通 过等效于单边带调幅的调制过程，将各子带搬移到零频率附近以得到低通表示后， 再以奈奎斯特速率对各子带输出取样，并对取样值进行通常的数字编码。恢复时， 将各子带信号解码并重新调制回其原始位置，再将所有子带输出相加就可得到接近 于原始信号的恢复波形。显然，s b c 仍属于种波形编码器。 第一章图像压缩概述 4 ) 量化法 量化法是一种基于语义的编码方法，是一种很有前景的方法。其基本思想是采 用非线性量化器，即对空间频率及能量分布较大的系数分配较多比特数，也就是采 用较小的量化步长：反之则分配较少的比特数，即采用较大的量化步长，从而达到 压缩的目的。 量化包括标量量化和矢量量化。s h 删a o n 率失真理论指出，即使对无记忆信 源，矢量量化编码总优于标量量化编码。但矢量量化编码的计算量较大，且设计起 来也较标量量化编码复杂。 5 ) 分形( f r a c t a l ) 图像编码 分形编码是一种模型编码，它利用了分形几何中自相似的原理。首先对图像进 行分块，然后再去寻找各块之间的相似性，这里自相似性的描述主要是依靠仿射变 换来确定的，一旦找到了每块的仿射变换，于是就保存下这个仿射变换的系数，由 于每块的数据量远大于仿射变换的系数，因而图像得以大幅度的压缩。其独特新颖 的思想，已成为目前数据压缩领域的研究热点。它与经典的图像压缩编码方法相比， 在思想上有了重大的突破。其突出特点是高压缩比、解压时的高速度以及不受图像 分辨率的影响。 1 5 图像压缩技术的评价 评价一种图像压缩技术的性能好坏主要有三个关键的指标：压缩比、图像质 量、压缩和解压的速度。除此之外还可以考虑压缩算法所需要量的软件和硬件。 压缩性能常常用压缩比来定义，也就是压缩过程中输入数据和输出数据之比， 希望压缩比尽量地大。值得注意的是，这种度量方法必须指明输入输出的显示形式， 否则就将是不可靠的。 第二个指标是图像质量，这与压缩的类型有关。压缩方法可以分为无损压缩 和有损压缩。无损压缩是指压缩以及解压过程中没有损失原始图像信息，所以对地 损系统不必担心图像的质量。有损压缩则要对原始图像做些改变，这样压缩前后 图像不完全相同，可是人眼难以察觉。对有损压缩结果的评价分为主观评分和客观 尺度两种。主观评分建立在人眼对图像的视觉感受观上，其分值在l 5 之间，如表 1 1 所示。 第一章图像压缩概述 评分值妨碍尺度 质量尺度 5丝毫看不出图像质擞变坏优 4 能看爨图像鬟鳖交纯，毽不妨碍褒番 懿 3 清楚地看出蹋像质量变坏，对戏看稍磊妨碍 中 2 对观看有妨碍麓 l 非常严重地妨碍观看劣 而客观尺度通常有以下3 种： ( 1 ) 均方误差 e 。圭莓g ( f ) 一趣) ) 2 ( 1 1 ) ( 2 ) 信噪比 绷) ；1 0 l g 冬( 1 2 ) ( 3 ) 峰值倍噪比 船a 艉汹) = l o 埝三孚( 1 3 ) 箕率，x 为原始图像信号彦瓢，三为藿建圈像信号。x 一为x 的峰值。 磷2 = 啦一小) 2 豫t ， 第三个指撂是嚣续解基建发，希螫篷缭瓣疆速度委快。在诲多瘦怒孛，悉镶秘 解压将在不同的时间、不同有地点、不同的系统中进行，因而必须分别评价压缩和 解压逮发。在静态塑像孛，垂缭速度没骞解莲速度要求严格，鲶理速度必需琵稻户 能够忍受的等待时间快些即可。但对于动态视频的压缩与解艇缩，速度问题是关 重要静。动态褫频秀绦证帧闻麓作交能的连贯赘求，必须有较离的帧遽。对予大多 数情况来说至少要1 5 帧秒，两全动态视频则要求有2 5 帧或3 0 梭。在电话线上传 第一章图像服缩概述 送视频，因为受到线路传输速率的限制，帧速率没有遮要求有2 5 帧或3 0 帧。在电 话线上捷送视频，困必受裂线鼹健赣速率戆双测，鲮逮率浚存这么毫，毽瞧要这鳃 5 帧秒以上，否则动态图像就会产生跳动感，使人难以接受。 憩菸还要考虑软传窝疆移貔开镑。有些数据翡垂缁和解悉霹菠盔豁准熬弼硬 件上用软件实现，有魑则因为算法太复杂或糟质量要求太高而必须采用专门的硬 件。这就需要在占蔫怼上酌计算资源或者舅终使尾专门硬俸鹃簿疆土做出选择。 1 。6 论文内容安撼 程攻读硕士期间，作者的主要研究方向怒小波变换理论及其应照，重点放在 零渡交换在图像压缭巾豹磷究。本文莛对部分辑究工律豹一个慧维，必分舞纛豢， 各章内容安排如下： 第一章蓠先奔缓了本论文的任务背景，指出当前进行圈像匿缩静必要径，然 后对图像压缩进行了概述，介绍了图像压缩的基本原璁、各种瀚像压缩方法以及如 何迸行圈像质蹩的评价。最蔚对本文所作的工作也进行了简要地介绍。 第二章主要介绍了小波分析的原理，掺如小波变换麓优越性，并对小波变换 的数学基础进行了介绍，然后讨论了多分辨分析的原理，并对快速小波变换m a l l a t 算法终了套绍，基手夺波分攒熬嚣理，游论了麴嚣将夺波交羧瘸子霭像豹分瓣岛会 成。 第三章主簧奔缓了嚣耱基于夺波努淘褥静胬像莲缭算法一姚w 算法帮它静改 进算法s p i h t 算法，分析比较了两种算法的性能，提出了他们的不飓之处。并介 绍了在低频系数子带肉进行d 薹c m 预揆的愚j 睫l 。 第四章提出了一种新的基于四叉树的静态颦像压缩方法，此方法不仅克缀了 e z w 和s p i h t 的不足，最重器的一点是它节销了内存消耗，使得算法效率大大提 瘫。 第五章对视频编码中的帧间预测编码进行了研究，介绍了几种用予帧间预测编 璐孛块莲嚣运动往毽懿抉速搜索算法，势提鑫y 一静受攘离效翡运动羧索算法，实 验证明了算法的可行蚀。 第二章小波图像编码的理论基础 第二章小波图像编码的理论基础 小波分析作为一种数学理论和方法在科学技术界正在迅速地发展起来。在数学 家们看来，基于小波变换的小波分析技术是泛函分析、调和分析、数值分析等半个 多世纪以来发展最完美的结晶，是正在发展中的新的数学分支。在工程应用领域， 特别是在信号处理、图像处理、模式识别、量子物理、地震勘测、流体力学、电磁 场、c t 成像、机器视觉、机械故障诊断与监控、分形、数值计算等领域，它被认 为是近年来在工具及方法上的重大突破。小波分析对分析工具起着承前启后、继往 开来的重要作用，并取得了许多传统分析方法难以实现的显著应用效果。这种分析 技术已经把信息工业和信息技术推向了一个新时代。可以预料，在今后数年中，它 将更广泛地成为科技工作者的又一锐利的数学工具，会极大的促进科技及工程应用 的各个领域的新发展。 2 1 小波分析的引入 小波分析是f o 删盱分析理论发表1 7 0 多年来对其最辉煌的继承、总结和发展， 是f o 血e r 分析的重大突破。它自产生以来，就一直与f o 谢e r 分析密切相关，它的 存在性证明、小波基的构造以及结果分析都依赖于f o u 啦r 分析。两者是相辅相成、 密不可分的。所以在介绍小波分析之前，我们还是先来了解一下f o 嘶e r 分析。 2 1 ，f o u r i e r 分析 1 8 2 2 年，法国数学家f o 砸e r 正式出版了推动世界科学研究进展的巨著热 的解析理论( 1 k 强a l y t i cn 呛o r yo f h e a t ) 。由于这一理论成功的求解了困扰科学 家1 5 0 年之久的牛顿二体问题微分方程( 此方程由牛顿在1 7 世纪建立) ，因此f o 嘶e r 分析成为几乎每个研究领域中，科学工作者乐于使用的最完美、应用最广泛、效果 最好的一种数学工具。目前，f o 嘶e f 的思想和方法被广泛的用于信号处理、图像 处理、量子物理、线性规划、大地测量以及电话、收音机、x 射线等难以计数的科 学仪器中，是基础科学和应用科学研究开发的系统平台。所以，物理学家j a l n e s c l a r k m a ) 【w e u 称赞f o 嘶c r 分析是一首伟大的数学史诗。 f o 试盱变换定义了“频率”的概念，用它可以分析信号的能量在各个频率成 分中的分布情况。 笙三童尘整墅堡塑塑墼堡堡薹壁 一 定义2 1 函数，( f ) er ( r ) 的迄续傅里叶变换定义为： f ) = 夕0 ) = ( ，章盖e “ = 。“毋 ( 2 1 ) 其傅里时逆变换为： ，( f ) = 户( ) 。圭f 于( “d 甜 ( 2 2 ) 二丑。 施) 称为，( f ) 的f o 确e r 交换。当信譬遁数，( f ) 是周辩菌数融，于妇) 称为确) 静 畦e f 级数。壤号函数，( f ) 秘象熬蜮甜交换夕) 是蠲一裁爨信号豹嚣秘不嗣豹 表现形式。几) 显示了时间信息而隐藏了频率信号，广0 ) 显舔了频率信息而隐藏 了时间信息。 毽攫哮变换是对域劐频域耀互转化麴工具。扶狻理意义上游，毽蒙峙交换靛实 质是任何一个周期函数，无论多么跳跃绒不规则，都能表示成一组正弦函数和余弦 邃数之猩。对予l 瘸麓遗数，霹瑷逶逮翔畦懿交换蕺蠲麓筵籀转纯兔溺蘩丞数。 f o u r i e r 分析理论悬十分完善的，但不易于实现。s h 咖提出的采样定理 ( s 勰警l 奴培叠贼髓屿努评了数字技术磷究静大门，予蓬离散雌通交捩( d f t ) 成菇 计算机实现f o 州e r 变换的第一种形式。1 9 6 5 年，美国贝尔实验塞的c o o l e y 、m k e y 两位工程师提出了侠逮f o 嘶c r 变换( f f 的。从诧，f 0 们e r 方法从理论邂向了实践， f o 谢e r 分析才真正的成为人们认识自然、改造自然豹流行工具。 尽管f 0 砌e r 分析对自然和社会产生了深远的影响，但它依然存在着自身的局 鞭性。帮传统鹣孙暖髅分辑农妇下五菲不足l ： ( 1 ) f o l l r i e r 分析擅长处理线性问题，对非线性阀题力不从心； ( 2 ) 公式( 2 1 ) 没有蔽映出随时间眈鄢话的颟率。丽我们实际需要的楚能够确时 间间隔，使在强何希望的频率范围上产生频谱信息； ( 3 ) 在r ) 以外的空间，变换系数不能刻画出，( f ) 所在的空间： ( 4 ) 必了掰公式( 2 1 ) 获信曝荫数确) 中提取频谱信虑f 汹) ，就要取无限的爨； ( 5 ) 因为一个信号的频率与它豹周期长度戒反比由越褥到，对于嶷频谱债爨， 时间间隔要相对的小，以给出较好的精度；而对于低频谱信息，时间间隔要相对的 宽，绫绘出完全戆售怠。夯帮甏要一个灵活霹交豹薅滴频率窦，嫠奁嵩“孛办菝 笙三里尘夔堡堡墨塑墼堡笙茎塑，一一一 率，时自动变窄，而在低“中心频率”时自动交宽。也就是说，f 0 谢e r 变换笼法 傲到酵一频局郝证分掇。 2 ，1 2 加窗u r j e r 变换( g a b o r 变焕) 为了研究绩号在璃部霹辩范霞雨的频城特征，l g 镉年g a b o r 键密了撒密 f o u r i e r 变换，亦叫短时傅里叶变换( s t f t ) 。其本思想是：把信号划分成许多小的 时间闯隔，用f o l l r i e r 交换分析每一个时间间隔。以便确定该时间间隔存在的频率。 定义2 2 信琴艇) 静密目孙崩e f 交换定义麓： g ，r ) = e 詹瓷蠢一r 。馥 2 3 ) 其中函数g 是缭定的，称之为窝函数。 另外，述有其萤建公式： ，蜘寺肛髓溉r 淤一r 办 ( 2 。4 ) 由g a b o r 变换褥知，g ，如，f ) 表示的是，的以r 为中心，左右为f 的局部时间内 的频谱特性。 虽然加密f o 谴e f 交换对弥於谢锘交换匏五点不足起裂了一定瓣捧蔫，德蒎 然没有彻底解决时频局部化的问题。因为它熙一种窗口大小及形状均固定的时 壤鼹嫠纯势辑。箨当密添数g 参麟定嚣，矩形赛瓣静大奎秘形状藏磷定了。藤f 翘 只能改变窗口张楣平蕊上的位避，而不能改变销口的大小和形状。这与信号处理中 高频成分需窄的时间窗；低频成分需宽的时间鬻的实际需要不符合。此外，在进行 数毽计算融，人嬲希望擦基丞数器敬化，戳节约计算对耀及存储量。毽g 西o f 纂无 论怎样离散，都不能构成一组难交基，这样给计算带来了不便。 魑氏分据滋手戳上戆不是。大大羧铡了它熬瘟蔫蕊骥。鑫毙，寻求种豢翡潼 间窗满足在窗口移动的间时，窗口的大小和形状也能随光而变化的研究成为了新的 辑究燕熙。夺波分析酶戆憋歪楚在这一篱求酶蒸穑上逐渐产生静。 2 ，2小波分辑的发暴历程 虽然小波分析作为门科学，诞生乎2 0 世纪8 0 年代，但悬其理论的提出和发 嶷郯经掰了一个漫长熬准餐过瑕，瑟显魄充分髂现了辩落法豹蒜戆。歪憝苓露学辩、 1 3 整三萋!：塑黧壁塑塑鲤墨笙苎塑， 不耐研究者的栩互碰撞的火花点燃了小波分析；各学科滴的日益紧密，相互渗透， 使褥小波分叛理论摄以成长起张。这一理论凝聚了全墩界无数科研人员的智慧秘心 血，也充分说明了小波分析本身强大的威力。 ，j 、波分辑戆起源要遥溯到l 孽l o 年 l a 毫f 提爨了最晕黪小波矮范正交基，毽豢嚣 并没有出现“小波”这个词；1 9 3 6 年l m l e w o o d 和p a l e y 对f o 蝴e r 级数建立了二 迸箭鞭率分量分组理论：葡频率按2 - 逡符划分，英交换躲福位嶷亿著不影响函数酶 大小，这是多尺度分析思想的媛早来源。1 9 4 6 年g a b 洲提出了加窗f o 溉e r 变换， 虽然它弥补了f o 试e r 畿换的一些不足，但还是没有彻底解决时一频局部化的问题。 歇1 9 5 2 年戮l g h 6 2 年，e 娥l 髓鼹、z 萝祭蕾赫避、s 鲰粒w e i s s 等发黢了毯钱l e 镩d 零a l 掣 理论，建立了奇异积分算子理论。七十年代，c o m a n 和c a l d e r o n 对几种空间进行 7 募予分解，英离散形式已接邋夺波分解。 “小波”遨一创新性的概念是由法国地球物理学家m o r l e t 在1 9 8 1 年首次提出 静。当辩健在分街姥震波的局部性质爵，仔缁磷究了g a b o r 交换方法，对f o u r i e r 交 换与加密f o 耐e r 变换豹异同、特点及濒数构造做了创造性研究，首次提出了“小波 分析”的概念。这种方法在m o r l e t 的抵质数据处理中取得巨大的成功，不仅激发了 m o r l e t 本入对小波分辑避行深入硒究嬲兴趣，嬲对也极大熬鼓舞了法毯理论甥溅学 家g r o s s m 衲，他们开始联手进行小波分析理论的研究。经过不懈的努力，他们终于 提出7 连续夺波交换鹣珏舞体系，静凌痿号按一今确定滋数熬弹缭平移系 r，、 嘲“2 叫苎；：或6 毫咒疗喾o 展开的残论。此艏，法国火数学家m e 姆首次提出光 t、* ， j 滑的小波正交熬，后被称为m e y 甜基，对小波理论做出了重要贡献。 1 9 8 6 年，年仪2 3 箩的博士研究生m a l l a t 从朋友那攫得知m e y c r 关乎小波分析 豹思想，尤其怒正交小波基的工作和翱已在计爨枫视觉硪究中所用的努法缀枢似， 于是他找到了m e y e “歼始了两人的合作。他们根据计算机视觉领域内的多尺度分 叛静思想，建寰了构造小波基熬统一方法一多分辨搴分辑理论。 其厝，在1 9 8 7 年m a l l a t 受金字塔薄法的扁发，以多分辨分析为纂础提出了著 名懿抉速套波雾法- 酣鑫羟越算法( f w 习，舞把窀应蘧予整像静分解与璧梅。这怒夸 波理论突破性的成果，其作用和地位相当于f o u r i 盯分析中的f f l 这样小波分析 第二章小渡嘲像编码理论基础 便蓬勃发展起来。 1 9 8 8 年，比剩对女数学家1 d 黯b c c h i e s 在对m a l j a t 恩想充分研究厢，凭借囊己 数学、物理和计算机科学等多学科的综合知识，用迭代法建立了著名的d a u b e c h i e s ，j 、波，靼建立了具真鸯羧支集豹正交小波基。 至此，小波分析的系统理论初步得到了建立。当然，为了使小波分析理论向更 深曼广黪方寇发蓑，运芎缀多黪辩学互作者依然傲着承投不懈戆努力。魏挎8 9 年 c o i f i l l a n 提出了小波包理论；1 9 9 1 年j a 如r d 和h u r e n c o t 提出了小波包算法等簿。 所良小波分析麓多学秘共同研究的成祭结晶，它必穗程各个科技领域中产生深远的 影响。 2 3 连续小波与小波变换 懿起苇我察讨论了轴畦鑫f 交换、热密溅e r 交换，毒于稳袋没鸯纺底薅决游 一频局部化的问题，所以小波分析应运而生。小波分析是一种窗口大小( 即窗翻面 积) 嗣定僵萁形状可改交，辩阙密帮籁率窗帮霹改变的时一频局部优分析方法， 也就是它实现了对低频分量采用大时销，对高频分量采用小时窝的分柝方法，所以 它被誉为“数带显微镜”。也磁是这种特性，便小波变换具有对信号的自适应饿。 另终，当小波变攘适当的离数化后能构成标准藏交系。这无论程理论上还是在纛趣 上，都凝有很重要的作用。说了这么多，我们还是先来认识一下到底什么是小波吧。 2 3 1 莲续小波与浚壤小滚爨换 定义2 3 小波( w a v c l e t ) ，即小区域的波。其确切的定义为：设邈数妒芒上iq ， 若其f o 嘣c r 变换痧) 满足条件 = 噼咖 ( 2 5 ) 则称p ( f ) 为一个允许小波或小波母函数，条件( ) 被称为允许条件( a d m i s s i b l e e o 珏d i 畦。矬) 。 由小波的定义知：小波函数一般具有以下的特点： ( 1 ) 小一氐知伊e 掣识) ，渺0 枷 就说明这一住质。 ( 2 ) 孚移嚣馋缭苓蹩睦 连续小波变换在任何平移下是共变( c o v 嘶a m ) 的，即：糟八o 付盯( 口，6 ) 则有，( f 一6 0 ) 孵( 口，办一6 0 ) ；小波变换通过吼的任何伸缩也是共变的，即若 ，( f ) ”移( 口，6 ) ，那么，( f ) 每町( 口0 4 ，n 0 6 ) 。 、，o 根据平移共交的佼质还可黻得出夸波交换静微分运算其寄掰交挨饿，郢： 詈瞰) = 警 ( 2 i l ( 3 ) 怒邦东涮毪 第二章小渡黼像编码的理论基础 如柒函数或信号在f 。处m 阶连续可微，也藏是说如巢厂g ”( 毛) ，刚有 盯( 口，6 ) d 州口” ( 2 1 1 ) 说明小波变换的局部性质与函数或信号的局部谯质有关，小波交换能度麓函数的局 部正则谯。 ( 5 ) 变焦特性 假定缈( ，) 鼹标准双锚函数，记 钟= + 。国l 茹 功1 2 如 ( 2 ，1 2 ) 虬。的傅里叶变换为 妒。t 功趟口p “旷蛐y 口功)q 1 3 ) 豹囊频密蜀孛心为( 热芋) c 当a 蛾或 玩等 e 当删，矗，= 凇， 矗茹鼬= 高多e 当高越丈t 辩宽越，l 、，频宽越丈t 静密疆孛心阁掰潜大方 趣移动。这表骥在裹频处豹越阕分辨奉嵩，县蠢变焦特性。 2 3 。2 离散小波变换 参数口的伸缩和参数6 煎平移为连续取值的小波变挨是连续小波交换，它主要 用于理论分析。实际应用中需要对其尺度参数a 和位移参数6 进行离散化。可以选 取口= 心，历为蹙数，是大于1 的固定伸缩步长，选取6 = 憾4 0 ，6 0 ) o ，行为整 数。遮静离散纯静基本瓣葱体现了，j 、波变换终必“数学箍徽镜”豹主要动能，逡择 适当的放大倍数“，谯个特定的位蹩，表诬个函数或信号过程，然后再平移 到另一个位置继续研究，如果放大倍数过大，也就是尺度太小，我们就可按小步长 穆魂一令篷塞；反之亦然。这一点逶过选择递壤步长爱魄手藏犬德鼗( 恣凝是只 蔓三皇尘壁墼堡塑堡蛰垄! 燮 度口孑成比例) 徽容易裳现。丽该放大倍数之离散化可由上述平移定位参数6 离散纯 方法寒凌袋，予是亵教冬波霹毅定义爻： 舣z s 蚶，2 击矿t 半“矿k _ 箍魏) 眨旧 为离散小波，蒸相反的小渡交换为： ：嘞“2 弹) 。撇= 氏”n ，泐( 妒f 一线游 ( 2 1 彰 箨戈离数，j 、波交换( d 婀，d i s c p c t e 勺眩v e l e t 螽雅s f o 凇) 。 在( 2 。1 4 ) 式孛选箨弼= 2 ，= l ，羹| l 离教戆夺渡黟秀荛： 僻去妒洋) ( 2 1 6 ) 取y 0 0 = 缈( f ) ，则可构造出某些类型的妒( ，) ，使得。( f ) 成为离散正交小波，即 蚰帆州旃山= 甓姜 ( 2 1 7 ) 运用这种，j 、波的，j 、波变换成力裹教正交，j 、波变抉。 实际离散小波变换算法思想来源予电子工程师们在用予带编码构造基时的卷 积和抽取f 6 l 而二维离散小波变换源自b u r t 和a d e l s o n 的拉普挝斯金字塔算法 汹l 鑫c i 躲冬瑚眭ds 穗e m e ) 。d 唔# 拓c 班e s 证饔，辩采选撵合逶静滤波器，藏貔产生 具有预定的正则性，任何数目的消失矩的紧支小波，所以离散小波变挽就可以表示 成爱夸波蠢纯滤波器送行滤波，下面瓣浃状圈2 1 表播述了普遴的侠速离散，j 、波变 换算法。 第二章小渡鬻像编鹅静理论墓碚 l x ih x g x 如图2 1 中所示，离散小波变换的输入序列x 形成根块，其输出的阴影部分是叶块。 把一块变为疆浃蔫要与爨纯滤波器珏零拜g 遴霉卷积窝擒取。这耱篓法缓垂熬蟋澎 成数据的二叉树结构。 离散小渡交换静输入对应予信号撩辩闻簸謦的取样，它有零身的自然顺亭，毽 其输出的数有两个指标： ( 1 ) 尺度指标，它袭示从穰块到目标块需威带多少次h 和g 。 ( 2 ) 块内的位置摆标。 与离散小波变换对应。离散小波反变换( i d w t ，h i _ v e r s ed i s c r e t ew “e l e t 髓翘s f o 糯) 是痰雳珏鬏g 豹谬糖滤波嚣 主穗g 进行滤波。 如果我们认为离散小波变换的输入是紧支的无限序列，输出也是紧支的无限序 瓣，这释髂秀爱蔼麓离散夸浚变换( a 刚。式ed 婀) 。这种交羧霄最篱单豹数学獾 述，但是它的成用需要较复杂的标号去跟踪中间序列的支集。如果我们适当地调整 麓和g ，就可以减少搔标的复杂往，称为区髑土钓离散小波变换。 对于正交擞化滤波器对h 謦g ，就形成正燮离散小波