一種基于模板的二階段ZS細(xì)化算法

陳 品，王 濤，張德港

(華南師范大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510631)

0 引 言

細(xì)化算法是指在保持原二值圖像的拓?fù)浣Y(jié)構(gòu)和連通性的前提下，生成單像素寬度的骨架圖[1]。骨架是一種重要的圖像幾何特征，利用骨架來(lái)表示原始圖像，可以在保持圖像重要拓?fù)湫畔⒌那疤嵯聵O大地消除圖像中的冗余信息,提取目標(biāo)特征,簡(jiǎn)化后續(xù)圖像處理數(shù)據(jù)量,提高運(yùn)行速度。因此，細(xì)化是很多圖像預(yù)處理中的重要步驟,目前細(xì)化算法已經(jīng)廣泛應(yīng)用于指紋識(shí)別[2]、漢字處理[3]、裂縫檢測(cè)[4]、儀表檢測(cè)[5]、物料分選[6]等場(chǎng)景。

優(yōu)秀的細(xì)化算法應(yīng)在維持原圖拓?fù)浣Y(jié)構(gòu)的前提下,既保持骨架的連通性，又不會(huì)過(guò)度腐蝕,并具有一定的抗噪性能。理想的細(xì)化紋線骨架應(yīng)在中間位置,且保持紋線的連接性、拓?fù)浣Y(jié)構(gòu)和細(xì)節(jié)特征。因此，細(xì)化算法應(yīng)滿足以下幾點(diǎn)要求[7]：

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

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

(3)拓?fù)湫裕翰灰鸺y線的逐步吞食,保持原圖像的基本結(jié)構(gòu)特性。

(4)保持性：保護(hù)原圖像的細(xì)節(jié)特征。

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

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

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

由以上7點(diǎn)要求中可以發(fā)現(xiàn),前6條要求主要集中在對(duì)細(xì)化質(zhì)量的評(píng)價(jià),最后一條是對(duì)細(xì)化速度的要求。因此，評(píng)價(jià)一個(gè)細(xì)化算法的優(yōu)劣,主要是從細(xì)化質(zhì)量和細(xì)化速度兩個(gè)方面進(jìn)行。

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

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

由以上分析可見(jiàn),現(xiàn)有對(duì)ZS細(xì)化算法的改進(jìn)算法各有優(yōu)缺點(diǎn),受到IZS細(xì)化算法與NFPT細(xì)化算法的啟發(fā),該文在ZS細(xì)化算法的基礎(chǔ)上提出一種基于模板的二階段改進(jìn)算法。實(shí)驗(yàn)表明，提出的改進(jìn)算法在保留ZS細(xì)化算法的優(yōu)點(diǎn)同時(shí),解決了二像素細(xì)化的問(wèn)題,減少了輪廓分叉,提高了算法的魯棒性。

1 相關(guān)工作

1.1 基本定義

設(shè)G為二值圖像,前景點(diǎn)為白色像素并且值為1,背景點(diǎn)為黑色像素并且值為0。P1為圖像G中任意一個(gè)值為1的目標(biāo)像素點(diǎn)。

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

定義2 交叉數(shù)A(P1)：沿著目標(biāo)像素點(diǎn)P1的8鄰域順時(shí)針環(huán)繞一周像素由1變?yōu)?的次數(shù),其中P10=P2。

(1)

(2)

定義3 連接數(shù)B(P1)：沿著目標(biāo)像素點(diǎn)P1的8鄰域中像素點(diǎn)為1的總數(shù)。

(3)

定義4 邊界點(diǎn)：目標(biāo)像素點(diǎn)P1為前景點(diǎn),其8鄰域中至少存在一個(gè)背景點(diǎn)。

圖1 目標(biāo)像素點(diǎn)的8鄰域與16環(huán)域

定義5 端點(diǎn)：目標(biāo)像素點(diǎn)P1為前景點(diǎn),其8鄰域中只存在一個(gè)前景點(diǎn)并且為骨架點(diǎn)。

1.2 ZS細(xì)化算法

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

