GPS航跡線的自適應(yīng)折半查找化簡算法

王 靜,譚祥爽,宋現(xiàn)鋒,,汪超亮

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

GPS航跡線的自適應(yīng)折半查找化簡算法

王 靜1,譚祥爽1,宋現(xiàn)鋒1,2,汪超亮2

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

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

GPS航跡;線化簡;折半查找;最優(yōu)骨架點(diǎn)

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

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

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

1 材料與方法

1.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)區(qū)位于某市,面積約13.7 km×9.8 km.這些GPS航跡線涵蓋了直線、彎曲、平面和多層立交各種交通結(jié)構(gòu),可以滿足驗(yàn)證化簡算法的需求.GPS航跡數(shù)據(jù)來自于巡檢車輛上安裝的低成本GPS接收機(jī),以1 s的頻率記錄坐標(biāo)點(diǎn),包括經(jīng)度、緯度和時(shí)間.文中用于化簡的航跡約有10條,合計(jì)18 401個(gè)航跡點(diǎn).

1.2 最優(yōu)骨架點(diǎn)定義

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

根據(jù)上述定義,骨架點(diǎn)不一定是最優(yōu)骨架點(diǎn).仍然以P1為起點(diǎn),移動終點(diǎn)至P4,構(gòu)成新的判斷區(qū)間,判斷P1與P4所連基線是否可以代替P1與P4之間的曲線段.如果可以近似代替,此時(shí)P4是骨架點(diǎn),同時(shí)確認(rèn)P3不是最優(yōu)骨架點(diǎn).依次類推,當(dāng)P1與P5構(gòu)成判斷區(qū)間時(shí),如果基線不能夠近似代表曲線段,則P5為非骨架點(diǎn),而P4則可確認(rèn)為最優(yōu)骨架點(diǎn).這種最優(yōu)骨架點(diǎn)的定義方式使得航跡線達(dá)到了最大程度化簡.

圖1 化簡過程示意圖

1.3 自適應(yīng)折半查找化簡算法

1.3.1 最優(yōu)骨架點(diǎn)的折半查找

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

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

1.3.2 搜索區(qū)間的動態(tài)預(yù)測

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

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

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

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

其中,X(k)即為第k個(gè)骨架點(diǎn)的步長,U(k)為當(dāng)前狀態(tài)的控制量,A和B是系統(tǒng)參數(shù),H是測量系統(tǒng)的參數(shù); W(k)和V(k)分別表示過程和測量的噪聲.其協(xié)方差分別是Q和R.則有

其中,X(k|k-1)是預(yù)測結(jié)果;X(k-1|k-1)是前一個(gè)狀態(tài)的結(jié)果,即前兩個(gè)骨架點(diǎn)之間的長度; P(k|k-1)是X(k|k-1)對應(yīng)的協(xié)方差;P(k-1|k-1)是X(k-1|k-1)對應(yīng)的協(xié)方差;A′是A的轉(zhuǎn)置矩陣;Q是系統(tǒng)過程的協(xié)方差.

根據(jù)以上兩個(gè)式子得到當(dāng)前步長的預(yù)測結(jié)果,結(jié)合測量值,計(jì)算得到步長最優(yōu)化估算值為

其中,Kg(k)為卡爾曼增益;P(k|k)為k狀態(tài)下的協(xié)方差,用于下一個(gè)骨架點(diǎn)步長的預(yù)測.

1.4 評價(jià)方法

根據(jù)Mc Master提出的化簡算法的評估方法,這里選取了壓縮率、長度比、距離位移、面積位移和曲折度指標(biāo),從航跡線的壓縮程度和骨架線質(zhì)量兩個(gè)方面對化簡算法進(jìn)行了評價(jià).

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

壓縮率為

長度比為

距離位移為

面積位移為

曲折度為

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

2 結(jié)果與討論

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

2.1 可視化對比分析

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

為了驗(yàn)證自適應(yīng)折半查找算法的化簡效果,在限差值相同(如3.5 m)的情況下,利用以上5種算法對GPS航跡線分別進(jìn)行了化簡.圖3顯示了各算法在轉(zhuǎn)彎、直線處的局部化簡結(jié)果,其在整個(gè)實(shí)驗(yàn)數(shù)據(jù)中的位置在圖2中進(jìn)行了標(biāo)示.

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

圖2 折半查找化簡結(jié)果

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

所給化簡區(qū)間大小的限制產(chǎn)生了大量冗余點(diǎn).由于其化簡區(qū)間的大小由人工根據(jù)經(jīng)驗(yàn)設(shè)定,使得化簡結(jié)果的質(zhì)量具有很大的不確定性;RW算法保留了部分冗余點(diǎn),沒有達(dá)到最大程度的化簡;OP算法在RW算法的基礎(chǔ)上,進(jìn)一步保留了更多骨架點(diǎn),雖然提高了與原始航跡線的形態(tài)符合程度,但是卻大大降低了壓縮率,尤其是在平直線段位置.

2.2 定量評價(jià)與分析

2.2.1 壓縮率比較

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

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

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

2.2.2 化簡效率與效果比較

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

表2 相同壓縮率下的各算法化簡結(jié)果評價(jià)指標(biāo)

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

3 結(jié)束語

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

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

[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線狀要素簡化中的應(yīng)用[J].唐山學(xué)院學(xué)報(bào),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]任海艷,陳飛翔.自適應(yīng)遺傳算法的改進(jìn)及在曲線化簡中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,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].測繪學(xué)報(bào),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">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2014-01-12

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

王 靜(1986-),女,中國科學(xué)院大學(xué)博士研究生,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