Leveraging similarity analysis to understand variability in movement behavior

The increasingly large volume of trajectories of moving entities obtained through GPS and cellphone tracking, telemetry, and other location-aware technologies motivates researchers to understand the implicit patterns hidden in movement trajectories and understand how movement is influenced by the environmental context. Trajectory similarity serves as an important tool in computational movement analysis and as the foundation of revealing those patterns. However, there are various trajectory similarity measures, each of which has its own strengths and weaknesses. In this article, we present a hierarchical clustering framework that integrates five commonly used similarity measures, including Fréchet distance, dynamic time warping, Hausdorff distance, longest common subsequence, and normalized weighted edit distance, a special kind of edit distance for movement analysis. The framework aims at clustering similar patterns and identifying variability in movement. The optimal number of clusters are first obtained. Then, the clusters are characterized by environmental variables to explore the associations between variability in movement and the environmental conditions. We evaluate the proposed framework using 15 years of tracking data of turkey vultures, tracked at 1- to 3-h sampling intervals, during their fall and spring migration seasons. The results suggest that, at 5% significance level, turkey vultures select their movement paths intentionally and those selections appear to be related to certain environmental context variables, including thermal uplift, vegetation state (observed indirectly through Normalized Difference Vegetation Index), temperature, precipitation, tailwind, and crosswind. And interestingly, there exist preferential differences among individuals. Although the preference of the same turkey vulture is not strictly consistent over different years, each individual tends to preserve a more similar preference over different years, compared with the preferences of other turkey vultures.     

利用浮动车GPS轨迹识别与提取城市道路交叉口

道路交叉口作为道路交汇的枢纽,是路网的重要组成部分,也是最重要的基础地理信息数据之一。浮动车GPS数据具有易获取、低成本和数据量大等优点,但工作同时伴随不少噪点。为了降低噪点对交叉口提取过程的影响,提高计算效率,本文运用KNN算法建立空间索引;计算向量夹角,判定道路出入口,粗筛取交叉口附近点;分别采用K-means算法、DBSCAN算法和层次算法进行聚类分析,进一步确定交叉口位置。最后以成都某区域浮动车GPS数据为例,提取道路交叉口并进行了对比分析,进一步表明本文方法可以服务于智能交通研究与应用。     

Travel time estimation at intersections based on low-frequency spatial-temporal GPS trajectory big data

ABSTRACT

Intersections are the critical parts where different traffic flows converge and change directions, forming “bottlenecks” and “clog points” in urban traffic. Intersection travel time is an important parameter for public route planning, traffic management, and engineering optimization. Based on low-frequency spatial-temporal Global Positioning System (GPS) trace data, this article presents a novel method for estimating intersection travel time. The proposed method first analyzes the different travel patterns of vehicles through an intersection, then determines the range of an intersection dynamically and reasonably, and obtains traffic flow speed and delay at the intersection under different travel patterns using a fuzzy fitting approach. Finally, the average intersection travel time is estimated from traffic flow speed and delay and intersection range in different travel patterns. Wuhan road network data and GPS trace data from taxicabs were tested in the experiments and the results show that the proposed method can improve the accuracy of travel time estimation at city intersections.     

基于地理格网的复杂路线车辆通行时间估算方法

车辆通行时间隐含了特定时隙的交通状况，准确地计算该时间在交通监测和路径规划中具有重要意义。现有研究通常利用车辆历史轨迹估算一定距离内选定路径的通行时间，然而当路径距离较长时，限于很难找到完整穿越指定路径的历史轨迹而无法对其通行时间进行准确估计；此外，海量历史轨迹在估计路径通行时间时会产生巨大的数据管理和计算压力。因此，本文引入地理格网，首先构建统一的时空索引，将路网及其历史轨迹分别划分为一系列落在地理格网单元（Cell）中的路段模式及轨迹段；然后利用一系列频繁共享轨迹在Cell中的停留时间计算车辆在当前路段模式的通行时间；最后通过一组历史时段相似路径模式的通行时间估算较长路线的车辆通行时间。通过对北京市10 000辆出租车一周的轨迹数据进行试验，验证了本文方法在处理海量历史轨迹数据上的有效性，以及在估算较长路径上车辆通行时间的优越性。     

