Brevet FR2664117A1 — publié le 19920103

Procédé de codage à paramètres ajustables d'un champ de mouvement dans une séquence d'images animées La présente invention concerne un procédé de codage à paramètres ajustables d'un champ de mouvement dans une séquence d'images animées. L'analyse du mouvement dans une séquence d'images animées, notamment en télévision, est une - opération qui est fondamentalement importante dans la chaîne des opérations effectuées pour traiter les images. Les méthodes d'estimation hiérarchiques connues telles que décrites par exemple dans la demande de brevet français n0 89 11328 déposée au nom de la Demanderesse apparaissent jus qu a présent les plus efficaces, et les mieux adaptées au fait que le champ de mouvement d'une image peut être considéré comme l'assemblage de zones d'images à déplacement constant. Ces méthodes présentent aussi l'avantage qu'elles permettent d'obtenir un déplacement constant sur des zones homogènes de l'image ou de trouver le déplacement correspondant aux grandes zones en mouvement (panoramique ...) mais aussi d'avoir une bonne précision notamment sur les frontières des zones en mouvement et dans les zones à mouvements variés. Cependant le problème qui se pose est de pouvoir coder le champ de vecteurs obtenus de façon à obtenir un débit aussi faible que possible. Le problème a été Jusqu a présent résolu en différenciant d'une part, le codage d'un champ de mouvement comme partie du codage d'image, et d'autre part, le codage spécifique d'un champ de mouvement pour des applications précises de télévision notamment. Des exemples de codage de champ de mouvement comme partie du codage d'image ont déjà fait l'objet des publications suivantes intitulées "Variable block-size image coding" J.Jacques VAISEY and Allen GERSHO IEEE - 1987 1,Video codec for audiovisual services AT px64 Kits" Draft revision of recommendation H.261 - 30 march lus90 et "Motion vector coding with conditional transmission" WOO YOUNG CHOI and RAE-HONG PARK - Signal processing vol. 18 n03 - nov. 89 pages 259-267 Des exemples de codage de champs de mouvement pour des applications plus spécifiques comme la télévision peuvent être trouvés dans les articles intitulés "HDMAC coding for MAC compatible Broadcasting of HDTV signals" F.W.P. VREESWIJK and Dr. M.R.HAGHIRI - 3rd International workshop or HDTV - 30th August 1989 Torino et ITCoding of motion information on signal processing of HDTV" J.P. HENOT - 2rd International workshop on signal processing of HDTV - 29 february-2 march 1988 - L'Aquiia. Dans le premier cas, un codage des vecteurs mouvements ne représentait que de l'ordre de 10% du débit numérique total. Dans ces conditions, il ne nécessite pas, de ce fait, de développement spécifique. Les procédés utilisés sont alors les mêmes que pour le codage d'image et consistent à effectuer un codage à longueur variable adapté à des méthodes différentielles par rapport aux voisins du point courant ou par rapport à la moyenne du voisinage, ou encore adapté à des méthodes par entropie, cette dernière nécessitant le calcul d'un histogramme. Certaines solutions utilisent d'autre part, en plus une décomposition par un arbre de codage pour regrouper les zones homogènes de l'image. Dans ces différentes applications le coût binaire du champ de mouvement n'est pas la contrainte principale. Cependant les contraintes rencontrées en télévision haute définition ont nécessité de développer des méthodes de codage spécifiques pour les informations de déplacement. L'article de M. J. P. Henot précité utilise un codage pour utiliser la corrélation spatiale qui existe dans une image, l'article de MM. VREESWIJK et HAGHIRI décrit une utilisation d'un adressage relatif des vecteurs d'une image sur la précédente pour utiliser la corrélation temporelle. Malgré tout ces méthodes ne permettent pas de réguler le débit de transmission, ou même parfois, d'obtenir un débit inférieur à 1 Mbit/s avec une qualité d'image qui reste acceptable. Le but de l'invention est de pallier les inconvénients précités. A cet effet, l'invention a pour objet un procédé de codage à paramètres ajustables d'un champ de mouvement dans une séquence d'images animées caractérisé en ce qu'il consiste à décomposer chaque champ de mouvement de l'image suivant un arbre de codage et à identifier par un menu chaque vecteur mouvement présent dans l'image en accompagnant chaque vecteur de son mot de code. Cette décomposition est effectuée par macrobloc, c'est-à-dire en une partie de l'image ou en l'image entière (1 seul macrobloc). Par le fait qu'il met en oeuvre un menu de vecteurs le procédé selon l'invention a pour avantage qu'il offre la possibilité de réguler le débit, d'effectuer un codage par arbre de codage spatial et temporel en prenant en compte le mouvement sur 2 images consécutives. Il offre aussi la possibilité d'avoir des mots de code de longueur variable en fonction du nombre de vecteur par macrobloc, de limiter l'information à coder en supprimant les vecteurs les moins occurents au lieu d'analyser spatialement les informations, il permet d'avoir une borne maximale pour le débit, et enfin il permet de coder l'arbre comme un "vecteur" spécifique ou de coder l'arbre séparément. Le procédé selon l'invention a également pour avantage de pouvoir être utilisé sur tout dispositif de traitement d'images qui nécessite une réduction de débit d'information. ll peut s'appliquer notamment au codage de champs de mouvement en télévision haute définition, au codage d'image comme au codage numérique des signaux d'assistance de télévision du système de télévision connu sous la désignation HDMAC. Il permet à l'utilisateur de choisir suivant ses contraintes les paramètres du codage qui lui donneront le meilleur compromis -débit-qualité, et ce de façon dynamique (c'est-à-dire différemment suivant les images et en fonction du débit ou de la qualité obtenus) ou statique (c'est-à-dire une fois pour toutes, au départ). D'autres caractéristiques et avantages de l'invention apparaîtront ci-après à l'aide de la description qui suit faite en regard des dessins annexés qui représentent - Les figures 1A, 1B, 1C un procédé de décomposition d'images en blocs auquel est associé un arbre de décomposition pour le codage des blocs. - La figure 2 une composition des champs de mouvement à transmettre après application de la décomposition en arbre de codage des figures 1A, 1B et 1C. - La figure 3 une composition des mots de codes à transmettre lorsque le nombre de feuilles ajoutées au nombre de noeuds est supérieur à la taille de l'image à transmettre. - La figure 4 un mode d'assemblage du menu de vecteurs à transmettre en effectuant une décomposition en arbre de codage sur deux images successives. - La figure 5 une composition des champs de mouvement à transmettre après application de la décomposition en arbre de codage des figures lA, 1B et 1C pour le cas où l'arbre est codé séparément par les vecteurs. Pour pouvoir coder un champ de vecteurs mouvement de façon à obtenir pour la transmission des images un débit de mots de code aussi faible que possible, l'idée de l'invention est de regrouper ces informations afin d'obtenir un champ de vecteurs avec des blocs aussi grands que possible correspondant aux zones homogènes de l'image. Cela revient à déterminer un arbre de codage défini par les zones homogènes de l'image et à lier ce codage au codage d'un champ de mouvement en tenant compte de paramètres variables pour obtenir un bon compromis résolution-débit. La décomposition en arbre de codage consiste, comme le montre les figures lA, 1B et 1C, à découper une image en blocs homogènes de taille nxn les plus grands possibles, puis à associer au découpage obtenu un arbre (figure 1C) dont la racine R représente l'image, les noeuds (N1 à N7) > les blocs de taille 2nx2n, non homogènes qui sont décomposés en quatre sous blocs de taille nxn et les feuilles F1 à F25 des blocs non homogènes.On obtient ainsi dans le cas de l'exemple représenté aux figures lA, 1B, et IC, 4 niveaux de codes, un premier niveau (niveau 1) correspond à un bloc de taille 8x8 pixels formant la racine, un deuxième niveau (niveau 2) fait apparaître 4 blocs de taille 4x4 pixels, un troisième niveau (niveau 3) est composé de 9 blocs de 2x2 pixels et le quatrième niveau (niveau 4) est composé des pixels restants. Ainsi au lieu d'avoir une information pour chaque bloc élémentaire ou pixel, le procédé selon l'invention permet d'obtenir une découpe en zones où l'information à coder est identique (représentée par les feuilles). Dans le cas du codage d'un champ de mouvement l'information à coder est la valeur du vecteur déplacement obtenu à laquelle s'ajoute un codage des noeuds nécessaires à la construction de l'arbre au décodage sous la forme d'un "vecteur" spécifique. Dans l'hypothèse où le codage est limité à des vecteurs d'amplitude nominale +V dans les directions horizontale et verticale de l'image, le nombre de combinaisons possibles est alors de (2V+1)a et le nombre de bits nécessaires au codage est égal à log2 [ (2V+1)aJ A titre d'exemple, pour un vecteur d'amplitude +6 pixels (V = 6), le nombre de combinaisons est de 13 x 13 = 169 + 1 (noeud) = 170 et le nombre de bits par mot de code est alors égal à 8. Cependant, comme dans une image tous les vecteurs possibles ne sont pas forcément présents, une des caractéristiques de l'invention est de réaliser un menu de vecteurs contenant tous les vecteurs présents dans l'image. Dans ces conditions l'information à coder n'est plus la valeur du vecteur, mais un adressage relatif dans le menu. Ainsi en reprenant l'exemple précédent et en supposant que seulement 45 vecteurs différents sont présents sur les 169 possibles. Le nombre de combinaisons se réduit à 45 + 1 = 46 et le nombre de bits par mot de code se réduit à 6. Mais ceci oblige à transmettre les vecteurs de menu accompagnés de leurs mots de code comme le montre la configuration de la figure 2. Sur cette figure le champ Deb représente un mot de début contenant le nombre de vecteur (n) et le nombre de mot de code (nombre de feuille et de noeud = m). Les champs Vect. représentent les vecteurs présents dans l'image et les champs MC. représentent les mots de code représentant soit un noeud, soit le numéro d'un vecteur du menu. Cependant si la décomposition précédente des vecteurs mouvement en arbre de codage, tire avantage de la forte corrélation spatiale bidimensionnelle existante entre les vecteurs mouvement, elle ne tient pas compte de la corrélation temporelle qui existe d'une image à l'autre et qui à coup sûr peut permettre de réduire le débit. Ce problème est résolu par l'invention par une décomposition en arbre de codage qui est faite non plus sur une image mais sur deux images successives et qui conduit à n'utiliser qu'un seul arbre pour deux images. Un bloc homogène doit dans ces conditions l'être spatialement sur deux images consécutives avec le même vecteur. Le nombre de vecteurs du menu est alors égal au nombre de vecteurs différents de l'image courante et de l'image précédente ou suivante et le nombre de combinaisons est égal au nombre de vecteurs différents de l'image courante multiplié par le nombre de vecteurs différents de l'images précédente ou suivante. Cependant, lorsque pour une image de taille nxn le nombre de feuilles ajoutées au nombre de noeuds devient supérieur au produit nxn, le codage au moyen de la décomposition en arbre nta alors plus d'intérêt et dans ce cas les mots de code sont transmis directement suivant l'organisation de la figure 3, où les mots de codes MC. ne se rapportent qu'à l'indice du vecteur correspondant dans le menu, aucun noeud n'étant pris en considération et il y a autant de MC. que de pixels dans l'image. Naturellement ce cas de figure correspond à un débit maximum. Dans le cas où la décomposition est effectuée sur 2 images consécutives le champ DEB contient le nombre N1 de vecteurs de l'image courante, le nombre N2 de vecteurs de l'image précédente (ou suivante), le nombre de vecteurs différents (N) dans l'image courante et dans l'image précédente (ou suivante) et le nombre de mots de codes MC. Le menu des vecteurs VECT1 ... VECTn est alors transmis de la façon représentée à la figure 4 en tenant compte des vecteurs semblables dans les vecteurs N1 et N2 qu'il n'est pas utile de transmettre deux fois dans le menu. Comme dans les applications nécessitant un codage, le débit maximal admissible est en général fixé, le procédé selon l'invention a pour avantage qu'il permet le codage de n'importe quel champ de mouvement quelque soit le débit fixé. Cependant comme il existe une dégradation de qualité lorsque les débits fixés sont de plus en plus faibles, un bon compromis entre débit et qualité peut être obtenu en adaptant la taille des blocs. Par exemple, au lieu de descendre dans la décomposition de l'arbre de codage jusqu'au pixel il est toujours possible de s'arrêter à une taille de blocs de 2x2 ou 4x4 ... etc, avec un vecteur associé à chaque taille élémentaire, le débit dans ces conditions devient plus faible. Il est aussi possible de régler l'amplitude des vecteurs. Dans ce cas le débit peut être réduit très sensiblement et seul le menu des vecteurs est à modifier du fait de l'adressage relatif. Une autre méthode de réduction du débit peut aussi consister à limiter le nombre de vecteurs par image et par conséquent le nombre de bits par mot de code mais cependant ce procédé revient à interdire certains vecteurs dans l'image. Toutefois en découpant l'image en macroblocs de taffle par exemple égale à i d'image et en calculant un arbre sur cha cun de ces blocs de manière à obtenir plusieurs menus par image, le nombre de vecteurs peut être réduit dans chaque macrobloc tout en conservant pour toute l'image la possibilité d'avoir tous les vecteurs possibles. Pour éviter des dégradations importantes du champ de mouvement il est important de réaliser un compromis entre la taille des macroblocs et le nombre de vecteurs maximal autorisé à l'intérieur de ces blocs. Ces paramètres sont déterminables à l'initialisation du procédé et peuvent naturellement aussi être modifiés en cours de transmission pour assurer une transmission à débit constant. Dans ce dernier cas le codage du champ de mouvement peut avoir lieu dans un premier temps sans restriction et peut ensuite être modifié seulement lorsque le débit optimum est dépassé par action sur certains paramètres pour rester dans le débit maximal fixé. Le procédé selon l'invention est avantageusement applicable au codage des images de télévision du standard HDMAC. Dans ce cas en effet le codage a lieu sur la base de blocs 16x16 pixels toutes les 40 ms en considérant chaque fois deux trames entrelacées. Dans ce type de codage, chaque bloc est défini suivant trois modes, un mode 80 ms pour les blocs fixes pour lesquels le mouvement est nul, un mode 40 ms pour les blocs en mouvement d'amplitude inférieure à 6 pixels et un mode 20 ms pour les blocs en mouvement supérieur à i 6 pixels. Seul le mode 40 ms qui utilise des vecteurs déplacements est compensé en mouvement et sur 80 ms correspondant à la durée de deux images entrelacées seules les combinaisons suivantes sont autorisées (80-80, 40-40, 40-20, 20-40, 20-20). Le procédé de codage selon l'invention prend en compte cette réduction du nombre de combinaisons possibles, le mode 40 ms n'utilisant la compensation de mouvement qu'une trame sur deux.L'information à coder par blocs 16x16 est celle du mode obtenu avec le vecteur éventuellement associé avec un débit maximal de I Mbit/s. Les paramètres de définition de l'arbre de codage sont alors - taille des blocs élémentaires: 16x16 pixels - amplitude des vecteurs : i 6 pixels - macrobloc choisi de taille: 128x128 pixels - taille des images HD : 1440x1152 pixels - débit maximal autorisé : 1 Mbit/s - information codée toutes les 80 ms par bloc 16x16. Le nombre de combinaisons est défini pour chaque combinaison du mode comme suit 80-80 --- > 1 combinaison 40-40 --- > NlxNz combinaisons 40-20 + N1 combinaisons 20-40 ~ N2 combinaisons 20-20 - > 1 combinaison où N1 désigne le nombre de vecteurs dans la première image par bloc de 128x128 pixels, et N2 désigne le nombre de vecteurs dans la deuxième image par bloc de 128x128 pixels. Pour N1max = N2max = 64 le nombre de possibilités maximales (incluant un noeud) est égal à 3 + N1 + N2 + N1.N2 = 4227 et peut être codé par mots de code de 13 bits. Comme dans la norme HDMAC seuls 1408 points/ligne et 1152 lignes sont transmis le nombre de macroblocs de taille 128x128 à considérer est égal à 99. En retournant aux figures 2, 3 et 4 le mot de début DEB de chaque macrobloc contient dans ces conditions pour chaque image 1 et 2 successive N1 vecteurs de l'image 1 (N1 compris entre 0 et 64) N2 vecteurs de l'image 2 (N2 compris entre 0 et 64) N vecteurs différents dans les images 1 et 2 (N étant égal au maximum de la somme des N1 plus N2 vecteurs). et n mots de codes (n compris entre 1 et 64). Soit un maximum total de N1 x N2 x N x n = 34881600 combinaisons possibles représentables par un mot de code DEB de 26 bits. (Ces informations étant nécessaires au décodage pour retrouver les mots de code parmi le flux binaire). Les vecteurs d'amplitude t6 pixels nécessitent 8 bits pour être codés. Le débit binaire maximal théorique est égal dans ces conditions au produit du nombre de macroblocs transmis (99) par la somme des bits composant le mot DEB (26), des bits composant le menu de vecteur (2x64x8), et des bits de mots de code (64x13) le résultat du produit obtenu étant à nouveau multiplié par la fréquence 12,5 Hz correspondant à une transmission de ce paquet de bits toutes les 80 ms. Dans l'application HDMAC considérée le débit qui en résulte est de 2328975 bits/s. Pour entrer dans le débit de 1 M bit/s le nombre de vecteurs doit être limité à 13 par macrobloc (sur les 64 possibles). Le débit obtenu est alors de 99x [ 19+(13x2x8) +(64x8) ] x12,5 = 914513 bits/s En considérant non plus des vecteurs d'amplitude i 6 pixels mais des vecteurs de + 14 dans la direction horizontale de l'image et de + 8 dans la direction verticale, le débit maximal devient 99x [ 19+(13x2x9)+(64x8)lx12,5 = 946687,5 bits/s. Naturellement au lieu de choisir de limiter comme précédemment le nombre de vecteurs à 13 sur toutes les images il est encore possible d'opérer cette limitation de façon dynamique, en transmettant par exemple tous les vecteurs possibles si le débit est inférieur à 1 M bit/s et en limitant par contre le nombre de vecteurs jusqu'à ce que le débit soit inférieur à 1 M bit/s. La limitation à 13 des vecteurs peut s'obtenir en prenant que les 13 les plus occurents par macrobloc et en assignant le plus proche vecteur parmi les 13 vecteurs supprimés. D'autre part la taille normal des blocs qui est 16x16 dans le codage HDMAC peut éventuellement être réduite car le procédé de l'invention peut toujours être appliqué indépendamment de la taille des blocs plus grande ou plus petite choisie. Afin de réduire le débit, il est préférable de non plus coder un noeud comme un "vecteur" spécifique (afin de reconstruire l'arbre au décodage) mais de transmettre un champ "ARBRE" tel que représenté à la figure 5, qui représente l'arbre de code. Chaque bit de ce champ indique un noeud ou une feuille, le premier bit indique l'état de la racine (bloc de taille nxn, feuille ou noeud), le deuxième, le troisième, le quatrième et le cinquième l'état des. 4 sous-blocs de tarne n/2,xn/2, etc... jusqu a l'avant dernier niveau possible.Ainsi pour les figures lA, 1B, 1C, le mot "ARBRE" serait 1 0111 0000 0011 0000 0110 avec 1 2 R 0111 - > F1 N1 N2 N3 0000 0011 r F1 E3 N4 N5 0000 p F F4 F5 F6 0110 > F8 N6 N7 Fg et 1 = noeud 0 = feuille. Les mots de code (MCi) ne représentent plus qu'une des combinaisons mode/vecteur. Ainsi pour l'application HDMAC, on a quatre niveaux (128, 64, 72, 16) le mot "ARBRE" est donc un 21 bits. Le gain en débit est obtenu par le fait que précédemment un noeud était codé avec autant de bit qu'un vecteur (soit 8 bits maximum). En supposant que l'on ait seulement 5 noeuds (sur les 21 possibles), il faudrait 8x5 = 40 bits pour l'arbre. Avec la présente méthode seulement 21 sont nécessaires. Au maximum cette méthode peut donner un gain de [ 21(nombre de noeuds)x8 ] - [ 21 ] = 147 bits par macrobloc avec 8 bits par mot de code soit 147x99x12,5=181912,5 bits/s De plus avec le codage séparé de l'arbre, le cas représenté par la figure 3 peut être utilisé pour le cas où l'arbre est complètement décomposé. On garantit ainsi le même débit maximum que précédemment (le mot "ARBRE" n'est pas transmis). REVENDICATIONS 1. Procédé de codage à paramètres ajustables d'un champ de mouvement dans une séquence d'images animées caractérisé en ce qu'il consiste à décomposer chaque champ de mouvement de l'image suivant un arbre de codage et à identifier par un menu chaque vecteur mouvement (Vecti) présent dans l'image en accompagnant chaque vecteur (Vecti) de son mot de code (MCi). 2. Procédé selon la revendication 1 caractérisé en ce que la décomposition de chaque champ de mouvement a lieu à l'intérieur de blocs (nxn) de dimension déterminée de l'image. 3. Procédé selon la revendication 2 caractérisé en ce que la taille des blocs est ajustable. 4. Procédé selon la revendication 3 caractérisé en ce qu'il consiste à ajuster la longueur des vecteurs mouvements. 5. Procédé selon l'une quelconque des revendications 1 à 4 caractérisé en ce qu'il consiste à découper l'image en macroblocs de dimension déterminée et à calculer un arbre de codage sur chacun des blocs de façon à obtenir plusieurs menus de vecteurs par image. 6. Procédé selon l'une quelconque des revendications 1 à 5 caractérisé en ce que la décomposition en arbre de codage a lieu sur deux images successives. 7. Procédé selon l'une quelconque des revendications 1 à 6 caractérisé en ce qu'il consiste à limiter le nombre de vecteurs en supprimant les vecteurs les moins occurents. 8. Procédé selon la revendication 1 caractérisé en ce que l'arbre peut être décrit soit comme un vecteur spécifique, soit transmis séparément.