摘 要：本文綜合運(yùn)用圖像處理，模式識(shí)別的理論來構(gòu)建答題卡的識(shí)別系統(tǒng)。當(dāng)前使用的答題卡閱讀機(jī)，均采用光反射閱讀方式。要求使用指定的鉛筆，按嚴(yán)格的格式涂填。這與平時(shí)的習(xí)慣差距較大，容易發(fā)生人為失誤。這里，采用圖象處理和模式識(shí)別技術(shù)，對(duì)答題卡進(jìn)行閱讀，希望解決對(duì)書寫工具約束、需要特制答題卡等問題。實(shí)現(xiàn)了答題卡的計(jì)算機(jī)識(shí)別 ，采用打鉤的方法答題，方便，快速。

關(guān)鍵詞：灰度分割；夾線法；小波變換；霍夫變換；區(qū)域連通

針對(duì)答題卡的識(shí)別，光電識(shí)別技術(shù)已是應(yīng)用多年的成熟技術(shù)，在世界范圍內(nèi)廣泛使用，而基于影像模式的OMR識(shí)別技術(shù)，識(shí)別準(zhǔn)確率超過了傳統(tǒng)光標(biāo)OMR閱讀機(jī)，但是其兩者都對(duì)其填題方式進(jìn)行了限制，即應(yīng)用2B鉛筆填涂，超出答題區(qū)域在方框外答題的，答案無(wú)效，這很大程度上減慢了考生的填題時(shí)間，并都存在其誤率，如機(jī)械傳動(dòng)機(jī)構(gòu)復(fù)雜、使用壽命短、維護(hù)量大、設(shè)備一致性差、答題卡出現(xiàn)污點(diǎn)[1]等。

本文設(shè)計(jì)的系統(tǒng)支持考生使用任何深色筆做答，且最大程度上放寬了對(duì)填圖區(qū)域的限制，最大優(yōu)點(diǎn)在于考生可以使用劃鉤子或其他方式來選擇答案，系統(tǒng)采用圖像處理和模式識(shí)別技術(shù)來自動(dòng)識(shí)別答題卡信息，方便且快速。

1 系統(tǒng)設(shè)計(jì)流程

（一）讀取并顯示BMP圖象，讀取的BMP圖像如圖1所示。

圖1 原始答題卡

（二）運(yùn)用雙峰算法計(jì)算閾值，二值化圖象，二值化后的圖像如圖2所示。

圖2 二值化后的圖像

（三）運(yùn)用夾線法求水平與垂直的各投影線，處理后的圖像如圖3所示。

圖3 夾線法求水平與垂直的各投影線

（四）對(duì)圖象進(jìn)行水平與垂直投影，小波變換求投影線中點(diǎn)坐標(biāo)，處理后的圖像如圖4所示。

圖4小波變換求投影線中點(diǎn)坐標(biāo)

（五）根據(jù)色調(diào)的不同，二值化提取鉤子，處理后的圖像如圖5所示。

圖5二值化提取鉤子

（六）識(shí)別圖像得到結(jié)果圖，如圖6所示。

圖6輸出結(jié)果圖

2 系統(tǒng)主要實(shí)現(xiàn)技術(shù)

（一）求水平和垂直投影線算法的實(shí)現(xiàn)

用兩條間距較小的水平夾線平移至線條兩端，橫向掃描兩條直線間的象素點(diǎn)，記錄每水平行象素點(diǎn)的個(gè)數(shù)，如果大于一定的值，則其為一直線，取其中一條象素點(diǎn)最多的作為水平投影線。這里采用visual c++編碼實(shí)現(xiàn)[5]，具體實(shí)現(xiàn)代碼省略。

（二）閾值確定算法的實(shí)現(xiàn)

圖象的二值化需要一個(gè)閾值，先對(duì)圖象進(jìn)行縱向掃描，利用雙峰算法找到圖象中線條部分與空白部分的一系列中心坐標(biāo)，對(duì)各自的一系列中心坐標(biāo)點(diǎn)的灰度進(jìn)行最大概率值計(jì)算，取各自概率最大的值的平均值，以此值作為閾值，二值化圖象。

（三）Hough變換算法的實(shí)現(xiàn)

Hough變換的應(yīng)用可用如下的方法實(shí)現(xiàn)：

在（x，y）域中每一離散數(shù)據(jù)點(diǎn)變換為域中的曲線。將和分成許多小段，每一個(gè)小段和每個(gè)小段構(gòu)成一個(gè)小單元。對(duì)應(yīng)于每一個(gè)小單元可設(shè)一累加器（可定義一個(gè)二維數(shù)組Accumulator）。在（x，y）域中可能落在直線上的每一點(diǎn)對(duì)應(yīng)于變換域中一條曲線。分別使等于0，，2，3…，便可求出相應(yīng)的值，并分別計(jì)算落在各個(gè)小單元的次數(shù)，待全部的（x，y）域內(nèi)數(shù)據(jù)點(diǎn)變換完后，可對(duì)小單元進(jìn)行檢測(cè)，這樣，落入次數(shù)最多的單元（也就是求二維數(shù)組Accumulator元素的最大值），說明此點(diǎn)為較多曲線的公共點(diǎn)，而這些曲線對(duì)應(yīng)的（x，y）平面上的點(diǎn)可以認(rèn)為是共線的。檢測(cè)出（x，y）平面上n點(diǎn)后，將曲線交點(diǎn)坐標(biāo)，便可得到逼近n點(diǎn)的直線方程。

Hough變換的一個(gè)最大的優(yōu)點(diǎn)[2-3]就是其抑制噪聲的能力強(qiáng)，它能夠提取處在噪聲背景中的直線，并且能夠把斷了的線段連接起。

（四）連續(xù)小波變換的計(jì)算機(jī)實(shí)現(xiàn)

采用連續(xù)小波函數(shù)Marr小波，就可以根據(jù)連續(xù)小波變換的卷積定義對(duì)信號(hào)進(jìn)行運(yùn)算。計(jì)算機(jī)采集實(shí)際波形信號(hào)時(shí)必須以一定的時(shí)間間隔采樣數(shù)據(jù)，只要這個(gè)時(shí)間間隔滿足先農(nóng)采樣定理，就可以完全反映連續(xù)信號(hào)的全部信息[4]。鑒于計(jì)算機(jī)離散采樣的特點(diǎn)，在算法實(shí)現(xiàn)上必須考慮這一特點(diǎn)，即要按照數(shù)字信號(hào)處理的方法實(shí)現(xiàn)連續(xù)信號(hào)的處理，采用連續(xù)小波變換的離散化形式進(jìn)行計(jì)算。

借鑒Mallat的定義方法，直接按卷積來定義小波變換，與之不同的是，我們?nèi)匀徊捎脷w一化系數(shù)，而不是Mallat定義的：

由于選取的Marr小波是關(guān)于t=0對(duì)稱的，即，因此

時(shí)移因子b的實(shí)際意義是平行移動(dòng)，當(dāng)時(shí)移因子b>0時(shí)，沿橫向坐標(biāo)軸右移，否則向相反方向移動(dòng)。因此，我們可以將上式改寫成以下形式，而不會(huì)改變小波變換的實(shí)際意義。

（1）

尺度a的選擇可以根據(jù)需要直接調(diào)整，計(jì)算是直接依賴于最原始的。Marr小波函數(shù)的系數(shù)只是影響波形的幅值，其有無(wú)不會(huì)使波形失真，因此選取的小波基函數(shù)為：

（2）

可以近似地認(rèn)為其支集為[-7，7]，在這個(gè)區(qū)間以外，Marr小波基本為0。由于涉及到指數(shù)函數(shù)的計(jì)算，我們采用插值的技術(shù)來計(jì)算Marr小波的近似值，即預(yù)先計(jì)算好從[0，7]的每隔0.05的值共141點(diǎn)（在程序初始化或某個(gè)類的構(gòu)造中如此選定），然后通過普通的插值來實(shí)現(xiàn)小波基函數(shù)的計(jì)算。又由于該小波基函數(shù)的對(duì)稱性，可以得到自變量小于0的各個(gè)函數(shù)值。求解Marr小波函數(shù)的具體算法如下：

由于Marr小波函數(shù)的對(duì)稱性，我們只離散化采樣其非負(fù)時(shí)間軸的值，并且認(rèn)為時(shí)Marr小波值為0。采樣時(shí)間為取采樣時(shí)間間隔（采樣步長(zhǎng)）為0.05，由式（2），Marr小波離散化采樣值為：

（3）

當(dāng)Marr小波時(shí)間變量time不是0.05的整數(shù)倍時(shí)，需要用插值計(jì)算法求出。在此之前，要考慮time<0的情況。由于Marr小波是關(guān)于t=0對(duì)稱的，可作如下變換：

time= -time，time<0（4）

