JPH04248595A - Ｄｐマッチング法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はパターンマッチング方法
に関する。

【０００２】

【従来の技術】従来、「情報基礎学詳説」（コロナ社出
版、坂井利之編）に記載されているように、ｕ（ｉ）を
入力パターンＡのｉフレームを標準パターンＢのｕ（ｉ
）フレームに対応づけるパターン伸縮関数とする時、入
力パターンＡと標準パターンＢの時系列間の距離の定義
式が、

【０００３】

【数３】

【０００４】で表され、境界条件を｛ｕ（１）＝１、ｕ
（Ｉ）＝Ｊ｝とするＤＰマッチング法や、「Ｔｗｏ−ｌ
ｅｖｅｌ　ＤＰ−ｍａｔｃｈｉｎｇ−ａ　ｄｙｎａｍｉ
ｃ　ｐｒｏｇｒａｍｍｉｎｇ　ｂａｓｅｄ　ｐａｔｔｅ
ｒｎ　ｍａｔｔｉｎｇａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｃ
ｏｎｎｅｃｔｅｄ　ｗｏｒｄ　ｒｅｃｏｇｎｉｔｉｏｎ
ｓ」（ＩＥＥＥ　Ｔｒａｎｓ．　Ａｃｏｕｓｔ．，Ｓｐ
ｅｅｃｈ＆　Ｓｉｇｎａｌ　Ｐｒｏｃｅｓｓ．，ＡＳＳ
Ｐ−２７，６，ｐｐ５８８−５９５　　ｂｙ　Ｈ．　Ｓ
ａｋｏｅ）に記載されているように、連続単語認識のた
めの２段ＤＰマッチング法が知られていた。

【０００５】ここで、Ｉは入力パターンのフレーム数、
Ｊは標準パターンのフレーム数を表す。

【０００６】

【発明が解決しようとする課題】しかし、従来のＤＰマ
ッチング法では、入力パターン中に、本来照合すべきパ
ターンの前後に、標準パターンの特徴パラメータと特徴
量が異なる余分なパターンが付加された場合、入力パタ
ーン全体と、標準パターン全体を照合するため、正確な
パターンマッチングが不可能となるという問題点を有し
ていた。

【０００７】従来のＤＰマッチング法を単語音声認識に
応用した場合、単語の前後に、話者が自然に発声してし
まう、「えー」「んー」「です」等の言葉を付けて発声
した時に、余分なパターンを含んだ入力パターン全体と
、単語の標準パターンとのパターンマッチングを行うた
め、誤認識を起こしてしまうという問題点を有していた
。この問題を解決する方法として、２段ＤＰマッチング
法を用いて、入力パターンから、単語部分をスポッティ
ングする方法があるが、この方法では、入力パターン長
がＩフレームであった場合、入力パターンの総てのフレ
ームを始点とするＩ個の入力パターンと標準パターンと
のパターンマッチングを行うため、計算時間が長くなり
、音声認識の実時間処理が難しくなる、という問題点を
有している。

【０００８】

【課題を解決するための手段】本発明のＤＰマッチング
法は、ＤＰマッチング法において、入力パターンＡと標
準パターンＢの特徴パラメータの列を、Ａ＝ａ１、ａ２
、・・、ａｉ、・・、ａＩ、Ｂ＝ｂ１、ｂ２、・・、ｂ
ｊ、・・、ｂＪ （Ｉは入力パターンのフレーム数、Ｊは標準パターンの
フレーム数） で表し、ｕ（ｉ）を、前記入力パターンＡのｉフレーム
を前記標準パターンＢのｕ（ｉ）フレームに対応づける
パターン伸縮関数とする時、前記入力パターンＡと前記
標準パターンＢの列間の距離の定義式を、

【０００９】

【数４】

【００１０】とし、前記列間の距離の定義式中の部分式

【００１１】

【数５】

【００１２】における境界条件を｛ｕ（ｉ１）＝１、ｕ
（ｉ２）＝　　Ｊ｝とし、前記列間の距離の定義式にお
いて、ｉ＞ｉ１の時、ｕ（ｉ）≠１とすることを特徴と
する。

【００１３】

【実施例】（実施例１）本発明のＤＰマッチング法を、
ワードスポッティングを行う単語認識の音声認識装置に
応用した実施例を図面に沿って説明する。

【００１４】図１は、本発明のＤＰマッチング法を用い
た音声認識装置のシステム構成図である。話者によって
発話された音声を、マイク１より入力し、Ａ／Ｄ変換部
２において、１６［ＫＨｚ］、１２ビットのディジタル
信号に変換し、特徴抽出部３において、２０［ｍｓ］を
１フレームとして、１フレーム毎に、ハミングウィンド
ウ処理、線形予測分析を行い、１４次ＬＰＣケプストラ
ム係数を特徴パラメータとして求める。この時、フレー
ムのシフト量は１０［ｍｓ］とする。このようにして得
た特徴パラメータ列を入力パターンとして、単語認識部
４において、あらかじめ学習させてあるＮ個の単語の標
準パターンと、本発明のＤＰマッチング法を用いてパタ
ーンマッチングを行うことにより、単語をスポッティン
グし、認識する。このときＮ個の単語の標準パターンは
単語辞書５に登録されている。

【００１５】まず、図２、図３の説明に必要な記号を定
義する。

【００１６】話者が発話した音声を入力パターンαとし
、入力パターン長をＩとし、単語名をｎとし、単語数を
Ｎとし、単語ｎの標準パターンをβｎとし、単語ｎの標
準パターン長をＪｎとし、入力パターンαの特徴パラメ
ータの時系列を、ａ（１）、ａ（２）、・・・、ａ（Ｉ
）、とし、単語ｎの標準パターンβｎの特徴パラメータ
の時　　系列を、ｂｎ（１）、ｂｎ（２）、・・・、ｂ
ｎ（Ｊｎ）、とする。

【００１７】ｄｎ（ｉ、ｊ）を入力パターンαの第ｉフ
レーム（ａ（ｉ））と単語ｎの標準パターンβｎの第ｊ
フレーム（ｂｎ（ｊ））のフレーム間距離とする。

【００１８】ＢＰｎ（ｉ、ｊ）は、格子点（ｉ、ｊ）に
おいて、照合する入力パターンαの照合開始位置を示す
バックポインタとする。

【００１９】ｇｎ（ｉ、ｊ）は、入力パターンαのＢＰ
ｎ（ｉ、ｊ）フレームからｉフレームと、単語ｎの標準
パターンβｎの１フレームからｊフレームとの最小累積
距離とする。

【００２０】ｕｎ（ｉ）を、入力パターンαのｉフレー
ムを標準パターンβｎのｕｎ（ｉ）フレームに対応づけ
るパターン伸縮関数とし、本実施例においては、パター
ン伸縮関数ｕｎ（ｉ）の条件を、ｕｎ（ｉ−１）＝ｊ、
または、ｕｎ（ｉ−１）＝ｊ−１、または、ｕｎ（ｉ−
１）＝ｊ−２、の時に限り、ｕｎ（ｉ）＝ｊ、とする。 この条件は、図４で示すＤＰパス４１、４２、４３に対
応する。

【００２１】入力パターンαと標準パターンβｎの時系
列間の距離の定義式を、

【００２２】

【数６】　　　　・・・（１）式

【００２３】とする。

【００２４】ここで、ｉｎ（１）は｛１≦ｉｎ（１）＜
Ｉ｝の範囲の任意の入力パターンαのフレーム番号で、
単語ｎの標準パターンβと入力パターンαの照合開始位
置を示す。

【００２５】ｉｎ（２）は｛１＜ｉｎ（２）≦Ｉ｝の範
囲の任意の入力パターンαのフレーム番号で、単語ｎの
標準パターンβと入力パターンαの照合終了位置を示す
。

【００２６】（１）式で表される時系列間の距離の定義
式中の部分式、

【００２７】

【数７】　　　　・・・（２）式

【００２８】における境界条件を、｛ｕｎ（ｉｎ（１）
）＝１、ｕｎ（ｉｎ（２））＝Ｊｎ｝とする。これは、
「入力パターンαの照合開始フレームが任意の第ｉｎ（
１）フレームの時、単語ｎの標準パターンβｎの照合開
始フレームは第１フレームである」ということ　　と、
「入力パターンαの照合終了フレームが任意の第ｉｎ（
２）フレームの時、単語ｎの標準パターンβｎの照合終
了フレームは第Ｊｎフレームである」ということを示す
。この境界条件により、部分式（２）式は、単語ｎの標
準パターンβｎと、　　入力パターンα中の任意のｉｎ
（１）フレームから任意のｉｎ（２）フレームまでのパ
ターンとの最小累積距離を表す。

【００２９】よって、部分式（２）式を最小にする、ｉ
ｎ（１）フレームとｉｎ（２）フレームを選択すること
により、単語ｎの標準パターンβｎとの距離を最小にす
る、入力パターンα中の最適範囲をスポッティングでき
る。このようにスポッティングされた入力パターンα中
のｉｎ（１）フレームからｉｎ（２）フレームまでのパ
ターンと標準パターンβｎとの最小累積距離が、入力パ
ターンαと標準パターンβｎとの最小累積距離であり、
この定義式は（１）式となる。

