多模版匹配的特殊符號識別定位算法研究

曹長玉 鄭佳春 黃一琦

(集美大學廈門市海洋智能終端研發及應用重點實驗室 福建 廈門 361021)

0 引 言

傳統基于人工的試卷批改方式需花費教師大量的時間與精力，大大增加了教學負擔。為節約教師時間使其全身心投入到教學任務中，機器自動閱卷成為一個值得研究的課題。然而，手寫答案的精準定位是成功自動閱卷極其重要的關鍵技術，查閱大量文獻未見有相關報道，為此本文展開技術研究。

深度學習不但在檢測與高精度識別方面得到廣泛應用，而且在OCR領域中也占據主導地位。文獻[1]提出Faster R-CNN網絡模型，使用RPN(Region Proposal Networks)網絡生成目標候選框，替代了選擇搜索算法[2]，由分類定位網絡對候選框做分類與定位處理，取得較高的定位精度。文獻[2]提出R-FCN模型，采用卷積層替換Faster R-CNN網絡中的全連接層，構建位置敏感分布得分圖估計目標類別概率，解決了目標分類平移不變性與檢測平移變化的矛盾。文獻[3]提出基于回歸思想的單階段SSD(Single Shot MultiBox Detector)算法，引入SPPNet[4]特征金字塔檢測定位，實現不同尺寸目標的精準定位。文獻[5]提出基于回歸思想的YOLO算法，將圖像劃分為S×S個網格，每個網格負責檢測目標中心落入該網格內目標的位置及類別，定位速度快。文獻[6]提出CTPN(Connectionist Text Proposal Network)模型，檢測文本行中的單個字符，通過雙向長短時記憶循環神經網絡連接單個字符得到文本行信息。文獻[7]提出RRPN ( Rotation Region Proposal Networks)模型，在Faster R-CNN基礎上通過旋轉anchor框，實現傾斜字符的檢測。文獻[8]改進SSD算法得到TextBoxes模型，為匹配文本行呈長方形的特點，使用長方形的卷積核替換傳統正方形的卷積核；為降低網絡回歸的難度，使用長寬比較大的錨框，而后使用非極大值抑制算法過濾冗余的邊界框。文獻[9]提出SegLink模型，將文字檢測分為兩部分，一部分檢測文本行中的文字片段，另一部分預測文字片段之間的連接關系，最后通過深度優先搜索結合算法，把文字片段連接成完整的單詞或文本行。

上述深度學習的字符檢測，盡管取得較高的精度，但也存在幾個主要問題：首先，硬件要求高，低平臺計算速度慢耗時嚴重；其次，深度學習檢測需標注試卷中的符號，成千上萬張試卷收集困難且符號標注費時費力；最后，單個符號或文本行在試卷中所占面積比例極小，深度卷積提取特征時易忽略符號特征，不能正確定位試卷中的符號位置，進而無法獲取符號內答案。為此，根據符號之間的相似性，本文提出基于OCR[10]多模板匹配方法，該方法對硬件要求低，且多模板的建立具有保留覆蓋機制，可以對任意張試卷中的符號實現高精度定位，具有較好的通用性。本文將通過Tesseract-OCR符號定位問題，引出多模板匹配方法。

1 Tesseract-OCR符號定位

1.1 OCR定位流程

OCR識別原理主要包含文本檢測和文字識別兩大關鍵技術。首先，使用二值化、降噪、畸變校正和圖像增強等方式預處理輸入圖片；其次，分析預處理后圖片的版面信息，確定圖中文本的位置區域，逐行分割文本區域中的字符，提取字符特征送入分類器；最后，由分類器識別分割字符，再通過文本校正校訂識別字符確保識別結果的正確性，生成文本信息。如圖1所示。

圖1 定位流程

1.2 符號識別定位

學生作答試卷在空白區域留下的點、字跡會影響Tesseract-OCR識別定位效果，導致符號錯誤定位數量增多。因此，使用OCR定位空白試卷的符號，來消除學生字跡的影響，提高符號定位準確率。但由于OCR缺少特殊符號語言包，在本文所有實驗均使用中文包，符號識別定位如圖2所示。

圖2 符號識別定位

通過深度平滑預處理輸入的空白試卷，來消除空白黑點的干擾[11]；使用OCR對預處理后的試卷圖片按SYMBOL方式進行識別。根據識別結果可知，OCR識別出的字符包含漢字、數字和符號字符等，然而我們僅關心符號字符，故需要對每個識別字符做進一步的判斷篩選，來保留符號識別結果及坐標。分別設置圓圈、左括號、右括號、方塊判斷條件，若OCR識別字符置信度閾值大于80且滿足圓圈判斷條件，則將圓圈坐標保存于圓圈列表中，其他符號做類似處理。至此，即可得到符號在試卷中的位置坐標。每個自然段開始時縮進兩個漢字。

