面向矢量路網(wǎng)的自適應(yīng)緊湊二維圖像表達(dá)方法

鄢鵬高，賈 濤

武漢大學(xué) 遙感信息工程學(xué)院，武漢430072

道路網(wǎng)絡(luò)是一種典型的非結(jié)構(gòu)化網(wǎng)絡(luò)數(shù)據(jù)，傳統(tǒng)的路網(wǎng)數(shù)據(jù)模型考慮道路的幾何形狀、拓?fù)溥B接和層次等級等信息對道路網(wǎng)絡(luò)進行建模，例如線性參考模型[1-2]、多尺度分層模型[3-4]、三維道路模型[5-6]以及單向行駛車道模型等[7-8]。這些數(shù)據(jù)模型充分保留了路網(wǎng)的拓?fù)湫畔?，并且能夠?qū)⒙肪W(wǎng)進行結(jié)構(gòu)化存儲。傳統(tǒng)的路網(wǎng)數(shù)據(jù)模型有利于海量路網(wǎng)數(shù)據(jù)的存儲，但是無法直觀地表示路網(wǎng)，這對于道路交通流的預(yù)測研究是不利的。

另一種路網(wǎng)建模方式與實體之間的空間映射有關(guān)，該方式在道路交通流的預(yù)測研究中占據(jù)了主流地位，其中圖網(wǎng)絡(luò)表示和柵格圖像表示是最常見的兩種映射方式：（1）圖網(wǎng)絡(luò)表示是將道路和交叉點映射為拓?fù)鋱D中的邊和節(jié)點[9]，該方式可以減少數(shù)據(jù)體量，而且可以借助復(fù)雜網(wǎng)絡(luò)的理論來研究路網(wǎng)的特性。但是該方式僅適合于小尺度范圍的路網(wǎng)表達(dá)[10-13]，而且只能維持路網(wǎng)的拓?fù)溥B接關(guān)系，無法維持道路之間的拓?fù)浞较蜿P(guān)系。（2）柵格圖像表示是將路網(wǎng)進行區(qū)域劃分，建立區(qū)域和格網(wǎng)之間的一一映射[14]，該方式能夠直觀地表達(dá)路網(wǎng)的整體分布，而且適合較大尺度范圍的路網(wǎng)表達(dá)[15-18]。但是由于格網(wǎng)本身的結(jié)構(gòu)特性，這種表示方法丟失了路網(wǎng)的空間拓?fù)潢P(guān)系。此外，它也容易受到空間分辨率的影響：高分辨率如1 km×1 km 以下的格網(wǎng)易產(chǎn)生稀疏格網(wǎng)圖像[16]，而低分辨率如3 km×3 km以上的格網(wǎng)則局限于較大區(qū)域的交通預(yù)測研究[17]。

鑒于此，本文提出一種矢量路網(wǎng)的自適應(yīng)二維緊湊圖像表達(dá)方法，在最大維持空間拓?fù)潢P(guān)系的前提下，能將具有不同結(jié)構(gòu)的矢量路網(wǎng)表達(dá)為緊湊二維圖像。該方法能夠在較大程度上直觀地表示原始路網(wǎng)的拓?fù)浣Y(jié)構(gòu)，并且能夠在大區(qū)域范圍下對各道路進行精細(xì)表達(dá)，解決了傳統(tǒng)路網(wǎng)數(shù)據(jù)模型不夠直觀、圖網(wǎng)絡(luò)模型受限于小區(qū)域范圍、格網(wǎng)劃分模型被空間分辨率制約等問題，為基于路網(wǎng)的交通預(yù)測問題研究提供了一種新的視角。

1 矢量路網(wǎng)的自適應(yīng)緊湊二維圖像表達(dá)與評價方法

1.1 矢量路網(wǎng)的自適應(yīng)緊湊圖像表達(dá)方法

本方法首先采用逐級分割的思想，對路網(wǎng)進行自適應(yīng)的逐級分割，得到一系列的子路網(wǎng)；然后利用路段間的相對位置關(guān)系，將每個子路網(wǎng)中的路段映射到各自的最小分割圖像中；最后按照第一步逐級分割的順序，將所有最小分割圖像進行拼接，得到最終的緊湊型二維圖像。本方法的主要步驟如下：

（1）基于自適應(yīng)的路網(wǎng)逐級最優(yōu)分割

首先，構(gòu)建路網(wǎng)分割方案的三叉樹結(jié)構(gòu)，如圖1（a）第一部分所示。將路網(wǎng)進行逐級分割，每次分割依次采用三種分割方案，每種方案將路網(wǎng)按照空間位置關(guān)系劃分為(i∈{1,2,3})份，使得每份中的路段數(shù)目大致相同；對分割后的子路網(wǎng)再次進行分割，直到滿足分割停止條件。針對不同路網(wǎng)，該過程能夠構(gòu)建相應(yīng)深度的三叉樹結(jié)構(gòu)。其次，通過搜索三叉樹獲取路網(wǎng)最優(yōu)分割方案。利用自下而上的方式遍歷三叉樹，得到所有路網(wǎng)分割方案路徑，計算每條路徑對應(yīng)的圖像填充率，將圖像填充率最高的路徑作為最優(yōu)分割方案。針對同一路網(wǎng)，該過程能夠自動調(diào)整每一級的分割方案。

圖1（a） 算法示意圖

具體而言，基于自適應(yīng)的路網(wǎng)逐級最優(yōu)分割的流程如下：

①設(shè)置初始化變量。利用路段中點表示路段，得到路段中點集合P；設(shè)置分割方案取值為v1=2,v2=3,v3=5,這三種方案在每一級分割中避免將路網(wǎng)劃分成過多的子路網(wǎng)，從而維持一定的拓?fù)潢P(guān)系，而在整體的多級分割中，各級的方案經(jīng)過組合可以形成多種分割策略，從而適應(yīng)不同的路網(wǎng)；設(shè)置子路網(wǎng)所包含的最少路段數(shù)目候選集sGrid={22,32,52}，作為分割停止條件。

②構(gòu)建三叉樹結(jié)構(gòu)。根節(jié)點的值為 |P|，子節(jié)點的值從左到右依次為，邊權(quán)值依次為{v1,v2,v3}；各子節(jié)點保持生長直到其值屬于sGrid,則該節(jié)點停止生長，并設(shè)為葉節(jié)點。

③獲取最優(yōu)分割方案。遍歷三叉樹的葉節(jié)點，建立各葉節(jié)點到根節(jié)點的路徑，從所有的路徑中找到圖像填充率最高的路徑，并用其逆序的邊權(quán)值向量W={w1,w2,…,wn}表示最優(yōu)分割方案；同時，記錄該路徑葉節(jié)點的值c2∈sGrid。

④根據(jù)最優(yōu)分割方案，對P進行逐級分割。在第k(k=1,2,…,n)級分割中，先后在X方向和Y方向上對路網(wǎng)進行wk均分，對分割后的所有子路網(wǎng)進行下一級分割，最終得到個子路網(wǎng)，每個子路網(wǎng)對應(yīng)一個最小分割圖像，且其中的路段數(shù)不超過c2。具體算法的偽代碼如下：

（2）最小分割圖像中的路段映射

最優(yōu)分割方案確定了每個子路網(wǎng)所對應(yīng)的最小分割圖像，且由于每個子路網(wǎng)中路段數(shù)目較少，路段之間的空間拓?fù)潢P(guān)系相對簡單，因此可以通過相對位置關(guān)系將每個路段映射到最小分割圖像中的相應(yīng)位置。如圖1（a）第二部分所示，將子路網(wǎng)中的路段分別按照X方向和Y方向進行排序，得到各路段在兩個方向上的相對位置關(guān)系，然后根據(jù)相對位置關(guān)系將路段一一映射到最小分割圖像中。路段映射算法的具體流程如下：

①任取一個子路網(wǎng)并記為Q，Q中每個路段中心點具有經(jīng)度q.lon和緯度q.lat。

②按照X方向?qū)中所有點進行排序，從而確定每個點在X方向上的相對位置關(guān)系。

③按照Y方向?qū)中所有點進行排序，從而確定每個點在Y方向上的相對位置關(guān)系。

④根據(jù)②③所確定的相對位置關(guān)系，將所有點映射到尺寸為c×c的最小分割圖像中。

圖1（a）第二部分中紅色點和黑色點在X方向上有相同的位置，但是在Y方向上，黑色點在紅色點的上方，由此可以確定兩點在圖像中的位置關(guān)系，同理可得到其他點的映射，該算法的偽代碼如下所示。

基于自適應(yīng)的路網(wǎng)逐級最優(yōu)分割算法盡可能保持路網(wǎng)的全局拓?fù)潢P(guān)系，而路段映射算法根據(jù)路段的相對位置關(guān)系，將路段映射到緊湊的最小分割圖像中，盡可能保持路網(wǎng)的局部拓?fù)潢P(guān)系。經(jīng)過上述兩步，最終得到了矢量路網(wǎng)的緊湊型二維圖像表示。圖1（b）為路網(wǎng)示意圖，圖中線條顏色的深淺用于區(qū)分各路段；采用矢量路網(wǎng)的緊湊型二維圖像表示算法，將圖1（b）中路網(wǎng)轉(zhuǎn)化為圖1（c）中的緊湊型二維圖像?？梢钥吹?，圖1（b）中有24 條路段，其中x、h、o路段位于路網(wǎng)中心區(qū)域，a、d、j、m路段位于路網(wǎng)邊界；經(jīng)過轉(zhuǎn)化之后，圖1（c）中共有25 個像素（包含一個空白像素），其中x、h、o路段的中心聚集特性得到保留，a、d、j、m路段的邊界特性也得到保留。

圖1（b） 轉(zhuǎn)化前的路網(wǎng)

圖1（c） 轉(zhuǎn)化后的矩陣表示

1.2 評價方法

由于轉(zhuǎn)化后圖像中存在部分未填充的像素（空值像素），這些空值像素不攜帶任何信息，因此應(yīng)該盡量減少空值像素的比例即提高非空值像素的比例。據(jù)此，本文采用圖像填充率來定量描述路網(wǎng)的轉(zhuǎn)化圖像的緊湊性。定義整個路網(wǎng)所包含的路段集合為S，轉(zhuǎn)化后的圖像尺寸為M×M，則轉(zhuǎn)化后圖像的填充率為：

此外，在矢量路網(wǎng)轉(zhuǎn)化為緊湊型二維圖像的過程中，空間拓?fù)潢P(guān)系會發(fā)生一定的變化。為此，本文提出了兩個指標(biāo)用于定量計算并評價拓?fù)潢P(guān)系的變化程度，即拓?fù)溥B接誤差和拓?fù)浞较蛘`差。

（1）拓?fù)溥B接誤差

在矢量路網(wǎng)中，定義兩個相連路段的拓?fù)溥B接距離為1。如圖2（a）所示，路段x的相連路段為{g,h,k,w,l}，那么x和{g,h,k,w,l} 的拓?fù)溥B接距離向量為={1,1,1,1,1}；如圖2（b）所示，矢量路網(wǎng)的二維圖像表示中，任意兩個像素（路段）的拓?fù)溥B接距離定義為max(Δx,Δy)，那么x和{g,h,k,w,l}的拓?fù)溥B接距離向量為={1,1,2,2,1}。由此，可以定義轉(zhuǎn)化后x路段的拓?fù)溥B接誤差為，整個路網(wǎng)轉(zhuǎn)化后的平均拓?fù)溥B接誤差公式如下：

圖2（a） 轉(zhuǎn)化前的拓?fù)溥B接誤差示意圖

圖2（b） 轉(zhuǎn)化后的拓?fù)溥B接誤差示意圖

（2）拓?fù)浞较蛘`差

在矢量路網(wǎng)中，定義兩個路段中心點連線的方位角為它們之間的拓?fù)浞轿唤?，如圖2（c）所示，路段a與路段b的拓?fù)浞轿唤菫椤Ｔ诙S圖像中，任意兩個像素（路段）的拓?fù)浞轿唤菫橄袼刂行狞c連線的方位角，如圖2（d）所示，像素a和像素b的拓?fù)浞轿唤菫?。因此，路段a和b的拓?fù)浞较蛘`差可以定義為=，路段a的拓?fù)浞较蛘`差定義為，其中U表示路段a的一階拓?fù)渎范渭?，即U={b,c,d}，整個路網(wǎng)轉(zhuǎn)化之后的平均拓?fù)浞较蛘`差公式如下：

圖2（c） 轉(zhuǎn)化前的拓?fù)浞较蛘`差示意圖

