模式识别的理论与方法

1、第十章模式识别的理论与方法n 第十章模式识别的理论与方法Ø 模式识别概述Ø 基本概念模式与模式类Ø 统计模式识别决策论法Ø 句法模式识别结构法Ø 模式识别的应用实例2第十章 模式识别的理论与方法对地观测与数字地球科学中心模式识别概述n 图像模式识别概述Ø 图像分析的重要目的ü 图像分割得到目标ü 纹理分析得到表示纹理的特征ü 图形描述得到特定目标图像的抽象化描述ü 图像的模式识别进一步明确目标的性质与特征Ø 图像识别（模式识别）：对待研究的对象，根据其某些特征，进行识别并分类Ø

2、; 文字识别是迄今为止人类最熟悉、应用最识别领域的图像Ø 目前在鉴别、手语识别、面容识别、表情识别等方面正在取得进展Ø 进一步的发展结合人工智能，向更高级的识别水平发展3第十章 模式识别的理论与方法对地观测与数字地球科学中心模式识别概述4第十章 模式识别的理论与方法对地观测与数字地球科学中心模式识别系统模式识别概述n 模式识别流程结果5第十章 模式识别的理论与方法对地观测与数字地球科学中心特征提取预处理数据获取模式识别概述n 图像模式识别的现状Ø 模式识别（pattern cogniton，亦可译为模式辨认、图像识别、图形识别、型式识别）是近30年来得到迅速发展的

3、一门新兴边缘学科。关于什么是模式或者所能辨认的模式，迄今还没有一个确切而严格的定义。(KanalL.)曾经说过这样一段话：ü “关于什么是模式识别和所能辨认的模式，至 今还没有人能象香农(Shannon)对信息一词做出定义那祥，给出一个确切的定义。如果一旦出现了这样一个定义并被证实能够推动理论的发展，标志着人类智力的一大进展。虽然如此，目前的局面并不影响模式识 别在各领域中的广泛应用。”Ø 我们可以设计出自动图像识别系统，但仍然缺乏理论依据。有待人类视觉认识理论的进一步研究。Ø 我们可以做出在某一应用上超过人的能力的系统，但缺乏扩展性。过分依赖具体应用。6第十章

4、模式识别的理论与方法对地观测与数字地球科学中心模式识别概述n 图像模式识别的基础理论与方法Ø 决策理论是图像识别的理论基础Ø 特征和分类是图像识别的关键Ø 图像识别的基本方式ü 从待分类的图像中提取能够代表或排除某些类别的特征ü 根据特征将图像目标分到相应的类别中Ø 分类器的两个基本过程ü 学习过程：首先分离具有典型性的特征，根据这些特征对每个类别建立的描述，建立特征相应的特征空间ü 测试过程：根据输入样本和特征空间的划分，对全体图像进行分类Ø 图像的分割与识别实际上是一项非常的工作，很难说清楚为什么图像

5、应该是这样而不是那样7第十章 模式识别的理论与方法对地观测与数字地球科学中心模式识别概述n 图像模式识别的基本方法Ø 识别的统计分类方法：对待分类图像进行大量统计分析的基础上，找出规律性，抽取反映目标特征的统计进行识别。Ø 识别的句法结构方法：通过对图像结构的分析，一幅 图像可模仿语言构造，用一些语句来表达。通过符号匹配、语法分析等，实现图像中目标的识别Ø 宏观比较：统计识别方法很少利用图像本身的结构关系；句法结构方法未考虑图像获取过程中的噪声干扰n 现代方法研究Ø 模糊模式识别、神经网络模式识别、8第十章 模式识别的理论与方法对地观测与数字地球科学中心

6、模式识别概述n 统计模式识别方法Ø 基本原理有相似性的样本在模式空间中互相接近，并形成“n 特征与适用于：”，即“物以类聚”Ø 图像目标特征提取过程中的不精确性误差的存在Ø 同一类目标图像存在多种表述的可能性表述的随机性Ø 利用统计概念，如何使对已知类别的正确识别，在某种意义下使得错误识别的可能性达到最小9第十章 模式识别的理论与方法对地观测与数字地球科学中心模式识别概述n 句法模式识别方法Ø 基本原理基于形式语言的理论与概念，模式按其结构分解为子模式或模式基元，模式基元的连接关系以文法形式进行描述n 特征与适用于：Ø 图像中存在结构

7、信息，且识别的目的不仅需判别图像属于哪一类，还需描写图像的形态时某些识别目标，复杂图像可视为一些相对较简单的子图像组成，而这些子图像又可由一些更为简单的子图像来表示，最终分解为一系列简单的图像基元¾10第十章 ¾模图式识像别基的理元论之与间方法按一对组地成观测目与数标字地图球像科学中心规基本概念模式与模式类n 基本概念模式与模式类¾模式的定义¾模式类的定义¾模式识别的定义¾常用的模式序列9模式9模式串9模式树11第十章 模式识别的理论与方法对地观测与数字地球科学中心基本概念模式与模式类n 模式的定义Ø 样本(sample,

8、object)：一类事物的一个具体体现，对具体的个别事物进行观测所得到的某种形式的信号或表达Ø 模式(pattern)：表示一类事物，表示对该类事务特征或属性的抽象的描述；如印刷体A 与手写体A属同一模式，B与A则属于不同模式Ø 样本是具体的事物，而模式是对同一类事物概念性的概括12第十章 模式识别的理论与方法对地观测与数字地球科学中心基本概念模式与模式类n 模式的定义Ø 模式是图像中的一个对象或某些感区域的特征或结构的描述物体抽象特征的描述Ø 模式是由一个或多个描述子来组成Ø 模式是一个描述子的序列（名词“特征”经常被用来代指描述子）

9、6; 模式是一组特征或一组描述子13第十章 模式识别的理论与方法对地观测与数字地球科学中心基本概念模式与模式类n 模式类的定义Ø 模式所属的类别或同一类中模式的总体称为模式类，其中个别具体的模式常常称为样本Ø 模式类是具有某些公共特征的模式的系列Ø 模式类与模式使用时，模式表示具体的事物，而模式类则是对这一类事物的概念性描述n 模式识别的定义Ø 根据图像中对象的特征组成的模式，确定对象是属于那一个模式类，即为模式识别Ø 模式识别是从样本到类别的14第十章 模式识别的理论与方法对地观测与数字地球科学中心基本概念模式与模式类n 模式与模式类举例&#

10、216; 已知汽车的长、宽、高（x1,x2,x3），希望识别出： 大客车、小轿车、卡车（w1,w2,w3）9汽车的长、宽、高（L,W,H）模式大客车：(L,W,H)大；小轿车：(L,W,H)小；卡 车：(L,W,H)卡从而有模式类（w大, w小, w卡）Ø 定义了不同汽车的载重量，希望识别出大客车、小轿车、卡车（w1,w2,w3）9汽车的载重量M模式大客车：M大；小轿车：M小；卡车：M卡从而有模式类（w大, w小, w卡）第十章 模式识别的理论与方法15对地观测与数字地球科学中心基本概念模式与模式类n 常用的模式序列模式Ø 模式、模式串、模式树用粗体的小写字母表示，如x,y

11、形式如下：x1 x29模式.xnx =其中每一个x 代表第i个描述子，n是这种描述子的数量。模式被表示为一列或表示成x = (x1, x2, , xn)T16第十章 模式识别的理论与方法对地观测与数字地球科学中心基本概念模式与模式类Ø 模式举例假设我们想描述三种蝴蝶花（多毛的、多色的）通过测量它们花瓣的宽度和长度。这里涉及一个两维的模式：x1 x2x =其中x1、x2分别对应花瓣的长和宽三种模式类用w1、w2、w3表示17第十章 模式识别的理论与方法对地观测与数字地球科学中心基本概念模式与模式类由于所有的花瓣在宽和长上都有某种程度的变化，所以描述这些花瓣的模式也将有变化，不仅在不同的

12、类之间，而且也在类的内部在这种情况下每一种花变成二维空间的一个点18第十章 模式识别的理论与方法对地观测与数字地球科学中心基本概念模式与模式类x2 花瓣宽3.02.52.01.51.00.5多毛的多色的x1 花瓣长123456719第十章 模式识别的理论与方法对地观测与数字地球科学中心基本概念模式与模式类Ø 对结果的分析对花瓣长宽的测量， 它两种分离，但对于分离的。地将多毛的蝴蝶花与其和多色的是失败这个结论说明了分类的特性选择问题，在这个问题中，类的可分离性的程度，完全依赖于对模式尺寸测量的选择20第十章 模式识别的理论与方法对地观测与数字地球科学中心基本概念模式与模式类Ø