1.3 OCR符號定位問題

使用OCR識別定位小學二年級試卷中的符號發現以下問題：(1) 符號漏檢數量多，OCR自身缺少特殊符號語言包，使用中文包對特殊符號識別過程中易將符號認定為圖片而不產生識別，以致符號識別定位準確率較低。(2) OCR識別符號存在錯誤，OCR將圓圈符號(“○”)識別為括號的左半邊或右半邊(“(”，“)”)。在符號識別條件判斷時，圓圈符號坐標保存于括號列表中，致使圓圈定位產生漏檢，括號產生誤檢。(3) 在三種符號同行緊密排列，OCR字符檢測過程的切割算法無法做到精確切割，識別效果較差。OCR符號識別定位如圖3所示，鑒于識別定位存在的問題，單純使用OCR無法滿足準確定位的功能要求。

(a) 試卷正面定位局部效果圖

2 多模板匹配識別定位

模板匹配[12-13]即用模板圖像在測試圖片上進行滑動，計算模板在測試圖片上的覆蓋區域與模板的相似程度。若相似程度大于設定的閾值，則認為覆蓋區域與模板相匹配，以此得到符號在測試圖像中的位置。多模板匹配識別流程如圖4所示。

圖4 多模板匹配識別流程

為增強方法的通用性及識別定位的準確性，每張試卷中的每種符號需自動截取3～6幅子圖像作為模板，建立符號模板集；使用模板匹配判定方法，計算模板集中的模板與測試圖片的相似程度值，該值取值范圍為[0,1]，設定閾值過濾相似程度較小的符號；模板匹配過程中每種符號匹配出多個位置坐標，用式(1)非極大值抑制算法(Non-Maximum Suppression，NMS)[1]刪除重疊的坐標。

nms=(A∩B)÷(A∪B)

(1)

式中：A、B代表匹配出的位置坐標區域。

2.1 符號模板集建立

由于OCR能成功定位每張試卷中部分符號，因此可通過OCR建立各種符號的模板集。參考1.2節OCR識別定位方法來得到試卷中部分方塊、圓圈、左右括號位置坐標，利用二值圖對符號坐標進行判斷，進而截取各個符號的多幅不同類型的子圖像建立符號模板集，如圖5所示。

圖5 建立模板集

1) 輸入整張試卷做兩部分處理，一部分調用1.2節方法，獲得試卷中部分符號坐標；另一部分將試卷圖片轉為灰度圖，并通過式(2)對灰度圖做二值化處理。

(2)

式中：f(x,y)為灰度圖像在(x,y)處的像素值。

2) 方塊圓圈均為單邊符號建立模板集方法相同，以方塊為例。首先計算所有識別出的方塊的寬與高，根據經驗保存寬度介于60～100且高度大于65的方塊(圓圈保存寬度大于60且高度大于60)，并按寬從大到小順序排列，用式(3)在二值圖中判斷方塊坐標最右側區域是否為空白區域，依次截取寬度最大、寬度居中、寬度最小三幅子圖像作為模板,模板保存名分別為Fang3.jpg、Fang2.jpg、Fang1.jpg。

(3)

式中：x2、y3分別為符號右下角水平方向及垂直方向坐標；y1為左上角垂直方向坐標。若result=0，則坐標最右側為空白區域，利用方塊坐標從試卷圖像中截取方塊子圖像，建立模板，使用同名模板名覆蓋之前對應的模板；若result≠0，則為非空白區域，設置循環50次，方塊最右側每次向右移動一個像素點，再進行空白區域判斷，截取模板覆蓋此前遺留對應模板。若退出循環仍未截取模板，則此時該部使用遺留模板，避免了截取不到模板產生程序報錯問題。

3) 左右括號模板截取方法類似，以左括號為例。觀察發現試卷中存在中英文輸入法下輸入的多種括號類型，不同括號類型高度有所不同。為成功匹配多種括號類型，根據計算保留寬度20～35且高度大于40的括號，并按高度從大到小排列，左右括號各截取6幅長寬比不同的括號子圖像。用保留左括號的個數除以6得step，每隔step取左括號坐標。設選取的6個左括號高度為[h6,h5,h4,h3,h2,h1],設置6個比率[1.3,1.5,1.3,1.2,0.9,0.7]，則需將此6個左括號右下角水平方向坐標分別再向右延伸對應位置的[1.3×h6,1.5×h5,1.3×h4,1.1×h3,0.9×h2,0.7×h1]個像素點(右括號則將左上角水平方向坐標向左延伸)，在二值圖中判斷向右延伸的區域是否為空白區域。若為空白區域，則按調整后的坐標截取括號模板，使用同名模板名覆蓋之前對應模板；否則跳過，該位置使用遺留模板。

