王宇昆，曹 力，趙 洋，李 琳

基于有向無環(huán)圖的立交結(jié)構(gòu)構(gòu)建方法

王宇昆1,2，曹 力1,2，趙 洋1,2，李 琳1,2

(1. 合肥工業(yè)大計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230601；2. 工業(yè)安全與應(yīng)急技術(shù)安徽省重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230009)

道路信息是數(shù)字城市中的重要元素，道路網(wǎng)中的立交結(jié)構(gòu)建模對(duì)于城市交通三維仿真、交通優(yōu)化、城市規(guī)劃等諸多領(lǐng)域均有重要意義。當(dāng)前已有大量針對(duì)城市道路網(wǎng)建模技術(shù)的研究工作，但對(duì)立交結(jié)構(gòu)的處理尚未有針對(duì)性的表達(dá)方法。通過對(duì)立交結(jié)構(gòu)的觀察分析，提出一種基于有向無環(huán)圖的立交結(jié)構(gòu)構(gòu)建方法，期望達(dá)到高效、高質(zhì)量建模的目的。首先對(duì)二維柵格數(shù)據(jù)進(jìn)行預(yù)處理，提取有效道路信息；其次依據(jù)提取的信息構(gòu)建有向無環(huán)圖(DAG)，用于表達(dá)立交結(jié)構(gòu)拓?fù)潢P(guān)系；再次基于提出的立交橋道路高度自動(dòng)估算方法，利用DAG結(jié)合道路的結(jié)構(gòu)特性、功能特性及相關(guān)先驗(yàn)知識(shí)，計(jì)算得到道路控制點(diǎn)的高度；最終依據(jù)計(jì)算得到的道路高度和拓?fù)湫畔⑦M(jìn)行立交結(jié)構(gòu)三維模型構(gòu)建。實(shí)驗(yàn)選取了華東地區(qū)3個(gè)典型立交結(jié)構(gòu)進(jìn)行測試，結(jié)果證明該方法在數(shù)據(jù)獲取、計(jì)算正確率方面有一定優(yōu)勢，有助于簡化立交結(jié)構(gòu)建模流程。

計(jì)算機(jī)輔助建模；啟發(fā)式建模；城市道路網(wǎng)；立交結(jié)構(gòu)；有向無環(huán)圖

在虛擬三維數(shù)字城市中，道路網(wǎng)是至關(guān)重要的部分，立交橋則是城市道路網(wǎng)中的連接樞紐。近年來，城區(qū)場景仿真在城市規(guī)劃、交通仿真、電影、游戲等領(lǐng)域應(yīng)用廣泛[1-2]。其中，對(duì)具有顯著三維特征的城市立交橋快速建模已成為該領(lǐng)域的重要應(yīng)用課題[3]，具有一定的理論意義和重要實(shí)用價(jià)值。目前在主流的移動(dòng)端地圖軟件中，會(huì)出現(xiàn)立交橋模型與實(shí)際情況不符的情況，表現(xiàn)為白模沒有下穿隧道、道路間層級(jí)關(guān)系錯(cuò)亂等。如圖1所示白模道路層級(jí)關(guān)系與實(shí)際情況恰恰相反。

當(dāng)前已有大量針對(duì)城市路網(wǎng)、交通路網(wǎng)建模技術(shù)的研究工作[1-2,4-6]。針對(duì)城區(qū)尺度的道路網(wǎng)，研究者提出不同方法用于快速生成真實(shí)的城區(qū)規(guī)模道路網(wǎng)。如PARISH和MüLLER[7]采用L-system并以二維地圖數(shù)據(jù)作為輸入同時(shí)添加約束條件生成道路網(wǎng)；SUN等[8]提出基于模版的方法；VANEGAS等[9]提出前向反向建模相結(jié)合的方法；NISHIDA等[10]提出基于實(shí)例的方法；SONG和WHITEHEAD[11]以基于代理的方法從GIS數(shù)據(jù)中提取道路信息進(jìn)行建模等。但這些工作并不涉及城區(qū)道路網(wǎng)中立交結(jié)構(gòu)的生成。

立交結(jié)構(gòu)是城市交通網(wǎng)絡(luò)中比較復(fù)雜的部分，一般由主體、交叉構(gòu)件、空間連接件組成，具有顯著的三維特征和復(fù)雜的拓?fù)浣Y(jié)構(gòu)[3]。已有大量針對(duì)立交結(jié)構(gòu)圖形表達(dá)及快速建模的研究。胡碧松和龔建華[12]給出了基于高分辨率遙感影像的大型立交結(jié)構(gòu)建模流程；陳卓和馬洪超[13]提出一種基于機(jī)載激光雷達(dá)數(shù)據(jù)(light detection and ranging，LIDAR)的立交橋建模方法。這些方法在參數(shù)設(shè)置、數(shù)據(jù)處理等方面對(duì)用戶的專業(yè)素養(yǎng)要求較高且成本高昂。文獻(xiàn)[14-16]提出了針對(duì)立交結(jié)構(gòu)拓?fù)潢P(guān)系的抽象表達(dá)，并應(yīng)用于對(duì)特定形態(tài)的立交結(jié)構(gòu)提取分類；文獻(xiàn)[17-18]提出了基于二維地圖數(shù)據(jù)的立交結(jié)構(gòu)快速建模方法，但對(duì)層數(shù)較多的復(fù)雜立交結(jié)構(gòu)建模效果不理想。

綜上，對(duì)城區(qū)道路網(wǎng)中的立交結(jié)構(gòu)的描述和建模還存在很多不足，本文提出一種立交結(jié)構(gòu)快速構(gòu)建的方法，并通過生成實(shí)際的城市立交橋模型驗(yàn)證方法的有效性，主要貢獻(xiàn)為：①提出基于有向無環(huán)圖(directed acyclic graphs，DAG)的立交結(jié)構(gòu)拓?fù)潢P(guān)系的抽象描述；②提出一種基于立交橋道路的空間特性、功能特性的道路高度計(jì)算方法。

1 相關(guān)工作

1.1 立交結(jié)構(gòu)構(gòu)建

近年來，針對(duì)立交結(jié)構(gòu)建模方法的研究可根據(jù)數(shù)據(jù)來源分為2類：①基于高分辨率的航空影像、衛(wèi)星遙感影像圖、高精度三維點(diǎn)云數(shù)據(jù)直接獲取目標(biāo)區(qū)域的拓?fù)潢P(guān)系和精確的高度信息進(jìn)行建模。如胡碧松和龔建華[12]根據(jù)高分辨率航空影像提出了建立立交橋的三維數(shù)據(jù)結(jié)構(gòu)和空間拓?fù)潢P(guān)系，以及大型立交橋三維建模的具體流程。陳卓和馬洪超[13]提出一種基于LIDAR數(shù)據(jù)的立交結(jié)構(gòu)建模方法，可直接獲取地物表面高精度、高密度的三維點(diǎn)云。YANG等[19]提出了一種從大規(guī)模移動(dòng)激光掃描點(diǎn)云中識(shí)別道路邊緣點(diǎn)，提取并構(gòu)建其三維模型。這類方法數(shù)據(jù)采集成本較高，數(shù)據(jù)解析難度較大，建模結(jié)果的好壞依賴于對(duì)數(shù)據(jù)的前處理，無法實(shí)時(shí)建模，對(duì)非專業(yè)用戶不友好。②基于更易獲取的二維地圖數(shù)據(jù)確定拓?fù)潢P(guān)系和計(jì)算高度信息，再提供一定的交互方式由用戶手動(dòng)調(diào)整計(jì)算錯(cuò)誤的結(jié)果。該方法更依賴計(jì)算完成的后處理，需要設(shè)計(jì)友好的用戶交互方式。如文獻(xiàn)[17]基于二維柵格數(shù)據(jù)提出一種包括立交橋道路中心線提取、交叉點(diǎn)檢測、道路三維建模的立交橋快速構(gòu)建方法。該方法需要檢測道路交點(diǎn)再去掉大量共線點(diǎn)，導(dǎo)致構(gòu)建的曲線道路不夠平滑，且限定了立交橋?qū)訑?shù)不能超過3層，無法構(gòu)建更復(fù)雜的立交橋。文獻(xiàn)[18]提出將描述二維道路中心線的GIS數(shù)據(jù)轉(zhuǎn)換為三維道路網(wǎng)模型的方法，從而實(shí)現(xiàn)多種立交橋的參數(shù)化構(gòu)建，但由于數(shù)據(jù)模型限制，對(duì)于層次較多的立交結(jié)構(gòu)，最終構(gòu)建的模型正確率不高。

1.2 立交結(jié)構(gòu)抽象描述

針對(duì)在大尺度道路網(wǎng)中快速提取立交結(jié)構(gòu)的難點(diǎn)問題，提出立交結(jié)構(gòu)拓?fù)潢P(guān)系的不同抽象化描述。如文獻(xiàn)[14]利用有向?qū)傩躁P(guān)系圖描述具有典型平面結(jié)構(gòu)的立交橋，構(gòu)建立交結(jié)構(gòu)模版庫，采用圖匹配技術(shù)從道路網(wǎng)中快速匹配立交結(jié)構(gòu)；文獻(xiàn)[15]提出基于立交結(jié)構(gòu)的幾何特征構(gòu)建量化表達(dá)式，對(duì)不同立交結(jié)構(gòu)進(jìn)行抽象化描述。文獻(xiàn)[16]提出一種基于特征的3層數(shù)據(jù)模型，用于立交結(jié)構(gòu)的交通仿真，可描述簡單立交結(jié)構(gòu)的拓?fù)潢P(guān)系和層級(jí)關(guān)系，但對(duì)較復(fù)雜的立交結(jié)構(gòu)缺乏深入研究。這些抽象化描述方法并未用于立交結(jié)構(gòu)的建模，且在應(yīng)用時(shí)均存在一定的局限性。

1.3 城市道路網(wǎng)建模

過程式建模方法被認(rèn)為是構(gòu)建大尺度道路網(wǎng)的有效方法。文獻(xiàn)[7]最早在L-system的基礎(chǔ)上以二維地圖數(shù)據(jù)作輸入并添加約束條件，計(jì)算生成城市道路網(wǎng)及有約束地生成道路周圍的建筑群。隨后諸多研究者在此基礎(chǔ)上提出了改進(jìn)的道路網(wǎng)生成方法。如LINDORFER等[20]利用最小生成樹算法將人口密度高的區(qū)域連接起來作為快速路，并在快速路圍成的封閉區(qū)域中利用L-system生成區(qū)域內(nèi)的道路。CHEN等[21]首先提出允許用戶編輯的路網(wǎng)生成模型，提升了建模的真實(shí)性；SUN等[8]以模版的規(guī)則生成系統(tǒng)的路網(wǎng)生成模型；文獻(xiàn)[9]提出前向和反向建模相結(jié)合的方法，應(yīng)用參數(shù)估計(jì)(避免提供明確的參數(shù)輸入)并支持交互式的路網(wǎng)模型生成和編輯。文獻(xiàn)[10]引入一種基于實(shí)例的方法，由用戶在OSM (OpenStreetMap)中自主選擇一到多個(gè)局部實(shí)例定義要生成的道路樣式，該系統(tǒng)無需設(shè)定輸入?yún)?shù)，但選擇的局部實(shí)例限制了生成的道路網(wǎng)的多樣性；文獻(xiàn)[22]提出一種新的基于語義的過程式建模方法，將基于實(shí)例和參數(shù)輸入的方法相結(jié)合，提供一種“回退”機(jī)制，當(dāng)用戶找不到合適的實(shí)例時(shí)可自行設(shè)置輸入?yún)?shù)構(gòu)建道路網(wǎng)；文獻(xiàn)[11]根據(jù)交通仿真的需要，提出一個(gè)基于代理的道路網(wǎng)生成系統(tǒng)，且可分析生成的道路網(wǎng)的方向性、連通性、曲率等參數(shù)。

立交結(jié)構(gòu)相比普通道路，具有顯著的三維特征和復(fù)雜的拓?fù)浣Y(jié)構(gòu)，其模型各個(gè)部分的參數(shù)更為復(fù)雜，現(xiàn)有的道路網(wǎng)生成方法需要用戶設(shè)置各種參數(shù)輸入，并不適用于目標(biāo)區(qū)域的立交結(jié)構(gòu)模型生成。

綜上所述，目前針對(duì)城市道路網(wǎng)建模、立交結(jié)構(gòu)構(gòu)建及抽象化描述的研究較為廣泛。但所述方法在數(shù)據(jù)源獲取的難易性、層級(jí)關(guān)系計(jì)算及應(yīng)用范圍等方面均存在一定的局限，這是本文主要的研究動(dòng)機(jī)。本文的研究內(nèi)容主要是依托易于獲取的二維地圖數(shù)據(jù)、基于DAG快速得到立交橋子道路的拓?fù)浣Y(jié)構(gòu)和高度信息，從而進(jìn)行高效、高質(zhì)量建模。

2 基于有向無環(huán)圖的立交橋描述

2.1 問題描述

空間結(jié)構(gòu)的形式化描述方法主要有串文法、樹文法、圖文法等。圖作為一種常用的數(shù)據(jù)結(jié)構(gòu)，常被用于描述各種事物基元之間的拓?fù)潢P(guān)系，是一種有效的結(jié)構(gòu)特征信息描述方式。在對(duì)立交橋拓?fù)浣Y(jié)構(gòu)進(jìn)行抽象化描述時(shí)，直接參考平面道路的拓?fù)潢P(guān)系，如圖2(a)所示，僅能描述無匝道和引橋的平面交叉道路。研究者嘗試?yán)糜邢驁D(directed graph，DG)對(duì)道路結(jié)構(gòu)進(jìn)行描述，如文獻(xiàn)[14]提出了描述立交結(jié)構(gòu)的有向?qū)傩躁P(guān)系圖，即用DG描述立交結(jié)構(gòu)的拓?fù)潢P(guān)系，再引入相關(guān)屬性描述其空間結(jié)構(gòu)；文獻(xiàn)[15]根據(jù)立交結(jié)構(gòu)的拓?fù)潢P(guān)系和幾何形態(tài)，將立交結(jié)構(gòu)抽象為具有不同拓?fù)潢P(guān)系的DG，建立典型的量化表達(dá)式模板庫，通過對(duì)比量化表達(dá)式達(dá)到識(shí)別目的；文獻(xiàn)[17]在數(shù)據(jù)處理階段將二維柵格地圖抽象為點(diǎn)和線構(gòu)成的DG再進(jìn)行分析。

使用DG描述立交橋拓?fù)潢P(guān)系時(shí)在圖中會(huì)形成環(huán)路，甚至形成全連通圖，如圖2(b)所示。立交結(jié)構(gòu)拓?fù)潢P(guān)系、空間結(jié)構(gòu)復(fù)雜，計(jì)算高度信息時(shí)，需要多次迭代。形成環(huán)路勢必會(huì)對(duì)相應(yīng)的算法設(shè)計(jì)產(chǎn)生限制，如文獻(xiàn)[17]的算法在設(shè)計(jì)之初就限定立交橋?qū)訑?shù)不超過3層，就是出于這種考慮。

綜上所述，基于DG設(shè)計(jì)立交結(jié)構(gòu)的高度計(jì)算方法有很大局限性。本文提出將具有拓?fù)浔磉_(dá)優(yōu)勢的DAG用于立交結(jié)構(gòu)道路拓?fù)潢P(guān)系的描述，以解決環(huán)路帶來的限制，并以此為基礎(chǔ)設(shè)計(jì)相應(yīng)的高度計(jì)算方法。

2.2 立交橋的有向無環(huán)圖描述

一個(gè)完整的立交結(jié)構(gòu)可以抽象為由若干道路中心線、道路控制點(diǎn)組成的圖形結(jié)構(gòu)。本文采用DAG的=(,)描述，其中為所有道路控制點(diǎn)的集合，為道路中心線的集合，用(1,2,···,P)?表示從控制點(diǎn)1到控制點(diǎn)的道路。本文方法所采用的控制點(diǎn)數(shù)據(jù)結(jié)構(gòu)為：

圖2是采用DG和DAG對(duì)十字形道路交叉口描述的對(duì)比，為了使對(duì)比效果更明顯，這里僅畫出DAG部分連接關(guān)系。按照車輛行駛方向?qū)⒁粭l道路分為方向相反的2個(gè)方向，由+/–號(hào)代表不同車流方向。按照車流右行規(guī)則，圖2(c)所示是十字路口的DAG部分描述。全部的拓?fù)潢P(guān)系見圖3(a)。從圖2中可以看出，圖2(a)所描述的拓?fù)浣Y(jié)構(gòu)無法描述更多方向之間的拓?fù)潢P(guān)系；圖2(b)會(huì)形成環(huán)路；圖2(c)的描述可以克服前2種方法的不足，更為合理。

