幾何代價和語義－識別代價融合的脫機手寫漢字切分方法

2023-10-08 12:59:34

專利名稱：幾何代價和語義－識別代價融合的脫機手寫漢字切分方法
技術領域：
幾何代價和語義-識別代價融合的脫機手寫漢字切分方法屬於字符識別領域。
背景技術：
Optical Character Recognition(OCR)技術一直是模式識別中的熱點問題，針對漢字識別的漢字OCR技術也有了二十餘年的發展歷史。脫機漢字的識別是指通過掃描儀、數位相機或者攝像頭獲取的漢字圖像進行識別(圖3)，脫機手寫漢字的識別一直是一個難點。這是因為人的自然書寫相對來說具有比較大的自由度，而且它不能像聯機手寫漢字那樣提供更多額外的信息。
脫機漢字識別中涉及到一個關鍵的問題就是字符的切分，這是因為現行的分類器一般只是對單獨圖像做出識別和判決，它需要首先確定哪些部分是屬於同一漢字的。對於人眼來說，將相鄰漢字分開並不成為問題，但是對於機器來說，這並不是容易的。傳統的切分技術基本上都依賴於幾何特徵作判決，一部分方法同時用到了識別器給出的置信度信息。
然而事實上從人類閱讀的情況來看，僅僅依賴於以上的信息是不夠的，大腦在完成把相鄰漢字符圖像分開的過程中更重要的是考慮相鄰漢字結合的緊密程度，傾向於接受從語法和語義上更可以接受的切分結果。
漢字具有非常豐富的結構，其中相當一部分漢字具有左右的字體結構，在從左到右的書寫習慣下，脫機漢字切分一個無法避免的問題就是左右結構的漢字常常被分開，例如「村莊」的「村」字切分成「木寸」，對於這樣的切分，識別器也往往給出非常大的置信度，所以單純依賴於分類器置信度的方法也是不可靠的。無論是利用幾何代價的方法還是利用識別器置信度的方法，都忽視了漢字切分中實質上最有意義的特徵——語義信息。
人們對於語言模型的研究已經有很長的時間，基於統計方法的統計語言模型在實踐中取得明顯的效果，特別是在語音識別和漢字識別的後處理技術中。主要是通過二元或者三元語法的隱馬爾科夫模型(HMM)來進行識別和判決。
本發明主要利用了基於二元語法的隱馬爾科夫模型來得到字符切分的語義-識別置信度，然後同時將字符切分的幾何代價和字符識別的置信度信息三者結合起來，得到一個統一的切分識別代價，這一過程實際把字符的切分、識別和後處理三個過程有機地結合在一起，當切分方法決定之後字符的識別與後處理也同時完成了。實驗證明，本發明是高速有效的。本發明同時提出了一種模型，統一了脫機手寫漢字的切分、識別和後處理，這種漢字的切分思路是其他文獻中沒有出現的，具有一定的創新性。

