FR 2526199 A1 19831104 FR 8217713 A 19821022 La présente invention concerne l'analyse de la parole et porte plus particulièrement sur des systèmes d'alignement temporel dynamique pour la reconnaissance de configurations de parole. Les dispositifs de reconnaissance de parole permettent l'entrée directe d'information dians des systèmes de télécommunications, d'informatique et de commande Un dispositif de reconnaissance comporte de façon caractéristi- que un vocabulaire de référence enregistré de façon numéri- que, sous la forme de configurations acoustiques qu'on appelle des gabarits Une émission sonore d'entrée est convertie sous forme numérique et comparée aux gabarits de référence On sélectionne le gabarit le plus similaire en tant qu'identité de l'émission sonore d'entrée Orn peut trouver un examen général de la reconnaissance automatique de la parole dans un article de S E Levinson et M Y. Liberman intitulé "Speech Recognition by Computer", Scientific American, avril 1981, Vol 244, n O 4, pages 63-76. Pour comparer une configuration d'entrée, par exemple un mot prononcé, avec une référence, on divise cha- que mot en une séquence d'intervalles de temps Dans chaque intervalle de temps, on élabore des signaux représentatifs de caractéristiques acoustiques de la configuration de paro- le Pour chaque intervalle du mot d'entrée, on sélectionne un intervalle du mot de référence On élabore des signaux représentatifs de la similitude ou de la correspondance entre chaque paire d'intervalles sélectionnés, sous la dépendance des signaux de caractéristiques acoustiques On utilise les signaux de correspondance pour la séquence de paires d'intervalles du mot d'entrée et du mot de référence pour élaborer un signal représentatif de la similitude globale ou d'ensemble entre le mot d'entrée et un gabarit de mot de référence. Du fait qu'il y a de nombreuses manières diffé- rentes de prononcer le même mot, le décalage dans le temps des caractéristiques acoustiques qui constituent le mot est variable Différentes émissions du même mot, même par la meme personne, peuvent être largement décalées dans le temps. La sélection de paires d'intervalles de temps n'est donc pas necessairement liréaire Par exemple, le fait de faire correspondre les quatrième, cinquième et sixième intervalles de l'émission sonore d'entrée avec les quatrième, cinquième eu sixième intervalles, respectivemernt, du mot de référence, peut distordre la mesure de similitude et produire des erreurs inacceptables. On a développé des systèmes d'alignement temporel i O dynamique qui alignent les intervalles d'une configuration de test et d'une configuratiron de référence d'une mar ère efficace ou optimale L'alignemernt est optimal lorsque la mesure de similitude globale passe par un extrémum Par exemple, il se peut que le cinquième intervalle du mot de test doive être apparié avec le sixième intervalle du mot de référence pour obtenir la meilleure mesure de similitude. Dans le brevet U S 3 816 722, onr élabore des signaux de caractéristiques pour les intervalles de mots d'entrée et de référence On génère des signaux de corres- pondance locale entre goutes les paires possibles d'inter- valles de mots d'entrée et de référence, dans une plage ou une fenêtre donnée On sélectionne un chemin extrémal des signaux de correspondance locale, par un processus récursif de programmation dynamique La génération de tous les signaux de correspondance locale dans une fenêtre donnrée peut cependant être incommode Par exemple, dans un système à microprocesseur, le processus du brevet précité est rela- tivement lent. L'invertion a d 3 nc pour but de procurer un système perfectionné pour l'aligrtimenrt temporel de configuratiors je parole qui raccourcisse la généraicon de signaux de ccrres- porndance locale. L'inventionr porte sur un système destiné à aligner dans le temps une première corfiguration de parole avec une seconde configuration de parole On génère une séquence d'intervalles de temps de signaux de caractéristiques acous- tiques pour chaque configuration de parole Pour chaque signal d'intervalle de temps successif de la première confi- guration de parole, on génère un ensemble de signaux qui correspondent à des intervalles de temps candidats de la seconde configuration de parole On élabore un ensemble de signaux représentatifs de la correspondance entre les caractéristiques acoustiques de l'intervalle de temps cou- rant de la première configuration de parole et les signaux de caractéristiques acoustiques des intervalles de temps candidats de la seconde configuration de parole Sous la dépendance des signaux de correspondance des intervalles de temps précédents et courant de la première configuration de parole, on génère un signal pour chaque intervalle de temps candidat de la seconde configuration de parole et pour d'xeintervalle de temps courant de la première configura- tion de parole, et le signal qui est ainsi généré constitue une prédiction de la similitude entre les première et seconde configurations de parole, le long d'un chemin con- tenant l'intervalle de temps de la seconde configuration de parole et l'intervalle de temps courant de la première con- figuration de parole Sous la dépendance des signaux de prédiction de l'intervalle de temps courant de la première configuration de parole, on sélectionne l'un des interval- les de temps candidats de la seconde configuration de paro- le, pour la paire d'intervalles de temps associée à l'intervalle de temps courant de la première configuration de parole. L'invention sera mieux comprise à la lecture de la description qui va suivre d'un mode de réalisation et en se référant aux dessins annexés sur lesquels: La figure 1 montre un circuit de reconnaissance de parole à micro-ordinateur qui illustre l'invention; La figure 2 est un organigramme du fonctionnement d'ensemble du circuit de la figure 1; La figure 3 est un organigramme représentatif de l'invention; La figure 4 est un organigramme de l'opération d'alignement temporel dynamique du circuit de la figure 1 La figure 5 est un organigramme de la génération du signal de distance totale prédite, relatif à la figure 4; et La figure 6 est un diagramme illustrant la séquen- ce de fonctionnement du système de l'invention. La figure 1 montre un schéma synoptique général d'un dispositif de reconnaissance de parole à micro-ordina- teur conçu pour accomplir les fonctions de traitement numé- rique de signal de l'invention On peut utiliser le systè- me de la figure 1 pour identifier une émission sonore. Selon une variante, le système de reconnaissance de mots peut être réalisé avec du matériel numérique spécialisé, comme il est bien commu. En considérant la figure 1, on voit que le micro- ordinateur 100 comprend un dispositif d'entrée 101, un con- vertisseur analogique-numérique 102, un microprocesseur 103, une mémoire 104 et un dispositif d'utilisation 105 Un bus de données 106 interconnecte les bornes de données du con- vertisseur 102, du microprocesseur 103, de la mémoire 104 et du dispositif d'utilisation 105 Un bus d'adresse 107 interconnecte de façon similaire les bornes d'adresse respectives. Le convertisseur 102 peut être par exemple un cir- cuit intégré du type TDC 1 00 OJ fabriqué par TRW, Incorpora- ted, La Jolla, Californie, E U A Le microprocesseur-103 peut être par exemple un circuit intégré du type 8086 fabriqué par Intel Corporation, Santa Clara, Californie La mémoire 104 peut être par exemple constituée par des cir- cuits intégrés du type 2118 fabriqués par Intel Corporation. Le dispositif d'entrée 101 peut être par exemple un micro- phone, un téléphone,un dispositif d'enregistrement vocal ou un autre équipement de communication. Le dispositif d'utilisation 105 peut être par exem- ple un système de vérification de locuteur ou un dispositif de reconnaissance de mots prononcés Un dispositif de reconnaissance de mots prononcés est décrit en détail dans l'article de L R Rabiner, S E Levinson, A E Rosemberg et J G Wilpon intitulé, "Speaker Independent Recognition of Isolated Words Using Clustering Techniques", IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol ASSP-27, n O 4, pages 336-349, août 1979. On va considérer la figure 2 sur laquelle l'orga- nigramme 200 fait apparaître des cases d'opération et de décision représentatives de traitements exécutés par le microprocesseur 100 Sous l'effet du signal DEPART provenant du dispositif d'utilisation 105, le microprocesseur 103 est conditionné de façon à commencer les opérations de traite- ment de signal (case 205 sur la figure 2) Un signal de parole analogique provenant du dispositif d'entrée 101 est appliqué à l'entrée du convertisseur 102 (case 210) Le signal d'entrée est numérisé dans le convertisseurl O 2 (case 215) Le signal d'entrée numérisé est ainsi disponible pour le microprocesseur 103 Sous l'effet des signaux d'entrée numérisés, le microprocesseur 103 élabore des signaux T(n) qui sont représentatifs des caractéristiques acoustiques du signal d'entrée (case 220) L'index N spécifie un inter- valle particulier du mot d'entrée, et chaque intervalle représente par exemple 45 ms de parole, tandis que les intervalles adjacents sont espacés de 15 ms Les signaux de caractéristiques acoustiques T(n) peuvent être obtenus sur la base d'une analyse de prédiction linéaire, bien connue dans la technique Selon une variante, on peut utiliser des signaux de caractéristiques de type spectral, élaborés à partir des formants, ou d'autres signaux de caractéristi- ques Le microprocesseur 103 normalise ensuite les signaux de caractéristiques T(n) et il les soumet à un alignement temporel linéaire pour leur donner une durée standard, qui est par exemple de N = 21 intervalles de temps (case 225). L'index N s'étend donc sur la plage N, 1, 2,, N Des procédés de traitement de signal correspondant aux opéra- tions de normalisation et d'alignement temporel linéaire sont décrits de façon plus détaillée dans l'article de C S Myers, L R Rabiner et A E Rosenberg intitulé, "Performance Trade Offs In Dynamic Time Warping Algorithm For Isolated Word Recognition", IEEE Transactions On Acoustic, Speech, and Signal Processing, Vol ASSP-28, pages 622-635, décembre 1980. Les signaux de caractéristiques d'entrée T(n), normalisés et soumis à un alignement temporel linéaire, sont enregistrés dans la mémoire 104 Des signaux de gabarit de caractéristiques Rv(m), obtenus précédemment, pour des mots de référence, sort également enregistrés dans la mémoire 5104 L'indice v de Rv(m) spécifie un mot de référence parti- culier dans un vocabulaire ayant un total de V mots de réfé- rence, c'est-à-dire que v s'étend sur la plage: v = 1, 2,, V L'index m spécifie un intervalle particulier d'un mot de référence, et les intervalles des mots de référence ont la même durée et le même écartement que les in Lervalles des mots d'entrée ( 45 et 15 ms). A la suite des opérations d'alignement temporel linéaire (case 225), le microprocesseur 103 sélectionne l'un des mots de référence v pour le comparer au mot d'entrée (case 230) La comparaison est accomplie par un traitement du signal par alignement temporel dynamique con- formément à l'invention (case 235) Le signal de similitude résultant D est enregistré dans la mémoire 104 (case 240). v Les signaux de similitude Dv sont élaborés et enregistrés de façon similaire pour les autres mots de référence Une fois que le dernier signal de similitude a été généré (case 245), le signal de similitude extrémal est sélectionné dans le microprocesseur 103 et ii est émis vers le disposi- tif d'utilisation 105 (case 250) L'index de mot de référence v correspondant est également appliqué au dispositif 105, en tant qu'identité du mot d'entrée Le traitement pour un mot d'entrée particulier est ainsi terminé (case 255). Le tiaitement du signal par alignement temporel dynamique, conformément à l'invention (case 235), peut être décrit commodément en considérant le diagramme 600 de la figure 6 Le diagramme 600 ccmporte une grille de points ou de noeuds La séquence d'intervalles de test N est pcrtée en abscisse (variable indépendante) et la séquence d'inter- valles de référence m est portée en ordonnée (variable dépendante) Chaque noeud représente la similitude ou la correspondance entre les signaux de caractéristiques de l'intervalle de rang n, T(n), du mot d'entrée, et les signaux de caractéristiques de l'intervalle de rang m, Rv(m), du mot de référence On peut obtenir ce signal de correspondance d'après le rapport de vraisemblance loga- rithmique d'Itakura, de la manière décrite dans l'article de F Itakura intitulé, "Minimum Prediction Residual Prin- ciple Applied to Speech Recognition", IEEE Transaction on Acoustics, Speech, and Signal Processing, Vol ASSP-23, n 1, pages 67-72, février 1975: d(I(n),Rv(m)) log l T(n) Rv(m)l ( 1) c'est-à-dire que c'est le logarithme du produit scalaire des deux vecte Urs T(n) et Rv(m). Le signal de correspondance d est habituellement appelé distance locale, du fait que la valeur de d augmen- te lorsque la correspondance entre T(n) et R(m) diminue. Il faut cependant noter qu'on peut utiliser d'autres mesu- res de similitude, comme des coefficients de corrélation qui augmentent lorsque la correspondance entre T(n) et R(m) augmente. Du fait que l'index d'intervalle d'entrée N a été défini comme étant la variable indépendante, on peut écrire de façon équivalente l'index d'intervalle de réfé- rence m en fonction de N: m w(n) ( 2) On a trouvé que cette orientation donne de bonnes perfor- mances dans les systèmes de reconnaissance de mots On peut donc écrire le signal de distance locale dans l'équa- tion ( 1) sous la forme: d(T(n), Rv(w(n))). L'orientation inverse est également possible. Pour aligner de façon optimale les intervalles d'entrée N avec les intervalles de référence m, on minimise la somme des signaux de distance locale d(T(n)), Rv(w(n))) entre un mot d'entrée et un mot de référence v: D -min '32 d(T(n), R (w(n))) ( 3) v w(n) n= 1 v Le signal Dvest appelé le signal de distance moyenne tota- le ou globale pour le mot de référence v On rappelle que l'index de mot de référence v = 1, 2 V qui correspond au signal de distance globale minimal est transmis au dispositif d'utilisation 105 en tant que meilleur candidat pour l'iden- tification du mot d'entrée Selon une variante, il peut être utile de transmettre au dispositif 105 une liste ordonnée de signaux de distance globale. Pour obtenir un signal de distance moyenne globale DV, il serait possible de générer un signal de distance loca- le d pour chaque noeud dans le diagramme 600 On pourrait alors trouver la séquence particulière de noeuds, ou "chemin", qui donne le signal de distance globale minimal Cependant, outre le fait qu'elle aurait un mauvais rendement, une telle recherche exhaustive pourrait également conduire à un chemin qui ne soit pas réaliste au point de vue acoustique Il est donc souhaitable d'imposer certaines contraintes au chemin. On suppose que les intervalles de début et de fin des mots de référence comme des mots d'entrée ont été déter- minés avec précision Le premier intervalle d'entrée N 1 est donc apparié avec le premier intervalle de référence m, 1, ou: w( 1), 1 ( 4) De façon similaire, le dernier intervalle d'entrée n, N est apparié avec le dernier intervalle de référence m = M: w(N), M ( 5) On suppose également que les contraintes de chemin d'Itakura sont respectées: o t w(n) w(n-1) 4 2 ( 6) w(n) w(n-1) 4 O si w(n-1) w(n -2) O ( 7) Ces contraintes de chemin locales garantissent que la pente moyenne de la fonction d'alignement temporel w(n) est comprise entre 1/2 et 2 et que le chemin est monotone et non décroissant En d'autres termes, les contraintes de che- min locales définissent des chemins possibles au point de vue acoustique. On peut résumer les contraintes de chemin locales et d'extrémités par un ensemble de contraintes de chemin globales: m L(n) i m im H(n) ( 8) avec: m L(n), min l 2 (n-1) + 1, M 3 (N-n), Ml ( 9) m H(n) 5 max 12 (n-1) + 1, M 2 (N-n), 'l ( 10) Les contraintes de chemin globales définissent le parallélo- gramme ou la fenêtre représenté sur le diagramme 600 de la figure 6 Les chemins admissibles ne comprennent que des noeuds situés à l'intérieur de la fenêtre. Conformément à l'art antérieur, on peut trouver le chemin minimal par un processus de programmation dynamique. On définit un signal de distance totalisée DA pour n'importe quelle paire donnée d'intervalles N et m, comme étant la somme des signaux de distance locale d à partir du noeud ( 1,1), jusqu'au noeud présent (N,M), ce dernier étant com- pris, le long du chemin de distance minimale ou "meilleur" chemin, entre les noeuds ( 1,1) et (N,M) Le signal de dis- tance totalisée DA peut être généré de façon récursive depuis le noeud ( 1,1) jusqu'au noeud (N,M) conformément à l'équation suivante: DA (n,m) d(T(n),R(m)) + minlDA(n-l,m)g(n-l,m), DA(n-l,m-1), DA(n-l,m-2)l ( 11) dans laquelle les contraintes sont: 1 A N % N, m L(n) alors égal au signal de distance totalisée DA(N,M). Le processus d'alignement temporel dynamique précé- dent nécessite la génération d'un sigrnal de distance locale à chaque noeud à l'intérieur de la fenêtre dans le diagramme 600 Cependant, la génération des signaux de distance locale est relativement lente dans un simple microprocesseur De ce fait, conformément à l'invention, on ne génère des signaux de distance locale qu'à des noeuds qui sont des candidats vraisemblables pour le chemin minimal. En considérant le diagramme 600, on désigne le noeud de rang i par ses coordonnées N et m: i = (n,m) ( 14) Le roeud de départ S est défini par S = ( 1,1) et le noeud final t est défini par t = (N,M) Dars l'exemple considéré, N = M = 21. On définit un signal de distance totalisée g(i) comme étant la somme des signaux die distance locale d le long du meilleur chemin, depuis le nceud de départ s jusqu'au noeud i, ce dernier compris Le meilleur chemin correspond à la séquence de noeuds précédant le nceud i qui a la distance totale minimale. On'définit un second signal de distance totalisée h(i) comme étant la somme des signaux de distance locale d le long du meilleur chemin depuis le noeud i jusqu'au noeud final t En commençant au noeud S = ( 1,1) et en progressant de gauche à droite sur le diagramme 600, on peut connattre de façon exacte le signal g(i) à chaque noeud i Au con- traire, le signal h(i) n'est pas connu et on doit donc l'estimer ou le prédire On désigne par h(i) le signal de prédiction de h(i). A partir du signal de distar nce totalisée g(i) et du signal de prédiction h(i), on peut trouver un signal de distance totale prédite f(i) , conformément à l'équation ( 15): f(i) = g(i) + h(i) (i 15) Le signal f(i) représente la dis:ance totale prédite d'un chemin allant du noeud S au r oeud t et qui passe par le noeud i. Avant de décrire comment est généré le signal de prédiction h(i) lui-m;me, on va tout d'abord considérer en détail l'utilisation de h(i) conformément à l'invenbion pour ne générer des signaux de distance locale qu'aux rnoeuds qui sont des candidats vraisemblables. L'état nodal à n'importe quel noeud i est défini 1 l par les paramètres suivants: le signal de prédiction h(i), le signal de distance totalisée g(i), et un signal pointeur (adresse) qui désigne le noeud précédent ou "parent" sur le chemin Le chemin allant d'un noeud de départ S à n'importe quel noeud intermédiaire i est ainsi complètement caracté- risé par l'état nodal du noeud i et des noeuds qui le précè- dent. Lorsqu'on cherche le chemin de distance minimale dans le diagramme 600, on rencontre généralement des noeuds appartenant à plusieurs chemins possibles On introduit dans une "liste ouverte" l'état nodal du dernier noeud sur chacun des chemins possibles On classe les rubriques de la liste de façon que l'état nodal du dernier noeud du chemin qui a la plus faible distance totale f(i) soit au sommet de la liste. On retire ensuite de la liste ouverte l'état nodal qui se trouve au sommet et on l'introduit au sommet d'une "liste fermée" On effectue une "expansion" de l'état nodal du sommet de la liste fermée, c'est-à-dire qu'on sélectionne tous les noeuds successeurs admissibles On génère de nou- velles distances totales f(i) pour chaque noeud successeur. Onclame l'information d'état nodal pour chaque noeud succes- seur dans la liste ouverte, et on répète le processus jusqu'à ce qu'on ait identifié le noeud final t La distance g(t) au noeud t devient le signal de distance minimale DV Le processus de recherche précédent peut être résumé conformément à l'invention de la manière illustrée par l'organigramme 300 sur la figure 3 On génère des signaux de caractéristiques acoustiques pour des première et seconde configurations de parole (case 305) Les première et seconde configurations de parole peuvent correspondre par exemple respectivement à un mot testé et à un mot de référence On génère un intervalle de temps courant de la première confi- guration de parole (case 310) On génère un intervalle de temps candidat de la seconde configuration de parole, pour l'intervalle de temps courant de la première configuration de parole (case 320) On génère des signaux de correspondance entre les signaux de caractéristiques acoustiques de l'inter- valle de temps courant de la première configuration de parole et les signaux de caractéristiques acoustiques de l'inter- valle de temps candidat de la seconde configuration de paro- le (case 330) On génère un signal de similitude prédit pour un chemin qui comprend l'intervalle de temps candidat de la seconde configuration de parole et l'intervalle de temps cou- rant de la première configuration de parole (case 340) On répète la génération de signaux de correspondance et de pré- diction (cases 320, 330 et 340) pour chaque intervalle de temps candidat de la seconde configuration de parole et pour l'intervalle de temps courant de la première configuration de parole (case 350) On sélectionne ensuite l'un des inter- valles de temps candidats de la seconde configuration de parole pour la paire d'intervalles de temps courante rela- tive à la première configuration de parole (case 360) On répète les opérations (cases 310-360) pour chaque signal d'intervalle de temps successif de la première configuration de parole. Le processus de recherche de l'invention peut être accompli au moyen du microprocesseur 103 Le micropro- cesseur 103 est commandé par des codes d'instruction enre- gistrés dans la mémoire 104 La liste des codes d'instruc- tion en langage FORTRAN figure en annexe On peut décrire les opérations conformes aux codes d'instruction en se réfé- rant à l'organigramme 400 de la figure 4 et au diagramme 600 de la figure 6 On initialise la liste ouverte et la liste fermée, c'est-à-dire qu'on efface ou qu'on remet à zéro leur contenu (case 405) On introduit ensuite l'état nodal du noeud de départ S = ( 1,1) au sommet de la liste ouverte (case 405) On enlève ensuite la rubrique qui se trouve au sommet de la liste ouverte et on la place au sommet de la liste fermée, pour l'opération d'expansion (case 410) On génère un noeud successeur, en respectant les contraintes locales (case 415) Dans le cas du noeud de départ S ( 1,1), les noeuds ( 2,1), ( 2,2) et ( 2,3) sont les trois successeurs autorisés Sur le diagramme 600, les noeuds successeurs autorisés sont de façon générale réunis par une ligne à leur noeud prédécesseur ou parent. Si un noeud successeur est généré (case 420), on contrôle la liste ouverte et la liste fermée pour voir si le noeud apparaît dans une liste ou dans l'autre (case 425) Si le noeud apparatt dans la liste fermée, il n'est pas néces- saire de l'ajouter à la liste ouverte, du fait qu'on a déjà trouvé un chemin optimal pour ce noeud En outre, si le noeud successeur apparait déjà dans la liste ouverte, il n'est pas non plus nécessaire de l'ajouter, du fait que le chemin par lequel ce noeud a été généré précédemment est optimal pour aller au noeud soumis à expansion, et il doit avoir une dis- tance inférieure à celle du chemin courant considéré, car sinon il n'aurait pas été soumis précédemment à une expansion (case 430) On contrôle ensuite le noeud successeur vis-à-vis des contraintes globales (case 435) Si le noeud est compris dans les limites de la fenêtre (case 440), on sauvegarde un pointeur désignant le noeud parent, on positionne un paramè- tre de contraintes locales et on génère le signal de distance locale totalisée g(i) (case 445) Le paramètre de contraintes locales est nécessaire, d'après l'équation ( 13), pour que le chemin s'élève obligatoirement de 1 un noeud sur deux. Si le noeud successeur n'est pas le noeud final t (case 450), la distance totale prédite f(i) est générée Sur la base du signal f(i), l'état nodal du noeud successeur est classé dans la liste ouverte (case 455) Un autre noeud successeur est sélectionné (case 415) et traité (cases 420-455) jusqu'à ce que tous les noeuds successeurs autorisés aient été générés et jusqu'à ce que leurs états nodaux correspondants aient été classés dans la liste ouverte. Lorsq 4 xaucun noeud successeur supplémentaire ne peut être généré (case 420), le noeud successeur ayant la plus faible distance f(i) est sélectionné en tarnt que nouveau noeud parent (case 410) Le noeud parent est soumis à expansionr comme ci-dessus. Le processus se répète (case 410-455) jusqu'à ce qu'un noeud successeur soit identifié comme étant le noeud final t (case 450) La distance globale Dv est égale à g(t), c'est-à-dire la distance totalisée au noeud t (case 465) Le processus de comparaison d'un mot d'entrée et d'un mot de référence est ainsi terminé. Sur la figure 6, le processus de recherche commence au noeud S = ( 1,1) Parmi les noeuds successeurs possibles ( 2,1), ( 2,2) et ( 2,3), le noeud ( 2,1) a la plus petite distarnce totale prédite f(i) et il est donc sélec- tionné pour l'expansion Sur le diagramme 600, les nombres désignent (dans l'ordre) les noeuds sélectionnr és pour l'expansion; le noeud (,1) est désigné comme étant le noeud 1. On rappelle que le chemin doit obligatoirement s'élever de 1 un intervalle sur deux, ce qui fait que le noeud 1 a deux noeuds successeurs possibles:les noeuds ( 3,2) et ( 3,3) Le noeud ( 3,3), qui est désigné comme étant le noeud 2,a la plus petite distance f(i) et il est donc soumis à l'expansion Ce processus de poursuit jusqu'à l'expansion du noeud 17 On trouve que les successeurs possibles du noeud 17, c'est-à- dire les noeuds ( 19,19) et ( 19,20) ont tous deux une distance totale prédite f(i) plus grande que celle du noeud ( 8,7) Le noeud ( 8,7) devient donc le noeud 18 et est soumis à l'expansion. Les noeuds successeurs possibles ( 9,8) et ( 9,9) sont représentés reliés par des lignes en pointillés au noeud parent 18 sur le diagramme 600 Le noeud ( 9,9) est éliminé de toute considération ultérieure, du fait qu'il a été rencontré précédemment au moment de l'expansion du noeud 7 D'autre part, onr trouve que le noeud ( 9,8) a une distance totale prédite f(i) supérieure à celle du noeud ( 19,19) Le noeud ( 19,19) devient donc le noeud 19 et est soumis à l'expansion L'expansion du noeud 19 conduit ensuite au noeud 20 et un atteint finalement le noeud t avec une distance totale minimale. Le gain sur le nombre de signaux de distance locale d qu'on doit générer (dans cet exemple dans lequel il y a N 21 intervalles), par rapport à un processus de programmation dynamique classique, correspond approximati- vement au rapport entre les noeuds non reliés et les noeuds reliés dans le diagramme ( 600), scit environ 2 à 1 Onr a trouvé expérimentalement que le gain était encore meilleur, soit environ 3 à 1, dans un cas plus usuel dans lequel N = 42 intervalles. En retournant maintenant à la considération du signal de prédiction h(i) on rappellera qu'on fait la somme de h(i) avec le signal de distance locale totalisée g(i) pour donner la distance prédite totale f(i) On peut générer de plusieurs manières le signal de prédiction h(i) Il peut consister par exemple en un estimateur de la forme: h(i) = (N-n)o ( 16) dans laquelle O est un paramètre de l'estimateur Cependant, cette forme fixe peut sous-estimer fortement la distance totalisée depuis le noeud i jusqu'au noeud t, lorsque les mots d'entrée et de référence proviennent de classes acous- tiques différentes. Il est préférable de générer le signal de prédic- tion h(i) de façon adaptative, conformément à l'équation: h(i), (N-n)" g(i) ( 17) n Le signal de prédiction de l'équation ( 17) offre l'avantage que pour des mots d'entrée et de référence provenant de classes acoustiques différentes, g(i)/n devient grand et force h vers la plage appropriée. L'expérimentation faite avec le signal de prédic- tion de l'équation ( 17) a montré que les distances de chemin résultantes étaient indépendantes de o( sur une plage étendue Sur la base de cette expérimentation, on a déter- miné qu'une valeur ç, 0,7, par exemple, convient. On peut encore améliorer l'efficacité du processus de recherche de chemin en forçant o à devenir très supérieur à 0,7 lorsque des résultats préliminaires indiquent que les mots de test et de référence proviennent de classes acous- tiques différentes Ceci rend h(i) prédominant dans la génération de f(i) et minimise donc les retours en arrière pendant la recherche Le signal de prédiction h(i) peut donc être généré de la manière suivante: h(i) = 0,7 g()(N-n) si g(i) n n ( 18) 2,0 g(i)(N-n) si (i) > n N " en désignant par 3 la plus grande distance moyenne raisonna- ble attendue lorsqu'on compare des mots de test et de réfé- rence appartenant à la même classe acoustique Des valeurs de 8 entre environ 0,6 et 0,7, par exemple, conviennent. L'organigramme 500 qui est représenté sur la figu- re 5 montre la génération du signal de prédiction h(i) et du signal de distance totale prédite f(i) L'organigramme 500 montre en détail les opérations de la case 455 sur la figure 4 Si le signal de distance totalisée g(i) divisé par l'index de l'intervalle d'entrée N est inférieur à la distance moyenne p (case 510), le paramètre O sont combinés pour générer le signal de distance totale pré- dite f(i) (case 550). Il va de soi que de nombreuses modifications peuvent être apportées au dispositif et au procédé décrits et représentés, sans sortir du cadre de l'invention Par exemple, selon une variante, la séquence de noeuds qui constituent le chemin optimal peut être déterminée en remon- tant dans la liste fermée d'états nodaux (case 460). ANNEXE SUBROUTINE DSWARP(NR,NT,DT,LVP,E) DIMENSION LVP( 75),NODE( 5,500),CNODE( 2,500) INTEGER HEAD,HEAD 2,EMP *LOGICAL LSENSW COMMON/ECST/ECOST,NND,EMP C*****PROGRAMME POUR EFFECTUER UN ALIGNEMENT TEMPOREL DYNA- C MIQUE EN UTILISANT UNE RECHERCHE DIRIGEE C*****FONCTIONS DE CONTRAINTES GLOBALES MH(I)=MINO( 2 *(I-1)+l,NR-0 5 *(NT-I),NR) ML(I)=MAXO((I-1)/2 + 1,NR-2 *(NT-I),1) C C STRUCTURE DES DONNEES DE NOEUD: C 1 IR C 2 IT C 3 POINTEUR VERS L'AVANT(LISTE OUVERTE) C 4 POINTEUR VERS LE NOEUD PARENT C 5 PARAMETRE DE CONTRAINTE LOCALE C C C STRUCTURE DES DONNEES CNODE C 1 COUT REEL, G(N) C 2 COUT TOTAL ESTIME DU CHEMIN, F'(N) C*****VERIFICATION QUE LE CHEMIN DE TRANSFORMATION EST REALISABLE IF(NR GE 2 *NT OR NT GE 2 *NR) RETURN 5 C*****INITIALISATION NND=O HEAD=i HEAD 2 =O EMP= 2 NODE( 1,1)= NODE( 2,1)= 1 NODE( 3,1)=O NODE( 4,1)=O NODE( 5,1)=, CNODE(l,l)=DIST(l,1) moii Dnnomimi ausiwzad vu He MOIIVSIIVHU*****D 01 OD ( 0-10-iGV 2 lH)JI Moilin(joaliii SUSII Ig Hd VI Ha 11 D Vi S 'ilig ga NIW H Iq G Ufl Od SIMIN O J D ZIU 2 MO f 1 Sf'î VI SNVCI WION n G -j C " (d Wq'2 "IGON-JN) ( 9 '0 'SD'ISODAV)àI ISODAV*ISODS*L'O=JV 2071 ( 9 '0 '11 'ISOOAV)JI S:iss Vq) xnza V NOISID Sa oc 311 ni U f SV 9 VI Hn S gnql VWII Sqîq Sa ïlfl)IIIVNACI NOI 1 VXIJ*****D 111 WMO PIG ' 'VIOI MOD n G t IOIIVNIISS*****D Ot 7 01 00 (IN'ÈS'(d WS'i 7,)HGON)JI IVNIJ Gfl SON n G IIDVS q IS Ha MIWHSISG Un Od Zq OHINOD*****D GZ- "dws,2 )Sraom 1 (dwgll)21 cfom)lsicl+(OEVSH'I)SGOMD=(d WS'I)g GOND INVU 00 In OD na NOIIVNINUSISOE*****D O? Ssliv;Doli SHINIVHIN 00 9 G SHISWVH Vd na NO Il VXII*****D GVSH=(d WS'V)HGON NIWSHD n G 9 GUVDS Anvs*****D TE 01 OD "(d Wg'2)SGOM)HW'ID'(d Wq'I)SOEON'UO' 91 si SHIV 901 D SHINIMIN 00 SHG SIOUINOD*****D Un Nilmol) Gi TC 01 OD "X'e)SGON 1-dtqaq=m Gi oa 91 01 OD ( 9 'LI'd WUA 1 qf Wusj Mi SMS An O SSISTI SZ' '3 tl VG Cf)SON n VUMION Nfli G E'(GVSH'q)3 GON=I le 09 T+OENN=CNN Gflq ON Nni C NOIOM Vd Xa*****D Pl 66 MSZ NODE( 3,EMP)=-O HEAD 2 =EMP GO TO 30 C*****CONTROLE DE LA TETE DE LA LISTE OUVERTE IF(CNODE( 2,EMP) GT CNODE( 2,HEAD 2)> GO TO 8 C*****AJOUT DU NOEUD EN TETE DE LA LISTE__QUVERTE NODE( 3,EMP)=HEAD 2 HEAD 2 =EMP GO TO 30 C*****CONTROLE DU RESTE DE LA LISTE OUVERTE IPT-N O DE( 3,HEAD 2) IP 1 S-HEAD 2 DO 20 J= 2,300 IF(IPT GT O) GO TO il C*****FIN DE LA LISTE; AJOUT DU NOEUD NODE( 3,IPTS)EMP NODE( 3,EMP)=O GO TO 30 C*****CONTROLE DE LA LISTE DE COUT il IF(CNODE( 2,EMP) GT CNODE( 2,IPT)) GO to 13 C*****DETERMINATION DE L'EMPLACEMENT POUR L'INTRODUCTION DU NOEUD NODE( 3,EMP)=IPT NODE( 3,IPTS)=EMP GO TO 30 ""**PASSAGE AU COUT SUIVANT DANS LA LISTE OUVERTE 13 IPTS=IPT IPT-NODE( 3,IPT) EMP=EMP+l 31 CONTINUE C*****INITIALISATION POUR L'EXPANSION SUIVANTE HEAD= HEAD 2 HEAD 2 =NODE( 3,HEAD) GO TO 5 C*****RECAPITULATION DU CHEMIN DT-CNODE( 1,EMP) LVP(NT)= NR IPT= NODE( 4,EMP) LVP(NT-1)=NODE( 1,IPT) DO 50 I-3,NT IPT= NODE ( 4, IPT) 50 LVP(NT+ 1- I)=NODE( 1,IPT) RETURN END REVENDICATIONS 1 Procédé pour aligner dans le temps une première configuration de parole avec une seconde configuration de parole comprenant les opérations suivantes: on génère une séquence d'intervalles de temps de signaux reprpsertatifsdes caractéristiques acoustiques de la première configuration de parole, on génère une séquence d'intervalles de temps de signaux représentatifs des caractéristiques acoustiques de la seconde configuration de parole, et on apparie chaque inter- valle de temps de la première configuration de parole avec l'un des intervalles de temps de la seconde configuration de parole, sous la dépendance des signaux de caractéristiques de la première configuration de parole et des signaux de caractéristiques de la seconde configuration de parole; caractérisé en ce que, pour apparier les intervalles de temps, on génère une série de signaux représentatifs de la succession d'intervalles de temps de la première configuration de parole et, sous la dépendance de chaque signal d'intervalle de temps successif de la première configuration de parole, on génère un ensemble de signaux correspondant à des intervalles de temps candidats de la seconde configuration de parole pour un intervalle de temps courant de la première configuration de parole, on génère un ensemble de signaux représentatifs de la correspondance entre les signaux de caractéristiques acousti- ques de l'intervalle de temps courant de la première configu- ration de parole et les signaux de caractéristiques acousti- ques des intervalles de temps candidats de la seconde confi- guration de parole, on génère pour chaque intervalle de temps candidat de la seconde configuration de parole et pour l'intervalle de temps courant de la première configuration de parole, un signal qui constitue une prédiction de la simili- tude des première et seconde configurations de parole le long d'un chemin comprenant l'intervalle de temps candidat de la seconde configuration de parole et l'intervalle de temps cou- rant de la première configuration de parole, sous la dépen- dance des signaux de correspondance des intervalles de temps précédents et courant de la première configuration de parole, et on sélectionne l'un des intervalles de temps candidats de la secornde configuration de parole, pour la paire d'inter- valles de temps qui correspond à l'intervalle de temps ccu- rant de la première configuration de parole, sous la dépen- dance des signaux de prédiction de l'intervalle de temps cou- rant de la première configuration de parole. 2 Procédé selon la revendication 1, caractérisé en ce que les signaux de correspondar nce sont des sigraux de dis- tance. 3 Procédé selon la revendication 2, caractérisé en ce que chaque signal de prédiction f(i) est généré confcrmé- ment à la relation: f(i) = g(i) + h(i) dans laquelle i est l'index d'un noeud qui correspond à l'intervalle de temps courant de la première configuration de parole et à l'un des intervalles de-temps candidats de la seconde configuration de parole, g(i) est la distance tota- lisée minimale des noeuds courant et prédécesseurs et h(i) est la distance totalisée prédite des noeuds successeurs. 4 Procédé selon la revendication 3, caractérisé en ce que les signaux de prédiction h(i) sont générés con- formément à la relation: h(i) = () (N-n) n dans laquelle a est un paramètre du signal de prédiction h(i), N est l'intervalle de temps courant de la première configuration de parole et N est le dernier intervalle de temps de la première configuration de parole. Procédé selon la revendication 4, caractérisé en ce que le paramètre î est approximativement de 0,7. 6 Procédé selon la revendication 4, caractérisé en ce que le paramètre o est approximativement de 0,7 si: n et le paramètre C est approximativement de 2,0 si: g(i) > n en désignant par f la distance moyenne attendue pour des comparaisons de configurations de parole appartenant à la même classe acoustique. 7 Procédé selon la revendication 6, caractérisé en ce que la distance moyenne p est dans la plage d'environ 0,6 à 0,7. 8 Procédé selon l'une quelconque des revendica- tions 2 à 7, caractérisé en ce que chaque signal de caracté- ristiques acoustiques de la première configuration de parole, T(n), correspond à une caractéristique de prédiction linéaire de l'intervalle de temps de rang N de la première configura- tion de parole, et chaque signal de caractéristiques acousti- ques de la seconde configuration de parole, R(m),correspond à une caractéristique de prédiction linéaire de l'intervalle de temps de rang m de la seconde configuration de parole. 9 Procédé selon la revendication 8, caractérisé en ce qu'on génère les signaux de distance conformément à la relation d(T(n), R(m)) log(T(n) R(m) ) dans laquelle représente le produit scalaire. Dispositif destiné à aligner dans le temps une première configuration de parole avec une seconde configura- tion de parole, conformément au procédé de la revendication 1, comprenant des moyens destinés à générer une séquence d'intervalles de temps de signaux représentatifs des carac- téristiques acoustiques de la première configuration de paro- le, des moyens destinés à générer une séquence d'intervalles de temps de signaux représentatifs des caractéristiques acous- tiques de la seconde configuration de parole, et des moyens qui fonctionnent sous la dépendance des signaux de caracté- ristiques acoustiques de la première configuration de parole et des signaux de caractéristiques acoustiques de la seconde configuration de parole, de façon à apparier chaque inter- valle de temps de la première configuration de parole avec l'un des intervalles de temps de la seconde configuration de parole, caractérisé en ce que les moyens destinés à apparier les intervalles de temps comprennent: des moyens destinés à générer une série de signaux représentatifs de la succession des intervalles de temps de la première configuration de parole, des moyens destinés à générer un ensemble de signaux correspondant à des intervalles de temps candidats de la seconde configuration de parole, pour l'intervalle de temps courant de la première configuration de parole, des moyens destinés à générer un ensemble de signaux représentatifs de la correspondance entre les caractéristiques acoustiques de l'intervalle de temps courant de la première configuration de parole et les signaux de caractéristiques acoustiques des intervalles de temps candidats de la seconde configuration de parole, des moyens qui fonctionnent sous la dépendance des signaux de correspondance des intervalles de temps pré- cédents et courant de la première configuration de parole, de façon à générer, pour chaque intervalle de temps candidat de la seconde configuration de parole et pour l'intervalle de temps courant de la première configuration de parole, un signal qui constitue une prédiction de la similitude des première et seconde configurations de parole, le long d'un chemin qui comprend l'intervalle de-temps candidat de la seconde configuration de parole et l'intervalle de temps cou- rant de la première configuration de parole, et des moyens qui fonctionnent sous la dépendance des signaux de prédiction de l'intervalle de temps courant de la première configuration de parole, de façon à sélectionner l'un des intervalles de temps candidats de la seconde configuration de parole, pour la paire d'intervalles de temps qui correspond à l'intervalle de temps courant de la première configuration de parole. 11 Dispositif selon la revendication 10, caracté- risé en ce que les moyens destinés à générer des signaux de correspondance comprennent des moyens qui génèrent des signaux de distance. 12 Dispositif selon la revendication 11, caracté- risé en ce que les moyens destinés à générer un signal de prédiction comprennent des moyens qui génèrent chaque signal de prédiction f(i) conformément à la relation f(i) = g(i) + h(i) dans laquelle i est l'index d'un noeud qui correspond à l'intervalle de temps courant de la première configuration de parole et à l'un des intervalles de temps candidats de la seconde configuration de parole, g(i) est la distance totali- sée minimale des noeuds courant et prédécesseurs et h(i) est la distance totalisée prédite des noeuds successeurs. 13 Dispositif selon la revendication 12, caracté- risé en ce que le signal de prédiction h(i) est généré cor- formément à la relation: h(i) = P(i) (N-r) darns laquelle c% est un paramètre du signal de prédiction h(i), N est l'intervalle de temps courant de la première configuration de parole et N est le dernier intervalle de temps de la première configuration de parole. 14 Dispositif selon la revendication 13, caracté- risé et ce que le paramètre a est approximativement égal à 0,7. Dispositif selon la revendication 13, caracté- risé en ce que le paramètre a est approximativement égal à 0,7 si: g(i) N et le paramètre O est approximativement égal à 2,0 si: g(i) > $ n en désignant par ( la distance moyenne attendue pour des comparaisons de configurations de parole appartenant à la même classe acoustique. 16 Dispositif selon la revendication 15, carac- térisé en ce que la distance moyenne P est dans la plage d'environ 0,6 à 0,7. 17 Dispositif selon la revendication 10, carac- térisé en ce que chaque signal de caractéristiques acousti- ques de la première configuration de parole, T(n),correspond à une caractéristique de prédiction linéaire de l'intervalle de temps de rang N de la première configuration de parole, et chaque signal de caractéristiques acoustiques de la seconde configuration de parole, R(m), correspord à une caractéristique de prédiction linéaire de l'intervalle de temps de rang m de la secor de configuration de parole. 18 Dispositif selon la revendication 17, carac- térisé en ce que les signaux de distance sont générés corfor- mément à'la relation: d(T(n), R(m)) = log(T(nr,) R(m)) dans laquelle représente le produit scalaire. P