Ce billet est un résumé de la communication présentée à GREC2009 en juillet 2009 :

• [2009,inproceedings] bibtex
  F. Morain-Nicolier, J. Landré, and S. Ruan, "Binary Symbol Recognition from Local Dissimilarity Map," in 8th International Workshop on Graphic Recognition (GREC2009), La Rochelle, France, 2009, pp. 143-148.
  @INPROCEEDINGS{Nicolier2009,
  author = {F. Morain-Nicolier and J. Landr\'e and S. Ruan},
  title = {Binary Symbol Recognition from Local Dissimilarity Map},
  booktitle = {8th International Workshop on Graphic Recognition (GREC2009)},
  year = {2009},
  pages = {143--148},
  address = {La Rochelle, France},
  month = {jul},
  url = {http://pixel-shaker.fr/wp-content/uploads/publications/Nicolier2009.pdf} }

Introduction

Dans des travaux antérieurs ¹, avec Étienne Baudrier, nous avons proposé une mesure de dissimilarités locales entre images binaires. Cette mesure permet de localiser et de quantifier les différences entre deux images. Un des derniers résultats de la thèse d'Étienne fut d'obtenir une formule rapide de la Carte de Dissimilarités Locales (CDL):

$\mathrm{CDL}_{A, B} (p) = |A (p) - B (p) | \max (\mathrm{dt}_A (p), \mathrm{dt}_B (p))$

où $\mathrm{dt}_X$ est la transformée en distance de l'image $X$. Je montre que cette formule peut être linéarisée en :

$\mathrm{CDL}_{A, B} = B \mathrm{dt}_A + A \mathrm{dt}_B .$

Cette formulation est particulièrement intéressante puisque les opérateurs $\max$ es $\mathrm{abs}$ sont éliminés. Ce qui permet une implémentation très rapide dans le domaine de Fourier et ouvre la voie à la localisation de motifs.

Comment appliquer la CDL à la reconnaissance de symboles

Le problème est de choisir dans une bibliothèque de modèles, celui qui ressemble le plus à une image donnée. La solution retenue ici est de construire un scalaire représentatif de la dissimilarité entre $I$ et $M$ (un des modèles), puis de choisir le modèle dont la dissimilarité est la plus faible. Le scalaire est calculé par une somme des valeurs de la CDL:

$\sum_p CDL^{}_{I, M} (p)^{} = \sum_p M(p) \mathrm{dt}_I(p) + \sum_p I(p) \mathrm{dt}_M(p).$

Cette équation peut être interprétée comme un Chamfer Matching (CS) symétrique. Le Chamfer Score :

$\mathrm{CS}(I, M) = \frac{1}{N} \sum_p M(p) \mathrm{dt}_I(p)$

mesure comment l'image I est dissimilaire au modèle M. Autrement dit, c'est une mesure de la ressemblance de I à M. Une comparaison des équations du CS et de la somme des valeurs de la CDL montre que la mesure globale est une mesure de :

• la ressemblance de I à M,
• et de la ressemblance de M à I. La mesure globale est symétrique, mais l'introduction de pondérations permet d'obtenir une mesure flexible, la Mesure de Dissimilarités Globale (MDG) :

$\mathrm{MDG}(I, M) = \alpha \sum_p M(p) \mathrm{dt}_I^2(p) + \beta \sum_p I(p) \mathrm{dt}_M^2(p).$

Des sommes quadratiques sont employées pour améliorer la détection. Le choix des facteurs $\alpha$ et $\beta$ dépend de la mesure qui est nécessaire. Une mesure symétrique est obtenue si $\alpha = \beta$. Cette introduction possible d'asymétrie dosée permet d'obtenir une mesure se rapprochant de certains résultats de psychologie (voir Tversky entre autres).

Reconnaissance robuste aux changements d'échelle et d'orientation par estimation log-polaire

La mesure proposée n'est effective qu'avec des symboles de taille et d'orientation comparables. La CDL est une mesure robuste aux petites variations. Elle n'est donc robuste qu'au petits changements d'échelle et d'orientation. Pour comparer des symboles quelconques, une estimation de la déformation est réalisée dans le plan log-polaire. Ce recalage permet d'obtenir les paramètres d'homothétie et de rotation. Un recalage permet alors d'aligner les deux symboles au mieux.

L'algorithme final complet

1. Calculer Ilp la représentation log-polaire de I.
2. Pour chaque modèle M :
   • calculer Mlp la représentation log-polaire de M,
   • estimer les paramètres de déformation entre Ilp et Mlp
   • effectuer le recalage de M
   • calculer la dissimilarité MDG entre I et le modèle recalé.
3. Choisir le modèle avec la dissimilarité la plus faible.

Cet algorithme est efficace (mais pas partout)

Cette méthode est testé sur la base de symboles du grec2005 international symbol recognition contest. Six dégradations différentes sont disponibles. La série utilisée comporte 50 images contenant un symbole à reconnaître parmi 50.

Quelques (bons) exemples de recalage

Exemple de symbole recalé sous la dégradation n°1

Exemple de symbole recalé sous la dégradation n°2

Exemple de symbole recalé sous la dégradation n°3

Exemple de symbole recalé sous la dégradation n°4

Exemple de symbole recalé sous la dégradation n°5

Exemple de symbole recalé sous la dégradation n°6

Quelques résultats qui montrent que l'algortithme n'est pas très efficace s'il faut recaler

Taux de réussite :

• Si les symboles sont de taille et orientation comparable, la méthode est très efficace. Dans le contest la meilleure performance pour la déformation 6 est de 59.81%. Les scores que nous obtenons sont donc intéressants.
• Dans le cas de rotations/homothéties plus conséquentes les scores sont assez variés, parfois bons parfois mauvais. La cause d'échec est le plus souvent un mauvais recalage, ce qui compromet forcément la comparaison qui suit.
• Aucune hypothèse n'est nécessaire sur les symboles et aucune segmentation n'est nécessaire.

Discussion et travail à fournir

• Je considère que la validité de la mesure de dissimilarité est faite puisque les performances sont mauvaises dans le cas où le recalage n'est pas bon.
• Cependant pour le moment cette mesure n'est toujours pas robuste aux grands changements d'échelle et de rotation. Il faut étudier plus précisément la robustesse à ces changements. Il serait ainsi efficace d'évaluer l'erreur en fonction d'une variation d'échelle ou de rotation, pour déterminer la variation de rotation (ou d'échelle) supportable. Un nombre de patrons suffisant pourrait alors être déterminé. Est-ce que cette variation supportable dépend du contenu de l'image?
• Une piste temporaire sera de tester la mesure de dissimilarité entre les deux images, directement dans le plan log-polaire, pour éviter l'étape de recalage.
• Une formule rapide et flexible de la mesure de (dis)similarité entre deux images a été obtenues, locale ou globale. Il reste à étudier l'influence et l'efficacité du choix de pondération plus graduée. Par exemple $\alpha = 0.1$ et $\beta = 0.9$. Mon idée est que la robustesse au bruit risque de varier avec ces poids.

FMN.

1.

• [2008,article] bibtex
  E. Baudrier, F. Nicolier, G. Millon, and S. Ruan, "The Adaptative Local Hausdorff-Distance Map as a new Dissimilarity Measure," Pattern Recognition, vol. 41, iss. 5, pp. 1461-1478, 2008.
  @ARTICLE{Baudrier2008,
  author = {E. Baudrier and F. Nicolier and G. Millon and S. Ruan},
  title = {The Adaptative Local Hausdorff-Distance Map as a new Dissimilarity Measure},
  journal = {Pattern Recognition},
  year = {2008},
  volume = {41},
  pages = {1461--1478},
  number = {5},
  month = {may},
  url = {http://pixel-shaker.fr/wp-content/uploads/publications/Baudrier2008.pdf} }