1. Domaine de l'invention

Le domaine de l'invention est celui du codage et du décodage d'information, appliqué notamment à la compression de données.

Plus précisément, l'invention concerne les techniques de codage utilisant des codes à longueur variable.

L'invention peut notamment s'appliquer au codage d'images fixes, ou au codage d'informations d'un flux vidéo, constitué d'une série d'images successives, mis en œuvre dans les codeurs vidéo actuels (MPEG, H.264, etc.) ou à venir (ITU-T/VCEG (H.265) ou ISO/MPEG (HVQ).

2. Art antérieur

On décrit ci-après l'art antérieur relatif à la compression de données dont l'objectif est notamment de transformer une suite de données A en une suite de données B plus courte.

Classiquement, dans cet objectif de compression de données, un code de longueur variable est utilisé pour le codage d'une valeur n-aire. On entend par valeur n-aire une variable qui peut prendre n valeurs entières, avec n e [0,+∞[.

Parmi les codes de longueur variable connus, les codes établis selon l'algorithme de Huffman sont souvent utilisés du fait de leur efficacité en compression. La longueur d'un code selon cet algorithme est déterminée à partir d'une estimation de la probabilité d'observation des données source, un code court étant associé aux données les plus redondantes.

Les codes de type Exp-Golomb proposent une alternative aux codes de Huffman, en particulier lorsque le nombre de valeurs possibles des données à coder n'est pas borné. Le code Exp-Golomb est notamment utilisé dans la norme de compression vidéo H.264 ou MPEG-4 AVC.

Ce code est utilisé afin de coder des valeurs n-aires telles que le type de l'image, les vecteurs mouvement, une information de texture, un niveau de gris, les modes de prédiction inter ou intra. Les codes utilisés sont de longueur variable, et leur construction s'établit suivant une logique définie par une table. Le nombre de ces valeurs à coder n'est pas un nombre fini, et plus la valeur à coder est grande et plus la longueur du mot de code correspondant (c'est-à-dire la chaîne binaire correspondante) est grande. C'est pour cela que l'on attribue un mot de code proche du zéro pour les valeurs à coder fréquentes et un mot de code plus grand pour ceux qui sont plus rares. Chaque type de valeur à coder (information de texture, vecteurs mouvement, etc.) est codé via une table spécifique, qui permet de lui associer le mot de code lui correspondant. Typiquement, ces mots de codes sont définis comme ci-dessous.

Un préfixe est tout d'abord codé avec une suite de N bits à 1 suivi d'un bit 0. Puis, un suffixe est codé sur N bits x (x prenant la valeur 1 ou la valeur 0), le suffixe comprend donc classiquement autant de bits que le nombre de bits à 1 du préfixe.

De tels codes de Huffman ou de type Exp-Golomb sont certes optimaux pour un codage d'un type de donnée présentant une probabilité d'observation connue, mais ils ne permettent pas d'obtenir la meilleure efficacité de compression, notamment en cas de variation de la probabilité d'observation de ces symboles à coder.

Une autre approche particulière de compression dans le contexte de codage d'images utilisant le codage de vecteurs mouvement, pour des blocs d'une image découpée en macroblocs, eux-mêmes subdivisés en blocs, est décrite dans le document « Motion Vector Forecast and Mapping (MV-FMAP) Method for entropy Coding based Video Coder s » (J. Le Tanou, J.M. Thiesse, M. Antoni, Proceedings of Multimedia Signal processing (MMSP) 2010 Oct 2010).

Selon cette approche, une redistribution adaptative des résidus de vecteurs mouvement est mise en œuvre, préalablement au codage entropique, permettant de réduire le coût de codage.

Cette technique propre au codage d'informations de mouvement présente certes une amélioration du coût de codage, mais présente en contrepartie une complexité importante du fait qu'elle nécessite la mise en œuvre des résidus de vecteurs mouvement bidimensionnels. Par ailleurs, tout comme les techniques classiques de codage précédemment citées, cette technique ne permet pas de pallier des mé -performances en cas de variation de la probabilité d'observation des données à coder.

Il existe donc un besoin pour une nouvelle technique de faible complexité permettant de garantir une optimisation du codage en termes de compression même en cas de variation de la probabilité d'observation des données à coder. 3. Exposé de l'invention

L'invention propose une solution nouvelle qui ne présente pas l'ensemble de ces inconvénients de l'art antérieur, sous la forme d'un procédé de codage d'une valeur n-aire.

Selon l'invention un tel procédé comprend :

- une étape de sélection d'un dictionnaire de mots de code, ladite sélection tenant compte d'au moins une valeur n-aire précédemment codée, dite information d'à priori, délivrant un ensemble de mots de code ordonnés selon un critère prédéterminé, une étape d'ordonnancement d'un ensemble de valeurs n-aires possibles, ledit ordonnancement tenant compte de ladite au moins une information d' a priori, délivrant un ensemble ordonné de valeurs n-aires possibles,

une étape d'association à au moins ladite valeur n-aire à coder dudit ensemble ordonné de valeurs n-aires possibles, d'un mot de code dudit ensemble de mots de code ordonnés, selon une règle prédéterminée,

une étape de codage de ladite valeur n-aire par ledit mot de code associé lors de ladite étape d'association.

Ainsi, l'invention repose sur une approche nouvelle et inventive du codage d'une valeur n- aire, permettant d'associer à cette valeur n-aire à coder un mot de code dont la longueur est optimisée quelle que soit la probabilité d'observation des données à coder. La compression de données résultant de la mise en œuvre du procédé de codage selon l'invention est donc améliorée, du fait qu'une adaptation optimale de la longueur des mots de codes est obtenue.

