（计算机应用技术专业论文）分形图像压缩方法研究.pdf

大连理工大学硕士学位论文 摘要 非线性科学是一门研究非线性现象共性的基础科学，其中分形理论是非线性科学的 一个重要分支。本文利用理论推导和实验仿真相结合的方法研究了几种提高分形编码性 能的方法： 本文引入纹理特征相关和智能分类算法来加快分形图像编码的速度和提高压缩率。 纹理特征是描述图像特征的一个重要属性，由灰度共生矩阵获得的熵和最大熵用来计算 图像块的纹理特征值。对于给定的待编码值域块，只在同其具有相同纹理特征的相邻值 域块对应的连续定义域块中搜索。并且，在智能分类搜索中，只有同当前待编码的值域 块具有相似的纹理特征的定义域块才被搜索，这样充分利用了图像块问的纹理相关性， 并且加速了编码过程。 提出了一个更优的基于拟合平面的灰度级变换。同自适应平面灰度级变换相比，对 于一个给定的值域块，该灰度级变换能降低值域块和其相对应定义域块问的匹配误差， 提高两者之间成功匹配的概率。另外，我们可以用更少的比特来存储编码参数。因此能 够减少待编码值域块的数量，提高压缩率，提高重构图像质量。实验结果表明，该方法 在各个方面都优于自适应平面无搜索方法；该方案重构图像质量在压缩率较低时，要优 于f u r a o 的无搜索方法；在压缩率较高时，几乎与f u r a o 的无搜索方法相同。虽然拟合 平面无搜索方案使用了较多的编码参数，但是它能加快编码，提高重构图像质量。 提出了一个新颖的基于图像拆分的无搜索分形图像编码方法。我们并不是直接对原 始图像进行分形编码，而是将其拆分为两幅特殊的图像。然后对这两幅图像运用改进灰 度级变换的无搜索方法分别进行编码。在理论上证明了本文方法能够降低值域块和定义 域块匹配时的匹配误差，提高值域块和定义域块匹配成功的概率。在编码新的图像时， 首先判断当前待编码值域块是否是平坦块。编码结束后，再将解码得到和两幅图像合并 为一幅图像。针对大量标准测试图像的实验表明，本文所提方法能够加快编码速度，提 高压缩率，并且能够获得较高的重构图像质量。即便我们仅仅处理由原始图像拆分获得 的第一幅图像，仍然能够获得非常好的性能。并且，该方法对于不同内容的图像，都能 获得较好的效果。 关键词：分形图像压缩；纹理相关；拟合平面；图像拆分；无搜索 人连理工大学硕士学位论文 r e s e a r c ho nf r a c t a li m a g ec o m p r e s s i o nm e t h o d s a b s t r a c t n o n l i n e a rs c i e n c ei saf o u n d a t i o n a ld i s c i p l i n ew h i c hc o n c e r n st h ec o m m o np r o p e r t i e so f n o n l i n e a rp h e n o m e n a a n df r a c t a lt h e o r yi so n eo fi m p o r t a n ts u b d i s c i p l i n e so fn o n l i n e a r s c i e n c e t h er e s e a r c hs t u d i e ss e v e r a lm e t h o d st oi m p r o v e 仃a c t a li m a g ec o m p r e s s i o n at e x t u r ec o r r e l a t i o na n dt h ei c as e a r c hs t r a t e g ya r eu t i l i z e dt os p e e du pt h ee n c o d i n g p r o c e s sa n di m p r o v et h eb i tr a t ef o rf r a c t a li m a g ec o m p r e s s i o n t e x t u r ef e a t u r ei so n eo ft h e m o s ti m p o r t a n tp r o p e r t i e sf o rt h er e p r e s e n t a t i o no fa ni m a g e e n t r o p ya n dm a x i m u me n t r y f r o mc o - o c c u r r e n c em a t r i c e sa r eu s e df o rr e p r e s e n t i n gt e x t u r ef e a t u r ei nt h ei m a g e f o ra r a n g eb l o c k ，c o n c e r n e dd o m a i nb l o c k s o fn e i g h b o r i n gr a n g eb l o c k sw i t hs i m i l a rt e x t u r e f e a t u r ec a nb es e a r c h e d i na d d i t i o n ，d o m a i nb l o c k sw i t hs i m i l a rt e x t u r ef e a t u r ea r es e a r c h e d i nt h ei c as e a r c hp r o c e s s ，w h i c hf u r t h e rm a k e su s eo ft h et e x t u r ec o r r e l a t i o nb e t w e e nb l o c k s a n ds p e e d u pt h ee n c o d i n gp r o c e s s af a s ta n de f f i c i e n tn o s e a r c hf r a c t a l i m a g ec o d i n gm e t h o db a s e do n am o d i f i e d g r a y 。l e v e lt r a n s f o r mw h i c hu s e saf i t t i n gp l a n ei sp r e s e n t e d n ei m p r o v e dg r a y l e v e l t r a n s f o r mc a nr e d u c et h em i n i m u mm a t c h i n ge r r o rb e t w e e nag i v e nr a n g eb l o c ka n di t s c o r r e s p o n d i n gd o m a i nb l o c k ，a n dt h u s ，i tc a ne n h a n c et h ep o s s i b i l i t yo fs u c c e s s f u l d o m a i n r a n g em a t c h i n g i nc o m p a r i s o nw i t ht h eg r a y l e v e lt r a n s f o r mw h i c hu s e sa na d a p t i v e p l a n e ，t h ei m p r o v e ds c h e m er e s u l t si nac o n s i d e r a b l ea c c e l e r a t i o no ft h ee n c o d i n gp r o c e s s ， d e c r e a s e st h ec o m p r e s s i o nr a t i oa n di m p r o v e st h eq u a l i t yo ft h er e c o n s t r u c t e di m a g e si nt h e m e a n w h i l e c o m p a r i n gw i t hf u r a o sn o s e a r c hs c h e m e ，o u ri m p r o v e ds c h e m ec a ng e th i g h e r p s n ra th i g h e rb p p ，a n di ta c h i e v e sa l m o s tt h es a m ep s n ra tl o w e r b p p a l t h o u g hi tu s e s m o r et r a n s f o r mc o e f f i c i e n t s ，s u c haf i t t i n gp l a n em e t h o dc a ns p e e du pt h ee n c o d i n gp r o c e s s w i t ht h eq u a l i t yo ft h er e c o n s t r u c t e di m a g e si m p r o v e d an o v e ln os e a r c hf r a c t a li m a g ec o d i n ga p p r o a c hb a s e do nc o n v e r s i o ni sp r o p o s e di nt h i s p a p e r w ed on o te n c o d et h eo r i g i n a li m a g ed i r e c t l yb u tc o n v e r ti tt ot w os p e c i a li m a g e s ，t h e n e n c o d et h e mu s i n gn os e a r c hf r a c t a li m a g em e t h o db a s e do nt w o g r a y 1 e v e lt r a n s f o r m s r e s p e c t i v e l y ，o n ef o rt h el a r g eb l o c k sa n dt h eo t h e rf o rt h es m a l lb l o c k sb a s e do nt h eq u a d t r e e p a r t i t i o ns c h e m e ，m e a n w h i l eap r e c o n d i t i o ni si n t r o d u c e dt os e ew h e t h e rt h er a n g eb l o c ki sa c o n s t a n tb l o c k w ea n a l y z ea n dp r o v et h a ti tr e d u c e st h em i n i m u mc o n v e r s i o nm a t c h i n ge r r o r o ft h er a n g eb l o c ki nt h e o r y i nt h ee n dw ec o n v e r tt h et w od e c o d i n gi m a g e st oo n e e x p e r i m e n t so ns t a n d a r dt e s ti m a g e ss h o wt h a tt h ei m p r o v e ds c h e m es p e e d su pt h ee n c o d i n g t i m e ，i m p r o v e st h ec o m p r e s s i o nr a t i oa n de n h a n c e st h eq u a l i t yo ft h er e c o n s t r u c t e di m a g e i i i 分形图像压缩方法研究 e v e ni fo n l yd e a l i n gw i t ht h ef i r s ti m a g eg o tf r o mt h eo r i g i n a li m a g e ，i ta l s ow o r k sw e l l f u r t h e rm o r e ，t h ei m p r o v e ds c h e m ec a nm a i n t a i nag o o db a l a n c ef o rg e n e r a li m a g e s k e yw o r d s ：f r a c t a i m a g ec o m p r e s s i o n ；t e x t u r ec o r r e t a t i o n ；f i t t i n gp t a n e ； i m a g ec o n v e r s i o n ；n o s e a r c h i v 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 坌盔! 】旦i 盏塾盘垄丝塑杰 作者签名：上些盟一日期j 4 年上卑日 人连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：盈塑! 盈i 垒丝亟盔适垄盔盘 作者签名： ， 至湮整 日期：1 4 年月2 乙日 导师签名： 型z 兰乏。日期：巡年监月三墨日 人连理1 二大学硕十学何论文 引言 随着计算机技术、现代通信技术的飞速发展，人类社会正逐步迈入信息化时代。尤 其是近几年，随着多媒体技术、互联网技术等新技术的迅猛发展，许多信息都是以图形、 图像形式存储的，它所面临的一个关键问题就是如何有效地存储、传输图形图像数据， 其中数据压缩方法比起数据的存储和数据传输具有更为突出的实用价值和商业意义。因 此，图像数据作为其中数据量最大的一类，在满足一定图像质量要求的前提下如何高效 地对图像进行压缩1 1 。3 l ，并且保持较好的图像质量，这是图像编码人员努力研究的重点。 分形1 4 , 5 l 的概念是由数学家m a n d e l b r o t 于1 9 7 5 年提出的，他把分形定义为“一种由 许多个与整体有某种相似性的局部所构成的形体”。分形概念的提出以及分形几何学的 创立为描述客观世界提供了更准确的数学模型。 目前，分形编码以其新颖的思想、高压缩比、分辨率无关性和快速解码等优点受到 学术界、技术界广泛关注，是目前公认的三种最有前途的新一代图像编码技术之一( 另 两个是小波技术与模型法技术) 。基本分形块编码算法虽然实现了计算机自动编码过程， 但从实用角度看，基本算法的计算复杂性很高，编码质量也不理想。如何减少编码时间、 提高编码质量，还有许多待解决的公开问题。国内外的许多学者针对基本分形块编码算 法的缺陷提出了一些改进方法，改进方向主要包括加快编解码速度、提高解码图像质量 和压缩比。加快编解码速度的改进方法主要是缩小值域块的搜索范围，主要包括分类法 1 6 q o l 、邻域法【1 1 - 1 3 j 、无搜索方法”1 7 l 等：提高解码图像质量的改进方法主要有寻找更合 理的值域块分割方法【1 8 垅1 、与其他编码方法结合的混合编码f 2 2 2 6 】等；提高压缩比的改进 方法主要是选择更有效的参数量化和熵编码算法1 1 9 ，2 1 j 。 本文在前人工作的基础上，以非线性理论中的分形理论为基础，对部分分形图像编 码方法进行了研究与该进。 本文章节安排如下：第一章简要地介绍了数字图像压缩的基础知识。第二章介绍了 分形图像编码的基础知识。第三章研究了空间纹理特征相关的快速分形图像编码方法。 第四章介绍了基于现有的灰度级变换的无搜索分形图像编码方法，并且研究了狄度级变 换的改进方法。第五章尝试将原始待编码图像拆分为两幅图像，研究了基于图像拆分的 分形图像编码方法。最后给出了全文的结论。 分形图像乐缩方法研究 1数字图像压缩的基本原理 图像压缩所解决的问题是尽量减少表示数字图像时需要的数据量。减少数据的基本 原理是除去其中多余的数据。以数学的观点来看，这一过程实际就是将二维像素阵列变 换为一个在统计上无关联的数据集合。这种变换在图像存储或传输之前进行。在以后的 某个时候，再对压缩图像进行解压缩来重构原图像或原图像的近似图像。 1 1图像数据冗余 “数据压缩 指减少表示给定信息量所需要的数据量。数据和信息之间必须给予明 确的区分。数据是信息传送的手段。对相同数量的信息可以以不同数量的数据表示。包 含了与所描述的内容无关联的或是重述己经知道了的信息，就叫做包含了数据冗余1 3 】。 数据冗余是数字图像压缩的主要问题。在数字图像压缩中，可以确定三种基本的数据冗 余并加以利用：编码冗余、像素间冗余和心理视觉冗余。当这三种冗余中的一种或多种 得到减少或消除时，就降低了图像的数据量，从而实现了图像压缩。 ( 1 ) 编码冗余：如果图像的灰度级在编码时用的编码符号数多于表示每个狄度级 实际所需的符号数，则用这种编码得到的图像包含编码冗余。通常，当被赋予事件集的 编码如果没有充分利用各种结果出现的概率去选择，就会存在编码冗余。 ( 2 ) 像素间冗余：任何给定像素的值可以根据与这个像素相邻的像素进行适当的 预测，所以由单个像素携载的信息相对较少。单一像素对于一幅图像的多数视觉贡献是 多余的，它的值可以通过以与其相邻的像素值为基础进行推测。 ( 3 ) 心理视觉冗余：在正常的视觉处理过程中各种信息的相对重要程度不同，那 些不十分重要的信息称作心理视觉冗余。这些冗余在不会削弱图像感知质量的情况下可 以消除。 1 2 图像压缩编码的分类 利用不同的编码方法删除冗余，就形成了不同类型的压缩编码方法。根据解码后的 数据是否和原始数据一致，图像编码可分为无损编码和有损编码两种1 2 7 1 。 ( 1 ) 无损编码 无损编码又称无失真编码或信息保持编码，这是一种在不引入任何失真的条件下使 比特率为最小的压缩方法。该方法要求在解码后得到的恢复图像与原始图像严格相同， 没有任何失真。无损编码方法由于没有利用人眼的视觉特性，一般情况下压缩比很低。 现有无损编码方法主要根据信息码字出现概率的分布特征进行压缩编码，寻找出现概率 人连理丁大学硕士学位论文 与码字长度间的最优匹配。常见的有霍夫曼( h u f f m a n ) 编码、香农费诺( s h a n n o n f a n o ) 编码以及算术编码( a r i t h m e t i cc o d i n g ) 。 ( 2 ) 有损编码 有损编码是一类有失真的编码方法，信息论中叫做熵压缩。该方法导致信息的减少， 有信息丢失。丢失了的信息是根本无法恢复的，所以是一个不可逆的过程。常用的方法 有：变换编码、预测编码、直接映射和分析综合编码。 冗余度压缩与不可逆压缩的结合形成了一类称为混合编码技术，它体现了不同类型 技术的交叉和综合，实际上许多国际标准都是采用混合编码技术。 1 3 图像压缩的性能指标 图像编码常用的技术指标主要有两个方面：压缩比或压缩率和保真度；另外还有消 耗的时间以及峰值信噪比等一些参数。 压缩比= 器黟压缩率= 丽1 消除心理视觉冗余数据导致真实的或一定数量的视觉信息的丢失，因为可能会由此 失去重要的信息，所以迫切需要一种对信息损失的测度来描述解码图像与原始图像的偏 离程度，这些测度一般称为保真度准则l 矧。而最常用的是客观保真度准则。 令f ( x ，y ) 表示输入图像， ，y ) 表示由对输入先压缩后解压缩得到的厂o ，y ) 的估 计量或近似量，并令图像大小为mx n 像素，则解压图像与原始图像之间的误差可用下t 列几种指标评价： 均方误差： 脚2 高荟t t z 荟。v ( 厂一于) 2 峰值信燥比： 气q 2 踟= l o l o g 嵩( 衄) 实际上，p s n r 为常用标准，当p s n r 超过3 0 d b 时，我们的主观视觉很难找出其差 异。 1 4 j p e g 压缩 目前静止图像的压缩算法以j p e g ( j o i n tp h o t o g r a p h i ce x p e l sg r o u p ) 和j p e g2 0 0 0 为主。j p e g 的任务是建立适用于连续色调图像压缩地国际标准。其提出的标准致力于 普通的、宽范围的连续图像色调应用，本文简要介绍j p e g 的理论基础。 分形图像压缩方法研究 j p e g 压缩算法包括四个部分i 图像格式转换、图像变换处理、量化和熵编码。 图像格式转换模块主要是为了下面的离散余弦变换编码准备好数据。原始的输入数 据是r g b 空间的信号，首先要变换到y c b c r 空间，然后是进行一定的采样，用交叉模 式下给出一组最小数据单元。如果图像是黑白色的，可以省去色度空间变换这一步。 图像变换处理是利用离散余弦算法来实现的。离散余弦变换主要目的是将信号量集 中到低频段，更好的呈现出图像的规律。对8 8 的数据而言，直流分量处在左上的顶 角处，而交流分量将会进一步远离直流分量。 j p e g 要对数据压缩，首先要做一次离散余弦变换。经过这个变换，就把图片里点 和点间的规律呈现出来了，更方便压缩。j p e g 是对每8 8 个点为一个单位处理的，所 以如果原始图片的长宽不是8 的倍数，都需要先补成8 的倍数，好一块块的处理。 j p e g 编码时使用的是f o r w a r d 离散余弦变换( f d c t ) ；解码时使用的是i n v e r s e 离散余弦变换( i d c t ) 。 对于前面得到的6 4 个空间频率振幅值，由于人眼对它们的敏感程度不一样，在此 对它们作幅度分层量化操作，方法就是分别除以量化表罩对应值( 人眼的敏感系数的倒 数) 并四舍五入。这样的量化结果值就是真正人眼可见值了。 将离散余弦变换系数按频率由小到大进行重新排列，使得每个数据之间都是相邻 的，连续的。在自然界图像在高频部分往往并不很重要，这样排列将更有利于更好的保 留有用信息，有利于后续的编码。具体操作是将一个8 8 的数组按照图中的顺序变换 成另一个8 8 的数组，结果数据在内存里是以z i g z a g 排序顺序存放的。然后对系数进 行相应的差值编码、行程编码、分组编码和哈夫曼编码。 一4 一 大连理工大学硕士学位论文 2 分形图像压缩基础 1 9 7 5 年，法国数学家m a n d e l b r o t 发表了( ( t h ef r a c t a lg e o m e t r yo fn a t u r e ) ) ，标志 着“分形( f r a c t a l ) 作为一门科学正式成立，分形理论也成为非线性科学的主要分支 之一，它对自然科学和社会科学都产生了巨大的影响。分形理论既有深刻的理论意义， 又有巨大的实用价值。特别是在图像压缩方面，由于分形结构一般都具有某种形式的自 相似性，尤其对于不规则的几何图形( 曲折的海岸线、多变的云彩图案、参差不齐的金 属表面以及涨落无常的股价曲线) 可由简单的函数簇迭代产生的这一特性，使基于分形 理论的图像压缩方法成为数据压缩的一种行之有效的重要方法【2 9 1 。 2 1 分形的定义 经典的欧氏几何所能处理的图形都是相当规则和光滑的，通常是整数维的( 如离散 点集是零维的，光滑曲线是一维的，光滑曲面是二维的等等) 。但随着科学的发展，人 们意识到对过去当作例外的不规则的图形可以而且必须进行详细的分析。分形几何恰好 为研究这些不规则图形提供了经典几何学所没有的理论和思想框架，分数维和自相似性 是其核心之一【2 9 - 3 1 1 。 分形是人们在自然界和社会实践中所遇到的不规则事物、状态和过程的一种数学抽 象，分形的描述式定义能够全面地概括这种抽象。m a n d e l b r o t 曾经指出，分形具有三个 要素：形状( f o r m ) ，机遇( c h a n c e ) ，维数( d i m e n s i o n ) 。首先，分形的形状是支 离破碎的，不规则的。其次，分形可以对一组给定的规则通过随机迭代而得到，而对象 本身并不依赖于随机性，得到同一个分形的概率是百分之百，因此随机性或者机遇仅仅 是工具，而结果却是确定的。第三，维数是分形图形最基本的不变量，是度量分形集“不 规则”程度的数量尺度；分形的维数可以是分数，称为分维。 2 2 分形图像压缩的理论基础 分形图像压缩的理论基础是压缩映射定理、迭代函数系统定理和拼贴定理f 2 9 , 3 2 , 3 3 1 。 定义2 1 度量空间( x ，d ) 上的变换f ：x x 称作压缩或压缩映射，如果存在 一个常数0ss 1 ，使得 d ( f ) ，厂( y ) ) ss d o ，y ) ，v x ，y e x 则称，为空间x 上的一个压缩映射，s 为压缩因子，且此压缩映射是连续的。 分形图像压缩方法研究 定理2 1 ( 压缩映射原理或b a n a c h 不动点定理)设( x ，d ) 为一完备度量空间， ，：x 呻x 是x 上的一个压缩映射。则厂存在唯一不动点z 。， 且 x 。= l i mf “o ) = l i r a 厂厂“1 0 ) ) ，v x e x 。 换言之，完备度量空间中压缩映射厂的不动点存在唯一，且可以由映射对任意初始 点的反复迭代逼近到任意精度。 压缩映射定理说明，一个完备度量空间上的压缩映射有唯一的吸引子。图像空间是 一个完备度量空间，因此，对图像空间上的压缩映射，其唯一的不动点就是平面上的一 幅图像。而且对平面任意一幅初始图像，反复使用压缩映射，经过一定次数的迭代以后， 就形成唯一的一幅图像，该图像决定于压缩映射，而与初始图像无关。这一性质在分形 图像压缩的解码过程中有非常重要的应用，是分形图像压缩解码过程的基础。 定义2 2 ( 迭代函数系统)一个迭代函数系统是由一个完备度量空间x 及其上的 一组压缩变换 咀，f = l 2 ，) 及其相应的压缩因子s 所组成。常用i f s 来表示迭代函数 系( i t e r a t e df u n c t i o ns y s t e m ，简称i f s ) ，记为 x ；咀，f = l 2 ，) 。其压缩因子是 st m a x s , ，i 一1 ，2 ，) 。 定理2 2 ( 压缩映射不动点定理)给定一个足2 上的迭代函数系统，就能生成唯一 的一幅图像。在计算机图像压缩技术中，更有意义的是：对任意一幅图像，都能找到一 个r 2 上的迭代函数系统，使得该迭代函数系统的吸引子就是该图像或者近似于该图像。 定理2 3 ( 拼贴定理)如果迭代函数系统对原图像的变换结果与原图像很接近， 而压缩因子又远小于1 ，则其吸引子与原图像也很接近。 2 3 分形图像压缩的基本原理 1 9 9 0 年，j a c q u i n 提出了基于分块迭代函数系统( p a r t i t i o n e di f s ) 的分形块编码算 法1 3 4 1 ，这是首次利用计算机进行数字图像的分形压缩的自动算法，对分形图像压缩方法 的实用化起了奠基的作用。 分形图像编码p i f s 方法，本质上是假设自然图像中不同区域间存在着跨尺度冗余 ( a c r o s s s c a l er e d u n d a n c y ) ，即不同尺度下的冗余来实现图像压缩的。对于自然图像， 我们不难找出其不同区域间存在这种不同尺度下的相似性，例如照片中不同远近、不同 位置的物体，如图2 1 标准测试图像“l e n a ”中肩膀处嵌套的两个区域、帽沿处的小区 域与右下角的大区域，两个大区域缩小一定比例就分别与各自的小区域基本吻合。 人连理人学硕十学位论文 图2ll e n a 图像中的自相似区域 f i g2 1 s e l fs i m i l a r p o r l i o n s o f t h e l e n a i m a g e 分形编码的任务就是要寻找个压缩变换w ，使得w 的不动点尽可能接近待编码图 像。假设一副大小为m 的灰度图像，( 获度级为2 5 6 ) ，在分形编码过程中，图像r 被分割为大小为b x b 的且互不重叠的值域块和大小为c x c 的且可以相互重叠的定义 域块，通常定义域块的大小是值域块的2 倍。所有的值域块r n s i s mx n ( b x 占) ) 组成 了r 块池，所有的定义域块组成定义域块池q 一 q 旧c ， 。对于每个值域块r ，找们 在定义域块池中搜索一个最佳匹配的定义域块n ，并计算相应的压缩映射毗，使得 坼( 皿) 和r 的误差最小，这里的误差度量一般采用均方误差来度量。重复进行直到所有 的值域块都找到相应的虽佳匹配定义域块，这样我们就得到一组压缩映射集合 w = 似1 1s f s mx n 佃丑) ) 和相应的最佳匹配定义域块位置。由拼贴定理我们知道， 如果一组映射是压缩的，则这组压缩映射存在唯一不动点，且这个不动点到原始图像的 距离任意小。因此拼贴定理保证了w 的不动点图像和原始图像，近似。当最佳匹配定义 域块变换堆及其位置找到之后，存储或传输其量化参数，完成尺块r 的编码。待所有r 块被编码以后，原图像的分形编码也就完成了。 每一个压缩映射砒由三部分组成，定义如下所示： m ( 皿) ；刚( 日) ( 2 1 ) 其中表示空域压缩算子，r 表示等矩变换算子，f 表示灰度级变换，口表示一个 图像定义域块。定义域块空域压缩算子通常采用四像素平均来构造。 分形图像压缩方法研究 采用等矩变换可以扩大定义域块池，提高值域块和定义域块之间成功匹配的概率。 一个图像子块的等距变换一般有8 种方式，即恒等变换和9 0 * 、1 8 0 和2 7 0 顺时针旋转 以及关于垂直中线、水平中线、主对角线和次对角线对称反射，如图2 2 所示。 获度级变换一般被定义为如下形式： 9 ( d ) - s d + 甜 ( 2 2 ) 其中s 表示亮度调整，o 表示亮度偏移d 表示经过空域压缩和等矩变换作用后的定义 域子块，表示大小与d 相同的全1 矩阵。正是参数j 和。的引进，才使仿射变换后的d 块的灰度有可能匹配r 块的灰度，如图2 3 所示。 l 竺 o | ” 川像块 司同同f 回国闭阿 图2 2 图像块的8 种旋转和变换 f i g 2 2t h ee i g h tr o t a t i o n sa n d f l i 口；o f a r t i m a g e b l o c k h 寻 矧像块 图23 亮度调整与偏移 f i g 2 3t h e g x e y l e v e ls c a l i n g a n d g r e y l e v e l0 f m 因此，对一幅图像的分形编码问题转化为对图像中的每一个值域块在定义域块池中 搜索最优的定义域块并计算相应的参数s 和。的过程，而对一个值域块r 和一个收缩变 换后的定义域块d ，其相应的最优参数s 和。由下面定义的匹配误差e ( r d ) 决定： e ( r , o ) - i 曲+ n ，一删 ( 2 3 ) 通过使用最小二乘法，我们可以得到s 和。如下： 大连理t 大学硕十学位论文 扣警穿 亿4 ， 扣历广 皑“ 0 ：f s d 一( 2 5 ) 这里f 表示值域块尺的均值，孑表示压缩变换后的定义域块d 的均值。每个值域块的分 形编码涉及四个参数恤，朋o ) ，墨，o a ，前两个参数k 、m ( i ) 分别指明等矩变换和最佳匹配定 义域块的位置，是不能量化的。因此，只有后两个参数才需要量化。一般采用一致量器 来量化参数s 、0 ，实验表明，s 和0 分别采用5 比特和7 比特来量化是合适的。此外， 为了进一步提高压缩比，可以采用考虑参数概率分布的熵编码对量化后的s 和0 进行二 次编码。 总之，在分形编码中，一幅图像是用一个使图像近似不变的压缩变换的参数来表达 的，而这样的参数往往可以紧凑地编码。这大大减少了储存图像的比特数，因而实现了 图像数据的高压缩比。分形解码较为简单，分形解码器是利用b a n a c h 不动点定理给出 的迭代算法设计的，即对于任意初始图像，变换不动点加一l i m ( ) ，w 是表达图 像的分形变换。于是，待编码图像可按迭代方式简单地重构( 有一定的失真) ，即待编 码图像近似等于w ( ) ，其中是迭代次数。应该指出，从严格的数学角度上讲，这 种迭代应该是无穷次的，但在实际的数字图像的解码中，由于分辨率的限制，这种迭代 只需有限次即可。此外，试验结果表明，一般ns 1 0 可以满足条件。 2 4 分形图像压缩基本算法的实现 基于上述描述，一个基本分形编码解码算法的具体步骤如下【3 5 3 6 l ： 1 编码算法 ( 1 ) 分割图像：把原始图像按分辨率b b 像素分割成若干块( 记为r ) ，构成尺 块池。相邻尺块之间没有重叠，它们的并集恰好为原始图像。 ( 2 ) 构成码本：在原始图像中按步长6 从左到右、自上而下滑动一个2 b 2 b 窗 1 ：3 得到d 块池q 。每个d 块经过4 邻域像素值平均( 或欠采样) 得到b b 的收缩定义 域块，所有收缩后的定义域块构成初始码本，所有初始码本分别经过8 个等矩变换构成 扩大的码本。 ( 3 ) 计算分形码：对于每个r 块r ，可以按下面两个步骤在扩大的码本中寻找其 最优的匹配块： 一9 一 分形图像压缩方法研究 对码本中的每个块按公式( 2 4 ) 和( 2 5 ) 来计算参数s 和q 。分别用，量 化参数量和o i ，例如采用一致量化器。把量化后的参数带入公式( 2 3 ) 计算误差，在码 本中寻找误差最小的d 块。 输出当前尺块足的分形码，即量化参数墨和o i ，最优匹配块的位置以及等矩变 换的序号。 ( 4 ) 编码每个尺块：对尺块池中的所有块，重复步骤( 3 ) 直至所有尺块为止。 ( 5 ) 输出分形码，即得到了分形编码文件。 2 解码算法 ( 1 ) 从分形编码文件中读取原始图像大小，尺块大小、步长以及所有j r 块的分形 码信息。 ( 2 ) 根据所得数据，定义一个和原始图像一样大小的初始迭代图像，这个迭代图 像用于产生初始码本。 ( 3 ) 对每个尺块r ，根据它的分形码中最佳匹配d 块位置，在码本中找到相应d 块，然后由公式( 2 2 ) 得到一次迭代恢复的r 。所有恢复后的r 经过拼贴以后就形成 了一次迭代的图像。 ( 4 ) 如果迭代的次数达到预定次数，则停止；否则用前一次得到的图像作为码本 重复步骤( 3 ) 。 ( 5 ) 输出重建图像。 2 5 本章小结 本章首先介绍了分形理论的产生发展和分形的定义；然后介绍了分形图像压缩的重 要理论，包括不动点定理、拼贴定理和仿射变换等；最后给出了基本分形图像压缩算法 的编解码过程。从实用角度来看，基本分形图像编码算法的计算复杂性很高，解码质量 也不很理想。如何减少编码时间、提高编码质量、提高压缩比等方面成为分形图像压缩 亟待解决的课题。 大连理t 大学硕士学位论文 3 基于纹理相关的改进快速分形图像压缩方法 分形编码的一个重要步骤就是对每个尺块在d 块池中搜索最好匹配块( 在某种度量 意义下，通常是m s e ( 均方误差) ) 。可以看出，分形编码的编码时间复杂度非常高， 编码过程十分耗时。文献【3 7 】认为引入8 种等距变换徒增了编码复杂性，相同或更好的 编码质量可以通过减小相邻d 块的间隔6 ( 从而也扩大了码书) 来实现，无需8 种等距 变换。仅仅作上述处理远远不够，因为这样得到的码书仍然很大。要使分形编码实用化， 还必须采用别的降低编码时间复杂度的方法。 3 1t r u o n g 的空间相关快速分形图像压缩方法 3 1 1 空间相关性 t r u o n g 提出了一个新的基于空间相关性1 3 8 j 的策略，用来加快编码速度，降低存储 空间，同时保持重构图像的质量。空间相关性是指相邻块之问通常拥有一些相似的特性， 如边缘和形状等等。并且，空间相关的特征依赖于边缘和形状的方向。例如，对于一个 给定的图像块，考虑与其相邻最近的8 个图像块，如果给定图像块拥有水平方向的边缘， 那么它的左边和右边的相邻图像块通常也拥有水平方向的边缘，而不是其它6 个相邻图 像块。类似的，如果给定图像块拥有主对角线方向的边缘，那么它的左上角和右下角的 相邻图像块通常也拥有主对角线方向的边缘，而不是其它6 个相邻图像块。基于这一特 征，可以将当前图像块的搜索空间定义到其相邻图像块所对应的最佳匹配定义域块，这 样码本的搜索空间要远远小于全搜索所需的搜索空间，能够提高编码速度。另外，由于 当前值域块的搜索空间被相对的限制到其相邻值域块的最佳匹配定义域块周围范围内， 只需要较少的比特数用来存储其最佳匹配定义域块的相对位置，而不需要像全搜索那样 花费较多的比特数来存储绝对位置，因此，压缩率也能得到提高。 为了加快编码速度，利用空间相关来减少搜索空间。正如图3 1 所示，不妨将当前 待编码的值域块表示为r ，分别用r 。，毛，瓦。和r 来代表其相邻的左上角、垂直正 上方、右上角和水平左方四个相邻的已经编码的值域块。假设值域块r ，r ，r 。和r 对应的最佳匹配定义域块分别为谚。，谚，d ：和d ：。 分形图像压缩方法研究 图3 1空间相关方案中当前值域块的搜索空间 f i g 3 1 t h es e a r c h i n gs p a c eo ft h ec u r r e n tr a n g eb l o c ki ns p a t i a lc o r r e l a t i o na p p r o a c h t r u o n g 的方案中，当前待编码的值域块r 的搜索空l n j 被限制为定义域块磁。，磁， 谚。和d ：及其对应方向的相邻定义域块中。例如，当前值域块尺c 水平方向左方的相邻值 域块凡对应的最佳匹配定义域块为d ：，正如图3 1 所示，扩大水平方向上的搜索空间 至珑，d ：，珑和d ：。类似的，谚。，磁，磁。也都在其相应方向上作搜索空间扩展。 这样，待编码值域块兄的搜索空间就被限定为： s = 戳，谚。，玩，p 纛，硝，磁，研，讲，珑，珑，珑，珑，珑，珑，0 ，2 ，珑】。 为了避免由空间相关性获得的局部最小匹配误差和全搜索获得的全局最小匹配误 差之间有太大的差距，需要预先设定一个阀值。如果当前待编码值域块获得的空间相关 局部最小匹配误差大于r ，那么采用全搜索方案以求取该值域块的全局最小匹配误差， 用以保证最终得到较好的重构图像质量。 3 1 2 空间相关快速分形图像压缩算法 空间相关分形图像压缩的详细步骤如下： ( 1 ) j 一0 。 ( 2 )为值域块r ；执行全搜索。假设其最佳匹配定义域块为d ，记录此值域块的 分形编码参数。 ( 3 ) j = j + l ，如果_ 变为最后一个值域块的编号，算法终止。 ( 4 ) 定义如图3 1 所示的搜索空间s 为： 大连理工人学硕+ 学位论文 s = i o o ，巩，碱，巩，硝，谚，研，讲，珑，跣，瑗，珑，珑，珑，珑，d 甜 ( 5 )从搜索空间s 中为值域块r ；搜索其最佳匹配定义域块d ，如果有 m s e ( o j ，r ；) st 成立，记录其分形编码参数，转到步骤( 3 ) ；否则转到步骤( 2 ) 。 在步骤( 2 ) 中，全搜索执行后，记录块的绝对位置。在步骤( 5 ) 中，如果m s e ( d _ ，r ；) st 条件成立的话，值域块j r ；称为“命中块”，它指明该局部最小匹配误差是可接受的。对 于这样的命中块，只需要4 比特来记录其对应的最佳匹配定义域块的偏移量，而不需要 花费1 6 比特来记录其绝对位置。其中2 比特用来记录图3 1 右半部所示的相邻值域块相 关性，另外2 比特用来记录图3 1 左半部所示的定义域块的相关性。 3 1 3 方案缺陷及解决方法 空间相关分形图像编码方案不失为一种良好的编码方案。但是，与空间相关的机制 相反，对于一个给定的值域块，它需先在规定的搜索空间s 中搜索其局部最优匹配定义 域块，而不管该值域块的相邻四个值域块是否也具有相同的特征。如果获得的局部最小 匹配误差大于预先设定的阀值，接下来就要为当i j i 值域块执行全搜索，这就意味着刚才 查找的搜索空间s 中的1 6 个定义域块必须再重新搜索一遍。另外，即便在搜索空间s 中 为当前值域块找到了可接受的局部最优匹配定义域块，那也并不意味着当前值域块的四 个相邻值域块都具有与其相同的特征，也就是说，那些与当前值域块具有不同特征的相 邻值域块所对应的四个定义域块同当前值域块的匹配计算不是必需的。并且，同相关性 相对应的，那些同当前值域块具有相同特征的定义域块应当被搜索，而不是要在所有的 定义域块中执行全搜索。 分形图像编码的基本思想，就是寻找图像不同区域之间在不同尺度下的相似性。分 形的一个重要特征就是自相似性。自然图像中存在着局部自相似性，分形图像编码就是 要为每一个值域块寻找其最相似的定义域块。这就意味着两个块之问的匹配依赖于某种 相似性的度量。纹理特征是图像的一个重要属性，并且被广泛应用于图像检索1 3 9 卅。空 间相关性揭示了图像中相邻图像块具有相似的纹理特征。为了避免不必需的和重复的匹 配误差计算，充分利用图像块间的相关性，首先计算当前值域块r 和其每个相邻的己经 完成编码的值域块尺r ( x = n w ，咒，n e ，们之间的相似性，如果r 和尺r 之间的相似性小于某 个