面向中文矢量筆跡中單字詳細分類的特征和方法比較
2008-12-31 00:00:00張堃張習文
計算機應用研究 2008年11期
(中國科學院 軟件研究所 人機交互技術實驗室， 北京 100080)
摘要：在識別矢量筆跡文本時，不同類型單字需要采用不同識別器，確定詳細類別是單字識別的前提。對實際中文矢量筆跡文本中單字進行漢字、標點、數字、字母和單詞的詳細分類，提出了自身和相對（包括近鄰和同行）特征，選用決策樹、邏輯模型樹、貝葉斯網絡和支持向量機四種分類器。針對大量實際數據，測試和比較了多種特征和分類器的性能。實驗表明，近鄰單字的組合特征具有較好的分類能力，支持向量機對各種單字均有較好分類性能。
關鍵詞：矢量筆跡文本；單字識別；單字分類；特征；分類器
中圖分類號：TP39141文獻標志碼：A
文章編號：1001-3695(2008)11-3486-04
Comparison of features and classifiers for detailedlyclassifying handwriting characters in Chinese ink texts
ZHANG Kun，ZHANG Xi-wen
(Laboratory of Human-Computer Interaction， Institute of Software， Chinese Academy of Sciences， Beijing 100080， China)
Abstract:Different types of characters from Chinese ink texts are recognized before they are need to different recognizers. Thus it is prerequisite to identify writing characters’ detailed categories for improving their recognition. This paper aimed to classify writing characters into Chinese character， punctuation， digit， number， as well as English letter and word.Extracted each writing character’ self and relative features， and applied representative classifiers， such as decision trees， logistic model trees， Bayesian network and SVM.Features and classifiers were evaluated with many real-life Chinese ink texts. Experimental results show that relative features are more powerful and SVM is the most efficient classifier for each type of writing characters.
Key words:Chinese ink text; handwriting character recognition; handwriting character classification; feature; classifier
0引言
隨著矢量筆跡采集設備的日趨成熟，人們能夠以自然、連續而高效的方式將手寫手畫數據輸入計算機，如書寫文字和公式、徒手畫圖和繪制表格等。得到廣泛應用的采集設備包括Anoto紙筆[1]和手寫電腦（tablet PC）[2]等。對于沒有受過打字訓練的普通中文用戶來說，由于漢字結構和鍵盤輸入的復雜性，采用手寫將漢字輸入計算機更為自然和高效。但中文矢量筆跡文檔只有筆畫信息，需要進行分割和識別才能進行高層次處理，如基于多層次結構的編輯、修改、排版和識別輸出到已有軟件（MS Word）等。
在中文矢量筆跡文檔中，文字內容占有較大比例，需要進行較多處理。識別矢量筆跡文本可以提供符號化、結構化的計算機文檔，方便在MS Word等文字處理軟件中作進一步的處理。對于不同類別單字需要采用不同識別器，確定詳細類別是單字識別的前提。微軟單字識別器[3]在識別前必須指定語言類別（中文簡體和繁體、英文等）；漢王單字識別器[4]可以設定一級漢字、二級漢字、標點、數字、字母及其組合等詳細類別，在識別組合類別時，多數符號識別錯誤是由詳細類別錯誤導致的。如果能提供正確的詳細分類，可以大大提高單字識別率。在識別單字前確定待識別單字的詳細類別是十分必要的。
對中文矢量筆跡文本中單字的詳細分類問題，已有研究工作但還沒有給予足夠的重視。已有方法多選取較為簡單的自身幾何特征[5~7]。處理印刷體掃描圖像的工作較多，但多是非中文的，面向的是文本區域和文本行，而不是單字[8~12]。本文將針對實際中文矢量筆跡文本中單字的詳細分類問題，研究更為復雜而高效的特征，采用多種分類器進行深入的對比研究。本文對單字進行漢字、標點、數字、英文字母和單詞等詳細分類；提出采用組合特征，不僅包括已有較多研究的單字自身特征，還包括單字與相鄰字、整行單字的相對特征；選用包括決策樹、邏輯模型樹、貝葉斯網絡、支持向量機在內的具有代表性的四種分類器對分類正確率和計算時間等進行對比。
1已有相關工作
目前，針對中文矢量筆跡文本中的單字，能夠區分漢字、標點符號、數字、英文字母和單詞的工作還很少。Zhang等人[13]通過筆畫密度、筆畫方向和筆畫交叉度三種特征對矢量筆跡文本中單字進行漢字和英文單詞的分類。
矢量筆跡可以很容易地轉換為光柵筆跡。Spitz[8]對混合多種語言光柵筆跡中的單字進行分類，包括了23種語言的拉丁語系和中、日、韓三種語言的亞洲語系。該工作首先用向上凹度特征來區分開拉丁語系和亞洲語系，然后用文字形狀令牌（word shape tokens）特征進行拉丁語系分類，用光密度特征進行亞洲語系分類。Y.Suen等人[9]區分阿拉伯語系、象形文字語系和拉丁語系，通過高度分布、單字密度和水平投影進行粗分類，得到對應語系，然后對于拉丁語系采用文字形狀令牌特征進行細分類。Tan等人[10]先利用包圍框等基本特征對漢語、拉丁語系、泰米爾語系進行粗分類，然后對拉丁語系利用文字形狀令牌特征細分為英語和馬來語。Lyu等人[5]對視頻中文本區域進行了中英文分類。矢量筆跡轉換為光柵筆跡會丟失筆畫及其時序等很多信息，不利于單獨的單字詳細分類，但可以提供補充信息。
針對印刷體掃描圖像中單字分類已有較多工作。Zheng等人[11]對單字圖像進行中英文分類；U.Pal等人[12]對文本行圖像進行英文、中文、梵文、孟加拉文的分類。
在中文矢量筆跡文本中，雖然以中文為主，但其中也會包含英文單詞，多是專業詞匯，尤其是在中國的英語教學中，更是中英文對等混排。因此，本文以實際中文矢量筆跡文本為研究對象，利用已開發工具獲得原始矢量筆跡數據，采用豐富的矢量特征與光柵特征，通過四種具有代表性的分類器進行單字詳細分類的特征和分類器的對比研究，以期為提高單字識別率提供較好的預處理。
2特征的選取與對比
中文矢量筆跡文本由筆畫構成，先從中提取單字和文本行，采用MS Tablet PC development kit 1.7[14]進行自動處理；然后基于筆手勢交互修改，獲得正確提取的單字和文本行。原始中文矢量筆跡文本及其分割結果如圖1、2所示。
對單字進行詳細分類，不僅利用了已有較多研究的單字自身特征，還提出了相對特征，考慮單字與前后字、所在行單字之間的特征對比值。這些新型特征包括3個方差類特征、6個近鄰特征和4個同行特征。在實驗中，共計使用了22個特征。
21自身特征
12個自身特征中，有7個特征是來自于已有筆跡單字識別工作，將這些特征引入單字詳細分類中；另外3個特征是根據觀察所得的；矢量特征是基于筆畫信息的，筆畫是指筆尖從落下到抬起所記錄的時序采樣點集合。
a）高寬比(aspectRatio)[5]，Ra=H/W。其中H和W分別表示該單字正放包圍矩形的高度與寬度。該特征能夠很好地區分寬型符號和高型符號。
b）筆畫間交叉點數目[6]Nint。較多的漢字擁有較多的筆畫間交叉點，而數字、英文字母、單詞則很少存在筆畫間交叉點，該特征適用于區分漢字與其他單字。
c）筆畫數目[5]Nstrokes。漢字、英文單詞筆畫個數較多，而標點、數字和英文字母具有較少筆畫，該特征可以區分中英文和其他單字。
d）折線密度[5]，den=(Nstrokesi=1Li)/A。其中：Li表示第i個筆畫的所有采樣點連接線長度和；A表示其正放包圍矩形的面積。多數漢字具有較多筆畫，結構緊密，密度要大于其他單字，因而該特征能夠區分漢字與其他單字。
e）筆畫平均線長[15]，Larc=（Nstrokesi=1Di)/Nstrokes。其中：Di表示第i個筆畫的終點與起點的直線距離。該特征可以區分單字筆畫的開放和閉合。漢字極少有閉合筆畫，而英文和標點則較多，因此該特征能夠用于確定漢字。
f）筆畫平均控制面積[15]，Aarc=（Nstrokesi=1Aarc，i)/Nstrokes。其中：Aarc，i表示第i個筆畫的矢量弧所涵蓋的類扇形面積。該特征能夠區分直線形和曲線形筆畫。漢字筆畫一般屬于直線形，而英文和標點則有較多曲線形，因此該特征能夠用于確定漢字。
g）平均直線逼近度[15]。為了計算直線逼近度，首先利用最小二乘法作一條擬合曲線，然后通過計算采樣點到擬合曲線的平均投影距離得到平均直線逼近度。同上一個特征類似，都是用來區分是否屬于類直線形筆畫。漢字筆畫多是橫平豎直，而其他字符則多為類圓弧筆畫，因此該特征能夠用于確定漢字。
h）對稱度[7]。將矢量筆跡的光柵圖像以中心為原點分為四個象限，計算四個象限的像素密度，最大密度差值為對稱度。多數漢字四個象限的像素密度大體相當，而英文則不能滿足這一點，有些數字和標點符號更是極為不對稱，如“2”“7”和“？”。
i）MRLSA (modified run length smoothing approach)[12]。對矢量筆跡光柵圖像，先進行縱向和橫向的腐蝕運算，然后計算前后的點陣數目變化。通過實驗對比發現，往往中文漢字經過MRLSA運算后，前后點陣數目變化巨大，而英文、字母與數字則變化很小。
j）橫向像素個數方差，varhor=var(H1，H2，…，Hk)。其中：Hi表示圖像橫向第i列的像素點數目；var(…)表示其方差。
k）縱向像素個數方差，varver=var(V1，V2，…，Vk)。其中：Vi表示圖像縱向第i行的像素點數目。
l）雙向方差之差，VV=abs(Vhor-Vver)。其中：abs()表示對一個實數取絕對值。
22近鄰特征
單字自身特征受單字大小影響較大，而相鄰單字的相對特征則具有較好的穩定性。尤其是對于標點符號、數字和字母這樣的單字，其相鄰特征與漢字單字或是英文單詞單字差別非常大。根據對矢量筆跡文本數據所作的大量分析，提出相鄰單字的水平位置比、面積比、高度比和寬度比。
a）相對前字水平位置比Ppos=（Ti-1-Mi)/（Mi-Bi-1）；相對后字的水平位置比Fpos=(Ti+1-Mi)/(Mi-Bi+1)。其中：Mi表示當前單字正放包圍矩形的中心點縱坐標；Bi-1、Bi+1與Ti-1、Ti+1則分別表示相鄰前字和相鄰后字的正放包圍矩形的最低點縱坐標與最高點縱坐標。
b）相對前字面積比PA=Ai/Ai-1；相對后字面積比FA=Ai/Ai+1。其中：Ai、Ai-1、Ai+1分別表示當前單字、相鄰前字與相鄰后字的正放包圍矩形的面積。
c）相對前字寬度比PW=Wi/Wi-1；相對后字寬度比FW=Wi/Wi+1。其中：Wi、Wi-1、Wi+1分別表示當前單字、相鄰前字與相鄰后字的正放包圍矩形的寬度。
23同行特征
中英文混排時，通常同行漢字位于同一條水平線，而英文字母、單詞則要低于這一水平線。同樣的，大部分標點符號也是分布在水平線的上下兩端。另一方面，因為數據庫中的樣本是由不同的書寫者分別完成的，每個人習慣書寫的字體大小差別很大，如果不引入平均的統計計量，則無法共同進行比較學習。本文引入的同行特征如下：
a）單字高度與所在行單字平均高度的比值RH=Hi/。其中：Hi表示當前單字正放包圍矩形的高度；表示所在行單字正放包圍矩形平均高度。
b）單字寬度與所在行單字平均寬度的比值RW=Wi/。其中：Wi表示當前單字正放包圍矩形的寬度；表示所在行單字正放包圍矩形平均寬度。
c）單字面積與所在行單字平均面積的比值RA=Ai/。其中：Ai表示當前單字正放包圍矩形的面積；表示所在行單字正放包圍矩形平均面積。
d）字行平均水平位置RR=(i-M)/(M-i)。其中：M表示當前單字正放包圍矩形的中心點縱坐標；i、i分別表示當前文本行所有單字正放包圍矩形的平均最高點與平均最低點的縱坐標。
24特征的對比與分析
根據對大量數據的觀察和相關工作，選取和提出了上述特征。基于類內方差σ2W、類間方差σ2B和總體方差σ2T對它們的分類能力進行定量對比。各方差計算公式如下：
σ2W=ni=1σ2i/n
σ2B=ni=1(σi-σM)2/n
σ2T=σ2B+σ2W
其中：N表示類別的數目；σi表示某特征具體到某一個類別的標準差值；σM表示某特征對于所有類別的標準差的平均值。當σ2B/σ2T較大時分類性能較好。
在圖3中，橫坐標為22個特征，排列順序與本文介紹的順序一致。由圖3可以看出，大部分特征具有較強的分類能力。
3分類器的選取與對比
1）決策樹（J48）[16]決策樹利用樹結構進行分類，根據特征遞歸創建節點子樹，節點記錄特征，葉子節點為類別。J48決策樹算法采用C4.5決策樹，它可以處理連續和離散數據，支持缺省訓練數據、調整訓練數據權重和剪枝。決策樹是一種基于樹的自上而下的分類器，其直觀、高效的知識表示方法是廣為采用的一個重要原因。
2）邏輯模型樹（logistic model trees，LMT）[17]在決策樹中引入線性邏輯回歸，節點包含邏輯回歸函數。相對于C4.5和邏輯回歸來說，在分類精度和樹規模方面都有明顯優勢[11]。邏輯模型樹是在決策樹的基礎上引入了線性邏輯回歸，使得其性能和分類精度都要優于決策樹。
3）貝葉斯網絡（Bayesian network，BN）[16]采用圖進行分類，通常是有向非循環圖，節點表示特征，節點之間有向弧表示變量之間的概率。風險能夠涵蓋所有變量獨立性，可以容忍變量輸入丟失；能夠學習因果關系；可以導入先驗知識；可以預防過擬合。貝葉斯網絡的特點在于其不確定性知識表達形式、豐富的概率表達能力、綜合先驗知識的增量學習能力。
4）支持向量機（supported vector machine，SVM）[18]SVM是一種主要的統計學習方法，以VC維理論和結構風險最小原理為基礎，具有較好的推廣能力，解決了神經網絡中局部極值問題，計算復雜度與樣本維數無關。它通過非線性變換生成到高維特征空間，從而利用線性判別函數實現非線性分類。支持向量機是基于結構風險最小化原則發展起來的分類器，目前應用非常廣泛，同時其在小樣本問題上的優勢也是選擇它的一個重要因素。
實驗中采用了兩個測試平臺，即WEKA[16]和SVMTorch[18]。WEKA是一個數據挖掘平臺，包含了很多機器學習、模式識別算法；SVMTorch是一個支持向量機的源碼包，特別適用于大尺度樣本數據訓練，在支持向量機分類領域廣受肯定。
4實驗與結果分析
測試數據采集于不同的書寫者，使用Anoto 紙筆[1]，采用自然的書寫方式。測試數據包括中英文混排文本、純中文詩詞文本和普通文本。詳細數據如表1所示。
表1測試數據構成單位/個
測試數據 頁碼數/頁漢字標點符號數字英文字母英文單詞合計
中英文混排135 4741 7732963231 8039 669
純中文詩詞1911 5411 89000013 431
普通文本83 990395975604 538
合計4021 0054 0583933791 80327 638
測試所采用分類器參數如表2所示，J48、LMT和BN是在WEKA平臺上進行的，而SVM則是通過SVMTorch實現的。
表2分類器參數
分類器實驗參數
BN局部Tan函數，ADTree，10-fold交叉驗證
DT使用BinSplit，ADTree，10-fold交叉驗證
LMT使用AIC，10-fold交叉驗證
SVM多分類，STD 10，10-fold 交叉驗證
本文采用數據來測試四種分類器的性能，實驗結果如表3所示。其中：F1、F2、F3分別表示自身特征、相鄰特征和同行特征。
表3全部樣例針對四類分類器的實驗結果（分類正確率）
特征BN/%DT/%LMT/% SVM/%
F281.899 785.752 0 85.277 0 80.738 8
F384.854 986.8602 86.860 2 85.646 4
F186.807 489.551 5 90.870 7 91.662 3
F1+F2 88.443 390.343 0 92.401 1 92.612 1
F1+F2+F392.981 591.978 9 94.036 9 96.092 3
從表3可以看出，對四種分類器而言，單獨采用一類特征進行測試，自身特征的性能最好，同行特征較次，而近鄰特征最差。這并不表示自身特征優于其他兩種相對特征，而是由于自身特征的數目較多，而相對特征數目較少造成的。當逐漸加入相對特征后，實驗顯示出越來越強的分類性能。通過對不同分類器的對比測試發現，SVM分類最為有效，因而采用SVM進行深入測試。表4給出了基于不同訓練數據進行測試的結果。從表4可以看出，基于同類型數據訓練模型進行測試，會取得更好的測試效果，因而建議采用該方式。表5對不同分類器的系統耗時進行了初步對比；圖4給出了采用組合特征和SVM分類器的詳細分類結果。本文用字母C、E、L、P、N分別表示中文單字、英文單詞、英文字母、標點符號和數字。第一行的字母表示該單字的實際類別，第二行的字母表示自動分類得出的結果，如果得出的結果不正確，則用矩形框標記出來。圖示的文本來自于實際英語教學筆記，共計218個單字。經過詳細分類標注后，209個單字標注正確，9個單字標注錯誤。
表4采用SVM以及全部特征對數據庫的實驗結果（分類正確率）
數據庫中文庫訓練/%中英文混排庫訓練/%全部樣例訓練/%
中文庫測試98.436 398.287 498.808 6
中英文混排庫測試69.774 990.032 295.211 1
表5采用全部樣例和全部特征對比不同分類器的系統耗時
（CPU：Intel Pentium 4 1.8 GHz，內存512 MB）
測試項BN/sDT/sLMT/sSVM/s
分類耗時0.190.280.470.44
5結束語
針對實際中文矢量筆跡文本中單字詳細分類，本文選取和提出了自身特征和相對特征，選用了決策樹、邏輯模型樹、貝葉斯網絡和SVM四種典型的分類器，采用實際數據進行了特征和分類器的性能比較。測試結果表明，相對特征具有較強的區分效果，支持向量機具有較好的分類性能。
參考文獻：
［1］Anoto Website[EB/OL].http://www.anoto.com.
[2]Microsoft Windows XP Tablet PC[EB/OL].http://www.microsoft.com/windowsxp/tabletpc/default.mspx.
［3］Windows XP Tablet PC edition 2005 recognizer pack[EB/OL].http://www.microsoft.com/downloads/details.aspx?FamilyID=080184dd-5e92-4464-b907-10762e9f918bDisplayLang=en.
[4] 北京漢王科技有限公司.漢王主頁[EB/OL].http://www.hw99.com.
[5]LYU M R，SONG Ji-qiang，CAI M.A comprehensive method for multilingual video text detection[J].IEEE Trans on Circuits and Systems for Video Technology，2005，15(2):243-255.
[6]TRIER O D，JAIN A K，TAXT T.Feature extraction methods for cha-racter recognition: a survey[J].Pattern Recognition，1996，29(4):641-662.
［7］TAPPERT C C，SUEN C Y，WAKAHARA T.The state of the art in on-line handwriting recognition[J].IEEE Trans on Pattern Anal Machine Intelligence，1990，12(8):787-808.
［8］SPITZ L.Determination of the script and language content of document images[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1997，19(3):235-245.
［9］SUEN Y，BERGLER S，NOBILE N，et al.Categorizing document images into script and language classes[C]//Proc ofInternational Conference on Advances in Pattern Recognition.1998:297-306.
［10］TAN C L，LEONGP Y，HE Shou-jie.Language identification in multilingual documents[C]//Proc of International Symposium on Intelligent Multimedia and Distance Education.1999:59-64.
［11］ZHENG Ye-feng，LIU C，DING X.Single character type identification[C]//Proc of SPIE Conference on Document Recognition and Retrieval.2002:49-56.
［12］PAL U，CHAUDHURI B B.Automatic identification of English， Chinese， Arabic， Devnagari and Bangla script line[C]//Proc of the 6th International Conference on Document Analysis and Recognition.Washington DC:IEEE Computer Society，2001:790-794.
［13］ZHANG Xi-wen，LYU M R，DAI Guo-zhong.Extraction and segmentation of tables from Chinese ink documents based on a matrix model[J].Pattern Recognition，2007，40(7):1855-1867.
［14］MS Tablet PC development kit 1.7[EB/OL].http://www.microsoft.com/downloads/details.aspx?FamilyId=B46D4B83-A821-40BC-AA85-C9EE3D6E9699displaylang=en#QuickInfoContainer.
［15］LaVIOLA J.Mathematical sketching:a new approach to creating and exploring dynamic illustrations[D].Providence:Brown University，2005.
［16］WRITTEN I H，FRANK E.Data mining:practical machine learning tools and techniques with Java implementations[M].2nd ed.San Francisco:Morgan Kaufmann Publishers，2000.
［17］LANDWEHR N.Logistic model trees[D].[S.l.]:University of Freiburg，2003.
［18］SVMTorch[EB/OL].http://bengio.abracadoudou.com/projects/SVMTo rch.html.
