一种答题卡客观题识别算法

要曙丽，王少荣,2，盖 孟，王 震

一种答题卡客观题识别算法

要曙丽1，王少荣1,2，盖 孟2,3，王 震4

(1. 北京林业大学信息学院，北京 100083；2. 北京市虚拟仿真与可视化工程技术研究中心，北京 100871；3. 北京大学信息科学技术学院，北京 100871；4. 沈阳理工大学艺术设计学院，辽宁 沈阳 110159)

在保证阅卷质量的前提下，网上阅卷系统不仅极大地减少了教师的工作量，而且降低了对试卷纸张质量的要求，节约能源。但是，网上阅卷系统中的客观题识别效果对答题卡图像质量和排版有很强的依赖。为此，提出一种鲁棒的客观题识别算法。首先，考虑到用户填涂时可能偏离填涂区域，或者用户图像和模板图像位置匹配出现的误差，提出了滑动窗口策略重新定位实际的填涂区域，消除相关的偏差。然后，通过分析各选项的直方图，并引入加权平均灰度消除单个选项中填涂不均匀的影响。对同一题下的每个选项进行比较，使得识别算法有很强的局部适应性，克服使用全局识别策略带来的参数选择困难。实验结果表明，该算法兼容性好，可以适用于不同排版类型的答题卡客观题识别，鲁棒性强，识别精度高，适用于各种扫描质量和不同填涂质量的答题卡。

网上阅卷系统；客观题识别算法；滑动窗口；加权平均灰度

传统的手工阅卷方式成本高、效率低且阅卷误差大，网上阅卷方式不仅快速准确，而且可以方便地记录和汇总考生数据[1]。客观题识别算法是网上阅卷系统的核心算法之一。大部分的网上阅卷系统对答题卡图像质量等有严格要求[2]；当答题卡图像噪声较多，或者存在填涂不均匀、擦除不干净等情况时，其识别算法的正确率会大大降低。刘志方[3]将系统通过设置同步头等方法辅助识别，但对答题卡的排版有严格的要求。

为了解决以上问题，本文提出一种鲁棒的客观题识别算法。考虑到用户填涂时可能偏离填涂区域，或者用户图像和模板图像位置匹配出现的误差，滑动窗口算法的策略重新定位考生的填涂区域，消除相关的偏差。在识别过程中，已有算法往往通过计算填涂比例来进行判别，通过分析选项区域的直方图，并引入加权平均灰度，以消除单个选项中填涂不均匀的影响。对同一题下的每个选项进行比较，使得该算法有很强的局部适应性，克服使用全局识别策略带来的参数选择困难。

本文算法具备以下优点：①兼容性好，可以适用于不同排版类型的答题卡客观题识别。②识别准确率高，鲁棒性好，适用于各种扫描质量和不同填涂质量的答题卡。

1 相关工作

本文将制作模板的答题卡图像定义为模板图像，将需要识别的考生填涂的答题卡图像称为用户图像。

答题卡客观题的识别流程主要包括答题卡格式描述文件的载入、用户图像矫正、填涂识别等。

1.1 答题卡格式描述文件的制作

制作答题卡格式描述文件需要用户手动设置答题卡信息。文献[3]需要用户手动标定答题卡的定位信息和填涂信息，用户通过鼠标左键点击和拖曳实现框选区域的功能。阮少林[4]制作答题卡模板时，首先将卡片上所有的填涂区域全部填涂，然后扫描输入，对输入图像进行预处理，提取所有的目标点；手动分类划分题组。

1.2 用户图像的矫正

图像矫正操作是答题卡正确识别的前提。文献[3]基于图像的偏转角度进行纠偏，首先计算偏转量，然后矫正图像。吴军[5]介绍了基于图像倾斜角的矫正算法，提出了全新的边界特征点检测算法和边界倾斜角度故计算法。白士御[6]提出了一种基于连通域分析和Hough变换的倾斜校正方法，通过连通域分析预估倾角，以较长的连通域为依据划分出文本区域，结合经边缘检测处理后的版面区域，以不同角度步长分别进行Hough变换，得到最终精确的倾角。在已有模板图像的信息，文献[3]取用户图像中3个定位块的中心坐标和模板中对应区域的中心位置求其坐标变换矩阵，然后对用户图像进行几何变换来进行矫正。

1.3 填涂区域的判断

判断考生选择结果有2种方式：判断填涂点和判断考生手写的英文字符。对于不同的填涂点识别算法，填涂率都是判断某区域是否填涂的重要指标。文献[4]通过给定一个阈值，计算二值图像中某区域中黑色像素的数量与该区域面积的比值，通过比较该值和阈值来判断是否填涂。相对于仅依靠图像的灰度信息或填涂面积等单一信息进行判断的算法，文献[3]提出了基于图像综合特征的填涂点识别算法。先对图像进行灰度级形态学和自适应二值化等预处理操作以后，然后去除图像中干扰轮廓，再根据选项的平均灰度、灰度和、填涂面积和方差等信息计算出评价指标，最后再根据评价指标进行填涂结果的判断。识别手写字符方法的一般流程为：首先定位答题区域，然后利用神经网络分类器识别英文字符。SIMONYAN和ZISSERMAN[7]提出VGG卷积神经网络，更精确地完成图像分类工作。SZEGEDY等[8]提出一个22层深的网络GoogLeNet，提高了网络识别率。HE等[9]提出了深度为VGG网络的8倍，但仍然具有较低的复杂度的ResNet。本文通过识别填涂点完成选项判断工作。

2 算法概要

本文使用的答题卡格式描述文件通过用户交互制作而成。答题卡格式描述文件主要包括定位块的位置信息和客观题组织结构的信息。

图1为答题卡识别流程，首先载入答题卡格式描述文件，自动识别输入的用户图像。算法同时接收一张答题卡的正、反面2张图像作为输入，在阅卷之前，首先判断用户图像的正反面，同时调整图像的上下方向；然后根据定位块信息完成矫正操作，最后根据答题卡格式描述文件中的客观题区域进行填涂识别，输出判断结果。

图1 答题卡识别流程

3 答题卡识别

答题卡识别时，根据制作好的答题卡格式描述文件对用户图像的对应区域进行识别。一组用户图像包括一张答题卡的正、反面2张图像，由于人工因素和扫描仪设置，这2张图像的正反顺序和上下方向都可能出现错误。因此，输入2张图像后，首先需要完成正反面和上下方向的判断，然后根据定位块信息进行矫正，完成客观题判断。

3.1 答题卡格式描述文件

答题卡格式描述文件的制作是答题卡客观题识别的首要问题[3]，主要通过用户交互编辑完成。

图2为答题卡格式描述文件的部分信息。其中紫色矩形框区域为标题，标题只出现一次，且位于答题卡第一页，因此本文使用标题完成答题卡正反面判断；红色矩形框为定位块，用于用户图像矫正；蓝色矩形框为题号，绿色矩形框为选项，黄色矩形框为客观题的一道小题，包含题号和选项。

图2 答题卡格式描述文件的部分信息

3.2 正反面判别

如图2所示，比较标题区域与其他区域的字号，标题区域的字号明显相对较大，故可通过检测标题完成答题卡正反面的判断，同时调整用户图像的方向。答题卡格式描述文件中保存有模板图像的长宽信息和标题矩形r。标题检测算法如下：

(1) 将当前图像旋转调整到与模板图像具有相同的长宽比，在模板图像上截取矩形r：将矩形r的坐标往左右各扩张个像素的长度，往上下各扩张个像素的长度(=50，=30)。

(2) 截取r区域图像，首先进行二值化和反相操作，然后检索轮廓，计算轮廓的包围盒并将包围盒从左到右排序。自左侧的包围盒开始，当2个包围盒的距离不超过阈值时，合并包围盒；最终，在方向形成一个矩形r图3(a)中蓝色矩形框为各个轮廓的包围盒，红色矩形框为r。

(3) 图3(b)中红色矩形框即为上述的r。由于噪声影响，红框所示的r与r形态差距较大。因此，当r.h/r.h≥时，重新计算r.b：将包围盒的下边界由低到高排序，计算队列中从1/3到2/3的平均值作为r.b。结果如图3(c)所示。

(a) 轮廓包围盒和初始的r检测结果图

(b) 存在噪声的r检测结果图

(c) 更新的rpt结果图

输入一张答题卡的正反面2张图像，存在4种可能的组合，计算每种组合下的r，存入队列l。通过综合比较r和r的属性，将与r相似度最高的r所在组合作为正确结果。相似度计算过程如下：

(1) 基于矩形图像的特征，需计算2个图像的高度、宽度、位置偏差和灰度均值的差值，分别用d，d，d，d表示，即

其中，g为图像的平均灰度。

(2) 定义式(6)的相似度函数，w(=0,1,2,3)是平衡条件(1)中多个度量的权重。也就是选择值最小的r作为用户图像的标题区域，即

其中，和分别为用户答题卡上点的和坐标；(，)为图像在点的像素值；，，，分别为矩形的左、右、上、下边界。

3.3 图像矫正

3.3.1 定位块的寻找

答题卡格式描述文件中保存了多个定位块b(=1,···,)，设r为每个定位块的最小外接圆半径。在用户图像中，在以b的中心为中心，r+(=50)为半径的圆形区域中提取对应的定位块。将该区域内符合条件的所有定位块都压入定位块候选队列l。本文结合轮廓检测和区域检测2种途径提取定位块，具体步骤如下：

步骤1.采用文献[3]提出的定位块识别算法：对上述区域图像执行二值化和形态学操作，然后进行轮廓查找，判断轮廓是否为矩形，如果符合条件，则将其存入l。

步骤2. 对于图4所示的用户图像的定位块灰度不均匀或与其他元素粘连，无法获取其完整轮廓的情况，步骤1无法处理。因此，本文继续执行模板匹配算法在该圆形区域上寻找与定位块图像最相似的区域，将该区域的矩形数据压入l。

通过以上2个步骤之后，可寻找该区域上所有可能的定位块。

(a) 标定块不均匀情况

(b) 标定块与其他元素粘连情况

图4 特殊定位块图像

3.3.2 定位块的匹配及选择

每个定位块b均得到候选列表l，因此可能存在多种组合。在执行矫正操作之前，需要对模板中的每个定位块从用户图像中选择相应的定位块进行匹配，定位块匹配算法流程如下：

(1)l长度为1的b存在唯一确定的组合，将匹配结果保存到集合；

(2) 对剩余的候选列表大于1的定位块：对于中的每一个元素，计算定位块相对于模板定位块在和方向的平均偏移值。将当前定位块的位置减去偏移值得到其应该存在的位置，从候选列表中选择与该位置最接近的定位块作为匹配结果；

(3) 如果初始时不存在唯一匹配的情况，每个b选择与其最接近的定位块作为正确匹配。

算法得到集合之后，如果集合的长度大于3，如图5所示，需要从中选取不在同一直线上的3组定位块。

图5 4个定位块的答题卡图像

部分答题卡的定位块个数存在小于3的情况，或者，由于印刷原因，定位块被遗漏或者浓度很低，实际用于矫正的定位块数量会少于3个。因此，本文根据集合的长度选择不同的矫正算法。

3.3.3 图像矫正

本文根据对答题卡图像执行矫正操作进行讨论：

(1) 当=3时，本文采取仿射变换方法来实现图像矫正[3,10]。

(2) 当=2时，假设模板和用户图像之间的变换只包含缩放和平移，即

根据式(7)，利用最小二乘法，解线性方程组，即

在得到，t和t的值之后，构造转换矩阵，将当前的用户答题卡图像转换成矩阵与转换矩阵相乘，则可以得到矫正之后的图像。

(3) 当=1时，可以假设模板和用户图像之间只包含平移变换，即

其中，和分别为用户答题卡上点的和坐标；和分别为模板答题卡上对应点的和坐标；为和方向的伸缩量；t和t分别为点在和方向的平移量；、分别为和方向的偏移量。

3.4 客观题自动识别

经过矫正后的用户图像中的客观题区域与模板图像的基本一致，但依然可能存在一定偏差，因此首先采用滑动窗口算法消除误差，然后计算该区域图像的灰度指标，综合判断考生的填涂结果。

3.4.1 填涂区域定位

为了消除用户图像与模板图像中选项的坐标位置可能存在的偏差，本文提出一种消除偏移影响的滑动窗口算法。滑动窗口算法如下：

(1) 以答题卡格式描述文件中的选项位置作为初始窗口(图6(a)中绿色矩形区域)，计算该窗口在和方向可移动的最大距离，本文取值为相邻选项之间相距最近的横向距离和纵向距离。搜索窗口为(图6(a)中蓝色虚线框)。

(2) 如图6(a)所示，初始窗口首先在方向上移动，寻找灰度总和最小的区域，作为下一步检测的初始窗口，即棕色矩形框包围区域。

(3) 如图6(b)所示，控制寻找到的棕色窗口在方向上下移动，寻找灰度总和最小的区域，定位到黄色矩形框所在位置。

(4) 计算图6(c)中黄色窗口区域的平均像素值g，从窗口边缘向内进行次(=2)收缩操作，若第层的像素平均值小于g，则停止收缩；直到=。4边都停止收缩得到的窗口即为本文所求的实际填涂区域，也就是图6(c)中红色矩形框包围的区域。

(a) 初始窗口

(b)方向移动结果

(c) Y方向移动结果

结果如图7所示，绿色矩形框为答题卡格式描述文件上选项所对应的参考位置，红色矩形框为本文算法的计算结果。面对不同情况，本文提出的滑动窗口算法都可以定位到考生实际的填涂区域。

图7 填涂区域定位结果

3.4.2 填涂区域的简单灰度特征

选项是否被填涂主要由此区域内数量最多的同类像素的灰度特征决定，由于考生填涂不均匀，所以本文统计选项的256色图像的直方图，计算图像中像素聚集区间的灰度特征。

本文首先将修正的填涂区域灰度图像分成个等级(=12)，统计各个等级内的像素数量。为了消除噪声的影响，统计包含像素最多的灰度等级及其相邻等级中的灰度总和g与像素个数g，计算像素平均值g=g/g。

图8为一组截自用户答题卡的4个选项，其属于同一选择题。图9为图8选项对应的直方图，图中蓝色竖线为g所在区间。其中横轴代表灰度等级，纵轴代表像素数量；图中每个柱子的宽度为(=256/)，高度为该灰度等级内像素数量。选项A，C，D都为未填涂的选项，直方图集中在230~255像素区间内；选项B为填涂项，像素主要分布在60~80区间。

图8 选项样例

图9 统计直方图

3.4.3 填涂区域的加权灰度特征

由于考生具有不同的填涂习惯，因此被填涂区域的g处于跨度较大的灰度区间，如图10所示。因此，如果把g作为选项是否被填涂的度量，则当选项满足条件g≤(≥185)，则认为该选项被填涂。但是，图11中已经被擦除的选项B的g<185，此种情况下此度量难以完成正确的判断。

图10 考生填涂的原图像和选项gm的可视化

(a) 考生擦除选项B (b) 选项gm的可视化

同时，上述算法计算得到的g值可能比考生实际填涂的灰度值低很多，因而不能反映选项的填涂情况，如图10(a)的A选项，视觉判断其g不能表示经过用户填涂的A选项。

因此，本文引入新的选项填涂识别度量：带权重的灰度均值g和带权重的前景比例r。

具体的计算过程如下：

(1) 对选项区域进行二值化操作，搜索轮廓，将轮廓包围的像素面积小于等于的区域中的所有像素的像素值的灰度降低(=3)，此步骤填补用户填涂不均匀导致的空隙。将填充后的二值图像的黑色像素的比例作为前景比例r，白色像素的比例作为背景比例r。

图12为图8各个选项r可视化的图像，图13为图8各个选项r可视化的图像。

图12 选项rf的可视化图像

图13 选项rb的可视化图像

(2) 根据图像的灰度值，采用分段线性的方式计算选项中各个像素的权重，即

(3) 根据，计算选项的g，即

其中，和分别为用户答题卡上点的和坐标；(，)为图像在点的像素值；为图像的宽度；为图像的高度。

(4) 统计选项区域内像素值小于g的像素所占比例，此值为r。

图14为图8各个选项r可视化的图像，图15为图8各个选项g可视化的图像。

图14 选项rwf的可视化图像

图15 选项gwm的可视化图像

结果如图16所示，可以明显观察到图16(b)中4个选项的灰度与图10(a)中原图像的4个选项的灰度相近；而r又体现了填涂区域和未填涂区域的前景比例的差别。

(a) 选项r的可视化

(b) 选项g的可视化

图16 图10中(a)组的参数信息

