图像分析及识别_课件_7

1、123如果没有物体识别的帮助，即使是最简单的机器视觉问题也无法解决。模式识别被用于区域和物体的分类，为了学习更复杂的机器视觉操作，有必要先了解一些基本的模式识别方法。 4物体或区域分类已经被提到过多次，识别是自底向上图像处理方法的最后步骤，此外它也经常被用于图像理解的其它控制策略。当需要得到有关一个物体或区域的信息时，几乎总是要用上某种模式识别方法。5没有先验知识是无法进行识别的。对于被分类物体到底属于哪一个类别或群体的判断根据的是那些对物体分类提供了必要信息的关于物体及类别的知识。既需要关于待处理物体的特殊信息，同时也需要关于物体类别的高层次的一般知识。 6首先，我们将介绍常用的知识表示方法

2、。在计算机上用适当的形式表达知识并不是一个简单明了的概念。78人工智能研究有关知识和知识表示的问题，计算机视觉则利用这些研究的结果。在较高层次的处理中通常要用到人工智能的方法。为了完全掌握计算机视觉和图像理解，有必要对人工智能有所了解。 9已有的经验表明，一个好的知识表示设计是解决理解问题的关键所在。并且，对一个人工智能系统来说，如果假定已经有了复杂的知识基础，则通常只需要几个相对简单的控制策略就能够实现很复杂的行为。10换句话说，要表现出智能的行为并不需要非常复杂的控制策略，而是需要一个庞大的先验数据和假设集合，并且这些先验知识具有良好的结构化表示。其它一些需要规范使用的术语还有语法和语义。

3、11q一个表示的语法是指可能用到的符号和这些符号的合法排列方式。q一个表示的语义是指语法允许的符号和符号排列所表达的含义。q一个表示则是一个可以描述事物的语法和语义的集合。12人工智能中的主要知识表示技术有形式语法和语言、谓词逻辑、产生式规则、语义网络和框架。知识表示数据结构大都是常规数据结构的扩展，如链表、树、图、表、分级（分层）、集合、环、网、矩阵等。13描述和特征不能被看作是纯粹的知识表示。但是，它们作为复杂表示结构的一部分，可以用来描述知识。 描述通常可以表示物体的某些标量特性，称为特征。14一般来说，仅仅一个描述不足以表示物体，因此可以联合几个描述形成特征向量。数值特征向量是统计模式

4、识别的输入。15例如，大小特征可以用来表示面积特性，紧致度特征表示圆形度。如果假定已知关于大小和圆形度的信息，则采用特征向量x=(size, compactness)可以将物体分为如下几类：小、大、圆形、非圆形、小圆形、小非圆形等等。 16 当描述一个物体的结构时，特征描述不再适用。一个结构化描述由现有基元和这些基元之间的关系生成。 基元由它们的类型信息表示。最简单的结构化表示形式有链、树和广义图。 17一个物体可以用由符号构成的链、树或图等来描述。然而，整个物体类别却不能仅仅用一个简单的链、树等描述。如果一个类别中的物体都已经被结构化描述了，则这个类可以用语法和语言来表示。语法和语言提供了如

5、何由一个符号（基元）集合构造链、树或图的规则。 18谓词逻辑在知识表示中有着非常重要的作用它为从旧知识中通过演绎得到新知识提供了一种数学形式。谓词逻辑的处理对象是逻辑变量、量词和逻辑运算符的组合。逻辑变量都是二值的。证明思想和推论规则，如假言法则和归结法构成了谓词逻辑的主体。 19产生式规则代表了诸多基于条件行动对的知识表示。一个基于产生式规则的系统所表现出的行为，从本质上可以描述为如下模型： if 条件X 成立 then 采取行动 Y。何时采取怎样的行动的信息代表了知识。20 为了弥补数值或精确知识表示的明显局限性，可以采用模糊逻辑。模糊规则有如下形式： if X 是 A then Y 是

6、BX和Y代表某种性质，A和B为语言变量。if圆形度很高then物体有很大可能性是球。21 语义网络是关系数据结构的一个特殊变种。语义网络由物体、物体的描述及它们之间的关系（通常是邻近物体之间的关系）组成。22知识的逻辑形式可以被包含在语义网络内，谓词逻辑可以用来表示或估计局部信息和局部知识。语义网络采用的数据结构是赋值图，节点表示物体，弧表示物体间的关系。下面关于人脸的定义就是语义网络的一个简单例子。 2324 框架提供了一种非常通用的知识表示方法。这种方法可以包含迄今为止所介绍的所有知识表示法则。有时也被称为脚本。框架适合表示特殊环境下的普通知识。 25框架可以用来代替缺失的信息，这些信息可

7、能在视觉问题中至关重要。 从形式化的观点来看，框架以一个广义语义网络加上一个相关变量、慨念和情景串联的列表来表示。并不存在框架的标准形式。26框架代表一种利用基本类型的物体组织知识，利用特定场合的典型行为描述物体间相互关系的工具。框架被看作是一种高层次知识表示。2728一个物体是一个物理单位，在图像分析和计算机视觉中通常表示为分割后图像中的一个区域。整个物体集合可以被分为几个互不相交的子集合，子集合从分类的角度来看具有某种共同特性，被称为类。29物体识别从根本上说就是为物体标明类别，而用来进行物体识别的工具叫做分类器。类别的数目通常是事先已知的，一般可以根据具体问题而定。但是，也有可以处理类别

