（计算机应用技术专业论文）作业图形拓扑关系识别技术的研究与开发.pdf

西南交通大学硕士研究生学位论文第1 页摘要作业是教学过程中的一个重要环节，现代教育技术的迅猛发展以及传统作业技术手段的落后使得作业环节技术手段亟待改革。远程作业系统在作业技术手段改革方面进行了有益的尝试，解决了数学表达式的自动识别和批改的难题。然而，对于理工科专业基础课程中大量出现的图形作业题目的批改而言，作业系统依然无能为力。针对这一现状，本论文对作业图形自动批改的相关问题进行了深入的研究。作业图形是学生解题过程中根据题意大致绘制的简略图形，具有很大的随意性和不规范性。论文分析归纳了作业图形识别技术不同于与其他工程制图类图形识别技术的特殊性：1 ) 识别对象的模糊性；2 ) 识别技术的学科独立性：3 ) 作业图形与数理逻辑的相关性。由于以上这些特殊性和作业图形本身的“无固定起点，无精确坐标，无统一比例”的“三无特点，使得作业图形的识别方法不同于精确图形的识别方法，只能是基于图形定性描述基础上的相似识别。本论文对作业图形的定性相似识别中的一些关键性问题进行了研究，取得的成果主要有：1 ) 建立了作业图形定性描述模型g q d 。本论文通过提取作业图形的图形类别、图形属性、相邻属性( 位置关系，拓扑关系) 实现了对作业图形的定性特征的完整和有效的描述。2 ) 设计了针对作业图形的消噪机制。作业图形中存在的噪声给后续的图形关系计算以及图形的综合识别带来干扰，消噪机制的存在能够有效的消除这种干扰保证了后续研究的顺利进行。3 ) 提出“泛化拓扑”概念，完成泛化拓扑关系的划分和计算。为了更准确和详细的描述作业图形间的拓扑关系，在九交模型理论的基础上，提出了“泛化拓扑 的概念，并针对作业图形中经常出现的拓扑关系进行了分类和算法实现。关键词：定性描述；特征分析；消噪；泛化拓扑；西南交通大学硕士研究生学位论文第1 i 页a b s t r a c tt h eh o m e w o r ki sa ni m p o r t a n tt e a c h i n gp r o c e s si ne d u c a t i o n t h er e f o r m a t i o no fh o m e w o r kt e c h n i q u ei sn e c e s s a r yd u et ot h el o we f f i c i e n c yo ft r a d i t i o n a lm e t h o d s t h ed i s t a n c eh o m e w o r ks y s t e mi sag o o dt r i a lt oi m p r o v eh o m e w o r kt e c h n i q u e ，w h i c hc a ns o l v et h ep r o b l e m so fa u t o m a t i cr e c o g n i t i o na n dc o r r e c t i o no fm a t h e m a t i c a le x p r e s s i o n h o w e v e r , t h ed i s t a n c eh o m e w o r ks y s t e mi ss t i l lu n a b l et oc o r r e c tt h es c i e n c ea n de n g i n e e r i n gc o u r s e s h o m e w o r kw h i c hc o n t a i n sg r a p h i c s t h i st h e s i sc o n c e n t r a t e so nt h ea u t o m a t i cr e c o g n i t i o na n dc o r r e c t i o no fg r a p h i c si nh o m e w o r k ”t h eg r a p h i c si nh o m e w o r ka r es i m p l ea n di n f o r m a l ，w h i c ha l ed r a w nb ys t u d e n t si nt h ep r o c e s so fd o i n gt h e i rh o m e w o r k t h i st h e s i sa n a l y s e sa n ds u m m a r i z e st h ep a r t i c u l a r i t i e so ft h et e c h n i q u eo fg r a p h i c s r e c o g n i t i o n ：1 ) t h eg r a p h i c si nh o m e w o r ka r eb l u r r y ；2 ) t h et e c h n i q u eo fg r a p h i c s r e c o g n i t i o ni si n d e p e n d e n to ft h es p e c i f i cd i s c i p l i n e sk n o w l e d g e ；3 ) t h eg r a p h i c si nh o m e w o r ka r er e l a t i v et om a t h e m a t i c a ll o g i c b e c a u s eo ft h e s ep a r t i c u l a r i t i e sa b o v ea n dt h eg r a p h i c s s p e c i a l t i e s , n of i x e ds t a r t i n gp o i n t , n op r e c i s ec o o r d i n a t e s , a n dn ou n i f i e dp r o p o r t i o n ，t h er e c o g n i t i o no fh o m e w o r k sg r a p h i c sm u s tu s et h es i m i l a rr e c o g n i t i o nw h i c hb a s eo nt h eq u a l i t a t i v ed e s c r i p t i o no ft h eg r a p h i c s t h eq u a l i t a t i v es i m i l a rr e c o g n i t i o no fh o m e w o r k sg r a p h i c si ss t u d i e di nt h i sp a p e ra n dt h er e s u l t sa r ea sf o l l o w i n g ：1 ) t h ep a p e rp r o p o s e st h eg o dm o d e l 弱t h em o d e lo ft h eh o m e w o r kg r a p h i c s q u a l i t a t i v ed e s c r i p t i o n t h eg q dm o d e ld e s c r i b e st h eq u a l i t a t i v es p e c i a l t i e sc o m p l e t e l ya n de f f e c t i v e l yb ye x t r a c t i n gg r a p h i c s t y p e ，a t t r i b u t e s ，p o s i t i o nr e l a t i o n sa n dt o p o l o g i c a lr e l a t i o n s 2 ) t h ep a p e re s t a b l i s h e sak i n do fd e n o i s i n gm e c h a n i s mt oe l i m i n a t en o i s ei nt h eh o m e w o r kg r a p h i c s t h i sn o i s ee x i s t i n gi nt h eg r a p h i c sw i l ld i s t u r bt h el a t e rr e s e a r c h e s ，s u c ha st h et o p o l o g yc a l c u l a t i n ga n dc o m p r e h e n s i v er e c o g n i t i o n s ot h ed e n o i s i n gm e c h a n i s mc a ne f f e c t i v e l ye l i m i n a t et h en o i s ei n t e r f e r e n c e ，a n de n s u r et h ef o l l o w i n gs t u d y 3 ) t h ep a p e rp r e s e n t st h ec o n c e p to f ”g e n e r a l i z a t i o nt o p o l o g i c a lr e l a t i o n s ”a n dc o m p l e t et h ec l a s s i f i c a t i o na n dc a l c u l a t i o no fh o m e w o r kg r a p h i c s t o p o l o g i c a l西南交通大学硕士研究生学位论文第l i i 页r e l a t i o n s t h ec o n c e p ti sp r e s e n t e di no r d e rt od e s c r i b et h et o p o l o g i c a lr e l a t i o n so ft h eh o m e w o r kg r a p h i c sm o r ea c c u r a t ea n dd e t a i l e d k e yw o r d s ：q u a l i t a t i v ed e s c r i p t i o n ；f e a t u r ea n a l y s i s ；d e n o i s i n g ；g e n e r a l i z a t i o nt o p o l o g y ；西南交通大学曲南父逋大罕学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。本学位论文属于1 保密口，在年解密后适用本授权书；2 不保密母靠用本授权书。( 请在以上方框内打“4 一)学位论文作者签名：鳓日期：训j 坪，u鱼一7轹，咿猁舯师2老：导期指日西南交通大学学位论文创新性声明本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。本学位论文的主要创新点如下：l 、建立了作业图形定性描述模型g q d 。本论文通过提取作业图形的图形类别，。图形属性，相邻属性( 位置关系，拓扑关系) 实现了对作业图形的定性特征的完整和有效的描述。解决了图形作业几何特征定性描述的难题。2 、设计了针对作业图形的消噪机制。作业图形中存在的噪声给后续的作业图形关系计算以及图形综合识别带来干扰，消噪机制的建立能够有效的消除这种干扰保证了后续研究的顺利进行。3 、提出“泛化拓扑一概念，完成泛化拓扑关系的划分和计算。为了更准确的描述作业图形问的拓扑关系，在九交模型理论的基础上，提出了“泛化拓扑一的概念，并针对作业图形中经常出现的拓扑关系进行了分类和算法实现。最后通过对实际数据的测试达到了较好的识别效果。西南交通大学硕士研究生学位论文第1 页1 1 研究背景和意义第1 章绪论1 1 1 问题的提出信息技术的在现代教育技术中的广泛应用使得教育手段改革不断的向数据化和网络化方向纵深发展，多媒体技术在课堂教学中的普遍应用，使得教学效果与效率大大提高。然而作业作为教学过程中的一个重要环节n 3 ，并没有随着日益深入的信息化改革发生相应变化，仍然停留在“刀耕火种”的手工批改阶段，作业环节的教学质量和工作效率受到了很大影响。针对这一现状，远程作业系统在作业技术手段改革方面进行了有益的尝试隆一，它解决了数学表达式的自动识别和主观性题目自动批改的难题旧，然而在大量理工科专业的基础课程中，作业内容涉及到大量的图形元素，例如大学物理、电子学和基础力学等课程。对于这些课程来讲，图形是一个题目正确解答的重要组成部分，学生解答是否正确不仅仅取决于数学表达式推演过程和数值计算阳1 ，还取决于图形的绘制是否正确，甚至在有的情况下一个题目的解答就是图形( 例如材料力学中的剪力图、弯矩图) 。然而当前计算机对作业图形识别技术的研究相当有限。如果学生绘制的作业图不能得到自动批改与信息反馈，会直接影响到计算机作业的效果，更会影响教学的效果。远程作业系统迫切需要一个具有一定智能的作业图形批改模块，来帮助教师完成图形作业的批改任务，让先进计算机技术真正彻底地改变传统作业技术手段。1 1 2 研究现状图形作业题目出现最多的是理工科的画法几何和机械制图学科，这几类学科中由于大量的使用了工程制图类软件如a u t o c a d 等，因此该领域对图形作业的研究大都是基于a u t o c a d 和a u t o c a d 二次开发工具o b j e c t a r x 的。在此类图形作业的自动识别方面，国内外已经有不少人进行了相当的研究。工程类作业图形的自动识别的研究应用目前主要分为两类。类是通过图形作业的形状识别，来达到对零部件的归类方面的应用。文献 7 通过对图形特征分析和提取，实现了对图形形状的识别，以此来实现对模具类型的识别。文献 8 在零件几何特征分类的基础上，根据工程制图的。西南交通大学硕士研究生学位论文第2 页特点，提出了零件视图信息矩阵表示模型，和基于d x f 文件格式的几何特征识别方法。另一类是对图形作业的批改系统，通过对作业中制图关键信息的提取和判断来达到对工程制图的自动批改。文献 9 ，1 0 介绍了基于网络的a u t o c a d 环境下的制图作业评判系统，但只是简单的对图形绘制中的漏线、错线、线形属性等错误进行批改。文献 1 l ，1 2 中何培英与其合作者针对凯图c a d t o o l 2 0 0 0 开发了基于w e b的工程制图作业批改系统，在算法上采用图形直接比较法，即以标准答案为模板去核对学生的作图情况，从而判断学生作业中的正误。这套批改系统具有作业批改、作业评分、成绩统计、批改后的作业保存等比较完整的功能，但也是针对简单的c a d 图形。文献 1 3 中吴学文针对一些简单的制图作业设计了自己的批改系统。他提出了两种批改方案：一种是比较学生作业图元数据与答案图元数据；一种是比较学生作业图形与答案图形块。这两种方法适合检验补画图线、补视图等答案唯一的这类习题。前一种方法通过线形属性检测判断学生作业中的作图是否精确，检验学生的精确绘图能力。后一种方法在使用时仍需要人工干预来检验作业情况。显然，这两种方法都有比较大的缺陷。文献 1 4 ，1 6 中许占民和李蓉以a u t o c a d 2 0 0 0 为开发对象，使用图形直接比较法对机械制图中的轴套类作业进行了研究开发。文献 1 8 中袁宁同样对轴套类作业进行了基于a u t o c a d 的开发，但其采用了扫描线方法，并且相应的提出了一些重要的思路和算法。国外在作业图形识别领域的研究和国内的状况大致相同，文献 1 9 2 1 均来自国外文献，其中对作业图形的研究都是针对工程制图c a d 类甚至模具制造类的精确图形的识别和研究。总结以上研究可知，国内外对于图形识别的研究大致在同一水平，研究和应用最多的均是精确尺寸的图形( 也称定量图形) ，这类图形最大的特点是尺寸比较精确，识别时一般是简单的对尺寸进行扫描比较识别。课程作业中的作业图形，类似于w o r d 中的示意图形( 也称定性图形，描述见后面1 2 节) ，它们的最大特点就是尺寸随意，手写汉字也有尺寸随意的特点，但对它的识别研究属于图像模式识别领域，文献 2 2 ，2 3 介绍了汉字识别过程中的一些关键问题，汉字识别对字笔画和笔顺要求严格，使用的研究方法是统计和结构识别法，并且要借助字库模板，而作业图形对绘图顺序没西南交通大学硕士研究生学位论文第3 页有要求，并且识别过程中根本没有固定的模板可言，因此对手写汉字识别的研究方法不适合用于对作业图形的识别。因此，图形作业的识别技术还没有见到相对成熟的研究，对作业图形识别算法的研究具有重要的意义。1 1 3 研究意义就计算机对作业图形识别技术的研究具有重大意义。首先，作业图形的识别属于定性图形的识别，而国内外对于定性图形识别研究基本上还属于空白领域，因此，对作业图形定性识别的研究实际上也是对定性图形识别领域的积极探索，具有重要的研究意义。再次，图形识别模块的成功实现，使网上作业系统从原有的符号识别功能逐步扩展为集符号与图形识别于一体的智能识别系统。再者，对作业图形识别技术的研究有助于作业环节手段改革的扩大与深入，使得更多作业题目和课程能够通过计算机和网络技术进行改造，从而使教学工作的总体质量、效率和效益得到进一步扩大提高。1 2 作业图形的基本特征定义l 图形空间g ：远程作业系统中给学生和教师提供的图形绘制空间，具体而言就是作业系统的答题窗口。学生和老师分别属于不同的图形空间g s和g ，( “远程作业系统 见后面章节详细介绍) 。远程作业系统自身携带的绘图工具h 1 可以绘制各种图形，能够满足常用的各种作业题目绘图的需要，本论文的研究工作主要是对远程作业系统绘图工具绘制的图形进行的识别和批改。作业图形是学生解题过程中根据题意大致绘制的简略图形，具有很大的随意性和不规范性。学生在计算机上绘制的作业图形也具有这样的特点：1 ) 无固定起点，学生可以在图形空间内选择任意一个位置开始绘图，绘制的图形也没有固定的起始位置。2 ) 无精确尺寸，作业中的图形对实际物体和概念的反映往往是简略的和定性的，因此作业图形一般没有精确的尺寸，同时图形之间的相对位置也不确定。3 ) 无统一比例，学生可以随意指定每一个图形的大小比例，图形间更没有统一的比例可言，只要求能够定性反映图形元素间关系。本论文就是对具有“三无”特点的作业图形进行的识别研究。西南交通大学硕士研究生学位论文第4 页1 3 本论文主要工作本论文针对作业图形的识别做了大量相关的研究，主要工作包括以下几个方面：1 ) 分析研究了作业图形的“三无 特点和作业图形识别技术的特殊性。2 ) 建立了作业图形定性描述模型g q d 。论文通过提取作业图形的图形类别、图形属性、相邻属性( 包括位置关系，拓扑关系) ，实现了对作业图形的定性特征的完整和有效的描述。解决了图形作业定性描述的难题。3 ) 设计了针对作业图形的消噪机制。作业图形中存在的噪声给后续的图形间拓扑关系计算以及图形的综合识别带来干扰，消噪机制的存在有效消除了这种干扰，保证了后续研究的顺利进行。4 ) 提出“泛化拓扑 概念，完成图形拓扑关系的定义和分类。为了更准确和详细的描述作业图形问的拓扑关系，在九交模型理论的基础上，提出了“泛化拓扑 的概念，并针对作业图形中经常出现的拓扑关系进行了定义和分类。5 ) 用d e l p h i 语言编程实现了数据剥离、消噪和封装模块，完成了图形数据的对象化创建；在拓扑关系分类的基础上完成了常用作业图形闾拓扑关系的计算。1 4 后继章节内容简介本论文共5 章。第章：绪论。介绍了作业图形自动批改技术的研究背景和意义。介绍了作业图形的基本特征和本论文的主要工作。第二章：系统介绍。介绍了远程作业系统的系统模块构成和作业图形数据存储结构，为后继论文工作的展开提供了数据来源。第三章：作业图形特征描述和识别模型。对作业图形进行识别，必须对图形的定性特征进行完整和有效的描述，论文通过提取图形类别、属性特征和相邻特征( 包括位置关系，拓扑关系) ，建立了作业图形定性特征描述模型g q d 。在此基础上，提出并阐述了通过计算作业图形间定性关系相似度来达到识别目的的方法模型q s i ，为定性图形的识别提供了一种解决方案。西南交通大学硕士研究生学位论文第5 页第四章：图形数据对象的创建。通过g d c e n t e r 处理模块的三个子模块完成了从数据库端字符串数据到相应图形类对象之间的转换，其中在d 2 g d e n o i s e 模块中完成了图形数据的消噪处理，为后继识别过程的各种操作提供了数据支持。第五章：拓扑关系分类与计算。对作业图形间的拓扑关系进行了深入的研究，在拓扑关系定性描述模型一九交模型的基础提出了“泛化拓扑”的概念，建立了常用图形间拓扑关系分类，并编程实现了作业图形中常用图形间的拓扑关系的计算。最后介绍了程序计算中的使用的容差控制。第六章：拓扑关系计算应用实例。通过对材料力学中的作业图形实例的拓扑关系计算，对本论文的拓扑关系计算识别效果进行了测试，试验结果表明达到了较好的识别效果。“最后总结了本论文，并且提出后继研究需要改进的方面，给出了该领域的展望。西南交通大学硕士研究生学位论文第6 页第2 章作业系统简介与数据存储格式2 1 远程作业系统介绍智能型远程作业系统是一套基于互联网的智能、开放式、跨学科和多层次的远程作业系统，该系统能够实现题目的设计、作业布置、学生答题、自动批阅和评讲总结等作业环节的全程微机化，系统能够自动识别和批阅学生包括选择题、判断题、填空题、表格题等题型在内的解答过程。并且具有自动“透视”功能和动态构筑学生学习“病例”的功能h 1 。2 1 1 远程作业系统的模块划分系统按功能来分，可以划分为数据库服务器、应用服务器、管理系统、学生系统、教师系统和工具系统六个部分。如图2 一l 所示图2 - 1 远程作业系统功能结构工具系统主要用于教师设计题目，包括题文的设计以及正确答案的设置等。学生系统主要用于学生做作业，自动批改作业，并且供学生查看批改结果和作业评讲。教师系统主要用于教师布置作业，查看学生答题的情况，管理作业等。管理系统主要用于对教学资源( 如题目、学生答案等) 和系统运行状态进行管理维护等。在远程作业系统的六个功能模块h 叼中，与图形识别相关的只有教师设定参考标准答案的工具系统以及学生绘图答题的学生系统。下面将分别介绍这西南交通大学硕士研究生学位论文第7 页两个功能模块。2 1 2 远程作业工具系统简介“工具系统”h 1 是教师系统独立出来的一个子模块。利用工具系统，任课教师对已有的题目进行增、删或改等编辑操作。工具系统根据需要可以单独发布，这也是远程作业系统全开放式设计架构的一个重要体现。该系统允许对文字、公式和图形进行一体化的编辑，用户不再需要依靠其它任何工具软件即可完成完整的作业题目的设计和制作工作。工具系统要求教师在设计题目时不但要根据不同的题型来制作题目，还需要设置此题目的参考标准答案，后续的文字、公式和图形识别就是以工具系统设置的参考标准答案为基准来进行识别的。工具系统着重对作业题目的设计，其功能侧重于图文混排，文字公式一体化，公式与图形结合等。教师通过工具系统进行题目编辑并保存提交以后，工具系统对题目中所有数据加以处理，通过远程通讯模块，存储到s q ls e r v e r数据库中。以后不管是公式识别还是图形识别都是依据读取工具系统设置的参考标准答案，对学生的答题给予识别。所以工具系统的对题目的编排，参考标准答案设置直接影响后续识别的效果。工具系统的界面如图2 2 所示，图中已经标定了图形绘制工具条，图形线条属性工具条，题目设计窗口以及答案设置窗口。e 窭2 = 要露翟磴蜀曩署舞蠹窝露器墨：舞露要裹芑墓譬2 喧墓譬妻彗：缬善j 、要j i 一1 了一一一一二! j j l文竹f f l 矗f 日k 强r 们箍 m西五，负冀盟l 丑i 毋i 口1照量魏l 旦三! 銎! ! 奠筻苎! 礁塑圭壁垒篓攫舅黧! 至壁玉点曼一曼丝l 二：二：二图2 - 2 工具系统窗口界面西南交通大学硕士研究生学位论文第8 页教师通过笛形绘制工具以及图形线条属性设置工具分别在题目设计窗口和答案设置窗1 3 绘制作业图形。其中在题目设计窗1 3 的图形属于题目主题带有的图形，答案设置窗口的图形属于答案图形。图形识别的主要参考标准答案图数据就是答案窗口绘制的图形。2 1 3 远程作业学生系统简介学生系统中学生可以选课，完成作业，另外还可以利用本系统的核心智能识别程序实现作业的自动批阅，并且根据学生的错误给予错误评价( 即“病例”) ，最后给予评分。“答题模块”是学生解答作业题目标模块，在“答题模块”中学生可在“学生答题窗口”基本无约束地输入题目的解答过程，包括文字、图形和公式等内容。若作业没有全部完成则可在退出“答题模块”时不要求系统批改作业，即一次作业可以分成几次做完，做完后由系统一次性批改；相反，一次作业也可让系统分做多次批改。蜀趸互璺髓静蕊岛霉赛露霹墨曩黟露露嚣蕊露蜀盟黑慧芝嚣譬夏互乏芝? ：j ? 。= 型! i冀- 姻i 啦疆入口置c 匐绩髑a 话目】凹f 蛊。t t - 1i - 2 、jo05口i - - j 1 1 ：阳墨i i 习学生解答窗口 ；l 到：l曩崔橱“打字翘量咖立f i 压罩0 z 0 。c 曙号：p z l 王，f 墨- 墨摩：4 0图2 3 学生系统答题窗口若学生在退出时( 点击“退出批改按钮”) 要求系统对作业进行批改，则系统的“批阅模块”h 1 即对已完成的作业部分进行详细的批改，根据作业题量和解答复杂程度的不同，批改时问在数秒或几分钟之间。批改的内容不仅包括公式文字部分，而且包括作业图形部分。西南交通大学硕士研究生学位论文第9 页学生系统答题系统界面如上图2 3 所示。“评讲与总结”模块供学生了解已经完成或部分完成且已由系统批改完毕的作业情况，包括每个题目的评判情况和相应的正确解答。这个模块主要显示学生作业批改完毕之后的错误情况，也就是学生作业图形的识别的结果，与图形作业识别关系不大，不是本文论述的重点。2 2 远程作业系统数据存储结构前面已经介绍，工具系统用于题目的设计和答案的编制，其中编制题目答案时可以设置多种参考正确答案h 1 ( 也就是该题目的多种解法) 。设置完成后工具系统通过通讯模块将所有题目数据均保存在s q l s e r v e r 数据库中j g数据库的t k 数据表中，参考正确答案保存在z q d a 字段中。学生答题后所有数据保存在j d 数据表中，数据存储格式与工具系统一致，本节对存储在z q d a字段中的参考正确答案的数据格式作具体分析。z q d a 字段是一个文本字段，在s q ls e r v e r 数据库中设为“v a r c h a r ”数据结构，数据长度为5 0 0 0 。也就是说存储z q d a 字段中的参考正确答案数据全部以文本字段格式存放的。z q d a 字段中存有丰富的作业信息，除了各种答案数据，还有很多数据控制信息。我们使用时需要逐一剥离，找到我们识别需要的数据。z q d a 字段数据格式如下：正确答案席l l 正确答案翻1 1 正确答案脯l l# 1 1 分隔开的是不同的正确答案，就是我们所说的一题多解的多种解答信息，正确解答，的数据结构就是工具系统中编辑控件h 3 的输出格式。正确答案j 格式如下：t le n g t h ，g l e n g t h ，n _ g r a p h ， t 文本信息t l g 图形信息g 。格式各部分含义如下：t l e n g t h ：文本部分字符串长度( t 和t 不计算在内) ：g l e n g t h ：图形部分字符串长度( g 和g ) 不计算在内) ；n _ g r a p h ：图形元素的个数； t 文本信息t ) ：题目中的文本信息，即在系统中未采用标注图形“1 表示而是直接输入的文字，其中包括一些控制字符，用于分割不同行的文本内容；西南交通大学硕士研究生学位论文第10 页 g 图形信息g ：题目中的图形元素数据( 已分解成字符串形式) ，其中包括一些用于分割不同图形信息字符串的控制字符。为了节省存储空间，图形信息全部采用带有固定格式的文本字符串来保存，格式如下：图形元素席1 3 # 1 0 图形元素z ： 1 3 # l o 图形元素麒1 3 # 1 0 。2 3 远程作业系统图形数据存储结构为了说明图形元素的在数据库中的存放格式，有必要先介绍一下系统中的图形对象类型。2 3 1 图形对象类型说明图形对象类型是作业系统中对作业图形种类的定义，如矩形、直线等，这些均在远程作业系统中给予明确的定义嘲：直线：以常量c t l i n e 表示，c t l i n e = l ，其中直线又分为5 种类型( 为l i n e t y p e ) ，5 种l i n e t y p e 分别如下表示：1 ) 简单直线：i t l i n e ，定义i t l i n e = l ；2 ) 终点带箭头：i t a r r o w ，定义l t a r r o w = 2 ；3 ) 起点带箭头：l t 从r r o w ，定义l t a a r r o w = 3 ；4 ) 双箭头：i t d a r r o w ，定义i t d a r r o w = 4 ；5 ) 尺寸线：l t s i z e a r r o w ，定义i t s i z e a r r o f 5 ：矩形：以常量c t r e c t a n g l e 表示，定义c t r e c t a n g l e = 4 ；圆形：以常量c t c i r c l e 表示，定义c t c i r c l e = 5 ；椭圆：以常量c t e l l i p s e 表示，定义c t e l l i p s e = 6 ；圆弧：以常量c t a r c 表示，定义c t a r c = 7 ；多义线：以常量c t p o l y l i n e 表示，定义c t p o l y l i n e = 8 ；注释：以常量c t a n n o t a t i o n 表示，定义c t a n n o t a t i o n = 9 ；公式：以常量c t e q u a t i o n 表示，定义c t e q u a t i o n = 1 0 ；抛物线：以常量c t t a r c 表示，定义c t t a r c = ll ：2 3 2 图形对象数据结构系统中原有图形对象数据结构如下：t f e a t u r e = r e c o r d图形对象定义i n d e x ：w o r d ：图形对象的索引值西南交通大学硕士研究生学位论文第11 页s t y l e ：t p e n s t y l e ：画笔类型c o l o r ：t c o l o r ：线条颜色p e n w i d t h ：i n t e g e r ；线条宽度g r o u p e d ：b o o l e a n ：图形对象是否已经分组s e l e c t e d ：b o o l e a n ：图形对象是否已经被选中c a s ef t r t y p e ：t f e a t u r e t y p eo ff t l i n e ：直线的定义( x ll ，y l l ，x 1 2 ，y 1 2 ：i n t e g e r ：l i n e t y p e ：i n t e g e r ) ：起始点和终止点坐标值，l i n e t y p e 为直线类型f t r e c t a n g l e ，f t c i r c l e ，f t e l l i p s e ：矩形，圆，椭圆的定义( x l ，y 1 ，x 2 ，y 2 ：i n t e g e r ；矩形以及圆和椭圆外界矩形的左上角和右下角坐标b r u s h c o l o r ：t c o l o r ；画刷颜色值b r u s h s t y l e ：t b r u s h s t y l e ：) ：画刷类型值f t a r c ：圆弧的定义( x a l ，y a l ，x a 2 ，y a 2 ，x a 3 ，y a 3 ，x a 4 ，y a 4 ：i n t e g e r ；) ：x a l ，y a l ，x a 2 ，y a 2 为圆弧所在椭圆的外接矩形左上角和右下角坐标，x a 3 ，y a 3 ，x a 4 ，y a 4 的说明见下图2 - 4 所示( x a l ，图2 - 4 圆弧数据格式说明f t p o l y l i n e ：多义线的定义( p o i n t c o u n t ：i n t e g e r ；多义线的点的总数p o i n t s ：a r r a y 1 1 6 o ft p o i n t ：) ；1 1 多义线上的点坐标集合f t t a r c ：抛物线的定义西南交通大学硕士研究生学位论文第12 页( p o i n t c o u n t l ：i n t e g e r ；p o i n t s ：a r r a y 1 3 o ft p o i n t ：) ：抛物线有起点、终点、中间点三个关键点f t a n n o t a t i o n ：标注文本定义( f o n t s i z e ：i n t e g e r ：标注文本字体大小f o n t c o l o r ：t c 0 1 0 r ：标注文本字体颜色b o l d ：b o o l e a n ：标注文本字体是否粗体i t a li c ：b o o l e a n ；标注文本字体是否斜体r e c t ：t r e c t ：标注文本所占的矩形框t e x t ：s t r i n g 1 6 ：) ：标注文本内容f t e q u a ti o n ：公式( p e q t ：p e q u a t i o n ) ：指向公式对象的指针e n d ：2 3 3 图形元素内容数据库存储格式从上节可知，不同图形对象的文本格式( “图形元素i # 1 3 # 1 0 ”中的图形元素字段) 格式如下描述：直线：对象类型值( 直线为1 ) ，索引值，画笔模式，对象颜色，画笔宽度，直线类型，起点x ，起点y ，终点x ，终点y 。矩形：对象类型值( 矩形为4 ) ，索引值，画笔模式，对象颜色，画笔宽度，画刷颜色，画刷类型，左上角x ，左上角y ，右下角x ，右下角y 圆形：对象类型值( 圆为5 ) ，索引值，画笔模式，对象颜色，画笔宽度，画刷颜色，画刷类型，外接矩形左上角x ，外接矩形左上角y ，外接矩形右下角x ，外接矩形右下角y 。椭圆：对象类型值( 椭圆为6 ) ，索引值，画笔模式，对象颜色，画笔宽度，画刷颜色，画刷类型，外接矩形左上角x ，外接矩形左上角y ，外接矩形右下角x ，外接矩形右下角y 。圆弧：对象类型值( 圆弧为7 ) ，索引值，画笔模式，对象颜色，画笔宽度，x a l ，y a l ，x a 2 ，y a 2 ，x a 3 ，y a 3 ，x a 4 ，y a 4 。标注：对象类型值( 标注9 ) ，索引值，画笔模式，对象颜色，画笔宽度，字体尺寸，字体颜色，是否粗体，是否斜体，左上角x ，左上角y ，右下角x ，右下角y ，文本内容。公式：对象类型值( 公式为1 0 ) ，索引值，画笔模式，对象颜色，画笔宽度，公式左上角x ，左上角y ，右下角x ，右下角y ，公式内容( 由公式编辑西南交通大学硕士研究生学位论文第13 页器生成，以# 1 2 分隔符结束) 。多义线：对象类型值( 多义线为8 ) ，索引值，画笔模式，对象颜色，画笔宽度，点数，点l x ，点l y ，点n x ，点n y 。抛物线：对象类型值( 抛物线为1 1 ) ，索引值，画笔模式，对象颜色，画笔宽度，点数，点l x ，点l y ，点2 x ，点2 y ，点3 x ，点3 y 。2 4 本章小结本章主要介绍在远程作业系统中与图形识别相关的数据格式，首先介绍设定参考标准答案图的工具系统以及学生作业答题的答题窗口，然后讲述图形数据的存储格式，最后剖析这些图形数据的具体的存放格式，为后面章节图形数据处理和算法的设计奠定了基础。西南交通大学硕士研究生学位论文第14 页第3 章作业图形特征描述与识别模型3 1 引言人工批改图形作业涉及到一系列极其复杂的思维工程。从教师对作业图形的批改过程来看，这往往是教师将学生的作业图形与存放在在头脑中的根据题意描述而形成的正确作业图形之问不断进行比较、验证的过程。由此来看，作业图形的识别是一种比较识别，由计算机模拟人工的批改也应该是一种比较识别的过程。如果用计算机来模拟人工批改，那么就必须让计算机能够提取正确作业图形的图形特征和学生解答图形的图形特征，然后对两者进行比较，由此可见，对作业图形的图形特征的提取对作业图形的识别至关重要。文献 9 1 2 介绍了工程制图类图形作业的几种识别技术，但大部分工程制图类图形识别技术都是在精确尺寸和统一比例基础上进行的图形识别，通过识别对象的关键点尺寸，加上拓扑和尺寸约束的判别来最终达到对图形对象的识别目的，比如对a u t o c a d 中的模具形状进行识别和分类等，它们所提取图形特征都是基于精确图形的量化特征。作业图形本身所具有的“三无特点使得对作业图形的识别不能使用精确图形类的识别方法来进行识别。要定义和提取作业图形识别过程中需要的图形特征，首先就要分析作业图形识别技术不同于工程制图类图形识别技术的特点。3 2 作业图形识别技术的特点本文将图形空间g 。或g 。中由老师或学生绘制的所有图素的集合称为图形域g g ，教师和学生的图形域分别用g g ，和g g 。来表示。3 2 1 作业图形识别对象的模糊性作业图形是学生在解题过程中根据题意大致绘制的简略图形，具有很大的随意性和不规范性。学生在计算机上绘制的作业图形也具有这样的特点，本文在绪论中将其归纳为“无固定起点，无精确尺寸，无统一比例”的“三无 特点。这些特点就使得作业图形的识别对象只能是模糊的大概的图形，而不同于工程制图类的精确图形，这一特点我们称之为识别对象的模糊性。西南交通大学硕士研究生学位论文第15 页3 2 2 作业图形识别技术的学科独立性作业图形反映的物理对象与课程知识有关，例如同样一个矩形在电学中可能代表一个电阻，而在力学中可能代表一个受力的杆件，如图3 一l 所示；另一方面，同一种图形对象在同一门课程之中，特别是同一个作业题目当中所代表的物理对象在绝大多数情况下是唯一的。因此作业图形的识别技术就必须要回避作业图形所反映的物理对象和课程知识，在此基础上建立起一套独立于课程知识之外的识别方法。b仁二= = = a ) 电路图“b ) 受力图图3 - i 相同图形反映不同课程知识3 2 3 作业图形与数理逻辑的相关性物理、力学和电学等课程都用到了矢量概念和矢量的运算，题目的正确解答和数理逻辑的推演与矢量的方向有关。如图3 - 2 所示，在力学当中对于未知力的方向是可以任意假设的，如果假设压如图3 - 2a ) 所示，那么关于结点a 正确的平衡方程应该是：一e + c o s 0 - 0( 3 一1 )如果假设尼如图3 - 2b ) 所示，那么关于结点a 正确的平衡方程应该是：一e e c o s 0 - 0( 3 - 2 )jf 1fa ) 受力图画法lb ) 受力图画法2图3 - 2 图形与数理逻辑的耦合上述两种做法都是正确的，但是如果将上述的推演公式与图形中所假设的力的方向对调，那么结果就是错误的。由此可见，在有些情况下作业图形还与公式推演具有一定的耦合作用，作业图形的识别不能单独进行，还要考西南交通大学硕士研究生学位论文第16 页虑与公式推演的相互关系。3 3 图形特征的定性描述作业图形本身的“三无特点和作业图形识别技术的特殊性( 识别对象模糊性，学科独立性，数理逻辑相关性) ，使得对作业图形的识别不可能通过计算图形元素的坐标、比例和尺寸，确定其实际大小或尺寸来进行定量识别，只能在图形域之间进行定性的相似的识别( 简称定性相似) ，这就需要建立一种合适的模型来充分描述图形域中作业图形的定性图形特征。定性描述模型所能反映的作业图形的定性特征是图形识别的基础，因此一个合适的描述方法至关重要，文献 2 7 对二维参数化应注意的问题进行了研究，文献 2 8 从图形特征点入手，提出了一种新的图形表示法，及图形对象特征点描述法，但不完全适用于描述作业图形的图形特征。作业图形属于定性图形，这一特点使它丢失了精确图形所有的一些信息，比如尺寸约束和比例约束之类的量化信息，但它作为一个图形，本身的属性信息，在图形空间中的坐标点信息，与其他图形之间的邻接关系等信息还在。因此要在有限的定性条件约束下达到尽可能精确的识别效果，描述模型必须要尽可能多的反映图形的定性特征。在此思想指导下，本论文建立了如下的作业图形特征描述模型：图形特征= l i ：属性特征= i j ；邻接特征= l 。属性特征是图形本身所具有的特点。此模型中列举的几点，如关键点特征，方向特征等大部分图形都有的特征，具体到不同的图形种类，其属性特征还应该包含该种类所特有的特征。邻接特征是图素个体与同一个图形域中的其他图素之间的相互关系，包括位置关系和拓扑关系。设一个图形域g g 中有k 个图形元素反以下简称图素) ，则任意图素e t的图形特征的数学模型表示为e s it l i ( 0 f s k )at t r 一 l l c o l o r ( 3 3 )a d j i o n 一 i 本论文称式子( 3 - 3 ) 为作业图形的定性描述g o d ( g r a p hq u a l i t a t i v e西南交通大学硕士研究生学位论文第17 页d e s c r i p t i o n ) 模型。模型中各部分的具体含义介绍如下：1 ) 图形类别g t y p e ：g ? y p e e 耋线，矩形，圆，椭圆，圆弧，抛物线，注释，多义线等) 。2 ) 关键点特征k e y d o t ：指历上的关键点集合7 r 喝一，吲，( 1 7 为整数) 。 = 阢彬，( j 翻即螈为关键点坐标。不同图形有不同的关键点集合，常见图形关键点集合如下表所示。表3 - 1 常见图形关键特征点集合定义图形种类常见关键点特征直线起点，终点圆圆心，圆上一点矩形对角定点椭圆椭圆外切