基于分級柵格化和改進(jìn)細(xì)化算法的軌跡數(shù)據(jù)路網(wǎng)生成研究

蔡 林，李英冰，鄒子昕

(武漢大學(xué) 測繪學(xué)院，湖北 武漢 430079)

當(dāng)前在城市中的出租車每天都生成海量軌跡數(shù)據(jù)，數(shù)據(jù)中蘊(yùn)含車輛狀態(tài)、人類行為等信息，這些信息對城市規(guī)劃、交通建設(shè)等有重要應(yīng)用價(jià)值[1]，從軌跡數(shù)據(jù)中挖掘居民出行特征等信息[2]、路網(wǎng)等城市建設(shè)信息[3]已成為研究的熱點(diǎn)。

近年我國城市道路建設(shè)迅速發(fā)展，但路網(wǎng)信息更新慢，現(xiàn)勢性無法滿足人們?nèi)找嬖鲩L的出行需求。傳統(tǒng)道路更新技術(shù)，如測量技術(shù)，周期較長且花費(fèi)成本高，而從遙感影像中提取路網(wǎng)相較于測量技術(shù)，周期短，效率高，但相比于從軌跡數(shù)據(jù)獲取路網(wǎng)信息，其過程較復(fù)雜、數(shù)據(jù)成本較高。軌跡數(shù)據(jù)不僅能反映路網(wǎng)實(shí)時變化，且數(shù)據(jù)成本低，利用軌跡數(shù)據(jù)進(jìn)行挖掘與分析，能實(shí)現(xiàn)對某一區(qū)域路網(wǎng)幾何信息的獲取，使構(gòu)建或?qū)崟r更新道路地圖成為可能，如文獻(xiàn)[4]利用軌跡地圖匹配技術(shù)，從路段周邊局部范圍內(nèi)的軌跡數(shù)據(jù)中提取并更新相關(guān)道路信息。

目前從軌跡數(shù)據(jù)中提取路網(wǎng)的方法主要有3種：第一種是將軌跡點(diǎn)連接成軌跡線，進(jìn)而融合成道路，如文獻(xiàn)[5]利用新軌跡與舊軌跡基于Delaunay三角網(wǎng)進(jìn)行融合獲取路網(wǎng)。這類方法是以舊軌跡線為基礎(chǔ)獲取新道路中心線，其精度會受到原有軌跡線的影響。第二種是聚類算法，將軌跡數(shù)據(jù)進(jìn)行聚類，從中提取中心線獲取路網(wǎng)，如文獻(xiàn)[6]使用一種滾動式聚類算法完成了道路拓?fù)涞纳珊徒徊婵诘淖R別。這類方法在軌跡數(shù)據(jù)量多的情形下，算法復(fù)雜，處理速度較慢。第三種是將軌跡數(shù)據(jù)轉(zhuǎn)為柵格數(shù)據(jù)，通過軌跡點(diǎn)落入柵格點(diǎn)中個數(shù)確定柵格點(diǎn)的像素值，將柵格圖像中骨架線作為道路中心線，如文獻(xiàn)[7]在此基礎(chǔ)上從軌跡數(shù)據(jù)中構(gòu)建了路網(wǎng)，但丟失原始軌跡的連通性，對路網(wǎng)拓?fù)涮崛≡斐衫щy，面對海量軌跡數(shù)據(jù)，使用這類方法可實(shí)現(xiàn)一群軌跡點(diǎn)的聚類處理，而非單個點(diǎn)，從而減少軌跡數(shù)據(jù)處理時間，但這類方法提取路網(wǎng)，沒有顧及細(xì)化后交叉點(diǎn)細(xì)節(jié)變化及其提取，且忽略柵格點(diǎn)中軌跡點(diǎn)的速度、方向等有效信息，也沒有顧及近鄰車道、數(shù)據(jù)缺失對提取骨架線的影響。

筆者基于第三種方法設(shè)計(jì)了一種分級柵格化方法，不僅提升柵格化速度，且保留利用軌跡點(diǎn)方向、速度等信息；利用圖像膨脹算法將近鄰車道合并、斷開路段連接；使用改進(jìn)Zhang細(xì)化算法對柵格路網(wǎng)圖像進(jìn)行細(xì)化，提取道路交叉口、中心線，最后生成矢量路網(wǎng)。

