Keywords: Nautical chart, submarine relief, ontology, cartography, multi-agent system, generalisation

A nautical chart is a kind of map used to describe the seafloor morphology and the shoreline of adjacent lands. One of its main purposes is to guaranty safety of maritime navigation. As a consequence, construction of a nautical chart follows very specific rules. The cartographer has to select and highlight undersea features according to their relevance to navigation. In an automated process, the system must be able to identify and classify these features from the terrain model.

An undersea feature is a subjective individuation of a part of the seafloor. Landform recognition is a difficult task because its definition usually relies on a qualitative and fuzzy description. Achieving automatic recognition of landforms requires a formal definition of the landforms properties and their modelling. In the maritime domain, the International Hydrographic Organisation published a standard terminology of undersea feature names which formalises a set of definitions mainly for naming features and communication purpose. This terminology is here used as a starting point for the automatic classification of the features from a terrain model.

In order to integrate knowledge about the submarine relief and its representation on the chart, this research aims to define ontologies of the submarine relief and nautical chart. Then, the ontologies are applied to generalisation of nautical chart. It includes two main parts. In the first part of the research, an ontology is defined to organise geographical and cartographic knowledge for undersea feature representation and nautical chart generalisation. First, a domain ontology of the submarine relief introduces the different concepts of undersea features with their geometric and topological properties. This ontology is required for the classification of features. Second, a representation ontology is presented, which describes how bathymetric entities are portrayed on the map. Third, a generalisation process ontology defines constraints and operations in nautical chart generalisation. In the second part, a generalisation process based on the ontology is designed relying on a multi-agent system. Four kinds of agents (isobath, sounding, feature and group of features) are defined to manage cartographic objects on the chart. A database model was generated from the ontology. The bathymetric data and the ontology are stored in a triplestore database, and are connected to an interface in Java and C++ to automatically classify the undersea features extracted from the bathymetry, and evaluate the cartographic constraints. At first, geometrical properties describing the feature shape are computed from soundings and isobaths and are used for feature classification. Then, conflicts are evaluated in a MAS and generalisation plans are provided.

LIST OF FIGURES xvii 3.4 The AGENT generalisation model. [START_REF] Ruas | A prototype generalisation system based on the multiagent system paradigm[END_REF] . . . . . . . . . . . . . 3.5 CartACom model. [Duchêne et al., 2012] . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 A relation between two agents. [START_REF] Duchêne | The cartacom model: transforming cartographic features into communicating agents for cartographic generalisation[END_REF] . . . . . . . . . . . . . . . . . 3.7 GAEL model. [Duchêne and Gaffuri, 2008] . . . . . . . . . . . . . . . . . . . . . . . 3.8 The values and methods attached to a constraint and their interdependencies. [START_REF] Galanda | Automated polygon generalization in a multi agent system[END_REF]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.9 Relationship of AGENT, CartACom and GAEL. [START_REF] Gaffuri | Field deformation in an agent-based generalisation model: the gael model[END_REF] . . . . . . . . . . . . 4.6 An example of process occurring in JNI [START_REF] Liang | The Java Native Interface: Programmer's Guide and Specification[END_REF]

Introduction Context

In the information age, maps play a key role in geographic information system (GIS) to master various cartographic data for knowledge representation and spatial analysis. All maps are concerned with two elements of reality: locations are position in two-dimensional space (e.g. coordinates x,y); attributes are qualities or magnitudes (e.g. slope of terrain) [START_REF] Robinson | Elements of Cartography[END_REF]. The relationships of different locations and attributes as topological and metrical relationships need to be considered in the map. Most maps are designed to store geographic information in spatial format.

Other maps serve mobility and navigation needs. The modern mapping has a trend toward greater analytical purpose involving measuring and computing. Still other maps are used to summarise voluminous statistical data and assist in various analysis.

A topographic map is a type of map characterized by large-scale detail of land area [START_REF] Robinson | Elements of Cartography[END_REF]. Maps of much larger scale are required for site location and other engineering purposes.

The maps especially designed to serve the needs of navigators, nautical and aeronautical, are called charts. Depending on the scale of the chart, it may show depths of water and heights of land, undersea features, details of the coastline, navigational hazards, locations of natural and human made aids to navigation, information on tides and currents, local details of the Earth's magnetic field, and human made structures such as harbours, buildings and bridges. Nautical charts are essential tools for marine navigation. They may take the form of charts printed on paper or computerised Electronic Chart Display and Information System (ECDIS). ECDIS, which use computer software and electronic databases to provide navigation information, can augment paper charts and replace it in some cases.

Cartography can be a drama played by two actors, the map maker and map user, with two stage properties, the map and the data domain [START_REF] Robinson | Elements of Cartography[END_REF]. There are four processes in cartography: firstly, collecting and selecting the data for mapping; secondly, manipulating and generalising the data, designing and constructing the map; thirdly, reading or viewing the map; fourthly, responding to or interpreting the information and knowledge. Making a usable map should fulfil its purpose by respecting all of its constraints. Figure 1 illustrates three stages in cartography. The first stage is data collection, in which geographical data will be acquired (through e.g. remote

INTRODUCTION

Figure 1: Map construction process [START_REF] Kimerling | Map use: reading and analysis[END_REF].

sensing techniques) and prepared for the cartographer. In the second stage, the cartographer needs to transform the data that have been collected into a visualisation of features relevant to the purpose of a map [START_REF] Kimerling | Map use: reading and analysis[END_REF]. It includes four steps, selection, classification, generalisation and symbolisation. Selection is choosing the relevant bits of information to include on a map, and thus also determining what should be left out. Classification is to classify all the data with different relationships (e.g. taxonomy). Generalisation is a fundamental process in cartography to reduce redundant data depending on map scale, objective, graph limitation and other factors [START_REF] Mackaness | Generalisation of geographic information: cartographic modelling and applications[END_REF]. Generalisation has been defined by the International Cartographic Association as the selection and simplified representation of detail appropriate to the scale and/or purpose of a map [START_REF] Ica | Standardization of undersea feature names[END_REF]. Map symbolisation is the characters, letters, or similar graphic representations used on a map to indicate an object or its characteristics in the real world. Symbolisation should consider size, shape, colour and other factors of symbols. At last, the map will be published for reading, analysis and interpretation.

Creating maps has evolved from manual to digital construction techniques rapidly. This shift comes with great benefits like the automation of the process, but it also should guarantee some fundamental requirements during digital map construction process, such as maintaining attributes of the data in the map. Therefore, it is necessary to consider why we need to make a map, what kind of map to create and how to produce a good map.

Motivation and Problems Motivation

The main purpose of a nautical chart is to ensure safety and efficiency of navigation [START_REF] Maxim | Nautical Chart User's Manual[END_REF].

It provides a schematic representation of the seafloor emphasising navigation hazards and marking navigation channels, which assists navigators in positioning and planning their route. Indeed, as the seafloor is not visible from the vessel, danger cannot be assessed visually and navigators have to rely on the chart. As a consequence, seafloor representation on nautical charts follows different rules from terrain representation on topographic maps as the cartographer's objective is not to represent the terrain as accurately as possible but to select and emphasise terrain features that are relevant to navigation. The seafloor being modelled by soundings and isobaths, undersea features are represented as sets of isobaths and soundings which are selected by the cartographer.

Generalisation is one of the most important step to improve the accuracy of nautical chart and efficiency of submarine relief analysis. Nautical chart generalisation requires the consideration of undersea features due to its specific purpose. Therefore, automating the chart construction process requires the identification and classification of undersea features, which are relevant to navigators. Such classification would then be used in the generalisation process to select and portray relevant landforms on the chart. Such approach is indeed more relevant to object generalisation and database modelling. Currently, there is no technique in nautical chart generalisation that automatically identifies terrain features as perceived on the chart and generalises them appropriately considering not only spatial information but also their semantic meaning. Some generalisation operators specific to sounding selection [START_REF] Oraas | Automated sounding selection[END_REF] or isobath smoothing [START_REF] Guilbert | Cartographic generalisation of lines based on a b-spline snake model[END_REF] were defined, but generalisation is a complex task which is still performed informally by cartographers relying on their own experience. In order to move towards its automation, the submarine relief and its representation on the nautical chart need to be formalised.

Problems

Map construction is greatly facilitated with GIS technology, which integrated data collection, editing, storage, processing, and display [START_REF] Robinson | Elements of Cartography[END_REF]. But generalisation is a complex process and is hard to automate. In these challenges, two main issues exist. The first issue is how to design the generalisation process with multifarious factors such as rules. The map is a complex mix of metric and topological patterns reflecting spatial information [START_REF] Mackaness | Understanding geographic space. Generalisation of Geographic Information: Cartographic Modelling and Applications[END_REF]. Depending on the purpose of maps, this system needs to understand and convey geographic and cartographic knowledge. In order to reach the objective of generalisation, different phases of generalisation should organised in a framework. The second issue is how to extract large volume of geographic and cartographic information from geographic data. visual issue in the map construction. But it is not enough to deal with geographic data during map construction. Geographic data identifies the geographic location of features, characteristic of features, relationships between features and so on. It provides analysis, navigation and other applications through maps. Hence, it is necessary to mine the data to get more information and knowledge and integrate them accurately in a GIS. These works should be considered in the object generalisation.

Objectives

Nautical chart construction necessaries to consider feature attributes and their spatial, topological and semantic relationships in the whole seafloor. In order to design an automatic generalisation system for nautical chart, a first step is to organise geographic and cartographic knowledge carried by the chart. On the one hand, it should provide an accurate description of undersea features, which does not lead to any ambiguity. On the other hand, the process of generalisation need to be organised. Such an explicit formalisation of concepts, attributes and relationships characterising undersea features can be achieved through an ontology. Ontology allows the integration of information and the building of relationships primarily based on data meaning [START_REF] Fonseca | Ontology-driven geographic information systems[END_REF]. The main objective of this study is to provide an automatic method for undersea feature characterisation and generalisation on the nautical chart. Hence, this research should define an ontology of the submarine relief and nautical chart generalisation process that will be at the root of a generalisation process driven by the significance held by undersea features. In order to reach this main objective, there are three sub-objectives:

• Firstly, this work needs to integrate knowledge of submarine relief and cartography. The IHO has published a list of standardised names for undersea features [International Hydrographic Organization, 2008](Appendix A) with their textual definition. This work uses undersea features of the IHO document [International Hydrographic Organization, 2008] to define the ontology of submarine relief. The ontology of submarine relief with undersea features' geometric, topological and semantic characteristics is defined at two levels. First, a subject ontology of the submarine relief is presented. This ontology introduces the different concepts required for the classification of features based on their spatial and semantic properties. Second, a representation ontology describing how bathymetric entities are portrayed on the chart is presented. Both ontologies will be integrated together into an ontology conceptualising the submarine relief elements and their representation to form the root of a larger ontology of the bathymetry and nautical chart generalisation process.

• Secondly, the knowledge of generalisation constraints and operations should be organised for cartographic generalisation application. Features are identified on the chart by sets of isobaths from which properties are computed. Moreover, soundings will assist to determine and represent the undersea features on the nautical chart during the automatic generalisation process.

In order to maintain geometric and topological characteristics of cartographic objects, it is necessary to define generalisation constraints and operations in the ontology.

• Thirdly, this research needs to automatically evaluate conflicts on a nautical chart and arrange generalisation plans. Hence, a multi-agent system based on the ontologies will be designed to control evaluation in the generalisation process.

Research Design

Firstly, literature review on feature characterisation and generalisation of nautical chart will be carried out. The focus is on the one hand on foundational concepts of nautical chart and relief representation techniques (digital terrain models), and on the other hand on previous works related to map generalisation and landforms representation. The previous researches on generalisation include methods of isobaths and soundings generalisation and chart generalisation strategies. The landforms representation reviews from quantitative and qualitative approaches are reviewed. The literature study helps to identify the advantages and disadvantages of previous researches and the needs for an improved undersea feature representation and generalisation model. In order to bridge the gaps of previous works, a geo-ontology will be used to design feature representation and generalisation model based on the findings of the literature review. Hence, the previous researches on ontology and geo-ontology will be also reviewed. In addition, multi-agent techniques should be reviewed and as it is considered for implementation of feature representation and generalisation model.

Secondly, the conceptual model will be designed based on ontology. In this main phase, the main point is organisation and integration knowledge of undersea features and cartography. The knowledge of undersea features focuses on topological and geometric information of features, such as shape and position of undersea features. The components of chart and generalisation strategies are then integrated in the model. The generalisation strategies contains generalisation constraints that consider safety, legibility, structural/topological and position/shape. Lastly, operations related to different cartographic objects are taken into account.

INTRODUCTION

Thirdly, in order to use knowledge of ontologies and provide solutions for nautical chart generalisation, agent will be used to control the generalisation process. A multi-agent system will be designed to control and perform evaluation of nautical chart for generalisation. Previous defined knowledge of nautical chart and generalisation (e.g. ontology model) will be used as a knowledge basis. Three main aspects need to be designed in this phase. First, the structure of multi-agent system should be designed refer to cartographic objects. Second, the life cycle of multi-agent system should be designed for each agent. Then, the generalisation rules and operations should be considered in the agents. At last, the interaction of different agents should be considered in the multi-agent system.

Finally, an information system and multi-agent system will be implemented based on the ontologies and tested on a set of bathymetric data provided by the French Hydrographic Office for a large scale map (1:12500) of a coastal area. On the one hand, feature identification will be realised in the information system based on the ontology of undersea features and cartography. On the other hand, the evaluation of nautical chart will be implemented in the multi-agent system based on the ontology of cartography and generalisation. In addition, an ontology database should manage ontologies and bathymetric data. A cartographic application platform should be designed to represent undersea features and realise evaluation of conflicts on the chart.

Thesis outline

The thesis is subdivided into 6 chapters. Apart from the chapter of introduction, a review part (chapter 1) is followed by our contribution (chapters 2 to 4). The last chapter presents some conclusions and an outlook for future research. A short preview the contents of the chapters is provided below:

• chapter 1: This chapter focuses on the representation and generalisation of the seafloor. It firstly introduces basic concepts about nautical charts, including the components and purpose of the nautical chart. Next, most common digital terrain models (DTM) are introduced. Then, existing works on rules and techniques used in nautical chart generalisation on terrain and landform representation are reviewed. This chapter is decided to the representation of the submarine relief using ontology.

• chapter 2: It starts with existing works on geographic ontologies, which introduces concepts of ontologies in philosophy, computer science and geographic domain. Then, this chapter discusses the definition of an ontology framework for geographical applications. Also, this chapter discusses existing ontologies that have been defined in geography and in cartography. Based on previous works, this chapter defines the first contribution of this thesis, which is the development of an ontology of the submarine relief in two parts: first is the submarine relief ontology, which aims to describe undersea features with their components and properties; the other part includes the cartographic representation ontology and generalisation process ontol-ogy, in which undersea features are defined as cartographic objects with their relationships, and the generalisation process ontology which defines the constraints, evaluation methods and operations which are parts of the generalisation process.

• chapter 3: This chapter is devoted to design a multi-agent system (MAS) based on the ontologies defined on chapter 2 in order to evaluate conflicts on the chart. The first section of this chapter introduce the concept of agent and the existing models of agent that are applied to geographic domain. This chapter introduces another contribution of this thesis, which is the design of different types of agents that are related to types of cartographic objects in cartographic representation ontology. Each agent has a life cycle to evaluate nautical chart.

Then, according to the generalisation process ontology, the interactions of each agent are designed to get solution of generalisation automatically.

• chapter 4: It is devoted to implementation of the undersea feature representation and the multi-agent system for evaluate conflicts on the chart. In order to implement and validate ontologies, this chapter firstly presents a system to classify and represent undersea features. Then, this system is extended to the evaluation of conflicts on a nautical chart and the creating of generalisation plans. The first section introduces a triplestore database to manage ontology. Meanwhile, a cartographic application platform classifies features and implements MAS. Then, we present a case study in two parts: one is the undersea feature classification and identification, the other is implementation of the MAS for automatic evaluation of conflicts on a nautical chart and preparing generalisation solutions.

• chapter 5: This chapter concludes the thesis by pointing the main contributions and identifying the limitations of the method. Some perspectives on future research challenges with respect to development of ontology and bathymetric generalisation are given.

Chapter 1

Representation and Generalisation of the Submarine Relief

H

ow to represent landforms and provide useful and accurate information on a legible chart? This is a fundamental issue in chart construction. Currently, there are various kinds of maps related to different applications. Constructing a map consists in selecting the data to be portrayed in consideration with the type of representation and the purpose of the map.

A topographic map provides a representation of the relief and of natural and man-made features. Relief can be seen as a continuous phenomenon and modelled by a field function while features such as buildings, roads and rivers are perceived and modelled as objects on the map. Map generalisation requires the application of different types of operators which need to be combined and applied to different objects. In exiting works, digital terrain models (DTM) are widely used to represent terrain surfaces from different types of data, such as vector data and aerial image. In order to meet the applications requirements and represent useful and accurate information, terrain generalisation may be perceived as a mathematical process, where the objective is to obtain an CHAPTER 1. REPRESENTATION AND GENERALISATION OF THE SUBMARINE RELIEF optimal representation of the terrain according to threshold given precision, which also preserves the terrain morphology and the legibility of map. Generalisation is affected by two kinds of factors: one is quantitative factors that are related to the data size and the scale, and the other is qualitative factors related to characteristics of topographic features and their meaning. Hydrographic map is a type of topographic map to represent the underwater world and nautical chart focuses on submarine relief and so are concerned with the portrayal of salient features on the seafloor and their incidence on navigation.

Approaches for representing landforms on a DTM fall into two categories, quantitative and qualitative representations. Quantitative representation means numerical representation that describes landforms with some parameters, such as slope describes terrain surface in the DTM. Qualitative representation uses general terms to describe terrain features. Landscape description is something that people can do easily, although they may have a different understanding influenced by their culture, language or experience, leading to a more complex and richer description: a feature belonging to the peak class can be any kind of elevation from the ground such as a hill, a mountain. This distinction is very relative [START_REF] Stewart | Experiences in developing landform ontologies[END_REF] as it depends on people's knowledge. Different understanding may create confusions when people of different languages or professions communicate together. They also make it difficult to achieve a formal definition that can be used for computer applications. Establishing a universal list of features that persons can recognise is still an open problem. In that case, terrain classification is rather a problem of defining formal specifications that correspond to verbal descriptions for the purpose of communication within a community or for digitised representation [START_REF] Smith | Do mountains exist? towards an ontology of landforms[END_REF].

This chapter discusses previous works related to the representation at different scales of the bathymetry on nautical chart and the extraction of landforms from a terrain model. Research in both areas have mostly been conducted separately, the first one being concerned with the selection of cartographic elements and the latter focusing on the characterisation of landforms from terrain data.

The outline of this chapter is as follows. Section 1.1 introduces basic definitions about the role and components of nautical chart. Section 1.2 reviews most common terrain models. Section 1.3 reviews exiting works on chart generalisation works, including generalisation strategies, cartographic generalisation and model generalisation. Section 1.4 presents existing landform representation methods in DTM and qualitative models. At last, section 1.5 concludes this chapter.

Nautical Charts

A map is a kind of geographic language to describe real world at different scales. There are four main classifications of map [START_REF] Kraak | Cartography: visualization of geospatial data[END_REF]. Physical maps illustrate the physical (natural and man-made) features of an area, such as the mountains, rivers and lakes. Political maps aim to show territorial borders and not to show physical features. Thematic maps are 1.1. NAUTICAL CHARTS designed to show a particular theme connected with a specific geographic area, such as transport maps that show subway lines in a city and population map that shows density of population in an area. Topographic maps are a summary of the landscape and show important physical features with details of elevation and shape in an area, usually using contour lines. A hydrographic map is a kind of topographic map that is used to reveal the slopes and contours of land, specifically made to survey underwater land terrain. Such maps can be used to help in investigations, oceanography studies and naval services. Also, hydrographic map can be intended to produce navigation aids for ships, boats, which is called nautical chart.

Nautical chart is a type of hydrographic map, which is a working document used by the navigators on the sea, as a "road map" for drivers, and is essential for safe navigation. The construction of nautical chart not only needs to consider the general constraints of topographic chart, like legibility and topology constraints, but also must consider navigation safety constraints that refer to function of nautical charts. Hence, the construction of nautical charts is different from other topographic charts, and how to represent the seafloor on nautical charts is an important issue of cartography.

Figure 1.1 shows an example of nautical chart. Soundings and isobaths are used to describe the submarine relief. Colours distinguish between man-made features, dry land, intertidal zone and seabed permanently underwater, and indicate water depth. In figure 1.1, the yellow area is land, the green area is the intertidal zone, the blue and white regions are under the sea. In addition, symbols provide navigation information about the nature and position of features which are useful to navigators, such as undersea features, sea marks and landmarks. Some symbols describe the seafloor with information such as its depth, materials as well as possible hazards such as shipwrecks.

Other symbols show the position and characteristics of buoys, lights, lighthouses, coastal and land features and structures that are useful for fixing a position. For example, the abbreviation "ED" is commonly used to label geographic locations whose existence is doubtful. Because this thesis focuses on the bathymetry and undersea feature representation on the nautical chart, other symbols are not considered in the discussion.

Generally, there are three sorts of features portrayed on a nautical chart: topography, hydrography, and aids and services [START_REF] Maxim | Nautical Chart User's Manual[END_REF]. Topographic features are natural and cultural features, landmarks and ports. Natural features refer to coastlines, terrain relief and so on where coastlines correspond to the intersection between the land and the level of the highest seas [Guilbert and Lin, 2007a]. Cultural features, landmarks and ports refer to man-made features. In general, topographic features refer to charted features located on land and above water. Hydrographic features include natural and artificial features. Natural features are nature of the bottom, rocks and shoals, which are extremely important to describe the submarine relief in the nautical chart. Artificial features refer to wrecks, marine structures, unexploded ordnance, cable, and pipeline areas [START_REF] Maxim | Nautical Chart User's Manual[END_REF].

Aids and services to navigation are the man-made structures or devices external to a craft designed to assist in determining the craft's position or a safe course or to warn of dangers or obstructions [START_REF] Maxim | Nautical Chart User's Manual[END_REF], including lights, beacons, fog signals, radar, radio, satellite navigation systems and RELIEF so on. This work will focus on natural hydrographic features portrayed on the chart.

A sounding is a depth point and an isobath line is a contour line joining points of equal depth. A sounding is a spot at an exact location whose depth is shown by a number on the chart (Figure 1. 1). It provides information about the shape of the ocean bottom between depth curves [START_REF] Zoraster | Automated cartographic sounding selection[END_REF]. Depths on charts published in most parts of the world use metres. It is one of the ways to represent bathymetric information on the nautical chart (Figure 1.1). Hence, in the cartography of nautical chart, selecting a subset of available soundings is very important for representing nautical chart at different levels. There are three basic types of soundings, prime soundings, background soundings, and limiting depth soundings [START_REF] Zoraster | Automated cartographic sounding selection[END_REF]. Prime soundings mark ocean bottom features which would be expected based on linear interpolation between chart depth curves. Background soundings describe the whole regular pattern in the nautical chart. Hence, the total number of background soundings is the largest one in the nautical chart. Limiting depth soundings show the least depth encountered when following the deepest part of a natural channel or river [START_REF] Zoraster | Automated cartographic sounding selection[END_REF]. There are three major criteria of sounding selection [START_REF] Oraas | Automated sounding selection[END_REF]: a) the shallowest sounding must be chosen; b) the density of soundings must be such as to draw attention to dangerous areas; c) the sounding pattern must be "pretty", which means that the sounding pattern must have a relatively even spacing.

As on a topographic map, landforms and characteristic terrain features are characterised by the sets of contours based on their shape and spatial layouts [START_REF] Robinson | Elements of Cartography[END_REF]. Usually, there are several models that are denoted as digital terrain models (DTM) to represent terrain surfaces, such as those based on contour lines. The contour interval is the vertical distance between the parallel horizontal surfaces. Hence, if the contour interval increases, more details of terrain surfaces will be lost. Through a set of contours, users can identify morphometric features such as valleys and ridges. Similarly, groups of isobaths provide a general representation of the structure of the seafloor. However, isobaths on nautical charts are not set at regular vertical intervals, the interval being shorter in shallow areas while the density of soundings on the chart depends on the roughness of the terrain. This is important to represent undersea features for navigation. Isobaths play a slightly different role than elevation lines on topographic maps. They are used to "illustrate shallow areas, shoals and banks, irregular bottoms, navigable channels and passages, and deeps" [START_REF] Maxim | Nautical Chart User's Manual[END_REF]. Therefore, the generalisation of isobaths is one of the most important operations in the construction of a nautical chart as it directly impacts on the safety of the navigation.

Digital Terrain Models (DTM)

Digital terrain model (DTM) is a key technique to create relief representation [START_REF] Kraak | Cartography: visualization of geospatial data[END_REF]. Digital terrain models (DTM) are topographic models of the earth terrain relief, commonly used in GIS to represent surfaces. [START_REF] Li | Digital terrain modeling: principles and methodology[END_REF] gave a definition: "The digital terrain model (DTM) is simply a statistical representation of the continuous surface of the ground by a large number of selected points with known X, Y, Z coordinates in an arbitrary coordinate field." The data files contain the spatial elevation data of the terrain in a digital format. The most commonly used models are regular square grids (RSG) (Figure 1.2a), triangulated irregular networks (TIN) (Figure 1.2b) and contour lines (Figure 1.2c).

CHAPTER 1. REPRESENTATION AND GENERALISATION OF THE SUBMARINE RELIEF

RSG is a common form of raster-based modelling, which is simply a grid of height values in which each cell contains a single value representative of the height of the terrain that is covered by the cell.

It is easy to calculate surface's slope and aspect in DTM, and extract terrain surface. Nevertheless, too large set of data is simply managed in RSG, such as the elevation of a cell is an approximation of elevation data.

TIN is a vector-based representation of the terrain surface or submarine relief, made up of irregularly distributed nodes and lines with three-dimensional coordinates (x, y and z) that are arranged in a network of non-overlapping triangles. An advantage of using TIN in mapping and analysis is that the points of TIN are variably distributed. Therefore, data input is flexible and fewer points need to be stored than in a raster-based model. Also, the point distribution can be adapted to the smoothness of the surface, for example more points in rough surface and less points in flat area. TIN adapts to various terrain structures and data density. However, TIN needs more time to divide irregular point set. As well as, some point sets have many possible different triangulations.

The Delaunay triangulation is mostly used in GIS that maintenances the circumscribed circle of a triangle, but it is more expensive in computation and the data structure is more difficult to handle.

Contour line connects a series of points of equal elevation and is used to illustrate relief on a map. DTM can be generated by a set of contour vector data. Contour lines can be digitised from existing topographic maps and generated automatically from photogrammetric stereo models, such as extracting contour lines from RSG or TIN model. The topological relationship can be represented through contour lines. There is no elevation data between the contour lines. Elevations can be interpolated from the contours but depending on the vertical interval and the type of terrain, it can lead to imprecise and sometimes inaccurate interpolations and all terrain variations which are smaller than the vertical interval are ignored.

The multi-scale representations of DTM is an essential task that relates to scale and resolution.

The scale is the ratio between distances on the map and in the real world. In the DTM, data are produced at various scales for different applications. The resolution is the size of the basic unit for measurement or representation. Because the resolution means the level of detail and scale means the level of abstraction, the resolution is a good indicator of scale for DTM data in normal case [START_REF] Li | Digital terrain modeling: principles and methodology[END_REF]. In the RSG modelling, it is easy to use quadtree for multi-scale representation (Figure 1.3). But it is more difficult to manage TIN data in multi-scale representations. Usually, the operations of TIN for multi-scale representation are triangle removal, vertex removal, edge collapse and triangle collapse. The common method for representing contour lines at multiple scales is by removing and filtering the contours.

Generalisation

In cartography, the process of deriving small-scale maps from large-scale maps through different operations is called generalisation. Also, DTM generalisation is only to maintain and update DTM [START_REF] Li | Digital terrain modeling: principles and methodology[END_REF].

data at the largest scale and to derive DTM data at any smaller scale [START_REF] Li | Digital terrain modeling: principles and methodology[END_REF]. Over the last decade, generalisation methods transited from manual to automatic or semi-automatic digital techniques. In order to support different purpose of map users, automatic generalisation should consider how to formalise and apply cartographic knowledge [START_REF] Sarjakoski | Conceptual models of generalisation and multiple representation[END_REF]. There are three aspects which should be considered in the generalisation process: when, what and how. "When" is relevant to conflicts on the map, which is supported by various generalisation rules and practices. Then, we need to know what should be done in the generalisation, includes generalisation operations, such as simplification and smoothing. At last, it needs a framework/model to control the whole generalisation process. In the following sections, the three parts will be introduced in detail.

Automating the generalisation process consists in developing some techniques to perform specific operations, and in developing some approaches modelling the whole process. Nautical chart is not only about describing submarine relief accurately, but also about providing meaningful information related to navigation. Therefore, automating the chart construction process requires the identification and classification of undersea features into categories relevant to navigators. Mostly, there are three kinds of generalisation, object generalisation, cartographic generalisation and model generalisation (Figure 1.4). Object generalisation encodes a cartographic data set through the application of spatial and attribute transformations, in order to build a primary model of the real world. It takes place at the time of defining and building the original database [START_REF] Weibel | Generalising spatial data and dealing with multiple representations[END_REF]. The main objective of model generalisation is to control data reduction for various purposes [START_REF] Weibel | Generalising spatial data and dealing with multiple representations[END_REF]. The objective of cartographic generalisation is to fit portrayal of selected features to the map scale and to the requirements of effective communication [Robinson , 1995]. Cartographic generalisation describes the generalisation of spatial data for cartographic visualisation.The difference between cartographic generalisation and model generalisation is that cartographic generalisation is aimed at generating visualisations, and brings about graphical symbolisation of data objects [START_REF] Weibel | Generalising spatial data and dealing with multiple representations[END_REF].

Generalisation Process

Modelling the generalisation process

Manual generalisation is a holistic process, which includes selection and simplified representation of detail appropriate to the different scales and/or purposes of a map [START_REF] Sarjakoski | Conceptual models of generalisation and multiple representation[END_REF]. Cartographers draw a reduced map by hand. They eliminate unimportant features, simplify lines and boundaries, combine area features, and resolve conflicts as they draw. This process is extremely subjective and time consuming. With the development of computer science, the last decades saw the development of digital cartography including digital generalisation and its automation. Automated generalisation process goes through several steps and one needs to determine when to apply generalisation operations and how to control and integrate them. Therefore, in addition to defining generalisation operations, it is necessary to design a model expressing the different cartographic rules and practices for decision making. The three existing strategies for modelling the overall generalisation process are condition-action modelling, human interaction modelling, and constraint based modelling [START_REF] Harrie | Modelling the overall process of generalisation[END_REF].

• In condition-action modelling, the validity of a map is defined by a set of conditions applied to cartographic objects. If a condition is not observed by an object or set of objects, an action is triggered. Such a model requires the explicit definition of rules formed by conditions and actions usually in a if-then-else form. It leads to the creation of an expert system which first extract relationships between objects and applies the rules to trigger the actions. Expert systems were the first systems to provide automation however it could only solve limited problems. Generalisation practices are usually too subjective to be formalised in rules and, due to the large number of objects and relationships, problems were often too complex to solve, with cascading or contradictory operations to handle.

• Human interaction modelling was developed with consideration of the limitations of conditionaction modelling. As some problems are too complicated to be handled by the system alone, the principle is that the cognitive workload can be shared between the system and the operator.

The system is able to extract knowledge and to propose and perform operations. The operator controls the process and validates the propositions. However this model remained a concept with no development outside the academic world.

• Moving away from the rigidity of rules, constraint based modelling aims at providing a more flexible approach where the system focuses on the final goal rather than how to reach it. Constraints are used to express the map requirements and the objective of the map. Here the operator acknowledges that all constraints cannot be fully satisfied and looks for a best solution minimising constraint violations. Constraints can be prioritised and evaluated with a score instead of a simple Boolean value as with rules.

Constraint based methods developed from the late 90's and brought big improvement in generalisation automation as they allowed dealing with larger and more complicated sets of data. Three approaches have been considered in constraint modelling [START_REF] Harrie | Modelling the overall process of generalisation[END_REF]]:

• Combinatorial optimisation modelling techniques in cartographic label placement stems from the fact that it is natural to determine a fixed number of trial positions for each label [START_REF] Harrie | Modelling the overall process of generalisation[END_REF]. In generalisation, according to some constraints, the best map will be searched from several possible maps. Such techniques are based on heuristic methods from artificial intelligence such as genetic algorithm or simulated annealing. They look for a best solution among a set of solutions obtained by combination. It means that the set of solutions can be very large but must be finite. Hence it can only be used to model discrete operations such as selection but not continuous deformations.

• Continuous optimisation modelling aims at finding the minimum or maximum value of an objective function defined on a continuous space [START_REF] Harrie | Modelling the overall process of generalisation[END_REF]. But it cannot handle some generalisation operators as well, such as aggregation and selection. Methods are based on optimisation methods such as least square adjustment [START_REF] Sester | Generalization based on least squares adjustment[END_REF], elastic beams [START_REF] Bader | Energy Minimization Methods for Feature Displacement in Map Generalization[END_REF] and snakes [START_REF] Burghardt | Cartographic displacement using the snakes concept[END_REF]. Each constraint is associated to an objective function and evaluated on each object. A best solution is then found by minimising the objective functions. The interest of the approach is that constraints can be put together CHAPTER 1. REPRESENTATION AND GENERALISATION OF THE SUBMARINE RELIEF as long as they can be expressed by a function [START_REF] Harrie | Simultaneous graphic generalization of vector data sets[END_REF]. Limitations are that solving a system of equations often involves issues related to numerical errors and ill conditioning and the method cannot perform discrete operations.

• Agent modelling techniques come from the field of artificial intelligence. An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through effectors [START_REF] Russell | Artificial intelligence: a modern approach[END_REF]. Meanwhile, a multi-agent system is composed of several interacting agents where objects can be handled individually or as a group. In a generalisation process, an agent can evaluate any type of constraint and apply heuristic and optimisation methods. Moreover, any types of generalisation algorithms can be integrated.

Comparing the three approaches, agent based is the most powerful as it indeed provides a framework that can integrate the other two approaches and so handle all types of operations and the interaction between different types of objects. It also comes with mechanisms to test and select the best operation or to roll back in case a solution is not valid. The principal limitation in implementing an agent system may lay in the overhead computation due to agents constantly listening and evaluating their environment waiting to trigger an operation. Another issue, common to all constraint-based method, is the definition of constraints that accurately express the requirements of the chart.

Generalisation Constraints

In order to produce a generalised map, rules and practices shall be translated into a set of measurable constraints. There are two principles governing map generalisation. One is the map must be adapted to represent the real world, the other is the map should be readable by users. To model the generalisation process, six categories of constraints have been introduced [START_REF] Harrie | Modelling the overall process of generalisation[END_REF] (Table 1.1) that consider either single objects, groups of objects or both. Position constraints consider absolute and relative position during generalisation. Absolute position constraints require individual objects which can not move in relation to the geodetic reference system, and relative position constraints consider the distance between objects. Topology constraints manage the topological relationships of objects in the generalisation process. Shape constraints preserve the characteristics of single objects in the generalisation process. Structure constraints protect the patterns of objects. Functional constraints relate to special purpose of map. Legibility constrains maintain visual representation of cartographic objects on the map. According to [START_REF] Beard | Constraints on rule formation. Map generalization: making rules for knowledge representation[END_REF]'s classification and definition of generalisation constraints [START_REF] Ruas | Strategies for automated generalization[END_REF], four types of isobath generalisation constraints on the nautical chart are classified by [Guilbert and Lin, 2007a;[START_REF] Guilbert | Generalisation of submarine features on nautical charts[END_REF]]:

• The functional constraint is specific to the type of map. For nautical charts, it relates to enlighting navigation routes and guaranteeing navigation safety. In order to ensure the safety of navigation, the depth portrayed on a chart must never be deeper than the real depth [ Guilbert and Lin, 2007a]. For instance, a pit can be removed, but a peak must be maintained on the seabed (Figure 1.5). Hence, on a nautical chart, an isobath line cannot be deleted if it represents the upper section of seabed, as shown in the right of figure 1.5;

• Graphical legibility constraint: objects on the chart must be clearly legible and a minimal distance must be observed between them. The final chart should not include either real line intersection (which would violate the topology constraint) or visual line intersection that is the distance between two objects must be below a given tolerance. In map generalisation, the tolerance is usually set as the thickness of pencil.

• The structural and topological constraints relate to the preservation of spatial relationships between contours. Distribution and mean distance between contours must be respected.

• Position and shape constraints seek to preserve the absolute and relative position and shape of objects in the generalisation process. Absolute position and shape of contours must be preserved, and relative distances between isobaths and soundings must be maintained.

All constraints do not have the same importance. Functional and legibility constraints must be respected to obtain a valid nautical chart. Structural/topological and position/shape constraints CHAPTER 1. REPRESENTATION AND GENERALISATION OF THE SUBMARINE RELIEF are "weak constraints" and can be used to evaluate how well the information is preserved and assess the quality of the chart.

1.3.2 Generalisation of the Bathymetry

1.3.2.

Isobath Generalisation

The isobath is one kind of contour line. Hence, isobath generalisation is similar to traditional cartographic contour line generalisation. The objective of line generalisation is to reduce the amount of data and/or to approximate the overall shape of the line [START_REF] Guilbert | Cartographic generalisation of lines based on a b-spline snake model[END_REF]. The generalisation process includes different generalisation operations in order to satisfy cartographic rules. Operators on lines have been classified in different categories. [START_REF] Shea | Cartographic generalization in a digital environment: When and how to generalize[END_REF] listed 12 operations for generalisation. In addition, [START_REF] Regnauld | A synoptic view of generalisation operators[END_REF] add 5 operations of line feature generalisation, and [START_REF] Li | Algorithmic foundation of multi-scale spatial representation[END_REF] explains operations of individual line features and a set of line features respectively. Based on existing works, 8 line generalisation operations are summarised in table 1.2:

• Simplification selects the characteristic, or retains points for shape description, or rejects redundant points considered to be unnecessary to display the line's character [START_REF] Shea | Cartographic generalization in a digital environment: When and how to generalize[END_REF]];

• Smoothing removes small line details that are not relevant at the scale of representation and makes line appear smoother;

• Typification keeps the typical pattern of line bends while removing some either too small or too numerous segments;

• Exaggeration amplifies a specific part of an object to maintain clarity during the scale reduction;

• Merge combines two or more close lines together in order to preserve the character of individual linear features [START_REF] Regnauld | A synoptic view of generalisation operators[END_REF];

• Displacement moves one line away from the other or both lines away from each other [START_REF] Li | Algorithmic foundation of multi-scale spatial representation[END_REF];

• Selective omission selects the more important lines to be retained [START_REF] Li | Algorithmic foundation of multi-scale spatial representation[END_REF];

• Enhancement can be used to show the true character of the line feature being represented and is often used by the cartographer to highlight specific details about his or her specific knowledge, that would otherwise be left out.

Simplification, smoothing, typification and exaggeration apply to individual line objects, while merge, displacement, enhancement apply to groups of line objects. In addition, selective omission can be applied to individual or groups of line objects. Due to functional constraints, all these operators do not apply to isobaths or need to be adapted. For example, deformation must be done towards greater depths. Earlier works in this direction relate mostly to simplification techniques. Constraint based operators relying on a snake model have also been developed for displacement [START_REF] Guilbert | Conflict removal between B-spline curves for isobathymetric line generalization using a snake model[END_REF] and smoothing [START_REF] Guilbert | Isobathymetric line simplification with conflict removal based on a B-spline snake model[END_REF].

The snake (or active contour) model is an optimization model based on the principle that a physical system is at its equilibrium position when its total energy is minimum. The model was introduced by [START_REF] Kass | Snakes: active contour models[END_REF] in image processing for delineating object boundaries. In line generalisation [START_REF] Burghardt | Cartographic displacement using the snakes concept[END_REF], a line is seen as a system with an internal energy part which represents the intrinsic features of the line and an external energy which represents external constraints applied to the line. The external energy definition depends on the application. The internal energy controls the shape of the line and is defined by its derivatives. [START_REF] Guilbert | Cartographic generalisation of lines based on a b-spline snake model[END_REF] introduced an algorithm of isobath line generalisation, which is based on a B-spline snake model with a global approach. It combines some operators (smoothing, displacement and aggregation) and the safety constraint is considered. All the application constraints of nautical chart have been considered in this algorithm. Based on the B-spline snake model, the smoothing operator pushes the line in one direction, and deals with spatial conflicts (distance between lines, smoothness and legibility) through internal and external energies. The equation (1.1) defines the snake model. E int is the internal energy and E ext is the external energy. The internal energy controls the shape of snake and is defined by equation (1.2). In order to consider position constraints, a boundary line defining an admissible area is built. The external energy (equation (1.3)) is defined to constrain the curve towards the admissible area. f (t) is a parametric curve defined on the interval [a, b], L is the boundary line and P is a point of the line f (t). This operator can perform automatic generalisation of individual lines however processing a set of lines requires topological information to automatically define adjacencies between isobaths and the direction for deformation. [START_REF] Guilbert | Cartographic generalisation of lines based on a b-spline snake model[END_REF] apply the method semi-automatically as they have to provide indication about the topology and choose the operator according to the direction of greater depth.

E snake = b a [E int (f (t)) + E ext (f (t))] dt (1.1) E int = 1 2 α (t) f ′ (t) 2 + β (t) |k (t)| 2 (1.2) E ext (P ) =    d(P,L) 2 ε 2 dist if P is on the wrong side 0 otherwise (1.3) 1.3. GENERALISATION 1.3.2.

Sounding Selection

Sounding selection is the process of selecting a small number of soundings from a much larger group in order to adequately represent the bathymetry [START_REF] Oraas | Automated sounding selection[END_REF]. As mentioned in section 1.1, there are three kinds of sounding: prime sounding, background sounding and limiting depth sounding. Prime soundings are the most significant soundings for navigation. Usually, prime soundings are selected with a shoal. Considering the large number of soundings especially since the use of multibeam soundings, most existing works paid more attention on the selection of prime soundings and limited depth soundings than what and why. Much works are only concerned with sounding selection alone although isobathic lines play an important role in guiding manual and automatic sounding selection [START_REF] Zoraster | Automated cartographic sounding selection[END_REF].

In order to imitate the manual procedure of sounding selection, Oraas designed an automatic method [START_REF] Oraas | Automated sounding selection[END_REF] which is still widely used. First all soundings are sorted by depth starting from the shallowest. The first sounding in the list is selected. All soundings in the list within a given radius are eliminated. Then the algorithm moves to the next sounding of the list, which is the shallowest of all remaining soundings and repeats the process until no sounding is left in the list. During this process, most critical soundings should be selected. Moreover, this algorithm has another advantage, which is that soundings can be preselected and placed in the selected sounding list with some appropriate radius of influence. However, the isobaths are not considered in this algorithm. Figure 1.6 also shows sounding selection method that uses radius to decide the influence area.

In Zoraster's algorithm, the ocean bottom model is initialized from depth curves at the beginning.

During the iterations of the sounding selection process, the certain soundings will be selected from current ocean bottom model. Iterations will stop when all soundings have been chosen for chart display or have been eliminated from consideration because they were near selected soundings. This algorithm has been toward to background soundings selection. Comparing to the manual generalisation, this algorithm improves the accuracy and efficiency of sounding selection. However, the efficiency of the method is hindered by the size of the data and the large amount of calculation.

In Sui's algorithm, three major kinds of problems have been solved [START_REF] Sui | A system for fast cartographic sounding selection[END_REF]. Firstly, critical soundings can be selected accurately, such as shallowest soundings. Secondly, the depth curves can be created from the soundings. Third, the relationship between the depth curves and soundings should be adjusted. In addition, Wang introduced an automatic sounding selection method based on artificial neural network techniques [START_REF] Wang | The cartographic generalization of soundings on chart by artificial neural network techniques[END_REF]. It focuses on deals with spatial and attributive factors at the same time in the soundings selection.

Most methods defined above apply either to isobaths or soundings separately and focus on data selection or simplification to produce a legible map with respect to the safety constraint. However, these two constraints are applied locally: algorithms check if no conflict occurs in the vicinity of a line or a point. They are mostly concerned with adapting a representation to a smaller CHAPTER 1. REPRESENTATION AND GENERALISATION OF THE SUBMARINE RELIEF scale but do not look at the morphology of the seafloor and the information conveyed by the bathymetry for navigation. Algorithms could be integrated in a larger generalisation process but operations selecting and emphasising undersea features according to their relevance need to be defined and articulated with existing methods in a global strategy if one wants to move towards a more automated approach.

Chart Generalisation

Agent modelling is beneficial to integrate most of generalisation operators and constraints in the nautical chart generalisation (chapter 2). [START_REF] Tsoulos | An expert system approach for the design and composition of nautical charts[END_REF] designed a knowledge based architecture for nautical chart, which including two main representational paradigms: objects (point, line, area and text entities) and rules (selection, design, composition and procedural rules). This generalisation is performed as a sequence of operations and follows condition-action modelling requiring an exhaustive description of all possible situations. The generalisation rules controlled the behaviour of the strategy to detect cartographic problems, but it lacks of a strategy to manage generalisation operations to resolve conflicts in the resolutions. [START_REF] Zhang | A multi-agent system approach for feature-driven generalization of isobathymetric line[END_REF] introduced a generalisation strategy based multi-agent system, which aims to represent feature in the agent model. However, feature agents at macro-level and line agents at micro-level are not enough to control all the compositions of nautical chart in the generalisation process. [START_REF] João | Causes and consequences of map generalization[END_REF].

Model Generalisation

Model generalisation controls data reduction for various purposes. Figure 1.7 illustrates the relationship of model generalisation and cartography generalisation for terrain generalisation. In generalisation, the first problem is referred to as model generalisation and yields a digital landscape model (DLM) and the second is referred to as cartographic generalisation and produces the digital cartographic model (DCM) [START_REF] Guilbert | Terrain generalisation[END_REF]. In order to save storage and increase computational efficiency, model generalisation integrates datasets at lower semantic and geometric resolutions from higher one to different resolutions. In the model generalisation, a target map is not generalised from an original map, but derived from a generalised geospatial model [START_REF] Başaraner | Model generalization in gis[END_REF]. [START_REF] Meng | Atkis: Modell-und kartographische generalisierung[END_REF] distinguishes model generalisation and cartographic generalisation clearly. Because relative objective data reduction and relative objective map organisation are separated, the problems can be solved separately and without double expenditure rises. As well as, it is beneficial to the model-based data analysis and map-based space planning.

In the model generalisation process, operations can be implemented as methods excluding representation-oriented operations, such as displacement and smoothing [START_REF] Başaraner | Model generalization in gis[END_REF]. The following introduces some common model generalisation operations:

• Selection aims to remove or keep objects based on the requirements of application and constraints [START_REF] Liu | Frameworks for generalization constraints and operations based on object-oriented data structure in database generalization[END_REF].

• Classification groups together objects into different categories of features with similar attributes. The classification process is often necessary because of the impracticability of symbolizing and mapping each individual value [START_REF] Shea | Cartographic generalization in a digital environment: When and how to generalize[END_REF]].

• Aggregation is a process of semantic abstraction of objects connected to each other from geometric or semantic aspects [START_REF] Meng | Atkis: Modell-und kartographische generalisierung[END_REF]. In addition, it is necessary to consider spatial relationships of objects, because only neighbouring objects can be aggregated. Hence, there are some relationships in the aggregation hierarchy to connect objects, such as the part-of relationship.

• Simplification is a process to reduce the number of attributes of an object type [START_REF] Başaraner | Model generalization in gis[END_REF].

• Association describes the member-of relationship of objects [START_REF] Egenhofer | Object-oriented modeling for gis[END_REF]. The relationship between objects and associations should be represented by networks instead of trees [START_REF] Molenaar | An introduction to the theory of spatial object modelling for GIS[END_REF]. Therefore, the is-a relationship can be used to describe the association of objects.

1.4 Landform Representation

Landform Representation on DTM

Landform is natural physical feature of the earth's surface that is part of the terrain (or relief), such as valleys and mountains. Landform elements also include seascape and oceanic waterbody interface features such as bays, seas and so forth, including sub-aqueous terrain features such as mid-ocean ridges and the great ocean basins. In the DTM representation, there are some factors to describe terrain surface, slope, relief and wavelength. Relief is used to describe the vertical dimension or amplitude of the topography. Wavelength is used to describe the horizontal variations. Then, slope is used to connect relief and wavelength. The relationship between them can be illustrated in Figure 1.8. It can clearly be seen that the slope angle at a point on the wave varies from position to position [START_REF] Li | Digital terrain modeling: principles and methodology[END_REF]. Characterisation of landforms have long been studied in GIS. They are usually described by geometric attributes such as the elevation, the slope steepness or the curvature. Different approaches are considered in the following.

The first approach, mostly used for processing raster images, consists in classifying the points by using filtering methods. In [START_REF] Wood | The geomorphological characterisation of digital elevation models[END_REF], points are classified in six categories (peak, pit, channel, ridge, pass and plane) based on the sign of their derivatives (Figure 1.9). Landform description Figure 1.9: Six classes of morphometric features [START_REF] Wood | The geomorphological characterisation of digital elevation models[END_REF].

depending on the scale or level of detail of the representation, Wood defines different sizes of filter to classify terrain features. In [START_REF] Fisher | Where is Helvellyn? Fuzziness of multi-scale landscape morphometry[END_REF], the authors propose a multi-level description of the landscape taking into account the fuzziness of the features. In [START_REF] Chaudhry | Creating mountains out of mole hills: Automatic identification of hills and ranges using morphometric analysis[END_REF], the authors present another approach where prominences are defined by their summit point and their spatial extent corresponds to a contour. Depending on the size of their extent, they can be viewed at different levels of detail and parent-child relationships based on inclusion between hills can be established.

The second approach, which is closely related to segmentation techniques used on meshes in computer graphics and CAD, consists in partitioning a surface in homogeneous regions based on a specific attribute. Regions are separated by feature lines intersecting at feature points [START_REF] Bajaj | Visualization of scalar topology for structural enhancement[END_REF]. Feature areas can be defined first by grouping adjacent patches sharing a same characteristic (curvature sign [START_REF] Mangan | Partitioning 3D surface meshes using watershed segmentation[END_REF], slope, aspect [START_REF] Saux | A new approach for a topographic featurebased characterization of digital elevation data[END_REF]). However, although commonly used in CAD, these methods are too sensitive to terrain roughness and may give an over segmented terrain.

Landform identification can also be done by identifying first the feature points. In that case, feature points are defined by local elevation extrema (peaks, pits, saddles) and are connected by feature lines (ridges and channels). The set of critical points and lines forms the critical net [START_REF] Danovaro | Morphologydriven simplification and multiresolution modeling of terrains[END_REF] and yields a topological structure that can be stored in a surface network, a Reeb graph [START_REF] Takahashi | Algorithms for extracting surface topology from digital elevation models[END_REF] or an extended Reeb graph [START_REF] Biasotti | Surface shape understanding based on the extended reeb graphs[END_REF]. Equivalent topological structures can also be built from a set of contours. The most commonly used structure is the contour tree [START_REF] Kweon | Extracting topographic terrain features from elevation maps[END_REF] from which pits and peaks formed by tree leaves can be identified.

Based on containment relations, a single contour tree is built for the whole map and extract peaks and pits from the contour tree by considering the number of children of a node (Figure 1.10). But one of the difficulties for feature characterisation is that all contours are considered closed, thus it is limit to define which side is the interior or the exterior of a contour [START_REF] Guilbert | Multi-level representation of terrain features on a contour map[END_REF]. Moreover, contour tree can not handle multiple representation with the hierarchy of features. Features can be defined at different levels of representation in a hierarchy [START_REF] Guilbert | Multi-level representation of terrain features on a contour map[END_REF]. This method classifies all the features into eminences (peaks and ridges), depressions (pits and channels) and mixed features at different levels of detail based on their spatial relationships (Figure 1.11). This method can be applied to terrain analysis and generalisation of a contour map by selecting the most relevant features according to the purpose of the map.

In addition, there are some existing quantitative descriptors to identifying specific landforms. [START_REF] Straumann | Delineation of valleys and valley floors[END_REF] developed a object-based and top-down method to define valley floor and to eventually compute valleyness or the degree of being in a valley from a DEM [START_REF] Straumann | Computation and elicitation of valleyness[END_REF]. [START_REF] Feng | Ontology-based qualitative feature analysis: Bays as a case study[END_REF] designed a bottom-up approach to extract qualitative spatial relations from geographic representations (raster or vector) and a top-down approach to determine which qualitative relations can possibly hold between the parts of the geographic features.

Overall, the main objective of these methods is to provide a formal decomposition or description for computational purpose based on quantitative descriptors. Such classification can be used as a base but is still too limited for analysing a landscape in terms understandable to the common user.

Landforms Representation on Qualitative Models

Each geographic object (e.g. mountain, channel) exists in the real world, but it is difficult to describe its position and shape [START_REF] Smith | Do mountains exist? towards an ontology of landforms[END_REF]. In order to represent terrain surface in the map, terrain features in the human mind should be defined, classified and translated from real world to computer language. In the qualitative representation, which are expressed in general terms, most of methods have no relationships with DTM, such as undersea feature description in the IHO document [International Hydrographic Organization, 2009]. The IHO description of seamount is as follow : "Seamount(s) is a discrete (or group of ) large isolated elevation(s), greater than 1,000m in relief above the sea floor, characteristically of conical form.". Based on models that are closed to human perception, qualitative representation are the result of cognition and naive geography [START_REF] Egenhofer | Naive geography. Spatial Information Theory A Theoretical Basis for GIS[END_REF]. [START_REF] Li | Digital terrain modeling: principles and methodology[END_REF] has introduced four types of qualitative representation:

• The representation based on terrain surface cover: Vegetation, water, desert, dry soil, snow, artificial or man-made features (e.g., roads, buildings, airports, etc.), and so on.

• The representation based on genesis of landforms: There are two main groups of landforms [START_REF] Demek | Manual of detailed geomorphological mapping[END_REF]. One is endogenetic forms that are formed by internal forces, including neotectonic forms, volcanic forms, and those forms resulting from deposition of hot springs. The other is exogenetic forms that are formed by external forces, including denudation forms, fluvial forms, karst forms, glacial forms, marine forms, and so on.

• The representation based on physiography: Generalised regions according to the structure and characteristics of their landforms, each of which is kept as homogenous as possible and has dominant characteristics, for example, seamount, plateau, channel, bank, basin, etc.

• The representation based on other classifications.

Those representations can provide the user with some very general information about a particular landforms. [START_REF] Kulik | Linearized Terrain: Languages for Silhouette Representations[END_REF] developed a qualitative description to identify two dimensional terrain features using the silhouette of a terrain. The horizon of a terrain silhouette is represented as a string. Orientated straight line segments have eight different qualitative slope values (Figure 1.12) that correspond to the qualitative vectors to distinguish terrain features slopes. Each vector has a superscript (the magnitude order) that correspond to the magnitude of the [START_REF] Chevriaux | A landform-based approach for the representation of terrain silhouettes[END_REF] developed a qualitative approach for the modelling of terrain silhouettes that considers the particular point of view of an observer located on the ground, and perceiving constituent landforms and silhouettes at the horizon. This model is flexible enough to describe landforms in the horizon at different levels of abstraction.

In general, these models are help to extract terrain features (e.g., ridge, valley) visually and use them to describe spatial properties concisely. The qualitative approach for feature description deals with the problem of the representation of natural or semi-natural environment by qualitative models extracted from the human mental representation of these landscapes. Indeed, people usually associate features to usual terrain geometrical properties such as summits or saddle points which are visually perceived and not to their boundaries not always well-defined. Uncertainty of geographical object boundaries is a modelling issue that has been discussed in related works by [START_REF] Frank | The prevalence of objects with sharp boundaries in gis[END_REF], [START_REF] Meathrel | A general theory of boundary-based qualitative representation of two-dimensional shape[END_REF], [START_REF] Smith | Do mountains exist? towards an ontology of landforms[END_REF]. A feature is overall considered as a subjective individuation of a rough part of the Earth's surface. It follows that the objective of qualitative methods is not to explicitly locate the beginning and ending of a feature, but to find out the presence of features corresponding to an end-user typology. Referring to the terrain silhouettes modelling approach of [START_REF] Chevriaux | A landform-based approach for the representation of terrain silhouettes[END_REF], their representation can only be used for general planning but not for project design. To design a particular project, more precise quantitative representation are essential [START_REF] Li | Digital terrain modeling: principles and methodology[END_REF].

