Brevet FR3060147A1 — publié le 20180615

DOMAINE DE L'INVENTION L'invention concerne un procédé de caractérisation du cycle de marche d'un humain. ETAT DE LA TECHNIQUE La marche d'un humain est un phénomène cyclique. Un cycle de marche est décomposable en une pluralité de phases prédéterminées, c'est à dire des phases débutant et se terminant chacune lorsqu'un pied est dans une position prédéterminée. Ces phases sont de durées variables selon les sujets. Ainsi, la marche d'un sujet peut être caractérisée en identifiant les différentes phases du cycle de marche de ce sujet. Il a déjà été proposé dans le document - Hidden Markov Modeling of Human Normal Gait using Laser Range Finder for a Mobility Assistance Robot » par Papageorgiou et al., un procédé de caractérisation de la marche d'un sujet au moyen d'une chaîne de Markov cachée (généralement abrégé en HMM). Selon les procédés classiquement utilisés en HMM, des données biomécaniques (inertielles, cinématiques, etc.) représentatives du mouvement d'un sujet sont acquises par un capteur (inertiel, caméra infra-rouge, laser, etc.), pendant que le sujet marche, de façon à produire des courbes de grandeurs biomécaniques (accélération, vitesse, déplacement, position, etc.) caractérisant le cycle de la marche. Ces données biomécaniques font l'objet d'un étiquetage par un expert qui étudie les courbes et identifie à l'oeil nu les intervalles de temps au cours desquelles surviennent les différentes phases du cycle de marche du sujet. Toutefois, un tel étiquetage présente l'inconvénient d'être long, fastidieux, et demande à la personne chargée de l'étiquetage une grande expérience. RESUME DE L'INVENTION Le but principal de l'invention est de caractériser la marche d'un sujet de manière plus rapide et moins fastidieuse que l'état de l'art antérieur discuté ci-dessus. A cet effet, il est proposé un procédé de caractérisation d'un cycle de marche d'un sujet, le procédé comprenant des étapes de: - acquisition de données inertielles par au moins un capteur inertiel attaché au sujet au cours d'une marche du sujet, - apprentissage d'un modèle de Markov caché caractéristique de la marche du sujet mis en oeuvre au moyen d'un algorithme EM de Baum-Welch, le modèle de Markov caché étant défini par : 3060147 2 une séquence des états cachés Z N étant le nombre d'observations, les états cachés étant les phases du cycle de marche du sujet, le nombre de phases étant prédéterminé, et une séquence d'observations X = (xt, x2, ...,xt, xN ) issue des données inertielles 5 acquises, correspondant à au moins un cycle de marche, les paramètres de Markov À {11,A,B}, A étant la matrice de transition, B la matrice d'observation, et n le vecteur des probabilités initiales, - estimation de la séquence d'états cachés Z ...,zN) correspondant à chaque séquence d'observations X = (x1,x2,...,xt,...,xN) à l'aide des valeurs finales des 10 paramètres À {11,A,B} du modèle de Markov caché et de la séquence d'observations X; dans lequel l'étape d'apprentissage est non-supervisée : elle est mise en oeuvre par itérations successives, en utilisant en entrée uniquement la séquence d'observations X, afin de trouver les valeurs finales des paramètres = {11,A,B}, qui maximisent la probabilité d'avoir généré la séquence d'observations X ; les paramètres initiaux ÀO)) (7()), 13(°) } 15 étant initialisés avec des valeurs aléatoires ou à partir de connaissances a priori, chaque itération comprenant les sous-étapes suivantes: o une étape d'évaluation d'une espérance E d'une log-vraisemblance associée aux valeurs candidates des paramètres de Markov À(1) (7(0, A(i), B(0 }, à partir uniquement de la séquence d'observations X ; i est un entier naturel supérieur ou égal à 0 ; 20 o une étape de maximisation M, comprenant une estimation des valeurs candidates des paramètres de Markov .1(i+1) = pr(i+i),A(i+i),B(i+i)}, qui maximisent la valeur de la log-vraisemblance, o un test de convergence en se basant sur les valeurs de log-vraisemblance des itérations i et i+1, 25 o en fonction du résultat du test de convergence par rapport à une valeur seuil, une mise en oeuvre d'une nouvelle itération pour l'estimation de nouvelles valeurs, ou une utilisation des valeurs candidates e+1) = B(i+i)} comme valeurs finales des paramètres du modèle de Markov caché. 30 Le procédé tel que proposé peut être complété à l'aide des caractéristiques suivantes prises seules ou en combinaison lorsque cela est techniquement possible. Le modèle de Markov caché peut avoir une topologie de type gauche-à-droite. Il peut il y avoir 6 états cachés. Les phases du cycle de marche peuvent comprendre: 3060147 3 - une phase qui débute lorsqu'un premier pied du sujet entre en contact avec le sol et prend fin lorsque le deuxième pied du sujet quitte le sol, - une phase qui débute lorsque le deuxième pied quitte le sol et prend fin lorsque le centre de gravité du sujet se trouve au-dessus et à la verticale du pied droit, 5 - une phase qui débute lorsque le centre de gravité du sujet se situe au-dessus et à la verticale du pied droit et prend fin lorsque le deuxième pied entre en contact avec le sol, - une phase qui débute lorsque le deuxième pied entre en contact avec le sol et prend fin lorsque les orteils du premier pied quittent le sol, 10 - une phase qui débute lorsque les orteils du premier pied quittent le sol et prend fin lorsque le tibia du premier pied est vertical, - une phase qui débute lorsque le tibia du premier pied est orienté verticalement et prend fin lorsque le premier pied du sujet entre en contact avec le sol. Les données inertielles peuvent comprendre au moins une des données suivantes : 15 - une accélération suivant un axe longitudinal parallèle à la direction de déplacement du sujet, - une accélération suivant un axe latéral perpendiculaire à la direction de déplacement du sujet et parallèle au sol, - une accélération verticale par rapport au sol, 20 - au moins une vitesse angulaire autour d'un axe de rotation d'un pied du sujet. L'étape d'acquisition de données inertielles peut être réalisée par deux capteurs inertiels attachés au sujet au cours d'une marche du sujet pendant une période d'acquisition, chaque capteur inertiel est attaché à un pied du sujet. L'algorithme d'estimation de la séquence des états cachés Z = (zt, z2 , ..., zt, ..., zN) 25 peut être un algorithme de Viterbi. Le modèle de Markov Caché peut être continu ou discret. Lorsque le modèle de Markov Caché est continu, la valeur de la log-vraisemblance, peut être calculée sous l'hypothèse que les observations suivent une densité de mélange gaussienne, et dans lequel on définit une densité de probabilité: 30 bk (xt) = J\l' (xt, ilk,Ek) et les paramètres de Markov être alors : À - (Ir, A, [LE} La génération des valeurs candidates pour les paramètres peut être mise en oeuvre sous l'hypothèse que le modèle de Markov caché est continu, dans l'étape E de l'algorithme de Baum-Welch, peuvent être calculées une fonction auxiliaire Q ainsi que la probabilité a posteriori 1-(1) de l'état d'indice k à l'instant t étant donnée la séquence 3060147 4 d'observations X et la probabilité jointe (tql)kde l'état d'indice k à l'instant t et de l'état d'indice l à l'instant t-1, la fonction auxiliaire Q, maximisée par rapport à À dans l'étape de maximisation M, est l'espérance de la log-vraisemblance des données complétées : Q(yl, yl(q)) = E [L (a; X, Z)I X, .1(01 K N K K = 1 IE [zik IX, il(q)1 log (7k) +11 / IE[zt-i,tzt,k IX, il(q)] log (aki) 1=1 t=2 k=1 1=1 N K + / / E [ztk IX, yl(q)]/og(N(xt, ilk,Ek)) t=1 k=1 K N K K =IP(zi = kW, .1(q)) log (irk) +111P(zt-i = 1, zt = klX,2,(q))10g(akt) 1=1 t=2 k=1 1=1 N K +11P(zt = kW, .)(q))10 g (J\l' (xt, ilk,Ek)) t=1 k=1 K N K K N K =I T ta) 10 g (T E k) +111(teli)k 10 g (aki) +11 t(telk) 10 g (Ar (X t , µk, , Ek)) 1=1 t=2 k=1 1=1 t=1 k=1 5 où la log -vraisemblance des données complétées s'écrit: K N K K N K L(1; X, Z) =Izik log (7k) +IIIzt_tizt,klog(aki) +II ztklog (.7V(xt, [4, Ek)) 1=1 t=2 k=1 1=1 t=1 k=1 où zt,k est une variable binaire qui vaut 1 si zt est l'état d'indice k et qui vaut zéro sinon. La génération des valeurs candidates pour les paramètres, mise en oeuvre sous 10 l'hypothèse que le modèle de Markov caché est discret, peut comprendre une étape de quantification vectorielle des données inertielles pour produire les observations discrètes V = (v1, v2, ..., vm, ..., vivil, avec M le nombre total de symboles. Au cours de l'étape E de l'algorithme de Baum-Welch, peuvent être calculées une fonction auxiliaire Q ainsi que la probabilité a posteriori T(tc11) de l'état d'indice k à l'instant 15 t étant donnée la séquence d'observations X et la probabilité jointe (tcill>cle l'état d'indice k à l'instant t et de l'état d'indice l à l'instant t-1, la fonction auxiliaire Q, maximisée par rapport à À dans l'étape de maximisation M, étant l'espérance de la log-vraisemblance des données complétées : 20 Q(.1,.1(q)) = E[L(.1; X, Z) IX, .1(01 3060147 5 K N K K = 1 JE [zik IX, yl(q)] /0g(7k) + / / / lE[zt-1,izt,k1X, 21(0]/0g(akt) 1=1 t=2 k=1 1=1 N K + / / E [ztk IX, yl(q)]/og(bk(xt)) t=1 k=1 K N K K =IP(zi = kW, .1(q)) log (7k) +111P (zt-i = 1, z t = kIX,2.(q))1og(akt) 1=1 t=2 k=1 1=1 T (tqk) log (bk(xt)) N K +11P(Zt = k IX , À(q))log(bk (xt)) t=1 k=1 K N K K N K =1 t(ig) log(irk) +111109(akt) +II tak 1=1 t=2 k=1 1=1 t=1 k=1 la log -vraisemblance des données complétées étant : K N K K N K L (À; X, Z) =Izik log (7k) +III zt_tiz t,klog (aki) +II ztklog (bk (xt)) 1=1 t=2 k=1 1=1 t=1 k=1 où zt,k est une variable binaire qui vaut 1 si zt est l'état d'indice k et qui vaut zéro sinon, et où : bk(xt) = P(xt = vinizt = k)/ t E [1 N], k E [1 K], m E [1 M] 5 La quantification vectorielle peut utiliser un dictionnaire comprenant 40 vecteurs prédéterminés ; les observations étant alors formées par l'un des vecteurs du dictionnaire. Le procédé peut en outre comprendre une étape d'évaluation des performances sur la base de la séquence d'observations X où sont comparés la séquence des états cachés Z 10 estimés par le modèle de Markov caché et la séquence de référence Z' des états cachés obtenue par étiquetage pouvant être effectué par un expert. Il est également proposé un produit programme d'ordinateur comprenant des instructions de code de programme pour l'exécution des étapes du qui précède, lorsque ce programme est exécuté par au moins un processeur. 15 DESCRIPTION DES FIGURES D'autres caractéristiques, buts et avantages de l'invention ressortiront de la description qui suit, qui est purement illustrative et non limitative, et qui doit être lue en regard des dessins annexés où : 20 - La figure 1 représente schématiquement un système pour caractériser la marche d'un sujet selon un premier mode de réalisation de l'invention. 3060147 6 - La figure 2 est un organigramme d'étapes d'un procédé pour caractériser la marche d'un sujet selon un premier mode de réalisation de l'invention. - La figure 3 représente (a) les différentes phases d'un cycle de marches d'un sujet et (b) une modélisation de ces phases au moyen d'un modèle de Markov caché de type 5 gauche-droite. - La figure 4 est un organigramme d'étapes d'un procédé pour caractériser la marche d'un sujet selon un deuxième mode de réalisation de l'invention. - La figure 5 représente schématiquement un système pour caractériser la marche d'un sujet selon un deuxième mode de réalisation de l'invention. 10 - La figure 6 est un exemple de données d'accélération 3D recueillies pendant cinq cycles de marche d'un sujet. - La figure 7 est un exemple d'étiquetage manuel de données utilisant le relevé de la Force de Réaction au Sol (vGRF). - La figure 8 montre une évolution des phases de la marche obtenue avec (a) un 15 modèle de Markov caché continu MMCC, et avec (b) un modèle de Markov caché discret MMCD. Sur l'ensemble des figures, les éléments similaires portent des références identiques. DESCRIPTION DETAILLEE 20 1/ Système pour caractériser une marche En référence à la figure 1, un système pour caractériser la marche d'un sujet comprend un dispositif d'acquisition de données 1 et un dispositif de traitement de données 2. Le dispositif d'acquisition de données 1 comprend des moyens 10 de fixation au corps 25 d'un sujet, par exemple à une jambe ou un pied du sujet. Le dispositif d'acquisition 1 comprend en outre au moins un capteur 12 configuré pour acquérir des données inertielles, par exemple deux capteurs 12, un par pied. Ces données inertielles comprennent par exemple toute ou partie des données suivantes, pour chaque capteur 12: 30 - une accélération suivant un axe longitudinal parallèle à la direction de déplacement du sujet, - une accélération suivant un axe latéral perpendiculaire à la direction de déplacement du sujet et parallèle au sol, - une accélération verticale par rapport au sol, 35 - au moins une vitesse angulaire autour d'un axe de rotation d'un pied du sujet. 3060147 7 Le dispositif de traitement 2 est adapté pour recevoir les données acquises par le dispositif d'acquisition, par exemple via des moyens de communication 14, 22, comme par exemple des moyens de radiocommunication sans fil (Wi-Fi, Bluetooth, etc.). Le dispositif de traitement 2 comprend au moins un processeur 20 adapté pour 5 exécuter un programme d'ordinateur ayant pour fonction principale de fournir des indications sur la marche du sujet sur la base des données inertielles, et plus particulièrement caractériser les phases qui constituent le cycle de marche d'un sujet. Le processeur 20 est configuré pour mettre en oeuvre l'algorithme de Baum-Welch et l'algorithme de Viterbi. 10 2/ Rappels généraux sur les modèles de Markov cachés Un modèle de Markov caché est classiquement défini par : - une séquence d'observations X = (xt, x2, ..., xt, ..., xN ) - une pluralité d'états cachés Z = (z1,,z2,...,zt,...,zN), qui sont des données non 15 directement observables mais que l'on cherche à déterminer. Chaque état zt est susceptible de prendre une valeur 5k, ou k va de 1 à K, chacune de ces valeurs étant représentative d'une phase d'un cycle de marche. - un jeu de paramètres de Markov = (H, A, B}, A étant la matrice de transition associé au modèle, B la matrice d'observation associé au modèle, et n le vecteur des 20 probabilités initiales. En particulier, l'apprentissage d'un modèle de Markov caché est un procédé qui prend en entrée une séquence d'observations X connue, et qui produit en sortie un jeu de paramètres À - (H, A,B} qui maximise la probabilité d'avoir généré la séquence d'observations d'entrée X. 25 Par ailleurs, le décodage d'un modèle de Markov caché est un procédé qui prend en entrée une séquence d'observations X connue, un jeu de paramètres À - (H, A, B} préalablement déterminé, et qui estime une pluralité d'états cachés Z à partir de ces observations. 30 3/ Procédé de caractérisation de la marche En référence à la figure 2, un procédé de caractérisation de la marche d'un sujet au moyen du système précédemment décrit comprend les étapes suivantes. Est présenté dans ce qui suit un mode de réalisation dans lequel on suppose que le cycle de marche d'un sujet comprend les six phases suivantes : 3060147 8 - une phase S1 qui débute lorsqu'un premier pied du sujet entre en contact avec le sol et prend fin lorsque le deuxième pied du sujet quitte le sol, - une phase S2 qui débute lorsque le deuxième pied quitte le sol et prend fin lorsque le centre de gravité du sujet se trouve au-dessus et à la verticale du pied droit, 5 - une phase 53 qui débute lorsque le centre de gravité du sujet se situe au-dessus et à la verticale du pied droit et prend fin lorsque le deuxième pied entre en contact avec le sol, - une phase 54 qui débute lorsque le deuxième pied entre en contact avec le sol et prend fin lorsque les orteils du premier pied quittent le sol, 10 - une phase S5 qui débute lorsque les orteils du premier pied quittent le sol et prend fin lorsque le tibia du premier pied est vertical, - une phase S6 qui débute lorsque le tibia du premier pied est orienté verticalement et prend fin lorsque le premier pied du sujet entre en contact avec le sol. Au cours d'une étape préliminaire, le dispositif d'acquisition 1 est attaché au(x) 15 pied (s) d'un sujet à l'aide des moyens de fixation 10. Pendant que le sujet marche, chaque capteur 12 acquiert des donnes inertielles. Ces données sont acquises au cours d'une période suffisamment longue pour couvrir un cycle complet de marche du sujet (étape 100). Les données inertielles sont transmises au dispositif de traitement 2. 20 Le processeur 20 crée puis utilise un modèle de Markov caractéristique de la marche du sujet. Le processeur 20 est paramétré de sorte à utiliser, en guise d'observations X, les données inertielles acquises pendant le cycle de marche du sujet. Par ailleurs, les états cachés du modèle de Markov caché sont les six phases à identifier du cycle de marche. Ces états, inconnus, sont à déterminer. 25 Dans l'étape 200, le processeur met en oeuvre un apprentissage du modèle de Markov caché au moyen de l'algorithme de Baum-Welch. Le processeur 20 fait l'hypothèse que le modèle de Markov caché a une topologie de type gauche-à-droite. En effet, cette topologie est bien adaptée au caractère séquentiel des différents états à déterminer, c'est-à-dire des intervalles de temps des différentes 30 phases du cycle de marche du sujet. L'algorithme de Baum-Welch prend en entrée les observations X issues des données inertielles et produit un jeu de paramètres À - (H, A,B} qui maximise la probabilité d'avoir généré la séquence d'observations d'entrée X. 3060147 9 L'étape 200 d'apprentissage est non-supervisée. Autrement dit, l'algorithme de Baum-Welch utilise seulement les observations X comme données d'entrée, mais pas de données d'étiquetage déterminées empiriquement par un expert. L'algorithme de Baum-Welch génère des valeurs initiales À()) - (7()), AM,13(°) } pour 5 le jeu de paramètres À - {11,A,B} à déterminer. Ces valeurs initiales sont arbitraires ou tiennent compte de connaissances a priori. L'algorithme de Baum-Welch comprend plusieurs itérations successives. L'algorithme de Baum-Welch produit, à l'issue des itérations successives, le jeu de paramètres À= (11,A,B} qui maximise la probabilité d'avoir généré la séquence 10 d'observations X. Une itération d'indice i (i est un entier naturel supérieur ou égal à 0) de l'algorithme de Baum-Welch comprend une étape d'évaluation de l'espérance (E) où l'on calcule l'espérance de la vraisemblance en tenant compte des observations (étape 202), et une étape de maximisation (M) où l'on estime les paramètres du modèle maximisant la 15 vraisemblance trouvée à l'étape E (étape 204). L'itération i prend en entrée des valeurs candidates des paramètres de Markov À(0 - (7(0, A(i) , B(0} préalablement déterminées (dans le cas de la première itération, il s'agit des valeurs initiales ÀO)) - (Ir ()), AM,13(°) } choisies aléatoirement). Dans l'étape 202 d'évaluation de l'espérance E, le processeur 20 calcule plus 20 précisément l'espérance de la log-vraisemblance associée aux valeurs candidates des paramètres de Markov .1(0 = fir(i) , A(0 , B(0}, à partir uniquement de la séquence d'observations X. Dans l'étape de maximisation M, le processeur estime les nouvelles valeurs candidates des paramètres de Markov .1(i+1) - frr(i+1), A(i+1),B(i+1)}, qui maximisent la valeur de la log-25 vraisemblance. L'itération i comprend également l'étape 206 de test de convergence en se basant sur la valeur de la log-vraisemblance calculée, et en comparant à un seuil prédéterminé l'écart entre la valeur de la log-vraisemblance à l'itération i et celle à l'itération précédente. Si l'écart de log-vraisemblance n'est pas supérieur au seuil prédéterminé, une 30 nouvelle itération i+1 est mise en oeuvre ; celle-ci prenant en entrée les nouvelles valeurs candidates calculées au cours de l'itération i. Si l'écart de log-vraisemblance est supérieur au seuil prédéterminé, le processeur utilise les valeurs candidates .1(i+1) = frr(i+1)A(i+1)B(i+1)} comme valeurs finales des paramètres du modèle de Markov caché. L'étape d'apprentissage est alors terminée. 35 A ce stade, les états cachés Z de ce modèle sont encore inconnus. 3060147 10 Conformément au principe de décodage d'un modèle de Markov caché rappelé précédemment, dans l'étape 300, le processeur 20 estime les états cachés de ce modèle, c'est-à-dire la séquence d'états Z = (z1,,z2,...,zN), et ce à l'aide des valeurs finales des paramètres À (H , A, B} du modèle de Markov caché et de la séquence d'observations X. 5 Typiquement, pour tout i allant de 1 à N (N étant le nombre d'observations), la valeur z, estimée est l'instant de début (ou de fin) de la ieme phase du cycle de marche. L'étape d'estimation 300 est mise en oeuvre au moyen de l'algorithme de Viterbi. a) Modèle de Markov caché continu 10 Dans un premier mode de réalisation, le modèle de Markov caché utilisé est continu. Dans ce cas, les observations X peuvent directement être les données inertielles acquises. Ainsi, la génération de valeurs candidates pour les paramètres du modèle au cours de l'étape d'apprentissage est mise en oeuvre sous l'hypothèse que le modèle de Markov caché est continu. 15 Notamment, au cours de l'étape E de l'algorithme de Baum-Welch, sont calculées une fonction auxiliaire Q ainsi que la probabilité a posteriori r(ta) de l'état Sk à l'instant t étant donnée la séquence d'observations X et la probabilité jointe (i)k de l'état Sk à l'instant t et de l'état si à l'instant t-1. Par abus de langage, on identifie un état Sk par son indice k dans la suite du présent 20 texte. La fonction auxiliaire Q est maximisée par rapport à À dans l'étape de maximisation M. Cette fonction auxiliaire est l'espérance de la log-vraisemblance des données complétées : Q (À, À(q)) E[L(À; X, Z)1X, À(q)] K N K K = IE [zik il(q)1 log (Ir k) IE[zt-i,tzt,k il(q)llo g (aki) 1=1 t=2 k=1 1=1 N K E [ztk IX, yl(q)]/og(bk(xt)) t=1 k=1 K N K K = p(z1 = k I X,)(q)) log(7k) + 111P(Zt_i = l,zt il(q))10g (a kl) 1=1 t=2 k=1 1=1 N K +11P(Zt = À(q))lo g (bk(xt)) t=1 k=1 N K K N K T (il) 10 g(E k) +111((tPki 0 g (a ki) +11 (ta) 10 g(bk(xt)) 1=1 t=2 k=1 1=1 t=1 k=1 25 Par ailleurs, la log-vraisemblance des données complétées est : 3060147 11 K N K K N K L (À; X, Z) =Izik log(7k) +III z t_tiz t,klo g (aki) +II z tklo g (bk(xt)) 1=1 t=2 k=1 1=1 t=1 k=1 où zt,k est une variable binaire qui vaut 1 si zt = k (i.e xt provient du kième état à l'instant t) zéro sinon. En outre, la valeur de la log-vraisemblance est calculée sous l'hypothèse que les observations suivent une densité de mélange gaussienne, telle que : bk(xt) - N(xt, 11k, Ek) 5 Les paramètres de Markov déterminés au cours de l'étape d'apprentissage sont alors À = (TE, A, u' E}. b) Modèle de Markov caché discret Dans un deuxième mode de réalisation, le modèle de Markov est discret. En d'autres 10 termes, le modèle de Markov prend en entrée des observations discrètes ne pouvant prendre que des valeurs discrètes (symboles) dans un dictionnaire préalablement établi. Dans ce cas, le processeur met en oeuvre une étape de quantification vectorielle des données inertielles afin de produire les observations discrètes V = fyl, v2, ..., v'' ..., vml, avec M le nombre total de symboles du dictionnaire. 15 Par ailleurs, dans l'étape E de l'algorithme de Baum-Welch, sont calculées, une fonction auxiliaire Q ainsi que la probabilité a posteriori t(tql2 de l'état k à l'instant t étant donnée la séquence d'observations X et la probabilité jointe Ltak de l'état k à l'instant n et de l'état l à l'instant t-1. La fonction auxiliaire Q, maximisée par rapport à À dans l'étape de maximisation M, 20 est l'espérance de la log-vraisemblance des données complétées : (2(À, ,i(q)) = E[L(a, x,z)lx, Â.(q)] K N K K = 1 IE [zik IX, yl(q)] /0g(7k) +/ / / E[zt-1,1zt,k1X, 21(0]/0g(akt) 1=1 t=2 k=1 1=1 N K + / / E [ztk IX, yl(q)]/og(bk(xt)) t=1 k=1 K N K K =IP(zi = kW, .1(q)) log (7k) +111P (zt-i = 1, z t = kW, À(q))log (akt) 1=1 t=2 k=1 1=1 N K +11P(Zt = klX,À(q))10g(bk(xt)) t=1 k=1 3060147 12 K N K K N K =1 t(q) log(ik) +IIIeklog(aki) +II T(tq) log (bk(xt)) ik 1=1 t=2 k=1 1=1 t=1 k=1 La log vraisemblance des données complétées s'écrit: K N K K N K L (À; X, Z) =Izik log(7k) +III zt_tiz t,klo g (aki) +II ztklo g (bk(xt)) 1=1 t=2 k=1 1=1 t=1 k=1 où : bk(xt) - P (xt - vin /zt - k)/ t E [1 1\1],k E [1 K], m E [1 M] En outre, le processeur 20 peut mettre en oeuvre une étape d'évaluation des 5 performances du procédé sur la base de la séquence d'observations X ; l'évaluation comprenant une comparaison entre la séquence des états cachés Z estimés par le modèle de Markov caché et la séquence de référence Z' obtenue par étiquetage pouvant être effectué par un expert. 10 4/ Méthodologie suivie pour la réalisation de l'invention L'invention traite de la reconnaissance des phases du cycle de marche d'un humain au moyen de deux capteurs inertiels portables; un capteur est placé au niveau de chaque pied. L'utilisation de capteurs inertiels portables présente plusieurs avantages : faible coût, packaging ultra-miniature, faible consommation, faible poids et facilité de pose et de 15 retrait. Un Modèle de Markov Caché non supervisé discret/continu est proposé pour reconnaître six phases d'un cycle de marche. Le procédé proposé prend en compte l'évolution séquentielle des phases du cycle de marche. L'utilisation d'un Modèle de Markov Caché (MMC) dans un contexte non supervisé ne nécessite aucun étiquetage manuel des données qui peut constituer une tâche fastidieuse et longue dans le cas d'une analyse 20 de données massives. Pour évaluer les performances de la méthodologie proposée, les quatre critères suivants sont utilisés: taux de bonne classification, F-mesure, rappel et précision. Les expériences réalisées sur cinq sujets sains montrent des résultats satisfaisants et démontrent la capacité de l'approche proposée à reconnaître avec précision les phases d'un cycle de marche. 25 Il est fait référence dans ce qui suit à des documents connus de l'état de l'art de la technique. Ces documents sont listés en fin de la présente description. I. INTRODUCTION La marche est une forme particulière de mobilité et c'est également l'activité 30 physique humaine la plus importante en raison de sa forte incidence sur la majorité des activités quotidiennes. Le cycle de marche décrit la façon dont les êtres humains marchent 3060147 13 et il comporte des aspects spécifiques propres à chaque personne. Il s'agit d'un schéma cyclique impliquant des mouvements répétés des membres inférieurs et supérieurs, et également du tronc. Un cycle de marche complet commence lorsqu'un pied du sujet entre en contact avec le sol et se termine lorsque ce même pied entre de nouveau en contact 5 avec le sol. Le cycle de marche comporte deux phases principales : (i) la phase d'appui durant laquelle le pied touche le sol ; (ii) la phase d'oscillation, durant laquelle ce même pied ne touche pas le sol. La phase d'appui représente 60 % du cycle de marche tandis que la phase d'oscillation n'en représente que 40 %. Il existe des classifications plus détaillées du cycle de marche, allant de six à huit phases. 10 L'analyse du cycle de marche peut s'avérer être une tâche fastidieuse et longue, en particulier lorsqu'elle est effectuée manuellement. Il existe, par conséquent, un besoin croissant de développer des approches automatiques pour extraire les phases de marche. L'analyse automatique du cycle de marche reste un problème ouvert abordé dans différents domaines [1], [2], [3]. Le premier concerne le fait d'apprendre à des robots 15 humanoïdes à marcher en imitant la marche humaine [4], [5], [6]. Le deuxième concerne la conception et le contrôle de dispositifs d'assistance physiques portables, tels que les prothèses, les orthèses et les exosquelettes, dans le cadre de l'aide à la mobilité pour les personnes âgées et pour les patients atteints d'une parésie des membres inférieurs [7], [8], [9], [10]. Le troisième domaine d'application est la rééducation clinique à la marche [11]. 20 Depuis quelques années, l'analyse et le suivi des activités physiques de la vie quotidienne, en général, [12], [13], et de la marche en particulier, jouent un rôle important dans le contexte de la rééducation, de la prévention des chutes et du suivi médical en général. L'émergence de nouvelles technologies de capteurs portables et miniaturisés à faibles coût et consommation d'énergie s'impose comme une solution privilégiée pour l'analyse de 25 la marche chez l'être humain. Cette étude a été motivée par le problème de la reconnaissance automatique des phases d'un cycle de marche au moyen de capteurs inertiels portables placés sur les pieds d'un sujet. Un MMC (Modèle de Markov Caché) non supervisé discret/continu est utilisé pour reconnaître les phases de la marche. Six phases sont prises en considération dans cette étude, à savoir : mise en charge, milieu d'appui, fin 30 d'appui, début d'oscillation, milieu d'oscillation et fin d'oscillation. Les performances du procédé proposé sont évaluées en termes de taux de bonne classification, de F-mesure, de précision et de rappel. Les parties suivantes sont organisées comme suit. La Section II présente un aperçu des travaux connexes réalisés sur la reconnaissance automatique des phases d'un cycle de 35 marche. La Section III définit les phases du cycle de marche et la Section IV décrit le 3060147 14 protocole expérimental et l'étiquetage des données. La Section V présente l'approche proposée pour la reconnaissance des phases du cycle de marche. Les performances de cette approche sont évaluées et examinées dans la Section VI. 5 II. TRAVAUX CONNEXES L'analyse du cycle de marche joue un rôle important dans plusieurs domaines: analyse biomécanique de la marche, suivi médical, rééducation clinique, robotique d'assistance. Récemment, plusieurs procédés ont été proposés pour l'analyse automatique du cycle de marche. Ces procédés diffèrent principalement en termes de capteurs utilisés et 10 d'emplacement de ces derniers, mais aussi d'algorithmes de classification et de nombre de phases considérées. Dans [14], un système vidéo est utilisé pour la reconnaissance d'êtres humains sur la base de leur profil de marche. Toutefois, les conditions opératoires telles que l'éclairage, la présence d'obstacles (occlusion), le champ visuel restreint, peuvent conduire à une 15 dégradation des performances des systèmes vidéo [2]. D'autres types de capteurs, comme des capteurs de pression plantaire, sont également utilisés pour analyser le cycle de marche [2], [15], [16]. Même si ces capteurs présentent plusieurs avantages, tels qu'un faible coût et une précision de mesure, ils présentent toutefois certains inconvénients. Ils sont caractérisés par une mauvaise linéarité, nécessitent un traitement complexe des 20 signaux délivrés et ont une durée de vie limitée. Des capteurs de type télémètres laser montés sur des déambulateurs ont également été utilisés pour analyser le cycle de marche [17]. Toutefois, ces capteurs qui sont relativement onéreux, ne sont pas bien adaptés aux environnements encombrés et imposent plusieurs contraintes en termes de contexte d'utilisation. Récemment, des capteurs inertiels portables ont été utilisés pour l'analyse du 25 cycle de marche [1], [3], [18], [19], [20], [3]. Ces capteurs permettent de pallier les limitations mentionnées ci-dessus. Ils peuvent être utilisés aussi bien en environnement intérieur qu'en environnement extérieur. En outre, les nouvelles avancées technologiques dans le domaine des systèmes micro-électromécaniques (MEMS) ont permis de réduire le coût, la taille et la consommation énergétique des capteurs inertiels portables. 30 Dans [15], des capteurs de pression plantaire et un Modèle de Markov Caché (MMC) supervisé sont utilisés pour reconnaître six phases du cycle de marche. Le taux de bonne classification du système proposé varie entre 92,6 % et 95,6 %. Une autre étude utilisant des capteurs de pression plantaire est proposée dans [2]. Une approche basée sur un modèle de régression est proposée pour segmenter la phase d'appui en six phases. Un 35 gyroscope et trois capteurs de force de type FSR sont utilisés dans [20] pour reconnaître les 3060147 15 quatre phases d'un cycle de marche à l'aide d'un MMC. De même, un MMC est utilisé dans [17] pour analyser les phases de la marche à partir de données fournies par un télémètre laser monté sur un déambulateur d'aide à la marche. Une approche de reconnaissance de la marche basée sur un MMC supervisé et utilisant un gyroscope monté sur chaque pied est 5 présentée dans [19]. Le taux de bonne classification obtenu dans le cas d'un cycle de marche à quatre phases est supérieur à 95 %. Dans [21], un modèle de type Séparateurs à Vaste Marge (SVM) est utilisé pour classifier les cinq phases d'un cycle de marche à partir de données fournies par des capteurs de force, des capteurs de déformation et des accéléromètres placés sur chaque pied. Le taux de bonne classification obtenu pour la 10 reconnaissance des cinq phases d'un cycle de marche est d'environ 91%. La plupart des études susmentionnées soulignent la possibilité d'utiliser un Modèle de Markov Caché (MMC) pour reconnaître les phases du cycle de marche. Ces études utilisent des techniques de classification supervisées et nécessitent des données étiquetées. Cependant, l'étiquetage des données est une tâche fastidieuse et longue. 15 Dans le cadre de cette invention, un MMC non supervisé discret/continu est proposé pour la reconnaissance des phases du cycle de marche à l'aide de deux capteurs inertiels portables; un capteur est placé au niveau de chaque pied du sujet. L'utilisation d'un MMC dans un contexte non supervisé ne nécessite aucun étiquetage de données. Ceci peut s'avérer très utile dans le cas d'une analyse de données massives. En outre, le MMC permet 20 de prendre en compte les aspects multidimensionnels et séquentiels des données caractérisant le cycle de marche. Dans le modèle proposé, les phases du cycle de marche sont modélisées par un MMC gauche-droite, dans lequel chaque phase est représentée par un état caché. Les paramètres du MMC sont estimés de façon non supervisée à l'aide de l'algorithme de Baum-Welch [22]. La séquence la plus probable des phases de la marche est 25 alors estimée en utilisant l'algorithme de Viterbi [23]. III. DESCRIPTION DU CYCLE DE LA MARCHE HUMAINE Le cycle de marche correspond à une enjambée ou deux pas. Sa description peut différer d'un auteur à un autre mais elle tend aujourd'hui vers une définition unique. Par 30 convention, le cycle d'une marche normale débute lorsque le talon d'un pied touche le sol (contact du talon) et se termine lorsque le talon du même pied entre de nouveau en contact avec le sol. Le cycle de marche comporte deux phases principales : la phase d'appui et la phase d'oscillation. Selon [25], le cycle de marche peut être divisé en huit phases: contact initial, 35 mise en charge, milieu d'appui, fin d'appui, pré-oscillation, début d'oscillation, milieu 3060147 16 d'oscillation et fin d'oscillation Sans perte de généralité, on considère dans cette étude un cycle de marche comportant six phases, comme présenté dans [25]. En prenant le pied droit comme référence d'étiquetage, comme indiqué en haut de la figure 3, les phases considérées sont définies comme suit : 5 - Mise en charge (S1) : débute lorsque le pied droit touche le sol (contact du talon) et se termine lorsque l'autre pied quitte le sol (les orteils ne touchant plus le sol). - Milieu d'appui (S2) : débute lorsque le pied gauche quitte le sol et se termine lorsque le centre de gravité se trouve au-dessus et à la verticale du pied droit. - Fin d'appui (S3) : débute dès la fin de la phase de milieu d'appui et se termine 10 lorsque le pied gauche touche le sol. - Début d'oscillation (S4) : débute lorsque le talon du pied gauche touche le sol et se termine lorsque les orteils du pied droit quittent le sol. - Milieu d'oscillation (S5) : débute lorsque les orteils du pied droit quittent le sol et se termine lorsque le tibia du même pied se trouve en position verticale. 15 - Fin d'oscillation (S6) : débute dès la fin de la phase de milieu d'oscillation et se termine lorsque le pied droit touche le sol. IV PROTOCOLE EXPÉRIMENTAL ET ÉTIQUETAGE DES DONNÉES Les différentes étapes du procédé de reconnaissance des phases du cycle de marche 20 sont représentées sur la figure 4. A. Acquisition des données Les phases du cycle de marche sont identifiées à l'aide de deux capteurs inertiels 3- DOF MTx de Xsens® ; un capteur est porté par un sujet au niveau de chaque pied, comme 25 illustré sur la figure 5. Chaque unité MTx est équipée d'un accéléromètre/gyromètre triaxial mesurant l'accélération et la vitesse angulaire dans l'espace 3D. Les capteurs inertiels MTx sont interconnectés via un câble Xbus® à l'unité centrale appelée - Xbus Master » ; cette unité est placée au niveau de la taille du sujet. Les données recueillies sont transmises à un ordinateur via une liaison Bluetooth. La fréquence d'échantillonnage 30 est réglée à 100 Hz, ce qui est suffisant pour évaluer le cycle de marche. Les expérimentations ont été réalisées au laboratoire LISSI / Université de Paris-Est Créteil (UPEC) avec la participation de cinq sujets sains présentant des profils différents (moyenne d'âge : 27 ans, poids moyen : 79 kg). Il a été demandé à chaque sujet d'effectuer trente cycles de marche le long d'une ligne droite selon son propre style de 3060147 17 marche. La figure 6 montre l'évolution des données d'accélération du pied gauche et du pied droit sur cinq cycles de marche. Les données recueillies peuvent être exprimées comme suit : = (1), où 5 S est le nombre total de sujets. Pour chaque sujet s E [1, S], nous définissons un vecteur d'observation composé des données fournies par le capteur j à chaque instant tk, où k E [1, T(s)] et T(s) représente la durée totale de la séquence d'acquisition. On pose : 10 où - ax, ay et a, représentent respectivement les accélérations longitudinale, latérale et verticale - wx, wy et w, représentent respectivement les vitesses angulaires de tangage, de roulis et de lacet ; 15 - les indices r et l correspondent respectivement au pied droit et au pied gauche. B. Etiquetage des données Pour estimer avec précision les différents intervalles de temps de chaque phase, on utilise le système de cartographie de la pression plantaire F-Scan de la société Tekscan. Comme illustré sur la figure 5, ce système comprend : (1) deux semelles souples placées 20 chacune dans une chaussure ; chaque semelle est une matrice de capteurs de pression ; (2) une base permettant de transmettre les données issues des capteurs de pression de chaque semelle vers un enregistreur de données ; cette base est fixée à chaque pied par le biais de bandes auto-agrippantes ; (3) un enregistreur de données sans fil jouant le rôle de passerelle entre les deux bases et un ordinateur ; cet enregistreur est fixé à une ceinture 25 portée par l'utilisateur. L'étiquetage des données est réalisé manuellement en analysant les profils des Forces de Réaction au Sol au niveau de chaque pied (vGRF) [15]. La figure 7 montre un exemple d'étiquetage des phases du cycle de marche; le pied droit est ici utilisé comme référence pour l'étiquetage. 30 V. MÉTHODOLOGIE DE RECONNAISSANCE DES PHASES DU CYCLE DE MARCHE BASÉE SUR LE MMC A. Modèles de Markov Cachés 3060147 18 Le MMC est un outil puissant pour modéliser des séries temporelles. Il est utilisé dans de nombreuses applications, telles que la reconnaissance vocale [26], la reconnaissance d'écriture [27], l'identification de séquences d'ADN [28], la reconnaissance d'activités humaines [29], etc. Le MMC est un processus doublement stochastique [26] et part du 5 principe que le processus de Markov sous-jacent n'est pas observable (états cachés), mais qu'il peut être observé par d'autres processus stochastiques. Ce modèle consiste en une structure composée d'états, de probabilités de transition et d'un ensemble de distributions de probabilités. Selon le type d'observations, la distribution de probabilité peut être discrète ou continue. Dans le cas d'un MMC discret (MMCD), les observations sont des 10 symboles discrets issus d'un alphabet fini. Un MMCD est défini par un quintuplé À - (N,M,A,B,r(), avec : - K, le nombre d'états S = [Si, 52,..., sk, ..., sid, où l'état sk, à l'instant t, est défini par la variable zt. - M, le nombre d'observations distinctes : V= {vi, v2,..., vm, ..., vm}. 15 - A, la matrice des probabilités de transition notée A = [akil, telle que : akt = P(si = zt+ilsk = zt),1 1,k K. - B, la matrice de distribution des probabilités d'observations notée B[bk(m)1, telle 20 que : bk(m)= P(vinisk = zt), 1 k K, 1 0) 1, k E [1, K]2 5 La topologie gauche-droite, également appelée topologie de Bakis, est un modèle qui commence toujours au premier état (« le plus à gauche ») et dans lequel les transitions sont autorisées uniquement vers le même état ou vers des états ultérieurs (situés « à droite »). La contrainte sur les probabilités de transition, depuis un état s, vers un état sj, est 10 définie comme suit : (aki = 0 f or 1 > k) tt 1, k E [1, K] Trois problèmes majeurs doivent être résolus lorsque on utilise un MMC : le problème de reconnaissance, le problème d'analyse (décodage) et le problème d'apprentissage. 15 1) Le problème de reconnaissance : Soient A = [A, B, rrl et X = {xl, x2,..., xt, xN} respectivement un MMC et une séquence d'observations. Le problème de reconnaissance consiste à estimer la probabilité P(XI )). Cette probabilité peut être calculée en utilisant l'algorithme Forward-Backward [22] 20 2) Le problème de décodage : Ce problème consiste à trouver la séquence d'états Z = [z1, z2, zt, zN1 qui maximise la probabilité P(XI )). En d'autres termes, pour un modèle A et une séquence d'observations X, le problème de décodage consiste à estimer la séquence d'état Q qui maximise la probabilité P(XI )). La séquence d'état Z peut être estimée en utilisant 25 l'algorithme de Viterbi [23], [24]. 3) Le problème d'apprentissage : Soit X une séquence d'observations. Le problème d'apprentissage consiste à estimer les paramètres du modèle À maximisant la probabilité P(XI)1). Ces paramètres peuvent être estimés de façon itérative à l'aide de l'algorithme de Baum-Welch [30]. Cet algorithme 30 part d'un modèle initial À° = [Ao, Bo, no} qu'il met à jour de façon itérative jusqu'à convergence. Dans le cas d'un MMC Continu (MMCC), les observations ont des valeurs continues. Par conséquent, pour garantir la ré-estimation des paramètres du modèle de façon cohérente, 3060147 20 il convient de prendre en considération certaines restrictions sur le modèle de la fonction de densité de probabilité des observations. Dans cette étude, nous utilisons le modèle de mélange fini Gaussien. 5 B. Reconnaissance des phases du cycle de marche à l'aide d'un Modèle de Markov Caché Pour reconnaître les six phases de la marche considérées dans cette étude, on utilise un MMC non supervisé discret/continu. On utilise un MMC à six états avec une topologie gauche-droite, où chaque état correspond à une phase du cycle de marche, comme illustré 10 en bas de la figure 3. Cette topologie est bien adaptée en raison de l'aspect séquentiel des phases de la marche [17]. Dans la suite du texte, MMCD et MMCC font référence au MMC utilisé respectivement dans le cas d'observations discrètes et dans le cas d'observations continues (DHMM et CHMM respectivement en anglais). Cas du MMCC : les distributions d'émission pour chaque état sont modélisées en 15 utilisant une distribution gaussienne multivariée, telle que bk (x) = ckmMx, P-km,Elcm] m=1 où: - Cjm est le coefficient de mélange du m'eme mélange à l'état k ; 20 - .N'est la densité gaussienne multivariée ; - //km est le vecteur moyen du m'eme mélange à l'état k ; - 1km est la matrice de covariance du m'eme mélange à l'état k; Etant donné que le nombre d'états est égal à six, le seul paramètre à ajuster est le nombre de mélanges M. Ce nombre résulte d'un compromis entre la complexité de la 25 structure du MMCC et les performances de ce dernier en termes de taux de reconnaissance. Dans cette étude, chaque état est modélisé en utilisant un mélange de 3 gaussiennes à matrice de covariance diagonale. Dans le cas du MMCD, les observations continues sont transformées en observations discrètes au moyen du procédé de Quantification Vectorielle (QV). Ce procédé est utilisé 30 dans plusieurs applications, telles que la compression d'images, la compression de la parole, la reconnaissance des formes, etc. Il permet d'approximer un signal d'amplitude continue par un signal d'amplitude discrète. Autrement dit, il représente tout vecteur X c 3060147 21 Rd par un autre vecteur V = {vi, v2, v3, ..., vAi} à l'aide d'un dictionnaire (codebook) C = [C1, C2, C3, ..., CM) dans Rd de M vecteurs où : - C. = c2, Cd} est le ileme code - Rd est l'espace euclidien de dimension d. 5 L'algorithme des k-moyennes est l'un des algorithmes les plus simples et efficaces pour élaborer un dictionnaire (codebook) à partir de données inconnues. Cet algorithme possède comme entrée la matrice xs des observations, et comme sortie le vecteur des observations discrètes V. Une taille du dictionnaire de 40 éléments fournit le meilleur compromis entre l'erreur de quantification et les performances du modèle en termes de 10 taux de reconnaissance. Les paramètres des modèles MMCD et MMCC sont estimés en utilisant l'algorithme de Baum-Welch [26]. En ce qui concerne la reconnaissance des phases, on utilise l'algorithme de décodage de Viterbi pour estimer la séquence d'états, c'est-à-dire les phases de la marche. Dans cette étude, le MMC est développé en utilisant une boîte à outils Matlab 15 dédiée pour HMM [31]. VI. RESULTATS EXPERIMENTAUX A. Evaluation des performances Pour évaluer les performances de l'approche proposée pour la reconnaissance des 20 phases d'un cycle de marche, on utilise quatre critères : le taux de bonne classification (Accuracy), la F-mesure (F-measure)), le rappel (recall) et la précision (precision). Ces critères sont définis comme suit : où : Tp et Tn représentent, respectivement, le nombre d'exemples vrais positifs et 25 vrais négatifs. Fp et Fn représentent, respectivement, le nombre d'exemples faux positifs et faux négatifs. Le critère de Fp-mesure est défini comme suit : f1 4- 30 3060147 22 où 13 est un facteur de pondération. Dans cette étude, 13 est fixé à 1 pour attribuer la même importance aux critères précision et rappel. B. Résultats et discussions 5 Le tableau 1 ci-dessous résume les résultats obtenus pour chaque sujet à l'aide du MMCC et du MMCD. Ces résultats montrent la capacité du MMC à reconnaître avec précision les phases d'un cycle de marche. En effet, dans le cas du MMCC, les taux de bonne classification obtenus sont supérieurs à 79,30 %, tandis que le taux moyen de bonne classification est d'environ 82,62 %. Dans le cas du MMCD, les taux de bonne classification 10 sont supérieurs à 76,85% alors que le taux moyen de bonne classification est de 78,25%. MMCC MMCD Sujet 1 (%) 85,31 80,80 Sujet 2 (%) 84,91 78,35 Sujet 3 (%) 82,18 77,28 Sujet 4 (%) 79,30 77,02 Sujet 5 (%) 80,66 76,85 TABLEAU 1 : Taux de bonne classification pour chaque sujet Les performances obtenues en termes de F,-mesure par classe, F,-mesure, précision, 15 rappel, taux moyen de bonne classification et son écart type (std), sont donnés dans le tableau II. On constate que le MMCC donne de meilleurs résultats par rapport au MMCD. Ces résultats peuvent s'expliquer par le fait que, dans le cas du MMCD, la transformation des observations continues en observations discrètes est nécessaire. Cette transformation peut entraîner une perte d'information qui peut avoir des effets sur la qualité de l'estimation 20 des paramètres du modèle. Des tests effectués à l'aide du logiciel Matlab sur un processeur Intel® CoreTM i7-3687U CPU @ 2.10GHz 2.60 GHz avec une RAM de 8GB montrent que le MMCD nécessite un temps de calcul moins élevé que le MMCC. Pour reconnaître les 6 phases du cycle de marche d'un sujet, le MMCD nécessite un temps de calcul de 4,63s tandis que le MMCC en nécessite 16,69s. 25 Les matrices de confusion globales obtenues, respectivement, dans le cas du MMCC et du MMCD sont représentées dans les tableaux III et IV. On peut remarquer que la phase de mise en charge est reconnue avec une précision de 95,83 % dans le cas du MMCC. On obtient une performance également élevée dans le cas du MMCD dans la mesure où cette même phase est reconnue avec une précision de 93,13 %. Dans le cas du MMCC, on peut 3060147 23 également remarquer que des confusions se produisent entre : (i) la phase de milieu d'appui et la phase de fin d'appui avec un taux de confusion de 20,58 %, (ii) la phase de fin d'appui et la phase de début d'oscillation avec un taux de confusion de 14,43 %, (iii) la phase de milieu d'oscillation et la phase de fin d'oscillation avec un taux de confusion de 5 15,95 %. Dans le cas du MMCD, des confusions se produisent entre (i) la phase de milieu d'appui et la phase de fin d'appui avec un taux de confusion de 16,11 %, (ii) la phase de fin d'appui et la phase de début d'oscillation avec un taux de confusion de 13,30 %, (iii) la phase de pré-oscillation et la phase de milieu d'oscillation avec un taux de confusion de 13,87 %, (iv) la phase de milieu d'oscillation et la phase de fin d'oscillation avec un taux de 10 confusion de 23,48 %. Ces confusions peuvent s'expliquer par le fait que les étiquettes de référence (vraies étiquettes ou vraies classes) sont élaborées manuellement par l'expert. Des erreurs d'étiquetage peuvent se produire notamment dans le cas des transitions entre phases. Fi_Mesure par classe F1_ Préci- sion Rap- pel Taux de Mesure bonne classification 1 2 3 4 5 6 MMCD (%) 92,45 79,30 74,88 76,07 67,83 79,01 78,28 78,25 87,32 78,25+1,63 MMCC (%) 92,58 80,87 79,18 79,58 76,55 86,73 82,71 82,62 82,79 82,62+72,61 15 Tableau II : Fi_Mesure par classe, Fi_Mesure, précision, rappel, taux moyen de bonne classification et son écart type 3060147 24 51 S2 S3 54 S5 56 S1 (%) 95,83 4,16 0 0 0 0 S2 (%) 11,19 84,68 4,12 0 0 0 S3 (%) 0 20,58 77,70 1,70 0 0 S4 (%) 0 0 14,43 75,00 10,56 0 S5 (%) 0 0 0 11,77 78,45 9,76 S6 (%) 0 0 0 0 15,95 84,05 Tableau III : Matrice de confusion globale obtenue dans le cas du MMCC 51 S2 S3 54 S5 56 S1 (%) 93,13 6,86 0 0 0 0 S2 (%) 8,34 80,80 10,85 0 0 0 S3 (%) 0 16,11 74,31 9,57 0 0 S4 (%) 0 0 13,30 75,77 10,92 0 S5 (%) 0 0 0 13,87 68,98 17,13 S6 (%) 0 0 0 0 23,48 76,51 Tableau IV : Matrice de confusion globale obtenue dans le cas du MMCD 5 La figure 8 représente les phases estimées obtenues dans le cas du MMCC et du MMCD pour cinq cycles de marche, ainsi que les données de référence étiquetées manuellement. Ces résultats montrent que les états cachés, c.à.d. les phases reconnues à la fois pour le MMCC et le MMCD suivent une évolution séquentielle qui correspond aux phases du cycle de 10 marche. En outre, le MMCD et le MMCC fournissent une segmentation précise des données par rapport aux étiquettes de référence. Dans certains cas, on peut observer que les phases reconnues ne correspondent pas aux étiquettes de référence. Ce phénomène se produit généralement pendant les transitions entre phases dans la mesure où les phases d'un cycle de marche sont modélisées en utilisant un MMC à topologie gauche-droite. 15 VII. CONCLUSION ET PERSPECTIVES Dans cette étude a été présentée une approche de reconnaissance des phases d'un cycle de la marche humaine basée sur l'utilisation de seulement deux capteurs inertiels portables ; un capteur est porté par un sujet au niveau de chaque pied. Un MMC non 20 supervisé discret/continu à topologie gauche-droite est utilisé pour modéliser l'apparition 3060147 25 séquentielle des phases du cycle de marche et les transitions entre ces phases. L'utilisation d'un MMC dans un contexte non supervisé est très utile pour classifier une grande quantité de données non étiquetées en différentes phases du cycle de marche. Les résultats obtenus avec des sujets sains sont satisfaisants et démontrent l'efficacité de l'approche proposée. 5 Ce travail peut être étendu selon plusieurs directions. Références bibliographiques [1] C. Nickel, C. Busch, S. Rangarajan, and M. Mobius, "Using hidden markov models for accelerometer-based biometric gait recognition," in Proceedings of the 7th IEEE 10 International Colloquium on Signal Processing its Applications (CSPA), 2011, pp. 58-63. [2] S. Mohammed, A. Same, L. Oukhellou, K. Kong, W. Huo, and Y. Amirat, "Recognition of gait cycle phases using wearable sensors," Robotics and Autonomous Systems, 2014. [3] A. Rampp, J. Barth, S. Schulein, K.-G. Gasmann, J. Klucken, and B. M. Eskofier, "Inertial sensor-based stride parameter calculation from gait sequences in geriatric 15 patients," Proceedings of the IEEE Transactions on Biomedical Engineering, vol. 62, no. 4, pp. 10891097, 2015. [4] K. Hirai, M. Hirose, Y. Haikawa, and T. Takenaka, "The development of honda humanoid robot," in Proceedings of the IEEE International Conference on Robotics and Automation, 1998, pp. 1321-1326. 20 [5] J. Yamaguchi, E. Soga, S. Inoue, and A. Takanishi, "Development of a bipedal humanoid robot-control method of whole body cooperative dynamic biped walking," in Proceedings of the IEEE International Conference on Robotics and Automation, 1999, pp. 368-374. [6] S. Collins, A. Ruina, R. Tedrake, and M. Wisse, "Efficient bipedal robots based on 25 passive-dynamic walkers," Science, vol. 307, no. 5712, pp. 1082-1085, 2005. [7] S. Mohammed, J. Moreno, K. Kong, and Y. Amirat, Intelligent Assistive Robots: Recent Advances in Assistive Robotics for Everyday Activities. Springer, 2015. [8] W. Hassani, S. Mohammed, and Y. Amirat, "Real-time emg driven lower limb actuated orthosis for assistance as needed movement strategy." in Robotics: Science and 30 Systems, 2013. [9] M. H. Thaut, G. Mcintosh, and R. Rice, "Rhythmic facilitation of gait training in hemiparetic stroke rehabilitation," Journal of the neurological sciences, vol. 151, no. 2, pp. 207-212, 1997. [10] D. P. Ferris, G. S. Sawicki, and A. Domingo, "Powered lower limb orthoses for gait 35 rehabilitation," Topics in spinal cord injury rehabilitation, vol. 11, no. 2, p. 34, 2005. 3060147 26 [11] J. F. Veneman, R. Kruidhof, E. E. Hekman, R. Ekkelenkamp, E. H. Van Asseldonk, and H. Van Der Kooij, "Design and evaluation of the topes exoskeleton robot for interactive gait rehabilitation," Proceedings of the IEEE Transactions on Neural Systems and Rehabilitation Engineering, vol. 15, no. 3, pp. 379-386, 2007. 5 [12] B. Najafi, K. Aminian, A. Paraschiv-lonescu, F. Loew, C. J. Buta, and P. Robert, "Ambulatory system for human motion analysis using a kinematic sensor: monitoring of daily physical activity in the elderly," Proceedings of the IEEE Transactions on Biomedical Engineering, vol. 50, no. 6, pp. 711-723, 2003. [13] J. Hwang, J. Kang, Y. Jang, and H. Kim, "Development of novel algorithm and real- 10 time monitoring ambulatory system using bluetooth module for fall detection in the elderly," in Proceedings of the IEEE 26th Annual International Conference on Engineering in Medicine and Biology Society, 2004, pp. 2204-2207. [14] A. Kale, A. Rajagopalan, N. Cuntoor, and V. Kruger, "Gait-based recognition of humans using continuous hmms," in Proceedings of the 5th IEEE International Conference on 15 Automatic Face and Gesture Recognition, 2002, pp. 336-341. [15] S. De Rossi, S. Crea, M. Donati, P. Rebersek, D. Novak, N. Vitiello, T. Lenzi, J. Podobnik, M. Munih, and M. Carrozza, "Gait segmentation using bipedal foot pressure patterns," in Biomedical Robotics and Biomechatronics (BioRob), 2012 4th IEEE RAS Et EMBS International Conference on. IEEE, 2012, pp. 361-366. 20 [16] K. Kong and M. Tomizuka, "Smooth and continuous human gait phase detection based on foot pressure patterns," in Proceedings of the IEEE International Conference on Robotics and Automation, 2008, pp. 3678-3683. [17] X. S. Papageorgiou, G. Chalvatzaki, C. S. Tzafestas, and P. Maragos, "Hidden markov modeling of human normal gait using laser range finder for a mobility assistance robot," in 25 Proceedings of the IEEE International Conference on Robotics and Automation, 2014, pp. 482487. [18] R. Williamson and B. J. Andrews, "Gait event detection for fes using accelerometers and supervised machine learning," Proceedings of the IEEE Transactions on Rehabilitation Engineering, vol. 8, no. 3, pp. 312-319, 2000. 30 [19] A. Mannini and A. M. Sabatini, "A hidden markov model-based technique for gait segmentation using a foot-mounted gyroscope," in Proceedings of the IEEE Annual International Conference on Engineering in Medicine and Biology Society, 2011, pp. 43694373. 3060147 27 [20] I. P. Pappas, T. Keller, S. Mangold, M. R. Popovic, V. Dietz, and M. Morari, "A reliable gyroscope-based gait-phase detection sensor embedded in a shoe insole," IEEE Sensors Journal, vol. 4, no. 2, pp. 268-274, 2004. [21] B. Huang, M. Chen, X. Shi, and Y. Xu, "Gait event detection with intelligent shoes," 5 in IEEE International Conference on Information Acquisition, 2007, pp. 579-584. [22] L. E. Baum and T. Petrie, "Statistical inference for probabilistic functions of finite state markov chains," The annals of mathematical statistics, pp. 1554-1563, 1966. [23] A. J. Viterbi, "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm," IEEE Transactions on Information Theory, vol. 13, no. 2, pp. 260-269, 10 1967. [24] G. D. Forney Jr, "The viterbi algorithm," Proceedings of the IEEE, vol. 61, no. 3, pp. 268-278, 1973. [25] J. Perry, J. R. Davids et al., "Gait analysis: normal and pathological function." Journal of Pediatric Orthopaedics, vol. 12, no. 6, 1992. 15 [26] L. R. Rabiner, "A tutorial on hidden markov models and selected applications in speech recognition," in Proceedings of the IEEE, 1989, pp. 257-286. [27] A. Krogh, M. Brown, I. S. Mian, K. Sjolander, and D. Haussier, "Hidden markov models in computational biology: Applications to protein modeling," Journal of molecular biology, vol. 235, no. 5, pp. 1501-1531, 1994. 20 [28] M. Liwicki, H. Bunke et al., "Hmm-based on-line recognition of handwritten whiteboard notes," in Tenth International Workshop on Frontiers in Handwriting Recognition, 2006. [29] D. Trabelsi, S. Mohammed, F. Chamroukhi, L. Oukhellou, and Y. Ami-rat, "An unsupervised approach for automatic activity recognition based on hidden markov model 25 regression," IEEE Transactions on Automation Science and Engineering, vol. 10, no. 3, pp. 829-835, 2013. [30] A. P. Dempster, N. M. Laird, and D. B. Rubin, "Maximum likelihood from incomplete data via the em algorithm," Journal of the royal statistical society. Series B (methodological), pp. 1-38, 1977. 30 [31] K. Murphy, "Hidden markov model (hmm) toolbox for matlab," online at http://www. ai. mit. edu/' murphyk/Software/HMM/hmm. html, 1998. REVENDICATIONS1. Procédé de caractérisation d'un cycle de marche d'un sujet, le procédé comprenant des étapes de: - acquisition (100) de données inertielles par au moins un capteur inertiel attaché au sujet au cours d'une marche du sujet, - apprentissage (200) d'un modèle de Markov caché caractéristique de la marche du sujet mis en oeuvre au moyen d'un algorithme EM de Baum-Welch, le modèle de Markov caché étant défini par : - une séquence des états cachés Z = (z1,,z2,...,zt,...,zN), N étant le nombre d'observations, les états cachés étant les phases du cycle de marche du sujet, le nombre de phases étant prédéterminé, et - une séquence d'observations X = (xt, x2, ...,xt, ..., xN ) issue des données inertielles acquises, correspondant à au moins un cycle de marche, les paramètres de Markov À - {11,A,B}, A étant la matrice de transition, B la matrice d'observation, et n le vecteur des probabilités initiales, - estimation (300) de la séquence d'états cachés Z = (z1,,z2,...,zt, ...,zN) correspondant à chaque séquence d'observations X = (x1,,x2,...,xt,...,xN) à l'aide des valeurs finales des paramètres À - (11,A,13) du modèle de Markov caché et de la séquence d'observations X; caractérisé en ce que l'étape d'apprentissage est non-supervisée : elle est mise en oeuvre par itérations successives, en utilisant en entrée uniquement la séquence d'observations X, afin de trouver les valeurs finales des paramètres = {11,A,B} , qui maximisent la probabilité d'avoir généré la séquence d'observations X ; les paramètres initiaux ÀO)) - (70)), AM, 13(°) } étant initialisés avec des valeurs aléatoires ou à partir de connaissances a priori, chaque itération comprenant les sous-étapes suivantes: o une étape d'évaluation d'une espérance E d'une log-vraisemblance associée aux valeurs candidates des paramètres de Markov À(1) - (7(0, A(i), B(0 }, à partir uniquement de la séquence d'observations X ; i est un entier naturel supérieur ou égal à 0 ; o une étape de maximisation M, comprenant une estimation des valeurs candidates des paramètres de Markov .1(i+1) = pr(i+1),A(i+1),B(i+1)}, qui maximisent la valeur de la log-vraisemblance, o un test de convergence en se basant sur les valeurs de log-vraisemblance des itérations i et i+1, 3060147 29 o en fonction du résultat du test de convergence par rapport à une valeur seuil, une mise en oeuvre d'une nouvelle itération pour l'estimation de nouvelles valeurs, ou une utilisation des valeurs candidates .1(i+1) = wi-Ei) A(i+i) B(i+i)} comme valeurs finales des paramètres du modèle de Markov caché. 5 2. Procédé selon la revendication précédente, dans lequel le modèle de Markov caché a une topologie de type gauche-à-droite. 3. Procédé selon l'une des revendications précédentes, dans lequel il y a 6 états cachés. 10 4. Procédé selon la revendication précédente, dans lequel les phases du cycle de marche comprennent: - une phase qui débute lorsqu'un premier pied du sujet entre en contact avec le sol et prend fin lorsque le deuxième pied du sujet quitte le sol, 15 - une phase qui débute lorsque le deuxième pied quitte le sol et prend fin lorsque le centre de gravité du sujet se trouve au-dessus et à la verticale du pied droit, - une phase qui débute lorsque le centre de gravité du sujet se situe au-dessus et à la verticale du pied droit et prend fin lorsque le deuxième pied entre en contact avec le sol, 20 - une phase qui débute lorsque le deuxième pied entre en contact avec le sol et prend fin lorsque les orteils du premier pied quittent le sol, - une phase qui débute lorsque les orteils du premier pied quittent le sol et prend fin lorsque le tibia du premier pied est vertical, - une phase qui débute lorsque le tibia du premier pied est orienté verticalement et 25 prend fin lorsque le premier pied du sujet entre en contact avec le sol. 5. Procédé selon l'une des revendications précédentes, dans lequel les données inertielles comprennent au moins une des données suivantes : - une accélération suivant un axe longitudinal parallèle à la direction de déplacement 30 du sujet, - une accélération suivant un axe latéral perpendiculaire à la direction de déplacement du sujet et parallèle au sol, - une accélération verticale par rapport au sol, - au moins une vitesse angulaire autour d'un axe de rotation d'un pied du sujet. 3060147 30 6. Procédé selon la revendication précédente, dans lequel l'étape d'acquisition de données inertielles est réalisée par deux capteurs inertiels attachés au sujet au cours d'une marche du sujet pendant une période d'acquisition, un capteur inertiel est attaché à chaque pied du sujet. 5 7. Procédé selon l'une des revendications précédentes, dans lequel l'algorithme d'estimation de la séquence des états cachés Z = (z1,,z2,...,zt,...,zN) est un algorithme de Viterbi. 10 8. Procédé selon l'une des revendications précédentes, dans lequel le modèle de Markov Caché est continu ou discret. 9. Procédé selon la revendication précédente, dans lequel, la valeur de la log-vraisemblance, dans le modèle de Markov caché continu, est calculée sous l'hypothèse que 15 les observations suivent une densité de mélange gaussienne, et dans lequel on définit une densité de probabilité: bk(xt) - J\r(xt, 11k,Ek) et dans lequel les paramètres de Markov sont : À - (Ir, A, ii, E} 10. Procédé selon la revendication précédente, dans lequel, la génération des valeurs 20 candidates pour les paramètres est mise en oeuvre sous l'hypothèse que le modèle de Markov caché est continu, et dans lequel, dans l'étape E de l'algorithme de Baum-Welch, sont calculées une fonction auxiliaire Q ainsi que la probabilité a posteriori t(tqi2 de l'état d'indice k à l'instant t étant donnée la séquence d'observations X et la probabilité jointe (tqii),cle l'état d'indice k à l'instant t et de l'état d'indice l à l'instant t-1, 25 la fonction auxiliaire Q, maximisée par rapport à À dans l'étape de maximisation M, est l'espérance de la log-vraisemblance des données complétées : Q (yl, yl()) = E [L(.1; X, Z)I X, .1(q)] K N K K - 1 E [zik IX, yl(q)] /0g(irk) +/ / / lE[zt-i,/zt,k IX, .1(01/0g(akt) 1=1 t =2 k=1 1=1 N K + / / E [ztk IX, yl(q)] lo g Pr (xt, P-k,Ek)) t =1 k=1 3060147 31 K N K K =1P(Z1 = kIX , À(q)) 10 g (TEk) +111P(Zt-i = 1, z t = klX,y1(q))10g(akt) 1=1 t=2 k=1 1=1 N K +11P(zt = kIX , .)(q))10 g Pr (xt, 14,>k)) t=1 k=1 K N K K N K =I T (IV 10 g (1T k) +111«),10 g (aki) +11 T (t72 10 g Pr (Xt, [1k, k)) 1=1 t=2 k=1 1=1 t=1 k=1 où la log-vraisemblance des données complétées s'écrit: K N K K N K L(.1; X, Z) =Izik log(irk) +IIIzt_tizt,klog(aki) +II ztklog (.7«xt, [4, Ek)) 1=1 t=2 k=1 1=1 t=1 k=1 où zt,k est une variable binaire qui vaut 1 si zt est l'état d'indice k et qui vaut zéro sinon. 11. Procédé selon la revendication précédente, dans lequel la génération des valeurs 5 candidates pour les paramètres est mise en oeuvre sous l'hypothèse que le modèle de Markov caché est discret, et dans lequel le procédé comprend en outre une étape de quantification vectorielle des données inertielles pour produire les observations discrètes V = (y1,1;2, ..., vin__ vivil, avec M le nombre total de symboles, et dans lequel, dans l'étape E de l'algorithme de Baum-Welch, sont calculées une fonction auxiliaire Q ainsi que la 10 probabilité a posteriori i(ta) de l'état d'indice k à l'instant t étant donnée la séquence d'observations X et la probabilité jointe (tql)kde l'état d'indice k à l'instant t et de l'état d'indice l à l'instant t-1, la fonction auxiliaire Q, maximisée par rapport à À dans l'étape de maximisation M étant l'espérance de la log-vraisemblance des données complétées : Q (À, À(q)) - E[L(À; X, Z)1X, À(q)] 15 K N K K = 1 IE [zik IX, yl(q)] /og (70 + / / / lE[zt-tizt,k1X, .1(0]/0g (akt) 1=1 t=2 k=1 1=1 N K + 1 1 [ztk IX, JEÀ(q)110 g (bk(xt)) t=1 k=1 K N K K - Ip(zi = kix,,i(o) log(7k) +111 P (zt-i = 1, zt = klX,P1))log(akt) 1=1 t=2 k=1 1=1 N K +11P(Zt = k IX À(q))10 g (bk (xt)) t=1 k=1 K N K K N K =1 1-(1(12 log(1k) +111(`,11)klog(aki) +II t( tkq) log (bk(xt)) 1=1 t=2 k=1 1=1 t=1 k=1 3060147 32 la log -vraisemblance des données complétées étant : K N K K N K Lg X, Z) = 1Z1k log (Irk) +IIIZt-1,1Z t,klOg (akt) +11ztklog(bk(xt)) 1=1 t=2 k=1 1=1 t=1 k=1 où zt,k est une variable binaire qui vaut 1 si zt est l'état d'indice k et qui vaut zéro sinon, et où : 5 bk(xt) = P(xt = Vm/Zt = k)I t E [1 N],k E [1 K], m E [1 M] 12. Procédé selon la revendication précédente, dans lequel la quantification vectorielle utilise un dictionnaire comprenant 40 vecteurs prédéterminés ; les observations étant formées par l'un des vecteurs du dictionnaire. 10 13. Procédé selon l'une des revendications précédentes 10, 11, 12, comprenant une étape d'évaluation des performances sur la base de la séquence d'observations X où sont comparés la séquence des états cachés Z estimés par le modèle de Markov caché et la séquence de référence Z' des états cachés obtenue par étiquetage pouvant être effectué 15 par un expert. 14. Produit programme d'ordinateur comprenant des instructions de code de programme pour l'exécution des étapes du procédé selon l'une de revendications précédentes, lorsque ce programme est exécuté par au moins un processeur. 20