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

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

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

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

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

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

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

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

當(dāng)前已有大量針對城市路網(wǎng)、交通路網(wǎng)建模技術(shù)的研究工作[1-2,4-6]。針對城區(qū)尺度的道路網(wǎng)，研究者提出不同方法用于快速生成真實的城區(qū)規(guī)模道路網(wǎng)。如PARISH和MüLLER[7]采用L-system并以二維地圖數(shù)據(jù)作為輸入同時添加約束條件生成道路網(wǎng)；SUN等[8]提出基于模版的方法；VANEGAS等[9]提出前向反向建模相結(jié)合的方法；NISHIDA等[10]提出基于實例的方法；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]。已有大量針對立交結(jié)構(gòu)圖形表達(dá)及快速建模的研究。胡碧松和龔建華[12]給出了基于高分辨率遙感影像的大型立交結(jié)構(gòu)建模流程；陳卓和馬洪超[13]提出一種基于機載激光雷達(dá)數(shù)據(jù)(light detection and ranging，LIDAR)的立交橋建模方法。這些方法在參數(shù)設(shè)置、數(shù)據(jù)處理等方面對用戶的專業(yè)素養(yǎng)要求較高且成本高昂。文獻(xiàn)[14-16]提出了針對立交結(jié)構(gòu)拓?fù)潢P(guān)系的抽象表達(dá)，并應(yīng)用于對特定形態(tài)的立交結(jié)構(gòu)提取分類；文獻(xiàn)[17-18]提出了基于二維地圖數(shù)據(jù)的立交結(jié)構(gòu)快速建模方法，但對層數(shù)較多的復(fù)雜立交結(jié)構(gòu)建模效果不理想。

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

1 相關(guān)工作

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

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

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

針對在大尺度道路網(wǎng)中快速提取立交結(jié)構(gòu)的難點問題，提出立交結(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á)式，對不同立交結(jié)構(gòu)進(jìn)行抽象化描述。文獻(xiàn)[16]提出一種基于特征的3層數(shù)據(jù)模型，用于立交結(jié)構(gòu)的交通仿真，可描述簡單立交結(jié)構(gòu)的拓?fù)潢P(guān)系和層級關(guān)系，但對較復(fù)雜的立交結(jié)構(gòu)缺乏深入研究。這些抽象化描述方法并未用于立交結(jié)構(gòu)的建模，且在應(yīng)用時均存在一定的局限性。

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

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

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

綜上所述，目前針對城市道路網(wǎng)建模、立交結(jié)構(gòu)構(gòu)建及抽象化描述的研究較為廣泛。但所述方法在數(shù)據(jù)源獲取的難易性、層級關(guān)系計算及應(yīng)用范圍等方面均存在一定的局限，這是本文主要的研究動機。本文的研究內(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)特征信息描述方式。在對立交橋拓?fù)浣Y(jié)構(gòu)進(jìn)行抽象化描述時，直接參考平面道路的拓?fù)潢P(guān)系，如圖2(a)所示，僅能描述無匝道和引橋的平面交叉道路。研究者嘗試?yán)糜邢驁D(directed graph，DG)對道路結(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á)式模板庫，通過對比量化表達(dá)式達(dá)到識別目的；文獻(xiàn)[17]在數(shù)據(jù)處理階段將二維柵格地圖抽象為點和線構(gòu)成的DG再進(jìn)行分析。

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

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

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

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

圖2是采用DG和DAG對十字形道路交叉口描述的對比，為了使對比效果更明顯，這里僅畫出DAG部分連接關(guān)系。按照車輛行駛方向?qū)⒁粭l道路分為方向相反的2個方向，由+/–號代表不同車流方向。按照車流右行規(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án)路；圖2(c)的描述可以克服前2種方法的不足，更為合理。

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

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)對立交結(jié)構(gòu)分類。首先根據(jù)道路交匯個數(shù)將立交橋分為三肢和四肢2類，再根據(jù)其中包含的弧段個數(shù)對其繼續(xù)細(xì)分為喇叭口形、苜蓿葉形、環(huán)形、單圈形、多圈形、十字形6類。由此可將典型立交橋分為11類，如圖4所示。

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

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

表1 立交橋道路分類

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

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

圖5 核心流程

3.1 DAG的構(gòu)造

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

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

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

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

3.2 立交橋道路分層

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

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

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

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

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

3.3 道路控制點高度計算

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

方法3.匝道、引橋控制點高度計算方法

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

輸出：匝道、引橋控制點的高度。

4 建模及分析

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

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

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

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

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

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

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

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

4.2 基于基本組件建模

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

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

圖10 建模過程示例

4.3 建模結(jié)果

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

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

表2 建模效果對比

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

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

表3 本文方法對于不同實驗區(qū)域的計算正確率

4.4 對比分析

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

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

表4 3種方法對比

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)特點和功能特性，結(jié)合領(lǐng)域先驗知識，進(jìn)行道路高度計算，最后通過基本組件的參數(shù)化建模方法，構(gòu)建城市立交結(jié)構(gòu)模型。對比現(xiàn)有方法，本文方法數(shù)據(jù)源易獲取、計算過程較為簡單。實驗結(jié)果表明本文方法對于典型立交結(jié)構(gòu)的道路高度自動計算結(jié)果正確率較高，簡化了立交結(jié)構(gòu)三維模型構(gòu)建的流程。

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

[1] 王華, 徐明亮, 毛天露, 等. 三維汽車群組動畫仿真研究綜述[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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] 陳卓, 馬洪超. 基于機載LiDAR數(shù)據(jù)的大型立交橋自動提取與建模方法[J]. 測繪學(xué)報, 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)識別方法[J]. 測繪學(xué)報, 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)系與道路分類的立交橋整體識別方法[J]. 測繪科學(xué)技術(shù)學(xué)報, 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è)計新理念與案例分析[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è)計[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è)計研究院. 城市道路設(shè)計規(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] 李尚林, 李琳, 曹明偉, 等. 面向真實構(gòu)建的徽州建筑快速建模方法[J]. 軟件學(xué)報, 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；

國家重點研發(fā)計劃基金項目(2016YFC0800106)；國家自然科學(xué)基金項目(61602146)；中央高校基本科研業(yè)務(wù)費專項資金項目(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-)，男，安徽安慶人，碩士研究生。主要研究方向為計算機圖形與可視化。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-)，男，安徽績溪人，副教授，碩士。主要研究方向為計算機圖形、計算幾何及數(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