一種動(dòng)態(tài)的漢字筆段提取方法
2008-12-31 00:00:00史偉傅彥陳安龍周俊臨
計(jì)算機(jī)應(yīng)用研究 2008年7期
摘 要：提出了一種筆段提取新方法，充分利用了撇筆段和捺筆段的輪廓規(guī)律，在提取筆段過程中動(dòng)態(tài)改變尋找方向，使提取正確率進(jìn)一步提高。實(shí)驗(yàn)證明了算法的有效性，與傳統(tǒng)筆段提取算法相比，正確率由99.3%提高到99.8%以上，為漢字識(shí)別創(chuàng)造了更有利的條件。
關(guān)鍵詞：漢字識(shí)別；筆段提取；字符點(diǎn)陣
中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：1001-3695(2008)07-1998-03
Dynamic stroke extraction algorithm for Chinese characters
SHI Wei，F(xiàn)U Yan，CHEN Anlong，ZHOU Junlin
（University of Electronic Science Technology of China， Chengdu 610054， China）
Abstract:A new algorithm was designed for Chinese stroke extraction， which based on the laws of the outline of PIE and NA.It dynamically changed the search direction during the process of extracting PIE and NA.The new dynamic algorithm had more efficiency than the traditional algorithms.The experiment shows that the extraction accuracy is increased from 99.3% to 99．8%.
Key words:Chinese character recognition；stroke extraction；character dotmatrix
方塊漢字已有數(shù)千年的歷史，也是世界上使用人數(shù)最多的文字，對(duì)中華民族燦爛文化的形成和發(fā)展有不可磨滅的功勛。在當(dāng)今的信息時(shí)代，讓計(jì)算機(jī)自動(dòng)識(shí)別漢字意義尤為重大。近些年，我國工作者對(duì)漢字的處理相繼做了不少卓有成效的研究工作，但識(shí)別的正確率仍不能滿足現(xiàn)實(shí)的需求[1]。
漢字識(shí)別的方法分為結(jié)構(gòu)方法和統(tǒng)計(jì)方法，結(jié)構(gòu)方法的優(yōu)點(diǎn)是對(duì)類別規(guī)模大、結(jié)構(gòu)復(fù)雜、相似模式多的漢字識(shí)別效果較好，所以得到了廣泛的關(guān)注和研究。采用結(jié)構(gòu)方法識(shí)別漢字的關(guān)鍵一步是提取基元，基元提取的正確率直接影響了漢字識(shí)別的正確率。結(jié)構(gòu)方法中選擇的基元可以是部件、筆劃、筆段。其中筆段是底層基元，部件和筆劃可以由筆段組合而成。目前，漢字筆段提取方法有細(xì)化法、輪廓信息法、數(shù)學(xué)形態(tài)法、小波分析法、行程長度法和段化法等。細(xì)化法可能造成圖像畸變，難有很高的正確率，且比較費(fèi)時(shí)；小波分析法還不夠成熟，目前還沒有高效的算法；輪廓信息法、數(shù)學(xué)形態(tài)法和行程長度法對(duì)字體和字型的適應(yīng)性較弱[2]。
段化法是基于點(diǎn)陣圖像行列連通像素提取筆段，與上述方法相比有自身的優(yōu)點(diǎn)，對(duì)漢字的字體和字型變化的適應(yīng)能力較強(qiáng)。但傳統(tǒng)的段化法在提取基元的正確率還有待提高，本文提出了一種動(dòng)態(tài)筆段提取算法，主要目的是進(jìn)一步提高提取基元的正確率，充分利用漢字筆段外圍輪廓的一階微分，發(fā)現(xiàn)其邊界特征，在尋找撇筆段和捺筆段時(shí)動(dòng)態(tài)調(diào)整查找優(yōu)先級(jí)，而不是簡單地在45°、135°方向上查找[3]。這與傳統(tǒng)的方法相比有明顯的優(yōu)越性，使提取結(jié)果更切合實(shí)際。
1 基本定義
本文提出的算法是以點(diǎn)陣圖像行（列）連通像素之間的關(guān)系為基礎(chǔ)，為便于敘述動(dòng)態(tài)筆段提取算法的提取過程，先把描述過程中用到的概念定義如下。
定義1 字符點(diǎn)陣圖像以N×N點(diǎn)陣取樣，且用二值圖像表示，設(shè)P(i， j)表示圖像中第i行第j列上的像素，則P（i， j）可表示為[4，6]。
P(i， j)=1前景像素
0背景像素；i， j=1，2，…，N（1）
定義2 點(diǎn)陣圖像中被人們感知為橫、豎、撇、捺四種基本筆劃之一的前景像素點(diǎn)集合稱為筆段。
定義3 集合C所含元素?cái)?shù)量count(C)為集合C中包含P（i， j）=1的像素點(diǎn)個(gè)數(shù)。
定義4 設(shè)點(diǎn)P為集合C之外的一個(gè)像素點(diǎn)，即pC，則點(diǎn)P到集合C的距離定義為P與C中所有點(diǎn)的距離的最小值，即Distance(CP)=min{[(Px-Cix)2+(Py-Ciy)2]|Ci∈C，i=1，2，…，N}。其中:
定義5 設(shè)集合C1與C2滿足C1∩C2=，則定義C1與C2的距離定義為集合C1中的點(diǎn)與集合C2中點(diǎn)的距離的最小值，即distance(C1，C2)=min{(C1ix-C2ix)2+(C1jy
定義6 合并集合C1與C2得到的集合combine （C1，C2）定義為C1∪C2，即combine(C1，C2)={Pi|Pi∈C1或Pi∈C2}。
定義7 圖像點(diǎn)陣中與像素點(diǎn)P相鄰的八個(gè)像素點(diǎn)構(gòu)成的集合，則稱該集合為點(diǎn)P的8鄰域[4]，記為neighbour（P）。
如圖 1所示，neighbour（P）={P0，P1，P2，P3，P4，P5，P6，P7}，P0~P7分別代表點(diǎn)P的
定義8 集合C所有元素的8鄰域的并集稱為該集合的8鄰域，記為neighbour（C），即
neighbour(C)={∪count(C)i=1neighbour(Pi)|Pi∈C}（2）
2 動(dòng)態(tài)筆段提取算法描述
文獻(xiàn)[3]提出了漢字筆段的直線段描述算法，并在四個(gè)方向進(jìn)行筆段提取，分別是0、45°、90°、135°方向，這也是傳統(tǒng)的方法。這種方法有嚴(yán)重的缺陷，它并不符合漢字筆段的實(shí)際特征，漢字的撇和捺筆段并不是像文獻(xiàn)[2]中所描述的那樣分別是135°和45°走向，而是有它自身的規(guī)律——階梯型向135°和45°方向延伸。典型的漢字筆段輪廓如圖2所示。
本文對(duì)漢字筆段的外圍輪廓進(jìn)行簡單的描述，研究筆段外圍輪廓的一階微分，以便發(fā)現(xiàn)其規(guī)律，并把此規(guī)律運(yùn)用到筆段提取上，使得到的筆段結(jié)果更接近于實(shí)際。為考查筆段輪廓的一階微分變化趨勢，對(duì)筆段輪廓作如下定義，如圖3所示。
對(duì)于大小為N×N的字符點(diǎn)陣，P（x，y）表示點(diǎn)陣中坐標(biāo)為（x，y）的像素點(diǎn)（見定義1），C表示筆段像素點(diǎn)的集合。
左側(cè)輪廓L(i)=min{x|P（x，y）∈C，y=i}；i=1，2，…，N
右側(cè)輪廓R(i)=max{x|P(x，y)∈C，y=i}；i=1，2，…，N
頂部輪廓T(j)=min{y|P(x，y)∈C，x=j}；j=1，2，…，N
底部輪廓B(j)=max{y|P(x，y)∈C，x=j}；j=1，2，…，N
上述四個(gè)輪廓式的一階微分分別為
對(duì)于任何筆段，如果LD（i）和RD（i）恒為1，則說明其走向趨勢分別為135°或者45°方向；如果LD（i）和RD（i）恒為0，則說明其走向趨勢分別為0或者180°方向。針對(duì)24×24的漢字庫字符點(diǎn)陣做大量的實(shí)驗(yàn)表明，對(duì)于任何一個(gè)撇或捺筆段，其左側(cè)輪廓LD(i)和右側(cè)輪廓RD(i)總小于等于2，這說明撇和捺是階梯型走向135°或者45°方向，所以在查找撇和捺筆段時(shí)不能簡單地在135°或者45°方向上查找，而應(yīng)動(dòng)態(tài)改變查詢方向，這樣才能保證查詢結(jié)果更接近于實(shí)際。實(shí)驗(yàn)還表明對(duì)于撇和捺筆段n-1i=1LD(i)，n-1i=1RD(i)的值總大于某個(gè)閾值min T（對(duì)于24×24的漢字庫點(diǎn)陣取值為5效果最佳）；對(duì)于橫筆段，n-1j=1TD(j)，n-1j=1BD(j)的值，對(duì)于豎筆段n-1i=1LD(i)，n-1i=1RD(i)總小于某個(gè)閾值max T（對(duì)于24×24的漢字庫點(diǎn)陣取值為3效果最佳）。min T和max T與字符點(diǎn)陣的大小有關(guān)，且需要實(shí)驗(yàn)確定。在提取算法中充分利用了這些特點(diǎn)，具體見下面的算法。
對(duì)于上述論斷，證明其一即可，其余論斷同理可證。對(duì)于任何筆段，若RD(i)恒為1，則說明其走向?yàn)?5°。
證明 對(duì)于i，1 2．1 算法1:scanHorizontal()(橫筆段提取算法) 設(shè)集合S為N×N字符點(diǎn)陣所有P（x，y）=1的像素點(diǎn)組成的集合。 輸入：原始字符點(diǎn)陣S。 輸出：標(biāo)記出橫筆段的字符點(diǎn)陣以及所有橫筆段的起始點(diǎn)、終止點(diǎn)的坐標(biāo)值。 1）如果S！=NULL，則在S中按從左到右、從上到下的順序找出一個(gè)像素點(diǎn)，從該點(diǎn)出發(fā)沿0方向在N×N字符點(diǎn)陣中掃描橫筆段，被掃描的點(diǎn)構(gòu)成集合T。 2)將集合S中去掉集合T。 3)如果count（T）≥min T，則記錄該筆段的起始位置和終止位置。 4)如果S！=NULL轉(zhuǎn)向1)；否則S=NULL，轉(zhuǎn)向5)。 5）對(duì)任意兩個(gè)橫筆段集合T1、T2，如果distance（T1，T2）≤1，則合并T1、T2，把T=combine（T1，T2）作為新的橫筆段集合，x1=min{x|P（x，y）∈T}，y1=min{y|P（x，y）∈T}，x2=max{x|P（x，y）∈T}，y2=max{y|P（x，y）∈T}。 6）將（x1，（y1+y2）/2）和(x2，（y1+y2）/2)作為起始點(diǎn)和終止點(diǎn)的坐標(biāo)。 7)將所有橫筆段的點(diǎn)標(biāo)記為橫點(diǎn)，橫筆段掃描結(jié)束。 2．2 算法2:scanVertical()(豎筆段提取算法) scanVertical()算法思想與scanHorizontal()一樣，為了描述的完整性，也列出了此算法的詳細(xì)步驟。 設(shè)集合S為N×N字符點(diǎn)陣所有P（x，y）=1的像素點(diǎn)組成的集合。 輸入：原始字符點(diǎn)陣S。 輸出：標(biāo)記出豎筆段的字符點(diǎn)陣以及所有豎筆段的起始點(diǎn)、終止點(diǎn)的坐標(biāo)值。 1)如果S！=NULL，則在S中按從上到下、從左到右的順序找到一個(gè)點(diǎn)，從該點(diǎn)開始沿90°方向在N×N字符點(diǎn)陣中掃描豎筆段，被掃描到的點(diǎn)構(gòu)成集合T。 2）將集合S中去掉集合T。 3）如果count（T）≥min T ，則記錄該筆段的起始位置和終止位置。 4）如果S！=NULL轉(zhuǎn)向1)；否則S=NULL，轉(zhuǎn)向5)。 5）對(duì)任意兩個(gè)豎筆段T1、T2，如果distance（T1，T2）≤1，則合并T1、T2，把T=combine（T1，T2）作為新的豎筆段集合，x1=min{x|P（x，y）∈T}，y1=min{y|P（x，y）∈T，x2=max{x|P（x，y）∈T}，y2=max{y|P（x，y）∈T}。 6）將（（x1+x2）/2，y1）和（（x1+x2）/2，y2）作為起始點(diǎn)和終止點(diǎn)的坐標(biāo)。 7）將所有豎筆段的點(diǎn)標(biāo)記為豎點(diǎn)，豎筆段掃描結(jié)束。 2．3 算法3:scanLeft()(撇筆段提取算法) 掃描撇筆段時(shí)要根據(jù)當(dāng)前像素點(diǎn)判斷下一個(gè)像素點(diǎn)的掃描方向，即動(dòng)態(tài)改變，而這個(gè)改變方向的依據(jù)正是當(dāng)前像素點(diǎn)的性質(zhì)，因此scanLeft()的輸入與前兩種算法不同。 令S為N×N點(diǎn)陣中所有P（x，y）=1的像素點(diǎn)構(gòu)成的集合，且集合中所有橫筆段標(biāo)記為橫點(diǎn)，所有豎筆段標(biāo)記為豎點(diǎn)。 輸入：處理過的字符點(diǎn)陣S。 輸出：所有撇筆段的起始點(diǎn)、終止點(diǎn)的坐標(biāo)值。 1）如果S！=NULL，則在S中從上到下、從右到左的順序找到一個(gè)點(diǎn)，從該點(diǎn)按優(yōu)先級(jí)90°、180°、135°的方向在點(diǎn)陣中掃描撇筆段。 2）如果該點(diǎn)被標(biāo)記為橫點(diǎn)，則改變優(yōu)先級(jí)為90°、135°、180°。 3）如果該點(diǎn)被標(biāo)記為豎點(diǎn)，改變優(yōu)先級(jí)為180°、135°、90°。 4）被掃描到的點(diǎn)構(gòu)成集合T，將集合S中去掉集合T。如果count（remove（T，“橫點(diǎn)”，“豎點(diǎn)”））≥max T，即集合T中除去橫點(diǎn)、豎點(diǎn)后包含元素的個(gè)數(shù)大于等于max T， 則記錄該筆段的起始位置和終止位置。 5）如果S！=NULL轉(zhuǎn)向步驟1）；否則S=NULL，轉(zhuǎn)向步驟6）。 6）對(duì)任意兩個(gè)撇筆段集合T1、T2，如果distance（T1，T2）≤1，或者P∈T1，且Pneighbour（T2），或者P∈T2，且P∈neighbour（T1），則合并T1、T2，并將T=combine（T1，T2）作為新撇筆段集合。 7）x1=min{x|P（x，y）∈T}，y1=min{y|P（x，y）∈T，x2=max{x|P（x，y）∈T}，y2=max{y| P（x，y）∈T}，并將（x2，y1）和（x1，y2）作為起始點(diǎn)和終止點(diǎn)的坐標(biāo)，撇筆段掃描結(jié)束。 2．4 算法4:scanRight()(捺筆段提取算法) scanRight()算法思想與scanLeft()一樣，為了描述的完整性，也列出了此算法的詳細(xì)步驟。 令S為N×N點(diǎn)陣中所有P（x，y）=1的像素點(diǎn)構(gòu)成的集合，且集合中所有橫筆段標(biāo)記為橫點(diǎn)，所有豎筆段標(biāo)記為豎點(diǎn)。 輸入：處理過的字符點(diǎn)陣S。 輸出：所有捺筆段的起始點(diǎn)、終止點(diǎn)的坐標(biāo)值。 1）如果S！=NULL，則在S中從上到下、從左到右的順序找到一個(gè)點(diǎn)，從該點(diǎn)按優(yōu)先級(jí)90°、0、45°的方向在點(diǎn)陣中掃描捺筆段。 2）如果該點(diǎn)被標(biāo)記為橫點(diǎn)，則改變優(yōu)先級(jí)為90°、45°、0。 3）如果該點(diǎn)被標(biāo)記為豎點(diǎn)，改變優(yōu)先級(jí)為0、45°、90°。 4）被掃描到的點(diǎn)構(gòu)成集合T，將集合S中去掉集合T。如果count（remove（T，“橫”，“豎”））≥max T， 即集合T中除去橫點(diǎn)、豎點(diǎn)后包含元素的個(gè)數(shù)大于等于max T， 則記錄該筆段的起始位置和終止位置； 5）如果S！=NULL轉(zhuǎn)向步驟1）；否則S=NULL，轉(zhuǎn)向步驟6）。 6)任意兩個(gè)捺筆段集合T1、T2，如果distance（T1，T2）≤1，或者P∈T1，且P∈neighbour（T2），或者P∈T2，且P∈neighbour（T1），則合并T1、T2，并將T=combine（T1，T2）作為新撇筆段集合； 7）x1=min{x|P（x，y）∈T}，y1=min{y|P（x，y）∈T，x2=max{x|P（x，y）∈T}，y2=max{y|P（x，y）∈T}，并將（x1，y1）和（x2，y2）作為起始點(diǎn)和終止點(diǎn)的坐標(biāo)，結(jié)束。 至此，整個(gè)筆段提取結(jié)束，得到了所有筆段的起始點(diǎn)和終止點(diǎn)的坐標(biāo)。 3 實(shí)驗(yàn)結(jié)果與對(duì)比 為測試上述筆段提取算法的實(shí)際效果，對(duì)國家標(biāo)準(zhǔn)GB2312—80規(guī)定的6 763個(gè)漢字進(jìn)行了提取實(shí)驗(yàn)（Microsoft Windows XPPIV + eclipse3.2環(huán)境），實(shí)驗(yàn)數(shù)據(jù)分別選取常用的楷體、宋體和黑體，即6 763×3個(gè)漢字。分別采用本文的算法和文獻(xiàn)[2]中的算法作提取實(shí)驗(yàn)，并把實(shí)驗(yàn)結(jié)果作對(duì)比（在同一實(shí)驗(yàn)環(huán)境下測試）。其中一級(jí)漢字的實(shí)驗(yàn)結(jié)果如表1所示。 表1 一級(jí)漢字實(shí)驗(yàn)結(jié)果 算法漢字?jǐn)?shù)用時(shí)/ms平均用時(shí)/ms/字正確率/% 本文算法3 775×322 7182.00699.94 文獻(xiàn)[2]的算法3 775×330 0842.656 499.36 二級(jí)漢字的實(shí)驗(yàn)結(jié)果如表2所示。 表2 二級(jí)漢字實(shí)驗(yàn)結(jié)果 算法漢字?jǐn)?shù)用時(shí)/ms平均用時(shí)/ms/字正確率/% 本文算法3 008×318 7192.20299.87 文獻(xiàn)[2]的算法3 008×326 8432.97599.32 從實(shí)驗(yàn)數(shù)據(jù)可以看出，無論是提取正確率和提取速度，本文算法相比傳統(tǒng)方法都有很大的提高。圖4和5都是實(shí)驗(yàn)時(shí)截取的圖片。其中：第一行是字庫中黑體字字樣；第二行是根據(jù)第一行字樣字符點(diǎn)陣提取出橫、豎、撇、捺筆段，然后畫出來的字樣。 4 結(jié)束語 本文從研究漢字筆段外圍輪廓的一階微分出發(fā)，發(fā)現(xiàn)其規(guī)律，從而在提取過程中充分運(yùn)用此規(guī)律，動(dòng)態(tài)改變其搜索方向，徹底改變傳統(tǒng)的只在45°和135°方向?qū)ふ移补P段和捺筆段的方法，使筆段提取結(jié)果更接近于實(shí)際，正確率更高。實(shí)驗(yàn)也表明了規(guī)律的科學(xué)性與算法的有效性。但本文提出的動(dòng)態(tài)筆段提取算法的對(duì)印刷體漢字提取效果最佳，對(duì)于手寫體漢字一些閾值如min T、max T等，需要大量實(shí)驗(yàn)確定，且效果不是太好。下一步研究的主題是如何使這些閾值自動(dòng)優(yōu)化，使其能運(yùn)用到手寫體漢字的筆段提取過程中。 參考文獻(xiàn)： ［1］吳佑壽，丁曉青.漢字識(shí)別原理、方法與實(shí)現(xiàn)[M].北京：高等教育出版社，1992. ［2］劉峽壁，賈云得.漢字筆段的形成規(guī)律及其提取方法[J].計(jì)算機(jī)學(xué)報(bào)，2004，27（3）：1319. ［3］王貴新，汪同慶，劉建勝，等.一種新穎的漢字筆畫提取算法[J].光電工程，2002，29（增）：3-5. ［4］胡必錦.標(biāo)準(zhǔn)漢字的自動(dòng)識(shí)別[J].重慶交通學(xué)院學(xué)報(bào)，2006，25（8）：27-32. ［5］劉云飛，李麗娟.一種基于字符邊界的細(xì)化算法[J].科學(xué)技術(shù)與工程，2006，6（10）：75-87. ［6］秦嬌華，向旭宇.漢字復(fù)雜指數(shù)特征提取技術(shù)的實(shí)現(xiàn)及其改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27（2）：13-16. ［7］張炘中，閻昌德， 劉秀英.漢字識(shí)別的特征點(diǎn)法及其一種應(yīng)用[J].中文信息學(xué)報(bào)，1987，1(3)：14-20. 注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”