圖2 有向圖與有向無環(huán)圖的對(duì)比

Fig. 2 Comparison between DG and DAG

2.3 立交橋的典型結(jié)構(gòu)

立交橋所處的交叉口根據(jù)形態(tài)分類主要有T形、Y形、十字形、X形等形式[23]，圖3是十字形路口及T形路口的DAG描述。

圖3 典型交叉口的有向無環(huán)圖描述

參考道路橋梁專業(yè)中立交橋的分類方法[24]，可根據(jù)二維形態(tài)對(duì)立交結(jié)構(gòu)分類。首先根據(jù)道路交匯個(gè)數(shù)將立交橋分為三肢和四肢2類，再根據(jù)其中包含的弧段個(gè)數(shù)對(duì)其繼續(xù)細(xì)分為喇叭口形、苜蓿葉形、環(huán)形、單圈形、多圈形、十字形6類。由此可將典型立交橋分為11類，如圖4所示。

圖4 典型立交結(jié)構(gòu)

同時(shí)可結(jié)合道路的功能及形態(tài)特點(diǎn)將立交橋道路分為3類，見表1。

表1 立交橋道路分類

3 立交結(jié)構(gòu)分層方法

立交結(jié)構(gòu)模型構(gòu)建前需要獲取道路間的拓?fù)潢P(guān)系和層級(jí)關(guān)系。從原始數(shù)據(jù)中利用DAG對(duì)其進(jìn)行結(jié)構(gòu)化描述，可以確定拓?fù)潢P(guān)系。層級(jí)關(guān)系可以根據(jù)立交橋道路的功能特性、幾何特點(diǎn)、相關(guān)先驗(yàn)知識(shí)并結(jié)合DAG推導(dǎo)得到。根據(jù)計(jì)算得到的圖元參數(shù)結(jié)合基本組件可生成模型。對(duì)于產(chǎn)生沖突的情況可回退至高度計(jì)算環(huán)節(jié)重新計(jì)算確定道路的層級(jí)關(guān)系。圖5為本文方法核心流程。

圖5 核心流程

3.1 DAG的構(gòu)造

根據(jù)上述，DAG在表達(dá)立交橋拓?fù)潢P(guān)系、設(shè)計(jì)道路高度計(jì)算算法方面有諸多優(yōu)越性，本文提出一種立交橋DAG描述構(gòu)建方法。

方法1. 立交橋DAG描述構(gòu)建方法

輸入：和，道路控制點(diǎn)數(shù)組、道路中心線數(shù)組；

輸出：={，} 立交橋?qū)?yīng)的DAG描述，為控制點(diǎn)集合，為道路中心線集合。

3.2 立交橋道路分層

從原始數(shù)據(jù)的道路中心線和控制點(diǎn)構(gòu)造相應(yīng)DAG描述，很容易得到控制點(diǎn)之間的拓?fù)潢P(guān)系。并根據(jù)道路中心線進(jìn)行道路分類。由2.3節(jié)所述，匝道彎曲較大，主橋更接近直線。通過已知控制點(diǎn)進(jìn)行曲線擬合，再計(jì)算道路中心線上控制點(diǎn)相對(duì)于擬合曲線的平均殘差以區(qū)分主橋和匝道。引橋的作用是減緩主橋上、下橋坡度，跨度較小且接近直線，因此可以根據(jù)曲率變化區(qū)分匝道和引橋。本文提出以下方法對(duì)立交橋子道路進(jìn)行分類。

方法2.立交橋道路分類方法

輸入：={,}，立交橋的DAG描述；

輸出：，，，分別代表主橋、匝道、引橋集合。

方法2中曲線擬合過程需要根據(jù)實(shí)際情況選擇不同的擬合曲線。在主橋接近直線形時(shí)，可采用最小二乘法進(jìn)行直線擬合；在主橋彎曲程度較大時(shí)，選擇階貝塞爾曲線擬合效果更好。

3.3 道路控制點(diǎn)高度計(jì)算

通過前述方法可得到不同道路的拓?fù)潢P(guān)系以及確定道路所屬功能類別。計(jì)算道路控制點(diǎn)高度可以確定道路的層級(jí)關(guān)系。坡度常用來描述道路高度變化的趨勢。本文方法根據(jù)道路功能特性、相關(guān)先驗(yàn)知識(shí)估算道路控制點(diǎn)高度，并結(jié)合DAG的結(jié)構(gòu)特性對(duì)估算結(jié)果進(jìn)行自動(dòng)調(diào)整。按照主橋、匝道、引橋的順序依次計(jì)算道路高度。主橋作用是實(shí)現(xiàn)主方向上的車輛流通，定義了立交結(jié)構(gòu)的主方向。相對(duì)于匝道、引橋，主橋在高度上往往不存在上升和下降的變化。因此可根據(jù)道路橋梁建設(shè)標(biāo)準(zhǔn)[25]，直接對(duì)各方向上主橋賦予不同的高度層級(jí)，具體的高度層級(jí)需程序預(yù)設(shè)。引橋作用是減緩道路坡度變化，其高度變化只存在遞增和遞減2種情況。匝道的高度變化根據(jù)實(shí)際情況變化更加復(fù)雜，但同一條匝道高度變化最多只會(huì)出現(xiàn)上升、下降2次趨勢的變化。同時(shí)，匝道和引橋的起點(diǎn)、終點(diǎn)都在主橋上。因此可根據(jù)起始點(diǎn)高度，結(jié)合不同種類道路高度變化趨勢的不同以及坡度依次計(jì)算道路控制點(diǎn)的高度。在《城市道路設(shè)計(jì)規(guī)范》[25]中，針對(duì)立交橋坡度范圍做了明確規(guī)定。冰凍地區(qū)最大縱坡度為4%，非冰凍區(qū)域最大縱坡度為5%。本文調(diào)研了華東地區(qū)不同城區(qū)立交橋道路坡度情況，最終將實(shí)驗(yàn)計(jì)算過程中坡度范圍定為2.5%~3.5%。并通過方法3估算主橋、匝道、引橋控制點(diǎn)高度，以此估算層級(jí)關(guān)系。