發明內容
本發明的目的在於實現高準確率的脫機手寫漢字字符切分。本方法的處理對象是輸入的脫機手寫漢字的行圖像(圖4給出了手寫行圖像獲取的一般過程)，首先通過一些圖像分析的方法，提取字符的筆段，然後由筆段合併為子字符，同時提取一系列的幾何特徵和參數進行評價，然後根據這些幾何代價用K最短路徑的優化方法尋找前K選幾何代價最優的切分方式，然後對每種切分方式用基於二元語法的語言模型進行評價，得到相應的語義-識別置信度，然後將這兩個代價結合得到最終的評價從而挑選出最有的字符切分方式。
本發明包含理論推導，參數估計，特徵提取，候選集生成以及分類器判決這幾個部分。
1理論部分1)基於統計語言模型的HMM語義-識別置信度x1x2...xn——行圖像切分後的字符圖像；NCand——識別核心對單字字符圖像給出的識別候選字的個數，這是一個識別核心的性能參數，因而是常數，而與輸入字符圖像無關；ci，j——由識別核心給出的第i個字符圖像xi的第j個候選識別結果(識別核心根據識別距離由小到大的升序排列識別候選字)；一般漢字識別的後處理過程是要極大化在給定圖像序列下的字符後驗概率，使得滿足後驗概率最大化的字符串作為我們的識別字符串，即 利用Bayesian公式，我們有P(c1,k1,c2,k2,...,cn,kn|x1,x2,...,xn)=P(x1,x2,...,xn|c1,k1,c2,k2,...,cn,kn)P(c1,k1,c2,k2,...,cn,kn)P(x1,x2,...,xn)---(1)]]>字符識別的後處理過程一般依據如下的假設來計算上式①由於在給定字符序列的條件下，字符圖像出現概率是相對獨立的，而且每幅圖像只和它代表的字符有關，與其它字符沒有關係，所以P(x1,x2,...,xn|c1,k1,c2,k2,cn,kn)=i=1nP(xi,|ci,k1)=i=1nP(ci,k1|xi)P(xi)P(ci,k1)---(2)]]>第二個等號根據的是Bayes公式。
②在不考慮語料庫的情況下，各個漢字出現基本上是等概率的，因此認為各個字符出現的先驗概率近似一致，即每個字符我們都認為它有等可能出現的概率；③假定P(c1，k1，c2，k2，...，cn，kn)滿足二元語法模型，即僅僅是每個漢字的前一個漢字對於後一個漢字的出現有影響，那麼P(c1,k1,c2,k2,cn,kn)=P(c1,k1)i=2nP(ci,ki|ci-1,ki-1)---(3)]]>
事實上從統計語言學的角度來說，採用三元語法模型更符合實際情況，對應的公式為P(c1,k1,c2,k2,cn,kn)=P(c1,k1)P(c2,k2,c1,k1)i=3nP(ci,ki|ci-1,ki-1ci-2,ki-2)---(4)]]>但是考慮到時間複雜度和空間複雜度，只取二元語法模型就足夠了。
綜合(1)(2)(3)，得到P(c1,k1,c2,k2,...,cn,kn|x1,x2,...,xn)=i=1nP(ci,ki|xi)(P(c1,k1)i=2nP(c1,k1|ci-1,ki-1))i=1nP(xi)P(x1,x2,...,xn)i=1nP(ci,ki)]]>(5)根據假設②，並且注意到i=1nP(xi)]]>和P(x1，x2，...，xn)在字符圖像序列給定的情況下是常數，那麼上式說明P(c1,k1,c2,k2,...,cn,kn|x1,x2,...,xn)=i=1nP(ci,ki|xi)(P(c1,k1)i=2nP(c1,k1|ci-1,ki-1))]]>(「∝」符號表示「與……成正比」)。
OCR的後處理技術就是要在識別候選字集cij1≤i≤n 1≤j≤NCand中挑選出最優的狀態序列，所謂最優，就是極大化i=1nP(Ci,ki|xi)(P(c1,k1)i=2nP(ci,k1|ci-1,ki-1))]]>它從某種程度上反映了識別的語義-識別置信度。
設k1*k2*...kn*=argmax1k1,k2,...,kNNCandi=1nP(c1,k1)(P(c1,k1)i=2nP(ci,ki|ci-1,ki-1)),]]>則可以挑出最優的候選字序列c1,k1*c2,k2*...cn,kn*]]>這樣就轉化為HMM中的問題，如何在給定觀測序列估計最優的狀態序列，Viterbi方法是解決這個問題的經典算法，它的時間複雜度是O(nNCand2)。NCand2是識別候選字的個數，n是合併後的字符圖像的塊數。
Viterbi算法描述如下令Q[n][NCand]是一個二維數組，其中Q[t][j]保存了從第一個字符圖像某個候選字到字節點ct，j的最大可能候選字選擇方式所具有的概率的對數值，不難看出1≤t≤n 1≤j≤NCand另外取一個二維指針數組Path[n][NCand]用於記錄計算過程。
初始化t＝1，1≤j≤NCandPath[1][j]＝NULL
Q[1][j]＝logP(c1，j)+log(c1，j|x1)遞歸2≤t≤n，對1≤j≤NCandQ[T][j]=max1lNCand{Q[t-1][l]+logP(ct,j|ct-1,l)}+logP(ct,j|xt),j|]]>l*=argmax1lNCand{Q[t-1][l]+logP(ct,j|ct-1,l)}]]>Path[t][j]指向字節點ct-1，l*， 即字節點ct，j的父節點為ct-1，l* 終止t＝nj*=argmax1jNCandQ[n][j],]]>最優字節點為cn，j*。 回溯Path[n][j*]所指的路徑，輸出路徑上的每個字節點，得到最優狀態序列作為我們的識別結果，同時得到最大可能路徑的概率的對數值Q[n][j*]。
2)幾何代價與HMM語義-識別代價的融合s1，s2，...，sl——子字符圖像序列；x1，x2，...，xn——子字符圖像合併後的字符圖像序列；NCand——識別核心對單字字符圖像給出的識別候選字的個數，如前所述，是個常數；ci，j——由識別核心給出的第i個字符圖像xi的第j個候選識別結果(識別核心根據識別距離由小到大的升序排列識別候選字)；與已知切分的識別後處理不同的是，我們需要極大化後驗概率，也就是說在筆段合併結果給定情況下，極大化子字符合併方式和識別結果的後驗概率P(x1x2...xn，c1，k1c2，k2...cn，kn|s1s2...sl)根據恆等式P(x1x2...xn,c1,k1c2,k1...cn,kn|s1s2...sl)=P(c1,k1c2,k2...cn,kn|x1x2...xn,s1s2...sl)P(x1x2...xn|s1s2...sl)]]>當切分好圖像給定後，識別過程只與切分好的圖像x1，x2，...，xn有關，與筆段合併結果無關，因此上式第一項的條件裡面可以省略s1s2...sl，簡化為P(x1x2...xn,c1,k1c2,k1...cn,kn|s1s2...sl)=P(c1,k1c2,k2...cn,kn|x1x2...xn)P(x1x2...xn|s1s2...sl)---(6)]]>這樣我們將我們需要極大化的後驗概率分成兩個部分，第一部分是我們前面提到的語義-識別置信度，後一部分就是子字符圖像合併的幾何代價，代入前面的(5)
P(x1x2...xn,c1,k1,c2,k2,...,cn,kn|s1s2...sl)]]>=i=1nP(ci,ki|xi)(P(c1,k1)i=2nP(ci,ki|ci-1,ki-1))i=1nP(xi)P(x1,x2,...xn)i=1nP(ci,ki)P(x1x2...xn|s1s2...sl)]]>我們將切分、識別和後處理融合在一個統一的模型下了。但是在實際操作中，因為不同的切分路徑得到的字符圖像的個數是不同的，而切分的字數越多，後驗概率值往往越小，所以我們不能直接比較合併字數不同的切分路徑的後驗概率。
為了消除因為合併字數不同帶來的影響，我們取P(x1x2...xn，c1，k1，c2，k2，...，cn，kn|s1s2...sl)的幾何均值，即P(x1x2...xn,c1,k1,c2,k2,...,cn,kn|s1s2...sl)n]]>作為我們的目標函數。
我們首先取(7)式的對數函數為logP(x1x2...xn,c1,k1,c2,k2,...,cn,kn|s1s2...sl)]]>=i=1nlogP(xi)-logP(x1,x2,...,xn)-i=1nlogP(Ci,ki)+logP(x1x2...xn|s1s2...sl)]]>(8)+i=1nlogP(ci,ki|xi)+logP(c1,k1)+i=2nlogP(ci,ki|ci-1,ki-1)]]>幾何均值對應著(8)式的算術平均值，即將(8)式除以n作為我們的代價函數。
1nlogP(x1x2...xn,c1,k1,c2,k2,...,cn,kn|s1s2...sl)]]>=1n(i=1nlogP(xi)-logP(x1,x2,...,xn)-i=1nlogP(ci,ki))+1nlogP(x1x2...xn|s1s2...sl)]]>(9)+1n(i=1nlogP(ci,ki|xi)+logP(c1,k1)+i=2nlogP(ci,ki|ci-1,ki-1))]]>如何計算上式也不是容易的，我們需要進一步的近似來簡化我們的模型。
對P(ci，ki)，根據在漢字識別的後處理過程中的假設，在語料庫未知的情況下，認為每個字在文本中出現的先驗概率是一致的，即P(ci，ki)是一個常數，從而1ni=1nlogP(ci,ki)]]>也是一個常數，對極大化過程無影響；對於P(x1，x2，...，xn)，它表示一列字符圖像出現的概率，而字符圖像的出現我們可以近似認為是一個獨立的過程，前面一個字符圖像出現對後面一個圖像的出現基本沒有影響，從而P(x1,x2,...,xn)=i=1nP(xi).]]>從而
1ni=1nlogP(xi)-1nlogP(x1,x2,...,xn)=1nlogi=1nP(xi)P(x1,x2,...,xn)=0]]>綜合上面的分析，我們將極大化(10)式簡化為極大化T=1n(i=1nlogP(ci,k1|xi)+logP(ci,ki|ci-1,ki-1))+1n(x1x2...xn|s1s2...s2)---(10)]]>令H=i=1nlogP(ci,ki|xi)+logP(c1,k1)+i=2nlogP(ci,ki|ci-1,ki-1)nG=logP(x1x2...xn|s1s2...sl)n]]>所以，我們令T＝H+G，用T值作為我們判斷最優切分的準則。其中H可以認為是這種合併方式的平均語義-識別代價，G是這種合併方式對應的平均幾何代價。
由於系統給出的幾何代價是一種距離的度量，我們選用一個單調減函數來近似P(x1x2...xn|s1s2...sl)。
令P(x1x2...xn|s1s2...s2)=e-(gg-1)---(11)]]>其中λ是一個正的常數，g表示由子字符塊s1s2...sl合併為字符圖像x1x2...xn的幾何代價，g表示子字符塊s1s2...sl所有可能的合併方式中最小的幾何代價，則G=1nlog(e-(gg--1)),]]>我們稱它為歸一化後的平均幾何代價。
2參數估計本算法在實現中需要估計一系列的參數。
首先我們需要為二元語法模型估計字符出現的先驗概率和字符間的轉移概率，為此目的我們必須收集與待切分的行圖像涉及內容一致的語料庫，這樣才能有針對性地反映我們的語義約束條件，由不同領域預料計算出來的各個字出現的先驗概率和字與字之間的轉移概率是不同的。如果不能選擇合適的預料庫，那麼系統的性能會受到比較大的影響。
例如如果需要切分的行圖像是手寫信封的地址，那麼我們就必須收集地址資料庫作為我們的語料樣本。
聲明如下的符號Nc——漢字c在語料樣本中出現的次數；Nc1c2——雙字詞c1c2在語料樣本中出現的次數；
N——語料樣本中的漢字總數；P(c)——漢字c在語料樣本中出現的概率；P(c2|c1)——在語料樣本中漢字c1後面緊接著出現漢字c2的概率；Psmooth(·)——平滑處理後的概率；M——語料樣本中包含的不同漢字的個數，國家一級漢字標準包括了常用漢字3755個，我們簡單地設M＝3755；1)估計字符的先驗概率，也就是P(c)計算每個漢字在語料庫中出現的總次數Nc，並計算語料庫中的漢字總數N，則 為對P(c)的估計。
2)計算字符的轉移概率如果我們採用二元語法模型，由於P(c2|c2)=P(c1c2)P(c1),]]>那麼我們首先計算c1c2這個詞在語料庫中出現的次數Nc1c2，然後用 作為對P(c2|c1)的估計。
3)數據的平滑這裡面涉及到另外一個重要問題就是數據的平滑，因為不是所有的漢字都在我們的語料庫中出現的。因此一部分字的先驗概率和轉移概率是無法計算的，在統計語言模型中，人們提出了各種方法用於數據的平滑。數據稀疏平滑處理的基本思想是當訓練數據不充分時，採用某種方式對概率進行調整和修補，以得到更為精確的概率。因為在1)和2)對先驗概率的估計和轉移概率的估計中對未出現事件的概率都低估成0，而所有事件概率之和總是1，所以它對出現過的事件給出過高的估計。因此，平滑的目標是通過將小概率(或零概率)調高一些，將大的概率調低一些，使得整體上的概率分布更均勻。平滑技術不僅解決了零概率問題，而且能夠在整體上提高語言模型的性能。
平滑技術將n-gram的高階模型與低階模型相結合，包括了回退(back-off)和插值(interpolation)兩種結合模式。
以二元語法為例，回退模式有如下形式Psmooth(c2|c1)=P(c2|c1)ifNc1c2>0(c1)P(c2)ifNc1c2=0]]>上式表明，若同現對c1c2在訓練語料中出現過，則用P(c2|c1)來近似轉移概率；否則，退回至低階模型P(c2)，γ(c1)為歸一化因子。
插值模式則是將高階模型與低階模型進行線性插值，有如下形式Psmooth(c2|c1)＝P(c2|c1)+γ(c1)P(c2)
插值模式與回退模式的區別在於處理大於零的概率值時，前者利用了低階模型的信息，而後者沒有利用。兩者的共同之處為處理零概率時均利用了低階模型的信息。由此可見，對低階模型信息的利用是平滑技術的關鍵所在。
目前，常用的平滑方法有Jelinek-Mercer平滑、Katz平滑、絕對摺扣平滑、Witten-Bell平滑、Kneser-Ney平滑等方法。各種平滑方法的性能隨著訓練語料規模的大小、n-gram模型的階數、語料庫的內容變化。其中，訓練語料庫規模對平滑技術性能的影響最大。
4)字符置信度的估計置信度反映識別的信息，即我們的識別結果究竟在多大程度上是可信的，這是我們在字符識別完成後需要做的工作。
x——待識別的字符圖像；cj(x)——由識別核心給出的對圖像x的第j個候選識別字(識別核心根據識別距離由小到大的升序排列識別候選字，因此c1(x)就是圖像x的首選識別候選字)；dj(x)——由識別核心給出的圖像x的第j個候選識別字cj(x)對應的識別距離，因此d1(x)表示圖像x的首選識別候選字對應的識別距離；NCand——識別核心對單字字符圖像給出的識別候選字的個數，該值為常數，只與識別核心本身有關；P(cj(x)|x)——圖像x識別為cj(x)的置信度，這是我們需要估計的對象。
一般分類器對圖像x，給出它的識別候選字c1(x)，c2(x)，...，cNcand(x)，同時給出相應的識別距離d1(x)，d2(x)，...，dNCand(x)，如何計算P(cj(x)|x) 1≤j≤NCand是一個比較複雜的問題，可以考慮以下的幾種辦法，至於具體選用何種辦法需要在計算的時間複雜度，空間複雜度和準確率方面做一個折中。
①比較簡單的方法是利用距離經驗公式，主要是下面三種方法P(cj(x)|x)=1/dj(x)k=1NCand1/dk(x),1jNCand]]>或者P(cj(x)|x)=1dj(x)-d1(x)+1k=1NCand1dk(x)-d1(x)+1,1jNCand]]>或者P(cj(x)|x)=1/dx2(x)k=1NCand1/dk2(x),1jNCand]]>②還有一種方法是基於Gauss模型的置信度估計，也是本發明採用的方法。
P(cj(x)|x)=exp(-dj(x))k=1NCandexp(-dk(x))]]>(θ需要估計)利用混淆矩陣可以修正估計的置信度(混淆矩陣與識別核心本身性能有關，需要估計)，修正置信度由P(cj(x)|x)=k=1NCandP(ck(x)|x)P(cj(x)|ck(x))]]>得到。
如果我們按照上述方法估計置信度，就需要估計方差參數θ，和分類器的混淆矩陣。關於這部分內容將在本技術方案具體實施部分中介紹。一般說來，選擇何種方法作為我們的分類器性能估計，需要綜合考慮時間代價和存儲空間代價來決定。
3特徵提取特徵提取通過對行圖像的圖像分析，首先提取筆劃參數，然後提取漢字的基本筆段，將基本筆劃合併成各個子字符，同時給出幾何代價的打分。
1)行圖像的參數提取階段這一階段要提取三個參數ws——筆劃寬度； ——字符平均寬度； ——字符平均高度；①筆劃寬度ws提取筆劃寬度是指書寫筆跡的寬度。首先，對文本行的水平黑像素遊程進行直方圖分析(水平黑遊程是指橫軸方向上黑象素連續佔有的矩形區域，矩形的高為一個像素，寬即為水平黑遊程的長度)，直方圖的橫軸表示水平黑遊程長度，縱坐標表示具有此長度的水平黑遊程個數。設直方圖中對應遊程個數最多的水平黑遊程長度為p，對應遊程個數為hist(p)，(即直方圖的縱坐標最大值為hist(p)，它對應的橫坐標為p)則取ws=(p-1)hist(p-1)+phist(p)+(p+1)h(p+1)h(p-1)+h(p)+h(p+1).]]>(圖6給出了對圖5(a)圖像的直方圖分析，其中p＝4，hist(p)＝690)②字符平均寬度 的估計字符平均寬度反映了文本行的書寫風格，對字符切分有著直接的影響。首先對文本行圖像作豎直方向的投影，得到投影圖，此圖的橫坐標與文本行的橫坐標一一對應，縱坐標的值為文本行中相應橫坐標豎直方向上全部黑象素點的個數(圖7給出了圖5(a)的投影圖)。對投影圖水平坐標軸方向(縱坐標為0)作水平黑遊程分析，並且計算全部水平黑遊程的平均值，以此作為字符平均寬度的估計。對於文本行中的字符間距過小而造成字符間筆劃的相互重疊的情況，可以在投影圖y＝2ws+1的水平方向上做黑遊程統計，計算其平均值，可以得到較好的字符平均寬度 的估計。
(圖8給出了對圖5(b)豎直方向上的投影圖，這就是粘連嚴重的情況)③字符平均高度 的提取字符平均高度的提取相對比較簡單，只需將行圖像在水平方向上平均分成若干等分(一般是五等分)，再對所有小圖像的高度取平均即為字符的平均高度 (如圖9)2)筆段提取階段筆段是指漢字中橫豎撇捺四種基本元素，筆段提取可以有效地克服字符的粘連。筆段提取方法採用黑遊程跟蹤的方法，其思路是首先在圖像中尋找到一條水平黑遊程，作為某一筆段的開始，然後對該水平黑遊程從上向下逐行跟蹤，直到跟蹤結束，得到一筆段。
跟蹤採用的思路在當前水平黑遊程的下一行，取包含當前黑遊程所在水平位置且左右各偏移一個像素的水平範圍，在此範圍內找到所有的水平黑遊程；然後根據筆段已有遊程的平均寬度、以及由筆段已有遊程擬和得到的筆段方向，選擇某一水平黑遊程加入到已有的筆段遊程中，並更新原筆段的信息。我們將在具體實施中詳細描述這個過程。
(附圖10和11是筆段提取的結果)3)筆段合併階段在筆段提取完成之後，還需要將筆段進一步合併。設Ri和Rj分別為兩相鄰筆段的外接矩形。(見附圖12)(xi，1，yi，1)——Ri的左上角點的坐標；(xi，2，yi，2)——Ri的右下角點的坐標；(xj，1，yj，1)——Rj的左上角點的坐標；(xj，2，yj，2)——Rj的右下角點的坐標；DH(Ri，Rj)——Ri右側和Rj左側的水平距離(注意到DH(Ri，Rj)值用正、負表示方向，在圖12中Ri右邊框的水平位置在Rj左邊框的水平位置的右邊，因此用負值表示；否則若Ri右邊框的水平位置在Rj左邊框的水平位置的左邊，則用正值表示)；DV(Ri，Rj)——Ri底側和Rj頂側的垂直距離；(注意到DV(Ri，Rj)值用正、負表示方向，在圖12中Ri底側框的垂直位置在Rj頂側框的垂直位置的下面，因此用負值表示；否則若Ri底側框的垂直位置在Rj頂側框的垂直位置的上面，則用正值表示)；width(Ri)——Ri的寬度；width(Rj)——Rj的寬度；我們按照下面的原則合併筆段①如果Ri和Rj滿足在水平方向上，Ri包含Rj或者Rj包含Ri，則將筆段i，j合併；
②如果Ri和Rj滿足DH(Ri，Rj)＜0(即Ri右邊框在Rj左邊框之右)，並且有-DH(Ri,Rj)width(Ri)>T1]]>或-DH(Ri,Rj)width(Rj)>T1,]]>則將筆段i，j合併，此處T1為預定義門限，一般取0.7；③如果Ri和Rj滿足DH(Ri，Rj)＜O，並且有-DH(Ri,Rj)width(Ri)>T2]]>且-DH(Ri,Rj)width(Rj)>T2,]]>則將筆段i，j合併，此處T2為預定義門限，一般取0.5；算法將在具體實施階段中描述，圖13給出了圖11的筆段合併結果。
4)子字符打分我們把筆段合併的結果，從左向右排序記為s1，s2，...，sN，這就是我們筆段合併後的子字符圖像，要完成切分，需要將這些子字符圖像進行適當合併以完成切分操作。
按照下面的方式評估(sk，sk+1，...，sk+nk-1)合併的幾何代價。
wk——子字符圖像sk，sk+1，...，sk+nk-1合併後的字符圖像(sk，sk+1，...，sk+nk-1)的寬度(圖21)；hk——子字符圖像sk，sk+1，...，sk+nk-1合併後的字符圖像(sk，sk+1，...，sk+nk-1)的高度(圖21)；①字符寬度設(sk，sk+1，...，sk+nk-1)的寬度為wk，文本行的字符平均寬度為 (如3-2步所求)，則S(wk)=a(wkwc-1)2ifwkwc>1b(wkwc-1)2ifwkwc1]]>其中a，b均為預定義參數，我們取a＝100，b＝400。
②字符寬高比S(r)=min{c(rr-1)2,100},]]>其中一般c＝100。
r為字符(sk，sk+1，...，sk+nk-1)的寬高比，r=wkhk;]]>r為字符平均寬高比r=wchc;]]> 為文本行字符平均寬度，採用前面行參數提取的估計值； 為文本行字符平均高度，採用前面行參數提取的估計值；③字符內部子字符間的距離字符內部子字符之間的距離反映了字符中各子字符之間的可結合的程度，一般的書寫習慣是對於同一漢字內部的子字符具有相對較小的距離，而兩個子字符如果不屬於同一漢字，則其距離相對較大。
但是，僅僅採用上述子字符外接矩形距離量度不能完全反映子字符之間的親合程度，必須採用更適宜的距離量度。有以下三種不同的距離量度i外接矩形框的水平距離即子字符矩形框之間的水平距離(矩形框包圍的區域可以有重疊)(如圖14b)；ii歐幾裡德距離兩個像素點間的歐氏距離是說，如果像素點1的坐標為(x1，y1)像素點2的坐標為(x2，y2)，則這兩個像素點間的歐式距離定義為(x1-x2)2+(y1-y2)2.]]>子字符A與子字符B間的歐幾裡德距離定義為A中全部黑像素點與B中全部黑像素點之間所有的歐式距離值的最小值。
iii平均遊程距離如圖14(d)所示，我們計算兩個子字符之間全部水平遊程(白色遊程)的長度的平均值作為我們的平均遊程距離。
根據上述三種距離，我們定義(sk，sk+1，...，sk+nk-1)的內部距離為din=i=ki=k+nk-1di,i+1k,]]>其中子字符si與sj的距離di，j定義為di,j=nndijn]]>即是上述三種距離的加權平均和，γn*是加權係數，一般來說我們取γn都為1也就可以了。
定義內部距離分數為s(din)=0ifdin0100ifdin>wk4ordin>wc2400dinwkotherwise]]>(圖14(a)為原子字符圖像，圖14(b)為子字符間的外接矩形水平距離，圖14(c)為子字符間歐幾裡德距離，圖14(d)為遊程距離)④字符前後的距離在一行手寫文本中，一般字符內部子字符之間的距離要小於不同字符的子字符之間的距離，因此，我們對字符與其前後字符的子字符的距離進行了評估，並且給以打分。
假設字符(sk，sk+1，...，sk+nk-1)與前後子字符之間的距離分別為DL和DR。
DL——子字符sk的外接矩形框與子字符sk-1的外接矩形框之間的水平距離；DR——子字符sk+nk-1的外接矩形框與子字符sk+nk的外接矩形框之間的水平距離；如果k＝1則DL＝∞；如果k+nk-1＝N，則DR＝∞。最後取D＝min(DL，DR)。
對於字符前後距離的打分為S(D)，
S(D)=100ifD-wc25wc+100D-75DD+wcif-wcDD25(Dmax-D)Dmax-DifDDDmax0ijD>Dmax]]>其中 為文本行中字符的平均寬度，D和Dmax分別為文本行中平均子字符外接矩形框之間的水平距離和最大子字符外接矩形框之間的水平距離。
⑤子字符的連通度估計定義子字符si和子字符sj的連通度Cij為 字符(sk，sk+1，...，sk+nk-1)的連通性由三個量來表示CI——內部連通性；CL——左部連通性；CR——右部連通性；其中內部連通性指的是字符內部子字符的連通程度；左部連通性和右部連通性指的是子字符sk和子字符sk-1，子字符sk+nk-1與子字符sk+nk之間的連通性；C1=1nk-1i=ki=k+nk-2Ci,i+1nk>11nk=1]]>CL=Ck,k-1k>11k=1]]>CR=Ck+nk-1,k+nkk+nk-1N1k+nk-1=N]]>連通度得分S(C)=100[1-12(1+C1-DR+CL2)],]]>整體的分數是以上五種分數的加權平均和S=iiSiii.]]>4候選集產生對於目前的脫機漢字切分方法來說，利用幾何方法基本上能夠將粘連的漢字切開，但是切分後的單元是多於實際的漢字的數量的，這就需要我們對切分的部分進行合併，通過合適的合併算法得到最終的結果。傳統的基於幾何特徵的切分方法往往就根據生成的幾何代價由最短路徑算法計算幾何代價最小的切分方式，而從我們的觀點認為幾何代價並不是評價切分方式的最佳準則，單純依賴於分類器置信度的方法也是不可靠的，必須要考慮上下文約束的關係，而反映語義約束關係的模型就是我們前面介紹的隱馬爾科夫模型(HMM)。由於我們最後的結果是綜合幾何代價和語義-識別代價給出的，因此我們需要根據一定的準則產生一個切分方式的候選集，對候選集內的每個元素計算其對應的幾何代價和語義-識別代價，綜合得到最優切分結果。
對於已經切分好的N個子字符圖像s1，s2，...，sN，建立一個有向圖(V，E)，其中節點數為N+1，標記為Node1，Node2，Node3，...，NodeN+1，也即V＝{Node1，Node2，Node3，...，NodeN+1}。對於任意的Nodei，存在從Nodei到Nodei+1，Nodei+2，Nodei+3，...的有向路徑，其中路徑Nodei→Nodei+j對應了從第i，i+1，...，i+j-1塊子字符合併，也即合併子字符圖像si，si+1，...，si+j-1，路徑的代價就是此合併對應的幾何代價。切分圖每條由起點Node1到終點NodeN+1的路徑都對應了子字符圖像s1，s2，...，sN的一種合併方法，也就是對行圖像的一種切分方式，因此我們稱它為切分路徑。如圖20，對圖16a給出的行圖像提取筆畫，合併子字符，圖17a給出了對應的子字符塊，圖20給出了由此建立的切分圖，可見每一條弧就代表了若干子字符的合併。
傳統的方法直接搜索這個切分圖(Segmentation Graph)從起點到終點的最優路徑作為切分方式，而我們希望能搜索這個最優解附近的一個「鄰域」，因為如果我們的幾何代價函數能比較正確地反映各個子字符間的密合程度，即使最優幾何代價的切分方式不是正確解，它也應該和正確切分差別不大，因此我們轉向搜索切分圖的次優路徑。在次優路徑給定的情況下，就提取基於二元語法模型的語義-識別置信度，用於「評價」我們的候選切分方式。
我們搜索次優路徑的方法就是K最短路徑算法，它可以對切分圖計算出按路徑總代價升序排列的前K選最優的切分路徑(每條路徑都是從起點Node1到終點NodeN+1的)。
NNode——圖的節點數，NNode＝N+1，N代表已經切分好的子字符圖像的個數；NEdge——邊的條數；Start——起始節點(即為Node1)；Edge——終止節點(即為NodeN+1)；K——需要計算的最優路徑條數；πk(v)——從起點Start到節點v的路徑總代價排第k的路徑，其中v的取值集合為節點集Node1，Node2，Node3，...，NodeN+1，所達路徑代價按升序排列，因此π1(v)就是從起點Start到端點v的最短路徑，如果取v＝NodeN+1，那麼π1(NodeN+1)表示了從起點到終點的最短路徑；
Γ-1(v)——v的前趨節點的集合，即所有可能連接到v的節點的集合，對於任何u∈Γ-1(v)，均存在路徑u→v；·——兩條路徑的連接，其中a路徑的終點是b路徑的起始點，連接後的路徑a·b以a路徑的起點作為起點，b路徑終點作為終點；C[v]——節點v的候選路徑集合；然後按照下述步驟進行Step 1首先對於所有v∈V，計算π1(v)，即分別計算從起點Start到各個節點的最短路徑；Step 2對於每個v∈V，如果π1(v)，π2(v)，...，πk-1(v)已經完成，下面介紹如何利用π1(v)，π2(v)，...，πk-1(v)計算πk(v)，其中2≤k≤K。
如果k＝2，那麼初始化候選路徑集合C[v]，對v的前趨節點的集合Γ-1(v)中的每一個元素u，找到從起點Start到節點u的最短路徑，構造新的路徑π1(u)·v，添加到v的候選路徑集合裡，即C[v]←{π1(u)·v|u∈Г-1(v)}；如果k＞2，對路徑πk-1(v)，找到路徑πk-1(v)中v的前趨節點u0，即路徑πk-1(v)通過節點u0連到v。可以證明存在整數l，滿足1≤l≤k-1，使得πk-1(v)從起點Start到u0時走過的路徑與πl(u0)一致，也就是說πk-1(v)恰好等於由路徑πl(u0)的終點u0連接到節點v，即πk-1(v)＝πl(u0)·v。對這樣的整數l我們再計算πl+1(u0)然後我們從候選路徑集合C[v]裡面去掉路徑πl(u0)·v，而把πl+1(u0)·v添加到候選路徑集合C[v]裡面。即令C[v]←{C[v]-{πl(u0)·v}}∪{πl+1(u0)·v}；則求C[v]中的最短路徑，可以證明C[v]中的最短路徑就是πk(v)；遞歸地用以上算法，就可以得到前K條最優切分路徑，可以證明該算法在最壞情況下的時間複雜度是O(NEdge+KNNodelog(NEdgeNNode)),]]>其中NEdge是弧的個數，NNode是節點數。
5判決我們對於輸入的行圖像，首先提取出各個子字符，並且給出相應的幾何代價估計，再用4中的辦法根據幾何代價產生若干子字符的候選合併方案。
對於每個候選方案，我們用Viterbi算法計算每條子字符合併路徑的語義-識別代價。
根據我們前面的推導，我們對每個行圖像的前K條路徑，分別計算每條路徑的平均幾何代價(歸一化後的)Gk和平均語義-識別代價Hk，令Tk＝Hk+Gk，然後在候選路徑中挑出T值最大的作為最終給出的切分方法，注意到在切分方法給出的同時，每個圖像的識別結果與後處理的結果都已經同時給出。
具體實施方法本發明的特徵在於它是藉助圖像採集設備和與其相連的計算機實現的，依次含有以下實現步驟步驟一通過圖像採集設備為下述目的採集足夠的訓練樣本，建立相應的庫●脫機手寫漢字的單字圖像樣本庫；●已給出字符正確切分的行圖像樣本庫，見圖1a，我們對已事先已經提取出的行圖像樣本標定它們的正確切分方式，然後把它們分為兩個部分，一部分作為訓練樣本用於計算參數，另一部分作為測試樣本用於測試本申請所述方法的性能；●待切分對象涉及領域的語料庫；步驟二參數估計第2-1和2-2步是在給定的「待切分的行圖像所涉及領域的語料庫」上進行的，用於計算待切分的樣本所涉及領域的語義約束關係(圖1b)，我們聲明如下符號代表的含義Nc——漢字c在語料樣本中出現的次數；Nc1c2——雙字詞c1c2在語料樣本中出現的次數；N——語料樣本中的漢字總數；P(c)——漢字c在語料樣本中出現的概率；P(c2|c1)——在語料樣本中漢字c1後面緊接著出現漢字c2的概率；Psmooth(·)——平滑處理後的概率；M——語料樣本中包含的不同漢字的個數，國家一級漢字標準包括了常用漢字3755個，我們可以簡單地設M＝3755；第2-1步在語料樣本上估計P(c)，也就是字符c出現的先驗概率；另外還要估計字符間的轉移概率，也就是P(c2|c1)2-1-1步P(c)=NcN,]]>Nc為計算得到的每個漢字在語料庫中出現的總次數；2-1-2步對於二元語法模型，P(c1|c2)=Nc1c2Nc1,]]>其中Nc1c2為計算得到的c1c2這個詞在語料庫中出現的次數；2-1-3步我們採用了以下簡單的處理方法來平滑數據，對於二元語法模型Psmooth(c2|c1)=P(c2|c1)ifNc1c2>0ifNc1c2=0andNc2=01MifNc1c2=0andNc2>0]]>其中ε是一個預先給定的很小的正數，取ε＝10-9；
第2-2步是在「脫機手寫漢字的單字圖像樣本庫」中的單字手寫漢字圖象樣本上計算的(圖1c)，其中每個樣本圖像對應的正確字符是已知的，聲明如下約定Nsample——脫機手寫漢字圖像樣本庫中圖像樣本的個數；xi——第i個樣本圖像；dj(xi)——由識別核心給出的第i個樣本圖像xi的第j個候選識別字對應的識別距離，識別核心按照識別距離的升序排列識別候選字，因此d1(xi)表示第i個樣本圖像xi的首選識別候選字對應的識別距離；NCand——識別核心對單字字符圖像給出的識別候選字的個數，這是一個識別核心的性能參數，因而是常數，而與輸入字符圖像無關；Li——第i個字符圖像xi對應的正確漢字在字符圖像的識別候選集中出現的序號，其中識別候選集按照識別距離的升序排列各個識別候選字；2-2-1步計算脫機手寫漢字識別核心對應的方差參數，用符號θ表示首先，對在步驟一中談到的「脫機手寫漢字的單字圖像樣本庫」的全部圖像樣本進行識別，對每個圖像，得到NCand個識別候選字以及相應的識別距離；根據識別核心提供的識別距離計算第i個樣本圖像xi的首選字對應的識別距離d1(xi)與它的第j個識別字的識別距離之差，用yij表示，即令yij＝dj(xi)-d1(xi)，其次，極小化下式得到對參數θ的估計E=12Nsamplei=1Nsample{j=2Li[exp(-yij)-1]2+j=LI+1NCamdexp(-2yij)}]]>具體的極小化方法可以採取窮舉的辦法，在0和100之間取10000個點，0.01，0.02，0.03，…，99.8，99.9，100，作為θ代入上式，取得其中對應E最小值的作為對θ的估計；為了計算識別核心的混淆矩陣，我們聲明如下約定ωinput(x)——圖像x對應的真實類別；cj(x)——由識別核心給出的圖像x的第j個候選識別結果，識別核心根據識別距離由小到大的升序排列識別候選字，因此c1(x)就是圖像x首選識別候選字；{ωinput(x)＝ω}——對應的真實字符為ω的圖像的樣本集合；#{ωinput(x)＝ω}——對應的真實字符為ω的圖像樣本的個數；2-2-2步計算混淆矩陣混淆矩陣是一個M×M的矩陣，其中M表示語料樣本中包含了多少種不同的漢字，國家標準一級漢字字符集有3755個漢字，我們可設M＝3755；如果我們把所有漢字按任意選定的順序排列，char1，char2，…，charM，那麼混淆矩陣的第α行第β列的元素就是P(charβ|charα)，表示實際類別是charα，但是卻被識別核心識為charβ概率；
根據公式P(char|char)=1#{input(x)=char}x{input(x)=char}j=1NCandP(cj(x)=char|x)]]>計算出與識別核心相關的混淆概率矩陣，其中#{ωinput(x)＝charα}為對應於真實字符為charα的圖像樣本的個數；其中P(cj(x)=char|x)=exp(-dj(x))i=1NCandexp(-di(x)),]]>它是識別核心給出的對圖像x的識別結果為charβ的置信度；x{input(x)=char}j=1NCandP(cj(x)=char|x)]]>表示真實字符為charα，但是識別候選字中包含了charβ的全部字符圖像中關手charβ的識別置信度之和；除了上述四個方面外，我們還需要估計幾何代價與語義-識別代價融合的參數λ，它由行圖像的訓練樣本計算而來(圖2a)，我們放在最後一個部分來介紹如何估計參數λ；步驟三字符行圖像參數提取這一步完成對行圖像參數的提取，包括筆劃寬度、字符平均寬度和字符平均高度，涉及到如下的參數的估計ws——筆劃寬度； ——字符平均寬度； ——字符平均高度；第3-1步筆劃寬度，即書寫筆跡的寬度ws估計首先，對文本行的水平黑像素遊程進行直方圖分析，水平黑遊程是指橫軸方向上黑象素連續佔有的矩形區域，矩形的高為一個像素，寬即為水平黑遊程的長度，直方圖的橫軸表示水平黑遊程長度，縱坐標表示具有此長度的水平黑遊程個數；設直方圖中對應遊程個數最多的水平黑遊程長度為p，對應遊程個數為hist(p)，也就是說直方圖的縱坐標最大值為hist(p)，它對應的橫坐標為p，則取ws=(p-1)hist(p-1)+phist(p)+(p+1)h(p+1)h(p-1)+h(p)+h(p+1);]]>(圖6給出了對圖5(a)圖像的直方圖分析，其中p＝4，hist(p)＝690)第3-2步平均字符寬度 的估計字符平均寬度反映了文本行的書寫風格，對字符切分有著直接的影響；首先對文本行圖像作豎直方向的投影，得到投影圖，此圖的橫坐標與文本行的橫坐標一一對應，縱坐標的值為文本行中相應橫坐標豎直方向上全部黑象素點的個數(圖7給出了圖5(a)的投影圖)；對投影圖水平坐標軸方向(縱坐標為0)作水平黑遊程分析，並且計算全部水平黑遊程的平均值，以此作為字符平均寬度的估計；對於文本行中的字符間距過小而造成字符間筆劃的相互重疊的情況，可以在投影圖y＝2ws+1的水平方向上做黑遊程統計，計算其平均值，可以得到較好的字符平均寬度 的估計；(圖8給出了對圖5(b)豎直方向上的投影圖，這就是粘連嚴重的情況)第3-3步字符平均高度 的估計字符平均高度的提取相對比較簡單，只需將行圖像在水平方向上平均分成若干等分(一般是五等分)，再對所有小圖像的高度取平均即為字符的平均高度 (如圖9)步驟四筆段提取階段筆段是指漢字中橫豎撇捺四種基本元素，筆段提取可以有效地克服字符的粘連；筆段提取方法採用黑遊程跟蹤的方法，其思路是首先在圖像中尋找到一條水平黑遊程，作為某一筆段的開始，然後對該水平黑遊程從上向下逐行跟蹤，直到跟蹤結束，得到一筆段；跟蹤採用的思路在當前水平黑遊程的下一行的某個範圍內，通常是當前水平黑遊程所在位置左右各偏移若干像素(一般我們左右各偏移一個像素)，找到所有的水平黑遊程，並且根據已有筆段的信息，如筆段已有遊程的平均寬度、筆段已有遊程的直線擬合得到的筆段方向等，選擇某一水平黑遊程加入到已有的筆段遊程中，並更新原筆段的信息，我們來詳細描述一下這個過程，它依次含有以下步驟第4-1步按照由上到下的順序掃描到一段水平黑象素遊程時，如果它不在我們已有的各個筆段的黑遊程記錄中，那麼把它作為某一新筆段的開始，同時把這段水平黑遊程添加到新筆段的黑遊程記錄中；第4-2步對於最近添加到筆段記錄中的黑遊程，我們再在這個水平黑遊程下一行包含此水平遊程的水平位置，且左右各偏移一個象素開始搜索新的水平黑遊程，如果有某個水平遊程的黑色象素延伸到這個區域，則將此遊程提取出來；如果沒有黑遊程出現在這個區域，那麼此筆段提取結束，回到4-1步繼續搜索新的筆段；第4-3步對於提取出的黑遊程，我們考慮如何把它添加到筆段的黑遊程記錄中去。這裡我們需要分兩個情況討論，一種情況是上一步提取出的水平黑遊程僅有一個，那麼進行4-3-1步；另一種情況是上一步提取出來的水平黑遊程有兩個或者兩個以上，那麼進行4-3-2步；4-3-1步如果我們僅提取出一個水平黑遊程，■如果這一筆段已有水平黑遊程的平均寬度大於等於新的水平黑遊程寬度的兩倍，那麼判斷已達到筆段結束點，筆段提取結束；
■如果新的水平黑遊程寬度大於等於這一筆段已有水平黑遊程的平均寬度的三倍，則判斷其是一個筆段交叉點，那麼根據已有的這一筆段的水平黑遊程信息預測筆段方向，然後再在預測的方向上左右各偏移筆段水平黑遊程平均寬度的一半，作為新的筆段黑遊程加入到記錄中；■如果新的水平黑遊程寬度不滿足上述兩個前提，則判斷它為合理的筆段黑遊程，直接添加到筆段的水平黑遊程記錄中來；4-3-2步如果我們提取出兩個或以上的水平黑遊程，那麼我們首先利用已有的筆段水平黑遊程信息預測筆段的方向，然後提取在預測方向上的遊程作為我們的候選水平黑遊程，最後重複4-3-1的三個判斷更新黑遊程記錄表；步驟4-3-1和4-3-2採用的預測方法如下對於筆段已經跟蹤出來的所有水平黑遊程分別求中點，然後按照最小二乘原則用線性函數擬合這些中點，同時根據擬合出的直線預測出筆段的方向；第4-4步判決筆段的屬性對於提取出的筆段，我們首先分別計算它的高度和寬度■如果這一筆段所有水平黑遊程的平均寬度大於給定的閾值(一般我們設為10個像素)，並且筆段寬度大於筆段高度，那麼判斷它為橫筆劃。
■我們設定一個小步長，用MinStepLength表示(一般我們取3像素)◆計算第i行和第i+MinStepLength行這兩行的水平黑遊程中點(「+」表示加號)●如果中點一致，那麼角度累加器加上 ●如果第i行中點橫坐標大於第i+MinStepLength行中點的橫坐標，那麼角度累加器加上 ●如果第i行中點橫坐標小於第i+MinStepLength行中點橫坐標，那麼角度累加器加上 ◆從每個筆段的第一行往下一直掃描到距離筆段高度為零處為MinStepLength行時，也即第(筆段高度-MinStepLength)行，將所有角度相加，求平均角度●如果平均角度大於零且比預先設定的值α1要小(一般設α1為10度)，那麼判斷為豎筆劃；●如果平均角度大於上述的α1且小於預先設定的值α2(一般設α2為88度)那麼判斷為撇筆劃
●如果平均角度大於上述的α2且小於預先設定的值α2(一般設α3為98度)那麼判斷為橫筆劃；●如果平均角度大於上述的α2且小於預先設定的值α4(一般設α4為176度)那麼判斷為捺筆劃●如果平均角度大於上述的α4那麼判斷為豎筆劃如果沒有新的遊程被找到，則該筆段跟蹤結束；如果沒有新的筆段被找到，則筆段提取結束；在每一筆段被提取出來時，筆段的屬性，即橫豎撇捺即也被決定；附圖1O和11是筆段提取的結果，每個小筆段都由一個小的矩形所包圍步驟五筆段合併在筆段提取完成之後，還需要將筆段進一步合併為子字符，設Ri和Rj分別為兩相鄰筆段的外接矩形(見附圖12)(xi，1，yi，1)——Ri的左上角點的坐標；(xi，2，yi，2)——Ri的右下角點的坐標；(xj，1，yj，1)——Rj的左上角點的坐標；(xj，2，yj，2)——Rj的右下角點的坐標；DH(Ri，Rj)——Ri右側和Rj左側的水平距離(注意到DH(Ri，Rj)值用正、負表示方向，在圖12中Ri右邊框的水平位置在Rj左邊框的水平位置的右邊，因此用負值表示；否則若Ri右邊框的水平位置在Rj左邊框的水平位置的左邊，則用正值表示)；DV(Ri，Rj)——Ri底側和Rj頂側的垂直距離；(注意到DV(Ri，Rj)值用正、負表示方向，在圖12中Ri底側框的垂直位置在Rj頂側框的垂直位置的下面，因此用負值表示；否則若Ri底側框的垂直位置在Rj頂側框的垂直位置的上面，則用正值表示)；width(Ri)——Ri的寬度；width(Rj)——Rj的寬度；筆段合併按照下面三個原則進行1)如果Ri和Rj滿足在水平方向上，Ri包含Rj或者Rj包含Ri，則將筆段i，j合併；2)如果Ri和Rj滿足DH(Ri，Rj)＜0(即Ri右邊框在Rj左邊框之右)，並且有-DH(Ri,Rj)width(Ri)>T1]]>或-DH(Ri,Rj)width(Rj)>T1,]]>則將筆段i，j合併，此處T1為預定義門限，一般取0.7；3)如果Ri和Rj滿足DH(Ri，Rj)＜0，並且有-DH(Ri,Rj)width(Ri)>T2]]>且-DH(Ri,Rj)width(Rj)>T2,]]>則將筆段i，j合併，此處T2為預定義門限，一般取0.5；筆段合併算法依次含有如下的步驟
第5-1步初始化，筆段按水平方向上的位置從左向右排序；第5-2步按照原則1)搜索所有需要合併的筆段，如搜索到滿足條件的筆段則將它們合併，合併完則轉向第5-1步；否則轉到第5-3步；第5-3步按照原則2)搜索所有需要合併的筆段，如搜索到滿足條件的筆段則將它們合併，合併完則轉向第5-1步；否則轉到第5-4步；第5-4步按照原則3)搜索所有需要合併的筆段，如搜索到滿足條件的筆段則將它們合併，合併完則結束；圖13給出了圖11的筆段合併結果步驟六字符合併的幾何代價評估，包括六個子步驟我們把筆段合併的結果，從左向右排序記為s1，s2，...，sN，這就是我們筆段合併後的子字符圖像，要完成切分，需要將這些子字符圖像進行適當合併以完成切分操作，我們介紹一下子字符圖像的合併過程，圖21示範了這一過程我們用(sk，sk+1，...，sk+nk-1)，表示由子字符圖像sk，sk+1，...，sk+nk-1合併而成的字符圖像，我們按照下面的方式評估(sk，sk+1，...，sk+nk-1)合併的幾何代價wk——子字符圖像sk，sk+1，...，sk+nk-1合併後的字符圖像(sk，sk+1，...，sk+nk-1)的寬度(圖21)；hk——子字符圖像sk，sk+1，...，sk+nk-1合併後的字符圖像(sk，sk+1，...，sk+nk-1)的高度(圖21)；第6-1步字符寬度wk打分，用S(wk)表示字符寬度得分設(sk，sk+1，...，sk+nk-1)的寬度為wk，文本行的字符平均寬度為 (如3-2步所求)，則S(wk)=a(wkwc-1)2ifwkwc>1b(wkwc-1)2ifwkwc1]]>其中a，b均為預定義參數，我們取a＝100，b＝400；第6-2步字符寬高比r打分，用S(r)表示字符寬度得分S(r)=min{c(rr-1)2,100},]]>其中一般c＝100；r為字符(sk，sk+1，...，sk+nk-1)的寬高比，r=wkhk;]]>r為字符平均寬高比r=wchc;]]> 為文本行字符平均寬度，估計值(第3-2步)； 為文本行字符平均高度，估計值(第3-3步)；第6-3步字符內部子字符間的距離打分
1)外接矩形框的水平距離即子字符矩形框之間的水平距離(矩形框包圍的區域可以有重疊)(如圖14b)；2)歐幾裡德距離兩個像素點間的歐氏距離是說，如果像素點1的坐標為(x1，y1)像素點2的坐標為(x2，y2)，則這兩個像素點間的歐式距離定義為(x1-x2)2+(y1-y2)2;]]>子字符A與子字符B間的歐幾裡德距離定義為A中全部黑像素點與B中全部黑像素點之間所有的歐式距離值的最小值；3)平均遊程距離如圖14(d)所示，我們計算兩個子字符之間全部水平遊程(白色遊程)的長度的平均值作為我們的平均遊程距離；根據上述三種距離，我們定義(xk，xk+1，...，sk+nk-1)的內部距離為din=i=ki=k+nk-1di,i+1k,]]>其中子字符si與sj的距離di，j定義為di,j=nndijn]]>即是上述三種距離的加權平均和，γn是加權係數，一般來說我們取γn都為1也就可以了；定義內部距離分數為S(din)=0ifdin0100ifdin>wk4ordin>wc2400dinwkotherwise]]>(圖14(a)為原子字符圖像，圖14(b)為子字符間的外接矩形水平距離，圖14(c)為子字符間歐幾裡德距離，圖14(d)為遊程距離)第6-4步字符前後的距離打分，用S(D)表示假設字符(sk，sk+1，...，sk+nk-1)與前後子字符之間的距離分別為DL和DR；DL——子字符sk的外接矩形框與子字符sk-1的外接矩形框之間的水平距離(與步驟五中的定義一致)；DR——子字符sk+nk-1的外接矩形框與子字符sk+nk的外接矩形框之間的水平距離(與步驟五中的定義一致)；如果k＝1則DL＝∞；如果k+nk-1＝N，則DR＝∞，最後取D＝min(DL，DR)；對於字符前後距離的打分為S(D)，
(D)=100ifD-wc25wc+100D-75DD+wcif-wcDD25(Dmax-D)Dmax-DifDDDmax0ifD>Dmax]]>其中 為文本行中字符的平均寬度，D和Dmax分別為文本行中平均子字符外接矩形框之間的水平距離和最大子字符外接矩形框之間的水平距離；第6-5步連通度打分，用S(C)表示定義子字符si和子字符sj的連通度Cij為 字符(sk，sk+1，...，sk+nk-1)的連通性由三個量來表示CI——內部連通性；CL——左部連通性；CR——右部連通性；其中內部連通性指的是字符內部子字符的連通程度；左部連通性和右部連通性指的是子字符sk和子字符sk-1，子字符sk+nk-1與子字符sk+nk之間的連通性；cl=1nk-1i=ki=k+nk-2ci,i+1nk>11nk=1]]>CL=Ck,k-1k>11k=1]]>CR=Ck+nk-1,k+nkk+nk-1N1k+nk-1=N]]>連通度得分S(C)=100[1-12(1+Cl-CR+CL2)]]]>第6-6步計算總體分值作為幾何代價整體的分數是以上五種分數的加權平均和S=iiSiii,]]>一般我們取α1＝5，α2＝2，α3＝3，α4＝5，α5＝2步驟七根據已經評價出來的幾何代價計算前K條幾何代價最優的切分方式當進行完步驟六之後，我們把行圖像切分成了一列子字符圖像(見圖17(a)(b)(c)，它給出了圖16(a)(b)(c)行圖像切分為子字符圖像的結果，每個矩形框裡面包含的就是一個子字符圖像，這個矩形框就是子字符圖像的外接矩形框)，同時給出了子字符塊之間合併的幾何代價，但是我們需要進一步把子字符圖像合併為字符圖像從而完成字符的切分；下面我們利用步驟六得到的子字符塊合併的代價，生成一些可能的子字符合併方案(每個方案都對應行圖像的一種切分結果)，我們在步驟八中評價這些方案，並給出最優方案；第7-1步切分圖建立對於已經切分好的N個子字符圖像s1，s2，...，sN，建立一個有向圖(V，E)，其中節點數為N+1，標記為Node1，Node2，Node3，...，NodeN+1，也即V＝{Node1，Node2，Node3，...，NodeN+1}；對於任意的Nodei，存在從Nodei到Nodei+1，Nodei+2，Nodei+3，...的有向路徑，其中路徑Nodei→Nodei+j對應了從第i，i+1，...，i+j-1塊子字符合併，也即合併子字符圖像si，si+1，...，si+j-1，路徑的代價就是此合併對應的幾何代價；切分圖每條由起點Node1到終點NodeN+1的路徑都對應了子字符圖像s1，s2，...，sN的一種合併方法，也就是對行圖像的一種切分方式，因此我們稱它為切分路徑；(見圖20，對圖16a給出的行圖像提取筆畫，合併子字符，圖17a給出了對應的子字符塊，圖20給出了由此建立的切分圖，可見每一條弧就代表了若干子字符的合併)第7-2步產生前K條幾何代價最優的切分路徑我們下面介紹如何計算切分圖(V，E)中從起點Node1到終點NodeN+1按代價的升序排列的前K條路徑，這裡每條路徑都對應了行圖像的一種切分方式，實際上就是子字符圖像s1s2，...，sN一種合併方案，按照此方案合併子字符s1，s2，...，sN，從而完成對行圖像的切分；算法的具體過程如下給定圖(V，E)，設NNode——圖的節點數，NNode＝N+1，N代表已經切分好的子字符圖像的個數；NEdge——邊的條數；Start——起始節點(即為Node1)；Edge——終止節點(即為NodeN+1)；K——需要計算的最優路徑條數；πk(v)——從起點Start到節點v(其中v可以取節點集Node1，Node2，Node3，...，NodeN+1中任何一個節點)的路徑總代價排第k的路徑(路徑代價按升序排列)，因此πu1(v)就是從起點Start到端點v的最短路徑，如果取v＝NodeN+1，那麼π1(NodeN+1)表示了從起點到終點的最短路徑；Γ-1(v)——v的前趨節點的集合，即所有可能連接到v的節點的集合，對於任何u∈Г-1(v)，均存在路徑u→v；·——兩條路徑的連接，其中a路徑的終點是b路徑的起始點，連接後的路徑a·b以a路徑的起點作為起點，b路徑終點作為終點；C[v]——節點v的候選路徑集合；然後按照下述步驟進行7-2-1步首先對於所有v∈V，計算π1(v)，即分別計算從起點Start到各個節點的最短路徑；7-2-2步對於每個v∈V，如果π1(v)，π2(v)，...，πk-1(v)已經完成，下面介紹如何利用π1(v)，π2(v)，...，πk-1(v)計算πk(v)，其中2≤k≤K；如果k＝2，那麼初始化候選路徑集合C[v]，對v的前趨節點的集合Г-1(v)中的每一個元素u，找到從起點Start到節點u的最短路徑，構造新的路徑π1(u)·v，添加到v的候選路徑集合裡，即C[v]←{π1(u)·v|u∈Г-1(v)}；如果k＞2，對路徑πk-1(v)，找到路徑πk-1(v)中v的前趨節點u0，即路徑πk-1(v)通過節點u0連到v，一定存在整數l，滿足1≤l≤k-1，使得πk-1(v)從起點Start到u0時走過的路徑與πl(u0)一致，也就是說πk-1(v)恰好等於由路徑πl(u0)的終點u0連接到節點v，即πk-1(v)＝πl(u0)·v，對這樣的整數l，我們再計算πl+1(u0)；然後我們從候選路徑集合C[v]裡面去掉路徑πl(u0)·v，而把πl+1(u0)·v添加到候選路徑集合C[v]裡面，即令C[v]←{C[v]{πl(u0)·v}}∪{πl+1(u0)·v}；則求C[v]中的最短路徑，可以證明C[v]中的最短路徑就是πk(v)；遞歸地用以上算法，就可以得到前K條切分路徑；至於如何在實際應用中選擇K值，需要在時間複雜度和準確度間做一個折中，事實上，我們在實踐中並不需要找到完全正確的切分方式，次優的切分方式也能保證很高的字符識別率，我們一般取K＝200，更一般的情況下我們可以選擇自適應的K值(一般選擇K為子字符塊數的10倍)；由於我們的候選集是按照幾何代價準則生成的，因此有效的幾何代價函數能使我們的候選集儘量小，同時正確的切分方式出現在比較靠前的位置；第7-3步字符識別事實上，產生K候選的時間消耗並不大，時間瓶頸在於分類器識別消耗的時間，因此上述算法在我們具體應用中可以採取進一步的優化措施，注意到這前K個候選切分方式中雖然整體的切分方法不同，但是每條切分路徑都存在一些共有的切分方式，因此我們沒有必要對每條路徑都識別一遍，也不必全部重新計算置信度，採用如下的方法CharCandidatesSet——圖像識別候選集，其中的每個元素都包含了NCand個識別候選字和NCand個對應的識別置信度；CharCandidatesSetNum——圖像識別候選集中元素的個數；設子字符為s1s2...sN，我們建立一個(N+1)×(N+1)的查詢表LookupTable，LookupTable中的元素首先全部設為-1，清空圖像識別候選集CharCandidatesSet，並令CharCandidatesSetNum＝0；For 1≤k≤K對第k個候選切分路徑(幾何代價按升序排列排在第k的候選切分路徑)對spsp+1...sq(1≤p≤q≤N)這樣的合併方式，查詢LookupTable中的元素LookupTable(p，q+1)(表示查詢表LookupTable中第p行第q+1列的元素)；如果LookupTable(p，q+1)＝-1，那麼說明這種合併還沒有被識別過，對這種組合得到的圖像進行識別，得到NCand個候選字，並且估計每個識別候選字的置信度(第8-1步)，然後把識別候選字及其對應的識別置信度整體作為一個元素添加到圖像識別候選集CharCandidatesSet，然後令LookupTable(p，q+1)＝CharCandidatesSetNum，然後令讓CharCandidatesSetNum增加1，也即CharCandidatesSetNum＝CharCandidatesSetNum+1；如果LookupTable(p，q+1)≠-1，那麼說明這種合併已被考慮過，不用再處理End For圖22詳細解釋了7-3這一過程，這一過程帶來的好處是避免了識別核心的重複工作，大大節約了時間；在後面的步驟中如果我們需要知道子字符塊spsp+1...sq合併後的識別結果時，只要查詢LookupTable的第p行第q+1列元素，就可以得到子字符塊spsp+1...sq合併後的識別結果在CharCandidatesSet中的序號，從而找到在CharCandidatesSet對應位置中已經記錄的子字符塊spsp+1...sq合併後的識別結果及相應的置信度；步驟八依賴於前面給出的K條幾何意義下最優的候選切分方案，根據二元語法模型給出每個子字符合併方案對應的語義-識別代價第8-1步字符置信度估計x——待識別的字符圖像；cj(x)——由識別核心給出的對圖像x的第j個候選識別字(識別核心根據識別距離由小到大的升序排列識別候選字，因此c1(x)就是圖像x的首選識別候選字)；dj(x)——由識別核心給出的圖像x的第j個候選識別字cj(x)對應的識別距離，因此d1(x)表示圖像x的首選識別候選字對應的識別距離；NCand——識別核心對單字字符圖像給出的識別候選字的個數，如前2-2步所述，該值為常數，只與識別核心本身有關；P(cj(x)|x)——圖像x識別為cj(x)的置信度，這是我們需要估計的對象；對於7-3步得到的所有候選字，可以針對我們具體的需要選擇下面兩種不同的方法估計候選字的置信度①距離經驗公式P(cj(x)|x)=1/dj(x)k=1NCand1/dk(x),1jNCand]]>或者P(cj(x)|x)=1dj(x)-d1(x)+1k=1NCand1dk(x)-d1(x)+1,1jNCand]]>或者P(cj(x)|x)=1/dj2(x)k=1NCand1/dk2(x),1jNCand]]>②基於Gauss模型的置信度估計P(cj(x)|x)=exp(-dj(x))k=1NCandexp(-dk(x))]]>(θ就是我們前面2-2-1步計算出來的)利用前面計算的混淆矩陣可以修正估計的置信度(混淆矩陣由2-2-2計算得到)，修正置信度由P(cj(x)|x)=k=1NCandP(ck(x)|x)P(cj(x)|ck(x))]]>得到；估計識別置信度可以根據需要靈活選擇上面的方法，在本發明中，我們採用了基於Gauss模型的置信度估計方案；第8-2步；基於二元語法的語義-識別置信代價計算對於已經給出的K條行圖像切分路徑，對每條切分路徑應用以下的方法計算其對應的平均語義-識別置信代價，聲明如下符號及其意義nk——按照第k條切分路徑合併子字符圖像，共得到nk個合併後的字符圖像；
imagek，t——按照第k條切分路徑合併子字符圖像後的第t個字符圖像，其中1≤k≤K，1≤t≤nk；cj(imagek，t)——識別核心給出的字符圖像imagek，t的第j個識別候選字，其中1≤j≤NCand，1≤k≤K，1≤t≤nk，P(cj(imagek,t)|imagek，t)對應它的識別置信度；由於字符圖像的識別和置信度的估計已經在7-3步中完成，在此步驟中我們可以通過查詢LookupTable的方法從CharcandidatesSet中得到我們需要的識別結果和置信度；對第k條候選切分路徑，1≤k≤K，使用下述的Vieterbi方法計算語義-識別代價令Q[nk][NCand]是一個二維數組，其中Q[t][j]保存了從第一個字符圖像某個候選字到字節點cj(imagek，t)的最大可能候選字選擇方式所具有的概率的對數值，另外取一個二維指針數組Path[nk][NCand]用於記錄計算過程；初始化t＝1，1≤j≤NCandPath[1][j]＝NULLQ[1][j]＝logP(cj(imagek，1))+log(cj(imagek，1)|imagek，1)遞歸2≤t≤nk，對1≤j≤NCand計算Q[t][j]Q[t][j]=max1lNCand{Q[t-1][l]+logP(cj(imagek,l)|cl(imagek,t-1))}+logP(cj(imagek,t)|imagek,]]>另外找到使得Q[t-1][l]+logP(cj(imagek，t)|cl(imagek，t-1))最大的l，記作l*，即l*=argmax1lNCand{Q[t-1][l]+logP(cj(imagek,l)|cl(imagek,t-1))}]]>然後令Path[t][j]指向字節點cl*(imagek，t-1)，即字節點cj(imagek，t)的父節點為cl*(imagek，t-1)終止t＝nk最後找到j*，使得j*=argmax1jNCandQ[nk][j],]]>回溯Path[nk][j*]所指的路徑，輸出路徑上的每個字節點，得到字符串即為我們的字符識別結果；在得到最優字符串的同時，我們也得到了最大可能路徑的概率的對數值Q[nk][j*]，我們將這個值作為對這條切分路徑的語義-識別代價估計，將這個值除以nk，得到平均語義-識別代價Hk=Q[nk][j*]nk;]]>
步驟九綜合幾何代價與語義代價給出最終結果第9-1步我們需要估計幾何代價與語義-識別代價的融合參數λ融合參數λ的計算流程如圖2a聲明如下約定NL——已經給出子字符和正確子字符合併方式的行圖像個數(即訓練樣本個數)；ni，k——第i個訓練樣本第七個候選切分方式對應的字符個數；ni，0——第i個訓練樣本正確切分得到字符個數；gi，k——第i個訓練樣本第k個候選切分路徑對應的幾何代價，則gi，l表示第i個訓練樣本所有切分方式中幾何代價的最小值；Gi，k——第i個訓練樣本第k個候選切分方式對應的平均幾何代價(歸一化後的值)；Hi，k——第i個訓練樣本第k個候選切分方式對應的平均語義-識別代價；gi，0——第i個訓練樣本完全正確切分對應的幾何代價Gi，0——第i個訓練樣本完全正確切分對應的平均幾何代價(歸一化後的值)；Hi，0——第i個訓練樣本完全正確切分對應的平均語義-識別代價；我們挑選NL個訓練樣本行圖像(圖1a)，對每個行圖像按照從步驟三到步驟八的順序進行處理，從而可以得到ni，k，gi，k，Hi，k1≤i≤NL，1≤k≤K；我們選用下面的方式對步驟六中評價的幾何代價進行歸一化，並求其平均值，即我們令Gik=1ni,klog(e-(gi,k/gi,k-1)),1iNL,1kK,]]>類似地我們可以按照前面的步驟得到正確切分對應的幾何代價歸一化後的分數Gi，01≤i≤NL和平均語義-識別代價(利用8-2步介紹的方法)Hi，01≤i≤NL，記Tik=Hi,k+Gi,k]]>1≤k≤K，然後記Ti0(λ)為第i個樣本完全正確切分對應的T值，即Ti0=Hi,0+Gi,0;]]>極小化N=i=1NL#{Tik>Ti0|1kK}]]>即得到對加權係數λ的估計；其中#{Tik(λ)＞Ti0(λ)|1≤k≤K}表示在給定λ的情況下，第i個樣本圖像對應的K個候選切分路徑中，T值比正確切分方式對應的T值還要大的候選路徑的個數，極小化方法依然可以採用類似於極小化θ的嘗試法第9-2步根據融合參數λ計算最優的切分識別路徑(圖2b)對一般待切分的樣本行圖像，我們依步驟三——步驟八，計算出K條候選切分路徑，並計算出每條路徑的平均識別-語義代價Hk1≤k≤K，平均幾何代價(歸一化後的)Gk=1nklog(e-(gk/gl-1))--1kK,]]>(其中gk1≤k≤K對應步驟六中得到的每條切分路徑幾何代價)，則綜合的代價Tk＝Hk+Gk1≤k≤K，取k*=argmax1kKTk,]]>則第k*個候選切分方式作為我們給出的最優切分。
本申請所述方法的實驗結果我們為試驗準備如下的數據1)為了計算分類器的識別置信度，我們需要在已知類別的字符圖像樣本上計算參數θ，我們選用了由THOCR提供的50候選的漢字識別核心。樣本也是由清華大學電子工程系智能圖文處理實驗室收集的手寫漢字樣本。
2)我們收集了大約四千幅信封的手寫的信封圖像樣本，使用清華大學電子工程系智能圖文實驗室提供的CEARS程序處理了其中的一部分樣本，提取信封地址的地址行(包含了地理地址和單位名稱兩個部分)，去除掉其中誤提取地址行，得到了1141個實驗樣本作為我們的全部行圖像，並事先由人工方式給出了每個行圖像的正確字符切分方式，其中908挑出來作為訓練樣本計算參數λ，另外233個作為測試樣本。
3)我們實現的是手寫郵政地址行的切分，選用的是從中宇郵政信息公司購買的北京市郵政信息名址庫，共有18萬條名址信息，包括單位名稱和物理地址，實際共有約37萬個條目，作為我們訓練的語料庫。
然後按照我們上面所述的步驟二到步驟九進行，我們計算出θ＝2.322(第2-2-1步)，λ＝51.85(第9-1步)，識別核心輸出待識別圖像的前十個識別候選字(即Ncand＝10，第2-2步、第8-1步)。
我們比較兩個指標RL和RC。
其中RL表示行切分正確率，所謂行切分正確，是指這一行圖像的每個字符都被正確切分，

