陳 睿，唐 雁

(西南大學(xué) 計算機與信息科學(xué)學(xué)院，重慶400715)

從手寫漢字文檔圖像中提取關(guān)鍵詞是一項重要的任務(wù)，它能夠作為文本相關(guān)筆跡鑒別的預(yù)處理步驟，其實質(zhì)是從數(shù)字圖像中識別和定位目標(biāo)物體。目標(biāo)物體識別一般通過將目標(biāo)物體模型的特征與數(shù)字圖像中檢測到的實體的特征進(jìn)行匹配的方式實現(xiàn)。學(xué)術(shù)界提出了大量基于整體和局部方法的能夠抗旋轉(zhuǎn)和位移的目標(biāo)物體識別和定位技術(shù)[1-3]。整體方法基于整體特征，如邊界和區(qū)域。這些方法包括不變矩、Fourier描述子和互相關(guān)。局部方法使用局部特征，包括關(guān)鍵點(Dominant Point)、局部最大曲率和多邊形近似。

Hough變換是檢測直線、圓和其他解析曲線的有效方法，對它的研究一直非?；钴S[4-5]。Hough變換在目標(biāo)識別中有效的原因就在于其把目標(biāo)的識別轉(zhuǎn)化為對在參數(shù)空間投票多少的判定。最初的Hough變換只能用來檢測形狀有解析表達(dá)式的目標(biāo)。為了檢測形狀任意的、沒有解析表達(dá)式的目標(biāo)，BALLARD[5]提出了廣義Hough變換(GHT)算法。GHT的實質(zhì)也是讓輪廓邊界點進(jìn)行投票，只是投票地點不是由表達(dá)式的參數(shù)確定，而是定義一個參考點和一套投票機制，通過投票的集中程度來判定目標(biāo)是否存在。GHT解決了任意形狀邊界目標(biāo)的識別，但它需要目標(biāo)物體的完整輪廓邊界點信息。

對于手寫漢字文檔圖像中的關(guān)鍵詞提取問題，也可以看作是一類特殊的目標(biāo)識別問題，其特殊之處在于手寫漢字字符和單詞沒有一個完整的輪廓，即使找到漢字的最小外包輪廓也不能描述漢字的大量內(nèi)部形變結(jié)構(gòu)特性。然而，基于點對點匹配投票思想的廣義Hough變換同樣適用于手寫漢字的目標(biāo)識別問題。這就需要對傳統(tǒng)的基于輪廓邊界點的投票機制進(jìn)行改進(jìn)，改為基于每個字符像素的投票機制，同時局部特征和匹配策略也要做相應(yīng)的修改。

[6]提出了一種改進(jìn)的 GHT變換算法，能有效地對具有旋轉(zhuǎn)和部分遮擋的物體進(jìn)行識別。它采用一個兩階段的GHT策略，將三維參數(shù)空間(旋轉(zhuǎn)角度θ、橫軸坐標(biāo)x和縱軸坐標(biāo)y)轉(zhuǎn)化為一個一維參數(shù)空間(θ空間)和一個二維參數(shù)空間(x-y空間)進(jìn)行投票，將 θ空間中投票的結(jié)果用作x-y空間投票的條件，降低了運算量，提高了識別精度。但是該算法有很大的局限性：(1)它需要目標(biāo)的完整輪廓，這對漢字字符和單詞不適用；(2)它假定場景圖像中只包含一個待識別的目標(biāo)物體，否則x-y空間的投票無法進(jìn)行，這就無法實現(xiàn)對場景中包含的多個目標(biāo)物體進(jìn)行匹配定位。

1 改進(jìn)的廣義Hough變換算法

針對手寫漢字的特點，對廣義Hough變換做了改進(jìn)。首先將模板圖像和文檔圖像進(jìn)行二值化和骨架化，對模板圖像中的每個字符像素提取5個局部特征作為參考表的內(nèi)容，分別是分叉數(shù)、曲率、法線方向、重心夾角和重心距離；再用文檔圖像中的每個字符像素與參考表中的每一項進(jìn)行匹配投票。下面依次介紹這5種局部特征。

1.1 分叉數(shù)

分叉數(shù)是與字符像素相連接的分支數(shù)目。傳統(tǒng)的分叉數(shù)計算方法是對字符像素的8個鄰接點計算順時針（或逆時針）方向上像素值由1到0的跳變數(shù)目。由于手寫漢字骨架圖中形變大、分支多，斷裂和冗余連接普遍存在，采用傳統(tǒng)的分叉數(shù)計算方法不能充分體現(xiàn)字符的分叉程度。針對這個問題，提出了一種改進(jìn)的計算分叉數(shù)的方法。

