Kitabı oku: «Informationswissenschaft: Theorie, Methode und Praxis / Sciences de l'information: théorie, méthode et pratique», sayfa 5

Algorithmes de compression⁴

Décrire une image matricielle nécessite une grande quantité de données. En effet, puisqu’une image est composée d’un très grand nombre de pixels qui ont tous une couleur parmi un nombre de couleurs qui peut être gigantesque, le poids d’une image peut être très important. Par exemple, à une résolution de 300 ppp, ⁵ une image de 10 cm x 15 cm est composée de plus de 2 millions de pixels. Si chaque pixel peut avoir une couleur dans un ensemble de plus de 16 millions de couleurs (un cas tout-à-fait usuel pour les images naturelles), il est alors nécessaire de disposer de 24 bits par pixel.⁶ Un calcul montre que l’on obtient un fichier d’un poids de plus de 6 Mo.

C’est considérable, et cela pose la question du stockage des images lorsqu’elles sont en grande quantité, et aussi celle de leur transmission à travers un réseau. Pour y répondre, une intense activité de recherche est menée dans le domaine de la compression des données numériques. En effet, on peut (et il faut!) se demander s’il est possible de décrire une image de manière plus économique. Les succès dans ce domaine de recherche sont grands, et il est aujourd’hui courant de compresser efficacement les images matricielles avec toute sorte d’algorithmes de compression.

Essentiellement, il existe deux types d’algorithmes de compression: les algorithmes «sans perte», et les algorithmes «avec perte». Les algorithmes sans perte permettent de conserver la totalité de l’information originale, alors que les algorithmes avec perte ne permettent pas de retrouver l’image originale. L’utilisation de ce deuxième type d’algorithme permet des taux de compression spectaculaires.

Mais la compression est un sujet délicat dans le monde des archives et des bibliothèques puisqu’elle est souvent considérée comme un élément à éviter dans le cadre de l’archivage à long terme.⁷

De sorte à permettre une meilleure appréhension du sujet, quelques algorithmes simples et standards sont brièvement présentés dans la suite de cet article.

Pour ce faire, rappelons que toute information numérique se présente sous la forme d’une suite de 0 et de 1. Une telle suite est appelée un mot dans l’alphabet {0,1}. Le nombre de 0 et de 1 qui forment un mot est appelé la longueur de ce mot. Un algorithme de compression a comme objectif de remplacer un mot contenant une information d’intérêt par un mot d’une longueur plus faible. De plus, ce remplacement doit se faire sans perte d’information, ou avec une perte acceptable. Pour obtenir cet effet de compression, l’idée est de supprimer toutes les formes de redondance qui apparaissent.

Il est à noter qu’il est impossible de définir un algorithme de compression capable de remplacer n’importe quel mot par un mot de longueur plus faible. Plus précisément, cela est impossible sans perte d’information. En d’autres termes, pour tout algorithme de compression sans perte d’information, il existe au moins un mot que l’algorithme n’arrive pas à remplacer par un mot de longueur plus petite (en fait, il est possible de prouver que pour tout algorithme sans perte, il existe un nombre infini de mots qui ne peuvent pas être compressés en des mots de longueur plus faible).

Cela veut dire qu’avant de définir un algorithme de compression, il faut déterminer quel type d’information il s’agit de compresser. Certains algorithmes sont efficaces pour compresser du texte, alors que d’autres sont particulièrement efficaces pour compresser des images. Et parmi les algorithmes efficaces pour compresser les images, certains sont spécifiquement construits pour compresser des images qui représentent du texte en noir/blanc, alors que d’autres sont efficaces pour des images non-textuelles. En effet, tout type de données a un genre de redondance particulier dont il s’agit de tirer profit au mieux. Comme premier exemple, voyons l’algorithme de compression suivant.

Codage par plages – Run-length encoding (RLE)

