JPS6265090A - パタ−ン比較装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、特徴ベクトルの系列で表わされた複数種類の
標準パターンと入力パターンとの比較を行ない、入力パ
ターンの識別を行なうパターン比較装置に関し、特に連
続して発声した単語音声の認識などに適用可能なパター
ン比較装置に関する。

従来の技術 人間にとって最も自然な情報発生手段である音声が、人
間−機械系の入力手段として使用出来れば、その効果は
非常に大きい。その場合、音声認識装置としては、より
自然な発声で認識出来る条件として、連続して発声した
音声の認識が出来ることが望ましい。

連続して発声した単語音声の認識に有効なパターン比較
装置として、動的計画法（以下ＤＰと呼ぶ）を２段階用
いたいわゆる２段ＤＰ法を用いたパターン比較装置が既
に実用化されている。

しかし、この２段ＤＰ法は重複した計算が多く計算量が
膨大で、従ってこの方法を用いた実時間処理が可能なパ
ターン比較装置は極めて高速の処理が要求され、装置も
複雑で、高価なものとならざるを得ない。

以上の欠点を除去するために、大幅に計算量の少ないパ
ターン比較装置として、○（Ｎ）ＤＰ法。

ＣＷＤＰ法、ＡＣＤＰ法等を用いたパターン比較装置が
提案されている。しかし、これ等の方法を−・−ドウエ
ア的に実現するためには、高速にアクセス可能な大容量
のメモリを必要とする欠点がある。

本発明は、これ等の欠点を除去したパターン比軸装置を
提供するものであって、特に、特願昭５８−４８６００
号明細書に記載されている前記Ａ　ＣＤ　Ｐ　（Ａｕｇ
ｍｅｎｔｅｄ　Ｃｏｎｔｉｎｕｏｕｓ　ＤＰＭａｔｃｈ
ｉｎｇ）法に適用することを目的とする。この方法は単
語数未知、単語数既知、何れの場合にも適用可能であり
、オートマトン制御も可能である。

本発明を説明するに先だって次にＡＣＤＰ法について説
明する。以後、ここでは簡単のために単語数未知の場合
について説明する。壕だ、本発明のパターン比較装置は
、種々の入力パターンの認識に用いることが出来るが、
以下、連続して発声される連続単語音声を例に説明する
。

人間によ゛り発声される音声は人により１だ時により変
化し、基準となる標準パターンに対し時間的に非線形に
伸縮したものとなっている。この非線形に伸縮している
入力パターンと標準パターンとを比較し、入力音声の認
識を行なうためには、入力パターンと標準パターンの各
特徴ベクトルの対応付けを非線形に行ない、入力パター
ンがどの標準パターンと最も類似しているかを計算する
必要がある。しかし、この入力音声は非線形に伸縮する
とはいっても、異常に長く伸びたり、短くなったりする
ことはない。

このような入力パターンの物理的な特徴に注目し、入力
パターンと標準パターンを比較する際には無制限にすべ
ての可能性について比較するのではなく、入力パターン
の物理的な性質により定する妥当と考えられる範囲につ
いて比較を行なうようにする。

入力音声信号はパターン比較装置において、周波数分析
、ＬＰＣ分析、ＰＡＲＣＯＲ分析、相関分析等により、
いくつかの数値の組（特徴ベク）／りの系列に変換され
、この入力パターンの特徴ベクトルの系列と比較の対象
となる標準パターンの特徴ベクトルの系列とが各ベクト
ル毎に比較される。

この各ベクトル毎の比較値、すなわちベクトル間の距離
を合計した累積距離というものをパターンの類似の尺度
に用いる。この累積距離を計算する場合、各ベクトル毎
の比較をすべての組合せについて行なうのは計ｎ量が膨
大となり、パターン比較装置として実用化することが出
来ない。

入力パターンを一方の軸に、標準パターンを他方の軸と
する平面（以下、ｉ−ｊ平面という）を考えると、入力
パターンおよび標準パターンの各ベクトルの組合せと言
うのは、ｉ−ｊ平面上の各格子点（以下、単に点という
）により示すことが出来る。従って、前記あらゆる組合
せについて各ベクトル間の距離を計算するとは、各点に
おけるベクトル間の距離を計算することであり、累積距
離を計算するとは、入力パターンの特徴ベクトルと、そ
れに対応する標準パターンの特徴ベクトルとのベクトル
間距離を順次計算し、合計していくことである。この累
積距離を計算する過程で選択された、入力パターンと標
準パターンの特徴ベクトルの対応、即ち点列を径路と言
う。前記した入力パターンの物理的な性質を考慮して比
較の範囲を限定すると言うことは、径路の選択に拘束条
件を設けると言うことである。ここで、以後の説明にお
いて用いる用語および記号について説明する。

Ａ：入力パターン（Ａ−ａｌ、ａ２．・・・、ａｏ、・
・・。

ａｌ） ａｌ：入力パターンＡの第ｉフレームの特徴ベクトル Ｉ　：入力パターンのフレーム数 Ｒｎ：第ｎｍ準バター　７　（Ｈｎ＝ｂｎｊ　、ｂｎ２
．、、、、ｂｎｊ　。

・・・、ｂｎｙｎ） ｂｎｊ＝第ｎ標準パターンの第】フレームの特徴ベクト
ル １”：第ｎ標準パターンのフレーム数 ｎ：単語名（単語番号）１≦ｎ≦Ｎ Ｎ：標準パターンの総数 ｄｎ（ｉ、ｉ）：　第ｎ標準パターンの第ｊフレームの
特徴ベクトルｂｎｊと入カッリー ンの第ｉフレームの特徴ベクトル ａ・　とのベクトル間距離 Ｄｎ（ｓ：ｔ）：入力パターンの部分ノ（ターンａ３〜
ａｔと標準パターンＲｎ　との最小 累積距離（以下、部分累積距離と 呼ぶ） Ｄ（ｉ）　：第１〜第ｉフレームまでの入カッくターン
と、各標準パターンの最適な組合せの結合パターンとの
パターン間の距離（以下、終端累積距離と呼ぶ） Ｎ（ｉ）：　　第１〜第ｉフレームまでの入力パターン
に対する各標準パターンの最適な組合せの結合パターン
を求めたときの当該結合パターンを構成する最後尾標準
パターンを示す番号（以下、最後尾単語名と呼ぶ）Ｂ（
ｉ）　：　　Ｎ（ｉ）の始点フレームの１つ手前のフレ
ームを示すフレーム番号（以下、パックポインタと呼ぶ
） Ｄｎ（ｉ、ｊ）：入力パターンの部分パターンａｍ＋１
〜ａ、と標準パターンＲｎの部分パタ −ンｂｎ１〜ｂｎｊ　　との最小累積距離のｍについて
の最小値（以下、途中累 積距離と呼ぶ） Ｂ”（ｉ、ｉ）：　Ｄｎ（ｉ＋ｉ）　　ヲ満ｆｃｆ入カ
バター　ンｃＤ始点位置（以下、途中バックポイン タと呼ぶ） ただし、ＤＰマツチングの径路は、Ｄｎ（ｓ：ｔ）。

Ｄ（ｉ）については入力パターン側の軸を基本軸とする
径路であって、Ｄｎ（ｉ、ｉ）については標準パターン
側の軸を基本軸とする径路である。

ＤＰマツチングによる連続単語音声認識は次なる漸化式
を計算することによって効率的に実行される。即ち Ｂ（ｉ）＝ビ Ｎ（ｉ）＝ｎ“ ただし、ｍ”、ｎ’は式（１）を満たすｍ　、　ｎをｉ
＝１〜工について順次計算すればＮ（Ｉ）、Ｎ（Ｂ（Ｉ
））　、Ｎ（Ｂ（Ｂ（Ｉ））　）　、・・・、Ｎ（Ｂ（
Ｊ・・・Ｂ（Ｉ）・・）））によって入力された単語が
逆の順序で求められる。

第２図は式（１）の計算の物理的意味を説明する図であ
る。ｂはＤｎ（ｍ：ｉ）を計算する場合の径路の拘束条
件の一実施例である。即ち、点（’＋ｊ）に至る径路は
点（ｉ−２，１−１）、（ｉ−１，ｊ−１）。

（’−’　ｒ　ｊ−２）を必ず通り、累積距離が計算さ
れる際、選択された径路に応じて各点のベクトル間距離
に径路上に示した数字で表わされる重み付けがなされる
。このような重みの与え方をすれば同図に示す径路の拘
束条件の許では如何なる径路が選ばれようとも、その径
路に沿う重みの和は入力パターンのフレーム数に等しく
なり一定となる。

ａは入力パターンの第ｎ　＋　１フレームから第ｉフレ
ームまでの部分パターンと第ｎ標準パターンＨｎとのマ
ツチングの様子を示している。直線１は傾斜が％であっ
て、直線２は傾斜が２であり、ＤＰマツチングの径路は
ｂの拘束条件の許では両直線に挾まれる領域に限定され
る。３は選ばれたマツチング径路の一例である。

式（１）を計算するためには、Ｄｎ（ｍ＋１　：　ｉ　
）をｎ＝１〜Ｎについて、ｉと１０　に関係したｍのあ
る範囲に渡って、ｉ＝１〜Ｉのそれぞれについて計算し
なければならない。即ち、第２図ａの例で言えば、ｉが
変わる毎に直線１．２で囲まれる三角形の領域内の全格
子点についてベクトル間距離及び累積距離を計算しなけ
ればならない。

ＡＣＤＰ法は、このＤｎ（ｍ＋１　：　ｉ　）の計算を
ワードスポツティングの考え方を導入して近似的に行な
うことにより、その計算量を大幅に減らすものである。

第３図はＡＣＤＰ法の概念を説明する図である。

ａは径路の拘束条件の一例を示す図である。即ち、点（
’＋１）に至る径路は点（ｉ−２，ｊ−１）、（１−１
、ｊ−１）、（ｉ−１，ｊ−２）を必ず通り、径路上に
示した数字はこの重みを表わす。第２図すに示すものと
の本質的な違いは、このような重みの与え方をすれば同
図に示す径路の拘束条件の許では如何なる径路が選ばれ
ようとも、その径路に沿う重みの和は標準パターンのフ
レーム数に等しくなり一定となると言う点にある。

ＡＣＤＰ法の考え方を要約すれば、 （１）第３図ａの如き標準パターン側の軸を基本軸とす
る径路の拘束条件に従ってＤｎ（ｉ＋　Ｊｎ）　＋Ｂｎ
（ｉ、Ｊｎ）を計算する。

ｊ２）　　ｍ＋１−ｎ＝（ｉ、Ｉｎ）とおいて１）ｎ（
ｔ、■”）からＤｎ（ｍ−ｒ＋１：ｉ）　〜Ｄｎ（ｍ＋
ｒ＋１：ｉ）を近似的に推定する。即ち、 Ｄｎ（ｍ＋１：１）＝Ｄｎ（ｉ、Ｉｎ）拳−Ｊｎ となる。ここで、ｒはＤ”（ｍ＋１　：　ｉ　）の推定
の範囲である。

（１）　、　（２）より、結局 Ｂ”（１１１）−”１ｍ＋１≦Ｂｎ（ｉｊｎ）＋ｒの任
意の点を始点、ｌを終点とするＤｎ（ｍ＋１：ｉ）を近
似的に推定出来たことになる。

この方法を連続単語音声認識に適用すると次のようにな
る。

（１）初期条件 りゆ）＝Ｑ、１３ゆ）＝０ Ｄｎ（−１、１）＝Ｄｎ（ｏ、　ｊ）＝ｏｏ、ｆｏｒ　
ｎ＝＝１−Ｎ、　ｊ＝１〜Ｊ”（２）ｉ＝１〜Ｉについ
て（３）〜（′７）を実行ゆ）　ｎ＝１〜Ｎについて（
４）〜（６）を実行（４）初期値Ｄｎ（ｌ、１）−ｄｎ
（ｉ、１）（５）ｉ＝３〜Ｊｎについて （６）ｒ’＝ｏ〜ｒについて ｍ＋１＝Ｂｎ（ｉ、Ｊｎ） （Ｄ（ｍ’）＋ｒｆ′（ｍ’＋１　：１）１（７四゛）
−０７＝１゜−０，。。７０．。−１４，Ｎ、３（８）
判定処理（前記の如＜　Ｂ（ｉ）、　Ｎ（ｉ）から単語
列を逆の順序で求める） 以上の処理からも明らかなように、ＡＣＤＰ法によれば
、最も計算量の多いｄｎ（ｌ＋＋）の計算を含むステッ
プ（４１、（（へ）の計算は各ｉ、ｎについて１回行な
うのみでよいから、通常の２段ＤＰに比べると計算量が
大幅に減少するものである。

ところが、前記ベクトル間距離ｄｎ（ｉ＋＋）、途中累
積距離Ｄｎ（１１１）を７　Ｖ　−ムｉ毎にｎ＝１〜Ｎ
。

ｊ＝１〜Ｊｎ　について求めるためには、標準パターン
記憶用メモリとして、かなり高速なアクセスが要求され
ることになる。例えば、フレーム周期を５ｍ５ｅｃ　　
、標準パターン数Ｎ＝３００．標準パターンの平均フレ
ーム数１　＝３０とすれば、入力パターンのフレーム当
たりの計算すべき平均の格子点数はＮ　１　＝９０００
であり、特徴ベクトルの次元数を１５とすれば、入力パ
ターンのフレーム当たりの標準パターン記憶用メモリに
対するアクセス回数は９０００Ｘ１５＝１３５０００回
となる。

これを５ｍＢｅＣ内に行なうためには、アクセスタイム
３７　ｎ５ｅｃ以下が要求される。また、標準パターン
の記憶に必要とされるメモリ量は、特徴ベクトルの１要
素を１バイトで表現するものとすれば、１ｓｓｋＢとな
り、３７　ｎ５ｅｃ以下でアクセスできる高速メモリが
、１３５ｋＢも必要ということになり、装置として大変
高価なものになる。

発明が解決しようとする問題点 本発明は、前記ＡＣＤＰ法による連続的ノ（ターンの比
較装置において、高速アクセスが要求されるメモリの数
を大幅に減少させることを目的とする。

問題点を解決するだめの手段 本発明のパターン比較装置は、入力信号を特徴ベクトル
ａ　１　、　ａ　２　ｒ・・・＋　ａ　１　ｒ・・・、
ａＩの系列に変換する特徴抽出手段と、特徴ベクトルの
系列ｂｎ１．ｂｎ２゜・・・、ｂｎ３．・・・、ｂｎ■
ｎから成る標準パターンＨｎ（ただし、ｎ＝１〜Ｎ）を
記憶する標準パターン記憶手段と、入力のフレームｉを
横軸に、標準パターンのフレームｊを縦軸とする格子グ
ラフにおいて、標準パターンＨｎ　とマツチングすると
きは、入力パターンのフレームに対してＷフレーム隔た
った直線で挾まれる領域の格子点に対して、標準パター
ンの各フレームｊの特徴ベクトルｂｎｊのそれぞれに対
してｉ軸方向に前記Ｗの幅でＤＰマツチングをｊ＝１〜
■０の順に行ない、１つの領域の計算が完了すると次の
相隣る前記と同様な領域の計算を同様に行なうというよ
うに、入力パターンの全範囲に渡って前記マツチング計
算を行なうＤＰマツチング手段を備えている。

作　　用 入力信号を特徴ベクトルａ１　、　ａ２　、・・・、ａ
、、・・・　。

