夏 英，劉申藝

(1.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，四川成都 610031;2.重慶郵電大學(xué)計(jì)算機(jī)學(xué)院，重慶 400065)

0 引言

隨著移動(dòng)通信、空間定位、位置服務(wù)等技術(shù)的不斷發(fā)展，手機(jī)、PDA(personal digital assistant)等集成定位功能且具有通信和計(jì)算能力的智能終端得到廣泛應(yīng)用，大量移動(dòng)對(duì)象的軌跡數(shù)據(jù)隨之產(chǎn)生并隱藏著豐富的知識(shí)。在公共交通、醫(yī)療監(jiān)護(hù)、物流運(yùn)輸?shù)葢?yīng)用領(lǐng)域，移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡是預(yù)先設(shè)定的，偏離預(yù)定的軌跡可能預(yù)示著某種異常，實(shí)時(shí)地進(jìn)行異常軌跡檢測(cè)有利于及時(shí)發(fā)現(xiàn)隱患并輔助決策。

異常軌跡檢測(cè)的一種常用方法是通過(guò)地圖匹配技術(shù)［1］修正實(shí)時(shí)獲取的位置數(shù)據(jù)并投影到某條道路上，如果修正后的位置與預(yù)先定義的道路不匹配，則表示軌跡異常。地圖匹配的常用方法有直接投影法［2］、概率統(tǒng)計(jì)法［3］、模糊邏輯法［4］等。直接投影法簡(jiǎn)單易行，但是當(dāng)存在多條候選路段時(shí)存在一定誤差。概率統(tǒng)計(jì)法需要以概率統(tǒng)計(jì)的方法確定定位誤差區(qū)域，無(wú)法避免在推算過(guò)程中的誤差積累。模糊邏輯法適于解決地圖匹配過(guò)程中涉及的模糊度定性決策問(wèn)題，但計(jì)算復(fù)雜?？偟膩?lái)說(shuō)，現(xiàn)有的地圖匹配方法在道路稀疏區(qū)域能夠取得準(zhǔn)確的匹配結(jié)果，但在道路密集、道路形狀和交叉口復(fù)雜的路段大多數(shù)地圖匹配方法的準(zhǔn)確率還有待提高。另外，由于地圖匹配需要對(duì)路網(wǎng)進(jìn)行實(shí)時(shí)搜索，計(jì)算和通信資源消耗較大。

本文面向具有路網(wǎng)約束并要求預(yù)先設(shè)定正常軌跡的應(yīng)用領(lǐng)域，將手機(jī)、PDA等手持終端用戶(hù)作為移動(dòng)對(duì)象，考慮到預(yù)先定義的路線和用戶(hù)實(shí)際行進(jìn)路線均為包含位置信息的時(shí)間序列，嘗試?yán)脙蓚€(gè)時(shí)間序列的距離度量來(lái)發(fā)現(xiàn)異常，以提高異常檢測(cè)的準(zhǔn)確性和實(shí)時(shí)性。

1 相關(guān)基礎(chǔ)

一般地，從GPS(global positioning system)等定位設(shè)備采集的移動(dòng)對(duì)象的位置數(shù)據(jù)可以用P(x，y，v，t)表示，其中，x和y表示經(jīng)度和緯度坐標(biāo)，v表示速度，t表示時(shí)刻。軌跡T是一個(gè)反映移動(dòng)對(duì)象位置信息的時(shí)間序列，即 T={P1，P2，…}。

預(yù)定義軌跡為一條預(yù)先設(shè)定的正常軌跡，通常是由基于矢量地圖中的道路特征點(diǎn)組成的時(shí)間序列。道路特征點(diǎn)可以直觀地理解為路口或一條非直線道路上的拐點(diǎn)。實(shí)際軌跡由實(shí)時(shí)采集的位置序列構(gòu)成。如圖1所示，Tn表示預(yù)定義軌跡，Tr表示實(shí)際軌跡。

圖1 預(yù)定義軌跡和實(shí)際軌跡Fig.1 Predefined trajectory and actual trajectory

移動(dòng)對(duì)象的實(shí)際軌跡與預(yù)定義軌跡都表現(xiàn)為時(shí)間序列，而時(shí)間序列的相似性測(cè)度一般采用歐式距離、動(dòng)態(tài)時(shí)間彎曲［5］等方法。歐氏距離是使用最早也是最廣的一種相似性度量，其計(jì)算簡(jiǎn)單、容易理解，但不支持時(shí)間序列的時(shí)間軸伸縮，且要求兩個(gè)時(shí)間序列長(zhǎng)度相等。動(dòng)態(tài)時(shí)間彎曲方法支持時(shí)間軸伸縮，但是計(jì)算復(fù)雜。

Dubuisson 和 Jain［6］在 Hausdorff距離的基礎(chǔ)上提出了距離公式 MHD(modified hausdorff distance)，用于計(jì)算點(diǎn)集合之間的匹配程度。給定兩個(gè)點(diǎn)集，A={a1，…，ap}，B={b1，…，bq}，則點(diǎn)集合A到點(diǎn)集B的有向MHD為

(1)式中:h(a，B)表示點(diǎn)a到點(diǎn)集合B的最短距離，Na為集合A中點(diǎn)的個(gè)數(shù)。如圖2所示，h(a，B)為點(diǎn)a與點(diǎn)b之間的距離d。

圖2 點(diǎn)a到點(diǎn)集合B的最短距離Fig.2 Shortest distance between point a and point set B

2 改進(jìn)的有向MHD

考慮到預(yù)定義軌跡中的道路特征點(diǎn)集合具有明顯的線段特征，而用戶(hù)實(shí)際軌跡表現(xiàn)為點(diǎn)集合，簡(jiǎn)單的用有向MHD求解點(diǎn)集合間的距離是不合適的。假設(shè)實(shí)際軌跡中某一時(shí)刻的位置為Pri，而對(duì)應(yīng)的預(yù)定義軌跡為線段(Pn1，Pn2)，點(diǎn) Pri到線段(Pn1，Pn2)的最短距離更能夠反映位置的匹配程度。

假設(shè)a為一個(gè)點(diǎn)，BC為一條線段，在計(jì)算a到BC的最短距離時(shí)，需要首先判斷它們之間的位置關(guān)系。當(dāng)∠aBC(線段aB，BC的夾角)和∠aCB(線段aC，CB的夾角)均小于或等于正(負(fù))90度時(shí)，說(shuō)明a到BC的垂線與BC相交，則a到BC的最短距離為點(diǎn)a到線段BC的垂直距離;否則，點(diǎn)a到線段BC的最短距離為a到線段的兩個(gè)端點(diǎn)B，C距離值中的最小值。

由此，對(duì)有向MHD進(jìn)行改進(jìn)，定義h(a，Tn)為點(diǎn)a到線段集Tn中各線段的最短距離。給定點(diǎn)集合Tr和線段集合Tn，改進(jìn)有向MHD(improved mdified husdorff distance，)為

(2)式中:Na為T(mén)r中點(diǎn)的個(gè)數(shù)，h(a，Tn)定義為點(diǎn)a到Tn中各線段的最短距離。

3 基于改進(jìn)有向MHD的異常軌跡檢測(cè)算法

給定預(yù)定義軌跡Tn，一段時(shí)間內(nèi)的實(shí)際軌跡Tr，根據(jù)改進(jìn)有向MHD計(jì)算Tn和Tr之間的匹配程度。根據(jù)領(lǐng)域經(jīng)驗(yàn)設(shè)定一個(gè)閾值 DIS，如果hIMHD(Tr，Tn)＞DIS，說(shuō)明實(shí)際軌跡Tr和預(yù)定義軌跡Tn不匹配，則可以判斷出現(xiàn)了異常。

實(shí)時(shí)異常軌跡檢測(cè)的過(guò)程中，用戶(hù)的位置數(shù)據(jù)是不斷更新的，而且通常只針對(duì)當(dāng)前時(shí)間段的一個(gè)局部位置序列。定義一個(gè)數(shù)據(jù)流DS為一個(gè)有限的位置序列{…，Pt－1，Pt，…}，Pt代表用戶(hù)在 t時(shí)刻的位置。給定兩個(gè)時(shí)間戳 tm，tn，DS［tm，tn］代表位置序列{Pm，Pm+1，…，Pn}，DS的大小為 n－m+1。給定DS的大小W，當(dāng)前數(shù)據(jù)流為DS［t－W+1，t］，t為當(dāng)前時(shí)間。DS中的數(shù)據(jù)為當(dāng)前時(shí)間段內(nèi)的實(shí)際軌跡。

異常軌跡檢測(cè)按照一定的時(shí)間間隔進(jìn)行。每個(gè)時(shí)間間隔范圍內(nèi)從數(shù)據(jù)流DS中取出局部數(shù)據(jù)，假設(shè)在時(shí)間間隔［ts，te］內(nèi)獲得的實(shí)際軌跡為T(mén)r，且Tr={Ps，…，Pe}。

