Pourquoi ma compression RLE ne marche-t-elle pas ?

Bonjouuur !

J’essaie d’écrire un programme me permettant de compresser une image à l’aide de la RLE. Le projet en lui-même est en C++, et j’utilise l’API CImg, mais je souhaite dans ce topic faire abstraction du code et vous donner ma façon de faire, afin que vous le validiez ou non.

Mon programme : brève description

Il y a deux phases : une phase d’écriture d’un fichier-image (a) et une phase de lecture de ce même fichier-image (b). Mon programme prend un fichier-image en entrée noté A, et fournit en sortie un fichier-image compressé avec RLE noté B (a). Il permet par la suite de visualiser B (b).

La lecture des pixels se fait dans le sens de la lecture : de gauche à droite, puis de haut en bas.

Le fichier-image A est un peu particulier…

Chacun de ses pixels est codé sur un octet, de la manière suivante :

1. Ses deux premiers bits sont à 0

2. Les deux bits suivants sont les deux bits de poids fort de la valeur de rouge de ce pixel

3. Les deux bits suivants sont les deux bits de poids fort de la valeur de vert de ce pixel

4. Les deux bits suivants sont les deux bits de poids fort de la valeur de bleu de ce pixel

EXEMPLE.

Si la valeur de rouge du pixel est 128, la valeur de vert 0 et la valeur de bleu 255, l’octet du pixel sera codé : 00 10 00 11. On a bien deux bits à 0. Puis les deux bits de poids du rouge. Puis les deux bits de poids fort du vert. Enfin, les deux bits de poids fort du bleu.

Indication préalable sur ma compression RLE

Une répétition d’au moins 3 pixels de la même couleur sera codée de cette façon :

1. Un premier octet contiendra d’abord le bit n°1 mis à 1 pour indiquer qu’il y a répétition, suivi de 7 bits indiquant le nombre de répétitions

2. Un second octet, suivant directement celui de la puce n°1 de cette liste, contient la couleur du pixel (couleur codée dans la section Le fichier-image A est un peu particulier…).

Phase "(a)" : compression RLE de A et enregistrement dans un fichier

L’idée est de compter (incrémenter) le nombre de répétitions du pixel situé aux coordonnées $(x;y)$ par comparaison avec le pixel de coordonnées $(x+1;y)$ (ou bien $(0;y+1)$ si le pixel $(x;y)$ se situe en fin de ligne).

Dès que je rencontre un pixel $(x+1;y)$ (ou $(0;y+1)$) de couleur différente avec $(x;y)$ :

1. Si le nombre de répétitions est $>=3$, j’ajoute dans une liste l’octet indiquant les répétitions et l’octet indiquant la couleur (cf. la partie Indication préalable sur ma compression RLE). Le premier est ainsi égal au résultat de l’opération binaire "$128\text{ | nombre_repetitions}$" ("$128_text{ |}$" car le premier bit doit être mis à 1, cf. la partie Indication préalable sur ma compression RLE). Le second octet est simplement égal à la couleur du/des pixels (qui ont la même couleur, évidemment). Ensuite, je ré-initialise le nombre de répétitions.

2. Sinon, pour le pixel ou bien les deux pixels de couleur identique, j’ajoute dans cette liste l’octet indiquant les répétitions mais en le rendant égal à $0$, ainsi que l’octet indiquant la couleur. Ensuite, je ré-initialise le nombre de répétitions.

Une fois que toute l’image a été parcourue, j’enregistre chacun des octets de ma liste dans un fichier. Ainsi, j’obtiens B.

Bon je ne souhaitais pas vous embêter avec mon code mais finalement, peut-être que ce serait plus pratique pour vous de jeter un coup d’oeil ?

1. other_images(1) désigne A.

2. calc_2bits_char(other_images(1), x, y) désigne l’octet de couleur défini dans la partie Le fichier-image A est un peu particulier….

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

