基于距離變換的A*搜索骨架提取方法*

唐姝 劉俊

（武漢科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院 武漢 430065）

1 引言

一個對象的骨架被看作是其中軸，這個概念最早是由Blum提出的［1］。關(guān)于骨架的經(jīng)典定義有兩種：一種是火燒模型，其定義為火種從物體邊界同時向物體內(nèi)部燃燒，火種的相遇點就是中軸點即骨架點；另一種是最大圓盤模型，其定義為骨架即為包含在物體內(nèi)部的，與物體邊界至少有兩個相切點的，所有不重合的圓的圓心集合。骨架可以有效地表示物體的拓?fù)浣Y(jié)構(gòu)和物體的形狀特征。利用骨架對目標(biāo)進(jìn)行表示、識別，這些技術(shù)已經(jīng)被廣泛應(yīng)用于路徑規(guī)劃、交通警察的手勢識別［2］、考古學(xué)［3］、文學(xué)［4］、物料的分選［5］和信息存儲檢索［6］等領(lǐng)域。

關(guān)于骨架的提取方法，一般面臨以下問題：1）提取骨架是否具有連通性；2）提取的骨架是否具有單像素性；3）提取的骨架是否逼近物體的中軸；4）在小的形變下，提取的骨架是否可以保持位置的穩(wěn)定；5）提取的骨架是否保持原始物體的拓?fù)浣Y(jié)構(gòu)。

目前關(guān)于骨架提取的算法大致可以分為以下幾類：骨架細(xì)化方法［7］，其核心思想是在物體邊界上留下滿足骨架提取算法要求的點，并去除其他冗余點。利用迭代的思想，將邊界上的冗余點連續(xù)剝離，直到?jīng)]有多余的邊界信息為止，剩下的是提取的骨架。這種方法提取的骨架具有單像素性和連通性，但提取的骨架的位置，即骨架是否逼近物體的中軸不能得到保證，并且這種方法對邊界噪聲敏感，提取的骨架易產(chǎn)生冗余分支；利用物體距離場進(jìn)行骨架提取的方法［8～10］，其中心思想是先對物體進(jìn)行距離變換，尋找物體的局部極值點，最終形成骨架。這種方法提取的骨架的位置的準(zhǔn)確性得到了保證，但是提取的點一般是離散的，很難保證提取骨架的連通性；基于Voronoi圖的骨架提取方法［11］，其中心思想是利用Voronoi圖來獲得物體的骨架。這種方法提取到的骨架趨近于中軸，但是該算法的整體復(fù)雜性難以預(yù)料，并且對于如何處理非中軸部分也是比較復(fù)雜的；利用點云進(jìn)行骨架提取的方法［12］，其中心思想是利用點云中區(qū)域內(nèi)的連通性和區(qū)域間的相關(guān)性進(jìn)行骨架的提取。這種方法提取的骨架的原有的拓?fù)浣Y(jié)構(gòu)得到了保持，但是此類方法的計算較復(fù)雜。

A*（A star）算法是一種經(jīng)典的求解最短路徑的搜索方法，其中心思想是利用目前已知的信息，根據(jù)目標(biāo)的初始狀態(tài)，當(dāng)前狀態(tài)以及目標(biāo)狀態(tài)來搜索路徑。A*算法常被用于器械、游戲、導(dǎo)航、無人機等領(lǐng)域的路徑規(guī)劃工作。

