Brevet FR3054764A1 — publié le 20180202

Procédé de décodage d'une image, procédé de codage, dispositifs, équipement terminal et programmes d'ordinateurs associés 1. Domaine de l'invention Le domaine de l'invention est celui du codage et du décodage d'images ou de séquences d'images, et notamment de flux vidéo. Plus précisément, l'invention concerne la compression d'images ou de séquences d'images utilisant une représentation par blocs des images. L'invention peut notamment s'appliquer au codage image ou vidéo mis en oeuvre dans les codeurs actuels ou à venir (JPEG, MPEG, H.264, HEVC, etc et leurs amendements), et au décodage corresponda nt. 2. Art Antérieur Les images et séquences d'images numériques occupent beaucoup d'espace en termes de mémoire, ce qui nécessite, lorsque l'on transmet ces images, de les compresser afin d'éviter les problèmes d'encombrement sur le réseau utilisé pour cette transmission. En effet, le débit utilisable sur ce réseau est généralement limité. On connaît déjà de nombreuses techniques de compression de données vidéo, parmi lesquelles le standard de compression HEVC ("High Efficiency Video Coding, Coding Tools and Specification", Matthias Wien, Signais and Communication Technology, 2015). En relation avec la Figure 1, on considère une vidéo originale constituée d'une suite de M images Il, 12, ...IM, avec M entier non nul. Les images sont encodées par un encodeur, les données codées sont insérées un flux de données codées ou train binaire TB transmis à un décodeur via un réseau de communication, ou un fichier compressé FC, destiné à être stocké sur un disque dur par exemple. Le décodeur extrait les données codées, puis les traite dans un ordre prédéfini connu de l'encodeur et du décodeur, par exemple dans l'ordre temporel Il, puis 12, ..., puis IM, cet ordre pouvant différer suivant le mode de réalisation. Lors de l'encodage d'une image Im, avec m entier compris entre 1 et M, celle-ci est subdivisée en blocs de taille maximale qui peuvent à leur tour être subdivisés en blocs plus petits. 3054764 2 Chaque bloc C va subir une opération d'encodage ou de décodage consistant en une suite d'opérations, comprenant de manière non exhaustive une prédiction, un calcul de résidu du bloc courant, une transformation des pixels du bloc courant en coefficients, une quantification des coefficients et un codage entropique des coefficients quantifiés. 5 Le traitement d'un bloc C courant met en oeuvre un schéma de codage, par exemple tel que spécifié dans la norme HEVC, dans le document "ISO/IEC 23008-2:2013 - High efficiency coding and media delivery in heterogeneous environments -- Part 2: High efficiency video coding », International Organization for Standardization, publié en novembre 2013. Il fournit un ensemble d'éléments de description du bloc courant C. Ces éléments de 10 description peuvent être de types variés. De façon non exhaustive, ils comprennent notamment : - les informations relatives à des choix de codage du bloc courant C, par exemple un mode de codage du bloc courant, tel que le mode INTRA, INTER ou SKIP, un mode de prédiction du bloc courant, parmi les 35 modes de prédiction d'un bloc INTRA, un mode de prédiction d'un vecteur mouvement estimé pour le bloc courant, ouencore l'amplitude d'un 15 coefficient , connus en soi dans HEVC; - les valeurs de données à coder, telles que les composantes d'un vecteur mouvement, l'amplitude ou le signe d'un coefficient ; - etc Ces éléments de description sont ensuite codés, par exemple par codage de Huffman ou par 20 codage arithmétique ou toute autre technique connue de codage entropique, en une séquence de symboles binaires qui est insérée dans le flux de données codées. 3. Inconvénients de l'art antérieur Un inconvénient de l'art antérieur est que malgré le taux de compression élevé obtenu par le schéma de codage HEVC, le flux de données codées a des dimensions qui restent trop importantes 25 pour certains contenus multimédia, telles que les images à haute dynamique ou HDR (pour « High Dynaic Range », en anglais) ou encore les vidéos à haute fréquence d'images ou HFR de l'ordre de120 ou 240 images par seconde (pour « High Frame Rate », en anglais). 4. Objectifs de l'invention L'invention vient améliorer la situation. L'invention a notamment pour objectif de pallier ces inconvénients de l'art antérieur. 3054764 3 Plus précisément, un objectif de l'invention est de proposer une solution qui permette de réduire encore la taille du flux de données codées à transmettre à un décodeur. 5. Exposé de l'invention Ces objectifs, ainsi que d'autres qui apparaîtront par la suite, sont atteints à l'aide d'un procédé de 5 décodage d'un flux de données codées représentatif d'au moins une image, ladite image étant découpée en blocs, ledit flux comprenant une première portion et une deuxième portion. Selon l'invention, le procédé de décodage comprend une étape de test de séquences comprenant un nombre prédéterminé non nul d'éléments binaires, ladite étape comprenant au moins deux itérations des sous-étapes suivantes, pour ledit bloc courant: 10 - obtention d'une séquence distincte des séquences déjà testées; - décodage et reconstruction d'une version du bloc courant à partir de la séquence d'éléments binaires obtenue et de données codées lues dans la première portion de flux ; - évaluation d'une mesure de vraisemblance associée à la séquence obtenue à partir 15 de la version du bloc reconstruite. Il comprend en outre les étapes suivantes : - décodage d'une information caractéristique d'une première séquence comprenant le nombre prédéterminé non nul de symboles binaires à partir de la deuxième portion de flux ; 20 - sélection d'une séquence parmi les au moins deux séquences testées, en fonction des mesures de vraisemblance associées aux séquences testées et de l'information décodée, ladite séquence sélectionnée étant identifiée comme la première séquence ; et - décodage et reconstruction du bloc courant à partir de la première séquence et de la première portion de flux. 25 L'invention concerne aussi un procédé de codage d'un flux de données codées représentatif d'au moins une image, ladite image étant découpée en blocs, caractérisé en ce qu'il comprend les étapes suivantes, mises en oeuvre pour un bloc courant : - Codage du bloc courant en une pluralité de données codées ; 30 - Extraction de la pluralité de données codées d'une première séquence comprenant un nombre prédéterminé non nul de symboles binaires ; 3054764 4 - Insertion dans une première portion de flux des symboles binaires des données codées n'appartenant pas à la séquence extraite. Il comprend une étape de test de séquences comprenant le nombre prédéterminé non nul de symboles binaires, ladite étape comprenant au moins deux itérations des sous-étapes suivantes : 5 - obtention d'une séquence distincte des séquences déjà testées; - décodage et reconstruction d'une version du bloc courant à partir de la séquence de symboles binaires obtenue et de données codées lues dans la première portion de flux; - évaluation d'une mesure de vraisemblance associée à la séquence obtenue à partir 10 de la version du bloc reconstruite ; et il comprend en outre une étape de détermination d'une information caractéristique de la première séquence et une étape de codage de ladite information dans une deuxième portion du flux. Avec l'invention, un codeur produit des données codées relatives au bloc courant, dont il 15 extrait une séquence d'éléments binaires, qu'il n'insère pas dans la première portion de flux. En revanche, il insère dans la deuxième portion de flux une information caractéristique de la séquence extraite, que le décodeur pourra exploiter pour reconstruire cette séquence. L'invention propose donc une approche tout-à-fait nouvelle et inventive du codage d'images, qui consiste à supprimer une partie des données codées selon un schéma de compression classique et à transmettre, à leur 20 place, une information de taille plus réduite, qui permet au décodeur de reconstruire les données manquantes. Avec l'invention, un décodeur reçoit un flux de données codées comprenant deux portions, une première portion comprenant un sous-ensemble des données codées par le codeur pour représenter le bloc courant et une deuxième portion comprenant une information de signalisation 25 complémentaire, caractéristique d'une séquence de données codées qui est manquante dans la première portion de flux. L'invention propose ainsi une approche tout-à-fait nouvelle et inventive de la compression d'images, qui consiste à tronquer les données codées par le codeur d'un nombre prédéterminé de symboles binaires, les symboles tronqués pouvant être reconstruits par le décodeur en testant 30 différentes hypothèses et à partir de l'information complémentaire transmise par le codeur dans la deuxième portion de flux. 3054764 5 Le recours à un critère de maximisation d'une mesure de vraisemblance permet au décodeur d'identifier l'hypothèse correcte avec une bonne fiabilité. La probabilité pour une hypothèse d'être correcte n'étant pas associée à une distribution uniforme, l'information complémentaire peut être codée de manière efficace, en utilisant moins de bits que la séquence 5 tronquée. De cette manière, le flux de données obtenu est de taille réduite. Les différents modes ou caractéristiques de réalisation mentionnés ci-après peuvent être ajoutés indépendamment ou en combinaison les uns avec les autres, aux caractéristiques du procédé de décodage et/ou du procédé de codage défini ci-dessus. 10 Selon un aspect de l'invention, le procédé comprend une étape de tri des séquences testées selon des valeurs de mesures de vraisemblance associées décroissantes et l'information caractéristique de la première séquence comprend un rang de la première séquence parmi les séquences triées. Un avantage est que la première séquence étant généralement associée à une mesure de 15 vraisemblance élevée, le rang correspondant est faible et engendre un coût de signalisation réduit. Selon un autre aspect de l'invention, le procédé comprend une étape de détermination de la séquence testée la plus vraisemblable et l'information caractéristique de la première séquence comprend une mesure d'une différence bit à bit entre la valeur de la première séquence et celle de la séquence la plus vraisemblable. 20 Un avantage est qu'il n'est pas nécessaire de trier toutes les séquences testées, seulement de déterminer la plus vraisemblable. Un avantage supplémentaire réside dans le fait que le nombre de bits traités reste constant, qu'il s'agisse des bits de la séquence testée ou des différences bit à bit qui peuvent elle-même être codées chacune sur 1 bit. Ainsi, on va pouvoir traiter l'ensemble de ces données sur des architectures à longueur de bits constante, typiquement un multiple de 8, ce 25 qui permet une implémentation simple sur un circuit électronique qui manipule préférentiellement des octets. Selon un autre aspect de l'invention, l'étape d'évaluation comprend un calcul d'une mesure de distorsion des valeurs de pixels de part et d'autre d'au moins une frontière du bloc courant avec un bloc voisin déjà traité et la mesure de vraisemblance évaluée est inversement proportionnelle à 30 la mesure de distorsion. 3054764 6 Un avantage de cette mesure est d'être fiable pour les images naturelles dont les pixels proches ont des valeurs fortement corrélées. Selon encore un autre aspect de l'invention, l'étape de décodage et reconstruction complète la première portion de flux en insérant au moins une partie des éléments binaires de la séquence à 5 au moins une position prédéterminée. Le codeur extrait les éléments binaires des données codées à des positions qui sont connues au préalable du décodeur. De cette manière, il n'est pas nécessaire de prévoir de signalisation Selon un autre aspect de l'invention, la position déterminée est située avant le premier 10 élément binaire des données codées associées au bloc courant. Un avantage de ce mode de réalisation est d'une part sa simplicité et d'autre part de garantir qu'on pourra toujours supprimer au moins quelques éléments binaires des données codées relatives au bloc courant, même si leur taille est réduite. Selon encore un autre aspect de l'invention, le procédé de décodage comprend une étape 15 de reconstruction d'un flux de données codées complété à partir de la première portion de flux et de la séquence sélectionnée. Un avantage est de reconstruire un flux de données complet qui peut être décodé par un décodeur classique au cours d'une deuxième passe. 20 Selon un autre aspect de l'invention, le procédé de décodage comprend une étape de stockage dans une mémoire du bloc reconstruit. Un avantage est de permettre la restitution de l'image reconstruite sans nécessiter de deuxième passe de décodage. Avantageusement, les étapes de décodage comprennent un décodage entropique à états finis, 25 l'étape de stockage comprend en outre le stockage d'un état du décodeur entropique associé à la séquence sélectionnée. De cette manière, le décodeur entropique peut, suite au test des 2N hypothèses se repositionner sur l'état associé à l'hypothèse correcte avant de commencer le décodage du bloc suivant. 3054764 7 Les différents modes ou caractéristiques de réalisation mentionnés ci-après peuvent être ajoutés indépendamment ou en combinaison les uns avec les autres, aux caractéristiques du procédé de décodage et/ou du procédé de codage défini ci-dessus. L'invention concerne également un dispositif de décodage adapté pour mettre en oeuvre le 5 procédé de décodage selon l'un quelconque des modes particuliers de réalisation définis ci-dessus. Ce dispositif de décodage pourra bien sûr comporter les différentes caractéristiques relatives au procédé de décodage selon l'invention. Ainsi, les caractéristiques et avantages de ce dispositif de décodage sont les mêmes que ceux du procédé de décodage, et ne sont pas détaillés plus amplement. 10 Selon un mode particulier de réalisation de l'invention, un tel dispositif de décodage est compris dans un terminal. L'invention concerne également un dispositif de codage adapté pour mettre en oeuvre le procédé de codage selon l'un quelconque des modes particuliers de réalisation définis ci-dessus. Ce dispositif de codage pourra bien sûr comporter les différentes caractéristiques relatives au procédé 15 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. Selon un mode particulier de réalisation de l'invention, un tel dispositif de codage est compris dans un terminal, ou un serveur. Corrélativement, l'invention concerne aussi un équipement terminal comprenant un 20 dispositif de décodage et/ou un dispositif de codage qui viennent d'être décrits. L'invention concerne aussi un signal porteur d'un flux de données codées représentatives d'au moins une image numérique, ladite image numérique étant divisée en blocs de pixels traités dans un ordre défini, caractérisé en ce que le flux de données codées comprend, pour un bloc courant, au moins une première portion de flux comprenant des données codées représentatives 25 d'éléments de syntaxe du bloc courant et une deuxième portion de flux comprenant une information caractéristique d'une première séquence comprenant un nombre prédéterminé non nul d'éléments binaires, et en ce que, sur réception dudit signal, un décodeur est apte à identifier la première séquence d'éléments binaires à partir de l'information codée et à reconstruire le bloc courant à partir des données décodées de la première portion de flux et de la première séquence 30 identifiée. 3054764 8 Le procédé de décodage, respectivement le procédé de codage, selon l'invention peut être mis en oeuvre de diverses manières, notamment sous forme câblée ou sous forme logicielle. Selon un mode particulier de réalisation de l'invention, le procédé de décodage, 5 respectivement le procédé de codage, est mis en oeuvre par un programme d'ordinateur. L'invention concerne également un programme d'ordinateur comportant des instructions pour la mise en oeuvre du procédé de décodage ou du procédé de codage selon l'un quelconque des modes particuliers de réalisation décrits précédemment, lorsque ledit programme est exécuté par un processeur. Un tel programme peut utiliser n'importe quel langage de programmation. Il peut être 10 téléchargé depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur. Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. 15 L'invention vise aussi un support d'enregistrement ou support d'informations lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus. Les supports d'enregistrement mentionnés ci-avant peuvent être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou 20 encore un moyen d'enregistrement, par exemple magnétique tel qu'un disque dur. D'autre part, les supports d'enregistrement peuvent correspondre à un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. Alternativement, les supports d'enregistrement peuvent correspondre à un circuit 25 intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. 6. Liste des figures D'autres avantages et caractéristiques de l'invention apparaîtront plus clairement à la 30 lecture de la description suivante d'un mode de réalisation particulier de l'invention, donné à titre de simple exemple illustratif et non limitatif, et des dessins annexés, parmi lesquels : 3054764 9 - la figure 1 décrit de façon schématique le procédé de codage d'une image selon un mode de réalisation de l'invention ; les figures 2, 3 et 4 illustrent de façon schématique l'étape de décodage d'un bloc courant à partir d'une séquence d'éléments binaires testée et de données codées de la première 5 portion de flux ; - la figure 5 illustre de façon schématique un exemple de mesure de coût calculée pour évaluer une mesure de vraisemblance associée à une hypothèse testée pour le bloc courant ; - la figure 6 illustre de façon schématique un exemple de structure d'un flux de données 10 comprenant une première et une deuxième portions de flux selon l'invention ; - la figure 7 décrit de façon schématique un procédé de décodage d'une image selon un mode de réalisation de l'invention ; - la figure 8 illustre de façon schématique l'étape de lecture de données codées dans la première et la deuxième portion de flux à l'aide d'un premier et d'un deuxième pointeurs. 15 - la figure 9 illustre de façon schématique l'étape de décodage/reconstruction d'un bloc courant à partir de données codées et de la séquence d'éléments binaires identifiée par le décodeur ; - la figure 10 illustre de façon schématique la structure matérielle d'un dispositif de codage selon un mode de réalisation de l'invention ; et 20 - la figure 11 illustre de façon schématique la structure matérielle d'un dispositif de décodage selon un mode de réalisation de l'invention. 7. Description d'un mode de réalisation particulier de l'invention 7.1 Principe général 25 Le principe général de l'invention repose sur la suppression côté codeur, d'un sous- ensemble des symboles binaires constituant les données codées d'un bloc courant et sur la transmission d'un flux de données codées comprenant, dans une première portion, les données codées tronquées et, dans une deuxième portion, une information caractéristique de la séquence supprimée. 3054764 10 Le décodeur selon l'invention décode l'information puis reconstruit la séquence de symboles binaires à l'aide de l'information décodée 7.2 Description d'un mode de réalisation d'un procédé de codage selon l'invention En relation avec la Figure 1, on décrit les étapes d'un procédé de codage d'une image selon un 5 premier mode de réalisation de l'invention. Dans la suite, on considère une vidéo originale constituée d'une suite de M images Il, 12, ...IM. Les images sont encodées dans un ordre prédéfini connu de l'encodeur et du décodeur, par exemple dans l'ordre temporel Il, puis 12, ..., puis IM (cet ordre peut différer suivant le mode de réalisation). 10 Le procédé de codage selon l'invention comprend deux phases, une première phase de formation d'une première portion de flux de données codées et une deuxième phase de formation d'une deuxième portion de flux. 7.2.1 Formation d'une première portion de flux Lors de l'encodage, l'image Im est subdivisée en blocs de taille variable dont l'ordre de 15 traitement est connu de l'encodeur et du décodeur. Chaque bloc va subir une opération d'encodage consistant en une suite d'opérations (application d'étapes de prédiction, calcul de résidu, quantification, codage entropique) qui sera détaillée par la suite. 7.2.1.1 Sélection premier bloc Au cours de cette étape EO on sélectionne comme bloc courant B le premier bloc à traiter. 20 Dans le mode préféré de réalisation, il s'agit du premier bloc (dans l'ordre lexicographique). 7.2.1.2 Codage du bloc courant en éléments de syntaxe Au cours de cette étape El on va encoder de façon classique ce bloc B, par exemple comme le décrit la norme de codage vidéo HEVC. Cette étape consiste typiquement à prédire le bloc courant à l'aide de pixels précédemment 25 traités dans la même image ou dans une image précédemment traitée, à produire un résidu représentatif de la différence entre la prédiction et les vraies valeurs des pixels du bloc courant, à transformer ce résidu par transformée fréquentielle comme une DCT par exemple, à quantifier ce résidu transformé. Chacune de ces opérations (non exhaustives) est susceptible de produire des éléments de syntaxe qui sont des valeurs indicatives, par exemple, du type de prédiction utilisée, 3054764 11 du type de transformée utilisée, de la division du bloc courant en sous-blocs, de la valeur et du signe des résidus quantifiés, etc. 7.2.1.3 Codage des éléments de syntaxe Au cours de cette étape E2, chaque élément de syntaxe est ensuite codé par codage 5 entropique, par exemple de type CABAC comme spécifié dans la norme HEVC. Cette étape transforme donc les éléments de syntaxe en une suite de symboles binaires 0 et 1. Cette suite de symboles binaire représente le bloc courant. Le codage entropique consiste à exploiter la distribution des éléments de syntaxe pour en réduire le débit. Par exemple, pour un élément de syntaxe prenant de multiples valeurs possibles, 10 on attribuera un code binaire court aux valeurs fréquentes et un code binaire long aux valeurs rares. Ceci permet de réduire, en moyenne, le nombre de bits nécessaires au codage de ces valeurs. Le code Morse est un exemple de code entropique adapté à la statistique des lettres (qui constituent dans ce cas les éléments de syntaxe) dans la langue anglaise. Le code de Huffman est une technique pour construire un code binaire adapté à une statistique donnée, avec pour principe 15 que chaque élément de syntaxe est codé par un nombre entier de bits. Le codage arithmétique permet quant à lui de mutualiser des bits entre plusieurs éléments de syntaxe, et ainsi de coder un élément de syntaxe sur un nombre non entier de bits. La séquence d'éléments binaires issue de l'étape de codage entropique est ajoutée à la suite d'un train binaire intermédiaire TBO, comprenant les données codées des blocs déjà traités. 20 7.2.1.4 Détermination d'un ensemble EB de N éléments binaires du train binaire intermédiaire associés au codage du bloc courant B Au cours de cette étape E3, on détermine quel serait, pour le bloc courant, le premier bit qu'il serait nécessaire de lire dans le flux compressé intermédiaire si l'on tentait de décoder ce flux binaire à partir de moyens classiques tels qu'un décodeur HEVC. Selon un mode de réalisation de 25 l'invention, on a recours lors du décodage, à un pointeur de flux PFO que l'on déplace au fur et à mesure de la lecture de données codées dans le flux. Cette étape E3 peut être effectuée lors de l'encodage dudit bloc courant, ou encore en simulant son décodage. Ensuite, une séquence d'éléments binaires est identifiée. Il s'agit des bits consécutifs situés 30 après (et incluant) le premier bit et avant le dernier qu'il est nécessaire de lire pour décoder le bloc courant, dans la limite de N bits, où N est un nombre fixé. Ces bits forment un ensemble de bits EB 3054764 12 ayant une valeur. Ainsi, prenons un exemple où N vaut 4, pour le bloc courant, les bits EB valent par exemple 1011. On notera que si le bloc courant est codé sur moins de N bits, l'ensemble EB contient lui-même moins de N bits Dans un mode alternatif de réalisation, les N bits EB sont les N dernier bits lus lors du 5 décodage du bloc courant. 7.2.1.5 Création de la première portion de flux à partir des données codées Au cours de cette étape E4 on supprime du train binaire intermédiaire TBO les éléments binaires EB déterminés et on ajoute les éléments binaires restants à un deuxième train binaire TB1, qu'on désignera dans la suite par première portion de flux. Autrement dit, le deuxième train 10 binaire TB1 est donc constitué pour chaque bloc des symboles binaires du premier train binaire TBO auxquels sont retirés les éléments binaires EB associés à chaque bloc. On notera que dans un mode alternatif de réalisation, il est possible de combiner cette étape avec la précédente : dans ce cas, on n'a pas recours à un train binaire intermédiaire TBO, mais on écrit directement dans la première portion de flux TB1 les éléments binaires représentatifs 15 des données codées du bloc courant hormis les bits EB. 7.2.1.6 Test de dernier bloc Au cours de cette étape E5, on vient tester si le bloc courant est le dernier bloc à traiter par le codeur, compte tenu de l'ordre de parcours défini précédemment. Si oui, l'étape suivante est l'étape de sélection du premier bloc. Si non, l'étape suivante est l'étape de codage El du nouveau 20 bloc courant en éléments de syntaxe. 7.2.1.7 Bloc suivant Au cours de cette étape E6 on vient sélectionner le bloc suivant B à traiter selon le procédé qui vient d'être décrit. Ce bloc devient le bloc courant à traiter, et l'étape suivante est l'étape de prédiction. 25 A ce stade, tous les blocs de l'image courante ont été traités une première fois et une partie des données codées pour le bloc courant a été insérée dans la première portion de flux TB1. 7.2.2 Formation d'une deuxième portion de flux de données codées Au cours d'une deuxième phase du procédé d'encodage selon l'invention, on forme une deuxième 30 portion de flux TB2 de la façon suivante : 3054764 13 7.2.2.1 Sélection premier bloc Au cours de cette étape E7 on sélectionne comme bloc courant B le premier bloc à traiter. Dans le mode préféré de réalisation, il s'agit du premier bloc (dans l'ordre lexicographique). 7.2.2.2 Test de séquences 5 Au cours de cette étape E8, on teste les 2N séquences de N symboles binaires possibles, ou hypothèses, pour remplacer la séquence d'éléments binaires EB qui a été supprimée du train binaire TBO pour le bloc courant. L'objectif est de parcourir toutes les hypothèses et de reconstruire le bloc courant pour chacune d'elles. Par exemple, si EB contient 4 bits, on va tester 16 hypothèses. 10 7.2.2.2.1 Obtention d'une hypothèse En E81, on sélectionne une hypothèse, distincte de celles précédemment traitées, pour les bits EB associés au bloc courant, par exemple selon un ordre de valeur croissant du nombre formé par la séquence d'éléments binaires. Dans le cas où N vaut 4, on a : 15 Hypothèse numéro 0, H(0)=0000 Hypothèse numéro 1, H(1)=0001 Hypothèse numéro 2, H(2)=0010 Hypothèse numéro 15, H(15)=1111 20 La première hypothèse testée est donc l'hypothèse H(0)=0000. 7.2.2.2.2 Détermination des éléments de syntaxe sous l'hypothèse courante Au cours de cette étape E7 on décode le bloc courant en utilisant l'hypothèse numéro H(i) pour l'ensemble de bits EB. En relation avec les Figures 2,3 et 4 on considère un exemple de réalisation selon lequel 25 les éléments binaires EB ont été extraits à partir du premier élément binaire représentatif du bloc courant. On suppose que cette position est pointée par un premier pointeur de flux PF1. Elle correspond à une position de lecture d'éléments binaires du flux TB1. L'opération de décodage consiste donc à décoder les éléments de syntaxe du bloc à partir d'au moins une partie des bits EB de l'hypothèse courante suivie (le cas échéant, car le décodage 3054764 14 du bloc peut être terminé avant) des éléments binaires de la première portion de flux TB1 relatifs au bloc courant. Ce décodage produit une séquence d'éléments de syntaxe SES(i), où i est le numéro de l'hypothèse courante. Dans l'exemple de la Figure 2, la séquence d'éléments binaires H(i) est complètement lue 5 ainsi que les éléments binaires de la première portion de flux associés au bloc courant, à compter de la position du pointeur PF1. Dans l'exemple de la Figure 3, la séquence d'éléments binaires H(i) n'est pas complètement lue, parce que le décodeur intégré au codeur a obtenu les valeurs des éléments de syntaxe dont il a besoin à l'aide des premiers bits de la séquence selon cette hypothèse et n'en a 10 donc pas eu besoin. On peut donc supposer que l'hypothèse H(i) ne correspond pas à la séquence de bits extraite de TBO. Dans l'exemple de la Figure 4, la séquence d'éléments binaires EB(i) est complètement lue, ainsi que des éléments binaires de la première portion de flux situés au-delà de la limite des données codées du bloc courant. On peut donc supposer que l'hypothèse H(i) ne correspond pas à 15 la séquence de bits extraite de TBO. A l'issue de ce décodage, on dispose de la séquence d'éléments de syntaxe SES(i) pour l'hypothèse i. 7.2.2.2.3 Reconstruction du bloc associé à l'hypothèse courante Au cours de cette sous-étape E82, pour l'hypothèse H(i), on reconstruit une version 20 décodée VB(i) du bloc courant. Elle est construite à partir des éléments de syntaxe SES(i) lus dans la première portion de flux et/ou dans la séquence qui correspond à l'hypothèse. 7.2.2.2.4 Evaluation d'une mesure de vraisemblance associée au bloc décodé Au cours de cette sous-étape E83, nous allons évaluer un coût associé à chaque version décodée du bloc courant VB(i). Dans le mode préféré de réalisation et en relation avec la Figure 5, 25 cette approche consiste à extrapoler une série de valeurs {rj} de la façon suivante. Supposons que le bloc courant soit un bloc de taille 4x4 pixels. Les pixels situés immédiatement à gauche et au-dessus du bloc courant sont dénommés Al, A2,..., A8. Les pixels situés à gauche et au-dessus des pixels Al, A2,..., A8 sont dénommés Bl, B2, ,B8. Les valeurs {rj} extrapolées sont calculées de la façon suivante : 30 r1=2.A1-B1 r2=2.A2-B2 3054764 15 r3=2.A3-B3 r4=2.A4-B4 r5=2.A6-B6 r6=2.A7-B7 5 r7=2.A8-B8 Ensuite, le coût C(i) de l'hypothèse H(i) est calculé de la façon suivante : C(i) = Ir1-X11+Ir2-X21+Ir3-X31+Ir4-X41+Ir5-X51+Ir6-X61+Ir7-X71 Où X1, X2, X3, X4 sont les valeurs des pixels de la première colonne du bloc VB(i) et X4,X5,X6,X7 les valeurs de pixels de la première ligne de ce bloc. 10 On voit que cette mesure de coût est représentative de la discontinuité le long des frontières du bloc. Dans des modes alternatifs de réalisation, d'autres mesures de coût sont possibles. Par exemple, on peut choisir la somme des différences inter-pixels de tous les pixels internes au bloc. Ou encore, on peut calculer une énergie du résidu du bloc courant. 15 On en déduit une mesure de vraisemblance V(i) = -C(i). Plus le coût de l'hypothèse H(i) est élevé, moins l'hypothèse est vraisemblable. 7.2.2.2.5 Test de dernière hypothèse Au cours de cette étape (non représentée) on va vérifier si l'hypothèse courante H(i) est la dernière hypothèse à tester sur les bits EB. Dans le mode préféré de réalisation où nous testons les 20 valeurs binaires dans l'ordre croissant classique, ce test consiste à vérifier si la valeur ne contient que des 1. Si c'est le cas, on passe à l'étape E9 de détermination d'une information caractéristique de la séquence EB. Sinon, on retourne à l'étape E81 pour tester l'hypothèse suivante. 7.2.2.3 Détermination d'une information caractéristique de la séquence de symboles 25 binaires EB Toutes les hypothèses ont été testées. Dans un premier mode de réalisation de l'invention, on trie en E91 les séquences testées selon un ordre de mesure de vraisemblance décroissante et on détermine au cours d'une étape E92 la valeur d'une information caractéristique IC de la séquence d'éléments binaires EB qui correspond 3054764 16 à un rang de l'hypothèse correcte H(i) (soit la valeur H(4) = 1011 dans notre exemple) dans un tableau qui contient toutes les hypothèses classées par coût croissant ou par mesure de vraisemblance décroissante. Ainsi, on peut trouver que l'hypothèse 1011 est la 4ème parmi les 16 combinaisons classées par coût croissant. On va alors affecter la valeur 4 à un élément de syntaxe 5 DS associé au bloc courant. Bien sûr, on peut utiliser d'autres types d'informations caractéristiques. Ainsi, dans un deuxième mode de réalisation, on identifie en E91' la séquence S (i) qui correspond à l'hypothèse la plus vraisemblable, c'est-à-dire celle dont le coût est le plus faible. Ensuite, on compare bit à bit les séquences EB et S (i) en E92', et on construit une information caractéristique IC = BDIFF 10 représentative de l'égalité ou de l'inégalité entre les bits. Par exemple, on peut commencer par comparer les valeurs du bit de poids le plus fort de EB et SEB(i), et transmettre BDIFF-0 si ils sont différents et BDIFF-1 si ils sont égaux. Ensuite, on applique le même procédé au deuxième bit de poids fort, et on répète le procédé jusqu'au bit de poids faible. On constate que le plus souvent, les bits sont égaux. BDIFF prend donc plus souvent la valeur 1 que 0. 15 7.2.2.4 Codage d'une information caractéristique de la séquence d'éléments binaires dans la deuxième portion de flux Au cours de cette étape E10, on code la valeur de l'information caractéristique IC déterminée par codage entropique, de façon classique, par exemple avec un codeur CABAC. On insère la valeur codée dans la deuxième portion de flux TB2. 20 En ce qui concerne le premier mode de réalisation, le coût associé à la combinaison correcte tend à être faible, donc la valeur de DS est souvent petite. On a donc une répartition statistique non uniforme des occurrences de DS sur l'ensemble des valeurs possibles, ce qui permet de réduire le débit, en utilisant un codeur entropique classique (codage de Huffman, codage arithmétique), adapté à la statistique de DS. 25 En ce qui concerne le deuxième mode de réalisation, la séquence la plus vraisemblable est généralement proche de la séquence correcte ce qui fait que la différence bit à bit a une valeur qui est souvent petite. La répartition statistique des occurrences est dans ce cas aussi non uniforme ce qui permet au codeur entropique de réaliser une compression efficace. 7.2.2.5 Test de dernier bloc 30 Au cours de cette étape E11, on vient tester si le bloc courant est le dernier bloc à traiter, compte tenu de l'ordre de parcours défini précédemment. Si oui, l'étape suivante est l'étape E13 de 3054764 17 concaténation des première et deuxième portions de flux TB1 et TB2. Si non, l'étape suivante est l'étape de sélection du bloc suivant. 7.2.2.6 Bloc suivant Au cours de cette étape E12 on vient sélectionner le bloc suivant à traiter par l'unité de 5 codage, tel que décrit précédemment. Ce bloc devient le bloc courant à traiter, et l'étape suivante est l'étape de sélection de la première hypothèse. 7.2.2.7 Concaténation des trains binaires Au cours de cette étape E13 on va concaténer la première et la deuxième portions de flux TB1 et TB2 pour constituer le train binaire final TB3 qui peut être ensuite stocké ou transmis au 10 décodeur. La concaténation peut se faire par juxtaposition comme illustré par la Figure 6, ou par multiplexage des bits des flux TB1 et TB2, ou par toute autre façon de combiner les deux flux, pourvu qu'elle permette au décodeur de les distinguer. Cette étape peut comprendre en outre une insertion dans le flux final TB3 d'une information permettant d'identifier la localisation de la deuxième portion de flux TB2. Par exemple, 15 si les flux TB1 et TB2 sont juxtaposés dans cet ordre, une information sera insérée avant le début du premier flux TB1 afin d'indiquer où se trouve le début du flux TB2 dans le flux de données final TB3. Il s'agit par exemple d'un flag FL2 qui comprend une adresse correspondant au début de la deuxième portion TB2. 20 7.3 Description d'un mode de réalisation d'un procédé de décodage selon l'invention Dans la suite, on considère un décodeur ayant reçu le train binaire TB3 produit par le procédé de codage selon l'invention et on décrit un procédé de décodage selon l'invention en relation avec la Figure 7. 7.3.1 Identification de la première et de la deuxième portion TB1, TB2 dans le train binaire 25 TB3 Au cours de cette étape DOO, on va identifier la première portion de flux TB1 comprenant au moins une partie des données codées des blocs de l'image et une deuxième portion de flux TB2 comprenant les informations IC caractéristiques des séquences de symboles binaires manquantes dans la première portion de flux. 3054764 18 En relation avec la Figure 8, on suppose que la première et la deuxième portion de flux sont juxtaposées, avec TB1 suivi par TB2 et on lit dans le flux TB3 une information FL2 représentative d'une position de début de la deuxième portion de flux TB2 dans le flux complet TB3. Ainsi, techniquement, le décodeur a recours de façon classique à un premier pointeur de 5 fichier PF1 dont la position est initialisée au début du flux TB3 et qui se déplace dans la première portion de flux au fur et à mesure de l'avancement du décodage et, selon l'invention, un deuxième pointeur de fichier PF2, dont la position est initialisée au niveau de l'adresse indiquée par le flag FL2 et qui se déplace dans la deuxième portion de flux au fur et à mesure de l'avancement du décodage. 10 7.3.2 Sélection de premier bloc Cette étape DO est identique à celle mise en oeuvre au codage. 7.3.2 Traitement des données de la première portion de flux pour le bloc courant 7.3.2.1 Test des séquences d'éléments binaires de taille N Au cours de cette étape D1, on teste les 2N séquences de N symboles binaires ou 15 hypothèses H(j) possibles avec j entier compris entre 1 et 2N-1. L'objectif est de parcourir toutes les hypothèses. Par exemple, si le sous ensemble EB contient N=4 bits, on va tester 16 hypothèses. Par exemple, on parcourt les hypothèses selon un ordre prédéterminé comme déjà décrit dans la section 7.2.2.2.1 pour le procédé de codage selon l'invention et on réalise les étapes 20 suivantes : 7.3.2.1.1 Obtention d'une hypothèse H(j) - sous-étape D11 On obtient une hypothèse, parmi les hypothèses non encore traitées. 7.3.2.1.2 Détermination des éléments de syntaxe correspondant à l'hypothèse courante H(j).- sous-étape D12 25 On suppose que la séquence de N éléments binaires EB a été extraite par l'encodeur au début des données codées du bloc courant B. Le décodeur reproduit le fonctionnement de l'encodeur et commence par décoder les éléments binaires de la séquence de l'hypothèse courante H(j) pour déterminer les valeurs des éléments de syntaxe SES(j) dont il a besoin pour décoder le bloc courant. 30 Plusieurs cas de figure peuvent se présenter : 3054764 19 Le décodeur n'a pas décodé tous les éléments de syntaxe dont il a besoin à partir des N éléments binaires de la séquence H(j). Il continue son décodage en lisant les données de la première portion de flux TB1 à partir de la position courante du pointeur PF1 qu'il déplace au fur et à mesure de sa lecture, 5 le décodeur a décodé tous les éléments de syntaxe dont il a besoin pour le bloc courant à partir des N éléments binaires de la séquence H(i). Dans ce cas, il ne déplace par le pointeur PF1 et ne lit pas d'information dans la première portion de flux TB1; le décodeur a décodé tous les éléments de syntaxe dont il a besoin à partir des M REVENDICATIONS1. Procédé de décodage d'un flux de données codées représentatif d'au moins une image (Im), ladite image étant découpée en blocs, ledit flux comprenant une première portion (TB1) et une deuxième portion (TB2), caractérisé en ce que le procédé de décodage comprend une étape de test de séquences (D1) comprenant un nombre prédéterminé non nul d'éléments binaires, ladite étape comprenant au moins deux itérations des sous-étapes suivantes, pour ledit bloc courant (B): - obtention (D11) d'une séquence (H(j)) distincte des séquences déjà testées; - décodage et reconstruction (D13) d'une version du bloc courant à partir de la séquence d'éléments binaires obtenue (H(j)) et de données codées lues dans la première portion de flux ; - évaluation (D14) d'une mesure de vraisemblance V(j) associée à la séquence obtenue à partir de la version du bloc reconstruite ; et en ce qu'il comprend en outre les étapes suivantes : - décodage (D3) d'une information caractéristique (IC(EB)) d'une première séquence comprenant le nombre prédéterminé non nul de symboles binaires à partir de la deuxième portion de flux (TB2) ; - sélection (D4) d'une séquence parmi les au moins deux séquences testées, en fonction des mesures de vraisemblances associées aux séquences testées et de l'information décodée, ladite séquence sélectionnée étant identifiée comme la première séquence ; et - décodage et reconstruction (D9) du bloc courant à partir de la première séquence (H(j0)) et de la première portion de flux (TB1). 2. Procédé de codage d'un flux de données codées représentatif d'au moins une image (Im), ladite image étant découpée en blocs, caractérisé en ce qu'il comprend les étapes suivantes, mises en oeuvre pour un bloc courant (B) : - Codage (El) du bloc courant en une pluralité de données codées ; - Extraction (E3) de la pluralité de données codées d'une première séquence EB comprenant un nombre prédéterminé non nul de symboles binaires ; - Insertion (E4) dans une première portion de flux (TB1) des symboles binaires des données codées n'appartenant pas à la séquence extraite ; 3054764 27 en ce qu'il comprend une étape (E8) de test de séquences comprenant le nombre prédéterminé non nul de symboles binaires, ladite étape comprenant au moins deux itérations des sous-étapes suivantes : - obtention (E81) d'une séquence distincte des séquences déjà testées; 5 - décodage et reconstruction (E82) d'une version du bloc courant à partir de la séquence de symboles binaires obtenue et de données codées lues dans la première portion de flux; - évaluation (E83) d'une mesure de vraisemblance associée à la séquence obtenue à partir de la version du bloc reconstruite ; 10 et en ce qu'il comprend en outre une étape (E9) de détermination d'une information (IC) associée à la première séquence, une étape de codage (E10) de ladite information et une étape (E11) d'insertion de l'information codée dans une deuxième portion du flux (TB2). Procédé selon l'une des revendications 1 ou 2, caractérisé en ce que le procédé comprend une étape (D2, E91) de tri des séquences testées selon des valeurs de mesures de vraisemblance associées décroissantes et en ce que l'information (IC) caractéristique de la première séquence comprend un rang (DS) de la première séquence parmi les séquences triées. Procédé selon la revendication 1 ou 2, caractérisé en ce que le procédé comprend une étape (D2', E91') de détermination de la séquence testée la plus vraisemblable et en ce que l'information (IC) caractéristique de la première séquence comprend une mesure (BDIFF) d'une différence bit à bit entre la valeur de la première séquence et celle de la séquence la plus vraisemblable. Procédé selon l'une des revendications 3 ou 4, caractérisé en ce que l'étape d'évaluation d'une mesure de vraisemblance comprend un calcul d'une mesure de distorsion des valeurs de pixels de part et d'autre d'au moins une frontière du bloc courant avec un bloc voisin déjà traité et la mesure de vraisemblance évaluée est inversement proportionnelle à la mesure de distorsion. Procédé selon l'une des revendications précédentes caractérisé en ce que l'étape de décodage et reconstruction (D13, E82) complète la première portion de flux en insérant au moins une partie des éléments binaires de la séquence à au moins une position prédéterminée. Procédé selon la revendication précédente, caractérisé en ce que la position déterminée est située avant le premier élément binaire des données codées associées au bloc courant. 3. 15 4. 20 5. 256. 7. 30 3054764 28 8. Procédé de décodage selon la revendication 1, caractérisé en ce qu'il comprend une étape (D5) de reconstruction d'un flux de données codées complété à partir de la première portion de flux et de la séquence sélectionnée. 9. Procédé de décodage selon la revendication 1, caractérisé en ce qu'il comprend une étape 5 (D5') de stockage du bloc reconstruit dans une mémoire (MEM2). 10. Procédé selon la revendication 9, caractérisé en ce que les étapes de décodage comprennent un décodage entropique à états finis, l'étape de stockage comprend en outre le stockage d'un état (ET) du décodeur entropique associé à la séquence sélectionnée. 11. Dispositif (200) de décodage d'un flux de données codées représentatif d'au moins une image, 10 ladite image étant découpée en blocs, ledit flux comprenant une première portion (TB1) et une deuxième portion (TB2), caractérisé en ce que ledit dispositif de décodage comprend une unité (TEST) de test de séquences comprenant un nombre prédéterminé non nul d'éléments binaires, ladite unité étant apte à mettre en oeuvre au moins deux itérations des sous-unités suivantes, pour ledit bloc courant: 15 - obtention (OBT) d'une séquence distincte des séquences déjà testées; - décodage (DEC) et reconstruction d'une version du bloc courant à partir de la séquence d'éléments binaires obtenue et de données codées lues dans la première portion de flux ; - évaluation (EVAL) d'une mesure de vraisemblance associée à la séquence obtenue à 20 partir de la version du bloc reconstruite ; et en ce qu'il comprend en outre les unités suivantes : - décodage (DEC IC) d'une information caractéristique d'une première séquence comprenant le nombre prédéterminé non nul de symboles binaires aux séquences testées, à partir de la deuxième portion de flux ; 25 - sélection (SEL) d'une séquence parmi les au moins deux séquences testées, en fonction de la mesure de vraisemblance évaluée et de l'information décodée, ladite séquence sélectionnée étant identifiée comme la première séquence ; et - décodage (REC B) et reconstruction du bloc courant à partir de la première séquence et de la première portion de flux. 30 12. Dispositif (100) de codage d'un flux de données codées représentatif d'au moins une image, ladite image étant découpée en blocs, caractérisé en ce qu'il comprend les unités suivantes, aptes à être mises en oeuvre pour un bloc courant : - Codage (COD B) du bloc courant en une pluralité de données codées ; 3054764 29 - Extraction (EXT) de la pluralité de données codées d'une première séquence comprenant un nombre prédéterminé non nul de symboles binaires ; - Insertion (INS TB1) dans une première portion de flux (TB1) des symboles binaires des données codées n'appartenant pas à la séquence extraite ; 5 en ce qu'il comprend une unité (TEST) de test de séquences comprenant le nombre prédéterminé non nul de symboles binaires, ladite unité étant apte à mettre en oeuvre au moins deux itérations des sous-unités suivantes : - obtention (OBT) d'une séquence distincte des séquences déjà testées; - décodage (DEC) et reconstruction d'une version du bloc courant à partir de la 10 séquence de symboles binaires obtenue et de données codées lues dans la première portion de flux; - évaluation (EVAL) d'une mesure de vraisemblance associée à la séquence obtenue à partir de la version du bloc reconstruite ; et en ce qu'il comprend en outre une unité de détermination (DET IC) d'une information (IC) 15 caractéristique de la première séquence, une unité (COD IC) de codage de ladite information et une unité d'insertion (INS TB2) dans une deuxième portion du flux (TB2). 13. Signal portant un train binaire (TB3) comprenant des données codées représentatives d'au moins une image numérique (Im), ladite image numérique étant divisée en blocs de pixels traités dans un ordre défini, caractérisé en ce que le flux de données codées comprend, pour 20 un bloc courant (B), au moins une première portion de flux (TB1) comprenant des données codées représentatives d'éléments de syntaxe du bloc courant et une deuxième portion de flux (TB2) comprenant une information (IC) caractéristique d'une première séquence (EB) comprenant un nombre prédéterminé non nul d'éléments binaires, et en ce que, sur réception dudit signal, un décodeur est apte à identifier la première séquence d'éléments binaires à 25 partir de l'information caractéristique et à reconstruire le bloc courant à partir des données décodées de la première portion de flux et de la première séquence identifiée. 14. Equipement terminal d'utilisateur (ET) caractérisé en ce qu'il comprend un dispositif de décodage (200) d'au moins une image numérique selon la revendication 11 et un dispositif de codage (100) d'au moins une image numérique selon la revendication 12. 30 15. Programme d'ordinateur (Pg1, Pg2) comprenant des instructions pour la mise en oeuvre du procédé de selon l'une des revendications 1 à 10, lorsqu'il est exécuté par un processeur.