一種多模型超圖用于手寫漢字識別算法

魏炳輝 謝暉慧 鄧小鴻

(江西理工大學應用科學學院 江西 贛州 341000)

0 引 言

隨著社會經濟的快速發展，商業銀行每天需要處理、保存的票據數量在迅速增長。票據的處理程序包括人工錄入、核驗及存檔等繁瑣的過程，這給銀行工作人員帶來了沉重的負擔。面對銀行票據如此嚴格又繁瑣的處理程序，人工處理的方式工作效率低下，不但滿足不了日益增長的處理需求，而且容易出現人為錯誤，給銀行帶來不必要的經濟損失。為了解決上述問題，提高銀行業的自動化技術水平，票據自動處理技術的設計很快成為相關領域研究的重要課題。其中手寫漢字識別是最重要的一個難關。票據上的手寫漢字因其存在形式復雜多樣，致其識別率不高，難以達到商用化標準。因而票據手寫漢字識別技術的研究成果對商業銀行系統的運作有很大的實用和參考價值，同時取得的研究成果也將對圖像處理、模式識別、人工智能等多個學科的發展起到一定的推動作用，具有重要的實用價值和理論意義。

國外對手寫字符識別的研究比較早，目前已有許多實用化的產品[1-2]，一個完整的手寫字符識別系統的研究內容主要涉及字符分割、特征提取、字符識別，目前字符分割算法已達到商用化程度，以后研究的重點在于特征提取與字符識別。國內外在字符串分割與識別等處理技術方面都取得了重大進展[3-4]。對于字符目標提取，目前的大多數方法是通過對字符對象的亮度或筆畫特征建模來提取字符目標。典型的方法有Ye等[5]采用一種綜合亮度特征和局部幾何特征的字符筆畫雙邊緣模型，用于復雜背景中字符對象的提取，該筆畫模型融合筆畫寬度約束與筆畫亮度信息，能有效地解決背景突變帶來的問題。季婧婧等[6]利用二次分割的方法濾除票據上的彩色印章以提高文本內容的識別率。但這些成果都只在于數字與字母等結構相對簡單的字符識別研究，而手寫漢字方面識別正確率仍然不高。

造成這種情況的原因，是我國手寫漢字結構復雜，形體豐富多樣導致手寫漢字識別率達不到商用化標準。近年來研究較多的是手寫漢字塊的特征提取算法研究。根據不同的規則及分類，識別方法大體可分為三類：模板匹配法、統計模式識別方法以及結構模式識別方法。這些方法主要是基于人工神經網絡、支持向量機、隱馬爾可夫模型和最近鄰匹配等方法的推廣或幾種方法的集成[7-8]。根據系統的實際需要，采用多種信息源、多種特征提取以及多識別器結合等多項預處理技術[9-10]，來提高識別系統的性能。文獻[10]利用深度學習的方法識別手寫漢字正確識別率已經達到96.13%，是目前公布的最好結果。然而該研究所用的手寫漢字都是相對規范的、筆畫比較清楚的，另外深度學習模型需要大量的訓練樣本，訓練時間較長，但在現實中難以滿足這些條件。不同的人手寫漢字存在很多復雜的情況，如字符粘連、連筆現象、位置高低不一、大小不一等，提取單個的手寫漢字，再進行識別的效果受前述影響較大，難以達到商用化標準。在銀行票據手寫漢字識別需求中，存在訓練樣本少和實時性要求高的特點。

本文利用多模型超圖學習理論，對比較固定的文本塊學習其歸屬標志。其出發點有兩個：一是超圖學習方法適合小樣本學習，在訓練樣本較少的情況下可以獲得較好的分類性能；二是票據上有些文本塊的內容比較固定，利用超圖學習識別速度較快。超圖學習模型在公開的一些標準數據集上已經體現出一定的優勢，而在手寫漢字識別上還鮮有報道。

1 算法設計

