[科普中国]-结构模式识别

结构模式识别又称句法模式识别，它采用一些比较简单的子模式组成多级结构来描述 一个复杂模式，先将模式分为子模式.子模式又分为更简单的子模式，依次分解，直至在 某个研究水平上不再需要细分.最后一级最简单的子模式称为模式基元，识别模式基元比识别原模式要简单得多.

结构模式识别主要突出模式的结构信息，常用于以结构特征为主的目标识别中，例如指纹、染色体和汉字识别等.

图7 -1所示是一个模式多级分解的例子.

结构模式识别法将观察对象表达为一个由基元组成的句子，将模式类表达为由有限或无限个具有相似结构特性的模式组成的集合。基元构成模式所遵循的规则即为文法.或称句法.与统计模式识别类似，用已知类别的训练样本进行学习，产生该类或至少是这些样本的文法，这个学习和训练过程称为文法推断。

结构模式识别方法立足于分析模式的结构信息，至今比较成功的是句法结构模式识别方法。句法结构模式识别方法是美籍平人傅京孙教授提出的，它将物体 的结构视为基元（primitives)，采用规则或语法（rule，grammar)函数作为识别函数， 选择接受错误率作为准则函数，进行模式识别。在这个方法中，把模式的分层结构类比于语言中句子的构造，这样，就可利用形式语言学的理论来分析模式。句子由单词按文法规则构成，同样,模式由一些模式基元按一定的结构规则组合而成，分析模式如何由基元构成的规则就是结构分析的内容,这相当于在形式语言学中对一个句子作句法分析。句法结构模式识别就是检査代表这个模式的句子是否符合事先规定的某一类文法规则。如果符合，那么这个模式就属于这个文法所代表的那个模式类。除了分类信息外，句法结构模式识别方法还能给出模式的结构信息， 它为模式识别提供了用简单的、有限的模式基元和文法规则的有限集来描述一个复杂模式大（可能是无限的）集合的可能性。2

结构模式识别亦称句法模式识别.所谓句法，是描述语言规则的一种法则.一个完整的句 子一定由主语+谓语或主语+谓语+宾语（或表语）的基本结构构成；—种特定的语言，一定类型的句子，应有一定的结构顺序.无规则的任意组合，必然达不到正确的思想交流。形容词、副词、 冠词等可以与名词、动词构成“短语”，丰富句子要表达的思想内容。而这短语的构成也是有特定 规律的。如果用一个树状结构来描述一个句子，则如图9-13所示。

只有按照上述层状结构规则（或称为写作规则）才能组合成一定规则的句子，读者或听众才能正确理解你所表达的思想。3

自然句法规则的思想怎样用于模式识别呢？自然界的景物组合是千变万化的，但仔细分析某一对象的结构，也存在一些不变的规则。分析图9-14（a）所示的一座房子。它一定是由屋顶 和墙面构成的，组成屋顶的几何图像，可以是三角形、梯形、四边形、圆形等。组成墙平面的几何图像也是由矩形、平行四边形（透视效果）等构成，至少有一个墙面应该有门，而窗在高度上不低于门，等等。你还可以进一步提出一些用来刻画构成一栋房子的规则，如屋顶一定在墙面之上，且由墙面支承等。一栋房子的这些规则就像构成一个句子的句法规则一样.是不能改变的，如果将描述房子的规则（构成一栋房子的模式)存于计算机，若我们的任务是要在一张风景照照片上去识别有无房子，那么你可以按照照片上所有景物的外形匹配是否符合房子的模式（房子构成规则符合房子模式的就输出为“有房子”，否则，输出“无房子”。如果风景照片上有一棵树，如图 9-14 （b）所示，尽管顶部有三角形存在，也能寻找到一个支撑的矩形，但却找不到有“门”存在，这不符合一栋房子的结构规则，因而不会把它当成是一栋房子。3

可见，结构模式识别是以形式语言为理论基础的，它将一个复杂的模式分解成一系列更简单的模式（子模式），对子模式继续分解，最后分解成最简单的子模式（或称基元）.借助于一种形式语言对模式的结构进行描述，从而识别图像.模式、子模式、基元类似于英文句子的短语、单词、字母.这种识别方法类似语言的句法结构分析.因此称为句法模式识别.

句法模式识别系统框图如图9-15所示，它由识别和分析两部分组成。

分析部分包括基元的选择和句法推断。分析部分是用一些已知结构信息的图像作为训练样本.构造出一些句法规则。它类似于统计分类法中的“学习”过程。

识别部分包括预处理、分割描述、基元提取和结构分析。预处理主要包括编码、增强等系列操作。结构分析是用学习所得的句法规则对未知结构信息的图像所表示的句子进行句法分析。如果能够被抑制结构信息的句法分析出来.那么这个未知图像就有这种结构信息，否则，就不具 有这种结构。3