8、数目不定情况的方法。 30分类器（与人类相似）并不是根据物体本身来做出判断的而是根据物体被感知到的某些性质。这些被感知到的物体特性称做模式。分类器实际识别的不是物体，而是物体的模式。物体识别同模式识别被认为是同一个意思。31 构建形式描述模式分类器分类物体32q步骤“构造形式化描述”基于设计者的经验和直觉。q选择一个基本性质集合，用来描述物体的某些特征，这些性质以适当的方式衡量，并构成物体的描述模式。这些性质可以是定量的，也可以是定性的，形式也可能不同。33模式识别理论研究如何针对特定的（选择的）基本物体描述集合设计分类器。统计物体描述采用基本数值表述，这称为特征，x1, x2,xn。 特征来

9、自于物体描述。 34描述一个物体的模式（也称做模式向量，或特征向量）是一个基本描述的向量。所有可能出现的模式的集合即为模式空间X，也称为特征空间。 35如果基本描述选择得合适的话，类内物体间的相似性会使得物体模式在模式空间中也相邻。在特征空间中各类会构成不同的聚集，这些聚集可以用分类曲线（或高维特征空间中的超曲面）分开。36 37若存在一个分类超曲面可以将特征空间分为若干区域，并且每个区域内只包含同一类物体，则这个问题被称为是具有可分类别的。若分类超曲面是一个平面的话，则称为是线性可分的。若问题具有可分类别，则每个模式只能表示一类物体。38直观地，我们希望可分类别能够被准确无误地识别。然而大多

10、数物体识别问题并不具有可分类别，这种情况下在特征空间中不存在一个分类超曲面可以将各类无误地分开，肯定会有某些物体被错分。 39统计分类器是一个具有n个输入端和1个输出端的装置。每个输入端接收从待分类物体测量得到的n个特征x1, x2, , xn中的一个。40一个R-类分类器的输出为R个符号1, 2, , R中的一个，用户将这个输出符号视为对待分类物体的类别判断。输出符号r就是类别标识符。41函数d(x)=r描述了分类器输入与输出之间的关系，称为决策规则。决策规则将特征空间分成R个不相交的子集Kr，r=1,R，每个子集包含所有满足d(x)= r 的物体特征表示向量x。42子集Kr，r=1,R间的

