La présente invention se rapporte principalement au domaine des codages binaires entropique, plus particulièrement des codages utilisant des modèles d'encodage du type « range coder », c'est-à-dire utilisant des intervalles, ou arithmétique.

Les encodeurs du type range coder ou arithmétique permettent d'encoder sans perte une suite de symboles. Ces symboles peuvent être de tout type, notamment de caractères alphanumériques ou des caractères de ponctuation. Dans le cas de procédés de compression d'une image, les symboles sont des nombres résultant de la compression préalable de ladite image, par exemple par une compression différentielle ou une compression par ondelettes, généralement précédée d'une transformation côlorimétrique.

Un codage binaire dit entropique permet de réduire le nombre de bits nécessaires pour coder un signal, ici représenté par la suite des symboles à encoder, sans perte sur le contenu de celui-ci. Le niveau de réduction dépend de la probabilité d'occurrence des symboles dans le signal. En particulier, les codages dits « arithmétique » et « range coder » utilisent des modèles de probabilité au sein desquels chaque symbole est associé à une probabilité. Le nombre théorique de bits nécessaires pour coder le symbole est, dans le cadre d' un codeur de type « Range Coder » ou codage arithmétique, -log2(P), où P est la probabilité d' occurrence de ce symbole dans le signal.

Un codeur du type range coder ou codeur arithmétique doit toujours avoir, lors de l' encodage ou du décodage d' un symbole, un modèle de probabilité comprenant un ou plusieurs symboles, ainsi que leur probabilité d' occurrence, dont au moins le symbole courant. La probabilité du symbole est utilisée pour Γ encoder. Pour encoder un même signal, plusieurs modèles de probabilité sont possibles. Le plus adapté est le modèle pour lequel le signal est le plus compressé, c' est-à-dire pour lequel le code résultant de l' encodage a le poids le plus faible.

Pour qu' un codage binaire soit performant, il faut que :

- Les données décodées soient identiques aux données d' entrée ;

- Le poids des données compressées soit le plus faible possible ;

- Le temps d' encodage soit le plus court possible ;

- Le temps de décodage soit le plus court possible.

Ceci dépend de deux facteurs principaux :

- Le codage en lui-même, qui doit, pour une probabilité P donnée coder le symbole sur un nombre de bits le plus proche possible de -log2(P), tout en restituant le même symbole au décodage si on lui fournit le même modèle ;

- Le calcul des modèles, qui doit permettre de fournir le modèle le plus adapté à chacun des symboles, tout en étant le plus rapide possible ;

On peut ainsi utiliser un modèle pour tout le signal. On obtient alors un niveau de compression proche de l' entropie de Shannon. A l' opposé, certains encodeurs utilisent des modèles totalement adaptatifs, comme le procédé PPMd, de l'anglais : "Prédiction by Partial Matching, escape method D". Dans ce cas, les modèles sont établis au fur et à mesure de l'encodage. Ces encodeurs permettent d'obtenir de multiples modèles, adaptés pour chaque symbole, mais les durées de traitement sont beaucoup plus longues.

L'invention a pour but de proposer un procédé d'encodage qui permet d'obtenir un code dont le poids est plus faible que celui généralement obtenu à l'aide d'un modèle unique, et dont les durées de traitement soient plus courtes que celles généralement obtenues avec des modèles multiples.

Dans le cadre de la compression multimédia, on constate qu'après transformation du signal, par exemple par des méthodes dites d'ondelettes, les valeurs faibles sont généralement proches les unes des autres, de même que les valeurs les plus élevées sont plus proches les unes des autres.

Selon l'invention, un tel procédé de codage binaire entropique pour une suite de symboles utilisant au moins deux modèles, chaque modèle étant associé à un critère d'appartenance, comprenant des étapes lors desquelles :

- on parcourt ladite suite pour déterminer; pour chaque symbole, le modèle d'encodage auquel il appartient, en fonction desdits critères d'appartenance ; puis,

- pour chaque modèle et pour chaque symbole on détermine une probabilité d'occurrence du symbole dans le modèle ; puis,

- on parcourt de nouveau ladite suite en encodant chaque symbole successivement en fonction du modèle auquel il appartient ; et, ^'

- on stocke les modèles ou des informations permettant de les reconstituer, et, le code binaire ainsi obtenu.

Avantageusement, on parcourt préalablement la série pour déterminer les critères d'appartenance à chacun des modèles.

De préférence, l'appartenance d'un symbole courant à un modèle est déterminée selon une fonction d'appartenance calculée à partir d'un ou plusieurs symboles précédant ledit symbole courant dans la suite. Chaque symbole pouvant être un nombre, de préférence un nombre en base 10, la fonction d'appartenance peut être la moyenne de valeurs absolues d'un nombre donné de symboles de référence, de préférence quatre symboles de référence, précédant immédiatement ledit symbole courant dans la suite.

Pour le calcul de la fonction d'appartenance on fait avantageusement précéder la liste d'un nombre suffisant de symboles arbitraires, la valeur de chacun étant de préférence nulle.

Le critère d'appartenance à un des modèles peut être une limite inférieure pour un intervalle couvert par le modèle et la comparaison de la moyenne des symboles précédant avec ladite limite. Les limites de chacun des modèles étant rangées dans un ordre croissant, la différence entre deux limites successives augmente avantageusement lorsque la valeur desdites limites augmente. Pour déterminer la limite de chaque modèle on peut :

- calculer la moyenne des valeurs des symboles de la suite ; puis,

- calculer la valeur de la différence entre la valeur maximale et la moyenne d'une part et la moyenne et la valeur minimale d'autre part parmi les valeurs de symboles de la suite, et en déduire une distance égale au maximum parmi ces deux ; puis,

- calculer une déviation égale à la moyenne des valeurs absolues des différences entre chaque élément du signal et la moyenne de la suite ; puis,

- calculer un espacement selon la formule :

puis,

- calculer la limite entre les moyennes mobiles pour chacun des modèles successifs selon la formule suivante : L'invention porte aussi sur un procédé de compression d'un média du type image, vidéo ou son, caractérisé en ce qu'il utilise un procédé d'encodage selon l'invention. Un procédé de compression d'une image s'applique préférentiellement à des symboles compressés de l'image, chacun correspondant à une case d'une matrice, la suite étant formée par la mise en ligne desdits symboles. Pour la mise en ligne des symboles, pour chaque ligne on peut parcourir une ligne dans un premier sens puis la ligne suivante, s'il y a lieu, dans le sens inverse du premier.

Selon un autre objet de l'invention, un procédé de décodage binaire entropique pour une suite de symboles utilisant au moins deux modèles et encodée à l'aide d'un procédé selon l'invention est caractérisé en ce que :

- on extrait chacun des modèles utilisés à l'encodage,

- on extrait ou recalcule les critères d'appartenance à chacun de ces modèles, et,

- on utilise les mêmes critères d'appartenance qu'à l'encodage pour décoder chaque symbole à l'aide du modèle utilisé à l'encodage.

Plusieurs modes d'exécution de l'invention seront décrits ci-après, à titre d'exemples non limitatifs, en référence aux dessins annexés dans lesquels :

- la figure 1 illustre une couche d'une image à laquelle est appliquée un procédé selon l'invention ;

- la figure 2 illustre une sous-matrice, dite LH de 3 ^eme niveau, de coefficients, en base 10, résultant d'une transformation de l'image de la figure 1 par ondelettes, suivie d'une quantification et d'un arrondi ;

- la figure 3 illustre la méthode de mise en ligne des coefficients de la matrice de la figure 2, de façon à former une suite de symboles à traiter par le procédé selon l'invention ; - la figure 4 illustre un tableau donnant pour chaque modèle utilisé la valeur d'une limite inférieure correspondante ;

- la figure 5 est une représentation graphique du tableau de la figure 4 ;

- la figure 6 est un tableau représentant l'ensemble des valeurs en base 10 correspondant aux symboles de la suite et pour chaque valeur son nombre d'occurrences dans la suite, et donc sa probabilité dans le cadre d'un modèle unique ;

- la figure 7 est une représentation graphique du tableau de la figure 6 ; et,

