* Corresponding author
Noise Filtering, Trajectory Compression and
Trajectory Segmentation on GPS Data
Kunhui Lin Zhentuan Xu Ming Qiu
*
Xiaoli Wang Tianxiong Han
Software School of Software School of Software School of Software School of Software School of
Xiamen University Xiamen University Xiamen University Xiamen University Xiamen University
Xiamen,China Xiamen,China Xiamen,China Xiamen,China Xiamen,China
khlin@xmu.edu.cn xuzhentuan@126.com mingqiu@xmu.edu.cn xlwang@xmu.edu.cn 592211453@qq.com
Abstract—With the rapid development of GPS devices,
satellite and wireless communications technologies, many
trajectory data is generated. Consequently, processing and
analyzing trajectory data have become a hot topic. In this
paper, an improved noise filtering, trajectory compression and
trajectory segmentation method based on Kalman filter and
Douglas-Peucker algorithm and corner is proposed. Firstly, the
Kalman filter is used to filter noise in the trajectory and
making a mark in the points whose direction change are
greater than threshold. Secondly, combine the Douglas-
Peucker algorithm with the Sliding Window algorithm to
approximate the trajectory. Thirdly, segmenting the trajectory
into trajectory segmentation set according to the corner and
predefined corner threshold. Experiments on real dataset
demonstrate the efficiency and effectiveness of the improved
method, getting a good noise filtering and trajectory segment
results and have practical significance.
Index Terms—Trajectory Segmentation, GPS Trajectory,
Douglas-Peucker Algorithm, Corner, Noise Filtering
I.
INTRODUTION
With the development of science and technology, the
GPS receivers and 3G/4G cellular network or location
sensing technology embedded in mobile devices, such as
automobiles and smartphones, have been widely used in
practice. Thereby a large number of trajectory data which
contain a lot of valuable information is generated.
Such rich trajectories data offer us useful information to
understand locations and moving objects. It is a chance to
extract the movement characteristic patterns of moving
objects and to predict the movement behavior of the moving
objects and to understand traffic patterns [1].
Before using trajectory data, it is unavoidable to deal
with some issues, for example, noise filtering, stay point
detection, compress trajectory data and trajectory
segmentation. In general, it is called trajectory preprocessing
that is a fundamental step of lots of trajectory data analysis
work and mining tasks [2].
The purpose of noise filtering is to remove or replace
from trajectories some noise points which may be caused by
the poor signal of location positioning systems. Stay point
detection is to identify the location where a moving object
has stayed for a moment within a certain time threshold. A
stay point could stand for traffic light or starting point or
destination point. In order to reduce overhead in
communication, processing and data storage, trajectory
compression compresses the size of a trajectory while
maintaining the utility of trajectories. Moreover, trajectory
segmentation divides trajectories into fragments by spatial
shape, time interval or other factors so as to further process
like classification and clustering can get better result.
Intensive and extensive research has been done in the
field of trajectory data analysis and mining. Some researches
[3-4] take the whole trajectory as the basic unit into
calculation. There are two problems exist in the solution.
Firstly, it is unable to find common sub-pattern in the
trajectories. Secondly, it will ignore local characteristic of
trajectories.
Some other researches [6-8] take trajectory segmentation
into account and proposed some different segmentation
methods, which will introduce in the next section. These
segmentation methods have advantages and disadvantages
and none of the methods has been widely used so far.
In this paper, an improved noise filtering, trajectory
compression and trajectory segmentation method is proposed.
We have made improvements in the following areas.1) We
use the Kalman filter to filter noise in the trajectory and
improve it by marking the points whose direction change are
greater than direction threshold. 2) The Douglas-Peucker
algorithm is combined with the Sliding Window algorithm to
approximate the trajectory. Those marked points are used as
window split point for the input of algorithm. 3) Trajectory
corners of line simplification trajectories are calculated and
segmenting trajectories into trajectory segmentation set that
contain local feature according to the corner and corner
threshold. 4) In order to improve accuracy, the GPS
coordinate is converted into Mercator plane coordinate for
calculation. 5) In improved method, the knowledge of
triangle is applied to calculate distance in Douglas-Peucker
algorithm and calculate corner in trajectory segmentation.
The rest of the paper is organized as follows. Section II
discusses related work. An improved method is proposed in
Section III. Section IV presents the results of experimental
evaluation. Finally, conclusions are drawn in Section V.
II.
R
ELATED
WORK
A. Data processing based on GPS trajectory
Kreveld et al. [3] firstly introduced time-dependent
relationship into the shape-dependent trajectory analysis, and
978-1-5090-2218-2/16/$31.00 ©2016 IEEE
The 11th International Conference on
Computer Science & Education (ICCSE 2016)
August 23-25, 2016. Nagoya University, Japan
490
WdP1.2