GPS航跡線的自適應折半查找化簡算法

王 靜,譚祥爽,宋現鋒,,汪超亮

(1.中國科學院大學資源與環境學院,北京 100049; 2.中國科學院光電研究院,北京 100094)

GPS航跡線的自適應折半查找化簡算法

王 靜1,譚祥爽1,宋現鋒1,2,汪超亮2

(1.中國科學院大學資源與環境學院,北京 100049; 2.中國科學院光電研究院,北京 100094)

提出了一種新的全球定位系統(GPS)航跡線自適應折半查找化簡算法,采用了Sleeve-fitting算法的最優骨架點判斷模式來保證航跡線的化簡質量,通過粗篩與精選相結合的分步處理方式來提高化簡效率:粗篩是利用經驗步長值動態預測下一步搜索步長,快速確定包含骨架點的搜索區間;精選是在搜索區間內利用折半查找的方式搜索到骨架點.將某市城區的GPS航跡數據應用于文中算法,結果表明,該算法大幅度提高了化簡效率,同時最大程度地保持了化簡后航跡線與原始航跡在形態特征上的一致性.

GPS航跡;線化簡;折半查找;最優骨架點

隨著衛星導航系統的普及,出租車、公交車以及各種巡查車輛都安裝了低成本的全球定位系統(GPS)接收機,遍及城市的各條街道,用于實時監測車輛運行.這些定位數據精度低,但是覆蓋范圍廣、數據量大,已經逐漸成為交通路網提取的主要數據源.為了在道路轉彎處獲取精確的結果,通常GPS接收機以1 s甚至更小的頻率采集道路坐標數據.采樣點越密集,則越貼近原始道路的空間分布,但隨之而來的數據量急劇增大,對其管理和分析都帶來了困難[1].比如,不同尺度地圖展示的道路詳細程度存在差異,在給定尺度較為容易顯示的地圖信息,則無法有效地在較小尺度上展示[2].因此,需要對GPS航跡線進行有效化簡,剔除平直道路區大量的冗余點,轉彎的路口區保留較多的點,以最大程度反映原始道路的形態特征.

國內外學者圍繞曲線化簡問題進行了深入研究,但是當前方法對于GPS航跡線化簡的適用性受到限制.Mc Master將化簡算法劃分為:獨立點算法、局部處理算法、無限制條件的局部處理擴展算法、有限制條件的局部處理擴展算法以及全局算法[3].其中,獨立算法以固定間隔選取航跡點,不能保證最優航跡點(骨架點)被保留下來,化簡結果失真度大.全局算法中應用最廣泛的Douglas-Peucker算法[4],不能解決GPS航跡線中航跡重復、交叉以及起點與終點相近或重疊的問題.根據以上分析,GPS航跡線化簡需要采用一種局部化簡算法.近幾年,諸多學者提出遺傳、小波變換等人工智能算法進行曲線化簡[5-7],但是算法實現過程復雜,不適合大數據量的GPS航跡線的快速化簡需求.

為此,筆者提出了一種GPS航跡線的自適應折半查找化簡算法.該算法采用了Sleeve-fitting算法的最優骨架點判斷模式,在骨架點搜索過程中,利用經驗步長值來動態地預測下一步搜索步長,快速確定骨架點的合理搜索區間;然后,采用折半查找方法判斷搜索區間內的骨架點,加快了搜索速度.結果表明,文中算法的化簡效果較好地保持了原始道路形態,更重要的是效率得到了大幅度的提高,符合大數據量化簡的需求.

1 材料與方法

1.1 實驗數據

實驗區位于某市,面積約13.7 km×9.8 km.這些GPS航跡線涵蓋了直線、彎曲、平面和多層立交各種交通結構,可以滿足驗證化簡算法的需求.GPS航跡數據來自于巡檢車輛上安裝的低成本GPS接收機,以1 s的頻率記錄坐標點,包括經度、緯度和時間.文中用于化簡的航跡約有10條,合計18 401個航跡點.

1.2 最優骨架點定義

骨架點定義采用了Sleeve-fitting算法[8]提出的概念.假設一段航跡線由一系列連續點構成(如圖1所示),圖中矩形平行于首末點連線(虛基線),限差是矩形寬度的一半.點是否在矩形內表示其到基線垂直距離和限差的關系.給定起始點(或前骨架點)P1和終點P3,構成一個判斷區間.連接P1與P3形成基線,計算位于P1與P3之間的點到基線的垂直距離,如果所有點的垂直距離都小于給定的限差值,則認為P1與P3形成的基線可以近似代表P1與P3之間的曲線段,此時P3為骨架點.