L'association optimisée nécessite au préalable la mise en œuvre des étapes de sélection d'un dictionnaire de mots de code d'une part et d'ordonnancement d'un ensemble de valeurs n- aires possibles d' autre part.

Les étapes préalables de sélection d'un dictionnaire de mots de code et d'ordonnancement sont indépendantes et peuvent donc être mises en œuvre en parallèle ou l'une à la suite de l'autre. En outre, ces deux étapes tiennent compte des valeurs n-aires précédemment codées appelées informations d'à priori, afin de tenir compte de toute variation de la probabilité d'observation des données à coder.

Plus précisément, l'étape de sélection d'un dictionnaire de mots de code vise à tirer profit de l'analyse des informations d'à priori et adapte en fonction la longueur des mots de code qui seront associés ultérieurement aux valeurs n-aire à coder. Les mots de codes du dictionnaire ainsi sélectionné sont ordonnés selon un critère prédéterminé détaillé ci-dessous.

L'étape d'ordonnancement de l'ensemble des valeurs n-aires possibles est également mise en œuvre en tenant compte des informations d'à priori afin de réduire la complexité de l'étape d'association de la valeur n-aire à coder et d'un mot de code du dictionnaire de mots de code sélectionné. En effet, l'étape d'association est effectuée selon une règle prédéterminée basée sur l'ordonnancement des mots de codes et des valeurs n-aires possibles.

Selon un mode de réalisation de l'invention, ladite étape de sélection met en œuvre une étape de construction dudit dictionnaire de mots de code en fonction d'un critère d'optimisation de coût de codage.

Selon un mode de réalisation de l'invention, une étape de construction d'un dictionnaire de mots de code est mise en œuvre lorsque l'observation des informations d'à priori indique que la longueur des mots de code de dictionnaires connus n'est pas optimale.

Ainsi, l'étape de sélection d'un dictionnaire de mots de code vise explicitement à réduire le coût de codage et donc à améliorer la compression des données à coder.

Selon une option particulière de l'invention, ladite étape de sélection et/ou ladite étape d'ordonnancement tient compte d'une loi de probabilité d'apparition pour ledit ensemble de valeurs n-aires possibles, obtenue à partir de ladite au moins une information d'à priori.

Selon cette option une probabilité de l'ensemble des valeurs n-aires possibles est obtenue. Ainsi, toute valeur n-aire à coder différente des informations d'à priori est également prise en compte pour la sélection du dictionnaire de mots de code. Une telle technique permet donc d'affiner la sélection du dictionnaire adapté au contexte de codage.

En outre, lorsque l'étape d'ordonnancement des valeurs n-aires possibles tient également compte de cette loi de probabilité, la complexité du procédé de codage est réduite.

Selon un mode de réalisation de l'invention, ladite information d'à priori correspond à une valeur n-aire précédemment codée enrichie d'un degré de confiance.

Un degré de confiance correspond à une information additionnelle pour chaque information d'à priori, permettant d'indiquer l'importance de l'information d'à priori. Une information d'à priori avec un fort degré de confiance sera privilégiée par rapport à une information d'à priori associée à une valeur de degré de confiance moindre.

Avantageusement, ledit critère prédéterminé utilisé dans l'étape de sélection d'un dictionnaire de mots de code précédemment décrite, correspond à un ordre croissant de longueur de mot de code permettant d'obtenir une réduction du coût de codage

Selon un mode de réalisation particulier, ladite règle prédéterminée vise à associer à la k- ième valeur n-aire dudit ensemble ordonné de valeurs n-aires possibles, le k-ième mot de code dudit ensemble de mots de code ordonnés. Ce mode de réalisation particulier permet avantageusement une réduction de la complexité et du coût car on associe le plus petit mot de code possible à une valeur n-aire à coder.

Selon un mode de réalisation de l'invention, lorsque ladite valeur n-aire est une valeur multidimensionnelle, lesdites étapes dudit procédé sont mises en œuvre pour chaque composante de ladite valeur multidimensionnelle, permettant ainsi de réduire la complexité de codage de la valeur multidimensionnelle.

Selon une variante de ce mode de réalisation, ladite information d' a priori utilisée pour le codage d'une deuxième composante de ladite valeur multidimensionnelle dépend du codage d'une première composante de ladite valeur multidimensionnelle, permettant ainsi d'améliorer le codage de la deuxième composante.

L'invention concerne également un dispositif de codage d'une valeur n-aire.

Selon l'invention, un tel dispositif comprend :

des moyens de sélection d'un dictionnaire de mots de code, lesdits moyens de sélection tenant compte d'au moins une valeur n-aire précédemment codée, dite information d'à priori, délivrant un ensemble de mots de code ordonnés selon un critère prédéterminé, des moyens d'ordonnancement d'un ensemble de valeurs n-aires possibles, lesdits moyens d'ordonnancement tenant compte de ladite au moins une information d'à priori, délivrant un ensemble ordonné de valeurs n-aires possibles,

des moyens d'association à au moins ladite valeur n-aire à coder dudit ensemble ordonné de valeurs n-aires possibles, d'un mot de code dudit ensemble de mots de code ordonnés, selon une règle prédéterminée,

des moyens de codage de ladite valeur n-aire par ledit mot de code associé lors de ladite étape d'association.

Un tel dispositif de codage est notamment adapté à mettre en œuvre les étapes du procédé de codage décrit précédemment. Ce dispositif pourra bien sûr comporter les différentes caractéristiques relatives au procédé de codage selon l'invention. Ainsi, les caractéristiques et avantages de ce dispositif de codage sont les mêmes que ceux du procédé de codage, et ne sont pas détaillés plus amplement.

Un autre aspect de l'invention concerne un procédé de décodage d'un mot de code représentatif d'une valeur n-aire.

