改進(jìn)的骨架線提取及特征點(diǎn)定位算法

關(guān)鍵詞：文字細(xì)化；骨架線提??；特征點(diǎn)定位；視覺關(guān)注機(jī)制

0引言

近年來，隨著符號識別、文字識別、模式識別等識別技術(shù)的迅速發(fā)展，文字分割技術(shù)在醫(yī)學(xué)圖像處理、簽字印章、自動化線路檢測等各個(gè)領(lǐng)域得到了廣泛應(yīng)用，而文字細(xì)化作為文字分割技術(shù)的關(guān)鍵特征描述，也是表征文字拓?fù)浣Y(jié)構(gòu)特征的重要手段。從計(jì)算機(jī)視覺角度分析，文字也是一幅傳遞信息的圖像，因此對文字進(jìn)行細(xì)化研究具有重要意義[1]。

文字骨架線的提取是文字細(xì)化過程中的重要步驟，骨架線提取的質(zhì)量高低與算法本身有直接關(guān)系。特別是對于結(jié)構(gòu)復(fù)雜的文字，提取后的骨骼線可能存在毛刺、連通性斷點(diǎn)等問題，甚至出現(xiàn)變形或失真現(xiàn)象，對實(shí)際生產(chǎn)應(yīng)用產(chǎn)生誤判影響。因此，在保證文字原始拓?fù)浣Y(jié)構(gòu)和重要特征不變的前提下，如何優(yōu)化文字細(xì)化算法以獲取視覺關(guān)注質(zhì)量更佳的文字骨架線，成為文字識別領(lǐng)域研究的熱點(diǎn)問題[2]。

為提高文字細(xì)化準(zhǔn)確率，國內(nèi)外學(xué)者提出了多種優(yōu)化的文字細(xì)化算法。文獻(xiàn)[3]對Hilditch細(xì)化算法進(jìn)行改進(jìn)，獲得了準(zhǔn)確率更高的細(xì)化算法，但其抗干擾性能較差。文獻(xiàn)[4]對EPTA算法進(jìn)行優(yōu)化，獲取了文字骨架模型，但對文字交叉點(diǎn)及拐點(diǎn)的處理效果不佳。文獻(xiàn)[5]基于旋轉(zhuǎn)不變性對Pavlidis 算法進(jìn)行改進(jìn)，獲得了質(zhì)量更高的文字細(xì)化線，但對于筆畫較多的繁體文字仍存在細(xì)化不完全現(xiàn)象。文獻(xiàn)[6]采用徑向神經(jīng)網(wǎng)絡(luò)算法設(shè)計(jì)了一種迭代規(guī)則進(jìn)行文字細(xì)化，雖然獲得了較佳的文字骨架線，但細(xì)化結(jié)果嚴(yán)重依賴于參數(shù)選擇，適用性較差，且算法復(fù)雜度較高。文獻(xiàn)[7]對Zhang并行細(xì)化算法進(jìn)行優(yōu)化改進(jìn)，雖然進(jìn)一步降低了毛刺現(xiàn)象，但細(xì)化的文字骨架線易出現(xiàn)局部信息缺失問題。

以上算法在提高文字骨架線質(zhì)量方面取得了一定的成效，但細(xì)化的準(zhǔn)確率和真實(shí)性仍存在一定不足。這些算法多是從自身優(yōu)化角度或給予現(xiàn)有算法存在的弊端進(jìn)行改進(jìn)，其細(xì)化性能和魯棒性仍需提升。

本文從骨架線提取和骨架線定位兩個(gè)方面著手，以獲得更符合視覺關(guān)注度的文字骨架線。首先，基于深度優(yōu)先遍歷和八鄰域特性提出一種骨架線提取規(guī)則，并進(jìn)行迭代判斷，提取出準(zhǔn)確率更高的文字細(xì)化模型。然后，在提取的文字細(xì)化骨架線上采用極大似然估計(jì)結(jié)合空間映射機(jī)理定位文字骨架線，提高細(xì)化后文字的還原度，以達(dá)到真實(shí)性高、魯棒性強(qiáng)的文字骨架線要求和目的。

1 改進(jìn)的文字骨架線提取算法

針對 Zhang 并行細(xì)化算法在細(xì)化后文字存在局部信息缺失或毛刺問題，Li 等[8]對 Zhang 并行細(xì)化算法進(jìn)行了優(yōu)化，獲得了質(zhì)量更佳的文字骨架線，但對于個(gè)別繁體文字仍然不具普適性。研究表明[9]，文字骨架線是表征文字重要特征的關(guān)鍵信息，其特征主要分布在點(diǎn)和線上。本文首先將文字按書寫順序?qū)P畫進(jìn)行拆分并逆序壓入棧中，然后基于四鄰域機(jī)制按出棧順序?qū)γ總€(gè)筆畫采用設(shè)計(jì)的細(xì)化規(guī)則進(jìn)行遍歷和細(xì)化，確定細(xì)化后的骨架線點(diǎn)；最后，根據(jù)邊界點(diǎn)特性采用提出的判別機(jī)制篩選骨架線點(diǎn)，獲得細(xì)化后的文字骨架。

1）首先對當(dāng)前筆畫從任意邊界點(diǎn)Pi 出發(fā)，沿如圖1所示兩個(gè)方向順時(shí)針次序搜索，兩個(gè)方向點(diǎn)分別為Pj 和Pk，其中規(guī)定背景點(diǎn)像素值為0，前景點(diǎn)像素值為1。

2）對當(dāng)前邊界點(diǎn)Pi 采用設(shè)計(jì)的細(xì)化規(guī)則進(jìn)行遍歷，其計(jì)算公式如式（1）

式中：? （ Pi ，Pj ）E 表示點(diǎn)Pj 和Pk 都存在，? （ Pi ，Pj ）E表示點(diǎn)Pj 和Pk 僅有一個(gè)存在，NF （ Pj ） 表示Pj 點(diǎn)四鄰域像素值為0的點(diǎn)，NF （ Pk ）表示Pk 點(diǎn)四鄰域像素值為0的點(diǎn)，?表示與關(guān)系，Nbp 表示下一鄰接點(diǎn)，?表示終止該方向遍歷。

3）對當(dāng)前點(diǎn)Pi 執(zhí)行N次操作按公式（2）確定遍歷終點(diǎn)，其計(jì)算公式如式（2）：

式中：Pi （1） 表示遍歷初始點(diǎn)，Pi （N ） 表示遍歷N次終點(diǎn)，? F 表示執(zhí)行N 次遍歷起始點(diǎn)和終點(diǎn)重合時(shí)執(zhí)行下一公式（3），Ω表示執(zhí)行N 次遍歷起始點(diǎn)和終點(diǎn)不重合時(shí)保留遍歷過的骨架線點(diǎn)。

4）在起始點(diǎn)和終點(diǎn)重合時(shí)，執(zhí)行設(shè)計(jì)的判別機(jī)制，其計(jì)算公式如式（3）：

為驗(yàn)證提出算法的有效性，選取HWDB文字?jǐn)?shù)據(jù)集中的漢字進(jìn)行對比分析，圖2為本文算法相較于文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]算法的文字細(xì)化實(shí)驗(yàn)對比結(jié)果。

從人眼視覺關(guān)注機(jī)制主觀分析，圖2中本文提出的改進(jìn)的文字骨架線提取算法能夠獲得質(zhì)量更高的文字骨架線。相較于文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]的算法，該算法能很好地消除局部信息缺失和毛刺現(xiàn)象，實(shí)驗(yàn)效果更佳。

2 提出的文字骨架線定位算法

針對文字骨架線定位精準(zhǔn)度問題，許多學(xué)者提出了改進(jìn)的算法。Han等[10]基于縮放因子提出了優(yōu)化的特征點(diǎn)定位算法，但單一縮放因子難以實(shí)現(xiàn)精確定位且定位準(zhǔn)確率不高。本文采用提出的自適應(yīng)參數(shù)估計(jì)算法來確定細(xì)化后文字骨架線的位置。該算法基于三維空間到二維空間的映射機(jī)制，根據(jù)坐標(biāo)參數(shù)確定細(xì)化后文字骨架線點(diǎn)的實(shí)際位置。首先，對提取的文字骨架線點(diǎn)根據(jù)似然函數(shù)定義確定似然函數(shù)參數(shù)方程組；然后，對似然函數(shù)參數(shù)方程組求極值，得到方程組的駐點(diǎn)，即為極大似然函數(shù)估計(jì)值；最后，根據(jù)三維空間到二維空間的映射機(jī)制，由估計(jì)值確定二維空間坐標(biāo)點(diǎn)，最終確定文字骨架線的實(shí)際位置。

1）首先，細(xì)化前文字在三維空間的坐標(biāo)點(diǎn)Pi 可定義為（αx，βy，γz），細(xì)化后文字在二維空間的坐標(biāo)點(diǎn)可定義為（k1x1，k2 x2 ），則三維空間到二維空間的映射公式如式（4）：

對方程組（7）求解得到駐點(diǎn)，記為α'、β'、γ'，則α'、β'、γ'即為參數(shù)估計(jì)值。根據(jù)公式（4）即可確定k1、k2的數(shù)值，進(jìn)一步確定骨架線點(diǎn)的坐標(biāo)位置，最終得到細(xì)化后文字骨架線在二維空間的實(shí)際位置。

綜上所述，根據(jù)在二維空間實(shí)際位置確定的文字骨架線，按出棧順序進(jìn)行合并，最終得到細(xì)化后的文字骨架線真實(shí)位置。

為驗(yàn)證提出算法的有效性，在提取文字骨架線的基礎(chǔ)上，將提出算法與文獻(xiàn)[11]、文獻(xiàn)[12]和文獻(xiàn)[13]中的算法進(jìn)行對比分析。圖3為4種算法的實(shí)驗(yàn)對比結(jié)果。

從圖3中可以看出，本文提出的算法相較于其他三種算法能夠更精確地定位文字骨架線的特征點(diǎn)。相較于本文提出的算法，文獻(xiàn)[11]和文獻(xiàn)[12]的算法在特征點(diǎn)定位上存在較大偏差，而文獻(xiàn)[13]的算法在定位精度上有所改善，但其定位效果仍不如本文提出的算法。

3實(shí)驗(yàn)結(jié)果分析

3.1實(shí)驗(yàn)參數(shù)與評價(jià)指標(biāo)

為驗(yàn)證本文算法的有效性，在以下硬件配置環(huán)境中進(jìn)行仿真實(shí)驗(yàn)：Intel（R） Core（TM） i7-8700，主頻為3.2GHz，內(nèi)存為16GB；軟件配置為：Microsoft VisualStudio 2010 和 OpenCV 2.4.10。測試時(shí)采用 HWDB 提供的漢字?jǐn)?shù)據(jù)集。為評估本文提出算法在不同漢字?jǐn)?shù)據(jù)集下的細(xì)化性能，使用細(xì)化率、相對誤差和細(xì)化節(jié)省時(shí)間 T （%） 作為提出算法提取骨架線質(zhì)量的優(yōu)劣指標(biāo)；使用準(zhǔn)確率（Precision，PR）、召回率（Recall，RE）以及 F-評價(jià)值（F-Measure，F(xiàn)M）作為提出算法綜合性能的量化指標(biāo)[14]。

其中，細(xì)化率表征刪除的前景像素點(diǎn)與所有前景像素點(diǎn)的比值；相對誤差表征獲取特征點(diǎn)相對實(shí)際特征點(diǎn)位置之間歐式距離相對模型最大邊長的百分比。

3.2 實(shí)驗(yàn)結(jié)果分析

為定量分析本文算法提取文字骨架線的效果，在4種不同分辨率共100組測試數(shù)據(jù)集下，基于細(xì)化率指標(biāo)與文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中的算法進(jìn)行對比分析。表1為本文算法相較于其他3種算法的實(shí)驗(yàn)對比結(jié)果。

從表1中可以看出，本文算法在4組不同分辨率文字?jǐn)?shù)據(jù)集下的細(xì)化率結(jié)果均大于文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]的算法實(shí)驗(yàn)數(shù)值。這表明本文算法對于不同分辨率的文字具有更高的識別精度和更佳的細(xì)化效果，能夠進(jìn)一步消除像素缺失或毛刺現(xiàn)象。對于不同分辨率的測試數(shù)據(jù)集，細(xì)化率有所差異，這是由于分辨率越高的文字其邊緣像素飽和度越高，但不影響本文算法自身較高的魯棒性。

