Benoı ^t Eynard
email: benoit.eynard@utt.fr

Thomas Gallet

Pierre Nowak

Lionel Roucoules

UML based specifications of PDM product structure and workflow

Keywords: PDM, Object-oriented modelling, Product structure, Workflow, Aeronautics

The paper deals with the use of a UML approach for the specifications of a PDM system (product data management) implementation. A PDM system enables the management of the whole product data and related information about its entire lifecycle.

The main goal of this paper is to highlight the added value of using an object-oriented approach for modelling, specifying and implementing a PDM system on a business case study. The chosen object-oriented approach and the used UML diagrams for the modelling and integration of product, process, and resource data is detailed for a turboprop aircraft project.

Introduction

The turbo-prop engine market is increasingly competitive. ''Time to market'' is becoming one of the most important business and strategic key elements for product development and manufacturing. At the same time, customers want a more customized product with a higher security level. Companies therefore have to reduce design lead-time and provide a better-configured product with an enhanced level of quality and safety [START_REF] Pardessus | The multi-site extended enterprise concept in the aeronautical industry[END_REF][START_REF] Carratt | Concurrent aviation certification[END_REF]. These points represent especially high stakes in turbo-prop manufacturing as it is a niche market; in 2001, the sector total sales were equivalent to the sales of General Motors alone.

Brief PDM overview

A PDM (product data management) system manages and stores product design, manufacturing and support data [START_REF] Cimdata | Collaborative Product Definition management (cPDm): An Overview of a Collaborative Approach to Managing the Product Definition Lifecycle[END_REF][START_REF] Liu | A review of web-based product data management systems[END_REF]. Two main functionalities of such a system are: a product structure manager, which organizes and stores the whole product data. It manages the bills of www.elsevier.com/locate/compind Computers in Industry 55 (2004) 301-316 material and the various product configurations. It provides functionalities for versioning and linking the various parts and documents in the product structure. It also ensures the management of data status (available, frozen or obsolete); a workflow engine which, according to the product structure, sends the right available data at the right time to the right user. This functionality allows the implementation of ISO oriented processes in product development: from the preliminary design phase to the production engineering phase.

Many others functionalities are also currently available, such as integration with a mail server that notifies an event occurring on a given document (i.e. a check-in, check-out, promoting, etc.).

VPM-Chains project

At the end of the 1990s, Snecma Moteurs, one of the world leaders in turbo-prop manufacturing, has chosen to implement a new PDM system called VPM-Chains, mainly based on ENOVIA VPM from Dassault Syste `mes. Snecma Moteurs wants to have a huge customization of VPM functionalities in order to integrate the digital mock-up manager with a workflow functionality. Earlier, Snecma Moteurs was using a legacy PDM which did not fulfill the current and future needs of aircraft engine development. The company requires a single and secured storage of product data enabling an early access of production engineers to the design choices or allowing to share product data with its main contractors and suppliers.

As specified in [START_REF] Lafont | VPM-Chain design and industrialisation process software[END_REF], the main benefits of VPM-Chains implementation are:

Reducing development lead time and non-quality according to ISO oriented and predefined processes. Nowadays in aeronautics, this kind of ISO oriented process is required by the Federal Aviation Authority and Join Airworthiness Regulatory (JAR) before product certification [START_REF] Carratt | Inge ´nierie collaborative et gestion de donne ´es techniques en certification ae ´ronautique[END_REF]. Sharing the right updated data between the relevant users group regarding the product development process, e.g. between mechanical designers and computational fluid dynamic (CFD) designers to minimize their iterations; between engineering designers and production engineers to validate as soon as possible the decision-making involving manufacturing process specifications, etc. Enhancing reactivity and customer supports with a high level of traceability and an efficient product configuration management during the whole development cycle.

Research objectives

This paper aims at highlighting the added value of a UML approach [START_REF]The Unified Modeling Language, Release 1.1[END_REF][START_REF] Booch | The Unified Modelling Language User Guide[END_REF] for modelling and specifying the product structure [START_REF] Chao | Analysis of assembly through product configuration[END_REF][START_REF] Oh | Mapping product structures between CAD and PDM systems using UML[END_REF], the workflow [START_REF] Eynard | Aeronautics product development and certification workflow based on process modelling[END_REF][START_REF] Choi | An XML-based process definition language for integrated process management[END_REF] and the interoperability with CAE and scientific software [START_REF] Charles | Echange et gestion de donne ´es techniques en inge ´nierie me ´canique chez un motoriste avion[END_REF]. Considering its applications to enterprise modelling and business process reengineering [START_REF] Marshall | Enterprise Modeling with UML[END_REF], UML has been chosen for several reasons. First, it provides a fairly complete modelling notation for specifying the product breakdown structure (parts) with related product data (documents). Second, it provides an efficient language for modelling generic workflow with activities and transition criteria before their implementation in a workflow engine. Finally, UML enables to detail the overall class diagram of the VPM-Chains system and a framework for collaborative design with suppliers in an extended enterprise approach [START_REF] Jagdev | The extended enterprise -a context for manufacturing[END_REF][START_REF] Zhang | An Internet based STEP data exchange framework for virtual enterprises[END_REF].

Basically, the tasks of each involved person have been identified in a use case diagram (Fig. 1). The various kinds of functional user needs regarding VPM-Chains system have been clarified. This work has been carried out based on several interviews of design team members: mechanical designers, CFD designers, production engineers, project leader, design manager, etc. All these interviews have been analysed and provide a fairly good overview of the user needs and design project running based on data and process modelling. The method used for this work was based on a classical BPR approach [START_REF] Hammer | Re-engineering the corporation[END_REF].

One of our challenges was to explain and to communicate about this complex project and also to ascertain the various users' level of understanding. A good way to explain the functionalities and the running of a PDM system like this has been found in the use of UML [START_REF] Marshall | Enterprise Modeling with UML[END_REF][START_REF] Kim | The complementary use of IDEF and UML approaches[END_REF]. Its various views and diagrams enable the choice of a relevant way of explanation. These explanations are heavily dependent on what kind of information users want to share.

Product structure modelling and management

The product structure manages and stores all the instantiated data. It uses metadata for the data classification and configurable links between the metadata [START_REF] Eloranta | Improved project management throught improved document management[END_REF]. The product breakdown structure is based on a parts list (including: product, subassemblies, and basic components). Files are related to these parts via metadata links according to their types: CAD or MS-Office files. Regarding the instantiation level in VPM-Chains system, the product breakdown structure (Fig. 2) allows the management of bills of material and product configurations [START_REF] Rouibah | Change management in concurrent engineering from a parameter perspective[END_REF].

Product breakdown structure

Two types of breakdown viewpoints have been defined: a design breakdown, an assembly breakdown.

The main issue was that these two viewpoints of the product structure only partially provided a clear understanding of the full product breakdown structure. For example, the mechanical analysis and design of a high pressure compressor (HPC) is based on one specific sub-assembly. But a HPC is built on a spool that is a disk sub-assembly. Blades are also assembled on this spool. Regarding the assembly breakdown, the right disk has to be matched with the right blade. Then, no consistent links could be found between them in the product breakdown structure.

A joint product breakdown structure has been instantiated for an HPC made of three stages (Fig. 3). But new problems occurred: multi-instantiation of data shared between viewpoints (design, manufacturing, or assembly) could occur during implementation. As shown on Fig. 3, managing at the same time a viewpoint for design and one for manufacturing leads some parts to be instantiated twice, e.g. disks (1, 2 and 3) or blades (1, 2 and 3). It can be difficult to ensure consistency between data throughout the entire product lifecycle, from design to in-service phases of the turboprop. If a metadata is versioned in an instantiated part of the product breakdown, should this version update be notified to every user, even if they are working with the previous version? Do all the works in-progress have to be stopped or do the engineers are free to finish their structural analysis with the version previously in use?

Finally, a mixed modelling solution was chosen for the same instantiated HPC (Fig. 4): the top of the product breakdown (spool and stages) is common to every viewpoint (design, manufacturing, assembly), but each leaf (basic component: blade or disk) used in a lot of specific activities is dedicated to a single viewpoint. Then the whole stages of the HPC (generally, between four and twelve) with their corresponding disk and blade could be clearly modelled. This modelling solution avoids duplicating data: the shared data are integrated into the common part of the product breakdown. The instantiated product structure does not even have to be browsed when searching specific document related to a specific part used in a given activity. The query will be based on given part linking the document and the activity. The main goal is to allow the workflow engine to automatically retrieve the right data without ambiguity.

For example, on Fig. 5 the class diagram of the product structure provides not only static information. This diagram helps to understand the evolution rules based on methods and the quite complex links existing between metadata. The class diagram is also highlighting how the product is structured in the system and how it is used. The product breakdown will be composed of Part class, its sub-classes and Document class. The performer will be able to use these classes for carrying out his activity. The relevant data will be characterised with feature class and its sub-class.

Change of data status during their lifecycle

The status represents the current issue of a state change of a data or a document during its lifecycle. It provides maturity criteria for data transfer and persistency.

There are four possible statuses for a document:

''In progress'' means that the data is currently being modified by an activity (or that nothing has been done yet). ''Shared'' means that the data is mature enough to be used by the process as input for other activity. ''Released'' means that this data is frozen and will not be further modified in this configuration. ''Obsolete'' means that the data cannot be used as input for an activity. A comment usually explains why data is not usable.

The owner of the data is in charge of it and promotes or demotes the maturity level.

The state diagram of a document (Fig. 6) clearly shows the various levels and states of a document and the rules of evolution. The obsolete status means that the data is no longer used. It corresponds to a ''trashed'' status.

Workflow modelling and management

As above mentioned, the VPM-Chains system includes workflow functionality [START_REF] Fischer | The Workflow Handbook[END_REF]. The main goal is to build and run the same generic process with controlled data for each new product development cycle. This process ensures customers of ISO oriented quality and information traceability. It also allows the project team member to find every relevant input data of a given activity. For example, he could find the meshing and the boundary conditions required for a blade structural analysis.

Capture of workflow data and characteristics

During the first phase of the VPM-Chains project, interviews were carried out with experts, and the process was broken down into elementary and basic activities [START_REF] Scheer | Flexible industrial applications through model based workflows[END_REF][START_REF] Saikali | Flexibilite ´des workflows par l'approche objet: 2Flow: un framework pour workflows flexibles[END_REF] following two criteria: an activity is under the responsibility of one person, an activity lasts only a few days. Then all the business processes have been redefined. The relevant data (input or output process data) were identified for the whole process [START_REF] Gzara | Les patterns pour l'inge ´nierie des syste `mes d'information produit[END_REF][START_REF] Gzara | Product information systems engineering: an approach for building product models by Reuse of patterns[END_REF]. The most difficult job was to highlight which constraints were limiting activities. Some activities are ''push'' activities. This means that the end of such an activity launches the start of the following one. But this process-oriented control does not correspond to a real process behavior. The need to pull data in order to launch activity is required, mainly due to the concurrent engineering approach [START_REF] Sohlenius | Concurrent engineering[END_REF][START_REF] Prasad | Concurrent engineering fundamentals[END_REF]: rather than waiting the end of an activity before starting the following one, activities may start as soon as the input data are available. This data-oriented control is what the users needed, whereas today, only processoriented control is provided in VPM-Chains.

