Brevet FR2838258A1 — publié le 20031010

PROCÉDÉ DE CODAGE D'IMAGES NUMÉRIQUES UTILISANT UN CODE SPÉCIFIQUE POUR RACCOURCIR LE TEMPS DE CODAGE La présente invention se rapporte au domaine de la compression sans pertes destiné à des images numériques à deux couleurs (en général noir et blanc) . Un exemple de ce type de format de compression est le format JBIG (Joint Bi-Level Image experts Group). Dans la suite, nous expliquerons le procédé en nous référant à JBIG mais il est clair que l'invention s'étend à tout format auquel elle est applicable. Les applications de ce type de format sont nombreuses car beaucoup de domaines sensibles ont besoin d'images sans pertes : les MFP (Multi-Functions Peripherals : périphériques multi-fonctions) comme les fax, les photocopieurs ; mais aussi le domaine de l'imagerie médicale ou militaire. La présente invention se rapporte plus particulièrement à la partie codage/décodage des ces images. Elle concerne en particulier la modification des algorithmes de codage standard JBIG afin d'optimiser le temps de calcul. Elle a en effet pour objectif de réaliser un traitement d'un pixel par coup d'horloge, ce que le codage standard ne garantit pas. La présente invention a pour premier objet un procédé de codage d'images numériques comportant : une étape d'initialisation [INITENC] ; une étape de codage [ENCODE] ; une étape de nettoyage [FLUSH] ; ladite étape de codage comportant : une étape de choix ; une étape de calcul du code [CODELPS ou CODEMPS] ; une étape de renormalisation [RENORME] ; ladite étape de renormalisation comprenant en particulier une étape de sortie de code [BYTEOUT] qui comprend : une étape d'incrémentation d'une pile dans le cas où la valeur du code générée par le codeur est OxFF jusqu'à ce que la valeur dudit code soit différente de OxFF, le compteur ayant alors une valeur de n ; une étape d'écriture dans une mémoire tampon d'un code correspondant à n fois un symbole déterminé quand la valeur dudit code est différente de OxFF ; une étape de décrémentation de ladite pile ; caractérisé en ce que ladite étape d'écriture consiste à l'écriture dans une mémoire de sortie d'un code spécifique non utilisé pour d'autres fonctions, composé d'un marqueur spécifique correspondant au symbole à répéter et du nombre de répétitions de ce symbole. Selon une forme de réalisation avantageuse du procédé conforme à l'Invention, on définit trois marqueurs spécifiques pour coder 0x00000000, OxFFOOFFOO et OxOOFFOOFF. De préférence, ces marqueurs spécifiques sont OxFF82, OxFF80 et OxFF81. Avantageusement, le code spécifique est d'une longueur de deux fois 16 bits, soit 16 bits pour le marqueur spécifique et 16 bits pour le nombre de répétitions. La présente invention a également pour objet un procédé d'interprétation au vol d'une image codée conformément au procédé décrit précédemment par lecture de la mémoire de sortie permettant de générer un code standard à partir d'un code comportant des marqueurs spécifiques à l'invention caractérisé en ce que la lecture dudit code la lecture dudit code spécifique implique la génération du symbole correspondant le nombre de fois spécifié par le nombre de répétitions. De préférence, la lecture du premier marqueur implique la génération du symbole OxFFOOFFOO le nombre de fois indiqué par la deuxième partie du code spécifique, que la lecture du deuxième marqueur implique la génération du symbole OxOOFFOOFF le nombre de fois indiqué par la deuxième partie du code spécifique et que la lecture du troisième marqueur implique la génération du symbole 0x00000000 le nombre de fois indiqué par la deuxième partie du code spécifique. Avantageusement, le procédé de codage décrit précédemment comporte une étape additionnelle d'interprétation. La présente invention a aussi pour objet un procédé de décodage d'une image codée conformément au procédé décrit précédemment caractérisé en ce qu'il comporte une étape d'interprétation au début du procédé de décodage. On comprendra mieux l'invention à l'aide de la description, faite ci-après à titre purement explicatif, d'un mode de réalisation de l'invention, en référence aux figures annexées : # La figure 1 montre la décomposition de la partie encodage en plusieurs blocs ; # La figure 2 décrit la décomposition en blocs d'un bloc de réduction de résolution et de codage de couche différentielle ; # La figure 3 décrit la décomposition en blocs du codeur de plus basse résolution. Le procédé selon l'invention met en #uvre un codeur standard dans son architecture, illustré figure 1. Le codeur permet de réaliser la progressivité du codage, c'est à dire qu'une image est codée par couches, de la couche la plus grossière à la couche permettant de faire apparaître les détails les plus fins ; l'image est affichée avec plus ou moins de détails en fonction des capacités de l'équipement destiné à l'affichage (place disponible, connexion...). C'est pourquoi le bloc de codage de plus basse résolution (3) est nécessaire et les blocs de réduction de résolution et de codage de couche différentielle (2) sont optionnels. Cependant, c'est la présence de ces blocs qui permet d'obtenir plusieurs résolutions pour la même image. Le premier bloc de réduction de résolution et de codage de couche dif férentielle (1) prend l' image à coder en entrée et renvoie une image de plus basse résolution au premier bloc (2) suivant. Il envoie également le code permettant de retrouver les pixels manquants entre l'image de plus basse résolution et l'image d'entrée à la chaîne de sortie (4). Chaque bloc de réduction de résolution et de codage de couche différentielle (2) prend en entrée une image provenant du bloc de réduction de résolution et de codage de couche différentielle précédent et envoie en sortie d'une part une autre image (de plus basse résolution) au bloc suivant et d'autre part le code permettant de retrouver les pixels manquants entre l'image de sortie et l'image d'entrée à la chaîne de sortie (4). Chaque bloc de réduction de résolution et de codage de couche différentielle (1) ou (2) a une fonction identique, c'est pourquoi il est suffisant de décrire le mode opératoire d'un d'entre eux. Ainsi, pour chaque bloc, il y a seulement deux couches de résolution impliquées. Par souci de simplicité, l'image entrante est appelée image de haute résolution et l'image sortante est appelée image de basse résolution . Notons que ces résolutions ne sont en général pas la plus haute et la plus basse résolution de tout le système. D'autre part, l'image de basse résolution du bloc n est l'image de haute résolution du bloc n+1. Le bloc de réduction de résolution (10) reçoit une image de haute résolution en entrée et génère une image de basse résolution avec, si possible, deux fois moins de colonnes et deux moins de lignes que l' original . L'image de basse résolution est envoyée au bloc de réduction de résolution et de codage de couche différentielle suivant (16), au bloc de prédiction typique de la couche différentielle (11), au bloc de prédiction déterministe (12) et au bloc de patrons de modèles (14). Le bloc de prédiction typique de la couche différentielle (11) permet un gain de code mais son utilité première est d'accélérer l'implémentation. Il cherche les régions de couleur uniforme et quand il trouve qu'un pixel de l'image de haute résolution se trouve dans une telle région, aucune des étapes suivantes n'est nécessaire. Ce gain est particulièrement important pour les images de texte : 95 % de codage en moins. Il reçoit l'image de haute résolution et l'image de basse résolution du bloc de réduction de résolution (10) et envoie la valeur de la prédiction TPVALUE au codeur arithmétique (15) et au bloc de patrons adaptatifs (13) et la valeur LNTP spécifiant si la ligne est n'est pas typique , c'est à dire si un ou plusieurs pixels de la ligne seraient prédits incorrectement, au codeur arithmétique (15). Le bloc de prédiction déterministe (12) permet un gain de code de 7 % en moyenne. Quand les images sont réduites par un algorithme de réduction de résolution, il arrive parfois qu'un pixel de haute résolution soit déterminé par les pixels déjà connus du codeur et du décodeur, c'est à dire tous les pixels de basse résolution et tous les pixels de haute résolution qui sont directement en rapport avec le pixel concerné. Dans ce cas, on dit que ledit est prédictible de façon déterministe. Un drapeau est ajouté et ledit pixel n'est pas codé. Il reçoit l'image de haute résolution et l'image de basse résolution du bloc (10) et envoie la valeur de la prédiction déterministe DPVALUE au codeur arithmétique (15). Le bloc de patrons adaptatifs (13) permet un gain substantiel de code (jusqu'à 80 %) pour les images en niveau de gris. Il regarde la périodicité dans l'image et quand il la trouve, il change le patron de telle sorte que le pixel précédant le pixel courant avec cette périodicité est inclus dans le patron. Il reçoit l'image de haute résolution et la valeur de la prédiction typique TPVALUE envoyée par le bloc (11) et envoie la valeur ATMOVE de déplacement de patron au bloc de modèles de patrons(14). Pour chaque pixel de haute résolution, le bloc de modèles de patrons (14) fournit au codeur arithmétique un entier appelé contexte. Cet entier est déterminé par les couleurs de certains pixels de l'image de haute résolution, par certains pixels de l'image de basse résolution déjà disponible et par la phase spatiale du pixel à coder. La phase spatiale décrit l'orientation du pixel de haute résolution par rapport au pixel de basse résolution correspondant. Il reçoit les images de haute et basse résolution ainsi que la valeur ATMOVE du bloc (13) et envoie la valeur du contexte CX au codeur arithmétique (15) . Le bloc de codage arithmétique adaptatif (15) est un codeur entropique. Il consulte les valeurs fournies par des blocs de prédiction typique (11) et déterministe (12) pour déterminer s'il est nécessaire de coder un pixel. Si c'est le cas, il consulte la valeur du contexte et utilise son propre estimateur de probabilité pour estimer la probabilité conditionnelle que le pixel courant soit d'une couleur donnée. Le pixel étant souvent très prédictible à partir du contexte, la probabilité conditionnelle est souvent très proche de 0 ou de 1 et un grand gain de codage entropique est réalisé. Il reçoit les valeurs LNTP et TPVALUE du bloc de prédiction typique (11), la valeur DPVALUE du bloc de prédiction déterministe (12), la valeur de contexte CX du bloc de patrons de modèles (14) et l' image de haute résolution et envoie le code pour la différence entre l'image de haute résolution et l'image de basse résolution à la chaîne de sortie (17). Le codeur de plus basse résolution est plus simple que le codeur de couche différentiel parce que les blocs de réduction de résolution et de prédiction déterministe sont absents et que les blocs de prédiction typique, de patrons adaptatifs et de modèles de patrons ne tiennent pas compte d'une image de basse résolution. Cependant, les valeurs de sortie de ces blocs alimentant le codeur arithmétique sont de même nature. L'invention concerne en particulier le bloc de codage arithmétique commun aux codeurs de réduction de résolution et codage de couche différentielle et au bloc de codage de plus basse résolution. Ce codeur est plus simple que le codeur de couche différentiel parce que les blocs de réduction de résolution et de prédiction déterministe sont absents et que les blocs de prédiction typique, de patrons adaptatifs et de modèles de patrons ne tiennent pas compte d'une image de basse résolution. Cependant, les valeurs de sortie de ces blocs alimentant le codeur arithmétique sont de même nature. Nous décrivons dans la suite le détail du fonctionnement du codeur arithmétique. Ce module de codage arithmétique est alimenté par quatre variables d'entrée : VALEURPT (valeur de la prédiction typique), VALEURPD (valeur de la prédiction déterministe), CX (contexte) et PIX (valeur du pixel à traiter). En fonction des valeurs de VALEURPT et VALEURPD, la procédure ENCODAGE est appelée ou ne l'est pas. Si elle est appelée, on estime la valeur la plus probable du pixel grâce aux données fournies pas le contexte CX et si cette valeur est égale à PIX, on appelle la procédure CODEMPS. Dans le cas contraire, la procédure CODELPS est appelée. Ces deux procédures génèrent trois variables C, A et CT. Si CT est égale à 0, la procédure SORTIEOCTET est appelée et est alimentée par un octet de sortie TEMP. Dans cette procédure SORTIEOCTET, un compteur SC est mis en place. Le compteur SC est incrémenté chaque fois que TEMP est égal à OxFF. Il est remis à zéro lorsque TEMP est différent de OxFF. On incrémenté le compteur SC au lieu d'écrire OxFF en sortie car si un code avec une retenue arrive, il faut reporter cette retenue sur les codes précédents. Si le code précédent est OxFF, la retenue est propagée au code précédent et ceci autant de fois qu'il y a de OxFF consécutifs. Lorsqu'un code TEMP différent de OxFF arrive : # soit il est inférieur à OxFF, c'est à dire qu'il n'a pas de retenue (Ox4A par exemple) et dans ce cas, on génère une chaîne de sortie composée du code BUFFER correspondant au dernier code TEMP précédant la chaîne de OxFF et de SC fois OxFFOO ; on remplace la valeur de BUFFER par la nouvelle valeur de TEMP. # soit il est supérieur à OxFF, c'est à dire qu'il a une retenue (OxlC5 par exemple) et dans ce cas, la retenue ce propage jusqu'au premier terme précédent différent de OxFF. En se propageant, les OxFF sont remplacés par des 0x00 et on génère une chaîne de sortie composée du code BUFFER correspondant au dernier code TEMP précédant la chaîne de OxFF et de SC fois 0x00 ; on remplace la valeur de BUFFER par la nouvelle valeur de TEMP. Cette étape sera mieux comprise à la lecture d'un exemple (BYTEOUT est la valeur de la chaîne de sortie) : # TEMP=Ox 2A ; # TEMP=OxD4 . BYTEOUT=Ox2A ; SC=0 ; BUFFER=OxD4 ; # TEMP=Ox88 : BYTEOUT=OxD4 ; SC=0 ; BUFFER=Ox88 ; # TEMP=OxFF . SC=1 ; BUFFER=Ox88 ; # TEMP=OxFF . SC=2 ; BUFFER=Ox88 ; # TEMP=OxD6 . BYTEOUT=0x88FF00FF00 ; SC=0 ; BUFFER=OxD6 ; # TEMP=OxFF . SC=1 ; BUFFER=OxD6 ; # TEMP=OxlC4 . BYTEOUT=OxD700 ; SC=0 ; BUFFER=OxC4. Bien que la probabilité que le compteur prenne une valeur n suit une loi en 2-8n, aucune nouvelle donnée ne peut traitée pendant l'écriture de la chaîne de sortie. Il en advient que si la valeur du compteur est élevée, le temps d'interruption du traitement de l'image peut être long. Une des contraintes que l'on souhaite imposer au procédé est de traiter un pixel par coup d'horloge. Dans ces circonstances, une solution est de générer un code plus court à la place de SC fois un octet. Le procédé selon l'invention utilise pour cela des symboles non utilisés par JBIG : OxFF80, OxFF81 et OxFF82. C'est le choix qui a été réalisé dans l'invention mais ces codes peuvent être différents à condition que les symboles ne soient pas utilisés par JBIG. Dans tous les cas, trois symboles sont nécessaires : un pour coder la séquence OxFFOOFFOO ; un pour coder la séquence OxOOFFOOFF ; un pour coder la séquence 0x00000000. Un exemple permettra de faciliter la compréhension : On définit : # OxFF80 : correspond à OxFFOOFFOO # OxFF81 : correspond à OxOOFFOOFF # OxFF82 . correspond à 0x00000000 On doit générer la séquence : Ox3C62FFF OxOOFFOOFF OxOOFFOOFF OxOOFFOOFF OxOOFF008A Le codage selon l'invention permet de coder cette séquence ainsi : Ox3C62FFF OxFF810003 OxOOFF008A D'autre part, l'invention concerne un interpréteur du code spécifique définit ci-dessus. Cet interpréteur reçoit en entrée un code JBIG. Il génère en sortie une chaîne de code. Il interprète le code d'entrée en le comparant à une bibliothèque qui a été préalablement chargée dans le programme. Si un symbole n'appartient pas à la bibliothèque, il est rejeté. La particularité de l'interpréteur selon l'invention est l'inclusion dans la bibliothèque des marqueurs spécifiques à l'invention et de leur signification en langage JBIG. Ainsi, lorsqu'un des marqueurs spécifiques est détecté, l'interpréteur génère en sortie le ou les symboles JBIG correspondant au marqueur détecté. Si le symbole d'entrée n'est pas un code spécifique à l'invention et fait partie du code normalisé JBIG, l'interpréteur génère un symbole de sortie identique au symbole d'entrée. Cet interpréteur peut être intégré au codeur : une fois que toutes les étapes standards du codeur ont été réalisées, le code de sortie est envoyée dans l'interpréteur qui génère ainsi un code compatible JBIG. L'interpréteur peut aussi être implanté dans le décodeur. Le décodeur contient toujours un interpréteur destiné à lire le code avant de le traiter afin de générer l' image. Dans ce cas, un en-tête est ajouté au code avant son entrée dans le décodeur, ledit en-tête signifiant au décodeur la nécessité de charger la bibliothèque des symboles spécifiques à l'invention dans l'interpréteur standard du décodeur. L'invention est décrite dans ce qui précède à titre d'exemple. Il est entendu que l'homme du métier est à même de réaliser différentes variantes de l'invention sans pour autant sortir du cadre du brevet. REVENDICATIONS 1. Procédé de codage d'images numériques comportant : une étape d'initialisation [INITENC] ; une étape de codage [ENCODE] ; une étape de nettoyage [FLUSH] ; ladite étape de codage comportant : une étape de choix ; une étape de calcul du code [CODELPS ou CODEMPS] ; une étape de renormalisation [RENORME] ; ladite étape de renormalisation comprenant en particulier une étape de sortie de code [BYTEOUT] qui comprend : une étape d'incrémentation d'une pile dans le cas où la valeur du code générée par le codeur est OxFF jusqu'à ce que la valeur dudit code soit différente de OxFF, le compteur ayant alors une valeur de n ; une étape d'écriture dans une mémoire tampon d'un code correspondant à n fois un symbole déterminé quand la valeur dudit code est différente de OxFF ; une étape de décrémentation de ladite pile ; caractérisé en ce que ladite étape d'écriture consiste à l'écriture dans une mémoire de sortie d'un code spécifique non utilisé pour d'autres fonctions, composé d'un marqueur spécifique correspondant au symbole à répéter et du nombre de répétitions de ce symbole. 2. Procédé de codage d'images selon la revendication 1, caractérisé en ce que l'on définit trois marqueurs spécifiques pour coder 0x00000000, OxFFOOFFOO et OxOOFFOOFF. 3. Procédé de codage d'image selon la revendication 2, caractérisé en ce que lesdits marqueurs spécifiques sont OxFF82, OxFF80 et OxFF81. 4. Procédé de codage d'images selon l'une des revendications précédentes, caractérisé en ce que ledit code spécifique est d'une longueur de deux fois 16 bits, soit 16 bits pour le marqueur spécifique et 16 bits pour le nombre de répétitions. 5. Procédé d'interprétation au vol d'une image codée conformément au procédé selon l'une des revendications 2 à 4 par lecture de la mémoire de sortie permettant de générer un code standard à partir d'un code comportant des marqueurs spécifiques à l'invention caractérisé en ce que la lecture dudit code spécifique implique la génération du symbole correspondant le nombre de fois spécifié par le nombre de répétitions. 6. Procédé d'interprétation au vol selon la revendication 5, caractérisé en ce que la lecture du premier marqueur implique la génération du symbole OxFFOOFFOO le nombre de fois indiqué par la deuxième partie du code spécifique, que la lecture du deuxième marqueur implique la génération du symbole OxOOFFOOFF le nombre de fois indiqué par la deuxième partie du code spécifique et que la lecture du troisième marqueur implique la génération du symbole 0x00000000 le nombre de fois indiqué par la deuxième partie du code spécifique. 7. Procédé de codage selon la revendication 1, caractérisé en ce qu'il comporte une étape additionnelle d'interprétation selon la revendication 5. 8. Procédé de décodage d'une image codée conformément au procédé selon la revendication 1, caractérisé en ce qu'il comporte une étape d'interprétation préalable au décodage de ladite image, ladite étape d'interprétation étant définie par le procédé d'interprétation selon la revendication 5 ou 6.