Skip to content

1-1-5 Représentation d’images

Il existe de nombreux formats permettant de stocker et manipuler des images, les plus utilisés étant sans doute le JPEG1 (“Information Technology – Digital Compression and Coding of Continuous-Tone Still Images : Requirements and Guidelines” 1994), le PNG2 (“Information Technology – Computer Graphics and Image Processing – Portable Network Graphics (PNG) : Functional Specification” 2004) ou le TIFF3 (on pourrait encore citer des formats historiques comme le GIF ou le BMP…) Ces formats sont utilisés par les sites webs, par les appareils photos numériques, etc. Tous ces formats représentent des images de type bitmap4, et suivent le même principe de base. Une image y est vue comme une matrice de points, appelés pixels (contraction de l’anglais picture elements), qui sont indivisibles, et monochromatiques. Ce sont les éléments de base constitutifs d’une image. La couleur de chaque pixel peut (comme on l’a fait pour les caractères) alors être représentée par un naturel selon un encodage fixé a priori. Par exemple, sur \(8\) bits on pourra avoir une palette de 256 couleurs, ou 256 niveaux de gris… On peut alors représenter l’image comme la suite des encodages binaires de chacun des pixels, la matrice étant lue ligne par ligne (par exemple). Un fichier contenant une image contiendra en général d’autres informations utiles (commes les dimensions de l’image).

Les formats d’images utilisés en pratique comme JPEG ne se contentent pas de stocker la suite des pixels de l’image, mais appliquent aussi des techniques de compression pour réduire l’espace nécessaire pour stocker cette information (“Information Technology – Digital Compression and Coding of Continuous-Tone Still Images : Requirements and Guidelines” 1994). Notons enfin qu’une vidéo n’est jamais qu’une séquence d’image fixes. Les concepts développés ici s’appliquent donc aux différents formats (MPEG, AVI, etc) utilisés pour encoder des images en mouvement.

Détection et correction d’erreurs

Lorsque les informations sont stockées ou transmises, il arrive parfois que des erreurs soient introduites (par exemple, sur un réseau non-fiable). Il est alors utile de développer des techniques de représentation de l’information qui permettent au récepteur de détecter la présence d’erreurs éventuelles (auquel cas, il peut demander une re-transmission), voire de les corriger par lui-même. Nous allons maintenant étudier deux de ces techniques. Elles sont toutes les deux basées sur le même principe : introduire de la redondance dans l’information transmise, de manière à pouvoir détecter un nombre restreint d’erreurs, voire reconstituer l’information d’origine.

Bit de parité

Cette technique est sans doute la première à avoir été mise en œuvre. Elle consiste à ajouter, à toute information transmise, un bit (appelé bit de parité) qui indique si le nombre de bits à \(1\) dans l’information à représenter est impair (bit de parité à \(1\)) ou pair (bit de parité à \(0\)). Ainsi, si un seul bit est modifié, la parité change nécessairement, et cette erreur peut être détectée (mais pas corrigée car on n’a pas de moyen d’identifier le bit qui a été modifié).

Plus précisément, étant donnée une information binaire

\[b_{n-1}\cdots b_0,\]

on lui associé le bit de parité (ou bit de contrôle) \(b_c\) calculé de la manière suivante :

\[b_c=b_{n-1} \,\mathit{XOR}\, b_{n-2}\cdots \,\mathit{XOR}\, b_0.\]

On peut vérifier que \(b_c=1\) si et seulement si le nombre de bits à \(1\) parmi \(b_{n-1}\),…, \(b_0\) est impair.

Exemple :

Fixons \(n=7\). Si l’information considérée est \(011\ 1111\) (ce qui correspond par exemple au caractère ASCII ?, voir la figure donnant la table ascii), on a le bit de contrôle \(b_c=0\). On obtient alors l’octet \(0011\ 1111\), en supposant que le bit de contrôle est le bit de poids fort.

