Brevet FR2834376A1 — publié le 20030704

s 13825.3 P ADRESSAGE DE MÉMOIRE DE BLOCS DE RÉFÉRENCE EN CODAGE FRACTAL La présente invention concerne le traitement d' images numériques et plus particulièrement la compression d' images numériques par codage fractal Le codage fractal consiste à rechercher, dans une image numérique, des portions d' images similaires afin de réduire le volume de l' image en se contentant, pour les blocs considérés comme similaires, de coder un seul bloc et d' iden- tifier les autres blocs similaires par une référence au bloc premier. La figure 1 illustre, par une vue schématique, une image numérique I dans laquelle une fenêtre de recherche SW doit être codée par compression fractale. La fenêtre est découpée en blocs de même dimension ici B1, B2,.. ., B5,..., B9 de 32 par 32 pixels, la fenêtre de recherche SW faisant 34 par 34 pixels. Les blocs B1 à B9 se chevauchent ou se recouvrent dans les deux directions. En pratique, on utilise une fenêtre de recherche de plus grandes dimensions, par exemple, 64 par 64 pixels. Pour simplifier, l' invention sera décrite en relation avec un exemple de fenêtre de recherche de 34 par 34 pixels. Elle s' applique cependant quel que soit le nombre de pixels de la fenêtre de recherche et des blocs. La recherche des blocs similaires s'effectue par rapport à un bloc de référence appelé également bloc "Range" RB de dimensions inférieures à celle des blocs B1 à B9. Pour permettre la comparaison, les blocs B1 à B9 sont sous échantillonnés de facon à obtenir des blocs dits de domaine DB de même taille que le bloc de référence RB. La figure 2 illustre ce sous-échantillonnage par une transformation des blocs Bi en blocs de domaine DBi. Chaque bloc de domaine contient des valeurs correspondant aux valeurs moyennes de groupe de pixels du bloc entier correspondant. Les similitudes entre les blocs RB et DB ne sont pas recherchées uniquement pour les identités. On recherche également si chaque bloc de domaine correspond au bloc de référence après certaines transformations. Ces transformations sont nommoss des isométries et correspondent respectivement à une symétrie par rapport à l'axe vertical, une symétrie par rapport à l'axe horizontal, une rotation à 180 , une symétrie d'axe Y=X, une rotation à 270 , une rotation à 90 et une symétrie d'axe Y=-X. La technique de codage ou compression fractale d' images est décrite, par exemple, dans l'ouvrage "Fractal image compression: Theory and application to digital images" de Yuval Fisher publié par Springer Verlag, New-York en 1995. Un autre exemple d'algorithme de compression fractale d' images est décrit dans l 'article ''Design of an ASIC architecture for high speed fractal image compression" de Ancarani De Gloria et Olivieri Stazzone publié dans IEEE "Intenational ASIC conference" en septembre 1996. L'homme de l'art pourra également se référer à la demande de brevet français 2 775 812. Pour permettre les comparaisons des blocs de domaine par rapport au bloc de référence, le bloc de référence et ses sept isométries doivent classiquement être stockées dans des zones mémoire distinctes. La présente invention vise à réduire l'espace mémoire nécessaire dans un système de codage fractal d' images . numerlques. L' invention vise plus particulièrement à réduire l'espace de stockage nécessaire aux isométries des blocs de référence. Pour atteindre ces objets et d'autres, l' invention prévoit un procédé de stockage de valeurs d'un bloc de référence et de sept isométries utilisés dans un procédé de compression fractale d' image, consistant à utiliser quatre zones mémoire de tailles identiques dans lesquelles sont respectivement stockées l'identité, et trois premières isométries correspondant aux isométries de symétrie par rapport à l'axe vertical, de rotation de 270 , et de rotation de 90 . L' invention prévoit également un procédé de lecture de zones mémoire dans lequel chaque zone mémoire est adressée dans une première direction pour la lecture des valeurs stockées en vue d'obtenir l'identité et les trois premières isométries, et dans la direction inverse pour la lecture des quatre autres isométries de symétrie par rapport à l'axe horizontal, de rotation à 180 , de symétrie par rapport à une première diago nale et de symétrie par rapport à la deuxième diagonale. L' invention prévoit également un procédé de compres sion fractale d' images utilisant un bloc de référence et sept isométries de ce bloc, comprenant les étapes suivantes: - mémoriser les valeurs respectives des pixels du bloc de référence et de trois seulement de ses isométries; et adresser les zones mémoire correspondant en lecture dans une direction ou dans la direction inverse selon l'isométrie souhaitée. Selon un mode de mise en oeuvre de la présente invention, on stocke deux isométries du bloc de référence dans une même zone mémoire. L' invention prévoit également un circuit d'adressage d'une mémoire de stockage d'un bloc de référence de données image destiné à être utilisé dans un procédé de compression fractale d' image, comportant des moyens pour adresser chacune de quatre zones de ladite mémoire dans une première direction et dans la direction inverse. Ces objets, caractéristiques et avantages, ainsi que d'autres de la présente invention seront exposés en détail dans la description suivante de modes de réalisation particuliers faite à titre non-limitatif en relation avec les figures jointes parmi lesquelles: Les figures 1 et 2 décrites précédemment illustrent la compression fractale d' images à laquelle s' applique la présente invention; La figure 3 illustre les différentes isométries d'un bloc de référence d'une image numérique en codage fractal selon un exemple de quatre par quatre pixels; et La figure 4 représente l' architecture d'une mémoire selon l' invention destinse au codage des isométries de référence dans un procédé de codage fractal. Les mêmes éléments ont été désignés par les mêmes références aux différentes figures. Pour des raisons de clarté, seuls les éléments et étapes de procédé qui sont nécessaires à la compréhension de l' invention ont été représentés aux figures et seront décrits par la suite. En particulier, les différents calculs et traitements amont et aval aux stockages et à la lecture des blocs de référence n'ont pas été détaillés et ne font pas l'objet de la présente invention. De plus, le séquencement des traitements de chargement et déchargement des donnces des blocs de référence dépend de l' application et ne fait pas non plus l'objet de l' invention. La figure 3 représente, de façon schématique, les sept isométries possibles dans un codage d' image fractale pour un bloc de référence 1 de quatre par quatre pixels. Le choix du nombre de 16 pixels pour le bloc de référence est arbitraire. L' invention s'applique quel que soit le nombre de pixels des blocs de référence pourvu qu'il s'agisse de blocs carrés. En particulier, le plus souvent, ces blocs sont des blocs de huit par huit pixels, leur taille dépendant de la taille des blocs sous-échantillonnés (DBi, figure 2) obtenus. Le bloc de référence 1 est pris arbitrairement comme bloc d'identité, c'est-à-dire au cas o les pixcls P1 à P16 du bloc de référence 1 correspondent en valeurs et en dispositions aux pixels du bloc de domaine en cours de comparaison. En figure 3, les pixels du bloc de référence ont été numérotés P1 à P16 et arrangés ligne à ligne de gauche à droite depuis le bas du bloc dans la position de la figure. Une première isométrie 2 correspond à une symétrie par rapport à l'axe vertical Y centré au milieu du bloc de référence. Si un bloc de domaine correspond à la disposition représentée dans l'isométrie 2 de la figure 3, il sera considéré comme pouvant être transmis sous la forme du numéro du bloc de référence 1, associé au paramètre définissant l'isométrie d'axe vertical. Une deuxième isométrie 3 correspond à une symétrie par rapport à l'axe horizontal X centré au milieu de l' image de référence. Une troisième isométrie 4 correspond à une symétrie d'axe Y=X. Cela revient à une symétrie par rapport à la diagonale Dxy. Une quatrième isométrie 5 correspond à une rotation à 180 du bloc de référence. Une cinquième isométrie 6 correspond à une rotation à 270 . Une sixième isométrie 7 correspond à une rotation à 9oo. Une septième isométrie 8 correspond à une symétrie d' axe Y=-X, c 'est-à-dire une réflexion par rapport à la diagonale D_xy. Une caractéristique de la présente invention est de n'utiliser que quatre zones mémoire de taille correspondant à la taille du bloc de référence pour stocker toutes les isométries nécessaires à la comparaison. Une autre caractéristique de l' invention est de prévoir une lecture des isométries dans des sens inversés de sorte que chaque zone mémoire contient en fait deux isométries du bloc de référence. La figure 4 illustre, par une vue schématique à rapprocher à celle de la figure 3, quatre zones mémoire M1, M2, M3 et M4 stockant le bloc de référence 1 représentées en figure 3 et ses isométries. Selon l' invention, une première zone mémoire M1 contient les dispositions 1 et 3, c'est-à-dire l'identité et la symétrie par rapport à 1'axe horizontal. Une deuxième zone mémoire M2 contient les isométries 2 et 4, c'est-à-dire la symétrie par rapport à l'axe vertical et la rotation de 180 . Une troisième zone mémoire M3 contient les isométries et 6, c'est-à-dire la symétrie d'axe Y=X et la rotation à 270 . Une quatrième zone mémoire M4 contient les isométries 7 et 8, c'est-à-dire la rotation à 90 et la symétrie d'axe Y= -X. Comme il ressort de la figure 4, pour obtenir les différentes isométries, il suffit d'organiser la lecture de la zone mémoire correspondante une fois dans un sens de haut et bas puis dans un sens de bas en haut. Une telle lecture est aisément réalisable grâce à un circuit d'adressage de la mémoire, paramétré en fonction du type d'isométrie avec lequel on souhaite comparer le bloc de domaine courant. Un avantage de la présente invention est qu'elle divise par deux l'espace mémoire nécessaire pour le stockage des blocs de référence et de leurs isométries respectives. Un autre avantage de l' invention est qu'elle ntentraîne aucune complexité des sélecteurs de mémoire. La seule contrepartie est une programmation adaptée en lecture des zones mémoire M1 à M4 contenant les isométries des blocs de référence. Bien entendu, la présente invention est susceptible de diverses variantes et modifications qui apparaîtront à l'homme de l'art. En particulier, bien que l' invention ait été décrite en référence à des isométries de blocs de référence de 4 x 4 pixels, celle-ci s' applique à n'importe quels blocs de référence carrés et leurs isométries. De plus, l' invention s' applique plus généralement à lo tout procédé de traitement d' images nécessitant le stockage d'isométries de blocs d' image, similaires à celles utilisées dans une compression fractale. En outre, la réalisation pratique des circuits nécessaires à la mise en oeuvre de l' invention et les commandes en adressage des différentes zones mémoire sont à la portée de l'homme du métier à partir des indications fonctionnelles données ci-dessus. REVENDICATIONS 1. Procédé de stockage de valeurs d'un bloc de réfé- rence et de sept isométries utilisés dans un procédé de compres- sion fractale d' image, caractérisé en ce qu'il consiste à utiliser quatre zones mémoire (M1, M2, M3, M4) de tailles identiques dans lesquelles sont respectivement stocRées l'iden- tité, et trois premières isométries correspondant aux isométries de symétrie par rapport à l'axe vertical, de rotation de 270 , et de rotation de 90 . 2. Procédé de lecture de zones mémoire remplies en application du procédé selon la revendication 1, caractérisé en ce que chaque zone mémoire est adressée dans une première direction pour la lecture des valeurs stockées en vue d'obtenir l'identité et les trois premières isométries, et dans la direction inverse pour la lecture des quatre autres isométries de symétrie par rapport à l'axe horizontal, de rotation à 180 , de symétrie par rapport à une première diagonale et de symétrie par rapport à la deuxième diagonale. 3. Procédé de compression fractale d' images utilisant un bloc de référence et sept isométries de ce bloc, caractérisé en ce qu'il comprend les étapes suivantes: - mémoriser les valeurs respectives des pixels du bloc de référence et de trois seulement de ses isométries; et - adresser les zones mémoire correspondant en lecture dans une direction ou dans la direction inverse selon l'isométrie souhaitée. 4. Procédé selon la revendication 3, caractérisé en ce qu'il consiste à stocker deux isométries du bloc de référence dans une même zone mémoire. 5. Circuit d'adressage d'une mémoire de stockage d'un bloc de référence de données image destiné à être utilisé dans un procédé de compression fractale d' image, caractérisé en ce qu'il comporte des moyens pour adresser chacune de quatre zones (M1, M2, M3, M4) de ladite mémoire dans une première direction