曹奇林, 徐本柱

(合肥工業(yè)大學 計算機與信息學院,安徽 合肥 230601)

近些年來,隨著地理信息系統(tǒng)(geographic information system,GIS)技術(shù)的應用普及,數(shù)字地圖的使用越來越廣泛,基于高精度數(shù)字地圖的定位越來越重要。由于山區(qū)全球定位系統(tǒng)(Global Positioning System,GPS)信號較弱,道路信息相比于城市路網(wǎng)不那么完善,對于精確數(shù)字地圖的需求就大大增加。

主曲線是第一線性主成分的一般化,由Hastie和Stuetzle于20世紀80年代提出,其目標是使用一條光滑曲線來近似描述數(shù)據(jù)集[1]?，F(xiàn)有的主曲線算法對于提取分散度大、高度彎曲及自相交等復雜形態(tài)數(shù)據(jù),效果不理想[2]。文獻[3]提出一種k段主曲線算法來提取主曲線,解決了該類問題。在軌跡融合方面,文獻[4]針對大量的鐵路軌道GPS定位數(shù)據(jù),提出采用非線性組合數(shù)據(jù)約簡模型來減少存儲空間,并利用二分法的思想提出3種算法,使得鐵路軌道數(shù)字地圖的獲取更簡單;文獻[5]提出了3種帶約束的主曲線算法,對于鐵道軌跡數(shù)據(jù)可以得到理想結(jié)果;文獻[6]研究了多鐵道軌跡信息融合問題,提出改進的融合算法,但是算法過程較為復雜,實用性較差;文獻[7]提出了一種曲線線路的表示方法,采用連續(xù)的線段近似表示鐵路軌道中的曲線形狀部分;文獻[8]提出要充分利用線路中存在的固定點,并給出了算法和模型,但是算法比較復雜,實用性差;文獻[9]研究了車輛的無線定位,為了提高定位的精度,提出使用軌跡融合的方法,并且進行了相關(guān)驗證試驗。

文獻[10]提出了3種面向鐵路軌跡信息的融合算法,分別是CPCLa、CPCLs及CPCLi。其中,CPCLa算法主要思想是通過不斷增加頂點最終得到一條滿足誤差要求的k段主曲線;CPCLs算法和CPCLi算法對CPCLa算法進行了改進,主要是利用一維搜索的方法和進一步優(yōu)化搜索空間的選擇。由于山區(qū)的復雜地理環(huán)境會對GPS信號產(chǎn)生影響,信號太弱時,GPS接收機可能無法定位,而信號太強時,也會對定位產(chǎn)生干擾,從而產(chǎn)生漂移現(xiàn)象[11],即出現(xiàn)與實際位置不符的情況。同時由于山區(qū)路況復雜,采集到的GPS軌跡數(shù)據(jù)在部分區(qū)域具有數(shù)據(jù)分布稀疏且不均勻的特點,或者數(shù)據(jù)中包含離群值,而現(xiàn)有的融合算法對于山區(qū)GPS軌跡數(shù)據(jù)的融合問題處理效果不佳。

針對此問題,本文首先介紹文獻[10]中的算法模型,然后對其進行優(yōu)化,提出一種改進的GPS軌跡融合算法,最后通過實測山區(qū)軌跡數(shù)據(jù)進行驗證。本文算法可以有效融合低精度GPS數(shù)據(jù),且計算效率高,節(jié)省了人力和成本,適用范圍更大。

1 問題建模

1.1 問題描述

因為一些山體的干擾、人為因素的影響等等,在山區(qū)采集的原始數(shù)據(jù)中會有很多的噪音數(shù)據(jù),無法直接使用,所以對其進行融合處理,最終結(jié)果采用折線段來描述實際曲線,即采樣點云的骨架。

本文研究的問題描述如圖1所示。

圖1 問題描述

設頂點為Pi(i=1,2,…,n),數(shù)據(jù)點為dj(j=1,2,…,s),Li表示以Pi、Pi+1兩點作為端點構(gòu)成的線段。

k段主曲線是包含一系列通過數(shù)據(jù)集“中央”的線段的曲線,一般地,k段主曲線通過從初始主成分分析(principal component analysis, PCA)解逐步添加頂點,并且最小化點到線段和頂點之間距離得到。而約束k段主曲線的目標是利用最近鄰原則在固定端點的前提下生成k段主曲線。根據(jù)最近鄰原則,所有的數(shù)據(jù)點都被劃分到對應的線段和頂點。采取的原則是首先計算每個數(shù)據(jù)點與主曲線的各個頂點以及所有線段的距離,然后比較這些距離值,最小的距離值對應的頂點或者線段就是該數(shù)據(jù)點的所屬區(qū)域。

1.2 數(shù)學模型

根據(jù)最近鄰原則需要得到數(shù)據(jù)點dj到對應線段Li的距離為:

DLi,j=[|(XPi+1-XPi)Ydj-(YPi+1-

YPi)Xdj+XPiYPi+1-XPi+1YPi|]/

[(XPi+1-XPi)2+(YPi+1-YPi)2]1/2

(1)

數(shù)據(jù)點dj到對應頂點Pi的距離為:

(2)

其中,Xdj、Ydj為數(shù)據(jù)點dj的X、Y軸坐標;XPi、YPi、XPi+1、YPi+1分別為頂點Pi、Pi+1的X、Y軸坐標。

將數(shù)據(jù)點到目標折線段上最近的頂點或線段的垂直距離定義為投影距離,假設線段Lv的頂點為Pv和Pv+1,相鄰數(shù)據(jù)點為tj′(j′=p,p+1,…,q),則線段Lv相鄰數(shù)據(jù)點的平均投影距離AD定義為:

(3)

約束條件為:AD

局部誤差閾值E的設置與數(shù)據(jù)有關(guān),E太小則有可能無法構(gòu)造主曲線,需要根據(jù)經(jīng)驗判斷,數(shù)據(jù)分布比較均勻時,E取值較小;否則E一般取值稍大。

2 基于主曲線的自適應融合算法

本文算法首先對GPS數(shù)據(jù)進行坐標系轉(zhuǎn)換,將經(jīng)緯度轉(zhuǎn)換成為適合處理的平面坐標。由于采集到的GPS軌跡數(shù)據(jù)分布不均勻,無法直接處理,因此需要對其進行預處理,清除由于采集數(shù)據(jù)時GPS手持機發(fā)生略微抖動或者微小位移產(chǎn)生的冗余數(shù)據(jù)和漂移點。具體算法步驟如下。

初始化:n=2,n表示頂點個數(shù)。P1=Ps,Pn=Pe,其中Ps、Pe分別為起點和終點。

(1) 連接Pn-1和Pn作為初始子主曲線Ln-1。

(2) 計算所有未使用過數(shù)據(jù)點到線段Ln-1的平均投影距離AD是否小于預設誤差閾值E,若滿足條件則進入步驟(4),否則進入步驟(3)。

(3)n=n+1,增加新頂點Pn-1,連接Pn-2、Pn-1構(gòu)成子主曲線,計算線段Ln-2的局部誤差AD′,判斷AD′是否小于E,若滿足,則從數(shù)據(jù)集中刪除使用過的數(shù)據(jù)點,同時以Pn-1為起點,繼續(xù)增加新頂點,直至數(shù)據(jù)集為空;若不滿足則更新頂點,得到新頂點Pn-1′,重復此步驟。

(4) 將各個頂點P1,…,Pn依次連接得到最終結(jié)果,即k段主曲線生成結(jié)束。

其中,步驟(3)中添加新頂點以及更新頂點的方式是:以Pn-2為圓心,所有未使用過的數(shù)據(jù)點dt(t=1,2,…,m)到圓心的距離最大值為半徑R畫圓,同時以R′=Rθ(θ此處取值為0.8)為半徑畫另一個圓,取落在圓環(huán)中的m′個數(shù)據(jù)點坐標的平均值作為新頂點的可能取值。

