JPS6022283A - パタ−ンマツチング装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は文字や音声の認識システムの主要部を構成する
パターンマツチング装置の改良に関する。

本発明は時系列パターンのマツチング処理に広く利用さ
れ得るものであるが、以下では特に音声パターンに例を
とって説明を行う。

音声パターンは特徴の時系列として表現され、このよう
なパターン間の比較処理、すなわちパターンマツチング
を行って音声認識を行う方法が広く行われている。高精
度な認識のためにはパターン変動に対して安定な、すな
わちパターン変動吸収能力の尚いマツチング手法が必要
とされる。

時間方法の伸縮歪に対しては特願昭４５−５３８９６号
明細書（特公昭５０−２３９４１号公報）に記載された
動的計画法（Ｄｙｎａｍｉｃ　Ｐｒｏｇｒａｍｍｉｎｇ
　、以下ＤＰと略す）を用いたＤＰマツチング法が適用
され効果が得られている。

しかし、実際の音声パターンには、時間伸縮以外に例え
ば「日本音響学会音声研究会資料５Ｓ３−２５（１９８
３年６月２４日）に１連続音声中の母勧奇形について″
と題して発表された論文」に記されている如く、長音化
（例えばｋｉｎｏｕ−ｋｉｎｏｏ）。

鼻音化、無声化、脱落（ａｒｕ　１１ｉｔｏ−ａｒ　ｌ
；１ｔｏ）のように局所的な変形が生じる。しかも、こ
れらの変形は定常的に発生したり、発生しなかったりす
るのではなく、発生の速度や前後の音韻や単語などの要
因に応じて不確定的である。

このような変形に対処しつるＤＰマツチング法として「
ね・願昭５７−１５６４１３号明細書」Ｃ以下文献（１
）と呼ぶ）及び［日本音響学会音声研究会資料５８５−
２３に゛ＤＰマツチングのある一般化“と題して発表さ
れた論文］ｃＣ以下文献２）と呼ぶ）に記載されている
「スタックＤＰマツチング」と呼ばれる方法がある。こ
の方法を実行する装置は、上記文献（１）を引用すると
、「特徴の時系列中に分岐開始記号、分岐区切り記号、
分岐終了記号及び省略開始記号、省略終了記号等の制御
記号を含んで成る標準バタンを記憶する標準バタン記憶
部と、特徴の時系列として記述される入力バタンを保持
する入力バタンバッファと、上記標準バタン中の各要素
を制御記号と特徴とに分類するデコーダと複数の記憶番
地を層として多層構成されるスタックメモリーと、上記
人力バタンの特徴と標準バタンの特徴間の距離を算出す
る距離計算部と、上記スタックメモリより読み出される
複数個の数値を比較し、それらの最小値に前記距離計算
部よりの出力を加算し、前記スタックメモリに書き込む
という動的計画演算を行なうマツチング処理部と、前記
デコーダーよりの制御信号に応じて前記スタックメモリ
ーラアッシュ、ポツプ各層間の最小値選択各層間のデー
ター転送を行なうスタック演算部とより構成される。」
と定義される。

このスタックＤＰマツチング法では、標準パターンを特
徴の単純な時系列と考えず、時系列中に分岐や省略を許
容している。すなわち、゛（，゛／″・）″なる制御子
を時系列中に許し、゛（″と゛）″で囲まれ′″／＃で
区切られる複数個の部分時系列は、いずれか一つのみが
選択されるとしている。また制御子１〔′と１〕′で囲
まれる部分時系列は省略可能であり、省略すべきか否か
が選択される。

このような標準パターンと特徴時系列とのＤＰマツチン
グの実行のため、複数の記憶番地を一層として、多層構
成されるスタックメモリを用いる。

上記制御子が標準パターン時系列中に出現するのに応じ
てＤＰ計算に使用するスタックの層をＰＵＳＨあるいは
ｌ）　ＯＰすることによって、分岐や省略を最適決定す
るというアルゴリズムがスタックＤＰマツチング法であ
る。

