Brevet FR2990787A1 — publié le 20131122

PROCEDE D'ANALYSE PARCIMONIEUSE DE SIGNAUX PAR APPROCHE NON-ORIENTEE L'invention concerne un procédé de décomposition parcimonieuse par approche non-orientée et un procédé d'apprentissage de dictionnaire non-orienté. L'invention concerne un procédé de décomposition de mouvements. Elle s'applique notamment aux domaines de la robotique, de la vision par ordinateur, de la statistique et de l'apprentissage. Dans l'espace tridimensionnel appelé aussi espace 3D, il est utile dans de nombreuses applications de pouvoir décomposer le mouvement dans le temps d'un objet composé de P points et de N échantillons temporels. Cet objet peut être décrit comme la somme de K vecteurs de base. Pour décrire cet objet, plusieurs modèles peuvent être envisagés. Un objet 3D peut être décrit comme N nuages de points 3D successifs A[n] pour n = 1...N. Chaque forme 3D instantanée A[n] C peut être décrite en utilisant l'expression : K API] = 1 a k[n] S k k=1 dans laquelle : 3*P II: (1) ak[n] C représente le coefficient instantané ; II: II: représente l'ensemble des réels ; Sk C II: 3*P représente les vecteurs de forme. L'inconvénient de ce modèle est que la base des vecteurs de formes est composée de formes particulières spécifiques à l'objet étudié et a besoin d'être ré-estimée pour chaque nouvel objet. Pour éviter ce manque de flexibilité, il est possible d'exploiter la dualité entre la base de formes et la base de trajectoires utilisées. La base de trajectoires est définie indépendamment des données. L'objet 3D est décrit comme P trajectoires temporelles 3D B[p] pour p = 1...P. Chaque trajectoire 3D B[p] C II: 3"N est définie par l'expression : &pl - bk[Plek (2) k=1 dans laquelle : bk[p] C *1 désigne les coefficients ; II: ek C .1 *N désigne les vecteurs de trajectoires. Dans ce cas, et comme cela est illustré avec la figure 1 a, une trajectoire temporelle 100 est décomposée en une somme 101 de vecteurs monodimensionnels 102, chaque vecteur étant pondéré par un coefficient tridimensionnel 103. De manière alternative, un signal multi-composantes 110 peut s'exprimer comme étant la somme 111 de motifs multi-composantes 112 pondérés par un scalaire 113 comme illustré avec la figure 1 b. Réduite à trois composantes, une trajectoire temporelle dans un espace 3D de N échantillons est vue comme la somme de trajectoires 3D. Dans ce cas, la décomposition de chaque trajectoire y C PZ" peut être décrite en utilisant l'expression : K (3) Y = 1 X kVk k=1 dans laquelle : Xk C II: représente les coefficients de pondération ; (1)k C II: 3*N représente les motifs 3D. Pour alléger la notation, l'indice p est omis dans la suite du fait que la description se concentre sur la trajectoire 3D d'un seul point. Dans le modèle de l'expression (2) et de la figure 1a, chaque trajectoire uni-composante ek s'appuyant un des motifs 1D est multipliée par trois coefficients, c'est-à-dire un coefficient par dimension. Dans le modèle de l'expression (3) et de la figure 1 b, chaque trajectoire tri-composantes est décomposée avec des motifs 3D (pk, chaque motif étant multiplié par le coefficient scalaire 113. Ainsi, une trajectoire correspond à une somme pondérée de plusieurs motifs 3D. L'avantage d'utiliser le modèle décrit par l'expression (3) et la figure lb est de travailler avec des trajectoires 3D dont les trois composantes peuvent être très différentes. Cependant, ces modèles nécessitent des dictionnaires de taille importante et la qualité de la décomposition est dégradée si un même mouvement est orienté de manière différente dans un même repère 3D. Un but de l'invention est notamment de pallier les inconvénients précités. A cet effet l'invention a pour objet un procédé de décomposition d'une trame de coordonnées tridimensionnelles y en une somme d'atomes trivariés cpk pondérés par un coefficient xk, une matrice de rotation Rk étant appliquée à ces atomes pondérés, le procédé comprenant les étapes suivantes appliquées de manière itérative : un recalage 3D de l'ensemble des atomes tridimensionnels obtenus à partir d'un dictionnaire i.ji non orienté, le recalage étant effectué en utilisant la technique de décomposition en valeurs singulières afin d'obtenir un coefficient xk et une matrice de rotation Rk pour chaque atome ; une sélection d'au moins un atome, de son coefficient associé xk et de sa matrice associée Rk de manière à obtenir une décomposition parcimonieuse de la trame de coordonnées tridimensionnelles ; un calcul du résidu de décomposition après prise en compte du dernier atome sélectionné, ledit résidu étant utilisé par l'étape de recalage 3D de l'itération suivante.30 Selon un aspect de l'invention, les atomes sélectionnés sont déduits du dictionnaire lp par décalages temporels r des noyaux le composant. Selon un autre aspect, le dictionnaire i.ji est normé et redondant. Dans un mode de réalisation, au moins un atome est choisi durant l'étape de sélection, ledit atome celui permettant d'obtenir la plus forte décroissance en valeur absolue de l'erreur quadratique moyenne est sélectionné. Une étape d'optimisation peut être appliquée après le calcul du résidu afin d'ajuster les coefficients de pondération xk et les matrices de rotation Rk des atomes sélectionnés, cette optimisation étant réalisée par projection orthogonale du signal y sur les atomes sélectionnés par minimisation des moindres carrés afin réduire le plus possible la valeur du résidu. Les coefficients de pondération xk et les matrices de rotation Rk sont par exemple optimisés de manière à ce que les coefficients xk soient mis à jour pendant que les matrices Rk sont fixées et vice versa, chaque mise à jour étant basée sur la technique de descente de gradient. L'invention a aussi pour objet un procédé d'apprentissage d'un dictionnaire composé d'au moins un noyau, ledit dictionnaire étant adapté pour la décomposition d'une trame de coordonnées tridimensionnelles. Le procédé d'apprentissage comprend les étapes suivantes appliquées de manière itérative et consistant en : une initialisation des noyaux à apprendre ; une décomposition non-orientée par application du procédé de décomposition décrit précédemment à une base de signaux prédéterminée ; une mise à jour des noyaux basée sur le critère du maximum de vraisemblance sous hypothèse de bruit banc gaussien.30 Les noyaux sont par exemple initialisés sur du bruit blanc uniforme et sont normés. Selon un aspect de l'invention, l'étape de mise à jour est basée sur une descente de gradient stochastique. L'invention a aussi pour objet un dispositif d'apprentissage de mouvements tridimensionnels mettant en oeuvre le procédé de décomposition décrit précédemment. D'autres caractéristiques et avantages de l'invention apparaîtront à l'aide de la description qui suit donnée à titre illustratif et non limitatif, faite en regard des dessins annexés parmi lesquels : - la figure la illustre un modèle de décomposition d'une trajectoire temporelle en une somme de vecteurs mono- composantes pondérés par des scalaires, un par dimension ; - la figure lb illustre un modèle de décomposition d'une trajectoire temporelle en une somme de motifs multicomposantes pondérés par des scalaires ; - la figure 2 un modèle de décomposition utilisant un modèle invariant à la rotation 3D; - la figure 3 présente un diagramme illustrant de manière simplifiée un mode de mise en oeuvre du procédé 3DRIOMP ; - la figure 4 donne un exemple de méthode de recalage tridimensionnel pouvant être utilisé par le procédé 3DRIOMP ; - la figure 5 présente un exemple d'étape d'optimisation de la décomposition pouvant être mise en oeuvre dans un mode de réalisation du procédé 3DRI-OMP ; - la figure 6 illustre un procédé d'apprentissage de motifs 3D a partir d'un ensemble de signaux pouvant être mise en oeuvre dans un mode de réalisation du procédé 3DRI-DLA ; - la figure 7a représente un exemple de dictionnaire comprenant six noyaux trivariés à l'initialisation de l'apprentissage ; - la figure 7b représente le même dictionnaire à la fin de l'apprentissage après application du procédé 3DRI-DLA ; - la figure 8 illustre les trajectoires 3D invariantes à la rotation associées à un dictionnaire NOLD ; - la figure 9a représente un exemple de trajectoire 3D originale, la figure 9b représente la même trajectoire reconstruite non-orientée et la figure 9c représente la trajectoire reconstruite orientée ; - la figure 10a représente un exemple de trajectoire 3D après rotation, la figure 10b représente la même trajectoire reconstruite non-orientée et la figure 10c représente la trajectoire reconstruite orientée. Le procédé de décomposition décrit ci-après traite des signaux tri- composantes. A noter que les signaux tri-composantes sont à distinguer de signaux dits tridimensionnelles. En effet, un signal temporel y C PZ" composé de N coordonnées 3D est parfois improprement appelé tridimensionnel. En fait, ce signal n'est pas tridimensionnel mais tri- composante, c'est-à-dire trivarié ou tricanal selon le modèle utilisé. Un signal tridimensionnel est de la forme y C I':N1*N2*N3, telle que les trames vidéo ou tout autre donnée cubique. Le procédé de décomposition parcimonieuse décrit ci-après utilise un modèle invariant à la rotation 3D. Ce modèle est désigné par l'acronyme 3DRI venant de l'expression anglo-saxonne « 3D rotation invariant ». 2 990 787 7 La figure 2 illustre ce modèle de décomposition. Celui-ci met en oeuvre une somme 204 de motifs 3D 202 afin de décomposer un signal multicomposantes 200. Aux motifs 204 sont adjoints un coefficient 201 et une matrice de rotation 203. Ce modèle de décomposition est défini par 5 l'expression : dans laquelle Rk C trivarié (pk. K y = 1 xkRkvk , k=1 (4) 3"3 représente la matrice de rotation associée au motif II: Chaque matrice de rotation Rk doit être orthogonale, c'est-à-dire qu'elle doit vérifier la condition noté Co et correspondant à l'expression 10 RkRkT=Id dans laquelle Id représente la matrice identité et (.)T représente l'opérateur « transposée ». En utilisant ce modèle, la trajectoire y peut être représentée comme la somme pondérée de motifs 3D pouvant tourner. Dans la suite de la description, les motifs 3D sont aussi appelés atomes. 15 La figure 3 est un diagramme illustrant de manière simplifiée un mode de mise en oeuvre du procédé de décomposition selon l'invention. Cette famille de procédés est désignée dans la suite de la description en utilisant le sigle 3DRI-OMP. Le procédé comprend une phase de démarrage 20 311, une phase de recalage tridimensionnel 312, une phase de finalisation de la décomposition 313 et une phase d'arrêt 314. L'ensemble des étapes mises en oeuvre par ce procédé sont décrites dans la suite de la description. Dans un premier temps, le problème que résout le procédé de décomposition est formalisé le principe général du procédé est introduit. Dans un deuxième 25 temps, le recalage tridimensionnel est décrit en détail. Ensuite, les autres étapes du procédé sont décrites afin de permettre une compréhension globale de cet exemple de mise en oeuvre du procédé selon l'invention. La décomposition d'un mouvement en utilisant un modèle 3DRI a pour objectif de déterminer les coefficients x = fxkli = trace (ABT); et où la fonction trace() est la somme des éléments diagonaux. avec (.)T représentant l'opérateur transposé. Le procédé décrit ci-après vise à résoudre ce problème et se base sur une optimisation non-convexe utilisant le principe de l'OMP, acronyme venant de l'expression anglo-saxonne « Orthogonal Matching Pursuit ». Ce procédé de décomposition est désigné dans la suite par le sigle 3DRI-OMP. Dans une deuxième partie, nous nous intéresserons aux motifs 3D et à la manière d'apprendre le dictionnaire de motifs le plus adapté aux données étudiées. Cet apprentissage fera appel à la méthode de décomposition que nous présentons maintenant. Les matrices R seront considérées comme toujours orthogonales et donc vérifiant la condition Co. Une transformation rigide composée d'une rotation 3D R et d'une translation spatiale T est considérée ici entre le motif trivarié (I) et le signal original y. Le problème orthogonal de Procrustes consiste à trouver les paramètres R et T tels que : minRAy -Rço-Tr (6) 2 990 787 9 Dans l'article de D. Eggert, A. Lorusso, et R. Fisher intitulé Estimating 3-D rigid body transformations: a comparison of four major algorithms, Machine Vision and Applications, vol. 9, pp. 272-290, 1997, les trois principales méthodes donnant une solution analytique pour ce problème 5 de recalage rigide 3D sont passées en revue. Une première méthode propose une décomposition en valeurs singulières, une deuxième méthode propose une décomposition par quaternions unitaires et une troisième méthode propose une décomposition par matrices orthonormales. D'autre part, le problème multi-vues reconstruit le signal y à partir 10 de plusieurs observations wk prises sous différents angles, comme indiqué dans l'article de B. Kamgar-Parsi, J. Jones, et A. Rosenfeld intitulé Registration of multiple overlapping range images: scenes without distinctive features, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, pp. 857-871, 1991. Puisque les différentes vues se recouvrent, le 15 problème est donné par l'expression : 2 minR,T y U Rkg;ek T k k=1 (7) dans laquelle : Rk représente la matrice de rotation ; Tk représente la translation associée au motif trivarié (pk. 20 Cette formulation est différente du problème exprimée par l'expression (5). En effet, dans l'expression (7), l'union des motifs est considérée mais pas la somme comme dans l'expression (5). Dans l'article de l'article de J. Gower, "Generalized procrustes analysis," Psychometrika, vol. 40, pp. 33-51, 1975, l'analyse de Procrustes généralisée est décrite et traite plusieurs éléments wk résout le problème donné par l'expression suivante : 2 Mini? 0 çoi-R11O(8) i Dans l'article de J. Gower et G. Dijksterhuis, intitulé Procrustes Problems, Oxford Univ. Press, Ed. Oxford Statistical Science Series, 30, 2004, de multiples problèmes de Procrustes sont examinés ainsi que plusieurs généralisations. Cependant, le problème tel que décrit par l'expression (5) n'est pas traité. Dans l'approche désignée par l'expression anglo-saxonne « 3D curve matching » et en comparaison avec le problème donné par l'expression (6), la translation spatiale n'est plus considérée et i.p(t) est un motif court translatable avec complétion de zéros pour avoir N échantillons. Le problème consiste à résoudre l'expression suivante : min/1 y(t) - R yi(t -r)112 (9) dans laquelle T représente le décalage d'échantillons. Le problème peut être résolu en calculant la matrice de recalage R optimale par la méthode basée sur les matrices orthonormales à chaque échantillon T. De plus, paramétrée de cette façon, la méthode n'est pas invariante à l'échelle puisqu'il n'y a pas de facteur d'échelle x dans l'optimisation. S'il n'y a aucun décalage, le problème illustré par l'expression (6) de recalage 3D est retrouvé. Quant à l'algorithme très connu ICP, acronyme venant de l'expression anglo-saxonne « Iterative Closest Point », celui-ci ne résout pas le problème donné par l'expression (5). Il permet de faire coïncider deux ensemble de points 3D, dont l'un est le sous ensemble de l'autre. Cet algorithme hautement non convexe résout le problème donné par l'expression suivante : min F,R,T 0 y - R ço, -Tr (10) dans laquelle : y représente un ensemble de N points 3D; (Pr un sous-ensemble de N points 3D parmi les n possible, avec h>N. De plus, l'algorithme ICP utilise des signatures de formes pour identifier les N indices F. Pour ce qui est de la décomposition tricomposantes, différents modèles traitant des signaux tricomposantes sont revus. Comme exposé dans l'Introduction, le modèle (1) décrit un objet 3D comme une combinaison linéaire de vecteurs de base de formes. Utilisant le modèle dual (2), l'objet est maintenant une combinaison linéaire de vecteurs de base de trajectoires. Il faut remarquer que ces deux contributions viennent du structure-from- motion de la communauté vision par ordinateur désignée habituellement par l'expression anglo-saxonne « computer vision ». Une projection orthogonale est utilisée pour estimer des structures 3D à partir de mouvements 2D. En traitement du signal, une base redondante composée de M>N éléments est appelée dictionnaire. Dans ce cas, les éléments du dictionnaire ne sont plus appelés vecteurs mais atomes. Le modèle de l'expression (3) a été introduit dans ce domaine, et le choix des atomes et l'estimation des coefficients sont faits par approximation parcimonieuse multivariée. Le modèle introduit par l'expression (4) permet aux atomes de tourner mais l'on doit estimer en plus les matrices de rotation associées. Dans la suite de la description, et dans le but de décrire le procédé de décomposition selon l'invention, la notion d'invariance par translation est introduite, puis la notion d'approximation parcimonieuse est expliquée et le principe de l'invariance par translation et par rotation 3D est présenté. Dans le cas d'invariance par translation, l'objectif est de coder avec parcimonie le signal y comme une somme de structures courtes appelées noyaux. Ces noyaux sont caractérisés indépendamment de leurs positions. Ce modèle est habituellement appliqué aux données temps-séries et évite les effets de blocs dans l'analyse de signaux périodiques de large période et donne un dictionnaire de noyaux compact. Pour la décomposition, un dictionnaire Y est utilisé. Ce dictionnaire comprend un ensemble de noyaux prédéfinis. On dit dans ce cas que le dictionnaire est compact. Les L noyaux du dictionnaire compact Y peuvent être translatés et sont répliqués à toutes les positions possibles afin de constituer les M atomes d'un dictionnaire (1). La décomposition du signal y est réalisée en une série d'étapes exécutées sur plusieurs itérations. Après chaque itération, l'erreur résiduelle E est estimée et la décomposition continue sur cette base. Les N échantillons du signal y, l'erreur résiduelle E et les atomes cp, sont indicés par le temps t. Les noyaux { im }1-1-1 peuvent être de longueurs différentes. Le noyau i.jii(t) est décalé à l'échantillon t pour former l'atome im(t- t). Une complétion de zéros est faite pour avoir N échantillons. L'ensemble cy1 contient les translations actives t du noyau im(t). Pour les quelques noyaux qui engendrent tous les atomes, le signal y est exprimé de la manière suivante : m L y(t)=Ixmvm(t)+ e(t)=II.K1,m(t-1-)+ e(t) (11) m-1 1-1 re o-, avec c(t) l'erreur résiduelle. Ainsi, le signal y est approché comme la somme pondérée de noyaux translatables i.p. On introduit maintenant la notion d'approximation parcimonieuse. Du fait de l'invariance par translation, le dictionnaire (I) est la concaténation de L matrices de Toeplitz et est L fois sur-complet. Puisque M > N, le dictionnaire est redondant et le système linéaire est donc sous-déterminé et accepte de multiples solutions. L'introduction de contraintes telles que la parcimonie permet de régulariser la solution. L'approximation parcimonieuse sélectionne K atomes actifs parmi les M possibles et calcule leurs coefficients associés pour avoir la meilleure approximation du signal y. Le problème de l'approximation parcimonieuse peut être formulée en utilisant l'expression : 2 tel que 04 K min, L (12) y(t) -II xi,K(t - 2) 1=1 recy, dans laquelle : K « M est une constante ; 11x110 représente le cardinal du vecteur x. Mais ce problème est NP-difficile, l'acronyme NP venant de l'expression anglo-saxonne « non-deterministic polynomial time ». Ainsi, les algorithmes de poursuites non-convexes résolvent séquentiellement ce problème, comme les algorithmes connus MP, acronyme venant de l'expression anglo- saxonne « Matching Pursuit » et OMP, acronyme venant de l'expression anglo-saxonne « Orthogonal Matching Pursuit ». En combinant les problèmes d'invariance par translation et par rotation 3D, le problème à résoudre pour décomposer le signal y peut s'exprimer analytiquement de la manière suivante : 14 - 1=1 recri min x,R tel que : K et V1 =1..L,V e Id (13) Le procédé de décomposition parcimonieuse décrit ci-après s'appuie sur une optimisation non-convexe pour résoudre ce problème. Le problème exprimé par l'expression (13) a deux cas particuliers déjà résolus. Le premier cas particulier correspond au fait que lorsque K=1, on retrouve le problème du « 3D curve matching » tel que précédemment défini par l'expression (9). Le deuxième cas particulier est que lorsque chaque Rk est égal à la matrice identité, on retrouve le problème d'approximation parcimonieuse décrit à l'aide de l'expression (12), et ce avec des signaux trivariés. Ce cas est résolu par l'algorithme Multivariate-OMP désigné par l'acronyme M-OMP comme montré dans l'article de Q. Barthelemy, A. Larue, A. Mayoue, D. Mercier et J. Mars intitulé Shift & 2D rotation invariant sparse coding for multivariate signais, IEEE Trans. on Signal Processing, vol. 60, pp. 1597- 1611, 2012. La figure 4 donne un exemple de méthode de recalage tridimensionnel pouvant être utilisé par le procédé 3DRI-OMP de décomposition parcimonieuse selon l'invention. Le problème de recalage exprimé précédemment par l'expression (6) est considéré ici avec un motif cp normé, mais sans translation spatiale. Les paramètres recherchés sont la rotation matrice de rotation R et le facteur d'échelle x : minx,ROy - xRçor tel que RRT = Id (14) Pour résoudre le problème du recalage 3D, une décomposition en valeurs singulières peut être mise en oeuvre. Pour cela, plusieurs méthodes sont envisageables. A noter que la technique de décomposition en valeurs singulières est désignée dans la suite de la description par l'acronyme SVD venant de l'expression anglo-saxonne « Singular Value Decomposition ». Plusieurs méthodes de décomposition sont décrites dans l'article de D. Eggert, A. Lorusso, and R. Fisher intitulé Estimating 3-D rigid body transformations: a comparison of four major algorithms, Machine Vision and Applications, vol. 9, pp. 272-290, 1997. Un exemple de méthode pouvant être mise en oeuvre dans le cadre du procédé de décomposition parcimonieuse 3DRI-OMP est décrit ci-après. D'autres méthodes permettant d'aboutir à un résultat équivalent peuvent également être utilisées. Dans une première étape 400, une matrice de corrélation Mc = y(pT est déterminée. Sa SVD est calculée ensuite déterminée 401 en utilisant l'expression suivante : (U,A1,V) = SVD(Mc) dans laquelle : UC Ai C V C II: 3*3 désigne la matrice des vecteurs d'entrée orthonormés ; II: II: 3*3 désigne la matrice contenant les valeurs singulières de Mc; 3*3 désigne matrice des vecteurs de sortie orthonormés. Une matrice A2 est définie telle que A2 = diag ( 1, 1, det(UVT) ) C 3*3 est II: ensuite utilisée pour trouver 402 une matrice de rotation optimale R en utilisant l'expression : R = U A2 VT Une valeur de corrélation x fournissant le facteur d'échelle est ensuite déterminée dans une quatrième étape 403 en utilisant l'expression : x = trace ( R cp yT ) = trace ( A2 A1 ) 0. dans laquelle : la fonction trace() est la somme des éléments diagonaux. Le procédé 3DRI-OMP illustré à l'aide de la figure 3 utilise comme données d'entrée un signal trivarié y C 11:3*1 à décomposer et un dictionnaire lp de noyaux translatables. Le dictionnaire est normé. Cela signifie que les noyaux composant ce dictionnaire sont normés. Etant donné ce dictionnaire redondant, c'est-à-dire sur-complet, le procédé produit une approximation parcimonieuse du signal y. Pour cela, une fois que l'exécution du procédé est déclenchée 300, une étape d'initialisation 301 alloue le signal étudié y 302 à un résidu E°. A l'itération courante k, l'algorithme sélectionne l'atome qui produit la plus forte décroissance en valeur absolue de l'erreur quadratique moyenne I.1 ek-1 112, habituellement désignée par l'acronyme MSE venant de l'expression anglo-saxonne « mean square error ». C'est équivalent à trouver l'atome recalé qui est le plus corrélé au résidu x ek-1 c si-, La valeur de corrélation Xkl,,c = trace (Rki,,x4ii(t-t) 1) ) est calculée pour chaque décalage T, Rki,,c étant la matrice optimale pour recaler i.p(t-t) sur ck-1(t). Ainsi, l'algorithme de recalage 3D 303 est appliqué pour chaque t et chaque 1=1 ..L. Le maximum des valeurs absolues des xkl,.., est ensuite recherché 305 afin de sélectionner l'atome optimal. L'atome optimal est caractérisé par son indice de noyau lk et sa position Ti'. Dans une étape ultérieure 306, le vecteur x accumule les 25 coefficients actifs, c'est-à-dire les coefficients non nuls, qui sont les maximums des valeurs de corrélation soit : X Pour choisir le moment d'arrêt de l'exécution du procédé, il est possible de mettre en oeuvre un critère d'arrêt prédéfini et de surveiller si ce critère est vérifié. Si ce critère c'est le cas, l'exécution du procédé se termine 309. Sinon, k est incrémenté et une itération supplémentaire 310 est exécutée. Le critère d'arrêt 308 peut être choisi parmi plusieurs candidats. A titre d'exemple, le critère d'arrêt peut se baser sur un seuillage sur k, sur un nombre d'itérations prédéfini, sur un seuillage sur la racine carrée de l'erreur quadratique moyenne II ci' II / II y II, ou sur un seuillage sur la décroissance de la racine carrée de l'erreur quadratique moyenne. Le résultat obtenu à l'aide de ce procédé est une approximation K-parcimonieuse de y en utilisant les éléments actifs sélectionnés : K -", K y =1 Xik ,rk Rik ,rk Y/1k (t Tk ) k=1 (16) Le procédé de décomposition parcimonieuse peut être également décrit à l'aide du pseudo-code donné ci-après. 1: initialisation : k = 1, résidu c° = y 2: répéter 3: pour I Le nombre d'itérations I peut être choisi constant ou fonction de k. De cette manière, les derniers coefficients ont plus d'itérations pour approcher la solution des moindres carrés que les premiers. Il faut noter aussi qu'il est inutile de faire la procédure d'optimisation à la première itération k=1 puisqu'il n'y a pas de corrélation dans le dictionnaire actif réduit à un seul atome. Une implémentation possible de la procédure d'optimisation pour résoudre le problème représenté par l'expression (15) a été décrit. D'autres solutions peuvent également être mises en oeuvre dans le cadre de l'invention pour améliorer l'optimisation des moindres carrés. Il est à noter que le procédé de décomposition parcimonieuse 3DRI-OMP décrit notamment avec la figure 3 a une complexité algorithmique en 0(N2). Une implémentation plus rapide est possible. Pour cela, chacun des neuf éléments des N matrices de corrélation Mc (1,t) = _k-1 E (t) Lpi(t-T)T peut être calculé par transformée de Fourier rapide avec une complexité en 0[N.log(N)] pour tous T. Ensuite les N recalages sont calculés en 0(N). La complexité résultante est donc de 0 [N.log(N)]. Le procédé peut être facilement étendu à de plus grandes dimensions, considérant y C 11:1)*N avec D>3. Dans ce cas, le sens physique de la matrice de transformation est perdu. L'extension modifie seulement le recalage tridimensionnel, en étendant la définition de la variable interne A2 = diag ( 1, ... 1, det(UVT) ) D*D La figure 6 illustre un procédé de d'apprentissage de motifs 3D à partir d'un ensemble de signaux. Avant de décrire en détails ce procédé, les techniques d'apprentissage les plus connues de l'état de la technique sont mentionnées. Le modèle introduit à l'aide de l'expression (1) décrit un objet 3D comme une combinaison linéaire de vecteurs de base de motifs. Etant donné que la base de formes est dédiée à l'objet étudié, elle doit être ré-estimée à chaque nouvel objet. Un algorithme EM généralisé peut être utilisé pour apprendre des formes tridimensionnelles adaptées aux données étudiées. Utilisant le modèle dual de l'expression (2) qui représente un objet 3D avec des vecteurs de base de trajectoires, un algorithme EM peut être utilisé pour apprendre des trajectoires 1D adaptées aux données étudiées. D'autres techniques existantes sont désignées par l'acronyme DLA venant de l'expression anglo-saxonne « Dictionary Learning Algorithm ». Ces techniques apprennent empiriquement un dictionnaire dédié à un ensemble de signaux. Ces techniques comprennent deux étapes exécutées alternativement. L'une des étapes a pour objectif l'extraction des principaux motifs. C'est une étape d'approximation parcimonieuse. Ces motifs sont ensuite appris dans une autre étape de mise à jour du dictionnaire. A la fin de l'apprentissage, chaque signal de l'ensemble peut être décomposé avec parcimonie sur ce dictionnaire. Les techniques DLA sont différentes des techniques EM car elles utilisent la parcimonie dans l'étape de décomposition. La parcimonie fait émerger des données les motifs informatifs. Le procédé décrit ci-après avec l'aide de la figure 6 permet de calculer un dictionnaire 3DRI à partir d'un ensemble de signaux trivariés. Un ensemble d'apprentissage de signaux trivariés Y={h}Qq=i est considéré et l'indice q est ajouté aux variables. Ce procédé d'apprentissage est désigné par le sigle 3DRI-DLA. Ce procédé traite successivement chaque signal d'apprentissage h 603. Au début de du procédé, les noyaux sont initialisés 600 sur du bruit blanc uniforme et sont normés. En suite, le procédé met en oeuvre une alternance en ligne de deux étapes. Une étape 601 correspond à une décomposition 3D parcimonieuse et une étape 602 correspond à une mise à jour du dictionnaire. La décomposition 3D parcimonieuse 601 peut être effectuée en utilisant le procédé 3DRI-OMP décrit précédemment. Pour cela, l'expression suivante peut être utilisée : 2 =argmin arg y q(t)-1 - 1-) tg oxil K et VI =1..L,V E ai,RirR = Id (20) dans laquelle : tq est une abréviation de l'expression « tel que ». L'étape de mise à jour du dictionnaire 602 est basée sur le critère du maximum de vraisemblance, sous hypothèse de bruit banc gaussien. Pour cela, l'expression suivante peut être utilisée : 2 = arg min, y q ( t ) - x, q r, q (t 1=1 tqVI=1..L,Oyf 111=1 et VI=1..L,V zEo-,,R,,,qR,71,,,q= Id (21) Ce critère est habituellement optimisé par descente de gradient. Pour effectuer cette optimisation, une descente de gradient stochastique basée sur le LMS peut être choisie. Il a la particularité de traiter les matrices de rotation 3D et il est donc désigné par le sigle 3DRI-LMS. L'itération courante est notée j. Pour I=1..L, chaque noyau trivarié t.p1 peut être mis à jour en utilisant l'expression suivante : Yhi() =Vfi + 2'2.1 x e g-1-1 (t+ (22) 0-/ dans laquelle : I désigne les indices limités au support temporel de ; 2 990 787 24 À2 désigne le pas de descente adaptatif, choisi tel que À21=1/ ; En outre, les noyaux sont normalisés à la fin de chaque itération, et leurs longueurs peuvent être modifiées en fonction de l'énergie présente sur leurs bords. 5 Les deux étapes 601, 602 sont appliquées à tous les signaux 604 de la base de signaux 603 utilisée en entrée du procédé. Pour terminer 605 l'exécution du procédé, différent critères d'arrêt peuvent être utilisés, comme par exemple le seuillage sur le rRMSE, acronyme venant de l'expression anglo-saxonne Relative Root Mean- 10 Squared Error », calculé sur l'ensemble d'apprentissage ou le seuillage suri, c'est-à-dire sur le nombre d'itérations. Suite à l'exécution du procédé d'apprentissage, les motifs élémentaires caractéristiques d'un ensemble de signaux ont été appris empiriquement dans le dictionnaire optimal qui donne conjointement des 15 approximations parcimonieuses pour tous les signaux de cet ensemble. Il est à noter que les procédés 3DRI-OMP et 3DRI-DLA sont indépendants du système de capture de mouvement utilisé. Ainsi, celui-ci peut être de type inertiel, magnétique ou optique avec des marqueurs actifs ou passifs. Tous ces systèmes d'acquisition fournissent des coordonnées 20 spatiales 3D qui sont les signaux de mouvements traités par nos méthodes. Les figures 7a et 7b donne un exemple d'ensemble de signaux appartenant à un dictionnaire non orienté. A titre d'illustration, les procédés 3DRI-DLA et 3DRI-OMP sont 25 appliquées à des signaux de mouvement du langage parlé-complété LPC. Ce langage associe des articulations labiales à des clés formées par la main. Par la suite, seuls les mouvements de la main sont étudiés. La main peut être placée dans différentes configurations correspondants aux consonnes et dans différents placements sur le visage correspondants aux voyelles. Les signaux sont acquis par un système d'acquisition optique, fournissant les coordonnées spatiales 3D d'un marqueur. 0=57 signaux bruts sont dérivés pour donner les signaux de vitesse vx, vy et v7. Ces signaux tridimensionnels sont utilisés comme signaux d'entrées pour l'application des procédés. Dans cet exemple, le procédé 3DRI-DLA est appliqué aux données décrites précédemment. Ce procédé d'apprentissage est comparée avec un procédé connu de type M-DLA. Un dictionnaire appris à l'aide du procédé 3DRI-DLA est dit non- orienté, et est désigné de la sorte en utilisant l'acronyme NOLD venant de l'expression anglo-saxonne « Non-Oriented Learned Dictionary », car les noyaux sont invariants à la rotation et non plus appris dans une orientation fixe comme c'est le cas avec un procédé de type M-DLA. Un dictionnaire NOLD est appris avec L=6 noyaux. Le dictionnaire ainsi obtenu est illustré à l'aide des figures 7a et 7b. Les lignes pleines 700, et en pointillées 701, 702 représentent les trois composantes vx, vy et v7. L'erreur rRMSE moyennée sur l'ensemble d'apprentissage est de 21.3%, avec K=15 atomes dans chaque décomposition. La figure 7a représente le dictionnaire de L=6 noyaux trivariés à l'initialisation et la figure 7b représente ce même dictionnaire à la fin de l'apprentissage, c'est-à-dire après que le procédé 3DRI-DLA ait été exécuté. Afin d'effectuer une comparaison, un dictionnaire orienté OLD, 25 acronyme venant de l'expression anglo-saxonne « Oriented Learned Dictionary » est appris avec le procédé M-DLA utilisé dans un cas trivarié avec et L=6 noyaux. Son erreur rRMSE est de 30.9 % avec K=15 atomes. Les signaux de vitesse sont intégrés afin de donner une représentation plus visuelle du dictionnaire. La figure 8 montre les trajectoires 3D invariantes à la rotation associées au dictionnaire NOLD. Les étoiles 800, 801, 802, 803, 804, 805 représentent le début des trajectoires. Du fait de l'intégration, des noyaux de vitesses différents peuvent donner des trajectoires très ressemblantes. Ces trajectoires, extraites par le procédé 3DRI-DLA, correspondent aux motifs élémentaires du langage gestuel LPC. Le procédé de décomposition parcimonieuse 3DRI-OMP est ensuite appliqué avec le dictionnaire NOLD, ce qui donne une décomposition adaptée et non-orientée. Les atomes principaux sont ceux de plus fortes amplitudes, et ils concentrent l'information pertinente. Les atomes secondaires codent les variabilités entre les différentes réalisations d'un même geste. La trajectoire du signal yq avec q=52, q représentant l'indice courant sur les 0=57 signaux, est reconstruite avec ses cinq atomes principaux. La reconstruction non-orientée avec le NOLD et celle orientée avec le OLD sont comparées à l'aide des figures 9a, 9b et 9c. Par exemple, le signal the y52 est reconstruit comme la somme des noyaux NOLD d'indices trois, quatre et six qui sont utilisés trois fois dans des orientations différentes. Ils sont spécifiés par les amplitudes et les rotations données par le 3DRI- OMP. La figure 9a représente la trajectoire 3D originale de y52, la figure 9b représente la trajectoire reconstruite non-orientée et la figure 9c représente la trajectoire reconstruite orientée. Il apparaît de la figure 9b que le noyau NOLD d'indice six est utilisé trois fois dans des orientations différentes, alors que sur la figure 9c, le noyau OLD d'indice six est utilisé deux fois, mais sans qu'il soit possible de changer d'orientation pour mieux coïncider avec la trajectoire originale. Maintenant, les signaux sont tournés de différents angles aléatoires et sont maintenant notés par (.)'. Le dictionnaire NOLD et le dictionnaire OLD appris précédemment sont conservés pour effectuer les décompositions des signaux tournés. Avec K=15, l'erreur rRMSE moyennée sur l'ensemble d'apprentissage est de 21.3% pour le cas non-orienté et 83.1% pour le cas orienté. Il est intéressant de remarquer que les erreurs rRMSE des décompositions non-orientées sont similaires dans les deux expériences. Comme dans l'expérience précédente, la trajectoire du signal tourné y52' est reconstruite sur ces noyaux principaux comme illustré à l'aide des figures 10a, 10b et 10c. La figure 10a représente la trajectoire 3D de la figure 10b représente la trajectoire reconstruite non-orientée et la figure 10c représente la trajectoire reconstruite orientée. Avantageusement, les reconstructions non-orientées des figures 9b et 10b sont identiques. En effet, les mêmes atomes sont utilisés avec les mêmes amplitudes. Seules les rotations changent. Ces rotations correspondent à l'angle aléatoire appliqué au signal y52. La propriété avantageuse d'invariance à la rotation des méthodes non-orientées est ainsi illustrée. A l'inverse, les méthodes orientées donnent comme résultats des reconstructions très différentes comme illustrées sur les figure 9c et 10c. On peut notamment remarquer que les atomes utilisés ne sont pas les mêmes pour chaque reconstruction. Cela démontre la limitation d'un dictionnaire orienté figé dans une direction particulière, cette limitation étant évitée de lorsque les méthodes de reconstructions invariantes à la rotation sont utilisées. L'approche non-orientée permet d'obtenir de meilleurs résultats de reconstruction que les données soient tournées ou non. En outre, elle permet l'obtention et l'utilisation d'un dictionnaire compact et dont les noyaux peuvent être tournés ainsi que des décompositions invariantes aux rotations 3D. L'approche non-orientée peut être mise en oeuvre en robotique, notamment dans le but de donner aux robots une démarche humaine et non plus machinale. Toujours en robotique, cette approche peut être mise en oeuvre dans des systèmes de reconnaissance biométrique permettant d'identifier un individu à partir des caractéristiques de sa marche. En effectuant une étape de classification sur les paramètres de nos décompositions, il est possible de faire cette reconnaissance. Plus généralement, cette approche peut être mise en oeuvre pour la reconnaissance de gestes 3D. En effet, l'invention peut aussi être mise en oeuvre pour le suivi d'objet, l'analyse de trajectoires, l'apprentissage de primitives du mouvement. Suite à ces traitements, il est alors possible d'effectuer de la reconnaissance de geste.