Email: mbader@geo.unizh.ch , barrault@geo.unizh.ch
Problems arise when the user requires a map at a scale significantly smaller than that associated with the source data. Typical consequences of displaying pregeneralized data at a smaller scale than originally intended are that the detail of individual map features may become too small to be legible, while neighboring symbols that should be clearly distinguished may become too close or they may overlap each other. These latter problems of graphic conflict arise in particular when the map symbols are no longer true to scale of the features they represent.
Both in traditional and computeraided generalization, many operators have been identified. Line simplification is probably the best studied operator. In recent years special attention was paid to displacement. Displacement is necessary mainly due to increased symbol width of roads. The road symbols may be much wider, when map scale is taken into account, than the width of the road on the ground.
In this field of research mainly two types of displacement problems are discussed. First the relocation of buildings in a road partition is studied. Due to the increased width of the road symbol and the increased minimal distance between objects, buildings need to be shifted away from the road. This task becomes considerably complex if the free space is limited by other roads. A second type of algorithms intends to solve conflicts between roads. Such conflicts are resolved by shifting and deforming conflicting line fragments. In this article we focus mainly on propagation  an important step in the displacement process of such line conflicts.
The trigger for propagation is a displacement vector applied to a vertex within a line (see Figure 1). In the generalization process such a displacement vector is often the result of a previous algorithm specifying the amount and direction of displacement that would resolve a proximity conflict between two lines in the conflict spot. [However, the displacement vectors in the illustrations of this paper are specified by the user and are not the result of any computation.]

Displacement propagation needs to balance those conflicting constraints. The aim is to limit the propagation such that the character of the targeted line is preserved within a minimal cushioning distance. It is the cartographer who judges whether small shape distortion at the cost of reduced geometric accuracy is more important than higher precision at the cost of higher shape distortion.

We denote these constraints as intraline constraints. Such constraints can be evaluated taking only one line into consideration. Many more constraints come into play when we include interline problems. Such constraints describe the behavior between lines. We distinguish two types of interline problems. On the one hand, lines must be treated together if they are connected. If a line in a connected network is moved, the network has to react to this shift to avoid loss of connectivity. We will discuss such problems in Section 3. On the other hand, lines interact if they share any special spatial relationship, such as proximity and alignments. In this paper we do not respect such problems.
Recently researchers started tackling the problem in a different way. Instead of deriving displacement sequence, displacement direction, displacement magnitude and propagation in a sequence of tedious steps, displacement is regarded in a more global sense and is modeled as an optimization problem. E.g. Harrie (1999) minimizes the violation of geometric constraints which describe the shortcomings of a map, using a least squares method. Other researchers brought up energy minimizing techniques based on variational principles. Højholt's (2000) approach stems from solid mechanics. He models the map space as elastic material. The method is very promising for area displacement, but lacks from possibilities to integrate the character of lines. Burghardt (1997) adopted the technique of snakes for displacement. We will describe the basics of snakes in the next section and improve the model for cartographic displacement.
Thus the goals of this article are twofold: Enhance the adaption of the snake technique for cartographic generalization  a key requisite to a global displacement method; And present a robust, easy to handle and universally applicable algorithm for propagation. While displacement deals with the conflicts arising between lines, propagation is limited to intraline shape preservation.
In the next section we present the idea of snakes. The basic model is enriched in Section 3 to honor additional cartographic requirements, followed by a general outlook.
Snakes are a special case of deformable models. They were proposed by Kass et al. (1987) in the field of computer vision. The aim of the method in its initial form was to extract smooth shapes in a given region of a a raster image. The idea is to introduce an elastic curve (line) in the image, and let it evolve from an initial position under the action of internal forces (smoothness constraints) and external forces (attraction towards salient edges). Under these forces the line meanders towards a position of minimal energy. This movement resembles the one of a snake  that's where the method derived its name.
We formulate directly the model adopted to cartographic line treatment
and recall some definitions. Let
denote a line of length .
We define displacement as a mapping
where denote the coordinates of the initial line and , give the coordinates of the displaced line. So is a parameter representation of the displacement between the initial (original) line and a derived (displaced) line. We define a deformable model as a space of admissible deformations of the line and a functional representing the energy of a deformation.
This functional represents the energy of the model and has the form(2) 
where
and
denote derivatives of
with respect to
and where
is a potential associated with external influences (see below). The aim
of the method is to find among all admissible deformations
the deformation that minimizes this energy.
Inner Energy In contrast to classical snakes in computer vision, the inner energy defined in (2) does not mirror the geometry of a line, but measures the difference between two lines  the initial line and its geometry after propagation. Deviations of first and second order derivatives are used as quality measures. Such a treatment was proposed by Radeva et al. (1995) to incorporate structural information of objects in object recognitions. We owe the basic snake approach in cartographic generalization to Burghardt (1997). The properties of the model are controlled by the parameters and . Their choice determines the elasticity and rigidity of the model. A discussion of these values is subject of Chapter 3.
External Energy The outer energy is an arbitrary value that penalizes (or rewards) a current deformation of the line based on external criterias. E.g we could penalize a deformation when two neighboring lines get in conflict due to an intended shift. The power of snakes lies to a big part in this interplay between external forces, pushing a snake towards admissible places of interest, and internal regularization forces, making the line resemble its initial form. For this article we do not use any external energy. We give an outlook of this promising interplay in Section 4. As pointed out in section 1.1, we focus on intraline problems which are guided by the line's inner energy only. A thorough understanding of the inner energy is a key step towards a global displacement method.
The space of admissible deformations in (1) is restricted by the boundary conditions , , , , which define the displacements and line direction at the snake's head and tail. The aim is to minimize the energy stored in the line defined by the distance function subject to these imposed boundary conditions. These values define the best displacement.
According to the calculus of variations, is a local minimizer for if it satisfies the associated EulerLagrange equations
Here we already removed the external energy term which we assume to be zero. This is a pair of two independent differential equations of fourth order. It is solved for the direction, setting, and the direction using.Factoring out deformation dependent external energies makes the solution easier, as we can avoid an iterative solution. Because we can solve (2) without iteration, no snake is wiggling through the map. Nevertheless we maintain the name 'snake', as the definition of the inner energy is characteristic for snakes in computer vision and because the model can easily be extended again to incorporate external effects.
For the numerical solution of the partial differential equations we used a finite element method (FEM). Our implementation follows the ideas by Cohen and Cohen (1993), whereby line segments define a natural tesselation of the line. We did choose firstorder (cubic) Hermitian polynomials as basis functions. The finite element method leads to a linear eqaution system , where the matrix is symmetric, positive definite and pentadiagonal. From the solution, we can derive the necessary displacements.
If we apply the method with zeroboundary conditions, a valid solution for is . The resulting function is vanishing. So no displacement is applied if the snake is activated with vanishing displacements at the end. Of course we apply usually nonvanishing boundary conditions to one end, as we use a predefined displacement vector in the conflict spot as fixed tail of the snake, limiting the space of admissible deformations to such deformations that perform the required displacement.
We also tested a finite difference approximation, see Kass et al. (1987), Neuenschwander (1995) and Burghardt (1997). For equidistant and dense point sampling both methods work well and produce similar results. For irregular point sampling  which we encounter often in digitized roads  and large segments, the FEM is better suited. The results do not vary with the sampling, but with the shape of the line only.
Figure 3 shows the application of snakes for displacement propagation. Throughout the paper, arrows in figures indicate a user defined displacement which is imposed as boundary conditions to one side of the snake. Such a displacement vector is usually the result of a previous algorithm based on an analysis of the conflict area. Circles mark places where the snake is fixed at places on the initial line. So in Figure 3 we applied two snakes. Both snakes have their tails fixed to zero displacement somewhere on the initial line and the head fixed to the desired displacement. We incorporate boundary conditions such that the direction of the snakes head and tail stay the same as they were on the initial line. Thus we can ensure smooth transitions (first order continuity) between the snakes. Of course, it does not matter which end is the head and which is the tail of a snake. We just use these terms to distinguish the two ends of the snake.

Even though the results are fine in the above example, the approach violates important cartographic requirements:
To achieve this goal, we extend the standard snake model by an attraction term.
The term
is added to the internal energy (2)
and penalizes the line as long as it does not coincide with the original
position yet. As a consequence, the line strives to fall back to its initial
position. The higher the value for ,
the higher positional accuracy is assessed in comparison to the shape parameters
and .
Incorporating this additional term is straightforward. Applying the EulerLagrange equation we obtain
In Figure 4 the results
of applying the improved propagation is shown using different values for .
We can now choose any point on the line as the tail of the snake and get
the same result. The line will fall back to its initial position as soon
as possible. Only a subset of the entire snake length is used to cushion
the displacement. We can always use the line's endpoint as a snake limiting
extent and do not have to consider about the claimed extent of cushioning.
Of course, this is only true if the line is long enough to incorporate
a specified displacement. If the line is too short, resp. a displacement
offset is required close to the line's endpoint, the method mismatches
the displacement. The displacement changes the character of the line. We
return to this point in Section
3.3.

For problem (2) we change the parameters within each segment. We decrease and for those parts of a line which are oriented in displacement direction. Such a treatment makes these segments shrinking or growing such that they absorb more of the displacement magnitude. This approach is only useful for segments that are oriented in displacement directions, as other segments would be modified in a unacceptable way. They would compensate a desired displacement by changing their direction. This is no problem for segments placed in displacement direction, as they have no motivation to change their initial bearing.
Finally we protect any important feature of the line by increasing and drastically in these segments. This keeps the shape of the detected feature untouched. In Figure 5 results with the improved technique are illustrated.

This new demand is met by identifying a line as one snake only. The desired displacement is applied to an interior vertex of the snake. For the head and tail no displacement is prescribed. As we incorporated a term, the head and tail gravitate to their initial position by themselves (see Figure 6).