設(shè)經(jīng)過二值化和骨架化的模板圖像為 R，R＝{rij｜i＝1，…，m；j＝1，…，n}，其中 m 和 n 分別為模板圖像的行數(shù)和列數(shù)，字符像素定義為R中值為1的點。對于當(dāng)前考慮的字符像素rij，其半徑為t的鄰域定義為：A(rij)＝{rxy｜x＝i-t，i-t+1，…，i+t；y＝j(luò)-t，j-t+1，…，j+t}。下面給出字符像素rij在半徑為t的鄰域中的分叉數(shù)的計算。

算法 1：y＝ForkNum(R，i，j，t)

(1)置 y＝0，A(rij)＝{rxy｜x＝i-t，i-t+1，…，i+t；y＝j(luò)-t，jt+1，…，j+t}；

(2)從A(rij)的左上角開始沿順時針方向?qū)(rij)的邊界點依次放入點集 P，P(rij)＝A1，1…2t+1∪A2…2t+1，2t+1∪A2t+1，2t…1∪A2t…2，1＝{pi｜i＝1， …，8t}；

(3)依次從 P中讀取每個像點 pi(i＝1，…，8t)的值，當(dāng)pi＝1 且 pi+1＝0 時，置 y＝y(tǒng)+1；當(dāng) i＝8t時，將 p1作為 p8t+1考慮；

(4)輸出分叉數(shù) y，算法結(jié)束。

如圖1所示，黑色方塊表示字符像素，其中包含白色圓點的黑色方塊表示當(dāng)前考慮的字符像素，方形區(qū)域代表當(dāng)前考慮的二維鄰域，其大小為 11×11(半徑為5)。圖1(a)～圖1(f)分別代表分叉數(shù)從1～6的情況。如果采用傳統(tǒng)的分叉數(shù)計算方法，這6種情況下的分叉數(shù)都為2。從圖中可以看出，采用本文方法得到的分叉數(shù)能夠較準(zhǔn)確地反映出字符的局部分叉程度。鄰域大小的選擇很重要，當(dāng)鄰域大小為3×3時，本方法等價于傳統(tǒng)的分叉數(shù)計算方法。當(dāng)鄰域過大時，由于筆畫斷裂的原因，得到的分叉數(shù)不能準(zhǔn)確反映字符的局部分叉程度。本實驗中，采用字符大小的20%左右的鄰域計算效果最好。例如，對于平均字符大小為25×25的漢字文檔圖像，采用11×11的鄰域進(jìn)行計算。

1.2 曲率

曲率是表示曲線彎曲程度的量。平面曲線的曲率就是針對曲線上某個點的切線方向角對弧長的轉(zhuǎn)動率，通過微分來定義，表明曲線偏離直線的程度。曲率越大，表示曲線的彎曲程度越大。對于漢字字符圖像的每個像素，其曲率反映了筆畫的彎曲特性。對于給定大小的鄰域，采用邊界點到中心點連線的向量夾角來表示曲率，其范圍是[0，180°)。

算法 2：y＝Curvature(R，i，j，t)

(1)置 y＝0，用算法 1 的方法計算 A(rij)和 P(rij)；

(2)依次從 P中讀取每個像點 pi(i＝1，…，4t)的值，將其中連續(xù)值為 1的點劃分到集合 Sj(j＝1，…z，z≤2t)中；如果 p1＝1 且 p4t＝1，則置 S1＝S1∪Sz，z＝z-1；

(3)依 次 計 算 Sj(j＝1， …z，z≤2t)中 每 個 點 集 的 重 心位置 cj，并將其加入到集合 C 中，得到 C＝{ck｜k＝1，…，z}；

(4)依次取出 ck和 ck+1，以 ck為起點、rij為終點建立向量 v1，以 rij為起點、ck+1為終點建立向量 v2，計算 v1和v2的夾角 θ，置 y＝y(tǒng)+θ；當(dāng) k＝z時，將 c1作為 cz+1考慮；

(5)置 y＝y(tǒng)/z，算法結(jié)束。

如圖2(a)所示，白色圓點O代表當(dāng)前考慮的字符像素，白色圓點A和B代表兩個邊界點集的中心點，像點O的曲率定義為向量AO和OB的夾角。對于圖2(a)中的像點O，其曲率為15.26。對于分叉數(shù)大于2的字符像素，其曲率為相鄰邊界點集的中心點兩兩組合后與字符像素構(gòu)成向量的夾角的平均值。如圖2(b)所示，白色圓點O代表當(dāng)前考慮的字符像素，白色圓點A、B和C代表三個邊界點集的中心點，像點O的曲率定義為向量AO和OB的夾角、BO和OC的夾角及CO和OA的夾角的平均值，即 23.20°、151.70°和 5.10°的平均值 117.83°。