Generic process specification

The build-time is the VPM-Chains functionality for modelling design processes called templates. This means that UML-defined processes should be as generic as possible in order to ensure a huge level of reuse [START_REF] Liu | Workflow modeling for virtual processes: an order-preserving process view-approach[END_REF]. It includes generic sub-processes as specified in the class diagram of the process structure (Fig. 7). The process and the product structures contain the generic names of the relevant data (in the product structure, data is also identified by the name of the father's part). For example, a high pressure compressor consists of several stages of disks and blades. The design process of a turbo-prop stage is the same whatever the position of this stage in the compressor. Thus the same process can be instantiated for every stage of a turbo-prop (Fig. 8). If the process requires a data attribute called ''mass of the blade'' and the process associated to ''Stage X'' of the part is running, then the mass of the blade at stage X will be received.

The query on the right data is ensured by the link between a product and the considered process. This product is a sub-set of the product breakdown structure from which the query algorithm tries to retrieve the relevant data. The only way to associate this product with the process is to instantiate an empty activity in process. Thanks to this empty activity an engineering designer links the relevant data of product to be used in the process. Browsing the process the query algorithm is able to retrieve the associated product and relevant data. Then they could be taken into account for the next activity.

Classification of process and evolutions of the build time

Regarding design case, the process is strongly nonlinear. It corresponds to a collaborative workflow according to the basic classification of Leyman and Roller [START_REF] Leyman | Production Workflow[END_REF]. This means that it is not a predictable and structured workflow: choosing one activity over another is often an expert decision-making.

Currently, only basic sequencing functions between activities are supported by the build time, such as iteration, ''and'' diverging and creation of subprocesses. The writing of new specifications is currently underway:

The process has to control and monitor the product structure evolution. Users operations in the instantiated product structure are repetitive, complicated and boring, and therefore must be minimized. The data pull for controlling the start of activity should be enabled. This means to be able to launch an activity when all the required data are available. This allows a more complete concurrent engineer-ing organisation thanks to the activity start as soon as the data is available and not when the previous activity is completed. Because the sequence logic during the design process could not be predefined and predictable, optional tasks are required. Based on these optional tasks the engineering designers will be able to choose to right activities for carrying out their job. Then thanks to this mechanism of optional task a little bit of flexibility may be introduced in the workflow.

A good overview of these requirements can be found on Fig. 9 in the activity diagram of a process sample. This process describes a mechanical design of a blade using structural analysis with an optional task of CFD analysis in order to validate structural analysis output.

Integration of the product with the process and the resources based on a framework for collaborative work

In order to understand how the product is integrated with the process and the resources, the architecture of the VPM-Chains system is briefly summarized bellow. The user has three available applications:

Portal: the web client of the VPM server that supports the access to product data [START_REF] Rezayat | The Enterprise-Web portal for the lifecycle support[END_REF][START_REF] Huang | Web-based support for collaborative product design review[END_REF][START_REF] Xu | A web-enabled PDM system in a collaborative design environment[END_REF]. BuildTime: the module for modelling generic processes. RunTime: the workflow engine for running the instantiated processes.

Principles of the briefcase

When running an instantiated workflow in Run-Time, the system creates, at the expected time, an action in VPM for each workflow activity (Fig. 10). This action retrieves all the relevant data in the vault. After promoting his action, the engineering designer can download and read a package called ''the briefcase''. It contains the files corresponding to the relevant data and a procedure, which is an XML file that lists all the relevant data and their corresponding software release [START_REF] Burkett | Product data markup language: a new paradigm for product data exchange and integration[END_REF][START_REF] Yao | XML-based ISO9000 electronic document management system[END_REF]. A briefcase includes: elements of the process because actions are created according to a workflow, documents and files available in the product structure, metadata specifying the current implemented release of the CAD and CAE software to be used for issuing output data.

An action and its local instantiated briefcase provide the integration of the various dimensions of VPM-Chains system: product, process, and resource [START_REF] Lafont | VPM-Chain design and industrialisation process software[END_REF]. These dimensions are summarized in the class diagram of the system (Fig. 11). Product dimension is mainly composed of Part, Document, Turbo-prop, Module, and Detail part classes. Process dimension links Activity, Process, Action, and Performer classes.

Resource dimension is mainly composed of Part and Software part classes.

In Portal, a query can be done on the particular briefcase of the user computer. Portal reads the procedure in XML file and shows which documents should be availableintheactivity inputandoutput. Italso provides access to the attribute of the relevant data.

After carrying out his task, the engineering designer refreshes the relevant data attribute in his briefcase. He saves the modifications and checks the briefcase into the vault. Finally, he promotes his action and validates it.

A framework for collaborative work

This briefcase provides a framework enabling an easy transfer to a supplier. The current problem is how to maintain association with the context when the briefcase is out of the system [START_REF] Wang | CAD/CAM integrated system in collaborative development environment[END_REF]. Once the briefcase is downloaded, no more links to the VPM server are left. This problem is critical for CAD files. The mechanical engineer designs a part taking into account the constraints of the sub-assembly integrating the part. This means he needs to download a lot of data for his design task. It also means that a tool is required for synchronizing the changed and affected data. If a CAD model is modified, then the model has to be refreshed whether it is in the briefcase or not. All these questions remain unresolved for the time being.

Software interoperability

An XML based solution has been chosen for the interoperability of software with VPM when data are checked-out of the vault and downloaded on local computer. Linked software can read the XML procedure file and check the release of the referenced software and its own release. If the software identifies a difference, an alert message is sent to the user, but the work is not stopped.

Regarding specific software, the information are automatically retrieved by the procedure. For example, Patran, a finite element pre-processor, can find the value of the temperature field to be used and loads it in the current analysis session. It can also read other information such as the name of the project, etc.

Business case study

The aim of this section is to illustrate the use of the UML approach in an industrial project of PDM system deployment. This project is carried out with the help of an external business partner for specifying, customising, and implementing the requirements of Snecma Moteurs in VPM-Chains system. The several steps of such a project will be detailed and it will be underlined how UML can improve this work [START_REF] Kim | The complementary use of IDEF and UML approaches[END_REF].

Considering the viewpoint of the external business partner a PDM system deployment is always a new project. In such a project the past experiences and feedback of already achieved projects are difficult to take in account because PDM hugely affects the business processes and also has to integrate a lot of internal best practises. Because such a system deployment strongly influences the company competitiveness, it is quite difficult to get some benchmarks for implementing PDM systems.

Modelling processes and product data

First of all, PDM projects start with the clarification of the process and the data to be used in the system. Based on Snecma Moteurs experience, process and data modelling is quite new for such an industrial field. The use of formal languages for modelling and describing processes or data do not seem to be so common in IT companies. Fig. 12 shows a ''process'' as it was modelled by an external business partner. The figure does not contain a time axis, clear links between activities, and indication of task start or end. Neither sequence nor actor is specified.

Fig. 13 shows a data flow modelled by the same business partner. There are no explanations, no start or end of the flow, no time axis, and all the data are mixed. These two figures have been presented during the kick-off meetings of the project. Their reading and understanding are only possiblewith the help of thewriter. The model writer cannot always at the right place to explain his model. So we consider that the use of a common and formal language is required for a successful project.

The introduction of UML as a formal modelling notation enabled a global understanding and a common viewpoint of the project progress shared by all the team members. This required a training of the project team and a UML user support for carrying out the modelling often provided by software engineers or PDM implementers. Of course there are no guarantees of full understanding of diagrams because the modelling intent of UML users cannot be made explicit in the diagram semantics while diagrams are simple and clear. But UML seems to be a fairly good first step for sharing some structured ideas about clarifying business process and data. UML is considered as a structured notation system understandable without too many explanations. For many people, it could be used as a common language providing a shared point of view between users and PDM implementers. Even if there is not a single diagram of the whole system, there is always a set of diagrams which underlines a specific idea. The introduction of UML in the project has also improved the communication in the team. UML also natively supports main generic and instance concepts based PDM and workflow systems.

After modelling the process and the data, UML diagrams provide relevant tools for describing the link between the object of the system and the data of the company. This step is very useful because, if every links are clearly identified and specified, the implementation step will be easier and faster. It avoids to come back on process modelling and to ask clarifications to the users who are usually very busy with their daily tasks.

Clarifying needs and detailing specifications

The second field of a PDM-project where UML can prove to be useful is the clarification of needs. At this step of the project, the goal is to identify what will be the interactions between the users and the system. In other words, it means that the system implementers have to clearly identify the needs of the users and to share with them a common view (Fig. 1).

Use case diagrams can also be used to detail specifications. Splitting up the clarification of user needs and the system specifications is interesting because the second one has to fulfil the first one. After clarifying the needs, each one can be detailed into one or several specifications. UML also provides interesting tools for this step. Use case diagrams can be completed to show the links with functionality specifications (data upload and download) as described on Fig. 16.

Synthesis of business case study

UML has provided during the whole project a clear and efficient solution to communicate between team members who had heterogeneous views and understanding of PDM systems. Technically, the nine UML diagrams always provide useful viewpoints considering the ''to be'' implemented system. The class and object diagrams efficiently support product structure and workflow modelling. The activity diagrams have seemed to be a good way to specify, discuss, and establish common views.

Conclusion

Currently in its last phase of implementation, the VPM-Chains system provides a single and secured storage for CAD or CAE data linked with product structure and workflow. Like many PDM systems, the VPM-Chainssystemanditsstronglink with CAE software also ensures a high level of traceability of design activities and technical choices. Based on the VPM powerful mechanism, the product structure management is efficient regarding other PDM system. Data redundancy is avoided thanks to instantiable metadata.

The analysis of the process has highlighted the need for more flexible tools for the build time (workflow modelling) and run time (workflow instantiation) modules. Although the process is repetitive and iterative, control criteria are difficult to formulate. One of the system's main restrictions of use is its inability to support a real concurrent engineering organisation, specifically by controlling processes based on data flow. The last phase of implementation should normally solve these problems.

A PDM is a complex system which could be clearly defined and modelled using a tool such as the Unified Modelling Language. Various abstraction levels with the same kind of diagrams have been described: the needs of business case study, the global architecture, and the links between objects with class diagrams. The user interactions with the system have been modelled with use case diagrams and generic processes with activity diagrams. The system environment regarding the software links and the co-development work with suppliers have also been taken into account based on UML diagrams. To summarize, UML provides a relevant and efficient modelling notation that might limit misunderstanding problems for the various dimensions for specifying and implementing the product structure and workflow in a PDM system. Enterprise Modelling methodologies (e.g. ARIS, CIMOSA or GRAI) are useful for the global understanding and reengineering of company and its business processes but regarding the specification and implementation levels of dedicated software such as ERP, PDM, or SCM, UML is considered as an unquestionable supplementary modelling language.

Fig. 1 .

 1 Fig. 1. Use case diagram of PDM functionalities.

Fig. 2 .

 2 Fig. 2. Bill of material and product configuration manager of VPM-Chains system.

Fig. 3 .

 3 Fig. 3. Object diagram of the joint product breakdown.

Fig. 4 .

 4 Fig. 4. Object diagram of the mixed product breakdown.

Fig. 5 .

 5 Fig. 5. Class diagram of the product structure.

Fig. 6 .

 6 Fig. 6. State diagram of a document.

Fig. 7 .

 7 Fig. 7. Class diagram of a process structure.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Instantiated workflow in VPM-Chains RunTime.

Fig. 10 .

 10 Fig. 10. Action created by VPM server for each workflow activity.

Fig. 11 .

 11 Fig. 11. Summarized class diagram of the system.

Fig. 12 .

 12 Fig. 12. Process as modelled at the project beginning.

Fig. 14

 14 Fig. 14 represents the activity diagram detailing the issue in Fig. 12. The validation of the diagrams with all people involved in the activity is strongly suggested and also the clear specification of the transition criteria

Fig. 13 .

 13 Fig. 13. Data flow as modelled at the project beginning.

Fig. 14 .

 14 Fig. 14. UML based process modelling.

Fig. 15 .

 15 Fig. 15. UML based modelling of data lifecycle.

Fig. 16 .

 16 Fig. 16. Use case diagram of specifications.

B. Eynard et al. / Computers in Industry 55 (2004) 301-316

Powered by TCPDF (www.tcpdf.org)

Acknowledgement

The results presented in this paper have been developed within the VPM-Chains Project of Snecma Moteurs. The authors are most grateful to Snecma Moteurs for its support and technical contribution.

Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org)


