手持終端自動閱卷的表格數據定位算法的研究

夏 禾,馮軍煥

(西南交通大學 信息科學技術學院，四川 成都 610031)

傳統的人工閱卷方式往往花費大量的人力物力和時間，效率低下，卻不能得到一個很好的效果。因此,采用一種高效準確的閱卷方式顯得尤為重要。參考文獻[1]提出了一種基于圖像識別的閱卷系統，這種閱卷系統需要對現有的常用答題卷格式進行改造，并且需要用掃描儀對學生的答題卷進行掃描，這勢必會增加考試閱卷的復雜度。近年來，帶有照相機功能的智能手機等移動終端快速增長且廣泛使用，為高效地自動智能閱卷提供了很好的解決方案。

本文利用帶有照相機功能的智能手機設計實現自動閱卷，教師只需將標準答案輸入Android智能手機中，然后對學生答題卷進行拍照，如圖1所示，通過手機閱卷軟件便可以輕松得到學生客觀題的考試成績。這種閱卷方式可以降低人工評卷誤差，減少教師閱卷工作量。

1 智能手機自動閱卷系統設計

各類考試的試卷中一般都會包括客觀題部分，大多數考試答題卷的客觀題部分都是由表格設計構成的。本文重點介紹系統在Android平臺下識別表格圖像，實現智能手機自動閱卷功能，具體流程如圖2所示。

圖1 學生答題卷

圖2 手機自動閱卷流程

1.1 圖像采集

與掃描儀獲取圖像資源相比，采用智能手機中的照相機獲取圖片的方式具有方便、快捷、應用一體化等特點。通過Android操作系統自帶的照相機進行圖像采集，并將采集到的圖像存儲到SD卡中等待后臺應用程序進行處理。

1.2 圖像預處理

照相機獲取的圖片攜帶了顏色特征，所以首先需要對圖像進行二值化操作。除此之外，為了取得更好的字符定位效果和字符識別精度，還需要對圖像進行傾斜校正等操作。

1.2.1 圖像二值化

由于文檔圖片的顏色特征比較單一，因此本文采用參考文獻[2]提出的基于簡單閾值的Ridler和Calvard的聚類算法，取得了較好的二值化效果。

1.2.2 圖像的傾斜校正

答題卷在被照相機拍照的過程中，或多或少都會存在一定的傾斜。傾斜會給字符的分割和識別帶來很大的影響,所以處理表格圖像很關鍵的一步是圖像的傾斜校正。

[3]可知，傳統的校正方法可通過Hough變化求出水平線的角度后，采用仿射變換調節圖像的角度。該方法因為采用了Hough變化，需要耗費大量的時間。參考文獻[4]提出了一種基于縱坐標投影峰值的表格圖像傾斜調整算法，通過計算峰值之間的距離來度量表格的傾斜度。本文采用這種方法來進行傾斜矯正，該方法適用于帶有表格信息的二值圖像，其算法計算量較小，在實際中有一定的使用價值。

1.3 表格數據定位與拆分

往往一張答題卷分為多個部分，而客觀題部分只是其中一個模塊，所以表格數據定位拆分模塊主要負責表格邊框的定位，并且有效地對表格中的數據進行拆分。

1.4 表格數據識別

答題卷的客觀題部分一般主要由答題序號 (也就是印刷體數字)和答案(手寫體 A、B、C、D)構成。在進行數字和字符識別之前，通過參考文獻[4]提供的方法可以使每個字符邊緣沒有空白區域，如圖3所示。

圖3 字符預處理后

1.4.1 手寫字符特征提取算法

字符特征提取的好壞直接影響著最終的識別效果。參考文獻[5]提供了一些字符的特征提取應遵循的規則。參考文獻[6]提出了一種針對手寫數字適應性較強的模板法——13點特征提取法，該方法具有實時、快速和準確等特點，但是該方法遇到大小不一的圖片時就會難以識別。在此基礎上，本文采用此方法歸一化的結果來提取特征以適用于手寫英文字符的識別。

1.4.2 手寫體字符的識別

本文采用模板匹配進行字符識別，將標準的書寫方式作為模板錄入模板庫中，利用圖像之間的最短距離作為判別函數。對于一個待測試的樣本X=(a1,a2,…,an)T，計算X和訓練集中的某個樣本Xj(0＜j＜N,N為訓練集中樣本的個數)之間的距離循環求出待測樣本和。訓練集中各個已知樣本之間的距離為dj,比較所有的dj值，找出最小的d作為X所屬的訓練集類別。

2 表格數據定位算法優化

