（信号与信息处理专业论文）联机手绘图形识别的自适应hmm方法.pdf

摘要 本文提出了一种用于联机手绘图形的自 适应隐马尔科夫模型识别方法， 该方 法利用隐马尔可夫模型( h m m ) 对时序随机序列的描述能力作为手绘图形识别中的 核心分类器， 并且在传统h m m 识别结构的基础上进行了改进， 使得识别系统不仅 具有自 适应学习训练样本的能力， 而且具有根据输入图形特征调节系统行为的能 力。 为了使原始的手绘图形数据能够用于进行h m m 识别， 本文中设计了有效的预 处理算法用于去除噪声和规范化手绘图形数据， 同时根据h m m的特点选择了一组 特征用于进行训练和识别， 并设计了相应的特征提取算法。 为了使识别系统能够 更好的适应输入图形的变化，本文提出了一种a h m m 识别结构，利用基于单边积 分的 特征压缩算法和自 适应压缩率调整技术构造了一种闭环反馈识别系统， 既能 够根据图形的几何特征自 适应的 压缩特征向 量， 又能够通过闭环反馈调整特征向 量压缩率， 达到了很好的识别效果. 为了进一步提高识别速度， 满足联机识别中 实时性的要求，本文在 a h m m的基础上同时提出了一种双层自适应识别模型 ( b l - a h m m ) ， 通过预分类来减小识别空间， 提高了系统识别速度并同时提高了识 别率。 类似于其他的梯度下降学习算法， 在h m m 训练过程中不可避免的存在局部 最优以及对初始参数敏感的问题。 为了 减小这些问 题对识别系统的影响， 本文同 时提出了一种g a - h m m 训练模型，通过在h m m 训练过程中引入遗传算法来寻找全 局最优， 改善了h m m 训练效果， 从而提高了系统的识别性能。 文中通过大量的试 验证明了采用g a - h m m 训练的b l - a h m m自 适应模型的有效性和其相对传统h m m 识 别模型的优越性。 关键词: 联机手绘图形隐马尔科夫模型 单边积分 遗传算法 ab s t r a c t i n t h i s p a p e r , a n a d a p t iv e h i d d e n ma r k o v mo d e l ( a h m城 a p p r o a c h t o o n - l i n e h a n d - d r a w n s h a p e r e c o g n i t i o n i s p r e s e n t e d . i n o u r m e t h o d , h mms a r e c h o s e n a s t h e c o r e r e c o g n i z e r d u e t o it s g r e a t a b i l i t y t o m o d e l s t o c h a s t i c t i m e s e r i e s . ma n y i m p r o v e m e n t s a r e m a d e t o t h e t r a d i t i o n a l h mm r e c o g n i z e r i n o r d e r t o i n c r e a s e t h e fl e x i b i l it y o f t h e r e c o g n i t i o n s y s t e m , t h e r e s u l t i n g fr a m e w o r k c a n n o t o n l y a d a p t i v e l y l e a rn fr o m t r a i n i n g d a t a , b u t a l s o c a n a d a p t s y s t e m b e h a v i o r t o in p u t h a n d - d r a w n s h a p e . i n o r d e r t o f i tt i n g o r i g i n a l h a n d - d r a w n g r a p h i c s d a t a t o h mms , e ff e c t i v e p r e - p r o c e s s i n g a l g o r i t h m s a r e d e s i g n e d t o r e m o v e n o i s e a n d r e a r r a n g e i n p u t d a t a p o i n t s . f e a t u r e s f o r h mm t r a i n i n g a n d r e c o g n i t i o n a r e c a r e f u l l y s e l e c t e d a c c o r d i n g t o c h a r a c t e r i s t i c s o f h mms , a n d c o r r e s p o n d i n g f e a t u r e e x t r a c t i o n a l g o r i t h m s a r e i n t r o d u c e d . f o r b e tt e r p e r f o r m a n c e i n t h e c i r c u m s t a n c e o f d i ff e r e n t h a n d - d r a w n s h a p e i n p u t , a n a d a p t i v e h m m ( a h mm) s t ru c t u r e i s p r e s e n t e d w h i c h c o m b i n e s s i n g l e - b a n d i n t e g r a l a l g o r i t h m a n d a n a d a p t i v e c o m p r e s s i o n r a t i o c o n t r o l t e c h n i q u e i n t o o n e c l o s e d l o o p f e e d b a c k r e c o g n i t i o n s y s t e m , t h e a h mm c a n a d a p t i v e l y c o m p r e s s f e a t u r e v e c t o r s a c c o r d i n g t o g e o m e t r y f e a t u r e o f i n p u t g r a p h i c s , a l s o c a n i t a d a p t i v e l y a d j u s t t h e f e a t u r e c o m p r e s s i o n r a t i o b y f e e d b a c k , t h i s r e c o g n i t i o n s t r u c t u r e a c h i e v e g o o d p e r f o r m a n c e i n r e c o g n i t i o n . t a k i n g t h e r e a l - t i m e r e c o g n i t i o n r e q u e s t in t o c o n s i d e r a t i o n , a b i - l a y e r a h mm m o d e l ( b l - a h mm) i s i n t r o d u c e d . b l - a h mm c a n r e d u c e t h e r e c o g n i t i o n s p a c e b y p r e - c a t e g o r i z a t i o n , w h i c h i m p r o v e s t h e s p e e d a n d a c c u r a c y o f r e c o g n i t i o n . l i k e t h e o t h e r g r a d s d e s c e n d a l g o r i t h m s , t h e p r o b l e m o f l o c a l o p t i m a i s a l s o e x i s t e d i n t h e t r a i n in g o f h mm. i n o r d e r t o a l l e v i a t e t h e in fl u e n c e t o t h e r e c o g n i t i o n s y s t e m , a h y b r i d g a - h m m t r a i n i n g m o d e l i s a l s o p r e s e n t e d , w h i c h in t r o d u c e t h e g e n e t i c a l g o r i t h m i n t o t h e h m m t r a i n i n g t o s e a r c h f o r g l o b a l o p t i m a , t h e t r a i n i n g p e r f o r m a n c e i s g r e a t l y im p r o v e b y t h i s m o d e l . l o t s o f e x p e r i m e n t s a r e p e r f o r m e d i n t h i s p a p e r , t h e r e s u l t o f t h e s e e x p e r i m e n t s s h o w s t h a t t h e b l - a h mm m o d e l t r a i n e d b y g a - h m m m o d e l i s e ff e c t i v e a n d h a s b e tt e r p e r f o r m a n c e o v e r t h e t r a d i t i o n a l h mm r e c o g n i t i o n m e t h o d . k e y w o r d s : o n - l i n e h a n d - d r a w n s in g l e - b a n d i n t e g r a l s h a p e r e c o g n i t i o n h i d d e n ma r k o v mo d e l g e n e t i c a l g o r i t h m 创 新 性 声 明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了论文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人己经发表或撰写过的研究成果;也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 本人签名 a-翌 梦 - 4 - . r u 日期: 关于论文使用授权声明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即:研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文:学校可以公开论文的全部 内容或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本 人 签 名 : .丝猛- ” 曰月僵蛋 日 期 : z ,n 3 . 1 - ， 日 期: _ _ 第一章绪论 第一章绪论 随着计算机技术， 通信技术的发展， 现代的数值计算机己 经成为各行业不可 或缺的重要工具，i n t e rn e t 的发展更加速了计算机技术的发展和普及。随着使用群 体的日 渐扩大和数据通信技术的飞速发展，计算机设备逐渐向小型化， 便携化， 人性化方向发展。个人计算设备的普及从一个侧面表明了整个社会的信息化进程。 人机交互 ( h u m a n - m a c h i n e i n t e r a c t i o n )的问题伴随着现代计算机的诞生而出 现，输入输出设备从早期的硬连线，穿孔机，读卡机，演变到现今最为常用的鼠 标，键盘，c r t显示器. 人机交互方式从字符，命令行发展到现在 g u i / wi m p . 可以说，每一次人机交互方式的变革都使得计算机更易于操作，更容易被广大的 用户群所接受，在计算机的普及过程中， 人机交互技术的发展功不可没。 如今， 在计算机技术得到了前所未有的广阔发展前景的同时， 传统的人机交互方式也受 到了 越来越大的挑战。即便是g u i / wi mp 这样广为采纳的交互方式仍然不能满足 新一代计算设备的需要。 随着人们对新型人机交互方式的迫切需求， 人机交互技术的研究在近 1 0 年来 成为一个热点问题，作为计算机科学和人类认知心理学的交叉产物，人机交互技 术不仅具有广阔的应用前景，同时具有深远的理论研究意义。目前，人机交互技 术的发展己进入多模人机接口的研究阶段，其核心研究目 标就是提供一个便捷， 方便， 可以采用人与人之间自 然交流方式的人机交互环境.多模态人机交互技术 将综合利用语音，图像，手势，手写体，表情，动作等多通道的方式，提供一个 以人为中心的，具有适应性的交互环境。 作为一个新兴的学科，多模人机接口的研究工作得到了多方面的发展，目 前， 美国正在进行研究的有关人机交互技术的项目 主要有:mi t媒体实验室的多通道 自 然对话项目 ， c m u交互系统实验室( i s l ) 的i n t e r a c t 项目 ， 海军的 i n t e l l i g e n t m 4 系统。 在欧洲信息技术研究战略规划 ( e s p r i t i i )的a m o d e u s 项目 中， 有大 童 关于多 通道人 机交互的 理 论和 系统 研究。 在e s p r i t i i i 中， 正 在进 行m i a m i ( m u l t i m o d a l i n t e g r a t i o n f o r a d v a n c e d m u l t im e d i a i n t e r f a c e s ) 项目 的研究， 其 领域 包 括多 媒体和高级多通道人机界 面两部分， 语言内 容是通过视觉、听 觉、 触觉和 手势来访问、表示和产生多媒体信息的多通道交互的各个方面。 还有法国 i m a g 的 c o u t a z和 n i g a y设计的系统 m a t i s ( m u l t i m o d a l a i r l i n e t r a v e l i n f o r m a t i o n s y s t e m )中， 用户可以 利 用键盘、鼠 标、 话筒或者它们的 组合方式查 询航班信息， 体现了多通道用户界面人机交互的自 然性和高效性。语音、自 然语言、手势、视 联机手绘图形识别的自 适应h mm方法 线跟踪及头部跟踪等各种形式的输入技术正在研究中，沉浸式的头盔显示器已经 开始使用，新的立体显示设备也正在研制。在 g u i 基础上，新的人机交互技术已 逐渐开始应用。随着新式人机交互设备和非范式的交互方式的出现，计算机必将 在更广泛的领域中更好的为人们服务。 在各种新兴的人机交互手段中， 对手写信息的自 动识别处理是较早得到重视 的一种，由于产生和阅读手写信息的能力是一种基本技能，因此采用手写交互方 式能 够自 然的适 应大量的用户. 特别是在各种p d a设备中， 考虑到个人信息隐私 性的要求， 手写仍然是较语音更为恰当的输入方式。在m i c r o s o ft公司最新推出的 平板电 脑 ( t a b l e t p c )中， 更是把手写作为其便携设备的首选输入方式。 按照与 语言文字相关与否，手写信息可以分为手写体文字和手绘图形两大类，对手写文 字的识别处理在近年来受到了研究人员的广泛关注，而对手绘图形的识别工作则 相对开展较少。图形是手写信息中的一个重要组成部分，由于手绘图形识别的研 究工作相对文字识别落后， 使得一个能 够基于自 由 手写信息进行交互的人机界面 难以 形成。 木文的工作正是围绕手绘图形识别的 研究进行，以期在这方面做出 有 益的尝试。 互 1 . 1 基于联机手绘图形识别的人机交互技术 手绘信息是一种记录在平面上用于传达信息的人工图形符号，采用各种手绘 图形记录信息是人脑记忆能力的一种自 然的延伸。 在手绘产生的各种图形符号中， 用来代表语言的视觉符号被确定下来为作为文字，成为特定语系人群使用最为频 繁的图 形符号系。其它大量的手绘图形则根据其表意的不同 而被应用到不同的领 域中去，同样被相应应用域的人所熟悉。各种手绘图形符号是人们获取信息的最 重要的来源之一 数字技术的出现和日 益普及，虽然对传统的信息记录方式带来 了 挑战， 然而图形符号的社会记录的作用和交际工具的地位却没有任何改变，时 至今日， 笔和纸的使用频率仍然远远高于键盘和鼠 标 手绘图形具有直观、明确、歧义性小的特点，相对语音来说，其表意更为准 确， 文字的广泛应用正是图形符号这一优点的集中体现。 而在特定的应用领域中， 一般的图符往往具有比文字更强的表现能力，乐谱就是一个明显的例子。图形符 号广泛应用于各种领域中，以 下简单列出一些典型的应用领域: t .工程图。包括各种工程设计和实施中使用的图纸，如电路图、机械制图， 建筑图、设施配置图等等. 2 .地图。 包括与地形地物信息有关的各种图形， 如地理信息系统、 交通管理 系统、军事态势图等。 第一章绪论 3 . 其它图形符号系统。如乐谱、数学符号、商标、流程图表等等。 要对这些系统中的图形符号进行计算机处理所面临的首要问题就是图形符号 的输入和获取的问题。在目 前的以图形符号交互为主的系统，如c a d系统中，广 泛采用的是选取和组合的输入方式，即通过给定一个大型的图形库，由用户在其 中浏览选择， 或者通过给定一些简单的图形元素，由 用户自 行组合复杂图形的方 式进行。这些方法在图形符号库数量较小，或者需妥处理的图形符号不太复杂的 前提下是可行的，但是现在的系统大多需要处理数量庞大的图形符号库，其容量 可能是几千个或更多，图形符号的复杂程度也很高，此时无论是选取还是组合的 方式都显得过于繁琐而无法满足需要。 类似于文字识别工作取得的成功， 手绘输入无疑是输入图形符号的最佳方式。 因此，对手绘输入的图形符号的自动识别处理就成为此类系统中的一个重要的研 究课题。 互 1 . 1 . 1 联机手绘图形识别的研究现状 对手绘图形的识别过程是将一种表形的图形符号转变为表意的抽象符号的过 程，其最终目的是由机器理解特定图形符号在一定环境中表达的含义。为了满足 数值计算机处理的需要，在进行任何识别处理以前，手绘图形需要经过一个数字 化的过程转变为计算机能够处理的数据。按照其转换过程的不同，手绘图形识别 可以分为脱机识别和联机识别两种。前者通过扫描完成图形到数值的转换，后者 则通过特殊的设备，如数字化仪，光笔，电磁笔等完成这种转换。在脱机识别的 情况下，只能得到原始图形符号的图像，因而是一种 “ 空间一 灰度”的表示方法。 在联机识别的情况下，原始图形上每个点的二维坐标作为一种时间函数保存下来， 是一种 “ 空间一 时间”的表示方法。由于数据采集过程的不同，使得两者在处理方 式上也不尽相同。 目 前，联机手写文字识别的研究工作开展得较多，且取得了不少成果，但是 针对联机手绘图形识别的研究工作却开展的较少。对工程图中图形符号的识别工 作开始于上世纪8 0 年代中期，如s .t s u n e k a w a 等研究的t o s g r a p h电路图识别 系统 1 , k . a b e 等关于流程图中的图形符号识别的研究 2 。 如今， 对图 形符号识 别的 研究已 经 涉及到很多 应用领域， 包括电 路图 3 4 , g i s 系统【 5 6 、 建筑图 7 , 乐 谱 8 等 等， 并且 不断 有 新的 应 用 领 域 被 涉 及。 特别的， 在联机手绘图形的识别方面，也有一些研究工作在开展中， 如g r o s s 和d 。设计的 手绘图 形输入系统 9 , a j a y的 基于滤波器组的图 形识别系统 1 0 , a r v 。 和n o v i n s 设计的基于模糊规则的2 维图 形联机识别系统 1 1 等。 在手绘图形识别的研究工作中，目 前常用的识别方法有两大类: 联机手绘图形识别的自 适应h m m方法 第一类是基于结构特征和规则库的识别方法。 在此类识别处理方法中， 对图 形的描述主要基于其几何特征。试图通过对手绘图形形状的有效抽象来定义具有 一定不变性的描述，通过对所定义的规则的匹配和检索来完成对和图形的识别。 这类方法的突出 优点是具有很强的对图形整体特征的描述能力， 模型本身的可操 作性强， 不需要采集大量的 样本即可构造出相应模式的模型。 其缺点是推广性差， 对大容量模型库的修改十分烦琐，往往不能适应输入样本中的不规则形变。其常 见的方法包括基于图元和笔划分割的方法、变形模型匹配、规则库和决策树等. 第二类是基于统计模型的识别方法。这种识别方法特别在近 1 0 年来得到了飞 速的发展。在统计模式识别方法中，图形不再以其几何特征描述，而是以 特征空 间中的一组特征来描述.在这种描述方法中，不同的类型表现为特征空间中围绕 某个质心的多维概率分布函数。识别过程就是判断样本在特定模式类中出现的概 率的过程。基于统计模型的识别方法具有较强的鲁棒性，推广性好，利用各种学 习和优化算法，能够根据样本自 学习其统计特征，具有很好的适应能力，这些特 点都使得基于该方法的识别器特别适合于人机交互环境的需要。目 前常用的统计 模型包括人工神经网络 ( n n ) 3 1 1 、 时延网络 ( t d n n ) 3 幻、 隐马尔可夫模型( h m m ) 1 4 、支撑矢量机 ( s v m ) 3 2 等。 虽然取得了很多进展，但作为一个新兴的研究方向，在联机手绘图形识别的 研究中，仍然存在很多问 题.如:由于在手绘图形输入过程中缺乏固定的笔划和 笔顺，同时存在较严重的变形，使得对基本图形元素的分割极为困难，甚至无法 实现准确的分割。而基本元素分割的错误将直接导致后续识别错误率的上升; 在 图元识别过程中，仍然缺乏有效的对图形符号的建模方法，图形符号数量增大时 的规则爆炸和区分度下降的问题仍然存在; 在语义和语法级图形识别中，由于不 同图形库的专家知识不同，使得通用图形符号识别系统的设计尤为困难:缺乏对 图形符号识别系统性能评估的准则，使得不同应用中的图形识别系统识别性能的 比 较很困难。 1 . 1 . 2 隐马尔可夫模型在联机手绘图形识别中的意义 本文主要研究以隐马尔可夫模型 ( h mm)为基本识别模型的联机手绘图形识 别方法。 采用 h mm 描述手绘图形符号的统计特性的突出优点是能够根据采集到 的 样本数据进行自 适应学习， 通过参数优化自 动完成建立模型的 过程， 这样既避 免了传统的采用规则库或决策树的方法在处理大型或复杂图形库时面临的规则爆 炸问题，也极大的减小了对图形本身先验和专家知识的依赖，提高了系统的智能 性和适应性，使得识别系统的自 学习成为可能。同时由于 h mm 本身的特点，通 过自 适应学习得到的统计模型具有较为明确的物理意义，避免了采用多层感知器 第一章绪论 等学习机器时产生的难以修正训练得到模型的缺陷，为结合统计和句法模式识别 的优势提供了基础。采用 h m m 进行手绘图形识别的另一突出优势在于其集分割 和识别的能力为一体。在手绘图形识别的过程中，对基本图形元素的分割是很困 难的。采用 h mm 作为识别核心，避免了对基本图形元素的分割，使得对图形符 号的识别和分割可以同时进行，减小了由于基本图形元素分割错误而对后续识别 带来的影响，有助于提高系统的识别正确率。 h mm虽然已经在语音和手写文字识别中得到了广泛的应用， 然而在手绘图形 识别方面的应用较少。手绘图形在输入过程中存在较多的噪声和比较严重的不规 则形变， 是影响h m m有效应用于联机手绘图形识别的一个原因。 另外， h m m描 述的是特征向量的时变统计特性，对特征向量的长度有相应的要求。过长的特征 向量不仅会带来训练和识别算法时间复杂度的急剧增加，同时会使得识别率下降。 传统的基于 h mm 模型库的识别系统在处理类型较多的分类问题，由于各个类型 在特征空间中的质心间间距的缩小， 不可避免的带来分类错误的上升。 h mm的训 练算法是一种梯度下降的优化算法，因此在训练中存在局部最小的问题，同时由 于缺乏有效的模型参数初始化算法，更容易在训练中出现这样的问题。本文的工 作正是针对这些问题进行的。 1 . 2 本文的主要工作 本文研究工作来源为国家自然科学基金项目“ 有约束的自 适应联机手绘图形 识别技术研究”( 项目批准号:6 0 1 7 3 0 6 7 ) 。目前大多数图形符号识别系统是针对 某个特定应用领域开发的，并且往往基于基本图形元素和图元己被正确划分的假 设，在光栅图形矢量化基础上进行语法和语义级的识别。但在联机手绘图形符号 的识别中，这一假设一般是不成立的，对基本图形元素和图元的识别是联机识别 系统的关键之一。本文研究工作主要围绕对联机手绘输入图元的在线识别展开。 主要工作如下: ( 1 ) 针对联机手绘图 形的 特点， 讨论了消除手绘图 形输入中的噪声和不规则形变的 方法。 给出了有效的图形笔划规范化方法， 该方法消除了在手绘图形输入过程 中笔划和笔顺不固定造成的特征向量时序混乱的问题。 针对h mm的特点， 讨 论了用于h mm识别的手绘图形特征及其提取方法， 本文的工作证明了 这些特 征的有效性。 ( 2 ) 提出了 一 种带有反 馈的h m m联机图 形识别方法， 我 们称其为自 适应隐马尔可 夫模型 ( a h mm) 识别方法。 该方法采用课题组已 有成果单边积分算法， 对手绘图形的特征序列长度进行自 适应压缩。 通过对 h mm单次识别结果的决 联机手绘图形识别的自适应h mm方法 策，自 动判断是否需要调整单边积分参数，以增加特征序列的长度，进而要求 h mm进行较长特征序列的更精确识别。试验证明 a h mm识别方法较 h mm 方法在显著提高识别率的同时，识别速度也有明显的提高。 ( 3 ) 传 统的 基于h m m模型 的 识别 系 统 在 模式 类型 较多 的 情况 下， 往 往会导 致 分 类 错误上升。 为此， 本文提出了一种手绘图形识别的双层自 适应隐马尔可夫模型 ( b l - a h mm)方法。该 方法的 基本思路是将图形模式集合经过预分类， 分成 模式数量较少的子集合，由于减少了模式集合中的类型数量， 使得不同模式之 间更易区分;在对待识图形进行识别时，首先将手绘图形预分类到对应的子集 合中，然后采用 a h mm 方法在子集合中对数据样本细分类。实验证明， b l - a h m m识别率和识别速度较a h mm有显著提高。 ( 4 ) 基于h m m的 训练算 法本质上是一种梯度下降的 优 化算法， 因 此不 可避免存在 局部极小。以及对初始参数敏感的问题。 本文将遗传算法 ( g a)引入到 h mm 的训练中来，利用 g a的全局寻优能力来减小局部极小的概率。为此，本文提 出了两种g a - h mm训练方案，一方面较好地完成了对h mm参数的初始化， 同时有效地减小了h mm陷入局部极小的概率， 提高了整个h mm识别系统的 训练效果。 在此基础上， 提出了一种g a和b l , a h mm混合的手绘图形识别系 统模型。 综上，本文的工作对智能人机交互中的联机手绘图形识别的研究具有一定的 理论参考价值和较高的实际应用价值，对 h mm 模型的推广应用也具有一定的意 义。 本文的后续章节内容安排如下: 第二章中介绍了 h mm 的理论基础及应用问题，介绍了基于 h mm 的识别系 统的结构，同时分析了 h mm 对手绘图形统计特性的描述能力及其需要解决的问 题。 第三章介绍针对于手绘图形的预处理和特征提取算法。 第四章介绍a h mm识 别结构和相应的特征压缩算法，包括对单边积分算法的和 h mm 识别反馈机制的 介绍。给出了a h mm 与一般 h mm 的对比实验结构.第五章对 b i r a h mm和第 一层预分类算法进行了详细介绍。 第六章介绍了两种 g a - h mm训练模型， 并分别 给出他们和一般h mm训练算法的性能对比。 第二章隐马尔可夫模型及其在图形识别中的基本框架 第二章 隐马尔可夫模型及其在图形识别中的基本框架 采用隐马尔可夫模型构建的统计模式识别系统具有能够根据采集到的样本数 据自 适应学习，自学习得到的模型参数物理意义明确，分割和识别可同时进行等 显著优点。将隐马尔可夫模型引入到手绘图形识别中来，使得根据用户的输入习 惯自 学习以及根据图形集的先验信息对识别结果进行修正成为可能，是构建具有 适应性和自 学习能力的手绘图形识别系统的基础。 本章将首先介绍隐马尔可夫模型的相关理论及其常用算法，然后结合手绘图 形识别问题，介绍基于隐马尔可夫模型的识别系统基本结构。最后介绍本文中选 择的隐马尔可夫模型的拓扑结构及其描述手绘图形统计特性的原理。 2 . 1隐马尔可夫模型 ( h m m ) 俄国有机化学家v l a d i m i r v a s i l y e v i c h m a r k o v n i k o v 于1 8 7 0 年提出了马尔 可夫 ( m a r k o v )模型， 其本质上是一种随机过程。隐马尔可夫过程 ( h m m )是一个 二重马尔可夫随机过程， 起源于6 0 年代末【 1 2 ， 但由 于模型的参数估计问 题一直 没 有得 到 较 好地 解决， 因 此， 一 直 未能 得 到 广 泛 地重 视。 直 到1 9 7 7 年， d e m p s te r 等提出了一种最大期望 ( e m) 估算方法，并且由wu给出了收敛性证明，从而为 隐马尔可夫 模型的 参数估计 算法奠定了 基 础。 随 后， l e v i n s o n 等 1 3 又提出了 一种 模型参数的最大似然估计方法，并将它用于语音识别当中，取得了良 好的效果， 从而 促使隐马 尔可夫 模型 在语音识 别 研究中 得到 迅速推 广 1 4 1 习 。由 于 手写识 别 与语音识别之间存在许多的相似之处，因此，隐马尔可夫模型也被引入手写识别 领域中， 用来对手写模型进行建模，这方面取得了 相当多的成果 1 6 1 7 1 8 1 9 1 e 隐马尔科夫模型对很多随机序列信号来说， 是一种十分有效的数据描述统计 模型。与语音信号类似，联机手写数据也可以看作是一种随机序列信号，在使用 隐马尔可夫模型进行建模时，观测矢量通常直接由输入序列来构造，它能反映数 据中某种随时间变化的局部特征，但这种特征一般是不稳定的，通常具有较强的 随机性， 而模型中的状态能够描述数据中的某种全局特征， 这种特征通常是较为 稳定的，从统计特性上看，它可以反映出观测特征矢量在较大时间尺度上的统计 特征变化。 一隐马尔科夫模型定义 隐马尔科夫模型是一个双随机过程，一个是隐藏的有限马尔科夫链，另一个 联机手绘图形识别的自 适应h m m方法 是与状态相关联的一系列随机过程。马尔科夫链按转移概率矩阵改变状态，每个 状态以某个随机过程产生观察值。观察者只能看到与每一状态相关的随机过程的 输出 值， 而不能观察到马尔科夫链的 状态， 所以， 称为隐马尔科夫模型。 这样一个h m m 可以由下列参数描述: a ) n: 模型中m a r k o v 链状态数目 。 记n个状态为 b , ， 二 ， 0 , ， 记t 时 刻m a r k o v 链所处的状态为q , ，显然q , e ( b t , . . . , o n ) 。 b ) m: 每个状态对应的可能的 观察值数目 。 记m个观察值为k ， 八 ， 记t 时刻观察到的观察值为。 ， ，其中d , e m, . . . i v m ) 。 c )， : 初始状态 概率 矢量， 二 ( 二 ， ， 二 ， -r 刃其中 二 ， 一 p ( q ， 二 b 小1 s 6 5 n ( 2 - 1 ) d ) a : 状态 转 移 概 率 矩 阵 ， a 一 ( a d ) n . n ， 其 中 a 、 一 p ( q , . ; 二 b j l q ， 一 b ; ) , 1 i , j n ( 2 - 2 ) e ) b : 观 察 值 概率 矩 阵，b m ( b jk ) n . m ， 其中 b ik 二 p ( o a v k j q 二 b j ) , i s j s n ,1 s k s m 这样，可以记 一个h m m 为:a 二 ( n , m， 二 ， a 迢) 或简写为: a s ( n , a , b ) ( 2 - 3 ) ( 2 - 4 ) ( 2 - 5 ) 二.隐马尔可夫模型的基本算法 h m m 的基本算法有三个，这里我们只介绍本文要用到的前向一 后向算法和 b a u m 一w e l c h 算法。 一)前向一后向算法 前向一 后向 算法用来计算给定 一个观察 序列0 a 00 2 , . . . , 0 ， 以 及一个模型 a 二 ( j c , a , b ) 时， 由 模型参数d 产生出o 的概率p ( o / a .) 。 用该算法能比 直接计 算大 大的减少计算量。 ( 1 ) 前向算法: 定义前向变量为: a , ( i ) 二 p ( 0 ， ， o z ， . . . , 0 9 , 二 b , / a ) , . . . . . . . . . 1 s t :s t ( 2 - 6 ) 那么，有 a初 始化: a , ( i ) 二 二 . b r ( 0 i ) , ， 二 1 s i . s n ( 2 - 7 ) 匕 .递归: a , . . ( j ) = 著 a , (i)a , lb , (0 ，一 ， “ t 一 “ “ n ( 2 - 8 ) 第二章隐马尔可夫模型及其在图形识别中的基本框架 ，卜，户， n 。 . 终结: p ( o l ) , ) ( 2 ) 后向算法 与前向算法类似， 一 ) . a r (1) 定义后向变量为 ( 2 - 9 ) 16 , ( i ) 一 p ( 0 1 ,0 1 , . . . ， o r 1 q , 6 j , 11 ) , . . . 1 t t一 1 , 其中 i t ( i ) 二 1类似， 有 a 初始化: ( 2 - 1 0 ) b . c. # r ( i ) 1 , . . . . . . 1 (0 ,)r“ 一 ， ， 一 t 一 ,t 一 ， n 终 结 : p (o / a ) 昙 fi , (i) ( 2 - 1 1 ) . ,1， 1 i n ( 2 - 1 2 ) ( 2 - 1 3 ) ( 二)b a u m -w e l c h 算法 b a u m -w e l c h 算法实际上是解决h m m 训练问 题， 即h m m 参数估计问题， 或者说， 给 定 一 个 观 察 值 序 列o 二 oo z ， 一 ， o r ， 该 算 法 能 确 定 一 个 模 型a 二 ( , r , a , b )， 使 p ( o l 几 ) 达到局部最大。 定义mi 1 ) 为给定训练序列o 和模型a 时， 时 刻t 时 m a r k o v链处于。 ， 状态 和 时 刻t + 1 为 氏 状 态的 概 率， , ( i , j ) p ( o , r , 即: = 6 、 ， 叼 ， + 、 = 9 i / a ) 可以推导出: , 0 , j ) 二 【 a , ( i ) a ,; b ; ( 0 ,+ , ) ,6 , + , ( j ) l p ( o l 1 ) ( 2 - 1 4 ) ( 2 - 1 5 ) 那么，时刻t时m a r k o v 链处于。 ， 状态的 概率为: p ( o , r , 8 ; / 幻二 n ; se,(l,1 ， 一 “ , (t) j3, (i) i p (o i a ) ( 2 - 1 6 ) “ ， 表 示 从 8 ;状 态 转 移 出 去 的 次 数 的 期 望 值 ， 而 茗 氛 “ ， ” 表 示 从 ” (i)阳v台 岛 此 因 状 态 转 移 到 氏状 态的 次 数的 期 望 值。 由 此 导 出 了b a u m - w e l c h 算 法中 著 名的 重 估 公式: n ; mi ) r - 1 7- 1 a 一 p ,c , l ) / p ic ) 、 一 乌 m 1)/客 m i) ( 2 - 1 7 ) 且q _ 片 那么， h m m 参数a _ 伪 , a , b ) 的求取过程为: 根据观察值序列和选取的初始 模 型， 由 重 估 公 式， 求 得 一 组 新 参 数 j t ; , a ;i ,b ik ， 亦即 得 到 了 一 个 新的 模 型 .t = (n , a , 刃， 可以 证明， p ( o / x ) p ( o / ,i ) ， 即由 重估公 式 得到的a 要比 a 在 表示观察值序列口方面要好。那么，重复这个过程逐步改进模型参数，直到 联机手绘图形识别的自 适应h mm方法 p ( d乃收敛， 即不再明显增大， 此时的i 即为 所求之模型。 2 . 2联机手绘图形识别中的h m m 方法 一种图形识别方法的效果如何，取决于它在多大程度上利用了图形的原始信 息。我们在观察一个图形的时候，可以明显地观察到图形的大小，轮廓等等。 无疑地，我们可以利用一组数值特征来描述图形，并且利用这种数值特征来对图 形进行识别。但是模式识别研究的经验表明，简单地利用一组数值特征不能满意 地解决图形识别问题。我们理解，图形应当作为一个整体来描述.不仅仅包括图 形的数值特征，还应当包括各个笔划间的不同表象和相互关联。然而，怎样描述 不同表象和相互关联又成了问题。 隐马尔可夫模型 ( h m m ) 提供了描述复杂现象的一种可能机制。 按照这种模型， 观测到的一列特征 ( 例如描述各个图形一组数值特征)被看成是另一组不可观测 的 ( 因此是隐的) “ 状态”产生出的一列实现。 ”状态既然是不可观测的，它的个 数是未知的，但可以假定。选择状态个数的多少必须在模型的复杂性和描述复杂 现象准确度之间进行折衷。在隐马尔可夫模型中包含了产生观测的两层概率。一 层是选择状态的概率。 假定有 n 个状态， 从当前的状态出发选择下一个状态也有 n 个可能性。于是，状态选择概率必须用一个 n x n的状态转移矩阵来描述。另一层 是每个状态产生出一种实现的概率。如果实现只在一个离散集合中取值，产生实 现的概率就可用概率分布来描述。如果实现取连续值，产生实现的概率就应该用 概率密度函数来描述。一个合理的或好的隐马尔可夫模型应该是这样的:给定一 组观测序列，从关于状态的适当的一组初始分布出发，能够产生出一组实现序列， 它非常好地逼近给定的观测序列。 利用隐马尔可夫模型对图形进行描述和识别，我们就不是孤立地利用图形的 数值特征而是把这些特征和一个状态转移模型联系起来。我们可以这样解释图 形的隐马尔可夫模型。例如，我们把某一个图形的某一笔划抽象为一种状态。我 们观测到的不是抽象化的 “ 笔划” ，而是它的各种表象，如朝向的，笔划角度的、 水平的、斜度的表象等等。我们的模型将图形划分为多个显著区域:笔划特征变 化，如矩形，就分为 4个状态。在此基础上建立了用于图形的描述和识别的隐马 尔可夫模型。可以看出，这种模型既考虑了图形的各个笔划的不同表象，又考虑 了他们的相互关联，比起孤立地利用各个笔划的数值特征有概念上的进步。实验 结果也证实了h m m的合理性。 应该指出，将隐马尔可夫模型用于图形描述和识别，在概念上我们不必把隐 状态简单地理解为上面提到的图形的显著不同笔划。我们甚至可以直接理解为数 第二章隐马尔可夫模型及其在图形识别中的基本框架 从以上的分析可以看出，采用本文中的 h mm 模型，实际上描述了时序信号 随时间变化的统计特性。 通过对观测矢量和驻留时间两方面的参数估计，即可得 到对原始信号统计特性的一个较好的估计，从而完整描述了信号的特性。 相较传统的多层感知器学习模型来说，采用本文中的 h m m结构，一方面可以 减小训练的参数数量.另一方面，由于 h m m的明显物理意义，使得根据先验知识 对训练好的模型进行调整成为可能，同时为参数的初始化，避免落入局部最小提 供了条件。 同时也可以看到，采用本文中的模型设计，就对特征向量的时序提出了较高 的要求，因此训练和识别采用的特征矢量必须经过归一化处理以保证其维持统一 的时序。特别是对手绘图形这种具有较大变化的数据来说，笔划重排的处理更为 重要。 2 . 4小结 本章从处理联机手绘图形的需要， 引入了隐马尔可夫模型， 文中详细介绍了隐 马尔科夫模型的理论