Guillaume Touya

Jean-François Girres

ScaleMaster2.0: A ScaleMaster Extension to Monitor Automatic Multi-Scales Generalisations

Keywords: Generalisation, ScaleMaster, Multi-Representation Database

 allows formalising how to choose the features to map from the different datasets. The paper proposes an extension of the ScaleMaster model that drives automatic generalisation rather than guidelines for manual mapmaking. This ScaleMaster2.0 has been implemented and is tested for a use case with real data.

Introduction

The progress of geographic information capture and the emergence of volunteered geographic information allow more and more to command multiple datasets on the same territory [START_REF] Baella | ICC topographic databases: Design of a MRDB for data management optimization[END_REF]). These datasets have different level of detail or perspective. As a consequence, space may be represented differently in each dataset. The dataset variety makes mapmaking at different scales easier, relating a dataset level of detail to a visualisation scale. For instance, IGN (French national mapping agency) BDTOPO® can be mapped at the 1:15000 scale. However, making maps between the existing scales is necessary as it would greatly improve geoportals (no big gap between representations through zooming) and on-demand mapping (i.e. a default user may need a scale different than the pre-existing ones). Added to that, making maps that combine datasets is also necessary, even if the levels of detail (LoD) are not the same. For instance, a map for boat shuttles may require information from a topographic dataset in order to map the coast, and information from a bathymetric dataset to map the sea. Both issues require cartographic generalisation.

