Le choix d'Alice
Reconnaissance de formes et stratégies visuelles

 
Pour des informations complémentaires, contacter les chercheurs, en cliquant ici Page précédente

Selon les psychologues, nous utilisons des stratégies visuelles. Les chercheurs du Laboratoire de statistique et probabilités1 et du Centre de mathématiques et de leurs applications2 s’intéressent à la vision artificielle et à sa modélisation. Les points de fixation du regard sur une image dépendraient de la tâche à accomplir et du contenu de l'image. Ils ne seraient pas les mêmes quand nous souhaitons par exemple être capables de mémoriser une scène, de vérifier si un objet donné figure dans une image ou de lire un texte. Tout se passe comme si nous interrogions l'image, par fixations successives, par saccades. Et la durée des saccades (entre un dixième et une demi seconde), ainsi que le pointage de l'œil, seraient optimisés en fonction du but à atteindre.

Nos stratégies visuelles intriguent les chercheurs en vision artificielle. Ils ont bien du mal à se rapprocher des performances humaines en reconnaissance de formes avec des rétines artificielles dont les qualités optiques sont pourtant au moins aussi bonnes que celles d'un œil.

Considérons le jeu des 20 questions ou jeu des personnages célèbres. Alice choisit un personnage célèbre. Bob doit deviner de quel personnage il s'agit en posant des questions comme «Est-ce un tel ?» ou encore «Est-il vivant ?». Auxquelles Alice répond sans mentir par «oui» ou par «non». Si Bob trouve en moins de 20 questions, il gagne. Il perd dans le cas contraire. Le problème mathématique sous-jacent est de déterminer la stratégie optimale pour Bob, c'est-à-dire, quelles questions poser, et dans quel ordre, pour gagner en posant un minimum de questions.

Le nombre moyen de questions que doit poser Bob est toujours au moins égal à une quantité fondamentale que l'on nomme l'entropie du choix d'Alice. C'est une mesure de l'incertitude dans laquelle est Bob ou encore de la quantité d'informations contenues dans le choix d'Alice.

Si, au lieu d'un personnage, Alice choisit un nombre entier compris entre 1 et 16 et que tous les nombres sont équiprobables, alors en moyenne 4 questions3 seront nécessaires à Bob, c'est la valeur de l'entropie. C'est aussi une valeur suffisante pour Bob. En effet, il peut procéder de la manière suivante : la première question est «inférieur ou égal à 4 ?». Si Alice répond oui, alors Bob demande «inférieur ou égal à 2 ?». Si la réponse est «non», alors Bob demande «inférieur ou égal à 6 ?», et ainsi de suite. Si maintenant, Alice a des nombres préférés, et que Bob le sait, alors il peut espérer être plus rapide en moyenne, l'entropie est plus faible. La stratégie optimale pour Bob est connue sous le nom de code d'Hoffman. Le nombre moyen de questions ne dépasse l'entropie que d'au plus une question. Et si les réponses d'Alice n'étaient plus uniquement «oui» ou «non» mais, «oui avec probabilité 3/5», «non avec probabilité 2/3»..., le pro-blème est plus compliqué. Il existe beaucoup de variantes, il faut définir précisément le modèle probabiliste sous-jacent mais dans tous les cas, il est naturel de s'intéresser à une stratégie simple pour Bob, la stratégie dite à 1 coup : à chaque instant, choisir la question qui réduit le plus, en moyenne, l'incertitude sur le choix d'Alice. Cette stratégie coïncide avec la stratégie optimale dans certains cas et en particulier dans l'exemple très simple présenté ci-dessus.

De manière surprenante, il existe des situations simples où cette stratégie est mise en défaut. En voici un exemple en vision artificielle. Soit une image numérique en niveaux de gris qui contient ou ne contient pas un visage. Une fois sur 1 000, elle en contient un, et 999 fois sur 1 000, elle n'en contient pas. Nous disposons de deux types de questions. Poser une question consiste à calculer une fonction, à valeur binaire (0 ou 1), des niveaux de gris de l'image. Le premier type, type A, prend la valeur 1, chaque fois qu'il y a un visage, mais une fois sur deux quand il n'y en a pas. Le second type de question, le type B, prend la valeur 1, chaque fois qu'il n'y a pas de visage, mais une fois sur deux quand il y en a un. Il y a autant de questions que nécessaire de type A et de type B. Imaginons un instant que nous ayons à jouer à ce jeu de nombreuses fois, il est clair que la première question doit être de type A, afin de ne pas laisser passer un visage les rares fois où il y en a un. Nous pouvons montrer que c'est effectivement la meilleure chose à faire même dans le cas où l'on ne joue qu'une seule fois. En revanche, la stratégie à 1 coup consiste à choisir pour première question une question de type B. En effet, 9 995 fois sur 10 000, celle-ci permet de diviser par 2 la probabilité que l'image contienne un visage.

En vision artificielle, les résultats obtenus par l'étude des jeux de Bob et Alice ont permis d'accélérer des algorithmes. Par exemple, pour extraire les routes dans les images de la Terre acquises par un satellite de télédétection ou encore pour localiser des visages dans des images.

Références :
• Model-Based Classification Trees. Donald Geman4, Bruno Jedynak. À paraître dans IEEE Transactions on Information Theory.
• An Active Testing Model for Tracking Roads in Satellite Images. Donald Geman, Bruno Jedynak. IEEE Transactions on Pattern Analysis and Machine Intelligence. Janvier 1996.
Efficient Focusing and Face Detection. Yali Amit, Donald Geman et Bruno Jedynak. Face recognition : from theory to applications, ed. H. Wechsler et al. NATO Asi Series F. Springer Verlag, Berlin, 1997.

Pour en savoir plus :
Consulter le site à l’adresse suivante :
http://www.inria.fr/multimedia/Videotheque-fra.html (taper jedynak).

1 CNRS-Université Lille 1.

2 CNRS-ENS Cachan.

3 = log 216 ou logarithme en base 2 de 16.

4 Donald Geman est chercheur associé au Centre de mathéma-tiques et de leurs applications (CMLA) de l’ENS de Cachan (geman@cmla.ens-cachan.fr).