1 軌跡數(shù)據(jù)的索引與分級柵格化

軌跡數(shù)據(jù)生成路網(wǎng)柵格圖像的傳統(tǒng)過程為[8]：①確定柵格圖像中柵格大小和研究區(qū)域；②建立軌跡點(diǎn)和柵格對應(yīng)關(guān)系；③通過統(tǒng)計(jì)落入相應(yīng)柵格中的軌跡點(diǎn)個數(shù)確定柵格點(diǎn)的像素值，從而生成柵格圖像。

針對傳統(tǒng)方法為了追求計(jì)算速度而犧牲方向、速度等大量有用信息，筆者提出一種分級索引的柵格化方法。面對海量軌跡數(shù)據(jù)，為提高柵格化效率，該方法對軌跡點(diǎn)落入的選取區(qū)域進(jìn)行分級處理，為保留和利用柵格中的信息，建立方向、速度和時間索引，如圖1所示。

圖1 索引方案

首先根據(jù)選取區(qū)域大小對其進(jìn)行分級處理，將選取區(qū)域分為3級，分別對應(yīng)圖1中的Div、Grid以及Cell。對于提取道路中心線，Cell大小與車輛一致，約5 m×5 m，然后對Cell建立如圖1中的方向索引、時間索引、速度索引，其中方向索引將方向分為8個不同范圍，0～7代表不同方向，時間索引是以小時為單位，0～23代表不同時間段，速度索引是根據(jù)軌跡點(diǎn)速度大小將速度劃分為(0～9)10個不同范圍。

其次軌跡數(shù)據(jù)以天為單位進(jìn)行處理，對于每個屬于選取區(qū)域Div的軌跡點(diǎn)，先記錄所屬于的Grid，然后尋找對應(yīng)Grid中軌跡點(diǎn)所屬的Cell，對應(yīng)Cell內(nèi)軌跡點(diǎn)統(tǒng)計(jì)數(shù)加一，且將軌跡點(diǎn)的方向、時間、速度信息分別落入Cell的方向、時間、速度索引的對應(yīng)范圍內(nèi)統(tǒng)計(jì)數(shù)也加一，這樣不僅能記錄Cell中的軌跡點(diǎn)個數(shù)，而且能統(tǒng)計(jì)出Cell中不同方向、時段、速度范圍內(nèi)的軌跡點(diǎn)個數(shù)。

最后將多天同一Cell內(nèi)不同軌跡點(diǎn)個數(shù)相加，同時將不同索引范圍內(nèi)統(tǒng)計(jì)數(shù)相加，采用多天的軌跡數(shù)據(jù)，能夠補(bǔ)全部分缺少的道路信息。利用Cell速度索引中軌跡點(diǎn)速度信息和方位索引中軌跡點(diǎn)方位信息，去除Cell統(tǒng)計(jì)數(shù)中速度屬于高低速范圍或方向不合理的軌跡點(diǎn)，具有過濾噪聲的作用。若Cell中存在軌跡點(diǎn)，則像素值為0，不存在則為255，可得柵格路網(wǎng)圖像。

分級柵格化有兩個優(yōu)點(diǎn):①整個區(qū)域被分為不同級別，只對軌跡點(diǎn)落入Cell的前一級做計(jì)算，不針對整個選取區(qū)域做計(jì)算，速度相較于傳統(tǒng)柵格化會有所提高。②軌跡點(diǎn)的速度、方向等信息保留于柵格點(diǎn)中，且能利用其判斷軌跡點(diǎn)是否合理，能去除噪聲點(diǎn)，從而提高柵格路網(wǎng)圖像的準(zhǔn)確性。但分級柵格化有兩個要點(diǎn)：①根據(jù)選取區(qū)域分級，區(qū)域越大，分級次數(shù)越多，最小的區(qū)域級別一定為Cell，Cell與Div之間的Grid可根據(jù)區(qū)域分為多級；②Cell大小需控制，太大細(xì)節(jié)信息易丟失，太小近鄰車道明顯，會加大中心線提取難度。

2 快速膨脹與改進(jìn)細(xì)化算法在路網(wǎng)提取中的應(yīng)用

