Discussion :

[lilou1320]

Bonjour à tous,

Je précise d'emblée que je débute en traitement du signal.

J'ai à ma disposition deux matrices qui représentent des champs de hauteur différents. Je cherche à trouver un éventuel lien entre ces deux topographies, et surtout, à localiser les zones où la corrélation entre les deux distributions est suffisante.

Je me suis rapidement retrouvée à chercher du côté des fonctions de corrélations xcorr, xcorr2, normxcorr2.

Malgré le nombre important de sujet ouvert à ce sujet je n'ai pas réussi à comprendre comment réellement l'utiliser.

Mes matrices A et B sont carrées et de mêmes dimensions notées N. Le résultat de xcorr2(A,B) est donc une matrice carrée de dimension 2N-1. Comment, à partir de ce résultat, reporter les zones où la corrélation est élevée au niveau des matrices A et B? Les dimensions ont changé, le report n'est pas simple.

Je me suis donc penchée sur la manière avec laquelle MATLAB calcule cette matrice xcorr2 pour pouvoir avoir une idée du calcul mené. Et c'est là que repose mon gros problème. Comme traité dans un sujet précédent : http://www.developpez.net/forums/d11...nction-xcorr2/, il faut ajouter des zéros à l'une des matrices.

En prenant le cas suivant et en prenant les notations données par MATLAB : http://www.mathworks.fr/help/toolbox...ef/xcorr2.html

Code :

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

1
2
3
A=[1 2;3 4] Ma=2,Na=2
B=[2 3;4 5] Mb=2,Nb=2
C=xcorr2(I1,I2)=[5 14 8;18 40 20;9 18 8]

Mc=Ma+Mb-1 et Nc=Na+Nb-1. Niveau dimension, ça colle bien avec ce que l'on voulait : une matrice 3x3.

Essayons de retrouver avec la formule décrite.

C(0,0)=I1(0,0)I2(0,0)+I1(0,1)I2(0,1)+I1(1,0)I2(1,0)+I1(1,1)I2(1,1);
C(0,0)=1.2+2.3+3.4+4.5=40... C'est différent de la valeur trouvée par MATLAB...

Dés la premier terme je suis perdue... J'ai essayé à plusieurs reprises mais rien n'y fait, je ne vois pas mon erreur.

J'ai ensuite essayé de comprendre l'explication de MATLAB mais il semble que le résultat annoncé sur la cellule (2,4) soit en fait celle de la cellule (3,5). Résultat : Très désorientée...

Si vous pouviez m'expliquer ce que je ne comprends pas sur cette formule ce serait très sympa

Si vous avez d'autres alternatives à me proposer, n'hésitez pas

En vous remerciant par avance,

Lilou

[Jean Dumoncel]

Bonjour,

Il faut voir la cross-corrélation comme un balayage de la matrice A par a matrice B, et pour traiter les valeurs aux bords, on agrandi la matrice A pour pouvoir calculer la corrélation avec B.

Suivant ce principe A devient :

0 0 0 0
0 1 2 0
0 3 4 0
0 0 0 0

Puis on balaie cette matrice avec B, on a bien alors :
C(0,0)=A(0,0)B(0,0)+A(0,1)B(0,1)+A(1,0)B(1,0)+A(1,1)B(1,1)=5
Et tu peux facilement retrouver les autres valeurs.

Donc la position dans A de la plus forte corrélation avec B dépendra effectivement des dimensions de B.

Pour l'exemple de la doc c'est la même chose, sauf que les zéros ne sont pas représentés, mais c'est bien l'élément (2,4) qui est calculé.

La représentation avec les zéros c'est juste pour le principe, dans les algorithmes ces valeurs sont simplement ignorées.

[lilou1320]

Merci Magelan pour cette explication!

En effet, une fois que l'on comprend comment le calcul est effectué, tout s'éclaire

Pour ceux, qui comme moi, aiment avoir des exemples concrets, je reprends mon exemple très simple.


Pour calculer C(0,0), i.e. le premier terme de la matrice (3x3) C=xcorr2(A,B)
A s'écrit de la manière décrite par Magelan :

Code :

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

1
2
3
4
5
 
0 0 0 0 
0 1 2 0
0 3 4 0
0 0 0 0

B s'écrit de la manière suivante :

Code :

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

1
2
3
4
5
 
2 3 0 0 
4 5 0 0
0 0 0 0
0 0 0 0

