机器感知与模式识别：基于多Agent系统的脱机手写体汉字识别

第4卷第5期 智能系统学报 VoL.4 No.5 2009年10月 CAAI Transactions on Intelligent Systems 0ct.2009 doi:10.3969/j.i8sn.16734785.2009.05.003 基于多Agent系统的脱机手写体汉字识别 马少平12,3，金奕江123 (1.清华大学计算机科学与技术系，北京100084；2.清华大学智能技术与系统国家重点实验室，北京100084：3.清 华大学清华信息科学与技术国家实验室（筹），北京100084) 摘要：由于脱机手写体汉字的多样性和随意性，识别起来具有很大的难度，依靠单一的特征很难实现高准确率的 识别.引人多Agent的概念，将多种知识统一于多Agent系统之中，给出了一个面向脱机手写体汉字识别的多Aget 类市场模型，提出了一种模糊综合方法和辩论协商规侧，实现了一个基于多Agt系统的脱机手写体汉字识别系统. 初步测试结果显示出系统的有效性。 关键词：汉字识别；多Aget系统；类市场模型；模糊综合；辩论协商规侧 中图分类号：T391.4文献标识码：A文章编号：16734785(2009)05039808 Offline recognition of hand-written Chinese characters based on a multi-Agent system MA Shao-ping,JIN Yi-jiang (1.Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China;2.State Key Lab of Intelligent Technology and Systems,Tsinghua University,Beijing 100084,China;3.Tsinghua National Laboratory of Information Science and Technology,Tsinghua University,Beijing 100084,China) Abstract:Due to the diversity and randomness of Chinese characters,it is difficult for offline hand-written Chinese character recognition to perform well when based solely on analysis of a single feature.In order to solve this prob- lem,a multi-Agent based recognition method was proposed.It merges a variety of knowledge into a market-like model.A comprehensive approach using fuzzy rules to provide consultation and debate rules between Agents was al- so incorporated.With this proposed method,a multi-Agent offline hand-written Chinese character recognition sys- tem was constructed.Preliminary experimental results showed the effectiveness of this system. Keywords:hand-written chinese character;multi-Agent system;market-like model;fuzzy synthetic;debate-nego- tiation rules 从1966年BM公司首次发表关于汉字识别的 法3)，以弥补单一特征、单一分类器的不足.在印刷 研究文章以来，汉字识别的研究已经有40多年的历 体汉字和手写体数字识别中，已成功地开发出系统 史.在这期间，无论是在汉字特征的描述山、抽取方 集成识别系统，取得了良好的效果，不仅降低了系统 法，还是在分类器的构造方法上，均取得了很大进 的误识率，也使得系统的整体识别率达到了任何参 展，尤其是在印刷体汉字识别和联机手写体汉字识 与集成的单一系统所达不到的水平[45]」 别方面，已开发出一批实用的系统[.同时人们也 在现有的系统集成方法中，几乎无一例外地是 清醒地认识到，任何特征和分类器都有其局限性，使 多种识别器间的集成，这种方法在现有条件下，对脱 用单一的特征、单一的分类方法，很难使识别性能在 机手写体汉字识别来说存在较大的困难，以及不全 现有的基础之上再上一个新的台阶.为此，人们又提 面性和不合理性.在多识别器集成系统中，无论是采 出了综合使用不同的特征和分类器的系统集成方 用简单的投票表决方法，还是用各种不同的基于概 率的决策模型，均要求各分类器及所用特征间具有 收稿日期：200909-21. 独立性，这样才能使得决策结果具有公正性.而目前 基金项目：国家自然科学基金创新研究群体科学基金资助项目 (60621062). 较为有效的脱机手写体汉字识别方法中，虽然各有 通信作者：马少平.E-mail:msp@tsinghua.ed血.cm. 特色，但几乎全部是以方向线素特征[]为基础的

第5期 马少平，等：基于多Aget系统的脱机手写体汉字识别 ·399· 不能满足多识别器合成的独立性要求。 求其他Agent的帮助.这样一来，Agent在担当生产 手写汉字随意性较大，单靠特征很难正确地识 者的同时，有时也充当消费者的角色。 别手写相近字，在印刷体中一些明显的差别，对于手 结果 用户 处理结果与请求 管理者 写体来说也变地不那么可靠了.因此，单纯用多识别 任务 器集成来识别手写汉字，既不全面，也不尽合理，应 使用除特征以外的更多的知识，进行综合判断.而在 Agent 1 环 实际应用中，多是以文本为识别单位，这为综合利用 信息 Agent 2 多种知识提供了条件.后处理方法就是在这种情况 下应运而生的]. Agent 以往脱机手写体汉字识别模型的一个重要特点 是其串行性，后处理引起的任何错误都将被保存下 来，相对于识别来说，后处理具有权威性.而后处理 图1汉字识别类市场模型 的知识不可能是完备的，由于其权威地位，因此知识 Fig.1 A market-like model for Chinese character recognition 不足造成的错误得不到更正的机会.一种合理的想 系统的基本工作过程如下： 法是各种求解方法，无论是识别、后处理，还是其他 1)用户向系统提交任务，任务中包括识别对象 方法，均处于一个平等的地位.不同的方法之间，通 和要求等信息； 过协商、交流，达到总体上的和谐和最好的识别效 2)管理者根据用户提交的任务，按用户的需求 果.多Agent系统正好具备这方面的特点[).本文 规划任务求解，形成招标信息公布于环境中； 引人Agent的概念，针对手写体汉字识别的特点，给 3)Agent感知到招标信息后，根据自己的求解 出了一个基于多Agent系统的汉字识别模型，提出 能力及资源消耗，产生一种或几种投标方案，形成标 了一种模糊综合评判方法，以及各Agent间的协商 书，送交管理者； 辩论方法 4)管理者根据投标情况选择中标者，并规划任 务求解，通过环境将中标信息分发给相应的Aget; 1基于多Agent的汉字识别类市场模型 5)Agent在得到中标信息后，按中标合同组织 类市场模型是多Agent系统中的一个重要模 问题的求解，将结果送交管理者，在结果中也可能包 型，受到学者们越来越多的重视.根据计算生态学的 含新的任务请求； 研究发现，在所有生态系统中，市场结构最为完善， 6)管理者对各个Agent的求解结果进行分析， 具有最高的智能.根据手写体汉字识别的特点，借用 若有新的任务请求，则组织招标，重复3~5)，否则 市场模型的概念，给出基于多Agent系统的手写体 将结果进行组织后公布在环境中； 汉字识别模型如图1所示.其中环境用于存放各种 7)在所有任务求解完成之后，仲裁Agent对识 任务请求、处理所需的原始信息、处理的中间结果及 别结果进行仲裁，当存在矛盾冲突时，由管理者组织 其各Agent间的通讯信息等.管理者负责组织和规 相关Agent进行辩论协商，直到达成一致解或最大 划任务求解以及环境中的信息管理.Agent从环境 可能解； 中感知信息，利用自己的能力对其进行处理，并将处 8)最终由管理者将识别结果输出给用户， 理结果通过管理者有组织地对环境进行更新.在该 2模型的详细说明 模型中，用户相当于消费者，向系统提出任务请求并 接收系统的处理结果.管理者起中间商的作用，对欲 2.1任务 求解的任务组织招标，规划中标者的任务求解，当出 任务有2种类型，一种是由用户提交的任务，称 现矛盾冲突时，组织相关的Aget进行辩论和协商， 为用户任务，它指定了系统的最终求解目标另一种 以寻求一个可以接受的一致解.Agent相当于生产 是由系统内部产生的任务，称为系统任务.管理者根 者，时刻监视环境中的信息，一旦发现自己可以胜任 据用户任务的不同目标，规划求解路径，路径中的每 的任务，则根据自己的能力进行投标，一旦中标后， 一个求解目标均产生至少一个系统任务.当Aget 立即进行求解.除了用户提供的任务请求外，每个 在求解过程中请求其他的Agent支援或需要与别的 Agent也可以根据自己的需求提出任务请求，以寻 Aget对话时，生成系统任务.当发生矛盾冲突需要

·400 智能系统学报 第4卷 进行辩论协商时，管理者也生成系统任务 的存储格式为数组.最基本的可操作单位为特征分 一个任务具有如下的格式： 量.一个汉字样本，可以对应多组特征. (<任务名><对象><类型><目标> 4)单字层.识别器基于特征的识别结果，连同其 [<领域>]). 候选字、识别信度存放于该层.基本的存储格式为一 其中，<任务名>是任务标识，由系统自动分 结构，该结构含有2个关键域，一个域为按信度大小 配，任务名可以惟一地表示出一个任务；<对象>给 顺序存放的候选字，另一个域为候选字所对应的信 出该任务的操作对象，如一个切分任务，其对象可以 度，2个域均为数组.该层最基本可操作单位为字 是一个TF或BMP文件，而一个识别任务，其对象 5)词汇层.利用词汇知识对单字识别结果（包 则可以是已切分好的汉字图像点阵等；<类型>指 括候选)进行评判，评判结果存放于该层.基本的存 定了<对象>的类型，如TF_FLE、BMP_FLE等； 储格式为含有2个关键域的结构，一个域记录候选 <目标>给出该任务对给定对象最终求解到什么程 字的构词情况，另一个域记录评判信度.该层的最基 度，如对于一个T亚文件对象，是只给出切分结果 本可操作单位为词，包括单字词和多字词. (因为用户可能并不要求识别)就行了呢，还是要对 6)短语层.对各候选可能形成的短语或句子， 其进行识别，如果是识别是否进行后处理等等；<领 利用汉语的上下文知识进行评判，评判结果存放于 域>是一个可选参数，如果需要或者可能的话，它指 该层.基本的存储格式是一个复杂的多级链表结构， 定出<对象>所在的领域.领域既可以标识出识别 实际上表达的是一个搜索图.该层的基本可操作单 对象是汉字、数字还是英文等信息，又可以给出待处 位为短语或句子 理的对象属于社会科学范围，还是属于计算机科学 7)结果层.该层记录系统最终的识别结果，基 范围等信息，供与领域有关的Agent使用， 本的存储格式同单字层一样为一结构，该结构含有 2.2环境 2个关键域，一个域为按综合评判信度大小顺序存 环境由一个公告牌和一个分层结构的黑板组 放的候选字，另一个域为候选字所对应的信度，2个 成.用户提供的原始信息、招标投标信息、各Aget 域均为数组. 的处理结果及相互间的交互信息等均存放于环境之 2.3管理者 中.环境对于每个Agent是共享的. 管理者可以看作是一个特殊的Agent,它具有 公告牌是各种消息的集合.管理者与Agent之 多重身份.其一，管理者是一个中间商，它对用户或 间、Agent与Agent之间的各种通讯与交互均通过公 其他Agent提交的任务，规划求解路径，分解为若干 告牌进行 个子任务，发布于公告牌上，组织招标.在接收到A 黑板是问题的解空间以层次结构方式组织起来 get的标书后，根据任务的具体要求，从求解精度、 的全局数据库，是所有公有信息的集合，Agent使用 时间消耗和资源消耗等几个方面选择中标者.对于 的所有数据均存放于黑板之中.一个黑板被划分为 同一个求解目标，中标者可以是一个，也可以是多 以下7个层次： 个.为发挥更多的Agent的作用，在时间允许的情况 1)版面层.这是由扫描仪扫描汉字样张得到的 下，管理者尽可能多地选择中标者.其二，管理者实 最原始黑白二值图像，存储格式为F文件格式或 现对环境的管理.所有的任务请求，均通过管理者张 BMP文件格式.最基本的可操作单位为图像的 贴于公告牌上，所有处理结果，也要经过管理者组织 “点”.该层内容简称为版面， 之后放置于环境之中.其三，管理者是一个调节人， 2)样本层.对版面进行分析后，经行切分、字切 当发生矛盾冲突时，管理者负责组织各相关Agent 分后，得到单个汉字的点阵及其结构属性信息（如 间的辩论与协调，听取各辩论者的意见，使得在各 上下结构、左右结构、内外结构等)存放于该层.对 Aget间最终达成一个一致的意见或可能性最大的 汉字点阵进行噪声处理、光滑处理、规格化等预处理 结果 的结果也放于该层之中.汉字点阵基本的存储格式 2.4 Agent 为二维矩阵，最基本的可操作单位为“点”.该层内 Agent由感知器、发送器、任务分配器、知识库、 容简称为样本， 方法集和局部黑板6部分组成，其一般结构如图2 3)特征层.对汉字样本抽取出的识别特征存放 所示.其中感知器用于感知环境中的信息，它时刻监 于特征层，一个汉字的特征为一个N维向量，基本 视着环境的变化，随时捕捉与自己相关的信息.任务

第5期 马少平，等：基于多Aget系统的脱机手写体汉字识别 ·401· 分配器根据感知到的信息，分发给适合的方法.方法 局部黑板是Agent的私有数据库，用于存储求解问 集是该Aget能力的体现，与知识库相配合，实现对 题所需的各种数据、中间结果及最终结果等.发送器 问题的求解.方法集至少由3部分内容组成：投标方 将求解结果或任务请求发送给系统的管理者，以实 法、问题求解方法和辩论协商方法.方法集和知识库 现与环境或其他Agent的交互. 构成了Agent的大脑，是Agent最重要的组成部分， 环境 感知器 局 任务分配器 部 黑 !识市 管理者 发送器 板 方法集 Agent 图2 Agent的一般结构 Fig.2 General structure for recognition Agent Agent根据其功能的不同，可以分为以下几类： 别结果的手段。 1)扫描Aget:启动扫描仪，获得待识别文字的 各类Agent与环境信息层的关系如图3所示， 图像信息. 结果层 校对 2)切分Agent:对版面进行分析，将版面中的每 知层 个汉字从图像中分离出来，得到待识字样本；必要 词层 后处理 时，切分Agent也可以给出样本的结构信息，如左右 单字层 识别评价乳处理 结构、上下结构等 特征层 识别 3)预处理Agent:消除样本中存在的噪声，对汉 样木尽 预处理特抽取 字笔画边缘进行平滑处理，然后再对汉字样本进行 版层 6切分 非线性整形变换及大小归一化处理。 6扫描 4)特征抽取Agent:从归一化后的汉字样本中 抽取识别用特征 图3知识源与信息层的关系 5)识别Agent:对于不同的特征，采用不同的方 Fig.3 Relationship between knowledge sources and in- 法对待识样本进行分类，得到候选字及其识别参数。 formation layers 6)识别评价Agent:应用单字识别系统的误识 2.5仲裁 模型及识别参数对候选字进行评价，得到候选字的 对于脱机手写体汉字识别来说，各Agent的处 识别信度. 理结果很难做到完全一致，当出现任何不一致时，系 7)词汇处理Aget:利用词汇知识对前后相关联的 统就进行辩论协商，系统开销太大.一种可行的办法 候选字进行构词分析，提出假设，并给出信度评价. 就是对结果进行模糊综合评判，当评判结果达到一 8)后处理Agent:对各候选可能形成的短语或 定的可信度时，就认为该结果是一致的，否则被认为 句子提出假设，利用汉语语言模型进行分析，给出信 是有矛盾冲突的.只有在模糊评判意义下发生冲突 度评价 时才进行辩论协商。 9)仲裁Agent:对不同的Agent给出的结果，用 2.6协商与辩论 某种评判方法进行综合评判，一致的部分确定下来， 协商是多Agent系统中关键的组成部分12].若 产生矛盾的部分，送交管理者组织辩论. 干个Aget简单地堆放在一起，永远是几个独立的 10)自动校对Aget:对识别结果中与语言模型 个体，只有相互协调合作，才能使其综合能力具有质 不相符的部分提出警告，提示给用户。 的变化.辩论是协商的一种方式，通过辩论，使得各 11)人工校对Agent:提供一种便于用户校对识 Aget间取得一致的意见，也就是说，得到一个对于

·402 智能系统学报 第4卷 待识别样本可能性最大的识别结果. 在P部的特征进行识别时的识别器评价指标， 辩论是一个说理的过程，每个参与辩论的A 规则5如果P1是相对于Agent1的C1、C2间 gent,从自己的立场出发，重新审视所讨论的问题， 的最大差异部分，P2是相对于Agent2的C1、C2间的 提出自己的理由和根据.通过协商，或者坚持自己的 最大差异部分，P1≠P2,且当用P1替换P2时Aget2 原有观点，努力去说服其他的Agent同意自己的意 支持Agent1的结论；则有理由相信Agentl的结论是 见；或者被其他的Agent说服，改变自己的立场，支 正确的. 持说服者的意见.下面给出一些辩论规则. 该规则反映了Agent在辩论中的退让， 规则1如果C1是特定结构汉字，而C,是非特定 规则6如果已经确认0为专有名词的一员， 结构汉字，当当前待识别的汉字0与C1具有相同的特 且选择C1后，专有名词词典中含有该名词；则有理 定结构时；则有理由相信O为C1,而非C2 由相信0为C· 其中特定结构汉字指的是具有左右结构，或者上 专有名词指人名、地名、公司名等，在一个句子 下结构，或者内外结构的汉字 中，具有明确上下文特征的专有名词可以通过判别 C1、C2的结构信息存放于Agent的知识库中， 法则判定 而O的结构信息在切分时获得，或者通过求解笔画 规则7如果已经确认0为专有名词的一员， 的连通域获得. 且选择C1或C2后，在专有名词词典中均不含有该 注意该规则只规定了当O与C,具有相同的特 名词；则识别类Agent的结果更为可靠. 定结构时才确信O为C1,而0为非特定结构时，并 规则8如果识别Agent对C,和C2的可信度 不能确信0为C2·这是因为在手写体汉字中，习惯 之差小于给定值，而且C,的组句能力与C2的组句 性的连笔往往会破坏汉字的结构特征， 能力之差大于给定值；则有理由相信O为C 规则2如果C1与C2的复杂度差大于给定值， 其中C的组句能力定义为：当0固定为C时，经 且0与C,的复杂度差小于给定值；则有理由相信O 后处理后O所在句子的概率.这也是一条退让规则， 为C 反映了当识别Agent没有较大的把握区分出C,和 其中汉字的复杂度可以用规格化后汉字点阵的 C2时，把决定权交由后处理Agent.. 黑白点之比来度量，也可以用汉字的纵向层次数或 3模糊综合评判 横向层次数度量. 规则3如果0为汉语句子中的一员，且C1、C2 设x为待识汉字，C={c1,c2,…,cn}为其候选 为一对客观相似字，则识别类Agent对此不参与辩 集，A={a1,a2,…,an}为Agent集，每一个a从自 论 己的立场出发，对候选c:是否为x的识别结果有一 将相似字定义为客观相似字和主观相似字] 个评价，经适当的转换后，该评价可以看作是从A 客观相似字指的是那些拓扑结构相似的汉字，而主 到F(C)的模糊映射，即 观相似字指的是那些拓扑结构并不太相似，但是特 子：A+F(C), 征比较相似的汉字，这是由于特征抽取的不连续性 a→f(a）(ta,r2,…,m)∈F(C). 造成的。 式中：F(C)表示定义域为C的模糊集合的全体 客观相似字虽然它们的拓扑结构非常相似，但 由于各Agent所采用的知识不同，其对c:评判 字意一般有很大的差别，如“士”和“土”、“末”和 的精确程度和重要程度也不同，因此对不同的A “未”等.与其通过识别Agent找出它们在字形上的 gent给出的评判，要分别对待，有一定的权重分配. 差别，不如通过后处理等手段进行选择更为可靠. 权重分配可以看作是A上的模糊集，记为 规则4如果P是使C1、C2产生最大差异的部 W=(01,02,…,0m）∈F(A). 分，且在相同的部分0与C1的差异小于0与C2的差 式中：切，表示第j个Agent的权重，它们满足归一化 异；则有理由相信0为C· 条件： 其中，P为汉字的左半部、右半部、上半部、下半 部、中心部或外围部之一，差异指的是当只使用包含