B-Spline curve smoothing under position constraints for line generalisation

ABSTRACT

Currently, most of the operations performed for the construction of marine charts are still done manually. However, with the development of more and more powerful techniques, new processing methods must be developed in order to deal with the increasing amount of data and to achieve automatic construction. For that purpose, a new method for line smoothing is introduced in this paper and is applied to the generalisation of isobathymetric lines (lines connecting points at a same depth). The lines are modelled by B-spline curves which maintain their smooth feature. Smoothing is performed by reducing the curvature using a snake model. The generalisation constraint of navigation safety is satisfied by applying position constraints on the line. Spatial conflicts are also taken into consideration and are removed during the process. Parameters are automatically defined so that the method can be applied to large sets without user intervention. The method has been applied on real data sets and examples are provided and discussed for scale reduction of lines.

REFERENCES

• 1: L.-E. Andersson, T. Peters, and N. Stewart. Self-intersection of composite curves and surfaces. Computer Aided Geometric Design, 15(5):507--527, 1998.
• 2: M. Bader. Energy minimization methods for feature displacement in map generalization. PhD thesis, Universität Zürich, 2001.
• 3: P. Brigger, J. Hoeg, and M. Unser. B-spline snakes: A flexible tool for parametric contour detection. IEEE Transactions on Image Processing, 9(9):1484--1496, 2000.
• 4: Dirk Burghardt, Controlled Line Smoothing by Snakes, Geoinformatica, v.9 n.3, p.237-252, September 2005 [doi>10.1007/s10707-005-1283-3]
• 5: D. Burghardt and S. Meier. Cartographic displacement using the snakes concept. In W. Förstner and L. Plümer, editors, Semantic modeling for the acquisition of topographic information from images and maps, pages 59--71, 1997.
• 6: D. Douglas and T. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 10(2):112--122, 1973.
• 7: Gerald Farin, Curves and surfaces for CAGD: a practical guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 8: E. Fritsch. Représentations de la géométrie et des contraintes cartographiques pour la généralisation du linéaire routier. Thése de doctorat, Université de Marne-La-Vallée, 1997.
• 9: M. Galanda and R. Weibel. Using an energy minimization technique for polygon generalization. Cartography and Geographic Information Science, 30(3):263--279, 2003.
• 10: E. Guilbert, E. Saux, and M. Daniel. Conflict removal between b-spline curves for isobathymetric line generalization using a snake model. Cartography and Geographic Information Science, 33(1):37--52, 2006.
• 11: L. Harrie. The constraint method for solving spatial conflicts in cartographic generalization. Cartography and geographic information science, 26(1):55--69, 1999.
• 12: M. Kass, A. Witkin, and D. Terzopoulos. Snakes: active contour models. In Proceedings of International Conference on Computer Vision, pages 259--268, 1987.
• 13: Z. Li and S. Openshaw. Algorithms for automated line generalization based on a natural principle of objective generalization. International Journal of Geographical Information Systems, 6(5):373--389, 1992.
• 14: R. McMaster. The integration of simplification and smoothing algorithms in line generalization. Cartographica, 26:100--121, 1989.
• 15: Helmut Pottmann , Stefan Leopoldseder , Michael Hofer, Approximation with Active B-Spline Curves and Surfaces, Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, p.8, October 09-11, 2002
• 16: E. Saux. B-spline curve fitting: Application to cartographic generalization of maritime lines. In 8th International Conference on Computer Graphics and Visualization (GraphiCon'98), pages 196--203, 1998.
• 17: E. Saux. B-spline functions and wavelets for cartographic line generalization. Cartography and Geographic Information Science, 30(1):33--50, 2003.
• 18: W. Shi and C. Cheung. Performance evaluation of line simplification algorithms for vector generalization. The Cartographic Journal, 43(1):27--44, 2006.
• 19: David Thibault , Christopher M. Gold, Terrain Reconstruction from Contours by Skeleton Construction, Geoinformatica, v.4 n.4, p.349-373, December 2000 [doi>10.1023/A:1026509828354]
• 20: R. Weibel and G. Dutton. Generalising spatial data and dealing with multiple representations. In Geographical Information Systems. Wiley, 1999.
• 21: K. Zakšek and T. Podobnikar. An effective DEM generalization with basic GIS operations. In 8th ICA workshop on Generalisation and Multiple Representation, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms

Keywords:
B-spline curve, cartographic generalisation, smoothing, snake