IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

<figure><img src="image_2.png" /></figure>

ÉTUDE EXPÉRIMENTALE
DE LA
COMPRESSION DIFFÉRENTIELLE
PAR UN FILTRE RÉCURSIF
BIDIMENSIONNEL

Samer

S. Attasi

Rapport de Recherche N°165

Avril 1976

F
# ÉTUDE EXPÉRIMENTALE DE LA COMPRESSION DIFFÉRENTIELLE PAR UN FILTRE RÉCURSIF BIDIMENSIONNEL

S. Attasi

## Résumé :

Une étude expérimentale menée au centre de calcul hybride du LABORIA est décrite. Son objectif est d'étudier la viabilité d'un système de compression différentielle de signaux d'image, basé sur un algorithme de reconstruction récursif issu d'un modèle statistique bidimensionnel simple des images à traiter.

Les expérimentations semblent montrer qu'un tel système est particulièrement bien adapté au codage à longueur variable dans la mesure où il permet de concilier les exigences apparamment contradictoires d'une minimisation du débit binaire (quantification à 64 niveaux homogènes) et d'une bonne qualité de l'image reconstruite.

## Abstract :

The goal of the reported experiments is to study the feasability of an image differential compressor using a recursive reconstruction algorithm based on a two dimensional statistical model. Experiments show that such a system would be best adapted to a variable length coding satisfying two contradictory impairments of efficient compression (quantization with equal steps) and good quality of restored image.
Le problème de la compression de données est particulièrement important pour la transmission digitale de signaux d'image. Ainsi pour la transmission d'images de télévision, à raison de 6 à 8 éléments binaires (64 à 256 niveaux de gris) par point d'image, les débits nécessaires dépasseraient 100 Mbits/seconde. A ce prix on atteint assez rapidement la capacité des voies de transmissions les moins bruitées, et une réduction de ce débit s'impose.

Les méthodes de compression les plus utilisées à l'heure actuelle en raison de leur simplicité sont connues sous le nom de compression différentielle. Le principe théorique de ces méthodes est d'exploiter les propriétés de corrélation du signal {$y$} à transmettre en le transformant en un signal {$v$} mieux adapté au codage. Plus précisément la source transmettant le signal {$v$} doit avoir une entropie minimale. Sous l'hypothèse gaussienne (suffisante mais non nécessaire, vérifiée dans la pratique pour le signal {$v$} (voir figures 3 et 4)) cette condition revient à minimiser la variance du signal {$v$}. Autrement dit :

$$ (1) \qquad v_{i,j} = y_{i,j} - E[y_{i,j} | \bar{Y}_{i,j}] $$

où $\bar{Y}_{i,j}$ représente l'ensemble des échantillons déjà analysés.

Le codeur optimal est alors obtenu par le code de Huffman [HUFFMAN] adapté à la loi de probabilité des échantillons indépendants {$v_{i,j}$}.

Le schéma du compresseur différentiel théoriquement optimal serait alors :
<figure><img src="image_3.png" /><figcaption>Figure 1.</figcaption></figure>

Toutefois de nombreuses considérations pratiques limitent la portée de cette solution théorique :

- Considérations liées à la voie de transmission : le décodage et l'algorithme de reconstruction peuvent être plus ou moins sensibles au bruit de la voie de transmission.

- Considérations liées à la vision humaine.

L'expérience montre qu'une quantification (à espacements linéaires ou non) du signal {$v$} peut permettre une compression supplémentaire sans détérioration visible de l'image reconstruite.

La mesure de la dégradation visuelle d'une image reconstruite dépend largement de la forme du signal correspondant, laquelle est conditionnée par la quantification et par l'algorithme de reconstruction.
- Considérations de coût du système de compression...

Ainsi, le schéma pratique réaliste de l'émetteur dans un système de compression différentielle est plutôt le suivant :

<figure><img src="image_4.png" /><figcaption>Figure 2.</figcaption></figure>

A noter que la présence du quantificateur dans la "boucle" du pré-dicteur permet d'éviter l'accumulation éventuelle des erreurs de quantification entre l'image originale et l'image reconstruite.