基于超圖的學習模型是一種非常重要的直推式半監督學習方法，在已有的直推式半監督學習算法中，超圖學習方法能獲得較好的性能[11-12]。超圖學習目標是找到樣本間的高層相關性，在超圖構建時，超邊的權值需要依據一定的法則來確定。為了挖掘手寫漢字間的多重相關性，在普通超圖的模型中融入稀疏表示與成對約束理論，以及該結合模型的最優解論證方法。下面先介紹構建普通超圖，再以手寫文本塊特征向量的解稀疏表示系數建立稀疏超圖與標記樣本的成對約束模型，最后融合這幾個模型求解最優解。

1.1 構建普通超圖

構建普通超圖時，超邊選取有多種方法，對于給定樣本，一種辦法是距離其最近的若干樣本所組成的集合為一條超邊；第二種辦法是指定一個閾值，與該樣本的距離值小于設定閾值的樣本集合為超邊。本文選取前者構建超圖學習模型。

設定圖G=(X,E)，所有樣本x構成樣本集X，和所有的超邊e集合構成邊集E，每一條超邊包含了若干個樣本，邊的權重是該邊中所有樣本間的距離平均值。設定矩陣Dv、De和W對角線元素分別表示相應樣本所在的邊數、超邊中樣本的個數和超邊的權值，設定鄰接陣H，矩陣元素表示兩樣本間的連接關系。根據文獻[12]，得到目標函數如下：

(1)

1.2 構建稀疏超圖

(2)

式中：w=[w1,w2,…,wd]T。x和w表示同一個數據點,前一個是基于空間域，另一個是基于Σ域。我們的目標是求解出基于Σ的稀疏系數,即w包含盡量少的非零元素。根據文獻[14-15],這個稀疏解可以通過以下目標函數式求解得到：

(3)

假定數據集是采樣于一個包含k個獨立子空間的統一空間里，相當于這個數據集包含k類，該目標函數可以獲得塊稀疏解，每一塊中的非零元素對應一個子空間(關于塊稀疏求解方法請參閱文獻[14])。相近的樣本稀疏表示也相近，可以被同子空間中相近的點線性表示，稀疏系數對應著樣本間的相關性或權值。

根據求解后的稀疏表示，構建稀疏超圖，樣本相應的稀疏表示參數如果是非零值，表示兩樣本間相關，該參數表示相關性的緊密程度，鄰接關系陣A為：

(4)

式中：|(wi)j|表示wi的第j個元素的絕對值。設定Ls=I-Dv-(1/2)AWDe-1ATDv-(1/2)為基于稀疏表示的拉普拉斯矩陣，稀疏超圖的正則表達式為:

minfLsfT

(5)

1.3 樣本成對約束

近年來，成對約束[16-17]在半監督學習領域引起了廣泛關注。成對約束包含兩個約束：必須連接約束和不能連接約束。利用訓練樣本的標記信息，必須連接約束表示，標記信息相同的樣本或者說同類樣本通過學習后，其類別信念必須相近；而不能連接約束規定不同類的樣本通過學習后，其類別信念相距越遠越好。這里結合這兩個約束進超圖學習模型中以增強學習能力。

設定fi為xi的學習之后類別信念,C+表示與xi同類的樣本集，C-表示與xi不同類的樣本集,必須連接約束可以表示為:

(6)

和不能連接約束表示為：

(7)

結合這兩個約束為成對約束，表示為：

minfLpfT

(8)

1.4 融合稀疏表示與成對約束理論的超圖學習

在普通超圖中融入稀疏表示與成對約束理論成為一種新的結合學習算法，本文稱之為多模型超圖學習模型(CSP)，目標函數為：

(9)

(10)

式中：r>1。為解決這個目標函數，我們利用一種迭代求解的方法[18]，先初始化β=[1/3,1/3,1/3],固定β利用拉葛日乘法更新f：

(11)

然后固定f，最小化表達式(11)，可以計算出β為：

(12)

這個學習模型通過兩到三次迭代后收斂。表1給出了算法流程。

表1 算法流程

2 實 驗