13、 模式串以对象特征的结构或空间关系作为模式时，形成模式串Ø 模式串举例：梯状的模式a(1) S->aA(2) A->bS(3) A->bbaababb21第十章 模式识别的理论与方法对地观测与数字地球科学中心基本概念模式与模式类¾模式树以分层目录结构排序的模式类，一般多采用树结构¾模式树举例图像城市田园城区内城市郊公路草地森林区 商业区区 商业区22第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 统计模式识别决策论法¾统计模式识别基本概念与过程¾决策论法的基本概念¾最小距离分类器¾相关

14、匹配分析¾¾特征的抽取与选择23第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 统计模式识别基本概念Ø 假定我们所处理的模式每一个样本都表示为N维特征矢量N )¢x = (Ø 将样本表示为N维特征矢量空间中的一个点，在特征空间中研究不同样本归属不同类别的问题Ø 假设我们要把一个样本集合分成M类：xr , xr , w ,w,.,w1212MØ 在N如何找到一个正确的子空间划分Ø 对样本x进行分类统计决策理论24第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 统计模式识别基

15、本过程Ø 分析阶段（学习阶段）9确定需分类的目标与类别9对每一种类别，选定一组目标样本9对样本数据进行分析（训练、学习），形成不同类别目标的特征Ø 识别阶段，每个一个模式9对待分类图像进行必要的预处理与特征提取9按照上述各类别的特征，对提取的特征进行判决分类（匹配），确定其归属的类别25第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 统计模式识别基本过程26第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 统计图像识别基本过程识别分析27第十章模式识别的理论与方法对地观测与数字地球科学中心改进规则误差检测规则学习特征选择特征提取预处

16、理训练样本图像输入分类特征选择特征提取预处理图像输入统计模式识别n 决策论法的基本概念¾决策论识别法的定义：x = (x1, x2, ,xn)T，设：模式对于：M个模式类 w1，w2，wM，寻找M个决策函数d1(x)，d2(x)，dM(x)，具有这样的特性：如果模式x属于模式类wi，那么：di(x) > dj(x)j = 1, 2, , M; j i换句话说，如果一个未知模式x属于第i个模式类，把x代入所有的决策函数，di(x)的数值最大。28第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 决策论法的基本概念Ø 决策边界的定义9对于模式x，如果决

17、策函数值有：di(x) - dj(x) = 0此x值，被称为wi与wj的决策边界。9通常用一个单一的函数标识两个类之间的决策边界， 定义为：dij(x) = di(x) - dj(x) = 0如果 dij(x) > 0 x 属于类wi 如果 dij(x) < 0 x 属于类wj29第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 最小距离分类器以蝴蝶花的例子为例：1为多色（w ）和多毛（w2 ）的两种蝴蝶花，（或称模板）m1和m2确定两个2对于一个未知模式x，x与m1和m2的距离，如果与m1 的距离小于与m2 的距离，则x属于w1，否则属于w2 。30第十章 模

18、式识别的理论与方法对地观测与数字地球科学中心统计模式识别x2 花瓣宽3.02.52.01.51.00.5m1m2多毛的多色的xx1 花瓣长123456731第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 最小距离分类器1）算法思想：9对于M个模式类 wjj = 1,2,.,Mmj为每一个模式类确定一个模式x，如果x与mj 的距离最9对于一个未知模式小，就称x属于wj。32第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 最小距离分类器2）最小距离分类器定义：1计算模式类wj的：mj = 1/Nj å xj = 1,2, , MxÎw

19、j其中Nj是属于模式类wj的模式通过计算已知属于wj的模式的个数。的各分量的均值，得到模式mj2计算x 与 mj的距离dj(x) = | x mj |其中 | a | = (aTa)1/2是j = 1, 2, , M范式（平方和开方）33第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 最小距离分类器3 决策如果，di(x) = min(dj(x)就说：x 属于wij = 1, 2, , M改写最大的标准形式，决策函数为：dj(x) = xTmj 1/2mjmjT如果，di(x) = max(dj(x)就说：x 属于wij = 1,2, , Mj = 1, 2, , M4类

20、wi和wj之间的决策边界是：dij(x) = di(x) - dj(x)= xT(mi mj) 1/2(mi mj)T(mi mj) = 034第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别3）举例：多色的和多毛的蝴蝶花，用w1和w2分别表示，有简单的m1 = (4.4, 1.3)T决策函数是：m2 = (1.5, 0.3)Td1(x) = xTm1 1/2m1m1 = 4.3x1 + 1.3x2 10.1Td2(x) = xTm2 1/2m2m2 = 1.5x1 + 0.3x2 1.17T决策边界的等式：d12(x) = d1(x) d2(x) = 2.8x1 1.0x2

21、 8.9 = 035第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别x2 花瓣宽3.02.52.01.51.00.5m1m2多毛的多色的决策边界2.8x1 +1.0x2x- 8.9 = 0-+5x1 花瓣长12346736第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 相关匹配(1) 相关匹配的基本思想:a. 用样板子图像直接作为模式（不是用描述子）b. 通过子图像与原图像直接进行相关计算，把相关计算结果作为决策函数。c.相关计算获得最大值的位置，就被认为匹配。37第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 相关匹配(1) 相关

22、匹配基本思想38第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别ytn 相关匹配(2) 算法描述决策函数是相关函数c(s,t) = f(x,y)w(x-s,y-t)xyN原点Ks对图像的每一个点进行相关计算，只计算重叠部分。J(s,t)Mxw(x-s,y-t)f(x,y)39第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 相关匹配（3）问题：Ø 在边界处将失去准确性，其误差与子图像的正比成Ø 相关函数对振幅的变化太敏感，f(x,y)加倍，c(s,t)也加倍。40第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 相关

23、匹配(4) 改进用相关系数函数代替相关函数f(x,y) f(x,y)w(x-s,y-t) w(s,t)=f(x,y)f(x,y)2w(x-s,y-t) w21/2xyxy(s,t)的值域为（-1，1）实例41第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 相关性匹配(5) 对旋转和比例变化的分析9当被匹配图像中，对象的致，此方法将失效和角度与模式不一9的正则化，解决空间比例的问题9如果知道原图像的旋转角度，我们可以通过旋转原图像，对齐模式解决9如果被匹配的对象的角度任意，有结论：此方法不能用于这种问题42第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别（

24、Bayes）分析Ø 当特征抽取时存在噪声干扰，则抽取的特征可能代表不了相应的模式，具有某种随机性Ø 利用训练样本产生的不同类别的模式，每个模式难于用一个来表示，只能得到每一类模式的一个概率分布Ø 为对此类特征进行分类，需采用统计意义上最佳的分类方法Ø 统计分类方法的最基本方法之一：分析分类器、贝分析包括：叶斯估计理论、决策方法、距离等¾43第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别（Bayes）分析公式¾设有N个互不相容的率为P(Bi) ；已知仅当其中某些：B1, B2, BN，每个发生的概件A才发生。若其中某

25、一发生Bi发生，A发生的可能性以概率P(A/ Bi)描述。A确实已发生，则对于A反过来，若发生条件下Bi发生的概率应给与重新估计，可有公式：P ( B i ) P ( A / B i )/ A ) =P ( BiNåj = 1P ( B) P ( A / B)jj44第十章模式识别的理论与方法对地观测与数字地球科学中心统计模式识别分析分类法设有M类图像：B1, B2, BM若已知Bi的先验概率：和某观察特征值X的条件概率：则由特征X 所决定的Bi的概率由¾P(Bi) P(X/ Bi)公式决定：P(Bi )P( X / Bi )P(B / X ) =iNå P(Bj

26、 )P( X / B j )j =1分类实质：从统计角度，在已知分类模式概率分布的条件下， 模式所应归属的类别¾新出现的45第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别分析分类法两个类别的分类¾如果某观察特征值X使P(B1/X)>P(B2/X)，则表明在X特征值出现的情况下，类别B1的可能性较高分类法则：P(B1/X) > P(B2/X)，则决策B1若反之，若 P(B1/X) < P(B2/X)，则决策B2公式，不同模式间重要的区别是其等价决策法则为：项，可有另一若P(X/B1)P(B1) > P(X/B2)P(B2)，则决策B

27、1反之，若 P(X/B1)P(B1) < P(X/B2)P(B2)，则决策B246第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别分析分类法两个类别的分类（例）分布的两个模式类1和2，假定每个类中的模式均服从高斯分布，即有¾在三- 1 ( X - M )T C -1 ( X - M )1P ( X / w ) =iiie2i1 / 2( 2p ) n / 2Ci即每一个模式类中变量的密度函数均由其均值和协方差矩阵惟一确定Ei ( X - M i )( X - M i ) TMi = Ei Xé3ùC i =- 484- 4ù

28、50;é 8é1ùC = C= ê- 41 ê1 êúú48M1 = 4 ê1úM2 = 4 ê3úêêë- 4úúû12êë1úûêë3úû47第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别分析公式，可得出决策函数为：由P(wi / X) = P(X / wi )P(wi )为计算方便，采用对数形式：i = 1,2d

29、i (x) = lnP(wi / X) = ln P(X / wi ) + ln P(wi )进一步假定P(1)=P(2)=1/2 ，可有：i = 1,21d (x) = X T C -1M -M T C -1Mi = 1,2iiii2d1(x) = 4x1 -1.5d2 (x) = -4- 5.53进一步得出两个类别的决策面为：d1(x) - d2 (x) = 8+ 4 = 0348第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别分析分类法对多类别问题，可有：若 P(Bi/X)>P(Bj/X)对所有j¹i成立，则决策Bi¾¾分类器利用上述

30、函数分类器如右图实例49第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 特征的抽取与选择Ø 合适的特征抽取与选择是正确分类的基础Ø 特征的选择影响到决策方法的采用与实施效果Ø 特征的提取与选择与模式定义密切相关n 什么是好的特征？Ø 好的特征之间是相互可区别的Ø 好的特征常常必须由来确定Ø 好的特征有通过统计方法来确定性假设Ø 相似类别目标的特征在特征空间中聚在一起Ø 不相似类别目标的特征在特征空间中可能聚在一起或相互远离50第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n

31、 特征的抽取与选择Ø 所要提取的应当是具有可区别性、可靠性、独立性好的少量特征Ø 特征选择可以看作是一个（从的开始）不断删除无用的特征和组合有关联的特征的过程，直到特征的数目减少到易于驾驭的程度， 同时分类器的性能仍能满足要求为止51第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 特征的抽取与选择多种方式（例）统计模式识别n 特征的抽取与选择实例Ø 鱼群的特征抽取鱼的长度x1 鱼的面积x2Ø 在（x1 , x2 ）空间形成两种类别的聚类群53第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 特征的抽取与选择实例特

32、征选择存在问题ü 噪声与生物多样性使每种鱼的特征类散布在一定区域ü 特征类别的重迭将导致分类误差¾聚类的距离与密度问题ü ？处如何分类属于A：与A类十分靠近属于B：因为B在该特征区域的密度最高¾54第十章模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 特征的抽取与选择实例通过特征空间的尺度变换可改变特征的聚合状况特征空间尺度变换可能带来的问题¾¾55第十章模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 特征的抽取与选择实例特征空间尺度变换可能带来的问题改进方法：使变化量相同¾56第十章模

33、式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 特征的抽取与选择实例直接由测量特征进行分类，最好结果将不可避免地存在误差¾57第十章模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 特征的抽取与选择实例Ø 通过统计方法改进特征空间类别的确定对每一类别样本，分别计算其均值和方差，假定其分布为高斯分布58第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 特征的抽取与选择实例Ø 通过统计方法改进特征空间类别的确定形成二统计特征分布59第十章 模式识别的理论与方法对地观测与数字地球科学中心统计模式识别n 特征的抽取与选择实例通过

34、统计方法改进特征空间类别的确定通过Mahalanobis距离确定新的特征空间¾¾60第十章模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 句法模式识别Ø 统计模式识别，通过量化的方法处理模式，最大限度地忽略了模式形状的内在结构关系Ø 句法模式识别，则力求通过准确地抓住这些不同模式类的内在结构关系来进行模式识别Ø 以形式语言为理论基础以图像描述语言形成样本的字符描述，通过句法分析方法完成识别61第十章 模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 句法模式识别的有关基本概念Ø 字符集9一个任意的有限符号集合

35、Ø 句子9在某一字符集上的句子是任一有限长度字符串，该字 取自于这一字符集上的字符组成如，给定一字符集0,1，它上面的有效句子集合为：0,1,00,01,10,.。Ø 语言9定义为某一字符集上的任一句子集合，该集合不一定 是有限的62第十章 模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 句法模式识别的有关基本概念Ø 语法9定义为一个四元组：G = (VN ,VT , P, S )l VN为一非终止符（变量）集合l VT为终止符（常量）集合； VN与VT为互不相交的两个集合l P为产生式或重写规则的集合，即终止符与非终止符之间的关系表达式l S为起始

36、符由语法G产生的语言L(G)是满足下面两个条件的句子的集合：1.2.每一字符串中只包含终止符每一字符串可由起始符S出发，按照P的规则推导形成63第十章模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 句法模式识别的有关基本概念Ø 定义了字符集、句子、语言，既明确了基本规则：字符组成句子，句子组成语言Ø 字符按照一定规则组成句子，进而组成语言语则形成的要素Ø 与任何一种自然语言一样，语法在形式语言中起中心作用Ø 句法模式识别中的各个环节，都是开n 介绍两种方法Ø 匹配形状数Ø 串匹配着语法的研究展64第十章 模式识别的理论与

37、方法对地观测与数字地球科学中心句法模式识别n 句法模式识别的有关基本概念Ø 例定义有向线段之间的运算：语法定义：VT= a, b, c, dVN= S, A1 , A2 , A3 , A4G = (VN ,VT , P, S )65第十章 模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 句法模式识别的有关基本概念Ø 例P： S ® A * AA ® A * c1213A3 ® d + A4A2 ® a + bA4 ® c + (» d )”表示有向线段d 的反向。其中“ » d该语法产生的语

38、言类是：d + c + (» d )*(a + b) * c它可描述的图形结构为：66第十章 模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 匹配形状数(1) 匹配形状数的基本思想形状数：描述一个对象的边界、结构时，所得到表达式或特征数；可看作为模式串、模式树的一种通用表述。通过比较两个对象边界的形状数的相似程度， 来匹配对象。例如：未知模式模式类67第十章 模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 匹配形状数(2) 基本概念a.两个区域边界的相似级别k的定义： 相同形状数的最大序号。如：当考虑用4码表示的封闭区域边界的形状数时，A和B具有相似级别k

39、，如果满足s4(A) = s4(B), s6(A) = s6(B), s8(A) = s8(B), sk(A) = sk(B),sk+2(A) ¹ sk+2(B), sk+4(A) ¹ sk+4(B), ，这里s表示形状数,下标表示序号。68第十章 模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 匹配形状数(2) 基本概念b.两个区域边界A和B形状数的距离D(A,B)， 定义为相似级别k的倒数 ：D(A,B) = 1 / k距离满足如下性质：D(A,B) ³ 0D(A,B) = 0 iff A=BD(A,C) £ maxD(A,B),D(B

40、,C)69第十章 模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 匹配形状数(3) 算法思想a. 用不同密度的网格划分边界区域，获得不同序数的形状数。b. 如果使用相似级别k，k越大说明越相似。c.如果使用相似距离D，D越小说明越相似d 可以利用相似进行判别70第十章 模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 匹配形状数（4）举例假设我们有一个形状F，想在另5个形状（A，B，C，D，E）中找到与其最相似的形状ABCDE71第十章 模式识别的理论与方法对地观测与数字地球科学中心F句法模式识别这个问题类似于有五个原型形状，想找出一个给定的尚不确定的形状的最佳匹配的

41、问题。这个问题可以利用相似进行可视化判别468ABCDEF ABCDEFBCDEFAA AA10DDCFCFBE12BBEE14D实例72第十章 模式识别的理论与方法对地观测与数字地球科学中心CF句法模式识别n 串匹配（1） 串匹配的基本思想比较两个边界的串编码的相似程度，来进行匹配（2） 三个基本概念设: 两个区域边界A和B已分别被编码为串a1a2an和b1b2bm。73第十章 模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 串匹配a. 两个串的匹配数M:当 ak= bk 时我们说发生了一个匹配。令M代表A、B中匹配的总数。b. 不匹配的符号数量Q：Q = max（|A|，|B|）- M这里|arg|是字符串的长度。当且仅当A和B 完全相同时，Q = 0。74第十章 模式识别的理论与方法对地观测与数字地球科学中心句法模式识别串匹配c. A和B相似度的简便衡量R:R = M/Q = M / max(|A|,|B|) - M因此，当A和B完全匹配时，R = ¥； 当A和B中任何字符都不匹配时，M = 0，R = 0。75第十章模式识别的理论与方法对地观测与数字地球科学中心句法模式识别n 串匹配（3）算法思想a. 由于匹配是逐字符进行的，b. 选择一个好的开始点，可以大大减少计算量。任何将两个串规则化为相