Brevet FR2791848A1 — publié le 20001006

DISPOSITIF ET PROCEDE DE GENERATION D'IMAGE MODIFIEE PAR TRAITEMENT D'UNE IMAGE SOURCE L'invention a pour objet un dispositif et un procédé permettant d'obtenir, à partir d'une image source mémorisée sous forme d'une matrice à deux dimensions de pixels répartis sur une grille, une représentation de l'image source sous forme d'une matrice à deux dimensions de pixels qui diffère de la matrice d'origine par déplacement en translation, en rotation et par modification d'échelle (c'est-à-dire par effet de zoom). - Une application importante, mais non exclusive, de l'invention est l'affichage, dans le champ de vision du conducteur d'un véhicule, d'une fraction d'une carte géographique mémorisée représentant l'environnement du véhicule, avec une présentation en facilitant l'utilisation. Plus précisément, les images cartographiques sont généralement mémorisées sous forme d'une matrice de pixels répartis sur une grille avec le Nord suivant une des directions de la grille, généralement en haut. La couleur de chaque pixel est codée par un nombre et fait appel à un nombre réduit de couleurs de base, c'est-à-dire à une palette simplifiée afin d'obtenir des fichiers de taille réduite. Pratiquement, la palette comporte généralement 24 = 16 couleurs de base seulement, ce qui suffit à obtenir une qualité acceptable. Il est souhaitable de fournir, au conducteur du véhicule, une image cartographique représentant uniquement la fraction d'une carte d'origine correspondant à un environnement déterminé du véhicule à l'instant courant, dans une orientation telle qu'une direction déterminée sur l'afficheur corresponde au cap ou à la route et/ou avec un effet de zoom, ce qui implique d'afficher la fraction déterminée de la carte avec une définition différente de la définition d'origine. Il existe déjà des algorithmes qui permettent de calculer l'emplacement, sur la grille de départ, de chacun des pixels qui apparaîtront aux noeuds de la grille, généralement rectangulaire, de l'image modifiée à afficher. A l'heure actuelle, on calcule la couleur à donner à chaque pixel de l'image modifiée par interpolation spatiale, à partir de pixels proches de l'image source. Habituellement, on effectue une interpolation bidirectionnelle sur les quatre pixels les plus proches, avec des facteurs de pondération correspondant aux distances du pixel de l'image modifiée aux quatre pixels de l'image source. Cette opération oblige à réaliser, pour chacune des trois composantes de couleur de l'image modifiée, quatre multiplications par les facteurs de pondération et trois additions, c'est-à-dire en tout 7x3 = 21 opérations. Pour une image modifiée représentée sur une grille de 800x600 pixels avec une cadence de rafraîchissement de 50 Hz, la puissance de calcul nécessaire est proche de 500 Mflops. Une telle puissance de calcul est difficilement compatible avec une utilisation embarquée, que ce soit sur un véhicule terrestre ou un aéronef. Elle conduit notamment à une dissipation thermique importante du calculateur nécessaire. La présente invention vise notamment à fournir un dispositif et un procédé permettant de réduire notablement la puissance de calcul nécessaire, et donc les ressources matérielles à mettre en ouvre. Dans ce but, l'invention propose notamment un dispositif de génération d'une image modifiée à partir d'une image de départ, ou image source, comprenant: - une mémoire d'image source sous forme d'un fichier donnant les couleurs de pixels répartis sur une grille bidirectionnelle, - un organe de calcul de la position de chaque pixel de l'image modifiée, affectant ce pixel à un noeud d'une sous- grille de l'image source, - une table mémorisée de transcodage entre un code numérique d'entrée représentant la position d'un pixel d'image traitée sur la sous-grille ayant une dimension de maille qui est une fraction entière 1/n de la grille de départ et les couleurs possibles de chacun des quatre pixels définissant la maille dans l'image d'origine et un code de sortie représentant la couleur du dit pixel d'image modifiée pour chaque emplacement dans la sous-grille et pour chaque jeu possible de couleurs des quatre pixels, et - une table spécifique de la palette de base des couleurs de l'image source, donnant une correspondance entre chaque code de sortie et une couleur à afficher. Dans le cas d'image cartographique, la couleur sera généralement définie dans une palette comportant un faible nombre de couleurs de base, par exemple 24 Cependant, l'invention trouve d'autres applications pour lesquelles les couleurs seront constituées par d'autres paramètres, telles que des luminances (valeurs de gris). Lorsque la dimension de maille de la sous-grille est égale à une fraction d/2n de la grille de l'image source, il est avantageux de décaler cette sous-grille de d/2.2n par rapport à la grille, dans les deux directions. Cela permet de coder l'emplacement de chaque pixel à générer, pour constituer l'image modifiée, par un nombre comportant 2n bits seulement. Pour cela il suffit d' un arrondi faisant correspondre chaque pixel de l'image modifiée à un noeud de la sous-grille. Le code de représentation de chaque pixel de l'image modifiée devrait au contraire comporter 2(n+l) bits en cas de coïncidence de la grille et de la sous-grille de l'image source. L'invention propose également un procédé de génération d'une image modifiée, suivant lequel: - de façon préliminaire, on établit et on mémorise une table de transcodage entre un code numérique d'entrée représentant la position d'un pixel d'image modifiée sur- une sous- grille de l'image source ayant une dimension qui est une fraction entière 1/2n de la grille de départ et les codes couleurs possibles de chacun de quatre pixels de la maille de l'image source et un code de sortie représentant le code de configuration du dit pixel d'image modifiée, - on établit une table spécifique d'une palette de l'image de départ, donnant une correspondance entre chaque code de configuration et une couleur propre à la palette de l'image source, et - on calcule la position de chaque pixel de l'image modifiée en l'assimilant à un noeud de la sous-grille, on l'applique en entrée de la table de transcodage et on applique le code de sortie correspondant à la table spécifique, pour obtenir un code représentatif des couleurs du pixel de l'image transformée. L'algorithme de calcul de la position de chaque pixel de l'image modifiée peut être un des algorithmes largement utilisés à l'heure actuelle et mis en oeuvre sur un processeur. L'opération d'arrondi s'effectue simplement par troncature, c'est-à-dire que la position de chaque pixel de l'image modifiée fait l'objet d'une approximation par assimilation aux noeuds de la sous-grille placée en amont dans le sens du balayage ligne et du balayage colonne. En principe, le nombre des codes d'entrée est très élevé. Dans le cas d'une image source ayant une palette à 24 = 16 couleurs et d'une sousgrille définissant 16 pixels dans chaque maille de la grille de l'image source, les codes d'entrée, codés sur 20 bits, représentent environ un million de combinaisons. Mais la table de transcodage présente des symétries qui permettent de réduire le nombre de codes possibles en sortie à 41.000 codes environ, qui peuvent-être codés sur 16 bits seulement. A chacun de ces codes de sortie est associée par exemple des composantes de type RVB. Cette table de transcodage est indépendante des couleurs de base de l'image source. Elle peut donc être calculée et mémorisée une fois pour toutes. Elle ne fournit donc pas directement une indication affichable. Le rôle de la seconde table est de fournir les résultats d'un calcul des couleurs associées au code résultant du transcodage. La seconde table, dont le nombre d'entrées possible et le contenu sont beaucoup plus réduits que ceux de la première, peut être calculée de façon simple à partir de: - la palette de couleurs du fichier représentant l'image source, et - le choix fait pour l'affichage de l'image modifiée (couleurs identiques à celles de l'image d'origine, fausses couleurs, noir et blanc en fonction de la luminance des différents pixels de l'image source). Les caractéristiques ci-dessus ainsi que d'autres apparaîtront mieux à la lecture de la description qui suit d'un mode particulier de réalisation, donné à titre d'exemple non limitatif, et de la comparaison qui en est faite avec un procédé suivant l'art antérieur. La description se réfère aux dessins qui l'accompagnent, dans lesquels: - la figure 1 est un schéma montrant les paramètres de sélection de la position en translation et en rotation ainsi que la dimension de la région de l'image source qui est à afficher sous forme d'une image modifiée; - la figure 2 est un schéma à grande échelle destiné à montrer les emplacements respectifs des pixels de l'image source et de l'image modifiée ou traitée; - la figure 3 est un schéma synoptique montrant les composants principaux du dispositif. Sur la figure 1, le cadre 10 indique les limites d'une carte mémorisée sous forme d'une base de données cartographiques, formée par une matrice de pixels. Cette base de données donne, pour chacun des pixels, tels que les pixels 12, répartis suivant une grille bidimensionnelle, schématisée par les traits continus 14 sur la figure 2, les coordonnées dans une direction en ligne et une direction en colonne et un code d'identification de couleur à partir d'une palette dont on admettra par la suite, à titre d'exemple, qu'elle comporte 24 = 16 couleurs de base. En général, la base de données cartographiques est organisée de façon que le Nord N corresponde à la direction des colonnes. A bord d'un véhicule, et notamment d'un avion, on cherche souvent à visualiser une image d'une zone dans laquelle se trouve le véhicule sous forme de pixels organisés en lignes et colonnes, la direction R des colonnes correspondant au cap suivi par le véhicule (figure 1). De plus, la visualisation d'une région déterminée 16 de la carte conduit à un affichage des pixels que constitue l'image modifiée à afficher sous forme d'une matrice bidimensionnelle, les pixels 18 occupant les noeuds d'une grille, représentée en traits mixtes sur la figure 2, dont la dimension de maille est différente de la dimension de maille p de la grille de l'image source 10. L'affichage de l'image modifiée par des opérations qu'on peut considérer comme une sélection en position et en orientation et un zoom, implique de connaître, pour chacun des pixels 18, un code donnant la couleur par référence à une palette qui peut être différente de la palette de constitution de l'image source. On définit généralement les modifications à apporter à l'image source par les coordonnées X, Y du point de départ du balayage de l'image source en vue de constituer l'image modifiée, les biais 8X et 3Y et les dimensions Xt et Yt de la fenêtre de l'image source qui doit être traitée pour donner naissance à l'image modifiée. On connait déjà des algorithmes simples de calcul de la position de chacun des pixels 18 de l'image modifiée à afficher dans l'image source. Ce calcul n'implique que des opérations simples de multiplications et d'additions. Pour simplifier la mise en ouvre de l'invention, la position de chaque pixel de l'image modifiée fait l'objet d'une approximation conduisant à considérer ce pixel comme placé à un noeud proche d'une sous-grille qui est indiquée par les lignes en tirets 20 sur la figure 2. La dimension de chaque maille de cette sous-grille est une fraction p/2n de la dimension p de maille de la grille 14. Une façon simple d'effectuer l'approximation consiste, après calcul exact de la position de chaque pixel 18, à effectuer une troncature conduisant à assimiler la position de ce pixel à celle d'un noeud 22 de la sous-grille placé immédiatement à gauche et au-dessus (dans le cas d'un sens normal de balayage), comme indiqué par la flèche f. Pour éviter une accumulation d'erreurs, le calcul de position des pixels de l'image modifiée s'effectue par incrémentation d'un pixel à un autre à partir de la valeur exacte de position, la troncature n'intervenant qu'ensuite. Dans la pratique, il suffit en général d'une valeur n =2. En effectuant l'opération de troncature ou d'arrondi sur une sous-grille décalée de p/2.2n (c'est-à-dire dans le cas illustré un décalage de 1/8 de distance inter-pixels de la grille d'origine), le codage suivant les directions X et Y peut s'effectuer sur 2 x 2 bits, alors qu'une sous- grille sans décalage imposerait un codage sur 2 x 3 bits. Le dispositif peut avoir la constitution de principe montré sur la figure 3. Le dispositif comporte une base de données cartographique 24 généralement constituée par une matrice de pixels stockés sous forme de pavés (mosaïque). Chaque pavé est accompagné d'un identifiant donnant son emprise et la palette de couleurs utilisée, ainsi que sa localisation géographique et son orientation si elle n'est pas strictement identique pour tous les fichiers. Un processeur 26 est prévu pour extraire de la base de données 24 les informations définissant l'image de départ. Dans le cas d'un véhicule, la sélection par le processeur 26 s'effectuera à partir d'une instruction, qui peut être appliquée manuellement sur une entrée 28, indiquant la zone à visualiser, c'est-à-dire l'emprise de l'image modifiée, par rapport à l'emplacement du véhicule. L'emplacement du véhicule lui-même peut être donné sous forme de sa longitude L et de sa latitude 1, fournies par une centrale de navigation. Le cap du véhicule, qui détermine l'orientation R, est également fourni, par exemple à l'aide de la centrale. Dans le cas d'un avion, une information d'altitude peut également être donnée, surtout si le degré de zoom est automatiquement fixé en fonction de cette altitude. A partir des éléments ainsi fournis, le processeur détermine les paramètres X, Y, ÈX, 6Y, Xt et Yt et il provoque le transfert d'une fraction de l'image source recouvrant à la zone à visualiser sous forme d'une image modifiée dans une mémoire cache ou ante-mémoire 30. Souvent une mémoire ayant une capacité de 2048 x 2048 pixels sera satisfaisante pour recouvrir à coup sûr une zone de 800 x 600 pixels à afficher pour des vitesses de défilement importantes. Un extracteur 32 reçoit les paramètres élaborés par le processeur 26 et extrait de la mémoire cache 30, à fréquence vidéo, toutes les adresses de pixels de la sous-grille utilisée. Dans le cas d'une palette à 16 couleurs et d'un codage X, Y à 2 fois 2 bits (sur une sous-grille ayant un pas p/4), chaque pixel sera défini sur 20 bits, comprenant les 4 couleurs des 4 pixels avoisinants dans la maille de la mémoire cache. Une table de transcodage 34, ayant par exemple une capacité de 1 Mmots de 16 bits, permettant de fournir une valeur de sortie pour une image de 800 x 600 pixels. Les valeurs de sortie peuvent être codées sur 16 bits, du fait que le nombre de combinaisons susceptibles d'exister est beaucoup plus réduit que le nombre des entrées, du fait des symétries qui sont exploitées. Chacun des codes de sortie donne la couleur d'un pixel de l'image modifiée en fonction de la couleur des 4 pixels qui ont servi de référence pour le code et de la position sur la sous-grille. Il reste à affecter un code de couleur RVB (ou autres). Cette opération est effectuée par une seconde table, ayant par exemple une capacité de 64 Kmots, de 16 bits ou 24 bits par exemple, qui reçoit en 38 une information représentative des couleurs de base de l'image source et, éventuellement, des couleurs de la palette de l'image modifiée. Elle fournit en sortie des mots, de 16 bits ou 24 bits par exemple, donnant sous forme numérique les composantes RVB pour chaque pixel de l'image modifiée. Un convertisseur numérique- analogique 40 fournit, à partir de ces codes, les composantes analogiques de couleur destinées à l'affichage. On voit que l'invention permet de réduire de façon énorme la capacité de calcul requise. Dans le cas, qu'on peut considérer comme représentatif, d'une image à fréquence télévision de 800 x 600 pixels, le séquenceur doit simplement fournir les points de calcul à 24 MHz. La table de transcodage 34 et la table 36 peuvent respectivement avoir des capacités de 1 Mmots et de 64 kmots de 16 bits. Un mot de 16 bits permet en effet de couvrir 65.636 cas possibles, alors que l'exploitation des symétries et des arrondis permet de réduire le nombre de codes de sortie différents à 41.000 environ. REVENDICATIONS 1. Dispositif de génération d'une image modifiée à partir d'une image de départ, ou image source, comprenant: - une mémoire d'image source sous forme d'un fichier donnant les couleurs de pixels répartis sur une grille bidirectionnelle (14), - un organe de calcul de la position de chaque pixel de l'image modifiée, affectant ce pixel à un noeud d'une sous- grille (20) de l'image source, - une table mémorisée de transcodage entre un code numérique d'entrée représentant la position d'un pixel d'image traitée sur la sous-grille ayant une dimension de maille qui est une fraction entière 1/n de la grille de départ et les couleurs possibles de chacun des quatre pixels définissant la maille dans l'image d'origine et un code de sortie représentant la couleur du dit pixel d'image modifiée pour chaque emplacement dans la sous-grille et pour chaque jeu possible de couleurs des quatre pixels, et - une table spécifique de la palette de base des couleurs de l'image source, donnant une correspondance entre chaque code de sortie et une couleur à afficher. 2. Dispositif selon la revendication 1, caractérisé en ce que la couleur est définie dans une palette comportant 24 couleurs de base. 3. Dispositif selon la revendication 1 ou 2, dans lequel la dimension de maille de la sous-grille est égale à une fraction d/2n de la grille de l'image source, caractérisé en ce que la sous- grille est décalée de d/2.2n par rapport à la grille, dans les deux directions. 4. Dispositif selon la revendication 3, caractérisé en ce que l'emplacement de chaque pixel à générer, pour constituer l'image modifiée, est défini par un nombre comportant 2n bits, à l'aide d' un arrondi faisant correspondre chaque pixel de l'image modifiée à un noeud de la sous-grille. 5. Procédé de génération d'une image modifiée, caractérisé en ce que: - de façon préliminaire, on établit et on mémorise une table de transcodage entre un code numérique d'entrée représentant la position d'un pixel d'image modifiée sur une sous-grille de l'image source ayant une dimension qui est une fraction entière 1/2n de la grille de départ e-t les codes couleurs possibles de chacun de quatre pixels de la maille de l'image source et un code de sortie représentant le code de configuration du dit pixel d'image modifiée, - on établit une table spécifique d'une palette de l'image de départ, donnant une correspondance entre chaque code de configuration et une couleur propre à la palette de l'image source, et on calcule la position de chaque pixel de l'image modifiée en l'assimilant à un noeud de la sous- grille, on l'applique en entrée de la table de transcodage et on applique le code de sortie correspondant à la table spécifique, pour obtenir un code représentatif des couleurs du pixel de l'image transformée. 6. Procédé suivant la revendication 5, caractérisé en ce qu'on définit la position de chaque pixel de l'image modifiée, dans la grille de l'image source, par un arrondi par troncature, assimilant la position de chaque pixel de l'image modifiée à un noeud de la sous-grille placée en amont dans le sens du balayage ligne et du balayage colonne de l'image source.