JPH0466039B2 - - Google Patents
Info
- Publication number
- JPH0466039B2 JPH0466039B2 JP58201385A JP20138583A JPH0466039B2 JP H0466039 B2 JPH0466039 B2 JP H0466039B2 JP 58201385 A JP58201385 A JP 58201385A JP 20138583 A JP20138583 A JP 20138583A JP H0466039 B2 JPH0466039 B2 JP H0466039B2
- Authority
- JP
- Japan
- Prior art keywords
- pattern
- input pattern
- input
- standard
- time
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
- 230000015654 memory Effects 0.000 claims abstract description 32
- 239000013598 vector Substances 0.000 claims abstract description 23
- 230000006870 function Effects 0.000 claims description 4
- 238000004364 calculation method Methods 0.000 description 74
- 238000000034 method Methods 0.000 description 9
- 238000010586 diagram Methods 0.000 description 5
- 230000004044 response Effects 0.000 description 5
- 238000010606 normalization Methods 0.000 description 2
- 230000008602 contraction Effects 0.000 description 1
- 239000000463 material Substances 0.000 description 1
Classifications
-
- G—PHYSICS
- G10—MUSICAL INSTRUMENTS; ACOUSTICS
- G10L—SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING
- G10L15/00—Speech recognition
- G10L15/08—Speech classification or search
- G10L15/12—Speech classification or search using dynamic programming techniques, e.g. dynamic time warping [DTW]
-
- G—PHYSICS
- G10—MUSICAL INSTRUMENTS; ACOUSTICS
- G10L—SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING
- G10L15/00—Speech recognition
Landscapes
- Engineering & Computer Science (AREA)
- Computational Linguistics (AREA)
- Health & Medical Sciences (AREA)
- Audiology, Speech & Language Pathology (AREA)
- Human Computer Interaction (AREA)
- Physics & Mathematics (AREA)
- Acoustics & Sound (AREA)
- Multimedia (AREA)
- Image Analysis (AREA)
Description
【発明の詳細な説明】
本発明は音声のごとく特徴ベクトルの時系列と
して表現される２個のパタンを比較しその相異性
を評価する尺度（以下相異度という）を計算する
装置の改良に関する。
して表現される２個のパタンを比較しその相異性
を評価する尺度（以下相異度という）を計算する
装置の改良に関する。
音声認識の手段としては従来から種々の方法が
試みられている。それらの中で比較的簡単でかつ
有効な方法として非線形な伸縮を正規化してパタ
ンマツチングを行う方法が提案されている。音声
パタンには発声速度の変動による非線形で複雑な
変動があり、このため、入力パタンと標準パタン
をマツチングさせる時に時間軸の変動を考慮する
必要がある。第１図に示すように一方のパタンの
時間軸を歪ませて他方のパタンに最小近似させる
時間軸の対応関係（以下時間正規化関数）を求
め、時間軸の変動を正規化した相異度を得る方法
が、日本音響学会誌Vol27、No.９ 1971、P483〜
487に記載されている。この原理は大略以下のよ
うである。（以下横形アルゴリズムという） 入力パタンＡ、ｎ番目の標準パタンBnを特徴
ベクトルの時系列として表現し、（以下１特徴ベ
クトルを１フレームという） Ａ＝〓1、〓2………、〓i………〓I ……(1) Bo＝〓n 1、〓n 2、………〓n j、……、〓n jo
……(2) 標準パタンの時間軸ｊに入力パタンの時間軸ｉ
を写像する関数（時間正規化関数）をｊ＝ｊ(i)と
した時、時間軸の変動を正規化した正規化相異度
Ｄ（Ａ、Bn）は、 Ｄ（Ａ、Bn）＝min j=j(i)〔l 〓i=1 ｄ（ｉ、ｊ）〕 ……(3) ただしｄ（ｉ、ｊ）＝‖〓i−〓n j‖ ……(4) なる最小化問題の解として得られる。この最小化
問題は例えば第２図と第５図のフローチヤートに
示すように 初期条件go（０、０）＝０ ……(5) とし 漸化式 gn（ｉ、ｊ）＝ｄ（ｉ、ｄ）＋mingo（ｉ−
１、ｊ） go（ｉ−１、ｊ−１） go（ｉ−１、ｊ−２） ……(6) のｊを固定しｉ＝ｊ−ｒよりｊ＋ｒまで計算（横
１行の計算；第５図のブロツク１，２の計算）
し、横１行の計算をｊ＝１よりＪまでｊ軸方向へ
進め、（第５図のブロツク３の計算）、go（Ｉ、Ｊ）
を求める。このgo（Ｉ、Ｊ）が正規化相異度Ｄ
（Ａ、Bn）となる。
試みられている。それらの中で比較的簡単でかつ
有効な方法として非線形な伸縮を正規化してパタ
ンマツチングを行う方法が提案されている。音声
パタンには発声速度の変動による非線形で複雑な
変動があり、このため、入力パタンと標準パタン
をマツチングさせる時に時間軸の変動を考慮する
必要がある。第１図に示すように一方のパタンの
時間軸を歪ませて他方のパタンに最小近似させる
時間軸の対応関係（以下時間正規化関数）を求
め、時間軸の変動を正規化した相異度を得る方法
が、日本音響学会誌Vol27、No.９ 1971、P483〜
487に記載されている。この原理は大略以下のよ
うである。（以下横形アルゴリズムという） 入力パタンＡ、ｎ番目の標準パタンBnを特徴
ベクトルの時系列として表現し、（以下１特徴ベ
クトルを１フレームという） Ａ＝〓1、〓2………、〓i………〓I ……(1) Bo＝〓n 1、〓n 2、………〓n j、……、〓n jo
……(2) 標準パタンの時間軸ｊに入力パタンの時間軸ｉ
を写像する関数（時間正規化関数）をｊ＝ｊ(i)と
した時、時間軸の変動を正規化した正規化相異度
Ｄ（Ａ、Bn）は、 Ｄ（Ａ、Bn）＝min j=j(i)〔l 〓i=1 ｄ（ｉ、ｊ）〕 ……(3) ただしｄ（ｉ、ｊ）＝‖〓i−〓n j‖ ……(4) なる最小化問題の解として得られる。この最小化
問題は例えば第２図と第５図のフローチヤートに
示すように 初期条件go（０、０）＝０ ……(5) とし 漸化式 gn（ｉ、ｊ）＝ｄ（ｉ、ｄ）＋mingo（ｉ−
１、ｊ） go（ｉ−１、ｊ−１） go（ｉ−１、ｊ−２） ……(6) のｊを固定しｉ＝ｊ−ｒよりｊ＋ｒまで計算（横
１行の計算；第５図のブロツク１，２の計算）
し、横１行の計算をｊ＝１よりＪまでｊ軸方向へ
進め、（第５図のブロツク３の計算）、go（Ｉ、Ｊ）
を求める。このgo（Ｉ、Ｊ）が正規化相異度Ｄ
（Ａ、Bn）となる。
前記横形アルゴリズムのｊ行目の横１行の計算
には、入力パターンのｉ−ｒフレームよりｉ＋ｒ
フレームまでと標準パタンｊフレームが必要であ
り、次のｊ＋１行目の横１行の計算では入力パタ
ンのｉ−ｒ＋１フレームよりｉ＋ｒ＋１フレーム
までと標準パタンｊ＋１フレームが必要である
が、前のｊ行目の横１行の計算で使用したフレー
ムに対して入力パタンｉ−ｒフレームを捨て、入
力パタンｉ＋ｒ＋１フレームと標準パタンｊ＋１
フレームを追加すればｊ＋１行目の横１行の計算
が実行できる。すなわち、横形アルゴリズムを実
行するパタンマツチング装置は、入力パタン2r＋
１フレームと標準パタン１フレームのパタンバツ
フアを持ち、横１行の計算について入力パタン１
フレームと標準パタン１フレームを読み込み、(4)
式の距離計算と(6)式の漸化式計算を行う。
には、入力パターンのｉ−ｒフレームよりｉ＋ｒ
フレームまでと標準パタンｊフレームが必要であ
り、次のｊ＋１行目の横１行の計算では入力パタ
ンのｉ−ｒ＋１フレームよりｉ＋ｒ＋１フレーム
までと標準パタンｊ＋１フレームが必要である
が、前のｊ行目の横１行の計算で使用したフレー
ムに対して入力パタンｉ−ｒフレームを捨て、入
力パタンｉ＋ｒ＋１フレームと標準パタンｊ＋１
フレームを追加すればｊ＋１行目の横１行の計算
が実行できる。すなわち、横形アルゴリズムを実
行するパタンマツチング装置は、入力パタン2r＋
１フレームと標準パタン１フレームのパタンバツ
フアを持ち、横１行の計算について入力パタン１
フレームと標準パタン１フレームを読み込み、(4)
式の距離計算と(6)式の漸化式計算を行う。
さらにＮ個の標準パタンとの正規化相異度を求
める場合に第ｊ行目の横１行の計算を各標準パタ
ンごとに行うと、次の第ｊ＋１行目の横１行の計
算の時各標準パタンごとに、前の第ｊ行目で得ら
れたgo（ｉ、ｊ）を使用するためＮ個の標準パタ
ンのgo（ｉ、ｊ）の一時記憶が必要となる。この
ため各標準パタンごとに横１行の計算を１よりｊ
まで行う。この場合には、相異度go（ｉ、ｊ）は
ｊ行、ｊ−１行、ｊ−２行の３行分のメモリに順
次記憶することができ、相違度go（ｉ、ｊ）用メ
モリは少なくてよい。しかし、１つの標準パタン
との正規化相違度を求める操作をＮ回繰返すこと
になるため、入力パタンの最終フレームが得られ
た後計算を開始することになる。
める場合に第ｊ行目の横１行の計算を各標準パタ
ンごとに行うと、次の第ｊ＋１行目の横１行の計
算の時各標準パタンごとに、前の第ｊ行目で得ら
れたgo（ｉ、ｊ）を使用するためＮ個の標準パタ
ンのgo（ｉ、ｊ）の一時記憶が必要となる。この
ため各標準パタンごとに横１行の計算を１よりｊ
まで行う。この場合には、相異度go（ｉ、ｊ）は
ｊ行、ｊ−１行、ｊ−２行の３行分のメモリに順
次記憶することができ、相違度go（ｉ、ｊ）用メ
モリは少なくてよい。しかし、１つの標準パタン
との正規化相違度を求める操作をＮ回繰返すこと
になるため、入力パタンの最終フレームが得られ
た後計算を開始することになる。
以上述べたように、横形アルゴリズムを実行す
るパタンマツチング装置ではパタンデータの転送
量は少ないが、特徴ベクトル2r＋２フレーム分の
大容量のバツフアメモリが必要であり、さらに入
力パタンの最終フレームが得られるまで計算を開
始することができないため、応答時間が遅くなる
という欠点があつた。
るパタンマツチング装置ではパタンデータの転送
量は少ないが、特徴ベクトル2r＋２フレーム分の
大容量のバツフアメモリが必要であり、さらに入
力パタンの最終フレームが得られるまで計算を開
始することができないため、応答時間が遅くなる
という欠点があつた。
一方、(6)式の漸化式を計算する順序をｉとｊ入
れ換えた方法（以下縦形アルゴリズムという）
が、日本音響学会音声研究会資料S81−65（1981
−12）P517〜P524に記載されている。
れ換えた方法（以下縦形アルゴリズムという）
が、日本音響学会音声研究会資料S81−65（1981
−12）P517〜P524に記載されている。
この方法では、第３図と第６図のフローチヤー
トに示すように(6)式の漸化式をｉを固定しｊ＝ｉ
−ｒよりｉ＋ｒまで計算（縦形１列の計算、第６
図のブロツク１１，１２の計算）し、この縦１列
の計算をｉ＝１よりＩまでｉ軸方向へ進め、（第
６図のブロツク１３の計算）、ｇ（Ｉ、Ｊ）すなわ
ち正規化相異度Ｄ（Ａ、Bnを求めている。前記縦
形アルゴリズムの縦１列の計算は入力パタンの時
間軸ｉ方向へ進められるため、入力パタンの各フ
レームの入力と同期して計算を進めることがで
き、応答時間を小さくすることができる。
トに示すように(6)式の漸化式をｉを固定しｊ＝ｉ
−ｒよりｉ＋ｒまで計算（縦形１列の計算、第６
図のブロツク１１，１２の計算）し、この縦１列
の計算をｉ＝１よりＩまでｉ軸方向へ進め、（第
６図のブロツク１３の計算）、ｇ（Ｉ、Ｊ）すなわ
ち正規化相異度Ｄ（Ａ、Bnを求めている。前記縦
形アルゴリズムの縦１列の計算は入力パタンの時
間軸ｉ方向へ進められるため、入力パタンの各フ
レームの入力と同期して計算を進めることがで
き、応答時間を小さくすることができる。
しかし、Ｎ個の標準パタンとの相異度を入力パ
タンの入力と同期して計算する場合には第ｉ列の
縦１列の計算をＮ個の標準パタンについて行い、
その結果を相異度go（ｉ、ｊ）を各標準パタンに
ついて一時記憶し、次の第ｉ＋１列の縦１列の計
算に使用する。このためＮ個の標準パタンそれぞ
れについてgo（ｉ、ｊ）の縦１列分のメモリが必
要となる。一方、第ｉ列の縦１列の計算では標準
パタンが順次入れ代わるため標準パタンバツフア
は１フレーム分でよい。
タンの入力と同期して計算する場合には第ｉ列の
縦１列の計算をＮ個の標準パタンについて行い、
その結果を相異度go（ｉ、ｊ）を各標準パタンに
ついて一時記憶し、次の第ｉ＋１列の縦１列の計
算に使用する。このためＮ個の標準パタンそれぞ
れについてgo（ｉ、ｊ）の縦１列分のメモリが必
要となる。一方、第ｉ列の縦１列の計算では標準
パタンが順次入れ代わるため標準パタンバツフア
は１フレーム分でよい。
以上述べたように、縦形アルゴリズムを実行す
るパタンマツチング装置では、入力パタンの各フ
レームの入力と同期して計算を進めることがで
き、入力パタンの最終フレームの入力後すぐ計算
結果を得ることができる。さらに、距離計算に必
要なパタンバツフアメモリは入力パタン１フレー
ムと標準パタン１フレームの少容量でよい。しか
し、入力パタンの各フレームでＮ個の標準パタン
の転送が必要となり、横形アルゴリズムと比較し
て転送量はＩ倍となる欠点があつた。
るパタンマツチング装置では、入力パタンの各フ
レームの入力と同期して計算を進めることがで
き、入力パタンの最終フレームの入力後すぐ計算
結果を得ることができる。さらに、距離計算に必
要なパタンバツフアメモリは入力パタン１フレー
ムと標準パタン１フレームの少容量でよい。しか
し、入力パタンの各フレームでＮ個の標準パタン
の転送が必要となり、横形アルゴリズムと比較し
て転送量はＩ倍となる欠点があつた。
本発明の目的は、入力パタンの入力と同期して
計算を進め入力パタン数フレームをまとめて計算
することにより、パタンデータの転送量が少なく
パタンバツフアメモリが少なく応答速度の速いパ
タンマツチング装置を提供することにある。
計算を進め入力パタン数フレームをまとめて計算
することにより、パタンデータの転送量が少なく
パタンバツフアメモリが少なく応答速度の速いパ
タンマツチング装置を提供することにある。
本発明によるパタンマツチング装置は、入力パ
タンの時間点ｉをＬ個づつまとめてブロツク化し
前記ブロツク番号iiを１よりＩ／Ｌまで変化さ
せ、各iiに関して標準パタンの時間点を示す信号
ｊをマツチングを行う領域の下限Ｌ（ii）より上
限Ｕ（ii）まで変化させ、さらに各ｊについて入
力パタンの１ブロツク内の時間点を示す信号ｌを
１よりＬまで変化させて与えるパタンマツチング
制御部と、前記制御部の信号ｌによつて番地指定
される入力パタンバツフア部と、標準パタンの時
刻ｊのベクトル〓n jを一時記憶する標準パタンバ
ツフア部とを有し、前記入力パタンバツフア部と
標準パタンバツフア部より入力パタン〓iと標準
パタン〓n jを読み出しベクトル距離ｄ（〓i、〓n j）
を求める距離計算部と、 前記制御部の信号ｊとｎによつて番地指定され
る相異度メモリ部Go(j)を有し、入力パタンの時
間点のブロツク番号iiに関し、時間点（ii−１）・
Ｌにおける相異度Go(j)を接続条件として前記距
離ｄ（〓i、〓n j）を参照して動的計画の漸化式を
各標準パタンの時間点ｊと入力パタンの１ブロツ
ク内の各時間点ｌについて計算し、入力パタンの
時間点ii・Ｌにおける相異度Go(j)を求める漸化式
計算部とを有している。
タンの時間点ｉをＬ個づつまとめてブロツク化し
前記ブロツク番号iiを１よりＩ／Ｌまで変化さ
せ、各iiに関して標準パタンの時間点を示す信号
ｊをマツチングを行う領域の下限Ｌ（ii）より上
限Ｕ（ii）まで変化させ、さらに各ｊについて入
力パタンの１ブロツク内の時間点を示す信号ｌを
１よりＬまで変化させて与えるパタンマツチング
制御部と、前記制御部の信号ｌによつて番地指定
される入力パタンバツフア部と、標準パタンの時
刻ｊのベクトル〓n jを一時記憶する標準パタンバ
ツフア部とを有し、前記入力パタンバツフア部と
標準パタンバツフア部より入力パタン〓iと標準
パタン〓n jを読み出しベクトル距離ｄ（〓i、〓n j）
を求める距離計算部と、 前記制御部の信号ｊとｎによつて番地指定され
る相異度メモリ部Go(j)を有し、入力パタンの時
間点のブロツク番号iiに関し、時間点（ii−１）・
Ｌにおける相異度Go(j)を接続条件として前記距
離ｄ（〓i、〓n j）を参照して動的計画の漸化式を
各標準パタンの時間点ｊと入力パタンの１ブロツ
ク内の各時間点ｌについて計算し、入力パタンの
時間点ii・Ｌにおける相異度Go(j)を求める漸化式
計算部とを有している。
次に本発明の原理について説明する。本発明に
よる方法では(3)式の最小化問題を解く(6)式の漸化
式の計算順序が従来の横形アルゴリズムと縦形ア
ルゴリズムと異なつている。すなわち、本発明に
よる方法では、第４図と第７図のフローチヤート
に示すように入力パタンの時間軸ｉをＬ個づつま
とめてブロツク化し、各ブロツクiiではｊを固定
しｉ＝（ii−１）・Ｌ＋１よりii・Ｌまで計算（横
１行の計算；第７図のブロツクＰ２２，２３の計
算）し、この横１行の計算をｊ＝（ii−１）・Ｌ＋
１−ｒよりii・Ｌ＋ｒまで計算（縦Ｌ列の計算：
第７図のブロツク２１，２２，２３，２４の計
算）し、この縦Ｌ列の計算をii＝１よりＩ／Ｌま
でｉ軸方向へ進め（第７図のブロツク２５の計
算）、go（Ｉ、Ｊ）すなわち正規化相異度Ｄ（Ａ，
Bn）を求めている。
よる方法では(3)式の最小化問題を解く(6)式の漸化
式の計算順序が従来の横形アルゴリズムと縦形ア
ルゴリズムと異なつている。すなわち、本発明に
よる方法では、第４図と第７図のフローチヤート
に示すように入力パタンの時間軸ｉをＬ個づつま
とめてブロツク化し、各ブロツクiiではｊを固定
しｉ＝（ii−１）・Ｌ＋１よりii・Ｌまで計算（横
１行の計算；第７図のブロツクＰ２２，２３の計
算）し、この横１行の計算をｊ＝（ii−１）・Ｌ＋
１−ｒよりii・Ｌ＋ｒまで計算（縦Ｌ列の計算：
第７図のブロツク２１，２２，２３，２４の計
算）し、この縦Ｌ列の計算をii＝１よりＩ／Ｌま
でｉ軸方向へ進め（第７図のブロツク２５の計
算）、go（Ｉ、Ｊ）すなわち正規化相異度Ｄ（Ａ，
Bn）を求めている。
本発明の方法によれば、縦Ｌ列の計算はＩ／Ｌ
回行えばよいため、Ｎ個の標準パタンの転送が
Ｉ／Ｌ回となり、縦形アルゴリズムに比較して転
送量が１／Ｌへ減少する。さらに縦Ｌ列の計算を
ｉ軸方向へ進めているため、相異度の計算が入力
パタンの入力と同期して実行でき入力パタンの最
終フレームの入力後すぐに計算結果が得られ応答
速度が速くなる。また、横１行の計算は１ブロツ
ク分であるため、横１行の計算に必要なパタンバ
ツフアは入力パタンＬフレーム分と標準パタン１
フレーム分であり、横形アルゴリズムに比較して
Ｌ＋１／2r＋２へ減少する。
回行えばよいため、Ｎ個の標準パタンの転送が
Ｉ／Ｌ回となり、縦形アルゴリズムに比較して転
送量が１／Ｌへ減少する。さらに縦Ｌ列の計算を
ｉ軸方向へ進めているため、相異度の計算が入力
パタンの入力と同期して実行でき入力パタンの最
終フレームの入力後すぐに計算結果が得られ応答
速度が速くなる。また、横１行の計算は１ブロツ
ク分であるため、横１行の計算に必要なパタンバ
ツフアは入力パタンＬフレーム分と標準パタン１
フレーム分であり、横形アルゴリズムに比較して
Ｌ＋１／2r＋２へ減少する。
以上説明したように本発明によるパタンマツチ
ング装置は、パタンデータの転送量が少なく、パ
タンバツフアメモリの容量も小さくかつ応答速度
が速いという利点を持つている。
ング装置は、パタンデータの転送量が少なく、パ
タンバツフアメモリの容量も小さくかつ応答速度
が速いという利点を持つている。
次に本発明の１実施例を図面を参照しながら説
明する。本発明によるパタンマツチング装置は第
８図に示すように距離計算部１と、漸化式計算部
２と、パタンマツチング制御部３より構成され
る。距離計算部１は入力パタンＬフレーム分記憶
する入力パタンバツフア１１と、標準パタン１フ
レーム分記憶する標準パタンバツフア１２と、入
力パタンの第ｉフレーム〓iと標準パタンの第ｊ
フレーム〓n jのベクトル間距離‖〓i−〓n j‖を求め
るベクトル間距離計算部１３より構成される。漸
化式計算部２はワークメモリ２１と、計算部２２
と、漸化式計算制御部２３と、相異度メモリ部２
４より構成される。パタンマツチング制御部３は
第１１図に示すタイムチヤートに従つて距離計算
部１と、漸化式計算部２と、入力パタンメモリ部
４と標準パタンメモリ部５を制御する。
明する。本発明によるパタンマツチング装置は第
８図に示すように距離計算部１と、漸化式計算部
２と、パタンマツチング制御部３より構成され
る。距離計算部１は入力パタンＬフレーム分記憶
する入力パタンバツフア１１と、標準パタン１フ
レーム分記憶する標準パタンバツフア１２と、入
力パタンの第ｉフレーム〓iと標準パタンの第ｊ
フレーム〓n jのベクトル間距離‖〓i−〓n j‖を求め
るベクトル間距離計算部１３より構成される。漸
化式計算部２はワークメモリ２１と、計算部２２
と、漸化式計算制御部２３と、相異度メモリ部２
４より構成される。パタンマツチング制御部３は
第１１図に示すタイムチヤートに従つて距離計算
部１と、漸化式計算部２と、入力パタンメモリ部
４と標準パタンメモリ部５を制御する。
始めに、信号Clによつて相異度メモリ部２４の
Go(o)がクリアされる。次に信号iiによつて入力パ
タンメモリ部４より入力パタンの第（ii−１）・
Ｌ＋１フレームより第ii・Ｌフレームを入力パタ
ンバツフア１１へ転送する。さらに信号ｎとｊに
よつて指示される第ｎ番目の標準パタンの第ｊフ
レームを標準パタンバツフア１２へ転送する。
Go(o)がクリアされる。次に信号iiによつて入力パ
タンメモリ部４より入力パタンの第（ii−１）・
Ｌ＋１フレームより第ii・Ｌフレームを入力パタ
ンバツフア１１へ転送する。さらに信号ｎとｊに
よつて指示される第ｎ番目の標準パタンの第ｊフ
レームを標準パタンバツフア１２へ転送する。
続いて相異度メモリ部２４のGo(j)が読み出さ
れ、ワークメモリ部２１のgn（ii−１）・Ｌ、ｊ）
へ格納する。
れ、ワークメモリ部２１のgn（ii−１）・Ｌ、ｊ）
へ格納する。
続いてパタンマツチング制御部３の発する信号
dstによつてベクトル間距離計算部１３は‖〓i＋
〓n j‖の計算を行う。
dstによつてベクトル間距離計算部１３は‖〓i＋
〓n j‖の計算を行う。
ベクトル間距離は例えば
ｄ（ｉ、ｊ）＝‖〓i−〓n j‖K
＝〓k=1
｜〓ik−〓n jk｜
……(7) によつて求められる。ベクトル間距離計算部１３
は第９図と第１２図に示すように始めにベクトル
間距離計算制御部１３１の発するdclによりアキ
ユムレータ１３５をクリアし、ベクトル間距離計
算制御部１３１の発する１〜Ｋまで変化する信号
ｋに従つて入力パタンバツフア１１と標準パタン
バツフアより〓ikと〓n jkを読み出し、減算器１３
２と絶対値回路１３３によつて｜〓ik−〓n jk｜を
求め、加算器１３４とアキユムレータ１３５によ
つて〓｜〓ik−〓n jkを求める。ここで入力パタン
バツフア１１の第ｌフレームには入力パタンの第
（ii−１）・Ｌ＋ｌフレームが記憶されている。
……(7) によつて求められる。ベクトル間距離計算部１３
は第９図と第１２図に示すように始めにベクトル
間距離計算制御部１３１の発するdclによりアキ
ユムレータ１３５をクリアし、ベクトル間距離計
算制御部１３１の発する１〜Ｋまで変化する信号
ｋに従つて入力パタンバツフア１１と標準パタン
バツフアより〓ikと〓n jkを読み出し、減算器１３
２と絶対値回路１３３によつて｜〓ik−〓n jk｜を
求め、加算器１３４とアキユムレータ１３５によ
つて〓｜〓ik−〓n jkを求める。ここで入力パタン
バツフア１１の第ｌフレームには入力パタンの第
（ii−１）・Ｌ＋ｌフレームが記憶されている。
続いて第１０図に示す漸化式計算部２は、ベク
トル間距離計算部１３で得られた距離ｄ（ｉ、ｊ）
とワークメモリ２１のgo（ｉ、ｊ）を用いて(F)式
の漸化式を計算する。漸化式計算制御部２３はパ
タンマツチング制御部３より発せられた信号ｉ
（ｉ＝（ii−１）Ｌ＋ｌ）に従つて第１３図に示す
タイムチヤートに示すような信号ｊ１，ｊ２，ｊ
３を発し、go（ｉ−１、ｊ−２）、go（ｉ−１、ｊ
−１）とgo（ｉ−１、ｊ）を読み出しレジスタ２
２１，２２２，２２３へセツトする。比較器２２
４はレジスタ２２１，２２２，２２３の比較を行
い最小値を出力する。加算器２２５は距離ｄ（ｉ、
ｊ）と比較器２２４の出力とを加算し、その結果
はgo（ｉ、ｊ）へ書き込まれる。
トル間距離計算部１３で得られた距離ｄ（ｉ、ｊ）
とワークメモリ２１のgo（ｉ、ｊ）を用いて(F)式
の漸化式を計算する。漸化式計算制御部２３はパ
タンマツチング制御部３より発せられた信号ｉ
（ｉ＝（ii−１）Ｌ＋ｌ）に従つて第１３図に示す
タイムチヤートに示すような信号ｊ１，ｊ２，ｊ
３を発し、go（ｉ−１、ｊ−２）、go（ｉ−１、ｊ
−１）とgo（ｉ−１、ｊ）を読み出しレジスタ２
２１，２２２，２２３へセツトする。比較器２２
４はレジスタ２２１，２２２，２２３の比較を行
い最小値を出力する。加算器２２５は距離ｄ（ｉ、
ｊ）と比較器２２４の出力とを加算し、その結果
はgo（ｉ、ｊ）へ書き込まれる。
パタンマツチング制御部３は、第１１図に示す
タイムチヤートに従つて距離計算部１と漸化式計
算部２を制御して(6)式の漸化式計算をｌを１から
Ｌまで求め横１行の計算を行う。続いてワークメ
モリ２１よりgo（ii・Ｌ、ｊ）を読み出し、相異
度メモリ部２４のGo(j)へ格納する。続いてｊを
下限Ｌ（ii）より上限Ｕ（ii）まで求め縦Ｌ列の計
算を行う。続いてｎを１よりＮまで求め、Ｎ個の
標準パタンの縦Ｌ列の計算を行う。続いてiiを１
よりＩ／Ｌまで求め、go（Ｉ、Ｊ）を得る。ここ
で下限Ｌ（ii）上限Ｕ（ii）は第４図に示すように
漸化式を計算する範囲を示しており、 Ｌ（ii）＝max（１、（ii−１））Ｌ−ｒ） ……(8) Ｕ（ii）＝min（Ｊ、ii・Ｌ＋ｒ） ……(9) で与えられる。
タイムチヤートに従つて距離計算部１と漸化式計
算部２を制御して(6)式の漸化式計算をｌを１から
Ｌまで求め横１行の計算を行う。続いてワークメ
モリ２１よりgo（ii・Ｌ、ｊ）を読み出し、相異
度メモリ部２４のGo(j)へ格納する。続いてｊを
下限Ｌ（ii）より上限Ｕ（ii）まで求め縦Ｌ列の計
算を行う。続いてｎを１よりＮまで求め、Ｎ個の
標準パタンの縦Ｌ列の計算を行う。続いてiiを１
よりＩ／Ｌまで求め、go（Ｉ、Ｊ）を得る。ここ
で下限Ｌ（ii）上限Ｕ（ii）は第４図に示すように
漸化式を計算する範囲を示しており、 Ｌ（ii）＝max（１、（ii−１））Ｌ−ｒ） ……(8) Ｕ（ii）＝min（Ｊ、ii・Ｌ＋ｒ） ……(9) で与えられる。
以上本発明の構成を実施例にもとづいて説明し
たが、これらの記載は本発明の権利範囲を限定す
るものではない。特に本発明の説明においてワー
クメモリ部２１go（ｉ、ｊ）は、ｉ、ｊによつて
アドレスされるメモリであるが、リングバツフア
にすることによつて3L個のメモリで代用するこ
とができる。
たが、これらの記載は本発明の権利範囲を限定す
るものではない。特に本発明の説明においてワー
クメモリ部２１go（ｉ、ｊ）は、ｉ、ｊによつて
アドレスされるメモリであるが、リングバツフア
にすることによつて3L個のメモリで代用するこ
とができる。
すなわち、横１行の計算では、go（ｉ−ｊ）→
Ｘ、go（ｉ、ｊ−１）→Ｙ、go（ｉ、ｊ−２）→Ｚ
とすれば、第ｊ＋１行目はgo（ｉ、ｊ＋１）→Ｚ、
go（ｉ、ｊ）→Ｘ、go（ｉ、ｊ−１）→Ｙを用いて
計算を行うことができる。
Ｘ、go（ｉ、ｊ−１）→Ｙ、go（ｉ、ｊ−２）→Ｚ
とすれば、第ｊ＋１行目はgo（ｉ、ｊ＋１）→Ｚ、
go（ｉ、ｊ）→Ｘ、go（ｉ、ｊ−１）→Ｙを用いて
計算を行うことができる。
また、漸化式としては簡単な(6)式を用いたが、
特公昭56−28278号公報に記載されている形も、
使用できる。例えば go（ｉ−ｊ）＝ｄ（ｉ、ｊ）＋minｄ（ｉ−
１、ｊ）＋go（ｉ−２、ｊ−１） go（ｉ−１、ｊ−１） go（ｉ−１、ｊ−２） ……(10) を用いる方法も考えられる。ただし。この場合に
は、相異度は時刻ｉ−２まで用いるため、相異度
メモリとして縦２列分２・（2r＋１）Ｎ個のメモ
リが必要である。また、距離もｉ−１まで用いる
ため、横一行Ｌ個のメモリが必要である。
特公昭56−28278号公報に記載されている形も、
使用できる。例えば go（ｉ−ｊ）＝ｄ（ｉ、ｊ）＋minｄ（ｉ−
１、ｊ）＋go（ｉ−２、ｊ−１） go（ｉ−１、ｊ−１） go（ｉ−１、ｊ−２） ……(10) を用いる方法も考えられる。ただし。この場合に
は、相異度は時刻ｉ−２まで用いるため、相異度
メモリとして縦２列分２・（2r＋１）Ｎ個のメモ
リが必要である。また、距離もｉ−１まで用いる
ため、横一行Ｌ個のメモリが必要である。
さらに、入力パタン〓ｉと標準パタン〓n jとの
距離を(4)式のような距離尺度を用いて説明した
が、このかわりに(11)式のようなユークリツド距
離、(12)式のような内積等を用いてよいことは明白
である。
距離を(4)式のような距離尺度を用いて説明した
が、このかわりに(11)式のようなユークリツド距
離、(12)式のような内積等を用いてよいことは明白
である。
ｄ（ｉ、ｊ）＝K
〓k=1
（aik−bn jk）2 ……(11)
ｄ（ｉ、ｊ）＝K
〓k=1
（aik×bn jk） ……(12)
第１図はパタンマツチングの基本原理を示した
図であり、第２図と第５図は従来技術の横形アル
ゴリズムの計算順序を示した図とフローチヤート
であり、第３図と第６図は従来技術の縦形アルゴ
リズムの計算順序を示した図とフローチヤートで
あり、第４図と第７図は本発明の原理を示した図
とフローチヤートであり、第８図は本発明の１実
施例の構成図であり、第９図と第１０図は前記実
施例の詳細な構成図であり、第１１図、第１２
図、第１３図はそれぞれ前記実施例の全体、距離
計算部１、漸化式計算部２のタイムチヤートであ
る。 図面において、１は距離計算部、２は漸化式計
算部、３はパタンマツチング制御部、４は入力パ
タンメモリ部、５は標準パタンメモリ部、１１は
入力パタンバツフア、１２は標準パタンバツフ
ア、１３はベクトル間距離計算部、２１はワーク
メモリ部、２２は漸化式計算部、２３は漸化式計
算制御部、２４は相異度メモリ部、１３１はベク
トル間距離計算制御部、１３２は減算器、１３３
は絶対値回路、１３４は加算器、１３５はアキユ
ムレータ、２２１，２２２，２２３はレジスタ、
２２４は比較器、２２５は加算器である。
図であり、第２図と第５図は従来技術の横形アル
ゴリズムの計算順序を示した図とフローチヤート
であり、第３図と第６図は従来技術の縦形アルゴ
リズムの計算順序を示した図とフローチヤートで
あり、第４図と第７図は本発明の原理を示した図
とフローチヤートであり、第８図は本発明の１実
施例の構成図であり、第９図と第１０図は前記実
施例の詳細な構成図であり、第１１図、第１２
図、第１３図はそれぞれ前記実施例の全体、距離
計算部１、漸化式計算部２のタイムチヤートであ
る。 図面において、１は距離計算部、２は漸化式計
算部、３はパタンマツチング制御部、４は入力パ
タンメモリ部、５は標準パタンメモリ部、１１は
入力パタンバツフア、１２は標準パタンバツフ
ア、１３はベクトル間距離計算部、２１はワーク
メモリ部、２２は漸化式計算部、２３は漸化式計
算制御部、２４は相異度メモリ部、１３１はベク
トル間距離計算制御部、１３２は減算器、１３３
は絶対値回路、１３４は加算器、１３５はアキユ
ムレータ、２２１，２２２，２２３はレジスタ、
２２４は比較器、２２５は加算器である。
Claims (1)
- 【特許請求の範囲】 １ 特徴ベクトルの時系列よりなる入力パタン Ａ＝〓1、〓2、……〓Iとあらかじめ記憶され
ているＮ個の標準パタンの第ｎ番目の標準パタン
Bn＝〓n 1、〓n 2、……〓n Joとの間で入力パタンの時
間軸ｉと標準パタンの時間軸ｊを対応させる時間
関数ｊ(i)の上の入力パタンaiと標準パタン〓n jの
ベクトル間距離ｄ（〓i、〓n j）の和として定義さ
れる相異度の最小値を求めるパタンマツチング装
置において、入力パタンの時間点ｉをＬ個づつま
とめてブロツク化し前記ブロツク番号iiを１より
Ｉ／Ｌまで変化させ、各iiに関して標準パタンの
時間点を示す信号ｊをマツチングを行う領域の下
限Ｌ（ii）より上限Ｕ（ii）まで変化させ、さらに
各信号ｊについて入力パタンの１ブロツク内の時
間点を示す信号ｌを１よりＬまで変化させて与え
るパタンマツチング制御部と、前記制御部の信号
ｌによつて番地指定される入力パタンバツフア部
と、標準パタンの時刻ｊのベクトル〓n jを一時記
憶する標準パタンバツフア部とを有し、前記入力
パタンバツフア部と標準パタンバツフア部より入
力パタン〓iと標準パタン〓n jを読み出しベクトル
距離ｄ（〓i、〓n j）を求める距離計算部と、前記
制御部の信号ｊとｎによつて番地指定される相異
度メモリ部Go(j)を有し、入力パタンの時間点の
ブロツク番号iiに関し、時間点（ii−１）・Ｌにお
ける相異度Go(j)を接続条件として前記距離（〓i、
〓n j）を参照して動的計画の漸化式を各標準パタ
ンの時間点ｊと入力パタンの１ブロツク内の各時
間点ｌについて計算し、入力パタンの時間点ii・
Ｌにおける相異度Go(j)を求める漸化式計算部と
を持つことを特徴とするパタンマツチング装置。
Priority Applications (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58201385A JPS60179797A (ja) | 1983-10-27 | 1983-10-27 | パタンマツチング装置 |
| CA000466378A CA1218152A (en) | 1983-10-27 | 1984-10-26 | Pattern matching system |
| DE8484112926T DE3473667D1 (en) | 1983-10-27 | 1984-10-26 | Pattern matching system |
| EP84112926A EP0144689B1 (en) | 1983-10-27 | 1984-10-26 | Pattern matching system |
| US07/308,985 US4882756A (en) | 1983-10-27 | 1989-02-10 | Pattern matching system using dynamic programming |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58201385A JPS60179797A (ja) | 1983-10-27 | 1983-10-27 | パタンマツチング装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS60179797A JPS60179797A (ja) | 1985-09-13 |
| JPH0466039B2 true JPH0466039B2 (ja) | 1992-10-21 |
Family
ID=16440203
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP58201385A Granted JPS60179797A (ja) | 1983-10-27 | 1983-10-27 | パタンマツチング装置 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US4882756A (ja) |
| EP (1) | EP0144689B1 (ja) |
| JP (1) | JPS60179797A (ja) |
| CA (1) | CA1218152A (ja) |
| DE (1) | DE3473667D1 (ja) |
Families Citing this family (19)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS60211498A (ja) * | 1984-04-05 | 1985-10-23 | 日本電気株式会社 | 連続音声認識装置 |
| JPH0782544B2 (ja) * | 1989-03-24 | 1995-09-06 | インターナショナル・ビジネス・マシーンズ・コーポレーション | マルチテンプレートを用いるｄｐマツチング方法及び装置 |
| IT1229782B (it) * | 1989-05-22 | 1991-09-11 | Face Standard Ind | Metodo ed apparato per riconoscere parole verbali sconosciute mediante estrazione dei parametri e confronto con parole di riferimento |
| CA2042926C (en) * | 1990-05-22 | 1997-02-25 | Ryuhei Fujiwara | Speech recognition method with noise reduction and a system therefor |
| JPH04182700A (ja) * | 1990-11-19 | 1992-06-30 | Nec Corp | 音声認識装置 |
| US5189709A (en) * | 1991-08-26 | 1993-02-23 | The United States Of America As Represented By The United States National Aeronautics And Space Administration | Dynamic pattern matcher using incomplete data |
| US5845092A (en) * | 1992-09-03 | 1998-12-01 | Industrial Technology Research Institute | Endpoint detection in a stand-alone real-time voice recognition system |
| EP0702354A1 (en) * | 1994-09-14 | 1996-03-20 | Matsushita Electric Industrial Co., Ltd. | Apparatus for modifying the time scale modification of speech |
| JP2964881B2 (ja) * | 1994-09-20 | 1999-10-18 | 日本電気株式会社 | 音声認識装置 |
| US5664174A (en) * | 1995-05-09 | 1997-09-02 | International Business Machines Corporation | System and method for discovering similar time sequences in databases |
| JP3576272B2 (ja) * | 1995-06-22 | 2004-10-13 | シャープ株式会社 | 音声認識装置および方法 |
| JP2980026B2 (ja) * | 1996-05-30 | 1999-11-22 | 日本電気株式会社 | 音声認識装置 |
| US6122757A (en) * | 1997-06-27 | 2000-09-19 | Agilent Technologies, Inc | Code generating system for improved pattern matching in a protocol analyzer |
| US6851105B1 (en) * | 1999-10-05 | 2005-02-01 | Borland Software Corporation | Method and system for generating, applying, and defining a pattern |
| KR100344530B1 (ko) * | 1999-12-20 | 2002-07-24 | 한국과학기술원 | 시계열 데이터베이스에서 윈도우 구성의 이원성을 사용한 서브시퀀스 매칭방법 |
| US6785419B1 (en) * | 2000-12-22 | 2004-08-31 | Microsoft Corporation | System and method to facilitate pattern recognition by deformable matching |
| EP1435087B1 (de) * | 2001-10-11 | 2005-08-31 | Siemens Aktiengesellschaft | Verfahren zur erzeugung von sprachbausteine beschreibenden referenzsegmenten und verfahren zur modellierung von spracheinheiten eines gesprochenen testmusters |
| US8307339B2 (en) * | 2004-03-15 | 2012-11-06 | Ramco Systems Limited | Software reuse in model based software systems |
| US9805111B2 (en) * | 2010-10-04 | 2017-10-31 | Telefonaktiebolaget L M Ericsson | Data model pattern updating in a data collecting system |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3816722A (en) * | 1970-09-29 | 1974-06-11 | Nippon Electric Co | Computer for calculating the similarity between patterns and pattern recognition system comprising the similarity computer |
| US4059725A (en) * | 1975-03-12 | 1977-11-22 | Nippon Electric Company, Ltd. | Automatic continuous speech recognition system employing dynamic programming |
| US4400788A (en) * | 1981-03-27 | 1983-08-23 | Bell Telephone Laboratories, Incorporated | Continuous speech pattern recognizer |
| US4489434A (en) * | 1981-10-05 | 1984-12-18 | Exxon Corporation | Speech recognition method and apparatus |
| US4489435A (en) * | 1981-10-05 | 1984-12-18 | Exxon Corporation | Method and apparatus for continuous word string recognition |
| JPS5879300A (ja) * | 1981-11-06 | 1983-05-13 | 日本電気株式会社 | パタ−ン距離計算方式 |
| JPS5885499A (ja) * | 1981-11-18 | 1983-05-21 | 株式会社デンソー | 連続音声認識装置 |
| US4592086A (en) * | 1981-12-09 | 1986-05-27 | Nippon Electric Co., Ltd. | Continuous speech recognition system |
| JPS58100195A (ja) * | 1981-12-10 | 1983-06-14 | 日本電気株式会社 | 連続音声認識装置 |
| US4570232A (en) * | 1981-12-21 | 1986-02-11 | Nippon Telegraph & Telephone Public Corporation | Speech recognition apparatus |
| JPS58132298A (ja) * | 1982-02-01 | 1983-08-06 | 日本電気株式会社 | 窓制限付パタンマツチング装置 |
-
1983
- 1983-10-27 JP JP58201385A patent/JPS60179797A/ja active Granted
-
1984
- 1984-10-26 CA CA000466378A patent/CA1218152A/en not_active Expired
- 1984-10-26 EP EP84112926A patent/EP0144689B1/en not_active Expired
- 1984-10-26 DE DE8484112926T patent/DE3473667D1/de not_active Expired
-
1989
- 1989-02-10 US US07/308,985 patent/US4882756A/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CA1218152A (en) | 1987-02-17 |
| US4882756A (en) | 1989-11-21 |
| JPS60179797A (ja) | 1985-09-13 |
| EP0144689B1 (en) | 1988-08-24 |
| DE3473667D1 (en) | 1988-09-29 |
| EP0144689A1 (en) | 1985-06-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0466039B2 (ja) | ||
| US4592086A (en) | Continuous speech recognition system | |
| JP2595495B2 (ja) | パタンマッチング装置 | |
| US20030125938A1 (en) | Speech recognition system | |
| US4555796A (en) | DP Matching system for recognizing a string of words connected according to a regular grammar | |
| US5369728A (en) | Method and apparatus for detecting words in input speech data | |
| US4901352A (en) | Pattern matching method using restricted matching paths and apparatus therefor | |
| JPS6024994B2 (ja) | パタ−ン類似度計算方式 | |
| JPH01138597A (ja) | 連続音声認識方式 | |
| US5121465A (en) | Pattern matching system | |
| CA1301338C (en) | Frame comparison method for word recognition in high noise environments | |
| US4670850A (en) | Pattern matching apparatus | |
| JPH0887294A (ja) | 音声認識装置 | |
| JPS5898796A (ja) | 連続音声認識装置 | |
| US5420969A (en) | Apparatus using mean value image smoothing for a two-dimensional image signal | |
| JPH0320759B2 (ja) | ||
| JPH0638195B2 (ja) | パタンマッチング装置 | |
| JPS6122350B2 (ja) | ||
| JP3348735B2 (ja) | パターン照合方式 | |
| JPS5926960B2 (ja) | 時系列パタンマツチング装置 | |
| JPH0646358B2 (ja) | パタ−ン比較装置 | |
| JPH0577080B2 (ja) | ||
| JPH0554119B2 (ja) | ||
| JPH05249997A (ja) | 音声認識装置 | |
| KR960007131B1 (ko) | 음성인식시스템의 연속숫자음 인식방법 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |