扫描阅卷系统中模板定制和图像聚类方法的研究

孙建芳　李万秋　张国辉　李傲松

摘要：为了适应答题卡多样化需求和提高答题卡图像识别的准确率，提出了扫描阅卷系统中模板定制和图像聚类方法。首先基于人机交互方式进行模板定制，定义填涂区域属性和答题卡结构信息，并开发了模板制作器，实现答题卡模板文件的制作和管理；其次给出基于Kmeans改进算法的扫描阅卷系统中图像聚类方法，选择局部聚集密度最大的数據点作为初始聚类中心以得到全局较优的聚类结果，并通过计算区分度进行聚类结果评价；最后基于VC++和MS SQL Server2000开发了基于Kmeans改进算法的扫描阅卷系统，并对该系统进行了实验测试。测试结果表明，采用Kmeans改进算法进行扫描阅卷时能够得到稳定的图像聚类结果，大大提高了客观题阅卷准确率，具有较高的实用价值。

关键词：扫描阅卷系统，模板定制，Kmeans改进算法，图像聚类

中图分类号：TP391文献标识码：A

Abstract：To adapt to the requirement of exam card diversity and enhance the image recognition accuracy of exam card，template customization and image clustering method in the exam card scanningreading system has been proposed.At first，template customization based on human computer interaction has been given and the attribute of the filling zone and structural information of exam card has been defined.And template customization tool has been developed to realize template customization and management.Then image clustering method based on Kmeans improved algorithm has been given.To obtain clustering results of the global optimum，data points with the maximum local gathering density has been chosen as the initial clustering centers.And clustering results has been evaluated by calculating the item discrimination.At last with VC++ and MS SQL Server2000 exam card scanningreading system based on Kmeans improved algorithm has been developed and the system has been tested.It has been shown that that stable image clustering results can be obtained with the exam card scanningreading system based on Kmeans improved algorithm.And image recognition accuracy of exam card has been improved.The exam card scanningreading system has better utility value.

Key words：exam card scanningreading system；template customization；Kmeans improved optimization；image clustering

1引言

阅卷是考试中的一个重要环节，传统机器阅卷需要光电阅卷机和专用机读卡，虽然具有阅卷速度快和适合大规模考试的优点，但只能采用专用答题卡进行扫描阅卷，存在产品价格高和无法灵活定制试卷答题模板等缺陷[1-3]。另外，扫描阅卷系统对图像输入设备采集答题卡图像自动进行图像处理和识别，其操作简单且成本低廉，越来越得到广泛应用[4，5]；但在扫描阅卷系统中由于扫描得到的图像质量存在个体差异，填涂未擦除干净或填涂深浅不一会增加客观题的误判率。因此，为了适应答题模板多样化需求和提高扫描阅卷系统对答题卡图像识别准确率，必须进行模板定制和对答题卡进行合理的图像聚类。

目前扫描阅卷系统中采用统一阈值法进行图像识别，其扫描阅卷的准确率有待进一步提高[6-8]。基于划分的KMeans 算法以其简单、快速并有效处理大规模数据等诸多优点，成为最经典并应用最广泛的聚类方法之一[9]。算法中数据集数目是事先给定的，只有通过数据集的自动合并和分裂，才能得到较为合理的类型数目。初始聚类中心的选择对聚类结果有较大的影响，传统的Kmeans 算法随机选取初始聚类中心，算法容易陷入局部最优，并可能无法得到较好的聚类结果[10]。

本文提出了面向扫描阅卷系统的模板定制和图像聚类方法，通过模板定制对填涂区域属性和答题卡结构信息进行定义，基于模板信息采用Kmeans改进算法进行客观题涂写框图像聚类，初始聚类中心根据局部聚集密度最大数据点而确定，并对每张答题卡单独进行图像分类操作，从而得到很好的客观题判定结果，对高效准确地智能阅卷提供了很好的解决方案。

2扫描阅卷系统的模板定制

采用人机交互方式进行扫描阅卷系统的模板定制，模板定制的主要任务是定义填涂区域，每个填涂区域定义为一个矩形框，填涂的信息主要包括ID、中心位置X和Y、高、宽、题目标签、涂写值、组名、组顺序。在扫描阅卷时，根据中心位置X和Y、高、宽属性进行有效填涂信息的获取，根据题目标签、涂写值、组名、组顺序属性判断本填涂框是答题区域还是附加信息区域，并获得试卷的结构信息。填涂区域定义还包括其编辑功能，如填涂框的复制、删除、阵列、对齐、均布、属性的自动填充等。endprint

本文利用VC++和MS SQL Server2000作为基本的软件开发工具，开发了模板制作器，用于答题卡模板文件的制作和管理，实现了手工修正答题卡。模板制作器的界面友好并方便操作，在每次不同类型和不同阅卷需求的试卷批量阅卷之前，只需一次性定制模板并将模板存入数据库中，即可用于后续的扫描阅卷工作。模板定制界面和涂写框属性定义界面分别如图1和图2所示。

3扫描阅卷系统的图像聚类方法

