(57)【要約】【課題】本発明は、ベクトル列の照合処理における計算量を減らすことが出来、高速な照合処理が可能となる照合装置及びベクトル照合方法を提供することを課題とする。【解決手段】入力ベクトル列をベクトル列縮小部１−１，１−２によって縮小処理を施し、ベクトル列の長さを縮小して縮小ベクトル同士を照合部２によって照合する。これにより、照合処理における計算量を減らすことが出来る。また縮小ベクトルによる照合の結果に基づいて候補を選出し、縮小していない候補と入力ベクトル列を照合することによって高い照合精度を保ちながら１対複数の照合を実現することが出来る。【選択図】    図１
2004326362.tif 000002
【特許請求の範囲】
【請求項１】
第１のベクトル列を縮小して第１の縮小ベクトル列を生成する第１のベクトル列縮小手段と、
前記第１の縮小ベクトル列と、第２のベクトル列を縮小して生成した第２の縮小ベクトル列を照合する第１の照合手段と
を備えることを特徴とする照合装置。
【請求項２】
前記第１のベクトル列縮小手段は、前記第１のベクトル列内の隣り合うベクトルを、該隣り合うベクトルを代表する代表ベクトルに置き換えることにより前記第１の縮小ベクトルを生成することを特徴とする請求項１に記載の照合装置。
【請求項３】
前記第１のベクトル列縮小手段は、前記第１のベクトル列内の隣り合うベクトルのベクトル間距離を算出し、該隣り合うベクトルのうち該ベクトル間距離が近いものを代表ベクトルに置き換えることにより前記第１の縮小ベクトルを生成することを特徴とする請求項２に記載の照合装置。
【請求項４】
前記第１のベクトル列縮小手段は、前記ベクトル間距離の最も小さい値が既定値より大きくなるまで、前記隣り合うベクトルを前記代表ベクトルに置き換えることにより前記第１の縮小ベクトルを生成することを特徴とする請求項３に記載の照合装置。
【請求項５】
前記第１のベクトル列縮小手段は、前記第１のベクトル列内のベクトルの数が既定値以下になるまで、前記隣り合うベクトルを前記代表ベクトルに置き換えることにより前記第１の縮小ベクトルを生成することを特徴とする請求項３に記載の照合装置。
【請求項６】
前記第１のベクトル列縮小手段は、前記第１のベクトル列内の隣り合うベクトルのベクトル間距離を算出し、該ベクトル間距離が既定値以下であるベクトルが連続している部分を部分ベクトル列として検出し、該部分ベクトル列を該部分ベクトルを代表する代表ベクトルに置き換えることにより前記第１の縮小ベクトルを生成することを特徴とする請求項１に記載の照合装置。
【請求項７】
前記第１のベクトル列縮小手段は、前記部分ベクトル列内のベクトルを各要素毎に平均した値を用いて生成することを特徴とする請求項６に記載の照合装置。
【請求項８】
前記第１のベクトル列縮小手段は、前記部分ベクトル列内のベクトルの内、時間軸上において最も中央に近い位置にあるベクトルから前記代表ベクトルを生成することを特徴とする請求項６に記載の照合装置。
【請求項９】
前記第２のベクトル列を記憶する記憶手段を更に備えることを特徴とする請求項１乃至８の何れか１つに記載の照合装置。
【請求項１０】
前記記憶手段は、複数の前記第２のベクトル列を該第２のベクトル列に対応する前記第２の縮小ベクトル列と共に記憶することを特徴とする請求項９に記載の照合装置。
【請求項１１】
前記第１の照合手段による照合結果に基づいて、前記複数の第２のベクトル列から選択して前記第１のベクトル列との照合を行なう第２の照合手段を更に備えることを特徴とする請求項１０に記載の照合装置。
【請求項１２】
前記ベクトル間距離は、ユークリッド距離によって定義される値であることを特徴とする請求項３乃至１１の何れか１つに記載の照合装置。
【請求項１３】
前記ベクトル間距離は、ハミング距離によって定義される値であることを特徴とする請求項３乃至１１の何れか１つに記載の照合装置。
【請求項１４】
前記第２のベクトル列を縮小して前記第２の縮小ベクトル列を生成する第２のベクトル列縮小手段を更に備えることを特徴とする請求項１乃至１３の何れか１つに記載の照合装置。
【請求項１５】
生体認証に用いられる生体情報データが入力される入力手段と、
該入力手段から入力された前記生体情報データから特徴ベクトル列を算出する特徴ベクトル算出手段とをさらに有し、
前記第１のベクトル列および前記第２のベクトル列内の各ベクトルとして、前記特徴ベクトル算出手段によって算出された特徴ベクトルを用いることを特徴とする請求項１乃至１４の何れか１つに記載の照合装置。
【請求項１６】
第１のベクトル列を縮小して第１の縮小ベクトル列をＣＰＵによって生成し、
前記第１の縮小ベクトル列と、第２のベクトル列を縮小して生成した第２の縮小ベクトル列をＣＰＵによって照合する
ことを特徴とするベクトル列照合方法。
【請求項１７】
第１のベクトル列を縮小して第１の縮小ベクトル列をＣＰＵによって生成し、
前記第１の縮小ベクトル列と、第２のベクトル列を縮小して生成した第２の縮小ベクトル列をＣＰＵによって照合し、
前記第１の縮小ベクトル列と前記第２の縮小ベクトル列との照合の結果、距離が規定値以下の時、前記第１のベクトル列と前記第２のベクトル列との照合をＣＰＵによって行なう
ことを特徴とするベクトル列照合方法。
【請求項１８】
情報処理装置によって使用された時、
第１のベクトル列を縮小して第１の縮小ベクトル列をＣＰＵによって生成し、
前記第１の縮小ベクトル列と、第２のベクトル列を縮小して生成した第２の縮小ベクトル列をＣＰＵによって照合する
ことを前記情報処理装置に実行させるプログラム。
【請求項１９】
情報処理装置によって使用された時、
第１のベクトル列を縮小して第１の縮小ベクトル列をＣＰＵによって生成し、
前記第１の縮小ベクトル列と、第２のベクトル列を縮小して生成した第２の縮小ベクトル列をＣＰＵによって照合し、
前記第１の縮小ベクトル列と前記第２の縮小ベクトル列との照合の結果、距離が規定値以下の時、前記第１のベクトル列と前記第２のベクトル列との照合をＣＰＵによって行なう
ことを前記情報処理装置に実行させるプログラム。
【請求項２０】
情報処理装置によって使用された時、
第１のベクトル列を縮小して第１の縮小ベクトル列をＣＰＵによって生成し、
前記第１の縮小ベクトル列と、第２のベクトル列を縮小して生成した第２の縮小ベクトル列をＣＰＵによって照合する
ことを前記情報処理装置に実行させるプログラムを記憶した前記情報処理装置が読み出し可能な可搬記憶媒体。
【請求項２１】
情報処理装置によって使用された時、
第１のベクトル列を縮小して第１の縮小ベクトル列をＣＰＵによって生成し、
前記第１の縮小ベクトル列と、第２のベクトル列を縮小して生成した第２の縮小ベクトル列をＣＰＵによって照合し、
前記第１の縮小ベクトル列と前記第２の縮小ベクトル列との照合の結果、距離が規定値以下の時、前記第１のベクトル列と前記第２のベクトル列との照合をＣＰＵによって行なう
ことを前記情報処理装置に実行させるプログラムを記憶した前記情報処理装置が読み出し可能な可搬記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、認証に用いられるベクトル列の照合の技術に関する。
【０００２】
【従来の技術】
音声、筆跡、署名、血流、歩き方やキーボードの操作の仕方等の生体情報を用いて生体認証を行なう照合装置では、装置が予めベクトル列として記憶、保持している生体情報データと、新たに入力された生体情報を量子化してベクトル列にしたデータとを照合し、それらが同一人物のデータであるかを判定する。
【０００３】
例えば、特許文献１に開示されている署名認証装置では、手書き入力された署名をベクトルデータ化処理部１１ｂによってベクトル列に変換し、これを登録データバッファ１１ｃにベクトル列として予め登録されている登録署名データと１対１照合を行ない、その照合結果に基づいて署名を認証している。
【０００４】
また、特許文献２に開示されている音声認証装置では、特徴抽出処理部１１ｂによって入力音声からその音声区間の特徴データを抽出し、登録データバッファ１１ｃに予め保存されている特徴データと１対１照合を行なう。そして照合の結果、入力された音声と登録されている音声の各特徴データが同一と判断された場合に、同一人物による音声であると認証している。
【０００５】
このような照合装置では、採取毎に長さ（ベクトルの数）が異なる生体情報のベクトル列を、登録されている複数のベクトル列と比較するが、この比較処理は、基本的に２つのベクトル列による１対１照合であり、入力ベクトル列をｎ個の登録ベクトル列と照合する１対ｎ照合を行なうことは、この１対１照合をｎ回行なうことに対応する。
【０００６】
【特許文献１】
特開平２００２−２４５４５８号公報（ｐ．４−５、図２）
【特許文献２】
特開平２００２−２４４６９７号公報（ｐ．４、図２）
【０００７】
【発明が解決しようとする課題】
このような照合装置においては、１対１の照合に十分高速な計算方法を用いたとしても、１対ｎの照合を行なう場合にはｎの大きさによっては実用的な処理速度を得ることができない場合がある。この場合には、ベクトル列をクラスタリングすることである程度回避することができるが、クラスタリングの為にはベクトル列の取り得る分布を正確に把握しなければならず、また分布に偏りが多い時にはうまくクラスタリング出来ない場合もある。よって照合処理の高速化は、大きな課題の１つとなっている。
【０００８】
上記問題点を鑑み、本発明はベクトル列の照合処理における計算量を減らし、高速な照合処理が可能な照合装置、ベクトル列照合法を提供することを課題とする。
【０００９】
【課題を解決するための手段】
上記問題点を解決する為、本発明に基づく照合装置は、第１のベクトル列縮小手段及び第１の照合手段を備える。
第１のベクトル列縮小手段は、第１のベクトル列を縮小して第１の縮小ベクトル列を生成する。
【００１０】
この第１のベクトル列縮小手段は、例えば前記第１のベクトル列内の隣り合うベクトルを、該隣り合うベクトルを代表する代表ベクトルに置き換えることにより前記第１の縮小ベクトルを生成する。
そして第１のベクトル列縮小手段は、例えば前記第１のベクトル列内のベクトルの隣り合う特徴ベクトルのベクトル間距離を算出し、該ベクトル間距離が近い前記隣り合う特徴ベクトルを代表ベクトルに置き換えることにより前記第１の縮小ベクトルを生成する。
【００１１】
或いは、前記第１のベクトル列縮小手段は、例えば前記第１のベクトル列内の隣り合うベクトルのベクトル間距離を算出し、該ベクトル間距離が既定値以下であるベクトルが連続している部分を部分ベクトル列として検出し、該部分ベクトル列を該部分ベクトルを代表する代表ベクトルに置き換えることにより前記第１の縮小ベクトルを生成する。
【００１２】
そして第１のベクトル列縮小手段は、例えば、前記ベクトル間距離の最も小さい値が既定値より大きくなるまで、或いは前記第１のベクトル列内のベクトルの数が既定値以下になるまで、前記隣り合うベクトルを前記代表ベクトルに置き換えることによりベクトル列の縮小を行なう。
【００１３】
第１の照合手段は、前記第１の縮小ベクトル列と、第２のベクトル列を縮小して生成した第２の縮小ベクトル列を照合する。
第１の照合手段は、縮小された第１ベクトル列と第２のベクトル列の照合を行なうので計算量を減少させることが出来る。
【００１４】
また、本発明による照合装置は、複数の前記第２のベクトル列を該第２のベクトル列に対応する前記第２の縮小ベクトル列と共に記憶する記憶手段を更に備える構成としても良い。
更には、前記第１の照合手段による照合結果に基づいて、前記複数の第２のベクトル列から選択して前記第１のベクトル列との照合を行なう第２の照合手段を更に備える構成としてもよい。
【００１５】
この構成の場合、高い照合精度を保ちながら１対複数の照合を実現することが出来る。
【００１６】
【発明の実施の形態】
図１は、第１の実施形態、及び後述する第２及び第３の実施形態における照合装置の構成例を示すブロック図である。
同図の照合装置では、比較・照合を行なう２つのベクトル列に対して、まず縮小処理を行なってベクトル数を減らした後に照合を行なう。これにより照合処理における計算量を減少させることが出来、照合処理速度を向上させることが出来る。尚同図の照合装置を生体認証に用いる場合、その前段に生体認証に用いられる生体情報データが入力される入力部と、この入力部から入力された生体情報データを量子化する等の処理を行ない、特徴ベクトル列を算出する特徴ベクトル算出部を備える構成としても良い。
【００１７】
図１の照合装置は、２つのベクトル列縮小部１−１、１−２及び照合２を有している。
ベクトル列縮小部１−１、１−２は、入力されたベクトル列内の特徴ベクトルの数を減らし、ベクトル列を縮小する。ここで、入力されるベクトル列としては、例えば、本照合装置を音声認識に適用する場合には、認識対象の音声から抽出された特徴ベクトルのベクトル列と、装置に予め記憶されている特徴ベクトルのベクトル列を用いることができる。また、筆跡認証等、他の種類の認証を行う場合は、その認証対象データから抽出された特徴ベクトルなどを用いることができる。
【００１８】
照合部２は、ベクトル列縮小部１によって縮小された２つのベクトル列の比較・照合を行ない、照合結果を出力する。この照合部２による具体的な照合の仕方そのものは、特に限定されるものではなくどのようなものでも利用できるが、一例として特願２００３−９４１６８号「ベクトル系列の比較装置、比較方法、プログラム及び記憶媒体」に示されている方法を示す。
【００１９】
上記特許出願の方法では、まず、照合を行なう２つのベクトル列に対してＤＰマッチングを行なって各特徴ベクトルの間に対応が取れたベクトル列を生成する。そして生成されたこのベクトル列間で互いに対応関係がある特徴ベクトル間の距離ｄを求め、この距離ｄから２つのベクトル列間の類似性を示すベクトル列間距離Ｄを求めることによって照合を行なっている。
【００２０】
尚図１の構成では、照合装置に入力された２つの入力ベクトル列を比較・照合する構成となっているが、入力ベクトルと予めメモリ内に登録してある登録データを比較する構成としても良い。またこの時、登録データに既に縮小処理を施したベクトル列を用いる場合には、図１のようにベクトル列縮小部１を２つ設ける必要は無く、入力ベクトル側にのみ１つ有する構成としても良い。
【００２１】
次にベクトル列縮小部１で行なわれるベクトル列の縮小処理について説明する。
ベクトル列は特徴ベクトルが時系列に並んでいる構成を持つが、ベクトル列縮小部１では、まず入力されたベクトル列の隣り合う特徴ベクトル（以下ベクトルペアという）の間のベクトル間距離を算出する。そして、ベクトル列の中からベクトル間距離の近いベクトルペアを抽出し、このベクトルペアを１つのベクトルに置き換えてゆくことによって、ベクトル列内の特徴ベクトルの数を減らしてゆく。以下縮小処理において、複数のベクトルに代わって置き換えるベクトルを代表ベクトルという。
【００２２】
ｎ個の特徴ベクトルを持ち長さがｎの入力ベクトル列Ｖ＝｛ｖ１  ，ｖ２  ，・・・，ｖｎ  ｝の各特徴ベクトルｖｉ  をｍ個の要素を持つベクトルｖｉ  ＝｛ｖｉ１，ｖｉ２，・・・，ｖｉｎ｝とした時、各ベクトルペアの距離
ｄｉ  ＝ｄｉｓｔ（ｖｉ  ，ｖｉ＋１  ）    ；１≦ｉ≦ｎ−１
の系列は、ｄ＝｛ｄ１  ，ｄ２  ，・・・，ｄｎ−１  ｝となる。尚上式及び以下の説明において、ｄｉｓｔ（ｖｉ  ，ｖｉ＋１  ）は、ベクトルｖｉ  とベクトルｖｉ＋１  のベクトル間距離を示す。
【００２３】
この時に用いるベクトル間距離には様々な定義のものを用いることが出来、距離の定義の仕方は特に限定されない。例えばこのベクトル間距離には、ユークリッド距離が利用できる。ベクトルｖ１  ＝｛ｖ１１，ｖ１２，・・・，ｖ１ｎ｝とｖ２  ＝｛ｖ２２，ｖ２２，・・・，ｖ２ｎ｝との間の距離ｄｉｓｔ（ｖ１  ，ｖ２  ）をユークリッド距離として求める時には（１）式から算出できる。
【００２４】
【数１】
2004326362.tif 000003
【００２５】
またこのときのベクトル間距離には、ハミング距離を使うことも出来る。ハミング距離を用いた時、ベクトルｖ１  とｖ２  の間のベクトル間距離は（２）式から算出できる。
【００２６】
【数２】
2004326362.tif 000004
【００２７】
ベクトル列縮小部１では、ベクトル列内の全てのベクトルペア間のベクトル間距離ｄ１  〜ｄｎ−１  を算出すると、次にこの距離ｄ１  〜ｄｎ−１  の中から最小の距離を選択する。この選択された最小の距離をｄａ  とすると、このベクトル間距離ｄａ  の計算対象となったベクトルペアｖａ  ，ｖａ＋１  が連続して現れるベクトルで最もベクトル間距離の近いペアとなる。よってベクトル列縮小部１ではこのベクトルペアを１つのベクトル（代表ベクトル）に置き換える。
【００２８】
代表ベクトルを生成する方法は様々な方法があるが、以下に例として最も計算が簡単な方法の１つである、それぞれのベクトルを要素毎に加算平均して生成する方法を示す。
ベクトルｖ１  とベクトルｖ２  の要素毎の平均は（３）式で表せる。
ｃｉ  ＝（ｖ１ｉ＋ｖ２ｉ）／２      ；１≦ｉ≦ｍ      ・・・（３）
ここでｃ＝（ｃ１  ，ｃ２  ，・・・，ｃｍ  ）は生成された代表ベクトルである。
【００２９】
ベクトル列縮小部１では、このベクトル間距離ｄが最小となるベクトルペアの抽出処理、及び代表ベクトルへの置き換え処理を繰り返すことでベクトル列の長さを短くしてゆく。そしてベクトル列内のベクトルペアの最小のベクトル間距離が、予め定めておいた値ｅよりも大きくなると縮小処理を終了する。
【００３０】
図２は第１の実施形態における照合装置によって行なわれる処理の例を示すフローチャートである。
同図においてまずステップＳ１として、比較・照合を行なう為に入力された２つのベクトル列に対して、まずベクトル列縮小部１は縮小処理を行ない、次にステップＳ２としてこの縮小されたベクトル列をベクトル列照合部２によって比較照合する。
【００３１】
図３は第１の実施形態における照合装置で行なわれるベクトル列長縮小処理の例を示すフローチャートである。同図の処理は、図２のステップＳ１の処理に対応する。
同図において、ステップＳ１１として、まずベクトル列縮小部１は、入力されたベクトル列中の連続して現れる特徴ベクトル（ベクトルペア）間のベクトル間距離を計算し、最もベクトル間距離の近いベクトルペアを選択する。
【００３２】
次にステップＳ１２として、ベクトル列縮小部１は、ステップＳ１１で選択したベクトルペアのベクトル間距離が指定値ｅより小さく、ベクトル間距離が近いかどうかを判断し、ベクトル間距離が近ければ（ステップＳ１２、Ｙｅｓ）、ステップＳ１３としてこのベクトルペアを代表ベクトルに置き換える。そして、ステップＳ１１に処理を戻して、この置き換えた代表ベクトルと隣り合うベクトルのベクトル間距離を求める。
【００３３】
以降ステップＳ１１〜Ｓ１３の処理を繰り返してベクトル列を縮小してゆく。そして、ステップＳ１２において、ステップＳ１１で選択したベクトルペアのベクトル間距離が指定値ｅより大きく、ベクトル間距離が遠いと判断されると（ステップＳ１２、Ｎｏ）、処理を終了し、縮小されたベクトル列を照合部２に出力する。
【００３４】
照合部２は、この縮小されたベクトル列に対して照合処理を行なうので、照合処理における計算量を減らすことが出来る。特に、音声照合や署名照合では、採取データに似た特徴部分が連続することが多いので、効果を発揮する。
次に第２の実施形態について説明する。
【００３５】
第１の実施形態では、ベクトル列縮小部１によるベクトル列の縮小処理において、最小のベクトル間距離が予め指定した値ｅより大きくなるまで、ベクトルペアを代表ベクトルへ置き換える処理を繰り返していたが、第２の実施形態では縮小処理の完了をベクトル列全体の長さから判断する。
【００３６】
第２の実施形態では、ベクトル列縮小部１は、第１の実施形態と同様に最もベクトル間距離が近いベクトルペアを選択し、代表ベクトルに置き換えてゆく。その結果、ベクトル列が縮小されてゆき、ベクトル列の長さが予め指定した値以下になると処理を終了する。
【００３７】
よってこの第２の実施形態では、予め指定したベクトル列長の値が処理対象としてベクトル列縮小部１に入力されたベクトル列よりも短い場合、このベクトル列長縮小処理によって入力ベクトル列長は定値に揃えられる。よって、照合部２には同じ長さのベクトル列が入力されることになるので、照合部２では、マッチング処理を行なわずに、照合処理として単純に対応する要素ベクトルを比較することが出来る。
【００３８】
例えば、指定したベクトル列長の値をｎとし、ベクトル列縮小部１による縮小処理によって特徴ベクトルの数がｎ個になった２つのベクトル列をＸ＝｛ｘ１  ，ｘ２  ，・・・，ｘｎ  ｝，Ｙ＝｛ｙ１  ，ｙ２  ，・・・，ｙｎ  ｝としたとき、このベクトル列間の距離Ｄは、最も単純な計算の仕方を採用した場合（４）式で算出できる。
【００３９】
【数３】
2004326362.tif 000005
【００４０】
この様に第２の実施形態では、照合処理を行なうベクトル列の長さを揃えられるので、照合処理における計算量を減少させることが出来、照合処理速度を向上させることができる。
図４は第２の実施形態におけるベクトル列縮小部１による処理例を示すフローチャートである。尚第２の実施形態の照合装置で行なわれる処理は、図２に示した第１の実施形態の処理と基本的に同じであり、ステップＳ１の処理に対応する処理部分のみが異なる。
【００４１】
同図において、まずステップＳ２１として、ベクトル列縮小部１は、図３に示した第１の実施形態と同様入力されたベクトル列中のベクトルペアのベクトル間距離を計算し、最もベクトル間距離の近いベクトルペアを選択する。そしてステップＳ２２としてこのベクトルペアを代表ベクトルに置き換える。これにより処理対象となっているベクトル列は縮小され長さが短くなる。
【００４２】
次にベクトル列縮小部１は、ステップＳ２３として、ベクトル列の長さが指定値以下かどうかを判断し、指定値より大きければ（ステップＳ２３、Ｎｏ）、まだ縮小する必要があるので処理をステップＳ２１に戻して、置き換えた代表ベクトルと隣り合うベクトルのベクトル間距離を求める。
【００４３】
以降ステップＳ２１〜Ｓ２３の処理をベクトル列の長さが指定値以下になるまで繰り返し、ステップＳ２３においてベクトル列の長さが指定値以下と判断されると（ステップＳ２３、Ｎｏ）、処理を終了し、代表ベクトルに置き換えることによって縮小されたベクトル列を照合部２に出力する。
【００４４】
この第２の実施形態では、ベクトル列長を縮小すると共に、照合を行なうベクトル列の長さを揃えるので、第１の実施形態より更に照合にかかる計算量を削減することが出来る。
次に第３の実施形態について説明する。
【００４５】
第１及び第２の実施形態では、最もベクトル間距離の近い隣り合ったベクトルペアから代表ベクトルに置き換えていたが、第２の実施形態ではベクトル間距離が指定値以下の特徴ベクトルが連続する部分ベクトル列をまとめて代表ベクトルに置き換える。これにより、第１及び第２の実施形態のベクトル列縮小部１による縮小処理より、より高速にベクトル列の縮小処理を行なうことが出来る。
【００４６】
第３の実施形態のベクトル列縮小部１では、第１及び第２の実施形態と同様、まず、入力ベクトル列の全ての隣り合ったベクトル間のベクトル間距離を求める。
次に算出されたベクトル間距離列から、指定値以下のベクトル距離が連続する部分を部分ベクトル列として検出する。そして、検出された部分ベクトル列を代表ベクトルに置き換える。
【００４７】
例えば、部分ベクトル列内のベクトルを要素毎に平均を取って代表ベクトルとするのであれば、部分ベクトル列をＶ＝｛ｖａ  ，ｖａ＋１  ，・・・，ｖｂ  ｝、各ベクトルをｖｉ  ＝｛ｖｉ１，ｖｉ２，・・・，ｖｉｎ｝とすると、代表ベクトルｃ＝｛ｃ１  ，ｃ２  ，・・・，ｃｎ  ｝のベクトル要素ｃｉ  （ｉ＝１，・・・，ｎ）は、（５）式より算出できる。
【００４８】
【数４】
2004326362.tif 000006
【００４９】
ベクトル列縮小部１は、この部分ベクトル列の代表ベクトルへの置き換えを、検出された全ての部分ベクトル列に対して行なうことによって、入力ベクトル列の縮小を実現する。
この第３の実施形態では、指定値以下のベクトル間距離が連続する部分ベクトル列をまとめて代表ベクトルに置き換えるので、第１及び第２の実施形態に示した場合より、縮小処理に要する計算量を削減することが出来、より高速な処理を実現することが出来る。
【００５０】
図５は第３の実施形態における照合装置で行なわれるベクトル列長縮小処理の例を示すフローチャートである。尚第３の実施形態の照合装置で行なわれる処理も、図２に示した第１の実施形態の処理と基本的に同じであり、ステップＳ１の処理に対応する処理部分のみが異なる。
【００５１】
同図において、まずベクトル列縮小部１は、ステップＳ３１として、第１及び第２の実施形態と同様入力されたベクトル列中のベクトルペアのベクトル間距離を算出する。
次にベクトル列縮小部１は、ステップＳ３２としてベクトル間距離が指定値ｅ以下のベクトル間距離のベクトルが連続する部分ベクトル列を検出する。そして検出された部分ベクトル列の中から１つを選択し、ステップＳ３３としてこの選択された部分ベクトル列を１つの代表ベクトルに置き換える。
【００５２】
そしてステップＳ３４として、ステップＳ３２で検出した部分ベクトル列全てに対して処理を行ったかどうかを判断し、まだ処理を行っていない部分ベクトル列が存在していれば（ステップＳ３４、Ｎｏ）、ステップＳ３５としてその中から次に処理を行なう部分ベクトル列を選択し、処理をステップＳ３３に戻す。
【００５３】
以降ステップＳ３１〜Ｓ３３の処理を繰り返して、ステップＳ３４においてステップＳ３１で検出された全ての部分ベクトル列に対して処理を完了したと判断すると（ステップＳ３４、Ｙｅｓ）、処理を終了し、代表ベクトルに置き換えることによって縮小されたベクトル列を照合部２に出力する。
【００５４】
図６は、図４のステップＳ３２の部分ベクトル検出処理の詳細を示すフローチャートである。尚同図及び以下の説明では、入力ベクトル列をＶ＝｛ｖ１  ，ｖ２  ，・・・，ｖｎ  ｝、最大のベクトル間距離の指定値をｅとした時の部分ベクトル列検出の処理例を示している。
【００５５】
同図において、ステップＳ４１としてベクトル列縮小部１は、まずカウンタｉに初期値として１を、またカウンタｊに初期値として２を設定する。
次に、ベクトル列縮小部１は、カウンタ値ｊが入力ベクトルの長さｎより大きくないかどうかを判断し、ｎより長くなければ（ステップＳ４２、Ｎｏ）、隣り合うベクトルｖｊ−１  とｖｊ  のベクトル間距離を算出してこのベクトル間距離ｄｉｓｔ（ｖｊ−１  ，ｖｊ  ）が指定値ｅより小さければ（ステップＳ４３、Ｙｅｓ）、ステップＳ４７としてカウンタ値ｊを１つインクリメントした後処理をステップＳ４２に戻す。
【００５６】
また、ステップＳ４３で隣り合うベクトルｖｊ−１  とｖｊ  のベクトル間距離ｄｉｓｔ（ｖｊ−１  ，ｖｊ  ）が指定値ｅより大きければ（ステップＳ４３、Ｎｏ）、ステップＳ４４としてベクトルｖｉ  からｖｊ  までを本処理で検出する部分ベクトルとして記録する。そしてステップＳ４５としてカウンタｉにカウンタｊの値を設定し、またカウンタｊの値を１つインクリメントした後処理をステップＳ４２に戻す。
【００５７】
以降カウンタｊの値が入力ベクトルの長さｎより大きくなるまでステップＳ４２〜Ｓ４５の処理を繰り返し、ステップＳ４２においてカウンタｊの値が入力ベクトルの長さｎより大きくなると（ステップＳ４２、Ｎｏ）、ステップＳ４６としてベクトルｖｉ  からｖｊ  までを本処理で検出する部分ベクトルとして記録した後処理を終了する。
【００５８】
尚上記例では、検出された部分ベクトル列と置き換える代表ベクトルに部分ベクトルを要素毎に平均値を求めて生成したベクトルを用いていたが、本実施形態で代表ベクトルとして用いることの出来るベクトルは、置き換えられるベクトル列を代表できるものさえあればこれに限定されるものではなく、他の方法で求めたベクトルを用いても良い。
【００５９】
例えば置き換えられる部分ベクトル列の中のベクトルで、時間軸上において最も中央に近い位置にあるベクトルを代表ベクトルにしても良い。この場合部分ベクトルＶ＝｛ｖａ  ，ｖａ＋１  ，・・・，ｖｂ  ｝の代表ベクトルｃ＝｛ｃ１  ，ｃ２  ，・・・，ｃｎ  ｝のベクトル要素ｃｉ  （ｉ＝１，・・・，ｎ）は、（６）式より算出できる。
ｃｉ  ＝ｖｋｉ      ；ｋ＝（ａ＋ｂ）／２  １≦ｉ≦ｎ・・・（６）
この様に代表ベクトルを求めることによって、平均値などの演算を行なうことにより発生する「データの鈍り」を回避することが出来、更には縮小処理に要する計算量を削減することが出来る。
【００６０】
次に第４の実施形態について説明する。
第４の実施形態の照合装置は、１つの入力データを複数の登録データと参照することができるようにしたものである。
図７は、第４の実施形態における入力ベクトル列を複数の登録ベクトル列と照合する１対ｎ照合装置の構成例を示すブロック図である。
【００６１】
第４の実施形態の照合装置では、入力ベクトル列と比較・照合する複数の登録ベクトル列をその登録ベクトル列に対して上記した縮小処理を施した縮小登録ベクトル列と共に記憶・保持している。そして縮小処理を行った縮小入力データをこの縮小登録ベクトル列とまず比較して、照合度の高い縮小登録ベクトル列に対応する登録データと縮小処理を施していない入力データとで、再度比較・照合処理を行なう。これにより照合の精度を落とすことなく、照合処理における計算量を減少させることが出来、照合処理速度を向上させることが出来る。
【００６２】
図７に示す構成において、照合装置は、ベクトル列縮小部１１、縮小ベクトル列照合部１２、ベクトル列照合部１３、登録データベース部１４及び登録処理部１５を備えている。
ベクトル列縮小部１１は、図２のベクトル列縮小部１と基本的に同一の機能を果たすもので、入力されたベクトル列に対して縮小処理を行なう。縮小ベクトル列照合部１２は、ベクトル列縮小部１１によって縮小処理が施された縮小入力ベクトル列と、登録データベース１４に登録されている縮小登録ベクトル列との比較・照合処理を行なう。ベクトル列照合部１３は、縮小処理が施されていない入力ベクトル列と登録データベース１４内の縮小処理が施されていない登録ベクトル列との比較・照合を行なう。登録データベース部１４は、入力ベクトル列と比較・照合を行なう登録ベクトル列を、登録ベクトル列に対して縮小処理を施した縮小登録ベクトル列と共にデータベース化して記憶する記憶ユニットである。登録処理部１５は、登録データベース１４からの登録ベクトル列の読み出しや、登録を行なう。
【００６３】
図７の照合装置では、入力ベクトル列が入力されるとまずこれをベクトル列縮小部１１によって、第１乃至第３の実施形態で示した縮小処理を行って縮小入力ベクトル列を生成する。そして縮小ベクトル列照合部１２は、この縮小入力ベクトル列を登録処理部１５が順次登録データベース１４から読み出してくる縮小登録ベクトル列というと比較・照合を行なう。そして縮小ベクトル列照合部１２は、その照合の結果、ベクトル列間距離が特定値以下であったものを候補としてベクトル列照合部１３に通知し、ベクトル列照合部１３は、縮小ベクトル列照合部１２から通知された登録ベクトル列を登録処理部１５を介して登録データベース１４から読み出し、これをベクトル列縮小部１１による縮小処理を行っていない入力ベクトル列と比較・照合し、照合結果を出力する。
【００６４】
これにより、入力ベクトル列を複数の登録ベクトル列と照合する場合においても、縮小ベクトル列照合部１２による縮小ベクトル列との比較照合によって照合を行なう登録ベクトル列を絞った後に、ベクトル列照合部１３によって照合を行なうので、照合処理における計算量を減少させることが出来、照合処理速度を向上させることが出来る。またベクトル列照合部１３によって、縮小処理を施す前のベクトル列同士を比較・照合するので、照合精度が落ちることは無い。
【００６５】
また高速な演算で候補となる登録ベクトル列を選択し、精度の高い照合で結果を出すことにより、ベクトル列のクラスタリングが行ないにくい場合でも効率よく１対ｎ照合を行なうことが出来る。
図８は第４の実施形態における照合装置によって行なわれる処理例を示すフローチャートである。
【００６６】
同図において、まずステップＳ５１として、比較・照合を行なう為に入力された入力ベクトル列に対して、まずベクトル列縮小部１１が縮小処理を行ない、ステップＳ５２として、ベクトル列照合部２はこの縮小された縮小入力ベクトル列を登録データベース１４に縮小処理が施された状態で登録されている縮小登録ベクトル列の１つと比較照合する。
【００６７】
ステップＳ５２での照合結果、２つのベクトル列のベクトル列間距離が指定値以下かどうかを判断し、その結果指定値以下の場合（ステップＳ５２、Ｙｅｓ）には、その縮小登録ベクトル列の元となっている登録ベクトル列を候補としてメモリに登録した後に、また指定値より大きい場合（ステップＳ５２、Ｎｏ）にはそのまま、ステップＳ５４に処理を移す。
【００６８】
ステップＳ５４では、登録処理部１５が次の縮小登録ベクトル列を指定して登録データベース１４から読み出した後ステップＳ５２に処理を移し、全ての縮小登録ベクトル列を指定して、照合し終わるまで（ステップＳ５５、Ｎｏ）、ステップＳ５２〜Ｓ５５の処理を繰り返す。
【００６９】
ステップＳ５５において、登録処理部１５が全ての縮小登録ベクトルが指定して登録データベース１４から読み出し終わったと判断すると（ステップＳ５５、Ｙｅｓ）、ステップＳ５７として、ベクトル列照合部１３は、ステップＳ５６で候補として記録された登録ベクトル列の１つと縮小処理を施していない入力ベクトル列を照合する。
【００７０】
このベクトル列照合部１３による照合の結果、２つのベクトル列が同一人物の認証情報によるものであると判定されなければ（ステップＳ５８、Ｎｏ）、ステップＳ５９としてベクトル列照合部１３はステップＳ５６で候補として記録された登録ベクトル列の中から次の登録ベクトル列を登録処理部１５に指定して読み出させた後処理をステップＳ５７に戻す。またステップＳ５８でベクトル列照合部１３による照合の結果、同一人物のものと判定されれば、照合ＯＫとなり、入力されたデータが照合された旨等を照合結果として出力して処理を終了する。
【００７１】
またステップＳ５７〜ステップＳ６０の処理を、候補となった全ての登録ベクトルに対して行ない（ステップＳ６０、Ｎｏ）、候補となった全ての登録ベクトルに対して２つのベクトル列が同一人物の認証情報によるものであると判定されなければ（ステップＳ６０、Ｙｅｓ）、照合ＮＧとなり、入力されたデータが照合されなかった旨を照合結果として出力して処理を終了する。
【００７２】
図９は、本実施形態における照合装置をソフトウエアによって実現した場合の情報処理システムの環境図である。
本実施形態の照合装置を情報処理システム上でプログラムを実行することによって実現した場合、情報処理システムは、図９の様にＣＰＵ２１、主記憶装置２２、ハードディスク等の補助記憶装置２３、ディスプレイ、キーボード等の入出力装置（Ｉ／Ｏ）２４、モデム等のネットワーク接続装置２３及びディスク、磁気テープなどの可搬記憶媒体から記憶内容を読み出す媒体読取り装置２６を有し、これらが互いにバス２８により接続される構成を備えている。
【００７３】
図９の情報処理システムでは、媒体読取り装置２６により磁気テープ、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ等の記憶媒体２７に記憶されているプログラム、データを読み出し、これを主記憶装置２２または補助記憶装置２３にダウンロードする。そしてこのプログラムやデータに基づいて、ＣＰＵ２１が入力されたデータを主記憶装置２２や補助記憶装置２３に記憶したり、登録データを主記憶装置２２や補助記憶装置２３から読み出したり、両者を元に主記憶装置２２をワークエリアとしてマッチング処理やベクトルの合成、ベクトル間距離やベクトル列間距離の算出等を行なうなどして、これまで説明してきた本実施形態による各処理は、ソフトウエア的に実現される。
【００７４】
また、図９のコンピュータシステムでは、フレキシブルディスク等の記憶媒体２７を用いてアプリケーションソフトの交換が行われる場合がある。よって、本発明は、照合装置、ベクトル列照合方法に限らず、コンピュータにより使用されたときに、上述した本発明の実施形態の機能をコンピュータに行なわせるためのコンピュータ読み出し可能な記憶媒体２７として構成することもできる。
【００７５】
この場合、「記憶媒体」には、例えば図１０に示されるように、ＣＤ−ＲＯＭ、フレキシブルディスク（あるいはＭＯ、ＤＶＤ、リムーバブルハードディスク等であってもよい）等の媒体駆動装置３７に脱着可能な可搬記憶媒体３６や、ネットワーク回線３３経由で送信される外部の装置（サーバ等）内の記憶手段（データベース等）３２、あるいは情報処理装置３１の本体３４内のメモリ（ＲＡＭ又はハードディスク等）３５等が含まれる。可搬記憶媒体３６や記憶手段（データベース等）３２に記憶されているプログラムは、本体３４内のメモリ（ＲＡＭ又はハードディスク等）３５にロードされて、実行される。
【００７６】
また、既に説明した各記憶媒体や記憶手段としては、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の他にも、例えば、Ｂｌｕ−ｒａｙ  Ｄｉｓｃ（登録商標）やＡＯＤ（Ａｄｖａｎｃｅｄ  Ｏｐｔｉｃａｌ  Ｄｉｓｃ）などの青色レーザーを用いた次世代光ディスク記憶媒体、赤色レーザーを用いるＨＤ−ＤＶＤ９、青紫色レーザーを用いるＢｌｕｅ  Ｌａｓｅｒ  ＤＶＤなど、今後開発される種々の大容量記憶媒体を用いて本発明を実施することも可能である。
【００７７】
本実施形態のベクトル列の照合装置は、様々な分野の照合装置に適用できるが、特に、音声照合や署名照合では、採取データに似た特徴部分が連続することが多いので、効果を発揮する。
【００７８】
【発明の効果】
本発明によれば、ベクトル列の照合処理における計算量を減らすことが出来、高速な照合処理が可能となる。
また１対複数のベクトル列の照合においても、高い照合精度を保ちながら１対複数の照合を実現することが出来、ベクトル列のクラスタリングが行ないにくい場合でも効率よく１対複数の照合を行なうことが出来る。
【図面の簡単な説明】
【図１】第１、第２及び第３の実施形態における照合装置の構成例を示すブロック図である。
【図２】第１、第２及び第３の実施形態における照合装置によって行なわれる処理の例を示すフローチャートである。
【図３】第１の実施形態における照合装置によって行なわれるベクトル列長縮小処理の例を示すフローチャートである。
【図４】第２の実施形態におけるベクトル列縮小部による処理例を示すフローチャートである。
【図５】第３の実施形態における照合装置によって行なわれるベクトル列長縮小処理の例を示すフローチャートである。
【図６】部分ベクトル検出処理の詳細を示すフローチャートである。
【図７】第４の実施形態における照合装置の構成例を示すブロック図である。
【図８】第４の実施形態における照合装置によって行なわれる処理例を示すフローチャートである。
【図９】情報処理システムのシステム環境図である。
【図１０】媒体例を示す図である。
【符号の説明】
１、１１  ベクトル列縮小部
２  照合部
１２  縮小ベクトル列照合部
１３  ベクトル列照合部
１４  登録データベース
１５  登録処理部
２１  ＣＰＵ
２２  主記憶装置
２３  補助記憶装置
２４  入出力装置
２５  ネットワーク接続装置
２６  媒体読取装置
２７  記憶媒体
２８  バス
３１  情報処理装置
３２  記憶手段
３３  ネットワーク回線
３４  本体
３５  メモリ
３６  可搬記憶媒体
３７  媒体駆動装置
【図１】
2004326362.tif 000007
【図２】
2004326362.tif 000008
【図３】
2004326362.tif 000009
【図４】
2004326362.tif 000010
【図５】
2004326362.tif 000011
【図６】
2004326362.tif 000012
【図７】
2004326362.tif 000013
【図８】
2004326362.tif 000014
【図９】
2004326362.tif 000015
【図１０】
2004326362.tif 000016