Home | Business News | Browse by Publication | C | Cartography and Geographic Information Science

Conflict removal between B-spline curves for isobathymetric line generalization using a snake model.

Article Excerpt
Introduction

A maritime chart is a plane representaion of a part of the submarine relief. It is used by navigators to establish their route, and it must ensure their safety. On a maritime chart, the sea bottom is detailed with soundings (i.e., depth points) and isobathymetric lines (equal depth lines). The soundings and isobathymetric lines that compose the chart are defined in several stages.

The data used for chart construction come from different sounding campaigns and are gathered in a bathymetric database. When building a chart, the data corresponding to the desired area are extracted from the database (redundant and erroneous data are deleted from the database). From this sounding sample, a triangulated irregular network (TIN) is defined yielding a representation of the submarine relief of the area of interest. In order to build all the isobathymetric lines at a given depth h, a horizontal plane z =h is computed, and the intersection points between the triangle segments of the TIN and the plane are detected. Isobathymetric lines are then constructed as polygonal lines connecting the intersection points.

In order to reduce the amount of data, the polygonal lines are compressed with B-spline curves. They are approximated at a given accuracy by minimizing the number of control points. Saux (2003) reported that a B-spline curve representation is better than the usual polygonal line representation for isobathymetric line modeling. A better control of the curve shape is achieved and the intrinsic smooth feature of the lines is preserved, thus avoiding broken are effects. We remind the reader of the main definitions and properties of B-spline curves in an appendix at the end of this paper.

In this paper, we focus on isobathymetric line processing. Other objects such as soundings or coastlines are not taken into account. The isobathymetric lines obtained from the database are too numerous (more than two thousand curves for an A0 size chart at scale 1:50000) for all the information to be reported on a map. Depending on the scale of the chart, some data have to be suppressed or modified in order to obtain a simplified and schematic representation as close as possible to reality while being legible and usable for navigation. This important stage in cartography is called cartographic generalization (Figure 1).

[FIGURE 1 OMITTED]

The line generalization process is performed by applying operators such as compression, selection/suppression, aggregation, classification, smoothing, caricaturing, enlargement, and displacement (Ruas et al. 1993). During this stage, several constraints have to be respected to ensure the legibility and the reliability of the final map. According to Beard (1991), three types of constraints are expressed. They are the graphical, application, and structural constraints. Based on this classification, we identify:

* Graphical constraint of legibility: The final chart should not include either real-line intersections (i.e., transversal intersections, overlaps, tangencies) or visual line intersections (when curve segments are too close with respect to an accuracy criterion related to the working scale);

* Application constraint of safety: The displacement of an isobathymetric line should be made towards deeper areas to preserve the safety of navigation; and

* Geomorphologic structural constraint: The relief must be preserved and the more characteristic elements must be emphasized.

Among the different kinds of intersection, transversal intersections hardly occur as isobathymettic lines are level lines. They can appear during the construction stage when defining the initial polygonal isobathymetric lines or the corresponding B-spline curves. In the latter case, they are due to a bad conditioning of the modeling problem. Most of these intersections are in fact self-intersections. Overlaps and tangencies between the curves occur more frequently in steep slopes. The more common intersections are visual intersections which are encountered when the distance between two lines is less than the legibility distance [[epsilon].sub.vis] related to the thickness of the pen stroke. These conflicts also arise when reducing the scale of a chart. Both real and visual intersections can be characterized in the same way: there are two curve segments for which the legibility constraint is not preserved. Therefore, spatial conflicts have to be detected and removed during the generalization stage. A method for detecting B-spline curve conflicts in chart generalization was previously introduced in Guilbert et al. (2003).

Conflict removal between lines is done by applying such operators as suppression, aggregation, or displacement. The choice of the operator depends on the context and the cartographer's experience as formal rules cannot always be applied. Compression, smoothing, and aggregation operators have been defined in Saux and Daniel (1999) for B-spline curve construction and generalization. Following these works, this paper focuses on conflict removal between two B-spline curves with respect to cartographic constraints. The correction is done by displacing the curves.

In the literature, many displacement methods have been defined for spatial conflict removal. The oldest methods are geometrical methods. Their aim is to compute a displacement for each point of the curves based on the distance between neighboring curves. The first method for line generalization was introduced in Nickerson (1988). However, this method does not take into account the neighboring curves when correcting the conflicts. An answer to this problem is given in Lonergan and Jones (2001) who proposed the use of iteration. The iteration method also corrects conflicts locally, however, the distance to the objects in the vicinity is checked after each object displacement, and the process is repeated until no conflict occurs or the distance between the objects is maximal. Other geometrical methods based on optimization methods have been defined in Harrie (1999) and Sester (2000), where all the conflicts are solved simultaneously. Each constraint is expressed as an equation where the unknowns are the point locations or the point displacements. In many cases, all the constraints cannot be respected, and a compromise between different solutions is computed.

Heuristic methods such as genetic algorithms (Wilson et al. 2003) or combinatorial optimization method (Ware and Jones 1998) are also used but they are not easy to control. The solution is controlled by different parameters and their tuning requires some experience. Still other methods are based on physical models. One can find mechanical methods where a solution is obtained by balancing forces related to the constraints. Forces are expressed with a spring model (Bobrich 9001) or with a cable network (Guilbert et al. 2004). In addition, energy minimization models such as snakes and elastic beams have been introduced in Burghardt and Meier (1997) and Bader (2001) for line generalization, and in Galanda and Weibel (2003) for polygon generalization. They consist of computing an equilibrium state by minimizing the global energy of a system defined from the constraints. These methods are interesting in that the line behavior is related to physical parameters that the user can easily apprehend and because the snake is a continuous model which can perform smooth deformations.

The above-mentioned methods are based on two strategies. The first is a local approach which entails solving each conflict separately (Nickerson 1988; Lonergan and Jones 2001). Ira series of conflicts is corrected, the final result depends on the conflict processing order. The second approach is a global approach...

View this article FREE - Now for a Limited Time, try Goliath Business News
Free for 3 Days!