蔡 林,李英冰,鄒子昕
(武漢大學(xué) 測繪學(xué)院,湖北 武漢 430079)
當(dāng)前在城市中的出租車每天都生成海量軌跡數(shù)據(jù),數(shù)據(jù)中蘊含車輛狀態(tài)、人類行為等信息,這些信息對城市規(guī)劃、交通建設(shè)等有重要應(yīng)用價值[1],從軌跡數(shù)據(jù)中挖掘居民出行特征等信息[2]、路網(wǎng)等城市建設(shè)信息[3]已成為研究的熱點。
近年我國城市道路建設(shè)迅速發(fā)展,但路網(wǎng)信息更新慢,現(xiàn)勢性無法滿足人們?nèi)找嬖鲩L的出行需求。傳統(tǒng)道路更新技術(shù),如測量技術(shù),周期較長且花費成本高,而從遙感影像中提取路網(wǎng)相較于測量技術(shù),周期短,效率高,但相比于從軌跡數(shù)據(jù)獲取路網(wǎng)信息,其過程較復(fù)雜、數(shù)據(jù)成本較高。軌跡數(shù)據(jù)不僅能反映路網(wǎng)實時變化,且數(shù)據(jù)成本低,利用軌跡數(shù)據(jù)進(jìn)行挖掘與分析,能實現(xiàn)對某一區(qū)域路網(wǎng)幾何信息的獲取,使構(gòu)建或?qū)崟r更新道路地圖成為可能,如文獻(xiàn)[4]利用軌跡地圖匹配技術(shù),從路段周邊局部范圍內(nèi)的軌跡數(shù)據(jù)中提取并更新相關(guān)道路信息。
目前從軌跡數(shù)據(jù)中提取路網(wǎng)的方法主要有3種:第一種是將軌跡點連接成軌跡線,進(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ù),通過軌跡點落入柵格點中個數(shù)確定柵格點的像素值,將柵格圖像中骨架線作為道路中心線,如文獻(xiàn)[7]在此基礎(chǔ)上從軌跡數(shù)據(jù)中構(gòu)建了路網(wǎng),但丟失原始軌跡的連通性,對路網(wǎng)拓?fù)涮崛≡斐衫щy,面對海量軌跡數(shù)據(jù),使用這類方法可實現(xiàn)一群軌跡點的聚類處理,而非單個點,從而減少軌跡數(shù)據(jù)處理時間,但這類方法提取路網(wǎng),沒有顧及細(xì)化后交叉點細(xì)節(jié)變化及其提取,且忽略柵格點中軌跡點的速度、方向等有效信息,也沒有顧及近鄰車道、數(shù)據(jù)缺失對提取骨架線的影響。
筆者基于第三種方法設(shè)計了一種分級柵格化方法,不僅提升柵格化速度,且保留利用軌跡點方向、速度等信息;利用圖像膨脹算法將近鄰車道合并、斷開路段連接;使用改進(jìn)Zhang細(xì)化算法對柵格路網(wǎng)圖像進(jìn)行細(xì)化,提取道路交叉口、中心線,最后生成矢量路網(wǎng)。
軌跡數(shù)據(jù)生成路網(wǎng)柵格圖像的傳統(tǒng)過程為[8]:①確定柵格圖像中柵格大小和研究區(qū)域;②建立軌跡點和柵格對應(yīng)關(guān)系;③通過統(tǒng)計落入相應(yīng)柵格中的軌跡點個數(shù)確定柵格點的像素值,從而生成柵格圖像。
針對傳統(tǒng)方法為了追求計算速度而犧牲方向、速度等大量有用信息,筆者提出一種分級索引的柵格化方法。面對海量軌跡數(shù)據(jù),為提高柵格化效率,該方法對軌跡點落入的選取區(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ù)軌跡點速度大小將速度劃分為(0~9)10個不同范圍。
其次軌跡數(shù)據(jù)以天為單位進(jìn)行處理,對于每個屬于選取區(qū)域Div的軌跡點,先記錄所屬于的Grid,然后尋找對應(yīng)Grid中軌跡點所屬的Cell,對應(yīng)Cell內(nèi)軌跡點統(tǒng)計數(shù)加一,且將軌跡點的方向、時間、速度信息分別落入Cell的方向、時間、速度索引的對應(yīng)范圍內(nèi)統(tǒng)計數(shù)也加一,這樣不僅能記錄Cell中的軌跡點個數(shù),而且能統(tǒng)計出Cell中不同方向、時段、速度范圍內(nèi)的軌跡點個數(shù)。
最后將多天同一Cell內(nèi)不同軌跡點個數(shù)相加,同時將不同索引范圍內(nèi)統(tǒng)計數(shù)相加,采用多天的軌跡數(shù)據(jù),能夠補全部分缺少的道路信息。利用Cell速度索引中軌跡點速度信息和方位索引中軌跡點方位信息,去除Cell統(tǒng)計數(shù)中速度屬于高低速范圍或方向不合理的軌跡點,具有過濾噪聲的作用。若Cell中存在軌跡點,則像素值為0,不存在則為255,可得柵格路網(wǎng)圖像。
分級柵格化有兩個優(yōu)點:①整個區(qū)域被分為不同級別,只對軌跡點落入Cell的前一級做計算,不針對整個選取區(qū)域做計算,速度相較于傳統(tǒng)柵格化會有所提高。②軌跡點的速度、方向等信息保留于柵格點中,且能利用其判斷軌跡點是否合理,能去除噪聲點,從而提高柵格路網(wǎng)圖像的準(zhǔn)確性。但分級柵格化有兩個要點:①根據(jù)選取區(qū)域分級,區(qū)域越大,分級次數(shù)越多,最小的區(qū)域級別一定為Cell,Cell與Div之間的Grid可根據(jù)區(qū)域分為多級;②Cell大小需控制,太大細(xì)節(jié)信息易丟失,太小近鄰車道明顯,會加大中心線提取難度。
獲取的柵格路網(wǎng)圖像中存在數(shù)據(jù)缺失導(dǎo)致路段斷開和近鄰車道的情形,斷開路段需連接,提取道路中心線要進(jìn)行近鄰車道合并,而膨脹算法可以使路段向周圍擴張,同時將路段連接和合并車道。一種簡單快速的膨脹算法為依次掃描圖像中的像素點,尋找灰度值為255的像素點,分析該像素周圍8個像素點,僅要8個像素點中存在灰度值為0的像素點,就設(shè)置該像素點灰度值為0。
經(jīng)膨脹算法處理后,路網(wǎng)圖像基本顯示路網(wǎng)特征,但路段為多像素寬度,提取路段較復(fù)雜。而用細(xì)化算法處理能保持圖像中黑色部分的拓?fù)浣Y(jié)構(gòu),處理后表現(xiàn)為單像素寬度,圖中骨架線為道路中心線,筆者采用一種改進(jìn)Zhang細(xì)化算法。將膨脹后圖像二值化,對于具有道路信息點(像素值為0),其像素值設(shè)為1,稱為目標(biāo)點;對無道路信息點(像素值為255),將其像素值設(shè)為0,稱為背景點,可得簡單二值圖像。
改進(jìn)Zhang細(xì)化算法流程如下:
(1)尋找以目標(biāo)點為中心的8鄰域,記中心點為P1,其鄰域的8個點逆時針繞中心點分別記為P2,P3,…,P9,P2在P1上。標(biāo)記同時滿足下列條件的像素點:
①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)記的點,且將目標(biāo)點灰度值賦值為0,背景點灰度值賦值為255。
其中N(P1)為P的8鄰域內(nèi)非零鄰點的個數(shù),S(P1)為以P為中心,其周圍8鄰域內(nèi)任一點開始,依次沿逆時針方向,從0到1的變化次數(shù)。B(P1)為P1鄰域點的二進(jìn)制編碼值S,計算公式如式(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)實狀況,細(xì)化效果更好。
圖2 細(xì)化算法效果圖
圖2(a)、圖2(b)、圖2(c)相比,交叉口拓?fù)浣Y(jié)構(gòu)發(fā)生改變,主要是因細(xì)化過程不僅取決前次迭代結(jié)果,且取決本次迭代中已處理過像素點分布情況,與迭代次數(shù)、使用鄰域大小、細(xì)化條件有很大關(guān)系。三者本質(zhì)都是把多像素寬度路段細(xì)化為一條中心線,雖然交叉口等局部細(xì)節(jié)走向可能不同,但路段整體走向都是一致的。細(xì)化后圖像中依然存在著一些孤立像素點與較少像素點組成的像素段,是由軌跡數(shù)據(jù)發(fā)生漂移或者軌跡數(shù)據(jù)發(fā)生缺失等噪聲造成。對于提取路段來說,這部分像素是無價值的,需過濾。
像素點所在行列為其坐標(biāo),提取路段、路段交叉點、端點均用像素坐標(biāo)表示。提取路段前需進(jìn)行路段端點、交叉點的獲取,其思路為判斷某目標(biāo)像素點(像素值為0)3×3鄰域內(nèi)的其他目標(biāo)像素點個數(shù),若有2個,則該像素點為端點,3個以上為交叉點。
路段提取分兩類,首先是端點至端點或交叉點間的路段,如圖3中數(shù)字為1部分的路段,其中數(shù)字為3部分是交叉點,因細(xì)化后圖像為單像素寬度,則可從各端點出發(fā),依次在3×3鄰域?qū)ふ也Υ婢哂谢叶戎档狞c,再以儲存的點為開始,重復(fù)尋找,當(dāng)遇到其他交叉點或端點停止,可提取端點至端點或交叉點的路段。其次是交叉點至交叉點之間的路段,如圖3中數(shù)字為2部分,從某一交叉點3×3鄰域內(nèi)的各個像素值為0的點出發(fā),類似于從端點出發(fā)提取路段,但當(dāng)遇到另一交叉點停止,則可提取交叉點至交叉點間所有路段。
圖3 路段提取示意圖
基于端點和交叉點提取在細(xì)化后圖像中的全部路段,但由較少像素點組成的路段是非必要的,這類路段主要是由圖像中間隔較近交叉點(實際在現(xiàn)實中同為一道路交叉點)之間的路段組成,需將這些路段刪除,然后將這部分交叉點合并為一個交叉點,如圖4(b)所示,深色部分為交叉點。
經(jīng)過試驗,設(shè)置刪除長度小于或等于4個像素的路段,其大多都為間隔較近交叉點間的路段,路段刪除前后部分交叉口變化情況如圖4,圖中a、b為兩種不同的路口情況。
圖4 部分交叉口路段變化
刪除較短路段后,首先如果一個交叉點同時與3條路段以上相連接,則該點一定為真正交叉點,按照這種思路對這類交叉點獲取,如圖4(a),經(jīng)過此步,完成了部分真正交叉點的獲??;其次若在交叉點周圍存在其他交叉點,如圖4(b)刪除后,只需要從某一交叉點出發(fā),在該交叉點鄰域范圍內(nèi),搜索出其他交叉點,利用這些交叉點插值出一個新交叉點,將在這些路段中交叉點替換為新交叉點,能將一個交叉點與多條路段相連接,獲取合并后的真正交叉點,如圖4(b)所示,交叉點合并后路段較好連接,一個真交叉點至少與3條以上路段相連接,一條路段的首尾點必然是端點或者真正交叉點。
構(gòu)建矢量路網(wǎng)前,需用DP(Dougls-Pucker)算法進(jìn)行路段壓縮[10],DP算法使原始曲線路段更加接近真實的道路和保持光滑形態(tài),但必須選擇合適的閾值。本文選取的閾值為像素寬度0.8,代表真實距離為4 m左右,將提取路段進(jìn)行了DP算法壓縮。由于壓縮后路段的首尾點一定是端點或者真正交叉點,只需要將每條路段依次生成矢量路段,通過調(diào)用GDAL庫,生成了shpfile格式的路網(wǎng)矢量圖文件。
筆者利用成都市某5 km×5 km區(qū)域20161101~20161108共8天滴滴出租車軌跡數(shù)據(jù)進(jìn)行實驗,共計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)中的路段與真實地圖路網(wǎng)中路段相貼近,路段拓?fù)浣Y(jié)構(gòu)特征基本一致,但存在部分路段缺失,主要是因為軌跡數(shù)據(jù)沒有覆蓋這些區(qū)域或區(qū)域內(nèi)軌跡點數(shù)量較少造成的。之后將提取真正交叉點的經(jīng)緯度坐標(biāo)與真實的道路交叉點坐標(biāo)進(jìn)行對比,選取圖6區(qū)域2的A、B、C 3點,對比結(jié)果如表1所示。通過對比,坐標(biāo)差在30 m左右,這類誤差主要由在提取交叉點中將交叉口化為一個點造成的,更進(jìn)一步證明本文從出租車軌跡數(shù)據(jù)中提取路網(wǎng)方案是可行的。
圖6 百度地圖與實驗結(jié)果對比圖
表1 區(qū)域2中的交叉點坐標(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
針對目前利用軌跡數(shù)據(jù)實現(xiàn)構(gòu)建矢量路網(wǎng)的問題,提出利用分級柵格化和改進(jìn)Zhang細(xì)化算法實現(xiàn)路網(wǎng)快速提??;利用細(xì)化后路網(wǎng)柵格圖完成對路口端點、交叉點、矢量路網(wǎng)的提??;最后以成都市某5 km×5 km區(qū)域8天的滴滴出租車數(shù)據(jù)進(jìn)行了實驗論證。但由于路網(wǎng)復(fù)雜性,該方法還存在一定的不足,道路復(fù)雜的環(huán)形立交路段提取效果較差,路網(wǎng)構(gòu)造中車道識別也至關(guān)重要,研究中將車道合并,提取僅為道路中心線。這些研究有待于今后進(jìn)一步探索。