一種基于模板的二階段ZS細化算法

陳 品，王 濤，張德港

(華南師范大學 計算機學院，廣東 廣州 510631)

0 引 言

細化算法是指在保持原二值圖像的拓撲結構和連通性的前提下，生成單像素寬度的骨架圖[1]。骨架是一種重要的圖像幾何特征，利用骨架來表示原始圖像，可以在保持圖像重要拓撲信息的前提下極大地消除圖像中的冗余信息,提取目標特征,簡化后續圖像處理數據量,提高運行速度。因此，細化是很多圖像預處理中的重要步驟,目前細化算法已經廣泛應用于指紋識別[2]、漢字處理[3]、裂縫檢測[4]、儀表檢測[5]、物料分選[6]等場景。

優秀的細化算法應在維持原圖拓撲結構的前提下,既保持骨架的連通性，又不會過度腐蝕,并具有一定的抗噪性能。理想的細化紋線骨架應在中間位置,且保持紋線的連接性、拓撲結構和細節特征。因此，細化算法應滿足以下幾點要求[7]：

(1)收斂性：迭代必須是收斂的。

(2)連接性：不破壞紋線的連接性。

(3)拓撲性：不引起紋線的逐步吞食,保持原圖像的基本結構特性。

(4)保持性：保護原圖像的細節特征。

(5)細化性：骨架紋線的寬度為1個像素,即單像素寬。

(6)中軸性：骨架盡可能接近條紋中心線。

(7)快速性：算法簡單,速度快。

由以上7點要求中可以發現,前6條要求主要集中在對細化質量的評價,最后一條是對細化速度的要求。因此，評價一個細化算法的優劣,主要是從細化質量和細化速度兩個方面進行。

根據細化算法實現特點,可將細化算法分為兩大類：迭代法和非迭代法。非迭代細化算法不以基本像素點為處理條件,而是通過直接計算圖像的中心線或中值線生成骨架圖。非迭代算法的最大優點是處理速度快,但缺點是骨架有時會斷開或留下一些不必要的分支,通常骨架連通性差。迭代細化算法在每次迭代中以相同的條件迭代刪除邊緣像素點,直到生成骨架。迭代細化算法可分為串行細化算法和并行細化算法。串行細化算法通過光柵掃描或跟蹤圖像輪廓,按順序標記刪除邊緣像素點,刪除條件取決于之前所有迭代的結果和本次迭代中已處理過像素點情況。串行細化算法在處理目標圖像時,采用邊檢驗邊刪除的方式,雖然運行速度快,但每次像素點判定是否刪除難以預測,同時受到掃描順序的影響,容易造成骨架不對稱。并行細化算法在每次迭代用相同的約束條件處理目標圖像中所有的像素點,檢測并標記符合條件的像素點,在完成掃描后統一刪除。并行細化算法每次迭代細化的結果僅與本次目標像素點的鄰域相關,像素點的保留與否確定,骨架對稱性較好,因此并行細化算法成為研究的熱點。

ZS細化算法[8]是經典的快速并行細化算法之一,該算法能較精確地保持直線、T型交叉點和拐角等結構,細化速度快。但該算法會存在二像素斜線結構斜線細化消失的現象,同時細化后也會產生二像素寬度的冗余像素,此外2×2像素正方形結構在細化后消失。ZS細化算法在細化過程中交替消去左上邊緣像素和右下邊緣像素,消去操作不勻稱,容易產生邊緣輪廓分叉現象。LW細化算法[9]在ZS細化算法基礎上進行改進,放寬了迭代過程中像素刪除的判定條件,使得二像素斜線結構保留,避免二像素斜線結構局部信息丟失,但會產生更多邊緣輪廓分叉,也沒有解決冗余像素的問題。牟少敏等人[10]通過制作像素8鄰域的十進制模板,增加特定模板刪除條件，該算法解決了ZS 細化算法的像素冗余問題,改善了局部信息丟失問題,但該算法在X形狀的結構保持上效果并不好。韓建峰等人[11]通過完善ZS細化算法的判決條件來改進二像素寬度斜線信息腐蝕過度問題,但其細化結果仍存在局部信息丟失問題。包建軍等人提出的EPTA細化算法[12]在ZS細化算法基礎上新增一個迭代結束條件來保留只有連接數為2的待刪除的像素點集合,并新增一個階段利用兩個條件刪除冗余像素,但該算法依然存在斜線細化畸變以及冗余消除不完全的問題。針對單幅斜線圖像細化，存在其他輪廓點且所需要的迭代次數高于純粹的二像素斜線時,判決條件將會失效,造成斜線細化畸變。趙丹丹等人提出的IEPTA細化算法[13]在EPTA細化算法的基礎上新增兩個對稱的映像迭代過程,并同時增加了對連接數為2的刪除模板,在二階段掃描中增加兩個刪除冗余像素的條件,從而徹底去除冗余像素。但該算法存在2×2像素正方形結構的消失與邊緣輪廓分叉的問題。MZS細化算法[14]利用像素奇偶性進行細化,但像素的坐標索引值的奇偶性會對細化結果有直接影響。袁良友等人[15]提出一種引入平滑迭代的骨架提取細化算法IZS,在ZS細化算法的基礎上增加4×4保留模板與刪除模板,但參數平滑參數k設置會直接影響到細化質量。OPTA細化算法也是經典的并行細化算法之一,該算法每次進行單步迭代,使用8個消除模板和2個保留模板進行骨架細化。該算法的保留模板為偶數大小模板,刪除模板中凸角結構比凹角結構細化速度更快,操作不均勻,導致骨架中軸性差、像素冗余和骨架畸變。NFPT細化算法[16]將ZS細化算法與OPTA細化算法相結合,提高了細化速率,但該算法對圖像T型交叉點結構效果不佳。

由以上分析可見,現有對ZS細化算法的改進算法各有優缺點,受到IZS細化算法與NFPT細化算法的啟發,該文在ZS細化算法的基礎上提出一種基于模板的二階段改進算法。實驗表明，提出的改進算法在保留ZS細化算法的優點同時,解決了二像素細化的問題,減少了輪廓分叉,提高了算法的魯棒性。

1 相關工作

1.1 基本定義

設G為二值圖像,前景點為白色像素并且值為1,背景點為黑色像素并且值為0。P1為圖像G中任意一個值為1的目標像素點。

定義1 8鄰域與16環域：與目標像素點P1相鄰的8個鄰域所組成的像素點集合S={P2,P3,P4,P5,P6,P7,P8,P9}稱為P1的8鄰域。與像素點P1相鄰的16個鄰域所組成的像素點集合S'={A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16}稱為P1的16環域,如圖1所示。

定義2 交叉數A(P1)：沿著目標像素點P1的8鄰域順時針環繞一周像素由1變為0的次數,其中P10=P2。

(1)

(2)

定義3 連接數B(P1)：沿著目標像素點P1的8鄰域中像素點為1的總數。

(3)

定義4 邊界點：目標像素點P1為前景點,其8鄰域中至少存在一個背景點。

圖1 目標像素點的8鄰域與16環域

定義5 端點：目標像素點P1為前景點,其8鄰域中只存在一個前景點并且為骨架點。

1.2 ZS細化算法

ZS細化算法采用8鄰域方法,基于兩步迭代將二值圖像從左上邊緣、右下邊緣不斷逐層消去不屬于骨架的邊緣像素,直到生成骨架圖。ZS細化算法每次迭代可分為兩個子過程：子過程1掃描并標記滿足下面判定條件1、2、3、4的邊界點,掃描后統一刪除；子過程2掃描并標記滿足判定條件1、2、5、6的邊界點,掃描后統一刪除。

(1)A(P1)=1

(2)2≤B(P1)≤6

(3)P2×P4×P6=0

(4)P4×P6×P8=0

(5)P2×P4×P8=0

(6)P2×P6×P8=0

ZS細化算法的迭代次數N的奇偶性決定執行不同的迭代過程,奇數迭代執行子過程1,偶次迭代執行子過程2。重復迭代上述兩個子過程,直至沒有像素點刪除,此時剩下的點所構成的區域即為骨架,算法的細化過程結束。ZS細化算法中判定條件1要求目標像素點P1的交叉數為1,使其8鄰域內像素按黑白分別聚集,防止出現交錯的現象,使得目標像素點P1刪除后仍然保持骨架連通性。判定條件2要求目標像素點P1的連接數在2到6之間。端點的連接數為1,不能被標記刪除。若目標像素點P1連接數為7,為保證骨架的連通性,不能被標記刪除,避免骨架逐步被腐蝕。判定條件3、4分別控制標記刪除右下方與左上方非骨架的像素點,判定條件5、6分別控制標記刪除左下方與右上方非骨架的像素點。

2 改進算法

2.1 算法思想

