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

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

2、unay 三角網(wǎng);骨架;中圖分類號(hào): TP391 文獻(xiàn)標(biāo)識(shí)碼: 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基金項(xiàng)目:邯鄲市科技攻關(guān)項(xiàng)目(200510301-30 引 言骨架是圖像幾何形態(tài)的一種重要的拓?fù)涿枋?由一些表明物體大致形狀的細(xì)線組成。利用骨架表示原始圖像,可以在保持圖像重要拓?fù)涮卣鞯那疤嵯?減少圖像中的冗余信息。因此,骨架提取算法被廣泛應(yīng)用于生物形狀描述、模式識(shí)別、視覺檢測(cè)以及圖像壓縮編碼等領(lǐng)域。骨架一般應(yīng)具有以下性

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

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

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

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

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

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

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

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

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

14、果如圖3所示。說明本算法簡(jiǎn)單、高效,具有 很強(qiáng)的實(shí)用性和優(yōu)越性。圖3 提取骨架線效果4 結(jié) 語數(shù)學(xué)形態(tài)學(xué)在國(guó)外已被實(shí)際應(yīng)用于機(jī)器視覺、模式識(shí)別、圖像處理等領(lǐng)域。目前國(guó)內(nèi)也有不少學(xué)者研究了基于經(jīng)典形態(tài)學(xué)的骨架提取算法,獲得了較好的結(jié)果。本文研究的骨架提取算法,是經(jīng)典數(shù)學(xué)形態(tài)學(xué)骨架提取方法的拓廣和改進(jìn),因此有著廣泛的應(yīng)用前景。參考文獻(xiàn):1 嚴(yán)濤.基于圖像的樹木造型方法的研究D.中國(guó)科學(xué)院軟件研究所,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: