Le modele Gael

Julien GaffuriThèse de doctorat en informatique, spécialité sciences de l’information géographique

M Alexis DrogoulMme Cécile Duchêne M Hervé MartinMme Annabelle MasM Jean-Pierre MüllerMme Anne RuasM Robert Weibel

École doctorale ICMS – Université Paris EstInstitut Géographique National – Laboratoire COGIT

Généralisation à base d’opérations discrètes et continuespour la prise en compte des thèmes champ :

le modèle GAEL

RapporteurEncadrantePrésidentExaminateurExaminateurDirectriceRapporteur

Généralisation à base d'opérations discrètes et continues: le modèle GAEL - Julien Gaffuri - 1er juillet 2008 2

Introduction

ContexteÉvolution des besoins en données géographiques :

QuantitéQualité

Données géographiques de plus en plus fines

Nécessité de méthodes de transformation de données géographiques pour les adapter aux différents besoinsLa généralisation


Introduction

La généralisation est l’opération de simplification de données géographiques lorsque leur échelle de représentation diminue.

La généralisation cartographique

1:250k 1:1000k


Besoin en généralisation automatique à partir de bases de données géographiques vectorielles

Depuis ~20 ans : nombreux travaux en généralisation automatiqueModèles de généralisation automatique

Introduction


Plan

Introduction - contexteProblématiqueLe modèle GAEL

Un modèle hybrideUn modèle pour la prise en compte des relations objet-champ

Mise en œuvreConclusion et perspectives


ProblématiqueIntroduction Problématique Le modèle GAEL Mise en oeuvre Conclusion et perspectives


Problématique

Nombreux modèles de généralisation automatique2 approches :

Approche à base de transformations continues globalesDéformation holistique des objets géographiques.

Ex: triangles flexibles [Højholt 2000], moindres carrés [Sester 2000], snakes [Burghardt & Meyer 1997], poutres élastiques [Bader 2001], [Harrie 2001], agent [Fritsch 1997], [Baeijs 1998], etc.

Approche à base de transformations discrètes localesTransformations locales discrètes successives [Brassel & Weibel 1988]

Ex: exploration par escalade, recuit simulé [Ware et Jones 1998] [Neun et al. 2008], modèles à base d’agents géographiques [Ruas 1999], [Lamy et al. 1999], [Duchêne 2004], [Jabeur 2006], etc.

Introduction Problématique Le modèle GAEL Mise en oeuvre Conclusion et perspectives

Modèles conçus indépendamment les uns des autres


Problématique

Généralisation nécessite des opérations discrètes et continues ensemble

1:50k 1:100k


Opération discrète Opération continue


Problématique

Généralisation nécessite des opérations discrètes et continues ensembleUtilisation dépend:

du type d’objet – objets rigides/élastiques

du saut d’échelle

Faible Fort

Opérations sur le schéma

Opérations continues

Opérations discrètes

Saut d’échelle




Objectif de la thèse :


ou

Opération discrète

Opération continue

Proposer un modèle de généralisation hybride


Opérations continues particulières : déformation des thèmes champ« Phénomènes existants en tout point de l’espace géographique »

Relief

Partition administrative

Occupation du soletc.



Les champs en généralisation :Généralisation propreRelations entre objets et champs

Un village sur un sommet

Une route a une pente constante

etc.

Un cours d’eau dans un thalweg

Un bâtiment dans une zone d’occupation du sol



Nécessité de prise en compte des relations objet-champ


AvantGénéralisation

AprèsGénéralisation

!! !

!

!!

!!

! ! !


[SSC 1977] [IGN guide opérateur]

[SGK 2002]

Déformations manuelles



[SGK 2002]

Déformations manuelles


[SGK 2002]


Objectif de la thèse :


ou

Opération discrète

Opération continue

Proposer un modèle de généralisation hybride…

…pour la prise en compte des relations objet-champ


Le modèle GAELIntroduction Problématique Le modèle GAEL Mise en oeuvre Conclusion et perspectives

GAELGénéralisation à base d’Agents ELastiques



1- Un modèle hybride de généralisation

2- Un modèle pour la prise en compte des relations objet-champ


Proximité

Le modèle de [Ruas et Duchêne 2007]Principes : AGENT [Ruas 1999], CartACom [Duchêne 2004]

Les contraintes sont explicites, [Beard 1991]

Les objets géographiques sont des agents,But de chaque agent: satisfaire ses contraintes propres,Les agents essaient de s’appliquer des opérations discrètes,Niveaux hiérarchiques: micro et meso,

Interactions hiérarchiques et binaires micro.

but

Bâtiment

Îlot

Ville

micro

meso

meso

but

but

