• [cliquer ici pour la version en français]

Translate original post with Google Translate

Avec cet article, je commence une petite série destinée à expliquer quelques méthodes permettant de trouver des objets dans une image. Toute les méthodes seront accompagnées d'illustrations reproductible sous sage. Les codes sources seront également téléchargeables sous la forme d'un notebook sage.

Notebook

Vous pouvez télécharger le notebook sage contenant le code complet présenté ici accompagné des images de test : detecteur_de_motifs_base__sur_une_intercorrelation.sws

Objectif

Pour ce premier article, imaginons que j'ai l'image suivante (que j'appelle image reférence)  :

Je pense que vous avez tous remarqués le mignon petit ourson au centre de l'image. Tentons de le retrouver. Il faut d'abord posséder une image contenant un exemplaire de l'objet à chercher, en voici une que j'appelle image motif :

Méthode

L'idée est de faire glisser l'image de l'ourson sur l'image de référence et pour chaque position, de calculer le produit des pixels du motif avec les pixels de la référence, puis de faire la somme de toutes ces valeurs. Cette opération s'appelle un produit d'intercorrélation (cross-correlation en anglais). La formulation mathématique en est la suivante :

$D(r, c) = \sum_{k=-\infty}^{+\infty} \sum_{l=-\infty}^{+\infty} I(k, l)P(r+k,c+l)$

Implémentation

En pratique, l'inter-corrélation n'est quasiment jamais calculée sous cette forme. Il est beaucoup plus avantageux (en terme de temps de calcul) d'effectuer cette opération dans le domaine de Fourier :

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

(attention à la conjugaison de $TF(P)$). Ainsi l'inter-corrélation se transforme en un produit pixel à pixel, ce qui est rapide. L'implémentation est assez directe, mais il faut prêter attention aux points suivants, fréquemment négligés chez le débutant et sources d'erreurs :

• la transformée de Fourier discrète est une fonction $2\pi$-périodique,
• le produit pixel à pixel impose que $TF(I)$ et $TF(P)$ soient de même taille.

Ainsi l'image du motif doit être modifiée pour que :

• sa taille soit celle de la référence,
• le centre de l'image du motif corresponde à l'origine des axes.

Ceci est réalisé par la fonction suivante :

import numpy as np
def center_and_extend(img, dom):
    temp = np.zeros(dom)
    h, w = img.shape
    r, c = int(h/2), int(w/2)
 
    p = img[r:, c:]
    temp[0:height(p), 0:width(p)] += p
 
    p = img[:r, :c]
    temp[-height(p):,-width(p):] += p
 
    p = img[r:, :c]
    temp[0:height(p), -width(p):] += p
 
    p = img[:r, c:]
    temp[-height(p):, :width(p)] += p
 
    return temp

• en ligne 4 : le centre de l'image motif est calculé,
• lignes 6-7 : la partie sud-est du motif est extraite et ajoutée à l'image résultat,
• lignes 9-10 : la partie  nord-ouest du motif est extraite et ajoutée à l'image résultat,

L'image suivante est ainsi obtenue :

Vous remarquerez que si vous périodisez cette image (en la dupliquant), l'image de l'ourson est reproduite.

Il est maintenant possible de calculer l'inter-corrélation dans le domaine de Fourier :

import numpy.fft as ft
def intercorrelation(img, query):
    pattern = center_and_extend(query, img.shape)
    tf_pattern = ft.rfft2(pattern).conj()
    tf_img = ft.rfft2(img)
    ret = tf_img * tf_pattern
    return ft.irfft2(ret)

Résultat

L'image résultat est la suivante : L'ourson étant (a peu près) au centre de l'image, les niveaux de gris du centre devraient être plus importants que les autres, pour produire un max local de forte valeur. Cela ne semble pas être le cas. Le rendu est plus lisible en trois-dimensions ($z$ = niveau de gris) : On constate immédiatement que les max locaux ne correspondent pas à la position de l'objet. En fait l'inter-corrélation seule n'est pas très efficace. En effet, la valeur de l'inter-corrélation dépend plus du niveau de gris de la référence que de sa structure spatiale. Ainsi des objets très clairs (tels que le 'S' inversé en bas de l'image référence) ne correspondant pas au motif produisent une réponse plus forte que les objets moins clair qui correspondent au motif.

Nous verrons la prochaine fois comment pallier ce défaut.

FMN.