ZS細化算法通過迭代的方式循環刪除圖像中的非骨架像素點提取骨架,具有迭代少、速度快,對直線、T型交叉點和拐角細化精確等特點。但ZS細化算法在進行像素點刪除判定時,僅使用目標像素點附近8鄰域的信息,存在骨架毛刺,骨架斜線區域易出現像素冗余,二像素斜線結構和2×2正方形結構信息丟失等問題。細化的過程中結構信息的丟失會導致后續可提取特征點的減少,而冗余信息則會影響特征點提取的結果,特別是微小結構的丟失嚴重影響在某些微型結構場景下的細化效果。因此，該文提出的改進算法在細化迭代過程對于非骨架的邊緣像素刪除的判定中,加入目標像素點附近16環域的信息,增加5×5的模板進行細化,從而提高算法細化質量。

提出的改進算法可分為兩個階段,第一階段生成保留部分二像素結構的骨架圖,第二階段除去冗余像素,生成單像素寬度骨架圖。在第一階段中,使用ZS細化算法的判定條件進行標記,并在迭代過程中對標記的待刪除像素點中,對符合一階段保留模板的像素點去除標記,如圖2所示。其中a1-a8模板用于保留八個方向的二像素斜線結構信息,a9模板用于避免2×2正方形結構被徹底細化。同時在每輪迭代掃描中,對不符合ZS細化算法細化條件的像素點中,增加對滿足交叉數為2的像素點使用一階段額外刪除模板進行標記,如圖3所示。在每輪迭代掃描結束后,對標記像素點進行刪除,直至沒有像素點刪除。第二階段使用圖4中刪除模板進行2次迭代掃描,第1輪二階段迭代掃描使用c1、c2刪除模板,第2輪則使用c3、c4刪除模板,對第一階段處理后存在的二像素斜線冗余像素進行標記刪除,生成單像素寬度的骨架圖。

圖2 一階段保留模板

圖2～圖4為改進算法所使用的模板,模板中0表示在目標像素點P1的鄰域或環域中像素點的值為0且為黑色背景點,1表示該像素點值為1且是白色前景點,x表示該像素點即可為1也可為0。模板中符號E1、E2、G1和G2被定義為特殊標記符號,相同特殊標記符號的像素點的值相等。標記為E1的像素點的值與E2像素點的值無關,標記為G1的像素點的值與G2的像素點的值之和大于等于1。

圖3 一階段額外刪除模板

圖4 二階段刪除模板

2.2 改進算法流程

改進算法主要分為7個步驟,流程如圖5所示。

步驟1 初始化：迭代次數N=0。

步驟2 若迭代次數為偶數,跳轉至步驟3,否則跳轉步驟4。

步驟3 掃描目標圖像,若像素點P1滿足條件1、2、3、4且不滿足一階段保留模板a1-a9,則標記該像素點。若P1滿足A(P1)=2同時B(P1)=4或B(P1)=5,并滿足一階段額外刪除模板b1至b8,則標記該像素點。掃描完成后跳轉至步驟5。

步驟4 掃描目標圖像,若像素點P1滿足條件1、2、5、6且不滿足一階段保留模板a1-a9,則標記該像素點。若像P1滿足A(P1)=2同時B(P1)=4或B(P1)=5,并滿足一階段額外刪除模板b1至b8,則標記該像素點。掃描完成后跳轉至步驟5。

步驟5 若存在有刪除標記的像素點集合,則刪除像素,迭代次數N=N+1,跳轉至步驟2。若刪除標記像素點集合為空,跳轉至步驟6。

步驟6 掃描目標圖像,若符合刪除模板c1、c2,則標記刪除像素點。本次掃描后刪除標記像素點,跳轉至步驟7。

步驟7 掃描目標圖像,若符合刪除模板c3、c4,則標記刪除像素點。本次掃描后刪除標記像素點,算法結束。

圖5 改進算法流程

3 實驗與分析

為了驗證提出的改進算法的有效性,實驗在Windows10操作系統中使用Visual Studio2019開發環境并使用OpenCV3.4.9計算機視覺庫,對1 000個150×150像素常用黑體漢字進行細化,并將提出的改進算法與ZS細化算法、NFPT細化算法、IZS細化算法進行比較。圖6為改進細化算法與現有細化算法對二像素寬度斜線結構、正方形結構細化后的圖像對比。因細微結構對平滑迭代的敏感度高,故IZS細化算法只在漢字細化過程中加入平滑迭代進行對比。圖7是分別對漢字“聯”、“賓”和“資”細化后的圖像對比。表1為改進算法與現有算法對漢字“聯”、“賓”和“資”細化后,在各項數據上的對比結果,表2為1 000個常用黑體漢字細化后的平均結果對比。

圖6 二像素斜線結構以及2×2正方形細化圖

圖7 漢字“聯”、“賓”和“資”細化圖

定義6 細化率TR[17]：圖像的細化程度,由下列公式計算：

