唐姝 劉俊

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

1 引言

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

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

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

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

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

2 骨架特征分析

2.1 距離變換

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

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

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

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

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

2.3 潛在骨架圖

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

圖1 潛在骨架圖

3 骨架端點(diǎn)的確定

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

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

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

其中，0≤p≤1，若

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

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

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

4.1 算法流程圖

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

圖2 本文算法流程圖

4.2 A*算法的基本原理

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

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

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

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

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

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

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

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

其中，D代表從一個(gè)位置移動(dòng)到鄰近位置的最小代價(jià)。

5 實(shí)驗(yàn)結(jié)果與分析

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

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

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

5.2 連通性和單像素性分析

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

圖3 一些二值圖像的骨架

5.3 多尺度控制變化分析

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

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

5.4 骨架長(zhǎng)度分析

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

圖5 實(shí)驗(yàn)結(jié)果對(duì)比圖一

圖6 實(shí)驗(yàn)結(jié)果對(duì)比圖二

5.5 邊界噪聲

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

圖7 邊界噪聲分析圖一

圖8 邊界噪聲分析圖二

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

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

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

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

6 結(jié)語(yǔ)

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