EBCOT Tier-1 Tutorial

Les trois passes de codage dans EBCOT expliquées sur un exemple détaillé

Table des matières

1 Introduction
2 Exemple utilisé
3 Codage du premier plan de bits
 3.1 Passe de nettoyage
4 Codage du second plan de bits
 4.1 Passe de propagation de la signifiance
 4.2 Passe d’affinage de l’amplitude
 4.3 Passe de nettoyage
5 Suite et fin du codage

1 Introduction

Le codeur contextuel de JPEG2000 nommé EBCOT (Embedded Block Coding with Optimal Truncation Points) est un codeur par plans de bits. Sur chaque plan de bits, trois passes de codage sont utilisées : une passe de propagation de la signifiance (Significance Propagation), une passe d’affinage de l’amplitude (Magnitude Refinement), et une passe de nettoyage (Cleanup). Il existe quatre primitives de codage utilisées par ces passes : la primitive RL (Run-Length), la primitive ZC (Zero Coding), la primitive MR (Magnitude Refinement), et la primitive SC (Sign Coding). Dans ce document, nous allons montrer sur un exemple comment ces passes de codage sont utilisées conjointement aux primitives de codage.

2 Exemple utilisé

Le codeur EBCOT est un codeur par blocs, c’est-à-dire qu’il code les coefficients d’ondelettes bloc par bloc. En général, les blocs sont de taille 64 × 64. La portion de code-bloc que nous allons utiliser dans notre exemple est présentée sur la figure 1 . On fait l’hypothèse que ce bloc est dans une sous-bande LH. Les nombres représentent les valeurs des coefficients d’ondelettes après la quantification. Le parcours des coefficients est effectué par colonnes de 4 coefficients, et bande par bande, comme illustré sur la figure 1 . Sur cette figure, la première ligne de coefficients d’ondelettes appartient à la bande précédente, la dernière à la bande suivante.


fig1

FIG. 1: Portion de code-bloc utilisée dans notre exemple.


Le coefficient le plus fort en valeur absolue dans ce code-bloc vaut 61 (en position (4,7)). Il y a donc 6 plans de bits en amplitude dans ce code-bloc (26 = 64). On les numérote de 0 à 5, du plan de bits le moins significatif au plan de bits le plus significatif. Ce nombre de plans de bits est inclus dans le train binaire émis afin de signaler au décodeur à partir de quel plan de bits le codage est effectué.

3 Codage du premier plan de bits

Dans le premier plan de bits (n = 5) représenté sur la figure 2 , seule la passe de nettoyage est utilisée. En effet, la passe de propagation de la signifiance ne peut être utilisée parce qu’aucun coefficient d’ondelette n’est signifiant avant ce plan de bits. Comme il n’y a pas de coefficient signifiant connu, on ne peut pas propager le codage de la signifiance autour des coefficients signifiants. Pour la même raison, la passe d’affinage de l’amplitude ne peut-être utilisée. En effet, il faut d’abord trouver les coefficients signifiants pour ensuite pouvoir affiner leur amplitude dans les plans de bits moins significatifs. La seule passe utilisée pour coder le premier plan de bits est donc la passe de nettoyage. Cette passe est nommée ainsi parce qu’elle sert à coder tous les bits qui n’ont pas été codés par la passe de propagation de la signifiance ou la passe d’affinage de l’amplitude.

3.1 Passe de nettoyage


fig2

FIG. 2: Plan de bits n = 5.


On commence par le codage de la colonne j = 0. Avant le codage de cette colonne, on ne connaît pas de coefficient signifiant dans cette colonne. De plus, on ne connaît pas de coefficients voisins à cette colonne qui soient signifiants. Ces deux conditions réunies, le codeur passe en mode Run-Length. Le codeur parcourt alors la colonne j = 0. Au plan de bits n = 5, aucun coefficient n’est significatif dans cette colonne. Le codeur émet donc un symbole 0 dans le contexte (RL) pour signaler une colonne de zéros.

De même, sur la colonne j = 1, avant le codage, il n’y a pas de coefficient signifiant connu, ni de voisin signifiant connu. On reste donc dans le mode Run-Length. Comme aucun coefficient de cette colonne n’est significatif au plan de bits n = 5, le codeur émet un symbole 0 dans le contexte (RL).