Proximité

TailleGranularité

Taille

Granularité



Le modèle de [Ruas et Duchêne 2007] permet:

But:


ou


Les agents géographiques deviennent déformables localement. Agents « élastiques ».Principes :

l’agent élastique se décompose en parties contraintes,ses points sont des agents,l’agent élastique contrôle sa déformation.


Point

Triangle

Angle

Segment

…


Le modèle GAEL

Ajout d’un niveau interne : le niveau submicroObjet submicro : ensemble de points contraints

submicroPoints, triangles, segments…


Bâtiment

Îlot

Ville

micro

meso

meso


L’agent-point


Mon but est d’atteindre une position d’équilibre entre mes contraintes


Le modèle GAEL

les contraintes submicro

Position de point

Longueur de segment

Orientation de segment

Position de segment

Aire de triangle

Pente de triangle

Distance point segment

Distance point point

Distance segment segment

Valeur d’angle



Le modèle GAEL

- 6 segments

- 18 angles

- 6 triangles

L’agent-point: exemple de dynamique

1 insatisfait

6 insatisfaits

2 insatisfaits



Le modèle GAEL

- 6 segments

- 18 angles

- 6 triangles

1 insatisfait

6 insatisfaits

2 insatisfaits




Le modèle GAEL

- 6 segments

- 18 angles

- 6 triangles

1 insatisfait

6 insatisfaits

2 insatisfaits




Le modèle GAEL

L’agent-pointil est capable:

de déterminer s’il est en équilibre ou non,de se déplacer pour progresser vers son équilibre,d’activer ses agents-point accointants.



Le modèle GAEL

Suis-je en équilibre?

Le point est activé

OuiJe me

désactiveNon

Je tente de me déplacer vers ma position d'équilibre

J'active mes agents accointants

Fin

Fin

L’agent-point: cycle de vie



Le modèle GAEL

Activation des agents-point accointants

Seuls quelques points sont activésLa transformation est locale






1- Un modèle hybride de généralisation

2- Un modèle pour la prise en compte des relations objet-champ


contraint déforme

Champs

Relations objet-champ

Objets(bâtiments, routes…)


Interaction entre objets et champs:


Le modèle GAEL

Les champs sont des agents élastiques:Contraintes de préservation de formeContraintes de déformation: contraintes relationnelles.


Champs

Objets(bâtiments, routes…)

Relations objet-champ


Le modèle GAEL

Modélisation des relations objet-champ contraintes:Spécialisation des relations de [Duchêne 2004].

Agent géographique

Agent champ

Relation objet-champ

Contrainte relationnelle objet-champ

Contrainte relationnelle champ-objet



Le modèle GAEL

Prise en compte des contraintes relationnelles objet-champ dans le processus de généralisation des objets:Modèles compatiblesPrincipes:

1- Prise en compte de la satisfaction des contraintes relationnelles objet-champ dans le calcul de la satisfaction des agents géographiques,2- Capacité des agents géographiques à activer les agents champ pour les déformer,3- Incitation des agents géographiques par leurs contraintes relationnelles objet-champ à:

activer le champ,s’appliquer une transformation adéquate.



Le modèle GAEL

Exemple:


Déformationacceptée Déformation

refusée


Résultats possibles:



Le modèle GAEL

Modèle de données:


Agent Contrainte

Contrainteélastique

Agentélastique

Agent point

Contraintesubmicro

Objetsubmicro

Contrainte internesubmicro

Contrainte relationnellesubmicro

Agentchamp

Relationagent géo.-champ

Agentgéographique

Contrainte relationnelleagent géo.-champ

Contrainte relationnellechamp-agent géo

Contrainteagent géographique

discret

continu

générique

relationsobjet-champ

Agent micro Agent meso


Mise en œuvreIntroduction Problématique Le modèle GAEL Mise en oeuvre Conclusion et perspectives



Cas de mise en œuvre:Préservations d’altitude de bâtimentPréservation d’écoulement du réseau hydrographiquePréservation d’appartenance d’un bâtiment à une zone d’occupation du sol

Déplacement en généralisationGénéralisation de courbe de niveau



Préservation d’altitude de bâtimentPrincipes :

Les triangles du relief sont incités à se déplacer pour minimiser les écarts d’altitude des bâtiments situés sur euxLes bâtiments incités à se déplacer suivant la pente pour minimiser leur écart d’altitude



Préservation d’altitude de bâtimentRésultat :

Données initiales

Données généralisées sans GAEL

Données généralisées avec GAEL

Déformation du relief

6

0

00

0

0

10

6

109



Préservation d’écoulement de tronçon hydrographiquePrincipes :

Les triangles du relief sont incités à se déplacer et à pivoter pour minimiser l’écart entre les orientations de leur pente et l’orientation moyenne du réseau hydrographique sur euxLes segments du réseau hydrographique sont incités à s’orienter selon la pente.



Préservation d’écoulement de tronçon hydrographiqueRésultat :

Données initiales

Données généralisées sans GAEL

Données généralisées avec GAEL

Déformation du relief



Démonstration

cf. vidéos



Préservation d’appartenance de bâtiment à une zone d’occupation du solPrincipes :

Les triangles du champ occupation du sol sont incités à se déplacer pour rétablir l’appartenance des bâtiments qui sont sur eux.Les bâtiments sont incités à se déplacer pour appartenir à nouveau à leur zone d’occupation du sol.



Préservation d’appartenance de bâtiment à une zone d’occupation du solRésultat :

Données initiales Données généraliséessans GAEL

Données généraliséesavec GAEL

Déformation



Déplacement en généralisationBâtiments [Craipeau 2007]

Réseaux


Généralisation des courbes de niveau



Généralisation des courbes de niveau



Conclusion et perspectivesIntroduction Problématique Le modèle GAEL Mise en oeuvre Conclusion et perspectives


Le modèle GAEL permet:de disposer d’un modèle de généralisation hybride,de prendre en compte les relations objet-champ.

Modèle implémenté (production)Pertinence de l’approche agent :

en généralisation automatique,pour traiter des problème nécessitant de prendre en compte la dualité continu/discret


Conclusion et perspectives

ou


Perspectives:

Fusion des modèles de généralisation [Touya 2008]

Amélioration des stratégies de déformationContrôle de déformationAutres mises en œuvre




« Imagine a gorge with a river and a road and a railway. First we plot the river, then we display the road. The railway is displaced further and finally the contours are moved. This presents a very difficult problem for the machine to solve »anonyme, selon [Mackaness 2006]




Références

Bader, M. (2001), 'Energy minimization methods for feature displacement in map generalisation', PhD thesis, universitй de Zurich.Baeijs, C. (1998), 'Fonctionnalité émergente dans une société d'agents autonomes; étude des aspects organisationnels dans les systèmes multi-agents réactifs', PhD thesis, institut national polytechnique de Grenoble.Brassel, K. & Weibel, R. (1988), 'A review and conceptual framework of automated map generalisation', International Journal of Geographical Information Systems 2(3), 229--244.Burghardt, D. & Meier, S. (1997), Cartographic displacement using the snakes concept, in W. Foerstner & L. Pluemer, ed.,'Semantic modelling for the acquisition of topographic information from images and maps', Birkhaeuser verlag, Basel, .Duchêne, C. (2004), 'Généralisation cartographique par agents communicants: le modèle CartACom', PhD thesis, Universitй Pierre et Marie Curie Paris VI, laboratoire COGIT.Fritsch, E. (1997), 'Représentations de la géométrie et des contraintes cartographiques pour la généralisation du linéaire routier', PhD thesis, universitй de Marne la Vallйe, laboratoire COGIT.Harrie, L. (2001), 'An optimisation approach to cartographic generalisation', PhD thesis, Lund university, Lund institute of technology, department of technology and society.Højholt, P. (2000), 'Solving space conflicts in map generalisation: using a finite element method', Cartography and Geographic Information Sciences 27(1), 65--74.IGN (), 'Guide opérateur en généralisation, chapitre II'.Jabeur, N. (2006), 'A multi-agent system for on-the-fly web map generation and spatial conflict resolution', PhD thesis, Universitй Laval.Lamy, S.; Ruas, A.; Demazeau, Y.; Baeijs, C.; Jackson, M.; Mackaness, W. & Weibel, R. (1999), AGENT Project: Automated Generalisation New Technology, in '5th EC-GIS Workshop'.Neun, M.; Burghardt, D. & Weibel, R. (2008), 'Automated processing for map generalization using web services', GeoInformatica.Ruas, A. (1999), 'Modèle de généralisation de données géographiques a base de contraintes et d'autonomie', PhD thesis, Universitй de Marne la Vallйe, laboratoire COGIT.Schweizerische Gesellschaft für Kartographie (2002), 'Topografische Karten: kartengrafik und Generalisierung'.für Kartographie, S. G. (1977), Cartographic generalisation, topographic maps, Zürich.Sester, M. (2000), 'Generalization based on least square adjustment', International archives of photogrammetry and remote sensing 23, part B4, 931--938.Ware, J. M. & Jones, C. B. (1998), 'Conflict reduction in map using iterative improvement', GeoInformatica 2(4), 383--407.


Des questions?


Documents

Le modele Gael