基于手绘草图的工程图档检索技术

基于手绘草图的工程图档检索技术 南京航空航天大学硕士学位论文基于手绘草图的工程图档检索技术姓名:李雪峰申请学位级别:硕士专业:计算机应用技术指导教师:周良20081201南京航空航天大学硕士学位论文 摘 要 随着信息技术的高速发展,电子图档已逐渐取代传统的纸质图档,在各行各业发挥着巨大的作用。如何从图档数据库中方便、快捷地获取所需图档是一个难题。目前,图档检索一般是基于图档的项目名称、设计人、图号等关键字完成的。基于关键字检索技术速度快、实现简单,但人工标注费时费力,且图档内容往往不易用文字表述。 为此,本文提出了基于手绘草图的工程图档检索技术。基于手绘草图的图档检索隶属于基于内容的图档检索,考察的重点是图档的图形特征,而非设计人等关键字,这使得图档检索更加的直接、明确;另外,使用手绘草图作为检索条件大大方便了用户检索意图的表达。 论文对手绘草图的识别以及图档检索技术进行了较深入的研究,提出了基于手绘草图的工程图档检索系统框架,实现了原型系统,主要研究内容如下: 1 提出了基于自适应特征点检测的手绘草图识别方法:在草图识别中引入支持向量机技术,实现了用户自适应的特征点检测,提高了草图识别的准确性。 2 提出了图档的多重存储结构:在以基本图元存储结构的基础上,增加了不依赖于图档绘制方式的组合图元存储结构,一定程度上解决了一图多意对图档检索的影响,提高了图档的查全率和查准率。 3 提出了多重特征逐步过滤的图档检索方案:综合考虑了图档的形状特征、拓扑结构、空间关系三类特征,利用各类特征逐步过滤,缩小检索范围,提高了的检索效率。关键字:草图识别,支持向量机,特征点检测,存储结构,相似度,工程图档 i 基于手绘草图的工程图档检索技术 Abstract With the rapid development of the information technology, the electronic drawing-documents are gradually playing important roles in all walks of life replacing the traditional paper files. However, it is still a difficult work to obtain required drawing-documents from the drawing-documents database quickly and conveniently. Currently, the drawing-documents retrieval is usually accomplished based on the keywords, such as project name, designer and document number. Keyword-based retrieval technology is fast and simple, whereas manual labelling takes a lot of troubles. Moreover, it is not easy to describe the content in drawing-documents with wordsAs a result, in this paper we propose a novel sketch-based engineering drawing-documents retrieval technique, which belongs to the content-based image retrieval technology. It emphasizes on the graphic features of documents rather than keywords, therefore it makes the retrieval more direct and clear. Furthermore, it is more convenient for users to express their retrieval intention when the hand-drawn sketches are used directly as the retrieval conditionsAfter deep investigation on the sketches recognition and drawing-documents retrieval technique, this paper presents a system framework of the engineering drawing-documents retrieval technology based on hand-drawn sketches, and realizes a prototype system as well. The main researches are 1 Proposes a sketch recognition scheme based on adaptive vertex detectionWe bring Support Vector Machine into the sketch recognition and realize the user-adaptive vertex detection, consequently the recognition rate is improved2 Proposes the multiple storage structure of the electronic drawingsBased on the basic element storage structure, we add the combination element storage structure, which is independent of the graphics drawing methods. This amelioration, to some extent, resolves the problem of multi-understanding of one image and improves the recall ratio and precision ratio at the same time3 Puts forward a multi-feature-filtering retrieval schemeWe consider three kinds of features, i.e., we combine shape, topology as well as spatial relationship to filter the database images and gradually narrow the search scope, consequently we improve the efficiency of the retrievalKey words: sketch recognition, Support Vector Machine, vertex detection, storage structure, similarity degree, engineering drawing ii 南京航空航天大学硕士学位论文 图、表清单 图2.1 工程图纸检索系统功能及流程 9 图2.2 形状特征. 13 图2.3 拓扑特征. 13 图3.1 手绘草图识别流程 16 图3.2 笔画预处理结构. 17 图3.3 冗余点消除17 图3.4 去尾处理示意图. 18 图3.5 方向图 19 图3.6 曲率图 20 图3.7 多旋转笔画及其方向示意图. 21 图3.8 闭合检测. 21 图3.9 传统SVM与代价敏感SVM比较23 图3.10 自适应特征点检测流程. 23 图3.11 基本笔画种类24 图3.12 特征面积示意图. 25 图3.13 传统的控制点求法拟合结果 26 图3.14 改进后的控制点求法拟合结果. 26 图3.15 Snap Rounding 示意图. 28 图3.16 草图识别结果规整29 图4.1 图档的多种理解. 32 图 4.2 Bentley-Ottmann算法示意图40 图4.3 交点探测结果示意图. 41 图4.4 组合图元提取(一). 42 图4.5 组合图元提取(二). 42 图4.6 组合图元提取(三). 42 图4.7 图元层次结构 45 图4.8 不同层次考察的图形. 45 图5.1 图档检索流程 48 图5.2 拓扑关系. 51 图5.3 图档拓扑结构图. 51 图5.4 拓扑图谱计算 52 vii 基于手绘草图的工程图档检索技术 图5.5 空间关系. 53 图5.6 空间关系表示 53 图6.1 系统功能示意图. 58 图6.2 系统类图. 59 图6.3 草图识别时序图. 59 图6.4 图档检索时序图. 60 图6.5 特征点检测结果对比图62 图6.6 手绘草图识别结果 63 图6.7 手绘草图识别结果对比图 64 图6.8 图档多重存储实验图. 65 图6.9 检索结果对比图. 66 图6.10 图档检索查全率. 67 图6.11 图档检索查准率. 68 图6.12 草图输入界面69 图6.13 草图识别界面69 图6.14 图档检索界面70表3.1 基本笔画排序权值 27viii承诺书本人郑重声明:所呈交的学位论文,是本人在导师指导下,独立进行研究工作所取得的成果。尽我所知,除文中已经注明引用的内容外,本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体,均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件,允许论文被查阅和借阅,可以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或其他复制手段保存论文。 (保密的学位论文在解密后适用本承诺书)作者签名: 日 期:南京航空航天大学硕士学位论文 第一章 绪论 1.1 本文研究背景 工程图档在社会各行各业普遍应用,发挥着十分重要的作用。对于一个企业而言,工程图档是极其宝贵的知识财富、经验累积;对于工程人员而言,这些文档、图纸是他们极其重要的学习资料、交流手段,更是设计灵感和创新思维的可靠来源,有实验证明有近 80%的新图档是基于已有图档的基础之上的。随着信息技术的高速发展,CAD等电脑制图软件不断涌现,电子图档已逐步取代纸制图档,且数量和种类都迅速增长。然而,图档数目的迅猛增长以及各类电子图档的不断涌现给查阅带来了问题。如何高效地组织和管理电子图库并且快速地从庞大的数据库中准确地检索出特定的图纸或文档成为急需解决的难题,也吸引了越来越多的专家学者投入到对其的研究之中。 如今,工程图档的管理及检索主要有以下几种方式:第一,针对纸制图档,企业单位成立专门的图档管理部门,通过人工将各类图纸按类型、作者等信息进行分类管理,需要查阅时通过人工一份一份地找。这种方式工作量巨大,费时费力且很容易出错。第二,针对电子图档,配置专门的计算机对图档进行存储,这种方式由于缺乏统一的图档管理系统,其检索仍然是由专门的管理人员人工完成的,实质上等同于第一种方式,只不过是通过电脑存储电子图档而非纸质图档而已,同样费时费力。第三种方式是采用专门的图档管理系统,存储统一格式的电子图档,通过对每份图档标注项目名称、作者、日期等信息来实现基于文档关键字的图档检索,这种方式也是当前大多使用的图档管理方式。这种基于关键字检索技术的图档管理方式方法简单,检索速度也很快,因而有一定的优势,然而同样存在着十分明显的缺陷:首先,对每份文档需要人工添加诸如项目名称、工作阶段等信息,这是一项十分繁重的工作;第二,大部分所谓的关键字并没有真正的反映出文档、图纸的本身内容。 1.2 研究意义 基于手绘草图的工程图档的检索技术的出现很好地弥补了上述三种方式中的诸多缺陷。其工作方式是用户根据自己的检索意图通过人机交互界面输入查询草图,系统根据用户输入的查询草图从数据库中检索出相似的图档。基于手绘草图的图档检索方式与基于关键字的图档检索技术相比更加符合用户正常的行为习惯,更加的人性化。 当人们想要得到某个不易描述清楚的事物时,最直接的想法便是找个相似的事物作例子,比如去理发店理发,说不清要理什么样的发型时最直接的方法就是在发型杂志上找到理想发型图作为样图。这便是基于内容的图档检索的基本思想。通过采用基于内容的相似性匹配的方法1 基于手绘草图的工程图档检索技术 进行检索很好地克服了人工标注主观性强且费时费力的缺点。 手绘草图作为符合人类习惯的交流方式,是人类的一种常用的思路外化Externalization和12通信交流方式 ,当用语言无法表达清楚的时候,人们很习惯的用手来比划。所以,手绘草图很自然地被人们想到应用到人机交互中。基于手绘草图的人机交互是用户使用图形、标示等几何形状对用户意图进行模糊逼近的一种图形输入方式,符合人类思维特征,便于用户描述创34造性思维活动 。手绘草图以视觉空间媒体形象、直接地表达和传递概念,与传统的图形图像工具相比较,更加方便、自然、随意,可表达模糊概念,十分适合人的使用习惯。将手绘草图引入到工程图档检索技术的有着明显的先天优越性和适应性,因而,基于手绘草图的图档检索技术的研究具有非常重要的意义及很好的实用价值。 1.3 国内外研究现状 基于手绘草图的图档检索包括两个环节,首先用户需要绘制出自己想要检索的工程图档的草图,传递给计算机,计算机对用户的输入进行识别,作为检索条件。这是一个典型的人机交互过程。从计算机产生以来,人机交互就不断的得到研究发展,新的人机界面不断出现,从最初的插拔插头、批处理、命令行界面到现在比较熟悉的菜单图形界面等等,人机交互的频带不断扩张。 如今新兴的语音交互、手势交互、三维交互等等不断涌现,人机交互技术日趋成熟。尤其是笔式交互Pen-based Interaction的出现,“数字墨水”的出现更是极大地推动了手绘草图的发展,使得基于手绘草图的工程图档检索技术的提出成为可能。 第二,在完成用户输入识别之后,基于手绘草图的工程图档检索便转化为基于内容的图档检索,如何抽取图档的内容特征,并依据特征相似度检索出相似的图档是该环节的关键。计算机图形学经过多年的研究已经发展成为一个体系比较完善的学科,内容日趋完善,图形的特征抽取,图形间的匹配都有很多比较成熟的算法,这就为基于草图的工程图档检索技术奠定了一定的基础,使其最终的实现成为可能。 手绘草图识别技术和工程图档检索技术由于较强的应用需求吸引了众多专家学者投入研究,下面分别介绍这两项技术的研究现状。 1.3.1 手绘草图识别技术的研究现状 准确的草图识别是基于手绘草图的工程图档检索的前提和关键,但是手绘草图天生具有一定的模糊性和随意性,这也是草图识别的难点。手绘草图识别的研究早在二十世纪七十年代就已出现了,但是由于受技术条件的限制,其性能和效果不尽人意。二十世纪九十年代以来,小型化、便携式和无线化设备的发展和普及,“数字墨水Digital/Electronic Ink”,“智能纸Intelligent 56Paper/Electronic paper”和“平板计算机Tablet PC”等 的出现,使得手绘输入及相关技术研究和应用得以复苏。尤其是 W3C推出的 InkML标准草案实际上将“数字墨水”作为一种新2 南京航空航天大学硕士学位论文 78910型多媒体数据类型 ,这使得“还墨水以本色”,并使人类不再需要按计算机要求扭曲自11己最自然的交互方式成为可能 。这极大地推动了以手写体Handwritten和手绘草图Sketch为1213核心的笔式交互技术Calligraphic User Interface 的发展和应用,它以模拟现实的纸和笔为目标,具有易用、自然、高效和利于创造性思维等特点,成为感知交互技术Perceptual User 14Interface 和多通道用户接口技术Multi-modal User Interface研究中的关键课题之一。这个阶段出现了大量的原型系统和应用产品。 1516麻省理工学院人工智能实验室开发的支持机械设计的手绘交互系统:ASSIST 。它能解释和模拟大量的简单手绘机械系统,并能根据用户的反馈和上下文信息部分解决“一图多意”17的模糊性问题。麻省理工学院开发的支持 UML设计的笔试交互系统:Tahuti 。它采用多层识别框架来识别用户自由绘制的 UML设计图,并可以将之转换成 Rational Rose 中的 UML 图。18卡耐基?梅隆大学机械工程系设计开发的支持概念机械设计的工具:SketchIT 。能将草图转化为几何描述并向设计者提供多个基于此草图的设计方案。以 CMU 的 Garnet 系统为原型开发1920的 SILK 。该工具可让用户自由的绘制用户界面并可实时地将用户的界面草图设计自动转化为可运行的界面实现。加州大学伯克利分校的 GUIR实验室设计的基于草图的网站设计软件:21 22DENIM &SATIN 。它允许网站设计者在不考虑具体细节的情况下对网站设计过程中的诸如网站结构等重要问题进行思考,还可以把设计的结果输出为 6HTML格式的文件进行测试。同时也设计开发了支持笔式交互应用的开发工具包 SATIN。Colorado大学的 Mark D. Gross 研究小23 2425组研发的 Electronic Cocktail Napkin 。其目的是设计一个允许使用者进行各种类型设计、建模和仿真的自由绘制系统,对使用者瞬间的思想火花进行捕捉和验证。该小组也开发了通过26Sketch 来设计网站的工具 WebStyler 。Xerox PARC 开发的支持非正式会议的电子白板系统:Tivoli。它作为笔式交互研究中的一个划时代的笔式交互系统,原创性地提出了一些笔式交互的基本概念,如手势(Gesture)、笔划(Stroke)等。乔治亚理工大学、东京大学和 Xerox PARC 联合研制的:Flatland,它是继 Tivoli之后又一著名的电子白板系统。该系统的特征主要表现在三个方面:对白板内自由勾画对象的空间管理;可以对各种应用语义对象灵活的配置交互行为;27对使用白板的历史纪录的有效维护。东京大学设计实现的非精确的三维设计工具:Teddy 。它能根据用户绘制的二维自由笔划的轮廓自动构造合理的三维多边形表面,它在很大程度上简化了三维建模中构造任意外形的三维实体的工作。 国内的诸多研究机构也从交互模型和体系结构、识别算法等不同角度对笔式交互进行了研究。如中国科学院软件研究所的人机交互与智能信息处理实验室在手势识别,笔式字处理、概28念设计和交互平台等方面的研究 。西安电子科技大学谢维信教授领导的小组针对军事态势图中的手绘图形研究了多种图形识别方法,满足了军事应用的部分要求。 除了特定领域的手绘草图识别之外,领域无关的手绘草图识别越来越受到专家学者的关注。3 基于手绘草图的工程图档检索技术 领域无关的手绘草图识别不依赖于具体领域的知识背景,而着重于草图的图形特征,其图形种类理论上无限多。在领域无关的草图识别方面,Sezgin,T.M.在文献2930中提出了一套手绘草图的预处理方案,以及笔画顶点的探测方法,较好地处理了草图的随意性和模糊性。Yu和 Cai在文献31中提出了一个相对完整的领域无关的草图识别系统,该系统引入了特征面积的概念,32对基本笔画有较高的识别率。在 Yu和 Cai的基础上 Paulson, B.等 中提出了一个精准的手绘草图识别系统,该系统引入了两个新的特征值 NDDE、DCR,在识别率上有一定的提高,同时对识别图元种类进行了扩充。 综上所述,现有的草图识别算法主要还是分为两类:第一类是针对某一特定领域的手绘草图识别,在这种情况下,图形实体种类有限,如 UML中实体一般只限于用户、类、连接线等几种,电路图中的实体往往只限于电阻、电压、线路等。解决这类问题的方法主要是对一部分草图样本按某种方案抽取特征,训练分类器,使用训练有素的分类器对用户绘制的草图进行分类识别。第二类是领域无关的手绘草图识别,在这种情况下,绘制的草图可能是各种各样的。解决这类问题的方法只要是通过对草图的分割将草图识别为直线、曲线、圆等基本图元的组合体,对每类基本图元的识别主要也是通过几何特征。在本文中,手绘草图用以表达工程图档的检索意图,而工程图档理论上有无限多类图形实体,所以需使用领域无关的草图识别。 1.3.2 工程图档检索技术的研究现状 企业图档管理的手段大致经历了三个阶段,相应地,在不同阶段检索图档的方式也不相同。手工管理阶段,企业单位专门设置履行文档管理的部门,这种管理方式下,只能靠人工来检索图档。由于企业的图档数量庞大,所以这种方式成本很高,且检索效率十分低下。计算机中心管理和分布式计算机管理阶段,这两个阶段都是使用计算机对企业的图档进行管理,使用基于关键字的检索方式来检索需要的图档。计算机管理阶段在图档的检索方面比手工管理方式要强很多,用户给出与所需的图档相关的关键字,系统根据之前建立的关键字到图档的映射来查找包含有关键字的图档。关键字检索方式最显著的优点是检索速度非常快,并且基于文本的索引技术已经很成熟。信息和关键字的匹配上有两种方法,一种是人工标引,一种是自动提取。人工标引对于信息的准确度方面是效果比较好的,但是也面临几个主要的缺点:一是人工标引工作量太大,在海量系统中几乎是不现实的。二是人工标引的信息主观性比较强,有时候不能恰当的反映图档的真实信息或者反映的信息不完全(后者几乎总是存在)。自动提取方法的难点在于如何为图档提取正确的文字信息。由于信息组织的多样化以及难于判定具体的组织方式,很难确定哪些信息是与图档相关的。这种方法通常采用启发式规则来进行信息提取,并通过无用信息过滤等技术来尽可能的提高信息的准确性。 基于草图识别的工程图档检索隶属于基于内容的视觉信息检索(CBVIR)的范畴,其目的33是在大量的图纸库中检索出与用户输入的草图相似的并且是用户所期望的图纸。Chang等 的4 南京航空航天大学硕士学位论文 工作可以认为是基于空间关系的图形检索研究的始祖。他们通过使用 2D-String的方法对图标图形进行建模。每个字符代表图标在二维空间关系上的位置。这种方法使得对图形的检索转化为34更简单的对字符串的匹配。在 Gudivada和 Raghavan的论文 中,他们把研究对象定为由顶点关联起来的图形符号。这些对象间的空间关系通过连接质心的边的集合来表示。通过对一对边35 36集合的相似度计算完成对空间关系图的相似度计算。Gudivada 、El-Kwae和 Kabuka 对字符串方法进行了扩展。前者提出了所谓的 R-strings方法,后者则在空间关系匹配上引入了拓扑37 38关系和方向关系约束。Matusiak 利用曲率缩放空间(CSS)匹配草图的轮廓信息;Sciascio39采用基于傅立叶描述子的形状信息进行形状匹配。Fonseca等 利用笔划的层次结构、形状信息来检索复杂的图形,该方法对图形数据库进行高维索引,进而可以适应数据量大的草图库。4090年代初,人们从开始分析两个图形之间匹配的复杂度,并在以 S.K. Chang 分级,被命名为41type-0和 type-1的相似度下找到了结果。Tucci等人 研究了一个对象存在多个实例的情况,并42且发现这是一个完全 NP问题。之后,Guan等人 证明了在完全不同对象的情况下该问题同样的无限。在对象退化为点的情况下,相似度组织的计算问题被称为点模式匹配。这个问题在著43名的群问题-计算几何中得到研究。Cardoze和 Schulman 给出了一个随机算法来匹配经过平移2和旋转的点,但没有考虑尺度的变化,在匹配 n个点的情况下,其复杂度为 。此外On logn南京大学多媒体研究所孙正兴教授领导的 magic 项目组,也提出了许多基于轮廓、层次等特征的草图的检索技术。 1.4 研究领域现存问题 尽管基于手绘草图的工程图档检索的研究受到很多专家学者的广泛重视,并且已经取得了一定的成果,但是仍处于研究阶段,亟待解决的问题有以下几个方面: (1)草图检索是以用户输入的草图为依据进行检索的,然而用户手绘草图天生具有随意性、模糊性以及较大的用户相关性,如何正确地捕捉用户的意图,准确的识别草图且不受用户绘图习惯的影响是一个难题。 (2)用户手绘的草图以及数据库中存储的图档往往都是复杂的组合图形,同一图形可以存在多重理解方式。如何解决一图多意对图档检索的影响,确保图档检索的准确率。 (3)基于草图的工程图档检索是基于内容相似性的,然而单单一个笔画其特征值是很多的,如何选择出最具有代表性的特征值进行检索是十分值得研究。 (4)在基于手绘草图的工程图档检索中,用户输入的草图往往是目标图档中的一个子图,如何实现子图匹配也是十分重要的。 (5)待检索的数据库庞大,在保证检索质量的同时如何提高检索速度十分重要。 (6)如何充分利用用户对检索结果的反馈,使检索系统具有自学习能力,不断完善。 5 基于手绘草图的工程图档检索技术 1.5 本文主要研究内容及组织 本文进一步研究了手绘草图的识别技术以及基于内容的图档检索技术,在此基础上提出了基于手绘草图的工程图档检索的总体方案,并依据方案初步实现了原型系统。 1.5.1 本文的主要内容 (1)提出了基于自适应特征点检测的草图识别方法 特征点检测是草图识别的关键环节。不同于传统的设置笔画速率阈值及曲率阈值进行探测的方法,本文将支持向量机技术引入到特征点检测中来,较好地实现了用户自适应的特征点检测,并以此为基础实现草图识别。 (2)提出了图档的多重存储结构 在以往的图形匹配中,图档往往采用单一的基本图元存储结构,图档的存储结构和理解方式均依赖于用户的绘图方式。在本文中,增加了不依赖于用户的组合图元存储方式,实现了图档的多重存储,提高了检索的正确性。 (3)提出了多类特征逐层过滤的图档检索策略不同于以往的单层次、单类特征的基于内容的图档检索方式,在本文中,我们充分利用工程图档的层次性,且结合使用了图形的图元形状、拓扑结构以及空间关系等多类特征逐步缩小图档的检索范围,一定程度上提高了检索效率。 (4)完成了基于草图的工程图档检索系统的设计及开发 以本文讲述的图档检索框架为基础初步开发了原型系统,并从实验的角度分析了关键技术对检索结果的影响。 1.5.2 本文的组织结构 围绕上述内容,论文共分七章,各章节的具体安排如下:第一章 绪论 分析了论文研究背景,并对基于手绘草图的工程图档检索技术中所涉及到的草图识别技术及基于内容的图档检索的研究现状进行了分析与总结。给出了论文主要研究内容、研究目的与意义。 第二章 系统框架设计 提出了基于手绘草图的工程图档检索系统的总体框架设计,对关键技术进行了介绍。 第三章 手绘草图的识别 给出了手绘草图识别的具体流程,并对草图预处理、特征点检测、草图识别、草图规整以及用户反馈五个环节分别进行了具体的讲述。 第四章 图档多重存储结构 介绍了 XML存储方式,并给出了本系统中设计的基本图元存储结构以及组合图元存储结构对应的 XML设计模式。 第五章 图档检索 给出了基于草图的工程图档检索的具体策略,重点讲述了各类特征的提6 南京航空航天大学硕士学位论文 取方法、相似度计算公式以及特征过滤方法,同时描述了本系统的用户反馈机制。 第六章 系统实现 采用 UML 对系统进行了分析设计,给出了系统功能模块图以及部分类图、顺序图。给出了特征点检测实验结果图,并对基于传统特征点检测的草图识别结果和基于自适应特征点检测的草图识别结果进行了对比分析。给出了图档多重存储实验图,对使用多重存储和使用单一存储的检索结果进行了对比分析。最后给出了系统的部分运行界面。 第七章 总结与展望 总结本文研究工作,并展望了进一步的研究工作。 7 基于手绘草图的工程图档检索技术 第二章 系统框架设计随着计算机技术的迅速发展,越来越多的企业使用办公自动化软件实现无纸化办公,提高工作效率,实现资源共享。电子图档的管理对于一个企业而言有着无可比拟的重要性,尤其受到重视,良好的图档管理需要有较好的安全性,较高的共享率等,快速的图档检索更是图档管理系统的关键要求。现有图档管理系统中的图档检索主要是基于关键字检索技术,虽然这种检索方式速度比较快、思路比较简单,但是存在着固有的不足:一是引关键字工作量太大,在海量系统中几乎是不现实的。二是人工标引的信息主观性比较强,往往不能恰当地反映图档的真实信息。基于手绘草图的工程图档检索隶属于基于内容的图形检索技术,主要根据图形的几何特征来计算图档间的相似度,并依此实现检索。这种检索方式不需要对图档进行关键字标引等工人处理,大大减轻了工作量。此外,检索是直接基于图形相似度的,更加客观,不存在主观干扰的情况。引入手绘草图作为检索条件使得用户的检索意图更加容易表达,检索目标更加明确。本章给出了基于手绘草图的工程图档检索系统的总体框架,并对关键技术进行简要介绍。 2.1 系统总体框架 图 2.1为基于手绘的草图工程图档检索系统的整体框架,主要由三部分组成:草图识别、图档存储、图档检索。草图识别部分主要完成用户输入草图的识别任务,该部分的关键在于排除草图固有的随意性和模糊性的干扰,准确获取用户的意图。首先,对用户输入的笔画进行冗余点去除、去尾操作等预处理,然后进行特征点检测,之后使用各类基本笔画尝试拟合,对组合笔画先进行笔画分割再分别识别。系统将识别结果规整处理后返回给用户,用户对识别结果进行反馈。图档存储部分主要完成两项工作:一是将各类工程图档转换成 XML格式进行入库。二是将识别完成的查询图档转换成 XML格式。在本系统中,图档采用两种存储结构,一种是基本图元存储结构,即将图档分割成多边形、圆等基本图元进行存储,这种存储方式依赖于图档的绘制方式。另一种是组合图元存储方式,将图档按照不依赖于用户绘制方式的统一标准分割成若干封闭的组合图元。同时采用两种存储结构可以在一定程度上解决一图多意对图档检索的影响。图档检索部分综合考虑图档形状特征、拓扑结构以及空间关系三类特征,利用三类特征对数据库图档逐层过滤,最终按总体相似度的大小进行排序,将具有最高相似度的结果集返回给用户。 8 南京航空航天大学硕士学位论文 图 2.1 工程图纸检索系统功能及流程 2.2 关键技术手绘草图识别、图档多重存储以及图档检索是本系统中的关键技术,本节进行简要介绍,后续章节将做更加具体的阐述。 2.2.1 草图输入及识别 以手绘草图作为查询条件更加方便于用户表达自己的意图,利用手绘草图用户可以很方便、自由地表达图档的拓扑信息、形状信息等等。然而这些优越性都是以计算机准确地识别草图为前提的,只有正确理解用户输入草图所表达的意图,才能准确地检索出目标图档检索。 9 基于手绘草图的工程图档检索技术 草图识别指的是将通过笔式交互获取的模糊的草图表达映射至精确的图形表达。草图识别注重于草图图形构成的理解,需要从用户勾画草图的图形构造及表现中挖掘图形约束,将自由不规则的草图图形映射成规则的几何图形。然而,手绘草图固有的模糊性和随意性给草图识别设置了很大的障碍。草图信息的模糊性在于:手绘草图图形构成的完整性随着手绘过程而进化,且与其所表达的用户意图间无固定的映射关系。例如,用户输入一条直线,但是由于是徒手操作,笔画很可能有一定的弯曲(实际上是肯定会有的),这就使得该直线有可能就被识别为曲线。用户手绘输入的随意性表现在:用户的输入意图与领域背景、思维方式、手绘习惯和偏好等多种特性相关,手绘过程也会受到图形结构和设备特性等多种环境因素的影响,用户手绘图形的结构及其内部关联都带有很强的主观性。这两个特性给手绘草图的识别设置了很大的障碍,但也正是这两个特性决定了手绘草图在表达创造性思维方面的优势。因此,在草图识别的过程中,系统一方面应当尽可能地保留用户绘制的自由度,另一方面应尽量屏蔽模糊性和随意性的干扰,准确地把握用户意图。手绘草图识别主要分为笔画预处理、特征点检测、图元拟合、草图规整以及相关反馈五个部分。笔画预处理 预处理部分主要是去除由于用户绘制的随意性以及设备的局限性等因素所带来的噪声,如重复取样点、无意识的勾角等。此外,预处理部分还需计算笔画的方向图、曲率图以及速率图等特征图,为后续的特征点检测以及笔画识别做准备。特征点检测 特征点是指用户笔画中的拐点,这是基本笔画拟合以及组合图元分割的依据。然而,用户输入的手绘草图中存在着大量的噪声,如细微的抖动等。如何不受噪声的影响,准确地探测出用户有意而为的笔画拐点是特征点检测的难点所在。传统的特征点检测方法主要考虑了特征点处速度较小?曲率较大这两个特性,首先计算出所有采样点的平均速度和平均曲率,然后设定特定的阈值,通过阈值确定特征点。该方法的缺陷是其阈值的选取完全凭经验而得,并且在系统中固定不变,但是不同用户往往有着不同的绘图习惯,这就使得固定阈值在某些情况下过小或过大,从而影响了特征点检测的准确性。 本文将基于统计学习理论中结构风险最小化的支持向量机SVM分类技术引入到特征点检测环节,使用 SVM对采样点进行分类(分为特征点和非特征点),提出了具有用户自适应性的特征点检测方法,取得了较好的效果。具体方法在第三章将具体介绍。笔画识别 笔画识别是草图识别的核心,其本质是将预处理后的笔画轨迹按照特定的构成规则映射为相应的图形类别。用户的输入笔画首先用各类基本笔画尝试拟合,基本笔画包括直线、圆弧、曲线、椭圆、圆。对拟合成功的基本笔画,系统按照统一的排序算法进行排序,选择出最优识10 南京航空航天大学硕士学位论文 别结果。此外,用户在草图输入的时候往往一笔画输入一个组合笔画,所谓组合笔画是指由多个基本笔画组成的笔画,例如折线是由多条直线组成的。对于组合笔画,首先依据特征点检测结果进行笔画分割,再对分割后的各子笔画分别进行识别,最后组合各子笔画识别结果作为组合笔画的识别结果。图形规整 草图的识别只是使得草图映射为最贴近用户输入形状的图形,然而却可能并不是用户希望得到的图形。规整化的目的便是将识别后的图形调整到最规整的形状,使其与用户的输入意图更加吻合。图形规整化问题比较复杂,其过程分为图形内规整化与图形间规整化。图形内规整只依据图形自身的信息对其规整,如三角形有两条边近似等长,则将其规整为等腰三角形;而44图形间规整则利用了相邻图形的信息,如两个相邻矩形形状接近,则将它们调整到同等大小 。由于本文中草图的识别并非直接目的,只是为了理解用户的检索意图,我们将图形规整环节予以简化,使用类似于 Snap Rounding算法的方法简单处理图形规整的问题。用户反馈 手绘草图的最重要特征是“模糊性”,这种模糊性使得手绘草图具有强大的信息表达能力,利于创造性思想的快速表达、抽象思维的外化和自然交流,但同时,这又为手绘草图识别带来很多困难。这个困难最终可以归结为输入草图形态与人的视觉感受之间差异的“感觉鸿沟”及输入草图形态所表达的概念与人的理解之间差异的“语义鸿沟”这两个方面。已有的手绘草图识别方法基本上是基于几何特征的,即采用几何相似度来完成对草图的识别。一方面,几何特征是知识的载体,但它并不能完全表达知识,另一方面,在人类视觉思维规律问题解决之前,这种具有创造特征的模糊性是无法仅仅利用算法来消除的。 由于手绘草图这种固有的模糊性,一个输入笔画往往可以有多种解释方式,根据排序算法选择的识别结果往往并不是用户想要的识别结果。因此,在草图识别部分我们增加了用户反馈环节,对草图的识别结果进行反馈。通过用户的不断反馈,把握用户的习惯,完善识别机制。 2.2.2 图档多重存储结构基于手绘草图的工程图档检索是以用户输入的查询图档为条件,以内容特征为依据,检索出具有较高特征相似度的工程图档作为检索结果。这便首先需要使用一种统一的、有效的手段来存储和管理查询图档以及工程图档。并且存储文件需要具有可靠传输、读取简单,方便匹配等特点。XML(Extensible Markup Language,可扩展标志语言)是 W3C指定的一种通用语言规范,它具有强大的文档结构化功能,已逐步成为一种 Web环境中标准的数据交换格式。其最大特点是内容与表示分离,且具备良好的可扩展性和数据独立性。用户可以通过定义 XML DTD文件以及 Schema文件明确地表示数据模型中各个部分的意义,只要查看 XML文档就能确定该数据的意义,这就是 XML自我描述性。W3C DOM(Document Object Model,文档对象模型)11 基于手绘草图的工程图档检索技术 是对 XML 文档进行存取访问的接口,是一种提供随机访问机制的读写 API。本系统将 XML应用到图档信息管理领域,通过定义规则集把图档转换为 XML格式的表示信息,在词法和语法层次上保证信息表示的有效性和格式的一致性。DOM 接口可以方便地实现 XML文件的读写,二者的结合使得图档信息的表示和传输等操作能够得以很好的实现。 工程图档往往是由多图元组成的复杂图形。以往的系统往往采用基于基本图元的存储结构,也就是将图档分割成多边形、圆、椭圆等基本图元,以基本图元为单位存储、理解图档。然而,基本图元的存储结构往往是依赖于用户绘图的方式的,例如一个带对角线的矩形,也可理解为两个相邻接的三角形,对于基本图元存储结构,具体按哪种方式存储取决用户的绘制方式。所以,单独使用基于基本图元的存储结构势必会影响图档检索的结果。若用户对目标图档的理解不同于其绘制方式,此时用户根据自己的意图绘制查询图档进行检索则往往得不到所需图档。因此,在基本图元存储结构的基础上,本文增加了不依赖于用户绘图方式的组合图元存储结构,两者并存,实现图档的多重存储结构。组合图元的存储结构的构造方式在第四章将重点讲述,这里不再赘述。 2.2.3 图档检索 本系统中,图档的检索主要基于图档的内容特征,依据某类特征计算数据库图档与查询图档之间的相似度。一副图形可以有很多特征,如何选取特征使得检索效果最佳是关键问题。此外,鉴于工程图档检索的需要,所选取的特征还必须具有平移不变性、缩放不变性以及旋转不变性,且选取特征的相似程度应是可度量、易于计算的,相似度大小判断应与人的直觉相吻合。 现有图形匹配算法可以归于两类:基于图形特征矢量的方法与基于图形结构特征的方法,45同时还存在二者结合的方法 。基于图形特征矢量的方法是从图形中抽取一组图形的全局特征,并用统计方法建立这些特征的度量矩阵。常用的特征有紧密度、伸长度、自回溯系数及几何特征如面积、周长、力矩或傅立叶描述子等。抽取图形的全局特征不困难,但它不能精确描述图形的局部结构特征。基于图形结构特征的方法用图形的局部特征(如点、线段、弧)作为基元,通过一定的语法关系来描述图形,对图形模式进行编码,使用配对方法计算模式间的距离。 考虑到在基于手绘草图的工程图档检索中用户往往着重于图形的形状特征、拓扑结构以及图元间的空间关系,本文分别从这三类特征值出发,并结合三者计算图档之间总体相似度进行检索。形状特征 形状是物体的基本特征之一,是进行事物匹配最基础、最寻常的出发点。然而,对于本系统而言,单纯地提取整个图档的轮廓是没有什么意义的,如图 2.2所示,两图相差甚远,然而其外围轮廓却是相似的。但是,工程图档内各个图元的形状特征却是十分有意义的。由于本文12 南京航空航天大学硕士学位论文 中,除了基本图元存储结构还有组合图元存储结构,所以先确定图元的几何类型,再根据具体几何类型进行相应的形状相似度计算是不合适的。本文中,统一使用傅立叶形状描述子描述图元轮廓。 图 2.2 形状特征拓扑结构特征 草图在表述图档拓扑结构方面有着天生的优越性。用户以输入草图作为查询条件往往首先着眼于图档的拓扑结构。拓扑相似度着重考察图元之间构成的层次关系,也就是图档对应的拓扑树的相似度。 2对于在 R 空间中的简单区域,两图元之间可能有 8个不同的拓扑关系,分别为:disjoint,meet,equal,inside,contains,covers,covered by,overlap。本文对拓扑关系进行简化,将上述 8种拓扑关系分为包含、邻接以及其他三类,其中邻接包括了上述 8种拓扑关系中的 meet和重叠范围较小 overlap,inclusion包括了 inside, contains, covers, covered by 以及重叠范围较大的 overlap。如图 2.3,我们提取出工程图档的拓扑结构并构造相应的拓扑树,在该拓扑树中实线表示 inclusion关系,虚线表示 adjacent关系。 图 2.3 拓扑特征 由于我们的图档检索同样支持子图检索,也就是支持查询图档是工程图档的子图的情况(实际上子图检索更具有现实意义),所以在拓扑相似度计算的时候若查询图档的拓扑结构树与某工程图档的拓扑结构树的一部分相似,该工程图档仍然是满足要求的。空间关系特征 拓扑结构在一定程度上已经反映了图档中各子图的空间关系,然而其主要是反映了图档的层次关系,对于具有相似层次信息的矢量图之间仍需更多空间特征来区别。例如两个图元 A和13 基于手绘草图的工程图档检索技术 B,同样是连接关系,可以 A左 B右,亦可以 A上 B下, 这就需要进一步提取图元 A和 B之间的空间关系作为区别的依据。比较常用的空间关系有方位关系、子图连线坐标轴夹角等等。本文采用图元之间的坐标位移构造图元间的空间关系,具体内容将在第五章进一步阐述。 对各类特征相似度进行权值线性组合便可以得到图档间的总体相似度。最后将相似度较高的图档返回给用户,并根据用户对返回结果集的评价进行反馈来优化查询结果。图档检索相关反馈 用户在使用手绘