Pour le codage de la colonne j = 2, le codeur est toujours dans le mode Run-Length car les deux conditions sont réunies. Cependant, le coefficient (0,2) est signifiant au plan de bits n = 5. Le codeur émet alors le symbole 1 dans le contexte (RL) pour signaler la sortie du mode Run-Length. De plus, le codeur code la position du premier coefficient signifiant de la colonne. Il émet les symboles 00 dans le contexte (UNI)1 . Cela permet de signaler au décodeur la position exacte de sortie du mode Run-Length. Le signe de chaque coefficient d’ondelette est codé dès que le coefficient a été trouvé signifiant. Il faut donc maintenant coder le signe du coefficient (0,2).






χ¯h ¯χv κSC ˆχ




1 1 SC4 1
1 0 SC3 1
1 -1 SC2 1
0 1 SC1 1
0 0 SC0 1
0 -1 SC1 -1
-1 1 SC2 -1
-1 0 SC3 -1
-1 -1 SC4 -1





TAB. 1: Prédiction du signe ˆχ et contextes κSC de la primitive SC.

Pour le codage du signe, le codeur EBCOT utilise une prédiction basée sur les signes des quatre coefficients voisins. Les prédictions sont écrites dans le tableau 1 pour les sous-bandes LL, LH ou HH. Les valeurs ¯χh et ¯χv représentent le signe des deux voisins horizontaux et verticaux respectivement. Ces quantités sont inversées dans le tableau de prédiction pour le codage des sous-bandes HL. Une valeur χ¯ vaut 1 si les deux voisins sont positifs ou si un voisin est positif et l’autre n’est pas encore signé, 0 si les deux voisins ne sont pas encore signés ou de signes opposés, et -1 si les deux voisins sont négatifs ou si un voisin est négatif et l’autre n’est pas encore signé. La valeur ˆχ représente la prédiction du signe du coefficient codé. Si cette prédiction est exacte, le symbole 0 est émis dans le contexte SC respectif, sinon le symbole 1 est émis dans ce même contexte.

Dans le cas du coefficient (0,2), comme il n’y a aucun voisin signé, on est dans le contexte (SC0). Le signe prédit est donc positif. Cette prédiction étant incorrecte, le symbole 1 est émis dans le contexte (SC0).

Dans la colonne j = 2, il reste à coder les symboles (1,2) à (3,2). Comme on est sorti du mode Run-Length, c’est la primitive ZC qui est utilisée. Neuf contextes, notés ZC0 à ZC8, sont utilisés dans cette primitive. Ces contextes prennent en compte la signifiance connue des huit coefficients voisins du bit à coder. Ils sont définis dans le tableau 2 . Les valeurs κh, κv et κd représentent respectivement le nombre de coefficients voisins horizontaux, verticaux, et diagonaux qui sont déjà signifiants au moment du codage.











Sous-bandes LL et LH
Sous-bandes HL
Sous-bandes HH
κZC








κh κv κd κh κv κd κd κh + κv









0 0 0 0 0 0 0 0 ZC0
0 0 1 0 0 1 0 1 ZC1
0 0 2 0 0 2 0 2 ZC2
0 1 x 1 0 x 1 0 ZC3
0 2 x 2 0 x 1 1 ZC4
1 0 0 0 1 0 1 2 ZC5
1 0 1 0 1 1 2 0 ZC6
1 1 x 1 1 x 2 1 ZC7
2 x x x 2 x 3 x ZC8










TAB. 2: Contextes κZC de la primitive ZC. «x» signifie n’importe quelle valeur.

Le coefficient (1,2) n’a qu’un coefficient voisin signifiant : le coefficient (0,2). De plus, le coefficient (1,2) n’est pas signifiant au plan de bits n = 5. Le symbole 0 est donc émis dans le contexte (ZC3). Les coefficients (2,2) et (3,2) n’ont pas de voisins signifiants et ne sont pas signifiants au plan de bits n = 5. Deux symboles 0 sont donc codés dans le contexte (ZC0).

Le codeur s’apprête maintenant à coder la colonne j = 3. Comme le coefficient (0,2), voisin à cette colonne, est connu signifiant au plan de bits n = 5, le mode Run-Length n’est pas activé. C’est la primitive ZC qui est utilisée pour coder les quatre bits de cette colonne. Les symboles codés sont 0(ZC5), 0(ZC1), 0(ZC0), et 0(ZC0).

Il n’y a pas de coefficient voisin de la colonne j = 4 connu signifiant. De plus, aucun des coefficients de cette colonne n’est connu signifiant. Le codeur entre donc dans le mode Run-Length. Comme le coefficient (1,4) est signifiant au plan de bits n = 5, le codeur émet le symbole 1 dans le contexte (RL) et signale la position du premier coefficient signifiant de la colonne en codant sa position par les symboles 01 dans le contexte (UNI). Le signe de ce coefficient est ensuite codé. Le coefficient (1,4) est positif. Le contexte est (SC0). La prédiction d’un signe positif est correcte. Le symbole 0 est donc codé dans le contexte (SC0). Les deux bits suivant sont codés par la primitive ZC. Les symboles codés sont 0(ZC3) et 0(ZC0).