一种利用低频轨迹数据提取道路交叉口的方法

为实现从低频轨迹数据中提取城市道路交叉口,本文设计了一种基于数据预处理与聚类算法的道路交叉口精准识别方法。首先结合轨迹数据的特征,采用启发式滤波算法对原始数据进行清洗,剔除冗余点与异常点;然后依据车辆的运行规律,提出了一种分步式道路交叉口的提取算法,由此计算出疑似道路交叉口的特征点;最后利用层次密度聚类算法(HDBSCAN)对筛选过后的轨迹点进行聚类并提取质心,得到道路的交叉口,最终以成都市某日的出租车行驶轨迹为数据源,进行试验分析。结果表明,使用该算法提取交叉口,精确率达95.33%、召回率达82.11%、F值达88.46%,能有效且准确识别城市道路交叉口信息,在城市管理与交通规划中具有一定的应用价值。     

一个从基于位置相关服务而收集的零星位置点中获取连续车辆轨迹的方法(英文)

The paper proposes an economical and fast algorithm for deriving trajectories from sporadic tracking points collected in location-based services (LBS). Although many traffic studies or applications can benefit from the derived trajectories, the sporadic tracking points are always implicitly overlooked by most of existing map-matching algorithms. The algorithm proposed in this paper finds network paths or trajectories traveled by vehicles through augmenting GPS data with odometer data. An odometer can provide data of traveled distance which are compared with the lengths of candidate network paths in order to find the most approximate network path approaching the trajectory of a vehicle. Tracking points are classified into anchor points and non-anchor points. The former are used to divide trajectories, and the latter screen candidate network paths. An elliptic selection zone and a reduction process are applied to the selection of possible road segments composing candidate network paths. A brute-force searching algorithm is developed to find candidate network paths and calculate their lengths. A two-step screening process is designed to select the final result from candidate network paths. Finally, a series of experiments are conducted to validate the proposed algorithm. Supported by the National Natural Science Foundation of China (No.40701142), the Scientific Research Starting Foundation for Returned Overseas Chinese Scholars, Ministry of Education, China.     

Detecting vehicle traffic patterns in urban environments using taxi trajectory intersection points

Abstract

Detecting and describing movement of vehicles in established transportation infrastructures is an important task. It helps to predict periodical traffic patterns for optimizing traffic regulations and extending the functions of established transportation infrastructures. The detection of traffic patterns consists not only of analyses of arrangement patterns of multiple vehicle trajectories, but also of the inspection of the embedded geographical context. In this paper, we introduce a method for intersecting vehicle trajectories and extracting their intersection points for selected rush hours in urban environments. Those vehicle trajectory intersection points (TIP) are frequently visited locations within urban road networks and are subsequently formed into density-connected clusters, which are then represented as polygons. For representing temporal variations of the created polygons, we enrich these with vehicle trajectories of other times of the day and additional road network information. In a case study, we test our approach on massive taxi Floating Car Data (FCD) from Shanghai and road network data from the OpenStreetMap (OSM) project. The first test results show strong correlations with periodical traffic events in Shanghai. Based on these results, we reason out the usefulness of polygons representing frequently visited locations for analyses in urban planning and traffic engineering.     

红绿灯配时优化与仿真研究

固定相位时长的信号灯控制由于无法根据实时路况进行自适应调节,对交通拥堵现象的改善程度有限。为了模拟根据实时路况进行信号灯相位自适应调节,以Webster算法为基础,融合虚拟仿真和计算机视觉技术,构建信号灯配时优化与自反馈闭环系统。首先,构建基于Unity3D的道路交通仿真场景,模拟车辆启停、行驶及信号灯控制;然后,利用OpenCV库处理采集的车流视频,统计通车流量并计算最佳信号周期和确定通车相位;最后,将配时计算结果作用于仿真场景,实现信号灯相位的实时调整与优化循环。仿真实验结果表明,信号灯自适应配时优化与闭环反馈能较大幅度减少车辆等待时间,有效缓解交通拥堵状况。     

利用时空密度聚类的高速公路交通事故黑点路段鉴别

研究高速公路交通事故黑点路段的时空分布规律和关联因素,一直是交通领域的关注重点。本文针对事故统计的交通事故黑点路段鉴别方法存在地理学中的可塑面积单元(MAUP)问题,提出一种基于时空密度聚类的高速公路交通事故黑点路段鉴别方法。该方法改进了传统的DBSCAN空间聚类算法,引入一种顾及时间周期性和事故严重程度的事故时空邻近计算方法,通过密度连接规则自适应鉴别各种时空尺度的交通事故黑点路段。以2012—2016年湖南省的高速公路交通事故为例进行试验,结果表明,本文方法可有效克服不同划分单元的可塑面积单元问题,自适应鉴别不同长度的黑点路段,同时可进一步挖掘黑点路段上交通事故时空聚集模式。     

利用行人轨迹挖掘城市区域功能属性

城市土地利用功能区是城市规划中的一个重要概念,遥感技术手段在城市土地利用类型识别和动态监测中取得了很大进展。然而,由于城市实际功能的复杂,往往很难从遥感影像中获得城市各个区域的社会、经济或文化等功能属性。互联网技术的发展和移动定位设备的普及,极大地便利了行人移动轨迹数据的获取。本文从行人移动规律和模式与城市功能分区之间高度相关的角度出发,通过机器学习的方法,从大量行人轨迹数据中挖掘隐含的城市功能属性与强度。该方法首先利用矢量栅格化和数学形态学方法,将城市不同等级的路网分割为互不相同的空间单元;其次,根据行人轨迹数据的时空分布特点,定义9个变量并构建高斯混合模型(Gaussian mixture model,GMM),对上述空间单元进行非监督分类,得到7种城市用地类型;随后,结合选定的60个样本区以及人为标识的6种功能区(教育用地、绿地休闲区、一般商业区、政府设施、中心商业区、住宅区),依据样本功能区GPS轨迹时间分布特征,最终对7种城市用地类型进行功能配对;最后,利用核密度估计方法进行功能区强度的可视化。该框架结合机器学习的优势,结果具有较高的准确度。     

Modeling long-period noise in kinematic GPS applications

We develop and test an algorithm for modeling and removing elevation error in kinematic GPS trajectories in the context of a kinematic GPS survey of the salar de Uyuni, Bolivia. Noise in the kinematic trajectory ranges over 15 cm and is highly autocorrelated, resulting in significant contamination of the topographic signal. We solve for a noise model using crossover differences at trajectory intersections as constraints in a least-squares inversion. Validation of the model using multiple realizations of synthetic/simulated noise shows an average decrease in root-mean-square-error (RMSE) by a factor of four. Applying the model to data from the salar de Uyuni survey, we find that crossover differences drop by a factor of eight (from an RMSE of 5.6 to 0.7 cm), and previously obscured topographic features are revealed in a plan view of the corrected trajectory. We believe that this algorithm can be successfully adapted to other survey methods that employ kinematic GPS for positioning.     

利用GPS轨迹二次聚类方法进行道路拥堵精细化识别