此時(shí)無(wú)論原始時(shí)間變量是否為正，time都已轉(zhuǎn)換成非負(fù)值。進(jìn)一步：

（5）

設(shè)int[x]表示取的整數(shù)部分，引入整數(shù)變量：

（6）

此時(shí)，就可以用插值法完成對(duì)各個(gè)具體點(diǎn)的Marr小波函數(shù)值wave（time）的求?。?/p>

（7）

下面敘述如何用計(jì)算機(jī)實(shí)現(xiàn)式（1）定義的連續(xù)小波變換。采用最簡(jiǎn)單的數(shù)值積分方法—矩形法，也就是按照數(shù)字信號(hào)處理的習(xí)慣將式（1）按時(shí)間，時(shí)移因子作處理：

其中，是采樣時(shí)間間隔，取，則：

其中f（j.dt），是待分析信號(hào)按照采樣時(shí)間間隔連續(xù)采集的數(shù)據(jù)，設(shè)存放于數(shù)組tp[j]中，將式（3）～（7）求出的小波函數(shù)的離散化形式帶入，得出：

（8）

上述小波變換結(jié)果存放在數(shù)組中，即：

（9）

（五） 區(qū)域填充的掃描線算法的實(shí)現(xiàn)

區(qū)域填充可以使用遞歸算法實(shí)現(xiàn)，其原理和程序都很簡(jiǎn)單，但由于多次遞歸，費(fèi)時(shí)、費(fèi)內(nèi)存，效率不高。為了減少遞歸次數(shù)，提高效率可以采用采用掃描線算法。

算法的基本過程如下：當(dāng)給定種子點(diǎn)（x，y）時(shí)，首先填充種子點(diǎn)所在掃描線上的位于給定區(qū)域的一個(gè)區(qū)段，然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復(fù)這個(gè)過程，直到填充結(jié)束。

區(qū)域填充的掃描線算法可由下列四個(gè)步驟實(shí)現(xiàn)：

（1）初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。

（2）出棧：若棧空則結(jié)束。否則取棧頂元素（x，y），以y作為當(dāng)前掃描線。

（3）填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xl和xr。

（4）確定新的種子點(diǎn)：在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（2）步。

上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；而在遞歸算法中，每個(gè)象素都需要壓棧。因此，掃描線填充算法提高了區(qū)域填充的效率。

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)采用數(shù)碼相機(jī)拍攝答題卡圖像，進(jìn)行圖像預(yù)處理、答題卡的標(biāo)定位置識(shí)別，答題卡的涂填處識(shí)別，判定矩形框中有無(wú)字符、是什么字符，最后對(duì)答題卡信息分析和統(tǒng)計(jì)。實(shí)驗(yàn)采用80份試卷作為樣本，對(duì)12份試卷進(jìn)行測(cè)試，結(jié)果識(shí)別率達(dá)到100%。

4 結(jié)論

本文采用圖象處理和模式識(shí)別技術(shù)，對(duì)答題卡進(jìn)行閱讀。在實(shí)驗(yàn)中以深色筆對(duì)答題卡進(jìn)行勾選，經(jīng)過數(shù)碼相機(jī)拍攝答題卡，采集樣本，進(jìn)行答題卡的自動(dòng)識(shí)別。實(shí)驗(yàn)表明識(shí)別率達(dá)到100%，解決了對(duì)書寫工具約束、采用打鉤的方法答題，方便，快速。

參考文獻(xiàn)

[1]吳元君，張婷，雷驚鵬.一種改進(jìn)的OMR 技術(shù)在標(biāo)準(zhǔn)化考試中的應(yīng)用[J].計(jì)算機(jī)教育，2007（13）：250-272.

[2] 龐東虎，金偉杰.英文字符特征提取系統(tǒng)[J].計(jì)算機(jī)仿真，2007，24（12）：208-210.

[3] 楊玲，毛以芳，吳天愛.基于多特征多分類器的脫機(jī)手寫漢字識(shí)別研究[J].計(jì)算機(jī)與網(wǎng)絡(luò)，2008（01）：217-217.

[4] 覃勝，劉曉明.基于圖像的OMR技術(shù)的實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2003，29（10）：17-19.

[5] 何斌，《Visual C++數(shù)字圖象處理》[M]，人民郵電出版社，2002-4

作者簡(jiǎn)介

陳偉華（1977-），湖北襄樊， 講師， 碩士，主要研究方向：計(jì)算機(jī)教學(xué)與.net項(xiàng)目開發(fā)。