Discussion :

[pseudocode]

Afin de déterminer l'énergie externe du snake il faut calculer la matrice FLOW qui est la la carte de distance normalisée du gradient binarisé de l'image originale....ouf

1. Pour rectifier la vérité, le GVF n'a pas de rapport avec la carte des distances. C'est juste une approximation que j'ai choisi car c'est plus rapide à calculer.

2. il NE faut PAS normaliser la carte des distances. Dans mes posts, je l'ai normalisée uniquement pour la représenter sous forme d'une image en niveaux de gris. Dans le code, la matrice prends des valeurs entre 0 (pixel sur le pic de gradient) jusqu'à l'infini (enfin, jusqu'aux limites de l'image)

3. Je ne vois pas tes images car le serveur de ImagUp à l'air malade. Pour ce qui concerne mon image en niveau de gris, j'ai utilisé la formule "niveau_de_gris=Math.max(0,255-flow)". Mais c'est juste pour l'affichage de l'image. Dans le code on utilise les valeurs "brutes" de la carte des distances.

[b_reda31]

2. il NE faut PAS normaliser la carte des distances. Dans mes posts, je l'ai normalisée uniquement pour la représenter sous forme d'une image en niveaux de gris. Dans le code, la matrice prends des valeurs entre 0 (pixel sur le pic de gradient) jusqu'à l'infini (enfin, jusqu'aux limites de l'image)

Quand je disais "normaliser",c'etait par rapport au masque de Chamfer:

Si X est un point contours (Vaut 0)alors

Son voisinage avant normalisation:

4---3---4
3---X---3
4---4---3

Et apres normalisation :

4/3---1---4/3
1-----X---1
4/3---1---4/3

1. Pour rectifier la vérité, le GVF n'a pas de rapport avec la carte des distances. C'est juste une approximation que j'ai choisi car c'est plus rapide à calculer.

J'ai un petit problème concernant les notations:

GVF=GRADIENT+FLOW?
FLOW=Carte de distance?

Pour ce qui concerne mon image en niveau de gris, j'ai utilisé la formule "niveau_de_gris=Math.max(0,255-flow)". Mais c'est juste pour l'affichage de l'image. Dans le code on utilise les valeurs "brutes" de la carte des distances.

C'est exactement la question que je me suis posé.Merciiii à vous c'est beaucoup plus clair maintenant!

[pseudocode]

Quand je disais "normaliser",c'etait par rapport au masque de Chamfer

Ok. Donc là, oui, il faut normaliser. Cela fait partie integrante du calcul de Chamfer.

J'ai un petit problème concernant les notations:
GVF=GRADIENT+FLOW?
FLOW=Carte de distance?

FLOW = GVF = Gradient Vector Flow.

Dans mon approximation, c'est le vecteur gradient de la carte des distances (donc le gradient de la carte des distances du gradient ).

Dans la formule dans la methode f_gflow(), on cherche dans quelle direction ce vecteur "descend" le plus, et donc nous ammène vers le minimum local le plus proche dans la carte des distances.

C'est une approximation car, avec l'utilisation des masques de Chamfer, seule la "direction" est correcte. La "norme" est constante (=1) qu'on soit loin du minimum local.

[b_reda31]

FLOW = GVF = Gradient Vector Flow.

Dans mon approximation, c'est le vecteur gradient de la carte des distances (donc le gradient de la carte des distances du gradient ).

Alors si je comprend bien vous avez "approximé" le GVF en utilisant la carte de distance?
J'ai pu faire cette approximation pour l'énergie externe et ça marche très bien.Néanmoins cette approximation nécessite de binariser l'image avec un seuil que choisira l'utilisateur?!! c'est plutôt gènant ça
Connaissez vous une approximation du GVF qui ne m'oblige pas à binariser l'image (car le problème se situe au niveau du choix du Seuil de binarisation)

[pseudocode]

Connaissez vous une approximation du GVF qui ne m'oblige pas à binariser l'image (car le problème se situe au niveau du choix du Seuil de binarisation)

Le mieux c'est de calculer le vrai GVF. Cela dit, meme avec le vrai GFV, il y aura toujours le problème du choix de coefficients du snake.

[b_reda31]

Le mieux c'est de calculer le vrai GVF.

J'ai cherché sur google avec le mot clé GVF,hélas j'ai trouvé que des définitions très "analytiques dont je ne comprend le principe de calcu....
Auriez vous un lien qui pourra m'aider à implementer le vrai GVF comme vous dites,sinon juste le principe car la je suis un peu perdu.

Cela dit, meme avec le vrai GFV, il y aura toujours le problème du choix de coefficients du snake.

Oui certe,je voudrai juste pouvoir faire la comparaison entre les deux méthodes.

[pseudocode]

Auriez vous un lien qui pourra m'aider à implementer le vrai GVF comme vous dites,sinon juste le principe car la je suis un peu perdu.

c'est pourtant le 1er lien de google: http://iacl.ece.jhu.edu/pubs/p087c.pdf

1. Pour chaque pixel (x,y) on initialise u(x,y)=0 et v(x,y)=0
2. Pour chaque pixel (x,y) on recalcule u(x,y) et v(x,y) avec les formules (12a) et (12b) du document
3. retour a l'etape 2, jusqu'a convergence.

Sinon il y a des implémentations dans codesearch

[b_reda31]

c'est pourtant le 1er lien de google: http://iacl.ece.jhu.edu/pubs/p087c.pdf

Quand je parlais des articles très "analytiques" dont je n'ai compris le principe,celui que vous m'avez donné en fait justement partie

En tout cas je viens de l'imprimer, et je vais le relire à tête reposé.Peut être que demain je poserai une question plus utile concernant le GFV,car pour le moment je n y vois que du noir!
Merci

[b_reda31]

1. Pour chaque pixel (x,y) on initialise u(x,y)=0 et v(x,y)=0

Pourtant dans la source que vous m'avez donné u et v sont initialisés au GradientX,GradientY respectivement de la "edge map" (carte de contour)

2. Pour chaque pixel (x,y) on recalcule u(x,y) et v(x,y) avec les formules (12a) et (12b) du document

Voici les formules (12a) et (12b) j'ai retiré l'indiçage)

u=Mu*delta2(u)-(u-fx).(fx²+fy²)...(12a)
v=Mu*delta2(v)-(v-fy).(fx²+fy²)...(12b)

tel que :
f est la carte des contour (Edge map)
fx gradientX de f ,fy gradientY de f.

Pour ce qui est de Delta2 (Operateur Laplacien),je ne connais pas cet opérateur.Est ce le gradient du gradient?

La base du calcul du GVF repose sur le calcul de la Edge Map f ,Or c'est la première fois que j'entends ce terme ,Est ce tout simplement le gradient de l'image?

[benDelphic]

