基于Delaunay三角網(wǎng)的骨架提取算法研究_圖文

1、第28卷第4期2006年8月艦 船 科 學 技 術SH I P SC I E NCE AND TEC HNOLOGY Vo.l 28,No .4Aug .,2006文章編號:1672-7649(200604-0106-03基于Delaunay 三角網(wǎng)的骨架提取算法研究倪 健1,董 強2(1.河北工程大學,河北邯鄲056038;2.中國船舶重工集團公司第七一八研究所,河北邯鄲056027摘 要: 對目標圖像提取其骨架,在目標檢測、圖像編碼等計算機視覺、圖像處理與模式識別領域有著廣泛的應用。本文提出了一種基于D elaunay 三角網(wǎng)的骨架提取改進算法,給出了實驗效果。關鍵詞: 圖像處理;Dela

2、unay 三角網(wǎng);骨架;中圖分類號: TP391 文獻標識碼: AThe research of skeletonization algorith m based on D elaunay triangulationN I Jian 1,DONG Q iang2(1.H ebeiUn i v ersity of Eng i n eer i n g ,H andan 056038,Ch i n a ;2.The 718Research Institute of CSI C ,H andan 056027,ChinaAbst ract : The ske leton o f ob ject i m

3、 age is ex tracted have been app lied to co m puter v ision ,i m age processi n g and patter n recogn iti o n inc l u cling ob j e ct detection ,i m age code et a1.Th is paper presents a ne w ske l eton ization algo rithm based on de launay triangulati o n ,an experi m ent is g iven to de m onstrate

4、 t h e effecti v eness of t h e a l g orit h m here .K ey w ords : i m age processi n g ;De launay triangu lation ;ske leton收稿日期:2006-06-21基金項目:邯鄲市科技攻關項目(200510301-30 引 言骨架是圖像幾何形態(tài)的一種重要的拓撲描述,由一些表明物體大致形狀的細線組成。利用骨架表示原始圖像,可以在保持圖像重要拓撲特征的前提下,減少圖像中的冗余信息。因此,骨架提取算法被廣泛應用于生物形狀描述、模式識別、視覺檢測以及圖像壓縮編碼等領域。骨架一般應具有以下性

5、質1:(1骨架寬度應為一個像素;(2骨架要盡可能穿過物體的 中部 ;(3骨架應保持物體的拓撲架構。近年來人們提出了很多骨架化算法,本文根據(jù)Delaunay 三角網(wǎng)思想改進了骨架線提取算法,即采用較為簡單的三角形切割方法得到運動人體骨架線,有效地區(qū)分了輪廓內(nèi)部和外部,壓縮了信息,更利于后期處理。1 基于數(shù)學形態(tài)學的骨架提取方法數(shù)學形態(tài)學以圖像的形態(tài)特征為研究對象,它的主要內(nèi)容是設計一整套概念、變換和算法,用來描述圖像的基本特征和基本結構,也就是描述圖像中的元素與元素、部分與部分間的關系。數(shù)學形態(tài)學的數(shù)學基礎和所用語言是集合論,它把圖像看成是點的集合。數(shù)學形態(tài)學的長處在于能定量地描述幾何結構,應用

6、數(shù)學形態(tài)學可以簡化圖像的數(shù)據(jù),但仍保持他們的基本形狀特征2。生成圖像中一個物體骨架的一種方法可通過沿某方向反復刪除物體內(nèi)、外輪廓線上的像素來完成。這里假定處理的圖像為二值圖像,稱輪廓線上的點為 邊緣點 ,在下面的討論中假設背景為黑色(0,前景(人體為白色(1,物體表現(xiàn)為圖像平面上第一個8連通區(qū)域。被處理點及其相鄰像素構成一個3!3第4期倪 健,等:基于Delaunay 三角網(wǎng)的骨架提取算法研究的區(qū)域。若一個位置的值為1則稱其為白色,否則稱黑點。若從一個位置出發(fā)到達另一位置所經(jīng)過的路徑均為白點,則稱2個位置是連通的。骨架抽取的算法思想雖然較為簡單,即反復地沿著某一方向刪除物體的內(nèi)、外輪廓上的邊緣

7、點,直到滿足骨架性質為止,但實現(xiàn)起來卻有許多細節(jié)要特別注意。算法的任何不完備都將直接導致抽取的失敗。2 通過De launay 三角網(wǎng)得出骨架多邊形骨架線提取的關鍵在于探測多邊形內(nèi)部到邊界線上的等距離點集,在幾何特征上屬于空間鄰近關系的探測問題,而計算幾何中的De launay 三角網(wǎng)是一種較成熟的支持模型3,具有其他算法模型無可比擬的優(yōu)勢。2.1 多邊形內(nèi)部約束Delaunay 三角網(wǎng)構架4計算幾何研究的Delaunay 三角網(wǎng)從數(shù)學理論出發(fā),嚴格符合Delaunay 三角網(wǎng)的性質定義。當應用到實際領域時,需針對其特殊性對算法進行改進。當多邊形目標以群點角色直接構建三角網(wǎng)時,在多邊形覆蓋區(qū)域

8、以邊界離散點為運算對象建立約束Delaunay 三角網(wǎng),約束條件為三角形不能穿越多邊形的邊界。對多邊形內(nèi)部的三角形,根據(jù)鄰接三角形的數(shù)目,進一步細分為三類:類三角形是三角網(wǎng)中的邊界節(jié)點,其3個頂點中有一個頂點作為骨架線的端點;#類三角形是三角網(wǎng)中的跨接三角形,是骨架線的骨干結構,描述了骨架線的延展方向;類三角形作為骨架分支的交匯處,是向3方向伸展的出發(fā)點。2.2 三角網(wǎng)條件序貫遍歷及骨架線樹結構的建立對于骨架線的提取,可仿照柵格結構中的擴張算子來設計三角網(wǎng)結構中的擴張算子。由于De launay 三角網(wǎng)在幾何特征上具有最鄰近連接的特點,三角形的邊可以看作是多邊形邊界上的一點到其他邊界點的鄰近跨

9、接,三角形跨接邊的中點可以認為是多邊形在該局部區(qū)域的片斷中心。將鄰接的1批三角形跨接邊的中點順序連接起來,便可以反映多邊形在一維特征上的延展趨勢,即骨架線。其具體的算法思想如下:首先,建立2個集合,即遍歷三角形集TR I和分支三角形集BRANC H ,分別用來順序記錄遍歷的所有三角形和順序記錄遍歷的所有分支三角形(即類三角形。由任意一個類三角形出發(fā),將這個三角形放入BRANC H 集合中,同時沿三角形三邊方向進入鄰接的三角形5。 (1如果當前考察的三角形是#類三角形,則繼續(xù)行進的方向就是惟一的,只需將該三角形放入TR I集合中;(2如果當前考察的三角形是類三角形,則繼續(xù)行進的方向就有2個,這樣

10、的分支三角形既要放入TR I集合中,同時也要放入BRANC H 棧結構中,然后繼續(xù)遍歷;(3如果當前考察的三角形是類三角形,那么表示這個三角網(wǎng)的一個分支已經(jīng)遍歷完成,將該三角形放入TRI集合中。重復上述過程,考察BRANCH 棧是否為空,如果棧非空,則取出棧頂?shù)娜切?直至BRANCH 棧中元素為空,三角網(wǎng)遍歷結束,得到三角網(wǎng)中所有三角形元素之間的二叉樹結構。圖1(a表達了三角網(wǎng)內(nèi)的遍歷過程;圖1(b為記錄對應的二叉樹結構。二叉樹的葉子節(jié)點對應著多邊形骨架線的一個端點,其他節(jié)點對應著多邊形骨架線的分支節(jié)點,節(jié)點之間的層次關系則描述了骨架線的主干與分支間的嵌套結構。圖1 記錄三角網(wǎng)遍歷過程的二叉

11、樹結構2.3 主骨架線的提取上述方法得到的骨架線是二叉樹結構,而主骨架線是沿著主延伸方向的線性結構。為此,還需要對按照上述方法提取的骨架線做出取舍,以提取惟一確定的主骨架線。圖2描述了骨架線某個分支處的情況。從圖2(a可以看到,多邊形的骨架線在 P 1P 2P 3處產(chǎn)生分叉,是典型的二叉樹結構。根據(jù)Gesta lt 連續(xù)性原則,為了保持人們視覺上的連續(xù)性和完整性,較為粗壯的R 分支應作為主延展方向。這樣,L 分支被裁減,得到圖2(b中惟一確定的多邊形延展方向?；谏鲜龅姆治?對主骨架線的提取方法如下。在骨架線分支處,以分支部分的面積作為選取標準,舍棄面積較小的分支,保留面積較大的分支,直至終止

12、于多邊形的2個節(jié)點,得到主骨架線。對于圖1%107%艦 船 科 學 技 術第28 卷圖2 消減分支示意圖(a中的多邊形而言,主骨架線上的節(jié)點依次為L& A&B&C&H(即被虛線圈住的部分,得到的多邊形主骨架線即為圖1(b中加粗的線段。從圖1可以看到,得到的主骨架線可以反映出該多邊形的形態(tài)特征和主延伸方向。多邊形的形狀分析是屬于空間認知的問題,也是一個不確定性問題。這里選取圖2中R分支的依據(jù)是因為R分支更加粗壯,即R分支的面積比L分支的面積要大。換言之,是將分支部分的面積作為選取標準。這是因為在視覺認知中,吸引注意力的是圖形的主體。選取標準要根據(jù)具體需求來確定,并不是惟一的。同時,如果各部分面積

13、勢均力敵,也會難以做出確定的選擇,這說明,主骨架線只能針對線性結構延展十分明顯的多邊形,對于像圓形、五角星形等均勻分布的多邊形,談論主骨架線是沒有意義的。3 本文采用的骨架線提取方法由于De launay三角形方法無法區(qū)分輪廓內(nèi)部還是外部,因此本文在此思想的基礎上采用了一種按逆時針遍歷輪廓,找到最小的夾角,取對應兩邊的中線點,切割三角形,刪除這個夾角點,繼續(xù)遞歸,直到多邊形為三角形為止的方法。對于中線點的連接,是采用記錄被切割的三角形,在回復骨架時按照遞歸的方法尋找鄰邊三角形。其中,依據(jù)點與三角形內(nèi)角和為360來判斷某點是否在被切割三角形內(nèi)。 用本文提出的骨架線算法,可得到各關鍵幀的骨架,其效

14、果如圖3所示。說明本算法簡單、高效,具有 很強的實用性和優(yōu)越性。圖3 提取骨架線效果4 結 語數(shù)學形態(tài)學在國外已被實際應用于機器視覺、模式識別、圖像處理等領域。目前國內(nèi)也有不少學者研究了基于經(jīng)典形態(tài)學的骨架提取算法,獲得了較好的結果。本文研究的骨架提取算法,是經(jīng)典數(shù)學形態(tài)學骨架提取方法的拓廣和改進,因此有著廣泛的應用前景。參考文獻:1 嚴濤.基于圖像的樹木造型方法的研究D.中國科學院軟件研究所,2000.2 BLO C H I.M a itre Fuzzy m athe m atical m orpholog i es:acomparati ve studyJ.P attem R ecogn iti on,1995,28(9: