（计算机应用技术专业论文）基于区域分类的分形图像编码算法研究.pdf

西华大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：涨芬 日期：yii 6 j 指导教师鲐叮吨吁 日期2 口fi 、f 西华大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，在校 攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文。( 保密的论文在解 密后遵守此规定) 学位论文作者签号：，办者 指导教师签名：彳 日期：zp 。、 日期口、多：r 哆t ，字 l 西华大学硕士学位论文 摘要 在各种多媒体服务和数字通信等应用领域，图像编码是至关重要的技术之一。上世 纪9 0 年代，分形图像编码作为一种全新压缩编码方法开始兴起，它的整体理论是建立 在图像自相似基础之上的。由于大量的自相似几何形状存在于自然界中，因此，在压缩 过程中不仅要考虑到图像中局部与整体之间的相似性，更要考虑局部与局部之间的相似 性，因此就处理对象为自然图像的压缩情况来讲，分形编码技术将有很广的适应范围。 随着计算机技术的发展，虽然图像的分形编码技术在不断改进，但其结果仍然不够理想， 离实用化还有相当的一段距离。目前，分形编码的不足之处还有：解码图像的效果还不 够理想，编码速度还有待于提高，产生的压缩比还没有达到理论上的水准。但我们通过 理论分析知道，编码速度慢是分形编码不能走向实用化的最大障碍，但也是可以优化的， 分形图像编码的潜在优势还有很大的上升空间。 本文的研究工作主要如下： ( 1 ) 详细分析了分形编码的编码和解码算法的实现过程，在编码实现的基础上，通过 实验验证了子块分割大小和父块等距变换次数两大因素对分形编码性能的影响。 ( 2 ) 详细分析了人类视觉系统的相关特性以及视觉特性与图像纹理的相关性，并进一 步探讨了将视觉特性应用于图像编码的改进方案。 ( 3 ) 分析出了利用图像区域分类来实现在保证图像主观质量的前提下，提高分形编码 时间性能的方案。重点提出了综合考虑各种视觉影响因素来进行图像区域分类的方法， 按照本文的改进算法思路，能很好的将图像分割的子块划分为平滑区域、纹理区域和边 缘区域三类。 通过最终的实验结果，验证了本文分析出的从图像质量和编码时间方面改进分形编 码的新方案的有效性。改进是通过使用适应码本缩减策略实现的，即从人眼视觉特征出 发，在保证图像质量的情况下，减少匹配码本数量，与对应的全搜索分形算法比较，在 解码图像主客观质量没有明显下降的前提下，编码时间大大减少。 关键词：分形编码；迭代函数系统；人类视觉系统；粗糙度 基于区域分类的分形图像编码算法研究 a b s t r a c t i nv a r i o u sm u l t i m e d i as e r v i c e sa n dd i g i t a lc o m m u n i c a t i o na n do t h e rf i e l d so f a p p l i c a t i o n , i m a g ec o d i n gi sc r u c i a lt e c h n i c a lo n e i nt h e19 9 0 s ，f r a c t a li m a g ec o d i n ga san e w c o m p r e s s i o nc o d i n gm e t h o d ，i tb e g a nt or i s et h ei n t e g r a lt h e o r yi sb a s e do ni m a g es e l f - s i m i l a r f o u n d a t i o n b e c a u s eal o to fs e l f - s i m i l a rg e o m e t r ye x i s ti nn a t u r e ，t h e r e f o r e ，i nt h e c o m p r e s s i o np r o c e s ss h o u l dn o to n l yc o n s i d e rt h ei m a g es i m i l a r i t yb e t w e e nt h er e g i o n a la n d g l o b a l ，r e g i o n a la n dl o c a lm o r et oc o n s i d e rt h es i m i l a r i t yb e t w e e nt h eo b j e c t ，s oi tc a l lh a n d l e f o rn a t u r a li m a g ec o m p r e s s i o nc o n d i t i o ns p e a k i n g ，f r a c t a lc o d i n gt e c h n o l o g yw i l lh a v ea v e r y w i d er a n g e a tp r e s e n t , t h ef r a c t a lc o d i n gd e f i c i e n c ya n d ：d e c o d e di m a g ee f f e c ta l s o i n s u f f i c i e n ti d e a l ，e n c o d i n gs p e e dn e e d si m p r o v i n g , p r o d u c eb e t t e rc o m p r e s s i o nh a v e n t r e a c h e dt h el e v e li nt h e o r y b u tw et h r o u g ht h e o r e t i c a la n a l y s i sk n o w ，e n c o d i n gs p e e ds l o wi s t h ep r a c t i c a lf r a c t a lc o d i n gc a n tt h eb i g g e s to b s t a c l e ，b u ta l s oc a nb eo p t i m i z e df r a c t a li m a g e c o d i n g ，t h ep o t e n t i a la d v a n t a g ew i t hal o to fr o o mt or i s e t h e s t u d y i nt h i sp a p e rm a i n l ya sf o l l o w s ： ( 1 ) t h ed e t a i l e da n a l y s i so f t h ef r a c t a lc o d i n ge n c o d i n ga n dd e c o d i n ga l g o r i t h m ，a n dt h e r e a l i z a t i o np r o c e s so ft h eb a s i so ft h ec o d i n gr e a l i z e , v e r i f i e db yt h ee x p e r i m e n t ss u b - b l o c k d i v i s i o ns i z ea n df a t h e rb l o c ki s o m e t r i ct r a n s f o r mn u m b e rt w ob i gf a c t o r so nt h ei n f l u e n c eo f f r a c t a lc o d i n gp e r f o r m a n c e ( 2 ) t h ed e t a i l e da n a l y s i so ft h eh u m a n v i s u a ls y s t e mr e l a t e dc h a r a c t e r i s t i c sa n dv i s u a l c h a r a c t e r i s t i c sa n di m a g et e x t u r e , a n df u r t h e rd i s c u s s e st h ec o r r e l a t i o no ft h ev i s u a l c h a r a c t e r i s t i ca p p l i e dt oi m a g ec o d i n gt h ei m p r o v e m e n ts c h e m e ( 3 ) b yu s i n gt h ea n a l y s i so fi m a g er e g i o nc l a s s i f i c a t i o nt oa c h i e v ei ng u a r a n t e eu n d e r t h ep r e m i s eo f s u b j e c t i v ei m a g eq u a l i t yf r a c t a lc o d i n gt i m ep e r f o r m a n c e f o c u s e so nt h e c o m p r e h e n s i v ec o n s i d e r a t i o no f t h ev a r i o u sv i s u a li n f l u e n c ef a c t o r st ot h em e t h o do f i m a g e r e g i o n , a c c o r d i n gt ot h i sa r t i c l ec l a s s i f i e di m p r o v e da l g o r i t h mo fi d e a s ，c a l lb eav e r yg o o d w i l li m a g es e g m e n t a t i o ns u b - b l o c ki sd i v i d e di n t os m o o t ha r e a , t e x t u r ea r e aa n de d g e sa r e a t h r o u g ht h ef i n a le x p e r i m e n tr e s u l t ss h o wt h a tt h i sa n a l y s i so f t h ei m a g eq u a l i t ya n dt h e e n c o d i n gt i m ef r o mi m p r o v ef r a c t a lc o d i n gt h ee f f e c t i v e n e s so f t h en e w p l a n t h r o u g ht h eu s e o fi m p r o v e m e n ti st or e a l i z et h i sr e d u c t i o ns t r a t e g yo fc o d e ，t h a ti s ，f r o mh u m a nv i s i o n r e m a i n sc h a r a c t e r i s t i ce m b a r k s ，e n s u r et h eq u a l i t yo fi m a g ec a s e s ，r e d u c et h eq u a n t i t y , a n d m a t c h i n gc o d e sc o r r e s p o n d i n gf u l ls e a r c hf r a c t a la l g o r i t h mi nd e c o d e di m a g ec o m p a r i s o n , s u b j e c t i v ea n do b j e c t i v eq u a l i t yu n d e rt h ep r e c o n d i t i o no f n oa p p a r e n td e c l i n e ，c o d i n gt i m e g r e a t l yd e c r e a s e k e yw o r d s ： f r a c t a lc o d i n g ；i t e r a t e df u n c t i o ns y s t e m ；h u m a nv i s u a ls y s t e m ；r o u g h n e s s i i 西华大学硕士学位论文 目录 摘要j i a b s t r a c t i i 引言1 l 图像压缩概述2 1 1图像压缩简述2 1 2 图像压缩的可行性与方法分类2 1 2 1图像压缩的可行性2 1 2 2图像压缩编码的分类4 1 3图像压缩技术的发展与性能评价6 1 3 1图像压缩技术的发展6 1 3 2图像压缩技术的评定7 2 分形图像编码概述1 0 2 1 分形的概念1 0 2 2 分形理论的起源和发展1l 2 3 分形图像压缩简介一1 2 2 4 分形图像编码的最新研究进展1 3 3 分形图像压缩算法的分析1 6 3 1 局部迭代函数系统。1 6 3 2 分形编码的基本算法17 3 3 分形解码的基本算法19 3 4 子块分割大小对性能影响的验证2 0 3 5 父块等距变换次数对性能影响的验证2 7 4 根据区域特征进行匹配的改进算法3 1 4 1基于视觉掩盖效应的改进算法31 4 1 1 人类视觉系统模型。3 1 4 1 2 视觉特性与图像纹理分析。3 2 4 1 3 改进算法对视觉特性的运用3 4 4 2 改进算法的实现方法3 4 4 2 1 利用粗糙度算法进行图像区域划分3 4 4 2 2 利用图像纹理特征参数进行图像区域划分3 6 4 2 3 综合考虑各种视觉特性进行图像区域划分3 9 i i i 基于区域分类的分形图像编码算法研究 4 2 4 根据不同特征的区域块进行匹配4 4 4 3 实验结果与讨论4 5 论z 1 9 考文献5 0 读硕士学位期间发表的论文及科研成果5 3 谢5 z l i v 西华大学硕士学位论文 引言 本论文的研究对象是分形图像编码技术，主要是归纳了对这一技术进行优化和改进 的一些方向，关于这一论题在国内外都有许多文献从不同方面进行了讨论。本论文希望 通过对研究分形编码原理，从考虑人眼视觉特性这一方面对分形编码性能如何进行优化 进行一些探讨。 随着分形理论的发展和各种不同的分形编码优化算法的提出，分形的应用已经迅速 扩展到了数字图像处理、机器视觉等领域，并为这些领域的相关理论发展做出了巨大的 贡献。在分形理论产生前，并没有合适的工具来表示自然万物本身所具有的相似性，这 就给对于这种自相似性比较明显的物体进行分析造成了不便，分形理论的产生一举改变 了这一局面，成为了众多学科研究自相似性现象的一个重要工具，广泛应用于数学、自 然科学和社会科学等众多领域中，成为了非线性科学研究中一个十分活跃的分支。 目前，国内外的研究人员提出了众多分形编码的改进方案，从各种改进方案中，我 们可以看到，在分形编码中存在着加快图像压缩速度和提高解码图像质量这样一对矛 盾。要想加快压缩算法速度，必然需要在编码过程中丢失部分图像数据，但这样一来， 丢失的部分图像数据必然会使解码的图像质量有所下降；反过来，要想解码图像质量损 失较少，必然要求在压缩过程中尽量避免图像数据的损失，这对时间性能的提高提供不 了多少上升空间。所以，如何能够在提高压缩速度的同时，也不会对解码恢复图像的质 量造成太大的损坏，是以后的分形图像编码方案改进的主要目标。 人类的视觉系统从生理上来讲是相当复杂的，但在图像领域，我们可以简单地把它 看成是一个接受一处理系统，视觉特性就是指这个系统中接受和处理之间的关系。以下 几种特性在人类视觉系统中表现得最为突出： 对比灵敏度。大量的实验表明，在对亮度进行判断时，人眼是不能够正确判断出 亮度的绝对大小值，但是当在需要区分几种亮度值中哪个值更大时，人眼却有良好的表 现。在数字图像中，灰度值被用来量化图像的亮度，通过采样和量化操作，一幅数字图 像往往被表示为一串离散灰度值。 西华大学硕士学位论文 需要保证解码图像的亮度值大小趋近于原图像即可，而不需要强求有太大的亮度范围， 以此可以达到压缩数据量的目的。 空间分辨率。人眼能够正确区分相邻的两个发光点的能力就是利用了视觉系统中 的空间分辨率特性。通常用最小视角来表示能够分辨两个发光点的空间分辨率特性，这 种最小视角一般小于5 度。也就是说，当图像的像素值在某个方向上变化得太快时，这 种空间的快速变化可能会超出人眼的可以接受范围，最终导致人眼将无法再分辨相邻的 像点。 时间分辨力。有一些观测对象会随着时间而变化，人眼对于这些目标的分辨力大 小就称为视觉系统中的时间分辨力。从时间频率域上来，人眼的视觉惰性和频闪效应等 使人眼的视觉特性也是呈低通特性的。 可见度域值。人眼刚好能发现的干扰值即是视觉系统中的可见度域值，低于该域 值的干扰是不能被人眼所察觉出来的。 通过上面对人眼视觉系统各种特性的分析，我们知道人眼的视觉能力受限于很多方 面。因此，我们可以合理的把这些视觉特性运用于我们的编码技术中，对于人眼因受限 制而不能观测到得信息，我们可以进行减少信息量的处理，折中地实现了对图像数据的 压缩处理，既减少了图像的数据量，又不影响人眼对图像的使用质量。 ( 2 ) 图像的统计特性 在图像压缩领域，研究图像的统计特性也是一项非常有意义和必要的工作。像素之 间的相关性普遍存在于我们的图像当中，这也就给我们进行图像压缩提供了可能，比如 我们可以使用适当的编码方法删去像素之间的关联性，从而达到减少冗余的目的。从空 间域和频率域两方面来看图像的统计特性，我们可以了解到如何进行有效的图像编码将 在很太程度上取决于图像采样值之间存在的这些联系和规律。 图像的空间域统计特性。数字图像中像素点之间的相关性即是图像的空间域统计 特性。通过观察任意一幅数字图像，除非是一幅纯色图像，我们可以发现邻近的像素之 间灰度值虽然并不总是相等的，但极其近似。这也就充分证明了很强的相关性是存在于 图像的像素之间的。 图像的频率域统计特性。图像在不同的频率域上则表现为不同的能量分布。图像 中的平滑区域在频率域中就处于低频部分，而图像的纹理或结构区域则对应于高频部 分。 图像的编码系统如图1 1 所示：原图像m 经过图像压缩处理后生成对应信息n ，再 经存储介质存为文件。在使用时，进行图像解压缩以获得恢复图像m ，。或者图像文件n 经过通信媒体进行信道的编码和解码得到n ，再经解压缩获得恢复图像m 】。图1 1 表示 了这两种不同的编码系统。 基于区域分类的分形图像编码算法研究 m 固n 一匝d 亟丑m ， m t 日n 一匝丑叫叵母m t 图1 1 图像编码系统 f i g 1 1i m a g ec o d i n gs y s t e m 1 2 2 图像压缩编码的分类 从不同的角度进行考虑，图像数据编码技术可以有多种分类方法。最通用的分类方 法是，根据原图像与解压图像之间有无数据丢失，分为有损编码和无损编码两大类。然 而，在实际应用中，最常用分类的方法往往是按照编码的基本理论和原理来进行的。按 照编码的基本理论和原理，图像编码技术主要可以分为以下几类： ( 1 ) 预测编码 、 预测编码是利用相邻像素之间存在的高度相关性，以当前已经传出的近邻像素值作 为参考，先对当前值进行预测得到预测值，再与原像素的真实值进行求差，最后对差值 进行编码。为了进一步压缩数据量，还可以使用无失真编码，这是因为差值的熵值一般 不大，而且还可以利用人的主观视觉特性实现有针对性的量化处理。 ( 2 ) 变换编码 变换编码的原理是将一组像素值经过某种形式的正交变换( 目前最常用的是离散余 弦d c t ) 形成一组变换系数，然后再根据各种量化方案( 比如说人的主观视觉特性) 来 对每个变换系数进行量化操作，再对量化后的数据进行常规编码的技术。删除像素之间 的强相关性是进行正交变换的目的，以此可以降低冗余度。在众多的正交变换中，离散 余弦变换是最与k l 变换性能相接近的，因此，目前的大多图像编码的国际标准都采用 了离散余弦变换。 ( 3 ) 熵编码 也称统计编码，这是一类无损编码。它的理论依据是信息熵原理。在进行编码时用 短码来表示出现概率高的信息，而用长码来表示出现概率低的信息。最为常见的熵编码 有游程编码和哈夫曼编码，它们均在目前的国际编码标准中有着广泛的运用。 ( 4 ) 子带编码 4 西华大学硕士学位论文 分析一综合类的编码技术一般的原理是先分解，再处理，最后再合并，子带编码是 其中的一种。它的基本编码思想是，在编码时，先预处理图像信号，常用的手段一般是 在频率域内把原信号分解成不同特性的子带，然后再根据各个子带的不同统计特性，在 众多的编码器和比特分配方案中，选择与之相适合的进行数据压缩；在解码时，首先用 不同的解码方法对每一个子带进行解码，最后再合并解码后的各子带信号。该编码的特 点在于： 噪声不会扩散。由于每个子带是分别进行压缩与解压操作，所以单个子带的噪声 不会扩散。实验表明，使用子带编码进行图像处理，最容易被噪声感染的高频细节仍有 很好的还原度。 充分利用视觉特性可以很好地控制住编码噪声的频谱，使人眼不同的敏感程度都 能得到更大的满足。从而在进行编码时，可以在各个子带之间采取适当的编码方案，这 样加强了图像的恢复质量也可以达到进一步压缩数据的目的。 根据不同的特性进行子带分解，则把子带编码的运用扩大到了需要质量可分级的 图像处理领域中。目前，对小波变换理论的合理运用是子带编码进行子带分解的保证。 ( 5 ) 矢量量化编码 先把图像按照一定的策略进行分块，每块的像素组成一个矢量，再对每个矢量再进 行编码，这就是矢量量化的编码方案。在图像分块之后，我们可以用一个矢量来代表很 多比较相近的子块，在编码时，只需要对这些数量少于子块数量的矢量进行编码即可。 在解码时，我们可用这些矢量的码字来恢复图像。 。( 6 ) 模型编码 该编码技术的操作对象是模型的参数，在实际编码阶段，先按照一定的分割策略把 图像按照其内容定义划分成几个模型，这样的模型完全可以用对应的几个参数来表征， 以此只需要对这些参数进行编码即可，它是一种以模型为基准的参数编码方法。 基于分形理论的图像压缩方法是介于模型编码和矢量量化编码之间，但它又有自己 的独特之处，在当前主流的分形编码中，是把每一个分割后的子图像当作一个分形进行 处理，通过利用每个分形的迭代函数的参数，在解码阶段，就可以通过作用于任意图像 恢复原来的子图像，当每个子图像都被恢复出来时，解码图像也就生成了。然而，在实 际运用当中，并不是每个子图像都是完全属于分形的，所以在该理论当中，每个子图像 只是被看作逼近于分形，则分形编码是一种有损编码。 5 码技术。 第二代编码技术充分考虑到了第一代编码技术中的不足之处，即在压缩比高的情况 下，图像解压后的恢复质量不能被人接受；尽管在压缩比中等的情况下，图像恢复效果 能够令人满意，但对高压缩率高质量这一标准的追求在第一代编码技术中并未实现。通 过对第一代编码技术的全面分析，可以看出第一代技术中并没有考虑到人类视觉系统的 特性，同时也没有充分利用图像的结构特点，因此它们也就只能以像素或块作为编码的 对象，并不能达到令人满意的效 西华大学硕士学位论文 而第二代编码技术不再局限于信息论的框架，其所利用的理论模式也远远多于第一 代编码技术，随着相关理论的发展与突破，像分形理论，神经网络理论等被应用于图像 编码技术中，为图像编码的发展翻开了新的篇章。对这些新理论进行研究和分析，可以 看出来，它们的最大特点是在第一代编码技术的基础上，进一步挖掘了技术与图像特征 的适应性，无论在编码还是解码阶段，都充分考虑到了人类视觉对图像的感知特性，这 样一来，不仅在压缩比上得以提高，而且也保证了图像的恢复质量能够被人眼所接受。 随着第二代编码技术的发展，像分形图像编码这样的新编码技术也登上了历史舞台。 子带编码和基于小波变换的编码等是属于在第一代和第二代编码技术之间，产生出 来的一些过渡编码技术。这类方法对图像整体进行分解，一般分解成高低频部分分别进 行处理，为了使图像编码的压缩率和最终解码图像质量都有所提高，这类编码技术充分 利用率人类视觉特性，对高频段的数据采用了粗量化的方式以获得比较高的压缩率，而 这样的处理方式也能够让恢复图像质量被人眼所接受；而对于低频部分，由于这部分数 据直接决定了人眼对恢复图像的整体感知效果，所以对这一部分采用了细量化的处理方 式。这类编码方式的总体特征是，不仅充分利用了图像的结构特点，在技术操作阶段还 涉及到了对人类视觉特性的考虑。 1 3 2 图像压缩技术的评定 伴随着图像编码理论的发展，众多的编码技术被提了出来，如何判定一种编码技术 的优劣也成了图像编码发展中重要了的一环，目前最为通用的判定指标有以下三个方 面。 ( 1 ) 压缩算法性能：作为编码技术最为重要的一环，压缩算法的运算时间往往决定 了一种编码技术能否走向实用化，对如何减少压缩时间是众多研究人员的重要课题。另 外还要从算法结构的优化来考虑该算法是否容易实现、运算量是否适当。 ( 2 ) 解码算法性能：在图像编码技术运用的实际环境中，往往要求能够对图像进行 实时解码，因此解码算法的实时快捷性极其重要，这也对解码算法在时间性能上提出了 较高的要求。应用中往往是对图像压缩只需要进行一次，而后反复解码于这个压缩文件 以恢复图像，所以在实际运用中，解压比压缩更为强调时间性能。 ( 3 ) 重建图像质量：为了提高压缩率，编码技术运用得比较广的多是有损编码，这 样一来，源图像与解压恢复的图像不可避免的存在着一定的误差。恢复图像质量的好坏 也完全取决于这种误差的大小。但如果考虑到人眼的视觉效应，那么对恢复图像质量的 主观感觉并不绝对取决于这种误差的大小。所以，在重建图像方面就有两种角度的判定 方法： 主观方法 基于区域分类的分形图像编码算法研究 主观方法就是在进行质量评价时，其判定结果完全取决于判定人员对图像质量的主 观感受，并不涉及任何客观的计算数据作为参考。在用主观方法进行图像质量的判定中， 一般一幅恢复图像需要反复被一组判定人员进行评价，并打出分数便于统计，待所有判 定人员打分完毕，再参照事前约定的规则汇总分数得出最终结论。对恢复图像质量进行 主观方法评定，对判定者的知识水平有一定的要求，并且使用起来也不够方便，有时不 同的判定者还会得出不同的评价结论，但是在进行图像判定时仍然首推主观方法，因为 从图像的使用途径来看，放在第一位的是保证人眼可以接受，这是因为人的视觉往往是 大部分数字图像最终的接受者。 由于主观方法的判定结果完全取决于判定人员的主观判断，所以为了使判定结果不 失公允，往往对判定人员的数量和身份有一定要求：一般判定组人员的数量要求在2 0 人以上；而判定人员的身份要求不仅包括专业的图像处理研究员，还要有一般的非专业 观众。在主观方法实际进行中，往往是把原图像和恢复图像都呈现给判定人员，让其比 较两者的差异程度。 客观方法 该方法是直接利用数学公式计算解码恢复后的图像与原始图像的差异程度，除了对 图像质量差异的计算，还可以计算出压缩比等方面的指标。最为常用的数学公式有： 均方误差公式： 6 2 = 鼍警赫产 1 ，。 m n 【f ( x ，y ) 】2 一一7 原始图像和恢复图像分别由公式中的眠y ) 、f ( x ，y ) 来表示，m 为图像的长度，n 为 图像的宽度。 p s n r 公式： p s n r = 1 。l n 芝i l i i i f 石2i 歹x j _ 二m _ f n 丽( d b ) ( 1 2 ) 该公式中使用到了图像的最大灰度值，比如二值图像的灰度级为2 ，那么二值图像 的k = 2 。从公式中可以看出，该公式的结果大小精确到了每个像素的比较上，使得 该公式不仅在客观评价中广为运用，甚至对主观感觉的评价也提供了可靠的线索。 压缩比公式： c = 一 ( 1 3 ) n d 西华大学硕士学位论文 c 的数值即为我们通常所说的压缩率，分子、分母分别取原始图像和恢复图像所占 存储空间的大小。 从对压缩技术优劣的判定出发，上面都是一些常用的判定指标。但还没有哪种压缩 技术能够在各种指标上都处于优势，就目前来看，考虑到人眼视觉效应的编码技术往往 在客观评价中得分不高，但却在主观评价方面有很好的表现，所以说，一个好的压缩方 法应该是各个指标的一个较优的折衷。 9 通过对各种分形体的研究，研究人员们总结出了分形具有以下的一些特性： ( 1 ) 从理论上来讲，同自然界中的各种物体一样，分形也是无限可分的。当我们用放 大图像的方式来仔细观察计算机分形图时，总能看到更多的细节，也就是说，分形具有 无限的精细结构。 ( 2 ) 分形体的结构特征决定了它是不能用传统的几何学方法来进行分析的，分形既不 是满足某些条件的点的规矩，也不是某些简单方程的解。然而，分形维却是描述分形体 最恰当的几何量，也就是说分形体的维数一般是分数。 1 0 西华大学硕士学位论文 ( 3 ) 分形体不具有特征尺度。这里所谓的特征是指那些可以表征某一物体特点的尺 度，比如，地球上人的身高不会高于3 米，也不会低于3 厘米，能够恰好度量人身高的 尺度，便是人身高的特征尺度。而分形就不一样了，从理论上讲，用任何尺度看分形， 得到的结果都是几乎相等或者是相当相近的，换句话讲，分形拥有无限个特征尺度，这 也就相当于分形没有特征尺度。 ( 4 ) 一般来讲，分形体的分维数是严格大于组成分形体基本单位的拓扑维数( 类似于 欧氏维数) ，而小于分形体嵌入空间的维数，比如，科切曲线的分维数是1 2 6 8 1 ，而组 成科切曲线的基本单元是线，拓扑维数为1 ；而该曲线又是嵌入在平面中的，而平面的 维数是2 。 ( 5 ) 在大多数情况下，表面看起来十分复杂的分形结构，其实其产生方法的规则都是 非常简单的，般可以借助于计算机编写的迭代函数来实现，所以曼德勃罗说，“复杂 性只是我们用传统的几何方法看分形；从分形的角度看，分形体是非常简单的。 2 2 分形理论的起源和发展 1 9 7 5 年美国科学家m a n d e l b r o t 的专著f r a c t a l ：f r o m ，c h a n c ea n dd i m e n s i o n 发表了，这标志着分形理论作为一种崭新的理论诞生了。随后，分形理论广泛应用于 包括生命信息科学、工程地理技术等在内的各个科学领域，它是现代非线性科学研究 中十分活跃的一个分支。分形理论的数学基础是分形几何，分形几何与之前人们接触到 的规则几何形体不同，它主要是研究不规则几何形体的特征，最大限度的探求不规则几 何形体的规律。分形的思想和方法随着计算机科学技术的迅速发展得到了长足发展，广 泛应用于模式识别、信息控制等众多领域。 十九世纪中晚期，就有一些科学家开始了对分形的研究，当时的研究对象主要是以 大自然中物体的几何形状为主，但在研究过程中，科学家发现传统的欧氏凡何学在描述 这些普遍具有复杂的不规则的形状时显得苍白无力。随后，人们又发现，用确定论来描 述其他学科中的经典问题也是相当困难的，比如要研究布朗运动的规律和高分子空间结 构都不可能用确定论来很好的完成，伴随着这些不规则形体带来的问题的困扰，一门新 的学科诞生了，那就是对多个领域的发展都有着不可磨灭贡献的分形理论学科。 分形理论发展至今已有1 0 0 多年的历史了，根据其理论思想的发展深度，可以从三 个阶段来叙述分形理论的发展史。 第一阶段从1 8 世纪晚期到1 9 世纪初期。这一时期，大部分的研究工作主要是放在 对分形几何和规则几何的差异性进行比较，采用的手段是选取有代表性的具体的几何体 来详细研究。十九世纪，数学家普遍认为连续曲线上的不可微点应是极少的，虽然当时 已经认识到连续曲线与可微曲线的差别。但1 9 8 2 年，数学家w e i e r s t r a s s 在当时曾引 起了极大的震动，他构造了一个边界处处不可微的函数。函数表示为： 2 3 分形图像压缩简介 1 9 8 8 年，巴恩斯利第一次提出了把分形理论运用到图像编码中，并成功的实现了图 像压缩的分形方法，为图像压缩的发展开拓出了一条新的道路。 巴恩斯利所实现的图像压缩分形方法主要是基于压缩映射的不动点定理和拼贴定 理，这两大定理奠定了分形压缩编码的数学基础。在他的关于图像分形编码的论文中， 通过对自相似度比较高的枫叶进行压缩，验证了分形编码压缩比高的优势。 尽管巴恩斯利用他所实现的分形编码方法达到了在当时的图像压缩领域中相当高 的压缩比，但从该方法的实际操作中来看，还有几个不令人如意的地方：首先，该方法 西华大学硕士学位论文 在编码前的准备工作中，未能够实现对图像的自动分块，分块工作还必须由水平较高的 专业人员来完成；另一方面，在编码过程进行求分形码的步骤中，与分块的子图像进行 比较的父块只能是整幅图像，使得该方法的使用只能在自相似度比较高的特定图像上得 到比较好的效果，对于自相似度比较低的一般图像，其解码后的恢复图像质量并不如人 意，因为这两方面的原因，该方法在当时并没有得到广泛的推广。 虽然巴恩斯利开了用分形理论进行图像编码的先河，但要使分形编码方法得到广泛 的运用，必须要解决自动分块和精准匹配这两个问题。在1 9 9 0 年，j a c q u i n 提出一种全 新的分形编码思想，成功地解决了影响分形编码应用的两个问题，这就是著名的局部迭 代函数系统。该编码思想在自动分块的问题上采用了自动由计算机完成把图像划分为固 定大小的方块子图像方案；再对原图像按照一定的策略进行二次方块图像划分，以此作 为与子图像进行匹配的父块集合，解决了巴恩斯利方法中不能精准匹配的问题。j a c q u i n 的编码思想把分形图像编码的实现推向了自动化，可以说是整个分形图像压缩发展当中 的一次重大突破。 2 4 分形图像编码的最新研究进展 近几年来，随着分形理论的发展和各种不同的分形编码优化算法的提出，分形的应 用已经迅速扩展到了数字图像处理、机器视觉等领域，并为这些领域的相关理论发展做 出了巨大的贡献。分形理论不同于规则几何学，但我们可以把它看成是规则几何学的一 种扩展。在分形理论产生前，并没有合适的工具来表示自然万物本身所具有的相似性， 这就给对于这种自相似性比较明显的物体进行分析造成了不便，分形理论的产生一举改 变了这一局面，成为了众多学科研究自相似性现象的一个重要工具，广泛应用于数学、 自然科学和社会科学等众多领域中，成为了非线性科学研究中一个十分活跃的分支。 分形编码是分形理论成功运用到数字图像处理当中的一个典型案例，它突破之前 的图像编码理论，首次使用了存在于图像中的自相似性，编码解码的对象仅仅是相似匹 配变换参数，这也就为高倍压缩图像提供了可能性，在编码过程中，只需要求得每个子 块的分形码即可进行压缩数据的存储或传输。而在解码过程中，再利用这种分形码组成 的压缩变换反复作用于任意图像就可以获得重构图像。在该编码思想的发展过程中，最 为关键的一个问题是如何找到一个合适压缩变换，使得该编码方案能够按照理想的状态 进行下去。前面提到，由巴恩斯利首先提出了一个编码方案，但由于不能够实现自动化 操作，不方便推向于实际运用，所以没能得到广泛的认可。然后，由j a c q u i n 的改进算 法打破了这一局面。 基于区域分类的分形图像编码算法研究 管j a c q u i n 的改进算法虽然能够由机器实现自动编码，但由于编码算法的时间性 低，所以离分形编码的实用化仍然有一定的距离。但也是从j a c q u i n 的改进算法 ，分形编码开始浮出水面，它的发展潜力已被许多研究人员认可，于是通过不懈 ，提出了各种改进算法。从各种改进算法中，我们可以看到，在分形编码中存在 图像压缩速度和提高解码图像质量这样一对矛盾。要想加快压缩算法速度，必然 编码过程中丢失部分图像数据，但这样一来，丢失的部分图像数据必然会使解码 质量有所下降；反过来，要想解码图像质量损失较少，必然要求在压缩过程中尽 图像数据的损失，这对时间性能的提高提供不了多少上升空间。所以，如何能够 压缩速度的同时，也不会对解码恢复图像的质量造成太大的损坏，是以后的分形 码方案改进的主要目标。目前对分形图像编码技术的改进主要体现在以下方面。 ) 直接在局部迭代函数系统的基础上进行改进。 在分形编码的图像分块过程中，对子块的划分策略直接决定了分形编码的最终解 质量和整个算法能够达到的压缩比，因此许多研究课题就放在了如何科学的划分 问题上。一方面，如果子块尺寸划分过大，必然会是压缩比得以提高，甚至可以 速度加快，但也会导致最终的恢复图像质量不能被接受。另一方面，如果子块尺 得过小，虽然可以得到质量较高的解码图像，但对压缩比和时间性能来讲，都会 大的影响。比较经典的子块划分改进方案有： 叉树划分方案：该方案先还是按照传统的4 x 4 或8 x 8 像素大小进行子块的划分， 块编码的时候要比较编码误差与编码前规定的阈值，如果大于规定的阈值，就需 要对该子块进行二次划分，划分的方案为四叉树方法。 三角形划分方案：该方案是将传统分割后的正方形子块再分割成两个三角形，从最 后的解码恢复图像的质量来看，该分割方案对于斜边缘的恢复有较好的贡献。 而在众多的自然图像中，斜边缘是广泛存在的，所以该方案是相当实用的分割方案 之一。 此外，还有许多其他的突破了规则方块分割的方案，不同的方案对于整个编码过程 的部分性能指标都有所提升，有的为了提高压缩比，采用不规则形体尽量以大尺寸来进 行子块分割，这样一来，也就减少了编码后产生的分形码数量，从而提高了压缩比。分 1 4 西华大学硕士学位论文 割方案作为编码前的一种预处理，无论是对编码文件的大小，还是对最终的解码图像质 量都要很大的影响，所以选择适当的分割方案是分形编码技术中很重要的一环。 传统的分形编码方法中，子块与父块的匹配是一对一进行的，而这也是造成分形 编码阶段太慢的主要因素，因此，很多改进方法针对这一问题提了出来，普遍的做法是， 由于子块的数量对解码恢复图像的质量影响很大，所以就采取了子块数量不变，缩减父 块数量的方法。最常见的方法是把父块进行分类，然后对子块进行判定分类，最后子块 只在类别相同的父块中进行一一匹配，从而大大减少了匹配次数，达到了加快编码速度 的目的。 还有一类改进方案也是为了加快分形编码速度，当不同于分类匹配这样的方法， 它采用的是搜索匹配。即在编码过程进行到子、父块匹配时，先参照子块特征按照某种 规则对所有父块进行一次搜索，把不满足规则特征的父块直接删除，从而也减少了匹配 量。 ( 2 ) 除了在经典的分形编码思想上进行直接的算法改进，还有另一大类改进方法， 那就是借助于其他编码方式的优点，把其他编码方案中的部分适当技术运用到分形编码 中来。运用得比较多的是与经典编码哈夫曼编码的混合，使得编码生成的分形码进一步 压缩，再次提高压缩比；还有与小波编码的融合，使得子父块的匹配只需要参照很简单 的方案来进行，就可以取得很好的图像恢复质量。 1 5 定义3 1 局部迭代函数系统可以表示如下 ：acx ( i = o , t ，n ) ) 其中w ；a 之间是一种局部压缩映射关系，它们之间的压缩因子规定为实数s 。 分析该定义，可以看出只需要对每个子图像在压缩映射中产生的分形码进行存储即 可完成编码工作，在解码恢复图像时，先利用分形码首先恢复每一块子图像，再合并成 整张图像即可。所以，利用局部迭代函数系统进行分形图像编码的过程可以表示如下： 西华大学硕士学位论文 对每一子块 原始 图像 提取分 找到最佳匹 图像分块 形码 配块 恢复 图像分形码迭代恢复分 一一 _ _ 一 图像合并重