- la figure 8 est un tableau représentant, pour chaque valeur son nombre d'occurrences dans chacun des modèles.

Pour illustrer un exemple de procédé selon l'invention, on utilise une image d'origine dont les pixels sont disposés selon 320 colonnes et 240 lignes et codés avec trois composantes R (rouge), G (vert) et B (bleu). Cette image a ensuite subi une transformation colorimétrique du type Y, Cb, Cr. La figure 1 illustre sous forme d'une image, la composante Y de luminance résultant de cette transformation colorimétrique.

Une transformation par ondelettes CDF 5/3 en deux dimensions utilisant des nombres à virgule fixe est d'abord appliquée à l'image 1. La figure 2 illustre une matrice LHQ correspondant à une sous-matrice dite LH de 3 ^ème niveau résultant de cette transformation par ondelettes à laquelle a ensuite été appliquée une quantification par un coefficient égal à 3,53, puis un arrondi à l'entier le plus proche. Cette transformation par ondelettes est effectuée pour chaque niveau en deux dimensions : une passe verticale, puis une passe horizontale. La transformation par ondelettes verticale génère une matrice dite de détails, ou matrice H, et une matrice dite d'approximation, ou matrice L. L'application d'une passe d'ondelettes horizontale à la matrice L génère une matrice de détails LH et une matrice d'approximation LL. L'application d'une passe d'ondelettes verticale à la matrice H génère deux matrices de détails HL et HH. On applique ensuite récursivement de nouveaux niveaux d'ondelettes aux matrices d'approximation LL successives. Ainsi, la matrice LH de troisième niveau est la matrice de type LH obtenue lors du 3 ^e niveau d'ondelettes. Une fois la matrice LH obtenue, on la. quantifie par un facteur 3,53 puis on arrondit ses valeurs pour obtenir la matrice LHQ.

La matrice LHQ comporte 40 colonnes et 30 lignes, soit 1200 valeurs correspondant chacune à un symbole à encoder. Pour appliquer le traitement selon l'invention, on met les 1200 valeurs en ligne, c'est-à-dire que l'on constitue une suite S des 1200 valeurs. Dans l'exemple illustré, la mise en ligne se fait comme illustré à la figure 3, la première ligne de la matrice LHQ étant parcourue de gauche à droite, puis la deuxième de droite à gauche, de sorte que dans la suite S la dernière valeur de la première ligne de la matrice LHQ précède la dernière valeur de la deuxième ligne. Plus généralement, une ligne étant parcourue dans un sens, la ligne suivante est parcourue dans le sens inverse. On obtient ainsi un signal formé par la suite de N symboles Sn, n entier variant de 1 à N, avec N=1200, chaque symbole Sn ayant une valeur notée V(n).

Dans l'exemple illustré, pour déterminer les modèles à appliquer au signal S, on pratique d'abord une analyse de ce signal.

On calcule d'abord une moyenne arithmétique M de toutes les valeurs du signal, selon la formule :

On détermine ensuite la valeur minimale Min[V(n)] et la valeur maximale Max[V(n)] ; soit, dans l'exemple illustré :

Min[V(n)] = -42

Max[V(n)] =35 On en déduit une distance D, où D est égale à un maximum parmi la valeur de la différence entre la moyenne M et valeur minimale du signal Min[V(n)] d'une part et la valeur de la différence entre la valeur maximale du signal Max[V(n)] et la moyenne M d'autre part; soit, dans l'exemple illustré :

On calcule ensuite une déviation DV, c'est-à-dire une dispersion moyenne, des valeurs autour de la moyenne M. Cette dispersion est calculée comme la moyenne des valeurs absolue des différences entre les valeurs V(n) de chaque symbole Sn du signal et la moyenne M ; soit, dans l'exemple illustré :

On calcule ensuite un espacement E entre les modèles. Dans l'exemple illustré, cet espacement est calculé selon la formule :

Avantageusement, plus le signal à coder est large, plus le nombre de modèles est élevé. Il s'agit d'un paramètre d'entrée pouvant dépendre de la quantité d'information présente dans le signal. Dans l'exemple illustré, on a choisi d'utiliser 5 modèles.

On définit, pour chaque modèle numéroté de 0 à 4, une borne inférieure à partir de laquelle le symbole pourra appartenir à ce modèle. De préférence, plus le modèle concernera des variations faibles, plus les seuils seront proches les uns des autres. On définit ainsi la formule suivante pour calculer, dans le cadre de l'exemple, les limites inférieures de chaque modèle :

Où m est le numéro d'un modèle parmi les 5, m prenant les valeurs entières 0 à 4. Les valeurs inférieures ainsi calculées sont répertoriées au tableau Tabl, représenté à la figure 4 et illustrées sur le graphique de la figure 5.

Afin d'associer chaque symbole Sn à un modèle, il convient de définir un ^" critère d'appartenance qufpmsse être comparé aux limites Γ(ϊη) précédemment calculées. En outre, il faut que ce critère soit identique à l'encodage et au décodage, afin que le même modèle soit appliqué au même symbole, de sorte que la valeur restituée de ce symbole lors du décodage soit la même que sa valeur initiale. Dans ce but, le critère d'appartenance est choisi comme une fonction de valeurs de symboles précédant le symbole courant, c'est-à-dire à encoder ou décoder. L'encodage et le décodage s'effectuant sans perte, les valeurs précédant le symbole courant seront identiques à la compression et la décompression. Ainsi, l'application d'un même critère d'appartenance à ces mêmes valeurs à l'encodage et au décodage affectera le même modèle au symbole courant.

Dans l'exemple illustré, les valeurs après ondelettes sont supposées centrées ou presque centrées sur zéro ; en effet, la moyenne M est sensiblement égale à zéro. De ce fait, la fonction déterminant le critère d'appartenance choisie est une moyenne des valeurs absolues des quatre symboles précédant immédiatement le symbole courant, arrondie à quatre décimales. Le nombre de symboles précédant utilisés peut être différent, mais suffisant pour limiter l'influence d'une valeur trop déviante des autres, qui engendrerait un changement intempestif de modèle, et avantageusement une puissance de 2, pour faciliter sa notation binaire. Le nombre de décimales peut aussi être différent de 4, mais avantageusement une puissance de 2, pour faciliter sa notation binaire.

Le critère d'appartenance à un modèle, dans l'exemple illustré, est donc déterminé par la formule :

Où, la taille de la moyenne mobile T étant égale à 4, c'est-à-dire au nombre de symboles précédant pris en compte pour son calcul, n' variant de 1 à 4.

Ceci permet de sélectionner un modèle adéquat pour chaque symbole Sn. La moyenne mobile mm(n) est calculée avec une précision donnée en paramètre, ici quatre décimales, qui est identique à l'encodage et au décodage.

Chaque symbole Sn de valeur V(n) appartient au plus grand modèle m dont la limite inférieure l(m) est inférieure ou égale à la moyenne mobile des valeurs absolues précédentes mm(n) : l(m) <mm(n).

Le tableau Tab2, illustré à la figure 6, présente le nombre d'occurrences de chaque valeur V(n) dans le signal S. La figure 7 en est la représentation graphique. On remarque que la valeur nulle y est sur-représentée. L'utilisation d'un modèle unique serait donc particulièrement inadaptée.

Le tableau Tab3, illustré à la figure 8, présente le nombre d'occurrences de chaque valeur V(n) dans chaque modèle M.

A l'issue de la sélection d'un modèle m pour chaque symbole Sn, on applique un encodeur du type « range coder » ou arithmétique aux valeurs de ce modèle. Pour cela on calcule d'abord le nombre des occurrences de chaque symbole Sn dans ce modèle m et on en déduit une probabilité d'apparition de ce symbole dans ce modèle m.

Pour l'encodage, on parcourt le signal dans le sens des indices n croissants, tel que défini précédemment en référence à la figure 3. Pour chaque symbole, on détermine le modèle auquel il appartient, selon le critère d'appartenance défini précédemment. On utilise ensuite ce modèle dans l'encodeur choisi, par exemple un encodeur de type « range coder » ou arithmétique. Pour chaque modèle on peut aussi choisir un encodeur d'un type différent de celui choisi pour un autre modèle. -

