Décompression d'une image codée avec un quadtree

**souki22** · 09/02/2015, 23h32

Bonsoir à tous,

Je dispose d'une librairie graphique permettant la définition et la manipulation d'images. Je dispose aussi du code d'une classe définissant les quadtree.

Avec ces éléments, j'ai pu écrire une fonction constructQuadTree qui prend comme argument une image en noir et blanc (pas de niveaux de gris pour le moment) et qui retourne la racine d'un arbre quadtree qui traduit cette image (selon les règles connues de compression d'image à l'aide de quadtrees). Le code est en bas.

Maintenant, j'essaie d'écrire la fonction qui fait l'opération inverse, à savoir prendre en entrée la racine d'un quadtree tel que la valeur de chacun de ses noeuds est soit "noir" (ie 0) soit "blanc" (ie 255) et retourner l'image correspondante. J'ai appelé cette fonction imageBW et j'ai noté I la variable retournée dans le corps de cette fonction. Cette fonction telle que je l'ai écrite n'a pas le comportement souhaité

. C'est l'objet de mon post.

Après avoir consulté des articles en ligne, je me suis résolu à écrire cette fonction de manière récursive et je lui ai rajouté 4 autres arguments : int x, int y, int W, int H. (x,y) désigne les coordonnées d'un pixel et (W,H) les dimensions de l'image, I, qui va être retournée.

J'ai essayé de faire une lecture en profondeur de l'arbre. Je commence par tester si la racine passée en argument est une feuille ou pas. Si c'en est une, c'est facile, je retourne une image toute blanche ou toute noire. Sinon, je considère les quatre fils de la racine. Pour chaque fils f, je fais une des deux choses suivantes :

- soit je remplis le sous bloc qui lui correspond par une même couleur (blanc ou noir) si f est une feuille

- soit j'appelle la fonction imageBW avec les arguments (f, xf, yf, W/2, H/2) si f n'est pas une feuille. (xf,yf) dénote ici les coordonnées du point extrême à gauche et en haut du bloc correspondant au fils f.

Comportement de imageBW telle qu'elle est écrite dans le code ci-dessous
Pour tester mes fonctions, je prends une image que je compresse puis que je décompresse à l'aide de ces fonctions. "constructQuadTree" a l'air de bien marcher.
Quand je prends une image I0 en noir et blanc et que je la compresse, puis la décompresse, il s'avère que j'ai toujours en retour de "imageBW" une image dont le bloc nord-ouest est blanc, même si un tel bloc n'apparaît pas dans l'input I0. En plus, le reste de l'image semble être gris.

Je sais qu'il est difficile de comprendre à partir de cette simple description l'erreur que j'ai commise, moi même je ne comprends pas

. Mais peut être quelqu'un qui s'y connait trouvera une erreur dans mon code

.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
/*--------------------------------- Some helpful functions -----------------------------------------*/
void fillIn(Image<byte>& I, const Image<byte>& toBeCopied, int x0, int y0)
{
    int w=toBeCopied.width(); int h=toBeCopied.height();
 
    assert(x0<I.width() && y0< I.height());
    assert(w<I.width() && h< I.height());
 
    for(int x=x0; x<w; x++)
        for(int y=y0; y<h; y++)
            I(x,y)=toBeCopied(x,y);
}
 
 
Image<byte> whiteImage(int width, int height)
{
    Image<byte> I(width,height);
    for(int i=0; i<height; i++)
        for(int j=0; j<width; j++)
            I(j,i)=255;
    return I;
}
 
 
 
Image<byte> blackImage(int width, int height)
{
    Image<byte> I(width,height);
    for(int i=0; i<height; i++)
        for(int j=0; j<width; j++)
            I(j,i)=0;
    return I;
}
 
 
bool isAllWhite(Image<byte> I)
{
    int H=I.height(); int W=I.width(); assert(H==W);
    if (H==1)
        return I(0,0)==255;
    Image<byte> I_NW=I.getSubImage(0,0,W/2,H/2);
    Image<byte> I_NE=I.getSubImage(0,W/2,W/2,H/2);
    Image<byte> I_SE=I.getSubImage(H/2,W/2,W/2,H/2);
    Image<byte> I_SW=I.getSubImage(H/2,0,W/2,H/2);
    return isAllWhite(I_NW) && isAllWhite(I_NE) && isAllWhite(I_SW) && isAllWhite(I_SE);
 
}
 
 
bool isAllBlack(Image<byte> I)
{
    int H=I.height(); int W=I.width(); assert(H==W);
    if (H==1) 
        return I(0,0)==0;
    Image<byte> I_NW=I.getSubImage(0,0,W/2,H/2);
    Image<byte> I_NE=I.getSubImage(0,W/2,W/2,H/2);
    Image<byte> I_SE=I.getSubImage(H/2,W/2,W/2,H/2);
    Image<byte> I_SW=I.getSubImage(H/2,0,W/2,H/2);
    return isAllBlack(I_NW) && isAllBlack(I_NE) && isAllBlack(I_SW) && isAllBlack(I_SE);
 
}
 
 
 
 
 /*--------------------- Functions doing the compression and decompression -------------------------------*/
 
QTree<byte>* constructQuadTree(Image<byte> I)
{
 
 
    if(isAllWhite(I)) return new QLeaf<byte>(255);
    if(isAllBlack(I)) return new QLeaf<byte>(0);
 
    int H=I.height(); 
    int W=I.width(); 
    assert(H==W);
 
    QTree<byte>* root=new QNode<byte>(0,0,0,0); // sons of root are at this stage pointers stocking the adress NULL
 
    Image<byte> I_NW = I.getSubImage(0,0,W/2,H/2);
    Image<byte> I_NE = I.getSubImage(W/2,0,W/2,H/2);
    Image<byte> I_SE = I.getSubImage(W/2,H/2,W/2,H/2);
    Image<byte> I_SW = I.getSubImage(0,H/2,W/2,H/2);
 
    // construct first son NW
    if (isAllWhite(I_NW)) 
        root->son(NW)=new QLeaf<byte>(255); 
    else if (isAllBlack(I_NW)) 
        root->son(NW)=new QLeaf<byte>(0); 
    else
        root->son(NW)=constructQuadTree(I_NW);
 
    // construct second son NE
    if (isAllWhite(I_NE)) 
        root->son(NE)=new QLeaf<byte>(255); 
    else if (isAllBlack(I_NE)) 
        root->son(NE)=new QLeaf<byte>(0); 
    else
        root->son(NE)=constructQuadTree(I_NE);        
 
    // construct third son SE
    if (isAllWhite(I_SE)) 
        root->son(SE)=new QLeaf<byte>(255); 
    else if (isAllBlack(I_SE)) 
        root->son(SE)=new QLeaf<byte>(0); 
    else
        root->son(SE)=constructQuadTree(I_SE);
 
    // construct fourth son SW
    if (isAllWhite(I_SW)) 
        root->son(SW)=new QLeaf<byte>(255); 
    else if (isAllBlack(I_SW)) 
        root->son(SW)=new QLeaf<byte>(0); 
    else
        root->son(SW)=constructQuadTree(I_SW); 
 
    return root; 
}
 
 
 
Image<byte> imageBW(QTree<byte>* qt, int x, int y, int W, int H)
{
    /* ------------------------------ If the tree is just one node ------------------------- */
    if(qt->isLeaf())
    {
        if (qt->value()==0)
            return blackImage(W,H);
        if (qt->value()==255)
            return whiteImage(W,H);
    }
 
 
    /* -------------------------------- If the tree have sons ------------------------------- */
    Image<byte> I(W,H);
 
    QTree<byte>* nw=qt->son(NW);
    QTree<byte>* ne=qt->son(NE);
    QTree<byte>* sw=qt->son(SW);
    QTree<byte>* se=qt->son(SE);
 
    // Treatement of NW son
    if(nw->isLeaf())
    {
        if (nw->value()==0) fillIn(I, blackImage(W/2,H/2), 0, 0);
        if (nw->value()==255) fillIn(I, whiteImage(W/2,H/2), 0, 0);
    }
    else
    {
        Image<byte> I_nw = imageBW(nw,0,0,W/2,H/2);
        fillIn(I,I_nw,0,0);
    }
 
    // Treatement of NE son
    if(ne->isLeaf())
    {
        if (ne->value()==0) fillIn(I, blackImage(W/2,H/2), W/2, 0);
        if (ne->value()==255) fillIn(I, whiteImage(W/2,H/2), W/2, 0);
    }
    else
    {
        Image<byte> I_ne = imageBW(ne,W/2,0,W/2,H/2);
        fillIn(I,I_ne,W/2,0);
    }
 
    // Treatement of SW son
    if(sw->isLeaf())
    {
        if (sw->value()==0) fillIn(I, blackImage(W/2,H/2), 0, H/2);
        if (sw->value()==255) fillIn(I, whiteImage(W/2,H/2), 0, H/2);
    }
    else
    {
        Image<byte> I_sw = imageBW(sw,0,H/2,W/2,H/2);
        fillIn(I,I_sw,0,H/2);
    }
 
    // Treatement of SE son
    if(se->isLeaf())
    {
        if (se->value()==0) fillIn(I, blackImage(W/2,H/2), W/2, H/2);
        if (se->value()==255) fillIn(I, whiteImage(W/2,H/2), W/2, H/2);
    }
    else
    {
        Image<byte> I_se = imageBW(se,W/2,H/2,W/2,H/2);
        fillIn(I,I_se,W/2,H/2);
    }
 
    return I;
}

**bacelar** · 10/02/2015, 20h26

Qu'est qui dit le débuggeur ?

**souki22** · 11/02/2015, 11h38

Oui en effet, j'ai utilisé le débuggeur.

Je constate que mon code me retourne toujours une image dont le bloc nord ouest est blanc et dont le reste des blocs est gris, et ce pour les deux images avec lesquelles je le teste. La couleur gris m'étonne particulièrement vu que je n'utilise que des 0 et des 255.

Quand j'utilise le debuggeur, l'algorithme passe effectivement par les étapes qu'il faut (cad que j'avais en tête en l'écrivant). En revanche, je n'ai pas encore prêté attention aux valeurs que prennent les pixels de l'image qui va être retournée (faute de temps).

Je pense que je dois me confier à notre ami debuggeur.

Décompression d'une image codée avec un quadtree

C++

Discussions similaires

Partager

Partager