基于廣義Hough變換的手寫漢字文檔關(guān)鍵詞提取

陳 睿，唐 雁

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

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

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

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

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

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

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

1.1 分叉數(shù)

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

設(shè)經(jīng)過二值化和骨架化的模板圖像為 R，R＝{rij｜i＝1，…，m；j＝1，…，n}，其中 m 和 n 分別為模板圖像的行數(shù)和列數(shù)，字符像素定義為R中值為1的點(diǎn)。對(duì)于當(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ù)的計(jì)算。

算法 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)的左上角開始沿順時(shí)針方向?qū)(rij)的邊界點(diǎn)依次放入點(diǎn)集 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中讀取每個(gè)像點(diǎn) pi(i＝1，…，8t)的值，當(dāng)pi＝1 且 pi+1＝0 時(shí)，置 y＝y(tǒng)+1；當(dāng) i＝8t時(shí)，將 p1作為 p8t+1考慮；

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

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

1.2 曲率

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

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

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

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

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

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

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

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

1.3 法線方向

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

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

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

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

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

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

1.4 重心夾角

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

1.5 重心距離

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

1.6 參考表

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

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

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中字符像素個(gè)數(shù)的比值，投票算法如下：

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

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

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

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

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

2 實(shí)驗(yàn)

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

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

本文提出了一種基于廣義Hough變換的手寫漢字文檔關(guān)鍵詞提取技術(shù)。本技術(shù)使用具有形變的手寫關(guān)鍵詞圖像作模板，對(duì)該模板的每個(gè)字符像素抽取局部特征建立參考表。對(duì)于待提取的手寫文檔圖像，采用字符像素逐點(diǎn)匹配和投票的方式進(jìn)行廣義Hough變換，在參數(shù)空間中定位出手寫關(guān)鍵詞圖像的位置。本算法對(duì)手寫漢字文檔圖像中具有局部形變、部分旋轉(zhuǎn)和縮放的手寫關(guān)鍵詞能夠有效提取。后續(xù)工作如下：對(duì)文檔圖像進(jìn)行字符分割，對(duì)單個(gè)字符進(jìn)行匹配定位。在此基礎(chǔ)上，對(duì)超過一定數(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.