针对当前在精细识别道路拥堵时空范围方面研究的不足,提出一种利用GPS轨迹的二次聚类方法,通过快速识别大批量在时间、空间上差异较小且速度相近的轨迹段,反映出道路交通状态及时空变化趋势,并根据速度阈值确定拥堵状态及精细时空范围。首先将轨迹按采样间隔划分成若干条子轨迹,针对子轨迹段提出相似队列的概念,并设计了基于密度的空间聚类的相似队列提取方法,通过初次聚类合并相似子轨迹段,再利用改进的欧氏空间相似度度量函数计算相似队列间的时空距离,最后以相似队列为基本单元,基于模糊C均值聚类的方法进行二次聚类,根据聚类的结果进行交通流状态的识别和划分。以广州市主干路真实出租车GPS轨迹数据为例,对该方法进行验证。实验结果表明,该二次聚类方法能够较为精细地反映城市道路的拥堵时空范围,便于管理者精准疏散城市道路拥堵,相比直接聚类方法可以有效提升大批量轨迹数据的计算效率。     

利用轨迹大数据进行城市道路交叉口识别及结构提取

交叉口是城市交通路网生成、更新的重要组成部分。本文基于车辆时空轨迹大数据,提出了一种城市交叉口自动识别方法。该方法首先通过轨迹跟踪识别轨迹数据中包含的车辆转向点对;然后基于距离和角度的生长聚类方法进行转向点对的空间聚类,并采用基于局部点连通性的聚类方法识别交叉口;最后利用交叉口范围圆和转向点对提取城市各级别路网下的交叉口结构。以武汉市出租车轨迹大数据为例,对武汉市城区内189个交叉口进行了探测。试验结果表明,本文所提方法可以准确地从轨迹大数据中识别出城市交叉口及其结构。     

An intersection‐based trajectory‐region movement study

In order to better understand the movement of an object with respect to a region, we propose a formal model of the evolving spatial relationships that transition between local topologies with respect to a trajectory and a region as well as develop a querying mechanism to analyze movement patterns. We summarize 12 types of local topologies built on trajectory‐region intersections, and derive their transition graph; then we capture and model evolving local topologies with two types of trajectory‐region strings, a movement string and a stop‐move string. The stop‐move string encodes the stop information further during a trajectory than the movement string. Such a string‐format expression of trajectory‐region movement, although conceptually simple, carries unprecedented information for effectively interpreting how trajectories move with respect to regions. We also design the corresponding Finite State Automations for a movement string as well as a stop‐move string, which are used not only to recognize the language of trajectory‐region strings, but also to deal effectively with trajectory‐region pattern queries. When annotated with the time information of stops and intersections, a trajectory‐region movement snapshot and its evolution during a time interval can be inferred, and even the relationships among trajectories with respect to the same region can be explored.     

网络空间中线要素的核密度估计方法

核密度估计(KDE)方法是分析点要素或线要素空间分布模式的一种重要方法,但目前线要素核密度方法只能分析线要素在二维均质平面空间的密度分布,不能正确分析交通拥堵、交叉口排队、出租车载客等线事件在一维非均质道路网络空间中的密度分布。本文提出了一种网络空间中线要素的核密度估计方法(网络线要素KDE方法),首先确定每个线要素在网络空间上的密度分布,然后根据网络空间距离和拓扑关系确定网络空间的线要素核密度与时空分布。以出租车GPS轨迹数据中提取的"上客"线事件为例,分析出租车"上客"线事件在网络空间中的密度分布,通过与现有方法比较的试验结果表明,本文提出的方法更能准确反映路网空间中线事件的分布特征。     

Traj2Traj: A road network constrained spatiotemporal interpolation model for traffic trajectory restoration

In transportation, the trajectory data generated by various mobile vehicles equipped with GPS modules are essential for traffic information mining. However, collecting trajectory data is susceptible to various factors, resulting in the lack and even error of the data. Missing trajectory data could not correctly reflect the actual situation and also affect the subsequent research work related to the trajectory. Although increasing efforts are paid to restore missing trajectory data, it still faces many challenges: (1) the difficulty of data restoration because traffic trajectories are unstructured spatiotemporal data and show complex patterns; and (2) the difficulty of improving trajectory restoration efficiency because traditional trajectory interpolation is computationally arduous. To address these issues, a novel road network constrained spatiotemporal interpolation model, namely Traj2Traj, is proposed in this work to restore the missing traffic trajectory data. The model is constructed with a seq2seq network and integrates a potential factor module to extend environmental factors. Significantly, the model uses a spatiotemporal attention mechanism with the road network constraint to mine the latent information in time and space dimensions from massive trajectory data. The Traj2Traj model completes the road-level restoration according to the entire trajectory information. We present the first attempt to omit the map-matching task when the trajectory is restored to solve the time-consuming problem of map matching. Extensive experiments conducted on the provincial vehicle GPS data sets from April 2018 to June 2018 provided by the Fujian Provincial Department of Transportation show that the Traj2Traj model outperforms the state-of-the-art models.     

