一種復(fù)雜道路網(wǎng)中心線自動(dòng)提取算法

劉昌振，馬紅

(1.重慶市勘測院，重慶 401121； 2.重慶市地理國情監(jiān)測工程技術(shù)研究中心，重慶 401121)

1 引 言

道路作為地理信息要素的重要組成部分，是數(shù)據(jù)生產(chǎn)過程中重點(diǎn)采集的對象，道路中心線是路徑規(guī)劃、導(dǎo)航等應(yīng)用的基礎(chǔ)數(shù)據(jù)?；A(chǔ)測繪數(shù)據(jù)入庫一般要求提取道路中心線，并建立正確的拓?fù)潢P(guān)系和連通性。在實(shí)際生產(chǎn)中，一般先采集道路邊線，再根據(jù)道路邊線獲取道路中心線，因此，實(shí)現(xiàn)從道路邊線中自動(dòng)提取中心線可以有效提高生產(chǎn)效率。目前，關(guān)于中心線自動(dòng)提取的研究較多，如董箭等[1]提出了一種基于緩沖區(qū)邊界相向逼近求交模型的中心線生成算法，楊得志等[2]提出一種單位圓滾動(dòng)追蹤算法提取中心線，艾廷華等[3]、鐘世彬等[4]、羅小飛等[5]、李功權(quán)等[6]通過建立約束Delaunay三角網(wǎng)提取中心線，并基于三角網(wǎng)的鄰接關(guān)系確定道路起點(diǎn)和交叉口，楊偉等[7]基于Delaunay三角網(wǎng)從眾源軌跡數(shù)據(jù)提取中心線，朱莊生等[8]基于道路輪廓自動(dòng)生成道路中心線，喬慶華[9]等通過改進(jìn)Voronoi圖提取面狀河流中軸線，江嶺等[10]提出一種基于歐式距離分配的面狀河流圖斑中軸線提取方法，王新生等[11]對比了Voronoi圖矢量法和歐式距離區(qū)域分配柵格法提取復(fù)雜多邊形中軸線，胡鵬等[12]總結(jié)和對比了多種中心線提取的算法，并提出了理論上較為嚴(yán)密的點(diǎn)對序列法和地圖代數(shù)多邊形中軸法。以上算法對提取中心線有較好的效果，基于三角網(wǎng)的鄰接關(guān)系可以確定簡單道路的交叉口，但很難正確提取復(fù)雜道路交叉口。針對以上問題，本文提出一套新的、可應(yīng)用于實(shí)際生產(chǎn)的道路網(wǎng)中心線自動(dòng)提取算法，可以從較復(fù)雜的道路網(wǎng)中自動(dòng)提取中心線并構(gòu)建正確的拓?fù)潢P(guān)系。

2 道路網(wǎng)中心線提取算法原理

2.1 道路網(wǎng)交叉拆分

道路邊線的成果數(shù)據(jù)一般是連通的，較復(fù)雜的道路可能有多個(gè)交叉口，直接對原始道路網(wǎng)提取中心線難度較大，提取效果也不理想。通過交叉拆分的方式將道路網(wǎng)拆分成簡單道路邊線對，此處的簡單道路邊線對，指由兩條邊線組成、無交叉口的道路。本文路網(wǎng)交叉拆分的思想是設(shè)置最大寬度閾值，從一條道路邊開始，以最大寬度閾值建立緩沖區(qū)，搜索其他道路邊，獲得和緩沖區(qū)相交的所有邊線，取搜索結(jié)果中距離起始邊較近、在緩沖內(nèi)長度較長的道路，計(jì)算距離起始道路的最短距離，截取在緩沖區(qū)范圍內(nèi)的部分，用比最短距離稍大的寬度(本文使用最短距離1.5倍)建立截取部分的緩沖區(qū)，得到起始道路邊在緩沖區(qū)范圍內(nèi)的部分，最終獲得的這兩部分組成道路邊線對，并記錄邊線對的信息。依次類推，直到處理完所有的邊線，獲得所有邊線對。

道路網(wǎng)交叉拆分原理如圖1(a)所示，首先根據(jù)最大寬度閾值為道路邊線a建立緩沖區(qū)A，獲得和緩沖區(qū)A中相交的道路邊線，取在緩沖區(qū)A長度最長的邊線b，計(jì)算到邊線a和到邊線b的最短距離，用比最短距離稍大的距離(本文取最短距離的1.5倍)為邊線b建立緩沖區(qū)B，獲得邊線a在緩沖區(qū)B內(nèi)的部分a1，道路邊線a1和b組成一個(gè)簡單道路邊線對，對剩余的道路邊線用同樣的方法建立道路邊線對，直到所有道路邊線拆分完畢，圖1(b)中的道路邊線對1、2、3就是實(shí)例數(shù)據(jù)交叉拆分的結(jié)果。

圖1 道路網(wǎng)交叉拆分

2.2 約束迭代三角網(wǎng)建立

獲得邊線對后，對兩條邊線建立約束三角網(wǎng)。道路邊線作為約束建立三角網(wǎng)，符合提取中心線需要的三角網(wǎng)在兩條邊線之間。經(jīng)過第一步拆分的道路邊線對，長度差別不大，我們通過最短邊線法建立三角網(wǎng)。算法過程如圖2(a)所示，取第一條邊線的前兩個(gè)節(jié)點(diǎn)a1、a2和第二條邊線的前兩個(gè)節(jié)點(diǎn)b1、b2，節(jié)點(diǎn)a1、a2、b1構(gòu)成一個(gè)三角形，節(jié)點(diǎn)b1、b2、a1構(gòu)成另外一個(gè)三角形，計(jì)算第一個(gè)三角形邊a2b1的長度和第二個(gè)三角形b2a1的長度，取長度小的邊所在三角形為第一個(gè)三角形，如圖2(a)取節(jié)點(diǎn)a1、a2、b1組成的三角形為第一個(gè)三角形，這個(gè)三角形的其中兩個(gè)節(jié)點(diǎn)a1、a2在第一條邊線，另外一個(gè)節(jié)點(diǎn)b1在第二條邊線。取a1、a2所在邊線的節(jié)點(diǎn)a2、a3和第二條邊線的節(jié)點(diǎn)b1、b2，以同樣的方式獲得第二個(gè)三角形，以此類推，直到處理完兩條邊的所有節(jié)點(diǎn)，最終獲得兩條邊線的約束迭代三角網(wǎng)，結(jié)果如圖2(b)所示。三角網(wǎng)建立的關(guān)鍵在于約束和迭代，兩條邊線約束可以保證三角網(wǎng)始終在兩條邊線范圍內(nèi)，通過迭代獲得所有邊線約束的三角網(wǎng)。

圖2 建立迭代約束三角網(wǎng)

2.3 中心線提取和連接成網(wǎng)

通過迭代建立的約束三角網(wǎng)，每一個(gè)三角形中的兩個(gè)節(jié)點(diǎn)為其中一條道路邊節(jié)點(diǎn)，另外一個(gè)點(diǎn)屬于另外一條道路邊的節(jié)點(diǎn)，通過記錄三角形的生成順序，連接三角形中不屬于道路邊的邊線中點(diǎn)，即可獲得道路邊線對的中心線。

獲得所有道路邊線對的中心線后，依據(jù)道路交叉拆分設(shè)置的最大寬度閾值，在生成中心線的起點(diǎn)和終點(diǎn)搜索周圍是否有中心線生成，一般連接分為如下兩種情況，第一種連接搜索到的中心線組成一條中心線，第二種是將起點(diǎn)或終點(diǎn)連接到搜索到的中心線上。經(jīng)過最后這一步處理，即可獲得較完整的道路網(wǎng)。連接成網(wǎng)的時(shí)候可以根據(jù)實(shí)際情況設(shè)置條件(例如設(shè)置匝道中心線只能和匝道中心線或高速中心線連接)，從而控制最終的道路網(wǎng)，中心線自動(dòng)提取和連接成網(wǎng)如圖3所示。

圖3 中心線自動(dòng)提取和連接成網(wǎng)

3 實(shí)驗(yàn)與分析

我們用C#語言基于ArcObjects編寫程序?qū)崿F(xiàn)以上算法，以重慶市 1∶2 000地形圖生產(chǎn)航測立體采集成果數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)。

3.1 幾種典型道路網(wǎng)提取結(jié)果

道路網(wǎng)中心線提取的難點(diǎn)和關(guān)鍵點(diǎn)在于交叉口的自動(dòng)提取和連接，以三種典型道路網(wǎng)為例，展示本文算法中心線提取結(jié)果。

(1)鄉(xiāng)村道路網(wǎng)

鄉(xiāng)村道路形狀不規(guī)則，交叉口多且類型復(fù)雜。鄉(xiāng)村道路網(wǎng)中心線提取結(jié)果如圖4所示。

圖4 鄉(xiāng)村道路網(wǎng)

(2)街區(qū)道路網(wǎng)

街區(qū)道路形狀規(guī)整，某些地方交叉口多。街區(qū)道路網(wǎng)提取結(jié)果如圖5所示。

(3)立交路網(wǎng)

立交路網(wǎng)一般由匝道連接不同高速，交叉口眾多，不同的立交形狀差別大。立交路網(wǎng)提取結(jié)果如圖6所示。

圖5街區(qū)道路網(wǎng) 圖6立交路網(wǎng)

3.2 多種路網(wǎng)組合

以一幅1∶2 000地形圖中的道路網(wǎng)為例，自動(dòng)提取道路網(wǎng)中心線，原始數(shù)據(jù)有一條省道，兩條鄉(xiāng)道和數(shù)條機(jī)耕路交叉成網(wǎng)，提取結(jié)果如圖7所示。

圖7 多種路網(wǎng)組合

從提取結(jié)果來看，道路中心線基本可以正確提取，大部分道路交叉口可以正確連接，14個(gè)道路交叉口中，有12個(gè)正確連接，2個(gè)未連接，只需要人工處理2個(gè)未連接的交叉口即可獲得最終的結(jié)果。

4 結(jié) 論

本文提出一種新的道路網(wǎng)中心線自動(dòng)提取算法，通過道路網(wǎng)交叉拆分、建立迭代約束三角網(wǎng)和中心線提取并連接成網(wǎng)三個(gè)算法過程?？梢钥焖?、準(zhǔn)確地提取道路網(wǎng)中心線。實(shí)驗(yàn)表明：本文提出的算法可以提取多種復(fù)雜類型的道路網(wǎng)中心線，提取效果較好。