一種適用于移動設(shè)備在線閱卷的答題卡自動識別算法

， ，，，

(西南科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,四川 綿陽 621010 )

0 引言

答題卡主要用于內(nèi)容選項較多的考試中。常見的答題卡自動閱卷系統(tǒng)主要有光標(biāo)閱讀機[1]、掃描儀閱卷系統(tǒng)[2]和攝像頭閱卷系統(tǒng)[3]。這幾種常用的閱卷系統(tǒng)雖已達到了識別速度快、效率高，但工作時卻受設(shè)備的硬件條件所限，主要在PC或嵌入式端操作，使得辦公不夠靈活，且存在價格高昂、對紙張質(zhì)量和印刷的要求高等缺點。因此，它們主要被應(yīng)用在中高考、研究生考試、公務(wù)員考試等一些大型的正式考試場合中。然而對于像學(xué)校日常的隨堂測驗，英語四六級、會計資格證、銀行從業(yè)資格證等培訓(xùn)考試，這些需要用到答題卡的非正式考試場合，單位或人們更傾向于以一種低廉、簡單、便捷的操作方式來進行閱卷。移動互聯(lián)網(wǎng)的高速發(fā)展使得智能手機、智能平板電腦等移動設(shè)備越來越普及，在國家教育信息化的推行進程中，移動教育方式不斷地受到關(guān)注。在此背景下，出現(xiàn)了許多基于移動端的答題卡自動識別系統(tǒng)[4-5]。

目前基于PC端或是基于移動端的答題卡自動識別系統(tǒng)，大部分是獨立開發(fā)的，程序高度定制化，因而限制了其普遍適用性，相應(yīng)地增加了開發(fā)周期和成本。在實際使用時，由于個體間差異較大，答題卡填涂時可能出現(xiàn)填涂大小和深淺不一致、擦除不干凈等情況，進行采集識別時，不同的光照、擺放位置會造成采集的圖像出現(xiàn)陰影、反光、傾斜等問題，這些會相應(yīng)的增大識別難度。

為解決以上問題，本文設(shè)計研究一套識別率高、實時性強、能兼容適應(yīng)不同采集設(shè)備的答題卡識別算法。PC機可利用外接攝像頭，進行圖像采集，隨后通過計算機軟件識別答題卡，這種方式主要應(yīng)用在辦公室閱卷。移動設(shè)備普遍具有較高分辨率的相機，利用其采集答題卡圖像，然后在App上進行識別，這種方式便捷、高效、成本低，適合于移動辦公，能夠配合基于移動設(shè)備的教育軟件一起使用，具有較大的應(yīng)用價值和發(fā)展前景。

1 答題卡設(shè)計

答題卡要求識別正確率達到100%，因為一旦出現(xiàn)識別錯誤，將直接影響考生本場考試成績。考慮成本要求，在答題卡紙質(zhì)質(zhì)量和印刷方式方面要求不嚴(yán)格，支持普通紙60 g以上的打印、復(fù)印等方式的制作答題卡。針對以上需求，標(biāo)準(zhǔn)答題卡模板設(shè)計如圖1所示，四周采用方框做邊界標(biāo)定，相比傳統(tǒng)采用原點作為標(biāo)記點，在外觀上更簡潔大方。

答題卡主要包括兩大部分：個人信息區(qū)和答題區(qū)。個人信息區(qū)內(nèi)容為身份證號和試卷號(由數(shù)字+“X”構(gòu)成)，在手寫體識別中，由于個體間差異較大，書寫習(xí)慣不同，導(dǎo)致識別率不能得到保證。因此，為達到識別正確率高的目標(biāo)，設(shè)計如下數(shù)字填涂方格(1...9)與(X)，以小圓點作為標(biāo)記，引導(dǎo)考生做如下書寫：0123456789X。答題區(qū)每道題有A、B、C、D四個選項，每個選項之間的間隔相等，行之間的行間距相同，每行的行高也完全一致(可增加題量)。

圖1 答題卡模板

2 答題卡圖像處理與識別過程

針對答題卡圖像特點，設(shè)計算法流程圖如圖2所示。

圖2 算法設(shè)計流程圖

1)答題卡預(yù)處理：主要包括對圖像降噪、去陰影、灰度拉伸、二值化、形態(tài)學(xué)等處理，去除圖像采集過程中受到的一些外在因素影響。

2)待識別區(qū)域定位：根據(jù)預(yù)處理后的圖像特點，建立幾何映射關(guān)系，變換得到模型參數(shù)矩陣，并結(jié)合插值算法校正圖像。