Path-finding through flexible hierarchical road networks: An experiential approach using taxi trajectory data

Optimal paths computed by conventional path-planning algorithms are usually not “optimal” since realistic traffic information and local road network characteristics are not considered. We present a new experiential approach that computes optimal paths based on the experience of taxi drivers by mining a huge number of floating car trajectories. The approach consists of three steps. First, routes are recovered from original taxi trajectories. Second, an experiential road hierarchy is constructed using travel frequency and speed information for road segments. Third, experiential optimal paths are planned based on the experiential road hierarchy. Compared with conventional path-planning methods, the proposed method provides better experiential optimal path identification. Experiments demonstrate that the travel time is less for these experiential paths than for paths planned by conventional methods. Results obtained for a case study in the city of Wuhan, China, demonstrate that experiential optimal paths can be flexibly obtained in different time intervals, particularly during peak hours.     

Path segmentation for movement trajectories with irregular sampling frequency using space‐time interpolation and density‐based spatial clustering

Path segmentation methods have been developed to distinguish stops and moves along movement trajectories. However, most studies do not focus on handling irregular sampling frequency of the movement data. This article proposes a four‐step method to handle various time intervals between two consecutive records, including parameter setting, space‐time interpolation, density‐based spatial clustering, and integrating the geographic context. The article uses GPS tracking data provided by HOURCAR, a non‐profit car‐sharing service in Minnesota, as a case study to demonstrate our method and present the results. We also implement the DB‐SMoT algorithm as a comparison. The results show that our four‐step method can handle various time intervals between consecutive records, group consecutive stops close to each other, and distinguish different types of stops and their inferred activities. These results can provide novel insights into car‐sharing behaviors such as trip purposes and activity scheduling.     

Trajectories of Moving Objects on a Network: Detection of Similarities,Visualization of Relations,and Classification of Trajectories

Development in techniques of spatial data acquisition enables us to easily record the trajectories of moving objects. Movement of human beings, animals, and birds can be captured by GPS loggers. The obtained data are analyzed by visualization, clustering, and classification to detect patterns frequently or rarely found in trajectories. To extract a wider variety of patterns in analysis, this article proposes a new method for analyzing trajectories on a network space. The method first extracts primary routes as subparts of trajectories. The topological relations among primary routes and trajectories are visualized as both a map and a graph‐based diagram. They permit us to understand the spatial and topological relations among the primary routes and trajectories at both global and local scales. The graph‐based diagram also permits us to classify trajectories. The representativeness of primary routes is evaluated by two numerical measures. The method is applied to the analysis of daily travel behavior of one of the authors. Technical soundness of the method is discussed as well as empirical findings.     

Enhancing data privacy with semantic trajectories: A raster‐based framework for GPS stop/move management

Tracking facilities on smartphones generate enormous amounts of GPS trajectories, which provide new opportunities to study movement patterns and improve transportation planning. Converting GPS trajectories into semantically meaningful trips is attracting increasing research effort with respect to the development of algorithms, frameworks, and software tools. There are, however, few works focused on designing new semantic enrichment functionalities taking privacy into account. This article presents a raster‐based framework which not only detects significant stop locations, segments GPS records into stop/move structures, and brings semantic insights to trips, but also provides possibilities to anonymize users’ movements and sensitive stay/move locations into raster cells/regions so that a multi‐level data sharing structure is achieved for a variety of data sharing purposes.