Conclusion

The nautical chart is one kind of topographic map to describe submarine relief and provide information for navigators. Isobath and sounding are two important elements of nautical chart that help navigators to identify undersea features of seafloor. DTM is widely used to represent terrain surface in the GIS, including RSG, TIN and contour lines. Qualitative representation provides general term definition of terrain surface, but it is not enough to represent terrain surface precisely in the GIS. Qualitative representation helps to extract description of terrain features from general terms. Quantitative representation describes terrain surface through numerical methods. Depending on accuracy parameters, quantitative representation can calculate the property of terrain surface in DTM. In order to accurately represent undersea features from the terms of the IHO document, this work combines qualitative and quantitative representations to describe submarine relief and produce the framework of generalisation process.

Geographical space not only considers consist of geographical entities, but also incorporates the activities occurring in them [START_REF] Kavouras | Theories of geographic concepts: ontological approaches to semantic integration[END_REF]. During the generalisation process, there are some basic elements, generalisation constraints, generalisation methods and generalisation modelling. The generalisation constraints are often implemented as functions of generalisation. This chapter reviews two kinds of generalisation: model generalisation and cartographic generalisation.

Model generalisation focuses on selection and adaptation of objects from the database. Cartographic generalisation considers visualisation issues. Most of exiting works consider cartographic generalisation in the hydrographic chart construction. However, it is necessary to select useful data from database and manage semantic and relationship between objects in a chart. Generalisation operations can be specific to either model or cartographic generalisation or can be used in both.

Because the results of generalisation can be affected by sequence of generalisation operations, it is necessary to design a modelling to organise the whole generalisation process. In the existing works, there are some algorithms of nautical chart generalisation, which use isobaths and soundings selection. In the soundings selection, the soundings reflect the submarine relief as shape. Through the regulations, soundings can be selected during some iteration process. However, there are some problems in the soundings selection, such as the large number of soundings and the discrete distribution in the nautical chart. It is necessary to consider the density of soundings as well. The isobath represents the depth of submarine relief. The generalisation of isobath is similar to the generalisation of line segment. Moreover, it needs to consider the special constraints of nautical chart as well. The existing works have combined some operations of isobath generalisation and deal with some conflicts. Nevertheless, it has trouble to describe topological information in the nautical chart. The contour tree helps to define terrain features and recode the topological relationship in the nautical chart.

As a consequence, there are three main aspects that should be considered during construction of a legible chart. Firstly, it is necessary to know the purpose of map that is help to select suitable type of chart. Second, a DTM is required to organise data of chart and represent landforms accurately. Therefore, this works should consider how to organise the large set of submarine relief's information and build their spatial relationships in the conceptual model. Ontology is a beneficial method to organise different kinds of information. So far, few existing works have been done about model generalisation, and some concepts and operations of model generalisation are still imperfect. Also, automatic generalisation lacks of generalisation modelling process to decide what should be done and the sequence of operations. Because model generalisation is important for undersea feature representation and cartographic generalisation, this work will consider model generalisation. Before model generalisation, it is necessary to characterise and classify undersea features using ontology.

Then, this work will move to cartographic generalisation. The ontologies of submarine relief and generalisation process will lead to a nautical chart representation framework (Chapter 2) that will be integrate in generalisation process (Chapter 3). The automating the chart generalisation works on to identify and classify important and precise information on a chart without spatial and visual conflicts.

M

ost of current works focus on cartographic generalisation and consider isobath generalisation and sounding selection respectively. This work will consider isobath and sounding together. Hence, feature as an cartographic object considers in the nautical chart representation. Before construction of nautical chart, it is necessary to formalise geographic and cartographic knowledge. Formalisation of concepts, attributes and relationships characterising undersea features can be achieved using an ontology. Ontology allows the integration of knowledge and the building of relationships primarily based on data meaning [START_REF] Fonseca | Ontology-driven geographic information systems[END_REF]. In the geographic domain, ontology helps to organise geographic information and formalises topology and mereology relations between geographic objects [START_REF] Duce | Towards an ontology for reef islands[END_REF]. Construction of such an ontology is done by integrating different ontologies describing undersea features at different levels. This chapter aims at defining and building a framework of ontologies of the submarine relief and the generalisation process with their geometric, topological and semantic characteristics at two levels. This framework ONTOLOGIES is based on the conceptual framework for geographic information integration introduced by [START_REF] Fonseca | Ontology-driven geographic information systems[END_REF]. First, a domain ontology of the submarine relief is presented. This ontology introduces the different concepts required for the classification of features based on their spatial and semantic properties. The submarine relief ontology is defined as a subject ontology describing all types of undersea features in the logical universe. On the one hand, undersea features are classified by their absolute and relative position. On the other hand, an undersea feature is described by its shape and decomposed into several parts, such as its tip, body and base. All the information of undersea features' properties and relationships are organised in the ontology. Second, bathymetric entities that are portrayed on the map are presented. Two method ontologies are defined and connected, one includes different cartographic objects of nautical chart, such as isobath, sounding and feature, and the other describes generalisation constraints, conflicts and operations. All ontologies are integrated together into an ontology conceptualising the submarine relief elements and their representation to form the root of a larger ontology of the bathymetry and the representation of nautical chart. Section 2.1 reviews concepts of ontology and geographic ontology, and exiting works on this domain. Section 2.2 introduces the ontologies that are defined for nautical chart construction. It presents the framework of ontology, and details the submarine relief ontology as part of the application domain ontology and both cartographic representation ontology and generalisation process ontology as part of the phenomenological domain ontology. Section 2.3 concludes this chapter.

Geographical Ontologies

Concept of Ontologies

Ontology is a branch of philosophy that answers questions of being or existence [START_REF] Smith | Do mountains exist? towards an ontology of landforms[END_REF]. Ontology studies the nature and categories of being, since it seeks an answer to such questions as: what categories are, how they are specified, and how they are related to each other [START_REF] Englebretsen | A reintroduction to sommers' tree theory[END_REF]. Ontological theories are formulated from the perception of the world [Hartmann, 2012] through a continuous and complex process of examination and improvement on the basis of scientific research [START_REF] Kavouras | Theories of geographic concepts: ontological approaches to semantic integration[END_REF].

In recent years, ontologies have been a field of research in computer science with application in knowledge representation, information integration, information extraction and so on. In information science, ontology defines a set of concepts and their interrelationships, providing a specification of a conceptualisation of a given domain which can be accepted and reused [START_REF] Smith | Geographical categories: an ontological investigation[END_REF]. There are some differences between ontology research in computer science and philosophy [START_REF] Kavouras | Theories of geographic concepts: ontological approaches to semantic integration[END_REF]. First, in philosophy, ontology is a theoretical endeavour independent of the language used to represent it, whereas for computer science an ontology is an artificial engineering dependent on a specific vocabulary and computational environment. Second, ontology from the philosophical point of view is searching for the truth behind reality, whereas for computer scientists the truth is not a primary concern, since they are foremost interested in designing ontologies for specific needs pursuing functional criteria and constraints. Third, philosophy focuses on entities, properties, relations, actions, etc., whereas information science focuses primarily on languages, and generally representational and computational issues. [START_REF] Guarino | Formal Onthology in Information Systems[END_REF] adopts the term conceptualization for the philosophical perspective and the term ontology for the computer science perspective.

Ontology has been widely recognized as a priority research theme for the geospatial domain [START_REF] Smith | Ontology and geographic kinds[END_REF]]. Ontological research in the geospatial domain embodies both a philosophical as well as a computer science perspectives [START_REF] Kavouras | Theories of geographic concepts: ontological approaches to semantic integration[END_REF]. The philosophical perspective studies the constituents of geographic reality, that is, seeks to define the fundamental geospatial concepts, processes, and relations, as well as the theories governing them. In order to share common understanding of geographical information among people, geographical objects need to be defined accurately and organised into categories. The computer science perspective deals with issues relative to the strict description and formalisation of geospatial categories and relations in order to facilitate human understanding and interaction with geographic information, information standardisation and integration for effective information exchange and reuse [START_REF] Kavouras | Theories of geographic concepts: ontological approaches to semantic integration[END_REF]. Geospatial ontologies can deal with the totality of geospatial concepts, categories, relationships, processes, and with their interrelations at different resolutions [START_REF] Mark | Ucgis emerging research theme: Ontological foundations for geographic information science[END_REF]. Usually, ontologies have four components: concepts, relations, axioms, and instances [START_REF] Kavouras | Theories of geographic concepts: ontological approaches to semantic integration[END_REF]. As a vocabulary of the terms, concepts are expressed by a definition with their properties and relationships. For instance, the concept landform is described as a natural physical feature of the earth's surface. Relations consider that intended meaning can only be implicitly inferred using common sense, domain/expert knowledge, or available structural knowledge of the associated concepts, which are not mentioned in the concepts. In geo-ontology, two main sets of structures are used to describe relationships: is-a relationship (a subsumption relationship) and is-part-of relationship (mereology relationship). Is-a relationship is normally based on properties shared by similar concepts, forming taxonomies, like a mountain is a landform. Is-part-of relationship describes part-whole relationships, which form a partonomy, such as a ridge is a part of a mountain. Usually, both sets of relationships are mixed in the structure of an ontology. Figure 2.1 is an example of ontology including is-a and is-part-of relationships. In addition, there are some other relationships, like connectivity, adjacency, topology and so on. Axioms specify constraints or rules about the values of properties, relationships, properties of relationships, and instances. Instances are real "things" that are represented by a concept, such as Alps is an instance of mountain.

Ontology not only organises knowledge, but also makes reasoning to derive more information that are not expressed in ontology or in knowledge base explicitly. Reasoning "allows one to infer implicitly represented knowledge from the knowledge that is explicitly contained in the knowledge bas" [START_REF] Baader | Basic description logics[END_REF]. From a computer science point of view, ontology includes reasoning ONTOLOGIES engine based on the rules defined in First Order Logic (FOL) in order to infer some knowledge. Furthermore, logical reasoning can be used to discover implicit relationships between search terms and service descriptions [START_REF] Teller | Ontologies for urban development[END_REF]. It helps to obtain implicit spatial and temporal relationships in the geospatial domain. Hence, the ontology design should be supported by reasoning.

Ontology Levels

Ontologies may take different forms, but they always consist of a vocabulary of terms and the description of their meaning, usually through definitions, as well as a specification of their relationships [START_REF] Uschold | Ontologies: Principles, methods and applications[END_REF]. Figure 2.2 illustrates the two classification types of ontology. Depending on the level of formality, some ontologies may also include axioms which impose rules and constrain the values of concepts. In existing works, ontologies have been defined at different levels of dependence from the specific knowledge they conceptualise. [START_REF] Gruber | It is what it does: The pragmatics of ontology[END_REF][START_REF] Gruber | Every ontology is a treaty. interview for semantic web and information systems sig of the association for information systems[END_REF] classified ontologies into levels of formality: (a) informal ontology supports human understanding, (b) formal ontology supports automated processing and analysis, and (c) semi-formal ontology aims to integrate information, which includes informal parts and formal parts for real-world applications. Guarino classified ontologies into four generality levels according to their proximity to a specific task or point of view [START_REF] Guarino | Semantic matching: Formal ontological distinctions for information organization, extraction, and integration[END_REF]. Figure 2.3 represents relationships between the four categories.

• Top-level ontologies provide unified concepts, such as space and topologic relationships and address to large communities of users. Concepts are defined independently from any task, application or domain. Usually, these notions provide the framework for the definition of ontology categories, properties, and relationships and for the evolvement of domain ontologies [START_REF] Guarino | Semantic matching: Formal ontological distinctions for information organization, extraction, and integration[END_REF].

[ [START_REF] Kavouras | Theories of geographic concepts: ontological approaches to semantic integration[END_REF]. An example of top-level ontology is the mereotopology ontology that describes parts and wholes, and the topological relationships [START_REF] Smith | On drawing lines on a map[END_REF] .

• Domain ontologies describe the concepts related to a generic domain, such as geography and chemistry.

• Task ontologies describe the concepts related to a generic task or activity, such as image interpretation [START_REF] Fonseca | Ontology-driven geographic information systems[END_REF]. Domain and task ontologies are both specialisations of toplevel ontologies.

• Application ontologies are at the lowest level and describe a specific application through specialisation of both domain and task ontologies. For instance, a real estate ontology defines concepts regarding both the geography-cadastre domain and the task ontology related to land CHAPTER 2. A NAUTICAL CHART REPRESENTATION FRAMEWORK BASED ON ONTOLOGIES property buying and selling.

Conceptualising knowledge for a specific application is done by gathering specific knowledge from a domain and by integrating concepts from higher level ontologies.

Universes Paradigm of Geographic World

In order to represent real world through computer, it is necessary to understand the geographic world. [START_REF] Smith | Do mountains exist? towards an ontology of landforms[END_REF] provided an object-based ontology of mountains and other landforms that described the common conceptions of the environment. These ontologies supported spatial reasoning and natural language processing. Based on the "primary" theory, [START_REF] Smith | Do mountains exist? towards an ontology of landforms[END_REF] described natural objects in the ontology. Primary theory is part of common sense which we find in all cultures and in all human beings. Primary theory recognises not only objects but also corresponding attributes (properties, aspects, features) and their relationships.

Fonseca [2001] introduced a five-universe paradigm to represent the geographic world. Each of the five universes deals with conceptual characteristics of geographic phenomena of the real world in the abstraction model. The physical universe is the real world with all the real objects that people are capable of perceiving, such as rivers and mountains. When a geographic phenomenon in the real world is captured by the human cognitive system and is classified and stored in the human mind, the cognitive universe represents real world objects. Then the logical universe provides explicit ontologies formalising the cognitive universe. The representation universe deals with the description of geographical elements from the logical universe and contains ontologies conceptualising the elements according to the type of representation (e.g. field or object model). Finally, the implementation universe describes algorithms and data structures as implemented in the application. Figure 2.4 explains structure and connection of five universes. From physical universe to cognitive universe, images represent real world objects of the physical universe into the cognitive universe through vision process. These images are formalised in the logical universe. The semantic mediators connect the logical universe to the representation universe. The ontologies in the representation universe and logical universe can be translated into computer languages, generating classes that belong to the implementation universe.

In order to organise information about geographic worlds into ontologies, a multiple-ontology approach is considered. Knowledge is shared between the logical universe and the representation universe [START_REF] Fonseca | Ontology-driven geographic information systems[END_REF]. Fonseca defined first the Application Domain Ontology (ADO) in the logical universe. The ADO is concerned with describing specific subjects and tasks. There are therefore two kinds of ontologies: a subject ontology describing the vocabulary related to a generic domain, and a task ontology describing a task or application within a specialisation domain. Second, the Phenomenological Domain Ontology (PDO) in the representation universe manages different properties of the geographic phenomena in the GIS. It is composed of method and measurement ontologies. The method ontology defines a set of algorithms and data structures that can trans- The five universe paradigm [START_REF] Fonseca | Ontology-driven geographic information systems[END_REF].

form from the logical level to the representation level, and the measurement ontology describes the physical process of recording a geographical phenomenon. Both universes are defined separately. Different representations can be defined for one application or one representation used for different applications. The connection between both ontologies is made by semantic mediators, which perform two basic functions: selection and identification. Selection is the operation of choosing the right methods that perform the identification, and identification is the process of transforming generic entities present into entities from ADO to PDO at the representation level. Through semantic mediators, different application domain ontologies can be related to a single phenomenological ontology. The objectives of separating geo-ontologies in PDO and ADO is to emphasize the detection of spatio-temporal configurations of geographic phenomena, and reuse elements of the same ontology in different applications. Figure 2.5 illustrates the structure of PDO and ADO.

Geo-ontology in Cartography

A map represents various geographic information for different applications. Hence, ontology can be used in cartography to organise knowledge and formalise information. Both the data are portrayed on the map and on how to obtain and process them. In existing works, general domain ontologies Figure 2.5: Phenomenological and application ontologies [START_REF] Fonseca | Ontology-driven geographic information systems[END_REF].

were defined by mapping agencies such as the IGN-E in Spain [Gómez-Pérez et al., 2008] and the Ordnance Survey1 in the UK. Both ontologies rely on several ontologies including a topographic ontology and a hydrologic ontology. Top level ontologies such as spatial ontology are also included. The National Geographic Institute of Spain built a taxonomy ontology of geographic feature types, which aims to create an integration framework for maintaining databases and solve heterogeneity problems [Gómez-Pérez et al., 2008]. Two stages are used to deal with heterogeneity of data sources and build automatically a domain ontology about geographic feature types. One stage is to creates automatically an ontology, called PhenomenOntology, using the semantics of catalogue sections (Administrative boundaries, Vegetations, Buildings, etc.). This ontology has three levels of granularity: a common superclass of feature concepts whose names begin with an identified substring, a substring criterion level to solve the heterogeneity problems, and a new taxonomy level for different values of group that represents a top level classification of features. The other stage is to discover automatically mappings that can relate ontology concepts to database instances. Ordnance Survey provided several kinds of ontologies to organise knowledge of different domains and represent different datasets in a semantically meaningful way via ontologies, including administrative geography, hydrology and topography. The domain ontologies of Ordnance Survey and IGN-E aim at managing huge amount of geographic informations for cartography. The advantages of these ontologies are the improvement of knowledge management for mapping. But they do not consider map generalisation. Map generalisation is an important and complex part in the map construction. In order to improve the map construction, ontology not only needs to formalise the basic information of features, but also should manage the extra attributes (spatial relationship, geometric information, etc.) of cartographic objects and various factors in the generalisation process. [START_REF] Gould | An ontological approach to on-demand mapping[END_REF] developed a generalisation ontology for on-demand mapping attempting to capture, in one-step, all the knowledge that could be used to describe the generalisation process and considered legibility during change of scale. It includes an operation ontology that organises generalisation operations and conditions, which aims to describe the properties, behaviours and relations of generalisation operations in such a way that they can be selected and used to resolve conditions automatically. Figure 2.6 shows the operator ontology, including the condition concept that specialises further into logical conflict, congestion, high density congestion and imperceptibility. An algorithm ontology connects generalisation algorithms to different terrains and feature types. For example, the algorithm concept implements the smoothing operator that is applied to road feature type. This work is able to automatically select, sequence and execute map generalisation operations according to user requirements, but it can not automatically provide parameter values to the selected services especially since two algorithms performing the same generalisation operation may have different parameters. For instance, two algorithms have a common name with different values. In addition, each algorithm implements multiple generalisation operators. Finally, one should connect algorithms and operators to formalise generalisation plans. [START_REF] Touya | Towards an ontology of spatial relations and relational constraints[END_REF] provided an ontology to manage spatial relationships and relational constraints between geographic features in the context of generalisation. It classifies spatial relationships in eight categories depending on a taxonomy, which helps to automatically select algorithms in a process of generalisation or on-demand mapping. It includes topological relations that contain classical 9-intersection primitives [START_REF] Egenhofer | Point-set topological spatial relations[END_REF], orientation relations like relative orthogonality, position relations that gather the relative position relations, proximity relations, shape relations, size relations, semantic relations, and movement relations gathering relations that can be expressed by a movement verb like "the river circles the building". Figure 2.7 describes relationships between spatial relation, feature and operation. In addition, constraints are organised in a hierarchy within the constraints ontology (Figure 2.8). These ontologies help to improve map generalisation automation and on-demand mapping. But this work has not connected spatial relationships ontology and constraint ontology. Related to the whole generalisation process, ONTOLOGIES generalisation operations also need to be considered in the model.

In these works, concepts describing objects portrayed on the map relate to objects stored in the topographic database without ambiguity. For example, in the expression "the river circles the building", the river and the building already have properties including a geometry explicitly defined in the database. This does not apply to undersea features which are not modelled in the bathymetric database. One supplementary requirement is the characterisation of undersea features. As said by [START_REF] Janowicz | A geo-semantics flyby[END_REF], "the definitions of feature types are a product of human perception, cognition, current state of knowledge and social agreement" and so are often domain-specific. In hydrography, a nomenclature is provided by the IHO and used in the GEBCO gazetteer of undersea feature names 2 . As each feature type is defined by one or two sentences, a semantic model is required to capture the meaning into a set of concepts and relationships. On one hand, such model leads to an object-based representation where each feature is a part of the seafloor corresponding to common perception but whose properties including its boundaries are not clearly defined [START_REF] Smith | Do mountains exist? towards an ontology of landforms[END_REF]. On the other hand, the bathymetry is defined by a field model (and stored in the database by a discrete set of soundings and isobaths), leading to what [START_REF] Smith | Geographical categories: an ontological investigation[END_REF] called the "qualitative-quantitative divide".

Ontologies for Nautical Chart Generalisation 2.2.1 Organisation of the Ontology Framework

The conceptualisation of the bathymetry represented on nautical charts requires the definition of several ontologies. In order to formalise ontologies, there are two key steps: one describes submarine relief from human mind to computer language, the other organises cartographic information to formalise generalisation process. The whole work should consider universe paradigm of geographic world and defines ontologies in different levels. Based on existing works (Section 2.1), the PDO and ADO of Fonseca's framework helps to classify geographic and cartographic knowledge in logical and representation universes. Therefore, following Fonseca's framework, concepts describing the maritime domain are part of the logical universe (Figure 2.9). The subject ontology conceptualises knowledge about submarine relief and is derived from the IHO terminology [International Hydrographic Organization, 2008]. It defines literally all the characteristics of undersea features in terms of properties and relationships. Nautical charts being mainly designed and used for navigation purpose, the task ontology describes specialised applications that would logically be related to navigation and route planning.

The nautical chart that provides a representation of the seafloor and concepts pertaining to the construction of the chart and its generalisation is in the representation universe. As mentioned before, the PDO is defined for a specific representation independently from the ADO. Therefore, the method ontology describes the concepts used for the representation on the chart. That includes among others the graphical elements displayed on the chart (isobaths, soundings) but also the generalisation operations required (sounding selection, isobath extraction etc.) to deal with representational issue on a nautical chart and operations matching features from the ADO with the PDO. The measurement ontology refers to data collection techniques (e.g. echo sounding, LI-DAR etc.). The measurement and task ontologies are out of the scope of this thesis and they will not be address. ONTOLOGIES [International Hydrographic Organization, 2008]. The IHO provides a nomenclature of 46 undersea features, each of them defined in natural language. It is available in different languages to provide a uniform terminology but as discussed in section 1.4, the definitions are inherently vague and cannot be used directly for information representation. Therefore the terms of the nomenclature need to be formalised and organised into a set of properties and relationships in view of their automatic processing. This formalisation is done through the design of the subject ontology. The subject ontology relies mostly on the IHO terminology but other documents related to the preparation of nautical charts from hydrographic services [START_REF] Shom | Etude d'aides à la préparation des cartes marines étude de faisabilité: Partie 2 Conception detaillée des traitements. Rapport technique[END_REF][START_REF] Oraas | Automated sounding selection[END_REF] are also used for the extraction of entities and properties in ontologies. The nomenclature can be transformed into a set of formal definitions but is not concerned with the representation of the bathymetry on a chart or any kind of visual support. Perception of undersea features on a chart follows specific mechanisms, based on the spatial distribution of soundings and isobaths, which also need to be formalised through an ontology of the representation. Hence, building the domain ontology is done in two steps. First, properties and relationships characterising each of the 46 features are identified by analysing the definitions and extracting keywords corresponding to feature characteristics. Second, these characteristics are organised into different classes (composition, shape) and relationships. They correspond either to instances of different classes or to relationships (mereological, topologic, taxonomic) connecting features. At the end of the process, classes defining undersea features form a hierarchy of classes. Properties composing each feature are formally defined in separate classes by their instances. This research follows the principles underlined by Naive Geography [START_REF] Egenhofer | Naive geography. Spatial Information Theory A Theoretical Basis for GIS[END_REF] where formal models are derived from common sense and introduces a model where the main modelling primitives are considered as objects rather than geometric primitives. The model is also based on the assumption that the perception of a particular feature is dependent of the perception of its saliences defined as significant points of interest in the silhouette description. Figure 2.10 shows the structure of the proposed submarine relief ontology, which includes concepts of composition, morphometric class, undersea feature, shape value and depth level. Composition of seafloor includes rock, sand, volcanic and so on. In order to describe the feature shape, undersea feature can be divided into three parts: its body, tip and base (Figure 2.11). For example, a plateau has a flat or nearly flat (tip) elevation (body) of considerable areal extent (base), dropping abruptly on one or more sides (body). The attributes of these different parts are defined in the concepts of morphometric class and shape value. Finally, depth level helps to describe location and spatial relationships of undersea features. Details of each concept are introduced in the following parts.

Depth Level

The seafloor can be divided into three main parts: continental margin, basin and mid-ocean ridge [START_REF] Wright | The ocean basins: their structure and evolution[END_REF]] (Figure 2.12). Each part has its very own morphological characteristics and is related to different types of physical activities. They form a neat partition of the seafloor corresponding to different levels of depth. As a consequence, each undersea feature can be related to a specific part of the seafloor and classified accordingly, providing details on the depth at which the feature can be found and the possible features with which it can be related. It provides also same information the relevance of the feature according to different types of application (including navigation).

The continental margin is the most important part of the seafloor, corresponding to the transition between the continent and the deep ocean [START_REF] Seibold | The sea floor, an introduction to marine geology[END_REF]. There are two kinds of continental margin: the passive margin and the active margin [START_REF] Wright | The ocean basins: their structure and evolution[END_REF]]. Both of these continental margins are divided into a continental shelf, a shelf break and a continental slope.

In addition, many passive continental margins have a continental rise, a gentle slope of sediment that forms between the continental slope and the basin. Unlike passive continental margins, active continental margins lack a continental rise and the continental slope extends into an oceanic trench.

Basin is one of the largest features of the seafloor. It is a deep depression of more or less circular or oval form [START_REF] Stewart | Experiences in developing landform ontologies[END_REF]. Mid-ocean ridges are continuous submarine mountain chains separating ocean basins. These features form a partition of the seafloor (Figure 2.12) and are also defined in the IHO terminology. Therefore, they can be connected by spatial and mereological relationships as shown in Figure 2.13.

Shape Value

The Shape value class is the super class of three specialised classes describing different parts of the feature. Figure 2.14 shows relationship between undersea features and shape value in the submarine relief ontology. The body is described by the feature height, vertical profile and relative spatial extent. The vertical profile defines the overall shape (peak, ridge, plane area) which includes the morphometric class as well as the type of slope (steep, gentle, horizontal). The relative spatial extent indicates if a feature is relatively large or small with regard to its height. The tip concept applies to eminences and depressions and describes the shape of the extremity. For example, a summit can be sharp (like a pinnacle) or flat (like a plateau). Finally, the base is described by the horizontal profile (e.g. elongated, circular).

The Relative Spatial Extent is defined by the ratio between the feature height and its spatial extent. It includes two values, large and small. Large (respectively small) means that the area of the object is large (respectively small) with regard to its height and correspond to a value lower (respectively greater) than a given threshold.

The Horizontal Profile is defined by the ratio between the length and the width of the feature base. If close to 1, the feature is equidimensional otherwise it is elongated.

The Vertical Profile classifies undersea features with more details according to the slope and elevation of the feature with regard to its neighborhood. The value is indeed related to the Morpho-ONTOLOGIES metric Class. Although Morphometric Class classifies point features in six types, it is not enough to describe undersea features at different granularity. In order to represent submarine relief and refer to nautical chart generalisation, four sub-concepts are added to describe the vertical profile of undersea feature:

• Eminence if the feature is higher than its surrounding, such as a hill which is an isolated elevation.

• Depression if the feature is lower than its surrounding, such as a trench which is an asymmetrical depression of the seafloor.

• Slope if the feature is an inclined plane, such as a shelf or a levee. Depending on the IHO document, slope values can be gentle or steep.

• Horizontal plane if the feature refers to an horizontal flat plane.

The Tip Type concept describes the outline of eminence and depression features. Therefore, each type can describe either the summit of an eminence or the bottom of a depression. • Line means that the salient part of the feature is directed along a linear axis. This axis can be a line or a ring. The vertical profile of the features is like a 'V' shape. Ring features are like a circle. Figure 2.16 illustrates the line features. The Horizontal Profile value of Line feature is normally elongated.

• Area tip is a broad area at the top or bottom of an undersea feature. The Area tip is usually equidimensional. It can be a tapered area of relatively small extent and the change of elevation with its surrounding area is steep. Flat area means that the area is large and flat with big change of slope on the borders as for a plateau. Round area means the transition between the area which is a curved surface and the side slopes is rather smooth. Table 2.1 models such area tip types.

In summary, the undersea feature concept represents features from IHO document and characterises them according to their composition, morphometric class, shape values and depth level. For instance, a seamount feature is a peak feature whose height is greater than 1000 m, its horizontal profile is equidimensional and its composition is volcanic. In order to describe relationship of features, all feature concepts are gathered in a hierarchy where features at upper levels correspond to broad concepts from which several features sharing the same similarities can be derived. Figure 2.17 shows some examples of superclasses with their properties and relationships. A guyot is a kind of seamount feature, which has small smooth flat top and drops of abruptly around. A knoll is a hill feature with small rounded profile. The hill feature is smaller than the seamount feature. Both of them belong to peak feature, and eminence feature is a superclass of peak feature. In addition, basin is a plane feature, which has large area and flat tip, and is located at the bottom of the seafloor. Shelf and continental margin are slope feature, which are the other kind of plane feature.

They have large area and gently slope tip. Based on the depth level and spatial relationship, knoll is contained by shelf, and guyot is contained by basin. Also, basin touches with continental margin.

The Phenomenological Domain Ontology

The phenomenological domain ontology organises the representation of bathymetry on the nautical chart, and includes two method ontologies: the cartographic representation ontology and the generalisation process ontology. The generalisation process ontology aims at managing all the elements of generalisation and describing the whole generalisation process. The cartographic representation ontology describes objects that are portrayed on the nautical chart and their relationships. Following sections will introduce all the details of the two ontologies.

The Cartographic Representation Ontology in PDO

The PDO ontology not only defines cartographic elements drawn on the map and cartographic constraints, it also describes how features are portrayed on the chart. It is built based on documents from the SHOM3 and the NOAA 4 . In total, four main concepts -chart, isobath, sounding and feature -are defined together with their spatial relationships and data properties (e.g. density of soundings in a feature) (Figure 2.18).

Charts are produced at a large range of scales according to the purpose and area portrayed, from small scales used for route planning to very large scale for navigation along coastal areas and in harbours. Chart properties include the scale, the location and the date, and define metadata such as the isobath depth levels and the density of sounding from which generalisation constraints are derived.

Soundings are divided into three main classes: prime sounding, limiting depth sounding and background sounding [START_REF] Zoraster | Automated cartographic sounding selection[END_REF] (Figure 2.19). Prime soundings tend to be distributed irregularly over a nautical chart and reflect some significant undersea features in areas of high relief, such as shoal. Hence, prime soundings play an important role in navigation. Mostly, prime sounding present isolated features, which can be enclosed by an isobath. Limiting depth soundings show the least depth encountered when following the deepest part of a natural channel or river. They relate to some hazardous shallow areas. Background soundings describe regular areas on the nautical chart and represent the largest part of the soundings. In order to distinguish more details in the nautical chart, background soundings are separated into three kinds: deep soundings, fill soundings and supportive soundings. Deep soundings are approximately 10% to 20% deeper than their surroundings [START_REF] Maxim | Nautical Chart User's Manual[END_REF] and are less important than prime soundings and limiting depth soundings. Fill soundings provide information about large, gradually sloping depressions that are 52 CHAPTER 2. A NAUTICAL CHART REPRESENTATION FRAMEWORK BASED ON ONTOLOGIES not deep enough to be enclosed by an isobath [START_REF] Maxim | Nautical Chart User's Manual[END_REF]. Supportive soundings provide additional information about the shape of the seafloor and periodic identifiers for isobaths to show changes in bottom slope away from shoals or deeps [START_REF] Maxim | Nautical Chart User's Manual[END_REF].

Isobaths are equal depth contour lines depicting submarine relief. On a chart, the vertical interval between two consecutive isobaths is not regular, the interval being shorter in shallow areas where more information is required. For example, in figure 2.20, the purple ellipse identifies a channel in the sea. In addition, comparing the area in the red rectangle with the green rectangle, the interval of isobaths in the green rectangle is larger than that in the red rectangle. Hence, the area of the red rectangle could be more rough or dangerous. As a result, isobaths should be generalised depending on the purpose and application of the map. For instance, when generalising a map from high resolution to low resolution, a small isobath could be deleted if it is not important in the map.

The whole generalisation operations and process is based on specific rules, which will be defined in the generalisation process ontology (Section 2.2.3.2).

Feature is a concept defined in the cartographic representation ontology, which is deduced from the isobaths and soundings. The definition of feature combines the knowledge of submarine relief and cartographic representation ontologies. Navigators identify dangerous areas and other relevant features on the nautical chart as groups of isobaths combined with soundings and forming specific patterns. In addition, topological relationships describe the relationships between isobaths, soundings and features. Elements described in this concept are not portrayed on the chart like soundings and isobaths but can be perceived from the spatial structure. For example, an elevation is represented by at least a sounding higher than its surrounding or by a set of circular isobaths higher in the centre. It is divided into three subconcepts: critical lines, morphometric features and morphometric area (Figure 2.21).

• Critical lines connect critical points (saddles, maxima, minima) to identify same feature lines. They are perpendicular to isobaths [START_REF] Bajaj | Visualization of scalar topology for structural enhancement[END_REF]] (Figure 2.22). Critical lines help to identify morphometric features and are the support to some specific features, such as canyon.

• A Morphometric Feature is composed of soundings, isobathymetric lines, and/or critical lines Figure 2.22: Isobath (dotted line) and critical lines (black line) connect critical points [START_REF] Bajaj | Visualization of scalar topology for structural enhancement[END_REF].

and represents a feature on the chart. This concept provides the representation for features from the shape value of ADO. Among these features, the depression class includes channels and pits, and the eminence class includes ridges and peaks. On a nautical chart, pit and peak that are defined in the ADO are represented by at least one sounding most often enclosed by an isobath. Ridge and channel from ADO are described by soundings marking the critical line and bordered by one or several isobaths. A pass describes a feature located in a lower (respectively higher) region joining two higher (respectively lower) regions.

• Morphometric Area classifies different types of bottom and provides knowledge for sounding selection. There are three different kinds of seafloor: smooth area, rough area and hazard area. Smooth areas are described as wide with gentle slope variations and so can be represented with a low density of soundings. Smooth areas mostly include plane features and are located in deep sea. Rough areas contain different undersea features with large depth and slope variations.

Because there are some important undersea features in rough areas, more soundings will be selected. Moreover, supportive soundings are selected to reinforce the least depth as well as to define the zones between the shoals [START_REF] Maxim | Nautical Chart User's Manual[END_REF]. Hazard areas are shallow regions of the continental margin which are dangerous for navigation. Usually, the density of soundings in these areas is high.

The Generalisation Process Ontology in PDO

The ontology of the generalisation process is a method ontology in the representation universe, which describes and manages the whole generalisation process. During the generalisation process, some factors should be considered to represent terrain surface at different levels, such as generalisation operators and constraints [START_REF] Creac'h | Aide à la préparation des cartes marines, cahier des charges fonctionnel[END_REF]. Section 1.3 introduced three important aspects of generalisation process: when, what, how. When the conflicts are detected in the map, generalisation operations should operate on the cartographic elements to resolve conflicts. Therefore, this ontology includes three main components: generalisation constraints, evaluation measures and The generalisation process includes two main components: evaluation measures and generalisation operations. Evaluation measure is a group of methods detecting existing conflicts on a nautical chart. This activity implements before and after generalisation operations. At the beginning of generalisation, evaluation measure uses constraints to evaluate conflicts of cartographic elements. If there are some conflicts, generalisation operations will resolve them depend on priority of constraints. After generalisation operations, evaluation measures will re-evaluate conflicts in order to detect new conflicts that are produced during generalisation. Generalisation operations include several operators related to cartographic elements, such as displacement of features and sounding selection. Depending on result of evaluation measure, generalisation operations modify cartographic elements. During this process, constraints will be used to preserve the characteristics of cartographic objects and achieve the objectives of generalisation process. The generalisation process is guided by cartographic elements. The constraints are used by evaluation measures and generalisation operations to detect and resolve conflicts of features. The following introduces definitions of generalisation constraints, evaluation measure and generalisation operations.

Generalisation Constraints

Based on existing generalisation constraints (Section 1.3.1.1), this work classifies constraints in two groups (Figure 2.24): conflict and preservation. A conflict describes a constraint violation, such as a sounding overlays on an isobath. The preservation constraints are used to control the generalisation operations in order to preserve the requirements of generalisations.

All conflicts violate the legibility constraints. Legibility constraints aim to improve visual representation on the nautical chart. Important objects should be large enough and not too detailed.

In addition, the distance between two objects should be large enough to be distinguished. For instance, the distance between two isobaths must be larger than a threshold. Therefore, this work classifies conflicts into two groups: distance conflicts and area conflicts. The following equations describe legibility constraints of nautical chart generalisation where, S = {s 1 , s 2 , s 3 , ..., s n } is the set of sounding, I = {i 1 , i 2 , i 3 , ..., i n } is the set of isobath and F = {f 1 , f 2 , f 3 , ..., f n } is the set of undersea feature on a chart.

• Distance conflict: in order to identify features clearly, the distance between two features should be larger than a threshold. Feature is composed by soundings and isobaths. Hence, distance conflicts describe issues of distance between soundings, isobaths, sounding and isobath.

-C 1 . Distance between isobaths and soundings: a soundings cannot overlay on another sounding; a isobath cannot overlay on another isobath; a sounding cannot overlay on isobath.

C 1 = {∀(o m , o n )ǫO × O, o m ∩ o n = φ}, where O = {S, I}. (2.1) -C 2 .
Distance between features: distance from a feature to another features should not be less than a minimum distance.

C 2 = {∀(f m , f n )ǫF × F, distance(f m , f n ) > ε.
(2.2)

• C 3 . Area conflict: area of a feature should be large enough to be identified.

C 3 = {∀o m ǫO, size(o m ) > ε x }, where O = {I, F }. (2.
3)

The preservation constraints include functional, position and shape, topological and structure constraints. All of them are used to preserve various characteristics of objects during the generalisation process. Safety constraint is the functional constraint that cares about the safety of navigation, which is the most important constraints in the nautical chart generalisation. For example, depending on the safety constraints, hazardous undersea features must be kept in the nautical chart. In order to identify what features are hazardous features on a nautical chart, this work defines safety constraints in the following:

• C 4 . A sounding cannot be removed if the new interpolated depth is shallower than the sounding depth.

• C 5 . If a feature is an eminence feature, it cannot be deleted.

• C 6 . If an isobath is displaced, the displacement should be done towards the deeper area.

Structural and topological constraints seek to preserve object patterns and topological relationships between them on a nautical chart.

• C 7 . A closed isobath should contain at least one sounding marking its deepest or highest point. (2.4)

• Two isobaths cannot intersect.

C 8 = {∀(i i , i j )ǫI × I, intersect(i i , i j ) = φ}.
(2.5)

• C 9 . An isobath line cannot self-intersect.

(2.6)

Position and shape constraints preserve the absolute and relative position and shape of objects in the generalisation process.

• C 10 . The displacement of an isobath position should be minimized.

C 10 = {∀i m ǫI, M in(d(i m , i ′ m )) < ε, where d is the distance f unction, i ′ m is the displaced isobath i m .
(2.7)

• C 11 . The density of soundings should be controlled by a given threshold.

C 11 = {∀S ′ ǫS, density(S ′ ) > ε x },
where ε x depends on the morphometric area containing the soundings of S ′ .

(2.8)

In nautical chart generalisation, depending on different purposes, all of constraints refer to conflicts of an object or a group of objects. Most of existing works focus on constraints of isobath line generalisation (Section 1.3). In this work, the cartographic representation ontology defines that features are represented by a group of isobaths or soundings. Generating a feature not only needs to preserve its characteristics, but also should operate on isobaths and soundings. Hence, the generalisation process is guided by the features. The constraints and operations on features, isobaths and soundings are defined respectively. Refer to different kinds of objects and types of constraints, all constraints are defined and classified in several groups. Functional constraints are about the safety of navigation and are preservation constraints. Legibility constraints express conflicts to be removed during the generalisation. Both must be satisfied to provide a valid solution.

The position and topology constraints, shape and structural constraints are weak constraints and can be released if all constraints cannot be satisfied at the same time.

Evaluation Measure

Evaluation measure is a general concept for all measures of quantifying how much a constraint is preserved or violated during the generalisation process. Before generalisation, evaluation detects existing conflicts that is help to decide which generalisation operations are applied. After generalisation, evaluation is used to assess the quality of generalisation and check whether new conflicts occur. Five kinds of evaluations are defined: distance measure, area measure, density measure, shape measure and position measure (Figure 2.25). Distance measure computes the distance between two objects, such as distance between two isobaths (C 1 and C 2 ). Area measure computes the area of an object, such as the area of a feature. Distance and area measures are supported by legibility constraints. Shape measure checks the shape of a feature. Position measure checks the position of an object. The shape and position measures are supported by functional and position constraints. Depending on the priority of constraints, functional constrains must be considered firstly. Density measure computes the density of a group of objects, such as density of a set of soundings, which relates to structural constraints.

Generalisation Operations

After detecting conflicts, generalisation operations are used to resolve them. All generalisation operations are based on generalisation constraints. Meanwhile, generalisation operations should be applied to different kinds of objects. Figure 2.26 represents classification of generalisation operations and their relationships. Because the features are composed by isobaths and soundings, the generalisation of features should operate on isobaths and sounding as well. Meanwhile, the generalisation operations of isobath and sounding are different. Therefore the generalisation operations of different cartographic elements are defined respectively, and feature operation is composed of isobath operation and sounding operation.

• Sounding: Cartographic sounding selection is the operation of selecting a small number of soundings from a much larger group of soundings to represent the various information of submarine relief at different levels [START_REF] Oraas | Automated sounding selection[END_REF]. It is the only possible operation on soundings in nautical chart generalisation. Sounding selection deletes the superfluous soundings to satisfy the distance constraint on the chart. For instance, when a sounding overlays an isobath line, the sounding will be deleted or the isobath line will be displaced.

• Isobath:

-Smoothing: it aims to remove details in a line and makes the line appear smoother. In addition, smoothing must satisfy the safety constraint;

-Deletion: a line can be completely deleted;

-Segment removal: a part of line can be removed; ONTOLOGIES -Displacement: when several isobaths are too close or overlapping, displace lines or segments of lines are displaced to resolve visual conflicts;

-Merge: several isobaths fuse together.

• Feature: it is represented by a group of soundings or isobaths. Hence, the generalisation operations of features are applied to a group of soundings and isobaths. Thus, the generalisation operations of features are composed of operations on soundings and isobaths (Figure 2.26).

The following generalisation operations are presented in table 2.2.

-Deformation: the boundary line of a feature will move away from the other or both boundary lines away from each other to enlarge the distance between them. The distance between the two boundary lines should be larger than a minimum value. This operation includes displacement of isobath;

-Aggregation: it involves to join together multiple line features when the distance between them is too small. For instance, adjacent peaks are aggregated into one larger peak by merging their boundary isobaths. In this process, one small peak will be deleted, and another small peak will be enlarged as a larger peak. Deletion, merging, enlargement and smoothing operations on isobaths are used to realise the aggregation of features;

-Enlargement: in order to maintain and stress some important features, this operator enlarges the boundary line or other line segments of feature. It includes displacement and smoothing operations on isobaths;

-Selective omission: the feature is deleted with all its isobaths and soundings. It is composed by sounding selection and isobath deletion.

Formalising the Generalisation Process

The generalisation process is guided by cartographic elements and formalised by evaluation measures, constraints and generalisation operations. The score as a result of evaluations of the constraints decides generalisation operations. When we make a decision for generalisation, it is necessary to consider two sides: one is the result of evaluation measures and the other is the characteristics of features that are preserved by constraints. For example, if a feature has area conflicts, it should be deleted, enlarged or aggregated with other features. Then, we need to consider the constraints of this feature. If this feature is a peak, it should be enlarged or aggregated with other peak features. Otherwise, if this feature is a pit, it should be deleted. The following formula defines relationship of different concepts in generalisation process. The E is defined as cartographic elements without generalisation. The constraints and evaluations are composed of an element or a group of elements. The decision of generalisation operation is score of evaluation and constraint.

GenOperation(E) = Score(Constraint(E), Evalucation(Conf lict(E))). In addition, the relationships between the generalisation operations and constraints have been defined in generalisation process ontology that is help to take a decision during generalisation process. Figure 2.27 illustrates area conflict isResolvedBy aggregation, enlargement and selective omission, and distance conflict isResolvedBy aggregation, deformation and selective omission. Eminence feature is an instance of feature. In the evaluation, area measure is used to compute the area of this feature. If the evaluation result violates the area conflict that is defined in the legibility constraints, this feature has an area conflict that should be resolved by generalisation operations.

ONTOLOGIES FOR NAUTICAL CHART GENERALISATION

Enlargement is an instance of feature generalisation operation applied to an eminence feature. At the same time, the safety constraints help to choose suitable generalisation operations. Then, when enlargement operates on eminence feature to resolve area conflict, the safety constraints will control operations in order to protect the characteristics of feature. After the generalisation operation, evaluation will be used to assess the quality of the generalisation process and checks area conflicts again. During generalisation process, the sequence of generalisation operations are decided by the constraints in the generalisation process ontology.

Conclusion

The purpose of this chapter is to organise the knowledge about submarine relief and nautical chart generalisation. Taking into account the concepts of geographic ontologies and existing geoontologies for cartography, this chapter defines a framework to organise all the ontologies for nautical chart generalisation. In order to improve the nautical chart generalisation, all the information of submarine relief and nautical chart should be classified and defined in different levels. In addition, depending on the objective of this chart, all the components of generalisation should be defined. It results in two main parts: an application domain ontology (ADO) for the characterisation of undersea features, and a phenomenological domain ontology (PDO) for the representation of submarine relief on nautical charts and generalisation process. The different ontologies were developed in Protégé. This work developed a bottom-up approach derived from the acquisition and modelling of knowledge from standards established by the IHO terminology in the nautical chart representation domain.

In the ADO, the submarine relief ontology is a subject ontology formalising undersea features. The benefit of its hierarchical structure is that, depending on the density or quality of the input terrain data or the requirements of the application, the level of description can be adjusted to different granularities. As a domain ontology, the submarine relief ontology can be used not only for nautical chart production, but also for other applications (e.g. oceanography). On top of the IHO definitions, general concepts (e.g. eminence feature and plane feature) are added to provide a description of terminology. These general concepts are useful for undersea features characterisation because on one side, the bathymetric database usually does not contain enough data for a full characterisation of all features and on the other side, the amount of details is adapted to the scale and the purpose of the chart. According to the property of undersea features, submarine relief ontology uses composition relationship to describe an undersea feature in three parts: tip, base and body. Meanwhile, the depth level associated to the is-part-of relationship describes spatial and topological relationship of undersea features.

In the PDO, the cartographic representation ontology and generalisation process ontology are defined as method ontologies. It not only defines objects directly portrayed on the nautical chart, but also objects perceived or formed by patterns and linked by relationships. For instance, a feature is composed by soundings and isobaths. Generalisation process ontology defines generalisation constraints of nautical charts, evaluation measure to detect conflicts on a nautical chart, and generalisation operations apply to different objects. During the generalisation process, generalisation constraints include two types: conflict describes the visual issue, preserve is used to control generalisation operations to resolve conflicts. Based on the cartographic application on a nautical chart, generalisation constraints are classified in different levels. For instance, because the most important objective of nautical chart is to ensure safety of navigation, the safety constraints as function constraints must be considered firstly during generalisation process. In addition, generalisation operations are classified in different groups depending on the types of objects. The relationships between generalisation operations, constraints and evaluation measures have been defined and modelled in the generalisation process ontology. They are used to take a decision during generalisation process. The work in this chapter was published in [Yan et al., 2013b,a].

Based on the ontologies, the following chapter designs a multi-agent system to formalise the scheme and process of generalisation in nautical chart. It will provide generalisation plan for different conflicts depending on generalisation constraints. Also, evaluation will be implemented in the multi-agent system.

Chapter 3

A Multi-Agent System for Generalisation A utomatic generalisation is a complex process that should consider various constraints and organise different operations. In chapter 2, a nautical chart representation ontology has been defined for submarine relief characterisation and nautical chart generalisation. The ontology defines and classifies cartographic objects in three types. Depending on different constraints, different types of cartographic objects have different generalisation operations. The whole process is driven by the features. The constraints are formalised to evaluate conflicts and modify features. Hence, a framework should be provided to automatically evaluate constraints and decide which operator to apply. In addition, generalisation must consider spatial relationships between cartographic objects. Hence, the whole generalisation should be processed in several parts and consider interaction between each others at the same time. Multi-agent system (MAS) presents very attractive means for more naturally understanding, designing and implementing several classes of complex distributed and concurrent software [START_REF] Schumacher | Objective coordination in multi-agent system engineering: design and implementation[END_REF]. In order to use the knowledge of ontologies and provide solutions in autonomous map generalisation, MAS technology seems a powerful and flexible approach to be used for nautical chart generalisation. MAS technology has been used in map generalisation in different contexts. However, a framework for combining spe-cific constraints and generalisation operations, which are driven by features, into a comprehensive generalisation process is missing. This chapter outlines a multi-agent system for the automated generalisation of the bathymetry on nautical charts. Section 3.1 reviews previous works carried out by different levels of MAS that was defined by [START_REF] Ruas | The roles of meso objects for generalisation[END_REF] and four agent models for map generalisation: AGENT, CartACom, GAEL and Galanda's model. Then, a multi-agent system for bathymetric generalisation is designed in section 3.2, which is based on the nautical chart representation ontology of chapter 2. This MAS includes three levels of agents as basic component in the framework of MAS, which is introduced in section 3.2.1. The life cycle of agents are introduced in section 3.2.2. It describes the different stages an agent goes through and presents the communication mechanisms between agents in view of automating the generalisation process. Section 3.2.2.2 introduces agent methods evaluating constraints following definitions given in the generalisation ontology. After evaluation, plans of how to resolve conflicts are introduced in section 3.2.2.3. Generalisation operations are organised in plans. At last, section 3.3 concludes this chapter.

Multi-Agent System (MAS)

Agent Modelling

The concept of agent stems from the field of artificial intelligence and is defined as: An "agent is a computer system that is situated in some environment, and that is capable of autonomous action in this environment in order to meet its designed objectives [START_REF] Wooldridge | An introduction to multiagent systems[END_REF]." It has been used to solve complex problems in a broad set of domains. Each agent acts within an environment. The agent takes sensory input from its environment and produces output actions in order to affect its environment (Figure 3.1) [START_REF] Wooldridge | An introduction to multiagent systems[END_REF]. The main features of environment are nondeterministic, inaccessible, dynamic and continuous [START_REF] Russell | Artificial intelligence: a modern approach[END_REF]. Characteristics of agent are autonomy, social ability, reactivity and pro-activeness [START_REF] Russell | Artificial intelligence: a modern approach[END_REF]. An agent needs to be able to make appropriate decisions based on available information, but also to determine what to do after an action either succeeds or fails.

In the most common case, an environment contains several interacting agents to solve issues together, and is called a multi-agent system (MAS). It is a macro-system comprising multiple agents, each of them is considered as a micro-system [START_REF] Schumacher | Objective coordination in multi-agent system engineering: design and implementation[END_REF]. Hence, environment and agent are two basic components in MAS. The environment describes the situation of all agents and other objects in the system. Also, each agent should communicate with other agents in the MAS. Figure 3.2 illustrates the typical structure of a multi-agent system. An environment includes several agents and each agent has a 'sphere of influence'. The agents communicate to each other and control the environment together. The whole organization is done with a specific hypothesis and objective. Therefore, MAS should be modelled to control the interactions between agents in the environment. Schumacher [2001] introduced an architecture of an agent and explained how it works with other agents in the environment (Figure 3.1). An agent perceives its environment through its sensors. Based on its perception and its evaluation of its current state, the agent can decide (via a control algorithm) whether to take an action or not in order to move towards its objective. The action taken by the agent affects the environment and may be perceived by other agents. Following the changes in their environment, other agents may then trigger some actions in order to also meet their own objectives. In the MAS, an engine controls evolution of agents in order to reach their goals. Each agent is individual and acts in order to fulfill its own goals but all are evolving within the same environment. Figure 3.2 introduces a typical structure of a MAS that contains a number of agents, which interact with one another through communication. Each agent goes through a whole life cycle. The life cycle is formalised by several steps to describe sequence of activities in a agent. The life cycle will begin when the agent is activated and end when the agent is dead. In the life cycle, the agent might have some state: active, suspend, wait and dead. Figure 3.3 illustrates a generic life cycle of an agent. When the system is activated, the agent will go through the process, until the agent end.

Multi-Agent System (MAS) in Generalisation

In the late 1990s, agent modelling techniques began to be used in map generalisation. Modelling the generalisation process by a MAS means that "a sub-optimal but acceptable solution can often be reached" [START_REF] Lamy | The application of agents in automated map generalisation[END_REF]. Agents attempt to satisfy goals in order to achieve optimal rendering [START_REF] Ruas | A prototype generalisation system based on the multiagent system paradigm[END_REF] at the target scale. The goals can be equated with constraints in the constraint-based modelling. A MAS includes several agents to solve problems at both a local (related to a single agent) and a global (related to a group of agents) level [START_REF] Polson | Foundations of intelligent tutoring systems[END_REF]. Four agent models of generalisation will be reviewed and discussed in this section. [START_REF] Ruas | The roles of meso objects for generalisation[END_REF] proposed a system for generalisation by introducing the agent life cycle to coordinate constraints and actions and divided agents into three levels (macro, meso and micro) to coordinate their actions. Macro agents control generalisation of a population of objects, for example one macro agent controls a set of roads and the other controls a group of buildings. Meso agents govern generalisation of groups of objects such as city blocks. Micro agents are only responsible for generalisation of single objects such as buildings and roads. Macro agents contain meso agents and meso agents contain micro agents. [START_REF] Ruas | A prototype generalisation system based on the multiagent system paradigm[END_REF] designed a AGENT model for urban areas and road networks generalisation, which includes agent, constraint, conflict and operator. Figure 3.4 illustrates the different levels of agents and the constraints in the AGENT generalisation model. The engine allows a progressive generalisation of each agent by means of a succession of operators chosen and validated by the agent itself. The agent behaviours are modelled with constraints and procedural knowledge. The AGENT model can be applied to the generalisation of hierarchically structured data like topographical urban data and categorical land use data.

In order to manage more efficiently the constraints between agents in rural areas, the AGENT model builds communication between agents, which is called CartACom model [START_REF] Duchêne | Automated map generalisation using communicating agents[END_REF][START_REF] Duchêne | The cartacom model: transforming cartographic features into communicating agents for cartographic generalisation[END_REF]. Because topographical data of rural areas have not obvious pyramidal organisation of the space, it is difficult to identify pertinent disjoint groups of objects. CartACom model focuses on the management of constraints shared by two micro-agent and transversal interactions between agents directly (Figure 3.5). The relational constraints are used to model a relation between two agents, which includes: legibility constraints, constraints of preservation, and constraints of geographic coherence. When a relation between two agents is constrained, it constrains the behaviour [START_REF] Duchêne | The cartacom model: transforming cartographic features into communicating agents for cartographic generalisation[END_REF] of both agents (Figure 3.6). The communication between agents is based on the Speech Acts theory that includes two steps: request of action and information transmission.

The GAEL model has been proposed by [START_REF] Gaffuri | Field deformation in an agent-based generalisation model: the gael model[END_REF], and aims at extending the capabilities of existing agent-based model to manage background themes like relief or land use. It uses several agents to satisfy generalisation problems of terrain model at sub-micro level. Two types of cartographic constraints are considered in the GAEL model: constraints of shape preservation internal to a field theme, and constraints that aim to preserve a relation between a foreground object and a part of a background field (object-field constraint). In the GAEL model, a field theme is decomposed into a constrained Delaunay triangulation, and the field's shape preservation constraints are expressed as Figure 3.7: GAEL model. [START_REF] Duchêne | Combining three multi-agent based generalisation models: Agent, cartacom and gael[END_REF] constraints on sub-parts of the triangulations called sub-micro objects: segments, triangles, points. For example, triangulation is modelled by a group of point agents, and each object-field constraint concerns a sub-micro object that is translated into forces on the point agents that compose it. Interactions between agents can be hierarchical or transversal. Field agents can trigger their point agents (hierarchical interaction), and point agents can directly trigger their neighbours (transversal interactions). [START_REF] Galanda | Automated polygon generalization in a multi agent system[END_REF] designed four spatial levels for polygon generalisation, which are map, group, polygon and line. This agent prototype handles generalisation in accordance with the generic levels of analysis through macro, meso and micro agents [START_REF] Ruas | The roles of meso objects for generalisation[END_REF]. The generalisation operations of map agents consider the whole polygon map. Group agents handle contextual generalisation, i.e. conflicts between polygon objects. Each polygon agent coordinates the generalisation of an area object. Line agents deal with generalisation problems of boundary polylines of a polygon object. In addition, life cycle of this agent includes constraints, measures, agents and plans as components. [START_REF] Galanda | Automated polygon generalization in a multi agent system[END_REF] models generalisation constraints in the MAS (Figure 3.8). Each constraint must hold a goal value, a measure, an evaluation method, a list of plans, an importance value and a priority value, in order to meet the requirements of agent-based generalisation [START_REF] Galanda | Automated polygon generalization in a multi agent system[END_REF]. The evaluation of a constraint determines the satisfaction of a constraint with respect to a certain object [START_REF] Galanda | Automated polygon generalization in a multi agent system[END_REF]. The goal value affects the generalisation results directly. On a global level, goal values are derived from generalisation purpose such as map application, map scale, limits of perception and so on [START_REF] Weibel | Constraint-based automated map generalization[END_REF]], while on a local level the definition of a constraint's goal value is influenced by an object's semantics [START_REF] Ruas | Oo-constraint modelling to automate urban generalization process[END_REF]]. In the evaluation methods, some state values are the results of evaluation to compare with the goal value, which is used to determine the satisfaction in the evaluation. For example, distance state value is a result of qualifying the minimum distance between objects to compare with the distance conflict threshold. The measure CHAPTER 3. A MULTI-AGENT SYSTEM FOR GENERALISATION The values and methods attached to a constraint and their interdependencies. [START_REF] Galanda | Automated polygon generalization in a multi agent system[END_REF] method detects the conflicts of objects and a goal value is a threshold that objects should respect in order to satisfy a certain constraint.

To sum up, the four models are suited for different kinds of situations that are present on topographic map. In which, AGENT, CartACom and GAEL can be considered in different levels (Figure 3.9): AGENT model is meso agent, CartACom model is considered as micro agent, and GAEL model is defined as submicro agent. AGENT model is best suited for generalising dense areas where density and non-overlapping constraints are prevalent and strong contextual elimination is required [START_REF] Galanda | Automated polygon generalization in a multi agent system[END_REF], such as in urban areas. Single objects and groups of objects are represented by meso and micro agents. But there is no communication between meso and micro agents. CartACom model is applied to low density areas like rural zones of topographical data. Through transversal interactions between agents, it represents single geographic objects. The benefit of CartACom model is to share constraints of two agents and to manage both concerned agents. But it only considers the micro level of agents. GAEL model is applied to terrain model. It considers transversal interactions between agents that represent points of geographic objects connected by a triangulation, and hierarchical interactions between these agents and agents that represent field geographical objects (e.g. relief or land use cover). Galanda's work uses three level of agents to generalise polygon. The life cycle of agents helps to organise all the components of agents in the generalisation process. But it also lacks of communication between agents. GAEL model is more related to the objectives of our project. The transversal and hierarchical interac-Figure 3.9: Relationship of AGENT, CartACom and GAEL. [START_REF] Gaffuri | Field deformation in an agent-based generalisation model: the gael model[END_REF] tions between agents can be used in our project. But, for our project, the levels of agents are not enough to consider different landforms that are defined in the nautical chart representation ontology. In order to control the whole generalisation process in the MAS, it is necessary to design a life cycle to manage all the components of MAS, which includes agents, constraints, conflicts and operations. The conflicts describe the geometric or visualisation problems of objects in the map. The constraints control the generalisation operations in the agents. Based on the conflicts and constraints, some plans should be prepared for generalisation by agents. In addition, our project needs communication between agents.

A Multi-Agent System for Nautical Chart Generalisation

Three kinds of cartographic objects (isobath, sounding and feature) are defined in the cartographic representation ontology, and generalisation constraints, evaluation and operations are defined in the generalisation process ontology. In order to translate the concepts from the ontologies into the MAS, different types of agent with their own behaviour must be defined. The life cycle should be organised to control the generalisation process. In addition, the evaluation methods and possible plans will be introduced in this section.

Structure of the Multi-Agent System

A generalisation should take into account all information for each decision, such as generalisation constraints for different objects (Section 2.2.3.2). Meanwhile, generalisation operations are performed on a single object or on a group of objects (Section 2.2.3.2). Thus, the concept of different objects (Section 2.2.3.1) developed for the nautical chart representation is appropriated for gen-eralisation of nautical chart. Following the ontology, features are objects composed of soundings and isobaths, which hold the knowledge about the bathymetry. Hence, in the MAS, feature agents with their own geometrical and semantic properties can be defined. These agents can control their isobath and sounding components in order to evaluate their environment and act on it. Meanwhile, the relationships between each feature should be considered in the generalisation. Feature tree helps to define the structure of the MAS. [START_REF] Guilbert | Multi-level representation of terrain features on a contour map[END_REF] defined a method to represent features at different levels in a hierarchy, which is called feature tree (Section 1.4.1). This method classifies all the features into eminences (peaks and ridges), depressions (pits and channels) and mixed features (a region obtained by merging several regions) at different levels of detail based on their spatial relationships. This method identifies features at the highest level of detail first and moves to lower levels by aggregating regions into larger features. The region is defined by a set of isobaths. Feature classification is based only on adjacency relationships from the region graph and on comparison of their heights. Because feature tree can be applied to terrain analysis and generalisation of a contour map by selecting the most relevant features according to the purpose of the map, this work uses feature tree to classify undersea features. The feature tree contains all the features and the relationships between them. Therefore, a upper level of agent can be defined to control relationship between each feature.

Feature plays a key role for representation in the nautical chart. In order to control the operations on features and handle the relationship between features, a feature-centred structure of MAS is designed. Depending on the cartographic representation ontology and feature tree, the MAS should have a hierarchy from top to bottom to control cartographic objects. A group of features is parent of features at top level. Because feature is composed of isobaths and soundings, it as parent of isobath and sounding at middle level. Isobath and sounding, which are basic element of nautical chart, will be defined at bottom level. Related to macro, meso and micro agents (Section 3.1), five types of agents are defined in the MAS for nautical chart generalisation (Table 3.1). Macro agent includes horizontal cluster agent and vertical cluster agent at top level, feature agent is meso agent in the second level, and isobath agent and sounding agent are micro agents at the lowest level. If necessary upper level agents build lower level agents at run time, for instance horizontal cluster agent can build feature agent. Also, upper level agents are enabled to specify the lower level agents' constraints, e.g. a horizontal cluster agent can tell a feature agent not to enlarge itself when it knows about a lack of space with neighbouring features.

Sounding and isobath agents are attached to individual cartographic objects. They deal with the generalisation of objects at the lowest level. Both are reactive agents, which only act upon request from a feature agent. They only have a local knowledge of their environment and rely on knowledge communicated by feature agents to perform their actions.

Feature agent is controlled by a cluster agent or several cluster agents, and is able to control the micro agents. Feature agent applies generalisation operations on a single feature and resolves conflicts inside a feature. For example, if a feature is too small to be displayed on a chart, a feature agent will decide the operation depending on constraints. As an additional example, if this feature is a pit, it will be deleted. Otherwise, if it is a peak, feature agent may choose enlargement and build it's child agents to deal with the cartographic object modelling the feature.

Cluster agent instantiates and controls a group of feature agents. As parent agent, a cluster agent is able to decide which constraint applies to the child agents according to an analysis of all its child agents. Two kinds of cluster agents are defined to analyse relationships between features. Depending on the feature tree structure, cluster agents have horizontal and vertical cluster agents.

Their main responsibilities are to control feature agents and maintain the structure of the feature tree.

• Horizontal cluster agent gathers a group of neighbouring features. It will evaluate relationship between them, for example the features B, C and D in red circle in figure 3.10;

• Vertical cluster agent evaluates relationships between a feature and its children and resolves hierarchical conflicts between features, e.g. features G, H, I and D in green circle in figure 3.10.

The whole process is developed in a top-down method based on feature tree (Figure 3.11). Because feature tree classifies all the features at different levels of detail based on their spatial relationships and defines a hierarchy of features from top to bottom, the whole process begins to evaluate the features at the top level of the feature tree. When the evaluations and operations at a top level are finished, the second level will be activated. The whole process ends when either all constraints for all features on the chart are satisfied or no plan to be tried.

Operating of the Multi-Agent System

Life Cycle of Each Agent Type

During the generalisation process, each agent goes through a series of states which form its life cycle. In order to exchange information and to request actions, agents have to communicate. Figure 3.12 is the sequence diagram in MAS, which shows communication of different levels. As mentioned in section 3.2.1, upper level agents should create and control lower level agents. The upper level agent should supervise the constraints of lower level agents, and provide suggestion of operations or plans to lower level agents. Each agent will decide its plans or operations. The cluster agents evaluate the relationships between features and decide which constraint applies to feature agents, in the same way the feature agents decide which constraint applies to micro agents. The whole generalisation process will flow from top to bottom levels of the feature tree, and the re-evaluation process will move from bottom to top levels of the feature tree (Figure 3.11). Based on the concepts of generalisation process ontology, there are two basic steps for an agent: evaluation and plan selection. Because this work uses a constraint-based approach to generalisation, the evaluation should evaluate conflicts between objects depending on the generalisation constraints that have been defined in section 2.2.3.2. Then, a lower level agent should select operations or methods and organise them as a plan to resolve the conflicts. During this process, the upper level agents will make a final decision after interaction with all the lower level agents. Figure 3.13 is an example of communication between a feature agent and a cluster agent. If a feature agent has area conflict as evaluation result and get enlargement and aggregation as operations, the solutions will be sent to cluster agent. The solution of feature agent only consider the constraints of this feature. Cluster agent should consider all feature agents that are supervised by this cluster agent in the environment. If there is distance conflict between feature agents, cluster agent will decide the feature agent can not be enlarged. Then, only aggregation will be return to feature agent as decision. At last, it is necessary to re-evaluate the results in order to resolve new conflicts that may be created by the plan. Each type of agent has its own constraints, evaluation methods detecting conflicts and operators performing generalisation actions.

Horizontal cluster agent is activated at the beginning of the whole generalisation process. It evaluates and resolves conflicts from top to bottom of whole feature tree. When the evaluation of top level is finished, the evaluation of the lower level begins. There are two steps in the horizontal cluster agent. The first step is the evaluation of conflicts between features that are in the same level in the feature tree. The second step is to create either vertical cluster agent or feature agent for feature having children or not in the feature tree. The conflicts between parent and children features should be resolved before brother conflicts. Therefore if the conflicting features have children, the vertical cluster agent will be built to evaluate conflicts between parent and children features firstly. Then, the vertical cluster agent will evaluate conflicts of parent and children feature and feature agent will evaluate conflicts of each feature. After evaluation, the agents will send results to the horizontal cluster agent. Based on the evaluation results that are sent from vertical cluster agent and feature agent, horizontal cluster agent will decide the plan to resolve distance conflicts. At last, the decision of the horizontal cluster agent will be sent back to the vertical cluster agent or feature agent. Figure 3.14 shows the life cycle of an horizontal cluster agent that includes communication between the horizontal cluster agent and the other agents. When all levels are evaluated, the cluster agent will have a re-evaluation process that is from bottom to top of feature tree. The lower level agents (e.g feature agent) end before upper level agents (e.g. cluster agent). The generalisation process ends when the lowest horizontal cluster agent terminates its life cycle.

Vertical cluster agent evaluates conflicts between parent and child features. Then, it will create feature agents. After vertical cluster agent receives evaluation results from feature agents, it will decide how to resolve distance conflict between parent and children. At last, it will reply message to feature agents and send message to horizontal cluster agent. Vertical cluster agent will resolve conflicts between parent feature and its fist level of children features. Figure 3.15 shows the life cycle of vertical cluster agent.

Feature agent evaluates feature conflicts and has a series of possible operations (Section 2.2.3.2). These evaluation results will be sent to cluster agent. The cluster agent should consider the conflicts between features and decide which operations can be used. Then, the horizontal cluster agent and vertical cluster agent should reply the message about the possible generalisation operations to feature agent. Depending on the message from cluster agent and evaluation results of feature agent, a generalisation plan will be proposed. Then, the related isobath or sounding agents will be created. When the generalisation results are satisfied, the lower level agents will report the modified results to upper level agents. Figure 3.16 summarises the life cycle of feature agent.

Isobath agent and sounding agent evaluate isobath and sounding respectively. The micro agents also should care about messages from parent agents and their own constraints. Based on the relationships between feature generalisation operations, isobath and sounding generalisation operations (Section 2.2.3.2), the micro agent will choose operators to resolve the conflicts. Figure 3.17 explains the life cycle of micro agent.

Evaluation of Constraints

This work defines algorithm for distance and area measures that have been defined in section 2.2.3.2. The process of evaluating constraints is of great relevance in agent-based approaches to nautical chart generalisation, since it is responsible for conflict detection and evaluation of results. The evaluation measures, which have been defined in the generalisation ontology, are used in the evaluation of agents. Cluster agents evaluate distances between features. In addition, area measure will be used to evaluate feature conflicts in meso agent. Horizontal cluster agent aims to evaluate distance from a feature to its brothers, and vertical cluster agent detects conflicts between a feature and its children. Hence, the distance measure is used in the horizontal and vertical cluster agent that consider the distance conflict (Section 2.2.3.2). Algorithm 1 is an evaluation method of horizontal cluster agent. The distanceState as output value describes distance conflicts between brother features. If distanceState is null, these features have not distance conflict. Otherwise, they have distance conflict. Algorithm 2 is an evaluation method of vertical cluster agent. The childrenState as output value to describe distance conflict between parent and children. If childrenState is null, they have not distance conflict. Otherwise, the parent feature has distance conflict with its children feature.

Algorithm 1 check distance conflict with brother features

INPUT: a level of features (F i ) in feature tree, legibility distance (the goal value) OUTPUT: distanceState for all features F 0 to

F i do Distance ← F i .distance(F 0 )
for brother feature

F 0 to F i do T emp ← F i .distance(F j ) if temp < Distance then Distance ← temp Brother ← F j end if end for if F i .distance(Brother) < legibility distance (the goal value) then F i .distanceState ← Brother else F i .distanceState ← N U LL

end if end for

In the feature agent, area measure is used to detect area conflict. Because the most important constraint is safety constraints that relates to types of features, and the second one is legibility that includes distance and area conflicts, the feature agent should evaluate the type and area of features. After a feature agent takes decisions in the plan, it sends the evaluation results to horizontal or vertical cluster agents. In which, operations have been connected with conflicts to make decisions (section 2.2.3.2). Algorithm 3 shows the evaluation methods in feature agent.

Generation of a Plan for Operation

After evaluating the environment, the agent knows which constraints are violated. Based on the situation described by the state component (e.g. distanceStat and operationState), the agent prepares different plans that are suggested by the generalisation constraints in order to propose solutions that can help to resolve conflicts that have been detected. Each plan is defined by one operation or by a sequence combining different generalisation operators and communication between agents.

The horizontal cluster agent sends evaluation results to vertical cluster agent or feature agent. It is necessary to consider all the constraints in MAS. Therefore, the final plan should consider the operations of tables 3.2 and 3.3 at same time. For example, if there is a distance conflict, the features lack of space and cannot be enlarged. When a feature has area conflict and distance conflict at the same time, different plans will be produced and the best decision should depends on the type of feature. Table 3.4 concludes possible plans for different constraints. MAS also needs to consider the types of the original feature and the conflicting feature, such as if two features have same type, they can be aggregated. The isobath and sounding are components of feature. Therefore, the operations of feature agent should operate on isobath or sounding for further generalisation. The plans of isobath and sounding agents are decided by the operations of feature agent (Section 2.2.3). For example, deformation of features involves isobath displacement, isobath smoothing and sounding selection. The agent will extract these knowledge from ontology during generalisation.

An Example of MAS Process

This section uses an example to explain the process of MAS for evaluate conflicts on a nautical chart. Figure 3.18a is an example of feature tree that has been constructed from nautical chart. And figure 3.18b is evaluation process in the MAS. The whole process will begin at the first level of feature tree and evaluate each level from top to bottom, which describes in the following steps:

1. The horizontal cluster agent should be activated at the beginning of the whole generalisation process. The conflicts between brother features (B, C, D) in figure 3.19a should be evaluated in this step. If there are distance conflicts, the process will go to the second step. in figure 3.20a) will be created. Or if the feature has not children feature, feature agent (as C in figure 3.20a) will be created. Then, the distance conflicts between parent and children features will be evaluated in the vertical cluster agent. At the same time, the area conflict will be evaluated in the feature agent (C). This process shows in figure 3.21. At last, the result of evaluation will sent to the horizontal cluster agent. 3. In the third step, the other feature agents (Figure 3.22a) will be created as children agents of vertical cluster agent in the step 2. They evaluate feature conflicts (Figure 3.22b). A series of possible operations will be produced. Also, the solutions will be proposed to their parent agents. After receiving all the solutions, the horizontal cluster agent will consider them together and make a final decision to resolve conflicts on a nautical chart. At last, isobath or sounding agents will be created.

4. The isobath and sounding agents receive final decision and operate on the cartographic objects to resolve conflicts (Figure 3.23).

Conclusion

This chapter describes a MAS model based on nautical chart representation ontology (Chapter 2) for undersea feature generalisation. At the beginning, the existing works are introduced. It 88

CHAPTER 3. A MULTI-AGENT SYSTEM FOR GENERALISATION
includes the basic theory of MAS and its application in generalisation. Four agent models of map generalisation are reviewed, AGENT is used in urban area, CartACom is used in rural zone, GAEL is applied to terrain model, and Galanda's model is used in polygon generalisation. CartoACom only considers one level of agents. AGENT has two level of agents, but there is not interaction between them. GAEL includes two levels of agents, and has transversal and hierarchical interactions between agents. Galanda defines three levels of agent in the model, but also lacks of interactions between agents.

Based on the existing works and nautical chart representation ontology, a framework of MAS for automatic nautical chart generalisation process is defined in this chapter. In order to consider relationships between cartographic objects, the different levels of agents are defined based on the objects (isobath, sounding and feature) that have been defined in the generalisation process ontology and the feature tree that represents features at different levels and maintains relationships between features. Additionally, a top-down method is designed to control the whole generalisation process based on feature tree. The evaluation will begin at the top level of feature tree and end at the bottom level. Horizontal cluster agent and vertical cluster agent are defined as macro agents, which are used to evaluate the relationships between each feature at transversal and hierarchical direction of feature tree respectively. Feature agents are defined as meso agents to detect feature conflicts.

The isobath agent and sounding agent are defined as micro agents. Meanwhile, a life cycle includes the sequence and communication of different agents. For the MAS, there are two main steps in the generalisation process: constraints evaluation and plan proposition. The importance and priority of constraints are used to decide the sequence of generalisation operations, which are related to constraint concept in the generalisation ontology. Depending on the results of evaluation, the agent can propose a plan that contains generalisation operations in order to lead to a generalisation solution.

In the following chapter 4, the MAS will be implemented for conflicts evaluation on a nautical chart with bathymetric data of real world.

Chapter 4

Implementation and Results I n order to implement the ontologies to identify undersea features from a nautical chart and extend to cartographic application,this work designs a system to connect the ontologies, the bathymetric database and the application platform. Ontologies were built in Protégé 4.2 and exported into a RDF file. The knowledge of the system is inferred from the ontology defined in chapter 2. This chapter will use bathymetric data from real world for undersea feature characterisation and evaluation conflicts on a nautical chart. In order to represent undersea feature, the bathymetric data should be managed in the database depend on the concepts and relationships in the ontologies. From conceptual design to logical design, a ontology database should be designed to manage ontologies and bathymetric data. The bathymetric database is a set of soundings and isobaths and infers knowledge from the submarine relief representation ontology (Section 2.2.2) that defines and classifies undersea features and from the cartographic representation ontology (Section 2.2.3) that represents features on a nautical chart. Knowledge of the generalisation process ontology is used in the cartographic application. All the ontologies are stored in the database and the application queries data from the database. The ontological model was then integrated in Virtuoso. Virtuoso offers a triplestore database that is a purpose-built database for the storage and retrieval of triples in RDF terminology in the form of subject-predicate-object expressions. The cartographic application platform has two parts: one is information system for undersea feature identification, the other is a MAS for evaluation conflicts of nautical chart. The cartographic application platform connects to the bathymetric database to retrieve data. This chapter introduces the system design based on knowledge of ontologies and tools. The design database service and platform are introduced in section 4.1. Then, the implementation and result of undersea features representation are introduced in section 4.2. Cartographic application that relates to generalisation is realised in section 4.3. At last, the results are analysed and section 4.4 concludes this chapter.

System Design

The whole system includes three parts: the ontologies, database and cartographic application platform (Figure 4.1). The ontologies include geographic and cartographic knowledge. All the ontologies and bathymetric data are stored in the database to support cartographic applications. The cartographic application platform is designed for undersea features characterisation and evaluation conflicts of nautical chart. The following sections introduce the detail of each part.

Triplestore Database

Both ADO and PDO ontologies were designed in Protégé 4.2. Figure 4.2 is an extract of the undersea feature ontology. In order to manage all the ontologies in the database service and use them in the system for undersea features representation and cartographic application, a Web Ontology Language (OWL) document was exported from Protégé 4.2. OWL is a Semantic Web language designed to represent rich and complex knowledge about things, groups of things, and relations between things. It is built on top of Resource Description Framework1 (RDF) that is a standard model for data interchange on the Web and written in XML. The namespace declaration of the RDF/XML syntax is displayed in Appendix B. RDF has features that facilitate data merging even if the underlying schemas differ, and it specifically supports the evolution of schemas over time without requiring all the data consumers to be changed. The RDF data model is similar to classic conceptual modelling approaches such as entity-relationship or class diagrams, as it is based upon the idea of making statements about resources in the form of subject-predicate-object expressions. These expressions are known as triples in RDF terminology. In this thesis, all the classes of ontologies are defined to represent concepts of undersea features, cartographic objects and generalisation components. An example of such a RDF description is proposed in figure 4.3, and the RDF/XML format of this example is presented in the listing 4.1. The Hill concept, defined in the IHO terminology, inherits from the HillFeature and the PointFeature concepts and describes a feature having a point tip. The HillFeature concept is a generalisation of different concepts which differ by the type of tip and their possible location. They are organised into a superclasssubclass hierarchy. For example, HillFeature is a subclass of PeakFeature, and a superclass of Hill. Also, the properties and attributes are defined to describe the relationships between classes and individuals, such as Hill isAtDepthLevel BasinLevel, as well as topological relationships, such as Hill isContainedBy Basin. A triplestore is designed to store and retrieve identities that are constructed from triplex collections of strings (sequences of letters). Triplestore is in coherence with the current emphasis on development of native stores since their performance are optimised for the storage and retrieval of triples. Unlike Relational Database Management Systems, which store data in relations and are queried using SQL, triplestores store information or knowledge and are queried via SPARQL. A triple being a data entity composed of subject-predicate-object, like apple is fruit. A key feature of many triplestores is the ability to do inference. As a Database Management System, triplestore offers the capacity to deal with concurrency, security, logging, recovery, and updates, in addition to loading and storing data. Listing 4.2 expresses some examples of ontologies in subject-predicateobject format, which is the same as the triplestore format for the storage of bathymetric data in this thesis. Predicates in this database connect data together (e.g. feature F has boundary isobath I) and data with concepts (e.g. isobath I is an instance of the isobath concept). The last two rows below line of listing 4.2 show some examples of bathymetric data in subject-predicate-object format.

In addition, OpenLink Virtuoso4 supports SPARQL is the standard query language for RDF and the semantic web, embedded into SQL for querying RDF data stored in Virtuoso's database. Virtuoso is a high performance object-relational SQL database. It can function as a web application server as well as a host for data-driven web services. Therefore, Virtuoso as a database service to store all the concepts and relationships of the ontology to form an ontology database. Moreover, Virtuoso is also used to store the bathymetric database (soundings, isobaths, undersea features) from which chart data are extracted. In the ontology database, RDF files can be imported to Virtuoso directly and stored in the form of subject-predicate-object expressions. Finally, the database server is connected to an existing generalisation platform which is developed in C++ using Qt and CGAL5 libraries.

Cartographic Application Platform

In the cartographic application platform, there are two components: one is the information system that was initially developed in C++ language and is extended for ontologies management in Java language, the other is the MAS for cartographic application that is developed in Java language. The information system part (Figure 4.5) relies on previous works from Guilbert [2013] for the identification of features where only isobaths are considered and isobath generalisation operations are implemented. This system has been extended. The first step of the extension is to extract all these features and add them in the bathymetric database. Features as well as their topological relationships obtained from the feature tree are defined. Second, all features are classified by computing their shape properties from the soundings and isobaths composing each feature. Relationships between isobaths and soundings are defined by a constrained Delaunay triangulation. In order to manage all the data and relationships in the database, the Jena6 API was used to read from and write to the RDF graph in the Java platform. Jena is an open source Semantic Web framework for Java. It provides an API to extract data from and write to RDF graphs. The graphs are represented as an abstract "model". The model can be sourced with data from files, databases, URLs or a combination of these. The model can also be queried through SPARQL. In addition, Java Native Interface (JNI)7 is used to connect Java (i.e. Jena) and C++. The JNI is a native programming interface. It allows Java code that runs inside a Java Virtual Machine (VM) to interoperate with applications and libraries written in other programming languages, such as C, C++, and assembly. Figure 4.6 shows an example of how JNI work with Java and C. In addition, Jade8 (Java Agent Development Framework) is used to implement multi-agent systems, which is a software framework fully implemented in Java language.

Once classification is done, the system evaluates feature conflicts which require generalisation. The evaluation of nautical chart is implemented in the MAS. This part is developed using Java Agent DEvelopment Framework (Jade). The Jade simplifies the implementation of multi-agent systems through a middle-ware that complies with the Foundation for Intelligent Physical Agents (FIPA) specifications and through a set of graphical tools that support the debugging and deployment phases. Besides the agent abstraction, JADE provides a simple yet powerful task execution and composition model, peer to peer agent communication based on the asynchronous message passing paradigm. Using Jade, this work develops a list of behaviours to build different parts of MAS. The ontology is used to infer for each feature which evaluation methods shall be applied and which constraints are evaluated. Composition relationships automatically trigger the evaluation of constraints on isobaths and soundings. For example, evaluating the distance between two features delineated by isobaths is done by evaluating the distance between the isobaths.

Using triplestore database and cartographic application system, undersea features can be identified from isobaths and soundings on the nautical chart. Then, the MAS evaluate conflicts of cartographic objects on the nautical chart. The following sections introduce a case study of implementation of undersea features representation and evaluation in the MAS.

Undersea Features Classification

The model was tested on a set of soundings provided by the French Hydrographic Office for a large scale map (1:12500) of a coastal area. The projection is Mercator and the coordinate system is WGS84. The area of study is the channel between the tip of Port Navalo and Kerpenhir at the entrance of the Gulf of Morbihan in France (Figure 4.7). Map dimensions are 128.5mm wide and 90.4mm long. Isobaths were extracted with a 1 metre vertical interval by interpolation (Figure 4.5). A first step before feature classification is their identification. On such a chart, cartographers and readers mostly make use of isobaths to delineate hazards and navigation routes. Therefore, features are characterised by one or several isobaths at the same depth marking their boundary [START_REF] Guilbert | Multi-level representation of terrain features on a contour map[END_REF]. The method extracts features based on depth variations between adjacent isobaths and yields a feature tree [START_REF] Guilbert | Multi-level representation of terrain features on a contour map[END_REF] (Section 1.4.1, Figure 1.11) providing topological relationships between features (adjacency and inclusion). Relationships between isobaths and soundings are defined by a constrained Delaunay triangulation. Figure 4.8 shows all the soundings that have been used in the identification of feature types. The triangulation of isobaths and soundings is done within the application developed in C++ with CGAL library. Soundings and isobaths inside each feature are triangulated to generate the feature surface and compute its shape properties in order to classify them. After classification, features and their properties are stored as triples in virtuoso. Only features that inherit from the prominence and depression concepts are classified as they are the only ones identified on the chart. To discriminate two given features, there are many relevant representative parameters for feature identification based on the submarine relief ontology. In order to calculate Tip Type, Relative Spatial Extent, Horizontal Profile of shape value (Section 2.2.2.3) for feature identification, the following parameters are designed in the system:

• The area criterion is mainly used to discriminate features in terms of size. This criteria has not been defined in the ontology. But the area is a criterion which is used to compute some other criteria. The area is defined by the areas of the triangles projected on the horizontal plan. This work uses three parameters to determine four levels of area: if there are less than 20000 triangles on faces area in total, the feature has small size like pit; if there are greater than 20000 and less than 1500000 triangles on faces area, the size of feature is medium like channel; if there are greater than 1500000 and less than 100000000 triangles on faces area, the size of feature is large like bank; if there are greater than 100000000 triangles on faces area, the feature is huge as a special case in this work.

• Distinguishing the tip types requires to know how the surface varies around the tip. If the tip is a point or a line, the surface drops suddenly around the tip while for other types, the variation is gentler and so a more or less big area around the tip can be identified. The flatness is characterised by a so-called continuous flat area value (CFA). CFA accounts for the largest flat region of a given feature, i.e. the triangulation's largest continuous surface containing only triangles whose slope is lower than a certain slope threshold (the value of this minimum slope was arbitrarily set at 1%, but can be changed). The CFA is calculated in four steps: first it extracts the list of faces that are inside the feature and whose slope is inferior to a chosen threshold; second, the algorithm browses the created list. At each face, a recursive function is applied, which defines a new largest CFA if the face is part of the largest CFA previously computed, otherwise it is useless; third, if a face defines a new largest CFA, its area is stored in the variable AREA. And AREA is stored in the variable AREAMAX (initialized to zero at the beginning of the algorithm); fourth, when all the faces have been browsed, the value AREAMAX is returned. This work uses three parameters of CFA to identify three levels of flat region: if the value of CFA is less than 0.2, the tip of feature should be a point or a line; when the value of CFA is less than 0.8 and greater than 0.2, the tip of feature might be a line or area; if the value of CFA is greater than 0.8, the feature has a big flat area like plane feature that is a special case in this work.

• The Relative Spatial Extent of the shape value in the submarine relief ontology to describe the body of a feature. It is defined by the ratio between the feature height and its spatial extent. Therefore, Relative Spatial Extent is computed by the squared height (or depth) of the feature over the area of the feature. The greater the value of Relative Spatial Extent, the smaller of feature. It uses three values to distinguish features: when the value is less than 0.0001, the feature is relatively large like a bank; when the value is greater than 0.0001 and less than 0.000625, the feature has a relatively medium size like ridge; if the value is greater than 0.000625, the feature is relatively small like peak.

• The Horizontal Profile (HP) describes the shape value and to point out if a feature is elongated or not. It is a basic criterion giving reliable results to discriminate features (e.g. the difference between channel and basin). To compute this criterion the coordinates of face of the spatial extent of the feature F (max x (F ), min x (F ), max y (F ), min y (F )) are identified.

HP = max{max x x -min x x, max y y -min y y} 2 area where area represents the feature area. Its value is from 0 to 1. 0 is not elongated, and 1 is elongated.

Shape properties are computed from the soundings and isobaths composing a feature. Base properties are computed from the boundary contours. The tip is defined by starting from the highest or deepest sounding and by adding neighbouring triangles to extract the largest possible horizontal surface. Figure 4.9 presents a set of classified features. The left of figure 4.9 shows the leaves of the feature tree (Section 1.4.1, Figure 1.11), i.e. the features which do not contain any other features. The right of figure 4.9 shows features at the top of the hierarchy. The hierarchy of feature concepts defined in the ADO is used as a decision tree to reach the highest level of precision. Seven types of feature (peak feature, reef, bank, shoal, pit, channel and basin feature) are identified and characterised (Table 4.1). The first four features are prominences and three of them are defined in the IHO terminology. The last three are depressions and are not in the terminology because in shallow areas, noticeable features are mainly features which represent a danger for navigation.

In figure 4.9 (left), the largest peak feature, shown on right of this area, is above the sea level.

A channel corresponds to an elongated depression. The largest one, shown on figure 4.9 right, indicates a navigation route. Others are indeed contained by the first one. In the channel area, the distance between isobaths is shorter than isobaths' distance of other regions and more features are contained. It clearly identify different regions at higher level of the hierarchy, but more details of features can be displayed at lower level of hierarchy. 4.2 shows the run time of the whole process. Because the platform uses C++ and Java to store and read data, it spends some time to connect the two parts. In general, display is faster than storage. The storage feature tree includes triangulation and identification of feature type. Depending on the data size of each level, the time is different. Mostly, higher level is slower than lower level. All concepts defined in the ontology have not been implemented yet.

Relationships between isobaths and soundings are defined by a constrained Delaunay triangulation. Features are only bounded by one or several isobaths that are identified. Due to the inherent vagueness of landforms, delineating undersea features with a crisp boundary is subjective however it corresponds to the representation that is given on the chart and provides a rigorous definition for shape properties. Further work can be done by representing features by one or several soundings (e.g. a seamount where only the summit is marked) or by dealing with plane features. In such cases, features are not represented on the chart with a crisp boundary and therefore vagueness has to be taken into account in the position and computation of geometric properties [START_REF] Bittner | Vagueness and the trade-off between the classification and delineation of geographic regions-an ontological analysis[END_REF].

As the level of complexity would increase greatly with the number of feature concepts involved, the Feature Tree 3s -9m /per level Feature Tree 2s -15s /per level decision tree may be pruned according to the type of chart (large or small scale, coastal or offshore navigation) in order to limit the number of features considered.

Implementation of the multi-agent system

The application platform was extended to integrate the multi-agent system for evaluate conflicts on a nautical chart. Figure 4.10 is an example of the software interface. The main window displays the bathymetry, here showing features coloured according to their types , and the information box shows statistical data (Figure 4.10a). In addition, a sub-window provides application to query details of evaluation results for each feature, which includes information of area conflict, distance conflict and generalisation operations (Figure 4.10b). The evaluation results are detailed in the following.

Conflicts are detected by the evaluation methods and can be characterised by the elements involved in the conflict, the violated constraint and the score describing the importance of the violation. The ontology is used to infer for each feature which evaluation methods shall be applied and which constraints are evaluated. Multi-agent systems detect conflicts and get generalisation plans based on the generalisation process ontology, which is developed in Java language. Based on life cycle and constraints of each agent, a list of behaviours run in a sequence. Each agent has an AgentID as an identification in the MAS, a state to record evaluation result (e.g. 0: has area conflict; 1: has not area conflict.) and an object (e.g. a group of features, a feature, isobath and sounding) as attributes.

Each agent has a method (Evaluation()) to evaluate conflicts, and a method Plan() decides its operation. At the same time, ReceiveMessage() is used to receive message from other agents. In addition, horizontal cluster agent, vertical cluster agent and feature class should create other agents and decide generalisation operations (Operation()) after receiving messages from feature agents. All of these methods are presented in Appendix C.1. During evaluation, distance and area conflicts are considered together in the MAS. Distance conflicts are evaluated in the macro agents, and area conflicts are evaluated in the meso agent. Both of them should have parameters to estimate the quality of evaluation. Different parameters might produce different generalisation plans.

Distance conflict

Depending on the generalisation process ontology, agents evaluate distance conflicts between ad-

Area conflict

The radius parameters of area conflict are 2 mm, 3 mm, and 4 mm for three different assessments as well. Table 4.5 shows the amount of leaves features that have area conflict. It is same with the results of distance conflict, the larger the radius parameter the more the conflict features. Figure 4.12 shows some examples of area conflict. In the red rectangle, there is an example of channel feature. Feature 247 is only detected at 4 mm of radius parameter. In the blue rectangle, feature 942 has been detected while radius parameter is 2 mm. When radius parameter is 3 mm, features 244 and 943 have area conflict. When radius parameter is 4 mm, features 941 and 939 have also area conflict.

Generalisation plan

The whole process of MAS takes about 7 minutes to evaluate conflicts and get generalisation plans, and each level takes from 15 seconds to 60 seconds. Distance and area conflicts are displayed on nautical chart. Also, different colors are relevant to the types of features. All the information concerning conflicts and generalisation plans can be queried. The same distance is used to define conflicts between adjacent and parent-child features. Considering all conflicts and constraints on features, generalisation operations can be decided. Getting generalisation plans is a complex process. It is not only consider all the conflicts, but also should be controlled by constraints. Table 4.6 lists generalisation operations of a series of features that have brothers conflict when the distance and radius parameters are 2 mm. Table 4.7 lists generalisation operations of all the leaves features that have parent and child conflicts when the distance and radius parameters are 2 mm. The columns of distance conflict are the information about conflicting feature. For example, features 365 and 366 have brothers distance conflict without parent and child distance conflict. Thus, the generalisation operation of them is deformation. Because reef is a kind of eminence feature that can not be deleted, the generalisation operation on feature 942, which has area conflict without distance conflict, is enlargement. Meanwhile, the generalisation operation on pit 1286 is selective omission. Some features have no generalisation operation, which is due to different reasons: one is the operations are performed by the other conflicting features; the other is that the type of conflict feature is different from the original feature and they have other conflicting features, so this feature cannot be modified at this stage. For instance, in the green rectangle of figure 4.11, feature 1321 as a basin feature, which is a kind of eminence feature, is difficult to deform without enough space.

Hence, considering complex constraints on feature 1321, MAS does not perform operations to it at this stage. After generalisation, new conflicts might exist. Re-evaluation process is necessary to detect new conflicts. In this work, because the implementation of the generalisation operations is not realised, re-evaluation process has not been implemented. In this work, all ontologies are built in the Protégé 4.2 platform and exported into a RDF file.

In order to manage knowledge and relationships that are defined in the ontologies, we used a triplestore database to store all the data and knowledge. Virtuoso offers a triplestore database that is a purpose-built database for the storage and retrieval of triples in RDF terminology in the form of subject-predicate-object expressions. Triplestore is beneficial to do inference, storage and access of RDF graphs. Because Virtuoso provides Jena API to extract data from and write to RDF graphs, this work develops a platform allowing ontology management using Java. Meanwhile, feature identification relies on previous work [START_REF] Guilbert | Multi-level representation of terrain features on a contour map[END_REF] that was initially developed in C++ language. This work combines the system and ontology management to implement nautical chart representation ontology. However, this method helps to construct Delaunay triangulation and manage ontologies respectively, it should consume time to connect C++ and Java platform. Using Jade in Java platform, MAS was developed to evaluate conflicts of nautical chart and get generalisation plans at last.

The system has been tested on real data extracted from a large scale map (1:12500) of a coastal area in France. A constrained Delaunay triangulation is built upon the isobaths and the soundings. Several parameters are used to calculate values of Tip Type, Relative Spatial Extent, Horizontal

Profile of shape properties (Section 2.2.2.3). In total, seven types of features are identified and represented. Rough area have many more small features that have various types and are difficult to identify, and smooth area have some large features. The cartographic application platform can detect conflicts and, by making use of the constraints, checks through a list of generalisation operators and selects those relevant for solving the conflicts. Generalisation plans are inferred directly from the generalisation process ontology. Three parameters (2 mm, 3 mm, and 4 mm) are tested to detect distance and area conflicts for three different assessments respectively. At the same time, the system gets generalisation operations on each conflicting feature. The benefit of MAS is that features can be modelled as autonomous agents which evaluate their environment and control isobaths and sounding agents at lower levels.

There are two main limitations in the implementation. Firstly, it is difficult to determine parameters for feature classification. Some geometric properties are used to identify undersea features, such as area, continued flat area (CFA), Relative Spatial Extent, and Horizontal Profile. Different values of parameters might lead to different characterisations of types of features. Secondly, the parameters of conflicts influence the results of evaluation and the generalisation plans. All of them should be tested several times to get more precise parameters for feature classification and get satisfactory results for nautical chart evaluation. However, this work tested some value of parameters, it is not enough and lack of an evaluation method for results. Lastly, generalisation operations need to be implemented so that the plans made from the evaluation can be performed.

Conclusion and Perspectives

T his thesis designed a nautical chart representation framework based on ontologies, which aims to perform undersea feature classification and organise the generalisation process. Related to the problems that were mentioned in the chapter Introduction, the ontologies are defined to organise geographic and cartographic information, and a multi-agent system is designed to control the whole generalisation process. The main achievement of this work is the integration of knowledge about submarine relief and nautical chart, and it defines concepts for generalisation, which help to control data reduction for various purposes and provide an automatic evaluation methods for cartographic generalisation.

The submarine relief ontology describes undersea features in the ADO. In the PDO, the cartographic representation ontology describes the components and the cartographic objects of nautical chart, and the generalisation process ontology formalises knowledge about generalisation. The is-a, is-partof and topological relationships are used to describe relationships between different concepts, such as simplification is a generalisation operation, basin is part of seafloor, and basin contains guyot. Based on the generalisation process ontology, a multi-agent system is designed to evaluate conflicts and get generalisation plans. Three levels of agents are designed, which refer to cartographic objects. The upper level of agents controls lower levels of agents. Each kinds of agent has a life cycle. The agents will interact with each other to make the final decision for generalisation. Finally, a prototype system were implemented on the bathymetric data from real world. A triplestore database was designed to manage ontologies and bathymetric data. A cartographic application platform is also designed. It includes an information system for undersea features identification and a multi-agent system for evaluating the conflicts and proposing a generalisation strategy. In the case study, seven types of features are identified and represented. Then, the cartographic application platform can detect conflicts and, by making use of the constraints, goes through a list of operations and selects those relevant for correction. This section intends to subsume and highlight the main contributions of this work as well as the perspectives gained in landforms description. The contributions and perspectives initiate an outlook on further improvements of the nautical chart representation framework and possible future research with respect to the automated generalisation of different kinds of map.

Contributions

This work has two main contributions: one is to define three ontologies for nautical chart representation; the other is to design a multi-agent system for nautical chart generalisation based on the ontologies.

The ontologies for nautical chart representation. This thesis defined three ontologies in the Phenomenological Domain Ontology (PDO) and Application Domain Ontology (ADO) (Chapter 2). One is the submarine relief ontology defined as a subject ontology in the application domain ontology to conceptualise knowledge about undersea features. This work is derived from the International Hydrographic Organization (IHO) terminology. In the other part, cartographic representation ontology and generalisation process ontology are defined as method ontologies in the phenomenological domain ontology to formalise cartographic knowledge and generalisation factors. The first achievement of the work is to enrich the knowledge stored in the bathymetric database by integrating the new concepts into the database schema. The second direction is to formalise the way features are represented on the chart to automatically identify which information should be preserved when generalising the chart. Currently, the generalisation process is mostly done manually by cartographers. Due to its specificities and safety requirement, generalisation as terrain generalisation approaches for topographic maps do not apply to nautical charts. Furthermore, existing techniques are mostly relevant to cartographic generalisation and visualisation requirements. Thus, they do not take into account information about the features and the meaning carried by the final map. The ontologies presented here can be used as a base to enrich the generalisation process.

In the ADO, an ontology provides a formal description of each undersea feature's characteristics according to their composition, morphometric class, shape values and depth level in section 2.2.2. The knowledge is built in a bottom-up approach from standards established by the IHO. Different indicators based on the geometric properties have been introduced to characterise the shape of underrsea feature. These are the shape type, the relative spatial extend and the vertical and horizontal profiles. According to composition relationship, a feature shape is described in three parts: tip, base and body. The relative spatial extend describes the ratio between the feature height and its spatial extent. The Horizontal Profile describes the ratio between the length and the width of the feature base. According to the slope and elevation of the feature with regard to its neighborhood, the Vertical Profile classifies undersea features into four types: eminence, depression, slope and horizontal plane. Meanwhile, the depth level associated to the is-part-of relationship describes the spatial and topological relationships of undersea features. The benefit of the hierarchical structure is that features can be described at different levels of granularity according to the application requirements. On the top of the IHO definitions, general concepts are added to provide a description at different granularities. As a domain ontology, it can be used not only for nautical chart production but also for other applications related to oceanography or navigation for example. A classification and characterisation of the IHO terminology are formalised according to the concepts in the submarine relief representation ontology.

In the PDO, the cartographic application ontology is defined in the representation domain to describes the different elements portrayed on the chart, either directly drawn (soundings, isobaths) or interpreted from other elements (critical lines, features) (Section 2.2.3.1). The main contribution of the cartographic representation ontology is to define each feature as a cartographic object on the nautical chart. Features being composed of soundings and isobaths, those concepts are also defined at two levels where concepts at feature level are composed of concepts at isobath and sounding level. Additionally, within the PDO, the generalisation process ontology (Section 2.2.3.2) introduces constraint, evaluation measure and operation concepts which describe how a generalised representation can be achieved. The classification of the generalisation constraints based on the concepts of solving conflicts restricted to legibility conflict (distance and area conflicts) and preservation (safety for navigation, position and shape, topological structure). Related to cartographic objects and application of nautical chart, generalisation constraints of nautical charts have been formalised into two types in generalisation process ontology: conflict is used to detect constraint violation during evaluation, preservation controls generalisation operations in order to maintain characteristics and relationships of cartographic objects during generalisation. Then, the generalisation operations are classified in the ontology based on cartographic objects as well. Meanwhile, the operations of features are composed by the operations of soundings and isobaths. Five groups of measures for evaluation are classified in the generalisation process ontology, including area, distance, density, shape and position measure. They are used to evaluate conflicts on a nautical chart. Lastly, the whole generalisation process is formalised based on the ontologies. The score resulting from the measures and the evaluation of the constraints will trigger the generalisation operations. The ontology gathers enough knowledge to design a generalisation strategy that is implemented. Multi-agent system for generalisation. A multi-agent system is applied to automatic nautical chart generalisation in chapter 3. The MAS uses the generalisation process ontology. A top-down method is designed to control the whole life cycle of the generalisation process based on feature tree. Meanwhile, a life cycle controls the sequence and communication of different agents in the whole generalisation process. The importance and priority of constraints are used to decide the sequence of evaluation, which are related to the constraint concept in the generalisation process ontology. This system can evaluate constraints on different objects, and get generalisation plans after consideration of environments and communication between each agent.

The contribution of MAS for generalisation is to define agents relevant to the objects (isobath, sounding and feature) that have been defined in the cartographic representation ontology. Based on the levels of MAS and feature tree, horizontal cluster agent and vertical cluster agent are defined as macro agent to control feature agent that is defined at a meso level. The horizontal cluster agent evaluates conflicts of brothers features at a same level. The vertical cluster agent evaluates a feature and its first level children. Because isobath and sounding are components of feature, isobath agent and sounding agent are defined as micro agent in the MAS.

Implementation. In order to realise automatic evaluate conflicts on a nautical chart and propose generalisation plan, this work design a triplestore database and a cartographic application platform. The database includes two parts: one is ontologies, the other is bathymetric data. The platform extended previous work for feature identification and used MAS and ontologies for automatic evaluation conflicts on the nautical chart. The system has been tested on real data extracted from a large scale map (1:12500) of a coastal area in France. Seven types of features are identified and represented, which are calculated through values of Tip Type, Relative Spatial Extent, Horizontal Profile of shape properties. The cartographic application platform can detect conflicts and, by making use of the constraints, checks through a list of generalisation operators and selects those relevant for solving the conflicts. Generalisation plans are inferred directly from the generalisation process ontology. Three parameters (2 mm, 3 mm, and 4 mm) are tested to detect distance and area conflicts for three different assessments respectively.

Perspectives

The work presented in this thesis integrates knowledge of undersea features, nautical chart and generalisation process. Then, the ontologies are applied to generalisation in the MAS. But further work can be done to improve the study in this thesis:

• Firstly, generalisation operations should be realised in the MAS. At this stage, we don't evaluate the quality of the generalisation plan. When generalisation operations are integrated and realised in the MAS, MAS can evaluate the quality of the generalisation plan and the results. Thus, it helps to propose more satisfied generalisation plan.

• Secondly, further works should provide more tests on feature identification and evaluation conflicts on the nautical chart. Currently, in spite of the parameters have been tested several values, this work lacks of an evaluation approach to validate the quality of the results. It is necessary to provides an evaluation approach to validate the results of the feature identification and the generalisation plan.

• Thirdly, more features can be identified in the system. The undersea features have been defined in the submarine relief ontology. But only seven types of features are detected in the system. Although critical line and morphometric area have been defined in the cartographic representation ontology, they are not identified in the system. In the future, the system should considers these concepts to detect many more features. In addition, the cartographic representation ontology should integrates much more knowledge of other objects in order to represent features.

• Fourthly, the benefit of MAS is that the entire system will not fail if a component in the system fails. But the flexibility of MAS leads to issue of system control, especially difficulty of interaction between agents at different levels. Therefore, this work is still limited to evaluate nautical chart and get satisfactory generalisation plans. In order to solve this problem, we can integrate other knowledge (e.g. parameters of conflicts) in the ontology. This way will not only simplify the process in the MAS, but also extend the MAS to other applications easily.

• Fifthly, at a more conceptual level, other nomenclatures and representations can be considered.

For instance, the IHO regularly updates its standards and a 3D representation may be considered. Such work may require the definition of a common ontology pattern that can be reused but also which would facilitate their integration. The geo-semantics issue can be considered in the integration of different nomenclatures.

• Sixthly, the scope of ontologies can be extended to other applications. Based on the framework of ontology (Section 2.2.1), the other information (e.g. navigation) on the chart can be included in the task ontology in ADO. Large partie basse en forme de selle, entre deux hauteurs d'une DORSALE ou entre deux élévations contigües.

SEACHANNEL(S) CHENAL(AUX)

A continuously sloping elongated discrete (or group of) depression(s) found in FANS or ABYSSAL PLAINS and customarily bordered by LEVEES on one or both sides.

Dépression discrète (ou groupe de dépressions) de forme allongée et à pente continue, que l'on trouve sur les C ÔNES ou les PLAINES ABYSSALES, habituellement bordée(s) de LEV ÉES sur un ou les deux côtés.

SEAMOUNT(S) MONT(S)

A discrete (or group of) large isolated elevation(s), greater than 1,000m in relief above the sea floor, characteristically of conical form.

Elévation discrète (ou groupe d'élévations ) de grandes dimensions, , isolée(s), d'une hauteur supérieure à 1000m audessus du fond et généralement de forme conique.

SHELF PLATE-FORME

A zone adjacent to a continent (or around an island) and extending from the low water line to a depth at which there is usually a marked increase of slope towards oceanic depths.

Zone adjacente à un continent (ou entourant une île) et s'étendant du niveau des basses mers jusqu'á la profondeur á laquelle on note habituellement une nette augmentation de la pente vers les grands fonds.

SHOAL(S) HAUT-FOND(S)

An isolated (or group of) offshore hazard(s) to surface navigation with substantially less clearance than the surrounding area and composed of unconsolidated material.

Accident(s) du fond constitué(s) de mat à c riau non consolidé et représentant un danger pour la navigation de surface en raison d'un brassiage inférieur à celui de la zone environnante. Egalement appelé(s) Basse(s).

SLOPE PENTE

The deepening sea floor out from the SHELF-EDGE to the upper limit of the CONTINEN-TAL RISE, or the point where there is a general decrease in steepness.

D.1 Introduction

La carte marine est un cas particulier de carte topographique utilisée pour la navigation. Elle reproduit les fonds marins, les zones dangereuses et les aides à la navigation, la topographie de la zone côtière et fournit des informations sur les marées et le chanp magnétique terrestre. La cartographie se divise en quatre parties: la collection et la sélection des données ; la généralisation des données et la construction de la carte ; la lecture de la carte ; et son interprétation. La généralisation est une étape fondamentale où les données sont sélectionnées en fonction de l'échelle de la carte, de son objectif et des limites graphiques. L'objectif principale de la carte marine est de garantir la sécurité de la navigation. Elle fournit une représentation schématique du fond marin, met en avant les dangers (récifs, hauts-fonds) et indiquent les chenaux de navigation. La représentation du fond marin obéit à des règles différentes puisque l'objectif n'est pas de représenter le terrain le plus fidèlement possible mais de mettre en avant les formes de relief qui sont pertinentes pour la navigation. La bathymétrie étant modélisée par les sondes et les isobathes, les formes de relief sont représentées par des groupes de sondes et d'isobathes qui sont sélectionnées par le cartographe. De ce point de vue, la généralisation automatique du fond requiert la classification des formes de relief lafin de sélectionner les formes. Pour l'instant, il n'y a pas de méthode qui permette d'identifier les formes et de les généraliser en fonction de leur sens.

L'objectif de cette thèse est d'organiser les connaissances géographiques et cartographiques contenues sur la carte. Une formalisation explicite des différents concepts nécessaires peut être obtenue par une ontologie. Une première étape est donc de définir une ontologie qui formaliserait la description des formes de relief d'un côté et une ontologie traitant de la représentation des formes sur la carte. Les contributions de cette thèse sont donc d'abord le développement d'une ontogie traitant de la définition des formes de relief et de leur représentation et généralisation sur la carte puis de définir un système multi-agent fondé sur les concepts de l'ontologie pour la sélecion automatique des formes de relief permettant de mettre en oeuvre les principe de l'ontologie.

D.2 Une ontologie pour la représentation des cartes marines

L'intégration des connaissances caractérisant les formes du relief sous-marin peut se faire á l'aide d'une ontologie. L'objectif de ce chapitre est de définir et de construire un cadre ontologique pour la caractérisation et la généralisation du relief sous-marin à deux niveaux. D'abord, une ontologie de domaine du relief sous-marin est présentée introduisant les différents concepts nécessaires à la classification des formes sous-marines. Ensuite une ontologie des formes représentées sur la carte est présentée qui inclut la représentation des formes à partir des sondes et des isobathes ainsi que le processus de généralisation. Les deux ontologies sont intégrées en une seule formalisant les éléments du fond marin et leur représentation.

D.2.1 Organisation de l'ontologie

Les deux ontologies appartiennent à deux univers différents et correspndent à deux niveaux diffŕents de représentation des connaissances. La première ontologie conceptualise les connaissances sur le relief sous-marin et appartient donc à l'univers concptuel. Elle se base sur la terminologie définie par l'Organisation Hydrographique Internationale (OHI). Les caractéristiques de chaque forme de relief y est décrite en termes de propriétés et d'associations. La deuxième ontologie appartient à l'univers représentatif et s'attache à décrire les concepts nćessaires pour représenter la bathymétrie sur la D.2. UNE ONTOLOGIE POUR LA REPR ÉSENTATION DES CARTES MARINES 127 carte marine. Cela inclut entre autres les éléments graphiques apparaissant sur la carte (sondes, isobathes) mais aussi les opérations de généralisation et les liens entre les formes de l'ontologie de domaine et leur représentation.

D.2.2 L'ontologie de domaine

L'OHI a publié une liste de 46 formes sous-marines définies en langage naturel. Les définitions sont vagues par nature et ne peuvent pas être utilisées directement en traitement de l'information. Elles doivent donc être formalisées et organisées en une ontologie de domaine. Les propriétés des formes sont organisées en classes (composition, forme géométrique) et en associations (méréologiques, topologiques) et l'ensemble des formes sous-marines est structurée en une hiérarchie de classes. Les concepts décrivant une forme du relief sous-marin sont

• la composition (le matériau),

• la profondeur définie en niveaux correspondant à la structure du fond marin en fonction de caractéristiques morphologiques et des types d'activités physiques,

• la classe morphométrique et Par conséquent, l'ensemble du processus de généralisation doi t être traité en plusieurs parties tout en examinant l'interaction entre ces parties. Afin d'utiliser les connaissances issues des ontologies et de fournir des solutions pour la généralisation automatique de carte nautique, la technologie SMA semble être une approche puissante et flexible pour être utilisée dans le contexte de généralisation. Toutefois, même si cette technologie a été utilisée pour la généralisation de carte dans différents contextes, il manque un cadre théorique de généralisation par SMA fondé sur les formes de relief, combinant à la fois les contraintes spécifiques et les opérations de généralisation à appliquer.

D.3.1 Classification des agents

Basé sur les travaux existants et sur la représentation des cartes marines par ontologie, un cadre théorique de SMA pour la généralisation automatique de carte marine a été mis en place. Le formalisme repose sur une approche dirigée par les formes de relief. Afin de modéliser les relations entre les objets cartographiques, différents niveaux d'agents sont définis en fonction i) des objets cartographiques (isobathe, sonde et forme de relief) qui ont été définis dans l'ontologie du processus de généralisation et ii) de l'arborescence des formes de relief (c.-à-d. le "feature tree") qui représente les formes de relief à différents niveaux de résolution et maintient les relations topologiques entre les formes de relief. Liés à la représentation macro, méso et micro des agents (cf. partie 3.1, page 66), cinq types d'agents sont définis dans le système multi-agents (tableau 3.1, p age 75).

Les agents sonde et isobathe sont attachés à des objets cartographiques individuels. Ils portent sur la généralisation des objets au plus bas niveau. Les deux sont des agents réactifs, qui agissent uniquement sur la demande d'un agent associé à une forme de relief. Ils ont uniquement une connaissance locale de leur environnement et s'appuient sur les connaissances communiquées par les agents forme de relief pour effectuer leurs actions.

L'agent forme de relief est contrôlé par un groupe d'agents ou plusieurs groupes d'agents, et est lui-même capable de contrôler les agents micro. Un agent forme de relief applique les opérations de généralisation sur une seule forme de relief et résout les conflits à l'intérieur d'une seule forme de relief. Par exemple, si une forme de relief est trop petite pour être affichée sur une carte, un agent forme de relief décidera de l'opération de généralisation en fonction des contraintes à respecter. A titre d'exemple, si cette forme de relief est une fosse, elle sera supprimée. En revanche, s'il s'agit d'une éminence, l'agent forme de relief peut choisir un élargissement de cette forme de relief et construire alors ses agents fils pour traiter les objets cartographiques modélisant cette forme de relief.

L'agent groupe instancie et contrôle un groupe d'agents forme de relief. Comme agent parent, un agent groupe est en mesure de décider des contraintes à appliquer aux agents fils, selon une analyse de l'ensemble de ses agents fils. Deux types d'agents groupe sont définis pour analyser les relations entre les entités. Selon la structure du "feature tree", les agents groupe sont classifiés en agent groupe horizontal et agent groupe vertical. Leurs principales responsabilités consistent à contrôler les agents forme de relief contenus dans le groupe et maintenir la cohérence de la structure arborescente (c.-à-d. du "feature tree").

• Un agent groupe horizontal rassemble un groupe de formes de relief voisines. Il permettra d'évaluer les relations entre elles, par exemple les relations entre les formes de relief B, C et D dans le cercle rouge de la figure 3.10 (page 75);

• Un agent groupe vertical permet d'évaluer les relations entre une forme de relief et ses enfants et résout les conflits hiérarchiques entre les formes de relief, par exemple les conflits entre les formes de relief G, H, I et D dans le cercle vert sur la figure 3.10 (page 75).

D.3.2 Interaction entre les agents

Une méthode descendante est conçue pour contrôler l'ensemble du processus de généralisation à partir du "feature tree". L'évaluation commence au plus haut niveau de l'arbre et se termine au niveau le plus bas. Les agents groupe horizontal et groupe vertical sont définis comme des agents macro, qui sont utilisés pour évaluer les relations entre chaque forme de relief dans les directions horizontale et verticale respectivement. Les agents forme de relief sont définis comme des agents méso pour détecter les conflits internes à une forme de relief. Les agents isobathe et sonde sont définis comme des agents micro. Les figures 3.14, 3.15, 3.16 et 3.17 Le processus d'évaluation des contraintes est d'une grande importance dans les approches à base d'agents pour la généralisation de carte nautique, car il est responsable de la détection des conflits et des stratégies à mettre en oeuvre afin de les résoudre. Les algorithmes mis en place pour les mesures de distance et de superficie résultent des mesures d'évaluation qui ont été définies dans l'ontologie de la généralisation (cf. partie 2.2.3.2, page 54). Ces algorithmes d'évaluation sont utilisés par les agents. Les agents groupe évaluent les distances entre les formes de relief. La mesure de superficie donnera une connaissance supplémentaire sur les agents méso en conflit. Un agent groupe horizontal vise à évaluer la distance entre une forme de relief et ses frères, et un agent groupe vertical détecte les conflits entre une forme de relief et ses enfants. L'algorithme 1 (page 82) est une méthode d'évaluation d'un agent groupe horizontal. La valeur de sortie distanceState décrit les conflits de distance entre les éléments frères. Si distanceState est nulle, les formes de relief ne sont pas en conflit. De la même façon, l'algorithme 2 est une méthode d'évaluation d'un agent groupe vertical. La valeur de sortie childrenState est utilisée pour décrire les conflits de distance pouvant apparaître entre une forme de relief "parent" et ses enfants. Si la valeur childrenState est nulle, alors il n'y a pas de conflit. Dans le cas contraire, la forme de relief a un conflit de distance avec au moins une des formes de relief "enfants".

D.4.1 Base de données

Les ontologies ont été construites à partir de la plate-forme Protégé 4.2 puis exportées dans un format RDF. Afin de gérer les données ainsi que les concepts et les relations qui sont définis dans les ontologies, nous avons utilisé une base de données de type "triple store". Dans le cadre de cette thèse, nous avons utilisé un serveur de base de données fédérateur, nommé Virtuoso, qui joue le rôle d'un méta système de données (DBMS) "Data Base Management Systems" et qui propose une manipulation transparente de plusieurs systèmes de base de données autonomes. Les bases de données ainsi constituées peuvent être géographiquement décentralisées et interconnectées par un réseau. La tâche de centralisation du système fédéré revient à Virtuoso qui permet ainsi une harmonisation des requêtes malgré le fait que le système soit constitué de plusieurs serveurs de bases de données totalement autonomes. Virtuoso est libre et permet de stocker divers formats de données (json, xml, svg, etc.) 4.9 présente un ensemble de formes de relief classifiées. La figure 4.9 de gauche identifie les feuilles du "feature tree" (partie 1.4.1, figure 1.11, page 28), c'est-à-dire les formes de relief qui ne contiennent pas d'autre forme de relief. La figure 4.9 de droite présente les formes de relief au sommet de la hiérarchie. La hiérarchie des concepts de forme de relief définis dans l'ADO est utilisée comme un arbre de décision pour atteindre le plus haut niveau de précision en termes de classification. Sept types de forme de relief ("peak feature", "reef", "bank", "shoal", "pit", "channel" et "basin feature") sont identifiés et caractérisés (cf. tableau 4.1, page 100). Les quatre premières formes de relief sont des éminences et trois d'entre elles sont définies dans la terminologie de l'OHI. Les trois dernières sont des dépressions et ne sont pas dans la terminologie parce que dans des zones peu profondes -les formes de relief définies dans la terminologie de l'OHI sont principalement les formes de relief qui représentent un danger pour la navigation. D'après les tests, on remarque généralement que les zones rug ueuses contiennent de nombreuses petites formes de relief de différents types qui sont difficiles à identifier. A l'inverse, les zones plates ont de larges formes de relief plus facilement identifiables.

La plate-forme d'applications cartographiques peut ensuite détecter les conflits en faisant usage des contraintes. A partir d'une liste d'opérateurs de généralisation, les opérateurs les plus pertinents pour la résolution des conflits sont sélectionnés. Les plans de généralisation sont alors directement déduits de l'ontologie modélisant le processus de généralisation. Il existe deux principales limites à cette mise en oeuvre. Tout d'abord, il est difficile de déterminer des paramètres pour la classification des formes de relief. Certaines propriétés géométriques ont été utilisées pour identifier les formes de relief sous-marines : "Area", "Continued Flat Area", "Relative Spatial Extent" et "Horizontal Profil". Différentes valeurs de paramètres peuvent conduire à différentes caractérisations de types de forme de relief. Deuxièmement, les paramètres liés à la détection des conflits influencent les résultats de l'évaluation et les plans de généralisation. Chacun d'entre eux doit être testé à plusieurs reprises pour obtenir des paramètres plus précis pour la D.5. CONCLUSION 135 classification et obtenir des résultats satisfaisants pour l'évaluation des cartes marines. Des tests supplémentaires pourraient affiner les résultats obtenus dans cette partie. Enfin, les opérations de généralisation doivent être implémentées de sorte que les plans mis en place à la su ite de l'évaluation puissent être effectués.

D.5 Conclusion

Une carte marine est un type de carte utilisé pour décrire la morphologie du fond marin et du littoral adjacent. Un de ses principaux objectifs est de garantir la sécurité de la navigation maritime. En conséquence, la construction d'une carte marine est contrainte par des règles très précises. Le cartographe doit choisir et mettre en évidence les formes du relief sous-marin en fonction de leur intérêt pour la navigation. Au sein d'un processus automatisé, le système doit être en mesure d'identifier et de classer ces formes de relief à partir du modèle de terrain.

Un relief sous-marin est une individuation subjective d'une partie du fond océanique. La reconnaissance de la morphologie du fond sous-marin est une tâche difficile, car les définitions des formes de relief reposent généralement sur une description qualitative et floue. Obtenir la reconnaissance automatique des formes de relief nécessite donc une définition formelle des propriétés des reliefs et de leur modélisation. Dans le domaine maritime, l'Organisation Hydrographique Internationale a publié une terminologie standard des noms des formes de relief sous-marines qui formalise un ensemble de définitions principalement pour des objectifs de communication. Cette terminologie a été utilisée ici comme point de départ pour la classification automatique des formes de relief sous-marines d'un modèle numérique de terrain.

Afin d'intégrer les connaissances sur le relief sous-marin et sa représentation sur une carte nautique, cette recherche vise à définir des ontologies du relief sous-marin et des cartes marines. Les ontologies sont ensuite utilisées à des fins de généralisation de carte marine. Nos travaux de recherche sont structurés en deux parties principales. Dans la première partie de la recherche, une ontologie est définie afin d'organiser la connaissance géographique et cartographique pour la représentation du relief sous-marin et la généralisation des cartes marines. Tout d'abord, une ontologie de domaine du relief sous-marin présente les différents concepts de formes de relief sous-marines avec leurs propriétés géométriques et topologiques. Cette ontologie est requise pour la classification des formes de relief. Deuxièmement, une ontologie de représentation est présentée, qui décrit la façon dont les entités bathymétriques sont représentées sur la carte. Troisièmement, une ontologie du proces sus de généralisation définit les contraintes et les opérations usitées pour la généralisation de carte marine. Dans la deuxième partie de la recherche, un processus de généralisation fondé sur l'ontologie est conçu en s'appuyant sur un système multi-agents. Quatre types d'agents (isobathe, sonde, forme de relief et groupe de formes de relief) sont définis pour gérer les objets cartographiques sur la carte. Un modèle de base de données a été généré à partir de l'ontologie. Les données bathymétriques et l'ontologie sont stockées dans une base de données de type "triple store", et sont

3. 10

 10 Example of horizontal cluster agent and vertical cluster agent. . . . . . . . . . . . . . 3.11 The flow chart of the whole generalisation process. . . . . . . . . . . . . . . . . . . .3.12 Sequence diagram of MAS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 An example of communication between feature agent and cluster agent in order to get final decision. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14 Life cycle of horizontal cluster agent. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.15 Life cycle of vertical cluster agent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.16 Life cycle of feature agent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.17 Life cycle of micro agent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.18 Feature tree (3.18a); MAS process (3.18b). . . . . . . . . . . . . . . . . . . . . . . . . 3.19 Feature tree (3.19a); MAS process (3.19b). . . . . . . . . . . . . . . . . . . . . . . . . 3.20 Feature tree (3.20a); MAS process (3.20b). . . . . . . . . . . . . . . . . . . . . . . . . 3.21 Evaluation of vertical cluster agent and feature agent. . . . . . . . . . . . . . . . . . 3.22 Feature tree (3.22a); MAS process (3.22b). . . . . . . . . . . . . . . . . . . . . . . . . 3.23 Feature tree (3.23a); MAS process (3.23b). . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Architecture of system. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Extract of the ADO in Protégé: the Hill concept. . . . . . . . . . . . . . . . . . . . . 4.3 Graph associated with the RDF/XML description of the Hill concept. . . . . . . . . 4.4 Result of SPARQL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Example of the information system. . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 2 :

 2 Figure 2: Map generalisation.

Contents 1 . 1

 11 Nautical Charts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Digital Terrain Models (DTM) . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Generalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.1 Generalisation Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.2 Generalisation of the Bathymetry . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.3 Model Generalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4 Landform Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.4.1 Landform Representation on DTM . . . . . . . . . . . . . . . . . . . . . . . 26 1.4.2 Landforms Representation on Qualitative Models . . . . . . . . . . . . . . . 29 1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Figure 1 . 1 :

 11 Figure 1.1: Example extracted from nautical chart No. 7400 published by the SHOM in 2008 (scale 1:22500).

Figure 1 . 2 :

 12 Figure 1.2: Digital terrain models.

Figure 1 . 3 :

 13 Figure 1.3: Example of multi-scale representation of RGS by quadtree[START_REF] Li | Digital terrain modeling: principles and methodology[END_REF].

CHAPTER 1 .Figure 1 . 4 :

 114 Figure 1.4: The sequence of three types of generalisation[START_REF] Weibel | Generalising spatial data and dealing with multiple representations[END_REF].

Figure 1 . 5 :

 15 Figure 1.5: Safety constraints [Guilbert and Lin, 2007a].

Figure 1 . 6 :

 16 Figure 1.6: Illustration of radius of influence in the sounding selection process.

Figure 1 .

 1 Figure 1.7: Model and cartographic generalisation[START_REF] João | Causes and consequences of map generalization[END_REF].

Figure 1 . 8 :

 18 Figure 1.8: The relationship between slope, wavelength, and relief: (a) their full relationship and (b) simplified diagram[START_REF] Li | Digital terrain modeling: principles and methodology[END_REF].

CHAPTER 1 .Figure 1 .

 11 Figure1.10: Contour tree corresponding to a set of closed contours. Branches with white nodes are peaks or pits. Nodes with several children are passes[START_REF] Guilbert | Multi-level representation of terrain features on a contour map[END_REF].

Figure 1 .

 1 Figure 1.11: Left: Region graph from contour map of figure1.10 with depression and eminence features at different levels (Black: depressions, Grey: eminences). Right: Feature tree extracted from the inter-region graph.[START_REF] Guilbert | Multi-level representation of terrain features on a contour map[END_REF].

Figure 1 .

 1 Figure 1.12: Eight line primitives describing different qualitative slope values[START_REF] Kulik | Linearized Terrain: Languages for Silhouette Representations[END_REF]].

Figure 2 . 1 :

 21 Figure 2.1: Mixing is-a and is-part-of relationships in ontology.

Figure 2 . 2 :

 22 Figure 2.2: Classification of ontology types according to formality and generality [Kavouras and Kokla, 2008].

Figure 2 . 3 :

 23 Figure 2.3: Relationships of different levels of ontologies[START_REF] Guarino | Semantic matching: Formal ontological distinctions for information organization, extraction, and integration[END_REF].

Figure 2 .

 2 Figure 2.4: The five universe paradigm[START_REF] Fonseca | Ontology-driven geographic information systems[END_REF].

Figure 2 .

 2 Figure 2.6: Operator ontology [Gould and Chaudhry, 2012].

Figure 2 .

 2 Figure 2.7: Spatial relations ontology [Touya et al., 2012].

Figure 2 .

 2 Figure 2.8: Relational constraint ontology[START_REF] Touya | Towards an ontology of spatial relations and relational constraints[END_REF].

Figure 2 .

 2 Figure 2.9: Phenomenological and application domain ontologies for bathymetric representation.

Figure 2 .

 2 Figure 2.10: Conceptual model of submarine relief using Perceptory.

CHAPTER 2 .

 2 Figure 2.11: Composition of undersea feature.

Figure 2 .

 2 Figure 2.12: Characterisation of the seafloor.

