付鵬斌 董澳靜 楊惠榮

(北京工業(yè)大學 信息學部，北京 100124)

漢字種類多、結構復雜、書寫隨意性強，手寫文本中極易出現(xiàn)交錯、粘連、重疊、字內字間距離不固定等現(xiàn)象。錯誤的切分必然導致錯誤的識別，因此提高手寫文本切分正確率對識別有著重要的意義。目前，文本切分方法主要有投影法[1]、連通域搜索[2]、滴水算法[3]、基于識別反饋的切分方法[4- 5]和基于字體結構的切分方法[5- 6]。單一切分算法難以有效解決手寫文本切分中的復雜問題。Zhao等[7]提出了一種粗切分與細切分結合的方法，首先通過垂直投影和背景骨架分析得到粗切分結果，然后細化粘連字符，找出候選筆畫和特征點，利用模糊決策規(guī)則得到細切分結果，然而這種模糊決策的標準不易被確定。馬瑞等[8]提出多步切分方法，利用Viterbi算法[9- 10]進行初切分，然后基于骨架圖像分析粘連字符，最后利用A*算法求出最優(yōu)切分路徑，該方法切分效果明顯好于單一算法，但未能解決字符多重粘連問題。李小園等[11]提出基于結構聚類和筆畫分析的方法，僅針對兩個漢字粘連的情況。Xu等[12- 13]定義雙層學習濾波器提取候選粘連點，但濾波器對無約束手寫數(shù)據的適應性不高。對于過切分字符，吳相錦等[14]依照字距和寬高特征進行合并，實現(xiàn)較簡單，但準確性不高；Wu等[15]利用識別置信度指導合并，效果較好，但由于將整個文本切分序列作為搜索全集，合并計算量較大。近年，有學者提出基于無切分的端到端場景文本識別方法[16]，由于中文文本行的語義關聯(lián)性不夠強，效果不算很好，同時該方法要求海量數(shù)據和高硬件性能。

本研究提出的基于貪吃蛇算法和部首識別的手寫中文文本切分方法，模擬貪吃蛇運動軌跡作為切分依據，結合漢字特征、寬高閾值、部首結構、鄰域上下文信息和識別置信度等，對中文文本進行切分和合并，得到正確的文本切分結果；其可應用于教育領域的主觀題自動閱卷等方面。

1 基于貪吃蛇的手寫中文文本切分

1.1 貪吃蛇切分算法設計

基于垂直投影的切分算法只能形成豎直路徑，無法解決字符之間的交錯、粘連、重疊等問題；基于連通域的切分方法容易使連通元過碎，而真正粘連的字符，也不能通過連通域切分開；滴水算法通過模擬水滴向低處滾動形成非線性切分路徑，該算法可以取得比豎直切分更好的效果，但由于水滴在筆劃內部形成垂直滲透，造成字符損傷，并不適合處理具有復雜結構的手寫中文文本。

本研究的貪吃蛇切分算法，通過模擬貪吃蛇在文本圖像中爬行得到非線性切分路徑。將待切分文本圖像中的字符作為貪吃蛇爬行過程中的障礙物，規(guī)定爬行起點，且爬行趨勢為豎直方向。以向下爬行為例，若蛇在爬行過程中遇到障礙物，則沿障礙物邊緣繼續(xù)向下；若蛇進入字符凹陷區(qū)域，則逐步回溯，回溯軌跡不加入有效路徑，最終到達終點的有效軌跡形成原始切分路徑，之后依據多重約束規(guī)則對其進行優(yōu)化，得到候選切分路徑。貪吃蛇爬行過程中不穿過字符筆劃，因此減少了字符損傷。

待切分文本圖像為預處理后的二值圖像，貪吃蛇每一步爬行均與當前點下面3個像素和左右2個像素有關，其爬行規(guī)則如圖1所示，其中：·表示當前點位置；b表示字符像素點；w表示背景像素點；★表示任意像素點，即該點的像素值不會影響貪吃蛇的路徑選擇；→表示貪吃蛇下一步的運動軌跡；=>表示像素轉換。圖1(a)示出了當前點鄰域5像素的位置及命名。如圖1(b)所示，只要p3為背景像素，則下一步都將向p3爬行；若p3為字符像素，依次按照圖1(c)-1(f)判斷下一步爬行方向，根據背景像素點的位置，貪吃蛇可以向右下、左下、右、左爬行，但不切斷字符像素；特殊情況為圖1(g)所示，貪吃蛇進入字符凹陷區(qū)域，無法向下行進，則回溯到前一點，同時將該點標記為字符像素點。