Cet algorithme de compression vise typiquement les images en noir/blanc, ou tout autre type d’information dont la représentation numérique comporte une majorité de 0 (et de 1) qui se suivent. Par exemple, le mot 00000000000000000000000000000000111110000000001111000000000000000000000000

pourrait être une partie du codage d’une ligne de pixels dans une image qui représente du texte, en noir, sur un fond blanc. Les 1 représentent les pixels en noir, moins fréquents que les pixels en blanc. L’idée de l’algorithme RLE est de tirer profit des grandes plages de 0 (et de 1), en écrivant

32*05*09*04*24.

Ce mot doit être compris comme signifiant «32 zéros, puis 5 uns, puis 9 zéros, puis 4 uns, puis 24 zéros». En écriture binaire, il devient:

000111111000010000001000 1000001100010111;

sachant que l’on a simplement écrit les nombres 31,4,8,3,23 en binaire sur les 7 derniers bits de chaque groupe de 8 bits (les espaces sont là pour faciliter la lecture de ces groupes). Le premier bit de chaque groupe de 8 bits indique s’il s’agit d’une plage de 0 ou de 1. Il est évident que l’algorithme a effectivement permis d’obtenir un effet de compression: au lieu d’être écrite sur 74 bits, la même information a pu être compressée sur 40 bits.

La faiblesse évidente de cet algorithme réside dans le fait qu’il est incapable de compresser efficacement des mots qui contiennent peu de grandes plages de 0 et de 1. Dans ces cas, l’algorithme augmente la longueur des mots! Un autre point important est que la ligne originale de 0 et de 1 peut aisément être récupérée à partir du mot obtenu par cette méthode de compression. Il n’y a aucune perte d’information dans ce processus.

Codage de Huffman

Très souvent, chaque caractère d’un alphabet est codé avec le même nombre de bits. C’est le cas de la norme de codage ASCII, qui attribue 8 bits à chaque caractère textuel. C’est également le cas lorsque l’on code un ensemble de couleurs sans compression. On emploie fréquemment 24 bits pour coder une couleur. Toutefois, autant dans le cas d’un texte que d’une image, certains caractères apparaissent plus souvent que d’autres. L’idée de David Albert Huffman, en 1952, a été de coder les caractères apparaissant fréquemment avec un nombre plus faible de bits en suivant un processus rigoureux. Ainsi, le caractère apparaissant le plus souvent dans la langue française, «e», sera codé sur un seul bit lorsqu’il s’agit de coder des textes écrits dans cette langue.

Pour un texte particulier, il est possible que ce ne soit pas le caractère «e» qui apparaisse le plus souvent. Pour coder ce texte, il faudrait d’abord calculer les fréquences de chaque caractère pour en déduire le codage approprié. Deux difficultés se présentent dans cette situation. D’une part, pour que le décodeur puisse lire le texte, il faut que le codeur lui transmette la table de codage.⁸ Cela augmente le poids du fichier et réduit l’efficacité de la compression. D’autre part, le calcul préliminaire des fréquences augmente le temps de codage, ce qui peut être malvenu. Pour éviter ces deux difficultés, c’est une version adaptative du codage de Huffman qui est utilisée. L’idée est de commencer le codage sans utiliser de compression, et ensuite d’adapter la table de codage à chaque caractère codé. Cela se fait de façon à ce que le décodeur puisse reconstruire la table de codage au fur et à mesure du décodage, sans que le codeur n’ait besoin de lui fournir une information.

De la même manière, comme la fréquence d’apparition des couleurs dans une image dépend de celle-ci, c’est un codage adaptatif qui est souvent utilisé pour coder les images.

Compressions «Groupe 3» et «Groupe 4»

Ces deux algorithmes ont été pensés pour la transmission de documents en noir (l’information) et blanc (le papier) par fax. Ce sont des standards publiés par l’Union Internationale des Télécommunications (UIT), et leur dénomination officielle est UIT-T T.4 (compression «Groupe 3») et UIT-T T.6 (compression «Groupe 4»).⁹

La norme «Groupe 3» consiste en fait en deux algorithmes de compression différents: une compression unidimensionnelle et une compression bidimensionnelle. Le premier de ces algorithmes considère chaque ligne de pixels de manière indépendante des autres lignes, ce qui fait le caractère unidimensionnel de cette méthode. La compression se fait en deux temps. D’abord, il s’agit de procéder à un codage par plages, et ensuite c’est un codage de Huffman qui est appliqué en considérant chaque plage comme un caractère d’un alphabet. Il ne s’agit pas d’un codage adaptatif, mais d’un codage basé sur un set de documents représentatif défini par l’UIT. A titre d’exemple, le tableau de la figure 4 est une partie de la table de codage définie par le standard UIT-T T.4.

Figure 4: Extrait du Tableau 2/T.4 – Codes de terminaison¹⁰

La compression bidimensionnelle distingue différentes situations. Dans le meilleur des cas, il y a une forte redondance verticale en raison de la nature des documents visés (les documents transmis par fax) et l’idée est de coder une ligne de pixels par rapport à la ligne de pixels qui se trouve immédiatement au-dessus. Lorsqu’une telle redondance n’existe pas sur toute ou une partie d’une ligne, alors c’est le codage unidimensionnel décrit ci-dessus qui est employé. De plus, la compression «Groupe 3» est définie de sorte à pouvoir supporter des erreurs de transmission. Une des mesures prises dans ce cadre est le codage d’une ligne sur deux (ou sur quatre) selon la méthode unidimensionnelle, ce qui permet d’éviter qu’une seule erreur se propage dans toute la suite du document et le rende incompréhensible.

Cette façon de faire limite l’efficacité de la compression puisque l’algorithme renonce volontairement à exploiter la redondance verticale sur tout le document. Pour remédier à ce fait lorsqu’une résistance aux erreurs n’est pas nécessaire, la compression «Groupe 4» reprend le même processus que la compression bidimensionnelle «Groupe 3», en supprimant certains des mécanismes utiles dans des environnements propices aux erreurs. En particulier, l’entier du document est codé suivant le codage bidimensionnel, ce qui permet un taux de compression environ deux fois meilleur.

Algorithmes de compression basés sur un dictionnaire (algorithmes de la famille LZW)

Une famille d’algorithmes d’un type différent existe. Ce sont les algorithmes basés sur l’utilisation d’un dictionnaire. La stratégie consiste à parcourir le mot à compresser à la recherche de chaînes de caractères qui apparaissent dans un dictionnaire. Lorsqu’une telle chaîne de caractères est trouvée, elle est remplacée par le numéro d’index ¹¹ de la chaîne. Par exemple, admettons qu’il existe un dictionnaire pour le français contenant 99 999 mots au plus. Et supposons que le mot:

— «algorithme» arrive en 2415^ème position dans ce dictionnaire;

— «compression» arrive en 10 324^ème position;

— «de» arrive en 11 112^ème position;

— «dictionnaire» arrive en 12 956^ème position;

— «un» arrive en 74 454^ème position.

Dans ce cas, la phrase

«L’algorithme de compression LZW utilise un dictionnaire.» peut être codée de la manière suivante:

«L’*2’415*11 112*10 324*LZW*utilise*74 454*12 956*.», car «L’», «LZW», «utilise» et «.» ne se trouvent pas dans le dictionnaire considéré.

