EXTENSIONS DE LA DISTANCE LINEAIRE DE FRECHET ET ALGORITHMES D’APPARIEMENT

EXTENSIONS DE LA DISTANCE LINEAIRE DE FRECHET ET ALGORITHMES D’APPARIEMENT

Le chapitre Précédent a montré que les éléments caractéristiques importants pour l’intégration de MNT étaient essentiellement linéaires. Il faut donc disposer de distances permettant de comparer, apparier puis intégrer ces éléments. L’algorithme retenu pour réaliser l’intégration de données terre/mer à l’issue de cet inventaire est celui basé sur la distance de Fréchet car elle est la mesure la plus appropriée pour comparer des éléments linéaires complexes (thalwegs crêtes, etc.) Celle-ci, introduite par [Fréchet, 1906], se base sur l’assimilation de toute ligne à une suite de points orientés équivalente à une fonction continue. Le résultat est une distance maximale entre les deux lignes comparées. La difficulté à utiliser ce calcul vient de sa complexité à programmer. [Eiter & Mannila, 1994] proposent une solution en développant une estimation de cette distance : la distance de Fréchet discrète. Cette distance a pour intérêt de réaliser un appariement basé sur les points homologues des lignes comparées et non les points les plus proches. Cependant, telle qu’elle a été définie, elle est insuffisante pour répondre à toutes les attentes et contraintes d’un appariement de données géographiques. En effet l’algorithme de départ ne s’applique qu’à des lignes ouvertes, sensiblement de même taille et d’orientations identiques. Dans le cadre de l’appariement, il est nécessaire de l’adapter afin de pouvoir comparer des lignes d’emprises, de tailles, de natures et d’orientations différentes. Dans le cas de données réelles, les lignes numérisées (1) peuvent présenter l’aspect de lignes « fermées » (polygones dont les points sont ordonnés) et (2) ne sont pas obligatoirement saisies dans le même sens. Il convient donc de déterminer avant toute chose la « nature » d’une ligne : si le premier point est identique au dernier, alors la ligne représente une ligne fermée. Ensuite il faut également s’assurer des orientations respectives des lignes entre elles. Il s’agit de vérifier que les suites ordonnées de points de chaque ligne ouverte sont bien dans le même sens et que les points de début et de fin sont homologues et non diamétralement opposés. Les deux extensions développées dans ce chapitre se proposent donc de répondre aux différents problèmes posés lors de la comparaison de lignes en inventoriant les différents cas de figure rencontrés. Les algorithmes détaillés par la suite expliquent comment utiliser au mieux ces distances lors des processus d’appariement de lignes. La première partie présente succinctement les lignes et les attributs qui sont utilisés dans les processus de comparaison et d’appariement. La seconde partie détaille toutes les distances introduites pour la comparaison de lignes :

La troisième partie se base sur ces distances pour détailler les algorithmes d’appariement. La première section présente les étapes d’identification de la nature des lignes comparées. La seconde présente les différents types d’inclusion qu’il existe entre les emprises des lignes étudiées. Et la dernière section explique quel appariement est effectué selon les différents cas de figure identifiés et quelle distance est adaptée. Une dernière section réalise une synthèse en intégrant ces appariements simples dans un algorithme de traitement global de deux jeux de polylignes.Finalement, la dernière partie sert de validation des algorithmes appliqués au cas de comparaison de lignes en présentant le résultat d’une étude sur le suivi du trait de côte. Cette étude s’est réalisée au moyen d’indicateurs visuels extraits d’images satellites et de la distance de Fréchet pour la quantification des déplacements entre une ligne de référence et une ligne numérisée à une date donnée.

distance moyenne de Fréch et couples de points homologues

La distance de Fréchet discrète (ddF) représente l’écartement maximal entre deux points homologues des lignes comparées. Afin de compléter l’information fournie par cette mesure, d’autres distances, toutes dérivées de la ddF (voir Chapitre I), ont été introduites. La première distance exposée dans cette section, la distance de Fréchet moyenne (daF), permet l’évaluation de l’écartement moyen global entre les points homologues des lignes. Elle est la moyenne des distances euclidiennes entre couples de points issus du chemin minimum. Le « chemin minimum » est composé d’une suite de couples de points {(L1.1, L2.1),… (L1.n, L2.m)} pour lesquels la distance d’écartement entre les points du couple est inférieure ou égale à ddF. Les points ainsi retenus sont appelés points homologues. Pour reprendre l’exemple du maître et de son chien introduit au chapitre II, plusieurs chemins possibles respectent la distance de Fréchet. Parmi ces chemins candidats, le « chemin minimum » constitue celui pour lequel le promeneur et son chien évoluent le plus proche possible l’un de l’autre à chacun de leur déplacement. Pour calculer ce chemin, les deux matrices de distance et de Fréchet sont nécessaires ainsi que l’opérateur inférieur ou égal (<=) entre deux couples de réels.