張國棟，韓佳池

(沈陽航空航天大學計算機學院，沈陽 110136)

骨架作為一種簡單的物體形狀表示方式，不僅結(jié)合了物體的輪廓和區(qū)域信息，同時反應了物體重要的視覺信息，能夠方便的實現(xiàn)物體的特征匹配?；诠羌艿哪繕吮硎竞妥R別技術是模式識別和計算機視覺的重要研究內(nèi)容，被廣泛的應用于字符識別、指紋識別及醫(yī)學圖像分析等領域。

目前最具代表性的骨架定義主要有兩種。一種是火燒1模型(Grassfire)，該模型假設物體邊界點上的火源同時向內(nèi)燃燒，火焰成等距同心圓向內(nèi)推進，兩圓的切點就是物體的骨架點。細化法(Thinning)是模擬燒草模型的典型代表。傳統(tǒng)的細化算法能夠很好的保證骨架的連通性，但不能保證骨架點的準確性。另一種是最大圓定義法(maximal disk)，將骨架定義為物體內(nèi)最大圓圓心的集合［1］?；诰嚯x變換的骨架提取算法就是利用最大圓的理論，將任意點的距離變換值作為圓的半徑，比較所有內(nèi)切圓的包含關系最終找到最大圓的圓心。基于距離變換的骨架算法能夠保證骨架的正確位置，確保骨架的拓撲結(jié)構(gòu)，但缺點是不能保證骨架的連通性。典型的骨架生成算法無法避免的導致骨架產(chǎn)生過多的毛刺狀分枝，通常都需要一些后期的處理，因此骨架剪枝技術就成為一種輔助需要［2－3］。

模糊距離變換結(jié)合了距離變換與模糊理論的雙重特點，因此同距離變換一樣模糊距離變換也能夠反應物體的中軸信息。與此同時，由于模糊距離變換是對灰度圖像的操作，同時考慮了圖像的灰度信息和位置信息，因此相較于距離變換來說具有更強的穩(wěn)定性，并且能夠加精確的反應物體骨架點位置。對于邊界模糊的物體不再需要對其進行二值化操作，在處理模糊圖像時這一特性解決了難于對模糊圖像二值化的問題。通過以上分析可以發(fā)現(xiàn)，使用模糊距離變換值作為衡量骨架分支重要程度的標準，可以實現(xiàn)對物體粗骨架的剪枝操作。

本文提出的剪枝算法依據(jù)模糊距離變化這一理論基礎，在物體粗骨架圖中計算與骨架點相對應的模糊距離變換值，利用模糊距離變換值作為骨架分枝的顯著性度量標準，選取有效的剪枝閾值，通過分級剪枝操作去除骨架中的毛刺。

1 算法基本理論

1.1 基于模糊理論的模糊距離變換

距離變換作為一種有效的方法被廣泛的應用于目標識別和圖像處理領域。距離變換是針對二值圖像的操作，表示目標點到距其最近背景點的距離。由于距離變換的定義無法有效的應用于模糊對象中，因此我們將在模糊對象中的距離變換稱作模糊距離變換［4］。模糊距離變換是對灰度圖像的操作，它同時考慮了圖像的灰度信息和距離信息。模糊距離變換通過引入一個隸屬度函數(shù)，拓寬了距離變換的應用范圍，使其可以用于解決模糊對象問題。模糊距離變換(fuzzy distance transform，F(xiàn)DT)是模糊子集上的一個路徑長度，是兩點之間所有路徑長度的最小值［5］。下面給出模糊距離變換在數(shù)字網(wǎng)格空間中的定義和實現(xiàn)算法。

定義1(隸屬度函數(shù))設X是一個集合，S是X的模糊子集，則S是一個有序?qū)?，S={(x，μs(x))|x∈X}其中 μs(x):X→［0，1］是集合 S 的隸屬度函數(shù)。

定義2(支持域)o描述模糊分割后的目標物體，目標物體o的支撐域Θ(O)是所有隸屬度函數(shù)值不為零的像素的集合，如公式(1)所示。

定義3(鏈接)相鄰兩點p和q之間的長度定義為鏈接〈p，q〉，鏈接〈p，q〉的長度如公式(2)所示。