Toutes ces considérations font qu'une méthode de compression se juge sur de nombreux critères. Citons quelques uns qui ont servi dans l'étude expérimentale qui suit :

- Réduction du débit binaire d'informations à transmettre au récepteur. Dans le cas d'un code à longueur variable le nombre moyen d'éléments binaires n'est pas une mesure suffisante. En effet, il est nécessaire de prévoir une mémoire tampon entre la sortie du codeur et la voie de transmission. La taille de cette mémoire tampon est un paramètre important [CHOW] qui dépend essentiellement de l'homogénéité de la suite {$v^n$}.
- Qualité de l'image restituée. Si le seul critère de jugement demeure le critère subjectif, l'expérience montre néanmoins que certains effets, notamment celui de faux contour, sont liés à la forme du signal d'image reconstruit. Un signal reconstruit présentant des "paliers" dus à la quantification entraîne par exemple des faux contours sur l'image restituée.

- L'immunité au bruit de la voie de transmission dépend pour un codage donné, de l'habilité de l'algorithme de reconstruction à éliminer l'effet de ce bruit [PONCIN], autrement dit de sa stabilité au sens de la théorie des systèmes.

- La complexité du système de compression.

L'objet du travail expérimental présenté ci-après est d'étudier les performances d'un système de compression basé sur un algorithme bidimensionnel de prédiction issu d'un modèle statistique simple des images à transmettre.
Le système de compression étudié est du type schématisé par les figures (1) et (2) du paragraphe précédent où nous précisons ci-dessous la forme du prédicteur, du codeur et les diverses quantifications étudiées.

### II. 1. Algorithmes de prédiction et de reconstruction.

Les algorithmes sont basés sur une représentation de la fonction de corrélation du signal {$y$} à transmettre, sous la forme :

$$ (2) \qquad \Lambda(k,l) \triangleq E[y_{i+k,j+1} y_{i,j}] \triangleq \sigma_z^2 \alpha^{|k|} \beta^{|l|}. \quad (\dagger) $$

Les paramètres $\alpha$ et $\beta$ seuls interviennent dans les algorithmes de prédiction et de reconstruction, et mesurent la corrélation moyenne entre deux points de l'image adjacents sur une ligne ($\alpha$) ou sur une colonne ($\beta$).

Dans ces conditions la suite {$v_{i,j}$} optimale, définie par l'équation (1), est simplement donnée par [ATTASI, ATTASI-ABRAMATIC] :

$$ (3) \qquad v_{i,j} = y_{i,j} - \alpha y_{i-1,j} - \beta y_{i,j-1} + \alpha \beta y_{i-1,j-1}. $$

L'algorithme de reconstruction est défini par :

$$ (4) \qquad y_{i,j} = v_{i,j} + \alpha y_{i-1,j} + \beta y_{i,j-1} - \alpha \beta y_{i-1,j-1}. $$

En tenant compte de l'erreur de quantification introduite dans la figure (2) les équations (3) et (4) deviennent :

$$ (5) \qquad v_{i,j} = y_{i,j} - \alpha y_{i-1,j}^{q} - \beta y_{i,j-1}^{q} + \alpha \beta y_{i-1,j-1}^{q} \quad (\text{émetteur}) $$

$$ (6) \qquad \hat{y}_{i,j} = v_{i,j}^{q} + \alpha \hat{y}_{i-1,j} + \beta \hat{y}_{i,j-1} - \alpha \beta \hat{y}_{i-1,j-1} \quad (\text{reconstruction}) $$

<footnote>(\dagger) Aucune perte de généralité à supposer le signal {$y$} centré.</footnote>
où l'on a posé :