方法3.匝道、引橋控制點(diǎn)高度計(jì)算方法

輸入：,,，分別代表主橋、匝道、引橋集合；和上升坡度和下降坡度；

輸出：匝道、引橋控制點(diǎn)的高度。

4 建模及分析

本文基于Unity3D 2018.2.10f1開發(fā)了道路的拓?fù)潢P(guān)系、層級(jí)關(guān)系自動(dòng)計(jì)算、模型生成軟件工具。將目標(biāo)區(qū)域二維柵格地圖數(shù)據(jù)處理得到立交結(jié)構(gòu)道路中心線及道路控制點(diǎn)數(shù)據(jù)作為系統(tǒng)輸入數(shù)據(jù)，經(jīng)系統(tǒng)自動(dòng)計(jì)算可確定各條道路的拓?fù)潢P(guān)系和高度信息。最后利用基本組件結(jié)合上一步得到拓?fù)浼皩蛹?jí)關(guān)系進(jìn)行建模。

4.1 數(shù)據(jù)處理

首先從柵格地圖數(shù)據(jù)中提取有效信息，圖6為華東某城區(qū)立交橋的二維柵格地圖數(shù)據(jù)及相對(duì)應(yīng)的地圖數(shù)據(jù)，圖中藍(lán)色區(qū)域及其邊界線代表道路周圍的建筑物及其輪廓，非建筑物處的線段代表道路，線段上的點(diǎn)代表道路控制點(diǎn)。

圖6 地圖數(shù)據(jù)及柵格地圖

對(duì)柵格地圖數(shù)據(jù)預(yù)處理的目標(biāo)是提取立交橋子道路的中心線及控制點(diǎn)坐標(biāo)。預(yù)處理操作主要包括：①讀取柵格地圖，并進(jìn)行灰度化；②依據(jù)灰度化的結(jié)果，采用圖像二值化方法將地圖數(shù)據(jù)分隔成道路和建筑物區(qū)域，并只保留道路數(shù)據(jù)；③由于立交橋結(jié)構(gòu)復(fù)雜，道路的控制點(diǎn)數(shù)目多，且立交結(jié)構(gòu)周圍往往存在建筑物群落及內(nèi)道路，經(jīng)二值化并不能完全去除不必要的道路、建筑物信息，因此還需要去除噪聲數(shù)據(jù)；④根據(jù)像素點(diǎn)坐標(biāo)將道路和控制點(diǎn)轉(zhuǎn)化為更平滑的數(shù)據(jù)。經(jīng)以上步驟可提取目標(biāo)區(qū)域立交橋道路中心線及控制點(diǎn)信息，如圖7所示。

圖7 數(shù)據(jù)預(yù)處理流程

按圖7所示的操作步驟，可從二維柵格地圖中提取出立交橋的道路中心線和控制點(diǎn)，再根據(jù)點(diǎn)、線基本圖元的信息推導(dǎo)出該立交結(jié)構(gòu)相應(yīng)的DAG表達(dá)，至此得到該區(qū)域全部的拓?fù)潢P(guān)系。以圖6所示區(qū)域?yàn)槔?，結(jié)合2.2節(jié)所述，將一條道路上所有車輛流通方向定義為2個(gè)相反方向。對(duì)于數(shù)據(jù)處理所得的最終結(jié)果(圖7)，可以將道路控制點(diǎn)抽象為DAG節(jié)點(diǎn)，將2個(gè)控制點(diǎn)之間的道路中心線抽象為DAG的一條邊，將道路車流方向抽象為DAG有向邊的方向。以一組+/–號(hào)表示經(jīng)過一個(gè)道路控制點(diǎn)的2個(gè)相反的車流方向。首先確定主路對(duì)應(yīng)的邊的方向，再按照車流右行規(guī)則，可確定連接不同方向的主路的匝道對(duì)應(yīng)的有向邊的方向。經(jīng)過迭代推導(dǎo)最終可得到圖8所示的DAG表達(dá)結(jié)果。這里隱去了中間控制點(diǎn)，僅保留了每條道路的起始點(diǎn)及不同道路相交的點(diǎn)。

圖8 推導(dǎo)所得的DAG表達(dá)示意圖

4.2 基于基本組件建模

立交橋是由各種基本組件構(gòu)成的具有復(fù)雜空間結(jié)構(gòu)的建筑物。完整的立交橋除了道路，還包括橋墩以及各種輔助物(路燈、交通輔助線等)。李尚林等[26]提出一種基于基本組件的多層參數(shù)建模方法。本文定義立交結(jié)構(gòu)的高層參數(shù)是道路的拓?fù)潢P(guān)系及層級(jí)關(guān)系，低層基本參數(shù)包括道路長度、寬度、跨度、曲率等均可由道路中心線及控制點(diǎn)數(shù)據(jù)計(jì)算得出。構(gòu)建立交結(jié)構(gòu)的基本組件庫，結(jié)合上述方法得到的高層及低層參數(shù)，可快速生成真實(shí)的立交結(jié)構(gòu)模型。圖9是立交結(jié)構(gòu)基本組件示例，圖10是利用基本組件的立交結(jié)構(gòu)建模過程示例。4.3節(jié)給出了多組實(shí)驗(yàn)建模結(jié)果。

