Classez et segmentez des données visuelles

Motivation : "image matching"

Si vous tapez "Tour Eiffel" dans votre moteur de recherche d'images préféré, vous constaterez que les résultats représentent la même scène, mais de manières différentes. Beaucoup d'éléments peuvent varier d'une photo à une autre :

• La prise de vue (résultat d'une transformation affine ou d'une projection)

• L'orientation (résultat d'une rotation)

• L'échelle (résultat d'un zoom)

• Les propriétés photométriques : la luminosité et/ou le contraste (variations dues aux moments différents de la journée, météo, flash...)

• Occlusion : une partie de l'image est cachée

• Background clutter : une partie de l'image se confond avec les éléments en arrière-plan
   

Dans la première partie de ce cours, nous avions étudié différentes techniques permettant de transformer une image en une autre. Parmi elles, il y avait les transformations géométriques, qui modifient la position des pixels, et les manipulations d'histogrammes, qui corrigent la luminosité et le contraste.

Deux images d'une même classe, c'est-à-dire qui représentent la même chose, sont donc liées par une transformation. Cependant, la caractérisation précise de cette transformation nous est inconnue.

Il s'agit en fait d'un problème classique en vision par ordinateur, appelé image matching. Les applications sont nombreuses : parmi elles, la création de panoramas, la détection d'images similaires à une autre (visual search), ou encore la reconnaissance d'objets dans une image (object recognition).

Au lieu de chercher à déterminer l'équation mathématique précise de la transformation comme dans la partie précédente, la stratégie consiste à trouver les éléments communs aux deux images. La problématique est alors reformulée ainsi :

Cette tâche est plus ou moins triviale pour notre cerveau, mais difficile pour un ordinateur : celui-ci doit parvenir à décrire la particularité d'une classe d'images, et ce en dépit de toutes les variations possibles listées plus haut.

Le template matching avec les filtres

Dans la partie précédente, nous avons découvert les filtres comme des outils capables de réduire le bruit dans une image. En fait, les filtres sont également souvent utilisés pour retrouver des motifs particuliers dans une image. Ces motifs sont représentés par de petites images, appelées templates. La tâche de template matching a pour but de retrouver des templates dans une image.

Le template matching réalisé avec des filtres utilise l'opérateur de corrélation croisée (cross-correlation), noté $\$\backslash (\backslash otimes\backslash )\$$. Cet opérateur transforme l'image de représentation matricielle $\$\backslash (X\backslash )\$$ en une nouvelle image $\$\backslash (Y\backslash )\$$ de la façon suivante :

$\$\backslash [Y\_\{i,j\}\; =\; \backslash sum\_\{u=-k\}^k\; \backslash sum\_\{v=-k\}^k\; H\_\{u,v\}\; X\_\{i+u,\; j+v\}\backslash ]\$$

Dans ce contexte, $\$\backslash (H\backslash )\$$ est une petite image représentant le template à retrouver. Concrètement, cette opération revient à faire glisser $\$\backslash (H\backslash )\$$ sur l'image $\$\backslash (X\backslash )\$$, à multiplier les pixels qui se superposent et à sommer ces produits.

Ainsi, le template matching consiste à calculer la corrélation croisée entre une image  $\$\backslash (X\backslash )\$$ et un filtre dont le noyau $\$\backslash (H\backslash )\$$ représente un template que l'on souhaite retrouver dans $\$\backslash (X\backslash )\$$.

Rappelons la formule du produit de convolution entre un filtre de noyau $\$\backslash (H\backslash )\$$ et une image  $\$\backslash (X\backslash )\$$ : 

$\$\backslash [Y\_\{i,j\}\; =\; \backslash sum\_\{u=-k\}^k\; \backslash sum\_\{v=-k\}^k\; H\_\{u,v\}.X\_\{i-u,\; j-v\}\; \backslash ]\$$

