Le mot d'interprétation signifie dans le cas qui nous occupe une simple catégorisation du phénomène perçu, c'est-à-dire son affectation à une famille de phénomènes ressemblants; autrement dit, son identification par comparaison avec des phénomènes analogues conservés en mémoire.
La reconnaissance des formes a donc pour objet général, d'une part de capter et de décrire en mémoire des formes, c'est-à-dire les manifestations de l'univers extérieur auxquelles la machine a été rendue sensible et, d'autre part, de prendre sur la représentation mémoire ainsi obtenue une décision d'identification par référence à un ensemble d'apprentissage décrit dans une représentation analogue.
La partie essentielle est évidemment le choix de cette représentation mémoire; celle-ci doit être à la fois assez informative pour permettre une bonne précision à l'identification et assez condensée pour éviter une inutile redondance qui se traduirait par un temps de calcul exagéré au moment de la décision.
Le choix de l'espace de représentation dans lequel les formes vont être codées est un des facteurs les plus importants dans la réalisation d'un tel système. On devra le déterminer en fonction de deux paramètres souvent contradictoires: l'exactitude et la précision de la représentation choisie d'une part, ses possibilités mathématiques et algorithmiques d'autre part.
La difficulté vient souvent de ce que plus l'espace de représentation est proche de la réalité des phénomènes et moins il a de propriétés facilitant la décision; réciproquement, un espace de représentation possédant de fortes possibilités de calcul (une métrique, ou un algorithme rapide) est souvent peu adapté aux problèmes réels particuliers qu'il faut traiter. Le compromis doit donc être établi soigneusement, et pour cela, il importe de bien connaître les propriétés des espaces de représentation où l'on situe le problème.
L'emploi de l'ordinateur permet de se délivrer des contraintes de type mathématique (on peut calculer approximativement l'intégrale d'une fonction sans en avoir la primitive) et autorise des manipulations formelles sur des symboles abstraits dont la signification réelle n'importe plus (récritures, parcours d'arbres, etc.).
On a donc une grande latitude dans les opérations, sous la contrainte que celles-ci soient réalisables en un temps de calcul raisonnable (en pratique, de complexité au plus polynômiale par rapport aux données). Les propriétés des espaces de représentation peuvent donc être exploitées au mieux grâce à la puissance et à l'adaptabilité des calculs sur ordinateur.
Une distance pourra, dans un tel espace, être calculée non pas par une formule (du type de celle qui définit la distance euclidienne, par exemple), mais par une procédure algorithmique non formulable en équations, tenant compte par exemple d'une hiérarchie ou d'un ordre dans les coordonnées.
Avant d'entrer plus avant dans les détails des propriétés de ces espaces de représentation, indiquons d'abord quelques sujets actuels d'application de la reconnaissance des formes, et quelques unes des performances atteintes.
Le traitement du signal fournit des paramètres très utilisables pour pousser plus loin l'analyse, et décider quel est le signal émis, en fonction d'un répertoire de signaux possibles. Un exemple très spectaculaire, promis à un grand développement, est celui de la reconnaissance de la parole. Pour l'instant, les machines commercialisées reconnaissent des mots (ou des suites de quelques mots), pris dans un vocabulaire limité à quelques dizaines d'éléments... Des prototypes de laboratoire sont capables de tenir compte de la syntaxe et de maîtriser un vocabulaire raisonnablement étendu (quelques milliers de mots). On estime que d'ici à une dizaine d'années, les machines capables de comprendre la parole humaine auront des performances suffisantes pour être utilisables dans des tâches complexes (interrogation de bases de données, acquisition de connaissanes spécialisées, etc.).
Un autre domaine extrèmement utile est celui des signaux biomédicaux; la reconnaissance des formes permettrait d'automatiser ou de simplifier des tâches à la fois très complexes et très répétitives, comme un dépouillement d'électro-encéphalogramme, ou encore d'assurer une surveillance automatique sur des mesures prises en temps réel. Un grand nombre d'études sont en cours dans ce vaste domaine, et déjà certains systèmes sont implantés en laboratoire hospitalier.
Si l'on quitte les signaux physiologiques, la reconnaissance des formes s'intéresse aussi aux mesures de signaux d'origine artificielle: surveillance de machine, interprétation d'échos, etc.. Un bon exemple est la détection d'objets sur signal radar.
Un grand nombre d'images proviennent du domaine de la robotique, en particulier industrielle: reconnaissance de pièces pour saisie, par exemple. L'analyse des paysages est également très utile (photos aériennes, guidage en temps réel d'engins, etc.).
La reconnaissance d'objet, ou la détection d'éventuelles ressources sur les photographies prises par des satellites font également l'objet d'un très grand nombre d'études.
L'extraordinaire variété des domaines d'application de la reconnaissance des formes explique la vitalité de cette discipline. Les revues citées en bibliographie publient de nombreux exemples pratiques; les quelques cas illustratifs proposés au chapitre 6 montrent également la variété des sujets traités par les techniques de type structurel. A ce propos, examinons maintenant les deux grandes méthodologies utilisées: l'approche dite statistique et l'approche dite structurelle.
Une approche classique en reconnaissance des formes est fondée sur l'étude statistique des mesures que l'on a effectuées sur les objets à reconnaître. L'étude de leur répartition dans un espace métrique et la caractérisation statistique des classes permet de prendre une décision de reconnaissance du type "plus forte probabilité d'appartenance à une classe". Ces méthodes s'appuient en général sur des hypothèses (explicites ou non) concernant la description statistique des familles d'objets analogues dans l'espace de représentation.
Dans cette approche, on supposera donc que les mesures faites sur une forme peuvent s'exprimer sous la forme d'un vecteur X={x1xn} de l'espace Rn. On dispose d'un ensemble d'apprentissage, c'est-à-dire d'un jeu de tels vecteurs dont on connaît en plus la classe d'appartenance. Le problème peut alors se résumer sommairement de la façon suivante: étant donné un vecteur inconnu, obtenu par mesures sur une forme, trouver la classe à laquelle on doit l'affecter; autrement dit, reconnaître la forme reconnue en fonction de l'apprentissage effectué. Graphiquement, pour n=2, un tel problème peut être représenté par la figure 1. Dans cette figure, le point représenté par X appartient-il à la classe 1, à la classe 2, ou à la classe 3 ?
Avant de voir quelles techniques employer pour résoudre ce problème de décision, revenons un moment sur l'apprentissage. La situation décrite jusqu'ici est idéale, puisqu'on suppose connaître à priori le nombre de classes, et en plus avoir déjà décidé la classe de certains points (ceux de l'ensemble d'apprentissage).
En pratique, le problème n'est pas toujours aussi bien posé. Les classes "naturelles" perceptives (par exemple les sons élémentaires de la parole) peuvent se révéler peu adaptées à l'espace de représentation choisi; elles peuvent se recouvrir, ou mal décrire l'ensemble d'apprentissage. Pour les redéfinir au mieux, on peut s'aider de méthodes d'apprentissages automatiques ou semi-automatiques. Dans ce domaine, la Reconnaissance des Formes a bénéficié des travaux de l'analyse de données: d'une part pour les algorithmes d'inspection et de manipulation de données dans les espaces multidimensionnels (analyse en composantes principales, analyse discriminante, etc.), d'autre part pour la séparation même en classes d'un nuage de points par classification automatique (hiérarchique, ou globale, comme la méthode des nuées dynamiques). D'une façon générale, les méthodes d'analyse statistique des données sont donc très utiles pour l'aide à l'apprentissage en reconnaissance des formes (on peut mentionner également ici les techniques de sélection de paramètres ou la transformation de Karhunen-Loeve).
Si l'on suppose l'apprentissage réalisé, on peut revenir au problème de la décision tel qu'il a été formulé précédemment. On distinguera d'une façon générale deux grands types de méthodes: les méthodes dites non paramétriques, où l'on cherche à définir les frontières des classes dans l'espace de représentation, de façon à pouvoir classer le point inconnu par une série de tests simples; les méthodes dites paramétriques ou bayésiennes, où l'on se donne un modèle de la distribution de chaque classe (en général gaussien), et où l'on cherche la classe à laquelle le point a la probabilité la plus grande d'appartenir. Dans le premier cas, une tactique simple est de définir des hyperplans qui séparent au mieux les classes d'apprentissage. La décision se réduit alors à une série de produits scalaires. Ces méthodes sont dites de séparation linéaire. La détermination des équations de ces hyperplans a fait l'objet de nombreux travaux, et les probabilités théoriques d'erreur correspondantes ont été largement étudiées.
Une autre approche non paramétrique très utilisée est celle de la décision par plus proche voisin: on attribue au point inconnu la classe de son plus proche voisin de l'ensemble d'apprentissage. Cette méthode simple a de bons résultats statistiques, mais souvent longue en temps de calcul. Des versions accélérées en ont été proposées, ainsi que diverses extensions.
Dans le cas paramétrique, on cherche à minimiser l'erreur moyenne de mauvaise classification grâce aux hypothèses sur la nature statistique des classes. Si l'ensemble d'apprentissage (et l'espace de représentation) se prêtent à ces hypothèses, on est dans une situation optimale pour la décision. La difficulté est bien souvent que la répartition des points dans chaque classe n'est pas assez régulière, ou que les points ne sont pas assez nombreux, pour que la précision des calculs soit proche de celle que donne la théorie. Ces réserves faites, ce type de méthode est rapide et donne de bons résultats.
Si l'approche statistique permet de se placer dans un cadre mathématique solide et général, elle présente cependant le défaut d'oublier la nature des mesures qui sont faites sur les formes et de les traiter de façon abstraite; en particulier, l'utilisation d'une métrique de type mathématique oblige à considérer toutes les coordonnées caractérisant un point comme anonymes: on ne peut pas exprimer dans un tel modèle certains types de contraintes auxquelles pourtant obéissent les formes étudiées. Un exemple simple aidera à préciser ce concept.
Supposons que l'on cherche à caractériser deux familles de formes dans des images noires et blanches: les triangles équilatéraux à base horizontale et les carrés à base horizontale, et que la taille de ces formes et leur position dans l'image ne soient pas à prendre en compte. Une approche statistique consisterait à prendre un certain nombre de mesures sur ces images et à caractériser les objets sur un point dans un espace métrique de dimension égale au nombre de mesures. On voit déjà que toutes les mesures directement liées à la taille de objets seront inefficaces, puisque celle-ci n'est pas caractéristique. Une normalisation par rapport à celle-ci est donc indispensable, ce qui nous éloigne déjà d'un traitement aveugle des données captées. Pour avoir des mesures comparables, il faudra d'autre part sans doute recentrer les figures dans l'image. Ces opérations faites, des mesures telles que celles de la surface, le périmètre, la largeur de l'intersection avec des droites, etc., pourront être entreprises; l'espace de représentation sera défini de la sorte et une technique de décision sera mise en oeuvre.
On conçoit cependant qu'il est plus simple et plus riche d'utiliser des paramètres descriptifs liés à la nature même des formes étudiées. Si l'on possède une technique de suivi de contour (ce qu'il est facile d'imaginer dans des images à deux niveaux de gris) et un détecteur de segments, on voit que tous les triangles (fig. 2) peuvent se décrire par une caractéristique du type:
"la frontière est composée d'un segment horizontal de longueur l, suivi d'un segment oblique de longueur à peu près l, suivi d'un segment oblique de longueur à peu près l, qui se termine au point de départ du premier".
L'intérêt d'une telle description (et on peut bien sûr en faire une autre analogue pour les carrés, voir fig. 2) est d'être universelle pour tous les triangles équilatéraux, indépendamment de leur taille et de leur position dans l'image. Elle décrit ces figures, d'une part, en définissant des formes élémentaires (segments de droites dans la frontière) et, d'autre part, par l'assemblage de ces formes élémentaires pour constituer la figure totale. On dit qu'une telle description est de type structurel, puisqu'elle s'attache plutôt à définir les caractéristiques intrinsèques de la forme qu'à donner sa description métrique (qui ne se révèle pas riche dans un tel exemple).
Dans cet espace de représentation, une forme sera donc décrite par la suite des segments relevés le long de sa frontière. On voit que l'ordre de ces paramètres est fondamental (contrairement au cas statistique). Comment comparer deux telles formes d'une manière efficace ? Comment caractériser une famille de formes analogues par un être mathématique résumant leurs caractéristiques structurelles ?
Les problèmes d'apprentissage et de décision ainsi posés dans les espaces de représentation structurels vont évidemment avoir une nature très particulière et faire appel à des notions très différentes de celles utilisées dans les espaces métriques usuels.
C'est le but de cet ouvrage que d'introduire ces notions, d'abord sous leur aspect formel, puis de présenter les algorithmes que l'on peut mettre en oeuvre grâce à ces formalismes et enfin de montrer sur des exemples des applications pratiques de l'approche structurelle.
On verra donc au cours des chapitres à suivre, en particulier à propos des exemples d'application, quelles sont les façons possibles de représenter la structure d'une forme, et d'en tirer parti pour sa catégorisation, c'est-à-dire sa reconnaissance.
Un point important pour l'utilisateur potentiel, appelé à résoudre un problème pratique, est bien sûr le choix du type de méthodologie: statistique, ou structurelle ? Avant de chercher quel formalisme structurel est applicable et à quel prix, il est nécessaire de se demander si ce type même d'outil est indispensable. On doit donc ici donner quelques indications générales sur les mérites comparés des deux approches, avant que les outils proposés et les exemples cités permettent de rentrer dans la stratégie et les détails de la résolution d'un problème.
Une constatation s'impose d'abord à l'évidence: aucun des deux types d'approche n'est la panacée. Certains problèmes se résolvent naturellement mieux à partir d'une approche statistique (ceux où le nombre des mesures est important, et la taille de l'ensemble d'apprentissage très significative induisent un traitement de ce type); d'autres sont considérablement simplifiés par l'utilisation d'outils de type structurel (caractères manuscrits, par exemple).
D'un autre côté, forcer à tout prix des données à s'adapter à un formalisme, pour pouvoir appliquer les algorithmes correspondants, n'est pas toujours une procédure habile. En regardant la bibliographie des différentes applications, on s'aperçoit que le choix "statistique ou structurel" est avant tout pragmatique: il est très difficile de citer un domaine d'application où les deux types d'approches n'aient pas été utilisées, et souvent il ne se dégage pas une supériorité indiscutable de l'un sur l'autre.
Une autre remarque est que, bien sûr, les formalismes mathématiques et les philosophies des deux méthodologies sont très opposés; mais comme le remarque K.S.Fu, cette distinction n'est significative justement que si l'on se place du point de vue des formalismes: elle est beaucoup moins nette en termes d'application à un problème pratique. La plupart de ces problèmes ont intérêt à s'étudier sous les deux angles, de façon à ce que chaque approche puisse apporter ses avantages. Comme on l'a déjà dit, le dogmatisme n'est ici pas très payant, et il peut être très avantageux pour un "structuraliste" d'introduire un peu de décision statistique à un niveau de son problème, ce qui lui simplifiera considérablement le travail, ou à un "statisticien" de tenir compte de propriétés structurelles lui permettant d'éviter un traitement exhaustif, par exemple pour un problème à grand nombre de classes, ou dans la recherche d'un plus proche voisin. Les deux méthodologies n'ont évidemment rien à gagner à s'ignorer.
Un exemple concret concerne les grammaires probabilisées (cf. chap. 2 et 3) où l'introduction de mesures de probabilités permet d'accélérer l'analyse syntaxique de la structure de la forme, ou d'aider à l'apprentissage de cette structure. L'utilisation conjointe des deux approches est en général très enrichissante, comme en témoignent souvent les exemples bibliographiques. Un autre exemple est l'utilisation de critères de type structurel pour organiser un dictionnaire de représentants de l'apprentissage, afin d'accéder rapidement à un sous-ensemble sur lequel on fera une décision statistique. Dans les deux cas, une telle approche mixte combine les avantages des deux types d'approche. Pourquoi s'en priver?
L'objet de cet ouvrage est de décrire les principaux outils utilisés en reconnaissance des formes quand on a choisi une approche de type structurel, et, dans chaque espace de représentation ainsi défini, de présenter des algorithmes de décision et d'apprentissage.
On commencera par les modèles les plus simples, pour lesquels la forme est décrite par un enchaînement de formes élémentaires (comme dans l'exemple précédent). Ce sera l'objet du chapitre 1.
On trouvera les techniques de comparaison de chaînes, qui présentent plusieurs aspects selon le type de distance que l'on veut bien définir. Le cas des méthodes de comparaison dynamique sera abordé à cet endroit.
Les chapitres 2 et 3 traitent des modèles mathématiques (grammaires) dont l'objet est d'engendrer des familles de chaînes possédant en commun certaines caractéristiques structurelles. La reconnaissance des formes est une discipline qui utilise en effet les propriétés de ces modèles. L'idée de base est bien sûr de caractériser une classe de formes par une telle grammaire, ce qui pose à nouveau les problèmes de la décision (une chaîne peut-elle être engendrée par une grammaire?) et de l'apprentissage (comment extraire un modèle représentatif d'un ensemble de formes décrites de la sorte?). On abordera également les modèles syntaxiques pondérés, qui apportent une certaine souplesse supplémentaire aux grammaires classiques. Le chapitre 2 est consacré aux modèles réguliers et aux automates finis, le chapitre 3 aux modèles algébriques et à certaines de leurs extensions.
Le chapitre 4 présente les structures d'arbres, qui permettent d'introduire soit une description plus fine, soit des relations hiérarchiques entre les formes élémentaires. On y trouvera certaines techniques de comparaison entre de tels modèles, ainsi que la caractérisation sous forme de grammaire des propriétés communes à un ensemble d'arbres (représentant une classe de formes).
Le chapitre 5 décrit les structures de graphes, qui autorisent une description très souple de formes complexes en symbolisant les relations entre leurs composantes élémentaires d'une manière assez générale. Les problèmes de décision dans ces structures sont abordés. On étudie ensuite un aspect différent, que l'on pourra appliquer pratiquement à tous les formalismes décrits précédemment: celui de la représentation d'un problème sous forme d'un espace d'états, c'est-à-dire de graphe où l'on recherche un chemin optimal. La taille de ces graphes oblige à avoir en mémoire seulement un nombre partiel de leurs noeuds. On décrira des méthodes exactes et approchées permettant de résoudre ce problème, dont la généralité et l'intérêt sont grands.
Le chapitre 6 enfin, grâce à des exemples choisis dans des réalisations réelles de reconnaissance structurelle, visera à montrer comment les méthodologies introduites peuvent être appliquées en pratique. On y constatera que, bien souvent, les modèles présentés doivent être utilisés d'une manière souple, et jouent souvent plus le rôle d'outils que de méthodes infaillibles. Mais on verra aussi ce que leur utilisation apporte d'irremplaçable dans la résolution de certains problèmes complexes.