Discussion :

[pseudocode]

Bonjour,

Parmis toutes les objets mathématiques qu'il est souvent necessaire de calculer sur les pixels d'une image, il y en a deux qui reviennent assez souvent:

- Le vecteur Gradient, c'est a dire les derivées partielles du 1er ordre de l'intensité:

Code :

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

1
2
3
4
 
           dI(x,y)    dI(x,y)
G(x,y) = ( ------- , -------- )
             dx         dy

- La matrice Hessienne, c'est a dire les derivées partielles du 2nd ordre de l'intensité:

Code :

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

1
2
3
4
5
6
7
8
 
         | d²I(x,y)    d²I(x,y) |
         | --------    -------- |
         |    dx²        dxdy   |
H(x,y) = |                      |
         | d²I(x,y)    d²I(x,y) |
         | --------    -------- |
         |   dxdy         dy²   |

Remarque: la trace de cette matrice est appelé "Laplacien"


De part la nature discrete d'une image numérisée, les derivées sont approximées par des différences d'intensité au voisinage du pixel. Ces calculs vont dont etre tres sensibles au bruit. Pour limiter les effets du bruit, il est d'usage de lisser préalablement l'image (en la convoluant par une Gaussienne) avant de calculer les derivées.

Et c'est la que la magie de la convolution intervient car:

Code :

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

1
2
3
4
 
      d                        dF(t) 
     ---- [ F(t) * I(t) ] =  [ ----- ] * I(t)
      dt                        dt

Donc on peut inverser le calcul: d'abord calculer les derivées de la Gaussienne, puis convoluer ce résultat avec l'image. Cela nous donne deux avantages:

- Réduire les calculs de derivées partielles de l'intensité à des convolutions.
- Précalculer les noyaux de convolution, car ils sont indépendants de l'image.


Calculons les dérivées partielles de la Gaussienne:

Code :

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

1
2
 
G(x,y) = Exp( - (x²+y²) / 2*sigma² )

Derivées partielles du 1er ordre

Code :

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

1
2
3
4
5
6
7
8
 
dG(x,y)   
------- = - (x/sigma²) * Exp( - (x²+y²) / 2*sigma² )
  dx     
 
dG(x,y)   
------- = - (y/sigma²) * Exp( - (x²+y²) / 2*sigma² )
  dy

Derivées partielles du 2nd ordre

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
d²G(x,y)   
-------- = (x²-sigma²)/(sigma^4) * Exp( - (x²+y²) / 2*sigma² )
  dx²     
 
 
d²G(x,y)   
-------- = (y²-sigma²)/(sigma^4) * Exp( - (x²+y²) / 2*sigma² )
  dy²     
 
 
d²G(x,y)   
-------- = (x*y)/(sigma^4) * Exp( - (x²+y²) / 2*sigma² )
  dxdy

Quelques remarques sur les noyaux de convolutions obtenus:

1. Modifiez la valeur centrale du noyau afin que la somme des coefficients de la matrice soit égale a zero. Cela permet de s'assurer que la dérivée partielle sera nulle sur une zone d'intensité uniforme.

2. Choisissez une taille minimum de 3x3 pour le Gradient et 5x5 pour la Hessienne. En effet, plus la dérivée est d'un ordre élevé, plus il faut de points pour la calculer.

3. La valeur de sigma² permet de moduler la force du lissage (generalement une valeur entre 1 et 3 pour le Gradient, et entre 2 et 5 pour la Hessienne)


Exemple de code en Java:

Code Java :

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
 
public class HessianMatrix {
 
	int halfwindow = 3; // 7x7 kernel
	double sigma2 = 2.0;
 
	double[][] kernelGxx = new double[2*halfwindow+1][2*halfwindow+1];
	double[][] kernelGyy = new double[2*halfwindow+1][2*halfwindow+1];
	double[][] kernelGxy = new double[2*halfwindow+1][2*halfwindow+1];
 
	// Constructor
	public HessianMatrix() {
		for(int y=-halfwindow;y<=halfwindow;y++) {
			for(int x=-halfwindow;x<=halfwindow;x++) {
				kernelGxx[halfwindow+y][halfwindow+x] = Gxx(x, y);
				kernelGyy[halfwindow+y][halfwindow+x] = Gyy(x, y);
				kernelGxy[halfwindow+y][halfwindow+x] = Gxy(x, y);
			}
		}
	}
 
	// Kernel functions (gaussian 2nd order partial derivatives)
	private double Gxx(int x, int y) {
		double t = (x*x+y*y)/(2*sigma2);
		double d2t = (x*x-sigma2) / (sigma2*sigma2);
		double e = d2t * Math.exp( -t );
		return e;
	}
	private double Gyy(int x, int y) {
		double t = (x*x+y*y)/(2*sigma2);
		double d2t = (y*y-sigma2) / (sigma2*sigma2);
		double e = d2t * Math.exp( -t );
		return e;
	}
	private double Gxy(int x, int y) {
		double t = (x*x+y*y)/(2*sigma2);
		double d2t = (x*y) / (sigma2*sigma2);
		double e = d2t * Math.exp( -t );
		return e;
	}
 
	// return the 2x2 Hessian Matrix for pixel(x,y) 
	public double[][] getMatrix(Channel c, int x, int y) {
		double fxx=0, fyy=0, fxy=0;
		for(int dy=-halfwindow;dy<=halfwindow;dy++) {
			for(int dx=-halfwindow;dx<=halfwindow;dx++) {
				int xk = x + dx;
				int yk = y + dy;
				double vk = c.getValue(xk,yk); // <-- value of the pixel
				fxx += kernelGxx[halfwindow-dy][halfwindow-dx] * vk;
				fyy += kernelGyy[halfwindow-dy][halfwindow-dx] * vk;
				fxy += kernelGxy[halfwindow-dy][halfwindow-dx] * vk;
			}
		}
 
		double[][] hessianMatrix = new double[][] {
				new double[] { fxx, fxy },
				new double[] { fxy, fyy },
		};
 
		return hessianMatrix;
	}	
}

Code Java :

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
 
public class GradientVector {
 
	int halfwindow = 1; // 3x3 kernel
	double sigma2 = 1.4;
 
	double[][] kernelGx = new double[2*halfwindow+1][2*halfwindow+1];
	double[][] kernelGy = new double[2*halfwindow+1][2*halfwindow+1];
 
	// Constructor
	public GradientVector() {
		for(int y=-halfwindow;y<=halfwindow;y++) {
			for(int x=-halfwindow;x<=halfwindow;x++) {
				kernelGx[halfwindow+y][halfwindow+x] = Gx(x, y);
				kernelGy[halfwindow+y][halfwindow+x] = Gy(x, y);
			}
		}
	}
 
	// Kernel functions (gaussian 1st order partial derivatives)
	private double Gx(int x, int y) {
		double t = (x*x+y*y)/(2*sigma2);
		double d2t = -x / sigma2;
		double e = d2t * Math.exp( -t );
		return e;
	}
	private double Gy(int x, int y) {
		double t = (x*x+y*y)/(2*sigma2);
		double d2t = -y / sigma2;
		double e = d2t * Math.exp( -t );
		return e;
	}
 
	// return the Gradient Vector for pixel(x,y) 
	public double[] getVector(Channel c, int x, int y) {
		double gx=0, gy=0;
		for(int dy=-halfwindow;dy<=halfwindow;dy++) {
			for(int dx=-halfwindow;dx<=halfwindow;dx++) {
				int xk = x + dx;
				int yk = y + dy;
				double vk = c.getValue(xk,yk); // <-- value of the pixel
				gx += kernelGx[halfwindow-dy][halfwindow-dx] * vk;
				gy += kernelGy[halfwindow-dy][halfwindow-dx] * vk;
			}
		}
 
		double[] gradientVector = new double[] { gx, gy };
 
		return gradientVector;
	}	
}

[pseudocode]

A gauche: la norme du vecteur Gradient, Noyau 3x3, sigma²=1.4 (echelle Logarithmique)

A droite: la trace de la matrice Hessienne (Laplacien), Noyau 5x5, sigma²=2.0 (effet emboss)

[Methode]

Bonjour,

Par rapport à ces codes peux-tu m'expliquer d'où provient la classe channel ?
Par la même occasion, connais-tu les histogrammes pondérés et si ces codes pourraient s'y appliquer ?

Merci.

[pseudocode]

Par rapport à ces codes peux-tu m'expliquer d'où provient la classe channel ?

Ah. La classe Channel est une classe de ma librairie personnelle qui représente une image 8-bit, c'est à dire un tableau 2D d'entiers. Les accesseurs sont chargés de gérer les débordements (border-extender).

Une implémentation minimaliste possible est:

Code java :

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
 
public class Channel {
 
	private int width,height;
	private int[][] values = null;
 
	public Channel(int width,int height,int[][] array) {
		this.width = width;
		this.height = height;
		this.values = array;
	}
 
	public int getValue(int x,int y) {
		// gestion des débordements
		if (x<0) x=0;
		if (x>=this.width) x=this.width-1;
		if (y<0) y=0;
		if (y>=this.height) y=this.height-1;
 
		return this.values[x][y];
	}
 
	public void setValue(int x,int y,int v) {
		// gestion des débordements
		if (x<0) return;
		if (x>=width) return;
		if (y<0) return;
		if (y>=height) return;
 
		this.values[x][y]=v;
	}
 
	public int getWidth() {
		return this.width;
	}
 
	public int getHeight() {
		return this.height;
	}
 
	public int[][] asArray() {
		return this.values;
	}
}

[albert1983]

Bonjour,

Si j'ai bien compris.. dans un contexte d'une image :
G(x,y) represente la valeur du pixel au point (x,y).

Le gradient de chaque pixel nous donne: grad(G(x,y)) = (dG/dx,dG/dy)

Donc, pour chaque valeur de pixel j'aurais un couple de valeur!! Ce que je ne comprends pas, comment reproduire l'imagedu "gradient de l'image" avec ces nouveaux valeurs..

Merci d'avance

[pseudocode]

Donc, pour chaque valeur de pixel j'aurais un couple de valeur!! Ce que je ne comprends pas, comment reproduire l'image du "gradient de l'image" avec ces nouveaux valeurs..

Ce qu'on représente généralement ce n'est pas l'image du "gradient", mais l'image de la "norme du gradient".

Donc à partir d'un couple de valeur (a,b) on calcule la valeur n=racine(a²+b²). C'est cette valeur "n" qui est utilisée dans l'image.