JPH0420197B2

JPH0420197B2 -

Info

Publication number: JPH0420197B2
Application number: JP56206351A
Authority: JP
Inventors: Kyohiro Kano
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1981-12-21
Filing date: 1981-12-21
Publication date: 1992-03-31
Also published as: JPS58106599A

Description

【発明の詳細な説明】

(1) 発明の属する分野の説明本発明は、系列パターン・マツチング処理方
法、特に例えば音声等の系列マツチングによるパ
ターン認識装置の主要構成部分であるパターン・
マツチング処理方法に関するものである。 (2) 従来技術の説明本発明による系列パターン・マツチング処理方
法で取り扱える系列は、系列データであれば、何
でもよいが、以下では、代表的な系列の例として
音声の時系列を対象とする系列パターン・マツチ
ング方法について説明する。音声は人間にとつて最も容易に使いうる情報伝
達の手段であり、音声認識装置の実用化により、
音声によるデータ入力、機械との対話、音声によ
るダイアル等、数多くの分野での応用がある。音声認識における動的計画法を利用したマツチ
ング（以下、DPマツチングと略す）は、入力音
声の時系列〓＝a₁a₂…a_oと標準パターンの特徴ベ
クトルの時系列〓＝b₁b₂…b_nとの間で時間軸の伸
縮を許して、要素間の対応づけを行い、系列間距
離を計算する際に用いられる。従来、この種の動的計画法では、系列〓、〓の
要素間の距離マトリツクス〓＝（d_ij）（d_ijはa_iとb_j
の距離）上で、第１図Ａのような窓制限１１内の
すべての格子点（ｉ，ｊ）でDPマツチングのく
り返し逐次計算を実行するためや、１つの要素を
２つ以上の要素に対応ずけるのを防ぐための制限
（傾斜制限）１２のために多大な計算量を有する
という欠点や、DPマツチングの際の第１図Ｂ図
示の如き逐次計算値ｇ（ｉ，ｊ）の記憶のためバ
ツフアメモリ１３が大となるとする欠点をもつて
いた。即ち、従来の場合の手法においては、 (1) バスの傾斜に関する制限を例えば第１図Ａ図
示の点線の如く与えた上で、当該範囲内のすべ
ての可能なバスを探すようにしている。換言す
れば、第１図Ａ図示点線内のすべての格子点で
DP計算を行うことで、精密化をはかり、 (2) しかし、一方では、後述するように、斜めの
バスに対しては、縦や横のバスにくらべて大き
い重みをつける必要がある。換言すればバスの
比較に当つて公平が保たれていないという問題
をはらんでいる。 (3) 本発明の目的本発明は、上記の欠点を大幅に除去するもので
あり、DPマツチングの逐次計算のくり返し計算
を３点ごとの格子点のみで行うために、計算のく
り返し回数が1/3に、かつ、傾斜制限のための１
回分の逐次計算の計算量も1/2以下にすることが
でき、かつ、ｇ（ｉ，ｊ）の記憶のためのバツフ
アメモリも窓制限幅の２倍だけしか必要としない
という特徴を有している。よつて、従来からの
DPマツチング（例えば昭和55年10月日本音響
学会秋期発表会講演論文集１−１−10に示すDP
マツチング）と比較して、計算量で1/6以下にす
ることが可能となる。即ち、間引いたバス計算を
行うという意味で簡略化をはかりながら、バスの
比較において従来の場合よりもより厳密に（同等
性を与えて）比較を行うようにすることとなる。 (4) 発明の構成および作用の説明第２図は、本発明の一実施例であつて、１は入
力音声、２は特徴パラメータの抽出部、３は入力
音声の特徴パタメータ時系列〓＝a₁a₂…a_o、４は
あらかじめ蓄えられている標準パターンの特徴パ
ラメータの時系列〓＝b₁b₂…b_n、５は入力音声の
時系列〓＝a₁a₂…a_oと標準パターンの特徴パラメ
ータの時系列〓＝b₁b₂…b_nとの間の距離マトリツ
クス〓＝（d_ij）を計算する距離計算部、６は距離
マトリツクス、７は本発明によるDPマツチング
部、８はマツチングスコア、９は最小のスコアの
単語を決定する単語決定部、１０は単語名であ
る。動的計画法は、第１図図示のような距離マトリ
ツクス〓＝（d_ij）上で、始端（１，１）から終端
（ｎ，ｍ）まで格子点（ｉ，ｊ）の上をたどつて、
そのときの距離d_ijの和が最小になるときのスコア
を求めるものであり、例えば次の式のように表わ
される。

