面狀要素骨架線提取算法的設(shè)計(jì)與實(shí)現(xiàn)

連超 劉雪

(河南省金地遙感測(cè)繪技術(shù)有限公司，河南 鄭州 450003)

1 引言

面狀要素的骨架線是對(duì)面狀地物主體形狀的抽象描述，反映了面狀地物的主延伸方向和主體形狀特征，在GIS中有著非常重要的應(yīng)用[1]。其提取方法通常有基于矢量方式和柵格方式兩種，基于矢量方式的主要算法有平行線切割中點(diǎn)連線法和Delaunay三角網(wǎng)法[2-4]。平行線切割中點(diǎn)連線法是最簡(jiǎn)單、最直觀求取骨架線的方法，但只能處理簡(jiǎn)單的多邊形，對(duì)于復(fù)雜多邊形（含島多邊形）處理起來(lái)比較困難[5]。Delaunay三角網(wǎng)法具有很好的幾何特性、較大的靈活性和可操作性，但工作量較大，內(nèi)存操作頻繁，占用計(jì)算機(jī)資源較多，且被應(yīng)用于平行輪廓時(shí)，得到的中軸線會(huì)存在很多“鋸齒”[6]?；跂鸥穹绞降姆椒ù蠖嗍褂脭?shù)學(xué)形態(tài)學(xué)方法，內(nèi)存需求少，適應(yīng)性強(qiáng)，但提取效率低。為此，本文在研究上述算法基礎(chǔ)上，提出了一種新的面狀要素骨架線提取算法，以實(shí)現(xiàn)面狀要素骨架線的快速提取。

2 基本定義

圖1中黑線表示基本骨架線，依據(jù)文獻(xiàn)[7]對(duì)其建立結(jié)點(diǎn) -弧段拓?fù)潢P(guān)系。結(jié)合圖1進(jìn)行了以下定義：

度——與結(jié)點(diǎn)相關(guān)聯(lián)弧段的個(gè)數(shù)稱為結(jié)點(diǎn)的度。度為1的結(jié)點(diǎn)稱為懸掛結(jié)點(diǎn)，與懸掛結(jié)點(diǎn)相關(guān)聯(lián)的弧段稱為懸掛弧段；度為3的結(jié)點(diǎn)稱為岔口結(jié)點(diǎn)。

假岔口結(jié)點(diǎn)——對(duì)于岔口結(jié)點(diǎn)，若多邊形在其附近呈十字路口或丁字路口狀，則稱其為真岔口結(jié)點(diǎn)；反之，則稱其為假岔口結(jié)點(diǎn)。

節(jié)點(diǎn)——組成線段的點(diǎn)稱為節(jié)點(diǎn)。對(duì)于任意一節(jié)點(diǎn)，與其相鄰節(jié)點(diǎn)為該節(jié)點(diǎn)的鄰節(jié)點(diǎn)，與其鄰節(jié)點(diǎn)相鄰節(jié)點(diǎn)為該節(jié)點(diǎn)的跨節(jié)點(diǎn)。

角點(diǎn)——三點(diǎn)組成的夾角中，夾角對(duì)應(yīng)的點(diǎn)為角點(diǎn)（如圖1中，∠ABC的角點(diǎn)為B）。

圖1 假岔口結(jié)點(diǎn)、節(jié)點(diǎn)和角點(diǎn)

3 面狀要素骨架線的提取

3.1 基本思想

首先，依據(jù)文獻(xiàn)[8]提取多邊形基本骨架線，結(jié)合文獻(xiàn)[7]對(duì)基本骨架線建立結(jié)點(diǎn) - 弧段拓?fù)潢P(guān)系。其次，標(biāo)記Delaunay三角網(wǎng)中三角形。再次，根據(jù)已建立的拓?fù)潢P(guān)系和三角形標(biāo)記，對(duì)基本骨架線上的結(jié)點(diǎn)和弧段集合進(jìn)行懸掛結(jié)點(diǎn)、岔口結(jié)點(diǎn)、假岔口結(jié)點(diǎn)和懸掛弧段的判斷和標(biāo)記，并將它們分別存放至各自對(duì)應(yīng)的集合中。然后，根據(jù)上述集合對(duì)基本骨架線末梢進(jìn)行分類(lèi)，根據(jù)多邊形節(jié)點(diǎn)集合對(duì)多邊形進(jìn)行分類(lèi)。最后，根據(jù)骨架線末梢類(lèi)型、多邊形類(lèi)型和最小比例閾值對(duì)基本骨架線末梢進(jìn)行優(yōu)化。