Le reste du codage du plan de bits n = 5 par la passe de nettoyage est décrit dans le tableau 3 .





Symboles codés Commentaires
et contextes



j = 0 0(RL) Run-Length.



j = 1 0(RL) Run-Length.



j = 2 1(RL) Run-Length jusqu’au coefficient (0,2).
00(UNI) Position du premier coefficient signifiant.
1(SC0) Le signe prédit par le contexte (SC0) est incorrect.
0(ZC3) 0(ZC0) 0(ZC0) Reste de la colonne codé par la primitive ZC.



j = 3 0(ZC5) 0(ZC1) Pas de Run-Length parce que
0(ZC0) 0(ZC0) le coefficient (0,2) est signifiant.



j = 4 1(RL) Run-Length jusqu’au coefficient (1,4).
01(UNI) Position du premier coefficient signifiant.
0(SC0) Le signe prédit par le contexte (SC0) est correct.
0(ZC3) 0(ZC0) Reste de la colonne codé par la primitive ZC.



j = 5 0(ZC1) 0(ZC5) Pas de Run-Length parce que
0(ZC1) 0(ZC0) le coefficient (1,4) est signifiant.



j = 6 0(RL) Run-Length.



j = 7 0(RL) Run-Length.



j = 8 1(RL) Run-Length jusqu’au coefficient (0,8).
00(UNI) Position du premier coefficient signifiant.
0(SC0) Le signe prédit par le contexte (SC0) est correct.
0(ZC3) 0(ZC0) 0(ZC0) Reste de la colonne codé par la primitive ZC.



j = 9 0(ZC5) Pas de Run-Length parce que
0(ZC1) le coefficient (0,8) est signifiant.
1(ZC0) Un coefficient signifiant dans le contexte (ZC0).
1(SC0) Le signe prédit par le contexte (SC0) est incorrect.
0(ZC3)




TAB. 3: Codage du plan de bits n = 5 par la passe de nettoyage.

4 Codage du second plan de bits


fig3

FIG. 3: Plan de bits n = 4.


Le second plan de bits (n = 4) est représenté sur la figure 3 . Les coefficients signifiants au précédent plan de bits codé (plus significatifs) sont représentés en noir. Les coefficients trouvés signifiants au plan de bits n = 4 sont représentés en gris. Sur ce second plan de bits, les trois passes de codage sont utilisées : la passe de propagation de la signifiance est d’abord utilisée pour coder les bits voisins des coefficients déjà identifiés signifiants au plan de bits n = 4 ou aux plans de bits plus significatifs. En effet, les forts coefficients d’ondelettes sont souvent agglomérés. C’est pourquoi on commence par rechercher des coefficients signifiants autour des coefficients les plus forts déjà connus. Ensuite, la passe d’affinage de l’amplitude est utilisée pour affiner l’amplitude des coefficients qui étaient déjà signifiants aux plans de bits précédemment codés. Enfin, la passe de nettoyage est utilisée pour coder les bits restant.


fig4

FIG. 4: Passe de propagation de la signifiance sur le plan de bits n = 4.


4.1 Passe de propagation de la signifiance

Lors de la lecture du plan de bits n = 4, on trouve que le coefficient (0,0) a un voisin déjà signifiant : le coefficient (-1,0) qui est devenu signifiant au plan de bits n=4. Le bit à la position (0,0) est donc codé dans la passe de propagation de la signifiance. Dans la passe de propagation de la signifiance, seule la primitive ZC est utilisée. Le symbole émis pour coder le bit (0,0) est donc 0 dans le contexte (ZC3).

Les coefficients (1,0) à (3,0) n’ont pas de voisins signifiants connus. Ils ne sont donc pas codés par la passe de propagation de la signifiance. Ces coefficients sont marqués d’une croix sur la figure 4 .

Comme le coefficient (0,2) est signifiant, les bits aux positions (0,1) et (1,1) sont codés. Le bit (0,1) est signifiant au plan de bit n = 4. Le symbole 1(ZC6) est émis. Le signe du coefficient d’ondelette est ensuite codé par le symbole 1(SC3) car le signe prédit est négatif alors que le coefficient codé est positif. Le symbole 0(ZC3) est ensuite émis pour coder le bit (1,1).

