孫建芳　李萬(wàn)秋　張國(guó)輝　李傲松

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

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

中圖分類(lèi)號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：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引言

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

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

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

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

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

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

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

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

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

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

4實(shí)驗(yàn)與討論

本文利用VC++和MS SQL Server2000，開(kāi)發(fā)了基于Kmeans改進(jìn)算法的掃描閱卷系統(tǒng)，實(shí)現(xiàn)了有效識(shí)別涂寫(xiě)框及圖像聚類(lèi)功能，將每張?jiān)嚲頀呙璨⒈４鏋橐粋€(gè)圖片文件，可以方便地進(jìn)行答題卡的查詢(xún)與復(fù)核，客觀(guān)題掃面閱卷界面如圖3所示。

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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