Brevet FR2663139A1 — publié le 19911213

"DISPOSITIF DE RECONNAISSANCE AUTOMATIQUE D'OBJETS La présente invention concerne un dispositif de reconnaissance automatique d'objets. Cette invention est utilisable notamment dans le domaine de la robotique, par exemple pour la réalisation d'automates à usage industriel destinés à manipuler des pièces manufacturées. L'article "TYPER : A new approach for the recognition and positioning of two-dimensional objects", de N.Ayache et O.D. Faugeras, IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. PAMI-8, n01, janvier 1986, pp.44-54, décrit un dispositif de ce type, dans lequel on peut noter la mise en oeuvre des fonctions suivantes acquisition d'images, numérisation des signaux vidéo, détection d'un ou de plusieurs modèles que l'on veut reconnaître dans les images. Cette fonction de détection, qui est assez complexe, repose sur l'idée de base suivante, à savoir qu'on opère par prédiction (ou génération) d'un certain nombre d'hypothèses, qui sont ensuite évaluées quant à leur degré de validité et, finalement, examinées de façon comparative aux fins de validation de l'une d'entre elles. Ces opérations d'examen et de classification sont réalisées en construisant un arbre de décision basé sur des caractéristiques structurelles des objets à reconnaître. De telles caractéristiques structurelles sont cependant difficiles à obtenir. La procédure la plus courante consiste à effectuer le repérage d'un premier élément caractéristique dans l'ensemble de l'image (procédure dite "pattern matching'), puis à effectuer une recherche sélective d'autres éléments, pour confirmation ou infirmation suivant la position et le type du premier élément trouvé. Par cette manière de procéder, on parcourt un arbre de décision qu'il est nécessaire d'équilibrer afin d'optimiser le temps de reconnaissance, et cet équilibrage de l'arbre passe par la définition d'éléments caractéristiques au cours de la procédure de "pattern matching".La construction de l'arbre de décision peut cependant s'avérer délicate suivant le type d'objets que l'on veut reconnaître. Le but de l'invention est de proposer un dispositif de reconnaissance automatique d'objets dans lequel les opérations de définition des caractéristiques structurelles et de construction de l'arbre de décision sont considérablement simplifiées. A cet effet l'invention concerne un dispositif tel que défini plus haut et caractérisé en ce qu il comprend (A) un sous-ensemble d'extraction de contour, comprenant lui-même (a) un circuit de calcul de gradient morphologique (b) un circuit de comparaison (c) un circuit d'extraction de coordonnées des points de contour (d) un circuit de mémorisation (B) un sous-ensemble de détermination de caractéristiques locales des objets, comprenant lui-même (e) un circuit de détermination de courbure (f) un circuit de filtrage (g) un circuit de sélection des caractéristiques locales (C) un sous-ensemble de classification, comprenant lui-même (h) un circuit de reconnaissance locale (i) un circuit de classification globale. Les avantages de cette structure tiennent au fait que les caractéristiques utilisées sont générales et ne dépendent pas du type d'objets à reconnaître, que ces caractéristiques restent locales et peuvent donc résister à l'occultation d'une partie de l'objet (soit par recouvrement de plusieurs objets, soit par une mauvaise seugmentation de l'image), et qu'il n'y a pas d'arbre de décision explicite à reconstruire pour chaque nouveau problème, la procédure de classification et d'apprentissage par réseau de neurones étant tout à fait générale. Les particularités et avantages de l'invention apparaîtront maintenant de façon plus précise dans la description qui suit et dans les dessins annexés, donnés à titre d'exemples non limitatifs et dans lesquels - la figure 1 montre un exemple de réalisation du dispositif selon l'invention - la figure 2 montre les étapes essentielles de la méthode d'extraction de contour mise en oeuvre dans le dispositif de la figure 1 (A = calcul de gradient morphologique et seuillage, B = suivi de contour) - l'étape C de la figure 2 et la figure 3 montrent les étapes essentielles de la méthode de détermination de caractéristiques locales mise en oeuvre dans le dispositif de la figure 1 - la figure 4 montre les étapes essentielles de la méthode de classification mise en oeuvre dans le dispositif de la figure 1. Le dispositif de reconnaissance automatique d'objets représenté sur la figure 1 comprend tout d'abord un sous-ensemble 100 d'extraction de contour, comprenant lui-même successivement un circuit 101 de calcul de gradient morphologique, déterminant une estimation de contraste pour chaque point courant de l'image, un circuit de comparaison 102, dans lequel la valeur de contraste estimée est comparée à un seuil, un circuit 103 d'extraction de coordonnées des points de contour, et un circuit de mémorisation 104. Ce sous-ensemble 1001 qui reçoit l'image acquise et numérisée et est destiné à délivrer l'ensemble des points des contours présents dans cette image, opère dans l'exemple décrit par une méthode dont les étapes sont schématisées sur la figure 2. Dans une fenêtre centrée successivement sur chaque point d'image, la différence entre les valeurs de gris respectivement maximale et minimale est calculée (par le circuit 101), puis comparée à un seuil (dans le circuit 102), en vue de la sélection ou non de chaque point d'image selon que le seuil est dépassé ou non (étape A, sur la figure 2).Dans l'image binaire ainsi constituée (aux points d'image sélectionnés, sont associées des valeurs "1" et aux points d'image éliminés des valeurs "0"), l'utilisation d'une méthode de suivi (étape B, sur la figure 2) permet l'extraction (dans le circuit 103) des coordonnées des points ainsi sélectionnés. Cet ensemble des coordonnées des points de contour est alors stocké en mémoire (dans le circuit 104). Le dispositif de la figure 1 comprend ensuite un sous-ensemble 200 de détermination de caractéristiques locales des objets, comprenant lui-même successivement un circuit de détermination de courbure 201, un circuit de filtrage 202, et un circuit 203 de sélection des caractéristiques locales. Ce sous-ensemble 200, qui reçoit la séquence des paires de coordonnées des points de contour obtenus, opère de la façon suivante, en référence aux étapes schématisées sur les figures 2 et 3. Pour chaque point de contour, la courbure locale est déterminée (dans le circuit 201), par exemple par calcul de l'angle formé par deux droites de régression linéaire considérées avec quelques points qui précèdent et suivent, respectivement, le point de contour courant, puis la fonction périodique constituée par la variation de cette courbure locale CL en fonction de l'abscisse curviligne AC le long du contour est ensuite filtrée (dans le circuit 202), afin d'éliminer les variations dues à la numérisation de l'image courante (étape C, sur la figure 2). Sur la courbe représentative de la fonction ainsi "lissée", on isole les extrema locaux notés Ex, puis l'on calcule les distances entre extrema successifs (étape D, sur la figure 3). Chacune des distances dn ainsi calculées est alors relativisée (étape E, sur la figure 3) en la divisant par la somme de la distance courante considérée dn et des deux distances dn#1 et dn+1 qui l'entourent, la valeur relative étant appelée drn. Ces dernières opérations, relatives aux extrema locaux, sont effectuées par le circuit 203, qui délivre finalement, en association à chaque point de contour obtenu, la courbure du contour estimée en ce point et une grandeur dite distance relative entre deux extrema successifs. Le dispositif de la figure 1 comprend enfin un sous-ensemble de classification 300, comprenant lui-même successivement un circuit de reconnaissance locale 301 et un circuit de classification globale 302. Ce sous-ensemble 300, qui reçoit les deux jeux d'attributs de courbure locaux délivrés par le sous-ensemble 200 en association à chaque point de contour, opère de la façon suivante, en référence aux étapes schématisées sur la figure 4. Ces attributs de courbure prélevés dans une fenêtre d'examen glissant le long du contour sont fournis (étape F, sur la figure 4) à un réseau de neurones, dont les paramètres sont, de façon classique, fixés pendant une phase d'apprentissage. Au cours de cette phase, des images de référence dont on connaît le type sont également fournies au réseau, dont les coefficients sont alors adaptés en suivant l'algorithme d'apprentissage. Un exemple de procédé et de dispositif de traitement par réseau de neurones est décrit par exemple dans l'article "A VLSI architecture for feedforward networks with integral back-propagationW de J.J. Paulos et P.W. Hollis, D.E.C.E., North Carolina State University, Raleigh, NC 27695-7911, paru dans "Neural Networks", non1988, supplément n01, p.399, ou encore dans l'article "An introduction to computing with neural nets", de R.P. Lippmann, IEEE-ASPP-Magazine, avril 1987, pp.4-22. Ces documents décrivent en particulier la méthode d'apprentissage par rétropropagation du gradient, qui ne sera donc rappelée ici que dans ses grandes lignes. Dans un réseau de neurones en couches successives, des paramètres d'entrée sont fournis aux entrées du réseau qui reçoit par ailleurs des données de référence constituant les sorties souhaitées. Les informations d'entrée se répartissent alors dans#les connexions, en progressant des couches d'entrée du réseau vers les couches de sortie. Les écarts par rapport aux sorties souhaitées sont alors évalués puis rétropropagés dans le réseau pour ajuster les coefficients de celui-ci. Après une succession de reconnaissances locales (étapes F) ainsi effectuées dans le circuit 301 pour différentes fenêtres d'examen successives, les portions de contour classées comme concernant le même type d'objet sont regroupées par le circuit 302 (étape G, sur la figure 4), et cet objet reconstitué est visualisé sur écran. REVENDICATION 1. Dispositif de reconnaissance automatique d'objets, caractérisé en ce qu'il comprend (A) un sous-ensemble d'extraction de contour, comprenant lui-même (a) un circuit de calcul de gradient morphologique (b) un circuit de comparaison (c) un circuit d'extraction de coordonnées des points de contour (d) un circuit de mémorisation (B) un sous-ensemble de détermination de caractéristiques locales des objets, comprenant lui-même (e) un circuit de détermination de courbure (f) un circuit de filtrage (g) un circuit de sélection des caractéristiques locales (C) un sous-ensemble de classification, comprenant lui-même (h) un circuit de reconnaissance locale (i) un circuit de classification globale.