int x = 0, y = 0;
int repeated_pixels = 1;
std::vector<unsigned char> w_c = std::vector<unsigned char>();
cimg_forXY(other_images(1), x, y)
{
    if(x+1 <= (other_images(1)._width - 1) && y+1 <= (other_images(1)._height - 1)&&(other_images(1)(x, y) == other_images(1)(x+1, y)||other_images(1)(x, y) == other_images(1)(0, y+1)))
    {
        repeated_pixels++;
    }

    else
    {
        if(repeated_pixels < 3)
        {
            for(int i = 0; i < repeated_pixels; i++)
            {
                w_c.push_back(0);
                w_c.push_back(calc_2bits_char(other_images(1), x, y));
            }
        }

        else
        {
            w_c.push_back(128 || (repeated_pixels-3));
            w_c.push_back(calc_2bits_char(other_images(1), x, y));
        }

        repeated_pixels = 1;
    }
}

write_data(other_images(1)._width, other_images(1)._height, w_c);

Phase "(b)" : lecture de B, fichier-image au format RLE

Ici, je lis octet par octet B. Je remarque que selon que la position de l’octet est paire ou impaire, il correspond soit à l’octet indiquant les répétitions, soit à l’octet indiquant la couleur : je souhaite donc faire usage de cette propriété arithmétique pour la suite.

En fait, je vais me concentrer uniquement sur les octets de répétitions (i.e. : sur les octets de position paire, puisque la séquence d’octets est : "octet_repetitions = position 0, octet_couleur = position 1, octet_repetitions = position 2, octet_couleur = position 3, etc.").

Donc, si la position de l’octet est paire :

1. Si l’octet de répétitions est $>0$, je met à jour le nombre de répétitions avec la valeur de cet octet. Pour ce faire, je n’oublie pas de faire un déplacement binaire à gauche (valeur du déplacement : 1), tout de suite suivi d’un déplacement binaire à droite (valeur du déplacement : 1), afin de me débarasser du premier bit de cet octet (qui était mis à 1 pour indiquer la présence de répétitions).

2. Si l’octet de répétitions vaut $0$, alors je ne fais rien.

Puis, je récupère la couleur, située dans l’octet qui suit cet octet de répétitions.

Enfin, pour chaque valeur du compte du nombre de répétitions, je colorie les pixels de mon image. A chaque répétition, j’incrémente les coordonnées du pixel dessiné pour obtenir celles du pixels que je vais dessiner.

Voici le code. other_images(im_slot) est l’image qui doit, si mon programme marchait correctement (et ce n’est pas le cas ), refléter le contenu de B. calc_RGB_from_2bits_char(read_chars.at(i+1)); stocke le rouge, le vert et le bleu à partir de l’octet fourni en paramètre, ce dernier étant au format défini dans la partie Le fichier-image A est un peu particulier….

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

int width = 0, height = 0;
std::vector<unsigned char> read_chars = std::vector<unsigned char>();
read_data(width, height, read_chars);
other_images(im_slot) = cimg_library::CImg<unsigned char>(width, height, 1, 3);
int x = 0, y = 0;
int number_of_repetitions = 1;
std::vector<unsigned char> RGB_2bits = std::vector<unsigned char>();
for(int i = 0; i < read_chars.size(); i++)
{
    if(i%2 == 0)
    {
        if(read_chars.at(i) > 0)
        {
            number_of_repetitions = 3 + ((read_chars.at(i) << 1) >> 1);
        }

        RGB_2bits = calc_RGB_from_2bits_char(read_chars.at(i+1));
        for(int j = 0; j < number_of_repetitions; j++)
        {
            other_images(im_slot)(x, y, 0, 0) = RGB_2bits.at(0);
            other_images(im_slot)(x, y, 0, 1) = RGB_2bits.at(1);
            other_images(im_slot)(x, y, 0, 2) = RGB_2bits.at(2);
            x++;
            if(x == width)
            {
                y++;
                x = 0;
            }
        }

        number_of_repetitions = 1;
    }
}

Résultat de mon programme

Je pense que la phase (a) fonctionne bien, dites-moi si ce n’est pas le cas.

