一種改進的圖像骨架提取算法

葉福玲

（福州大學(xué)a.數(shù)學(xué)與計算機科學(xué)學(xué)院；b.網(wǎng)絡(luò)信息安全與計算機技術(shù)國家級實驗教學(xué)示范中心，福州 350116)

0 引言

隨著圖像識別技術(shù)的進步和計算機性能的發(fā)展，機器視覺領(lǐng)域重要的研究方向之一就是基于骨架的識別技術(shù)。骨架作為一種能夠使圖像降維的有力手段，能夠保持與原圖像相同的拓?fù)浣Y(jié)構(gòu)，存于對稱軸上，減少冗余干擾信息。對于圖像本身來說，它的整體框架和邊界信息能夠被保存下來，為識別保留了最關(guān)鍵的部分。

H.Blum最早提出中軸算法[1-2]，即對于區(qū)域內(nèi)的每一個點，在邊界中搜索到的最近的點多于一個時，則該點為圖像的骨架單元。但該方法比較費時，且對噪聲比較敏感，不能保證骨架線的連通。Dey等[3]通過構(gòu)造模型的 Voronoi圖得到了近似中軸的骨架，但該方法僅適用于比較簡單的骨架提取，對復(fù)雜的模型并不適用，且對邊界噪聲也很敏感。曹鐵勇[4]提出了一種基于勢能平衡方式的二值圖像骨架抽取算法。該方法將邊界點作為零勢能的等勢點，計算出處于勢能平衡點上的基本骨架點，由此構(gòu)建出的骨架，抗噪能力較強，但參與計算的邊界點的半徑較難確定。劉俊濤等[5]提出的梯度最短路徑的算法，首先計算物體距離變換的梯度，用搜索梯度最短路徑的方法來連接關(guān)鍵點，得到物體的線形骨架。該方法得到的線形骨架能很好地反映物體拓?fù)浜托螤钐卣?，并不易受邊界噪聲干擾。

本文引入Zhang-Suen[6]提出的以四個判別條件來判斷當(dāng)前點是否為可刪除點的方法。通過分析并發(fā)現(xiàn)了該算法的不足之處，提出了一種提取圖像骨架的改進算法。首先，根據(jù)提取的骨架特點設(shè)計細(xì)化模板，將骨架進行細(xì)化并且保持骨架的連通性和滿足單像素，便于后續(xù)處理；其次，利用8鄰域像素找出骨架的分支點，骨架減去分支點形成多個不連通區(qū)域，根據(jù)骨架特點選擇不同的閾值，去除小于該閾值的連通分支，從而去除骨架毛刺，該步驟高效地除去了多余的噪音和毛刺，優(yōu)化了骨架的整體視覺效果。

2 改進的圖像骨架提取算法

Zhang算法[6]能夠充分考慮到圖像骨架的連通性，并且對于有弧度的曲線、拐點以及交叉點，都能夠比較精確的提取出來，使得骨架與原圖像保持相對一致的結(jié)構(gòu)，效果較好。但是由于不同圖像的特點以及該算法對邊界敏感，細(xì)化之后得到的骨架會有多余的像素，不符合單像素骨架，且有部分毛刺沒有能夠識別出來。因此，本文在這個方法的基礎(chǔ)上，對提取出來的骨架進行進一步完善，刪除多余像素以及識別并消除毛刺。本文針對不足之處主要從細(xì)化單像素和去除毛刺兩方面入手，使得提取出來的骨架能夠更好符合單像素和光滑性，更加符合視覺感受。

2.1 骨架細(xì)化為單像素

將使用Zhang算法細(xì)化后的骨架圖像放大，我們可以發(fā)現(xiàn)提取出來的骨架并沒有滿足單像素的原則。通過仔細(xì)分析Zhang的算法思想和原理，我們可以得知：非單像素是由于冗余點沒有滿足S(P)=1而沒有被刪除,使得骨架不滿足單像素。本文在Zhang細(xì)化算法得出的骨架的基礎(chǔ)上，設(shè)計了用于細(xì)化的模板來判斷該點是否為冗余點，從而決定像素點的保留或者刪除，使得得到的骨架線條能夠符合單像素[7-9]。

單像素算法是基于如圖1所示模板。假設(shè)當(dāng)前的目標(biāo)色為像素點P，它的8領(lǐng)域為Pi=(1≤i≤8)。若P的8領(lǐng)域滿足圖1（b）的模板，即以P為目標(biāo)點，若它的鄰域P3、P5為目標(biāo)點，則將該目標(biāo)像素P刪去（即設(shè)為背景點），細(xì)化模板中的*號表示的是該位置可以為目標(biāo)點或者背景點。同時該細(xì)化模板還包括逆時針旋轉(zhuǎn)90°，180°，270°的情況。