Figure 2 .

 2 Figure 2.13: Mereology and taxonomy between the different parts of seafloor.

Figure 2 .

 2 Figure 2.14: Relationship of undersea feature and shape value in submarine relief ontology.

Figure 2 .

 2 Figure 2.15: Point features: round peak (left) and sharp peak (right).

Figure 2 .

 2 Figure 2.16: Line tip type (a: top and bottom line; b: ring).

CHAPTER 2 .

 2 A NAUTICAL CHART REPRESENTATION FRAMEWORK BASED ON ONTOLOGIES

Figure 2 .

 2 Figure 2.17: Example of class diagram of undersea feature terms.

Figure 2 .

 2 Figure 2.18: Conceptual model of the seafloor representation.

Figure 2 .

 2 Figure 2.19: Classification of sounding.

2. 2 .Figure 2 .

 22 Figure 2.20: Example of isobaths.

Figure 2 .

 2 Figure 2.21: Classification of feature.

Figure 2 .

 2 Figure 2.23: Generalisation process ontology.

Figure 2 .

 2 Figure 2.24: Classification of generalisation constraints.

C 7 =

 7 {∀iǫI, if i.closed() ∧ ∄jǫI such as, Contain(i, j) = true then ∃sǫS, such as Contain(i, s) = true∧ ∃f ǫF, such as Contain(f, i) = true}, where Contain(o m , o n ) returns the true value if object o m contains object o n .

Figure 2 .

 2 Figure 2.25: Evaluation ontology.

Figure 2 .

 2 Figure 2.26: Classification of generalisation operations with their relationship.

  Figure 2.28 is an example of the evaluation, and figure 2.29 is an example of the generalisation operations.

Figure 2 .

 2 Figure 2.27: Relationships between conflicts and operations.

Figure 2 .

 2 Figure 2.28: An example of the evaluation applied to an eminence feature.

Figure 2 .

 2 Figure 2.29: An example of the generalisation operations applied to an eminence feature.

Contents 3 . 1

 31 Multi-Agent System (MAS) . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.1.1 Agent Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.1.2 Multi-Agent System (MAS) in Generalisation . . . . . . . . . . . . . . . . . 67 3.2 A Multi-Agent System for Nautical Chart Generalisation . . . . . . . . 73 3.2.1 Structure of the Multi-Agent System . . . . . . . . . . . . . . . . . . . . . . 73 3.2.2 Operating of the Multi-Agent System . . . . . . . . . . . . . . . . . . . . . 76 3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Figure 3 . 1 :

 31 Figure 3.1: Architecture of an agent.[START_REF] Harrie | Modelling the overall process of generalisation[END_REF]

Figure 3 . 2 :Figure 3 . 3 :

 3233 Figure 3.2: Typical structure of a multi-agent system.[START_REF] Wooldridge | An introduction to multiagent systems[END_REF]

Figure 3 . 4 :

 34 Figure 3.4: The AGENT generalisation model.[START_REF] Ruas | A prototype generalisation system based on the multiagent system paradigm[END_REF]

Figure 3 . 5 :

 35 Figure3.5: CartACom model.[START_REF] Duchêne | The cartacom model: transforming cartographic features into communicating agents for cartographic generalisation[END_REF]

Figure 3 .

 3 7(a) represents a class diagram of GAEL model.

  Figure 3.7(b) illustrates the object-field constraints connecting field agent and geographic agent at micro level as relational constraints.

Figure 3

 3 Figure 3.8: The values and methods attached to a constraint and their interdependencies.[START_REF] Galanda | Automated polygon generalization in a multi agent system[END_REF]

Figure 3 .

 3 Figure 3.10: Example of horizontal cluster agent and vertical cluster agent.

Figure 3 .

 3 Figure 3.11: The flow chart of the whole generalisation process.

Figure 3 .

 3 Figure 3.12: Sequence diagram of MAS.

Figure 3 .

 3 Figure 3.13: An example of communication between feature agent and cluster agent in order to get final decision.

Figure 3 .

 3 Figure 3.14: Life cycle of horizontal cluster agent.

Figure 3 .

 3 Figure 3.15: Life cycle of vertical cluster agent.

Figure 3 .

 3 Figure 3.16: Life cycle of feature agent.

Figure 3 .

 3 Figure 3.17: Life cycle of micro agent.

CHAPTER 3 .

 3 Figure 3.19: Feature tree (3.19a); MAS process (3.19b).

Figure 3 .

 3 Figure 3.20: Feature tree (3.20a); MAS process (3.20b).

Figure 3 .

 3 Figure 3.21: Evaluation of vertical cluster agent and feature agent.

Figure 3 .

 3 Figure 3.22: Feature tree (3.22a); MAS process (3.22b).

Figure 3 .

 3 Figure 3.23: Feature tree (3.23a); MAS process (3.23b).

Contents 4 . 1

 41 System Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.1.1 Triplestore Database . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.1.2 Cartographic Application Platform . . . . . . . . . . . . . . . . . . . . . . . 94 4.2 Undersea Features Classification . . . . . . . . . . . . . . . . . . . . . . . 96 4.3 Implementation of the multi-agent system . . . . . . . . . . . . . . . . . 101 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

Figure 4 . 1 :

 41 Figure 4.1: Architecture of system.

Figure 4 . 2 :

 42 Figure 4.2: Extract of the ADO in Protégé: the Hill concept.

<<<

  !--http://www.semanticweb.org/ontologies/2010/11/6/Ontology1291602400995.owl#Hill --> <owl:Class rdf:about="&Ontology1291602400995;Hill"> <rdfs:subClassOf rdf:resource="&Ontology1291602400995;HillFeature"/> <rdfs:subClassOf rdf:resource="&Ontology1291602400995;PointFeature"/> <rdfs:subClassOf> <owl:Restriction> <owl:onProperty rdf:resource="&Ontology1291602400995;isAtDepthLevel"/> <owl:someValuesFrom rdf:resource="&Ontology1291602400995;BasinLevel"/> </owl:Restriction> 10 rdf:resource="&Ontology1291602400995;isContainedBy"/> <owl:someValuesFrom rdf:resource="&Ontology1291602400995;Basin"/> rdf:resource="&Ontology1291602400995;hasSummit"/> <owl:allValuesFrom rdf:resource="&Ontology1291602400995;Point"/> </owl:Restriction> </rdfs:subClassOf> <rdfs:comment rdf:datatype="&xsd;string">hillfeature</rdfs:comment> </owl:Class> Listing 4.1: An example in RDF/XML format of Hill concept.

Figure 4 . 3 :

 43 Figure 4.3: Graph associated with the RDF/XML description of the Hill concept.

Figure 4 .

 4 Figure 4.5: Example of the information system.

Figure 4 .

 4 Figure 4.6: An example of process occurring in JNI[START_REF] Liang | The Java Native Interface: Programmer's Guide and Specification[END_REF].

Figure 4 . 7 :

 47 Figure 4.7: Figure extracted from map No. 7107 published by the SHOM in 2008 (South latitude: 47 • 32 ′ 64 ′′ N ; North latitude: 47 • 33 ′ 25 ′′ N ; West longitude: 2 • 55 ′ 74 ′′ W ; East longitude: 2 • 54 ′ 46 ′′ W ). Permission to reproduce No. 318/2010. Do not use for navigation.

Figure 4 .

 4 Figure 4.8: Display of soundings. Spacing between soundings is 3mm. The sum of soundings is 5954.

Figure 4 . 9 :

 49 Figure 4.9: Results of undersea features characterization.

Figure 4 .

 4 Figure 4.10: Examples of conflict evaluations. Left displays features and conflict information. Right queries operations and conflicts of a feature.

4. 3 .Figure 4 .

 34 Figure 4.11: Examples of distance conflicts.

Figure 4 .

 4 Figure 4.12: Examples of area conflict.

  (a) Elévation (ou groupe d'élévations) longue(s) et étroite(s), à flancs escarpés et de complexité variable. (b) An isolated (or group of) elongated narrow elevation(s), often separating ocean BASINS. (b) Elévation (ou groupe d'élévations) longue(s) et étroite(s), séparant souvent des BASSINS océaniques. (c) The linked major mid-oceanic mountain systems of global extent. Also called MID-OCEANIC RIDGE. (c) Ensemble relié de systèmes médio-océaniques montagneux majeurs, s'étendant à tout un océan. RISE (Several meanings) MASSIF (plusieurs significations) (a) A broad elevation that rises gently and generally smoothly from the sea floor. (a) Vaste élévation offrant des pentes faibles et des formes généralement unies. (b) The linked major mid-oceanic mountain systems of global extent. Also called MID-OCEANIC RIDGE. (b) Ensemble relié de systèmes médioocéaniques montagneux majeurs s'étendant à tout un ocean. Egalement appelé DORSALE MEDIO-OCEANIQUE. SADDLE COL A broad pass or col, resembling in shape a riding saddle, in a RIDGE or between contiguous elevations.

  (pages 79, 80 et 81) montrent les cycles de vie des différents agents et la communication entre eux. Deux principales étapes du processus de généralisation composent le SMA : l'évaluation des contr aintes et la proposition d'un plan de généralisation.

  Figure extracted from map No. 7107 published by the SHOM in 2008 (South latitude: 47 • 32 ′ 64 ′′ N ; North latitude: 47 • 33 ′ 25 ′′ N ; West longitude: 2 • 55 ′ 74 ′′ W ; East longitude: 2 • 54 ′ 46 ′′ W ). Permission to reproduce No. 318/2010. Do not use for navigation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.8 Display of soundings. Spacing between soundings is 3mm. The sum of soundings is 5954. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.9 Results of undersea features characterization. . . . . . . . . . . . . . . . . . . . . . . 100 4.10 Examples of conflict evaluations. Left displays features and conflict information. Right queries operations and conflicts of a feature. . . . . . . . . . . . . . . . . . . . 102 4.11 Examples of distance conflicts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.12 Examples of area conflict. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

	xviii	LIST OF FIGURES
	4.7

. . . . . . . . . . . . . . . . . .

Table 1 .

 1 1: Different categories of constraints in generalisation[START_REF] Harrie | Modelling the overall process of generalisation[END_REF]

		Consider individual objects Consider groups of objects Consider the requirement
	Position	X(absolute)	X(relative)	Representation
	Topology		X	Representation
	Shape	X		Representation
	Structural		X	Representation
	Functional	X	X	Representation
	Legibility	X	X	Map readability

Table 3 .

 3 1: Organisation of agents at different levels.

	Level	Agent Name
	Macro Agent	Horizontal Cluster Agent Vertical Cluster Agent
	Meso Agent	Feature Agent
	Micro Agent	Isobath Agent Sounding Agent

Table 3 .

 3 2: Generalisation operations to solve distance and area conflict.

	Conflict	Operation	Conflict	Operation
		Deformation		Enlargement
	Distance conflict	Aggregation	Area conflict	Aggregation
		Selective omission		Selective omission

Table 3 .

 3 3: Generalisation operations applied according to the type of features.

	Feature Type	Operation	Feature Type	Operation
	Depression Feature	Deformation	Eminence Feature	Deformation Aggregation
		Selective omission		Enlargement
		Deformation		Deformation
	Pass Feature	Aggregation Enlargement	Plane Feature	Aggregation Enlargement
		Selective omission		Selective omission

Table 4 .

 4

	25	6	4	9	34	6	17	101

1: Undersea features (features defined in the IHO terminology are in bold). Peak feature Reef Bank Shoal Pit Channel Basin feature Total

Table

Table 4 .

 4 2: Time of data store (includes feature identification) and read from database.

	Storage		Display
	Object	Time	Object	Time
	Isobath	55s	Isobath	60s
	Sounding	40s	All feature leaves	9s

Table 4 .

 4 4 shows the total number of leaves features in different types, which have conflicts with adjacent features. The larger the distance parameters the more conflicts as well. In table 4.4, there are only one basin feature that has parent and children distance conflict with 2 mm of distance parameter, which is feature 1362. There is one more basin feature that has a conflict with 3 mm of distance parameter, which is feature 1321. In the figure4.11, compared to features 1362 in blue rectangle and 1321 in green rectangle, the legibility issue of feature 1362 is more serious than

