TITRE : Procédés de compression et de décompression d’un fichier de modèle numérique de terrain ; fichiers compressé et décompressé et produit programme d’ordinateur associés.

La présente invention concerne l’utilisation de fichiers de modèle numérique de terrain - ou fichiers MNT. Elle concerne plus particulièrement les procédés de compression / décompression de fichiers MNT permettant leur utilisation sur des calculateurs embraqués.

Un fichier MNT comporte les données d’élévation pour un ensemble de points géographiques d’un terrain. Ces points permettent de construire un maillage offrant une représentation en trois dimensions du terrain. Le terrain représenté peut être tout ou partie de la surface terrestre, du fond des océans, ou encore de la surface d’une autre corps céleste que la Terre.

La disponibilité croissante de fichiers MNT a favorisé l’émergence de nombreuses fonctions de navigation ou de sûreté dans des domaines comme l’aéronautique embarquée (drones, aéronefs, etc.), la navigation marine ou sous-marine embarquée (navires de surface, sous-marins, etc.), ou encore des applications terrestres embarquées (navigation automobile avec cartographie embarquée, etc.)

La résolution d’un fichier MNT est parfois très élevée. Par exemple, la distance caractéristique entre deux points d’un fichier MNT peut être inférieure à 0,1”, c’est-à-dire inférieure à 3 m.

Le volume de données à stocker dans un calculateur peut par conséquent être très élevé, avec par exemple des valeurs supérieures à la centaine de giga-octets pour les fichiers MNT mondiaux les plus précis.

Or, une plateforme par exemple avionique est équipée d’un calculateur embarqué, qui se caractérise par quelques centaines de mégaoctets de mémoire de masse, quelques mégaoctets de mémoire vive, et un processeur mono-cœur ne tournant qu’à quelques centaines de mégahertz.

Il s’agit en fait d’une conséquence de la nécessité de certifier un calculateur embarqué avant de pouvoir l’utiliser. Comme les processus de certification sont longs et coûteux, les calculateurs embarqués en service appartiennent à des générations de calculateurs anciennes. La complexité, le coût et le temps de développement et de certification d’un calculateur embarqué critique sont tels que l’on ne peut pas rajouter de la mémoire ou changer de processeur sans engager des frais très importants.

Il est donc nécessaire de compresser un fichier MNT source avant de le télécharger sur un calculateur embarqué aux ressources mémoires limitées.

Par ailleurs, les données de terrain doivent pouvoir être mises à la disposition des applications qui le requiert en temps-réel, notamment pour la réalisation de fonctions critiques de navigation ou de sûreté. Il faut donc que le calculateur embarqué soit capable de décompresser le fichier MNT compressé qu’il mémorise.

Or, les procédés connus de compression/décompression de données de terrain sont soit insuffisamment performants en taux de compression, de sorte que le fichier MNT compressé demande encore plusieurs giga-octets de mémoire de masse pour des représentations mondiales en haute résolution, soit insuffisamment performants en rapidité de décompression et demandent de disposer de processeurs tournant à plus d’un gigahertz pour pouvoir disposer des données décompressées en temps-réel.

Ainsi, par exemple, les documents US8665266B2 et US4890249A divulguent des procédés de compression/décompression fondés sur des représentations vectorielles. De tels procédés, quoiqu’efficaces en terme de compression, obligent le décodeur à utiliser des fonctions mathématiques (notamment des fonctions trigonométriques sin, cos, etc.) complexes pour reconstituer une matrice d’élévation du terrain environnant. L’utilisation de ces fonctions mathématiques est coûteuse en terme de performance. Ces procédés ne sont donc pas adaptés au cas de calculateurs embarqués.

Par exemple encore, les documents US9462275B2 ou CN102684703A divulguent des procédés de compression/décompression fondés sur des algorithmes du type « quad- tree » (« arbre quaternaire » ou « arbre Q »), couplés à des algorithmes de compression avec pertes du type à transformées espace-fréquence (comme des transformées en « ondelettes »), ainsi que des algorithmes d’encodage à base de codes d’Huffman ou de type CABAC (algorithmes connus de l’homme du métier). Ces procédés sont très performants en terme de taux de compression, mais ont le défaut d’être extrêmement gourmands en ressources de calcul, aussi bien pour la compression que pour la décompression. Les processeurs capables de décompresser en temps-réel les algorithmes proposés ci-dessus tournent typiquement à plus d’un gigahertz et utilisent plusieurs centaines de mégaoctets de mémoire vive.

Ces procédés connus sont par conséquent inutilisables sur des calculateurs embarqués. D’autant que ces procédés connus ne permettent pas de contrôler a priori l’erreur maximum due à la compression, obligeant à réaliser plusieurs cycles de compression-décompression-vérification pour garantir l’erreur maximum.