pour le laplacien
http://xphilipp.developpez.com/artic.../?page=page_12
http://www.developpez.net/forums/sho...d.php?t=513674
( c'est un Kernel de convolution pour un Edge detection)

[pseudocode]

Pourtant dans la source que vous m'avez donné u et v sont initialisés au GradientX,GradientY respectivement de la "edge map" (carte de contour)

oui... mais ca revient plus ou moins au même à une itération près.

Iteration 0:
u=0
v=0

Iteration 1:
u=Mu*delta2(0)-(0-fx).(fx²+fy²) = fx.(fx²+fy²) ~ d( gradient² ) / dx
v=Mu*delta2(0)-(0-fy).(fx²+fy²) = fy.(fx²+fy²) ~ d( gradient² ) / dy

La base du calcul du GVF repose sur le calcul de la Edge Map f ,Or c'est la première fois que j'entends ce terme ,Est ce tout simplement le gradient de l'image?

Oui. c'est la valeur absoloue (ou la norme) du gradient.

[pseudocode]

J'ai mis au propre une de mes implémentations Java, si ca peut aider...

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
 
/**
 * @param f : image normalized in [0,1] 
 * @param w : width of image
 * @param h : height of image
 * @param ITER : number of iterations
 * @param mu : iteration step
 * @return u[x,y] and v[x,y] arrays
 */
public static double[][][] gvf(double[][] f, int w, int h, int ITER, double mu) {
 
	// create empty arrays
	double[][] u = new double[w][h];
	double[][] v = new double[w][h];
	double[][] fx = new double[w][h];
	double[][] fy = new double[w][h];
	double[][] Lu = new double[w][h];
	double[][] Lv = new double[w][h];
 
	// precompute edge-map (gradient)
	for (int y=1;y<(h-1);y++) {
		for (int x=1;x<(w-1);x++) {
			fx[x][y] = (f[x+1][y]-f[x-1][y])/2;
			fy[x][y] = (f[x][y+1]-f[x][y-1])/2;
		}
	}
 
	// iterative diffusion
	for(int loop=0;loop<ITER;loop++) {
 
		// compute laplacian of U and V
		for (int y=1;y<(h-1);y++) {
			for (int x=1;x<(w-1);x++) {
				Lu[x][y] = -u[x][y] + 0.25*(u[x-1][y]+u[x+1][y]+u[x][y-1]+u[x][y+1]); 
				Lv[x][y] = -v[x][y] + 0.25*(v[x-1][y]+v[x+1][y]+v[x][y-1]+v[x][y+1]);
			}
		}
 
		// update U and V
		for (int y=0;y<h;y++) {
			for (int x=0;x<w;x++) {
				double gnorm2 = fx[x][y]*fx[x][y] + fy[x][y]*fy[x][y];
 
				u[x][y] += mu*4*Lu[x][y] - (u[x][y]-fx[x][y])*gnorm2;
				v[x][y] += mu*4*Lv[x][y] - (v[x][y]-fy[x][y])*gnorm2;
			}
		}
	}
 
	// return U and V arrays
	return new double[][][]{u,v};
}

[b_reda31]

J'ai mis au propre une de mes implémentations Java, si ca peut aider...

Si ça peut aider?!! Vous rigolez ou quoi,Vous me rendez un énorme service ....Merciii

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
 
/**
 * @param f : image normalized in [0,1] 
 * @param w : width of image
 * @param h : height of image
 * @param ITER : number of iterations
 * @param mu : iteration step
 * @return u[x,y] and v[x,y] arrays
 */
public static double[][][] gvf(double[][] f, int w, int h, int ITER, double mu) {
 
	// create empty arrays
	double[][] u = new double[w][h];
	double[][] v = new double[w][h];
	double[][] fx = new double[w][h];
	double[][] fy = new double[w][h];
	double[][] Lu = new double[w][h];
	double[][] Lv = new double[w][h];
 
	// precompute edge-map (gradient)
	for (int y=1;y<(h-1);y++) {
		for (int x=1;x<(w-1);x++) {
			fx[x][y] = f[x+1][y]-f[x-1][y];
			fy[x][y] = f[x][y+1]-f[x][y-1];
		}
	}
 
	// iterative diffusion
	for(int loop=0;loop<ITER;loop++) {
 
		// compute laplacian of U and V
		for (int y=1;y<(h-1);y++) {
			for (int x=1;x<(w-1);x++) {
				Lu[x][y] = -u[x][y] + 0.25*(u[x-1][y]+u[x+1][y]+u[x][y-1]+u[x][y+1]); 
				Lv[x][y] = -v[x][y] + 0.25*(v[x-1][y]+v[x+1][y]+v[x][y-1]+v[x][y+1]);
			}
		}
 
		// update U and V
		for (int y=0;y<h;y++) {
			for (int x=0;x<w;x++) {
				double gnorm2 = fx[x][y]*fx[x][y] + fy[x][y]*fy[x][y];
 
				u[x][y] += mu*4*Lu[x][y] - (u[x][y]-fx[x][y])*gnorm2;
				v[x][y] += mu*4*Lv[x][y] - (v[x][y]-fy[x][y])*gnorm2;
			}
		}
	}
 
	// return U and V arrays
	return new double[][][]{u,v};
}

Les résultats de cette fonction sont deux matrices u et v de mêmes dimensions que l'image originale.
Visuellement que représentent ces matrices?et comment pourrais je créer une énergie externe à minimiser à partir de u et v?

J'ai affiché la matrice u calculée a partir de cette image :






et voici la matrice u qui est obtenue mu=1 , nbiteration=20)