RC表示字切分正確率，是指單獨一個字符被正確切分的比率，

試驗結果如下(Intel Pentium4 2.8GHz 512MB RAM)

注測試樣本233個，共包括了3013個漢字。
每行平均處理時間小於300毫秒，這個時間裡面包含了字符圖像的合併，識別、後處理以及給出最優切分識別結果的全部時間。
對比傳統只搜索幾何代價最優的切分方式得到的結果(圖18(a)(b)(c)給出了對圖17(a)(b)(c)僅僅依賴於幾何代價最優得到的切分結果，圖19(a)(b)(c)給出了我們的方法給出的切分結果)，可見本發明提出的方法實現了高準確率的脫機手寫漢字的切分。同時從時間指標上來看，本方法可以對手寫文檔圖像進行實時的高效切分和識別。
當λ＝0即幾何代價不納入考慮的時候，單純依賴語義信息不能得到最好的結果，這是因為我們的單字識別可以允許一定的噪聲，因此某些情況下不一定非要在正確切分下才能得到正確的識別結果，而對於語義-識別代價接近的切分方式來說，就需要進一步比較它們的幾何代價了。
結論綜上所述，本發明提出的基於幾何代價和語義-識別代價融合的脫機手寫漢字切分方法具有以下優點1)基於提取圖像幾何特徵和圖像的統計特徵實現對脫機手寫漢字的過切分，能夠有效地克服手寫漢字的粘連問題。
2)本發明採用的各個字符子字符的幾何評估能較好地反映各個字符子字符間的親密程度，為下一步的合併提供正確的依據。
3)本發明提出的用計算K最短路徑給出切分候選的方法。傳統方法只取幾何代價最優的切分方式，不能保證最佳切分方式一定可以求得，K最短路徑方法克服了傳統方法的不足，擴大了搜索區域。
4)本發明提出了一個新的觀點，認為語義-識別代價才是評價切分有效性的最有力準則，在這個基礎上同時考慮切分的幾何代價，給出切分方式。這使得我們實現的脫機手寫漢字切分和識別的過程更接近於人類的認知過程。同時本發明給出的框架具有一定的指導意義，不論何種形式的幾何代價或者語義代價均可以按照本發明提供的思路進行融合。
5)本發明具有很好的推廣性，主要表現在一方面可以由中文切分推廣到英文(或者其他語言)的脫機手寫字符的切分上(可能需要考慮高階的語言模型)；另一方面本發明可以方便地應用到其他需要實現高效的脫機手寫字符切分的領域，只需要事先對該領域的語料庫計算相應的參數，代入我們模型的框架即可。
6)本發明對非本領域的文檔有一定的拒絕作用，在針對地址行訓練的Bi-gram模型，對於把姓名行錯誤提取成地址行的情況，可以發現這時的語義代價非常高，這使得我們能夠正確地拒絕這樣的錯誤提取行，使整個系統更具智能化。
本方法提出了漢字切分識別和後處理的統一模型，為脫機漢字的切分提出了一種新的思路。


