戴凌震，榮 曄，史有群

基于歐氏距離及向量內(nèi)積的骨架提取算法

戴凌震，榮 曄，史有群

對骨架算法進(jìn)行研究，提出一種骨架提取算法。通過對圖像內(nèi)部像素點(diǎn)進(jìn)行距離變換得到其最近邊界點(diǎn)的位置，將內(nèi)部像素點(diǎn)到最近邊界點(diǎn)的向量定義為邊界向量，根據(jù)物體內(nèi)部相鄰邊界向量的方向，計(jì)算每個(gè)像素點(diǎn)的內(nèi)積值和其8鄰域的最小內(nèi)積值，得到的最小內(nèi)積點(diǎn)，以確定的閾值從最小內(nèi)積點(diǎn)中選取骨架種子點(diǎn)，再對骨架種子點(diǎn)進(jìn)行處理，得到連通的骨架。試驗(yàn)證明這種算法能保證骨架具的完整性和連通性，正確反映物體的拓?fù)浣Y(jié)構(gòu)。

骨架；邊界向量；內(nèi)積；距離變換

0 引言

描述物體形狀的重要工具是骨架，它包含物體的拓?fù)浣Y(jié)構(gòu)和形狀特征，是描述物體形狀的方式，由骨架所體現(xiàn)的物體輪廓和區(qū)域信息，可以方便地進(jìn)行物體的特征匹配，在計(jì)算機(jī)圖形學(xué)、圖像檢索、圖像處理、模式識別和生物醫(yī)學(xué)等領(lǐng)域得到了廣泛的應(yīng)用，物體骨架的概念最早由 Blum 提出[1]。

近年來，骨架提取算法一直是圖像處理研究的一個(gè)熱門課題，許多學(xué)者都提出了不同的骨架算法。這些算法大致分為 3 類。第一類是細(xì)化和邊界擴(kuò)展算法，文獻(xiàn)[2]綜述了各種細(xì)化算法的實(shí)現(xiàn)及應(yīng)用?；馃Ｐ蚚3]和波形推進(jìn)面[4]方法是最常用的細(xì)化算法。第二類是基于區(qū)域的中軸算法。包括Voronoi圖及其應(yīng)用[5]，數(shù)學(xué)形態(tài)學(xué)[6]和最大圓盤[7]等。細(xì)化算法和中軸算法都對邊界噪聲敏感，微小的邊界噪聲干擾會出現(xiàn)較多的骨架分支，需要對骨架進(jìn)行剪枝處理，以簡化骨架的拓?fù)浣Y(jié)構(gòu)。第三類是基于距離變換的算法[8]，通過對象內(nèi)部像素點(diǎn)到邊界的距離圖確定對象的脊線。這種方法對于一些狹長的對象形狀無法得到清晰的脊線，骨架的連通性通常難以保證。

基于歐氏距離和向量內(nèi)積的骨架提取算法。首先計(jì)算圖像內(nèi)部每一個(gè)像素點(diǎn)到對應(yīng)邊界點(diǎn)的歐式距離，由歐氏距離變換的結(jié)果求出相應(yīng)最近邊界點(diǎn)的位置，定義將從內(nèi)部像素點(diǎn)指向最近邊界點(diǎn)的向量定義為邊界向量，根據(jù)相鄰邊界向量的方向，計(jì)算每個(gè)像素點(diǎn)的內(nèi)積值，并且求出其8鄰域的最小內(nèi)積值，由設(shè)定的內(nèi)積閾值在最小內(nèi)積值中選取骨架種子點(diǎn)，通過對骨架種子點(diǎn)的向外延伸和向內(nèi)連接，將骨架連通起來。得到的骨架完整并且連通，能正確描述物體的拓?fù)浣Y(jié)構(gòu)。

1.基本定義

文中物體定義為閉合曲線所包圍的部分，物體的邊界即為閉合曲線。物體的內(nèi)部像素點(diǎn)是邊界內(nèi)部的像素，邊界上的像素稱為物體的邊界點(diǎn)。距離變換是圖像內(nèi)部像素點(diǎn)到邊界點(diǎn)的最近距離。

通過距離變換確定物體內(nèi)部每一個(gè)像素點(diǎn)的最近邊界點(diǎn)。邊界向量是這樣一段有向線段，它的起始于內(nèi)部像素點(diǎn)、終止于與始于內(nèi)部像素點(diǎn)最近的邊界點(diǎn)，如圖1中的所示：

