[image] Snake (contour actif)

[pseudocode]

Envoyé par b_reda31

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 :

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]

Envoyé par pseudocode

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

Envoyé par pseudocode

Code java :

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]

Envoyé par b_reda31

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]

Envoyé par pseudocode

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 :

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 :

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 :

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 :

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]

Envoyé par b_reda31

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.

[chevalieroj]

Est-ce que quelqu'un pourrait nous montrer un exemple de methode snake sous Matlab? J'en ai fort besoins pour mon projet

[b_reda31]

Bonjour,
Voici un lien qui pourrait vous aider

[chevalieroj]

Merci bcp,b_reda

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

[pseudocode]

Envoyé par b_reda31

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.

oui c'est ca.

v'(s) représente la variation des points de la courbe (abcisse curviligne) => un vecteur tangeant au déplacement s.

La courbure représente géometriquement la variation de ce vecteur tangeant v'(s) par rapport au déplacement s, donc c'est d(v'(s))/ds = v"(s)

[b_reda31]

Envoyé par pseudocode

v'(s) représente la variation des points de la courbe (abcisse curviligne) => un vecteur tangeant au déplacement s.

La courbure représente géometriquement la variation de ce vecteur tangeant v'(s) par rapport au déplacement s, donc c'est d(v'(s))/ds = v"(s)

Merci pour ces précisions!

[b_reda31]

Bonjour,
En essayant de faire un résumé de cette méthode (Snake), je suis tombé sur un gros problème concernant toujours l’énergie de courbure.

Dans le schéma suivant j’illustre les déplacements possibles du point P4 de coordonnées (5,1), en considérant seulement l’énergie de Courbure. L’origine est en bas à gauche.







En appliquant les différences finies pour la seconde dérivée ( au carré), l’énergie de courbure s’exprimera par :

( Xi-1 - 2*Xi + Xi+1 )² + ( Yi-1 - 2* Yi +Yi+1 | )²



J’ai calculé ces énergies pour tous les voisins de P4 (Ce dernier y compris) avec une fenêtre 3X3, afin de déterminer quel serait le déplacement optimal qui minimiserait l’énergie. Les résultats des calculs sont dans la sous-matrice (Zoom sur P4)

Hélas je ne comprends vraiment ces résultats :
Pour les 3 voisins au-dessus de P4, ne devons nous pas obtenir la même valeur d’énergie ?!! car chacun des 3 voisin formera une ligne droite (180°) avec le successeur et prédécesseur (P3 et P5) .
Par ailleurs je ne comprends pas aussi pourquoi la valeur d’énergie du voisin au-dessous de P4, cette valeur devrai être supérieure à l’énergie de P4 car l’angle va s’accentuer


La formule de différence finie que j’ai cité est elle correcte ?En ajoutant des valeurs absolues aux différence des x et de cette manière
(| Xi-1 - Xi | + |Xi+1 – Xi | )² + (| Yi-1 - Yi | + |Yi+1 – Yi | )²
Cela permettrait de rendre les résultats plus cohérents, mais je ne peux citer cette formule dans mon résumé à moins qu’elle existe.

[pseudocode]

Envoyé par b_reda31

Hélas je ne comprends vraiment ces résultats :
Pour les 3 voisins au-dessus de P4, ne devons nous pas obtenir la même valeur d’énergie ?!! car chacun des 3 voisin formera une ligne droite (180°) avec le successeur et prédécesseur (P3 et P5) .

Le calcul de la dérivée seconde prend en compte la variation en position (angle entre les vecteurs) mais aussi la variation en grandeur (norme des vecteurs). La norme de la dérivée seconde dépend donc de ces 2 facteurs.

C'est donc normal que le point au dessus de P4 soit le meilleur car a la fois:
- il diminue l'angle entre les vecteurs
- il maintient le ratio (grandeur a gauche)/(grandeur a droite)

Par ailleurs je ne comprends pas aussi pourquoi la valeur d’énergie du voisin au-dessous de P4, cette valeur devrai être supérieure à l’énergie de P4 car l’angle va s’accentuer

Oui elle devrait.

Ce point a pour energie 16 et pas 4:

E.x = (0 - 2*5 + 10)² = 0
E.y = (2 - 2*0 + 2)² = 16

[b_reda31]

Envoyé par pseudocode

Le calcul de la dérivée seconde prend en compte la variation en position (angle entre les vecteurs) mais aussi la variation en grandeur (norme des vecteurs). La norme de la dérivée seconde dépend donc de ces 2 facteurs.

C'est donc normal que le point au dessus de P4 soit le meilleur car a la fois:
- il diminue l'angle entre les vecteurs
- il maintient le ratio (grandeur a gauche)/(grandeur a droite)

Encore merci à vous PseudoCode !

Ce point a pour energie 16 et pas 4:

E.x = (0 - 2*5 + 10)² = 0
E.y = (2 - 2*0 + 2)² = 16

Je me suis bien gourré en calculant les énergies de la dernière ligne,Maintenant les résultats concordent très bien avec les explications que vous m'avez donnée

[b_reda31]

Bonjour,J'ai une petite question concernant la normalisation des énergies

Envoyé par pseudocode

Code :

Cette normalisation sert à rendre toutes les valeur des trois énergies dans l'intervalle [ 0 , 1 ],et cela afin de ne pas favoriser une énergie par rapport à une autre.Est ce bien cela?
Si oui,est ce que ça reviendrait au même de diviser chaque sous-matrice d'énergie par sa plus grande valeur? Bien entendu les valeur ne seront pas les mêmes mais les "proportions" entre énergies seront conservées.

[pseudocode]

Envoyé par b_reda31

Cette normalisation sert à rendre toutes les valeur des trois énergies dans l'intervalle [ 0 , 1 ],et cela afin de ne pas favoriser une énergie par rapport à une autre.Est ce bien cela?

oui, c'est cela.

Si oui,est ce que ça reviendrait au même de diviser chaque sous-matrice d'énergie par sa plus grande valeur?

Heu... en théorie oui, on peut utiliser n'importe quelle mesure.

Dans ton cas, ca voudrait dire utiliser la distance Linfinie = max(abs(x)). Je n'ai jamais testé.

Dans mon code j'utilise la distance L1 = sum(abs(x))