ａＩの系列に変換し、特徴ベクトルの系列ｂｎ１゜ｂｎ
３．・・・、ｂｎｊ、・・・、ｂｎＩｎカラ成ル標準ハ
ターンＲｎ（ただし、ｎ＝１〜Ｎ）と、入力のフレーム
ｉを横軸に、標準パターンのフレームｊを縦軸とする格
子グラフにおいて、標準パターンＲｎとマツチングする
ときは、入力パターンのフレームに対してＷフレーム隔
たった直線で挾まれる領域の格子点に対して、標準パタ
ーンの各フレームｊの特徴ベクトルｂｎｊのそれぞれに
対してｉ軸方向に前記】 Ｗの幅でＤＰマツチングをｊ＝１〜■０の順に行ない、
１つの領域の計算が完了すると次の相隣る前記と同様な
領域の計算を同様に行なうというように、入力パターン
の全範囲に渡って前記マツチング計算を行なう。

実施例 第４図は本発明の原理を示す図である。径路の制限条件
を第３図のように選べば、８．９をｊ軸に平行で互いに
Ｗ（≦Ｉｎ／２）フレーム隔たった直線とすれば、直線
８上の途中累積距離Ｄｎ（ｉ。

））が求まっておれば、両直線で挾まれる領域（斜線部
分）の途中累積距離Ｄｎ（ｉ、ｉ）は計算することが出
来、さらに、直線８と直線ｔ、）ｎ　　との交点を１０
．直線９と直線ｊ＝Ｊ”　との交点を１１とすれば、１
０〜１１に含まれる各格子点までの終端累積距離Ｄ（ｉ
）は直線８以前の終端累積距離が求まっておれば計算出
来る。途中の計算は矢印１２に示すように横方向に順次
下から上へ計算を進めて行くことが出来る。このように
して、フレーム周期をＴとするとき、時間ＷＴの間に斜
線部Ａの計算を以上のように行ない、次のＷＴの間に斜
線部Ｂの計算を以上のように行なうと言うように、以上
に述べた計算を時間ＷＪ毎に順次進めてゆくこ・とが出
来る。

このようにすると、標準パターンの第ｊフレームは、Ｗ
フレームの入力パターンと照合する間一定で良いから、
標準パターン用メモリに対して要求されるアクセスタイ
ムを遅くすることが出来る。

即ち、各斜線部の格子点の数はＷＪであって、この各格
子点に対する計算をＴＷの間に行なう必要があるが（Ｔ
はフレームの周期とする）、このとき、標準パターンの
１フレームに対して許容される計算時間はＴＷ／ＩＮと
なり、これは、標準パターンの１フレ一ム分のデータを
読み出す時間に等しく、前記の数値を当てはめれば、Ｗ
＝Ｊ／２であるからＴ　（１／２　）／　ＴＮ−＝Ｔ／
２Ｎ　＝５ｍｓｅｃ／２Ｘ３００：８．３μｓｅｃ　で
あり、特徴ベクトルの次数を以前と同じく１６次とすれ
ば、標準パターンの１つのベクトルの要素を読み出すた
めに許されるアクセスタイムは８．３　ｐｓｅｃ　／１
５＝５５３ｎｓｅｃとなり、従来例で要求された値に比
べると約１６倍のアクセスタイムで良いことになる。但
し、今度は入力パターンを記憶するためのメモリに高速
性が要求されるが（標準パターンの第１フレームに対し
て、ＮＷ回の読み出しを時間ＴＷ／Ｊの間に行なわなけ
ればならない。前記の例に対しては、ＴＷ／Ｔ／ＮＷ＝
Ｔ／ＮＴ＝５ｍｓｅｃ／３００Ｘ３０＝０．５６１ｔｓ
ｅｃの間に１６個の特徴ベクトルを読み出す必要がある
。従って、ベクトルの１つの要素を読み出すのに許され
るアクセスタイムは３７　ｎ５ｅｃとなる。その必要と
される容量は、前記の例に対しては、平均１５Ｗ＝１５
Ｘ３０＝４５０　　バイトで良いことになり、大幅なコ
ストダウンにつながる。

以上が本発明の原理であるが、Ｗは固定とすることも可
変とすることも出来る。Ｗを固定とする場合は基本的に
は工０の最小値を■□とするとき、Ｗ≦Ｊ　、　／２　
　とするのが最も簡単であるが、工０礼！ として非常に短いものが含まれるときはあまり効果的で
ない。但し、メモリを用いれば、Ｗ＞Ｊｌｌ。

／′２の場合でも以上のような考え方により計算を行な
うことが出来る。即ち、Ｄｏ（ｉ、Ｉｎ）自体は）玉章
の入力フレームの幅で計算が可能であるが、これからＤ
ｎ（ｉ）を求めるためには、ｉ−Ｊ、７／２までの経端
累積距離が求まっている必要がある。従って、Ｗ）Ｔ、
／２としたときは、Ｄｎ（１）を計算すシラ るｉでＷ−ＩＪ２フｖ一部分のＤ”（ｔ、Ｉｎ）。

Ｂｎ（ｉ、■”）を記憶しておけば良い。また、前記欠
点を補うには、Ｊｎに応じてＷを可変とすることも可能
である。

本実施例ではＩｎに応じてＷを可変とする場合について
説明する。

第６図は本発明の詳細な説明する詳細図である。