11、边界构成了前面提到的分类超曲面。设计分类器的目的就是要确定分类超曲面（或定义决策规则）。 43分类超曲面可以由R个标量函数g1(x), g2(x), , gR(x)定义，这些函数被称为判别函数。物体模式x将被识别为判别函数具有最大输出值的类别： )(max)()(,.,1xgxgxdsRsrr44线性判别函数是最简单的判别函数，但应用十分普遍。其一般形式为：其中r=l,R。若分类器的所有判别函数都是线性的，则称此分类器为线性分类器。 nrnrrrxqxqqxg110)(45另一种方法基于最小距离准则构造分类器。假设特征空间中定义了R个点，v1, v2, , vR为类1, 2, , R的代表，或

12、称样本模式。最小距离分类器将待分类模式x识别为距其最近的代表所在的类别。xVxVxdsRsrr ,.,1min)(46若每类仅由一个模式表示。则分类器将是线性的。若一类中可能具有多个模式，则分类器为分段线性的分类超平面。47非线性分类器通常利用某些适当的非线性函数，将原始特征空间Xn变换到一个新的特征空间Xm，其中上标n，m表示空间的维数。 mnmXX:,.,2148非线性变换后，在新的特征空间中就可以采用线性分类器了函数的作用在于将原始特征空间中的非线性分类超曲面“拉直”，变成变换特征空间中的超平面。这种利用特征空间变换的方法称为-分类器。 49-分类器的判别函数为： 其中r=l,R。 )(

13、)()(110 xqxqqxgmrmrrr50基于判别函数的分类器是一种具有确定性的机器同一模式x总会被分到同一个类。模式x可能表示来自不同类别的物体。最优分类器的设置应该是概率方式的。51错分情况会给用户带来某些损失，根据损失的定义，可以得出不同的最优分类器设置标准。从数学的角度来看，这些优化标准表示了分类损失的平均值。52将分类器视为一种通用机，可以表示规则集合D中的任一决策规则。集合D可以根据某个与特定判别规则有关的参数向量q进行排序。损失J(q)的平均值依赖于所采用的决策规则： =d(x, q)。53与上一节中采用的决策规则定义相比，增加了参数向量q，它表示分类器使用的特定决策规则。使

14、得损失J(q)均值最小的决策规则： 称为最优决策规则，q*称为最优参数向量。 qxd,DqxdqJqJq),()(min*)(54q误差最小准则（Bayes准则，最大似然度）；q最佳近似准则：基本原理是用事先确定的一系列函数 ，i=1, , n的线性组合对判别函数进行最佳线性逼近，然后再构造-分类器。)(xi55能够由一个样本集合对分类器进行设置非常重要，这一过程被称为分类器学习。分类器设置根据的是一个已标明正确类别的物体（由特征向量表示）集合这一模式集合连同它们的类别信息被称作训练集合。56分类器的性能取决于训练集合的性质和规模，而训练集合通常是有限的。不可能在设计分类器时用到所有将来可能要

15、处理的物体；也就是说除了训练集合中的模式外，分类器还要面对那些在设计和设置分类器时没出现过的模式。 57分类器设置方法应该是归纳式的，因为从训练集合的元素中获取的信息将被推广到整个特征空间，这就意味着分类器设置应该对所有可能的模式来说都是（近似）最优的，而不仅仅是针对训练集合。换言之，分类器应该能够识别那些它没有“见过”的物体。 58训练集合越大，得到正确分类器的可能性也就越大分类正确率和训练集合的大小密切相关。 一般训练集合大小将经过几次增加，直到得到正确的分类设置为止。最初无法解决的问题，随着训练集合的增大，加入了更多的信息，直到求得问题的解。 59逐渐增加训练集合大小的基本思想可以理解为

16、：将一个很大的训练集合的一小部分用来设计分类器，而用余下的部分测试分类器的性能。所有分类器设置方法的特性在有生命的生物体的学习过程中都可以找到相似之处，学习的基本性质如下： 60q学习是一个基于样本顺序输入的自动的系统优化过程。q学习的目标是使优化准则最小。这一准则可以用错分损失均值表示。61q训练集合有限，这就要求学习过程具有归纳的特点。q在所有可能的样本都用来学习之前，通过推广已有样本信息达到学习目的。q样本可能是随机选取的。62对信息顺序输入的必然要求和系统存储的有限性导致了学习的渐进性。q因此，学习过程无法一步完成，而是一个循序渐进的过程。 63学习过程根据样本搜索最优分类器设置。分类

17、器系统被构造为一个通用机，这个通用机经过对训练集合的处理完成优化（有监督学习）。学习方法独立于应用问题。64分类器性能与可得到的信息总量及其性质密切相关。从这一角度来说，模式应该表示尽可能复杂的描述。但另一方面，这样做会带来大量的描述特征。因此，物体描述交际上是在允许分类错误率、分类时间和分类器构造复杂度之间的一种折衷。 65两个常用的学习策略：概率密度估计：对概率密度p(x|r)和概率P(r), r=1,R进行估计。q判别函数根据误差最小准则计算得到。66直接损失最小化：并不估计概率和概率密度，而是通过直接对损失J(q)进行最小化寻找决策规则 。q这种方法采用最佳近似准则。qxd,67算法：

18、最小距离分类器的学习和分类 学习：对于所有类，由训练集合计算类代表Vi： 其中xi(ki+1)为第i类的物体，ki表示目前第i类被学习过程使用的物体总数。) 1()(11) 1(iiiiiiiikxkvkkkv68分类：对一个物体描述向量x，计算x到所有类代表vi的距离。若其中x到vj的距离最短，则将此物体分为第j类。69存在不需要学习训练集合的分类算法。特别地，这类分类算法不需要学习阶段中关于物体类别的信息，没有指导它们也可以通过学习得到这种信息（无监督学习）。这种方法中的一类称为聚类分析。 70当出于某种原因无法得到训练集合或无法得到标有类别的样本时，就可以采用聚类分析方法。 聚类分析方法

19、根据待处理模式集合中各元素间的相似度将其分为若干子集合（聚类）。71每个聚类所包含的模式代表了在被选特征及相似准则意义下比较相近的物体。不相似的物体分属不同类别。 主要的聚类分析方法有两类：第一类为分级式的，第二类为非分级式的。72分级方法构造一棵聚类树，模式集合被分为差别最大的两个子集，每个子集再被分为不同的子集，等等。非分级方法顺序地将每个模式分到一个聚类中。 73非分级聚类分析方法要么是参数化的要么是非参数化的。参数化方法基于已知的类条件分布，需要对分布参数进行估计。74非参数聚类分析是一种应用普遍、简单实用的非分级式聚类分析方法。MacQueen k-均值（MacQueen k-mea

20、n）聚类分析法是这类方法中的一个著名实例。 75我们需要假设聚类总数k已知若k未知，则可令其等于有最大置信度的类别总数，或采用其它不需要这一信息的更复杂的聚类方法。 聚类的初始点在第一步中构造，由n维特征空间中的k个点表示。76这些点可以以随机方式选取，或直接取集合中的前k个模式。若聚类的代表已如，即使这些代表并不可靠，将它们作为聚类初始点也是非常有用的。 77方法主要有两个阶段：在第一阶段中，模式分配到已有聚类中的一个，依据就是模式到各聚类代表的距离，选择距离最小的类。1.然后，计算该聚类所有模式的重心，作为该类新的代表。78q若集合中的所有模式都已经处理完毕，则当前聚类代表被最终采用，将每

21、个模式分到一个聚类中，这些聚类由第一阶段确定的代表表示。q然后，根据模式到代表的距离将它们重新分类，模式被分到最近的类中。79第二阶段中不再新计算代表。可以看出，各聚类的初始点可能最终不在该聚类中。80算法：MacQueen k-均值聚类分析 定义聚类总数。选择聚类初始点（代表，初始猜测）v1,v2,vk。通常选择某些模式作为聚类初始点，也可以随机选取。 81第一轮：对每个模式决定其属于哪个聚类，选择距离最近者（初始化聚类所用的模式不再处理）。每向一个聚类中加入新物体后重新计算该类代表，可以采用如下公式。) 1()(11) 1(iiiiiiiikxkvkkkv82第二轮：令最终代表为结果聚类的

22、代表。根据第一轮得到的最终代表对所有物体分类（包括初始化聚类所用的模式）。与第一轮采用相同的距离准则。 8384自从80年代神经元网络重新受到瞩目并成为一种模式识别的典型方法以来，这种方法引起了人们的极大兴趣。神经元网络在许多公认的“困难”领域，特别是语音和视觉中的模式识别问题，都是一种强大的工具。85大多数神经元方法都源于基本处理器（神经元）的组合，每个基本处理器接收若干输入，产生单个输出。对每个输入都有一个权值与其相关联，于是输出（大多数情况下）就是关于输入加权和的一个函数。86v1w1v2w2vnwnF(v,w)输出y输入由v1,v2,vn表示，权值为w1,w2, wn，于是神经元的整个

23、输入为:niiiwvx187或者，更一般的：其中为与该神经元相关的阈值。与神经元相关联的还有一个输出函数f(x)，输出由此函数产生。niiiwvx188神经元集合（网络）的主要思想是神经元之间相互连接（于是一个神经元的输出也是另一个或另一些神经元的输入）。这一思想模仿了大脑中基本神经元的高度互连状态。89这种互连可能会接收若干来自外部的输入，并产生一些（数量上可能与外部输入不同）外部输出。这些外部输入与输出之间的关系即规定了网络。90基于反向传播算法的前馈网络假定输入与输出端之间至少存在一层神经元。在前馈网络中输入端接收数据，并且数据总是沿一个方向传递到输出端，输出端最终给出“答案”。 91使

24、用这种网络的标准方法是收集一个训练数据集一个”答案”已知的向量集合。采用这个训练集再加上某种训练算法就可以让网络进行学习了，最终得到的网络能够进行正确的联想。于是，在分类模式下，未知模式被送入网络。然后网络基于对已有知识的推广给出一个答案。 9293反向传播算法将网络的输出与希望值进行比较，并计算某种基于差别平方和的误差测度，然后再利用梯度下降法调整网络权重，使得误差最小化。94另一类不同的网络是自学习的就是说无需一个已知类别信息的训练集合，它们也可以进行自组织，达到自动识别模式的目的。这一大类网络中又有许多变形，其中最著名的是Kohonen特征图。 95Kohonen图的输入为n维数据向量，

25、输出也是n维的，代表了在邻近问题域内对特定输入的“最佳表示”。更精确地说，网络包含一层神经元，每个神经元都与输入向量的所有n个元素相连，并计算其自己的输入，具有最大输入值的被认为是“胜者”。96与输入弧相关联的n个权值就是最后的输出向量。权值的更新采用一种寻找自身数据结构（就是说不需要或真正知道先验类别知识）的学习算法实现。97 98 Hopfield网大多用于优化问题，然而，可以将识别问题表示为优化问题，即寻找待识别模式x和现有代表v之间的最大相似性。 99以上慨述只涉及到了神经元网络的主要原理和它们同传统统计模式识别的关系，对诸多神经元网络技术、方法及实现都未涉及。 100101统计模式识

26、别采用定量的物体描述，这类描述具有数值参数（特征向量）。而句法模式识别的特点则是定性的物体描述。 物体结构包含于句法描述中。 102当特征描述无法表示被描述物体的复杂程度时，或当物体可以被表示成由简单部件构成的分级结构时，就应该采用句法物体描述。句法描述的物体的最基本性质称为基元。 103第6.2.4节中提到了采用边界基元的物体边界的句法描述，这些边界基元表示边界上具有特定形状的片段。物体的图或关系描述是一个很好的例子，其中基元表示具有特定形状的子区域。104为所有基元赋一个符号后，就可以描述物体各个基元间的关系了，最终将得到一个关系结构。对基元描述和它们之间关系的设计不是算法化的，而是基于对

27、问题的分析、设计者的经验和能力。105基元类型不要太多。被选中基元应该能形成正确的物体表示。基元应该能较容易地从图像中分割出来。基元应该能够由某种统计模式识别方法较容易地识别出来。基元应该与待描述物体（图像）结构的重要的自然部件相对应。 106假定物体已经由一些基元和它们之间的关系正确地描述了。并且，假定对每一类来说其语法都已知，该语法能够生成特定类别中所有物体的描述。107句法识别决定一个描述词语对于特定类的语法是否在句法上是正确的，也就是说每个类只包含其句法描述能够由该类语法生成的物体。句法识别是一个搜索语法的过程，目标语法能够产生描述待处理物体的句法词语。108算法：句法识别学习：根据对

28、问题的分析，定义基元及它们之间可能的关系。对句法描述进行人工分析，或利用自动语法推导，为每类物体构造一个描述语法。109识别：首先，提取每个物体的基元，识别基元所属类别，并描述它们之间的关系。构造代表物体的描述词语。基于对描述词语的句法分析结果，对物体进行分类，若某类的语法（在第2步中构造）能够产生该物体的描述词语，则物体被判定为该类。110可以看出统计识别和句法识别的主要区别在于学习过程。利用目前的技术，语法构造过程很难算法化，需要大量的人工干预。111通常基元越复杂，则语法越简单，句法分析也越简单迅速。但是，复杂的集元描述使得上述算法中的第3步更加困难、更耗时间，而且，基元提取和关系估计也

29、变得不容易处理。112假设已经成功地提取了基元，则所有内部基元关系都可以从句法上描述为n元关系，这些关系构成的结构（链、树、图）称为词语，用来表示物体或模式。113因此每个模式由一个词语描述。特定类中所有模式构成的集合对应于一个词语的集合。这个词语集合称为形式语言，并且由一个语法描述。 114若已存在一个适当的语法可以用来表示各类别的所有模式，则最后一步就是设计一个能够正确判断模式（词语）类别的句法分类器。 115显然最简单的方法是为每个类分别构造一个语法。未知模式x被输入一个由若干黑箱构成的平行结构，这个装置可以判断是否xL(Gj)，其中j=1, 2, , R，R为类别总数；L(Gj)为由第

30、j个语法产生的语言。116如果第j个黑箱的决定为正，则模式被认为是来自于第j类，分类器将这个模式判定为属于第j类。判断一个词语是否能由某个语法产生是在句法分析过程中进行的。117为了为某类模式的语言构造尽可能贴切的模型，需要从一个样本词语的训练集合中提取语法规则。这一从样本中构造语法的过程称为语法推导。118119本节将讨论基于图匹配的识别方法。节点和弧都赋值的图将是我们考虑的对象，这种图出现在利用关系结构的图像描述中。图匹配的目的是判断一幅图像所表示的实际物体是否与图模型中关于这幅图像的先验知识相符。120如果将这一任务表示为模式识别问题，则物体的表示图应该与物体的模型图完全匹配。若问题是在

31、图像的图表示中寻找某个物体（由模型图表示），则模型图应该与图像表示图中的某个子图完全匹配。图之间的完全匹配称为同构。121图同构和子图同构的判定是图论中的经典问题，在应用和理论上都有很大的价值。 现实中的问题要复杂得多，因为在识别问题中完全匹配的要求通常是非常严格的。 122由于物体描述的不准确、图像的噪声、物体间的遮挡、不同光照条件等因素，物体图通常不能与模型图完全匹配。图匹配和图相似度估计是一个非常困难的问题。图相似度估计中的一个重要问题是设计一个衡量两幅图是否相似的尺度。 123无论所要求的是图同构还是子图同构，问题可以被分为三种主要类型：图同构；子图同构：寻找图G1与另一个图G2的子图

32、间的同构； 1.双重子图同构 ：寻找图G1的子图与图G2的子图间的同构。124同构的判定对于未赋值图和赋值图来说计算量都十分庞大。赋值图在识别和图像理解中更常用，其节点的取值根据所代表的区域的性质而定，而弧的取值根据所连接的节点间的关系而定。 125上面所提到的所有方法都用来检测图和或子图之间是否完全匹配。在实际应用中这些算法无法区别两幅十分相似但有少许差别的图和两幅根本不一样的图。若要检测图的相似度，则要研究如何量化相似性。 126两个字符串（链）的相似度可以用Levenshtein距离表示，该距离定义为将一个串变为另一个串所需的最少操作步数，可能的操作有删除、插入、替换。同样的原理也可以用

33、在图相似度的计算上。127先定义可能的节点和弧的变换（插入、删除、替换、重新标注）集合，再给每种变换赋一个变换代价。任一变换序列的代价用单个步骤代价的组合表示。将一个图变为另一个图的所有变换集合中具有最小代价值的那个集合就定义了这两幅图间的距离。128129考虑图像识别和理解问题，需要搜索最佳图像表示（要求图像和模型间的最佳匹配，目的是得到最佳图像理解）。一定会有某种刻画优良程度的目标函数，也就意味着可以采用某种优化技术，寻找目标函数的最大值，即寻找“最佳”。130一个函数优化问题可以这样定义：给定某个有限集合D和一个函数f: DR，R为实数集，在D中寻找f的最佳值。在D中寻找最佳值可以理解为

34、寻找xD，使得f取到最小值（函数最小化）或最大值（函数最大化）。)(min)(minxfxfDx)(max)(maxxfxfDx131函数f被称为目标函数。在此我们仅考虑目标函数的最大化，因为它是图像解释应用中的典型问题。搜索最大值和最小值的优化方法在逻辑上是等价的，无论要求目标函数最大化还是最小化，都可以使用优化技术。 132应该注意，若目标函数没有反应结果的优良程度，则无论什么优化算法也不能保证找到正确的解。因此，目标函数的设计是决定优化算法性能的关键因素（就好比选择合适的特征是设计成功分类器的关键）。 133大多数传统的优化技术都采用微积分的方法，如爬山算法（求最大值时）目标函数的梯度给

35、出了最陡峭的攀爬方向。微积分方法的主要局限在于其局部行为，搜索很容易止于一个局部极大值，而未找到全局最大值。 134有几种方法用来增加找到全局最大值的可能性。遗传算法和模拟退火就属于这类技术。 135遗传算法（GA）模拟自然界的进化机制来寻找目标函数的最大值。遗传算法不保征找到全局最优，但来自大量应用的经验显示最终解通常很接近全局最优。这一点在图像理解的应用中十分重要。136在图像理解或匹配中几乎总是存在几个局部最优的稳定（合理的）解，但这些可能的解中只有一个是真正最优的，表示了全局最大值。遗传算法与其他优化方法的主要区别有以下几个方面：137GA的作用对象是参数集合的编码，而不是参数本身。遗

36、传算法要求将优化问题的自然参数集合编码为有限字符集上的有限长字符串。这就意味着任何优化问题表示都要转换成字符串表示，通常采用二值字符中。将问题表示设计成字符串是GA方法的一个重要部分。138GA搜索一群点，而不是单个的点。每一步中被处理的解的代规模很大。q也就是说最优搜索是在搜索空间的许多位置同时进行的。这就增加了找到全局最优的可能性。 139GA直接利用目标函数，无需再进行其它演化和辅助知识。对新的更好的解的搜索只依赖于评价函数本身的值。GA只负责找到评价函数的（近似）全局最优。但不保证评价函数与问题相关。评价函数描述了特定字符串的优良程度。在GA中，评价函数的值被称为适合度。140GA采用

37、概率方式的变换规则，而不是确定式的。采用当前字符串代生成更优一代的变换规则。即有较高适合度的串将获得更大的机会，而那些适合度较低的串将被淘汰。这是遗传算法的关键思想。最好的字符串将在进化过程中以更高的概率存活下来，它就代表了最优解。 141q字符串编码的优胜劣汰是通过三种基本操作实现的：复制、交叉和突变。 q字符串的代由GA当前正在处理的所有串构成。q复制、交叉和突变的序列作用于上一个字符串代，从而生成新的一代。 142复制操作负责以慨率的方式保证适者淘汰劣者。复制机制将具有很高适合度的字符串拷贝到下一代中。选择过程通常是慨率方式的，一个字符串被复制到下一代的概率由它在当前代中的相对适合度决定

38、这就是它们的生存法则。 143这就使得一些具有很高适合度的字符符可能在下一代中会有多个拷贝。各代字符串的总数通常保持不变，新一代的平均适合度要高于以前的代。 144交叉的基本思想是令新一代中的字符串进行交叉，为一个字符对串随机地选择一个边界位置，然后交换这两个字符串从开始到边界位置的所有字符，以生成两个新的字符串。145146并不是所有新生成的字符串都来自交叉。有一个概率参数用来控制进行交叉操作的字符串对数。另外，还可以令复制得到的最佳串保持不变。 147交叉操作和复制操作构成了GA的主要功能。即使字符串本身并不是一个好的解，也可以在其中找到具有局部较好结构的字符片段。这些字符片段称为图式。图

39、式是那些可以作为字符串构造部件的子串，可以理解为字符的局部模式。148显然，若图式可以被作为局部正确的片段进行处理的话，就可以比将所有字符单独考虑更快地找到最优解。包含n个字符串的一代中，大约要处理n3个图式。这种处理称为遗传算法的隐含并行性。 149突变操作在GA中起到辅助作用。其原理是偶尔随机地改变一代中某些字符串的一个字符例如，突变发生的概率可以是约一千个位转换中出现一个（即在代代间转换时，转换一千个位就有一位发生突变）。 150突变的主要原因是字符串中的一些局部的字符组合可能由于复制操作和交叉操作而完全丢失。突变操作可以防止GA因这种无法恢复的丢失而找不到较好的解特征的情况发生。 15

40、1最少需要多少代达到收敛是一个重要的问题。对于应用目的来说，这一问题变为何时可以停止生成新的字符串代。一个普遍的同时也由实践证明的标准表示当连续几代中的最大适合度都没有实质性提高时，就可以考虑停止算法了。 152到此为止我们都还没有讨论如何创建初始代，通常初始代包含大量字符串，具体数目根据应用问题而定。假定已知字符集和字符串长度，则可以随机生成初始代。153若已知一些关于解的先验知识（可能的局部字符模式，字符在字符串中出现的概率，等等），则可以利用这些信息生成初始代，令适合度尽可能地大。初始代越好，搜索最优的过程将越快、越简单。154算法：遗传算法创建字符串编码的初始代，计算它们的目标函数值。

41、以概率方式将具有较高适合度的字符串复制到新一代中，淘汰适合度较低的串（复制）。组合从上一代拷贝来的字符串编码，构造新的串（交叉）。155偶尔随机地改变一些字符串中的某个字符（突变）。根据当前代中字符串的目标函数值（适合度）对它们进行排序。156若最大字符串适合度在连续的几代中都没有明显增加，则停止。q当前具有最大适合度的串即表示所求最优解。否则，跳到第2步。157模拟退火代表了另一类鲁棒的优化方法。与遗传算法相同，模拟退火也对表示复杂系统好坏的目标函数（代价函数）进行最小值搜索。 模拟退火不保证找到全局最优解，但通常可以得到近似最优解。 158模拟退火综合了两个基本的优化原理，分而治之和迭代改

42、进（爬山算法）。这样结合使用可以避免停止在局部最优上。统计力学和热力学之间的密切关系和多元或组合优化是退火优化的基础。 159在统计力学中，实验只观察到特定温度下系统热平衡时最可能的状态改变，每个状态都由系统的原子位置集合xi定义，并用Boltzmann常数概率因子赋给权值， TkxEBiexp160其 中 E ( xi) ) 为 状 态 的 能 量 ， kB是Boltzmann常数，T是温度。Boltzmann概率密度的一个主要特点是在温度很高时，所有的状态几乎有同样的可能性成为下一个状态，但在温度较低时具有低能量的状态更有可能成为新的状态。 161优化可以比喻为物质形成晶体结构的能力，若物