3)答題卡內(nèi)容識別：對校正后的答題卡圖像，①定位分割填涂項，結(jié)合填涂點灰度、面積等屬性設(shè)計算法，進行識別；②定位分割數(shù)字字符，做歸一化等預(yù)處理操作后，采用模板匹配結(jié)合結(jié)構(gòu)化特征的方法進行一一識別。

2.1 答題卡圖像預(yù)處理

在拍照過程中，受遮擋或光照不均勻等因素影響很容易在拍攝的圖像上產(chǎn)生陰影，若答題卡采用鉛筆填涂還容易出現(xiàn)反光現(xiàn)象。如圖3(a)所示，拍攝時造成了圖像右區(qū)域存在陰影，答題卡采用鉛筆填涂，在26～30題項區(qū)域出現(xiàn)反光現(xiàn)象，若直接采用自適應(yīng)閾值做二值化處理，會出現(xiàn)信息區(qū)域部分缺失，如圖3(b)所示，這樣會影響識別結(jié)果。因此，識別前應(yīng)對答題卡做預(yù)處理。分析答題卡圖像，發(fā)現(xiàn)答題卡內(nèi)容上表現(xiàn)出許多的細(xì)節(jié)信息，出現(xiàn)的陰影區(qū)域呈片型且亮度變化緩慢。一般情況下，線性濾波會給圖像的細(xì)節(jié)帶來模糊問題，這樣便可利用梯度濾波器來去除圖像中的陰影[6]，將陰影作為目標(biāo)，答題卡內(nèi)容作為背景，利用均值濾波器和背景差分法[7]，即可提取出陰影。設(shè)W(x,y)為大小為M×N，中心點在(x,y)處的均值濾波器窗口，Imean(x,y)為均值濾波后的圖像，I(u,v)為原始圖像，均值濾波器是計算濾波窗口內(nèi)的像素均值，并將其賦給窗口中心處的像素：

(1)

去除陰影后的圖像：

I′=255+Imean-I

(2)

去除陰影后的目標(biāo)圖像表現(xiàn)亮度不均，對比度較差，利用灰度拉伸延展整個灰度級范圍，使灰度變化具有分段性，圖像邊緣更清晰，從而改善圖像質(zhì)量。預(yù)處理效果如圖3(c)、(d)所示。

由于目前市面上的移動設(shè)備相機普遍具有較高的分辨率，獲得的目標(biāo)圖像數(shù)據(jù)量大，為節(jié)省設(shè)備存儲空間，獲得更高效的處理效率，系統(tǒng)研發(fā)時對采集的原始圖像按預(yù)設(shè)比例歸一化成標(biāo)準(zhǔn)規(guī)格圖像后，再執(zhí)行答題卡的識別過程。

圖3 預(yù)處理(去陰影、處理反光效果)

2.2 待識別區(qū)域定位分割

相機在拍照過程中，由于紙張擺放偏差或者相機未平行拍照都有可能使圖像產(chǎn)生旋轉(zhuǎn)或者傾斜，如圖3(a)所示。因此，需要對答題卡圖像是否發(fā)生形變進行檢測，同時進行相應(yīng)的校正處理。答題卡是由方框作為邊界，具有突出的4個頂點，對獲得的輪廓圖像采用多邊形逼近方式定位出答題卡的角點坐標(biāo)位置，建立相應(yīng)地映射關(guān)系對圖像進行傾斜和透視校正。多邊形逼近[8]算法的基本思想是在獲得的輪廓上尋找最遠的兩個點連成線段，然后在輪廓上查找到該線段最遠的點，并將其添加到新輪廓，反復(fù)迭代，不斷添加新的點到結(jié)果中，最后得到逼近的多邊形頂點。定位到角點后，通過三角函數(shù)變換確定目標(biāo)圖像的傾斜角，采用透視變換的方式對圖像進行傾斜校正。透視變換通過將檢測得到的目標(biāo)圖像的四個定點坐標(biāo)(x1,y1),(x2,y2),(x3,y3),(x4,y4)和基準(zhǔn)答題卡的四個頂點坐標(biāo)(X1,Y1),(X2,Y2),(X3,Y3),(X4,Y4)之間建立線性坐標(biāo)映射關(guān)系，得到透視變換參數(shù)矩陣，其中a,b,c,d,e,f,m,l是透視變換的參數(shù)。

(3)

把上式記作：

B=A*V

(4)