在實(shí)驗(yàn)結(jié)果較佳的基礎(chǔ)上，為進(jìn)一步驗(yàn)證本文算法的適用性，采用細(xì)化節(jié)省時(shí)間（T（%））表征本文算法的算法復(fù)雜度。

表2給出了本文算法相較于文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]算法的實(shí)驗(yàn)結(jié)果。從表2中可以看出，本文算法相較于其他3種算法在一定程度上節(jié)省了細(xì)化時(shí)間。

這表明在細(xì)化結(jié)果得到較大改善的情況下，本文算法能夠在一定程度上節(jié)省細(xì)化時(shí)間。

為進(jìn)一步驗(yàn)證本文算法在骨架線特征點(diǎn)定位精度上的準(zhǔn)確性，在8組不同的文字測試集下，針對文字在骨架線端點(diǎn)、骨架線上以及孤立點(diǎn)三種狀態(tài)的相對誤差進(jìn)行了測試分析。圖4展示了4種算法在骨架線端點(diǎn)、骨架線上以及孤立點(diǎn)三種狀態(tài)下的相對誤差對比結(jié)果，其中橫坐標(biāo)數(shù)字表示測試序列編號。

從圖4中的分析可知，本文算法在骨架線端點(diǎn)、骨架線上點(diǎn)以及孤立點(diǎn)三種狀態(tài)下的相對誤差均小于其他3種算法，這表明本文算法在文字骨架線特征點(diǎn)定位精度上更高，即本文算法對于細(xì)化文字的還原度更真實(shí)。相較于骨架線端點(diǎn)和骨架線上點(diǎn)兩種狀態(tài)，在孤立點(diǎn)狀態(tài)下，本文算法的相對誤差范圍更小，誤差范圍不高于0.8%，這依然證明了本文算法在文字細(xì)化方面的優(yōu)越性能。

為綜合考量本文算法的整體性能表現(xiàn)，在準(zhǔn)確率、召回率以及F-評價(jià)值評估指標(biāo)的基礎(chǔ)上，本文算法與文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中的算法進(jìn)行了對比分析。圖5為本文算法相較于其他3種算法的實(shí)驗(yàn)對比結(jié)果。

通過對圖5中的數(shù)據(jù)進(jìn)行分析，在準(zhǔn)確率方面，相較于文獻(xiàn)[3]算法、文獻(xiàn)[5]算法和文獻(xiàn)[7]算法，本文算法的PR 值更高，表明本文算法在文字骨架線提取方面具有更高的準(zhǔn)確性，即本文算法在文字骨架線的識別率上更具優(yōu)勢。在召回率方面，本文算法的實(shí)驗(yàn)結(jié)果更為可觀，這是由于本文算法在文字細(xì)化結(jié)果的真實(shí)性上具有較強(qiáng)的普適性。相較于其他3種算法，本文算法的FM 值最高，這表明本文算法在文字細(xì)化整體性能上表現(xiàn)最佳。綜上所述，本文算法在文字骨架線提取方面具有更高的準(zhǔn)確性和魯棒性。

4 結(jié)論

本文提出了一種改進(jìn)的骨架線提取及特征點(diǎn)定位算法。該算法首先基于深度優(yōu)先遍歷及四鄰域特性設(shè)計(jì)了一種優(yōu)化的遍歷規(guī)則，以提取文字骨架線，在節(jié)省一定細(xì)化時(shí)間的情況下能夠獲得主觀質(zhì)量更佳的文字骨架線。然后，結(jié)合極大似然估計(jì)和空間映射關(guān)系，設(shè)計(jì)了一種骨架線定位算法，可以在確定骨架線特征點(diǎn)的基礎(chǔ)上獲得還原度更高、穩(wěn)定性更強(qiáng)的文字骨架線。

實(shí)驗(yàn)結(jié)果表明，本文提出的算法能夠獲得質(zhì)量更佳的文字骨架線，在誤差極低的情況下確定骨架線特征點(diǎn)，并還原真實(shí)的文字骨架線。