圖9 立交結(jié)構(gòu)基本組件示例

圖10 建模過程示例

4.3 建模結(jié)果

本文選取了華東地區(qū)的3個(gè)典型立交結(jié)構(gòu)進(jìn)行數(shù)據(jù)計(jì)算并建模。表2依次給出選取區(qū)域的衛(wèi)星圖、計(jì)算及建模結(jié)果。計(jì)算結(jié)果示意圖是三維場景下帶有高度信息的道路中心線及控制點(diǎn)展示。為了突出表現(xiàn)道路層級(jí)的不同，本文還設(shè)置了特定的高度-RGB值計(jì)算公式，將道路中心線和控制點(diǎn)的高度信息映射為限定范圍內(nèi)唯一RGB值，表2中紅色點(diǎn)代表高度為0的控制點(diǎn)。同時(shí)從每個(gè)控制點(diǎn)中心向地面射一條直線，作為表現(xiàn)控制點(diǎn)高度的參照物。對(duì)建模結(jié)果進(jìn)行渲染可以得到真實(shí)的渲染結(jié)果。圖11是區(qū)域3的包含建模結(jié)果及周邊建筑場景的渲染結(jié)果。

表3為本文方法對(duì)于不同實(shí)驗(yàn)區(qū)域的計(jì)算正確率。其結(jié)果表明，對(duì)于具有典型形態(tài)特征的立交結(jié)構(gòu)，本文方法得出的道路分層結(jié)果正確率較高。模型生成時(shí)間包括數(shù)據(jù)處理時(shí)間、DAG構(gòu)建時(shí)間、通過DAG描述道路分類及高度計(jì)算時(shí)間、建模時(shí)間及必要的交互時(shí)間。如實(shí)驗(yàn)區(qū)域1的模型構(gòu)建流程用時(shí)為：數(shù)據(jù)處理耗時(shí)約15.0 s，DAG生成約0.8 s，道路分類及高度計(jì)算26.2 s，模型構(gòu)建過程約53.0 s，交互操作約14.0 s。

表2 建模效果對(duì)比

圖11 區(qū)域3渲染圖

可以看出，利用DAG的拓?fù)涿枋鰞?yōu)勢能夠在較短時(shí)間內(nèi)完成模型構(gòu)建的工作，3個(gè)區(qū)域的自動(dòng)建模過程時(shí)間均在200.0 s以內(nèi)，相比手工建模大大節(jié)省了時(shí)間。本文方法使得領(lǐng)域外用戶也可以對(duì)層級(jí)關(guān)系復(fù)雜的立交橋快速構(gòu)建出符合大致要求的高精度模型。本文方法尚不能自動(dòng)解決立交結(jié)構(gòu)中下穿隧道的分層處理，需要在自動(dòng)計(jì)算之后由用戶手動(dòng)對(duì)計(jì)算結(jié)果進(jìn)行調(diào)整。

表3 本文方法對(duì)于不同實(shí)驗(yàn)區(qū)域的計(jì)算正確率

4.4 對(duì)比分析

對(duì)立交結(jié)構(gòu)進(jìn)行建模在城市規(guī)劃、交通仿真等領(lǐng)域有著重要的應(yīng)用價(jià)值[1-3]。應(yīng)用價(jià)值決定了衡量建模方法的優(yōu)劣可從建模效率、建成模型準(zhǔn)確程度等方面評(píng)價(jià)。當(dāng)前立交橋模型構(gòu)建的方法主要數(shù)據(jù)來源包括，帶有高度信息的高精度衛(wèi)星遙感數(shù)據(jù)和無高度信息的二維地圖數(shù)據(jù)2類。文獻(xiàn)[13]和[17]屬于這2類方法的典型工作。

本文從數(shù)據(jù)來源、計(jì)算結(jié)果、應(yīng)用范圍3個(gè)方面與文獻(xiàn)[13]和[17]進(jìn)行了對(duì)比。從數(shù)據(jù)來源方面比較，文獻(xiàn)[13]方法的數(shù)據(jù)源為高精度LIDAR數(shù)據(jù)，文獻(xiàn)[17]及本文方法均為二維柵格數(shù)據(jù)，相比文獻(xiàn)[13]數(shù)據(jù)更易獲取及處理，對(duì)于領(lǐng)域外的普通用戶更加友好。在建模結(jié)果正確性方面，文獻(xiàn)[13]數(shù)據(jù)源本身提供了高精度的高度信息，因此正確率最高。文獻(xiàn)[17]顯示其高度計(jì)算結(jié)果正確率較高，但由于算法限制，所能解決的立交結(jié)構(gòu)層數(shù)被限定在3層，應(yīng)用有限制。而本文方法由于采用了DAG描述立交結(jié)構(gòu)的拓?fù)潢P(guān)系，不會(huì)出現(xiàn)環(huán)路情形，在后續(xù)的高度計(jì)算過程中對(duì)于立交橋?qū)蛹?jí)沒有限制。表3結(jié)果表明，本文方法對(duì)于典型立交橋的道路分層計(jì)算結(jié)果正確率較高。通過對(duì)比3種方法(表4)，本文方法所需數(shù)據(jù)獲取簡單，在保證計(jì)算結(jié)果正確合理的基礎(chǔ)上，能對(duì)更多不同形態(tài)的立交橋進(jìn)行道路的層級(jí)關(guān)系推算。

表4 3種方法對(duì)比

5 結(jié) 論

