掃描閱卷系統(tǒng)中模板定制和圖像聚類方法的研究

孫建芳　李萬秋　張國輝　李傲松

摘要：為了適應答題卡多樣化需求和提高答題卡圖像識別的準確率，提出了掃描閱卷系統(tǒng)中模板定制和圖像聚類方法。首先基于人機交互方式進行模板定制，定義填涂區(qū)域屬性和答題卡結構信息，并開發(fā)了模板制作器，實現答題卡模板文件的制作和管理；其次給出基于Kmeans改進算法的掃描閱卷系統(tǒng)中圖像聚類方法，選擇局部聚集密度最大的數據點作為初始聚類中心以得到全局較優(yōu)的聚類結果，并通過計算區(qū)分度進行聚類結果評價；最后基于VC++和MS SQL Server2000開發(fā)了基于Kmeans改進算法的掃描閱卷系統(tǒng)，并對該系統(tǒng)進行了實驗測試。測試結果表明，采用Kmeans改進算法進行掃描閱卷時能夠得到穩(wěn)定的圖像聚類結果，大大提高了客觀題閱卷準確率，具有較高的實用價值。

關鍵詞：掃描閱卷系統(tǒng)，模板定制，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引言

閱卷是考試中的一個重要環(huán)節(jié)，傳統(tǒng)機器閱卷需要光電閱卷機和專用機讀卡，雖然具有閱卷速度快和適合大規(guī)?？荚嚨膬?yōu)點，但只能采用專用答題卡進行掃描閱卷，存在產品價格高和無法靈活定制試卷答題模板等缺陷[1-3]。另外，掃描閱卷系統(tǒng)對圖像輸入設備采集答題卡圖像自動進行圖像處理和識別，其操作簡單且成本低廉，越來越得到廣泛應用[4，5]；但在掃描閱卷系統(tǒng)中由于掃描得到的圖像質量存在個體差異，填涂未擦除干凈或填涂深淺不一會增加客觀題的誤判率。因此，為了適應答題模板多樣化需求和提高掃描閱卷系統(tǒng)對答題卡圖像識別準確率，必須進行模板定制和對答題卡進行合理的圖像聚類。

目前掃描閱卷系統(tǒng)中采用統(tǒng)一閾值法進行圖像識別，其掃描閱卷的準確率有待進一步提高[6-8]?；趧澐值腒Means 算法以其簡單、快速并有效處理大規(guī)模數據等諸多優(yōu)點，成為最經典并應用最廣泛的聚類方法之一[9]。算法中數據集數目是事先給定的，只有通過數據集的自動合并和分裂，才能得到較為合理的類型數目。初始聚類中心的選擇對聚類結果有較大的影響，傳統(tǒng)的Kmeans 算法隨機選取初始聚類中心，算法容易陷入局部最優(yōu)，并可能無法得到較好的聚類結果[10]。

本文提出了面向掃描閱卷系統(tǒng)的模板定制和圖像聚類方法，通過模板定制對填涂區(qū)域屬性和答題卡結構信息進行定義，基于模板信息采用Kmeans改進算法進行客觀題涂寫框圖像聚類，初始聚類中心根據局部聚集密度最大數據點而確定，并對每張答題卡單獨進行圖像分類操作，從而得到很好的客觀題判定結果，對高效準確地智能閱卷提供了很好的解決方案。

2掃描閱卷系統(tǒng)的模板定制

采用人機交互方式進行掃描閱卷系統(tǒng)的模板定制，模板定制的主要任務是定義填涂區(qū)域，每個填涂區(qū)域定義為一個矩形框，填涂的信息主要包括ID、中心位置X和Y、高、寬、題目標簽、涂寫值、組名、組順序。在掃描閱卷時，根據中心位置X和Y、高、寬屬性進行有效填涂信息的獲取，根據題目標簽、涂寫值、組名、組順序屬性判斷本填涂框是答題區(qū)域還是附加信息區(qū)域，并獲得試卷的結構信息。填涂區(qū)域定義還包括其編輯功能，如填涂框的復制、刪除、陣列、對齊、均布、屬性的自動填充等。endprint

本文利用VC++和MS SQL Server2000作為基本的軟件開發(fā)工具，開發(fā)了模板制作器，用于答題卡模板文件的制作和管理，實現了手工修正答題卡。模板制作器的界面友好并方便操作，在每次不同類型和不同閱卷需求的試卷批量閱卷之前，只需一次性定制模板并將模板存入數據庫中，即可用于后續(xù)的掃描閱卷工作。模板定制界面和涂寫框屬性定義界面分別如圖1和圖2所示。

3掃描閱卷系統(tǒng)的圖像聚類方法

通過模板制作器靈活地定制試卷答題卡模板，定義客觀題中的每個涂寫框的屬性，并為涂寫框的填涂識別做好了數據準備。掃描閱卷系統(tǒng)在進行客觀題閱卷時，利用標準的TWAIN協(xié)議與掃描儀通訊獲取圖像，并將每張試卷被掃描成一個圖片，采用Kmeans改進算法進行客觀題涂寫框圖像聚類，具體步驟和主要參數選擇如下：

