Discussion :

[BeanzMaster]

Bonjour à tous je suis entrain d'étudier différents algorithmes de détection de contours. Après diverses lectures, j'ai un petit truc que je ne saisie pas très bien c'est la notion de "gradient"

Pour calculer un "gradient" on applique un filtre de convolution, et c'est là que je décroche un peu d'un point de vue compréhension.

Là ou j'ai un doute, c'est lorsque que l'on applique un filtre de convolution on divise le résultat par une valeur.
(par exemple pour Sobel le diviseur est 4)

Mais pour le calcul du "gradient" on ne divise pas c'est bien ça ?
Le calcul du "gradient" diffère-t-il légèrement de la convolution ?
Doit on borner le résultat dans l'intervalle [0,1] ?

Voici une partie simplifiée du code (en pascal) que j'utilise pour la convolution

Code pascal :

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
For Y := 0 To ImageHeight-1 Do
begin
  For X := 0 To ImageWidth-1 Do
  begin
       For J := 0 To KS Do //taille de la matrice = KSxKS
       Begin
          // Position Source Y
          pY := Clamp(Y + J - KSDiv2, OwnerBitmap.ClipRect.Top, OwnerBitmap.ClipRect.Bottom);
          moffset := J * Size;
          For I := 0 To KS Do
          Begin
            // Position Source X
            pX := Clamp(X + I - KSDiv2, OwnerBitmap.ClipRect.Left, OwnerBitmap.ClipRect.Right);
            KernelValue := aMatrix[moffset + I]; // Valeur dans la matrice
            FColor := TmpBmp.GetPixel(pX, pY).AsColorVector;
            // Convolution standard
            FColor := FColor * KernelValue;
            SumRec := SumRec + FColor;           
        end;
     end;
     SumRec := SumRec * RDiv; // RDIV = 1/Divisor
     SumRec := SumRec + (Bias * _FloatColorRatio);
     AColor.Create(SumRec);
     DstPtr^ := AColor;   
  end;
end;

et les données du filtre de sobel par exemple

Code pascal :

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

1
2
3
4
5
6
7
8
9
10
11
12
    ( 
     Name    : 'Sobel horizontal';
     Category : cfcEdgeDetect;
     Bias    : 0;
     Divisor : 4;
     MatrixType : mct3x3;
     MatrixSize : 3;
     Matrix  : (_3 : ( -1,-2,-1,
                        0, 0, 0,
                        1, 2, 1
               ));
    )

Après pour le reste ca va (je pense) :
la norme c'est Sqrt(Gx² + Gy²)
et pour la direction c'est Tan^-1(gx/gy) = arctan2(gx,gy)

Merci d'avance pour vos éclaircissements

Jérôme

[dev_ggy]

Bonjour,

Je comprends mal ta situation parce que je pense que tu dois confondre des choses.

Concernant le traitement d'Image, je connais deux raisons d'utiliser un Gradient.

Dans le premier cas, c'est avec un filtre comme le H.O.G. Histogramme Orienté Gradient qui ressemble sur le principe au Sobel.

Dans le second c'est dans le cas de Machine Learning pour classifier des images à travers soi un réseau de neurone, soit sur des résultats de filtres pour la machine learning classique.

Je ne prétends pas tout connaitre, mais je pense que cela peut t'aider.

Cordialement,

[BeanzMaster]

Bonjour

Cette notion de Gradient est aussi utilisé dans le cas de détection des contours, le truc c'est qu'il fallait que j'applique mes matrices horizontalement et verticalement sans diviser mes valeurs puis calculer la norme entre ces 2 valeurs. Si j'ai bien tout compris. Dans tous les cas mon détecteur de Canny fonctionne .

Code pascal :

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
function TBZBitmapSegmentationFilters.ComputeConvolutionGradientY(aMode : TBZDetectEdgeFilterMode) : TBZSingle2DMap;
Var
  size, moffset, idx, grad, x, y, i, j, pX, pY : Integer;
  KS, KSDiv2: Byte;
  KernelValue, K: Single;
  Sum, Value : Single;
  aMatrix : Array of Single;
begin
  Case aMode of
    defPrewitt: idx := 17;
    defSobel: idx := 21;
    defRoberts: idx := 19;
    defKirsch: idx := 23;
    defScharr: idx := 25;
    defRobinson: idx := 27;
    defMDif: idx := 29;
    defLaplace: idx := 38;
  end;
 
  Size := BZConvolutionFilterPresets[idx].MatrixSize;
  Case size of
    3: aMatrix := BZConvolutionFilterPresets[idx].Matrix._3;
    5: aMatrix := BZConvolutionFilterPresets[idx].Matrix._5;
    7: aMatrix := BZConvolutionFilterPresets[idx].Matrix._7;
  end;
 
  KS := Size - 1;
  KSDiv2 := KS Div 2;
 
  Result := TBZSingle2DMap.Create(OwnerBitmap.Width, OwnerBitmap.Height);
  For Y := 0 To OwnerBitmap.MaxHeight Do
  Begin
    For X := 0 To OwnerBitmap.MaxWidth Do
    Begin
      Sum := 0;
      For J := 0 To KS Do
      Begin
        pY := Clamp(Y + J - KSDiv2, 0, OwnerBitmap.MaxHeight);
        moffset := J * Size;
        For I := 0 To KS Do
        Begin
          pX := Clamp(X + I - KSDiv2, 0, OwnerBitmap.MaxWidth);
          KernelValue := aMatrix[moffset + I]; // Valeur dans la matrice
          Value := OwnerBitmap.GetPixel(pX, pY).Red * _FloatColorRatio;
          Value := (Value * KernelValue);
          Sum := Sum + Value;
        end;
      end;
      Result.Add(Sum);
    end;
  end;
end;    
 
procedure TBZBitmapSegmentationFilters.GradientConvolution(aMode : TBZDetectEdgeFilterMode);
Var
  x, y : Integer;
  GradX, GradY : TBZSingle2DMap;
  gX, gY : Single;
  c  : Integer;
begin
  GradX := Self.ComputeConvolutionGradientX(aMode);
  GradY := Self.ComputeConvolutionGradientX(aMode);
  For y := 0 to OwnerBitmap.MaxHeight do
  begin
    for x := 0 to OwnerBitmap.MaxWidth do
    begin
      gX := GradX.Items[x,y];
      gY := GradY.Items[x,y];
      c := Round(Clamp(System.Sqrt(gX * gX + gY * gY),0,1.0) * 255);
      OwnerBitmap.setPixel(x,y, BZColor(c,c,c));
    end;
  end;
end;

le H.O.G ? quelque chose que je connait pas, ca sert à quoi ?

Merci

Bon dimanche

[wiwaxia]

Bonjour,

Un produit de convolution résulte de la sommation du "produit" de deux "fonctions" dont les arguments sont décalés d'une quantité variable.

Le traitement d'image recourt au produit de deux matrices, celle du corps de l'image par une autre appelée "filtre", dont les termes sont généralement nuls, à l'exception d'un petit nombre voisins de la région centrale.
De plus le produit matriciel en cause est celui de Hadamard (ou de Schur), pour lequel tout élément (c_ij) de la matrice obtenue (C) est le produit des éléments correspondants des matrices (A, B) qui interviennent:

C = A×B impliquant [c_ij] = [a_ij*b_ij]

Le vecteur gradient

Grad(I_{(x, y)}) = G_x.u_x + G_y.u_y

intervient dans les variations élémentaires de l'"intensité" locale de l'image, de sorte que ses composantes correspondent aux dérivées partielles premières de la fonxtion I(x, y) considérée; on a par définition:

dI = Grad(I)|dOM = G_x*dx + G_y*dy <==> G_x = (∂I/∂x) et G_y = (∂I/∂y) ;

La discrétisation de l'espace en pixels conduit à employer des coordonnées entières, et des relations linéaires apparentées aux précédentes, de la forme:

G_{x(x, y)} = (I_{(x + h, y)} - _{I(x - h, y)})/(2*h) , G_{y(x, y)} = (I_{(x, y + h)} - _{I(x, y - h)})/(2*h) , avec par ex. h = 1 .