表1-1给出了统计模式识别和结构模式识别的异同比较。统计模式识别与结构模式识别最本质的区别有两点:①统计模式识别中的特征描述是定量描述，结 构模式识别的特征描述由子模式给出；②统计模式识别是以不同类别之间的特征量的不同来分类，结构模式识别采用文法，通过定义描述类结构的“语言"来完成模式识别的。从表1-1可以看出：统计模式识别和结构模式识别在不同方面，各自有着自己的优点，也存在着一定的不足。结构模式识别在描述与分类的过程中是基于领域知识的，传统的结构模式识别方法应用于新领域是受限的。因此，关于结构句法模式识别，目前最大的问题是没有提取数据结构子模式的一般化方法。 在模式识别的著作中，几乎很少提及原始数据结构特征选择问题，而大部分工作集中在描述特定领域的模式识别过程。例如，Friedman这样强调他的观点：原始特征选择，并基于此特征得到的模式，依赖于数据类型与相关的应用。Nadler支持该观点:一般根据设计者的经验、直觉与智慧提取特征。缺乏一般化的特征提取与描述方法，使结构模式识别研究者们陷入了困境，并阻碍了结构模式识别的进程与发展。为了克服这种限制，建立一种与领域知识无关的数据结构子模式提取方法势在必行。2

基于对大量文献的分析，研究者发现有两个重要的问题需要研究:①没有一种与领域知识无关的数据结构的特征提取方法;②将统计与句法相结合的混合分类器的研究还没有突破性成果。2

混合方法指的是将统计模式识别与结构模式识别相结合的一种统一的方法， 混合方法保留每一种模式识别方法的优势而避开了各自的不足。那么，在统计与结构的混合分类器设计过程中，基于统计知识来实现结构子模式的描述是一种可行的方法。如何将统计模式识别与结构模式识别结合,发挥各自特长，使统计模式识别与结构模式识别两种方法得以统一，进而完成混合分类器优化算法的设计与实现，将是一个新的问题。2

结构模式识别又称结构方法或语言学方法。结构模式识别理论是早期汉字识别研究的主要方法， 其思想是先把汉字图像划分为很多个基元组合，再用结构方法描述这些基元组合所代表的结构和关 系。通常抽取笔段或基本笔画作为基元，由这些基元及其组合关系可以精确地对汉字加以描述，最后利用形式语言及自动机理论进行文法推断，即识别。4

结构模式识别方法地主要优点是对字体变化的适应性强，区分相似字能力强，缺点是抗干扰能力差，从汉字图像中精确地抽取基元、轮廊.特征点比较困难，匹配过程复杂，若采用汉字轮廓结构信息作为特征，则需要进行松弛迭代匹配，耗时太长，而对于笔画较为模糊的汉字图像，抽取轮廓会遇到极大的麻烦。若采用抽取汉字图像中关键特征点来描述汉字，则特征点的抽取易受噪声点、 笔画的粘连与断裂等影响，总之，单纯采用结构模式识别方法的印刷体汉字识别系统的识别率是很低的。4

一个结构摸式识别系统可认为由三个主要部分组成，它们分别是预处理、模式描述、语法分析。该系统的简单框图如图9-29所示。

每一种经过预处理的模式，在模式描述阶段被表示成类语句结构（例如一个串、一个 图）。这一阶段的处理包括两部分：①模式分割；②基元抽取。为了将一个模式用若干子模 式来表示，我们应该对该模式予以分割，与此同时.抽取基元和基元间的关系。换言之，每一种经过预处理的模式，均按照预先制订的语法或合成操作规则，分割为子模式。进而，每一种子模式分割为一组基元。当然，若待识模式较简单，则也可以直接分割为基元。例如，借助于链接操作，每一种模式可用一串链接起来的基元表示。在语法分析阶段，系统应对已完成描述的模式作语法检査，以判定它是按何种语法结合成的，从而完成待识模式的分类。5

一般说来，识别的最简单的方式可能是“样板匹配"。用表示一种输入模式的基元串与 各种模型（也是用基元串表示的）相比较，按照选定的匹配准则，输入模式被划入匹配 “最好”的那一类。在这种“样板匹配”方式下，层次结构信息基本上不予考虑。上述“样板匹配”是一种方法，另一种识别方法是研究全部层次结构信息。此外还有若干介于这两种方法之间的研究方法。例如，设计一系列测试，以测定某些子模式（或某些基元）是否存在，或测定某些子模式的特定组合（或某些基元的特定组合）是否存在，测定的结果， 用作分类判决。注意，这里所说的一次测试，可以是一次样板匹配，也可以是对表达一个子模式的一棵子树的分析。要知道：识别方法的选取，通常取决于待识别的模式，若识别要求完整的模式描述，就要分析全部层次结构信息，反之就可用较简单的方法提高识别过程的效率.避免作完整的层次结构分析。5

一类模式的结构信息，要有一个文法来推述（实际上就是描述该类的结构，以与其他类相区别），这就需要文法推理，它能从给它的训练模式集中，归纳出一个文法，这类似于统计模式识别中用样本来训练判决函数。从图9-29可以看出，一类样品被送入语法推理机构，形成了该类的结构描述，作为语法分析机构入口之一的“样板”（如果按前面所说用样板匹配的话），或是层次结构分析的“文法”（如果用前述的层次结构分析）。其实，更广义的学习，还应包括基元的位置选定，这也是该推理机构的一种能力。5