引入平滑迭代的骨架提取改進(jìn)算法

袁良友，周 航，韓 丹，許國(guó)梁

北京交通大學(xué) 電子信息工程學(xué)院，北京100044

1 引言

作為計(jì)算機(jī)視覺領(lǐng)域提取目標(biāo)特征的處理步驟之一，細(xì)化已經(jīng)廣泛應(yīng)用于指紋識(shí)別、字符處理、運(yùn)動(dòng)人體分析、測(cè)繪信息提取[1-4]等各種應(yīng)用場(chǎng)景。細(xì)化是指在不影響原圖像拓?fù)溥B接關(guān)系的條件下，保持其目標(biāo)骨架或中軸線，將圖像的線條由多像素寬度減少至單位像素寬度，極大消除圖像冗余信息的過(guò)程，也稱骨架化。具有良好效果的細(xì)化算法須具有以下特點(diǎn)：迭代收斂、骨架可連通、拓?fù)浣Y(jié)構(gòu)不變、細(xì)節(jié)特征可保持、無(wú)冗余像素、骨架中心化、實(shí)時(shí)性好等。細(xì)化算法作為一個(gè)活躍的研究領(lǐng)域，目前已有一些經(jīng)典的成果。整體而言細(xì)化算法可分為迭代以及非迭代兩類，迭代算法分為串行[5]、并行以及串并行混合算法，而非迭代算法基于距離變換或其他原理，處理后的骨架通常缺乏整體連通性。在此背景下，速度快、條件簡(jiǎn)單的并行算法得到了更廣泛應(yīng)用，代表之一便是Zhang和Suen在文獻(xiàn)[6]中提出的ZS細(xì)化算法。

ZS算法對(duì)拐角、T型交叉點(diǎn)以及直線的結(jié)構(gòu)細(xì)化效果較好，能保持其整體連通性以及較快的細(xì)化速度。但是大量的實(shí)驗(yàn)表明，ZS 算法普遍存在三種處理不當(dāng)?shù)膯?wèn)題[7]：

問(wèn)題1 二像素寬度斜線細(xì)化出現(xiàn)結(jié)構(gòu)全丟失。

問(wèn)題2 2×2正方形結(jié)構(gòu)細(xì)化后拓?fù)浣Y(jié)構(gòu)全丟失。

問(wèn)題3 細(xì)化后大量存在二像素寬度的冗余像素。

細(xì)化過(guò)程中局部信息的丟失將導(dǎo)致可提取特征點(diǎn)的減少，冗余信息會(huì)混淆和誤導(dǎo)特征點(diǎn)提取的結(jié)果，微小結(jié)構(gòu)的丟失則嚴(yán)重影響某些微型結(jié)構(gòu)場(chǎng)景下的細(xì)化效果。如何同時(shí)處理結(jié)構(gòu)丟失、像素冗余的細(xì)化問(wèn)題顯得尤為重要。

因此，產(chǎn)生了各種ZS算法的改進(jìn)形式，Lu和Wang[8]提出LW 細(xì)化算法，去除了B(P0)=2 的刪除判定條件，使得二像素斜線結(jié)構(gòu)得到保留，但細(xì)化結(jié)果出現(xiàn)大量冗余分叉。牟少敏等人[9]通過(guò)制作像素周圍8鄰域的十進(jìn)制模板，增加了特定模板刪除條件，一定程度上解決了冗余像素問(wèn)題。包建軍等人[10]提出EPTA 的魯棒算法，增加了是否結(jié)束第一階段掃描的判斷條件并增加一個(gè)二階段掃描過(guò)程，有效改善了局部信息丟失和冗余像素等問(wèn)題，但其依然存在斜線細(xì)化畸變以及冗余消除不完全的問(wèn)題。趙丹丹等人[11]提出IEPTA 算法，在EPTA 算法的基礎(chǔ)上增加了兩個(gè)對(duì)稱的映像迭代過(guò)程，獲得了更加接近中心線的骨架圖像，但并沒有實(shí)現(xiàn)完全對(duì)稱的細(xì)化效果。文獻(xiàn)[12]提出了MZS算法，能夠完整保留2×2正方形結(jié)構(gòu)，但像素的坐標(biāo)索引值的奇偶性會(huì)對(duì)細(xì)化結(jié)果有直接影響。

好的細(xì)化算法應(yīng)能改善圖像線條紋路信息，而不僅僅是消極地進(jìn)行數(shù)據(jù)壓縮。對(duì)于線狀圖形信息豐富的圖像，細(xì)化之后除了骨架的大小、形狀與原圖像保持一致，一般也會(huì)存在原圖像的表面噪聲信息。文獻(xiàn)[13]指出，在足夠多的迭代次數(shù)下，不平滑的表面輪廓會(huì)使得細(xì)化結(jié)果存在第四種問(wèn)題：