Il est à noter que la complexité du procédé de compression peut être grande, puisque ce procédé n’est pas exécutée ni en temps-réel, ni sur le calculateur embarqué, mais sur un ordinateur externe, qui peut être un calculateur de dernière génération, et donc de grande puissance.

Il faut donc trouver des procédés de compression alternatifs permettant le stockage et la décompression de fichiers MNT sans avoir à changer la conception matérielle existante des plateformes.

Le but de la présente invention est par conséquent de résoudre ce problème, en proposant un procédé de compression amélioré de fichiers MNT,, ce procédé présentant un taux de compression élevé, tout en permettant au procédé de décompression correspondant, exécuté sur un calculateur embarqué, une grande vitesse de décompression, compatible d’applications temps-réel.

Pour cela l’invention a pour objet un procédé de compression d’un fichier de modélisation numérique de terrain - MNT source de manière à produire un fichier MNT compressé propre à être stocké et décompressé en temps réel par un calculateur embarqué, ledit fichier MNT source comportant une tuile source constituée d’une matrice de cellules, chaque cellule comportant une valeur d’élévation d’un point géographique d’un terrain modélisé, caractérisé en ce que ledit procédé comporte les étapes consistant à : Représenter la tuile source sous la forme d’un arbre initial comportant un nœud racine, des nœuds intermédiaires et des nœuds terminaux, l’arbre initial ayant une pluralité de niveaux de profondeur, chaque nœud de l’arbre initial représentant une zone de la tuile source, chaque nœud terminal de l’arbre initial représentant une zone de la tuile correspondant à une unique cellule ; Elaguer l’arbre initial en appliquant un critère d’élagage pour obtenir un arbre élagué, le critère d’élagage permettant, lorsqu’il est vérifié, de limiter localement un nombre de niveaux de profondeur de l’arbre initial en s’arrêtant à un nœud intermédiaire, le nœud intermédiaire étant alors considéré comme un nœud terminal de l’arbre élagué et représentant une zone d’une tuile simplifiée comportant une valeur d’élévation unique qui est fonction des valeurs d’élévation des cellules associées aux nœuds terminaux qui descendent dudit nœud intermédiaire et qui ont été élagués ; Encoder la valeur d’élévation associée à chacun des nœuds terminaux de l’arbre élagué pour obtenir une valeur d’élévation différentielle, la valeur d’élévation différentielle d’un nœud terminal de l’arbre élagué étant obtenu par différence entre la valeur d’élévation associée audit nœud terminal et la valeur d’élévation associée à un nœud terminal précédent de l’arbre élagué, défini conformément à des règles d’ordonnancement permettant d’ordonner les nœuds terminaux de l’arbre élagué les uns à la suite des autres à partir d’un nœud terminal de référence, dont la valeur d’élévation est prise comme élévation de référence et dont la valeur d’élévation différentielle est égale à zéro ; et sérialiser l’arbre élagué résultant de l’encodage pour obtenir le fichier MNT compressé en parcourant les nœuds terminaux de l’arbre élagué selon un ordre de sérialisation à partir du nœud terminal de référence, le fichier MNT compressé comportant un premier champ indiquant l’élévation de référence, puis une pluralité de séquences, chaque séquence comportant un en-tête, indicatif d’un niveau de profondeur du nœud terminal considéré, et une charge, indicative de la valeur d’élévation différentielle du nœud terminal considéré.

Suivant des modes particuliers de réalisation, le procédé comporte une ou plusieurs des caractéristiques suivantes, prises isolément ou suivant toutes les combinaisons techniquement possibles :

- lequel le critère d’élagage permettant de limiter localement le nombre de niveaux de profondeur de l’arbre initial en s’arrêtant à un nœud intermédiaire consiste à vérifier que l’ensemble des valeurs d’élévation associées aux nœuds terminaux qui descendent dudit nœud intermédiaire sont à l’intérieur d’un intervalle d’erreur prédéfini.

- les règles d’ordonnancement pour l’encodage consistent : si une zone de la tuile représentée par le nœud terminal considéré possède au moins une zone voisine à gauche, la valeur d’élévation différentielle associée au nœud terminal considéré est calculée à partir de la valeur d’élévation de la zone voisine à gauche qui est la plus au-dessus parmi ladite au moins une zone voisine à gauche ; si la zone de la tuile représentée par le nœud terminal considéré n’a pas de zone voisine à gauche, mais possède au moins une zone voisine au- dessus, la valeur d’élévation différentielle associée au nœud terminal considéré est calculée à partir de la valeur d’élévation de la zone voisine au-dessus la plus à gauche parmi ladite au moins une zone voisine au-dessus ; sinon, la valeur d’élévation différentielle associée au nœud terminal considéré est calculée en différence de l’élévation de référence.

