（计算机软件与理论专业论文）手绘草图理解的隐马尔可夫模型方法.pdf

中文摘要 本文以简单手绘草图设计为背景，以解决草图理解中的歧异性和模糊性为目 标，对草图理解系统功能构架、学习方法的选择，草图输入交互设计等方面进行 了初步的研究和实验。我们提出了一个通用的解决框架，选择了在语音识别中获 得良好应用的隐马尔可夫模型( m m ) 学习方法，实验验证了该方法的可行性， 基于h m m 学习方法，自主地进行了手势设计的开发。本文的成果主要体现在以 下几个方面： 基于h m m 的学习方法：在语音识别领域内h m m 成功应用的基础上，针对 草图理解与语音识别具有的相似性，结合用户在某一领域内会习惯性输入的 特点，把用户的输入习惯作为草图理解的时序信息，提出了基于h m m 学习 方法的草图理解模型。 利用目前在线识别系统中常见的特征表示方法对h m m 的应用能力进行了实 验，结果表明h m m 能较好地描述草图输入中的用户习惯，表现了良好的识 别效果，是手绘草图理解的可行方法。用手势识别的开发模拟复杂的手绘草 图理解的开发，在其内部实现机制上采用了h m m 建模。 关键词： 手绘草图，语义理解，隐马尔可夫模型，人机交互 a b s t r a c t t h ep u r p o s eo ft h i st h e s i si st of i n das o l u t i o nf o rs k e t c hu n d e r s t a n d i n g , i no r d e r t oe l i m i n a t ei t sa m b i g u i t y w et a k ea d v a n t a g eo fs i m p l ef r e e - h a n ds k e t c hw h i c h s u p p o r t sn o r m a lg r a p h i c sa p p l i c a t i o n b ys t u d y i n g t h ep r o b l e mo fs e m a n t i c s r e p r e s e n t a t i o na n ds e m a n t i c su n d e r s t a n d i n g ，w ed e s i g nas k e t c hu n d e r s t a n d i n gf r a i i l e a n dm o r e w et a k ei l s eo fs t a t i s t i c a ll e a r n i n gm e t h o d ，t r yt 0f r a m eaq u a l i t a t i v ea n d q u a n t i t a t i v et h e o r yf o rs k e t c hu n d e r s t a n d i n g t h em a i nc o n t r i b u t i o no ft h i s t h e s i s i n c l t a d e s ： f r e e - h a n ds k e t c ha n d e r s t a n d i n gb a s e do nh i d d e nm a r k o vm o d e l ：i l lt h el i g h t o ff a c tt h a ts k e t c hu n d e r s t a n d i n gi sf a m i l i a rw i t l ls p e e c hr e c o g n i t i o n , w el o o k o nu s e rh a b i ta ss k e t c hi n f o r m a t i o ni nt i m es e q u e n c e w ei n u o c i n c ch i d d e n m a r k o vm o d e l ( h m m ) ，w h i c hh a sb e e ns u c c e s s f u l l ya p p l i e di ns p e e c h r e c o g n i t i o n ，i n t os k e t c hu n d e r s t a n d i n gf i e l d w em a k ee x p e r i m e n t a lc o m p a r i s o n so fc o m m o nd e s c f i i p t i v ec a p a c i t y b y a n a l y z i n gu s e r s i n p u t t e ds t r o k e sa n ds o m ef a m i l i a rg r a p h i c su s e di nd e s i g n s o f t w a r e ，t h ee x p e r i m e n t a lr e s u l ts h o w st h a ta d a p t i v eh m mh a v eg o o d p e r f o r m a n c ei nf r e e - h a n ds k e t c hu n d e r s t a n d i n g w ea l s od e v e l o pag e s t u r e r e c o g n i t i o ns y s t e mb a s e do n q u i l l s y s t e m , i nw h i c hw eb u i l dh m m a l g o r i t h ma si t sc l a s s i f i e r k e yw o r d s f r e e - h a n ds k e t c h ，s e m a n t i c su n d e r s t a n d i n g h i d d e nm a r k o vm o d e l ，h u m a nc o m p u t e ri n t e r a c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨壅盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：多葫款签字日期：少p 年工月，g 日 学位论文版权使用授权书 本学位论文作者完全了解鑫壅盘茔有关保留、使用学位论文的规定。 特授权苤洼盘生可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 里乐寺、 导师签名： 签字日期：少9 f 年j 月，f 日，签字日期： 协 矽j 月 彦 “ 母萨、w 第一章绪论 1 1 课题背景与意义 第一章绪论 随着多媒体技术的飞速发展，人与计算机的交流越来越方便快捷，而网络的 不断普及使我们可获得的信息以惊人的速度递增。计算机的影子已触及到社会的 各个领域，越来越多的人习惯于利用计算机协助完成工作。相对于计算机处理性 能的高速发展，人类控制和使用计算机的方式的发展却相对非常落后，这严重影 响了计算机的高性能计算资源的利用率。人类使用和控制计算机的方式一般包含 两个过程：向计算机发送控制或计算指令和计算机反馈控制或计算结果，这一通 讯过程通常被称为人机交互( h u m a nc o m p u t e ri n t e r a c t i o n , h c i ) ，完成这个通讯过 程的媒介被称为用户界面( u s e r i n t e r f a c e ) 1 1 。用户界面在人机交互过程中负责 管理计算机的输入和输出，它决定了人们使用计算机的方式m y e r s 2 】等人对此 作了的深刻阐述，人机交互过程中通过用户界面交换信息的多少是影响计算机资 源使用效率的关键因素之一。因此，用户界面相关的研究已经成为愈来愈多的计 算机科学研究人员关注的焦点。用户界面的研究从计算机诞生之日起就开始了， 经过了五，六十年发展，其形态已经发生了重大的变化。从早期的批处理方式， 命令行界面，菜单界面到当今主流的图形用户界面，以及目前研究中的笔式交互， 三维用户界面，语音界面等，从早期以计算机系统为中心到如今以人为中心的用 户界面，人机界面愈来愈人性化，智能化和个性化。另外，新的交互设备的出现 也大大推进了用户界面的研究j a c o b1 3 1 在人机交互输入设备一文中做了详细介 绍，虽然它们大都还停留在实验室阶段，但为更自然，智能，高效的用户界面奠 定了基础。其中，笔交互设备以其独一无二的优势使得它作为其中一个佼佼者成 为学术界和产业界的研究热点。 早在1 9 6 3 年s u t h e r l a n d 就提出了笔式交互思想。他设计的s k e t c h p a d 【4 】是第 一个笔式交互系统。该系统使用光笔在阴极射线管显示器上指点和标记图形。他 的灵感来自于现实的生活中人们习惯于用笔书写一些通用的符号或者标志来完 成意图表达。笔的一个最为鲜明的特性是易于控制，可以进行高效自然的勾画， 而且基于纸笔的工作方式是人们数千年来进行信息捕捉和表达的一个有效途径， 无论是文字或图形都可以自然勾画在纸上x t h l i u ，j i n & s u n 2 0 0 2 【5 1 。 笔式交互技术经历了曲折的发展历程，随着m a r kw e i s e r 提出“遍在计算” 思想f 6 】以及计算机硬件性价比的不断提高，笔式交互技术的研究越来越受到 研究者与业界的重视。 第一章绪论 根据笔式交互系统的应用范围的不同，我们大致可以简单将它分为：支持 创造性工作，支持信息交流和捕捉，支持思想捕捉和基于g u i 的笔交互增强， 栗阳【7 】。它的意义在于： 第一：笔式交互的4 e 精确性和表达图形文字信息的方便性以及交互方式的自然 性，使得它非常适合早期的，概念设计阶段的创造性工作，人们早已熟悉使用 纸和笔向听众讲解某个处理流程的原理，某种产品的性能或者自己的创新的思 想等，这样的信息交流方式是一个非常自然的活动。 第二；许多灵感的颤动都是瞬问的事情，需要用户使用最快最自然的方式记录下 来，而传统的一些电子记录工具要求许多细节信息的录入，当用户局限于细节信 息的时候，灵感的火花已经熄灭了。由于笔的易控性和高效自然性的特点，使得 它毫无疑问地充当起捕捉思想火花的重任。 1 2 课题的内容与研究现状 作为笔式交互技术的核心内容，草图理解的困难是如何根据用户的笔输入来 理解其意图。这主要包括草图语义表达和语义理解两个方面，其中语义表达指的 是将通过笔式交互获取的模糊的草图表达映射至精确的图形表达，它更注重于图 形形状构成，而语义理解则是将用户输入的草图图形映射为某个领域内具有特定 含义的对象，它相对更注重草图图形所具有的含义或草图图形相互问的关系，由 于用户意图通常与其应用领域和目标密切相关，而且草图语义表达和语义理解可 以看成是用户笔划输入在不同应用层面或从应用视角的映射，因此，它们的界限 不是绝对的，此外，作为一种输入方式，草图理解还存在着二维和三维的区分， 但是草图理解关注更多的是从模糊草图图形向用户意图的转化。 草图理解就是要建立一种消除笔式交互固有的模糊性的机制，在用户交互的 过程中挖掘草图的内涵信息逐步获取用户的精确意图，使计算机能够正确理解草 图。前入学者的研究，一般的草图理解系统在逻辑上可以分为三层：应用理解， 草图识别和笔式交互界面，其结构如图1 之所示。 其中，应用理解层利用特定应用领域的背景知识对已经识别出来的草图进行 理解和推理，主要是理解用户的意图和蕴藏在草图中的创新想法： 草图识别层 对用户输入的草图形状进行识别，发掘用户输入的草图信息中的形状信息，这一 层处理通常只与物理形状和几何信息相关，不涉及应用领域相关的语义知识。笔 式交互提供给用户有一个便捷的草图绘制平台，并在草图绘制过程中快速采样， 尽量获取用户输入的所有信息，这是所有笔式交互的基础。 第一章绪论 i应用理解 l j i草图识别 j i交互界面 i多领域应用 i n i 统一形状表示 【 i草图识别 儿 i交互界面 图1 2 草图珲解系统的逻辑结构图1 3 面向多领域的系统的逻辑结构 草图理解的这三个层次相互影响，每一层都对用户输入的数据进行一次抽 象，同时也为上层提供处理数据，同时上层同时根据处理结果对下层的计算提供 反馈和指导。不是所有的草图理解系统总是可以清楚的分为这三个层次，有的系 统把草图识别和应用理解融合起来，共同完成针对对于某一个特定领域的草图计 算。 用户输入的草图本身只包含模糊的形状信息，但如果把草图与目标应用相结 合，就赋予草图丰富的语义。草图在不同的应用领域可能含有不同的语义，即使 在同一应用领域，不同上下文背景也可能赋予草图拥有不同的语义。为了屏蔽草 图应用语义的多样性，a l v a r a d o 8 1 等提出了面向多领域的草图理解框架这个框 架把与领域无关的草图识别和与领域相关的理解推理分隔开，此时草图理解系统 的逻辑结构如图1 3 所示。 草图理解相关技术的研究从笔式交互诞生时就已经开始。它的历史一样可以 追溯到i v a ns u t h e r l a n d 的s k e t c h p a d 系统，尽管受时代背景和技术条件的限制， 其性能，功能和效果远未达到草图理解的程度，而仅仅只能作为一种人机交互方 式。二十世纪九十年代中期，草图理解技术及其应用研究进入了新的阶段，书写 接口技术已成为多通道用户接口技术中知觉用户接口技术p u i ( p e r c e p t u a lu s e r i n t e r f a c e ) 【9 】的一个重要组成部分。迄今，在草图理解技术方面发表了大量研究 成果其中典型的有 1 0 ，1 1 ，1 2 ，1 3 ，1 4 ，1 5 ，1 6 ，1 7 ，1 8 ，1 9 ，2 0 ，2 1 ，2 2 ， 2 3 ，2 4 】，并成为诸如s i g c h i ，i f i p t c l 3 和a p c h l 等学术团体和学术会议的 重要研究内容，而a a a i 在2 0 0 2 年春天召开的“s k e t c hu n d e r s t a n d i n g ”专题讨论 会上所发布的研究成果则集中反映了草图理解领域的最新研究进展。d e m i n 【2 5 ，s a t i n 【2 6 ，s i l k 2 7 】，t a h u t i 2 8 】，t i v o l i 2 9 和f l a t l a n d 【3 0 】等是其中 非常有代表性的原型系统。 第一章绪论 1 3 本文的研究契合点机器学习 机器学习这门学科所关注的问题是：计算机程序如何随着经验积累自动提高 性能? ，而机器学习的核心是学习。历史上，关于学习有过很多不同的说法，但 是大家比较公认的是s i m o n 对学习的阐述：“如果一个系统能够通过执行某种过 程而改进它的性能，这就是学习。”在这个定义中阐述了三个要点：学习是一 个过程，学习是对一个系统而言的，学习能够改变系统性能。因此不难想象 机器学习的研究同认知科学、逻辑学、心理学、教育学，数学和哲学等学科必然 有着密切联系。机器学习对专家系统、计算机自动推理、智能机器人、自然语言 理解等方面产生重要的推动作用 3 l 】。机器学习的研究工作主要是围绕以下三 个基本方面进行的：学习机理的研究：学习方法的研究；面向任务的研究。 3 2 】 在1 9 5 7 年f r o s e n m a t t 提出了第一个学习机器的模型，称为感知器，这标志 着人们对学习过程进行数学研究的真正开始。从概念上讲，感知器的思想并不是 新的，它已经在神经生理学领域中被讨论了多年。但是，r o s e n b l a t t 把这个模型 表现为一个计算机程序，并且通过简单的实验说明这个模型能够被推广。感知器 模型被用来解决模式识别问题，在最简单的情况下就是用给定的例子来构造一个 把两类数据分开的规则。关于感知器的实验广为人知后，人们很快提出了一些其 他类型的学习机器，如：b w i d r o w 构造的m a d a l i n e 自适应学习机、k s t e i n b u c h 提出的学习矩阵等，实际上他们已经开始了构造特殊的学习机器硬件。与感知器 不同的是，这些机器从一开始就被作为解决现实中实际问题的工具来研究，而没 有被看作是学习现象的一般模型。为了解决现实中的实际问题、人们还开发了很 多计算机程序，包括创建各种类型的逻辑函数的程序，如最初为专家系统目的设 计的决策树、隐含马尔可夫模型等，这些方法也没有涉及到对一般学习现象的研 究。在感知器之后，关于构造一般性学习机器的研究的下一步是在1 9 8 6 年完成 的，这就是用所谓后向传播技术 3 3 ，3 4 】同时寻找多个神经元的权值。这一方 法实际上开创了学习机器研究历史的一个新时代。后向传播技术的发现可以看作 是感知器的第二次诞生。从感知器的第二次诞生到现在过去l o 多年了。从概念 上看，感知器的这第二次诞生的重要性小于第一次。虽然在一些特殊领域中应用 神经网络取得了很重要的成果，但是所得到的理论成果并没有对一般的学习理论 带来多大贡献。而且，在神经网络的实验中也没有发现新的有意义的学习现象。 实验中观察到的所谓过适应( o v e r - f i t t i n g ) i 佶q 题，实际上是在解决不适定问题的理 论中称之为“错误结构”的想象。由于神经网络是基于经验风险最小化结构，所以 无法从根本上解决过适应的现象。另外，用户神经网络采用的自动调整网络的权 重，是一个黑盒子，用户无法监控系统的训练，不利于应用主动学习。 第一章绪论 现在，更多的注意力放在了对神经网络的替代方法的研究上，比如，人们用 很大的精力进行了对径向基函数模型的研究0 5 1 。就像在6 0 年代一样，神经网 络又被叫着多层感知器。统计学习理论中的较高深的部分现在开始吸引更多的学 者。尤其是在过去的几年里，结构风险最小化原则和最小描述长度原则成了人们 分析研究的一个熟点。与渐进的理论形成对照，关于小样本理论的讨论广泛开展 起来。 本文工作综合考虑了人机角色转变中的交互方式和草图语义模糊性与多样 性等问题，主要针对手绘草图理解中的语义的表达与语义理解问题进行了初步的 研究和探索，从机器学习的角度解决草图理解中的关键问题，参考语音识别领域 内获得成功的隐马尔可夫模型( h m m ) 学习方法，提出手绘草图理解的自适应 h m m 方法。通过学习用户的历史数据，建立用户的绘画习惯模型。利用不同的 特征表示方法，以及在不同的参数选择下，对h m m 进行了实验对比，为此做了 一些相关的工作。 1 自适应h m m 学习方法 在已有h m m 的基础上，针对手绘草图理解的特定问题，提出了自适应h m m 的学习方法，实验表明：自适应h m m 的学习方法不仅可以很好地解决手绘草图 理解中的用户适应性问题，而且可以减轻用户收集样本数据的工作量。 2 手绘草图理解在不同特征表示下的对比实验 利用目前在线识别中常用的特征表示：r u b i n e 特征，转角函数和组合特征 对h m m 方法进行了实验对比。实验表明：组合特征和自适应h m v l 的组合可以 较好地解决在手绘草图理解中的用户适应性问题。基于自适应h m _ m 学习可以在 少量样本的基础上获得良好的效果，具有较强的用户适应性，消除了因用户随意 输入带来的困难。 3 基于h m m 的手势设计 用手势识别开发模拟复杂的手绘草图理解的开发，在q u i l l 手势识别原形系统 的基础上，进行了一定量的建模和编码工作，在内部实现机制上采用了h m v l 建 模。各章的具体内容概括如下： 第二章：介绍了手绘草图理解系统的方案框架，对各模块解决的几个关键 技术：交互策略，特征表示，建模方法，识别策略等分别做了相关阐述。针对在 第一章绪论 线手写识别领域内的特征选择问题进行了相关阐述，介绍了目前常用的几种特征 选择方法：转角函数，r u b i n e 特征，组合特征的概念。 第三章：从理论上详细分析了隐马尔可夫模型的三个问题及其解决方法， 基于隐马尔可夫模型，针对手绘草图理解中的时序，适应性等问题提出解决方法。 分析指出传统h m m 在解决用草图理解中的优缺点，并在此基础上提出了自适应 h m m 概念。 第四章：采用不同特征表示和参数选择，对手绘草图中的用户意图理解进行 了实验，从实验结果上证明了h m m 解决手绘草图领域草图理解问题的可行性。 通过传统h m m 和自适应h m m 的实验对比证明了后者的适用性。 第五章：手势是草图的简单样本，手势识别可以认为是草图理解的简单应用。 本章介绍了将h m m 引入手势设计中的应用。用手势识别开发模拟复杂的手绘草 图理解的开发。在其内部实现机制上采用了h l v i m 建模。 第六章：结束语，提出进一步可能的研究方向。 第二章草图理解的系统模型 第二章草图理解的系统模型 2 1 智能人机交互系统 智能人机交互的最终目的是为了让机器能适应人的思维方式，更好地理解用 户的意图，从而提供给用户更加自然流畅的交流方式。从功能上划分，智能人机 交互系统由三个部分组成，分别是多通道感知接口，识别，理解运用 3 6 。 三个模块既相互联系又有一定的独立性，如果将整个智能交互系统看成是一 个完整的“人”，交互界面就是人的皮肤，负责和外界的交流，也是外界对人“的” 唯一感知，识别子系统就是人的骨架，它支撑起整个系统，起承上启下的关键作 用；适应性就是人的大脑，它负责将所有的信息消化并加以吸收，从而提高自身 的适应能力。要想使三个模块各司其职，并能发挥出最大作用，需要利用到许多 领域内的不同技术。交互界葱中，为了能使用户更自然地和系统交互需要同时使 用不同的交互方式，而这正是多通道感知接口领域的研究范围；理解部分的难题 是如何利用用户相关和领域相关的信息将用户不同的表示理解成为正确的语义 对象，这就需要利用用户适应性和领域适应性的研究成果。相比之下，识别部分 是目前交互领域内的研究重点，技术方面相对成熟。 2 2 草图理解系统框架 基于手写人机交互的研究早在上世纪六十年代【4 】就已经开始，但在以后的 很长一段时间内没有得到重视，直到八十年代中期，这方面的研究才又开始恢复。 经过十多年的发展，已经取得了一定的成就，特别是手写字符方面已经出现了诸 如汉王笔的成熟商用产品。但是，在手绘草图领域，虽然m i t ，c m u ，b e r k e l e y ， t o k y o 等著名研究机构投入大量精力，也设计出许多原型系统，但在一些关键技 术尤其是适应性方面取得的进展甚微，这也导致了在线草图交互系统的研究仍处 在实验阶段。另外，当前绝大多数基于草图的人机交互系统仅包含了交互界面和 识别子系统。而结合语义的理解子系统的研究则比较少，因此，要想在基于草图 的人机交互领域取得突破，草图语义理解系统是研究的关键 3 7 。 智能人机交互系统的三个主要构成部分：交互方式，识别和理解应用。相比 其它的交互系统，基于手绘草图的交互系统有其自身的特殊性，主要表现在： 第二章草图理解的系统模型 在交互方式上，以视觉为主要感觉方式，以鼠标，键盘，手写笔，输入板等 为主要媒体。信息传递主要通过手绘草图完成，用户也可以通过g e s t u r e 对 已有的草图进行编辑。 手绘草图的语义的理解主要表现在用户意图的理解，用户的图形表述习惯， 笔序输入习惯，以及一些使用偏好等都对草图语义的理解有关联，相对于其 它的在线交互系统，手绘草图领域内的用户相关信息与草图理解联系系密 切。而用户相关的信息隐含在草图以及一些交互动作中，系统很难捕获。另 外，用户的图形表述习惯以及使用偏好具有时变性，即用户对同图形在不 同时期会有不同的理解，相应地构图方式以及输入习惯也会变化；而随着系 统使用的频繁，用户的偏好以及对系统的要求也会发生变化，这都增加了草 图理解的难度。 2 2 1 方案框架 基于手绘草图的智能人机交互中，从最初输入的草图到最终的意图猜测，需 要经过三个阶段：草图输入，草图识别和适应性辅助理解。在草图输入阶段，用 户通过笔式交互工具在输入设备上绘制草图，形成的点序列在显示设备上表现为 前后相连的笔划；在草图识别阶段，系统利用笔划之间的空间关系以及输入笔划 的时序信息将其归并成图形并进行初步的识别；在适应性辅助理解阶段，结合特 定的用户信息以及用户与系统的反馈来调整识别结果，使其符合用户的输入意 图。其中适应性辅助理解阶段最为关键，它降低了系统识别的普遍性和用户理解 的特殊性之阁的语义鸿沟，提高系统的扩展性和实用性。目前手绘草图领域内的 研究主要集中在识别上，而对用语义理解性，适应性问题考虑甚少，提出的原型 系统都有一定的局限性。本文提出的自适应草图识别系统利用了交互过程中的用 户信息对草图提供辅助识别。由于笔划空间关系以及笔划时序信息与用户的输入 习惯密切相关，而相对于隐蔽的用户习惯更易提取，因此，我们的自适应草图识 别框架中根据这些信息对用户建立模型，并利用这些模型识别提供指导。方案框 架如图2 - 1 所示。 交互界面： 交互界面接受的是用户输入的笔划和用户评价指导信息，反馈的是系统的识 别结果。在输入过程中，可以利用多通道技术记录用户的一些习惯，如笔端压力， 倾斜角度等，这些信息可以作为用户的固有信息用于建立用户模型。 第二章草图理解的系统模型 图2 1 草图理解框架模型 预处理 用户输入的时候，由于不小心或者输入习惯而产生的干扰笔划或信息，这些 信息不利于机器的学习、识别。需要处理的信息包括：用户起笔和落笔形成的勾 和拐角处形成圆圈等。 特征抽取 用户的输入笔划是按照时间来采样，即时间点序列采样。这种方式虽然能完 整地记录用户的所有信息。但是这种方式形成特征的维度往往比较大，而且维度 也不确定，不利于学习。所以时间点序列采样得到的样本需要进行特征抽取。我 们分析了目前在线识别系统中常见的几种特征表示方法，并针对草图的特点提出 了一种组合特征，经过实验证明具有较好的效果。 分类器 在笔划识别部分里，我们使用机器学习的方法进行笔划识别。这种方式有利 于适应多用户，也可以适应同一用户随着时间推移而不同的习惯，从而使笔划识 别具有较强的鲁棒性。我们采用的学习方法是h m m 。 用户库 保存各个用户模型，好多时候由于分类器本身精度比较低，需要根据用户库 中的信息对分类的结果进行评价，若存在错误，需要其提供正确的类别一最后需 要收集用户的数据，如果是库中已有的用户信息就对其进行更新，若是新用户， 就将其存储下来，为学习机制提供数据。 第二章草图理解的系统模型 用户模型 详细描述用户的信息，主要包括用户输入的笔划信息以及笔划问的关系以及 经过分类器识别出来的草图类别。当用户模型比较稳定后，可以抽取当前草图的 特征并与模型中的信息相匹配，若匹配成功则根据用户的历史习惯实时判断草图 的类别，并给用户以提示。若不成功则将其作为新用户数据用于学习，并建立新 的用户模型。用户可以接受用户模型的帮助，也可以对系统识别结果进行干预。 图形库 负责对图形的增，删，改，保存被识别出的图形信息便于以后的识别。图形 库的数据进行层次化存储。邵复杂图形信息由基本图形信息及其空问组合信息构 成。 2 2 2 用户建模及交互策略 用户模型是根据用户相关的信息建立的刻画用户行为的模式。这些模式往往 是一些符合特定语法的规则，用来指导系统对用户的某些行为做出正确的响应， 以符合用户的需求。用户建模的目的是为了提供给用户符合他们特定需求的服务 或者信息。为此必须获取与之相关的用户知识。用户建模从用户的角度出发，在 系统中根据用户的个性特征建立模型，从而使系统具有智能化，满足不同用户的 要求。在草图识别系统中，识别过程本身就是与用户息息相关的，同一领域中的 多个用户及多领域中的单用户的草图输入方式都存在差异，草图的笔划基本上是 随意的，草图构成与笔划数目和笔划顺序无关；同时，草图绘制过程是用户思维 过程的反映，草图识别往往与输入过程紧密相关，所以从用户模型的角度出发进 行草图识别将大大优于基于草图构成元素及相互关系的模板匹配的草图识别方 法。 用户信息的获得有两种方式：系统( 设计者) 预定义的和通过用户交互获取 的。前者适用于特定领域内少量用户参与的适应性系统，如早期的一些专家系统 以及小型在线学习系统。这类系统的使用者往往具有相似的知识背景，对信息的 需求相同，因此便于系统预先制定一些指导规则方便系统和用户的交互。但对于 在线识别系统来说，用户的知识背景，喜爱偏好千差万别，系统很难对每一个用 户预先定义其用户模型，因此更为实际的方法是在与用户交互的过程中获取用户 的信息，如何获取以及获取怎样的用户信息将直接影响用户模型是否能有效地帮 助系统适应不同的用户。而这正分别对应了用户模型中的两个关键问题：交互策 略和用户特征表示。 利用用户建模的方法可以让系统学习用户绘画多笔复杂图形时的习惯和方 第二章草图理解的系统模型 式，系统从而可以轻而易举得识别出用户的复杂图形。但是，用户建模并不是单 独起作用的，它必须结合一定的识别策略来共同建立草图识别系统中用户适应性 机制。正如形式化描述中所说，识别策略的目的是在用户模型的指导下在原始草 图和用户意图之间建立准确的映射。到目前为止，在线识别领域内常用的识别方 法可以分为以下凡类： 统计类方法： 基于圆锥曲线方程的线性最小平方匹配法，能实时地分类草图笔划，识别直 线，椭圆弧和圆角。 模糊类方法t 用模糊逻辑和模糊知识，从草图的位置，方向，速度和加速度捕获绘图者的 意图，进而实现草图识别。 几何方法； 有学者把手绘草图作为整体进行识别，需要进行平滑处理，提取圆弧段，识 别结点，分解出直线段，再根据相邻三点的矢量建立角度相似函数，采用夹角角 度值作为圆弧和直线段的提取特征，并给出角度的实验阈值，然后再进行分类。 神经网络方法t u l g e n 等通过提取图素几何形状的内角特征，用二进制突触的权重算法( 含 有一个隐层的前馈网) 进行识别的方法。该类方法以整体方式识别三角形，椭圆 和矩形三种图素，但仅适用于绘图包和掌上电脑的自动手绘输入。中提出模糊样 条曲线识别器f s c i ，并训练三层前向神经网络实现模糊分类规则，可识n 7 种图 素( 直线，圆，圆弧，椭圆，椭圆弧，开式自由曲线和闭式自由曲线) ，但各图 素均限制在水平，垂直和四分角方位，并且对于不同的使用者需要重新训练神经 网。 其它机器学习方法， 彭2 0 0 3 3 8 1 抽取简单图形的转角函数特征，利用s v m 对在线手绘的简单图 形进行识别，s u n g2 0 0 3f 3 9 】利用b a y e s 网对手写韩文进行识别，另外还有利用 隐马尔可夫模型( h m m ) 对拉丁字符，公式以及数字的在线识别做了一定的研究工 作。上述几类方法中，机器学习方法引入人工智能领域内的一些技术，通过学习 让系统逐渐适应用户，这种机制更符合人的思维模式，因此已成为在线识别领域 解决用户适应性的主要方法。 第二章草图理解的系统模型 2 3 特征选择 模式识别问题中，在训练分类器的时候，往往需要特征向量维数确定的样本 集。样本集中各样本的每一维都是该样本的一个特征。显然这些特征的选择是很 重要的，它强烈影响到分类器的设计及其性能。如果不同类别之间的特征差别很 大，那就比较容易设计出具有交好性能的分类器。因此，特征选择是模式识别中 的一个关键问题。由于在很多实际问题中常常不容易找到那些最重要的特征，或 者受到条件的限制不能对这些特征进行测量，这就使得特征选择和提取的任务复 杂化从而成为模式识另系统中最困难的任务之一。这个问题已经越来越受到人们 的重视。 根据描述角度的不同，草图识别领域内的描述特征可以分为两类：一类是 图形相关的特征，如：r u b i n e 特征 4 0 ，4 1 和转角函数；另一类是用户相关特 征，如个性化特征( p e r s o n a lf e a t u r e s ) 提取方法 4 2 】如输入笔端的压力，手与输 入设备之间的倾斜角度等。由于设备的限制，个性化特征难于获取，另外，草图 的形状以及输入的笔序往往包含了用户的个性信息，因此本文主要着眼于图形相 关的特征。 与图形相关的特征可以分为几何特征和动态特征，几何特征主要描述的几何 构成，包括草图形状，笔划问的空间关系，动态特征主要描述图形与时问相关的 特性，如输入草图总共花费时间，某一个笔划内的输入速度，加速度等；从另一 个角度来看，特征也可分为全局特征和局部特征两类。全局特征是由草图的所有 采样点的数据计算而得，如输入的时间，笔划数；输入的平均速度( 加速度) ， 最大速度( 加速度) ，速度( 加速度) 的过零次数；输入时的平均压力，最大压 力等。局部特征则是在笔划的每个采样点上计算出来的数据，如该点的速度，压 力等，对于局部特征，由于采样点的频率比较高，所得的数据中有很多冗余，不 能把所有的采样点用于分类器设计，必须从中选取特征点。一般是通过重采样和 通过分析形状的特征来提取特征点。 基于笔划和图形的特征提取方法大致上可以分为三类： 1 使用直观上人们很容易理解的特征，如环，交叉点和端点等。在手写字符和 g e s t u r e 识别方面，很小的几何特征就能给出令人惊讶的良好识别效果 4 0 ， 4 1 1 。 2 使用特征映射，将图形映射到大小统一的点阵中。 3 利用变换进行特征提取( 如傅立叶变换，g a b o r 变换) ，这种方法提取的特征 第二章草图理解的系统模型 v ， + 2 ， p 卜。 v ， s 图2 1 多边形和它的转角函数 4 向量维数没有限制，可以根据问题的复杂程度和网络的结构进行选择，这种 方法往往满足旋转、平移以及大小的不变性，如转角函数方法。 目前在线草图识别领域内比较有代表性的特征提取方法有转角函数，r u b i n e 特征，速率曲率特征，重径特征等。下面章节首先对它们进行简单介绍，并在速 率曲率特征以及重径的基础上，结合在线草图识别用户适应性的特点，重点介绍 组合特征的概念。 2 3 1 转角函数 转角函数方法由提出， 【3 8 】将其应用到基于支持向量机( s t l 印r tv e c t o r m a c h i n es v m ) 的增量学习中，对封闭的简单图形( 圆和凸多边形) 提取特征，取得 了良好的效果。 转角函数0 。是图形z 上关于弧长s 的一个函数，它标志了从么边界上的 初始点d 开始到当前点( 沿逆时针方向转过弧长为j 的点) 累积的转角( 逆时针方 向为正，顺时针方向为负) 。其中o 。( d ) 为选取的初始点d 的切线方向与某一特 定方向( 例如水平方向) 的夹角。具体如图2 - 1 所示： 因为处理的图形与它们的大小和位置是无关的，所以还要对记录下来的用户 图形进行归一化，即将图形的周长调整为l 。然后使用转角函数对图形进行特征 提取，得到一个d 维的特征向量。在使用转角函数的过程中，我们又加如了一定 的限制，制定转角函数的值在( o ，抚】的区间内，并且初始点的值为0 。定义转角 函数如公式： 第二章草图理解的系统模型 矿：j 土一i f 里型o f d ( 2 1 ) l 妒，+ 2 石矿妒， 和h m m 模型 a = 叫，e 汀) ，如何计算观察序列对h m m 的输出概率e ( o l a ) 。 2 状态序列选择问题：给定观察序列o = d 。，d ：，唧，如何确定一个 最优的状态转移列| ，= ，i 2 ，i r 3 模型参数的估计问题：如何调整a = 口，b ，巧) 的参数，以使p ( oia ) 最 大。 第三章基于隐马尔可夫模型的草图理解 下面分别针对以上三个问题进行解决。 3 3 2h m m 三个问题的求解方法 3 3 2 1 输出概率的解决一前向概率和后向概率 给定观察序列o = 0 。，口：，一唧) 和h m m 模型a = 似，e 石) ，如果已知状态转 移序列，= i i 屯，i r ，则h m m 模型a 以状态转移序列，输出观察序列d 的概率 为： f ( o l ，a ) = ( q ) 6 ( d ) 。, h i ( q ) ( 3 1 ) h m m 模型九输出序列，的概率为： e ( 1ia ) = 厅 口h j ：口讪”4j r - j 母b _ ( 0 ) ( 3 2 ) 而这里需要考虑所有可能的状态转移序列，因此，根据全概率公式，模型 输出观察序列d 的概率e ( o l a ) 为： e ( o l = p ( 0 1 1 , x ) p ( i i a ) ( 3 3 ) j = 庙。气( d 1 ) 口。( d ) a t l i r 。( q ) ( 3 4 ) f 这个式子的计算复杂度为o ( n 7 ) ，这在实际运算中是无法承受的，为了降低 计算量，可以采用前向算法和后向算法结合的策略。 h m m 的前向概率和后向概率 首先定义h m m 的前向概率为： 0 0 0 ) = p ( o , 0 2 ，q ，吼= ij a ) ( 3 5 ) 表示给定h m m 模型参数a ，部分观察序列 o 。0 2 ，q ) 在f 时刻出于状态j 的概率。 前向概率哦o ) 可以用下面的递推公式计算： 1 初试化： 0 0 ( d ；，r 岛( q ) ，1 s f n ( 3 6 ) 2 迭代计算： 口。+ i ( ，) 爿瑾，( o a q l q ( q “) ，1 s f t - 1 , 1 _ ，n ( 3 7 ) 第三章基于隐马尔可夫模型的草图理解 3 终止计算： p ( o i | ；l ) = 嘶( f ) ( 3 8 ) 1 f ；l 与前向概率相对应，定义后向概率为： p ，u ) = e ( o ，“q + 2 ，口r ，q ，= ，i 旯) ( 3 9 ) 表示给定h m m 模型参数a ，观察序列在t 时刻处于状态，系统给出部分观察 序列如+ 。q 。，吩，的概率。后向概率历( d 也有类似的递推公式计算： 1 初试化： 3 ，( f ) = 1 , 1 s i 蔓n ( 3 1 0 ) 2 迭代计算： n 屈( f ) = 嘞q ( q “) 届+ l u ) ，1 f t - i ，1 _ ，s n ( 3 1 1 ) j i 利用前向概率和后向概率计算输出概率，前向概率公式和后向概率公式将整 个观察序列对h m m 模型的输出概率分成两个部分观察序列的输出概率的乘积， 而且它们各自都有相应的递推公式，可以大大简化计算。经过分析，可以得到下 面的递推公式： n e ( o l a ) ；口，( o 屈( 力= a ，( f ) ，1 f - t 一1 ( 3 1 2 ) j = li = l 实际上，这就解决了前面提到的三个问题中的第一个问题，上面的公式也可以表 述为下面的形式： p ( oa ) = a ，( o a , p j ( o , 。) 肛+ 。( ，) ，l t r l ( 3 1 3 ) t f f i l ，；l 在实际计算中首先计算出对于每个，和每个状态i 的前向概率和后向概率，然后 利用上面的公式，计算出该观察序列对模型的输出概率。这两个公式也成为全概 率公式。 3 , 3 2 2 最优化问题的解决一v i t e r b i 算法 v i t e r b i 算法是种广泛应用于通信领域中的动态规划算法。利用全概率公 式，可以计算出系统的输出概率，但是无法找到一条最佳的状态转移路径。利用 v i t e r b i 算法，不仅可以找到一条足够好的状态转移路径，还可以得到该路径对 应的输出概率。同时，用v i t c r b i 算法计算输出概率所需要的计算要比全概率公 第三章基于隐马尔可夫模型的草图理解 式的计算量小的多。动态规划算法得到的结果通常是满意，但并不是最优的， 因此只能找到足够好的路径，而不是最好的路径。 v i t e r b i 算法的递推形式为： 1 初始化 4 = 以6 ( d 1 ) ，1 i s n ( f ) = 0 2 迭代计算 ( 3 1 4 ) ( 3 1 5 ) 6 ，( 歹) = m 。a ；。x 1 6 t - l ( f ) 吗 b j ( o f ) ，2 t g t , l _ ，( 3 1 6 ) y ，( _ ，) = a r g m a x i 玩- 1 ( f ) 口。i ，2 t t ，1 _ ，s n ( 3 1 7 ) 1 5 j 3 终止计算 p m a x 5 t ( i ) g ；= a r g m a x , s r ( f ) ( 3 1 8 ) j ， 4 回溯最佳路径 g ：= l f ，+ l ( q 二1 ) ，1 f t - 1 ( 3 1 9 ) 在上述的公式中，6 ，国为f 时刻第，状态的累积输出概率，帆为f 时刻第，状 态的前状态号，g ：为最优状态序列中t 时刻所处的状态，p 为最终的输出概率。 实际上，对于我们常用的状态转移只能局限于自身和下一个状态的h m m 模型来 说，在第二步计算中每次可能遇到的路径选择只有两个，与全概率算法相比并没 有减少多少计算量。在实际使用中，通常用对数形式的v i t e r b i 算法，这样将避 免进行大量的乘法计算，真正地减少了计算量，同时还可以保证有很高的动态范 围，而不会由于过多的连乘而导致溢出问题。对数形式的v i t e r b i 算法如下： 1 预处理 丌f = l o g ( x ，) ( 3 2 0 ) b ，( o t ) = l o g 【以( 口f ) 】 ( 3 2