Je suis actuellement sur un projet premettant de faire de la compression et décompression d'image via les arbres naires.
tout marche bien sauf une fonctionnalité : celle de reconstituer une image originale à partir d'un arbre.
voici sur la figure suivante un exemple d'arbre généré (à gauche) à partir de l'image test (à droite) :
Image_Arbre_et_Image.png
Ce projet est réalisé en ADA mais mon problème est plutôt d'ordre algorithmique.
Je vous rappelle brièvement la méthode de compression : on représente une image sous forme d'arbre quaternaire où il y a 4 fils et un père. En repérant les zones homogènes dans une image (où les valeurs sont les mêmes), on symbolise cette zone par un seul nombre, celui
qui correspond à la valeur des pixels de cette zone.
Dans mon programme, les 4 fils sont rangés dans l'ordre suivant pour les zones de l'image: Nord-Ouest, Nord-Est, Sud-Ouest et Sud-Est.
Comme vous pouvez le voir sur l'arbre de la figure ci-dessus, la valeur d'un père égale à -1 signifie que la zone n'est pas homogène et qu'il faut donc la décomposer en 4 sous-zones qui correspond aux 4 fils rangés dans l'ordre ci-dessus. Si elle est différente de -1, nous reconstitutons la zone de l'image.
Mon problème se situe au niveau de la reconstitution de l'image test à partir de l'arbre. La procédure utilisée est la suivante :
Cette procédure est appelée de cette manière :
avec n la dimension de l'image à reconstituer.
On voit bien que si la valeur en cours est égale à -1, alors, on appelle récursivement les autres fils, c'est-à-dire que l'on descend dans l'arborescence.
Mais malheureusement, l'image obtenue n'est pas tout à fait bien reconstituée; voici ce que j'obtiens:
image_obtenue.png
Le premier quart supérieur gauche comme les 3 autres ne sont pas bons. Pourtant, j'ai l'impression que les 4 indices i_d, i_f , j_d et j_f (avec l'indice d comme indice de début de la zone et f comme indice final de la zone") correspondent bien à ce qu'il faut faire dans la récursivité.
Quelqu'un pourrait-il voir où est l'erreur ?
tout marche bien sauf une fonctionnalité : celle de reconstituer une image originale à partir d'un arbre.
voici sur la figure suivante un exemple d'arbre généré (à gauche) à partir de l'image test (à droite) :
Image_Arbre_et_Image.png
Ce projet est réalisé en ADA mais mon problème est plutôt d'ordre algorithmique.
Je vous rappelle brièvement la méthode de compression : on représente une image sous forme d'arbre quaternaire où il y a 4 fils et un père. En repérant les zones homogènes dans une image (où les valeurs sont les mêmes), on symbolise cette zone par un seul nombre, celui
qui correspond à la valeur des pixels de cette zone.
Dans mon programme, les 4 fils sont rangés dans l'ordre suivant pour les zones de l'image: Nord-Ouest, Nord-Est, Sud-Ouest et Sud-Est.
Comme vous pouvez le voir sur l'arbre de la figure ci-dessus, la valeur d'un père égale à -1 signifie que la zone n'est pas homogène et qu'il faut donc la décomposer en 4 sous-zones qui correspond aux 4 fils rangés dans l'ordre ci-dessus. Si elle est différente de -1, nous reconstitutons la zone de l'image.
Mon problème se situe au niveau de la reconstitution de l'image test à partir de l'arbre. La procédure utilisée est la suivante :
Code:
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
-------------------------------------------------------------------
---- procedure arb_to_im: permet de reconstituer l'image originale
---- à partir de l'image compressée.
---- paramètres: a l'arbre reconstitué, im l'image à construire,
---- i_d,i_f,j_d,j_f les indices de début et de fin, n la dimension
---- de l'image originale
-------------------------------------------------------------------
procedure arb_to_im ( a: in arb_im ; im: out image ; i_d,i_f,j_d,j_f: in integer ) is
begin
-- cas terminal : arbre vide
if Aq_Vide(a) then
null; -- ne rien faire
-- cas général
-- Si la valeur est différente de -1
else if Aq_Valeur(a) /= -1 then
for i in i_d..i_f loop
for j in j_d..j_f loop
-- on ecrit dans le tableau im (représentant l'image) la valeur de la zone ou d'un seul pixel
im(i,j):=pixel(Aq_Valeur(a));
end loop;
end loop;
else -- appels recursifs pour parcourir l'arbre en entier
arb_to_im(Aq_Nord_Ouest(a),im,i_d,i_f/2,j_d,j_f/2);
arb_to_im(Aq_Nord_Est(a),im,i_d,i_f/2,j_f/2+1,j_f);
arb_to_im(Aq_Sud_Ouest(a),im,i_f/2+1,i_f,j_d,j_f/2);
arb_to_im(Aq_Sud_Est(a),im,i_f/2+1,i_f,j_f/2+1,j_f);
end if;
end if;
end arb_to_im;
Code:
arb_to_im(arb,im1,1,n,1,n);On voit bien que si la valeur en cours est égale à -1, alors, on appelle récursivement les autres fils, c'est-à-dire que l'on descend dans l'arborescence.
Mais malheureusement, l'image obtenue n'est pas tout à fait bien reconstituée; voici ce que j'obtiens:
image_obtenue.png
Le premier quart supérieur gauche comme les 3 autres ne sont pas bons. Pourtant, j'ai l'impression que les 4 indices i_d, i_f , j_d et j_f (avec l'indice d comme indice de début de la zone et f comme indice final de la zone") correspondent bien à ce qu'il faut faire dans la récursivité.
Quelqu'un pourrait-il voir où est l'erreur ?
Aucun commentaire:
Enregistrer un commentaire