Pour C(0,1),
A s'écrit :

Code :

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

1
2
3
4
5
 
0 0 0 
1 2 0
3 4 0
0 0 0

B s'écrit :

Code :

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

1
2
3
4
5
 
0 2 3 0 
0 4 5 0
0 0 0 0
0 0 0 0

Pour C(0,2),
A s'écrit :

Code :

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

1
2
3
4
5
 
0 0 
2 0
4 0
0 0

B s'écrit :

Code :

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

1
2
3
4
5
 
0 0 2 3
0 0 4 5
0 0 0 0
0 0 0 0

Pour C(1,0),
A s'écrit :

Code :

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

1
2
3
4
 
0 1 2 0
0 3 4 0
0 0 0 0

B s'écrit :

Code :

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

1
2
3
4
5
 
0 0 0 0
2 3 0 0
4 5 0 0
0 0 0 0

Pour C(1,1),
A s'écrit :

Code :

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

1
2
3
4
 
1 2 0
3 4 0
0 0 0

B s'écrit :

Code :

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

1
2
3
4
5
 
0 0 0 0
0 2 3 0
0 4 5 0
0 0 0 0

Pour C(1,2),
A s'écrit :

Code :

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

1
2
3
4
 
2 0
4 0
0 0

B s'écrit :

Code :

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

1
2
3
4
5
 
0 0 0 0
0 0 2 3
0 0 4 5
0 0 0 0

Pour C(2,0),
A s'écrit :

Code :

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

1
2
3
 
0 3 4 0
0 0 0 0

B s'écrit :

Code :

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

1
2
3
4
5
 
0 0 0 0
0 0 0 0
2 3 0 0
4 5 0 0

Pour C(2,1),
A s'écrit :

Code :

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

1
2
3
 
3 4 0
0 0 0

B s'écrit :

Code :

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

1
2
3
4
5
 
0 0 0 0
0 0 0 0
0 2 3 0
0 4 5 0

Pour C(2,2),
A s'écrit :

Code :

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

1
2
3
 
4 0
0 0

B s'écrit :

Code :

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

1
2
3
4
5
 
0 0 0 0
0 0 0 0
0 0 2 3
0 0 4 5

Il est alors possible de retrouver les 9 termes de la matrice C en suivant la formule donnée dans l'aide de MATLAB.

Pour A et B des matrices carrées de dimension 3, le même schéma est suivi. Avec A=[1 2 3;4 5 6; 7 8 9] et B=[9 8 7;6 5 4;3 2 1]
A devient :

Code :

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

1
2
3
4
5
6
7
8
 
0 0 0 0 0 0 0 
0 0 0 0 0 0 0
0 0 1 2 3 0 0
0 0 4 5 6 0 0
0 0 7 8 9 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Et B sera pour C(0,0) premier terme de la matrice (5x5) C=xcorr2(A,B)

Code :

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

1
2
3
4
5
6
7
8
 
9 8 7 0 0 0 0 
6 5 4 0 0 0 0
3 2 1 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Ensuite on suivra le même processus de calcul que pour les matrices (2x2) explicité en détail auparavant.

Pour étendre à une dimension plus élevée, en notant la dimension des matrices carrées N, le nombre de zéro à ajouter à A sera de N-1 sur chaque bord. La matrice A sera donc une matrice carrée de dimension N+2*(N-1).

Le résultat de xcorr2(A,B) sera de dimension N+(N-1) ce qui correspond au nombre de décalage que devra subir B pour parcourir A.


Je vais maintenant me pencher à trouver une signification physique de ce résultat...

[Jean Dumoncel]

Pour étendre à une dimension plus élevée, en notant la dimension des matrices carrées N, le nombre de zéro à ajouter à A sera de N-1 sur chaque bord. La matrice A sera donc une matrice carrée de dimension N+2*(N-1).

Le résultat de xcorr2(A,B) sera de dimension N+(N-1) ce qui correspond au nombre de décalage que devra subir B pour parcourir A.

Ceci est vrai dans le cas ou les 2 matrices sont des matrices carrées, mais les matrices ne sont pas obligatoirement carrées.

[lilou1320]

Il est en effet important de le souligner. En l’occurrence, je traite des matrices carrées que je cherche à comparer.

Je tente maintenant de comprendre comment à partir du résultat de la fonction C=xcorr2(A,B) il est possible de déterminer les zones communes à A et B qui présentent le plus de corrélation.