Another, more global approach is to handle the entire network simultaneously. Consider a connected set of lines. We allow the junctions to move, but assume the set is chosen such that any displacement can be cushioned without moving the endnodes (see definitions in 1.1). We model each line as individual snake. For each snake we can build a linear equation system as sketched in section 2. We do not use the extendedmodel and do not yet impose any boundary conditions to this equation system. So the resulting snake matrix is singular and thus the linear equation system has no solution. This is no surprise, as no best configuration can be found if we do not define a displacement nor a fixing to the lineends. In a next step we assemble all the single snake matrices in a huge matrix, which defines the entire road network. When snakes join nodes  which happens in all intersections  the values of the matrix cells are just added. So, a displacement of the intersection node affects all lines ending in the said node. Finally we impose the boundary conditions on the global matrix. Every endnode is fixed and the required displacement is included in the matrix.
This modification enables us to compute propagation for an arbitrary placed displacement vector in the road network. For the sake of simplification and computer power, a partitioning of the road network is usually applied before starting any generalization algorithm. These partition boundaries have to stay fixed to ensure smooth transitions between them. Therefore we applied no displacement to the endnodes in above description.
The scope of this paper unfortunately does not allow a detailed discussion of the advantages and drawbacks of the two proposed techniques.

Applying the algorithm to connected roads meets the cartographic demands (see Figure 8). Junctions move with more resistance, as they pass on the shifting to two or more other lines. Due to different settings of the shape parameters , displacement is strongly cushioned in the sinuous line to avoid passing over a displacement vector to the rigid main roads.

The process is guided using a single parameter . This parameter allows the map producer to weigh requirements concerning positional accuracy against shape distortion. If set once, the parameter is generally valid for an entire map series. Reference values for and are set internally. The initial absolute values are mostly arbitrary. The relative magnitude with respect to each other determines the sensitivity of lines.
Results do not depend on the sampling scheme and density of the line. Therefore we do not have to introduce auxiliary points to support the computation. We keep the amount of vertices low. Results were generated on a testbed implemented in Java on a Sun Ultra 30. Computing resources are mainly consumed by the Cholesky factorization to solve the linear equation system. We integrated a Cholesky factorization which does not respect the sparseness of the matrix. Note that the pentagonal structure of the global matrix is destroyed when handling more than one snake. Nevertheless, computation of up to 200 vertices is performed in less than a second.
This paper presented an algorithm for displacement propagation in cartographic line displacement. The method is based on snakes, a technique introduced to generalization by Burghardt (1997). The underlying energy definition was changed to perform fast cushioning of displacement. A special assembly of several snakes was presented which allows extending the method for entire road networks. The result of a preceding analysis of line shape and characteristics is translated into the model via setting model inherent shape parameters.
Our model does not include any external energy yet. Burghardt (1997)
already presented a method to handle displacement using snakes. For each
line a displacement potential is computed based on proximity measures.
In the conflicting areas, forces are applied to the snakes which push them
away from the conflict spots. The snakes iteratively leave the area of
conflicts. The propagation of such a displacement is guided by the inner
energy. Our proposed modification of the snake improves the quality of
such solutions. The characterization of lines, resulting in different resistance
against deformations, helps to
make the best suited roads move. Our future
goals include describing a global method for road displacement on an entire
road network, based on these modifications.
Burghardt D. and S. Meier (1997): Cartographic Displacement using the Snakes Concept. In: Foerstner W. and L. Pluemer (eds): Semantic Modeling for the Acquisition of Topografic Information from Images and Maps. BirkhaeuserVerlag, Basel, Switzerland.
Cohen L.D. and I. Cohen (1993): FiniteElement Methods for Active Contour Models and Balloons for 2D and 3D Images. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 15, No. 11, pp. 11311147.
Harrie L.E. (1999): The Constraint Method for Solving Spatial Conflicts in Cartographic Generalization. Cartography and Geographic Information Science, Vol. 26, No. 1, pp. 5569.
Huebner K.H., E.A. Thornton and T.G. Byrom (1995): The Finite Element Method for Engineers. Third Edition. John Wiley & Sons.
Højholt P. (2000): Solving Space Conflicts in Map Generalisation: Using a Finite Element Method. Cartography and Geographic Information Science, Vol. 27, No. 1, pp. 6574.
Kass M., A. Witkin and D. Terzopoulos (1987): Snakes:Active Contour Models. Proceedings of the First International Conference on Computer Vision. IEEE Computer Soc. Press, pp. 259269.
Lamy S., A. Ruas, Y. Demazeu, M. Jackson, W. Mackaness and R. Weibel (1999): The Application of Agents in Automated Map Generalisation. Conference Proceedings ICA, Ottawa, Canada, pp. 12251234.
Neuenschwander W.M. (1995): Elastic Deformable Contour and Surface Models for 2D and 3D Image Segmentation. Dissertation, Swiss Federal Institute of Technology (ETH) Zurich, Switzerland.
Nickerson B.G. (1988): Automated Cartographic Generalization for Linear Features. Cartographica, Vol. 23, No. 3, pp. 1566.
Radeva P., J. Serrat and E. Marti (1995): A Snake for ModelBased Segmentation. Fifth International Conference on Computer Vision, IEEE Computer Society Press, Los Alamitos, California. pp.816821.