李功權(quán)，蔡祥云 (長(zhǎng)江大學(xué)地球科學(xué)學(xué)院，湖北 武漢 430100)

一種基于約束三角網(wǎng)的道路中心線的提取方法

李功權(quán)，蔡祥云 (長(zhǎng)江大學(xué)地球科學(xué)學(xué)院，湖北 武漢 430100)

鑒于道路中心線應(yīng)用的廣泛性，研究了基于約束Delaunay三角網(wǎng)的道路中心線的提取算法。以道路邊界線作為約束線，采用Delaunay方法構(gòu)建三角網(wǎng)。通過確定相鄰三角形的類型，把獲取的節(jié)點(diǎn)分為3類，其對(duì)應(yīng)道路網(wǎng)絡(luò)中的十字路、T型路和環(huán)島路，對(duì)其分別進(jìn)行優(yōu)化處理，從而形成道路的中心線。在給出詳細(xì)的算法步驟的同時(shí)，并用C#語言實(shí)現(xiàn)該算法。實(shí)測(cè)數(shù)據(jù)應(yīng)用分析表明，該算法生成的道路中心線符合原道路多邊形的形態(tài)，保持了原圖形的拓?fù)涮卣鳌?/p>

道路中心線；約束Delaunay三角網(wǎng)；道路網(wǎng)絡(luò)模型

根據(jù)道路中心線建立的道路網(wǎng)絡(luò)模型，充分利用了GIS的網(wǎng)絡(luò)分析功能，在交通管理和汽車導(dǎo)航中有著廣泛的應(yīng)用。道路中心線的數(shù)據(jù)一般無法直接得到，在道路規(guī)劃設(shè)計(jì)中可能使用的是道路兩邊的邊界線，城市土地管理部門可能有各個(gè)地塊的邊界信息，這就需要從這些數(shù)據(jù)中提取道路中心線，而不是去實(shí)地人工采集。如果把需要求取道路中心線的區(qū)域看作一個(gè)多邊形，不是道路的相關(guān)空間信息作為約束信息，道路中心線的求取問題就可以轉(zhuǎn)化為多邊形骨架線的求取。所謂骨架線，就是用與原形狀連通性和拓?fù)浣Y(jié)構(gòu)相一致的細(xì)曲線作為原對(duì)象的一種抽象表示，多邊形骨架線的本質(zhì)是對(duì)多邊形形狀的抽象描述，它反映了多邊形的延伸方向和形狀特征[1-3]。在GIS中，面狀地理空間對(duì)象的分析等很多空間操作都需要提取骨架線[4-6]。

1 算法原理

多邊形骨架線提取的關(guān)鍵是搜尋多邊形內(nèi)部到邊界線上的等距離點(diǎn)集，本質(zhì)上屬于空間鄰近分析問題。一般的骨架線的提取算法有：①數(shù)學(xué)形態(tài)學(xué)提取骨架線，這種方法本質(zhì)是矢量化方法；②最大內(nèi)切圓盤法，最大圓盤完全落于目標(biāo)圖像內(nèi)，并且至少有2點(diǎn)與目標(biāo)邊界相切。骨架的每一個(gè)點(diǎn)都對(duì)應(yīng)于一個(gè)最大圓盤的圓心和半徑，圓盤的構(gòu)建特別是小圓盤的構(gòu)建是該算法的最大難題；③基于Delaunay三角網(wǎng)的多邊形骨架線提取算法，Delaunay 三角網(wǎng)是一系列相連但不重疊的三角形的集合，而且這些三角形的外接圓不包含面域中其他任意點(diǎn)，且是Voronoi圖的對(duì)偶[7]。Delaunay三角剖分可以最大限度地避免狹長(zhǎng)三角形的出現(xiàn)，并且可以不管何處開始都能保持三角網(wǎng)絡(luò)的唯一性，Delaunay三角網(wǎng)是探測(cè)空間圖形鄰近關(guān)系的優(yōu)秀工具。因此，筆者采用Delaunay三角網(wǎng)作為提取骨架線的理論工具。以多邊形的邊界為約束條件構(gòu)建三角網(wǎng)，取三角形邊線的中點(diǎn)作為骨架線的節(jié)點(diǎn)，順次連接這些節(jié)點(diǎn)，得到多邊形的骨架線[7]。