由(4)式得：

V=A-1*B

(5)

求解以上線性方程組得到參數(shù)值，將目標(biāo)圖像的每個像素點，變換到新的坐標(biāo)點，完成圖像的校正。圖像校正過程中，像素坐標(biāo)實際為整數(shù)，變換后的圖像可能出現(xiàn)空隙，所以需要對變換后的目標(biāo)圖像進行插值運算。從理論上來講，雙線性插值[9]性能介于最近領(lǐng)域插值與三次卷積插值之間，若采用三次卷積插值，算法時間復(fù)雜度較高，對圖像處理速度太慢，而采用最近鄰域插值效果不佳。因此，針對答題卡特征表現(xiàn)較為單一的特點，采用雙線性插值的方法來使圖像信息更接近原圖。結(jié)果如圖4所示。

圖4 拍攝角度校正效果

對校正后的答題卡圖像利用連通域、正交投影定位分割得到答題區(qū)域及個人信息標(biāo)識區(qū)域。

2.3 答題區(qū)識別

實際考試過程中，由于考生差異化填涂(例如：用筆不同、填涂大小和深淺不一致等)，這些都有可能影響識別結(jié)果。為避免上述情況，對分割得到的答題區(qū)圖像，做形態(tài)學(xué)處理，采用自適應(yīng)閾值進行二值化，然后根據(jù)填涂點灰度、面積及所處位置作為評價指標(biāo)，轉(zhuǎn)化得到選項答案。算法使用水平和垂直投影的方式，確定答題區(qū)每組題目之間的距離，題間距離及選項距離。利用相互之間的距離特性，對答題卡客觀題區(qū)域劃分網(wǎng)格，每個網(wǎng)格對應(yīng)題的選項答案(A,B,C,D)位置或者題號(1,2,3等)位置，存儲并記錄網(wǎng)格所代表的信息，及每道選擇題所對應(yīng)的答案位置。然后提取答題卡填涂區(qū)域的質(zhì)心，按其所處位置轉(zhuǎn)化為選項答案。同時計算該區(qū)域像素的平均灰度值及區(qū)域面積，進行有效填涂判定。最后，對以上結(jié)果進行綜合判定，確定選項答案。該方法也適用于多選題。

圖5 選擇題識別

2.4 個人信息識別

目前字符模式識別方法大致可分為統(tǒng)計模式識別[10]、結(jié)構(gòu)模式識別和人工神經(jīng)網(wǎng)絡(luò)[11-12]等。模板匹配[13]是統(tǒng)計模式識別方法中常用方法之一，將待識別數(shù)字與預(yù)先準(zhǔn)備好標(biāo)準(zhǔn)模板進行匹配，根據(jù)匹配相似度確定當(dāng)前識別結(jié)果。結(jié)構(gòu)模式識別通過尋找字符本身特征，譬如橫線、豎線、連通區(qū)域等來判定當(dāng)前識別內(nèi)容。神經(jīng)網(wǎng)絡(luò)通過對大量數(shù)據(jù)樣本進行訓(xùn)練學(xué)習(xí)，得到每類樣本的特征表示，進而分類識別。

由于神經(jīng)網(wǎng)絡(luò)識別方法，參數(shù)較多計算復(fù)雜度較高，訓(xùn)練過程需要有標(biāo)簽的龐大數(shù)據(jù)集且會花費大量時間。因此，采用模板匹配結(jié)合結(jié)構(gòu)化特征的方法對書寫結(jié)果進行識別。識別過程如圖6所示。

圖6 數(shù)字識別原理框圖

首先依據(jù)設(shè)計的數(shù)字填涂方格中標(biāo)記原點的位置關(guān)系設(shè)計如下模板圖像(尺寸大小22×34)：

圖7 字符模板圖像

歸一化輸入圖像大小，使其與模板圖像尺寸相同。然后計算模板與待識別圖片的Hausdorff距離作為相似性判斷，同時計算輸入圖像的結(jié)構(gòu)化特征。最后組合判定得到識別結(jié)果。

2.4.1 Hausdorff距離

Hausdorff距離是用來描述兩個實體之間相似性的一種度量方式，因平移、旋轉(zhuǎn)、縮放等變換對其影響較小，而受到廣泛運用[14]。假設(shè)有兩個點集A={a1，... ，an}，B={b1，... ，bn}，定義A、B點集合之間的hausdorff距離為:

H(A,B)=max(h(A,B),h(B,A))

(6)

其中:

(7)

(8)