い捷、入力パターンが第１フレームのときの処理を説明
する。前記斜線Ａ、Ｂ等のそれぞれをブロックと呼ぶこ
とにする。このとき、Ｄｎ（ｉ−ＩＪ”／２〕）が求ま
っていなければ、同図における○で示す格子点について
前記の計算を行ない、Ｄｎ（ｉ−［：Ｉｎ／２）　）、
Ｄｎ（ｉ　−（Ｉｎ／２）　＋１　）、　・、Ｄｎ（ｉ
）を求める。・はこのブロックの１つ前のブロックのｉ
＝１．２．・・・　Ｊｎにおける格子点でこれらの点に
おける途中累積距離Ｄｎ（’＋＋）は、本ブロックにお
ける途中累積距離Ｄｎ（’＋＋）の初期値となるもので
ある。Ｄｎ（ｉ−ＣＩ”／２）’）が求まっているとき
は、このｎに対応する標準・ぐターンに対する計算はス
キップすることになる。

以上のようにすれば、各標準パターンＲｎに対する前記
ブロックの幅をｎ毎にＷｎ＝（Ｉｎ／２）＋１として計
算したことになる。Ｄｎ（ｉ−（Ｉｎ／２））が求まっ
ているか否かを決定するには、最初にＤｎ（ｉ−［：Ｉ
ｎ／２）　）　ｔｏ　アルイハｃｘ：□に初期化ｔ、テ
おけば、求まっているときは、０あるいは（１）以外の
有限の値になっているはずであることから判断が可能で
ある。または、Ｄｎ（ｉ）が求まっているときはＧｎ（
ｉ）−〇、求まッテイナイときはＧｎ（ｉ）　＝　１と
設定されるフラグＧｎ（１）を設け、初期値をＧ”（ｉ
）　＝１　ｆｏｒ　　ｉ＝１〜Ｉと設定しておき、Ｄｎ
（ｉ）が求まる毎にＧ　”（ｉ）　−〇とすることにす
れば、Ｇ”（ｉ）を見ることにより、Ｄｎ（ｉ）が求ま
っているか否かが判定出来る。

第１図は、以上の原理に基づく本発明の実施例徴抽出部
であって、入力音声信号を特徴ベクトルａ、の系列Ａに
変換する。１０２は単語標準・（り一ン記憶部であって
、認識給食たるＮ個の単語がそれぞれ標準パターンＲｎ
　＝　ｂ　ｎｌ、・・・Ｂｒ）、、・・・。

ｂｎＩｎ（１≦ｎ≦Ｎ）として特徴ベクトルの形で予め
登録されている。１０３はベクトル間距離計算部であっ
て、入力パターンの第１フレームにおけル特徴ベクトル
ａｉ　とｎ番目の単語標準ノζターンＨｎの特徴ベクト
ルｂ、　　との距離ｄｎ（ｍｒ　＋　）を求め、必要が
無くなるまで記憶する。本例においては部分累積距離を
計算しているフレームの１つ前のフレームおよび当該フ
レームのベクトル間距離を当該フレームの途中累積距離
を計算するまで記憶する。ｄｎ（ｍ、））は、例えば〜
とｂｎｊの市街距離として定義できる。即ち、ベクトル
の次元をＬとし、輻＝（ａｍｌ、ａＸｎ２．・・・、ａ
ｍＬ）、ｂｎｊ＝（ｂｏ、１゜ｂｎｊ２．　・・、　、
ｂｎｊＬ）とするどき”　（ｍｒ　＋　）＝　　Σ　Ｄ
ｍｋ−ｂｎｊｋ’に＝１ となる。また、本実施例では計算の方向が１軸方向であ
って、第ｎ標準パターンＨｎの第ｊフレームのベクトル
ｂ、に対し、１−（Ｔｎ／２）≦ｍ≦ｉの範囲の入力パ
ターンに対しｄｎ（ｍ、ｊ）を求める。

１０４は途中累積距離計算部であって、前記ｃｌ”（ｍ
、ｊ）と同様の範囲で途中累積距離Ｄ”（ｍ、ｊ）。

途中バックポインタＢｎ（ｍ、ｊ）を求める。１１３は
終端累積距離計算部であって、Ｄ（ホ）、Ｂ（ホ）、Ｎ
−を前記ｄ０（ｍ＋＋）と同様の範囲で求める。第３図
ａに示したマツチング径路の拘束条件が採用されると、
Ｄｎ（ｍ、ｊ）、Ｂ”（ｍ、ｊ）は途中累積距離計算部
１０４においてつぎのように求まる。

ｊ＝１のとき Ｄｎ（ｍ、１）ｄｎ（ｍ、ｊ） Ｂ”（ｍ、１）＝ｍ ）≧３のとき ただし ｐ（ホ）、Ｂ（ホ）、Ｎに）は終端累積距離計算部１１
３において次のようにして求まる。

即ち、 ｐ＝Ｂｎ（ｍ　、　５　） ｍ’＝ｐ−ｒ＋＋＋ｐ＋ｒのｍ′についてを計算し、 なる漸化式によって Ｂに）＝ｍ″ Ｎ輛−ｎｌ として求まる。但し、ｍ”、ｎ”は式（２）を満たすｍ
′。

ｎである。

１１２は前記ベクトル間距離の計算と、累積距離の計算
の実行範囲を各ｎについて決定するものであって、Ｄ（
１−（Ｊｎ／２）　）が求まっていないとき、前記ｍの
範囲でｄ”（ｍ、ｊ）、Ｄｎ（ｍ、ｊ）の計算をそれぞ
れベクトル間距離計算部１０３．途中累積距離計算部１
０４．終端累積距離計算部１１３に指示する。