根據上述定義,骨架點不一定是最優骨架點.仍然以P1為起點,移動終點至P4,構成新的判斷區間,判斷P1與P4所連基線是否可以代替P1與P4之間的曲線段.如果可以近似代替,此時P4是骨架點,同時確認P3不是最優骨架點.依次類推,當P1與P5構成判斷區間時,如果基線不能夠近似代表曲線段,則P5為非骨架點,而P4則可確認為最優骨架點.這種最優骨架點的定義方式使得航跡線達到了最大程度化簡.

圖1 化簡過程示意圖

1.3 自適應折半查找化簡算法

1.3.1 最優骨架點的折半查找

航跡線的化簡過程就是最優骨架點的搜索過程.在化簡過程中,航跡線的首末兩個端點保留為骨架點.判斷首末兩端點之間是否含有骨架點的方法如下:連接兩個端點形成基線,如果兩個端點之間存在著某點到基線的垂直距離大于給定的限值,則認為存在骨架點;否則,兩端點連線就是化簡結果.

文中采用折半查找方法來實現骨架點的定位,即精選過程.給定一個搜索區間,位于前骨架點(首端點)的右側,假設其中含有骨架點.搜索區間的起點和前骨架點可以重合,也可以不重合.具體搜索過程如下:在搜索區間內,其中間點將搜索區間分為左右兩個子區間,連接前骨架點與搜索區間的中間點形成基線,如果前骨架點與中間點之間存在著骨架點,則將左子區間設為新搜索區間進行遞歸處理;否則,將右子區間設為新搜索區間進行遞歸處理.直到搜索區間不能劃分為止,最后一個搜索區間的左端點就是骨架點.值得注意的是,在處理過程中,基線的左端點一直是前骨架點保持不變,右端點根據折半查找方法在搜索區間內變動,直到確定骨架點為止.以搜索到的骨架點為起點,重復上述過程,查找新骨架點,直到完成整條航跡線的處理為止.

1.3.2 搜索區間的動態預測

為保證折半查找算法中的搜索區間含有骨架點,需要合理確定出搜索區間的長度,即粗篩過程.這里引入步長的概念,假定搜索區間的長度是步長的倍數,可表示為

其中,y為搜索區間長度,x為步長,k為整數,m為航跡線的總點數.給定步長x,搜索區間長度是隨著k值而變化的.k值的確定方法:將k值依次加一取值,對長度為kx的搜索區間進行判斷,直到其內部含有骨架點為止.

在確定搜索范圍的過程中,k值的窮舉法效率較低.如果指定的步長接近于被搜索的骨架點與前骨架點之間的長度,則窮舉次數將大大減小,化簡速度也將提高.下面給出了兩種步長賦值方法:平均值法和卡爾曼濾波預測法.平均值法是將前n個骨架點間長度的平均值賦為步長;卡爾曼濾波預測法是根據前兩個骨架點之間的長度,經過增益計算預測當前的步長值的,具體方法如下:

假設所有步長為離散控制過程的系統X(k),步長觀測量為Z(k),則觀測模型為

其中,X(k)即為第k個骨架點的步長,U(k)為當前狀態的控制量,A和B是系統參數,H是測量系統的參數; W(k)和V(k)分別表示過程和測量的噪聲.其協方差分別是Q和R.則有

其中,X(k|k-1)是預測結果;X(k-1|k-1)是前一個狀態的結果,即前兩個骨架點之間的長度; P(k|k-1)是X(k|k-1)對應的協方差;P(k-1|k-1)是X(k-1|k-1)對應的協方差;A′是A的轉置矩陣;Q是系統過程的協方差.

根據以上兩個式子得到當前步長的預測結果,結合測量值,計算得到步長最優化估算值為

其中,Kg(k)為卡爾曼增益;P(k|k)為k狀態下的協方差,用于下一個骨架點步長的預測.

1.4 評價方法

根據Mc Master提出的化簡算法的評估方法,這里選取了壓縮率、長度比、距離位移、面積位移和曲折度指標,從航跡線的壓縮程度和骨架線質量兩個方面對化簡算法進行了評價.

壓縮率高表明剔除的冗余點多,說明化簡效果好;長度比大表明壓縮后的骨架線越接近原始航跡線的長度,說明骨架線的保真度高;距離位移大表明骨架線偏移原始航跡線遠,說明骨架線的保真度低;面積位移大表明骨架線和原始航跡線之間的空隙大,說明骨架線的保真度低;曲折度高表明骨架線和原始航跡線相比變化幅度增大,說明保真度低.各參數的表達式如下:

壓縮率為

長度比為

距離位移為

面積位移為

