基于K-P算法優(yōu)化的手寫漢字細化算法

范勇峰，李成城，林 民

(內(nèi)蒙古師范大學(xué) 計算機科學(xué)技術(shù)學(xué)院，內(nèi)蒙古 呼和浩特 010022)

0 引 言

漢字骨架提取(漢字細化)作為漢字提取、漢字識別與漢字書寫質(zhì)量評價等工作的上游任務(wù)，使用骨架研究中國漢字可以較為靈活的存儲漢字的字形信息，節(jié)省存儲大量像素點所需的存儲空間[1]，同時在保證原有漢字重要結(jié)構(gòu)特征的前提下減少了圖像的冗余信息，與原始圖像相比，更好突出了漢字的拓撲特征[2]，且將模式簡化為細線后可以更好進行形狀分析與特征提取等[3]。因此，使用漢字骨架進行漢字研究具有較大的優(yōu)勢。

對于當(dāng)前機器學(xué)習(xí)細化算法中存在的骨架斷裂、毛刺與交叉點畸變等問題，本文提出了一種K-P算法用以優(yōu)化現(xiàn)有的手寫漢字細化算法。算法在現(xiàn)有漢字細化算法的基礎(chǔ)上針對性地進行了如下優(yōu)化：

(1)提出交叉點匹配模板，用于后續(xù)的骨架毛刺去除等任務(wù)；

(2)使用PCA(principal component analysis)算法對骨架走勢進行判斷，并結(jié)合端點距離信息，解決骨架斷裂問題；

(3)使用PBOD(point to boundary orientation distance)算法提取畸變交叉點算法的交叉區(qū)域并擴張，對區(qū)域內(nèi)的像素點進行Kmeans++聚類，將新的聚類中心作為初始合并交叉點，并用骨架與交叉區(qū)域相交的點對初始合并交叉點做出修正，使其更接近原有走勢，最后進行B樣線性插值對骨架進行重建，解決交叉點畸變問題。

通過上述方法解決了目前漢字細化中的重點問題，提取出的骨架光滑、無冗余像素與毛刺，且交叉點無畸變，可以有效提升后續(xù)漢字識別、漢字書寫質(zhì)量評價等任務(wù)的準確性。

1 相關(guān)研究

從1967年有研究者用中軸表示連續(xù)平面上的圖形以來，許多圖像細化算法相繼應(yīng)運而生。漢字細化算法從算法層面可分為基于深度學(xué)習(xí)的細化算法與基于傳統(tǒng)機器學(xué)習(xí)的細化算法。

基于深度學(xué)習(xí)的細化算法為了從漢字圖像中提取骨架，通常會借助卷積等操作對漢字圖像進行分析，將圖像級別的分類延伸到像素級別的分類，進而提取骨架。代表性算法有Gao等[4]在形態(tài)學(xué)細化算法的基礎(chǔ)上使用卷積運算表示侵蝕與膨脹，并借助TNet(skeleton transformation network)對圖像進行轉(zhuǎn)換，成功提取了漢字骨架。Wang等[5]提出基于FCN(fully convolutional network)的手寫漢字骨架提取法，此方法首先借助rDUC(regressive dense upsampling convolution)與HDC(hybrid dilated convolution)生成用于骨架提取的像素級預(yù)測，然后使用MDF(multi-rate dilated fusion)來融合不同粒度層數(shù)上的骨架信息，最后借助多損失函數(shù)對參數(shù)進行調(diào)優(yōu)，成功提取出骨架信息。Wang.Z等[6]利用BP(back propagation)神經(jīng)網(wǎng)絡(luò)對優(yōu)化的組合模板進行訓(xùn)練，得到優(yōu)化的訓(xùn)練參數(shù)，將優(yōu)化后的參數(shù)輸入漢字細化系統(tǒng)進行快速細化?；谏疃葘W(xué)習(xí)方法的缺點是需要大量的標注信息對網(wǎng)絡(luò)進行訓(xùn)練，此外，模型的訓(xùn)練與加載成本較大，對于后續(xù)實時性的識別與評價任務(wù)有所影響。