- l’en-tête d’une séquence d’un fichier MNT compressé est omis lorsque le nœud terminal considéré appartient au même niveau de profondeur que le nœud terminal précédent selon l’ordre de sérialisation.

- l’en-tête d’une séquence d’un fichier MNT compressé est défini de manière absolue par rapport au nœud racine de l’arbre élagué ou le niveau de profondeur le plus bas de l’arbre initial, ou de manière relative par rapport au niveau de profondeur du nœud précédent selon l’ordre de sérialisation.

- l’encodage permettant de limiter une plage des valeurs d’élévation différentielles associées aux nœuds terminaux de l’arbre élagué, est défini un nombre minimum de bits permettant de coder les valeurs d’élévation différentielles, et le fichier MNT compressé comportant un second champ indiquant le nombre minimum de bits.

L’invention a également pour objet un fichier MNT compressé résultant de la mise en œuvre du procédé de compression précédent.

Pour cela l’invention a pour objet un procédé de décompression d’un fichier MNT compressé, caractérisé en ce qu’il comporte les étapes consistant à : extraire du fichier MNT compressé, un flux binaire correspondant à une tuile simplifiée représentée par un arbre élagué ; et lire une élévation de référence à partir du premier champ du flux binaire ; puis, pour chaque séquence du flux binaire correspondant à un nœud terminal de l’arbre élagué en partant d’un nœud terminal de référence dont la valeur d’élévation est égale à l’élévation de référence, jusqu’à décompression complète du flux binaire, déterminer un niveau de profondeur à partir d’un en-tête de la séquence courante et lire une valeur d’élévation différentielle à partir de la charge de la séquence courante ; calculer une valeur d’élévation à partir de la valeur d’élévation différentielle lue et d’une valeur d’élévation d’un nœud terminal précédent, défini conformément à des règles d’ordonnancement ; mettre à jour, avec la valeur d’élévation calculée, les valeurs d’élévation des cellules d’une zone de la tuile simplifiée représentée par le nœud terminal courant, afin d’obtenir une matrice de cellules de la tuile simplifiée d’un fichier MNT décompressé.

L’invention a également pour objet un fichier MNT décompressé résultant de la mise en œuvre du procédé de décompression précédent.

L’invention a également pour objet un produit programme d’ordinateur comportant des instructions, qui lorsqu’elles sont exécutées par un ordinateur permettent la mise en œuvre du procédé de compression précédent ou le procédé de décompression précédent.

L’invention a également pour objet un fichier MNT compressé suite à la mise en œuvre du procédé précédent.

L’invention a également pour objet un procédé de décompression d’un fichier MNT compressé suite à la mise en œuvre du procédé précédent.

L’invention a également pour objet un produit programme d’ordinateur dont les instructions, lorsqu’elles sont exécutées par un ordinateur, permettent la mise en œuvre du procédé de compression précédent ou du procédé de décompression précédent.

L’invention et ses avantages seront mieux compris à la lecture de la description détaillée qui va suivre d’un mode de réalisation particulier, donné uniquement à titre d’exemple non limitatif, cette description étant faite en se référant aux dessins annexés sur lesquels :

[Fig 1] La figure 1 illustre la structure d’un fichier MNT source ; [Fig 2] La figure 2 est une représentation schématique d’un mode de réalisation du procédé de compression d’un fichier MNT source selon l’invention ;

[Fig 3] Les figures 3A, 3B et 3C est un exemple numérique de mise en œuvre du procédé de compression de la figure 2 ;

[Fig 4] La figure 4 est une illustration d’un fichier MNT compressé obtenu en sortie du procédé de compression de la figure 2 sur l’exemple numérique de la figure 3 ; et,

[Fig 5] La figure 5 est une représentation schématique d’un mode de réalisation du procédé de décompression d’un fichier MNT compressé selon l’invention.

De manière générale, si le procédé de compression selon l’invention est également fondé sur une représentation en arbre du fichier MNT source, il combine avantageusement une telle représentation avec un algorithme de compression du type « codage delta » (ou « delta coding » en anglais), spécifiquement adapté à une résolution non-homogène de la représentation en arbre, c’est-à-dire un nombre de nœuds par niveau de profondeur de la représentation en arbre qui n’est pas constant à travers l’ensemble des niveaux de profondeur de l’arbre.

De manière connue en soi, comme illustré sur la figure 1 , un fichier MNT source 1 , par exemple un fichier MNT mondial de la surface terrestre, comporte des valeurs d’élévation qui sont regroupées de la manière suivante.

La surface terrestre est d’abord subdivisée en au moins un premier niveau de régions. Par exemple, une région 2 est un carré de 1 ° de côté. Une région est orientée parallèlement aux méridiens terrestres et parallèlement aux parallèles terrestres.

Pour une résolution cible élevée de l’ordre de 0,1 ”, d’autres niveaux de régions, emboîtés les uns dans les autres, sont envisageables pour limiter le volume des données à manipuler à chaque niveau de régions. Par exemple, une région du premier niveau est subdivisée en une pluralité de régions d’un second niveau de régions. Une région du second niveau est par exemple un carré de 0,25° de côté. La région de premier niveau est alors subdivisée en 16 régions du second niveau.

Dans le présent mode de réalisation, la résolution cible étant de 3”, la décomposition avec un seul niveau de régions est adaptée.

Chaque région (ou chaque région du niveau de régions le plus bas) est ensuite subdivisée en une pluralité de tuiles. Dans le présent mode de réalisation, une tuile 3 est de préférence un carré de 6’ de côté, soit 0,1 ° de côté. Une région comporte par conséquent 100 tuiles.

Une tuile 3 est l’élément du fichier MNT source 1 qui regroupe effectivement les valeurs d’élévation de la zone de la surface terrestre représentée par cette tuile. Chaque tuile est identifiée par des coordonnées géographiques, par exemple une coordonnée de longitude et une coordonnée de latitude, qui correspondent aux coordonnées d’un point de référence de la tuile. Ce point de référence est par exemple le coin inférieur gauche de la tuile. Une tuile 3 est ensuite subdivisée en une pluralité de cellules 4.

Dans le mode de réalisation préféré, une tuile est constituée d’une matrice de 120x120 cellules. Une cellule est alors un carré de 3” de côté.

Une cellule comporte une unique valeur d’élévation, qui est l’élévation d’un point central de la zone de la surface terrestre représentée par cette cellule. En codant la valeur d’élévation de chaque cellule sur 16 bits, le volume d’une tuile

3 est d’environ 30 kilo-octets.

Pour faciliter la description du procédé selon l’invention et pouvoir l’illustrer par des figures, on considère aux figures 3 et 4 un mode de réalisation simplifié pour lequel une tuile est constituée d’une matrice de 8x8 cellules. En se référant à la figure 2, un mode de réalisation du procédé de compression 100 d’un fichier MNT source va être présenté.

Première étape

Dans une première étape 110, une tuile source 3 extraite d’un fichier MNT source 1 est représentée sous la forme d’un arbre initial 115. De manière générale, un graphe est constitué d’une pluralités de nœuds et d’arêtes, une arête connectant deux nœuds entre eux. Un arbre est définit mathématiquement comme un graphe acyclique (sans cycle) connexe (d’un seul tenant).

Dit autrement, les nœuds d’un arbre sont répartis sur N niveaux de profondeur, avec la spécificité que le niveau le moins élevé (niveau 0) comporte un unique nœud, ou nœud racine, et que, pour chaque autre niveau, un nœud du niveau de profondeur i (i entier entre 1 et N) est connecté par uniquement une arête, ou branche, à un seul nœud, ou nœud parent, appartenant au niveau de profondeur précédent, i-1. Les nœuds terminaux (c’est- à-dire des nœuds sans descendance) sont dénommés feuilles. Les nœuds autres que le nœud racine et les nœuds terminaux sont dits intermédiaires. Un nœud Ni,j de l’arbre peut être identifié par deux entiers : le premier entier i correspondant au niveau de profondeur auquel appartient ce nœud (i est donc un entier entre 0 et N) ; le second entier j correspondant à un identifiant donné à chacun des nœuds d’un même niveau de profondeur (j est donc un entier entre 1 et Ni, ou Ni est le nombre maximum de nœuds du niveau de profondeur i). La représentation d’une tuile 3 est un arbre initial 115 qui est un arbre homogène, dans la mesure où tous les nœuds terminaux appartiennent au même niveau de profondeur, le niveau N le plus bas.

Pour le cas d’une tuile de 120 cellules de côté, le représentation en arbre ne suit pas celui d’un « quad-tree » au sens strict puisque le chiffre de 120 cellules n’est pas aligné sur une puissance de deux.

La représentation en arbre est obtenue à partir du découpage de la tuile de 120x120 cellules de la manière suivante :

La tuile 3 est représentée par le nœud racine de l’arbre ;

Un premier découpage permet de définir 5x5 premières zones dans la tuile 3 : chaque première zone recouvre 24x24 cellules 4 de la tuile 3 et est représentée par un nœud intermédiaire du premier niveau de profondeur dans l’arbre initial 115 ;

Un second découpage permet de définir 3x3 secondes zones dans chaque premier zone: chaque seconde zone recouvre à 8x8 cellules et est représentée par un nœud intermédiaire du second niveau de profondeur dans l’arbre initial 115 ;

Un troisième découpage permet de définir 2x2 troisièmes zones dans chaque seconde zone: chaque troisième zone recouvre 4x4 cellules et est représentée par un nœud intermédiaire du troisième niveau de profondeur ;