獲取的柵格路網(wǎng)圖像中存在數(shù)據(jù)缺失導(dǎo)致路段斷開和近鄰車道的情形，斷開路段需連接，提取道路中心線要進(jìn)行近鄰車道合并，而膨脹算法可以使路段向周圍擴(kuò)張，同時將路段連接和合并車道。一種簡單快速的膨脹算法為依次掃描圖像中的像素點(diǎn)，尋找灰度值為255的像素點(diǎn)，分析該像素周圍8個像素點(diǎn)，僅要8個像素點(diǎn)中存在灰度值為0的像素點(diǎn)，就設(shè)置該像素點(diǎn)灰度值為0。

經(jīng)膨脹算法處理后，路網(wǎng)圖像基本顯示路網(wǎng)特征，但路段為多像素寬度，提取路段較復(fù)雜。而用細(xì)化算法處理能保持圖像中黑色部分的拓?fù)浣Y(jié)構(gòu)，處理后表現(xiàn)為單像素寬度，圖中骨架線為道路中心線，筆者采用一種改進(jìn)Zhang細(xì)化算法。將膨脹后圖像二值化，對于具有道路信息點(diǎn)(像素值為0)，其像素值設(shè)為1，稱為目標(biāo)點(diǎn)；對無道路信息點(diǎn)(像素值為255)，將其像素值設(shè)為0，稱為背景點(diǎn)，可得簡單二值圖像。

改進(jìn)Zhang細(xì)化算法流程如下：

(1)尋找以目標(biāo)點(diǎn)為中心的8鄰域，記中心點(diǎn)為P1，其鄰域的8個點(diǎn)逆時針繞中心點(diǎn)分別記為P2，P3，…，P9，P2在P1上。標(biāo)記同時滿足下列條件的像素點(diǎn)：

①2≤N(P1)≤6

②S(P1)=1或B(P1)∈{65,5,20,80,13,22,52,133,141,54}

③P2×P4×P8=0或S(P2)!=1

④P2×P4×P6=0或S(P4)!=1

(2)去除所有滿足標(biāo)記的點(diǎn)，且將目標(biāo)點(diǎn)灰度值賦值為0，背景點(diǎn)灰度值賦值為255。

其中N(P1)為P的8鄰域內(nèi)非零鄰點(diǎn)的個數(shù)，S(P1)為以P為中心，其周圍8鄰域內(nèi)任一點(diǎn)開始，依次沿逆時針方向，從0到1的變化次數(shù)。B(P1)為P1鄰域點(diǎn)的二進(jìn)制編碼值S，計(jì)算公式如式(1)所示[9]，Pi的值為其像素值。

(1)

改進(jìn)Zhang細(xì)化算法使用5×5鄰域，在加大鄰域范圍基礎(chǔ)上改變原有Zhang算法細(xì)化條件，并添加了文獻(xiàn)[8]改進(jìn)條件。某一交叉口3種細(xì)化算法效果如圖2所示，其中淺色部分為膨脹后交叉口效果，深色部分為細(xì)化后效果。圖2(a)為Zhang細(xì)化算法，細(xì)化后非單像素寬度，路段交叉口處效果較差；圖2(b)為文獻(xiàn)[8]改進(jìn)細(xì)化算法，僅將圖2(a)改為單像素寬度；圖2(c)為筆者改進(jìn)Zhang細(xì)化算法，細(xì)化后為單像素寬度且交叉口較前兩種更為直觀、符合現(xiàn)實(shí)狀況，細(xì)化效果更好。

圖2 細(xì)化算法效果圖

圖2(a)、圖2(b)、圖2(c)相比，交叉口拓?fù)浣Y(jié)構(gòu)發(fā)生改變，主要是因細(xì)化過程不僅取決前次迭代結(jié)果，且取決本次迭代中已處理過像素點(diǎn)分布情況，與迭代次數(shù)、使用鄰域大小、細(xì)化條件有很大關(guān)系。三者本質(zhì)都是把多像素寬度路段細(xì)化為一條中心線，雖然交叉口等局部細(xì)節(jié)走向可能不同，但路段整體走向都是一致的。細(xì)化后圖像中依然存在著一些孤立像素點(diǎn)與較少像素點(diǎn)組成的像素段，是由軌跡數(shù)據(jù)發(fā)生漂移或者軌跡數(shù)據(jù)發(fā)生缺失等噪聲造成。對于提取路段來說，這部分像素是無價(jià)值的，需過濾。