基于傳統(tǒng)機器學(xué)習(xí)的細化算法通常是對漢字圖像的像素點或輪廓進行分析，從而得到代表漢字骨架的中軸點。根據(jù)對圖像中的不同信息進行分析，基于傳統(tǒng)機器學(xué)習(xí)的細化算法又可分為基于模板匹配的細化算法和基于距離變換的細化算法。

基于模板匹配的細化算法使用預(yù)先設(shè)定的像素點模板對圖像中前景像素點類型進行判斷，刪除符合條件的前景像素點。常見的算法有Zhang-Suen算法[7，8]、EPTA(enhanced parallel thinning algorithm)算法[9]與Hilditch算法[10]等。此類細化算法由于其模板本身限制，忽略了對部分像素點的判定，因此通常存在非單像素、毛刺與交叉點畸變等問題。而基于距離變換的細化算法主要是借助圖形的中軸與輪廓信息對圖像抽取骨架。主流的算法有蟻群搜索法[11]、點云模型法[12，13]與Delaunay三角剖分法[14]等。基于距離變換的細化算法對于圖像的質(zhì)量與在細化過程中“經(jīng)驗值”要求較高，如果圖像質(zhì)量較低或者細化過程中的“經(jīng)驗值”選取不當(dāng)就容易產(chǎn)生骨架斷裂與毛刺等問題。

除了上述的幾種方法與其對應(yīng)的改進方法外，諸多研究者[15-23]均在傳統(tǒng)機器學(xué)習(xí)細化算法的基礎(chǔ)上提出了優(yōu)化算法，并針對性的解決了上述的骨架斷裂、交叉點畸變等問題，如周正揚等[15]將交叉區(qū)域全部移除后借助局部關(guān)聯(lián)度對骨架進行重建；Sathesh等[23]檢測輪廓像素并對噪聲邊緣進行豐富，然后使用形態(tài)學(xué)操作分離輪廓中不需要的像素，從而提取目標骨架信息。雖然研究者們有針對性地提出了漢字細化問題的解決方案，但是都沒有完整解決現(xiàn)在漢字細化中的重點問題。

基于傳統(tǒng)機器學(xué)習(xí)的細化算法可以在數(shù)據(jù)量較少時通過算法本身對圖像的分解，從而提取骨架，速度較快且可以更為直觀觀察骨架點與非骨架點的區(qū)域，進而更好優(yōu)化算法，使得算法可以提取出可觀性更強的漢字骨架。因此目前對于手寫漢字細化的研究方法仍然以傳統(tǒng)機器學(xué)習(xí)算法為主。

2 基本定義

設(shè)圖像Image為二值化圖像，像素值為1的設(shè)為前景像素點，像素值為0的為背景像素點。

定義1 8-鄰域，設(shè)P1為前景像素點，則其周圍8個方向的像素點組成的集合S(P1)=[P2，P3，P4，P5，P6，P7，P8，P9] 即為其八鄰域，如圖1所示。

定義2 端點、節(jié)點、模糊點，漢字細化后其骨架中的點類型可分為3類，其分類依據(jù)前景像素點8-鄰域中其它前景像素點的數(shù)量，設(shè)P1為前景像素點，則分類依據(jù)如圖2所示。

圖2 前景像素點分類

PE、PN、PA分別代表端點、節(jié)點與模糊點，其中N(P1) 為P18-鄰域中其它前景像素點的數(shù)量，定義如下

(1)

定義3 平均筆畫寬度，設(shè)P為一骨架點，計算P點處原始筆畫邊到邊的距離，最小的距離即是P點處的筆畫寬度。對所有骨架點處的筆畫寬度累加后求均值，即為平均筆畫寬度。

其中P點處原始筆畫邊到邊的距離設(shè)為BBOD(P)，漢字圖像img大小為H×W，P點處坐標為 (x，y)， 則有

BBOD(P)=L1+L2

(2)

其中L1為一整數(shù)，滿足

img(x+L1cos(θ)，y+L1sin(θ))=0

(3)

并且對于任何整數(shù)l∈(0，L1)， 均有

img(x+lcos(θ)，y+lsin(θ))=1

(4)

L2為一整數(shù)，滿足

img(x-L2cos(θ)，y-L2sin(θ))=0

(5)

并且對于任何整數(shù)l∈(0，L2)， 均有

img(x-lcos(θ)，y-lsin(θ))=1