Un quatrième découpage permet de définir 2x2 quatrièmes zones dans chaque troisième zone : chaque quatrième zone recouvre 2x2 cellules et est représentée par un nœud intermédiaire du quatrième niveau de profondeur ; et,

Un cinquième découpage permet de définir 2x2 cinquièmes zones dans chaque quatrième zone : chaque cinquième zone est une cellule de la tuile 3 et est représentée par un nœud terminal de l’arbre initial 115.

Ainsi, le produit du nombre de nœuds par niveau de profondeur, 5x3x2x2x2, donne bien le nombre de 120 cellules pour la tuile 3.

Pour le mode de réalisation simplifié, d’une tuile 3 constituée d’une matrice de 8x8 cellules 4, trois niveaux de profondeur sont suffisants, chaque niveau conduisant à la subdivision du nœud parent en 2X2 nœuds enfants.

Un exemple numérique d’une tuile de 8x8 cellules est donné à la figure 3A. La subdivision de la tuile suivant le premier niveau de profondeur est indiquée par un trait fort, la subdivision suivant le second niveau de profondeur est indiquée par un trait pointillé, et la subdivision suivant le troisième niveau de profondeur est indiquée par un trait fin (qui délimite par conséquent les cellules de l’arbre initial 115 représentant la tuile source 3).

L’arbre 115 représentant la tuile 3 de la figure 3A est celui illustré schématiquement sur la figure 2. Le nœud racine correspondant à la tuile 3 est représenté par un triangle, les nœuds terminaux correspondant aux cellules sont représentés par des ronds, et les nœuds intermédiaires sont représentés par des carrés.

Dans une seconde étape 120, l’arbre initial 115 (qui représente la tuile initiale) est élagué pour obtenir un arbre élagué 125. L’arbre élagué 125 représente une tuile simplifiée.

Une zone d’une tuile représentée par un nœud modélise une surface du terrain dont la taille dépend du niveau de profondeur de ce nœud. Il y a donc une correspondance entre résolution spatiale d’une cellule d’une tuile et niveau de profondeur d’un nœud terminal de l’arbre représentant cette cellule. L’étape 120 permet d’adapter la résolution locale de la représentation en arbre en fonction d’un critère d’élagage.

L’élagage de l’arbre initial 115 permet de limiter localement le niveau de profondeur de la représentation en arbre en transformant un nœud intermédiaire de l’arbre initial 115 en un nœud terminal de l’arbre élagué 125, lorsque les nœuds terminaux qui descendent de ce nœud intermédiaire dans l’arbre initial sont analogues entre eux, c’est-à-dire lorsque les valeurs d’élévation des cellules représentées par ces nœuds terminaux respectent un critère d’élagage prédéfini.

Dans ce cas, en devenant un nœud terminal, la zone représentée par ce nœud dans la tuile 3 devient une cellule pour la tuile représentée par ce même nœud dans l’arbre élagué 125. Cette cellule comporte une unique valeur d’élévation, qui est fonction des valeurs d’élévation des cellules représentées par les nœuds terminaux ayant été élagués.

Le critère d’élagage est avantageusement choisi pour représenter l’erreur d’élévation commise lorsque l’on choisit, pour un nœud intermédiaire Ni,j, de ne pas descendre aux niveaux de profondeur suivants et de donner une valeur d’élévation unique à toute la zone représentée par le nœud intermédiaire Ni,j considéré.

Par exemple, un paramètre d’élagage pij est choisi comme la différence entre la valeur d’élévation maximale et la valeur d’élévation minimale des cellules représentées par les nœuds terminaux issus du nœud intermédiaire Ni J considéré.

Le critère d’élagage est alors un test sur ce paramètre d’élagage pij. Par exemple, le paramètre d’élagage pij est comparé à un seuil maximum d’erreur, E max, ajusté préalablement à la mise en œuvre du procédé de compression 200.

A l’étape 120, on considère successivement chaque nœud Ni,j de l’arbre initial 115 en partant du nœud racine.

Lorsque le critère d’élagage n’est pas vérifié pour le nœud Ni,j considéré, le procédé passe au nœud suivant Ni,j+1 du même niveau de profondeur ou, si tous les nœuds du niveau de profondeur i qui subsistent ont été testés, au premier nœud du niveau de profondeur suivant i+1 qui subsiste. Lorsque le critère est vérifié pour le nœud Ni J, alors toutes les valeurs d’élévation des cellules représentées par les nœuds terminaux issus du nœud Ni J sont remplacées par une valeur d’élévation unique, sachant que l’erreur d’élévation qui découle de cette simplification reste inférieure au seuil maximum d’erreur, E max.

La valeur d’élévation unique est de préférence la valeur d’élévation maximale parmi les valeurs d’élévation des cellules représentées par les nœuds terminaux issus du nœud Ni,j. Le choix du maximum permet de garantir qu’en aucun cas, pour un même point de la surface terrestre, la valeur d’élévation du fichier MNT décompressé ne sera plus basse que la valeur d’élévation du fichier MNT source, de manière à garantir la sécurité des données fournies à une application aéronautique par exemple.

La figure 3B représente une tuile simplifiée 123 qui est le résultat de l’application de l’étape 120 sur la tuile source 3 de la figure 3A, avec un critère d’élagage dont le seuil d’erreur maximum est fixé à 10 m. La valeur d’élévation retenue est la valeur d’élévation maximale des cellules sous-jacentes.

L’arbre 125 qui représente la tuile simplifiée 123 est représenté schématiquement sur la figure 2. L’arbre 125 n’est pas forcément homogène, ses nœuds terminaux pouvant appartenir à des niveaux de profondeur différents.

Dans une troisième étape 130, l’arbre élagué 125 est parcouru pour encoder les valeurs d’élévation afin de limiter l’amplitude des données et permettre leur codage sur un plus petit nombres de bits.

L’encodage consiste à remplacer la valeur d’élévation d’une cellule représentée par un nœud terminal de l’arbre élagué par sa différence avec la valeur d’élévation d’un nœud terminal précédent. Cela nécessite d’ordonner les nœuds terminaux de l’arbre élagué 125.

Pour ce faire, un nœud de référence est tout d’abord défini pour l’arbre élagué 125. Il s’agit par exemple du nœud terminal de l’arbre élagué qui représente une zone recouvrant la cellule du coin supérieur gauche de la tuile initiale.

La valeur de l’élévation du nœud de référence dans l’arbre élagué est prise comme élévation de référence E Ref.

On notera que l’élévation de référence peut être différente de la valeur d’élévation de la cellule du coin supérieur gauche de la tuile initiale 3, lorsque cette dernière a été élaguée à l’étape 120.

Puis, la valeur d’élévation du nœud de référence est encodée en la remplaçant par sa différence avec l’élévation de référence E_Ref. La valeur d’élévation encodée pour le nœud de référence est donc égale à 0. Le choix du nœud terminal précédent avec lequel encoder la valeur d’élévation d’un nœud terminal est à définir précisément, car il faut s’assurer que les valeurs d’élévation initiales peuvent être reconstruites, pas à pas, à partir de la seule élévation de référence E Ref. De plus, la structure de l’arbre élagué n’étant pas homogène (c’est-à-dire que les nœuds terminaux n’appartiennent pas tous au même niveau de profondeur), ce choix n’est pas trivial.

Les règles d’ordonnancement sont avantageusement les suivantes :

- première règle : si la zone associée au nœud considéré a une zone voisine à sa gauche, sa valeur d’élévation sera encodée à partir de la valeur d’élévation du nœud associé à cette zone voisine (au cas où il existe plusieurs zones voisines à gauche, la zone voisine à gauche la plus au-dessus est choisie) ;

- deuxième règle : si la zone associée au nœud considéré n’a pas de zone voisine à sa gauche, mais a une zone voisine au-dessus, sa valeur d’élévation est encodée à partir de la valeur d’élévation du nœud associé à cette zone voisine (au cas où il existe plusieurs zones voisines au-dessus, la zone voisine au-dessus la plus à gauche est choisie);

- troisième règle : sinon, la valeur d’élévation est encodée en différence de l’élévation de référence E Ref.

Il est à noter que la première règle fait intervenir la zone voisine à gauche et que la seconde règle fait intervenir la zone voisine au-dessus, puisque la cellule de référence, qui est le point de départ de la décompression, est la cellule du coin supérieur gauche de la tuile initiale. Le choix d’une autre cellule de référence conduirait à d’autres règles d’ordonnancement.

La figure 3C illustre la tuile simplifiée encodée 133 résultant de l’application de l’étape 130 sur la tuile simplifiée 123 de la figure 3B. Les flèches indiquent la zone voisine de la zone considérée pour le calcul de la valeur d’élévation différentielle.

A l’issue de l’étape 130, l’amplitude des valeurs d’élévation différentielle encodées se situe dans l’intervalle réduit [0 ; 22] Il suffit donc de coder ces valeurs sur 6 bits seulement, au lieu des 11 bits requis pour encoder les valeurs d’élévation de la tuile source 3.

L’encodage différentiel permet donc de réduire l’amplitude des valeurs à coder, deux surfaces terrestres voisines ayant souvent des élévation proches.

Dans une quatrième étape 140, l’arbre élagué différentiel 135 est sérialisé afin d’obtenir un flux, de préférence binaire, en tant que composante d’un fichier MNT compressé. Le flux binaire est initialisé avec, dans un premier champ, l’élévation de référence E Ref de la tuile considérée. L’élévation de référence est codée de préférence sur 16 bits.

De préférence, est ensuite insérée, dans un second champ, une information relative au nombre de bits nécessaires au codage des valeurs d’élévation différentielle. Cette information est par exemple codée sur 4 bits. Ce second champ n’est pas nécessaire si nombre de bits nécessaire au codage est fixé par avance.

Puis, on insère une série de séquences, chaque séquence correspondant à un nœud terminal de l’arbre élagué différentiel.

Une séquence est constituée d’un en-tête et d’une charge.

L’en-tête vise à indiquer le niveau de profondeur du nœud terminal considéré.

La charge utile indique la valeur d’élévation différentielle du nœud terminal considéré. Chaque valeur d’élévation est codée sur le nombre de bits indiqué dans le second champ.

La série de séquences suit un ordre de lecture prédéfini des nœuds terminaux de l’arbre 135. Par exemple, le nœud suivant le nœud considéré est le noeud qui représente une zone voisine de celle représentée par le nœud considéré dans la tuile simplifiée 133 lorsque l’on parcourt ses cellules de gauche à droite et de haut en bas, en donnant la préférence à un retour à la ligne quand on peut rester au même niveau de résolution, c’est- à-dire au même niveau de profondeur que le nœud considéré.

Cet ordre de lecture est représenté par les flèches sur la figure 3B pour plus de lisibilité.

Ainsi, le flux binaire de la figure 4 résulte de l’application de l’étape 130 sur la tuile simplifiée encodée 133 de la figure 3C.

Le flux binaire comporte un premier champ indiquant l’élévation de référence, soit la valeur 650.

Le flux binaire comporte un second champ indiquant le nombre de bits sur lequel les valeurs d’élévation différentielle sont codées. Compte tenu de l’amplitude de ces valeurs, le codage s’effectue sur 6 bits. Le second champ indique par conséquent la valeur 6. Cette valeur est par exemple codée sur 4 bits.

Le flux binaire comporte une première séquence correspond au nœud de référence. Il s’agit dans cet exemple d’un nœud terminal appartenant au troisième niveau de profondeur. L’en-tête de la première séquence comporte alors un premier bit à 1 indiquant qu’il faut descendre au second niveau de profondeur, puis un second bit à 1 indiquant qu’il faut descendre au troisième niveau de profondeur, puis un troisième bit à 0 indiquant l’arrêt dans le niveau de résolution. Dès qu’un bit à 0 est ajouté, l’écriture de l’en-tête est terminée et la séquence est complétée par la valeur d’élévation différentielle du nœud de référence, soit la valeur 0, qui est codée sur 6 bits.

Le flux binaire comporte une seconde séquence correspond à un second nœud qui est le nœud suivant le nœud de référence. Il s’agit d’un nœud terminal appartenant au troisième niveau de profondeur. L’en-tête de la seconde séquence comporte alors un premier bit à 1 indiquant qu’il faut descendre au second niveau de profondeur, puis un second bit à 1 indiquant qu’il faut descendre au troisième niveau de profondeur, puis un troisième bit à 0 indiquant l’arrêt dans le niveau de résolution. Dès qu’un bit à 0 est ajouté, l’écriture de l’en-tête est terminée et la séquence est complétée par la valeur d’élévation différentielle du nœud de référence, soit la valeur 11 codée sur 6 bits.

Et de proche en proche l’ensemble de l’arbre élagué est parcouru entièrement pour obtenir un flux binaire du fichier MNT compressé.

Dans un mode de réalisation avantageux, l’en-tête ne définit pas le niveau de profondeur de manière absolu, mais de manière relative, en tenant compte de la structure connue de l’arbre.

Par exemple, si le nœud de référence appartient au troisième niveau de profondeur (comme c’est le cas sur les figures 3), on sait qu’il est suivi par trois nœuds de même niveau de profondeur, de sorte que les en-têtes des séquences correspondantes, S2, S3 et S4, peuvent être omis.

Les séquences S1 à S4 permettant de décrire une zone de la tuile représentée par un nœud du second niveau, après la séquence S4, on sait que l’on aura à décrire une zone représentée par un autre nœud du second niveau. Ainsi le premier bit de l’en-tête de la séquence décrivant cet autre nœud peut être omis.

Soit cet autre nœud est terminal et alors l’en-tête comprend un bit à 0 pour indiquer qu’il n’est pas nécessaire de descendre au troisième niveau de profondeur (cas de des séquences S5 et S6), soit cet autre nœud n’est pas terminal et alors l’en-tête comprend un bit à 1 suivi d’un bit à 0 pour indiquer il faut descendre au troisième niveau de profondeur (cas de des séquences S7),