1.3 法線方向

曲線的法線是垂直于曲線上一點的切線的直線。對于具有相同曲率的筆畫段，若其旋轉(zhuǎn)角度不一樣，則表明兩字符具有較大差異。這個差異可以通過字符像素的法線方向來體現(xiàn)。對于給定大小的鄰域，法線方向為邊界點連線中點與當(dāng)前考慮像素的連線構(gòu)成的向量的方向角，即與橫軸按逆時針方向所成夾角，范圍是[0，360°)。

算法 3：y＝NormalAngle(R，i，j，t)

(1)置 y＝0，用算法 1 和算法 2 計算 A(rij)、P(rij)、集 合 S和集合 C＝{ck｜k＝1，…，z}；

(2)依次取出 ck和 ck+1，計算 ck和 ck+1的連線中點 mk，以mk為起點、rij為終點建立向量v，計算v與橫軸夾角θ，θ∈[0，180°)；若 v 在三、四象限，置 θ＝360°-θ。 置 y＝y(tǒng)+θ；當(dāng) k＝z時，將 c1作為 cz+1考慮；

(3)置 y＝y(tǒng)/z，算法結(jié)束。

如圖2(c)所示，像點O的法線方向定義為線段AB的中點C與O所構(gòu)成的向量CO的方向角，其值為198.94°。對于圖2(b)中像點 O的法線方向，由線段 AB、BC、CA的中點為起點，O為終點的3個向量的方向角的平均值構(gòu)成， 即 213.40°、120.85°和 19.25°的平均值為117.83°。

1.4 重心夾角

對于模板圖像中的每個字符像素，它與模板圖像重心連線構(gòu)成的向量的方向角定義為重心夾角，值域為[0，360°)，記為 GravityAngle(rij)。 如圖3 所示，字符像素 A的重心夾角定義為模板圖像重心O到A構(gòu)成的向量OA的方向角，其值為 151.09°。

1.5 重心距離

重心距離定義為字符像素到模板重心的連線的長度，記為GravityDist(rij)。如圖3所示，字符像素A的重心距離即OA的長度，其值為11.16。

1.6 參考表

對于給定模板圖像的每個字符像素，計算上述5個局部特征，它們構(gòu)成了參考表RTable中的一行。在后續(xù)的匹配過程中，對文檔圖像中的每個字符像素也提取這5個局部特征，然后與參考表中的每一行進(jìn)行匹配，如果匹配度大于某個閾值，則在參數(shù)空間中進(jìn)行投票，最終在參數(shù)空間中形成局部峰值，即定位到的模板圖像的位置。

對于圖4(a)中的模板圖像“計算機”的每個字符像素，計算它的5個局部特征，得到圖4(b)中的參考表，其中每一行對應(yīng)一個字符像素的5個局部特征。

1.7 投票算法

設(shè)經(jīng)過二值化和骨架化的模板圖像和待檢索的文檔圖像分別為 R 和 I，其中 R＝{rij｜i＝1，…，m；j＝1，…，n}，I＝{ixy｜x＝1，…，k；y＝1， …，l}，k＞m，l＞n； 參 考 表 為RTable(rt)＝{rts｜s＝1，…，z}；鄰域半徑為 t；角度差閾值為ta；參數(shù)空間圖像為 S，S＝{sxy｜x＝1，…，k；y＝1，…，l}，k＞m，l＞n；匹配度閾值為 tm；匹配度定義為 sxy與 R中字符像素個數(shù)的比值，投票算法如下：

算法 4：Vote(R，I，Rtable，ta，tm)

(1)依次讀取I中的每個字符像素 ixy(ixy≠0)，在給定鄰域 t中計算它的 5個局部特征 ForkNum(ixy)、Curvature(ixy)、NormalAngle(ixy)、GravityAngle(ixy)和 GravityDist(ixy)；

(2)對于當(dāng)前 ixy，依次讀取參考表的每一行的 5個特 征：RTable(rts，1)、RTable(rts，2)… RTable(rts，5)。 如 果RTable(rts，1)≠ForkNum(ixy)， 取 下 一 個 ixy， 重 復(fù) 步 驟 (2)；若 abs(RTable(rts，2)-Curvature(ixy))＞ta｜abs(RTable(rts，3)-NormalAngle(ixy))＞ta，取下一個 ixy，重復(fù)步驟(2)；