3.3.4 填涂结果判定

设客观题题目个数为n。对客观题的选项完成上述操作之后，将所有选项按照g从小到大排序，将前n个选项作为统计数据，计算其平均灰度作为图像的前景值g。

若g大于等于某个给定阈值(本文取240)，即整体选项的前景像素接近255，那么将所有选项都判定为未填涂。

在判断填涂结果时，本文以一个小题为单位，横向比较该题目下的所有选项以判断考生的填涂结果。算法如下：

算法1.将此题目中的每个选项逐个判断，当选项的r≥0，直接认为该选项未被填涂；当r≥1，将该选项的识别标记记作1。本文0=0.43，1=0.4。

算法2.将>0的选项根据g从小到大排序，去除序列中g>T0的选项，然后将第一个选项的r和g保存，分别用′和′表示。若选项满足g–′≤D0且′–r≤D0或者′<r的条件，则将此选项视作填涂项。更新′为填涂项r的平均值。本文T0=180，D0=30，D0=0.12。

填涂判断结果如图17所示，矩形框选中的区域代表算法将此选项判定为填涂项。针对上述的用户图像，本文算法的识别结果全部正确。

(a) 填涂过浅的识别效果

(b) 填涂未满的识别效果

(c) 填涂不均匀的识别效果

(d) 涂擦不干净的识别效果

(e) 填涂区域过大的识别效果

(f) 卷

(g) 卷面存在折痕干扰的识别效果

4 结果和讨论

本文的测试图片由四川生学教育科技有限公司提供，所用答题卡图像均为考试实际扫描得到的图像。

程序的运行环境为：Windows10×64，Intel i7 8700，16 G RAM。对于分辨率为3105×2163的图像，识别速度大约6张/秒。

本文在5套不同扫描质量的答题卡图像的数据集上测试系统的识别准确率。测试数据集来自不同学校，使用不同扫描仪；包含纸张、印刷质量、填涂质量各不相同的答题卡。本文算法都能得到99.98%以上的识别率。表1为四川省三台高中高二2018年9月的月考的各科目的答题卡识别结果统计。

表1 四川省绵阳市三台县三台高中高二2018年 9月月考的答题卡识别结果统计表

(注：PN为答题卡总数；TN为题目总数；PE为识别错误的答题卡数目；TE为识别错误的题目；PER为识别错误的答题卡所占比例；TER为识别错误的题目所在比例；Acc为识别正确率，即正确识别的答题卡比例)

db_1到db_5表示5次考试的数据集，分别为三台高一2018年12月、三台高二2018年12月、三台高三2018年12月、绵阳一诊和三台高三2019年2月考试产生的数据集。GS，LZF，LSQ，ZY，ZL表示文献[2-3, 11-13]提出的答题卡自动识别软件。其中，LZF，GS和本文提出的识别算法都采用计算多个评价指标综合比较的方法；LSQ，ZY和ZL的识别算法都是通过比较选项内黑色像素的数量和固定阈值的方法来判断选项是否填涂，识别率很大程度上依赖于阈值的选取。因此，本文认为综合多个评价指标的识别算法产生的结果可能更好。图18为本文算法和上述2个系统的算法在5个数据集上各科目的平均识别率的曲线图。其中，db_5的纸张印刷质量比其他数据集差，所有算法的识别率均有所降低，但是本文算法的识别率仍然能够达到99.98%以上。由图5可见，本文算法具有较高的识别率且鲁棒性强。

图18 识别率的曲线图

如图19所示，当遇到第49题的情况时，即考生在实际选择的选项C中填涂较浅且填涂面积过小，同时，其他选项A存在擦除，2个选项的g和r计算结果在给定范围内，如图19(b)和(c)所示。识别结果可能会出现错误，算法将A选项也视为填涂项，图19(a)中红色矩形框表示识别错误，也是下一步工作的研究重点之一。

(a) 填涂识别结果(b) rwf可视化(c) gwm的可视化

5 结束语

本文实现了一个答题卡客观题的高效识别算法。首先根据答题卡格式描述文件完成正反面的判断，执行图像矫正操作，然后使用滑动窗口算法消除偏差，根据各选项区域的灰度特征完成客观题区域的识别。实验结果证明了本文算法的有效性。