曲折度為

其中,m和n分別為化簡后點數和原始點數;L′和L分別為化簡后曲線和原始曲線的長度;Pij是第i個原始點到第j條化簡弧段的垂直距離;Sj表示第j條化簡弧段與原始曲線圍成的面積;βij表示第i條原始弧段與第j條化簡弧段的夾角;αi表示原始曲線上第i條弧段與第i+1條弧段組成的夾角.

2 結果與討論

文中選擇了4種已有的經典局部算法Reumann-Witkam(RW)[9]、Sleeve-Fitting(SF)、Opheim (OP)[10]、Lang(LA)[11]和自適應折半查找(ABS)算法進行比較.對于ABS算法,根據1.3節提出的兩種步長賦值方法,分別得到了ABS_M(平均值)和ABS_K(卡爾曼濾波預測值)兩種化簡結果.

2.1 可視化對比分析

圖2顯示了壓縮率為93%時,折半查找方法化簡結果和原始航跡的疊加效果.圖2表明,GPS航跡線得到了大幅度化簡,尤其在道路平滑路段,其形狀與原始航跡保持高度一致.

為了驗證自適應折半查找算法的化簡效果,在限差值相同(如3.5 m)的情況下,利用以上5種算法對GPS航跡線分別進行了化簡.圖3顯示了各算法在轉彎、直線處的局部化簡結果,其在整個實驗數據中的位置在圖2中進行了標示.

由圖3可見,SF算法與ABS算法的化簡質量基本一致,二者均對航跡線進行了最大程度的化簡,獲得了較高的壓縮率,并且保留了曲率變化特征大的點以保持原始航跡線形態;LA算法在路口或轉彎處的化簡效果顯著,但在直線處受到

圖2 折半查找化簡結果

圖3 相同限差值下(3.5 m)各算法可視化化簡結果

所給化簡區間大小的限制產生了大量冗余點.由于其化簡區間的大小由人工根據經驗設定,使得化簡結果的質量具有很大的不確定性;RW算法保留了部分冗余點,沒有達到最大程度的化簡;OP算法在RW算法的基礎上,進一步保留了更多骨架點,雖然提高了與原始航跡線的形態符合程度,但是卻大大降低了壓縮率,尤其是在平直線段位置.

2.2 定量評價與分析

2.2.1 壓縮率比較

化簡過程中,給定相同的限差值(3.5 m),比較各算法化簡結果的壓縮率差異.

表1 相同限差值下各算法壓縮率

表1表明,在已有的4種算法中,SF算法具有最高的壓縮比率,超過93%的冗余點被剔除了,而其他3種算法結果接近,效果較差.LA算法的結果取決于初始步長值,不具有重復性;OP算法因增加兩個限制條件,保留了更多的原始點,壓縮率小于RW算法.文中提出的自適應折半查找化簡算法的壓縮率與SF算法的壓縮率接近,且略好,主要是因為SF算法和ABS算法的化簡思想類似,都為查找最優骨架點所致.

2.2.2 化簡效率與效果比較

化簡過程中,給定相同的壓縮率(85%),即保持骨架點數目相同,比較各種算法的化簡效率和效果,結果如表2所示.結果表明,在已有的4種算法中,SF算法的化簡結果具有最好的化簡質量,但是化簡效率很低; LA算法化簡質量次之;RW算法與OP算法化簡質量最差,不具可比性.其中,SF算法的結果具有重復性,但是LA算法的結果具有不確定性,主要取決于人工輸入的步長,步長越小,化簡所需時間越短,但化簡質量欠佳.OP算法在RW算法的基礎上增加了兩個限制條件,因此其運行時間較長.

表2 相同壓縮率下的各算法化簡結果評價指標

文中提出的自適應折半查找化簡算法的效果接近于SF算法,甚至更好些,但是化簡時間卻遠小于SF算法的.同SF算法一樣,ABS算法也是通過查詢最優骨架點來生成化簡曲線,因其采用了不同的骨架點搜索區間確定和骨架點查找方式,才大幅度地節省了化簡時間.ABS算法同樣具有可重復性,不需要人工干預.其中,基于卡爾曼濾波方法動態預測步長,使得化簡效率比平均值步長法的更高.

3 結束語

提出了一種高效的化簡算法用于降低GPS航跡線的數據冗余,同當前的幾種成熟的局部壓縮算法相比,該算法更適合于GPS航跡數據的化簡.相對于RW、OP和LA算法,該算法能提供自適應步長,應用靈活,適用于各種數據集;因僅有限差1個參數,其自動化程度更高.相對于SF算法,該算法利用折半查找的方法搜索骨架點,極大減少了骨架點的搜索時間,大幅度提高了化簡效率,但保持了很高的化簡質量.