圖1 細(xì)化算法的模板說明

單像素細(xì)化算法實現(xiàn)具體步驟：1.掃描整幅已用Zhang細(xì)化算法得到的細(xì)化效果圖；2.若遇到當(dāng)前點為目標(biāo)點，檢索8鄰域是否符合細(xì)化模板；若符合細(xì)化模板，則將該目標(biāo)像素點置為背景點，否則不做改動；3.重復(fù)步驟2直到掃描完整幅圖像，輸出圖像。

下面是采用該算法細(xì)化成單像素的效果與Zhang快速并行細(xì)化算法得到的細(xì)化的骨架進行對比，如圖2所示，前面為改進前的，后面為改進后的效果。

圖2 單像素細(xì)化前后效果對比

2.2 去除多余的骨架毛刺

仔細(xì)觀察毛刺會發(fā)現(xiàn)，毛刺的長度一般難以歸納，但是相對骨架中心來說，毛刺的長度顯得短許多[10-12]。利用這個特性，統(tǒng)計目標(biāo)像素8鄰域中值為1的像素點，然后確定相對目標(biāo)像素點的類型，形成的多個不連通區(qū)域，利用圖像特點來定義毛刺的特征，將像素點少的區(qū)域刪除來消除毛刺，對骨架進行改進和完善。改進的去除毛刺的具體實現(xiàn)步驟如下：

1.在2.1所得到的細(xì)化為單像素的骨架之后，設(shè)改進后的骨架圖像為f(x,y)，對于目標(biāo)像素點i即f(xi,yi)=1，計算點i的8鄰域模板中的目標(biāo)像素和，計入counti中。對每一個像素進行該操作直到所有的像素計算完畢。

2.分析counti的值，若counti＞3，說明該點至少有3個方向有目標(biāo)，則該點是分支點，記錄在Pi中；

3.在改進后的骨架圖像f(x,y)，減掉分支點的像素，這樣一來原本連通的區(qū)域會變成多個不連通的小區(qū)域。對區(qū)域進行標(biāo)記，從而得到標(biāo)記后的不連通圖g(x,y)。

4.對于不連通的標(biāo)記圖g(x,y)，從頂點出發(fā)計算不連通區(qū)域的長度，由于在單像素圖像上面進行計算，計算長度也就是計算面積即連通區(qū)域的像素和，記為Li。

5.設(shè)置閾值的大小T，若Li≤T，則刪去該小區(qū)域；否則，不作處理。

6.將剛才所刪除的分支點恢復(fù)，使圖像變?yōu)檫B通的區(qū)域，這樣就得到了去除了毛刺的骨架效果圖，并且重復(fù)步驟5的操作，得出精確的骨架圖。

3 實驗結(jié)果與分析

在實驗中，原始圖像首先采用的是Zhang細(xì)化算法來提取得到的骨架,如圖3所示。

圖3 算法改進效果圖

由以上4幅圖像可以看出，圖3中用經(jīng)典的Zhang細(xì)化算法來提取的骨架數(shù)字和字母上面會有長度不等的毛刺，影響整體骨架的視覺感官。根據(jù)上面的實驗結(jié)果可以明顯看出：利用骨架單像素后再去除毛刺，圖3（d）上面的毛刺相比圖3（b）來說減少了很多，使骨架更加接近真實，骨架效果更好。本文在處理毛刺的過程中根據(jù)圖像的特點，通過反復(fù)多次實驗，得到不同的合理閾值，能夠靈活地應(yīng)用在各毛刺類型不同的圖像上面，顯示出重要的實用性。

圖4 火烈鳥提取

圖5 航拍河流提取

圖6 腦血管的骨架線提取

圖7 文字骨架提取

為了驗證改進算法的有效性，下面將算法應(yīng)用在其他方面的圖像，實驗效果如圖4～7所示。

根據(jù)以上4個實驗的效果對比可以看出，改進算法比Zhang細(xì)化算法的效果更好，通過對閾值的設(shè)定來定義毛刺，能夠有效地去除毛刺且保持骨架的連通性以及主干骨架的存在。對于同一圖像，閾值設(shè)置的大小不同，骨架的最終提取效果也會有差異，因此需要嘗試閾值來提取最佳的骨架圖像。

4 結(jié)語

本文在深入研究Zhang細(xì)化算法的基礎(chǔ)上，針對圖像骨架沒有單像素化以及毛刺沒有有效處理的問題，進行了算法的優(yōu)化和改進，并用MATLAB將其實現(xiàn)。通過實驗的分析和對比，可以看出改進的算法能夠有效的去除毛刺，優(yōu)化骨架的視覺美感，效果優(yōu)于Zhang細(xì)化算法。此外，論文利用指定模板來決定像素點的保留或者刪除，還存在一定的局限性，今后將進一步研究這方面的工作。