圖1(a)對「已給出字符正確切分的行圖像樣本庫」，我們把它們分為兩個部分，一部分作為訓練樣本用於計算參數，另一部分作為測試樣本用於測試本發明所述方法的性能；圖1(b)對「待切分對象涉及領域的語料庫」，我們計算我們的語義約束關係，即字符出現的先驗概率和字符間的轉移概率(見具體實施方法的第2-1步)；圖1(c)對「脫機手寫漢字的單字圖像樣本庫」，我們估計方差參數θ和混淆矩陣，用於我們估計各個識別字的識別置信度(見具體實施方法的第2-2-1和2-2-2步)；圖2(a)計算幾何代價與語義-識別代價融合的參數λ的過程(見具體實施方法的第9-1步)；圖2(b)本發明所屬方法實現對脫機手寫漢字切分的過程；圖3我們把手寫漢字的文檔通過掃描儀掃描進我們的計算機，以圖像的方式存儲；圖4對於掃描進的文檔圖像，需要進行去噪聲和二值化處理，由於本發明是以行圖像為單位進行處理的，因此還需要對文檔圖像提取出其包含漢字的行，作為本發明的實施對象；圖5(a)提取出的行圖像的例子，字與字之間分離較好的情況；圖5(b)提取出的行圖像的例子，字與字之間粘連嚴重的情況；圖6圖6給出了對圖5(a)圖像的字符筆畫寬度的直方圖分析，其中長度為4的水平黑遊程出現的個數最多，因此在具體實施方法的第3-1步p＝4，對應hist(p)＝690圖7圖7給出了對圖5(a)圖像黑色像素點豎直方向上的投影圖(見具體實施方法的第3-2步)；圖8圖8給出了對圖5(b)圖像黑色像素點豎直方向上的投影圖(見具體實施方法的第3-2步)；圖9圖9給出了具體實施方法的第3-3步字符平均高度 的估計過程；圖10和圖11圖10和11是筆段提取的結果，每個小矩形包圍的就是一個提取出的筆段，見具體實施方法的步驟四。
圖12Ri和Rj分別為兩相鄰筆段的外接矩形，圖12標出了Ri右側和Rj左側的水平距離DH(Ri，Rj)以及Ri底側和Rj頂側的垂直距離DV(Ri，Rj)(見具體實施方法的步驟五)；圖13圖13給出了圖11的筆段合併為子字符的結果(見具體實施方法的步驟五)；圖14(a)(b)(c)(d)圖14(a)為原子字符圖像，圖14(b)為子字符間的外接矩形水平距離，圖14(c)為子字符間歐幾裡德距離，圖14(d)為子字符之間的水平遊程距離圖15對字符前後的距離D的打分，D到S(D)的映射關係(見具體實施方法的第6-4步)；
圖16(a)(b)(c)從信封上提出的待切分的行圖像；圖17(a)(b)(b)圖16(a)(b)(c)通過筆段提取和筆段合併後得到的子字符，每個子字符由一個外接矩形包圍；圖18(a)(b)(c)圖17(a)(b)(b)根據幾何代價評分，取其幾何代價最優的子字符合併方式，合併子字符塊後得到的結果；圖19(a)(b)(c)圖17(a)(b)(b)根據本申請所述方法合併子字符塊後得到的結果；圖20由圖17(a)給出的子字符切分結果建立的切分圖(見具體實施方法的第7-1步)；圖21子字符合併的一般過程(見具體實施方法的步驟六)；圖22圖22解釋了具體實施方法中步驟7-3的過程，這一步驟使得我們能夠避免重複識別相同的字符圖像。
權利要求
1.幾何代價和語義-識別代價融合的脫機手寫漢字切分方法，其特徵在於它是藉助圖像採集設備和與其相連的計算機實現的，依次含有以下步驟步驟一通過圖像採集設備為下述目的採集足夠的訓練樣本，建立相應的庫●脫機手寫漢字的單字圖像樣本庫；●已給出字符正確切分的行圖像樣本庫我們對已事先已經提取出的行圖像樣本標定它們的正確切分方式，然後把它們分為兩個部分，一部分作為訓練樣本用於計算參數，另一部分作為測試樣本用於測試本申請所述方法的性能；待切分對象涉及領域的語料庫；步驟二參數估計第2-1和2-2步是在給定的「待切分的行圖像所涉及領域的語料庫」上進行的，用於計算待切分的樣本所涉及領域的語義約束關係，我們聲明如下符號代表的含義Nc——漢字c在語料樣本中出現的次數；Nc1c2——雙字詞c1c2在語料樣本中出現的次數；N——語料樣本中的漢字總數；P(c)——漢字c在語料樣本中出現的概率；P(c2|c1)——在語料樣本中漢字c1後面緊接著出現漢字c2的概率；Psmooth(·)——平滑處理後的概率；M——語料樣本中包含的不同漢字的個數，國家一級漢字標準包括了常用漢字3755個，我們簡單地設M＝3755；第2-1步在語料樣本上估計P(c)，也就是字符c出現的先驗概率；另外還要估計字符間的轉移概率，也就是P(c2|c1)2-1-1步P(c)=NcN,]]>Nc為計算得到的每個漢字在語料庫中出現的總次數；2-1-2步對於二元語法模型，P(c2|c1)=Nc1c2Nc1,]]>其中Nc1c2為計算得到的c1c2這個詞在語料庫中出現的次數；2-1-3步我們採用了以下簡單的處理方法來平滑數據，對於二元語法模型Psmooth(c1|c2)=P(c2|c1)ifNc1c2>0ifNc1c2=0andNc2=01MifNc1c2=0andNc2>0]]>其中ε是一個預先給定的很小的正數，取ε＝10-9；第2-2步是在「脫機手寫漢字的單字圖像樣本庫」中的單字手寫漢字圖象樣本上計算的，其中每個樣本圖像對應的正確字符是已知的，聲明如下約定Nsample——脫機手寫漢字圖像樣本庫中圖像樣本的個數；xi——第i個樣本圖像；dj(xi)——由識別核心給出的第i個樣本圖像xi的第j個候選識別字對應的識別距離，識別核心按照識別距離的升序排列識別候選字，因此d1(xi)表示第i個樣本圖像xi的首選識別候選字對應的識別距離；NCand——識別核心對單字字符圖像給出的識別候選字的個數，這是一個識別核心的性能參數，因而是常數，而與輸入字符圖像無關；Li——第i個字符圖像xi對應的正確漢字在字符圖像的識別候選集中出現的序號，其中識別候選集按照識別距離的升序排列各個識別候選字；2-2-1步計算脫機手寫漢字識別核心對應的方差參數，用符號θ表示首先，對在步驟一中談到的「脫機手寫漢字的單字圖像樣本庫」的全部圖像樣本進行識別，對每個圖像，得到NCand個識別候選字以及相應的識別距離；根據識別核心提供的識別距離計算第i個樣本圖像xi的首選字對應的識別距離d1(xi)與它的第j個識別字的識別距離之差，用yij表示，即令yij＝dj(xi)-d1(xi)，其次，極小化下式得到對參數θ的估計E=12Nsamplei=1Nsample{i=1Li[exp(-yij)-1]2-j=Li+1NCandexp(-2yij)}]]>具體的極小化方法採取窮舉的辦法，在0和100之間取10000個點，0.01，0.02，0.03，…，99.8，99.9，100，作為θ代入上式，取得其中對應E最小值的作為對θ的估計；為了計算識別核心的混淆矩陣，我們聲明如下約定ωinput(x)——圖像x對應的真實類別；cj(x)——由識別核心給出的圖像x的第j個候選識別結果，識別核心根據識別距離由小到大的升序排列識別候選字，因此c1(x)就是圖像x首選識別候選字；{ωinput(x)＝ω}——對應的真實字符為ω的圖像的樣本集合；#{ωinput(x)＝ω}——對應的真實字符為ω的圖像樣本的個數；2-2-2步計算混淆矩陣混淆矩陣是一個M×M的矩陣，其中M表示語料樣本中包含了多少種不同的漢字，國家標準一級漢字字符集有3755個漢字，我們可設M＝3755；如果我們把所有漢字按任意選定的順序排列，char1，char2，…，charM，那麼混淆矩陣的第α行第β列的元素就是P(charβ|charα)，表示實際類別是charα，但是卻被識別核心識為charβ概率；根據公式P(char|char)=1#{input(x)=char}x{input(x)=char}j=1NCandP(cj(x)=char|x)]]>計算出與識別核心相關的混淆概率矩陣，其中#{ωinput(x)＝charα}為對應於真實字符為charα的圖像樣本的個數；其中P(cj(x)=char|x)=exp(-dj(x))i=1NCandexp(-di(x)),]]>它是識別核心給出的對圖像x的識別結果為charβ的置信度；x{input(x)=charj=1NCandP(cj(x)=char|x)]]>表示真實字符為charα，但是識別候選字中包含了charβ的全部字符圖像中關於charβ的識別置信度之和；除了上述四個方面外，我們還需要估計幾何代價與語義-識別代價融合的參數λ，它由行圖像的訓練樣本計算而來，我們放在最後一個部分來介紹如何估計參數λ；步驟三字符行圖像參數提取這一步完成對行圖像參數的提取，包括筆劃寬度、字符平均寬度和字符平均高度，涉及到如下的參數的估計ws——筆劃寬度； ——字符平均寬度； ——字符平均高度；第3-1步筆劃寬度，即書寫筆跡的寬度ws估計首先，對文本行的水平黑像素遊程進行直方圖分析，水平黑遊程是指橫軸方向上黑象素連續佔有的矩形區域，矩形的高為一個像素，寬即為水平黑遊程的長度，直方圖的橫軸表示水平黑遊程長度，縱坐標表示具有此長度的水平黑遊程個數；設直方圖中對應遊程個數最多的水平黑遊程長度為p，對應遊程個數為hist(p)，也就是說直方圖的縱坐標最大值為hist(p)，它對應的橫坐標為p，則取ws=(p-1)hist(p-1)+phist(p)+(p+1)h(p+1)h(p-1)+h(p)+h(p+1);]]>第3-2步平均字符寬度 的估計字符平均寬度反映了文本行的書寫風格，對字符切分有著直接的影響，首先對文本行圖像作豎直方向的投影，得到投影圖，此圖的橫坐標與文本行的橫坐標一一對應，縱坐標的值為文本行中相應橫坐標豎直方向上全部黑象素點的個數，對投影圖水平坐標軸方向也就是縱坐標為0的方向作水平黑遊程分析，並且計算全部水平黑遊程的平均值，以此作為字符平均寬度的估計；對於文本行中的字符間距過小而造成字符間筆劃的相互重疊的情況，在投影圖y＝2ws+1的水平方向上做黑遊程統計，計算其平均值，得到較好的字符平均寬度 的估計；第3-3步字符平均高度 的估計字符平均高度的提取相對比較簡單，只需將行圖像在水平方向上平均分成若干等分，一般取五等分，再對所有小圖像的高度取平均即為字符的平均高度 步驟四筆段提取階段筆段是指漢字中橫豎撇捺四種基本元素，筆段提取有效地克服了字符的粘連；筆段提取方法採用黑遊程跟蹤的方法，其思路是首先在圖像中尋找到一條水平黑遊程，作為某一筆段的開始，然後對該水平黑遊程從上向下逐行跟蹤，直到跟蹤結束，得到一筆段；跟蹤採用的思路在當前水平黑遊程的下一行，取包含當前黑遊程所在水平位置且左右各偏移一個像素的水平範圍，在此範圍內找到所有的水平黑遊程；然後根據筆段已有遊程的平均寬度、以及由筆段已有遊程擬和得到的筆段方向，選擇某一水平黑遊程加入到已有的筆段遊程中，並更新原筆段的信息；我們來詳細描述一下這個過程，它依次含有以下步驟第4-1步按照由上到下的順序掃描到一段水平黑象素遊程時，如果它不在我們已有的各個筆段的黑遊程記錄中，那麼把它作為某一新筆段的開始，同時把這段水平黑遊程添加到新筆段的黑遊程記錄中；第4-2步對於最近添加到筆段記錄中的黑遊程，我們再在這個水平黑遊程下一行包含此水平遊程的水平位置，且左右各偏移一個象素開始搜索新的水平黑遊程，如果有某個水平遊程的黑色象素延伸到這個區域，則將此遊程提取出來；如果沒有黑遊程出現在這個區域，那麼此筆段提取結束，回到4-1步繼續搜索新的筆段；第4-3步對於提取出的黑遊程，我們考慮如何把它添加到筆段的黑遊程記錄中去這裡我們需要分兩個情況討論，一種情況是上一步提取出的水平黑遊程僅有一個，那麼進行4-3-1步；另一種情況是上一步提取出來的水平黑遊程有兩個或者兩個以上，那麼進行4-3-2步；4-3-1步如果我們僅提取出一個水平黑遊程，■如果這一筆段已有水平黑遊程的平均寬度大於等於新的水平黑遊程寬度的兩倍，那麼判斷已達到筆段結束點，筆段提取結束；■如果新的水平黑遊程寬度大於等於這一筆段已有水平黑遊程的平均寬度的三倍，則判斷其是一個筆段交叉點，那麼根據已有的這一筆段的水平黑遊程信息預測筆段方向，然後再在預測的方向上左右各偏移筆段水平黑遊程平均寬度的一半，作為新的筆段黑遊程加入到記錄中；■如果新的水平黑遊程寬度不滿足上述兩個前提，則判斷它為合理的筆段黑遊程，直接添加到筆段的水平黑遊程記錄中來；4-3-2步如果我們提取出兩個或以上的水平黑遊程，那麼我們首先利用已有的筆段水平黑遊程信息預測筆段的方向，然後提取在預測方向上的遊程作為我們的候選水平黑遊程，最後重複4-3-1的三個判斷更新黑遊程記錄表；步驟4-3-1和4-3-2採用的預測方法如下對於筆段已經跟蹤出來的所有水平黑遊程分別求中點，然後按照最小二乘原則用線性函數擬合這些中點，同時根據擬合出的直線預測出筆段的方向；第4-4步判決筆段的屬性對於提取出的筆段，我們首先分別計算它的高度和寬度■如果這一筆段所有水平黑遊程的平均寬度大於給定的閾值，並且筆段寬度大於筆段高度，那麼判斷它為橫筆劃；■我們設定一個小步長，用MinStepLength表示，◆計算第i行和第i+MinStepLength行這兩行的水平黑遊程中點，「+」表示加號●如果中點一致，那麼角度累加器加上 ●如果第i行中點橫坐標大於第i+MinStepLength行中點的橫坐標，那麼角度累加器加上 ●如果第i行中點橫坐標小於第i+MinStepLength行中點橫坐標，那麼角度累加器加上 ◆從每個筆段的第一行往下一直掃描到距離筆段高度為零處的MinStepLength行時，將所有角度相加，求平均角度●如果平均角度大於零且比預先設定的值α1要小，那麼判斷為豎筆劃；●如果平均角度大於上述的α1且小於預先設定的值α2那麼判斷為撇筆劃；●如果平均角度大於上述的α2且小於預先設定的值α3那麼判斷為橫筆劃；●如果平均角度大於上述的α3且小於預先設定的值α4那麼判斷為捺筆劃；●如果平均角度大於上述的α4那麼判斷為豎筆劃；如果沒有新的遊程被找到，則該筆段跟蹤結束；如果沒有新的筆段被找到，則筆段提取結束；在每一筆段被提取出來時，筆段的屬性，即橫豎撇捺即也被決定；步驟五筆段合併在筆段提取完成之後，還需要將筆段進一步合併為子字符，設Ri和Rj分別為兩相鄰筆段的外接矩形；(xi，1，yi，1)——Ri的左上角點的坐標；(Xi，2，yi，2)——Ri的右下角點的坐標；(xj，1，yj，1)——Rj的左上角點的坐標；(xj，2，yj，2)——Rj的右下角點的坐標；DH(Ri，Rj)——Ri右側和Rj左側的水平距離，DH(Ri，Rj)值用正、負表示方向，Ri右邊框的水平位置在Rj左邊框的水平位置的右邊，用負值表示；否則若Ri右邊框的水平位置在Rj左邊框的水平位置的左邊，則用正值表示；DV(Ri，Ri)——Ri底側和Rj頂側的垂直距離，DV(Ri，Rj)值用正、負表示方向，Ri底側框的垂直位置在Rj頂側框的垂直位置的下面，用負值表示；否則若Ri底側框的垂直位置在Rj頂側框的垂直位置的上面，則用正值表示；width(Ri)——Ri的寬度；width(Rj)——Rj的寬度；筆段合併按照下面三個原則進行1)如果Ri和Rj滿足在水平方向上，Ri包含Rj或者Rj包含Ri，則將筆段i，j合併；2)如果Ri和Rj滿足DH(Ri，Rj)＜0(即Ri右邊框在Rj左邊框之右)，並且有-DH(Ri,Rj)width(Ri)>T1]]>或-DH(Ri,Rj)width(Rj)>T1,]]>則將筆段i，j合併，此處T1為預定義門限，一般取0.7；3)如果Ri和Rj滿足DH(Ri，Rj)＜0，並且有-DH(Ri,Rj)width(Ri)>T2]]>且-DH(Ri,Rj)width(Rj)>T2,]]>則將筆段i，j合併，此處T2為預定義門限，一般取0.5；筆段合併算法依次含有如下的步驟第5-1步初始化，筆段按水平方向上的位置從左向右排序；第5-2步按照原則(1)搜索所有需要合併的筆段，如搜索到滿足條件的筆段則將它們合併，合併完則轉向第5-1步；否則轉到第5-3步；第5-3步按照原則(2)搜索所有需要合併的筆段，如搜索到滿足條件的筆段則將它們合併，合併完則轉向第5-1步；否則轉到第5-4步；第5-4步按照原則(3)搜索所有需要合併的筆段，如搜索到滿足條件的筆段則將它們合併，合併完則結束；步驟六字符合併的幾何代價評估，包括六個子步驟我們把筆段合併的結果，從左向右排序記為s1，s2，…，sN，這就是我們筆段合併後的子字符圖像，要完成切分，需要將這些子字符圖像進行適當合併以完成切分操作；我們介紹一下子字符圖像的合併過程；我們用(sk，sk+1，...，sk+nk-1)，表示由子字符圖像sk，sk+1，...，sk+nk-1合併而成的字符圖像，我們按照下面的方式評估(sk，sk+1，...，sk+nk-1)合併的幾何代價wk——子字符圖像sk，sk+1，...，sk+nk-1合併後的字符圖像(sk，sk+1，...，sk+nk-1)的寬度；hk——子字符圖像sk，sk+1，...，sk+nk-1合併後的字符圖像(sk，sk+1，...，sk+nk-1)的高度；第6-1步字符寬度wk打分，用S(wk)表示字符寬度得分設(sk，sk+1，...，sk+nk-1)的寬度為wk，文本行的字符平均寬度為 由3-2步得出，則S(wk)=a(wkwc-1)2ifwkwc>1b(wkwc-1)2ifwkwc1]]>其中a，b均為預定義參數，一般我們取a＝100，b＝400；第6-2步字符寬高比r打分，用S(r)表示字符寬度得分S(r)=min{c(rr-1)2,100},]]>其中一般取c＝100；r為字符(sk，sk+1，...，sk+nk-1)的寬高比，r=wkhk;]]>r為字符平均寬高比r=wchc;]]> 為文本行字符平均寬度，估計方法見第3-2步； 為文本行字符平均高度，估計方法見第3-3步；第6-3步字符內部子字符間的距離打分1)外接矩形框的水平距離即子字符矩形框之間的水平距離，允許矩形框包圍的區域有重疊；2)歐幾裡德距離兩個像素點間的歐氏距離是說，如果像素點1的坐標為(x1，y1)像素點2的坐標為(x2，y2)，則這兩個像素點間的歐式距離定義為(x1-x2)2+(y1-y2)2;]]>子字符A與子字符B間的歐幾裡德距離定義為A中全部黑像素點與B中全部黑像素點之間所有的歐式距離值的最小值；3)平均遊程距離我們計算兩個子字符之間全部水平白遊程的長度的平均值作為我們的平均遊程距離；根據上述三種距離，我們定義(sk，sk+1，...，sk+nk-1)的內部距離為din=i=ki=k+nk-1di,i+1k,]]>其中子字符si與sj的距離di，j定義為di,j=nndijn]]>即是上述三種距離的加權平均和，γn是加權係數，一般來說我們取γn都為1；定義內部距離分數為S(din)=0ifdin0100ifdin>wk4ordin>wc2400dinwkotherwise]]>第6-4步字符前後的距離打分，用S(D)表示假設字符(sk，sk+1，...，sk+nk-1)與前後子字符之間的距離分別為DL和DR；DL——子字符sk的外接矩形框與子字符sk-1的外接矩形框之間的水平距離，與步驟五中的定義一致DR——子字符sk+nk-1的外接矩形框與子字符sk+nk的外接矩形框之間的水平距離，與步驟五中的定義一致如果k＝1則DL＝∞；如果k+nk-1＝N，則DR＝∞；最後取D＝min(DL，DR)；對於字符前後距離的打分為S(D)，S(D)=100ifD-wc25wc+100D-75DD+wcif-wcDD25(Dmax-D)Dmax-DifDDDmax0ifD>Dmax]]>其中 為文本行中字符的平均寬度，D和Dmax分別為文本行中子字符外接矩形框之間的水平距離的平均值和子字符外接矩形框之間的水平距離的最大值；第6-5步連通度打分，用S(C)表示定義子字符si和子字符sj的連通度Cij為 字符(sk，sk+1，...，sk+nk-1)的連通性由三個量來表示CI——內部連通性；CL——左部連通性；CR——右部連通性；其中內部連通性指的是字符內部子字符的連通程度；左部連通性和右部連通性指的是子字符sk和子字符sk-1，子字符sk+nk-1與子字符sk+nk之間的連通性；CI=1nk-1i=ki=k+nk-2Ci,i+1nk>11nk=1]]>CL=Ck,k-1k>11k=1]]>CR=Ck+nk-1,k+nkk+nk-1N1k+nk-1=N]]>連通度得分S(C)=100[1-12(1+CI-CR+CL2)];]]>第6-6步計算總體分值作為幾何代價整體的分數是以上五種分數的加權平均和S=iiSiii,]]>一般我們取α1＝5，α2＝2，α3＝3，α4＝5，α5＝2；步驟七根據已經評價出來的幾何代價計算前K條幾何代價最優的切分方式當進行完步驟六之後，我們把行圖像切分成了一列子字符圖像，同時給出了子字符塊之間合併的幾何代價，但是我們需要進一步把子字符圖像合併為字符圖像，從而完成字符的切分，下面我們利用步驟六得到的子字符塊合併的代價，生成一些可能的子字符合併方案，每個方案都對應行圖像的一種切分結果，我們在步驟八中評價這些方案，並給出最優方案；第7-1步切分圖建立對於已經切分好的N個子字符圖像s1，s2，…，sN，建立一個有向圖(V，E)，其中節點數為N+1，標記為Node1，Node2，Node3，...，NodeN+1，也即V＝{Node1，Node2，Node3，...，NodeN+1}；對於任意的Nodei，存在從Nodei到Nodei+1，Nodei+2，Nodei+3，...的有向路徑，其中路徑Nodei→Nodei+j對應了從第i，i+1，...，i+j-1塊子字符合併，也即合併子字符圖像si，si+1，...，si+j-1，路徑的代價就是此合併對應的幾何代價；切分圖每條由起點Node1到終點NodeN+1的路徑都對應了子字符圖像s1，s2，...，sN的一種合併方法，也就是對行圖像的一種切分方式，因此我們稱它為切分路徑；第7-2步產生前K條幾何代價最優的切分路徑我們下面介紹如何計算切分圖(V，E)中從起點Node1到終點NodeN+1按代價的升序排列的前K條路徑，這裡每條路徑都對應了行圖像的一種切分方式，實際上就是子字符圖像s1，s2，...，sN一種合併方案，按照此方案合併子字符s1，s2，...，sN，從而完成對行圖像的切分；算法的具體過程如下給定圖(V，E)，設NNode——圖的節點數，NNode＝N+1，N代表已經切分好的子字符圖像的個數；NEdge——邊的條數；Start——起始節點，即為Node1；Edge——終止節點，即為NodeN+1；K——需要計算的最優路徑條數；πk(v)——從起點Start到節點v的路徑總代價排第k的路徑，其中v的取值集合為節點集Node1，Node2，Node3，...，NodeN+1，所達路徑代價按升序排列，因此π1(v)就是從起點Start到端點v的最短路徑，如果取v＝NodeN+1，那麼π1(NodeN+1)表示了從起點到終點的最短路徑；Γ-1(v)——v的前趨節點的集合，即所有可能連接到v的節點的集合，對於任何u∈Γ-1(v)，均存在路徑u→v；·——兩條路徑的連接，其中a路徑的終點是b路徑的起始點，連接後的路徑a·b以a路徑的起點作為起點，b路徑終點作為終點；C[v]——節點v的候選路徑集合；然後按照下述步驟進行7-2-1步首先對於所有v∈V，計算π1(v)，即分別計算從起點Start到各個節點的最短路徑；7-2-2步對於每個v∈V，如果π1(v)，π2(v)，...，πk-1(v)已經完成，下面介紹如何利用π1(v)，π2(v)，...，πk-1(v)計算πk(v)，其中2≤k≤K；如果k＝2，那麼初始化候選路徑集合C[v]，對v的前趨節點的集合Γ-1(v)中的每一個元素u，找到從起點Start到節點u的最短路徑，構造新的路徑π1(u)·v，添加到v的候選路徑集合裡，即C[v]←{π1(u)·v|u∈Γ-1(v)}；如果k＞2，對路徑πk-1(v)，找到路徑πk-1(v)中v的前趨節點u0，即路徑πk-1(v)通過節點u0連到v，一定存在整數l，滿足1≤l≤k-1，使得πk-1(v)從起點Start到u0時走過的路徑與πl(u0)一致，也就是說πk-1(v)恰好等於由路徑πl(u0)的終點u0連接到節點v，即πk-1(v)＝πl(u0)·v，對這樣的整數l，我們再計算πl+1(u0)；然後我們從候選路徑集合C[v]裡面去掉路徑πl(u0)·v，而把πl+1(u0)·v添加到候選路徑集合C[v]裡面，即令C[v]←{C[v]-{πl(u0)·v}}∪{πl+1(u0)·v}；則求C[v]中的最短路徑，C[v]中的最短路徑就是πk(v)；遞歸地用以上算法，就得到了前K條切分路徑；第7-3步字符識別CharCandidatesSet——圖像識別候選集，其中的每個元素都包含了NCand個識別候選字和NCand個對應的識別置信度；CharCandidatesSetNum——圖像識別候選集中元素的個數；設子字符為s1s2...sN，我們建立一個(N+1)×(N+1)的查詢表，即LookupTable，LookupTable中的元素首先全部設為-1，清空圖像識別候選集，即CharCandidatesSet，並令CharCandidatesSetNum＝0；For 1≤k≤K對第k個候選切分路徑，即幾何代價按升序排列排在第k的候選切分路徑，對spsp+1...sq(1≤p≤q≤N)這樣的合併方式，查詢LookupTable中的元素LookupTable(p，q+1)，它表示查詢表LookupTable中第p行第q+1列的元素；如果LookupTable(p，q+1)＝-1，那麼說明這種合併還沒有被識別過，對這種組合得到的圖像進行識別，得到NCand個候選字，並且估計每個識別候選字的置信度，見第8-1步，然後把識別候選字及其對應的識別置信度整體作為一個元素添加到圖像識別候選集CharCandidatesSet，然後令LookupTable(p，q+1)＝CharCandidatesSetNum，同時讓CharCandidatesSetNum增加1，也即CharCandidatesSetNum＝CharCandidatesSetNum+1；如果LookupTable(p，q+1)≠-1，那麼說明這種合併已被考慮過，不用再處理End For這一過程帶來的好處是避免了識別核心的重複工作，大大節約了時間，在後面的步驟中如果我們需要知道子字符塊spsp+1...sq合併後的識別結果時，只要查詢LookupTable的第p行第q+1列元素，就得到子字符塊spsp+1...sq合併後的識別結果在CharCandidatesSet中的序號，從而找到在CharCandidatesSet對應位置中已經記錄的子字符塊spsp+1...sq合併後的識別結果及相應的置信度；步驟八依賴於前面給出的K條幾何意義下最優的候選切分方案，根據二元語法模型給出每個子字符合併方案對應的語義-識別代價第8-1步字符置信度估計x——待識別的字符圖像；cj(x)——由識別核心給出的對圖像x的第j個候選識別字，識別核心根據識別距離由小到大的升序排列識別候選字，因此c1(x)就是圖像x的首選識別候選字；dj(x)——由識別核心給出的圖像x的第j個候選識別字cj(x)對應的識別距離，因此d1(x)表示圖像x的首選識別候選字對應的識別距離；NCand——識別核心對單字字符圖像給出的識別候選字的個數，如前2-2步所述，該值為常數，只與識別核心本身有關；P(cj(x)|x)——圖像x識別為cj(x)的置信度，這是我們需要估計的對象；對於7-3步得到的所有候選字，用基於Gauss模型的置信度估計方法估計候選字的置信度P(cj(x)|x)=exp(-dj(x))k=1NCandexp(-dk(x)),]]>θ就是我們前面2-3步計算出來的；利用前面計算的混淆矩陣修正估計的置信度，其中混淆矩陣由2-4計算得到，修正置信度由P(cj(x)|x)=k=1NCandP(ck(x)|x)P(cj(x)|ck(x))]]>得到；第8-2步基於二元語法的語義-識別置信代價計算對於已經給出的K條行圖像切分路徑，對每條切分路徑應用以下的方法計算其對應的平均語義-識別置信代價，聲明如下符號及其意義nk——按照第k條切分路徑合併子字符圖像，共得到nk個合併後的字符圖像；imagek，t——按照第k條切分路徑合併子字符圖像後的第t個字符圖像，其中1≤k≤K，1≤t≤nk；cj(imagek，t)——識別核心給出的字符圖像imagek，t的第j個識別候選字，其中1≤j≤NCand，1≤k≤K，1≤t≤nk，P(cj(imagek，t)|imagek，t)對應它的識別置信度；由於字符圖像的識別和置信度的估計已經在7-3步中完成，在此步驟中我們通過查詢LookupTable的方法從CharcandidatesSet中得到我們需要的識別結果和置信度；對第k條候選切分路徑，1≤k≤K，使用下述的Vieterbi方法計算語義-識別代價令Q[nk][NCand]是一個二維數組，其中Q[t][j]保存了從第一個字符圖像某個候選字到字節點cj(imagek，t)的最大可能候選字選擇方式所具有的概率的對數值，另外取一個二維指針數組Path[nk][NCand]用於記錄計算過程；初始化t＝1，1≤j≤NCandPath[1][j]＝NULL，Q[1][j]＝log P(cj(imagek，1))+log(cj(imagek，1)|imagek，1)，遞歸2≤t≤nk，對1≤j≤NCand計算Q[t][j]，Q[t][j]=max1lNCand{Q[t-1][l]+logP(cj(imagek,t)|cl(imagek,t-1))}+logP(cj(imagek,t)|imagek]]>另外找到使得Q[t-1][l]+log P(cj(imagek，t)|cl(imagek，t-1))最大的l，記作l*，即l*=argmax1lNCand{Q[t-1][l]+logP(cj(imagek,t)|cl(imagek,t-1))},]]>然後令Path[t][j]指向字節點c1*(imagek，t-1)，即字節點cj(imagek，t)的父節點為cl*(imagek，t-1)終止t＝nk最後找到j*，使得j*=argmax1jNCandQ[nk][j],]]>回溯Path[nk][j*]所指的路徑，輸出路徑上的每個字節點，得到字符串即為我們的字符識別結果；在得到最優字符串的同時，我們也得到了最大可能路徑的概率的對數值Q[nk][j*]，我們將這個值作為對這條切分路徑的語義-識別代價估計，將這個值除以nk，得到平均語義-識別代價Hk=Q[nk][j*]nk;]]>步驟九綜合幾何代價與語義代價給出最終結果第9-1步我們需要估計幾何代價與語義-識別代價的融合參數λ聲明如下約定NL——已經給出子字符和正確子字符合併方式的行圖像個數，即訓練樣本個數；ni，k——第i個訓練樣本第k個候選切分方式對應的字符個數；ni，0——第i個訓練樣本正確切分得到字符個數；gi，k——第i個訓練樣本第k個候選切分路徑對應的幾何代價，則gi，1表示第i個訓練樣本所有切分方式中幾何代價的最小值；Gi，k——第i個訓練樣本第k個候選切分方式對應的平均幾何代價取歸一化後的值；Hi，k——第i個訓練樣本第k個候選切分方式對應的平均語義-識別代價；gi，0——第i個訓練樣本完全正確切分對應的幾何代價；Gi，0——第i個訓練樣本完全正確切分對應的平均幾何代價取歸一化後的值；Hi，0——第i個訓練樣本完全正確切分對應的平均語義-識別代價；我們挑選NL個訓練樣本行圖像，對每個行圖像按照從步驟三到步驟八的順序進行處理，從而得到ni，k，gi，k，Hi，k1≤i≤NL，1≤k≤K；我們選用下面的方式對步驟六中評價的幾何代價進行歸一化，並求其平均值，即我們令Gik=1ni,klog(e-(gi,k/gi,1-1))1iNL,1kK;]]>類似地我們按照前面的步驟得到正確切分對應的幾何代價歸一化後的分數Gi，01≤i≤NL和平均語義-識別代價Hi，01≤i≤NL；記Tik=Hi,k+Gi,k,1kK,]]>然後記Ti0*(λ)為第i個樣本完全正確切分對應的T值，即Ti0=Hi,0+Gi,0;]]>極小化N=i=1NL#{Tik>Ti0|1kK}]]>即得到對加權係數λ的估計；其中#{Tik(λ)＞Ti0(λ)|1≤k≤K}表示在給定λ的情況下，第i個樣本圖像對應的K個候選切分路徑中，T值比正確切分方式對應的T值還要大的候選路徑的個數，極小化方法依然採用類似於極小化θ的嘗試法第9-2步根據融合參數λ計算最優的切分識別路徑對一般待切分的樣本行圖像，我們依步驟三——步驟八，計算出K條候選切分路徑，並計算出每條路徑的平均識別-語義代價Hk1≤k≤K和歸一化後的平均幾何代價Gk=1nlog(e-(gk/g1-1))1kK,]]>其中gk1≤k≤K對應步驟六中得到的每條切分路徑的幾何代價，則綜合的代價Tk＝Hk+Gk1≤k≤K，取k*=argmax1kKTk,]]>則第k*個候選切分方式作為我們給出的最優切分。
全文摘要
幾何代價和語義－識別代價融合的脫機手寫漢字切分方法，屬於文字識別領域，其特徵在於，首先通過對輸入的脫機手寫漢字的行圖像進行分析，提取出筆段，將筆段合併成子字符塊，同時給出子字符塊合併的幾何代價，由這些幾何代價生成若干可能的候選切分方法，對每個方法用語言的二元語法模型進行評價，得到每種切分方式的語義－識別代價，最後綜合幾何與語義－識別代價給出最優的切分識別方案。本發明應用於手寫信封地址的切分與識別上，其切分正確率可以達到93％，大大改進了傳統切分方法的性能，對於其他語言文字或領域的切分問題也有一定的指導作用。
文檔編號G06K9/62GK1719454SQ20051001219
公開日2006年1月11日 申請日期2005年7月15日 優先權日2005年7月15日
發明者丁曉青, 蔣焰, 付強, 劉長松, 彭良瑞, 方馳 申請人:清華大學