Un format d'image simple et révolutionnaire.

Sans nécessairement en être conscient, la compression d’image est l'une des technologies centrales du monde actuel. Entre le web, les jeux vidéo, ou encore nos photothèques personnelles, nous sommes bombardés de centaines d'images chaque jour. Il est primordial que les images soient les plus petites possibles, sans toutefois perdre d'informations. Cela évitera de surcharger nos espaces de stockage ainsi que le réseau internet.

Dite bienvenue à FST ⎯ FaST Format Image ⎯, un nouveau format d’image révolutionnaire. FST est en fait un algorithme de compression sans perte ultra rapide pouvant compresser une image de façon équivalente à PNG, mais jusqu’à 20x plus rapidement.

Pourquoi utiliser FST?

FST tente d'arriver à un équilibre entre taux de compression et vitesse d'encodage/de décodage. En raison de sa rapidité, cet algorithme est moins demandant en ressources que d’autres formats comme PNG. Ce faisant, FST est idéal pour les applications où le nombre de ressources est limité.

Les systèmes embarqués sont souvent moins puissants que nos ordinateurs personnels. Encoder une image peut prendre de longues secondes ou minutes sur ces systèmes moins puissants. FST est idéal, car il offre le meilleur des mondes, un temps d’encodage réduit tout en gardant le même taux de compression que les techniques actuelles.

Les jeux vidéo, où la puissance de calcul est à un premium, seraient aussi un très bon candidat pour FST. En effet, ils doivent décoder un grand nombre d’images en permanence. Un outil tel que celui proposé pourrait donc améliorer la performance de ces jeux en réduisant la charge de calcul du décodage d’image.

Comment FST fonctionne?

FST a initialement été inspiré par QOI et réutilise plusieurs idées de ce dernier. Tout comme QOI, la compression s'effectue sur des pixels RGB. FST apporte cependant trois nouvelles méthodes pour améliorer le taux de compression.

À l’échelle macroscopique, l’algorithme tente d’encoder chaque pixel individuel avec le moins de bits possible. L'algorithme de compression reste simple et se déroule en trois étapes distinctes: la normalisation, le regroupement par blob et l’encodage des pixels restants en blocs.

Une image FST débute toujours par un en-tête. Celui-ci contient différentes informations sur l'image elle-même. L'en-tête est suivi de blocs qui représentent les pixels de l'image.

Un bloc est un pixel ou un groupe des pixels encodés d'une certaine façon. Un bloc débute toujours par un code qui sert à identifier son type. Le code est suivi d'une valeur qui décrit un ou des pixels. Les différents types de blocs seront vus plus loin.

La normalisation

La compression FST débute toujours par la normalisation des pixels. Cette phase tente de réduire la variation des couleurs des pixels de l'image sans perdre d'informations. Pour se faire, la valeur des canaux des pixels est rapprochée de zéros. Plus la valeur des canaux approche de zéro, plus l'image sera facile à compresser.

Une caractéristique importante des images est utilisée pour réaliser la normalisation: dans une image, deux pixels adjacents ont généralement une valeur similaire. Faire la différence de deux pixels adjacents rapprochera donc généralement les valeurs des pixels de zéro.

FST réalise ainsi la normalisation de la façon suivante: un pixel se voit soustraire à sa valeur, la valeur du pixel précédent. Cette étape est répétée pour tous les pixels d'une image.

(a) L'image d'origine. (b) L'image une fois la différence calculée.

L'image originale (à gauche), contient beaucoup plus de variation que l'image normalisée (à droite).

Le regroupement

Une fois la normalisation réalisée, une phase de regroupement est effectuée. Cette étape consiste à regrouper les pixels adjacents de couleur identique ensemble.

Les regroupements de pixels seront décomposés en rectangle qui eux pourront être décrits facilement. Pour réaliser cette décomposition, la méthode de décomposition proposée par Spiliotis et Mertzios est utilisée.

Les rectangles trouvés sont plus petits à représenter que si chaque pixel les formant était compressé et représenté séparément. Les rectangles seront enregistrés directement dans l'en-tête de l'image.

(a) L'image normalisée. (b) L'image normalisée avec les groupements

Il en va de soi que le regroupement de pixels est généralement plus efficace pour les captures d’écran et les images numériques.

L’encodage (okish)

Les pixels qui ne forment pas de regroupement seront encodés lors de cette dernière étape. On nomme un pixel encodé un bloc. Sept types de blocs sont à la disposition de l’algorithme. Chaque type de bloc encode différemment un même pixel. Un bloc débute par un code de deux, trois ou quatre bits. Ce code sert à identifier le type de bloc et donc la façon dont il doit être encodé. Le code est suivi d'une valeur représentant le pixel.