【００３０】本発明においては、部分式（２）式を計算
するアルゴリズムを高速化するために、ｉ＞ｉｎ（１）
の時、ｕｎ（ｉ）≠１とする。これは図４において、ｊ
−２＝１の時（すなわちｊ＝３の時）に限り、ＤＰパス
４３を許可しない、ということである。この条件により
、入力パターンαの任意の第ｉフレームと単語ｎの標準
パターンβｎの第１フレームとのフレーム格子点（ｉ、
１）における最小累積距離ｇｎ（ｉ、１）は、常にその
格子点でのフレーム間距離となり、他のフレーム間距離
とは無関係となる。すなわち、どのフレーム格子点（ｉ
、１）もパターン照合開始点となり得ることになる。

【００３１】この条件を用いることにより計算が高速に
なることを、図２を用いて説明する。

【００３２】格子点１４における最小累積距離のＤＰパ
スが、ＤＰパス１６、１７であった場合、格子点１４に
おける最小累積距離は、格子点１０、１３、１４のフレ
ーム間距離の和であり、この照合開始格子点は、格子点
１０である。格子点１２における最小累積距離は、上記
の条件により格子点１１から格子点１２へのＤＰパスは
存在しないため、格子点１２におけるフレーム間距離で
あり、照合開始格子点は格子点１２である。格子点１５
における最小累積距離を求めるためのＤＰパスは、格子
点１４における最小累積距離と格子点１２における最小
累積距離のうち、最小累積距離の値の小さい方の格子点
と格子点１５を結ぶパスとして求められる。ここで、Ｄ
Ｐパス１９が選択された場合、本発明のＤＰマッチング
法では、上記で述べたように、照合開始格子点は格子点
１２となる。このように、最初の照合開始格子点を、格
子点（１、１）として、最小累積距離の計算を始めた場
合、任意の格子点（ｉ、ｊ）の最小累積距離は、格子点
（１、１）から格子点（ｉ−１、１）のうちの最適な格
子点から格子点（ｉ、ｊ）までの累積距離として計算さ
れ、格子点（１、１）から格子点（ｉ−１、１）のうち
の最適な格子点が、新たに照合開始格子点として選択さ
れる。このようにして、ｉ＝１からＩまで、順にｉの値
を増やしながら、ｊ（１からＪｎまで）との格子点にお
ける最小累積距離を、　　１回だけ求めていくことによ
り、任意のｉを入力パターンαの終了フレームとする、
単語ｎの標準パターンβｎとの最小累積距離と、その照
合開始格子点を１点　　だけ求めることができる。

【００３３】従来方法では、格子点１５へのＤＰパスが
、ＤＰパス１９となった時、格子点１２における最小累
積距離は、格子点１０、１１、１２におけるフレーム間
距離の和で、照合開始格子点は格子点１０である。すな
わち、格子点１０から照合を開始した場合、どの格子点
においても、照合開始格子点は格子点１０となる。よっ
て、任意のｉを入力パターンαの終了フレームとする、
単語ｎの標準パターンβｎとの最小累積距離を求めるた
めには、照合開始格子点を格子点（１、１）から格子点
（ｉ−１、１）までのそれぞれの格子点とする、ｉ−１
回の計算を行い、どの格子点を照合開始格子点として計
算した時が、最も累積距離が小さいかを計算する必要が
ある。よって、入力パターン数をＩフレームとした場合
、最小累積距離の計算ループは本発明の（Ｉ−１）／２
倍となる。仮に、入力フレーム数Ｉが１００フレームの
場合、最小累積距離の計算ループは、本発明の約５０倍
となる。

【００３４】次に、図３を用いて、本発明のＤＰマッチ
ング法を実際に行うアルゴリズムを説明する。

【００３５】ループ２１では、単語辞書５に登録してあ
るＮ個の単語の標準パターンと入力パターンとのパター
ンマッチングを行うために、ｎ＝１、２、・・・、Ｎに
ついて、ループ２２、演算２３、演算２４、ループ２５
、演算２６、演算２７、ループ２８、ループ２９、演算
３０、演算３１、演算３２を実行する。

【００３６】ループ２２では、入力パターンの各フレー
ム、ｉ＝１、２、・・・、Ｉについて、演算２３、演算
２４を実行し、累積距離ｇｎ（ｉ、１）、バックポイン
タＢＰｎ（ｉ、１）を初期化する。

【００３７】累積距離ｇｎ（ｉ、１）の初期値は、入力
フレームαの第ｉフレームと単語ｎの標準パターンβｎ
の第１フレームとのフレーム間距離ｄｎ（ｉ、１）とす
る。格子点（ｉ、１）におけるバックポインタＢＰｎ（
ｉ、１）の初期値はｉとする。　　この初期化は、単語
ｎの標準パターンβｎと入力パターンαの照合開始位置
にお　　ける境界条件を示す。

【００３８】ループ２５では、単語ｎの標準パターンの
各フレーム、ｊ＝２、３、・・・、Ｊｎについて、演算
２６、演算２７を実行し、累積距離ｇｎ（１、ｊ）、バ
ックポインタＢＰｎ（１、ｊ）を初期化する。ここで、
累積距離ｇｎ（１、ｊ）の初期値は無限大とする。この
初期化も、単語ｎの標準パターンβｎと入力パターンα
の照合開始位置における境界条件を満たすための初期化
である。

【００３９】ループ２８では、入力パターンの各フレー
ム、ｉ＝２、３、・・・、Ｉについて、ループ２９、演
算３０、演算３１、演算３２を実行する。

【００４０】ループ２９では、単語ｎの標準パターン、
ｊ＝２、３、・・・、Ｊｎについて、演算３０、演算３
１、演算３２を実行する。

【００４１】演算３０では、格子点（ｉ、ｊ）において
、本実施例で許可する３つのＤＰパス、（図４で示され
る、ＤＰパス４１、ＤＰパス４２、ＤＰパス４３）のう
ち、最適なＤＰパスを選択する演算を行う。すなわち、
格子点（ｉ−１、ｊ）、（ｉ−１、ｊ−１）、（ｉ−１
、ｊ−２）までの累積距離が最小である格子点を選択す
る値である。演算３０の中で用いられている関数、

【０
０４２】

【数８】

【００４３】は、｛｝中の関数ｇｎ（ｉ−１，ｋ）の値
を最小にするｋを求める関数と定義する。この演算によ
って求められるｋ′の値は、上記に示したパターン伸縮
関数ｕｎ（ｉー１）の値である。よって、ｊまたは、ｊ
−１、または、ｊー２、のい　　づれかの値である。

【００４４】演算３１では、格子点（ｉ、ｊ）における
累積距離ｇｎ（ｉ、ｊ）を求める。この時、照合してい
るパターンは、入力パターンαのＢＰｎ（ｉ−１、ｋ′
）フ　　レームからｉフレームと、単語ｎの標準パター
ンβｎの１フレームからｊフレー　　ムである。ここで
、バックポインタＢＰｎ（ｉ−１、ｋ′）には、格子点
（ｉ−　　１、ｋ′）における、入力パターンαの照合
開始位置が保存されている。また、累積距離ｇｎ（ｉ、
ｋ′）は、入力パターンαのＢＰｎ（ｉ−１、ｋ′）フ
レームからｉフレームと、単語ｎの標準パターンβｎの
１フレームからｋ′フレームと　　の最小累積距離であ
る。更に、格子点（ｉ、ｋ′）は、演算３０で演算され
たように、格子点（ｉ、ｊ）にとって、最適なＤＰパス
をとる格子点ある。よって、ｇｎ（ｉ、ｋ′）の値に、
格子点（ｉ、ｊ）におけるフレーム間距離ｄｎ（ｉ、ｊ
）を加えることにより、入力パターンαのＢＰｎ（ｉ−
１、ｋ′）フレームからｉ　　フレームと、単語ｎの標
準パターンβｎの１フレームからｊフレームとの最小累
　　積距離ｇｎ（ｉ、ｊ）を求めることができる。

【００４５】この時、累積距離ｇｎ（ｉ、ｊ）が照合パ
ターン長に依存しないように、入力パターンの照合パタ
ーン長で割っている。また本発明のＤＰマッチング法で
は、（１）式で示されるように、累積距離ｇｎ（ｉ、ｊ
）は標準パターン長には依存　　しないため、標準パタ
ーン長に対する処置は施さない。

【００４６】演算３２では格子点（ｉ、ｊ）におけるバ
ックポインタを演算している。この演算により、格子点
（ｉ、ｊ）における累積距離ｇｎ（ｉ、ｊ）の入力パタ
ーンの照合開始位置を、バックポインタＢＰｎ（ｉ、ｊ
）に保存する。

【００４７】以上のように演算された累積距離ｇｎ（ｉ
、ｊ）の中から、入力パターンαの照合終了位置に関す
る境界条件｛ｕｎ（ｉｎ（２））＝Ｊｎ｝を満たす累積
距離ｇｎ（　　ｉ、Ｊｎ）を用いて、（ここで、ｉｎ（
２）は入力パターンαの任意のフレーム番号　　なので
、入力パターンαの任意のフレーム番号ｉと同義である
。）演算３３を実行することにより、累積距離ｇｎ（ｉ
、Ｊｎ）を最小にする、単語ｎ′と入力パターンαの照
合終了位置ｉ′フレームを選択する。

【００４８】このｎ′とｉ′をバックポインタＢＰｎ（
ｉ、ｊ）に代入して、演算３４を実行することにより、
単語名がｎ′で、入力パターンαの照合終了位置がｉ′
の時の、入力パターンαの照合開始位置Ｂフレームが得
られる。

【００４９】以上の全ての演算によって、話者が発話し
た余分な音声を含む入力パターンαの中から、最適な単
語ｎ′を認識し、その単語が存在する最適区間（Ｂフレ
ーム〜ｉ′フレーム）をスポッティングする、「ワード
スポッティング」を行うことができる。

【００５０】

【発明の効果】本発明のＤＰマッチング法を用いること
により、話者が自然に発話した音声中から、単語部分だ
けをスポッティングし認識する「ワードスポッティング
」を、従来方法に比べ短時間で実行することが可能とな
る効果がある。この効果を以下に、具体的な数字で示す
。

【００５１】従来方法の２段ＤＰマッチングを用いて計
算を行った場合、入力パターン長がＩフレーム、標準パ
ターン長がＪフレームの場合、累積距離を計算するルー
プの回数が、（Ｉ−１）／２＊Ｉ＊Ｊ回であるのに対し
、本発明のＤＰマッチング法を用いた場合、累積距離を
計算するループの回数は、Ｉ＊Ｊ回となる。すなわち、
累積距離を計算するループの回数は、従来方法の、２／
（Ｉ−１）となる。

【００５２】本実施例の様に、音声を１６［ＫＨｚ］で
サンプリングし、１フレームを２０［ｍｓ］とし、シフ
ト量を１０［ｍｓ］とした場合、１秒間の入力音声のパ
ターン長Ｉは、９９フレームとなるので、累積距離を計
算するループの回数は、従来方法の１／４８となる。

【図面の簡単な説明】

【図１】本発明に関する音声認識装置のシステム構成図
。

【図２】本発明に関するＤＰパスと、入力フレームと標
準フレームとの格子点を示す図。

【図３】本発明に関する音声認識方法のアルゴリズムを
示す流れ図。

【図４】本発明に関するＤＰパスを示す図。

【符号の説明】

１　　マイク ２　　Ａ／Ｄ変換部 ３　　特徴抽出部 ４　　単語認識部 ５　　単語辞書 １０　　格子点 １１　　格子点 １２　　格子点 １３　　格子点 １４　　格子点 １５　　格子点 １６　　ＤＰパス １７　　ＤＰパス １８　　ＤＰパス １９　　ＤＰパス ２１　　ループ ２２　　ループ ２３　　演算 ２４　　演算 ２５　　ループ ２６　　演算 ２７　　演算 ２８　　ループ ２９　　ループ ３０　　演算 ３１　　演算 ３２　　演算 ３３　　演算 ３４　　演算 ４１　　ＤＰパス ４２　　ＤＰパス ４３　　ＤＰパス

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　ＤＰマッチング法において、入力パタ
   ーンＡと標準パターンＢの特徴パラメータの列を、Ａ＝
   ａ１、ａ２、・・、ａｉ、・・、ａＩ、Ｂ＝ｂ１、ｂ２
   、・・、ｂｊ、・・、ｂＪ （Ｉは入力パターンのフレーム数、Ｊは標準パターンの
   フレーム数） で表し、ｕ（ｉ）を、前記入力パターンＡのｉフレーム
   を前記標準パターンＢのｕ（ｉ）フレームに対応づける
   パターン伸縮関数とする時、前記入力パターンＡと前記
   標準パターンＢの列間の距離の定義式を、【数１】 とし、前記列間の距離の定義式中の部分式【数２】 における境界条件を｛ｕ（ｉ１）＝１、ｕ（ｉ２）＝　
   　Ｊ｝とし、前記列間の距離の定義式において、ｉ＞ｉ
   １の時、ｕ（ｉ）≠１とすることを特徴とする、ＤＰマ
   ッチング法。