（计算数学专业论文）分形编码加速及基于样图的图像修复方法研究.pdf

摘要 本文研究的问题包含两方面的内容：分形编码加速方法和图像修复。这两个 方面都是目前图像处理领域的研究热点。 针对分形编码加速方法本文主要作了以下工作： 1 提出了一种衡量分类方法性能优劣的指标体系，并提出了一种基于定义域块 数目的自适应分类方法。结合满意匹配和质心特征给出了一种快速分形编码 方法。实验表明，该方法相对于全局搜索，在解码质量略有下降的基础上， 能极大地提高分形编码速度，当均匀度阂值取为1 2 0 时，其编码时间由原来 的1 3 1 8 4 s 降低为3 5 6 s ，解码图像质量只有1 4 2 d b 的损失；与均匀分类方 法相比，在取得相同压缩比的前提下，该方法可进一步提高分形编码的速度 和改善解码图像质量，当均匀度阙值取为2 0 时，自适应分类使编码时间减 少了约0 1 s ，而质量则提高了0 2 7 d b ； 2 为提高压缩比，我们提出了变门限方法，并结合自适应分类法和满意匹配， 给出了一种基于四叉树的快速分形编码方法；实验表明，与全局搜索相比， 自适应分类变门限满意搜索可以在基本保证解码质量的前提下，极大的提高 分形编码速度，当闽值取为1 1 0 时，与全局搜索相比，该方法将编码时间由 1 2 2 7 5 秒降低为2 4 7 8 秒，质量只有1 4 8 d b 的损失；与均匀划分相比，该 方法使压缩比增加了0 5 6 倍； 3 考虑到采用正方形划分忽略了图像的灰阶均匀性，而矩形划分计算量相当巨 大的问题。在充分分析均匀分类和自适应分类优缺点的基础上，我们提出了 一种混合分类法，并将其应用于质心特征，得到了一种基于矩形划分的快速 分形编码方法。实验表明，该方法相对于全局搜索，在压缩比和解码质量略 有下降的基础上。能极大地提高分形编码速度，当分类数目为1 6 6 时，其编 码时间由原来的6 4 3 2 s 降低为3 3 3 s ，而解码图像质量只有1 1 6 d b 的损失： 与均匀分类方法相比，混和分类法可以在编码时间基本相同的前提下取得 更好的解码质量，在解码质量基本相同的前提下取得更快的编码速度，并可 以在一定的条件下取得压缩比优势： 4 为了使分类后的定义域块库更容易找到最优匹配块，我们提出了一种基于二 维特征向量的自适应分类方法。利用“分割一合并，再分割一再合并”的过 程对定义域块库进行分类。实验表明，经过此分类方法后的定义域块库更利 于值域块找到最优匹配块，而且由于各区间定义域块数目分布更加均匀，也 会使得值域块找到最优匹配块的搜索量大大减少。使用基于二维特征向量的 自适应分类方法，并把图像的l 、2 阶矩不变量作为图像的主副特征给出了 一种能够较好地保证图像解码质量的快速分形编码方法，当分类数为1 0 0 时， 该方法相对于均匀分类法，编码时间减少了o 2 0 2 s ，同时解码图像质量提高 了0 2 4 d b ，与自适应分类法相比，该方法编码时间虽然增加了0 3 3 2 s ，但 是解码质量却提高了0 1 6 d b 。 针对图像修复本文主要作了以下工作： 1 提出了一种基于像素的纹理标准性系数，用来衡量待修复图像块纹理性的强 弱。将其用于图像修复，对于纹理性强的边缘面片直接利用颜色寻找最优匹 配块：对于结构性强的边缘面片，利用改进相似度匹配准则和优先级的 c r i m i n i s i 方法进行修复，得到了一种新的图像修复方法。实验表明，与改 进相似度匹配准则和优先级的c r i m i n i s i 方法相比，对于含有大量纹理性信 息的待修复图像块，本方法能够在修复效果令人满意的基础上，大大加快了 图像修复的速度。 关键词：分形图像压缩自适应分类混和分类纹理标准性系数图像修复 a b s t r a c t t h i sp a p e rp r e s e n t ss e v e r a ln e wm e t h o d st os o l v ep r o b l e m si nf r a c t a ii m a g e c o d i n ga n di m a g ei n p a i n t i n gw h i c ha r ew i d e l yi n v e s t i g a t e di nt h ef i e l do fi m a g e p r o c e s s i n g r e s e a r c h d o n ei nf r a c t a li m a g ec o d i n gi sa sf o l l o w s ： 1 w ef i r s tg i v eo u tt h eg u i d el i n e so ft h ep e r f o r m a n c ef o rc l a s s i f i c a t i o nm e t h o d s ， a n dp r o p o s eat e c h n i q u ec a l l e d a d a p t i v ec l a s s i f i c a t i o nb a s e do nt h en u m b e ro f d o m a i n s ”，c o m b i n e dw i t hm a s sc e n t e ra n ds a t i s f i e dm a t c h ，w eo b t a i naf a s t m e t h o df o rf r a c t a lc o d i n g e x p e r i m e n tr e s u l t si n d i c a t et h a ti nc o n t r a s tw i t h e x h a u s t i v es e a r c h ，t h ep r o p o s e dm e t h o dc a ni m p r o v et h es p e e do ff r a c t a lc o d i n g m u c hm o r eo nf o u n d a t i o no fw o r s eq u a l i t yo fd e c o d e di m a g e ，w h e nt h e u n i f o r m i t yt h r e s h o l di s1 2 0 ，e n c o d i n gt i m ed e c r e a s e df o r m1 3 1 8 4t o3 5 6 ；i n c o n t r a s tw i t ho r i g i n a lu n i f o r mc l a s s i f i c a t i o n ，t h ep r o p o s e dm e t h o di m p r o v et h e s p e e do ff r a c t a lc o d i n gw i t hj u s ts o m ei m p r o v e m e n to fq u a l i t yo fd e c o d e di m a g e a tt h es a m ec o m p r e s s i o nr a t i o ，w h e nt h eu n i f o r m i t yt h r e s h o l di s2 0 ，e n c o d i n g t i m ed e c r e a s e da b o u to 1 s b u tt h eq u a l i t yo f t h ed e c o d e di m a g ei n c r e a s e do 2 7 d b ； 2 i no r d e rt oi m p r o v ec o m p r e s s i o nr a t i o w ea d o p tq u a d t r e em e t h o di nf f a c t a l e n c o d i n g ，a n dp r o p o s e d d i f f e r e n tt h r e s h o l d m e t h o d u s i n ga d a p t i v e c l a s s i f i c a t i o na n ds a t i s f i e dm a t c hw eo b t a i naf a s t e rm e t h o df o rf r a c t a lc o d i n g b a s e do uq u a d t r e e ；e x p e r i m e n tr e s u l t si n d i c a t et h a tt h ep r o p o s e dm e t h o di m p r o v e t h es p e e do ff r a c t a lc o d i n ga n do b t a i nh i g hc o m p r e s s i o nr a t i ow i t hj u s tal i t t l el o s s o fd e c o d e di m a g eq u a l i t y , w h e nt h eu n i f o r m i t yt h r e s h o l di s110 ，e n c o d i n gt i m e d e c r e a s e df o r m1 2 2 ：7 5t o2 4 7 8 ，t h eq u a l i t yo fd e c o d e di m a g ej u s td e c r e a s e d 1 4 8 d b ；i nc o n t r a s tw i t ho r i g i n a lu n i f o r mc l a s s i f i c a t i o n ，t h ec o m p r e s s i o nr a t i o i n c r e a s e d0 ，5 6t i m e s 3 c o n s i d e r i n gs q u a r ep a r t i t i o ni g n o r e dt h eu n i f o r m i t yo fi m a g ea n dt h el a r g e c o m p u t a t i o n a lc o m p l e x i t yo fh vp a r t i t i o n o nf o u n d a t i o no ff u l la n a l y s i s o f o r i g i n a lu n i f o r mc l a s s i f i c a t i o na n da d a p t i v ec l a s s i f i c a t i o n ，w ep r o p o s eah y b r i d c l a s s i f i c a t i o nm e t h o da n du s ei to nm a s sc e n t e ro fi m a g e t h e nw eo b t a i naf a s t m e t h o df o rf r a c t a lc o d i n gb a s e do nh vp a r t i t i o n e x p e r i m e n t a lr e s u l t si n d i c a t e t h a ti nc o n t r a s tw i t he x h a u s t i v es e a r c hh y b r i dc l a s s i f i c a t i o nm e t h o dc a ni m p r o v e t h es p e e do ff r a c t a lc o d i n gm u c hm o r eo nf o u n d a t i o no fl o w e rc o m p r e s s i o nr a t i o a n dw o r s eq u a l i t yo fd e c o d e di m a g e ，w h e nt h ec l a s s i f i c a t i o ni s16 6 ，e n c o d i n g t i m ed e c r e a s e df r o m6 4 3 2t o3 3 3 ，t h eq u a l i t yo ft h ed e c o d e di m a g ed e c r e a s e d 1 1 6 d b ；i nc o n t r a s tw i mo r i g i n a lu n i f o r mc l a s s i f i c a t i o n h y b r i dc l a s s i f i c a t i o n m e t h o dc a l li m p r o v et h es p e e do ff r a c t a lc o d i n gw h e nt h e yh a v et h es a m eq u a l i t y o fd e c o d e di m a g ea n dt h es a m eq u a l i t yo fd e c o d e di m a g ew h e nt h e yh a v et h e s a l i l e e n c o d i n gt i m e m o r e o v e r i ns o m ec o n d i t i o ni te a na c h i e v eh i g h e r c o m p r e s s i o nr a t i o 4 w e p r o p o s eam e t h o dc a l l e d “a d a p t i v ec l a s s i f i c a t i o nb a s e do nt w o d i m e n s i o n a l c h a r a c t e r i s t i cv e c t o r i no r d e rt om a k et h er a n g em a t c h e db e s tc a l lb ee a s i l y f o u n d u s i n gt h ep r o c e s so f “s p l i t m e r g es p l i t m e r g e ”t oc l a s s i f yt h ed o m a i n s e x p e r i m e n tr e s u l t si n d i c a t et h a ta f t e rc a l s s i f i e dt h er a n g em a t c h e db e s tc a nb e e a s i l yf o u n d ，m o r e o v e rt h eq u a n t i t yo fs e a r c hc a r lb ed e c r e a s e db e c a u s eo ft h e u n i f o r m i t y o fc o m a i n s u s i n g“a d a p t i v e c l a s s i f i c a t i o nb a s e do i l t w o d i m e n s i o n a lc h a r a c t e r i s t i cv e c t o r ”a n df i r s to r d e ra n ds e c o n do r d e r q u a d r a t u r eo fi m a g ea sm a i na n ds e c o n d a r yf e a t u r e ，w eo b t a i naf a s tm e t h o df o r f r a c t a lc o d i n gw h i c hc a ng e tb e t t e r q u a l i t y o fd e c o d e di m a g e ，w h e nt h e c l a s s i f i c a t i o ni s10 0 ，i nc o n t r a s tw i t ho r i g i n a lu n i f o r mc l a s s i f i c a t i o n ，t h ee n c o d i n g t i m ed e c r e a s e do 2 0 2 s b u tt h eq u a l i t yo ft h ed e c o d e di m a g ei n c r e a s e do 2 4 d b ；i n c o n t r a s tw i t ha d a p t i v em e t h o dt h ep r o p o s e dm e t h o di n c r e a s e de n c o d i n gt i m e o 3 3 2 s b u tt h eq u a l i t yo f t h ed e c o d e di m a g ei n c r e a s e do 1 6 d b r e s e a r c hd o n ei ni m a g ei n p a i n t i n gi sa sf o l l o w s ： 1 w e p r o p o s et e x t u r es t a n d a r dp r o p e r t yb a s e do i lp i x e lw h i c h i su s e dt om e a s u r et h e t e x t u r eo fi m a g e t h e nw eu s et h i sp r o p e r t yi ni m a g ei n p a i n t i n g ，i ft h ei m a g e b l o c ki ss t r o n gt e x t u r es t a n d a r dp r o p e r t y , w ef i n dt h ec o l o rb e s t m a t c h e db l o c k f o rt h i si m a g eb l o c k ；i ft h ei m a g eb l o c ki ss t r o n gs t r u c t u r es t a n d a r dp r o p e r t y , w e r e p a i rt h i si m a g eb l o c ki nc r i m i n i s im e t h o dw h i c hi si m p r o v e do nm a t c h i n gr u l e a n dp r i o r i t y t h e nw eg e tan e wi m a g ei n p a i l a t i n gm e t h o d e x p e r i m e n t a lr e s u l t s i n d i c a t et h a ti ft h ei m a g eb l o c kh a sm u c ht e x t u r e ，t h i sm e t h o dc a l ls p e e du pt h e p r o c e s so fi n p a i n t i n go nf o u n d a t i o no fs a t i s f i e dr e s u l to fi n p a i n t i n g k e y w o r d s ：f r a c t a li m a g ec o m p r e s s i o na d a p t i v ec l a s s i f i c a t i o n h y b r i dc l a s s i f i c a t i o nt e x t u r e s t a n d a r dp r o p e r t y i m a g ei n p a i n t i n g 西北工业大学硕士学位论文第一章绪论 第一章绪论 1 1 分形图像压缩的发展及研究现状 分形编码算法是一种有损图像压缩技术，它是图像压缩的主要数学工具，有 着广阔的应用前景。分形图像压缩以迭代函数系统( 礤s ) 为理论基础，基于自然 景物的自相似性来进行数据压缩。分形图像压缩算法具有高压缩比、任息尺度下 的重构、快速解码等优越性质。 此项研究由m b a r n s l e y e l 于1 9 8 8 年首先提出，他成功地将基于迭代函数系 统的分形图像压缩应用于计算机图形学上，对航空图像进行压缩编码，并获得了 ： 1 0 0 0 0 ：1 的压缩比。但其算法有很大的局限性，最主要的就是编码过程需要人工 干预。 其后，在1 9 8 9 年，j a q u i n 提出了基于块的分形图像压缩算法 2 、3 】。虽然该 算法的压缩比大大低于m b a m s l e y 。但是它的编码过程可自动进行。因此此算法 已经成为这一研究方向的典型代表。 此后，国内外的研究工作还把分形和其它经典算法相结合。y z h a o 等人将 分形与d c t 相结合，用d c t 保留了图像的细节，取得了较好的效果【4 】。h a m z a o u i 等人把矢量量化与分形结合实现了编码压缩 5 】。1 9 9 8 年，d a v i s 从小波变换域角 度分析了分形编码算法 6 】，在小波域进行分形变换。 。 但由于在分形压缩编码过程中，运算量大，从而造成编码时间过长，且提高 压缩比同减小失真度之间的矛盾始终存在，从而局限了它的实用性。解决该问题 的主要方法是对定义域块和值域块进行正确地分类。分类的作用在于缩小最佳匹 配的搜索范围，使一个值域块只在它的同一类的匹配块集合中进行匹配，这样就 把全局搜索变为局部搜索，从而达到减少编码时间的目的。 p o l v e r e 根据基于块中密度中心的特征进行分类用。该方法计算一个图像块 的密度中心坐标，且根据密度中心位置在仿射变换下到图像块中心点的幅角不变 性，构造出由两个特征幅角鼠和岛。：组成的二维特征向量v ( 研，岛) ，在匹配搜 索中只对特征向量足够接近的定义域块和值域块作回归分析。 王学军首先用l a p l a c i a n 算子提取图像的边缘信息，然后根据边缘信息中非 西北工业大学硕士学位论文第一章绪论 零像素的数目和彼此相连的非零像素的数目来进行分类【8 】。 y f i s h e r 对给定的定义域块和值域块分为了左上、右上、左下、右下4 个象 限，分别根据每个象限的灰度级平均值和方差在图像块中出现的顺序来实现分类 【9 、1 0 】，共有7 2 类。 h u r t g e n 和f i s h e r 方法有许多相似之处，它同样是把矩形块分为4 个象限， 每一个象限对应一个比特位，如果该象限的亮度均值大于整个块的亮度均值，就 给对应象限的比特位置l ，否则就置0 。这样，一共有1 6 种可能的分类，但因为 不可能出现“1 1 1 1 ”的情况，故实际上只有1 5 类，然后同样用方差在图像块中 出现的顺序来实现分类得到2 4 个子类，予是一共得到3 6 0 个类【l l 】。 s a u p e 把定义域、值域的匹配查找转化为其相应特征空间的近领域搜索问题 【1 2 】 c h e r ty ：根据值域块和定义域块的特征差值来进行分类【1 3 】 许多人提出了各自有效的分类方法，加快了编码速度。但是随着编码时问的进 一步减少，解码图像质量也显著下降。为了解决这一问题，本文提出了自适应分 类方法用来对定义域块库进行分类，并用实验证明了此分类方法的有效性，给出 了一种基于自适应分类的快速分形编码方法：为了解决矩形划分计算量大的问 题，本文提出了混合分类法；为了提高解码质量，本文提出了基于二维特征向量 的自适应分类法，并分别用实验证明了本文所提出的方法的有效性。 1 2 图像修复的发展及研究现状 1 2 1 数字图像修复的背景和意义 早在文艺复兴时期，人们就开始修复中世纪的一些艺术品，目的是通过填补 一些裂缝来使中世纪的一些图画得到翻新，这样的工作就叫做”r e t o u c h i n g ( 润 饰) ”或者“i n p a i n t i n g ”( 修补或修复) 。那时的修复工作主要是由专业修复师手 工完成的，存在着费时、辛苦、主观等缺点。 受博物馆艺术家人工修复工作的启发，图像恢复技术开始作为数字图像处理 科学的一个新的关注方向，吸引了国内外众多学者对其进行了广泛而深入的研 究。数字图像修复是数字图像恢复技术的一个重要分支，就是用一定算法来处理 图画、照片或影片，包括使受损的图像恢复、移走或取代照片中被选择的物体等 2 西北工业大学硕士学位论文 第一章绪论 等。其主要工作原理是利用数字图像待修复区的邻域或前后帧信息填充数字图像 待修复区。数字图像修复的主要目的是使观察者无法察觉图像己被修改，或者获 得更好的视觉效果。 数字图像修复在图像处理、图像分析、电影工业、图像传输等中也有着广 泛的应用，例如照片或电影中划痕活文字的去除，遮蔽物去除( d i s o c c l u s i o n ) ，图 像中特定目标的消除等都与图像修复有关。还有通讯技术中的图像插值，图像 替换和错误隐藏等。 1 2 2 数字图像修复的发展状况 图像修复技术的发展主要集中在两个领域方向：基于纹理结构的图像修复和基于非纹 理结构的图像修复，如图1 1 所示： i 零鬟? 誓；翠7 謦鬻 i 兰娄，。ii 、鹰善：，霪“，篓，翟一鼍一p。甘麓一茹。鬻| 图1 1 图像修复技术的发展 对于非纹理结构的图像修复技术，目前研究者多采基于高阶偏微分方程( p d e ) 模型的修补算法，其主要思想是利用待修补区域的边缘信息，确定扩散信息和扩散 方向，从区域边界各项异性的向边界内扩散。该算法可同时填补多个包含不同结构 和背景的区域，并且对待修补区的拓扑关系没有限制。另外，m _ a n o u 等人根据上述 思想提出了一种快速图像技术，通过在待修复区域边界确定等光强线方向，用直线 连接对应的等光强线，边界通过将待修补区邻域信息在等光强线范围内扩散来填补 待修补区。这种方法对简单结构图像有较好的修复效果，而且修复时间大大缩短。 基于纹理结构的图像修复技术是纹理合成技术在图像修复领域的一种应用。纹 西北工业大学硕士学位论文 第一章绪论 理合成技术是当前计算机视觉和计算机图形学研究的热点之一，它在纹理填充、图 像和视频的有损压缩以及图像前景的消除中都有着广泛的应用。因为纹理是物质构 成成分的分布或特征的反映，它的局部性状信息能够表现相同纹理的共性，如木纹， 岩石花纹等。对一张纹理图，任取其中两小块纹理都是相似的。一般的，纹理可以 分为重复性纹理和随机纹理。纹理合成可以简单的描述为如下过程：对于给定的有限 纹理样本，合成与样本同样韵纹理，这种合成在视觉上是相似而连续的。这种技术 的基本思想就是首先选择一个纹理，通过仿真并生成局部纹理将它合成到需要填充 的区域里面去( 比如孔洞) 。 图t - 2 纹理合成修复 基于样图的图像修复方法有效地结合偏微分方程和纹理合成修复的优点。 这类方法一般分为三步计算优先级，确定当前需要填充的面片( 简称当前面 片) 优先级是指面片填充的顺序，优先级高的面片先填充，优先级低的后填 充。根据当前面片中已知信息，在图像的已知区域寻找相似块。用相似块 填充当前面片。此方法的修复效果比较理想。但是此方法忽略了图像的内部特 性，对结构面片和纹理面片采用同样的方法修复。针对此问题，本文首先提出 了一种度量图像结构性强弱的标准性系数。然后利用此系数将待修复块分为结 构块和纹理块。对于结构块和纹理块，采用不同的方法进行修复。 4 西北工业大学硕士学位论文 第一章绪论 1 3 本文的内容安排 本文共分六章，各章内容安排如下： 第一章介绍分形图像压缩的研究及发展状况和图像修复技术的研究及发展 一状况； 第二章介绍分形几何理论的发展概况、分形图像压缩的基本过程和改进的分 形图像压缩方法，并简要介绍了分形编码加速方法中存在的问题： 第三章针对分类方法中普遍存在的编码速度与解码质量之间的矛盾。提出了 一种衡量分类方法性能优劣的指标体系，并提出了一种基于定义域块数目的自适 应分类方法。结合满意匹配和质心特征得到了一种快速分形编码方法。为了提高 压缩比，我们采用四叉树划分，并提出了变门限方法，结合自适应分类法和满意 匹配，得到了一种基于四叉树划分的快速分形编码方法，分别作了相关的数值实 验。 第四章针对分形图像压缩中矩形划分计算量太大的问题，结合均匀分类和自 适应分类提出了一种混合分类法，并将其应用于质心特征，得到了一种基于矩形 划分的快速分形编码方法。并作了相关的数值实验。 第五章为解决分类方法中，编码时间的减少通常是以牺牲图像解码质量为代 价的问题，提出了一种基于二维特征向量的自适应分类方法。利用“分割一合并， 再分割一再合并”的过程对定义域块库进行分类。把图像的l 、2 阶矩不变量作 为图像的主副特征得到了一种能够较好地保证图像解码质量的快速分形编码方 法。并作了相关的数值实验。 第六章首先介绍了图像修复技术的原理，历史和现状，然后为解决在相似性 度量准则中引入梯度后计算量大大增加的问题，提出了一种基于像素的纹理标准 性系数，用来衡量图像纹理性的强弱。根据边缘面片纹理性的强弱用不同的方法 进行修复。得到了一种新的图像修复方法，并作了数值实验。 西北工业大学硕士学位论文 第二章分形图像压缩概述 第二章分形图像压缩概述 2 1 分形几何理论的发展概况 1 9 7 5 年，美国数学家b b m a n d e l b r o t 1 4 ，1 5 发表了他的划时代著作f r a c t a l s ： f o r m ，c h a n c ea n dd i m e n s i o n ) ) ，宣告了分形几何作为“大自然的几何学”这一新 型的几何语言的诞生，它能有效地描述自然界及科学研究中遇到的各种各样的复 杂的图形。在短短二十几年的时间里，以分形几何作为其数学基础的分形理论已 取得了迅速的发展，并已广泛应用到了当今的各个领域中。分形、小波与混沌被 认为是2 0 世纪后半叶科学界的三大发现。 分形理论的发展过程可以分为三个阶段 第一阶段是从1 8 2 7 到1 9 2 5 年，在这一阶段，数学家们构造并研究了种种奇异 或病态的集合及其图像，而且试图从这类集合与经典几何的差别进行描述，分类和 刻画，其中的一些后来被认为是典型的分形，如w e i e r s t r a s s 函数，k o c h 曲线，c a n t o r 三分集，p e a n o 曲线 第二阶段大致从1 9 2 6 到1 9 7 6 年在这半个世纪里，人们对分形几何的性质做 了深入的研究，p o n t r y a g i n , b e s i e o v i e h 等研究了曲线的维数，分形集的局部性质，分 形集的结构以及其在数论，调和分析，几何测度论中的应用，他们的研究成果极大 地丰富了分形集合理论，在这一阶段，l e v y 在两个方面的工作极其重要：第一，研究 了予相似集；第二，建立了分数布朗运动的理论，成为随机分形理论系统的重要的 先驱者之一 第三阶段为1 9 7 6 年至今，近些年来，分形的发展十分迅猛，不仅在理论方 面得到了进一步的完善，而且其研究领域也涉足甚广。如随机分形、随机布朗运 动、布朗曲面多重分形、迭代函数系统和分形的数值方法等。其它自然学科的迅 速发展也促使分形成为一门描述自然界中许多不规则事物的规律性的学科。它已 被广泛应用在生物学、地球地理学、天文学、计算机图形学等各个领域。用分形 理论来解释自然界中那些不规则、不稳定和具有高度复杂结构的现象，可以收到 显著的效果。国内外许多学者对分形的基础理论及其在各个领域内的应用进行了 大量的研究工作。目前，分形与小波【1 6 ，1 7 】、分形与混沌 1 8 】等的研究已引起人 6 西北工业大学硕士学位论文 第二章分形图像压缩概述 们的普遍关注。由于分形取得了令人瞩目的成果，于是就有了后来的分形几何学 分形几何是一门几何学，它研究的对象是欧氏空间的一类子集，这类子集结 构较复杂。如果说，欧氏几何是研究规则图形的几何学，那么，分形几何则是研 究“不规则”图形的几何学。这里的“规则”本质上指的是逐段可微或者更确切 地说，是逐段光滑的。而所谓“不规则”图形应当是满足某些“新规则”的图形， 正是这些“新规则”构成了分形的独特特征。 按一般方法，似乎应首先给分形下一个明确的定义，对给定的图形，再根据 它是否满足给出的定义，来判断它是不是分形。分形几何的创始人m a n d e l b r o t 曾给出了两个定义。最初( 1 9 8 2 ) 他把分形定义为分形维数严格大于其拓扑维数 的集合，但这显然把那些有着整数维的分形如p e a n o 曲线排除了。1 9 8 6 年他又 给出了第二个定义：具有在某种方式上部分与总体相似的形状特征的集合称为是 分形。这个定义强调了分形集的某种自相似特征，但仍有很多分形集没有包含在 其中。这些简单的定义确难包括分形如此丰富的内容，那么究竟什么是分形呢? 1 9 9 0 年英国的k e n n e m j f f l c o n e r 将生物学中对“生命”定义的方法引入到对“分 形”的定义【1 9 】。他认为虽然难于对“分形”下一个确切的定义，但可通过分形 集的一些特征来说明，如同“生命”并无精确的定义，但“生命”概念可通过生 命体的一系列特征来表征一样。 。 原则地说：分形集f 是一些简单空间如r 。，c ，e 上的一些“复杂”的点 集【2 0 】，这种几何具有某些特殊性质，首先是它所在空间的紧子集，并具有下列 典型的几何特征： ( 1 ) ，具有精细的结构，即有任意小比例的不规则的细节： ( 2 ) f 是如此的不规则，以至于无论它的整体或局部都不能用微积分的或传统 的几何语言来描述； ( 3 ) f 一般具有某种自相似或自仿射性质，可能是近似的或统计意义下的： ( 4 ) f 的“分形维数”( 以某种方式定义的) 通常严格大于它的拓扑维数； ( 5 ) 在多数令人感兴趣的情形下，可以通过递归、迭代等简单的方式产生。 对于各种不同的分形，有的可能同时具有上述的全部特征，有的可能只有( 1 ) 至( 5 ) 中的大部分性质，而对某个性质有例外，但这并不影响我们把这个集合 称为分形。应当指出，自然界和各门应用科学中涉及的分形绝大部分都是近似的， 7 西北工业大学硕士学位论文 第二章分形图像压缩概述 当尺度缩小到分子的尺寸，分形性也就消失了。严格的分形只存在于理论研究中， 正如严格的直线仅存在于理论研究中一样。 2 2 分形图像压缩的基本过程 m i c h e a leb a m s l e y 是将分形理论用于图像压缩的第一人，他的论文【2 l 】宣 用于整个图像的一组仿射变换 匆艺。组成后者构成了一个i f s 。将i f s 的系 的这个方法无法处理一般图像。b a r n s l e y 的博士生a m a u dj a c q u i n 改进了这个方 法。他提出了局部迭代函数系统【2 1 1 3 j ，通过下述两个步骤解决了i f s 方法所存 伺恻= 刖纠 其中“( z ) = s z + o 。表示像素点灰度值的压缩仿射变换，即墨 _ o ，y o 二：黝：f x 媳 i f xy ： 亿， s ， 万+ 口t a r i ( y 工) ， o ， o , y 邻近搜索法【2 6 】。对每一个值域块，其匹配定义域块只在其邻近区域中寻找， 其理论依据是自相似块的位置的概率分布几乎都集中在子块的附近； 函数方法匹配 2 7 】，不直接比较值域块与定义域块之间的自相似性，而是把 它们都与一个单位向量进行比较，只对与单位向量接近的那些定义域块才进 行匹配计算； 多分辨率的方法 2 8 、2 9 】，通过把待编码图像分成几种分辨率，对每一值域 块，其对应定义域块的搜索先在低分辨率下进行，如果在低分辨率下不能 找到，则不可能在高的分辨率中找到，这使搜索的目标范围缩小，也简化了 搜索时的计算量； 利用进化算法进行定义域块的搜索【3 0 】。这是一种随机搜索方法，它不像 j a q u i n 方法那样对定义域块进行穷举的搜索，来找到一个与值域块相匹配的 定义域块，而是通过随机抽取少量的定义域块( 称为进化集) ，在进行集中 进行匹配搜索，找到匹配较优的定义域块，进行传种、扩大；而对匹配较差 的定义域块进行淘汰，通过几次迭代，那些较优的定义域块能逐步进化，达 到较快地搜索到最优匹配定义域块的目的。 2 3 2 改进解码图像质量的方法 在基本模型中，定义域块和值域块尺寸和形状都是固定的。其实，定义域块 和值域块的尺寸和形状，对于分形图像编码的质量和压缩比的影响很大。而解码 图像的质量和压缩比之间是相互矛盾的。如果定义域块和值域块的尺寸取得很 大，虽然定义域块库中的定义域块数目很小，但很难找到值域块与定义域块之间 的相似关系，即使在此情况下能求出最优匹配系数，但拼贴误差将很大，其最后 的解码图像的质量也很差。另一方面，定义域块与值域块之间的自相似性总是能 找到的，极限情况是值域块的大小为一个像素。但在此情况下，定义域块数目将 变得很大，存储变换参数将占用甚至比原图像更大的存储空间，这显然达不到压 缩的目的。因此许多学者提出了灵活的图像划块方式。 1 四叉树方法 f i s h e r 和j a c q i u n 等人提出了根据允许的匹配误差和压缩比而改变值域块和 西：l l ；- r 业大学硕士学位论文 第二章分形图像压缩概述 定义域块的尺寸的做法。先在大尺寸的值域块和定义域块之间寻找满足匹配要求 的相似性，对达不到要求的值域块，缩小其尺寸和相应的定义域块的尺寸，再考 察它们的相似性。定义域块与值域块之间的匹配尺寸是以要求误差和压缩比来进 行的，这个方法称为自适应的四叉树方法 3 1 】，这是目前最流行的分形编码方法。 2 其他的划块方法 在分形编码中，为了方便往往将值域块、定义域块取为正方形。但是，正方 形并不是最好的划块方式，它的最大缺点就是值域块与定义域块的划分与图像内 容无关，这显然是影响解码图像质量的一个重要的因素。为此，一些学者提出了 矩形、三角形、多边形的分割方法。 矩形分割方法 3 7 1 矩形分割方法又称h - v 分割方法，它比上述四叉树方法更灵活，因为分割方 向是可变的。其基本思想是：图像首先被分割成矩形。给定一个矩形值域块，如 果找不到在给定误差下的相似定义域块，则四叉树方法被改为用两种分割进行： 一是将原矩形平行分割为两个矩形，二是垂直分割为两个矩形，然后再进行匹配 搜索。其分割的标准是建立在图像的灰阶均匀性上；通过计算这个块在垂直方向 和水平方向上的不均匀性，取这两个不均匀性数量的最大值，决定分割的方向和 位置，并以这种矩形分割的值域块寻找有关定义域块。这种分割方法不如四叉树 简单，但能带来较好的解码图像质量。 三角形分割方法 四叉树方法和i - i v 方法的缺点是当要求图像有较高的压缩比时，由于人眼对 水平和垂直方向的视觉灵敏性，解码图像的相邻像素块之间的边界看起来很明 显。造成这种现象的主要原因，是在寻找匹配的定义域块时用到的旋转变换其角 度只能是9 0 的倍数，这显然不够