Brevet FR2837949A1 — publié le 20031003

revendications 1 à 6. r 1 2837949 PROCEDE POUR LA VISUALISATION D'UNE IMAGE GEOGRAPHIQUE SEMI-REELLE. La présente invention concerne le domaine de l'imagerie de synthèse et plus particulièrement celui de la création de paysage numérique par exploitation de base d' images satellitaires par exemple ou topographique par exemple. Le brevet américain US4868771 ou européen EP285381B1 décrit une méthode et un système de génération d'images visuelles. Il concerne un système de création d' image visuelle par ordinateur destiné à créer des images visuelles à partir de données mémorisées, dans lequel une caractéristique de l' image est définie par au moins un polygone (18, 20). Le procédé produit des images visuelles qui reflètent l' interaction en temps réel entre une maquette de véhicule ayant un voisinage prédéterminé et un paysage ayant une topographie prédéterminée, dans lequel la maquette de véhicule peut se déplacer dans n'importe quelle direction à travers le paysage Le procédé comprend: - l'échantillonnage en temps réel des données mémorisées pour la topographie du paysage en avant de la maquette de véhicule dans la direction de déplacement de la maquette de véhicule pour obtenir au moins un échantillon représentatif de la topographie, cette topographie ayant un contour, - la détermination de l' interaction entre la topographie du paysage et la maquette de véhicule en réponse a l'un au moins des échantillons de données mémorisoes, et - la modification de l' image du paysage a afficher par rapport à un point d' observation prédéterminé en réponse a l' interaction déterminée. l 2 2837949 Le brevet européen EP311081 ou américain US4994989 décrit un dispositif pour afficher un modèle tridimensionnel d'un objet comportant: - a) une mémoire adaptée pour mémoriser des informations détaillées de modèle tridimensionnel d'un objet, lesdites informations comportant au moins un élément parmi - i) plusieurs dimensions, et - ii) plusieurs paramètres, et - iii) les grandeurs desdits paramètres, - b) un processeur étant - i) adapté pour accéder à ladite première mémoire, et - ii) adapté pour calculer des informations simplifiées de modèle tridimensionnel sur la base des informations détaillées de modèle tridimensionnel, - c) un processeur d'affichage adapté pour afficher des modèles tridimensionnels en des points (Ps) de l'écran d'affichage au niveau desquels une ligne située entre le modèle tridimensionnel à afficher et un point de visée extérieur (Pv) situé dans l'espace tridimensionnel recoupe l'écran d'affichage, de sorte que lesdits modèles affichés occupent un certain pourcentage de ladite surface dudit écran d'affichage, et - d) un sélecteur adapté pour sélectionner lequel parmi ledit modèle tridimensionnel détaillé et ledit modèle tridimensionnel simplifié doit être affiché par ledit processeur d'affichage sur ledit écran d'affichage sur la base d'un seuil de perception visuelle prédéterminé. Le problème posé par les solutions de l'art antérieur est qu'ils nocessitent des ressources importantes très importantes pour mémoriser et traiter en temps réel les données topographiques. Le but de la présente invention est de proposer un procédé permettant r r 3 2837949 de réaliser des représentations de très grande qualité, d'un rendu très réaliste, sur des équipements informatiques classiques tels que des ordinateurs destinés à des usages personnels ou bureautique. Les images de synthèses et les mondes virtuels manquaient à nos yeux d'un élément important: l'abondance et la complexité. Vu que la modélisation de ces univers est effectuée méticuleusement par des infographistes, plus ils sont grands et fournis, plus ils sont coûteux à générer. L'invention concerne un procédé informatique qui permet de faire " fabriquer " automatiquement par l'ordinateur des univers virtuels.; Elle met en _uvre des données qui expriment des éléments existants réellement (cartographie satellite de tout type) et des technologies fractales pour générer des rendus visuels qui imitent la réalité. La présente invention concerne selon son acception la plus générale un procédé pour la visualisation d'une image géographique semi-rcelle par; traitement logiciel d'une base d' information géographique de résolution N. constitué par une table contenant pour chaque pixel désigné par ses coordonnées une information représentative de l' altitude, caractérisé én ce que le procédé comporte une étape initiale de préparation d'une base géographique comprimée comprenant au moins une table de travail optimisée Tk, consistant à explorer la zone correspondante de la table complète, à lire la valeur Y(Xi Zj), à substituer dans une mémoire tampon les valeurs Ymin, YmaX si ladite valeur Y est respectivement supérieure ou inférieure auxdites valeurs mémorisées, à déterminer le nombre de bits P nécessaire pour coder la valeur AY correspondant à la différence des deux valeurs mémorisées à la fin de l' exploration de ladite zone, et à remplacer chacun des valeurs Y(xi Zj) par une valeur Yc(xi Zj) pour 4 2837949 reconstruire une table Tk optimisée associée à un descripteur du mode de codage des valeurs qu'elle contient. On entend au sens du présent brevet par " image géographique " une image de synthèse, numérique, représentant un paysage, un panorama, une vue topographique texturce. Selon un exemple de mise en _uvre, le calaul d' extrapolation consiste à déterminer la moyenne de la courbe passant par un ensemble d'au moins deux pixcls encadrant le pixel considéré. Selon une variante, ladite étape initiale comporte, un changement de référentiel pour minimiser le poids des valeurs Y(xi Zj) et la construction d'une base de système d' information géographique comportant une pluralité de tables optimisées associée chacune à un descripteur du mode de codage et du référentiel. Selon une autre variante, ladite étape initiale comporte, un comptage du nombre d' occurrence successives correspondant à la même valeur Y(xi Zj), l'enregistrement dans la table optimisée de ladite valeur et du nombre d' occurrences associé, et la construction d'une base de système d' information géographique comportant une pluralité de tables optimisées associée chacune à un descripteur du mode de codage et du référentiel. Selon un mode de réalisation préféré, la base de système d' information géographique occupe moins de 500 Méga octets pour la représentation du globe terrestre en projection de Mercator. De préférence, la base de système d' information géographique est divisoe en tables de 32x32 pixels. =? --: 2837949 Selon une variante préférée, la base de système d' information géographique correspond à une résolution d'environ 30' d'arc. Selon un mode de mise en _uvre particulier, le procédé selon l' invention comporte une étape de construction d'une table de travail locale T1 enregistrée en mémoire vive, par compression d'une partie de la base de système d' information géographique, consistant à procéder à une extraction périodique d'informations de ladite base réduite, la résolution Rt(Yo) de ladite table de travail Tl étant déterminée en fonction d'un paramètre représentatif de l' altitude YO de l' observateur virtuel, le procédé comportant des étapes ultérieures de calcul d'une représentation graphique en forme de squelette 3D [meshes] en fonction du contenu de ladite table de travail. Selon une première variante, il comporte une étape de construction d'une table de travail locale T1 enregistrée en mémoire vive, par expansion d'une partie de la base de système d' information géographique, consistant à procéder à une lecture séquentielle des valeurs YRi(x, z) de la table, à réaliser après chaque lecture d'un couple de deux valeurs consécutives une interpolation pour les coordonnces intercalaires, et à construire une table locale expansée comportant les valeurs YRi(x, z) réelles issues de la base réduite et les valeurs Yi(x, z) extrapolées. Avantageusement, le calcul d' extrapolation consiste à déterminer la moyenne entre les valeurs des deux pixels consécutifs. Selon une variante, le calcul d' extrapolation consiste à appliquer une fonction de lissage dépendant du sens de variation des valeurs de la table. Selon un mode de mise en _uvre préféré de l'invention, le calcul d'extrapolation consiste à 6 2837949 appliquer à la valeur obtenue une valeur pseudo-aléatoire issue d'une table comprenant M2 valeurs aléatoires [Rnd (X modM, Z mod M)]. Selon une variante, l'étape initiale comporte, pour chaque table de travail, une boucle récursive consistant à augmenter la résolution jusqu'à ce qu'elle soit supérieure à une valeur seuil Di déterminée, par un doublement de la résolution et une division par 2 du facteur Di1 enregistré pendant l'itération précédentes, et à comparer la valeur Doi = Yo-Y1 à la valeur Di jusqu'à ce que cette dernière soit supérieure à Doi. Selon une variante, il comporte une étape d'assignation à chaque pixel de la table de travail d'une valeur de couleur correspondant à la valeur issue de la base de système d' information géographique ou à une valeur extrapolée pour les pixels extrapolés. L' invention sera mieux comprise à la lecture de la description qui suit, se référant aux dessins annexés relatifs à un exemple non limitatif de réalisation. Le procédé de génération d' image comporte une succession d'opération. Globalement, une boucle principale du procédé effectue les étapes suivantes: À Fabriquer une base topographique de la zone autour du point d' observation À Fabriquer un meshe à partir de cette zone À Fabriquer les textures À Appliquer les textures À Effectuer les divers effets spéciaux (soleil, heure, ombres, etc.) À Projection 3D/2D & Affichages À Attendre instructions de déplacement À Libérer les tampons mémoires. 7 2837949 Opération de constitution d'une base de système d' information géographique Une première opération concerne la décompression par création. En informatique, la compression de donnée est es sent iel le pour réduire les coûts de stockage et accroître la rapidité des manipulations. Jusqu'à présent, on a cherché à réduire des éléments initialement grands. L'invention augmente un élément initialement petit. La compression classique, sans destruction, possède ses limites. Dans l'état actuel des connaissances, des données d'un certain type pourront être compressées jusqu'à un certain seuil (40% pour une photographie, 20% pour un échantillon sonore, etc. Les méthodes de compressions JPEG, MPEG, MP3, MP4, etc., offrent des taux de compression bien supérieurs mais ils détruisent le document original. Dans ces principes, le tout est de juger un seuil limite de destruction, pour qu'il reste imperceptible à l'il ou à l'oreille. Notre méthode de " décompression " ne possède pas de limite: A partir d'un ensemble de données initiales, d'un volume fini, on engendre un ensemble de données d'un volume infini. On peut prendre pour exemple un " ensemble de Mandelbrot ". On le sait, cette image est générée par un simple système d'équations dont le code tient dans quelques dizaines de Kilo-octets. Ainsi, à partir de données d'un volume de 58Ko (la taille du programme qui a généré cette image), on peut obtenir une richesse quasiment infinie si l'on essayait de ré-effectuer les calculs en " zoomant " sur l' image: La limite réside seulement dans la précision des calauls: En utilisant des nombres flottants définis sur une mantisse 64 bits (comme c'est le cas dans notre 8 2837949 programme de 58Ko), l' image zoomée qui peut être générée fera une taille d'environ 17 millions de milliards pixels de côté. Si l'on recompile le programme en utilisant des nombres flottants à mantisse 128 bits (ce qui S n'augmenterait guère sa taille initiale), on obtiendrai la possibilité de visualiser une image cohérente, possédant plus de pixcls qu'il n'y a d'atomes dans l'univers. Bref, de 58Ko, on génère l'infini. Opération de création des meshes Le terme " meshes " est le terme utilisé pour désigner le " squelette " 3D d'un objet ou d'un terrain: c' est la description de tous les polygones qui le constitue (chaque polygone est définis par 3 ou 4 points, eux-mêmes définis par trois coordonnées x, y, z), et uniquement les polygones (sans les textures). Il s'agit de plusieurs listes de donnces, une liste de points (x, y, z), une liste de polygones constitués de points, une liste d'objets constitués de polygones,: À point n l: 10,15,30 À point n 2: 25, 40,21 À point n 3: -12,0,15 À point n 4: 25,26,84 etc. À polygone n l: point n l, point n 2, point n 4 À polygone n 2: point n 3, point n l, point n 4 À polygone n 3: point n l, point n 2, point n 5 30... etc. À objet n l: polygone n l situé en x,y,z, polygone n 2 situé en x,y,z À objet n 2: polygone n 2 situé en x,y,z, polygone n 4 situé en x,y,z 9 2837949 À objet n 3: polygone n 3 situé en x,y,z, polygone n 4 situé en x,y,z etc. La modélisation d'un objet donne, entre S autres, un " meshe ". La technologie va donc créer automatiquement le meshe représentant la planète composée de polygones d'un mètre de côté (résolution minimale pour les polygones = 1 m, et 1 cm pour les pixels de textures). L'une des difficultés rencontrée est celle de la gestion de l'abondance. Il faudrait environ 510 mille milliards de polygones de 1 mètre de côté pour modéliser toute la Terre. Bien entendu, une telle base (un tel " meshe ") est totalement impossible à mettre en place, même si on la générait automatiquement, il faudrait presque 3000 tetra-octets pour la stocker! Pour gérer cette abondance, nous sommes part i s de quelques constatat ions: Première constatation: Quel que soit l'endroit dans l'espace o l'on se trouve, on ne " voit " touj ours qu'une partie limitée d'une telle base. La technologie ne va donc générer que les parties de cette base dont elle a besoin à un instant T et, lors d'un déplacement, détruire ce qu'elle vient de générer pour recréer une nouvelle partie, le tout en temps récl, constamment et au fur et à mesure des déplacements. Deuxième constatation: A hauteur d'homme, on a besoin de générer un espace de quelques kilomètres seulement (généralement, on ne voit pas au-delà). On a également besoin d'une bonne résolution (donc beaucoup de polygones) aux alentours proches du point d'observation, mais les polygones les plus éloignés du point d' observation peuvent être en nombre plus faibles et de 2837949 taille plus importante puisque après projection, ils auront une taille apparente similaire à celle des polygones proches, comme représenté en figure 1. A hauteur d'avion, puisqu'on est élevé, il faut générer un terrain plus vaste (quelques dizaines ou centaines de kilomètres en fonction de l'altitude). Cependant, le détail au sol (à la verticale du point d'observation) n'a pas besoin d'être finement défini, comme représenté en figure 2. En vue depuis l'espace, la zone est très vaste mais uniformément définie avec de grands polygones de même taille (figure 3). Finalement, quelle que soit la position du point d' observation, on n'utilise qu'un nombre fini (et raisonnable) de polygones pour modéliser le terrain. De plus, ce nombre est touj ours pratiquement identique, que l'on soit à hauteur d'homme ou en vue satellite. Opération de fabrication d'un monde d'apparence naturelle On a vu comment se faisait le découpage des polygones, il s'agit maintenant de leur donner des orientations et des altitudes judicieuses afin d'obtenir un " meshe " représentant un terrain d'apparence naturelle. Pour ce faire, on utilise le principe fractale " Landecape ": Une première zone existe (On verra plus loin que cette zone est en fait lue dans les bases de donnces topographiques existantes de la Terre), formé par 4 points (figure 4). On coupe la zone en 4 zones plus petites, de tailles identiques et on fait un tirage aléatoire pour attribuer l'altitude du point milieu (figure 5). Chaque zone est découpée de la même manière, avec, de nouveau, un tirage aléatoire définissant quatre nouveaux points d'altitude. Les tirages aléatoires sont effectués dans des limites définies par les altitudes des zones " pères " (figure 6). On répète l'opération un certain nombre de fois, on parle " d'itérations ", c'est la base du calcul fractal et on obtient finalement un " landecape " comme représenté en figure 7. Opération de fabrication des terrains à partir de donnces existantes. Les deux principes fondamentaux étant énoncés (choix du nombre de polygones et création d'un landecape fractal), voyons maintenant précisément ce que fait la technologie. Ces deux principes sont appliqués tout en utilisant une base réelle de données topographiques. On utilise la base " GTOPO30 " de 1' USGS (hÈtp://edcdaac.usgs.gov/gtopo30/gtopo30. hÉml) Celle-ci nous donne, pour toute la superficie de la Terre, une élévation exacte au mètre près pour chaque kilomètre carré (928 x 928 mètres exactement). Les informations recueillies dans cette base de données, comme celles de toute autre base existante ont bien entendu une précision limitée, plus ou moins fine. Cependant, l'objet de notre technologie et son principal atout est justement de pouvoir visualiser la Terre (ou d'autres planètes existantes et même imaginaires) à n'importe quelle échelle, depuis l'espace, jusqu'au sol, à hauteur d'une pâquerette. I1 n'existe aucune base de données suffisamment précise et même s'il elle existait, son volume dépasserait tout entendement, ce qui la rendrait inexploitable. Nous utilisons donc une base, qu'on qualifie de " grossière " et on extrapole les détails qui n'existent pas dans cette base. En d'autres termes, on effectue un zoom dessus en " inventant " de nouvelles données. 12 2837949 Ainsi, la base GTOPO30, vue depuis une hauteur de satellite, est utilisée telle quelle car le résultat est satisfaisant. La figure 8 représente un échantillon o chaque pixel donne une élévation par son niveau de gris. Mais, si le point d'observation descend, sans traitement, le résultat devient vite insatisfaisant. Ainsi, cette base de données doit être lue de différentes manières, fonction de l' altitude du point d' observation. A des altitudes élevées, il faut lire une information sur 4 par exemple, a de basses altitudes, il faut " extrapoler " l' information qui n'existe pas. - La figure 9 correspond à un zoom sur l' image en créant de l' information en utilisant des procédés fractals. Prenons par exemple, un échantillon d' information de la base depuis l' image initiale. Le seul élément que l'on connaît est que chaque information (les 4 valeurs de gris), sont des moyennes des véritables informations sous-jacentes. Après avoir effectué un niveau de zoom et créer par calcul fractal les informations de transition " supposées être vraies " entre les 4 pixels de l' image précédente, on obtient ceci une image représentée en figure 10. Le calcul fractal ne se contente pas de calculer des moyennes, il introduit aussi des " accidents " naturels et permet d'obtenir des informations extrapolées telles que représentées en figures 11 et 12 (en répétant le traitement défini ci dessus). On crée donc à chaque instant, une nouvelle base de données extrapolée depuis la GTOPO30, en plus grossier (une information sur 2 par exemple si le point d'observation est très élevé) ou en plus fin si le point d'observation est bas. On obtient une nouvelle liste de : :13 2837949 points d'élévation à partir desquels on fabrique un " meshe " (figure 13). i 14 2837949 REVEND I CAT I ONS 1 - Procédé pour la visualisation d'une image géographique semi-réelle par traitement logiciel d'une S base d' information géographique de résolution N. constitué par une table contenant pour chaque pixel désigné par ses coordonnées une information représentative de l'altitude, caractérisé en ce qu'il comporte une étape de construction d'une table de travail locale T1 enregistrée en mémoire vive, par expansion d'une partie d'une base de données d'un système d' information géographique d'une résolution déterminée, consistant à procéder à une lecture séquentielle des valeurs YRi(x, z) de la base, à réaliser, après chaque lecture d'un couple de deux valeurs consécutives, une interpolation pour les coordonnées intercalaires, et à construire une table locale expansée comportant les valeurs YRi(x, z) réelles issues de la base réduite et les valeurs YEi(x, z) extrapolées. 2 - Procédé pour la visualisation d'une image géographique semi-réelle selon la revendication 1, caractérisé en ce que le calcul d' extrapolation consiste à déterminer la moyenne de la courbe passant par un ensemble d'au moins deux pixels encadrant le pixcl , , consldere. 3 Procédé pour la visualisation d'une image géographique semi-réelle selon la revendication 2, caractérisé en ce que le calaul d' extrapolation consiste à appliquer une procédure de lissage dépendant de la variation des valeurs de la table. 4 - Procédé pour la visualisation d'une image géographique semi-réelle selon la revendication 3, caractérisé en ce que la procédure de lissage consiste à explorer la table aléatoire, pour l' entourage d'une zone à variation de relief, et à déterminer une valeur de rugosité en fonction de la dénivellation au moins. - Procédé pour la visualisation d'une image géographique semi-réelle selon l'une quelconque des revendications précédentes, caractérisé en ce que le calcul d'extrapolation consiste à appliquer à la valeur obtenue une valeur pseudo-aléatoire issue d'une table comprenant M2 valeurs aléatoires [Rnd (X modM, Z mod M)]. 6 - Procédé pour la visualisation d'une image géographique semi-réelle selon l'une quelcouque des revendications précédentes, caractérisé en ce qu'il comporte une étape initiale comporte, pour chaque table de travail, une boucle récursive consistant à augmenter la résolution jusqu'à ce qu'elle soit supérieure à une valeur seuil Di déterminée, par un doublement de la résolution et une division par 2 du facteur Di1 enregistré pendant l'itération précédentes, et à comparer la valeur Doi = Yo-Y1 à la valeur Di jusqu'à ce que cette dernière soit supérieure à Doi. 7 - Procédé pour la visualisation d'une image géographique semi-rcelle selon lune quelconque des revendications précédentes, caractérisé en ce qu'il comporte une étape d' assignation à chaque pixel de la table de travail d'une valeur de couleur correspondant à la valeur issue de la base de système d' information géographique ou à une valeur extrapolée pour les pixels extrapolés, pour la création de la topographie et de la texture. 16 2837949 8 - Procédé pour la visualisation d'une image géographique semi-réelle selon l'une quelconque des revendications précédentes, caractérisé en ce que le procédé comporte une étape initiale de préparation d'une base géographique comprimée comprenant au moins une table de travail optimisée Tk, consistant à explorer la zone correspondante de la table complète, à lire la valeur Y(xi Zj), à substituer dans une mémoire tampon les valeurs Ymin, YmaX si ladite valeur Y est respectivement supérieure ou inférieure aux dites valeurs mémorisées, à déterminer le nombre de bits P nocessaire pour coder la valeur AY correspondant à la différence des deux valeurs mémorisées à la fin de l'exploration de ladite zone, et à remplacer chacun des valeurs Y(x: Zj) par une valeur Yc(xi Zj) pour reconstruire une table Tk optimisée associée à un descripteur du mode de codage des valeurs qu'elle contient. 9 - Procédé pour la visualisation d'une image géographique semi-réelle selon la revendication 8, caractérisé en ce que ladite étape initiale comporte, un changement de référentiel pour minimiser le poids des valeurs Y(xi Zj) et la construction d'une base de système d' information géographique comportant une pluralité de tables optimisées associée chacune à un descripteur du mode de codage et du référentiel. - Procédé pour la visualisation d'une image géographique semi-réelle selon la revendication 8, caractérisé en ce que ladite étape initiale comporte, un comptage du nombre d' occurrences successives correspondant à la même valeur Y(xi zj), l'enregistrement dans la table optimisée de ladite valeur et du nombre d' occurrences associé, et la construction d'une base de système d' information géographique comportant une 17 2837949 pluralité de tables optimisées associée chacune à un descripteur du mode de codage et du référentiel. 11 - Procédé pour la visualisation d'une S image géographique semi-réelle selon la revendication 8, caractérisé en ce que la base de système d' information géographique occupe moins de 500 Méga octets pour la représentation du globe terrestre en projection de Mercator. 12 - Procédé pour la visualisation d'une image géographique semi-réelle selon l'une quelconque des revendications 8 à 11, caractérisé en ce que la base de système d' information géographique est divisée en tables de NxN pixels. 13 - Procédé pour la visualisation d'une image géographique semi-réelle selon l'une quelconque des revendications 8 à 12, caractérisé en ce que la base de système d' information géographique correspond à une résolution d' environ 30' d'arc. 14 - Procédé pour la visualisation d'une image géographique semi-réelle selon l'une quelconque des revendications précédentes caractérisé en ce qu'il comporte une étape de construction d'une table de travail locale Tl enregistrée en mémoire vive, par compression d'une partie de la base de système d' information géographique, consistant à procéder à une extraction périodique d'informations de ladite base réduite, la résolution Rt(Yo) de ladite table de travail Tl étant déterminée en fonction d'un paramètre représentatif de l' altitude YO de l'observateur virtuel, le procédé comportant des étapes ultérieures de calcul d'une représentation graphique en forme de squelette 3D A i 2837949 [meshes] en fonction du contenu de ladite table de