郭邦梅,王 濤,趙 榮,梁 勇

(1.山東農(nóng)業(yè)大學信息科學與工程學院,山東泰安 271018;2.中國測繪科學研究院,北京 100830)

面狀要素骨架線提取算法的研究

郭邦梅1,2,王 濤2,趙 榮2,梁 勇1

(1.山東農(nóng)業(yè)大學信息科學與工程學院,山東泰安 271018;2.中國測繪科學研究院,北京 100830)

基于柵格數(shù)據(jù)的經(jīng)典細化算法獲得的骨架線會丟失一些重要特征點或特征線,且無法按照需求保持該要素細化后與周邊重要要素間的關(guān)聯(lián)性。在經(jīng)典細化算法的基礎(chǔ)上提出改進算法,克服已有算法的一些不足,使獲得的骨架線更能適應(yīng)具體應(yīng)用。試驗結(jié)果表明此改進算法能夠按照實際需求,更準確地保留原圖形的重要特征,且很好地保持了該要素與周邊重要要素間的關(guān)聯(lián)性。

經(jīng)典細化算法;骨架線;細化

一、引 言

所謂骨架(skeleton),是指用與原形狀連通性和拓撲結(jié)構(gòu)相一致的細曲線作為理想表達的一種對象表示[1]。骨架線是描述物體幾何及拓撲性質(zhì)的重要特征,在 GIS中有著廣泛的應(yīng)用。制圖綜合中,在研究河系結(jié)構(gòu)時,各有關(guān)內(nèi)部結(jié)構(gòu)如局部寬度變化、分叉等可忽略時,可以用河道骨架線來代表河流[2];地物注記的自動配置中,如對于大面積面狀要素,需先提取骨架線,將該骨架線作為注記的定位參考線[3];面狀地理現(xiàn)象的分析等很多空間操作中都需要提取骨架線。

本文以提取面狀要素骨架線及河流骨架線為例,分析不同的提取骨架線算法的優(yōu)劣,如杜世宏[4]等提出的基于柵格數(shù)據(jù)提取骨架線的新算法,該算法是利用柵格算法研究最長骨架線的提取,具有較快的處理速度且主要用來提取面狀要素的主骨架線。文獻[5]中,王濤提出顧及多因素的面狀目標多層次骨架線提取。類似對提取骨架線算法的研究較多,但都無法保證骨架線與其周邊重要線的連通性。其中經(jīng)典細化算法具有快速實用的特點,同時能保證細化后曲線的連通性且較簡單快捷,故本文以經(jīng)典細化算法為基礎(chǔ)來提取骨架線。經(jīng)典細化算法提取的骨架線基本保持了面狀要素的連通性,但是有些主要特征點或線并沒有保留下來。同時,在水系要素處理中,提取的面狀河流骨架線同樣也沒有保留與周邊重要支流間的連通性,這樣就破壞了該河流與周邊主要支流間的關(guān)聯(lián)性。

針對以上提出的經(jīng)典細化算法所存在的不足,本文提出了相應(yīng)的改進算法。并對利用改進后的細化算法得到的骨架線,與改進前的經(jīng)典算法及ArcGIS 9.2提供的細化工具提取的骨架線進行了對比分析。

二、現(xiàn)有細化算法及評析

1.提取骨架線算法

骨架線的提取方法通常有基于矢量數(shù)據(jù)和柵格數(shù)據(jù)兩種方法。其中基于矢量數(shù)據(jù)的代表性算法有平行線切割中點連線法及 Delaunay三角網(wǎng)法。平行線切割中點連線法是最簡單、最直觀的求取骨架線的方法,但是它只能處理一些簡單的多邊形,對于復雜的多邊形(如有島多邊形),處理起來比較困難。Delaunay三角網(wǎng)法具有很好的幾何特性,能夠方便地建立起各地理目標的空間鄰近關(guān)系,探測目標的結(jié)構(gòu)特征,有著較大的靈活性和可操作性。但由于自動綜合中建立的 Delaunay數(shù)據(jù)結(jié)構(gòu)要比一般Delaunay數(shù)據(jù)結(jié)構(gòu)復雜,因此工作量和計算量都比較大,對內(nèi)存操作頻繁,占用更多的計算機資源[6]。