Selon l'invention, un tel procédé comprend les étapes suivantes :

une étape de sélection d'un dictionnaire de mots de code, ladite sélection tenant compte d'au moins une valeur n-aire précédemment décodée, dite information d'à priori, délivrant un ensemble de mots de code ordonnés selon un critère prédéterminé, une étape d'ordonnancement d'un ensemble de valeurs n-aires possibles, ledit ordonnancement tenant compte de ladite au moins une information d' a priori, délivrant un ensemble ordonné de valeurs n-aires possibles,

- une étape de décodage dudit mot de code, délivrant un mot de code lu,

une étape d'association dudit mot de code lu à au moins une valeur n-aire dudit ensemble ordonné de valeurs n-aires possibles, selon une règle prédéterminée.

L'invention concerne également un dispositif de décodage d'un mot de code représentatif d'une valeur n-aire, comprenant :

- des moyens de sélection d'un dictionnaire de mots de code, ladite sélection tenant compte d'au moins une valeur n-aire précédemment décodée, dite information d'à priori, délivrant un ensemble de mots de code ordonnés selon un critère prédéterminé, des moyens d'ordonnancement d'un ensemble de valeurs n-aires possibles, ledit ordonnancement tenant compte de ladite au moins une information d' a priori, délivrant un ensemble ordonné de valeurs n-aires possibles,

des moyens de décodage dudit mot de code, délivrant un mot de code lu, des moyens d'association dudit mot de code lu à au moins une valeur n-aire dudit ensemble ordonné de valeurs n-aires possibles, selon une règle prédéterminée.

Enfin l'invention concerne un programme d'ordinateur comportant des instructions pour la mise en œuvre d'un procédé de codage ou de décodage tels que décrits précédemment, lorsque ce programme est exécuté par un processeur.

4. Liste des figures

D'autres caractéristiques et avantages de l'invention apparaîtront plus clairement à la lecture de la description suivante d'un mode de réalisation particulier, donné à titre de simple exemple illustratif et non limitatif, et des dessins annexés, parmi lesquels :

les figures la et lb illustrent respectivement les principales étapes du procédé de codage d'une valeur n-aire, et du procédé de décodage, selon un mode de réalisation de l'invention ;

les figures 2a à 2d illustrent l'amélioration des performances de codage par le procédé selon un mode de réalisation de l'invention ;

la figure 3 illustre une application du procédé de codage à une valeur bi-dimensionnelle ; les figures 4 et 5 illustrent respectivement un exemple de structure simplifiée d'un dispositif de codage et de décodage, selon un mode de réalisation de l'invention. 5. Description d'un mode de réalisation de l'invention

5.1 Principe général

Le principe général de l'invention repose sur le choix, pour coder une valeur n-aire, d'un mot de code dont la longueur est optimisée en fonction d'informations connues relatives à cette valeur, par exemple en fonction de l'observation de valeurs n-aires précédemment codées, appelées informations d'à priori.

Ainsi, l'invention se base sur l'observation des informations d'à priori et, le cas échéant, sur la détermination d'une loi de probabilités obtenue à partir de ces informations d'à priori. Cette détermination de loi de probabilité permet ensuite la sélection optimisée d'un dictionnaire de mots de code qui peut être différent des dictionnaires classiquement utilisés. Selon un mode de réalisation de l'invention, un tel dictionnaire est construit, en fonction d'un critère d'optimisation de coût de codage.

Une fois ce dictionnaire de mots de code sélectionné, ou construit, une association entre un ensemble de valeurs n-aires possibles préalablement ordonné, et l'ensemble ordonné des mots de code du dictionnaire sélectionné est mise en œuvre.

Cette étape permet d'associer la valeur n-aire à coder à un mot de code dont la longueur de code est adaptée en fonction de la probabilité d'apparition de cette valeur n-aire.

Ainsi, l'invention permet d'obtenir une amélioration globale de la compression et du coût de codage d'une valeur n-aire en sélectionnant un dictionnaire de mots de code adapté en fonction d'une loi de probabilité d'observation de valeurs n-aires possibles, c'est-à-dire de valeurs que peut prendre la valeur n-aire à coder.

On entend par valeur n-aire à coder par exemple une composante d'un vecteur mouvement, une information de texture, un niveau de gris, un mode de prédiction inter ou intra, un niveau de gris relatif à une information de profondeur, une information d'amplitude d'un coefficient de transformée du signal...

5.2 Description d'un mode de réalisation

5.2.1 Procédé de codage

On présente maintenant, en relation avec les figures la et 2a à 2d, les principales étapes du procédé de codage selon un mode de réalisation de l'invention.

On considère dans ce mode de réalisation qu'une valeur n-aire précédemment codée est appelée information d'à priori. Une illustration sous forme graphique d'un exemple d'ensemble d'information d'à priori 100 est représentée sur la figure 2a.

Selon un aspect particulier de l'invention, une information d'à priori est enrichie par un degré de confiance. Un tel degré de confiance correspond à une information additionnelle pour chaque information d'à priori, permettant d'établir une probabilité que ladite information d'à priori soit sélectionnée ou utilisée par différents modules d'un codeur vidéo. On établit en quelque sorte un « pronostic » pour une sélection ultérieure, lors du codage, d'une information d'à priori. Cette information additionnelle représentative d'un degré de confiance permet à terme une utilisation optimisée de chaque module du codeur. En effet, plus la valeur du degré de confiance sera grande, et plus le codeur sera informé de l'importance de l'information à coder considérée. Une information d'à priori avec un fort degré de confiance sera privilégiée par rapport à une information d'à priori associée à une valeur de degré de confiance moindre, c'est-à-dire ayant été pronostiquée comme rare.