Therefore, a model is required to describe and produce smooth or continuous transitions between scales, using multiple data sources, in order to make legible generalised maps for a given non standard scale. To be integrated in mapmaking procedures, it should provide automatic generalisation whatever the scale of the map is. The ScaleMaster, proposed by [START_REF] Brewer | Framing guidelines for Multi-Scale map DesignUsing databases at multiple resolutions[END_REF], provides a model to describe such smooth transitions, but maps are produced interactively by a cartographer that reads the ScaleMaster. The paper proposes an extension of the ScaleMaster, called ScaleMaster2.0, which is readable by a generalisation system to provide automatic generalisation.

The next part details the problem of multi-scales generalisation and presents related work. The third part describes the proposed extension of the ScaleMaster model.

Then, experiments carried out on real data are presented and discussed. Finally, the fifth part draws some conclusions and explores further work.

Models for Multi-Scales Generalisations

MRDBs and Multi-Scales Generalisations

We call a Digital Landscape Model (DLM) a geographic dataset that has not been transformed for mapping purposes, and Digital Cartographic Model (DCM) a dataset that can be mapped at a given scale thanks to generalisation [START_REF] Meyer | Software developments for computer-assisted generalization[END_REF]). Producing maps is thus the creation of a DCM from a DLM, using generalisation. The aim of the paper is to carry out multi-scales generalisation, which is the creation of a DCM adapted to a target scale chosen by a user in a continuous range of scales, i.e. the user can pick whatever scale he wants. For instance, the system we aim at developing can automatically create either a 1:75k map or a 1:165k map from detailed DLMs. Multi-scales generalisation can be achieved by the use of a multiple representation database (Figure 1a), where the multiple representations of features correspond to different LoDs or scales. But multi-scales generalisation can also be achieved by the use of unrelated databases (Figure 1b) that contain complementary information that is generalised and mixed in the DCM (consistency between datasets should be achieved by another process). In both cases, the tricky problem is to produce DCM for in-between scales, which do not correspond to the LoDs of the DLMs.

Related Work

Producing maps at different scales with or without MRDB structures has been a research topic for several years, as generalisation techniques were improving. The first approach considers some well defined scales or LODs at which new DLMs or DCMs have to be derived from the existing DLMs. It is the standard approach of National Mapping Agencies that often produce one or two detailed DLMs and want to derive new products at smaller scales [START_REF] Trévisan | From DLM to multi representation DCM -modelling an application on buildings[END_REF]. Two strategies coexist in this approach, the star and the ladder architecture (Stoter 2005). For instance, the ladder approach is used in Catalonia [START_REF] Baella | ICC topographic databases: Design of a MRDB for data management optimization[END_REF]) and the star approach at the Ordnance Survey [START_REF] Mustière | Apprentissage supervisé pour la généralisation cartographique[END_REF]. [START_REF] Buttenfield | A comparison of star and ladder generalization strategies for intermediate scale processing of USGS national hydrography dataset[END_REF] compared both strategies for the generalisation of several hydrographical DLMs. The paper concludes that both strategies lead to similar results for river network simplification, when the scale change is not too significant (200K to 500K), but the star strategy may cause problems when the scale change is large (e.g. 200K to 2M). However, this approach does not prevent from problems when in-between scales are required. Otherwise, research tried to define models that enable smooth or continuous generalisation, i.e. data can be derived at any scale. The ScaleMaster model [START_REF] Brewer | Framing guidelines for Multi-Scale map DesignUsing databases at multiple resolutions[END_REF] allows the description of continuous rules to map a theme at a given scale in a timeline style where scale replaces time. The ScaleMaster model was used in a framework for building MRDBs, where it helped to balance workloads between all generalisation tasks [START_REF] Brewer | Mastering map scale: balancing workloads using display and geometry change in multi-scale mapping[END_REF]. It has also been used in a project for multi-scales generalisation of US toponyms [START_REF] Brewer | Combining varied federal data sources for multiscale map labeling of populated places and airports for the national map of the united states[END_REF]). The Scale-Master is not an interactive tool, but a formal way (Excel sheets) to record symbol changes for manual map design.

In order to produce maps with variable scales (e.g. large scale around user's location and small scale far from the user), Harrie et al. (2002) proposed continuous distortions of map features from large scale to small scale.

Finally, the vario-scale model [START_REF] Van Oosterom | Variable-scale topological data structures suitable for progressive data transfer: The GAP-face tree and GAP-edge forest[END_REF][START_REF] Van Oosterom | Towards a true vario-scale structure supporting smooth-zoom[END_REF]) is an attempt to structure features with continuous representations through scales. The vario-scale was successfully carried out on partition map features [START_REF] Meijers | Simultaneous & topologically-safe line simplification for a variable-scale planar partition[END_REF].

This literature provides different methods for multi-scale mapping but do not rely on the same hypotheses on initial data. We are interested in multi-scale mapping from existing DLMs at different resolution, so the ScaleMaster framework [START_REF] Brewer | Framing guidelines for Multi-Scale map DesignUsing databases at multiple resolutions[END_REF] seems the most appropriate starting point. The ScaleMaster has a Condition-Action view of generalisation [START_REF] Harrie | Modelling the overall process of generalisation[END_REF] whose limitations, compared to the Constraint-Based view, are discussed in section 4.4. However, multi-scale mapping is more at the 'Global Master [START_REF] Ruas | Strategies for automated generalization[END_REF] level, which is a Condition-Action scheme that encapsulates Constraint-Based generalisation procedures like AGENT [START_REF] Barrault | Integrating multi-agent, object-oriented, and algorithmic techniques for improved automated map generalisation[END_REF] or Least Squares (Harrie & Sarjakoski 2002[START_REF] Sester | Optimization approaches for generalization and data abstraction[END_REF]. Thus, the ScaleMaster framework can be a way to encapsulate Constraint-Based processes as well when necessary. The next part describes our proposed extension of the ScaleMaster that allows automatic derivation of DCMs at multiple intermediate scales.

A ScaleMaster Formalisation and Extension, the ScaleMas-

ter2.0

From ScaleMaster to Automatic Generalisation