Supposons maintenant que la donnée soit modifiée en \(0011\ \mathbf{0}111\) (le bit \(b_3\) a été inversé), suite à une erreur. On peut calculer la parité de l’information reçue \(0 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 0 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 1=1\), et constater que ce n’est pas le bit de contrôle reçu. On a donc détecté une erreur. Si, par exemple, l’information a été transmise sur un réseau, on peut demander une retransmission.

Supposons maintenant qu’une erreur ait lieu sur le bit de parité : la valeur \(\mathbf{1}011\ 1111\) est reçue. À nouveau, une erreur est détectée, même si l’information à proprement parler est correcte.

Supposons maintenant que deux erreurs ont lieu : \(0011\ \mathbf{00}11\). On voit que le bit de contrôle calculé est \(0\), ces deux erreurs ne seront donc pas détectées.

\(\blacksquare\)

On peut facilement se convaincre que la technique du bit de parité permet de détecter un nombre impair d’erreurs, mais ne permet d’en corriger aucune car rien ne permet d’identifier le bit qui a été altéré.

Code de Hamming

Le code de Hamming est en fait une famille de codes dont la version de base (appelée Hamming\((7,4)\) et que nous allons étudier ici) a été introduite dans les années 1950 (Hamming 1950) par Richard Hamming5, pour détecter et corriger des erreurs qui avaient lieu lors de la lecture de cartes et de rubans perforés.

Ce système est plus puissant que le bit de parité : il permet de corriger les erreurs de transmission, à condition que celles-ci affectent au maximum 1 bit. Naturellement, pour arriver à ce résultat, il faudra utiliser plus d’un bit de contrôle.

Pour expliquer le code de Hamming, nous allons changer quelque peu nos conventions et numéroter les bits à partir de \(1\). Nous allons considérer, pour l’exemple, des représentations (information et bits de contrôle) sur \(7\) bits, mais ces principes se généralisent aisément. Sur ces \(7\) bits, tous les bits dont le numéro est une puissance de \(2\) (donc, les bits \(1\), \(2\) et \(4\)) sont des bits de contrôle (\(C_i\)), les \(4\) bits restants sont des bits de données (\(D_i\)) :

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&2&3&4&5&6&7\\ \hline C_1&C_2&D_3&C_4&D_5&D_6&D_7\\ \hline \end{array}\]

Chacun des bits de contrôle sera en fait un bit de parité, mais ne portera pas sur tous les bits de données (sans quoi il serait inutile d’avoir plusieurs bits de contrôle qui auraient tous la même valeur). Au contraire, nous allons associer les bits de contrôle à des bits de données bien choisis, de manière à pouvoir reconstituer le numéro du bit erroné en cas d’erreur. Nous effectuons cette association de la manière suivante

Note :

Dans le code de Hamming, le bit de contrôle \(C_i\) est un bit de parité pour tous les bits de données \(S_j\), tels que le bit de poids \(i\) est à 1 dans l’expression binaire de \(j\).

\(\square\)

Quand un bit \(C_i\) est un bit de parité pour un bit de donnée \(D_j\), nous dirons que “\(C_i\) vérifie \(D_j\)”.

Élucidons cette définition dans le cas où \(n=7\). Les représentations binaires de numéros des bits de donnée sont les suivants \(011=3_{10}\), \(101=5_{10}\), \(110=6_{10}\) et \(111=7_{10}\). Donc, le bit de donnée \(3\) est vérifié par les bits de contrôle \(2\) et \(1\) (car en effet \(1+2=3\)), le bit de donnée \(5\) est vérifié par \(4\) et \(1\) (\(4+1=5\)), le bit de donnée \(6\) est vérifié par \(4\) et \(2\) (\(4+2=6\)) et le bit de donnée \(7\) est vérifié par \(4\), \(2\) et \(1\) (\(4+2+1=7\)). On peut donc observer les deux propriétés suivantes, qui découlent de la définition des bits de contrôle et qui seront cruciales dans la suite pour corriger les erreurs :

  1. quand on fait la somme des numéros des bits de contrôle qui vérifient un bit de donnée \(D_j\), on retrouve cette valeur \(j\) ;

  2. chaque bit de donnée est vérifié par au moins \(2\) bits de contrôle. Cela provient du fait que les numéros de bits de données ne sont pas des puissances de \(2\), leur représentation en binaire comprend donc au moins deux bits à \(1\).

