Brevet FR2643477A1 — publié le 19900824

i Procédé de détermination de transformée en cosinus discrète L'invention a pour objet un procédé et un dispositif de détermination de transformée en cosinus discrète en temps réel, & partir de données numériques. Elle trouve une application particulièrement importante, bien que non exclusive, dans le domaine du codage d'image: la tendance actuelle, notamment pour la transmission d'images sur le réseau téléphonique, semble s'orienter vers l'utilisation de la transformée en cosinus discrète (en abrégé TCD) bidimensionnelle de longueur 8 x 8. Pour d'autres applications, la TCD bidimensionnelle 16 x 16 semble préférable. Un procédé de détermination de TCD est d'autant plus satisfaisant qu'il remplit mieux deux conditions: le volume de calcul requis doit être aussi faible que possible, afin de réduire la complexité du logiciel, dans le cas d'une réalisation programmée, ou la surface de semi-conducteur requise, dans le cas d'une réalisation câblée. Le procédé doit avoir des propriétés de récursivité permettant de réaliser, avec le même matériel de base, des TCD de tailles différentes, et de régularité facilitant la réalisation physique. Enfin, ces résultats doivent être atteints tout en respectant les normes d'erreur maximum admissible par rapport à une référence: cette condition doit impéra- tivement être remplie pour qu'un codeur et un décodeur utilisant, l'un le procédé proposé, l'autre un procédé différent, restent compatibles. A l'heure actuelle, l'algorithme qui semble le plus favorable du point de vue du nombre d'opérations nécessaires semble celui de Toshiba (JP-A-6261 159) qui permet de calculer une TCD de longueur 8 au prix de onze multiplications et de vingt-neuf additions. Mais l'algo- rithme correspondant ne présente pas la récursivité et la régularité souhaitables. - On connaît également un procédé, décrit dans l'article "A new algorithm to compute the discrete cosine transform" de Byeong Gi Lee, IEEE Transactions on Accoustic Speech and Signal Processing, Vol. ASSP-32, No. 6, Décembre 1984, p. 1243 qui a les propriétés souhaitables de récursivité et de régularité, mais exige davantage d'opérations que l'algorithme Toshiba: une TDC de longueur 8 exige treize multiplications et vingt-neuf additions. Bien que la différence avec l'algorithme de Toshiba soit faible, elle est décisive lorsque la vitesse et la complexité constituent des facteurs essentiels, et en particulier - lorsqu'il est nécessaire de mettre en oeuvre, en temps réel, une TCD bidimensionnelle. Ce cas est notamment celui de logiciels de compression d'image en temps réel, o on recherche impérativement un nombre minimum d'instruc- tions, et de systèmes électroniques de compression d'image, o l'on recherche un minimum de composants, réduisant la surface de circuits intégrés requise. On connait encore de nombreux autres procédés de détermination de TCD en temps réel: on pourra par exemple se reporter au brevet U.S. 4 385 363, qui montre également des circuits de mise en oeuvre du procédé, et à 1 'article "Algorithm-architecture mapping for custom DSP chips" par Loeffler et autres, ISCAS '88, IEEE, pp. 1953-1956. L'invention vise à fournir un procédé de détermination de TCD présentant les avantages de celui décrit dans l'article de Byeong Gi Lee mentionné ci-dessus, mais mettant en oeuvre un nombre réduit d'opérations. Dans ce but, l'invention propose notamment un procédé de détermination de TCD en temps réel à partir des données numériques réelles Xj, avec J (0, 2n-1), comportant un étage de 2n-2 transformations en parallèle portant chacune sur quatre données d'entrée, caractérisé en ce que chaque transformation comprend: a) deux additions-soustractions, effectuées chacune sur deux termes d'entrée, b) deux multiplications sur les termes obtenus par soustraction, respectivement par: C3.(C2)-1 Cl.(C2)-1 c) deux additions-soustractions sur les termes résultant des étapes a) et b), d) une multiplication d'un des termes soustrac- tifs obtenus en c) par C2, et e) une addition du terme soustractif multiplié par C2 et du terme additif correspondant, les termes de sortie de la transformation étant constitués par le résultat de l'addition (e), le terme additif correspondant et les termes additifs et soustractifs restants provenant de l'opération c), les constantes Ci étant égales à 1/(2 cos i./8). Dans le cas d'une transformée de longueur 4, c'est-à-dire avec n = 2, la transformée est obtenue avec uniquement les opérations indiquées ci-dessus. Dans le cas d'une transformée de longueur 8, le procédé implique deux transformations du type ci-dessus défini, effectuées en parallèle, et l'étage ainsi cons- titué est précédé d'un étage d'entrée, comprenant des opérations d'addition-soustraction et de multiplication, et suivi d'un étage de sortie mettant uniquement en oeuvre des additions. A chaque doublement de longueur, le procédé comporte un étage de d'entrée et un étage de sortie supplémentaires. Ce qui est vrai au sujet de la transformée en cosinus directe, reste également valable pour la trans- formée en cosinus inverse, ou TCD-1, correspondante. L'invention sera mieux comprise à la lecture de la description qui suit d'un mode particulier de réali- sation, donné à titre d'exemple non limitatif. La description se réfère aux dessins qui l'accompagnent, dans lesquels: - la Figure i est un graphe de détermination de TCD de longueur 8 selon le procédé de Lee décrit ci- dessus; - la Figure 2 illustre des règles de transfor- mation de graphe; - les Figures 3 et 4, similaires à la Figure 1, sont, respectivement, un graphe montrant une modifica- tion possible de celui de Lee, et un graphe selon l'invention de détermination de la TCD de longueur 8; - la Figure 5 est un graphe de détermination de TCD de longueur 16 suivant l'invention. Pour mieux faire apparaître les avantages apportés par l'invention, on rappellera tout d'abord la constitution du procédé de calcul de Lee, dont une description complète pourra être trouvée dans l'article mentionné ci-dessus. Ce procédé, lorsqu'il est appliqué à une transformée de longueur 8, peut être représenté par le graphe de la Figure 1. Sur cette Figure, les données numériques d'entrée sont désignées par X0, Xl,.. ., X7 et les coefficients de la TCD par F0,...., F1,..., F7. Sur la Figure 1, les "papillons" fournissant, à partir de deux données d'entrée, la somme et la diffé- rence des deux entrées, sont représentés de la façon habituelle. Les coefficients C sont des multiplicateurs de la sortie sur laquelle ils sont indiqués, de sorte que, pour deux valeurs d'entrée x et y, les valeurs de sortie y+x et C(y-x) sont indiquées par la représen- tation suivante: C x C (y- x) y y +x un coefficient noté Ci a pour valeur: Ci = 1/(2 cos i,/16) Pour une transformée de longueur 8. Il faut relever que, le coefficient C4 du graphe de la Figure 1, est égal à ce que serait le coefficient C2 avec, en dénominateur, cos i,/8 au lieu de cos i,/16 et à ce que serait le coefficient C8 avec, en dénomina- teur, cos,/32. Enfin, la somme y + x de deux valeurs d'entrée, c'est-à-dire une opération d'addition, est représentée par: x y_ y+x On peut regarder le graphe de la Figure 1 comme comprenant deux sous-graphes correspondant chacun à une transformée de longueur 4, indiqués par des cades 10 en traits mixtes. Comme on l'a indiqué plus haut, il est souhaitable de réduire le nombre d'opérations requis, sans pour autant faire disparaître la récursivité et la régularité du graphe. Pour cela, les règles d'équiva- lence montrées en Figure 2 ont été utilisées. En appliquant les règles 1 et 3, on arrive à la présentation du graphe donné en Figure 3: suivant la règle 1, on peut substituer, aux multiplications par le coefficient C4 sur les deux sorties d'un papillon, les mêmes multiplications sur les deux entrées, comme indiqué par les flèches en tirets sur la Figure 1. Ces entrées étant constituées par les sorties additives d'un étage de papillon situé immédiatement en amont, on peut reporter encore le coefficient C4 sur les entrées de cet étage de papillon amont, à condition de multiplier la sortie soustractive par C4-1, comme indiqué par des flèches en traits pleins sur la Figure 3. On constate que les données d'entrée Xi sont multipli es par le coefficient multiplicateur ou facteur C4 égal à 1/V. Mais cette multiplication peut aussi bien être faite sur les coefficients Fi de sortie, puisque la fonction mise en jeu est linéaire, et n'a pas été indiquée. De plus, dans le cas, fréquent, o l'on cherche à réaliser une TCD bidimensionnelle, deux multiplications en cascade par C4 sont à effectuer au même point, ce qui revient à une multiplication par (C4)2, c'est-à-dire par 2-1: une telle multiplication est constituée par un simple décalage et n'exige pas de circuit ou de cycle de calcul supplémentaire. On peut donc omettre complètement les multiplications en entrée du graphe de la Figure 3. En appliquant alors les règles 2 et 3 de nouveau, on arrive, pour une transformée de longueur 8, au graphe de la Figure 4 qui fournit les coefficients Fi à une multiplication par (2)1/2 près. On constate que l'on obtient ainsi un graphe à huit étages, comportant trois fois un ensemble constitué d'un étage de papillons et d'un étage multiplicateur, puis deux étages d'additionneurs. En tout, le graphe met en oeuvre onze multiplications et vingt-neuf additions et fournit la TCD monodimensionnelle au facteur multi- plicatif 21/2 près. La Figure 5 montre qu'on passe aisément du procédé de détermination de la transformée de longueur 8 à une transformée de longueur 16. Chaque fois qu'on double le nombre de points qui interviennent, on doit ajouter deux étapes d'entrée et une étape de sortie. Sur la Figure 5, on a en particulier indiqué, en O10a, un des graphes de calcul de transformée de longueur 4, les indices des coefficients C étant simplement adaptés à un graphe complet correspondant à une transformée de longueur 16; on a donc Ci - 1/(2 cos iw/32). Plus généralement, pour une transformée sur 2P points, le coefficient Ci aura pour valeur Ci - 1/(2 cos iv/2 p+l). On retrouve, sur le graphe de la Figure 5, deux graphes de calcul de transformée de longueur 8, dont l'un est indiqué par le cadre 12 en traits mixtes. On voit que, là encore, on ajoute, en amont, un jeu de deux étages (un étage de papillons et un étage de multipli- eurs). On ajoute également, en aval, un étage d'additionneurs et un brassage. A chaque niveau, l'un des sous-graphes est légèrement différent des autres. On voit sur les Figures que la transformée sur quatre points qui fournit notamment F0 ne comporte pas de multiplieur par C4-1 (Figure 4) ou par C8-1 (Figure 5). Mais en fait, on peut considérer qu'il y a une multiplication par le facteur 1 et donc identité. La TCD bidimensionnelle est calculée classique- ment par regroupement en parallèle de plusieurs circuits du type décrit plus haut en association avec une mémoire. Il est de plus souhaitable de rechercher le meilleur compromis entre le nombre de bits qui doit être aussi faible que possible, et la précision requise. Cela implique d'optimiser les formats des constantes de multiplication et des données en chaque point du graphe pour arriver avec un nombre de bits donné à la précision de calcul la meilleure sans risque de débordements. Dans le cas d'une TCD monodimensionnelle à 16 points, il est souvent avantageux de coder les cons- tantes de multiplication sur 12 bits significatifs ap Zue4ttamtad aoTaem el jaTnoTez TsuTe Znad uo a6e,a, ge agToossQ aoT2:em ew V sa 4 N Qo Sú Cu - 3 maTog nzd uo 'eBeav,T ap (Iene ua) azToap g?:a (Zuome ua) eqoneb g sauuop sap sanesaA sal a %a D zed eu6Tsgp uo TS 'aIIaToTazew uoT4eoTTdTzlnm aun aed aTqe4uesgadea $ss $ueATns ne seB%9 un,p a6essed ai '%a;;a us OC -aqdeaB np pneou enbeqo ua sauuop sep uoTeTzvA ap seiiaxaeuT, i zeanol% ap eIqFssod 4se IF '[T+'T-] sIeI $aeuTI suep zueTzeA (TX) agazua,p sauuop sel enb asoddns uo Ts 'JoaiTp aD& aun,p seo sl suea uuapaoqqp GZ ap aouesqel zuessnuezeb ua %no% uoTsTogad ap unmTxem eT aToAe,p uTje xneTz ne sgsTTTZn a%9 $uaATop seuazuT sawguuop sap -abepoO ap s$Tq gT sel ------------------- ------------------- --------------- oz_ __ ___ --- O : OOOOTOIOTTOI: TESETZtTT: 0 : 0000IOIOIIOT: '96L9'TLOL'O: PD : OOOIOOTIOIIT: '''Lú06úLAe8'I: T-PD9 : ITIIIITTOOOOTI: ''I89999L'0: I-PDOD : 000101000001: '6LSS6L60 '0: I ST : IITTIOOTTOOI: '''L88PPE109'0:E : 01100110011I: '''08Z9L6668'0: 53 : OOOOOOIOOTOI: '''9TS96Z99'Z: úD : aBepoo: analeA: 0O -: $sauens eaTeuTq ua sagpoo suo%e$uesSgd sel zasdopu V $npuoo eTeD - s:e:Insqa SaT %usmanT$eT$uBrs apeabgp ssTq Il V aBessed el S anb %a uoTsTogad eT ap a$e:ogTuSTs uoTzeaoTTeue aunone - aiodde,u s%q l eI aBessed al anb Zaega ua $ueaiuom aftpoo ap ssursKs sal avd segsodwT suoT$puoo sal anod suo:$einwTs saq -aqtood snTd eI anaeaeA el g sTpuoaze passer de l'entrée du graphe à la sortie de l'un quelconque des étages en faisant le produit des matices associées successives. Ceci permet de calculer les valeurs maximum atteignables en chacun des points du graphe. La solution qui conduit à la meilleure précision des résultats consiste à optimiser le cadrage en chacun des noeuds du graphe. Mais elle nécessite un contrôle plus compliqué que pour une solution o l'optimisation est faite par étage, et pour cette raison on utilisera en général cette seconde solution. Le tableau suivant représente la progression des dynamiques maximum à chacun des huit étages du graphe de la Figure 4: étage intervalle dynamique 0 (entrée) [-1,+1[ 2 1 (+/-) [-2,+2[ 4 2(x) [-5.126..,5.126..[ 10.25.. 3(+/-) [-6.145..,6.145..E 12.29.. 4(x) [-7.391..,7.391..[ 14.78.. (+/-) -[-10.45..,10.45..[ 20.90.. 6(x) [-12.93..,12.93..[ 25.87.. 7(+) [-12.93..,12.93..[E 25.87.. 8(+) [-8,+8[ 16 Une première solution consiste à présenter en entrée du graphe des données sur 16 bits avec 4 bits de poids fort de garde (c'est-à-dire à zéro). Le cadrage reste constant tout au long des calculs et aucun débordement ne peut survenir puisque la dynamique maximum est moins de 16 fois plus grande que la dynamique d'entrée. Ces 4 bits permettent de coder la valeur maximum possible pouvant surgir à l'étage 6. Une autre solution consiste à présenter, en entrée du graphe, des données sans bits de poids fort de garde (donc multipliées par 16 par rapport au cas précédent), ce qui permet d'avoir plus de bits de précision. L'étage 1 doit alors fournir des résultats divisés par 2, l'étage 2 doit fournir des résultats divisés par 4 et l'étage 5 doit fournir des résultats divisés par 2. Ainsi une division par 16 est globalement effectuée et les résultats en sortie du graphe ont le même cadrage que pour la solution précédente. Il ne peut pas y avoir de débordements et la précision des résul- tats est meilleure que dans le cas précédent. Les simulations numériques des divers cas pos- sibles montrent qu'un bon compromis entre la précision des résultats et la simplicité de la réalisation con- siste à présenter des données avec 3 bits de poids fort de garde, l'étage 5 fournissant des résultats divisés par 2: une division par 4 sera donc effectuée entre la TCD ligne et la TCD colonne pour avoir 3 bits de poids fort de garde pour les données en entrée de la TCD colonne dans le cas d'une TCD bidimensionnelle. Dans le cas d'une TCD inverse, le passage de D à G (transformation inverse) est D = tMG. On peut encore calculer les valeurs maximum susceptibles d'apparaître en chacun des points du graphe. Le tableau de progres- sion des dynamiques maximum & chaque étage est le suivant: étage intervalle dynamique 9 (entrée) [-1,+1[ 2 8 (+) [-1.281..,1.281..[ 2.562 7(+) [-1.617..,1.617..[ 3.234.. 6(x) [-1.281..,1.281..[ 2.562.. (+/-) [-1.536..,1.536..[ 3.072.. 4(x) [-1.387..,1.387..[ 2.774.. 3(+/-) [-1.961..,1.961..[ 3.923.. 2(x) [-l,+1[ 2 1(+/-).[-1,+l[ 2 Il suffit cette fois de présenter des données sur les entrées avec un seul bit de garde, sans autres recadrages. Une simulation montre que la précision de calcul atteinte est parfaitement compatible avec les normes envisagées par le CCITT, notamment dans le cas d'une TCD directe suivie d'une TCD inverse. Les différents opérateurs requis peuvent être constitués par des composants existants. REVENDICATIONS 1. Procédé de compression d'image par détermination de la transformée en cosinus discrète en temps réel, à par- tir de données numériques réelles Xj représentant l'image, avec j E (0,2n-l) comportant un étage de 2n-2 transforma- tions en parallèle portant chacune sur quatre données d'entrée, caractérisé en ce que chaque transformation comprend: a) deux additionssoustractions, effectuées chacune sur deux termes d'entrée, b) deux multiplications sur les termes obtenus par soustraction, respectivement par: C3.(C2)-1 Cl. (C2)-l c) deux additions-soustractions sur les termes résultant des étapes a) et b), d) une multiplication d'un des termes soustractifs obtenus en c) par C2, et e) une addition du terme soustractif multiplié par C2 et du terme additif correspondant, les termes de sortie de la transformation étant constitués par le résultat de l'addition (e), le terme additif correspondant et les termes additifs et soustractifs restants provenant de l'opération c) et les constantes Ci étant égales à 1/2 cos i w/8. 2. Procédé selon la revendication 1, caractérisé en ce que, à chaque doublement de longueur à partir d'une transformée de longueur 4, il comporte un étage d'entrée et un étage de sortie supplémentaires et une multiplication par Vr du résultat sur l'une des transformations (branche Fo) de l'étape d'ordre précédent. 3. Procédé selon la revendication 1 de dé- termination de transformée de longueur 8, caractérisé en ce Le 5 octobre 1989 qu'il comprend, en plus de deux desdites transforma- tions, effectuées en parallèle et dont l'une comporte une multiplication supplémentaire par 2, un étage d'en- trée réalisant des opérations d'addition-soustraction et de multiplication et un étage de sortie mettant unique- ment en oeuvre des additions et une multiplication par 2. 4. Dispositif de détermination de transformée en cosinus discrète en temps réel, à partir de données numériques réelles Xj, avec J E (0, 2n-1), caractérisé en ce qu'il comprend au moins un module de calcul élémentaire ayant: a) deux papillons de calcul addition- soustraction effectuées chacune sur deux termes d'entrée, b) deux multiplieurs des termes obtenus par soustraction, respectivement par: C3.(C2)- Cl.(C2)-1 c) deux papillons d'addition-soustraction des termes fournis par les multiplieurs, d) un multiplieur d'un des termes soustractifs fourni par les seconds additionneurs-soustracteurs par C2, et e) un additionneur du terme soustractif multiplié par C2 et du terme additif correspondant, les constantes Ci étant égales à 1/2 cos iv/8.