定義4(路徑)在集合S中，點p∈S到點q∈S的路徑 π 是一個連續(xù)序列，〈p=p1，p2，…，pm=q〉其中 pi∈S，1≤i≤m，對于任意的1≤j≤m，pj與pj+1是鄰接關系。

定義5(路徑長度)路徑 π=〈p=p1，p2，…，pm=q〉的長度記為Πo(π)，是路徑π上所有鏈接的和，如公式(3)所示。

假設P(p，q)表示p點到q點間所有路徑的集合，對于任意的路徑 π∈P(p，q)，如果滿足 Πo(πp，q)≤Πo(π)，則稱 πp，q∈P(p，q)是 p 點到 q點的一條最短路徑。用ωo(p，q)表示p點到q點的模糊距離，即從p到q的最短路徑的長度，如公式(4)所示。

定義6(模糊距離)在數(shù)字空間中，Ωo(p)表示模糊對象中p點的模糊距離變換值，是p點到距其最近的背景點的模糊距離，如公式(5)所示。

本文使用Punam K.Saha提出的動態(tài)規(guī)劃方法計算物體的FDT值。

1.2 骨架中點的類型

實現(xiàn)骨架剪枝算法的關鍵之一在于找到骨架的各個分枝。骨架中的每個分枝都是由骨架上的點組成，因此分清骨架中點的類型則變得極為重要。骨架中的點主要分為3種，即端點、節(jié)點和一般點。其中一般點是骨架的主要組成部分，節(jié)點和端點則出現(xiàn)在骨架發(fā)生劇烈變化的地方，他們反應了骨架主要的拓撲變化。將節(jié)點和端點統(tǒng)稱為特殊骨架點。下面給出骨架點的具體描述。

對于任意骨架點p的8－鄰域范圍內(nèi)僅存在一個骨架點時，我們稱它為端點。端點標識骨架每個分支的起點。對于任意的骨架點p的8－鄰域范圍內(nèi)存在至少兩個骨架點時，我們稱它為節(jié)點。節(jié)點是骨架不同部分的交匯點。若節(jié)點的8－鄰域范圍內(nèi)存在3個骨架點且任意兩個骨架點不相鄰，則此節(jié)點有3個分枝，稱p為三分枝節(jié)點。如果任意的節(jié)點p存在至少兩個尾枝，則稱它為多尾枝節(jié)點。去除端點和節(jié)點后，骨架中其它點的8－鄰域范圍內(nèi)存在兩個骨架點，我們稱他們?yōu)橐话泓c。

骨架的一般點構(gòu)成的連通集合稱為骨架段。由定義可以看出骨架中大部分的點都是一般點。連通任意兩個特殊骨架點且不通過第3個特殊骨架點并且具有惟一連通通路的骨架段稱為骨架的分枝。將節(jié)點與節(jié)點之間的骨架稱為一般分枝，將節(jié)點與端點之間的骨架稱為尾枝。由任意端點可以惟一的確定一條尾枝。將由同一節(jié)點引出的多個尾枝中不符合條件的尾枝稱為毛刺。將非毛刺的尾枝稱為一般尾枝。

2 算法實現(xiàn)

2.1 算法基本原理

本文提出的基于模糊距離變換的骨架剪枝算法，在對模糊距離變換圖像成像特點分析的基礎上，在粗骨架中使用模糊距離變換值作為骨架點的權值，按照規(guī)定的剪枝規(guī)則和設定的剪枝閾值，實現(xiàn)對粗骨架圖像進行分級的骨架剪枝操作，最終得到只反映物體主要拓撲結(jié)構(gòu)的骨架。

圖1 算法流程

圖1給出了該算法的基本流程。首先對原始圖像做去噪聲、計算隸屬度等預處理;然后使用動態(tài)規(guī)劃算法對預處理后的圖像進行模糊距離變換操作，同時使用現(xiàn)有的形態(tài)學骨架提取算法獲得目標物體的粗骨架圖像;接下來結(jié)合上一步驟所得到的粗骨架圖像和模糊距離變換圖像獲得帶權值的骨架圖;最后結(jié)合骨架的最小尾枝權值和當前尾枝權值確定動態(tài)剪枝閾值，并結(jié)合分級的剪枝規(guī)則實現(xiàn)剪枝操作。

