Discussion :

[mobi_bil]

Bonjour à tous,
J'ai réalisé un système de recherche d'images par points d'intérêt basé sur le detecteur de HARRIS (impl de Pseudocode).
Le problème est que les points détectés ne sont pas invariants au changement d'échelle.
Après une recherche sur google concernant la localisation des points d'intérêt invariants au changement d'échelle, j'ai trouvé un article qui parle d'extraction de points multi-échelle.
Question 1 : Comment détecter les points d'intérêt sur plusieurs résolutions d'image (figure ci-dessous) ?

Question 2 : Comment choisir les points d'intérêt ainsi que l'échelle caractéristique ?
Merci pour votre aide.

[pseudocode]

Question 1 : Comment détecter les points d'intérêt sur plusieurs résolutions d'image (figure ci-dessous) ?

Il suffit de calculer la réponse de la fonction de Harris pour chaque échelle voulue.

- Soit en générant une image à l'echelle voulue et en calculant la formule de Harris

- Soit en calculant la formule de Harris multi-echelle sur l'image originale (formule 8 de ton document)

Question 2 : Comment choisir les points d'intérêt ainsi que l'échelle caractéristique ?

On cherche les points (x,y,s) qui sont à la fois:
- un maximum de la fonction de Harris au voisinage (spatial) de x,y
- un maximum de la fonction de Laplace au voisinage (échelle) de s

généralement on se "déplace" alternativement dans la représentation de harris, puis dans celle de Laplace, etc. (figure 4 de ton document):
1. on fixe s=1.0
2. on cherche un point qui est un maximum de la fonction de Harris pour l'echelle "1" --> (x1,y1,1)
3. on cherche maintenant la valeur "s1" qui est un maximum de la fonction de Laplace --> (x1,y1,s1)
4. on cherche un point au voisinage de (x1,y1) qui est un maximum de la fonction de Harris pour l'echelle "s1" --> (x2,y2,s1)

4a. si (x1,y1)=(x2,y2) alors on a trouvé notre point invariant (x1,y1,s1)

4b. sinon on retourne a l'etape 3, en utilisant (x2,y2) à la place de (x1,y1)

On réitère cette recherche pour tous les points maximum de la fonction de Harris de l'échelle 1.

[mobi_bil]

