FloodFill étendu non récursif

**jlf** · 05/06/2005, 14h00

bonjour

j'ai besoin d'un FloodFill un peu étendu par rapport à celui du GDI de Windaube
il faudrait notamment que je puisse paramètrer la fonction de comparaison des pixels, un test d'égalité stricte des couleurs n'étant pas suffisant, et sans utiliser une couleur de bordure (la limite de zone est marquée par un changement de couleur important, pas par une bordure au sens propre du mot)

c'est pour faire des trucs genre "magic wand" ...

je vois à peu près comment le faire en récursif en testant à chaque fois les 8 voisins de mon germe, mais sur des gros bitmaps avec de larges zones de couleurs semblables je risquerai certainement un débordement de pile, et le temps d'exécution risque d'être grand (?)

j'utilise Delphi

merci de votre aide
jlf

**Mac LAK** · 05/06/2005, 14h43

Envoyé par jlf

j'ai besoin d'un FloodFill un peu étendu par rapport à celui du GDI de Windaube

Change d'OS si celui-ci ne te plaît pas. Quand c'est pas des critiques parceque c'est "trop assisté", c'est des critiques parceque ce n'est "pas assez assisté"... Jamais contents...

Envoyé par jlf

il faudrait notamment que je puisse paramètrer la fonction de comparaison des pixels, un test d'égalité stricte des couleurs n'étant pas suffisant, et sans utiliser une couleur de bordure (la limite de zone est marquée par un changement de couleur important, pas par une bordure au sens propre du mot)

Effectue ton flood fill sur ton image, mais en comparant avec les pixels d'une dérivée de l'image, obtenue par application d'un filtre de gradient (ex : Sobel). C'est un détecteur de contours, la valeur des pixels obtenue correspond à la "force" de la transition de couleur. Il te suffit de calculer cette dérivée sur un bitmap caché (=en mémoire), car il n'est pas nécessaire de l'afficher. Ce n'est même pas nécessaire d'avoir un vrai bitmap, d'ailleurs : tu peux te contenter d'aller récupérer les pixels dans la propriété Scanline de ton TBitmap.

Envoyé par jlf

je vois à peu près comment le faire en récursif en testant à chaque fois les 8 voisins de mon germe, mais sur des gros bitmaps avec de larges zones de couleurs semblables je risquerai certainement un débordement de pile, et le temps d'exécution risque d'être grand (?)

La méthode du germe, bien que "parfaite" d'un point de vue algo, est très lente. Et à 8 voisins, "fermer" la zone devient très difficile, étant donné que l'algo va pouvoir passer "au travers" d'une ligne à 45°... On n'utilise que 4 voisins, habituellement.

Perso, j'utilise plutôt un remplissage type raster :
1) Prendre un point d'origine.
2) Tracer au maximum à gauche jusqu'à la condition d'arrêt (quelle que soit cette condition d'arrêt).
3) Arrivé à l'arrêt, mémoriser la position du pixel.
4) Refaire la même manip à droite. Arrivé à la condition d'arrêt, tracer la ligne directement.
5) Propager le tracé en haut, puis en bas de l'origine.
6) Lorsque la propagation verticale s'arrête, continuer à droite et à gauche pour trouver les "trous" => tu vas obtenir deux lignes à tracer et non plus une seule, puis 3, 4, etc...

Tu saisis le principe ? Ca demande beaucoup, BEAUCOUP moins de mémoire que le floodfill classique, et c'est plus rapide à tracer.
Accessoirement, c'est l'algo de tracé du GDI, à l'opération de comparaison près...

Bien sûr, il faut penser à chaque "butée" à propager dans les 4 directions, sinon les formes très concaves ne peuvent être remplies.

Une autre solution, assez élégante, consisterai à :
1) Dériver l'image.
2) Seuiller cette dérivée pour obtenir des zones "à remplir" (= sous un certain seuil, noir) et des zones "à éliminer" (=au dessus d'un certain seuil, blanc). Tu obtiens donc une image à 2 couleurs.
3) "Fermer" cette zone, avec un FloodFill GDI et une troisième couleur (ex : rouge) : tu vas donc avoir 3 couleurs :
- Rouge : Pixels sous le seuil, connexes avec l'origine du remplissage.
- Blanc : Pixels au dessus du seuil, à éliminer.
- Noir : Pixels sous le seuil, mais non-connexes, à éliminer aussi.
4) Tu convertis l'image en N&B de nouveau : rouge => noir, noir => blanc, blanc => blanc.
5) Tu obtiens un masque binaire, correspondant à ta "magic wand", à appliquer à ton image d'origine : une opération de copie de bitmap fera alors le reste, suivant ce que tu veux faire.

Cette méthode est normalement très rapide, car elle peut profiter d'un maximum d'accélération matérielle (FloodFill et copie/transferts de bitmaps).