基于柵格數(shù)據(jù)的方法大多使用數(shù)學形態(tài)學方法,主要經(jīng)過數(shù)學形態(tài)學的“序貫減薄”運算,選擇緊致的凸結(jié)構(gòu)元用逐次侵蝕與斷開運算形成一種骨架線算法。目前可歸納為兩大類：①基于距離變換,首先得到骨架像元,然后跟蹤距離變換圖中的“山脊線”(即在局部范圍內(nèi)灰度值最大的像元系列),并將其作為中軸線;②基于在不破壞柵格拓撲連通性的前提下,按對稱的原則刪除影像邊緣的柵格點[7]。此類算法主要有：用距離變換法搜尋中軸線法、最大數(shù)值計算法、經(jīng)典細化算法、邊緣跟蹤剝皮法。本文主要討論后一類中的經(jīng)典細化算法。

2.經(jīng)典細化算法

經(jīng)典細化算法的基本原理是：通過逐個考察某一像素 P的八個領(lǐng)域灰度值的分布格局,在不破壞原柵格影像拓撲連通性的情況下刪除該點,反之保留。這樣逐點掃描,消去所有不破壞連通性的點,直到點陣圖中不再有可刪除的點為止。

設(shè)已知目標點標記為 1,背景點標記為 0。算法對標記為 1的像元點進行了如下操作：考慮以某一像元點為中心的八個領(lǐng)域,記中心點為 P,其領(lǐng)域的八個點順時針繞中心點分別記為 P1、P2、P3、P4、P5、P6、P7、P8,其中 P1在 P的上方 (如圖 1所示)。將標記滿足下列任意一個條件的中心像元點保留。

圖1 像元P八領(lǐng)域示意圖

1)P1+P3+P5+P7=4且 P2+P4+P6+P8= 0(或 4);

2)P3+P7=0且 P1+P2+P8＞0且 P4+P5+ P6＞0;

3)P1+P5=0且 P2+P3+P4＞0且 P6+P7+ P8＞0;

4)P1+P3=0且 P2=1且 P4+P5+P6+P7+ P8＞0;

5)P3+P5=0且 P4=1且 P1+P2+P6+P7+ P8＞0;

6)P5+P7=0且 P6=1且 P1+P2+P3+P4+ P8＞0;

7)P7+P1=0且 P8=1且 P2+P3+P4+P5+ P6＞0。

需要注意的是,以上條件實際上是給出的連通性條件,如果簡單地將它們依次用于一幅圖像,那么一個連通區(qū)域的像元灰度值都將變?yōu)?0。因此對于某一方向的細化來說,中心像元的取舍決定,不能立即表現(xiàn)為物理上去除或保留,而應(yīng)先將中心像元 P置為 2(表示此點為中軸線上的像元)或 3(表示此為可刪除的像元),以免破壞原始影像的結(jié)構(gòu)。

依次迭代以上操作,直至沒有點可被刪除,這時剩下的點組成面的骨架線。

三、算法的改進

利用經(jīng)典細化算法提取面狀要素的骨架線,會出現(xiàn)很多重要特征點及線都沒有提取出來的情況,如圖 2中黑色圓圈標出的地方。下面對經(jīng)典算法作相應(yīng)的改進,以解決該問題。

圖 2 改進前得到的骨架線與原圖的疊加圖

1.保證骨架線完整性的改進

第二部分第 2節(jié)中已經(jīng)提到過,經(jīng)典算法中的七個條件實際上是給出的連通性條件,通過多次試驗發(fā)現(xiàn),這七個條件中的 2)和 3)是用來保證上下方向的連通性。由此可想到將經(jīng)典算法中的條件2)放寬,改為 P3+P7=0且 P1+P2+P8＞0或P4+ P5+P6＞0。圖 3為原柵格面狀要素,圖 4為對第二個條件作修改后所得到的骨架線與原圖的疊加圖,與圖 2改進前所得到的骨架線與原圖的疊加圖相比,可以發(fā)現(xiàn)保留了更多的重要支線與點,圖中黑色圓圈已標出。

圖3 原柵格面狀圖

圖 4 改進條件 2)后所得骨架線與原圖的疊加圖

同理,將條件 3)改為 P1+P5=0且 P2+P3+ P4＞0或 P6+P7+P8＞0,所得到的骨架線見圖 5,很明顯比圖 2保留了更多的特征線或點,但保留要素有些不同。

圖 5 改進條件 3)后所得骨架線與原圖的疊加圖

將條件 2)和 3)同時改進可得到圖 6,保留了更多的骨架支線和特征點。由此可以看出通過這樣的改進后,提取的骨架線更能比較詳細地反映面狀要素的基本特征。

圖 6 同時改變條件 2)和 3)所得骨架線

圖 7是利用ArcGIS軟件中的 Thin細化工具所得到的面狀要素骨架圖與原圖的疊加圖,可以明顯看出,骨架線不是很平滑,會產(chǎn)生一些抖動現(xiàn)象且很多支線或重要點被刪除。相比而言,通過對經(jīng)典細化算法改進后所得到的骨架線,更能比較詳細地反映面狀要素的形狀特征,且無抖動現(xiàn)象。

