北京交通大学图像处理-第10章-模式识别

数字图像处理学第10章模式识别的理论和方法（第五讲）5．

句法结构的分类与聚合的基本概念（１）最小距离分类最小距离分类是研究句子之间的距离，根据距离大小来分类。

(10—50)则指定y为类。假设有m个模式类。每一类有一个模板链，共有m个模板。当输入一个链y时，则可计算利汶施坦距离或加权利汶施坦距离。如果：（２）最近邻域分类对于m个模式类，每一类中有若干个模板链计算或，如果：

(10—51)则指定y为类。图10—23度量W的图示（３）句子到句子的聚合如果输入是一组样本，输出要x分成m个聚合，可按下述步骤进行：1)令，指定到类；2)将j增加1，对所有的i计算令，如果则指定到类，则对建立了一个新类别，m再增加1。这里t是某一阈值。3)重复第二步，直到中每一样本都被指定到一类为止。在利用距离的概念时，需要在一类中找到一个或少数几个基本样板作参考，如果这一要求作不到，就需要很多样板作参考，这就要存储许多句子，此时就不如用文法推断了。

6．

误差校正剖析（１）最小距离误差较正剖析程序这是一种算法。设是一个给定的语言，y是给定的句子。最小距离误差校正剖析的实质是在L(G)中寻找一个句子x，使它满足下述的最小距离准则。

(10—52)在这里x称为y的误差校正链。例如：对一个上下文无关语言的误差校正剖析可采用如下方法。如果有一个语言L(G)，现在有一条链y，y有两种可能性，一是y在L(G)中，另外是y在L(G)外面。第一种情况可能是由于噪声的原因使y在L(G)内部换成了另一个句子。第二种情况是原来的文法就不能产生y。在第二种情况下，可将原来的文法扩大，用改变产生式的方法将三种误差加进去，使扩大了的文法产生的语言包括受噪声影响的链，然后用扩大了的文法去剖析y，y可以被接受，而且可以知道最少用了几次误差转换。最后再把所用到的误差转换式去掉，就可得到L(G)中的链x，x就是y的误差校正链。

扩大的文法可用如下方法构成：假如给定一个上下文无关文法扩大的文法为则

1)

2)如果是P中的一个产生式，。于是把合到中去，其中是一个新的非终止符。

3)在中加入下列产生式：

对所有的

对所有的

所有

所有

在求链与语言之间的距离过程中，结构分析用扩大的文法设计。

（２）最近邻域结构识别如果有两个模式类和，分别用文法和加以描述。输入链y，如果

(10—53)则判定y是类。如果

(10—54)则判定y属于类。

若有m类，就应把每类文法都扩大，然后进行剖析。记下每类文法剖析所用的误差转换次数，这就表示输入y和每类之间的距离。最后检测与某类语言的距离最小，则y属于该类。除了决定y属于哪一类外，还可以知道y的误差校正链。

这种结构识别，首先要知道各类文法，有了原来的法G去产生扩大的文法，再进行剖析，所以叫ECP（ErrorCorrectingParsing）。分类器框图如图10—24所示（３）句法模式聚合步骤如果有n个样本，首先对推断一个文法，然后将和作误差校正剖析，计算和 的距离，如果距离较小，则将和分为一类，重新推断包括和的文法；如果距离较大，则将另立一类，并推断第二类文法。

这样对样本依次作下去，直到每个样本都被分到某一类中去。每一类中，每次有新的链加进来，就重新推断这一类文法。结果，n个样本被分到m类中，并形成m类文法。综上所述，聚合步骤可归纳如下：

1）从推断文法；

2）为构造一个误差校正剖析；

3）用确定是否与相似，如果和相似，则归入一类且从推断文法，如果和不相似，则从推断文法；

４）重复步骤（2），为构造或为构造；５）对新样本重复步骤（3），直到所有样本都考虑到为止。１）代替误差（４）随机误差校正剖析随机误差校正剖析是在误差产生式增加了概率值的剖析方法。按照误差转换的符号，与、、三类转换相关联的畸变概率可定义如下：其中，是用代换，且的概率。

３）抹去误差２）插入误差其中是在a前边插入终止符b的概率。其中是抹去的概率。

４）在一条链的末尾插入误差：其中，是在一条链的末端插入终止符a的概率。

令是a不发生误差的概率，可以认为它是在a上发生无误差转换的概率。

假定对于每一个终止符最多只能有一个误差存在，如果

(10—55)

且对于所有的则这种单误差模型上的畸变概率是一致的。下面可以通过一个例子来说明如何从一条链畸变为另一条链。畸变过程可由图10—25来说明。在图中，水平分支表示插入转换，垂直分支表示抹去转换，对角线分支表示代换转换或无误差转换。

(10—56)当然，x畸变到y可以有很多路径，可以说畸变概率是从B点到E点可能性最大的通路相联系的概率。图中，从点B到点E的每一条通路代表x畸变为y的一种方式。粗线表示的是如下通路，是前的一个插入，代换被抹去，代换，插入到链尾。如果把y分成，就可形成这种畸变，其中。这样就有图10—25用网络描述的随机畸变模型对于，符号a号畸变的概率可按下式计算（畸变概率表示为）如果

(10—57)把插入到一条链末尾的概率为

(10—58)

假定其中，则对于x畸变为y的概率如下其中

(10—59)其中，是y分成n+1段子链的一种划分。（５）最大似然误差校正剖析设是一个随机上下文无关语言，另外有一条噪声链y。可提出一个最大似然误差校正剖析算法，该算法在于找出一条链x，,使得

（10—60）

