（计算机应用技术专业论文）手绘几何图形的识别研究.pdf

武汉理工大学硕士学位论文 摘要 手绘图也称之为草图，是设计师在概念设计阶段表达其设计意图的常用表 达方式，它提供给设计师一个展现设计思维，开展创造性设计工作的平台。但 手绘图信息的模糊性和用户输入的随意性阻碍了手绘图识别技术的发展。随着 计算机软硬件性能的不断提高，计算机图形学、模式识别、人工智能和人机交 互技术等学科的迅速发展，目前同内外许多机构对基于人机交互技术的草图识 别展开了相关的研究，出现了许多具有代表性的识别方法，如基于笔划和图元 表示法、基于统计几何特征的方法等。本文对手绘几何图形识别理论与技术进 行了深入研究，并设计实现了相应功能的原型系统。 本文研究以几何特征为基础，在原型系统中提供了手绘图形，并采用基于 图元表示法对手绘图形进行识别：文中将图元分为：直线、椭圆弧、椭圆、圆 弧和圆以及其他= - i i e 二次曲线。根据图元表示法识别流程：图形绘制完毕后，首 先对组成图形的笔划组进行笔划分割，分割成基本的图元；笔划分割以笔划中 的曲率较大、绘制速度较低的采样点为依据，采用尺度空间法进行分割：接着 对每个图元进行直线性判断，对于非直线的图元采用二次曲线不变量理论对其 进行识别，并对图元拟合与矢量化描述；然后在图元识别的基础上，判断各个 图元间的位置关系，提取图元个数、闭合性、凹凸性等1 3 个特征数据，运用结 构模式识别理论对整个图形进行识别；最后根据图形规整规则对识别后的图形 进行规整矢量化输出。 本文基于图元表示法识别流程及相关理论，设计和实现了在线手绘几何图 形识别系统，并对文中提出的部分识别算法进行了有效验证；同时对常见几何 图形识别结果进行了分析。结果证明：基于图元表示法对常见手绘几何图形识别 速度快、准确率高；虽然系统还存在着一些需要进一步解决的问题，但其中的 一些识别算法对复杂图形识别及其他领域的草图识别有一定的借鉴意义。 关键词：手绘图，图元，笔划分割，尺度空间，图形识别，图形规整 武汉理工大学硕士学位论文 a b s t r a c t h a n d d r a w i n gg r a p h i c sa r ea l s ok n o w na ss k e t c h e s i t sac o m m o nw a yt o e x p r e s sd e s i g n e r sd e s i g ni n t e n tw h e nt h e ya r ei nt h ec o n c e p t u a ld e s i g ns t a g e a n d p r o v i d ed e s i g n e r sw i t hap l a t f o r mt od i s p l a yt h e mt h o u g l l ta n dc r e a t i v ew o r k s 1 1 l e f u z z i n e s so fs k e t c h e si n f o r m a t i o na n du s e r s a r b i t r a r yi n p u t h i n d e r e dt h e d e v e l o p m e n t o fs k e t c h r e c o g n i t i o nt e c h n i q u e s w i t hc o m p u t e rs o f t w a r ea n d h a r d w a r ep e r f o r m a n c ec o n t i n u e st oi m p r o v ea n dt h ed e v e l o p m e n to fc o m p u t e r g r a p h i c s ，p a t t e r nr e c o g n i t i o n , a r t i f i c i a li n t e l l i g e n c ea n dh u m a n - c o m p u t e ri n t e r a c t i o n t e c h n o l o g y m a n yi n s t i t u t i o n sh a v ed o n eal o to fr e s e a r c ho ns k e t c hr e c o g n i t i o nb o t h h o m ea n da b r o a da tp r e s e n t a n dt h e r eh a v eb e e nm a n ys k e t c hr e c o g n i t i o n a p p r o a c h e s s u c ha st h ea p p r o a c hb a s e do ns t r o k ea n dg r a p h i cu n i ta n dt h ea p p r o a c h b a s eo ns t a t i s t i c a lg e o m e t r i cf e a t u r e s t h i sa r t i c l ed o e ss o m ed e e p l yr e s e a r c ho n t h e o r i e sa n dt e c h n i q u e so fs k e t c hr e c o g n i t i o na b o u tg e o m e t r i e sa n dd e s i g n sa f u n c t i o nm o d e ls y s t e m 1 1 1 er e s e a r c hb a s e so nt h eg e o m e t r i cc h a r a c t e r i s t i c s n em o d e ls y s t e mp r o v i d e s af u n c t i o na b o u td r a w i n ga g e o m e t r i c 、析n lh a n d s a n dr e c o n g n i s e sg e o m e t r i e sw i t h t h ea p p r o a c hb a s e do ng r a p h i cu n i t 而eg r a p h i cu n i ti n c l u d e sl i n e , e l l i p s e ，e l l i p t i c a r c ，c i r c l e ，c i r c u l a ra r c f i r s t ，t h es y s t e ms p l i t st h es t r o k ei n t og r a p hu n i ta c c o r d i n gt o t h ef e a t u r e so ft h es t r o k ef i , o mt h es t r o k eg r o u pa f t e rd r a w i n gag e o m e t r i c i td e t e c t s f e a t u r e sf r o mt h es a m p l ep o i n t sa c c o r d i n gt ot h es t r o k ec u r v ea n ds p e e di n f o r m a t i o n a n du s i n gt h es c a l es p a c em e t h o d s e c o n dt h es y s t e mm a k eaj u d g m e n ta b o u tg r a p h u n i ti sal i n e ? a n di tr e c o g n i s e sn o n l i n e a rg r a p h i cu n i tw i t ht h et h e o r yo fc o n i c i n v a r i a n t t h i r dt h es y s t e md e t e c t st h ef e a t u r e so ft h ew h o l es k e t c ha c c o r d i n gt ot h e r e l a t i o n s h i pa m o n gg r a p h i cu n i t s s u c ha st h en u m b e ro fg r a p hu n i t , c l o s e d ， c o n v e x - c o n c a v ec h a r a c t e r i s t i c se t c t h e nr e c o g n i s e ss k e t c hw i t ht h et h e o r yo ft h e s t r u c t u r ep a t t e r nr e c o g n i t i o n l a s t l yt h es y s t e ma d j u s t st h er e c o g n i z e ds k e t c ha l o n g t h ea d j u s t i n gr u l e sa n dd i s p l a y si t 砀ea u t h o rd e v e l o p sas y s t e ma b o u tt h es k e t c hr e c o g n i t i o n0 1 1g e o m e t r i ca n d l i 武汉理工大学硕士学位论文 c o n f i r m st h er e c o g n i t i o na l g o r i t h m si nt h i sa r t i c l e w ea l s oa n a l y z et h er e c o g n i z e d r e s u l t t h er e s u l t sp r o v et h a t ：o u rs y s t e mh a sah i 曲s p e e da n da c c u r a c y o u rs y s t e m h a ss o m er e s t r i c t i o n b u ts o m eo ft h ea l g o r i t h m sh a v ea l s or e f e r e n c ev a l u ef o ro t h e r d o m a i n ss k e t c h k e yw o r d s ：s k e t c h i n g , g r a p h i c s u n i t ，s t r o k e - s p l i t ，s c a l es p a c e ，g r a p h i c s r e c o g n i t i o n , g r a p h i c sa d j u s t i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：勉蒸日期：丝2 1 ! ! ! 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：椎导师( 签名) ： 武汉理工大学硕士学位论文 1 1 引言 第1 章绪论 草图是设计师在设计构思阶段徒手绘制的简略产品图形。它以其简便、迅速 的方式表达出设计师对产品造型的设想，记录和捕捉瞬间即逝的灵感和构思， 有利于设计师进行创造性工作。但是传统的纸质草图难以修改，即缺少所谓的 “设计记忆 ，整个设计方案难于存储、整理、搜索和重用，尤其缺少有效的互 动式交互性能n 吲；而现今的绘图工具操作步骤繁琐，需从大量的菜单、图标、 工具栏中选择绘制图形，不利于捕捉设计师的瞬间灵感，阻碍其创造性工作。 随着计算机软硬件性能的不断提高，计算机图形学、模式识别、人工智能以及 人机交互技术的迅速发展，基于人机交互的草图识别技术已成为近几年的一个 研究热点。本文在此背景下，展开对手绘几何图形的研究。 1 2 手绘图 手绘图也称之为草图，它是一种自由、随意、靠直觉进行交互的工作模式， 是创新探索过程中进行图形思维的重要媒介和载体，是对人类有限的意念再现 能力的一种延伸，对于创新设计具有非常重要的价值。草图给设计师提供了自 然直接的交流方式，使设计师在设计时，不必受一些不必要的细节( 如大小、精 确位置、色彩等) 的干扰，能把瞬间的灵感表达出来，这对创新设计有重大的意 义。 纸笔绘图是设计师采用的一种传统设计绘图方式，但纸笔绘图也有其缺点： 当经过多次修改后，方案就会变得混乱不清，随着设计的进行，纸上草图往往 难以修改，也不能记下整个设计过程，即缺少所谓的“设计记忆”，若需要较大 的调整比如从另一个视角看造型效果，则需要重新绘图；另外，设计方案难于 存储、整理、搜索和重用，尤其缺少有效的互动式交互性能。而且，即使将画 好的各部分收集起来，也无法组合成一个整体方案口3 。 目前，许多绘图工具直接采用规则图元输入，例如m i c r o s o f to f f i c e ，v i s i o 以及大部分c a d 系统，在绘图时要求用户从大量的菜单和按钮中选择预定义 的标准图形，这样的方式也存在以下方面的缺点h 1 ： 武汉理工大学硕士学位论文 1 ) 输入不方便。用户发现绘制自己需要的图形时，往往要多次点击鼠标进 行选择，特别当有许多预定义的图形或对象时，用户很难记住n 嘎$ j l 选 择自己需要的图形。例如微软的v i s i o 中有1 0 0 0 0 个预定义组合图形供用 户选择，复杂的界面让用户感到难以适从。 2 ) 输入不自然。有些应用例如方案设计，需要用户随时随地地快速记录其 设计思路，而不是拘泥于某一细节，这与传统的以最终设计为目标的应 用是截然不同的。在这些系统中，选择预定义标准对象的过程往往会打 断用户的思路，从而阻碍用户平滑、流畅地体现其设计思想。 3 ) 不适合小屏幕掌上设备。对于p d a 等仅有笔输入界面的小屏幕掌上设备 来说，这种输入方式很不实际。因为大量的菜单和按钮会使得原本拥挤 的屏幕更加紧张，从而挤压用户的使用区域。 随着硬件设备的不断更新，如手写板、t a b l e tp c 的出现，基于p c 的交互式 手绘草图设计正逐渐成为设计师进行手绘草图设计的一种新的方式晦1 。但是手 绘草图输入的自由度较大，输入意图与领域背景、思维方式、手绘习惯和偏好 等多种特性相关，手绘过程也会受到图形结构和设备特性等多种环境因素的影 响，用户手绘图形的结构及其内部关联都带有很强的主观性。这给手绘识别带 来很大的难度。 1 3 手绘图识别 手绘图识别分为：联机识别和脱机识别，所谓 脱机一是指将通过特定的采 集系统( 如摄像机、扫描仪) 将图形以图像的方式采集并输入到计算机，然后识 别系统根据图像数据进行识别；联机识别则主要通过各种与计算机直接相连的 二维坐标输入设备( 手写板、光笔、数字化仪、鼠标等) 将笔的运动轨迹实时送 入计算机进行识别。 联机识别与脱机识别的主要区别在于获取数据方式不同，从而也导致了两 者识别方法也不相同。通常脱机识别数据是以矩阵i 厂( x ”y i ) i 来描述的，其中 f ( x i ，y ；) 为平面坐标( f ，歹) 处的图像灰度值，因此，在脱机识别系统中，原始数 据矩阵需要进行降噪、二值化、细化、跟踪等预处理；而联机识别的数据为一 维数据，可用二元序列( x 。，y 。) 来表示，即用手写笔迹的采样点坐标序列来表示。 联机识别的数据可以含有比脱机识别的数据更多的信息，除了采样点的坐标外， 还可以采集笔的移动速度和加速度以及笔尖的压力等。这些数据可以构成多维 2 武汉理工大学硕士学位论文 特征点列，为识别算法提供更多的信息。另外，联机识别的数据可以方便的转 化为脱机数据，以进行脱机识别，反之则不行。 手绘图形识别与手写文字识别一样，同属于模式识别和计算机视觉研究领 域的分支，但手写文字研究已有三十几年的历史，目前手写文字识别系统已进 入实用阶段，有很多成型产品，而手绘图形的识别研究则刚刚起步。实际上手 写文字识别与手写图形识别二者既有联系又有区别，二者的区别主要在于：手写 文字识别主要解决主要问题是：将输入数据识别并转化为字符或词句，然后存 储、显示或者加以解释和执行。它有固定的字符集合以及相应的词法和语法。 而手写图形则是首先从二维平面上对输入笔划的形状、尺寸、方向等特征进行 识别和估计，其次再由总体结构分析得出笔划适当的描述或解释。从广义上讲， 文字可以看成是一种特殊的图形。其特殊性表现在以下几个方面：首先，文字具 有固定的字符集，以及严格的词法和语法，因此便于对每个特定字符进行特征 分析，以及对整个字符集的整体特征( 统计特征等) 进行分析；其次，文字的笔 划形态相对简单，不论是曲线字符还是结构字符都具有这样的特点，因此，这 一特点便于寻求稳定的特征来建立鲁棒的分类器；再次，文字具有相对较少的 几何特征，不论是曲线字符还是结构字符，在书写时通常遵循严格的位置、方 向和尺寸的限制，这些限制都有利于预处理算法以及特征的准确获取，对提高 识别的正确率有很大帮助；最后，文字在结构特征上相对简单。西方文字在书 写时通常遵循从左到右的顺序，因此，一段笔迹可以看成是左右结构或线状结 构的而汉字的结构一般遵循左右，上下和里外结构三种模式，具有很强的规律 性，可以用来帮助建模。 对手绘图识别来说，将其特点进行归纳，首先，与文字相比，图形一般没 有特定的字符集；其次，笔划形态复杂、多样，难以用简单的特征加以描述； 第三，图形的几何特征也较多，包括：方向、尺寸以及封闭、连接、对称、交叉 等拓扑特征，而且，对图形来说，这些特征取值的准确估计有时非常重要；最 后，图形的结构特征也较为复杂，与汉字相比，对位置特征的量化更细，从而 增加了模型的复杂度呻1 。 在实际应用中，事实上二者是紧密结合的，可以说图形识别是对文字识别 的一种扩充，因此在研究方法上可以借鉴文字识别技术中已经取得的很多研究 成果。 3 武汉理工大学硕士学位论文 1 4 草图理解 对于一个具体领域的草图识别研究，就存在一个草图语义理解问题。草图 语义理解是在图形识别的基础上，应用一定的背景知识，包括领域知识、用户 信息等，或借助其辅助手段，赋予草图真实的含义，从而实现用户绘制意图的 捕获与辅助设计的目的。草图语义理解的的领域依赖性较强，不同领域间识别 方式的差别较大。但归结起来，草图语义理解一般包括三个环节：语义获取、关 系分析和高层应用。 语义获取是指输入草图经过图形识别后，系统获取草图中的图形在特定用 户及应用背景下的含义，语义获取的主要困难来自：相同的图形表现的草图对象 在不同的领域、不同的用户、不同的上下文环境下，可能存在不同的解释。 草图语义理解中，关系在不同的概念层次上都存在，此处的关系指的是草 图的空间布局在特定领域背景下的语义解释，关系分析的核心问题是对空间布 局建模。大多数系统试图利用领域的特殊性，将定量的位置信息转化为定性表 达，并使用更为自然的语言在较高的抽象层次上建立便捷的关系描述机制。关 系分析技术主要包括以下环节：第一，预先定义基本关系，确定关系的属性，作 用对象及其约束条件等；第二，人为制定或系统半自动定制复合关系，复合关 系由多个基本关系构成，它代表某种确定的关系语义；第三，系统根据已有的 关系定义发现草图中存在的关系。 高层应用是在确定了基本对象及其关系的语意，捕捉到用户意图，服务于 特定领域的应用。既然高层应用服务于特定领域，那不同应用间的实现方法差 别很大，不具有可比性口1 。 1 5 手绘图识别研究现状 随着“数字墨水 ，“智能纸”，“平板计算机”等n 7 ，的出现，以及小型化， 便携式智能设备的普及，笔式输入方式因其与人们使用传统的纸笔操作习惯相 符，越来越受到人们的青睐。目前手写识别( h a n d w r i t i n gr e c o g n i t i o n ) 已经达 到很好的使用效果，已开始向完全无限制的整句识别技术方向发展呻1 。 手绘图( s k e t c h ) 拥有强大的信息表达能力，能直接传递形象和关系属性， 有利于思想的快速表达和自然交流，是以人为中心的人机交互的重要方式之一； 同时，由于用户手绘草图输入较随意，自由度较大，没有固定的结构和模板， 4 武汉理工大学硕士学位论文 不可避免地带来了语义模糊性和歧义性，难以准确传递信息。现有的计算机系 统尚不能对用户的手绘草图进行准确、快速的直接解释，计算机对手绘图识别 与理解能力成为人机交互领域的一个十分重要的研究课题，成为学术界和产业 界的研究热点哺1 2 0 世纪6 0 年代，s u t h e r l a n d 就提出了笔式交互的思想，设计了第一个笔式 交互式系统s k e t c h p a d 阳3 ，在人机交互、信息检索和人工智能等领域得到进一步 发展。2 0 世纪7 0 年代，中期光栅显示器的流行和鼠标被广泛接受，基于桌面 隐喻，应用w l m p ( w i n d o w ，i c o n ，m e n u ，p o i n t ) 范式的界面因其有对象可视 化、语法极小化和快速语义反馈等非常明显的优点，逐渐占据了人机交互的主 导地位，笔式交互逐渐被人们遗忘。2 0 世纪8 0 年代末9 0 年代初，随着网络技 术的兴起和硬件技术的发展，移动计算和普适计算成为计算机技术的一个重要 发展方向，数字终端设备逐渐多样化，如手机、p d a 等终端设备迅速普及。传 统的w i m p 界面范式不能利用人的听觉和触觉，无法适应普适计算。随着计算 的普遍深入和嵌入化，人们越来越不满足于传统的w i m p 界面交互方式。从用 户角度看，用笔操作手机、p d a 等终端设备能够手眼一致，远比用键盘鼠标方 便，笔式交互逐渐成为便携式领域的一个重要特征，受到许多公司和科研机构 的重视。作为笔式交互核心内容的草图理解也迎来了发展的良机，逐渐受到研 究人员的重视呻1 。 2 0 世纪9 0 年代计算机支持的草图技术逐渐成为有关学者专家研究的热点，他 们从各个方面，各个角度展开研究工作。a c m a 从i 继2 0 0 2 年就“s k e t c h u n d e r s t a n d i n g 举行专题研讨后，又于2 0 0 4 年举行了“m a k i n gp e n b a s e d i n t e r a c t i o ni n t e l l i g e n ta n dn a t u r a l 的专题研讨会；“i n t e m a t i o n a lw o r k s h o po n g r a p h i c sr e c o g n i t i o n 研讨会中也设有“手绘草图识别 专题；欧洲图形学学会 则于2 0 0 4 年在法国就这一主题召开了专题研讨会展现了基于手绘草图交互在 多个领域的最新应用研究成果隅1 。比较有代表性的研究有以下几个： m i t 人工智能实验室以r a n d a l ld a v i s 为首在草图识别方面进行了大量的研 究，研究领域涉及多个领域，包括机械工程设计、u m l 流程图、室内布局等。 他们应用基于上下文的识别推理方法，认为领域知识对识别的准确性和鲁棒性 有充分的促进作用。 卡耐基麦隆大学的人机交互学院将笔交互嵌入了工具箱系统g a r n e t ，同 时设计实现了基于草图的图形用户界面设计原型工具s i l k u 0 1 。j e n k i n s 给出了 武汉理丁大学硕士学位论文 一种基于用户意图的，通过在线方式将各种约束施加于自由二维草图的手绘草 图工具，简称e a s e l 。e a s e l 采用一种比较实用合理的方法处理原始的线条，可 以识别各种随意的不一定十分准确的线条，并将它们分割成直线段和圆弧，然 后在这些直线段和弧线之间添加合适的关系或者约束，最终生成完整的几何草 图。该系统通过后台运算的方式使得草图绘制过程得到快速的反应，还避免了 使用菜单以防打扰创新过程。但当线条数量较多时，就难以施加各种关系，特 别是很难确定各种约束之间的逻辑关系和优先权。 k a t o 等人描述了一个用于自由手绘流程图的交互处理的系统。该系统是二 维的，能够识别和规整二维几何元素，如直线、圆、流程符号、以及一些中文 字符。s p u r 和j a n s e n 则提出一个可以自动识别手绘的轮廓线条，以便应用到 c a d 中。b e l l 西和o z g u c 给出一个建筑草图识别的系统。该系统是可以处理二 维建筑规划手绘草图，识别和整理直线段和圆弧，尤其是它可以规整拐角。e g g l i 等人提出一个包括实体建模和草图的工具，该系统是三维的，但草图本身是在 一个基准面上完成的，这样可以避免重建阶段的诸多问题。p i l g l l 提出了另一个 类似的通过交互草图识别与理解进行设计建模的系统。该系统接受扫描来的线 条图，它能够将图形元素和文本、标本、注释等分别开来。 国内的诸多研究机构从纸笔交互的界面隐喻、体系结构和识别算法等不同 角度对草图理解进行了研究。如中国科学院软件研究所的栗阳等人设计实现了 笔式用户界面开发工具pe i l _ b u i l d 盱，允许用户自由笔式输入，支持各种笔交 互信息和灵活的事件的处理，支持跨平台的面向无处不在的计算的笔计算环境； 微软亚洲研究院的多通道用户界面组正在研究和探索先进的用户界面技术，以 实现更加自然的用户界面，其正在研究的智能数字墨水能够帮助人们在电脑上 用自己的笔迹随意书写，用墨水记录自己的思想；南京大学计算机软件新技术 国家重点实验室孙正兴教授等人也对此开展了相关研究，从c a d 系统出发，对 手绘草图识别进行了研究，取得了一系列成果1 。 1 6 本文研究内容及整体结构 本文研究的是手绘几何图形识别，研究对象为：基本的几何图形( 直线，圆， 多边形，曲线等) ，目的是对通过手写板，光笔，鼠标等输入设备绘制的几何图 形进行实时地识别。 本文各章的主要内容如下： 6 武汉理丁大学硕士学位论文 第一章：绪论。首先针对纸质草图和传统绘图工具的不便之处，引出对基于 人机交互的手绘图识别研究；接着介绍了草图识别与草图理解理论，以及草图 识别领域的国内外研究现状；最后给出了本文研究内容及整体结构。 第二章：手绘图识别相关知识。首先介绍了常见的手绘图识别方法，根据研 究对象的特点，选择基于图元表示法，并给出了识别流程：接着介绍了与图元表 示法相关的概念，并对图元作出了简单的分类；最后简单介绍了数据采集与预 处理技术。 第三章：笔划分割。首先介绍了笔划的特性曲率及绘制速度，同时对离散曲 率的求解方法进行了详细的研究。然后根据曲率及绘制速度来检测笔划中的特 征点进行分割。文中介绍了两种分割算法：均值滤波和尺度空间滤波法。并着重 对尺度空间法理论进行研究。 第四章：图元识别与拟合。首先给出了图元的识别流程，按照识别流程对直 线识别的理论方法以及如何用最小二乘法对直线拟合进行研究；接着研究了如 何用二次曲线不变量进行曲线识别，并用最小中值二乘法对其拟合。最后给出 了图元的矢量化以及对非二次曲线的处理。- 一 第五章：图形识别与规整。本章主要在前几章的基础上，对绘制整个图形 进行识别，首先介绍了结构模式识别理论，接着介绍了如何判断图元间的位置 关系以及根据图元间的位置关系进行特征值提取，进而和模板库中图形匹配来 识别整个图形；最后对识别出的图形根据规整规则进行规整输出。 第六章：手绘几何图形在线识别系统。本章结合前几章的理论，自主设计 了手绘几何图形识别系统。并且给出了系统数据的主要存储结构，同时介绍系 统中主要的类、类之间的关系，以及笔划类和几何图形类的主要属性及成员函 数。然后对图形的编辑进行简单的介绍，最后对识别结果总结以及分析，也指 出了系统存在的不足之处。 总结与展望：本文研究工作的总结以及需要进一步解决的问题。 7 武汉理工大学硕士学位论文 第2 章手绘图识别相关知识 本章首先介绍联机手绘图识别方法，然后结合本文研究对象特点，给出文 中所采用的方法及识别流程。最后介绍数据采集和笔划预处理。 2 1 联机手绘图识别的方法 联机草图识别是指将通过笔式交互获取的模糊草图表达映射至精确的图形 的表达，它注重图形形状的构成与理解，它需要从用户勾画草图的图形构造及 表现中挖掘图形约束，将不自由不规则的草图图形映射成规则的几何图形。 手绘图识别研究方法主要有以下几大类但1 ： 1 ) 统计类方法：基于圆锥曲线方程的线性最小平方匹配法，能实时地分类 手绘笔划，识别直线、椭圆弧和圆角u 射。 2 ) 模糊类方法：用模糊逻辑和模糊知识，从草图的位置、方向、速度和加 速度捕获绘图者的意图j 实现草图识别n 纠副。 3 ) 几何方法：文献e 1 6 把手绘图作为整体进行识别，需要进行平滑处理、 提取圆弧段、识别结点、分解出直线段；在根据相邻三点的矢量建立角 度相似函数，采用夹角角度作为圆弧和直线段的提取特征，并给出角度 的实验阈值，然后进行分类。 4 ) 神经网类方法：文献 1 7 提出通过提取图素几何形状的内角特征，用二 进制突触的权重算法b s w ( 含一个隐层的前馈网) 进行识别的方法。该方 法以整体方式识别三角形、椭圆和矩形三种图素，但仅适用于绘图包和 掌上电脑的自动草绘输入。文献 1 8 提出模糊样条曲线识别器f s c i ， 并训练三层前向神经网实现模糊分类规则，可识别7 中图素( 直线、圆、 圆弧、椭圆、椭圆弧、开式自由曲线和闭式自由曲线) ，但各图素均限 制在水平、垂直和四分角方位，且对于不同的使用者需重新训练神经网。 手绘图识别根据图形构成最小单元的定义和其表示方法的不同又可以分为 以下几种博1 ： 1 ) 基于笔划表示的方法 基于笔划表示的方法以用户落笔和提笔之间取样点构成的笔划为 8 武汉理工大学硕士学位论文 基本识别单位，该方法识别简单、有效，对单笔绘出的图形有很好的识 别效果。但此方法往往跟人的绘图习惯和笔顺有关，对用户的限制性比 较高，而且以笔划为单位并不能保证图形构成的唯一性，很难适应笔划 复杂的图形。 2 ) 基于图元的表示方法 基于图元的表示方法将图形表示成有直线、圆弧、曲线、椭圆、圆 等图元在一定空间关系下的组合，可消除对用户笔划模式限制且有效地 处理多笔划草图识别问题。该方法首先对基本图元识别，然后再对整个 图形识别。主要步骤包括笔划分割、图元识别和图形的识别与规整。此 方法解决了图形构成的唯一性问题。但是图形识别的结果往往很大程度 上受制于笔划分割的好坏。对复杂图形的识别效果还远未尽如人意。 3 ) 基于几何特征的表示方法 基于几何特征的表示方法以整个图形作为识别单位进行识别，通过 提取草图的几何特征用于分类。该方法利用图形构成的几何特性来模拟 人类形状输入交互的视觉思维习惯。因此如何有效地从局部和整体描述 。 图形构成的几何特征，既保证能有效捕捉用户的输入意图，又能从细节 构成上区分相似图形是该方法的关键。 4 ) 基于组合图形的表示方法 基于组合图形的表示方法主要是用来解决复杂图形识别问题的。目 前该方法多数采用图匹配策略，即首先被分解成几何图元，然后将其集 成到一个包括图元的内在属性和图元间关系的图结构中，这样，图形识 别问题就转化为“图与子图同构 问题。该方法试图从图形构成的内部 和外部关系来解决复杂图形的识别问题，图匹配方法可以有效地解决不 同复杂度图形的统一表示问题，但却很难解决图匹配本身为n p 问题的 计算复杂性问题。 2 2 本文采用的方法及识别流程 本文研究的主要对象是在联机方式下绘制的常见几何图形，如图2 1 列出 了部分常见图形。由图2 - 1 我们可以看出这些几何图形组成比较简单，基本上 都是由直线、圆弧等组成，适合采用基于图元的表示方法。基于图元表示法首 9 武汉理工大学硕士学位论文 先把输入的笔划分割成简单的图元，进而识别分割出来的各个图元，然后提取 各图元间的空间位置关系，并和标准图形库中图形的图元位置关系比较来识别 图形，最后对图形进行规整输出。基于图元表示法不仅可以消除对用户笔划模 式限制且有效地处理多笔划草图识别问题，而且对笔划的输入顺序无关，提高 了用户绘图的自由度。主要流程如图2 2 ： oo 险 口r i oo 图2 - i 常见几何图形 图预笔图图图形 形处划 兀形规整 输理分识识输出 入 割别别 图2 - 2 图元表示法识别流程 武汉理工大学硕士学位论文 2 3 基本概念与图元分类 2 3 1 基本概念 图元：组成图形的最小构成单元，无法再分割成其他几何线条。例如：直线， 圆弧等 笔划：落笔和提笔之间取样点构成的运动轨迹。 图形输入：绘制图形后，如果提笔时间超过某一设定阈值，则认为该图形输 入完毕。 笔划分割：用某种规则把输入的笔划分解成简单的图元。 手绘图识别：用模式识别的方法，把用户绘制的手绘图形转化为标准的图 形的过程。 2 3 2 图元分类 根据本文研究对象的特征，我们把图元划分为：直线，圆，圆弧，椭圆， 椭圆弧及其他曲线。如图2 3 所示： 2 4 数据采集与预处理 2 4 1 数据采集 联机数据采集一般采用专门的外设。目前较为普及的手写输入设别有电磁 式感应板或压敏式感应板，除此外，还有其他的一些设备也可以用作输入装置， 如鼠标、触摸屏。这些设备书写方式与传统的纸笔书写方式相同。在本文所做 的系统中，用鼠标器来完成原始手绘图形数据采集，从鼠标器得到的手绘图形 的采样点记为： 武汉理工大学硕士学位论文 m p ： pl ，p2 ，p 。) 其中g p 表示从鼠标器按下到抬起之间的全部采样点，我们称为一个笔划，刀代表该笔划 得总采样点数，p f = ( 而，y i ) ，x i 为第j 点横坐标值，y t 为第j 点纵坐标值。一个手绘图 形就是其包含的全部笔划集合，记为： g p ： 坳l ，m p2 ，m p ，) 其中s 表示该图形包含的总笔划数。鼠标器是以事件驱动的方式进行采样的， 其采样方式为等时采样。 2 4 2 预处理 数据采样后的下一步工作是进行预处理。预处理目的是消除因输入条件的限 制和输入习惯的差异而存在于笔划中的噪声。如图2 4 中的笔划含有非常多的噪 声。噪声主要来源于：绘图时，由于手无意识的抖动造成笔划有很多毛刺；或 者绘图较慢时，造成很多的点重复取样。如果不处理这些噪音会严重影响后面 笔划分割的准确性，同时也会增加后面识别时计算复杂度。 图2 4 带噪声的笔划 降低噪声的方法通常采用线性平滑算子或非线性平滑算子进行处理。方贵盛 等人n 钾采用每隔两点计算其中心点，然后连接这些中心点作为后续处理笔划的 方法。陈东帆等人伽1 通过限定草图的点间距的方法过滤掉多余的草绘点。但方 法可能会丢失草绘时的一些动态特征，如速度、加速度等，造成实际分段点的 丢失。孙正兴等人乜首先消除笔划中的冗余点，然后根据笔划上点的密度消除 武汉理工大学硕士学位论文 聚点( 聚点分为钩和圈，如图2 5 ) ，最后进行端点校正的方法取得不错的效果。 豳 图2 5 笔划中的聚点 本文中为了保持用户笔划中采样点的速度等其他信息，根据这些信息进行特 征点检测，对笔划进行正确分割，暂时不对输入的原始笔划不做任何处理。真 正的笔划处理是从笔划分割开始的。 2 5 本章小结 本章首先介绍了常见的手绘图识别方法，根据研究对象的特点，选择基于图 元表示法，并给出了识别流程；接着介绍了与图元表示法相关的概念，并对图元 作出了简单的分类；最后简单介绍了数据采集与预处理技术。 武汉理工大学硕士学位论文 第3 章笔划分割 笔划分割的目的是把用户一笔勾勒出的图形或复杂图元分割成基本的图 元。笔划分割是基于图元表示法的基础与关键，分割的结果将将会直接影响到 后期的识别效果心羽，本章将介绍如何用曲率和绘制速度来寻找笔划中的特征点， 首先描述笔划中各采样点的曲率与绘制速度，之后阐述如何用曲率与绘制速度 确定采样点是否为特征点。 3 1 笔划的特性 笔划是有用户落笔和提笔之间的取样点序列组成，笔划复杂程度不定，有 时可能是图形的一部分，可能整个图形。但笔划中有些特征能描述其形状及特 性。下面说明下笔划中的曲率和绘制速度特征。 3 1 1 曲率 3 1 1 1 曲率与几何特征 曲率描述了曲线上各点在沿曲线方向的变化情况，因此借助曲率可以刻画 曲线的几何特性1 。如表3 1 所示： 表3 - 1 一些曲率刻画的几何特性 曲率几何特性 连续零曲率直线段 连续非零曲率圆弧段 局部最大曲率绝对值( 一般) 角点 局部最大曲率正值凸角点 局部最大曲率负制凹角点 曲率过零点特征点 大曲率平均绝对值或平方值形状复杂，与弯曲度无关 3 1 1 2 曲率计算 曲率描述了一段曲线的弯曲程度。其计算公式： 1 4 武汉理工大学硕士学位论文 k ：鲤 ( 3 1 ) s 其中：矽表示切线倾角变化值，s 表示曲线的弧长。 对于数字曲线的曲率计算有很多方法h 羽，通常的方法是将曲线表示弧长的 函数，然后求取曲率。例如某曲线表示成弧长的函数：f = 厂( 工( 甜) ，少( “) ) 。则曲 率可以表示为： c = 等等器笋 2 ， 其中：训，荆。分别表示其一阶、二阶导数。 上述通用方法曲率计算较复杂。另外一种方法，对于某个给定的笔划，采 样点序列s = 只( ，y ，) if = l ，2 ，n ) ，计算曲线在某点切线倾角变化9 ， 一种简单的方式是：首先计算连续两个采样点p ，、办+ 。的相对位置的改变量x 和每( 其中3 c - - x l + i 一而，今= 叫) ，然后用缈= a t a n ( a y a x ) 作为曲线在点p j 角度变化值；丛为p ，、p 川两点间的距离。 上述方法看起来是一种很自然的求解离散点曲率方式，并被许多文献所采 用，但是当笔划含有较多噪声时，该方法计算出噪声点处的曲率较大，真正的 特征点曲率也比较大，这就无法区分出真正的特征点和由噪声引起的特征点。 在本文中采用文献 2 4 中的o d r ( o r t h o g o n a ld i s t a n c er e g r e s s i o n ) 方法求曲线在某 点的切线方向。该方法是用直线拟合的方法来寻找一条过该点直线，使得该点 邻域内的各点到该直线的距离之和最小，然后取该直线与x 轴的夹角作为该点 的切线方向。 对于曲线上某点p 。，首先确定该点的一个邻域： q ( 忍) = 易一i ，易一l ，a ，忍+ l ，易+ i ) ， 其中k 为邻域半径，对超出笔划范围的邻域点，取值和当前点值相同。算法如下： 1 ) 通过循环选择某以角度口( 其中0 ( 一等，i j l , ) ) ，设斜率缈= t a n ( o ) ，求解 二 二 过点p l 的直线方程：a ( x 一五) + b ( y 一只) + c = 0 。 2 ) 求邻域内各点到直线的距离之和： 武汉理工大学硕士学位论文 缸2 匕舻 3 ， 循环未结束，转( 1 ) ，循环结束，转( 3 ) 。 3 ) 比较求出：m i n ：i 丸i 。定义曲线在点p ，的切线倾角为：口。 4 ) 计算出曲线上点p ，切线倾角后，曲率定义如下： i 矽( d 川一d i ) i c 一2 訾著i ；爿( 3 - 4 ) 其中鳓一毛刀+ 妨代表第n - k 点到n + k 点的距离，k 为很小的整数，通常情 况下取2 ，有利消除噪声的影响。 从曲率的定义可以看出，在切线倾角改变相同的情况下，两点间距离越小， 曲率越大。这一特性非常适用于判断特征点，因为笔划中特征点处采样点之间 的距离较小，而角度变化较大。 3 1 2 绘制速度 用户绘图过程中，在拐角处绘制速度会变慢，所以绘图时的绘制速度也是我 们进行特征点判断的重要依据。由于在绘图的过程中是等时采样，任意点的绘 制速度，可以用相邻两点间的距离代替。 3 2 特征点检测 特征点检测是笔划处理的开始，如图3 1 作为例子来说明在特征点检测过 程中需要做那些工作。图3 1 中被红圈标记的点为笔划的特征点。这些特征点 的局部曲率都比较大，但是原始笔划中并没有标记那些曲率值可以被标记为特 征点。在寻找特征点的过程中，尽可能选择曲率较大的点，同时要尽可能选择 少的特征点。多边形拟合不能满足这方面的要求。 特征点检测经常出现在有关图像识别的文献中，但是这些方法大都和分段线 性拟合相关。本文中充分利用了交互式绘制草图中曲率和速度的信息。图3 1 中 笔划各采样点切线夹角( 图3 2 ) 、曲率( 图3 3 ) 和速度图( 图3 4 ) 所示。我们在 曲率最大和速度最小的地方定位特征点。 武汉理工大学硕士学位论文 图3 1 手绘笔划，红圈处为特征点 ：1 8 i i ，1 4 ， ，1 2 一 。67 i ；： 图3 - 2 图3 1 中采样点的切线夹角 。? j “憾钐聋矽形霞移7 莎豫z 形? 缨巧够弼i 孑镑弼稳：i 事? 弱穆 0 秀 ，乒 k _ i 乒碱= 乒融l 莓：二 图3 3 图3 - 1 中笔划的曲率图 1 7 武汉理工大学硕士学位论文 图3 4 图3 - 1 笔划绘制速度 尽管曲率和速度的极值对应原始笔划的特征点，但是我们也不能盲目以此来 判断特征点。因为笔划中不可避免的含有一些噪声，这样会产生许多的伪特征 点。接下来介绍两种方法，在噪声存在的笔划中寻找特征点，同时消除伪特征 点。 3 2 1 均值滤波法 数据的极值有时可能是数据中的噪声所致，所以极值有可能会增加处理结果 的误差。为了消除由于噪声所引起的极值，我们选择极值要大于某一固定阈值。 但是设