The ScaleMaster framework is a very rich tool, but it is designed for manual mapmaking on standard GIS. In order to extend the framework to enable automatic multi-scale map production, some issues have to be overcome. First, the ScaleMaster is dedicated to standard symbolisation and generalisation operations that can be trig-gered from a GIS (Figure 3). But, map generalisation often requires complex processes (see an overview in Harrie & Weibel 2007) that may combine multiple operations. So, the extension has to handle both complex processes as standalone operations and the use of several processes for the generalisation of a given theme.

Then, complex processes but also simple generalisation algorithms require the definition of specific parameters to work properly and derive legible data at a given scale.

In order to be triggered automatically from the ScaleMaster, the processes to be used have to be described including the parameters and their values for each scale range (e.g. between 1:50k and 1:100k, use process1 with parameter1 = 12), which is not the case in the current ScaleMaster framework (Figure 3). Moreover, if several processes can be dedicated to the generalisation of a theme, a processing order (i.e. priorities) has to be included in the ScaleMaster extension. For instance, to generalise the built-up area parcels from 1:100k to 1:250k, first merge the adjacent features, then select the ones bigger than 10 km². If the processes are applied the other way round, the result is completely different (Figure 4). Finally, map generalisation is highly context dependant and initial data often has to be enriched with implicit patterns and structures to be properly generalised [START_REF] Mcmaster | Cartographic generalization in digital environment: A framework for implementation in a GIS[END_REF][START_REF] Mackaness | The importance of modelling pattern and structure in automated map generalisation[END_REF]. For instance, road network selection requires the identification of complex junctions like roundabouts. So, the ScaleMaster extension needs to handle the definition of required enrichment for some themes.

The ScaleMaster2.0 model

Considering the issues presented in the previous section, we propose an extension of the ScaleMaster framework that enables automatic multi-scale generalisation, the ScaleMaster2.0 model. It takes up the components of the ScaleMaster framework, enriching them to overcome the issues of automation (Figure 5). Like in the initial model, where different ScaleMasters were defined for topographic, road or geological maps, a ScaleMaster has a unique point of view, using the MRDB vocabulary. A ScaleMaster is defined on a global scale range and is composed of ScaleLines (in analogy to timelines).

A ScaleLine described the generalisation rules for one data theme across the scales.

In the proposed model, it is composed of scale intervals (e.g. 1:25k to 1:50k) where several ScaleMasterElement instances are defined, each one monitoring the generalisation of a source from which the theme is derived. For instance, the "river line" theme can be derived from river lines from a dataset and river areas from another, and each case is monitored by a different ScaleMasterElement.

The ScaleMasterElement is the key component of the model as it holds the generalisation rules. It is composed of required enrichments, an attribute based query that selects the appropriate data for the scale interval (described with the OGC Filter norm) and of several generalisation processes, described with the parameter values.

Priorities are set on the filter and on each process.

In order to allow the re-use of previously computed generalisation, the ScaleMas-ter2.0 model adds a MRDB n:m link between initial and generalised features.

Ontologies to Control the ScaleMaster2.0

ScaleLine instances of the ScaleMaster2.0 model describe the derivation rules to display a given theme on the map (e.g. road lines, building points or water areas). Thus, the theme of the ScaleLine is composed of a geographic concept (e.g. road) and a geometry type (e.g. line). In order to guarantee the interoperability of the ScaleMas-ter2.0, a geographic concepts ontology is required to control the geographic concept of the theme only with ontology concepts. Several ontologies describing geographic concepts exist and we used the one produced at IGN France, by [START_REF] Abadie | Schema matching based on attribute values and background ontology[END_REF].

Moreover, an ontology of generalisation algorithms and automatic processes is necessary, in order to fill the ScaleMaster elements for a given scale interval. Algorithms are implementations of one generalisation operation like displacement, simplification or aggregation. For instance, the well-known [START_REF] Douglas | Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[END_REF] algorithm that filters the vertices of a polyline, is an implementation of the 'filter' operation. Processes are complex computer programs that orchestrate the use of multiple operations. The Least Squares generalisation from (Harrie & Sarjakoski 2002) and CartACom [START_REF] Duchêne | Automated map generalisation using communicating agents[END_REF] are different examples of the processes that need to be listed in the ontology.

The ontology thus needs to rely on one of the existing generalisation operators taxonomies [START_REF] Mustière | Apprentissage supervisé pour la généralisation cartographique[END_REF][START_REF] Foerster | Towards a formal classification of generalization operators[END_REF][START_REF] Roth | A typology of operators for maintaining legible map designs at multiple scales[END_REF]. The taxonomy from Mustière ( 2001) is chosen as it is simple and the vocabulary used to name operators is not ambiguous (Figure 6). The ontology of algorithms and automatic processes is based on the operators' one.

Existing ontologies [START_REF] Gould | An ontological approach to on-demand mapping[END_REF][START_REF] Touya | CollaGen: Collaboration between automatic cartographic generalisation processes[END_REF] were used as a basis but the proposed one differs as it is not intended to be used the same way.

How to Automatically Process a ScaleMaster2.0

The aim of the ScaleMaster extension is to provide automatic generalisation for every scale within the ScaleMaster range. As a consequence the ScaleMaster2.0 needs an engine that interprets the information contained in a ScaleMaster2.0 and carry out automatic sequences of generalisation procedures. Themes and related ScaleLines are picked iteratively from top to bottom of the ScaleMaster. Then, the elements corresponding to generalisation scale are fetched and processed iteratively. For a given element, the processes and the attribute query are ordered by priority, while the required enrichments are carried out if it has not been done for a previous element (several processes may use the same enrichment). When enrichments are made, each process is parameterised and executed on the features described in the element. There is no risk of infinite loop as the number of elements by theme, and the number of processes by element, are finite, as defined by the user in the ScaleMaster.

Experiments

Model Implementation

To implement the ScaleMaster2.0, the CartAGen library (Renard et al. 2011), developed since 2009 by the generalisation team of the COGIT lab, is used. The availability of a large number of generalisation processes and the possibility to manage different databases in the same time justifies the use of this Java platform. The ScaleMas-ter2.0 implementation is Open Source as part of the GeOxygene project [START_REF] Bucher | GeOxygene: Built on top of theexpertness of the french NMA to host and share advanced GI science research results[END_REF].

To facilitate the parameterisation of the model, three XML interfaces are associated to the Java core: the ScaleMaster.xml, Parameters.xml, and Symbology.xml files, as illustrated in Figure 9. The ScaleMaster.xml file is the XML transcription of the ScaleMaster2.0. As presented in Figure 5, the operations are organised in attribute queries and generalisation processes, for a given scale interval in a ScaleLine. Attribute selection queries are formalised using OGC filters and generalisation processes are structured as a list of processes, involving a series of parameters. These operations are classified by priority order to facilitate the scheduling of the generalisation procedure. At the moment, the edition of these three XML interfaces is only available using classical text editors. Nevertheless, an interactive editor, as exposed in figure 10, is also being developed in order to facilitate the parameterisation by the user.

Use Case

The ScaleMaster2.0 model is experimented using the VMAP MRDB, exploited as part of a research project conducted by the COGIT Lab. The Vector Map (VMAP) is a MRDB providing a large variety of themes at three different levels of details: VMAP0 for small scales (~1:1000k), VMAP1 for medium scales (~1:250k) and VMAP2 for large scales (~1:50k).

The study area (Figure 12) used for the experiment is located in the region of Abéché (Tchad). Its surface is 1 sq.degree, which is about 12000 km². The following themes are generalised: roads, rivers, lakes, contours, and built-up areas. At the moment, only basic generalisation processes are carried out by the ScaleMaster2.0: Douglas-Peucker filtering, Gaussian smoothing, polygon merging, polygon skeletonization, strokes-based road selection and contours selection.

The main issue of the ScaleMaster2.0 editing deals with the parameterisation of the different algorithms used for generalisation. Indeed, experiments by trial and error need to be previously carried out, in order to define the appropriate value of the parameter according to the target scale. To set these values, specifications of the derivation rules from VMAP2 to VMAP1 DLMs, and VMAP1 to VMAP0 DLMs were used.

