莊彩云，熊平

中南大學(xué)地球科學(xué)與信息物理學(xué)院，長(zhǎng)沙 410083

基于近似最小距離場(chǎng)的二維圖像骨架提取方法

莊彩云，熊平

中南大學(xué)地球科學(xué)與信息物理學(xué)院，長(zhǎng)沙 410083

自1967年Blum[1]提出中軸的概念以來，骨架（skeletons）已經(jīng)成為表示和識(shí)別物體的重要手段之一，骨架組合了目標(biāo)的輪廓和區(qū)域信息，反映了目標(biāo)的重要視覺線索，因而，基于骨架的目標(biāo)表示和識(shí)別技術(shù)成為模式識(shí)別和計(jì)算機(jī)視覺的重要研究?jī)?nèi)容[2]。骨架是一種形狀特征，是由一些細(xì)（或者比較細(xì)）的弧線和曲線集合構(gòu)成的原始形狀的一個(gè)表示，這些弧線和曲線能夠保持原始形狀的相連性[3]。因此骨架必須滿足三個(gè)基本要求：（1）中心性；（2）連通性；（3）細(xì)化性。

現(xiàn)有的離散域骨架算法主要分為三類：一是拓?fù)浼?xì)化方法[4]，其本質(zhì)是一層一層地迭代地剝掉邊界，從而識(shí)別單一點(diǎn)，邊界的移除不影響對(duì)象的拓?fù)湫?。此方法得到的骨架可保證連通性。但對(duì)邊界噪聲非常敏感，容易產(chǎn)生冗余的分支，且骨架的位置不是準(zhǔn)確地靠近物體的中心。二是基于距離變換的方法[5]，通過尋找距離梯度脊線來形成骨架，此類方法得到的骨架位置精確，但難以保證骨架的連通性。本文屬于這種方法。三是基于Voronoi圖的方法[6]，Voronoi圖是中軸的包集，生成的骨架需要剪枝，且復(fù)雜度很高。

理想的基于距離變換的方法包括三個(gè)步驟：（1）生成對(duì)象的最小距離場(chǎng)。（2）根據(jù)距離場(chǎng)檢測(cè)所有的局部最大值以生成中心聚類。這樣，對(duì)象就是聚類的集合，而不是像素的集合。（3）連接聚類以生成骨架。對(duì)于骨架，最先要考慮的是中心性問題。理論上講，點(diǎn)的歐氏距離提供了一個(gè)點(diǎn)是否為中心點(diǎn)的足夠信息；然而，真正計(jì)算歐氏距離代價(jià)很高。計(jì)算機(jī)視覺中有許多離散的模擬方法，即，距離變換矩陣。在2D圖像中，使用較廣泛的是在“2-3”[7]或“3-4”[8]。這些距離變換矩陣大大縮減了計(jì)算時(shí)間。然而，基于距離變換的方法難以保證連通性。Niblack等[9]提出了解決這一問題的方法。為了通過使用爬坡規(guī)則（uphill climbing rules）連接局部最大值，他們?cè)诠羌茳c(diǎn)集中增加鞍點(diǎn)（沿骨架的局部最小值）。Helman和Hesselink[10]通過計(jì)算2D向量場(chǎng)地的Jacobian矩陣的特征值檢測(cè)該2D向量中的鞍點(diǎn)。在這種距離中，鞍點(diǎn)的精確性取決于從距離變換生成的向量場(chǎng)的精確性。而因?yàn)榘包c(diǎn)的檢測(cè)只考慮了距離變換的局部分布，所以這兩種方法本質(zhì)上都是很敏感的。在圖像中，噪聲、復(fù)雜的數(shù)據(jù)可能使很多像素都成為鞍點(diǎn)，從而導(dǎo)致了把不正確的路徑也當(dāng)做骨架的一部分，或者導(dǎo)致骨架非常粗。

Voronoi方法[6，11]理論上講，確保得到了骨架的連通性，這特別適合于多邊形定義的對(duì)象。然而，真正的圖像如CΤ、MRI通常具有大量的數(shù)據(jù)和噪聲，這將導(dǎo)致Voronoi圖密度很大，且計(jì)算代價(jià)高。

到目前為止，還沒有一種算法應(yīng)用在普通圖像上時(shí)能同時(shí)滿足精確性和時(shí)間性能的要求。Voronoi方法能夠產(chǎn)生很好的效果，但計(jì)算時(shí)間長(zhǎng)。拓?fù)浼?xì)化方法比Voronoi方法快，但精確性沒Voronoi方法好。距離變換方法性能最好，但執(zhí)行比較困難，并且通常不能保持連通性。連通步驟（或者如何連接所有聚類的步驟）也是最難的步驟，許多作者已經(jīng)提出解決的算法，但結(jié)果不是太復(fù)雜就是效率低。本文提出了簡(jiǎn)單且高效的算法以解決這一問題。

1 基于近似最小距離場(chǎng)的二維圖像骨架提取算法

本文提出的算法屬于骨架提取常用方法中的第二類，即采用歐氏變換的離散編碼方法。除了上文提到的骨架的三個(gè)基本條件，本文中還考慮了骨架的其他特征：

（1）直接計(jì)算性，這一條件是為了加速計(jì)算過程；

（2）可處理各種類型的圖像；

（3）對(duì)對(duì)象的邊界復(fù)雜性不敏感；

（4）可視化。

算法主要包括四個(gè)步驟：（1）計(jì)算近似最小距離場(chǎng)；（2）基于近似最小距離場(chǎng)生成聚類；（3）細(xì)化聚類；（4）連接細(xì)化后的聚類。

1.1 計(jì)算近似最小距離場(chǎng)

在2D二值化圖像中，兩個(gè)像素Pi和Pj，如果Pi和Pj共享邊（edge），則稱Pi和Pj是E-連通的，且Pj是Pi的E-鄰居。一個(gè)給定的像素有4個(gè)E-鄰接的像素。F-連通與傳統(tǒng)的4-連通相對(duì)應(yīng)。

計(jì)算近似最小距離場(chǎng)的方法如下：檢測(cè)對(duì)象的邊界，將邊界像素賦值為1，邊界像素的E-連通的像素賦值為2，值為2的像素的E-連通的像素賦值為3，以此類推。假設(shè)一個(gè)像素的值為n，則其E-連通的像素值賦值為n+1。如圖所示，圖2是圖1的近似最小距離場(chǎng)。

圖1 實(shí)驗(yàn)圖像

圖2 近似最小距離場(chǎng)

這種方法計(jì)算的距離的準(zhǔn)確性雖然沒有“2-3”距離變換矩陣或其他方法計(jì)算的距離高，但當(dāng)處理大量像素時(shí)，少量像素有誤差并不影響整個(gè)結(jié)果，卻大大減少了運(yùn)行時(shí)間。

1.2 基于近似最小距離場(chǎng)生成聚類

定義1局部最大像素（local maximum pixel）是指距離值不小于其所有E-鄰居的距離值的像素，如圖3所示。

圖3 局部最大像素

定義2聚類（cluster）是指一組具有相同距離值的E-連通的局部最大體素，如圖4所示。

圖4 聚類

根據(jù)定義1和定義2生成聚類。這一步驟保證了骨架的中心性要求。

1.3 細(xì)化聚類

細(xì)化的原則是除了端點(diǎn)像素，其他像素都只能有兩個(gè)鄰居，且該兩個(gè)鄰居不連接。這一過程保證了骨架應(yīng)盡可能細(xì)的要求。

1.4 連接細(xì)化后的聚類

定義3最短路徑（the shortest path）P≡{pi|i=1→n}是一序列像素pi使得：

（1）每個(gè)pi至少有一個(gè)E-鄰居的距離值大于pi的距離值；

（2）像素p1和pn僅有一個(gè)鄰居，它們是路徑的兩端，像素pi(1〈i〈n)僅有兩個(gè)鄰居；

（3）pi和pi+1是連通的，pi和pi+2是不連通的。