(6)

式(3)～式(6)中的θ=3K，K=0°，1°，2°，…，60°， BBOD(P)可存儲60個P點處原始筆畫邊到邊的距離。則P點處的筆畫寬度為

L(P)=min(BBOD(P))

(7)

設(shè)漢字骨架像素點數(shù)量為n，則平均筆畫寬度為

(8)

定義4 交叉點，對定義2中的模糊點進一步劃分，可以劃分為交叉點與非交叉點，交叉點為N(P)=3且起“分叉”作用的點，而非交叉點不起“分叉”作用。通過對模糊點的進一步劃分，可以在骨架去毛刺與交叉點畸變修復(fù)任務(wù)中更快定位到毛刺起點與交叉區(qū)域，從而減少算法的計算量，提升效率。本文對骨架圖像中的模糊點進行分析，從對稱性的分叉與不對稱的分叉出發(fā)，提出了如圖3的交叉點匹配模板，可以在模糊點匹配的基礎(chǔ)上進一步定位到交叉點。

圖3 交叉點匹配模板

3 算法研究

3.1 骨架去毛刺

由于書寫力度的不同，筆畫的寬度也隨之不同，在筆畫寬度變化較大的地方容易出現(xiàn)毛刺，而毛刺的出現(xiàn)影響后續(xù)的漢字識別或書寫質(zhì)量評價任務(wù)，因此，需要對毛刺進一步處理。本文首先對漢字圖像進行預(yù)處理，然后提取骨架并進行非單像素處理，最后通過計算交叉點到端點的距離是否大于平均筆畫寬度對毛刺進行判斷。

骨架毛刺去除算法的具體步驟如下：

步驟1 圖像預(yù)處理(包括圖像二值化、噪聲去除、中值濾波)；

步驟2 漢字細化算法結(jié)合非單像素處理方法提取漢字骨架；

步驟3 遍歷骨架圖像，找到所有的交叉點與端點；

步驟4 遍歷交叉點，沿著交叉點分叉的方向進行遍歷，直至端點(或者遍歷到的前景像素點數(shù)量大于平均筆畫寬度)，然后將遍歷路徑加入到歷史像素點列表中；

步驟5 若歷史像素點列表中像素點的數(shù)量小于平均筆畫寬度，則將列表中的像素點添加到待刪除像素列表中；

步驟6 重復(fù)步驟4、步驟5，直至所有交叉點全部遍歷完；

步驟7 在圖像中刪除所有待刪除像素列表中的像素，算法結(jié)束。

經(jīng)過毛刺去除算法處理之后的圖像如圖4(圖例骨架均采用Zhang-Suen細化算法)所示。

圖4 骨架去毛刺前后對比

由圖4可見，經(jīng)過毛刺去除算法之后，骨架變?yōu)槠交覠o冗余像素，此外借助定義4中的交叉點匹配模板對毛刺的起點進行定位，避免了因為非交叉點引起的遍歷，通過交叉點匹配后再進行毛刺去除比之前直接進行毛刺刪除節(jié)約了80%的時間。

3.2 骨架斷裂連接

由于書寫問題與圖像質(zhì)量問題，漢字提取出的骨架常常存在斷裂，這些斷裂影響了后續(xù)任務(wù)中筆畫提取與漢字特征提取等任務(wù)，因此需要對斷裂的骨架進行連接。在對斷裂的骨架進行連接時，為了預(yù)測斷點(或端點)處骨架的大致方向與其它骨架的對應(yīng)關(guān)系，避免誤連接，本文使用統(tǒng)計模式識別中一種著名的方法，即主成分分析算法(PCA)。主分量定義為協(xié)方差矩陣最大特征值對應(yīng)的特征向量，因此，主成分捕捉最大方差的方向，即骨架走勢，在數(shù)學(xué)中，將協(xié)方差矩陣寫為

(9)

式中：X，Y為坐標，l為骨架段長度，當(dāng)前斷點處骨架的主成分記為Pcurrent，其余斷點處的骨架主成分為iPcurrent(i為其它斷點，不包括當(dāng)前斷點)，計算兩者的點積為

Dp=|Pcurrent·iPcurrent|

(10)

則對應(yīng)的

(11)