通過與當前4種成熟化簡算法的定性和定量比較,結果表明,文中提出的算法在應用于GPS航跡線化簡時,克服了壓縮率和化簡效率低的缺點,同時保證了化簡效果.此外,該算法還可以做進一步的探索,比如考慮GPS數據本身誤差對化簡過程的影響,提供自適應限差值控制化簡的程度和質量等.

[1]Ivanov R.Real-time GPS Track Simplification Algorithm for Outdoor Navigation of Visually Impaired[J].Journal ofNetwork and Computer Applications,2012,35(5):1559-1567.

[2]Park W,Yu K.Hybrid Line Simplification for Cartographic Generalization[J].Pattern Recognition Letters,2011,32 (9):1267-1273.

[3]Mc Master R B.The Geometric Properties of Numerical Generalization[J].Geographical Analysis,1987,19(4):330-346.

[4]Douglas D,Peucker T.Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J].The Canadian Cartographer,1973,10(2):112-122.

[5]黃娟,程耀東.多分辨率小波分析在GIS線狀要素簡化中的應用[J].唐山學院學報,2010,23(7):13-16.

Huang Juan,Cheng Yaodong.Application of Multi-resolution Wavelet Analysis in GIS Linear Element Simplification [J].Journal of Tangshan College,2010,23(7):13-16.

[6]任海艷,陳飛翔.自適應遺傳算法的改進及在曲線化簡中的應用[J].計算機工程與應用,2012,48(11):152-155.

Ren Haiyan,Chen Feixiang.Improvement of Adaptive Genetic Algorithms and Application in Line Simplification[J]. Computer Engineering and Applications,2012,48(11):152-155.

[7]武芳,鄧紅艷.基于遺傳算法的線要素自動化簡模型[J].測繪學報,2003,32(4):349-355.

Wu Fang,Deng Hongyan.Using Genetic Algorithms for Solving Problems in Automated Line Simplification[J].Acta Geodaetica et Cartographica Sinica,2003,32(4):349-355.

[8]Zhao Z,Saalfeld A.Linear-time Sleeve-fitting Polyline Simplification Algorithms[DB/OL].[2012-12-30].http:// mapcontext.com/autocarto/proceedings/auto-carto-131pdf/linear-time-sleeve-fitting-pdyline-simplification-algorithm.pdf.

[9]Reumann K,Witkam A P M.Optimizing Curve Segmentation in Computer Graphics[C]//Proceedings of International Computing Symposium.Amsterdam:North-Holland,1974:467-472.

[10]Opheim H.Fast Data Reduction of a Digitized Curve[J].Geo-Processing,1982,2:33-40.

[11]Lang T.Rules for Robot Draughtsmen[J].Geographical Magazine,1969,42(1):50-51.

(編輯:齊淑娟)

Adaptive binary search polyline simplification algorithm for GPS trajectories

WANG Jing1,TAN Xiangshuang1,SONG Xianfeng1,2,WANG Chaoliang2
(1.College of Resources and Environment,Graduate University of Chinese Academy of Sciences,Beijing 100049,China;2.Academy of Opto-Electronics,Chinese Academy of Sciences,Beijing 100094,China)

This paper proposes an adaptive binary search polyline simplification algorithm for simplifying GPS trajectories,which adopts the optimal skeleton point conceptual model of the Sleeve-fitting algorithm to retain a maximum point reduction.Meanwhile,the innovating modifications of screening roughly and handpickedly are suggested to improve the efficiency of simplification process significantly:Dynamically predicting the search step to determine quickly a search interval within which at least one skeleton point falls;Applying a binary search in the search interval of the GPS trajectory to locate the optimal skeleton point.The GPS trajectories acquired in Huaibei City,China are used for testing polyline simplification.As a result,our proposed algorithm preserves the best shape characteristics with a shortest running time.

GPS trajectories;binary search;polyline simplification;the optimal skeleton point

P208

A

1001-2400(2014)05-0155-06

2013-07-09< class="emphasis_bold">網絡出版時間:

時間:2014-01-12

中國科學院知識創新工程重要方向性資助項目(KZCX2-EW-QN605);國家科技重大專項“大型油氣田及煤層氣開發”資助項目(2011ZX05039-004)

王 靜(1986-),女,中國科學院大學博士研究生,E-mail:qiufengwj@163.com,xfsong@ucas.ac.cn.

http://www.cnki.net/kcms/doi/10.3969/j.issn.1001-2400.2014.05.026.html

10.3969/j.issn.1001-2400.2014.05.026