2.2 直線模板集

形態學濾波是重要的圖像處理操作，可以消除噪聲、連接斷點像素和分割圖像等，其中，腐蝕、膨脹、開運算與閉運算是最為常見的形態學運算。設背景色像素值為0，二值圖為F(x,y)，結構元素B(x′,y′)，形態學定義運算如下[14-15]：

腐蝕運算：結構元素B(x′,y′)對二值圖F(x,y)腐蝕運算表達式(FΘB)(x,y)如下：

(FΘB)(x,y)=min{F(x+x′,y+y′)-B(x′,y′)|

(x+x′,y+y′)∈DF,(x′,y′)∈DB}

(4)

膨脹運算：結構元素B(x′,y′)對二值圖F(x,y)膨脹運算表達式(F⊕B)(x,y)如下：

(F⊕B)(x,y)=max{F(x-x′,y-y′)+B(x′,y′)|

(x+x′,y+y′)∈DF,(x′,y′)∈DB}

(5)

式中：DF與DB分別是F(x,y)和B(x′,y′)的定義域。

開運算：結構元素B(x′,y′)對二值圖F(x,y)開運算表達式F°B如式(6)所示,經過開運算，可以除去二值圖中孤立的小點，使二值圖更加光滑。

F°B=(FΘB)⊕B

(6)

閉運算：結構元素B(x′,y′)對二值圖F(x,y)閉運算表達式F·B如式(7)所示，經過閉運算可以填平黑洞，連接斷點，使二值圖中目標更加完整。

F·B=(F⊕B)ΘB

(7)

輸入試卷經式(2)二值處理后，再經閉運算處理后得到新的二值圖src_img，使用findContours函數查找src_img目標輪廓。經實驗驗證，直線高度小于5、寬度大于70。因此，設置判斷條件，保留輪廓高度小于5、寬度大于70的輪廓坐標，此坐標即為試卷中直線位置所在。將直線按照寬度從大到小順序排列，用式(3)依次選取寬度最大、寬大居中、寬度最小三個直線子圖像建立直線模板集，使用同名模板名覆蓋保留上一步模板。

2.3 模板匹配判定方法

為減少計算負擔，輸入圖像與模板圖像在灰度圖[16]下，采用基于歸一化相關系數匹配法求輸入圖像與模板圖像庫的匹配程度，如式(8)所示，數值越大匹配度越高，結果越可靠。設置閾值為0.8，過濾較小的符號區域坐標。

(8)

式中：T(x′,y′)表示模板圖像(x′,y′)處的像素值；I(x′,y′)為待匹配圖像I(x+x′,y+y′)處像素值；I(x+x′,y+y′)為模板圖像在待匹配圖像(x,y)位置進行匹配。

3 實 驗

3.1 實驗環境及數據

本文所有實驗在Ubuntu 18.04系統進行，在Pycharm開發環境下使用Python 3.6編寫測試代碼，使用Inter Core i7-4790 CPU@3.60 GHz×8處理器執行計算。實驗主要使用39張小學二年級不同階段試卷(試卷在排版、字體格式、清晰度等上有所不同)，驗證OCR建立符號模板集及查找輪廓建立直線模板集的多模板匹配算法。

3.2 實驗設計

首先，輸入試卷做兩部分處理，一部分轉為灰度圖，用于后續模板匹配，對應灰度模板匹配判定方法，另一部分使用2.1節與2.2節方法，生成多個方塊、圓圈、括號、直線模板，并將生成的符號模板轉為灰度圖；其次，采用2.3節模板匹配判定方法，匹配試卷中的符號。雖設置閾值0.8過濾相關系數較小的符號，但試卷中同一符號仍保留多個相關程度較高的符號坐標，則用NMS算法過濾重復多余的坐標，每個符號有且僅保留一個。方塊圓圈直線過濾后即可得到純凈的坐標，而匹配的左括號、右括號經過濾后，仍需做括號對的判斷及寬度調整。

括號對的判斷分為兩種情況：(1) 當左右括號數量不相等時，通過NMS判斷左右兩框是否相交。若相交則表示左右括號為同一對括號，即可通過右括號坐標減去左括號坐標得到括號對的真實寬度，使用此寬度調整左括號坐標，并過濾右括號坐標;若無相交則使用所用成功配對括號寬度的平均值進行左右括號寬度的調整。(2) 當左右括號數量相等時，將左右括號根據左上角坐標按行從上到下、從左到右排列，即可成功找出所有括號對，使用右括號坐標減去其位置之前與之相鄰的左括號坐標即可得到括號的真實寬度，使用此寬度調整左括號坐標，并過濾右括號坐標，如圖6所示。