3.2 Delaunay三角網(wǎng)中三角形的標(biāo)記

根據(jù)基本骨架線和Delaunay三角網(wǎng)中三角形間的空間關(guān)系，對(duì)Delaunay三角網(wǎng)中三角形進(jìn)行標(biāo)記：基本骨架線穿過(guò)的三角形標(biāo)記為true；反之，標(biāo)記為false。

3.3 懸掛結(jié)點(diǎn)、岔口結(jié)點(diǎn)、假岔口結(jié)點(diǎn)和懸掛弧段的判斷

對(duì)于懸掛結(jié)點(diǎn)、岔口結(jié)點(diǎn)和懸掛弧段，根據(jù)其定義進(jìn)行判斷，并把岔口結(jié)點(diǎn)存放至岔口結(jié)點(diǎn)集合中，用于假岔口結(jié)點(diǎn)的判斷；假岔口結(jié)點(diǎn)的判斷是在岔口結(jié)點(diǎn)的基礎(chǔ)上，根據(jù)其定義進(jìn)行的。

假設(shè)基本骨架線上岔口結(jié)點(diǎn)M關(guān)聯(lián)的三條弧段為L(zhǎng)1、L2、L3，L1、L2、L3上的非M結(jié)點(diǎn)在其對(duì)應(yīng)弧段上的鄰節(jié)點(diǎn)分別為A、B、C，A、B、C三點(diǎn)間兩兩組成線段的中點(diǎn)依次為P1、P2、P3，則判斷M是否為假岔口結(jié)點(diǎn)的步驟為：（1）計(jì)算出點(diǎn)P1、P2、P3。（2）依據(jù)“點(diǎn)是否在多邊形內(nèi)部判斷方法”判斷出P1、P2、P3是否在多邊形內(nèi)部。（3）根據(jù)步驟2判斷結(jié)果和假岔口結(jié)點(diǎn)定義，對(duì)M進(jìn)行判斷：若P1、P2、P3都在多邊形內(nèi)部，則多邊形在M附近沒(méi)有呈現(xiàn)十字路口或丁字路口狀，M為假岔口結(jié)點(diǎn)；否則，多邊形在M附近呈現(xiàn)十字路口或丁字路口狀，M為真岔口結(jié)點(diǎn)。按照上述步驟對(duì)圖2中岔口結(jié)點(diǎn)O進(jìn)行判斷可得：O為假岔口結(jié)點(diǎn)。

點(diǎn)是否在多邊形內(nèi)部的判斷方法：首先，找出以點(diǎn)為重心、一定閾值為對(duì)角線長(zhǎng)度的最小矩形。其次，在Delaunay三角網(wǎng)中找出與最小矩形屬于包含關(guān)系的三角形，并將其存入三角形集合中。再次，根據(jù)上述結(jié)果對(duì)該點(diǎn)進(jìn)行判斷：若集合中沒(méi)有三角形或存在標(biāo)記為false的三角形，則該點(diǎn)在多邊形外部；反之，該點(diǎn)在多邊形內(nèi)部。

圖2 假岔口結(jié)點(diǎn)的判斷

3.4 基本骨架線末梢和多邊形的分類(lèi)

基本骨架線末梢，是指基本骨架線的末端。根據(jù)基本骨架線和懸掛弧段的定義可知；在基本骨架線末梢在懸掛弧段上。因此，本文根據(jù)懸掛弧段集合和假岔口結(jié)點(diǎn)集合對(duì)基本骨架線末梢進(jìn)行了分類(lèi)：若懸掛弧段上非末梢處的懸掛結(jié)點(diǎn)是假岔口結(jié)點(diǎn)，且與該結(jié)點(diǎn)相關(guān)聯(lián)的另兩條弧段中至少有一條為懸掛弧段，則將該結(jié)點(diǎn)附近末梢稱為T(mén)形末梢；反之，稱為拐角末梢。

對(duì)于多邊形，根據(jù)其節(jié)點(diǎn)個(gè)數(shù)N進(jìn)行了分類(lèi)：若N≠4，稱其為一般多邊形；否則，稱其為四點(diǎn)多邊形。對(duì)于四點(diǎn)多邊形，根據(jù)其內(nèi)角進(jìn)行分類(lèi)：若時(shí)，稱其為似矩形四點(diǎn)多邊形；否則，稱為一般四點(diǎn)多邊形。

3.5 基本骨架線末梢的優(yōu)化

多邊形分為四點(diǎn)多邊形和一般多邊形。下面分別對(duì)這兩種多邊形基本骨架線末梢的優(yōu)化進(jìn)行討論。

通過(guò)分析四點(diǎn)多邊形基本骨架線末梢類(lèi)型可知，其都為拐角末梢。因此，四點(diǎn)多邊形基本骨架線末梢的優(yōu)化實(shí)際上是指四點(diǎn)多邊形基本骨架線拐角末梢的優(yōu)化。四點(diǎn)多邊形基本骨架線末梢的優(yōu)化步驟為：（1）對(duì)四點(diǎn)多邊形進(jìn)行分類(lèi)：若其為一般四點(diǎn)多邊形，則保持不變；否則，進(jìn)入下一步。（2）找出步驟1中四點(diǎn)多邊形每條邊上的中點(diǎn)，并將屬于相對(duì)關(guān)系兩條邊的中點(diǎn)歸為一組。（3）計(jì)算出每組兩點(diǎn)連線間的距離，并進(jìn)行比較。（4）依據(jù)步驟3的比較結(jié)果和骨架線最長(zhǎng)原則，保留長(zhǎng)度值較大兩點(diǎn)間的連線為優(yōu)化后的骨架線。如圖3（a）中BD表示已構(gòu)建Delaunay三角網(wǎng)的似矩形四點(diǎn)多邊形的基本骨架線，按照上述步驟對(duì)其優(yōu)化，可得到優(yōu)化后的骨架線，即圖3（b）中的P2P4。

圖3 似矩形四點(diǎn)多邊形基本骨架線末梢的優(yōu)化

分析一般多邊形基本骨架線末梢類(lèi)型可知，其既可屬于拐角末梢，又可屬于T形末梢。下面對(duì)一般多邊形兩種類(lèi)型末梢的優(yōu)化分別進(jìn)行討論。

（1）拐角末梢的優(yōu)化。假設(shè)一般多邊形基本骨架線拐角末梢處端點(diǎn)為O，則拐角末梢的優(yōu)化過(guò)程為：首先，找出以O(shè)為頂點(diǎn)、標(biāo)記為true的三角形。其次，在找到的三角形中找出以O(shè)為端點(diǎn)的兩條邊，并確定這兩條邊的中點(diǎn)M、N。再次，在基本骨架線上找出O的鄰節(jié)點(diǎn)和跨節(jié)點(diǎn)。最后，依次計(jì)算出O、M、N和鄰節(jié)點(diǎn)、跨節(jié)點(diǎn)組成的以鄰節(jié)點(diǎn)為角點(diǎn)的夾角，找出最大角，并將O移至最大角所對(duì)應(yīng)的點(diǎn)（鄰節(jié)點(diǎn)、跨節(jié)點(diǎn)除外）。如圖4（a）中AI為基本骨架線，其末梢都為拐角末梢，按照上述過(guò)程對(duì)其優(yōu)化，可得到優(yōu)化后的骨架線，即圖4（b）中的P2P4。

圖4 拐角末梢的優(yōu)化

（2）T形末梢的優(yōu)化。它是在已優(yōu)化拐角末梢的基礎(chǔ)上進(jìn)行的。假設(shè)一般多邊形基本骨架線T形末梢處對(duì)應(yīng)的假岔口結(jié)點(diǎn)為O，則T形末梢的優(yōu)化過(guò)程為：

