(57)【要約】【課題】標準パターンを圧縮した場合でもマッチングエラーの発生率を低減する。【解決手段】パターンマッチング装置１０は、標準パターンを構成する各特徴要素Ｂ１，Ｂ２，Ｂ３について、パターン圧縮部１２で、隣接する特徴要素と近似しているものを１つの特徴要素に統合することによって標準パターンを圧縮する。また、圧縮情報生成部１３で、圧縮された圧縮標準パターンの特徴要素毎の圧縮比の系列を圧縮情報として生成する。そして、圧縮された圧縮標準パターンを、記憶部１４で当該圧縮標準パターンに対して生成された圧縮情報と関連付けて記憶する。そして、記憶された圧縮標準パターンと入力パターンとのパターン間距離を、当該圧縮標準パターンに対して生成された圧縮情報を変数として持つ動的計画法の漸化式によって算出する。【選択図】      図１
2011022621.tif 000002
【特許請求の範囲】
【請求項１】
それぞれ特徴要素の時系列で示される標準パターンと入力パターンとのパターン間距離を求め、そのパターン間距離を認識結果として出力するパターンマッチング装置において、
前記標準パターンを構成する各特徴要素について、隣接する特徴要素と近似しているものを１つの特徴要素に統合することによって前記標準パターンを圧縮するパターン圧縮手段と、
前記パターン圧縮手段により圧縮された圧縮標準パターンの特徴要素毎の圧縮比の系列を圧縮情報として生成する圧縮情報生成手段と、
前記パターン圧縮手段により圧縮された前記圧縮標準パターンを、当該圧縮標準パターンに対して前記圧縮情報生成手段により生成された前記圧縮情報と関連付けて記憶する記憶手段と、
前記記憶手段により記憶された前記圧縮標準パターンと前記入力パターンとのパターン間距離を、当該圧縮標準パターンに対して前記圧縮情報生成手段により生成された前記圧縮情報を変数として持つ動的計画法の漸化式によって算出する距離演算手段と、
を具備したことを特徴とするパターンマッチング装置。
【請求項２】
前記距離演算手段において用いられる漸化式は、
前記入力パターンの特徴要素ａｉと前記圧縮標準パターンの特徴要素ｂｊとの要素間距離をｄ（ｉ，ｊ）とし、前記入力パターンと前記圧縮標準パターンとの要素間累積距離をｇ（ｉ，ｊ）とし、前記圧縮比ｎの系列である圧縮情報をｎｊとすると、
【数１】
2011022621.tif 000009
で表されることを特徴とする請求項１記載のパターンマッチング装置。
【請求項３】
前記距離演算手段において用いられる漸化式は、
前記入力パターンの特徴要素ａｉと前記圧縮標準パターンの特徴要素ｂｊとの要素間距離をｄ（ｉ，ｊ）とし、前記入力パターンと前記圧縮標準パターンとの要素間累積距離をｇ（ｉ，ｊ）とし、前記圧縮比ｎの系列である圧縮情報をｎｊとすると、
【数２】
2011022621.tif 000010
で表されることを特徴とする請求項１記載のパターンマッチング装置。
【請求項４】
前記距離演算手段において用いられる漸化式は、
前記入力パターンの特徴要素ａｉと前記圧縮標準パターンの特徴要素ｂｊとの要素間距離をｄ（ｉ，ｊ）とし、前記入力パターンと前記圧縮標準パターンとの要素間累積距離をｇ（ｉ，ｊ）とし、前記圧縮比ｎの系列である圧縮情報をｎｊとすると、
【数３】
2011022621.tif 000011
で表されることを特徴とする請求項１記載のパターンマッチング装置。
【請求項５】
それぞれ特徴要素の時系列で示される標準パターンと入力パターンとのパターン間距離を求め、そのパターン間距離を認識結果として出力するパターンマッチング装置におけるパターンマッチング方法であって、
前記標準パターンを構成する各特徴要素について、隣接する特徴要素と近似しているものを１つの特徴要素に統合することによって前記標準パターンを圧縮する圧縮工程と、
前記パターン圧縮手段により圧縮された圧縮標準パターンの特徴要素毎の圧縮比の系列を圧縮情報として生成する生成工程と、
前記圧縮工程で圧縮された前記圧縮標準パターンと前記入力パターンとのパターン間距離を、当該圧縮標準パターンに対して前記生成工程により生成された前記圧縮情報を変数として持つ動的計画法の漸化式によって算出する演算工程と、
を含むことを特徴とするパターンマッチング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、音声，文字，図形等の入力パターンが、予め想定されている標準パターンのうちのいずれであるかを判定するパターン認識分野で利用されるパターンマッチング装置及び方法に関する。
【背景技術】
【０００２】
従来のパターン認識分野では、パターンマッチング方式として動的計画法（Dynamic programming : ＤＰ）が広く活用されている（例えば、特許文献１参照）。
【０００３】
音声のパターン認識分野を例に、動的計画法の原理について説明する。  
音声パターンＡは、次の（１）式のように表現される。
【数１】
2011022621.tif 000003
【０００４】
（１）式において、ｉ｛ｉ＝１，２，…，Ｉ｝は時間を示し、ａは音声パターンＡの時間ｉにおける特徴要素を意味している。
【０００５】
そこで、各種の単語毎に、音声パターンＡと同様の、特徴要素の時系列で表現される標準パターンＢを用意しておく。この標準パターンＢは、次の（２）式のように表現される。
【数２】
2011022621.tif 000004
【０００６】
（２）式において、ｊ｛ｊ＝１，２，…，Ｊ｝は時間を示し、ｂは音声パターンＢの時間ｊにおける特徴要素を意味している。
【０００７】
パターンマッチング装置では、入力された音声パターンＡを、各種単語の標準パターンＢとそれぞれ比較してパターン間の距離を求める。そして、最小距離の標準パターンを認識結果として出力する。
【０００８】
実際の音声パターンでは、発話速度の変動に起因して時間軸歪が生じる。動的計画法は、この時間軸歪を整合する手法として極めて有効である。
【０００９】
動的計画法では、次の（３）式に示された漸化式を繰返し演算する。
【数３】
2011022621.tif 000005
【００１０】
（３）式において、ｄ（ｉ，ｊ）は、音声パターンＡの特徴要素ａｉと標準パターンＢの特徴要素ｂｊとの要素間距離である。ｇ（ｉ，ｊ）は、音声パターンＡと標準パターンＢとの要素間累積距離である。
【００１１】
パターンマッチング装置では、上記漸化式（３）を繰り返し計算する。そして、図９に示すように、Ａ，Ｂ平面でａｉとｂｊとを最適に対応付ける経路（ＤＰ−pass）を求める。
【００１２】
上記漸化式（３）の最上段の式は、図１０に示すＡ，Ｂ平面上の任意の点（ｉ，ｊ）に対し、下方に隣接する点（ｉ，ｊ−１）との関係を規定している。同漸化式（３）の中段の式は、点（ｉ，ｊ）に対し、左斜め下に隣接する点（ｉ−１，ｊ−１）との関係を規定している。同漸化式（３）の最下段の式は、点（ｉ，ｊ）に対し、左側に隣接する点（ｉ−１，ｊ）との関係を規定している。
【００１３】
なお、この漸化式（３）から最上段の式を省略することで傾斜制限を加える場合もある。この場合は、任意の点（ｉ，ｊ）に対して図１１に示すような関係が規定される。傾斜制限は極端な伸縮を制限するために設けられる。
【００１４】
ところで一般に、パターンマッチングに必要な標準パターンは多数用意される。このため、標準パターンを圧縮することによって、標準パターンを記憶する領域の効率化を図ることが考えられている。標準パターンを圧縮する方法としては、次の方法がある。すなわち、標準パターンを構成する各特徴要素について、それぞれ隣接する特徴要素との差をとる。そして、その差があらかじめ設定された閾値より小さい場合は、隣接した特長要素が近似していると判定する。近似しているものがあった場合には、それらを１つの特徴要素に統合する。かくして、標準パターンが圧縮される。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開昭５０-９６１０４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、上述した方法で標準パターンを圧縮した場合、パターン認識に有益な時間情報が消失してしまう。すなわち、隣接する特徴要素が１つに統合されるので、各要素がそれぞれ有していた時間情報の一部が消失する。標準パターンから時間情報の一部が失われると、一般に、マッチングエラー（matching error）が発生し易くなる。特に、ノイズ（noise）の混入により部分的に近似した特徴パターンが数多く認識された場合や、傾斜制限が設けられた場合には、マッチングエラーが顕著に見られる。
【００１７】
本発明は、このような事情に基づいてなされたもので、その目的とするところは、標準パターンを圧縮した場合でもマッチングエラーの発生率を低減することができるパターンマッチング装置及びその方法を提供しようとするものである。
【課題を解決するための手段】
【００１８】
本発明のパターンマッチング装置は、標準パターンを構成する各特徴要素について、隣接する特徴要素と近似しているものを１つの特徴要素に統合することによって標準パターンを圧縮する。また、圧縮された圧縮標準パターンの特徴要素毎の圧縮比の系列を圧縮情報として生成する。そして、圧縮された圧縮標準パターンを、当該圧縮標準パターンに対して生成された圧縮情報と関連付けて記憶する。そして、記憶された圧縮標準パターンと入力パターンとのパターン間距離を、当該圧縮標準パターンに対して生成された圧縮情報を変数として持つ動的計画法の漸化式によって算出する。
【発明の効果】
【００１９】
かかる手段を講じた本発明によれば、標準パターンを圧縮した場合でもマッチングエラーの発生率を低減することができるパターンマッチング装置及びその方法を提供できる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態であるパターンマッチング装置の構成を示すブロック図。
【図２】同パターンマッチング装置で行われる標準パターン圧縮処理を説明するための図。
【図３】同パターンマッチング装置の記憶部に記憶されるデータ構造を示す模式図。
【図４】第１の実施の形態におけるパターンマッチング処理部の要部構成を示すブロック図。
【図５】第２の実施の形態におけるパターンマッチング処理部の要部構成を示すブロック図。
【図６】第２の実施の形態のパターンマッチング処理部で計算される第１の漸化式を説明するための図。
【図７】第２の実施の形態のパターンマッチング処理部で計算される第２の漸化式を説明するための図。
【図８】第２の実施の形態のパターンマッチング処理部で計算される第３の漸化式を説明するための図。
【図９】従来の動的計画法を説明するための図。
【図１０】従来の動的計画法で計算される漸化式を説明するための図。
【図１１】従来の動的計画法で計算される漸化式の他の例を説明するための図。
【発明を実施するための形態】
【００２１】
以下、本発明を音声のパターン認識分野に適用した実施の形態について、図面を用いて説明する。はじめに、第１の実施の形態について、図１〜図４を用いて説明する。
【００２２】
図１は本実施の形態に係るパターンマッチング装置１０の要部構成を示すブロック図である。パターンマッチング装置１０は、音声分析部１１，パターン圧縮部１２、圧縮情報生成部１３、記憶部１４及びパターンマッチング処理部１５を備えている。
【００２３】
音声分析部１１には、音声信号Ｍが入力される。音声信号Ｍは、マイクロフォンを通して入力された音声から変換された電気信号である。音声分析部１１は、入力された音声信号Ｍを分析する。そして、入力音声の特徴要素ａを時系列で抽出して、前記（１）式で示される音声パターンＡを生成する。音声パターンＡは、パターンマッチング処理部１５に出力される。
【００２４】
パターン圧縮部１２には、複数の標準パターンＢ１，Ｂ２，Ｂ３，…が入力される。各標準パターンＢ１，Ｂ２，Ｂ３，…は、各種の単語毎に予め用意されたものである。これらの標準パターンＢ１，Ｂ２，Ｂ３，…は圧縮されていない。パターン圧縮部１２は、入力された各標準パターンＢ１，Ｂ２，Ｂ３，…をそれぞれ時間方向に圧縮する。
【００２５】
その圧縮方法について、図２を用いて説明する。同図において、ｂ１，ｂ２，ｂ３，…，ｂ９は任意の標準パターンＢｘの各特長要素を示している。標準パターンＢｘは、各特長要素ｂ１，ｂ２，ｂ３，…，ｂ９がその順番に時系列に並べられたものである。
【００２６】
パターン圧縮部１２では、標準パターンＢｘを構成する各特長要素ｂ１，ｂ２，ｂ３，…，ｂ９について、それぞれ隣接した特徴要素との距離を求める。そして、距離が予め設定された閾値以下であった場合に、これら隣接した複数の特徴要素を一つの平均特徴要素ｂ′ｋ（ｋ＝１，２，３，…）に置き換える。この処理により、局所的に複数の特徴要素が平均特徴要素に圧縮される。標準パターンＢｘの全体にこの処理を施すことにより、圧縮標準パターンＢ′ｘが生成される。
【００２７】
図２の例の場合、隣接する特徴要素ｂ２とｂ３との距離が閾値以下であり、これら特徴要素ｂ２，ｂ３が平均特徴要素ｂ′２｛ｂ′２＝（ｂ２＋ｂ３）／２｝に置き換えられている。また、隣接する特徴要素ｂ４，ｂ５及びｂ６の距離が閾値以下であり、これらの特徴要素ｂ４，ｂ５及びｂ６が平均特徴要素ｂ′３｛ｂ′３＝（ｂ４＋ｂ５＋ｂ６）／３｝に置き換えられている。また、隣接する特徴要素ｂ７とｂ８との距離が閾値以下であり、これら特徴要素ｂ７，ｂ８が平均特徴要素ｂ′４｛ｂ′４＝（ｂ７＋ｂ８）／２｝に置き換えられている。かくして、標準パターンＢｘ（＝ｂ１，ｂ２，ｂ３，…，ｂ９）が圧縮標準パターンＢ′ｘ（＝ｂ′１，ｂ′２，ｂ′３，ｂ′４，ｂ′５）に圧縮される。
【００２８】
圧縮情報生成部１３は、前記パターン圧縮部１２により圧縮された圧縮標準パターンＢ′ｘの特徴要素ｂ′１，ｂ′２，ｂ′３，ｂ′４，ｂ′５毎の圧縮比ｎ１，ｎ２，ｎ３，ｎ４．ｎ５の系列を圧縮情報Ｎｘとして生成する。本実施の形態では、図２に示すように、圧縮標準パターンＢ′ｘの各特徴要素ｂ′１，ｂ′２，ｂ′３，ｂ′４，ｂ′５が、それぞれ元の標準パターンＢｘの何個分の特徴要素を代表しているのかを示す値を圧縮比ｎ１，ｎ２，ｎ３，ｎ４．ｎ５と定義している。
【００２９】
すなわち、圧縮標準パターンＢ′ｘの特徴要素ｂ′１は、標準パターンＢｘの特徴要素ｂ１だけを代表しているので、圧縮比ｎ１は“１”である。同様に、特徴要素ｂ′２は、特徴要素ｂ２とｂ３とを代表しているので、圧縮比ｎ２は“２”である。特徴要素ｂ′３は、特徴要素ｂ４とｂ５とｂ６とを代表しているので、圧縮比ｎ３は“３”である。特徴要素ｂ′４は、特徴要素ｂ７とｂ８とを代表しているので、圧縮比ｎ４は“２”である。特徴要素ｂ′５は、特徴要素ｂ９だけを代表しているので、圧縮比ｎ５は“１”である。
【００３０】
かくして、圧縮標準パターンＢ′ｘに対する圧縮情報はＮｘは、“１，２，３，１，２”となる。
【００３１】
記憶部１４は、図３に示すように、パターン圧縮部１２で圧縮された圧縮標準パターンＢ′ｘを、当該圧縮標準パターンに対して圧縮情報生成部１３で生成された圧縮情報Ｎｘと関連付けて記憶する。
【００３２】
パターンマッチング処理部１５は、図４に示すように、復元部２１と、平滑化処理部２２と、距離計算部２３とを備えている。
【００３３】
復元部２１は、記憶部１４に記憶されている圧縮標準パターンＢ′ｘを、当該圧縮標準パターンＢ′ｘと関連付けて記憶されている圧縮情報Ｎｘに基づき伸長して、標準パターンＢｘ１に復元する。例えば図２の例の場合、圧縮標準パターンＢ′ｘ（ｂ′１，ｂ′２，ｂ′３，ｂ′４，ｂ′５）に関連する圧縮情報Ｎｘ（ｎ１，ｎ２，ｎ３，ｎ４．ｎ５）は、“１，２，３，１，２”である。
【００３４】
したがって、特徴要素ｂ′１は、そのままとなる。特徴要素ｂ′２は、隣接する２つの特徴要素ｂ′２，ｂ′２となる。特徴要素ｂ′３は、隣接する３つの特徴要素ｂ′３，ｂ′３，ｂ′３となる。特徴要素ｂ′４は、隣接する２つの特徴要素ｂ′４，ｂ′４となる。特徴要素ｂ′５は、そのままとなる。かくして、圧縮標準パターンＢ′ｘは、標準パターンＢｘ１（ｂ′１，ｂ′２，ｂ′２，ｂ′３，ｂ′３，ｂ′３，ｂ′４，ｂ′４，ｂ′５）に復元される。
【００３５】
平滑化処理部２２は、復元部２１で復元された標準パターンＢｘ１に対して低域通過フィルタによる平滑化処理を行う。復元された標準パターンＢｘ１には、圧縮によるノイズが発生している。平滑化処理を施すことによって、この種のノイズを除去できる。
【００３６】
距離計算部２３は、音声分析部１１を介して入力された音声パターンＡと、平滑化処理部２２にて平滑化処理された標準パターンＢｘ１とのパターン間距離Ｇｘを、周知の動的計画法により算出する。例えば、前記（３）式に示された漸化式の繰返し演算によってパターン間距離Ｇｘを算出する。
【００３７】
パターンマッチング処理部１５では、全ての圧縮標準パターンＢ′ｘについて、前記復元部２１、平滑化処理部２２及び距離計算部２３での処理を繰返し実行する。そして、算出されたパターン間距離Ｇｘが最小となる標準パターンＢｘ１を求めて、音声パターンＡの認識結果Ｇとして出力する。
【００３８】
このように、本実施の形態のパターンマッチング装置１０においては、標準パターンＢｘを圧縮して圧縮標準パターンＢ′ｘを生成する際に、その圧縮標準パターンＢ′ｘの特徴要素毎の圧縮比の系列を圧縮情報Ｎｘとして生成している。そして、圧縮標準パターンＢ′ｘを、当該圧縮標準パターンＢ′ｘに対して生成された圧縮情報Ｎｘと関連付けて記憶部１４で記憶している。
【００３９】
音声信号Ｍが入力されると、音声分析部１１により入力音声の特徴要素ａが時系列で抽出されて、音声パターンＡが生成される。音声パターンＡは、パターンマッチング処理部１５に出力される。パターンマッチング処理部１５では、記憶部１４に記憶された全ての圧縮標準パターンＢ′ｘに対して、以下のパターンマッチング処理が実行される。
【００４０】
先ず、記憶部１４から任意の圧縮標準パターンＢ′ｘと、それに関連する圧縮情報Ｎｘとが読み出される。そして、圧縮標準パターンＢ′ｘが圧縮情報Ｎｘに基づき伸長されて、標準パターンＢｘ１に復元される。次に、復元された標準パターンＢｘ１に対して平滑化処理が行われる。しかる後、入力された音声パターンＡと平滑化処理が施された標準パターンＢｘ１とのパターン間距離Ｇｘが動的計画法により算出される。
【００４１】
こうして、パターンマッチング処理部１５では、圧縮標準パターンＢ′ｘ毎に、音声パターンＡとのパターン間距離Ｇｘが算出される。そして、パターン間距離Ｇｘが最小となる標準パターンＢｘ１が音声パターンＡの認識結果Ｇとして出力される。
【００４２】
このように、圧縮された標準パターンＢ′ｘをそのまま音声パターンＡとのパターン間距離の演算に用いるのではなく、圧縮情報Ｎｘで標準パターンＢｘ１に復元してから用いている。したがって、標準パターンＢｘの圧縮により失われた時間情報が加味されるので、マッチングエラーの発生率が低減される。
【００４３】
次に、第２の実施の形態について説明する。第２の実施の形態は、パターンマッチング処理部１５のみが第１の実施の形態と異なる。第２の実施の形態におけるパターンマッチング処理部１５の要部構成を図５のブロック図で示す。
【００４４】
パターンマッチング処理部１５は、漸化式設定部３１と距離計算部３２とを備えている。距離計算部３２は、音声パターンＡと圧縮標準パターンＢ′ｘとのパターン間距離Ｇｘを、漸化式設定部３１に設定された漸化式の繰返し演算によって算出する。この際、圧縮標準パターンＢ′ｘと関連付けられて記憶されている圧縮情報Ｎｘを用いて漸化式の計算を行う。
【００４５】
漸化式設定部３１には、次の（４）式に示された漸化式が設定されている。
【数４】
2011022621.tif 000006
【００４６】
（４）式において、ｄ（ｉ，ｊ）は、音声パターンＡの特徴要素ａｉと圧縮標準パターンＢ′ｘの特徴要素ｂ′ｊとの要素間距離である。ｇ（ｉ，ｊ）は、音声パターンＡと圧縮標準パターンＢ′ｘとの要素間累積距離である。ｎｊ−１は圧縮情報Ｎｘの要素（圧縮比）である。
【００４７】
上記漸化式（４）の最上段の式は、図６に示すＡ，Ｂ平面上の任意の点（ｉ，ｊ）に対し、左側に隣接する点（ｉ−１，ｊ）との関係を規定している。
【００４８】
同漸化式（４）の最下段の式は、圧縮情報要素ｎｊ−１が“１”の場合である。この場合は、点（ｉ，ｊ）に対し、左斜め下に隣接する点（ｉ−１，ｊ−１）との関係を規定している。
【００４９】
同漸化式（４）の中段の式は、圧縮情報要素ｎｊ−１が“１”より大きい場合である。この場合は、点（ｉ，ｊ）に対し、左斜め下に隣接する点（ｉ−１，ｊ−１）から、さらに特徴要素ｂ′ｊ−１に対応する圧縮情報要素ｎｊ−１に従い制限経路長が伸長された点（ｉ−ｎｊ−１，ｊ−１）との関係を規定している。
【００５０】
このような漸化式（４）の演算を繰返し行うことによって、圧縮標準パターンＢ′ｘの特徴要素ｂ′ｊ−１は、入力パターンＡのｎｊ−１個の要素ａｉとの対応が課せられる。したがって、標準パターンＢｘの圧縮により失われた時間情報が加味されるので、マッチングエラーの発生率が低減される。
【００５１】
同様な効果が得られる漸化式は、上記（４）式に限定されるものではない。例えば、図７に示すように、制限経路長の伸長を、特徴要素ｂ′ｊに対して行う下記（５）式の漸化式を漸化式設定部３１に設定してもよい。
【数５】
2011022621.tif 000007
【００５２】
あるいは、図８に示すように、制限経路長の伸長を、特徴要素ｂ′ｊとｂ′ｊ−１との両方に対して行う下記（６）式の漸化式を漸化式設定部３１に設定してもよい。
【数６】
2011022621.tif 000008
【００５３】
なお、前記各実施の形態では、標準パターンＢｘを圧縮する際に、近似した複数の特徴要素の平均をとるようにしたが、近似した特徴要素の１つを代表として選択するようにしてもよい。また、コードブックによるクラスタリング手法を用いることも可能である。
【００５４】
また、前記実施の形態では、圧縮情報ｎＸの要素（圧縮比）ｎｊをそのまま用いているが、所定の倍率、例えば０．８倍の値を用いてパターン間距離を計算するようにしてもよい。
【００５５】
また、前記実施の形態では、音声のパターン認識分野に適用した場合を示したが、本発明は、文字，図形等のパターン認識分野にも同様に適用できるものである。この他、本発明の要旨を逸脱しない範囲で種々変形実施可能であるのは勿論である。
【符号の説明】
【００５６】
１０…パターンマッチング装置、１１…音声分析部、１２…パターン圧縮部、１３…圧縮情報生成部、１４…記憶部、１５…パターンマッチング処理部。
【図１】
2011022621.tif 000012
【図２】
2011022621.tif 000013
【図３】
2011022621.tif 000014
【図４】
2011022621.tif 000015
【図５】
2011022621.tif 000016
【図６】
2011022621.tif 000017
【図７】
2011022621.tif 000018
【図８】
2011022621.tif 000019
【図９】
2011022621.tif 000020
【図１０】
2011022621.tif 000021
【図１１】
2011022621.tif 000022