針對部分傳統(tǒng)骨架提取方法提取骨架位置偏離中軸的問題，提出了一種基于距離變換的A*搜索骨架的提取方法。該方法提出通過物體得到的距離場和形態(tài)學(xué)分水嶺算法獲得包含有物體骨架的骨架潛在圖，然后通過主動輪廓線模型及物體頂點到物體凸包的距離得到對物體形狀信息貢獻(xiàn)較大的骨架端點，并將其視為骨架關(guān)鍵點；根據(jù)分水嶺算法得到的潛在骨架圖和骨架關(guān)鍵點，利用A*算法來搜索出物體的骨架線。該方法得到的骨架既避免了骨架的離散性問題，又保證了骨架的單像素性，對邊界噪聲具有一定的抗敏性。通過控制頂點到目標(biāo)凸包邊界的距離進(jìn)行篩選，得到對目標(biāo)形狀有不同貢獻(xiàn)的骨架關(guān)鍵點，實現(xiàn)骨架的多尺度控制，并且最終的骨架長度與傳統(tǒng)的骨架提取算法相比，更接近于目標(biāo)的長度。

2 骨架特征分析

2.1 距離變換

距離變換是一種圖像變換的方法，會將二值圖像轉(zhuǎn)換成灰度圖像，其中，圖像中越靠近“脊”的點表示這個點距離物體的邊界（零點）越遠(yuǎn)。其核心思想是根據(jù)一定的距離定義方法確定從一個點到物體邊界點的最小距離。根據(jù)最小距離值的大小，給予點對應(yīng)的像素值，所有的點及其對應(yīng)的距離值構(gòu)成對應(yīng)的距離場。根據(jù)不同的距離定義，可以將距離變換劃分為：非歐氏距離變換和歐氏距離變換。

關(guān)于骨架的定義有兩種：一種是火燒模型；另一種是最大圓盤模型。因此，骨架是從對象內(nèi)部到邊界的距離最小的點集。由此可知，通過距離變換得到的距離場中的“脊”可以很好地反映這一特性，通過距離變換得到距離場，進(jìn)而得到骨架的相關(guān)信息。本文利用歐氏距離變換得到的距離場。

2.2 形態(tài)學(xué)分水嶺算法

形態(tài)學(xué)分水嶺算法是一種傳統(tǒng)的用于圖像分割的形態(tài)學(xué)方法，其基本思想是假設(shè)在每個區(qū)域的最低點打一個洞，讓水通過這些洞以均勻的速率進(jìn)入每個區(qū)域，自下往上的淹沒每個區(qū)域。當(dāng)每個區(qū)域的水平面逐漸上升時，通過修建一個分水嶺來阻止這些水平面的匯集。當(dāng)在水平面上只能看到分水嶺的頂部的時候，這些分水嶺的頂部（由單像素構(gòu)成）就相當(dāng)于是分水嶺分割算法中的分割線，也叫分水線。因此，這些分水線是由分水嶺分割算法得到的連通的分割線。

距離場中的物體邊界相當(dāng)于是分水嶺分割算法中的區(qū)域最低點，距離場中的高亮部分相當(dāng)于是其中的“分水嶺”，分水線是“分水嶺”極值點的集合，而骨架是距離場中高亮部分的極值點，即分水線相當(dāng)于是距離場中的骨架。

2.3 潛在骨架圖

從圖1（b）中可以看出，距離場中較亮的部分處于原圖物體中的中間位置，且其構(gòu)成的拓?fù)浣Y(jié)構(gòu)與原物體相似，具備了原物體大致的骨架形態(tài)。在提取潛在骨架圖的步驟中，將距離場中的“脊”看作是圖像分割中的“物體邊界”，利用形態(tài)學(xué)分水嶺算法對距離場進(jìn)行“分割”，進(jìn)而得到潛在骨架圖。從圖中1（c）可以看出，物體的骨架已經(jīng)在骨架潛在圖中有了體現(xiàn)。

圖1 潛在骨架圖

3 骨架端點的確定

關(guān)于端點的定義，廣義上，所有的物體邊界點都可以看作是端點，而關(guān)于骨架的端點，所有的物體邊界凸點都可以看作是物體骨架的端點［13］，所以可以通過找到所有的物體邊界上的凸點，進(jìn)而確定物體骨架的端點。因此，本文利用主動輪廓線模型確定骨架端點的候選點，并根據(jù)這些點到目標(biāo)凸包邊界的最短距離選擇不同尺度的骨架端點，從而在克服一定邊界噪聲的同時控制骨架尺度。

