基于點(diǎn)云模型的低質(zhì)漢字骨架提取算法

侯顯玲

(四川旅游學(xué)院信息與工程系，成都610100)

漢字骨架提取是漢字識(shí)別領(lǐng)域的一個(gè)重要的研究方向[1－4]，漢字骨架提取尤其是低質(zhì)漢字骨架提取仍然是一個(gè)困難問(wèn)題.本文討論的漢字降質(zhì)因素主要有五種:稀疏、斷裂、模糊、墨跡點(diǎn)以及噪聲.其中，被上述一種或幾種降質(zhì)因素同時(shí)影響的印刷體或手寫(xiě)體漢字稱作低質(zhì)漢字.大量的信息損失使得正確提取符合人類視覺(jué)的“好”的漢字骨架成為一個(gè)非常困難的問(wèn)題.文獻(xiàn)[2]中，作者給出了一個(gè)“好”的漢字骨架應(yīng)該滿足的條件:1)與原始漢字形狀接近;2)符合人類的視覺(jué);3)粗細(xì)應(yīng)是一個(gè)像素(或接近一個(gè)像素);4)獨(dú)立于原始形狀的大小、位置、質(zhì)量和辨識(shí)度;5)在噪聲擾動(dòng)和可容許的扭曲形變下應(yīng)是穩(wěn)定的.此外，“好”的骨架還應(yīng)該穿過(guò)筆畫(huà)中心.因?yàn)楣羌苁且环N在噪聲影響下具有穩(wěn)鍵性的且信息量較少的漢字替代物，是穿過(guò)數(shù)據(jù)分布中心的像素點(diǎn)集合[1－2].因此，本文中將只有同時(shí)滿足上述條件的漢字骨架才稱為“好”骨架.

過(guò)去幾十年業(yè)內(nèi)學(xué)者提出了眾多的漢字骨架提取算法，其中大多數(shù)算法都是基于漢字輪廓是可以確定的這一假設(shè)之上.基于這種假設(shè)的算法可分為三類:對(duì)稱軸分析算法、細(xì)化算法和形狀分解算法[3－4].對(duì)稱軸分析算法的思想是通過(guò)尋找漢字輪廓的對(duì)稱軸來(lái)獲得骨架[5].這類算法將骨架看作是中軸變換的對(duì)稱中心點(diǎn)構(gòu)成的集合.然而，這類算法很難在離散域里準(zhǔn)確地尋找出漢字骨架，且骨架通過(guò)中軸變化后一般都是斷裂的，從而造成算法的性能嚴(yán)重地依賴于輪廓提取的結(jié)果.這一類算法常見(jiàn)的有Tang等人提出的利用小波極大模提取漢字骨架方法[6－8].細(xì)化算法通過(guò)迭代地將目標(biāo)的邊緣點(diǎn)更新成背景點(diǎn)，最后，當(dāng)目標(biāo)變成一個(gè)由大量單像素寬的弧線和曲線所組成的集合時(shí)，也即為漢字的骨架，算法收斂.雖然這些曲線和弧線較完整地保持了目標(biāo)的拓?fù)湫再|(zhì)[2].但細(xì)化算法在處理一些規(guī)則漢字時(shí)，其提出的骨架中常常會(huì)出現(xiàn)許多斷裂和分叉.同時(shí)，這類算法也很難從間斷或稀疏嚴(yán)重的低質(zhì)漢字中提取出完好的骨架.一些研究者試圖用形狀分解算法來(lái)抑制骨架中人造小分支的產(chǎn)生[9].該類算法將目標(biāo)分解成一些簡(jiǎn)單的部分，再分別提取這些簡(jiǎn)單部分的骨架，以獲取最終目標(biāo)的骨架.例如，Zou等人通過(guò)約束的德勞內(nèi)三角形對(duì)形狀進(jìn)行分解[10－12]，該算法涉及到形狀的三角剖分、規(guī)則性分析及區(qū)域融合，計(jì)算復(fù)雜度高.

綜上，提取低質(zhì)漢字的骨架仍然是業(yè)內(nèi)的一大挑戰(zhàn)，尤其是在出現(xiàn)斷裂和稀疏的情形下，當(dāng)前大部分骨架提取算法都不能準(zhǔn)確的提取出符合人類視覺(jué)的“好”骨架.本文建立一種低質(zhì)漢字的點(diǎn)云模型，同時(shí)，將該模型與優(yōu)化和數(shù)理統(tǒng)計(jì)方法相結(jié)合，從而獲得符合人類視覺(jué)的“好”骨架.

