Brevet FR2644263A1 — publié le 19900914

Procédé et dispositif d'acquisition et de stockage numérique de cartes géographiques en couleurs et de restitution de ces cartes L'invention concerne l'acquisition et le stockage numérique de cartes géographiques en couleurs et leur restitution. Les cartes géographiques traditionnelles sur papier répondent mal à de nombreux besoins qui se développent à l'heure actuelle, par exemple la prépa- 0 ration de missions à longue distance: chaque carte ne peut représenter qu'une surface très limitée, d'autant plus réduite que la carte est à grande échelle. Les discontinuités représentées par les frontières entre cartes gênent la préparation d'un plan global. Rien ne s'oppose en théorie à l'acquisition et au stockage numérique de cartes géographiques sur papier: il suffit d'une acquisition et d'une numéri- sation de pixels par balayage du type utilisé en télévision. Mais ce mode de stockage se heurte au problème du volume d'informations à mémoriser et, au surplus, ne résout pas le problème du passage d'une carte à une carte adjacente. L'invention vise à fournir un procédé d'acqui- sition et de stockage numérique de cartes géographiques réduisant très considérablement le volume d'informations à mémoriser et évitant toute discontinuité comparable à celles qu'on rencontre en passant d'une carte papier à une autre; elle vise au surplus à permettre une grande souplesse d'utilisation. Pour cela, l'invention utilise le fait que la résolution requise pour les pixels colorés (le nombre de couleurs utilisées sur une carte étant généralement faible et ne dépassant pas 8) est beaucoup plus faible que celle souhaitable pour les indications en noir (lignes de niveau, indications alphanumériques, repères,...) et qu'une dégradation des couleurs est peu gênante. L'invention propose en conséquence un procédé suivant lequel: (a) on numérise des cartes, chacune par balayage de type télévision pour la représenter par une matrice de pixels avec codage sur au moins trois couleurs fondamentales; (b) on classifie les pixels en les affectant à un nombre réduit de classes en fonction de leur couleur, ]o chaque pixel étant défini par un code ayant un nombre de -bits inférieur à celui nécessaire pour l'opération (a); (c) on constitue une mosaïque de cartes raccor- dées par ré-échantillonnage dans une grille commune de référence, en affectant avantageusement à chaque pixel ré-échantillonné la valeur pour le pixel le plus proche obtenu par l'opération (b); (d) on fractionne la mosaïque en pavés iden- tiques, ayant chacun un nombre prédéterminé de pixels; (e) on constitue un fichier couleurs de chaque pavé en (el) regroupant les pixels en macropixels de chacun n pixels adjacents (par exemple n = 4 pixels disposés en carré) et en affectant à chaque macropixel un seul code représentatif de classe puis (e2) en mémorisant, pour chaque ligne de macropixels, chaque segment de couleur constante sous forme du code de la classe du premier macropixel et du nombre de macropixels du segment; et (f) on constitue un fichier en noir et blanc de chaque pavé en mémorisant, pour chaque ligne, chaque segment noir sous forme de l'indication du premier pixel noir et du nombre de pixels du segment. L'invention sera mieux comprise à la lecture de la description qui suit d'un mode particulier de réalisation, donné à titre d'exemple non limitatif. La - description se réfère aux dessins qui l'accompagnent, dans-lesquels: - la Figure 1 est un logigramme de principe du procédé d'acquisition et de stockage - la Figure 2, complémentaire de la Figure 1, est un logigramme du procédé de restitution; - la Figure 3 est un schéma de principe montrant les composants matériels qui interviennent dans la restitution sur écran. Le procédé suivant l'invention comporte un certain nombre d'étapes dont certaines sont connues et, pour cette raison, ne feront pas l'objet d'une descrip- tion détaillée. 1. Dans le cas d'une acquisition à partir d'une carte papier, la première étape (désignée par 10 sur la Figure 1) consiste en une numérisation pour réaliser, à partir d'une carte en couleurs au moins trois fichiers correspondant aux trois couleurs de base. On peut notamment utiliser un scanneur qui, en trois passes, fournit trois fichiers obtenus par balayage du type télévision, constitués de pixels répartis de façon régulière. Un écartement entre lignes et entre pixels d'une même ligne de 0,1 mm sera généralement satis- faisant. Les trois couleurs de base seront en général celles utilisées pour la télévision, c'est-à-dire cyan, magenta et Jaune. Il est possible, bien que généralement superflu, de prévoir une passe supplémentaire destinée à constituer un fichier différenciant les pixels de ré- flectivité inférieure à un niveau déterminé, considérés comme "noirs", de tous les autres. A l'issue de cette étape, chacune des cartes à stocker est disponible sous forme de trois fichiers o chaque pixel est affecté d'un nombre qui sera par exemple de huit bits représentant une valeur radio- métrique (réflectivité par exemple) pour la couleur considérée. 2. Un premier codage consiste en une classifi- cation (12 sur la Figure 1) qui réduit le volume de données à mémoriser. La classification peut s'effectuer en deux phases, d'abord un calcul de signature, puis un codage proprement dit par application d'un algorithme de classification à maximum de vraisemblance. Le calcul des signatures se fait en déterminant des frontières optimales de classes. Il commence par le calcul d'un histogramme à trois dimensions correspondant aux trois couleurs de base, sur la totalité de la carte. Les frontières entre classes peuvent alors être déter- minées par segmentation de l'histogramme de façon à définir les classes les mieux appropriées à la nature des cartes individuelles d'origine (terrain représenté et mode de représentation). On peut notamment segmenter l'histogramme par l'algorithme des moyennes migrantes, qui est un algo- rithme itératif permettant de faire évoluer progressi- vement les frontières de classes en fonction de la répartition des points. Le nombre de classes est généralement défini a priori. Il est souhaitable de ne pas dépasser seize classes, de façon à pouvoir définir chaque pixel par un nombre de quatre bits. Pour des cartes relativement homogènes, huit ou dix classes suffisent. Il est souhaitable de vérifier que le choix de classes effectué se traduit, lors de la restitution, par une impression visuelle satisfaisante. Un apprentissage interactif peut être prévu. Il consiste à choisir une portion de référence, ou imagette, par exemple de 512 x 512 pixels, dans une carte représentative, cette portion étant choisie pour contenir des exemples de toutes les données graphiques et de toutes les couleurs. L'imagette est codée, puis restituée sur écran et l'opérateur la compare à l'original. Il peut alors modifier les signa- tures retenues pour écarter des défauts; par exemple constitués par des affectations qui donnent une im- pression subjective jugée non satisfaisante. Le codage proprement dit utilise une répartition entre les classes (certains pixels pouvant ne corres- pondre à aucune classe, ou au contraire à plusieurs classes et devant cependant être affectés). On peut notamment utiliser une classification à maximum de vraisemblance du genre décrit par exemple dans Duda et Hart, "Pattern classification and scene analysis", Wiley Jo & Sons, 1979, Ch. II. Divers modes de groupement ou "clustering" sont utilisables; par exemple on définit les limites de classe par un écart pour chacune des couleurs de base par rapport à une moyenne pour chaque classe (classification à parallélépipèdes). On peut notamment utiliser des classes correspondant à: blanc rouge gris clair vert gris foncé bleu noir Jaune La démarche ci-dessus suffit lorsque les cartes individuelles à assembler sont homogènes, c'est-à-dire ont des contrastes comparables et des couleurs dont la nuance varie peu. Cette situation favorable se rencontre lorsque les cartes appartiennent à un même lot de fabrication. Dans d'autres cas, il n'est plus possible d'obtenir des résultats satisfaisants avec un nombre de classes réduit. On peut alors être amené, même pour des cartes n'ayant que quelques couleurs, à faire une répartition en un nombre de classes plus élevé. Ces classes sont définies par l'opérateur: celui-ci examine préalablement, éventuellement hors ligne, toutes les cartes individuelles à assembler en mosaïque, et détermine par tâtonnements quel nombre de classes (et quelles signatures de classes) donne le meilleur résultat sur les imagettes sélectionnées. 3. L'assemblage de cartes individuelles en une carte mosaïque permet de résoudre le problème posé par les recouvrements de cartes adjacentes et, surtout, par le fait que les cartes individuelles sont échantillon- nées régulièrement suivant leur surface, et non pas dans une projection commune à toutes les cartes individuelles à assembler. L'assemblage en mosaïque 14 consiste à ré- échantillonner les cartes individuelles dans une projec- tion commune, qui peut être celle d'une des cartes. Elle implique: - de saisir des points caractéristiques sur chacune des cartes élémentaires codées par classifica- tion, ces points caractéristiques pouvant être ceux d'un quadrillage géométrique ou UTM; - de calculer les coordonnées de ces points caractéristiques dans la carte mosaïque résultant de l'assemblage des cartes individuelles et d'en déduire des opérateurs de déformation, opérant par exemple par régression polynomiale de degré faible, toujours inférieur à 6; - de ré-échantillonner chacune des cartes individuelles, pour disposer, dans chaque carte, de pixels régulièrement répartis dans la projection commune. Le ré-échantillonnage peut être effectué de façon simple, en utilisant l'algorithme du plus proche voisin, consistant à affecter chaque pixel de la projection commune à la classe du pixel le plus proche dans la carte individuelle correspondante (ou l'une des cartes individuelles en cas de recouvrement). La déformation subie au cours de cet assemblage est toujours suffisamment faible pour que la taille du pixel ne soit pas significativement modifiée. 4. Pour des raisons de facilité d'affichage lors de la restitution, il est commode d'organiser la carte mosaIque en 'pavés" correspondant à une fraction seule- ment d'une carte élémentaire et n'occupant qu'une frac- tion d'un écran de visualisation standard. Un découpage 16 en pavés de 512 x 512 pixels donne généralement des J0 résultats satisfaisants. 5. Il est nécessaire d'avoir une résolution élevée pour les graphismes et les inscriptions alpha- numériques en surcharge sur la carte, alors qu'une résolution plus faible est acceptable pour les plages simplement colorées: le codage 18 tient compte de cette différence. On représente en conséquence chaque pavé par un fichier intermédiaire "noir" à résolution correspondant à la taille d'un pixel (0,1 mm par exemple) et un fichier intermédiaire "couleurs" à résolution réduite, correspondant à la taille d'un "macro-pixel" regroupant plusieurs pixels, quatre par exemple. Dans le fichier "noir", un bit suffit pour identifier la valeur radiométrique du pixel (noir ou blanc); en affectant chaque macro-pixel à une classe, il suffit de quatre bits pour chaque macro-pixel, ce qui correspond & un bit par pixel. On peut dans certains cas accepter une visuali- sation complète à résolution réduite, correspondant à la taille d'un macro-pixel de 0,2 x 0,2 mm. Pour qu'elle soit meilleure, la matrice de pixels noirs peut être fractionnée en carrés de taille correspondant à celle des macro-pixels; dans le fichier, un des pixels de chaque carré (le pixel en haut et à gauche par exemple) est affecté à une classe définie, non par sa valeur réelle, mais par une valeur calculée à partir des quatre pixels (en 22 sur la Figure 1). Dans le fichier "couleurs" 20, chaque macro- pixel est calculé à partir des quatre pixels corres- pondants par un opérateur faisant intervenir une table de priorité des couleurs. Cette table peut être définie, pour chaque cas particulier, par l'opérateur, mais toujours sur la base de la même règle générale, à savoir qu'on affecte une priorité à la couleur la plus signi- ficative, c'est-à-dire la plus riche en information. Cela revient en pratique à adopter les priorités décroissantes suivantes: - couleur du texte et des surcharges, - couleur affectée aux éléments de petite surface ou linéaires, - autres couleurs, par ordre d'importance. On peut notamment, sur une carte o les courbes de niveau sont en noir, adopter l'ordre de priorités décroissantes suivant pour les couleurs: couleur affectée à des inscriptions ou symboles, - couleur affectée au réseau routier, - couleur affectée au réseau hydrographique, - couleur affectée aux forêts, - couleurs de fond. Cette démarche permet d'obtenir une restitution beaucoup plus satisfaisante qu'un sous-échantillonnage retenant un pixel couleur sur n. 6. Une compression finale utilise le fait que, le long d'une ligne de balayage, une même couleur peut exister sur une distance importante. Chaque fichier noir peut notamment être comprimé par codage des longueurs de plages noires et blanches le long de la direction de balayage lors de la numérisa- tion, en identifiant le premier pixel et les nombres de pixels avant passage au noir ou hors noir (ou inverse- ment). Dans la pratique, cette compression finale permet de réduire le volume de stockage à 0,38 bit/pixel dans le fichier "noir". Le fichier couleur de chaque pavé peut faire l'objet d'une compression similaire 26, en mémorisant le chiffre indiquant la classe de chaque pixel au début de chaque segment de couleur uniforme, et le nombre de pixels de la plage qui suit. Du fait que les plages colorées sont plus nom- breuses et de plus grande surface que les plages noires, on arrive, dans un cas représentatif, à mémoriser le fichier sous une forme qui conduit à 0,25 bit/pixel, soit 1 bit/macro-pixel. La mémorisation complète corres- pond alors à 0,63 bit/pixel. On dispose finalement, pour chaque pavé, de deux fichiers 28 qui peuvent être stockés dans une mémoire adressable de grande capacité (disque dur par exemple) contenant tous les fichiers de la mosaIque. Le procédé peut être mis en oeuvre à l'aide d'une chaîne de production dont l'organe d'entrée est constitué par un scanneur. Ce scanneur peut être disjoint du reste de la chaîne qui reçoit alors direc- tement, sur des supports de données à grande capacité, les fichiers de représentation des cartes papier en trois couleurs fondamentales. La chaîne peut alors être utilisée aussi bien pour l'acquisition que pour la restitution, avec simplement adjonction d'une carte électronique spécifique à la fonction de restitution. La restitution en temps réel s'effectue par un processus inverse du précédent. Elle sera décrite tout d'abord dans le cas o elle s'effectue avec une réso- lution de 0,1 mm/pixel, sur une chaîne ayant la constitution de principe montrée en Figure 3. La chaîne de la Figure 3 comporte une unité centrale de calcul 30 munie d'une unité 32 de disque dur constituant mémoire à grande capacité de stockage des fichiers 28. L'unité de calcul est munie d'une mémoire vive d'affichage 34 de capacité suffisante pour contenir au moins le nombre de pavés nécessaire pour constituer l'image sur un écran de visualisation 36. Sur la Figure 3 sont schématisés une mémoire vive 34 ayant une capa- cité de neuf pavés 38 et, en superposition, le contenu de la mémoire d'écran correspondant à la zone à visualiser. L'unité de calcul 30 est munie d'organes d'entrée constitués par un clavier 42 et une souris 44 permettant par exemple de désigner un point à amener au milieu de l'écran, par modification du contenu de la mémoire d'écran sous la commande de l'unité de calcul 30 qui, si nécessaire, transfère de nouveaux pavés de l'unité de disque 32 à la mémoire vive 34. En d'autres termes, la mémoire vive d'affichage 34 est mise à jour en permanence en réponse aux commandes de déplacement dans la carte mosaïque introduites par l'opérateur. L'unité de calcul 30 non seulement assure la sélection des pavés, mais aussi traite les informations prélevées dans l'unité de disque 32 avant de les inscrire dans la mémoire vive d'affichage 34, afin qu'elles soient directement utilisables par la mémoire d'écran. La sélection 46 est effectuée par l'utili- sateur. Les pavés correspondants sont adressés dans l'unité de disque 32 et les deux fichiers 28 de chaque pavé sont traités en parallèle. Pour chaque fichier, une décompression 48 restitue les pixels noirs et les macropixels couleurs. Les pavés noirs sont décomprimés et amenés au format de balayage de type télévision avant d'être écrits dans la mémoire d'affichage. Les pavés couleurs sont traités de la même façon mais, de plus, les macropixels sont sur-échantillonnés en 50 par duplication, pour restituer des pixels de méme taille que les pixels noirs. Enfin, les pixels noirs sont incrustés dans les pavés couleurs correspondants. La décompression est effectuée par une carte spécifique de restitution inclue dans la chaine et qui n'intervient qu'au cours de la restitution. Lorsqu'une définition correspondant à la taille d'un macropixel est suffisante, l'étape 50 est omise mais par contre un étape supplémentaire 52 de traitement du fichier "noir" est prévue: seuls sont retenus les pixels provenant du fichier "noir" qui ont été obtenus à partir des valeurs radiométriques d'un groupe de quatre pixels. En d'autres termes, il y a sous-échantillonnage (une colonne sur deux et une ligne sur deux). La valeur du pixel retenu est affectée à un macropixel complet. Le pavé reconstitué est dans tous les cas transféré à sa place dans la mémoire d'affichage. On voit que l'unité de calcul 30, l'unité de disque dur 32, le clavier de commande 42 et l'écran de visualisation 36 de la chaîne sont utilisables aussi bien pour l'acquisition que pour la restitution; une carte supplémentaire spécifique à la restitution est nécessaire. La mise en oeuvre des algorithmes de prépa- ration des pixels noirs en vue de leur restitution avec une définition égale à celle d'un macropixel peut s'effectuer par logiciel. La réduction du volume de données à stocker apparaît lorsqu'on considère un exemple représentatif, constitué par l'acquisition de cartes au 1/50000 du type IGN, avec une définition au pas de 0,1 mm/pixel. La numérisation classique en trois couleurs de base exige un stockage de 20.106 pixels. Le codage par classifi- cation permet d'atteindre un taux de compression de 6. La constitution de deux fichiers, l'un noir, l'autre couleurs, permet de doubler le taux de compression sans perte significative de visibilité. Enfin, grâce à la compression par segments, on peut atteindre un taux global de compression de l'ordre de 38, c'est-à-dire mémoriser l'ensemble de la carte à l'aide de 1,6.106 octets, au lieu de 60.106 dans le cas d'une numérisation directe. REVENDICATIONS 1. Procédé d'acquisition et de stockage numé- rique de carte géographique en couleurs, caractérisé en ce que: (a) on numérise des cartes, chacune par balayage de type télévision pour la représenter par une matrice de pixels avec codage sur au moins trois couleurs fondamentales; (b) on classifie les pixels (12) en les affectant à un nombre réduit de classes en fonction de leur couleur, chaque pixel étant défini par un code ayant un nombre de bits inférieur à celui nécessaire pour l'opération (a); (c) on constitue une mosaIque de cartes raccor- dées (14) par ré-échantillonnage dans une grille commune de référence, en affectant avantageusement à chaque pixel ré-échantillonné la valeur pour le pixel le plus proche obtenu par l'opération (b); (d) on fractionne la mosaïque en pavés iden- tiques (38), ayant chacun un nombre prédéterminé de pixels; (e) on constitue un fichier couleurs de chaque pavé en (el) regroupant les pixels en macropixels de chacun n pixels adjacents et en affectant à chaque macropixel un seul code représentatif de classe puis (e2) en mémorisant, pour chaque ligne de macropixels, chaque segment de couleur constante sous forme du code de la classe du premier macropixel et du nombre de macropixels du segment; et (f) on constitue un fichier en noir et blanc de chaque pavé en mémorisant, pour chaque ligne, chaque segment noir sous forme de l'indication du premier pixel noir et du nombre de pixels du segment. 2. Procédé selon la revendication 1, caractérisé en ce qu'on constitue chaque macropixel de quatre pixels disposés en carré. 3. Procédé selon la revendication 2, caractérisé en ce qu'on substitue, dans le fichier en noir et blanc, à un pixel prédéterminé dans chaque macropixel, une valeur obtenue à partir des quatre pixels constituant le macropixel. 4. Procédé selon la revendication 1, 2 ou 3, caractérisé en ce que les classes sont déterminées par l'algorithme des moyennes migrantes sur l'histogramme à 0 trois dimensions de répartition des couleurs dans une carte ou un groupe de cartes. 5. Procédé selon la revendication 4, caractérisé en ce que le nombre de classes est inférieur à 16 dans le cas de cartes en huit couleurs. 6. Procédé selon l'une quelconque des revendica- tions précédentes, caractérisé en ce qu'on visualise une zone de carte sur l'écran à partir des fichiers obtenus par mise en oeuvre du procédé selon l'une quelconque des revendications précédentes, les pavés recouvrant la zone à visualiser, et en soumettant ces pavés successivement à une expansion, un sur-échantillonnage du fichier couleurs et une incrustation des pixels noirs. 7. Dispositif d'acquisition et de stockage numérique de cartes géographiques, caractérisé en ce qu'il comprend: (a) des moyens pour numériser des cartes, chacune par balayage de type télévision pour la - représenter par une matrice de pixels avec codage sur au moins trois couleurs fondamentales; (b) des moyens de classification des pixels (12) en les affectant à un nombre réduit de classes définies par une signature, suivant un critèrede maximum de vraisemblance, chaque classe étant définie par un code ayant un nombre de bits inférieur à celui nécessaire pour l'opération (a); (c) des moyens pour constituer une mosaïque de cartes raccordées (14) par ré-échantillonnage dans une grille commune de référence; (d) des moyens pour fractionner la mosaïque en pavés identiques (38), ayant chacun un nombre prédéter- miné de pixels; (e) des moyens pour constituer un fichier cou- leurs de chaque pavé en regroupant les pixels en macro- pixels de chacun n pixels adjacents et en affectant à chaque macropixel un seul code représentatif de classe puis en mémorisant, pour chaque ligne de macropixels, chaque segment de couleur constante sous forme du code de la classe du premier macropixel et du nombre de macropixels du segment et pour constituer un fichier en noir et blanc de chaque pavé en mémorisant, pour chaque ligne, chaque segment noir sous forme de l'indication du premier pixel noir et du nombre de pixels du segment; et (f) des moyens d'écriture des fichiers dans une mémoire de masse à adressage des pavés.