FR 2524740 A1 19831007 FR 8110898 A 19810602 PROCEDE DE COMPRESSION D'UNE IMAGE NUMERISEE La présente invention concerne les procédés de compression d'une image numérisée, destinés à réduire la quantité d'informations représentant cette image, avant de stocker ou de transmettre celle-ci Dans le premier cas, une compression permet d'utiliser une mémoire de taille plus faible 5 donc moins coûteuse Dans le deuxième cas une compression permet de transmettre, en un temps donné, une image par un canal dont le débit est plus faible. On distingue deux catégories de procédés de compression d'une image, ceux utilisant une mémoire de trame et ceux utilisant une mémoire 10 ligne Ces derniers sont moins performants mais nécessitent une mémoire de taille plus faible donc moins coûteuse Le procédé selon linvention appar- tient à cette deuxième catégorie Dans cette catégorie de procédés l'art antérieur comprend principalement les procédés de codage par pentes et de codage par plages Les critères d'appréciation des résultats obtenus sont le 1 5 facteur de réduction de la quantité d'information, la complexité des algorithmes, traduite par le nombre d'opérations élémentaires de calcul effectuées pour chaque point, et lécart-type entre les valeurs de brillance de Pimage reconstituée et les valeurs de brillance de l'image originale. Parmi les deux procédés cités ci-dessus le codage par plages est 20 celui qui obtient le meilleur facteur de réduction, pour un écart-type donné et un nombre d'opérations donné Son principe est le suivant: Une image est analysée, et la valeur de la brillance de chaque point est numérisée Puis, au lieu de coder la brillance de chaque point individuel- lement, le procédé consiste à coder en une fois la brillance de "plages", 25 constituées de points adjacents appartenant à une même ligne et ayant la même valeur de brillance Chaque plage est caractérisée par sa longueur et sa brillance Le codage consiste à remplacer la suite des valeurs de brillance des points, par une suite de couples longueur-brillance Ce procédé est simple, il nécessite peu de calculs, il ne cause pas d'erreur de codage- 30 décodage, mais le facteur de réduction de la quantité d'information est faible, 1,1 à 1,3 Ce procédé est décrit notamment dans "A Probabilistic Model for Run-Length Coding of Pictures" par J CAPON, I R E , Transac- tion Information Theory l T 5, du 4 décembre 1954, pages 157-163, et dans 2 "Run Length Encodings", par S W GOLOMB l E E E Transaction information Theory l T 12, juillet 1966, pages 399-401. D'autre part, l'art anterieur comprend une methode de compression de données, très classique, le codage différentiel, avec pour perfectionne- 5 ment une pondération de la valeur de reference, pour diminuer l'effet des erreurs de transmission Ce codage est décrit dans "Delta Modulation Systems" Pentech Press London, par R STEELE. Par exemple, si la référence est prise sur la même ligne, la valeur B.ij de la brillance du jeme point de la ieme ligne peut être codée par 1 J 10 Dij = Bij Bij I o ? est un nombre fixe compris entre O et 1, et Bi, j 1 la valeur de la brillance du point immédiatement précédent sur la même ligne. Le procédé selon l'invention étend le codage par plage aux deux dimensions et le combine avec le codage différentiel avec pondération, pour 15 obtenir de meilleures performances. Selon l'invention, un procéde de compression d'une image numérisée par codage d'une suite de valeurs numériques Bij B étant une valeur caractéristique du point de rang j situe sur la i ligne de l'image, caractérise 20 en ce que pour le codage des valeurs Bij caractéristiques des points de la ime ligne, i étant supérieur à 1, trois suites de valeurs numériques sont calculées pour j = I à N: 51 (aij = Bij B' i-l,j ) 52 bij Bij B'i -lj-l 25 53: (cij = Bij B I Bij,j+) o N est le nombre de points par ligne, o est un nombre fixe, compris entre 0,5 et 1, choisi pour optimiser la compression d'information selon le type d'image traite, et o B' ilj Bilj_ , B'il sont les valeurs comprimées expansees de Bilj , Bil_ 1 , Bi-l,j+l; 30 en ce que la suite de valeurs caracteristiques des points de la ieme ligne, (Bij j = I à N) est codée par blocs formés de valeurs Bij consécutives; en ce que si Bip est la valeur de rang le plus grand appartenant au bloc precedant le bloc considéré sur la i 6 me ligne, la valeur de rang le plus grand appartenant au bloc considére est Bi Q telle que Q = Max (K, L, M) o 35 K, L et M sont des nombres entiers inférieurs à N et tels que 3 pour j = P+l à K, ( Max aij Min aij)Z 2 e pour j = P+ 1 à L, (Max bij -Min bij) A> Min aij si Q = K, ou telle que pour j = P+ 1 à L Max bij>, A) Min bij si Q = L, ou telle que pour j = P+ 1 à M Max cij > A >y Min cij si Q =M, un mot binaire D, appelé indicateur de décalage, diffèrent selon que Q 15 est égal ài, L, ou M; en ce que la première ligne (i=l) est comprimée et expansée selon un procédé quelconque; et en ce que pour j =P+Il à Q la valeur décodée B'ij de la valeur caractéristique Bij est 20 égale à A+ B' i-l j si au codage Q = K, ou bien à A + ) B'i 1 j 1 si au codage Q= L, ou bien à A+ B'I si au codage Q = M, i.-ls+l la distinction entre ces trois cas étant assurée par l'indicateur de décalage D. 25 L'invention sera mieux comprise et d'autres caractéristiques apparaîtront dans la description ci-dessous et les figures s'y rapportant: la figure I représente un exemple cd'organigramme des opérations de codage d'une image par le procédé selon l'invention. les figures 2, 3 et 5 représentent en détails des parties de 30 l'organigramme représenté par la figure 1. la figure 4 représente un exemple de mise en oeuvre d'une partie de l'organigramme représenté par la figure 1. la figure 6 représente un exemple d'organigramme des opérations de décodage d'une image par le procédé selon l'invention. 35 les figures 7 et 8 représentent en détails des parties de l'organi- gramme représenté par la figure 6. 4 Les valeurs numeriques 13 _ cdracteristiques des points de l'image 1 l peuvent être, notamment,les valeurs de brillince. Des perfectionnements connus permettent d'aineliorer notablemilent le procede de codage par plages. 5 Une première amélioration consiste a definir une tolerance autour de la valeur de brillance de chaque plage Cette tolerance peut être egale a 1 ou 2 % de la valeur maximale de la brillance Ce nivellement des plages est peu gênant pour la qualité de l'image, il a même l'avantage de supprimer une partie du bruit Plus la tolérance est grande plus les plages sont longues, 10 statistiquement, et plus le facteur de réduction est grand, en contrepartie l'écart type augmente. Une deuxieme amélioration consiste a optimiser le nombre des bits alloués au codage de la longueur des plages Par exemple, pour des images comportant 512 points par ligne, 80 % des plages, ont statistiquement une 15 longueur inférieure à 8 points Le champ réservé au codage de la longueur est choisi égal à 8 bits Les plages de longueur supérieure à 8 points sont codées en plusieurs fractions. Une troisième amélioration connue consiste à optimiser le nombre de bits alloués au codage de la brillance d'une plage Pour des brillances 20 codées sur 8 bits, par exemple, la difference des brillances de deux plages consécutives dépasse rarement + 16 Le codage optimisé consiste à trans- mettre les différences de brillance, avec seulement 5 bits, au lieu de la valeur absolue codée sur 8 bits Quand la valeur de la différence des brillances est plus grande que + 16, ce qui est exceptionnel, elle est 25 remplacée par la valeur absolue de la brillance codée sur 8 bits Pour distinguer ces deux cas un bit est rajouté au champ de codage de la brillance. Le procédé selon l'invention perfectionne le procedé de codage par plages, notamment en exploitant la corrélation existant entre les brillances 30 d'une part, entre les longueurs d'autre part, des plages de deux lignes successives Si Pimage est tramée, les deux lignes considérées appartiennent à la même trame. Par ailleurs le procédé selon l'invention combine avec le procedé de codage par plages, le procédé de codage différentiel; avec un coefficient de 35 pondération ?^ choisi preferentiellement égal a 2 Compte-tenu des carac- téristiques statistiques des valeurs des brillances d'une image ce coefficient donne un taux de compression particulièrement bon D'autre part, une division par 2 est facile à réaliser sur un calculateur, et en peu de temps, car elle peut être faite en décalant d'un rang les chiutres binaires du nombre à diviser. 5 Le procede selon l'invention comprend trois grandes étapes, dont la première est l'exploitation de la correlation entre les brillances des points de deux lignes successives La brillance B du point de rang j sur la jèmne ligne subit un codage différentiel pondere ayant pour reterence une des valeurs de brillance Bl I j ou B I j ou Bl I , qui correspondent respec- 10 tivement au point homologue du point courant sur la ligne précédente, au point précédant et au point suivant ce point homologue. Aprés leur stockage ou leur transmission les données sont décodées pour être utilisables Le décodage utilise comme reéfrence une des valeurs de brillance codées-décodées B'i I j ou B' I j ou B'i I j+l correspondant à 15 Bi Iîj * Bl Bl j I B i I j+l Il y a une certaine erreur entre les valeurs originales et les valeurs codées-décodées Pour éviter de faire le codage et le décodage avec deux références non identiques, ce qui causerait une erreur supplémentaire, le codage prend en fait comme référence une des valeurs codées-décodées B' ij, B' ,B- 20 Selon les cas, le point de la ligne précédente ayant la valeur de brillance la plus proche de celle du point courant est soit le point homologue, soit le point qui précéde, soit le point qui suit le point homologue Pour améliorer la compression d'information obtenue par le codage différentiel le procédé selon l'invention utilise comme référence la 25 valeur de brillance du point qui permet la meilleure compression d'informa- tion D'autre part, il combine le codage par plages au codage différentiel pondéré utilisant une de ces trois reférences Les valeurs de brillance sont codées par blocs, correspondant a des points adjacents sur une ligne, mais contrairement au codage par plages, ces points n'ont pas une même 30 brillance, ils ont une même différence de brillance par rapport à leur point de référence respectif situé sur la ligne précédente, exactement au même rang, ou avec un décalage d'un rang à droite ou à gauche Les points correspondant à un bloc étant traités globalement, la position relative de leur point de référence respectif est prise identique, soit non décalée, soit 35 décalée à droite, soit decalee à gauche Deux bits sont nécessaires pour indiquer, au moment du décodage d'un bloc, la position relative des points de référence. Soit par exemple une image numérisée, comportant-512 lignes de 512 points, o la brillance de chaque point est numérisée par un octet, représenté par les valeurs hexadécimales des deux demi-octets: Ligne i à coder : 50, 53, 53 ,54 ,61 ,60 ,71 ,70 ,70 ,68 ,69, (i> 1) lignei-I :38 ,53 ,53 ,53 ,60 ,60 ,60 ,72 ,72 ,50 ,51 ,50, (après codage et décodage) Lignei-l : 19, 26, 26, 26, 30, 30, 30, 36, 36, 25,25 ,25, pondérée par Le calcul de (Bi,j-à B'i-l,j) pour la i èrne ligne donne S :31,27,27,28,31,30,41,34,34,43,44 , Le calcul de (Bij ~ B'i ,_ 1) pour la ieme ligne donne: 'j i-hj-I 52 :31 ,34 , 27 , 28 , 35,30,41 ,40,34,324 , 44 Pour la première valeur B' -1,1 1 n'existant pas le calcul est fait avec B'i l,1 , soit 38. Le calcul de (Bi j B'ilj+ 1) pour la i&me ligne donne: 53 :24,27,27,24,31,30,35,34,45,43,44 , Pour la dernière valeur, B'I n'existant pas, c'est B' qui est i-1,N+l i-1,N utilisée à sa place. Le codage différentiel pondéré de la iême ligne fournit ainsi trois suites de N valeurs numériques Si, 52, 53, correspondant chacune à un lot de valeurs de références Ces valeurs de référence sont les valeurs de brillance de la (i-l)ème ligne, sans décalage pour 51 avec décalage d'un rang à gauche pour 52 avec décalage d'un rang à droite pour 53. Le procédé de codage par plages est alors appliqué à ces suites, en se limitant à la recherche de la première plage dans chaque suite D'autre part les nombres contenus dans une plage n'ont pas une valeur unique mais appartiennent à un intervalle e, appelé tolérance, tel que la différence entre la valeur maximale et la valeur minimale dans une plage soit inférieure ou égale à 2 e. Par exemple si e = 2, les premières plages dans SI, 52, 53 sont: 51 :31 ,27 ,28 28,31 30 ,41,34,34,43,44 , 52:31 34-, 27,28,35,30, 41, 40,34,32, 44 , 53 :24 ,27,27,241, 31 ,30 ,35 ,34 ,45 ,43, 44 , 7 Le procedé consiste a rechercher laquelle de ces plages est la plus longue, c'est-à-dire Idquelle contient le plus grand nombre de valeurs dans un intervalle de largeur 2 e = 4 La plage la plus longue est celle de la suite Sl Elle contient 6 valeurs comprises entre 27 et 31. 5 Une plage est caractérisée aussi par une valeur de différence de brillance, dite valeur mediane qui est égale à la valeur située au milieu d'une liste lorsque ses valeurs sont classées par valeurs croissantes Si le nombre de valeurs est impair la valeur médiane est une des deux valeurs proches du milieu de la liste Ces valeurs sont départagees en considérant celle qui 10 apparaît le plus grand nombre de fois dans la liste, ou qui est la plus proche de la moyenne arithmétique des valeurs 31 , 27 , 28 , 31 , 301 a pour valeur médiane 30. Une variante du procédé consisterait à choisir le nombre entier le plus proche de la moyenne arithmétique des valeurs contenues dans cette 1 5 plage Dans l'exemple ci-dessus ce serait 31 + 27 + 28 + 31 + 30 = 29. La longueur et la valeur médiane d'une plage constituent la valeur codée d'un bloc de valeurs de brillance Bij Les valeurs de brillance d'un tel bloc ne sont pas forcément identiques contrairement au codage par plages classique. 20 La longueur du bloc de valeurs de brillance correspondant à une plage, définie par le procédé selon l'invention, est identique à la longueur de cette plage. Pour coder les valeurs de brillance suivantes, le procédé consiste à rechercher dans chacune des trois suites, 51 y 52 et 53, une deuxième plage, 25 commençant à partir du 7 e rang dans l'exemple considéré: 1: longueur: 6 ; valeur: 30 A, 34 43 44, s 2: 41 40,34 ,32 ,44, 53: 45 43 44 Puis les longueurs des trois plages sont comnparees La plage la plus 30 longue est retenue pour caractériser un deuxième bloc de valeurs de brillance. Dans rexemple considéré les suites 52 et 53 possèdent une deuxième plage de longueur identique Pour les départager le critère peut être la différence de valeur par rapport à la plage précedenmnent retenue La plage 35 ayant la plus faible différence de valeur par rapport à la plage précé- demment retenue est 35 , 34 qui a pour longueur 2 et pour valeur médiane 34. ilongueur 6: valeur: 2 ~l Y,43 #44 24 l , 32 , 44 45 , 43 ,44 Ensuite une troisierne plage, commiençant du 9 e rang est recher- 5 chee dans chacune des suites, et la plus longue des trois est selectionnee Sa longueur et sa valeur mediane codent un trolsieine bloc de valeurs de brillance Ce processus est reitere Jusqu'a la fin de Id ie'lie hligne 6 ~'l 10 2 ; 34 3 ; 44 Chaque bloc de valeurs de brillance est code par sa longueur, la valeur médiane de la plage correspondante, et par deux bits indiquant que le codage de ce bloc a lieu par rapport à la ligne precedente, sans décalage ( 51), ou avec décalage à droite ( 53) ou avec décalage à gauche ( 52). 15 Les blocs de valeurs de brillance, ainsi définis ne coïncident pas forcément avec les plages de brillance constante qui auraient eté définies par le procéde classique de codage par plages Le terme bloc est employé pour éviter toute confusion avec les plages définies par le procédé classique. Soit G la longueur d'un bloc, A la difference de brillance et D) le mot 20 binaire indicateur de décalage La brillance decodee B'i de chacun des G l J points correspondant à un bloc sera égale à A + ^ 13 ou A+ + B' Ài-l,j ou A + X B' Ài-l,j-I ou A+~g Ài-l,j*l 25 selon la valeur de l'indicateur de décalage. Le procede selon l'invention comporte une deuxième grande etape qui est l'exploitation de la correlation entre les longueurs des plages de deux lignes successives: Dans le procede selon l'invention la longueur G d'un bloc de valeurs 30 de brillance est codée différentiellement par rapport à celle du bloc le plus proche appartenant a la ligne precedente, quand elle existe Pour déterruiner eme la position relative des blocs de la (i-l)eme ligne par rapport à ceux de la .eme ieme ligne en cours de traitement, une table mémorise le rang reperant dla position du milieu de chaque bloc de la (i-l)&me ligne, ainsi que leur 35 longueur Le bloc le plus proche est celui dont le milieu est le proche du 9 milieu du bloc considere Soit G" la longueur du bloc le plus proche sur la (i-l> ligne La longueur codée du bloc considéré est alors: H= G->\ G" Au décodage, le nombre de points correspondant à ce bloc est égal à 5 G'=H+ h G". La troisième grande étape du procédé selon l'invention est l'exploi- tation de la corrélation entre les différences de brillance de deux blocs adjacents sur la même ligne: Elle consiste à coder, par un codage différentiel avec une pondéra- 10 tion, la valeur de différence de brillance A d'un bloc par rapport à celle, A" du bloc immédiatement précédent sur la même ligne. La valeur codée de A est J = A 7 A" Si le bloc considére est le premier de la ligne A" = O J = A. Après décodage la différence de brillance du bloc considéré est: 15 J'=J + i A" La première ligne de l'image constitue un cas particulier puisque son codage ne peut avoir pour référence la ligne précédente, qui n'existe pas. Tout autre procédé de codage peut être utilise, par exemple un codage par plages amélioré, consistant à coder les valeurs de brillance B j (j=l à N) par 20 blocs, appelés plages, constitués de valeurs B j consécutives, comprises dans un intervalle tel que (Max B Min B), = 2 Après décodage la valeur de brillance de tous les points d'une plage est égale à: Ao = C + ) - A"l 35 Le procédé decrit ci-dessus peut être amélioré en lui combinant d'autres procédés connus, pour comprimer encore les données résultant des opérations de compression decrites. 10 En premier lieu, il est possible d'utiliser le procéde de codage cfd'Huffmann ou codage à prefixe: 11 consiste a exploiter les caractéristiques statistiques des symboles à coder pour diminuer le nombre total de bits à transmettre Le nombre de bits codant un symbole dépend de celui-ci, les 5 symboles apparaissant le plus frequemment sont codes par un très petit nombre de bits, les symboles apparaissant peu frequemment sont codés par un nombre maximal de bits Ces bits sont stockes ou sont transmis sans trame permettant d'individualiser les symboles ce qui réduit la quantité d'informations Pour permettre le décodage, les mots binaires représentant 10 les symboles sont constitués de telle façon qu'aucun de ces mots ne peut être obtenu en rajoutant des bits à la suite d'un autre mot du code, plus court Exemple: On veut coder les messages A, B, C, D, E, F, G, H affectes des probabilités d'occurrence suivantes: A B C D E F G H 1 5 0,4 0,05 0,2 0,02 0,1 0,03 0,14 0,06 Ces symboles sont classes par ordre de probabilités d'apparition décroissantes et sont codes selon une méthode décrite, par exemple, dans "A Method for the Construction of Minimum Redundancy Codes", Proceedings of the I R E , David A Huffmann Septembre 1952 ; et dans "Probabilistic 20 Information Theory" par Jelinck, Editions Mac Graw Hill. Symbole Probabilité Code A 0,4 O C 0,2 111 G 0,14 101 25 E 0,1 100 H 0,06 1100 B 0,05 11011 F 0,03 110101 D 0,02 110100 30 Le décodage peut être fait par l'une des méthodes décrites dans les publications citées ci-dessus. Dans le procede selon l'invention le codage de Huffmann est appliqué aux données résultant dejà d'une combinaison de codages appliquée aux valeurs de brillance d'une image Pour établir les tables de codage et de 35 décodage propres à ce cas, il est nécessaire d'utiliser les caractéristiques statistiques de ces donnees apres ces codages et non pas des données Il originales Ces calculs statistiques sont fait une seule fois, pour un type d'image donne L'expérience montre que ces caractéristiques statistiques varient peu en fonction du type d'image Il y a deux codes de Huffmann différents, l'un pour les longueurs de bloc, l'autre pour les valeurs de 5 différence de brillance, puisque ces deux grandeurs n'ont pas les mêmes caractéristiques statistiques Les valeurs des longueurs et des brillances des, plages de la première ligne sont codées avec ces mêmes codes L'indicateur de décalage D ne comportant que 2 bits peut être codé par un codage de Huffmann très simple, consistant à représenter l'absence de décalage, qui 10 est le cas le plus fréquent, par le code 0, qui ne nécessite qu'un bit, et les décalages à droite et à gauche par des mots de deux bits par exemple 11 et 10. En second lieu, si un codage de Huffmann n'est pas utilisé, il est néanmoins possible d'exploiter les caractéristiques statistiques des données 1 5 codées obtenues selon le procédé décrit précédemment par une optimisation des champs codant les différentes valeurs. Par exemple, si les lignes ont 512 points la statistique des longueurs de blocs pour un ensemble d'images montre que 80 % des longueurs sont inférieures à 8 points Il suffit donc de coder les longueurs sur 3 bits Les 20 blocs de longueur supérieure à 8 points sont codés en plusieurs fractions. Si les différences pondérées entre les valeurs des brillances sont, par exemple, comprises le plus souvent entre + 16 et -16 le nombre de bits optimal est de 5 Comme il est nécessaire de pouvoir coder des valeurs supérieures à 16 en valeur absolue, il est prévu de coder ces valeurs 25 exceptionnelles sur 8 bits permettant de couvrir tous les 256 niveaux de brillance d'une image Pour distinguer les deux cas un bit supplémentaire est adjoint aux bits de données Quand le nombre de bits utilisés passe à 8, il est le même que s'il n'y avait pas de codage différentiel, il est alors avantageux de ne pas utiliser le codage différentiel par rapport au bloc précédent sur la 30 même ligne et de représenter par ces 8 bits, la valeur réelle de la différence de brillance du bloc considéré L'utilisation de la valeur réelle a pour avantage d'arrêter la propagation des erreurs survenues éventuellement auparavant. Ces variantes améliorent la compression dans le cas o un codage 35 dc Huffmann n'est pas utilisé Sinon elles ont peu d'intérêt. 12 En troisième lieu, il est possible de proceder à l'élimination du bruit de forte amplitude Le bruit de faible amplitude est eliminé en définissant l'intervalle de tolérance 2 e entre deux valeurs d'une même plage Pour éliminer le bruit de forte amplitude un procédé complementaire est 5 employé Il consiste a considérer qu'une valeur de différence de brillance qui ne peut appartenir à la plage qui la précede, est aberrante si la valeur suivante peut appartenir à cette même plage La valeur aberrante est alors remplacée par la valeur représentative de la plage, en loccurrence la valeur médiane Si la valeur suivant la valeur hors de la plage ne peut appartenir à 10 cette plage, une nouvelle plage est définie à partir de la première valeur hors de la plage précédente L'élimination des valeurs aberrantes dues au bruit de forte amplitude, non seulement améliore la qualité de l'image restituée, mais augmente le facteur de réduction, en évitant des fractionne- ments inutiles de plages. 1 5 Enfin, lorsque les données compressees constituant une image sont juxtaposées en série, par exemple pour les transmettre, l'absence de trame individualisant les données point par point se traduit par une réduction importante du débit d'information Néanmoins, il reste nécessaire de répérer le début des lignes Pour cela, il est commode d'utiliser le format HDLC, 20 classique, qui consiste à faire précéder chaque lot de données par un motif caractéristique Les données compressées correspondant à une ligne ont une longueur variable et constituent un lot, précédé d'un motif HDLC : 01111110 Pour éviter qu'un tel motit soit présent parmi les bits de données, un dispositif automatique détecte ces motifs présents dans les 25 données et les modifie en rajoutant un bit au niveau O après tout groupe de 5 bits consécutifs au niveau 1 A la réception un autre dispositif automatique supprime systématiquement le bit de niveau O qui suit un groupe de 5 bits au niveau 1 dans les données. Pour éviter la propagation d'une erreur au-delà d'une ligne, il est 30 possible de placer après chaque lot de données un mot de code détecteur d'erreur, du type CRC classique, par exemple Une ligne erronnée est remplacée par la ligne précédente, ou par la ligne homologue dans l'autre trame, si une mémoire de trame est utilisée. Le procédé selon l'invention est applicable à une image quelconque 35 fixe ou animée Si elle est composée de deux trames celles-ci sont traitées indépendemment, en l'absence de mémoire de trame Une variante du procédé consiste à stocker une trame en mémoire, calculer la différence pondérée des valeurs de brillance des points homologues dans les deux trames et comprimer la valeur de cette différence en utilisant le procédé décrit ci-dessus La valeur de la différence constitue alors la valeur 5 caractéristique B La compression obtenue est améliorée, par rapport au cas o les trames sont codées indépendemment. Il est possible de comprimer aussi -des images de télévision couleur en appliquant le procédé selon l'invention à la valeur de luminance Y et aux deux valeurs de chrominance B-Y et R-Y Ces trois valeurs caractéristiques 1 ( Bij sont codées séparément Chaque valeur de luminance est propre à un point, par contre chaque valeur de chrominance est commune à deux points adjacents Par exemple pour les 5 premiers points d'une ligne, les données originales sont 8 bits 4 bits 8 bits 4 bits | 8 bits | 4 bits | 8 bits | 4 bits 8 gbits 4 bits 15 Yl | Rl-Yl Y 2 Bl-Y | Y 3 R 3-Y 3 Y 4 B 3-Y 3 Y 5 5-Y 5 12 bits En ne calculant les valeurs de chrominance que pour une ligne sur deux le nombre de bits par point sera, en moyenne, égal à 10 bits Les deux lignes appartiennent à la même trame, sauf si une mémoire de trame est 20 disponible. La mise en oeuvre du procédé selon l'invention peut être réalisée par un dispositif à logique câblée ou à logique programmée dont la réalisation est à la portée de l'homme de lart Par exemple, pour lacompression d'une image non tramée, ce circuit effectue les opérations dont la séquence est 25 représentée sur la figure 1 Les valeurs de brillance Bij sont fournies en série au dispositif, qui les code et les restitue en série en insérant des motifs binaires permettant d'identifier le début d'une image et le début dune ligne. Au départ le dispositif est en attente Avant de recevoir des valeurs de brillance, il reçoit un signal de synchronisation indiquant qu'une image va 30 être commencée ou qu'une ligne va être commencée Si c'est le début d'une image le dispositif génère un motif binaire HDLC, par exemple 011111110, pour identifier le début de l'image Ensuite il initialise un compteur de ligne à i = 1, et traite toutes les valeurs de brillance de la première ligne par un algorithme de codage propre à cette ligne et qui est décrit plus loin. 35 Par contre, si le dispositif reçoit un signal de synchronisation annonçant le début d'une ligne, un autre motif binaire HDLC, par exemple - 01111110, est généré Le compteur de ligne est incrémenté d'une unité Les valeurs de brillance de toute la ie ligne sont alors traitées par un algorithme de codage, qui est décrit plus loin Ces deux programmes de codage n'incluent pas les codages de Huffmann, qui sont réalisés après. 5 Pour permettre les traitements ultérieurs, sont stockées: les valeurs J de différence de brillance codées, sans le codage d'Huffmann, de la ième ligne; éme les valeurs B' j de brillance codées-décodées de la i ligne, éme les rangs repérant la position des blocs de la (i-1) ligne. 10 Les valeurs de brillance Bi, codées par les valeurs codées J des différences de brillance et les valeurs codées H des longueurs de blocs, subissent un codage d'Huffmann, selon deux tables de codage distinctes, une pour les différences de brillance, une pour les longueurs de blocs Les données codées de la première ligne ont des caractéristiques statistiques 15 différentes de celles des données codées des autres lignes, néanmoins les mêmes codes de Huffmann sont utilisés. Un mot de code détecteur d'erreurs, du type CRC de 16 bits, est calculé par un algorithme classique, et est adjoint à la séquence des données codées d'une ligne Cette séquence est fournie en série au dispositif 20 utilisateur des données, puis le dispositif réalisant la compression passe en attente. Les étapes du codage, applicables à toutes les lignes sauf la première, sont représentées sur la figure 2 Les valeurs de brillance de toute la i ème ligne sont mémorisées Une première suite Si: ,aj = Bl BI 1 25 est calculée, pour j = I à N; B'I est la valeur codée-décodée de la e m brillance du point de rang j sur le (i-l) ligne Les valeurs de brillance B subissent ainsi un codage différentiel, pondéré d'un coefficient \= , par rapport aux valeurs de brillance, B il-j , de la ligne précédente non décalée. Une deuxième suite 52 : bij = B' est calculée pour j = l 30 à N ; B'i l ô l est la valeur codée-décodée de la brillance du point de rang j- I sur la (i-t)e e ligne Les valeurs de brillance B subissent ainsi un codage différentiel, pondéré par un coefficient )\ = 2 par rapport aux valeurs de brillance, B I ô t, de la ligne précédente décalée d'un rang vers la gauche. Une troisième suite 53: c 1 j = B ad B'I est calculée pour j = 1 i-1,j 4-1 35 à N; B'I est la valeur codée-décodée de la brillance du point de rang i-sj l eme l j+ 1 sur la (i-t)emeligne Les valeurs de brillance B ' subissent donc un codage différentiel, pondéré par un coefficient par rapport aux 2 pr valeurs de brillance BièI j+ de la ligne précédente décalée d'un rang vers la droite. Un algorithme, décrit plus loin, est appliqué à chacune des suites 5 51 ' 52 ' 53 pour déterminer une plage dans chaque suite, avec une tolérance e donnée, et en éliminant les points aberrants isolés dans une plage Dans le cas général, la plage précédente s'arrête, par exemple, au rang P Soit K, L, M les rangs constituant les bornes supérieures respectives de chacune de ces plages Soit G le nombre de valeurs contenues dans la plage la plus longue. 10 G= Q-PoQ= Max(K,L, M) Un mot binaire D est généré pour indiquer si Q = Max (K, L, M) = K, ou L ou M. La valeur médiane A, des valeurs de différence de brillance consti- tuant la plage la plus longue, est calculée, puis est codée différentiellement 15 avec une pondération > = 2 par rapport à la valeur médiane A" du bloc précédent sur la même ligne Si ce bloc n'existe pas la valeur médiane A" est prise égale à 0. J = A ->) A" La longueur G est codée différentiellement, avec une pondération 20 >I = par rapport à la longueur G" du bloc précédent sur la même ligne, s'il existe S'il n'existe pas G" = 0. H = G -> G" Si Q = N le codage de la ième ligne est terminé, le traitement se poursuit par le stockage des données codées, comme représenté sur la figure 25 I. Si Q i N, le codage de la ieme ligne n'est pas terminé, trois nouvelles plages sont déterminées respectivement dans les suites SI S, 53 ; la plus longue est recherchée et codée comme décrit ci-dessus. La figure 3 représente un exemple d'organigramme des opérations de 30 détermination d'une plage o les différences de brillance sont identiques à une tolérance e près, en éliminant les points aberrants isolés Cet organi- gramme considère les valeurs aij de la suite 51 à titre d'exemple mais il est identique pour les suites 52 et 53 * Un indicateur logique I (drapeau) est initialisé à O Un compteur de 35 rang j est initialisé à la valeur P+ I o P est le rang de la borne supérieure de la plage la plus longue trouvée précédemment Un compteur de longueur de plage G est initialisé à zéro. 16 Le dispositif calcule M aij + e. et m aij e Les compteurs de rang j et de longueur G sont incrémentés d'une 5 unité :j,* j+l ; G m la valeur a j appartient à la plage, la valeur précédente a était aberrante Elle compte pour la longueur du bloc, mais pas pour la détermination de la valeur médiane Seule aij est mémorisée dans la mémoire servant pour le calcul de la valeur médiane. -D'autre part l'indicateur I est remis à zéro pour pouvoir resservir s'il 35 y a une autre valeur douteuse isolée dans la même plage Le compteur de rargsest testé Si son contenu j est inférieur à N le traitement recommence 17 à partir de l'incrémentation de ce compteur S'il est égal à N, la ligne étant terminée, la plage est terminée aussi, ce traitement est fini La valeur de G indique la longueur de la plage. b) Si M^^ m, l'indicateur I est testé Si la valeur précédente était 5 douteuse, I = I, ceci confirme que la plage est terminée, le traitement est fini Le compteur de rang est décrémenté de deux unités puisque les deux dernières valeurs n'appartiennent pas à la plage, elles ne doivent pas compter dans sa longueur: G m est réalisée tant que la courbe M est au-dessus de la courbe m Chaque fois qu'une valeur a j s'éloigne de la plage et devient une 15 valeur extrêmale de la plage les deux courbes M et m se rapprochent irréversiblement A la 14 ème valeur la courbe m (en pointillés)passe au- dessus de la courbe M, cette 14 me valeur ne fait donc pas partie de la plage, a priori Dans ce cas Palgorithme reconstitue les valeurs de M et m précédentes et considère la valeur a suivante ( 15 eme rang) par rapport à 'J 20 ces valeurs (traits pleins) La valeur suivante, ai,15, ne provoque pas d'intersection de ces courbes, elle appartient donc à la plage La valeur douteuse ai 4 est considérée comme aberrante, elle n'interrompt pas la plage. La figure 5 représente la séquence des opérations de codage propres 25 à la première ligne. Les valeurs de brillance B j arrivent en série et sont stockées en attendant que toutes soient disponibles Un compteur de rang est initialisé à zéro j O Les plages telles que (Max B 1 j Min B 1 j) 18 C = B ?' B"o. Le compteur de rangsj est testé Si j Un compteur de lignes est incrémenté, in i±, la reconnaissance 20 du début de la ligne suivante déclenche la mémorisation des données codées de cette ligne, et la reconnaissance du prochain début de ligne arrête cette mémorisation Ceci permet de séparer les données de chaque ligne Le mot de détection d'erreur CRC est testé S'il y a une erreur, les données de cette ligne ne sont pas décodées, les valeurs de brillance de la ligne précédente 25 sont stockées dans la mémoire d'image à la place des valeurs qui auraient été erronnées S'il n'y a pas d'erreur un algorithme, décrit plus loin, décode les données en prenant pour référence les valeurs de brillance de la ligne précédente Les valeurs de brillance résultantes sont stockées dans la mémoire d'image Le compteur de ligne est testé; si l'image est terminée le 30 dispositif attend le prochain motif binaire 011111110 caractéristique du début de l'image suivante Si Pimage n'est pas terminée, les opérations recommencent à partir de la reconnaissance du début de la ième ligne après avoir incrémenté le compteur de lignes i 4 i+l. La figure 7 représente un exemple d'organigramme des opérations 35 réalisant le décodage de la ieme ligne par rapport à (i-1)éme ligne (i 19 correspondant à un premier bloc de valeurs de brillance sont lues en mémoire Un premier décodage de Huffminann fournit une valeur de différence de brillance codée différentiellement J Un deuxième décodage de Huffmann fournit H valeur de longueur de bloc codée différentiellement La 5 valeur codée 3 de la différence de brillance du bloc est décodée en prenant pour référence A" différence de valeur de brillance du bloc précédent sur la même ligne, s'il existe: A' = J+ > A" La valeur codée H de la longueur du bloc est décodée par rapport à la longueur G" du bloc le plus proche situé sur la ligne précédente: 10 G' = H+ t G" Le compteur de rangs est incrémenté de la valeur G' La valeur codée A' de la brillance est décodée avec pour référence une des valeurs de brillance Bi_, ou B'ilj ou B'ilj+ correspondant respectivement au i-î,j i-î,j-î u i-,+ point en face, au point décalé à gauche et au point décalé à droite sur la 15 ligne précédente. B Ij = A' +? i , ou B' = A' + B' ou 20 20 BB'ij = A +) B' i-l,i+l La sélection est faite selon la valeur du mot binaire D, indicateur de décalage, accompagnant les données codées Les valeurs de brillance B'ij obtenues sont stockées dans la mémoire d'image Le compteur de rangs est testé Si la ligne est terminée, j = N, ce traitement est terminé Si la ligne 25 n'est pas terminée, j 20 est décodée par rapport à la valeur B"` de la brillance de la plage précédente, si elle existe Pour la première plage la référence B"o est égale à 0. B' = C t A B` o 'o 5 Les G valeurs de brillance Bj = B'i sont mémorisées dans la mémoire d'image. Le contenu du compteur de rangs est testé Si j REVENDICATIONS 1 Procédé de compression d'une image numérisée par codage d'une suite de valeurs numériques Bi, Bi étant une valeur caractéristique du À, èmel ~l, point de rang j situé sur la ieme ligne de l'image, caractérisé -en ce que pour le codage des valeurs Bij caractéristiques des points 5 de la ime ligne, i étant supérieur à 1, trois suites de valeurs numériques sont calculées pour j = I à N: S:(a =B -X- B' ) SI: (aij = Bij -) Bi-1,j 52 (bij Bl >B'i-lj -) 2 ij ij 'i-l,j-I 53: (Cij Bij ) B il,j+l) 10 o N est le nombre de points par ligne, o est un nombre fixe, compris entre 0,5 et 1, choisi pour optimiser la compression d'information selon le type crd'image traité, et o B'ilj B'ilj_l , B'_,+ sont les valeurs comprimées-expansées de Bil Bilj_ Bilj+; i-ili i-lj-1 i-lj+l eme en ce que la suite de valeurs caractéristiques des points de la ie 15 ligne, (Bij, j = 1 à N) est codée par blocs formés de valeurs Bij consécu- tives; en ce que si Bip est la valeur de rang le plus grand appartenant au bloc précédant le bloc considéré sur la iime ligne, la valeur de rang le plus grand appartenant au bloc considéré est Bl Q telle que Q = Max (K , L, M) o 20 K, L et M sont des nombres entiers inférieur à N et tel que pour j= P+I à K, (Max aij Min aij) / A>, Min aij si Q= K, ou telle que pour j = P+l à L Max bij> A>, Min bij si Q = L, ou telle que pour j = P+l à M Max cij> A > Min cij si Q = M, un mot binaire D, appelé indicateur de décalage, différent selon que Q 35 est égal à K, L, ou M; 22 en ce que la première ligne (i=l) est comprimée et expansée selon un procédé quelconque; et en ce que pour j P+ 1 à Q la valeur décodée B'ij de la valeur caractéristique B est Ij 5 égale à A +)B B'ilj si au codage Q = K, ou bien à A +\-B'i Ij I si au codage Q L i-1,j-1 ou bien à A +> B'j 1 si au codage Q M, la distinction entre ces 3 cas étant assurée par l'indicateur de décalage D. 2 Procédé selon la revendication 1, caractérisé en ce que les 10 longueurs G des blocs sont elles-mêmes codées; en ce qu'au codage et au décodage de la i ème ligne sont calculés les rangs repérant les milieux des blocs constituant la (i-l)ème ligne, le rang repérant le milieu du bloc en cours de codage ou de décodage, et la longueur G" du bloc de la (i-l)/me ligne dont le milieu est le plus proche du milieu du bloc en cours de codage 15 ou de décodage; en ce que la valeur codée de G est H = G G"; et en ce que la valeur décodée de G est G' = H + > GC". 4 Procédé selon l'une quelconque des revendications I à 3, caractérisé en ce que le codage des valeurs caractéristiques Bij des points de la première ligne est un codage par blocs, appelés plages, constitués de valeurs Bj consécutives telles que (Max Blj Min Blj) 2 e pour les rangs j correspondant à une plage en ce qu'est calculé, pour chaque plage, le nombre Go de valeurs Bij 30 qu'elle contient, G étant appelé longueur de la plage considérée; en ce qu'est calculée, pour chaque plage, la valeur A appelée valeur caractéristique de la plage et telle que pour les rangs j correspondant à la plage considérée, Max Bij> Ao>, Min Bij 35 et en ce que chaque plage est codée par: la valeur numérique de sa longueur G 0, la valeur numérique de C = A û A" 0, o A" O est la valeur caractéris- tique de la plage précédant la plage considérée sur la première ligne, A"o étant pris égal à O si la plage considérée est la première plage de la 5 première ligne; en ce que la valeur caractéristique décodée de chaque point d'une plage a pour valeur décodée : A'o = C+ > A" O .CLMF: 5 Procédé selon l'une quelconque des revendications 1 à 4 caractéri- sé en ce que X = 0,5. 10 6 Procédé selon l'une quelconque des revendications 1 à 5, caracté- risé en ce qu'au moins une des données codées représentant la longueur, la valeur caractéristique, et l'indicateur de décalage d'un bloc subit un codage supplémentaire, chaque type de données selon un code à préfixe établi en fonction des caractéristiques statistiques propres à ce type de données. 15 7 Procédé selon l'une quelconque des revendications 1 à 6, caracté- risé en ce que le nombre de bits utilisés pour coder la longueur d'un bloc est limité à un nombre permettant de représenter la plupart des valeurs de longueur, et en ce que les autres valeurs, correspondant à des blocs exceptionnement longs, sont codées en plusieurs fractions dont la somme est 20 égale à la longueur à coder. 8 Procédé selon l'une quelconque des revendications I à 7, caracté- risé en ce que le nombre de bits utilisés pour exprimer la valeur caractéristique codée d'un bloc, J, est limité à un nombre permettant de représenter la plupart des 'valeurs J ; en ce que toute autre valeur, exceptionnellement 25 élevée, est remplacée par la valeur caractéristique A, non codée, exprimée par un nombre de bits suffisant pour représenter la valeur maximale de A; et en ce que ces deux cas sont distingués par un bit adjoint aux bits exprimant A ou J. .CLMF: 9 Procédé selon l'une quelconque des revendications I à 8, caracté- 30 risé en ce qu'un débruitage est effectué lors de la détermination des plages dans les suites Sl, 52, 53, en incorporant à -la plage qui la précède toute valeur, qui ne remplit pas les conditions pour appartenir à cette plage, mais qui est suivie par une valeur remplissant ces conditions. 10 Procédé selon l'une quelconque des revendications 1 à 9, 35 caractérisé en ce que les valeurs B caractéristiques des points de l'image sont les valeurs de brillance de ces points. 11. Procédé selon l'une quelconque des revendications I à 9, appliqué à des images de télévision, caractérisé en ce que les valeurs caractéristiques Bij des points de l'image sont les valeurs des différences de brillance entre les points homologues des deux trames formant l'image. 5 12 Procédé selon l'une quelconque des revendications I à 9, appliqué à des images de télévision en couleur, caractérisé en ce que les valeurs caractéristiques Bij des points de l'image sont les valeurs de luminance Y, et les valeurs de chrominance R-Y et B-Y; et en ce qu'elles subissent trois codages distincts. 3 Procédé selon l'une des revendications I et 2, caractérisé en ce que la valeur caractéristique A d'un bloc de la ième ligne est elle-même codée; en ce que sa valeur codée est: 20 3 = A -/ A" o A" est la valeur caractéristique du bloc immédiate- ment précédent sur la ième ligne, s'il existe, et o A" est nulle si le bloc considéré est le premier de la i 6 me ligne; et en ce que la valeur décodée de A est: A' = 3 + A"