（计算机应用技术专业论文）远程作业系统表格题自动批改技术的研究与开发.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 作业是一个重要的教学环节。作业的批改对学生的学习起着指导、鼓励和 鞭策作用，对教师起着检查课堂教学效果、促进教学的作用。利用计算机对学 生作业进行自动识别和批改，较手工批改作业能大大提高作业批改的速度，提 高作业批改质量，并且减轻教师的工作量。目前已有很多作业批改软件，它们 大多数只能对选择题、判断题等题型进行识别和批改，目前还没有软件能够对 表格题进行t l 动识别和批改。然而在许多课程中，它们包含的一些知识结构需 要以表格的形式来呈现和描述，例如工程测量、会计学原理、部分理工科课程 的实验报告等。 表格题的答案是批改表格题的重要元素，它由答案内容和内容的位置信息 组成。本文研究了提取答案内容、确定答案内容的位置信息的方法。其中重点 之一是如何获取答案的位置信息，即获取答案所在的单元格的信息。为此，提 出了一种适用于任何结构的表格的单元格编码算法，用于对单元格进行标识。 使用单元格编码算法得到的单元格编号，可以表示内容所在单元格的信息，即 答案内容的位置信息。 本文研究了表格题的自动识别算法。表格题的答案的识别类型包括匹配、 包含、范围、相关4 种，匹配、包含类型主要是针对答案内容为文字类型的答 案，范围、相关类型是针对答案内容为数字类型的答案而提出的。每一种识别 类型的答案具有不同的识别算法。按照先识别匹配、包含、范围类型的答案， 最后识别相关类型的答案的顺序，以正确答案为标准，根据每种识别类型的识 别算法对学生答案进行识别。 关键词：远程作业，表格，识别和批改 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t t h ee x e r c i s ei sai m p o r t a n tt e a c h i n gp r o c e s s t h ee x e r c i s ec o r r e c t i n g c a ns u p e r v i s e ，e n c o u r a g ea n ds p u ro ns t u d e n t st os t u d y ，a n dc a nc h e c kt h e t e a c h i n ge f f e c t ，i m p r o v et h et e a c h i n gq u a l i t y m a k eu s eo fac o m p u t e rt o c a r r yo u tt h ea u t o m a t i o nr e c o g n i t i o na n dc o r r e c t i o no ne x e r c i s ei sf a s t e r t h e nt h em a n sc o r r e c t i o no fe x e r c i s e ，a n de a s et h et e a c h e r sw o r k l o a d a t p r e s e n t ，t h e r e a r em a n ye x e r c i s ec o r r e c t i n gs o f t w a r e ，t h e yc a no n l y r e c o g n i z ea n dc o r r e c tc h o o s i n gp r o b l e ma n df i l l i n gp r o b l e m ，t h es o f t w a r ea t p r e s e n ti sn o ta b l et or e c o g n i z ea n dc o r r e c t i n gt h et a b l ep r o b l e m i ne x e r c i s e i nm a n y s u b j e c t ，i n c l u d es o m ek n o w l e d g e w h i c hh a v et ob ei n s c r i b eb y t a b l e ， s u c ha se n g i n e e r i n gs u r v e y , a c c o u n t a n c yt h e o r y , l a b o r a t o r yr e p o r ti ns c i e n c e a n de n g i n e e r i n gc o u f s e t h ea n s w e ro ft a b l ep r o b l e mi ne x e r c i s ei sai m p o r t a n td e m e n t ，i ti s c o m p o s e do fc o n t e n ta n dp o s i t i o ni n f o r m a t i o n t h et h e s i s s t u d i e st h e e x t r a c t i o no fa n s w e rc o n t e n t ，a n dc o n f i r mt h ep o s i t i o ni n f o r m a t i o no f a n s w e r o n ek e y s t o n ei sh o wt oa c l u i r et h ep o s i t i o ni n f o r m a t i o no fa n s w e r ， h o wt oa c q u i r et h ep o s i t i o ni n f o r m a t i o no fc e l l f o rt h i sp u r p o s e ，w eb r i n g f o r w a r do n ek i n do fc e l lc o d i n ga l g o r i t h mt h a tc a na p p l yi na n yt a b l e t r o u g hu s i n gt h ec e l lc o d i n ga l g o r i t h m ，g a i n e dt h en u m b e ro fc e l l s ，t h e n u m b e ro fc e l ld e n o t et h ep o s i t i o ni n f o r m a t i o no fa n s w e r t h en u m b e ro f c e l la n dc o n t e n tc o m p o s et h ea n s w e r b r i n gf o r w a r dar e c o g n i t i o nc o n t r o lm o d e lo f t h ea u t o m a t i o nc o r r e c t i o n i nt a b l ee x e r c i s e d i v i d et h er e c o g n i t i o nt y p eo fa n s w e ri n t o4k i n d s ，i n d u d e t h em a t c h i n g ，i n d u s i o n ，r a n g ea n dr e l e v a n c e ，t h em a t c h i n ga n di n c l u s i o n t y p ei sf o rt h ea n s w e rw h i c hc o n t e n ti st e x t ，t h er a n g ea n dr e l e v a n c ei sf o r t h ea n s w e rw h i c hc o n t e n ti sf i g u r e b r i n gf o r w a r dd i f f e r e n tr e c o g n i t i o n a l g o r i t h mf o re v e r yk i n dr e c o g n i t i o nt y p e s a c c o r d i n gt h es e q u e n c et h a t r e c o g n i z et h ea n s w e ro fm a t c h i n g ，i n c l n s i o n ，r a n g er e c o g n i t i o nt y p ef i r s t ，a t l a s tr e c o g n i z et h ea n s w e ro fr d e v a n c er e c o g n i t i o nt y p e r e f e rt or i g h t a n s w e r , a c c o r d i n gt h i sr e c o g n i t i o ns e q u e n c e ，a c c o r d i n gt ot h er e c o g n i t i o n a l g o r i t h mt od i f f e r e n tr e c o g n i t i o nt y p e ，r e c o g n i t i o nt h es t u d e n t sa n s w e r 西南交通大学硕士研究生学位论文第l ii 页 k e yw o r d s ：d i s t a n c ee x e r c i s e ，t a b l e ，r e c o g n i t i o na n dc o r r e c t i n g 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景和意义 第一章绪论 1 1 1 问题的提出 作业是一个重要的教学环节【m 】。作业有助于学生消化和巩固课堂上所学 的知识，并将知识转化成技能、技巧，训练和培养学生独立工作的能力和习惯， 它是检查学生学习效果的“刻度尺”，是发挥学生主体角色的具体实践活动。 作业的批改对学生的学习起着指导、鼓励和鞭策作用，对教师起着检查课堂教 学效果、促进教学的作用。在作业环节中可以产生和收集大量有关学生学习状 态和对各部分知识掌握情况的有用信息，用以反馈和指导教学。因此，作业是 教学双边活动的一个重要内容，是教学信息反馈的主渠道。 不同的学科具有不同的知识结构，这些不同的知识结构决定了作业形式的 多样性。在文科中，通常以填空题、问答题等形式来考查学生掌握知识的情况， 在理工科中，作业通常以填空题、计算题等形式出现。而有的课程中包含一些 知识结构需要以表格题形式呈现才能够表述清楚，比如工程测量、会计学原理 等课程、理工科课程的实验报告等。 表格题通常含有大量数据，以材料力学实验报告为例，据统计，包括原始 数据、学生测量出的数据和需要使用前两者计算得出的数据，大约平均每个表 格中有9 0 个数据。由于每个学生测出的数据不可能相同，教师手工批改表格 题的需要使用原始数据和实验数据计算出的数据时，没有确切的答案可供参 考，教师要按照学生测出的数据重新计算一遍。假设一个实验班有1 2 0 个学生， 每个学生每周做一次实验，编写一份实验报告，一份报告中含有9 0 个数据， 教师每周需要批改的数据将上万，这个工作量是非常大的，并且每个报告中还 有一些数据需要教师重新根据理论知识和学生测出的数据进行复杂的计算，以 判断学生算出的数据结果是否正确，这使得教师不堪重负。教师手工批改表格 题作业存在以下弊端，不容忽视： 1 学生抄袭。有的学生可能未参与做实验，随意编造几个实验数据，把 别人的计算结果抄过来；或者有的学生参与了测量实验数据，但是对实验所考 察的理论知识没有掌握，最后也把别人计算出的实验结果数据照搬过来。这样 做的结果当然是牛头马尾。教师手工批改表格题很难批改非常仔细，发现学生 西南交通大学硕士研究生学位论文第2 页 抄袭，可能助长抄袭之风。 2 教师工作量大，反馈时问过长。根据上述分析，表格题的数据量可能 很大，并且还有一些数据需要重新计算得出，这不仅使得教师的工作量非常大， 而且会造成每次作业批改的周期过长，使得学生在作业中出现的问题不能及时 纠正，从而影响到教学质量。 1 1 2 周内外研究现状 目前国内以练习或者考试形式出现的教育软件大致分为两类：一类是主要 研究资源共享、在线提交作业、作业管理，末对作业的自动批改技术进行研究 的系统。如文献 6 】研制开发了一个网上作业上传和批改系统，介绍一个基于 w 曲远程教学的作业上传批改系统，改变了以前只能通过f t p 服务器或e m a i l 提交或下载作业的情况，在任何时间任何地方通过i n t e m e t 访问教学服务器提 交作业，进行批改和评分。文献 7 】研制开发的计算机辅助作业系统主要对作业 进行管理。文献 8 】研制开发了基于局域网w e b 方式的作业管理系统，主要研 究了作业布置、作业提交、作业批改和作业信息反馈等功能。另一类软件研究 了选择题和判断题等题型的自动批改技术。文献【9 对网上作业包括选择题和填 空题的自动批改进行了研究。文献f 1 0 1 7 介绍的考试系统也都只能自动批阅 判断题和选择题。目前还没有能够对表格题进行识别和自动批改的软件。 目前也有一些学校利用e x c e l 对部分作业进行自动批改。文献 1 8 】使用 e x c e l 对全部是选择题的作业、试卷进行自动批改和自动统计成绩。文献1 9 使用e x c e l 生成测试样卷、制作标准答案卷、设置自动评分公式、自动改卷并 统计学生成绩，这也是针对选择、填空和判断等简单题型。但是，e x c e l 不能 用于完成表格题的自动批改，这是因为：1 e x c e l 不能设计任何形状的表格体； 2 e x c e l 只能进行简单的匹配和计算，表格题中包含各种类型的答案，答案的 关系更复杂，用e x c e l 根本不能完成表格题答案的自动识别。 表格题型中的实验报告普遍具有数据量大和实验结果计算复杂的特点，批 改实验报告的工作量非常大，针对这种情况，有的学校使用硬件直接采集学生 测量的实验数据，将实验数据直接导出到e x c e l ，按照教师预先设置好的公式 自动计算出实验结果，学生直接从e x c e l 中将数据抄到实验报告中。这种做法 保证了实验结果计算的正确性，只要学生测量的数据是正确的，实验结果就一 定正确，这样可以方便教师批改实验报告，但是，实验的目的是为了让学生通 过实践迸一步巩固理论知识，这种直接代替学生计算出实验结果的做法不能起 到让学生达到巩固理论知识的作用。 西南交通大学硕士研究生学位论文第3 页 通过上述文献研究，可以得知目前教育软件的表格题自动批改技术的研究 尚属空白。由于表格题的特殊结构，在批改表格题之前，需要提取带有位置信 息的表格中的学生解答内容。我们把表格题自动批改技术的研究延伸到与表格 识别和表格信息内容提取的相关领域的研究。 在某种程度上，表格是文本类文档和图形文档之间的一个范畴【，是一种 结构化的数据表示方式，长期以来人们对表格图像的识别主要是从表格结构上 进行分析，建立以表格结构特征为基础的识别系统，以某些表格的特殊标记、 主表格线的数量及其交叉方式等结构特征作为识别依据。这类较为具有代表性 的方法有：2 0 世纪9 0 年代初，w a t a n a b e 和他的同事用分类树的方法来对表格进 行分析、识别；y u 和j a i n 采用区域邻接图( b a g ) 的方式来提取表格的框架 结构和其中的数据，实现表格的识别；1 9 9 8 年e g e s a r i n i 和他的同事建立的基于 表格线条、徽标等特征的高级表格数据提取系统i n f o r m y s 。文献 2 1 2 2 】根据 表格的结构特征，提出了一种统计特征点网格分布的表格图像识别方法，该方 法以表格框线间的交叉点类型作为表格分类的主要结构特征，把表格图像外接 矩形区域归一化为n * n 的网格，并统计每一网格内各种类型特征点的分布情 况，由此形成的n * n 个向量作为表格识别的特征向量。采用了类似度的方法作 为表格分类的判别准则，将未知表格类型的特征向量与预先经过学习建立的表 格模板库中的标准特征向量进行相似性度量，取其类似度最高的模板类型作为 识别结果。这类基于表格具体结构特征的表格识别技术的主要缺点是范化能力 比较差，其使用范围主要限于某些特定类型表格，很难在多领域的表格识别方 面推广开来【2 3 1 。 文献 2 4 】对a u t o c a d 工程图样中标题栏( 注：标题栏为表格) 信息计算机 自动提取方法进行了研究，根据制图规范分析了a u t o c a d 工程图形文件中标 题栏的结构特征，将标题栏划分成若干个区域，提出了用特征识别的方法处理 自由表格结构数据，使结构数据规范化，实现了标题信息智能提取。文献 2 5 】 提出了一种有效的a u t o c a d 工程图零部件信息提取方法，通过分析工程图中 标题栏和明细栏的形式，从宏观布局和微观结构出发归纳了表格的位形特征， 提出了基于单元格和特征点的图纸数据自动提取策略。文献 2 6 对表单文件的 物理结构和逻辑结构进行了分析，提出了自上而下的分析方法和基于文法的分 析方法。但是，上述都是对a u t o c a d 工程图中的表格信息提取和表格图象的 研究，主要是根据a u t o c a d 工程图的制图规范对表格结构进行分析，没有对 通用表格的物理特征进行分析，因此，以上文献只是研究了具有一定规范的 西南交通大学硕士研究生学位论文第4 页 a u t o c a d 工程图的表格信息提取，没有研究普通结构的表格的信息提取方法。 总结以上研究可知，表格题的自动批改技术在国内尚属空白。虽然在表格 图象领域中的表格结构分析和遵循规范的c a d 工程图领域中的对表格信息内 容提取的研究有一定的成果，但都这无法运用于普通表格题作业的识别和批 改，因此，对表格题的识别和批改技术的研究具有重要的意义。 1 1 3 研究意义 研究表格题的自动批改技术具有以下意义： 首先，自动提取表格题信息的技术的研究。提出一种通用的、能够获取任 何结构形式的表格的信息位置的算法。这个算法不仅可以应用于远程作业系统 表格题的信息提取，也可以应用于任何需要对表格内的信息内容进行提取的领 域，主要包括目前使用最广泛的a u t o c a d 工程图标题栏、明细栏的信息提取。 其次，由于表格题通常包含有大量的数据和复杂的计算，表格题自动批改 技术的实现，可以提高表格题作业的批改质量和效率，从而提高实验教学和相 关理论教学的质量。 再次，表格题自动批改技术的实现，可以减轻教师批改表格题作业的工作 量，并且可以返回详细的学生答题情况信息。 1 2 表格题识别技术的特点 1 2 1 表格题基本特征的假设 表格题由表格、表格内的信息、表格外的信息组成。表格内的信息又分为 两类，已知信息和答案信息，除上述特征外，对表格题作以下假设： ( 1 ) 表格题的任何内容包括表格图形和题目信息只能使用远程作业系统的 工具来绘制和表示。 ( 2 ) 表格结构作为己知信息由题文提供，学生不需要对表格形式和结构进 行设计。 ( 3 ) 学生不能变更题目中已知的表格形式和结构。 ( 4 ) 表格题的表格必须是由垂直线和水平线相交构成。 ( 5 ) 表格题的批改对象是表格内的信息，不对表格外的信息进行批改。 ( 6 ) 只对学生输入的答案信息进行批改，不对表格内的己知信息进行批改。 ( 7 ) 不对表格线的粗细、颜色、线型等属性进行识别。 西南交通大学硕士研究生学位论文第5 页 1 2 2 表格题自动批改系统的设计要求 ( 1 ) 适用于各种表格结构。表格题的表格结构多种多样，可能是简单的表 格，也可能是复杂的表格。本系统能够对表格为任意结构形式的表格题进行自 动批改。 ( 2 ) 表格单元与答案内容相关。表格题的答案由位置、答案内容两个部分 组成，相同的答案内容在不同的位置( 即不同的单元格) 它们的意义是不相同 的，只有学生在正确的位置填写正确的内容才识别为正确。 ( 3 ) 适用于各种学科领域。表格题应用的学科领域不同，对学生答案和正 确答案的关系的要求也不同。对于文科的某些概念，学生只要答出关键点即可， 对于另外一些概念，可能需要完全相同，而对于实验报告等答案主要为数据的 题目，可能无法给出一个精细的答案。本系统针对以上情况，总结设置了4 种 识别类型，包括匹配、包含、范围、相关类型。 为了使本系统更便于操作，并且防止在操作过程中可能会出现的一些影响 系统正常运行或识别结果的问题，需要设置以下功能： ( 1 ) 自动生成正确答案。表格题的正确答案由多个答案组成，。在设置正确 答案时很难将与答案内容和它所在的单元格的位置信息对应起来，自动生成正 确答案则可解决这个问题。 ( 2 ) 指示功能。点击一个正确答案，显示它所对应的单元格，用于人工核 实或修改完善正确答案。 ( 3 ) 纠错功能，自动更正教师在绘制表格时可能出现的误差。 1 ，3 本论文主要工作 1 3 1 本论文主要工作 本论文对远程作业系统的表格题的自动批改技术进行了研究。首先研究了 表格题的描述方式和表示方法。然后通过分析通用表格的结构特征，提出了用 于标识表格题答案位置的单元格编码算法。将表格题答案分为四种识别类型， 对每种识别类型的答案提出了不同的识别方法。最后，利用d e l p h i 语言加以实 现。 本论文的主要工作包括以下几个方面： ( 1 ) 表格题的描述方式和表示方法。远程作业系统的表格题的描述方式与 传统的表格题的描述方式一致，主要包括表格和表格内的信息。表格题用图形 西南交通大学硕士研究生学位论文第6 页 对象进行描述，以图形的形式存储在内存中。 ( 2 ) 分析表格的结构特征。对简单表格和复杂表格的拓扑结构与相邻单元 格之间的位置关系进行分析，总结了表格的通用属性，为单元格编码作铺垫。 ( 3 ) 单元格编码算法。单元格编码算法用于对表格内的所有单元格进行标 识，得到的单元格编号用于表示表格题的答案内容的位置信息，单元格编号在 表格题的识别过程中起着重要的作用。 ( 4 ) 表格题的识别算法。将表格题的答案归纳为匹配、包含、范围、相关 四种类型，对每种不同类型的答案提出了不同的识别算法。 ( 5 ) 利用d e l p h i 语言加以实现。本系统实现作业设计、作业布置、作业提 交、作业自动批改和作业信息反馈一整套功能，这些功能主要用工具系统和学 生系统两个子系统来实现。工具系统主要用于设计作业和布置作业等，学生系 统用于学生答题、作业上传、自动批阅以及作业管理等。 1 3 2 各章节论述方式简介 本文共分为5 章。 第一章：介绍了表格题自动批改技术的研究背景和意义。介绍了表格题作 业的基本特征和自动批改系统的应用范围。 第二章：分析了表格的结构特征。分析了简单表格和复杂表格的拓扑结构， 分析了相邻单元格之间的位置关系，总结了表格的通用属性。最后论述了表格 题图形对象的表示方式。 第三章：本章是本论文的重点，其中单元格编码算法又是本章的重中之重。 本章主要论述了三个内容，单元格编码前的表格预处理模块、单元格编码、单 元格编码后的提取单元格信息内容。 第四章：提出了匹配、包含、范围、相关4 种识别类型，针对不同类型的 答案提出了识别算法。提出了以表格题的正确答案为标准的表格题批改的识别 控制方法。 第五章：论述了远程作业系统中表格题自动批改技术的实现。介绍了远程 作业系统，包括系统功能结构、子系统功能结构；介绍了在工具系统中表格作 业的设计包括表格的自动生成、正确答案的设置、语法检查，学生系统中学生 答题和评讲总结功能。 最后总结了本论文，并且提出了展望。 西南交通大学硕士研究生学位论文第7 页 1 4 本章小结 本章主要介绍了本文研究背景、意义及国内外研究情况。通过对表格题作 业自动批改技术及相关的表格图象和表格信息提取领域中的国内外文献的查 阅可知，目前的作业和考试批改软件只能对选择题、判断题等题目进行自动批 改，还不能对表格题进行自动批改。在a u t o c a d 工程图领域内的表格信息内 容提取虽有一定的研究，但是这些研究方法局限于遵循规范的表格，不适用于 任何结构形式的表格。因此，表格题自动批改技术的研究尚属空白。而表格题 的自动批改对减轻教师作业批改工作量、提高教学质量等都有重要意义。 西南交通大学硕士研究生学位论文第8 页 第二章表格的结构特征分析和图形对象描述 表格题由表格、表格内的信息和表格外的信息组成，其中表格内的信息分 成两种：题文信息以及待填写的答案信息。表格题的批改是以正确答案为标准， 对学生答案进行识别的过程，因此，在批改表格题之前必须先从表格中提取学 生答案。表格题的学生答案是由位置、答案内容两部分组成，相同的答案内容 位于不同的位置( 即不同的单元格) 它们的意义是不相同的。因此，在提取学 生答案内容的同时，必须获取答案内容的位置信息。答案内容是位于表格的单 元格中，它的位置信息可以用单元格的物理位置或者是单元格的标识符号来表 示，每个单元格的位置信息必须是唯一的。 表格的基本构成元素是水平线和垂直线相交构成的单元格 2 7 2 8 】( 图2 1 ) ， 由于单元格的分布不同，表格的结构形式是多种多样的，有的简单而有的比较 复杂。这里我们讨论采用单元格的标识符号来表示答案内容的位置信息。要设 计一种方法，能够对任何结构形式的表格的单元格进行标识，给每个单元格确 定唯一的标识符号，首先需要对表格的结构进行分析，总结出不同形式的表格 的共同特征和属性。下面我们主要分析表格内相邻单元格之间的位置关系，表 格的拓扑结构，表格的顶点属性，顶点元素之间的关系等。 图形对象描述主要说明了用来表示表格题的图形对象类型，以及它们的格 式和数据结构。 k 弹性甓量2 期泊桑化，翻蹙实验 缴茼馕离 寮蒋( | 辩) 壤黜( “0镌熬差( )谈教( 戋靛基( ”) 平遣壤散差 “临) 转撬煨娥 置l _ 掣l盖嬲。i 斑变增蠢 盐- z 置糟。+ 曲麟t ：4 ( i 檬) 船氍：前憾x 平斯醒熬熊= 嚣算 气知g p a )一争 图2 - 1 实验报告表格 西南交通大学硕士研究生学位论文第9 页 2 1 表格的结构特征分析 表格是由许多水平线和垂直线相交构成的，这些线垂直相交构成了许多的 矩形区域，我们把由2 条水平和2 条垂直线包围起来的矩形区域称为单元格1 2 。 单元格是表格的基本构成单元。不同结构形式的表格是由于它的单元格分布不 同造成的。 根据单元格的分布可以把表格分为简单表格和复杂表格两类1 3 0 。 定义1 ：所有左右相邻的单元格的高度相等并且所有上下相邻的单元格的 宽度相等的表格称为简单表格。如图2 - 2 所示。 a ) 图2 2 简单表格 定义2 ：存在左右相邻的单元格的高度不相等或者上下相邻的单元格的宽 度不相等的表格称为复杂表格。如图2 - 3 所示。 a ) 上下相邻的单元格长度不相等 b ) 左右相邻的单元格高度不相等 图2 - 3 复杂表格 简单表格的单元格排列整齐，上下相邻的单元格的各对应的顶点纵坐标相 等，左右相邻的单元格的各对应的顶点的横坐标相等。复杂表格的相邻单元格 之间的关系如图2 - 4a ) 和b ) 所示。简单表格相邻单元格的位置关系如图 2 - 4c ) 所示。 西南交通大学硕士研究生学位论文第1 0 页 a ) 复杂表格中上下相邻的单元格间的位置关系 b ) 复杂表格中左右相邻的单元格间的位置关系 c ) 简单表格中相邻的单元格间的位置关系 图2 - 4 单元格与其相邻的单元格间的位置关系 从图2 4 可以看出，简单表格的相邻单元格间的位置关系简单，指定某一 行某一列就可以找到对应的单元格，只要从左至右、从上至下对单元格顺序编 号，得到的编号就可以作为单元格的标识符号。而复杂表格的相邻单元格之间 的位置关系复杂，不能对它进行顺序编号。如图2 3a ) 中的单元格a b c d ，不 能确认它到底是属于第二列还是第三列。 西南交通大学硕士研究生学位论文第11 页 单元格是由四条边和四个顶点构成的，简单表格和复杂表格之间的区别在 于相邻单元格的长度和宽度的相等与否，单元格的边长属性不能作为确定单元 格唯一标识符的通用属性。表格中单元格的分布位置是由水平线和垂直线相交 的交叉点确定的，交叉点也是单元格的顶点，各顶点除坐标属性不同之外其它 的属性都是相同的。因此，单元格顶点是确定表格中单元格的标识符的重要元 素。 单元格顶点的类型有4 种，分别为左上角顶点、右上角顶点、左下角顶点、 右下角顶点，如图2 5 所示。单元格对角的两个顶点就可以确定单元格的位置， 在后面的论述中我们使用左上角顶点和右下角顶点确定单元格的位置。 厂l 一 a ) 左上角顶点b ) 左下角顶点c ) 右上角顶点d ) 右下角顶点 图2 - 5 单元格顶点 为了便于后面描述，先给出几个顶点属性定义： ( 1 ) 向下连通( d ) ：如果顶点不是它所在的竖线段的下端点，则该顶点 向下连通；如果顶点是它所在的竖线段的下端点，则该顶点向下不连通。 ( 2 ) 向右连通( r ) ：如果顶点不是它所在的横线段的右端点，则该顶点 向右连通：如果顶点是它所在的横线段的右端点，则该顶点向右不连通。 观察图2 - 5 ，可以发现单元格顶点的几个特点： ( 1 ) 左上角顶点：向下连通并且向右连通，da n dr ； ( 2 ) 右下角顶点：向下不连通并且向右不连通，( n o td ) a n d ( n o tr ) ； ( 3 ) 左下角顶点：向下不连通，但是向右连通，( n o td ) a n dr ； ( 4 ) 右上角顶点：向下连通，但是向右不连通，da n d ( n o tr ) 。 4 类顶点的r 、d 属性都不相同，可以根据r 、d 属性来判断顶点属于哪种 类型。 在前面我们叙述了一个单元格的位置可以由它的左上角顶点和右下角顶 点决定，因此，在后面的论述中会经常使用这两类顶点，判别它们的方法是判 断它们的r 、d 属性。 顶点和单元格之间的关系： ( 1 ) 每个左上角顶点对应唯一一个单元格，表格内有多少个左上角顶点 西南交通大学硕士研究生学位论文第12 页 就有多少个单元格。 ( 2 ) 在表格内每个左上角顶点都对应一个右下角顶点，它们共同确定一 个单元格。 ( 3 ) 顶点可以是一个单元格的左上角顶点，同时是另一个单元格的右下 角顶点；也可以只是一个单元格的左上角顶点。 简单表格的拓扑结构很简单，如图2 - 6 所示，树上的每个结点表示一个单 元格。每棵子树由4 个结点组成，父结点表示某个单元格，它的3 个子结点表 示在向右向下方向上的3 个相邻单元格。叶子结点表示的单元格在向右向下方 向上没有相邻的单元格。 由于复杂表格的相邻单元格之间的位置关系多种多样，每个复杂表格的拓 扑结构都不一样，很难找出一种通用的表示拓扑结构的方法。拓扑结构是由单 元格的物理位置决定的，不具有通用的表示方法，很难用于确定单元格的相对 位置，因此还需把它细化。 图2 - 6 一个简单表格和它的拓扑结构 单元格是由顶点定位而成，只要获取了单元格的4 个顶点，就确定了单元 格。每个单元格有一个左上角顶点，只要搜索到这个顶点，再搜索出对应的其 它3 个项点就可以确定一个单元格。搜索过程如图2 7 所示，每棵子树为一个 单元格，其中父结点是单元格的左上角顶点，子结点是父结点对应的左下角顶 点、右上角顶点、右下角顶点。判断一个顶点是何种类型可以根据顶点的r 、d 属性来完成。简单表格和复杂表格的顶点属性相同，很显然，这种搜索方法对 它们都适用，可以利用搜索顶点来搜索出单元格，按照单元格被搜索出的顺序 给表格的每个单元格确定一个标识符号。 西南交通大学硕士研究生学位论文第1 3 页 67 1 0u2 67 91 0 1 21 3 1 31 41 51 6 1 51 6 1 71 8 a ) 一个简单表格示例b ) 一个复杂表格示例 c )图a ) 对应的树状搜索图 4 d ) 图b ) 对应的树状搜索图 图2 7 表格和它们对应的树状搜索图 西南交通大学硕士研究生学位论文第1 4 页 2 2 表格题的图形对象描述 表格题由表格、表格内的信息、表格外的信息组成。因此，表格题的表示 主要包括表格的表示和信息的表示，称用来表示表格题的表格和信息的元素为 图形对象。 用来表示表格的图形对象比较明显，可以是直线、矩形、多义线等。表格 题的答案需要填写在各个单元格内，并且所需填的答案数目普遍较多，如果采 用直接的文字输入，用户需要花不少的时间用来回车换行空格来给各个答案定 位。同时由于在识别过程中需要判断哪个答案在哪个单元格中，用普通的文字 输入将会加重定位工作的工作量。因此，我们用图形来描述答案，这里图形的 是有局限性的，不是指广义上的图形，定义和范围见下面内容。 根据目前表格题的常用学科涉及到的知识内容，一般单元格中的内容可以 分为文字、数字、数学公式。我们把文字和数字归为一类，称为普通文字。我 们用标注图形来表示普通文字，用公式图形来表示数学公式。 2 2 1 图形对象类型的说明 图形对象类型就是表示表格题的某一类图形的定义，包括矩形、直线、多 义线、标注、公式等，这些均在远程作业系统中给予明确的定义： 直线：以常量c t l i n e 表示，c t l i n e = l ； 矩形：以常量c t r e c t a n g l e 表示，c t r e c t a n g l e = 2 ： 多义线：以常量c t p o l y l i n e 表示，c t p o l y l i n e = 3 ； 标注( 表示文本) ：以常量c t a n n o t a t i o n 表示，c t a i m o t a t i o n = 4 公式：以常量c t e q u a t i o n 表示，e t e q u a t i o n = 5 ； 其中直线、矩形、多义线用来表示表格，标注表示文字文本，公式表示数 学公式。 2 2 2 图形对象数据结构 1 ) 图形对象的数据结构 t f e a t u r e = r e c o r d 图形对象定义 i n d e x ：w o r d ；图形对象的索引值 s t y l e ：t p e n s t y l e ；s t y l eo f t h ep e n c o l o r ：t c o l o r ； c o l o ro f t h ef e a t u r e p e n w i d t h ：i n t e g e r ；| 嘲谶o f t h el i n e 西南交通大学硕士研究生学位论文第1 5 页 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 f 图形对象的类别 ，直线定义 f i l i n e ：fx l l , 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 l r e e t a n g l e ：( x 1 , y 1 , x 2 ，y 2 ：i n t e g e r ；矩形以及圆和椭圆外界矩形 的左上角和右下角坐标 b m 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 e1 ：画刷类型值 多义线定义 f i 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 ； 多义线的点的数量( 1 ，判断单元格( t o ，t 1 ，t 2 ，t 3 ) 与单元格( t o 一1 ，t 广1 ，t 2 1 ，t 3 1 ) 的高度值是否相等，t o 和t o 一1 点的垂直坐标是否相同。如果不满足上述条件 令p = 0 。 ( 4 ) 如果j ) l ，判断单元格( t o ，t 1 ，3 2 ，t 3 ) 与单元格 ( t o - l 一1 ，t l l _ 1 ，t 2 一l l ，t 3 一l _ 1 ) 的宽度值是否相等，t o 与t o - l - 1 点的水 平坐标是否相同。如果不满足上述条件令p - - 0 。 ( 5 ) 如果p = - i 且j = l ，则i = i + l ；t k = t k + 1 ( k = 0 “3 ) ；返回第二步。 ( 6 ) 如果p = 0 且j = 1 ，则- i - i - i 广- - i ：i = l ；转行t k = t k + 2 ( k = 0 3 ) ；j = j + 1 ；返回 第二步。 ( 7 ) 如果p = i 且j 1 且i l 且i = l ，则转行t k = t k + 2 ( k = o 3 ) ：i = l ；j = j q ；返回 第二步。 ( 9 ) 如果p = 0 且j l 且i l ，则g = j 一1 ，结束搜索。 o 4 8 1 2 1231 9 设计1 56 。丝杠 审核1 91 1 0 1 1 2 1 批准h 31 41 5 比例 1 ：1 1 7 4 5 钢机械厂 更改员 更改号更改次日期 2 0 2 2 1 61 8 2 3 图3 - 1 1a u t o c a d 图标题栏 用同样的方法就可以搜索出标题栏中的所有区域。如图3 - 1 1 中共有6 个 区，表示成以对角点所围成的矩形区域为：( 01 5 ) ，( 1 21 6 ) 。( 31 8 ) ，( 1 92 0 ) ，( 2 1 西南交通大学硕士研究生学位论文第2 5 页 2 2 ) ，( 1 72 3 ) 。图3 - 1 2 是共有9 个分叉组成的树状搜索图，每一个分叉由4 个 顶点构成，可表示一个单元格。 表格区域搜索算法是先把一个复杂表格划分成若干个区域，每个区域为一 个简单表格。再对简单表格进行信息提取。 图3 一1 2 树状搜索图 3 2 2 单元格编码算法 表格区域搜索算法的主要思想是：从表格的左上角顶点开始，找出单元格 的左上角顶点，再以左上角顶点为基点向右向下搜索出它对应的另外3 个顶点， 计算出单元格的高度和宽度，以高度和宽度作为判断条件，如果水平方向单元 格左上角顶点的纵坐标相同，单元格高度值相等，垂直方向单元格左上角顶点 的横坐标相同，单元格宽度值相等，则继续向右向下搜索，否则这个区域划分 结束。区域搜索算法是先将复杂表格划分为简单表格，再对每个简单表格进行 编码。 是否可以不对复杂表格划分区域而直接对复杂表格进行编码呢? 由于复 杂表格内不是所有的单元格高度和宽度都相等，不能使用高度和宽度作为条 件。本节提出了一种依据表格内单元格顶点的属性和单元格之间的位置关系， 可以对任何形式的表格的单元格进行编码的方法。单元格编码主要分为两步， 首先搜索出所有的单元格顶点并得出它们的属性，然后沿着向右向下的方向遍 历整个表格，按照单元格被搜索出的顺序给它们编码。 西南交通大学硕士研究生学位论文 第2 6 页 1 单元格顶点搜索 单元格顶点指标定单元格几何位置的定义点，即水平表格线和垂直表格线 的交叉点，其类型有9 种，如图3 8 所示。定义单元格顶点集合v s k ( k = 1 ， 2 ，m ) ，m 为顶点总数，其中s k 为顶点，s k = x k ，y k ，n k ，r ，d ，f l a g 。 x k 、y k 为顶点坐标；n k 为顶点在顶点序列中的编号，在进行单元格编号之前为 初始值0 ：r 、d 为布尔值，r 表示顶点是否向右连通，向右连通表示顶点不 是所在水平线的的右端点，d 表示顶点是否向下连通，向下连通表示顶点不是 所在垂直线的下端点；f l a g 为布尔值，表示顶点是否已扩展，在进行单元格编 号之前为初始值f a l s e 。在单元格顶点搜索过程中可以 ：导到x k 、y k 和r 、d 的值， i l k 和f l a g 的值在单元格编号过程中获得。 将水平线和垂直线分别存储在横线组和纵线组，并且均己按位置排序( 横 线按纵坐标从小到大排序，纵线按横坐标从小到大排序) 。对横线和纵线组采用 单元格顶点遍历算法，逐个搜索单元格顶点。添加至单元格顶点集合。单元格顶 点遍历算法如下： 算法3 1 单元格顶点搜索【3 习 ( 1 ) 从横线组中取出表格中第一条横线作为当前横线； ( 2 ) 从纵线组中取第一条与当前横线相交的纵线作为当前纵线，进入 ( 3 ) ；若没有相交纵线则转( 5 ) ； ( 3 ) 判断得出相交点的r 、d 属性的值，并记录其坐标x k 和y k ，添加进 单元格顶点集v s k ； ( 4 ) 从纵线组中当前纵线后面，取出与当前横线相交的下一条纵线作为 当前纵线，回到( 3 ) ；若没有相交纵线则进入( 5 ) ； ( 5 ) 从横线组中取出当前横线的下一条横线作为当前横线，转至( 2 ) ； 若无后继横线，则进入( 6 ) ； ( 6 ) 完成单元格顶点遍历。 2 单元格搜索 图3 - - 1 3 单元格特征图 单元格是指d a 4 条水平和垂直线包围起来的矩形区域。定义单元格集合为 t t k ( k = l ，2 ，3 ，n ) ，n 表示单元格总数，t k 表示第k 个单元格，t k = ( n u m b e r ， 西南交通大学硕士研究生学位论文第2 7 页 x k l ，y k l ，x h ，y h ) in k ，x l d ，y u ，x k r ，r ( 实数集) ，n u m b e r = 表示单元格 的编号，x k l ，y u 表示单元格左上角顶点坐标，x h ，表示单元格右下角顶点坐 标。 整个表格的单元格搜索工作主要分为两步：( 1 ) 搜索单个单元格；( 2 ) 搜 索当前单元格的后续单元格。遍历整个表格的方法是：搜索出表格中的第一个 单元格，再搜索出当前单元格的后续单元格，直到搜索出表格中的最后一个单 元格为止。搜索原则