Simplification of GPS trajectories


Paper: M. Chen, M. Xu, P. Franti, "A Fast O(N) Multi-resolution Polygonal Approximation Algorithm for GPS Trajectory Simplification", IEEE Trans. on Image Processing  pdf




Recent advances in geo-positioning mobile phones have made it possible for users to collect a large number of GPS trajectories by recording their location information. However, these mobile phones with built-in GPS devices usually record far more data than needed, which brings about both heavy data storage and a computationally expensive burden in the rendering process for a web browser.  


Our Algorithms


We present a O(N) bottom-up multi-resolution polygonal approximation algorithm for the GPS trajectory simplification under the so-called integral square synchronous distance error criterion.




Original route with 575 points

Approximated result with 13 vertices for resolution 2

Approximated result with 6 vertices for resolution 3




Visualized approximated result with 44 vertices for resolution 1

Visualized result

Visualized result






Testing Dateset


The proposed algorithm is tested MOPSI Dataset and  Microsoft geolife dataset. 




   Matlab Code can be downloaded here. C++ code will be published soon.


Addtional Notes


   Greedy solution can also have O(N) when LSSD are applied. However, the proposed solution has lower ISSD as fine-tune methods are applied and the "dominated" points are selected at each scale.