Table 4 . 3 :

 43 According to different distance parameters, the total number of features that have parent-child distance conflict.

			Parent-child distance conflict
	Distance parameter (mm)	Feature Number Peak feature Reef Bank Shoal Pit Channel Basin feature	Total
	2	2	0	0	1	2	2	0	7
	3	2	0	0	1	2	2	1	8
	4	2	0	0	1	4	2	1	10
	the one of feature 1321. The brother conflict feature of feature 1362 is feature 1353, which is a
	peak feature. The conflicting feature adjacent to 1321 is feature 1304, which is a peak feature
	as well. Features 1321 and 1304 are enlarged and shown in the relevant blue and green rectangle
	respectively. Yellow rectangle of figure 4.11 shows another example of conflict between adjacent
	features. The distance conflict of features 365 and 366 has been detected with a parameter value
	of 2 mm.

Table 4 .

 4 4: According to different distance parameters, the total number of features that have brothers distance conflict.

			Brothers distance conflict
	Distance parameter (mm)	Feature Number Peak feature Reef Bank Shoal Pit Channel Basin feature	Total
	2	5	3	0	3	1	0	1	13
	3	5	3	0	3	1	0	2	14
	4	6	5	0	3	2	0	3	19

Table 4 .

 4 5: The total number of features that have area conflict, according to different values of radius parameters.

	Area conflict

Table 4 .

 4 6: Score of leaves features with brothers conflict (NO: has not conflict or operation; YES: has conflict).

	Feature ID	Feature Type	Distance Conflict Feature ID Feature Type	Area Conflict	Generalisation operation
	259	Peak feature	260	Peak feature	NO	Deformation
	261	Peak feature	262	Peak feature	NO	Deformation
	365	Reef	366	Reef	NO	Deformation
	372	Pit		NO	YES	Selective omission
	735	Shoal		NO	YES	Enlargement
	777	Shoal	778	Shoal	NO	Deformation

Table 4 .

 4 7: Score of leaves features with parent-child conflict (NO: has not conflict or operation; YES: has conflict).This chapter designs a database and a cartographic application platform to manage ontologies. Ontology database was built to access ontologies that were defined in chapter 2 and bathymetric data. Making use of submarine relief ontology (Section 2.2.2) in ADO and cartographic representation ontology (Section 2.2.3.1) in PDO, features are identified and represented in the information system. Based on generalisation process ontology (Section 2.2.3.2) in PDO, conflicts are detected by the evaluation methods and generalisation plans are produced in multi-agent systems.

	Feature ID	Feature Type	Distance Conflict Feature ID Feature Type	Area Conflict	Generalisation operation
	435	Reef	434	Peak feature	NO	NO
	391	Peak feature	534	Channel	NO	Deformation
	393	Channel	534	Channel	NO	Deformation
	394	Pit	534	Channel	NO	Deformation
	395	Channel	534	Channel	NO	NO
	705	Shoal	704	Peak feature	NO	NO
	811	Peak feature	810	Peak feature	NO	NO
	942	Reef		NO	YES	Enlargement
	1238	Pit	1240	Peak feature	NO	Deformation
	1362	Basin	1353	Peak feature	NO	NO
	1082	Pit	1377	Channel	YES	Selective omission
	1286	Pit		NO	YES	Selective omission
	4.4 Conclusion

•

  Lastly, the different representation methods can be considered, such as 3D representation of nautical chart. 3D visualisation is widely used in representation of terrain surface. The data structure, objects and other knowledge of 3D visualisation are different from that of 2D visualisation on the nautical chart. Therefore, a method ontology about 3D representation can be defined in PDO.

	Dépression (ou groupe de dépressions) relative-An isolated (or group of) elevation(s), smaller Elévation isolée (ou groupe d'élévations) plus An isolated (or group of) relatively narrow, deep ment étroite(s), profonde(s) et à flancs escarpés, than a SEAMOUNT. petite(s) qu'un MONT. depression(s) with steep sides, the bottom of dont le thalweg présente généralement une pente HOLE CUVETTE which generally deepens continuously, developed continue, située de fa à §on caractéristique sur A small local depression, often steep sided, in Dépression locale de faible étendue, souvent à characteristically on some continental SLOPES. certaines PENTES continentales. the sea floor. flancs escarpés.
	Appendix A CONTINENTAL MARGIN KNOLL(S)	MARGE CONTINENTALE D ÔME(S)
	Undersea Feature Terms and Definitions Zone séparant le continent émergé des An elevation somewhat smaller than a Elévation au profil arrondi, dont les dimen-The zone, generally consisting of SHELF, grands fonds océaniques ou d'une PLAINE SEAMOUNT and of rounded profile, char-sions sont quelque peu inférieures à celles d'un SLOPE and CONTINENTAL RISE, separat-ABYSSALE, constituée généralement d'une acteristically isolated or as a cluster on the sea MONT. Généralement isolée, elle peut aussi ing the continent from the deep sea floor or PLATE-FORME, d'une PENTE et d'un floor. faire partie d'un groupe. ABYSSAL PLAIN. Occasionally a TRENCH GLACIS CONTINENTAL. Parfois une FOSSE LEVEE LEV ÉE may be present in place of a CONTINENTAL peut exister à la place du GLACIS CONTI-A depositional natural embankment bordering a Talus sédimentaire naturel bordant un RISE. NENTAL. CANYON, VALLEY or SEACHANNEL on the CANYON, une VALL ÉE, ou un CHENAL
	CONTINENTAL RISE ocean floor.	GLACIS CONTINENTAL sur le fond océanique.
	ABYSSAL HILL(S) An isolated (or tract of) small elevation(s) on Déclivité de faible pente s'élevant des pro-COLLINE(S) ABYSSALE(S) Elévation isolée (ou groupe d'élévations) de PASSAGE (GAP) PASSAGE A gentle slope rising from the oceanic depths towards the foot of a continental SLOPE. fondeurs océaniques jusqu'au pied d'une PENTE continentale. Brèche étroite dans une DORSALE ou un MAS-A narrow break in a RIDGE or a RISE. SIF. Egalement appelé Goulet.
	the deep seafloor. DEEP(S) PEAK(S)	faible hauteur sur les fonds océaniques. GRAND-FOND(S) PIC(S)
	ABYSSAL PLAIN An extensive, flat, gently sloping or nearly level region at abyssal depths. APRON Une zone (ou un groupe de zones) localement PLAINE ABYSSALE Région de grande profondeur où le fond est sen-siblement plat, horizontal ou peu incliné. GLACIS An isolated (or group of) prominent elevation(s) Elévation (ou groupe délévations) An isolated (or group of) localized deep area(s) profonde(s), au sein d'une forme plus étendue either pointed or of a very limited extent across proéminente(s), à sommet pointu ou de within the confines of a larger feature, such as a comme une D ÉPRESSION, un BASSIN ou une the summit. trés faible extension. TROUGH, BASIN or TRENCH. FOSSE. PINNACLE(S) AIGUILLE(S)
	Surface de faible pente, de genèse essentielle-ESCARPEMENT A discrete (or group of) high tower or spire-ESCARPMENT Rocher(s) ou bloc(s) de corail effilé(s), en forme A gently dipping surface, underlain primarily by sediment, at the base of any steeper SLOPE. ment sédimentaire, à la base d'une PENTE plus forte. ARCHIPELAGIC APRON GLACIS PERI-INSULAIRE A gentle SLOPE with a generally smooth sur-face of the sea floor, characteristically found Déclivité de faible PENTE généralement unie, que l'on trouve particulièrement autour de Déclivité de forme allongée, généralement shaped pillar(s) of rock, or coral, isolated or de colonne ou de pointe, isolé(s) ou surmontant An elongated, characteristically linear, steep linéaire et abrupte, séparant des zones horizon-cresting a summit. un sommet. slope separating horizontal or gently sloping sec-tales ou à faible pente, dans des zones situées en PLATEAU PLATEAU tors of the sea floor in non-SHELF areas. Also dehors d'une PLATE-FORME. Egalement ap-A flat or nearly flat elevation of considerable Elevation relativement plate et horizontale, abbreviated to SCARP. pelé Talus. areal extent, dropping off abruptly on one or de grande extension et présentant une pente
	around groups of islands or SEAMOUNTS. FAN (CONE) C ÔNE more sides.	groupement d'îles et de MONTS sous-marins. abrupte sur un ou plusieurs côtés.
	BANK(S) A relatively smooth, fan-like, depositional fea-REEF(S)	BANC(S) Elément sédimentaire de forme générale R ÉCIF(S)
	An isolated (or group of) elevation(s) of the sea floor, over which the depth of water is relatively shallow, but sufficient for safe surface naviga-tion. BASIN A depression, in the sea floor, more or less ture normally sloping away from the outer ter-mination of a CANYON or canyon system. conique, à faible pente, situé généralement au Elévation isolée (ou groupe d'éévations) au-dessus de laquelle (desquelles) la profondeur d'eau est relativement faible, mais ne présente pas de danger pour la navigation de surface. BASSIN Dépression de forme générale plus ou moins ar-voisinage du débouché inférieur d'un CANYON. GUYOT(S) GUYOT(S) MONT isolé (ou groupe de MONTS) de sommet Ensemble de roches ou autres matériaux solides, A mass (or group) of rock(s) or other indurated affleurant ou situées à très faible profondeur et material lying at or near the sea surface that pouvant représenter un danger pour la naviga-may constitute a hazard to surface navigation. tion de surface. An isolated (or group of) SEAMOUNT(S) hav-relativement horizontal et uni. Voir également RIDGE(S) (Several meanings) DORSALE(S) (plusieurs significations) ing a comparatively smooth flat top. MONT(S). (a) An isolated (or group of) elongated narrow
	equidimensional in plan and of variable extent. HILL(S) COLLINE(S) rondie et d'étendue variable. elevation(s) of varying complexity having steep
	CANYON(S) sides.		CANYON(S)

  'ontologie de la représentation est divisée en deux parties. Une première partie s'attache à formaliser les relations entre les différents éléments de la carte et introduit dans la représentation le concept de forme de relief composée par un ensemble de sondes et d'isobathes. Les sondes sont classées en sondes principales, sondes de profondeur limite et sondes de fond. Les isobathes sont des lignes polygonales qui connectent des points de même profondeur. Parmi les autres concepts viennent la carte qui contient les méta-données définissant le contexte (échelle, coordonnées) et les formes caractéristiques qui décrivent les éléments du fond qui ne sont pas des éléments cartographiques mais sont représent'ees sur la carte à partir de groupes de sondes et d'isobathes comme les lignes critiques et les formes de relief. Cette approche permet de définir les formes comme elles sont perçues sur la carte et de faire le lien entre les forme s représentées et les formes décrites dans l'ontologie de domaine.La seconde partie décrit les éléments du processus de généralisation que sont les contraintes, l'évaluation et les opérations. Ils correspondent à trois aspects du processus répondant aux questions quand, quoi et comment généraliser. Les contraintes sont de deux types: les contraintes de préservation contrôlant le processus en indiquant ce qui doit être conservé et les contraintes de conflit indiquant où les règles cartographiques ne sont pas respectées. Les contraintes sont définies à plusieurs niveaux pour les sondes, les isobathes et les formes de relief. Les formes de relief étant composées de sondes et d'isobathes, leurs contraintes peuvent aussi être décrites comme des compositions de contraintes sur les sondes et les isobathes.L'évaluation est l'ensemble des mesures appliquées aux objets cartographiques pour évaluer les contraintes. Elles peuvent retourner un résultat booléen su une contrainte est respectée ou pas ou retourner une valeur mesurant la violation d'une contrainte comme par exemple la distance entre deux isobathes trop proches ou l'aire d'une forme de relief trop petite. Là aussi, les évaluations peuvent s'appliquer aux sondes et aux isobathes et par composition aux formes de relief.Finalememnt, les opérateurs de généralisation sont appliqués pour résoudre les conflits mesurés. Les opérateurs sont définis pour chaque type d'objet. Par exemple, le seul opérateur applicable aux sondes est l'élimination. Les isobathes peuvent être supprimées, lissées, déplacées ou agrégées. Les formes de relief sont supprimées, élargies, déformées ou amalgamées. Les opérations sur les formes sont aussi obtenues par composition. Par exemple, une forme est supprimée en supprimant toutes les sondes et les isobathes qui la composent.Le processus de généralisation est formalisé en reliant les contraintes, les évaluations et les opérations entre elles. Chaque contrainte est liée à une ou plusieurs évaluations qui s'appliquent aux objets de la carte vérifiant si les contraintes sont respectées ou pas. Les opérateurs sont reliés aux contraintes qu'ils peuvent résoudre et aux types d'objet auxquels ils s'appliquent mais aussi aux mesures qui permettent de les contrôler.D.3 Système multi-agents pour la généralisation de données bathymétriquesLa généralisation automatique est un processus complexe qui doit tenir compte de diverses contraintes en lien avec la mise en place de différents opérateurs. Dans le chapitre 2, une ontologie sur la représentation des cartes marines a été définie pour la caractérisation du relief sous-marin et la généralisation de carte marine. L'ontologie définit et classe les objets cartographiques selon trois types : les sondes, les isobathes et les formes de relief. Selon les différentes contraintes, différentes opérations de généralisation sont affectées à ces types d'objets cartographiques afin de piloter l'ensemble du processus de généralisation par les formes de relief. Cependant, un cadre théorique doit être défini pour évaluer automatiquement les contraintes et décider quel opérateur à appliquer. En outre, la généralisation doit tenir compte des relations spatiales entre les objets cartographiques. D.3. SYST ÈME MULTI-AGENTS POUR LA G ÉN ÉRALISATION DE DONN ÉES BATHYM ÉTRIQUES 129

• le profil incluant le profil horizontal, c'est-à-dire l'empreinte de la forme à la base, le profil vertical, incluant la raideur de la pente, et le type d'extrémité (sommet ou fond pointu, plat ou linéaire).

Chaque forme définie par l'OHI correspond à une classe généralement située au bas de la hiérarchie.

Des formes nouvelles sont ajoutées par généralisation des concepts afin de fournir une classification à différents niveaux de granularité.

D.2.3 L'ontologie de la représentation

L

  D.3. SYST ÈME MULTI-AGENTS POUR LA G ÉN ÉRALISATION DE DONN ÉES BATHYM ÉTRIQUES 131 Pour un agent forme de relief, la mesure de superficie est utilisée pour détecter un conflit de zone. Parce que la contrainte de généralisation la plus importante est la contrainte de sécurité qui se rapporte aux types de forme de relief, et que la seconde est la contrainte de lisibilité qui inclut les conflits de distance et de superficie, un agent forme de relief doit évaluer le type et la superficie de la forme de relief. Après qu'un agent forme de relief ai pris des décisions, c.-à-d. a élaboré un plan de généralisation, il envoie les résultats de l'évaluation aux agents groupes horizontal et/ou vertical. La partie 2.2.3.2 (page 54) présente les opérations/décisions de généralisation afin de résoudre les conflits précédemment cités. qui les contient (partie 2.2.3, page 50). Par exemple, la déformation d'une forme de relief implique le déplacement et le lissage d'isobathes et la sélection de sondes. Au fil de la généralisation, chaque agent va donc extraire ses connaissances à partir de l'ontologie précédemment définie. Dans la partie suivante, le système multi-agents est mis en oeuvre pour l'évaluation des conflits et la génération de plan de généralisation. Les tests ont été réalisés avec des données bathymétriques du monde réel. D.4 Mise en oeuvre informatique et résultats Dans cette partie, nous présentons l'architecture sur laquelle est mise en oeuvre la plate-forme logicielle destinée à accueillir les applications cartographiques. L'ensemble du système est composé de trois parties : les ontologies, les bases de données et la plate-forme d'applications cartographiques (figure 4.1, page 90). Les ontologies conceptualisent les connaissances géographiques et cartographiques. Les concepts ontologiques et les données bathymétriques sont stockés dans une base de données afin de supporter les applications cartographiques. Pour les besoins de cette thèse, la plate-forme d'applications cartographiques est initialement dédiée à la caractérisation des formes de relief pour la cartographie marine. Cette plate-forme est ensuite étendue par l'intégration d'un système multi-agents permettant l'évaluation des conflits de formes de terrain à des fins de généralisation de carte marine. Les parties suivantes présentent plus en détail ces différents composants.

  et permet d'utiliser des techniques de requêtes basées sur les langages sql ou sparql. De nos jours, il peut facilement s'adapter au contexte spatial et est très performant en association avec d'autres serveurs spécialement dédiés à la gestion et au stockage d'informations spatiales. Virtuoso propose une base de données "triple store" qui est une base de données spécialement conçue pour le stockage et la récupération de triplets dans la terminologieD.4. MISE EN OEUVRE INFORMATIQUE ET R ÉSULTATS133RDF sous forme d'expression de type sujet-prédicat-objet. Les intérêts associés à ces bases de données sont de pouvoir bénéficier des outils associés au Web sémantique ou Web des données afin de faire de l'inférence, du stockage et des requêtes sur des graphes RDF.D.4.2 Plate-forme d'applications cartographiquesLa plate-forme d'applications cartographiques est fondée sur deux composants principaux. Le premier est le système d'information initialement développé en langage C++ et qui a été étendu pour la gestion des ontologies en langage Java. L'autre composant est le système multi-agents pour l'application cartographique qui est, lui aussi, développé en langage Java. La partie système d'information (figure4.5, page 95) s'appuie sur des travaux antérieursde Guilbert [2013] pour l'identification des formes de relief où seules les isobathes sont prises en compte et seules les opérations de généralisation sur ces isobathes sont mises en oeuvre. Ce système a donc été étendu. La première étape de l'extension consiste à extraire toutes les formes de relief relatives à une zone géographique et à les ajouter dans la base de données bathymétriques. Les formes de relief ainsi que leurs relations topologiques obtenues à partir du "feature tree" sont définies. Deuxièm ement, toutes les formes de relief sont classifiées en calculant leurs propriétés de forme à partir des sondes et des isobathes composant chaque forme de relief. Les relations entre les isobathes et les sondes sont définies à partir d'une triangulation de Delaunay contrainte. Afin de gérer toutes les données et les relations dans la base de données, l'API Jena a été utilisée pour lire et écrire dans un graphe RDF (cf. partie précédente). "Java Native Interface" (JNI) a été utilisée pour connecter les développements faits en Java (c.-à-d. Jena) et les développements faits en C++. JNI est une interface de programmation qui permet à du code Java, exécuté à partir d'une machine virtuelle Java (VM), d'interagir avec des applications et des bibliothèques écrites dans d'autres langages de programmation tels que C ou C ++. La figure4.6 illustre par un exemple la façon dont JNI fonctionne avec du code Java et C.Une fois la classification faite, le système évalue les conflits entre formes de relief et qui nécessitent alors une généralisation. L'évaluation de la carte marine est mise en oeuvre dans le SMA. Cette partie est développée en utilisant "Java Agent DEvelopment Framework" (JADE). JADE simplifie la mise en oeuvre de systèmes multi-agents à travers un middle-ware conforme aux spécifications de la "Foundation for Intelligent Physical Agents" (FIPA) et à travers un ensemble d'outils graphiques qui prennent en charge les phases de débogage et de développement. Par l'utilisation de JADE, nous avons développé une liste de comportements afin de construire les différentes parties du SMA. L'ontologie est utilisée pour associer à chaque forme de relief les méthodes d'évaluation qui doivent être appliquées et les contraintes qui doivent être évaluées. Les relations de composition déclenchent automatiquement l'évaluation des contraintes sur les isobathes et les sondes. A titre d'exemple , l'évaluation de la distance entre deux formes de relief définies par des isobathes est réalisée en évaluant la distance entre les isobathes de ces deux formes de relief.D.4.3 Cas d'étudeLa plate-forme d'applications cartographiques a été testée sur des données réelles extraites d'une carte à l'échelle 1 : 12500 couvrant une zone côtière en France (figures 4.7 et 4.8, pages 97 et 98). Une triangulation de Delaunay contrainte reposant sur les isobathes et les sondes a été initialement définie. Plusieurs paramètres sont ensuite utilisés pour calculer la valeur des propriétés relatives à la géométrie des formes de relief : Tip Type, Relative Spatial Extent et Horizontal Profile (cf. partie 2.2.2.3, page 47). La figure

  Trois valeurs (2 mm, 3 mm, et 4 mm) ont été testées pour détecter les conflits de distance (tableaux 4.3 et 4.4, pages 103 et 104) et de superficie (tableau 4.5, page 104). Dans le même temps, le système propose les opérations de généralisation sur chaque forme de relief en conflit. Les tableaux 4.6 (page 106) et 4.7 (page 106) présentent les opérations de généralisation proposées par le système dans notre cas d'étude. L'avantage du SMA est que les formes de relief p euvent être modélisées comme des agents autonomes qui évaluent leur environnement et contrôlent les agents isobathe et sonde au niveau inférieur.

http://data.ordnancesurvey.co.uk/ontology

http://www.ngdc.noaa.gov/gazetteer/

Hydrographic and Oceanographic Service of the French Navy

National Oceanic and Atmospheric Administration

Table 3.4: Generalisation plans for different conflicts and feature types.

http://www.w3.org/RDF/

PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>

http://virtuoso.openlinksw.com/

https://www.cgal.org/

http://jena.apache.org//

http://docs.oracle.com/javase/7/docs/technotes/guides/jni/

http://jade.tilab.com

Après évaluation de l'environnement, un agent a la connaissance que les contraintes de généralisation sont violées ou non. Sur la base de la situation décrite par les évaluations issues des méthodes distanceState et operationState, l'agent prépare différents plans, qui sont suggérés à partir des contraintes de généralisation, afin de proposer des solutions qui peuvent aider à résoudre les conflits qui ont été détectés. Chaque plan est défini par une seule opération ou par une séquence combinant différents opérateurs de généralisation. Plus précisément, un agent groupe horizontal envoie les résultats de l'évaluation à un agent groupe vertical ou aux agents forme de relief. De la même façon, un agent groupe vertical envoie les résultats de l'évaluation aux agents forme de relief. L'agent forme de relief choisit alors les opérations de généralisation à appliquer en fonction des conflits entre les formes de relief et la préservation des contraintes. Parce qu'il est nécessaire de préserver les relations entre les formes de relief et d'éviter de créer de nouveaux conflits entre les formes de relief, la décision des opérations de généralisation sera envoyée aux agents parents, c.-à-d. aux agents groupe horizontal et/ou groupe vertical. Ensuite, l'agent groupe vérifie les opérations de tous les agents forme de relief, et décide du plan qui sera finalement réalisé. Parce que la contrainte de sécurité est la contrainte la plus importante dans le processus de généralisation de carte nautique, la décision du plan doit tout d'abord tenir compte du type de forme de relief. Dans l'ontologie de généralisation, les opérations de généralisation ont été définies pour résoudre différents conflits (cf. tableau 3.2, page 84). En complément, différents types de forme de relief sont associés à des opérateurs de généralisation différents (cf. tableau 3.3, page 84).

Il est nécessaire de tenir compte de toutes les contraintes dans le SMA. Par conséquent, le plan final doit simultanément tenir compte des opérations des tables 3.2 et 3.3. A titre d'exemple, si il existe un conflit de distance, les formes de relief doivent être espacées et ne peuvent pas être agrandies. Lorsqu'une forme de relief possède des conflits de superficie et de distance en même temps, différents plans de généralisation seront produits et la meilleure décision dépendra du type de la forme de relief. Le tableau 3.4 (page 85) présente les différents plans possibles pour différentes contraintes. Le SMA doit également tenir compte -en plus du type de l'entité d'origine -du type de la forme de relief en conflit, de façon à ce que si deux formes de relief ont le même type alors elles peuvent être agrégées. Les isobathes et les sondes sont des composants de forme de relief. Par conséquent, les opérations sur les formes de relief doivent opére r sur les isobathes et les sondes. Les plans de généralisation des agents isobathe et sonde sont décidés par les opérations de l'agent forme de relief

Ontology1291602400995.owl#" > ]> <rdf:RDF xmlns="http://www.semanticweb.org/ontologies/2010/11/6/Ontology1291602400995.owl#" xml:base="http://www.semanticweb.org/ontologies/2010/11/6/Ontology1291602400995.owl" xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#" xmlns:swrl="http://www.w3.org/2003/11/swrl#" xmlns:protege="http://protege.stanford.edu/plugins/owl/protege#" xmlns:owl2xml="http://www.w3.org/2006/12/owl2-xml#" xmlns:xsp="http://www.owl-ontologies.com/2005/08/07/xsp.owl#" xmlns:Ontology1291602400995="http://www.semanticweb.org/ontologies/2010/11/6/ Ontology1291602400995.owl#" xmlns:owl="http://www.w3.org/2002/07/owl#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" xmlns:swrlb="http://www.w3.org/2003/11/swrlb#" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">

Also, the vertical cluster agent sends evaluation results to feature agent. In the feature agent, the generalisation operations will be selected according to the conflicts of features and preservation constraints. Because it is necessary to preserve relationship between features and avoid to produce many new conflicts between features, the decision of generalisation operations will be sent back to horizontal cluster agent or vertical cluster agent. After cluster agent checks operations of all feature agents, the final plan will be realised. Because safety constraint is the most important constraint in nautical chart generalisation, the decision of plan should consider the type of feature firstly. In the generalisation ontology, generalisation operations have been defined to resolve different conflicts (Table 3.2). In addition, different types of features have different operations (Table 3.3). Because the eminence feature cannot be removed, selective omission will not be used to resolve any conflicts of eminence feature. fsm. registerTransition ("B", "E", 0); fsm. registerTransition ("C", "E", 1); //fsm.registerTransition("E", "A", 0);//this is for re-evaluation after resolve conflicts, and E should be registerState() addBehaviour(fsm); connectées à un système d'information implémenté en Java et C++. Le système proposé classe automatiquement les formes de relief sous-marines extraites à partir de la bathymétrie, et évalue les contraintes cartographiques. Dans un premier temps, les propriétés géométriques décrivant une forme de relief sont calculées à partir des sondes et des isobathes et sont utilisées pour la classification des form es de relief. Ensuite, les conflits de distance et de superficie sont évalués dans le SMA et des plans de généralisation sont proposés au cartographe. Des tests ont été réalisés avec des données bathymétriques du monde réel montrant ainsi l'intérêt de la recherche dans le domaine de la cartographie nautique.

Cependant des travaux supplémentaires peuvent être envisagés pour améliorer cette recherche :

• Tout d'abord, les opérations de généralisation doivent être implémentées dans le SMA. A ce stade, nous n'évaluons pas la qualité du plan de généralisation. Dans la mesure où les opérations de généralisation sont intégrées et réalisées dans le SMA, le système peut évaluer la qualité du plan de généralisation et les résultats de généralisation. Ainsi, il pourrait permettre de proposer plusieurs plans de généralisation dans le cas de résultats non satisfaisants.

• Deuxièmement, davantage de tests sur l'identification des formes de relief et sur l'évaluation des conflits doivent être envisagés. Actuellement, malgré que les paramètres aient été testés avec plusieurs valeurs, un processus d'évaluation permettant de valider la qualité des résultats doit être mise en place. Il est nécessaire de fournir une évaluation afin de valider les résultats de l'identification des formes de relief et du plan de généralisation.

• Troisièmement, plus de formes de relief sous-marines doivent être identifiées dans le système.

Les entités sous-marines ont été définies dans l'ontologie du relief sous-marin. Actuellement, seuls sept types de forme de relief sont détectés par le système. Bien que les concepts de ligne critique et de zone morphométrique soient définis dans l'ontologie de la représentation cartographique, ces concepts ne sont pas identifiés par le système. Dans l'avenir, le système devra considérer ces concepts afin de détecter plus de formes de relief. En complément, l'ontologie de la représentation cartographique devra intégrer plus de connaissances afin de mieux représenter les entités.

• Enfin, un des intérêts du SMA concerne la robustesse du système face à la faiblesse d'un des composants du système. Cependant la flexibilité du SMA conduit à envisager la mise en place d'un système de contrôle du système, en particulier pour gérer la difficulté des interactions entre agents à différents niveaux. Cette perspective vise non seulement à simplifier les processus et leurs interactions dans le SMA, mais aussi à étendre facilement le SMA proposé à d'autres applications.