JPS59200A - パタ−ンマツチング装置 - Google Patents
パタ−ンマツチング装置Info
- Publication number
- JPS59200A JPS59200A JP58105844A JP10584483A JPS59200A JP S59200 A JPS59200 A JP S59200A JP 58105844 A JP58105844 A JP 58105844A JP 10584483 A JP10584483 A JP 10584483A JP S59200 A JPS59200 A JP S59200A
- Authority
- JP
- Japan
- Prior art keywords
- register
- pattern
- distance
- route
- cumulative
- 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.)
- Pending
Links
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔発明の利用分野〕
本発明は音声入力等のパターン認識システムに使用され
るパターンマツチング装置に関するものである。
るパターンマツチング装置に関するものである。
るために、あらかじめ記憶した各種の標準パターンと入
カバターンを比較して認識を行うパターンマツチング法
が用いられている。例えば音声認識では、標準パターン
として、認識したい単語分の標準パターンを記憶して用
いる。
カバターンを比較して認識を行うパターンマツチング法
が用いられている。例えば音声認識では、標準パターン
として、認識したい単語分の標準パターンを記憶して用
いる。
このような音声認識等において、パターンマツチング法
を用いるとき問題になるのは、入力音声が発声毎に時間
軸に対して任意に伸縮することである。すなわち、同一
の話者が同一の単語を発声しても、全く同じ長さに発声
できない。したがって標亭パターンとのマツチングにお
いで１記憶された標準パターンが入力音声を発声した、
話者であっても１発声速度が任意に変化するため類似度
が発声毎に変化し、正しい認識結果が得られない。
を用いるとき問題になるのは、入力音声が発声毎に時間
軸に対して任意に伸縮することである。すなわち、同一
の話者が同一の単語を発声しても、全く同じ長さに発声
できない。したがって標亭パターンとのマツチングにお
いで１記憶された標準パターンが入力音声を発声した、
話者であっても１発声速度が任意に変化するため類似度
が発声毎に変化し、正しい認識結果が得られない。
この人カバターフと標準パターンの時間軸のずれを整合
しながらマツチングを行う方法きして、動的計画法（以
下１３Ｐと略す。）が広く用いられている。次にＩＪ
Ｐについて説明する。
しながらマツチングを行う方法きして、動的計画法（以
下１３Ｐと略す。）が広く用いられている。次にＩＪ
Ｐについて説明する。
音声パターンＡは、特徴ベクトル”１１、”２１％”ｍ
ｌ ・・、”ｎｌ ）の時系列として、Ａ＝ａａ
ａ−１ａｓ−１ａ ｆｌ）１ ２％
３ １ Ｉと表わさ
れる。この特徴ベクトルａｌは、音声信号を１個の区間
に区切ったときの１市目の区間のけ声のｉｎ徴ベクトル
であり、特徴ベクトルきしては、たきえは中心周波数の
異なったｎ個の帯域フィルタ１序の出力が考えられる。
ｌ ・・、”ｎｌ ）の時系列として、Ａ＝ａａ
ａ−１ａｓ−１ａ ｆｌ）１ ２％
３ １ Ｉと表わさ
れる。この特徴ベクトルａｌは、音声信号を１個の区間
に区切ったときの１市目の区間のけ声のｉｎ徴ベクトル
であり、特徴ベクトルきしては、たきえは中心周波数の
異なったｎ個の帯域フィルタ１序の出力が考えられる。
”＋ｎｌとは音声の１番目の区間の帯域フィルタｎ （
Ｎ中のｍ番目のフィルタ出勾である。人力音声パターン
Ｘ１標準行声パターンＹは特徴ベクトルの時系列として
、Ｘ＝Ｘ、、Ｘ２．Ｘ３．、、、、、Ｘ、、、、、、、
Ｘ□）・（２） Ｙ’−Ｙ１＋ Ｙ２ ＋ ”３ ＋ ”’ ＋ ＹＨ＋
”’ ＋ Ｙｌここで、入カバターンＸｓ ｍ準パタ
ーンＹＯ）＠似度を求めるため、両特徴ベクトルの距離
を求める必要があり、距離ｄは例えば、ユークリッド距
離として、 （Ｄ、ｉ ＋ ｊ）−（Ｘ、−Ｙ、 ）”’ 、ｉ（ｘ
、、−ｙ、、 ）”（３） で求められる。仮に入カバターンＸと標準パターンＹの
時間軸の伸縮がほとんど無いとすると、類似度Ｓは、距
離ｄの総和として、 Ｓ−（Σ（Ｘ、 −Ｙ、 ）２）／ｍ −（Σｄ（ｍ、
ｍ））／ｍ・・・（４） として求められる。Ｓは小さいほど、類似度が高い。す
なわち、良く似たパターン（単語）である。
Ｎ中のｍ番目のフィルタ出勾である。人力音声パターン
Ｘ１標準行声パターンＹは特徴ベクトルの時系列として
、Ｘ＝Ｘ、、Ｘ２．Ｘ３．、、、、、Ｘ、、、、、、、
Ｘ□）・（２） Ｙ’−Ｙ１＋ Ｙ２ ＋ ”３ ＋ ”’ ＋ ＹＨ＋
”’ ＋ Ｙｌここで、入カバターンＸｓ ｍ準パタ
ーンＹＯ）＠似度を求めるため、両特徴ベクトルの距離
を求める必要があり、距離ｄは例えば、ユークリッド距
離として、 （Ｄ、ｉ ＋ ｊ）−（Ｘ、−Ｙ、 ）”’ 、ｉ（ｘ
、、−ｙ、、 ）”（３） で求められる。仮に入カバターンＸと標準パターンＹの
時間軸の伸縮がほとんど無いとすると、類似度Ｓは、距
離ｄの総和として、 Ｓ−（Σ（Ｘ、 −Ｙ、 ）２）／ｍ −（Σｄ（ｍ、
ｍ））／ｍ・・・（４） として求められる。Ｓは小さいほど、類似度が高い。す
なわち、良く似たパターン（単語）である。
先に述べたように、音声等の場合は、時間軸での伸縮が
大きいため、前の（４）式では正確に類似度Ｓを求める
ことができない。したがってｌ）Ｐでは、次のように時
間軸を整合しながらＳを求める。第１図に時間軸−Ｆて
の入カパターノＸお標準パターンＹの整合の祠程を示し
、第２図の人カバターンＸ％標準パターンＹを縦座標、
横座標に変換したものを示１−０第２図の矢印で示す経
路で距離を求めながら、類似度Ｓを求めると、 ” Ｓ＝ （ｒｌ（］ 、 １ ）＋ｒｌ（２，２）＋
ｄ（２，３）＋・・＋ｄ（８，７））／９ ・・・（５
） が求められる。
大きいため、前の（４）式では正確に類似度Ｓを求める
ことができない。したがってｌ）Ｐでは、次のように時
間軸を整合しながらＳを求める。第１図に時間軸−Ｆて
の入カパターノＸお標準パターンＹの整合の祠程を示し
、第２図の人カバターンＸ％標準パターンＹを縦座標、
横座標に変換したものを示１−０第２図の矢印で示す経
路で距離を求めながら、類似度Ｓを求めると、 ” Ｓ＝ （ｒｌ（］ 、 １ ）＋ｒｌ（２，２）＋
ｄ（２，３）＋・・＋ｄ（８，７））／９ ・・・（５
） が求められる。
このような経路の選択は次のようにして行なわれる。
すなわち、いま、第３図の点Ｅ（ｉ、ｊ）に至るまでの
距離ｄの累オ［１をＤ（ｉ、ｊ）、その点Ｅ（ｉ、ｊ）
までの経路長をＬ（ｉ 、 ｊ ）とすれば、その点Ｅ
（ｉ、ｊ）にＦ”（ｉ、ｊ−１）、Ｇ（ｉ−１，ｊ−１
）、Ｈ（ｉ−１，ｊ）からそれぞれ判った時の次の（６
）式の値を求め、その頃が最小であるものの経路を選び
、その値を、累卵Ｌ）（ｉ。
距離ｄの累オ［１をＤ（ｉ、ｊ）、その点Ｅ（ｉ、ｊ）
までの経路長をＬ（ｉ 、 ｊ ）とすれば、その点Ｅ
（ｉ、ｊ）にＦ”（ｉ、ｊ−１）、Ｇ（ｉ−１，ｊ−１
）、Ｈ（ｉ−１，ｊ）からそれぞれ判った時の次の（６
）式の値を求め、その頃が最小であるものの経路を選び
、その値を、累卵Ｌ）（ｉ。
］）および経路長Ｌ（ｉ、ｊ）として求める。
（１）（ｉ、ｊ−１）＋ｄ（ｉ、ｊ））／Ｌ（ｉ、ｊ〜
１）＋１（Ｌ）（ｉ−１，ｊ−１）＋ｗｄ（ｉ、ｊ）ｌ
／Ｌに−ｉ、ｊ−ｘ）＋、ｔ（Ｄ（ｉ−１，ｊ）＋ｄ（
ｉ、ｊ）／Ｌ（ｉ−１，ｊ）弓（６） なお、初期値Ｄ（１，ｌ）、Ｌ（１，１）は次のように
表わされる。
１）＋１（Ｌ）（ｉ−１，ｊ−１）＋ｗｄ（ｉ、ｊ）ｌ
／Ｌに−ｉ、ｊ−ｘ）＋、ｔ（Ｄ（ｉ−１，ｊ）＋ｄ（
ｉ、ｊ）／Ｌ（ｉ−１，ｊ）弓（６） なお、初期値Ｄ（１，ｌ）、Ｌ（１，１）は次のように
表わされる。
１）（１，１）＝ｄ（１，１）
） ・（７）
Ｌ（１、１）−１
本（６）式は次式の制約で行なわれる。
１＜ｉく１．１＜ｊくＪ
） ・・（８）
ｊ−ｒ＜ｉくｊ＋ｒ ｒ雷整数
ｒは入カバターンＸ々標準パターンＹの時間軸の変化を
整合するときの範囲を決めるもので、ｒを大きくすると
、広範囲に長さの異った入カバターンと標準パター７の
整合を行う。しかし、ｒが太きいき処理量が増加してし
まう。第２図の場合は、ｒ＝３で、整合ができることを
示している。
整合するときの範囲を決めるもので、ｒを大きくすると
、広範囲に長さの異った入カバターンと標準パター７の
整合を行う。しかし、ｒが太きいき処理量が増加してし
まう。第２図の場合は、ｒ＝３で、整合ができることを
示している。
第２図において、最終的な類似度Ｓは、累卵Ｄ（８，９
）と経路長Ｌ（８，７）によって、Ｓ−１）（８，７）
／Ｌ（８，７） ・・・（９）と求められ、こ
れは（５）式となる。
）と経路長Ｌ（８，７）によって、Ｓ−１）（８，７）
／Ｌ（８，７） ・・・（９）と求められ、こ
れは（５）式となる。
このように点（’、Ｊ）における値Ｄ（ｉ、ｊ）、Ｌ（
’＋ｊ）を求めるためには、（６）式に示すように、前
回までに求められた隣接点の値Ｄ（ｉ、ｊ−１）、Ｄ（
ｉ−１，ｊ−１）、Ｄ（ｉ−１，ｊ）およびＬ（ｉ 。
’＋ｊ）を求めるためには、（６）式に示すように、前
回までに求められた隣接点の値Ｄ（ｉ、ｊ−１）、Ｄ（
ｉ−１，ｊ−１）、Ｄ（ｉ−１，ｊ）およびＬ（ｉ 。
ｊ−１）、Ｌ（ｉ−１，ｊ−１）、Ｌ（ｉ−ｉ 、 ｊ
）を利用する必要があるが、従来は、このような値を
メモリに記憶しておき、必要な時に、それらを−々読み
出して利用する方法が考えられている。
）を利用する必要があるが、従来は、このような値を
メモリに記憶しておき、必要な時に、それらを−々読み
出して利用する方法が考えられている。
しかしながら、このように、必斐に応じてメモリから読
み出すようにした場合、１点における値り、Ｌを求める
のに６回もデータの読み出しを行なわなければならず、
演算時間が非常に長くなるばかりか、これらのデータ読
み出しのための制御回路がａｍになるという問題があっ
た。
み出すようにした場合、１点における値り、Ｌを求める
のに６回もデータの読み出しを行なわなければならず、
演算時間が非常に長くなるばかりか、これらのデータ読
み出しのための制御回路がａｍになるという問題があっ
た。
本発明の目的は、１）Ｐによるパターン類似度の演算を
高速かつ、簡単な構成で行なえるようにしたパターンマ
ツチング装置を提供することにある。
高速かつ、簡単な構成で行なえるようにしたパターンマ
ツチング装置を提供することにある。
このような目的を達成するために、本発明では、所定計
算点における入力パターンサ樟準パターンとの距離を格
納する第１のレジスタと、この距離の上記計算点までの
累卵および経路長を格納する第２および第３のレジスタ
と、第１〜第３のレジスタの内容により、次の計算点に
おける経路毎の距離の累卵および経路長を計算する第１
の計算手段さ、この手段で求めた値を格納する第４のレ
ジスタと、この第４のレジスタの内容から、次の計算点
に至る最適の経路を選び、その経路での距離の累オｌお
よび経路長を次の８１３！点の値として求める第２の計
算手段とを備えたパターンマツチング装置に特徴がある
。
算点における入力パターンサ樟準パターンとの距離を格
納する第１のレジスタと、この距離の上記計算点までの
累卵および経路長を格納する第２および第３のレジスタ
と、第１〜第３のレジスタの内容により、次の計算点に
おける経路毎の距離の累卵および経路長を計算する第１
の計算手段さ、この手段で求めた値を格納する第４のレ
ジスタと、この第４のレジスタの内容から、次の計算点
に至る最適の経路を選び、その経路での距離の累オｌお
よび経路長を次の８１３！点の値として求める第２の計
算手段とを備えたパターンマツチング装置に特徴がある
。
第４図は本発明によるパターンマツチング装置の一実施
例のブロック回路図を示す。本装置では、３つのモード
処理を行う。第５〜７図に３つの処理のそれぞれが使用
する部分のみの回路を第４図からＩＱきだして示す。
例のブロック回路図を示す。本装置では、３つのモード
処理を行う。第５〜７図に３つの処理のそれぞれが使用
する部分のみの回路を第４図からＩＱきだして示す。
第４１ン１において、 ４．６． ８は累卵りを格納
するレジスタである。その内、４．６はシフトレジスタ
であり、４には外部よりデータ（Ｄ）が入力される。８
（１外部・＼読み出しができるレジスタである。
するレジスタである。その内、４．６はシフトレジスタ
であり、４には外部よりデータ（Ｄ）が入力される。８
（１外部・＼読み出しができるレジスタである。
５．７．９はレジスタ４．６，８に対応する経路Ｊ、ｊ
Ｌを格納Ｊるレジスタである。１は、距離ｄを格納す
るレジスタ、１０は図示しないマルチプレクサに上りへ
釈されるレジスタ４，６．８のいづれかと同ト１′：に
図示されるマルチプレクサにより選ばれるレジスタ１．
２のどちらかの加算をする加算器であり、また、レジ
スタ出力をそのまま通］尚させる機能を有するものであ
る。１１は、レジスタ５．７．９のいづれかに１１ｒる
インクリメンタで、１２はインクリメンタ１１の出力の
逆数を取るＲ ＯＭである。３は加泗、器１０の出力と
ＲＯＭ１２の出力の乗■をする乗算器であり、その他に
加算器１０を通過したレジスタ１の内容に対してＷを乗
算する役目をする。レジスタ２は、レジスタ１の出力ず
なわちｄとＷの東算結贈を格納する。１３．１４．１５
は、乗遭器３の出力を格納するレジスタであり、レジス
タ１３．１５は直接乗算器３の出力を格納し、レジスタ
１４は１３との間でデ タシフトをする。１６はレジス
タ１３．１４Ｖ １５の大小を比較する比較器で、この
比較結果により、加算器１０とインクリメンタ１１の選
択を制御する。比較器１６は、レジスタ１３，１４．１
５の値が２つ以上同じときは、１４．１３．１５の順に
優先的に選ぶ。
Ｌを格納Ｊるレジスタである。１は、距離ｄを格納す
るレジスタ、１０は図示しないマルチプレクサに上りへ
釈されるレジスタ４，６．８のいづれかと同ト１′：に
図示されるマルチプレクサにより選ばれるレジスタ１．
２のどちらかの加算をする加算器であり、また、レジ
スタ出力をそのまま通］尚させる機能を有するものであ
る。１１は、レジスタ５．７．９のいづれかに１１ｒる
インクリメンタで、１２はインクリメンタ１１の出力の
逆数を取るＲ ＯＭである。３は加泗、器１０の出力と
ＲＯＭ１２の出力の乗■をする乗算器であり、その他に
加算器１０を通過したレジスタ１の内容に対してＷを乗
算する役目をする。レジスタ２は、レジスタ１の出力ず
なわちｄとＷの東算結贈を格納する。１３．１４．１５
は、乗遭器３の出力を格納するレジスタであり、レジス
タ１３．１５は直接乗算器３の出力を格納し、レジスタ
１４は１３との間でデ タシフトをする。１６はレジス
タ１３．１４Ｖ １５の大小を比較する比較器で、この
比較結果により、加算器１０とインクリメンタ１１の選
択を制御する。比較器１６は、レジスタ１３，１４．１
５の値が２つ以上同じときは、１４．１３．１５の順に
優先的に選ぶ。
本装置の動作を、第２図のｒ＝３の場合を用いて説明す
る。今累卵Ｄ（ｉ−２，ｊ−１）、Ｄ（ｉ−１、ｊ−１
）、Ｄ（ｉ、ｊ−１）と、これに対応する各部分和経路
長Ｌ（ｉ−２，ｊ １）、Ｌ（ｉ−１゜ｊ−１）、Ｌ
（’ｌＪ ’）が求められているとする。
る。今累卵Ｄ（ｉ−２，ｊ−１）、Ｄ（ｉ−１、ｊ−１
）、Ｄ（ｉ、ｊ−１）と、これに対応する各部分和経路
長Ｌ（ｉ−２，ｊ １）、Ｌ（ｉ−１゜ｊ−１）、Ｌ
（’ｌＪ ’）が求められているとする。
まずＤ（” ＩＩ）、Ｌ（ｉ−１，ｊ）を求める。
第６図の処理は、距１１ｉｄをレジスタ１に人力するこ
とにより起動される。具体的にはｄ（ｉ−１゜Ｊ）をレ
ジスタに入力すると、第６図（ａ）ζこより、レジスタ
２にｗ−ｄ（ｉ−１，ｊ）が格納される０ここで１）（
ｉ ＝１．ｊ）、Ｌ（ｉ−１，ｊ）は、 ３つの最小値
ではなく、 （Ｄ（ｉ−２，ｊ −１）＋ｗｄ（ｉ −１、ｊ ）／
Ｌ（ｉ−２，ｊ−１）＋１０１ｉｎ［］）１ （ＩＣ（ｉ −１、ｊ−１）＋ｄ（ｉ −１、ｊ ］／
Ｌ（ｉ−１、ｊ −１）＋１・ （１０） の２つの最小値より求める。したがって、この最下端の
点の演算のみ第５図の処理を用いる。第５図の処理は、
累卵りと経路長りをレジスタ４．５に入力するこ乏によ
り起動され、る。レジスタ４．５に１）（’ ２．Ｊ
１）ｓ Ｌ（＋ ２．Ｊ １）を入力するＬｌ
レジスタ】３．１５に （１）（ｉ−２，ｊ−１）＋ｗ−ｄ（ｉ−１，Ｊ））／
Ｌ（ｉ ２．ｊ １）”１・（１１） が格納される。次に第７図（こより（Ｊ（ｉ −１、ｊ
−１）、ｒ、（！−ｔ、ｊ １）をレジスタ４．５に
入力する。第動され第７図ｔａ＋て、レジスタ４．５
（’） ｊ（’ｓｌｔよ、レジスタ６．７に格納ざイす
る。レジスタｌ Ｉには、（Ｄ（ｉ−１，ｊ−１）＋ｒ
ｌ（ｉ−１，ｊ）ｌ／Ｌ（ｉ−１，ｊ−１）＋１・・（
１２） が入力され、レジスタ１３に格納されていた値は、レジ
スタ１４に格納される。比紋器１６は、このレジスタ１
３，１４．１５の内最小（こなる値を有するレジスタを
検出し、第７図（１））のよう（こ１）（ｉ−１、ｊ）
、Ｌ（ｉ−１，ｊ）を計算し、レジスタ８．９に格納す
る。すなわち、レジスタ１３が選ばれると、レジスタ９
、分子をレジスタ８番こ格納し、レジスタ１４が選ばれ
たときは、レジスタ６．２．１４、−４５は同１直とな
るため、レジスタ１５は選択されず、レジスタ８．９は
選ばれない。この結果レジスタ８．９よりＤ（ｉ−司、
Ｊ）、Ｌ（ｉ−１゜ｊ）が取り出すこきができる。次に
Ｄ（ｉ、ｊ）、１ｉ （１＋ Ｊ ）を求めるには、同
様に第６図の処理により、（１（ｉ、Ｊ）をレジスタ１
に格納する。第１図（ａｌではレジスタ２に、ｗ −ｄ
（ｉ 、 ｊ ）が格納され、第６図（ｂｌでは （Ｄ（ｉ−１，ｊ）＋ｄ（ｉ、ｊ））／Ｌ（ｉ−１，Ｊ
）＋１（１３） が計ｐされ、レジスタ１５に格納され、第６図（Ｃ）で
、 （”ｌ−１１Ｊ ’）＋Ｗｄ（’＋Ｊ月／Ｌ（ｉ−１，
ｊ−１）＋１（１４） がバＨｉ＋されレジスタ１３に格納される。次に第７図
の処理を用いてＩ）（ｉ、ｊ−１）、Ｌ（ｉ 、 ｊ−
１，）を人力すると、図７（ａ）で、 （ＩＸｉ、ｊ−１）＋ｄ（ｉ、ｊ））／Ｌ（ｉ、ｊ−１
）＋１・・（１５）がル（稗されレジスタ１３に格納さ
れる。これによりレジスタ１５には（１３）式、レジス
タ１４には式（１４） ％ レジスタ１３には（１５）
式が格納され、第７図（ｂ）（こより、レジスタ８．９
に１）（ｉ、Ｊ）、Ｌ（ｉ’、ｊ）が格納される。同様
に１）（ｉ弓、ｊ）、Ｌ（ｉ＋１．ｊ）は、第６図てｄ
（ｉ＋１．ｊ）を入力し、第７図でＤ−〜（実際は最大
値）、■・−〇を入力することにより求められる。また
ｒ＞３（１）、場合でも第６図と第７図の処理を繰返え
すことにより、処理ｉ」能で、第５図の処理を行うこと
により最下端の点の０％ Ｌの演算処理に戻る。
とにより起動される。具体的にはｄ（ｉ−１゜Ｊ）をレ
ジスタに入力すると、第６図（ａ）ζこより、レジスタ
２にｗ−ｄ（ｉ−１，ｊ）が格納される０ここで１）（
ｉ ＝１．ｊ）、Ｌ（ｉ−１，ｊ）は、 ３つの最小値
ではなく、 （Ｄ（ｉ−２，ｊ −１）＋ｗｄ（ｉ −１、ｊ ）／
Ｌ（ｉ−２，ｊ−１）＋１０１ｉｎ［］）１ （ＩＣ（ｉ −１、ｊ−１）＋ｄ（ｉ −１、ｊ ］／
Ｌ（ｉ−１、ｊ −１）＋１・ （１０） の２つの最小値より求める。したがって、この最下端の
点の演算のみ第５図の処理を用いる。第５図の処理は、
累卵りと経路長りをレジスタ４．５に入力するこ乏によ
り起動され、る。レジスタ４．５に１）（’ ２．Ｊ
１）ｓ Ｌ（＋ ２．Ｊ １）を入力するＬｌ
レジスタ】３．１５に （１）（ｉ−２，ｊ−１）＋ｗ−ｄ（ｉ−１，Ｊ））／
Ｌ（ｉ ２．ｊ １）”１・（１１） が格納される。次に第７図（こより（Ｊ（ｉ −１、ｊ
−１）、ｒ、（！−ｔ、ｊ １）をレジスタ４．５に
入力する。第動され第７図ｔａ＋て、レジスタ４．５
（’） ｊ（’ｓｌｔよ、レジスタ６．７に格納ざイす
る。レジスタｌ Ｉには、（Ｄ（ｉ−１，ｊ−１）＋ｒ
ｌ（ｉ−１，ｊ）ｌ／Ｌ（ｉ−１，ｊ−１）＋１・・（
１２） が入力され、レジスタ１３に格納されていた値は、レジ
スタ１４に格納される。比紋器１６は、このレジスタ１
３，１４．１５の内最小（こなる値を有するレジスタを
検出し、第７図（１））のよう（こ１）（ｉ−１、ｊ）
、Ｌ（ｉ−１，ｊ）を計算し、レジスタ８．９に格納す
る。すなわち、レジスタ１３が選ばれると、レジスタ９
、分子をレジスタ８番こ格納し、レジスタ１４が選ばれ
たときは、レジスタ６．２．１４、−４５は同１直とな
るため、レジスタ１５は選択されず、レジスタ８．９は
選ばれない。この結果レジスタ８．９よりＤ（ｉ−司、
Ｊ）、Ｌ（ｉ−１゜ｊ）が取り出すこきができる。次に
Ｄ（ｉ、ｊ）、１ｉ （１＋ Ｊ ）を求めるには、同
様に第６図の処理により、（１（ｉ、Ｊ）をレジスタ１
に格納する。第１図（ａｌではレジスタ２に、ｗ −ｄ
（ｉ 、 ｊ ）が格納され、第６図（ｂｌでは （Ｄ（ｉ−１，ｊ）＋ｄ（ｉ、ｊ））／Ｌ（ｉ−１，Ｊ
）＋１（１３） が計ｐされ、レジスタ１５に格納され、第６図（Ｃ）で
、 （”ｌ−１１Ｊ ’）＋Ｗｄ（’＋Ｊ月／Ｌ（ｉ−１，
ｊ−１）＋１（１４） がバＨｉ＋されレジスタ１３に格納される。次に第７図
の処理を用いてＩ）（ｉ、ｊ−１）、Ｌ（ｉ 、 ｊ−
１，）を人力すると、図７（ａ）で、 （ＩＸｉ、ｊ−１）＋ｄ（ｉ、ｊ））／Ｌ（ｉ、ｊ−１
）＋１・・（１５）がル（稗されレジスタ１３に格納さ
れる。これによりレジスタ１５には（１３）式、レジス
タ１４には式（１４） ％ レジスタ１３には（１５）
式が格納され、第７図（ｂ）（こより、レジスタ８．９
に１）（ｉ、Ｊ）、Ｌ（ｉ’、ｊ）が格納される。同様
に１）（ｉ弓、ｊ）、Ｌ（ｉ＋１．ｊ）は、第６図てｄ
（ｉ＋１．ｊ）を入力し、第７図でＤ−〜（実際は最大
値）、■・−〇を入力することにより求められる。また
ｒ＞３（１）、場合でも第６図と第７図の処理を繰返え
すことにより、処理ｉ」能で、第５図の処理を行うこと
により最下端の点の０％ Ｌの演算処理に戻る。
以上のように本発明のパターンマツチング装置は、レジ
スタ６，７．８．９により値Ｄ、１・を保持しているた
め、毎回Ｄ％ Ｌを本装置に入れなおす必殻がない。そ
のため制御が簡単になり、外部のメモリ等との接続が簡
学になるばかりか、非常に高速な処理ができる。また、
レジスタに保持されていることによりパイプライン処理
が可能きなり、従来のものと比べて２倍以上高速の演算
が１１能となる。
スタ６，７．８．９により値Ｄ、１・を保持しているた
め、毎回Ｄ％ Ｌを本装置に入れなおす必殻がない。そ
のため制御が簡単になり、外部のメモリ等との接続が簡
学になるばかりか、非常に高速な処理ができる。また、
レジスタに保持されていることによりパイプライン処理
が可能きなり、従来のものと比べて２倍以上高速の演算
が１１能となる。
以上のＩ） Ｐにより入カバターンと標準パターンの却
似度Ｓを求めたが、入カバターンがどの標準パターンに
似ているかを調べる必要がある。すなわち各伸準パター
ンとの類似度Ｓを比較する必要がある。（以下判定処理
と呼ぶ〕。ある標準パターンとの類似１蜆Ｓは、ｌ）Ｐ
終ｒ時点の累卵Ｄ（Ｉ 、 Ｊ ）き経路長Ｌ（Ｉ、Ｊ
）として斤められているため、Ｓ−１）（Ｉ 、Ｊ ）
／Ｌ（Ｉ 、、１ ）を計算し、全標準パターンに対し
て求めたＳを比較する心安がある。
似度Ｓを求めたが、入カバターンがどの標準パターンに
似ているかを調べる必要がある。すなわち各伸準パター
ンとの類似度Ｓを比較する必要がある。（以下判定処理
と呼ぶ〕。ある標準パターンとの類似１蜆Ｓは、ｌ）Ｐ
終ｒ時点の累卵Ｄ（Ｉ 、 Ｊ ）き経路長Ｌ（Ｉ、Ｊ
）として斤められているため、Ｓ−１）（Ｉ 、Ｊ ）
／Ｌ（Ｉ 、、１ ）を計算し、全標準パターンに対し
て求めたＳを比較する心安がある。
本発明の装置では、第８図に示すように、第４図の回路
に小計のハードを付加するのみでこれらの、判定処理を
実現できる。判定処理は第５図の処理←−ドで４ｄ１作
するため、第５図に対して付加した図を第８図に示す。
に小計のハードを付加するのみでこれらの、判定処理を
実現できる。判定処理は第５図の処理←−ドで４ｄ１作
するため、第５図に対して付加した図を第８図に示す。
第８図において、１７はマルチプレクサ、１８は最大類
似１ｆ３ｉＦ、足部である。
似１ｆ３ｉＦ、足部である。
第９図は第８図の算定部１８の具体的構成の一例を示す
ものである。判定処理では、ＤＰ／刊定切換ノリツブフ
ロッグ１８０を”１”にセットする。これによりフリッ
プフロッグ１８０のＱ出力は”１”レベルとなり、カウ
ンタ１８２は”０”（こクリアされる。マルチプレクサ
１７は、ナンド（ＮＡＮｉ））回路１８１の出力により
制御され、ナンド回路１８１の出力が”１“レベルにな
る古、レジスタ１３の内容をレジスタ１４に送り”０”
レベルではレジスタ１４の内容を保持する。同時に、マ
ルチプレクサ１８３は、ナンド回路１８１の出力が”０
”レベルになると、レジスタ１８４の内容を保持し、１
”レベルになるよ、カウンタ１８２の内容をカウンタ１
８４に送る。ナンド回路１８１に送られる比較器１６の
制御信号は、レジスタ１３〈レジスタ１４のと４”Ｑ”
レベルとなる信号である。
ものである。判定処理では、ＤＰ／刊定切換ノリツブフ
ロッグ１８０を”１”にセットする。これによりフリッ
プフロッグ１８０のＱ出力は”１”レベルとなり、カウ
ンタ１８２は”０”（こクリアされる。マルチプレクサ
１７は、ナンド（ＮＡＮｉ））回路１８１の出力により
制御され、ナンド回路１８１の出力が”１“レベルにな
る古、レジスタ１３の内容をレジスタ１４に送り”０”
レベルではレジスタ１４の内容を保持する。同時に、マ
ルチプレクサ１８３は、ナンド回路１８１の出力が”０
”レベルになると、レジスタ１８４の内容を保持し、１
”レベルになるよ、カウンタ１８２の内容をカウンタ１
８４に送る。ナンド回路１８１に送られる比較器１６の
制御信号は、レジスタ１３〈レジスタ１４のと４”Ｑ”
レベルとなる信号である。
まず各標準パターンに対して得られた最終の累卵をり。
、 Ｄｌ、 Ｄ２・・・Ｄ５、経路長をり。ｌ ＬＩ
Ｉ Ｌ２１・・・Ｌｕ♂する。まず、第６図の処理によ
り距離ｄ＝０を入力し、レジスタ２をＯにする。次にＤ
Ｐモードすなわちフリップフロッグ１８０をリセットに
した状四で第５図の処理により値り。、Ｌｏを入力し、
次に１直り、、Ｌｌを入力すると、レジスタ１４會こは
Ｄ ／Ｌ レジスタ１３にはり、／Ｌ、が０
０１ 格納される。次に判定処理にするため、フリップフロッ
プ１８０をセットし、カウンタ１８２をクリアする。カ
ウンタ１８２は第５図の処理を実行する毎に＋１され、
もしレジスタ１３がレジスタ１４より小さくなった時は
、カウンタ１８２の内容がレジスタ１８４に格納され、
レジスタ１４にはレジスタ１３より小さい場合は、レジ
スタ１４．１８４共その値が保持される。したがって％
ＤＢ ！Ｌ（ｎ＝２〜ｎ）まで同様に実行することに
より、レジスタ１４，１８４には、最大の類似度Ｓとそ
れが何番目に入力したものかが格納される。
Ｉ Ｌ２１・・・Ｌｕ♂する。まず、第６図の処理によ
り距離ｄ＝０を入力し、レジスタ２をＯにする。次にＤ
Ｐモードすなわちフリップフロッグ１８０をリセットに
した状四で第５図の処理により値り。、Ｌｏを入力し、
次に１直り、、Ｌｌを入力すると、レジスタ１４會こは
Ｄ ／Ｌ レジスタ１３にはり、／Ｌ、が０
０１ 格納される。次に判定処理にするため、フリップフロッ
プ１８０をセットし、カウンタ１８２をクリアする。カ
ウンタ１８２は第５図の処理を実行する毎に＋１され、
もしレジスタ１３がレジスタ１４より小さくなった時は
、カウンタ１８２の内容がレジスタ１８４に格納され、
レジスタ１４にはレジスタ１３より小さい場合は、レジ
スタ１４．１８４共その値が保持される。したがって％
ＤＢ ！Ｌ（ｎ＝２〜ｎ）まで同様に実行することに
より、レジスタ１４，１８４には、最大の類似度Ｓとそ
れが何番目に入力したものかが格納される。
以上述べたように、本発明によれば、Ｉ）Ｐによるパタ
ーンマツチングを簡単な構成で、極めて高床に行なうこ
さができる。
ーンマツチングを簡単な構成で、極めて高床に行なうこ
さができる。
第１図〜第３図はＤＰによるノシターンマッチングを説
明する説明図、第４図は本発明による・シターンマッチ
ング装置の一実施例のブロック図、第５図〜第７図は各
モードで動作Ｃる第４図の回路部分を示すブロック図、
第８図は本発明によるノくターンマツチング残置の他の
実施例の主要部の構成を示すブロック図、第９図は第８
図の一部の具体的構成の一例を示す回路図である。 ４．６，５，７，１３．１４シフトレジスタ、１．２，
８，９．１５レジスタ、３乗暉器、１０：加痺器、１１
：インクリメンタ、１２：ＲＯＭ、１６：比較器。 第 １ １Ｕ （Ｙ） 第 ３ 曙 第 ゲ １２ 、ｙ ！；＋幻 第 ６ 図 （Ｑ’） 第 ７１］ （α） （ｂ）
明する説明図、第４図は本発明による・シターンマッチ
ング装置の一実施例のブロック図、第５図〜第７図は各
モードで動作Ｃる第４図の回路部分を示すブロック図、
第８図は本発明によるノくターンマツチング残置の他の
実施例の主要部の構成を示すブロック図、第９図は第８
図の一部の具体的構成の一例を示す回路図である。 ４．６，５，７，１３．１４シフトレジスタ、１．２，
８，９．１５レジスタ、３乗暉器、１０：加痺器、１１
：インクリメンタ、１２：ＲＯＭ、１６：比較器。 第 １ １Ｕ （Ｙ） 第 ３ 曙 第 ゲ １２ 、ｙ ！；＋幻 第 ６ 図 （Ｑ’） 第 ７１］ （α） （ｂ）
Claims (1)
- 時間軸を整合しながら、入カバターンと標準パターンの
マツチングを行なう動的計画法を用いたパターンマツチ
ング装置において、所定計算点における入カバターンと
標準パターンとの距離を格納する第１のレジスタと、上
記距離の上記計算点までの累卵および経路長を格納する
第２および第３のレジスタと、上記第１〜第３のレジス
タの内容により、次の計與点における経路毎の距離の累
卵および経路長を計算する第１の計算手段と、該手段で
求めた値を格納する第４のレジスタと、該第４のレジス
タの内容から、次の計算点に至る最適の経路を選び、そ
の経路での距離の累卵および経路長を次の計算点におけ
る値として求める第２の計算手段とを備えたことを特徴
とするパターンマツチング装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58105844A JPS59200A (ja) | 1983-06-15 | 1983-06-15 | パタ−ンマツチング装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58105844A JPS59200A (ja) | 1983-06-15 | 1983-06-15 | パタ−ンマツチング装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS59200A true JPS59200A (ja) | 1984-01-05 |
Family
ID=14418322
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP58105844A Pending JPS59200A (ja) | 1983-06-15 | 1983-06-15 | パタ−ンマツチング装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS59200A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS59174700A (ja) * | 1983-01-31 | 1984-10-03 | ユニリ−バ− ナ−ムロ−ゼ ベンノ−トシヤ−プ | バタ−様脂肪およびその製造法 |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5628278A (en) * | 1979-08-15 | 1981-03-19 | Matsushita Electric Ind Co Ltd | Pyrogenic composition |
| JPS5926960A (ja) * | 1982-08-02 | 1984-02-13 | 藤井 実 | 被覆方法 |
-
1983
- 1983-06-15 JP JP58105844A patent/JPS59200A/ja active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5628278A (en) * | 1979-08-15 | 1981-03-19 | Matsushita Electric Ind Co Ltd | Pyrogenic composition |
| JPS5926960A (ja) * | 1982-08-02 | 1984-02-13 | 藤井 実 | 被覆方法 |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS59174700A (ja) * | 1983-01-31 | 1984-10-03 | ユニリ−バ− ナ−ムロ−ゼ ベンノ−トシヤ−プ | バタ−様脂肪およびその製造法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2595495B2 (ja) | パタンマッチング装置 | |
| JPS5998387A (ja) | メモリ回路 | |
| JPS5885499A (ja) | 連続音声認識装置 | |
| US4918733A (en) | Dynamic time warping using a digital signal processor | |
| US4901352A (en) | Pattern matching method using restricted matching paths and apparatus therefor | |
| JPS58132298A (ja) | 窓制限付パタンマツチング装置 | |
| JPS59200A (ja) | パタ−ンマツチング装置 | |
| Stainhaouer et al. | New parallel implementations for DTW algorithms | |
| JPH0887294A (ja) | 音声認識装置 | |
| JPH0436400B2 (ja) | ||
| JPS63188199A (ja) | パタンマッチング装置 | |
| JPS592954B2 (ja) | パタンルイジドケイサンソウチ | |
| JP3348735B2 (ja) | パターン照合方式 | |
| JPS61292697A (ja) | パタン類似度計算装置 | |
| JPS6118760B2 (ja) | ||
| JPS63226696A (ja) | 高能率パタ−ンマッチング方式 | |
| JPS60237496A (ja) | 音声認識方法及びその装置 | |
| JPS5926960B2 (ja) | 時系列パタンマツチング装置 | |
| JPS6154240B2 (ja) | ||
| JPS6265090A (ja) | パタ−ン比較装置 | |
| JPH02292685A (ja) | パターンマッチング回路 | |
| JPS61219100A (ja) | 特定話者用音声入力装置 | |
| JPS58105294A (ja) | 信号波形認識方式 | |
| JPH03253900A (ja) | 音声認識装置 | |
| JPH0465397B2 (ja) |