（交通信息工程及控制专业论文）分形、小波变换和神经网络在图象处理中的应用研究.pdf

o 7 丁膨9 f 中文摘要 分形、小波变换和神经网络在图象处理中的应用为图象处理中的许多问题 的解决提供了新的手段，具有很大的潜力和发展前途。本报告主要介绍分形) ， 小波变换和神经网络在图象处理中应用的几个方面。 ，、 ( 本报告首先概述了图象处理技术的发展及其在其它领域中的应用和存在的 问题。简要介绍了分形、小波变换和神经网络在图象处理中的应用。l 叉 第二章哥在介绍分形和分形维数的基础上，研究了图象的分形插值方法， 并把它应用于图象压缩编码和图象放大。着重研究了图象的分形压缩编码问 题，提出了d c t 域分形图象压缩编码方法和快速的编码算法。 中的应用的两个实例，一个是纹理图象分割， 关彳喜词 小波变换和神经网络在图象处理 另一个是图象压缩编码。 ：叼熟星，易哆，参形伊敬，- 如埃，辛诤戈 a b s t r a c t t h ea p p l i c a t i o n so ft h ef r a c t a lt h e o r y , w a v e l e tt h e o r ya n dn e u r a ln e t w o r kt o i m a g ep r o c e s s i n gp r o v i d en e w m e t h o d st om a n y p r o b l e m s i nt h i sf i e l da n d g i v ev e r y p r o m i s i n g s o l u t i o n si nt h i s r e p o r t s o m ea p p l i c a t i o n so ff r a c t a l t h e o r y , w a v e l e t t h e o r ya n dn e u r a ln e t w o r k t oi m a g e p r o c e s s i n g a r eg i v e n t h ed e v e l o p m e n ta n da p p l i c a t i o n so fi m a g ep r o c e s s i n ga n ds o m ep r o b l e m s e x i s t i n gi n t h i sf i e l da r eg e n e r a l l ys u m m a r i s e da tf i r s tt h ea p p l i c a t i o n so ff f a c t a l t h e o r y , w a v e l e tt h e o r ya n dn e u r a ln e t w o r k t oi m a g e p r o c e s s i n g a r eo u t l i n e db r i e f l y i n c h a p t e r2 ，f r a c t a li m a g ei n t e r p o l a t i o n m e t h o da n df r a c t a l i m a g ec o d i n g m e t h o d sa r es t u d i e db a s e do nf f a c t a lt h e o r ya n df r a c t a ld i m e n s i o n sf r a c t a li m a g e c o d i n g i nd c td o m a i na n di t sf a s ta l g o r i t h ma r ep r e s e n t e d 。 ab r i e fi n t r o d u c t i o no fw a v e l e tt h e o r ya n dab r i e fi m r o d u c t i o no fs o mn e u r a l n e t w o r ka r eg i v e ni nc h a p t e r3a n di nc h a p t e r4 r e s p e c t i v e l y a tt h ee n do f t h e r e p o r t ，t w oe x a m p l e so fi m a g ep r o c e s s i n gu s i n gf f a c t a lt h e o r y w a v e l e tt h e o r ya n ds o mn e u r a ln e t w o r kc o m b i n e dt o g e t h e ra r er e p o r t e d ，o n ei s t e x t u r ei m a g es e g m e n t a t i o n ，a n da n o t h e ri si m a g ec o d i n g 2 第一章引言 数字图象处理是一门年轻的、发展十分迅速的学科，并且在许多领域有着 广泛的应用。同时一些新兴的科学技术在数字图象处理中的应用，也大大促进 了数字图象处理技术的发展。本章首先概述了数字图象处理技术的发展、应用 及存在的一些难题，其次概述了主要的三门新兴科技在图象处理中的应刚，其 中着重讲述分形技术在图象处理中的应用。最后，给出了本研究报告的内容安 排。 1 1 数字图象处理的发展概况、应用及存在的问题 数字图象处理技术是- f - j 新兴的学科。虽然早在本世纪二十年代，图象处 理技术已应用于改善海底电缆传送的图片的质量，但其后的发展十分缓慢。这 是由于表示数字图象的数据量非常大，数字图象处理技术的计算量往往也很 大，如果没有计算机，处理数字图象是难以想象的。到了本世纪五十年代，由 于计算机技术的飞速发展和广泛应用，数字图象处理才真正引起人们的巨大兴 趣，并取得迅速发展，同时逐渐在其它领域得到应用。到了六十年代末，数字 图象处理已形成了比较完整的理论体系，成了一门新兴的学科。六十年代至八 十年代中期，由于离散数学理论的创立和完善，数字图象处理技术又一次得到 了迅速的发展，处理理论和方法进步完善，应用范围更加广泛。八十年代中 期以来，由于一些新兴的学科、方法的引入，使数字图象处理技术正经历一次 新的飞速发展。这一发展的趋势我们将在下一节作以介绍。 伴随着对数字图象处理技术的研究，图象处理技术在现今信息社会也正扮 演着越来越多、越来越重要的作用。大到全球定位系统及全球互联网络，小到 信用卡的识别，图象处理技术无处不在、无处不有，概括说来，图象处理可以 用在以下方面： j 图象通信和存贮。现代信息社会通信中，不仅涉及到语音和文字的传 输和存贮，随着技术的发展，也越来越多地涉及到图象的传输和存贮。 图象生动、形象、逼真，有时传输和存贮图象是非常必要的。在更有 效地传输和存贮图象数据方面，图象处理中的图象压缩技术起着重要 的作用。 2 卫星图象。通过处理卫星图象，人们向外了解宇宙，向内了解地球自 身，这对军事、科学、经济、日常生活等多方面都有不可低估的作用。 近年来发展的全球定位系统就依赖于卫星图象的传输和处理。 3 生物医学领域。数字图象处理技术被广泛应用于生物医学领域的研究 和医学诊断中，医学图象已成为生物医学领域中研究和具体工作的一 个重要工具和手段。 4 工业生产中的应用。这方面的应用非常广泛，主要有产品的质量检测、 生产过程的自动控制、计算机辅助设计( c a d ) 和计算机辅助制造 ( c a m ) 等。 5 军事、公安、金融、档案等方面的应用。 6 计算机视觉。 当然还有许多其它方面的应用，如在虚拟现实技术( t ) 中的应用等， 这里就不一列举了。 尽管图象处理技术已经得到了很大的发展，并且这种发展的速度也越来 越快，但图象处理领域仍存在诸多的难题等待克服。以下仅举几例来说咧这个 问题。例如用现有的某一种方法进行图象边缘的提取时，边缘的连续性和精确 位置是一对矛盾。为了保证边缘的连续性进行的边缘提取，边缘往往很粗，边 缘的精确位置就难以确定；相反，为了保证边缘的精确位置进行的边缘提取， 部分边缘将难以提取出，因而边缘的连续性将难以保证。在图象压缩方法中， 压缩比和信噪比也是一对矛盾，为了提高图象传输和存贮的效率，就要提高压 缩比，但压缩比的提高往往以降低图象质量作为代价；相反，为了获取足够信 息或为了观赏的需要，在很多场合下又要求提高恢复图象的质量，这时压缩比 就不能太高。在图象目标识别中，目标的误判和漏判也是一对矛盾，为r 防止 目标的误判，目标的判别门限或阀值就要求选取得比较严，从而导致漏判；为 了肪止目标的漏判，目标的判别门限就要求选取得比较宽，从而导致不是目标 的物体也被判为目标，即误判。图象处理领域中还有其它的许多难题等待克服， 这里就不再一列举了。这些难题的存在。就需要我们去寻求图象处理的新方 法。采用新的图象处理方法，并不是为了根本地解决这些矛盾，也不可能根本 4 地解决这些矛盾，而是为了使这些矛盾缓和下来，达到较好满足人们的需要的 目的即可。 12 三项新理论在图象处理中的应用 数字图象处理是一门年轻的学科，又是- - f l 边缘交叉学科，其它领域的研 究新进展对其有很大的推动作用。近年来，伴随着新的数学理论，如数学形态 学、分形几何学、小波变换等，以及相关学科，如模式识别、神经网络、感知 生理心理学等的出现和深入研究，在图象处理领域中出现了若干国内外热门研 究课题。其中尤其是对神经网络、小波变换、分形几何学在图象处理中的应用 的研究，已经并将继续对图象处理中的许多问题的解决提供新的思路和方案。 我们这里粗略介绍一下神经网络、小波变换在图象处理中的应用，较多地谈一 下分形理论在图象处理中的应用问题。 小波分析是一种新的时( 空) 域频域信号分析工具，是国内外学者研究 的热点。借助于这种分析工具，可以将图象信号分解成为许多具有不同的空间 分辩率、频率特性和方向特性的子带信号，实现了低频长时特征和高频短时特 征的同时处理，有效地克服了传统分析方法( 如f o u r i e r 分析) 的局限性。小 波分析提出以后，很快就被应用于图象处理的诸多方面，例如图象压缩、图象 边缘检测、图象分割等，都取得了很好的效果。 神经网络的特征是并行分布处理，特别适合于作模式识别及分类。而且神 经网络在某种意义上与人的视觉系统相似，因而把神经网络引入图象处理领域 是很有意义的。神经网络可以应用于图象处理的以下方面：1 ) 图象模式汉别； 2 ) 图象特征提取；3 ) 图象边缘检测；4 ) 图象分割；5 ) 图象压缩编码。 经典的欧氏几何学一般适于用来研究比较规则和简单的形状，但是自然界 的实际景物绝大部分却是由非常不规则的形状( 如处处连续处处不可导) 组成 的。为了研究这些对象，人们创立了分形几何学。分形的基本特征是白相似性， 它反映了自然界中广泛存在的一类事物的基本属性：局部与局部、局部与整体 在形态、功能、时空等方面具有的相似性。 在把分形理论应用于图象处理中时，首先遇到的问题将是“图象有没有分 形特征? ”。我们认为“图象有没有分形特征? ”依赖于对分形和分形维数的 正确认识。分形是自然形态的几何抽象。如果对分形和分形维数的理解局限于 严格的数学定义，那么不单一般图象没有分形特征，就是自然界也不存在“真 正的分形”了。当把分形和分形维数做一定近似理解时，那么图象就可以有分 形特征了。 如果图象具有分形特征，就必然存在某种形式的相似，而相似就表叫存在 信息冗余，所以分形理论在图象处理中的第一个应用就是依据这种相似进行图 象数据压缩。既然存在某种相似，因而也就可以利用分形维数进行图象插值。 以实现图象放大和插值压缩编码。当把分形维数理解为客体复杂性或物体表面 粗糙度的标志时，分形维数就可以作为一种图象纹理特征参数而用以图象纹理 分割。另外分形维数还可以用于进行图象边缘的提取等方面。 1 3 本研究主要完成的工作 本研究主要完成以下工作： 1 通过对分形理论和现有图象压缩编码方法的研究，提出了d c t 域 分形图象压缩编码方法。为了克服分形图象压缩的根本缺陷压 缩速度问题。提出了提高分形压缩编码压缩速度的方法。并把这种 分形图象压缩编码方法应用于图象的无损压缩和级进式转输。 2 把分形插值应用到图象领域中，实现了分形插值图象放大和压缩编 码。 3 对小波理论和小波分析方法进行了研究，在小波变换域进行分形图 象压缩，取得了好的效果。 4 通过对神经网络的研究，并结合小波变换和分形方法，提出了纹理 图象的多尺度分割方法。 2 1 1 分形 第二章分形理论及其在图象处理中的应用 2 1 分形与分维 “分形”( f r a c t a l ) 是一个很新的词汇，1 9 7 5 年，美国科学家m a n d e l b r o t 以大无畏的科学探索精神，提出了“分形”( f r a c t a l ) 的概念，但由于分形理 论只被少数人所认识，所以即使是现在刚刚发行的词典里也查不到关于“分形” 的定义。尽管人们对分形的认识是如此的贫乏，但是分形现象却是非常酱遍存 在的一种现象；尽管人们对分形理论的认识也才刚刚起步，但是分形理论却是 一个在很多领域发生作用的理论。 其实分形的某些概念，早在一百多年前便已出现。只不过从传统的眼光来 看，它们的存在一直被认为是一种反常的现象，而称为数学中的反例。分形的 一个重要的特征是具有无限精细的结构，它是对大自然的数学抽象。在计算机 产生以前，这种“无限精细”的结构很难被人们直接地观察到。到了六十年代， 由于计算机的应用，分形结构才被大量发现，从而促进了分形理论的提出。 由于计算机的广泛应用，人们才发现了“蝴蝶效应”、“倍周期 现象”，才能够提出后来分形生成的重要手段l 系统和迭代函 数系统( i f s ) 。在这些现象发现的基础上，1 9 8 2 年m a n d e l b r o t 系 统阐述了分形理论，分形是关于大自然的数学描述，这标志着分形 几何学的产生。 “分形”是一个很抽象和很基本的概念，象数学中“集合”的概念一样， 至今人们对它仍没有严格的科学的定义，而只有描述性的定义。人们了解和认 识分形，不是从分形的严格的科学的定义开始的，而是从某些具体的分形结构 开始的，从这些具体的分形结构中人们可以得到分形的直观形象的认识。 产生具体分形结构的两种重要的方法是l 系统和迭代函数系统( i f s ) 。l 系统这个名字的l ，是指美国生物学家l i n d e n m a y e ra 。他于1 9 6 8 年提出了研 究植物形态与生长的描述方法，开始时只着重于植物的拓朴结构，即植物组件 ( 主干、旁支等) 之间的相邻关系，后来把几何解释加进描述进程，形成后来 所谓的l 系统。l 系统分为两种，一种是确定性l 系统，另一种是随机l 系统。 二者均能生成给人印象非常深刻的分形结构，其中尤其是随机l 系统，它能够 生成非常逼真的植物的自然形态。 迭代函数系统( i f s ) 是分形绘制的最重要方法。它在图象数据压缔i 中起 重要作用，我们将在后面作介绍。植物的叶子具有典型的分形结构，这q ! 给出 用i f s 绘制的一个叶子( 图1 ) ，以得到关于分形的直观认识。 图l 。i f s 绘制的叶子 人们已经认识了很多象叶子的结构这样的典型的分形，但人们对于分形的 统一的观念只是以下关于分形的描述： 称集合f 是分形，f 则应具有以下性质： ( 1 ) f 具有精细的结构，也就是说在任意小的尺度之下，它总是有复杂的 细节； ( 2 ) f 是不规整的，它的整体与局部都不能用传统的几何语言来描述； ( 3 ) f 通常有自相似形式，这种自相似可以是近似的或是统计意义下的： ( 4 ) 般地，f 的某种定义之下的分形维数大于它的拓朴维数； ( 5 ) 在大多数令人感兴趣的情形下，f 以非常简单的方法确定，可能由 迭代过程产生。 2 1 2 分形维数 维数是图形的最基本的不变量，分形维数是刻画分形的不变量，一般认为 它是客体复杂性或粗糙性或占据空间能力的度量，是分形的极其重要的特征数， 是判断两个分形是否一致的重要标准。分形维数定义多种多样，其中最重要的 是h a u s d o r f f 维数，因为它对理解分形的概念很重要。 对于给定的点集f c r “和万， ，j 为，的一个万覆盖， 坼 为f 的一个占覆盖2 f 的全部万覆盖。s 为一非负实数，考虑： r 、 h 。4 ( f ) = l n f h j l 铷，) 为f 的6 覆盖 1 2 - - 1 ) l l = lj 其中下确界i n f 考虑的范围是f 的全部占覆盖。当占递减时，f 的允许 的覆盖类别减少，因此d 4 ( f ) 递增；所以当占- - - 0 时，日s5 ( j f ) 趋向于仑 极限，记为： 日5 ( f ) 。慨日s ( ，) ( 2 一2 ) 对于任意fcr ”，这个极限是存在的，它可能是一个非负实数或+ o o ，我 们称h 。( f ) 为集合f 的s 维h a u s d o r f f 测度，可以想象，h 越小，如，j 作为 f 的艿覆盖，其覆盖的“面积”越接近于f 本身的“面积”，所以可以取占 s ，则： h ( f ) u 啦占“h 旷) o u 如果月。旷) m ，则月) = 0 ，这就是说存在s 的一个临界值，使 月。( ，) 从无穷大跃变到0 ，这个临界值就称为点集f 的h a u s d o r f f 维数。记为 办( ，) ，即： 办( f ) = i n f i 5 ( ，) = o ) = s u p s ，( ，) ：悯 h a u s d o r f f 维数并不是分形集特有的，对于任何集合都可以计算它的 h a u s d o r f f 维数。但是对于分形集而言，它的整体和任一局部具有相同的h a u s d o r f f 维数，这是分形集与非分形集的区别。h a u s d o r f f 维数有许多性质，其最能体现 分形集特征的是以下性质。 若f c 只w ，r ：f r m 是双l i p s c h i t z 变换，则h a u s d o r f f 维数有如下性质： d 。( ，( f ) ) = d h ( f ) ( 2 3 ) ( 2 3 ) 式提示了分形集的重要特征。在分形几何中，如果两个集合之间 存在双l i p s c h i t z 变换，则视这两个集合是相同的；如果两个集合具有不同的 h a u s d o r f f 维数，则它们之间不存在从一个集合到另一个集合的双l i p s c h i t z 变 换。如果两个集合具有相同的h a u s d o r f f 维数，则有可能寻找到一个双l i p s c h i t z 变换，从个集合出发产生出另一个集合。对于任一严格分形集而言，其整体 和任意大小的各个局部都具有一个h a u s d o r f f 维数，因此可能寻找到一个双 l i p s c h i t z 变换，由分形集的任一部分产生另一部分或分形集合整体，或由分形 集合整体产生其任一部分。这也就是说，对于分形集而言，分形集的任意一局 部所包含的结构和信息都是一样的，并且都和分形集合整体所包含的结构和信 息一样。这一结论充分体现了分形集合的自相似性、无限精细结构等重要特性。 2 2 图象分形特征及提取 2 2 i 图象的f b r 场模型 分数布朗运动( f r a c t i o n a l b r o w n i a n m o t i o n ，f b m ) 是描述自然界中随机 分形最有效的数学模型。p e n t l a n d 把分数布朗运动扩展到高维情况，给出了图 象的分数布朗随机场( f r a c t i o n a lb r o w n i a nr a n d o mf i e l d 。f b r ) 模型，其定义 如下： 设x 、a x e 尺2 ，0 h 1 ，f ( y ) 是均值为0 的高斯随机函数，只( ) 表示概 率测度，”i f 表示范数，若随机场b n ( 功满足 只【业静型 叫玎 则( 功为分数布朗随机场( f b r ) 。h 参数反映了分形图象表面的粗糙度， 由h 参数值可以得到图象表面的分形维数d 为 d = 及+ 1 一h( 2 4 ) 式中所为图象表面的拓朴维数。 0 b 。( 功具有以下性质：“ e 【l b ( x + a r ) 一曰( z ) i2 】= e 【f 占( x + 1 ) 一目h ( x ) 1 2 】i a r i 2 日 ( 2 5 ) 式中e 【】表示数学期望。根据2 4 和2 5 可以计算出图象表面各处的h 值和d 值。 2 2 2 图象表面分形特征提取 对一幅肘x 的图象，选取kx k 的窗口，从图象的起始点开始，计算各 窗口内图象予块的分形特征参数，计算方法如下： ( 1 )计算图上空间距离为缸的象索亮度差的期望值 e 口。( z + 缸) 一b 。( 曲1 2 】。 ( 2 ) 确定尺度极限参数f 叫。、l 缸l 。 如果图象是完全理想分形的，则在任何尺度下分维均保持为常数。但实际 图象并不是完全理想分形的，所以要确定一个尺度范围，在此范围分维保持常 数。确定方法为：画出分维图，即l o g e fj 毋o + 卅一( 列2 相对于j 0 9 i 纠曲 线。由图中可见在一段范围内保持为直线，该范围的下、下限即为i 纠m m 、 l 酬。 ( 3 ) 计算参数h 和象索灰度正态分布的标准差盯( 盯也称为离差值) 。 根据2 5 可以得关系： l o g e 【l b 。( x + a x ) 一b ，( x 2 】：1 。g e 【l b 。( x + 1 ) 一b 。( 功i 2 】十2 日l 。g | 叫 ( 2 6 ) 即： l 。g e 【p 。( ，+ a t ) 一( x 1 2 】一2 h l o g l x ：l 。g 口：( 2 - - 7 ) 其中：盯2 = e 【l 毋o + 1 ) 一( x ) 1 2 。采用最小= 乘法解上述方程，即可计 算出参数h 和d 。从而也就可以计算出分形维数。 实际上，在提取图象上各处的分形特征时，式2 7 并未规定缸的方向性。 研究表明取不同的血方向，所得的分形特征值是不一样的。 2 3 分形插值图象放大和压缩编码 2 3 1 图象的分形插值方法 在图象处理中，经常会遇到图象插值阅题。图象内插的最简单方法是进 行线性内插，但进行线性内插后，常会使图象丢失纹理特征。利用分形插值方 法可以产生高分辨率图象，而又能保持原图象的纹理特征。p e n t l a n d 通过对自 然景物纹理图象的研究，证明了大多数的自然景物的灰度图象是满足分数布朗 随机场( f b r ) 模型的。分数布朗随机场可以用内插的方法来形成，而内插方 法所使用的是随机中点位移方法。图象的分形插值实质上是一种递归中点位移 的过程，其递推公式如下式进行。对于图象上的任意点( i ，j ) ，假定当i ，i 均 为奇数时，它的灰度值巩已经确定，则对i ，j 均为偶数时： ( ，) = 丢 ( f _ 1 一1 ) + ( ，+ l 一1 ) + ( ，一l ，+ 1 ) + ( ，十1 + 1 ) + 铲m h 伊g ( 2 8 ) 当i ，j 中有且仅有个为偶数时： 峨o ，) = 去溉o ，一1 ) + b ( i - l ，_ ，) + b 。o ，歹+ 1 ) + b 。( f + l ，硝 + 2 h 2 l 一2 ”蚓h 仃g ( 2 9 ) 其中：g 是g a u s s 随机变量，服从n ( o ，1 ) 分布，l 缸i 是样本的间距。h 为 h u r s t 指数，盯为象索灰度芷态分布的标准差。由此可见插值点的亮度由描述 原始数据的分数布朗运动参数h 和盯决定。 上述步骤可以重复迭代直到得到所需的空间分辨率为止。 2 3 2 图象分形插值放大 进行通常的内插将图象放大时，常会丢失纹理特征；利用分形内插图象 放大，就能保持原图象表面形状的内在特征。分形内插图象放大的大致步骤为： 首先取出图象待放大的部分，提取其分形参数h 和盯；然后按公式3 1 和3 一2 进行内插。 图2 为国际标准图象m u g 图象，图象大小为2 5 6 2 5 6 。在图2 中以( 2 2 5 ， 3 1 ) 为左上角，取出一块大小为3 2 x 3 2 的子图象，该子图象具有纹理特征。 把该子图象用分形内插放大为2 5 6 x 2 5 6 大小的图象，如图3 所示。由图以看 出，利用分形内插图象放大，较好地保持了原图象的纹理特征。 图2 。2 5 6 x 2 5 6m u g 图象及其一个图3 。子图象放大到2 5 6 2 5 6 3 2 x 3 2 的纹理子图象的放大图象 2 3 3 分形插值用于图象压缩编码 这里所论述的分形内插法编码，属于固定式内插法编码，即被传输或存 贮的那部分象索是固定的，未被传输或存贮的象素利用已传输或存贮的象素经 分形内插计算恢复。分形插值用开图象压缩编码有两种不同的方案，分别如图 4 和图5 所示。图4 所示方案压缩比略高，信噪比略低：图5 所示方案则刚好 相反。 编码 解码： 编码： 解码： 恢复 图象 原始 图象 图象分 形插佰 计算抽样图象子 块的h 和盯 图4 。分形内插法编码编、解码框图 图象 分块 计算图象子块 的h 和r 抽 样 图象 分块 恢复抽样 后的图象 保留h 和仃及 轴样后的图象 卧圜爱 2 4 1 引言 图5 。改进的分形内插法编码编、解码框图 2 4 分形图象压缩编码方法 图象数据的有效压缩是实现图象通讯的必要前提。图象数据压缩的目标就 是在维持可接受的图象质量条件下，尽可能地减少表征该图象的数据量。图象 数据的压缩潜力既涉及图象信源的特性，又涉及图象信宿的特性。人们观察一 幅图象时，图象给人的感觉既依赖于图象的各个部分，又依赖于的图象的各个 部分之间的关系。传统的变换编码方法的基本原理是将原来在通常的空间域描 述的图象信号变换到另外一些正交矢量空间( 变换域) 中进行描述。图象信号 一般具有明显的相关性。图象信号变换到变换域后，其相关性明显下降，这样 就能实现图象数据的压缩。通常情况下，变换是按一个个子象块或子图象进行 的，这样做利用了子图象的信息冗余，是变换编码的优点。但是它存在着明显 的缺点，即没有利用象块与图象之间，象块与象块之间的信息冗余。后一种信 息冗余存在的原因在于：自然界具有标度不变性的自相似结构，图象是自然界 的反映，因此图象也存在很多的分形特征。为了利用后一种信息冗余进行图象 的数据压缩，m b a m s l e y 于1 9 8 8 年提出了分形图象压缩编码方法，1 9 9 0 年， 1 4 a j a c q u i n 提出了全自动的可行的分形压缩编码算法。分形图象压缩编码的物 理依据是自然界具有标度不变性的自相似结构，即分形特性。分形图象压缩编 码的数学基础是迭代函数系统( i f s ) ，不动点原理( t h ef i x e dp o i n tt h e o r e m ) 和拼贴原理( t h ec o l l a g et h e o r e m ) 。但是分形图象压缩编码方法，无论是计算 速度或是恢复图象质量均不是很理想。为了提高速度，一个方向是对图象块进 行分类。匹配搜索只在同类中进行，另一个方向是确定最佳的搜索路径。为了 提高恢复图象质量，一个方向是对图象块进行细分，另一个方向是增加一些图 象子块作为匹配不佳时的补充。 2 4 2 一般分形图象压缩编码方法的缺陷和改进 最早的分形图象编码算法是基于i f s 的算法。该算法是用一套简单的变换 关系产生出复杂的图象。这样这一套变换关系或公式就可表征图象，存储和传 输图象，即可用这一套公式来代替图象本身。若能找到表示图象的这么一套公 式( 球s ) ，则可以得到非常高的压缩比。但是对于幅现实世界的图象，寻找 i f s 代码是非常困难的。所以现在一般分形图象编码算法是基于p i f s 算法。 它是将图象分成不同子块对每一个子块寻找其对应的i f s 代码。这样的i f s 代码称为p i f s 代码。解码时采用拼贴定理。由p i t s 代码可以快速地恢复图象。 现在用一般分形图象压缩编码方法进行编码时，对幅m n 的图象， 先生成( m 2 ) x ( 2 ) 的收缩图象，然后把原图象分成互不重叠的各个子块，这 些子块合起来完全覆盖该图象。对于原图象中作任子块z ，( ij 表示子块位 置) ，寻找其p i f s 代码的过程即为在收缩图象上，寻找一个大小相同的子块 g ，使得鼠，经过以下变换后形成的，。，与，非常逼近。 z ，= 霉，“( i o ( g ) ) + 包， ( 2 1 0 ) 其中i ，。代表旋转和翻转变换；i 。，代表对比度变换；6 u 代表亮度调整，它 相当于一个象索值均为一个实值6 的大小相同的子块。对原图象中每一子块 ，编码的实质就是寻找最佳的z ，o 、7 ：，牡、6 。及乳，使得z 、，与于，在某一 距离意义下最接近。 在编码过程中，l ，o 的求取是编码速度低的重要原因之一，若去掉这 变换，则有 z ，= r ，( 踟) + 6 。 ( 2 一】1 ) 则编码速度可以提高接近8 倍。而恢复图象的质量没有明显的降低。 这样( 2 1 1 ) 式可以写成 z = d g + 6 1 ( 2 一1 2 ) 式中的口、6 为实数，1 为象素值均为1 的子块，z ，、既，意义同上。 这样求取变换l ，啦和b 。的过程就是求取实数。和b 的值。 文献1 1 0 l 中确定n 、b 的方法是先让d 试取某一值，然后确定b ，最后选取 使：，与z ，最接近的一对d 、b 值。这样做是比较费时的，且求出的a 、b 值 并不是最佳的。文献【1 1 直接取a = o 5 ，这样做将造成恢复图象质量的下降。 文献 1 2 】给出了求最佳口、b 对的方法，现在般都用这种方法求取口、b 。我 们以下给出求取方法和证明其存在的问题。 z ，马z ，的含义是，d k j ，z ，) - + m i n ，d b 户，) 表示，与z ， 之间的距离，其定义可采用以下表示： d 怃，五，) ：m - i n - i 协，”一z ，副) 2 ， x = 0 卢0 z ，x , y 代表子块z ，中坐标为伍，) 的象素值，z ，7 代表子块z ，中坐标为k y ) 的象索值。埘、即为子块z ，与z ，的长和宽。 欲使d z ，- - ) r a i n ，即使 甜( ，：。z ，胁= 0 ，1 a 如。7 j 、铀：o l 可得 l 一l ，、， n t - in - i ， 、m l 一l 口h 。卜6 h 0 = z ，g “， x = 0 ，2 0 x = 0 y = 0 x = 0j o l 一l 一1 月一l 口，。+ 6 忻疗= z ，一 x = 0v = 0 x = 03 = 0 ( 2 1 3 ) 由( 2 1 3 ) 式解议程即可求出口、b 值。由( 2 一1 3 ) 式可以看出，a 、 b 是相互关联的，这样，口、b 值的误差将相互影响、传递，降低恢复图象质 量，所以( 2 一1 2 ) 存在缺陷。 为此，对( 2 1 2 ) 式进行如下改进，使 z ，= d g 一岛，) + 0 5 t 。，+ 6 1 ， ( 2 1 4 ) 1 6 其中。，为一子块，其象素值。，为 ，。k 去薹薹乳，。f l y a( 2 1 5 ) 我们证明此时口、b 不相关。 取d ( ，：j ，z ，) - - - + m i n ，从而有 甜l ，z ，批= 0 ，1 甜t z ，枷6 ：o ，j 由( 2 - - 1 6 ) 可得 口：i m - i n - i rx,2(gflx , y 划t ，一“，x y ) l 篁芝g 川t ， 口= i 一一 划l ) l 7 j = o y = o l x = oy = 0 6=1l?llx=-0y=oz，x,yu萎萎乩，x,yrn-i i j 1， 一m lh l 、 ( 2 一1 7 ) 由( 2 1 7 ) 式可知，使用( 2 1 4 ) 式，订、b 互不关联，各自的误差互 不影响、传递。 2 4 3d c t 域分形图象压缩编码方法 利用( 2 _ 一1 4 ) 式，寻找每一子块的p i f s 代码，是空间域进行的分形图象 压缩编码过程。把( 2 1 4 ) 式变换到d c t 域，即可得到d c t 域( 2 1 4 ) 式 变换形式：( 一般取子块为正方形，即埘= 1 1 ) 丘，“。 丘，。 _ j | ：。，“ 声，。 + og k ，“1 ：一g 。g 。 i o - 0 ( 2 1 8 ) 亏，x y 是夕，子块经过d c t 变换后的系数，q ，x , y 是乳j 子块经过d c t 变换后 的系数，子块b l 经过d c t 变换后的系数，只有直流项不为0 ，即b o 。此时n 和6 。变得非常容易求取，而不再用( 2 1 7 ) 式求。其中的求取按下式： 1 7 b o = f ，o 一一0 5 g ，0 。 用( 2 1 8 ) 式在d c t 域寻找p i f s 代码进行分形图象压缩编码与用( 2 m 1 4 ) 式在空间域进行分形图象压缩编码无本质区别。 d c t 变换编码利用了子块内的信息冗余，而没有利用图象子块之间的信 息冗余；分形图象编码方法利用了图象子块之间的信息冗余而没有利用图象子 块内部的信息冗余。对( 2 1 8 ) 式进行改进，使得能够利用这两种冗余。 在d c t 域，假设z 。，的d c t 某变换系数f ，与对应的f ，相差较大而 导致d 晾。e ，) 较大，则把该系数作为一个参数独立出来对待，这样将降低寻 找合适的p i f s 代码的难度，提高速度，也有利于提高丘。与f ，的相似程度， 从而有利于恢复图象质量的提高。从这一观点出发构造以下八类变换公式。 其中五，瓦，五，z l ，z 2 ，z 3 可取0 或1 ，巧z l ，t z 2 ，五z 3 ，f ，为子 块z 经过d c t 变换后的系数。 f ，“o t ，。 声，o t ，1 。 + _l 0 5 g k ，f 叩+ b o 正f ，“ 瓦f ，。o五f ，“ z l g i f 0 1 z p t ? 。 g i j 2 1 。 g ，。2 q ，2 g ，2 _ 2 ( 2 一1 9 ) 对于任一d c t 域子块，p i f s 自适应地取以上八种形式中的一种，这样就 可以利用d c t 域能量集中的特性，从而利用了子块内的信息冗余。对于每一 图象子块，其p i f s 代码可以有不同的构成形式，这种不同的构成形式一是指 ( 2 一1 9 ) 式中z ，瓦，五为0 或1 的组合形式( 共8 种，占3 位) ，二是指在收 缩图象上寻找相似子块时在什么样的区域上进行的( 共4 种，占2 位) 。口和 6 0 对恢复图象是必须的，必须记录。e ，7 和收缩图象上相似子块的位置标记 是否对恢复图象必须以及需要多少位去记录它们，则依据p i f s 代码的构成形 式而定，而p i f s 代码的构成形式，则依据图象子块的复杂程度自适应地决定。 2 4 4 实验结果和结论 曲 o 。矾吁 依据上述方法，我们做了对比实验。图6 为原始的5 1 2 5 1 2 8 的l e n n a 图象，图7 为压缩后恢复图象，变换采用8 8 子块。 图6 。原始l e n n a 图象图7 。恢复图象( p s n r 为3 24 ( 图象大小为5 1 2 5 12 ) d b ，压缩比为2 40 倍) 、 从恢复图象上看，没有! j 1 | 显的失真，图象细节和边缘恢复较好。 表1 给出了用p e n t i u m l 6 6 微机对5 1 2 5 1 2 l e n n a 图蒙进行压缩和恢复的 实验结果，可以看出在压缩比大体一致的条件下，与文献中原分形方法( 快速 l i f s ) 相比较，改进后的方法信噪比提高了3 24 d b ，压缩速度也捉高了很多。 表1 实验结果 p s n r ( d b )压缩比( 倍)压缩时间t 1 1 )箍注 l i f s 3 092 482 5弓白文献【lij 快速l i f s 2 90 2 52 7p c 4 8 6 微机 新方法 3 24 2 400 2 2 5p e n t i u m l 6 6 2 。4 5 匹配搜索方法的优化 分形图象压缩编码中匹配相似子块的最佳的搜索次序应为：区域0 寸区域 lo 区域2 一区域3 ，如图8 所示，其中区域3 对应整个收缩图象。刘于现实 世界的图象和分块迭代函数系统而言，一个值域块一：，的最佳相似予块往往存 在于收编图象( i n t ( i 1 6 ) x8 ，i n t ( i l l 6 ) x8 ) 的位置上或附近( i n t 代表取艇运算) 。 所以我们认为在上述区域_ j + 寻找的最佳相似子块，可以近似地认为是整幅收缩 图象上的最佳相似子块。这种近似所造成的恢复图象的质量下降是很小的。基 于这种认识，在整幅收缩图象上的搜寻不再是必要的，这将极大地提高编码速 度，因为对于编码过程而言，大部分的计算时间是花费在整幅收缩图象的搜寻 上。这一认识虽然看似简单，但对整个方法的改善来说，意义是很大的。 图8 。分形图象压缩编码搜索示意圈 把一个特定区域内寻找到的最佳相似子块作为整幅收缩图象上的最佳相似 子块，这种近似看法所造成的恢复图象质量的微小下降和编码速度的极大提高 可以从实验结果上得到印证。依据以上所述，作了对比实验。表2 给出了实验 结果，实验中变换采用8 x 8 子块。 表2 。搜索方法优化实验结果 p s n r ( d b )i 压缩比( 倍)压缩时间( 分) d c t 域方法3 24 f 2 4 0 1 3 5 快速d c t 域方法3 1 8 i2 4 oo 1 2 5 2 4 6i 圉象分形压缩用于级迸式传输和无损压缩 d c t 域分形图象压缩方法恢复图象质量好，方块效应比较小，是一种新 的较好的图象压缩方法。我们提出用d c t 域分形图象压缩方法去实现图象有 损压缩，基于这种有损压缩来实现图象的级进式传输和无损压缩。 2 4 6 1 图象级进式传输 图象级进式传输过程如下：1 ) 传输开始；2 ) 传输原图象的压缩图象；3 ) 图象质量可以接受，转向5 ) ，否则，转向4 ) ；4 ) 传输差图象压缩数据：并把 解压后的差图象和已接收的图象相加，转向3 ) ；5 ) 传输结束。 基于d c t 域分形图象压缩编码方法，做了图象级进式传输实验。实验结 果如表3 所示，其中比特率b p = b i t s p i x e l ，单级比特率为某一级传输时的 比特率，累计比特率为某一级传输后以前所有级比特率的累加；“一级”指对 原始图象的有损压缩传输，其他级是针对差图象的；信噪比为p s n r 信噪比， 它是每级传输后得到的恢复图象( 等于上一级恢复图象加这一级恢复差图象) 的信噪比。 从表中可以看出，二级传输后，图象质量已相当好，能满足大部分情况下 对图象质量的要求，而此时的总的图象压缩比约为1 0 倍。三级传输后，图蒙 信噪比为3 6 1 d b ，这一图象质量能满足绝大部分情况下对图象质量的要求。 表3 。级进式传输实验结果 单级比特率( b p ) 累计比特率( b ) )信噪l l ( d b ) 一级 0 3 303 33 2 4 二级 0 4 908 23 4 5 三级 o 6 3 1 4 53 6 1 2 4 6 2 图象差法无损压缩方法 图象差法无损压缩方法编码过程如图9 所示，图象差法无损压缩方法解码 过程如图1 0 所示。可以看出，该方法将对原始图象的无损压缩转化为对差图 象的无损压缩。如果有损压缩部分恢复图象质量好，则差图象的相关性就小， 因此差图象比原始图象更有利于进行无损压缩。 图9 。图象差法无损压缩方法编码过程 基于d c t 域分形图象压缩编码方法，进行无损压缩实验，结果见表4 。 可以看出本方法作为无损压缩方法，压缩倍数在两倍以上，不失为一种新的方 2 法。它的另一个优点是它同时具有无损压缩和有损压缩两种功能，它的有损压 缩部分可以作为无损压缩的一部分，也可以单独使用，这是其他无损压缩方法 所不具备的。 图1 0 。图象差法无损压缩方法解码过程 表4 。无损压缩实验结果 比特率( b p ) 原图象有损压缩部分 o4 5 差图象无损压缩部分 3 4 8 累计 39 3 第三章小波概论 3 1 小波概述 小波变换是8 0 年代发展起来的一种新的时间一频率分析方法，从理论上看 小波分析是一个新的数学分支。它是泛函分析、付里叶分析、调和分析、数值 分析的较完美的结合的产物，在信号处理、语音分析和模式识别等领域有着广 范的应用前景，被认为是近年来工具方法上的重大突破。小波分析经过数学家、 工程技术专家十多年来的共同努力，已建立了比叫完善的数学形式化体系，有 了扎实的理论基础。 信号处理与小波分析有着深刻的联系，许多小波分析的新思想是首先在信 号处理领域中提出的。小波的基本概念是1 9 8 4 年法国地球物理学家m o r l e t 在 分析地震波的局部性时提出的。他在分析地震波的时域局部化特性时，希望使 用在高频处时窗变窄，低频处频窗变窄的一种自适应变换，因为传统的f o u r i e r 分析难以满足这种要求，随后他引入了高斯余弦调制函数，将其伸缩和平移得 到一组函数系，现称为“m o r l e t 小波基”。这标志着小波概念的正式提出。9 8 6 年s j a