Examinons l’efficacité de cet algorithme. La phrase qu’il faut coder est constituée de 56 caractères. En utilisant le code ASCII, on constate que 448 bits sont requis pour coder ce texte. Calculons maintenant le nombre de bits nécessaires lorsque l’on profite du dictionnaire. Comme il faut 17 bits ¹² pour coder les nombres jusqu’à 100 000, on doit utiliser 18 bits pour coder les mots qui se trouvent dans le dictionnaire. En effet, il faut 1 bit supplémentaire pour indiquer si ce qui suit correspond à un index ou à un mot codé en ASCII. Les mots présents dans le dictionnaire étant au nombre de 5, cela nous donne 90 bits. De plus, les quatre chaînes de caractères codées en ASCII nécessitent respectivement 22,30,62 et 14 bits, puisqu’il faut 1 bit pour indiquer que ce qui suit est codé en ASCII, 5 bits pour indiquer la longueur du code ASCII, puis le code ASCII. On arrive à un total de 218 bits. On constate qu’il a effectivement été possible de compresser efficacement la phrase proposée.

Ci-dessus, c’est un dictionnaire traditionnel qui a été utilisé. Pour augmenter l’efficacité de l’algorithme, les dictionnaires utilisés contiennent en réalité des chaînes de caractères ¹³ qui n’ont pas nécessairement de signification. De plus, la conception à l’avance d’un dictionnaire peut être irréalisable lorsque les données ne sont pas des données textuelles. C’est typiquement le cas des images. Il n’est pas évident qu’il soit possible de trouver des arrangements de couleurs qui reviennent régulièrement dans toutes les images. Pour cette raison, il est nécessaire de définir des algorithmes capables de construire un dictionnaire différent pour chaque image. Pour éviter la transmission du dictionnaire entre le codeur et le décodeur de l’image, il s’agit de le construire selon une procédure permettant au décodeur de reconstruire le dictionnaire au fil du décodage.

Par exemple, le codeur peut démarrer avec un dictionnaire vide ou par défaut (constitué des lettres de l’alphabet par exemple). Ensuite, en cours de codage, le codeur cherche dans le dictionnaire le mot le plus long qui correspond à la chaîne de caractères qu’il doit coder. Supposons que la prochaine chaîne de caractères à coder soit «couleurs» mais que seul le mot «coule» soit déjà présent dans le dictionnaire. Dans ce cas, le codeur code uniquement le début, à savoir «coule», du mot «couleur», et le codeur précise que la lettre suivante est le u. Ensuite il ajoute le mot «couleu» au dictionnaire, et il s’attaque à la prochaine chaîne de caractères à coder. Dans notre cas, il s’agit de «rs» et de ce qui suit. Ainsi, le dictionnaire est en constante évolution, en fonction des redondances qui apparaissent.

Parmi les algorithmes faisant appel à une procédure de ce genre, on trouve les algorithmes précurseurs LZ77 et LZ78, publiés par A. Lempel et J. Ziv en 1977 et 1978 respectivement. Par la suite, une variante de ces algorithmes a été publiée en 1984 par T. Welch. Cet algorithme est connu sous le nom de LZW et est probablement le plus fameux des algorithmes de la famille LZ, qui regroupe les variantes de LZ77 et de LZ78.

Plutôt qu’une efficacité ciblée sur un type de donnée très particulier, les algorithmes de la famille LZ ont tendance à être efficaces sur des données de tout type. Cette caractéristique en fait un algorithme «tout-terrain», très utile lorsqu’il s’agit de compresser différents types de données ensemble. Toutefois, lorsqu’il s’agit de compresser un type de données bien précis, il existe souvent un algorithme plus efficace.

Algorithmes de compression JPEG, JPEG 2000 et JBIG2

Les méthodes de compression JPEG (pour les images en couleur; compression avec perte), JPEG 2000 (pour les images en couleur, compression sans ou avec perte) et JBIG2 (pour les images noir/blanc, compression sans ou avec perte) font appel à des mathématiques avancées, et ne peuvent donc être résumes dans le cadre du présent article. Ces algorithmes bénéficient de techniques récentes et sont particulièrement efficaces.

Gestion des couleurs