1.1約束Delaunay三角網(wǎng)的構(gòu)建

對(duì)于約束Delaunay三角網(wǎng)生成算法，大致可以分為3種：分治算法、逐點(diǎn)插入法和三角網(wǎng)生長(zhǎng)法。而逐點(diǎn)插入算法的特點(diǎn)是實(shí)現(xiàn)比較簡(jiǎn)單，占用內(nèi)存小，因此筆者采用逐點(diǎn)插入法生成無約束的Delaunay三角網(wǎng)，再根據(jù)約束邊刪除多邊形外部多余的三角形。具體過程如下：

1)將離散后多邊形的頂點(diǎn)，建立一個(gè)包含其他數(shù)據(jù)點(diǎn)的初始多邊形，稱其為凸包；

圖1 約束Delaunay三角行的生成過程

2)在初始多邊形中建立初始三角網(wǎng)，對(duì)所有初始多邊形中數(shù)據(jù)點(diǎn)循環(huán)處理(見圖1(a))。

3)插入一個(gè)數(shù)據(jù)點(diǎn)P，在已有三角網(wǎng)中找出包含P的三角形T，把P與T的3個(gè)頂點(diǎn)相連，生成

3個(gè)新的三角形，用LOP算法優(yōu)化三角網(wǎng)(見圖1(b))。

4)刪除不在多邊形內(nèi)部的三角形。判斷三角形的一邊是否在多邊形的內(nèi)部，如果在其內(nèi)部保留該邊，如果不在則舍棄。具體的實(shí)現(xiàn)過程是每次選取一個(gè)三角形一邊的中點(diǎn)，從該點(diǎn)根據(jù)射線法進(jìn)行判定，最后結(jié)果如圖1(c)所示。

1.2三角形類型的確定

圖2 三角形類型的劃分

三角形類型的確定是在Delaunay三角剖分的同時(shí)確定三角形的類型。在該過程中，還要標(biāo)記出新生成的三角形為何種類型，目的是用來識(shí)別道路中心線節(jié)點(diǎn)的類型。從多邊形內(nèi)部三角形的鄰近關(guān)系來看，可以分為3種類型的三角形：第Ⅰ類三角形是只有1個(gè)鄰接三角形；第Ⅱ類三角形是有2個(gè)鄰接三角形；第Ⅲ類三角形是3條邊都有鄰接三角形。根據(jù)鄰近三角形的數(shù)目，將三角形分為3類(見圖2)：第Ⅰ類三角形是三角網(wǎng)中的邊界節(jié)點(diǎn)，其中一邊的中點(diǎn)作為骨架線的端點(diǎn)；第Ⅱ類三角形是三角網(wǎng)中的橋接三角形，是道路中心線的骨干結(jié)構(gòu)，描述了中心線的延展方向；第Ⅲ類三角形作為中心線分支的交匯處，是向3個(gè)方向伸展的出發(fā)點(diǎn)。

三角形類型的確定方法主要依據(jù)與某個(gè)三角形相鄰三角形的個(gè)數(shù)。首先統(tǒng)計(jì)分別與三角形的三條邊相鄰三角形的個(gè)數(shù)總和，默認(rèn)的情況下設(shè)置與三角形的一條邊的鄰接三角形的個(gè)數(shù)為0；其次，根據(jù)三角形三邊相鄰三角形的總和判斷三角形的類型，當(dāng)值為1時(shí)就是第Ⅰ類三角形，值為2時(shí)就是第Ⅱ類三角形，值為3時(shí)就是第Ⅲ類三角形。這樣就能判斷出三角形的類型。

1.3中心線的提取

首先，判斷三角形是否是多余三角形，如果不是就判斷它是哪種類型的三角形。如果是第Ⅰ類的三角形，提取橋接邊的中點(diǎn)和另外2邊中較長(zhǎng)的一邊的中點(diǎn)；第Ⅱ類的三角形提取2個(gè)橋接邊的中點(diǎn)；第Ⅲ類三角形則需要提取該三角形的重心和3條橋接邊的中點(diǎn)。其次，對(duì)于第Ⅰ類和第Ⅱ類的三角形來說提取的2個(gè)點(diǎn)便是中心線；對(duì)于第Ⅲ類三角形來說，將重心分別和其他的3個(gè)點(diǎn)相連便也是中心線。但求出的中點(diǎn)是事先需知道該三角形的哪條邊是橋接邊，這樣便于找出橋接點(diǎn)、端點(diǎn)、分支點(diǎn)，從而確定中心線各節(jié)點(diǎn)的類型。這樣把Delaunay三角形一個(gè)個(gè)的單獨(dú)處理，提取他們各自的這些端點(diǎn)、橋接點(diǎn)、分支點(diǎn)連起來，便可獲得最終的結(jié)果(見圖3)。

圖3 中心線的提取

2 算法實(shí)現(xiàn)

根據(jù)道路多邊形提取道路中心線，涉及到2個(gè)基本的數(shù)據(jù)結(jié)構(gòu)。一是三角形的定義，作為三角網(wǎng)的構(gòu)成基本單元，不僅需要表達(dá)自身三角網(wǎng)的特征，還需要考慮三角形之間的關(guān)系；二是道路中心線的表達(dá)，可以看成是一系列具有特定屬性的頂點(diǎn)的集合。

三角形的數(shù)據(jù)結(jié)構(gòu)可以用一個(gè)結(jié)構(gòu)體來定義，具體的數(shù)據(jù)結(jié)構(gòu)如下：

struct Triangle

{

public long V1Index; //三角形的三個(gè)頂點(diǎn)

public long V2Index;

public long V3Index;

public bool edge1; //(v1,v2)是否已經(jīng)存在

public bool edge2; //(v2,v3)是否已經(jīng)存在

public bool edge3; //(v1.v3)是否已經(jīng)存在

public int AdjIndexE1; //edge1的鄰近三角形的索引

public int AdjIndexE2; //edge2的鄰近三角形的索引

public int AdjIndexE3; //edge3的鄰近三角形的索引

public bool bDelete ; //判斷多余的Delaunay三角形是否被刪

public bool Fkind; //第Ⅰ類三角形

public bool Skind; //第Ⅱ類三角形

public bool Tkind; //第Ⅲ類三角形

}

其中，AdjIndexE1、AdjIndexE2、AdjIndexE3分別用來存儲(chǔ)(v1，v2)邊、(v2，v3)邊、(v1，v3)邊的鄰近三角形的索引，默認(rèn)賦值為-1；Fkind、Skind、Tkind 3個(gè)bool變量分別用來判斷該三角形屬于那種類型，F(xiàn)kind代表第Ⅰ類三角形，Skind代表第Ⅱ類三角形，Tkind代表第Ⅲ類三角形，默認(rèn)值都為false。

根據(jù)相鄰三角形的類型可以把形成的中心線節(jié)點(diǎn)分為端點(diǎn)、橋接點(diǎn)和分支點(diǎn)，具體的數(shù)據(jù)結(jié)構(gòu)如下：

struct Vertex

{

public long x; //頂點(diǎn)的x坐標(biāo)

public long y; //頂點(diǎn)的y坐標(biāo)

public long ID; //頂點(diǎn)的索引

public int isHullEdge; //凸殼頂點(diǎn)標(biāo)記

}

在定義了這2個(gè)數(shù)據(jù)結(jié)構(gòu)后，用C#語言根據(jù)上述原理實(shí)現(xiàn)了道路多邊形文件的讀取、道路邊界點(diǎn)加密、約束三角網(wǎng)的構(gòu)建、三角形中心點(diǎn)的提取、道路中心線各節(jié)點(diǎn)的優(yōu)化處理5個(gè)模塊。