Maintenant que je comprends comment chacun des termes de C est obtenu, je peux me ramener à l'exemple où N=2.
A:

Code :

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

1
2
3
 
1 2 
3 4

et B:

Code :

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

1
2
3
 
2 3 
4 5

C:

Code :

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

1
2
3
4
 
5  14  8
18 40 20
9  18  8

C(1,1)=40 est la valeur maximale de corrélation entre les 2 matrices (2x2). Si l'on regarde de plus près, la position du calcul pour trouver 40 était :

Pour C(1,1),
A s'écrit :
1 2 0
3 4 0
0 0 0
B s'écrit :
Sélectionner tout - Visualiser dans une fenêtre à part
0 0 0 0
0 2 3 0
0 4 5 0
0 0 0 0

Pour obtenir cette valeur de C(1,1) on comprend qu'aucun des 0 du contour n'a été appelé. Il est donc normal que ce soit ce résultat qui soit le plus grand.

de plus, l'article cité par la documentation MATLAB pour xcorr2 mentionne quelques inconvénients pour cette fonction (http://www.idiom.com/~zilla/Papers/n...tml#eq1:normcc). Notamment :

• The correlation between the feature and an exactly matching region in the image may be less than the correlation between the feature and a bright spot.
• The range of C is dependent on the size of the feature.
• C is not invariant to changes in image amplitude such as those caused by changing lighting conditions across the image sequence.

La solution serait de normaliser la fonction xcorr2 ce que fait la fonction normxcorr2.

En notant D=normxcorr2(A,B) dans le cas des matrices (2x2) on aura :

Code :

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

1
2
3
4
 
  0.7746    0.9467    0.2582
  0.6742    1.0000   -0.2108
 -0.2582   -0.8345   -0.7746

Dans ce cas, le maximum de corrélation semble toujours correspondre à C(1,1). Il est à souligner que normxcorr2 rend des valeurs comprises dans l'intervalle [-1;1].

Passons à la dimension supérieure. A et B de dimension (3x3)
A:

Code :

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

1
2
3
4
 
1 2 3
4 5 6
7 8 9

B:

Code :

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

1
2
3
4
 
9 8 7
6 5 4
3 2 1

Dans ce cas, C=xcorr2(A,B):

Code :

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

1
2
3
4
5
6
 
1    4    10    12      9
8    26    56   54     36
30  84   165   144   90
56  134  236  186   108
49  112  190  144    81

Dans ce cas en notant D=normxcorr2(A,B):

Code :

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

1
2
3
4
5
6
 
0.5477    0.7169    0.7926    0.5092    0.2739
0.4442    0.5446    0.5241    0.1905    0.0180
 0          -0.2739   -1.0000   -0.7455   -0.5477
-0.1936   -0.4973   -0.9761   -0.8014  -0.5820
-0.2739   -0.5249   -0.8165   -0.7100  -0.5477

Le maximum de xcorr2 n'est plus situé au même endroit que normxcorr2. Je décide donc d'abandonner xcorr2 pour n'utiliser que normxcorr2.

Le maximum est ici D(0,2)=0.7926
Pour obtenir cette valeur il a fallu effectuer l'opération en ce sens:
A:

Code :

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

1
2
3
4
5
6
7
8
 
0 0 0 0 0 
0 0 0 0 0
1 2 3 0 0
4 5 6 0 0
7 8 9 0 0
0 0 0 0 0
0 0 0 0 0

B:

Code :

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

1
2
3
4
5
6
7
8
 
0 0 9 8 7 0 0 
0 0 6 5 4 0 0
0 0 3 2 1 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

La question que je me pose est la suivante :

Comment à partir du résultat de normxcorr2 peut on avoir une correspondance avec les matrices A et B? (L'objectif étant d'obtenir les coordonnées des zones de plus grande corrélation sur A et B)

1. Plus généralement, peut on tirer ce genre de conclusion en faisant ce type d'analyse?
2. Si oui, en se ramenant au cas des matrices A, B de dimension 3, est ce la zone sur A {A(0,0) A(0,1) A(0,2)} qui a le plus de corrélation avec B?
3. Si non, Existe t'il une fonction plus adaptée pour répondre à cette question?

J'ai essayé de fournir une explication détaillée de ce que je cherche à faire, j'espère que cela reste compréhensible