Discussion :

[Feriaman]

Bonjour,

J'ai codé une intercorrelation en java en utilisant JAI.
Mon objectif est de rechercher une image dans une autre.
Le comportement obtenu est "presque" celui attendu.

Mon algo ressemble à celui-là :

Code :

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

1
2
3
4
5
6
7
8
- agrandissement et centrage de l'image cherchée
- transformée de fourier de l'image cherchée
- suppression des modules (je ne garde que les phases)
- transformée de fourier de l'image dans laquelle je cherche
- suppression des modules (je ne garde que les phases)
- produit des deux TF
- transformée inverse du produit
- localisation du maximum

Voici le résultat sur un cas simple :

(pardon pour la mauvaise qualité du jpeg, mais pour être bien clair : il n'y a que 2 couleurs dans chaque fichier)

Tout se passe bien donc !

Sauf que quand je complexifie mon image de départ, mon maximum trouvé diminue :

(observez la valeur du maximum !)

Ceci est fort génant, pour trois raisons :

1. Cela ne correspond pas à ce que j'obtiendrais en faisant une intercorrelation "directe" sans passer par une FT
2. Si j'ai deux images de départ, je ne peux plus savoir dans laquelle des deux l'intercorrelation a le mieux marché
3. Surtout ! Si je complexifie assez l'image de départ, je n'ai plus aucun résultat

Pour illustrer le troisième point : voici un exemple (attention la différence est subtile et se situe au niveau du disque tronqué) :


Je n'arrive pas à savoir si ce comportement est normal étant donné la méthode utilisée, ou bien s'il provient de mon implémentation (ou par exemple du ma DFT ou de mon IDFT).

Voici les DFT() et IDFT(DFT()) de deux des images de départ ci-dessus :

Ces images montrent sans doute à quel moment mon implémentation foire, mais je ne comprends réellement pas pourquoi.

Merci à tous ceux qui ont lu,
Merci à ceux qui pourront m'aider

[Feriaman]

P.S : Si certains aiment le Java (et JAI en particulier), voici mon code réduit à sa plus simple expression :

traitement de l'image dans laquelle on cherche

Code :

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

1
2
3
4
5
toFindIn_Pi = toFindIn;
RenderedOp toFindIn_DFT_Prev = DFTDescriptor.create(toFindIn_Pi, DFTDescriptor.SCALING_NONE, DFTDescriptor.REAL_TO_COMPLEX, null);
RenderedOp toFindIn_Magn = MagnitudeDescriptor.create(toFindIn_DFT_Prev, null);
RenderedOp toFindIn_MagnBi = BandSelectDescriptor.create(toFindIn_Magn, new int[]{0,0},null);
toFindIn_DFT = DivideDescriptor.create(toFindIn_DFT_Prev,toFindIn_MagnBi,null);

traitement de l'image cherchée

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
toFind_Pi = toFind;
toFind_DFT = BorderDescriptor.create(	toFind_Pi,
	0,
	(toFindIn_DFT.getWidth()-toFind_Pi.getWidth()),
	0,
	(toFindIn_DFT.getHeight()-toFind_Pi.getHeight()),
	null,
	null);
toFind_DFT = PeriodicShiftDescriptor.create(	toFind_DFT,
	toFind_Pi.getWidth()/2,
	toFind_Pi.getHeight()/2,
	null);
toFind_DFT = DFTDescriptor.create(toFind_DFT, DFTDescriptor.SCALING_NONE, DFTDescriptor.REAL_TO_COMPLEX, null);
RenderedOp toFind_Conj = ConjugateDescriptor.create(toFind_DFT, null);
RenderedOp toFind_Magn = MagnitudeDescriptor.create(toFind_Conj, null);
RenderedOp toFind_MagnBi = BandSelectDescriptor.create(toFind_Magn, new int[]{0,0},null);
toFind_DFT = DivideDescriptor.create(toFind_Conj,toFind_MagnBi,null);

intercorrelation

Code :

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

1
2
3
RenderedOp opCrossPowerSpec = MultiplyComplexDescriptor.create(toFind_DFT, toFindIn_DFT, null);
opCrossPowerSpec = IDFTDescriptor.create(opCrossPowerSpec, IDFTDescriptor.SCALING_NONE, IDFTDescriptor.COMPLEX_TO_COMPLEX, null);
RenderedOp opCrossPowerMagn = MagnitudeDescriptor.create(opCrossPowerSpec, null);

[pseudocode]

Cela ne correspond pas à ce que j'obtiendrais en faisant une intercorrelation "directe" sans passer par une FT

En fait si.

Mais je vois ce que te veux dire : la normalisation ne serait pas la même si tu faisais une convolution temporelle. Tu calculerais la corrélation entre une sous-image (de la taille du motif recherché) et le motif. Dans ce cas, la corrélation entre la sous-image et le motif ne dépend pas du reste de l'image.

Dans Fourier, tu calcules la corrélation entre une image et une autre image (composée de ton motif "agrandi" et de beaucoup de vide autour). Et bien sur, plus ton image de départ contient d'autres éléments que le motif, plus la corrélation devient faible.

Hum... suis-je clair ?

[Feriaman]

Ohhhh la belle division par zéro.

Je crois que je tiens une piste.

Je vous tiens au courant.

[Feriaman]

En fait si.

Mais je vois ce que te veux dire : la normalisation ne serait pas la même si tu faisais une convolution temporelle. Tu calculerais la corrélation entre une sous-image (de la taille du motif recherché) et le motif. Dans ce cas, la corrélation entre la sous-image et le motif ne dépend pas du reste de l'image.

Dans Fourier, tu calcules la corrélation entre une image et une autre image (composée de ton motif "agrandi" et de beaucoup de vide autour). Et bien sur, plus ton image de départ contient d'autres éléments que le motif, plus la corrélation devient faible.

Hum... suis-je clair ?

Super ! Merci pour cette réponse.

C'est donc normal que la valeur absolue du max de mon résultat varie, parce que ce que je compare, ce n'est pas ma petite image, c'est ma petite image avec des bords noirs.

Et comme mes bords noirs sont présents dans l'image source dans un cas et pas dans l'autre, j'ai une moins bonne correlation.

Il me semble que c'est clair.

Et du coup ça n'a aucun rapport avec le fait qu'au bout d'un moment je n'ai plus de résultat du tout.

[Feriaman]

Super ! Merci pour cette réponse.

C'est donc normal ...

Mais du coup : comment est-ce que je corrige cela ?

Une première solution me vient immédiatement à l'esprit : une fois que j'ai localisé mon image, je découpe le morceau correspondant dans l'image de base et je refais une correlation.

Mais n'y a-t-il pas plus élégant ?

[pseudocode]

Et comme mes bords noirs sont présents dans l'image source dans un cas et pas dans l'autre, j'ai une moins bonne correlation.

voila. c'est ca.

Et du coup ça n'a aucun rapport avec le fait qu'au bout d'un moment je n'ai plus de résultat du tout.

Non... là tu dois avoir un bug quelque part.

[pseudocode]

Une première solution me vient immédiatement à l'esprit : une fois que j'ai localisé mon image, je découpe le morceau correspondant dans l'image de base et je refais une correlation.

Mais n'y a-t-il pas plus élégant ?

Avec de la corrélation de phase, je ne pense pas qu'on puisse faire plus élégant.

[Feriaman]

Avec de la corrélation de phase, je ne pense pas qu'on puisse faire plus élégant.

Super !
Merci beaucoup pour ces explications !!

Concernant mon "bug", je crois que j'ai trouvé, c'est une division par zéro qui se cache en dessous : pour supprimer le module et ne conserver que la phase de mes DFT, je fais en réalité ceci :

• je calcule le module (magnitude en JAI)
• je mets ce modules sur deux "bandes", c'est à dire que comme le module n'est pas une image complexe, mais une image réelle, je "dédouble" les valeurs
• je divise bande à bande : la partie réelle par la première "bande" et la partie imaginaire par la seconde "bande". Mais de toute façon les deux bandes contiennent la magnitude

Et cela doit poser un problème pour des très petites valeurs de la magnitude. J'ai modifié cet algo en ajoutant un truc un peu crade, mais facile à implémenter : j'ajoute 1O^-4 à la magnitude, et cela résoud le problème.

Merci encore pour ton aide !!
C'est très sympa.