实时异常轨迹检测方法及其应用

夏 英，刘申艺

(1.西南交通大学信息科学与技术学院，四川成都 610031;2.重庆邮电大学计算机学院，重庆 400065)

0 引言

随着移动通信、空间定位、位置服务等技术的不断发展，手机、PDA(personal digital assistant)等集成定位功能且具有通信和计算能力的智能终端得到广泛应用，大量移动对象的轨迹数据随之产生并隐藏着丰富的知识。在公共交通、医疗监护、物流运输等应用领域，移动对象的运动轨迹是预先设定的，偏离预定的轨迹可能预示着某种异常，实时地进行异常轨迹检测有利于及时发现隐患并辅助决策。

异常轨迹检测的一种常用方法是通过地图匹配技术［1］修正实时获取的位置数据并投影到某条道路上，如果修正后的位置与预先定义的道路不匹配，则表示轨迹异常。地图匹配的常用方法有直接投影法［2］、概率统计法［3］、模糊逻辑法［4］等。直接投影法简单易行，但是当存在多条候选路段时存在一定误差。概率统计法需要以概率统计的方法确定定位误差区域，无法避免在推算过程中的误差积累。模糊逻辑法适于解决地图匹配过程中涉及的模糊度定性决策问题，但计算复杂。总的来说，现有的地图匹配方法在道路稀疏区域能够取得准确的匹配结果，但在道路密集、道路形状和交叉口复杂的路段大多数地图匹配方法的准确率还有待提高。另外，由于地图匹配需要对路网进行实时搜索，计算和通信资源消耗较大。

本文面向具有路网约束并要求预先设定正常轨迹的应用领域，将手机、PDA等手持终端用户作为移动对象，考虑到预先定义的路线和用户实际行进路线均为包含位置信息的时间序列，尝试利用两个时间序列的距离度量来发现异常，以提高异常检测的准确性和实时性。

1 相关基础

一般地，从GPS(global positioning system)等定位设备采集的移动对象的位置数据可以用P(x，y，v，t)表示，其中，x和y表示经度和纬度坐标，v表示速度，t表示时刻。轨迹T是一个反映移动对象位置信息的时间序列，即 T={P1，P2，…}。

预定义轨迹为一条预先设定的正常轨迹，通常是由基于矢量地图中的道路特征点组成的时间序列。道路特征点可以直观地理解为路口或一条非直线道路上的拐点。实际轨迹由实时采集的位置序列构成。如图1所示，Tn表示预定义轨迹，Tr表示实际轨迹。

图1 预定义轨迹和实际轨迹Fig.1 Predefined trajectory and actual trajectory

移动对象的实际轨迹与预定义轨迹都表现为时间序列，而时间序列的相似性测度一般采用欧式距离、动态时间弯曲［5］等方法。欧氏距离是使用最早也是最广的一种相似性度量，其计算简单、容易理解，但不支持时间序列的时间轴伸缩，且要求两个时间序列长度相等。动态时间弯曲方法支持时间轴伸缩，但是计算复杂。

Dubuisson 和 Jain［6］在 Hausdorff距离的基础上提出了距离公式 MHD(modified hausdorff distance)，用于计算点集合之间的匹配程度。给定两个点集，A={a1，…，ap}，B={b1，…，bq}，则点集合A到点集B的有向MHD为

(1)式中:h(a，B)表示点a到点集合B的最短距离，Na为集合A中点的个数。如图2所示，h(a，B)为点a与点b之间的距离d。

图2 点a到点集合B的最短距离Fig.2 Shortest distance between point a and point set B

2 改进的有向MHD

考虑到预定义轨迹中的道路特征点集合具有明显的线段特征，而用户实际轨迹表现为点集合，简单的用有向MHD求解点集合间的距离是不合适的。假设实际轨迹中某一时刻的位置为Pri，而对应的预定义轨迹为线段(Pn1，Pn2)，点 Pri到线段(Pn1，Pn2)的最短距离更能够反映位置的匹配程度。

假设a为一个点，BC为一条线段，在计算a到BC的最短距离时，需要首先判断它们之间的位置关系。当∠aBC(线段aB，BC的夹角)和∠aCB(线段aC，CB的夹角)均小于或等于正(负)90度时，说明a到BC的垂线与BC相交，则a到BC的最短距离为点a到线段BC的垂直距离;否则，点a到线段BC的最短距离为a到线段的两个端点B，C距离值中的最小值。

由此，对有向MHD进行改进，定义h(a，Tn)为点a到线段集Tn中各线段的最短距离。给定点集合Tr和线段集合Tn，改进有向MHD(improved mdified husdorff distance，)为

(2)式中:Na为Tr中点的个数，h(a，Tn)定义为点a到Tn中各线段的最短距离。

3 基于改进有向MHD的异常轨迹检测算法

给定预定义轨迹Tn，一段时间内的实际轨迹Tr，根据改进有向MHD计算Tn和Tr之间的匹配程度。根据领域经验设定一个阈值 DIS，如果hIMHD(Tr，Tn)＞DIS，说明实际轨迹Tr和预定义轨迹Tn不匹配，则可以判断出现了异常。

