关于运动对象轨迹的分割与聚类算法研究

摘要

随着卫星定位技术、跟踪监测设备、无线通信及电子技术的快速发展，人们对持续移动物体所处的空间位置的跟踪能力不断加强，使得收集大量运动对象轨迹数据成为可能。运动对象轨迹包含着丰富的信息，分析这些轨迹对于许多应用领域来说是一个有趣的工作。这些应用涉及交通控制、气象监测、智能导航、生物医药、商业决策、军事分析和反恐监测等多个方面。其中典型的数据分析目标之一是聚类相似的运动轨迹并提取出运动特征模式，用来分析和预测对象运动行为。 一条运动对象轨迹经过的路径很长很复杂，许多轨迹可能会有一小段相似而在整体上是不相似的，如在交通监测中发现许多入都会经过一条主要路段而最终目的地是各不相同的；并且各条运动轨迹的长度差别很大，短轨迹可能和长轨迹的其中一段相似。距离度量方法是影响聚类结果的一个主要因素，传统的轨迹聚类方法是将这条轨迹看作是一个整体，轨迹之间的距离要考虑它所包含的全部轨迹点信息。部分段相似的轨迹之间的距离可能差距很大，不能聚到一个簇中，这样就将这一相似段的信息丢失了。本文研究目的是将这些称为子轨迹段的相似段找出来，采用的框架是将一条长轨迹曲线先分割成一组直线段，然后聚类相似直线段，最后从直线段簇中提取公共子轨迹段。具体有以下几个方面的主要工作： 1.为处理不同时间以不同速度运动的对象轨迹，采用折线段表示轨迹数据模型。即轨迹沿直线均速运动，直到改变了方向和/或速度，并在空间维中加入了时间维和速度维。 2.为达到准确聚类轨迹分割线段的目的，采用多层距离处理方法。先用空间距离过滤相似线段，再用时间距离和速度距离提纯线段簇。 3.提出一种将长轨迹分割成一组直线段的算法。既考虑方向的变化也考虑速度的变化，在轨迹方向和速度变化超过给定阈值的地方将其分割开。 4.采用基于密度的聚类方法OPTICS对轨迹分割线段进行聚类，根据可达图找出相似的线段簇。 5.本文对涉及到的具体问题给出了理论分析和相关算法，并在时空数据集上进行实验分析和验证。结果表明，本算法能很好的从轨迹数据集中发现公共子轨迹段，并具有较高的执行效率和可伸缩性。

目录

文摘

英文文摘

声明

第1章绪论

1.1研究背景

1.2研究意义

1.3运动对象轨迹聚类研究的核心问题与研究现状

1.3.1运动对象轨迹数据模型

1.3.2运动对象轨迹聚类距离函数

1.3.3轨迹聚类方法和算法

1.4研究内容

1.5本文章节安排

第2章时空数据库技术概论

2.1时空数据库概述

2.2时空数据表达

2.2.1清晰与确切的表达对象

2.2.2模糊与不确切的表达对象

2.3时空数据建模

2.3.1时空概念建模

2.3.2时空数据建模

2.3.3移动对象建模

2.3.4移动对象轨迹模型

2.4时空数据索引

2.4.1 B-树索引及其变体

2.4.2 R-树索引及其变体

2.4.3其它索引

2.5时空数据查询

2.6时空数据库体系结构

2.6.1分层体系结构

2.6.2单集成的体系结构

2.7时空数据库应用

2.8本章小结

第3章运动对象轨迹聚类算法STCLUS概述

3.1轨迹数据定义模型及相关概念

3.2轨迹聚类算法STCLUS总提纲

3.3轨迹距离函数

3.3.1空间距离函数

3.3.2时间距离和速度距离

3.4本章小节

第4章轨迹分割与线段聚类及予轨迹提取算法

4.1轨迹分割算法

4.1.1简明性和准确性

4.1.2观测现象

4.1.3轨迹分割算法T-part(Trajectory Partition)

4.2基于密度线段聚类算法

4.2.1采用基于密度聚类算法的优势

4.2.2 OPTICS概念描述

4.2.3线段聚类的T-OPTICS(Trajectory-OPTICS)算法

4.2.4可视化识别聚类结构

4.2.5线段簇的优化和提纯

4.3从轨迹分割线段簇中提取代表子轨迹段

4.4本章小节

第5章实验结果与性能评估

5.1实验背景

5.2实验结果

5.2.1参数选择

5.2.2轨迹聚类得到的公共子轨迹

5.2.3执行时间的可伸缩性

5.2.4比较STC LUS算法与TRACLUS算法

总结与展望

参考文献

致谢

攻读硕士学位期间发表论文情况、参与的科研项目