2.2 算法描述

2.2.1 骨架權值計算

通過模糊距離變換我們得到了一個標量場，即模糊距離變換場。按照骨架的最大圓定義可以發(fā)現(xiàn)模糊距離變換與骨架之間有著某種聯(lián)系［6］，骨架點處的模糊距離變換值比其大多數(shù)相鄰點的模糊距離變換值要大。因此，利用模糊距離變換值作為骨架分枝的權值，對粗骨架進行剪枝操作將會得到良好的效果。在計算圖像的模糊距離變換時使用1.1節(jié)中所介紹的距離計算公式和實現(xiàn)方法，選取高斯函數(shù)為隸屬度函數(shù)，如公式(6)所示。

其中f是圖像灰度函數(shù)，mA和σA分別是灰度的平均值和標準差，Gma，σA是未規(guī)范化的高斯函數(shù)。

圖2(a)為由彩色圖像得到的灰度圖，圖2(b)表示了圖2(a)中物體的模糊距離變換，亮色處表示數(shù)值較大的位置，圖2(c)為利用matlab自帶函數(shù)bwmorph得到的物體粗骨架圖。從圖2(b)中可以看到，模糊距離變換圖像的脊線能夠精確的表示物體的拓撲結(jié)構(gòu)。從圖2(c)中我們可以看到，由函數(shù)bwmorph得到的骨架中，除了能夠反應物體拓撲特征的關鍵分枝外，在每條關鍵分枝上還存在很多細小的多余分枝，這些多余分枝會直接影響后續(xù)目標識別和特征提取等操作的效果及正確性。這里我們使用模糊距離變換作為剪枝權值同時結(jié)合了骨架的位置和灰度信息，與文獻［3］中使用的受圖像形狀因素影響過大的方法相比有更好的準確性和穩(wěn)定性。

圖2 物體灰度圖、物體FDT圖、物體的粗骨架圖、物體的帶權值骨架圖

利用粗骨架上各點對應的模糊距離變換值便可以得到帶權值的粗骨架圖，如圖2(d)所示。具體步驟如下。

步驟1:利用bwmorph函數(shù)對圖像進行骨架提取，得到粗骨架圖像。

步驟2:利用動態(tài)規(guī)劃法對圖像進行模糊距離變換計算，得到圖像的模糊距離變換圖。

步驟3:合并(1)(2)得到的結(jié)果，即得到帶權值的粗骨架圖像，該骨架圖反映了骨架的不同等級信息。

2.2.2 剪枝閾值的確定

剪枝閾值作為判斷尾枝是否為毛刺的依據(jù)，對骨架的剪枝效果起到了決定性的作用。在粗骨架圖中檢測并標記骨架的端點和節(jié)點。從骨架的每一個端點出發(fā)，對骨架進行跟蹤，直至跟蹤到一個節(jié)點，得到一條尾枝，將尾枝上所有骨架點的值進行累加作為該尾枝的權值。設置一個能夠反映尾枝重要程度的剪枝閾值。將尾枝的權值與剪枝閾值做比較來判定該尾枝是否是骨架的毛刺。被判定為毛刺的尾枝意味著它是由噪聲或細節(jié)產(chǎn)生的，在目標匹配中將不予以考慮。如果被判定為一般尾枝，則說明它能夠反映目標的重要形態(tài)結(jié)構(gòu)，對后期工作的開展意義重大。

剪枝閾值(Ath)的選取必須能夠動態(tài)的表征全局信息，并且能夠體現(xiàn)當前尾枝的信息，這樣才能保證快速、有效的實現(xiàn)骨架剪枝操作。設骨架中尾枝權值的最小值為 Amin，當前尾枝權值為Anow，剪枝閾值如公式(7)所示。

每次刪除毛刺都會影響到Amin的值，隨著剪枝次數(shù)的增加Amin的值在不斷增大，說明Amin能夠動態(tài)的表示骨架的全局信息，這也是我們在選取剪枝閾值時使用Amin值的主要原因。