為了檢測(cè)該時(shí)間間隔內(nèi)的軌跡是否異常，需要確定對(duì)應(yīng)的正常軌跡段。算法通過(guò)歐式距離從正常軌跡中分別選取距離Ps和Pe最近的兩個(gè)點(diǎn)，這兩點(diǎn)間的位置點(diǎn)集合構(gòu)成參與計(jì)算的正常軌跡段SubTn。

基于改進(jìn)有向MHD的異常檢測(cè)算法流程如圖3所示。算法分為2部分:第1部分代表用戶(hù)位置數(shù)據(jù)的實(shí)時(shí)采集，通過(guò)隊(duì)列queue的出隊(duì)列和入隊(duì)列操作形成數(shù)據(jù)流DS;第2部分每間隔一定的時(shí)間，將數(shù)據(jù)流中的數(shù)據(jù)復(fù)制到Tr中，并通過(guò)改進(jìn)有向MHD判斷軌跡Tr與對(duì)應(yīng)的SubTn是否發(fā)生了偏離。

圖3 算法流程圖Fig.3 Flow chart of algorithm

4 應(yīng)用實(shí)例及性能測(cè)試

利用基于改進(jìn)有向MHD的異常檢測(cè)算法，設(shè)計(jì)一個(gè)安全路線檢測(cè)系統(tǒng)SafeRoute，并應(yīng)用于具備GPS定位功能的智能手機(jī)。手機(jī)用戶(hù)出行前首先設(shè)定正常軌跡和異常警報(bào)接收者等信息。一旦用戶(hù)在行進(jìn)過(guò)程中偏離正常軌跡，系統(tǒng)將通過(guò)短信給接收者發(fā)送警報(bào)。系統(tǒng)體系結(jié)構(gòu)如圖4所示。

圖4 SafeRoute體系結(jié)構(gòu)Fig.4 System architecture of SafeRoute

圖4中，Map Service提供地圖查詢(xún)和表現(xiàn)功能;Service Manager用來(lái)管理系統(tǒng)的各種服務(wù);GPS Manager實(shí)時(shí)獲得用戶(hù)位置坐標(biāo)點(diǎn);GPS Buffer Manager用于緩沖獲得的位置坐標(biāo)點(diǎn)，并對(duì)坐標(biāo)點(diǎn)進(jìn)行有效性判斷和修正;Safe Route Manager提供正常軌跡設(shè)定和存儲(chǔ)功能;Log Manager記錄系統(tǒng)日志;Detection Engine負(fù)責(zé)異常軌跡檢測(cè);Anomaly Notification用于發(fā)送警報(bào)信息。

系統(tǒng)開(kāi)發(fā)環(huán)境為 Eclipse，Android 1.6，使用嵌入式數(shù)據(jù)庫(kù)SQLite，采用Google地圖，位置數(shù)據(jù)由Android手機(jī)采集。

圖5顯示了系統(tǒng)的2個(gè)主要界面。圖5a中用戶(hù)激活安全路線并對(duì)有效時(shí)間進(jìn)行設(shè)置。圖5b中線條顯示了用戶(hù)設(shè)置的一條安全路線。

圖5 安全路線檢測(cè)系統(tǒng)主界面Fig.5 Main interface of SafeRoute system

實(shí)驗(yàn)利用Android手機(jī)采集的位置數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，首先分析異常軌跡檢測(cè)的準(zhǔn)確率。從圖6中可以看出，本文提出的異常檢測(cè)算法除第5次檢測(cè)的準(zhǔn)確率為0.54以外，其余幾次的檢測(cè)都可以達(dá)到1。實(shí)際情況中，第5次檢測(cè)時(shí)用戶(hù)正在慢慢偏離安全路線。本次實(shí)驗(yàn)總共進(jìn)行13次檢測(cè)，在第1，7，8，9次檢測(cè)時(shí)，用戶(hù)經(jīng)過(guò)交叉口路段，而此時(shí)準(zhǔn)確率依然保持為1，可見(jiàn)本文所提算法能夠避免復(fù)雜路段對(duì)準(zhǔn)確性的影響。

