Algorithme SIFT

Version imprimable

Voir 40 message(s) de cette discussion en une page

16/09/2010, 13h52
pseudocode

Citation:

Envoyé par tayeb1

bonjour, je veux seulement détecteur les point d 'intérêt d 'une image, je pense que je n 'ai donc pas besoin de calculer le gradient ?? je souhaite avoir une confirmation, svp.

Edit : j 'ai oublié de préciser que c'est avec l 'algorithm de SIFT.

Effectivement, le calcul du laplacien est suffisant.

(enfin dans SIFT c'est remplacé par la différence de Gaussiennes).
19/05/2011, 12h19
T_Lara

Papier de Lowe

De ma part j'ai trouvé deux implémentation de l'algo SIFT de Lowe et dans les deux cas pour construire la pyramide gaussienne ( sans prendre le cas special Py[0] et après interprétation du code)

Py[i] = gaussien ( P[i-1] , sqrt ( ( sigma0 K^i )^2 - ( sigma0 K^i-1 )^2 ) avec sigma0= 1,6 K et K= 2^(1/s)

ce qui donne apres quelques simplification:
Py[i] = gaussien ( P[i-1] , 1,6 *K^(i) * Sqrt(1 -1/K^2) ) ( pour i>=1 pour i=0 c'est tjrs diff.)

En relisant le papier de Lowe au long et travers j'ai pas trouvé d'ou viens ce Sqrt !!

qui peut m'expliquer ??
( gaussien est dans la premiere implementation avec matlab c'est "imsmooth" qui est utilisée et avec le C : "cvSmooth" )

De meme je trouve pas d'ou viens nombre d'ovctave = log2( MIN(hauteur_image_initial, largeur_image_initial ) - 2;
19/05/2011, 13h12
pseudocode
Citation:

Envoyé par T_Lara

De ma part j'ai trouvé deux implémentation de l'algo SIFT de Lowe et dans les deux cas pour construire la pyramide gaussienne ( sans prendre le cas special Py[0] et après interprétation du code)

Py[i] = gaussien ( P[i-1] , sqrt ( ( sigma0 K^i )^2 - ( sigma0 K^i-1 )^2 ) avec sigma0= 1,6 K et K= 2^(1/s)

ce qui donne apres quelques simplification:
Py[i] = gaussien ( P[i-1] , sqrt ( 1,6 *K^(i) * Sqrt(1 -1/K^2) ) ( pour i>=1 pour i=0 c'est tjrs diff.)

En relisant le papier de Lowe au long et travers j'ai pas trouvé d'ou viens ce Sqrt !!

J'ai déjà abordé ce point dans d'autres discussions. Dans son papier, Lowe raisonne avec les valeurs de "sigma", alors que la théorie des scale-space utilise des valeurs qui sont en fait des "sigma²".
- scale-space : G(t1)*G(t2) = G(t1+t2)
- Lowe: Gaussian(σ1)*Gaussian(σ2) = Gaussian(σ3) avec σ1²+σ2²=σ3²
Moralité, quand on veut monter d'un cran dans la pyramide, on cherche "w" tel que :

Gaussian( σ0 . K^i-1 ) * Gaussian( w ) = Gaussian( σ0 . K^i )

alors on a

(σ0 . K^i-1)² + w² = (σ0 . K^i)²

et donc

w = racine( (σ0 . K^i)² - (σ0 . K^i-1)² )
19/05/2011, 15h53
T_Lara

Conclusion ??:

Lowe s'est trompé dans son papier ? ou bien ca influence pas trop ?
Ie si je suis amener a implemente l'algo de Lowe je peux garder 1,6 K^i ??
19/05/2011, 16h33
pseudocode
Citation:

Envoyé par T_Lara

Conclusion ??:

Lowe s'est trompé dans son papier ? ou bien ca influence pas trop ?
Ie si je suis amener a implemente l'algo de Lowe je peux garder 1,6 K^i ??

Non, Lowe ne s'est pas trompé. J'expliquais juste qu'il utilise une notation différente de celle des scale-space, et c'est pour cela qu'on arrive a une formule du genre racine( (σ0 . K^i)² - (σ0 . K^i-1)² ).

Par contre, il y a effectivement une erreur dans la "simplification" (il y a une racine en trop)
```
w=racine( (σ0 . K^i)² - (σ0 . K^i-1)² )
 =racine( (σ0 . K^i)² - (σ0 . K^i/K)² )
 =racine( (σ0 . K^i)² . (1-1/K²) )
 =(σ0 . K^i).racine(1-1/K²) 
```
19/05/2011, 16h54
T_Lara

oui oui faute de frappe de ma part je l'avais rectifier avant meme que vous poster ;)

Merci alors faut peut être que je revois cette theorie de space scale plus en details si je veux mieux comprendre mais pour l'implementation je vois..sinon pour le nombre d'octave vous avez une idee??
19/05/2011, 17h32
pseudocode

Citation:

Envoyé par T_Lara

oui oui faute de frappe de ma part je l'avais rectifier avant meme que vous poster ;)

Merci alors faut peut être que je revois cette theorie de space scale plus en details si je veux mieux comprendre mais pour l'implementation je vois..sinon pour le nombre d'octave vous avez une idee??

Le nombre d'octave, c'est le nombre de fois où l'on peut réduire l'image par 2

500x500 --> 250x250 --> 125x125 --> 62x62 --> 31x31 --> 15x15 --> 7x7 --> 3x3 --> 1x1

ici, 8 réductions successives, donc 8 octaves.

C'est donc lié au Log_2, c'est à dire le nombre de puissance de 2 dans les dimensions de départ. En effet, on a 2^8=256 < 500 < 512=2^9.

Le "-2" au bout de la formule c'est pour s'arrêter avant d'atteindre des dimensions trop ridicules du genre 1x1. :aie:
20/05/2011, 00h55
T_Lara

mais c'est pas trop aller jusqu’à la fin ?? est ce que le nombre d'octave influence sur la methode? ou bien suis libre de choisir le nombre d'octave ??
20/05/2011, 01h23
pseudocode

Citation:

Envoyé par T_Lara

mais c'est pas trop aller jusqu’à la fin ??

Le descripteur dans SIFT a besoin d'un voisinage 16x16, donc il ne faut pas que l'image soit plus petite que cela.

Citation:

est ce que le nombre d'octave influence sur la methode? ou bien suis libre de choisir le nombre d'octave ??

Non, ca n'influence pas le calcul, mais ca influence le nombre de descripteur que l'on peut trouver. Il faut avoir suffisamment d'images à différentes échelles pour trouver des descripteurs intéressants.
25/05/2011, 12h03
T_Lara

pourquoi le seuillage par rapport a 0.5*thr_contr/ S avant la detection des extremum ( je trouve pas dans le papier de low ce qui indique ca et surtout que thr_contr= 0.04 )

et pourquoi ils ont fait un seuillage apres interpolation par rapport a th_contr/S au lieu de 0.03 de low ( d'ou vient ce /S tjrs )
25/05/2011, 15h17
pseudocode

Citation:

Envoyé par T_Lara

pourquoi le seuillage par rapport a 0.5*thr_contr/ S avant la detection des extremum ( je trouve pas dans le papier de low ce qui indique ca et surtout que thr_contr= 0.04 )

et pourquoi ils ont fait un seuillage apres interpolation par rapport a th_contr/S au lieu de 0.03 de low ( d'ou vient ce /S tjrs )

Je ne sais pas, il faut demander aux "ils". :D
26/05/2011, 11h16
T_Lara

lool oki cela veut dire que dans Low y a pas ça c'est ce qui m'importe

Dans leur implémentation lors du calcul de l'orientation du point d’intérêt et après la creation de l'histogramme ils procèdent a une phase de lissage ( qui se fait 2 fois ) et qui se fait comme suit :

h[i]= 0.25 h[i-1] + 0.5 h[i] + 0.25 h[i+1] ( en manipulant h d'une maniere circulaire)

Je trouve pas une indication dans le papier de Low qui parle de ça..
Est ce que cette phase parrait quelques part dans le papier de Low car ca m'arrive a echapper des ptit details dans le papier
26/05/2011, 22h16
pseudocode

Citation:

Envoyé par T_Lara

Est ce que cette phase parrait quelques part dans le papier de Low car ca m'arrive a echapper des ptit details dans le papier

Heu, non. Ca n'apparait pas dans l'implémentation de Lowe

Bonjour Pseudocode je vais vous embeter encore une fois la je plante je vois pas dans ce code d'ou vient ces calcule la pour la creation du discripteur

Voici le code

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/*
Computes the 2D array of orientation histograms that form the feature
descriptor.  Based on Section 6.1 of Lowe's paper.
 
@param img image used in descriptor computation
@param r row coord of center of orientation histogram array
@param c column coord of center of orientation histogram array
@param ori canonical orientation of feature whose descr is being computed
@param scl scale relative to img of feature whose descr is being computed
@param d width of 2d array of orientation histograms
@param n bins per orientation histogram
 
@return Returns a d x d array of n-bin orientation histograms.
*/
static double*** descr_hist( IplImage* img, int r, int c, double ori,
							 double scl, int d, int n )  //scl=ddata->scl_octv, d=4 , n=8 );
{
	double*** hist;
	double cos_t, sin_t, hist_width, exp_denom, r_rot, c_rot, grad_mag,
		grad_ori, w, rbin, cbin, obin, bins_per_rad, PI2 = 2.0 * CV_PI;
	int radius, i, j;
 
	hist = calloc( d, sizeof( double** ) );
	for( i = 0; i < d; i++ )
	{
		hist[i] = calloc( d, sizeof( double* ) );
		for( j = 0; j < d; j++ )
			hist[i][j] = calloc( n, sizeof( double ) );
	}
 
	cos_t = cos( ori );
	sin_t = sin( ori );
	bins_per_rad = n / PI2;
	exp_denom = d * d * 0.5;
	hist_width = 3* scl;
	radius = hist_width * sqrt(2) * ( d + 1.0 ) * 0.5 + 0.5;
	for( i = -radius; i <= radius; i++ )
		for( j = -radius; j <= radius; j++ )
		{
			/*
			Calculate sample's histogram array coords rotated relative to ori.
			Subtract 0.5 so samples that fall e.g. in the center of row 1 (i.e.
			r_rot = 1.5) have full weight placed in row 1 after interpolation.
			*/
			c_rot = ( j * cos_t - i * sin_t ) / hist_width;
			r_rot = ( j * sin_t + i * cos_t ) / hist_width;
			rbin = r_rot + d / 2 - 0.5;
			cbin = c_rot + d / 2 - 0.5;
 
			if( rbin > -1.0  &&  rbin < d  &&  cbin > -1.0  &&  cbin < d )
				if( calc_grad_mag_ori( img, r + i, c + j, &grad_mag, &grad_ori ))
				{
					grad_ori -= ori;
					while( grad_ori < 0.0 )
						grad_ori += PI2;
					while( grad_ori >= PI2 )
						grad_ori -= PI2;
 
					obin = grad_ori * bins_per_rad;
					w = exp( -(c_rot * c_rot + r_rot * r_rot) / exp_denom );
					interp_hist_entry( hist, rbin, cbin, obin, grad_mag * w, d, n );
				}
		}
 
	return hist;
}
 
 
 
/*
Interpolates an entry into the array of orientation histograms that form
the feature descriptor.
 
@param hist 2D array of orientation histograms
@param rbin sub-bin row coordinate of entry
@param cbin sub-bin column coordinate of entry
@param obin sub-bin orientation coordinate of entry
@param mag size of entry
@param d width of 2D array of orientation histograms
@param n number of bins per orientation histogram
*/
static void interp_hist_entry( double*** hist, double rbin, double cbin,
							   double obin, double mag, int d, int n )
{
	double d_r, d_c, d_o, v_r, v_c, v_o;
	double** row, * h;
	int r0, c0, o0, rb, cb, ob, r, c, o;
 
	r0 = cvFloor( rbin );
	c0 = cvFloor( cbin );
	o0 = cvFloor( obin );
	d_r = rbin - r0;
	d_c = cbin - c0;
	d_o = obin - o0;
 
	/*
	The entry is distributed into up to 8 bins.  Each entry into a bin
	is multiplied by a weight of 1 - d for each dimension, where d is the
	distance from the center value of the bin measured in bin units.
	*/
	for( r = 0; r <= 1; r++ )
	{
		rb = r0 + r;
		if( rb >= 0  &&  rb < d )
		{
			v_r = mag * ( ( r == 0 )? 1.0 - d_r : d_r );
			row = hist[rb];
			for( c = 0; c <= 1; c++ )
			{
				cb = c0 + c;
				if( cb >= 0  &&  cb < d )
				{
					v_c = v_r * ( ( c == 0 )? 1.0 - d_c : d_c );
					h = row[cb];
					for( o = 0; o <= 1; o++ )
					{
						ob = ( o0 + o ) % n;
						v_o = v_c * ( ( o == 0 )? 1.0 - d_o : d_o );
						h[ob] += v_o;
					}
				}
			}
		}
	}
}
 
 
static int calc_grad_mag_ori( IplImage* img, int r, int c, double* mag, double* ori )
{
	double dx, dy;
 
	if( r > 0  &&  r < img->height - 1  &&  c > 0  &&  c < img->width - 1 )
	{
		dx = pixval32f( img, r, c+1 ) - pixval32f( img, r, c-1 );
		dy = pixval32f( img, r-1, c ) - pixval32f( img, r+1, c );
		*mag = sqrt( dx*dx + dy*dy );
		*ori = atan2( dy, dx );
		return 1;
	}
 
	else
		return 0;
}

Je suppose que ca

hist_width = 3* scl;
radius = hist_width * sqrt(2) * ( d + 1.0 ) * 0.5 + 0.5;

est relatif a la taille des 4*4 carree dans le cas de Low on va prendre directement radius= 7 ( je sai pas si on peut se permettre ca vu que c et r c'est des entiers)

mais j'arrive pas a voir ces c_rot ,r_rot ,rbin et cbin

d'apres vos posts j avais compris qu une simplification par rapport a Low va etre la suivante:

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
 
static double*** descr_hist( IplImage* img, int r, int c, double ori,
							 double scl, int d, int n )  //scl=ddata->scl_octv, d=4 , n=8 );
{
	double*** hist;
	int radius, i, j;
 
	hist = calloc( 4, sizeof( double** ) );
	for( i = 0; i < 4; i++ )
	{
		hist[i] = calloc( 4, sizeof( double* ) );
		for( j = 0; j < 4; j++ )
			hist[i][j] = calloc( 8, sizeof( double ) );
	}
 
 
	exp_denom = 4 * 4 * 0.5;
	for( i = -7; i <= 8; i++ )
		for( j = -7; j <= 8; j++ )
		{	if( calc_grad_mag_ori( img, r + i, c + j, &grad_mag, &grad_ori ))
				{      
					grad_ori -= ori;
					while( grad_ori < 0.0 )
						grad_ori += PI2;
					while( grad_ori >= PI2 )
						grad_ori -= PI2;
 
 
					w = exp( -(i * i + j* j) / exp_denom );  // la est le pb est ce qu'il faut garder i et j ?
					distance= sqrt( i*i+j*j)
					v= w* Max ((1-distance),0) * grad_mag
 
 
                                        for ( t=0; t<=7; t++)
					if ( grad_ori < t* 45){
					        hist[(7+i) Div 4][(7+j) Div 4][t-1] += v * (t*45-grad_ori)/45
						hist[(7+i) Div 4][(7+j) Div 4][t] += v * (grad_ori-(t-1)*45)/(5
					    break;
					}
				}
		}
 
	return hist;
}

Ce code est il juste

d'un autre part cette façon de faire avec la distribution sur les deux Bins les plus proche est elle utilisée même lors de la création du premier histogramme pour la détection de l'orientation

car dans le même code que j’étudie il utilise plutôt Hist [36*(Ori+pi)/2pi]=w*Mag

( par contre comme je l'avais mentionné il procède a un certain lissage de l'histogramme après sa construction )

01/06/2011, 00h05
pseudocode

Citation:

Envoyé par T_Lara

Je suppose que ca

hist_width = 3* scl;
radius = hist_width * sqrt(2) * ( d + 1.0 ) * 0.5 + 0.5;

est relatif a la taille des 4*4 carree dans le cas de Low on va prendre directement radius= 7 ( je sai pas si on peut se permettre ca vu que c et r c'est des entiers)

oui, je le suppose aussi. Je ne vois pas trop ce que vient faire le "3*scl" dans l'histoire, mais passons.

Citation:

mais j'arrive pas a voir ces c_rot ,r_rot ,rbin et cbin

a mon avis : c= column, r=row

c_rot = colonne après rotation (pour aligner avec l'orientation)
r_rot = ligne après rotation

rbin et cbin, ca a l'air d'être les coordonnées du pixels, en bidouillant c_rot et r_rot pour tomber "au milieu" des cases.

Citation:

d'apres vos posts j avais compris qu une simplification par rapport a Low va etre la suivante

Hum... je ne me souvient pas avoir dit qu'on pouvait simplifier quoi que ce soit. :?

Citation:

w = exp( -(i * i + j* j) / exp_denom ); // la est le pb est ce qu'il faut garder i et j ?

i²+j² ca représente la distance (au carré) du pixel au centre du patch. Ce n'est donc pas sensible a l'orientation. Tu peux donc garder i et j.

Citation:

Ce code est il juste

J'en sais rien. :aie:

Je ne vois pas trop où est passé la rotation pour aligner le patch avec l'orientation dominante.

Citation:

d'un autre part cette façon de faire avec la distribution sur les deux Bins les plus proche est elle utilisée même lors de la création du premier histogramme pour la détection de l'orientation

EDIT: Oui, il faut distribuer la valeur de l'orientation sur les 2 bins les plus proches dans l'histogramme 36 bins.

(je n'avais pas compris la question.)
01/06/2011, 11h34
T_Lara

Citation:

c_rot = colonne après rotation (pour aligner avec l'orientation)
r_rot = ligne après rotation

rbin et cbin, ca a l'air d'être les coordonnées du pixels, en bidouillant c_rot et r_rot pour tomber "au milieu" des cases.

La suis daccord mais c'est la formule que je vois pas comment elle est faite avec un / width_hist

Citation:

Hum... je ne me souvient pas avoir dit qu'on pouvait simplifier quoi que ce soit.

Non non j'ai pas parler non plus de simplifier Lowe c'est simplifier le code que j'ai pour coincider avec Lowe

Citation:

Je ne vois pas trop où est passé la rotation pour aligner le patch avec l'orientation dominante.

Cela ve dire qu'il faut prendre la fenetre de 16*16 par rapport a l'axe lier a l'orientation ?? ( chose que j'ai pas pris en compte)
et l'orientation des pixel autour du point d'interet va etre ori_pixelt - ori_pointd'interet

Est ce que ca rentre ailleur aussi ??
01/06/2011, 11h41
pseudocode

Citation:

Envoyé par T_Lara

La suis daccord mais c'est la formule que je vois pas comment elle est faite avec un / width_hist

Là, je ne sais pas non plus.

Citation:

Cela ve dire qu'il faut prendre la fenetre de 16*16 par rapport a l'axe lier a l'orientation ?? ( chose que j'ai pas pris en compte)
et l'orientation des pixel autour du point d'interet va etre ori_pixelt - ori_point d'interet

Oui, c'est ca.
02/06/2011, 11h32
T_Lara

Une derniere question pour le discripteur ( esperons lool :p)

Pour la disatance d
each entry into a bin is multiplead by a weiight of 1-d for each dimension where d is the disatance of the sample from the central value of the bin as measured in units of the histogram bin spacing

c'est la distance entre le pixel et le centre du carré qui le contient parmi les 16 carré ?

la magnitude du pixel ne diffère toujours pas après rotation c'est celle liee a l'image sans rotation sans rien
SQRT ((L(x+1,y)- L(x-1,y ))^2 +( L(x,y+1)-L(x,y-1))^2 ))
02/06/2011, 13h17
pseudocode

Citation:

Envoyé par T_Lara

c'est la distance entre le pixel et le centre du carré qui le contient parmi les 16 carré ?

C'est la distance entre le pixels et le centre d'un des 4 patchs (4x4) adjacent.

Une petite image pour que ca soit plus clair.

http://xphilipp.developpez.com/tmp/s...ar_interpo.png

à répéter pour les 3 autres patchs : noirs, bleu et vert.

PS : ne pas oublier de pré-multiplier la norme du gradient par la gaussienne centrée sur le patch 16x16.
02/06/2011, 14h55
T_Lara
suis très reconnaissante pour l'illustration super bien faite la vérité j étais loin de comprendre ça Je croyais que le pixel orange n'allais influencer que l'histogramme du patch noir chose qui a l'air complètement fausse aparament et ce qui m'embete le plus c'est que j'arrive pas a voir ca dans le papier de Lowe directement.

juste une autre question

Citation:

C'est la distance entre le pixels et le centre d'un des 4 patchs (4x4) adjacent.

1-qu'est ce que vous appelez adjacent ? j'ai essayée d'analyser votre raisonnement et comment avoir que 4 patch adjacent je n'est trouvee qu'une seule interpretation ..le pixel influence sur les histogrammes des patch dont sa distance horisontal et vertical de leurs centre est inferieure a 4

cela est il vrai ? dans ce cas est ce que l image illustrative est juste?

2-cette manipulation se fait pour tout les pixel pas seuls dans les patch des frontieres ??

Citation:

PS : ne pas oublier de pré-multiplier la norme du gradient par la gaussienne centrée sur le patch 16x16.

3- ie : exp( -(i * i + j* j) /( 4*4*0.5)) ( ou i et j sont pris par rapport au point d'interet ) ??

4- Pour la normalisation du vecteur discripteur "to unit length" cela veut dire ca ??:: ( enfin moi j'avais pas compris qu'est ce que ca veut dire unit length mais d'apres le code c'est la racine des somme des carres )
Code:

1 2 3 4 pour ( i=0 , i< longeur_du_vecteur, i++) l += v[i]*v[i] pour ( i=0 , i< longeur_du_vecteur, i++) v[i]= v[i]/ sqrt( v[i] )
PS: je reviens sur un petit point pour l'assurer concernant le calcul de l'orientation du point d’intérêt ..lors de la création de l'histogramme si 0<tetha<10 c'est hist[0] qui reçoit le mag n'est-ce pas

Vraiment dsl pour tous ce derrangement

Voici l'image : http://www.imagup.com/data/1121684450.html
http://www.imagup.com/data/1121684450.html

Voir 40 message(s) de cette discussion en une page