圖1 貪吃蛇爬行規(guī)則Fig.1 Rules of snake’s crawling

本算法對手寫文本進行兩次切分，分別為粗切分和二次切分。粗切分主要分割非粘連字符和交錯字符，在此基礎上，結合寬度和寬高比閾值判斷粘連字符，并以候選粘連點作為貪吃蛇爬行的起點，進行粘連字符的二次切分。

1.2 基于多重約束規(guī)則的候選路徑優(yōu)化

貪吃蛇在文本圖像爬行后的原始軌跡存在冗余，本研究結合字符平均寬度、水平重疊率、分段投影特征建立路徑優(yōu)化規(guī)則，得到文本候選切分路徑。水平重疊率、單列投影特征定義如下。

定義1 左右兩字符塊在垂直方向上的重疊長度與兩字符塊寬度比值的最大值記為水平重疊率，數(shù)學定義為

(1)

其中，WL和WR分別為兩字符塊的寬度，XL為左側字符塊橫坐標的最大值，XR為右側字符塊橫坐標的最小值，XL≥XR。

定義2 分段投影特征，即以像素點(y，x)為界，將所在列像素點分為上下兩段，分別統(tǒng)計字符像素個數(shù)，用G1(y，x)和G2(y，x)分別表示點(y，x)上方和下方的字符像素個數(shù)。

將預處理后H×W的字符圖像用I表示，H為高，W為寬。其中I(h，w)=1表示字符像素，I(h，w)=0表示背景像素，h=1，2，…，H；w=1，2，…，W。假定路徑列表為P=[P1，P2，…，Pi，…，Pn]，其中Pi={(y1，x1)，(y2，x2)，…，(ym，xm)}表示一條路徑的坐標點集合，i=1，2，…，n。多重約束規(guī)則定義如下：