目前,表格框線檢測算法有很多種，如Hough變換算法、投影法和交叉點特征法等。這些算法在傳統的表格識別中都能運用于單一表格的拆分和框線的識別，但是對于表格外噪聲數據的抗干擾能力較差。本文結合了Hough變換算法與交叉點特征法，實現了一種基于區域生長的表格定位算法。

2.1 算法假設

(1)圖像中存在的表格是封閉的矩陣單元。

(2)圖像中的待識別區域只存在單一表格，不存在多個表格混合識別的情況。

(3)圖像中識別區域以外的數據應該與表格有一定的距離。

(4)圖像中表格數據的直線檢測允許出現斷線，但不允許出現整個表格完全斷裂。

2.2 算法設計

要對表格邊框進行定位，首先需要對表格線進行檢測。在答題卷中，經過傾斜校正后，常見的表格線分為水平橫線和垂直豎線兩種。

目前，Hough變換是在圖像中尋找直線的最佳方法。OpenCV提供了基本Hough變換和累計Hough變換[7]兩種Hough變換算法。設定一定閾值T，采用比較直線起點與終點的橫坐標與縱坐標來對線條進行分類。設一條直線l(x1,x2)起點為x1(i1,j1),終點為x2(i2,j2),則分類規則為：

提取表格邊線后，可以得到大量的橫線與豎線的線條集合，如圖4所示。可以看出這些集合不僅包含圖像中待識別的表格部分的線條,同時也包含表格外的線條。

圖4 通過Hough算法得到的直線集

2.3 算法描述

本文針對橫線集和豎線集中包含非目標區域的表格線的問題以及橫線集與豎線集斷線的問題，改進了表格框線檢測提取算法中的Hough變換算法和交叉點特征法[8],提出了一種基于區域生長的表格定位算法。算法具體流程如下。

(1)對傾斜校正過后的圖像表格線進行檢測，將檢測到的線條進行歸類，得到橫線集與豎線集。設橫線集為U1，豎線集為U2，通過與操作可以粗略得到交點集C，而最終需要得到的表格線外區域由4點集B構成。同時假設C中包含孤立交點為e。

(2)從C中選取4個相鄰交點作為R的起始節點或叫種子節點，如圖5(a)所示，區域應盡量小，且不包含其他交點，并且a與d和b與c形成橫線關系，a與b和c與d形成豎線關系。

(3)生長區域選定，擴充區域R進行生長，這樣可以填充掉斷線區域。選定閾值T，將R區域向4個方向擴充T個像素,如圖5(b)所示(T的選擇應該適中，選擇過大，會導致區域錯誤生長；選擇過小，區域不能正常生長)。

(4)迭代橫線集U1與豎線集U2中的線段，若線段L與生長區域相交，則R區域向線段L擴充直至L末端為止，形成新的R區域，返回步驟(3)進行新生長區域的選定；若不存在L與生長區域相交,則跳轉至步驟(5)。圖5(c)、圖5(d)、圖5(e)所示為表格生長區域的生長過程。

(5)對最終得到的R區域運用局部Hough算法，得到線段集合,線段集合將R區域分割開來形成最終的識別區域。將新生成的線段集合中的線段延長可以得到所有的交點，如圖 5(f)所示。

圖5 表格識別過程舉例

由區域算法的特性可知，如果選擇適當的閾值T,可以在生長過程中找到區域的邊界{m,n,o,p}，同時不會包含表格外的直線和交點e。

2.4 算法原理

(1)算法中，生長區域R由4個滿足一定條件的相鄰交叉點包圍的區域B向外擴充閾值T所構成。由于B為4個相鄰交叉點構成的區域，則R∩(U1∪U2)!=Ф，則必定可以選擇一條相交直線進行延伸。

(2)假如在延伸過程中,一條直線l與表格的其他直線之間存在斷線，但是斷裂距離小于T，則在生長過程中，必定有l∩Rn!=Ф(Rn為R的第N次生長結果)，生長區域R則可以沿該直線擴充。

(3)由于算法假設中整個表格不可能出現完全斷裂(這里完全斷裂是指小模塊與表格其他線段的最小距離大于T),因此通過線段連通性可以證明區域多次擴展后,最后的生長區域R在包含所有的表格區域后停止生長。

(4)由于假設中表格數據與表格外的數據之間存在一定的距離(假設距離大于T)，則最終的生長區域不包含表格外數據。

3 測試結果及分析

本文采用三星i9300作為測試平臺，Android 4.0.4的系統版本。本文采用OpenCV2(版本號為2.4.5)作為圖像處理的庫。