分析每次異常軌跡所需耗費(fèi)的時(shí)間，實(shí)驗(yàn)結(jié)果如圖7所示，連續(xù)進(jìn)行7次異常檢測(cè)，每次檢測(cè)實(shí)際軌跡Tr中點(diǎn)的個(gè)數(shù)不超過(guò)30個(gè)，檢測(cè)所需的時(shí)間基本穩(wěn)定在100～150 ms之間。而現(xiàn)在大多數(shù)地圖匹配算法的單點(diǎn)匹配時(shí)間一般為50 ms左右，30個(gè)點(diǎn)匹配所需消耗的時(shí)間大約為1 500 ms。由于算法通過(guò)改進(jìn)有向MHD計(jì)算實(shí)際軌跡與預(yù)定軌跡間的距離，避免了對(duì)路網(wǎng)的實(shí)時(shí)搜索，從而提高了異常軌跡的檢測(cè)效率。

5 總結(jié)

在公共交通、醫(yī)療監(jiān)護(hù)、物流運(yùn)輸?shù)葢?yīng)用領(lǐng)域中，實(shí)時(shí)檢測(cè)車(chē)輛、行人等移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡，能夠及時(shí)發(fā)現(xiàn)軌跡偏離等異?，F(xiàn)象，本文提出了一種實(shí)時(shí)異常軌跡檢測(cè)方法，在一定的時(shí)間間隔范圍內(nèi)，參照實(shí)際軌跡動(dòng)態(tài)調(diào)整參與計(jì)算的正常軌跡范圍，從而提高算法的效率。同時(shí)，考慮到預(yù)定義軌跡的線段特征，通過(guò)點(diǎn)集、線段集合之間的相似性，改進(jìn)有向MHD度量，更加有效地度量軌跡偏離程度。由于不需要采用傳統(tǒng)的地圖匹配技術(shù)對(duì)用戶(hù)位置進(jìn)行修正，從而避免了道路復(fù)雜性對(duì)檢測(cè)準(zhǔn)確性的影響，減輕了計(jì)算和網(wǎng)絡(luò)資源的負(fù)擔(dān)。實(shí)驗(yàn)分析和案例應(yīng)用表明算法具有較高的準(zhǔn)確性和實(shí)時(shí)性。

［1］陳嘉，胡繼華，張飛舟.面向車(chē)輛監(jiān)控導(dǎo)航的地圖匹配算法研究［J］.北京大學(xué)學(xué)報(bào)，2009，49(2):299－305.

CHEN Jia，HU Ji－h(huán)ua，ZHANG Fei－zhou.Research on Map－Matching Algorithm Oriented Navigation and Monitor［J］.Acta Scientiarum Naturalium Universitatis Pekinensis，2009，49(2):299－305.

［2］秦文斌，王培東.基于投影的GPS地圖匹配算法研究［J］. 硅谷，2008，24(5):23－24.

QINWen－bin，WANG Pei－dong.Research ofmap matching algorithm of GPS bases on projection［J］.Silicon Valley，2008，24(5):23－24.

［3］彭飛，柳重堪，張其善.基于代價(jià)函數(shù)的組合導(dǎo)航系統(tǒng)地圖匹配算法［J］.北京航空航天大學(xué)學(xué)報(bào)，2002，28(3):261－264.

PENG Fei， LIU Chong－kan， ZHANG Qi－shan.Cost Function Based Map Matching Algorithm for GPS/DR Integrated Navigation Systems［J］.Journal of Beijing University of Aeronautics and Astronautics，2002，28(3):261－264.

［4］張維，王忠，薛曉娜.確定性值地圖匹配算法的改進(jìn)［J］. 四川大學(xué)學(xué)報(bào)，2009，46(1):52－56.

ZHANG Wei，WANG Zhong，XUE Xiao－na.Improvementofmapmatching algorithm based on C－measure［J］.Journal of Sichuan University，2009，46(1):52－56.

［5］董文明，吳樂(lè)華，姜德雷.基于背景重構(gòu)的運(yùn)動(dòng)目標(biāo)檢測(cè)算法［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2008，20(6):754－757.

DONGWen－ming，WU Le－h(huán)ua，JIANG de－lei.Moving object detection algorithm based on background reconstruction［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2008，20(6):754－757.

［6］蔣新土，呂岳.基于改進(jìn)的加權(quán)Hausdorff距離的圖像

匹配［J］. 計(jì)算機(jī)應(yīng)用研究，2007，24(4):182－185.JIANG Xin－tu，LV Yue.Improved Approach to Image Matching Based on Weighted Hausdorff Distance［J］.Application Research of Computers，2007，24(4):182－185.

(編輯:田海江)