主動輪廓線模型常用來進(jìn)行圖像分割，主動輪廓線模型的基本原理是：首先給定一個大致的輪廓曲線，然后以給定的輪廓曲線為模板，通過調(diào)整輪廓曲線使其更貼近目標(biāo)輪廓。給定的輪廓曲線是可以通過調(diào)整參數(shù)來改變的參數(shù)曲線，曲線具有相應(yīng)的能量函數(shù)。能量函數(shù)不僅有表示外部能量，即圖像本身的整體輪廓信息的部分，還有表示內(nèi)部能量，即給定輪廓曲線的形狀信息的部分。通過控制參數(shù)曲線，達(dá)到目標(biāo)能量函數(shù)最小的目的。此時，得到的曲線就是目標(biāo)輪廓線。雖然主動輪線廓模型在調(diào)整過程中容易陷入局部極值，不能陷入輪廓深度凹陷部分，但不影響目標(biāo)邊界凸點的確定。

確定目標(biāo)邊界的凸點后，將原始圖像看作二維平面上的一組點，得到目標(biāo)的凸包。利用目標(biāo)邊界凸點到凸包邊界的最短距離，通過中心極限定理，對選定的點進(jìn)行篩選，得到骨架端點。得到骨架端點之后，通過調(diào)整距離閾值d，利用物體邊界凸點到凸包邊界的最短距離di對骨架端點進(jìn)行篩選，其中：

其中，0≤p≤1，若

則di所對應(yīng)的端點候選點為篩選之后的骨架端點。這樣，可以得到不同尺度的物體骨架端點，進(jìn)而得到不同尺度的物體骨架。

4 基于A*搜索算法的骨架提取

得到的骨架潛在圖相當(dāng)于是路徑搜索過程中的地圖，骨架端點相當(dāng)于是起點和終點。地圖中，有不通的路，有障礙，若要搜索路徑，A*算法在這方面表現(xiàn)較好。

4.1 算法流程圖

本文提出的基于距離變換的A*搜索骨架提取方法的具體流程如圖2所示。

圖2 本文算法流程圖

4.2 A*算法的基本原理

A*算法是一種用于靜態(tài)路網(wǎng)中求解最短路徑有效的搜索方法，常用于路徑規(guī)劃。相較于其他的路徑搜索算法，A*算法相對靈活，能用于多種多樣的情形之中。在一定條件下，A*算法具有與Dijks?tra算法一樣的功能，可用于搜索最短路徑；在某些條件下，A*算法也可以和BFS（最佳優(yōu)先搜索算法）一樣快，此時搜索到的路徑不一定是最短的，但是時間上有很大的優(yōu)勢。原因在于，A*算法中會有一個啟發(fā)式函數(shù)用于預(yù)估代價，A*算法在路徑搜索的過程中會綜合考慮從初始狀態(tài)到當(dāng)前狀態(tài)的代價和從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的預(yù)估代價。A*算法可以表示為

其中，g（n）代表從初始狀態(tài)到當(dāng)前狀態(tài)的代價，h（n）代表從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的預(yù)估代價。在路徑搜索過程中，A*算法會權(quán)衡兩者，使f（n）的值最小。在f（n）中，g（n）的值是可知的，故啟發(fā)式函數(shù)h（n）可以控制A*的行為，其中，存在兩種極端的情況：若h（n）=0，即f（n）=g（n），只有g(shù)（n）起作用，此時A*算法等價于Dijkstra算法，可以保證能找到最短路徑；若h（n）>>g（n），只有h（n）起作用，此時A*算法等價于BFS（最佳優(yōu)先搜索算法）算法。所以，通過調(diào)整g（n）和h（n），可以得到符合要求的路徑。