**jlf** · 05/06/2005, 15h28

Change d'OS si celui-ci ne te plaît pas. Quand c'est pas des critiques parceque c'est "trop assisté", c'est des critiques parceque ce n'est "pas assez assisté"... Jamais contents...

ça me rappelle un proverbe qui dit en gros : "si tu n'est pas content de ton voisin recule ta maison"
c'est une soluce, bien sûr

Une autre solution, assez élégante, consisterai à :
1) Dériver l'image.
2) Seuiller cette dérivée pour obtenir des zones "à remplir" (= sous un certain seuil, noir) et des zones "à éliminer" (=au dessus d'un certain seuil, blanc). Tu obtiens donc une image à 2 couleurs.

j'aime bien cette idée, effectivement élégante et à ma portée a priori

mais quelle "dérivation" faut-il faire ?

il y a quelques jours sur ce forum j'ai entendu parlé des filtres graphiques

je n'ai pas vraiment mis en application mais j'ai cru comprendre que ça consiste à multiplier une matrice constante par toutes les matrices possibles de même taille fabriquées avec n pixels contigus, la matrice résultat de chaque produit étant collée d'une manière encore mystérieuse pour moi (entière ou juste les valeurs centrales ?) dans un bitmap vide

est-ce cela la dérivation que tu évoques ?

si oui quelle matrice faut-il appliquer en (1), et en (2) je suppose que le seuil à appliquer dépend alors de la matrice constante utilisée, comment le déterminer ?

quoi qu'il en soit merci d'avoir déjà éclairé un peu l'ignare que je suis
bien amicalement
jlf

**Mac LAK** · 05/06/2005, 15h55

Envoyé par jlf

ça me rappelle un proverbe qui dit en gros : "si tu n'est pas content de ton voisin recule ta maison"
c'est une soluce, bien sûr

Il est bien, ce proverbe... On dirait un truc hindou ou arabe, oriental en tout cas.
Sinon, c'est vrai que ça m'énerve que l'on dénigre à tout bout de champ cet OS, surtout lorsqu'on l'utilise... Ca n'aurait pas été sur de l'imagerie, je n'aurais même pas répondu à cause de cette remarque, tu sais ?

Envoyé par jlf

j'aime bien cette idée, effectivement élégante et à ma portée a priori

Merci.

Envoyé par jlf

mais quelle "dérivation" faut-il faire ?

Un filtre Sobel, par exemple.
En fait, il faut calculer ce que l'on appelle le gradient de l'image, en général obtenu par application de deux filtres simples par convolution.

Envoyé par jlf

je n'ai pas vraiment mis en application mais j'ai cru comprendre que ça consiste à multiplier une matrice constante par toutes les matrices possibles de même taille fabriquées avec n pixels contigus, la matrice résultat de chaque produit étant collée d'une manière encore mystérieuse pour moi (entière ou juste les valeurs centrales ?) dans un bitmap vide

En très gros... Ton explication revient à "Comment expliquer un truc simple de manière imbitable"... ;-)

Envoyé par jlf

si oui quelle matrice faut-il appliquer en (1), et en (2) je suppose que le seuil à appliquer dépend alors de la matrice constante utilisée, comment le déterminer ?

En général, on utilise des filtres séparables, ça va beaucoup plus vite qu'une convolution "complète".
Un filtre de Sobel, c'est la combinaison de deux filtres horizontaux et verticaux de composantes [-1 2 -1].
Tu appliques d'abord le filtre vertical sur l'image, tu obtiens les contours horizontaux. Puis, sur une seconde copie, tu appliques le filtre horizontal (tu obtiens les contours verticaux).
Ensuite, tu fusionnes les deux images (avec une moyenne des pixels, par exemple) pour obtenir ton image "finale". C'est ça, la dérivée de l'image.

Je n'ai pas sous la main la théorie mathématique de la convolution de matrices, mais plusieurs ici ont ce qu'il faut : il suffit de demander...

Voici un bout de code pour appliquer les deux types de convolutions en Delphi. Il est "brut de fonderie", je l'ai simplement extrait d'une de mes unités.

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
Type
    // Type vecteur pour convolutions.
    TVector = Array Of Real ;
 
    // Type FrameBuffer (interne).
    TFrameBuffer = Array Of PByteArray ;
 
procedure ConvolveH (const Vector: TVector);
Var
   X, Y, P, D : Integer ;
   N          : Real    ;