For example, from VMAP2 (~1:50k) to VMAP1 (~1:250k), only 1 contour out of 5 is preserved. Thus, to derive contours at the scale 1:100k, 1 contour out of 3 is preserved, and at the scale 1:200k, 1 contour out of 4 is preserved.

Results

To experiment the ScaleMaster2.0 model, we propose to derive DCMs at three target scales from the VMAP MRDB: 1:100k, 1:200k (from VMAP2) and 1:500k (from VMAP1). The 1:250k results are just VMAP1 extracts for comparison purposes.

The derivation of the road theme is mainly based on attribute filtering (important roads are kept) and strokes-based selection [START_REF] Thomson | The "good continuation" principle of perceptual organization applied to the generalization of road networks[END_REF], with Douglas-Peucker filtering (Figure 13). The derivation of rivers for the three target scales also relies on attribute selection and geometrical filtering. The generalisation procedure of the river theme also integrates the possibility to collapse river areas from polygons to polylines, when their width is below a given threshold (Figure 15). A skeletonization algorithm is provided in the ScaleMaster2.0 implementation to allow this task. The generalisation of urban areas illustrates the possibility given by the ScaleMas-ter2.0 model to order processes in a generalisation procedure. As exposed in Figure 16, the derivation of urban areas at the 1:100k scale involves: 1-the merging of neighbouring polygons, 2-the filtering with appropriate parameters. The derivation of contour lines (Figure 17) also involves two processes : the selection of contour lines (1 out of 3 at the 1:100k scale, and 1 out of 4 at the 1:200k scale), and a light filtering of the preserved contours. These results underline the possibility offered by the ScaleMaster2.0 model (and its implementation) to automatically derive DCMs from a MRDB, involving the use of several generalisation processes. In terms of computing performance, the ScaleMas-ter2.0 is also efficient, but its efficiency greatly depends on processes efficiency. For instance, the generalisation procedure of the five VMAP2 themes at the 1:100k scale needs almost 10 seconds, including data loading and exporting.

Finally, the enrichment of the model with other algorithms available in the CartAGen library will give the opportunity to provide better generalisation results, especially for themes that require contextual algorithms like roads, rivers or land use.

Discussion

Although the ScaleMaster2.0 model has the genericity to allow a large variety of generalisations, it still has limitations to discuss. First, there is a loss compared to the previous ScaleMaster model in relation to symbol design. We still do not have symbol information in our research project, so we did not focus on modelling symbol choices. We plan to extend the model to allow symbol design at the ScaleMasterElement level, using the SLD standard.

Up to now, the generalisation processes triggered by the ScaleMaster2.0 only concern one of the themes of the map (e.g. not roads and rivers at the same time). But such operations are frequently required, for instance to remove symbol overlaps between network features like parallel roads and rivers. Such operations cannot be included in one of the ScaleLines due to processing order issues, so the model has to be extended to manage the specification of multi-themes processes in additional Scale-Lines.

Moreover, many of the existing generalisation processes are based on trial/error mechanisms [START_REF] Harrie | Modelling the overall process of generalisation[END_REF], but the ScaleMaster2.0 runs sequentially. When such mechanisms are required, the simple way to handle the problem is to encapsulate a trial/error process as a single process that can be parameterised and triggered by the ScaleMaster, like in CollaGen model [START_REF] Touya | CollaGen: Collaboration between automatic cartographic generalisation processes[END_REF]): the process is triggered as a black box, the same way a simple algorithm is triggered, with eventually more complex parameters as the process is more complex.

CollaGen also differentiates the processes to be used according to landscapes (e.g. different processes are used in urban and rural areas), and such an extension is necessary to improve the results that can be provided by a ScaleMaster2.0 generalisation system. Indeed, it is rare that a single set of parameters for a process, or even a single process, is suitable for the generalisation of all landscapes: for instance, the generalisation of river networks requires different parameters in humid and arid landscapes [START_REF] Buttenfield | Multiscale representations of water: Tailoring generalization sequences to specific physiographic regimes[END_REF]. A way to overcome this problem would be to specify in the ScaleMaster the kind of landscape suitable for a process.

Added to that, our experience on the use case illustrated the well-known difficulty to specify the parameters of generalisation processes in order to obtain the expected map result. Testing is required to correctly tune the parameters of the processes for each of the scale intervals. Past research demonstrated that it easier to define generalisation constraints [START_REF] Beard | Constraints on rule formation[END_REF], from which the parameters could be automatically extracted like in [START_REF] Touya | CollaGen: Collaboration between automatic cartographic generalisation processes[END_REF].

Finally, we believe that the ScaleMaster2.0 model is a good opportunity to work on generalisation processes aware of the multiple representations they are working on.

For instance, multi-scale generalisations would benefit from processes that take into account the other representations of a feature in scales further in the ScaleLine to decide which operation to apply to the feature (Figure 18).

Conclusion

To conclude, we proposed an extension of the ScaleMaster framework, the ScaleMas-ter2.0, which allows automatic multi-scale generalisation. This generic model can be filled by any generalisation process and provides maps at any scale derived from MRDB source data. The model was implemented in CartAGen Open Source platform and it can be specified with XML files. The model was tested on real data with good results considering the low number of processes that have been integrated yet.

The ScaleMaster2.0 is a generic tool that now needs experiments with a large number of processes. However, some limitations have already been identified and the model needs to be improved to manage symbol design, multi-themes processes, landscape differentiation or constraints. Moreover, we plan to work on what we call multi-representation aware generalisation to make good use of the ScaleMaster2.0 possibilities.

Figure 1 .

 1 Figure 1. (a) Multi-Scales generalisation from MRDB. (b) Multi-Scales generalisation from unrelated DLMs.

Figure 2 .

 2 Figure 2. The Star and Ladder strategies to generalise predefined DCMs.

Figure 3 .

 3 Figure 3. (a) extract from a ScaleMaster for hydrography data. (b) the operations related to the keys used in the Scale-Master extract.

Figure 4 .

 4 Figure 4. Illustration of the importance of processing order in map generalisation: it greatly impacts the results.

Figure 5 .

 5 Figure 5. UML class diagram of the ScaleMaster2.0 model.

Figure 6 .

 6 Figure 6. Extract of the generalisation operators ontology, two of the operators being illustrated with examples.

  Figure 7shows how the ontology is modelled centred on the concepts algorithm and process. An algorithm (or a process) works on a geometryType, applies to geographic entities and has parameters. An algorithm implements one (or several) operation(s), while a process triggers algorithms (e.g. CartACom process[START_REF] Duchêne | Automated map generalisation using communicating agents[END_REF]) or operations (e.g. least squares(Harrie & Sarjakoski 2002) that triggers displacements).

Figure 7 .

 7 Figure 7. Extract of the generalisation algorithms ontology.

Figure 8

 8 shows the algorithm used by the engine to carry out automatic generalisation. It's a pretty straightforward algorithm that reproduces the task made by the cartographer in the initial ScaleMaster: themes are generalised from top to bottom of the ScaleMaster, whose order should follow the principle "from the ground up"[START_REF] Brewer | Framing guidelines for Multi-Scale map DesignUsing databases at multiple resolutions[END_REF], i.e. first terrain, then hydrography, then transportation, etc.

Figure 8 .

 8 Figure 8. Automatic process of the ScaleMaster2.0 to produce a DCM at a given scale.

Figure 9 .

 9 Figure 9. Implementation of the ScaleMaster2.0 model using the CartAGen library

Figure 10 .

 10 Figure 10. Structure of the ScaleMaster.xml file The Parameters.xml file defines the map final scale and what DLMs (or layers of a DLM) are available to be used as sources. Finally, the Symbology.xml file is proposed to describe how map themes are displayed. The formalisation of symbology in this XML file follows the SLD (Styled Layer Descriptor) standard.