圖 7 通過ArcGIS 9.2提取的骨架線

2.保證線、面連通性的優(yōu)化

在制圖綜合中,時常會通過提取河流骨架線來作雙線河到單線河的轉(zhuǎn)變。圖 8為某條河流及它周邊的一條支流,圖 9是對圖 8中黑色方格處的放大圖,從圖 9可以看出,提取該河流的骨架線時,在保證河流與周邊支流間的獨立性的同時,必須保持該河流的骨架線與其周邊支流間的關(guān)聯(lián)性。而利用經(jīng)典細化算法提取該河流的骨架線時,無法實現(xiàn)與特定支流間的連通性,從圖 10中可以看出提取的骨架線與支流沒有任何連接,破壞了該河流與支流間的關(guān)聯(lián)性。對于這個問題,可以通過對原始數(shù)據(jù)進行預(yù)處理來解決。

圖8 河流柵格圖

圖 9 對圖 8中黑色方格處的放大圖

圖 10 未改進時所得骨架線與原圖的疊加圖

首先對原始數(shù)據(jù)進行掃描,找出該河流與支流的相交點并將該交點的像素值改為其他值,此試驗中原像素值為 1,將其改為 2。圖 11即為運用此改進后的經(jīng)典算法提取河流的骨架線與原圖的疊加圖,該圖方框中標出的線即為強制保留的骨架線,與圖 10改進前提取的骨架線與原圖的疊加圖比較,可以發(fā)現(xiàn)經(jīng)過改進后的經(jīng)典算法能夠很好地保持骨架線與其周邊重要要素間的關(guān)聯(lián)性。

圖 11 改進后所得骨架線與原圖的疊加圖

四、結(jié)束語

不同的應(yīng)用目標,對細化結(jié)果的要求不同。從試驗結(jié)果可以看出,利用改進后的算法所得到的結(jié)果比較符合實際需要,在提取骨架線的同時保留了必要特征點,既實現(xiàn)了骨架線的連通性,同時也保持了與其他要素之間的關(guān)聯(lián)性。經(jīng)總結(jié)改進后的經(jīng)典細化算法有以下優(yōu)點：①通過修改經(jīng)典算法的基本規(guī)則,使得骨架線可以延伸至面狀目標邊界,保證了骨架線的完整性;②通過改變線狀要素與周邊其他要素間的交點像素值,保留了它們之間的連通性;③最大限度地消除冗余數(shù)據(jù)的同時,根據(jù)需要提取線狀要素的骨架線,具有較強的靈活性和實用性。

[1] 車武軍,楊勛年,汪國昭.動態(tài)骨架算法 [J].軟件學報,2003,14(4)：818-823.

[2] 毋河海.地圖綜合基礎(chǔ)理論與技術(shù)方法研究[M].北京：測繪出版社,2004.

[3] 樊紅.地圖注記自動配置的研究[M].北京：測繪出版社,2004.

[4] 杜世宏,杜道生,樊紅,等.基于柵格數(shù)據(jù)提取主骨架線的新算法 [J].武漢測繪科技大學學報,2000,25 (5)：432-436.

[5] 王濤,毋河海.顧及多因素的面狀目標多層次骨架線提取[J].武漢大學學報：信息科學版,2004,29(6)：533-536.

[6] 艾廷華,郭仁忠.支持地圖綜合的面狀目標約束Delaunay三角網(wǎng)剖分[J].武漢測繪科技大學學報,2000,25 (1)：35-41.

[7] 張宏,溫永寧,劉愛利,等.地理信息系統(tǒng)算法基礎(chǔ)[M].北京：科學出版社,2006：80-82.

[8] 喬慶華,吳凡.河流中軸線提取方法研究[J].測繪通報,2004(5)：14-17.

[9] ZHANG T Y,SUEN C Y.A Fast Parallel Algorithm for Thinning Digital Patterns[J]. Image Processing and ComputerVision,1984,27(3)：236-239.

[10] 杜瑞穎,劉鏡年.面狀地物名稱注記的自動配置研究

[J].測繪學報,1999,28(4)：365-368.

Research on Algorithm of Polygon Skeleton L ine Extracting

GUO Bangmei,WANG Tao,ZHAO Rong,L IANG Yong

0494-0911(2010)12-0017-03

P208

B

2010-01-26

國家863計劃項目

郭邦梅(1986—),女,青海互助人,碩士生,主要研究方向為地圖制圖學與地理信息工程。