begin
     // Protection.
     If (Length(Vector)<2) Then
        Raise EAbstractImage.Create(aisBadVector);
     If Not Odd(Length(Vector)) Then
        Raise EAbstractImage.Create(aisBadVector);
     // Copie de l'ancienne image.
     EnableBackup;
     // Centrage du vecteur.
     D:=Length(Vector) Div 2;
     // Convolution.
     For Y:=0 To (FSize.Y-1) Do
         For X:=0 To (FSize.X-1) Do
             If (X<D) Or (Y<D) Then FFrameBuffer[Y]^[X]:=FBakFrame[Y]^[X]
                               Else Begin
                                    N:=0;
                                    // On applique le vecteur.
                                    For P:=-D To D Do
                                        N:=N+Vector[P+D]*FBakFrame[Y]^[Min(X+P,(FSize.X-1))];
                                    FFrameBuffer[Y]^[X]:=Round(N);
                                    End;
     // Destruction de l'ancienne image.
     DisableBackup;
     // Fin du traitement, l'image est convoluée.
     FChanged:=True;
end;
 
procedure ConvolveV (const Vector: TVector);
Var
   X, Y, P, D : Integer ;
   N          : Real    ;
begin
     // Protection.
     If (Length(Vector)<2) Then
        Raise EAbstractImage.Create(aisBadVector);
     If Not Odd(Length(Vector)) Then
        Raise EAbstractImage.Create(aisBadVector);
     // Copie de l'ancienne image.
     EnableBackup;
     // Centrage du vecteur.
     D:=Length(Vector) Div 2;
     // Convolution.
     For Y:=0 To (FSize.Y-1) Do
         For X:=0 To (FSize.X-1) Do
             If (X<D) Or (Y<D) Then FFrameBuffer[Y]^[X]:=FBakFrame[Y]^[X]
                               Else Begin
                                    N:=0;
                                    // On applique le vecteur.
                                    For P:=-D To D Do
                                        N:=N+Vector[P+D]*FBakFrame[Min(Y+P,(FSize.Y-1))]^[X];
                                    FFrameBuffer[Y]^[X]:=Round(N);
                                    End;
     // Destruction de l'ancienne image.
     DisableBackup;
     // Fin du traitement, l'image est convoluée.
     FChanged:=True;
end;

Bon, y'a du taf qui reste, c'est évident...
En gros : FFrameBuffer est une représentation virtuelle de l'image, tu peux la remplacer par l'accès à la propriété Scanline d'un TBitmap.
FBakFrame est la copie (=instance précédente) du frame buffer. On s'en sert parcequ'il faut impérativement utiliser l'image originale non modifiée pour calculer la convolution.
EnableBackup copie le frame buffer courant vers sa copie. En pratique, ça alloue un nouveau frame buffer, et stocke l'ancien comme étant une copie.
DisableBackup ne fait que détruire la copie de backup.

OK ?

**jlf** · 05/06/2005, 16h46

Voici un bout de code pour appliquer les deux types de convolutions en Delphi

merci c'est super sympa

comme tu n'utilises qu'une valeur par pixel j'en déduis que pour une image RVB il faut d'abord la mettre en tons de gris (r+g+b/3) ?

puis à chaque fois tu doubles l'intensité du pixel central et lui retire la valeur de ses deux voisins (vecteurs -1,2,-1)

j'intuite que ça doit laisser des pixels le plus souvent proches de 0 ou 255, rarement dans des tons centraux, et de ce fait à l'étape suivante (binarisation) il me suffit de choisir un seuil genre 255/2 ?

**Mac LAK** · 05/06/2005, 18h22

Envoyé par jlf

comme tu n'utilises qu'une valeur par pixel j'en déduis que pour une image RVB il faut d'abord la mettre en tons de gris (r+g+b/3) ?

Non, c'est parceque je travaillais sur des images en niveaux de gris. Tu peux y mettre un RGBQUAD par exemple, ou le faire 3 fois (une fois par canal, R, G et B) : en effet, chaque canal couleur est considéré comme une image en niveaux de gris.
Convertir ton image en niveaux de gris, ça améliorera la performance, au prix de la précision. Le faire 3 fois, ça sera précis, mais plus lent. A toi de voir quel est le critère le plus important pour toi...
A propos, la formule de conversion RGB->Gr est celle-ci :

Code :

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

Gr = 0.3R + 0.59G + 0.11B

Envoyé par jlf

puis à chaque fois tu doubles l'intensité du pixel central et lui retire la valeur de ses deux voisins (vecteurs -1,2,-1)

Ouch, je viens de relire, je devais être bourré, moi...

Bon, le filtre de Sobel, c'est ça :

Code :

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

1
2
3
/ -1 0 1 \    / -1 -2 -1 \
| -2 0 2 | et |  0  0  0 |
\ -1 0 1 /    \  1  2  1 /

Ce qui donne, en filtres séparés :

Code :

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

1
2
3
4
5
6
7
8
9
/ 1 \
| 2 | et [ -1 0 1 ]
\ 1 /
 
puis
 
/ -1 \
|  0 | et [ 1 2 1 ]
\  1 /