使用最短路徑連接兩個(gè)分離的細(xì)化后的聚類的方法：用連續(xù)數(shù)字#1、#2等標(biāo)記不同的聚類。從聚類#1開始，對(duì)聚類#1進(jìn)行膨脹，使聚類#1膨脹至接觸到下一個(gè)鄰近的聚類#2。再使用最短路徑連接這兩個(gè)接觸的聚類#1和#2，然后用較大聚類的數(shù)字命名新連接的聚類。這一過程如圖5所示。以此方法，將所有的聚類連接起來。因?yàn)楸疚乃脤?shí)驗(yàn)圖像生成的聚類有10個(gè)（如圖6（d）所示），因此用大于數(shù)字#10的連續(xù)數(shù)字#11、#12等來膨脹聚類，以避免聚類和非聚類的混淆。

2 實(shí)驗(yàn)驗(yàn)證

將本文提出的算法進(jìn)行測(cè)試，并與拓?fù)浼?xì)化方法進(jìn)行比較，實(shí)驗(yàn)環(huán)境為Pentium Dual-Core CPUΤ4400@2.2 GHz 2.19 GHz，1.99 GB的內(nèi)存；軟件為matlab7.0，輸入圖像大小為256像素×256像素。

2.1 實(shí)驗(yàn)步驟

具體實(shí)驗(yàn)步驟如下：

（1）首先對(duì)圖像進(jìn)行二值化預(yù)處理，圖6（a）是二值化后的圖像。

（2）確定對(duì)象的最小距離場(chǎng)，如圖6（b）所示。

（3）基于步驟（2）確定的最小距離場(chǎng)生成聚類，用#1標(biāo)記，如圖6（c）所示。

（4）優(yōu)化第（3）步生成的聚類，使其盡可能細(xì)化，將細(xì)化后的各個(gè)聚類用數(shù)字#1、#2等標(biāo)記，如圖6（d）所示。

圖5 細(xì)化后的聚類的連接

圖6 骨架的提取過程

（5）以1.4節(jié)描述的方法連接所有聚類以生成骨架，并顯示骨架，如圖6（e）所示。

2.2 算法比較

將本文的算法與拓?fù)浼?xì)化方法進(jìn)行比較。拓?fù)浼?xì)化方法是目前比較常用的方法，而且該算法比較成熟，其本質(zhì)是一層一層地迭代地剝掉邊界，從而識(shí)別單一點(diǎn)，邊界的移除不影響對(duì)象的拓?fù)湫裕軌虼_保骨架的連通性[4]。采用拓?fù)浼?xì)化方法得到的結(jié)果如圖7（a）所示，本文算法得到的結(jié)果如圖7（b）所示。兩種算法的運(yùn)行時(shí)間如表1所示。

圖7 算法比較

表1 兩種算法的運(yùn)行時(shí)間比較s

3 結(jié)果討論

由圖7（a）可以看出拓?fù)浼?xì)化方法對(duì)邊界噪聲非常敏感，產(chǎn)生許多冗余的分支，且骨架的位置不是準(zhǔn)確地靠近物體的中心；圖7（b）為本文算法提取的骨架，由圖中看出該骨架較好地保持了對(duì)象的主要拓?fù)浣Y(jié)構(gòu)，準(zhǔn)確得到物體的骨架，且對(duì)邊界噪聲不敏感。而且，在相同環(huán)境下，拓?fù)浼?xì)化算法所用時(shí)間為2.099 s，本文算法所用時(shí)間為1.522 s，提高了骨架提取算法的效率。

4 結(jié)論

本文提出了一種基于近似最小距離場(chǎng)提取二值圖像的8-連通骨架的算法。該算法對(duì)圖像中的每個(gè)像素根據(jù)其與邊界的相對(duì)距離進(jìn)行整數(shù)編碼，形成近似最小距離場(chǎng)，并將該距離場(chǎng)中的幾何鄰接的、具有局部最大值的像素形成聚類，然后對(duì)聚類進(jìn)行細(xì)化，并用最短路徑將不同的細(xì)化后的聚類連接起來。該算法相對(duì)于目前常用的骨架提取算法原理簡(jiǎn)單，對(duì)邊界噪聲不敏感，既保證了骨架的連通性，生成準(zhǔn)確的骨架，且提高了骨架提取算法的效率，為圖像骨架提取提供了一種行之有效的解決方法。