式(11)中n為斷點的數(shù)量，不包括當(dāng)前斷點。通過上述公式即可計算并得出最優(yōu)的連接方案。

此外，骨架的斷裂通常都在一個小的區(qū)域范圍內(nèi)，為了減少對不同斷點主成分的分析，降低計算量與誤連接率，可借助斷點之間的距離作為輔助判斷條件。先用斷點之間的距離做一次篩選，再使用PCA算法進行判斷，如果在設(shè)定的閾值范圍內(nèi)(通過實驗測試結(jié)果，閾值為15時即可判斷兩者之間的關(guān)系)，即將兩個斷點進行連接。為了使連接后的骨架更為平滑，優(yōu)化算法使用了B樣插值法對斷裂的骨架進行修復(fù)，進而在不影響骨架原有拓撲性的基礎(chǔ)上完成骨架斷裂連接。圖像通過骨架斷裂修復(fù)算法前后對比如圖5所示。

圖5 骨架斷裂修復(fù)前后對比

3.3 交叉點畸變修復(fù)

當(dāng)前的細化算法在對圖像交叉區(qū)域處進行細化時，由于像素的剝落速度不一與圖像質(zhì)量問題，使骨架在交叉區(qū)域產(chǎn)生了畸變，由一個交叉點分裂成兩個或者更多交叉點，如圖6所示。

圖6 交叉點畸變

交叉點的畸變使后續(xù)的任務(wù)復(fù)雜度變高且準確率也會下降，因此需要對在交叉區(qū)域產(chǎn)生畸變的骨架進行修復(fù)。本文提出了一種漢字圖像與骨架圖像相結(jié)合的方法對畸變骨架進行修復(fù)，首先獲取所有的交叉點，然后對所有獲取到的交叉點按交叉點之間的距離進行分組，若某一組中存在兩個及以上的交叉點，則驗證該交叉點所在的交叉區(qū)域存在骨架畸變問題，最后對交叉區(qū)域分析，修復(fù)畸變的骨架。為了對產(chǎn)生畸變的交叉區(qū)域進行分析，本文使用PBOD算法[24]提取漢字圖像中的交叉區(qū)域：算法沿著一個前景像素點360°遍歷(每隔3°一個方向，初始方向豎直向下)，獲取每個方向上點到漢字筆畫輪廓的距離，通過計算點到漢字輪廓的距離得到每個點的PBOD曲線，觀察PBOD曲線的波谷信息，波谷數(shù)量在3個及以上的點即為交叉區(qū)域內(nèi)的點。根據(jù)波谷獲取交叉區(qū)域的角點，連接這些角點，即可提取交叉區(qū)域。設(shè)漢字圖像img大小為H×W，P點處坐標為 (x，y)， 像素點P的PBOD曲線定義如下

L=PBOD(θ)

(12)

式中：θ為曲線的橫坐標，L為縱坐標，θ=3K，K=0°，1°，2°，…，120°。

其中L為一整數(shù)，滿足

img(x+Lcos(θ)，y+Lsin(θ))=0

(13)

并且對于任何整數(shù)l∈(0，L)， 均有

img(x+lcos(θ)，y+lsin(θ))=1

(14)

由于事先借助漢字骨架獲取到了交叉區(qū)域?qū)?yīng)的交叉點，因此只需要對交叉點處理后對處理后的交叉點做PBOD算法，而不需要對全部像素點進行PBOD，減少獲取交叉區(qū)域所需時間，降低了計算量。其中交叉點處理方法如式(15)所示

(15)

式(15)中num為交叉點的數(shù)量，X，Y為處理后用來進行PBOD點的坐標。

對圖6中交叉點使用式(15)處理后進行PBOD，得到了對應(yīng)的PBOD曲線圖(如圖7所示)。

由圖7可知，該交叉區(qū)域有6個波谷，通過波谷信息可以進一步獲取交叉區(qū)域的角點坐標，連接這些角點所取得的多邊形即為交叉區(qū)域。提取結(jié)果如圖8所示。

圖8 交叉區(qū)域提取

