Gestion de la base de données cartographique - Map database management

Les systèmes de gestion de bases de données cartographiques sont des logiciels conçus pour stocker et rappeler efficacement des informations spatiales. Ils sont largement utilisés dans la localisation et la navigation, en particulier dans les applications automobiles. De plus, ils jouent un rôle de plus en plus important dans les domaines émergents des services basés sur la localisation , des fonctions de sécurité active et des systèmes avancés d'aide à la conduite . Le point commun à ces fonctions est l'exigence d'une base de données cartographiques embarquée contenant des informations décrivant le réseau routier.

Lorsqu'elle est bien conçue, une base de données cartographiques permet l'indexation et la recherche rapides d'une grande quantité de données géographiques.

Contenu d'une base de données cartographique

Figure 1 : entités et leurs attributs respectifs dans une base de données cartographique

Les cartes sont stockées sous forme de graphiques ou de tableaux bidimensionnels d'objets avec des attributs d'emplacement et de catégorie, où certaines catégories courantes incluent les parcs, les routes, les villes, etc.

Une base de données cartographiques représente un réseau routier ainsi que des entités associées. Les fournisseurs de cartes peuvent choisir différents modèles de réseau routier comme base pour formuler une base de données. Généralement, un tel modèle comprend des éléments de base (nœuds, liens et zones) du réseau routier et les propriétés de ces éléments (coordonnées de localisation, forme, adresses, classe de route, plage de vitesse, etc.). Les éléments de base sont appelés caractéristiques et les propriétés en tant qu'attributs. D'autres informations associées au réseau routier sont également incluses, notamment les points d'intérêt, la forme des bâtiments et les frontières politiques. Ceci est représenté schématiquement dans l'image ci-contre. Les fichiers de données géographiques (GDF) sont une description standardisée d'un tel modèle.

Chaque nœud dans un graphique cartographique représente un emplacement de point de la surface de la Terre et est représenté par une paire de coordonnées de longitude (lon) et de latitude (lat). Chaque lien représente un tronçon de route entre deux nœuds, et est représenté par un segment de ligne (correspondant à une section droite de route) ou une courbe ayant une forme qui est généralement décrite par des points intermédiaires (appelés points de forme) le long du lien. Cependant, les courbes peuvent également être représentées par une combinaison de centroïde (point ou nœud), avec un rayon, et des coordonnées polaires pour définir les limites de la courbe. Les points de forme sont représentés par des coordonnées lon-lat comme le sont les nœuds, mais les points de forme ne servent pas à connecter des liens, comme le font les nœuds. Les zones sont des formes bidimensionnelles qui représentent des choses comme des parcs, des villes, des blocs et sont définies par leurs limites. Ceux-ci sont généralement formés par un polygone fermé , qui sont des formes indiquant qu'un objet sur une carte doit avoir une limite étroite, ce qui signifie que le premier polygone doit être identique au dernier polygone. (Par exemple, pour tracer un objet carré sur une carte, les polygones sont 1,2,3,4,1.)

Un autre point de validation sur les données est le point dans polygon , qui aide à trouver des points situés à l'extérieur d'un polygone. Par exemple, pour des coordonnées lon-lat particulières dans une ville, si le point coupe le polygone en nombre impair, alors il est à l'intérieur du polygone et un point valide ; sinon, il est en dehors du polygone et invalide.

Format d'échange

Les fournisseurs de cartes collectent, regroupent et fournissent généralement des données dans un format de fichier bien défini et documenté qui est spécifiquement destiné à l'échange d'informations, par exemple Navteq utilise le format standard d'échange (SIF) et GDF , tandis que Tele Atlas utilise une forme propriétaire de GDF. Il se présente généralement sous forme de texte brut ( ASCII ) composé de champs qui sont facilement analysés et interprétés par les différentes parties qui le traiteront. Le format portable permet d'effectuer facilement des ajouts, des suppressions et des modifications par de simples programmes d'édition de texte.

Un petit nombre de types d'enregistrements sont utilisés pour représenter les divers types de données. Chaque type d'enregistrement se compose d'une séquence de champs, qui sont soit de longueur fixe, soit délimités par un caractère de ponctuation tel qu'une virgule. Par exemple, une entité de lien pourrait être représentée par un enregistrement de la forme :


type1,label,node1,z1,node2,z2,class,nombre de points de forme,nombre de voies,vitesse


où type1 le définit comme un type d'enregistrement de lien et l' étiquette sert d'identifiant pour distinguer ce lien de tous les autres. Les champs z1 et z2 déterminent la séparation verticale de ce lien des autres partageant les nœuds correspondants node1 et node2 . Ainsi, un viaduc vers un lien, par exemple, peut être représenté comme non connecté à ce lien. D'autres types d'enregistrements sont utilisés pour représenter des informations d'adresse, des points de forme pour un lien, des villes et des états, des points d'intérêt (POI), etc.

Le format d'échange pour une base de données cartographiques n'est pas bien organisé pour une utilisation par une unité de navigation pendant l'exécution. Les enregistrements sont dans un ordre arbitraire et donc difficiles à rechercher et les données, telles que les noms de rue et les valeurs de coordonnées, sont répétées d'enregistrement en enregistrement. Par conséquent, le contenu de la base de données est réorganisé sous une forme binaire plus adaptée aux opérations d'exécution.

Format d'exécution

Les formats d'exécution sont généralement propriétaires, empêchant l'interopérabilité des cartes entre différents systèmes de navigation. Cependant, une nouvelle initiative appelée Navigation Data Standard (NDS) est un regroupement industriel de constructeurs automobiles, de fournisseurs de systèmes de navigation et de fournisseurs de données cartographiques dont l'objectif est la normalisation du format de données utilisé dans les systèmes de navigation automobile. Les entreprises impliquées incluent TomTom , BMW , Volkswagen , Daimler , Renault , ADIT, Alpine Electronics , Navigon , Bosch , DENSO , Mitsubishi , Harman Becker, Panasonic , PTV, Continental AG , Navteq et Zenrin .

La base de données est réorganisée par un fournisseur de navigation via un processus de compilation qui comprend au moins les cinq étapes suivantes :

  1. Vérifiez la cohérence du réseau. Par exemple, assurez-vous que toutes les paires de nœuds qui devraient être connectées par un lien ont un tel lien et inversement toutes les paires de nœuds qui ne devraient pas être connectées n'ont pas de lien de connexion.
  2. Attribuez des identifiants (ID) à toutes les entités de manière systématique.
  3. Appliquez plusieurs ensembles d'index aux entités pour faciliter la recherche dans la base de données de la manière attendue.
  4. Remplacez les occurrences multiples d'éléments de données (noms de rues, coordonnées, etc.) par des indices dans des tableaux contenant une seule copie de chacun de ces éléments.
  5. Appliquez d'autres techniques de compression pour réduire la taille globale de la base de données.

Le contrôle de cohérence de l'étape 1 est généralement un processus très interactif et itératif qui peut prendre des semaines. Pendant ce temps, les écarts doivent être détectés, étudiés et résolus.

À l'étape 2, les identifiants sont généralement attribués de manière séquentielle au fur et à mesure que des entités de chaque type sont rencontrées. Toute modification apportée à la base de données d'entrée d'une version à une autre affectera l'attribution d'ID à toutes les entités. Par conséquent, il y a peu d'attentes de continuité dans l'affectation entre les versions.

A l'étape 3, chaque index appliqué permet de rechercher rapidement la base de données d'une manière spécifique. Un ensemble d'index appliqué aux liens peut être trié par ordre alphabétique des noms de rue des liens. Un autre ensemble d'index appliqué aux liens peut être trié en fonction des nœuds auxquels ils sont connectés pour faciliter la planification des itinéraires. Encore un autre jeu d'index appliqué aux nœuds peut être trié selon leur ordre d'apparition le long d'une route. Dans certains de ces cas, une recherche binaire peut être effectuée au lieu d'une recherche exhaustive et dans certains cas, un processus de recherche peut être remplacé par une simple consultation de table.

Mise à jour incrémentielle