この手法によって分岐や省略の可能性を含んだ時系列の
パターンマツチングが可能であり、前記の無声化、鼻音
化、脱落等の音声パターン変形に対処出来る。しかし、
上記文献（１）の第１図に関連して述べられているごと
く、従来のスタックＤＰマツチング法は本質的に横形窓
式の１）Ｐマツチング法を改良したものであって、スタ
ックメモリの各層にある幅（整合窓と呼ばれる）分の記
ｍ番地が必要とされるためスタックメモリー全体として
の、記憶量が大きくなるという問題があった。また最近
「日本音響学会音声研究会資料Ｓ８１−６５　（１９８
１年１２月）に゛クロック同期伝播Ｄｒ法による連続音
声認識の検討′と題して発表された論文Ｃ以下文献（３
）と呼ぶ）」に記載されている効率良い連続単語認識ア
ルゴリズＣ以下クロックワイズｌ）Ｐ法と略称）が実行
できないという難点があった。

本発明の目的は、従来のスタックＤＰマツチングと同等
の機能を有しながら所要メモリが少なくかつクロックワ
イズＤＰ法への組込みにも適したパターンマツチング装
置を実現することにある。

本発明によるパターンマツチング装置は、特徴の時系中
に分岐や省略を制御する制御子を含んで成る標準パター
ンを供給する手段と、入カバターンたる特徴の時系列を
供給する手段と、上記入カバターンの特徴と標準パター
ンの特徴との間の距離を算出する距離計算部と標準パタ
ーンの時系列中の特徴の位置に対処・シて番地指定され
るワークメモリと、このワークメモリより読み出される
複数個の数値と前記距離とにもとづいてＤＰマツチング
順化式の計算を行う順化式計算部と一制御子とその出現
位置をプツシ−／ボ、７プするためのスタックと、制御
子が入力された場合、その種類に応じて前記スタックを
ブツシュ／ボ、ブし、かつ前記漸化式計算部で実行する
ＤＰマツチング漸化式を制御するスタック処理部とより
構成される。

以下に図面を参照しながら実鴫例にもとづいて本発明の
原理と構成を詳述する。

第１図は本発明の一実施例を示すブロック図である。こ
の装置は制御部２０よりのアドレス信神クロックパルス
等の制御のもとに動作するが、Ｍ中には説明のために必
要な制御信号のみを示している。

音声入カバターンは前記特願昭４５−５３８９６号明細
書（特公昭５０−２３９４１号公報）の場合と同様に特
徴ベクトルａｉの時系列として、 Ａ−ａｍ、ａ２・・・・・・・・・・・−・・山・・・
・・・・・・・・・・・・・・・・・・ａ（１）■ と記述されているとする。第２図に示すようにとのよう
な特徴ベクトルａｉが順次、このパターンマツチング装
置に与えられるとする。標準パターン記、ｔＸ１部２０
には認識対象となる単語ごとに標準１＜ターンが記憶さ
れる。いま、単語に番号ｎをつけて指定することとし、
Ｎ　ｇの単語セット、！　−（ｎ　Ｉ　ｎ　−１，２，
・−−−−・・・・−・Ｎ’ｊ　（２）を考えることと
する。単ｉｎには標準パターンＢ−ｂ１．ｂ、・・・・
・・・・・・・・ｂ・・・・・・・・・・・・・ｂｊｒ
：、　（３）が記憶される。なお、標準パターンを一般
的に取扱うときには添字ｎを省略して、 Ｂ−ｂ、、ｂ、・・・・・・・・・・・・ｂｊ・・・・
・・・・・・・・５丁　（４）なる表現を用いる。

この標準パターン中には特徴ｂｊの他に分岐や省略を示
す次のような制御子が含まれる。

