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

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

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

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

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

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

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

經典細化算法;骨架線;細化

一、引 言

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

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

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

二、現有細化算法及評析

1.提取骨架線算法

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

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

2.經典細化算法

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

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

圖1 像元P八領域示意圖

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。

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

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

三、算法的改進

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

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

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

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

圖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細化工具所得到的面狀要素骨架圖與原圖的疊加圖,可以明顯看出,骨架線不是很平滑,會產生一些抖動現象且很多支線或重要點被刪除。相比而言,通過對經典細化算法改進后所得到的骨架線,更能比較詳細地反映面狀要素的形狀特征,且無抖動現象。

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

2.保證線、面連通性的優化

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

圖8 河流柵格圖

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

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

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

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

四、結束語

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

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

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

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

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

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

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

[7] 張宏,溫永寧,劉愛利,等.地理信息系統算法基礎[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—),女,青海互助人,碩士生,主要研究方向為地圖制圖學與地理信息工程。