Pour certaines utilisations, les couleurs des images ne sont pas très importantes, voire superflues. Ainsi, la fidélité exacte des couleurs est sans valeur pour le lecteur intéressé uniquement par le texte d’un document. Pour ce genre d’usages, il peut même être avantageux de ne pas prendre en compte la couleur et de se contenter d’une numérisation en noir/blanc. Le poids des images numérisées en noir/blanc, nettement inférieur au poids des mêmes images numérisées en couleur, est un atout important. Dans le même genre de cas, l’impression est également une fonction pour laquelle une numérisation sans couleur peut être profitable. Par exemple, cela permet de réduire l’utilisation du toner des imprimantes.

Mais les bibliothèques et les archives peuvent tout à fait être confrontées à des situations dans lesquelles le respect des couleurs originales est important. Cela peut être le cas lorsqu’un utilisateur publie des images de documents. Par exemple, des images peuvent être publiées dans un catalogue d’exposition. Il peut aussi arriver que quelqu’un ait comme projet la création d’un fac-similé qui soit le plus fidèle possible au document original. Et si la numérisation a comme but de créer une copie pouvant remplacer le document original, alors la fidélité de la reproduction est primordiale. En effet, une institution patrimoniale peut estimer que certains originaux sont dans un tel état que la création d’une copie est nécessaire pour assurer la pérennité de l’information. Pour ces situations, il est nécessaire de savoir comment les formats d’images gèrent les couleurs.

Espace de couleurs et profil ICC

Aujourd’hui, de nombreux appareils gèrent des couleurs. Les imprimantes, les écrans, les appareils photographiques et les scanners sont dans ce cas. Dans le but de transmettre fidèlement les couleurs entre ces appareils, différents standards ont été émis par les organismes compétents. En l’occurrence, il s’agit de la Commission Internationale de l’Eclairage (CIE) et de l’International Color Consortium (ICC).

Le concept d’espace de couleurs est important. Un espace de couleurs est une correspondance définie entre un ensemble de couleurs et un ensemble de nombres. Cette correspondance permet de coder les couleurs avec des nombres. Plus précisément, il s’agit de faire correspondre un triple ¹⁴ de nombres à chaque couleur. Par exemple, l’espace RVB (RGB en anglais) décompose une couleur C en un rouge R, un vert V et un bleu B. A la couleur C est associé le triple (r, v, b) où r est le nombre associé à la couleur R, v est le nombre correspondant à la couleur V et b est le nombre décrivant la couleur B. Concrètement, (255,0,0) correspond au rouge primaire alors que (110,11,20) décrit la couleur grenat.¹⁵ Il est toutefois nécessaire d’être très prudent: il existe un grand nombre d’espaces RVB. Parmi les espaces de ce type qui sont souvent utilisés se trouvent sRGB et Adobe RGB (1998).

Cela veut dire qu’un même triple peut très bien correspondre à des couleurs différentes en fonction de l’espace de couleurs considéré. De plus, deux espaces différents ne couvrent pas nécessairement le même gamut.¹⁶ Par exemple, l’espace de couleurs sRGB a un gamut plus petit que l’espace Adobe RGB (1998), ce qui veut dire qu’il existe des couleurs que l’on peut décrire dans l’espace Adobe RGB (1998) alors qu’elles ne peuvent pas être décrites par l’espace sRGB.

Examinons un cas concret qui rappelle que chaque appareil gère son propre espace de couleurs. Prenons le cas d’un utilisateur qui visionne sur un écran une image numérisée à l’aide d’un scanner. Supposons que certains pixels de l’image aient été codés comme du rouge primaire par le scanner: (255,0,0) dans l’espace de couleurs RVB du scanner. Si cette image est fournie sans aucune précaution, l’écran affichera le rouge primaire (255,0,0) correspondant à son propre espace RVB. Et cet espace n’a aucune raison d’être le même que celui du scanner. Par conséquent, l’image que l’utilisateur visionne sur l’écran ne correspond pas, en termes de couleurs, au document qui a été numérisé.