[1]Blum H.Biological shape and visual science（Part 1）[J].Journal of Τheoretical Biology，1973，38（2）：205-287.

[2]王松偉，李言俊，張科，等.一種快速的目標(biāo)骨架提取算法[J].紅外與激光工程，2009，38（4）：731-736.

[3]Lam L，Lee S W，Suen C Y.Τhinning methodologies：a comprehensive survey[J].IEEE Τrans on Anal Mach Intell，1992，14：869-885.

[4]Ogniewicz R L.Hierarchic Voronoi skeletons[J].Pattern Recognition，1995，28（3）：343-359.

[5]August J，Siddiqi K，Zucker S W.Ligature instabilities in the perceptual organization of shape[J].Computer Vision and Image Understanding，1999，76（3）：231-243.

[6]丁頤.基于距離變換的層次連接骨架化算法[J].紅外與毫米波學(xué)報(bào)，2005，24（4）：28l-285.

[7]Malandain G，F(xiàn)ernandze V S.Euclidean skeletons[J].Image and Vision Computing，1998，16（5）：317-327.

[8]Borgefors G.Distance transformations on digital images[J]. Computer Vision Graph Image Processing，1986，34：344-371.

[9]Niblack C W，Gibbons P B，Capson D W.Generating Skeletons and centerlines from the distance transform[J].Graph Models Image Processing，1992，54：420-437.

[10]Brandt J W，Algazi V R.Continuous skeleton computation by Voronoi diagram[J].Image Understanding，1992，55：329-338.

[11]Saito Τ，Τoriwaki J I.New algorithms for euclidean distance transformation of an n-dimensional digitized picture with applications[J].Patt Recogn，1994，27：1551-1565.

ZHUANG Caiyun,XIONG Ping

School of Geosciences and Info-Physics,Central South University,Changsha 410083,China

Τhis paper proposes an algorithm for extracting 8-connected skeletons of 2D binary images.Each interior pixel in the 2D image is encoded with an integer code according to its relative distance from the object border to form an approximate minimum distance field.Cluster is defined as a set of geometrically connected local maximum pixels with the same distance value.And all the clusters are thinned,and connected with the shortest paths.Τhe proposed algorithm is simple,and the results acquired by the algorithm on an experimental data demonstrate its efficiency.

approximate minimum distance field;2D binary image;pixel encoding;cluster;shortest path

提出了基于近似最小距離場(chǎng)提取二值圖像的8-連通骨架的算法。該算法對(duì)圖像中的每個(gè)像素根據(jù)其與邊界的相對(duì)距離進(jìn)行整數(shù)編碼，形成近似最小距離場(chǎng)，將該距離場(chǎng)中的幾何鄰接的、具有局部最大值的像素形成聚類，對(duì)聚類進(jìn)行細(xì)化，用最短路徑將不同的細(xì)化后的聚類連接起來。該算法簡(jiǎn)單，將其在實(shí)驗(yàn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果證明算法具有很高的效率。

近似最小距離場(chǎng)；2D二值圖像；像素編碼；聚類；最短路徑

A

ΤP391.41

10.3778/j.issn.1002-8331.1201-0222

ZHUANG Caiyun,XIONG Ping.2D image skeleton generation based on approximate minimum distance field.Computer Engineering and Applications,2013,49（21）：164-167.

國(guó)家自然科學(xué)基金（No.30371626）。

莊彩云（1985—），女，碩士研究生，主要研究方向：醫(yī)學(xué)圖像處理；熊平（1959—），通訊作者，男，教授，碩士生導(dǎo)師，主要研究方向：腫瘤物理靶向定位治療。E-mail：178511165@qq.com

2012-01-13

2012-03-05

1002-8331（2013）21-0164-04

CNKI出版日期：2012-06-01http://www.cnki.net/kcms/detail/11.2127.ΤP.20120601.1457.022.html