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

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

關(guān)鍵詞：掃描閱卷系統(tǒng)，模板定制，Kmeans改進(jìn)算法，圖像聚類

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

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

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

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

采用人機(jī)交互方式進(jìn)行掃描閱卷系統(tǒng)的模板定制，模板定制的主要任務(wù)是定義填涂區(qū)域，每個填涂區(qū)域定義為一個矩形框，填涂的信息主要包括ID、中心位置X和Y、高、寬、題目標(biāo)簽、涂寫值、組名、組順序。在掃描閱卷時，根據(jù)中心位置X和Y、高、寬屬性進(jìn)行有效填涂信息的獲取，根據(jù)題目標(biāo)簽、涂寫值、組名、組順序?qū)傩耘袛啾咎钔靠蚴谴痤}區(qū)域還是附加信息區(qū)域，并獲得試卷的結(jié)構(gòu)信息。填涂區(qū)域定義還包括其編輯功能，如填涂框的復(fù)制、刪除、陣列、對齊、均布、屬性的自動填充等。endprint

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

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

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

定義數(shù)據(jù)點并計算數(shù)據(jù)點間的距離

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

4實驗與討論

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

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

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

5結(jié)束語

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

參考文獻(xiàn)

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

[2]王紅玉.基于網(wǎng)上閱卷的OMR 掃描圖像識別系統(tǒng)的設(shè)計與實現(xiàn)[D].武漢：武漢理工大學(xué)，2007.

[3]楊青燕子.基于灰度圖像的答題卡識別技術(shù)[J].山東科技大學(xué)學(xué)報：自然科學(xué)版，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]呂鳴，陳志平.提高自學(xué)考試答題卡識別準(zhǔn)確率的探討及實踐[J].中國考試，2011，5：38-41.

[6]陳浩鵬.基于圖像識別的移動端閱卷系統(tǒng)的研究與實現(xiàn) [D].廣州：中山大學(xué)，2014.

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

[8]吳柏雄.攝像頭閱卷系統(tǒng)關(guān)鍵技術(shù)的分析與應(yīng)用[J].計算機(jī)系統(tǒng)應(yīng)用，2010，19（2）：147-151.

[9]吳夙慧，成穎，鄭彥寧，等.K_means算法研究綜述.現(xiàn)代圖書情報技術(shù).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