Est normal que je n'obtienne que du "bruits"?!










PS:J'ai testé le filtre de Laplace pour la même image,et voici ce que j'obtient :

C'est bon vous pensez?

[pseudocode]

Les résultats de cette fonction sont deux matrices u et v de mêmes dimensions que l'image originale.
Visuellement que représentent ces matrices?

U et V représentent les composantes sur X et sur Y du vecteur de flux.

=> Pour un pixel de coordonée (x,y) le vecteur de flux est Flux(x,y) = ( U[x][y] , V[x][y] )

et comment pourrais je créer une énergie externe à minimiser à partir de u et v?

Tu peux favoriser le déplacement vers les fortes intensités de flux (i.e. là où la norme du vecteur de flux est la plus grande).

Tu peux également favoriser les déplacement qui remontent le flux (i.e là où le produit scalaire déplacement*flux est le plus négatif).

Bref plein de choix possibles.

[b_reda31]

Tu peux favoriser le déplacement vers les fortes intensités de flux (i.e. là où la norme du vecteur de flux est la plus grande).

J'ai essayé de faire ça,en mettant ( après le calcul du u et v ) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
//Calcul de la norme du vecteur de flux
for (int j=0;j<h;j++) {
			for (int i=0;i<w;i++) {
                                 u[i][j]=u[i][j]*u[i][j];
                                 v[i][j]=v[i][j]*v[i][j];
                                 intensite_flux[i][j]=u[i][j]+v[i][j] ;
 
 
                          }
}

J'ai testé avec une image 7*7 qui contient un point noir au centre sur un fond blanc :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
255     255     255     255     255     255     255
 
255     255     255     255     255     255     255
 
255     255     255     255     255     255     255
 
255     255     255       0     255     255     255
 
255     255     255     255     255     255     255
 
255     255     255     255     255     255     255
 
255     255     255     255     255     255     255

Pour cette image,plus je me rapproche du centre plus l'intensité du flux doit être grande,n'est ce pas?



Or,
Après avoir normalisé cette image sur [0,1],voici l'intensité du flux que j'obtient :

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
 
Matrice "Intensité du flux" :
 
0.00       0.00       0.00       0.00       0.00       0.00       0.00
 
0.00       2.28       6.17       1.84       6.17       2.28       0.00                          
 
0.00       6.17       1.54       5.42       1.54       6.17       0.00
 
0.00       1.84       5.42       0.00       5.42       1.84       0.00 
 
0.00       6.17       1.54       5.42       1.54       6.17       0.00 
 
0.00       2.28       6.17       1.84       6.17       2.28       0.00
 
0.00       0.00       0.00       0.00       0.00       0.00       0.00

à la rigueur les zéros qui enveloppent cette matrice je comprends ( car le traitement commence à partir de l'indice [1][1] dans l'image).Mais les valeurs à l'intérieur de cette matrice n'ont aucun sens,non ?

[pseudocode]

hum... je n'obtiens pas les mêmes valeurs

- image de test 7x7 normalisée : 1.0 partout sauf au centre 0.0
- ITER = 25, mu=0.1
- resultat : r[x][y] = Math.sqrt(u[x][y]*u[x][y] + v[x][y]*v[x][y])

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
0,00  0,00  0,00  0,00  0,00  0,00  0,00  
 