Le nœud de la séquence S7 appartenant au troisième niveau de profondeur, on sait qu’il est suivi par trois nœuds de même niveau de profondeur, de sorte que les en-têtes des séquences correspondantes, S8 à S10, peuvent être omis.

Les séquences S1 à S10 ayant permis de décrire une zone de la tuile représentée par un nœud de premier niveau, après la séquence S10, on sait que l’on aura à décrire une zone représentée par un autre nœud du premier niveau. Ainsi le premier bit de l’en-tête de la séquence décrivant cet autre nœud peut être omis. Soit cet autre nœud est terminal et alors l’en-tête comprend un bit à 0 pour indiquer qu’il n’est pas nécessaire de descendre au second niveau de profondeur (cas des séquences S11 et S12), soit cet autre nœud n’est pas terminal et alors l’en-tête comprend un bit à 1 pour indiquer qu’il faut descendre au second niveau de profondeur, suivi d’un bit par exemple à 0 indiquant qu’il n’est pas nécessaire de continuer à descendre (cas des séquences S13).

Le nœud de la séquence S13 appartenant au second niveau de profondeur, on sait qu’il est suivi par trois nœuds du même niveau de profondeur, de sorte que les en-têtes des séquences correspondantes peuvent être simplifiées en omettant le premier bit à 1 (cas des séquences S14 à S16).

Le flux binaire obtenu présente un taux de compression important par rapport à la tuile initial.

Le flux binaire est stocké dans la mémoire d’un processeur embarqué.

Il doit être décompressée pour permettre d’accéder aux valeurs d’élévation de l’arbre élagué représentant une tuile simplifié décompressé.

La figure 5 illustre un mode de réalisation d’un procédé de décompression 200.

Un flux binaire est extrait d’un fichier MNT compressé 5.

Dans une première étape 210, les informations d’élévation de référence et le nombre de bits de codage des valeurs d’élévation différentielles sont extraites du flux binaire.

Puis, pour chaque séquence du flux binaire (boucle 220), est déterminé le niveau de profondeur de la séquence courante (étape 222). Cette profondeur courante est déterminée à partir de l’en-tête de la séquence courante et/ou de l’endroit de la reconstruction de la tuile simplifiée où l’on se trouve à l’instant de décompression courant.

Puis, toujours pour cette séquence courante, est déterminée une valeur de l’élévation différentielle (étape 224). Elle est décodée à partir de la charge.

Puis, à l’étape 226, une valeur d’élévation absolue est calculée à partir de la valeur de l’élévation différentielle en tenant compte des règles d’ordonnancement qui ont été utilisées pour la compression à l’étape 120.

Enfin, à l’étape 228, la matrice de cellules de la tuile simplifiée est mise à jour en associant à la zone représentée par le nœud terminal correspondant à la séquence courante la valeur d’élévation absolue. La zone concernée est identifiée en tenant compte de l’ordre séquentiel qui a été utilisé pour la compression, à l’étape 140.

En répétant les étapes 222 à 228 pour chaque séquence du flux, la tuile simplifiée est reconstruite. Elle constitue tout ou partie du fichier MNT décompressé. Elle est représentée par l’arbre élagué 125. Ce fichier MNT décompressé est finalement transmis à l’application qui a requis la décompression du flux binaire correspondant.

L’homme du métier constatera que le flux binaire obtenu ne requiert qu’un nombre limité d’accès mémoire par valeur d’élévation codée ainsi que des opérations arithmétiques simples et peu nombreuses (décalage et addition). Cela rend le décodage très rapide, y compris sur les processeurs de faible puissance de calculateurs embarqués.

Ainsi, le procédé de compression selon l’invention, en couplant une représentation du terrain en arbre avec un algorithme de compression différentiel rapide prenant en compte des contraintes d’erreur maximale, permet d’atteindre des taux de compression élevés tout en ne demandant que peu de puissance de calcul et de mémoire à la décompression et en maîtrisant l’erreur sur les valeurs décompressées.

Il est donc tout à fait adapté à une utilisation sur des calculateurs embarqués de faible puissance, tels que ceux que l’on trouve à bord des avions.

Le procédé de compression selon l’invention permet en outre de garantir, a priori, l’erreur de compression maximum, la rendant facilement utilisable dans des applications critiques.

Il est à noter que le critère d’élagage utilisé peut être modulé de manière à l’adapter opportunément sur des zones d’intérêt de la tuile considérée. Cela permet de moduler la précision de la modélisation d’une surface de terrain en fonction d’un besoin fonctionnel identifié.

De la même manière, afin de maximiser l’utilisation de l’espace mémoire, il est possible de configurer le niveau de profondeur maximum de l’arbre élagué sur des zones d’intérêt et ainsi limiter la résolution plancher à ce qui est fonctionnellement suffisant.

Ces mécanismes d’adaptation concourent à rationaliser la taille du fichier MNT compressé en regard d’une application donnée.