為了修復(fù)畸變的交叉點，需要對筆畫在交叉區(qū)域處的走勢進行分析，因此首先獲取處于交叉區(qū)域內(nèi)的筆畫像素點，這些像素點大致包括了筆畫在交叉區(qū)域處的密度與走勢信息，而為了更好獲取交叉區(qū)域處筆畫的走勢信息，選擇將交叉區(qū)域向外圍進行擴張，把部分非交叉區(qū)域的筆畫像素點包括進來，這些筆畫像素點所包含的走勢信息更為豐富。

使用Kmeans++算法對這些像素點進行聚類分析，通過聚類可以發(fā)現(xiàn)像素點的分布規(guī)律，從而獲取可以反映原始筆畫走勢的聚類中心點，將獲取到的聚類中心點作為初始合并交叉點，結(jié)合骨架與交叉區(qū)域的交點作為輔助信息，借用式(15)對初始合并交叉點做出修正，使其可以更好保持原始筆畫的拓撲性，以便得到最后的合并交叉點。

得到最終的合并交叉點后，將骨架圖像中位于對應(yīng)交叉區(qū)域內(nèi)的骨架像素點全部清除后進行骨架修復(fù)。

為了使恢復(fù)的骨架不喪失原有的走勢信息，使用B樣插值法連接交叉點與骨架段，而由于使用B樣插值法連接骨架時可能會存在像素溢出問題，因此需要對修復(fù)后的骨架圖像再進行一次非單像素處理，處理后的圖像即為最終的圖像，可用于后續(xù)的漢字筆畫提取與漢字書寫質(zhì)量評價任務(wù)等。交叉區(qū)域畸變修復(fù)前后圖像如圖9所示。

圖9 交叉區(qū)域畸變修復(fù)前后對比

盡管優(yōu)化算法需要借助骨架中的交叉點信息，但是由于有交叉點匹配模板和不需要遍歷所有像素點等原因，優(yōu)化算法提取交叉區(qū)域所需時間只有原始PBOD算法提取交叉區(qū)域的15%左右。使用優(yōu)化算法后的細化算法提取出的骨架平滑、無非單像素問題且原始筆畫的拓撲性也得到了保證。

手寫漢字細化算法優(yōu)化方法流程如圖10所示。

圖10 優(yōu)化算法流程

4 實驗結(jié)果及分析

在驗證K-P算法對于現(xiàn)有細化算法的優(yōu)化效果時，選取了目前漢字細化方面使用較為廣泛的Hilditch算法、LuWang算法、Stentiford算法與Zhang-Suen算法，使用K-P算法分別在4種細化算法上進行優(yōu)化，通過對比算法優(yōu)化前后的結(jié)果驗證K-P算法的優(yōu)化效果并分析當(dāng)前優(yōu)化算法不足。

實驗所使用的數(shù)據(jù)集采集自師范生粉筆字自動訓(xùn)練系統(tǒng)中的手寫漢字圖像，為師范生參加三筆一畫考試中粉筆字測試環(huán)節(jié)中手寫漢字圖像，是自然環(huán)境中的圖像，具有較好的代表性。實驗數(shù)據(jù)從采集到的數(shù)據(jù)集選取了部分，總計100首詩詞，共875個字，均為楷體，包括了大多數(shù)的漢字筆畫形態(tài)，實驗圖像大小設(shè)置為600*600。實驗環(huán)境采用PyCharm作為開發(fā)平臺，PC機處理器為I5-7300HQ。

在4種漢字細化算法上將優(yōu)化后的算法與未優(yōu)化的算法結(jié)果進行對比，部分結(jié)果如圖11所示。

圖11 細化算法優(yōu)化前后對比

由圖11可知，細化算法經(jīng)過優(yōu)化后，毛刺、斷裂與交叉點畸變等問題基本得到了解決，提取出的漢字骨架更具有可觀性，但如果細化算法本身原因?qū)е鹿P畫骨架部分偏離了筆畫走勢，如Hilditch算法細化的骨架存在著許多凹陷，特別在筆畫“撇”中，則優(yōu)化算法無法解決。