Par contre mon programme ne fonctionne pas bien : j’obtiens une quarantaine de lignes de pixels colorés dans mon image censée refléter B. Aucune forme bien définie n’est dinstinguable, mais les couleurs sont bonnes (genre y a pas du violet fluo ou quoi). Les pixels en-dessous de cette quarantaine de lignes sont tous noirs.

Je pense donc que la phase (b) n’est pas bien réalisée. Du coup si quelqu’un pouvait me dire en quoi je me trompe dans mon raisonnement, ma façon de faire… merci d’avance !

Illustration du problème

A gauche : le fichier-image A chargé en RAM et affiché. A droite : le fichier-image B chargé en RAM et affiché. Les deux devraient être identiques, ce n’est pas du tout le cas.

Salut The-Aloha-Protocol,

Comme souvent j’ai l’impression que tu t’attaques à un problème sans bien maîtriser certaines notions.

On a assez peut de précision sur l’espace de couleur de ton image d’entrée / la profondeur de couleur, mais pour moi cette phrase est au mieux inexacte, voire fause:

Les deux bits suivants sont les deux bits de poids fort de sa valeur de rouge

Si une couleur (ou n’importe quelle info en fait) est codée sur 2 bits le premier (gauche) est le bit de poids fort et le second (dernier) le bit de poids faible. (Enfin ça dépend de ta méthode de codage de tes infos, mais bon). C’est la définition même, avec une donnée codée sur 2 bits, ces 2 bits ne peuvent pas être deux bits de poids fort. Les mots en anglais ne laissent pas le doute la dessus : most significant bit, least significant bit. Peut être que tu veux dire que ces deux bits correspondent au MSB et au bit suivant d’une valeur originalement codée sur 8 bits ???

(x+1;y)(x+1;y) (ou bien (0;y+1)(0;y+1) si le pixel (x;y)(x;y) se situe en fin de ligne)

Mauvaise idée. Est ce que ton traitement utilise la notion de proximité géographique entre deux pixel ? Ou utilise-t-il seulement la notion de pixels consécutifs ? Tu pourrait très largement simplifier ton algo de ce côté la. Gros indice au dernier paragraphe: http://cermics.enpc.fr/cours/java/notes/notes8.html

Je pense que la phase (a) fonctionne bien, dites-moi si ce n’est pas le cas.

Comment veut tu déboguer ça alors que tu ne sait pas d’où vient le problème ? Pourquoi tu ne commence pas par vérifier que ton image produite en (a) est correcte ? Tu as deux moyens à ta disposition:

• Faire un test manuel avec une image de 10x10, ça devrait te permettre de voir si ton résultat est correct
• Ecrire une batterie de test pour être sur que ton programme fonctionne sur différents cas (matrice remplies de 0? Matrice sans répétition ? etc.)

Je pense qu’en y passant quelques heures tu peux commencer par t’assurer que le résultat de (a) est correct.

Hello Anto,

On a assez peut de précision sur l’espace de couleur de ton image d’entrée / la profondeur de couleur, mais pour moi cette phrase est au mieux inexacte, voire fause:

Je travaille avec des images RGB en deux dimensions.

Si une couleur (ou n’importe quelle info en fait) est codée sur 2 bits le premier (gauche) est le bit de poids fort et le second (dernier) le bit de poids faible. (Enfin ça dépend de ta méthode de codage de tes infos, mais bon). C’est la définition même, avec une donnée codée sur 2 bits, ces 2 bits ne peuvent pas être deux bits de poids fort. Les mots en anglais ne laissent pas le doute la dessus : most significant bit, least significant bit. Peut être que tu veux dire que ces deux bits correspondent au MSB et au bit suivant d’une valeur originalement codée sur 8 bits ???

Oui c’était bien ça, je viens d’éditer l’OP ! Désolé de ne pas avoir été clair. L’idée est donc de récupérer la valeur de rouge, d’en prendre les deux premiers bits, et de mettre ces derniers en guise de bits juste après les 00 (mon exemple est plus parlant ).