3 應(yīng)用效果評(píng)價(jià)

如果道路線上的邊界點(diǎn)過于稀疏，在生成的三角網(wǎng)中容易出現(xiàn)小內(nèi)角的狹長(zhǎng)三角形。為了解決該問題，可以采用對(duì)道路多邊形邊界點(diǎn)作適當(dāng)加密的辦法，首先對(duì)各邊界點(diǎn)作3次樣條函數(shù)擬合，然后把道路的平均寬度作為間距加到邊界點(diǎn)中。

為了驗(yàn)證該算法，把同樣的數(shù)據(jù)用ArcGIS 9進(jìn)行了處理。在ArcGIS中，如果要提取道路的中心線，如果是面要素，要先將面要素轉(zhuǎn)換為線要素(此處的線要素是雙線要素)，然后利用制圖工具中的提取中心線工具，設(shè)定最大值和最小值參數(shù)，且必須給定最大值。設(shè)計(jì)的測(cè)試數(shù)據(jù)不僅考慮了實(shí)際數(shù)據(jù)的特點(diǎn)，而且還設(shè)計(jì)了多種道路類型。ArcGIS提取的結(jié)果如圖4所示，雖然在多數(shù)區(qū)域提取的道路中心線符合實(shí)際，但在圖4中圓圈和矩形所圈定的區(qū)域都存在著明顯錯(cuò)誤，圓圈所指示的道路中心線明顯不存在；對(duì)于某些交叉路口(矩形所指示的范圍)，和實(shí)際的道路網(wǎng)絡(luò)模型不符。筆者設(shè)計(jì)的算法提取的道路中心線如圖5所示，對(duì)于任何類型的道路限制條件都能適用。

圖4 ArcGIS提取的道路中心線 圖5 筆者設(shè)計(jì)算法提取的道路中心線

4 結(jié) 語

由于形成道路的多邊形樣式變化多端，道路中心線的提取是一個(gè)復(fù)雜的過程。 筆者運(yùn)用約束的Delaunay 三角網(wǎng)法提取道路中心線，算法完全基于矢量數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，算法建立在多邊形的形狀分析基礎(chǔ)上，高效穩(wěn)定。從試驗(yàn)結(jié)果來看，提取的道路中心線能反映出道路的基本特征?？梢姽P者設(shè)計(jì)的算法可以用來求取道路中心線。但該算法可能產(chǎn)生不需要的細(xì)長(zhǎng)三角形，多邊形邊界的細(xì)微波動(dòng)可能會(huì)導(dǎo)致道路中心線的明顯偏移，這個(gè)問題值得進(jìn)一步研究。

[1]Shaked D,Bruckstein A M. The curve axis [J].Computer Vision and Image Understanding, 1996, 63(2):367-369.

[2] LI Z L. Algorithmic Foundation of Multi-scale Spatial Representation [M].CRC Press, 2007：20-23.

[3]Attneav E F. Some informational aspects of visual perception [J].Psychological Review, 1954, 61(3):183-193.

[4] Mcmaster R B. A statistical analysis of mathematical measures for line simplification[J]. The American Cartographer, 1986, 13: 103-116.

[5] Mcmaster R B. Automated line generalization [J]. Cartographica, 1987, 24(2): 74-111.

[6] LI Z L. An examination of algorithms for detection of critical points on digital lines [J]. The Cartographic Journal, 1995, 32(2): 121-125.

[7]Haunert J H,Sester M. Area Collapse and Road Centerlines based on Straight Skeletons [J]. Geoinformatica,2008,12:169-191.

[8] Paul C L. Constrained Delaunay Triangulations [J]. Algorithmica, 1989, 4:97-108.

2012-11-24

中國石油科技創(chuàng)新基金(2010D-5006-0205)

李功權(quán)(1971-)，男，博士，副教授，現(xiàn)主要從事GIS、數(shù)字油藏方面的教學(xué)與研究工作。

TP391.4

A

1673-1409(2013)04-0047-04

[編輯] 洪云飛