分岐開始　１（′ 分岐区分　／〃 分岐縫子　゛）″ 省略開始　・〔・ 省略終了　〕“ これらの意味は、前記文献ｆｌ）、　（２）と同様であ
る。

例えば、 Ｂ　−ｂ１＋　ｂ、（ｂ、　ｂ、／ｂ、　ｂ、　ｂ７／
ｂ、　ｂ、　）ｂｌ。ｂｕ　Ｃｂｔｔ　ｂｔｓ　ｂｔｔ
：）　ｂｓｙ　（５）なる標準パターンにおいては、ｂ
、　ｂ４．　ｂ、　ｂ、　ｂ、　。

ｂ、　ｂ、の部分系列は、いずれか１個のみが選択され
る。また、部分系列ｂｔｔ　ｂｋｍ　ｂｌ４は省略され
てよい。

標準パターン記憶部２０の内部では、第３図のように表
現される。すなわち、各特徴ｂｊに付随して必要に応じ
て制御子が書き込まれている。メモリ８０け単語指定信
号ｎとアドレス信号ｊとによって番地指定され、Ｇ　ｆ
ｊ）なる値が記憶されるようになっている。

以下に本装置の動作を説明する。まず、最初の特徴ベク
トルａ１が入力されると単語指定信号ｎが１から３ｎま
で変化されるのに応じて、ｏ’１１＞−ｄ　（１，１）
（６） なる初期設定がなされる。ここにｄ（１，１）は、ベク
トルａ、とｂｌ１間のユークリッド距離である。

一般には、 ｄ（ｉ、　ｊ　）　−１１ａＩ−ｂ”ｊｌｌ　（７）と
定義される。この初期設定は文献（１）の（６）式と同
じ処理であって、公知であり、またそのための操作は簡
単なので詳細は省略する。

次に、一般的にベクトルａｉが入力された時の動作を第
２図を参照して説明する。

ａｉがベカされると、単語指定信号ｎが１からＮまで変
化される。単語指定信号が値ｎとなるとメモリ８０より
Ｇ？ｊ）がｊ−１からＪｎｔでワークメモリ５１にＧ、
（ｊ）として転写される。続いて、アドレス信号ｊが１
からＪ”まで順次カウントアツプされる。

とのｊとｎによって番地指定され前記標準パターン記憶
部２０より特徴ベクトルｂｊが信号線すに、また、この
ベクトルに付随する制御子信号が信号線Ｃに出力される
。

制御子が無かった場合には、順化式計算部５０で次のよ
うな通常のＤＰマツチング漸化式の計綽がすなわち、前
記ワークメモリ５１よりＧｌ（ｊ）。

Ｇｌ　（３−１）、Ｇｔ　（ｓ−２）としてｇ（ｉ−１
，ｊ　）、　ｇ（ｉ−］＋　ｊ−１）ｇ（ｉ−１，ｊ−
２）が読み込まれ、それらが比較され最小値が決定され
る。池方距離計算部４０では入力の特徴ベクトルａｉと
標準パターンのベクトルｂ二との１−クリット距離ｄ（
ｉ、ｊ）が算出され、信号ｄとして順化式計算部５０に
与えられる。この距離ｄ（ｉ、ｊ）前記の最小値と加算
される。かくして（８）式の計算が終了する。かくして
得られたｇ（ｉ、ｊ）はレジスタ５２にＧｔ（ｊｌとし
て記入される。かくの如き漸化式計算処理は特願昭５６
−１９９０９８号明細書の第１０図に示す回路構成によ
って実行できるが、ここでは同種の原理をマイクロプル
セッサによって実行することにする。かくの如く、制御
子が付いていないときは、（８）式の基本的な漸化式計
算を繰返される。このときのＤＰババス第６図＋３）に
参照数字１で示す如きである。

特徴ベクトルｂｊに制御子が付いて読み出されたときの
動作を第４図（ａｌ、　（ｂ）を引用して説明する。

