| |
La reconnaissance des formes à l'épreuve des faits
mensuel 312
daté septembre 1998 - 
Née avec les ordinateurs, l'intelligence artificielle vise à reproduire les facultés humaines les plus élevées. Moins ambitieuse, la reconnaissance des formes se limite à la simulation des capacités humaines de perception, visuelles ou auditives. Force est de reconnaître que ces deux disciplines scientifiques n'ont pas tenu leurs promesses initiales. Les résultats ont longtemps tardé à sortir des laboratoires et à se manifester dans la vie quotidienne. Pourquoi ? Le développement récent d'un système industriel éclaire les obstacles, conceptuels et pratiques, qui se dressent sur le chemin des applications. Ce système est opérationnel dans un domaine particulièrement sensible aux erreurs d'interprétation : la reconnaissance des montants manuscrits sur les chèques bancaires !
Que signifie une loi physique ? En quoi explique-t-elle un phénomène, comment le prévoit-elle ?
Depuis Galilée, les mathématiques sont censées expliquer le monde et, à l'évidence, de très grands succès ont été obtenus par leur application dans tous les domaines de l'étude de la nature. On sait que, le plus souvent, des équations différentielles ou aux dérivées partielles sont au coeur de ces réussites. Et l'on sait également qu'il reste toujours à en calculer les solutions !
Dans les années 1940-1950, les ordinateurs ont été créés pour cela même. Bien que binaires, on s'aperçoit qu'ils permettent d'effectuer n'importe quelle opération d'analyse numérique. Mais, plus fondamentalement, ils sont capables de transformer toute chaîne de caractères en une autre chaîne de caractères par des « algorithmes », qu'on peut écrire dans des programmes et mettre en oeuvre avec des ordinateurs. De fait, cette faculté ouvre la voie à des modélisations inédites.
Aujourd'hui, avec les progrès inouïs des machines informatiques, nous voyons naître des modèles du deuxième type, appelés ainsi par opposition aux modèles mathématiques ou aux modèles de l'analyse numérique. Ces modèles, représentés par des programmes mettant en oeuvre des algorithmes, ne sont en rien des applications numériques de formules ou d'équations. Ils ont une existence propre, quasi indépendante de la culture de la physique mathématique, et ils permettent tout aussi légitimement d'expliquer ou de simuler des phénomènes naturels. Ils ont acquis droit de cité là où les mathématiques ne sont quasiment d'aucune aide, en biologie, en linguistique et, pour ce qui nous intéresse ici, en reconnaissance des formes. En 1966, dans la nouvelle formule d' Atomes , journal auquel a succédé La Recherche , j'avais exposé l'intérêt d'étudier et de construire des « opérateurs » de reconnaissance, matérialisés par des programmes exécutables par ordinateur1. L'énoncé du principe est simple : recueillir les données d'un capteur, c'est-à-dire une représentation le signifiant, et en obtenir une ou des interprétations les signifiés par l'exécution d'algorithmes. Le but ultime est la reproduction des capacités humaines de perception, visuelles ou auditives. Contrairement aux prévisions optimistes des pionniers de l'époque, dont je faisais partie, les problèmes ainsi posés se sont pourtant révélés très coriaces. Certains détracteurs ont même été jusqu'à affirmer l'impossibilité de les résoudre !
Dans ce domaine, comme dans bien d'autres, la preuve ultime de la validité des idées et des recherches et de leur intérêt se trouve dans la résolution d'un problème « réel », par opposition à celle d'un problème « d'école » restant confinée dans les laboratoires. La physique nucléaire aurait-elle connu un tel développement sans le bruit de la bombe et les centrales nucléaires ? Toute proportion gardée, la saisie industrielle par programme des montants de chèques n'est-elle pas une preuve de la validité des idées en matière de reconnaissance des formes ?
Dès son irruption sur la scène scientifique, l'intelligence artificielle avait affiché de hautes ambitions : reproduire avec des moyens informatiques toutes les facultés humaines, y compris les plus élevées, telles que le raisonnement logique, la compréhension du langage et le comportement. Moins ambitieuse, la discipline scientifique de la reconnaissance des formes RdF - Pattern Recognition, en anglais s'est développée depuis la fin des années 1960, en même temps que l'intelligence artificielle IA, et ceci au fur et à mesure de l'augmentation de la puissance et des capacités de mémoire des ordinateurs. Très tôt, dès le début des années 1970, les deux disciplines se sont séparées. Le fait était aussi regrettable qu'inévitable, étant donné les origines différentes des chercheurs de chaque domaine : les premiers IA provenaient des mathématiques tandis que les seconds RdF étaient en majorité des physiciens et des ingénieurs2. Malgré de nombreux efforts des uns et des autres, les résultats des premiers programmes d'IA ou de RdF se sont révélés très éloignés des performances humaines ou même animales. Pourquoi ? Nous avons souligné qu'une machine informatique programmable - un ordinateur - est capable d'opérer n'importe quelle transformation d'une donnée de départ, la représentation, en une image d'arrivée, une interprétation. C'est une machine « universelle » et elle est opérationnelle, c'est-à-dire qu'elle donne un résultat concret : une image, un texte, des chiffres. Toutefois, cette généralité se paye par des contraintes importantes : le volume de mémoire, le temps de calcul. Tout algorithme, en particulier un opérateur de reconnaissance, est en effet caractérisé par une complexité de calcul Ofn*, nombre d'opérations à effectuer en fonction du volume n des données d'entrée. La plupart des algorithmes utilisés en RdF sont exponentiels, leur complexité varie en Oean, ce qui les rend vite impraticables si n est un peu grand, quelle que soit la puissance de calcul et de mémoire à disposition.
Comment échapper à cette complexité ? On dispose de trois possibilités, non exclusives l'une de l'autre :
1. diminuer n, c'est-à-dire avoir affaire à des sous-images, donc à des sous-problèmes ;
2. décomposer le processus global de décision en niveaux multiples de décision ;
3. utiliser des opérateurs qui ne sont pas exponentiels, mais polynomiaux, en particulier linéaires. Ce faisant, on introduit nécessairement des erreurs mais, idée essentielle, on échange de la précision pour de la rapidité.
Toute opération de reconnaissance de formes s'organise ainsi selon des niveaux successifs fig. 1. A chaque niveau, une opération concrète permet de passer d'une représentation à une ou plusieurs interprétations, lesquelles vont constituer la représentation du niveau suivant. Chaque interprétation est plus abstraite, donc plus générale, et ce qui est gagné en abstraction est perdu en localisation. Avec un peu d'audace, on verrait là une analogie avec les relations d'incertitude de la physique quantique.
Les opérations de RdF apparaissent chaotiques, c'est-à-dire qu'une variation très petite de la donnée de départ peut faire basculer l'interprétation d'une décision à une autre. Ceci distingue particulièrement ces simulations, accomplies par ces opérateurs informatiques, de la perception humaine dont chacun sait, par expérience, qu'elle tolère des bruits et des déformations très importants. Pour éviter ce caractère chaotique, notre pratique nous a appris à introduire du « continu » là où l'algorithmique impose du « discret ». Faut-il s'en étonner si l'on se souvient que l'on tente en fait de simuler des processus analogiques* à l'aide de machines qui, par construction, sont d'essence binaire ?
Un caractère essentiel des décisions des différents niveaux est donc de ne pas conclure tout de suite par « vrai ou faux », mais d'affecter chaque possibilité de décision d'un coefficient de vraisemblance. Il s'agit d'entretenir l'ambiguïté sur l'interprétation et, autant que faire se peut, de retarder la décision définitive. Pour obtenir un optimum, une autre leçon de l'expérience consiste à utiliser, pour une même interprétation, plusieurs opérateurs de RdF élaborés selon des principes différents. Chacun fournit un résultat qui, pris isolément, est le plus souvent peu informatif, mais c'est leur combinaison qui devient pertinente. D'où d'intenses travaux visant à trouver la meilleure façon de combiner les données produites par ces opérateurs. En fait, il semble qu'une simple combinaison multiplicative de leurs résultats - l'addition des logarithmes, ce qu'en physiologie on appelle la loi de Fechner - soit voisine de l'optimum.
On souhaiterait bien sûr que de tels opérateurs puissent être créés par apprentissage automatique à partir de bases de données réelles. Malheureusement, cette direction de recherche n'a pas donné de résultats satisfaisants. Dans la pratique, les opérateurs de RdF sont le plus souvent programmés « à la main », suivant l'intuition et l'imagination du reconnaisseur. Seuls les réseaux de neurones* présentent une solution générale intéressante, mais leur mise en oeuvre est relativement lourde3.
On ne peut s'empêcher de rapprocher ces descriptions de ce que nous savons du cortex visuel humain : existence de couches multiples, multiplicité des neurones. Là s'arrêtent malheureusement les analogies : un cerveau n'est pas un ordinateur dans lequel on peut implanter un programme et, heureusement pour nous, ses opérations ne sont pas chaotiques...
Parmi les activités humaines, la perception visuelle ou auditive est un automatisme, en ce sens que nous ne pouvons la contrôler, au contraire par exemple des mouvements corporels ou de la pensée. Peut-on s'empêcher de reconnaître un objet visible ? Dans l'évolution du vivant, ces capacités essentielles sont arrivées très tôt les insectes sont de parfaits automates visuels par exemple, bien avant le contrôle volontaire. Ce dernier provient-il effectivement de l'addition, au cours de l'évolution, de niveaux similaires à ceux que nous avons décrits ? Là réside peut-être la cause des échecs répétés de l'intelligence artificielle, dont le paradigme s'inspire de la logique formelle, en particulier de la démonstration de théorème. Il suffisait, pensait-on, de trouver les règles logiques et d'appliquer des techniques inductives ou déductives pour simuler les activités humaines de traitement de l'information. Dans la réalité, à cause de leur caractère chaotique, les « systèmes experts » se révèlent inutilisables en dehors de cas d'école ou d'applications très limitées. Inspirée par la physique et l'expérimentation plus que par les mathématiques et les idées a priori, la RdF a pris une voie différente, largement expérimentale4. Peut-être suffisait-il d'écouter les leçons de l'ontogenèse pour se convaincre que la modélisation de l'humain passait d'abord par celle des facultés perceptives, et non par celle de la pensée logique ?
Comment parvient-on à résoudre un problème particulier de RdF, la reconnaissance de l'écriture manuscrite et, plus précisément, celle des chiffres et des lettres, mots et phrases sur les chèques bancaires ? Au départ, un capteur d'image - un réseau de diodes - fournit une matrice bidimensionnelle de valeurs numériques - une image dite « de niveaux de gris ». Chaque valeur correspond à la luminosité d'une petite zone.
Le terme de pixel* correspond à la fois à la zone en question et à sa valeur. Fixant un seuil, une image bitonale ou binaire s'en déduit en affectant un 1 aux valeurs supérieures à un seuil, un 0 aux valeurs inférieures. Cette opération de binarisation se fait soit au niveau du capteur lui-même, soit par programme.
Une valeur 0 ou 1 demande évidemment moins de mémoire d'ordinateur - un bit - qu'une valeur numérique de 64 niveaux 5 bits, ou 256 niveaux 7 bits. A titre d'exemple l'image d'un écran de PC demande environ un million de pixels. Pour la garder en mémoire, 1 Mo méga-octet est nécessaire. En général, la représentation d'un document écrit demande 200 dpi dots per inch ou 8 pixels/mm, soit environ 90000 pixels pour un chèque. Les contraintes de mémoire et de transmission amènent à représenter les images de chèques en binaire. Toutefois, l'opération de binarisation est délicate et, située en début de chaîne, elle comporte des défauts ayant des conséquences importantes sur l'ensemble du traitement. Dans le principe, il serait donc préférable de traiter des images primaires en « niveaux de gris » plutôt qu'en binaire. Mais l'opération se révèle encore trop coûteuse pour être réalisée industriellement.
Après binarisation de l'image, le traitement des informations met en oeuvre, à chaque niveau, deux principes qui se sont dégagés au cours de nos recherches : la segmentation-reconnaissance et le principe de régularité-singularité.
Nous avons indiqué la nécessité de segmenter les images en sous-images. Ainsi, sur un chèque, le montant numérique doit être segmenté en chiffres, le montant littéral en mots, les mots en lettres. Parfois, la segmentation est clairement définie : les objets à reconnaître sont connexes et séparés les uns des autres. Mais souvent ce n'est pas le cas. Il faut choisir entre différentes hypothèses de segmentation : elles sont évaluées en probabilités a priori et a posteriori par la reconnaissance de l'élément segmenté, y compris la non-reconnaissance « ce n'est pas une lettre », « ce n'est pas un mot ».... La segmentation implique la reconnaissance et inversement : les deux opérations ne sont pas séparables.
Que signifie notre second principe, la régularité-singularité ? Pour l'illustrer, plaçons-nous dans un autre domaine, celui de la reconnaissance de la parole. D'une façon générale, il est possible de décomposer un signal de parole en régions périodiques, qui correspondent aux voyelles. Celles-ci sont faciles à reconnaître : elles constituent les parties régulières du signal. En revanche, les consonnes, « accidents » des voyelles, sont les parties singulières, dont l'expérience montre qu'elles sont difficiles à localiser et identifier. L'idée consiste à détecter en priorité les parties régulières et à les retirer du signal. Il reste ainsi les parties singulières, bien localisées, et donc plus faciles à reconnaître. De même, pour une écriture, un mot manuscrit, mal et rapidement écrit, se réduit à une oscillation autour de l'horizontale, signal périodique, comparable aux voyelles de la parole bien que sans contenu en information utile fig. 2. Les « accidents » de cette partie régulière sont les parties singulières de l'écriture : ascendants, descendants, boucles, ligatures. La mise en oeuvre de ce principe est illustrée sur la figure 3 : la partie supérieure montre l'image d'origine et, en dessous, s'affiche la décomposition en parties singulières, que nous appelons les graphèmes, alternativement en blanc et en noir, après suppression de la partie dite régulière. D'une façon générale, un chiffre ou une lettre quelconque est constituée d'un à trois graphèmes. Ces graphèmes représentent les formes primitives de premier niveau.
La figure 4 donne le schéma général d'un système de reconnaissance d'un montant de chèque :
1. l'image bitonale du montant en chiffres est localisée l'absence de norme française sur sa position ne facilite pas la tâche et le fond est « nettoyé », c'est-à-dire qu'on ne retient que les traits identifiés comme tels par les programmes ;
2. les chiffres sont reconnus ; une liste de montants, ordonnés en valeurs de vraisemblance décroissantes, est obtenue ;
3. Si la valeur de vraisemblance de la tête de liste est suffisamment élevée, ce montant est retenu ; si cette valeur est trop faible, le chèque est rejeté et proposé à un observateur humain. Entre les deux valeurs seuils, on met en route la reconnaissance du montant littéral, nécessairement plus coûteuse en temps calcul ;
4. L'image du montant littéral est alors à son tour localisée et nettoyée ;
5. Le montant littéral est segmenté ; les mots sont reconnus. Une liste de montants, ordonnés en valeurs de vraisemblance décroissantes, est dressée ;
6. Combinant les informations indépendantes recueillies sur les chiffres et les lettres, on aboutit à une nouvelle liste de montants. Si une valeur de vraisemblance dépasse le seuil admissible, le montant est adopté ; sinon l'image du chèque est proposée à un opérateur humain.
Précisons quelques détails de ce processus. Que ce soit pour les chiffres ou les lettres, après l'extraction et le nettoyage du fond, les images binaires sont normalisées en taille et en inclinaison les écritures penchées sont redressées. Pour les lettres, la nature « imprimés ou bâtons » par rapport à « manuscrits » est détectée en France 20 % des chèques sont imprimés. Si l'écriture est manuscrite, une zone de lettres ne comportant ni partie ascendante ni partie descendante est déterminée : elle donne une information importante sur la nature des lettres « ce n'est probablement pas un b, ni un d, ni un p, etc. ». Enfin, on établit un graphe, c'est-à-dire une description d'un ensemble de points reliés entre eux par des traits fig. 5. Ce graphe est utilisé pour trouver les parties régulières, et donc, par complémentarité, les graphèmes, point essentiel de notre technique. A chaque étape, sont mis en oeuvre divers opérateurs de reconnaissance faisant appel à des techniques multiples mentionnons-les pour mémoire : classifieur de Bayes, silhouettage corrélation, programmation dynamique, automates probabilisés, Hidden Markov Models, réseaux de neurones. C'est à ce prix qu'on parvient à augmenter le résultat moyen final et à diminuer le caractère inévitablement chaotique de la programmation. Les opérateurs sont optimisés par un apprentissage statistique, en utilisant des bases d'images de chèques pour lesquels on dispose du montant saisi. Ces bases doivent être aussi larges que possible. Ainsi, pour la mise au point adaptative des réseaux de neurones du montant littéral, nous avons dû faire appel à 100 000 images de chèques. Un tel chiffre est nécessaire parce que la fréquence d'apparition des mots cent, mille, sept... est très inégale. Pour l'apprentissage du réseau de neurones de reconnaissance des caractères, il a fallu exploiter jusqu'à 400 000 exemples !
Là également diverge l'analogie avec les mécanismes humains. Si apprendre à lire demande beaucoup de temps, il suffit de présenter un seul exemple de caractère à un lecteur normal, pour qu'il soit capable de le reconnaître sous une infinité de représentations : la base d'apprentissage semble vraiment minimale. Sur une seule image de chèque, l'erreur de lecture d'un opérateur humain est très faible. Cette remarquable stabilité n'est malheureusement pas atteinte par notre système qui, en dépit des efforts accomplis, affiche un comportement parfois erratique sur une image isolée. Les taux de reconnaissance ne deviennent stables que sur un très grand nombre de chèques : par exemple, sur 1 000 chèques, la fluctuation des résultats peut dépasser 10 %. En revanche, sur des échantillons d'au moins 100 000 images de chèques, le taux de reconnaissance absolument stable est de l'ordre de 70 %, avec un taux d'erreur de 1 % voisin de celui des opérateurs humains. Ces performances sont atteintes dans un environnement industriel quotidien par un système Interchèque , de la société A2iA qui, pour fixer les idées, est constitué par une centaine de milliers de lignes de code, écrites en langage C, et s'exécute sous Windows NT 4.0 sur de simples PCs.5
Au terme de cette description, le lecteur aura peut-être l'impression qu'on lui a présenté les résultats d'un « bricolage », certes habile mais très spécifique. Et il aura raison ! Mais il se souviendra aussi que, selon François Jacob, le bricolage n'est pas étranger aux phénomènes de l'évolution du vivant : leur simulation devrait-elle l'être ? De fait, ce système de reconnaissance de l'écriture manuscrite sur des chèques bancaires n'a rien de générique. Il est spécifiquement adapté à cette tâche, même si sa conception a été guidée par les idées et les principes généraux que nous avons évoqués. Au-delà de cet exemple, il nous semble ainsi que s'ouvrent des perspectives de modélisation constructive de la vision et, plus largement, de la compréhension de nos mécanismes perceptifs, tout en restant conscient des différences considérables entre un ordinateur programmé et un cerveau. Jusqu'à présent, l'explication de la perception et des interprétations des sens était largement « philosophique ». Si une immense quantité de recherches a été faite par les physiologistes de la vision et de l'ouïe, nous savons peu de choses sur le fonctionnement du cerveau en tant que système d'information. D'où d'innombrables discussions sur ce qu'il faut entendre par le sens, c'est-à-dire l'interprétation d'un message extérieur. Sans prétendre que nos algorithmes « expliquent » la vision humaine, on peut penser que ce type de démarches introduit la méthode expérimentale dans un domaine dont l'état empirique rappelle celui de la médecine au début du XIXe siècle, avant que Claude Bernard y introduise la méthode expérimentale.
La science fait affecter des budgets gigantesques à des domaines tels que l'espace, la physique des particules, l'astrophysique, pour des retours que l'on peut parfois estimer minimes. En comparaison, les études qui concernent les mécanismes humains de compréhension et d'interprétation ne sont pratiquement pas soutenues alors que leur intérêt pour comprendre l'homme est extrême. Qu'est-ce que « communiquer » sinon interpréter des représentations ? Continuerons-nous à appréhender ces sujets avec la culture du passé ? En liaison avec les physiologistes, la voie de l'explication par la modélisation est ouverte. Comme l'a dit le prix Nobel Francis Crick, « il n'y a pas d'étude scientifique plus vitale pour l'avenir de l'homme que l'étude de son propre cerveau. Toute notre conception de l'Univers en dépend » .
1 J.-C. Simon, Atomes, 231 , 157, avril 1966.
2 R.O. Duda et P. Hart, Pattern Classification and Scene Analysis , Wiley Interscience 1974 ; K. Fukunaga, Pattern Recognition , Academic Press, 1972.
3 C.M. Bishop, Neural Network for Pattern Recognition , Oxford University Press, 1995.
4 J.-C. Simon, La Reconnaissance des formes par algorithmes , Masson, Paris, 1984.
5 S. Knerr et al ., The A2iA Intercheque System : Courtesy Amount and Legal Amount Recognition for French Checks, International Journal of Pattern Recognition and Artificial Analysis, vol. 11, n°4, 505-548, 1997.
NOTES
*O fn correspond à la partie dominante de la fonction fn quand n croît infiniment.
*Un signal est dit ANALOGIQUE s'il transcrit de façon continue, par une relation de proportionnalité, le message dont il est porteur. Les disques vinyles, par exemple, sont gravés par des procédés analogiques. En revanche, on sait que les disques compacts font appel à des procédés numériques où l'information est codée de façon discontinue, le signal étant représenté par une succession de 0 et de 1.
*Les RÉSEAUX DE NEURONES formels, inventés en 1943, n'ont que de très lointains rapports avec ce que l'on sait aujourd'hui du fonctionnement des neurones cérébraux. Schématiquement, un neurone formel est doté d'un nombre n d'entrées affectées chacune d'un poids ai i=1 à n, et d'une sortie S. Une mesure xi se présente sur chaque entrée : S vaut 1 si la somme des ai xi est supérieure à un seuil, 0 dans le cas contraire. La théorie des neurones formels porte sur l'assemblage de telles entités et sur les mécanismes d'apprentissage des poids ai.
*Un PIXEL est le résultat de mesure d'intensité donné par un capteur d'image - une diode par exemple - dans une petite surface ou un petit angle solide. C'est un échantillon d'amplitude. Regardant à la loupe une photo imprimée dans un journal, on voit qu'elle est constituée de tels éléments isolés dans des petits carrés. Si l'amplitude est 0 ou 1, on dit que le pixel - I'image - est binaire ou bitonale, sinon qu'elle est « en niveaux de gris ».
DOCUMENT larecherche.fr LIEN |