Les coefficients (2,1) et (3,1) ne sont pas codés. Le coefficient (0,2) n’est pas codé non plus car il était déjà signifiant au plan de bits précédent. Le codeur émet le symbole 0(ZC3) pour coder le bit (1,2). Les coefficients (2,2) et (3,2) ne sont pas codés.

Le reste du codage du plan de bits n = 4 par la passe de propagation de la signifiance est décrit dans le tableau 4 .





Symboles codés Commentaires
et contextes



j = 0 0(ZC3) Codage du coefficient (0,0).



j = 1 1(ZC6) Codage du coefficient (0,1).
1(SC3) Le signe prédit dans le contexte (SC3) est incorrect.
0(ZC3) Codage du coefficient (1,1).



j = 2 0(ZC3) Codage du coefficient (1,2).



j = 3 1(ZC6) 0(SC3) Codage du coefficient (0,3).
1(ZC7) 0(SC2) Codage du coefficient (1,3).
0(ZC3) Codage du coefficient (2,3).



j = 4 0(ZC7) 0(ZC3) Codage des coefficients (0,4) et (2,4).



j = 5 0(ZC3) 0(ZC5) 0(ZC1) Codage des coefficients (0,5) à (2,5).



j = 6 0(ZC1) 0(ZC1) Codage des coefficients (0,6) et (3,6).



j = 7 1(ZC5) 1(SC3) Codage du coefficient (0,7).
0(ZC3) 0(ZC3) Codage des coefficients (1,7) et (3,7).



j = 8 0(ZC3) Codage du coefficient (1,8).
1(ZC5) 1(SC3) Codage du coefficient (2,8).
0(ZC4) Codage du coefficient (3,8).



j = 9 0(ZC5) 0(ZC3) 0(ZC3) Codage des coefficients (0,9), (2,9), et (3,9).




TAB. 4: Codage du plan de bits n = 4 par la passe de propagation de la signifiance.

4.2 Passe d’affinage de l’amplitude

Dans la passe d’affinage de l’amplitude, seule la primitive de codage MR est utilisée. Cette primitive code les bits des coefficients déjà signifiants aux plans de bits précédents en utilisant les trois contextes du tableau 5 notés MR0 à MR2. La variable ˜σ vaut 0 si c’est la première fois que la passe d’affinage de l’amplitude est appliquée au coefficient codé, sinon la variable ˜σ vaut 1. Les variables κh et κv sont les mêmes que pour la primitive de codage ZC.





σ˜ κh + κv κMR



0 0 MR0
0 ⁄=0 MR1
1 x MR2




TAB. 5: Contextes κMR de la primitive MR.

Les coefficients qui étaient signifiants dans les plans de bits précédemment codés ont leur amplitude affinée dans cette passe. Le symbole 0(MR1) est donc émis pour affiner l’amplitude du coefficient (0,2). De mêmes, les symboles 1(MR1), 0(MR1), et 1(MR1) sont émis pour affiner l’amplitude des coefficients respectivement en positions (1,4), (0,8), et (2,9).

4.3 Passe de nettoyage

La passe de nettoyage est utilisée pour coder les bits qui n’ont pas été codés par les deux passes précédentes. Ce sont les bits qui ne sont pas marqués d’une croix sur la figure 5 . Le codage est décrit dans le tableau 6 .


fig5

FIG. 5: Passe de nettoyage sur le plan de bits n = 4.






Symboles codés Commentaires
et contextes



j = 0 0(ZC1) 0(ZC0) 0(ZC0)



j = 1 1(ZC0) 0(SC0) Codage du coefficient (2,1).
0(ZC3)



j = 2 0(ZC6) 0(ZC1)



j = 3 0(ZC0)



j = 4 0(ZC0)



j = 5 0(ZC0)



j = 6 0(ZC6) 0(ZC1) 0(ZC0)



j = 7 0(ZC5)




TAB. 6: Codage du plan de bits n = 4 par la passe de nettoyage.

5 Suite et fin du codage

Dans la suite, le déroulement du codage est similaire jusqu’au plan de bits n = 0. Le codeur arithmétique MQ code chaque bit émis en utilisant des probabilités d’apparitions différentes pour chaque contexte. Ces probabilités conditionnées par les contextes sont ajustées à chaque bit codé. Ce processus de codage des codes-blocs constitue la première partie du codeur EBCOT. Elle est nommée Tier1. Dans Tier2, la seconde partie du codeur, les morceaux de trains binaires, issus du codage des plans de bits des codes-blocs dans Tier1, sont organisés de façon à optimiser le train binaire final en termes de débit-distorsion. Ce processus est nommé PCRD-opt (Post-Compression Rate-Distorsion OPTimization).