的计算可如前面介绍的方法进行。y要对中每个句子进行计算，然后指出畸变概率最大的情况，所以算法与ECP相似。

首先构成随机扩展文法。方法如下：输入一个随机上下文无关文法输出是一个随机扩展文法

(a)

,其中

(b)

，对于所有的

其步骤如下：1)2）3)如果是中的一个产生式，在中，在中，于是在中加入产生式，其中每个都是一个新的非终止符，。4）在中加入下列产生式

5)对于所有的，在中加入下列产生式(a)(b),对所有的;(c)(d),对所有的

假定y是x的一个误差畸变链，。用第三步中加到的产生式，可知其中，当且仅当，其中是中的第i个导出式的概率。首先用步骤4)的(b)，可进一步导出，其中。如果，是的一种划分，则步骤5)中的产生式产生，对所有的。步骤5)中的(a)、(b)、（c）、(d)分别对应于非误差转换、代换转换、抹去转换和允许多重插入的插入转换。于是，由产生的随机语言是

(10—61)其中r是从x导出y的相异转换序列的数目。是与第i个序列相联系的概率，。于是，贝叶斯决策规则为

如果有两个句法模式和，假设x在中的概率为 是已知的，如果考虑贝叶斯分类，运用贝叶斯规则可知x在第j类的后验概率为

=1,2(10—62)

(10—63)有时候往往会出现两个文法产生同一个句子的情况，如C1

类产生英文字母B，C2

类产生数字8，在有噪声干扰时，B和8可能在两类交叠处，也可能在两类之外。对于交叠处的可以用随机文法计算概率，用最大似然分类器解决。在两类之外可用最大似然误差校正剖析来解决。10.3.4文法推断

在句法模式识别中，有两个问题比较困难，一是噪声和干扰，另一个就是文法推断。文法推断是在解决了被研究模式的基元提取问题后，研究如何构成能正确描述这类模式的文法。这实际上是句法结构的学习问题。即从句子中学习文法，。由于模式可分别用链、树、图来表示，所以就有链文法推断，树文法推断以及图文法推断。文法推断课题主要涉及推断一个未知文法的句法规则所有的方法，推断的依据是产生的语言中句子或链的一个有限集合，也可能还有的补集中的链的有限集合。推断出的文法是一种规则，它描述中的给定有限集合，并预测给定集以外的链，这些链与给定集在某种意义上具有同样的性质。文法推断的方框图如图10—27所示。

1.有限状态文法推断

有限状态文法可用下述方法实现：输入k个样本，。其中，中不同的终止符}。对个样本中的一条链寻找其产生式。因为正规文法的产生式只有两种形式，即及。

:所以对于每一条链，其产生式规则为:上述方法可通过一个例子来说明。例:所以这个文法共有9个非终止符，2个终止符，12个产生式。

2.上下文无关文法的推断

在实用中，用有限数目的句子来推断文法一般总能用正规文法产生这些句子。但是有时会很大。如果采用上下文无关文法来推断，的数目会大大减小，因此，实现起来自动机的状态也会大大减少。上下文无关文法的推断大致有两种方法，一种方法是PumpingLemma方法，另一种方法是采用具有结构性样本的推断法。上下文无关的语言有一个特性，即如果一个句子可以分成5段UVWXY，这个句子在内，那么形如的句子也在内（UVWXY定理）。例如，用人机对话的方式，逐个询问机器是否在 内，如果机器回答，则检验 是否在内，如果它们都在内，则得到产生式这种方法的缺点是需要大量的外界信息，中的句子也较多。采用具有结构特性的样本的方法是不仅要知道句子，还要知道句子的结构。为说明方便起见，在此结构用括弧来表示。

例如：，结构信息为。结构树如图10—28所示。产生这个句子的文法的产生式为它的结构信息为求出产生的文法的产生式这种方法需要知道句子的结构，这对于模式识别来说是可以做到的。用这个方法推断出的文法，由于基本模式数目很少，可能得到的文法质量不高，但这个缺点可用ECP来补偿。

3.图文法推断

定义正样本集和负样本集，而。

如果和

图文法规则如下：拱型→

分别是图10—29所示的景物，希望有个文法产生这个图形。此图的关系图如图10—30所示。

第一个样本进来，只有A在B、C上，B在C的左边；第二个样本进来，B与C不能靠得太近；第三个样本进来，A一定在B、C上而不能在下面；第四个样本……等等。按上述步骤，从根向下不断加入新的关系就可推断出图文法。

4.树文法推断

链可以看成是只有一枝的树，而树是多枝的链。如果只对于树支全从根开始的这种特殊形状的树，则可直接把链的方法搬过来用。

5.上下文敏感文法推断

对于上下文敏感的文法(即上下文有关的文法)还没有推断办法。对于这类问题可用两种办法解决，一种是上下文无关程序文法，另一种是用属性文法。

6.关于属性文法

在属性文法中，每一个基元都由两部分组成，基元为()。其中b表示名字，表示属性或语义信息，这是识别基元的根据。在使用产生式时，要考虑属性之间的关系。例如：图1031的树图，子模式为()，B的属性由a,b,c的属性得到。。式中的可能是简单的函数，也可能是复杂的运算式。上例中的产生式规则为，属性规则为。

属性文法的优点在于当每个模式结构一样只是大小不同的情况，可利用属性这一信息将二者分开。属性往往是识别基元时所需要的特征量。属性并不限于一个量，可以是一组参量。属性的计算顺序是从基元属性计算起，然后是子模式属性，再往上计算模式属性。例如是上下文无关语言，基元如图10—32(a)所示，其所描述的图形如图10—32(b)所