（机械设计及理论专业论文）基于图像特征的分形图像编码方法研究.pdf

摘要 摘要 随着计算机科学和多媒体技术的发展，现代信息社会对信息通信提出了更高 的要求，而图像压缩编码是实现数字信息化社会的关键技术之一。在众多的图像 j ：氍编方法之中，分形图像压缩是目前广泛研究的图像压缩方法之一，它以压缩理 论新颖、解码速度快、恢复图像好等优点而备受关注。本论文的工作是在深入研 究了国内外分形图像编码技术的基础上开展的，提出了一种考虑图像特征并充分 利用人眼的视觉特性的新的编码方法。 本文首先介绍了课题的研究背景与意义，以及图像压缩的概念、方法和评价 标准。接着介绍了分形的概念、特点，分形方法可以用于图像压缩的依据，重点 讨论了迭代函数系统理论、仿射变换、压缩映射的不动点定理及拼贴定理等分形 编码的数学基础和理论基础。 通过对分形图像压缩编码的原理和编码方法的分析与研究，编程实现了已有 的分形编码方法，如j a c q u i n 的编码方法、四叉树法、三角形分块等方法，并通 过埘比、综合、分析各种方法的特点，提出了一种基于图像特征的新的编码方法。 这种方法考虑到图像的灰度分布特征以及人眼对灰度变化的敏感程度会随着背景 而变化的特性，以平均灰度值与灰度方差为基准将图像块分为特征块和普通块， 冉将普通块进行区域合并，以减少图像块的个数，提高编码速度；同时，针对区 域合并后图像块大小、形状各异的问题，采取了对图像块形状参数单独存储的方 法，利用参数间的空间关系去除了参数存储的冗余，提高了编码效率。 本论文的研究既是对分形图像编码方法的深入学习和研究，同时也是对分形 图像编码理论的进步扩充，结合小波变换、离散余弦变换等其它数据压缩方法， 分形图像编码方法将更加成熟和完善。本论文为今后进一步的研究提供了理论基 础和算法基础。 关键词：分形，图像压缩，迭代函数系统，仿射变换 华南理工大学工学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e ra n dm u l t i m e d i a ，m u c hh i g h e rd e m a n df o r c o m m u n i c a t i o nc o r r e s p o n d i n gi s b e i n gb r o u g h tf o r w a r db ym o d e r nc o m m u n i c a t i o n s o c i e t y i m a g ec o m p r e s s i o nc o d i n gi s o n eo ft h ek e yt e c h n o l o g yb yw h i c hr e a l i z e c o m m u n i c a t e ds o c i e t y f r a c t a li m a g ec o m p r e s s i o ni so n eo ft h ei m a g ec o m p r e s s i o n m e t h o d st h a ta r es t u d i e dw i d e l yn o w p e o p l eg i v ei tm u c ha t t e n t i o na si t sa d v a n t a g e s u c ha si t sn o v e lt h e o r y ，i t sf a s td e c o d i n g ，i t sg o o dr e s u m p t i v ei m a g e ，a n ds oo n t h i s p a p e r sr e s e a r c hb a s e do nt h ec u r r e n tf r a c t a li m a g ec o m p r e s s i o nt e c h n o l o g yw i t ht h e m a i np u r p o s eo fp r o p o s i n ga ni m a g ec o d i n gm e t h o dw h i c hh a sb e t t e rs u b j e c t i v e q u a l i t ya n dc o d i n gp e r f o r m a n c e f i r s t ，t h eb a c k g r o u n da n d t h e s i g n i f i c a n c e o ft h i s p a p e r s r e s e a r c ha r e p r e s e n t a t e d a t t h es a m et i m e ，t h i sp a p e ri n t r o d u c e st h ec o n c e p t ，t h em e t h o da n dt h e e v a l u a t i o nm e a s u r eo ft h ei m a g ec o m p r e s s i o n t h e n ，t h ec o n c e p ta n dt h et r a i t s o f f r a c t a la n dt h eg i s tw h i c hf r a c t a lt h e o r yc a nb eu s e di nt h ei m a g ec o m p r e s s i o na r e d i s c u s s e d t h ep a p e ra n a l y s e st h em a t h e m a t i cb a s ea n dt h ea c a d e m i cb a s ef o rf r a c t a l i m a g ec o m p r e s s i o n s u c ha si t e r a t e df u n c t i o n s y s t e m s ，a f f i n e t r a n s f o r m a t i o n ， c o n t r a c t i v em a p p i n gf i x e d p o i n tt h e o r e m ，a n dc o l l a g et h e o r e m a c c o r d i n gt o s o m ef r a c t a li m a g ec o m p r e s s i o nc o d i n gm e t h o d sw h i c hh a db e e n r e s e a r c h e d ，w ec o l l i g a t e ，b a l a n c et h e m ，a n da n a l y s e t h e i rc h a r a c t e r i s t i c t h r o u g h s t u d y i n g t h eb a s i c p r i n c i p l e s ，m e t h o d o l o g i e s ，g e n e r a l p r o c e s s f o rf r a c t a l i m a g e c o m p r e s s i o n an e wm e t h o do fi m a g ec o d i n g b a s e do nt h et r a i to ft h ei m a g ei s d e s i g n e d i n t h i s a l g o r i t h m ，w ea n a l y s e t h ec h a r a c t e ro ft h e o r i g i n a li m a g e a n d a d e q u a t e l yc o n s i d e r t h et r a i tt h a th u m a n sv i s u a ls e n s i t i v i t yr e l a t e st ot h eb a c k g r o u n d t h em e a ng r a yl e v e la n dd i f f e r e n c eo ft h ei m a g et a k e ni n t o a c c o u n ts y n t h e t i c a l l y ， p a r t i t i o n st h ei n i t i a li m a g e i n t oi r r e g u l a rb l o c k sa c c o r d i n gw i t ht h eg r e yf r a m eo ft h e i m a g e ，a n d t h e r e f o r et h eb e t t e r p a r t i t i o n s a r eo b t a i n e d t h ep a r a m e t e ro fa f f i n e t r a n s f o r m s ，a n dc o n s e q u e n t l yi n c r e a s e st h ee f f i c i e n c yo fc o m p r e s s i o n i na l l u s i o nt o t h ep r o b l e mo ft h ei r r e g u l a rf i g u r e ，w es t o r et h es h a p ep a r a m e t e r ss e p a r a t e l y ，w i p e o f f t h er e d u n d a n c eo fp a r a m e t e r s s t o r a g eb yu s i n gt h es p a c ec o n n e c t i o no fp a r a m e t e r s ， a n dc o n s e q u e n t l yi n c r e a s et h ee f f i c i e n c yo fc o m p r e s s i o n t h i sr e s e a r c hi sd e e ps t u d yw h i c ha c c o r d i n gt of r a c t a li m a g ec o d i n gm e t h o d ，a t t h es a m et i m e ，t h i ss t u d yi sa l s ot h em o r ee x p a n s i o nf o rf r a c t a li m a g ec o d i n gt h e o r y i i a b s t r a c t t h ef r a c t a li m a g e c o d i n gm e t h o dw i l lb em o r em a t u r ea n dc o l l s u m m a t ei ft h i ss t u d y w o u l db ec o m b i n e dw i t ho t h e rd a t ac o m p r e s s i o nm e a n ss u c ha sw a v e l e tt r a n s f o r m a n dd i s c r e t ec o s i n et r a n s f o r m ，a n ds oo n t h i sp a p e rp r o v i d e st h e o r e t i cb a s ea n d a l g o r i t h m i cb a s ef o rf u t u r em o r es t u d y k e yw o r d s ：f r a c t a l ，i m a g ec o m p r e s s i o n ，i t e r a t e d f u n c t i o ns y s t e m s ， a f f i n et r a n s f o r m a t i o n i 华南理工大学 学位论文原创性声明 本人! j 5 一，- - + b 凋：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：徐瑾 吩磊 日期：2 0 0 4 年4 月2 5 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被套阅和借阅。本人授权华南理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上相应方框内打“”) 作者签名：徐瑾 导师签名：蔡秀云 镰影 旁如 ， 日期：2 0 0 4 年4 月2 5 日 日期：2 0 0 4 年4 月2 5 日 第一章绪论 1 1 研究背景与意义 第一章绪论 随着计算机科学和多媒体技术的发展，信息高速公路、高清晰数字电视、多 媒体教学、远程医疗等都不断地对信息数据的存储和传输提出了更高的要求。多 媒体信息的处理，其中遇到的一个重要问题就是数字化图像的巨大数据量，而仅 仅依靠增大计算机的存储容量、扩大网络带宽来解决这一问题显然是跟不e 发展 的。面对数据量巨大的数字化图像的存储、传输、处理和交换等问题，图像压缩 编码成为当今通信和信号处理领域的一个重要课题。 图像压缩编码的目的是以尽量少的比特数表征图像，同时保持恢复图像的质 量，使它符合预定应用场合的要求，以便于图像的处理、存储、传输。通常把图 像压缩编码简称为图像编码。图像的各象素之间存在着很大的相关性，可以利用 一些编码的方法删除相关性，减少冗余，达到压缩图像的目的。传统的图像压缩 编码方法都是从数字信号处理角度出发，利用信号理论和信息理论作为工具，以 信号序列或信号矩阵为基本的微观编码方法。因此，传统的压缩算法已成了定势， 其发展受到很大的限制。基于分形几何学的图像压缩方法思想新颖，在压缩比达 到很高时，解码图像仍然保持很好的视觉效果，是一种很有发展前途的压缩方法。 分形是描述自然界许多不规则事物的规律性的科学，它的描述对象是极其复 杂、极= ：_ i i 规则的许许多多自然形态，如d l 、云、闪电及雪花等。多数自然形貌具 有分形的特点，利用分形原理可以生成逼真的自然场景和美妙无比的图案，并可 以通过计算机图像图形技术来实现，应用前景十分广阔。 分形压缩编码的基本思想是利用图像的自相似性，在编码时将图像分解为若 干分形子图，提取其i f s ( 迭代函数系统) 代码，然后编码传输这些i f s 代码。 在解码时，则由该代码按规律迭代重构各子图。由于多数的自然景物都具有不同 程度的白相似特征，因而分形图像编码技术的适用范围较广。分形编码方法具有 j 五缩原理新颖、压缩比高、解码效果好等优点。 1 9 9 2 年圣诞节，美国微软公司推出一张名为“m i c r o s o f te n c a r t a ”的光盘， 是一本多媒体百科全书，广泛收集了文章、动画片、声音、插图、照片、地图册 和一本字典，内有几百幅彩色地图( 可以被局部放大) ，几千张优质彩色照片。这 么多内容，全部用分形图像压缩为不足6 0 0 m b 的数据”“j 。 分形图像压缩这一由交叉学科形成的很有潜力的研究方向，在短短几年内就 华南理工大学工学硕士学位论文 显示出了- 强大的力量，它的出现大大丰富了图像压缩的内容。自j a c q u i n 提出一 种全自动的分形图像编码方法以来，国内外众多研究者对这一新的编码方法进行 了学习研究，并有针对性地提出了很多改进算法，在经典的四叉树的基础l 提出 了基于区域划分、基于不规则分块、与小波分析相结合等算法。但由于分形图像 压缩是一种不对称的编码方法，其编码时阳j 跃，解码时删短，所以如何缩短编码 时间提高压缩效率仍是研究热点，因此，分形图像压缩还有很广阔的研究空间。 1 2 图像压缩概论 1 2 1 图像压缩编码概念 图像是指当光辐射能量照在物体上，经过反向或透射，或出发光物体本身发 出光能量，在人的视觉器官中所重现出的物体的视觉信息。研究表明，人类所接 收到的全部信息中，有7 0 以上是通过视觉得到的。和语言、文字等信息相比， 图像包含的信息量更大、更直观、更确切。因而具有更高的使用效率和更广泛的 适应性，可见，图像信息对于人们的生活和工作是非常重要的。 通常，图像在空间和亮度1 z 都是连续取值的，称为连续图像或模拟图像，如 果对连续图像在空间和亮度上进行离散化，就成为数字图像。一幅数字图像所占 的总数据量，由其总的灰度所需的二进制位数( 即比特数) 决定。例如，一幅1 0 2 4 7 6 8 的数字图像，如果具有2 5 6 个灰度级，即每个像素用8 b i t ( 一个字节) 表示， 那么其总数据量就是7 6 8 k 个字节。对于如此庞大的数据量，若不经压缩，数字 图像传输所需的高传输速率和数字图像存储所需的巨大容量将给存储器容量、传 输传输率( 带宽) 以及计算机的处理速度等增加巨大的压力。为了实现数字图像 通信，就必须采用有效的压缩编码技术压缩数字图像的数据量。 由于在图像数据内部存在着大量的冗余，所以数据压缩是可能的。我们就一 幅风景画( 如图1 1 所示) 进行具体分析，首先注意到画的上方是蓝色的天空( 规 则的并且均匀着色) ，这里就含有空间冗余，即一幅图像内部的相邻象素之间的大 量高度相关的信息。其次注意到画中的天空上是朵朵白云，这里就含有结构冗余。 结构冗余是指图像的部分区域内存在着非常强的纹理结构，或是图像的各个部分 之间存在着某种关系，例如自相似性。另外，注意到画中有天空、大地、花草， 其相对位置是固定的，这便有知识冗余。知识冗余是指图像中包含某些与先验的 基础知识有关的信息。除了这些以外，一般图像中还包括信息熵冗余和视觉冗余。 2 一 第一章绪论 图i 一1 风景图像 f i g1 1l a n d s c a p ei m a g e 信息熵冗余一由信息论的有关原理可知，为表示图像数据的一个象素点，只 要按其信息熵的大小分配相应的比特数即可。然而对于实际图像数据的每个象素， 很难得到它的信息熵，因此在数字化一幅图像时，对每个象素是用相同的比特数 表示，这样必然存在冗余。信息熵冗余和空间冗余、时间冗余统称为统计冗余， 因为它们都决定于图像数据的统计特性。 视觉冗余一在多数情况下，重建图像的最终接收者是人的眼睛。虽然人眼的 视觉系统足到目前为止世界上最好的图像处理系统，但它远远不是完美的。人类 的视觉系统并不是对于图像中的任何变化都能感知，在一定范围内的图像失真是 不能被人眼所察觉的。可以利用人的某些视觉不敏感性或者容忍性进行有损压缩， 例如图像亚采样( s u b s a m p l i n g ) ，一组象素用一个象素来表示，降低图像的分辨 率，达到压缩的目的( 如图1 2 ) 。 1 11 2t 51 4 1 己1 3t 55 己 1 已5 己5 15 1 5 6 s 65 5s 4 1 li s 1 25 l 图1 2 亚采样数据压缩例子 f i g1 - 2s u b s a m p l i n gd a t ac o m p r e s s i o n 另外，对于视频序列而言，还存在时间冗余，即视频序列中的各帧图像之间 一3 - 华南理工大学工学硕士学位论文 存在的人量高度相关的信息。 综上所述，在图像数据中存在着空间冗余、时间冗余、信息熵冗余、视觉冗 余和结构冗余等，这些形式的冗余是编码压缩图像的出发点，图像压缩方法就是 要尽可能地消除这些冗余信息，以降低表示图像所需的数据量。 图像压缩编码方法很多，根据恢复图像的准确程度可将常用的图像编码方法 分为两类： ( 1 ) 无损信息编码：无损编码利用数据的统计特性来进行数据压缩，要求图像 信息编码一解码过程中必须保证图像信息不丢失，从而可以完整地重建原图像。 典型的编码方法有霍夫曼( h u f f m a n ) 编码、行程编码、算术编码和l e m p e l z e v 编 码。无损压缩的压缩比比较低，一般为2 ：l 5 ：l 。 ( 2 ) 有损信息编码：有损编码不能完全恢复原始数据，而是利用人的视觉特性 使解压缩后的图像看起来与原始图像一样，也就是在允许的失真条件下或一定的 保真度准则下进行图像压缩编码，可以获得较高的压缩比。有损编码的主要方法 有预测编码、变换编码、模型编码、小波变换编码、分形编码以及混合编码方法 等。压缩比随着编码方法的不同差别较大f 5 。j 。 图l 一3 所示为图像压缩编码方法。 图像压缩编码方法 无损压缩 h u f f m a n 编码 行程编码 算术编码 l e m p e l z e v 编码 有损压缩 预测编码i | 变换编码| | 模型编码l l 摹于重要性l l 混合编码 运动辛 偿 i d t c 啊t 编码 分形编码 图1 3 图像压缩编码方法 滤波ij p e g 子采样j m p e g 矢量量化 。h 2 6 1 图1 4 所示是典型的图像压缩编码系统的原理图。 4 第一章绪论 信、) 源【信源)b ip c m 编码器e = ：引压缩编码器e = = 叫 信道编码器 接收器( 信宿) l c = jp c m 解码器 噪声 急 百赢 图1 4图像压缩编码系统原理 f i g1 4t h ep r i n c i p l eo fi m a g ec o m p r e s s i o nc o d i n gs y s t e m 1 2 2 图像压缩编码的发展 数 字 信 道 图像压缩编码的理论基础是信息论，从信息论的角度看，压缩就是去掉信息 中的冗余，即保留不确定的信息，去除确定的信息( 可推知的) ，也就是用一种更 接近信息本质的描述来代替原有冗余的描述。这个本质的东西就是信息量( 即不 确定因素) 。但信息量不是孤立、绝对的，它与信息的传输密切相关。信息接受者 知识世界的改变是信息传输的本质所在。但由于接受者知识结构世界的复杂性， 使得很难构造数学模型，从而只能对其进行具有普遍意义的某种限定，这就是仙 农信息论，即以经典集合论为基础基于某种统计概率模型来描述信源。 山于仙农( s h a n n o n f a n n o n ) 信息沦具有高度的抽象性和综合性，因此得到了 广泛应用。图像压缩编码的发展历程实际上就是以仙农信息论为基础，并综合考 虑图像特征和人眼特性的过程。 图像压缩技术的发展可以看作是经历了图像压缩编码的经典方法和现代方法 两个时代，经舆的图像压缩编码方法依据仙农信息论，充分考虑了图像信源的统 计特性，根据其核心技术的不同又可以分为：预测编码，变换编码和统计编码等。 ( 1 ) 预测编码 预测编码足利用相邻象素之问的相关性，去掉图像中冗余的信息，只对有用 的信息进行编码。由于象素的获度是连续的，所以在一片区域中，相邻象素之问 灰度值的差别可能很小。如果只记录第，一个象素的灰度，其他象素的灰度都它与 前一个象素灰度之差来表示，就能起到压缩的目的。常用的预测编码法有增量调 制m ( d e l t am o d u l a t i o n ，简称d m ) 和微分预测编码( d i f f e r e n t i a l p u l s ec o d e m o d u l a t i o n ，d p c m ) 。 ( 2 ) 变换编码 变换编码是指将给定的图像变换到另一个数据域( 如频域) 上，使得大量的 5 率 华南理工大学工学硕士学位论文 信息能用较少的数据来表示，从而达到压缩目的的方法。常用的正交变换编码有 傅立叶变换( d i s c r e t ef o u r i e rt r a n s f o r m ，d f t ) 、离散余弦变换( d i s c r e t ec o s i n e t r a n s f o r m ，d c t ) 和离散沃尔什哈达玛变换( d i s c r e t ew a l s h h a d a m a r dt r a n s f o r m ， d w h t ) 等。 ( 3 ) 统计编码 统计编码是根据信息码字出现概率的分布特征进行压缩编码，寻找出现概率 与码字长度间的最优匹配。常用的统计编码技术有哈夫曼( h u f f m a n ) 编码和算术编 码。在当前流行的图像编码方案中，统计编码很少独立使用，往往是作为变换编 码的后续手段使用。统计编码把变换和量化后得到的符号序列通过进一步的无损 压缩，转化成为二进制位流，完成图像的最后一步工作。 经典的图像压缩编码方法都是非常优秀的编码方法。它们能够在中等压缩比 的情况f ，提供非常好的图像质量。但是在较低位率的情况下，它们无法提供令 人满意的重建图像质量。上个世纪八十年代初期，第一代编码技术已经达到了顶 峰。 由于图像编码的经典方法以独立的象素或波形作为编码对象，没有考虑到图 像本身整体的结构特点和频率分布特性，也没有考虑到人类视觉系统的特性，其 恢复例像不能达到很好的主观满意度。 1 9 8 8 年在图像压缩编码的发展历史中是极为重要的一年。4 0 年的研究成果集 中表现在确定了h 2 6 1 和j p e g 两个建议的原理框架。首届“6 4 k b s 活动图像编 码工作会议”宣告“模型基”方法必将成为新一代的图像编码方法。而分形和神 经网络应用研究，都取得了令人注目的进展。有人称1 9 4 8 1 9 8 8 年间主要研究的 图像编码方法为经典方法，同时把有重要发展前景的图像编码方法称为现代方法。 现代方法主要有小波变换编码、分形编码、模型基编码、神经网络编码等。 小波变换编码是将原图像信号分解成不同的频率区域，根据人的视觉、图像 的统计、细节和结构等特性，对不同的频率区域采取不同的压缩编码手段，从而 使数据量减少。小波变换的本质是多分辨率或多尺度地分析信号，适合人眼视觉 对图像的m u l t i r e s o l u t i o n ，m u l t i s c a l e 效应，即人眼视觉分辨率的不均匀性。 分形图像编码主要是利用图像的自相似性，有效去除图像数据之间局部的相 关性和整体与局部的相关性，从而达到压缩的目的。图像的相似性的描述是以仿 射变换确定的，而仿射变换的系数远远小于相应图像的数据量，所以可以达到经 典方法不能达到的压缩比。由于自然景物都存在着不同程度的自相似性，所以适 用范围广。 基1 二模型或知识的编码方法是在编码端通过各种分析手段，建立一定的模型 来描述待编码的图像，同时提取模型的特征与状态参数并进行编码。在解码端依 据这些参数，利用模型及相关知识生成所建模的信源。这种方法计算复杂度较高， 6 第一章绪论 并且通用性比较差，所以模型编码技术目前还处丁- 进一步研究中，尚未成为成熟、 通用的编码技术m 】。 总之，图像编码的现代方法都是在编码时对信源进行分析，将其分解成一系 列更易于表示的“基元”，或从中提取出若干更本质的参数，进行编码。在解码时 借助一定的规则或模型，按定的算法，将这些基元或参数再“综合”成原图像 的个逼近，因而与经典方法相比，刚以取得更大的压缩比。 l - 3 图像压缩方法的评价标准 图像的压缩编码，其实质是在一定质量条件下，以最少比特数来表示( 传送) 一幅图像。为了比较各种压缩编码效率，需定义表示其压缩效率的压缩比，通用 的压缩比可定义为： r b ( i ，j ) r c ( i ，j ) 式中，吒为原始图像每象素使用的比特数；为压缩后平均每象素使用的比 特数。上式给出了原信息率和压缩后信息率之间的关系。 通常以8 比特象素为基础来规定压缩比，即在没有进行数据压缩的p c m 量化比特数n = 8 经过压缩编码后，平均每个象素的平均比特数为，则编码的压 缩比为 e：旦(1-2) 图像质量的评价是对图像压缩与处理系统优劣的检验。虽然图像质量评价与 人的视觉心理有关( 即对图像的认识或理解是由感觉和心理状况来决定的) ，但是 找个合理的图像质量评价方法还是很有必要的。 一般地，允许图像压缩后再恢复的图像具有一定误差，因此需要某种准则来 评价压缩后图像的质量。保真度准则就是这样一种压缩后图像质量评价的标准。 保真度准则有两种：客观保真度准则和主观保真度准则。前者是以压缩前后图像 的误差来度量的，后者则取决于人的主观感觉。 1 3 1 客观评价 客观保真度准则指原图像和压缩后图像之间的均方误差或压缩后恢复图像的 信噪比或峰值信噪比。 7 。v厶盟。v厶芦 。旦。h l l ( 华南理工大学工学硕士学位论文 对f m n 大小的灰度图像，设原图像为f ( i d ) ，压缩后恢复图像为，( ，j ) ， 其中i = 0 ，l ，m ，j = o ，j v 。 则均方误差为： 圳肛赤善荟( ，( f 舶“彬 ( 1 - 3 ) 归一化均方误差为： nmse：ms，e(1-4) 盯， 其中；2 斋善善心m 信噪比为： 仃： s n r ( d b ) = 1 0 l o g l ( 如) = 一l o l o g n m s e ( d b ) ( 1 5 ) m s e 、 、 峰值信噪比为： p s n r = 1 0 1 0 9 朋2 5 泄5 2 ( 诒) ( 1 6 ) 1 3 2 主观评价 由于被处理的图像最终是为了让人进行观察，那么用人的视觉来评价图像的 质量就更加有意义。事实上，具有相同客观保真度的不同图像，在人的视觉中可 能引起不同的视觉效果。这是因为客观保真度准则是一种统计平均意义下的度量 准则，对于图像中的细枝末节它是无法反映出来的。而且人的视觉系统还有许多 特殊的性质，例如对光强敏感的对数特性，使得图像暗区的误差比其亮区的误差 影响更为重要。又如人的视觉系统对灰度突变的特别敏感性，使得发生于图像边 缘轮廓附近的误差，比发生于一般背景上的误差对图像质量有着更坏的影响等等。 所有这些呵能引起视觉明显差异的因素，用客观保真度准则往往是无法表示出来 的，因此，根据人的主观感觉来评价图像就十分必要了。 主观评价的任务就是要把人对图像质量的主观感觉与客观参数和性能联系起 来，只要主观评价正确，就可以用相应的客观参数作为评价图像质量的依据。主 观测试结果可以是一个单一数值，如平均判分m o s ( m e a n o p i n i o ns c o r e ) ，也可以 是同时反映判断差异的一组数值，比如多值计分( m d s ) 测试【6 j 。 8 第一章绪论 1 4 分形图像压缩 分形理论是卜世纪7 0 年代产生的一fj 新兴学科。分形图像压缩是分形理论证 图像压缩领域的应用。分形图像可以看作一种具有复杂几何形状，但其内部存在 无穷多个a 相似性的图像。可以用一组表示仿劓变换的迭代函数方程描述这些相 似性。并且，分形图像可以通过这个迭代函数系统多次迭代而得到。任何图像都 可以近似为分形图像，那么只要找到其图像内部存在的自相似性，得到自千日似迭 代函数系统，就可以通过迭代函数系统的多次迭代而得到图像。 分形编码方法的目的是发掘自然物体在结构上的自相似性，而这种自相似性 是图像整体与局部相关性的表现。分形编码正是利用了分形几何中的自相似的原 理柬实现的。首先对图像进行分块，然后再去寻找各块之间的相似性，这罩相似 性的描述主要是依靠仿射变换来确定的，一旦找到了每块的仿射变换，就保存下 这个仿射变换的系数，由于每块的数据量远远大于仿射变换的系数，因而图像得 以大幅度的压缩。 分形图像压缩方法与其它压缩方法相比较，在保证相同的信噪比下，可以达 到更高的匠缩比。例如，对于幅5 1 2 5 1 2 个象索点的黑白枫叶图像，采用以离 散余弦变换为核心的压缩方法，压缩比在8 2 0 倍左右：通过精心调整的小波变 换方法，压缩比可达到1 0 0 左右；如果采用分形图像压缩编码，自相似迭代函数 系统有2 4 个参数，占2 4 个字节，原始图像占3 2 7 6 8 个字节，压缩比可高达l3 6 5 倍( 如图l 一5 ) 。由此可见，分形图像压缩方法具有高压缩比的应用前景 5 ，8 】。 幽1 - 5 枫叶图像 f i g1 - 5t h ei m a g eo fm a p l el e a f 9 华南理工大学工学硕士学位论文 1 5 本文研究目标 1 + 5 1 研究目标 在全面、深入研究分形理论、图像压缩方法以及分形图像压缩技术的基础上， 针对幽像本身的獗度分稚特征，考虑到人跟对灰度的敏感程度与背景有关的视觉 特性，提出了一种具有较高压缩效率的基于图像特征的分形图像压缩算法。 1 5 2 研究思想 传统的分形图像编码方法，都是将图像划分为形状规则的图像块进行处理的， 这种规则分块的方法有很大的局限性。因为图像的内容是丰富多变的，规则的图 像块很容易把图像的内容割裂开来，影响解码图像的质量。基于这种考虑，本课 题在研究过程中，主要对图像块划分和参数存储两方面进行改进。在图像分块阶 段，首先将图像划分为较小的图像基块，根据基块的平均灰度值与灰度方差值对 图像进行特征提取，然后对特征分布图中的基块进行区域合并，从而形成大小、 形状f i 一的图像块，再对这些图像块进行编码。出于图像块的形状各异，采用对 图其形状参数单独存储的方法，利用参数问的空间关系去除参数存储的冗余。解 码时，按照编码参数对任一初始图像进行反复迭代重构得到恢复图像。 1 5 3 论文的组织 本文共分为四章。第一章绪论部分介绍本课题的研究背景与意义、图像压缩 技术、分形图像压缩编码以及本研究的目标。第二章论述分形图像编码的数学基 础与理论基础。第三章讨论分形图像编码的基本原理、基本方法和改进算法。第 四章阐述本文提出的基于图像特征的分形图像编码方法，并给出用该方法得到的 实验结果与分析。文章的最后是全文的结论，提出了进一步工作的展望。 1 0 第二章分形图像压缩的基础理论 ! s ! ! g ! ! ! ! ! 自自| ! s ! ! ! 目! ! ! ! ! ! e ! ! ! 皇i i i i i i ! ! ! ! ! e ! ! ! ! ! e ! ! ! ! ! e ! ! ! ! ! ，! ! ! ! ! ! ，e ! ! ! ! ! ! ! ! ! ! ! ! ! 摹 第二章分形图像压缩的基础理论 2 1 分形的概念 分形的原文f r a c t a l 是b ，m a n d e l b r o t 用拉丁词拼造的单词，意思是细片、破碎、 分数、分级等。m a n d e l b r o t 说“1 9 7 5 年，我由描述碎石的拉丁文f r a c t u s ，创造出 f r a c t a l ( 分形) 一词，分形是几何外形，它与欧几里德外形相反，是没有规则的， 首先它们处处无规则可言，其次它们在各种尺度上都有同样程度的不规则性。” 分形是描述不规则几何形态的有力工具。 到目前为止，分形还没有确切的简明的定义，但是分形的集合具有如f 特征： ( 1 ) 该集有精细结构，即在任意小的比例尺度内都包含整体； ( 2 ) 无论从局部和整体来看，分形集都是很不规则的，无法用传统的几何语言 来描述； ( 3 ) 通常分形集都有自相似性，可能是近似的，也可能是统计意义； ( 4 ) 通常分形集的“分形维数”比它的拓扑维数要大； ( 5 ) 许多情况下，分形集是非常简单的，或者是递归的【i j 。 分形是人们在自然界和社会实践活动中所遇到的不规则事物的一种数学抽 象。人们对丁二分形的兴趣是由于可以用它来描述和解决一些实际问题，正如历史 上人们对于欧氏几何与微积分的应用叶￥，这种描述和应用允许在一定尺度下的 近似性。同样，在利用分形来描述海岸线、云层的边界、地表的形状、岩石的裂 缝、流体的湍流以及一些经济现象时，也具有一定意义的近似性。实际l ，现实 世界c p 没有真正的分形，正如m a n d e l b r o t 所强调的那样，自然界的分形与我们数 学中讨论的分形是有区别的。 分形理论的发展是迅猛的，分形的思想和方法正日益影响着现代社会的生活 和活动，随着分形的，泛应用，一些新的数学方法和数学工具被不断提出，所有 这些都显示了分形理论的强大生命力。 分形具有广阔的应用前景，在分形的发展过程中，它已渗透到各个学科领域。 在数学、物理、化学、材料科学、生物与医学、地质与地理学、地震和天文学、 计算机科学乃至经济、社会、艺术领域，都不断发表大量的学术论文。许多传统 的科学难题，由于分形的引入而取得显著进展。 华南理工大学工学硕士学位论文 2 2 分形方法压缩图像的依据 根据分形理论，不少复杂的图形，从计算的观点看来，其信息含量并不大， 可以用简单的程序来产生。 比如蕨类植物的图形，看上去比较复杂，用一般图形表示法要用上万个数据 但采用分形方法，依据仿射变换w ( 习= 匀= ( ： 匀+ ； ，仅需z 。个数据 用迭代函数系统( i f s ) 方法便可在计算机上产生这种图形( 如图2 - 1 ) 。 a 0 08 5 0 2 0 1 5 扫 0 0 0 4 - 0 2 6 0 2 8 c 0 0 0 4 o 2 3 0 2 6 d 0 1 6 0 8 5 0 2 2 0 ，2 4 0 1 6 1 6 0 4 4 圈2 - 1 迭代函数系统生成的蕨类植物图形 f i g2 - 1f e r nf i g u r eb a s e do ni t e r a t i v ef u n c t i o ns y s t e m 这说明，通过迭代这全反馈的动态过程，用参数不多的算法就可以在计算机 卜显示出相当复杂的自然图形，复杂的图形寓于简单的算法之中。这是可以采用 1 2 ， 第_ 二章分形图像压缩的基础理论 分形方法进行图像压缩的 要根据之一。 科学家竹 发现，自然界许多事物的发展过程，如生长、凝聚、进化等，形成 多种分形结构。理论生物学家推测，在形态发生的过稃中，分形结构不仅是常见 的，而目是普遍的。 树木的枝叶呈分形，用以获取阳光、空气和抵抗风力。在植物和种子里，只 有一定的信息为这种植物编码，所以植物的复杂程度是有限的。它不过是在生长 过程中新陈代谢( 不断迭代) 而形成的分形形态。 因此，分形意味着自然界是许多复杂形态中潜藏着有组织的结构。大自然的 荚，就在于她在本质上是简单的。如果我们能找到这些有效的信息，我们就能简 洁地表述自然界的图景。 这是我们能够采用分形方法进行图像压缩的另一个重要根据”1 。 当然，这些称为分形的自然体，没有一个是真正的分形。它们只是在一定的 尺度内表现得非常像分形，在这种尺度范围内可以看作分形。“自然分形”与数学 上的“分形集”是有区别的，本质上不存在真正的分形，就像并不存在真正的线 和同一样。但是，这并不妨碍我们用欧几里德j l 何去描述物体的形状，也不妨碍 我们用分形去进行图像压缩。 2 3 分形编码的数学基础 2 3 1 分形几何与维数 人类在认识世界和改造世界的活动中离不开几何学。在历史上，科学技术的 发展与几何学的进步始终是密切相关的。 计算机特别是计算机图形学的迅速发展，使人们在使用计算机深入探讨一系 列问题的过程中，逐渐感到，用传统的几何学已不能有效地描述某些自然界大量 存在的对象，如：海岸线、山形、河川、岩石、树木、云团、闪电等。它们都是 非规则形状，用欧几里德几何学是无能为力的。计算机图形学在自然景物的模拟 以及动画的制作中，如果用直线、圆弧、样条曲线等去建模生成，则其逼真程度 就非常差。 另外，在科学研究中，对许多非规则对象建模分析，如：星系颁布、凝聚生 长、渗流、金融市场的价格浮动等复杂对象，都需要一种新的几何学来描述。 l9 7 3 年，b b m a n d e l b r o t 在法兰西学院讲课时，首次提出了分维和分形几何 的设想。分形几何是一门以非规则几何形状为研究对象的几何学。由于不规则现 象在自然界是普遍存在的，因此分形几何又称为描述大自然的几何学。 分形几何建立以后，很快就引起了许多学科的关注，这是由于它不仅在理论 1 3 华南理工大学工学硕士学位论文 上，而且在实用卜都具有重要价值。 与传统几何学相比，分形几何有以下特点： ( 1 ) 从整体上看，分形几何图形是处处不规则的。例如，海岸线和山川形状， 从远距离观察，其形状是极不规则的。 ( 2 ) 在不同尺度上，图形的规则性又是相同的。上述的海岸线和山川形状，从 近距离观察，其局部形状又和整体形态相似，它们从整体到局部，都是自相似的。 当然，也有一些分形几何图形并不完全是自相似的。其中一些是用来描述一般随 机现象的，还有一些是用来描述混沌和非线性系统的。 分形几何与传统的几何完全不同，传统的欧几里德几何的对象具有一定的特 征长度和标度，其所描述的是人类生产的工业产品的规则形状。分形几何则是无 特征长度与标度的，它擅长描述自然界普遍存在的景物，分形几何的图形具有自 相似性和递归性，它比较适于用计算机迭代生成1 0 | 。 为了定量地描述客观事物的“非规则”程度，1 9 1 9 年，数学家从测度的角度 引入了维数的概念，将维数从整数扩大到分数，从而突破了拓扑集维数为整数的 界限。分数维可以用束表示分形集的不规则程度。 在分形中，人们对维数进行了更深入的研究和理解，提出了许多关于维数的 新概念。常见的有： f 1 ) 相似性维数 如果某图形是由把原图缩小为l a 的相似的b 个图形所组成，有： d d ；b d ：l o g bf 2 1 ) l o g a 的关系成立，则指数d 称为相似性维数，d 可以是整数，也可以是分数”】。相似 性维数，通常被定义为具有严格自相似性的维数。对于具有不同的非整数维数的 图形或几何对象来说，维数愈大，其复杂性就会相应提高。 (