(3)用 RTable(rts，4)和 RTable(rts，5)計 算 模 板 圖 像 中以字符像素rts為起點、重心點G為終點的向量v，做向量運算ixy+v得到參考圖像S中的投票點sxy，置sxy＝sxy+1。取下一個 ixy，轉(zhuǎn)步驟(2)；

(4)統(tǒng)計 S中所有 sxy，sxy＞tm，將其作為匹配點畫出外包矩形。

2 實驗

本文對96名學(xué)生建立了一個手寫文檔數(shù)據(jù)庫，每名學(xué)生都書寫了一段相同的文字。如圖5所示。圖5(a)中的關(guān)鍵詞取自圖5(b)中左上角的“計算機”，它們都經(jīng)過了二值化和骨架化處理。在圖5(b)中，標(biāo)記投票數(shù)超過給定閾值的點，并對以該點為重心的關(guān)鍵詞還原其大小，用方框標(biāo)出。在這個例子中，角度差閾值取為30，鄰域半徑取為5，匹配度閾值取為0.07。從圖中可以看出，匹配點和方框集中的地方就是關(guān)鍵詞出現(xiàn)的地方，算法對關(guān)鍵詞“計算機”的提取非常準(zhǔn)確。

圖6為對圖5(c)中模板圖像進(jìn)行匹配定位的結(jié)果，其中圖5(c)的關(guān)鍵詞取自圖6中右下角的“計算機”。在這個例子中，角度差閾值取為30，鄰域半徑取為 5，匹配度閾值取為0.055。從圖中可以看出，算法找出了全部9個“計算機”的準(zhǔn)確位置，但是在圖像的右上部分出現(xiàn)了一個誤匹配，將“處理圖”和“計算機”匹配，其原因為算法在計算字符像素的局部特征時只考慮了該像素鄰域中的字符形狀特征，不能描述模板圖像整體的特征，加上手寫漢字骨架圖中形變大、分支多，斷裂和冗余連接大量存在，影響了算法定位的準(zhǔn)確性。針對這個問題，對匹配定位的結(jié)果，即提取出的關(guān)鍵詞圖像，與原模板圖像進(jìn)行相關(guān)運算，去掉相關(guān)度低于給定閾值的匹配結(jié)果。經(jīng)過實驗統(tǒng)計，給定合適的閾值(其范圍是[0.5，1.2])，在96篇手寫文檔中“計算機”整詞匹配的正確率能夠達(dá)到85%。

本文提出了一種基于廣義Hough變換的手寫漢字文檔關(guān)鍵詞提取技術(shù)。本技術(shù)使用具有形變的手寫關(guān)鍵詞圖像作模板，對該模板的每個字符像素抽取局部特征建立參考表。對于待提取的手寫文檔圖像，采用字符像素逐點匹配和投票的方式進(jìn)行廣義Hough變換，在參數(shù)空間中定位出手寫關(guān)鍵詞圖像的位置。本算法對手寫漢字文檔圖像中具有局部形變、部分旋轉(zhuǎn)和縮放的手寫關(guān)鍵詞能夠有效提取。后續(xù)工作如下：對文檔圖像進(jìn)行字符分割，對單個字符進(jìn)行匹配定位。在此基礎(chǔ)上，對超過一定數(shù)目且位置相鄰的字符進(jìn)行組合得到整詞，再進(jìn)行整詞匹配提取關(guān)鍵詞，建立訓(xùn)練集以進(jìn)行筆跡鑒別。

參考文獻(xiàn)

[1]LENG W Y，SHAMSUDDIN S M.Writer identification for Chinese handwriting[J].Int.J.Advance.Soft Comput.Appl，2011，2(2)：160-173.

[2]Tan Jun，Lai Jianhuang，Wang Changdong.A stroke shape and structure based approach for off-line Chinese handwriting identification[J].I.J.Intelligent Systems and Applications，2011，3(2)：1-8.

[3]MOKHTARIAN F，MACKWORTH A K.Scale-based description and recognition of planar curves and two-dimensional shapes[J].IEEE Trans Pattern Anal Mach Intell，1986，8(1)：34-43.

[4]HAN M H，JANG D.The use of maximum curvature points for the recognition of partially occluded objects[J].Pattern Recognition Pattern Recognition，1990，23(1-2)：21-33.

[5]BALLARD D H.Generalizing the Hough transform to detect arbitrary shapes[J].Pattern Recognition，1981，13(2)：111-122.

[6]TSAI D M.An improved generalized Hough transform overlapping objects[J].Image and Vision Computing，1997，15(12)：877-888.