Brevet FR2669137A1 — publié le 19920515

PROCEDE DE RECONNAISSANCE D'OBJETS TRIDIMENSIONNELS PAR ANALYSE D'IMAGE L'invention se rapporte au domaine de la vision par ordinateur, et plus particulièrement à un procédé de reconnaissance d'objets tridimensionnels projetés en deux dimensions sur une image à partir d'une seule vue de l'objet. Elle trouve ses applications dans le domaine des chaines de montage automatisées et de la robotique et plus généralement dans les domaines du traitement d'images nécessitant l'identification d'objets tels que par exemple la reconnaissance de cibles assez proches Les systèmes de reconnaissance connus sont généralement basés sur la comparaison avec des modèles Il existe des méthodes stéréoscopiques qui permettent de reconstruire en volume l'objet à reconnaître Ces méthodes disposent d'un ensemble de modèles tridimensionnels de plusieurs objets Après reconstruction, en trois dimensions, de l'objet à reconnaître, la méthode consiste à rechercher le modèle tridimensionnel qui s'en rapproche le plus. Ces méthodes peuvent fournir précisément la position de l'objet en plus de la reconnaissance, sous réserve d'une bonne qualité d'image, mais sont coûteuses en matériel, en puissance de calcul requise et en effort de mise en oeuvre. Il existe des méthodes utilisant plusieurs modèles bidimensionnels de différents objets Pour chaque objet, on dispose de nombreuses vues, bien réparties autour de l'objet La reconnaissance d'un objet sur une image nouvelle consiste à extraire des caractéristiques, par exemple des segments, ou des faces, sur l'image, et à chercher à les mettre en correspondance avec les caractéristiques des modèles Les principaux problèmes que posent ces méthodes sont les suivants: la modélisation d'un objet quelconque est difficile et il est souvent préférable de se limiter à des objets polygonaux De plus, la modélisation nécessite généralement l'intervention d'un opérateur, ce qui est coûteux. La mise en concordance des caractéristiques extraites de l'image avec les modèles est coûteuse en puissance de calcul. Pour remédier à ces problèmes, l'invention a pour objet un procédé de reconnaissance d'objets tridimensionnels 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 projections en deux dimensions d'exemples d'objets tridimensionnels, chaque objet étant disponible sous de nombreuses vues différentes, bien réparties autour de l'objet A l'issue de cette phase, le réseau de neurones est capable de reconnaître rapidement un objet tridimensionnel sur une image nouvelle. Ce procédé a l'avantage de fonctionner par apprentissage et ne nécessite donc pas de modélisation explicite des objets ni de stéréoscopie; il ne nécessite pas d'intervention humaine ni de limitation à des objets polygonaux; sa mise en oeuvre est aisée, la reconnaissance des objets est très rapide, nécessite une puis- sance de calcul réduite et peut être effectuée à partir d'une seule vue de l'objet, bien qu'il soit possible d'améliorer les taux de reconnaissance en utilisant plusieurs vues du même objet. Selon l'invention, le procédé de reconnaissance d'objets tridimensionnels est caractérisé en ce qu'il consiste: dans une phase préalable, et pour un nombre fixé d'exemples d'objets tridimensionnels, à effectuer des projections en deux dimensions de ces exemples d'objets tridimensionnels de façon à obtenir un fichier d'images représentant les objets sous de nombreuses vues différentes réparties en plusieurs classes, à extraire le contour externe des objets, à décomposer ce contour en série de Fourier, et à normaliser les coefficients basse fréquence de la décomposition en série de Fourier, dans une phase d'apprentissage, pour chaque exemple d'objets tridimensionnels, les valeurs des coefficients de Fourier normalisés 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 sorties du réseau de neurones soient représentatives des différentes classes d'objets considérées. enfin, dans une phase de reconnaissance, les valeurs des coefficients de Fourier normalisés d'un objet à reconnaître 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é. 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, un schéma synoptique d'un neurone, selon l'invention, la figure 2, un schéma synoptique d'un réseau de neurones multi-couches, selon l'invention, les figures 3 a et 3 b, différents contours relatifs à un support de ruban adhésif vu sous des angles différents; l'angle azimutal est respectivement égal à 0 et 30 , l'angle de rotation a autour de l'axe vertical varie de 180 à 350 , la figure 4, un organigramme de la phase d'apprentissage, selon l'invention, la figure 5, un organigramme de la phase de reconnaissance, selon l'invention. Comme indiqué ci-dessus, les systèmes de reconnaissance d'objets tridimensionnels nécessitent des modèles Ces modèles sont en nombre restreint et la reconnaissance des objets est limitée à ceux-ci De plus, la modélisation est généralement une opération difficile et coûteuse 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 dif- férents degrés de liberté, obtenir en sortie du réseau de neu- rones le résultat attendu pour différentes classes d'objets dites "apprises", ce réseau pouvant être ensuite utilisé pour des ima- ges nouvelles et pour déterminer à quelle classe appartiennent les objets tridimensionnels projetés sur l'image par analogie avec ces classes d'objets. La figure 1 représente un schéma synoptique 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 1, 02 ' i ',n du sommateur pondéré, 10, sont multipliées par des coefficients de pondération respectivement Wlj, W 2 j' - 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(X) est de préférence, une fonction non linéaire tangente hyperbolique. 0 = F(X J = th(X /2) Cette fonction tangente hyperbolique permet d'obtenir une valeur de sortie O qui tend vers + 1 ou -1 lorsque les valeurs intermédiaires X augmentent en valeur absolue. La figure 2 représente un schéma synoptique d'un réseau de neurones multi-couches, 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'à 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 l'ensemble 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 des coefficients basse fréquence normalisés de la décomposition en série de Fourier de la silhouette de l'objet à reconnaître. Le réseau de neurones utilisé et représenté sur la figure 2 est un réseau seuillé, 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, c'est-à-dire au nombre de coefficients de Fourier basse fréquence normalisés calculés pour chaque objet, et en outre un neurone seuil qui n'est pas connecté aux entrées. Les neurones de ce premier niveau ne font que recopier les entrées. le deuxième niveau comporte un nombre N 2 de neurones compris entre Ni et la valeur N 3 du nombre de neurones du dernier niveau Chaque neurone du deuxième niveau a (Nl+l) entrées reliées aux (Nl+l) 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 N 3 é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 (N 2 + 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 des valeurs caractéristiques d'un objet tridimensionnel à apprendre ou à reconnaître. Dans un premier temps, une base de données d'images, ou fichier d'exemples, est constituée à partir de plusieurs objets tridimensionnels projetés en deux dimensions de façon à obtenir différentes vues de l'objet sous des angles différents A titre d'exemple, une base de données de 216 images de taille environ égale à 300 x 200 pixels a été constituée à partir de trois objets tridimensionnels différents. Pour chaque objet deux séries d'images ont été obtenues en plaçant l'objet sur une table tournante et en faisant tourner la table autour de son axe vertical par pas de dix degrés, l'angle de rotation étant appelé angle O Une série d'images a été effectuée avec un angle azimutal de prise de vues égal à O et l'autre série avec un angle azimutal de prise de vues égal à 30 . Le fichier des exemples étant constitué, une image est extraite aléatoirement de ce fichier La silhouette, c'est-à-dire le contour extérieur de l'objet, est alors extrait de cette image par un dispositif à seuil suivi d'un dispositif de détection de surface connexe La surface ainsi obtenue est ensuite gardée ou supprimée de façon automatique ou de façon interactive par un opérateur suivant qu'elle correspond à un objet ou à un reflet. Un suivi de contour est ensuite effectué et des valeurs caractéristiques correspondant à ce contour sont calculées. A titre d'exemple, les figures 3 a et 3 b représentent différents contours relatifs à un support de ruban adhésif vu sous des angles différents Les figures 3 a et 3 b correspondent à un angle azimutal égal respectivement à O et à 30 et un angle de rotation e autour de l'axe vertical variant de 180 à 350 . Dans un deuxième temps des valeurs caractéristiques de la silhouette de l'objet sont calculées en utilisant des fonctions de base Les fonctions de base des séries de Fourier ont des propriétés intéressantes, notamment, une translation, une rotation et une dilatation peuvent être effectuées par de simples opérations en représentation dans l'espace transformé. Le contour d'un objet pris, par exemple, dans le sens in- verse des aiguilles d'une montre, peut être considéré comme une succession de points, et une abscisse curviligne peut être dé- finie sur ce contour Cependant la distance entre deux points successifs ainsi obtenus sur ce contour n'est pas constante, ce qui rend impossible le calcul des coefficients de Fourier Pour pouvoir utiliser les fonctions de base des séries de Fourier, une solution consiste à rééchantillonner le contour de l'objet de façon à obtenir un contour de vitesse uniforme de N points équi- distants Un exemple de rééchantillonnage du contour d'origine est tel que la distance entre des points de connexité 4 est prise égale à 1, et la distance entre des points de connexité 8 est prise égale à YY'Lorsque le contour d'origine a été complète- ment rééchantillonné, toutes les distances séparant deux points successifs sont égales Pour des images de faible résolution, ce type de rééchantillonnage ne convient pas et il est nécessaire d'utiliser un rééchantillonnage plus complexe tel que, par exem- ple, en utilisant une approximation polygonale. En notant U (m) les points du contour rééchantillonné (ces points peuvent être considérés comme des vecteurs dans le plan complexe), les coefficients de Fourier sont obtenus par l'équation ( 1) suivante: N-1 (l) C(n) = i/N E U (m) e -j 2 r nm/N m=o Il y a N coefficients de Fourier, et C(n) est le coefficient de Fourier d'ordre n La transformation de Fourier inverse est la suivante: N-1 ( 2) U (m) = E C(n) e j 2 nm/N n= O Lorsque les N coefficients de Fourier ont été calculés, ils sont normalisés de façon à être invariants par rapport à une rotation du dispositif de prise de vues des objets, ou caméra, autour de son axe optique, une modification de la distance caméra-objet, et une translation parallèle au plan focal; ainsi les coefficients de Fourier sont invariants lorsqu'entre deux images un objet a subi l'une des transformations géométriques suivantes: une translation, une rotation, une dilatation ou un décalage du point de début du contour. Lorsqu'un objet a subi une translation T, les coefficients de Fourier deviennent: U'(m) = U (m) + T C'( 0) = C(O) + T Lorsqu'un objet a subi une rotation d'angle, les coefficients de Fourier deviennent: U' (m) = U(m) ejo C' (n) = C(n) ejo Lorsque les points du contour d'un objet ont subi une dilatation d'un facteur p, les coefficients de Fourier deviennent: U' (m) = p U (m) C' (n) =p C(n) Lorsque les points du contour d'un objet ont subi un déca- lage de k points, les coefficients de Fourier deviennent: U'(m) = U((m + k) modulo N) C' (n) = C(n) e 2 jn kn/N Pour que les coefficients de Fourier soient invariants en fonction de ces quatre transformations il est nécessaire de normaliser ces coefficients Un exemple de normalisation consiste à: ne pas tenir compte du coefficient d'ordre 0, C'( 0), de façon à obtenir l'invariance par translation diviser tous les coefficients par le coefficient d'ordre 1, C'( 1), de façon à obtenir l'invariance par rotation et par dilatation K'(n) = C'(n)/C'( 1) = K(n) exp ( 2 jk(n- 1)/N) multiplier tous les coefficients par exp (j( 1-n)o'2) o o'2 est la phase de K'( 2) et est égale à ( 02 +( 2 irk/N)) pour obtenir l'invariance par un décalage des points du contour P'(n) = K'(n) exp (j( 1-n)q'2) = P(n) La phase q'2 du coefficient K'( 2) doit être arrondie à la valeur la plus proche de la forme 2 rl/N, o 1 est un nombre en- tier, afin d'éviter des incohérences dans les coefficients de Fourier normalisés, ce qui ne permettrait pas de pouvoir les interpréter comme le résultat d'un décalage discret des points du contour. Après avoir effectué cette normalisation, la forme des objets peut être reconstituée sans perte d'information Les objets subissent uniquement une composition de translation, de rotation et de dilatation Seuls les coefficients de Fourier normalisés correspondant aux basses fréquences sont utilisés car ils contiennent l'information de forme de l'objet, les hautes fréquences représentant du bruit de quantification. Le prétraitement décrit ci-dessus et consistant à extraire les coefficients de Fourier normalisés d'un objet tridimensionnel, 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 ap- prend 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 La même classe d'objets est présentée plusieurs fois au réseau de neurones jusqu'à ce que le réseau ne restitue plus aucune sortie fausse A titre d'exemple, en considérant la base de données d'images précédemment constituée à partir de trois objets tridimensionnels différents, les trois objets peuvent être répartis en 6 classes différentes de la façon suivante: les classes O et 1 correspondent à l'objet n'1 vu sous un angle azimutal égal respectivement à O' et à 30 les classes 2 et 3 correspondent à l'objet N 02 vu sous un angle azimutal égal respectivement à O et à 30 les classes 4 et 5 correspondent à l'objet N 03 vu sous un angle azimutal égal respectivement à O et à 30 . Les sorties du réseau de neurones pour cet exemple doivent être au nombre de six et leurs valeurs seront par exemple les suivantes: (+ 1,-1, -1,-1,-1,-1) pour la classe O il (-1,+ 1,-1,-1,-1,-1) pour la classe 1 (1,-1,+ 1,-1,-1,-1) pour la classe 2 (-1,-1,-1,+ 1,-1,-1) pour la classe 3 (-1,-1,-1,-1,+ 1,-1) pour la classe 4 (-1,-1,-1,-1,-1,+ 1) pour la classe 5. 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 d'une classe ou de plusieurs classes d'objets, éven- tuellement 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'un coefficient de pondération 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 4. L'algorithme d'apprentissage utilisé est l'algorithme de rétropropagation. Dans une étape d'initialisation, 1, les coefficients de pon- dération W sont tout d'abord initialisés en utilisant une loi J de probabilité P(W ij) uniforme dans l'intervalle -M, +M L'ap- prentissage consiste alors en la modification des coefficients de pondération Wij, cette modification des coefficients se déroulant de la façon suivante: à un rang d'itération k donné, dans une étape 2, un objet exemple est extrait parmi différents exemples et les valeurs des coefficients de Fourier normalisés cor- respondant aux basses fréquences et calculées pour cet objet sont appliquées aux entrées du réseau de neurones Les sorties cor- respondantes du réseau sont alors calculées, dans une étape 3. Cet exemple étant caractéristique d'une classe d'objets donnée devra donner en fin d'apprentissage, en sortie du neurone associé à cette classe, un coefficient égal à + 1 ou voisin de + 1, les sorties des autres neurones du dernier niveau donnant des valeurs négatives aussi proches de -1 que possible Une fonction d'erreur est calculée dans une étape 4 en comparant les valeurs de sortie 0.du réseau aux valeurs de sortie S; désirées L'erreur sur la sortie, notée E, par rapport à la sortie désirée est mesurée par la valeur 1/2 (Oj-Sj) L'erreur de sortie totale E est la somme des erreurs E; ainsi calculées pour l'ensemble des sorties de j= 1 à N 3 Dans une étape 5 le calcul des poids, ou coefficients de pondération est effectué Les valeurs des coefficients de pondé- ration sont modifiées en tenant compte des modifications des coefficients de pondération effectuées au rang d'itération pré- cédent, k-1, ces valeurs étant pondérées par un coefficient de filtrage f 3, et de la dérivée de la fonction d'erreur pondérée par une valeur d'un paramètre -q, dit "vitesse d'apprentissage", de la manière suivante: AWIJ (k) = a E (k) + R AW (k-1) ij ' Cette modification des coefficients de pondération permet de faire varier les valeurs des poids WJ en fonction inverse du gradient d'erreur, tout en tenant compte des variations ef- fectué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 de la variation du coefficient de pondération. Ces coefficients étant modifiés, le rang de l'itération est incrémenté dans l'étape 6, un test est effectué, dans une étape 7, pour voir si tous les exemples ont été présentés au réseau de neurones, sinon 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;puis lorsque tous les exemples ont été présentés au moins une fois, un test est effectué dans une étape 8, afin de voir si tous les exemples ont été correctement classifiés sinon, le rang de l'ité- ration est remis à zéro et le processus est recommencé depuis le début jusqu'à 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 pro- ches de -1 pour toutes celles qui ne correspondent pas à l'exem- ple et proche de + 1 pour celle qui correspond à l'exemple, quel que soit l'exemple considéré. Les paramètres d'apprentissage q et de filtrage 13 sont choisis par l'opérateur, par exemple il pourra choisir ' = 0,005 et 1 = 0,985. Lorsque la phase d'apprentissage est terminée, le réseau de neurones est capable de reconnaître à quelle classe appartient un objet d'une image inconnue, son état est sauvegardé dans une étape 9, c'est-à- dire que 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 tridimensionnels. La figure 5 représente un organigramme de la phase de recon- naissance d'objets tridimensionnels. En phase de reconnaissance, dans une étape 51 une image nouvelle représentant la projection en deux dimensions d'un objet tridimensionnel est analysée Dans une étape 52, l'extraction du contour extérieur de l'objet présent sur l'image est effectuée et rééchantillonné dans une étape 53, de façon à obtenir un contour de vitesse uniforme de N points équidistants Le contour ré- échantillonné est ensuite décomposé en série de Fourier dans une étape 54, et dans une étape 55,les coefficients basse-fréquence de la décomposition en série de Fourier sont normalisés et cons- tituent alors les valeurs caractéristiques de l'objet à classi- fier Dans une étape 56, ces valeurs sont appliquées à l'entrée du réseau de neurones multi-couches et conduisent par l'applica- tion des coefficients de pondération fixés en f in de phase d'ap- prentissage, à des valeurs de sortie. Dans une étape 57, 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 jl 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 ( 1/2 (Oil -Oj)) 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. L'invention n'est pas limitée au procédé précisément décrit ci-dessus En particulier, il est possible d'utiliser un réseau de neurones qui ne soit pas seuillé, d'utiliser un modèle de neurone différent avec un algorithme d'apprentissage différent. REVENDICATIONS 1 Procédé de reconnaissance d'objets tridimensionnels par analyse d'image, caractérisé en ce qu'il consiste: dans une phase préalable, et pour un nombre fixé d'exemples d'objets tridimensionnels, à effectuer des projections en deux dimensions de ces exemples d'objets tridimensionnels de façon à obtenir un fichier d'images représentant les objets sous de nombreuses vues différentes réparties en plusieurs classes, à extraire le contour externe des objets, à décomposer ce contour en série de Fourier, et à normaliser les coefficients basse-fréquence de la décomposition en série de Fourier, dans une phase d'apprentissage, pour chaque exemple d'objet tridimensionnel, les valeurs des coefficients de Fourier normalisés sont utilisées pour ajuster, par approches sucessives, les valeurs des coefficients de pondération d'un réseau de neurones jusqu'à ce que les valeurs de sorties du réseau de neurones soient représentatives des différentes classes d'objets considérées. enfin, dans une phase de reconnaissance, les valeurs des coefficients de Fourier normalisés d'un objet à reconnaître 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é. 2 Procédé selon la revendication 1, caractérisé en ce que l'algorithme d'apprentissage est l'algorithme de rétro- propagation. 3 Procédé selon la revendication 2, caractérisé en ce que les neurones du réseau comportent un sommateur pondéré ( 10) associé à un dispositif de calcul d'une fonction non linéaire ( 20). 4 Procédé selon la revendication 1, caractérisé en ce que le réseau de neurones est un réseau seuillé.