規(guī)則1 若Pi到Pi+k(0

規(guī)則2 若Pi左右兩側字符塊的LX≥TX，則刪除Pi。其中，TX為水平重疊率閾值，本文取TX=50%。

規(guī)則3 若Pi為非線性路徑，存在(y，x)∈Pi，G1(y，x)=0，則在從點(y，x)向上形成垂直路徑；G2(y，x)=0，則在點(y，x)向下形成垂直路徑，刪除原Pi。

規(guī)則4 若Pi到Pi+c(0

1.3 基于輪廓曲線極值和骨架特征的候選粘連點提取

水平手寫的文本粘連大多是由連筆或字間距較近造成的，粘連類型可分為簡單粘連和復雜粘連。如圖2所示，A、D區(qū)域都只有一筆粘連，屬于簡單粘連；B、C區(qū)域存在多筆粘連的同時還存在筆劃重疊，屬于復雜粘連。根據漢字內部筆劃緊湊，字間筆劃稀疏的特點，簡單粘連點一般在字間筆劃薄弱的位置，復雜粘連點處的結構與漢字內部結構相似，多為筆劃交叉點。本研究基于輪廓曲線局部極值提取簡單粘連點，基于骨架特征提取復雜粘連點，并結合筆劃估計寬度、兩點距離、四方向筆段長度、鄰域像素個數(shù)建立粘連點篩選機制，確定候選粘連點。相關定義如下。

圖2 粘連點類型Fig.2 Adhesion point type

定義3 字符輪廓曲線由每列字符像素邊界點坐標組成，字符上輪廓曲線如式(2)所示：

Sup(x)=min{y|I(y，x)，x=1，2，…，W}

(2)

字符下輪廓曲線如式(3)所示：

Sdown(x)=max{y|I(y，x)，x=1，2，…，W}

(3)

定義4 水平和豎直掃描二值圖像，統(tǒng)計連續(xù)字符像素個數(shù)mi(其中1

(4)

定義5 某一特征點分別在0°、45°、90°、135° 4個方向上連續(xù)字符的個數(shù)為四方向筆段長度。

采用差分遍歷向量法分別計算上輪廓曲線的波峰和下輪廓曲線的波谷，得到局部極值點，將其加入粘連點集合。為了更加直觀，以圖像左下角作為原點繪制輪廓曲線，如圖3所示。利用細化算法[17]提取字符骨架，掃描字符像素點，若其八鄰域內有3個及以上字符像素，則認為該點為骨架點。由于骨架提取過程中存在一定程度的毛刺和畸變，導致提取到冗余骨架點，如圖4所示。

圖3 輪廓曲線與極值點Fig.3 Contour curves and extremum points

圖4 骨架點提取Fig.4 Skeleton point extraction

定義規(guī)則對冗余骨架點進行過濾。

規(guī)則5 若骨架點所在的四方向筆段長度均小于Um，認為該點為孤立的噪點，則刪除該點。

規(guī)則6 若兩個骨架點距離較近，滿足Ds

如圖5所示，經過濾，去掉了大多數(shù)冗余點，將其加入粘連點集合。大多數(shù)情況下，粘連點位于字符中間，且鄰域像素密度較小，與輪廓粘連點距離較近。將粘連點集合對應到粘連字符原圖，建立粘連點篩選規(guī)則，確定候選粘連點。

圖5 骨架點過濾Fig.5 Skeleton point filtration

規(guī)則8 保留距離輪廓粘連點2Um范圍內的骨架點。

規(guī)則9 保留相鄰Um范圍內鄰域像素個數(shù)最小的粘連點。

1.4 基于貪吃蛇的文本切分算法

1.4.1 基于貪吃蛇的手寫中文文本粗切分算法

對手寫文本首先進行粗切分，使非粘連字符和交錯字符得到正確切分。根據手寫文本字間筆劃稀疏的特點，粗切分起點由垂直投影值和筆劃寬度自適應得到。垂直投影列表記為V=[V1，V2，…，VW]，則粗切分起點(y，x)應符合式(5)定義：

(5)

其中ξ是調節(jié)參數(shù)。ξ越大，蛇的初始爬行路徑越多，本研究取ξ=3，得到起點集合A(x) ={(y，x|y=1，x∈[1，W]}。

基于貪吃蛇的手寫中文文本粗切分算法(SnakeSegmentB)實現(xiàn)過程如下：

(1) 輸入二值化的文本圖像I。

(2) 初始化切分路徑列表P，一次爬行軌跡集合Pi。

(3) 計算垂直投影列表V和筆劃寬度Um。

(4) 計算貪吃蛇爬行起點集合A(x)。

(5) 遍歷A(x)，依據第1.1節(jié)貪吃蛇爬行規(guī)則向下爬行，將有效軌跡坐標加入Pi；若Pi終點坐標在圖像最后一行，則將Pi加入到P；否則，Pi置空；直到遍歷結束。

(6) 對P，應用規(guī)則1-4。

(7) 輸出手寫文本切分路徑列表P。

圖6示出了文本圖像粗切分過程。圖6(a)為輸入的文本圖像；圖6(b)為圖像的垂直投影直方圖，結合筆劃寬度自適應得到貪吃蛇的爬行起點；圖6(c)為貪吃蛇的原始爬行軌跡。可以看出：進入字符凹陷區(qū)域的貪吃蛇無法向下行進，需進行回溯，最終到達文本底部的原始軌跡存在重疊，且兩字符之間有多條路徑；由于爬行起點設置比較寬泛，當蛇經過字符間較窄區(qū)域之后，會得到相同軌跡。因此，采用多重約束規(guī)則對原始路徑進行優(yōu)化，得到粗切分路徑，如圖6(d)所示。粗切分結果中仍存在粘連字符，需進一步處理。

(a)骨架點提取

(b)垂直投影直方圖

(c)貪吃蛇原始爬行軌跡

(d)應用規(guī)則后的切分路徑圖6 文本圖像的粗切分過程Fig.6 Rough segmentation process of text image

1.4.2 基于貪吃蛇的手寫中文文本二次切分算法

手寫文本粗切分后，粘連字符易被當成一個字，造成分割不足。傳統(tǒng)的切分算法處理粘連效果不好，如圖7所示。

圖7 傳統(tǒng)算法切分圖Fig.7 Segmentation graphs by traditional algorithms

由于漢字的方塊字特點，其寬度、寬高比一般在一定范圍內。因此，設置寬度、寬高比閾值選出粘連字符，進行基于貪吃蛇算法的二次切分，主要包括提取候選粘連點和篩選分割路徑。基于貪吃蛇的手寫中文文本二次切分算法(SnakeSegmentT)實現(xiàn)過程如下：

(1) 輸入二值化的文本圖像I，手寫文本切分路徑列表P。

(2) 初始化粘連點集合E(i)和一次爬行軌跡集合Pi。

(3) 遍歷P，計算字符的寬度Wei、寬高比Rwhi、平均寬度Wavgc和平均寬高比Ravg。

(4) 若Wei>Wavgc&&Rwhi>Ravg，則判定其為粘連字符，計算輪廓曲線局部極值點，加入E(i)；提取骨架點并應用規(guī)則5和規(guī)則6，加入E(i)。

(5) 對E(i)應用規(guī)則7-9，得到二次切分起點B(x) ={(y，x|y∈[1，H]，x∈[1，W]}。

(6) 遍歷B(x)，檢測粘連點四方向的最短筆段，進行像素反轉，令貪吃蛇在該粘連點處雙向爬行，對于一個粘連區(qū)域，可能形成多段路徑，因此Pi=l1∪l2∪…lj∪…∪lk，lj(j=1，2，…，k)表示從粘連點出發(fā)的一段路徑。

(7) 若Pi終點坐標在圖像最后一行，則將Pi加入到P；否則，Pi置空。

(8) 對粘連字符形成的Pm到Pm+k，應用規(guī)則1-4。

(9) 循環(huán)步驟(2)-(8)，直到判定沒有粘連字符。

(10) 輸出手寫文本切分路徑列表P。

圖8示出了粘連字符圖像二次切分過程。圖8(a)為通過寬度閾值和寬高比閾值選出的粘連字符圖像，其示出了所提取的候選粘連點。圖8(b)示出了粘連點像素的反轉，即字符在粘連點處的斷開。之后以候選粘連點作為起點，應用貪吃蛇切分算法，并進行路徑優(yōu)化，得到二次切分結果，如圖8(c)所示?？梢钥闯?，本研究提出的算法在粘連字符切分中獲得了較好的效果。經過粘連點提取算法處理，分割點一般包含在候選粘連點中，結合貪吃蛇切分算法可使分割路徑更加準確。

圖8 粘連字符二次切分Fig.8 Additional segmentation of adherent characters

2 基于部首識別的過切分合并

2.1 基于輪廓編碼的部首筆段提取

部首的筆段信息相對其他特征更具有代表性，現(xiàn)有的筆段提取方法多采用細化的方式，但細化過程計算量較大，且會產生不可預知的效果，并不適于提取手寫部首的筆段。

圖像的輪廓包含著比其他位置更多的信息，因此本研究設計了基于輪廓編碼的部首筆段提取方法，主要步驟如下：

(1)提取字符輪廓，并對輪廓像素點進行Freeman編碼[18]。

(2)基于連續(xù)相同或相近方向碼提取線段。

(3)根據傾斜角對線段進行聚類。

(4)合并傾斜角相同或相近的線段，得到最終筆段。

通過八鄰域模板檢測輪廓，規(guī)定每個輪廓點最多有2個相鄰點，以保證輪廓編碼的唯一性。Freeman鏈碼是一種依據鄰域點和中心點的連線方向對曲線編碼的方法，本研究采用可以更好描述輪廓形狀的八鄰域編碼方式(如圖9(a)所示)，分別用1，2，…，8等8個鏈碼值表示當前點與中心像素點P的鄰接方向，編碼結果為一系列具有特定長度和方向的連續(xù)直線段，如圖9(b)所示。

圖9 輪廓編碼Fig.9 Contour encoding

由于噪聲以及筆劃邊緣不光滑等原因，導致輪廓鏈碼在局部范圍內快速變化，不利于后續(xù)的線段提取，因此需要對鏈碼進一步平滑。令C={f1，f2，…，fn}，表示當前輪廓的鏈碼集合，n為輪廓所包含的像素點個數(shù)，Cj={fj-s+1，fj-s+2，…，fj}表示以鏈碼fj結尾、長度為s的一段鏈碼，即Cj?C，Cj中各鏈碼元素及其組合方式共同確定是否對f(2j-s+1)/2進行平滑。平滑復雜程度與s的大小有關，s越大越復雜；本研究取s=3，只考慮被平滑點的前后兩點。通過分析輪廓鏈碼特征，待平滑邊緣分為直角型和鈍角型兩種類型，如圖10所示。不同類型判斷依據如式(6)所示。為簡要起見，表1示出了部分直角型和鈍角型的鏈碼串及輪廓形狀。

圖10 待平滑類型Fig.10 The type to be smoothed

(6)

len(fi)表示一段具有相同fi鏈碼的長度。若Cj為直角型，且len(fi-2)和len(fi)均小于Um，則按式(7)平滑fi -1；否則，按式(8)平滑fi-1；若Cj為鈍角型，且fi-2=fi，則令fi-1=fi；否則，判斷l(xiāng)en(fi-2)和len(fi)，若兩者都小于Um，則不改變fi-1的值；否則按式(8)平滑fi-1。平滑后鏈碼如圖11所示。

fj-1=(fj-2+fj)/2

(7)

(8)

表1 部分直角型、鈍角型鏈碼串及輪廓形狀Table 1 Part of right angle，obtuse angle chain and outline shape

(a)平滑前 (b)平滑后圖11 平滑后鏈碼Fig.11 Smoothed chain code

一條線段滿足：①最多包含3種鏈碼，即fi-1、fi、fi+1；②假定fi為主鏈碼，則fi可表示該線段方向，fi-1、fi+1分布在鏈碼轉折處，經過鏈碼平滑，出現(xiàn)次數(shù)很少。因此，可依據主鏈碼提取線段。一個筆劃可能被提取為多條線段，而屬于同一筆劃的多條線段之間具有相同或相似的傾斜角，并且線段距離不超過筆劃寬度。設L為線段集合，其元素為五元組(xi，yi，xj，yj，θ)，其中xi、yi、xj、yj為線段端點坐標，θ為線段與X軸正方向的夾角。Mseg為聚類集合，其元素為三元組(θi，Nsegi，Jsegi)，其中θi為該類中心，Nsegi為該類線段個數(shù)，Jsegi為該類線段集合?；谳喞幋a的部首筆段提取算法(Stroke Extract)的實現(xiàn)過程如下：

(1) 輸入過切分字符圖像。

(2) 初始化線段集合L，聚類集合Mseg。

(3)輪廓檢測，編碼并平滑，得到鏈碼集合C。

(4) 遍歷C，若fi=fi-1，則fi屬于當前線段；否則，計算|fi-fi-1| mod 4的值，若其值為2，當前線段Li提取完畢；若|fi-fi-1| mod 4≠2，分別計算當前線段起點與fi-1、fi兩點連線的θi-1、θi，若|θi-1-θi|≤5°，則fi屬于當前線段，否則當前線段提取完成；若len(Li) ≥Um，則加入集合L；直至遍歷結束，得到線段集合L。

(5)遍歷L，取當前線段θ，若Mseg中存在|θi-1-θi|≤5°，則將當前線段加入Jsegi，并按式(9)更新θi，按式(10)更新Nsegi：

(9)

Nnumi=Nnumi+1

(10)

若|θi-1-θi|>5°，新增聚類中心θ，初始化Nsegi=0，Jsegi=?；直至遍歷結束，得到聚類集合Mseg；在Mseg中，每一類中的線段可能屬于同一筆段，也可能屬于多個筆段，根據平行線間距離和線段重疊部分來判斷是否對兩條線段進行合并。

(7) 輸出筆段集合HStroke={(xi，yi，xj，yj，θ)}。

筆段提取效果如圖13所示。

圖12 線段距離Fig.12 Line distanceion

圖13 筆段提取Fig.13 Stroke extraction

2.2 基于多級分類的部首識別

部首作為漢字的一部分，結構相對簡單，一級常用漢字中包含左右結構的部首只有幾十類，且大多數(shù)在七筆畫以內，因此本研究采用特征提取的方式識別部首，選取有代表性的特征作為識別依據。本研究結合筆段類型、筆段長度、筆段個數(shù)、相對位置、交叉點、橫縱交截、寬高比多維特征對部首進行識別。

部首的筆段主要分為橫、豎、撇、捺4種類型，輪廓鏈碼1、5對應橫筆段，3、7對應豎筆段、2、6對應撇筆段，4、8對應捺筆段。根據輪廓編碼的不同，筆段長度的計算方式也不同，如式(11)、(12)所示：

(11)

(12)

在部首結構中，筆段存在相離、相連、相交3種位置關系，相連在書寫過程中較為隨意，因此結合相離和相交兩種位置關系提取筆段特征。對于相離的兩筆段，其相對位置主要有上下、左右和斜方。對于相交筆段，使用交點個數(shù)作為特征，每類部首包含的交點個數(shù)一般不同。

橫縱向交截特征可在一定程度上表現(xiàn)部首筆劃緊密程度，其定義如下。

定義6 在圖像每一行插入水平射線，在每一列上插入垂直射線，射線上像素的黑白交替變化次數(shù)即為橫縱向交截特征。

經過筆段提取之后，每個部首用一個字典序列Fi={Y：{‘Ynum’：Ynums，‘Yseg’：Ysegs}}表示其筆段信息。其中，Y={t|t=T，H，S，P}，為筆段類型，T、H、S、P分別表示橫、豎、撇、捺4類筆段。由于手寫漢字存在一定差異，并不能保證橫平豎直，因此根據圖14設置筆段模糊分類范圍；Ynum為某一類型筆段的數(shù)目，Yseg為該類筆段集合。在筆段提取過程中，曲線、折線、彎鉤等被線段化，所以部首所提取到的筆段數(shù)一般大于其實際筆畫數(shù)。

圖14 筆段模糊分類范圍Fig.14 Stroke segment classification scope

4種筆段可以大體反映一個部首的形狀，雖然4種筆段有許多組合方式，但并不是任意的組合就可以形成部首，這一點在簡單部首中表現(xiàn)更為明顯。多級分類可以加快識別速度，因此首先依據筆段數(shù)目進行一級分類，當總筆段數(shù)sum(Ynums)≤TSN時定義為簡單筆段，當sum(Ynums)>TSN時，定義為復雜筆段，其中TSN為筆段數(shù)閾值。經實驗分析，本研究取TSN=3。

簡單筆段的部首可以直接通過筆段類型、數(shù)目和位置結構來判斷。 當總筆段數(shù)sum(Ynums)≤3時，主要有丨、丿、丶、亅、卜、亻、冫、乚、氵、彡、彳、刂、忄、卩、厶15組可能的情況，而這15組部首首先在筆段組合方式上就有很大差異，如“彳”的筆段組合可表示為“0120”，即“彳”由一豎兩撇筆段組成，而“乚”由于手寫習慣的不同，在筆段提取后，可能存在“1200”、“1110”、“1101”幾種情況。根據筆段不同的組合方式可以將簡單筆段的大部分部首區(qū)分開。對于特殊情況，如“亅”和“卜”都是由一豎和一捺組成，且在筆段長度上也沒有明顯特征，但兩者捺筆段的位置是明顯不同的，如圖15所示。因此，在一級分類的基礎上，簡單筆段的部首識別，根據筆段類型及其數(shù)目的不同組合方式進行二級分類，一些部首在二級分類后已經可以得到分類結果，而相近筆段的部首再結合筆段長度和位置特征設計三級分類器完成識別。

圖15 筆段相對位置Fig.15 Relative position of stroke segments

復雜部首，筆段位置關系也更加復雜，直接通過筆段位置判斷會包含大量的計算。因此采用模板匹配的方式進行識別。將橫、豎、撇、捺4種筆段信息作為前4維特征分量的基礎上，加入交點個數(shù)、橫向最大交截數(shù)、縱向最大交截數(shù)、寬高比四維特征，用于復雜部首的識別。特征模板的建立基于課題組收集到的陜西省某高中課堂手寫數(shù)據，從中分割出部分部首，進行預處理和歸一化，每類部首最終保留5組特征向量。識別過程使用加權歐氏距離計算待識別字符與模板字符的距離：

(13)

其中：n為特征維數(shù)；xi為待識別字符的第i維特征；μi為第i維特征的均值；σi為第i維特征的標準差；βi是第i維特征的修正系數(shù)，βi=0表示該特征未提取到，其他情況下βi=1。

部首識別(RadicalRecognition)的實現(xiàn)過程為：

(1) 輸入待識別字符圖像，筆段集合HStroke={(xi，yi，xj，yj，θ)}。

(2) 初始化字典序列F={Y：{‘Ynum’：Ynums，‘Yseg’：Ysegs}}。

(3) 遍歷HStroke，根據θ進行筆段分類，更新Ynum，將(xi，yi，xj，yj)加入Yseg。

(4) 若sum(Ynums)≤TSN，進行二級分類，若筆段特征與候選樣本完全一致，則識別輸出；若屬于筆段相近字符，進行三級分類，若筆段特征與候選樣本完全一致，則識別輸出；否則，標記為拒識字符。

(5) 若sum(Ynums)>TSN，提取字符交點特征、橫縱向交截特征、寬高特征，與筆段信息組成特征向量。

(6) 模板匹配，計算d2，若min(d2)

(7) 輸出分類結果。

2.3 基于部首識別的過切分字符合并算法

經上述切分，同一漢字由于左右部分間距過大，會出現(xiàn)過切分現(xiàn)象。在GB2312—80的3755類一級漢字中，包含了2 049類左右結構的漢字，177類左中右結構的漢字，占多半部分，因此，過切分字符的合并對于文本切分也非常重要。過切分的字符中一般包含部首，其作為漢字特有的結構，雖然手寫風格多變，但相對位置并不會改變。如“亻”、“氵”一般出現(xiàn)在漢字左邊，“刂”、“攵”出現(xiàn)在右邊，“阝”左右都可組成漢字。因此，可利用部首的結構特征在字符合并之前確定合并方向，進一步計算待合并字符局部上下文的幾何置信度和識別置信度，取置信度最高者作為最終合并結果。

根據中文形態(tài)特征，部首的書寫一般比單字窄，又由于每位書寫者所寫成的單字寬高比值變化不大。由此，可得出部首的寬高比與單字的寬高比存在較大差距。設置寬高比閾值TWH，對部首和單字分類，如式(14)所示：

(14)

其中，Rwhi為每個待識別字符的寬高比，取TWH=0.5。

設Ci， j為連續(xù)路徑Pi，Pi+1，…，Pj之間的組件，該組件寬度和高度分別為wi， j和hi， j。組件Ci， j為一個漢字的幾何置信度為

(15)

由幾何特征zk(k=1，2，3)及權重因子wk共同決定：

(1)組件Ci， j的平均寬度差異度為

(16)

其中Wavgc為平均字符寬度。

(2)組件Ci， j的平均寬高差異度為

(17)

(3)組件Ci， j的字內密集度為

(18)

其中，ds，s+1表示相鄰組件最小外接矩形之間的距離。本研究中，w1=0.3，w2=0.4，w3=0.3。

識別置信度通過將待識別圖像輸入到預先訓練好的卷積神經網絡[19]中得到。經大量實驗驗證，該識別模型在所收集的樣本數(shù)據中，識別準確率可達到93.87%。將組件Ci， j的識別置信度記為Oi， j，則組件Ci， j的合并置信度如式(19)所示：

Ki， j=ηZi， j+(1-η)Oi， j

(19)

其中，η為幾何置信度和識別置信度的占比系數(shù)，0≤η≤1，本研究取η=0.45。

基于部首識別的過切分合并算法(Radical-Merge)的實現(xiàn)過程如下：

(1) 輸入二值化的文本圖像I，手寫文本切分路徑列表P。

(2) 遍歷P，計算字符的寬度Wei、寬高比Rwhi、平均寬度Wavgc和平均寬高比Ravg。

(3) 若Rwhi≤TWH，則通過Stroke Extract算法提取該字符筆段信息，執(zhí)行步驟(4)；否則，執(zhí)行步驟(7)。

(4) 通過RadicalRecognition算法進行識別，若得到分類結果，執(zhí)行步驟(5)；若RadicalRecognition拒識，執(zhí)行步驟(6)。

(5) 根據步驟(4)的分類結果計算字符合并方向，在此方向上取3Wavgc范圍內的字符計算不同組合方式的Ki， j，取max(Ki， j)作為合并結果，刪除Pi+1，Pi+2，…，Pj-1。

(6) 在左右方向上分別取3Wavgc范圍內的字符計算不同組合方式的Ki， j，取max(Ki， j)作為合并結果，刪除Pi+1，Pi+2，…，Pj-1。

(7) 循環(huán)執(zhí)行步驟(3)-(6)，直至Rwhi>TWH。

(8) 根據P切分文本圖像，并凈化。

(9) 輸出文本切分結果。

圖16示出了過切分字符的合并過程。圖中，WHR表示字符寬高比，OCR表示識別置信度?！般摺钡膶捀弑确线^切分字符，對其識別之后，可判斷出合并方向為向右，計算其右側鄰域內字符合并的置信度得出最優(yōu)合并結果。由于大部分部首位置結構相對明確，合并方向單一，大大降低了計算量。

圖16 過切分合并Fig.16 Over-segmentation merge

3 實驗結果與分析

收集了陜西省某高中期末考試語文試卷中300張手寫文本圖像，對本研究提出的算法進行實驗驗證。圖17示出了一個文本的切分過程。如圖17(a)所示，首先基于水平投影算法對文本圖像進行行切分，共得到1 542行手寫數(shù)據。圖17(b)為基于貪吃蛇算法的文本粗切分結果，圖17(c)為基于貪吃蛇算法的二次切分結果，圖17(d)為基于部首識別的過切分字符合并結果。從圖中可以看出，本研究提出的算法取得了較好的切分效果，能夠準確地切分到每個漢字的主體結構。

基于貪吃蛇算法進行手寫文本二次切分時，有一些粘連字符存在共享筆劃、多重粘連、粘連區(qū)域較大等情況，導致切分路徑不能精確分割字符邊緣，但通過手寫漢字識別模型驗證可知，這種情況對漢字識別準確率的影響極小。因此，本研究認為這種情況屬于正確切分。本研究將錯誤情況分為3種，分別為漏切、過切和誤切，見圖18。圖18(a)中，“一”和“樣”有共同筆畫，由于無法正確提取到粘連點，造成漏切。圖18(b)中，“確”被分為了“石”和“角”，這兩部分的寬度以及寬高比接近單字，且可以單獨成字，識別置信度較高，導致未能合并。圖18(c)中，由于“長”右下方的捺筆段與“官”水平重疊率較高，應用多重約束規(guī)則之后，判定該筆段所屬“官”，造成誤切。

(a) 手寫文本數(shù)據

(b)基于貪吃蛇算法的文本粗切分

(c)基于貪吃蛇算法的二次切分

(d)基于部首識別的過切分字符合并圖17 文本切分Fig.17 Text segmentation

圖18 錯誤情況Fig.18 Error cases

為驗證本研究提出的算法的有效性，采用切分正確率、粘連字符切分正確率、過切分字符合并正確率作為評價標準，數(shù)學定義分別如(20)、(21)、(22)所示：

(20)

其中，u為切分正確率，TP為切分正確的字符個數(shù)，TN為切分錯誤的字符個數(shù)。

(21)

其中，q為粘連字符切分正確率，AP為切分正確的粘連字符個數(shù)，AN為誤切數(shù)，AW為漏切數(shù)。

(22)

其中，r為過切分字符合并正確率，OP為正確合并數(shù)，OM為欠合并數(shù)。

對1 542條手寫數(shù)據進行實驗，共包含27 372個字符，統(tǒng)計實驗結果：TP、TN、AP、AN、AW、OP、OM分別為22 487、4 885、12 163、1 329、1 934、8 101、1 622。可以看出：學生手寫數(shù)據存在大量粘連情況，切分過程中，較容易出現(xiàn)過切分現(xiàn)象。根據式(20)-(22)計算可得出，本研究提出的算法在粘連字符切分方面，可達到78.84%的準確率，對于過切分字符，合并正確率在83.32%，整體切分正確率為82.15%。

為進一步驗證本文算法的有效性，表2示出了不同切分方法的統(tǒng)計結果。

表2 不同切分方法對比Table 2 Contrast of different segmentation methods

從表中可以看出，本研究提出的方法在獲得較好切分效果的同時，平均處理時間最短。本研究利用貪吃蛇算法進行粗切分，之后僅針對粘連字符進行二次切分，在過切分合并過程中，通過部首的位置特征確定合并方向，減少了大量的計算。

4 結語

手寫文本變化多端，字符間極易發(fā)生粘連、交錯、重疊等現(xiàn)象，切分過程中也極易出現(xiàn)過切分現(xiàn)象。針對以上問題，本研究提出的基于貪吃蛇算法和部首識別的手寫文本切分方法取得了較好的效果，且在時間效率上優(yōu)于其他算法。但對于一些復雜結構的字符粘連情況，如共享水平筆畫、豎直筆畫重疊等，很難準確找到粘連位置將字符完整分開。因此，需進一步研究復雜粘連字符的分割。另外，在過切分合并過程中，由于一些偏旁部首也可以獨立成字，當書寫者書寫的字體寬高特征不明顯時，很難判斷當前字符是作為偏旁部首還是作為單字，可進一步結合語義對切分結果進行后處理。