结构模式识别

用模式的基本组成元素（基元）及其相互间的结构关系对模式进行描述和识别的方法结构模式识别01基本信息与传统的区别识别系统基本原理优点与缺点目录03050204基本信息对于比较复杂的模式，把它作为一个整体进行分类是相当困难的，这就需要把它分解为若干较简单的子模式，而子模式又分解为若干基元，然后，通过对基元的识别，来识别子模式，最终达到识别模式的目标，这样对模式进行识别的方法，称为结构模式识别。简言之，结构模式识别是用模式的基本组成元素（基元）及其相互间的结构关系对模式进行描述和识别的方法。在多数情况下，可以有效地用形式语言理论中的文法表示模式的结构信息，因此也常称为句法模式识别。一个结构摸式识别系统可认为由三个主要部分组成，它们分别是预处理、模式描述、语法分析。基本信息基本信息结构模式识别又称句法模式识别，它采用一些比较简单的子模式组成多级结构来描述一个复杂模式，先将模式分为子模式，子模式又分为更简单的子模式，依次分解，直至在某个研究水平上不再需要细分。最后一级最简单的子模式称为模式基元，识别模式基元比识别原模式要简单得多。结构模式识别主要突出模式的结构信息，常用于以结构特征为主的目标识别中，例如指纹、染色体和汉字识别等。图7-1所示是一个模式多级分解的例子。图7-1结构模式识别法将观察对象表达为一个由基元组成的句子，将模式类表达为由有限或无限个具有相似结构特性的模式组成的集合。基元构成模式所遵循的规则即为文法，或称句法。与统计模式识别类似，用已知类别的训练样本进行学习，产生该类或至少是这些样本的文法，这个学习和训练过程称为文法推断。结构模式识别方法立足于分析模式的结构信息，至今比较成功的是句法结构模式识别方法。句法结构模式识别方法是美籍平人傅京孙教授提出的，它将物体的结构视为基元（primitives），采用规则或语法（rule，grammar）函数作为识别函数，选择接受错误率作为准则函数，进行模式识别。基本原理基本原理图9-13结构模式识别亦称句法模式识别。所谓句法，是描述语言规则的一种法则。一个完整的句子一定由主语+谓语或主语+谓语+宾语（或表语）的基本结构构成；一种特定的语言，一定类型的句子，应有一定的结构顺序。无规则的任意组合，必然达不到正确的思想交流。形容词、副词、冠词等可以与名词、动词构成“短语”，丰富句子要表达的思想内容。而这短语的构成也是有特定规律的。如果用一个树状结构来描述一个句子，则如图9-13所示。只有按照上述层状结构规则（或称为写作规则）才能组合成一定规则的句子，读者或听众才能正确理解你所表达的思想。

图9-14自然句法规则的思想怎样用于模式识别呢？自然界的景物组合是千变万化的，但仔细分析某一对象的结构，也存在一些不变的规则。分析图9-14（a）所示的一座房子。它一定是由屋顶和墙面构成的，组成屋顶的几何图像，可以是三角形、梯形、四边形、圆形等。组成墙平面的几何图像也是由矩形、平行四边形（透视效果）等构成，至少有一个墙面应该有门，而窗在高度上不低于门，等等。你还可以进一步提出一些用来刻画构成一栋房子的规则，如屋顶一定在墙面之上，且由墙面支承等。一栋房子的这些规则就像构成一个句子的句法规则一样，是不能改变的，如果将描述房子的规则（构成一栋房子的模式）存于计算机，若我们的任务是要在一张风景照照片上去识别有无房子，那么你可以按照照片上所有景物的外形匹配是否符合房子的模式（房子构成规则符合房子模式的就输出为“有房子”，否则，输出“无房子”）。与传统的区别与传统的区别表1-1给出了统计模式识别和结构模式识别的异同比较。统计模式识别与结构模式识别最本质的区别有两点：①统计模式识别中的特征描述是定量描述，结构模式识别的特征描述由子模式给出；②统计模式识别是以不同类别之间的特征量的不同来分类，结构模式识别采用文法，通过定义描述类结构的“语言”来完成模式识别的。从表1-1可以看出：统计模式识别和结构模式识别在不同方面，各自有着自己的优点，也存在着一定的不足。结构模式识别在描述与分类的过程中是基于领域知识的，传统的结构模式识别方法应用于新领域是受限的。因此，关于结构句法模式识别，最大的问题是没有提取数据结构子模式的一般化方法。在模式识别的著作中，几乎很少提及原始数据结构特征选择问题，而大部分工作集中在描述特定领域的模式识别过程。例如，Friedman这样强调他的观点：原始特征选择，并基于此特征得到的模式，依赖于数据类型与相关的应用。Nadler支持该观点：一般根据设计者的经验、直觉与智慧提取特征。缺乏一般化的特征提取与描述方法，使结构模式识别研究者们陷入了困境，并阻碍了结构模式识别的进程与发展。为了克服这种限制，建立一种与领域知识无关的数据结构子模式提取方法势在必行。

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

混合方法指的是将统计模式识别与结构模式识别相结合的一种统一的方法，混合方法保留每一种模式识别方法的优势而避开了各自的不足。那么，在统计与结构的混合分类器设计过程中，基于统计知识来实现结构子模式的描述是一种可行的方法。优点与缺点优点与缺点结构模式识别又称结构方法或语言学方法。结构模式识别理论是早期汉字识别研究的主要方法，其思想是先把汉字图像划分为很多个基元组合，再用结构方法描述这些基元组合所代表的结构和关系。通常抽取笔段或基本笔画作为基元，由这些基元及其组合关系可以精确地对汉字加以描述，最后利用形式语言及自动机理论进行文法推断，即识别。

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

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

一般说来，识别的最简单的方式可能是“样板匹配”。用表示一种输入模式的基元串与各种模型（也是用基元串表示的）相比较，按照选定的匹配准则，输入模式被划入匹配“最好”的那一类。在这种“样板匹配”方式下，层次结构信息基本上不予考虑。上述“样板匹配”是一种方法，另一种