Type	Code	Taille du bloc
Déplacement (Offset)	0b00	10 bits
Palette (Palette)	0b01	10 bits
Répétition (Repeating)	0b100	9 bits
Gris (Gray)	0b101	10 bits
Pixel Court (Short)	0b110	10 bits
Pixel Moyen (Medium)	0b1110	10 bits
Pixel Long (Long)	0b1111	10 bits

Les blocs les plus fréquents ont les codes les plus courts et inversement pour les blocs moins fréquents.

Puisque chaque bloc a une taille fixe selon son type, les blocs sont simplement disposés les uns à la suite des autres. Les blocs sont placés directement à la suite de l'en-tête.

Les prochaines sections décrivent les différents types de blocs utilisés par FST.

La répétition (repeating)

Pour différentes raisons, l'étape de regroupement ne regroupe pas tous les pixels identiques adjacents ensemble. Un bloc de répétition est donc nécessaire. La répétition encode une série de plusieurs pixels de même couleur en deux blocs. Le premier encode la couleur de la répétition alors que le second encode le nombre de pixels dans l'enchainement. Le premier bloc est encodé à l'aide d'un des six autres types de blocs.

La répétition est représentée sur six bits, cela signifie que le nombre maximum de récurrences ne doit pas dépasser 64. Lorsque le nombre de récurrences excède 64, un nouveau bloc de répétition est inséré directement après le premier.

L'écart (offset)

Pendant l'encodage d'une image, un tampon de la valeur des 256 pixels précédents est gardé en mémoire. Dans le cas où un pixel a la même valeur que l'un des pixels du tampon, le bloc de l'écart est utilisé. Celui-ci encode la distance entre le pixel encodé et le pixel avec une valeur identique.

Le bloc de l'écart utilise une propriété des images. Pour une région donnée d'une image, plusieurs pixels non consécutifs ont souvent la même valeur. Indiquer une distance avec un pixel précédent est donc bénéfique pour ne pas encoder une même couleur à répétition.

L'écart est encodé sur huit bits, c'est pourquoi le nombre de pixels gardés en mémoire est 256.

Gris (gray)

L'une des conséquences de l'étape de la normalisation est la transformation d'une grande partie des pixels en tons de gris. La couleur grise est représentée par une même valeur dans les trois canaux (rouge, vert, bleu). Lorsqu'un pixel est une nuance de gris, stocker la valeur de seulement un des canaux est possible.

Ce bloc encode la valeur du canal sur deux bits, cela signifie que la valeur de chacun des canaux doit être entre -2 et 1. Cela peut sembler comme très restrictif, cependant, grâce à la normalisation, la majorité des nuances de gris entre dans cette fourchette de valeurs.

Palette (palette)

Dans une image, il arrive souvent qu'un petit nombre de couleurs reviennent très fréquemment. Une palette de couleur est donc utilisée pour encoder ces couleurs très fréquentes.

La palette est créée à partir des 16 couleurs les plus fréquentes de l'image. L'assortiment de couleurs est créé à partir d'un échantillon de l'image. En effet, trouver la fréquence de chacune des couleurs dans l'image serait trop long. Chacune des couleurs est numérotée entre 0 et 15.

Lorsqu'une couleur est présente dans la palette, le bloc palette est utilisé et encode le numéro de la couleur.

Pixel (short, medium et long)

Dans le cas où aucun autre type de bloc convient, la valeur des canaux d'un pixel est directement encodé dans un bloc. Lorsque cette catégorie de bloc est utilisée, FST encode simplement les valeurs des canaux du pixel, les uns à la suite des autres.

Pour optimiser la grosseur du fichier, trois tailles de blocs existent. La taille est la seule différence entre les blocs short, medium et long.

Si tous les canaux d'un pixel peuvent être représentés en moins de quatre bits, le pixel sera encodé comme un short. Si tous les canaux peuvent être représentés en moins de six bits, un bloc medium sera utilisé. Pour tous les autres cas, un bloc long est utilisé.

À cause de l'étape de la normalisation, la valeur des canaux peut varier entre -255 et +255. Cette fourchette de valeur peut seulement être représentée sur neuf bits. Pour cette raison, le bloc long est toujours représenté avec neuf bits par canal.

En-tête

L'en-tête du fichier compressé stocke l'information nécessaire à la décompression du fichier. Celui-ci contient le type d'image, la taille de l'image, la palette utilisé, les regroupements présents et la version de l'algorithme.

Toutes ces informations sont nécessaire pour reconstituer l'image ainsi pouvoir l'afficher à l'écran.

Récapitulatif

Contrairement à QOI qui se concentre sur la vitesse d'encodage, FST ou PNG sur le taux de compression, FST est un entre deux. FST est un équilibre entre la vitesse de compression et le taux de compression. Bien qu'il soit plus rapide que PNG (mais bien moins que QOI), il produit un taux de compression semblable à celui que PNG offre.