3.1 幾種常見定位算法的對比

對帶有表格外噪聲數據的考試試卷(如圖6所示)運用不同表格框線檢測算法進行表格數據定位。分別通過Hough變換表格框線檢測算法[8]、交點特征提取算法[9]、由鄭秀清等人提出的一種改進的自動表格框線檢測算法[10]和本文提出的基于區域生長的表格定位算法得到的結果如圖7所示。

圖6 帶有表格外噪聲數據的考試試卷

圖7 各種不同的表格框線檢測算法的測試結果

Hough變換檢查直線算法輸入原始圖片后，可以檢測到圖像中的所有直線。將這些直線中的橫線與豎線選擇出來，可以構成檢測結果，如圖7(a)所示。由結果可以看出，Hough算法得到的線段除表格框線外，還存在表格外的直線，利用算法得到的直線集很難區分出哪些是表格線，哪些是非表格線，因此很難對表格區域進行有效的定位。

交點特征提取算法將橫線與豎線的交點作為特征，通過交點可以大體描繪出表格區域。然而由于圖像采集中光線不均勻與圖像預處理的誤差，容易出現漏檢短框線的問題，從而會直接影響到交點的檢測，如圖7(b)中出現部分交點漏檢的情況。

鄭秀清等人提出的改進的自動表格框線檢測算法主要應用數學形態學來對表格框線進行處理，對表格線進行了斷點補償，很好地去除噪聲帶來的困擾，但是同樣不能過濾掉表格外的孤立交點，如圖7(c)所示。

通過區域定位算法則可以很好地進行斷線補償并且過濾掉表格區域以外的孤立交點，如圖7(d)所示，采用該方法可以得到表格數據的交點集，對表格數據進行有效的定位。

隨機選取20種常見的不同類型的表格型試卷，通過圖像采集得到80張圖片作為圖像庫，分別用不同方法進行答題區域的分割，結果如表1所示。對比結果表明，基于區域生長的表格定位算法在圖片較清晰、滿足算法假設條件的情況下有較高的定位準確率。

表1 幾種常見的表格定位算法的對比

3.2 常見答題卷的定位結果

由于考試科目的不同，答題卷的類型有所不同，客觀題的數量也有所不同。本文對不同格式的幾種試卷進行了測試。用Android手機采集其中兩種類型的試卷照片，經過圖像的二值化、圖像去噪、傾斜校正、Hough直線檢測和區域定位等算法后,可以得到有效的識別區域，如圖8所示。

圖8 學生答題卷區域定位結果

傳統的考試答題卷客觀題部分主要存在于表格中，針對這種答題卷，本文針對Android移動終端設計了一種高效易用的自動閱卷方案，包括圖像的采集、預處理、表格圖像的識別和字符識別等。針對表格圖像定位與手寫字符識別算法進行了優化，實驗結果表明，該自動閱卷方案具有高效、簡單易用、便于推廣的優點。

參考文獻

[1]張站,劉政怡.基于圖像識別的閱卷系統的設計與實現[J].微型機與應用,2011,30(4)：44-47.

[2]RIDLER T W,CALVARD S.Picture thresholding using an iterative threshold selection method[J].IEEE Transactions on Systems,Man and Cybernetics,1978,8(8)：630-632.

[3]謝亮.表格識別預處理技術與表格字符提取算法的研究[D].廣州：中山大學,2005.

[4]巨志勇,鄭應平.二值表格圖像傾斜校正算法[C].第一屆中國高校通信類院系學術研討會論文集,2007.

[5]許雁飛,陳春玲,陳夏梅.基于 OpenCV的脫機手寫字符識別技術[J].信息與電腦(理論版),2011(8)：39.

[6]鐘樂海,胡偉.手寫體數字識別系統中一種新的特征提取方法[J].四川大學學報 (自然 科 學 版),2007(5)：15.

[7]KIRYATI N,ELDAR Y,BRUCKSTEIN A M.A probabilistic Hough transform[J].Pattern Recognition,1991,24(4)：303-316.

[8]ILLINGWORTH J,KITTLER J.A survey of the Hough transform[J].Computer Vision,Graphics,and Image Processing,1988,44(1)：87-116.

[9]WENYIN L,DORI D.From raster to vectors：extracting visual information from line drawings[J].Pattern Analysis&Applications,1999,2(1)：10-21.

[10]鄭秀清,付茂名.一種改進的自動表格框線檢測方法[J].中國民航飛行學院學報,2004,15(4)：30-32.