SPECIFICATIONS CVC (document présent dans le zip)
I Format brut
A - Définition
B - Format
II Compression CVC
A - Principes
B - Notion de variation
C - Compression
C1 - Méthodes de balayage
C2 - Normalisation du flux
C3 - Matrice des variation
C4 - Atténuation de la perte de données
C5 - Compression de la matrice des variations
C6 - Ecriture dans le fichier
D - Décompression
Annexes :
1 - Compression CVC de base
2 - Compression RLE (24 bits)
3 - Format cvc
I Format brut
A - Définition
Le format brut d'une image est un flux de pixels ordonnés non compressé. Il correspond à une représentation d'une image sous sa forme la plus simple. Peu importe le format d'image source utilisé, le format brut d'une image sera toujours le même.
B - Format
Une image peut être transcrite en informatique comme un tableau à 2 dimensions contenant des pixels ; chaque pixel est caractérisé par une couleur. Suivant la profondeur de couleur choisie (8, 16, 24 ou 32 bits), nous pourront attribuer une plage plus ou moins importante de couleurs à chaque pixel.
8 bits : 256 couleurs
16 bits : 65'536 couleurs
24 bits : 16'777'216 couleurs
32 bits : 4'294'967'296 couleurs
Dans l'étude de la compression CVC, nous allons nous limiter au mode 24 bits RGB(Red Green Blue) même si les autres modes peuvent être implémentés.
Le mode 24 bits permet de stocker chaque pixel sur 3 octets ; chacun de ces octets correspond à une couleur (Rouge, Vert et Bleu RVB ou RGB en Anglais). Chacune de ces composantes contient une valeur comprise entre 0 et 255. Il est alors possible, pour chaque pixel, de connaître la valeur de chacune des composantes de sa couleur.
II Compression CVC
A - Principes
La compression CVC repose sur la notion de variation de couleurs qu'il existe dans un flux de pixels (format brut) RGB. En plus de compresser les variations, CVC utilise aussi la technologie RLE (Run Lenght Encoding) afin d'obtenir des ratios de compression plus importants.
B - Notion de variation
Une variation est la différence numérique qui sépare deux couleurs. Elle peut être positive mais aussi négative. Pour pouvoir calculer la variation, il faut regrouper les composantes (rouge, verte et bleue) afin d'obtenir un nombre codé sur 3 octets ; ce nombre est appelé valeur numérique.
Valeur numérique d'une couleur :
La valeur numérique d'une couleur est notée Vn.
Voici la formule utilisée pour obtenir la valeur numérique d'une couleur(notation c++) :
Vn = (Bleu<<16) | (Vert<<8) | Rouge
Exemple 1:
Valeur numérique de la couleur grise (Rouge : 128 / Vert 128 / Bleu 128)
Vn=(128<<16) | (128<<8) | 128
Vn= 8'421'504
Variation numérique :
La variation numérique qu'il existe entre deux couleurs x et y est notée Va(x Þ y)
Voici la formule utilisée pour calculer la variation de deux couleurs :
Va(x Þ y) = Vn(y) - Vn(x)
Exemple 2:
Variation numérique entre la couleur bleue(Rouge 0 / Vert 0 / Bleu 255) et rouge (Rouge 255 / Vert 0 / Bleu 0).
Soit b = bleu
Soir r = rouge
Vn(b) = (255<<16) | (0<<8) | 0
Vn(b) = 16'711'680
Vn(r) = (0<<16) | (0<<8) | 255
Vn(r) = 255
Représentation binaire :
Bleu Vert Rouge Valeur
Bleu = 11111111 00000000 00000000 = 16'711'680
Rouge = 00000000 00000000 11111111 = 255
Va(b Þ r) = Vn(r) - Vn(b)
Va(b Þ r) = 255 - 16'711'680
Va(b Þ r) = -16'711'425
Une variation est relative et elle peut donc être négative ou positive. Le principe de base de la méthode CVC est de stocker la variation de couleur entre chaque pixel et non pas la couleur du pixel.
C - Compression
Nous allons maintenant étudier les différentes étapes de la compression CVC. Pour des informations complémentaires, reportez-vous aux annexes 1,2 et 3.
C1 - Méthodes de balayage
Avant de créer la matrice des variations (voir C2), il faut choisir une méthode de balayage. Il en existe 2. La méthode de balayage verticale scanne le flux de pixel verticalement tandis que la méthode de balayage horizontale le scanne horizontalement.
Le ratio de compression final pourra être différent en fonction du mode de balayage retenu car il en résultera une matrice des variations totalement différente.
C2 - Normalisation du flux
La toute première opération à effectuer est une normalisation du flux. L'utilité de cette normalisation sera expliquée plus tard dans le paragraphe C4. Pour le moment nous allons juste voir comment cette normalisation est implémentée.
La compression CVC est une compression avec perte de données (même si elle reste négligeable). Cette perte a une valeur décimale égale à 8. (la nature de cette perte sera expliquée au paragraphe C4). La normalisation du flux permet de prendre en compte cette perte de données et d'éviter toute erreur lors de l'étape d'aténuation d'erreurs.
La normalisation vérifie pour chaque composante rouge, verte et bleue de chaque pixel si un dépassement de capacité (débordement si la valeur d'une composante est <0 ou >255) est possible lors de l'étape d'aténuation d'erreurs. Si un dépassement est possible, la couleur du pixel est corrigée.
Voici la formule utilisée :
Soit PERTE = 8 (perte de données maximale)
Soit pixel.Composante une composante de couleur (rouge, verte ou bleue comprise entre 0 et 255) du pixel courant pixel.
SI(pixel.Composante < PERTE)
pixel.Composante = PERTE;
SINON SI(pixel.Composante > (255-PERTE))
pixel.Composante = (255-PERTE);
C3 - Matrice des variations
La matrice des variation est un tableau à une dimension (mais pouvant être représenté comme un tableau à deux dimensions pour se rapprocher de la représentation d'une image) contenant la liste des variations de couleurs du flux de pixel. Ce flux peut être balayé de deux façons différentes (voir C1), selon la méthode retenue, on obtiendra une matrice différente avec une capacité de compression différente.
Pour créer cette matrice, on calcule pour chaque pixel la variation avec le pixel qui le précède dans le flux normalisé. Pour le premier pixel, la couleur de référence est le noir (Vn=0).
C4 - Atténuation de la perte de données
La perte de données maximale de la compression CVC est égale à 8 (valeur décimale) Les 3 bits réservés lors de la compression correspondent à une capacité de stockage égale à 8 ce qui explique cette perte de données.
Comme CVC utilise la variation de couleur comme mode de stockage (les variations sont interdépendantes les unes des autres), la perte de donnée s'additionne au fil de la compression. Il est alors nécessaire de réduire au maximum cette perte de données.
Pour cela, on ajoute à la variation courante le résultat du modulo 8 appliqué sur la variation précédente. Ainsi, la perte de données est atténuée car on récupère la perte de données de la variation courante sur les variations suivantes :
Variation_courante += Variation_precedente % 8
C5 - Compression de la matrice des variations
Maintenant que la matrice des variations est prête, nous pouvons commencer à la compresser. Réportez-vous à aux annexes 1, 2 et 3 pour plus d'informations.
La compression de la matrice reprend les règles ennoncées dans les annexes de ce document. Pour chaque variation, on determine le nombre d'octets necessaires à son enregistrement, on vérifie ensuite si la compression RLE peut être utilisée. Il suffit ensuite d'encoder la variation, de paramètrer convenablement les 3 bits de poids faible du premier octet et d'enregistrer octet par octet le résultat.
C6 - Enregistrement dans le fichier
Une fois la matrice compréssée, il suffit de générer le header du fichier. Ensuite, il faut enregistrer le header dans le fichier puis la matrice compressée. Le fichier cvc est alors enregistré.
D - Décompression
Nous n'étudirons pas les diférentes étapes de la décompression de fichier cvc. Il suffit juste d'implementer le processus inverse de la compression CVC.
Annexe 1 : Compression CVC de base
Une variation peut prendre une valeur comprise entre -16'777'215 et 16'777'215 (Va(Noir Þ Blanc) et Va(Blanc Þ Noir)).
Si l'on considère uniquement la valeur absolue de la variation maximale possible, il nous faudrait au maximum 3 octets pour la stocker. Par contre, le stockage du signe de cette variation reste obligatoire, on réserve donc le bit de poids faible du premier octet pour stocker le signe de la variation.
Chaque variation pourra être stockée sur un nombre d'octets différents en fonction de sa valeur numérique. Voici le tableau explicatif :
Valeur décimale de la variation : Nombre d'octets nécessaires : Ratio (par rapport au format brut)
<=256 1 66
>256 ET <=65536 2 33
> 65536 3 0
Exemple :
Flux brut (format RGB):
255 ;0 ;0 0 ;0 ;255
0 ;255 ;0 0 ;255 ;0
Calcul des valeur numériques :
255 16'711'680
65'280 65'280
:
255 16'711'425 -16'646'400 0
Matrice des variations en balayage horizontal :
Annexe 2 : Compression RLE
La compression CVC utilise RLE afin d'atteindre des ratios encore plus élevés. Il arrive parfois que plusieurs variations voisines (dans la matrice des variations) aient la même valeur numérique (il s'agit souvent d'une variation égale à 0 et donc de plusieurs pixels continus de même couleur). Sans RLE, il faudrait coder chacune de ces variations ce qui représente une perte de place non négligeable. RLE permet de coder jusqu'à 224 variations continues identiques en seulement 4 octets. Lorsque plusieurs variations qui se suivent sont identiques, l'utilisation de RLE devient possible.
RLE demande 4 octets pour être utilisé (1 octet réservé et 3 octets pour enregistrer le nombre de variations, on parle alors de RLE 24 bits), il faut donc l'utiliser uniquement si une compression est possible. C'est pour cela que l'on a défini des seuils à partir desquels la compression RLE devient avantageuse :
Seuils pour une variation codée sur:
- 1 octet = 5
- 2 octets = 2
- 3 octets = 3
Annexe 3 : Format cvc
Dans cette partie nous allons définir la structure du fichier. Celui-ci portera par défaut l'extension cvc (*.cvc).
Le header est l'en tête du fichier, il contient des informations relative au fichier CVC (version, méthode de compression utilisée etc.)
Header :
IDFichier : 1 octet (tag permettant d'identifier un fichier cvc)
Version : 1 octet (version de CVC utilisée lors de la compression)
Reservé1 : 1 octet (réservé pour une utilisation ultérieure)
Reservé2 : 1 octet (idem)
Image_Info : Hauteur : 4 octets
Largeur : 4 octets
Taille totale du header : 12 octets.
La partie Image_Info contient les informations relatives à l'image compressée (dimensions). Résolution maximale : 4'294'967'296 x 4'294'967'296 (soit une image de plusieurs millions de teraoctets en format brut)
Après le header, on trouve la matrice compressée.
Chaque variation compressée est enregistrée à l'envers dans le fichier (octet de poid faible en premier) car le premier octet doit contenir les 3 bits réservés qui sont indispensables pour l'étape de décompression.
Dans ce tableau, on ne s'occupe que des 3 bits de poids faible, les autres bits sont grisés.
Bit réservé Utilisation
00111000 Signe de la variation (0 si positive, 1 si négative)
00111000 Les deux bits suivants peuvent prendre plusieurs valeurs : 00 : Flag RLE, indique que les 3 prochains octets contiennent le nombre de variations identiques. Dans ce cas, tous les autres bits de cet octet valent 0. 01 : Variation <= à 256 qui sera donc codée sur un octet. 10 : Variation > à 256 et <= 65536 qui sera donc codée sur deux octets. (dont un octet situé après celui-ci) 11 : Ce pixel possède une variation > 65536 qui sera donc codée sur trois octets. (dont deux octets situés après celui-ci)
Exemple 1 :
Nous avons une variation x qui vaut 211 (11010011 en binaire)
Celle-ci nécessite un seul octet pour être enregistrée
Voici donc comment sera codée la variation : 11010010
Il y a ici une perte de donnée (valeur : 3).
Exemple 2 :
Nous avons une variation y qui vaut -15000 (00111010 10011000 en binaire, on ne stocke pas le signe)
Celle-ci nécessite deux octets pour être enregistrée
Voici donc comment sera codée la variation : 10011101 00111010
Le bit de poid faible du premier octet prend la valeur 1 lorsque la variation est négative.