Brevet FR2708168A1 — publié le 19950127

Procédé et dispositif d'estimation d'un budget de bits pour encodeurs à longueur de mot variable. La présente invention se rapporte à un procédé d'estimation d'un budget de bits pour encodeurs à longueur de mot variable, ainsi qu'à un dispositif de compression d'images mettant en oeuvre ce procédé. Dans le domaine de la compression d'images, notamment dans le domaine de la télévision à haute définition, les images à compresser sont soumises à différents traitements (estimations du mouvement, transformation dans le domaine des fréquences, par exemple par DCT ("Discrete Cosine Transform" en terminologie anglaise)), avant que les données ainsi obtenues soient codées pour la transmission. Pour éliminer les données redondantes tout en conservant l'intégrité des informations, on peut faire appel aux procédés de codage à longueur de mot variable ("Variable length coding" ou VLC en terminologie anglo-saxonne). Ces procédés tiennent compte de la probabilité d'apparition des données parmi l'ensemble des mots possibles pour ces données. Seront alors codés par des mots binaires courts les mots apparaissant souvent et par des mots binaires plus longs les mots apparaissant moins souvent. Ceci aura pour conséquence une diminution de la longueur de mot moyenne, c'est à dire une diminution du nombre de bits à transmettre. Un exemple d'un dispositif utilisant un tel codage à longueur variable est décrit ci-dessous. Selon un exemple simplifié de circuit de compression (qui peut travailler, par exemple, au standard MPEG (pour "Motion Picture Expert Group")) représenté à la figure 1, un signal vidéo RGB est numérisé par un convertisseur analogique/numérique 1, alimentant une matrice de conversion RGB/YUV 2, dont la sortie est connectée à une mémoire image 3. Un buffer d'entrée 4 fait l'interface entre la mémoire image 3 et le ou les estimateur(s) de mouvement 5. Les résultats de cette ou ces estimation(s) sont traités par des circuits non représentés sur la figure 1. Le signal est d'autre part soumis à une transformation cosinus discrète (DCT) par un circuit approprié 6, qui effectue aussi la quantification des coefficients. Ces coefficients sont finalement codés par un procédé de codage à longueur variable de type connu, par exemple le codage par la méthode d'Huffman (circuit 8). Un buffer 9 recueille le signal compressé issu du codeur pour l'émettre en fonction de la capacité du canal de transmission, canal non représenté sur la figure 1. Un problème apparaît lorsque le buffer 9 se remplit plus vite qu'il ne se vide. Dans certains cas, cela peut conduire à un débordement dudit buffer et donc à une perte de données. Pour éviter ce problème, une boucle de retour de réglage de débit 10 contrôle la quantification des coefficients de la DCT, et par conséquent le débit des données vers le buffer 9. Il apparaît donc comme nécessaire de procéder à un codage VLC des données avant de pouvoir connaître le budget de bits correspondant, c'est à dire le nombre de bits nécessaires pour coder le signal ou la partie de signal sous forme compressée. Cette solution est peu satisfaisante, car on est obligé d'effectuer un certain nombre de calculs inutiles, si le codage est effectué en deux passes, la première destinée à une première estimation du budget de bits, la seconde au codage en soi, avec éventuellement une correction en fonction des résultats de la première passe. II en résulte une perte de temps et d'énergie, ainsi qu'une complexité accrue des circuits. L'invention a pour but d'éviter ces inconvénients. L'invention a d'autre part pour but de permettre une estimation du débit de données issu du codeur, ceci avant le codage à longueur de mot variable. L'invention a pour objet un procédé d'estimation d'un budget de bits dans un circuit de compression de données numériques, notamment de signaux de télévision numérisés, caractérisé par le fait que, lesdits signaux étant représentés par des échantillons de N bits, I'estimation est basée sur la probabilité qu'a un bit de poids donné d'avoir une valeur donnée parmi M mots binaires représentant M échantillons d'un signal, un calcul d'entropie étant effectué sur la base desdites probabilités correspondant aux N bits, la somme de toutes les entropies correspondant à l'estimation désirée. On connaît la performance de certaines méthodes de codage par rapport à la limite inférieure que constitue l'entropie. Dans le cas de la méthode de codage d'Huffman, on sait que le nombre de bits moyen nécessaire pour coder un échantillon du signal est au plus supérieur d'un bit par rapport à l'entropie. Connaissant l'entropie, ou du moins une estimation de l'entropie, on connaîtra, avant même le codage, le débit, ou du moins une estimation du débit auquel il faut s'attendre. Dans le procédé selon l'invention, on tient compte de la corrélation entre bits de même poids parmi les M échantillons du signal au lieu de tenir compte directement de la corrélation entre les échantillons en soi. Nécessairement, I'estimation ainsi obtenue est supérieure à la valeur que l'on trouverait par un calcul entropique classique. Mais le nombre de comparateurs et de compteurs nécessaires pour le calcul est réduit au nombre de bits dans chaque échantillon dans le cas de l'estimation, ce qui représente un gain de matériel appréciable par rapport au calcul classique nécessitant 2 comparateurs et compteurs (un comparateur et un compteur par valeur possible pour les échantillons). L'invention a aussi pour objet un dispositif mettant en oeuvre ledit procédé. Selon une utilisation particulière du procédé conforme à l'invention, I'estimation du budget de bits sert à prévoir le débit des données issues du codeur. Selon une utilisation particulière de l'invention, I'estimation du budget de bits sert à réguler le degré de remplissage du buffer vidéo et donc à adapter le codage au débit du canal de transmission. Le procédé conforme à l'invention peut être appliqué à toutes sortes de données, que ce soit dans le domaine temporel ou fréquentiel. D'autres avantages de l'invention apparaîtront à travers la description du mode de réalisation préférentiel non limitatif, représenté par les figures jointes, parmi lesquelles: la figure 1, déjà décrite, représente un diagramme fonctionnel partiel d'un circuit de compression de signaux de télévision, la figure 2 représente le diagramme fonctionnel d'un exemple d'implémentation du procédé conforme à l'invention, la figure 3 représente le diagramme fonctionnel d'un circuit de calcul de l'entropie correspondant à un bit de poids 2i, ledit circuit étant utilisé dans le diagramme de la figure 2. Un échantillon représenté par un mot binaire de longueur N est de la forme: by Iby 2...bi blbo bi est le bit de poids 2i (OlilN-l), chaque bit pouvant prendre la valeur 0 ou 1. On détermine, pour chaque bit bi, le nombre de fois Ci que ce bit prend la valeur 1 dans les M échantillons. La probabilité que bi prenne la valeur 1 est alors pi = Ci/M. La probabilité que bi prenne la valeur 0 est bien évidemment qi = 1-Ci/M. L'entropie, pour ce bit, est calculée de façon classique en utilisant la formule: Ht =-p1Log2p1-q1Log2q1 ce qui est équivalent à: Ht = -(C,lMZog2(CjlM) (l- CjlM)log2(1- Ç/M) On somme ensuite les entropies pour tous les bits bi. Cette somme représente l'estimation désirée. En sommant sur les M échantillons, on obtient l'estimation du budget de bits. En divisant par M, on obtient l'estimation du nombre moyen de bits nécessaires pour coder un mot: La figure 2 montre un diagramme fonctionnel d'un circuit d'estimation du nombre de bits nécessaires pour coder un signal représenté par M échantillons de N bits. Le circuit comprend une horloge 11 synchrone avec la fréquence des données sur un bus 12. L'horloge 1 1 fournit un créneau lorsque les données sont établies sur le bus 12. Chaque ligne du bus 12 correspond à un bit bi d'un échantillon représentant le signal et est connectée à l'entrée 15i d'un compteur à L bits 14i. Les compteurs 14i sont tels qu'il permettent de compter au moins jusqu'à M. On choisira donc L tel que 2(-2) Ledit circuit 13 comporte un compteur et un comparateur et fournit un signal sur sa sortie chaque fois que M signaux d'horloge ont été comptés. Les compteurs 14i s'incrémentent d'une unité lorsqu'au moment du front montant de l'horloge 12 sur l'entrée 16i, L'entrée 15i est à 1. Au début d'une phase d'estimation, tous les compteurs (compteurs 14i et compteur du circuit 13) sont à zéro. A chaque fois qu'une donnée correspondant à un signal numérisé se stabilise sur le bus 12, L'horloge 1 1 envoie une impulsion. Les compteurs 1 4i s'incrémentent alors si leur entrée 15i est haute. Le compteur du circuit 13 compte le nombre d'impulsions données par l'horloge. Si ce nombre dépasse M, le circuit 13 remet son propre compteur et les compteurs 14i à zéro. Selon une variante de réalisation, I'état du compteur du circuit 13 est fourni à un circuit supplémentaire non représenté qui élabore un signal lorsque M mots ont été comptés, de façon à avertir à quel moment un résultat correct est disponible aux sorties 21 et 22. Les modalités de mise en oeuvre d'une telle réalisation sont à la portée de l'homme du métier. La sortie de chaque compteur 14i est connectée à l'entrée d'un circuit correspondant 18i décrit ultérieurement. Les circuits 18i fournissent chacun l'entropie correspondant au bit bi. Les entropies sont sommées par un sommateur 19. Le résultat est retiré au terme constant NLogM de l'équation (1) par le sommateur 20. Suivant que l'on désire une estimation du nombre total de bits nécessaire pour coder les M échantillons ou du nombre moyen de bits par échantillon, on choisira respectivement la sortie 21 ou la sortie 22. La sortie 21 correspond directement à la sortie du sommateur 20, tandis que la sortie 22 correspond à cette sortie vue à travers un diviseur par M 23. Le figure 3 représente un diagramme fonctionnel correspondant à l'un des circuits 18i. Ce circuit possède en entrée les valeurs de M, ainsi que les valeurs de Ci correspondant au nombre de fois qu'un bit bi était à 1 dans les M échantillons. Le circuit comprend principalement deux tables logarithmiques 24 et 25 de base 2. Ces circuits ont la particularité de fournir un zéro en sortie quand un zéro est présenté à leur entrée, même si le log de zéro n'est normalement pas défini. L'entrée de la table 24 reçoit le terme M-Ci, tandis que la table 25 reçoit le terme Ci. Les sorties des tables vont chacune vers un multiplicateur recevant d'autre part respectivement M-Ci et Ci. Les sorties des deux multiplicateurs sont ensuite additionnés pour fournir la sortie du circuit 1 8i. Selon une variante de réalisation, une seule mémoire de logarithmes est utilisée pour tous les circuits 18i, un microprocesseur ou équivalent étant employé pour fournir les valeurs à partir de cette mémoire. Selon une variante de réalisation, le circuit 13 comporte une remise à zéro qui permet de choisir exactement à partir de quel échantillon on désire commencer l'estimation, en appliquant au moment voulu un signal sur cette entrée. L'estimation obtenue peut ensuite être utilisée par les autres circuits du dispositif de compression, notamment pour réguler le degré de remplissage du buffer de données compressées, ou pour adapter la quantification des coefficients. L'interaction du dispositif d'estimation selon l'invention avec le dispositif d'ensemble dans lequel il sera implémenté ainsi que la régulation en soi se feront selon l'un des schémas connus par l'homme de métier concerné. Selon un mode de réalisation particulier, I'estimation du budget de bits est effectuée dans une première passe du codeur, le résultat correspondant étant ensuite utilisé pour adapter la quantification des coefficients pendant une seconde passe pour obtenir le débit de bits désiré, ladite seconde passe se terminant par le codage VLC véritable, tandis que la première passe se termine par l'estimation du budget de bits selon le procédé conforme à l'invention. Selon un mode de réalisation particulier, I'estimation selon le procédé conforme à l'invention est obtenue après que les données aient été soumises à une transformation Walsh-Hadamard au lieu d'une transformation DCT. La transformée Walsh-Hadamard est plus simple à mettre en oeuvre que la transformée DCT, n'exigeant que des additions et des soustractions et non des multiplications. On pourra également utiliser l'estimation obtenue grâce au procédé conforme à l'invention après une transformation Walsh-Hadamard pour adapter la quantification de coefficients obtenus par DCT. D'autres implémentations du procédé que celle donné dans l'exemple ci-dessus sont bien sûr possibles. Certaines étapes pourront notamment être mises en oeuvre grâce à un microprocesseur. Le procédé d'estimation du budget de bits peut bien évidemment être utilisé dans d'autres applications comportant des codeurs à longueur variable. REVENDICATIONS 1. Procédé d'estimation d'un budget de bits dans un circuit de compression de données numériques, notamment de signaux de télévision numérisés, caractérisé par le fait que, lesdits signaux étant représentés par des échantillons codés de N bits, I'estimation est basée sur la probabilité qu'a un bit de poids donné d'avoir une valeur donnée (0 ou 1) parmi M mots binaires représentant M échantillons du signal, un calcul d'entropie étant effectué sur la base desdites probabilités correspondant aux N bits, la somme de toutes les entropies correspondant à l'estimation désirée. 2. Procédé selon la revendication 1, caractérisé en ce qu'on détermine, parmi les M échantillons du signal, le nombre de fois Ci (O 3. Procédé selon l'une des revendication précédentes, caractérisé en ce que lorsque les M échantillons ont été traités, on somme les entropies Hi pour obtenir l'estimation du budget de bits désirée. 4. Procédé selon l'une des revendications précédentes, caractérisé en ce que l'estimation du nombre moyen de bits nécessaires pour codeur un mot est: 5. Dispositif mettant en oeuvre le procédé selon l'une des revendications précédentes caractérisé en ce qu'il comprend N compteurs de L bits (14i) avec L tel que 2(L-2) 6. Dispositif de compression de signaux de télévision mettant en oeuvre le procédé selon l'une des revendications 1 à 4 et comprenant un codeur à longueur variable, ledit dispositif étant caractérisé en ce que ledit procédé est mis en oeuvre avant toute transformation linéaire des échantillons représentant le signal, I'estimation qui en résulte étant utilisée pour adapter le taux de compression des données aux capacités du canal de transmission.