Brevet FR2701134A1 — publié le 19940805

Procédé de reconnaissance automatique de formes volumiques La présente invention concerne un procédé de reconnaissance automatique de formes volumiques. Elle s'applique notamment aux domaines qui nécessitent la reconnaissance de formes à trois dimensions que ce soit en robotique pour la reconnaissance d'objets, en productique pour le tri automatique de pièces industrielles, en imagerie radar ou laser pour la reconnaissance de véhicules ou de bâtiments, en imagerie médicale pour la reconnaissance automatique d'organes ou de tumeurs, en biologie pour la classification automatique de micro-organismes, en microscopie à effet tunnel pour la classification automatique de structures moléculaires. La reconnaissance de formes dans un espace à trois dimensions reste un domaine encore peu exploré du fait des difficultés théoriques rencontrées pour l'obtention d'invariances lors des transformations géométriques, telles que les rotations, translations, facteurs d'échelle, déformations, qu il est nécessaire de réaliser dans l'espace à trois dimensions. Les procédés connus mettent en oeuvre des méthodes structurelles qui partent de l'hypothèse que les formes doivent être suffisamment simples pour pouvoir être décrites par un assemblage de polygones, cylindres ou d'ellipses. Des exemples de description de ces méthodes sont connus par exemple du livre de Herbert FREEMAN ayant pour titre "Machine Vision for Three Dimensional Scenes" New-York: Academic Press, 1990.Les problèmes rencontrés sont à la fois liés d'une part, au fait que les méthodes sont appliquées essentiellement à des formes très simples et d'autre part, au fait de leur importante complexité lorsque celles-ci s'attachent à prendre en compte des structures cylindriques ou ellipsoïdales par exemple. Ces méthodes présentent aussi l'inconvénient d'être peu robustes au bruit, lorsque par exemple il existe des points critiques pour lesquels une faible variation de forme réelle provoque une importante variation de sa description structurelle et par là conduit à une mauvaise reconnaissance.D'autre part, la description structurelle d'une forme qui conduit à une description hiérarchique à longueur variable a également pour inconvénient d'imposer l'utilisation d'un classifieur symbolique de reconnaissance, ce type de classifieur étant nécessairement moins performant qu'un classifieur numérique. Il existe cependant des méthodes numériques basées sur des calculs de moments invariants telles que celles décrites dans l'article de Messieurs Firooz A. SADJADI, Ernest L. Hall, ayant pour titre "Three-Dimensional moment invariants" publié dans IEEE-PAMI, vol. 2, n 2, de mars 1980, ou dans l'article de Chong-Huah LO, Hon-Son DON ayant pour titre "3D moments forms: their construction and application to object identification and positioning" paru dans IEEE-PAMI, vol. 11, ne10, d'octobre 1989.Cependant les procédés qui mettent en oeuvre ces méthodes sont difficilement exploitables à la reconnaissance d'objets réels, contrairement à la reconnaissance d'objets de synthèse, car elles sont confrontées aux problèmes habituellement associés aux méthodes à base de moments et qui sont caractérisés par une très forte instabilité numérique due à des élévations à des puissances élevées dans les formules de calcul des moments. Elles conduisent en effet à des moments qui ne sont plus invariants lorsqu'ils sont calculés sur des objets réels donc nécessairement bruités. De plus le nombre de moments invariants est faible, pas plus grand qu'une douzaine. Il s'ensuit un pouvoir discriminant insuffisant du fait qu'il existe alors un grand nombre de formes différentes qui conduisent aux mêmes moments.D'autre part, les développements théoriques de ces méthodes sont assez mal maîtrisés car les moments invariants utilisés sont en fait définis avec une grande part de hasard suite aux nombreuses astuces de calculs. Le but de l'invention est de pallier les inconvénients précités en proposant un procédé de reconnaissance de formes entièrement numérique qui fait un grand usage du calcul tensoriel en considérant chaque forme à reconnaître comme un vecteur de l'espace vectoriel des formes à trois dimensions, en utilisant comme base orthonormée de cet espace vectoriel les vecteurs propres commun aux opérateurs "carré du moment cinétique orbital" et "moment cinétique orbital" connus de la mécanique quantique. A cet effet, l'invention a pour objet un procédé de reconnaissance automatique de la forme volumique d'un objet dans un espace à trois dimensions caractérisé en ce qu'il consiste à décomposer la forme à reconnaître sur une base orthonormée de l'espace vectoriel des formes à trois dimensions formée des vecteurs propres communs aux opérateurs L2 et Lz connus de la mécanique quantique pour désigner le carré du moment cinétique orbital et le moment cinétique orbital selon l'axe z de particules, à calculer des tenseurs contravariants d'ordre 1 à partir du résultat de la décomposition, et à calculer les invariants géométriques par contraction tensorielle pour alimenter un classifieur de forme par ces invariants. L'invention a pour principal avantage qu'elle permet le traitement de formes quelconques en offrant une forte résistance au bruit. Elle a aussi pour avantage d'être entièrement numérique et de rendre possible l'usage de classifieurs numériques dont les temps de calcul sont indépendants de la complexité des formes à reconnaître. Elle offre aussi l'avantage d'être peu coûteuse en puissance de calcul et de ne pas nécessiter une constitution de modèles a priori. D'autres caractéristiques et avantages de l'invention apparaîtront ciaprès à l'aide de la description qui suit faite en regard des figures annexées qui représentent: - la figure 1 une vue d'ensemble du procédé selon l'invention sous la forme d'un organigramme; - la figure 2 les conventions angulaires adoptées pour la représentation de chaque point d'une forme en coordonnées sphériques. Selon l'organigramme de la figure 1, le procédé comporte une première étape qui consiste à acquérir une description dans l'espace à trois dimensions de la forme à reconnaître par tout dispositif adapté connu, par reconstruction tomographique à partir de plusieurs vues provenant d'un capteur passif caméra par exemple, ou à l'aide de capteurs actifs donnant une information de profondeur comme cela existe dans les installations radar, laser ou faisant usage d'ultrasons. Cette représentation de l'objet est normalisée à l'étape 2 en translation et en homotétie. Au cours de cette normalisation l'origine du repère dans lequel est décrit l'objet à reconnaître est ramenée sur un point particulier, par exemple son centre de gravité pour assurer la normalisation en translation. En choisissant comme unité de longueur la distance entre l'origine et le point de l'objet le plus éloigné de l'origine, la normalisation en homothétie est réalisée. Il existe cependant une autre possibilité pour effectuer cette normalisation en choisissant l'unité de longueur de telle sorte que le volume de l'objet soit ramené à une valeur standard, par exemple égale à un 1/2. Le procédé s'exécute ensuite en sui vant deux modes de représentation possibles, une première représentation surfacique qui est assez simple à réaliser mais qui peut présenter certaines ambiguïtés pour certains types d'objets et une deuxième représentation volumique plus compliquée. Dans le mode de représentation surfacique l'objet à reconnaître est représenté par une fonction w(9, ) qui représente la distance par rapport à une origine O du point de l'objet le plus éloigné dans la direction (0 O représentant dans le repère orthonormé (o,x,y,z) de la figure 2 l'angle (o,z,o,M) et + l'angle formé par l'axe ox avec la direction projetée de oM sur le plan o,x,y. La procédure de reconnaissance qui a lieu suivant les étapes 4, 5, 6, 7 et 8 de la figure 1 consiste à effectuer à l'étape 4 une décomposition de l'objet sur une base orthonormée formée des vecteurs propres communs aux opérateurs L2 et Lz connus notamment en mécanique quantique et représentant respectivement le carré du moment cinétique orbital et le moment cinétique orbital selon l'axe z et dont une description peut être trouvée dans les tomes 1 et 2 des livres publiés par Hermann, Paris 1973 de Messieurs Claude COHEN-TANOUDJI, Bernard DIU et Franck LALOË ayant pour titre "mécanique quantique".L'opérateur L2 s'écrit en coordonnée sphérique: L'operateur Lz est défini par la relation Lz = h # i ## Les vecteurs propres communs à ces deux opérateurs sont des fonctions harmoniques sphériques Ylm(0f&commat;. Ces fonctions constituent une base orthonormée de l'espace vectoriel de l'espace des formes à trois dimensions. Dans cette base l'opérateur de rotation prend une forme irréductible au sens de la théorie des groupes de sorte qu'il est impossible de trouver une autre base qui simplifie davantage l'opérateur de rotation.Les harmoniques sphériques sont calculées par récurrence à l'aide d'équations de la forme Le procédé consiste ensuite à considérer la forme à reconnaître comme un vecteur de l'espace vectoriel des formes à trois dimensions dont les composantes sont définies dans la base des harmoniques sphériques suivant la relation pour l = 0, 1, 2, ..., L et m = -l, ..., l-1, l. Dans la relation précédente L est une constante fixée une fois pour toutes. Plus L est grand plus l'analyse de la forme est fine et permet de différencier des formes très voisines mais les temps de calcul sont plus importants. En pratique une valeur de L = 5 est généralement suffisante pour pouvoir bien différencier des formes. L'étape 5 consiste ensuite à construire des tenseurs contravariants d'ordre 1 à partir des composantes cl obtenues dans la base des harmoniques sphériques à l'étape 4.Cette construction a lieu en calculant les coefficients 11(4,4)m1 du tenseur par la relation Il 12 #(l1, l2)lm = # # cl1m1 cl2m2 m1=-l1 m2=-l2 Dans cette relation les produits scalaires correspondent aux coefficients numériques réels de Clebsch-Gordan tels que définis dans les tomes 1 et 2 de mécanique quantique cité précédemment. ll(4,12)rniest calculé pour l1 = 0, 1, ..., L l2 = 0, 1, ..., l1 I =0,1,...,L etm=-l,...,l-1,1 L'étape 6 consiste à construire des invariants géométriques en transformant le tenseur contravariant d'ordre 1 en un tenseur covariant d'ordre 1 par conjugaison de ses composantes, puis en effectuant une multiplication contractée c'est-à-dire en multipliant le tenseur contravariant d'ordre 1 par un tenseur covariant de même ordre et en égalant les indices tensoriels. Le résultat de la multiplication est un tenseur d'ordre 0 c'est-à-dire un inva riant. Dans cette opération qui est effectuée à l'étape 6, les grandeurs suivantes sont calculées : N(l)=##[#]* m=-1 P(l,l1,l2)=##(l1,l2)#[#]* m=-1 Q(l,l1,l2,l3,l4)=##(l1,l2)#[#(l3,l4)#]* m=-1 N(1) est calculé pour les valeurs de 1 = 0, 1, ..., L, Le calcul des valeurs P(l,l1,l2) est limité aux indices entiers vérifiant simultanément les relations 1#l2#l1#l#L l1-l2#l#l1+l2 l2#l1 ou pair l1#l ou l2 pair De la même façon Q(l, l1,l2,l3,l4) est limité aux indices entiers vérifiant simultanément les relations 0#l2#l1#L 0#l4#l3#l1 1 l1-l2#l#l1+l2 l3-l4#l#l3+l4 l2#l1 ou l pair 14 i 13 oui pair L'opération de réduction qui est effectuée à l'étape 7 consiste à construire un ensemble de coefficients ou invariants réduits à partir des coefficients N, P et Q pourliquer ceux-ci à l'entrée d'un classifieur. Les coefficients réduits constituent un ensemble de nombres réels définies comme suit (on désigne par # et # la partie imaginaire d'un nombre complexe: n(l) = [ R{N(1)} ] 2 p(l,l1,l2) = H3({P(1,4,12)J) Si 1+11+12 est pair = H3(#{P(l,l1,l2)}) si l + l1 + l2 est impair q(l,l1,l2,l3,l4) = H4(#{Q(l,l1,l2,l3,l4)}) si l1 + l2 + l3 + l4 est pair = H4(#{Q(l,l1,l2,l3,l49}) si l1 + l2 + l3 + l4 est impair où Hn(a) = signe (a)##a#1 n Le classifieur utilisé dans l'étape 8 peut être par exemple un classi- fleur opérant suivant l'algorithme connu des K plus proches voisins ou un classifieur de Bayes ou encore un réseau de neurones.Pour adapter les paramètres internes du classifieur, il est nécessaire dans une phase préalable, de lui appliquer des jeux de coefficients n, p et q accompagnés chaque fois de l'indication de la classe de l'objet sur lequel ils ont été calculés. Lorsque l'objet est à décrire dans une représentation volumique, I'ob- jet à reconnaître est représenté également par une fonction (x, y, z) qui vaut 1 lorsque le point de coordonnées xyz se trouve dans l'objet et 0 dans le cas contraire. Dans ce cas la procédure de calcul des invariants consiste à décomposer l'objet sur une base orthonormée formée comme précédemment des vecteurs propres communs aux opérateurs L2 et Lz, cette base orthonormée de vecteurs propres communs aux opérateurs L2 et Lz étant nécessairement constituée de fonctions de la forme Oklm(X,Y,Z) = Rkl(r) Ylm(#,#) où (r, 0, 4 > ) désignent comme précédemment les coordonnées sphériques du point de coordonnées cartésiennes x, y, z et la fonction Ylm(#,#) est un harmonique sphérique. Rkl(r) peut être représenté par une fonction de la forme Comme précédemment la forme à reconnaître est considérée comme un vecteur de l'espace vectoriel des formes à trois dimensions, et ses composantes sur la base {#klm(x,y,z)} sont calculées suivant la relation pour: l=0,I,2,...,L 1-1,1 où K est un entier fixé une fois pour toutes. Une faible valeur de K, K = 2 par exemple, est cependant suffisante. Comme Cklm est un tenseur contravariant d'ordre 1, le tenseur ll(k1, k2, l1,l2)klm est calculé suivant la relation l1 l2 #(k1,k2,l1,l2)klm= # # ck1l1m1 ck2l2m2 m1=-l1 m2=-l2 avec 1 l1 = 0, 1, ..., L l2 = 0, 1, ..., l1 l = 0, 1, ..., L Comme précédemment les grandeurs m2lAm > représentent les coefficients de Clebsch-Gordan. De façon similaire à la reconnaissance des formes surfaciques les coefficients N, P et Q sont calculés par des relations de la forme: N(k,l) est calculé pour l=0, 1, ..., l P(k,l,k1,l1,k2,l2) est calculé pour: l#k,k1,k2#K 1#l2#l1#l#L I,-12 12 #l1 ou I pair l1#l ou l2 pair Q(k,l,k1,lk2,l2,k3,l3,k4,l4) est calculé pour: 1#k,k1,k2,k3,k4#K 0#l2#l1#L 0 1 l1-l2#l#l1+l2 13-14 l2#l1 ou l pair l4#l3 ou l pair La classification est également obtenue à partir d'un ensemble de coefficients réduits n, p et q définis à partir des coefficients N, P et Q suivant les relations n(k,l)=[#{N(k,l)}]# p(l,k1,l1,k2,l2)=H3(#{P(k,l,k1,l1,k2,l2)}) si l+l1+l2 est pair =H3(#{P(k,l,k1,l1,k2,l2)}) si l+l1+l2 est impair q(k,l,k1,l1,k2,l2,k3,l3,k4,l4)=H4(#{Q(k,l,k1,l1,k2,l2,k3,l3,k4,l4)}) si l1 + l2 + l3 + l4 est pair =H4(#{Q(k,l,k1,l1,k2,l2,k3,l3,k4,l4)}) si l1+l2+l3+l4 est impair où Hn(a) = signe(a).#a## La totalité ou un sous-ensemble des coefficients n, p et q est appliquée à l'entrée d'un classifieur, mettant en oeuvre par exemple l'algorithme connu de classification suivant les K plus proches voisins, soit à l'entrée d'un classifieur de Bayes ou encore à l'entrée d'un classifieur formé par un réseau de neurones multicouches. REVENDICATIONS 1. Procédé de reconnaissance automatique de la forme volumique d'un objet dans un espace à trois dimensions caractérisé en ce qu'il consiste à décomposer (1 ... 4) la forme à reconnaître sur une base orthonormée de l'espace vectoriel des formes à trois dimensions formée des vecteurs propres communs aux opérateurs L2 et Lz connus de la mécanique quantique pour désigner le carré du moment cinétique orbital et le moment cinétique orbital selon l'axe z de particules, à calculer (5) des tenseurs contravariants d'ordre 1 à partir du résultat de la décomposition, à calculer (6, 7) les invariants géométriques par contraction tensorielle pour alimenter un classifieur de forme (8) par ces invariants. 2. Procédé selon la revendication 1 caractérisé en ce que la description dans un espace à trois dimensions de l'objet subit au préalable une normalisation en translation (2) qui consiste à ramener l'origine du repère dans lequel est décrit l'objet sur un point particulier de l'objet tel que par exemple son centre de gravité. 3. Procédé selon la revendication 2 caractérisé en ce que l'objet subit immédiatement après la normalisation en translation une normalisation en homothétie consistant à choisir comme une unité de longueur la distance entre l'origine et le point de l'objet le plus éloigné de l'origine. 4. Procédé selon l'une quelconque des revendications 1, 2 et 3 caractérisé en ce que l'objet est décrit par une représentation surfacique x 4 > ) où w(0, 4 > ) est la distance entre l'origine et le point de l'objet le plus éloigné dans la direction (0, 4 > ) et où la base est formée par les fonctions harmoniques sphériques, Ylm (0,4 > ). 5. Procédé selon l'une quelconque des revendications 1 à 3 caractérisé en ce que l'objet est décrit par une représentation volumique w(x,y,z) où w(x,y,z) vaut 1 si le point est à l'intérieur de l'objet et 0 dans le cas contraire et en ce que la base est formée par un ensemble de fonctions Rkl(r)Ylm(#,#) où Ylm sont des harmoniques sphériques. 6. Procédé selon la revendication 5 caractérisé en ce que la fonction Rkl(r) est une fonction harmonique défini par la relation Rkl(r)=#2 sin(#kr). r 7. Procédé selon l'une quelconque des revendications 1 à 6 caractérisé en ce que les tenseurs contravariants sont formés à l'aide de coefficients de Clebsch-Gordan. 8. Procédé selon l'une quelconque des revendications 1 à 7 caractérisé en ce que les invariants sont calculés en multipliant les tenseurs contravariants par des tenseurs covariants de même ordre pour former un tenseur d'ordre 0 et en ce que les résultats des multiplications subissent une opération dite de réduction (7) avant d'alimenter le classifieur pour ne retenir que les parties réelles ou imaginaires de l'invariant. 9. Procédé selon l'une quelconque des revendications précédentes caractérisé en ce que le classifieur (8) est un réseau de neurones multicouches. 10. Procédé selon l'une quelconque des revendications 1 à 8 caractérisé en ce que le classifieur (8) est du type utilisant l'algorithme connu des K plus proches voisins. Il. Procédé selon l'une quelconque des revendications 1 à 8 caractérisé en ce que le classifieur (8) est un classifieur de Bayes.