①找出與O相關(guān)聯(lián)的三條弧段，計(jì)算出它們的長(zhǎng)度，并進(jìn)行排序。②分別計(jì)算出最長(zhǎng)弧段與另兩條弧段的比值以及另兩條弧段間的比值。若前兩個(gè)比值都大于最小比例閾值，且最后一個(gè)比值接近1，則進(jìn)入下一步；否則，T形末梢保持不變。③分別判斷較短兩條弧段是否為懸掛弧段。才若都為懸掛弧段，則進(jìn)入下一步；否則，T形末梢保持不變。④在步驟1中找到的三條弧段上分別找出O的鄰節(jié)點(diǎn)和跨節(jié)點(diǎn)。⑤找出O所在三角形，計(jì)算出三邊的中點(diǎn)，并從中點(diǎn)中找出與O鄰節(jié)點(diǎn)（在最長(zhǎng)弧段上）坐標(biāo)相同的點(diǎn)。⑥依據(jù)文獻(xiàn)[9]判斷步驟5中找到三角形的類(lèi)型，若為Ⅰ類(lèi)或Ⅲ類(lèi)三角形，則刪除較短的兩條弧段，并將O移至與步驟5中找到點(diǎn)所在三角形的邊屬于相對(duì)關(guān)系的三角形的頂點(diǎn)即可；否則，進(jìn)入下一步。⑦依次計(jì)算出O在兩條較短弧段上的鄰節(jié)點(diǎn)和O在最長(zhǎng)弧段上的鄰節(jié)點(diǎn)、跨節(jié)點(diǎn)組成的以最長(zhǎng)弧段上O的鄰節(jié)點(diǎn)為角點(diǎn)的夾角，找出較大角所對(duì)應(yīng)的點(diǎn)（最長(zhǎng)弧段上結(jié)點(diǎn)O的鄰節(jié)點(diǎn)和跨節(jié)點(diǎn)除外），并判斷不包含該點(diǎn)的弧段（最長(zhǎng)弧段除外）是否為懸掛弧段，若為懸掛弧段，則刪除，并將O移至該步驟中已找到的點(diǎn)處即可。如圖5（a）中黑線表示拐角末梢優(yōu)化后的骨架線，假岔口結(jié)點(diǎn)O、M附近的末梢都為T(mén)形末梢，按照上述過(guò)程對(duì)其優(yōu)化，優(yōu)化后的結(jié)果如圖5（b）中的黑線。

3.6 骨架線提取的步驟

步驟一：提取多邊形基本骨架線，并對(duì)其建立結(jié)點(diǎn)形 -弧段拓?fù)潢P(guān)系。

步驟二：標(biāo)記Delaunay三角網(wǎng)中三角形。

步驟三：標(biāo)識(shí)懸掛結(jié)點(diǎn)、岔口結(jié)點(diǎn)、假岔口結(jié)點(diǎn)和懸掛弧段，并將它們分別存入各自對(duì)應(yīng)的集合中。

步驟四：對(duì)基本骨架線末梢和多邊形進(jìn)行分類(lèi)。步驟五：對(duì)四點(diǎn)多邊形的基本骨架線進(jìn)行優(yōu)化。步驟六：對(duì)一般多邊形的基本骨架線進(jìn)行優(yōu)化。

圖5 T形末梢的優(yōu)化

4 試驗(yàn)分析

筆者運(yùn)用這一算法，以某地區(qū)地面支渠數(shù)據(jù)為例，進(jìn)行了面狀要素骨架線提取。如圖6（a）表示地面支渠原始數(shù)據(jù)，圖6（b）表示運(yùn)用本文算法提取的骨架線。分析結(jié)果可知，該算法不僅有效解決了提取平行輪廓或似平行輪廓中軸線時(shí)出現(xiàn)的“鋸齒”，而且較好反映了面狀地物的主延伸方向和主體的形狀特征，準(zhǔn)確性較高。

圖6 地面支渠骨架線的提取

5 結(jié)束語(yǔ)

本文所用方法實(shí)現(xiàn)了面狀要素骨架線的提取，利用Visual Studio 2010編寫(xiě)了程序，對(duì)某地區(qū)地面支渠進(jìn)行了骨架線的提取。實(shí)驗(yàn)結(jié)果表明該方法是可行的，且準(zhǔn)確性較高，適合大多數(shù)地面支渠數(shù)據(jù)，但還不太成熟，特別是在地面支渠數(shù)據(jù)比較復(fù)雜的情況下，優(yōu)化后的骨架線并不理想。這些問(wèn)題需要在以后的研究過(guò)程中進(jìn)一步改善，使其更加實(shí)用化。