以上のようにして求められた終端累積距離Ｄ−は終端累
積距離記憶部１０５に、バンクポインタＢ（ホ）はバッ
クポインタ記憶部１０６に、最後尾単語番号Ｎに）は最
後尾単語記憶部１０７に記憶される。

なお、Ｄｎ（ｍ＋ｉ）＋Ｂｎ（ｍ、ｊ）（ただし、ｊ＝
１２　＋　”’　＋　１　”　；　ｎ＝１．２　＋　・
・・＋　Ｎ　）は必要が無くなるまで、部分累積距離計
算部１０４に一時的に記憶′される。本実施例において
は途中累積距離を計算しているフレームの１つ前および
２つ前のフレームの途中累積距離を計算するまで記憶す
る。

また、終端累積距離記憶部１０５に記憶される終端累積
距離りに）は式（１）の初期値で必要なものであり、Ｄ
に）についてはＤｎ（ｍ＋１．１　）を求めるまで記憶
しておけばよい。

１０８は音声区間検出部であって、入力信号の大きさ等
から音声区間を判定するものである。音声区間検出部１
０８が、音声入力が開始されたことを検出するとフレー
ム数計数部１０９はフレーム毎に計数を始める。前記の
処理は第ｉフレームについての処理であったが、このフ
レーム数計数部１０９の計数値が即ちとのｉを設定して
いる。

従って、前記と同様の処理が、フレームが１進む毎に行
なわれることになる。フレーム数計数部１０９は音声区
間が検出されると計数を始め、音声区間が終了するとリ
セットされる。最後尾単語記憶部１０７．パックポイン
タ記憶部１０６には、従って、Ｎ（ｉ）　、　Ｂ（ｉ）
がｉ＝１．２．・・・、■について３己憶されることに
なる。

セグメンテーンヨン部１１０はパックポインタ記憶部１
０６に対し、所定のパックポインタを読出すべき命令を
発するものである。即ち、セグメンテー／ヨン部１１０
がｉなる値をパックポインタ記憶部１０６に発すると、
パックポインタ記憶部１０６からはパックポインタＢ（
１）が読出される。

セグメンテー７．Ｊン部１１０はパックポインタ記憶部
１０６からＢ　（ｉ）なる値を受は取ると、その同じ値
をバンクポインタ記憶部１０６に発する。従っ−Ｃ１音
声区間検出部１０８が音声入力の終了を検知すると、フ
レーム数計数部１０９の最終値Ｉがセグメンテーンヨン
部１１０に供給され、セグメンテーンヨン部１１０は先
ず工なる値をバンクポインタ記憶部１０らに発する。以
後、前記説明の動作に従って、パックポインタ記憶部１
０６から、Ｂ（Ｉ）、Ｂ　（Ｂ（Ｉ）、　Ｂ　（Ｂ　（
Ｂ（Ｉ））））　、−＝、ｏ　　なる出力が頃次得られ
ることになる。これらの値は最後から２番目の単語の終
わりのフレーム、同３番目の単語の終わりのフレーム、
同４番目の単語の終わりのフレーム、・・・・・という
ものであり、Ｎ（ｉ）はｌフレームで終わる単語であっ
たから、この値をそのまま最後尾単語記憶部１０７に与
えると、最後の単語から逆の順序で認識結果が得られる
。

なお、認識結果が本来の順序で得られるようにするため
には、この順序の変換をツクツクポインタ記憶部１０６
の出力に対して行なうか最後尾単語記憶部１０７の出力
に対して行なえばよい。

以上の実施例においては、説明の便宜のために、点（ｍ
、ｊ）におけるベクトル間距離、途中累積距離、途中パ
ックポインタ等はそれぞれｄｎ（”＋　１　）　＋シ（
ｍＩＩＬ”（”＋］）等と表記したが、これらの記憶領
域はｉ、ｉ、ｎの全範囲に渡って準備する必要は無く、
第１段の格子点におけるＤｎ（”　＋　ｌ　）　＋”　
（ｍＩ　］　）の計算には、前記漸化式からも明らかな
ように、第３図の径路に対しては第ｉ−１段。

についてはｄｎ（ｍ＋］　　’）（但し、Ｉｎ　”　ｌ
　−１０２〜ｌ）についてのみ記憶していればよい。ま
た、ｎ毎にｊ＝１〜Ｊｎについてこれらの値を計算する
ことにすれば、”（ｍ＋＋）、Ｂｎ（ｌ＋＋）について
ばｎに関して一旦一つのブロックについて計算してしま
うことになるので、何時迄も記憶しておく必要はない。

この考え方に基づいて、さらに詳細な説明を第６図に従
って説明する。ソフトウェアにより実現する場合もこれ
に従えばよいのは勿論である。同図において ＮＤＤＯ なる記法はＸが満足される間Ｙを実行することをＮＤＤ
Ｏ なる記法はＸなる条件が満足されるまでＹを実行するこ
とを ＬＳＥ ＥＮＤＩＦなる記法はＸなる条件が満足されればＹを、
そうでなければ、Ｚを実行することをそれぞれ意味する
ものとする。