Mauvaise idée. Est ce que ton traitement utilise la notion de proximité géographique entre deux pixel ? Ou utilise-t-il seulement la notion de pixels consécutifs ? Tu pourrait très largement simplifier ton algo de ce côté la. Gros indice au dernier paragraphe: http://cermics.enpc.fr/cours/java/notes/notes8.html

Non bein juste les pixels consécutifs oui. Pourquoi est-ce que c’est une si mauvaise idée que ça ?

Comment veut tu déboguer ça alors que tu ne sait pas d’où vient le problème ? Pourquoi tu ne commence pas par vérifier que ton image produite en (a) est correcte ? Tu as deux moyens à ta disposition:

Ouaip je vais faire des tests, j’allais en faire hier mais je n’en ai pas eu le temps

Pourquoi est-ce que c’est une si mauvaise idée que ça ?

Tout simplement par ce que ça t’obliges à faire un traitement bien complexe pour pas grand chose ? En gros dans ton code tu veux travailler sur des pixels consécutifs. Si j’ai bien suivi ton code tu t’amuses à détecter quand est ce que tu arrives en fin de ligne pour continuer ton traitement à la ligne suivante. Ce qui t’obliges à faire de choses du genre if (x+1) < img.width ... else .... Alors que pour traitement tu ne t’interesse pas du tout à la notion de géographie de l’image ou à la notion de ligne. Je connais assez mal le C++ et pas du tout l’API que tu utilise, mais je pense que le secret suivant (en python) est une approche plus simple pour ton cas

1
2
3
4

image [[0, 1, 2], [1, 2, 3], [9, 8, 7]] # Image carrée de 3 pixels
pixels = [x for row in image for x in row]

# Problem solved ? Begin RLE here

Le code que tu présente me parait assez obscur. Perso je ne voudrait pas maintenir quelque chose comme ça :

1

    if(x+1 <= (other_images(1)._width - 1) && y+1 <= (other_images(1)._height - 1)&&(other_images(1)(x, y) == other_images(1)(x+1, y)||other_images(1)(x, y) == other_images(1)(0, y+1)))

Oui effectivement ça augmenterait la lisibilité ! Si tu fais abstraction de ma façon de parcourir l’image (ce à quoi sert e.g. la ligne de code que tu viens de citer), est-ce que globalement mon raisonnement d’écrire et de lecture te paraît correct ?

est-ce que globalement mon raisonnement d’écrire et de lecture te paraît correct ?

Honnêtement je trouve le code très (trop ?) difficilement lisible pour répondre à cette question

Concentres toi sur la partie (a) du problème, simplifies ton algorithme, nommes mieux tes variables, indentes mieux ton code, tests tes résultats et je pense que ça sera plus facile pour répondre aux interrogations restantes.

Bein à part les lignes au-dessus des for (qui sont juste des déclarations de variables), y a pas grand-chose comme ligne que je pourrais retirer… En tout cas oui, je vais voir pour l’indentation (j’ai utilisé un reindenter)

Edit : après si j’ai passé beaucoup de temps à décrire mon algorithme en français, c’est quand même pour vous guider

Est-ce que tu as commencé par tester les résultats de l’étape (a) ?

Si tu es sur que l’erreur est dans (a) ou (b) ça devrait probablement t’aider, non ?

Diviser pour mieux régner.

Donc, comme le dit @Anto59290, on commence par avec (a) qui fonctionne, puis on attaque l’implémentation de (b).

En C++, les tableaux à plusieurs dimensions, c’est vraiment pas terrible, on préfère largement "linéariser" ce type de tableau : avec un tableau 1D avec une API qui fait la translation (x,y) => (x*row_size + y). Cela rendrait le code largement plus lisible que ce "if" des Enfers.

En plus, ce "other_images(1)" qui se ballade dans votre pseudo-code, donnez lui un "vrai" nom, significatif. Le if des Enfers, il aurait déjà largement mérité l’implémentation d’une fonction dédiés.

Pensez à vérifier (a) avec des cas au limites, comme un damier de case 1 pixel, pour voir la cas d’une image qui ne se compresse pas du tout.

Et dans le cas du damier, votre assertion de base de (b) sur les octets paires et impaires est complètement fausse.