蔡 林,李英冰,鄒子昕
(武漢大學(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í)變化,且數(shù)據(jù)成本低,利用軌跡數(shù)據(jù)進(jìn)行挖掘與分析,能實(shí)現(xiàn)對某一區(qū)域路網(wǎng)幾何信息的獲取,使構(gòu)建或?qū)崟r(shí)更新道路地圖成為可能,如文獻(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ǔ)獲取新道路中心線,其精度會(huì)受到原有軌跡線的影響。第二種是聚類算法,將軌跡數(shù)據(jù)進(jìn)行聚類,從中提取中心線獲取路網(wǎng),如文獻(xiàn)[6]使用一種滾動(dòng)式聚類算法完成了道路拓?fù)涞纳珊徒徊婵诘淖R(shí)別。這類方法在軌跡數(shù)據(jù)量多的情形下,算法復(fù)雜,處理速度較慢。第三種是將軌跡數(shù)據(jù)轉(zhuǎn)為柵格數(shù)據(jù),通過軌跡點(diǎn)落入柵格點(diǎn)中個(gè)數(shù)確定柵格點(diǎn)的像素值,將柵格圖像中骨架線作為道路中心線,如文獻(xiàn)[7]在此基礎(chǔ)上從軌跡數(shù)據(jù)中構(gòu)建了路網(wǎng),但丟失原始軌跡的連通性,對路網(wǎng)拓?fù)涮崛≡斐衫щy,面對海量軌跡數(shù)據(jù),使用這類方法可實(shí)現(xiàn)一群軌跡點(diǎn)的聚類處理,而非單個(gè)點(diǎn),從而減少軌跡數(shù)據(jù)處理時(shí)間,但這類方法提取路網(wǎng),沒有顧及細(xì)化后交叉點(diǎn)細(xì)節(jié)變化及其提取,且忽略柵格點(diǎn)中軌跡點(diǎn)的速度、方向等有效信息,也沒有顧及近鄰車道、數(shù)據(jù)缺失對提取骨架線的影響。
筆者基于第三種方法設(shè)計(jì)了一種分級(jí)柵格化方法,不僅提升柵格化速度,且保留利用軌跡點(diǎn)方向、速度等信息;利用圖像膨脹算法將近鄰車道合并、斷開路段連接;使用改進(jìn)Zhang細(xì)化算法對柵格路網(wǎng)圖像進(jìn)行細(xì)化,提取道路交叉口、中心線,最后生成矢量路網(wǎng)。
軌跡數(shù)據(jù)生成路網(wǎng)柵格圖像的傳統(tǒng)過程為[8]:①確定柵格圖像中柵格大小和研究區(qū)域;②建立軌跡點(diǎn)和柵格對應(yīng)關(guān)系;③通過統(tǒng)計(jì)落入相應(yīng)柵格中的軌跡點(diǎn)個(gè)數(shù)確定柵格點(diǎn)的像素值,從而生成柵格圖像。
針對傳統(tǒng)方法為了追求計(jì)算速度而犧牲方向、速度等大量有用信息,筆者提出一種分級(jí)索引的柵格化方法。面對海量軌跡數(shù)據(jù),為提高柵格化效率,該方法對軌跡點(diǎn)落入的選取區(qū)域進(jìn)行分級(jí)處理,為保留和利用柵格中的信息,建立方向、速度和時(shí)間索引,如圖1所示。
圖1 索引方案
首先根據(jù)選取區(qū)域大小對其進(jìn)行分級(jí)處理,將選取區(qū)域分為3級(jí),分別對應(yīng)圖1中的Div、Grid以及Cell。對于提取道路中心線,Cell大小與車輛一致,約5 m×5 m,然后對Cell建立如圖1中的方向索引、時(shí)間索引、速度索引,其中方向索引將方向分為8個(gè)不同范圍,0~7代表不同方向,時(shí)間索引是以小時(shí)為單位,0~23代表不同時(shí)間段,速度索引是根據(jù)軌跡點(diǎn)速度大小將速度劃分為(0~9)10個(gè)不同范圍。
其次軌跡數(shù)據(jù)以天為單位進(jìn)行處理,對于每個(gè)屬于選取區(qū)域Div的軌跡點(diǎn),先記錄所屬于的Grid,然后尋找對應(yīng)Grid中軌跡點(diǎn)所屬的Cell,對應(yīng)Cell內(nèi)軌跡點(diǎn)統(tǒng)計(jì)數(shù)加一,且將軌跡點(diǎn)的方向、時(shí)間、速度信息分別落入Cell的方向、時(shí)間、速度索引的對應(yīng)范圍內(nèi)統(tǒng)計(jì)數(shù)也加一,這樣不僅能記錄Cell中的軌跡點(diǎn)個(gè)數(shù),而且能統(tǒng)計(jì)出Cell中不同方向、時(shí)段、速度范圍內(nèi)的軌跡點(diǎn)個(gè)數(shù)。
最后將多天同一Cell內(nèi)不同軌跡點(diǎn)個(gè)數(shù)相加,同時(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)圖像。
分級(jí)柵格化有兩個(gè)優(yōu)點(diǎn):①整個(gè)區(qū)域被分為不同級(jí)別,只對軌跡點(diǎn)落入Cell的前一級(jí)做計(jì)算,不針對整個(gè)選取區(qū)域做計(jì)算,速度相較于傳統(tǒng)柵格化會(huì)有所提高。②軌跡點(diǎn)的速度、方向等信息保留于柵格點(diǎn)中,且能利用其判斷軌跡點(diǎn)是否合理,能去除噪聲點(diǎn),從而提高柵格路網(wǎng)圖像的準(zhǔn)確性。但分級(jí)柵格化有兩個(gè)要點(diǎn):①根據(jù)選取區(qū)域分級(jí),區(qū)域越大,分級(jí)次數(shù)越多,最小的區(qū)域級(jí)別一定為Cell,Cell與Div之間的Grid可根據(jù)區(qū)域分為多級(jí);②Cell大小需控制,太大細(xì)節(jié)信息易丟失,太小近鄰車道明顯,會(huì)加大中心線提取難度。
獲取的柵格路網(wǎng)圖像中存在數(shù)據(jù)缺失導(dǎo)致路段斷開和近鄰車道的情形,斷開路段需連接,提取道路中心線要進(jìn)行近鄰車道合并,而膨脹算法可以使路段向周圍擴(kuò)張,同時(shí)將路段連接和合并車道。一種簡單快速的膨脹算法為依次掃描圖像中的像素點(diǎn),尋找灰度值為255的像素點(diǎn),分析該像素周圍8個(gè)像素點(diǎn),僅要8個(gè)像素點(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個(gè)點(diǎn)逆時(shí)針繞中心點(diǎn)分別記為P2,P3,…,P9,P2在P1上。標(biāo)記同時(shí)滿足下列條件的像素點(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)的個(gè)數(shù),S(P1)為以P為中心,其周圍8鄰域內(nèi)任一點(diǎn)開始,依次沿逆時(shí)針方向,從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à)值的,需過濾。
像素點(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)個(gè)數(shù),若有2個(gè),則該像素點(diǎn)為端點(diǎn),3個(gè)以上為交叉點(diǎn)。
路段提取分兩類,首先是端點(diǎn)至端點(diǎn)或交叉點(diǎn)間的路段,如圖3中數(shù)字為1部分的路段,其中數(shù)字為3部分是交叉點(diǎn),因細(xì)化后圖像為單像素寬度,則可從各端點(diǎn)出發(fā),依次在3×3鄰域?qū)ふ也?chǔ)存具有灰度值的點(diǎn),再以儲(chǔ)存的點(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)的各個(gè)像素值為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)合并為一個(gè)交叉點(diǎn),如圖4(b)所示,深色部分為交叉點(diǎn)。
經(jīng)過試驗(yàn),設(shè)置刪除長度小于或等于4個(gè)像素的路段,其大多都為間隔較近交叉點(diǎn)間的路段,路段刪除前后部分交叉口變化情況如圖4,圖中a、b為兩種不同的路口情況。
圖4 部分交叉口路段變化
刪除較短路段后,首先如果一個(gè)交叉點(diǎn)同時(shí)與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)插值出一個(gè)新交叉點(diǎn),將在這些路段中交叉點(diǎn)替換為新交叉點(diǎn),能將一個(gè)交叉點(diǎn)與多條路段相連接,獲取合并后的真正交叉點(diǎn),如圖4(b)所示,交叉點(diǎn)合并后路段較好連接,一個(gè)真交叉點(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)矢量圖文件。
筆者利用成都市某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,分級(jí)柵格化只需400 756 ms,兩者相比,分級(jí)柵格化速度有所提升。
選取區(qū)域經(jīng)分級(jí)柵格化、膨脹、細(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)中兩個(gè)區(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)中將交叉口化為一個(gè)點(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
針對目前利用軌跡數(shù)據(jù)實(shí)現(xiàn)構(gòu)建矢量路網(wǎng)的問題,提出利用分級(jí)柵格化和改進(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)造中車道識(shí)別也至關(guān)重要,研究中將車道合并,提取僅為道路中心線。這些研究有待于今后進(jìn)一步探索。