Note: Descriptions are shown in the official language in which they were submitted.
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
DISPOSITIF ET PROCEDE D'ENCODAGE DE TYPE CABAC
La présente invention concerne un procédé d'encodage,
du type CABAC (Codage arithmétique binaire à contexte
adaptatif), d'un flux initial d'informations numériques
binaires destinées à générer un flux sortant pour former,
après décodage, des images vidéo.
On sait que la syntaxe et les procédés permettant
d'assurer le décodage d'un flux d'informations vidéo sont
définis dans la norme de compression vidéo dit ITU H.264 ou
ISO/IEC 14496 MPEG-4 Part.10. Cette norme propose, à titre
informatif, des procédés permettant de produire des flux
compressés d'informations.
Les dispositifs d'encodage générant des flux conformes
à cette norme comportent un étage d'encodage dont la tâche
est de générer un flux binaire qui est représentatif des
informations à transmettre. Cet étage d'encodage peut faire
appel à deux méthodes dites respectivement CAVLC (Codage de
longueur variable à contexte adaptatif) et CABAC. Cette
dernière méthode est plus intéressante en ce qu'elle génère
un flux binaire dont le débit est plus faible que celui
produit par la première, au détriment cependant d'une plus
grande complexité.
On sait que la méthode CABAC comporte une étape, dite
renormalisation . Cette étape fait appel à un processus
itératif qui constitue en quelque sorte le goulot
d'étranglement de la méthode, dans la mesure où, par
principe même, son temps d'exécution est relativement long.
Cette étape fait intervenir un intervalle de probabilité
d'occurrence associée à un bit, et des variables de seuils
qui seront désignées ci-après par V1/4 et V1/2. V1/4 est égal à
0,25 en mode décimal. Dans la suite du texte, on pourra
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
2
aussi écrire "01000..." en mode binaire (le nombre total de
bits dépendant de la précision souhaitée pour le codage de
l' intervalle) . De même, V1/2, qui est égal à 0, 5 en mode
décimal, pourra s'écrire "1000..." en mode binaire.
La présente invention a pour but de proposer un
dispositif et un procédé d'encodage dans lequel on remplace
le processus itératif de l'état antérieur de la technique
par un processus permettant d'accéder de façon directe aux
mêmes résultats, et ceci à partir des mêmes paramètres
d' entrée .
La présente invention a ainsi pour objet un dispositif
d'encodage de type CABAC, d'un flux binaire initial
d'informations numériques destinées à générer un flux sortant
pour former, après décodage, des images vidéo comprenant :
- des moyens d'analyse aptes à analyser bit à bit des
séries successives de bits du flux binaire initial et à en
déduire, pour chaque bit, un intervalle représentant la
probabilité d'occurrence associée à ce bit, cet intervalle
étant défini par sa taille CIR et sa borne inférieure CIL,
- des moyens de stockage du nombre BO de bits en
attente d'insertion après traitement du bit précédant le bit
courant dans le flux binaire initial,
- des moyens de renormalisation aptes à déterminer si
une renormalisation est nécessaire pour le bit en cours et à
effectuer cette renormalisation,
caractérisé en ce que lesdits moyens de renormalisation ne
sont pas itératifs et comprennent :
a) un premier module de calcul de la borne supérieure de
l'intervalle CIH égale à CIL + CIR - 1,
b) un deuxième module de détermination de la séquence S
des bits de poids forts communs à CIL et CIH, la longueur de
cette séquence étant dénommée M,
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
3
c) un troisième module de détermination du nombre entier
N tel que CIR.2N-1 < V1/4 <- CIR.2N,
d) un quatrième module de calcul du minimum P entre M et
N pour, si P est non nul, insérer dans le flux sortant les P
bits de poids forts de la séquence S et les BO bits en
attente, et mettre BO à 0,
e) un cinquième module de mise à jour du nombre BO de
bits inconnus qui sont en attente d'insertion pour la
renormalisation du bit suivant du flux binaire initial, par
augmentation de BO de N - M,
f) un sixième module de calcul de la valeur de CIR pour
le bit suivant du flux binaire initial, égale à la valeur de
CIR pour le bit courant multiplié par 2N,
g) un septième module de calcul de la valeur de CIL pour
le bit suivant du flux binaire initial, égale à la valeur de
CIL pour le bit courant multipliée par 2N et, si M est
différent de N, pour y retrancher V1/2.
De manière préférée, les moyens de renormalisation sont
contenus dans un composant de type circuit intégré pour
application spécifique (ASIC), ou réseau de portes
programmables in-situ (FPGA) ou sous forme de logiciel dans
un processeur de traitement de donnés.
Le dispositif selon l'invention permet un traitement de
renormalisation, qui ne nécessite que quelques opérations de
calcul simples, et aucune itération. Il est ainsi beaucoup
plus rapide que le dispositif selon l'art antérieur.
L'invention a également pour objet un procédé d'encodage
de type CABAC, d'un flux initial d'informations numériques
binaires destinées à générer un flux sortant pour former,
après décodage, des images vidéo dans lequel :
- on analyse bit à bit des séries successives de bits
du flux binaire initial et on en déduit, pour chaque bit, un
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
4
intervalle représentant la probabilité d'occurrence associée
à ce bit, cet intervalle étant défini par sa taille CIR et sa
borne inférieure CIL,
- on analyse cet intervalle et on assure, si
nécessaire, une renormalisation de celui-ci, la
renormalisation prenant notamment en compte un nombre BO de
bits en attente d'insertion résultant du traitement du bit
précédent du flux binaire initial,
caractérisé en ce que la renormalisation est non itérative et
comporte les étapes consistant à:
a) calculer la borne supérieure de l'intervalle CIH
égale à CIL + CIR - 1,
b) déterminer la séquence S des bits de poids forts
communs à CIL et CIH, la longueur de cette séquence étant
dénommée M,
c) déterminer le nombre entier N tel que CIR.2N-1 < V1/4
CIR.2N,
d) calculer le minimum P entre M et N puis, si P est non
nul, insérer dans le flux sortant les P bits de poids forts
de la séquence S et les BO bits en attente après le
traitement du bit précédent dans le flux binaire initial, et
mettre à 0 le nombre BO et
e) mettre à jour le nombre BO de bits inconnus qui sont
en attente d'insertion pour la renormalisation du bit suivant
du flux binaire initial, en augmentant BO de N - M,
f) calculer la nouvelle valeur de CIR pour la
renormalisation du bit suivant du flux binaire initial en la
multipliant par 2N,
g) calculer la nouvelle valeur de CIL pour la
renormalisation du bit suivant du flux binaire initial, en la
multipliant par 2N et, si M est différent de N, y retranchant
V1/2 de la nouvelle valeur de CIL, et
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
h) poursuivre la renormalisation en appliquant les
étapes ci-dessus pour le bit suivant de la séquence de bits.
On décrira ci-après, un encodeur de type CABAC et plus
particulièrement l'étape de renormalisation, en référence au
5 dessin annexé sur lequel :
- la figure 1 est une représentation schématique d'un
encodeur conforme à la norme H.264 montrant les différents
modules permettant d'exécuter les étapes de mise en ceuvre de
la méthode CABAC,
- la figure 2 est une représentation schématique des
différentes étapes de la phase de renormalisation suivant
l'état antérieur de la technique, et
- la figure 3 est une représentation schématique des
différentes étapes de la phase de renormalisation suivant
l'invention.
Ainsi que représenté sur la figure 1, l'encodeur 1
conforme à la norme H.264 comprend des moyens encodeurs 3,
qui, à réception des pixels vidéo, fournissent en sortie,
des données, appelées éléments de syntaxe, qui sont envoyées
vers des moyens d'encodage conformes à la méthode CABAC.
Pour des raisons de simplification, ces moyens 5 seront
désignés ci-après par le CABAC .
Le CABAC 5 possède ainsi des moyens de binarisation 7,
qui transforment les éléments de syntaxe en séquences de
bits. Les moyens de binarisation 7 sont suivis de moyens 9
dénommés EncodeDecision dans la norme H.264 qui
analysent bit à bit ces séquences de bits afin d'en déduire
un intervalle qui est représentatif de la probabilité
d'occurrence associée au bit considéré. Cet intervalle est
caractérisé par deux paramètres, à savoir, d'une part, sa
taille dénommée CodIRange dans ladite norme et désignée
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
6
ci-après CIR et, d'autre part, sa borne inférieure dénommée
CodILow dans ladite norme et désignée ci-après CIL.
Les moyens EncodeDecision 9 sont en relation avec des
moyens de renormalisation 11 qui mettent en ceuvre la
fonction de renormalisation précédemment mentionnée. Cette
fonction assure l'analyse de l'intervalle associé à chacun
des bits de ladite séquence de bits et décide si celui-ci
doit être ou non remis à l'échelle, autrement dit
renormalisé. Lorsqu'il s'avère que la renormalisation n'est
pas nécessaire, cette étape est court-circuitée.
Les moyens de renormalisation 11 coopèrent avec des
moyens d'insertion 12 dont le rôle est d'insérer, en cas de
renormalisation, un ou plusieurs bits dans le flux compressé
de sortie de l'encodeur.
On a représenté pour mémoire sur la figure 2 les
différentes étapes de la phase de renormalisation mise en
oeuvre par les moyens de renormalisation 11 suivant l'état
antérieur de la technique, c'est-à-dire celle dans laquelle
on fait appel à un processus itératif pour déterminer les
bits à insérer dns le flux.
Dans une première étape de cette phase, on teste (bloc
13) la valeur de CIR afin de savoir si sa taille est
inférieure à V1/4 (la valeur binaire sur 10 bits de V1/4 est
de 01 0000 0000) . Si tel n' est pas le cas, il n' y a pas de
renormalisation et l'on court-circuite cette étape pour le
bit considéré.
Si la valeur de CIR est inférieure à V1/4, il doit y
avoir remise à échelle autrement dit renormalisation, et
l'on multiplie (bloc 15) alors successivement par 2 cette
valeur tant qu'elle reste inférieure à V1/4. Ce sont ces
itérations successives qui représentent un temps d'exécution
important. Comme on le voit sur la figure, à chaque
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
7
itération on teste également la valeur de CIL, et on met à
jour les valeurs de CIL et de BO (nombre de bits inconnus en
attente d'insertion tel que défini dans la norme H.264).
La présente invention se propose de remplacer tout le
processus itératif par un traitement direct. L'invention
repose sur l'exploitation d'une propriété du codage
arithmétique. Ce dernier prévoit que lors du codage d'un
message (séquence de bits à transmettre), la taille de
l'intervalle définissant la probabilité d'occurrence d'un
bit du message ne fait que se réduire. Cela signifie qu'à un
instant du codage, les bits de poids fort (en mode binaire)
ou les premières décimales (en mode décimal) de la borne
inférieure de l'intervalle qui sont identiques à celles de
la borne supérieure sont définitivement figés et resteront
constants jusqu'à la fin du codage.
Prenons un exemple pour illustrer ce principe.
Supposons que l'intervalle final définissant un message
soit, exprimé en mode décimal :
[ 0,1234567 ; 0,1234568 [
Considérons qu'en cours de codage, l'intervalle soit
égal à .
[ 0,1234023 ; 0,1235871 [
Les premières décimales 0,123 de la borne
inférieure sont identiques aux premières décimales de la
borne supérieure. La théorie nous dit qu'on peut à cet
instant prédire qu'elles resteront constantes jusqu'à la fin
du codage, ce qui est bien le cas à la vue des valeurs de
l'intervalle final.
La transposition de cette propriété dans le contexte de
la renormalisation du CABAC est particulièrement
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
8
intéressante puisqu'elle va nous permettre de prédire
directement les résultats de ce processus à partir des
caractéristiques de l'intervalle.
On a représenté schématiquement sur la figure 3 un mode
de réalisation du procédé de renormalisation selon
l'invention.
Ce procédé utilise comme données d'entrée la taille CIR
et la borne inférieure CIL de l'intervalle définissant la
probabilité d'occurrence associé au bit courant à traiter.
Dans une première étape 100, la borne supérieure CIH de
l'intervalle est calculée. Elle est simplement égale à la
somme de CIL et CIR, diminuée de 1 (en mode binaire).
Dans une deuxième étape 110, on détermine la séquence S
qui correspond à la suite des bits de poids forts de CIL et
CIH qui sont identiques et la longueur M (nombre de bits) de
cette séquence S. Cette opération peut être réalisée
simplement en appliquant l'opérateur "OU EXCLUSIF" (XOR) à
la paire CIL, CIH et en comptant le nombre de bits "0"
consécutifs de poids forts dans le résultat pour obtenir M.
En pratique, il n'est pas nécessaire de définir une variable
particulière S. Il suffit de mémoriser le nombre M de bits
de poids forts identiques de CIL et CIH. S est alors
simplement la suite des M bits de poids forts de CIL ou CIH.
On détermine ensuite, dans une étape 120, le nombre
d'itérations N qui seraient nécessaires dans le procédé de
renormalisation selon l'art antérieur. Ce nombre N est égal
au nombre de multiplications par deux ou, ce qui revient au
même, de décalage vers la gauche des bits de CIR (bloc 15,
figure 2) pour que CIR devienne supérieur à V1/4.
Il n'est en pratique pas nécessaire de procéder à un
calcul itératif pour déterminer la valeur de N. On sait en
effet que N peut être obtenu directement par l'équation :
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
9
N = lmbd(l, CIR) - lmbd(1,V1/4)
où -"lmbd(a,b)" est une fonction courante en particulier
sur les processeurs de traitement de signal (en abrégé et en
anglais "DSP") qui fournit le numéro du bit de valeur a le
plus à gauche (de plus haut poids) dans le nombre binaire b,
et
-"l" est un bit de valeur un.
On pourra se reporter au document US2005/0001745, et
notamment aux paragraphes [0026] à [0028], sur l'utilisation
de l'équation ci-dessus pour le calcul de N. Il convient
cependant de noter que, dans ce document, le fait de
calculer N sans itération ne supprime pas le processus
itératif selon l'art antérieur, qui est au contraire indiqué
comme nécessaire, pour déterminer les bits à insérer (cf.
[0030] du document cité).
On notera que les étapes 110 et 120 du procédé selon
l'invention sont indépendantes et peuvent donc être
exécutées dans un ordre quelconque ou en parallèle.
Dans l'étape 130 qui suit, on calcule le minimum P
entre M et N. Si P est non nul (test 135), on passe à
l'étape d'insertion 140 pour insérer les P bits de poids
forts de S et les BO bits en attente dans le flux sortant,
et mettre BO à 0. Cette étape 140 est connue et définie dans
la norme H.264. Elle consiste à insérer dans le flux sortant
le bit de poids fort de S (ou ce qui revient au même de CIL
ou de CIH), puis BO bits de valeur inverse de celle du bit
de poids fort de S, puis d'insérer les P-1 bits restants de
S.
L'étape 150 suivante du procédé de renormalisation
consiste à calculer le nombre BO de bits inconnus (définis
dans la norme H.264 et mis à jour, dans le procédé selon
l'art antérieur décrit en référence à la figure 2, par le
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
bloc 17) qui sont en attente d'insertion pour la prochaine
renormalisation. Ce nombre est augmenté de la différence N -
M. Ensuite, les nouvelles valeurs pour CIR et CIL sont
calculées. Elles sont obtenues dans une étape 160 par
5 multiplication de CIR et CIL par 2N (c'est-à-dire, en
pratique, N décalages vers la gauche des bits de CIR et CIL)
et, si M est différent de N (test 170), par soustraction de
V1/2 à la valeur de CIL (étape 180).
Chacune des étapes référencées 100 à 180 dans la figure
10 3 correspond, pour le dispositif d'encodage selon
l'invention, à l'un des modules ou à une partie de module de
ce dispositif d'encodage.
A titre d'exemple, un mode de réalisation de l'étape de
renormalisation représentée sur la figure 3 est donnée en
annexe. Elle est exprimée sous forme d'une implémentation
logicielle en langage C. Les variables ont une dynamique de
32 bits. Dans cet exemple, la fonction norm() est une
instruction spécifique qui compte le nombre de bits de poids
fort identiques et consécutifs de l'argument qui lui est
passé.
Dans cet exemple, les nombres "21", "Ox3ff" et "0x200"
sont liés au nombre de bits de CIL et CIR dans la norme.
Ainsi "21" vient de norm(10 0000 0000) qui est le bit
de poids forts des variables sur 10 bits. Ceci permet de
compter le nombre de bits de poids forts égal à 0 en ne
considérant que les 10 bits significatifs des deux
variables.
La valeur "Ox3ff" est un masque avec 10 bits à"l" pour
éviter les débordements dans les autres bits et "0x200" est
la valeur V1/2 codée sur 10 bits.
CA 02656125 2008-12-22
WO 2008/001012 PCT/FR2007/051543
11
ANNEXE
RENORMALISATION
// ----------------------------------------
// entrée: CIL (résolution 10 bits suivant la norme)
// CIR (résolution 9 bits suivant la norme)
/ / BO
int N, M, P, CIH;
N = norm (CIR) - norm (V1 4) ;
CIH = CIL + CIR - 1;
M = norm(CIL ^ CIH) - 21;
P = min(M, N) ;
Si (P!=0)
// émission des P bits de poids forts de CIL et
des BO bits en attente, et remise à 0 de BO
BO = 0
BO += N - M;
CIL = (CIL N) & Ox3ff;
if (M != N) CIL -= 0x200;
CIR = N;
// ----------------------------------------