2.4.2 結(jié)構(gòu)化特征

分析填涂數(shù)字的特征，可通過數(shù)字的孔洞質(zhì)心位置、歐拉數(shù)(歐拉數(shù)=連通域數(shù)-孔數(shù))、橫線、豎線(利用水平投影、垂直投影計算)來區(qū)分部分?jǐn)?shù)字,見表1。

歐拉數(shù)：用于將數(shù)字分為3類：{0，6，9}，{8}，{1，2，3，4，5，7，X}；

孔洞質(zhì)心位置：用于區(qū)分{0}，{6}，{9}；

橫線、豎線：用于區(qū)分{1}，{3}，{4}，{7}，{X}。

表1 各數(shù)字結(jié)構(gòu)特征

3 答題卡自動識別算法的實現(xiàn)

3.1 答題卡識別算法實現(xiàn)

跨平臺(Cross-platform)的應(yīng)用程序是指其在多種平臺下不改動或稍改動即可編譯運行[15-16]。本文跨平臺系統(tǒng)主要分為兩部分：答題卡自動識別算法庫和跨平臺實現(xiàn)。總體架構(gòu)如圖8所示。

圖8 跨平臺系統(tǒng)總體框架圖

答題卡自動識別算法的開發(fā)環(huán)境是VS2013+OpenCV3.0，利用C++語言編寫實現(xiàn)。C++語言具有很好的跨平臺性，面向?qū)ο缶幊踢m合處理像圖像這類具有復(fù)雜數(shù)據(jù)結(jié)構(gòu)的問題。OpenCV是一個跨平臺且開源的計算機視覺圖像處理算法庫，常用于商業(yè)和科研用途。在算法庫的基礎(chǔ)上實現(xiàn)跨平臺性，共包括PC平臺、Android平臺以及IOS平臺。Android平臺下，將原始算法庫封裝成符合JNI命名規(guī)范的so庫，并再次封裝為能直接使用的jar包，做成發(fā)布版Android SDK。IOS平臺下，由于Xcode支持 Object C 與C++的混編，因此可直接將算法庫編譯成靜態(tài)類庫供開發(fā)人員調(diào)用。

3.2 測試結(jié)果與分析

測試使用的答題卡模板均由6位試卷號、11位身份證號、50個選擇項組成。為驗證算法的跨平臺性，測試平臺選擇了基于IOS、Android系統(tǒng)的多種采集設(shè)備，分別采集了110張答題卡圖像。

表2 不同機型正常填涂測試結(jié)果

正常填涂采集(正確填涂，拍攝時答題卡方框區(qū)域拍攝完全，成像區(qū)域不能過小)圖像80張，測試結(jié)果如表2所示。正常填涂識別正確率為100%。不同操作系統(tǒng)下算法運行時間在2 s內(nèi)，運行時間主要與設(shè)備處理器和運行內(nèi)存有關(guān)，PC采用的是雙核處理器，運行時間較長。

異常填涂采集(答題卡的填涂大小、深淺、擦除不干凈等特殊情況，采集時不同的光照、擺放位置等情況)圖像30張，如圖9所示，這些會相應(yīng)的增大識別難度。經(jīng)測試，算法能有效處理拍照時出現(xiàn)的陰影、反光、傾斜(-45～45°)情況，異常填涂識別正確率為93.6%。不能識別√、×、Ο類填涂方式，及答題卡旋轉(zhuǎn)傾斜角度較大等情況。

圖9 不同條件下拍攝的圖片

4 總結(jié)

本文針對答題卡圖像采集時存在陰影、反光、傾斜等問題進行了研究，采用梯度濾波結(jié)合背景差分法的方式去除陰影。對預(yù)處理后的圖像，采用多邊形輪廓逼近的方式定位角點，進而進行傾斜校正等操作，為進一步識別做鋪墊。采用網(wǎng)格定位法對填涂區(qū)域信息進行定位，并結(jié)合填涂區(qū)域位置、面積及灰度等信息，形成評判體系，確定選項答案。對個人信息區(qū)利用模版匹配結(jié)合結(jié)構(gòu)化特征的方式，進行數(shù)字的提取識別。最后，根據(jù)跨平臺編程的思想，設(shè)計實現(xiàn)了一套能兼容不同系統(tǒng)下不同的采集設(shè)備，實際運用時識別速度快，準(zhǔn)確率高的答題卡自動識別算法。下一步將考慮復(fù)雜的拍攝背景，以及答題卡出現(xiàn)折皺做進一步研究。