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 ([email protected]).