通过模板制作器灵活地定制试卷答题卡模板，定义客观题中的每个涂写框的属性，并为涂写框的填涂识别做好了数据准备。扫描阅卷系统在进行客观题阅卷时，利用标准的TWAIN协议与扫描仪通讯获取图像，并将每张试卷被扫描成一个图片，采用Kmeans改进算法进行客观题涂写框图像聚类，具体步骤和主要参数选择如下：

定义数据点并计算数据点间的距离

客观题中的每个涂写框作为一个数据点，计算每个涂写框中包括所有点的灰度平均值作为对应数据点的指标值。设N个数据点x1，x2，...xN的集合S=xiNi=1，，I1，I2，...IN为对应数据点的指标值，且Imin

4实验与讨论

本文利用VC++和MS SQL Server2000，开发了基于Kmeans改进算法的扫描阅卷系统，实现了有效识别涂写框及图像聚类功能，将每张试卷扫描并保存为一个图片文件，可以方便地进行答题卡的查询与复核，客观题扫面阅卷界面如图3所示。

本文对所开发的基于Kmeans改进算法的扫描阅卷系统进行了实验测试，测试系统运行在Intel i7-7500U处理器、8 GB DDR4内存和128GB SSD+1.0TB硬盘，操作系统为Windows 10的主机上，并采用DR2020U扫描仪进行答题卡扫描。测试时统计的客观题填涂识别的平均速度是每分钟60～75张。对同一个测试样本（单项选择题）分别采用统一阈值法、传统KMeans算法和KMeans改进算法对扫描阅卷系统的图像聚类进行测试。在统一阈值法中设置阈值Hb过滤掉背景灰度，像素点灰度小于Hb的点判定为已填涂点，否则为空白点；设置阈值Ht确定填涂面积程度，涂写框已填涂点的百分比大于Ht时判定为已填涂框，否则为空白涂写框；采用统一阈值法进行图像分类时，选取不同的阈值，阅卷的准确率不同，需要在测试过程中找到一个较优的阈值组。在传统KMeans算法中随机选取初始聚类中心，在KMeans改进算法中取局部聚集密度最大的两个涂写框作为初始聚类中心。

图4给出了选用不同图像聚类方法时的比较结果。如图4所示，扫描阅卷系统会用蓝框在图中标出每个填图区域，如果识别为有效填涂，则用红色勾选。测试结果表明，采用统一阈值法，当Hb和Ht分别是100和30%时，扫描阅卷系统判定第1、3和7题分别出现两个选择项；采用传统KMeans算法，由于随机选取初始聚类中心，较难得到较优的全局聚类结果，扫描阅卷系统判定第3题出现两个选择项；采用Kmeans改进算法时，由于选取了较优的初始聚类中心，因而可以得到较优的全局聚类结果，虽然有些涂写框的灰度值很接近，但扫描阅卷系统能正确识别所有涂写框的填涂情况。由此可见，统一阈值法和传统的Kmeans 算法进行客观题阅卷的准确率较低，而采用Kmeans改进算法进行扫描阅卷系统的客观题图像聚类时，对未擦除干净或填涂深浅不一引起的误判率明显降低，能取得较高的客观题阅卷的准确率。

5结束语

为了解决试题答题卡的多样性和答题卡图像识别误判率偏高的问题，本文提出了基于模板定制和Kmeans改进算法的扫描阅卷系统。选用模板定制器定义填涂区域属性和答题卡结构信息，便于涂写框的填涂识别，并采用Kmeans改进算法进行客观题涂写框图像聚类，选取两个局部聚集密度最大数据点作为初始聚类中心，对每张答题卡单独进行涂写框分类，能够屏蔽不同答题卡图像之间的个体差异，从而得到较好的聚类结果。实验测试证明，与统一阈值法和传统KMeans算法相比较，KMeans改进算法能够得到更好的阅卷准确率，具有较好的实用性。

参考文献

[1]翟长波.光标阅读机OMR 原理的设计与实现[J].工业控制计算机，2010，23 （4） ：61-62.

[2]王紅玉.基于网上阅卷的OMR 扫描图像识别系统的设计与实现[D].武汉：武汉理工大学，2007.

[3]杨青燕子.基于灰度图像的答题卡识别技术[J].山东科技大学学报：自然科学版，2009，28（3） ：99-102.

[4]RUSHTON V，HIRSCHMAMM P，BEARN D.The effectiveness of undergraduate teaching of the identification of radiographic film faults [J].Dentomaxillofacial Radiology，2014，34（6）：225-232.

[5]吕鸣，陈志平.提高自学考试答题卡识别准确率的探讨及实践[J].中国考试，2011，5：38-41.

[6]陈浩鹏.基于图像识别的移动端阅卷系统的研究与实现 [D].广州：中山大学，2014.

[7]徐金伟.基于高拍仪的自动阅卷系统的设计与实现[D].北京：华北电力大学，2013.

[8]吴柏雄.摄像头阅卷系统关键技术的分析与应用[J].计算机系统应用，2010，19（2）：147-151.

[9]吴夙慧，成颖，郑彦宁，等.K_means算法研究综述.现代图书情报技术.2011，205 （5）：28-35.

[10]KHAN S S，AHMAD A.Cluster center initialization algorithm for KMeans clustering [J].Pattern Recognition Letters，2004，25（11）：1293-1302.endprint