0,00  0,03  0,07  0,09  0,07  0,03  0,00  
 
0,00  0,07  0,18  0,24  0,18  0,07  0,00  
 
0,00  0,09  0,24  0,00  0,24  0,09  0,00  
 
0,00  0,07  0,18  0,24  0,18  0,07  0,00  
 
0,00  0,03  0,07  0,09  0,07  0,03  0,00  
 
0,00  0,00  0,00  0,00  0,00  0,00  0,00

L'interprétation c'est que le flux est concentrique. Plus on s'éloigne du centre, plus la valeur diminue. Au centre, la valeur est nulle car on est au centre du cyclone => les forces partent dans toutes les directions et donc se compensent mutuellement.

[pseudocode]

Le "vrai" GVF calculé sur l'image d'exemple "trefle":

[b_reda31]

Il doit avoir quelque chose qui cloche dans mon code...
Merci pour tous ces renseignement !

Le GVF a été introduit pour pouvoir faire une diffusion de l'information des contours sur l'ensemble de l'image afin de pouvoir rapprocher le snake du contour et cela même s'il n'est pas situé (initialement) prés de l'objet d'intérêt(n'est ce pas ?)Mais aussi parce qu'en utilisant le gradient comme énergie externe il a été constaté que le snake ne convergeait pas vers les zones à forte concavité.

Est ce que l'approximation du GVF par la carte de distance permettra de rapprocher le Snake vers les zones à forte concavité?

En jouant sur les paramètres pour faire des essais,j'ai constaté que le snake convergeait difficilement vers les zones à forte concavité.Mais je pense que c'est le mécanisme d'auto-adaptation qui à permis au snake d'entrer vers zones concaves.non?

[pseudocode]

Est ce que l'approximation du GVF par la carte de distance permettra de rapprocher le Snake vers les zones à forte concavité?

Oui. La seule limitation de l'approximation c'est qu'elle ne fait pas la difference entre un fort/faible pic de gradient (du fait de la binarisation du gradient, on perd cette information).

En jouant sur les paramètres pour faire des essais,j'ai constaté que le snake convergeait difficilement vers les zones à forte concavité.Mais je pense que c'est le mécanisme d'auto-adaptation qui à permis au snake d'entrer vers zones concaves.non?

Le mécanisme d'auto-adaptation y est en effet pour beaucoup. Sinon, on doit pouvoir y arriver en mettant un fort coef sur l'energie de continuitén et un faible coef sur l'energie de courbure. Mais ca necessite un tuning plus précis que le mécanisme d'auto-adaptation.

[b_reda31]

Bonjour,
Il y a une question qui me trotte la tête dont je n'arrive à trouver la réponse.

Pour résumer, on a l'énergie interne qui gère la cohésion du contour et on a l'énergie externe qui tente de rapprocher ce contour vers l'objet d'intérêt dans l'image.
L'énergie interne peut être décomposée en deux énergies :l'énergie de courbure et l'énergie de continuité:

Energie interne = Alpha *||v'(s)||² + Beta *||v''(s)||²
Tel que V(s) représente les coordonnées du point s dans le Snake.

D'un point de vu analytique :
L'énergie de continuité dépend de la dérivée des coordonnées des points du Snake.Minimiser cette énergie revient à minimiser la Variation des coordonnées entre elles, soit donc rapprocher les points.

Mais pour l'énergie de courbure,j'admet être un peu perdu cette énergie va tenter pour chaque point du Snake de maximiser l'angle formé entre ce point ,son successeur et son prédécesseur...Je ne comprend pas pourquoi utiliser la seconde dérivée pour ça!

La seconde dérivée a t elle un rapport avec la variation de la tangente ou quelque chose du genre?j'avoue avoir oublié quelques notions fondamentales en analyse.