University of Zurich, Switzerland

Email: mbader@geo.unizh.ch

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.

**Lamy, S. et al.,** 1999, The application of agents in automated
map generalisation.

Nickerson, B.G., 1988, Automatic cartographic generalization for linear
features. *Cartographica* **25**(3), pp.15-66.