本文提出將具有拓?fù)浔磉_(dá)優(yōu)勢的DAG用于立交結(jié)構(gòu)拓?fù)潢P(guān)系的描述。以二維柵格地圖作為輸入數(shù)據(jù)，將立交結(jié)構(gòu)道路抽象為DAG，可以方便地獲取道路之間的拓?fù)潢P(guān)系。根據(jù)道路的形態(tài)特點(diǎn)和功能特性，結(jié)合領(lǐng)域先驗(yàn)知識(shí)，進(jìn)行道路高度計(jì)算，最后通過基本組件的參數(shù)化建模方法，構(gòu)建城市立交結(jié)構(gòu)模型。對(duì)比現(xiàn)有方法，本文方法數(shù)據(jù)源易獲取、計(jì)算過程較為簡單。實(shí)驗(yàn)結(jié)果表明本文方法對(duì)于典型立交結(jié)構(gòu)的道路高度自動(dòng)計(jì)算結(jié)果正確率較高，簡化了立交結(jié)構(gòu)三維模型構(gòu)建的流程。

然而立交橋設(shè)計(jì)及建造之初就受到諸多因素的限制，因此有相當(dāng)部分的立交橋并不能用嚴(yán)格的分類方法對(duì)其進(jìn)行劃分。對(duì)于非典型形態(tài)的立交橋，本文方法計(jì)算效果不夠理想，后續(xù)的研究重點(diǎn)將在針對(duì)非典型形態(tài)的立交橋擴(kuò)充推算其道路層級(jí)關(guān)系的方法。

[1] 王華, 徐明亮, 毛天露, 等. 三維汽車群組動(dòng)畫仿真研究綜述[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2017, 29(2): 211-220. WANG H, XU M L, MAO T L et al. Survey of three-dimension traffic animation[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(2): 211-220 (in Chinese).

[2] SHEN J J, JIN X G. Detailed traffic animation for urban road networks[J]. Graphical Models, 2012, 74(5): 265-282.

[3] 劉耀丹. 立體交通三維道路網(wǎng)快速構(gòu)建算法研究[D]. 鄭州: 鄭州大學(xué), 2017. LIU Y D. Fast construction algorithm of the three-dimensional road network[D]. Zhengzhou: Zhengzhou University, 2017 (in Chinese).

[4] CHAO Q W, SHEN J J, JIN X G. Video-based personalized traffic learning[J]. Graphical Models, 2013, 75(6): 305-317.

[5] CHAO Q, JIN X, HUANG H W, et al. Force-based heterogeneous traffic simulation for autonomous vehicle testing[C]//2019 International Conference on Robotics and Automation (ICRA). New York: IEEE Press, 2019: 8298-8304.

[6] CHAO Q W, DENG Z G, REN J P, et al. Realistic data-driven traffic flow animation using texture synthesis[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(2): 1167-1178.

[7] PARISH Y I H, MüLLER P. Procedural modeling of cities[C]//The 28th Annual Conference on Computer Graphics and Interactive Techniques – SIGGRAPH’01. New York: ACM Press, 2001: 301-308.

[8] SUN J, YU X B, BACIU G, et al. Template-based generation of road networks for virtual city modeling[C]//Proceedings of the ACM Symposium on Virtual Reality Software and Technology – VRST’02. New York: ACM Press, 2002: 33-40.

[9] VANEGAS C A, GARCIA-DORADO I, ALIAGA D G, et al. Inverse design of urban procedural models[J]. ACM Transactions on Graphics (TOG), 2012, 31(6): 168.

[10] NISHIDA G, GARCIA-DORADO I, ALIAGA D G. Example-driven procedural urban roads[J]. Computer Graphics Forum, 2016, 35(6): 5-17.

[11] SONG A, WHITEHEAD J. TownSim: agent-based city evolution for naturalistic road network generation[C]// The 14th International Conference on the Foundations of Digital Games. New York: ACM Press, 2019: 1-9.

[12] 胡碧松, 龔建華. 大型立交橋三維建模方法研究[J]. 測繪科學(xué), 2008, 33(1): 100-102, 87, 248-249. HU B S, GONG J H. Research on 3D modeling method of large-scale overpass[J]. Surveying and Mapping Science, 2008, 33(1): 100-102, 87, 248-249 (in Chinese).

[13] 陳卓, 馬洪超. 基于機(jī)載LiDAR數(shù)據(jù)的大型立交橋自動(dòng)提取與建模方法[J]. 測繪學(xué)報(bào), 2012, 41(2): 252-258.CHEN Z, MA H C. Automatic extracting and modeling approach of city cloverleaf from airborne LiDAR data[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(2): 252-258 (in Chinese).

[14] 徐柱, 蒙艷姿, 李志林, 等. 基于有向?qū)傩躁P(guān)系圖的典型道路交叉口結(jié)構(gòu)識(shí)別方法[J]. 測繪學(xué)報(bào), 2011, 40(1): 125-131.XU Z, MENG Y Z, LI Z L, et al. Recognition of structures of typical road junctions based on directed attributed relational graph[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(1): 125-131 (in Chinese).

[15] 王驍, 錢海忠, 丁雅莉, 等. 采用拓?fù)潢P(guān)系與道路分類的立交橋整體識(shí)別方法[J]. 測繪科學(xué)技術(shù)學(xué)報(bào), 2013, 30(3): 324-328. WANG X, QIAN H Z, DING Y L, et al. The integral identification method of cloverleaf junction based on topology and road classification[J]. Journal of Geomatics Science andTechnology, 2013, 30(3): 324-328 (in Chinese).

[16] DENG M, FEI L. Research on modeling the overpasses for mapping and navigation[C]//Geoinformatics 2008 and Joint Conference on GIS and Built Environment: The Built Environment and Its Dynamics. Bellingham: International Society for Optics and Photonics (SPIE), 2008: 71442L.

[17] ZHAO X C, LIU Y D, WANG Y P. Automatic extraction and construction algorithm of overpass from raster maps[M]//Lecture Notes in Computer Science. Cham: Springer International Publishing, 2016: 479-489.

[18] WANG J, LAWSON G, SHEN Y Z. Automatic high-fidelity 3D road network modeling based on 2D GIS data[J]. Advances in Engineering Software, 2014, 76: 86-98.

[19] YANG B S, FANG L N, LI J. Semi-automated extraction and delineation of 3D roads of street scene from mobile laser scanning point clouds[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2013, 79: 80-93.

[20] LINDORFER M, BACKFRIEDER C, KIESLICH C, et al. Environmental-sensitive generation of street networks for traffic simulations[C]//2013 European Modelling Symposium. New York: IEEE Press, 2013: 457-462.

[21] CHEN G N, ESCH G, WONKA P, et al. Interactive procedural street modeling[C]//ACM SIGGRAPH 2008 Papers on – SIGGRAPH’08. New York: ACM Press, 2008: 1-10.

[22] TENG E, BIDARRA R. A semantic approach to patch-based procedural generation of urban road networks[C]//The International Conference on the Foundations of Digital Games – FDG’17. New York: ACM Press, 2017: 1-10.

[23] 李晉, 趙之仲, 黎奎. 公路設(shè)計(jì)新理念與案例分析[M]. 徐州: 中國礦業(yè)大學(xué)出版社, 2014: 220-222. LI P, ZHAO Z Z, LI K, et al. New concept of highway design and case analysis[M]. Xuzhou: China University of Mining and Technology Press, 2014: 220-222 (in Chinese).

[24] 宋培抗. 城市道路交叉口規(guī)劃與設(shè)計(jì)[M]. 天津: 天津大學(xué)出版社, 1995: 132-135. SONG P K. Urban Road intersection planning and design[M]. Tianjin: Tianjin University Press, 1995: 132-135 (in Chinese).

[25] 北京市市政設(shè)計(jì)研究院. 城市道路設(shè)計(jì)規(guī)范[EB/OL].(2006-06-20) [2020-04-20]. https://wenku.baidu.com/view/d2f32584e53a580216fcfef1.html. Beijing Municipal Design and Research Institute. Code for design of urban roads[EB/OL]. (2006-06-20)[2020-04-20]. https://wenku.baidu.com/view/d2f32584e53a580216fcfef1.html (in Chinese).

[26] 李尚林, 李琳, 曹明偉, 等. 面向真實(shí)構(gòu)建的徽州建筑快速建模方法[J]. 軟件學(xué)報(bào), 2016, 27(10): 2542-2556. LI S L, LI L, CAO M W, et al. Construction-oriented rapid modeling method on Huizhou architectures[J]. Journal of Software, 2016, 27(10): 2542-2556 (in Chinese).

Construction method of overpass structure based on directed acyclic graph

WANG Yu-kun1,2, CAO Li1,2, ZHAO Yang1,2, LI Lin1,2

(1. School of Computer Science and Information Technology, Hefei University of Technology, Hefei Anhui 230601, China; 2. Anhui Province Key Laboratory of Industry Safety and Emergency Technology, Hefei Anhui 230009, China)

Road information is an important element for a digital city. Modeling the overpass structure is of great significance to many areas, such as the simulation of urban traffic, traffic optimization, and urban planning. Although a great amount of research was conducted on the modeling of urban road networks, a targeted solution for the treatment of overpass structures remained to be put forward. Through the analysis of the overpass structure, a method for constructing overpass structures is proposed based on the directed acyclic graph, with the purpose of realizing efficient and high-quality modeling. Firstly, the two-dimensional raster data was preprocessed to extract effective road information. Secondly, a directed acyclic graphs (DAG) was constructed to express the topological relationship of overpass structure. Then, the height of each control point was calculated using the proposed height calculation method designed according to the structural characteristics, functional characteristics and related prior knowledge of the road. Finally, the overpass structure was constructed, based on the calculated road height and topological information with component units. The experiments selected three typical overpass structures in East China for testing. The results prove that the proposed method is advantageous in data acquisition and calculation accuracy and can help simplify the modeling process of overpass structures.

computer-aided modeling;heuristic modeling; urban road network; overpass structure; directed acyclic graph

TP 391

10.11996/JG.j.2095-302X.2020040583

A

2095-302X(2020)04-0583-10

2020-03-20；

2020-04-26

26 April，2020

20 March，2020；

國家重點(diǎn)研發(fā)計(jì)劃基金項(xiàng)目(2016YFC0800106)；國家自然科學(xué)基金項(xiàng)目(61602146)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(JZ2019YYPY0011)

National Key Research and Development Program of China (2016YFC0800106); National Natural Science Foundation of China (61602146); Fundamental Research Funds for the Central Universities (JZ2019YYPY0011)

王宇昆(1994-)，男，安徽安慶人，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)圖形與可視化。E-mail：wykhfut@163.com

WANG Yu-kun (1994-), male, master student. His main research interests cover computer graphics and visualization. E-mail：wykhfut@163.com

曹 力(1982-)，男，安徽績溪人，副教授，碩士。主要研究方向?yàn)橛?jì)算機(jī)圖形、計(jì)算幾何及數(shù)據(jù)可視化。E-mail：lcao@hfut.edu.cn

CAO Li (1982-), male, associate professor, master. His main research interests cover computer graphics, computational geometry and data visualization. E-mail：lcao@hfut.edu.cn