Par exemple, en relation avec la figure 2a, on considère que la valeur n-aire à coder correspond au niveau de gris d'un bloc d'une image et que les informations d'à priori correspondent par exemple au niveau de gris des blocs voisins à gauche (21), en haut (22) et à droite (23) précédemment codés. Ces informations d'à priori sont représentées en abscisse (l'ordonnée de la figure 2a correspondant à la redondance de chacune de ces informations d'à priori).

Selon une option de ce mode de réalisation, une loi de probabilité 24 est obtenue (101) à partir d'au moins une information d'à priori de l'ensemble des informations d'à priori 100.

En relation avec la figure 2a, la loi de probabilité 24 obtenue permet d'obtenir la probabilité de l'ensemble des valeurs n-aires possibles comprenant notamment les probabilités des informations d'à priori 21, 22 et 23.

Pour obtenir cette loi de probabilité 24, on utilise par exemple une technique statistique appelée estimation par noyau (ou encore méthode de Parzen-Rozenblatt). Cette méthode est une méthode non-paramétrique d'estimation de la densité de probabilité d'une variable aléatoire.

Selon cette technique, on considère un ensemble d'observations Xj avec pour chacune une probabilité d'à priori pj. On définit alors la probabilité d'observation d'une valeur x comme étant :

p x) oc ^ P _i F(x— x _i ) où F est un noyau de filtrage. i

Par exemple, F peut être un noyau de filtrage gaussien ( (JC) = , e -4 ^7x7 - ), laplacien l _H

( (JC) =— e ^b ), ou tout autre filtre à valeurs positives. La probabilité est définie ici de façon 2b

proportionnelle, afin de prendre en compte la normalisation au besoin (i.e. que la somme des probabilités pour chaque valeur vaille 1). Comme illustré en figure la, le procédé de codage 11 selon ce mode de réalisation comprend principalement quatre étapes 111, 112, 113 et 114.

Lors d'une première étape 111 de sélection d'un dictionnaire de mots de code en fonction d'au moins une information d'à priori, on détermine le dictionnaire de mots de code le plus adapté pour le codage de l'ensemble des valeurs n-aires possibles.

Cette première étape 111 tient compte, de manière optionnelle (101), de la loi de probabilité 24 décrite précédemment. La loi de probabilité est triée selon un ordre décroissant de la probabilité des valeurs n-aires possibles, tel qu'illustré en figure 2b.

Par ailleurs, selon cette loi de probabilité et l'application des enseignements connus de la théorie de l'information, il est possible de déterminer le « gabarit théorique » de la longueur de code optimale en fonction des informations d'à priori. La figure 2c représente notamment un tel gabarit obtenu selon l'équation : longueur =—\og2p(x) .

L'étape de sélection 111 permet donc de sélectionner, ou de construire, un dictionnaire de mots de code, c'est-à-dire un ensemble de mots de code ordonnés, présentant des performances les plus proches possibles de ce cas théorique.