La seule différence entre cet opérateur et la corrélation croisée se situe au niveau des indices des éléments de $\$\backslash (X\backslash )\$$. Plus exactement, la produit de convolution entre $\$\backslash (H\backslash )\$$ et $\$\backslash (X\backslash )\$$ revient à faire la corrélation croisée entre $\$\backslash (H\backslash )\$$ pivoté de 180° et $\$\backslash (X\backslash )\$$. Pour vous en rendre compte, vous pouvez effectuer le changement d'indice $\$\backslash (u\text{'}\; =\; -u\backslash )\$$ et $\$\backslash (v\text{'}\; =\; -\; v\backslash )\$$ dans la formule de la corrélation croisée.

Par conséquent, les deux opérateurs sont strictement équivalents seulement lorsque la matrice $\$\backslash (H\backslash )\$$ est symétrique. C'est le cas pour le filtre gaussien, mais pas pour les templates. La corrélation croisée est utilisée ici puisqu'on retrouve le template dans l'image tel qu'il est, et non pivoté de 180°.

La nouvelle image $\$\backslash (Y\backslash )\$$, appelée carte de corrélation, nous indique où le template a été détecté : plus une région est claire (d'intensités élevées), plus elle ressemble au template recherché.

Trouver Charlie devient alors beaucoup plus facile !

En réalité, ce n'est pas très compliqué. Imaginez les coefficients de  H  formant un vecteur en dimension $\$\backslash ((2k+1)^2\backslash )\$$ , et de même pour l'imagette de  X  correspondante. Comme les coefficients sont divisés par la norme du vecteur, ce sont des vecteurs unitaires. La corrélation croisée normalisée est alors leur produit scalaire, c'est-à-dire le cosinus de l'angle entre ces vecteurs, prenant au maximum la valeur 1, ce qui arrive quand les vecteurs sont identiques.

Bon, en réalité, cette technique n'est pas si pratique.

D'une part, pour pouvoir définir le template, j'ai dû chercher Charlie "à la main" avant de faire du template matching. D'autre part, si j'utilise ce même template dans un autre dessin d'un album d'Où est Charlie, je n'obtiendrai pas des résultats aussi convaincants. En effet, Charlie sera représenté différemment, par exemple avec une autre posture ou d'autres vêtements, et l'opérateur de corrélation croisée (normalisée ou non) est très sensible à ces variations ! 

Nous devons donc trouver un moyen d'obtenir un template plus générique. En d'autres termes, il faut formaliser les propriétés des éléments caractéristiques d'une classe d'images. C'est là qu'intervient la notion de features d'une image. 

Les features, ou zones d'intérêt d'une image

En vision par ordinateur, le terme de (local) features désigne des zones intéressantes de l'image numérique. Ces zones peuvent correspondre à des contours, des points ou des régions d'intérêt. A chaque feature détectée est associé un vecteur, appelé descripteur (feature descriptor ou feature vector), qui, comme son nom l'indique, décrit la zone concernée.

La résolution du problème d'image matching se fait alors en deux étapes :

1. Détecter et décrire les features dans chaque image

2. Trouver les paires de features qui se correspondent dans les deux images (features matching)

L'algorithme d'image matching étudie des images caractérisée par leurs features, donc la qualité des résultats dépend (entre autres) de la pertinence des features détectées. En ce sens, la première étape est fondamentale et ne doit en aucun cas être négligée. 

Un mauvais choix de features peut entraîner plusieurs difficultés dans l'étape de matching features :

• Problème 1 : deux images n'ont pas les mêmes features alors qu'elles représentent la même chose de manières différentes

• Problème 2 : ces deux images présentent les mêmes features, mais trouver les paires qui se correspondent est très difficile

Ces deux problèmes rendent le matching impossible et doivent donc être anticipés dès la première étape, lors de la détection et la description de features. Cela nous amène à la question suivante : 

Je vous avais introduit les features comme étant des zones intéressantes de l'image. Plus précisément, une zone constitue un bon choix de features si elle est :

1. Répétable : une feature doit se retrouver dans les images représentant la même scène malgré les différences géométriques et photométriques. Une feature doit donc présenter des propriétés d'invariance à ces transformations.

2. Distinctive : une feature  doit être suffisamment unique et non-ambiguë au sein d'une image pour faciliter le matching. Ce sont les informations contenues dans son descripteur qui doivent mettre en valeur sa particularité.  

3. Locale : une feature doit correspondre à une zone suffisamment petite, et elle est décrite selon son voisinage uniquement. Cela permet d'éviter les difficultés de matching dues aux phénomènes d'occlusion et de background clutter.

De plus, les features détectées doivent être nombreuses, mais l'effectif total doit être strictement inférieur au nombre de pixels de l'image afin que l'algorithme de matching soit efficace.

En résumé, une bonne feature doit être suffisamment unique pour pouvoir différencier deux classes d'images différentes, et suffisamment générique pour pouvoir reconnaître facilement les images d'une même classe malgré la diversité des représentations.