4.3 結(jié)點的選擇和地圖的構(gòu)成

已經(jīng)確定的骨架端點構(gòu)成了A*算法中的結(jié)點集，其中，選定一個結(jié)點作為初始結(jié)點，剩余結(jié)點構(gòu)成目標(biāo)結(jié)點集。原圖的潛在骨架圖構(gòu)成了A*算法中的地圖，像素點被視為網(wǎng)格，其中，白色的部分視為可通路徑，黑色部分則視為障礙。如果找到初始結(jié)點到某一目標(biāo)結(jié)點的路徑，則搜索成功，保存該路徑且在目標(biāo)結(jié)點集中刪除該目標(biāo)結(jié)點重新設(shè)置A*算法的目標(biāo)結(jié)點集，即搜索到的路徑為一骨架分支；如果找不到初始結(jié)點到某一目標(biāo)結(jié)點的路徑，則搜索失敗，在目標(biāo)結(jié)點集中刪除該目標(biāo)結(jié)點重新設(shè)置A*算法的目標(biāo)結(jié)點集。

4.4 代價函數(shù)和啟發(fā)式函數(shù)的設(shè)置

A*算法的搜索過程不是靜態(tài)的，可以建立一個啟發(fā)式函數(shù)，假定通過一個網(wǎng)格空間的最小代價是1，可以建立代價函數(shù)用于測量：

若?=0，則改進(jìn)后的代價函數(shù)的值恒為1，這種情況下，A*算法變成簡單地判斷一個網(wǎng)格可否通過；若?=1，則最初的代價函數(shù)將起作用。

A*算法在搜索過程中，會擴展結(jié)點進(jìn)行搜索，當(dāng)啟發(fā)式函數(shù)精確地等于實際最佳路徑時，A*算法的擴展結(jié)點將會非常少。在網(wǎng)格地圖中，有很多啟發(fā)式函數(shù)，例如歐氏距離、城市街區(qū)距離、棋盤距離等，本文啟發(fā)式函數(shù)中采用的是城市街區(qū)距離，故：

其中，D代表從一個位置移動到鄰近位置的最小代價。

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

5.1 實驗數(shù)據(jù)集及參數(shù)設(shè)置

實驗采用的是MPEG—7 CE Shape-1 Part B數(shù)據(jù)集中的圖像。關(guān)于實驗中的參數(shù)設(shè)置，式（4）中?值設(shè)置為0.5，故通過式（4）可得到：

式（5）中D值設(shè)置為1，故通過式（5）可得到：

5.2 連通性和單像素性分析

本文提取的骨架是直接在得到的骨架潛在圖中提取出來的，骨架潛在圖是由通過形態(tài)學(xué)分水嶺分割算法作用在物體的距離場上得到的分水線構(gòu)成。通過形態(tài)學(xué)分水嶺分割算法得到的分水線具有連通性和單像素性，故骨架潛在圖中的骨架具有連通性和單像素性，由此可知，最后得到的物體骨架具有連通性和單像素性。如圖3所示，本文的方法得到的骨架有較好的連通性。

圖3 一些二值圖像的骨架

5.3 多尺度控制變化分析

通過主動輪廓線模型得到物體骨架端點候選點之后，通過調(diào)整p值，控制閾值大小，進(jìn)而得到不同尺度的骨架端點。圖4所示是本文算法通過調(diào)整參數(shù)得到的不同尺度的物體骨架。從圖中可以看出，本文算法通過調(diào)整參數(shù)得到了三種不同的骨架尺度，具有一定的骨架尺度控制能力。

圖4 同一物體不同尺度的骨架

5.4 骨架長度分析

