|
Key words: Snake, Line Displacement, Automated Map Generalization, Energy Minimization
Displaying cartographic data on small scale maps requires generalization because objects interfere and the map lacks legibility. Spatial conflicts mainly emerge due to increased symbol width. The visualization of roads especially leads to major overlaps. Such conflicts can be solved by deforming the line, which includes displacing conflicting vertices and propagating these shifts so that the shape of the line is preserved.
Previous approaches (e.g., Nickerson, 1988) fail to preserve line characteristics in general without an elaborate shape analysis that leads to a complex parameter set-up. Moreover, such sequential methods disregard possible propagation facilities (or worse, impossibilities) when computing the initial displacement vectors. The sequentiality becomes a major problem when many lines interfere. A fully-automated generalization approach (Lamy et al., 1999) can not rely on these methods, because the results are not generic enough. Recently, mathematical techniques treating the problem in a more global sense have appeared. Harrie (1999) optimizes a cost function which incorporates cartographic constraints. Burghardt and Meier (1997) address the problem by using variational techniques that minimize the energy of a smooth function rather than of a discrete set of points. He introduces snakes - a wide-spread technique in pattern recognition (Kass et al., 1987). This latter approach is very promising. The underlying concept is to minimize a function which consists of an inner energy, which measures the shape distortion of a displaced line, and an outer energy, which describes the cause of displacement. The distortion of shape is measured by calculating the deviations of first and second order derivatives between the original line and the corresponding displaced line.
The snake approach is interesting because it preserves global line shapes efficiently and, moreover, allows better sharing of the displacement magnitude between interfering lines. However, the existing snake models are not able to preserve positional accuracy nor do they take significant line characteristics into consideration. Important line characteristics such as remarkable bends and straight segments need protection; to enforce geometric accuracy the snake should be squeezed to the initial line. The paper describes how the snake model may be enriched to meet these cartographic requirements. Parameters are refined in order to mirror the underlying line shape. The definition of a new energy function modifies the snake to respect accuracy constraints. Furthermore, special treatment is needed at junctions between lines ('nodes'). Building the skeleton of the road network nodes should remain as close as possible in their initial position. The paper emphasizes how the modification of the adapted model helps optimize node translation with respect to shape preservation.
The paper is a contribution to linear feature generalization since it provides a methodology to solve line conflicts while meeting high cartographic requirements. The need for an improved method is emphasized and the basic idea of snakes is presented as such a method. We describe how this technique can be improved to fulfil important cartographic criteria. Our approach is illustrated by worked examples on real data.
References
Burghardt, D. and Meier, S., 1997, Cartographic displacement using the snakes concept. In Foerstner W. and Pluemer, L. (Eds), Semantic Modeling for the Acquisition of Topografic Information from Images and Maps, Basel, Switzerland, Birkhaeuser.
Harrie, L., 1999, The constraint method for solving spatial conflicts in cartographic generalization. Cartography and Geographic Information Science 26(1), pp. 55-69.
Kass, M.A. et al., 1987, Snakes: Active contour models. Proceedings of the First International Conference on Computer Vision. IEEE Computer Society Press, pp. 259-268.
Lamy, S. et al., 1999, The application of agents in automated map generalisation. Conference Proceedings ICA, Ottawa, Canada, pp.1225-1234.
Nickerson, B.G., 1988, Automatic cartographic generalization for linear features. Cartographica 25(3), pp.15-66.