(4)

其中，TM1表示細化圖像的總三角形計數,計算公式如下：

(5)

P(i,j)=1表示為二值圖中前景點,TC函數用于計算P(i,j)及其相鄰像素構成的白色三角形的數量,計算公式如下：

TC(p1)=p1×[(p8×p9)+(p9×p2)+

(p2×p3)+(p3×p4)]

(6)

TM2表示圖像可以計算的最大白色三角形數,計算公式如下：

TM2=4×[max(m,n)-1]2

(7)

其中，m,n代表圖像的矩陣P的尺寸，當TR=1時,圖像將完全細化。

定義7 細化速率TS：圖像平均每秒細化的像素點數,由下列公式計算：

(8)

DP=OP-SP

(9)

其中，DP為細化過程中刪除的前景點數量,OP為原圖中前景點的數量,SP為細化后圖像中前景點的數量,ET為圖像進行細化所需時間,單位為秒。

定義8 縮減率RR：圖像細化過程中前景點減少率,由下列公式計算：

(10)

圖6展示了提出的改進算法與現有算法在二像素斜線結構以及2×2正方形細化圖的細化結果。ZS細化算法細化后不能完全保留二像素斜線結構信息,細化后直接生成兩條短線,同時2×2正方形結構也在細化后消失。IZS細化算法、NFPT細化算法和改進算法都實現了對二像素斜線結構細化以及2×2正方形結構細化,但NFPT細化算法在二像素斜線下半部分斜線結構細化效果劣于IZS細化算法和提出的改進算法。

由圖7和表1可以看出,ZS細化算法細化后存在冗余像素的問題,細化率與縮減率都最低。在“聯”字右下角的筆畫中細化出現了分叉毛刺,在“賓”字左下角的筆畫也出現了輪廓分叉毛刺,在“資”字左上角的筆畫出現了過度細化導致直接生成小點,細化時間大幅增加,細化速率最慢,而且在右上方的橫鉤結構細化后出現了輪廓分叉毛刺。NFPT細化算法解決了ZS細化算法存在的冗余像素問題,細化時間最短,細化速率最快。“資”字沒有出現分叉毛刺問題,但“聯”字與“賓”字毛刺問題依舊存在,且對T型結構交叉點處理效果不佳,細化率低于IZS細化算法和提出的改進算法。IZS細化算法沒有出現二像素冗余的問題,在沒有進行平滑迭代時,沒有出現ZS細化算法存在過度細化的問題,但仍然存在分叉毛刺現象,縮減率和細化速率在現有改進的細化算法中最低。進行1次平滑迭代后,“聯”字沒有出現毛刺問題,細化率提高,但“賓”字和“資”字分叉毛刺問題仍然存在。進行5次平滑迭代后,都沒有出現毛刺問題,且細化率和縮減率最高,但細化時間明顯增加。該文提出的改進算法沒有出現冗余像素與分叉問題,細化時間快于IZS細化算法,對T型結構處理優于NFPT細化算法,在“聯”字和“資”上細化率最高,“賓”字上細化率僅次于5次平滑迭代后的IZS細化算法。

表1 漢字“聯”、“賓”和“資”細化結果比較

表2展示改進細化算法和現有細化算法對1 000個常用漢字的平均細化結果,NFPT細化算法速度最快,但細化率低于IZS細化算法與改進算法,存在對T型結構交叉點細化不準確的問題。IZS細化算法細化速率最慢,通過增加平滑迭代次數可以提高細化率和縮減率。但是該算法的平滑迭代次數k需要預先設置,設置過大會導致耗時明顯增大,k值設置過小則會細化不完全,平滑迭代次數的設置導致算法的實時性不穩定。該文提出的改進算法雖然增加了額外的判斷條件與模板,但是細化速度仍快于未增加平滑迭代的IZS細化算法,在速度上接近ZS細化算法,而且細化率和縮減率僅次于進行平滑迭代后的IZS細化算法。

表2 1 000個常用漢字細化算法平均結果比較

4 結束語

針對ZS細化算法的缺陷,提出一種改進細化算法,該算法在ZS細化算法基礎上增加5×5模板。在第一階段針對二像素斜線結構和2×2正方形結構信息丟失等問題增加保留模板,并對交叉數為2像素點增加額外刪除模板。在二階段掃描處理中,使用刪除模板對存在的二像素斜線冗余像素進行刪除。實驗結果表明，改進算法有效解決了ZS細化算法二像素畸變與冗余像素的問題,并且減少了細化過程中產生的輪廓分叉,完整地保留原圖拓撲信息。