Distortion-constrained compression of vector maps

ABSTRACT

An algorithm for lossy compression of vector maps for given error tolerance was developed. The algorithm is based on optimal polygonal approximation and dynamic quantization of vector data. A near optimal distortion-constrained quantizer with step defined by the tolerance level was constructed. The proposed algorithm performed well compared to other approaches.

REFERENCES

• 1: Akimov, A., Kolesnikov, A., Fränti, P. Coordinate quantization in vector map compression, In Proc. IASTED Int. Conf. Visualization, Imaging and Image Processing-VIIP'04, Marbella, Spain, 2004, 748--753.
• 2: Michela Bertolotto , Max J. Egenhofer, Progressive Transmission of Vector Map Data over the World Wide Web, Geoinformatica, v.5 n.4, p.345-373, December 2001 [doi>10.1023/A:1012745819426]
• 3: Barbara Buttenfield, Transmitting Vector Geospatial Data across the Internet, Proceedings of the Second International Conference on Geographic Information Science, p.51-64, September 25-28, 2002
• 4: Chan, W. S., and Chin, F. On approximation of polygonal curves with minimum number of line segments or minimum error, Int. J. Comput. Geometry and Applications, 6 (1996) 59--77.
• 5: Douglas, D. H., and Peucker, T. K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature, The Canadian Cartographer, 10, 2 (1973), 112--122.
• 6: J G Dunham, Optimum uniform piecewise linear approximation of planar curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.1, p.67-75, Jan. 1986 [doi>10.1109/TPAMI.1986.4767753]
• 7: Hiroshi Imai , Masao Iri, Computational-geometric methods for polygonal approximations of a curve, Computer Vision, Graphics, and Image Processing, v.36 n.1, p.31-41, Oct. 1986 [doi>10.1016/S0734-189X(86)80027-5]
• 8: Kolesnikov, A., and Fränti, P. Optimal multiresolution polygonal approximation, In. Proc. Int. Conf.on Image Processing-ICIP'04, Singapore, October 2004, 3037--3040.
• 9: Kolesnikov, A. Optimal encoding of vector data with polygonal approximation and vertex quantization, In Proc. IAPR 14th Scandinavian Conf. on Image Analysis-SCIA '05, Joensuu, Finland, 2005, LNCS, vol. 3540, 2005, 1186--1195,.
• 10: Kolesnikov, A., and Fränti, P. Data reduction of large vector graphics, Pattern Recognition, 38, 3 (2005), 381--394.
• 11: Li, Z., and Oppenshaw, S. A natural principle for the objective generalization of digital maps, Cartography and Geographical Information Systems, 20, (1993) 19--29.
• 12: Schuster, G. M., and Katsaggelos, A. K. An optimal polygonal boundary encoding scheme in the rate-distortion sense, IEEE Trans. on Image Processing, 7, (1998), 13--26.
• 13: Schuster, G. M., Melnikov, G., and Katsaggelos, A. K. Operationally optimal vertex-based shape coding, IEEE Signal Processing Magazine, vol. 15, (1998), 91--108.
• 14: Shashi Shekhar , Yan Huang , Judy Djugash , Changqing Zhou, Vector map compression: a clustering approach, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA [doi>10.1145/585147.585164]
• 15: S. Shekhar , Y. Huang , J. Djugash, Dictionary Design Algorithms for Vector Map Compression, Proceedings of the Data Compression Conference (DCC '02), p.471, April 02-04, 2002
• 16: Visvalingam, M., and Whyatt, J. Line generalization by repeated elimination of points, Cartographic Journal, 30, 1 (1993), 46--51.
• 17: Wu, X. L∞-constrained high fidelity image compression via adaptive context modeling, IEEE Trans. on Image Processing, 9, (2000) 536--542.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

General Terms:
Algorithms

Keywords:
compression, polygonal approximation, quantization, simplification, vector map