On trouve des explications très claires par les liens ci-dessous, que tu connais peut-être déjà:
https://fr.wikipedia.org/wiki/Filtre_de_Sobel
http://www.tsi.enst.fr/pages/enseign...ur3/index.html
http://www.tsi.enst.fr/pages/enseign...r/pres_PS.html

Le seul point flou concerne à ce que j'ai cru comprendre la définition de l'intensité locale I(x, y),
implicitement assimilée au niveau de gris g = r + v + b ,
et qui va de soi dans le cas d'une image monochrome;
on pourrait cependant envisager l'intervention d'une luminance sommairenent définie par la combinaison linéaire

L = K_r*r + K_v*v + K_b*b ,

ou trois vecteurs gradients parallèlement définis (G_r, G_v,G_b) pour chacune des couleurs fondamentales.

[wiwaxia]

... / ... Cette notion de Gradient est aussi utilisée dans le cas de détection des contours, le truc c'est qu'il fallait que j'applique mes matrices horizontalement et verticalement sans diviser mes valeurs puis calculer la norme entre ces 2 valeurs. Si j'ai bien tout compris. Dans tous les cas mon détecteur de Canny fonctionne ...

À la limite du contour d'un objet, on observe une variation très rapide de la teinte locale, et par conséquent une valeur énorme pour la norme de son gradient.
Les deux filtres proposés te donnent manifestement les valeurs des composantes (Gx, Gy), à un facteur multiplicatif près: il suffit pour cela de détailler les combinaisons linéaires correspondantes.

PS_1: Trouvée par hasard, une mise au point clairement présentée, et dont les données sont immédiatement incorporables à tes programmes:

https://web.fe.up.pt/~campilho/PDI/N...eDetection.pdf

PS_2: ... et en relisant la fin de ton premier message:

... la norme c'est Sqrt(Gx² + Gy²)
et pour la direction c'est Tan^-1(gx/gy) = arctan2(gx,gy) ...

ne s'agirait-il pas plutôt de Tan^-1(gy/gx) = arctan2(gx,gy) ? À vérifier.

[BeanzMaster]

Bonjour Wiwaxia

Bonjour,

Un produit de convolution résulte de la sommation du "produit" de deux "fonctions" dont les arguments sont décalés d'une quantité variable.

Le vecteur gradient

Grad(I_{(x, y)}) = G_x.u_x + G_y.u_y

intervient dans les variations élémentaires de l'"intensité" locale de l'image, de sorte que ses composantes correspondent aux dérivées partielles premières de la fonxtion I(x, y) considérée; on a par définition:

dI = Grad(I)|dOM = G_x*dx + G_y*dy <==> G_x = (∂I/∂x) et G_y = (∂I/∂y) ;

La discrétisation de l'espace en pixels conduit à employer des coordonnées entières, et des relations linéaires apparentées aux précédentes, de la forme:

G_{x(x, y)} = (I_{(x + h, y)} - _{I(x - h, y)})/(2*h) , G_{y(x, y)} = (I_{(x, y + h)} - _{I(x, y - h)})/(2*h) , avec par ex. h = 1 .

On trouve des explications très claires par les liens ci-dessous, que tu connais peut-être déjà:
https://fr.wikipedia.org/wiki/Filtre_de_Sobel
http://www.tsi.enst.fr/pages/enseign...ur3/index.html
http://www.tsi.enst.fr/pages/enseign...r/pres_PS.html

Merci pour ces explications complémentaires et les liens. En plus pour la page du Wiki sur le gradient, je ne sais pas comment j'ai pu passer à travers lors de mes recherches

Le seul point flou concerne à ce que j'ai cru comprendre la définition de l'intensité locale I(x, y),
implicitement assimilée au niveau de gris g = r + v + b ,
et qui va de soi dans le cas d'une image monochrome;
on pourrait cependant envisager l'intervention d'une luminance sommairenent définie par la combinaison linéaire

L = K_r*r + K_v*v + K_b*b ,

ou trois vecteurs gradients parallèlement définis (G_r, G_v,G_b) pour chacune des couleurs fondamentales.

Oui, en fait mon image est déja convertie en niveaux de gris d'ou l'utilisation de juste la composante Rouge.
Très bonne idées de pouvoir calculer les gradients de chaque canal. Je l'implémenterai

