Dans un billet précédent, nous avons vu comment (en théorie) une inter-corrélation pouvait permettre de localiser un objet dans une image. La conclusion était que l'inter-corrélation n'est pas très efficace car sa valeur dépend énormément du niveau de gris des images et assez peu de leur information spatiale. Nous allons voir comment corriger cela.

Le notebook sage de ce billet est : detecteur_de_motifs_phase.sws

Rappels

Il s'agit d'exploiter les propriétés de la transformée de Fourier, utilisée pour calculer l'inter-corrélation. La formule que nous avions utilisée était :

$\hat{D} = \hat{I} \cdot \hat{P}^* ,$

$\hat{A}$ étant la transformée de Fourier discrète (TFD) de l'image $A$. Le calcul consiste donc à prendre la TFD de l'image référence $I$, la TFD de l'image motif $P$ (moyennant les précautions décrites précédemment) et de multiplier pixel à pixel les deux images obtenues. Penchons nous d'un peu plus près sur les transformées de Fourier qui sont manipulées.

Répartition de l'information dans une transformée de Fourier

La transformée de Fourier d'une image réelle est une image dont les valeurs sont des nombres complexe. Un nombre complexe $c$ peut s'exprimer de deux façons :

$c = x + i y = A e ^ \varphi ,$

où $x$, $y$, $A$ et $\varphi$ sont des nombres réels. $x$ est la partie réelle, $y$ la partie imaginaire. $A$ est le module et $\varphi$ l'argument. Nous exploiter cette dernière écriture.

Puisque $\hat{I}$ est une image complexe, il est également possible de l'écrire sous la forme d'un module et d'un argument. L'argument étant en général appelé phase :

$\hat{I} = A_I e^{\varphi_I}.$

$A_I$ est alors une image contenant le module de chaque valeur de $I$, $\varphi_I$ est une image contenant la phase. Si nous cherchons à comprendre quelles informations sont contenue dans $A_I$ et $\varphi_I$, il est nécessaire de les isoler à partir de $\hat{I}$ :

$A_I = |\hat{I}|, \mathrm{~et~} \varphi_I = \frac{\hat{I}}{|\hat{I}|}.$

Prenons un exemple illustratif. Voici le portrait de Joseph Fourier :

import pylab as pl
def disp(img):
    pl.imshow(img, interpolation = 'nearest')
pl.figure(); disp(fourier); pl.savefig('fourier')

Voici le module et la phase de la TFD de ce portrait :

import numpy as np
import numpy.fft as fft
tf_fourier = fft.fft2(fourier)
module_fourier = abs(tf_fourier)
phase_fourier = tf_fourier / abs(tf_fourier)
 
pl.figure()
pl.subplot(121)
disp(np.log(int(1)+fft.fftshift(module_fourier)))
pl.title('Module')
pl.subplot(122)
disp(fft.fftshift(abs(phase_fourier)))
pl.title('Phase')
pl.savefig('tf_fourier')

Le module contient beaucoup d'informations sur la répartition fréquentielle de l'image et sur les valeurs (en niveaux de gris) de l'image, mais ne contient que peu d'information sur les structures de l'image. C'est la phase qui contient l'information de position des structures de l'image. Cela devient clair lorsque l'on prend la TFD inverse de l'image module et de l'image phase :

phase = abs(fft.ifft2(phase_fourier))
module = np.log(int(1)+abs(fft.ifft2(module_fourier)))
 
pl.figure()
pl.subplot(121)
disp(m)
pl.title('Module')
pl.subplot(122)
disp(p)
pl.title('Phase')
pl.savefig('module_phase')

Il est alors clair que la phase contient les contours de l'image, donc ses structures.

Retour sur l'inter-corrélation

Pour améliorer le détecteur de motif, il est donc nécessaire de  :

1. supprimer l'information du module, car il contient des informations sur les niveaux de gris des images
2. conserver la phase, car elle contient les structures de l'image.

Le détecteur amélioré

Ainsi le détecteur est modifié pour ne conserver que la phase des images :

$D = TF^{-1} \left( \frac{\hat{I}}{|\hat{I}|} \cdot \frac{\hat{P}^*}{|\hat{P}^*|} \right) .$