$$
(7) \quad \left\{
\begin{array}{l}
y_{i,j}^q = y_{i,j} + (v_{i,j}^q - v_{i,j}) \\
\hat{y}_{i,j} = \text{signal reconstruit.}
\end{array}
\right.
$$

Enfin, pour tenir compte des "bords" de l'image, on aura :

pour la première ligne d'image ($v_{0,0} = y_{0,0}$) :

$$
(8) \quad \left\{
\begin{array}{l}
v_{0,j} = y_{0,j} - \alpha y_{0,j-1}^q \quad \text{(émetteur)} \\
\hat{y}_{0,j} = v_{0,j}^q + \alpha \hat{y}_{0,j-1} \quad \text{(reconstruction)}
\end{array}
\right.
$$

pour la première colonne d'image (éventuellement) :

$$
(9) \quad \left\{
\begin{array}{l}
v_{i,0} = y_{i,0} - \beta y_{i-1,0}^q \quad \text{(émetteur)} \\
\hat{y}_{i,0} = v_{i,0}^q + \beta \hat{y}_{i-1,0} \quad \text{(reconstruction)}.
\end{array}
\right.
$$

Notons que les coefficients $\alpha$ et $\beta$ n'ont pas à être évalués pour chaque image transmise. En effet, leurs variations sont peu significatives à l'intérieur d'une classe d'images présentant des structures voisines dès lors que le nombre de points de l'image devient réaliste (supérieur à 256 x 256).

Typiquement, une corrélation moyenne suivant l'une des deux direc-
tions induit un coefficient de l'ordre de 0,9 dans la direction correspondante ;
une forte corrélation (bandes parallèles à une direction) induit un coefficient
de l'ordre de 0,95 dans la direction correspondante. Ces règles pratiques peu-
vent évidemment être remplacées par des méthodes systématiques d'estimation des
paramètres α et β pour une classe d'images données [ATTASI] ou par une méthode
intermédiaire qui consiste à estimer ces coefficients à l'aide d'un corrélateur
placé en amont du système de compression ($\alpha \approx \frac{\Lambda(1,0)}{\Lambda(0,0)}$, $\beta \approx \frac{\Lambda(0,1)}{\Lambda(0,0)}$)
## II. 2. Les diverses quantifications étudiées.

Trois modes ont été utilisés :

- sans quantification. La suite {$v$} est transmise sur 8 bits vers le codeur ;

- quantification homogène sur 64 niveaux : les 6 bits de poids fort de la suite {$v$} sont transmis au codeur ;

- quantification à échelle non linéaire : 16 seuils et 16 niveaux de quantification sont utilisés, suivant le tableau suivant proposé par [ARGUELLO et all] :

<table><thead><tr><td>Valeur quantifiée</td><td>Seuil de décision</td></tr></thead><tbody><tr><td>- 103</td><td>- 83</td></tr><tr><td>- 63</td><td>- 50</td></tr><tr><td>- 37</td><td>- 30</td></tr><tr><td>- 23</td><td>- 18</td></tr><tr><td>- 13</td><td>- 10</td></tr><tr><td>- 7</td><td>- 5</td></tr><tr><td>- 3</td><td>- 2</td></tr><tr><td>- 1</td><td>0</td></tr><tr><td>+ 1</td><td>+ 2</td></tr><tr><td>+ 3</td><td>+ 5</td></tr><tr><td>+ 7</td><td>+ 10</td></tr><tr><td>+ 13</td><td>+ 18</td></tr><tr><td>+ 23</td><td>+ 30</td></tr><tr><td>+ 37</td><td>+ 50</td></tr><tr><td>+ 63</td><td>+ 83</td></tr><tr><td>+ 103</td><td></td></tr></tbody></table>
## II. 3. Le codeur.

Le codeur a été choisi en fonction de 2 critères :

- ses performances absolues : nombre de bits moyens à transmettre pour une entropie donnée ;

- son indépendance vis-à-vis de la loi de probabilité P(v), impliquant en particulier son indépendance vis-à-vis de la quantification choisie.

Le second critère, garant de la simplicité du codeur, semble contra-dictoire avec le premier. Toutefois un codeur proposé par [CHOW et all] semblait satisfaire les deux critères. Une forme simplifiée ("basic compressor") de ce codeur a été retenue ; il s'agit d'un codeur adaptatif schématisé ci-dessous :

<figure><img src="image_5.png" /></figure>

Le premier codeur fait correspondre au $j^{ème}$ niveau de quantification positif (+), la suite :

<figure><img src="image_6.png" /></figure>

et au $j^{ème}$ niveau de quantification négatif, la suite :

<figure><img src="image_7.png" /></figure>

Il s'agit d'un code "reconnaissable" qui tient compte de la propriété très générale de la loi P(v), à savoir son caractère symétrique et décroissant autour de la valeur 0.

<footnote>(+) 0 étant compté comme un nombre positif.</footnote>
Lorsqu'une séquence de N (fixé) mots a été codée et emmagazinée par le sélecteur de code (le nombre de mots étant identifié par le nombre de bits à "1") celui-ci totalisera le nombre F de bits utilisé pour ce premier codage et sélectionnera le codage définitif de la séquence (appelée séquence fondamentale ou SF) suivant la valeur du rapport $\frac{F}{N}$ :

- Si $\frac{F}{N} > 3$, la séquence contient beaucoup de 0, et on gagne à la recoder par le second codeur à 8 entrées défini par la table ci-dessous :

<table><thead><tr><td>entrée</td><td>sortie</td></tr></thead><tbody><tr><td>000</td><td>0</td></tr><tr><td>001</td><td>100</td></tr><tr><td>010</td><td>101</td></tr><tr><td>100</td><td>110</td></tr><tr><td>011</td><td>11100</td></tr><tr><td>101</td><td>11111</td></tr><tr><td>110</td><td>11101</td></tr><tr><td>111</td><td>11111</td></tr></tbody></table>

- Si $1 < \frac{F}{N} < \frac{3}{2}$, la séquence contient beaucoup de 1, on se trouve dans la situation symétrique de la précédente, aussi on complémente la séquence fondamentale et on la transmet au second codeur.

- Si $\frac{3}{2} < \frac{F}{N} < 3$, la séquence fondamentale est transmise telle quelle sans codage supplémentaire.

La sortie du codeur complet sera ainsi formée de séquences de bits (représentant le codage de N mots) précédées de 2 bits d'identification du mode de récodage choisi par le sélecteur de code.

En dépit de son caractère adaptatif qui lui permet de s'adapter partiellement aux statistiques des N derniers points à transmettre, ce codeur est facile à réaliser avec des comparateurs, compteurs, etc...
Enfin des essais sur des images de satellites auraient montré que la longueur optimale des séquences était de $N \approx 20$ mots [CHOW et all].

Toutefois, les performances annoncées (nombre moyen de bits - entropie $\le 0,25$) par l'auteur de ce code n'ont pu être vérifiées sur les images que nous avons traitées (voir plus loin). Il n'en reste pas moins qu'il s'agit d'un code efficace, indépendant du nombre de niveaux de quantification et simple à implanter.

## II. 4. Implémentation.

L'ensemble du système de compression défini ci-dessus a été simulé sur le calculateur T2000 du centre de calcul hybride du LABORIA, et appliqué à des images numérisées sur bande magnétique. Les divers critères de jugement de la qualité du système, cités plus haut, ont été appliqués, avec comme base de comparaison le prédicteur différentiel le plus utilisé, ($\hat{y}_i = y_{i-1}$) associé au même codeur. La simulation de ce dernier système était particulièrement aisée puisque celui-ci apparaît comme un cas particulier du système de compression étudié (avec $\alpha = 1, \beta = 0$).

Cette comparaison peut s'extrapôler facilement (et nous le faisons) aux systèmes à prédiction bidimensionnelle puisque les performances relatives de ces derniers par rapport au prédicteur "monodimensionnel" ($\hat{y}_i = y_{i-1}$) ont déjà été analysées [CHOW, PONCIN ...].
<figure><img src="image_8.png" /><figcaption>Figure 3 : Loi de probabilité P(v) associée à l'image n° 1.</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Figure 4 : Loi de probabilité P(v) associée à l'image n° 2.</figcaption></figure>
Nous retenons pour la comparaison les deux images reproduites ci-dessous. L'image n° 1 possède une forte entropie et une information "diffuse". L'image n° 2 possède relativement moins de détails, mais présente dans la partie droite des bandes verticales.

<figure><img src="image_10.png" /><figcaption>Image n° 1
(Figure 5)</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Image n° 2
(Figure 6)</figcaption></figure>

Notons d'abord que les histogrammes des lois de probabilité P(v), présentés dans les figures 3 et 4, confirment l'hypothèse d'une loi de probabilité symétrique et décroissante autour de la valeur 0. Ce fait qui demeure vrai pour tout algorithme de prédiction raisonnable appliqué aux images [PONCIN] justifie la méthode qui consiste à minimiser la variance de la suite {$v_{i,j}$} afin d'obtenir une source d'entropie minimale (voir paragraphe I).

### III. 1. Réduction du débit binaire d'information.

Les résultats correspondants sont présentés dans les tableaux suivants :
<table><caption>Image n° 1.</caption><thead><tr><th></th><th></th><th>quantification<br>de (v)<br>performance</th><th>256 niveaux<br>homogènes</th><th>64 niveaux<br>homogènes</th><th>16 niveaux<br>(échelle non<br>linéaire)</th></tr></thead><tbody><tr><td rowspan="2">Prédicteur défini au<br>paragraphe 2</td><td>Entropie de {v}</td><td>3,7</td><td>2,3</td><td>2,3</td><td></td></tr><tr><td>Nombre EB moyen</td><td>7,3</td><td>3,3</td><td>3,7</td><td></td></tr><tr><td rowspan="2">Prédicteur différen-<br>tiel monodimensionnel</td><td>Entropie de {v}</td><td>4</td><td>2,6</td><td>2,4</td><td></td></tr><tr><td>Nombre EB moyen</td><td>9</td><td>3,8</td><td>3,8</td><td></td></tr></tbody></table>

<table><caption>Image n° 2.</caption><thead><tr><th></th><th></th><th>quantification<br>de (v)<br>performance</th><th>256 niveaux<br>homogènes</th><th>64 niveaux<br>homogènes</th><th>16 niveaux<br>(échelle non<br>linéaire)</th></tr></thead><tbody><tr><td rowspan="2">Prédicteur défini au<br>paragraphe 2</td><td>Entropie de {v}</td><td>2,9</td><td>1,7</td><td>1,9</td><td></td></tr><tr><td>Nombre EB moyen</td><td>4,7</td><td>2,4</td><td>2,8</td><td></td></tr><tr><td rowspan="2">Prédicteur différen-<br>tiel monodimensionnel<br>balayage dans le sens<br>des bandes verticales</td><td>Entropie de {v}</td><td>2,8</td><td>1,6</td><td>1,9</td><td></td></tr><tr><td>Nombre EB moyen</td><td>4,7</td><td>2,3</td><td>2,8</td><td></td></tr><tr><td rowspan="2">Prédicteur différen-<br>tiel monodimensionnel<br>balayage perpendicu-<br>laire aux bandes ver-<br>ticales</td><td>Entropie de {v}</td><td>3,4</td><td>2,1</td><td>2,2</td><td></td></tr><tr><td>Nombre EB moyen</td><td>6,7</td><td>2,9</td><td>3,2</td><td></td></tr></tbody></table>
Les observations que l'on peut en tirer sont les suivantes :

- Le codeur utilisé semble être le mieux adapté au codage de sources dont l'entropie est inférieure à 2,5 eb/message (64 niveaux de quantification). Dans ce cas la différence entre le nombre moyen d'éléments binaires par mot et l'entropie est de l'ordre de 0,5 eb/mots. Pour une entropie de 3 eb/message (quantification de l'image n° 2 sur 256 niveaux homogènes), cette différence est déjà de 1,8 eb/message...

- La quantification à espacements croissants autour de l'origine est fort mal adaptée au codage à longueur variable, à tel point que pour le codage utilisé la transmission de 16 niveaux à espacements croissants coûte en moyenne 0,5 eb/mot de plus que la transmission de 64 niveaux à espacements réguliers.

- La comparaison des prédicteurs indique un gain brut en faveur du prédicteur récursif du même ordre que celui obtenu pour les prédicteurs bidimensionnels classiques (0 à 0,5 eb/mot pour une quantification à 64 niveaux, jusqu'à 2 eb/mot pour une quantification à 256 niveaux). Un avantage important est toutefois à signaler en faveur des prédicteurs bidimensionnels (le prédicteur étudié en particulier), il s'agit de l'homogénéité plus grande du débit binaire à la sortie du codeur, qui conditionne ainsi la dimension de la mémoire tampon. Il suffit pour s'en convaincre de remarquer la différence de performance importante relevée pour l'image n° 2, suivant que le balayage est perpendiculaire ou parallèle à la direction des bandes verticales.

### III. 2. Qualité de l'image reconstruite.

Nous reproduisons ci-dessous quelques images reconstruites pour les 2 types de prédicteur et pour les quantifications à 64 niveaux homogènes et 16 niveaux à espacements non homogènes.
<figure><img src="image_12.png" /><figcaption>**Figure 7.**
Image n° 1 reconstruite à partir de 64 niveaux (prédicteur monodimensionnel).</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>**Figure 8.**
Image n° 1 reconstruite à partir de 64 niveaux (prédicteur récursif).</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>**Figure 9.**
Image n° 2 reconstruite à partir de 64 niveaux (filtre monodimensionnel).</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>**Figure 10.**
Image n° 2 reconstruite à partir de 64 niveaux (filtre récursif).</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>**Figure 11.**
Image n° 2 reconstruite à partir de 16 niveaux (filtre monodimensionnel).</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>**Figure 12.**
Image n° 2 reconstruite à partir de 16 niveaux (filtre récursif).</figcaption></figure>

L'observation essentielle concernant les résultats ci-dessus est que la quantification à 64 niveaux **homogènes** qui semblait la mieux adaptée au contexte à longueur variable est particulièrement défavorable au prédicteur monodimensionnel. Ainsi, on observe sur l'image n° 2 (Figure 9) des faux contours dûs à la quantification (en bas à droite par exemple) et situés principalement dans les zônes "plates". Ces faux contours sont inexistants sur les autres images reconstruites.

Pour expliquer ce phénomène, nous reproduisons (Figures 15 à 17), une "ligne" du signal d'image en une zône où les images reconstruites des figures 9 et 10 sont visuellement identiques. Il apparaît ainsi que l'effet de la quantification, bien marqué pour le signal reconstruit par le filtre monodimensionnel, est pratiquement inexistant dans le signal reconstruit par le filtre récursif. Il est remplacé pour ce dernier par un léger effet granulaire qui, rappelons le, est obtenu lorsque volontairement on superpose au signal transmis un bruit pseudo aléatoire afin d'éliminer précisément les effets de la quantification (faux contours, flottement de contours...). Cela semble être
dû à l'effet de filtrage du prédicteur récursif. C'est là que réside à notre
sens le principal intérêt du prédicteur récursif même par rapport aux prédic-
teurs bidimensionnels classiques.

L'utilisation de code à longueur variable dans un système à prédic-
tion différentielle se heurtait en effet à deux exigences contradictoires :

- Une quantification à espacements croissants est nécessaire pour
assurer la qualité de l'image reconstruite.

- Une quantification à espacements homogènes est nécessaire pour assurer un débit binaire minimum.

L'utilisation d'un prédicteur récursif semble concilier les 2 exigen-
ces ci-dessus.

Puisque toutes les images reconstruites à l'aide de l'algorithme
récursif et à partir de 64 niveaux de quantification homogènes, sont prati-
quement identiques aux images originales, on peut se demander si une quantifi-
cation supplémentaire (par exemple 32 niveaux homogènes) ne permettrait pas
une réduction supplémentaire du débit binaire sans une détérioration importante
de l'image reconstruite. Nous reproduisons ci-dessous l'image n° 2 reconstruite
par l'algorithme récursif avec une quantification de 32 niveaux homogènes.

<figure><img src="image_18.png" /><figcaption>Figure 13.</figcaption></figure>

Image n° 2 reconstruite avec 32 niveaux
homogènes (1,9 eb/mot, entropie = 1,3).
L'effet de granularité est maintenant visible sur l'image reconstruite ;
le débit binaire moyen est par contre très faible (1,9 eb/mot).

Il est difficile de comparer les figures 9 et 13 car elles sont dé-
tériorées par des effets différents ; le critère de comparaison dépend de l'uti-
lisation ultérieure (visualisation, classification, etc...). On peut cependant
comparer les débits binaires pour des figures reconstruites toutes deux de très
bonne qualité visuelle (Figure 10 et figure 11). On obtient :

2,4 bits/mot pour l'algorithme récursif,

2,8 bits/mot à 3,2 bits/mot pour l'algorithme monodimensionnel,

suivant que le balayage est perpendiculaire ou parallèle aux bandes verticales.

Le lecteur expérimenté notera enfin que les plages uniformes et som-
bres de l'image n° 2 sont particulièrement sensibles aux effets de la quantifi-
cation (faux contour et granularité). Des essais sur des images ne comportant
pas ces plages sombres et uniformes ont montré que des images reconstruites, de
très bonne qualité pouvaient être obtenues à partir de 32 niveaux de quantifi-
cation homogènes, ainsi que le montre l'image reproduite ci-dessous :

<figure><img src="image_19.png" /><figcaption>Figure 14.</figcaption></figure>

Image n° 1 reconstruite par le filtre récursif à partir
de 32 niveaux homogènes (2,6 eb/mot, entropie = 1,75).
### III. 3. Autres critères : immunité au bruit, coût...

L'immunité aux perturbations intervient au niveau de l'algorithme de reconstruction et de son ability à éliminer les perturbations passagères. Ainsi l'algorithme de reconstruction doit définir un système stable au sens de la théorie des systèmes, c'est-à-dire dont la "réponse impulsionnelle" tend vers zéro. En ce sens l'algorithme récursif de reconstruction utilisé est toujours stable puisque sa réponse impulsionnelle est de la forme $\alpha^{|i|} \beta^{|j|} (\alpha$ et $\beta$ coefficients de corrélation de module inférieur à 1) et tend exponentiellement vers 0.

La stabilité ne peut par contre être garantie pour d'autres algorithmes bidimensionnels optimisés aux moindres carrés [HABIBI] car on ne sait pas déterminer leur réponse impulsionnelle. Ces considérations de stabilité font qu'en pratique les coefficients des filtres bidimensionnels [PONCIN] sont choisis très faibles (de l'ordre de 0,5) au détriment probablement de l'effet de faux contour dû aux "paliers" qui resteront apparents dans le signal reconstruit.

L'algorithme étudié devrait réaliser un compromis entre la sensibilité aux perturbations et l'élimination des effets de la quantification dans le signal reconstruit.

Quant à l'algorithme de reconstruction basé sur le prédicteur monodimensionnel ($\hat{y}_j = y_{j-1}$), il est notoire qu'il accumule les effets des perturbations, et qu'un "rafraîchissement" du récepteur est toujours nécessaire.

Quant au coût, les algorithmes bidimensionnels et l'algorithme étudié en particulier supposent la mémorisation d'une ligne d'image et quelques opérations arithmétiques (3 multiplications et 4 additions dans le cas du filtre étudié) par point d'image à reconstruire. Toutefois, l'homogénéité du débit sortant du codeur dans un système de prédiction bidimensionnelle permet de diminuer la taille de la mémoire tampon à la sortie du codeur et permet de rendre viable la solution de code à longueur variable.
<figure><img src="image_20.png" /><figcaption>Figure 15 : Une ligne "originale" d'image n° 2.</figcaption></figure>
<figure><img src="image_21.png" /><figcaption>Figure 16 : Même ligne reconstruite par l'algorithme récursif.</figcaption></figure>
<figure><img src="image_22.png" /><figcaption>Figure 17 : Même ligne reconstruite par algorithme monodimensionnel.</figcaption></figure>
L'étude expérimentale présentée confirme la viabilité d'un système de prédiction différentielle basé sur un modèle statistique simple des images à transmettre, qui induit un filtre récursif de reconstruction. D'une part le code à longueur variable se justifie mieux (longueur de la mémoire tampon) que pour les systèmes à prédiction monodimensionnelle, d'autre part des débits bi-naires de l'ordre de 2 à 2,5 bits par mots peuvent être obtenus avec un codage simple et adaptatif et sans les effets néfastes sur les contours, associés aux systèmes différentiels classiques. On notera, en outre que des débits de l'ordre de l'entropie de la loi P(v) (1,5 à 2 eb/mot) peuvent être obtenus à l'aide du codage optimal de HUFFMAN.

Une étude expérimentale plus poussée porterait également sur le dimensionnement précis de la mémoire tampon mais devrait pour être motivée, être conduite pour une classe d'images précise.

On atteint ainsi une limite des performances des systèmes de compression point par point à prédiction différentielle simple puisqu'il a été vérifié que les échantillons {$v$} successifs étaient pratiquement indépendants (corrélation moyenne de deux échantillons successifs inférieure à 1/10). Les systèmes basés sur les transformations orthogonales doivent prendre la relève si des réductions de débits supérieures sont souhaitées.
REFERENCES

[1] ARGUELLO R.J. "The Effect of Channel Errors in the Differential Pulse Code. Modulation Transmission of Sampled Imagery". SELLNER H.R. STULLER J.A. IEEE Trans, COM 19. N° 6. (December 1971).

[2] ATTASI S. "Modélisation et traitement des suites à deux indices". Thèse Docteur es-Sciences. PARIS VI. (1975).

[3] ATTASI S. "Nouvelles applications de la modélisation statistique des suites gaussiennes à deux indices". Rapport LABORIA N° 157. (Mars 1976).

[4] CHOW M.C. "Variable Length Redundancy Removal Coders for Differentially Coded Video Telephone Signals". IEEE Trans, COM 19. N° 6. (December 1971).

[5] HABIBI A. "Comparison of n<sup>th</sup> Order DPCM Encoder with Linear Transformations and Block Quantization Techniques". IEEE Trans, COM 19. N° 6. (December 1971).

[6] HUFFMAN D.A. "A Method for the Construction of Minimum Redundancy Codes". Proc. IRE. Vol.40. (September 1952).

[7] PONCIN J. "Codage de signaux d'images avec réduction du débit binaire". Dans : "Codage et traitement des images". CCETT. Rapport DIR/T/u/74. (Mars 1974).

[8] RICE R.F. PLAUNT J.R. "Adaptive Variable Length Coding for Efficient Compression of Spacecraft Television Data". IEEE Trans, COM 19. N° 6. (December 1971).
TABLE DES MATIERES

<table><thead><tr><th></th><th>Pages</th></tr></thead><tbody><tr><td>I. INTRODUCTION AUX METHODES DE COMPRESSION DIFFERENTIELLE</td><td>1</td></tr><tr><td>II. DEFINITION DU SYSTEME DE COMPRESSION ETUDIE</td><td>5</td></tr><tr><td>II.1. Algorithmes de prédiction et de reconstruction</td><td>5</td></tr><tr><td>II.2. Les diverses quantifications étudiées</td><td>7</td></tr><tr><td>II.3. Le codeur</td><td>8</td></tr><tr><td>II.4. Implémentation</td><td>10</td></tr><tr><td>III. RESULTATS COMPARES AUX AUTRES SYSTEMES DE COMPRESSION DIFFERENTIELLE</td><td>13</td></tr><tr><td>III.1. Réduction du débit binaire d'information</td><td>13</td></tr><tr><td>III.2. Qualité de l'image reconstruite</td><td>15</td></tr><tr><td>III.3. Autres critères : immunité au bruit, coût</td><td>20</td></tr><tr><td>IV. CONCLUSION</td><td>24</td></tr><tr><td>REFERENCES</td><td>25</td></tr></tbody></table>