À la limite du contour d'un objet, on observe une variation très rapide de la teinte locale, et par conséquent une valeur énorme pour la norme de son gradient.
Les deux filtres proposés te donnent manifestement les valeurs des composantes (Gx, Gy), à un facteur multiplicatif près: il suffit pour cela de détailler les combinaisons linéaires correspondantes.

PS_1: Trouvée par hasard, une mise au point clairement présentée, et dont les données sont immédiatement incorporables à tes programmes:

https://web.fe.up.pt/~campilho/PDI/N...eDetection.pdf
.

Que veux tu dire par : à un facteur multiplicatif près ? je ne comprend pas cette nuance.
Un bon document, même si l'anglais me brouille un peu l'esprit.

PS_2: ... et en relisant la fin de ton premier message:

ne s'agirait-il pas plutôt de Tan^-1(gy/gx) = arctan2(gx,gy) ? À vérifier.

Oui tu as raison, j'ai oublié d'inverser les termes.

Merci à bientôt

[wiwaxia]

Les deux filtres proposés te donnent manifestement les valeurs des composantes (Gx, Gy), à un facteur multiplicatif près: il suffit pour cela de détailler les combinaisons linéaires correspondantes.

Que veux tu dire par : à un facteur multiplicatif près ? je ne comprend pas cette nuance ...

Étant donné une fonction de deux variables (U_{(x, y)}), le vecteur gradient qui lui est associé est par définition

Grad(U) = (dU/dx).u_x + (dU/dy).u_y ;

il admet pour composantes les dérivées partielles premières de la fonction par rapport à (x) et (y):

U'_x = (dU/dx) ; U'_y = (dU/dy)

- mon logiciel de caractères spéciaux est en panne).
Les filtres de Prewitt et Sobel font appel à la combinaison linéaire de 8 points proches d'un point central de coordonnées (x, y), et en lesquels la fonction (U) pred les valeurs approchées (au second ordre près en h):

U(x + h, y) = U(x, y) + h*U'_x ; U(x, y + h) = U(x, y) + h*U'_y ;
U(x - h, y) = U(x, y) - h*U'_x ; U(x, y - h) = U(x, y) - h*U'_y ;
U(x + h, y + h) = U(x, y) + h*U'_x + h*U'_y ; U(x + h, y - h) = U(x, y) + h*U'_x - h*U'_y ;
U(x - h, y + h) = U(x, y) - h*U'_x + h*U'_y ; U(x - h, y - h) = U(x, y) - h*U'_x - h*U'_y ,

Le filtre (Gx) par exemple livre la combinaison linéaire:

Gx = c*(U(x + h) -U(x - h)) + U(x + h, y + h) + U(x + h, y - h) - (U(x - h, y + h) + U(x - h, y - h)) ,

ce qui donne

Gx = c*(0 + 2*h*U'_x) + 2*(U(x, y) + h*U'_x) - 2*(U(x, y) - h*U'_x) ,

soit finalement:

Gx = (2*c + 4)*h*U'_x) .

On obtient pareillement Gy = (2*c + 4)*U'_y) , de sorte que le vecteur G apparaît colinéaire au gradient:

G = (2*c + 4).Grad'U_{(x, y)}) .

L'intervention d'un facteur multiplicatif n'est pas gênant, le maximum local de la norme permettant de repérer le bord de l'image.
(h) représente le pas de la grille et est égal à l'unité.

... l'anglais me brouille un peu l'esprit.

Dans ce cas, garder en permanence à portée de clic l'un des liens suivants:
https://www.reverso.net/text_translation.aspx?lang=FR
https://www.linguee.fr/
et si tu veux te servir de la Grosse Bertha pour contrer l'omniprésence de l'anglais dans tous les domaines de la science et de la technique, connecte-toi au Dictionnaire terminologique de l’Office québécois de la langue française.

Note: un développement des termes au second ordre selon la formule de Taylor/Mac Laurin conduit à des résultats identiques; par exemple

Gx = (2*c + 4)*U'_x ;

l'erreur par approximation est donc beaucoup plus faible, puisqu'elle n'apparaît qu'au niveau du 3^me ordre (en h³).