Par exemple, la figure 2d représente une courbe illustrant la longueur des mots de code de type Exp-Golomb (précédemment décrit en relation avec l'art antérieur). La comparaison des courbes des figures 2d et 2c révèle les mauvaises performances du code de type Exp-Golomb, et donc la nécessité de sélectionner un autre dictionnaire de mots de code.

Selon un aspect particulier de ce mode de réalisation de l'invention, l'étape de sélection

111 met en œuvre la construction 1110 du dictionnaire de mots de code optimal à sélectionner, prenant en compte des informations d'à priori et délivrant un dictionnaire de mots de code adapté à la probabilité d'observation des données à coder.

Pour ce faire, l'invention propose une technique de construction d'un dictionnaire de mot de codes de type préfixe-suffixe en faisant varier la longueur du suffixe de sorte à converger vers le gabarit théorique de la figure 2c. Ainsi, au contraire de art antérieur relatif aux mots de code de type Exp-Golomb précédemment décrit, le nombre de bits utilisés pour le suffixe peut être différent du nombre de bits à 1 utilisés dans le préfixe. Un exemple d'un tel code est présenté ci-dessous :

Il est à noter que dans cet exemple, la longueur du suffixe pour un préfixe ayant 3 bits à 1 est plus petite.

Par ailleurs, on remarque que le dictionnaire de mots de code de type Ex-Golomb utilisé par AVC délivre une série linéaire de longueur de suffixe égale à 0, 1, 2, 3, 4, ... bits respectivement pour chacun des ensembles de valeurs (0), (1, 2), (3, 4, 5, 6) , (7, 8, 9, 10, 11, 12, 13, 14) et (15, 16, 17, 18, 29, 30), tandis que le dictionnaire construit selon ce mode de réalisation de l'invention délivre la série non linéaire optimisée de longueur de suffixe égale à 0, 1, 2, 2, 3, 4, ... bits. Ainsi, le suffixe de longueur 2 apparaît deux fois pour les ensembles de valeurs (3, 4, 5, 6) et (7, 8, 9, 10).

Ainsi, l'invention permet de définir un dictionnaire de mots de code ayant des spectres de longueur de mot de code variable adaptée à la probabilité d'observation des valeurs n-aires possibles.

Le programme présenté en Annexe 1 permet de construire, selon un mode de réalisation de l'invention, le dictionnaire de mots de code le plus adapté.

Selon une option alternative de ce mode de réalisation, une sélection (111) basée sur une mesure de l'étalement (ou inter-distance) des informations d' a priori est mise en œuvre et comprend les étapes suivantes :

- un ensemble d'informations d'à priori Xj est considéré,

- on calcule l'inter-distance moyenne: ID =

- si l'inter-distance ID est supérieure à un seuil (par exemple, on peut prendre une valeur de seuil égale à 4), on utilise alors le nouveau dictionnaire construit selon l'exemple donné ci-dessus, sinon, on utilise le dictionnaire des codes Exp-Golomb utilisé par AVC. En parallèle, ou une fois cette première étape de sélection 111 de dictionnaire de mot de code effectuée, une étape 112 d'ordonnancement d'un ensemble de valeurs n-aires possibles est mise en œuvre.

Selon une première variante, l'ordonnancement des valeurs n-aires possibles, tel que représenté (25) sur la figure 2b, est effectué suivant leur probabilité d'apparition déduite de la loi de probabilité 24 représentée sur la figure 2a.

Le principe d'un tel ordonnancement de valeurs n-aires possibles, basé sur leur probabilité d'apparition, est notamment appliqué au cas particulier du codage de valeurs n-aires correspondant à des vecteurs mouvement, pour des blocs d'une image découpée en macroblocs, eux-mêmes subdivisés en blocs, et est décrit dans le document « Motion Vector Forecast and Mapping (MV- FMAP) Methodfor entropy Coding based Video Coder s » (J. Le Tanou, J.M. Thiesse, M. Antoni, Proceedings of Multimedia Signal processing (MMSP) 2010 Oct 2010).

Selon une autre variante, les valeurs n-aires possibles à coder sont réordonnées empiriquement, sans définir pour chacune d'elle une valeur de probabilité d'observation. L'approche suivante est par exemple utilisée:

- initialisation d'une pile d'attente ordonnée selon un degré de confiance contenant les valeurs n-aire précédemment codées,

- extraction du premier élément de la pile, ayant le degré de confiance le plus fort, pour le placer en première position dans l'ordonnancement de valeur n-aires possibles,

- ajout dans l'ordonnancement de valeur n-aires possibles des valeurs voisines (+1 et -1 relativement à la valeur courante) si elles ne figurent pas dans la pile d'attente ordonnée des valeurs n-aires précédemment codées,

- itération des étapes d'extraction et d'ajout tant que l'ensemble des valeurs n-aires possibles n'a pas été intégré dans l'ordonnancement

Une fois ces deux étapes indépendantes de sélection 111 et d'ordonnancement 112 effectuées l'une après l'autre ou en parallèle, une étape d'association 113 est mise en œuvre.

Cette étape d'association associe à au moins une valeur n-aire de l'ensemble ordonné de valeurs n-aires possibles, correspondant à la valeur n-aire à coder, un mot de code de l'ensemble de mots de code ordonnés, selon une règle prédéterminée.

Selon un aspect particulier de l'invention, cette règle prédéterminée vise par exemple à associer à la k-ième valeur n-aire de l'ensemble ordonné de valeurs n-aires possibles, le k-ième mot de code de l'ensemble de mots de code ordonnés.

On pourrait également envisager une autre règle, notamment dans un contexte de brouillage utilisant une clé de brouillage prédéterminée.

Une fois cette association effectuée, une étape de codage 114 de la valeur n-aire par le mot de code associé lors de l'étape d'association 113 est mise en oeuvre.

5.2.2 Procédé de décodage

On présente maintenant, en relation avec les figures lb et 2a à 2d, les principales étapes du procédé de décodage selon un mode de réalisation de l'invention.

On considère dans ce mode de réalisation une information reçue par le décodeur correspondant par exemple à un train binaire Τβ à décoder, le train binaire Τβ ayant été préalablement codé selon le procédé de codage décrit précédemment, et un ensemble 120 d'informations d'à priori correspondant à des valeurs n-aires précédemment décodées dont les probabilités d'informations d'à priori 21, 22, 23, sont par exemple représentées sur la figure 2a précédemment décrite (les mêmes références numériques étant utilisées pour les probabilités des informations d'à priori des valeurs n-aires possibles utilisées au codage et pour les probabilités des informations d'à priori des valeurs n-aires précédemment décodées utilisées au décodage).

De manière similaire au codage, selon un aspect particulier de l'invention au décodage, une information d'à priori peut être enrichie par un degré de confiance. Un tel degré de confiance correspond à une information additionnelle pour chaque information d'à priori, permettant d'établir une probabilité que ladite information d'à priori soit sélectionnée ou utilisée par différents modules d'un décodeur vidéo. On établit en quelque sorte un « pronostic » pour une sélection ultérieure, lors du décodage, d'une information d'à priori. Cette information additionnelle représentative d'un degré de confiance permet à terme une utilisation optimisée de chaque module du décodeur. En effet, plus la valeur du degré de confiance sera grande, et plus le décodeur sera informé de l'importance de l'information d'à priori à considérer. Une information d'à priori avec un fort degré de confiance sera privilégiée par rapport à une information d'à priori associée à une valeur de degré de confiance moindre, c'est-à-dire ayant été pronostiquée comme rare.

Selon une option de ce mode de réalisation, une loi de probabilité est obtenue (121) à partir d'au moins une information d'à priori de l'ensemble des informations d'à priori 120. Une telle loi de probabilité est par exemple obtenue au décodage, de manière similaire au codage décrit précédemment, par exemple selon une technique statistique appelée estimation par noyau (ou encore méthode de Parzen-Rozenblatt).

Comme illustré en figure lb, le procédé de décodage 12 selon ce mode de réalisation comprend principalement quatre étapes 1021, 1022, 1023 et 1024.

Les étapes de sélection d'un dictionnaire de mots de code 1021, d'ordonnancement d'un ensemble d'information d'à priori 1022 et d'association 1024 associant à au moins un mot de code lu dans l'ensemble de mots de code ordonnés du dictionnaire sélectionné, une valeur n-aire de l'ensemble ordonné d'information d'à priori, selon une règle prédéterminée, sont mises en oeuvre de manière similaire au décodage et au codage (précédemment décrit).

Lors d'une première étape 1021 de sélection d'un dictionnaire de mots de code en fonction d'au moins une information d'à priori, on détermine le dictionnaire de mots de code le plus adapté pour le décodage de l'information transmise.

Cette première étape 1021 tient compte, de manière optionnelle (121), de la loi de probabilité décrite précédemment. La loi de probabilité est triée selon un ordre décroissant de la probabilité des information d'à priori, tel qu'illustré en figure 2b.

Par ailleurs, selon cette loi de probabilité et l'application des enseignements connus de la théorie de l'information, il est possible de déterminer le « gabarit théorique » de la longueur de code optimale en fonction des informations d'à priori. Comme décrit précédemment en relation avec le codage, la figure 2c s'applique également au décodage et représente notamment un tel gabarit obtenu selon l'équation : longueur =—\og2p(x) .

L'étape de sélection 1021 permet donc de sélectionner, ou de construire, un dictionnaire de mots de code présentant des performances les plus proches possibles de ce cas théorique.

Par exemple, la figure 2d représente une courbe illustrant la longueur des mots de code de type Exp-Golomb (précédemment décrit en relation avec l'art antérieur). La comparaison des courbes des figures 2d et 2c révèle les mauvaises performances du code de type Exp-Golomb, et donc la nécessité de sélectionner un autre dictionnaire de mots code.

Selon un aspect particulier de ce mode de réalisation de l'invention, l'étape de sélection 1021 met en œuvre la construction 1020 du dictionnaire de mots de code optimal à sélectionner, prenant en compte des informations d'à priori et délivrant un dictionnaire de mots de code adapté à la probabilité d'observation des informations d'à priori correspondant aux valeurs n-aires possibles précédemment décodées.

Pour ce faire, l'invention propose une technique de construction d'un dictionnaire de mots de code de type préfixe-suffixe en faisant varier la longueur du suffixe de sorte à converger vers le gabarit théorique de la figure 2c. Ainsi, de même qu'au codage, le nombre de bits utilisés au décodage pour le suffixe peut être différent du nombre de bits à 1 utilisés dans le préfixe.

Ainsi, l'invention permet de définir un dictionnaire de mots de code ayant des spectres de longueur de mot de code variable adaptée à la probabilité d'observation des valeurs n-aires possibles précédemment décodées. De manière similaire au codage, le programme présenté en Annexe 1 permet de construire, selon un mode de réalisation de l'invention, le dictionnaire de mots de code le plus adapté.

Selon une option alternative de ce mode de réalisation, une sélection (1021) basée sur une mesure de l'étalement (ou inter-distance) des informations d' a priori est mise en œuvre au décodage de manière similaire au codage.

En parallèle, ou une fois cette première étape de sélection 1021 de dictionnaire de mots de code effectuée, une étape 1022 d'ordonnancement d'un ensemble de valeurs n-aires possibles précédemment décodées est mise en œuvre.

De même qu'au codage, selon une première variante du procédé de décodage, l'ordonnancement des valeurs n-aires possibles, tel que représenté (25) sur la figure 2b, est effectué suivant leur probabilité d'apparition déduite de la loi de probabilité 24 représentée sur la figure 2a.

Le principe d'un tel ordonnancement de valeurs n-aires possibles, basé sur leur probabilité d'apparition, est notamment appliqué au cas particulier du décodage de mots de code représentatifs de vecteurs mouvement, pour des blocs d'une image découpée en macroblocs, eux-mêmes subdivisés en blocs, et est décrit dans le document « Motion Vector Forecast and Mapping (MV- FMAP) Methodfor entropy Coding based Video Coder s » (J. Le Tanou, J.M. Thiesse, M. Antoni, Proceedings of Multimedia Signal processing (MMSP) 2010 Oct 2010).

Selon une autre variante, similaire à celle précédemment décrite pour le codage, les valeurs n-aires possibles précédemment décodées sont réordonnées empiriquement, sans définir pour chacune d'elle une valeur de probabilité d'observation.

Une fois ces deux étapes indépendantes de sélection 1021 et d'ordonnancement 1022 effectuées l'une après l'autre ou en parallèle, une étape de décodage 1023 à partir du train binaire Τβ de l'information reçue, à savoir le mot de code, est mise en œuvre.

Cette étape de décodage 1023 décode le train binaire Τβ par lecture dans le dictionnaire sélectionné d'un mot de code décodé, appelé mot de code lu. En effet, la sélection du dictionnaire établit le type de préfixe-suffixe utilisé lors du codage, et délivre un mot de code lu correspondant.

Une fois l'étape de décodage effectuée, une étape d'association 1024 est mise en œuvre.

Cette étape d'association associe au mot de code lu obtenu précédemment, au moins une valeur n-aire de l'ensemble ordonné de valeurs n-aires possibles issu de l'étape d'ordonnancement 1022, selon une règle prédéterminée. Cette valeur n-aire associée correspond à la valeur n-aire à décoder.

Selon un aspect particulier de l'invention, cette règle prédéterminée vise par exemple à associer au mot de code lu qui correspond au k-ième mot de code de l'ensemble de mots de code ordonnés du dictionnaire de mots de codes sélectionné, la k-ième valeur n-aire de l'ensemble ordonné de valeurs n-aires possibles.

On pourrait également envisager une autre règle, notamment dans un contexte de brouillage utilisant une clé de brouillage prédéterminée.

5.3 Description d'une variante du mode de réalisation appliquée au codage d'une valeur n-aire multidimensionnelle

La figure 3 illustre une variante du mode de réalisation décrit ci-dessus dans laquelle on considère que la valeur n-aire est une donnée multidimensionnelle.

En particulier, la figure 3 est appliquée au codage d'une valeur n-aire correspondant à vecteur mouvement à deux dimensions. Le principe de codage présenté ici se généralise aisément à plus de composantes.

L'invention propose d'effectuer un codage de vecteur mouvement composante par composante. Plus précisément, les quatre étapes du procédé de codage précédemment décrites, sont mises en œuvre pour chaque composante du vecteur mouvement à coder 31 1.

L'ensemble des informations d'à priori utilisé par le procédé de codage est tout d'abord établit (312) pour une première composante. Par exemple, une information d'à priori est une valeur n-aire correspondant à un vecteur mouvement précédemment codé, d'un bloc voisin ou encore d'un bloc co-localisé d'une image précédemment codée.

Selon une option de ce mode de réalisation, une loi de probabilité est obtenue à partir d' au moins une information d' a priori.

Pour ce faire, la technique statistique appelée estimation par noyau (ou encore méthode de

Parzen-Rozenblatt) est généralisable à une valeur n-aire multidimensionnelle. On définit par exemple la probabilité d'observation d'une valeur n-aire correspondant à un vecteur mouvement bidimensionnel (x, y) comme étant: p(x, y ) oc ^ p.F. [x— x. , y— y. ) . Le noyau estimateur, appelé fenêtre de Parzen, est alors ici bidimensionnel. Typiquement, on peut utiliser une fenêtre de Parzen séparable tel que F(x,y) = F(x).F(y).

Il est aussi possible de définir des probabilités d'observation pour chaque composante du vecteur. Ainsi, pour la première composante à coder (on considère sans généralisation qu'il s'agit de la composante "x"), on peut définir la probabilité d'observation comme suit : p(x) oc ^ p.F. — χ. ) , où F est un noyau de filtrage, et pi des probabilités d'à priori sur les différentes observations Xj. Typiquement on peut prendre pj =1/B où B est le nombre d'à priori. Les quatre étapes de sélection d'un dictionnaire de mots de code, d'ordonnancement, d'association et de codage sont par la suite mises en œuvre (313) pour la première composante.

Comme décrit précédemment, ces quatre étapes tiennent bien compte de l'ensemble d'informations d'à priori précédemment établi (312).

Puis, l'ensemble des informations d'à priori utilisé par le procédé de codage est établi (314) pour la deuxième composante, appelée ici « y ». Selon une option de ce mode de réalisation, une loi de probabilité est également obtenue à partir d'au moins une information d'à priori. La technique statistique appelée estimation par noyau est par exemple utilisée selon les deux approches suivantes:

p{y) ^ Y _j p F _i {y - y _i )

i

b) - p(y /x)< ^x _J p' _i F(y - y _i )F(x - x _i ) où les p'j représentent des probabilités d'à priori (par défaut identique aux pj, mais pouvant prendre également des valeurs différentes du fait que l'observation de la première composante diffère de celle de la deuxième composante). La première approche (a) permet de réaliser un codage indépendant des composantes du vecteur à coder, au détriment de l'efficacité de compression. La seconde formulation (b) permet de prendre en compte la probabilité conjointe d'observation des deux composantes.