43、质被熔化后再以很慢的速度冷却的话，晶体结构将是能量最小的状态。这一最小值可以看作是能量函数的优化最小值，而能量函数的作用与目标函数相同。162结晶过程依赖于冷却熔化液体的速度，若冷却速度太快，则晶体将包含许多局部瑕疵，因此也就没达到全局最小能量。模拟退火由迭代的下山步骤和有控制的上山步骤组成，使得它有可能跳出局部极小点。 163上山步骤使得它可以跳出局部极小点；虚线表示可能的收敛路经 164这一过程的物理模型为，对物质加热直至熔化，然后将熔液在保持准热平衡的条件下慢慢冷却。冷却算法包括反复随机地替换物质中的原子（状态改变），及每次状态改变后计算能量的改变E。165若E0（更低的能量），则状态改

44、变被接受，新状态作为下一轮步骤的起始状态。若E0，则状态以如下概率被接受： TkEEPBexp166为了将这个物理模型应用于优化问题，应该在优化过程中将温度参数T以可控制的方式降低。算法的随机部分可以通过生成在(0,1)上满足平均分布的随机数实现，选择这样一个随机数并与P(E)进行比较。 167算法：模拟退火优化 令x为优化参数的向量，计算目标函数J(x)的值。将第3步和第4步重复n(T)次。对参数向量x做轻微扰动，得到新向量xnew，计算新的优化函数值J(xnew)。168生成一个随机数r(0,1)，满足区间(0, 1)上的平均分布。若 则令x=xnew且J(x)=J(xnew) 。TKxJ