問(wèn)題4 圖像出現(xiàn)較多受噪聲影響的輪廓分叉。

文獻(xiàn)[14]通過(guò)改進(jìn)刪除規(guī)則，提出了一種基于輪廓篩檢的骨架細(xì)化算法，并應(yīng)用于交通指揮動(dòng)作骨架提取過(guò)程中，但其刪除規(guī)則的制定依據(jù)于人體骨架而不具普遍性。文獻(xiàn)[15]提出了一種基于筆劃連續(xù)性檢測(cè)的并行細(xì)化算法，可以控制筆劃交叉或交叉處的大變形，免受表面噪聲干擾，但其適用范圍局限于字符圖像。對(duì)于不同類型的二值圖像，細(xì)化時(shí)若能夠在刪除冗余像素和保留特定結(jié)構(gòu)的前提下減少其表面噪聲信息，將大大提高后期特征提取的效果和精度。

為了解決細(xì)化過(guò)程出現(xiàn)的以上問(wèn)題，本文在細(xì)化過(guò)程中加入保留模板和消除模板以處理冗余與結(jié)構(gòu)丟失現(xiàn)象；同時(shí)在進(jìn)行全局的細(xì)化迭代前引入一定次數(shù)的輪廓平滑迭代過(guò)程，有效抑制了實(shí)際二值圖像的表面噪聲帶來(lái)的分支效應(yīng)。

引入通用的并行計(jì)算平臺(tái)和編程模型可以加快算法的運(yùn)算速度[16]。目前，各個(gè)并行細(xì)化算法的CUDA并行編程模型正在成為研究熱點(diǎn)，其算法的并行版本平均可比傳統(tǒng)的CPU順序版本快幾十倍以上。

2 細(xì)化算法基本原理

2.1 基本定義

規(guī)定二值圖像的前景點(diǎn)像素為1，背景點(diǎn)像素為0。對(duì)某一像素點(diǎn)P0，其8 鄰域與24 鄰域的像素點(diǎn)集合如圖1 所示，P0為掃描點(diǎn)像素，P1～P8為其8 鄰域像素，在周圍擴(kuò)展一層像素集合P9～P24得到其24 鄰域像素。在細(xì)化的迭代過(guò)程中，每次迭代的次序記為N，子迭代次序記為S。像素P0的交叉數(shù)A(P0)定義為沿其八鄰域順時(shí)針環(huán)繞一周像素由1變?yōu)?的次數(shù)，P0的連接數(shù)B(P0)定義為其八鄰域中像素為1的總數(shù)。

圖1 像素8鄰域與像素24鄰域

2.2 細(xì)化約束條件

對(duì)于ZS 細(xì)化算法，子迭代次數(shù)S的奇偶性決定了不同的判斷條件。若S為奇數(shù)，當(dāng)每次判斷像素點(diǎn)P0滿足下列4 個(gè)條件，標(biāo)記為待刪除點(diǎn)，并在該子迭代結(jié)束時(shí)統(tǒng)一刪除。

若S為偶數(shù)，公式（3）、（4）變?yōu)椋?/p>

當(dāng)某次迭代中不存在滿足刪除條件集合的像素，算法結(jié)束。

2.3 平滑像素點(diǎn)的判定條件

迭代次數(shù)較多的二值圖像通常存在不光滑的輪廓，由于目標(biāo)各處由表面到內(nèi)部的細(xì)化速度是均勻的，最終在各不平滑輪廓的突起處將會(huì)形成不同長(zhǎng)度的分支?？梢酝葡?，當(dāng)待細(xì)化圖像擁有平滑程度更高的輪廓，將會(huì)得到更少分支的細(xì)化結(jié)果。

滿足公式（1）的目標(biāo)輪廓像素點(diǎn)可分為平滑像素點(diǎn)與非平滑像素點(diǎn)。如圖2，像素點(diǎn)1～4 依次代表了斜方向與水平方向上的平滑像素點(diǎn)，它們滿足公式（2）和（7）。

圖2 光滑像素點(diǎn)1～4

2.4 保留與刪除模板

24鄰域可以劃分出4個(gè)不同方向上的4×4子域，如圖3 中的M1～M4 所示，它們適合用來(lái)區(qū)分不同方向上的特定結(jié)構(gòu)。

圖3 4×4子域