為了進一步評估骨架提取與優(yōu)化結(jié)果，將優(yōu)化算法處理之后的圖像從優(yōu)化耗時、細化率、端點數(shù)、交叉點數(shù)4個方面與優(yōu)化前的細化算法進行對比。對比特征中的優(yōu)化耗時與細化率反映了方法的計算復(fù)雜度與細化后骨架中非單像素存在情況，端點數(shù)的多少說明了骨架是否有較多的斷裂與毛刺等，而交叉點數(shù)則是反應(yīng)骨架毛刺的數(shù)量與骨架在交叉區(qū)域是否產(chǎn)生形變，產(chǎn)生交叉點分叉的現(xiàn)象。通過對4個細化算法進行優(yōu)化并進行實驗，結(jié)果見表1。

表1 細化算法優(yōu)化前后對比

由此可知，優(yōu)化算法在細化率、端點數(shù)、交叉點數(shù)這3個方面均表現(xiàn)較多的優(yōu)勢。

(1)細化率上Stentiford算法提升最大，因為此算法的像素點匹配模板較少而忽略了部分像素點的判定，存在大量的冗余像素，經(jīng)過非單像素處理后，細化率從87.90%提升到90.83%，提升了2.93%，在4種細化算法上平均細化率也提升了1.59%，較好解決圖像中的像素冗余問題。

(2)端點數(shù)量上，優(yōu)化后的LuWang算法與真實值的差距降到了0.5，但是它是4個細化算法中唯一一個在經(jīng)過優(yōu)化后比優(yōu)化前端點數(shù)量多的一個算法，通過對數(shù)據(jù)進行分析，發(fā)現(xiàn)此算法的細化結(jié)果在骨架端點處存在較多的非單像素問題，因此造成了在經(jīng)過優(yōu)化算法之后其端點數(shù)不降反升，而其余細化算法得益于優(yōu)化算法中的骨架去毛刺與斷裂連接處理后，端點數(shù)量都有所減少。

(3)交叉點數(shù)量上，優(yōu)化后的Zhang-Suen算法與真實值差距只有0.8，最接近真實值，其原因是此算法在細化過程中產(chǎn)生的交叉點畸變與毛刺較少，因此優(yōu)化后的結(jié)果最接近真實值，而優(yōu)化后的Stentiford算法交叉點數(shù)量減少的最明顯，由優(yōu)化前的68.9減少到優(yōu)化后的8.1，對數(shù)據(jù)進行觀察后發(fā)現(xiàn)Stentiford算法對漢字的細化不夠充分，骨架中存在著大量的細小毛刺，導(dǎo)致了其交叉點數(shù)量較多，在經(jīng)過優(yōu)化后，毛刺問題得到了有效改善。優(yōu)化算法中的斷裂連接與交叉點畸變修復(fù)較好改善了當(dāng)前細化算法的缺陷，在端點與交叉點數(shù)量上與真實值的平均差距由優(yōu)化前的9.5與31.8分別降低到1.025與1.4。

(4)優(yōu)化耗時上，因為優(yōu)化算法耗時部分主要在骨架斷裂連接與交叉點畸變處理，而LuWang算法與Zhang-Suen算法的斷裂和交叉點畸變問題較其它兩個算法更少，因此在細化耗時上表現(xiàn)較為優(yōu)秀。

綜上所述，現(xiàn)有的細化算法在經(jīng)過K-P算法優(yōu)化后可以較好解決骨架圖像中非單像素、毛刺、斷裂與交叉點畸變等重點問題，從而較為完整、準確地提取手寫漢字骨架，為漢字骨架在漢字研究任務(wù)上鋪墊了良好的基礎(chǔ)。

5 結(jié)束語

K-P算法通過分析漢字書寫特征與筆畫走勢等信息解決了骨架中斷裂連接、交叉點畸變問題，彌補了現(xiàn)有細化算法的缺陷，使細化算法提取出的骨架在保證原有漢字結(jié)構(gòu)形體特征的前提下更具有可觀性。但本文在處理交叉區(qū)域時，對于交叉點組的劃分較為依靠距離因素，如果畸變的交叉點相距較遠，則畸變問題可能無法優(yōu)化。后續(xù)考慮在本文方法的基礎(chǔ)上進行手寫漢字筆畫提取與漢字特征提取，用于漢字識別與漢字書寫質(zhì)量評價任務(wù)中，從而借助更精細化與更準確的漢字書寫特征以提升漢字識別與漢字書寫質(zhì)量評價任務(wù)的準確率。