algorithme de remplissage en 4 connexité (lent) -> image non remplie complètement

**piponux** · 17/12/2016, 08h03

Bonjour,
j'ai écrit une fonction de remplissage en 4 connexité, mais le résultat n'est pas "plein". Il y a beaucoup de pixels oubliés. Cela vient-il du fait qu'il s'agit d'une '4-connexité' et non d'un '8-connexité'?

Code c :

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
void flood_fill (image I, int x, int y, colour couleur_de_remplissage)
{
 int position_P1 = image_offset (I, x, y);
 
 fifo F = standard_empty_fifo_create (NULL, NULL, NULL, NULL);
 fifo_push (F, (void*) position_P1);
 
 
 int position_P_nord = 0;
 int position_P_sud = 0;
 int position_P_est = 0;
 int position_P_ouest = 0;
 
 int position_P_diagonale_haut_gauche = 0;
 int position_P_diagonale_bas_gauche = 0;
 int position_P_diagonale_haut_droite = 0;
 int position_P_diagonale_bas_droite = 0;  
 
 
 while (!is_fifo_empty (F))
  {
    /* 
   assert (position_P1 >= 0);
   assert (position_P_nord >= 0);
   assert (position_P_sud < I->h);
   assert (position_P_est < I->w);
   assert (position_P_ouest >= 0);
   */
 
   if (position_P_sud > I->h) position_P_sud = I->h - 1;
   if (position_P_nord < 0) position_P_nord = 0;
   if (position_P_est < 0) position_P_est = 0;
   if (position_P_ouest > I->w) position_P_ouest = I->w -1;
 
 
   position_P1 = (int) fifo_pop (F);   
 
 
 
 
   /*if ((I->pixel[position_P1] != c) && (I->pixel[position_P1] == 0x000000FF)) return;*/
   /*if (I->pixel[position_P1] == 0x000000FF) return;*/
   if (I->pixel[position_P1] != couleur_de_remplissage) I->pixel[position_P1] = couleur_de_remplissage;
 
 
   position_P_nord = position_P1 - I->w;
   position_P_sud = position_P1 + I->w;
   position_P_est = position_P1 + 1;
   position_P_ouest = position_P1 - 1;
 
   position_P_diagonale_haut_gauche = position_P_nord - 1;
   position_P_diagonale_bas_gauche = position_P_sud - 1;
   position_P_diagonale_haut_droite = position_P_nord + 1;
   position_P_diagonale_bas_droite = position_P_nord + 1;  
 
/*
   if (position_P_diagonale_haut_gauche < 0) position_P_diagonale_haut_gauche = 0;
 
   if (position_P_diagonale_haut_droite > I->w) position_P_diagonale_haut_droite = I->w - 1;
   if (position_P_diagonale_haut_droite < 0) position_P_diagonale_haut_droite = 0;   
 
   if (position_P_diagonale_bas_droite > I->w) position_P_diagonale_haut_droite = I->w - 1;
   if (position_P_diagonale_bas_droite > I->h) position_P_diagonale_bas_droite = I->h - 1;   
 
   if (position_P_diagonale_bas_gauche < 0) position_P_diagonale_bas_gauche = 0;
   if (position_P_diagonale_bas_gauche > I->h) position_P_diagonale_bas_gauche = I->h -1;   
 
*/
 
   if ((I->pixel[position_P_nord] != couleur_de_remplissage) && (I->pixel[position_P_nord] != 0x000000FF)) 
     fifo_push (F, (void*) position_P_nord);
 
   if ((I->pixel[position_P_sud] != couleur_de_remplissage) && (I->pixel[position_P_sud] != 0x000000FF)) 
     fifo_push (F, (void*) position_P_sud);
 
   if ((I->pixel[position_P_est] != couleur_de_remplissage) && (I->pixel[position_P_est] != 0x000000FF)) 
     fifo_push (F, (void*) position_P_est);
 
   if ((I->pixel[position_P_ouest] != couleur_de_remplissage) && (I->pixel[position_P_ouest] != 0x000000FF)) 
     fifo_push (F, (void*) position_P_ouest);
 
 
/*        
    if ((I->pixel[position_P_diagonale_haut_gauche] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_haut_gauche] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_haut_gauche);
 
   if ((I->pixel[position_P_diagonale_haut_droite] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_haut_droite] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_haut_droite);
 
 
   if ((I->pixel[position_P_diagonale_bas_gauche] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_bas_gauche] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_bas_gauche);
  
   if ((I->pixel[position_P_diagonale_bas_droite] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_bas_droite] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_bas_droite);
      
        
  */      
 
 
 
 
 
   fifo_remove(F);
 
  }
 
 fifo_destroy(&F);
 
}

**Matt_Houston** · 17/12/2016, 10h09

Code :

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

position_P_diagonale_bas_droite = position_P_nord + 1;

Il semble déjà qu'un bug se soit glissé ici.

**devbreizhbugs** · 17/12/2016, 15h49

Envoyé par Matt_Houston

Code :

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

position_P_diagonale_bas_droite = position_P_nord + 1;

Il semble déjà qu'un bug se soit glissé ici.

Il me semble que cette partie est commenté car il ne l'utilise pas en 4-conexités...

Moi je miserai plutot sur le fifo_remove ligne 100 qui n'as pas lieu d'être puisqu'un fifo_pop (ligne 36) est censé retiré l'élément de tête...
Cela dit, il me semble que le calcul
position_P_nord = position_P1 - I->w;
position_P_sud = position_P1 + I->w;
position_P_est = position_P1 + 1;
position_P_ouest = position_P1 - 1;
est faux pour est et ouest aux abord de l'image!... il est plus facile de passer par de la 2d(x,y) ...
Pourquoi ne pas simplement pusher un vecteur 2D et juste faire la conversion 1D pour l'accès au tableau?

**piponux** · 17/12/2016, 16h13

Bonjour et merci pour votre intérêt sur la question.

Effectivement, la position de la diagonale bas droite n'était pas bonne.
J'utilise la 4 connexité. Je commente la 8 connexité car j'ai des erreurs de segmentation en pagaille.

Et, je ne l'avais pas vu, mais c'est vrai, la fonction fifo_pop retire l'élément après qu'on l'ait récupéré. A la différence de fifo_remove, qui retire purement et simplement l'élément, sans qu'on l'ait récupéré.

Merci à tous deux, je reviendrai ici pour vous dire si j'ai réussi (ou pas) à faire tourner ma fonction de remplissage.

**piponux** · 17/12/2016, 18h14

