LA RECONNAISSANCE DE FORMES

Le cadre général de la Reconnaissance de Formes 

La Reconnaissance automatique de Formes (RF) est née à la fin des années 50; on associe souvent ses débuts à l’élaboration du perceptron par ROSENBLATT [Rosenblatt-62]. Depuis, la discipline n’a pas cessé d’évoluer et les développements concomitants de l’instrumentation (notamment des capteurs) et des moyens informatiques ont aussi joué un rôle important dans l’essor de la RF. Cette évolution concerne aussi bien les domaines et les thématiques des applications que les méthodes opératoires proprement dites; hier on associait une méthode de reconnaissance à un problème donné; aujourd’hui, pour un problème particulier, on a tendance à faire coopérer plusieurs approches ou démarches (ou bien à définir des stratégies multi-agents). Dans un problème de reconnaissance il y a un petit nombre de notions (les constantes fondamentales de la RF) qui apparaissent systématiquement; nous allons les retrouver dans le schéma suivant qui peut être vu, aujourd’hui, comme une composante élémentaire de tout problème de reconnaissance Schéma élémentaire D’une façon schématique, on peut dire que toute action de reconnaissance de formes met en jeu trois ensembles et deux applications. O : ensemble des objets à reconnaître. C’est un sous-ensemble du monde qui nous entoure, limité par le problème auquel nous nous intéressons. R : ensemble ( ou mieux espace) des représentations de ces objets Ω : ensemble d’interprétation. Il est très souvent réduit à un ensemble de noms ou d’étiquettes; c’est l’ensemble des classes. Le but du problème est d’associer une interprétation (un nom) à chaque entité de O. On peut considérer que, dans la plupart des cas, à un certain niveau, les ensembles O et Ω sont connus ; ce n’est, en fait, pas vrai pour Ω en classification automatique (c’est à dire non supervisée par un être humain) et dans certains problèmes de diagnostic [Dubuisson-90]. 

 En reconnaissance automatique, nous devons passer par l’espace de représentation (qui permet de fournir des données acceptables par nos machines) et nous avons besoin, pour réaliser l’association évoquée ci-dessus, de construire en plus de ℜ les deux applications suivantes: ψ : O Æ R ξ : R Æ Ω On peut résumer ce cadre dans le schéma suivant: Commentaires sur les espaces et les applications. L’ensemble O. Il est impossible de faire des hypothèses sur cet ensemble et sur une quelconque structure mathématique sous-jacente, la donnée d’un problème particulier de reconnaissance de formes doit nous permettre de spécifier les éléments de O. L’espace de représentation R : Cet espace permet de décrire ou de représenter les objets de O, c’est une représentation opératoire de l’objet que l’on doit avoir, en d’autres termes, elle doit être sous forme numérisée (ou facilement numérisable) afin que l’ordinateur puisse la prendre en compte et la traiter. Des prises de mesures réalisées grâce à des capteurs physiques ou de simples descriptions permettront de représenter chaque objet de O par une suite de descripteurs ou caractéristiques qui peuvent être : – des valeurs numériques, des mesures, le niveau de gris pour le pixel,… – des formes élémentaires (des critères de formes, des éléments d’un alphabet, des primitives, …) qui sont elles-mêmes facilement représentables par une liste d’entités numériques. Un élément de R est donc un ensemble de caractéristiques pris dans un certain ordre; on l’appellera, selon le cas, chaîne ou vecteur de caractéristiques (bien que ce ne soit pas un vecteur au sens de la théorie des espaces vectoriels mais seulement un n-uple !); le fait de O Ω R ψ ξ pouvoir doter R de structures (des éléments organisationnels) pourra faciliter la résolution du problème de reconnaissance, notamment en servant pour la construction de ξ. Il n’y a pas de règle associée à la définition de R mais cet ensemble dépend nécessairement de ξ et ψ : – le choix de R est associé étroitement au choix de ξ ; c’est le cœur de la partie algorithmique du problème de reconnaissance de formes. Un fil directeur pourrait être la recherche du meilleur rapport de la pertinence de l’information apportée sur la limitation de la complexité. – on ne peut pas mettre n’importe quelle caractéristique dans R; il faut impérativement que ψ nous permette de la saisir et de la mémoriser, c’est le problème de la calculabilité ou de l’informatisation. L’ensemble R est souvent considéré comme un espace dans le sens où il est structuré. La relation existant entre ses éléments est souvent une relation de voisinage qui peut être associée à une distance, à une (dis)similarité ou encore à une ressemblance. L’espace d’interprétation Ω : Ω se présente souvent sous la forme d’un ensemble fini de classes ω : Ω = {ω1, …ωn}. En OCR (Reconnaissance Optique de Caractères) par exemple, chaque élément ω est le nom d’un caractère, d’un chiffre, d’une lettre majuscule ou minuscule, d’un des signes (de ponctuation ou non), qu’on peut voir sur les claviers de machines à écrire ou des ordinateurs. Dans de nombreuses situations de diagnostic, médical en particulier, la définition de Ω est complexe On peut avoir recours à des structures très diverses afin de modéliser au mieux le problème, ainsi, par exemple il pourrait être une réunion de sous-ensembles flous. Dans tous les cas il est très raisonnable d’introduire une étiquette supplémentaire que nous ferons correspondre à une classe dite de rejet; elle permettra de traduire le fait que dans certaines situations, on ne sait pas, ou bien on ne peut pas, conclure. Dans les problèmes que nous appelons classification automatique ou coalescence l’objectif est, de fait, la construction des classes, c’est à dire la construction de Ω qui doit satisfaire à des contraintes données a priori. Ω, comme R, peut aussi être considéré comme un espace, c’est à dire muni d’une structure qui se résume généralement par des relations de ressemblance ou de proximité entre ses éléments. L’application ψ : Pour la facilité du langage, nous parlons d’application, bien qu’en fait ψ puisse recouvrir les activités des capteurs (caméras, scanners, appareils de mesures, .) qui peuvent saisir les informations qui sont accessibles par les organes des sens de l’homme, ou qui ne le sont pas (l’infrarouge par exemple). Les informations issues de ces capteurs (des signaux bruts) ne sont pas toujours exploitables par la machine Des procédures de prétraitement et/ou de paramétrisation sont alors mises en œuvre; ψ recouvre aussi ces activités. La fonction d’identification ξ : ξ, tout comme ψ, n’a pas d’existence propre bien que l’on dise qu’une identification est une application ξ de l’espace de représentation dans l’espace d’interprétation « Le but de la reconnaissance de formes est d’effectuer cette application de manière constructive, en d’autres termes de trouver un algorithme qui l’effectue pour toute valeur de R » [Simon-84]. Un tel algorithme est souvent appelé opérateur de reconnaissance, soulignant sa nature effective ou programme de reconnaissance de formes s’il est utilisable par un système informatique. On désignera même ξ par le vocable méthode de reconnaissance. Il faut noter que le résultat donné par ξ, appliqué sur R n’est pas toujours une classe ω unique. Ce résultat peut être un couple (OU une famille de couples) de type (ω,f) où f désigne par exemple une valeur d’appartenance floue ou une probabilité. Le mot interprétation trouve davantage son sens ici que lorsque l’on a simplement une identification pour ω.

