Brevet FR2768006A1 — publié le 19990305

La présente invention concerne un procédé de quantifi- caion d'un signal à échantillons multidimensionnels compor- tant au moins un échantillon multidimensionnel de dimension N donnée, le ou chaque échantillon comportant N composantes, le procédé comportant les étapes consistant à: a) transformer, pour chaque échantillon, chaque com- posante en un ensemble de coefficients transformés dans N bases de numération connues; b) réunir les ensembles de coefficients transformés; et c) procéder à une quantification progressive de la réunion des ensembles de coefficients transformés. Le procédé est destiné notamment à la compression de signaux représentatifs d'images en couleurs, notamment de té- lévision, de sons stéréophoniques ou de données résultant de transformées, telles que des transformées de Fourier, des transformées en cosinus discrètes ou des transformées en onde- lettes. Dans ce contexte, chaque signal est formé d'un ensem- ble d'échantillons multidimensionnels transformés ou non de dimension N donnée. Ainsi, chaque échantillon comporte N com- posantes. Dans le cas de la compression d'un ensemble de signaux à échantillons multidimensionnels, les schémas de compression actuels considèrent chaque composante du signal comme un sous- signal indépendant. Chaque sous-signal est d'abord transformé puis quantifié indépendamment des autres sous-signaux trans- formés du même signal à échantillons multidimensionnels. Par exemple, les trois plans de couleurs (rouge, vert, bleu) d'une image de télévision en couleurs sont habituelle- ment quantifiés indépendamment les uns des autres. Une méthode de quantification est par exemple décrite dans l'article de J. Shapiro "Embedded image Coding Using Ze- rotrees of Wavelet Coefficients", (IEEE Trans. on Signal Pro- cessing, vol. 41, n' 12, Dec. 1993). Les travaux de J. Shapiro concernent un procédé de quantification progressive intégrée d'images à plusieurs ni- veaux de gris ayant subi une transformation en ondelettes. La quantification proposée autorise une transmission progressive des données comprimées. La quantification progres- sive permet qu'une information dégradée puisse être partielle- ment rétablie à partir de la trame de bits comprimée seulement partiellement reçue. Ainsi, par un procédé de quantification progressive, la trame de bits obtenue à un haut niveau de compression est le début de la trame de bits obtenue à un niveau de compres- sion plus faible. Autrement dit, augmenter le niveau de com- pression revient à tronquer la trame de bits pour ne converver que le début de celle-ci. L'algorithme de J. Shapiro transposé pour le traite- ment d'images en couleurs, consistant à traiter successivement chaque couleur, ne tient pas compte des corrélations entre les couleurs de sorte que les performances de compression sont af- faiblis. Afin de remédier à ces problèmes, A. Said et W.A. Pearlman ont proposé dans l'article "A new Fast and Efficient Image Codec Based on Set Partitioning In Hierachical Trees" (IEEE trans. on circuits & Systems for Video Technology, vol. 6, n' 3, Jun. 1996) des solutions visant notamment à transfor- mer préalablement les variables caractéristiques correspondant à chacune des couleurs en décorrelant celles-ci, notamment grâce à une méthode d'analyse en composantes principales. Se- lon cette méthode, les trois couleurs sont préalablement transformées en d'une part une composante de luminance, et d'autre part deux composantes de chrominance. A. Said et W.A. Pearlman ont proposé pour cela une transformation de Karuhnen- Lowe appliquée sur les différentes bandes pour assurer la dé- corrélation de celles-ci. Toutefois, le recours à une décorrélation nécessite une transformation supplémentaire relativement longue à ef- fectuer. De plus, cette opération est non réversible à cause des problèmes d'arrondis, ce qui nuit à la qualité de l'image reconstituée, interdisant son utilisation dans cer- tains domaines comme le domaine médical pour des raisons ré- glementaires. En outre, suivant ces méthodes, les trames de don- nées comportent successivement les informations relatives à chacune des couleurs, ou si le signal a été préalablement transformé à la luminance puis à la chrominance. Ainsi, la trame doit être transmise complètement afin de permettre une reconstitution satisfaisante de l'image. En effet, toute transmission partielle de seulement une trame tronquée ne permet de disposer que des premières informations qui sont à elles seules insuffisantes pour re- constituer une image correcte. Le risque existe alors de perdre toutes les informations d'un plan de couleur, ou, si le signal a été préalablement transformé, certaines informa- tions de chrominance. Pour résoudre ce problème, A. Said et W.A. Pearlman ont proposé de mélanger les composantes formées des varia- bles caractéristiques transformées en entrelaçant celles-ci suivant un tri particulier avant de procéder à la quantifi- cation des composantes ainsi réunies. Toutefois, cette méthode est relativement longue à utiliser puisqu'elle nécessite la mise en oeuvre d'un tri particulier. De plus, malgré l'entrelacement des composantes, la quantification s'effectuant sur chaque coefficient scalaire transformé indépendamment de la composante à laquelle il correspond, une trame de données tronquée n'est pas toujours porteuse du même nombre d'informations en ce qui concerne toutes les composantes représentatives de l'image. Ainsi, ces méthodes ne sont pas complètement satis- faisantes. L'invention a pour but de proposer un procédé de quantification d'un signal à échantillons multidimensionnels tenant compte de la forte dépendance entre les composantes des échantillons multidimensionnels, tout en permettant une exploitation efficace d'une trame tronquée du signal quanti- fié. A cet effet, l'invention a pour objet un procédé de quantification d'un signal à échantillons multidimensionnels comportant au moins un échantillon multidimensionnel de di- mension N donnée, le ou chaque échantillon comportant N com- posantes, le procédé comportant les étapes consistant à: a) transformer, pour chaque échantillon, chaque com- posante en un ensemble de coefficients transformés dans N bases de numération connues; b) réunir les ensembles de coefficients transformés; et c) procéder à une quantification progressive de la réunion des ensembles de coefficients transformés; caractérisé en ce que pour la réunion des ensembles des coefficients transformés, il comporte les deux étapes successives suivan- tes: A) créer, pour le ou chaque échantillon multidimen- sionnel, un vecteur dont les coefficients sont des N-uplets formés par les coefficients transformés de même rang i dans les N bases de transformation des variables caractéristi- ques; et B) réunir les vecteurs de N-uplets; le procédé comportant enfin la mise en oeuvre d'une quantification progressive de la réunion des vecteurs de N- uplets, la quantification progressive s'effectuant sur les N-uplets. Suivant des modes particuliers de réalisation, le procédé peut comporter l'une ou plusieurs des caractéristi- ques suivantes: -la transformation de chaque composante de chaque échantillon en un ensemble de coefficients transformés dans N bases de numération connues s'effectue par une transforma- tion directe de chaque échantillon dans une base de numéra- tion dont les vecteurs de base sont des N-uplets; - la réunion des vecteurs de N-uplets s'effectue suivant l'ordre des échantillons multidimensionnels dans le signal; - l'étape de quantification progressive comporte une étape de codage conditionnel de certains éléments d'un même N-uplet en fonction des autres éléments du N-uplet considé- ré; - les échantillons multidimensionnels sont obtenus par la transformation préliminaire d'un ensemble d'informa- tions multidimensionnelles comportant chacune N variables caractéristiques, la transformation préliminaire effectuée sur les informations multidimensionnelles étant constituée d'un ensemble de transformations indépendantes opérées cha- cune sur l'un des N plans constitués des variables caracté- ristiques de même rang des informations multidimensionnelles et - le signal est un signal représentatif d'une image numérique en couleurs. L'invention sera mieux comprise à la lecture de la description qui va suivre, donnée uniquement à titre d'exem- ple et faite en se référant aux dessins sur lesquels: - la figure 1 est un diagramme schématique montrant le schéma général de la compression et de la décompression d'une image; et - la figure 2 est une vue schématique d'un élément d'image de 4 pixels sur 4 pixels sur lequel est représenté un sens de parcours de celui-ci pour sa quantification. La mise en oeuvre du procédé va maintenant être dé- crite sur l'exemple de la compression d'un signal à échan- tillons tri-dimensionnels représentatif d'un élément d'une image de télévision en couleurs de 4 pixels sur 4 pixels. Sur la figure 1 est modélisé le schéma général de la compression d'une image. Comme connu en soi, pour comprimer une image de grande taille, on décompose d'abord celle-ci, dans une étape O, en un ensemble de blocs de taille réduite prédéterminée, par exemple de 4 pixels sur 4 pixels, comme représenté sur la figure 2. Le procédé de compression est ensuite appliqué sur les blocs de taille réduite qui forment des éléments d'image. Dans l'exemple décrit ici, le signal comporte 16 in- formations multidimensionnelles relatives chacune à un pixel. Les informations sont tri-dimensionnelles et compor- tent ainsi trois variables caractéristiques, notées R, G, B, correspondant chacune à une des trois couleurs (rouge, vert, bleu). Avant de procéder à la quantification proprement dite, on effectue à l'étape 1 une transformation prélimi- naire des variables caractéristiques de même rang de l'en- semble des informations multidimensionnelles. L'ensemble des variables caractéristiques de même rang définit un plan cor- respondant, dans le cas considéré, à l'une des trois ou- leurs. Ainsi, à l'étape 1, on procède à une transformation de chacun des plans de couleur. En l'espèce, on effectue trois transformations distinctes appliquées chacune sur un plan de couleur. On obtient ainsi, pour chaque pixel, une information multidimensionnelle transformée, appelée échan- tillon et notée (R, G, B) pour chaque pixel. De nombreux procédés de transformation peuvent être utilisés. Les transformées efficacement utilisées pour la compression d'image appartiennent à deux groupes principaux, à savoir d'une part les transformées "basées fréquence" qui dérivent de la transformée de Fourier et de ses approxima- tions et d'autre part les transformées "temps-fréquence", dont les représentants les plus connus sont les transformés en ondelettes qui prennent en compte la non stationnarité du signal. Après mise en oeuvre de la transformation prélimi- naire, on procède à l'étape de quantification proprement dite notée 2. Celle-ci comporte d'abord une étape 2A de transfor- mation consistant à transformer, pour chaque échantillon, ici une information relative à un pixel transformée dans un plan couleur, successivement chaque composante, ici l'une des trois couleurs transformées, en un ensemble de coeffi- cients transformés dans trois bases de numération connues, chacune définie pour une composante. L'étape 2A de transformation conduit ainsi à expri- A ^ A mer, pour chaque échantillon (R, G, B), les trois composan- AA\ tes R, G, B, dans une base de numération de dimension donnée pour chaque composante. Dans l'exemple décrit, les bases as- sociées aux trois composantes sont supposées de dimension k = 8, les coefficients transformés étant des nombres binai- res. Ainsi, les composantes représentatives des trois couleurs s'écrivent sous la forme: R = ú 2iri i=0 A 7 G = E 21gi A 7 B = 27bi i=0 avec (ri, gi, bi)({0,1}3 pour iE{0;1;2;3;4;5;6;7}. Pour chaque pixel, on construit alors un vecteur de dimension k - 8 dont les coefficients sont des tri-uplets formés par les coefficients transformés (ri, gi, bu) de même rang i (avec i appartenant à {0;1;2;3; 4;5;6;7}). Dans la pratique, pour la transformation de chaque composante de chaque échantillon (R, G, B) en un ensemble de coefficients transformés dans les trois bases de numération connues, on effectue une transformation directe de chaque échantillon (R, G, B) dans une unique base de numération, de dimension 8 dans l'exemple considéré. Dans cette base de nu- mération, les coefficients transformés sont des tri-uplets. Ainsi, dans cette base, chaque échantillon s'écrit sous la forme: (R, G, B) = E (ri, gi, bi)2 i-0O Dans le procédé selon l'invention, les vecteurs de tri-uplets ainsi formés sont réunis suivant l'ordre des échantillons multidimensionnels dans le signal pour former une matrice de tri-uplets correspondant aux coefficients transformés du signal à échantillons multidimensionnels transformés. Cet ordre de parcours correspond par exemple à celui représenté sur la figure 2. Un exemple d'une telle matrice est représenté ci- dessous sous forme de tableau. 0 1 2 3 4 5 6 7 8 9 A B C D E F RGB RGB RGB R RGB RGB R R RGB RGB RGB RGB RGB RGB RGB RGB RGB 7 101000 000 000 0 0 000 000 000 000 000 000 000 000 000 000 000 6 110 101 100 000 000 000 OO 000 000 000 000 000 000 000 000 1 0 00000 000 000 000 000 000 000 000 000 '11 010Ol 111 1 00 OOOàà àà -OOO O O O O O O O 4 1 111 010 110 011 111 101 000 000 00O0 000 000 000 000 000 001 101 001 110001 110 1 110 100 100 000 000 000 000 000 2 100 101 001 100 010 001 101 110 001 011 011 101 100 000 010 000 1 111 010 001 100 011 101 010 101 010 100 010 110 011 111 011 000 0 111 101 100 010 011 010 001 100 010 101 010 100 1 011 101 111 Ainsi, dans ce tableau, les coefficients transformés associés aux vecteurs de base sont numérotés de 7 à 0 du plus significatif au moins significatif et sont indiqués en ligne. Les seize pixels de l'élément d'image considéré sont représentés en colonne et sont numérotés en hexadécimal de O à F. Chaque pixel est ainsi représenté par un vecteur de huit tri-uplets. Le premier élément de chaque tri-uplet cor- respond au coefficient transformé du rang considéré de la première composante, à savoir le rouge dans l'exemple consi- déré. Les second et troisième éléments de chaque tri-uplet correspondent respectivement aux coefficients transformés des seconde et troisième composantes, à savoir le vert et le bleu respectivement. Selon l'invention, on procède ensuite à la quantifi- cation progressive des informations regroupées dans le ta- bleau 1. La quantification progressive s'effectue directe- ment sur les tri-uplets. Dans le cadre du schéma général représenté sur la figure 1, l'étape de quantification progressive notée 2B correspond à la fois à l'étape habituelle de quantification, et à l'étape habituelle de codage. En effet, on entend habi- tuellement par quantification, le processus visant à suppri- mer les coefficients transformés qui sont porteurs de peu d'informations et qui peuvent être négligés sans perte im- portante de qualité de l'image. Le codage quant à lui con- siste, dans sa forme habituelle, à retranscrire les coeffi- cients transformés quantifiés sous une forme réduisant la longueur de la trame et adaptée pour le traitement ultérieur de l'image comprimée. En l'espèce, la quantification pro- gressive, décrite par exemple par J. Shapiro, permet de pro- céder simultanément aux opérations de quantification et de codage. La quantification progressive s'effectue suivant un ordre de parcours de l'élément d'image de seize pixels. Ce parcours peut être de tout type adapté et par exemple sui- vant l'ordre représenté sur la figure 2. Ainsi, en notant E le symbole d'échappement, le si- gnal comprimé obtenu par le procédé selon l'invention, n'in- tégrant que les trois premiers niveaux de poids les plus forts, s'exprime sous la forme: 101E/110101100E/lllO10011111100E On comprend qu'avec un tel procédé, toute trame tronquée comporte obligatoirement l'ensemble des informa- tions relatives aux trois couleurs pour le niveau de quanti- fication retenu. En particulier, le nombre de bits pour cha- que niveau sera obligatoirement un multiple de trois. En effet, la quantification étant effectuée directe- ment sur les tri-uplets, il est sûr que toute troncature de la trame de données contiendra des nombres analogues d'1élé- ments représentatifs de chaque couleur. A partir du signal comprimé avec le niveau de com- pression retenu, on procède, à l'étape 3, à une "déquantification progressive" du signal représentatif de l'image. Avec les schémas habituellement retenus, cette "déquantification progressive" consiste tout d'abord en une étape de "déquantification" notée 3A, suivie d'une étape de transformation inverse notée 3B, correspondant à l'inverse de l'étape 2A. Le procédé comporte ensuite, à l'étape 4, une nou- velle étape de transformation inverse correspondant à l'opé- ration inverse de la transformée préliminaire opérée à l'étape 1. Enfin, afin de reconstituer l'image décomprimée com- plète, les éléments d'image formés des blocs de taille ré- duire sont réassemblés les uns aux autres lors de l'étape finale notée 5 sur la figure 1. Suivant une variante de mise en oeuvre du procédé selon l'invention, l'étape 2B de quantification peut être menée différemment et peut notamment être effectuée de ma- nière conditionnelle. Dans cette variante, lors de la quantification d'un tri-uplet donné, on laisse inchangé le premier coefficient transformé puis, pour les deux coefficients suivants, on code ceux-ci suivant un codage conditionnel en fonction du codage du premier coefficient transformé du tri-uplet consi- déré. Ainsi, pour chaque tri-uplet, les second et troi- sième coefficients quantifiés sont obtenus à partir de pro- babilités conditionnelles relatives au premier coefficient du tri-uplet considéré. Par ailleurs, l'étape 1 de transformation préalable est facultative et peut être omise. Le procédé de quantifi- cation selon l'invention est alors mis en oeuvre directement sur les échantillons multidimensionnels dont les composantes ne sont pas des transformées d'informations multidimension- nelles mais les informations multidimensionnelles elles- mêmes. Il va maintenant être décrit plus généralement le procédé de quantification selon l'invention, à partir d'un exemple d'algorithme présenté en pseudo-code. Considérant un signal formé d'un ensemble d'échan- tillons C. Chaque échantillon C est constitué de N composan- tes Co,..., CN_1. Pour réaliser la quantification progressive on se donne deux relations d'ordre compatibles: - un ordre (total) de parcours des échantillons (noté x largeur d'abord). En désignant de la manière suivante les coefficients d'une matrice 4x4 représentative d'un élément d'image de 4 pixels sur 4 pixels: (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) l'ordre correspondant au codage "zerotree" est défi- ni par: pour (i,j) différent de (0,0) (2i,2j)"(i,J) (2i+1, 2j) (0,0)(0,1)(0,2)(0,3)(1,2)(1,3)(1,0)(2,0)(2,1)(3,0)(3,1)(1,1) (2,2)(2,3)(3,2)(3,3) - Parcours en largeur d'abord * (0,0)(0,1)(1,0)(1,1)(0,2)(0,3)(1,2)(1,3)(2,0)(2,1)(3,0)(3,1) (2,2)(2,3)(3,2)(3,3) La base de numération de RN utilisée ici est la base classique des puissances de 2, les coefficients de la décom- position (coefficients transformés) associés à chaque vec- teur de la base sont des N-uplets. De plus, on dit qu'un échantillon est significatif par rapport à un seuil S si une de ses composantes est supé- rieure ou égale (en valeur absolue) à S. Pour le codage d'un échantillon, deux cas sont possibles: si l'échantillon n'a jamais été codé l'ensemble des symboles est {-1, 0,1N}" plus le symbole d'échappement E si l'échantillon a déjà été codé l'ensemble des symboles est {0, 1}N Si tous les échantillons inférieurs à C (pour l'ordre pour tous les échantillons C par ordre de parcours décrois- sant (pour sinon si tous les échantillons infé- rieurs à P (pour ") sont non signi- ficatifs par rapport à 2P on code le symbole d'échappement E sinon (en variante) on code le symbole (0,..., O) sinon pour chacune des composantes de l'é- chantillon si la composante est supérieure ou égale à 2P on pose c, =1 sinon si composante est infé- rieure ou égale à -2P on pose cn -1 sinon on pose cn - O on code le symbole (c0,...,cnl) dif- férent de (O,...,O) sinon pour chacune des composantes de l'échantil- lon on pose Cn = la valeur du p" bit de la valeur absolue de la composante on code le symbole (c0,...,c_..1) Plus généralement, le procédé selon l'invention peut se définir de la manière suivante, les échantillons C étant des éléments de RN(avec R ensemble des nombres réels). On définit une base de numération dans RN par les éléments suivants: une suite B strictement croissante de réels Bk (kEZ avec Z ensemble des entiers relatifs)(en général, Bk-2k) 20. un ensemble fini S d'éléments de RN comprenant le vecteur nul, ces éléments sont nommés les chiffres (en général on prend S = {-1, 0, 1}N ou {(O, 1lN) B et S doivent vérifier la propriété suivante: tout vecteur X de RN peut s'écrire (de façon unique ou non) sous la forme X = E xkBk (xkES) kEZ On dit qu'une écriture X - ú xkBk de X est minimale k On dit qu'un vecteur X est non significatif par rap- port à Bk s'il existe une écriture minimale de X avec xi-O pour iÄk. On suppose que tous les échantillons sont écrits sous une forme minimale et on détermine K, la plus grande valeur de k nécessaire pour écrire tous les échantillons. L'algorithme du procédé selon l'invention s'écrit alors sous la forme: pour k décroissant de K à 0 pour tous les échantillons par ordre de parcours décroissant (pour s'il est inférieur (pour ") à un échan- tillon pour lequel on a codé un symbole d'échappement (une racine de zéros) on passe à l'échantillon suivant sinon si tous les échantillons inférieurs à P(pour ") sont non significatifs par rapport à Bk on code le symbole d'échappement E sinon (en variante) on code le symbole (chiffre) corres- pondant au vecteur nul sinon on code le chiffre Pk sinon on code le chiffre Pk. REVENDICATIONS 1. Procédé de quantification d'un signal à échan- tillons multidimensionnels comportant au moins un échan- tillon multidimensionnel de dimension N donnée, le ou chaque A, A échantillon comportant N composantes (R, G, B), le procédé comportant les étapes consistant à: a) transformer, pour chaque échantillon, chaque com- posante (R, G, B) en un ensemble de coefficients transformés (ri, gi, bi) dans N bases de numération connues; b) réunir les ensembles de coefficients transformés; et c) procéder à une quantification progressive de la réunion des ensembles de coefficients transformés; caractérisé en ce que pour la réunion des ensembles des coefficients transformés, il comporte les deux étapes successives suivan- tes: A) créer, pour le ou chaque échantillon multidimen- sionnel, un vecteur dont les coefficients sont des N-uplets formés par les coefficients transformés (ri, gi, bi) de même rang i dans les N bases de transformation des variables ca- ractéristiques; et B) réunir les vecteurs de N-uplets; le procédé comportant enfin la mise en oeuvre d'une quantification progressive de la réunion des vecteurs de N- uplets, la quantification progressive s'effectuant sur les N-uplets. 2. Procédé selon la revendication 1, caractérisé en ce que la transformation de chaque composante de chaque échantillon (R, G, B) en un ensemble de coefficients trans- formés (ri, gi, bl) dans N bases de numération connues s'ef- fectue par une transformation directe de chaque échantillon (R, G, B) dans une base de numération dont les vecteurs de base sont des N-uplets. 3. Procédé selon la revendication 1 ou 2, caractéri- sé en ce que la réunion des vecteurs de N-uplets s'effectue suivant l'ordre des échantillons multidimensionnels dans le signal. 4.- Procédé selon l'une quelconque des revendica- tions précédentes, caractérisé en ce que l'étape de quanti- fication progressive comporte une étape de codage condition- nel de certains éléments d'un même N-uplet en fonction des autres éléments du N-uplet considéré. 5.- Procédé selon l'une quelconque des revendica- tions précédentes, caractérisé en ce que les échantillons multidimensionnels (R, G, B) sont obtenus par la transforma- tion préliminaire d'un ensemble d'informations multidimen- sionnelles (R, G, B) comportant chacune N variables caracté- ristiques, la transformation préliminaire effectuée sur les informations multidimensionnelles (R, G, B) étant constituée d'un ensemble de transformations indépendantes opérées cha- cune sur l'un des N plans constitués des variables caracté- ristiques de même rang des informations multidimensionnel- les. 6.- Procédé selon l'une quelconque des revendica- tions précédentes, caractérisé en ce que le signal est un signal représentatif d'une image numérique en couleurs.