VECTOR ROAD MAP COMPRESSION- A PREDICTION APPROACH
Zongyu Zhang · 2006
This paper explores a new method to compress vector road network map. The com-pression schema flows as: (1) Traversing road networks based on its topology; (2) Keeping predicting the next vertex based on the visited vertices; (3) Encoding the prediction errors using the entropy coding method (i.e. Huffman or arith-metical coding). Based on the analysis of the road network’s spanning characteristics, two prediction models will be designed to capture the trends of roads’ “flow” trends. A spanning tree like road network traversal method will be developed to help solve the problem of topological imperfection of digitized road maps and integrate the compression of road network map’s geometrical and topological data. Additionally, a compression benchmark will be designed to help capture the essence of the proposed compression schema and make a fair comparison over the performances of prediction methods. Our prototype implementation has demonstrated that the simple vertex-based linear prediction approach beat the angle length prediction method in reducing the entropy of the predicted vertices’ errors. It also shows the total compression ratio can be close to one eighth for most of the road networks, which agrees with the compression benchmark.