改進的骨架線提取及特征點定位算法

關鍵詞：文字細化；骨架線提取；特征點定位；視覺關注機制

0引言

近年來，隨著符號識別、文字識別、模式識別等識別技術的迅速發展，文字分割技術在醫學圖像處理、簽字印章、自動化線路檢測等各個領域得到了廣泛應用，而文字細化作為文字分割技術的關鍵特征描述，也是表征文字拓撲結構特征的重要手段。從計算機視覺角度分析，文字也是一幅傳遞信息的圖像，因此對文字進行細化研究具有重要意義[1]。

文字骨架線的提取是文字細化過程中的重要步驟，骨架線提取的質量高低與算法本身有直接關系。特別是對于結構復雜的文字，提取后的骨骼線可能存在毛刺、連通性斷點等問題，甚至出現變形或失真現象，對實際生產應用產生誤判影響。因此，在保證文字原始拓撲結構和重要特征不變的前提下，如何優化文字細化算法以獲取視覺關注質量更佳的文字骨架線，成為文字識別領域研究的熱點問題[2]。

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

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

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

1 改進的文字骨架線提取算法

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

1）首先對當前筆畫從任意邊界點Pi 出發，沿如圖1所示兩個方向順時針次序搜索，兩個方向點分別為Pj 和Pk，其中規定背景點像素值為0，前景點像素值為1。

2）對當前邊界點Pi 采用設計的細化規則進行遍歷，其計算公式如式（1）

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

3）對當前點Pi 執行N次操作按公式（2）確定遍歷終點，其計算公式如式（2）：

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

4）在起始點和終點重合時，執行設計的判別機制，其計算公式如式（3）：

為驗證提出算法的有效性，選取HWDB文字數據集中的漢字進行對比分析，圖2為本文算法相較于文獻[3]、文獻[5]和文獻[7]算法的文字細化實驗對比結果。

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

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

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

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

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

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

為驗證提出算法的有效性，在提取文字骨架線的基礎上，將提出算法與文獻[11]、文獻[12]和文獻[13]中的算法進行對比分析。圖3為4種算法的實驗對比結果。

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

3實驗結果分析

3.1實驗參數與評價指標

為驗證本文算法的有效性，在以下硬件配置環境中進行仿真實驗：Intel（R） Core（TM） i7-8700，主頻為3.2GHz，內存為16GB；軟件配置為：Microsoft VisualStudio 2010 和 OpenCV 2.4.10。測試時采用 HWDB 提供的漢字數據集。為評估本文提出算法在不同漢字數據集下的細化性能，使用細化率、相對誤差和細化節省時間 T （%） 作為提出算法提取骨架線質量的優劣指標；使用準確率（Precision，PR）、召回率（Recall，RE）以及 F-評價值（F-Measure，FM）作為提出算法綜合性能的量化指標[14]。

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

3.2 實驗結果分析

為定量分析本文算法提取文字骨架線的效果，在4種不同分辨率共100組測試數據集下，基于細化率指標與文獻[3]、文獻[5]和文獻[7]中的算法進行對比分析。表1為本文算法相較于其他3種算法的實驗對比結果。

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

在實驗結果較佳的基礎上，為進一步驗證本文算法的適用性，采用細化節省時間（T（%））表征本文算法的算法復雜度。

表2給出了本文算法相較于文獻[3]、文獻[5]和文獻[7]算法的實驗結果。從表2中可以看出，本文算法相較于其他3種算法在一定程度上節省了細化時間。

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

為進一步驗證本文算法在骨架線特征點定位精度上的準確性，在8組不同的文字測試集下，針對文字在骨架線端點、骨架線上以及孤立點三種狀態的相對誤差進行了測試分析。圖4展示了4種算法在骨架線端點、骨架線上以及孤立點三種狀態下的相對誤差對比結果，其中橫坐標數字表示測試序列編號。

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

為綜合考量本文算法的整體性能表現，在準確率、召回率以及F-評價值評估指標的基礎上，本文算法與文獻[3]、文獻[5]和文獻[7]中的算法進行了對比分析。圖5為本文算法相較于其他3種算法的實驗對比結果。

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

4 結論

本文提出了一種改進的骨架線提取及特征點定位算法。該算法首先基于深度優先遍歷及四鄰域特性設計了一種優化的遍歷規則，以提取文字骨架線，在節省一定細化時間的情況下能夠獲得主觀質量更佳的文字骨架線。然后，結合極大似然估計和空間映射關系，設計了一種骨架線定位算法，可以在確定骨架線特征點的基礎上獲得還原度更高、穩定性更強的文字骨架線。

實驗結果表明，本文提出的算法能夠獲得質量更佳的文字骨架線，在誤差極低的情況下確定骨架線特征點，并還原真實的文字骨架線。