(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細(xì)化算法的迭代次數(shù)N的奇偶性決定執(zhí)行不同的迭代過(guò)程,奇數(shù)迭代執(zhí)行子過(guò)程1,偶次迭代執(zhí)行子過(guò)程2。重復(fù)迭代上述兩個(gè)子過(guò)程,直至沒(méi)有像素點(diǎn)刪除,此時(shí)剩下的點(diǎn)所構(gòu)成的區(qū)域即為骨架,算法的細(xì)化過(guò)程結(jié)束。ZS細(xì)化算法中判定條件1要求目標(biāo)像素點(diǎn)P1的交叉數(shù)為1,使其8鄰域內(nèi)像素按黑白分別聚集,防止出現(xiàn)交錯(cuò)的現(xiàn)象,使得目標(biāo)像素點(diǎn)P1刪除后仍然保持骨架連通性。判定條件2要求目標(biāo)像素點(diǎn)P1的連接數(shù)在2到6之間。端點(diǎn)的連接數(shù)為1,不能被標(biāo)記刪除。若目標(biāo)像素點(diǎn)P1連接數(shù)為7,為保證骨架的連通性,不能被標(biāo)記刪除,避免骨架逐步被腐蝕。判定條件3、4分別控制標(biāo)記刪除右下方與左上方非骨架的像素點(diǎn),判定條件5、6分別控制標(biāo)記刪除左下方與右上方非骨架的像素點(diǎn)。

2 改進(jìn)算法

2.1 算法思想

ZS細(xì)化算法通過(guò)迭代的方式循環(huán)刪除圖像中的非骨架像素點(diǎn)提取骨架,具有迭代少、速度快,對(duì)直線、T型交叉點(diǎn)和拐角細(xì)化精確等特點(diǎn)。但ZS細(xì)化算法在進(jìn)行像素點(diǎn)刪除判定時(shí),僅使用目標(biāo)像素點(diǎn)附近8鄰域的信息,存在骨架毛刺,骨架斜線區(qū)域易出現(xiàn)像素冗余,二像素斜線結(jié)構(gòu)和2×2正方形結(jié)構(gòu)信息丟失等問(wèn)題。細(xì)化的過(guò)程中結(jié)構(gòu)信息的丟失會(huì)導(dǎo)致后續(xù)可提取特征點(diǎn)的減少,而冗余信息則會(huì)影響特征點(diǎn)提取的結(jié)果,特別是微小結(jié)構(gòu)的丟失嚴(yán)重影響在某些微型結(jié)構(gòu)場(chǎng)景下的細(xì)化效果。因此，該文提出的改進(jìn)算法在細(xì)化迭代過(guò)程對(duì)于非骨架的邊緣像素刪除的判定中,加入目標(biāo)像素點(diǎn)附近16環(huán)域的信息,增加5×5的模板進(jìn)行細(xì)化,從而提高算法細(xì)化質(zhì)量。

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

圖2 一階段保留模板

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

圖3 一階段額外刪除模板

圖4 二階段刪除模板

2.2 改進(jìn)算法流程

改進(jìn)算法主要分為7個(gè)步驟,流程如圖5所示。

步驟1 初始化：迭代次數(shù)N=0。

步驟2 若迭代次數(shù)為偶數(shù),跳轉(zhuǎn)至步驟3,否則跳轉(zhuǎn)步驟4。

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

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

步驟5 若存在有刪除標(biāo)記的像素點(diǎn)集合,則刪除像素,迭代次數(shù)N=N+1,跳轉(zhuǎn)至步驟2。若刪除標(biāo)記像素點(diǎn)集合為空,跳轉(zhuǎn)至步驟6。

步驟6 掃描目標(biāo)圖像,若符合刪除模板c1、c2,則標(biāo)記刪除像素點(diǎn)。本次掃描后刪除標(biāo)記像素點(diǎn),跳轉(zhuǎn)至步驟7。

步驟7 掃描目標(biāo)圖像,若符合刪除模板c3、c4,則標(biāo)記刪除像素點(diǎn)。本次掃描后刪除標(biāo)記像素點(diǎn),算法結(jié)束。

圖5 改進(jìn)算法流程

3 實(shí)驗(yàn)與分析

為了驗(yàn)證提出的改進(jìn)算法的有效性,實(shí)驗(yàn)在Windows10操作系統(tǒng)中使用Visual Studio2019開(kāi)發(fā)環(huán)境并使用OpenCV3.4.9計(jì)算機(jī)視覺(jué)庫(kù),對(duì)1 000個(gè)150×150像素常用黑體漢字進(jìn)行細(xì)化,并將提出的改進(jìn)算法與ZS細(xì)化算法、NFPT細(xì)化算法、IZS細(xì)化算法進(jìn)行比較。圖6為改進(jìn)細(xì)化算法與現(xiàn)有細(xì)化算法對(duì)二像素寬度斜線結(jié)構(gòu)、正方形結(jié)構(gòu)細(xì)化后的圖像對(duì)比。因細(xì)微結(jié)構(gòu)對(duì)平滑迭代的敏感度高,故IZS細(xì)化算法只在漢字細(xì)化過(guò)程中加入平滑迭代進(jìn)行對(duì)比。圖7是分別對(duì)漢字“聯(lián)”、“賓”和“資”細(xì)化后的圖像對(duì)比。表1為改進(jìn)算法與現(xiàn)有算法對(duì)漢字“聯(lián)”、“賓”和“資”細(xì)化后,在各項(xiàng)數(shù)據(jù)上的對(duì)比結(jié)果,表2為1 000個(gè)常用黑體漢字細(xì)化后的平均結(jié)果對(duì)比。

圖6 二像素斜線結(jié)構(gòu)以及2×2正方形細(xì)化圖

圖7 漢字“聯(lián)”、“賓”和“資”細(xì)化圖

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

(4)

其中，TM1表示細(xì)化圖像的總?cè)切斡?jì)數(shù),計(jì)算公式如下：