圖2（d） 轉(zhuǎn)化后的拓?fù)浞较蛘`差示意圖

2 實驗與分析

2.1 世界主要城市路網(wǎng)的案例研究

為了驗證本文方法的有效性與合理性，選取了世界重要城市的路網(wǎng)數(shù)據(jù)進行實驗。實驗中，將本文方法與隨機編碼、順序編碼的方法進行對比，分別計算三種編碼方式的拓?fù)溥B接誤差和拓?fù)浞较蛘`差。隨機編碼方式下，每條路段被賦予隨機二維坐標(biāo)，得到隨機二維圖像矩陣；順序編碼下，路段按照經(jīng)度從低到高、緯度從高到低進行排序，將排序后的路段依次填入圖像矩陣中。

根據(jù)城市的政治和經(jīng)濟重要性，在世界范圍內(nèi)均勻選取了十個重要的城市：北京、武漢、上海、紐約、洛杉磯、倫敦、巴黎、柏林、慕尼黑和斯德哥爾摩，這些城市都是相應(yīng)國家的首都或經(jīng)濟中心，具有較高的研究價值。獲取十個城市的路網(wǎng)數(shù)據(jù)后（OpenStreetMap），對道路屬性進行篩選，保留一級道路、二級道路、三級道路和高速公路，然后利用本文方法得到這十個城市矢量路網(wǎng)的緊湊二維圖像表達(dá)。以下以倫敦和北京為例，對本文算法的轉(zhuǎn)化結(jié)果進行可視化，并將本文算法和其他算法的轉(zhuǎn)化誤差進行了比較與可視化。

圖3（a）為倫敦路網(wǎng)的真實地理拓?fù)浣Y(jié)構(gòu)，圖3（b）為運用本文算法轉(zhuǎn)化后的倫敦路網(wǎng)的二維圖像表示，其中黑色像素點代表無路段填充，其他顏色的像素點代表有路段填充，整個圖像的填充率達(dá)到97.92%。同理，圖3（c）和（d）分別顯示了北京路網(wǎng)及其轉(zhuǎn)化后的二維圖像，整個圖像的填充率為94.42%。

圖3（a） 倫敦路網(wǎng)的地理拓?fù)浣Y(jié)構(gòu)

圖3（b） 倫敦路網(wǎng)的二維圖像表示

圖3（c） 北京路網(wǎng)的地理拓?fù)浣Y(jié)構(gòu)

圖3（d） 北京路網(wǎng)的二維圖像表示

圖4 顯示了對倫敦路網(wǎng)分別采用本文方法和隨機編碼、順序編碼進行轉(zhuǎn)化后的誤差，每條路段的顏色代表了該路段拓?fù)浞较蛘`差或拓?fù)溥B接誤差的取值大小。從拓?fù)溥B接誤差上看，采用本文方法轉(zhuǎn)化的結(jié)果（圖4（a））最優(yōu)，各路段的誤差集中在2 以下，而隨機編碼（圖4（b））的誤差集中在56 以上、順序編碼（圖4（c））的誤差集中在11左右。三種算法的表現(xiàn)在拓?fù)浞较蛘`差上也有著相似的結(jié)果，采用本文方法（圖4（a））轉(zhuǎn)化后的各路段的誤差集中在1.1以下，而隨機編碼（圖4（b））和順序編碼（圖4（c））的誤差均集中在1.7左右。圖5顯示了對北京路網(wǎng)分別采用上述三種算法進行轉(zhuǎn)化后的誤差，與倫敦的結(jié)果相似，本文方法的轉(zhuǎn)化效果最好。

圖4 倫敦路網(wǎng)的表達(dá)效果評價

圖5 北京路網(wǎng)的表達(dá)效果評價

