Brevet FR2667255A1 — publié le 19920403

PROCEDE DE CLASSIFICATION AUTOMATIQUE D'OBJETS A DEUX DIMENSIONS La présente invention se rapporte à un procédé de classification automatique d'objets à deux dimensions, par exemple de pièces industrielles, présents sur une image et trouve ses applications notamment dans le domaine de la robotique tels que les systèmes de vision pour les robots et plus généralement dans tous les domaines nécessitant la reconnaissance automatique d'objets. Il existe des systèmes automatiques capables de reconnaître et de localiser, par vision, des objets isolés représentés en deux dimensions sur une image ayant un fond contrastant avec les objets. Cependant dans certains cas, il est impossible, ou cela reviendrait trop cher, d'arranger les objets de façon à ce qu'ils soient isolés. Il existe également des systèmes de reconnaissance d'objets partiellement visibles. Ces systèmes de reconnaissance sont généralement basés sur la comparaison des pièces avec des modèles de pièces stockés dans la mémoire d'un ordinateur. Ces systèmes fonctionnent sur un principe de génération et de vérification d'hypothèses en recherchant par exemple les coins présents sur l'image des pièces à classifier. La figure i montre un exemple d'image de deux pièces P1, P2 à reconnaître parmi trois modèles d'objets 01, 02, 03 connus. Ces objets 01, 02, 03 comportent respectivement 8 coins, 12 coins, 6 coins. Pour chaque coin de limage à reconnaître il y a donc 26 hypothèses possibles correspondant aux associations avec les coins des modèles. On connaît les distances d entre les coins d'un même modèle. A chaque hypothèse d'association faite pour un coin d'une pièce de l'image, il faut donc vérifier si cette pièce comporte un autre coin à une distance d.Par exemple, si C'1 et C'2 sont deux coins voisins de l'objet 03 et sont espacés d'une distance dl, et si pour le premier coin CI de la pièce P1 de l'image l'hypothèse est CI = C'i, il faut vérifier si cette hypothèse est vraie ou fausse et donc rechercher si la pièce P1 comporte un autre coin C2 distant d'une distance dl du coin Ci. Si cette hypothèse est vraie, les autres coins de la pièce sont recherchés et vérifiés de la même façon ; si cette hypothèse est fausse, une nouvelle hypothèse est faite et ainsi de suite. Dans la réalité, le processus de vérification d'hypothèses est plus complexe car certains coins peuvent être masqués ou non détectés en cas de recouvrement de deux ou de plusieurs objets. Les taux de reconnaissance obtenus par ce processus sont généralement satisfaisants, mais ce processus est très lent car il est rare que les hypothèses envisagées soient correctes dès les premières itérations, ce qui nécessite un grand nombre de retours en arrière, coûteux en temps de calcul. L'invention a pour objet un procédé de classification de pièces utilisant une approche différente, selon laquelle, dans une phase préalable, un apprentissage par un réseau de neurones est effectué à partir d'images comportant des exemples de pièces ou de morceaux de pièces, une même pièce pouvant être présente sur plusieurs images mais visible par morceaux et les différentes vues d'une même pièce formant une même classe. A l'issue de cette phase, le réseau de neurones est capable de reconnaître rapidement des objets entiers ou des morceaux d'objets présents sur une image nouvelle. Ce procédé peut être utilisé seul et a l'avantage de fonctionner par apprentissage et de permettre une mise en oeuvre rapide du système de reconnaissance puisque l'opérateur n'a pas à réaliser une modélisation des objets. Ce procédé peut également être couplé à un procédé de reconnaissance classique, et permet alors, en guidant la génération d'hypothèses, d'accélérer le système de reconnaissance. Selon l'invention, le procédé de classification automatique d'objets à deux dimensions présents sur une image est caractérisé en ce que - dans une phase préalable, et pour un nombre fixé d'images comportant des exemples d'objets ou de morceaux d'objets appartenant à différentes classes, des fonctions de reconnaissance correspondant à des configurations angulaires relatives à une approximation polygonale d'un contour de l'objet considéré, sont calculées - puis, dans une phase d'apprentissage, pour chaque exemple d'objets, les valeurs des fonctions de reconnaissance sont utilisées pour ajuster, par approches successives, les valeurs des coefficients de pondération d'un réseau de neurones jusqu a ce que les valeurs de sortie du réseau de neurones soient représentatives des différentes classes considérées - enfin, dans une phase de reconnaissance, les valeurs des fonctions de reconnaissance d'un objet à classifier sont calculées et présentées aux entrées du réseau de neurones qui, par application des coefficients de pondération fixés en fin de phase d'apprentissage, donne une configuration de sortie à partir de laquelle est déterminé à quelle classe, parmi les classes apprises, appartient l'objet considérée. D'autres particularités et avantages de l'invention apparaîtront clairement dans la description suivante donnée à titre d'exemple non limitatif et faite en regard des figures annexées qui représentent - la figure 1 précitée, un exemple de deux pièces à reconnaître, selon l'art antérieur - la figure 2, une représentation modélisée d'un neurone - la figure 3, le schéma d'un réseau de neurones multicouche utilisé dans le dispositif, selon l'invention; - la figure 4, un exemple d'organigramme permettant la réalisation de l'approximation polygonale, selon l'invention; - la figure 5, un exemple d'approximation polygonale selon l'invention; - la figure 6, une illustration des fonctions de reconnaissance correspondant aux angles d'intersection entre deux segments successifs et entre trois segments successifs, selon l'invention;; - la figure 7, un organigramme de la phase d'apprentissage, selon l'invention; - la figure 8, un organigramme de la phase de reconnaissance des pièces industrielles, selon l'invention. Comme indiqué ci-dessus, les systèmes de reconnaissance de pièces industrielles fonctionnent sur un principe de génération et de vérification d'hypothèses et nécessitent des modèles. La modélisation nécessite souvent l'intervention d'un opérateur, ce qui est coûteux. De plus, la génération et la vérification d'hypothèses sont des processus lents. L'invention permet de remédier à ce problème en utilisant un réseau de neurones ayant un nombre de degrés de liberté suffisant pour pouvoir, en fixant ces différents degrés de liberté, obtenir en sortie du réseau de neurones le résultat attendu pour différentes classes d'objets dites "apprises", ce réseau pouvant être ensuite utilisé pour des images inconnues et pour déterminer à quelle classe appartiennent les objets de l'image par analogie avec ces classes d'objets. La figure 2 représente un exemple de modélisation d'un neurone. Un neurone J peut être modélisé à l'aide d'un sommateur pondéré, 10, associé à un dispositif de calcul d'une fonction, 20. Les valeurs aux entrées 01, 02, ..., O. ... 0n du sommateur pondéré, 10, sont multipliées par des coefficients de pondération respectivement Wlal, W2j, Wij, ... > Wnj puis additionnées pour former une valeur intermédiaire x. appelée potentiel du neurone J à laquelle est appliqué un calcul de fonction correspondant, f (x;), qui fournit la valeur de la sortie O. de ce neurone J. La fonction f(xj) est de préférence, une fonction non linéaire tangente hyperbolique. O. = f(x.)=th(x./2) J J J Cette fonction tangente hyperbolique permet d'obtenir une valeur de sortie 0. qui tend vers +1 ou -1 lorsque les valeurs intermédiaires x. augmentent en valeur absolue. La figure 3 représente le schéma d'un réseau de neurones multi-couches utilisé dans le dispositif, selon l'invention. Ce réseau de neurones est organisé en plusieurs niveaux, les sorties d'un niveau constituant les entrées du niveau suivant, de telle façon que, en tenant compte de valeurs caractéristiques calculées sur des exemples et présentées aux neurones du premier niveau du réseau, les coefficients de pondération évoluent en cours d'apprentissage jusqu a ce que les neurones du dernier niveau du réseau fournissent pour tous les exemples d'une classe d'objets donnée un coefficient +1 sur la sortie du neurone correspondant à cette classe d'objets, et des coefficients -1 sur ltensemble des sorties des autres neurones. Les valeurs caractéristiques calculées sur les différents exemples de chacune des classes d'objets, puis sur les objets à classifier, sont les valeurs d'un ensemble de fonctions de reconnaissance qui sont des fonctions booléennes correspondant à une configuration angulaire de segments successifs d'un polygône approximant le contour d'un objet. Le réseau de neurones utilisé et représenté sur la figure 3 est un réseau seuil, c'est-à-dire qu'il comporte sur chacun de ses niveaux, sauf le niveau de sortie, un neurone supplémentaire appelé neurone seuil, NS, dont l'état reste toujours égal à 1 et qui permet d'ajouter un degré de liberté supplémentaire dans la masse d'informations que constituent les coefficients de pondération dits "poids". Ce degré de liberté supplémentaire permet au réseau d'apprendre plus facilement et plus vite. Le réseau de la figure 3 comporte trois niveaux - le premier niveau comporte un nombre de neurones Ni égal au nombre d'entrées, ctest-à-dire au nombre de fonctions booléennes calculées pour chaque objet, et en outre un neurone seuil qui ntest pas connecté aux entrées. - le deuxième niveau comporte un nombre N2 de neurones compris entre Ni et la valeur N3 du nombre de neurones du dernier niveau. Chaque neurone du deuxième niveau a (nu+1) entrées reliées aux (N1+1) sorties des neurones du premier niveau et du neurone seuil. Le deuxième niveau comporte en outre un neurone seuil qui n' est pas relié aux neurones du premier niveau. - le troisième niveau comporte un nombre de neurones N3 égal au nombre de classes d'objets utilisées pendant la phase d'apprentissage et qui pourront être reconnues dans les images dans une phase ultérieure de classification. Les entrées des neurones du dernier niveau sont reliées aux (N2+1) sorties des neurones du deuxième niveau. Ce niveau ne comporte pas de neurone seuil. Le dispositif fonctionne de la manière suivante : un prétraitement est réalisé pour extraire les fonctions de reconnaissance d'un objet ou d'un morceau d'objet à classifier. Ces fonctions de reconnaissance sont des indicateurs de configurations angulaires relatives à l'approximation polygonale d'un contour de objet. Dans un premier temps, le contour extérieur d'un objet à classifier est extrait d'une image par un détecteur de contour ou par un dispositif à seuil suivi d'un dispositif assurant un suivi de contour. Ce contour est fermé et peut être approximé à un polygône. Une approximation polygonale du contour est donc réalisée par exemple à partir d'un algorithme itératif dont l'organigramme est représenté sur la figure 4. L'algorithme itératif est le suivant : le premier polygône est obtenu en choisissant 2 points courants appartenant au contour et en les reliant de façon à obtenir les 2 segments dlun polygône. Ces 2 segments sont initialement confondus mais d'orientation opposée. A l'itération suivante, pour chaque segment, les distances des points du contour avec le segment sont calculées, et la distance maximale est considérée et comparée à une valeur seuil. Si la distance maximale est supérieure à la valeur seuil, deux nouveaux segments sont créés à partir du point contour correspondant, sinon le segment est inchangé.Lorsque tous les segments du polygône correspondant à la iième itération ont été considérés, l'itération suivante est considérée et ainsi de suite jusqu'a ce qu'il n'y ait plus de changement entre deux itérations successives. La figure 5 représente un exemple d'approximation polygonale pour deux itérations successives de rang i et i+l respectivement. Dans un deuxième temps, les fonctions de reconnaissance sont calculées. Ces fonctions de reconnaissance sont des fonctions booléennes qui prennent la valeur vraie si une valeur d'angle considérée correspond à la valeur d'un angle d'intersection entre deux segments successifs du polygône obtenu lors de l'approximation polygonale du contour ; elle prend la valeur fausse dans le cas contraire. Une fonction de reconnaissance peut également être obtenue sur un nombre de segments successifs supérieur à 2. La figure 6 Illustre les fonctions de reconnaissance correspondant aux angles d'intersection entre 2 segments successifs et entre 3 segments successifs. La fonction booléenne correspondant à 2 segments successifs, notée FA (polygône), prend la valeur vraie si le polygône comporte 2 segments successifs Segi et Seg2 qui font entre eux un angle A avec une tolérance égale par exemple à + 5 ; ; elle prend la valeur fausse dans le cas contraire. Par exemple, la valeur vraie correspond à la valeur +1 et la valeur fausse à -1. FA (polygône) = +1, s'il existe Segl et Seg2 sur le polygône tels que Seg2 suit Segi et angle (Segi, Seg2) = A La fonction booléenne correspondant à 3 segments successifs, notés FA, B(polygône), prend la valeur vraie si le polygône comporte 3 segments successifs Segl, Seg2, Seg3, tels que les 2 premiers segments fassent entre eux un angle A et les 2 derniers un angle B avec une tolérance égale par exemple à + 100 ; elle prend la valeur fausse dans le cas contraire, FA,B (polygône) = +1 s'il existe Segi, Seg2, Seg3 sur le polygône tels que (Seg2 suit Segl avec angle (Segl,Seg2) = A) et (Seg3 suit Seg2 avec angle (Seg2,Seg3) = B) A titre d'exemple les fonctions booléennes correspondant à 2 segments pourront être calculées par pas de 100, soit il y aura 36 fonctions booléennes Fgo, F100, F200..., F3500, à calculer Pour les fonctions correspondant à 3 segments, par exemple il ne sera pris en compte que les configurations angulaires présentes sur les objets traités pendant la phase d'apprentissage. Lorsque toutes les fonctions booléennes sont calculées elles sont présentées aux entrées du réseau de neurones. Le prétraitement décrit ci-dessus et consistant à extraire les fonctions de reconnaissance d'un objet, est effectué pour tout objet à classifier, que ce soit en phase d'apprentissage ou en phase de reconnaissance. L'apprentissage est du type dit "supervisé", c 'est-à-dire que pour des exemples d'une classe d'objets donnée, l'opérateur apprend au réseau de neurones à reconnaître cette classe d'objets en lui indiquant les valeurs que doivent avoir ses sorties pour cette classe d'objets. Chaque classe d'objets est présentée plusieurs fois au réseau de neurones jusqu a ce que le réseau ne restitue plus aucune sortie fausse.Pendant la phase d'apprentissage, le réseau de neurones ajuste les coefficients de pondération à partir de valeurs de départ arbitraires, par approches successives, en utilisant tous les exemples de chaque classe d'objets, éventuellement plusieurs fois, et dans un ordre quelconque aléatoire. A l'issue de la phase d'apprentissage une classe d'objets donnée correspond à l'obtention d'une valeur aussi proche de 1 que possible sur la sortie du réseau caractéristique de cette classe, et aussi proche de -1 que possible sur les autres sorties, et ce pour chacune des classes d'objets considérées. La phase d'apprentissage est effectuée de la manière suivante décrite ci-après en référence à la figure 7. Les coefficients de pondération Wij sont tout d'abord initialisés en utilisant une loi de probabilité P(W) uniforme dans l'intervalle -M, +M. Pour les neurones du deuxième niveau, la valeur de M est choisie égale à et pour les neurones du troisième niveau, la valeur de M est choisie égale à L'apprentissage consiste alors en la modification des coefficients de pondération W, cette modification des coefficients se déroulant de la façon suivante : à un rang d'itération k donné, un objet exemple est extrait parmi différents exemples et les valeurs des fonctions booléennes calculées pour cet objet sont appliquées aux entrées du réseau de neurones. Les sorties correspondantes du réseau sont alors calculées.Cet exemple étant caractéristique d'une classe d'objet donnée devra donner en fin d'apprentissage, en sortie du neurone associé à cette classe, une valeur égale à +1 ou voisin de +i, les sorties des autres neurones du dernier niveau donnant des valeurs négatives aussi proche de -1 que possible. Les valeurs de sortie du réseau sont donc comparées aux valeurs de sortie désirées. L'erreur sur la sortie, notée E., par rapport à la sortie désirée S. est mesurée par la J J valeur i (Oj-Sj) 2 lorsque I O.-S I est inférieure ou JJ jj égale à 1 et par la valeur (-SjXj+1)/2 si IO.-S.Iest J J supérieur à 1. L'erreur de sortie totale E est la somme des erreurs Ej ainsi calculées pour l'ensemble des sorties de j=l à N3.Les valeurs des coefficients de pondération sont alors modifiées en tenant compte des modifications des coefficients de pondération effectuées au rang d'itération précédent, k-l, ces valeurs étant pondérées par un coefficient de filtrage ss et de la dérivée de la fonction d'erreur, pondérée par une valeur d'un paramètre rl, dit "vitesse d'apprentissage", de la manière suivante Cette modification des coefficients de pondération permet de faire varier les valeurs des poids W en fonction inverse du gradient d'erreur, tout en tenant compte des variations effectuées à l'itération précédente, c'est-à-dire en effectuant un filtrage passe-bas qui permet d'éviter des oscillations pour conserver la valeur moyenne du coefficient de pondération. Ces coefficients étant modifiés, un nouvel exemple d'objets est présenté aux entrées du réseau de neurones et la même opération est effectuée plusieurs fois à partir de tous les exemples disponibles jusqu a ce que les sorties du réseau de neurones soient toujours dans l'état correspondant au type de classe utilisé, c'est-à-dire que pour tous les exemples, les sorties soient proches de -1 pour toutes celles qui ne correspondent pas à l'exemple et proche de +1 pour celle qui correspond à l'exemple, quel que soit l'exemple considéré. Les paramètres d'apprentissage L) et de filtrage B sont choisis par l'opérateur, par exemple il pourra choisir 0= 0,005 et B = 0,985. Lorsque la phase d'apprentissage est terminée, le réseau de neurones est capable de reconnaître à quelle classe appartiennent les objets d'une image nouvelle, les coefficients de pondération sont gelés et sauvegardés et le réseau de neurones peut être utilisé à des fins de reconnaissance d'objets. La figure 8 représente un organigramme de la phase de reconnaissance des pièces industrielles. En phase de reconnaissance, un objet ou un morceau d'objet appartenant à une image nouvelle est analysé en effectuant un suivi du contour de l'objet et une approximation polygonale de ce contour. Les valeurs des fonctions de reconnaissance c'est-à-dire des fonctions booléennes correspondant à cet objet sont calculées et appliquées à l'entrée du réseau de neurones multi-couches. Ces valeurs conduisent par l'application des coefficients de pondération fixés en fin de phase d'apprentissage, à des valeurs de sortie. La classe attribuée à l'objet correspond alors à la classe associée au neurone de sortie ayant la plus forte valeur. Une mesure de confiance est attribuée à cette classification.Cette confiance est calculée de la manière suivante : si ji est le numéro de neurone dont la sortie a la valeur la plus forte, la confiance est mesurée par la valeur minimum de l'écart entre la valeur de la sortie la plus forte et la valeur de chacune des autres sorties - confiance = + min ( jl- j) Par exemple, pour un réseau de neurones ayant appris à reconnaître quatre classes d'objets différentes et dont le niveau 3 comporte 4 sorties, si les sorties des neurones appartenant au niveau 3 ont respectivement des valeurs égales à -i, 0,95, - 0,35,-0,98, la classe de l'objet considéré est celle qui correspond au deuxième neurone de sortie et la confiance correspondant est égale à i (min (O > 95+i), (0,95+0,35), (0,95+0,98)) = 0,65 Le coefficient de confiance ayant été normalisé en divisant par - 2, la confiance est une valeur comprise entre O et 1, la valeur 1 correspondant à la confiance maximale. REVENDICATIONS i . Procédé de classification automatique d'objets à deux dimensions présents sur une image, caractérisé en ce que - dans une phase préalable, et pour un nombre fixé d'images comportant des exemples d'objets ou de morceaux d'objets appartenant à différentes classes, des fonctions de reconnaissance correspondant à des configurations angulaires relatives à une approximation polygonale d'un contour de l'objet considéré, sont calculées - puis, dans une phase d'apprentissage, pour chaque exemple d'objets, les valeurs des fonctions de reconnaissance sont utilisées pour ajuster, par approches successives, les valeurs des coefficients de pondération d'un réseau de neurones jusqu'à ce que les valeurs de sortie du réseau de neurones soient représentatives des différentes classes considérées - enfin, dans une phase de reconnaissance, les valeurs des fonctions de reconnaissance d'un objet à classifier sont calculées et présentées aux entrées du réseau de neurones qui, par application des coefficients de pondération fixés en fin de phase d'apprentissage, donne une configuration de sortie à partir de laquelle est déterminé à quelle classe, parmi les classes apprises, appartient l'objet considérée. 2 . Procédé selon la revendication 1, caractérisé en ce que les fonctions de reconnaissance sont des fonctions booléennes qui prennent la valeur vraie lorsque les configurations angulaires prédéterminées sont présentes sur un polygone approximant le contour de l'objet et qui prennent la valeur fausse dans le cas contraire. 3 . Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le réseau de neurones est organisé en plusieurs niveaux, le premier niveau comportant un nombre de neurones égal au nombre de fonctions de reconnaissance calculées pour chaque objet et le dernier niveau comportant un nombre de neurones égal au nombre de classes d'objets à apprendre. 4 . Procédé selon la revendication 3, caractérisé en ce que le réseau de neurones est un réseau seuillé.