Figure 11 .

 11 Figure 11. An interactive editor for the ScaleMaster2.0 model

Figure 12 .

 12 Figure 12. Study area experimented with the ScaleMaster2.0

Figure 13 .

 13 Figure 13. Derivation of roads from VMAP MRDB.

  Figure 14 clearly demonstrates that the use of the ScaleMas-ter2.0 model allows the automatic generation of continuous representations of a theme with smooth changes in the level of details.

Figure 14 .

 14 Figure 14. Derivation of rivers from VMAP MRDB.

Figure 15 .

 15 Figure 15. Collapse of the hydrographical surfaces from polygons to polylines.

Figure 16 .

 16 Figure 16. Derivation of urban areas from VMAP MRDB.

Figure 17 .

 17 Figure 17. Derivation of contours from VMAP MRDB.

Figure 18 .

 18 Figure 18. Multi-representation aware road selection process.


Nicholas M Gould
email: n.gould@mmu.ac.uk

William A Mackaness
email: william.mackaness@ed.ac.uk

Guillaume Touya
email: guillaume.touya@ign.fr

Glen Hart
email: glen.hart@nottingham.ac.uk

Collaboration on an Ontology for Generalisation

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

An ontology can be defined as a "formal, explicit specification of a shared conceptualization" [START_REF] Studer | Knowledge engineering: Principles and methods[END_REF]. The term "shared", first introduced by [START_REF] Borst | Construction of Engineering Ontologies[END_REF], implies that the knowledge encapsulated is consensual, without which the benefits of the ontology are limited. This is why the development of any ontology has to be a collaborative effort. Here we call for a collective effort to build an ontology for generalisation.

The proposal is to extend and broaden the work of [START_REF] Gould | A prototype for ontology driven on-demand mapping of urban traffic accidents[END_REF] where an ontology was designed specifically to support the on-demand mapping of road accidents. The aim is to collaboratively develop an ontology for the selection of generalisation algorithms.

Consider the number of algorithms that perform road network generalisation [START_REF] Benz | Road network selection using an extended stroke-mesh combination algorithm[END_REF][START_REF] Weiss | Road Network Selection for Small-Scale Maps Using an Improved Centrality Approach[END_REF]ESRI, 2012;[START_REF] Li | Integration of linear and areal hierarchies for continuous multiscale representation of road networks[END_REF][START_REF] Yang | Generating hierarchical strokes from urban street networks based on spatial pattern recognition[END_REF][START_REF] Liu | Road selection based on Voronoi diagrams and strokes in map generalization[END_REF][START_REF] Savino | Data enrichment for road generalization through analysis of morphology in the cargen project[END_REF][START_REF] Touya | A Road Network Selection Process Based on Data Enrichment and Structure Detection[END_REF][START_REF] Chen | Selective omission of road features based on mesh density for automatic map generalization[END_REF][START_REF] Jiang | A Structural Approach to the Model Generalization of an Urban Street Network[END_REF][START_REF] Thomson | The 'Good Continuation' Principle of Perceptual Organization applied to the Generalization of Road Networks[END_REF][START_REF] Mackaness | Analysis of Urban Road Networks to Support Cartographic Generalization[END_REF]. It requires a reading of the literature to determine which of these is appropriate for a particular context. But if it is difficult for humans to select an algorithm based on a natural language description then it is even more so for machines. If the move to develop spatial data infrastructures based on web services continues then there is a need to formalise algorithm knowledge to aid their automatic selection.

Why develop an ontology of generalisation?

Although the results of generalisation are the results of manipulating geometric primitives, those manipulations need to be based on the geographical contextnot just user needs [START_REF] Mackaness | Understanding Geographic Space[END_REF]. When mapping road accidents, for example, the road network cannot be generalised without taking account of its relationship with the location and type of accidents. For example, the generalisation of road network might lead to the removal of a minor road that provides context for a group of mapped accidents; road accidents mapped without the road on which they occur are meaningless. Context is part of the semantics of a domain, which can be "encapsulated, elucidated, and specified by an ontology" (Kavouras and Kokla, 2008, p10). In the domain of generalisation, the semantic relationships that govern generalisation must be made explicit and formalised [START_REF] Wolf | Ontology-Driven Generalization of Cartographic Representations by Aggregation and Dimensional Collapse[END_REF][START_REF] Dutton | Ontological Modeling of Geographical Relationships for Map Generalization[END_REF]. In this example, the ontology would describe the semantic relationship between road accidents and the road network. Over twenty years ago, [START_REF] Nyerges | Representing geographical meaning[END_REF] pointed out that cartographers lacked the means to systematically document the knowledge required for generalisation. The concept of ontologies provides that means.

Using an ontology to describe a domain can lead to intelligent knowledge retrieval [START_REF] Benjamins | Knowledge Management through Ontologies[END_REF]. In particular, if the ontology is formalised using logic, such as the Web Ontology Language (OWL), automated reasoning is possible [START_REF] Horrocks | What Are Ontologies Good For?[END_REF]. The aim is to develop an ontology that sufficiently describes the characteristics of generalisation algorithms, the geographic features they operate on, and the context they operate in, such that algorithms can be selected automatically. Such characteristics might include the effects the algorithm has on the geographic features, such as a change in dimensionality or a reduction in the number of features, and source and target scales. To express these characteristics, entities such as Operator, Algorithm, Geometry, Feature Type and Feature Collection will need to be encapsulated in the ontology. These entities will then be related using axioms such as Collapse reduces Dimensionality.

It has been argued that every information system contains an implicit ontology and making it explicit reduces conflicts between the ontological concepts and the implementation [START_REF] Fonseca | Semantic Granularity in Ontology-Driven Geographic Information Systems[END_REF]. For example, two different algorithm programmers might have different understandings of the concept of the amalgamation and thus create different implementations that share the same name. The ontology can be used to describe characteristics of each algorithm, the input features and the current context. If the descriptions contain sufficient detail then the appropriate algorithm can be selected using its characteristics and not its name.

The knowledge required for automatic generalisation is currently encapsulated either formally and implicitly (Figure 1) in generalisation software such as agent-based systems [START_REF] Taillandier | Multi-criteria diagnosis of control knowledge for cartographic generalisation[END_REF] or informally and explicitly, for example, in different generalisation operation taxonomies [START_REF] Roth | A typology of operators for maintaining legible map designs at multiple scales[END_REF][START_REF] Foerster | Towards a formal classification of generalization operators[END_REF][START_REF] Mcmaster | Generalization in digital cartography[END_REF]. Encapsulating that knowledge explicitly and formally in an ontology will allow that knowledge to be shared, expanded and utilised by generalisation software for all forms of map production and interaction. The formalisation of the description of the features we wish to map will also lead to "smarter" data where the business logic is no longer held in the software but with the data [START_REF] Carral | An Ontology Design Pattern for Cartographic Map Scaling[END_REF]; how the features are described in the ontology will determined how they are generalised.

Figure 1 Classifying generalisation knowledge representations

Ontologies have also been used in generalisation by [START_REF] Kulik | Ontology-driven map generalization[END_REF] to aid road line simplification; by [START_REF] Dutton | Ontological Modeling of Geographical Relationships for Map Generalization[END_REF] to represent the roles of geographic features and semantic and structural relationships between features in a coastal region; by [START_REF] Wolf | Ontology-Driven Generalization of Cartographic Representations by Aggregation and Dimensional Collapse[END_REF] to influence the aggregation and dimensional collapse of features; and by [START_REF] Lüscher | Where is the Terraced House? On the Use of Ontologies for Recognition of Urban Concepts in Cartographic Databases[END_REF] to aid the recognition of terrace houses. However, none of these ontologies described the process of generalisation; the identification, sequencing and execution of generalisation algorithms. A collaborative effort is called for in the creation of such an ontology.