3 從細(xì)化路網(wǎng)圖中提取路段構(gòu)建矢量路網(wǎng)

像素點(diǎn)所在行列為其坐標(biāo)，提取路段、路段交叉點(diǎn)、端點(diǎn)均用像素坐標(biāo)表示。提取路段前需進(jìn)行路段端點(diǎn)、交叉點(diǎn)的獲取，其思路為判斷某目標(biāo)像素點(diǎn)(像素值為0)3×3鄰域內(nèi)的其他目標(biāo)像素點(diǎn)個數(shù)，若有2個，則該像素點(diǎn)為端點(diǎn)，3個以上為交叉點(diǎn)。

路段提取分兩類，首先是端點(diǎn)至端點(diǎn)或交叉點(diǎn)間的路段，如圖3中數(shù)字為1部分的路段，其中數(shù)字為3部分是交叉點(diǎn)，因細(xì)化后圖像為單像素寬度，則可從各端點(diǎn)出發(fā)，依次在3×3鄰域?qū)ふ也Υ婢哂谢叶戎档狞c(diǎn)，再以儲存的點(diǎn)為開始，重復(fù)尋找，當(dāng)遇到其他交叉點(diǎn)或端點(diǎn)停止，可提取端點(diǎn)至端點(diǎn)或交叉點(diǎn)的路段。其次是交叉點(diǎn)至交叉點(diǎn)之間的路段，如圖3中數(shù)字為2部分，從某一交叉點(diǎn)3×3鄰域內(nèi)的各個像素值為0的點(diǎn)出發(fā)，類似于從端點(diǎn)出發(fā)提取路段，但當(dāng)遇到另一交叉點(diǎn)停止，則可提取交叉點(diǎn)至交叉點(diǎn)間所有路段。

圖3 路段提取示意圖

基于端點(diǎn)和交叉點(diǎn)提取在細(xì)化后圖像中的全部路段，但由較少像素點(diǎn)組成的路段是非必要的，這類路段主要是由圖像中間隔較近交叉點(diǎn)(實(shí)際在現(xiàn)實(shí)中同為一道路交叉點(diǎn))之間的路段組成，需將這些路段刪除，然后將這部分交叉點(diǎn)合并為一個交叉點(diǎn)，如圖4(b)所示，深色部分為交叉點(diǎn)。

經(jīng)過試驗(yàn)，設(shè)置刪除長度小于或等于4個像素的路段，其大多都為間隔較近交叉點(diǎn)間的路段，路段刪除前后部分交叉口變化情況如圖4，圖中a、b為兩種不同的路口情況。

圖4 部分交叉口路段變化

刪除較短路段后，首先如果一個交叉點(diǎn)同時與3條路段以上相連接，則該點(diǎn)一定為真正交叉點(diǎn)，按照這種思路對這類交叉點(diǎn)獲取，如圖4(a)，經(jīng)過此步，完成了部分真正交叉點(diǎn)的獲??；其次若在交叉點(diǎn)周圍存在其他交叉點(diǎn)，如圖4(b)刪除后，只需要從某一交叉點(diǎn)出發(fā)，在該交叉點(diǎn)鄰域范圍內(nèi)，搜索出其他交叉點(diǎn)，利用這些交叉點(diǎn)插值出一個新交叉點(diǎn)，將在這些路段中交叉點(diǎn)替換為新交叉點(diǎn)，能將一個交叉點(diǎn)與多條路段相連接，獲取合并后的真正交叉點(diǎn)，如圖4(b)所示，交叉點(diǎn)合并后路段較好連接，一個真交叉點(diǎn)至少與3條以上路段相連接，一條路段的首尾點(diǎn)必然是端點(diǎn)或者真正交叉點(diǎn)。