[1] ZHOU J X, YANG J C, SONG H B, et al. An online marking system conducive to learning [J]. Journal of Intelligent and Fuzzy Systems, 2016, 31(5): 2463-2471.

[2] 郭崧.答题卡图像识别系统研究与实现[D]. 沈阳: 辽宁大学, 2017.

[3] 刘志方. 基于数字图像处理的答题卡自动识别软件[D]. 广州: 华南理工大学, 2015.

[4] 阮少林. 网上阅卷中信息提取与识别技术研究[D]. 成都: 电子科技大学, 2010.

[5] 吴军. 扫描文档图像的处理方法的研究和应用[D]. 济南: 山东师范大学, 2015.

[6] 白士御. 基于SVM的印刷体数学公式识别方法研究与系统设计[D]. 沈阳: 沈阳工业大学, 2015.

[7] SIMONYAN K, ZISSERMAN A. Very deep convolutional networks for large-scale image recognition [EB/OL]. (2015-04-10). [2019-09-18]. https://arxiv.org/abs/1409.1556.

[8] SZEGEDY C, LIU W, JIA Y, et al. Going deeper with convolutions [C]//2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). New York: IEEE Press, 2015: 1-9.

[9] HE K M, ZHANG X Y, REN S Q, et al. Deep residual learning for image recognition [C]//2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). New York: IEEE Press, 2016: 770-778.

[10] 李春阳. 基于同源图像配准算法的研究及系统设计[D]. 长春: 吉林大学, 2016.

[11] 刘胜强. 纸卷数字化和图像识别在网上阅卷中的应用[D]. 成都: 电子科技大学, 2010.

[12] 赵洋. 基于OpenCV的网上阅卷技术的研究[D]. 济南: 山东大学, 2009.

[13] 张玲. 基于图像工程的网上阅卷系统的研究与设计[D]. 济南: 山东大学, 2010.

A Novel Recognition Algorithm of Objective Questions for Exam Answer Sheets

YAO Shu-li1, WANG Shao-rong1,2, GAI Meng2,3, WANG Zhen4

(1. School of Information Science and Technology, Beijing Forest University, Beijing 100083, China; 2. Beijing Virtual Simulation and Visualization Engineering Center, Beijing 100871, China; 3. School of Electronics and Computer Science, Peking University, Beijing 100871, China; 4. Shenyang Ligong University, School of Art and Design, Shenyang Liaoning 110159, China)

Under the premise of ensuring the quality of the marking, the online marking system not only greatly reduces the workload of the teachers, but also lowers the requirement of high quality exam paper and saves energy. However, the results produced by automatic judgment by the online marking system for objective questions heavily depends on the image quality of high-speed scanning and layout of the exam answer sheets. This article proposes a robust recognition algorithm of objective questions for exam answer sheets. Firstly, considering the possibility that the user may deviate from the filling area, or the possible error in the match between the present image and template image, a sliding window strategy is proposed to relocate the practical filling area in order to eliminate the related deviation. Then the histogram of each option is calculated, and a weighted average intensity is introduced to remove the effect of the uneven filling between different options. The comparison between each option for the same question enables the recognition algorithm to have strong local adaptability. At the same time, this strategy overcomes the difficulty of parameter selection caused by the global recognition strategy. The experimental results show that owing to good compatibility, our algorithm is suitable for different typesetting types of exam answer sheets in the recognition of objective questions. In addition, the algorithm is characteristic of high recognition accuracy as well as strong robustness, thus applicable to exam answer sheets of varying scanning quality and different filling quality.

online marking system; recognition algorithm of objective questions; sliding window; weighted average intensity

TP 391

10.11996/JG.j.2095-302X.2019050900

A

2095-302X(2019)05-0900-08

2019-04-11；

定稿日期：2019-05-01

国家重点研发计划项目(2017YFB1002705)；中央高校基本科研业务费专项基金(2015ZCQ-XX)；北京林业大学“北京市大学生科学研究与创业行动计划”项目(S201710022068)

要曙丽(1996-)，女，山西寿阳人，本科生。主要研究方向为图形图像处理、计算机视觉等。E-mail：shuliyao@outlook.com

王少荣(1975-)，男，江西永丰人，讲师，博士。主要研究方向为图像处理、计算机图形学等。E-mail：shaorongwang@hotmail.com