為處理細(xì)化過(guò)程中的結(jié)構(gòu)丟失與冗余像素問(wèn)題，分別設(shè)計(jì)了24 鄰域子域下的保留模板以及8 鄰域下的刪除模板[17]，如圖4、圖5。模板中的像素點(diǎn)Px可為1也可為0。

3 骨架提取改進(jìn)算法

3.1 改進(jìn)算法整體描述

引言中論述的四種問(wèn)題在不同的細(xì)化場(chǎng)景下其處理的優(yōu)先級(jí)是不同的。目標(biāo)像素總數(shù)與迭代次數(shù)較少時(shí)，問(wèn)題1～3所代表的拓?fù)浣Y(jié)構(gòu)丟失與像素冗余問(wèn)題應(yīng)當(dāng)被優(yōu)先考慮。而當(dāng)像素總數(shù)與整體迭代次數(shù)較多時(shí)，問(wèn)題4 中不光滑輪廓引起分支問(wèn)題的解決對(duì)于目標(biāo)特征提取更加關(guān)鍵。

因此，在進(jìn)行全局迭代前，本文引入一定次數(shù)的平滑迭代過(guò)程，用以解決不同場(chǎng)景下的細(xì)化問(wèn)題。在平滑迭代過(guò)程中對(duì)平滑像素點(diǎn)進(jìn)行保留，抑制了平滑輪廓出像素點(diǎn)集合的細(xì)化速度。同時(shí)，為了解決結(jié)構(gòu)和冗余問(wèn)題，在前期的迭代過(guò)程中引入保留模板，而在后續(xù)的二階段掃描過(guò)程中引入刪除模板。

圖4 保留模板

圖5 刪除模板

3.2 算法細(xì)節(jié)描述

如圖6所示，改進(jìn)算法將整個(gè)細(xì)化過(guò)程分成三種迭代流程：平滑迭代、全局迭代以及二階段掃描。針對(duì)問(wèn)題1 和2，在平滑迭代與全局迭代中加入保留模板的判定條件，保留所有既有刪除標(biāo)記又滿足保留模板的像素點(diǎn)，從而避免了一些拓?fù)浣Y(jié)構(gòu)的刪除。其中，圖4（a）～（h）用來(lái)保持二像素寬度斜線，圖4（i）用于保持2×2 正方形結(jié)構(gòu)。針對(duì)問(wèn)題3，在二階段掃描中加入刪除模板（圖5）的判定條件，挑選出那些不滿足刪除條件但滿足刪除模板的像素點(diǎn)進(jìn)行單獨(dú)刪除，可避免細(xì)化結(jié)構(gòu)出現(xiàn)冗余點(diǎn)。不同于全局迭代中添加刪除標(biāo)記的處理過(guò)程，直接刪除滿足刪除模板判定條件的像素點(diǎn)，能有效避免拓?fù)浣Y(jié)構(gòu)的斷裂情況出現(xiàn)。對(duì)于問(wèn)題4，引入的K次平滑迭代可以很好地抑制輪廓噪聲。在每次迭代過(guò)程中，滿足公式（1）、（2）的像素點(diǎn)集合代表了所有的目標(biāo)邊緣像素，滿足公式（7）的像素點(diǎn)集合代表了輪廓上的所有平滑像素。僅標(biāo)記所有的不平滑像素點(diǎn)，意味著直接對(duì)輪廓噪聲進(jìn)行過(guò)濾，使得目標(biāo)圖像在后續(xù)的全局迭代過(guò)程中能得到更整體化的細(xì)化結(jié)構(gòu)。

圖6 改進(jìn)算法整體框圖

此外，過(guò)多的或者不合適的平滑迭代次數(shù)會(huì)導(dǎo)致提取的骨架出現(xiàn)結(jié)構(gòu)變形。K值的選取應(yīng)由實(shí)際圖像的輪廓平滑程度以及前景像素點(diǎn)總數(shù)決定。輪廓平滑程度較高，對(duì)平滑迭代的要求降低；前景像素點(diǎn)總數(shù)較少，對(duì)判定條件的敏感度提高，兩種情況下K值均應(yīng)該取較小。

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

修改后的細(xì)化算法方案流程如下：

步驟1 根據(jù)待細(xì)化圖像的像素總數(shù)和輪廓平滑情況選定平滑迭代次數(shù)K，初始化N=0,S=0。

步驟2N＜K時(shí)，進(jìn)行平滑迭代。首先對(duì)同時(shí)滿足公式（1）、（2）的像素點(diǎn)進(jìn)行刪除點(diǎn)標(biāo)記，再在這些像素集合中除去滿足公式（7）以及滿足保留模板圖4（a）～（i）之一的像素點(diǎn)。每次迭代結(jié)束時(shí)刪除掉有刪除標(biāo)記的像素，N=N+1。

步驟3N≥K時(shí)，進(jìn)行全局迭代。奇數(shù)次子迭代對(duì)同時(shí)滿足公式（1）～（4）的像素點(diǎn)進(jìn)行刪除點(diǎn)標(biāo)記，偶數(shù)次子迭代對(duì)同時(shí)滿足公式（1）、（2）、（5）、（6）的像素點(diǎn)進(jìn)行刪除點(diǎn)標(biāo)記，然后在這些像素集合中除去滿足保留模板圖4（a）～（i）之一的像素點(diǎn)，每次迭代結(jié)束時(shí)刪除掉所有刪除標(biāo)記的像素，N=N+1,S=S+1。當(dāng)某次迭代后無(wú)刪除標(biāo)記像素時(shí)，進(jìn)入步驟4。

步驟4 進(jìn)行一次全局迭代的二階段掃描。掃描過(guò)程中直接刪除滿足刪除模板（圖5 后兩個(gè)）的像素點(diǎn)。當(dāng)?shù)鬅o(wú)刪除標(biāo)記像素時(shí)，細(xì)化結(jié)束。

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

圖8 二像素寬度斜線細(xì)化效果對(duì)比

4 改進(jìn)算法效果及性能

為了檢驗(yàn)改進(jìn)算法對(duì)問(wèn)題1～4的改善效果，本文在Visual Studio 2019 環(huán)境下，分別對(duì)二像素寬度斜線結(jié)構(gòu)、正方形結(jié)構(gòu)、人體結(jié)構(gòu)以及字母結(jié)構(gòu)進(jìn)行細(xì)化，并將改進(jìn)算法、經(jīng)典ZS算法與較新的IEPTA算法、MZS算法細(xì)化結(jié)果進(jìn)行比較?？紤]到細(xì)微結(jié)構(gòu)對(duì)平滑迭代的敏感度高，僅在字母結(jié)構(gòu)細(xì)化過(guò)程中加入平滑迭代。

如圖8 所示，相比ZS 算法無(wú)法有效保持二像素寬度結(jié)構(gòu)，IEPTA 算法與MZS 算法均解決了二像素斜線細(xì)化畸變的問(wèn)題，但前者細(xì)化后的斜線長(zhǎng)度有所減少，后者由于判斷條件的不對(duì)稱其結(jié)果出現(xiàn)了上下兩部分結(jié)構(gòu)的中心偏移。這兩種情況在改進(jìn)算法中均有所改善。

如圖9所示，ZS算法和IEPTA算法無(wú)法保留左邊的2×2 正方形拓?fù)浣Y(jié)構(gòu)。而MZS 和改進(jìn)算法均能克服該缺點(diǎn)，同時(shí)也能完整保留圖右邊的兩正方形交叉結(jié)構(gòu)。

如圖10 所示，ZS 算法處理后人體的右腿部出現(xiàn)較多的冗余像素，而IEPTA、MZS 以及改進(jìn)算法均實(shí)現(xiàn)了對(duì)冗余像素的去除。其中，IEPTA 算法由于從4 個(gè)方向上進(jìn)行迭代且加入刪除冗余信息的消除模板，處理后的人體骨架較為光滑，但其手部區(qū)域也相應(yīng)地出現(xiàn)了結(jié)構(gòu)丟失。MZS 算法保留的骨架具有較好的連通性，但沒有充分刪除諸如右腳處的分叉像素點(diǎn)，易受表面噪聲的影響。改進(jìn)算法保持了具有良好連通性的ZS算法細(xì)化后的主干結(jié)構(gòu)，同時(shí)對(duì)噪聲點(diǎn)像素也能合理的去除。

圖9 正方形細(xì)化效果對(duì)比

圖10 人體結(jié)構(gòu)細(xì)化效果對(duì)比

圖11 字母結(jié)構(gòu)細(xì)化效果對(duì)比

圖12 仿真實(shí)驗(yàn)細(xì)化圖片示例對(duì)比

如圖11 所示，對(duì)字母圖片進(jìn)行細(xì)化處理后，ZS 算法、IEPTA 算法、MZS 算法的效果圖均出現(xiàn)端點(diǎn)和邊緣處的較大分叉。受到不平滑輪廓的干擾，未加入平滑迭代的改進(jìn)算法也出現(xiàn)了邊緣分叉，通過(guò)取一定大小的K值，有效去除了上下兩處分叉，同時(shí)整體的骨架更加光滑。

以上4組圖片的實(shí)驗(yàn)結(jié)果分別展示了改進(jìn)算法對(duì)4類問(wèn)題的展示效果。為了對(duì)各算法的細(xì)化程度進(jìn)行精確的評(píng)估，對(duì)MPEG7 圖像數(shù)據(jù)集進(jìn)行細(xì)化仿真實(shí)驗(yàn)，圖12展示了仿真實(shí)驗(yàn)的一個(gè)示例。

用于細(xì)化的目標(biāo)圖像應(yīng)該具有整體的線條化結(jié)構(gòu)，且所細(xì)化目標(biāo)應(yīng)具有可提取的特征及一定的現(xiàn)實(shí)意義。細(xì)化性能往往受到圖像大小和圖像內(nèi)容的影響。因此從全部1 402張二值圖像中選取適合細(xì)化的527張圖片作為仿真對(duì)象。同時(shí)，在細(xì)化仿真前，進(jìn)行必要的濾波和形態(tài)學(xué)預(yù)處理[18]，首先對(duì)數(shù)據(jù)集中的原始圖像進(jìn)行背景像素點(diǎn)填充，使其符合模板匹配的要求。然后針對(duì)圖像中大量存在的邊緣噪聲和孔洞結(jié)構(gòu)進(jìn)行適當(dāng)?shù)男螒B(tài)學(xué)開操作與閉操作[19]。定義細(xì)化率為算法細(xì)化過(guò)程中刪除掉的前景像素點(diǎn)數(shù)占原有前景像素點(diǎn)數(shù)的比例，各算法細(xì)化率結(jié)果和冗余像素情況在表1～表3中給出。

表1 各算法細(xì)化率對(duì)比

表2 不同K 值下的改進(jìn)算法細(xì)化率對(duì)比

表3 各算法冗余像素情況對(duì)比

表1 展示了ZS、IEPTA、MZS 以及改進(jìn)算法(K=0)的細(xì)化率仿真情況，其中改進(jìn)算法的細(xì)化程度最高，其細(xì)化率比前三種算法分別高出0.23%、0.05%、0.11%，說(shuō)明改進(jìn)算法能夠高效濾除圖像中的冗余信息。表2 比較了不同平滑迭代次數(shù)下的改進(jìn)算法的細(xì)化率，驗(yàn)證了增大平滑迭代次數(shù)將會(huì)進(jìn)一步提高其細(xì)化程度，同時(shí)能提高對(duì)輪廓噪聲的改善效果。表3 表明改進(jìn)算法的細(xì)化結(jié)果無(wú)冗余像素，很好處理了像素冗余與結(jié)構(gòu)丟失的矛盾問(wèn)題。

5 結(jié)論

本文針對(duì)二像素寬度斜線結(jié)構(gòu)全刪除、正方形結(jié)構(gòu)丟失、大量斜線冗余像素存在以及不平滑輪廓帶來(lái)大量分叉四類問(wèn)題，在原始ZS 細(xì)化算法基礎(chǔ)上引入了平滑迭代流程以及后續(xù)的掃描過(guò)程，并在其中加入保留模板和刪除模板條件的判定。通過(guò)針對(duì)性地保留和刪除一些特定的拓?fù)浣Y(jié)構(gòu)，有效保留了二像素寬度斜線結(jié)構(gòu)和正方形結(jié)構(gòu)，并完全刪除了斜線上的冗余像素，引入的平滑迭代能有效減少骨架輪廓的噪聲分叉。仿真實(shí)驗(yàn)數(shù)據(jù)表明，不引入平滑迭代階段的改進(jìn)算法的細(xì)化率相比ZS、IEPTA、MZS算法提高了0.05%～0.25%不等；而平滑迭代次數(shù)的增加，能進(jìn)一步提高細(xì)化程度，減少大量的輪廓分叉，完整保留了目標(biāo)圖像的骨架信息和拓?fù)湫浴?/p>

本文解決了現(xiàn)有細(xì)化算法在細(xì)化過(guò)程中的局部結(jié)構(gòu)丟失、冗余像素以及輪廓分叉的問(wèn)題，但沒有對(duì)具體細(xì)化背景下合理的平滑迭代次數(shù)的選取做出精準(zhǔn)估算，同時(shí)受到匹配模板及平滑迭代次數(shù)的影響其算法的實(shí)時(shí)性并不穩(wěn)定。后期將就確定自適應(yīng)的K值以及提高算法實(shí)時(shí)穩(wěn)定性做進(jìn)一步研究，完善其改進(jìn)算法性能。