制御子は信号ＷＪＩＣを経由してレジスタ６１に送られ
る。さらに信号線Ｃ１を経由してスタック制御部６３に
送られ、制御子の種類が判定される。スタック処理部６
０には、この他に制御子スタック６２とアドレススタッ
クとの２種が内蔵されており、それぞれ第５図（ａ）、
　（ｂ）のような構成になっている。制御子スタックは
、スタックカウンタにで番地指定され、アドレススタッ
クはスタックｌで番地指定される。

これらのカウンタの初期値は１である。

分岐開始制御子１（′が与えられると、スタック制御部
６３よ抄制御信号ＰＰＩ、　ＰＰ２が発生される。

その指示によって制御子スタック６２の策に番地に・（
・及びその時点での前記アドレス信号ｊとが書き込まれ
、アドレススタックの第１番地には前記アドレス信号ｊ
が書き込まれる。その後、ｋ＋１−に、ｔ＋１−ｚなる
ＰＵＳＨ処理が行われる。特徴ベクトルｂｊに対しては
（８）式の処理が行われる。

分岐区分制御子′／＃が検知されたときは、制御信号Ｐ
ＰＩの指示によってスタック６２の第に番地に・／・と
その時点のアドレス信号ｊとが書き込まれ、ｋ＋１−に
なるＰＵＳＨ処理が行われる。またスタック６４の第（
／−１）番地の内容が信号ｊ′として読み出される。ス
タック制御部６３は、この信号ｊ′を信号ｊｊとして順
化式計算部５０に転送する。

そこではこの信号ｊｊを基にして次のようなりＰ漸化式
処理が実行される。

この計算に必要な右辺のｇはワークメモリ５１より読み
出され、結果として得られるｇ（ｉ、ｊ）がワークメモ
リ５２に記入されるのは、（８）式の場合と同様である
。

ここで（９）式の意味を説明しておく。アドレススタッ
ク６４より読み出される信号ｊｊは、その直前に現われ
た分岐開始制御子“（′のアドレスｊの値である。した
がって（９）式の右辺にあるｇ　（ｉ−１，ｊｊ　）と
ｇ（１−１ｎ　ｊ　ｊ−１）の項は、分岐開始制御子゛
（・の直前から現在のアドレスｊへの接続を評価してい
ることになる。（５）式及び第３図の例の中でｊ−５に
おけるゾ・に対応しては、第６図に参照数字２で示すよ
うな漸化式が計算される。

すなわち、ｊ−２からの接続が評価されることになる。

ｊ−８に表われる分岐区分制御子に対しても同様な処理
が行われる。

次匿分岐終了制御子１）′が検出されたときの動作を説
明する。ｋ−１−にとして制御子スタック６２の第に＠
地より制御子とアドレス信号をＣｊとして読み出すとい
うＰＯＰ処理が行われる。

スタック制御部６０では制御子が判定され、分岐区分制
御子１／′であったならば前記のアドレス信号を信号Ｈ
として漸化式計算部５０に送る。この処理は分岐開始制
御子１（ｌが制御子スタック６２から読み出されるまで
繰返され、最後にｅ　−１−１！とアドレススタック６
４もＰＯＰされる。との間漸化式計算部５０では、ワー
クメモリ５１より読み出されるｇ（ｉ−１，３）とｇ（
＋−１，ｊ−１）、　ｇ（ｉ−１，ｊ−２）順次与えら
れる前記信号ｊｊに対応してワークメモリ５１から読み
出されるｇ（ｉ−１，ｊ　ｊ−１）、　ｇ（ｉ−１，ｊ
　ｊ−２）の群の最小値検出が行われ、最後に最小値に
ｄ（ｉ、ｊ）が加算される。すなわち、順次与えられる
ｊｊをｊｌｊ、・・・・・・・・・とするとき、 なる漸化式計算が行われる。（５）式及び第３図の例で
は、Ｊｚ、Ｉｔとしては、との゛）“の前に現れた／″
の位置に対応してｂ−８，Ｊｔ−５が読み出される。し
たがって、ｊ　−１０では、 なるＤＰ漸化式が計算されたことになる。すなわち、分
岐区分制御子１戸で分けられた３個の部分系列のいずれ
が最適かを決定したことになる。