1 點(diǎn)云模型

由于現(xiàn)有的骨架提取模型并非針對(duì)低質(zhì)漢字，因此本文提出了一種新的模型即點(diǎn)云模型.

本文討論的漢字降質(zhì)因素有稀疏、斷裂、噪聲、模糊和墨跡點(diǎn)(見(jiàn)圖1).

圖1 漢字降質(zhì)因素

圖1中，(1)～(5)為低質(zhì)漢字圖像，(6)～(10)是與之對(duì)應(yīng)的細(xì)化方法得到的骨架.

一般地，漢字筆畫(huà)在受圖1中的降質(zhì)因素干擾以后會(huì)出現(xiàn)如下的問(wèn)題:1)由一些孤立的像素點(diǎn)和孤立的像素區(qū)域構(gòu)成的稀疏筆畫(huà)使得大部分中軸算法和細(xì)化算法不能準(zhǔn)確地提取骨架;2)一些不再聯(lián)通的筆畫(huà)片段造成當(dāng)前骨架提取算法提取的骨架是斷裂的;3)在噪聲污染的筆畫(huà)中存在許多不同質(zhì)的點(diǎn)，從而引起細(xì)化算法產(chǎn)生人工分叉或無(wú)法運(yùn)行;4)模糊因素造成筆畫(huà)邊緣提取困難，因此依賴輪廓精確定位的算法無(wú)法運(yùn)行;5)墨跡點(diǎn)使?jié)h字輪廓不規(guī)則，對(duì)于這類漢字，通過(guò)對(duì)稱軸分析法所提取的骨架是斷裂的，而使用細(xì)化算法提取的骨架則產(chǎn)生長(zhǎng)的人工分叉.

圖2 漢字及其輪廓

低質(zhì)漢字的筆畫(huà)是由稀疏孤立筆畫(huà)點(diǎn)和孤立筆畫(huà)片段構(gòu)成以及低質(zhì)漢字的輪廓定位困難，從而造成基于輪廓精定位的骨架提取算法很難獲得“好”骨架.而當(dāng)前的骨架提取算法都是依賴于輪廓的精確定位，因此，本文將該模型稱之為輪廓模型.圖2中(1)和(2)給出了理想漢字(即沒(méi)有受到任何降質(zhì)因素影響的規(guī)則漢字)“標(biāo)”及其輪廓，(3)和(4)是斷裂漢字“村”及其輪廓.圖2(2)很好的描述了理想漢字“標(biāo)”的輪廓，基于此理想輪廓，采用現(xiàn)有骨架提取算法可以提取出較好的骨架，但基于圖2(4)采用現(xiàn)有算法則很難提取出符合人類視覺(jué)的“好”骨架.由于低質(zhì)漢字受到降質(zhì)因素影響無(wú)法正確提取出理想輪廓，因此輪廓模型不適用于低質(zhì)漢字.

本文利用點(diǎn)云模型來(lái)刻畫(huà)低質(zhì)漢字，通過(guò)在低質(zhì)漢字的像素點(diǎn)上直接進(jìn)行處理，從而消除漢字輪廓的定位準(zhǔn)確性帶來(lái)的影響.點(diǎn)云是在同一空間參考系下表達(dá)目標(biāo)空間分布和目標(biāo)表面特性的點(diǎn)的集合，點(diǎn)云中的點(diǎn)既可以是孤立的、稀疏的，也可以是成片的.點(diǎn)云模型不僅可以刻畫(huà)低質(zhì)漢字及多種降質(zhì)情況，還可以描述理想漢字;不依賴于輪廓定位結(jié)果，直接對(duì)漢字的數(shù)據(jù)點(diǎn)進(jìn)行處理;該模型對(duì)噪聲魯棒，處理點(diǎn)云的相關(guān)理論分析也較為成熟.

2 初始骨架提取