また、途中累積距離、途中パックポインタ、ベクトル間
距離等に関する記法を次のように変更する。即ち、第３
図に示した径路を用いるときは、第１段の途中累積距離
と途中パックポインタの計算は第ｉ−１段と第１−２段
の途中累積距離と途中パックポインタと、第ｊ−１段の
ベクトル間距離が記憶されておればよく、前記ブロック
の最初の入力パターンのフレームにおける途中累積距離
と途中パンクポインタの計算は１フレーム前と２フレー
ム前の途中累積距離と途中パックポインタ、１フレーム
前のベクトル間距離が記憶されておればよい。結局、必
要なメモリは”　（ｉｌ　］　）　。

Ｎｎ（ｉ、＋）については１＝−１〜工。＋１　の範囲
で３段分、ｄｎ（ｉ、ｉ）についてはｉ＝０〜１ｏ＋１
の範囲で２段分（但し、−１は直前のブロックの最終フ
レームの１つ前のフレーム、０は直前のブロックの最終
フレームを意味する。）、各ブロックの最終フレームの
１つ前のフレームと最終フレームニオけるＤｎ（’Ｉ］
ＬＥ３ｎ（ｌＩＩＬ各）０７りの最終フレームにおける
ｄｎ（ｉ、ｉ）がそれぞれ記憶されておれば漸化式の計
算は出来るものであり、各単語ｎ毎に１ブロック分の計
算を行なうことにすれば、１＝−１〜Ｊ０＋１の３段分
の”（’ｌ］）。

Ｂｎ（’ｌ］）は１＝−１〜Ｊ−＋１とすることによっ
てすべてのｎについて共通に用いることが出来るから、
これらをそれぞれＤ（ｉｏ、ｋ）、Ｂ（ｉｏ、ｋ）（但
し、１ｏ＝−１〜Ｉｆｎ＋１　、にｍｏ　〜２　）、ｉ
＝０〜工。＋１の２段分（７）ｄｎ（ｉ、＋）は１＝ｏ
−ＩＩｎ＋１　とすることによってすべてのｎについて
共通に用いることが出来るから、これをｄ　（ｉｏ　、
　ｋ　）　（但し、１０＝０〜７　　＋１．に＝ｏ〜２
）とし、次のブロックの初期値を記憶しておくだめのメ
モリとして、各ブロックの最終フレームの１つ前のフレ
ームと最終フレームニオけるＤｎ（１＋ｌ）＋Ｂｎ（’
＋Ｉ）、各プロｙりの最終フレームにおけるｄ”（’＋
＋）をそれぞれＤｎ（’　ｌ　］）ｌＢｎ（’　ｌ　Ｉ
Ｌｄｎ（］）（但し、ｉ＝ｏ　〜１゜ｊ＝１〜■０　で
あって、ｉ＝ｏは最終フレーム、ｉ　＝　１　ハ最ｉフ
レームの１つ前のフレーム）トスることが出来、メモリ
の大幅な節約が図れる。

第６図において、ステップ２０１．２０２は初期化を行
なう部分である。ステップ２０３は入力の第ｉフレーム
における処理を行なう部分である。

ステップ２０４は前記ブロック内の各格子点に対し、第
１〜Ｎ標準パターンと入力パターンとのマツチングを行
なう処理である。ステップ２０６は第ｎ標準パターンに
対する前記ブロックの幅を求めている。ステップ２０６
は入力の第ｉフレームにおいて、第１　　Ｔｏフレーム
〜第ｉフレームの終端累積距離り一が求まっているか否
かを前記フラグＧｎ（ホ）の状態から判断し、求まって
いないときはそのブロックの計算を行ない、求まってい
るときはｎ＝ｎ＋１の処理ヘスキップする処理である。

ステップ２ｏ了は該当する前記ブロックが未だ計算され
ていないことが判明したとき、以下のステップでそのブ
ロックの計算を行なうのであるから、前取てそこに含ま
れるフレームについてフラグＧ０（ホ）を０とおいて計
算済みの状態にしている。ステップ２０８では後の計算
の便宜のために計算すべきブロックの開始フレーム−１
をｍｏとして算出しておく。ステップ２０９はｊ＝１．
２百（ｉｏ、Ｊ）（但し、１０＝１〜工。＋１）を計算
している。ステップ２１１は入力パターンの第１フレー
ムからのフレームの通し番号を求めている。ステップ２
１２は入力パターンの第ｍ番のベクトル輻と標準パター
ンの第１番のベクトルｂｎ１とのベクトル間距離を求め
ている。ステップ２１３はこの値を基にｊ＝１について
Ｄ（ｔｏ、ｉ）＋Ｂ（’ｏ。

Ｊ）（但し、１０＝１〜■。＋１）を計算している。

ステップ２１４，２１５はｊ＝２，１ｏ＝１〜Ｔ　ｏ　
＋１におけるベクトル間距離ｄ　（ｉｏ　、　２　）を
求めている。

ステップ２１６はこの値を基にｉ＝２におけるＤ（ｉｏ
、ｉ）、百（ｉｏ、ｉ）（但し、１０＝１〜工。＋１）
を計算している。ステップ２１７は次のブロックの計算
に使うためにｄ’（２）＝ｄ（Ｊ。＋１．２）なる置き
換えを行なっている。

ステップ２１８はｊ＝３〜Ｊ０におけるＤ（１０゜ｋ）
　、Ｂ　（ｉｏ　、　ｋ　）　（但し、１０＝１〜工。