(5)

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

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

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

(6)

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

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

(7)

其中，m,n代表圖像的矩陣P的尺寸，當(dāng)TR=1時(shí),圖像將完全細(xì)化。

定義7 細(xì)化速率TS：圖像平均每秒細(xì)化的像素點(diǎn)數(shù),由下列公式計(jì)算：

(8)

DP=OP-SP

(9)

其中，DP為細(xì)化過(guò)程中刪除的前景點(diǎn)數(shù)量,OP為原圖中前景點(diǎn)的數(shù)量,SP為細(xì)化后圖像中前景點(diǎn)的數(shù)量,ET為圖像進(jìn)行細(xì)化所需時(shí)間,單位為秒。

定義8 縮減率RR：圖像細(xì)化過(guò)程中前景點(diǎn)減少率,由下列公式計(jì)算：

(10)

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

由圖7和表1可以看出,ZS細(xì)化算法細(xì)化后存在冗余像素的問(wèn)題,細(xì)化率與縮減率都最低。在“聯(lián)”字右下角的筆畫(huà)中細(xì)化出現(xiàn)了分叉毛刺,在“賓”字左下角的筆畫(huà)也出現(xiàn)了輪廓分叉毛刺,在“資”字左上角的筆畫(huà)出現(xiàn)了過(guò)度細(xì)化導(dǎo)致直接生成小點(diǎn),細(xì)化時(shí)間大幅增加,細(xì)化速率最慢,而且在右上方的橫鉤結(jié)構(gòu)細(xì)化后出現(xiàn)了輪廓分叉毛刺。NFPT細(xì)化算法解決了ZS細(xì)化算法存在的冗余像素問(wèn)題,細(xì)化時(shí)間最短,細(xì)化速率最快?！百Y”字沒(méi)有出現(xiàn)分叉毛刺問(wèn)題,但“聯(lián)”字與“賓”字毛刺問(wèn)題依舊存在,且對(duì)T型結(jié)構(gòu)交叉點(diǎn)處理效果不佳,細(xì)化率低于IZS細(xì)化算法和提出的改進(jìn)算法。IZS細(xì)化算法沒(méi)有出現(xiàn)二像素冗余的問(wèn)題,在沒(méi)有進(jìn)行平滑迭代時(shí),沒(méi)有出現(xiàn)ZS細(xì)化算法存在過(guò)度細(xì)化的問(wèn)題,但仍然存在分叉毛刺現(xiàn)象,縮減率和細(xì)化速率在現(xiàn)有改進(jìn)的細(xì)化算法中最低。進(jìn)行1次平滑迭代后,“聯(lián)”字沒(méi)有出現(xiàn)毛刺問(wèn)題,細(xì)化率提高,但“賓”字和“資”字分叉毛刺問(wèn)題仍然存在。進(jìn)行5次平滑迭代后,都沒(méi)有出現(xiàn)毛刺問(wèn)題,且細(xì)化率和縮減率最高,但細(xì)化時(shí)間明顯增加。該文提出的改進(jìn)算法沒(méi)有出現(xiàn)冗余像素與分叉問(wèn)題,細(xì)化時(shí)間快于IZS細(xì)化算法,對(duì)T型結(jié)構(gòu)處理優(yōu)于NFPT細(xì)化算法,在“聯(lián)”字和“資”上細(xì)化率最高,“賓”字上細(xì)化率僅次于5次平滑迭代后的IZS細(xì)化算法。

表1 漢字“聯(lián)”、“賓”和“資”細(xì)化結(jié)果比較

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

表2 1 000個(gè)常用漢字細(xì)化算法平均結(jié)果比較

4 結(jié)束語(yǔ)

針對(duì)ZS細(xì)化算法的缺陷,提出一種改進(jìn)細(xì)化算法,該算法在ZS細(xì)化算法基礎(chǔ)上增加5×5模板。在第一階段針對(duì)二像素斜線結(jié)構(gòu)和2×2正方形結(jié)構(gòu)信息丟失等問(wèn)題增加保留模板,并對(duì)交叉數(shù)為2像素點(diǎn)增加額外刪除模板。在二階段掃描處理中,使用刪除模板對(duì)存在的二像素斜線冗余像素進(jìn)行刪除。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法有效解決了ZS細(xì)化算法二像素畸變與冗余像素的問(wèn)題,并且減少了細(xì)化過(guò)程中產(chǎn)生的輪廓分叉,完整地保留原圖拓?fù)湫畔ⅰ?/p>