在點(diǎn)云模型下，為了提取出一個(gè)像素寬且滿足對(duì)稱性要求的初始骨架，本文考慮選擇一種統(tǒng)計(jì)方法來(lái)滿足對(duì)稱性要求，同時(shí)能夠?qū)崿F(xiàn)點(diǎn)云數(shù)據(jù)的降維.對(duì)稱統(tǒng)計(jì)方法中，主成分分析法(PCA)是一種簡(jiǎn)單而又魯棒的線性降維方法.假設(shè)漢字的骨架是分段線性的，若用適當(dāng)?shù)臉?biāo)簽去標(biāo)記漢字的點(diǎn)云，那么每類點(diǎn)云的對(duì)稱線性歸納構(gòu)成其主成分分量.因此，低質(zhì)漢字的初始骨架可以看成是由所有類別的主成分構(gòu)成.然而，點(diǎn)云的類別個(gè)數(shù)是并不是已知的.為了確定類別個(gè)數(shù)，本文采用增量聚類方法.因此，本文利用增量廣義K均值聚類算法來(lái)提取初始骨架.

有研究工作表明均值聚類(KMC)中心可以是單個(gè)的點(diǎn)，也可以是主成分線段[13].給定一組觀測(cè)值(x1，x2，…，xn)，廣義 K均值聚類指將 n個(gè)觀測(cè)值分成 K 個(gè)數(shù)組(k＜ n)S={S1，S2，…，Sk}，分組的標(biāo)準(zhǔn)是最小化聚類內(nèi)部的平方和即:

指中的點(diǎn)的主成分線段.

在KMC中，骨架提取結(jié)果的準(zhǔn)確性嚴(yán)重依賴于K的取值，而K的取值又隨著漢字的變化而變化.基于軟K主曲線[14]增量搜索算法，本文尋找K值的方法是逐步地增加漢字點(diǎn)云中主成分線段的數(shù)量，直到滿足收斂條件為止.最后，通過(guò)增量廣義K均值聚類方法便可得到由一些主成分線段構(gòu)成的集合，我們稱之為初始骨架.其中，集合中的元素為初始骨架段.具體地，初始骨架提取算法的步驟如下:

1)初始化步驟:基于點(diǎn)云模型，本文將低質(zhì)漢字看作二維平面點(diǎn)陣圖，表示為 X=(x1，x2，…，xn).讀入數(shù)據(jù)點(diǎn)集X，零均值化后計(jì)算出第一主成分線，然后截取圖像點(diǎn)陣重心左右3σ/2的長(zhǎng)度作為初始線段的長(zhǎng)度，其中σ2是第一主成分線上投影點(diǎn)的方差.令初始線段為s1，其對(duì)應(yīng)的Voronoi區(qū)域?yàn)?V1={x1，x2，…，xm}，k=1，n=3.

2)添加新線段步驟:首先添加新關(guān)鍵點(diǎn)(關(guān)鍵點(diǎn)按目標(biāo)函數(shù)最大下降的準(zhǔn)則選擇)，新關(guān)鍵點(diǎn)xq需滿足line(xi))}

其中:d(xi，xq)= ‖xi－ xq‖2，(i=1…m)，

則新選取的關(guān)鍵點(diǎn)xq的Voronoi區(qū)域?yàn)?

Vq={x∈X|‖x －xq‖≤min d(x，sj)，j=1，2，…k}

判斷更新后的Voronoi區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)數(shù)是否小于n，若是，則程序結(jié)束;反之，則依據(jù)1)中的方法，求取Vq中的第一主成分線段，k=k+1.

3)調(diào)整步驟:調(diào)整原有Voronoi區(qū)域中的第一主成分線段:

a.設(shè)原有 Voronoi區(qū)域?yàn)?V=(V1，V2，…，Vk);?si，i=1，…，k，求調(diào)整過(guò)后的區(qū)域 V'，其中

b.依次比較 V=(V1，V2，…，Vk)與 V'=[V'1，V'2，…，V'k]每一個(gè)區(qū)域是否相同，如果不同則計(jì)算V'j(j=1，2，…k)的第一主成分線段，完畢后更新 V=(V1，V2，…，Vk)，繼續(xù)第2)步，如果相同則結(jié)束調(diào)整步驟.

4)重復(fù)2)～3)，直到Voronoi區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)的個(gè)數(shù)小于等于n，最后輸出初始骨架.

3 初始骨架的連接

本節(jié)考慮如何連接初始骨架，以滿足“好”骨架的第1)、2)和4)條件.本文利用高層馬可夫模型將初始骨架段連接問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題.考慮到大部分漢字結(jié)構(gòu)都是規(guī)則分布的，本文將漢字的這種規(guī)則結(jié)構(gòu)作為一種先驗(yàn)信息加入到代價(jià)函數(shù)中，以獲得更加符合人類的視覺(jué)的漢字骨架.

本文基于后驗(yàn)信息，利用Bayesian理論與最大后驗(yàn)－馬爾可夫隨機(jī)場(chǎng)框架設(shè)計(jì)出了一個(gè)目標(biāo)優(yōu)化函數(shù)，以將最大后驗(yàn)概率轉(zhuǎn)化為最小后驗(yàn)勢(shì)團(tuán)能量[15].在 MAP－MRF框架下，初始骨架作為地點(diǎn)集合，集合中的每一個(gè)元素為初始骨架段.由于地點(diǎn)集合定義在特征層上，因此，我們采用高層的馬可夫隨機(jī)場(chǎng)模型.假設(shè)初始骨架由k個(gè)初始骨架段構(gòu)成，則地點(diǎn)集定義為:S={1，…，k}.S中的地點(diǎn)通過(guò)鄰域系統(tǒng)與其他地點(diǎn)相關(guān)，N={Ni-?i∈S}表示S的一個(gè)鄰域系統(tǒng).Ni是鄰近地點(diǎn)集的集合.其中，鄰域系統(tǒng)是一個(gè)所有的初始骨架段都是相鄰的全局鄰域.通過(guò)MAP－MRF理論，原優(yōu)化問(wèn)題可以轉(zhuǎn)化為一次標(biāo)記問(wèn)題，利用最小化勢(shì)團(tuán)能量來(lái)獲取最優(yōu)標(biāo)記f*(f*=arg minfU(f|d)，U(f)為能量函數(shù)).設(shè)L為標(biāo)簽集，則一個(gè)標(biāo)簽假定為由k個(gè)標(biāo)簽組成的標(biāo)簽集L中的一個(gè)離散值，即L={1，…，k}.集合f={f1，…，fk}表示標(biāo)簽集L在地點(diǎn)集S里的一次標(biāo)記.這里，能量被描述成幾個(gè)項(xiàng)之和，每項(xiàng)由確定大小的勢(shì)能團(tuán)來(lái)描述，即:

這里，把不希望得到的結(jié)果的勢(shì)團(tuán)能量定義得較大，同時(shí)將期望得到的結(jié)果的勢(shì)團(tuán)能量定義得較小.因此，這樣可以方便地加入先驗(yàn)信息.在初始骨架的接連時(shí)，我們將較小能量的兩個(gè)線段連接起來(lái)，而能量值大的兩個(gè)線段不予連接.其中，兩線段間的勢(shì)能團(tuán)能量可以描述為:

這里 αi=1，…，4 是超參數(shù)，d1(i，i')是線段 i和它鄰居線i'段間的最短距離，定義為:

d1(i，i')=inf{d(x，y)| ?x∈ i，?y∈ i';{i，i'}∈C2}

d2(i，i')線段i與它相鄰線段i'之間的夾角.d3(i，i')為線段和筆畫(huà)趨勢(shì)的角差.其中筆畫(huà)趨勢(shì)定義為:

Li表示線段 i的長(zhǎng)，α 是常數(shù)，tan θi表示線段的斜率，tan φi'為線段 i'的斜率.d4(i，i')為線段 i與i'的連接線上白點(diǎn)的數(shù)目(假定筆畫(huà)點(diǎn)為黑點(diǎn)，白點(diǎn)不是筆畫(huà)點(diǎn)).

本文初始骨架連接算法的思路是用貪婪算法去迭代地更新地點(diǎn)集與標(biāo)簽集，直到所有初始骨架線段被連接.算法步驟為:首先初始化，假設(shè)初始骨架由 m 條線段組成，S={1，…，m}，f={f1，…，fm}，定義閥值為T(mén)(依據(jù)先驗(yàn)信息，一般人工的設(shè)為7到10個(gè)像素距離).接著，計(jì)算任意兩初始骨架段間的能量U(f)，連接滿足U(f)＜T條件的線段，為了判斷連接方式，先延長(zhǎng)其中一條線段，然后用線段連接兩線段端點(diǎn).然后，更新S和f.最后，重復(fù)上一步，計(jì)算所有線段對(duì)之間的勢(shì)能團(tuán)能量，以遍歷完任意線段，且任意兩線段間的勢(shì)能團(tuán)能量U(f)＞T為止，最后輸出骨架.

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

本文提出的新方法提取低質(zhì)漢字骨架框架見(jiàn)圖3.

圖3 本文算法整體框架

初始骨架的提取和連接是提出算法的兩大核心步驟.在此框架下所提取的低質(zhì)漢字骨架滿足“好”骨架的要求.

圖4 CDT方法、軸對(duì)稱方法及本文方法提取結(jié)果對(duì)比

為了更好地描述本文所提出的低質(zhì)漢字骨架提取新方法性能，我們將CDT方法、軸對(duì)稱方法與新方法的提取骨架結(jié)果進(jìn)行了比較.在圖4中，第一列是低質(zhì)漢字.第二列是CDT方法骨架提取的結(jié)果，提取的骨架存在人工小分支和斷裂，，不滿足保持拓?fù)湫院团c人類視覺(jué)吻合的要求，不是“好”骨架，從圖4(2)中可以看出CDT并不適用于稀疏漢字情況.第三列是軸對(duì)稱方法獲得的骨架結(jié)果，同樣存在稀疏斷裂的情況，且無(wú)法對(duì)受噪聲點(diǎn)影響的漢字提取骨架，第四列是我們的方法提取的結(jié)果.其中，為了顯示最終骨架與低質(zhì)漢字的吻合度，綠色的最終骨架被疊放在黑色的低質(zhì)漢字上.很明顯最終骨架與漢字有很高的吻合度，這說(shuō)明我們方法提取的骨架很好地修正和保持了低質(zhì)漢字的拓?fù)涮匦?很顯然，最后一列骨架滿足本文第一節(jié)所提出的“好”骨架的要求.

5 結(jié)語(yǔ)

本文提出了一個(gè)新的適合低質(zhì)漢字骨架提取的模型即點(diǎn)云模型.在點(diǎn)云模型基礎(chǔ)上，本文的新方法分兩步實(shí)現(xiàn)骨架提取:首先獲取初始骨架，本文利用增量廣義均值聚類方法;然后在高層馬可夫模型下連接初始骨架，最終得到的骨架滿足“好”骨架要求.本文方法是基于概率統(tǒng)計(jì)和優(yōu)化理論，因此在很多降質(zhì)因素影響的情形下也具有高魯棒性.

[1]LAM L，LEE S W，SUEN C Y.Thinning methodologies:A comprehensive survey[J].IEEE Trans.Pattern and Machine Intelligence，1992，14(9):869－885.

[2]廖志武.2－D骨架提取算法研究進(jìn)展[J].四川師范大學(xué)學(xué)報(bào):自然科學(xué)版，2009，32(5):5676－5688.

[3]KLETTE G.A comparative discussion of distance transforms and simple deformations in digital image processing(a survey)[J].Machine Graphics and Vision International Journal，2003，12(2):235－256.

[4]CAGRI A.Disconnected skeletons for shape recognition[D].Mph thesis for Middle East Technical University，2005.

[5]H LUM.Biological shape and visual science(Part 1)[J].J Theo Biol，1973，38:205 －287.

[6]TANG Y Y，YOU X G.Skeletonization of ribbon－like shapes based on a new wavelet function[J].IEEE Trans.Pattern and Machine Intelligence，2003，25(9):1118 －1133.

[7]YOU X G，CHEN Q，F(xiàn)ANG B，et al.Thinning character using modulus minima of wavelet transform[J].International Journal of Pattern Recognition and Artificial Intelligence，2006，20(3):361－375.

[8]YOU X G，TANG Y Y.Wavelet－based approach to character skeleton[J].IEEE Transactions on Image Processiong，2007，16(5):1220－1231.

[9]SIMON J C.A complemental approach to feature detection[C]//From Pixels to Features，Amsterdam:Elsevier Science，Netherlands，1989:229 －236.

[10]ZOU J J，YAN H.Skeletonization of ribbon－like shapes based on regularity and singularity analyses[J].IEEE Trans Syst Man Cybern，2001，31B(3):401－407.

[11]MORRISON P，ZOU J J.Triangle refinement in a constrained delaunay triangulation skeleton [J]. Pattern Recognition，2007，40(10):2754－2765.

[12]ZOU J J.Efficient skeletonization based on generalized discrete local symmetries[J].Optical Engineering，2006，45(7):1－7.

[13]DING C，HE X.－means clustering via principal component analysis[C]//Proc.of Int’l Conf.Machine Learning(ICML 2004)，2004:225－232.

[14]VERBEEK J J，VLASSIS N，KOSE B.A k－segments algorithm for finding Principal Curves[J].Pattern Recognition Letters，2002，23:1009 －1017.

[15]STAN Z L.Markov random field modeling in computer vision[M].3rd.Berlin:Springer，2009.