定義數據點并計算數據點間的距離

客觀題中的每個涂寫框作為一個數據點，計算每個涂寫框中包括所有點的灰度平均值作為對應數據點的指標值。設N個數據點x1，x2，...xN的集合S=xiNi=1，，I1，I2，...IN為對應數據點的指標值，且Imin

4實驗與討論

本文利用VC++和MS SQL Server2000，開發(fā)了基于Kmeans改進算法的掃描閱卷系統(tǒng)，實現了有效識別涂寫框及圖像聚類功能，將每張試卷掃描并保存為一個圖片文件，可以方便地進行答題卡的查詢與復核，客觀題掃面閱卷界面如圖3所示。

本文對所開發(fā)的基于Kmeans改進算法的掃描閱卷系統(tǒng)進行了實驗測試，測試系統(tǒng)運行在Intel i7-7500U處理器、8 GB DDR4內存和128GB SSD+1.0TB硬盤，操作系統(tǒng)為Windows 10的主機上，并采用DR2020U掃描儀進行答題卡掃描。測試時統(tǒng)計的客觀題填涂識別的平均速度是每分鐘60～75張。對同一個測試樣本（單項選擇題）分別采用統(tǒng)一閾值法、傳統(tǒng)KMeans算法和KMeans改進算法對掃描閱卷系統(tǒng)的圖像聚類進行測試。在統(tǒng)一閾值法中設置閾值Hb過濾掉背景灰度，像素點灰度小于Hb的點判定為已填涂點，否則為空白點；設置閾值Ht確定填涂面積程度，涂寫框已填涂點的百分比大于Ht時判定為已填涂框，否則為空白涂寫框；采用統(tǒng)一閾值法進行圖像分類時，選取不同的閾值，閱卷的準確率不同，需要在測試過程中找到一個較優(yōu)的閾值組。在傳統(tǒng)KMeans算法中隨機選取初始聚類中心，在KMeans改進算法中取局部聚集密度最大的兩個涂寫框作為初始聚類中心。

圖4給出了選用不同圖像聚類方法時的比較結果。如圖4所示，掃描閱卷系統(tǒng)會用藍框在圖中標出每個填圖區(qū)域，如果識別為有效填涂，則用紅色勾選。測試結果表明，采用統(tǒng)一閾值法，當Hb和Ht分別是100和30%時，掃描閱卷系統(tǒng)判定第1、3和7題分別出現兩個選擇項；采用傳統(tǒng)KMeans算法，由于隨機選取初始聚類中心，較難得到較優(yōu)的全局聚類結果，掃描閱卷系統(tǒng)判定第3題出現兩個選擇項；采用Kmeans改進算法時，由于選取了較優(yōu)的初始聚類中心，因而可以得到較優(yōu)的全局聚類結果，雖然有些涂寫框的灰度值很接近，但掃描閱卷系統(tǒng)能正確識別所有涂寫框的填涂情況。由此可見，統(tǒng)一閾值法和傳統(tǒng)的Kmeans 算法進行客觀題閱卷的準確率較低，而采用Kmeans改進算法進行掃描閱卷系統(tǒng)的客觀題圖像聚類時，對未擦除干凈或填涂深淺不一引起的誤判率明顯降低，能取得較高的客觀題閱卷的準確率。

5結束語

為了解決試題答題卡的多樣性和答題卡圖像識別誤判率偏高的問題，本文提出了基于模板定制和Kmeans改進算法的掃描閱卷系統(tǒng)。選用模板定制器定義填涂區(qū)域屬性和答題卡結構信息，便于涂寫框的填涂識別，并采用Kmeans改進算法進行客觀題涂寫框圖像聚類，選取兩個局部聚集密度最大數據點作為初始聚類中心，對每張答題卡單獨進行涂寫框分類，能夠屏蔽不同答題卡圖像之間的個體差異，從而得到較好的聚類結果。實驗測試證明，與統(tǒng)一閾值法和傳統(tǒng)KMeans算法相比較，KMeans改進算法能夠得到更好的閱卷準確率，具有較好的實用性。

參考文獻

[1]翟長波.光標閱讀機OMR 原理的設計與實現[J].工業(yè)控制計算機，2010，23 （4） ：61-62.

[2]王紅玉.基于網上閱卷的OMR 掃描圖像識別系統(tǒng)的設計與實現[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]陳浩鵬.基于圖像識別的移動端閱卷系統(tǒng)的研究與實現 [D].廣州：中山大學，2014.

[7]徐金偉.基于高拍儀的自動閱卷系統(tǒng)的設計與實現[D].北京：華北電力大學，2013.

[8]吳柏雄.攝像頭閱卷系統(tǒng)關鍵技術的分析與應用[J].計算機系統(tǒng)應用，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