Vers l’implémentation

L’ensemble d’apprentissage Souvent, dans un processus de reconnaissance de formes on procède à un échantillonnage de l’espace de représentation R sous forme d’un ensemble T, dit ensemble d’apprentissage. Il est généralement considéré soit comme un sous ensemble de R, soit comme un sous-ensemble du produit cartésien R × Ω. Mais rien ne garantit a priori que T soit représentatif de R ; le bon fonctionnement de ξ, sur les éléments de T, ne permet pas, a priori, de préjuger qu’il s’étendra à tous les éléments de R ; on retrouve ici la nécessité de statuer sur R en termes mathématiques. On a, longtemps considéré un ensemble d’apprentissage comme une donnée figée ou a priori du problème ; diverses raisons tendent à remettre en cause cette hypothèse :

 1- Le temps peut être un paramètre du problème, il y a alors une évolution des formes donc de leur représentation (de nouvelles formes peuvent apparaître, par exemple des polices nouvellement créées en Reconnaissance Optique de Caractères (OCR) ); 2- T est incomplet ou non représentatif, car nous n’avions pas une connaissance totale du problème, notamment parce que Ω n’était pas parfaitement appréhendé; 3- Des informations et des connaissances externes peuvent valider ou infirmer de nouveaux couples de type (x,ω), ce qui donne une possibilité d’agrandir T. 4- On peut aussi dire que les capacités de nos machines nous le permettent alors qu’il y a très peu d’années c’était impossible. Cette évolution de T doit pouvoir s’accompagner d’une évolution de ξ.