其余城市路網(wǎng)的實驗結(jié)果如表1 所示，可以看出，本文方法在這兩種類型的路網(wǎng)上都具有較好的性能，其二維圖像填充率都能達(dá)到90%以上。此外，本文方法產(chǎn)生的平均拓?fù)溥B接誤差低于2.31，平均拓?fù)浞较蛘`差低于0.97，相比于隨機編碼和順序編碼，本文方法具有最好的空間拓?fù)潢P(guān)系保持能力。

表1 十個主要城市路網(wǎng)的二維圖像表達(dá)結(jié)果及評價

2.2 我國324個主要城市路網(wǎng)案例研究

為了進一步驗證本文方法的有效性與合理性，從OpenStreetMap（OSM）上獲取我國324 個主要城市的路網(wǎng)進行實驗。如圖6（a）所示，經(jīng)過統(tǒng)計，約95%的城市矢量路網(wǎng)的二維圖像填充率達(dá)到85%以上，這說明本文算法能夠適應(yīng)中國大部分城市路網(wǎng)；此外，沿海地區(qū)和中部城市路網(wǎng)的二維圖像填充率較高，而西部城市的較低，這是因為沿海和中部城市較為發(fā)達(dá)，路網(wǎng)相對更加密集，因此二維圖像填充率較高。

圖6 我國324個主要城市路網(wǎng)的實驗結(jié)果

圖6（b）和（c）顯示，這些城市的平均拓?fù)溥B接誤差集中在1.98 附近，平均拓?fù)浞较蛘`差集中在0.82 附近，且所有城市的空間拓?fù)湔`差都較小，這說明了本文算法的有效性。此外，沿海地區(qū)的平均拓?fù)溥B接誤差相對較高，而拓?fù)浞较蛘`差相對較低，這與中西部城市呈現(xiàn)的結(jié)果相反。這是因為沿海地區(qū)的城市更為發(fā)達(dá)，路網(wǎng)結(jié)構(gòu)更加復(fù)雜，一條路段往往有多條拓?fù)湎噜徛范?。由于任意格網(wǎng)最多有4 個格網(wǎng)與之距離為1，因此當(dāng)路段的拓?fù)渎范芜^多時，格網(wǎng)反映拓?fù)溥B接關(guān)系的能力減弱，因此拓?fù)溥B接誤差增大。相反地，由于中西部城市的路網(wǎng)密度相對較低，為了提高二維圖像的填充率，路段之間的方向拓?fù)潢P(guān)系會受到更大的影響，因此拓?fù)浞较蛘`差會變大。

3 結(jié)束語

本文提出了一種矢量路網(wǎng)的緊湊型二維圖像表示方法，主要包括自適應(yīng)的逐級分割算法和最小分割圖像中的路段映射算法。該方法解決了現(xiàn)存路網(wǎng)表達(dá)中存在的空間拓?fù)鋪G失和空間分辨率不易確定等問題。本文選取了中外數(shù)百個城市路網(wǎng)進行實證研究，以拓?fù)溥B接誤差和拓?fù)浞较蛘`差為評價標(biāo)準(zhǔn)，與常見的隨機編碼和順序編碼方法進行了比較。實驗結(jié)果表明，大多數(shù)城市路網(wǎng)可以表達(dá)為具有較高填充率的二維圖像，且圖像具有最高的拓?fù)浔３帜芰Α?/p>

本文方法為基于深度學(xué)習(xí)的交通流預(yù)測研究提供了一種新的數(shù)據(jù)表示方法：傳統(tǒng)方法常用柵格表示路網(wǎng)交通流，這只能描述某個區(qū)域內(nèi)整體的交通流，而本文的方法能夠?qū)⒙肪W(wǎng)交通流轉(zhuǎn)化為“低失真”的二維圖像，從而可以精確地表示各條道路的交通流，達(dá)到精確預(yù)測道路交通流的目的。本文方法已經(jīng)運用在武漢市道路交通流預(yù)測[19]中，將武漢市內(nèi)35 575條道路轉(zhuǎn)為為192×192的緊湊型二維圖像，通過構(gòu)建端到端的深度學(xué)習(xí)模型對城市尺度下道路級的交通流進行了預(yù)測，預(yù)測結(jié)果表明本文的方法是合理且有效的。

此外，本文方法也存在一定的局限性：對于外形不規(guī)則的城市路網(wǎng)，本文算法統(tǒng)一轉(zhuǎn)化為正方形圖像，這會增大轉(zhuǎn)化結(jié)果的拓?fù)湔`差；將最小分割圖像進行拼接時，沒有考慮兩兩圖像交界處的路段拓?fù)潢P(guān)系，從而造成一定的拓?fù)湔`差；構(gòu)建自適應(yīng)的轉(zhuǎn)化算法時，只考慮了圖像填充率的自適應(yīng)，沒有考慮拓?fù)湔`差的自適應(yīng)?？紤]上述因素，設(shè)計適應(yīng)不同城市路網(wǎng)形狀、考慮拼接邊緣拓?fù)潢P(guān)系、融合拓?fù)湔`差自適應(yīng)的算法，使得轉(zhuǎn)化后的二維圖像具有最小的拓?fù)湔`差和最大的圖像填充率，這將會是后續(xù)路網(wǎng)圖像表示算法的重要研究方向之一。