Bonjour Pseudocode et merci (comme d'hab) pour votre aide,
Concernant la réponse à la première question, quelle est la relation entre la taille de la fenetre du masque et le sigma car en modifiant seulement le sigma de la fonction gaussienne, je trouve toujours la même image (le même flou gaussien). Merci.

[pseudocode]

Concernant la réponse à la première question, quelle est la relation entre la taille de la fenetre du masque et le sigma car en modifiant seulement le sigma de la fonction gaussienne, je trouve toujours la même image (le même flou gaussien). Merci.

Dans la théorie, il n'y a pas de rapport. La fenêtre du masque gaussien est censée être de taille infinie car la fonction gaussienne ne devient jamais nulle.

En pratique, quand on s'éloigne suffisamment du centre de la fenêtre, les valeurs de la fonction gaussienne deviennent très petites et donc on peut les considérer comme nulles. On peut donc limiter la taille de la fenêtre.

Avec la fonction gaussienne, on sait que la distribution des valeurs est fonction du paramètre sigma:



En prenant un rayon 2*sigma, on dispose de 95% des valeurs.

[mobi_bil]

Voici un code java de la fonction gaussienne (basé sur votre algo de harris).

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
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
 
static int [][] gaus( int[][] input, int W, int H,double sigma2)
	{
	int [][] output=new int[W][H];
	int radius = (int)(0.5+2*Math.sqrt(sigma2)); // rayon = 2*sigma
	int window = 2*radius+1; 
	int halfwindow = (window-1)/2;
 
	double xx=0;
	double[][] filter = new double[window][window];
	double filtersum = 0;
	for(int j=-halfwindow;j<=halfwindow;j++) {
		for(int i=-halfwindow;i<=halfwindow;i++) {
			double w = gaussia(i,j,sigma2);
			filter[i+halfwindow][j+halfwindow]=w;
			filtersum+=w;
		}
	}
	for(int j=0;j<window;j++)
		for(int i=0;i<window;i++)
			filter[i][j]/=filtersum;
 
 
	for (int y=0; y<H; y++) {
		for (int x=0; x<W; x++) {
 
		for(int dy=-halfwindow;dy<=halfwindow;dy++) {
			for(int dx=-halfwindow;dx<=halfwindow;dx++) {
			             int xk = x + dx;
				int yk = y + dy;
				if (xk<0 || xk>=W) continue;
				if (yk<0 || yk>=H) continue;
 
			// filter weight
			double f = filter[dx+halfwindow][dy+halfwindow];
			xx+=f*input[xk][yk];
 
			// convolution
 
				}
			}
			output[x][y]=(int)xx;
			xx=0;
		}
	}
 
	return output;
 
	}

Par exemple, en premier lieu, j'ai éssayé pour une image de "input" donné de générer les résolutions suivantes :

gaus(input,im.getWidth(),im.getHeight() , 3, 1.2 )
cas 1 : sigma = 1.2 , j'ai trouvé une image flou
gaus(input,im.getWidth(),im.getHeight() , 3, 1.2 * 1.2)
cas 2 : sigma = (1.2 * 1.2) j'ai trouvé presque la même image du cas n°1
gaus(input,im.getWidth(),im.getHeight() , 3, 1.2 * 1.2 * 1.2)
cas 3 : sigma = (1.2 * 1.2 * 1.2), même chose, toujour la même image du premier cas.

Je ne sais pas quoi faire, merci pour votre aide.

[pseudocode]

Attention, dans mon implémentation la valeur est en fait sigma² (au carré).

Je ne sais pas quoi faire, merci pour votre aide.

il faut prendre une fenetre (window) plus grande. Par exemple:

double sigma2 = 1.2*1.2*1.2;
int radius = (int)(0.5+2*Math.sqrt(sigma2)); // rayon = 2*sigma
int window = 2*radius+1;

[mobi_bil]

On cherche les points (x,y,s) qui sont à la fois:
- un maximum de la fonction de Harris au voisinage (spatial) de x,y
- un maximum de la fonction de Laplace au voisinage (échelle) de s

Pour le voisinage spatial, c'est simple, on compare le point avec ses 8 proches voisins, mais pour le voisinage (échelle) de s, j'ai pas compris.
Supposons le point (3,5) est un maximum de harris dans (s=1), est ce que un maximum de laplace au voisinage (échelle) du point (3,5) est la plus grande valeur de la fonction laplace de toutes les valeur calculées pour différent s ? merci.

[pseudocode]

Supposons le point (3,5) est un maximum de harris dans (s=1), est ce que un maximum de laplace au voisinage (échelle) du point (3,5) est la plus grande valeur de la fonction laplace de toutes les valeur calculées pour différent s ? merci.

Oui, le "s" optimal ets celui qui donne la plus grande valeur de la fonction de Laplace calculée au point (3,5).

[mobi_bil]

Bonjour pseudocode et meci pour votre réponse.
Je suis entrain d'implementer l'algorithme du post #2, pour cela, j'ai utilisé votre algo Harris-Fast pour la detection des points d'intérêt.
Question : Comment calculer la fonction F(Image,(x,y),échelle)

[mobi_bil]

Pour être clair , comment calculer la fonction de laplace en un pixel (x,y) d'une image I à l'échelle s:
Laplace(I,(x,y),s). Merci pour votre aide.

[pseudocode]

Bonjour pseudocode et meci pour votre réponse.
Je suis entrain d'implementer l'algorithme du post #2, pour cela, j'ai utilisé votre algo Harris-Fast pour la detection des points d'intérêt.
Question : Comment calculer la fonction F(Image,(x,y),échelle)

F(x,y) est le résultat de la convolution de Image au point (x,y) par une gaussienne de variance "échelle".

C'est la meme chose que la fonction "L(x,y;t)" dans l'article de wikipedia : http://en.wikipedia.org/wiki/Scale-space

[mobi_bil]

Bonjour Pseudocode et merci pour la réponse précédente,
Dans mon implementation, je me suis bloqué sur la 4ème étape :

4. on cherche un point au voisinage de (x1,y1) qui est un maximum de la fonction de Harris pour l'echelle "s1" --> (x2,y2,s1)

Si deux points ont la même valeur de Harris maximale, par exemple (x1,y1) et (x2,y2), est ce qu'on peut considérer le point (x1,y1) comme invariant à l'échelle. mERCI .

[pseudocode]

Si deux points ont la même valeur de Harris maximale, par exemple (x1,y1) et (x2,y2), est ce qu'on peut considérer le point (x1,y1) comme invariant à l'échelle. mERCI .

Normalement non. Il faut que ce soit un "vrai" extrema local afin que le point soit robuste.

[mobi_bil]

Bonjour Pseudocode,
Je vous rappelle, ma question c'était :
Si deux points ont la même valeur de Harris maximale, par exemple (x1,y1) et (x2,y2), est ce qu'on peut considérer le point (x1,y1) comme invariant à l'échelle. mERCI
Et vous avez répondu :

Normalement non. Il faut que ce soit un "vrai" extrema local afin que le point soit robuste.

Dans ce cas, qu'est qu'on va prendre à la place de (x1,y1) ?
Si la réponse était (x2,y2), Supposons qu'on a un troisième point au voisinage de (x1,y1) qui est aussi un maxima de harris, toujour qu'est qu'on va prendre à la place de (x1,y1) ? mERCI pour votre aide et votre participation

[pseudocode]

Dans ce cas, qu'est qu'on va prendre à la place de (x1,y1) ?
Si la réponse était (x2,y2), Supposons qu'on a un troisième point au voisinage de (x1,y1) qui est aussi un maxima de harris, toujour qu'est qu'on va prendre à la place de (x1,y1) ? mERCI pour votre aide et votre participation

Si (x1,y1) n'est pas un maximum local ,car il y a un point voisin (x2,y2) avec une valeur identique, alors (x1,y1) n'est pas un point d'intéret. Donc on l'ignore. De même (x2,y2) ne sera pas un maximum local, car (x1,y1) à une valeur identique, donc on ignore aussi (x2,y2).

Pour être intéressant, un point doit être un vrai maximum local.

[mobi_bil]

Bonjour Pseudocode,
Je veux utiliser cette pyramide gaussienne pour trouver les points d'intérêt invariant à l'échelle ( j'éspère que ça marche).

j'ai compris la grande partie du code, sauf deux procédures.

Si vous pouvez m'aider, j'ai préparé quelques questions :

Par exemple, pour l'exemple que vous avez posté :

GaussianPyramid gp = new GaussianPyramid(4, 3);
gp.build(data, width, height, 1.6);

1 : les images de pyramide levels[i][0] (0<=i<=3) sont la convolution de l'image originale avec le masque gaussien de sigma2=1.6.

Question 1 : Est ce qu'on a besoin de ces pyramides levels[i][0] pour les traitements, ou bien on les utilise juste pour générer les différentes pyramides

2 :
toujour d'après l'exemple, on a :

K=1.26 , k^3=2
kernels[1] : masque gaussien de sigma2 =0.76
kernels[2] : masque gaussien de sigma2 =0.96
kernels[3] : masque gaussien de sigma2 =1.21

par exemple levels[0][2] contient les informations suivantes :

width, height : taille de l'image.
data=convolution de data de la pyramide levels[0][1] et kernels[2] (masque gaussien de sigma2=0.96).
sigma=1.26^2 * 1.6

Question 2 : Que représente ce sigma ? On l'a jamais utilisé dans les calculs ? même l'image de cette pyramide utilise un masque gaussien de sigma2=0.96.


Questions 3:

L(0) has scale K^0 = 1.0
L(s) = L(s-1)*G(w) has scale K^s

C'est quoi L(s) ? C'est quoi G(w) ? Comment vous avez passé de :

scale(L(s)) = scale(L(s-1)*G(w)) = sqrt( scale(L(s-1))^2 + w^2 )

[pseudocode]

1 : les images de pyramide levels[i][0] (0<=i<=3) sont la convolution de l'image originale avec le masque gaussien de sigma2=1.6.

masque gaussien avec sigma = 1.6

J'ai utilisé "sigma" et pas "sigma²" pour être conforme avec les notations utilisées dans le papier de Lowe. Mais c'est vrai que ce n'est pas très lisible et non conforme avec les notations usuelles du scale-space (cf. le livre de Tony Lindeberg "scale-space théory in computer vision")

J'ai donc reposté une nouvelle version du code qui utilise sigma^2.

Question 1 : Est ce qu'on a besoin de ces pyramides levels[i][0] pour les traitements, ou bien on les utilise juste pour générer les différentes pyramides

Non, on n'en a pas "besoin". C'est juste une commodité, par exemple quand on veut calculer la DoG (difference of Gaussian). Dans mon implémentation, je calcule deux niveaux "supplémentaires" par octave : le niveau "0" et le niveau "max+1". Par exemple, pour une pyramide avec 3 niveaux par octave, j'en calcule 5

Code :

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

1
2
3
4
5
6
Octave 1, niveau 0 
Octave 1, niveau 1 
Octave 1, niveau 2 
Octave 1, niveau 3 
Octave 1, niveau 4

2 :
toujour d'après l'exemple, on a :

K=1.26 , k^3=2
kernels[1] : masque gaussien de sigma2 =0.76
kernels[2] : masque gaussien de sigma2 =0.96
kernels[3] : masque gaussien de sigma2 =1.21

par exemple levels[0][2] contient les informations suivantes :

width, height : taille de l'image.
data=convolution de data de la pyramide levels[0][1] et kernels[2] (masque gaussien de sigma2=0.96).
sigma=1.26^2 * 1.6

Question 2 : Que représente ce sigma ? On l'a jamais utilisé dans les calculs ? même l'image de cette pyramide utilise un masque gaussien de sigma2=0.96.

Sigma^2 c'est l'échelle (= la coordonnée dans le "scale-space"). C'est la meme valeur de "sigma^2" qui est utilisée dans le calcul de la gaussienne.

Une image a l'echelle "t", c'est une image qui a été floutée avec une gaussienne "sigma^2 = t":

L(t) = L(0)*G(t)

avec,
L(t) = image a l'échelle "t"
L(0) = image a l'échelle zéro, c'est à dire l'image originale
G(t) = gaussienne de variance sigma^2 = t

Dans mon implémentation, il y a deux valeurs de sigma:

GaussianPyramid.getSigma2(int o,int s) : qui donne la valeur de "sigma^2" par rapport à l'image originale

PyramidLevel.sigma2 : qui donne la valeur de "sigma^2" par rapport à la 1ere image de l'octave. Comme on double le vrai sigma à chaque octave, on a:

GaussianPyramid.getSigma2(int o,int s) = (2^o)*PyramidLevel[s].sigma2

Questions 3:

L(0) has scale K^0 = 1.0
L(s) = L(s-1)*G(w) has scale K^s

C'est quoi L(s) ? C'est quoi G(w) ?

J'ai expliqué ci-dessus.

Comment vous avez passé de :

scale(L(s)) = scale(L(s-1)*G(w)) = sqrt( scale(L(s-1))^2 + w^2 )

Ce sont les propriétés du scale-space (http://en.wikipedia.org/wiki/Scale-space_axioms), et surtout une propriété des fonctions gaussiennes. La convolution de deux gaussienne est une gaussienne dont la variance est la somme des 2 premières: G(a)*G(b) = G(a+b). C'est à dire que leurs "sigma^2" s'additionnent.

NB : Comme j'utilise maintenant sigma2, la formule que tu as citée n'est plus valable. J'ai modifié le commentaire dans le code.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
// Level[0] has scale K^0 = 1.0
// Level[s] = Level[s-1]*G(w) has scale K^s
// Level[max] has scale K^max = 4.0
//
// => K = 4^(1/max)
//
// Level[s] = Level[0]*G(K^s) = Level[s-1]*G(w) = Level[0]*G(K^(s-1))*G(w) 
// => G(K^s) = G(K^(s-1))*G(w) 
// => K^s = K^(s-1) + w
// => w = K^s - K^(s-1)

Dans notre pyramide, l'échelle d'un niveau (par rapport a la base de l'octave) est K^s

Par définition du scale-space:

Level[s] = Level[0]*G(K^s)
Level[s-1] = Level[0]*G(K^(s-1))

Comme on souhaite que:

Level[s] = Level[s-1]*G(w)

Cela implique que :

Level[0]*G(K^s) = Level[0]*G(K^(s-1))*G(w)

et donc que

G(K^s) = G(K^(s-1))*G(w)

Par la propriété d'addition des variances :

K^s = K^(s-1) + w

=> w = K^s - K^(s-1)

et voila.

[mobi_bil]

Bonjour Pseudocode et merci pour votre aide,

Dans mon implémentation, je calcule deux niveaux "supplémentaires" par octave : le niveau "0" et le niveau "max+1". Par exemple, pour une pyramide avec 3 niveaux par octave, j'en calcule 5

Code :

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

1
2
3
4
5
6
Octave 1, niveau 0 
Octave 1, niveau 1 
Octave 1, niveau 2 
Octave 1, niveau 3 
Octave 1, niveau 4

Dans votre code, je vois que 3 niveaux (sans compter Levels[i][0]), donc au final il y a 4 niveaux :
On a : Levels[i][0], Levels[i][1], Levels[i][2], Levels[i][3]

Code :

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

1
2
3
for(int s=1; s<this.scales+1; s++)
     this.levels[o][s] = newDownScaled(this.levels[o][s-1],kernels[s],K);

Dans mon implémentation, il y a deux valeurs de sigma:

GaussianPyramid.getSigma2(int o,int s) : qui donne la valeur de "sigma^2" par rapport à l'image originale

PyramidLevel.sigma2 : qui donne la valeur de "sigma^2" par rapport à la 1ere image de l'octave. Comme on double le vrai sigma à chaque octave, on a:

GaussianPyramid.getSigma2(int o,int s) = (2^o)*PyramidLevel[s].sigma2

Qustion 1 : Est ce que la première image de l'octave i est celle de la pyramide : Levels[i][0] ?

Question 2 : Pourquoi vous dites : on double le vrai sigma à chaque octave ? dans le code vous divisez le sigma2 du dernier niveau d'une octave par 2.
J'ai pas bien compris.

De toute façon, j'ai préparé un schéma qui montre la trace de votre code.



d'après le schéma, les échelles de Levels[i][0] sont les mêmes ? c'est pour ça, je n'arrive pas à comprendre pourquoi

GaussianPyramid.getSigma2(int o,int s) = (2^o)*PyramidLevel[s].sigma2

[pseudocode]

Dans votre code, je vois que 3 niveaux (sans compter Levels[i][0]), donc au final il y a 4 niveaux :
On a : Levels[i][0], Levels[i][1], Levels[i][2], Levels[i][3]

Heu... oui. C'est moi qui me suis trompé dans mes explications.

Je calcule 1 niveau en plus, le dernier, qui équivalent au niveau "0" de l'octave suivant.

Qustion 1 : Est ce que la première image de l'octave i est celle de la pyramide : Levels[i][0] ?

Oui.

Lors de l'appel de la méthode build(), on passe en paramètre sigma² qui est utilisé pour flouter la première image.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
Levels[0][0] --> sigma2=sigma²     | echelle globale = sigma² 
Levels[0][1] --> sigma2=K*sigma²   | echelle globale = K*sigma²
Levels[0][2] --> sigma2=K^2*sigma² | echelle globale = K^2*sigma²
Levels[0][3] --> sigma2=4*sigma²   | echelle globale = 4*sigma²
 
(Levels[1][0] = downsampling de Levels[0][3])
 
Levels[1][0] --> sigma2=sigma²     | echelle globale = 4*sigma² 
Levels[1][1] --> sigma2=K*sigma²   | echelle globale = 4*K*sigma²
Levels[1][2] --> sigma2=K^2*sigma² | echelle globale = 4*K^2*sigma²
Levels[1][3] --> sigma2=4*sigma²   | echelle globale = 16*sigma²
 
...

Question 2 : Pourquoi vous dites : on double le vrai sigma à chaque octave ? dans le code vous divisez le sigma2 du dernier niveau d'une octave par 2.
J'ai pas bien compris.

d'après le schéma, les échelles de Levels[i][0] sont les mêmes ? c'est pour ça, je n'arrive pas à comprendre pourquoi

NB : Du fait que j'ai changé mon implémentation pour utiliser "sigma^2" au lieu de "sigma", il faut diviser par 4 et non plus pas 2. J'ai corrigé l'erreur.

Les "sigma²" des niveaux sont effectivement les mêmes. Normalement, en continuant a faire des convolutions, les "sigma²" devraient continuer leur progression géométrique : K, K^2, K^3, K^4, K^5, ...

Mais entre les 2 octaves, on a fait un downsampling = la taille de l'image a été divisée par 2. Et donc l'echelle est divisée par 2^2 = 4.

Mathématiquement, cela revient a faire un changement de variable.

L(x,y, octave_2) = L(2x,2y, octave_1)

En reprenant la formule du scale-space L(x,y,t) = L(x,y)*G(t), et en appliquant le changement de variable, on trouve :

L(2x,2y,t) = L(2x,2y)*G(t) = L(x,y)*G(t/4)

La dernière égalité vient du changement de variable dans une fonction gaussienne.

[mobi_bil]

// As G(ax,ay,w) = (1/a^2).G(x,y,w/a^2)