本文算法得到的骨架是通過對物體的距離場圖進(jìn)行分水嶺分割算法得到的，得到的骨架長度相較于其他算法，更接近于物體的長度。圖5、圖6所示是本文算法和Yu等［14］方法、Choi等［15］方法的實驗結(jié)果對比，其中，圖5（a）、圖6（a）為本文算法實驗結(jié)果，圖5（b）、圖6（b）為Yu方法實驗結(jié)果，圖5（c）、圖6（c）為Choi方法實驗結(jié)果。從圖5中可以看出，本文算法和Yu方法實驗結(jié)果的骨架長度相較于Choi方法實驗結(jié)果的骨架長度更接近于物體的長度；Yu方法得到的骨架在錘子彎曲的地方有冗余的骨架分支（白色圓圈內(nèi)）。從圖6可以看出，本文算法與Yu方法實驗結(jié)果的骨架長度相較于Choi方法實驗結(jié)果的骨架長度更接近于物體的長度；本文方法與Yu方法的對比：鑰匙柄處是上下對稱的，上方兩條骨架分支的交點與下方兩條骨架的交點（或左方兩條骨架分支的交點與右方兩條骨架分支的交點）應(yīng)該在同一垂直線（或水平線）上。這一點，本文方法表現(xiàn)比Yu方法好。

圖5 實驗結(jié)果對比圖一

圖6 實驗結(jié)果對比圖二

5.5 邊界噪聲

本文算法利用距離變換得到的距離場，進(jìn)行分水嶺分割，以及利用對噪聲不敏感的主動輪廓線模型來確定骨架的端點，在一定程度上克服了一定的邊界噪聲的影響。圖7、圖8比較了在有無邊界噪聲情況下，本文算法的表現(xiàn)。由圖可以看出，有噪聲時，得到的物體骨架在細(xì)微處會有些變化，但從整體上看，得到的物體骨架仍然可以表示物體的拓?fù)浣Y(jié)構(gòu)。

圖7 邊界噪聲分析圖一

圖8 邊界噪聲分析圖二

5.6 物體骨架的拓?fù)浣Y(jié)構(gòu)分析

骨架常被用來進(jìn)行物體識別，所以提取的物體骨架是否能正確的表示物體的拓?fù)浣Y(jié)構(gòu)至關(guān)重要。圖9比較了本文算法和Yu方法的實驗結(jié)果，其中，圖9（a）是本文算法的實驗結(jié)果，圖9（b）是Yu方法的實驗結(jié)果。由圖可以看出，物體邊界有一處較為凸起的部分（白色圓圈內(nèi)），圖9（a）相較于圖9（b）在此處多了一條骨架分支，加上這條骨架分支，更能很好的表示物體的拓?fù)浣Y(jié)構(gòu)。圖10是本文算法對兩個形狀相似的物體的實驗結(jié)果。圖10（a）和圖10（b）之間的差別在于，圖10（b）的邊界不是直線，而是向物體內(nèi)部凹陷的曲線。由圖可以看出，兩個實驗結(jié)果在底邊處有明顯的差別（白色圓圈內(nèi)），圖10（a）此處的骨架趨近于水平直線，圖10（b）此處的骨架向物體內(nèi)部凹陷。

圖9 拓?fù)浣Y(jié)構(gòu)分析圖一

圖10 拓?fù)浣Y(jié)構(gòu)分析圖二

6 結(jié)語

針對部分傳統(tǒng)骨架提取方法提取骨架位置偏離中軸的問題，提出了一種基于距離變換的A*搜索骨架的提取方法。該方法利用距離場和形態(tài)學(xué)分水嶺算法獲得包含有物體骨架的骨架潛在圖；利用主動輪廓線模型確定物體凸點，通過物體頂點到物體凸包的距離，對骨架凸點進(jìn)行篩選，得到骨架關(guān)鍵點；利用A*算法對多個目標(biāo)點進(jìn)行搜索，進(jìn)行骨架修剪，得到骨架。實驗結(jié)果表明，該方法獲得的骨架具有連通性、單像素性、一定的抗噪能力等優(yōu)點。