For an ontology to be successful, if success is measured by its acceptance and use within its target community, then the creation of the ontology has to be a collaborative process. Indeed the development of an ontology -a shared conceptualisation -is intrinsically a collaborative process [START_REF] Groza | State of the art and open challenges in community-driven knowledge curation[END_REF]. A collaboration will have a plurality of stakeholders and is therefore more likely to lead to a sustainable ontology. However, in a collaboration involving partners with potentially differing perspectives and goals, it is important to define a clear methodology for the ontology development.

Methodology

The application of a methodology will provide structure to the process of building an ontology and will ensure best practice [START_REF] Hart | Linked Data: A Geographic Perspective[END_REF]. A number of ontology design methodologies, which provide guidance on defining concepts and relationships, have been developed but there is a lack of widely accepted methodologies, possibly because many of them were developed for a particular application [START_REF] Iqbal | An Analysis of Ontology Engineering Methodologies: A Literature Review[END_REF].

However, a number of criteria to aid selection of an ontology methodology have been defined [START_REF] Iqbal | An Analysis of Ontology Engineering Methodologies: A Literature Review[END_REF] and one important criterion is the support provided by the methodology for collaborative construction, where different members of the team, even in different geographic locations, can work simultaneously on different aspects of the ontology.

The much cited Ontology Development 101 guide of [START_REF] Noy | Ontology Development 101: A Guide to Creating Your First Ontology[END_REF]is a methodology in all but name. Their guide states that for an ontology to work effectively it should be designed with a specific task in mind. It is necessary therefore to be clear about the purpose of the ontology before the process of designing it is started. The aim of the proposed project is not the design of an all-purpose ontology but an ontology to aid the selection of generalisation algorithms.

Many methodologies stress the importance of using existing ontologies and there has been recent interest in "geo-ontologies" [START_REF] Janowicz | Geospatial semantics and linked spatiotemporal data -Past, present, and future[END_REF], which might be of use, particularly when describing physical geographic concepts. However, the focus will be on those characteristics of geographic features that effect their generalisation. Immaterial concepts such as generalisation operator and algorithm will also need to be defined and it may be that a set of related ontologies, developed by different partners but to a common template, will need to be developed rather than a single ontology.

The open source webProtégé ontology editor [START_REF] Tudorache | WebProtégé: A collaborative ontology editor and knowledge acquisition tool for the Web[END_REF] allows for the collaborative development of ontologies and can be downloaded and installed on a server or used via the Stanford University hosted version. Collaboration is supported by change tracking, and a discussion forum for each class defined in the ontology (Figure 2). Ontologies developed using webProtégé support the popular OWL 2 standard for ontologies [START_REF] Grau | OWL 2: The next step for OWL[END_REF], which will be employed by the project.

Figure 2 The webProtégé interface

The webProtégé interface is specifically a tool for the knowledge engineer. It is important to recognise the distinctly separate roles of the knowledge engineer and the domain expert and the key collaboration is between these two roles. It might be possible for domain experts to act as knowledge engineers [START_REF] Denaux | Supporting domain experts to construct conceptual ontologies: A holistic approach[END_REF].

Evaluating and using the ontology

The evaluation of the ontology is seen as a key phase in several ontology development methodologies [START_REF] Sure | Ontology Engineering Methodology[END_REF][START_REF] Grüninger | Ontology Summit 2007 -Ontology, taxonomy, folksonomy: Understanding the distinctions[END_REF][START_REF] Fernández-López | Methontology: from ontological art towards ontological engineering[END_REF]. We propose a number of measures, of increasing complexity, to evaluate the ontology. Firstly, a set of competency questions [START_REF] Grüninger | Methodology for the Design and Evaluation of Ontologies[END_REF], which are proposed at the start of the design process, can be used to evaluate whether the ontology meets requirements and act as a justification for the ontology. In particular, the competency questions will help define the scope of the ontology.

Once the competency questions have been answered to satisfaction the second stage in the evaluation will be to use the ontology to capture the properties of a number of generalisation algorithms described in the literature. Particular types of algorithm such as road network generalisation or building amalgamation can be used as case studies. Line simplification algorithms would provide a particularly interesting use case since there are a large number of competing algorithms, which often share very similar, but distinctly different, characteristics. The ontology is evaluated by comparing the algorithm definitions; if any two algorithms have exactly the same definition then their definitions need to be refined, possibly by introducing new concepts and relationships to the ontology. It is also necessary to consider the fact that some algorithms may implement multiple operators such as aggregation and simplification. The next two evaluation steps will put the ontology to practical use, firstly by using it to support web-based generalisation services.

For geospatial web services to be used effectively they require semantic interoperability: "the ability of services to exchange data in a meaningful way and with a minimum of human intervention" (Janowicz et al., 2010, p112). The standard for implementing geospatial web services is the OGC's Web Processing Service (WPS) protocol, which has been adopted by the WEBGEN generalisation platform [START_REF] Neun | WEBGEN: Web Services to Share Cartographic Generalization Tools[END_REF]. The WPS protocol allows for a natural language description of what the service provides but not the formal, machine readable description required for semantic interoperability. Semantic interoperability allows services to interact at a semantic level, not just a syntactic level.

The WPS protocol allows for syntactic interoperability, by requiring the formal definition of the input and output parameters (specifying geometries, for example) but again the semantics are missing; why should one building displacement algorithm be chosen over another? The knowledge required to make such decisions can be formalised using an ontology, but how can the ontology be integrated with generalisation web services?

One solution is to introduce a Semantic Enablement Layer [START_REF] Janowicz | Semantic Enablement for Spatial Data Infrastructures[END_REF], where a Web Ontology Service injects semantics into both data and processing services (Figure 3). The Web Ontology Service could be employed to maintain a shared set of generalisation ontologies. In this depiction a separate ontology is used to describe geographic features and it may be that a set of related ontologies will need to be developed rather than a single ontology. There might, for example, be a separate ontology for describing spatial relations [START_REF] Touya | Modelling Geographic Relationships in Automated Environments[END_REF]. A Web Reasoning Service can then be used to search for an appropriate generalisation service by using Web Ontology Language (OWL) queries. We suggest the application of a Semantic Enablement Layer to the WEBGEN service (Dresden University of Technology, 2014).

Figure 3 Semantic injection of data together with processing web services

The final evaluation of the ontology will be to utilise it to support existing map generalisation software such as an agent-based system. As stated earlier, much domain knowledge is embedded in generalisation software systems and the formalisation of some of that knowledge in an ontology can help make it shareable. Currently such systems are configured to generalise familiar feature types such as roads, rivers and buildings at a fixed set of target scales and their associated knowledge base has to be updated every time a new generalisation algorithm is introduced to the system or when user requirements change [START_REF] Taillandier | Multi-criteria diagnosis of control knowledge for cartographic generalisation[END_REF]. If the knowledge required to generalise road accidents, for example, is shared via an ontology, then such systems might become more flexible.

Conclusion

The aim of the project is to develop an ontology of cartographic generalisation. Specifically, the ontology should contain sufficient knowledge to allow for the automatic selection of generalisation algorithms. To achieve this, we propose the creation of a consortium of partners, and collective agreement on a project plan to confirm the aims of the project, define a methodology for developing the ontology, and define criteria for evaluating the ontology. The ontology should build on previous attempts at formalising generalisation knowledge such as for map specifications and constraints [START_REF] Stoter | State-of-the-art of automated generalisation in commercial software[END_REF][START_REF] Burghardt | Investigations on Cartographic Constraint Formalisation[END_REF].

In this paper we have argued the need for a generalisation ontology for algorithm selection of a form that supports machine reasoning, and thus higher levels of automation in the delivery of web-based generalisation services. Such an effort would reduce redundancy in the development of algorithms. More broadly this ambition reflects the need for 'geographic generalisation' methodologiesi.e. algorithms sensitive to the geographic context of the problem rather than just the geometric.

17th ICA Workshop on Generalisation and MultipleRepresentation, Vienna, Austria, 23 Sept. 2014