On peut ré-exprimer la relation entre les bits de contrôle et les bits de données de la façon suivante, ce qui nous permet de calculer directement les bits de contrôle :

  • le bit de contrôle \(C_1\) vérifie les bits de données \(D_3\), \(D_5\) et \(D_7\) ;

  • le bit de contrôle \(C_2\) vérifie les bits \(D_3\), \(D_6\) et \(D_7\) ;

  • le bit de contrôle \(C_4\) vérifie les bits \(D_5\), \(D_6\) et \(D_7\).

Par exemple le bit de contrôle \(C_2\) est un bit de parité pour \(D_3\), \(D_6\) et \(D_7\), donc

\[C_2=D_3 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7.\]

Mettons ces idées en pratique sur un exemple :

Exemple :

Supposons que nous ayons la donnée \(1011\) :

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline C_1&C_2&D_3&C_4&D_5&D_6&D_7\\ \hline &&1&&0&1&1\\ \hline \end{array}\]

En appliquant le développement ci-dessus, nous obtenons :

\[\begin{array}{rclllll} C_1 &= &D_3 \,\mathit{XOR}\, D_5 \,\mathit{XOR}\, D_7 &= &1 \,\mathit{XOR}\, 0 \,\mathit{XOR}\, 1 &= &0;\\ C_2 &= &D_3 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7 &= &1 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 1 &= &1;\\ C_4 &= &D_5 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7 &= &0 \,\mathit{XOR}\, 1 \,\mathit{XOR}\, 1 &= &0. \end{array}\]

La représentation de la donnée accompagnée de son code de Hamming est donc :

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline C_1&C_2&D_3&C_4&D_5&D_6&D_7\\ \hline 0&1&1&0&0&1&1\\ \hline \end{array}\]

\(\blacksquare\)

Cette technique de codage permet non seulement de détecter une erreur mais également de la corriger. Nous pouvons aisément nous convaincre du fait qu’on peut détecter une erreur (c’est-à-dire le fait qu’un seul bit soit inversé), en constatant que chaque bit de donnée est vérifié par au moins un bit de parité parmi \(C_1\), \(C_2\), \(C_3\). Or, nous savons déjà que la technique du bit de parité permet de détecter tout changement d’un seul bit.

En ce qui concerne la correction de l’erreur, supposons que celle-ci est unique. Nous avons alors deux cas à considérer:

  • soit cette erreur a lieu sur un bit de donnée, \(D_j\). Dans ce cas, tous les bits de contrôle qui vérifient \(D_j\) auront une valeur qui ne correspond pas à la donnée vérifiée. Il suffit dès lors de faire la somme des numéros de ces bits de vérification pour retrouver la valeur \(j\) (cfr. la première des deux propriétés énoncés ci-dessus).

  • soit cette erreur a lieu sur un bit de contrôle \(C_i\). Dans ce cas, ce bit sera le seul à poser problème, et nous saurons donc qu’il n’y a pas d’erreur dans les données (sans quoi il y aurait au moins deux bits de contrôle problématiques, selon la seconde propriété énoncée ci-dessus).

Exemple :

Continuons l’exemple ci-dessus et imaginons qu’il y ait une erreur sur le bit \(D_3\), soit :

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline C_1&C_2&D_3&C_4&D_5&D_6&D_7\\ \hline 0&1&\mathbf{0}&0&0&1&1\\ \hline \end{array}\]

Re-faisons le calcul de chacun des bits de contrôle :

Bit \(C_1\) : le calcul de \(D_3 \,\mathit{XOR}\, D_5 \,\mathit{XOR}\, D_7\) donne \(1\), au lieu de \(0\) ;

Bit \(C_2\) : le calcul de \(D_3 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7\) donne \(0\) au lieu de \(1\) ; et enfin