構(gòu)建矢量路網(wǎng)前，需用DP(Dougls-Pucker)算法進(jìn)行路段壓縮[10]，DP算法使原始曲線路段更加接近真實(shí)的道路和保持光滑形態(tài)，但必須選擇合適的閾值。本文選取的閾值為像素寬度0.8，代表真實(shí)距離為4 m左右，將提取路段進(jìn)行了DP算法壓縮。由于壓縮后路段的首尾點(diǎn)一定是端點(diǎn)或者真正交叉點(diǎn)，只需要將每條路段依次生成矢量路段，通過調(diào)用GDAL庫，生成了shpfile格式的路網(wǎng)矢量圖文件。

4 結(jié)果分析

筆者利用成都市某5 km×5 km區(qū)域20161101～20161108共8天滴滴出租車軌跡數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，共計(jì)66 196 629條，其中最小柵格Cell為5 m×5 m,傳統(tǒng)柵格化方法需427 678 ms，分級柵格化只需400 756 ms，兩者相比，分級柵格化速度有所提升。

選取區(qū)域經(jīng)分級柵格化、膨脹、細(xì)化且去噪后進(jìn)行矢量化處理的路網(wǎng)如圖5所示。

圖5 不同類型路網(wǎng)圖像

圖5(a)與圖5(b)相比，圖5(b)中道路中心線明顯，近鄰車道合并，斷開路段相連，更有利于從中提取道路中心線，但道路中心線是非單像素寬度。圖5(c)為該區(qū)域細(xì)化且去噪后的路網(wǎng)圖像，道路寬度為單像素寬度，與圖5(b)中路網(wǎng)拓?fù)湫畔⒒疽恢?。圖5(d)是圖5(a)的基礎(chǔ)上提取矢量路網(wǎng)，兩圖中道路中心線基本一致，說明了矢量路網(wǎng)的生成過程是正確的。

為說明生成路網(wǎng)的有效性，筆者選取矢量路網(wǎng)中兩個區(qū)域與相應(yīng)百度地圖路網(wǎng)相比，如圖6所示，矢量路網(wǎng)中的路段與真實(shí)地圖路網(wǎng)中路段相貼近，路段拓?fù)浣Y(jié)構(gòu)特征基本一致，但存在部分路段缺失，主要是因?yàn)檐壽E數(shù)據(jù)沒有覆蓋這些區(qū)域或區(qū)域內(nèi)軌跡點(diǎn)數(shù)量較少造成的。之后將提取真正交叉點(diǎn)的經(jīng)緯度坐標(biāo)與真實(shí)的道路交叉點(diǎn)坐標(biāo)進(jìn)行對比，選取圖6區(qū)域2的A、B、C 3點(diǎn)，對比結(jié)果如表1所示。通過對比，坐標(biāo)差在30 m左右，這類誤差主要由在提取交叉點(diǎn)中將交叉口化為一個點(diǎn)造成的，更進(jìn)一步證明本文從出租車軌跡數(shù)據(jù)中提取路網(wǎng)方案是可行的。

圖6 百度地圖與實(shí)驗(yàn)結(jié)果對比圖

表1 區(qū)域2中的交叉點(diǎn)坐標(biāo)對比

ID(a)中坐標(biāo)(°)(b)中坐標(biāo)(°)差距/mA104.078 992,30.713 222104.078 714,30.713 18331B104.078 943,30.715 717104.078 804,30.715 85322C104.076 161,30.714 127104.076 049,30.714 32926

5 結(jié)論

針對目前利用軌跡數(shù)據(jù)實(shí)現(xiàn)構(gòu)建矢量路網(wǎng)的問題，提出利用分級柵格化和改進(jìn)Zhang細(xì)化算法實(shí)現(xiàn)路網(wǎng)快速提?。焕眉?xì)化后路網(wǎng)柵格圖完成對路口端點(diǎn)、交叉點(diǎn)、矢量路網(wǎng)的提??；最后以成都市某5 km×5 km區(qū)域8天的滴滴出租車數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)論證。但由于路網(wǎng)復(fù)雜性，該方法還存在一定的不足，道路復(fù)雜的環(huán)形立交路段提取效果較差，路網(wǎng)構(gòu)造中車道識別也至關(guān)重要，研究中將車道合并，提取僅為道路中心線。這些研究有待于今后進(jìn)一步探索。