圖1 圖像點(diǎn)和邊界向量

在圖1（a）中， L1， L2分別是兩條平行邊界線上的邊界點(diǎn)。 L1L2線段上所有的點(diǎn)都是內(nèi)部像素點(diǎn)。若 M 為L1L2線段的中點(diǎn)，則線段上每個(gè)像素點(diǎn)的邊界向量方向一致，指向上像素點(diǎn)的邊界向量一致，指向。在M點(diǎn)附近像素點(diǎn)的邊界向量方向相反。中點(diǎn)M的位置可以根據(jù)邊界向量方向變化確定。

邊界向量的變化可以用相鄰像素點(diǎn)的邊界向量夾角φ表示，如圖1（b）中的點(diǎn)和點(diǎn)。二維邊界向量的夾角大小定義如公式（1）：

最小內(nèi)積值 A由式（2）確定如公式（2）：

根據(jù)邊界向量和最小內(nèi)積點(diǎn)的定義，物體的中點(diǎn)兩邊的邊界向量方向不同，中點(diǎn)邊界和其鄰近點(diǎn)的邊界向量具有最大的向量夾角和最小的內(nèi)積值，因此中點(diǎn)必為最小內(nèi)積點(diǎn)，物體的骨架點(diǎn)就存在于最小內(nèi)積點(diǎn)中。通過計(jì)算物體內(nèi)部像素的內(nèi)積值，可以繪制出物體的內(nèi)積值圖。圖（2）是 MPEG7圖形數(shù)據(jù)庫中鹿的最小內(nèi)積值圖，圖中線段的顏色越深，表示其內(nèi)積值越小，顏色最深的點(diǎn)就是最小內(nèi)積點(diǎn)。

圖2 MPEG7 圖形數(shù)據(jù)庫中鹿的最小內(nèi)積值圖

2.基于內(nèi)積骨架提取算法

圖2的結(jié)果表明，每個(gè)最小內(nèi)積點(diǎn)到對應(yīng)邊界的距離最遠(yuǎn)，因此，物體的骨架點(diǎn)包含在這些最小內(nèi)積點(diǎn)中。但是，這些最小內(nèi)積點(diǎn)不能直接作為物體的骨架，因?yàn)樗鼈儼诉^多的冗余分支。為了得到物體的主干骨架結(jié)構(gòu)和良好的骨架連通性，本文提出一種基于內(nèi)積的骨架提取算法。

首先，對給定的二值圖像進(jìn)行距離變換，計(jì)算每個(gè)內(nèi)部像素點(diǎn)到邊界的最近距離和最近邊界點(diǎn)的位置，根據(jù)得到的數(shù)據(jù)計(jì)算每個(gè)內(nèi)部像素點(diǎn)的邊界向量。其次，對內(nèi)部像素點(diǎn)邊界向量及相鄰的八鄰域點(diǎn)邊界向量進(jìn)行內(nèi)積計(jì)算，取出具有最小內(nèi)積值的最小內(nèi)積點(diǎn)及與之對應(yīng)的最小配對點(diǎn)。根據(jù)最小內(nèi)積值畫出最小內(nèi)積值圖，在最小內(nèi)積值圖中選擇骨架種子點(diǎn)。然后，對骨架種子點(diǎn)進(jìn)行向外延伸和向內(nèi)連接處理，最后，輸出完整的骨架圖。

其中骨架種子點(diǎn)選擇和骨架的向外延伸和向內(nèi)連接處理是算法的核心，下面將詳細(xì)討論。

2.1 骨架種子點(diǎn)選擇

骨架種子點(diǎn)是最小內(nèi)積值圖中具有較高可信度的內(nèi)部像素點(diǎn)，它要滿足最小內(nèi)積值條件，也就是說這個(gè)點(diǎn)必須為最小內(nèi)積點(diǎn)。根據(jù)最大圓盤定理，以最小內(nèi)積點(diǎn)為圓心的最大內(nèi)切圓與邊界的切點(diǎn)就是最小內(nèi)積點(diǎn)的最近邊界點(diǎn)，且有邊界向量垂直邊界切線的關(guān)系。如果兩條邊界切線平行，如圖1（a）所示，那么邊界向量夾角為π，兩個(gè)邊界切點(diǎn)連線的中點(diǎn)必定是骨架點(diǎn)。如果邊界切線不平行，如圖3 所示：

圖3 邊界向量夾角和邊界切線夾角的關(guān)系

綜上所述在最小內(nèi)積值圖中,滿足最小內(nèi)積值小于 0、邊界向量夾角大于 °90 的像素點(diǎn)可能是骨架種子點(diǎn)。由此選定內(nèi)積閾值等于0，最小內(nèi)積值小于 0的最小內(nèi)積點(diǎn)為骨架種子點(diǎn)。

在數(shù)字圖像中斜邊界線由于存在鋸齒現(xiàn)象引起邊界凸起部分，這些凸起部分的內(nèi)積值也會滿足骨架種子點(diǎn)的條件，造成多余骨架點(diǎn)的存在。為了避免虛假骨架點(diǎn)的干擾，對骨架種子點(diǎn)的選擇加一個(gè)限定條件：骨架點(diǎn)與邊界的距離必須大于一個(gè)像素。

由內(nèi)積閾值確定的骨架種子點(diǎn)，可能是一些孤立的點(diǎn)，也可能組成連續(xù)的骨架線段，對圖2的最小內(nèi)積值圖進(jìn)行內(nèi)積閾值處理后，得到的骨架種子點(diǎn)圖如圖4所示：

圖4 MPEG7 圖形數(shù)據(jù)庫中鹿的骨架種子點(diǎn)圖

出現(xiàn)了骨架斷裂現(xiàn)象，需要輔以適當(dāng)?shù)姆绞竭B接這些種子點(diǎn)，以得到連通的骨架。

2.2 骨架向外延伸過程

要正確描述物體的形狀，物體的骨架必須包含主骨架和骨架分支。物體的中軸表現(xiàn)物體主干部分的拓?fù)浣Y(jié)構(gòu)，是主骨架，在圖2中就是鹿的身體部分的骨架。骨架分支表示的是物體的凸起部分，它們是主骨架延伸的部分，如圖2中鹿的鹿角、四肢部分。在最小內(nèi)積值圖中，在主骨架種子的附近沿著其凸起部分存在另一個(gè)骨架種子，則在這兩個(gè)種子點(diǎn)之間必定存在連通這兩點(diǎn)、且內(nèi)積值大于0的其他最小內(nèi)積值點(diǎn)，如圖4所示。這些點(diǎn)可能是骨架的部分分支，但是，不滿足骨架種子點(diǎn)選擇的原則，出現(xiàn)了骨架斷裂現(xiàn)象，因此需要進(jìn)行骨架向外延伸處理，將骨架分支延伸到凸起部分的終端。

為了實(shí)現(xiàn)骨架向外延伸，連接有效的骨架分支，需要給出骨架種子點(diǎn)和其最小配對點(diǎn)的最近邊界點(diǎn)的位置、這些邊界點(diǎn)在邊界序列中的編號。通過邊界序列編號，計(jì)算出每對點(diǎn)對應(yīng)的邊界長度。

沿著凸起部分連接骨架種子過程如圖5所示：

圖5 骨架向外延伸示意圖

在圖5中，設(shè)骨架種子點(diǎn) A1和最小配對點(diǎn)A2對應(yīng)的最近邊界點(diǎn)的邊界序列號分別為 a1 和 a2。另外一個(gè)骨架種子點(diǎn) B1和最小配對點(diǎn) B2對應(yīng)的最近邊界點(diǎn)的邊界序列號分別為 b1 和 b2。骨架分支向外延伸（即向物體凸出部分延伸）時(shí)，如果在最小內(nèi)積值圖中能找到像 A1和 B1這樣的兩個(gè)骨架種子點(diǎn)，滿足邊界線段 b1b2 含在 a1 a2 邊界線段中，且邊界長度小于那么這兩個(gè)骨架點(diǎn)之間內(nèi)積值大于 0的最小內(nèi)積點(diǎn)都可以表示為骨架點(diǎn)，由這些點(diǎn)來連通兩個(gè)骨架種子。這個(gè)延伸處理可以得到物體凸起部分的骨架分支。

2.3 骨架內(nèi)連接過程

經(jīng)過以上兩個(gè)骨架連通處理步驟，使得物體的所有骨架分支連接到主骨架上后，最后得到的連通的骨架結(jié)構(gòu)如圖6所示：

圖6 MPEG7 圖形數(shù)據(jù)庫中鹿的骨架圖

3.算法試驗(yàn)結(jié)果

用本文的算法對MPEG7圖形數(shù)據(jù)庫的所有樣本進(jìn)行了骨架提取試驗(yàn)，試驗(yàn)時(shí)，我們用本文的算法和文獻(xiàn)[9]中的算法對 MPEG7 圖形數(shù)據(jù)庫中圖形進(jìn)行骨架提取，部分結(jié)果如圖7所示：