本文收集68個志愿者同時寫64遍“華為技術有限公司”和“網絡基礎”的文本塊圖像，圖1為四個志愿者手寫漢字圖像。本文利用8重交叉驗證方法，即在每一次實驗中，把所有標記數據與非標記數據分別分成8等份，選取其中1份作為訓練樣本集，剩下的7份為測試樣本集。然后重復8次，每一個樣本都有機會成為訓練樣本，取均值作為性能評估。

圖1 手寫漢字示例

實驗首先對每個文本塊進行特征分析[19-20]。志愿者在寫文字時沒有限定寫法，對字體、字號、粗細、字間距、高低等不作要求，完全按照其真實的寫法。結構特征包含質心特征、筆畫特征、筆畫特征點、幾何特征。質心特征(2D)是文本筆畫分布的體現，將二值圖像轉化成點陣形式，再依據質心計算公式求出水平質心與垂直質心。筆畫特征(4D)由橫、豎、撇、捺四種基本筆畫構成，對單字分別提取這四種基本筆畫，統計出各自的數量。筆畫特征點(4D)主要有端點、折點、歧點與交點，端點是筆畫的起點或終點，折點是筆畫方向出現顯著變化的點，歧點是三叉點，交點是四叉點。按序對二值圖像進行掃描，統計出各筆畫特征點的個數。幾何特征(1D)是計算包含文本塊的最小矩形的長寬比值。統計特征包含方向特征、網格特征、Gabor特征等。方向特征(1D)是文本塊的方向角度。網格特征(30D)是把包含文本塊的最小矩形平均分成若干行若干列，每個單元格中文字像素點的個數統計，本文實驗時分成3行10列共30個單元格。Gabor特征(30D)是在網格基礎上計算Gabor變換后的對應能量表示。最后組合這些多種特征為文本塊的72維的特征向量。

為檢測所提出的算法，我們在實驗中對比以下幾種方法：k-近鄰分類器(KNN)確定某點中最近鄰的k個點中，相同標記最多的標記指定給此點，簡單易實現，本文把KNN當作基本的方法用來比較；半監督區分性分析(SDA)算法[21]通過求解一個關于訓練數據區分結構的映射，利用訓練數據，包含未標記數據，構建一個目標函數，這個目標函數加入了由局部幾何流形的離散估計得出的拉普拉斯圖，這樣能保持數據內部的流形結構；自適應超圖學習算法(AHL)[22]選取多個領域作為超邊集，然后迭代學習每邊的權值，以此來更新樣本的類別信念c；本文提出的結合稀疏表示和成對約束理論成為一種新的超圖學習框架(CSP)。

圖2所示為兩類手寫漢字的四個分類算法的正確率及誤差，可以看出本文提出的算法CSP在正確識別率上表現最好，與AHL比較接近。但在誤差方面，CSP表現較之于AHL的波動較大，說明CSP受噪聲影響較大。而SDA算法表現較為穩定，在兩類數據集上的正確識別率相差較小，每次實驗間的誤差更小。KNN只考慮樣本特征間的距離相似性而表現一般，并且受噪聲影響最大。綜合這四類算法表現都不高，主要是志愿者在連續寫字時，會隨著心情的變化而有所改變。剛開始時寫的字比較規范，到后面是越來越潦草，多筆畫少筆畫都有可能出現。如圖3所示兩位志愿者寫的“網絡基礎”，是錯判率最高的兩類樣本。可以看出，字形與筆畫都有變化，出現連筆現象較多，致使作出錯誤的判斷。

圖2 兩類手寫漢字塊的四個分類算法識別率

圖3 錯判率較高的兩位志愿者手寫漢字示例

3 結 語

本文為提高手寫漢字的識別率，考慮樣本間更多層的關系，融合稀疏表示與成對約束理論成為一個新的超圖學習模型。通過加入稀疏表示，更好地表現同類樣本間的相關性。通過增加成對約束，對有標記樣本的類別屬性進行更有力的約束，加強同類樣本間未標記樣本的樣本類別屬性傳遞。在兩類手寫漢字數據集上的實驗表明，本文提出的新超圖學習模型有一定效果，但在現實中由于手寫體易受外在因素與手寫者的主觀因素的影響，總體識別率還較低，需要進一步的研究提高。