45、xJrBnew)()(exp169重复第2步和第4步直到满足收敛标准。这时参数向量x表示优化问题的解。 170注意，事先并不知道需要多少次迭代步骤，怎样的参数扰动（状态改变），选择什么温度T，采用多快的冷却速度才能得到最好（或仅仅是较好）的结果。虽然有一些一般性的原则可供参考，但对于特定的问题有特定的合适的参数。 171目前只知道对任一温度来说，退火过程都应该用足够长的时间来达到稳定状态。温度序列和每个温度达到热平衡所需的迭代步数n称为退火进度。172较大的迭代步数n和较小的温度T变化步长可以产生的最终优化函数值也更低（解更接近于全局最小），但需要较长的计算时间。 较小的迭代步数n和较大的温度

46、T变化步长可以更快结束，但结果也可能离全局最小比较远。173因此需要仔细设置T和n的值，使得在可以接受的时间内得到比较接近全局最小的解。然而目前还没有设计出退火进度的实用方法。 很多应用问题都用到退火算法，如模式识别、图的分割等，退火算法有着极大的实用价值。174175模糊系统可以表示多变的、不精确的、不确定的和不准确的知识或信息。同人类表达知识的方式类似，模糊系统采用修饰语，如明亮的、比较暗的、暗的，等等。176模糊系统可以表示复杂的知识，甚至是来源矛盾的知识。模糊系统基于模糊逻辑，后者代表了一类强大的决策方法。177 人描述物体时通常会采用不精确的描述，如明亮的、巨大的、圆形的、长条的，等

47、等。 模糊逻辑使得同一区域可以同时属于不同的模糊集合。 178模糊空间X中的一个模糊集合S为一个有序对的集合： 其中S(x)表示x在集合S中的隶属程度。通常模糊集合仅用其隶属函数表示。XxxxSS|)(,179下图中所示对暗色区域的描述是一个经典的模糊集合的例子，体现了模糊空间的性质。 模糊集合的定义域画在x轴上，取值从黑到白（0255）。垂直坐标轴表示隶属度(x)。隶属度可以取0到1间的值，0表示不属于，l表示完全属于。180一块平均灰度值为255的白色区域关于模糊集合DARK的隶属度为0，而一块黑色区域（平均灰度值为0）关于模糊集合DARK具有完全隶属度。隶属度函数可以是线性的，见图b。也

48、可以采用其它形式的曲线（见图c和图d）。181 精确集合表达了集合DARK的布尔性质；模糊集合DARK；与模糊集合DARK相关的另一种可能的隶属函数；再一种隶属函数。 182考虑晴天云和积雨云的平均灰度值，下图画出了可能与模糊集合DARK、MEDIUM_DARK和BRIGHT相关的隶属函数。模糊集合的最大隶属度取值称为模糊集合的高度。183一个具有特定平均灰度值g的区域可能同时属于多个模糊集合。隶属度DARK(g)，MEDIUM-DARK(g)和BRIGHT(g)表示了描述的模糊性。因为它们估计了区域属于特定模糊集合的确定程度。184 与模糊集合DARK、MEDIUM_DARK和BRIGHT相

49、关的隶属函数。注意可能有几个隶属度取值与同一特定平均灰度值g相关联。 185在模糊系统的设计中采用规一化的隶属函数。最小正规形式要求在模糊集合的定义域中至少有一个元素的隶属度为1。最大正规形式是定义域中至少有一个元素的隶属度为0的最小正规形式。 186在模糊推理系统中，模糊隶属函数通常被设计为最小正规形式。 模糊隶属函数的形状可以通过模糊集合限制进行调整。限制可以对模糊集合中元素的隶属度进行加强、减缓、求补、精细或大体上近似，等等。187 模糊集合VERY_DARK。模糊集合SOMEWHAT_DARK。模糊集合NOT_VERY_DARK188 很少有某个识别问题可以仅仅用一个模糊集合及其隶属函

50、数就能解决。因此，需要有一个工具能够将不同模糊集合结合起求，并确定这种联合后的隶属度。 189对于模糊集合有三个基本运算：模糊交、模糊并和模糊补。令A(x)和B(y)为两个隶属函数，分别与模糊集合A和B相关，这两个集合的定义域分别为X和Y。于是对所有xX，yY，交、并和补逐点定义为 ： 190注意，模糊集合运算可以同限制相结合，从而构造新的模糊集合。 )(),(min,:yxyxBABABA交)(),(max,:yxyxBABABA并)(1)(:xxAACAC补191在模糊推理中，将一些含有信息的单个模糊集合结合起来做出决策。决定相关模糊隶属度的函数关系被称为合成方法（混合办法），并且定义了模

51、糊解空间。192为了做出决策，采用一个逆模糊（分解）过程确定模糊解空间和决策间的函数关系。合成和逆模糊过程构成了模糊推理的基础。193限制模糊规则模糊变量解空间模糊合成决策逆模糊194模糊模型使用了一系列无条件和有条件的命题，称为模糊规则。无条件模糊规则的形式为：x是A有条件模糊规则的形式为： if x 是 A then w 是 B1.其中A和B是语言变量，z和w表示分别属于各自定义域的标量。195与一个无条件规则相关联的隶属度就是A(x)。无条件模糊命题用于限制解空间，或定义默认解空间。由于这些规则是无条件的，因此采用模糊集运算可以直接将它们作用于解空间。考虑条件模糊规则，有几种方法可以对其

52、做出决策。196单调模糊推理是其中最简单的一种，不用合成及逆模糊就可以生成解。 令x为表示描述云彩暗度的一个标量灰度值，w表示雷雨的激烈程度。则下列模糊规则可以表达我们关于雷雨激烈程度的知识。if x是DARK then w是SEVERE197根据对云彩灰度的判断（在例子中x=80），确定隶属度DARK(80)=0.35。这个值就表示隶属度SEVERE(w)=DARK(x)，据此可以对雷雨激烈程度做出判断。 在如下例子中w=4.8，其定义域为0到10。198基于一条模糊规则的单调模糊推理：若云的灰度值为DARK，则雷雨为SEVERE199这个方法同样适用于具有如下形式的复杂的断言：if (x是

53、A)(y是B) (u是F) then w是Z其中表示合取AND或析取OR运算。可以结合模糊交和模糊并来实现复杂断言，AND对应模糊交，OR对应模糊并。 200单调方法体现了模糊推理的根本概念，但它只能用于由一条模糊规则控制的单个单调模糊变量（可能还有一个复杂断言）。当谓词命题的复杂度增加时，判断的合理性会有所下降 。 201为完成决策过程所需的知识通常包含在若干条模糊规则中。许多模糊规则将参与到决策过程中，并且所有决策规则将在这一过程中被平行地激活。202显然，不是所有模糊规则对最终解都有同样的贡献，前提根本就不会成立的那些规则对结果就不会有任何影响。有几条合成机制来帮助我们进行规则组合，在此

54、将讨论其中一种最常用的方法，称为最小最大规则。203最小最大规则在最小最大合成方法中，采用一系列最小化和最大化操作。首先，采用谓词真值的最小化（相关性最小化）Ai(x)约束结果模糊隶属函数Bi(w)。令规则具有如下的形式，i表示第i条规则。 if x 是 A then w 是 B204于是，结果模糊隶属函数B，逐点地被更新，形成新的模糊隶属函数Bi+。2.由这些最小化后的模糊集合的逐点最大值构造解模糊隶属函数。 )(),(min)(xwwiiiABBmax)(wwiBiS205 206上面所介绍的相关最小化是最常采用的用来完成最小最大合成第一步的方法。另一种可选的方法称为相关乘积，这种方法对原

55、结果模糊隶属函数乘一个尺度因子，而不是对其进行截断操作。207相关最小化只需要较少的计算量并且容易被逆模糊。而相关乘积在很多方面都代表了一种更好的最小化方法，因为模糊集合的原有形状没有被改变。208 209模糊合成对每一个解变量生成一个解模糊隶属函数。为了找到用于做出决策的真正的准确解，需要先找到一个最佳表示了解模糊集合中信息的标量向量（每个标量分量对应一个解变量）。这一过程对每个解变量独立地进行，称为逆模糊。 210常用的逆模糊方法有两种，分别称为力矩合成和最大值合成，此外还有许多其它方法。力矩合成寻找解模糊隶属函数的质心c下图a演示了质心方法如何将解模糊隶属函数转换为明确解变量c。 211

56、最大值合成将定义域点等同于取到解模糊隶属函数最大隶属度值的那一点。若这一点不确定（在一个平台上或存在几个相同的全局最大值点），则平台的中心（或最左和最右全局最大值点的中点）将作为明确解c，参见下图b。 212由力矩合成产生的结果对所有规则都敏感，而最大值合成方法确定的解只对有最高断言真值的那条规则生成的隶属函数敏感。力矩合成大多用在控制应用中，而最大值合成则用于识别应用中。 213 (a) 力矩合成 (b) 最大值合成214 模糊系统设计主要由如下算法中的几个步骤组成。 215算法：模糊系统设计设计系统的功能和运转特性确定系统输入、基本处理方法、系统输出。在物体识别中，输入为模式，输出表示判定。 通过将模糊系统的输入和输出分解为一个模糊隶属函数的集合，定义模糊集。216q与每个变量相关联的模糊隶属函数数目依赖于具体问题。q通常每个变量关联的模糊隶属函数总数为3到9间的一个奇数。q建议相邻模糊隶属函数相互重叠l050。重叠部分的隶属度总和最好小于1。 217将特定问题的知识转变为if-then形式的模糊规则，这些规则代表了模糊联想记忆。q规则的数目与输入变量的数目有关。对于分到M个模糊隶属函数的N个变量来说，需要MN条规则来覆盖所有可能的输入组合