【表】 (1)
｛ただし、｛（ｉ，ｊ）｝は（i₁，j₁）（i₂，j₂）…
（ｎ，ｍ）の系列を表わし、｜i_k+1−i_k｜＋｜j_k+1−j_k｜＝１ (2) であり、最小値を与えるパスを最適パスと呼ぶ。｝これは連続系で表わすと、距離関数ｄ（ｘ，ｙ）
上で、（０，０）の点から（ｎ，ｍ）の点までの
もつとも小さい積分値を求める問題の近似解であ
る。

【表】｛ただし、ｃは（０，０）から（ｎ，ｍ）への単
調増加な積分路。｝距離マトリツクス上での最適パスには、通常次
の制約、がつけられている。 () パスのたどり方通常、パス（１，１）（i₁，j₁）（i₂，j₂）…
（ｎ，ｍ）は(2)式のように、市街化距離が１に
なるようなパスが選ばれるか、あるいは、 max｛｜i_k+1−i_k｜，｜j_k+1−j_k｜｝＝１ (4) になるようなパスが選ばれている。よつて、格
子点上で進むパスは、第３図図示矢印のような
パス14である。縦、横の長さのパスを「１」と
すると、斜めのパスは長さが「２」とされてい
る。実際の斜めの長さは、縦あるいは横の長さ
を「１」とすると√２であり、(3)式の連続系と
は、大幅な違いをもつことになつてしまう。 () 傾斜制限極端にかたよつたマツチングを阻止するため
に、第４図のような傾斜制限をもつたパス15が
用いられる。この傾斜制限パスは、認識性能の
向上には寄与しているが、計算量を増大させて
いる。本発明は、DPマツチングの（）の縦・横の
パスの長さと斜めのパスの長さの違いの矛盾を軽
減し、（）の傾斜制限を、計算量を増大させる
ことなく実現する手段に関してである。以下、詳
しく説明する。傾斜制限を距離マトリツクス上で、自然に実現
するために、第５図のような例えば３点おきにず
らした格子点１６を考える。すると第６図のよう
に、ずらした格子点間をひし形のパスで結ぶこと
ができ、すべてのパスの長さが等しくなる。よつ
て、（）のパスの長さの矛盾が緩和される。ま
た、（）のパスの傾斜制限も第６図のように自
然に導入できる。しかも、DPマツチングのくり
返し逐次計算は、３点おきに行えばよく、従来か
らのものに比べて1/3の段数になる。さらに、逐
次計算値ｇ（ｉ，ｊ）を格納するバツフアメモリ
１３も少なくてすむ。つまり、DPマツチングの
くり返し逐次計算を第７図のように、ｉ＋ｊ＝3l
＋２を満す格子点（ｉ，ｊ）上で、ｌ＝０、１、
２、…の順序で行うとき、各段の格子点の数
（ｒ）の２倍の第７図のようなバツフアメモリｇ
（−ｒ）〜ｇ（ｒ）を用意すれば十分である。以下、各格子点（ｉ，ｊ）でのくり返し逐次計
算を示す。ただし、格子点（ｉ，ｊ）に対応する
逐次計算値のバツフアメモリをｇ（ｐ）とする。（方法）ｇ（ｐ）＝min｛ｇ（ｐ−１），ｇ（ｐ＋１）｝＋d_ij(5) これは、第６図のパスを終端の点（ｉ，ｊ）の
d_ijで代用していることになる。(3)式の積分値によ
り近づけるためには、パスの近くの他の点の距離
の値も用いることにして、次の方法、方法が
考えられる。

【表】 (5)〜(6)式で、ｐの値は、ｐ＝ｊ−ｉで決定され
る。方法の計算式は第１図図示のDPマツチン
グの式に比べて、１段当りの計算式の計算量は1/
４以下であり、DPマツチング全体では1/12以下と
なる。方法、は、第１図図示のDPマツチン
グの式に比べて、１段当りの計算量は1/2以下で
あり、全体では1/6以下になつている。以上述べた方法〜方法のDPマツチングの
有効性を調べるために、従来からの第１図のDP
マツチング（従来の方法と呼ぶ）との処理時間お
よび認識性能の比較を行つた。認識対象は、男性
４名が２回ずつ発声した641都市名単語音声デー
タである。単語認識の方法としては昭和55年10月
日本音響学会秋期発表会講演論文集１−１−17
に示すSPLiT法を用いた。SPLiT法では、計算
量のほとんどがDPマツチング部についやされて
いる。まず、処理時間の比較を行う。従来の方法で
641単語×64単語の認識実験をミニコンP.E.3240
で行つた場合、約８時間かかつた。同じ条件で方
法は、約60分、方法、は約70分であつた。
SPLiT法の計算量が全体で1/8近くになつている
ことがわかる。次に、方法、方法の認識性能の評価を４人
の発声者の音声データを用いて行つた。従来の方
法では、４人の平均で96.3％の認識率が得られて
いる。方法では、94.7％、方法では、95.6％
の認識率が得られた。方法は、方法とほぼ同
じ性能である。認識性能で従来の方法より、若干
下まわるものの、かなり高い認識率が得られるこ
とが確かめられた。以上の説明では、要素間の距離をもとにDPマ
ツチングの手法を述べてきたが、要素間の類似度
に対しても同様に定式化できる。また、本発明では、DPマツチングのくり返し
逐次計算を３点おき、つまりｉ＋ｊ＝3l＋２の上
の点（ｉ，ｊ）のみで行うことを述べたが、Ｑ点
おき、つまり、ｉ＋ｊ＝Ｑ・ｌ＋２（ただし、Ｑ
＝５、７、９、…）の上の点（ｉ，ｊ）のみで行
うことにしても、さらに計算量が少なく、しか
も、傾斜制限の強いくり返し逐次計算を行なうこ
とができる。 (5) 効果の説明以上述べたように、本発明によれば、従来の
DPマツチングの計算量に比らべ、1/6〜1/12以下
の計算量で、処理の厳密性を保ちつつ、DPマツ
チングを実行することができ、かつ、比較的高い
認識性能も達成することができる。また、DPマ
ツチングによる単語音声認識装置の簡易化が可能
である。更に、その他の分野での系列の非線形伸
縮マツチングにも本発明を用いることができるこ
とは言うまでもない。

【図面の簡単な説明】

第１図は、従来からのDPマツチングの例と距
離マトリツクスを示したもので、第２図は単語音
声認識システムの一実施例、第３図はDPマツチ
ングにおける縦、横、斜めのパスを表わす説明
図、第４図は代表的な傾斜制限パスを表わす説明
図、第５図は、本発明で考える３点おきにずらし
た距離マトリツクス上の格子点を表わす説明図、
第６図は本発明で考える長さが等しく、かつ、傾
斜制限のつけられたDPマツチングのパスを表わ
す説明図、第７図は本発明でのDPマツチングの
逐次計算値を蓄えるバツフアメモリについて説明
する説明図を示す。図中、２は特徴パラメータ抽出部、４は標準パ
ターン、５は距離計算部、７はDPマツチング部、
９は単語決定部、１３はバツフア・メモリ（又は
バツフアメモリ格納範囲）、１７はパスを表わす。

Claims

【特許請求の範囲】１２個の特徴パラメータの系列〓＝a₁，a₂，
…，a_oと〓＝b₁，b₂，…，b_nとの系列間の距離を
動的計画法を用いた非線形正規化マツチングで求
める系列パターン・マツチング処理方法におい
て、系列の要素間の距離マトリクス〓＝（d_ij）（但
し、ｉは系列〓のｉ番目の要素a_iを意味し、ｊは
系列〓のｊ番目の要素b_jを意味し、d_ijは要素a_iと
要素b_jとの距離を表わす）上のｉ＋ｊ＝Ｑ・ｌ＋
ｃ（但しＱは３、ｃは正の整定数）に該当する点
を抽出するとともに、該抽出された点について距
離計算を行い、座標（ｉ、ｊ）について、ｊ−ｉ＝ｐ座標（ｉ−１、ｊ−２）について、（ｊ−２）−
（ｉ−１）＝ｊ−ｉ−１＝ｐ−１座標（ｉ−２、ｊ−１）について、（ｊ−１）−
（ｉ−２）＝ｊ−ｉ＋１＝ｐ＋１とおき、該距離計算にあたつては動的計画法の繰り返し
逐次演算の漸化式の値ｇ（ｐ）として、ｉ＋ｊ＝
Ｑ・（ｌ−１）＋ｃを満足する座標（ｉ−１、ｊ−
２）上のg′（ｐ−１）およびｉ＋ｊ＝Ｑ・（ｌ−
１）＋ｃを満足する座標（ｉ−２、ｊ−１）上の
ｇ（ｐ＋１）を用いて、ｇ（ｐ）＝min｛ｇ（ｐ−１）、ｇ（ｐ＋１）｝＋d_ij の繰り返し逐次演算を、ｌ＝０、１、２、…の順
序で逐次行なうことにより、系列間距離Ｓ（〓：
〓）を計算することを特徴とする系列パターン・
マツチング処理方法。２２個の特徴パラメータの系列〓＝a₁，a₂，
…，a_oと〓＝b₁，b₂，…，b_nとの系列間の距離を
動的計画法を用いた非線形正規化マツチングで求
める系列パターン・マツチング処理方法にあたつ
ては、系列の要素間の距離マトリクス〓＝（d_ij）
（但し、ｉは系列〓のｉ番目の要素a_iを意味し、
ｊは系列〓のｊ番目の要素b_jを意味し、d_ijは要素
a_iと要素b_jとの距離を表わす）上のｉ＋ｊ＝Ｑ・
ｌ＋ｃ（但しＱは３、ｃは正の整定数）に該当す
る点を抽出するとともに、該抽出された点につい
て距離計算を行い、座標（ｉ、ｊ）について、ｊ−ｉ＝ｐ座標（ｉ−１、ｊ−２）について、（ｊ−２）−
（ｉ−１）＝ｊ−ｉ−１＝ｐ−１座標（ｉ−２、ｊ−１）について、（ｊ−１）−
（ｉ−２）＝ｊ−ｉ＋１＝ｐ＋１とおき、該距離計算にあたつては動的計画法の繰り返し
逐次演算の漸化式の値ｇ（ｐ）として、ｉ＋ｊ＝
Ｑ・（ｌ−１）＋ｃを満足する座標（ｉ−１、ｊ−
２）上のｇ（ｐ−１）およびｉ＋ｊ＝Ｑ・（ｌ−
１）＋ｃを満足する座標（ｉ−２、ｊ−１）上の
ｇ（ｐ＋１）を用いて、ｇ（ｐ）＝min｛ｇ（ｐ−１）＋d_i,j-1，ｇ（ｐ＋１）｝＋d_i-1,j｝＋d_i-1,j-1 の繰り返し逐次演算を、ｌ＝０、１、２、…の順
序で逐次行なうことにより、系列間距離Ｓ（〓：
〓）を計算することを特徴とする系列パターン・
マツチング処理方法。３２個の特徴パラメータの系列〓＝a₁，a₂，
…，a_oと〓＝b₁，b₂，…，b_nとの系列間の距離を
動的計画法を用いた非線形正規化マツチングで求
める系列パターン・マツチング処理方法において
は、系列の要素間の距離マトリクス〓＝（d_ij）（但
し、ｉは系列〓のｉ番目の要素a_iを意味し、ｊは
系列〓のｊ番目の要素b_jを意味し、d_ijは要素a_iと
要素b_jとの距離を表わす）上のｉ＋ｊ＝Ｑ・ｌ＋
ｃ（但しＱは３、ｃは正の整定数）に該当する点
を抽出するとともに、該抽出された点について距
離計算を行い、座標（ｉ、ｊ）について、ｊ−ｉ＝ｐ座標（ｉ−１、ｊ−２）について、（ｊ−２）−
（ｉ−１）＝ｊ−ｉ−１＝ｐ−１座標（ｉ−２、ｊ−１）について、（ｊ−１）−
（ｉ−２）＝ｊ−ｉ＋１＝ｐ＋１とおき、該距離計算にあたつては動的計画法の繰り返し
逐次演算の漸化式の値ｇ（ｐ）として、ｉ＋ｊ＝
Ｑ・（ｌ−１）＋ｃを満足する座標（ｉ−１、ｊ−
２）上のｇ（ｐ−１）およびｉ＋ｊ＝Ｑ・（ｌ−
１）＋ｃを満足する座標（ｉ−２、ｊ−１）上の
ｇ（ｐ＋１）を用いて、ｇ（ｐ）＝min｛ｇ（ｐ−１）＋d_i,j-1，ｇ（ｐ＋１）｝＋d_i-1,j｝＋d_ij の繰り返し逐次演算を、ｌ＝０、１、２、…の順
序で逐次行なうことにより、系列間距離Ｓ（〓：
〓）を計算することを特徴とする系列パターン・
マツチング処理方法。