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

Abstract

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

Description

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

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

音声パターンは特徴の時系列として表現され、このよう
なパターン間の比較処理、すなわちパターンマツチング
を行って音声認識を行う方法が広く行われている。高精
度な認識のためにはパターン変動に対して安定な、すな
わちパターン変動吸収能力の高いマツチング手法が必要
とされる。時間方向の伸縮歪に対しては特願昭４５−５
３８９５号明細書（特公昭５０−２３９４１号公報）に
記載された動的計画法（Ｄｙｎａｍｉｃ　Ｐｒｏｇｒａ
ｒｒｍｉｎｇ、以下ＤＰと略す）を用いたＤｒマツチン
グ法が適用され効果が得られている。

しかし、実際の音声パターンには、時間伸縮以外に、例
えば「日本音響学会音声研究会資料８８３−２５（１９
８３年６月）に　１連続音声中の母音の変形について“
　と題して発表された論文」に記載されている如く、長
音化、鼻音化、無声化、脱落のように局所的な変形が生
じる。しかもこれらの現象は発声速度や感情などの要因
に応じて不確定的に発生するものである。

このような変形に対処し得るＤＰマツチング法が同一出
願人より昭和５８年７月１９日に出願の［パターンマツ
チング装置」の明細書（文献（１・）とする）に記され
ている。それによると、標準パターンは特徴の時系列中
に分岐を指示するだめの゛カッコ“　形式の分岐制御子
を用いている。この分岐制御子で囲まれた部分は、いく
つかの選択が可能であるとするとか、省略可能であると
するとかの制御が可能であるとしている。しかしこの方
法では、゛カッコ″　が矛盾なく現れることを要請して
いたため、標準パターンで記述できる変形の範囲が狭か
った。簡明な例を次に示す。いま特徴の時系列中の一部
に次の３通りの変形が許されるものとする。

・・・・・・・ａｌｌ）、０％　ｄ・・・・・・パ・・
・　ｔ・・・・・・・・ｅ％ｆ、ｈ％　ｄ　・・・・・
−・・・・　・。

このような変形を［前記文献（１）」の分岐制御子で表
現すると −・・・・・（ａ　ｂ　ｃ　ｄ／ｅ　ｆａｔ　ｓ／（ｇ
ｃ／ｈ）ｄ）ｌ　（２１となる。ここに　１（“　と　
１　）”　はその中に囲まれてかつ　′／“　で区切ら
れる時系列のいずれかを選択することを意味し、入れる
形式で使用することができる。

（２）式の標準パターンには第１図のようなオートマト
ン表現が対応する。しかし、このオートマトンは簡略化
が可能であって、第２図のオートマトンがよシ簡単でか
つ同値なものである。第１図は１０状態を要していたの
に対して、第２図では８状態で記述されている。すなわ
ちカッコ形式で分岐を表現していた従来方法では、時と
して冗長な形式となり、標準パターン記憶のだめのメモ
リーが多く必要とされ、またそれを処理するための演算
量も多いという欠点があった。

甘だ、分岐制御子は、　′　（“　が先に現れてから　
“）“　が出現するという制限があり、このためループ
を含んだオートマトンを表現できないという欠点もあっ
た。

本発明の目的は一般的なオートマトン形式で表現される
標準パターンを効率良＜Ｄ、Ｐマツチング処理できるパ
ターンマツチング装置を実現することにある。

本発明によるパターンマツチング装置は、特徴の時系列
中に番地情報を含んでなる標準パターンを供給する手段
と、入カバターンたる特徴時系列を供給する手段と、複
数個の数値を記憶するワークメモリと、ワークメモリよ
り読み出される数値にもとづいてＤＰマツチング漸化式
を計算する漸化式計算部と、前記番地情報と前記漸化式
計算部用力とにもとづいてワークメモリよりの読み出し
番地を制御する手段とを含んで構成される。

以下に実施例を示す図面を引用して本発明の原理を詳述
する。

第３図は本発明の一実施例を示すブロック図である。標
準パターン記憶部２０には第４図の形式の標準パターン
が記憶される。すなわち特徴の時系列 ｂ１ｂ２・・・・・−・−・−・・ｂ　・・−・−・−
・−・−ｂ　（３１Ｊ　Ｊ の中に必要に応じて番地情報Ｃが埋め込まれている。　
いま−例として Ｂ＝ｂ］　−ｂ２　ｂ４　ｂ４（２）、ｂｓ・・・・・
・・・〔す〔８〕〔１２〕ｂ１３・・・・・ｂ。

（４） なる標準パターンを考える。０内の数値が番地情報であ
る。第４図では、最上位ビットがＯであるか１であるか
によって特徴と番地情報の区別を行っている。（４）式
の標準パターンは第５図のオートマトンに対応する。

以下に本パターンマツチング装置の動作を説明する。信
号線ａより入カバターンが Ａ＝ａｌ　ａｔ　・・・・・・・・ａｉ　・・・・・・
・・・ａｌなる特徴の時系列として与えられる。最初の
特徴が入力された時点でワークメモリ５０に初期設定動
作がなされる。このワークメモリは制御部１０よりのア
ドレス信号ｊによって番地指定される。

Ｇ（１）　（３（２１・・・・・・・・・（’ｄｊ）・
・・・・・・・・Ｇ（Ｊｌ、・　（５）Ｇ’　（］ｌ＋
　Ｇ’　（２）・・・・・・・・・Ｇ’（ｊ）・・・・
・・・・Ｇ’　（Ｊ）なる記憶番地よりなっている。初
期条件の設定はＱ１１番地に対して次の如く行われる。

（Ｊ）　＝　ｄ（１，ｌ）（６） これは前記文献（１）の（６）式に対応するもので、通
常のＤ　Ｐマツチングでの ｇ（１、ｊ）　＝　ｄ（１，１） なる初期設定に対応する。なお、ｄ（Ｉ、１）は特徴ａ
１　七ｂｊとの距離である。

制御部１０にはカウンター（とｊ（とが内蔵されている
。これらは特徴ａ　が与えられるごとにに−１，Ｊ　１
；１とリセットされる。また、別に制御フラグｆが内蔵
されており、ａ　が入力される鵞 とｆ＝０なる初期値にリセットさｎ、る。ＪＪ後カウン
タｋがＪから順次カウントアツプされる。このｋの値は
前記の標準パターン記ｆ２部２０にアドレス信号１（と
じて送られる。このアドレス信号に応じて（４）式の標
準パターンがハ追次伯月Ｘとして読み出され、デコーダ
３０で特徴か指地情報かが検定される。

信号アが特徴ｂｊ　でかつ制御フラグが０であるときは
この信号は特徴すとし、て距離計算部４０に送られる。

そして次のような基本的なりＰ漸化式が計算される。

このだめ、制御部１０内のカウンタ信号ｊ１　をもとに
しでＪ及び（ｊ　−］　）か発生され伯七′ＩｄＪ□を
経由してワークメモリ５０に送られる。ワークメモリ５
０からは、このアドレス信号に対応して　−漸化式値Ｇ
（ｊｌ＝’ｇ（ｉ−１、Ｊ）とＧ（ｊ　−１）　＝　ｇ
（ｉ　−１゜ｊ−１）が出力され最少値検出部７０に送
られる。

イこではこれらの値が比較され、ｚｌ□７：ｃる方の値
がｇ２　として出力される。他方、距離計鉋部４０では
入カバターンの特徴ａ　と標準パターンの特徴＋１Ｊ　
のｆｉｊで距離ｄ（ｉ、ｊ）が割算されイｄ号ｄとして
出力される。加算器６０ではこの信”１５’　ｄと前記
信号ｇ２　との和が計算される。かくして（７）式のｇ
（ｉ、」）が計算されたことになる。この値は信号？ｉ
１ｇＢ　を経由してワークメモリ５０に送られＧ′Ｕｌ
＝ｇ　（ｉ、ｊ　）として書き込まれる。

以上の漸化式計算の後、制御部１０内のカウンタｋ及び
」１は１だけカウントアツプさハる。また制御フラグｆ
はＯのままである。

（４）式の標準パターンの〔２〕なる番地情報が読み出
されたときは、この信号はデコーダ３０から制御部ＪＯ
へ送られる。こねを受けて制御部１０からはｊ２−２な
るアドレス信号が発生されワークメモリ５０に送られる
。これによりワークメモリ５０からはＧ（２）＝　ｇ（
ｉ　−１，２）が読み出され最小値検出回路７０に送ら
れる。その後制御部１０内のカウンタにのみが１だけ増
加される。また制御フラグｆは１にセットされる。

番地情報〔２〕に続いて特徴ｂ５が入力されたときは、
ｆ＝１となっているので（力式とは異なった処理が行わ
れる。制御部１０ではカウンタ信号ｊ１＝５を信号線ｊ
２　に供給する。これを受けてワークメモリ５０よシ漸
化式値（３４５）　＝　ｇ　（ｉ　−１，５亦出力され
る。最小値検出部７０ではこの値と、先に人力されたＱ
（２）　＝　ｇ（ｉ−１，５）とが比較され小なる方の
値が信号ｇ２　として出力される。一方距離計算部４０
では人力の特徴ａ、と標準パターンの特徴ｂ５　との距
離ｄ＝ｄ（ｉ、５）がｎ出される。

