（电路与系统专业论文）基于分形和Markov随机场的纹理综合方法研究[电路与系统专业优秀论文].pdf

摘要 纹理综合是当前计算机图形学、计算机视觉和图像处理领域的研究热点之 一。本文对纹理综合技术进行了研究，提出了一些新的观点和算法。 本文首先介绍了纹理综合研究中的一些基本概念、常用方法以及国内外的发 展；又介绍了分形的基本理论和基本方法，为后续章节提供了理论依据；接着阐 述了纹理综合的基础以及综合方法，对纹理综合技术的做了介绍，然后对当前一 些较为典型的纹理综合方法进行了研究，并对它们的算法思想、能够处理的纹理 范围和存在的问题等进行了对比和总结。 接着介绍了基于分形的纹理综合方法，该方法以纹理样本作为输入，通过金 字塔算法和直方图匹配生成与纹理样本视觉上相似的任意大小的综合纹理图像。 这种方法是以人类的感知模型为基础的，对于计算机图形生成技术具有现实意 义。 最后主要是针对采用m a r k o v 随机场唧) 模型的基于样本的纹理综合算 法，并给了一种邻域大小自动识别的方法，能够获取最佳邻域大小，在此基础上 合成的图像能够基本满足人类的视觉要求，能够在合成质量和合成时间之间取得 平衡。进一步减少了纹理合成算法的参数输入数量，更方便了用户的操作。 在文章的最后，我们简要介绍了在纹理综合方面我们以后要做的工作。 关键词：纹理综合，纹理样本，分形，金字塔算法，m a r k o v 随机场模型 a b s t r a c t t e x t u r es y n t h e s i sh a sb e e no n eo ft h eh o t t e s ta r e a si nc o m p u t e rg r a p h i c s ， c o m p u t e rv i s i o na n di m a g ep r o c e s s i n gf i e l d s i nt h i sp a p e r , w eb r i n gf o r w a r ds e v e r a l n e wo p i n i o n sa n da l g o r i t h m s t e x t u r es y n t h e s i s f i r s t l y , w ei n t r o d u c es o m en o t i o n s , t e c h n i q u e s ，a n dr e c e n td e v e l o p m e n ti nt h e t e x t u r es y n t h e s i sf i e l d s e c o n d l y , w ep r e s e n ts o1 0b a s i ct h e o r i e sa n dm e t h o d so f f x a c t a lg e o m e t r y , w h i c hp r o v i d e sab a s i sf o rt h er e s e a r c hw o ko ft h es u c c e e d i n g c h a p t e r s t h i r d l y ，w ea n a l y z ee x i s t e n ta l g o r i t h m sd e e p l y , s o m ec o m p a r i s o n s s u m m a k z a f i o n sa b o u tt h ei d e a sa n dt r a n s a c t i n gr a n g ea n dd e f e c t so ft h e s et e x t u r e s y n t h e t i ca l g o r i t h m sa r ed r a w n , t h e nt h et h e s i sp r e s e n t sat e x t u r es y n t h e s i sa p p r o a c hb a s e do nf r a e t a lt h e o r y t h i sm e t h o dr e q u i r e so n l yt b es a m p l et e x t u r ea si n p u ta n dc a ns y n t h e s i z eb yp y r a m i d a l g o r i t h ma n dh i s t o g r a mm a t c h i n ga sm u c ha st e x t u r ea sd e s i r e d , w h i c hm a t c h e st h e a p p e a r a n c eo f t h es a m p l et e x t u r e t h ea p p r o a c hi sb a s e do i lam o d e lo f h u m a nt e x t u r e p e r c e p t i o n , a n do f p r a c t i c a ls i g n i f i c a n c eo nc o m p u t e rg r a p h i c st e c h n o l o g y a f t e rt h a t , w ep r e s e n tt h ea l g o r i t h ms a m p l e - b a s e do 咀m a r k o vr a n d o mf i e l d q t 啪m o d e l am e t h o df o ra u t o m a t i cr e c o g n i z i n g 眦g e tt h ea p p r o p r i a t es i z eo f n e i g h b o r h o o db a s e do ns t a t i s t i c si sa l s op r e s e n t e d , w h i c h 咖d e c r e a s et h en u m b e ro f i n p u tp a r a m e t e r sa n db ec o n v e n i e n t f o ru s e so p e r a t i n gi nt e x t u r e s y n t h e t i c a l g o r i t h m s t h et e x t u r es y n t h e s i sr e s u l tc a l ls a t i s f yt h er e q u i r e m e n to ft h et e x t u r e q u a l i t ya n ds y n t h e s i ss p e e da sw e l l 。 f i n a l l y ，t h ef u t u r ew o r k sa b o u tt h et e c h n i q u eo f t e x t u r es y n t h e s i sa r ei n t r o d u c e d k e yw o r d s ：t e x t u r es y n t h e s i s ，t e x t u r es a m p l e ，如e t a l , p y r a m i da l g o r i t h m , m a r k o vr a n d o mf i e l d ( m r f ) m o d e l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫壅盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：张移 签字日期：矽矽多年f 月班日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权盘洼盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 磕哟裼 签字日期：7 卯锌1 月诈日= 童名日 签字日期：衙j 月w 日 第一章绪论 第一章绪论 纹理是图像分析、图像理解、计算机图形学等领域研究的重点和难点。一方 面，纹理分析与综合方法具有许多重要应用价值；另一方面，尽管人类区分不同 纹理的能力十分突出，但自动描述、识别和生成这些同样的纹理模式却被证明是 非常复杂的，现有的纹理识别与生成方法很难满足实际应用的需要。纹理分析与 综合方法既具有一定的理论意义，又具有实际应用价值。本章主要介绍纹理研究 中的一些基本概念、常用方法和国内外的进展。 1 1 概述 1 1 1 纹理的定义m 纹理是普遍存在的，它可以描述一系列的自然现象，例如，强大噪音背景下 的声音，行动( 动物跑步) ，几何表面的颜色外观，人类的动作( 日常行为) 等等。 然而，由于纹理比较分散，来描述和重现他们就有一定的困难。只有采用有效描 述纹理特性的方法来分析纹理图像，才能真正有效描述与重构它们。 虽然纹理特征在图象分析中有广泛的应用，但是对纹理至今还没有一个统一 明确的定义。h a w k i n s 对纹理作过以下描述，他认为纹理有三个主要标志： 1 ) 某种局部的序列性在比该序列更大的区域内不断重复； 2 ) 序列是由基本部分非随机排列组成的； 3 ) 各部分大致都是均匀的统一体，在纹理区域内的任何地方都有大致相同 的结构尺寸。 根据h a w k i n s 对纹理的描述，可以给出了一个比较普遍接受的纹理定义： 由像素组成的具有一定形状和大小的集合，称为纹理基元。纹理是由纹理基 元按某种确定性的规律或只有某种统计规律排列组成的，前者称为确定性纹理， 后者称为随机性纹理。对确定性纹理，我们可以用结构方法进行分析，而对随机 性纹理，我们一般采用统计方法或谱方法。在自然纹理图像中，纹理基元的分布 主要是随机分布的，对这类纹理特征的描述我们使用纹理的统计特征。 纹理是图像中一个重要而难于描述的特性。习惯上，人们把图像中局部不规 则、但整体上有规律的特性称之为纹理。以纹理特性为主导特性的图像称为纹理 图像。生活中得到的很多图像都是纹理图像，例如，用各种观测系统取得的图像 l 第一章绪论 很多是纹理型的；卫星或飞机从地球表面取得的遥感图像是对地面的宏观考察， 其图像大部分呈纹理型；在海洋波浪方面波浪的波长越长，图像的纹理越租。由 于波长与浪高有密切关系，浪高也可以从纹理图像信息中获得。观察图1 1 的图 像可以看出，这些图像在局部呈现不规则性，而在整体上又呈现某种规律性。 图1 1 纹理图像 根据纹理特征分布的方式不同，可以把纹理分为三类：结构性纹理、随机性 纹理以及既有结构性又有随机性的纹理。如图1 2 所示。结构性纹理中存在纹理 基元( 保持纹理局部特性的最小纹理块) ，整个纹理可以由一系列的纹理基元及其 摆放规则决定( 例如砖墙、地板) ；随机性纹理中找不到明确的纹理单元( 例如沙粒、 裂痕、花岗岩) f 但更多的从现实世界得到的纹理同时包含了以上两种特性( 例 如织物、犁过的田地) 图1 2 中，( a ) 、( b ) 、( c ) 分别为结构纹理、随 机纹理、两者都有的纹理。 ( a ) 1 1 。2 纹理和图像的区别洲 ( b )( c ) 图1 2 纹理的种类 2 第一章绪论 纹理和图像是不同的，纹理显然是图像，但并不是所有的图像都是纹理。我 们可以把纹理看作是具有局部性和稳定性的随机过程的实现。也就是说，纹理中 的每一个像素点都可以由其空间邻域内的像素的集合来表达，并且这种表达对每 个像素都是一样的。如图1 3 所示，假设给定一张图像，但只允许观察者通过较 小的可移动窗口( 图1 3 中黑框) 来观察它，当移动窗口时观察者可以看到图像的 不同部分。所谓图像的稳定性是指：在观察窗口大小合适的前提下，观察者看到 的部分总是相似的；所谓图像的局部性是指：窗口中的任一像素可以由其周围邻 域内的像素预测得到，而与图像中的剩余部分无关。具备了局部性和稳定性的图 像即为纹理。 ( a )( b ) 图1 3 图像和纹理的比较 1 1 3 什么是纹理综合叫田 纹理综合问题描述：给定一幅小的输入纹理作为样本，通过一定的方法生成 一幅指定大小的纹理且能使人感觉输出纹理和输入纹理在视觉上没有多大区别， 或者说两幅纹理的视觉效果相同。 计算机图形学上常常用纹理来修复图像。纹理大多是通过手画或扫描得到 的，采用手画得到图像不大现实，尤其是对尺寸要求比较严格的时候。的而扫描 图像一般尺寸较小，想得到较大尺寸的图像，如果直接复制拼凑在一起，会产生 很明显的边沿效应。 纹理综合则可以很好实现这个愿望。给定已知纹理，采用合适的纹理综合方 法，生成较大的或者任意打的纹理图像，而且产生的纹理图像与纹理样本在视觉 上相似。如图1 4 所示。其中( a ) 为样本纹理，( b ) 为得到的综合纹理，其目 的是通过纹理综合产生一个和样本纹理相似的新纹理。 3 第一章绪论 ( a ) 图1 4 纹理综合模型 ( b ) 纹理综合在图像处理和计算机图形学等许多领域具有重要意义。例如，如果 图像中的某些区域被污染了或者丢失了，可以采用人工纹理去替代这些数据。在 图形编码方面，可以将那些少了重要细节的纹理区域检测出来，用人工纹理去替 代原来的区域，人工纹理的编码要比直接图像编码有效的多，m p e g 一4 视频编 码中的网格编码就可以应用上述方法。同时，纹理综合也具有重要的实用价值， 如在纺织印染等行业，可以通过纹理综合来生成模拟自然的图像；在国防工业中， 通过模拟自然纹理来制造各种迷彩服。 1 2 国内外研究现状及分析刀n 们 2 0 世纪7 0 年代，人们便开始研究纹理综合，尤其近几年来，在该领域的研 究中取得了丰硕的成果。研究纹理综合首先要建立描述图像纹理的模型，描述纹 理的模型粗略的可分为三类： 第一类是压缩模型，使用固定参数来描述各种纹理，h e e g e r 和b e r g e n ( 1 9 9 5 年) 应用色度直方图作为描述纹理的参数，p o r t i l l a 和s i m o n c d l i ( 2 0 0 0 年) 提出 这样一个模型，该模型包括各种小波特征及它们的关系。参数模型在综合较大尺 寸纹理时不如其他模型，因为尺寸增大相应计算量成倍增大，但是它非常适合纹 理分析，而且使人们能够很好的理解纹理的感知过程。 。 第二类时非参数模型，这就意味着不需要固定数量的参数，而是收集大量的 样本来模拟纹理。b o n e t 是该领域的先驱，他于1 9 9 7 年通过收集多级滤波器的 响应作为样本，来生成纹理。e t i o s 和l e n n g 于1 9 9 9 年首次采用了一个更简单的 方法，直接从输入纹理拷贝像素来生成新的纹理。w e i 和l e v o y 于2 0 0 0 年把e f r o s 和l e u n g 的方法延伸应用到频域。这些技术的一个显著特点是，纹理综合时，每 次生成一个像素。 4 第一章绪论 第三类是在第二类的基础之上，形成的一个非参数模型，该模型是通过从输 入纹理拷贝到整片区域( 而不是像素) 来生成新的纹理。a s h i k h m i n 于2 0 0 1 年 对该模型的形成做了开创性的工作，他使用一个基于像素的技术，来拷贝若干片 生成新纹理，该技术支持在输入纹理中连贯的部分相互转移。2 0 0 1 年，l i a n g l i u 和x u g u o 以及e f i o s 和f r e e m a n 都使用拷贝整片的技术生成了新纹理图像。 p r a u n , f i n k e l s t e i n 和h o p p e ( 2 0 0 0 年) 也采用相似的技术，对一个3 d 模型进行 了纹理覆盖。可以证明第三类模型在综合大尺寸纹理时是最理想的。近几年来我 国的一些学者对纹理综合领域的研究也做了不少工作。但与国外相比，无论研究 的广度还是投入的研究人员都还有一定的差距。 1 3 本文的研制任务及结构 本文主要是基于分形和m a r k o v 因果邻域系统的纹理综合方法研究，主要采 用m a f l a b 进行编程来实现纹理综合算法。 本文的大致结构如下： 第一章绪论，主要介绍了纹理综合的研究发展现状； 第二章分形理论基础，对纹理综合的基础一一分形理论进行了简单介绍； 第三章纹理综合方法综述，主要对纹理综合的方法进行了概括； 第四章基于分形的纹理综合方法； 第五章基于m a r k o v 因果邻域纹理综合方法； 第六章结束语。 5 第二章分形理论基础 第二章分形理论基础 分形理论是现代非线性科学研究中十分活跃的一个数学分支，也是纹理综合 方法的基础。本章旨在介绍分形的基本理论和基本方法，为我们在后续章节的应 用作准备。本章第一节引出分形理论及其发展进程；第二节介绍分数维；第三节 介绍分形布朗运动。这些均为纹理综合的算法基础。 2 1 分形理论及其发展进程嘲 分形理论是当今世界十分风靡和活跃的新理论、新学科。分形的概念是美籍 数学家曼德布罗特( b b m a n d e l b o r t ) 首先提出的。1 9 6 7 年他在美国权威的科学 杂志上发表了题为英国的海岸线有多长? 的著名论文。海岸线作为曲线，其特 征是极不规则、极不光滑的，呈现极其蜿蜒复杂的变化。我们不能从形状和结构 上区分这部分海岸与那部分海岸有什么本质的不同，这种几乎同样程度的不规则 性和复杂性，说明海岸线在形貌上是自相似的，也就是局部形态和整体形态的相 似。在没有建筑物或其他东西作为参照物时，在空中拍摄的1 0 0 公里长的海岸线 与放大了的l o 公里长海岸线的两张照片，看上去会十分相似。事实上，具有自 相似性的形态广泛存在于自然界中，如：连绵的山川、飘浮的云朵、岩石的断裂 口、布朗粒子运动的轨迹、树冠、花菜、大脑皮层曼德布罗特把这些部分与 整体以某种方式相似的形体称为分形( f r a e t a i ) 。1 9 7 5 年，他创立了分形几何学 ( f r a c t a lg e o m e t r y ) 。在此基础上，形成了研究分形性质及其应用的科学，称为分形 理论( f r a e t a lt h e o r y ) 。 自相似原则和迭代生成原则是分形理论的重要原则。它表征分形在通常的几 何变换下具有不变性，即标度无关性。由自相似性是从不同尺度的对称出发，也 就意味着递归。分形形体中的自相似性可以是完全相同，也可以是统计意义上的 相似。标准的自相似分形是数学上的抽象，迭代生成无限精细的结构，如科契 ( k o c h ) 雪花曲线、谢尔宾斯基( s i e r p i n s h ) 地毯曲线等。这种有规分形只是少数， 绝大部分分形是统计意义上的无规分形。 分形理论既是非线性科学的前沿和重要分支，又是一门新兴的横断学科。作 为一种方法论和认识论，其启示是多方面的：一是分形整体与局部形态的相似， 启发人们通过认识部分来认识整体，从有限中认识无限；二是分形揭示了介于整 6 第二章分形理论基础 体与部分、有序与无序、复杂与简单之间的新形态、新秩序；三是分形从一个特 定层面揭示了世界普遍联系和统一的图景。 分形理论在物理、地质、材料科学以及工程技术中都有广泛的应用。特别是 随着计算机的迅速发展和广泛应用，分形的思想和方法在信号处理、模式识别、 自然图像的模拟以及艺术的制作等领域都取得了极大的成功。分形理论的研究对 象是自然界和非线性系统中出现的不光滑和不规则的几何形体，分形应用中的数 学基础是分形几何学。 2 2 分数维 分数维，作为分形的定量表征和基本参数，是分形理论的又一重要原则。长 期以来人们习惯于将点定义为零维，直线为一维，平面为二维，空间为三维，爱 因斯坦在相对论中引入时间维，就形成四维时空。对某一问题给予多方面的考虑， 可建立高维空间，但都是整数维。在数学上，把欧氏空间的几何对象连续地拉伸、 压缩、扭曲，维数也不变，这就是拓扑维数。然而，这种传统的维数观点受到了 挑战。曼德布罗特曾描述过一个绳球的维数：从很远的距离观察这个绳球，可看 作一点( 零维) ；从较近的距离观察，它充满了一个球形空间( 三维) ；再近一些， 就看到了绳子( 一维) ；再向微观深入，绳子又变成了三维的柱，三维的柱又可分 解成一维的纤维。那么，介于这些观察点之间的中间状态又如何呢? 显然，并没有绳球从三维对象变成一维对象的确切界限。数学家豪斯道夫 ( h a u s d o f 0 在1 9 1 9 年提出了连续空间的概念，也就是空间维数是可以连续变化 的，它可以是整数也可以是分数，称为豪斯道夫维数。记作d f , 一般的表达式 为：k = l d f , 也作k 可1 l ) - d f , 取对数并整理得d f = - h u l n l ，其中l 为某客体沿 其每个独立方向皆扩大的倍数，k 为得到的新客体是原客体的倍数。显然，d f 在一般情况下是一个分数。因此，曼德布罗特也把分形定义为豪斯道夫维数大于 或等于拓扑维数的集合。英国的海岸线为什么测不准? 因为欧氏一维测度与海岸 线的维数不一致。根据曼德布罗特的计算，英国海岸线的维数为1 2 6 。有了分数 维，海岸线的长度就确定了。 b b - l a n d e l b o r t 认为维数更易于描述集合的不规则度或破碎度，因此，他 定义了一种观点，即：若一个集合的h a u s d o r f f 维数严格大于它的拓扑维数，那 么该集合就称为分形集。h a u s d o r f f 维就是一种分数维，它是分形可以广泛应用 于各学科领域的出发点。 数学上的维数并不是一个很简单的、易于理解的东西，c a r a t h e o d o r y1 9 1 4 年 提出了用集的覆盖来定义测度的思想，h a u s d o r f f1 9 1 9 年用这种方法定义了以他 7 第二章分形理论基础 名字命名的测度和维数。以此为基础，至今数学家已经发展出了十多种不同的维 数，拓扑维、h a u s d o r f f 维、自相似维、盒子维、容量维、信息维、相关维、l y a p u n o v 维等等。这里主要讨论常用的h a u s d o r f f 维数及测度。 在h a u s c l o r f f 测度及维数优点是它对任意集都是适用的，且由于它是以测度 为基础，在数学上是方便的，也比较容易处理。其主要不足是在很多情形下用难 以计算。然而对于理解分形的数学理论，熟悉h a u s d o r f f 测度及维数是最基本的。 首先我们来了解一下什么是覆盖。若u 是n 维欧氏空间r n 的任意非空子集； u 的直径定义为i u - f - s u p o x - y l , 】【，y u ，即u 内任意两点的距离的最大值，式中 的s u p 是上确界的缩写。若 u 是直径至多为6 的且覆盖f 的一个可数( 或有限) 集族，即f c uu i 且对每个i ，o | u i l o ，我 们定义： i 弼口) = = i n f l qi ： u i ) 是f 的一个6 覆盖，k 是 u i ) 的元素总个数， 式中i n f 是下确界的缩写( 取下确界的就自动保证了在覆盖上是没有浪费 的) 。此时式中的6 是一个定值。于是考虑所不超过6 的f 的覆盖，并试图使这 些直径的s 次幂的和达到最小。当6 减少时，能覆盖f 的集类的个数是减少的， 而下确界研的数值是增加的。当6 一。时，下确界弼口) 趋于一个极限记 为： 砰盱熙联( 刃 ( 2 - 1 ) 对r n 中任何子集f ，这个极限都存在，但极限的值可能是o 或一。i - p 口) 被 称为f 的s 维h a u s d o r f f ：i 煲d 度。 h a u s d o r f f 测度的数学定义是严密的，作为基础性的了解，我们只要简单地 认为：h a u s d o r f f 测度是与1 维的长度、2 维的面积和3 维的体积相等同意义的对 任意s 维都适用的一种度量，是长度、面积和体积等概念的推广。说得再通俗一 点：l 维的大小用长度来度量，2 维的用面积来度量，3 维的用体积来度量，那 么s 维的大小用什么来度量呢，就是h a u s d o r f f 测度。 h a u s d o r f f 测度的一个重要性赛一比例性质：长度、面积和体积的比例性 质是我们熟悉的。当比例放大九倍时，曲线的长度放大九倍，平面区域的面积放 大九2 倍。三维物体的体积放大妒倍。正如可以预料到的，s 维h a u s d o r f f 测度扩 大r 倍，见图2 1 。于是我们很容易理解下面的比例性质成立： i - p 产” r ( f ) ( 2 - 2 ) 这个比例性质是分形理论的基础，也是分形理论的最重要性质之一。 8 第二章分形理论基础 甜一例 一。益崖x i 。7 、 i l h r x 斧 子冀 - ， 图2 1 不同h a u s d o r f f 维的放大倍数 上面我们讲的都是抽象的，下面我们来看一个实例：求k o c h 曲线的1 维 h m s d o 攒测度和2 维h 眦s d o r 疗测度。首先来看几种可能的覆盖及相应的磁0 f ) 。 取6 ：1 3 时，见图2 2 ： 图2 2 ( a ) ，有 ， 月；( k o c h ) - - i n f iv ! i u i ) 是f 的一个6 覆l l , k 是 u i ) 的元素总个数 t = l = a l + a 2 + a 3 + + a s( 2 - 3 ) 其中，a l ，a 2 ，a 3 ，a 8 分别表示覆盖该图的八个圆的直径。 图2 2 ( b ) ，有 i 弼( k o c h ) - - - i n f iv , l ： u i ) 是f 的一个6 覆盖，k 是 u i ) 的元素总个数 m - - b l + b 2 + b 3 + ”+ b 8( 2 - 4 ) 其中，b l ，b 2 ，b 3 ，b 8 分别表示覆盖该图的八个圆的直径。 图2 2 ( c ) ，有 i 叼( k o c h ) - - i n f iv , | 1 u i 是f 的一个6 覆盖，k 是 u i ) 的元素总个数， t - i - - - d l + d 2 + d 3 + d 4( 2 5 ) 其中，d 1 ，d 2 ，d 3 ，“分别表示覆盖该图的4 个圆的直径 回融哦馥黔 ( a )( b ) 图2 2 直径不超过l ，3 的三种可能覆盖 9 ( c ) 毫t q 寸 很显然，当6 减少时，能覆盏k o c h 的集类的个数是减少的，所以下确界层( f ) 的数值是增加的。现在我们就来考虑但当8 一o 情况。这里为了简便起见我们只 考虑最特殊的一种覆盖，即所有u i 的直径都相等的情况。 在图2 2 ( c ) 中，取6 = i 3 ，让d l 鼍i 2 = d 3 = d 4 = l 3 ，则 巩3 ( k o c h ) = l 3 + 1 1 3 + i b + l 3 = 4 3 取8 = 1 9 ，用直径都为6 的u i 去覆盖k o c h 贝| 有 巩，( k o c h ) = l 9 * 1 6 = ( 4 3 ) 2 取& = 1 2 7 ，用直径都为6 的u i 去覆盖k o c h 则有 冀：m ( k o c h ) = l 2 7 6 4 = ( 4 3 ) 3 取6 = i 3 “，用直径都为6 的u i 去覆盖k o c h 则有 叫，( k o c h ) = 1 3 4 k ( 4 3 ) “ 当n 时，6 一。此时的焉0 c o c h ) 就为k o c h 曲线的l 维h a u s d o r f f度 即 h 1o 沁驴烛碗r ( k o c h ) 2 熙固”铷 ( 2 - 6 ) 这个结论和我们进行的直观分析是一样的。下面我们来分析一下k o c h 曲线 的2 维h a s d o 面测度。首先我们来了解一下k o c h 曲线的另一种表示方法，其 生成过程如图2 3 所示。 图2 3k o c h 曲线的另一种生成方法 当迭代无穷多次之后，生成的图形就是k o c h 曲线。用上述同样的方法不难 推出： h 2 ( k o c h ) = 烛- 2 r ( k o c h ) = 舰争卸( 2 - 7 ) 这个结论也和我们进行的直观分析是样的。分析到此，我们知道k o c h 曲 线的维数比i 大比2 小。实际上任何维数s ，只要比k o c h 曲线的维数小，那么 1 0 一一一一 第二章分形理论基础 在该维数s 下的h a u s d o r f f 测度就为o o ；比k o c h 曲线的维数大，则在该维数s 下 的h a u s d o r f f 测度就为0 。让s 值从0 开始慢慢变大，日；( k o c h ) 的值起初一段一 直保持o o ，当s 为某个值d h 时h a u s d o r f f 测度的由o d 突然变为一个非零实数，此 时的s 值就称为k o c h 曲线的h a u s d o r f f 维数。当继续增大时h a u s d o r f f 测度又突 然变为0 并一直保持为0 。用数学语言对任何的集合的h a u s d o r f f 维数表述如下： 对任意一个集合f ，当s 从0 逐渐增大时，存在s 的临界值，使得i - l g ) 由o o 突然变为o ( 见图2 4 ) ，则称这个临界值为集合f 的h a u s d o r f f 维数，常用d h 或 d h ( f ) 表示，即： 珥 产 当铲d h 时，有 o 磁口) 0 0 c o ( s 如曲 0 ( p d h ) ( 2 8 ) ( 2 9 ) 图2 4h 孤s d o r 仃维数曲是使乓a f ) 从m 跳跃到0 发生的s 的数值 上述的定义只是数学意义上的，难以用它来求具体的i - i a u s d o r f f 维数。为了 测量的方便，大部分维数的定义基于“用尺度6 进行量度”这样的设想，都用这 样的方法进行测量：忽略尺寸小于6 时的不规则性，并且察看当6 - - - 0 时。这些 测量值的变化。所以，也可以用类似的方式来描h a u s d o r f f 维数。 最后在来看一个例子：计算k o c h 曲线的h a u s d o f f 维数。 启发计算式：把k o c h 曲线( 见图2 2 ) 划分为4 个全等的部分，从左到右 分别记为：k o c h l ，k o c h 2 ，k o c h 3 和k o c h 4 。k o c h l = k o c h n k o c h 的 o ，1 3 ) 部分 ， k o c h 2 = k o c h n k o c h 的 1 3 ，1 2 ) 部分) ，k o c b 3 = k o c h n k o c h 的 1 2 ，2 3 ) 部分， k o c h 4 = k o c h n k o c h 的 2 3 ，l 】部分 ，我们很容易得到： 盯( k o c h ) = m s ( k o c h l 卜i - p ( k o c h 2 ) + 砰( k o c h 3 hi - p ( k o c h 4 ) ( 2 1 0 ) 第二章分形理论基础 因为k o e h l = k o e l o = k o c h 3 = k o e h 4 = k o e h 3 砰( k o c h ) = i - g ( k o c h 3 ) + i - g ( k o c h 3 ) + 盯( k o c h 3 ) + i - i ( k o c h 3 ) = 4 i - i (koch3)(2-1 1 ) i - i a u s d o r f f $ 4 度的比例性质有 r i ( k o c h ) = 4 + ( i 3 ) 。l - g ( k o c h ) ( 2 1 2 ) 两边同时除以i - 1 ( k o c h ) 得 1 - - 4 + ( 1 3 y 解得s f l n 4 l n 3 ，与用相似维数一致。 虽然h a u s d o r f f 维数的定义是极其严密的而且适用于任何集合，但是要从不 规则的图形中得到启发来计算i - i a u s d o r f f 维数相当困难，而且有些情况使用6 0 是不适合的，例如，在物理学上当6 一o 时，一都要受到h e i s e n b e r g 不确定性原 理的拒绝，即使不是这样，要进行实验测定也是是相当困难的。在实际应用中， 人们还提出了不少实用的分形维数，如盒维数、关联维数和链维数等。这里我们 就不一一介绍了。 2 3 分形布朗运动( f b m ) 为了更好的理解分形布朗运动，首先需要对布朗运动的定义加以介绍。 2 3 1 布朗运动 布朗运动指的是一种无相关性的随机行走，满足统计自相似性，即具有随机 分形的特征，但其时间函数( 运动轨迹) 却是自仿射的。具有以下主要特性：粒子 的运动由平移及其转移所构成，显得非常没规则而且其轨迹几乎是处处没有切 线；粒子之移动显然互不相关，甚至于当粒子互相接近至比其直径小的距离时也 是如此；粒子越小或液体粘性越低或温度越高时，粒子的运动越活泼；粒子的成 分及密度对其运动没有影响；粒子的运动永不停止。 1 9 2 3 年，德国数学家n w i e n e r 建立了布朗运动的数学模型，后来的研究大 都是基于维纳的这一模型。从一个平面来看，布朗运动构成了最简单的随机分形。 在一维情况下，如果一个随即过程b ( t ) 满足下面两个性质，该过程即为布朗运动。 ( 1 ) 增量b ( t 2 ) - b ( t 0 服从高斯分布； ( 2 ) 均方增量正比于时间的变化，即： e i b ( t 2 ) 一b ( t 0 1 2 o cl t 2 一t l i “其中h - l 2 ( 2 1 3 ) 2 3 2 分形布朗运动 1 2 第二章分形理论基础 分形布朗运动f b m ( f r a c t a lb r o w nm o t i o n ) 是1 9 6 8 年m a n d e l b r o t 和n e s s 提出的一种数学模型，它主要用于描述自然界的山脉、云层、地形地貌以及模拟 星球表面等不规则形状。我们这里主要用来模拟各种具有分形特征的噪声等，现 在已经成为一个能反映自然物体特性的数学模型。我们这里主要介绍一维分形布 朗运动。 上式e b ( t 2 ) - b ( t i ) 1 2 o c i t 2 - t t i “中，如果考虑一般情况，即o h i 时，就称 之为分形布朗运动。 实际上，我们所说的分形布朗运动是一种随机分形，而b 0 ) 的图形只是某一 次的取样图形，但是对一定的h ，b ( t ) 的所有取值都具有相同的分数维。 d - - - - 2 - - h，(2-14) 参数h ( o q i i 2 ， 这些增量有正的相关值；相反的，对于h l 2 ，增量间存在一个负相关，有较大 的分数维。如图2 5 所示。 图2 5 各种h 值对应的分形布朗运动 分形理论是研究非线性问题的一门新学科，内容广泛而复杂，我们在此只是 针对我们后面的应用作一下简单介绍。 1 3 第三章纹理综合方法模型综述 第三章纹理综合方法模型综述 计算机自然纹理模拟与生成是图像处理、计算机图形学等研究的重要领域之 一，具有很高的应用价值。根据不同物体的几何结构和灰度上的差别，人们发展 了多种纹理综合方法。这些方法可以粗略地归结为两种纹理模型，即纹理的结构 模型和纹理的统计模型。结构模型通常采用树或图等形状文法描述织物、砖墙等 较规则的人为纹理结构，但用结构模型综合自然纹理则效果不佳。统计模型根据 纹理图像的灰度在空间的分布规律综合纹理，取得了一些成功，但仍然存在很多 问题。例如，应用较多的m a r k o v 随机场模型，用有参模型模拟自然纹理的效果 不佳，而用无参模型模拟自然纹理则计算量太大，难以满足实际应用的需要。研 发一种有效而实用的纹理综合方法是值得深入研究的。 为了定量描述纹理，需要研究纹理本身可能具有的特征。从人的感知经验可 知，粗糙性和方向性是人们区分纹理时所用的两个最主要特征。多年来研究者们 建立了许多纹理算法以测量纹理特性，这些方法大体可分为两大类：统计分析方 法和结构分析方法。前者从图像有关属性的统计分析出发；后者则着力找出纹理 基元，以后再从结构组成上探索纹理的规律，也有直接去探求纹理构成的结构规 律。无论从历史发展还是从当前进展来看，统计的方法仍然占主导地位。在统计 方法中：有最简单的研究纹理区域中的统计特性；有研究像元邻域内的灰度或属 性的一阶统计特性；有研究一对像元或多像元及其邻域灰度或属性的二阶或高阶 统计特性；有研究用模型来述纹理，如m a r k o v 模型，f r a c t a l 模型，有研究基于 滤波器的纹理分析与综合，如基于小波理论、子带分解算法等。 3 1 纹理的结构模型删呻1 晦刀 结构模型采用树或图等形状文法来描述藤制品、砖墙等较规则的人为纹理结 构，也可以用来模拟自然纹理。例如，先形成一些基本的原始图形，然后按位置 编排规则在空间里重复这些图形。基本图形可以是从自然纹理区中提取的一小部 分，或者由更小的原始元素如点和线段来构成。原始图形的位置编排可以是确定 的，也可以是随机性的，或者根据某种混合的策略加以编排。这种方法的一个主 要缺点是原始图形在空间位置交接的部分存在边界效应，必须进行平滑处理。 纹理的结构模型是基于纹理基元的重复性分布规则，因此在结构模型中，不 仅要确定提取基本的纹理基元，还要研究存在于纹理基元之间的重复结构关系。 1 4 第三章纹理综合方法模型综述 纹理基元可能是明确的、直观的，也可能是不明确的需要人为根据情况设定的。 无论怎样确定纹理基元，都需要通过图像的区域分割或边缘、线的抽取来提取纹 理基元。对于存在于纹理基元之间的结构关系，可以有不同的分析途径。简单的 方法是分析纹理基元之间存在的相位、距离、尺寸等统计特性，也可以考虑用复 杂的方法，例如用模型，句法等。具体的方法选择依赖于纹理综合的要求。 为了简单起见，我们假定景物中的表面，现在来研究这个平面上的纹理，看 看如何由图像上的纹理梯度来确定这个平面的方向，下面简要介绍一种树状结 构。 纹理结构的树状分析方法是把纹理定义为结构基元按某种规则重复分布规 则所构成的模式。为了分析纹理结构，首先要描述结构基元的分析原则，通常从 输入图像中提取结构基元，并描述其特性和分布规则。用树方法描述纹理图像是 可按如下步骤： ( 1 ) 把图像分割成固定大小的若干窗口，窗口内的纹理基元可以是一个像 素，也可以是4 个或9 个灰度比较一致的像素集合。 ( 2 ) 把窗口内的纹理基元用某种树结构表示。纹理的表达可以是多层次的。 如图所示，它可以从像素或小块纹理一层一层向上合并，这样就组成一个多层的 树状结构。图给出了图像基元的一种标记方法。 囊覆 l 手 ； i 基元 图3 1 纹理的树状描述 纹理的树状结构可由多种方法。如将树根安排在中间，树枝向两边伸出，每 个树枝有一定的长度。当窗口中像点数为奇数时用这种排列比较方便，此时，每 个分枝长度相同。另一种方法可将树根安排一侧，分枝都向另一侧伸展。这种排 列对奇数像点和偶数像点都适用。 识别树状结构可以用树状自动机，对每一个纹理文法建立一个“结构保存的 误差修正树状自动机”。该自动机不仅可以接收每个纹理图像中的树，而且能用 最小距离判据、辨识类似的含有噪声的树，并对每一个分隔成窗口的输入图像进 1 5 第三章纹理综合方法模型综述 行分类。 纹理中某个局部的纹理结构是与该局部邻域的灰度变化规律密切相关的，纹 理特征的度量必然依赖于以这一邻域组成的子图像窗1 ：3 。因此，在图像纹理分析 综合模型中，窗1 ：3 的选取方式是至关重要的。如果纹理结构不同，整体性质也就 有区别，如不同的粗糙度，边缘和像素灰度直方图的局部特性有明显的差异，子 图像可以适当的缩小。反之亦然。 3 2 纹理的统计模型 纹理的结构模型是基于纹理基元的重复性原则，适合于研究比较规则的人工 纹理。对于不太规则的纹理，就要考虑统计模型了。统计模型是跟据纹理图像灰 度在空间上按一定的分布变化而生成的机理，采用一些统计参量来表征和定义纹 理，进而生成具有相同统计特征的纹理。例如，通过产生二维相关随机场来生成 纹理。j u l e s z 发现人的视觉不能鉴别具有相同二阶统计特性的纹理场。因此如果 某种纹理测度是足够的，那么它应该有可能产生一种二维的二阶过程与自然纹理 相匹配，只要人工和自然的纹理区具有类似的纹理测度值。尽管近期的研究表明， 这一理论并不完善，但是这一方法还是可行的。基于统计模型的纹理综合方法很 多，如基于m a x k o v 随机场的纹理综合方法，基于子带分解和直方图匹配的纹理 综合方法等，下面介绍几种常用的统计模型。 3 2 1 基于分形和分数维的模型盯嘲 自然界存在许多规则的形体，它们可以用欧氏几何分析处理。这些几何对象 具有整数维数，零维点、一维线、二维面、三维体等都是人们熟知的例子。然而 自然界存在更多的是不规则形体，这就要考虑分数维的概念了。m a n d e l b r o t 经过 多年研究提出了分形几何学( f r a c t a lg e o m e t r y ) ，用来描述自然界中不规则的、具 有自相似特性的物体，这类物体称为分形( f r a c t a l )