圖7 算法結(jié)果比較

在圖7中，左邊一列圖像是本文算法的提取結(jié)果，右邊一列是文獻(xiàn)[9]算法的提取結(jié)果。文獻(xiàn)[9]算法的提取結(jié)果雖然能很好地克服邊界噪聲對骨架的影響，但是也有物體局部特征遺漏現(xiàn)象，如圖6-2(b)所示；或有冗余骨架分支存在現(xiàn)象，如圖6-2(f)所示。試驗(yàn)結(jié)果表明用本文提出的算法提取物體的骨架結(jié)構(gòu)，不僅能很好地保留物體的整體骨架結(jié)構(gòu)，同時(shí)對物體的局部細(xì)節(jié)特征也能很好地描述。在表征物體的拓?fù)浣Y(jié)構(gòu)時(shí)，對于對象明顯的視覺特征部分都有對應(yīng)的骨架分支。

4 結(jié)論

本文研究了基于內(nèi)積的物體骨架提取算法，距離變換求出物體中的像素點(diǎn)所對應(yīng)的最近邊界向量，再通過相鄰邊界向量的方向找出可能的骨架點(diǎn)位置，通過內(nèi)積閾值確定骨架種子點(diǎn)，經(jīng)過對骨架種子點(diǎn)的向外延伸和向內(nèi)連接處理，得到連通的骨架。本文提出的算法具有簡單有效的特點(diǎn)，通過本文算法提取的骨架不僅完整，而且連通性也得到保證，能夠?yàn)楹罄m(xù)圖像處理提供物體的拓?fù)湫畔ⅰ?/p>

[1] Blum H., A Transformation for Extracting New Descriptors of Shape. Models for Perception of Speech and Visual Form[J], Cambridge: Data Sciences Laboratory, 1967, 45(18): 362-380.

[2] Lam L. and Lee S. W., Thinning Methodologies - a Comprehensive Survey[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14( 9): 869-885.

[3] Leymarie F. and Levine M. D., Simulating the Grassfire Transform Using an Active Contour Model[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(1): 56–75.

[4] Tang Y. Y. Skeletonization of Ribbon-like Shapes Based on a New Wavelet Function[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(9):1118–1133.

[5] Aurenhammer F.Voronoi Diagrams – A Survey of A Fundamental Geometric Data Structure[J], ACM Computing Surveys, 1991, 23(3): 345–405.

[6] Jang B. K. Analysis of Thinning Algorithms Using Mathematical Morphology[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990,12(6): 541-551.

[7] Ge Y. and Fitzpatrick J. M. On the Generation of Skeletons from Discrete Euclidean Distance Maps[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 18(11): 1055-1066.

[8] Choi W. P. Lam K. M. and Siu W. C., Extraction of the Euclidean Skeleton Based on a Connectivity Criterion[J], Pattern Recognition, 2003,l(36): 721–729.

[9] Bai X. and Latecki L. J. Skeleton Pruning by Contour Partitioning with Discrete Curve Evolution. [J]IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(3): 449-461.

A Euclidean Distance and Inner Production Based on Skeleton Extraction

Dai Lingzhen, Rong Ye, Shi Youqun
（School of Computer Science and Technology, Donghua University, Shanghai 201620, China）

In this paper, a skeleton calculation method is proposed. Distance transform is used to determine the nearest edge element for each pixel in a binary image. A vector from each pixel that stops at the nearest edge element is defined as edge vector. An inner-product for a pixel is calculated as the minimal value of the inner-products of edge vectors of the pixel and its 8 neighbor pixels. Seeds of the skeleton are determined by a threshold for the inner-product value. A well connected skeleton is obtained by growing calculation. It is demonstrated that the proposed algorithm produces a integrated and well connected skeleton that represents object’s topology.

Skeleton; Edge Vector; Inner Product; Distance Transform

TP 391.41

A

1007-757X(2014)02-0041-04

2013.11.10)

戴凌震（1987-）男，江蘇太倉人，東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，碩士研究生，研究方向：計(jì)算機(jī)圖像處理，上海，201620榮 曄（1985-）男，上海人，東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，碩士研究生，研究方向：計(jì)算機(jī)圖像處理，上海，201620史有群（1985-）男，東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，教授，研究方向：計(jì)算機(jī)圖像處理，上海，201620