（模式识别与智能系统专业论文）基于支持向量机的复合草图形状识别方法.pdf

中文摘要 草图形状识别是草图语义理解的基础，它可分为两个顺序的、循环的阶段： 简单草图形状识别和复合草图形状识别。简单草图形状识别已得到较为广泛的关 注，而复合草图形状识别得到的关注则较少 支持向量机是一个通过核函数将输入空间影射至特征空间再进行训练的线 性分类器系统，基于泛化性理论和最优化技术来求解问题。虽已有些基于支持向 量机的简单草图形状识别的研究工作，但基于支持向量机的复合草图形状识别的 研究还很少，并且没有充分利用支持向量机强大的学习、分类和泛化功能。 本文提出一种基于形状空间约束的复合草图表示方法，并设计了一个基于 d a g s v m 的复合草图形状识别算法。该算法利用了笔画的时间信息，综合了基 于相似度的算法和基于分类器算法的优点。具体工作包括： 1 在综述草图识别的研究现状和基本方法的基础上，提出了一种新的基于 简单草图形状空间约束的复合草图形状表示方法。 2 根据r b f 核参数的特征，设计了一个启发式参数搜索算法，减少了参数 搜索范围，提高了格搜索的效率。 3 基于所提出的复合草图形状表示方法，设计了复合草图形状的d a g s v m 分类器。 4 开展了简单草图形状和复合草图形状的实验研究，实验结果说明了所提 出的表示方法和识别算法是可行的。 关键词：复合形状表示支持向量机草图识别格搜索 a bs t r a c t s k e t c hs h a p er e c o g n i t i o ni st h eb a s i so fs k e t c hs e m a n t i cu n d e r s t a n d i n g ，a n di t c o n s i s t so ft w os e q u e n t i a la n dc y c l i cp h a s e s ：p r i m i t i v es k e t c hs h a p er e c o g n i t i o na n d c o m p o s i t es k e t c hs h a p er e c o g n i t i o n t h ef o r m e rg o tal o to fr e s e a r c ha n d p r o g r e s s ， w h i l et h el a t e rg o tl e s sa t t e n t i o n s u p p o r tv e c t o rm a c h i n e s ( s v m ) i sas y s t e mf o re f f i c i e n t l yt r a i n i n gt h el i n e a r c l a s s i f i c a t i o nm a c h i n e si nt h ek e m e l i n d u c e d f e a t u r e s p a c e s ，w i t hu n d e r l y i n g g e n e r a l i z a t i o nt h e o r ya n do p t i m i z a t i o nt h e o r y h o w e v e r , t h e r ea r e 佗ww o r ko f c o m p o s i t es k e t c hr e c o g n i t i o nb a s e do ns v m ，a n dt h ee x i s t i n gw o r k sh a v en o t 协k e n f u l l a d v a n t a g eo fs v m p o w e r f u lc a p a b i l i t yo f l e a r n i n g ，c l a s s i f i c a t i o n a l l d g e n e r a l i z a t i o n t h et h e s i sb r i n g sf o r w a r da c o m p o s i t es h a p ed e s c r i p t i o nm e t h o db a s e do nm e s p a c ec o n s t r a i n t so fp r i m i t i v es h a p e s ，a n dad a g s v mb a s e d r e c o g n i t i o na l g o r i t h mi s p r o p o s e dc o r r e s p o n d i n g l y t h ea p p r o a c hm a k e su s eo ft i m es e q u e n c ei n f o r m a t i o no f s t r o k e s ，a n di n t e g r a t e st h ea d v a n t a g e so ff e a t u r e b a s e da n ds t r o k e b a s e dr e c o g n i t i o n a p p r o a c h t h em a i nc o n t e n t sc a nb es u m m a r i z e d 嬲f o l l o w s ： 1 ) t h es t a t e - o f - a r t so fs k e t c hr e c o g n i t i o na r er e v i e w e df i r s ti nt h et h e s i s w ep u t f o r w a r dan e wc o m p o s i t es k e t c hs h a p ed e s c r i p t i o nm e t h o db a s e do ns p a c e c o n s t r a i n t so f p r i m i t i v es h a p e s 2 ) w ed e s i g nah e u r i s t i ca l g o r i t h mo fp a r a m e t e rs e a r c hw i t ht h el a wo fr b f k e r n e lf u n c t i o n t h ea l g o r i t h me n h a n c e st h e e f f i c i e n c yo f 西ds e a r c ha n dt h e p a r a m e t e rs c o p ei sr e d u c e d 3 ) ac o m p o s i t es h a p er e c o g n i t i o na l g o r i t h mb a s e do nd i r e c t e da c y c l i cg r a p h s s v m ( d a g s v m ) i sp r o p o s e d 4 ) t h ee x p e r i m e n t sh a v es h o w e dt h ef e a s i b i l i t yo ft h en e wm e t h o d 锄d 吐l e r e c o g n i t i o na l g o r i t h m k e yw o r d s ：c o m p o s i t es h a p er e p r e s e n t a t i o n , s u p p o r tv e 曲wm a c h i l l e s s k e t c h r e c o g n i t i o n ，g r i ds e a r c h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：孛天叫 签字日期： 一伽刁年。明口岁日 学位论文版权使用授权书 本学位论文作者完全了解墨注盘堂有关保留、使用学位论文的规定。 特授权苤盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 支1 文司1 签字日期：伽可年吃月哆日 导师虢秘步穸 签字日期：w q 下1 月岁日 第一章绪论 1 1 研究背景 第一章绪论 草图理解( s k e t c hu n d e r s t a n d i n g ) 是人工智能领域的一个新兴的分支，旨在自 动或半自动地从草图或绘制中正确地抽取语义知识。草图理解系统使得用户可以 捕捉绘制者设计者的思路，使得彼此间的交互如同在纸面上涂鸦一样自然。 草图理解的研究可以追溯到2 0 世纪6 0 年代i v a ns u t h e r l a n d 关于s k e t c h p a d 1 】 的工作。但是由于2 0 世纪7 0 年代鼠标的出现以及广泛应用，基于w i m p ( w i n d o w , i c o n ，m e n u ，p o i n t ) 的界面逐渐占据了人机交互的主导地位，草图交互方式的研究 进入一个相对缓慢的阶段。进入2 0 世纪9 0 年代，随着网络技术的兴起和硬件技 术的发展，移动计算和普适计算成为计算机技术的一个重要发展方向，小型化、 无线化的设备逐渐多样化。特别是数字墨水( d i g i t a li n k ) 等显示技术和平板计算机 ( t a b l e tc o m p u t e r ) 的出现极大推动草图输入及相关技术研究和应用。迄今为止已 经出现了智能纸张( i n t e l l i g e n tp a p e r ) 的产品，数字墨水和草图也成为继数字文本、 图像和视频之后的新兴电子化多媒体数据类型。在计算机辅助建模和设计【2 j 、人 机界面和网页等布局设计【3 】【4 】、可视化对象建模网、计算机支持的协同工作【6 】、 g i s 导航和指挥r 丌、基于内容的多媒体检索【引、虚拟现实环境【9 】、远程教学和数字 办公【l0 j 等多种场合和多个领域都出现了对草图输入技术的研究和应用。 2 0 0 2 年3 月2 5e t 至2 7 日，美国人工智能协会( t h en a t i o n a lc o n f e r e n c eo n a r t i f i c i a li n t e l l i g e n c e ，a a a i ) 在斯坦福大学召开了首届草图理解春季研讨会，标志 着草图理解研究进入了一个崭新的时期。草图理解之所以受到如此地重视，主要 是因为其潜在的巨大的实用价值和理论价值。从用户角度看草图能够快速自由的 记录思想，适于短期记忆；由于其本身固有的模糊性和抽象性，使用户不必局限 于细节问题。从应用的角度看草图理解系统力图结合纸笔交互的灵活性和计算机 在数据处理方面地高效性、快捷性【l ，使得人机交互更加简便。从理论研究角度 看，通过草图语义的定性与定量层面上基本特征的研究，可以比较好地处理草图 语义的歧义性和草图形式的随意性；通过研究草图语义表示、草图识别方法，可 以进一步发展机器学习方法，尤其是基于统计的学习方法，提高现有方法的稳健 性和可操作性。 国外学者对草图理解技术进行了广泛的研究，出现了大量的研究成果，形成 第一章绪论 了很多非常有价值的原型系统。麻省理工学院( m a s s a c h u s e t t s i n s t i t u t eo f t e c h n o l o g y , m i t ) 的人工智能实验室在r a n d a l ld a v i s 的领导下在多领域的草图识 别框架【1 2 1 ，草图描述语言【1 3 】【1 4 1 ，特征点检测【1 5 】【1 6 - 1 ，构建基于b a y e s 网络的草图识 别框架b t 1 s 等方面进行了深入研究，并讨论了i - m m 模型在基于用户潜在的绘制 顺序下的效果【l 圳；在机械设计和u m l 等领域实现了草图理解的原型系统，如 s k e t c h r e a d l 2 0 ，a s s i s t , t a h u t i j 。加州大学柏克利分校( u n i v e r s i t yo fc a l i f o r n i a b e r k e l e y , u c b ) 的j a l a n d a y 在文章中指出一个尚未被大家充分认识到的重要原 则：计算机应当服从于人的交互方式，而不是其他的方式；成功的p u i s ( p e r c e p t u a l u s e ri n t e r f a c e s ) 应当在设计阶段保持草图而不加解释，这个因素对于保持交互流 畅性至关重要瞄j 【2 3 1 。利用动态规划方法给出一个基于模板的草图符号分割算法 【2 4 1 ；并且开发了支持草图理解系统的工具包s a t i n 2 5 1 和o o p s 。卡纳基梅隆大学 ( c a r n e g i em e l l o nu n i v e r s i t y , c m u ) 给出了一个多笔划符号的识别器1 2 刨；设计了一 种利用几何推理和物理推理的方法来理解物理装置示意图的方法 2 7 1 ；s i l k 2 8 】是 j a l a n d a y 在该大学期间设计的一个支持界面设计的草图理解系统。西雅图华盛 顿大学( u n i v e r s i t yo fw a s h i n g t o ns e a t t l e ，u w s ) 建筑学院通过草图在本领域的应 用，提出了一个广泛意义上的课题1 2 9 ：形式和功能、语义和语法之间的区别、联 系以及如何交互来共同的完成设计的功能：而草图理解需要两者分开处理以简化 问题，但是又要联合起来才是完整的过程；草图理解过程可看作是设计推理的过 程。里斯本大学( u n i v e r s i t yo f l i s b o n ) 的研究人员给出了基于模糊逻辑和几何特征 的识别算法，结合可扩展的启发式信息集合设计了c a l i 在线草图识别器【3 0 】；并 使用此识别器设计了一个可视化的设计用户界面的静态部件s k e t c h j a v a l t l 3 。 国内研究机构从纸笔交互的界面隐喻、体系结构和识别算法等不同角度对草 图理解进行了研究，取得了很多不错的成果。中国科学院软件研究所的栗阳等人 【3 2 j 设计实现了笔式用户界面开发工具p e n b u i l d e r ，允许用户自由笔式输入支持多 种笔交互信息和灵活的事件的处理。微软亚洲研究院的多通道用户界面组正在研 究和探索先进的用户界面技术，其正在研究的智能数字墨水能够帮助人们在电脑 上用自己的笔迹随意书写，用墨水记录自己的思划3 3 1 。南京大学计算机软件新技 术国家重点实验室孙正兴教授等人也对此开展了相关研究，从c a d 系统出发对手 绘草图识别进行了研究，取得了一系列成果【3 4 】【3 s l 。 1 2 研究目的 草图理解根据用户绘制获得草图的形状信息，进而捕捉和理解用户意图。它 从用户连续的笔划输入增量地提取轨迹信息，应用一定的机器学习方法消除草图 2 第一章绪论 输入的随意性，给出草图的规整形式；进一步根据图形间的关系，结合上下文信 息和领域知识，消除语义模糊性，推理、理解用户意图。 草图理解的首要任务是草图的识别，即对单个草图形状对象构成元素以及之 间的几何、拓扑关系进行识别。应当注意n - 在同一领域中的不同用户或者同一 用户在不同时刻的草图输入方式都存在很大的差异；草图的笔划基本上是随意 的，草图构成与笔划数目和笔划顺序无关。所以草图识别是非常艰巨的任务，系 统应当尽可能小地限制用户的绘制习惯。 草图绘制过程作为用户思维过程的反映，往往与用户输入过程紧密相关。草 图形状的确定性也随着用户绘制的进行逐渐凸现的过程，这是将一个笔划集合分 割为若干个然后再明确为某个特定领域的、有意义实体的过程。它允许计算机随 着笔划的绘制对其进行解释，可以由下面两个顺序的、循环的子问题构成：简单 草图形状识别和复合草图形状识别。简单草图形状( p r i m i t i v es k e t c hs h a p e ) 也称为 基本图形、图元，本论文中包含的元素有：线段、弧线、波浪线、箭头、椭圆、 三角形、四边形、五边形、六边形。简单图形可能由单个笔划构成，也可能是笔 划中部分，还可能是多笔划组合。复合草图形状( c o m p o s i t es k e t c hs h a p e ) 在本论 文中定义除去简单形状之外的所有图形符号都为复合形状。复合形状是若干简单 形状在几何、拓扑关系上共同表现出的在某个领域中具有特定意义的图形符号。 草图识别的研究已经有很长时间也取得了很多成果。其中简单草图形状识别 问题获得相对广泛研究和相当的进展，而复合形状的识别问题得到的关注则比较 少。主要是因为对于大多数的应用，简单图形识别可以基本满足需求；在需要较 复杂图形识别的少数场合仅稍少作修改就能胜任。而且已有工作对于草图识别的 歧义性和手工草图的随意性等这个问题并没有彻底解决。从本论文出发认为复合 图形识别不仅仅在未来的实际应用而且在理论方面都存在很大的研究空间。所以 论文在简单草图形状识别的基础上主要集中讨论复合草图形状识别问题。 1 3 本文工作 本文将基于统计学习理论的支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 方法 应用到复合草图识别系统中，充分利用s v m 强大的学习。、分类和泛化能力，对 草图识别问题进行了研究。s v m 是统计学习理论的v c 维理论和结构风险最小 化原则的具体实现，根据有限的样本信息在模型的复杂性和学习能力之间寻求最 佳折中，以获得最好的推广能力。s v m 是一种崭新模式分类、机器学习方法。 由于其强大的学习、分类性能，已经在手写体数字识别、人脸识别、文本分类、 生物信息学、基于内容的图像检索等许多领域取得了成功的应用。文章还引入了 第一章绪论 一个格搜索的启发式原则用于s v m 识别器训练过程中，降低了原始格搜索的查 找范围，提高了获得优化识别器的效率。 针对上一章节中提出的复合草图形状识别的问题本篇论文给出一种复合草 图形状的表示方法，在此基础上提出了一个识别算法。算法利用笔画的时间、空 间信息，综合了基于相似度的算法和基于分类器算法的优点。初步的研究表明该 算法可以处理不同用户、不同场合下的草图绘制顺序问题，在某种程度上解决了 由于绘制顺序导致的歧义性问题。 本文的主要工作包括以下几个方面： 1 详细介绍草图识别的研究现状和所采用的方法。为进一步提高草图的识 别率，提出了一种新的基于简单草图形状空间约束的复合草图形状表示方法。 2 在实验过程中发现对r b f 核函数的参数进行格搜索时候存在某种规律， 利用该规律设计了一个启发式算法，该算法的应用减少了参数搜索的范围。 3 对复合草图形状固有的模糊性和丰富的信息承载能力进行了系统分析， 详细介绍了s v m 方法如何通过降低绘制的歧义性并进一步进行识别的过程。 1 4 文章结构 本文将以复合草图形状识别为主要目标，以降低草图识别的歧义性为手段， 结合领域的特征，设计并实现了一个复合草图识别算法，全文共分为六章： 第一章：简单介绍草图识别的研究背景，总结草图识别的发展历程并介绍 国内外关于该领域的发展状况。介绍了研究的目的和本文所作的工作，给出文章 的整体结构。 第二章：详细介绍常用的草图识别的识别技术和典型的原型系统。给出了 较常用的简单草图形状识别和复合形状识别算法。分析了在这些常用方法中存在 的问题。 第三章：系统介绍了论文使用的的s v m 方法理论基础，详细论述了它的组 成要件和赖以工作的原理。 第四章：基于r b f 核函数的特征设计了启发式搜索算法，改进了格搜索效率； 详细描述了复合草图形状表示方法。 第五章：详细描述简单形状识别、复合形状识别的处理过程和相应的算法， 并通过实验示例说明了方法的可行性和性能。 第六章：总结全文，提出进一步的研究方向。 第二章草图识别概述 第二章草图识别概述 草图识别是草图理解的基础。草图广泛用于早期设计中，作为表达想法的重 要工具可以指导思维的进行，也可以用于保存信息。但是手绘草图在外形上不够 美观，在表达和存储形式上也不够简约，也不利于计算机的存储和处理【3 6 】。前面 章节看到很多草图识别系统已经开发来处理该问题。 从用户的角度来看，草图识别系统应当满足如下四个条件：不应对图形符 号的笔划数目进行限制，不应对图形笔划的输入顺序加以限制，不应对图形 的倾斜度或其它几何特征加以限制，识别结果的呈现和系统提供的反馈不应干 扰用户的绘制和思路。前三点主要针对草图系统的输入：系统的输入应当允许用 户有尽可能大的自由度；最后一点对草图识别系统的输出方式进行了限制：应在 合适的时机以合适的方式把当前的识别处理结果反馈给用户【1 2 1 。从研究者的角度 看，草图识别系统应当满足如下三个条件【37 】：能够处理草图的多样性和模糊性， 能够提供实时性的响应，有较强的可扩展性，能以比较简捷的方式扩展到新 图形和新领域。 草图识别将手绘的草图识别为已知的图形，并为下一步的理解提供基础。它 的过程是匹配一个笔划集合为某个特定领域的、有意义的实体。它允许计算机随 着笔划的绘制对其进行解释，可以由下面两个顺序的、循环的子问题构成： 1 ) 简单草图形状识另t ( p r i m i t i v es k e t c hs h a p er e c o g n i t i o n ) ：用户的一个或者几个 笔划绘制完成之后，根据用户的意图判定其简单形状的类别( 可以是线段、 椭圆、三角形、矩形等) ，然后根据给定的函数准则计算该形状的具体参数。 2 ) 复合草图形状识， u ( c o m p o s i t es k e t c hs h a p er e c o g n i t i o n ) ：如果可能，将识别的 简单形状同以前识别的形状根据彼此间存在的时间和空间关系进行合并。进 一步决策或预测复合形状的类别并计算具体的参数值。 接下的章节首先介绍目前为止简单草图形状识别的技术手段和进展。然后给 出复合形状识别两类常用技术。最后指出已有技术中存在的问题。 2 1 简单草图形状识别 笔划预处理的主要任务是要消除笔划中的噪声，得到笔划的精简表示形式。 简单图形分类方法总体可以分为基于模板匹配和基于统计两类。文章主要介绍六 第二章草图识别概述 种简单图形识别方法：基于r u b i n e 特征的识别算法、基于决策树的识别算法、 基于滤波器的识别方法、基于能量最小化的识别方法、基于转角函数的识别方法、 基于正规化重径的识别方法。 2 1 1 笔划预处理 笔划预处理主要用来消除隐含在笔划中的噪声，得到精简的多边形或者规则 的曲线。预处理后的笔划是输入的笔划的精练形式，应当于原笔划尽量相似。笔 划中的噪声指冗余的笔划信息，包括冗余点、重描( o v e r - t r a c e ) 和折点。 笔划由多线条组成，许多线条到其相邻点构成的线段的距离很小。消除这些 点并不会对图形的外貌产生明显影响。因此某种程度上这些点称为冗余点。对这 些冗余点可以使用精确的直线或者曲线段来代替，这样仅需要少数的控制点信 息。这里的控制点一般指笔划的拐角。笔划的拐角是刻画草图形状特征的重要信 息。由于用户在绘图时，通常在拐角处的笔速会变小，而曲率会增大( 图2 1 ) ，因 此可以应用笔划的速度和曲率数据来定位拐角，作为笔划的特征 2 6 1 。s e z g i n 结合 笔划方向、笔划的速度和曲率信息，使用均值过滤方法检测笔划的拐角1 5 】【1 6 】 3 羽。 其中笔划的速度根据笔划采样点问的距离与所用时间间隔求得，曲率的符号可通 过平滑窗口方法获得。根据检测到的拐角把笔划分割成直线段和曲线，使用分段 线性近似算法拟合直线段，使用b e z i e r 曲线拟合曲线部分。最后根据图元之间的 关系改进拟合结果、得到规整的图形。 但是对于不同的笔划获取硬件、不同的用户，得到的笔速和曲率有很大差别， 需要根据情况调整相应参数。尤其是对于一些非常杂乱的笔划，均值过滤方法不 能很好地处理其中的噪声，拟合后的图形总是含有假顶点。为了解决噪声的干扰 问题，可以结合尺度空间( s c a l es p a c e ) 方法检测拐角【3 9 1 。 重描指的是用户对某些绘制过的笔划重新绘制，以使得图形更完美；这会产 生近似素描画的效果，但对于识别来说却是一个难题。折点包括钩子和圈两种情 况。钩子产生于笔端开始接触或将要离开输入板时手的颤动；圈一般产生于笔划 转折处。上述错误一般无法在冗余点消除过程中处理，将在很大程度上影响后继 结构化属性的抽取。折点部分的曲率比较大，所以其附近节点的密度远远大于其 他部分。所以折点可由线条曲率或节点密度来判断并消除1 4 0 l 。对于笔划任一折线 图2 - l 矩形的笔划和它对应的方向、曲率和速度数据 6 第二章草图识别概述 段，若其相对节点密度大于某给定阈值，则认为该折线段的顶点均为折点，可用 这部分顶点的重心进行替代。 2 1 2 简单草图形状识别 笔划预处理完成之后，可以对其进行特征抽取和图形的分类。简单图形分类 模块对笔划预处理模块得到的精简笔划进行处理，根据用户的意图判断其所属的 基本图形类别。这方面已经有了相当多的工作，下面给出主要方法的简单介绍。 ( 1 ) 基于r u b i n e 特征1 4 1 i 的简单草图形状识别算法 r u b i n e 分类器是一个可训练的、单一笔划的手势识别器，它使用了经典的线 性判别训练算法。r u b i n e 特征是一种统计特征，该特征起初用于识别单笔划特征 手势。它通过应用1 1 个几何特征和2 个数学特征组成的1 3 维的特征向量表示手 势笔划。它们是手势笔划起始角的余弦值，i ，起始角的正弦值压，矩形闭包对角 线的长度万，矩形闭包对角线的倾角压，起点和终点的距离居，起点和终点连线倾 角的余弦值后，起点和终点连线倾角的正弦值力，手势的长觑，转角总枷，各 点角度的绝对值之和五o ，各点角度的平方和币l ，手势的最大绘制速度，j 2 ，绘制手 势的持续时间_ ，i 3 ( 如图2 - 2 所示) 。通过训练可以为这1 3 个特征分量分配合适的 权重k ，其中c 是手势类、0 f f ，肋特征的个数这里等于1 3 ；利用如下线 性判别函数来识别手写的特征手势，其中c 表示整个手势类： 上 1 l ，。= w 印+ z ，0 c u o f j ( 2 - 4 ) 慨+ 2 万i f 仍 为正规化重径( r g r ) 。将此序列作为b p 神经 网络的输入，分类器的训练算法中采用梯度下降算法和冲量项的适应学习方法。 正规化重径特征具有一定的抗噪声能力。 2 2 复合草图形状识别 目前为止主要有两种方法来处理复合草图形状识别问题：基于相似度的方法 和基于分类器的方法。 盖嚣匹亟至= 0 3 压圃t 压亟芦 图2 - 5 基于r g r 和b p _ a n n 草图识别的算法 1 0 第二章草图识别概述 2 2 1 基于相似度的方法 基于相似度的方法中，首先需要定义两个复合图形之间的相似度以及如何计 算。复合图形被分为几个简单图形部分，可以是笔划段或者简单闭合图形。利用 简单图形的属性作为节点，之间的关系作为边，构建复合图形的描述图。这种图 称为属性关系图( a t t r i b u t e dr e l a t i o ng r a p h ，a r g ) 5 1 j 或者区域邻接图( r e g i o n a d j a c e n tg r a p h ，r a g ) 等。在使用图表示复合图形结构时：复合图形间相似度的 一问题就转变为如何计算对应的描述图之间的相似度，这通常被称为图匹配【5 2 】。最 后最相似的图形被选择出作为识别结果。同基于统计的方法相比该方法的一个特 点是不需要大量的训练数据，另一特点是易于扩展。但该方法通常包含子图匹配 问题，计算代价比较大。已证明经典子图同构( 精确匹配) 是一仰问题，所以基 于相似度的方法一般会引入某些技巧来降低图匹配算法的复杂性。 c a l h o u n 等在【2 6 j 中首次提出将一个复合图形分为多个简单笔划，并在一个语 义网中表示它们之间的关系。每类图形的定义需要很少的样例( 3 4 个) ，笔划速 度和曲率用于将笔划分割为简单图形。识别过程中同输入图形相比具有最小误差 的对象被认为是识别结果。c a l h o u n 尝试了两种识别方法：一种假设符号以同样 的顺序进行绘制，这种方法比较快；另一种方法是最优搜索的一种变形，它允许 绘制顺序不同。s m a r t s k e t c h p a d 5 3 】也使用了基于相似度的方法。嗍引入了基于约 束的部分枚举算法，可以在用户绘制完成前作出结构的预测。 2 2 2 基于分类器的方法 a l v a r a d o 的s k e t c h r e a d 2 0 】将草图识别的两个子过程也可以作为个统一的 过程。系统采用动态构建的贝叶斯网络来进行图形符号的识别，其中每个图形符 号用一个贝叶斯网络片段来描述。底层节点对应的是简单图形和其空间关系，高 层对应的是复合图形的类别。采用这种方法的优点有两个：第一点保存了图形内 部结构的信息，能够更好的进行笔划分组。贝叶斯网络既能够进行自下而上又能 够进行自上而下的推理，系统不但能够根据用户输入的部分笔划提供的信息来推 断出用户的意图，还可推理不完整复合图形所缺少的笔划；第二，系统允许用户 自由的勾画图形，这个特点会造成笔划分割模块在分割基元时产生错误。贝叶斯 网络一方面可以把这种分割歧义性表示在网络的条件概率表中，另一方面网络的 推理机制使得系统对每个输入笔划的理解都都受到它周围的笔划的影响，使得系 统能够从底层模块的识别错误中恢复过来。鉴于手工构建网络的繁琐性，廖士中、 王晓军【5 5 j 给出采用机器学习的方法来构建贝叶斯网络。用户提供勾画样例，系统 从样例中抽取笔划信息和结构信息，并应用k 2 学习算法得到贝叶斯网络。 第二章草图识别概述 图2 - 6 多笔划草图的转角函数 基于转角函数的简单图形分类算法通过改进也可以处理复合图形识别。在提 取出来离散的笔划信息的基础上，加入各个笔划之间的空间位置关系和绘制顺序 信息。可以将用户绘制的每一笔的终点和下一笔的起点用线段连接起来，使得用 户输入的基本图形可以看成一条完整连续的曲线，如图2 6 所示。粗点为起点， 箭头表示绘制时的笔划方向。图中有两类信息：用户输入的原始笔划信息( 粗线 条表示) 和改进的表示空间和绘制时序的关系信息( 细线条表示) 。将图中连续的曲 线作为一个整体抽取它的转角函数特征 s s l ，然后用s v m 方法进行识别。该识别 方法拥有较好的识别率。但该方法易受噪声影响；而且用户相关性较大不易扩展。 上述方法没有充分利用s v m 强大的学习、分类和泛化能力，有待进一步改进。 2 3 存在的问题 下面首先介绍已有的简单草图形状识别算法的缺点，然后描述了现存两个复 合图形识别算法的不足。 r u b i n e 方法是一种统计方法，具有较高的识别率，能比较准确地识别单笔划 符号；有时这种方法不能区分两个明显不同的手势。基于决策树的离线图形识别 算法对于在线图形的识别不够稳定，这是因为很难将笔划没有歧义地分割为离散 的线段。基于滤波器的方法对于处理特征上区分不明显的图形如五边形、六边形， 并且该方法的扩展性不好。能量最优化算法存在的缺点是局部最优。应用转角函 数所抽取的特征和参考点的位置有关，并没有充分利用笔划的时间信息。而且该 方法要求草图必须是单笔输入的，容易受到噪声的影响。正规化重径特征方法与 用户的绘图习惯有很大相关性，计算复杂度比较高。 在基于相似度的算法中的缺点是它们对噪声敏感，并且当绘制形状较少的时 候健壮性不够好。基于分类器的方法中s k e t c h r e a d 对于复合图形的识别率不高 不能用于实际，而且得到图形描述也不是简单的任务。基于s v m 的方法依赖统 计机器学习，在近年来逐渐引起了研究人员的重视。这类方法的特点是具有很好 的稳健性，缺点是需要大量的训练数据。采用该类方法建立的分类器不易扩展， 但允许用户自由地、多笔划绘制草图，用户可以重新按照自己的绘图习惯重新训 练分类器，具有一定的用户适应性。 侈冲 第三章s v m 理论基础 3 1 线性学习器 第三章s v m 理论基础 线性判别理论在人工智能领域由于r o s e n b l a r 提出的感知机而受到关注，感 知机是第一个学习机器的模型，标志着人们对学习过程进行数学研究的开始。 最简单的是两类情况，即用给定的例子来构造一个分类器把两类数据分开。 令朦示输入空间，壤示输出空间，通微f ，y c _ r ，对于两类问题】，= + 1 ， 二l 。训练集是训练样例的集合一般表示为：( ( x l ，y 1 ) ，( 1 2 ，y 2 ) ( x ，蝴) 。，为训练 样例的个数，x 沩样例其形式为( x l ，x 2 ，硝，弦称为x 肭标记。两类问题的分类 通常由实值函黼用来做判别函数，a x b - - ( w x ，川) 耋。则x t 分为正勤= 1 ， 否则分为负撕= 一l 。决策规则由s 印( 及x ) ) 给出。即输入和输出有下列关系： y = s 缈( ( x ) ) = s 印( + 6 )( 3 - 1 ) = s g n ( e ；。哗薯+ 6 ) ( w ，6 ) 是控制函数的参数，w 称为权重向量，6 为偏置。为得到决策函数必须 从训练样例中学习c ，功。根据决策规则和公式( 3 - 1 ) 知若得到的( w ，6 ) 对任意伍， 曲( 卢1 乃棚x f ) - - 0 ，则学习到决策函黼。r o s e n b l a r 感知机迭代算法如下： 1 ) 初始化( b k ) 为( o ，0 ) ，七表示权值更改的次数，初始值为0 。 2 ) 若训练数据中的下一个样例( x 轴l ，胁1 ) 被正确分类。( w b k ) 保持不变。 3 ) 若样例( x 斛l ，胁1 ) 被错误分类，虽口胁l ( + b ) - - 0 ，则修正( w 岛b k ) ： w “2w i + 弘x j 吃+ l = 气+ r l y , r 2 ( 3 _ 2 ) k = k + 1 4 ) 若遇到训练数据末尾而3 ) 中没有错误则结束，否则返回2 ) 。 其中叩为正数称为学习率，r = m a x x 圳( 卢l d 为输入样例模的最大值。如果 训练数据是线性可分的，已证明该算法通过合适的参数可以保证收敛到某个解向 量【5 9 1 。最终w ，贝x ) 的对偶形式可以表示为训练数据的线性组合： ， 1 1 w 2 乙a , y , x f 扭1 ，( 3 3 ) ， 、一， ( x ) 兰 + b = 呸只 + b 第三章s v m 理论基础 为得到好的解向量提出间隔的概念。( x f ，蝴相对超平面( w ，6 ) 的函数间隔扮： 乃= y , f ( x 。) ( 3 _ 4 ) 超平面( w ，6 ) 相对于训练集的间隔分布是指间隔集合( ) ，l 您们的分布。( w ，6 ) 相 对于训练集的函数间嘞指间隔集合( y l ，) ，2 们中的最小值。对( w ，6 ) 使用规一化 操作( w 4 1 w l l ，b l l w l l ) ，那么函数间隔p 成为相对于训练集的几何间l 辗i p l l w l l 。不特别 指明以后用p 来表示几何间隔。使彻最大的超平面称为最大间隔超平面。另一个 比较重要的概念是样例伍f ，蝴相对于( w ，6 ) 和某个间隔) ，的间隔松弛变量6 每( ( w ，6 ) ，y ) = m a x ( o ，r - y , f ( x ；) ) ( 3 5 ) 铆时耽舡f ) 耋o ，x f 被( w ，6 ) 误分。的咖f ) 耋o ，x 放( w 6 ) 正确分开。 n o v i k o f f 在1 9 6 2 年给出了关于感知器的第一个定理，这标志着学习理论的 开始。定理指出若训练集线性可分，使用感知机算法可以在次修正之后收敛： n 纠r 2 p 2 】( 3 6 ) 但是感知机算法给出的仅仅是解集合妖x ，力) ( 这里令，= = 佃t t 以方便讨 论) 中的一个。为得到最优的分类暑歌i ，曲，需要使预测的期望风险： ，r ( 伍) = i l ( y ，厂( x ，a ) ) d f ( x ，y ) 其蚴y 胞呦= 窖嚣炉酣伍叻) 弋3 。7 最小。三f y , 久x ，神) 为损失函数代表预测值同真实值之间的差距；联合概率分布f ( x ， 力未知。上述风险最小化模型还有很多其他的应用：对回归估计问题样例数据变 为( ( x l ，y o ，( x 2 ，弦) ，( x ，如) ，弦矿，相应上 a x , 酌) 三陟- 贝x ，力) 2 ，其帆力 口彳为实函数集合；对密度估计问题样例数据变为( x l ，x 2 ，i i ) ，需要从密度 函数集p ( x ，a ) a g a 中估计密度函数，相应的损失函数三a x , ) 兰一l o g p ( x , 力。 对公式( 3 7 ) 稍作修改得到学习问题的一般表示：给定在空间x 上的未知概率 测度只x ) ，考虑函数集合3 ( x ，反) 废a 。学习的目标是最小化风险泛函： r ( o t ) = ij ( x , c t ) ) d f ( x ) 旺a ( 3 8 ) 其中y ( x ，a ) 是损失函数，前面给出的三个三 炽，口) ) 都是这一函数的特例。为最 小化公式( 3 8 ) 采用经验风险最小化( e m p i r i c a lr i s km i n i m i z a t i o n ，e r m ) 归纳原则： ( q ) = 篙酶伍) ( 3 - 9 ) 将风险泛函r ( 口) 替换为经验风险泛函风m p ( ，用使得见m p ( 瘦) 最小化的地劫来逼 近使月( 力最小的函数地投哪力。这个准则定义了一个新的学习过程，为求解最优 的分类锹x ，p t ) 的公式( 3 7 ) 建j - 应的问题转变为： r 呷( 仅) = 三( y ，f ( x ，a ) ) ( 3 1 0 ) t = l 对应的回归估计和密度估计问题需要最小的泛函变成如下形式： 第三章s v m 理论基础 回归估计r 叩( c 4 0 = ( 以一厂( 墨，伍) ) 2 i = 1 1i 密度估计足呷( a ) = 一i n p ( x ，n j 3 2 核函数特征空间 ( 3 1 1 ) 需要学习的目标函数的复杂程度往往取决于数据的表达方式。原始的数据量 称为属性，描述数据的量称为特征【6 l 】。虽然原始数据无法使用线性分类器区分开， 但可以通过将其映射到另一特征空间来使用线性分类器： x = ( 五，吃，) 屿少( x ) = ( ( x ) ，( x ) ，( i ) ) ( 3 一1 2 ) 映射以) 由输入空间肢为特征空间f ，庐 以x ) ix 娜。一个说明性的例子如下： 函数g ( x l x 2 ，x 3 ) = g x p ( x i ) * x 2 2 x 3 4 ，显然该函数产生的样例集合不能用线性学习器 来表示。个简单的映射加l ：( x l ，x 2 ，x 3 ) 一( 1 n ( x 1 ) ，l n ( x 2 ) ，i n ( x 3 ) ) 给出表达式： 办( x l ，娩，而) = i n g ( x t ，x 2 ，物) = 孔+ 2 1 n x 2 4 l i l 而= x + 矽一4 z 那么对样例数据做相应的变换就可以用线性表达式来学习。 考虑另一个二维输入空间的例子，对于向量x ，y 定义函数 2 ： 强y 卟暖) ) 2 =c # ，! k 恐， 吃 = c 3 - 3 ， 该函数隐式定义了映射函数似x ) ，y ( x ) 的维数为3 。如果是一个以维输入空间情况 g 隐式定义的映射y ( x ) 的维数d i m ( v ( x ) ) 为( 时g 一1 ) ! n ! ( q 一1 ) l ，随着”、g 的增 大认x ) 的维数以指数形式增长，依赖于缈( x ) 的计算将无法进行。如何克服这种维 数灾难( c u r s eo f d i m e n s i o n ) ，考虑公式( 3 3 ) w ，胸的对偶形式可得到的结论： 上 f ( x ) 暑 + b = 只 + b ( 3 _ 1 4 ) i = l 这时候只要能够计算 需要运算的项数变为h l ，而在上述描述 中知道 = d ，这使得特征空间的维数不再影响计算。 上面过程启发了核函数的应用。核是一个函数匠对所有的x ，y e x , 满足： k ( x ，y ) = (3-15) 容易从上式中得到核函黼足对称性和c a u e h y s c h w a r z 不等式。对于训练数据 ( ( x 1 ，y 0 ，( x 2