Code de répétition

message décodé

0 0 0 0 1 1 0

Table 1 – Exemple de transmission d’un message utilisé a code a répétation. Ce code

permet de corriger 2 des 4 erreurs ayant eu lieu dans la transmission

sont corrigées par le décodeur.

source

s

encoder

t

ˆs

Décodeur

r

Canal bruité

Figure 3 – Principe de l’encodage

La manière la plus simple d’encoder un message, le code de répétition consiste tout

simplement à répéter chaque bit du message un certain nombre de fois. Par exemple,

dans le code R3 chaque bit est répété 3 fois et le message source s suivant :

s = 0 0 1 0 1 1 0

sera encodé en :

t = 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0

Il est alors possible, en considérant successivement 3 bits du message reçu et en réalisant

un vote majoritaire de retrouver le message original. La table 1 donne un exemple de la

reconstruction d’un message.

2 Travail à réaliser

Vous trouverez sur le site du cours le squelette d’un programme permettant de mettre

en œuvre les principes décrits dans la section précédente. La fonction main de ce pro-

gramme va :

1. charger une image (vous pouvez utiliser l’image d’exemple donnée sur le site ou

n’importe quelle image, l’image doit être placée à la racine de votre projet) ;

2. convertir l’image en niveau de gris puis binariser celle-ci. L’image binarisée est

sauvegardée dans le fichier binary.png ;

3. convertir l’image binaire en un tableau de 0 et 1 ;

3

4. simuler la transmission de cette image binaire au travers d’un canal bruité ; le

résultat de cette transmission est stocké dans le fichier noise.png ;

5. encoder l’image, la transmettre au travers du canal bruit et la décoder ; le résultat

de cette transmission est stockée dans le fichier encoded.png ;

Vous devez réaliser les méthodes suivantes :

1 une méthode permettant de bruiter une suite de bits :

int[] addNoise(int[] data, double f)

Le parametre f doit être compris entre 0 et 1 et correspond a la probabilité qu’un

bit soit mal transmis. Cette méthode revoie un tableau binaire de même taille que

le tableau passé en paramètre. Le ie élément de ce tableau correspond soit au ie

élément de data avec une probabilité 1 − f soit à son opposé (avec une probabilité

f , cf. figure 2).

Pour déterminer si un bit doit être modifié ou non, il faut :

— définir une variable randomGenerator de la manière suivante :

Random randomGenerator = new Random();

— changer le bit si la condition randomGenerator.nextFloat() < f est vraie

2 une méthode permettant d’encoder une image selon le principe décrit § 1 :

int[] encode(int[] data)

Cette méthode renvoie un tableau dont la taille est trois fois plus grande que le

tableau passé en paramètre et qui contient chaque élément du tableau d’entrée

répété trois fois ;

3 une méthode permettant de décoder une image selon le principe décrit § 1 :

int[] decode(int[] data)

Cette méthode permet de reconstruire le signal original à partir du signal encodé.

4 une méthode permettant d’évaluer la qualité de la reconstruction

float score(int[] imageOriginale, int[] imageFinale)

Cette méthode renvoie le pourcentage de bit différents entre l’image originale et

l’image reconstruite.

5 Modifier le programme principal pour afficher la (cid:28) qualité (cid:29) du code de répétition.

3 Pour ceux qui veulent aller plus loin

3.1 Théorie de l’information

6 On suppose que l’on cherche à transmettre un message au travers d’un canal bruité

symétrique en utilisant le codage R3. Quelle est la probabilité qu’un bit soit mal

transmis ?

7 La probabilité qu’un bit soit mal transmis dans le cadre d’un codage RN est :

N

(cid:88)

pb =

n=(N +1)/2

(cid:19)

f n (1 − f )N −n

(cid:18)N

n

4

si N est impaire. Représenter cette probabilité en fonction de N. Que peut-on en

conclure ?

3.2 Binarisation d’une image

Le programme fourni sur le site du cours propose une méthode permettant de trans-

former une image en niveaux de gris en une image binaire (dans laquelle tous les pixels

sont soit noirs, soit blancs). Nous supposerons, dans la suite, que chaque niveau de gris

est décrit par entier et qu’ils sont ordonnés de maniere croissante (c.-a-d. que la couleur

d’index 0 correspond a la couleur la plus claire et celle dont l’index est le plus grand a

la plus foncée).