なお、このときのＤＰババス第６図（ｂ）に参照数字３
で示すごときである。

省略開始制御子゛〔″が検出されたときは、制御信号Ｐ
Ｐｌの働きによって１〔″と現時点のアドレス信号ｊと
が制御子スタック６２の第に番地に書き込まれ、ｋ＋１
−にとするＰＵＳＨ処理が行われる。

ＤＰ漸化式としては（８）式が実行される。省略終了制
御子ゞ〕“が検出されたときは、ｋ−１−にとして制御
子スタックの第に番地より信号Ｃｊが読み出される。そ
のアドレス信号の部分が、スタック制御部６３によって
、信号Ｈとして漸化式計算部５０に転送される。そこで
は次の漸化式が計算される。

これによって、（ｊｊ＋１）から（ｊ−１）までの部分
系列を省略すべきか否かの判定が行われることになム（
５）式を第３図の例ではｊ−１５の点で第６図（ａ）に
参照数字１５で示すような漸化式が計算されることにな
る。

以上述べたスタック処理部６０と漸化式計算部５０での
処理を第４図に７四−チャードで示す。かくの如き処理
をｊ−１２，・・・・・・・・・・・・Ｊに対して行う
ことによってワークメモリ５２にＧ＊（ｊ）としてｇ（
ｉ、ｊ）がすべて得られる。この時点でワークメモリ５
２の内容Ｇ２（ｊ）は、メモリ８０にＧ”（ｊ）として
転写される。

単語ｎに対する上記処理はｎ−１，２・・・・・・・・
・Ｎなるすべての単語に対して実行される。この処理が
終了すると次の入力特徴ベクトルａｉオ、が入力され同
様の処理が繰返される。最後の入力特徴ベクトルａ工に
対する処理が終了した時点でＧ”（Ｊ’）として入カバ
ターンＡと標準パターンＢｒｌとの距離Ｄ（Ａ、Ｂ”が
得られる。

本パターンマツチング装置を音声認識システムとして用
いる場合には、この距離Ｄ（Ａ、Ｂ”）を比較してその
橢小となる単語名ｎを決定することによって認識処理が
達成される。

かくして標準パターン中に分岐や省略を許容する制御子
が存在する場合でも入力特徴ベクトルａｉの入力に同期
的にＤＰマツチング処理を実行できることになった。

本発明によると、前記特願昭５７−１５６４１３号明細
書の第８図に示されるごとき大容量なスタックメモリが
不要であり、かつ、パターンＡの入力が完了する以前に
、ａｉの入力に同期して処理が実行できるという効果が
得られる。

以上、実施例に基づいて本発明の詳細な説明したが、ど
れらの記載は本発明の権利範囲を限定するものではない
。

例えば、本実施例ではａｉとｂｊと。類似性を距離ｄ（
ｉ、ｊ）で評価したが、相関のように距離と大小関係が
逆の量を用いてもよい。その場合には（８）式等の最小
値選択操作を最大値選択操作に置換えれば本発明の原理
が、そのまま適用される。

また、距Ｍｄ（ｉ、ｊ）を直接計算せず、例えば「電子
通信学会誌ｖｏＩ！、　Ｊ６５−Ｄ、　Ｎｏ、８（１９
８２年８月）のＰ４Ｏ１０の図１に示される５ＰＬＩＴ
方式と同様にたプル参照方式によってもよい。この場合
には特徴ｂｊはベクトルではなく擬音韻を指定する奇岩
となる。