Les premiers symboles à encoder étant précédés d'un nombre de symboles insuffisant pour calculer le critère d'appartenance, on fait précéder le signal d'un nombre de valeurs arbitraires suffisant pour ce calcul. Ainsi, dans l'exemple illustré, on fait précéder le signal de quatre valeurs, arbitrairement choisies nulles ; ces valeurs permettent le calcul du critère d'appartenance des quatre premiers symboles S1-S4 à encoder.

Avantageusement, on crée un fichier F contenant le code binaire C obtenu par l'encodage du signal S. Pour permettre le décodage du code binaire C, on dispose dans un entête du fichier, l'ensemble des informations nécessaires au décodage, notamment, dans l'exemple illustré :

- le nombre de modèles ;

- la moyenne M ;

- la déviation DV

- le nombre d'éléments précédant à utiliser pour le calcul de la moyenne mobile mm, sous forme de puissance de deux ; et,

- La précision à utiliser pour le calcul de la moyenne mobile, sous forme de puissance de deux.

Pour le décodage, on récupère les limites des modèles, par simple lecture ou recalcul, puis on détermine l'appartenance d'un symbole Sn à décoder à un modèle de la même manière que pour l'encodage, à partir des symboles précédemment décodés sans perte, puis on utilise le modèle trouvé pour décoder le symbole. De la même façon qu'à l'encodage, les premiers symboles à décoder étant précédés d'un nombre de symboles insuffisant pour calculer le critère d'appartenance, on fait précéder le code, correspondant au signal S encodé, d'un nombre de valeurs arbitraires suffisant pour ce calcul. Ces valeurs sont identiques à celles utilisées pour l'encodage. Ainsi, dans l'example illustré, on fait précéder le code de quatre valeurs, arbitrairement choisies nulles ; ces valeurs permettent le calcul du critère d'appartenance des quatre premiers symboles SI -S4 à décoder.

On calcule des valeurs de poids théoriques avec les hypothèses suivantes :

• On néglige le poids des modèles et autres informations d' en-tête nécessaires pour décoder le signal ; et

• Le codeur binaire utilisé est un codeur parfait codant chaque symbole Sn en fonction de sa probabilité P(Sn) sur -log ₂ (P(Sn)) bits, P(Sn) étant sa probabilité selon le modèle fourni.

On utilise pour le calcul théorique les notations suivantes :

• P(Sn) : probabilité des symboles, égale au nombre d'occurrences de ce symbole divisé par le nombre de symboles pour ce modèle ;

• ^' N(Sn) nombre d'occurrences du symbole Sn

Ainsi, chaque symbole rencontré pèsera en. théorie -log ₂ (P(Sn)), l'ensemble des symboles s dans le cadre d'un modèle donné pèsera donc :

- N(Sn) x log ₂ (P(Sn)).

Dans le cas d'espèce les symboles sont compris entre -42 et 35, le poids théorique de l'ensemble des symboles dans le cadre du modèle unique illustré par le tableau Tab2 est : Avec les valeurs ci-dessus, on obtient un poids de P _{modèle unique} = 1941 bits.

Dans le cadre de la séparation en 5 modèles, on utilise la même formule, en calculant la probabilité par rapport au nombre de symboles du modèle courant. On obtient alors :

• Modèle 0 : 300 bits ;

• Modèle 2 : 92 bits ;

• Modèle 3 : 505 bits ;

• Modèle 4 : 588 bits ;

• Modèle 5 : 34 bits :

Le poids total est donc la somme des poids des symboles codés avec chacun de ces modèles, soit :

P _{5 modèles} = 300 + 92 + 505 +588 +34 = 1519 bits.

On a gagné, selon ces hypothèses de calcul, 422 bits par rapport au modèle unique. Le gain prévisible est d'autant plus grand que le nombre de symboles à encoder est plus important. En outre, plus il y de symboles différents dans un signal, plus il peut être avantageux d'augmenter le nombre de modèles utilisés.

Bien sûr, l'invention n'est pas limitée aux exemples qui viennent d'être décrits.