La binarisation d’une image peut se réaliser simplement par seuillage des couleurs : le

pixel aux coordonées (x, y) dont la couleur est donnée par f (x, y) est transformé en une

valeur binaire par la fonction g suivante :

(cid:40)

1

0

si f (x, y) ≥ T

sinon

g(x, y) =

(1)

Dans la méthode utilisée dans la première partie de ce TP, la valeur de T est fixée, de

maniere arbitraire, a 120. Nous allons présenter une méthode permettant de déterminer

automatiquement un seuil (cid:28) optimal (cid:29) pour la binarisation des images : l’algorithme

d’Otsu.

Cette méthode est fondée sur l’analyse de l’histogramme de l’image. Cet histogramme

associe à chacun des 256 niveaux de gris possible de l’image le nombre de pixels ayant

cette couleur.

8 Écrivez une méthode int[] histogram() qui détermine l’histogramme d’une image.

Il est possible d’accéder a la couleur des pixels d’une image a l’aide du code suivant :

WritableRaster raster = img.getRaster();

int[] data = new int[img.getWidth() * img.getHeight()];

data = raster.getSamples(0, 0, img.getWidth(), img.getHeight(), 0, data);

où data est un tableau comportant autant d’éléments que l’image a de pixels,

chaque élément décrivant la couleur d’un pixel.

L’histogramme permet de déterminer p(c) la probabilité d’apparition de la ce couleur :

p(c) =

nc

n

(2)

où n est le nombre de pixels de l’image et nc le nombre de pixel de couleur c.

L’objectif est l’algorithme d’Otsu est d’utiliser l’histogramme pour répartir les différentes

couleurs dans deux groupes (on parle, techniquement, de classes) différents : l’un décrivant

l’arrière-plan de l’image et l’autre son premier plan.

La qualité d’une séparation des pixels en deux groupes par le seuil T peut être évaluée 1

par :

within(T ) = nB(T ) · σ2

σ2

B(T ) + nO · σ2

O(T )

(3)

1. Ce critère, ainsi que celui de l’équation (6) peuvent être justifiés dans un cadre statistique (cf.

l’étude des méthodes de clustering ou de partitionnement de données).

5

où :

— nB(T ) = (cid:80)T −1

i=0 p(i) est le nombre de pixels dans la premiere classe (c.-a-d. dont

la valeur est inférieure au seuil) ;

i=T −1 p(i) est le nombre de pixels dans la seconde classe ;

— nO(T ) = (cid:80)256

— σ2

— σ2

B(T ) est la variance des pixels de la première classe ;

O(T ) est la variance des pixels de la seconde classe ;

Pour mémoire, la variance d’une classe est définie comme la distance moyenne entre

l’ensemble des points d’une classe et la moyenne de celle-ci :

σ2

C =

µC =

1

N

1

N

(cid:88)

i∈C

N

(cid:88)

i∈C

(µ − p(i))2

p(i)

(4)

(5)

où C est l’ensemble des N points d’une classe.

Intuitivement, le critère décrit dans l’équation (3) est d’autant plus petit que les points

d’une classe sont proches de la moyenne de celle-ci et par conséquent que la séparation

entre les deux classes soient grandes.

Une fois ce critère défini, il suffit, pour chaque valeur possible de T de calculer la

qualité de la binarisation induite par ce seuil et de chercher le seuil de meilleur qualité

(c.-à-d. minimiser σ2

within(T )).

9 Implémenter la méthode permettant de trouver la valeur optimale de T selon le

critère d’Otsu.

La complexité (nombre d’opérations/calculs) de la méthode précédente peut-être for-

tement réduite en observant que minimiser σ2

within revient à maximiser :

between(T ) = σ2 − σ2

σ2

within(T )

= nB(T ) · nO(T ) (µB(T ) − µO(T ))2

(6)

(7)

10 Montrer que :

nB(T + 1) = nB(T ) + nT

nO(T + 1) = nO(T ) − nT

µB(T + 1) =

µO(T + 1) =

µB(T ) · nB(T ) + nT · T

nB(T + 1)

µO(T ) · nO(T ) − nT · T

nO(T + 1)

11 Modifier la méthode précédente pour calculer plus efficacement la qualité du par-

titionnement.

6