Ainsi, selon cette deuxième approche (b), le codage 315 (comprenant les quatre étapes de sélection d'un dictionnaire de mots de code, d'ordonnancement, d'association et de codage) d'une deuxième composante du vecteur mouvement bidimensionnel dépend du codage d'une première composante du vecteur mouvement bidimensionnel.

Ainsi, en comparaison avec la technique de l'art antérieur présentée dans le document « Motion Vector Forecast and Mapping (MV-FMAP) Method for entropy Coding based Video Coders » (J. Le Tanou, J.M. Thiesse, M. Antoni, Proceedings of Multimedia Signal processing (MMSP) 2010 Oct 2010), le codage selon l'invention permet une réduction de complexité.

En effet, si on considère P le nombre de valeurs n-aires possibles que peut prendre chaque composante, le procédé de codage selon l'invention permet de réduire le nombre d'opérations de PxPxlog(P) (selon le document de l'art antérieur précédemment cité) à 2xPxlog(P). Les P opérations selon le procédé de l'invention étant effectuées en parallèle selon l'approche (a) précédemment décrite ou à la suite l'une de l'autre selon l'approche (b).

5.4 Structure d'un dispositif de codage et de décodage

La figure 4 illustre un exemple de structure simplifiée d'un dispositif de codage selon un mode de réalisation de l'invention.

Par exemple, le dispositif de codage comprend une mémoire 40 constituée d'une mémoire tampon, une unité de traitement 41, équipée par exemple d'un microprocesseur μΡ, et pilotée par le programme d'ordinateur 42, mettant en œuvre le procédé de codage selon l'invention.

A l'initialisation, les instructions de code du programme d'ordinateur 42 sont par exemple chargées dans une mémoire RAM avant d'être exécutées par le processeur de l'unité de traitement 41. L'unité de traitement 41 reçoit en entrée au moins une valeur n-aire à coder. Le microprocesseur de l'unité de traitement 41 met en œuvre les étapes du procédé de codage décrit précédemment, selon les instructions du programme d'ordinateur 42, pour délivrer au moins un mot de code pour le codage de la valeur n-aire. Pour cela, le dispositif de codage comprend, outre la mémoire tampon 40 :

des moyens de sélection d'un dictionnaire de mots de code, lesdits moyens de sélection tenant compte d'au moins une valeur n-aire précédemment codée, dite information d'à priori, délivrant un ensemble de mots de code ordonnés selon un critère prédéterminé, - des moyens d'ordonnancement d'un ensemble de valeurs n-aires possibles, lesdits moyens d'ordonnancement tenant compte de ladite au moins une information d'à priori, délivrant un ensemble ordonné de valeurs n-aires possibles,

des moyens d'association à chaque valeur n-aire dudit ensemble ordonné de valeurs n-aires possibles, d'un mot de code dudit ensemble de mots de code ordonnés, selon une règle prédéterminée,

des moyens de codage de ladite valeur n-aire par ledit mot de code associé lors de ladite étape d'association.

Ces moyens sont pilotés par le microprocesseur de l'unité de traitement 41.

La figure 5 illustre un exemple de structure simplifiée d'un dispositif de décodage selon un mode de réalisation de l'invention.

Par exemple, le dispositif de décodage comprend une mémoire 50 constituée d'une mémoire tampon, une unité de traitement 51, équipée par exemple d'un microprocesseur μΡ, et pilotée par le programme d'ordinateur 52, mettant en œuvre le procédé de décodage selon l'invention.

A l'initialisation, les instructions de code du programme d'ordinateur 52 sont par exemple chargées dans une mémoire RAM avant d'être exécutées par le processeur de l'unité de traitement 51. L'unité de traitement 51 reçoit en entrée au moins un mot de code à décoder, le mot de code est extrait d'un flux de données codées. Le microprocesseur de l'unité de traitement 51 met en œuvre les étapes du procédé de décodage décrit précédemment, selon les instructions du programme d'ordinateur 52, pour délivrer au moins une valeur n-aire pour le décodage d'un mot de code. Pour cela, le dispositif de décodage comprend, outre la mémoire tampon 50 :

des moyens de sélection d'un dictionnaire de mots de code, lesdits moyens de sélection tenant compte d'au moins une valeur n-aire précédemment décodée, dite information d'à priori, délivrant un ensemble de mots de code ordonnés selon un critère prédéterminé, des moyens d'ordonnancement d'un ensemble de valeurs n-aires possibles, lesdits moyens d'ordonnancement tenant compte de ladite au moins une information d'à priori, délivrant un ensemble ordonné de valeurs n-aires possibles,

des moyens de décodage dudit mot de code, délivrant un mot de code lu,

des moyens d' association dudit mot de code lu à au moins une valeur n-aire dudit ensemble ordonné de valeurs n-aires possibles, selon une règle prédéterminée.

Ces moyens sont pilotés par le microprocesseur de l'unité de traitement 51.

ANNEXE 1

Exemple de programme permettant de sélectionner un dictionnaire de mots de code selon l'invention:

Dans ce programme, en entrée, on considère que les données sont triées selon leur probabilité décroissante. Plus précisément, il y a « nbSamples » données et le paramètre proba(i) définit la probabilité d'apparition de la valeur n-aire considérée. for(int i=0; i<nbSamples; i++)

{

aTotCost [i] = 0; // used for storing totCost at Pos

aLastLenSuff [i] = 0; // used for storing lastLenSuff at Pos

aSumProba [i] = 0; // used for storing sumProba

aCriterion [i] = 0; // used for storing CriterionCost

aPrefLen [i] = 0; // used for storing prefix len at pos

aPosFrom [i] = 0; // used for storing incoming last pos

} //— store sumProba

aSumProba[0] = proba(O);

for(int i=l ; i<nbSamples; i++)

aSumProba[i] = aSumProba[i-l] + proba(i);

//— dynamic programmation to optimize

int posFrom=-l, suffLenFrom=0; //

double totCostFrom = 0, sumProbaFrom=0;

int prefLen = 1 ; // initialising prefix len

while (posFrom<nbSamples-l)

{

//- testing various suffLen

for(int suffLen=suffLenFrom; suffLen<suffLenFrom+2; suffLen++)

{ //— consider using for interval JposFrom; posTo], a prefix of len prefLen, and suffix of len suffLen

int cwCost = prefLen + suffLen;

int nbCW = (l«suffLen);

int posTo = posFrom + nbCW;

if (posTo>=nbSamples)

posTo = nbSamples-1 ;

double sumProbaFromTo = aSumProba[posTo]-sumProbaFrom; //— probability for interval double totCost = totCostFrom + sumProbaFromTo*cwCost; //— estimated coding cost for symbols up to posTo

double criterion = totCost + (l-aSumProba[posTo]) * prefLen; //— estimated criterion with considered parameter

if ( (aTotCost[posTo]==0) Il (aCriterion[posTo]>criterion) )

{ //— estimated that this setting is better than previously observed at position posTo

aTotCost[posTo]= totCost;

aLastLenSuff[posTo] = suffLen;

aCriterion[posTo] = criterion;

aPrefLen[posTo] = prefLen;

aPosFrom[posTo] = posFrom;

}

}

// searching for next available posFrom

do

{

posFrom++;

} while (aTotCost[posFrom]==0);

totCostFrom = aTotCost[posFrom] ;

suffLenFrom = (int) aLastLenSuff [posFrom] ;

sumProbaFrom = aSumProba[posFrom] ;

prefLen = aPrefLen[posFrom] + 1 ;

}

//— set the len for each codeword for(int i=nbSamples-l ; i>=0; i=aPosFrom[i])

{

for(int j=i; j>aPosFrom[i]; j— )

lenCW[j] = aPrefLen[i]+(int)aLastLenSuff[i]; //— use a prefix len of "aPrefLen[i]", and suffix len of "aLastLenSuff[i]"

En sortie, on obtient donc pour chaque valeur n-aire possible à coder (nbSamples étant le nombre de valeurs possibles), la longueur du préfixe et celle du suffixe utilisées pour le mot de code.