Pour la plupart des fonctions de navigation, il est important d'avoir dans le véhicule une base de données cartographiques à jour, et pour certaines fonctions, c'est essentiel, en particulier celles liées à la sécurité active. Une stratégie courante consiste à transférer les informations de mise à jour au véhicule chaque fois qu'elles deviennent disponibles sur un canal sans fil. Le canal sans fil peut être bidirectionnel, comme le Wi-Fi et le téléphone portable, diffusé , comme la radio satellite, la sous-porteuse FM ou la diffusion de données ATSC , ou une combinaison des deux. Dans tous les cas, il serait peu pratique ou extrêmement inefficace de transmettre l'intégralité de la nouvelle base de données pour remplacer une version existante, car sa taille est susceptible de plusieurs gigaoctets.

Au lieu de cela, il est souhaitable de transférer uniquement les informations relatives aux modifications apportées à la base de données existante. Une difficulté majeure est que toute modification apportée au contenu d'une base de données cartographique entraîne généralement des modifications de tous les ID d'entité attribués et de tous les index attribués au cours du processus de compilation. Ces nouveaux identifiants et indices imprègnent l'ensemble de la base de données compilée de sorte que toute collection d'incréments constituera probablement la majeure partie de la base de données. Pour surmonter cette difficulté, trois approches ont été adoptées, qui sont brièvement 1) un compilateur embarqué 2) un magasin réservé 3) des tuiles géographiques.

Compilateur embarqué

Dans ce cas, les modifications de base apportées au format d'échange de la base de données sont transmises au véhicule. De tels changements sont représentés sous forme transactionnelle consistant en ajouts , suppressions et remplacements . Ces modifications sont appliquées à la base de données embarquée existante au format d'échange. Le format d'échange pour la base de données embarquée peut être soit stocké séparément, soit généré selon les besoins en « décompilant » le format d'exécution. La base de données combinée est ensuite compilée, ce qui implique l'attribution d'identifiants et l'application d'indices.

Cette compilation embarquée sera probablement gourmande en calculs et nécessitera une mémoire considérable. Cependant, il n'a pas besoin d'être interactif et itératif comme le fait la compilation hors carte puisque les vérifications de cohérence et la résolution auront déjà été effectuées. De plus, la compilation intégrée peut être effectuée en arrière-plan, de sorte que le temps de calcul n'est pas critique.

Magasin réservé

Dans ce cas, les modifications de base sont également transmises au véhicule, mais sont placées dans un emplacement de mémoire distinct appelé magasin réservé . Les modifications sont également représentées sous forme transactionnelle mais peuvent apparaître dans n'importe quel format pratique, qui n'est pas nécessairement ni l'échange ni l'exécution. Pendant le fonctionnement de l'unité de navigation, le magasin réservé est recherché à chaque accès à la base de données principale. Toutes les transactions (changements) qui se rapportent aux données consultées sont ensuite appliquées.

La nécessité d'examiner le magasin look-aside et d'appliquer des modifications pour chaque accès à la base de données complique bien sûr les algorithmes de navigation et allonge leur temps de calcul. Cependant, cela évite le besoin d'un compilateur embarqué.

Tuiles géographiques

Dans cette approche, la base de données cartographiques est décomposée en régions rectangulaires relativement petites (tuiles) qui quadrillent la carte. La taille des tuiles est de l'ordre de 1 km de côté. Ces tuiles sont compilées séparément, de sorte que tous les ID et indices sont conditionnés par la tuile particulière à laquelle ils s'appliquent. Les tuiles qui ont changé en raison de modifications d'entités ou d'attributs de base dans la base de données sont transmises au véhicule, où elles remplacent la tuile existante correspondante.

Le remplacement des tuiles est considérablement plus simple que la compilation à bord ou l'utilisation d'un magasin réservé. Cependant, il peut ne pas être efficace pour la transmission. Une modification locale des entités et des attributs, quelle que soit l'étendue, nécessite la transmission de l'intégralité de la tuile conteneur. De plus, il existe des effets de bord dans lesquels un changement dans une entité dans une tuile affecte les entités dans les tuiles voisines. Il est tout à fait possible qu'un petit nombre de changements d'entité nécessite la transmission de presque toutes les tuiles, ce qui va à l'encontre de l'objectif des mises à jour incrémentielles. Ces problèmes peuvent être résolus en sélectionnant la taille des tuiles et la fréquence de mise à jour.

Joindre des données auxiliaires

Diverses fonctions de navigation, impliquant la sécurité active, l'assistance à la conduite et les services basés sur la localisation, nécessitent des données qui ne sont pas considérées comme faisant partie d'une base de données cartographiques et sont probablement fournies par un fournisseur autre que celui du fournisseur de cartes. Ces données doivent être croisées avec les entités et les attributs de la base de données principale. Cependant, étant donné que les données auxiliaires ne sont pas nécessairement compilées avec la base de données principale, d'autres moyens sont nécessaires pour établir des références croisées, ce que l'on appelle l' attachement des données auxiliaires. Deux approches courantes sont les tables de référencement spécifiques à la fonction et le référencement générique.

Tables de référencement spécifiques aux fonctions

Les tables de référencement spécifiques à une fonction permettent de rattacher des données spécifiques à une fonction à une base de données cartographiques produite par tout fournisseur participant. Un tel tableau est produit de manière collaborative pour prendre en charge une fonction ou une classe de fonctions spécifique impliquant un service basé sur la localisation, une sécurité active ou une assistance à la conduite avancée. Il consistera généralement en une liste d'éléments cartographiques d'un type spécifique (par exemple, des liens, des intersections, des points d'intérêt, etc.) ainsi que des attributs d'identification (par exemple, des noms de rue, des coordonnées de longitude/latitude, etc.). De plus, chaque entrée du tableau se voit attribuer un identifiant unique. L'ensemble des entrées d'un tableau est généralement sélectionné, par consensus de toutes les parties intéressées. En pratique, le résultat représentera un petit sous-ensemble des éléments du type donné qui sont disponibles dans les bases de données cartographiques et se composera de ceux qui sont les plus importants pour le domaine d'application. Une fois le tableau élaboré, il appartient à chaque fournisseur participant de déterminer et de croiser les éléments de sa base de données cartographiques qui correspondent aux entrées du tableau.

Figure 2 : Emplacements TMC dans la région métropolitaine de Detroit

Un exemple largement utilisé est la norme TMC pour les tables de codes de localisation pour référencer les données de trafic. TMC, qui signifie Traffic Message Channel , fait partie du Radio Data System (RDS), qui est implémenté en tant que modulation de sous-porteuse d'un signal de diffusion FM commercial. Les tables TMC fournissent principalement des références aux emplacements des points le long des routes principales correspondant aux intersections avec d'autres routes. Une entrée de tableau identifie un emplacement de point en utilisant à la fois des informations contextuelles (telles que la région, la route et la section de route, le nom de l'intersection) et des coordonnées de longitude/latitude approximatives.

Les identifiants attribués aux entrées d'une table sont des entiers de 16 bits et ont donc une plage de 65536 valeurs. C'est trop peu pour couvrir le monde, donc des tableaux séparés sont formulés pour chaque pays ou région d'un pays. Pour une région métropolitaine donnée, seules les intersections le long des autoroutes, des artères et de certaines routes principales sont incluses. Ceci est illustré dans la figure suivante pour la région métropolitaine de Détroit. La couverture est destinée à fournir des informations d'avertissement de trafic sur les routes à forte fréquentation. La planification d'itinéraire basée sur le trafic, d'autre part, nécessite une couverture de toutes ou presque toutes les routes principales et, par conséquent, n'est pas suffisamment prise en charge par les tables de codes de localisation TMC telles qu'elles sont actuellement formulées.

Référencement générique

Le référencement générique est une tentative d'attacher des données à n'importe quelle base de données cartographique en découvrant des informations de référence via une forme de correspondance de carte. Les éléments de données spécifiques à une fonction sont attribués à des éléments, tels que des points, des liens ou des zones, qui se rapprochent probablement uniquement des éléments cartographiques correspondants dans une base de données cartographique spécifique. Une recherche dans la base de données cartographiques est effectuée pour le meilleur ajustement. Pour améliorer le processus de recherche, des éléments voisins sont stratégiquement ajoutés à chaque élément donné pour garantir que la bonne solution est trouvée dans chaque cas. Par exemple, si l'élément cartographique est un lien reliant deux intersections, alors une ou les deux rues transversales peuvent être ajoutées pour les besoins de la recherche. Espérons que cela rend peu probable une correspondance incorrecte. Bien que la procédure soit assez heuristique, une norme proposée appelée Agora décrit la stratégie de choix des éléments voisins à ajouter.

Consortium européen ActMAP

Un consortium européen appelé ActMAP (Actualize Map) est (selon leurs termes) « développer des mécanismes normalisés pour mettre à jour le contenu de la base de données cartographique existante et permettre l'attachement dynamique d'informations à la carte numérique embarquée ». Le consortium ActMAP comprend ERTICO (coordinateur), BMW, CRF Fiat Research Centre, DaimlerChrysler, Navigon, Navteq, Tele Atlas et Siemens VDO Automotive. Ils ont terminé la plupart de leurs travaux et publié un certain nombre de rapports, qui ont été soumis au comité ISO TC204 WG3 pour normalisation. Leurs rapports constituent un bon point de départ et une référence pour le travail de ce projet. Un problème important que leurs rapports traitent de la complexité de plusieurs fournisseurs de cartes, utilisant des formats propriétaires, associés à plusieurs fournisseurs de données et à plusieurs versions de cartes embarquées. Ils résolvent ce problème en utilisant un format de carte intermédiaire ouvert exprimé avec XML et basé sur les concepts de la norme ISO GDF 4.0. Toutes les modifications apportées à la base de données d'un fournisseur sont d'abord converties dans ce format intermédiaire, stockées sur un serveur, puis converties dans chaque format utilisé dans les véhicules individuels. Ils supposent que chaque voiture dispose d'une carte « de base » d'un fournisseur de cartes et que cette base définit des identifiants de référence (par exemple, un identifiant de segment de carte) pour la plupart des fonctionnalités à mettre à jour. Pour les entités sans identifiant de référence dans la ligne de base, ils proposent d'utiliser une référence "générique" qui est découverte de manière heuristique à l'aide de la correspondance de carte telle que décrite par une norme proposée appelée AGORA

Un problème majeur qui n'est pas directement traité par ActMAP est que pour chaque nouvelle version de la base de données cartographique d'un fournisseur, tous les identifiants de référence sont généralement réaffectés par un processus de compilation, ce qui détruit toute correspondance avec les identifiants des versions précédentes. Cela interfère sérieusement avec la possibilité d'utiliser des mises à jour incrémentielles pour générer une nouvelle version d'une base de données cartographiques à partir d'une version précédente. Un autre problème non résolu par ActMAP est l'incapacité de référencer et de caractériser des sous-sections de segments de route (par exemple, des courbes, des collines, des voies de manœuvre, etc.) afin de les mettre à jour.

Voir également

Les références

  1. ^ ISO 14825, Systèmes de transport intelligents - Fichiers de données géographiques (GDF) - Spécification globale des données, première édition 2004, Suisse, http://www.iso.org
  2. ^ Format d'échange standard (SIF), Navteq, Chicago, Ill, http://www.navteq.com/
  3. ^ GDF ASCII Sequential, Tele Atlas, "Copie archivée" . Archivé de l'original le 2008-08-27 . Récupéré le 2007-10-01 .CS1 maint: copie archivée comme titre ( lien )
  4. ^ "Norme de données de navigation" . NDS eV Récupéré le 2015-02-13 . Lien externe dans |publisher=( aide )
  5. ^ Navigon, http://www.navigon.com
  6. ^ Aisin, http://www.aisin.com/
  7. ^ Denso, http://www.denso-europe.com/Navigation--1002010000000001.aspx
  8. ^ ISO 14819, préparé par ISO/TC 204 "Services de transport intelligents", http://www.iso.org
  9. ^ ActMAP, Ertico, http://www.ertico.com/en/subprojects/actmap/objectives__approach/objectives__approach.htm Archivé 2007-04-07 à la Wayback Machine