Quadtree, traitement image

Version imprimable

Bonsoir a tous,
Voila j'ai un peu petit problème :cry: avec les quadtree pour traiter des images. J'ai cherché pas mal par moi même et ensuite sur internet mais je ne comprends toujours pas comment coder cette fonction...

Tout d'abord nous avons une structure image comprenant ces différentes fonctions:
Code:

1 2 3 4 5 Image*createImage (int w, int h);/* creer une image de taille w*h */ int getWidth(Image*image); /* donne la largeur de l'image */ int getHeight (Image *image); /*donne la hauteur de l'image */ int getValue (Image *image, int x, int y); /* donne la valeur du pixel (x,y) */ void setValue (Image *image, int x, int y, int val); /* attribue la valeur val au pixel (x,y) */
La structure du Quadtree:
Code:

1 2 3 4 5 typedef struct Quadtree { struct Quadtree *FilsNE, *FilsNO, *FilsSE, *FilsSO; int valeur /* Pour stocker la valeur moyenne de la couleur */ }Quadtree;
La fonction que j'essaye de coder est :

Code:

Image* QuadtreeToImage(Quadtree* qt); /* qui prend en argument un quadtree, et retourne l'image associée */

Voila donc je ne sais pas comment faire pour la coder...

Je me doute qu'il faut l'aborder recursivement, commencer par la racine, recuperer les valeurs des couleurs a l'aide de la fonction prevu a cet effet mais je ne vois pas comment lui fournir les bonnes coordonnées... et faire les appels recursivement...

Je vous remercie deja de m'avoir lu, et si vous pouviez me donner des pistes de reflexions ce serait formidable!!!

Merci,

Bonne soirée a vous

NB: Les images auront une taille carrée, de coté egal a une puissance de deux.

27/04/2007, 00h50
Bob.Killer

tu partages récursivement ton image en 4 sous images de même taille et tu iteres
27/04/2007, 00h56
souviron34

Citation:

Envoyé par line86

Quadtree* imageToQuadtree(Image* image); /* qui prend en argument un quadtree, et retourne l'image associée */
....

d'après ce que tu définis, ce serait plutôt :

qui prend en argument une image et retourne un quadtree ..

C'est bien ça ce que tu veux faire ?
27/04/2007, 09h18
line86

Petite correction

Merci pour vos reponses,
et merci souviron34 pour ta remarque...
Je me suis effectivement trompé dans ma fonction :oops: :oops:
La fonction que j'essaye de faire est

Code:

Image*QuadtreeToImage (Quadtree* qt) /* qui prend en argument un quadtree, et retourne l'image associée */

Merci

bonjour a tous,
voila j'ai continué a chercher et je suis arrivé a ce petit bout de code mais je ne comprends toujours pas comment faire pour recuperer les coordonnées de x et y pour creer l'image

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Image* QuadtreeToImage (Quadtree* qt)
{
 int h = getHeight(image); /* permet de recuperer la hauteur de l'image */
 Image* a = createImage(h,h); /* c'est une image carrée */
 if (qt != NULL)
   {
     setValue (a,?,?,qt->valeur); /* c'est ici que je ne comprends pas comment faire pour recupere la valeur de x et y sachant qu'ils n'ont pas la meme valeur a chaque appel de fonctions...*/
     QuadtreeToImage (qt->FilsNE);
     QuadtreeToImage (qt->FilsNO);
     QuadtreeToImage (qt->FilsSE);
     QuadtreeToImage (qt->FilsSO);
   }
}

merci encore

d'abord ça ne marchera pas comme ça car là tu crée une image à chaque appel de la fonction...

Et je pense que ce qu'il nous faudrait pour t'aider c'est :

quelle est la définition minimum du quadtree, c'est-à-dire quand il n'y a plus d'enfants (tous les 4 NE, NO, SE, SO, sont NULL), quelle est la dimension de la zone.

Car de plus, quand tu fais GetHeight, ça ne donne pas vraiment d'indication...

Supposons un instant que l'élément du quadtree soit défini comme :

Code:

1
2
3
4
5
6
7
8
9
10
11
typedef struct PQuadtree {
int         x ;
int         y ;
int     width ;
int     height ;
int     valeur ;
PQuadtree FilsNO ;
PQuadtree FilsSO ;
PQuadtree FilsNE ;
PQuadtree FilsSE ;
} Quadtree ;

(ce que je ne sais absolument si c'est le cas).

Alors, la fonction serait quelque chose comme :

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
 
 
void QuadtreeToImage (Quadtree* qt, Image *a)
{
int i, j ;
int x0, y0, x ;
 
 if (qt != NULL)
   {
      for ( i = 0 ; i < qt->height ; i++ )
        {
           y0 = qt->y + i ;
           x0 = qt->x ;
 
           for ( j = 0 ; j < qt->width ; j++ )
             {
                 x = x0 + j ;
 
                 setValue (a,x,y0,qt->valeur);
             }
        }
 
     QuadtreeToImage (qt->FilsNE, a);
     QuadtreeToImage (qt->FilsNO, a);
     QuadtreeToImage (qt->FilsSE, a);
     QuadtreeToImage (qt->FilsSO, a);
   }

Et l'appel se ferait comme ceci :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
...
 int           h = 0 ;
 int           w = 0 ;
 int           flag = 0 ;
 Quadtree  qt ;
 
/* On obient le quadtree */
  statut = GetQuadtree ( &qt) ;
 
/* On explore le quadtree pour obtenir la taille de l'image a créer */
  flag = 0 ;
  GetImageWidth ( &qt, &w, &flag );
  flag = 0 ;
  GetImageHeight ( &qt, &h, &flag );
 
/* On crée l'image */
 Image* a = createImage(h,w);
 
/* On rempli l'image */
  QuadtreeToImage (qt, a);
 
....

Avec les fonction GetImage.. :

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
 
void GetImageWidth (Quadtree* qt, int *w, int *Flag)
{
 if (qt != NULL)
   {
           *w = *w + qt->width ;
           *Flag = (*Flag+1) % 2 ;
           if ( *Flag == 1 )
                GetImageWidth ( qt->filsSE, w, Flag );
           else
                GetImageWidth ( qt->filsNE, w, Flag );
   }
}
 
void GetImageHeight (Quadtree* qt, int *h, int *Flag)
{
 if (qt != NULL)
   {
           *h = *h + qt->height ;
           *Flag = (*Flag+1) % 2 ;
           if ( *Flag == 1 )
                GetImageHeight ( qt->filsSE, h, Flag );
           else
                GetImageHeight ( qt->filsSO, h, Flag );
   }
}

01/05/2007, 15h54
line86
Je ne m'attendais pas a une aussi longue réponse :oops:
Je te remercie beaucoup !!!!!!!!!!!!!!!!!!!!!!
Je suis entrain d'essayer de comprendre ce que tu m'as indiqué :oops:

Oui effectivement ca ne marchera pas énormément si je recréais mon image a chaque appel !
J'avais indiqué ma structure pour le quadtree dans mon premier message et j'avais indiqué que j'avais besoin que de la structure des fonctions pour traiter les images :$ Mais merci a toi de les avoir écrites ca me permet d'y voir plus clair !!!!

Pour la fonction:

Code:

QuadtreeToImage (Quadtree* qt, int h, int w, Image *a)

Quand tu fais les appels
Code:

1 2 3 4 QuadtreeToImage (qt->FilsNE, h, w, a); QuadtreeToImage (qt->FilsNO, h, w, a); QuadtreeToImage (qt->FilsSE, h, w, a); QuadtreeToImage (qt->FilsSO, h, w, a);
Je ne comprends pas comment tu fais pour envoyer des nouvelles valeurs pour h et w :oops:

merci encore pour cette réponse autant détaillée !!!
02/05/2007, 01h25
souviron34
Les nouveles valeurs ce n'est pas dans la fonction QuadtreeToImage.

Dans QuadtreeToImage les w et h sont fixes... Ils ont été calculés au préalable avec GetImageWidth et GetImageHeight.

Et d'ailleurs je viens de m'apercevoir d'une grossère erreur dans les fonctions :

:oops: :oops:

Milles excuses..

Il faut lire :

Pour QuadtreeToImage :
Code:

1 2 3 4 5 for ( i = 0 ; i < qt->height ; i++ ) { y0 = qt->y + i ; x0 = qt->x ;
et tu n'as du coup pas besoin des paramètres h et w....

Donc la fonction deviendrait :
Code:

1 2 void QuadtreeToImage (Quadtree* qt, Image *a)
Encore désolé pour cette mauvaise réponse..

[EDIT]

J'ai également directement modifié le code de mon post précédent, pour d'éventuelles futures consultations...

[/EDIT]
02/05/2007, 10h37
souviron34

je rajouterais de plus que si tu ne veux pas avoir une boucle infinie, il faudrait mettre un flag dans les quadtree pour vérifier que tu n'es pas déjà passé dedans...
02/05/2007, 18h36
line86

Merci beaucoup souviron34 pour toute cette aide et ce temps passé
:ave: :ave: :ave:
03/05/2007, 01h24
souviron34

lol de rien :D on est là un peur ça..

Par contre on ne connait toujours pas ta structure d'origine du quadtree...

Mais enfin si la solution marche, n'oublie pas le Tag Résolu :resolu: