Accueil » Publications » Le Bulletin Vert » Spécial journées » 256-257. Fondements mathématiques de (...)
  APMEP   256-257. Fondements mathématiques de la reconnaissance des structures

Article du bulletin 256-257

- 27 janvier 2013 -

par Monique PAVEL GIVENS

Maître de Conférence à la Faculté des Sciences de Clermont-Ferrand chargée d’un cours à la Faculté des Sciences de Paris

1. Introduction.

  • 1.1. Définitions du problème.
    Reconnaître un objet (image) l donné et de catégorie inconnue, c’est associer par son inspection à l une des classes (données d’avance) $P_{1}, P_{2}... P{n}$
  • 1.2 délimitation du domaine.
    La reconnaissance automatique des structures couvre actuellement un domaine d’applications assez bien défini, essentiellement :
    - a) reconnaissance des caractères écrits (chèques bancaires. cartes de crédit, etc.) ;
    - b) reconnaissance de la parole ;
    - c) autres domaines tels que : recherche dans un fichier d’empreintes digitales, tri de plaques photographiques provenant d’expériences de physique nucléaire, analyse photométrique de la cellule sanguine, exploitation des photographies de reconnaissance aérienne, etc.
    Cette liste est loin d’être exhaustive ; il faut cependant remarquer que presque toutes les applications ont pour but de résoudre l’un ou l’autre de ces deux problèmes voisins que sont la suppression du goulot d’étranglement que constituent les entrées des calculateurs et l’exploitation de documents non codés lorsque leur volume devient intolérable. Nous nous intéresserons en particulier aux caractères écrits.
  • 1.3 Génération et analyse de structures

    - a) Invariants
    Les structures les plus élémentaires que l’on rencontre usuellement sont les figures géométriques. Elles peuvent être caractérisées par leurs propriétés intrinsèques, i.e. par la constance de certaines fonctions à travers diverses transformations. C’est au reste le but des géométries, définies par la donnée d’un espace topologique et d’un ensemble de transformations de cet espace, que d’étudier les systèmes invariants par rapport à cet ensemble.
    Une structure sera donc initialement caractérisée par des invariants, que nous appellerons structuraux, et qui pourront être algébriques ou topologiques.
    Lorsque les membres d’une classe diffèrent l’un de l’autre uniquement par une translation de l’axe des coordonnées, une des approches les mieux connues consiste à utiliser les mesures invariantes par rapport aux translations, et la classe la mieux connue de mesures de translations sont les fonctions d’auto-corrélation. D’autres fonctions invariantes par rapport aux translations qui ont été utilisées pour caractériser les structures sont les transformées de Fourier et les moments centraux d’ordre supérieur. Malheureusement elles n’ont pas la propriété désirée d’unicité (par exemple, la première fonction d’auto-corrélation n’est pas une transformation biunivoque ; plusieurs structures qui diffèrent l’une de l’autre par autre chose qu’une translation ont la même fonction d’auto-corrélation).
    On peut aussi déduire des invariants pour des changements d’échelle et des rotations.
    - b) Approche descriptive
    Si les invariants permettent de définir les formes géométriques simples en l’absence de bruit, ou avec une certaine approximation en présence de bruit, ils peuvent devenir inéconomiques dès que celles-ci deviennent complexes (voir, par exemple, les caractères manuscrits de l’alphabet latin, les empreintes digitales, etc.).
    On les définit alors descriptivement. Prenons l’exemple de M. EDEN qui décrit les lettres manuscrites de l’alphabet latin à l’aide des quatre éléments ou signes suivants :

que l’on combine par concaténation et par un certain nombre de règles précisant l’emplacement des signes au sein d’une lettre et la façon de les joindre (conditions aux limites).

On est ainsi conduit à l’idée d’une analyse et donc d’une reconnaissance grammaticale des images. Précisons néanmoins que l’on doit combiner une définition grammaticale de l’ensemble et une définition géométrique de chacun des éléments. Il se pose un double problème, d’une part de définition grammaticale des structures, d’autre part de reconnaissance des structures, et pour prendre une image commode, d’une part de génération d’un langage, d’autre part de reconnaissance de ce langage.

2. Un modèle mathématique de génération et de reconnaissance des structures.

D’un point de vue formel, le modèle que nous présenterons est linguistique en ce qu’il s’attache à créer un formalisme permettant de décrire et d’analyser une structure, non pas simplement en énumérant des propriétés, mais en mettant l’accent sur la génération des objets que nous observons, i.e. en spécifiant des règles de génération et de transformation par similitude donc en liant les différentes parties d’une image. Cette approche est fondamentalement celle des grammaires génératives.

Les premiers auteurs qui, dans la pratique, ont effectué une analyse grammaticale sont R. A. KIRSCH sur des figures géométriques, R. NARASIMHAN sur des chambres à bulles, LIPKIN-WATT-KIRSCH sur des images biomédicales, M. EDEN sur des caractères manuscrits et U. GRENANDER sur des empreintes digitales.

L’idée de concevoir un modèle mathématique du problème en partant de l’analyse grammaticale est due à U. GRENANDER ; nous nous en sommes inspirés dans cette étude.

  • 2.1. Exemple : Un modèle génératif pour les lettres manuscrites anglaise (Narasimhan et Reddy).
    Nous commencerons par un exemple avant de développer la théorie mathématique générale, en espérant qu’il montrera ce que cette théorie se propose de formaliser dans quelle mesure elle y arrive et quels sont les problèmes de recherche qui restent ouverts.
    L’article présenté donne un modèle génératif pour les lettres manuscrites anglaises et la simulation sur calculateur de ce modèle.
    Le modèle décrit fait partie d’un modèle plus général. appelé syntactique.
    Une grammaire à structure de phrase pour un langage L est spécifiée en termes d’un vocabulaire fini V et d’un ensemble fini R de règles de production de réécriture ; V est composé de deux parties disjointes $V = \Sigma\cup S$, $ \Sigma\cap S = \emptyset $, appelées respectivement vocabulaire terminal et vocabulaire non-terminal ; Nous appellerons les éléments de $\Sigma$ mots, ou signes, et ceux de S phrases, ces derniers permettant d’exprimer les règles de R. S contient un élément défini $S _0$, appelé axiome.

Chaque règle de réécriture est de la forme : $\alpha A\beta\rightarrow\alpha\gamma\beta$

où $A\in S$, $\alpha,\beta, \gamma\in V=\Sigma\cup S$. Les règles de réécriture spécifient que dans le contexte $\alpha-\beta$, la phrase A peut être réécrite sous la forme $\gamma$. Une grammaire dans laquelle la part du contexte est nulle dans toutes ses règles de réécriture s’appelle grammaire context-free. sinon c’est une grammaire context-sensitive.

On peut donc dire qu’une grammaire (context-free) G pour un langage L est un quadruplet...

Lire l'article dans son intégralité

(Article mis en ligne par Christiane Zehren)
 Accueil   Plan du site   Haut de la page   Page précédente