J'ai fait je ne sais pas quel mélange, moi... Désolé.
Donc, pour calculer le gradient "final", ça fera 4 convolutions 1D à appliquer, OK ?
Pour appliquer le 1er opérateur de Sobel sur ton image, tu vas enchaîner un appel à ConvolveH, puis ConvolveV, mais sans modifier l'image entre les deux convolutions !!

Envoyé par jlf

à l'étape suivante (binarisation) il me suffit de choisir un seuil genre 255/2 ?

Non, tu vas choisir un seuil en fonction de la "puissance" de ton FloodFill : si tu le mets très bas (genre 10), tu va prendre des pixels très voisins. Si, par contre, tu le prends à 100, tu vas "prendre" beaucoup plus de pixels, même s'ils sont assez différents au final.
Fais des essais, ce sera le plus simple pour te rendre compte de l'effet... Essaie à 5, 20, 128, 200 et 240 pour bien voir ce que ça donne.

OK ?

**jlf** · 05/06/2005, 19h48

Donc, pour calculer le gradient "final", ça fera 4 convolutions 1D à appliquer, OK ?
Pour appliquer le 1er opérateur de Sobel sur ton image, tu vas enchaîner un appel à ConvolveH, puis ConvolveV, mais sans modifier l'image entre les deux convolutions !!

bon si j'ai bien compris soit je passe successivement les 2 matrices 3x3, soit, c'est plus rapide, je passe 4 fois les vecteurs 1x3 ou 3x1 vers 4 bitmaps "neufs" avec tes fonctions :
- ConvolV avec (1, 2, 1)
- ConvolH avec (-1, 0, 1)
- ConvolV avec (-1, 0, 1)
- ConvolH avec (1, 2, 1)

je fusionne les 4 bitmaps en 1 seul en "moyennisant" les r, g, b de chaque pixel :
R := (r1+r2+r3+r4)/4, G = etc

puis je binarise en testant plusieurs seuils, ce qui signifie que ce seuil variera en fonction du bitmap traité et que ce n'est pas vraiment automatisable ?

**Mac LAK** · 06/06/2005, 00h33

Envoyé par jlf

bon si j'ai bien compris soit je passe successivement les 2 matrices 3x3, soit, c'est plus rapide, je passe 4 fois les vecteurs 1x3 ou 3x1 vers 4 bitmaps "neufs" avec tes fonctions :
- ConvolV avec (1, 2, 1)
- ConvolH avec (-1, 0, 1)
- ConvolV avec (-1, 0, 1)
- ConvolH avec (1, 2, 1)

Non, tu n'as que 2 bitmaps "neufs", tu passera 2 convolutions de vecteurs à la suite. En effet, le fait de pouvoir passer deux vecteurs au lieu d'une matrice est liée à la séparation du filtre, mais il faut passer les deux pour faire l'équivalent d'un filtre 3x3 ! Rappelles-toi de tes cours de maths : un vecteur 3x1 multiplié par un vecteur 1x3, ça donne une matrice 3x3... Multiplie les paires de vecteurs que je t'ai donnés, tu verras que tu retombera sur les opérateurs (les matrices) de Sobel.
Donc, en pseudo-algo :
- A = Copy(Image).
- B = Copy(Image).
- A=ConvolV(A,(1, 2, 1))
- A=ConvolH(A,(-1, 0, 1))
- B=ConvolV(B,(-1, 0, 1))
- B=ConvolH(B,(1, 2, 1))
- Dérivée(Image) = Fusion(A,B)

Envoyé par jlf

je fusionne les 4 bitmaps en 1 seul en "moyennisant" les r, g, b de chaque pixel :
R := (r1+r2+r3+r4)/4, G = etc

Tu n'en auras que deux, mais c'est ça.

Envoyé par jlf

puis je binarise en testant plusieurs seuils, ce qui signifie que ce seuil variera en fonction du bitmap traité et que ce n'est pas vraiment automatisable ?

Non, pour la simple et très bonne raison que ta "magic wand" doit avoir un paramétrage... Tu peux le calculer plus ou moins automatiquement, mais il faut bien définir un critère... Celui-ci peut devenir "permanent", mais il va falloir que tu cherches un minimum "la" bonne valeur en fonction des images que tu traites.
Par exemple, si ce sont des scans de dessins type "ligne claire" (des dessins type Tintin, si tu ne connais pas), un seuil très bas va suffire.
Par contre, si ce sont des digitalisations de photos "réelles", le seuil va devoir être relativement haut.

Tu remarqueras que dans les logiciels de retouche d'image, il est toujours possible de "régler" la force de l'outil "magic wand"... Ben tu devras faire pareil. Même si le réglage sera finalement fait "une fois pour toutes" dans ton programme, il te faudra bien trouver une valeur de seuillage adéquate !!

OK ?