＋１）を計算している。ステップ２１９はＤ（五〇、ｋ
）、Ｂ（ｉｏ。

ｋ　）　＋　ｄ　（ｔ　ｏ　、　ｋ　）　　なるメモｌ
Ｊ’を巡回的に用いるためにｋの値ｔｉの値に応じて設
定している。ステノブ２２０は直前のブロックの値から
初期値を設定している。ステップ２２１は第３段におけ
るベクトル間距離を計算している。ステップ２２２はこ
の値を基に第】段におけるＤ（１０，Ｊ）、Ｂ（１０゜
））（但し、１゜−１〜Ｔ　ｏ　＋　１　）を旧線して
いる。ステップ２２３は次のブロックの計算に使うだめ
の置き換えを行なっている。

ステップ２２４は以上のようにして求めたから、前記説
明に従って、Ｄ（ホ）、Ｂ（ホ）、Ｎ（ホ）を計算して
おり、ｎが変わる毎に以前に計算した値と比較し、段縫
的に最小値が求められる。

ステップ２０３の処理が終了すると判定処理に入る。即
ち、ステップ２３０においてｉ　＝　Ｉとおいて前記説
明に従ってステップ２３１で求めるべき単語列が逆の順
序で求められる。

本実施例においては、第３図に示すような径路の拘束条
件を用いたため径路の最大の傾斜は２と全るので、ブロ
ックの幅は（Ｊｎ／２）＋１となったし゛が、径路の拘
束条件としては、これ以外にも種々溝えられ、例えば、
第７図のような場合は、最大の傾斜が３となるからこの
場合のブロックの幅は２−４ｌ−（Ｉｎ−１）／３］と
なる。一般に径路の最大の傾斜がｋのときは、ブロック
の幅Ｗば２−（１−、−（Ｉｎ−１）／に’ｌ以下であ
れば良いことになる（ｋ＝　２　（’）場合１ｄ、　Ｃ
Ｊｎ／２）　＋１　ト２−（１−（Ｊ”−１）／２）と
は■１　が整数の場合は等しい）。

発明の効果 以上のように、本発明によれば、ＡＣＤＰ法のように、
ＤＰマツチングを高速に連続して行なう方法においては
、高速、大容量のメモリが必要であったのが、高速性を
要求されるメモリ数を大幅に減らす事が出来、安価な装
置の実現が可能となったものである。

【図面の簡単な説明】

第１図は本発明の原理を示すブロック図、第２図はＤＰ
マツチングにより連続パターンを認識する原理を説明す
るだめの説明図、第３図は本発明が適用さるべきＡＣＤ
Ｐ法を説明するだめの説明図、第４図は本発明の原理の
考え方を説明するための説明図、第５図は本発明の詳細
な説明するだめの詳細説明図、第６図は本発明の処理手
順を詳細（で説明するための処理手順図、第７図は径路
の拘束条件の他の例を説明するための説明図である。 １０１・・・・特徴抽出部、１０２・・・・・単語標準
パターン記憶部、１０３・・・・・・ベクトル間距離計
算部、１０４・・・・・途中累積距離計算部、１０５・
・・・・・終端素晴距離記憶部、１０６・・・・・バッ
クポインタ記憶部、１０７・・・・・・最後尾単語記憶
部、１０８・・印・音声区間検出部、１０９　・・フレ
ーム数計数部、１１０・・・・・セダメンテーショ７部
、１１２・・・・・マノナング計算実行範囲決定部。 代理人の氏名　弁理士　中　尾　敏　男　はが１名第４
図 第５図 第６図　（ｆ／）す ２ＤＩ　　、Ｌ−［Ｊｌｌ、ヮ／２］ アイゴ７ ｉ　Σ 第６図　（＋０４） ア“　イ″　ゲ ２３０　　　ｉ＝Ｉ 第７図

Claims (1)

【特許請求の範囲】
1. 入力信号を特徴ベクトルａ＿１、ａ＿２、・・・、ａ＿
   ｉ、・・・、ａ＿Ｉの系列に変換する特徴抽出手段と、
   特徴ベクトルの系列ｂ＾ｎ＿１、ｂ＾ｎ＿２、・・・、
   ｂ＾ｎ＿ｊ、・・・、ｂ＾ｎ＿（Ｊ＾ｎ）から成る標準
   パターンＲ＾ｎ（ただし、ｎ＝１〜Ｎ）を記憶する標準
   パターン記憶手段と、入力のフレームｉを横軸に、標準
   パターンのフレームｊを縦軸とする格子グラフにおいて
   、標準パターンＲ＾ｎとマッチングするときは、入力パ
   ターンのフレームに対して互いにＷフレーム隔たった直
   線で挾まれる領域の格子点に対して、標準パターンの各
   フレームｊの特徴ベクトルｂ＾ｎ＿ｊのそれぞれに対し
   てｉ軸方向に前記Ｗの幅でＤＰマッチングをｊ＝１〜Ｊ
   ＾ｎの順に行ない、１つの領域の計算が完了すると次の
   相隣る前記と同様な領域の計算を同様に行なうというよ
   うに、入力パターンの全範囲に渡って前記マッチング計
   算を行なうＤＰマッチング手段とを備えたことを特徴と
   するパターン比較装置。