また、本発明によるパターンマツチング装置で処理の対
象とするパターンは音声に限定されるものではない。例
えば特願昭５７−１５６４１３号明細書の実施例の如く
オンライン文字認識の文字パター刈あってもよい。

制御子の定義とその具体的処理にも種々の変ルが考えら
れる。例えば、省略も一種の分岐と考えて、゛〔′や〕
″を用いず、゛（″と”）′の間に／″が無い場合け゛
（″と“）″で囲まれる部分は省略可能であると定義す
ることもできる。その場合も゛）″が出現したとき第７
図のフローチャートで示すような処理を行うことによっ
て、スタックによる制御が可能である。また、分岐処理
や省略処理は１）“や］＃で必ず閉じなければならない
という性質のものではない。例えば、 ・・・・・・・・・・・・（・・・・・・・・・・・・
／・・・・・・・・・・・・／・−・・・・・・・・・
・のように分岐した状態のままで終了させ、３種の分岐
の結果を並列に外部に出力するようにしてもよい。

また、本パターンマツチング原理を前記特願昭５６−１
９９０９８号明細書の第７図のＤＰマツチング部１６０
に組み込んで連続音声認識装置を実現することができる
が、そのような応用でもＤＰマツチング部に関しては本
発明の権利範囲に含まれるものである。

また、（８）式のＤＰ漸化式のかわりに、例えば、ＩＥ
ｇＢ　ＴＲＡＮＳＡＣＴＩＯＮ　ＯＮ　ＡＣＯＵ８ＴＩ
Ｃ８５ＰＥＥＣＨＡＮＤＳＩ■ＫＬ　ＰＨ□ＣＥＳ８Ｉ
ＮＧ、　Ｖａｔ、　ＡＳＳＰ−２６，Ｎｏ、　１のＰｄ
２に示されるような種々の漸化式を用いてもよい。

【図面の簡単な説明】

第１図は本発明の実施例ブロック図であり、第２図から
第７図は、その動作説明図である。 図中、１０は制御部、２０は標準パターン記憶部４０は
距離計算部、５０は漸化式計算部、５１はワークメモリ
、６０はスタック処理部、６１はレジスタ、６２は制御
子スタック、６３はスタック制御部６４はアドレススタ
ック、５２はワークメモリ、８００　仁　−一 ７５図 オ６図 （Ｑ）　（１）） １−１　１　１−１　１ 手続補正書（自発） ５Ｄ、１０．−４ 特許庁長官　殿 １、事件の表示　昭和５８年　特許　願第１３１４３８
号２、発明の名称　パターンマッチンク装置３、補正を
する者 事件との関係　出　願　人 東京都港区芝五丁目３３番１号 ４、代理人 〒１０８　東京都港区芝五丁目３７番８号　住友三田ビ
ル５、補正の対象 ｔ「アルゴリズム」と訂正する。 （３）同憂同頁に「−制御子」とあるのを「制御子」と
訂正する。 のをｒｙ（ｆ−ｘ、３）Ｊと訂正する。

Claims (1)

【特許請求の範囲】
1. 特徴の時系列中に分岐や省略を制御するための制御子を
   含んでなる標準パターンを供給する手段と入カバターン
   たる特徴の時系列を供給する手段と、上記入カバターン
   の特徴と標準パターンの特徴との間の距離を算出するた
   めの距離計算部と標準パターンの時系列中の位置に対応
   して番地指定されるワークメモリと、このワークメモリ
   より読み出される複数個の数値と前記距離に基づいてＤ
   Ｐマツチング漸化式の計算を行う漸化式計算部と制御子
   とその出現位置をブツシュ／ポツプするためのスタック
   と制御子が検知された場合、その種類に応じて前記スタ
   ックを操作し、かつ前記漸化式計算部で実行するＤＰマ
   ツチング漸化式を制御するスタック処理部とより構成さ
   れることを特徴とスルパターンマツチング装置。