Bit \(C_4\) : le calcul de \(D_5 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7\) donne \(0\), ce qui est bien la bonne valeur.

Il y a donc des problèmes avec les bits de contrôle \(C_1\) et \(C_2\). On en déduit que le bit erroné est le bit \(D_j\) avec \(j=1+2=3\). On peut donc re-constituer la donnée d’origine en inversant le bit \(D_3\).

Continuons toujours le même exemple et supposons qu’il y ait une erreur sur le bit de contrôle \(C_2\), soit :

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline C_1&C_2&D_3&C_4&D_5&D_6&D_7\\ \hline 0&\mathbf{0}&1&0&0&1&1\\ \hline \end{array}\]

Re-faisons le calcul de chacun des bits de contrôle :

Bit \(C_1\) : le calcul de \(D_3 \,\mathit{XOR}\, D_5 \,\mathit{XOR}\, D_7\) donne \(0\), ce qui est bien la bonne valeur ;

Bit \(C_2\) : le calcul de \(D_3 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7\) donne \(0\) au lieu de \(1\) ; et enfin

Bit \(C_4\) : le calcul de \(D_5 \,\mathit{XOR}\, D_6 \,\mathit{XOR}\, D_7\) donne \(0\), ce qui est bien la bonne valeur.

Il y a donc un problème sur le bit \(C_2\) uniquement, c’est donc lui qui est erroné et la donnée est donc transmise correctement.

\(\blacksquare\)

Applications des codes correcteurs d’erreur

Comme nous l’avons déjà évoqué, le bit de parité est une technique qui a largement été utilisée pour détecter des erreurs lors de la transmission de données en ASCII sur des lignes téléphonique ou des réseaux informatiques. Le code de Hamming a initialement été développé pour détecter et corriger des erreurs lors de la lecture de cartes perforées.

On pourrait croire que les progrès technologiques ont diminué voire supprimé la nécessité des codes correcteurs d’erreur. Il n’en est rien, nous sommes encore aujourd’hui confrontés à une série d’applications où la transmission d’information fait l’objet d’erreurs. Prenons deux exemples :

  1. La lecture d’un CD ou d’un DVD est un processus délicat, car le rayon LASER qui doit lire la surface du disque est très fin, et car le disque lui-même est souvent couvert de poussières, de griffes, voire de traces de doigts… De nombreuses erreurs de lecture ont donc lieu en permanence…

  2. Avec l’âge des smartphones, une nouvelle famille de code barres, appelés codes matriciels, ont fait leur apparition. Les plus célèbres sont les codes QR (la figure suivante donne un exemple) qui ont été inventés dans les années 1990 au Japon pour simplifier la logistique de pièces automobiles, et ont depuis été standardisés (“Information Technology – Automatic Identification and Data Capture Techniques – QR Code Bar Code Symbology Specification” 2015). À nouveau, les conditions de lecture de ces codes ne sont pas toujours idéales, et de nombreuses erreurs de lecture ont lieu (c’était d’ailleurs déjà le cas avec les code à barre “classiques” unidimensionnels que l’on retrouve aujourd’hui sur tous les emballages de produits manufacturés).

Ces deux exemples ont en commun la technique utilisée pour détecter et corriger les erreurs, à savoir les codes de Reed6 et Salomon7, introduits en 1960 par ces deux auteurs (Reed and Solomon 1960). Nous n’allons pas expliquer ici comment ils fonctionnent, cela nous emmènerait trop loin… mais ces deux exemples montrent que les codes détecteurs et correcteurs d’erreur restent importants. Ils font d’ailleurs encore l’objet d’une recherche active.

image image

Conclusion: sémantique d’une représentation binaire

Cette section nous a convaincu que tous les types d’information manipulés par l’ordinateur peuvent être représentés uniquement à l’aide de \(0\) et de \(1\). Il est maintenant naturel de se poser la question inverse, à savoir “quel est le sens à associer à une représentation binaire donnée ?”

Exemple :