De sorte à pouvoir maintenir la fidélité des couleurs tout au long d’une chaîne allant de la production des images à leur visualisation, on utilise un espace de couleurs intermédiaire et standardisé. Différents espaces de couleurs standardisés par la CIE existent. Par exemple, CIE L*a*b*, datant de 1976, est un tel espace. Ce standard décrit l’ensemble des couleurs qu’un humain perçoit. De plus, cet espace est conçu pour que la distance mathématique entre deux triples associés à deux couleurs corresponde à la différence de perception visuelle entre ces deux couleurs. A titre d’exemple, il y a la même différence de perception entre les couleurs représentées par (50,100,150) et (50,100,200) et entre les couleurs représentées par (50,100,200) et (50,150,200).

L’existence d’un tel espace standard permet de respecter les couleurs tout au long d’une chaîne. Mais pour cela il faut introduire le concept de profil ICC, introduit par l’ICC et reconnu conjointement par l’Organisation Internationale de normalisation (ISO) et par l’ICC (ISO 15076–1). Un profil ICC établit la correspondance entre un espace de couleur d’intérêt (par exemple celui d’un scanner ou d’un écran) et un espace de couleur standardisé (CIE L*a*b* par exemple).

Retournons à l’exemple de l’utilisateur qui visionne sur un écran une image numérisée par un scanner. Cette fois, supposons que le scanner est muni d’un profil ICC. De même, supposons que l’écran dispose de son propre profil ICC. A nouveau, regardons le cas du pixel dont la couleur est codée (255,0,0) par le scanner. Lorsque l’écran affiche ce pixel, il va suivre le processus suivant: il cherche d’abord à quelle couleur dans l’espace CIE L*a*b* correspond (255,0,0), en utilisant le profil ICC du scanner. Appelons «rouge» cette couleur. Puis il s’agit de voir à quoi correspond ce «rouge» dans l’espace de couleurs de l’écran, en utilisant le profil ICC de ce dernier. Ce pourrait être (252,10,15) par exemple. Maintenant, le respect des couleurs est assuré tout au long de la chaîne!

Comme le rouge, codé (255,0,0), du scanner pouvait être représenté par l’écran, il a été possible de conserver cette couleur sur le chemin entre le scanner et l’écran. Toutefois, il peut arriver que le gamut de l’écran ne contienne pas le rouge indiqué par le scanner. Dans un tel cas, l’écran affiche le rouge le plus «proche» possible.

Pour que ce qui précède puisse fonctionner, il est nécessaire que les logiciels permettant l’affichage d’une image aient accès au profil ICC du scanner. Pour cela, il y a deux possibilités. L’une est d’intégrer le profil dans le fichier de l’image. Pour ce faire, il faut que l’image matricielle soit codée dans un format qui permet d’intégrer le profil ICC du scanner. La solution alternative est d’indiquer l’endroit où les logiciels peuvent trouver le profil ICC, sauvegardé de manière indépendante.

Il semble que la solution qui s’est imposée soit celle de l’intégration du profil ICC dans le fichier de l’image. Cette solution a l’avantage de lier le profil avec l’image. Cela permet de faciliter la gestion de la correspondance entre les images et le profil ICC du scanner lors de l’échange d’images, mais aussi dans le cours de l’archivage. A l’inverse, il y a aussi un désavantage puisque l’on constate que le même profil est susceptible d’être conservé en de multiples copies. Ce qui augmente légèrement l’espace de stockage nécessaire. A titre d’illustration, remarquons que la Bibliothèque de Genève (BGE) conserve actuellement plus de 800 000 images dans le cadre du projet e-rara. Chacune de ces images contient un profil ICC, alors que seuls 5 profils différents ont été utilisés. Sur la base d’un poids moyen de 265 Ko par profil ICC, il en résulte un poids supplémentaire d’environ 200 Go. Ce poids correspond approximativement à 1,5 % du poids total des 800 000 images, ce qui donne la mesure de l’économie qui pourrait être réalisée en n’intégrant pas les profils dans les images.