（信号与信息处理专业论文）基于小波分析的分形图像压缩.pdf

山东大学硕士学位论文 中文摘要 二十多年前，分形图像压缩技术首次被应用于计算机图形学 中。19 8 1 年，约翰哈奇森( j o h nh u t c h i n s o n ) 改进了迭代函数系 统i f s 的数学理论，分形图像压缩的这新方法即来源于此。迈克 尔巴恩斯利( m i c h a e lb a r n s l e y ) 是提出分形图像压缩编码流程的 第一人，但是他所提出的方法却是分形图像压缩中最简单基本的算 法，而且这一算法需要人工分部实现。巴恩斯利的博士研究生，简 库恩( j a c q u a i n ) ，首次提出一种能自动完成运行的分形图像压缩算 法；后来，弗歇尔( y u v a lf i s h e r ) 更为详尽的描述了全自动编码 过程。根据弗歇尔的方法，压缩图像之前要先给待压缩图像分块， 根据一定规则，把图像所有可能划出的小块分为定义域块d 和值域 块r 。进一步说，这一分形图像压缩的算法要求对所划分出的每一 个值域块在定义域块库中寻找到其最佳的匹配块。这一理论原来以 迭代函数系统i f s 为基础，现在以后来发展出的局部迭代函数系 统p i f s 为基础。更确切地讲，这一压缩编码过程要求寻找每一个 可匹配定义域块的大小并确定其位置后，求出相应定义域块的仿射 变换系数。图像解码时，则需要对编码中用到的定义域块进行一系 列的仿射变换，每一定义域块经过仿射变换后的不动点图像可视为 由其恢复的值域块。这一个个值域块就是整幅解码图像的一部分， 而它们的全体则形成整幅解码图像。 本文提出了一种基于小波变换的分形图像压缩算法。传统的空 间域分形图像编码被扩展应用到小波域中，这就可以通过适当的仿 射变换充分利用小波树间的相似性。基于小波的分形图像压缩是在 小波域中用有效的块分类方法，将多分辨率分析理论与迭代函数系 统理论有机地结合在了一起。用分形方法压缩原始图像在之前，先 将其转换到小波域，在小波域中将图像分为定义域块和值域块。通 过一定的加速块分类方法，利用小波树之间的相似性，可以有效地 降低算法的计算复杂度，并大大缩短编码时间。同时，这种混合图 1 i i 山东大学硕士学位论文 像压缩算法可以采用误差图像补偿的方法获得较高的峰值信嗓比， 从而获得较好的编码效果，这是此方法的主要优点。这一在小波域 中进行块分类的方法已得到了大量实验的证明，并将在分形图像压 缩的研究中发挥其巨大的潜力。 关键字：分形编码，小波变换，图像压缩，块分类 i v 山东大学硕士学位论文 a b s t r a c t s a b o u tt w e n t y y e a sa g o f r a c t a l i m a g ec o m p r e s s i o nt e c h n i q u e s w e r ei n t r o d u c e di n c o m p u t e rg r a p h i c s t h e s en e wi d e a sc a m ef r o ma m a t h e m a t i c a lt h e o r yc a l l e d i t e r a t e df u n c t i o ns y s t e m ( i f s ) t h a th a d b e e nd e v e l o p e di n19 81 b yj o h nh u t c h i n s o n m i c h a e lb a r n s l e yist h e f i r s tt oi n t r o d u c ea ne n c o d i n gp r o c e s sf o rf r a c t a li m a g ec o m p r e s s i o n b u tw h a th eh a dp r o v i d e di s o n l y a p r i m i t i v ea l g o r i t h mt h a t n e e d s h u m a n i n t e r a c t i o n j a c q u a i n ，o n eo fb a r n s l e y sp h ds t u d e n t s ，w a st h e f i r s tt op u b l i s ha na u t o m a t e df r a c t a li m a g ec o m p r e s s i o ns c h e m e ，a n d y u v a lf i s h e rd e s c r i b e dan e w e rs c h e m ef o ra u t o m a t e d e n c o d i n g p r o c e s si nd e t a i l t oc o m p r e s sa ni m a g ea c c o r d i n gt o y u v a lf i s h e r s s c h e m e ，a n yg i v e ni m a g e ，w h i c hi s t ob ec o m p r e s s e d ，i sd i v i d e di n t o s u b b l o c k s t h e nr a n g eb l o c k sa n dd o m a i nb l o c k sa r et ob ei d e n t i f i e d f r o ma l lt h ep o s s i b l es u b d i v i s i o n so ft h ei m a g e 。i no t h e rw o r d s ，t h e f r a c t a li m a g ec o m pr e s s i o ns c h e m er e q u i r e st of i n dm a t c h i n gr a n g e b l o c k st od o m a i nb l o c k sf r o ma 1 1t h ep o s s i b l ed i v i s i o no fa ni m a g e i n t os u b b l o c k s t h et h e o r yu s e dt ob eb a s e do ni f s ，a n dn o wp i f s i nf r a c t a l i m a g ec o m p r e s s i o n ，e n c o d i n gp r o c e s s f o ra n i m a g e i st o f i n das e to fc o e f f i c i e n t sf o ras e to fa f f i n et r a n s f o r m a t i o n st o g e t h e r w i t hi n f o r m a t i o nt od e f i n et h ed o m a i nb l o c k s m o r es p e c i f i c a l l y ，t h e p r o c e s s i st of i n dc o e f f i c i e n tsf o re a c ha f f i n et r a n s f o r m a t i o nt h a t c o r r e s p o n d st o e a c hd o m a i nb l o c ka sw e l la st of i n dt h es i z e sa n d r e f e r e n c ec o o r d i n a t e so fe a c hd o m a i nb l o c k d u r i n gt h ed e c o d i n g p r o c e s st h es e to f a f f i n et r a n s f o r m a t i o na p p l i e dt ot h ed o m a i nb l o c k s t h ef i x e d p o i n t o ft h er e c u r s i v e o p e r a t i o n o fe a c ha f f i n e t r a n s f o r m a t i o na p p l i e dt oi t sc o r r e s p o n d i n gd o m a i nb l o c ki sc a l l e da r a n g e b l o c k ，ar a n g eb l o c kf o r m sp a r to ft h e o r i g i n a li m a g e a n d c o l l e c t i o no fa l lt h er a n g eb l o c k sf o r m st h eo r i g i n a lv i s u a lf o r mo f v 山东大学硕士学位论文 t h ei m a g eb e c a u s et h es e to ft h er a n g eb l o c k si s ap a r t i t i o no fag i v e n i m a g e i nt h i sp a p e r ，aw a v e l e t b a s e df r a c t a li m a g ec o d i n ga l g or i t h mi s p r o p o s e d t h ec o n v e n t i o n a lf r a c t a li m a g ec o d i n gi ns p a t i a ld o m a i ni s e x t e n d e dt ow a v e l e td o m a i n b yt a k i n ga d v a n t a g e o ft h e s e l f s i m i l a r i t i e s a m o n g d i f f e r e n tw a v e l e ts u b t r e es t h r o u g hpr o p e r a f f i n et r a n s f o r m a t i o n t h i sm e t h o di sb a s e do nt h ec o m b i n a t i o no ft h e t h e o r yo fm u l t i - r e s o l u t i o na n a l y s i sw i t hi t e r a t e df u n c t i o ns y s t e m sb y i n t r o d u c i n g s o m ee f f e c t i v eb l o c k c l a s s i f i c a t i o ns c h e m e s t h e o r i g i n a li m a g e i sf i r s tt r a n s f or m e di n t ow a v e l e td o m a i ni nw h i c h f r a c t a l c o m p r e s s i o n a n da r i t h m e t i c c o d i n g a r e p er f o r m e d b y c l a s s i f y i n g db l o c k sa n drb l o c k sc h os e ni nt h i s d o m a i n ，t h e a p p r o a c h c a ns i g n i f i c a n t l yr e d u c et h e c o m p u t a t i o nc o m p l e x i t y a n d e n c o d i n gt i m e m e a n w h i l e ，t h eh y b r i di m a g ec o m p r e s s i o na l g o r i t h m o b t a i n sm u c hb e t t e rc o d i n gp e r f o r m a n c ei nt e r m so fp s n rw i t he r r o r m o d i f i c a t i o n t h isi st h em a i na d v a n t a g eo ft h i s m e t h o d as e to f e x p e r i m e n t s a n ds i m u l a t i o n ss h o wt h e p o t e n t i a l s o f u s i n g t h e s e c l a s s i f i e a t i o n t e c h n i q u e s i nw a v e l e td o m a i nf o r f u r t h e r i m p r o v e m e n t s k e y w o r d s ：f r a c t a l c o d i n g ，w a v e l e tt r a n s f o r m ，i m a g ec o m p r e s s i o n ， b i o c kc l a s s j f i c a t i o n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：这堇纽日期： 趁2 垒：主：2 9 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：独耋b 导师签名：窆2 窒丝日期：幽 山东大学硕士学位论文 第一章引言 1 1 课题的目的和意义 近二十年来，科学技术取得了飞速的发展。由计算机技术所带 来的信息革命使人类由工业化的社会进入到了信息化的社会。多媒 体技术和i n t e r n e t 互连网技术的广泛应用加速了全球高速公路的建 设，基于网络的多媒体数据传输正改变着人类的生活方式。 科学实验表明，人类从外界获取的知识之中，有8 0 以上都是 通过视觉感知获取的。眼睛获取的是图像信息，一幅图胜过干言万 语，图像信息是人类认识世界及人类自身的重要源泉。然而，数字 图像中包含的数据量十分巨大，如考虑中分辨率( 6 4 0 4 8 0 ) 下，全 屏幕显示( f u l i s c r e e i l ) ，真彩色( t r u e c o o r2 4 位) 全动作( f u l i m o t i o n ，2 5 3 0 帧秒) 的图像序列，播放1 秒钟的视频画面数据量 为：6 4 0 4 8 0 3 3 0 = 2 7 ，6 4 8 ，0 0 0 字节，相当于存贮一千多万个汉字 所占用的空间。即使降低彩色性逼真要求，量化为8 位灰度，每秒 显示2 5 帧，数据量也达：6 4 0 4 8 0 2 5 = 7 ，6 8 0 ，0 0 0 字节。如此庞大 的数据量，给图像的传输、存贮以及读出造成了难以克服的困难， 例如在基于i n t er n e t 的多媒体通信中，虽然目前美国的主干网速率 己达155 m b p s ，面向最终用户的局域网的速率也有1 0 m b p s 或 10 0 m b ps ，如此高的传输速率仍无法完全满足视频通讯等应用的巨 大数据量。”j 。 图像压缩就是在没有明显失真的前提下，将图像的位图信息转 变成另外一种能将数据量缩减的表达形式。首先，尽管图像中数据 量很大，但数据之间不是完全独立的，图像中存在着各种各样的相 关性或冗余信息。即一部分数据可以由另一部分数据完全推算出 来。其次，大部分图像视频信号的最终接收者都是人眼，而人类的 视觉系统是一种高度复杂的系统，它能从极为杂乱的图像中抽象出 有意义的信息，并以非常精练的形式反映给大脑。人眼对图像中的 不同部分的敏感程度是不同的，如果去除图像中对人眼不敏感或意 山东大学硕士学位论文 义不大的部分，对图像的主观质量是不会有很大影响的。 正由于图像压缩的必要性和可能性，图像压缩编码研究成为一 个越来越活跃的领域。在诸如基于i n t e r n e t 的多媒体通信、可视电 话、数字电视，多媒体计算机等领域得到了广泛的应用。图像编码 技术包括三个主要方面：1 ) 图像压缩的新算法的研究。2 ) 基于v l s i 技术的压缩算法的硬件实现。3 ) 面向不同应用场合的压缩编码标准 的制定。其中，压缩算法的研究是图像编码技术的关键。本课题的 主要工作是对压缩算法的研究，并且采用分形方法对图像进行压缩 处理。 1 2 分形图像压缩技术的发展前景 1 0 多年来，虽然分形图像自动编码和解码不断改进但仍然 不够成熟产生的压缩比不够高，压缩效果还不十分理想，在当前 图像压缩编码中还不能占据主导地位。国际标准m p e g 4 中已经把 小波列了进去，但分形不在其中。静态图像压缩标准j p e g 2 0 0 0 是 完全使用小波的图像编码方法，也没有把分形方法列进去。但分形 图像压缩方法的优势和潜力是巨大的。 分形图像压缩既考虑局部与局部，又考虑局部与整体之间的相 关性，适合于自相似或自仿射的图像压缩，而自然界中存在大量的 自相似或自仿射的几何形状。因此，它的适应范围很广。 分形图像压缩( 当前尚须人工干预) 能获得相当高的压缩比( 一 万比一甚至几万比一) 和很好的压缩效果，具有很大的潜力。分形 解码时能放大到任意大的尺寸，且保持精细的结构。在高压缩比的 情况下，分形图像压缩自动编码能有很高的信噪比和很好的视觉效 果，这是其他方法不能相比的。因此分形图像压缩是一个有潜力、 有发展前途的压缩方法。 分形编码在人工干预条件下能够达到相当高的压缩比。但对于 如何去掉人工干预则需研究给定的图像，实现计算机自动确定分形 生长模型、l 系统、i f s 码和r i f s 码等，寻找新的压缩模型和新 山东大学硕士学位论文 的突破点。综合分析当前自动编码的各种改进算法，在此基础上， 继续寻找加快编码速度、提高压缩比、改善压缩效果的突破性的改 进方法。研究按分形维数分割图像、将分形维数相同的区域块用分 形方法进行编码的理论、方法和实现的算法。继续研究分形编码与 其他编码方法相结合的新的编码方法1 2 i 。对分形图像压缩的计算机 仿真和实际应用的研究 j 。 信息时代带来的“信息爆炸”使数据的压缩存储和传输成为信 息科学的重要课题之一，诸如基于小波和d c t 的数据压缩、分形 图像压缩、j p e g 等图像压缩方法应运而生。在这一领域分形压 缩方法因其具有的高压缩比而有着广阔的发展前景。分形图像压缩 以迭代函数系统( i f s ) 为理论基础，是基于图像的自相似性来进 行数据压缩的。这一研究方法首先由m b a r n s l e y 提出，之后a e j a c q u a i n 、y f i s h e r 等人又提出了基于局部迭代函数系统( l i f s ) 的理论【2 ”。随着多分辨率分析技术的成熟，分形图像压缩的适用 范围进一步扩大了，但降低算法的复杂度和缩短压缩时间是分形图 像编码一直需要解决的问题。 1 3 本课题要实现的目标及技术指标 本课题采用分形图形压缩结合小波变换、多分辨率分析的方 法，在小波域中对待压缩图像进行编码。分形图像压缩的难点之一 是如何提高压缩编码的时间和保证解码图形的质量。考察以往分形 方法在图形压缩中的应用，只要寻找到了有效的加速算法，编码时 间的缩短是必然的。但这些算法往往以降低图像恢复质量为代价， 换取图像压缩的提高，以致解码图像的块效应明显，视觉效果很差。 若没有达到视觉要求的解码效果，压缩没有太大的实用价值；若压 缩的时间过长，也很难在实时编码中使用；若压缩比得不到有效提 高，使用分形方法压缩图像的意义就不大。所以，本文提出的压缩 算法，力图找到一个使图像压缩比、图像恢复质量和图像的压缩时 问三者最佳的平衡点，而不是单纯提高压缩比或降低压缩时间。 山东大学硕士学位论文 自! ! ! _ ! = l _ _ _ _ e _ 自日g 自_ _ l _ e - _ _ l _ i _ 对于恢复图像的质量控制，根据人眼睛的视觉特性及图像恢复 质量的常用指标p s n r ：当这一指标超过3 0 d b 时，人的主观感觉就 很难找出原始图像和恢复图像的差异f 1 1 。算法要将恢复图像的峰值 信噪比至少提高到3 0 d b 以上，以满足人眼对图像质量的最低要求。 在图像解码后，引入误差修正算法，并再次使用分形压缩的算法。 这样，在图像的编码过程中，就可以有意提高编码时间和压缩比， 而不必太顾及解码图像的质量。 在图像的压缩比的控制上，用分形方法本身压缩图像就可以获 得很高的压缩比。当然，这是依靠牺牲部分解码图像质量的有损编 码来实现的。所以，在用小波方法对原始图像的预处理中，就不必 刻意去用小波方法压缩图像。这里，小波变换的使用只是为分形方 法创造一个变换域，并去除图像胞部分冗余信息，使得图像中的自 相似部分以小波树【2 】的形式表现出来。解码时应用小波逆变换的无 失真特性，既保证了图像压缩比，又缩短了图像压缩时间。因为在 解码后又添加了误差图像的编码过程，所以在小波域中寻找自相似 块时，可以通过调节阈值参数s 的方法，大大提高小波域图像的压 缩比。而对误差图像的编码，则会使当地降低整幅图像的压缩比， 从而在保证恢复图像质量的基础上，获得4 0 倍左右的压缩比。 至于图像的压缩时间，它是和图像压缩比密切相关的。当图像 压缩比越高，解码图像的恢复质量也就越低，压缩时间越短：反之， 压缩时间越长。根据以往的经验，分形方法不能应用于实时图像压 缩的重要原因之一就是计算复杂度高，压缩编码过程太长。但是， 图像的压缩时间不是衡量图像压缩效果的唯一标准。若牺牲一定的 鳃码图像质量，是可以大大缩短分形图像编码时间的，以往的研究 十分重视图像的恢复质量，所以一味提高压缩时间不是课题的最终 目的。本文提出的方法，是在保证图像质量的前提下，力求有效缩 短压缩时间。但不能达到可以实时应用的程度，这是以后仍需要解 决的一个重要课题1 2 j 。 山东大学硕士学位论文 1 4 分形图像压缩方法的发展现状 1 4 1 分形图像编码大体原理 对现实世界中的图像集合引入h a u s d o r f f 度量，使其形成一个完 备的度量空间，它的每个点既表示一幅图像，又是欧氏空间的一个 紧子集。分形图像压缩的理论基础是迭代函数系统i f s 定理、收缩 映射定理和拼贴定理。一个迭代函数系统由个完备的度量空间和 其上的一组收缩映射组成。收缩映射定理告诉我们，函数空间中的 每一个收敛映射都有一个固定点，使函数空间中的每个点经过这 个收缩映射的连续作用后形成的点列收敛于这个固定点1 3 j 。 迭代函数系统定理指出，每个迭代函数系统都可以构成函数空 间中的一个收缩映射。于是，我们得到结论；每个迭代函数系统都 决定一幅图像。反过来考虑：给定一幅图像，找到一个迭代函数系 统，而使这个系统正好能决定给定的图像则是要解决的问题。此问 题由拼贴定理给出了回答。拼贴定理告诉我们：给定一幅图像丁， 可以选择n 个收缩映射，这幅图像经过n 个变换得到n 个像集每 个像集都是一块小图像。如果这n 个小图像拼贴起来的图像与图像 丁之间的距离任意小，则这n 个收缩映射构成的迭代函数系统所决 定的图像就任意地接近图像7 1 。这就告诉了我们寻找迭代函数系统 的方法【2 - 3 1 。 1 4 2 分形图像编码一些方法 分形图像编码的过程是依据拼贴定理，通过绘定的图像，寻找 一组收缩映射，使其组成的迭代函数系统的吸引子逼近给定图像， 然后记录下相应参数。解码过程是由相应参数确定迭代函数系统， 并根据迭代函数系统定理经过迭代生成图像。 传统的分形图像编码要先把原图像，分割为r a n g e 块( r ! ) ，即 山东大学硕士学位论文 ! ! ! _ 目_ _ _ _ _ e ! 日e _ g 目l _ _ e - _ _ _ _ _ _ _ - _ _ ! l ! n ，= u r ，且r ，n r ，= ( i ，) ；对于每个r ，在，中搜索最优的 j = 1 d o m a i n 块d j ，并确定对比度因子5 。和亮度平移值f ，使其满足 慨一t ( d ，) 1 1 ：2 。m 。i n i i r 。一s d 一, 1 1 ：。其中d 表示口块的2 x 2 采样 ( 此处 假设d ，的边长为r ，的2 倍) ，通过搜索得到变换( x 。，y ；j 。t ) ，y ，表 示d 块的位置。所有仿射变换 w o ，w i ，w 2 ，w a 构成的l i f s 就是编码的 结果。根据不动点原理和肼s 的拼贴定理，可通过迭代解码并重构 图像5 1 。 1 分形图像压缩编码有两种基本方法 人工干预的交互式分形图像编码方法主要是针对给定图像的 形状，采用边缘检测、频谱分析、纹理分析、分维方法等传统的图 像处理技术进行图像分割要求被分开的每部分都有比较直观的自 相似特征【2 】。然后寻找迭代函数系统，确定各个变换系统。再由图 像中灰度分布求得各个变换的伴随概率。解码过程是采用随机迭代 法来生成近似图像。这种方法的压缩比一般是相当高的。 适应块状分形编码方法首先将图像分割成若干不重叠的值域块 r 和可以重叠的定义域块d ，接着对每个r 寻找某个d ，使d 经过 某个指定的变换映射到r 达到规定的最小误差，记录下确定月和d 的参数及变换矽，得到一个迭代函数系统。最后对这些参数进行编 码。 码过程包括对图像的分割、搜索最佳匹配、最后记录相关的系 数三个步骤。 自适应块状分形解码方法是由编码传来的参数确定迭代函数系 统，经过有限次迭代，图像会稳定下来，它趋近迭代函数系统的吸 引子，该吸引子就是被编码图像的解码图。上述编码过程中搜索匹 配的计算量很大，耗用时间太长，限制了实际应用。因此，人们不 断进行研究改进，提出了许多改进方案。 山东大学硕士学位论文 2 分形图像压缩的改进方法 为了提高压缩比和编码效果，人们研究出的改进方法2 】有： ( 1 ) 改进分割的方法有基本四叉树分割法、基于h v 分割法。 这两种分割方法都是将图像分割成矩形。而图像块的相似性未 必都落在矩形内。代替水平或垂直剖分而采用的分割方法有基于三 角形分割法、基于六边形分割法、基于边界分割法、基于菱形分割 法、基于多边形分割法。 以上分割方法各有千秋其中最常用、最普遍的是四叉树分割 法。四叉树分割方法的优势是定义域池中分类的复用率很高，且值 域块存储用位数较少。h v 分割法使用的变换个数比四叉树少，但 定义域块的分类不能复用。使用h v 分割并采用特征追踪法，其编 码速度可以有很大提高。六边形、三角形、菱形、多边形分割各有 优势，但在搜索、存储等方面仍需进一步研究。 ( 2 ) 覆盖式方法 覆盖式方法有快速覆盖式分形压缩方法和四叉树重组q r 算法 两种。它们都是采用通过合并值域块来提高压缩比。前者要求合并 后不一定规则，后者合并后则是规则的。 ( 3 ) 提高显示效果的后处理法 分形图像压缩对值域块独立编码，这不能保证块与块之间的连 接最光滑的，常有块效应出现，人的眼睛对此比较敏感。消除块效 应的一个常用方法是后处理一股采用2 ：1 加权平均或3 ：2 ：1 加权 不均法。 编码过程中最耗时的是搜索最佳匹配的定义域块，要提高编码 速度1 6 l ，就必须缩小搜索范围，且保证最佳匹配落在该范围之内。 其改进方法有： ( 1 ) 分类法 搜索最佳匹配计算量很大，占用了编码的大部分时涮，因而限 制了它的实际应用。为了缩短搜索时间，在匹配之前按照图像的特 征如中值、方差、力矩和其他感知或统计的几何特征，将定义域和 山东大学硕士学位论文 值域块进行分类，匹配时只在同一类中进行搜索比较。这样在不降 低图像质量的前提下，大大提高了编码速度。常用的分类方法有： 基于明暗度的定向分类、基于空域特征的分类、基于相对矩的分类、 基于小波的分类、基于人类视觉系统( h v s ) 分类、基于模糊分类、 原形的分类、自适应码本簇化的分类、向量量化的分类。 以上各种方法分别从不同的角度、使用不同的工具对图像块分 类，各自保持了自己的特点对加速编码有不同程度的作用。 ( 2 ) 搜索法 匹配搜索耗时最长，常用的加速搜索方法有，局部搜索法、提 取特征追踪法、基于方差搜索法、f f t 搜索法。 分形解码速度相对于编码要快得多，一般它迭代1 0 次左右即 可完成。然而对于一些实际应用来说，仍然希望迭代次数越少越好， 这样可以进一步加快解码速度。常用的加速方法有金字塔式解码 器、去均值解码算法、非迭代算法、b c c 和i c c 算法。 近两年来分形与其他方法混合编码【2 i 取得了很好的效果。常 用的混合方案8 9 ，1 0 l 有与小波变换结合编码、与d c t 变换结合编码、 与加权有限自动机结合编码、与向量量化结合编码、与遗传算法结 合编码、与f f t 算法结合编码、与非线性模型结合编码和与算术结 合编码。 近10 年来人们对于自适应块状分形编码进行了不懈的研究， 提出了以上若干改进算法，这些算法在不影响视觉效果的条件下， 大力减少了编码时间。而且在高压缩比和解码图像任意放大方面， 比现有的静态图像国际压缩标准j p e g 好得多，已经开始显露出它 的优势。分形图像编码方法的实际应用也初见端倪。如分形图像压 缩解码速度很快，当前已经适合于一次写入、多次读出的文档。 山东大学硕士学位论文 = l = ! _ l e i t l e e e e e 自e l _ _ _ _ _ 目j l _ _ _ - i _ _ 一 第二章分形理论及数字图像编码的主要方法介绍 2 1 分形图像压缩的可能性 分形( f r a c t a l ) 自曼德勃罗特1 4 】( m a n d e l b r o t ) 发现以来，已经 成为非线性科学的一个重要分支h 】。但是至今分形还没有确切 的简明的定义。m a n d e l b r o t 给出分形集合的般特征为： ( 1 ) 该集合有精细结构，即在任意小的比例尺度内包含整体： ( 2 ) 无论从局部和整体来看，分形集合都是很不规则的，无法用传 统的几何语言来描 ( 3 ) 通常分形集合都具有某种自相似性，可能是近似的，也可能是 统计意义的； ( 4 ) 通常分形集合的”分形维数”比它的拓扑维数要大： ( 5 ) 许多情况下，分形集合是简单的或者是递归的算法集合 虽然分形【4 ，”1 的这种描述性定义比较抽象，但是自然界许多不 规则的复杂现象，如山峦和云团的外形，曲折的海岸线等都具有分 形特征。而且自然界许多事物的发展过程，如生长、凝聚、进化等 也形成多种分形结构。这种客观世界的内在规律，自然的会反映在 认识的信息世界和概念世界，从而可用分形刻画反应客观的数据。 事实上，分形既被看成大自然的几何学，又被看成混沌运动的产物 即混沌几何【3 1 。这些观念对现代数据库具有重要意义：一方面，现 代数据库的管理对象不同于传统的数据库：传统的数据库管理都是 以数值和字符数据为管理对象，其应用对象主要是一般的商业或事 务数据，现代数据库管理对象已扩充到以管理多媒体数据。复杂数 据对象等数据：它们一般具有多维特征，多维是分形刻画的特长； 另一方面，由于分形集合具有简洁的算法表达，它能消除客观世界 事物的自相似冗余。这对数据存储、传输响应、快速奁询和分析等 具有显而易见的重要意义；它对于更高级别、大容量的且需要在线 分析处理的数据仓库更具有重要意义。数字图像的分形编码方法， 就是分形的一个重大应用。这些工作基于b a r n s l e y ，j a e q u a i n ，f i s h e r 9 山东大学硕士学位论文 等人的研究成果和国内众人的课题经验f2 1 。虽然这一方法还不是很 成熟，但已经被证明是可行有效的。相信在不久的将来，这一方法 会赶超现有的压缩编码方法，而被推广采用。 图像分形编码的基本思想就是发现图像的简洁分形码。它是分 形图形生成的逆过程，通过获取分形码，消除相似冗余，可使图像 存储的压缩比达到6 0 到1 0 0 0 甚至更高( 与具体的图像有关) 。图 像分形编码的基础性理论是不动点定理和b a r n s l e y 的拼贴定理。目 前经常使用的分形图像编码方案是j a c q u a i n 在1 9 9 0 年首次提出的， 它是一种全自动的基于块的分形图像压缩方案，为分形图像编码的 研究带来了一次质的飞跃。在这之后，各国的研究者们纷纷效仿 j a c q u a i n 的压缩方案+ 提出了各种各样的改进方案，从而掀起了分 形图像编码研究的高潮【2j 。 分形图像编码利用了原始图像块与块之问的相似性，能够较 好出去除图像块的冗余度。但在j a c q u a i n 提出的分形压缩方案中， 尚有一部分冗余度可以去除，特别是存储系数间仍有较大的相关性 另外在j a c q u a i n 的压缩方案中，其解码图像中存在着明显的方块效 应，仔细观察以前文献中的实验结果就可以发现这一点。 与自然界的景物图像相比，人像中的相似性是最难寻找的，但 人身上局部的相似性却是存在的且可以利用这一相似性对其进行 分形编码1 2 l 。图2 1 就是用于图像压缩的一张标准的l e n n a 上身图 像，图2 2 表明镜子里帽子像的一部分与她帽子的一部分在经过一 定的旋转亮度后是相似的。另外，在人像的肩膀、耳朵和脸颊等多 处地方都存在着至少是相似的自相似性。这些相似性只反映了图中 显而易见的几处分块，而对于大量灰阶值变化不大的块来说，其自 相似性更是可以用一个非常小的块通过仿射变换来代替一片大面 积的图像。所以，在含低频成分较多的图像中使用分形编码方法是 十分有效的，且高频成分越少，图像的压缩比就愈高。对于一般的 图像，其高频成分和低频成分是不定的，所以我们用标准的l e n n a 图 像来验证分形图像压缩方法的有效性。 1 0 山东大学硕士学位论文 图2 1 原始l e n a 图像图2 - 2l e n a 图像中的自相似部分 2 2 图像压缩编码的可能性及压缩编码方法的分类 从信息论观点来看，图像作为一个信源，描述信源的数据是信 息量( 信源熵) 和信息冗余量之和。信息冗余量有许多种，如空间冗 余，时间冗余，结构冗余，知识冗余，视觉冗余等，数据压缩实质 上是减少这些冗余量。可见冗余量减少可以减少数据量而不减少信 源的信息量。从数学意义上讲，图像可以看作一个多维函数，压缩 描述这个函数的数据量实质是减少其相关性。另外在一些情况下， 允许图像有一定的失真，而并不妨碍图像的实际应用，那么数据量 压缩的可能性就更大了【l 7 ”6j 。 编码压缩方法有许多种，从不同的角度出发有不同的分类方 法。比如从信息论角度出发可分为两大类：( 1 ) 冗余度压缩方法， 也称无损压缩，信息保持编码或熵编码。具体讲就是解码图像和压 缩编码前的图像严格相同，没有失真，从数学角度讲是一种可逆 运算。( 2 ) 信息量压缩方法，也称有损压缩，失真度编码或熵压缩 编码。也就是将解码图像和原始图像是有差别的，允许有一定的失 真。应用在多媒体中的图像压缩编码方法从压缩编码算法原理上 可以分类为：( 1 ) 无损压缩编码种类：哈夫曼编码、算术编码、行 程编码等。( 2 ) 有损压缩编码种类：预测编码：d p c m ，运动补偿： 频率域方法：正文变换编码( 如d c t ) ，子带编码：空间域方法：统 山东大学硕士学位论文 _ ! ! g s = = ! = ! e _ _ 目e l 自自l e l e j ! _ 日_ 日目_ _ 目 计分块编码：模型方法：分形编码，模型基编码：基于重要性：滤 波，子采样，比特分配，矢量量化。( 3 ) 混合编码：j b i g ，h 2 6 1 ， j p e g ，m p e g 等技术标准。 衡量一个压缩编码方法优劣的重要指标是： ( 1 ) 压缩比要高，有几倍、几十倍，也有几百乃至几千倍： ( 2 ) 压缩与解压缩要快，算法要简单，硬件实现容易； ( 3 ) 解压缩的图像质量要好。 要特别说明的是选用编码方法时要考虑图像信源本身的统计 特征、多媒体系统( 硬件和软件产品) 的适应能力、应用环境以及技 术标准。选择编码的方法是至关重要的，下面是几种编码的大体方 法。 1 9 6 9 年在美国召开的第一届”图像编码会议”标志着图像编码 作为一门独立的学科诞生了。到了7 0 年代和8 0 年代，图像压缩技 术的主要成果体现在变换编码技术上，矢量量化编码技术也有较大 发展，有关于图像编码技术的科技成果和科技论文与日俱增，图像 编码技术开始走向繁荣。自8 0 年代后期以后，由于小波变换理论， 分形理论，人工神经网络理论，视觉仿真理论的建立，人们开始突 破传统的信源编码理论，例如不再假设图像是平稳的随机场。图像 压缩编码向着更高的压缩比和更好的压缩质量的道路前进，进入了 一个崭新的、欣欣向荣的大发展时期。 数字图像压缩技术可以分为无损压缩技术和有损压缩技术。图 像无损压缩技术主要有：位平面编码、无损预测编码( d p c m ) 以及 有损编码与残差无损编码的组合编码技术。传统的数字图像有损压 缩技术主要有预测( p c m 、d p c m ) 、方块化( b l o c kt r u n c a t i o n c o d i n g ) 、向量量化v q ( v e e t o rq u a n t i z a t i o n ) 、层次化( h i e r a r c h i c a l c o d i n g ) 、子频带( s u b b a n dc o d i n g ) 和变换( t r a n s f o r mc o d i n g ) 等等。 近年来，人们又提出了神经网络法、几何模型化、分形和小波变换 等编码技术。通常认为，j b i g 、j p e g 、m e p g 1 、m p e g 2 、m e p g 4 以及酝酿中m p e g 一7 图像压缩的国际标准是针对不同应用的最佳 压缩算法之一。在这些标准之中成功地采用了以上的一种或多种混 山东大学硕士学位论文 _ _ g e ! ，e 目= ! ! ! ! = ! ! ! ! ! e ! ! ! s _ _ _ l e 自= = ! ! ! 一 合压缩技术。 一般说来，d p c m 对于保持物体在景象中的位置是最佳的，能 提供良好的潜像与灰度性能，保存背景信息，实现简单。但边缘清 晰度临界，缩减比率有限；同时，由于误差会传播，所以抗通道误 码的能力较弱。j b i g 是针对二值图像的压缩标准。j p e g 则是处理 彩色或单色静止图像的压缩标准。利用它可以获得较高的压缩比， 并保持较好的信噪比，从而大大节省图获得较高的压缩比，并保持 较好的信噪比，从而大大节省图像存储空间，降低通信带宽，但是 编码过程会使物体在景象中的位置略有移动( 即发生几何畸变) 。 另外，在高压缩比场合，j p e g 的重建图像在水平和垂直方向可能 有晕圈、幻影，产生“方块”效应。m p e g 是针对运动图像压缩的 国际标准，它能达到比j p e g 更高的压缩比。 j p e g2 0 0 0 ，正式名称为“i s o15 4 4 4 ”，同样是由j p e g 组织 负责制定。j p e g2 0 0 0 与传统j p e g 最大的不同，在于它放弃了 j p e g 所采用的以离散余弦转换( d i s c r e t ec o s i n et r a n s f o r m ) 为主 的区块编码方式，而改采以小波变换( w a v e l e tt r a n s f o r m ) 为主的多 解析编码方式16 1 。小波变换的主要目的是要将影像的频率成分抽 取出来。 j p e g 2 0 0 0 的优点如下： ( 1 ) j p e g 2 0 0 0 作为j p e g 升级版，高压缩( 低比特速率) 是其目标、， 其压缩率比j p e g 高约3 0 左右。 f 2 1j p e g 2 0 0 0 同时支持有损和无损压缩，而j p e g 只能支持有损 压缩。无损压缩对保存一些重要图片十分有用。 f3 ) j p e g 2 0 0 0 能实现渐进传输，这是j p e g 2 0 0 0 的个极其重要的 特征。也就是我们对g i f 格式影像常说的“渐现”特性。它先传 输图像的轮廓，然后逐步传输数据，不断提高图像质量，让图像由 朦胧到清晰显示，而不必是像现在的j p e g 一样，由上到下慢慢 显示。 r 4 1j p e g 2 0 0 0 支持所谓的“感兴趣区域”特性，你可以任意指定 影像上你感兴趣区域的压缩质量，还可以选择指定的部分先解压 山东大学硕士学位论文 ! ! ! ! ! = = = j j _ 目自e ! s ! ! ! = ! ! ! ! ! ! ! ! ! ! ! ! 一! 。 i 缩。这样我们就可以很方便的突出重点了。 j p e g2 0 0 0 的应用领域可概略分成两部分，一为传统j p e g 的 市场，像印表机，扫描器，数位相机等，一为新兴应用领域，像网 路传输，无线通讯，医疗影像等。目前对j p e g2 0 0 0 主要应用于数 字照相机中。j p e g2 0 0 0 和j p e g 相比优势明显，且向下兼容，因 此取代传统的j p e g 格式指日可待。 2 3 图像质量的判别标准【2 对于有损压缩，原图像和重建图像之间存在着差异。差异的大 小意味着恢复图像的质