Dans la littérature, cette détection est connue sous la dénomination SPOMF (Symmetric Phase Only Matched Filter) :

• [1994,article] bibtex
  Q. Chen, M. Defrise, and F. Deconick, "Symmetric phase-only matched filtering of Fourier-Mellin transforms for image registration and recognition"," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 16, pp. 1156-1168, 1994.
  @ARTICLE{Chen1994,
  author = {Q. Chen and M. Defrise and F. Deconick},
  title = {Symmetric phase-only matched filtering of Fourier-Mellin transforms for image registration and recognition"},
  journal = {IEEE Trans. on Pattern Analysis and Machine Intelligence},
  year = {1994},
  volume = {16},
  pages = {1156-1168},
  owner = {fredn},
  timestamp = {2008.12.18} }

Les résultats

Si l'on applique le nouveau détecteur à la recherche d'un ourson dans une image, le résutat est bien meilleur. Voici à nouveau l'image référence et le motif :

Le code sage permettant de réaliser la détection :

def phase(s): return s / abs(s)
 
def SPOMF(img, query):
    pattern = center_and_extend(query, img.shape)
    tf_pattern = fft.rfft2(pattern).conj()
    tf_img = fft.rfft2(img)
    ret = phase(tf_img) * phase(tf_pattern)
    return fft.irfft2(ret)
 
testspomf = SPOMF(ref, bear)

L'image obtenue est la suivante :

pl.figure()
disp(testspomf.max() - testspomf)
pl.savefig('testspomf')

Cette fois-ci, le maximum local se distingue clairement dans l'image et permet une localisation facile de l'ourson.

Localisation du motif dans l'image

Dans notre exemple, l'image obtenue est propre et comme il n'y a qu'une seule instance du motif, il n'y a qu'une seule position à trouver. Il suffit donc de chercher la position du maximum dans l'image :

def localise_max(img):
    m = img[0,0]
    for r in range(img.shape[0]):
        for c in range(img.shape[1]):
            if img[r, c] > m:
                m = img[r, c]
                pos = (r, c)
    return pos
localise_max(testspomf)

La position trouvée est (45, 69), ce qui correspond bien à la position de l'ourson dans l'image.

Localisation avec une précision sous-pixel

La méthode est la même, il s'agit toujours de détecter un maxmim dans l'image. Mais nous allons interpoler l'image pour améliorer la précision de la localisation. Pour accélérer les calculs, nous ne travaillerons qu'avec une petite image centrée autour du maximum détecté (45, 69).

import scipy
import scipy.interpolate as ip
 
part = testspomf[44:47, 68:71]

Cette imagette 3x3 est alors interpolée sur une grille plus fine (ici dix fois plus précise). Entre chaque pixel de l'ancienne grille, une interpolation linéaire permet de trouver la valeur des pixels sur la nouvelle grille.

xrange = np.arange(part.shape[0])
yrange = np.arange(part.shape[1])
X, Y = np.meshgrid(xrange, yrange)
outgrid = ip.interp2d(X,Y, part , kind='linear')
xi = np.arange(0, 2.1, .1, float)
yi = xi
z = outgrid(xi, yi)
pl.figure()
disp(z)
pl.savefig('interp')

Il suffit alors de rechercher la position du maximum dans l'image z, en n'oubliant pas de translater le résultat :

(r, c) = localise_max(testspomf)
(dr, dc) = localise_max(z)
(dr, dc) = dr/10., dc/10.
(R, C) = r + dr - 1, c + dc - 1

On obtient alors R = 45.0 et C = 69.2.

Pour obtenir une précision encore plus grande, il est possible :

• d'interpoler plus finement la grille,
• ou de choisir une autre méthode d'interpolation : spline, quadratique, ...

Conclusion

Ne conserver que la phase des transformées de Fourier des images à comparer permet d'obtenir une bonne localisation du motif. Cependant, si dans la référence, les instances possèdent des orientation et des tailles différentes de l'image motif, la méthode ne peut plus fonctionner. Ou alors si les variations d'orientation et d'échelle sont faibles. Dans un prochain billet nous verrons comment encore améliorer le détecteur pour le rendre robuste à ces variations

FMN.