本文在構(gòu)造主曲線的過程中,對更新頂點步驟進行改進,考慮到山區(qū)GPS采集數(shù)據(jù)特點,當m′不為0時,將半徑縮小為原來的1/2,即R=R/2;當m′為0時,即無法根據(jù)所畫圓環(huán)獲得頂點的坐標,為了能夠順利構(gòu)造主曲線,將在區(qū)間[R,2R]中繼續(xù)尋找頂點,即R=R+R/2n,直到找到滿足誤差要求的頂點坐標。算法流程如圖2所示。

圖2 算法流程

3 實驗結(jié)果與分析

本文采用的實驗環(huán)境為Matlab R2016a, CPU為Intel(R) Core(TM) i5-4590(3.30 GHz),內(nèi)存4.00 GiB,Windows10操作系統(tǒng)。實驗數(shù)據(jù)是由黃山風景區(qū)索道管理人員采用手持GPS接收機人工采集,GPS手持機型號為GPSMAP 60CS,誤差范圍為15 m。

所采集的區(qū)域包括整個黃山風景區(qū)各個游覽路段的GPS數(shù)據(jù)信息。為了驗證本文算法對于復雜形狀路徑信息融合的可行性與適應度,選取黃山風景區(qū)鰲魚峰南北路口之間的一段路徑信息作為實驗對象,將采集到的51個軌跡點作為算法輸入,采用本文算法、文獻[10]中CPCLa算法及k段主曲線算法對該路段進行軌跡融合,最終結(jié)果如圖3所示。

圖3 3種算法生成結(jié)果

局部誤差閾值與算法精度之間的變化關(guān)系如圖4所示。

圖4 本文算法與CPCLa算法誤差變化曲線

2種算法的性能對比見表1所列。

表1 算法性能誤差比較

由圖3、圖4及表1可以看出:①k段主曲線算法由于涉及角度懲罰參數(shù)設置、沒有約束點和局部誤差閾值的概念,因此無法與另2種算法比較E和AD,且運算時間最長;② CPCLa算法對于復雜數(shù)據(jù)的適應性不好,對于預設誤差閾值的依賴度較高,由于沒有考慮數(shù)據(jù)分布分散的情況,得到的結(jié)果AD較大,而且與實際位置偏差較大,雖然頂點數(shù)較少(即節(jié)省了存儲空間),但是損失了計算精度;③ 本文算法可以提取符合實際曲線的處理結(jié)果,縮短軌跡生成時間,而且精度最高,占用內(nèi)存空間較小,適應性更強;④ CPCLa算法和本文算法的運算時間都較少,本文算法由于對CPCLa算法的頂點更新步驟進行了改進,因此本文算法可以獲得更高精度的結(jié)果。

經(jīng)過多次驗證實驗,在不同復雜度的樣本數(shù)據(jù)下,本文算法測試結(jié)果均表現(xiàn)良好,可以快速生成GPS軌跡融合結(jié)果,滿足高精度數(shù)字地圖的要求。

4 結(jié) 論

本文在主曲線思想的基礎(chǔ)上,采用已有的模型算法對山區(qū)GPS軌跡數(shù)據(jù)融合作了深入研究,提出一種改進的融合算法,適用范圍廣,算法性能較好;通過黃山風景區(qū)實測的GPS數(shù)據(jù)對算法進行驗證,實驗結(jié)果表明本文算法計算時間較少,占用存儲空間少,生成結(jié)果符合實際數(shù)據(jù)曲線,具有一定的現(xiàn)實意義。

后續(xù)研究將在目前所獲得的解的基礎(chǔ)上進行優(yōu)化,同時考慮相鄰線段之間的轉(zhuǎn)角對于生成軌跡結(jié)果的影響,使算法性能進一步提升,提高算法的魯棒性和計算精度等。