Détection de contours, "gradient"/convolution

Version imprimable

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:

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:

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

30/04/2020, 08h10
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,

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 :D.

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
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

03/05/2020, 08h56
wiwaxia

1 pièce(s) jointe(s)

Détection de contours, "gradient"/convolution

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.

Pièce jointe 562403

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.
03/05/2020, 09h11
wiwaxia

Détection de contours, "gradient"/convolution

Citation:

Envoyé par BeanzMaster

... / ... 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 :D ...

À 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:

Citation:

Envoyé par BeanzMaster

... 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.
05/05/2020, 13h45
BeanzMaster

Bonjour Wiwaxia

Citation:

Envoyé par 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 :plusser:

Citation:

Envoyé par wiwaxia

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 :ccool:

Citation:

Envoyé par wiwaxia

À 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.

Citation:

Envoyé par wiwaxia

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
11/05/2020, 10h48
wiwaxia

1 pièce(s) jointe(s)

Détection de contours, "gradient"/convolution

Citation:

Envoyé par BeanzMaster

Citation:

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 ,

Pièce jointe 564565

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é.

Citation:

Envoyé par BeanzMaster

... 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³).