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.
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 |
|
|
|
|
The proposed algorithm is tested MOPSI Dataset and Microsoft geolife dataset.
Matlab Code can be downloaded here. C++ code will be published soon.
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.