圖6 符號混合定位

3.3 結果分析

為驗證提出算法的有效性，每種符號分別使用OCR建立單模板法(OCRST)與OCR建立多模板法(OCRMT)測試試卷，實驗結果如表1、表2所示。實際數代表需在符號內填答案的個數，正確數為正確檢測符號的數量，誤檢數為錯誤定位符號的個數。使用準確率、精確度、召回率對算法進行評價，計算方法如下：

準確率=正確數/(實際數+誤檢數)精確度=正確數/(正確數+誤檢數)召回率=正確數/實際數

(9)

特殊符號誤檢主要發生于題干中，題干中存在的符號僅為提示作用并不需要作答；直線誤檢主要發生于表格中，行線與直線的相似程度較高故被定位。然而，雖然使用多模板大大提高直線的召回率，但其準確率相對較低，經測試發現在二值圖中查找直線輪廓，而后設置判斷條件篩選輪廓，直線定位準確率可達96%。OCRMT較OCRST優勢為可獲取不同類型的模板，較大限度提高正確數，但同時也提高了誤檢的可能性。兩者相對而言，正確數的增加占據主導作用，提高了符號定位的準確率、精確度與召回率。OCRMT定位效果如圖7所示。

(a) 正面定位局部效果圖

3.4 算法對比

計算OCRMT定位方塊、圓圈、括號的平均準確率，將其與Tesseract-OCR、FCN、TextBoxes等不同檢測定位方法[8,9,17-20]進行比較，結果如表3所示。

表3 不同算法比較 %

可以看出，本文提出的OCRMT定位試卷中的特殊符號有著較高的準確率，其他一些深度學習方法定位字符或文本行時，準確率最高為74.4%。然而，單個符號在文本行及試卷中所占面積極小，深度卷積由于提取不到較小目標特征，在定位試卷中符號時，往往有著更低的準確率。此外，在時間上效果較優的深度學習SSTD法使用TITAN X GPU加速計算，每秒可處理7.7幀圖像，而本文使用CPU計算每幀耗時約10 s，但由于GPU加速計算能力遠超CPU，所以本文提出的多模板匹配相對深度學習方法在準確率與速度上占有一定的優勢。

3.5 答案定位

以上得到空白試卷中所有方塊、圓圈、括號、直線的坐標，由于空白試卷與學生作答試卷在掃描過程中出現偏差，造成二者掃描圖片大小不一致，導致作答試卷中特殊符號及直線位置出現一定的偏移。此外，考慮到后續答案識別模塊的設計及識別計算量，提取學生答案時應盡量減少空白區域的干擾。對學生的作答試卷做二值化處理，求出空白試卷符號坐標的中心點；將中心點映射于答卷二值圖中，在二值圖中向上下左右四個方向進行掃描，直至四個方向全部掃描不到黑色像素點，記錄此時的位置，即可得到答案在試卷中左上角及右下角坐標。

3.6 分析討論

題干中非答題區域的方塊、圓圈、括號與作答題目中方塊、圓圈、括號相同，使用OCR獲取符號多模板匹配易定位出題干中非答題區域的方塊、圓圈、括號，針對此問題有兩種解決方案。(1) 題干中的特殊符號僅作為提示作用，并無實在意義，出卷時可使用漢字替代，以提高符號識別定位的準確率；(2) 在知道試卷每題的區域及答案數量的前提下，通過逆序排列定位出符號坐標，再選取與答案數量對應的符號坐標，可排除題干中符號的干擾，同時也可利用每題區域消除表格對直線的影響。另外，試卷中存在中英文輸入法下輸入的多種符號類型，本文為提高特殊符號識別定位的準確率，使用OCR獲取多模板方式，但同時也增加了時間負擔。保持試卷中特殊符號的統一性、規范性，有利于保證特殊符號識別定位的準確率和穩定性，同時也可減少模板的使用，整體降低運行時間。

4 結 語

基于深度學習的檢測方法定位準確率低且硬件要求高，難以滿足實際應用需求。為解決試卷智能批閱場景中答案定位關鍵問題，本文提出的多模板匹配法，方塊圓圈括號的平均識別定位準確率為94.5%，直線定位準確率為87.8%，對于定位作答試卷截取手寫答案識別具有重要意義。獲取多模板方法具備的通用性，可實現任意張試卷中符號的高精度定位。同時減少題干中特殊符號的個數及保持試卷特殊符號的規范性與統一性，不僅能提高符號識別定位的準確率，而且也可通過減少模板個數來降低運行時間。在接下來研究中，將通過訓練深度神經網絡獲取分類器，識別作答試卷符號內答案，完成試卷的智能批閱。