この信号ｄとｆｆ２が加算され なる値が得られる。この値はＧ’　（５１：　＝　ｇ（
ｉ、　５）としてワークメモリ５０に書き込まれる。そ
の後制御部１０内のカウンタにとｊｚ　は１だけカウン
トアツプされ、制御フラグｆＶｉｏにリセットされる。

以上によって第５図の状態２から状態５への分岐が評価
されたことになる。

同様にして、（４）式の〔４〕、〔８〕、〔１２〕、ｂ
１３　の部なる漸化式が計算される。すなわち、番地情
報〔４〕〔８〕、〔１２〕に応じてＧ（４）＝　ｇ（ｉ
　−１，４）、Ｑ８１　＝　ｇ（ｉ〜１．８）、Ｇ（１
２）＝ｇ（ｉ　−１，１２）がワークメモリ５０より読
み出され、ｂ１３が人力された時点でＧ（１３）　＝　
ｇ（ｉ−１，１３）が読み出さする。最小値検出部７０
ではこれらの最小値が計算され、距離計算部４０より出
力されるｄ　＝ｄ（ｉ、　１３）と加算される。

一般に〔Ｃ］〕、（Ｃ２）　−−−−−−−（ｃｍ）ｂ
（ｎＪ なる標準パターンの系列が与えられたときは、なる漸化
式が計算される。

かくして標準パターンの特徴ｂＪ　まですべて処理が終
了するとげ（」）→Ｑｊ）なる転写が行われる。

次にａＩ＋１が入力され、ａｌ　に対するのと同様の処
理が繰返される。最後にａ工に対する処理が終ると入カ
バターンＡと標準パターンＢとの距離がＤ（Ａ、Ｂ）　
二〇’　（Ｊ） とし、て得られる。

かくの如き構成によると（１０）の（Ｃ）に帯地情報を
設定することにより、自由な分岐を表現することができ
、かつ入カバターンとのマツチングを極めて効率良く実
行することができるという効果が得られた。

以上本発明の原理を実施例にもとづいて説明したがこれ
らの記載は本発明の権利範囲を限定するものではない。

特に、基本的なりＰ漸化式としては（７）式以外のもの
が用いられることがあるが、その場合でも本発明の原理
は適用できる。例えばよく用いられる を（７）式として用いる場合には、（１１）式のかわり
になる漸化式を用いることかで衰ノシ、：また最小値検
出部７０とワークメモリ５０の構成に関しても種々の変
形が考えられる。以上のように本発明によれば比較的演
算量も少なく効率的なりＰマツチング装置を得ることが
出来その効果は大なるものがある。

【図面の簡単な説明】

第１図、第２図は原理説明図、第３図に本発明の一実施
例を示すブロック図、第４図と第５図は捕捉説明図であ
る。 図において１０は制御部、２（）は標準パターン記憶部
、３０はデコーダ、４０は距離計算部、５０はワークメ
モリ、６０は加算器、７０は最小値検出部をそれぞれ示
す。 手続補正書（台企） 特許庁長官　殿 １、事件の表示　昭和５８年　特許願第１８５４０２号
２　発明の名称　パターンマツチング装置３、補正をす
る者 事件との関係　−出　願　人 東京都港区芝五丁［−１３３番１汀 （４２３）　日本電気株式会社 代表者　関本忠弘 ４、代理人 （連絡先　１１本電気株式会社特許部）５、補正の内容 明細書の特許請求の範囲の欄。 明細書の発明の詳細な説明の欄。 ６　補正の内容 １）特許請求の範囲を別紙のとおり補正する。 ２）明細書第５頁第１０行目から第１１行目に「・・・
・・・情報と前記漸化式計算部出力とにもとづいて・・
・・・・」とあるのを「・・・・・・情報にもとづいて
・・・・・・」と補正する。 （別紙） 特許請求の範囲 特徴の時系列中に番地情報を含んでなる標準パターンを
供給する手段と、入カバターンたる特徴時系列を供給す
る手段と、複数個の数値を記憶するワークメモリと、ワ
ークメモ−りより読み出される数値にもとづいてＤＰマ
ツチング漸化式を実行する漸化式計算部と、前記番地情
眠寥もとづいてワークメモリよシの読み出し番地を制御
する手段とを含んで構成されることを特徴とするパター
ンマツチング装置。

Claims (1)

【特許請求の範囲】
1. 特徴の時系列中に番地情報を含んでなる標準パターンを
   供給する手段と、人カバターンたる特徴時系列を供給す
   る手段と、複数個の数値を記憶すと、前記番地情報と前
   記漸化式計算部用力とにもとづいてワークメモリよりの
   読み出し番地を制御する手段とを含んで構成されること
   を特徴とするパターンマツチング装置。