Bon, voilà, en rajoutant le pixel en haut à gauche et le pixel en bas à droite, j'arrive presque à ce que je veux, sauf qu'il y a deux pixels non peints (à côté de chaque "fenêtre" - j'ai dessiné une maison - elle est pas belle ma maison ?)

ça ne marche toujours pas en 8 connexité.

Code c :

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
void flood_fill (image I, int x, int y, colour couleur_de_remplissage)
{
 int position_P1 = image_offset (I, x, y);
 
 fifo F = standard_empty_fifo_create (NULL, NULL, NULL, NULL);
 fifo_push (F, (void*) position_P1);
 
 
 int position_P_nord = 0;
 int position_P_sud = 0;
 int position_P_est = 0;
 int position_P_ouest = 0;
 
 int position_P_diagonale_haut_gauche = 0;
 int position_P_diagonale_bas_gauche = 0;
 int position_P_diagonale_haut_droite = 0;
 int position_P_diagonale_bas_droite = 0;  
 
 
 while (!is_fifo_empty (F))
  {
   assert (position_P1 >= 0);
   assert (position_P_nord >= 0);
   assert (position_P_sud < (I->h * I->w));
   assert (position_P_est < (I->w * I->h));
   assert (position_P_ouest >= 0);
 
   position_P1 = fifo_pop(F);
   fifo_remove(F);
 
   if (I->pixel[position_P1] != couleur_de_remplissage) I->pixel[position_P1] = couleur_de_remplissage;
 
 
   position_P_nord = position_P1 - I->w; 
   position_P_sud = position_P1 + I->w; 
   position_P_est = position_P1 + 1;     
   position_P_ouest = position_P1 - 1; 
 
   if ((I->pixel[position_P_nord] != couleur_de_remplissage) && (I->pixel[position_P_nord] != 0x000000FF))
     fifo_push (F, (void*) position_P_nord);
 
   if ((I->pixel[position_P_sud] != couleur_de_remplissage) && (I->pixel[position_P_sud] != 0x000000FF))
     fifo_push (F, (void*) position_P_sud);
 
   if ((I->pixel[position_P_est] != couleur_de_remplissage) && (I->pixel[position_P_est] != 0x000000FF))
     fifo_push (F, (void*) position_P_est);
 
   if ((I->pixel[position_P_ouest] != couleur_de_remplissage) && (I->pixel[position_P_ouest] != 0x000000FF))
     fifo_push (F, (void*) position_P_ouest);
 
 
 
   position_P_diagonale_haut_gauche = position_P1 - I->w - 1;
   position_P_diagonale_bas_droite = position_P1 + I->w + 1;  
 
   if ((I->pixel[position_P_diagonale_haut_gauche] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_haut_gauche] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_haut_gauche);
 
 
   if ((I->pixel[position_P_diagonale_bas_droite] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_bas_droite] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_bas_droite); 
 
  }
 
 fifo_destroy(&F);
 
}

**devbreizhbugs** · 17/12/2016, 20h12

Envoyé par piponux

Et, je ne l'avais pas vu, mais c'est vrai, la fonction fifo_pop retire l'élément après qu'on l'ait récupéré. A la différence de fifo_remove, qui retire purement et simplement l'élément, sans qu'on l'ait récupéré.
.

Ben supprime tes appels à fifo_remove alors!
Tes calculs de position sont toujours incorrects!

**piponux** · 17/12/2016, 20h41

Si je retire fifo remove j ai des erreurs de segmentation.

**devbreizhbugs** · 17/12/2016, 23h12

C'est quoi le code lié à fifo?
tu n'as pas corrigé les formules de calcul de position...

**piponux** · 17/12/2016, 23h21

le code lié à fifo se trouve sur multiparadigme, le site de Jacques Olivier Lapeyre, la partie sur les listes doublement chaînées, unité 2, dossier Cfuns. "dlist.c"

J'ai beau retourner le pb dans tous les sens

, il me semble que je ne me trompe pas dans le calcul de la position des pixels.

**devbreizhbugs** · 18/12/2016, 00h24

Envoyé par piponux

le code lié à fifo se trouve sur multiparadigme, le site de Jacques Olivier Lapeyre, la partie sur les listes doublement chaînées, unité 2, dossier Cfuns. "dlist.c"

T'es obligé d'utiliser ça?

Envoyé par piponux

J'ai beau retourner le pb dans tous les sens

, il me semble que je ne me trompe pas dans le calcul de la position des pixels.

Quand tu es sur un bord (gauche / droite) et que tu veux bouger vers l'Est / L'Ouest, juste décrémenter / incrémenter de 1 fait que tu changes de bord!
Au lieu de floodfill ta maison (au centre de l'image), divise ton image en 2 verticalement et colorie un seul coté pour voir?)
Sinon la 4-connexité marche très bien (en c# par contre!)
Le "plus" de la 8 connexité c'est quelle considère ce genre de chemin possible:
1 0 0
0 1 0
0 0 1
mais il ne se présente pas dans ton dessin...
(
la 4 connexité a besoins d'une diagonale plus large pour passée:
1 1 0 0
0 1 1 0
0 0 1 1
)

**piponux** · 18/12/2016, 08h24

Envoyé par devbreizhbugs

T'es obligé d'utiliser ça?

Non, mais c'est un modèle de liste doublement chaînée avec un curseur, une cellule appelée "sentinelle" et un memory pool. C'est trés rapide.
La liste vide ne pointe pas sur NULL, mais sur la sentinelle.
moi, j'aime bien.

**piponux** · 18/12/2016, 09h45

Ca y est, j'ai réussi à faire ce que je voulais!
la fonction marche du feu de dieu :

- plus aucune erreur de segmentation (en fait, il y avait un if qui n'avait pas d'effet car je n'avais pas mis les accolades au bon endroit).
-> au passage, les positions de mes pixels sont bonnes depuis le début

voici donc le code de ma fonction (je ne suis pas peu fier)

j'ai réussi en suivant l'algo sur wikipedia : https://fr.wikipedia.org/wiki/Algori..._par_diffusion

Code c :

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
 
void flood_fill (image I, int x, int y, colour couleur_de_remplissage)
{
 
 int position_P1 = image_offset (I, x, y);
 
 fifo F = standard_empty_dlist_create (NULL, NULL, &generic_int_print, NULL);
 fifo_push (F, (void*) position_P1);
 
 
 int position_P_nord = image_offset (I, x, y-1);
 int position_P_sud = image_offset (I, x, y+1);
 int position_P_est = image_offset (I, x+1, y);
 int position_P_ouest = image_offset (I, x-1, y);
 
 
 int position_P_diagonale_haut_gauche = image_offset (I, x-1, y-1);
 int position_P_diagonale_bas_droite = image_offset (I, x+1, y+1); 
 
 int position_P_diagonale_bas_gauche = image_offset (I, x-1, y+1);
 int position_P_diagonale_haut_droite = image_offset (I, x+1, y-1); 
 
 while (!is_fifo_empty (F))
  {
 
   assert ((position_P1 >= 0) || (position_P1 < I->w * I->h));
   assert ((position_P_nord >= 0) || (position_P_nord < I->w * I->h));
   assert (position_P_sud < (I->h * I->w));
   assert (position_P_est < (I->w * I->h));
   assert ((position_P_ouest >= 0) || (position_P_ouest < I->w * I->h));
 
 
   position_P1 = fifo_pop(F);
   position_P_nord = position_P1 - I->w; 
   position_P_sud = position_P1 + I->w;  
   position_P_est = position_P1 + 1; 
   position_P_ouest = position_P1 - 1; 
 
   if (I->pixel[position_P1] != 0xFF0000FF && I->pixel[position_P1] != couleur_de_remplissage)
    {
 
    I->pixel[position_P1] = couleur_de_remplissage;
 
    if (I->pixel[position_P_nord] != couleur_de_remplissage && I->pixel[position_P_nord] != 		0x000000FF)     
       fifo_push (F, (void*) position_P_nord);
    if (I->pixel[position_P_est] != couleur_de_remplissage && I->pixel[position_P_est] != 		0x000000FF)      
       fifo_push (F, (void*) position_P_est);
    if (I->pixel[position_P_sud] != couleur_de_remplissage && I->pixel[position_P_sud] != 		0x000000FF)     
       fifo_push (F, (void*) position_P_sud);
    if (I->pixel[position_P_ouest] != couleur_de_remplissage && I->pixel[position_P_ouest] != 		0x000000FF)       
       fifo_push (F, (void*) position_P_ouest);
 
    }  
 
  }
 
 fifo_destroy(&F);
 
}

**piponux** · 18/12/2016, 09h54

Avec une image TGA 24 bit non compressée en dimensions 1600 x 960 :

real 0m0.131s
user 0m0.120s
sys 0m0.000s

Je ne trouve pas cet algo si lent finalement.

**Matt_Houston** · 18/12/2016, 10h07

Passe tout de même ton code à valgrind, c'est pas bon signe ces crashes qui disparaissent.

**piponux** · 18/12/2016, 10h30

ok, merci du conseil, le temps d'installer valgrind et de voir comment ça marche.

**CodeurPlusPlus** · 18/12/2016, 22h31

Effectivement, fifo_pop retire l'élément retourné de la liste, donc la version où il était suivi d'un fifo_remove ne pouvait pas être correcte.

Jacques-Olivier

**piponux** · 19/12/2016, 07h29

Bonjour Jacques-Olivier.
Un grand merci pour tes vidéos sur youtube. C'est clairement cela qui m'a donné le goût de programmer en c.
Effectivement, avec fifo_remove, je détruisais deux fois plus de cellules que ce que je croyais. Donc, quand j'arrivais en fin de liste, je demandais à ce que la dernière cellule soit détruite, alors qu'elle n'existait déjà plus.

algorithme de remplissage en 4 connexité (lent) -> image non remplie complètement

C

Discussions similaires

Partager

Partager