一種復雜道路網中心線自動提取算法

2019-09-05 01:10:32劉昌振馬紅

城市勘測 2019年4期

劉昌振，馬紅

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

1 引言

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

2 道路網中心線提取算法原理

2.1 道路網交叉拆分

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

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

圖1 道路網交叉拆分

2.2 約束迭代三角網建立

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

圖2 建立迭代約束三角網

2.3 中心線提取和連接成網

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

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