La représentation binaire \(1000\ 0001\) s’interprète comme \(129_{10}\) si on considère des nombres non-signés, comme \(-1_{10}\) si on considère le bit de signe, comme \(-127_{10}\) si on considère le complément à deux, comme le caractère “ü” si on considère qu’on a affaire à un caractère ASCII étendu…

\(\blacksquare\)

La réponse à cette question est que rien ne permet, a priori, de décider quelle interprétation donner à une séquence binaire particulière. C’est le contexte, et en particulier le programme qui est exécuté sur ces données, qui leur donne un sens. Nous le prouvons à l’aide du programme C++ de la figure suivante. Il consiste à placer la même représentation binaire (sur 32 bits) dans trois variables x, y et z différentes, qui ont des types différents. Cela signifie que les instructions machines qui seront in fine exécutées pour afficher ces variables (instructions std::cout << à la fin du programme) seront différentes. Dans le cas la variable x, la représentation binaire sera interprétée comme un entier signé en complément à deux ; dans le cas de la variable y, la représentation binaire sera interprétée comme un entier non-signé ; et dans le cas de la variable z, la représentation binaire sera interprétée comme un caractère (les 24 bits de poids fort seront donc ignorés).

#include <iostream>

int main() {
    int x ; // x est un entier signe (complement a  deux)
    unsigned int y ; // y est un entier non negatif
    char z ; // z est un caractere

    // Toutes ces variables tiennent sur 32 bits

    // On place la meme valeur de 32 bits dans les 3 variables
    // avec le bit de poids fort valant  1
    // 1000 0000  0000 0000  0000 0000  0010 1111

    x = 0b10000000000000000000000000101111 ;
    y = 0b10000000000000000000000000101111 ;
    z = 0b10000000000000000000000000101111 ;

    // L'affichage des trois valeurs est different
    // L'affichage tient compte du type: ce sont les
    // instructions qui donnent leur semantique aux
    // valeurs representees en binaire.

    std::cout << x << std::endl ;

    std::cout << y << std::endl ;

    std::cout << z << std::endl ;

}

La sortie du programme confirme cela :

-2147483601
 2147483695
 /

Hamming, Richard W. 1950. “Error Detecting and Error Correcting Codes.” Bell System Technical Journal 29 (2): 147—160.

“Information Technology – Automatic Identification and Data Capture Techniques – QR Code Bar Code Symbology Specification.” 2015. International Organization for Standardization. https://www.iso.org/standard/62021.html.

“Information Technology – Computer Graphics and Image Processing – Portable Network Graphics (PNG): Functional Specification.” 2004. International Organization for Standardization. https://www.iso.org/standard/29581.html.

“Information Technology – Digital Compression and Coding of Continuous-Tone Still Images: Requirements and Guidelines.” 1994. International Organization for Standardization. https://www.iso.org/standard/18902.html.

Reed, Irving S., and Gustave Solomon. 1960. “Polynomial Codes over Certain Finite Fields.” Journal of the Society for Industrial and Applied Mathematics 8 (2): 300–304.


  1. Voir https://jpeg.org/ 

  2. Voir: http://www.libpng.org/pub/png/ 

  3. Voir: https://www.loc.gov/preservation/digital/formats/fdd/fdd000022.shtml 

  4. Notons qu’il existe d’autres formats, comme le SVG, qui représentent les images sous formes de points connectés par des lignes ou des courbes décrites de manière mathématique. Ces formats ont l’avantage de permettre des agrandissements sans perte de qualité. 

  5. Né le 11 février 1915 et mort le 7 janvier 1998 , Richard Hamming est un mathématicien américain, récipiendaire du prix Turing en 1968, qui a travaillé entre autres pour le projet Manhattan et aux laboratoires des Bell Labs. 

  6. Irving Reed, né le 12 novembre 1923, et mort le 11 septembre 2012, est un mathématicien et ingénieur américain, qui a enseigné à l’University of Southern California, É-U d’Amérique. 

  7. Gustave Solomon, né le 27 octobre 1930 et mort le 31 janvier 1996 est un mathématicien et ingénieur américain, qui a travaillé pour la Hughes Aircraft Company