（航空宇航制造工程专业论文）支持概念设计的手绘图在线识别研究.pdf

西北工业大学硕l 论文摘要 支持概念设计的手绘图在线识别研究 摘要 本文系江西省自然科学基金( 0 3 11 0 1 8 ) ，南昌航空工业学院测试技术与控制 工程研究中心开放基金( 2 0 0 3 - - 0 1 3 ) 资助项目的一部分。 在线识别技术是提高入机交互智能化水平的一项关键技术，是模式识别和机 器视觉研究领域中的个分支，历经了较长时间的发展，并随着计算机技术的不 断进步以及计算机应用的不断普及，得到了越来越多的重视和研究。 通过研究人员和工程技术人员的不断努力，己经取得了相当丰富的成果，并 且某些研究还推出了接近实用的原型系统，但从总体上看，该技术的发展还远未 达到实用阶段。目前的研究成果主要集中在手写文字的在线识别上，而对手绘图 形的在线识别研究则刚刚起步。在这样的背景下，本文对手绘图形的联机识别技 术进行了系统的研究。 本文主要研究了手绘图在线识别中的单笔划识别问题。通过分析笔划的几何 特征，对笔划进行分类和定义。通过折线化处理、最小中值二乘法对单一线元进 行识别，笔划的最终识别单元为直线、折线段、椭圆、椭圆弧、圆、圆弧、双曲 线、抛物线。对于复合线元通过分析得到了分割点特征，将其分为超复合线元和 非超复合线元，并给出了相应的分割识别算法。本文的在线识别算法得到了自主 开发的原型系统的验证，实验证明该算法适用性强、并且扩充方便。 关键词：手绘图，在线识别，概念设计，单笔划，最小中值二乘 西北t 业人学硕士论文摘要 o n - l i n es k e t c h i n gr e c o g n i t i o nf o r c o n c e p t u a ld e s i g n a b s t r a c t o n l i n er e c o g n i t i o ni sab r a n c ho fp a a e mr e c o g n i t i o na n dc o m p u t e rv i s i o n ，a n d p l a y sav e r yi m p o r t a n tr o l ei nh u m a n - m a c h i n ei n t e r a c t i o n s i ts t u d i e st h em e t h o d s a n dt e c h n i q u e st or e c o g n i z eas k e t c ha si t i sd r a w n u s i n gad i g i t i z e r o ra n i n s t r u m e n t e ds t y l u s w i t ht h er a p i dg r o w t ho ft h ec o m p u t e rt e c h n o l o g ya n di t sw i d e s p r e a da c c e p t a n c e t ot h es o c i e t y , t h i sr e s e a r c hd r a w sm u c hm o r ea t t e n t i o nr e c e n t l y ，m a n yr e s e a r c ht e a m s d e v o t et ot h i sc o m p l e xt a s kw h i c hc o v e r sab r o a df i e l d t h ep r e s e n tr e s e a r c hr e s u l t s m a i n l yc o n c e n t r a t ei nt h eh a n dp r i n t e dc h a r a c t e r sr e c o g n i t i o n ，b u tt h ef r e e h a n d s k e t c h i n gr e c o g n i t i o nr e s e a r c hi sj u s ts t a r t e d a i m i n ga tt h ed e f e c t so ft h ee x i s t i n g m e t h o d s ，as t u d yo nd e v e l o p i n ga ne f f e c t i v er e c o g n i t i o nm e t h o di sp e r f o r m e di nt h i s d i s s c r t a t i o n i nt h i st h e s i s ，w em a i n l ys t u d yt h em e t h o df o ro n l i n er e c o g n i z i n gt h ef r e e h a n d s k e t c h i n gf o r t h es i n g l es t r o k e t h es t r o k ei sc l a s s i f i e da n dd e f i n e db a s e do nt h e g e o m e t r yc h a r a c t e r i s t i c w ea d o p tt h ea d a p t i v ep o l y g o n a la p p r o x i m a t i o na p p r o a c h a n dl e a s tm e d i a ns q u a r ec u r v i l i n e a rr e g r e s s i o nt or e c o g n i z et h es i n g l el i n e a re l e m e n t t h er e c o g n i t i o nr e s u l t si n c l u d el i n e ，f o l d l i n e ，e l l i p s e ，e l l i p t i ca r c ，c i r c l e ，c i r c u l a ra r e ， h y p e r b o l aa n dp a r a b o l a b a s e do nt h ec h a r a c t e r i s t i c so ft h es e g m e n tp o i n t s ，c l a s s i f y t h ec o m p o u n dl i n e a re l e m e n ta st h eu l t r ac o r n p o u n dl i n e a re l e m e n ta n dt h en o n u l t r a c o m p o u n dl i n e a re l e m e n t ，a n dw ec o n c l u d et h es e g m e n t a t i o na l g o r i t h m sa c c o r d i n g l y t h ef r e e h a n ds k e t c hr e c o g n i t i o np r o t o t y p es y s t e mi s i n d e p e n d e n t l yd e v e l o p e di nt h e a b o v em e t h o da n dc o n f i r m so u ra l g o r i t h m st ob es e r v i c e a b l ea n de x t e n s i b l e t h i sd i s s e r t a t i o ni st h ep r o j e c ts u p p o r t e db yn a t u r a ls c i e n c ef o u n d a t i o no f j i a n g x ip r o v i n c e ( n o 0 3 1 1 0 1 8 ) a n do p e nf o u n d a t i o no fr e s e a r c hc e n t e r o f m e a s u r i n gt e c h n o l o g i e sa n dc o n t r o le n g i n e e r i n go f j i a n g x ip r o v i n c e ( n o 2 0 0 3 0 1 3 ) k e yw o r d s ：f r e e h a n ds k e t c h i n g ；o n l i n er e c o g n i t i o n ；c o n c e p t u a ld e s i g n s i n g l es t r o k e ；l e a s tm e d i a ns q u a r e i l 西北丁业大学钡t 论文第一章绪论 第1 章绪论 1 1 手写识别与人机交互 手写识别分为离线识别和在线识别，所谓“离线”是指将通过特定的采集系 统( 如扫描仪、摄像机) 将文字或图形以图像方式采集并输入计算机存储，随后 识别系统根据该图像数据进行文字或图形识别；在线识别则主要通过各种与计算 机相连的= 维坐标输入设备( 如数字化仪、鼠标、写字板等) 将笔的运动轨迹实 时送入计算机并进行识别。 离线识别与在线识别的区别主要在于获取数据的方式不同，这种不同也导致 了识别方法存在差异。通常，离线数据用矩阵 坂切 来描述，其中厂( i d ) 为平面 坐标( 玎) 的图像灰度，因此，在离线识别系统中，原始数据矩阵需要进行降噪、 二值化、细化、跟踪等预处理，而在线识别的数据为一维数据，可用二元序列( x n ， r n ) 来表示，即用手写笔迹的采样点坐标列来表示。在线识别的数据可以含有比离 线识别的数据更多的信息，除了采集点的坐标之外，还可以采集笔的移动速度和 加速度以及笔尖的压力等。这些数据可以构成多维特征点列，为识别算法提供更 多的信息。另外，在线识别的数据可以方便地转化成脱机数据，以进行离线识别， 反之则不行l l 。j 。 按照识别对象来划分，手写在线识别可以分为手写文字识别和手绘图形识别 两个研究方向【4 】。手写文字的在线识别主要解决的问题是：将输入数据识别并转 换成字符或词句，然后存储、显示，或者加以解释和执行。而手绘图形的在线识 别，则是首先从二维平面上对输入笔划的形状、尺寸、方向等特征进行识别和估 计，其次再由总体的结构分析得出笔划适当的描述或解释。二者的主要区别在于， 前者有固定的字符集合以及相应的词法和语法，而后者则不具备这些特点。一般 来说，图形识别是对一个开放集合做出识别和解释，其方法与前者有着本质的区 别。 从广义上来讲，文字是一种特殊的图形。其特殊性表现在以下几个方面 4 1 ， 首先，文字具有固定的字符集，以及严格的词法和语法。因此便于对每个特定字 符进行特征分析，以及对整个字符集的整体特征( 统计特征等) 进行分析；其次， 文字的笔划形态相对简单，不论是曲线字符还是结构字符都具有这样的特点，因 此，这一特点便于寻求稳定的特征来建立鲁棒的分类器；再次，文字具有相对较 少的几何特征，不论是曲线字符还是结构字符，在书写时通常遵循严格的位置、 方向和尺寸的限制，这些限制都有利于预处理算法以及特征的准确获取，对提高 l 西北工业大学硕士论文第一章绪论 识别的正确率有很大帮助。最后，文字在结构特征上相对简单。西方文字在书写 时通常遵循从左到右的顺序，因此，一段笔迹可以看成是左右结构或线状结构的； 而汉字的结构一般遵循左右，上下和里外结构三种模式，具有很强的规律性，可 以用来帮助建模。 对手绘图在线识别来说，将其特点进行归纳【4 j ，首先，与文字相比，图形一 般没有特定的字符集；其次，笔划形态复杂、多样，难以用简单的特征加以描述： 第三，图形的几何特征也较多，包括：方向、尺寸以及封闭、连接、对称、交叉 等拓扑特征，而且，对图形来说，对这些特征取值的准确估计有时非常重要。最 后，图形的结构特征也较为复杂，与汉字相比，对位置特征的量化更细，从而增 加了模型的复杂度。表1 1 对文字和图形的特性进行了比较。 表1 1图形与文字的特征比较 字符集笔划形态几何特征结构特征 曲线类字符小复杂少少 结构类字符大简单较多 较多 图形无复杂多多 在实际应用中，事实上二者是紧密结合的，可以说图形识别是对文字识别的 一种扩充，由于图形与文字既有区别又有联系，因此在研究方法上可以借鉴文字 识别技术中已经取得的很多研究成果。 手写文字和手绘图形的识别问题都是模式识别和计算机视觉研究领域的分 支，手写识别的研究已经有差不多三十年的历史，但只是到近年才进入实用的阶 段，这主要得益于硬件技术的发展。目前的研究成果主要集中在手写文字的在线 识别上，而对手绘图形的在线识别研究则刚刚起步【5 l 。 1 2 支持概念设计的草图设计 在灵感充斥并易逝的工业设计领域中，对高效交互工具、设计模式、交互技 术的要求更加明显。工业产品的功能已不再是消费者决定购买的最主要因素，产 品外观造型、宜人性等因素越来越受到重视，在竞争中占据突出的地位。创新是 工业设计的灵魂，以知识为基础的产品创新竞争是2 l 世纪初全球制造业竞争的核 心，一个新产品在功能、原理、布局、形状、结构、人机、色彩、材质、工艺等 任一方面的创新，都会直接影响产品的特性，影响产品的最终质量和市场竞争力， 而概念设计阶段是完成创新功能的重要阶段。形状是产品的主要表现形式，是用 西北工业大学硕士论文第一章绪论 户的第一刺激物，设计中的大部分活动都是围绕着形状进行的。结构优化、动力 学分析和仿真等设计活动都是在产品有了明确形状之后才进行的，因此可以说概 念设计的主要目标是获得产品基本形式或形状6 1 。这一阶段所作的工作对后续其 它阶段有着重要的影响，占设计工作1 0 左右的概念设计工作一旦被确定，产品 设计的7 5 左右也就被确定了 7 1 。图1 1 为一个理想的设计过程【8 】。 媸 呕 图1 1 一个理想的设计过程 从图1 1 中不难看出，草图设计在整个设计过程的地位和作用，它在设计的 前期阶段都起着极其重要的作用，而这一阶段对产品设计的成功与否又是关键的 一步。因此，研制能支持设计全过程的c a d 系统，无论是对c a d 系统发展还是 对产品设计而言，都是非常必要的。 1 2 1 草图设计 徒手草图是设计早期阶段明确概念的必要手段，通过在纸上表达出各种概念 并审查它们，这有助于明确它们和修订自己的想法。可以说通过草图发现不同类 型的信息是修订设计概念的驱动力。研究表明，草图给设计师带来的不仅仅是知 西北工业大学硕士论文 第一章绪论 觉特征，还包括它本身固有的非视觉功能性关系，允许设计师通过对草图的理解 抽取各种功能，这意味着将来的草图工具可以刺激设计师产生一些创造性思维。 草图之所以成为设计早期阶段的关键环节，是由草图自身具有的独特性能决 定的。草图是在设计构思阶段徒手绘制简略的产品图形，其作用是以最简便，迅 速的方法，表现出设计师对产品造型的设想，记录和捕捉瞬间既逝的灵感和构思。 其最显著的特点在于快速灵活、简单易做、记录性强，同时在于它不要求特别精 确或者拘泥于细节，因而塑性强，有利于大量设计方案的产生和设计思路的扩展。 总的来说，草图的基本特性主要表现在抽象性、模糊性、不精确性、不确定性以 及随意性等方面。 相对于其它设计表达形式，草图是面向概念设计阶段的，在这个时候设计师 头脑中的产品形象一般是模糊的，抽象的。通过草图表达出来的也是不完整的、 轮廓性的。草图不像其它图形表达方式那样要求严格的尺寸、位置和比例关系， 也不一定确切表达出局部的设计细节，允许其中存在一定的不确定性，这是由产 品创意阶段设计概念的不确定决定的。之所以c a d 系统不能很好的支持早期概 念设计，就是因为它不能像草图那样支持早期概念产生和发现的认知过程，在分 析和综合模式方面都不能很好地支持创新发现。 尽管草图设计是生产和设计工作中最常用的一种表达手段，然而直到最近， 人们才开始认识到草图设计的重要性，并致力于这一方面的研究。u l l m a n 认为由 于人的s m t 效应( s h o r tt e r mm e m o r ys y s t e m ) ，及时地将各种构思具体化是非常必 要的。并且通过对机械设计人员的调查，发现利用草图来进行设计是设计人员习 惯用的方式，概念设计得到的图形几乎1 0 0 都以草图形式存在【l 。1 。s c i v c n e r 和 c l a r k 将草图设计描述为“一种特殊的图形形式，使得创造者可以更快的生成他们 的构思”1 9 1 。 1 2 2 在线草图设计 近来的研究 1 0 , l l 强调草图在机械设计，尤其是在概念设计中的重要性。概念 设计阶段是人脑趋向于寻找一种形象、直观、简易、高效的形式来表达设计思维， 反映设计结果以便进一步的进行设计的阶段。草图正是这样一种表达形式。所以 在很长一段时间内，纸上草图便成为了辅助人脑进行概念设计的有效方法。不过， 纸上草图设计有它的缺点。当经过多次修改后，设计方案就会变得混乱不清，随 着设计的继续进行，纸上草图往往难以修改，也不能记下整个设计过程，即缺少 所谓的“设计记忆”，若需要对产品进行较大的调整，则需要重新绘图。另外，设 计方案难于存储、整理、搜索和重用，尤其缺少有效的互动式交互性能【l ”。 计算机系统能够很好的弥补上述草图设计的不足。计算机的记忆功能可以弥 4 西北工业大学硕士论文第一章绪论 补草图设计所缺少的设计记忆；能够实现几乎任意次的修改和恢复操作，同时保 证每步设计结果的清晰：能够很好的解决整合、组织、搜索、重用的问题；能够 和人进行有效的交互。因此，如果能够将纸上手绘草图和计算机支持的设计两种 模式相结合，各取所长，提供一个计算机支持的真正适应草图设计特征的实用工 具，让设计师一开始就在一个可以直接进入自由手绘的计算机环境，进行创意工 作，并能自动平稳的转入进一步的详细设计，对于促进产品创新和提高设计效率 将具有重要意义。由此可见基于手绘草图的c a d 系统的研究势在必行。 随着c a d 技术的不断发展和相关学科的融入，将来的c a d 技术将更加智能， 对设计全过程有更加全面的支持。但目前，大多c a d 系统对于早期的草图创意 阶段仍然不能提供一定意义上的支持和辅助，设计师需要一种技术或者工具，让 他们能够像在纸上徒手草绘那样在计算机上自由地进行草图设计工作，能够和这 种平台进行自然的交互，并能和后续的进一步详细设计有效地集成，允许他们不 断地添加设计细节，直到形成一个完善规整的设计方案。智能草图技术就是在计 算机支持的环境下，应用c a d 和人工智能等技术，实现计算机对早期概念设计 阶段的支持，它是对当前c a d 技术的延伸和扩展。 1 3 在线草图设计的研究现状 近几年，国内外c a d 领域围绕基于手绘方式进行快速、自然、高效的三维 实体造型展开了广泛的研究。研究的重点落在两个方面，其一为如何合理设计用 户表达体系，提高系统基于草图的知识捕获能力，准确的捕获用户模糊的绘制信 息和设计意图，进行准确快速的概念设计，其二为如何将= 维绘制环境自然、准 确的演化成三维环境，从而在一种新型方式下进行三维实体的设计。 国外较早开展了这方面的研究工作。最早的计算机化草图系统( 实际上也是 最旱的c a d 系统) 是s u t h e r l a n d 在1 9 6 3 的博士论文中研制的s k e t c h p a d ，在该系 统中，使用者可以在屏幕上绘制线，并对基本几何元素( 圆、直线) 进行操作。 从此，大量的图形软件包出现，但极少的系统去着重“理解”屏幕上绘制的图形， 也就是说它们不去探究用户明确定义的图形关系，不把分散的图形元素作为整体 理解，但人却可以。 k a t o 等在1 9 8 2 年研制出一个交互处理手绘图表的系统1 1 3 j 。这个系统是二维 的，能识别和处理二维基本图素，比如线、圆、流程图和中文字符。j e n k i n s 和 m a r t i n 在1 9 9 3 年提出了一个叫e a s e l 的在线交互手绘图系统【l4 1 ，这些手绘图由直 线、圆弧和b 样条曲线组成。该系统接受手绘图并允许一些绘图错误，避免使用 菜单而妨碍创造过程，并且能自动识别不同的笔画类型，以此来推断它们之间隐 含的几何约束关系。该系统在后台进行计算处理，因此速度显得较快。f a t o s 和 5 西北工业丈学硕士论文第一章绪论 o z g u c 在1 9 9 4 年提出了一个用于建筑草图识别的系统 1 5 1 ，该系统处理二维手绘建 筑平面图，识别、规整直线和圆弧等图索，引人注意的是对角点的规整。 e g g l ie ta l 在1 9 9 5 年提出一个实体模型和草图融合的系统【i “，该系统是三维 的，但草图要求在特定平面内，避免了重建过程的一些问题。p o n c e 在1 9 9 2 年也 设计了一个用交互草图设计实体的系统【1 7 1 。一些系统接受通过扫描图纸得到的扫 描图，可以区分几何实体、文字、符号和注释等。理论上，这些系统可以用来分 析处理扫描手绘图，但草图固有的错误将会产生推测和解析算法问题，比如矢量 化问题。 处理描述三维场景草图的系统较少。主要的难题是怎样完成从三维场景草图 这样一个二维信息的图样中反投影，得到三维信息。该步骤具有信息的不完备性， 但人类能够处理这个困难。从已有的文献资料看，着眼于解释三维场景手绘图的 研究主要集中在重建过程，而对输入的类型是草图还是正规图样不感兴趣。下面 介绍几个输入草图的系统。s u f f e i 和b l o u n t 在1 9 8 9 年提出了一个系统i l 引，其最 终目标是将艺术家的手绘草图原稿数字化，并将其直接转化为三维模型。正如他 们指出的那样，要实现这个目标有大量的障碍，主要是因为缺乏尺寸约束和绘图 中的一些错误。l a m b 和b m l d o p a d h a y 在1 9 9 0 年也提出了一个从粗糙二维草图解 释三维对象的系统【1 9 】，该系统接受各种来源的草图，进行处理，重建对象，采取 先将一个角点标记为直角坐标系的原点，然后用相邻面顺序重建的方法。对于非 直角坐标面，需要交互式求助用户，因此该系统对流畅的草图( 含有非直角坐标 曲面) 显得不是十分理想。 目前，在草图的识别中，主要面临的一个问题就是转换不精确的、模糊的手 绘图为标准的线画图。许多方法已经被用来分析线画图，通过转换图片信息为几 何信息1 2 0 。然而图片信息的分析与在线草图笔迹的分析是不同的。文献 1 l 】用曲 率分析方法将笔迹分割成各种实体类型。文献 1 3 1 对笔迹中某点处的角度值进行 了分析。在文献【1 1 ，1 2 】中，角点被定义为曲率变化最大处。然而这种分析很容 易受笔迹的晃动、尖点、穿刺的影响。因此在手绘草图的整形中，该方法很难保 证正确性。文献【2 1 】提出了通过预先确定模板，然后通过匹配来确定线画图的方 法，文献 2 2 】提出神经网络方法，文献 1 6 】指出这些方法均要求用户明确指出想要 那种实体类型，因此，达不到概念设计的要求。文献 2 3 1 中的滤波主要是通过拉 平、回旋或拟合成b e z i e r 曲线、b 样条曲线和圆锥曲线来实现的。文献 2 4 】是通 过用最小二乘拟合来分割笔迹的。 除了笔迹分割和滤波之外，一般笔迹均是在笔迹的终点、交叉点处连接起来 的。但手绘草图是一个粗略的，非精确的图形，尤其是3 d 草图，经常会导致连 接过程非常复杂。文献【1 3 】考虑用一个距离公差来连接几何元素，在此基础上， 6 西北工业大学硕士论文第一章绪论 文献 2 5 】定义距离公差为实体长度的百分之一，文献 2 4 1 又进一步改进并提到了用 适应性的方法定义距离公差。 虽然草图c a d 识别是实现基于3 d 手绘草图交互界面遇到的一个首要问题， 但目前相关的研究工作却并不充分，而且还没有一个适用性较强的算法框架被提 出。然而它是实现计算机概念设计的一个前提条件，是人们必须跨过的障碍。所 以，随着概念设计热潮的兴起，该方面的研究已经引起了国内外人机交互领域和 机器视觉领域专家的重视，如i e e e 的会刊中系统、人和控制论学报( s m c ) 以 及其他杂志如计算机视觉( c o m p u t e r v i s i o n ) 等有越来越多的文章对此予以 讨论。 从现有的文献资料看，国内对这方面的研究还不太多，近来能查到的就是西 北工业大学对基于场景草图( 单视图) 的3 d 重建进行了深入研究、浙江大学基 于工程三视图的三维重建，西安电子科技大学对草图识别进行了研究，中科院软 件研究所对支持概念设计的c a d 系统进行了研究。 1 4 本文研究内容 西北工业大学在基于场景草图( 单视图) 的3 d 重建进行了深入研究，得到 了陕西省自然科学基金、江西省自然科学基金和江西省南昌航空工业学院测试技 术与控制工程研究中心开放基金的支持，项目名称分别为：复杂物体线图计算 机解释的机理研究和基于单幅线图建立复杂物体模型的研究等。本文所要 研究的“支持概念设计的手绘图在线识别研究”是该项目研究的一个组成部分。 本文内容安排如下： 第一章，概述了手写识别与人机交互的内容和支持概念设计的手绘图在线设 计，以及在线草图设计的研究现状。 第二章，首先概述了在线识别技术，然后对本文所涉及到的基本概念进行了 定义和分类，其中包括对线元类型的定义，如直线，折线段，二次曲线以及二次 曲线的个具体类型的定义，并对笔划进行了分类，为后续章节的展开做出了必要 的准备。 第三章，详细介绍了在线识别理论，按照笔划识别的顺序对识别理论进行了 剖析，包括折线段识别模块，二次曲线识别模块，复合线元识别模块。在复合线 元识别模块中，首先给出了非超复合线元和超复合线元的概念，其次介绍了非超 复合线元和超复合线元识别的具体实现方法。 第四章，阐述了作者研制的手绘图在线识别系统。首先，在系统概述中给出 了数据存储结构，以及系统面向对象的设计结构；其次，给出了二次曲线显示的 方法，并简单介绍了二次曲线的参数拟合方法，在此基础上给出了一种改进的椭 7 西北工业大学硕士论文 第一章绪论 圆参数拟合方法：最后，给出若干具体算例，并根据实验数据，总结出算法的特 点，并指出在线识别算法的有待改进之处。 第五章，结束语，对本文研究工作进行了总结。 西北工业大学硕士论文第2 章于绘图在线识别的理论基础 第2 章手绘图在线识别的理论基础 本章首先概括介绍了在线识别技术，然后给出了笔划的分类和定义，为后续 章节的展开奠定的理论基础。 2 1 在线识别技术概况 在线识别技术中一般包含以下四个部分：数据采集与预处理技术、笔迹分割 技术，特征提取、建模以及匹配技术，后处理技术。经过长期的研究，在这些方 面已有很多的研究成果，下面分别加以介绍。 2 1 i 数据采集与预处理技术 在线数据的采集一般要使用专门的外设，压敏式感应板和电磁式感应板都是 目前较为普及的手写输入设备，除此之外，还有其他的一些设备也可以用作输入 装置，如触摸屏、鼠标。这些设备的一个共同特点是：允许人以习惯的方式来书 写。在作者研制的系统中，就是采用鼠标来进行数据采集的。 数据采集后的下一步工作是进行预处理。预处理的目标是减少或消除笔迹数 据中的干扰。从输入装置采集的原始数据通常都含有少量的噪声，这种噪声是由 采集器本身的噪声或者量化噪声混合而成的，这种噪声对笔迹的影响表现为笔迹 坐标的快速抖动。减少这种噪声的方法是采用线型平滑算子或非线性平滑算子来 处理笔迹数据口睨8 1 。另外，还有一类笔迹扰动是由人的书写不稳定产生的，例如， 在起笔和抬笔时，手很可能会发生抖动造成笔迹弯曲或抖动，这种噪声通常只出 现在一个笔划的端点附近，因此在预处理中也可以采取适当的方法加以消除【2 8 刀】。 目前，大多数预处理方法都要求对原始的笔迹坐标数据进行重采样。通常是 以等距采样为多；也有以等时间间隔进行采样的方法，目的是提取笔尖移动的速 度信息。在作者研制的系统中，就是采用等距采样进行重采样的。 2 1 2 笔划分割技术 笔迹分割既可以被看成是预处理的一个步骤，也可以看作是与匹配算法紧密 结合的一部分1 30 1 。笔迹分割通常在两个层次上进行口1 】： ( 1 ) 外部分割：先将输入的笔迹从时间和空间上迸行划分，分解成具有识别 9 西：i l t _ 业大学硕士论文 第2 章手绘图在线识别的理论基础 意义的待识单元【2 。 ( 2 ) 内部分割：将待识单元继续进行分解，对文字识别来说就是将其分解成 字符单元( 对于西文) 或笔划单元( 对于中文等结构化字符) 。对图形笔迹的分解 则以某几种有特定含义的原型为单元来进行分解。例如，可以使用直线和圆弧作 为原型【3 2 】。 对笔迹进行正确的分割有时是非常困难的，特别是对连笔书写的西文字符的 分割【2 ”。对于这种笔迹的分割一般需要对特定的数据集进行有效的训练，以便使 系统能够对字符形态的变化进行适应。目前，较为成熟的分割方法有基于最大曲 率点的方法 3 3 】，利用笔的运动速度进行分割，使用空间位置特征进行分n t 3 5 】： 此外还有尺度空间法【3 6 】，以及基于特征点的分割方法1 3 7 - 3 9 j ，基于模型的分割算法 h ，有的方法还将分割与识别紧密地结合起来f 4 1 】。由于分割方法种类繁多，而且 与应用紧密相关，因此，通常无法构造出一种通用的分割算法。不同的应用，对 分割方法提出的要求可能完全不同，而且对算法的性能进行比较是十分困难的。 手绘图形的识别中，输入笔迹的分割也同样存在上面的问题。一般来说，图 形的形态特征与字符相比更为丰富，因此在对图形笔迹进行分割时通常以图形的 形态特征作为依据，另外，图形的结构特征也是用于分割的一种重要特征。 2 1 3 特征提取、建模及匹配技术 首先，特征的提取是模式识别过程中的一项重要工作，会直接影响到分类器 的设计及性能。所谓特征是对识别对象的某种性质描述的量化度量。一般认为， 特征的选择和提取过程是一个与应用紧密相关的过程，不同的识别对象，其特征 的选择和提取可能是完全不同的。即使对同一类识别对象，也可能由于识别方法 的不同而选择完全不同的特征。在实际应用中，特征的定义与选取方法的种类很 多，并没有一个统一标准来评价其优劣。 对在线手写识别来讲，特征的提取主要是针对输入的笔划数据，这些数据中 包括笔划的位置信息( 坐标) 、时问信息或速度信息以及笔划中每个采样点的压力 信息。按照其描述的特征区域的大小，可以分为两类：局部特征和全局特征。局 部特征的提取方法一般较为简单，例如，在很多方法中，通常直接使用笔划中采 样点的位置信息( 坐标) 或该点切线的斜率( 一次导数) 以及该点的曲率( 二次 导数) 作为特征，这种特征定义较为简单，计算复杂度低，因此被广泛采用【4 2 】， 但其缺点也较明显。由于特征的计算只使用了相邻的几个采样点的信息，因此容 易受到噪声点的影响，特征值不稳定，另外，局部特征对笔划形态信息的反映不 足，造成特征的分类性能变差。 人们为了克服上述不足进行了一些改进，基本方法是通过对局部区域的加窗 1 0 两北工业大学坝e 论文第2 章手绘图在线识别的理论基础 处理来获取窗口内的局部特征【4 3 】，有的方法还迸一步采用了自适应的窗口宽度 1 4 ，在一定程度上改善了局部特征对笔划形态信息的描述能力。 除了局部特征外，全局特征是另一种重要特征，两种主要的全局特征为形态 特征以及结构特征。形态特征是对曲线形态的一种量化度量。结构特征用于描述 图形或文字中基本部分( 一般称为“基元”) 的结构关系，其中，常用的基本度量 包括：基元之| 1 日j 的相对位置、夹角、基元之间的连接关系、如相交、包含、邻接等， 基元在平面空间中分布等，这些特征通常需要用某种数据结构进行有效地表示， 例如，树状结构、关系属性图、关系矩阵等等。结构特征的选取与待识别目标的 描述模型有着紧密的联系。 在模式识别中，另一个主要环节是对待识对象进行建模。模型的建立是在完 成了特征的定义和获取的基础上进行的。在线识别研究中，建模方法可以概括为 以下几类一j ： 1 ) 结构化模型 结构化模型通常用来描述结构特征丰富的对象，如汉字、各种符号以及几何 图形。结构化模型的建立是以结构特征为基础的，一般，用于建立模型的基本单 元，称为基元，在手写识别中，基元可以是一个自然分段的笔划，也可以通过专 门的分割算法对输入笔划进行进一步的划分来获得。 在结构化模型的研究中，人们提出了很多有价值的方法，例如，文献 4 5 ，4 6 】 中用严格的语法关系来描述基元之唰的结构关系。文献 4 7 给出了一种用图论模 型来描述基元的结构关系的方法。结构化模型的特点是对图形或文字中的结构信 息表达得较充分，但对形态信息，则几乎无法描述，因此，该模型往往需要通过 其它方法来弥补这一弱点。 2 1 统计模型与模糊模型 这两种模型都是用来描述数据中含有不确定信息的模型。由于各种因素会使 数据中的不确定性信息大大增加，因此，提高模型的适应能力是改善识别系统性 能的必要手段。统计模型是一个发展较早、比较成熟的模型，常用的模型包括： 隐马尔可夫模型【4 8 5 0 1 ，自组织特征图( s o f m ) 模型 5 1 , 5 2 ，延迟网络模型 5 3 , 5 4 l 等等， 它建立在将输入数据看作随机数据的基础上，通过对随机样本集的学习，获得数 据的各种统计特征，并以此建立模型。 模糊模型也是用来描述不确定信息的一种有效模型，它的建立一般是通过对 特征的模糊化来实现，例如，使用模糊语言对特征空间进行模糊化；建立特征量 之间的模糊关系以及运算 5 5 , 5 6 1 等。该模型的一个突出优点是可以将专家知识或先 验知识直接引入模型中，另外，与统计模型相比，模型的训练对数据样本的要求 较低，并且模型的稳定性很好。 3 1 神经网络模型 西北t 业人学坝 j 论文第2 章 手绘图在线识别的理论基础 该模型是通过使用一定的网络拓扑结构以及连接权值来记忆和表述图形的形 态特征，通过选择适当的网络模型可以获得较好的鲁棒性和实时性 5 3 , s i 】。由于神 经网络的固有特点，使该模型往往对训练样本、训练算法的依赖程度较高，对书 写方式变化的适应能力较弱。 需要指出的是，在一个实用的识别系统中，有时需要依靠多种模型建立所谓 的混合模型，来进一步提高识别性能。 在线识别中，匹配算法的设计也是以特征和模型的选择为基础的，针对不同 的应用，人们提出了大量的方法，应用较广泛的有：基于形态特征的匹配算法、基 于统计模型的匹配识别方法、基于模糊模型的匹配识别方法、基于神经网络的识 别方法等等。除此之外，基于混合模型的识别方法也是一个研究热点，并且也获 得了相当多的成果队5 8 j 。 总的来说，虽然目6 u 已取得了相当丰富的研究成果，也推出了一些实用的识 别系统，但从实用角度来讲，还有许多的工作要完成，其发展还有赖于理论上以 及硬件技术上的突破。 2 2 笔划的基本概念与分类 2 2 1 线元类型的定义 草图识别的基本功能就是通过早期的处理将初始笔划转换为想要的几何对象 5 9 1 。表现为单纯线型的最基本的几何线条称为线元【6 0 】，本文的线元包括：直线、 折线段、椭圆、圆、椭圆弧、圆弧、抛物线、双曲线。 2 2 1 1 直线的定义 与直线方程产生的标准直线不i 司，手绘直线是借助图形交互设备随意绘制的， 在这种情况下，人们通常根据以下原则柬判断输入笔划是否是直线：笔划首尾点 距离与输入点序列的累积弦长的比值是否大于一个给定的闽值来判断。本文定义 直线率为笔划首尾点距离与输入点序列的累积弦长的比值。 设输入笔划的点序列s ：p o ，二，县，丘其中只( 五，z ) ，i = 0 ，1 女。 笔划首尾点距离d 为 d = 9 只一只| 1 = ( x 。一x k ) 2 + ( k x ) 2 ( 2 1 ) 笔划的累积弦长l 为 两北下业火学坝j 论文 第2 章手绘图在线识别的理论基础 l ：自p 一圳：圭瓜j 了不磊了 ( 2 _ z ) 直线率也为 r z ：一d ( 2 3 1 l 由于l d 9 ，故r z o ，1 。可以看出直线率r z 越趋近于1 ，笔划是直线的可 能性越大。直线率r = 的判定阈值可由实验或经验确定。 2 2 1 2 折线段的定义 不同于手绘直线的定义，折线段的定义要复杂一些，首先要从笔划得到可能 的折线段，这里只作简单的介绍，在之后的章节中将具体讨论折线段的求解方法。 首先对笔划进行折点检测，通过检测到的折点将笔划分割，对分割后的各段进行 直线拟合，求相邻拟合直线的交点，得到最终的折线段。本文通过定义折线段率 来判别笔划是否为折线段。 设得到的折线段的折点序列为 ( ，y o ) ， ：，y 2 ) ，( 毛，咒) ，其中包括笔划的 首尾点。这样就可得到折线的第i 段的直线方程，即将( 一+ m 一。) 和( 一，y i ) 连接起 来的直线方程如下： 兰导= 警 ( 2 4 ) x x f lt x 上式可以改写为隐式方程： atx+biy+c120(2-5) 其中，i = 1 ，2 ，3 ，“，4 = ( y ，- y , 一1 )骂= ( x i 一薯一1 )c i = 一i y ，一一m l ，而 p = 4 2 + e 2 是折点( 蕾+ 只一。) 和( t ，只) 之间的距离，笔划上任意一折点( t ，只) 与上述直线段的距离d j 为 嘭：掣 6 ， 折线段率吃为 器 警 i = l ，2 ，“= 1 ，2 ，f ( 2 7 ) 两北l t 业人学烦士论文第2 章于绘翻在线识别的理硷慕础 其中：“为折线段的段数，m 为折线段的第i 段所对应的笔划的采样点数。 f l = _ - t - d ，o ，故r 【o ，+ 叫，可以看出折线段率毛越趋近于o ，笔划是折线 段的可能性越大。折线率兄的判定阈值可由实验或经验确定。所以判断输入笔划 是否为折线段的原则为：折线率是否小于一个给定的阈值。 2 2 1 3 二次曲线的分类及定义 就像手绘直线和折线段一样，手绘二次曲线也是由人借助图形交互设备随意 绘制的，在这种情况下，手绘二次曲线与由二次曲线方程产生的标准二次曲线不 同。为了引出手绘二次曲线各类型的定义，本文首先介绍标准二次曲线中关于不 变量的一些知识。 曲线方程一般是随着坐标系的改变而改变的，但既然这些方程都是代表同一 条曲线，它们的系数应该有某些共同的特征是不随坐标系的改变而变化的，将陆 线方程系数的一个确定的函数，如果在任意一个直角坐标变换下它的函数值不变， 那么就称这个函数是一条曲线的一个正交不变量，简称为不变量。不变量既然 与直角坐标系的选择无关，于是它就反映了曲线本身的几何性质。 在给定的直角坐标系中，设平面上二次曲线的一般方程为 4 x 2 + b x y + c y 2 + d x + 点y + f = 0( 2 - 8 ) 其中a 、口，f 不全为零。令： 料巨 弘， 则、是二次曲线的不变量，为二次曲线的半不变量，k 在旋转下不变， 并且对于二= 五= o 的二次曲线，k 在平移下也不变。由二次曲线的不变量得到标准 二次曲线的类型和形状，见表2 1 。 考虑笔划在欧几里得空间的不变性，本文采用了文献【2 3 1 中的归一化处理方 案，设一：+ 兰二+ c ：2 ，从而使系数在控制范围内变化，有利于阈值的确定。 2 现在定义手绘二次曲线，本文是通过二次曲线的不变量来确定手绘二次曲线 的。首先通过笔划的点序列进行二次曲线拟合，得到二次曲线的一般方程，如公式 2 8 所示。设输入笔划的点序列为s ：p o ，只，只，其中 f ( 爿，r ) ，i = 0 ，l k 。笔划点序列中第i 点到二次曲线方程的偏差s 为 s = 戤2 + b x ，r + c z 2 + d x , + e z + f( 2 1 0 ) 1 4 =k d 一2 e 一2 f b 一2 c e 一2 4 b一2d一2 f i b 一2 c m 旧一眨 = l c+爿 西北工业大学硕士论文第2 章手绘图枉线识别的理论基础 表2 - 1 由不变量判别二次曲线类型和形状 类型类别 识别标志