结构模式识别

用模式的基本组成元素(基元)及其相互间的结构关系对模式进行描述和识别的方法

对于比较复杂的模式,把它作为一个整体进行分类是相当困难的,这就需要把它分解为若干较简单的子模式,而子模式又分解为若干基元,然后,通过对基元的识别,来识别子模式,最终达到识别模式的目标,这样对模式进行识别的方法,称为结构模式识别。

基本信息
结构模式识别又称句法模式识别,它采用一些比较简单的子模式组成多级结构来描述一个复杂模式,先将模式分为子模式,子模式又分为更简单的子模式,依次分解,直至在 某个研究水平上不再需要细分。最后一级最简单的子模式称为模式基元,识别模式基元比识别原模式要简单得多。
结构模式识别主要突出模式的结构信息,常用于以结构特征为主的目标识别中,例如指纹、染色体和汉字识别等。
图7-1所示是一个模式多级分解的例子。
结构模式识别法将观察对象表达为一个由基元组成的句子,将模式类表达为由有限或无限个具有相似结构特性的模式组成的集合。基元构成模式所遵循的规则即为文法,或称句法。与统计模式识别类似,用已知类别的训练样本进行学习,产生该类或至少是这些样本的文法,这个学习和训练过程称为文法推断。
结构模式识别方法立足于分析模式的结构信息,至今比较成功的是句法结构模式识别方法。句法结构模式识别方法是美籍平人傅京孙教授提出的,它将物体的结构视为基元(primitives),采用规则或语法(rule,grammar)函数作为识别函数,选择接受错误率作为准则函数,进行模式识别。在这个方法中,把模式的分层结构类比于语言中句子的构造,这样,就可利用形式语言学的理论来分析模式。句子由单词按文法规则构成,同样,模式由一些模式基元按一定的结构规则组合而成,分析模式如何由基元构成的规则就是结构分析的内容,这相当于在形式语言学中对一个句子作句法分析。句法结构模式识别就是检查代表这个模式的句子是否符合事先规定的某一类文法规则。如果符合,那么这个模式就属于这个文法所代表的那个模式类。除了分类信息外,句法结构模式识别方法还能给出模式的结构信息,它为模式识别提供了用简单的、有限的模式基元和文法规则的有限集来描述一个复杂模式大(可能是无限的)集合的可能性。
基本原理
结构模式识别亦称句法模式识别。所谓句法,是描述语言规则的一种法则。一个完整的句子一定由主语+谓语或主语+谓语+宾语(或表语)的基本结构构成;一种特定的语言,一定类型的句子,应有一定的结构顺序。无规则的任意组合,必然达不到正确的思想交流。形容词、副词、冠词等可以与名词、动词构成“短语”,丰富句子要表达的思想内容。而这短语的构成也是有特定规律的。如果用一个树状结构来描述一个句子,则如图9-13所示。
只有按照上述层状结构规则(或称为写作规则)才能组合成一定规则的句子,读者或听众才能正确理解你所表达的思想。
自然句法规则的思想怎样用于模式识别呢?自然界的景物组合是千变万化的,但仔细分析某一对象的结构,也存在一些不变的规则。分析图9-14(a)所示的一座房子。它一定是由屋顶和墙面构成的,组成屋顶的几何图像,可以是三角形、梯形、四边形、圆形等。组成墙平面的几何图像也是由矩形、平行四边形(透视效果)等构成,至少有一个墙面应该有门,而窗在高度上不低于门,等等。你还可以进一步提出一些用来刻画构成一栋房子的规则,如屋顶一定在墙面之上,且由墙面支承等。一栋房子的这些规则就像构成一个句子的句法规则一样,是不能改变的,如果将描述房子的规则(构成一栋房子的模式)存于计算机,若我们的任务是要在一张风景照照片上去识别有无房子,那么你可以按照照片上所有景物的外形匹配是否符合房子的模式(房子构成规则符合房子模式的就输出为“有房子”,否则,输出“无房子”)。如果风景照片上有一棵树,如图 9-14 (b)所示,尽管顶部有三角形存在,也能寻找到一个支撑的矩形,但却找不到有“门”存在,这不符合一栋房子的结构规则,因而不会把它当成是一栋房子。
可见,结构模式识别是以形式语言为理论基础的,它将一个复杂的模式分解成一系列更简单的模式(子模式),对子模式继续分解,最后分解成最简单的子模式(或称基元)。借助于一种形式语言对模式的结构进行描述,从而识别图像。模式、子模式、基元类似于英文句子的短语、单词、字母。这种识别方法类似语言的句法结构分析,因此称为句法模式识别。
句法模式识别系统框图如概述图所示,它由识别和分析两部分组成。
分析部分包括基元的选择和句法推断。分析部分是用一些已知结构信息的图像作为训练样本,构造出一些句法规则。它类似于统计分类法中的“学习”过程。
识别部分包括预处理、分割描述、基元提取和结构分析。预处理主要包括编码、增强等系列操作。结构分析是用学习所得的句法规则对未知结构信息的图像所表示的句子进行句法分析。如果能够被抑制结构信息的句法分析出来,那么这个未知图像就有这种结构信息,否则,就不具有这种结构。
与传统的区别
表1-1给出了统计模式识别和结构模式识别的异同比较。统计模式识别与结构模式识别最本质的区别有两点:①统计模式识别中的特征描述是定量描述,结构模式识别的特征描述由子模式给出;②统计模式识别是以不同类别之间的特征量的不同来分类,结构模式识别采用文法,通过定义描述类结构的“语言”来完成模式识别的。从表1-1可以看出:统计模式识别和结构模式识别在不同方面,各自有着自己的优点,也存在着一定的不足。结构模式识别在描述与分类的过程中是基于领域知识的,传统的结构模式识别方法应用于新领域是受限的。因此,关于结构句法模式识别,最大的问题是没有提取数据结构子模式的一般化方法。 在模式识别的著作中,几乎很少提及原始数据结构特征选择问题,而大部分工作集中在描述特定领域的模式识别过程。例如,Friedman这样强调他的观点:原始特征选择,并基于此特征得到的模式,依赖于数据类型与相关的应用。Nadler支持该观点:一般根据设计者的经验、直觉与智慧提取特征。缺乏一般化的特征提取与描述方法,使结构模式识别研究者们陷入了困境,并阻碍了结构模式识别的进程与发展。为了克服这种限制,建立一种与领域知识无关的数据结构子模式提取方法势在必行。
基于对大量文献的分析,研究者发现有两个重要的问题需要研究:①没有一种与领域知识无关的数据结构的特征提取方法;②将统计与句法相结合的混合分类器的研究还没有突破性成果。
混合方法指的是将统计模式识别与结构模式识别相结合的一种统一的方法,混合方法保留每一种模式识别方法的优势而避开了各自的不足。那么,在统计与结构的混合分类器设计过程中,基于统计知识来实现结构子模式的描述是一种可行的方法。如何将统计模式识别与结构模式识别结合,发挥各自特长,使统计模式识别与结构模式识别两种方法得以统一,进而完成混合分类器优化算法的设计与实现,将是一个新的问题。
优点与缺点
结构模式识别又称结构方法或语言学方法。结构模式识别理论是早期汉字识别研究的主要方法,其思想是先把汉字图像划分为很多个基元组合,再用结构方法描述这些基元组合所代表的结构和关系。通常抽取笔段或基本笔画作为基元,由这些基元及其组合关系可以精确地对汉字加以描述,最后利用形式语言及自动机理论进行文法推断,即识别。
结构模式识别方法地主要优点是对字体变化的适应性强,区分相似字能力强,缺点是抗干扰能力差,从汉字图像中精确地抽取基元、轮廊,特征点比较困难,匹配过程复杂,若采用汉字轮廓结构信息作为特征,则需要进行松弛迭代匹配,耗时太长,而对于笔画较为模糊的汉字图像,抽取轮廓会遇到极大的麻烦。若采用抽取汉字图像中关键特征点来描述汉字,则特征点的抽取易受噪声点、笔画的粘连与断裂等影响,总之,单纯采用结构模式识别方法的印刷体汉字识别系统的识别率是很低的。
识别系统
一个结构摸式识别系统可认为由三个主要部分组成,它们分别是预处理、模式描述、语法分析。该系统的简单框图如图9-29所示。
每一种经过预处理的模式,在模式描述阶段被表示成类语句结构(例如一个串、一个 图)。这一阶段的处理包括两部分:①模式分割;②基元抽取。为了将一个模式用若干子模式来表示,我们应该对该模式予以分割,与此同时,抽取基元和基元间的关系。换言之,每一种经过预处理的模式,均按照预先制订的语法或合成操作规则,分割为子模式。进而,每一种子模式分割为一组基元。当然,若待识模式较简单,则也可以直接分割为基元。例如,借助于链接操作,每一种模式可用一串链接起来的基元表示。在语法分析阶段,系统应对已完成描述的模式作语法检查,以判定它是按何种语法结合成的,从而完成待识模式的分类。
一般说来,识别的最简单的方式可能是“样板匹配”。用表示一种输入模式的基元串与 各种模型(也是用基元串表示的)相比较,按照选定的匹配准则,输入模式被划入匹配 “最好”的那一类。在这种“样板匹配”方式下,层次结构信息基本上不予考虑。上述“样板匹配”是一种方法,另一种识别方法是研究全部层次结构信息。此外还有若干介于这两种方法之间的研究方法。例如,设计一系列测试,以测定某些子模式(或某些基元)是否存在,或测定某些子模式的特定组合(或某些基元的特定组合)是否存在,测定的结果,用作分类判决。注意,这里所说的一次测试,可以是一次样板匹配,也可以是对表达一个子模式的一棵子树的分析。要知道:识别方法的选取,通常取决于待识别的模式,若识别要求完整的模式描述,就要分析全部层次结构信息,反之就可用较简单的方法提高识别过程的效率,避免作完整的层次结构分析。
一类模式的结构信息,要有一个文法来推述(实际上就是描述该类的结构,以与其他类相区别),这就需要文法推理,它能从给它的训练模式集中,归纳出一个文法,这类似于统计模式识别中用样本来训练判决函数。从图9-29可以看出,一类样品被送入语法推理机构,形成了该类的结构描述,作为语法分析机构入口之一的“样板”(如果按前面所说用样板匹配的话),或是层次结构分析的“文法”(如果用前述的层次结构分析)。其实,更广义的学习,还应包括基元的位置选定,这也是该推理机构的一种能力。
全国各地天气预报查询

上海市

  • 市辖区
  • 云南省

  • 临沧市
  • 云南省

  • 丽江市
  • 云南省

  • 保山市
  • 云南省

  • 大理白族自治州
  • 云南省

  • 德宏傣族景颇族自治州
  • 云南省

  • 怒江傈僳族自治州
  • 云南省

  • 文山壮族苗族自治州
  • 云南省

  • 昆明市
  • 云南省

  • 昭通市
  • 云南省

  • 普洱市
  • 云南省

  • 曲靖市
  • 云南省

  • 楚雄彝族自治州
  • 云南省

  • 玉溪市
  • 云南省

  • 红河哈尼族彝族自治州
  • 云南省

  • 西双版纳傣族自治州
  • 云南省

  • 迪庆藏族自治州
  • 内蒙古自治区

  • 乌兰察布市
  • 内蒙古自治区

  • 乌海市
  • 内蒙古自治区

  • 兴安盟
  • 内蒙古自治区

  • 包头市
  • 内蒙古自治区

  • 呼伦贝尔市
  • 内蒙古自治区

  • 呼和浩特市
  • 内蒙古自治区

  • 巴彦淖尔市
  • 内蒙古自治区

  • 赤峰市
  • 内蒙古自治区

  • 通辽市
  • 内蒙古自治区

  • 鄂尔多斯市
  • 内蒙古自治区

  • 锡林郭勒盟
  • 内蒙古自治区

  • 阿拉善盟
  • 北京市

  • 市辖区
  • 吉林省

  • 吉林市
  • 吉林省

  • 四平市
  • 吉林省

  • 延边朝鲜族自治州
  • 吉林省

  • 松原市
  • 吉林省

  • 白城市
  • 吉林省

  • 白山市
  • 吉林省

  • 辽源市
  • 吉林省

  • 通化市
  • 吉林省

  • 长春市
  • 四川省

  • 乐山市
  • 四川省

  • 内江市
  • 四川省

  • 凉山彝族自治州
  • 四川省

  • 南充市
  • 四川省

  • 宜宾市
  • 四川省

  • 巴中市
  • 四川省

  • 广元市
  • 四川省

  • 广安市
  • 四川省

  • 德阳市
  • 四川省

  • 成都市
  • 四川省

  • 攀枝花市
  • 四川省

  • 泸州市
  • 四川省

  • 甘孜藏族自治州
  • 四川省

  • 眉山市
  • 四川省

  • 绵阳市
  • 四川省

  • 自贡市
  • 四川省

  • 资阳市
  • 四川省

  • 达州市
  • 四川省

  • 遂宁市
  • 四川省

  • 阿坝藏族羌族自治州
  • 四川省

  • 雅安市
  • 天津市

  • 市辖区
  • 宁夏回族自治区

  • 中卫市
  • 宁夏回族自治区

  • 吴忠市
  • 宁夏回族自治区

  • 固原市
  • 宁夏回族自治区

  • 石嘴山市
  • 宁夏回族自治区

  • 银川市
  • 安徽省

  • 亳州市
  • 安徽省

  • 六安市
  • 安徽省

  • 合肥市
  • 安徽省

  • 安庆市
  • 安徽省

  • 宣城市
  • 安徽省

  • 宿州市
  • 安徽省

  • 池州市
  • 安徽省

  • 淮北市
  • 安徽省

  • 淮南市
  • 安徽省

  • 滁州市
  • 安徽省

  • 芜湖市
  • 安徽省

  • 蚌埠市
  • 安徽省

  • 铜陵市
  • 安徽省

  • 阜阳市
  • 安徽省

  • 马鞍山市
  • 安徽省

  • 黄山市
  • 山东省

  • 东营市
  • 山东省

  • 临沂市
  • 山东省

  • 威海市
  • 山东省

  • 德州市
  • 山东省

  • 日照市
  • 山东省

  • 枣庄市
  • 山东省

  • 泰安市
  • 山东省

  • 济南市
  • 山东省

  • 济宁市
  • 山东省

  • 淄博市
  • 山东省

  • 滨州市
  • 山东省

  • 潍坊市
  • 山东省

  • 烟台市
  • 山东省

  • 聊城市
  • 山东省

  • 菏泽市
  • 山东省

  • 青岛市
  • 山西省

  • 临汾市
  • 山西省

  • 吕梁市
  • 山西省

  • 大同市
  • 山西省

  • 太原市
  • 山西省

  • 忻州市
  • 山西省

  • 晋中市
  • 山西省

  • 晋城市
  • 山西省

  • 朔州市
  • 山西省

  • 运城市
  • 山西省

  • 长治市
  • 山西省

  • 阳泉市
  • 广东省

  • 东莞市
  • 广东省

  • 中山市
  • 广东省

  • 云浮市
  • 广东省

  • 佛山市
  • 广东省

  • 广州市
  • 广东省

  • 惠州市
  • 广东省

  • 揭阳市
  • 广东省

  • 梅州市
  • 广东省

  • 汕头市
  • 广东省

  • 汕尾市
  • 广东省

  • 江门市
  • 广东省

  • 河源市
  • 广东省

  • 深圳市
  • 广东省

  • 清远市
  • 广东省

  • 湛江市
  • 广东省

  • 潮州市
  • 广东省

  • 珠海市
  • 广东省

  • 肇庆市
  • 广东省

  • 茂名市
  • 广东省

  • 阳江市
  • 广东省

  • 韶关市
  • 广西壮族自治区

  • 北海市
  • 广西壮族自治区

  • 南宁市
  • 广西壮族自治区

  • 崇左市
  • 广西壮族自治区

  • 来宾市
  • 广西壮族自治区

  • 柳州市
  • 广西壮族自治区

  • 桂林市
  • 广西壮族自治区

  • 梧州市
  • 广西壮族自治区

  • 河池市
  • 广西壮族自治区

  • 玉林市
  • 广西壮族自治区

  • 百色市
  • 广西壮族自治区

  • 贵港市
  • 广西壮族自治区

  • 贺州市
  • 广西壮族自治区

  • 钦州市
  • 广西壮族自治区

  • 防城港市
  • 新疆维吾尔自治区

  • 乌鲁木齐市
  • 新疆维吾尔自治区

  • 伊犁哈萨克自治州
  • 新疆维吾尔自治区

  • 克孜勒苏柯尔克孜自治州
  • 新疆维吾尔自治区

  • 克拉玛依市
  • 新疆维吾尔自治区

  • 博尔塔拉蒙古自治州
  • 新疆维吾尔自治区

  • 吐鲁番市
  • 新疆维吾尔自治区

  • 和田地区
  • 新疆维吾尔自治区

  • 哈密市
  • 新疆维吾尔自治区

  • 喀什地区
  • 新疆维吾尔自治区

  • 塔城地区
  • 新疆维吾尔自治区

  • 巴音郭楞蒙古自治州
  • 新疆维吾尔自治区

  • 昌吉回族自治州
  • 新疆维吾尔自治区

  • 自治区直辖县级行政区划
  • 新疆维吾尔自治区

  • 阿克苏地区
  • 新疆维吾尔自治区

  • 阿勒泰地区
  • 江苏省

  • 南京市
  • 江苏省

  • 南通市
  • 江苏省

  • 宿迁市
  • 江苏省

  • 常州市
  • 江苏省

  • 徐州市
  • 江苏省

  • 扬州市
  • 江苏省

  • 无锡市
  • 江苏省

  • 泰州市
  • 江苏省

  • 淮安市
  • 江苏省

  • 盐城市
  • 江苏省

  • 苏州市
  • 江苏省

  • 连云港市
  • 江苏省

  • 镇江市
  • 江西省

  • 上饶市
  • 江西省

  • 九江市
  • 江西省

  • 南昌市
  • 江西省

  • 吉安市
  • 江西省

  • 宜春市
  • 江西省

  • 抚州市
  • 江西省

  • 新余市
  • 江西省

  • 景德镇市
  • 江西省

  • 萍乡市
  • 江西省

  • 赣州市
  • 江西省

  • 鹰潭市
  • 河北省

  • 保定市
  • 河北省

  • 唐山市
  • 河北省

  • 廊坊市
  • 河北省

  • 张家口市
  • 河北省

  • 承德市
  • 河北省

  • 沧州市
  • 河北省

  • 石家庄市
  • 河北省

  • 秦皇岛市
  • 河北省

  • 衡水市
  • 河北省

  • 邢台市
  • 河北省

  • 邯郸市
  • 河南省

  • 三门峡市
  • 河南省

  • 信阳市
  • 河南省

  • 南阳市
  • 河南省

  • 周口市
  • 河南省

  • 商丘市
  • 河南省

  • 安阳市
  • 河南省

  • 平顶山市
  • 河南省

  • 开封市
  • 河南省

  • 新乡市
  • 河南省

  • 洛阳市
  • 河南省

  • 漯河市
  • 河南省

  • 濮阳市
  • 河南省

  • 焦作市
  • 河南省

  • 省直辖县级行政区划
  • 河南省

  • 许昌市
  • 河南省

  • 郑州市
  • 河南省

  • 驻马店市
  • 河南省

  • 鹤壁市
  • 浙江省

  • 丽水市
  • 浙江省

  • 台州市
  • 浙江省

  • 嘉兴市
  • 浙江省

  • 宁波市
  • 浙江省

  • 杭州市
  • 浙江省

  • 温州市
  • 浙江省

  • 湖州市
  • 浙江省

  • 绍兴市
  • 浙江省

  • 舟山市
  • 浙江省

  • 衢州市
  • 浙江省

  • 金华市
  • 海南省

  • 三亚市
  • 海南省

  • 三沙市
  • 海南省

  • 儋州市
  • 海南省

  • 海口市
  • 海南省

  • 省直辖县级行政区划
  • 湖北省

  • 十堰市
  • 湖北省

  • 咸宁市
  • 湖北省

  • 孝感市
  • 湖北省

  • 宜昌市
  • 湖北省

  • 恩施土家族苗族自治州
  • 湖北省

  • 武汉市
  • 湖北省

  • 省直辖县级行政区划
  • 湖北省

  • 荆州市
  • 湖北省

  • 荆门市
  • 湖北省

  • 襄阳市
  • 湖北省

  • 鄂州市
  • 湖北省

  • 随州市
  • 湖北省

  • 黄冈市
  • 湖北省

  • 黄石市
  • 湖南省

  • 娄底市
  • 湖南省

  • 岳阳市
  • 湖南省

  • 常德市
  • 湖南省

  • 张家界市
  • 湖南省

  • 怀化市
  • 湖南省

  • 株洲市
  • 湖南省

  • 永州市
  • 湖南省

  • 湘潭市
  • 湖南省

  • 湘西土家族苗族自治州
  • 湖南省

  • 益阳市
  • 湖南省

  • 衡阳市
  • 湖南省

  • 邵阳市
  • 湖南省

  • 郴州市
  • 湖南省

  • 长沙市
  • 甘肃省

  • 临夏回族自治州
  • 甘肃省

  • 兰州市
  • 甘肃省

  • 嘉峪关市
  • 甘肃省

  • 天水市
  • 甘肃省

  • 定西市
  • 甘肃省

  • 平凉市
  • 甘肃省

  • 庆阳市
  • 甘肃省

  • 张掖市
  • 甘肃省

  • 武威市
  • 甘肃省

  • 甘南藏族自治州
  • 甘肃省

  • 白银市
  • 甘肃省

  • 酒泉市
  • 甘肃省

  • 金昌市
  • 甘肃省

  • 陇南市
  • 福建省

  • 三明市
  • 福建省

  • 南平市
  • 福建省

  • 厦门市
  • 福建省

  • 宁德市
  • 福建省

  • 泉州市
  • 福建省

  • 漳州市
  • 福建省

  • 福州市
  • 福建省

  • 莆田市
  • 福建省

  • 龙岩市
  • 西藏自治区

  • 山南市
  • 西藏自治区

  • 拉萨市
  • 西藏自治区

  • 日喀则市
  • 西藏自治区

  • 昌都市
  • 西藏自治区

  • 林芝市
  • 西藏自治区

  • 那曲市
  • 西藏自治区

  • 阿里地区
  • 贵州省

  • 六盘水市
  • 贵州省

  • 安顺市
  • 贵州省

  • 毕节市
  • 贵州省

  • 贵阳市
  • 贵州省

  • 遵义市
  • 贵州省

  • 铜仁市
  • 贵州省

  • 黔东南苗族侗族自治州
  • 贵州省

  • 黔南布依族苗族自治州
  • 贵州省

  • 黔西南布依族苗族自治州
  • 辽宁省

  • 丹东市
  • 辽宁省

  • 大连市
  • 辽宁省

  • 抚顺市
  • 辽宁省

  • 朝阳市
  • 辽宁省

  • 本溪市
  • 辽宁省

  • 沈阳市
  • 辽宁省

  • 盘锦市
  • 辽宁省

  • 营口市
  • 辽宁省

  • 葫芦岛市
  • 辽宁省

  • 辽阳市
  • 辽宁省

  • 铁岭市
  • 辽宁省

  • 锦州市
  • 辽宁省

  • 阜新市
  • 辽宁省

  • 鞍山市
  • 重庆市

  • 重庆市

  • 市辖区
  • 陕西省

  • 咸阳市
  • 陕西省

  • 商洛市
  • 陕西省

  • 安康市
  • 陕西省

  • 宝鸡市
  • 陕西省

  • 延安市
  • 陕西省

  • 榆林市
  • 陕西省

  • 汉中市
  • 陕西省

  • 渭南市
  • 陕西省

  • 西安市
  • 陕西省

  • 铜川市
  • 青海省

  • 果洛藏族自治州
  • 青海省

  • 海东市
  • 青海省

  • 海北藏族自治州
  • 青海省

  • 海南藏族自治州
  • 青海省

  • 海西蒙古族藏族自治州
  • 青海省

  • 玉树藏族自治州
  • 青海省

  • 西宁市
  • 青海省

  • 黄南藏族自治州
  • 黑龙江省

  • 七台河市
  • 黑龙江省

  • 伊春市
  • 黑龙江省

  • 佳木斯市
  • 黑龙江省

  • 双鸭山市
  • 黑龙江省

  • 哈尔滨市
  • 黑龙江省

  • 大兴安岭地区
  • 黑龙江省

  • 大庆市
  • 黑龙江省

  • 牡丹江市
  • 黑龙江省

  • 绥化市
  • 黑龙江省

  • 鸡西市
  • 黑龙江省

  • 鹤岗市
  • 黑龙江省

  • 黑河市
  • 黑龙江省

  • 齐齐哈尔市