实时异常轨迹检测的过程中，用户的位置数据是不断更新的，而且通常只针对当前时间段的一个局部位置序列。定义一个数据流DS为一个有限的位置序列{…，Pt－1，Pt，…}，Pt代表用户在 t时刻的位置。给定两个时间戳 tm，tn，DS［tm，tn］代表位置序列{Pm，Pm+1，…，Pn}，DS的大小为 n－m+1。给定DS的大小W，当前数据流为DS［t－W+1，t］，t为当前时间。DS中的数据为当前时间段内的实际轨迹。

异常轨迹检测按照一定的时间间隔进行。每个时间间隔范围内从数据流DS中取出局部数据，假设在时间间隔［ts，te］内获得的实际轨迹为Tr，且Tr={Ps，…，Pe}。

为了检测该时间间隔内的轨迹是否异常，需要确定对应的正常轨迹段。算法通过欧式距离从正常轨迹中分别选取距离Ps和Pe最近的两个点，这两点间的位置点集合构成参与计算的正常轨迹段SubTn。

基于改进有向MHD的异常检测算法流程如图3所示。算法分为2部分:第1部分代表用户位置数据的实时采集，通过队列queue的出队列和入队列操作形成数据流DS;第2部分每间隔一定的时间，将数据流中的数据复制到Tr中，并通过改进有向MHD判断轨迹Tr与对应的SubTn是否发生了偏离。

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

4 应用实例及性能测试

利用基于改进有向MHD的异常检测算法，设计一个安全路线检测系统SafeRoute，并应用于具备GPS定位功能的智能手机。手机用户出行前首先设定正常轨迹和异常警报接收者等信息。一旦用户在行进过程中偏离正常轨迹，系统将通过短信给接收者发送警报。系统体系结构如图4所示。

图4 SafeRoute体系结构Fig.4 System architecture of SafeRoute

图4中，Map Service提供地图查询和表现功能;Service Manager用来管理系统的各种服务;GPS Manager实时获得用户位置坐标点;GPS Buffer Manager用于缓冲获得的位置坐标点，并对坐标点进行有效性判断和修正;Safe Route Manager提供正常轨迹设定和存储功能;Log Manager记录系统日志;Detection Engine负责异常轨迹检测;Anomaly Notification用于发送警报信息。

系统开发环境为 Eclipse，Android 1.6，使用嵌入式数据库SQLite，采用Google地图，位置数据由Android手机采集。

图5显示了系统的2个主要界面。图5a中用户激活安全路线并对有效时间进行设置。图5b中线条显示了用户设置的一条安全路线。

图5 安全路线检测系统主界面Fig.5 Main interface of SafeRoute system

实验利用Android手机采集的位置数据进行实验，首先分析异常轨迹检测的准确率。从图6中可以看出，本文提出的异常检测算法除第5次检测的准确率为0.54以外，其余几次的检测都可以达到1。实际情况中，第5次检测时用户正在慢慢偏离安全路线。本次实验总共进行13次检测，在第1，7，8，9次检测时，用户经过交叉口路段，而此时准确率依然保持为1，可见本文所提算法能够避免复杂路段对准确性的影响。

分析每次异常轨迹所需耗费的时间，实验结果如图7所示，连续进行7次异常检测，每次检测实际轨迹Tr中点的个数不超过30个，检测所需的时间基本稳定在100～150 ms之间。而现在大多数地图匹配算法的单点匹配时间一般为50 ms左右，30个点匹配所需消耗的时间大约为1 500 ms。由于算法通过改进有向MHD计算实际轨迹与预定轨迹间的距离，避免了对路网的实时搜索，从而提高了异常轨迹的检测效率。

5 总结

在公共交通、医疗监护、物流运输等应用领域中，实时检测车辆、行人等移动对象的运动轨迹，能够及时发现轨迹偏离等异常现象，本文提出了一种实时异常轨迹检测方法，在一定的时间间隔范围内，参照实际轨迹动态调整参与计算的正常轨迹范围，从而提高算法的效率。同时，考虑到预定义轨迹的线段特征，通过点集、线段集合之间的相似性，改进有向MHD度量，更加有效地度量轨迹偏离程度。由于不需要采用传统的地图匹配技术对用户位置进行修正，从而避免了道路复杂性对检测准确性的影响，减轻了计算和网络资源的负担。实验分析和案例应用表明算法具有较高的准确性和实时性。

［1］陈嘉，胡继华，张飞舟.面向车辆监控导航的地图匹配算法研究［J］.北京大学学报，2009，49(2):299－305.

CHEN Jia，HU Ji－hua，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］彭飞，柳重堪，张其善.基于代价函数的组合导航系统地图匹配算法［J］.北京航空航天大学学报，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］. 四川大学学报，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］董文明，吴乐华，姜德雷.基于背景重构的运动目标检测算法［J］.重庆邮电大学学报:自然科学版，2008，20(6):754－757.

DONGWen－ming，WU Le－hua，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］蒋新土，吕岳.基于改进的加权Hausdorff距离的图像

匹配［J］. 计算机应用研究，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.

(编辑:田海江)