2.2.3 骨架的分級剪枝

由于刪除毛刺的同時會導致新的毛刺的產(chǎn)生，因此骨架剪枝不可能一步完成，必須分級進行處理，級別由小到大會導致剪枝后的骨架結(jié)構(gòu)由繁到簡。適度的把握剪枝級別有助于得到精確的骨架結(jié)構(gòu)。級別過小會導致骨架分枝過多，無法準確的反映物體的真實結(jié)構(gòu);級別過大會導致骨架分枝過少，無法正確表示骨架的拓撲結(jié)構(gòu)，最終導致錯誤的表現(xiàn)物體的形狀及形態(tài)。

為了實現(xiàn)分級剪枝，設計如下的剪枝規(guī)則。如果節(jié)點只有一個尾枝，則將尾枝的權值與剪枝閾值做比較，若尾枝的權值小于剪枝閾值，則認為該尾枝并非是目標的結(jié)構(gòu)信息，應將其作為毛刺去除，否則保留。如果節(jié)點為多尾枝節(jié)點，則需對其進行分類處理，首先將小于閾值的尾枝去除，若仍存在兩條的尾枝，則比較兩尾枝權值的差值與閾值的大小，找到毛刺尾枝予以去除。

每次剪枝后，骨架中端點和分叉點的信息都會改變，因此每次剪枝結(jié)束后都需要重新檢測骨架中的端點和分叉點。尾枝類型的轉(zhuǎn)換及骨架點的更新原則。假設由節(jié)點p引出n條尾枝，如果p的k(k＜n)條尾枝被去除，骨架的端點數(shù)減少k個，節(jié)點p變?yōu)?n－k)條尾枝節(jié)點;如果p的(n－1)條被刪除，p點轉(zhuǎn)化為普通的一般點，剩下的這條尾枝與節(jié)點所在的骨架段組成了一條更長的尾枝，骨架的端點數(shù)減少(n－1)個。假設從節(jié)點p只引出一條尾枝，若該尾枝是毛刺則去除，此時節(jié)點變?yōu)橐话泓c，否則保留，骨架點信息不變。根據(jù)上述操作不難看出，每次刪除毛刺都會影響到Amin的值，隨著剪枝次數(shù)的增加Amin的值在不斷增大，說明Amin能夠動態(tài)的表示骨架的全局信息，這也是我們在選取剪枝閾值時使用Amin值的主要原因。

在某一級別處理結(jié)束之后，如果端點的數(shù)目沒有變化，說明本級處理過程沒有去除任何一條尾枝，此時算法收斂，終止處理過程。需要注意的是，在本算法中如果骨架比較簡單，在處理級別還未達到極限處理級別時，算法就會結(jié)束。此時骨架將是一條折線，沒有任何的分枝?？梢姡趯嶋H應用中，針對骨架的復雜情況選取適當?shù)奶幚砑墑e是十分重要的。

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

實驗中，首先對原始圖像進行形態(tài)學骨架提取(使用Matlab7.0中提供的形態(tài)學骨架化函數(shù)bwmorph)，然后使用本文提出的骨架剪枝算法對形態(tài)學方法得到的粗骨架進行剪枝處理。骨架尾枝權值的計算和骨架剪枝規(guī)則按照前節(jié)介紹方法進行，剪枝從第一級別開始，直至得到最佳效果。不同的圖像得到的骨架圖復雜程度不同，在剪枝時所需的剪枝級別也相應的不同。

對楓葉圖像進行實驗，結(jié)果如圖3所示，左邊是試驗原圖像，中間是原圖像通過形態(tài)學骨架算法提取的粗骨架，右邊是對中間圖像剪枝后的結(jié)果?？梢?，剪枝后的骨架正確的反應了楓葉葉片的形態(tài)結(jié)構(gòu)，同時有效的去除了有細節(jié)部分所產(chǎn)生的小分支。

圖3 圖2中物體骨架提取和毛刺去除效果

圖4是對同一飛機圖片不同仿射變換結(jié)果進行剪枝的試驗結(jié)果。左邊一列為圖像在不同仿射變換下的灰度圖像，中間一列是不同仿射變換圖像的粗骨架圖像，從圖4中我們可以看出，同一圖像在不同的仿射變換后得到的粗骨架圖是截然不同的，右邊一列是應用本文算法，對粗骨架剪枝后的結(jié)果圖像。

通過對圖4中3組圖像的對比不難看出，該算法對不同仿射變換后的復雜圖像具有良好的剪枝效果。與文獻［2］中提出的使用骨架權值的最大值和最小值結(jié)合得到的剪枝閾值相比較，本算法提出的剪枝閾值在剪枝操作中效率更高。表1中分析了在以上兩幅圖像中使用不同的剪枝閾值所需要的剪枝操作次數(shù)。

圖4 同一目標仿射變換后剪枝效果

從表1可以看出，針對同一副圖像，本文所使用的剪枝閾值更加能夠更加快速的獲得最優(yōu)的剪枝結(jié)果。在處理楓葉圖像時，本文算法相較于文獻［2］算法節(jié)省了12次剪枝操作;在飛機圖像中節(jié)省了8次剪枝操作。說明本算法在保證實驗結(jié)果的同時，提高了骨架剪枝效率。

表1 本文算法與文獻［2］算法剪枝次數(shù)比較

以上實驗結(jié)果說明該算法能夠快速、有效的去除由細節(jié)或噪聲產(chǎn)生的多余分支和毛刺，并且能夠保證較好的穩(wěn)定性。

4 結(jié)束語

針對傳統(tǒng)骨架提取方法獲得的結(jié)果中出現(xiàn)骨架多像素及毛刺較多的現(xiàn)象，本文提出一種基于模糊距離變換的骨架剪枝算法。該算法依據(jù)物體的模糊距離變換值，通過比較粗骨架中各尾枝權值和剪枝閾值的關系實現(xiàn)粗骨架的剪枝處理。確定剪枝閾值時充分考慮其動態(tài)性，使剪枝閾值隨著剪枝級別的升高而逐漸增大，使剪枝過程分級化，避免將骨架主要部分作為毛刺去除。實驗結(jié)果表明，該方法實現(xiàn)簡單、快速，能夠去除骨架中多余的分支，同時保證了骨架結(jié)構(gòu)的穩(wěn)定性。通過對物體模糊距離變換圖像的分析，發(fā)現(xiàn)物體的骨架線恰好在模糊距離變換圖像的脊線上，由此將其應用于骨架剪枝操作中，根據(jù)這一特性，可以考慮在后期研究中利用模糊距離變換圖像中局部較大的值直接對物體進行骨架提取，用這種方法得到的骨架將會比利用形態(tài)學方法得到的骨架更加精確，且不再需要后期的剪枝操作。

［1］丁頤，劉文予，鄭宇化.基于距離變換的多尺度連通骨架算法［J］.紅外與毫米波學報，2005，24(4):281－285.

［2］李小燕，程顯毅.基于權值的骨架修剪算法［J］.計算機工程與設計，2009，30(14):3374 －3376.

［3］秦筱楲，蔡超，周成平.一種有效的骨架毛刺去除算法［J］.中華科技大學學報(自然科學版)，2004，32(12):28－31.

［4］ Punam K.Saha，F(xiàn)elix W.Wehrli，Bryon R.Gomberg.Fuzzy distance transform:theory，algorithms and applications［J］.Computer Vision and Image Understanding，2002，86(3):171 －190.

［5］許燕，Punam K.Saha，胡廣書，等.基于模糊距離變換的三維血管造影冠狀動脈形狀分析［J］.清華大學學報(自然科學版)，2010，50(3):454 －457.

［6］ Stina Svensson.Centres of maximal balls extracted from a fuzzy distance［R］.Proceedings of 8th International Symposium on Mathematical Morphology(ISMM 2007)in Pio de Janerio，Brasil，Oct.10 － 13，2007.

［7］劉俊濤，劉文予，吳彩華，等.一種提取物體線形骨架的新方法［J］.自動化學報，2008，34(6):617 －622.

［8］王金玲，段會川，劉弘.基于輪廓線度量的形態(tài)學骨架剪枝方法［J］.計算機工程與設計，2009，30(9):2283－2285.