FR 2518783 A1 19830624 FR 8221431 A 19821221 La présente invention concerne un appareil pour réaliser la comparaison de formes de séquences, qui est utilisé par exemple dans le domaine de la reconnaissance de la parole, en vue d'obtenir la mesure de similarité- entre deux formes de séquences de paramètres caractéris- tiques, sous la forme de la distance ou de la similarité entre lesdites formes au moyen d'une comparaison à norma- lisation non linéaire utilisant un programmation dynamique. La séquence, que l'on peut traiter au moyen du système de comparaison de formes de séquences selon la pré- sente invention est une séquence de grandeurs caractéristi- ques Si la distance ou la similarité entre les grandeurs caractéristiques est définie, on peut traiter une séquence ayant n'importe quelle forme, telle qu'une forme vocale ou une forme de lettre manuscrite Ci-après, on va décrire le système de comparaison de formes de séquences comme étant appliqué à une séquence temporelle de grandeurs caractéris- tiques d'une forme vocale. La voix est le moyen de transmission d'informations, qui est le plus commode à utiliser pour l'homme et qui lui est le plus familier Par conséquent un appareil de recon- naisance de la parole possède un champ d'application éten- du, comme par exemple l'introduction de données à l'aide de la voix, le dialogue avec une machine, la composition d'un numéro à l'aide de la voix et ainsi de suite - La vitesse d'élocution varie souvent même pour le même mot dit par la même personne Compte tenu de ce fait, la comparaison utilisant la programmation dynamique dans la reconnaissance de la parole (désignéeci- après sous le terme de comparaison à programmation dynamique) est utilisée-dans le calcul de la distance entre une séquence temporelle d'une parole d'entrée, A = a,, a 2, an, et une séquence temporelle d'une forme de référence, B bl, b 2 bm, en faisant correspondre entre eux leurs éléments, tout en per- mettant une dilatation et une contraction de l'axe du temps entre les séquences, comme cela est représenté par exemple dans le brevet EtatsUnis d'Amérique no 3 816 722 accordé à Sokoe et consorts en date du il Juin 1974 (voir en particulier, les figures l et 2) Dans le cas de la comparaison classique à programmation dynamique de ce type, un calcul à itératior successives est effectué au niveau de tous les points du réseau, (ij) à l'intérieur d' une fenêtre d'ajustement dans une matrice de distances D = (d i) des éléments des séquences A et B, d étantlea i O distance entre un i ème élément de la séquence A et un j-ème élément bj de la séquence B comme cela est indiqué dans le brevet Etats Unis d'Amérique mentionné ci-dessus En outre une condition concernant la pente est prévue afin d'empêcher la correspondance d'un élément avec- plus de deux éléments C'est pourquoi, même en utilisant la programmation dynamique, la comparaison à programmation dynamique présente l'inconvénient de mettre en jeu une gran- de quantité de calculs En outre le fait de prévoir la con- dition concernant la pente introduit l'inconvénient de né- cessiter un certain nombre de mémoires tampons pour la mé- morisation d'une valeur obtenue par calculs successifs g(i,j). En dehors de cela, dans i' art antérieur, la com- paraison à programmation dynamique est réalisée uniquement dans une matrice de distances, qui peut être calculée à par- tir d'éléments a et b ( l éléments a et b 1 au point de départ d'une période d'extrac- tion de la parole Cependant, dans la pratique, il est dif- ficile d'extraire de façon précise la période de la parole depuis le point de départ jusqu'au point d'extrémité ou final de cette période à tous moments et, dans l'art antérieur, la comparaison à programmation dynamique entre les séquences temporelles de la parole estaffectée d'une telle ambiguïté dans l'extraction de la période de la parole Par conséquent un défaut de reconnaissance est provoqué par ureerreur dans l'extraction de la période de la parole Afin d'éviter cela, l'inventeur à la base de la présente demande a proposé dans le procès-verbal 1-1-10 de la réunion d'automne organisée par la Société Japonaise d'A Coustique en Octobre 1980, d' utiliser un trajet particulier suivant une direction verti- cale ou latérale uniquement au voisinage du point de départ de la période d'extraction de la parole (laquelle méthode sera désignée ci-après sous le terme de méthode sans pseudo- bords) Etant donné que la-méthode sans pseudo-bords utili- se un trajet particulier de programmation dynamique, il exis- te des cas o il apparaît une correspondance anormale, affec- tant de façon nuisible la performance de reconnaissance. C'est pourquoi un but de la présente invention est de fournir un appareil de comparaison de formes de séquences dans lequel la quantité des calculs est faible et qui ne re- quiert pas de mémoires tampons de capacité importante pour mémoriser les valeurs calculées successivement. Un autre but de la présente invention est de four- nir un appareil de comparaison de formes de séquences, qui soit apte à fournir la mesure de similarité avec une préci- sion élevée, sans être affecté par l'ambiguité de segmenta- tion de la séquence extraite des paramètres caractéristiques. Conformément à la présente invention, le calcul à itérations successives de la programmation dynamique n' est pas effectué pour tous les points du réseau dans une ma- trice D = (di j) (o di, est la distance ou la similarité entre des éléments ai et bj) entre des éléments de deux sé- quences A = al, a 2, an et B =bl b 2, bm, mais le cal- cul à itérations successives est effecté auxpointsde calcul correspondant aux points du réseau espacés de N(N_> 3) points. C'est-a-dire que le calcul à itérations successives de la programmation dynamique est effectué en tous les points du réseau qui satisfont à la relation i + j = M + N (M étant une constante); le calcul à itérationssuccessives de la programmation dynamique est effectué en tous les points du réseau qui satisfont à la relation i + j = M + 2 N; et ensuite le calcul à itérations successives de la program- mation dynamique est effectué de façon similaire pour i + j = M + 3 N, i + j = M + 4 N, Par conséquent, conformément à la présente invention, le nombre de répétitions du calcul à itérations successives est abaissé à une valeur égale à la fraction 1/N du nombre de répétitions mises en jeu dans le système de l'art antérieur, et en outre, la quantité des calculs pour la condition relative à la pente peut être ré- duite et le nombre des mémoires tampons pour la mémorisa- tion des valeurs calculées successivement, c'est-à-dire des valeurs g(i,j) de fonction de coût, est seulement le double de la largeur de la fenêtre d'ajustement Par conséquent la quantité des calculs peut être notablement réduite par rap- port à celle nécessitée dans la comparaison classique à pro- grammation dynamique En outre, on utilise également une in- formation de séquence an, à a O et bm, à b O (n' précédant les éléments a et bl, au niveau desquels on consi- dère que la période d'extraction de la parole commence, et la vale-ur de la fonction de coût de la comparaison à program- mation dynamique est obtenue en utilisant les-distances en- tres ces éléments, et le point de départ est déterminé ulté- rieurement de sorte que la valeur de fonction de coût peut prendre une valeur minimum De même au point d'extrémité, on utiliseuneinformation de séquence an+ 1 à an, et bm+ 1 à b,, (n" > n, m > m) succédant aux éléments a et bm, au ni- n m veau desquels on considère que la période d'extraction de la parole se termine, et la position du point d'extrémité est déterminée plus tard de sorte que la fonction de coût de la comparaison à programmation dynamique peut devenir mini- mum dans la matrice de distances D = (di,) (n' m' grammation dynamique, la fonction de coût est nécessaire, mais l'information concernant le point d'extraction de la parole n'est pas toujours nécessaire et par conséquent le point de départ n'est pas obtenu de façon explicite Ainsi la présente invention permet l'exécution de la comparaison à programmation numérique entre des séquences temporelles, qui est affectée par l'ambiguïté de l'extraction de la pa- role, et par conséquent permet une réduction substantielle du défaut de reconnaissance quiest provoqué par une erreur dans l'extraction de la parole, réalisée dans l'art anté- rieur. D'autres caractéristiques et avantages de la pré- sente invention ressortiront de la description donnée ci- après prise en référence aux dessins annexés, sur lesquels: la figure l est un schéma-bloc montrant Uiexemple de l'agencement du système de reconnaissance de la parole conformément à la comparaison de programmation dynamique; la figure 2 est un schéma montrant,, à titre d' exemple, la comparaison à programmation dynamique et une matrice de distances utilisée jusqu'alors; la figure 3 est un schémàa montrant des trajets vertical, latéral et oblique dans la comparaison classi- que à programmation dynamique; la figure 4 est un schéma montrant un trajet ty- pique avec une condition relative à la pente, dans la com- paraison classique à programmation dynamique; la figure 5 A est un schéma montrant un réseau de points distants de N points et des trajets de program- mation dynamique dans une matrice de distances dans une première forme de réalisation de la présente invention; la figure 5 B est un-schéma montrant un réseau de points distants de N points et des trajets de programma- tion dynamique dans une matrice de distances dans une secon- de forme de réalisation de la présente invention; les figures 6 A à 6 D sont des schémas montrant des exemples de trajets de programmation dynamique dans la pre- mière forme de réalisation de la présente invention; la figure 7 est un schéma montrant la relation en- tre des mémoires tampons servant à mémoriser des valeurs de calcul obtenues par itérations successives, lors de la comma- raison à programmation dynamique, et des points de calcul des réseau selon la présente invention; les figures 8 A et 8 B sont desschémas permettant d'expliquer la longueur du trajet de programmation dynami- que dans la seconde forme de réalisation de la présente in- vention; les figures 9 A à 9 E sont des schémas montrant des exemples de trajets de programmation dynamique dans la secon- de forme de réalisation de la présente invention; la figure 10 est un schéma montrant des régions de bord dans la matrice de distances dans le cas de la compa- raison à programmation dynamique sans pseudo-bords; la figure il est un schéma montrant une matrice de distancespermettant d'expliquer la méthode sans bords conforme à la présente invention; la figure 12 est un schémabloc montrant une forme de réalisation de l'appareil de comparaison à programmation dynamique selon la présente invention, tel qu'il est appli- qué à un appareil de reconnaissance de la parole; la figure 13 est un organigramme montrant le fonc- tionnement de l'appareil de la figure 12; et la figure 14 est un schéma montrant la relation entre la durée de traitement de reconnaissance et la quan- tité de calculs, permettant d'expliquer l'effet obtenu grâce à la présente invention. On va décrire ci-après l'agencement général de l' appareil de reconnaissance de la parole. La figure 1 illustre à titre exemple l'agencement d'un système de reconnaissance de la parole,auquel la pré- sente invention est applicable Une parole d'entrée arrivant d'une borne d'entrée li est appliquée à une section 12 d'ex- traction'de paramètres caractéristiques, dans laquelle elle est transformée en une séquence temporelle de paramètres ca- ractéristiques A = al, a 2, an La séquence temporelle A desparamètres caractéristiques de la parole d'entrée est envoyée à une section 14 de calcul de distances, dans la- quelle est réalisé le calcul d'une matrice D = -(d) de distances entre la séquence temporelle A et une séquence temporelle B = bl, b 2 bn de paramètres caractéristi- ques d'une forme de référence mémorisée d'avance dans une section 13 de mémorisation de formes de référence La ma- trice de distances ainsi calculée est soumise, dans une section 15 de comparaison à programmation dynamique, à un processus de comparaison utilisant une programmation dynamique pour obtenir des distances (scores) entre les pa- ramètres caractéristiques de la séquence temporelle A de la parole d'entrée et la séquence temporelle B de la forme de référence Un mot (la séquence de la forme de référence) possédant le plus faible des scores est déterminé par une section 16 de détermination de mots et le'nom du mot est déli Vré en tant que résultat de la reconnaissance de la parôle d'entrée, sur une borne 17. Comparaison classique à programmation dynamique Le processus mis en jeu par la section 15 de comparaison à programmationdynamique a été effectué de la manière suivante telle que décrite dans le brevet dépo- sé aux Etats Unis d'Amérique mentionné précédemment Com- me cela est illustré sur la figure 2, la matrice de distan- ces D = (d;) est obtenue en disposant le nombre des élé- ments i de la séquence A de la forme de la parole d'entrée suivant la direction des lignes et en disposant les nombres des éléments j de la-séquence B de la forme de référence sui- vant la direction des colonnes Un calcul à itérationssuc- cessives de la programmation dynamique est effectué pour chacun des points du réseau 1812 et 1821, qui satisfont à la relation i + j = 2 + 1; le calcul à itérations suc- cessivesde la programmation dynamique est effectué pour chacun des points du réseau 18131 1822 et 1831 qui satis- font à la relation i + j = 2 + 2; et ensuite le calcul à itérations successives de la programmation dynamique est effectué de façon similaire pour chacun des points du ré- seau qui satisfont à la relation i + j = 2 + 3, i + j = 2 - + 4, De cette manière on obtient le score (la distan- ce) en mettant en oeuvre la formule de récurrence suivante pour chaque point 18 du réseau, depuis le voisinage du point de départ ( 1,1) jusqu'au point d'extrémité ou final (n,m). g(i-l, j-2) + 2 d j l+ di, i,j'-l L,j g(i,j) -= min g(i-l, j-l) + 2 di () l g(i-2, j-l) + 2 di-l,j+ di, En outre il est prévu une condition de fenêtre d'ajustement 22 afin de limiter, pour le calcul des points du réseau dans une certaine zone de chaque côté de - la droitereliant le point de départ ( 1,1) et le point d'ex- trémité (n,m). De cette manière la programmation dynamique consis- te à se déplacer depuis le point de départ ( 1,1) jusqu'au point final (n, m) en passant par chaque point du réseau (i,j) dans la matrice de distances D = (di,) de sorte que la somme des valeursd des distances entre les points du réseau suivis peut être minimum, et la somme des distances di est utilisée en tant que score S(A:B), qui est four- ni par l'expression suivante: S(A: B) = min (d 11 + di) ( 2) In + ml{(i,j) } {(iij)} dans laquelle {(i,j)} représente la séquence des points du réseau ( 1,1) (i 2,j 2) (n,m) et lik+l ikl + jk+l ik= ( 3) (ik+l ik' k+l) et le trajet qui fournit la valeur minimale est désigné sous le terme de trajet optimum. De façon idéale, la valeur la plus faible d'une intégrale curviligne entre le point ( 0,0) et un point (n,m) devrait être obtenue pour une fonction de distance d(x,y) d'un système continu, mais on utilise l'expression ( 2) à titre de solution approchée Dans le système continu, cet- te valeur minimale est formulée comme suit: S = min {fcd(x,y)ds/fcds} ( 4) c dans laquelle c est un trajet d'intégration curviligne à croissance monotone partant du point ( 0,0) pour aboutir au point (n,m). Dans le cas de la formulation de la solution approchée telle que représentée par l'expression ( 2) et du calcul de la valeur du score S(A:B) moyennant l'uti- lisation de la programmation dynamique, les limitations suivantes sont imposées au trajet selon la méthode clas- sique. Différence de la longueur du trajet Comme séquence de trajet ( 1,1), (il, j 2), (n,m) dans le cadre de la comparaison a programmation dynamique de l'art antérieur, on choisit une séquence de points du réseau qui diffèrent d'une unité en termes de distance de blocs de mots de villes comme indiqué par l'expression ( 3) ou bier une séquence de points du réseau, qui satis- font à la relation suivante: ma Ji l max{lik+ 1 ikl, jk+l ikl} 1 ( 5) (ik+ l _ ik' Jk+l jk) Par conséquent les trajets qui sont suivis sur la matrice de distances sont des trajets vertical, latéral et oblique 15, 20 et 21 comme représenté sur la figure 3. Etant donné que la définition de la distance de blocs de mots de villes est utilise en tant que définition de la longueur du trajet, les trajets vertical et latéral 19 et 20 ont une longueur égale à 1 et le trajet oblique 21 pos- sède une longueur égale à 2 De façon idéale la longueur du trajet devrait être prise en compte dans un tel systè- me continu conformément à ce qu'indique l'expression ( 4) et, dans un tel cas, la distance entre les points du ré- seau est la distance euclidienne et le trajet oblique 21 possède une longueur égale à I/T 7 1 T = /2; par consé- quent les expressions ( 2) et ( 4) diffèrent fortement. Condition relative à la pente Afin d'empêcher une comparaison le long d'un trajet extrêmement déséquilibré, une succession de tra- jets seulement latéraux ou verticaux n'est pas autorisées mais le trajet latéral ou vertical est combiné à un trajet oblique; en effet on utilise des trajets 23 et 24, qui font l'objet d'une condition sur la pente, comme représen- té sur les figures 2 et 4 Le trajet qui fait l'objet d'une condition sur la pente, contribue fortement à amélio- rer l'opération de reconnaissance, mais implique un accrois- sement de la quantité des calculs. -Première forme de réalisation La figure 5 A montre, sur la matrice de distances D, un exemple de points de calcul dans l'appareil de com- paraison selon la présente invention Sur la figure 5 A, des petits cercles 18 a repèrent des points du réseau, o un cal- cul a lieu, et des points noirs 18 b repèrent-des points du réseau o aucun calcul n'a lieu Comme cela est visible sur la figure 5 A, le calcul à itérations successives de la programmation dynamique n'est pas effectué en chaque point du réseau, mais en un point du réseau distant de N (N > 3; dans cetexemple N = 5) points de chaque échelon de calcul C'est-à-dire qu'un calcul en un premier échelon est effectué pour chaque point du réseau 18 a 1 o i +j = 2 + N; un calcul du second échelon est effectué pour chaque point du réseau 18 a 2, o i + j = 2 + 2 N; un cal- cul à un troisième échelon est effectué pour chaque point du réseau o i + j = 2 + 3 N; ensuite les calculs sont ef- fectués -de façon similaire pour des points du réseau distants de N points Les trajets de programmation dynamiques reliant les points du réseau ainsi espacés forment un côté du même losage et les longueurs des trajets de programmation dyna- mique sont tous égaux en termes de distance euclidienne et en outre la condition relative à la pente est naturelle- ment présente De plus l'angle de la direction partant du point de départ du losange jusqu'au point d'extrémité de ce dernier est plus faible que dans le cas représenté sur la figure 3. Comme décrit ci-dessus, conformément à la présen- te invention, le calcul à itérations successives de la comparaison dé programmation dynamique est effectué uni- quement pour les points du réseau distants de N Points et donc le nombre des répétitiorsdu calcul à itéra- tiorssuccessives permettant de calculer les scores dans le cas du suivi d'un trajet optimum est égal à 1/N fois le nombre requis dans le procédé de l'art antérieur, qui met en oeuvre le calcul à itérations successives en chaque point du réseau; en effet la quantité de calculs peut être notablement réduite En outre les longueurs des trajets de programmation dynamique sont tous égaux en termes-de dis- tance euclidienne et par conséquent il n'existe aucune dif- férencequant à la longueur du trajet de programmation dy- namique En outre, étant donné que chaque trajet lui-têrmte est oblique, la condition concernant la pente, imposée aux trajets verticaux et latéraux, peut naturellement être in- troduites Les trajets de programmation dynamique n'ont pas dé coudes brusqueset le calcul de la valeur de l'inté- grale de la distance le long des trajets consiste à calcu- ler une quantité proche de la valeur de l'intégrale obtenue avec l'expression ( 4) dans le système continu; c'est-à-dire que la valeur de l'intégrale indiquée ci-dessus est voisine de la valeur idéale. Ci-après on va donner une description d'une mémoi- re tampon G(k) servant à mémoriser la valeur calculée succes- sivement au point (i,j), c'est-à-dire la valeur de la fonc- tion de coût g(i,j) Dans ce cas, k = j i On choisit com- me échelcpour le calcul à itérations successives de la com- paraison à programmation dynamique chaque point du réseau (i,j) qui satisfait à la relation i + j = 2 + N 9, comme re- présenté sur la figure 7, et le calcul à itérations succes- sives de la comparaison de programmation dynamique est ef- fectué pour les points du réseau dans l'ordre Z = 1, 2, Par exemple, étant donné que la valeur précédente calculée g nécessaire pour le calcul en chaque point du réseau situé au (Z+ 2)-ème échelon est uniquement la valeur calculé-dans un ( res tampons G(-r) à G(r) en un nombre double du nombre r des points du réseau dans chaque échelon; ainsi' le cal- cul à itérations successives peut être effectué-avec un nombre plus faible de mémoires tampons que par le passé. Dans l'art antérieur, comme cela ressort des trajets 23 et 24 représentés sur la figure 4, le calcul à itération successives à chaque échelons requiert également les valeurs calculés g obtenues trois échelons auparavant; c' est-à-dire qu'il est nécessaire de mémoriser toutes les valeurs calculées g dans-une zone repérée par 30 sur la figure 2 et un nombre plus important de mémoires tampons est nécessaire Exemples spécifiques d'expressions de calcul Ci-après on va donner la description d'exemples de calcul à itérations successives en chaque point de calcul dans le cas de la mise en oeuvre de la présente invention. lDans le cas de N = 33 Exemple 1 La figure 6 A représente des trajets de programma- tion dynamique de la comparaison à programmation dynamique dans le cas d'un calcul au niveau du point (i,j) du réseau. Les trajets de programmation dynamique sont un trajet 27 a entre les points du réseau (i-l,j-2) et (i,j) et un trajet 27 b entre les points du réseau (i-2, j-l) et (i,j), et la distance entre les séquences A et B sur chaque trajet est représentée par di j. g(k 1) + dij g(k) = min ( 6) g(k + 1) + dij o k = j i Les termes supérieurs et inférieurs situés sur le côté droit de l'expression ( 6) concernent respectivement les trajets 27 a et 17 b g(k-l) et g(k+l) sont calculés conformé- ment aux contenus des mémoires tampons G(k-l) et G(k+l) et on utilise le plus faible de ces contenus comme valeur g(k). Exemple 2 On obtient les distances entre les séquences A et B sur les trajets de programmation dynamique 27 a et 27 b en * réalisant une interpolation des éléments des points du ré- seau à proximité de ces trajets C'est-à-dire que, comme re- présenté sur la figure 6, la distance entre les séquences A et B au niveau de l'intersection de la droite reliant les points du réseau (j-l, j-l) et (i,j-l) avec le trajet 27 a peut être calculée à partir des distances dilj_ 1 et dij_ 1 au niveau de ces points du réseau, de la manière suivante: di-j,j-1 + di,j-1 Cette valeur est considérée comme étant la dis- tance entre les séquences A et B sur le trajet 27 a Con- formément à cela, il est possible d'obtenir une valeur plus proche de la distance entre les séquences A et B sur le tra- jet 27 a que dans le cas de l'utilisation de dl dans l'exem- ple 1 De façon similaire la distance entre les séquences A et B sur le trajet de programmation dynamique 27 b est obtenue de la manière suivante: d + d. i-l,j 2 i-l,j-1 Etant donné que les distances sur ces trajets sont toutes multipliées par 1/2, le coefficient 1/2 est inutile lors de l'obtention d'une valeur minimum'de ces distances. Par conséquent l'expression suivante est valable: g(k-1) + dij 1 + dilj 1 g(k) t min g(k+l) + dij + dil,j-1 min{g(k-l) + di j_ 1, g(k+l) + di_j j}+ di jj-1 ( 7) Exemple 3 Dans le cas de la détermination des distances en- tre les séquences A et B sur les trajets de programmation dy- namiques par interpolation comme décrit ci-dessus, il est également possible de décaler les trajets de programmation dynamique afin de faciliter l'interpolation En d'autres ter- mes, le point de calcul n'a pas besoin d'être toujours le point du réseau Par exemple, comme représenté sur la figu- re 6 C, les points de calcul sont chacun décalés de la moi- tié de la distance entre des points voisins respectivement suivant une direction latérale (i) et suivant une direc- tion verticale (j) Dans ce cas le calcul itératif est le suivant: g(k) = min {g(k-l) + dijl g) + d g(k+) + di_l,j} + dij ( 8) lDans le cas de N = 53 Exemple 4 Dans cet exemple, N = 5 et l'on utilise des tra- jets de programmation dynamique 27 a et 27 b obtenus par dé- calage d'un trajet entre les points du réseau (i-2,j-3) et (i,j) et d'un trajet entre les points du réseau (i-3,j-2) et (i,j) de la moitié de la distance entre les points du ré- seau suivant les directions respectives i et j L'expression des calculs successifs devient la suivante: g(k-) m+ 3 (di-lj-2 + dij) + di-lj-1 ij- g(k) v min g(k+l) + 3 (di_ 2,j_ 1 + di,j) + di-lj-1 + di-l,j ( 9) Dans le cas de l'exemple 1, la quantité de calculs par échelon de calcul est égale environ au quart de la quan- tité de calculs qui est nécessaire dans la ccmparaison à pro- grammation dynamique représentée sur la figure 2 (désignée ci-après sous le terme de méthode classique) et la quanti- té de calculs mise en oeuvre tout au long de la ccmnaraison à programmation dynamique est égale environ au douzième (= 1/4 x 1/3) de la quantité entrant en jeu dans la métho- de classique La quantité de calculs dans les exemples 2 et 3, comparée à celle mise en jeu dans la méthode classique, est égale approximativement à la moitié par échelon de cal- cul et environ au sixième pour l'ensemble La quantité de calculs dans l'exemple 4, comparée à celle requise selon la méthode classique, est égale environ aux 5/4 par éche- lon et environ au quart (= 5/4 x 1/5) pour l'ensemble Cette valeur 1/5 est basée sur une diminution du nombre des éche- lons de calcul. Afin de vérifier l'efficacité de la comparaison à programmation dynamique des exemples 1 à 3 décrits ci-des- sus, on a comparé son temps de traitement et sa performan- ce de reconnaissance par rapport à ceux de la comparaison à programmation dynamique de la méthode sans pseudo-bords mentionnée précédemment (désignée ci-après comme étant la méthode classique) L'objet de la reconnaissano était cons- titué par des informations vocales de mots de 641 villes énoncés deux fois par quatre hommes Comme méthode de recon- naissance des mots, on a utilisé méthode à subdivision indi- quée dans le compte rendu 1-1-17 de la réunion d'automne drganiséepar la Société Japonaise d'Acoustique en Octobre 1980 Avec cette méthode de subdivision, la quantité de calculs est presque dépensée pour la comparaison à program- mation dynamique. On va donner une description de la comparaison du temps de traitement Lorsque l'on a effectué un test de reconnaissance de 641 x 641 mots au moyen de la métho- de classique grâce à l'utilisation d'un mini-ordinateur P.E 3240, le temps de traitement fut d'environ 210 minutes. Dans les mêmes conditions que dans l'expérience ci-des- sus,le temps de traitement fut égal à environ 60 minutes dans le cas de l'exemple 1 et à environ 70 minutes dans le cas des exemples 2 et 3 Ceci indique que la quantité globale de calculs mis en jeu par la méthode de subdivi- sion est inférieureau tiers de la quantité de calculs in- tervenant dans le cas de la méthode classique. Ci-après on évalue le rendement de-reconnaissance des exemples 1 et 2 en utilisant les informations vocales desquatre personnes Avec la méthode classique, on a obte- nu en moyenne un taux de reconnaissance de 96,3 % Dans les exemples 1 et 2 on a obtenu respectivement des taux de reconnaissance de 94,7 % et 95,6 % La performance de reconnaissance dans l'exemple 3 a été essentiellement la même que-dans le cas de l'exemple 2 On s'est rendu compte que la méthode selon la présente invention fournissait un taux élevé appréciable de reconnaissance, bien que présen- tant une performance de reconnaissance légèrement infé- rieure à celui de la méthode classique. Bien que par le passé le trajet de programmation dynamique ait été décrit comme étant situé sur un côté du- losange réunissant les points du réseau distants de N points, on peut également utiliser une diagonale du losange pour ser- vir de trajet de programmation dynamique La figure 5 B mon- tre à titre d'exemple de tels trajets de programmation dyna- mique en liaison avec le cas de N = 3. Dans la comparaison classique à programmation dynamique, étant donné que la longueur du trajet de pro- grammation dynamique est basée sur la distance des blocs des mots des villes la longueur du trajet vertical ou du trajet latéral 19 ou 20 est la longueur unité comme re- présenté sur la figure 3; par conséquent deux poids sont attribués au trajet oblique 21 bien qu'un poids 1,414 (=/2) devrait lui être attribué Par conséquent le trajet oblique est affecté d'un poids supplémentaire par multipli- cationpar 1,414 (= 2//2) Dans la seconde forme de réalisation de la seconde invention, par exemple, comme représenté sur la figure 8 A qui illustre le cas N = 5, le rapport entre la longueur d'un trajet 25 le long d'un côté du losange et la longueur d'un trajet 26 le long de la diagonale du losange est égale à 1,2:1 et même si leurslongueurs sont considérées comme égales, il ne se pose aucun problème dans la pratique Dans le cas N = 4, le rapport entre les longueuxsde deux trajets 27 et 28 est égal à 1,12:1 comme représenté sur la figure 8 B et, également dans ce cas, il ne se pose aucun problème même si ces trajets sont considé- rés comme ayans des longueurs identiques Par conséquent, conformément à la seconde forme de réalisation de la pré- sente invention, la différence de longueur du trajet, qui apparaissait dans le méthode de l'art antérieur, peut être éliminée D'une manière générale également dans le cas o N est égal ou supérieur à 3, la différence de la longueur du trajet est éliminée comme suit: Lorsque N est impair: /1 + ( 1)2: 1 Lorsque N est pair: /1 + ()2: 1 Exemples spécifiques de l'expression de calcul On va donner une description d'exemples de l'ex- pression du calcul à itérations successives pour chaque point de calcul dans le cas de la mise en oeuvre de la seconde forme de réalisation de la présente invention. Exemple 5 La figure 9 A représente des trajets de programma- tion dynamique dans le cas N = 3, qui sont le trajet 27 a entre les points du réseau (i-l,j-2) et (i,j), le trajet 26 entre les points du réseau (i-3,j-3) et (i,j) et le tra- jet 27 b entreles points du réseau (i-2,j-l) et (i,j) Con- formément à ces trajets, l'expression des calculs successifs est la suivante: g(k-l) + dij g(k) m rin k)d+ g(k)min g(k) + di_lj 1 2 di 2,j 2 + di 1 lj_ 1 ( 10) g(k+l) + dilj Les termes supérieurs, médians et inférieurs sur le côté droit de l'expression ( 10) correspondent res- pectivement aux trajets 27 a, 26 et 27 b et le coefficient du troisième terme médian est une constante destinée à ren- dre les longueurs des trajets 27 a et 27 b égales à la lon- gueur du trajet 26 Incidemment, le trajet 26 est un tra- jet obtenu dans unecomparaison linéaire et est désigné sous le terme de trajet de programmation dynamique 1/1. Exemple 6 Il s'agit du cas dans lequel les trajets de programmation dynamique 26 a, 26 et 27 b de l'exemple 5 sont décalés respectivement suivant les directions i et j de la moitié de l'espace des points du réseau, comme cela est représenté sur la figure 9 B. g(k-l) + dij 1 + d g(k) = min g(k) 2,j 2 + dil,j_ 1 + di j) x 4/3 ( 11) g(k+l) + dijj + di La valeur 4/3 situéedans le terme médian sur le côté de droite est un poids servant à rendre égales des longueurs de trajets Dans cet exemple, étant donné que tous les éléments de matrice sur le trajet de programma- tion dynamique 1/1 sont inclus dans le calcul, la préci- sion de la comparaison est accrue. Exemple 7 C'est le cas de N = 4 et les trajets de program- mation dynamique sont représentés sur la figure 9 C Un tra- jet entre les points du réseau (i-l,j-3) et (i,j), un tra- jet entre les points du réseau (i-2,j-2) et (i,j) et un tra- jet entre les points du réseau (i-3,j-3) et (i,j) sont déca- lés respectivement de la moitié de l'espacement des points du réseau, suivant les directions i et j. g(k-2) + 3 dij + 2 (di,2 + dij ii 1 i,j-î 2 d,2 d) dil,j-2 + di+l,j g(k) = min g(k) + (di j + di_lj_ 1 l) x 9/2 ( 12) g(k+ 2) + 3 di_lj + 2 (di-2, j + di,j) + di-2,j-,1 dij+l Le rapport entre les distances aux points du ré- seau (i-l,j-2) et (i,j-2) est 2:1, de sorte que, afin de donner un poids correspondant à ce rapport, le trajet 27 a est pondéré sous la forme di _ lj-2, 2 dij-2 dans le terme supérieur du côté droit Les autres trajets sont pondérés de façon similaire. Exemple 8 C'est le cas dans lequel les trajets représentés sur la figure 9 C sont utilisés et l'expression de calcul est amen 6 esous une forme plus simple que l'expression ( 12). g(k) = min g(k-2) + 2 di,j-1 g(k) + dij + di-lj-_ g(i+ 2) + 2 di_ 1,j Exemple 9 C'est le cas o N = 5 et les trajets de la compa- programation dynamique sont représentis sur la fi- g(k) = min g(k-l) ±3 (di 1,j-2 + dij) + di-lj + di,j-1 g(k) + (dij + dil, j-1 + di-2,j-2 + di_ 3,j_ 3 + di_ 4,j_ 4) x 16/5 g(k+l) + 3 (di_ 2,j-1 + di,j) + di-l,j-1 + di 1, J Exemple 10 - C'est le cas o N = 6 et les trajets de programma- tion dynamique sont représentés sur la figure 9 E. g(k) = min g (k-2) g(k) + g(k+ 2) + d,+ d + d,jl+ di 2 + di 13 (dij + d-l,j-1 + di-2,j-2) x 4/3 + dij +d + dilj + di-2,j 1 + di 3,j li, i-l,j i-2,j-l i-3,j-1 ( 15) Ainsi la valeur calculée g(i,j) de la formule de récurrence du calcul à itération successives est déterminée par g(k-1), g(k) et g(k+l) (dans le cas o-N est un nombre pair, g(k), g(k+ 2) et g(k-2)) et par la valeur de la ma- trice D de distances des points au voisinage du point (i,j). ( 13) raison à gure 9 D. ( 14) Ci-après on va établir une comparaison simple entre les quantités de calculs nécessaires pour la comparaison à programmation dynamique dans les cas o l'on utilise les expressions de calcul représentées dans les exemples 5 à 10 et la quantité de calculs nécessaire pour la comparaison à programmation dynamique selon lé système classique. (Exemple 5) La quantité de calculs par éche ion est essentiellement égale à la quantité de calculsin- tervenant dans le système classique de comparaison à pro- grammation dynamique, mais étant donné que le nombre de calculs d'itérations successives est égal au tiersde celui intervenant dans le système classique, la quantité globale de calculs est égale environ au tiers de celle requise dans le système classique. (Exemple 6) La quantité de calculs par éche- lon est égale à environ aux neuf huitièmesde celle inter- nant dans le système classique et la quantité globale de calcule est égale environ au tiers (= 9/8 x 1/3). (Exemple 7) La quantité de calculs par éche- lon est environ 2,5 fois supérieure à celle intervenant dans le système classique, mais la quantité globale de calculs est approximativement égale à 2,5 x 1/4 fois celle interve- nant dans le système classique. (Exemple 8) La quantité de calculs par éche- ion est égale à environ 2/3 de celle intervenant dansle système classique et la quantité globale de calcul est éga- le environ au sixième ( 2/3 x 1/4) de celle intervenant dans le système classique. (Exemple 9) La quantité de calculs par éche- lon est égale approximativement au double de celle nécessai- re dans le système classique, mais la quantité globale de calculs est égale environ au deux cinquièmes Je celle re- quise dans le système classique. (Exemple 10) La quantité de calculs par éche- Ion est égale environ auctreize huitièmesde celle interve- nant dans le système classique, et la quantité globale de calculs et égale environ au quart (= 13/8 x 1/6) de celle nécessaire dans le système classique. Pour mettre en évidence l'efficacité de la pré- sente invention, on a comparé les exemples 6 et 9 à la méthode de comparaison à programmation dynamique du type sans pseudo-bords, mentionn&-précédemment (méthode désignée sous le terme de comparaison à programmation dyna- mique selon la méthode classique) en rapport avec le temps de traitement et la performance de reconnaissance L'objet de la reconnaissance était constitué par des informations vocales de mots des noms de 641 villes, répétées deux fois par quatre hommes On a utilisé la méthode de subdivision mentionnée précédemment Tout d'abord on a effectué la comparaison du point de vue du temps de traitement Dans le cas d'un essai de reconnaissance de 641 x 641 mots avec la comparaison à programmation dynamique selon la métho- de classique grâce à l'utilisation d'un micro-ordinateur Perkin-Elmer 3240 sous la commande d'un programme FORTRAN, le temps de traitement fut de 210 minutes Au moyen de la comparaison à programmation dynamique des exemples 6 et 9, les essais de reconnaissance furent-terminés en une durée d'environ 110 minutes Ceci indique que le temps de calcul au moyen de la méthode de sudvision est égal à environ la moitié de celui mis en jeu par-la comparaison à programmation dynamique selon la méthode classique, pourvu que la quantité de calculs mise en oeuvre par la comparaison à programmation dynamique de la seconde forme de réalisation soit faible. Ensuite, on a évalué la performance de reconnaissance en utilisant les informations vocales des quatre personnes. Avec la comparaison à programmation dynamique selon la mé- thode classique, le taux de reconnaissance fut en moyenne de 96,3 % Dans le cas de l'utilisation de la comparaison à programmation dynamique de l'exemple 6, le taux de recon- naissance fut'en moyenne de 96,2 % et dans le cas de l'uti- lisation de la comparaison à programmation dynamique de 1 ' exemple 9, le taux de reconnaissance fut en moyenne de 95,6 % On a pu établir que la performance de reconnaissance dans le cas des exemples 6 et 9 était essentiellement éga- le à celle de la comparaison a programmation dynamique selon la méthode classique. Méthode sans pseudo-bords Comme cela a été décrit précédemment en référence à la figure 2 il est d'une pratique générale dans la techni- que d'effectuer la comparaison à programmation dynamique sur la matrice de distances, que l'on peut calculer à partir d' éléments succédant aux éléments a 1 et b 1 au point de départ (i = 1, j = 1) de l'extraction de la parole En raison de ce fait, la technique antérieure fait l'objet du défaut de reconnaissance provoquée par l'ambiguïté du départ de 1 ' extraction de la parole Afin d'améliorer cet état de choses, l'auteur de la présente invention a proposé la méthode sans pseudo-bords mentionnée précédemment Conformément à cette méthode, l'initialisation 'de la comparaison à programmation dynamique sur une matrice de distances entre une séquence A = a 1, a 2, an et une séquence B = bl, b 2, bm comme représenté sur la figure 10 est effectuée comme suit: g( 0) = 2 x d 1 g(jl) = g(j-2) + dlj pour 2 2518783 - départ 28 Incidemment, dans le cas de la comparaison clas- sique à programmation dynamique représentée sur la figure 2, g(j-l) = pour 2 2 Pour cette initialisation, on effectue les ité- rations successives de l'expression ( 1) à partir du point du réseau (i,j) possédant une faible valeur jusqu'au point d'extrémité (i=n, j=m) Le point d'extrémité est également r. choisi de sorte que c'est une région 34 de (n r à n, m) m r et (n, m a à m), qui peut être le point d'extrémité Ain- 2- si la méthode sans psudo-bords permet des trajets particu- liers uniquement suivant les directions verticale et laté- rale au voisinage du point de départ Cette méthode est supérieure au système illustré sur la figure 2, mais il peut apparaître quelquefois une correspondante anormale affectant de façon nuisible la performance de reconnais- sance. Troisième forme de réalisation On va donner une description de la méthode selon la présente invention,(désignée ci-après sous le nom de mé- thode sans bords) qui résoud le problème de l'ambigu Lté mentionnéeprécédemment du départ de l'extraction de la paro- le Comme entrées on utilise des séquences du-départ ambigu de l'extraction, A = an, a O a 1 an an, et B = bm, - b O b 1 bm bmi,, Dans la comparaison à programmation dyna- mique de l'art antérieur, le calcul à itératiorssuccessives est répété à partir du point de départ al,b 1 (le point du réseau ( 1,1)) jusqu'au point d'extrémité an, bm (du point du réseau (n,m)) et l'axe des temps n'est pas dilaté et comprimé linéairement de sorte que le score prend une va- leur minimum C'est un cas analogue à ce qui est représen- té à la figure 2 Dans la comparaison à programmation dyna- mique de -la présente invention, au point de départ,la valeur di, de la distance à partir d'un élément précédant l'élément a 1 ou b 1 est également utilisée Afin de réaliser cela, les points du réseau au niveau du (ú= 0)-ème échelon de la com- paraison à programmation dynamique sont accrus par dilata- tion sous la forme d'une région d'éléments précédant l'élé- ment a 1 ou hb, comme représenté sur la figure il Par consé- quent le point de départ, qui est seulement le point du ré- seau ( 1,1) dans la comparaison classique à conformation dy- namique, est accru par dilatation pour prendre la forme d'un ensemble de points du réseau (,it) à l'intérieur de la fenê- tre d'ajustement qui satisfait à i + j = 2 La valeur ini- tiale du calcul à itérations successives dans l'ensemble (-1,3), ( 0,2), ( 1,1) ( 2,0), ( 3,-l) des points du réseau (i,j)ei + j = 2 au point de départ est réglée à g(k) = O (o k = j i) De façon similaire, le point d'extrémité est accru par dilatation sous la forme d'un ensemble (ij) de l'échelon 9 max à l'intérieur de la fenêtre d'ajustement, qui satisfait à i + max, Forme de réalisation spécifique En référence aux figures 12 et 3 on va donner la description, d'un exemple spécifique d'un appareil de reconnaissance vocaled'un mot, mettant en oeuvre la com- paraison à programmation dynamique de la présente invention, décrite précédemment A un bus 55 sont raccordés une unité centrale de traitement (désignée ci-après sous le sigle abrégé CPU) 41 servant à la commande de l'ensemble du système, uneunité 42 d'analyse de coefficients d'autocor- rélation, un tampon d'-entrée 43, une unité 44 d'analyse LPC (à code prédictif linéaire) une unité 45 de calculs des paramètres caractéristiques, une mémoire 46 de formes vocales d'entrée servant à la mémorisation d'une séquence temporelle de paramètres caractéristiques d'une parole d'en- trée, une mémoire 47 de formes de référence dans laquelle sont mémorisées des séquences temporelles de paramètres ca- ractéristiques de formes de référence de tous les mots de- vant être reconnus, une unité 48 de calculs de la matrice de distances servant au calcul d'une matrice de distances entre deux séquences temporelles, un tampon 49 de la matri- ce de distancespour la mémorisation d'éléments de la matri- ce de distances calculées,une unité 51 de calcul de la fonc- tion de coût servant à calculer une valeur de fonction de coût dans le calcul à itérations successives dela ccmparai- son à programmation dynamique, une mémoire à accès direct (désigne ci-après sous le terme abrégé RAM) 52 servant à mémoriser des données des paramètres nécessaires pour dif- férents calculs, des résultats intermédiaires de calculs, des indices pour les calculs et ainsi de suite, une sec- tion de sortie 53 pour la délivrance des résultats de la reconnaissance, et une mémoire morte (désignée ci-après sous le sigle abrégé ROM) 54 dans laquelle se trouve mémo- risé un programme indiquant des moyens de commande de l'en- semble du système L'unité centrale CPU 41 lit de façon sé- quentielle le programme à partir de la mémoire ROM 54 et le décode et l'exécute,,en effectuant le traitement de reconnaissance comme décrit ci-après. Au cours du pas 51 dans l'organigramme de la fi- gure 13, une parole d'entrée introduite à partir d'une bor- ne d'entrée 56 est envoyée à un convertisseur analogique/ numérique 57, dans lequel elle est échantillonnée par exemple à une fréquence de 8 k Hz et chaque valeur échan- tillonnée est convertie en un signal numérique à 12 bits qui est envoyé à l'unité 42 de calcul des coefficients autocorrélation Dans le pas 52, l'unité 42 de calcul des coefficients d'autocorrélation accentue une composantaà haute fréquence du signal vocal d'entrée, comme cela est requis, puis calcule les coefficients d'autocorrélation jusqu'au 10-ème degré par exemple avec une période de séquence de 16 millisecondes, moyennant l'utilisation d'une fenêtre de Hamming de 32 millisecondes Les résultats calculés sont mémorisés dans le tampon d'entrée 43 Au cours du pas 53 les coefficients d'autocorrélation provenant du tam- pon d'entrée 43 sont envoyés à l'unité 44 d'analyse LPC, dans laquelle une analyse LPC (à codage prédictif linéai- re) est effectuée jusqu'au 10-ème degré pour chaque séquen- * ce Le coefficient LPC ainsi obtenu est envoyé à l'unité de calcul des paramètres caractéristiques, dans laquel- le les coefficients du cepstre LPC Cisont calculées jusqu' au 16-eme degré et les coefficient de corrélation Pl sont calculés jusqu'au 16-ème degré d'une enveloppe du spectre LPC, et les résultats calculés sont mémorisés dans la mé- moire de formes d'entrée 46 (pas 54) Dans la mémoire 46 - des paramètres d'entrée se trouve mémorisée une séquence temporelle A de paramètres caractéristiques d'une parole d'entrée de mot, ainsi que le coefficient de cepstre Ci et le coefficient d'autocorrélation Pl en tant qu'élément ai De façon similaire une séquence temorelle B de paramè- tres caractéristiques d'une forme de référence est mémori- sée dans la mémoire 47 des formes de référence, avec le coefficient de cepstre Ci et le coefficient l'autocorréla- M ton Pl en tant qu'élément bi. Au cours du pas suivant 55, la séquence temporel- le A de la parole d'entrée provenant de la mémoire 46 de formes d'entrée et la séquence temporelle B de la forme de référence provenant de la mémoire 47 de formes de ré- férence sont introduites dans l'unité 48 de calcul de la matrice de distance, dans laquelle la distance d entre des éléments respectifs des deux séquences temporelles A et B est calculée en fonction de la valeur WLR fournie par l'expression suivante: 16 - E (C i Pl i=l On obtient de cette manière la matrice de dis- tances,et ce pour toutes les formes de référence du mot devant être reconnu. Ensuite l'opération passe au processus de compa- raison à programmation dynamique et, au cours du pas 56, l'initiation est réalisée C'est-à-dire que lescontenus g(-r) à g(r) des tampons de la fonction de coût G(-r) à G(r) (o r est la largeur de la fenêtre d'ajustement) -prévus dans une région 58 de la mémoire RAM 4 52 sont réglés à O et les autres valeurs sont choisies élevées Une cons- tante M = 5, une valeur maximale d'un nombre i, une valeur minimale du nombre i et k = j i sont positionnées res- pectivement dans les régions 59,61,62 et 63 de la mnmoire RN 4 52. Au cours du pas 57, les données dij dij di-1,j-l di_ 2,j_ 2 g(k-l), g(k) et g(k+l) nécessaires pour le calcul à programmation dynamique conformément à i, j et k dans les régions 61 à 63 sont transférées du tampon 49 de la matrice de distances et du tampon 58 de la fonction de coût à l'unité 51 de calcul de la valeur de la fonction de coût, dans laquelle le calcul suivant est effectué: g(k-l) + dij_ + d, g(k) = min g(k)2,j 2 + dil,j_ 1 + di j) x 4/3 g(k+l) + di_l,j + di,j Le résultat de ce calcul, c'est-à-dire la va- leur de la fonction de coût g(k), est introduit dans le tampon correspondant G(k) de la région 58 Au cours du pas 58, j est réduit d'une unité, i est accru d'une uni- té et k est diminué de deux unités Il en résulte que si le point de calcul (i,j) sort de la fenêtre d'ajustement, les valeurs j = M+r + 1, i = M jet k m j i sont cal- culées avec M + 3 supposé être égal à M De toute façon, ces valeuis M, j, i et k sont mémorisées dans les régions 59, 61, 62 et 63 chaque fois qu'elles sont mises à jour. En outre à chacune de leur mise à jour, il se produit lors du pas 59 une vérification pour savoir si la nouvelle va- n+m leur de M est supérieure à la somme d'un entier (-5) et de 3 Si ce n'est pas le cas, l'opération revient au pas 57, au cours duquel les données requises sont prélevées du tampon 49 de la matrice de distance et de la mémoire RAM 52, et la valeur de la fonction de coût g(k) est cal- culée dans l'unité 51 de calcul de la valeur de fonction de coût et la même opération que décrite ci-dessus est à nouveau effectuée. Dans le cas o la valeur de M est supérieure à la valeur indiquée ci-dessus, la comparaison à programma- tion numérique des deux séquences temporelles A et B est terminée et, au cours du pas 51 o, la distance entre mots S(A:B) à cet instant est calculée au moyen de l'expression suivante: S(A:B) = (Min g (k))/( 3 x (M 3)) (i,j)ei + j = M -3 Cette distance entre mots est mémorisée dans une région 64 de la mémoire RAM 52 Ensuite au cours du pas S il se produit une vérification pour savoir si la séquence temporelle B de la forme de référence, dont la distance à la séquence temporelle A de la parole d'entréedoit être calculée, subsiste encore dans la mémoire 47 de formes de référence S'il en est ainsi, l'opération revient au pas et, s'il n'en est pas ainsi, l'opération se poursuit par le pas 512, lors duquel la région 64 de la mémoire RAM 52 est lue et le nom de mots de la plus courte des distances entre motsobtenues jusqu'alors est délivrée sous la forme d'un affichage ou d'une lettre imprimée, par l'unité de sortie 53, ou est envoyée à un autre dispositif. Dans ce qui précède, l'initialisation au pas 56, la mise à jour des indices au pas 58 V le calcul de la dis- tance entre mots au pas Slo, la décision au cours du pas Sil et 1 a détermination du mot lors du pas 512 sont des opérations qui sont toutes effectuées sous la comman- de de l'unité de commande centrale CPU 41. Effets concrets La comparaison à programmation dynamique utili- sant la méthode sans bords mentionnée précédemment a été évalué au moyen d'un test de reconnaissance Vocale de mots en utilisant des informations vocales de mots de 641 noms de villes répétés deux fois par quatre hommes. L'essai fut effectué dans une salle d'ordinateur dans la- quelle le niveau de bruit était compris entre 68 et 70 d B(A) et dans laquelle les informations vocales étaient introduites moyennant l'utilisation d'un microphone élec- trodynamique Les informations vocales obtenues en premier lieu et les informations vocales obtenues deux semaines ul- térieurement serontconsidérées comme formant respectivement l'ensemble A et l'ensemble B La parole fut appliquée à un filtre passe-bas à 4 k Hz et échantillonnée à 8 k Hz, puis une analyse d'autocorrélation au douzième degré fut effec- tuée en utilisant une fenêtre de Hamming de 32 ms avec des pas de 16 ms Dans une zone des coefficients de corréla- tion, la région à haute fréquence fut accentuée en utili- sant un filtre à un pôle d'annulation ( 1 Z-1), après quoi la région à basse fréquence fut pondérée au moyen d'un filtre à un pôle d'annulation ( 1 + 0,3 Z 1)' pour la mesure WLR Ensuite on a effectué une analyse LPC du di- xième degré La période vocale des mots fut extraite automatiquement en utilisant ureinformation de puissance. Comme méthode de reconnaissance, on aemployé la méthode à SUIDM ISI Nutilisant la valeur de mesure WLR. Pour chaque personne parlante, on a produit 128 formes de référence de pseudo-phonèmes à partir des données vo- cales de plus de 90 des premiers mots de l'ensemble A, de sorte que l'on a pu réduire une distorsion du spectre par la mesure WLR Ensuite on a obtenu des formes de ré- férence de mots (séquences de quasi-phonèmes) en utilisant les données vocales de l'ensemble A Pour effectuer la comparaison à programmation numérique selon la méthode sans bords, il est nécessaire d'utiliser des séquences vocales précédant le point de départ et succédant au point d'ex- trémité La donnée pour l'évaluation est déjà extraite et envoyée à une base de données Par conséquent les séquences précédant le point de départ et succédant au point d'extrémité furent extrapolées au moyen de sé- quences marginales lors de cet essai de reconnaissance. La comparaison à programmation dynamique sans bords selon la présente invention fut évaluée en utili- sant les données vocales de l'ensemble B On a comparé cette comparaison à la comparaison à programmation dyna- mique sans pseudo-bords mentionnée précédemment (DP-OLD) et à la comparaison à programmation dynamique des pre- mière et seconde formes de réalisation de la présente in- vention utilisant la méthode sans pseudo-bords Le tableau 1 montre les taux moyens de reconnaissance des mots des quatre personnes parlantes De même on a représenté sur le tableau 1 les temps de traitement obtenus lors d'es- sais de reconnaissance de 641 x 641 mots selon la méthode de comparaison à programmation dynamique sans pseudo-bords des première et seconde forme de réalisation En consi- dérant que, sur l'ensemble du temps de reconnaissance des 641 x 641 mots, environ 25 minutes sont nécessaires pour l'analyse LPC et le calcul de la mesure WLR et qu ' en- viron 20 minutes sont nécessaires pour la réalisation de la comparaison de la programmation dunamique autre que les calculs successifs, le temps de reconnaissance des 641 x 641 mots contenu dans le tableau 1 et les quantités globales de calculs décrites précédemment en liaison avec les première et seconde forme de réalisation présen- tent une excellente correspondance comme cela est illustré sur la figure 14. Sur la figure 14, A, B, C, D, E, F, G et H repèrent respectivement les exemples 1, 2, 3, 5, 6, 7, 9 et 10 et la comparaison DP-OLD Dans le tableau 1, les temps de traitement des exemples -7 et 10 sont des temps de reconnaissance dans le cas de la méthode dite sans -.;: 2518783 bords Le surcroît du taux de reconnaissance des mots avec l'utilisation de la comparaison à programmation dy- namique sans bords selon la présente invention par rap- port aux taux de reconnaissance des mots moyennant-l'uti- lisation de la comparaison à programmation dynamique sans bords selon la présente invention augmente de 0,1 à 0,8 %; on peut voir que le traitement sans bords est efficace. Dans le cas du traitement sans bords dans le test indiqué ci-dessus, les séquences précédant le point de départ et succédant au point d'extrémité ont été remplacées par des séquences marginales,mais on considère que le taux de reconnaissance serait encore accru dans le cas de l'utilisa- tion de séquences de données vocales réelles - TABLEAU 1 Temps de trai Taux de recon Taux de recon- tement naissance sans naissance sans (minutes) pseudo-bords bords (%) (%) DP-OLD 210 96,3 Exemple 1 60 94,7 94,8 Exemple 2 70 95,6 95,8 Exemple 3 70 94,7 95,5 Exemple 5 85 95,9 96,5 Exemple 6 110 96,2 96,7 Exemple 9 110 96 96,6 Exemp Dle 7 _ 140 _ 95,7 Exemple 10 100 95,9 Bien que dans ce qui précède la description ait porté sur la méthode de comparaison à programmation dyna- mique basée sur la distance entre des paramètres caractéris- tiques, la présente invention est également applicable au cas de la mise en oeuvre de la comparaison à programmation dynamique utilisant la similarité entre les paramètres carac- téristiqueset, dans un tel cas, il suffit d'introduire 1 ' indication max (maximum) à la place de l'indication min (mi- nimum) dans chacune des expressions mentionnées précédemment. Un accroissement de la valeur de N réduit le taux de recon- naissance et, dans le cas du même langage de mots, la dif- férence de vitesse entre les séquences temporelles A et B n'est pas aussi importante; par-conséquent en supposant que le trajet de programmation dynamique selon la méthode de comparaison linéaire est représenté par un trajet 1/1 com- me mentionné précédemment, le trajet de programmation dyna- mique utilisable dans la présente invention est préféré à un trajet N,1 t lorsque N est un nombre impair et à un tra- N-2 Nl jet N+ 2 lorsque N est un nombre pair En outre la présente invention peut être appliquée non seulement à la comparai- son à programmation dynamique entre des séquences temporel- les de parole F,mais également à la comparaison à programma- tion dynamique entre des séquences caractéristiques de let- tres manuscrites, par exemple, comme cela a été décrit pré- cédemment. Il ressort à l'évidence que de nombreuses modifi- cations et variantes peuvent être apportées à l'objet de l'invention sans sortir du cadre de cette dernière. REVENDICATIONS 1 Appareil de comparaison de formes de séquences, servant à l'obtention de la mesure de similarité, telle que la distance ou la similarité entre deux séquences de para- mètres caractéristiques A = ai, a 2, an et B = bl, b 2, bm au moyen d'une comparaison à normalisation non linéaire utilisant une programmation dynamique, caractérisé en ce qu'il comporte des moyens ( 48, 49, 51,58) servant à exécu- ter un calcul à itérations successives de la programmation dynamique pour les points de calcul correspondant à tous les points du réseau qui satisfont à la relation i + j = M + N (o M est une constante et N > 3) dans une matrice D = (dij) (ou di, représente la mesure de similarité entre un i-ème élément ai de la séquence A et un j-ème élément bj de la séquence B) entre les séquences A et B, et des moyens ( 41,47,52,54) pour répéter le calcul à ité- rations successives pour les points de calcul correspondant à tous les points du réseau satisfaisant à la relation i + j = M + QN, en rendant séquentiellement Z égal à 1, 2,3, 2 Appareil de comparaison de formes de séquen- ces, selon la revendication 1, caractérisé en ce qu'un trajet de programmation dynamique dans le calcul à itéra- tions successives est choisi parmi deux trajets-dont les longueurs aboutissant au point de calcul sont égales en terme de distance euclidienne. 3 Appareil de comparaison de formes de séquen- ces, selon la revendication 2, caractérisé en ce qu'un tra- jet de comparaison linéaire est ajouté en tant que trajet de programmation dynamique. 4 Appareil de comparaison de forme de séquences selon la revendication 2, caractérisé en ce qu'une valeur. de fonction de coût g(k) obtenue par le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminé par calcul de l'expression suivante: -2518783 g(k) min {g(k-l), g(k+l)} + dij o N = 3 et k = j i. Appareil de comparaison de formes de séquences selon la revendication 2, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenue par le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: g(k) o N = 3 et k = j 1. 7 Appareil de comparaison de formesde séquences selon la revendication 2, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenue par le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: g(k) 4 max {g(k-l) + dij_l, g(k+l) + dil,} + dilj_ i-î,j-,j- o N = 3 et k = j i 8 Appareil de comparaison de formes de séquences selon la revendication 2, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenue par le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: g(k) 4 min {g(k-l) + dij_ 1, g(k+l) + dil 1 j} + di j o N = 3 et k j i. 9 Appareil de comparaison de formes de séquences selon la revendication 2, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenue par le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminéepar le calcul de l'expression suivante: g(k) o N = 3 et k = j i. Appareil de comparaison de formes de séquences selon la revendication 2, caractérisé-en ce qu'une valeur de fonction de coût g(k) obtenue par le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: ng(k-1) + 3 (dil,j_ 2 + di,j) + di-jj + di,j 1- g(k) 4 min g(k+l)-+ 3 (di_ 2,j_-l + dij)+ di-l,j-1 + di-l,j o N = 5 et k = j i. 11 Appareil de comparaison de formes de séquences selon la revendication 2, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenue par le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: g(k-l) + 3 (dilj_ 2 + d ij) + dilj+ dj- g(k) o N = 5 et k = j i. 12 Appareil de comparaison de formee de séquences selon la revendication 2, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenue par le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: g(k)l) + d. r di, j-1 g(k) min g(k) + d 2 d +d i-l,j-1 + i 2,j_ 2 g(k+l) + di_lj o N = 3 et k = j i. 13 Appareil de comparaison de formes de séquences selon la revendication 3, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenue par le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: c(k-1) + dij-1 g(k) max g(k) + dilj-1 + 2 di-2, j 2 + di-lj- g(k+l) + dil,j o N = 3 et k = j i 14 Appareil de comparaison de formes de séquences selon la revendication 3, caractérisé en-ce qu'une valeur de fonction de coût g(k) obtenue par le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: g(k-l) + di, + dij g(k) min g(k) + (di_ 2,j_ 2 + di-l,j-1 + di,j) x 4/3 g(k+l) + di-li + di,j o N = 3 et k = j i. Appareil de comparaison de formes de séquences selon la revendication 3, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenoepar le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: g(k-1) + di,j_ 1 + di,j g(k) max g(k) + (di_ 2,j-2 + dij_+ dij) x 4/3 g(k+ l) + dil, +dij i-l,j, o N = 3 et k = j i. 16 Appareil de comparaison de formes de séquences selon la revendication 3, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenutpar le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par,le calcul de l'expression suivante: g(k) ≤ min g(k-2) + 3 di jl + 2 (di,j-2 + di-l,j-2 + di+l,j g(k) + (dij + dil,j-l) x g(k+ 2) + 3 di_lj + 2 (di_ 2,j + di_ 2,j-1 + di,j+l o N = 3 et k = j i. 17 Appareil de comparaison de formes de séquences selon la revendication 3, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenuepar le calculà itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: g(k-2) + 3 dij+ + 2 (dij 2 + dij) + dil,j-2 + di+l,j g(k) 4 max g(k) + (dij + dil,jl) x 9/2 g(k+ 2) + 3 dii + 2 (di 2, + dij) + d + d i-2,j-1 i, j+l o N =-3 et k = j i. 18 Appareil de comparaison de formes de séquences selon la revendication 3, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenuepar'le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: r g(k-2) + 2 dij_ i,j-1 g(k) ≤ ming(k) + dij + diljl - g(k+ 2) + 2 dil, j o N = 4 et k = j i. 19 Appareil de comparaison de formes de séquences selon la revendication 3, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenoe par le calcul à itérations successi Ves de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: + dij 9/2 + di) 1 ', g(k-2) + 2 dij 1 g(k) = max g(k) + dij + di-_lj_ l g(k+ 2) + 2 dil,j o N = 4 et k = j i. 20 Appareil de comparaison de formes de séquences selon la revendication 3, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenuepar le calcul à itérations successives de la programmation dynamique en chaque point de calcul est déterminéepar le calcul de l'expression suivante: g(kl) + 3 (dil,j-2 + dij) + d il,j-1 + di,j-1 g(k) + (di, + di-l,_-1 + di-2, j-2 g(k)4 = min + di_ 3,j_ 3 + di,4,j_ 4) x 16/5 g(k+l) + 3 (di 2,jl + di) + di_l,jl + dirl,j o N = 5 et k = j i. 21 Appareil de comparaison de formes de séquences selon la revendicaton 3, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenuepar le calcul par itérations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: g(k-1) + 3 (dlj_ 2 + di) + diljl + dij l g(k) max g(k) + (dij + di_ljl + di-2,j-2 + di-3,j 3 + di_ 4,j_ 4) x 16/5 g(k+l) + 3 (di_ 2, + di,j) + dil,j-1 + di-l,j o N = 5 et k = j i. 22 Appareil de comparaison de formes de séquences selon la revendication 3, caractérisé en ce qu'une valeur de fonction de coût g(k) obtenuepar le calcul par iterations successives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression sui- vante: g(k-2) + d + dij_ +dilj 2 + dilj 3 g(k) 4 min g(k) + (dij + dil,j_ 1 + di-2,j-2) x 4/3 =g(k+ 2), -l + dij + dij + di 2,j-1 + di-3,j o N = 6 et k = j i. 23 Appareil de comparaison de formede séquence selon la revendication 3, caractérisé en ce qu'une valeur de fonc- tion de colt g(k) obtenue par le calcul à itérations succes- sives de la programmation dynamique en chaque point de calcul est déterminée par le calcul de l'expression suivante: , g(k-2) + dij + di,jl + di-1,j-2 + di-l,j-3 g(k)ming() (di,j + dil,j-1 + di-2,j-2) x 4/3 g(k+ 2) + di j + dil,j + di 2 j 1i 3,j 1 s\ o N = 6 et k = j i. 24 Appareil de comparaison-de formes de séquences selon l'une quelconque des revendications 1 à 23, caracté- risé en ce que les deux séquences de paramètres caractéristi- ques sont A = an,, a 0, a a et B = bm,, b 0, bl, m o a 1 et b 1 sont considérés comme constituant des points de départ des séquences A et B et rendent nulle la valeur de la fonction de cout g(k) (o k = j i) correspondant au point satisfaisant à la relation i + j = M. Appareil de comparaison de formes de séquences selon la revendication 24, caractérisé en ce que les séquences de paramètres caractéristiques sont A = an,, a 0, al, an, an, et B = bm, b 0, bl, bm, bm, o anet bm sont considérés comme constituant-des points d'extrémité des sé- quences A et B