(57)【要約】【課題】リニアサーチは多数の登録データと照合データを照合する必要があるので、処理時間がかかり、属性情報の比較においての誤りが避けられない。【解決手段】複数の特徴を用意し、すべての登録データと特徴の組について計算された特徴量からなる特徴量テーブルを生成しておき、照合データの特徴量を計算し、当該特徴量と特徴量テーブルから次に照合すべき登録データの順序を制御し、当該登録データと照合データの照合度を計算し、前記照合度をしきい値と比較して、当該照合データが登録データのどれに当たるかを決定する。また、特徴量テーブルの代わりに参照データと相互相関テーブルを用いることもできる。【選択図】図２
2010244511.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを用いて照合データが複数（Ｎ個。Ｎは２以上の自然数）の登録データのどれに当たるかを決定する１対Ｎ認証装置であって、
前記登録データとは別に複数の特徴を用意し、すべての登録データと特徴の組について計算された特徴量からなる特徴量テーブルを生成する特徴量テーブル生成手段と、
照合データの特徴量を計算する照合データ特徴量計算手段と、
該照合データ特徴量計算手段にて計算された特徴量と前記特徴量テーブルとから次に照合すべき登録データの順序を制御する照合順序制御手段と、
該照合順序制御手段にて制御された照合順序にしたがって登録データと照合データの照合度を計算する登録データ照合データ照合度計算手段と、
該登録データ照合データ照合度計算ステップにて計算された照合度を予め定められた閾値と比較して、当該照合データが登録データのどれに当たるかを決定する認証手段と
からなる１対Ｎ認証装置。
【請求項２】
コンピュータを用いて照合データが複数（Ｎ個。Ｎは２以上の自然数）の登録データのどれに当たるかを決定する１対Ｎ認証方法であって、
前記登録データとは別に複数の特徴を用意し、すべての登録データと特徴の組について計算された特徴量からなる特徴量テーブルを生成する特徴量テーブル生成ステップと、
照合データの特徴量を計算する照合データ特徴量計算ステップと、
該照合データ特徴量計算ステップにて計算された特徴量と前記特徴量テーブルとから次に照合すべき登録データの順序を制御する照合順序制御ステップと、
該照合順序制御ステップにて制御された照合順序にしたがって登録データと照合データの照合度を計算する照合度計算ステップと、
該照合度計算ステップにて計算された照合度を予め定められた閾値と比較して、当該照合データが登録データのどれに当たるかを決定する認証ステップと
からなる１対Ｎ認証方法。
【請求項３】
コンピュータを用いて照合データが複数（Ｎ個。Ｎは２以上の自然数）の登録データのどれに当たるかを決定する１対Ｎ認証装置であって、
前記登録データとは別に複数の参照データを用意し、すべての登録データと参照データの組について計算された照合度からなる相互相関テーブルを生成する登録データ参照データ相互相関テーブル生成手段と、
照合データと参照データの照合度を計算する照合データ参照データ照合度計算手段と、
該照合データ参照データ照合度計算手段にて計算された照合度と前記登録データ参照データ相互相関テーブルとから次に照合すべき登録データの順序を制御する照合順序制御手段と、
該照合順序制御手段にて制御された照合順序にしたがって登録データと照合データの照合度を計算する登録データ照合データ照合度計算手段と、
該登録データ照合データ照合度計算ステップにて計算された照合度を予め定められた閾値と比較して、当該照合データが登録データのどれに当たるかを決定する認証手段と
からなる１対Ｎ認証装置。
【請求項４】
コンピュータを用いて照合データが複数（Ｎ個。Ｎは２以上の自然数）の登録データのどれに当たるかを決定する１対Ｎ認証方法であって、
前記登録データとは別に複数の参照データを用意し、すべての登録データと参照データの組について計算された照合度からなる相互相関テーブルを生成する登録データ参照データ相互相関テーブル生成ステップと、
照合データと参照データの照合度を計算する照合データ参照データ照合度計算ステップと、
該照合度計算ステップにて計算された照合度と前記登録データ参照データ相互相関テーブルとから次に照合すべき登録データの順序を制御する照合順序制御ステップと、
該照合順序制御ステップにて制御された照合順序にしたがって登録データと照合データの照合度を計算する登録データ照合データ照合度計算ステップと、
該登録データ照合データ照合度計算ステップにて計算された照合度を予め定められた閾値と比較して、当該照合データが登録データのどれに当たるかを決定する認証ステップと
からなる１対Ｎ認証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ICカードやID番号の入力を必要としない1対N認証システムにおいて、登録データと照合データの照合に時間のかかる指静脈や指紋などの生体画像データの照合の高速化に関するものである。本発明は銀行等のATMシステムや入退出管理等のセキュリティシステムの基礎技術として使われる。
【背景技術】
【０００２】
従来の技術の一つは、蓄えられた登録データを先頭から一つずつ順番に取り出し、照合データと照合し、照合度の高い登録データを検出するというリニアサーチ（総当たり法）である。この手法は平均として全登録データの半分と照合する必要があり、処理時間がかかる。
【０００３】
また、リニアサーチにおいて、各登録データの属性情報をあらかじめ抽出しておき、時間のかかる照合の前に照合データの属性情報と比較し、似ている登録データだけを選び出して照合することにより、処理を高速化するという改良がよく行われている。属性情報は、例えば、特許文献１では画像データの濃度ヒストグラムのピークが用いられている。
特許文献２及び非特許文献１では、複数の登録データから二つを選ぶすべての組み合わせに対して計算した照合度による相互相関テーブルをあらかじめ作成しておき、最初の登録データと照合データの照合度を算出し、以後、照合度と相互相関テーブルを用いて次に照合すべき登録データの順序を制御して、この登録データと照合データの照合度を算出することを繰り返す手法が記述されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−１４１６８０号公報
【特許文献２】特許３０５３６０７号公報
【非特許文献】
【０００５】
【非特許文献１】T. Maeda, M. Matsushita and K. Sasakawa：Identification Algorithm Using a Matching Score Matrix：IEICE TRANS. INF. & SYST., VOL.E84-D, NO.7 July 2001
【発明の概要】
【発明が解決しようとする課題】
【０００６】
リニアサーチは多数の登録データと照合する必要があるので、時間がかかり、また、属性情報の比較において誤りが避けられないという課題があった。
また、相互相関テーブルを用いる手法は、登録データの数の自乗個の要素からなる相互相関テーブルを蓄えるために莫大なメモリを必要とするという強い制限があった。
さらに、総当り法でも相関テーブルを用いる手法でも、繰返し登録データとの照合が発生するので、この回数にほぼ比例して他人受入率が悪化した。
本発明の目的は、スピードも速く、しかも誤りの少ない１対Ｎ認証システム及び１対Ｎ認証方法を提供することにある。
【課題を解決するための手段】
【０００７】
上述した課題を解決するために、本発明に係る１対Ｎ認証方法は、複数の特徴を用意し、すべての登録データと特徴の組について計算された特徴量からなる特徴量テーブルを生成する特徴量テーブル生成ステップと、照合データの特徴量を計算する称号データ特徴量計算ステップと、当該特徴量と特徴量テーブルから次に照合すべき登録データの順序を制御する照合順序制御ステップと、当該登録データと照合データの照合度を計算する照合度計算ステップと、前記照合度をしきい値と比較して、当該照合データが登録データのどれに当たるかを決定する認証ステップと、からなるものである。
前記特徴量テーブルを生成する際の前記特徴の数をＮ以下の個数から選んだものとする。
前記特徴量テーブルを生成する際に、生成された特徴量テーブルの大きさが所望の範囲になるように、特徴の個数を増減して特徴量テーブルを生成することが望ましい。
前記特徴量テーブルを生成する際の前記特徴は、人工的に生成されたものとすることができる。
前記特徴量テーブルを生成する際に登録データ及び特徴の一つ一つについて特徴量を計算して照合データベクトルを生成しそれから一次元の波形を作り、前記照合データ特徴量を計算する際に照合データの特徴量を計算して照合データベクトルを生成しそれから一次元の波形を作り、前記照合順序を制御する際に前記二つの手段が生成した一次元の波形に着目しそれらの部分波形を切り出してマッチングを行い、最もマッチしている登録データを選び出すことができる。
さらに、前記認証により決定できなかった場合に、前記照合順序の制御により切り出した部分波形を拡張して、部分波形のマッチングをやり直すことができる。
また、前記「特徴」を「参照データ」に、前記「特徴量テーブル」を「相互相関テーブル」に、前記「特徴量」を「参照データとの照合度」に、前記「登録データの特徴量」を「登録データと参照データとの照合度」に、前記「照合データの特徴量」を「照合データと参照データとの照合度」に、置き換えた認証方法を提供することもできる。
その場合、参照データの数をＮ以下の個数から選んだものとできる。
生成された登録データ参照データ相互相関テーブルの大きさが所望の範囲になるように、参照データの個数を増減して登録データ参照データ相互相関テーブルを生成することができる。
前記参照データは、人工的に生成されたものとすることができる。
前記参照データは、乱数を用いて生成されたものとすることができる。
前記相互相関テーブルは、登録データを引数とする複数の任意の関数によって算出される実数値の相互相関テーブルとすることができる。
一次元の波形によるマッチングによる認証、認証失敗の場合の部分波形の拡張によるマッチングのし直しについても、同様である。
したがって、
コンピュータを用いて照合データが複数（Ｎ個。Ｎは２以上の自然数）の登録データのどれに当たるかを決定する１対Ｎ認証方法であって、
前記登録データとは別に複数の参照データを用意し、すべての登録データと参照データの組について計算された照合度からなる相互相関テーブルを生成する登録データ参照データ相互相関テーブル生成ステップと、
照合データと参照データの照合度を計算する照合データ参照データ照合度計算ステップと、
該照合度計算ステップにて計算された照合度と前記登録データ参照データ相互相関テーブルとから次に照合すべき登録データの順序を制御する照合順序制御ステップと、
該照合順序制御ステップにて制御された照合順序にしたがって登録データと照合データの照合度を計算する登録データ照合データ照合度計算ステップと、
該登録データ照合データ照合度計算ステップにて計算された照合度を予め定められた閾値と比較して、当該照合データが登録データのどれに当たるかを決定する認証ステップと
からなる１対Ｎ認証方法を提供することができる。
さらに、この認証方法を、利用者識別子の入力なしに利用者の複数部位の生体情報を利用して利用者を識別することに応用すると、
前記登録データは、各利用者の複数部位の生体情報をそれぞれ登録した第一部位の登録データと第二部位の登録データを有するものであって、
前記登録データ参照データ相互相関テーブル生成ステップにおいて生成する前記相互相関テーブルは、全利用者の第一部位の登録データと参照データとの組について計算された照合度からなる第一相互相関テーブルと、全利用者の第二部位の登録データと参照データとの組について計算された照合度からなる第二相互相関テーブルとを有するものであって、
前記照合データ参照データ照合度計算ステップは、利用者を認証する時点において、利用者の複数部位のうちの第一部位の生体情報を取得して、これを第一部位の照合データとして全参照データとの照合度ベクトルを計算し、
前記照合順序制御ステップは、前記第一相互相関テーブルを用いて、先に計算した第一の照合データと参照データの照合度ベクトルとの類似度の高い登録データを選択して、次に照合すべき第一部位の登録データの順序を制御し、
前記登録データ照合データ照合度計算ステップは、該照合順序制御ステップにて制御された照合順序にしたがって前記第一部位の登録データと前記第一部位の照合データとの照合度を計算し、
前記認証ステップが、閾値比較により同一生体情報と判断できれば利用者を認証し、
同一生体情報と認証できなければ、さらに、
利用者の複数部位のうちの第二部位の生体情報を取得して、これを第二部位の照合データとして全参照データとの照合度ベクトルを計算する第二部位照合データ参照データ照合度計算ステップと、
前記第二相互相関テーブルを用いて、先に計算した第二の照合データと参照データの照合度ベクトルとの類似度の高い第二部位の登録データを選択して、次に照合すべき第二部位の登録データの順序を制御する第二部位照合順序制御ステップと、
該第二部位照合順序制御ステップにて制御された照合順序にしたがって第二部位の登録データと第二部位の照合データとの照合度を計算する第二部位登録データ照合データ照合度計算ステップと、
閾値比較により同一生体情報と判断でき、さらに該第二部位の登録データを所有する当該利用者の第一部位の登録データと前記第一部位の照合データとが同一の生体情報と判断できることを条件に、利用者を認証する第二部位認証ステップと
を有する１対Ｎ認証方法を提供できる。
さらにまた、
利用者識別子の入力なしに利用者の複数部位の生体情報を利用して利用者を識別する認証方法であり、
前記登録データは、各利用者の複数部位の生体情報をそれぞれ登録した第一部位の登録データと第二部位の登録データを有するものであって、
前記登録データ参照データ相互相関テーブル生成ステップにおいて生成する前記相互相関テーブルは、全利用者の複数部位の生体情報を一つにまとめて登録データと参照データとの組について計算された照合度からなる相互相関テーブルと、利用者識別子から該相互相関テーブルのインデックスを求める利用者識別子インデックステーブルと、該相互相関テーブルのインデックスから利用者識別子を求めるインデックス利用者識別子テーブルとを有するものであって、
前記照合データ参照データ照合度計算ステップは、利用者を認証する時点において、利用者の複数部位のうちの利用者が任意に選んだ部位の生体情報を取得して、これを第一部位の照合データとして全参照データとの照合度ベクトルを計算し、
前記照合順序制御ステップは、前記相互相関テーブルを用いて、先に計算した照合データと参照データの照合度ベクトルとの類似度の高い登録データを選択して、次に照合すべき登録データの順序を制御し、
前記登録データ照合データ照合度計算ステップは、該照合順序制御手段にて制御された照合順序にしたがって前記登録データと前記第一部位の照合データとの照合度を計算し、
前記認証ステップが、閾値比較により同一生体情報と判断できれば利用者を認証し、
同一生体情報と認証できなければ、さらに、利用者の複数部位のうちの利用者が任意に選んだ第二部位の生体情報を取得して、これを第二部位の照合データとして全参照データとの照合度ベクトルを計算する第二部位照合データ参照データ照合度計算ステップと、
前記相互相関テーブルを用いて、先に計算した照合データと参照データの照合度ベクトルとの類似度の高い登録データを選択して、次に照合すべき登録データの順序を制御する第二部位照合順序制御ステップと、
該照合順序制御ステップにて制御された照合順序にしたがって前記登録データと前記第二部位の照合データとの照合度を計算する第二部位登録データ照合データ照合度計算ステップと、
閾値比較により同一生体情報と判断でき、さらに該第二部位の登録データを所有する当該利用者の第一部位の登録データを、前記利用者識別子インデックステーブルと前記インデックス利用者識別子テーブルとを参照して取得し、その第一部位の登録データと前記第一部位の照合データとが同一の生体情報と判断できることを条件に、利用者を認証する第二部位認証ステップと
を有する１対Ｎ認証方法を提供できる。
以上述べた認証方法を構成する一つ一つのステップは、コンピュータプログラムにより提供できるものである。したがって、コンピュータが必要なプログラムを読み込んで動作することを装置と捉えることにより、１対Ｎ認証装置としての提供ができる。
【発明の効果】
【０００８】
本発明によれば、特徴量テーブルを用いて、照合データと似ている登録データを次の照合候補に選び出すことにより、照合の効率的な適用が可能となるので、全体として照合に要する処理時間を短縮できる効果がある。また、照合は特徴の総数の回数まで適用されるので、属性情報を用いる方法と比べて誤りが少なくなるという効果がある。
【０００９】
また、参照データと相互相関テーブルを用いる実施例によれば、登録データとの照合の回数を少なくできるので、処理時間が短くすることができるとともに、属性情報の比較における誤りを避けることができる。参照データの個数を任意に選べるので、相互相関テーブルのメモリの容量を任意に調節することができるとともに、処理時間の上限も制限できる。参照データを人工的に生成したものとしてもよいので、相互相関テーブルの生成が容易になる。
【００１０】
さらに、部分波形ではなく、全参照データと照合データとの照合度を計算、参照データ数の長さの一次元波形の類似度が高い登録データとのみ繰返し照合する実施例によれば、登録データとの繰返し照合回数を減らすことができるので、他人受け入れ率を下げることができる。
【図面の簡単な説明】
【００１１】
【図１】特徴量テーブルと部分波形の概念を説明する図である。（実施形態）
【図２】実施例１のブロック図である。（実施例１）
【図３】実施例１のフローチャートである。（実施例１）
【図４】ステップ３０３・ステップ３０４・ステップ３０５の詳細を示すフローチャートである。（実施例１）
【図５】実施例１の方式とリニアサーチ方式の平均処理時間を示すグラフである。（実施例１）
【図６】相互相関テーブルと部分波形の概念を説明する図である。（実施例１）
【図７】実施例２のブロック図である。（実施例２）
【図８】実施例２のフローチャートである。（実施例２）
【図９】ステップ８０３・ステップ８０４・ステップ８０５の詳細を示すフローチャートである。（実施例２）
【図１０】図１０は、実施例３のフローチャートである。（実施例３）
【図１１】図１１は、実施例４のフローチャートである。（実施例４）
【図１２】図１２は、登録者ＩＤから相関テーブルのインデックスを求めるためのテーブルであるである（実施例４）。
【図１３】図１３は、相関テーブルのインデックスから登録者ＩＤを求めるためのテーブルであるである（実施例４）。
【発明を実施するための形態】
【００１２】
図１の左側にある行列が特徴量テーブルである。行列の縦は登録データに対応し、行列の横は特徴に対応する。行列の要素の値は対応する登録データの特徴量である。この特徴量テーブルの各行に注目して、その要素の値をプロットすると、右列のような一次元の波形になる。照合データについても、特徴量を計算して照合データベクトルを生成し、それから一次元の波形を作ることができる。重要なことは、照合データとある登録データが似ていれば、それぞれの一次元の波形も似ているということである。したがって、早い段階で一次元の波形の似ている登録データを探し出せば、照合が速くできる。
【００１３】
そこで、次の1対N認証のアルゴリズムが考えられる。
(1) 左端の部分波形を切り出して、マッチングを行い、最もマッチしている登録データを選び出して、それと照合データとを照合する。
【００１４】
(2) もし照合が成功しなかったなら、部分波形を右方向に拡張して、部分波形のマッチングを行い、最もマッチしている登録データを選び出して、それと照合データとを照合するということを照合が成功するまで繰り返す。
【００１５】
特徴の総数をNとすると、特徴量テーブルの各行と照合データベクトルはN次元特徴空間の点であり、部分波形はN次元特徴空間の部分空間の点であると考えられる。したがって、上記のアルゴリズム(1)は部分空間での照合データベクトルの点と最も“近い”登録データの点を探索し、その登録データと照合データとを照合している。また、アルゴリズム(2)はもし照合が成功しなかったなら、部分空間の次元を一つ増やし、同様の登録データの点を探索し、その登録データと照合データとを照合するということを照合が成功するまで繰り返している。
【実施例１】
【００１６】
図２は実施例１のブロック図である。特徴部２０１は登録データや照合データと組合される複数の特徴を蓄える。登録データ部２０２は特徴と組合わされたり、照合データと比較されたりする複数の登録データを蓄える。特徴量計算A部２０３は特徴部２０１から特徴を、登録データ部２０２から登録データをそれぞれ一つずつ読み込み、それらから特徴量を計算する。特徴量計算B部２０４は特徴部２０１から特徴を一つ読み込み、入力された照合データと組合わされて特徴量を計算する。照合処理部２０５は登録データ部２０２から登録データを一つ読み込み、入力された照合データとの照合度を計算する。特徴量テーブル部２０６は特徴量計算A部で計算された特徴量を行列の形式で蓄える。照合判定部２０７は照合処理部２０５で計算された照合度をしきい値と比較して、照合データがどの登録データに対応するかを判定する。登録データ読み出し部２０８は特徴量計算B部２０４で計算された特徴量と特徴量テーブル部２０８に蓄えられている特徴量テーブルから、登録データ部２０２から次に照合すべき登録データを決定する。
【００１７】
1対N認証の処理の前に、以下のようにして、あらかじめ特徴量テーブルを生成しておく。特徴量計算A部２０３は、すべてのn1とn2について特徴部２０１からn1番目の特徴Fn1を、登録データ部２０２からn2番目の登録データEn2をそれぞれ一つずつ読み込み、それらの特徴量F(En2, Fn1)を計算して、特徴量テーブル部２０６に渡し、特徴量テーブルを生成する。
【００１８】
図３は本発明の1対N認証の一実施例のアルゴリズムを示すフローチャートである。まずステップ３０１でカウンタnを１にする。次にステップ３０２でカウンタnが参照データの総数nmax以内か判定する。以内でなければ、照合は不成功となって処理を終了する。以内であれば、特徴量計算B部２０４で照合データVuとn番目の特徴Fnの特徴量F(Vu, Fn)を計算する（ステップ３０３）。次に登録データ読み出し部２０８で、すべてのiについてこの特徴量と特徴量テーブルからi番目の登録データに対応する部分波形と照合データベクトルに対応する部分波形間の部分相関度z(i, n)を計算し、部分相関度を最大にするiの値imaxを求める（ステップ３０４・ステップ３０５）。部分相関度z(i, n)はn要素からなる部分波形同士が似ているほど大きな値を持つような関数である。登録データ読み出し部２０８で得られた登録データの番号imaxを登録データ部２０２に送り、登録データ部０２は登録データEimaxを照合処理部２０５に渡す。照合処理部２０５は照合データVuと登録データEimaxの照合度M(Vu, Eimax)を計算する（ステップ３０６）。次に照合判定部２０７でこの照合度がしきい値Tを越えているか判定する（ステップ３０７）。越えていれば、照合は成功し、処理は終了する。越えていなければ、ステップ３０８でカウンタnの値を一つ増やし、部分波形を拡張して、ステップ３０２に戻ってループする。なお、ステップ３０５で過去においてimaxとなったことのあるiを、最大化の対象から除外する。
【００１９】
部分相関度z(i, n)は部分波形をn次元のベクトルと考えて、以下のように二つのベクトルのなす角度のコサインとして定義できる。
【００２０】
【数１】
2010244511.tif 000003
【００２１】
ここで、x(i, k) = F(Ei, Fk)、y(u, k) = F(Vu, Fk)である。すなわち、x(i, k)は特徴量テーブルの要素であり、y(u, k)は照合データベクトルの要素である。
【００２２】
また、部分相関度z(i, n)は以下のように部分波形間の差の絶対値の総和としても定義できる。
【００２３】
【数２】
2010244511.tif 000004
【００２４】
部分相関度z(i, n)が部分波形間の差の絶対値の総和で定義されている場合、その計算が簡単になるので、高速な認証処理が可能である。図４は、この定義に基づいている場合の図３のステップ３０３・ステップ３０４・ステップ３０５の詳細を示すフローチャートである。このフローに入る前に、配列z[ ]と配列flag[ ]の各要素はそれぞれ0とFALSEという値に初期設定しておく。ステップ４０１で照合データVuと特徴Fnの特徴量F(Vu, Fn)を計算し、yv[n]に代入する。ステップ４０２で変数zmaxを小さい数で初期設定する。ステップ４０３以下は変数iに関するループを形成している。ステップ４０３で変数iを1に初期設定する。ステップ４０４でiが登録データの総数I以下か判定する。以下でなければ、すべての登録データに関する処理を終えたのでループから脱出し、imaxとなったことのあるiを最大化の対象から除外するために、ステップ４１２でflag[imax]に値TRUEを代入した後、抜ける。以下であれば、ステップ４０５でflag[i]がTRUEか判定し、TRUEならば、既にimaxがこのiになったことがあったので、ステップ４１１に移る。TRUEでなければ、ステップ４０６でxv[n]に特徴量テーブルの要素x[i][n]の値を代入する。ステップ４０７でz[i]からxv[n]とyv[n]の差の絶対値を引く。ステップ４０８からステップ４１０まででz[i]がzmaxより大きければ、z[i]の値をzmaxに代入し、その時のiの値をimaxに代入して記憶する。次にステップ４１１で変数iの値を一つ増やして、ループする。
【００２５】
指静脈や指紋などのバイオメトリック認証の場合、照合データと登録データは画像であり、照合は通常テンプレートマッチングによって行われる。線形な明るさの変化に影響されない正規化相互相関法は代表的なテンプレートマッチングであり、以下の式Ｒ（ｍ，ｎ）で計算される。
【００２６】
【数３】
2010244511.tif 000005
【００２７】
Ｒ（ｍ，ｎ）の値が大きい程、画像が類似していることを意味する。したがって、正規相互相関法では、Ｒ（ｍ，ｎ）の最大値を求める処理となる。Ｒ（ｍ，ｎ）を計算するには画像全体を走査する必要がある。ｍとｎとの範囲を、それぞれ、ＭとＮとすると、Ｒ（ｍ，ｎ）の最大値を求めるにはＭＮ回画像全体を走査することになり、非常に多くの計算量を必要とする。
【００２８】
本発明によれば、計算量の多いテンプレートマッチングの適用を最小限にすることができる。例えば、画像に関する特徴を以下のように定義する。
【００２９】
【数４】
2010244511.tif 000006
【００３０】
いずれの特徴も数回の画像走査で計算可能である。前もってこのような計算量の少ない特徴の情報を用いて部分相関度の最も高い登録データを次の照合候補に選び出すことにより、テンプレートマッチングの効率的な適用が可能となる。
【００３１】
また、画像に関する特徴の別の定義は、照合データVuや登録データEiと同種の画像である参照データHkを用いる。特徴量テーブルの要素x(i, k)を,登録データEiと参照データHkの間の照合度と定義する。すなわち、以下の式で定義する。
【００３２】
【数５】
2010244511.tif 000007
【００３３】
同様に、照合データベクトルの要素y(u, k)を、照合データVuと参照データHkの間の照合度と定義する。すなわち、以下の式で定義する。
【００３４】
【数６】
2010244511.tif 000008
【００３５】
この定義によれば、特徴の総数は参照データの数であるので、特徴の総数を容易に決めることができる利点がある。
【００３６】
図５は指静脈の認証実験における本発明の方式とリニアサーチ方式の平均処理時間を100個から3000個までの登録データ数に対してプロットしたグラフである。参照データ数は200個である。また、部分相関度z(i, n)は部分波形間の差の絶対値の総和で定義されている。3000個の登録データで本発明方式とリニアサーチ方式の平均処理時間はそれぞれ0.083秒と1.500秒である。したがって、この時本発明の方式はリニアサーチ方式の約18倍の速度を得ている。一般に登録データ数が多くなると、平均処理時間の差はさらに拡大する傾向がある。このように参照データを用いた特徴の定義による方式は高速な1対N認証を実現する。
【実施例２】
【００３７】
実施例２の１対Ｎ認証方法は、登録データ（個数がＮ個。Ｎは２以上の自然数）とは別に複数の参照データを用意し、すべての登録データと参照データの組について計算された照合度からなる相互相関テーブルを生成しておき、照合データと参照データの照合度を計算し、当該照合度と相互相関テーブルから次に照合すべき登録データの順序を制御し、当該登録データと照合データの照合度を計算し、前記照合度をしきい値と比較して、当該照合データが登録データのどれに当たるかを決定するものである。
【００３８】
参照データは登録データと同種のデータとするが、他のデータでもよい。例えば、登録データが会社の営業部門の社員のデータである場合、参照データはその会社の開発部門の社員のデータとすることができる。また、参照データは人工的に生成されたものでもよい。例えば、参照データは乱数で発生させた画像データとすることができる。
【００３９】
また、参照データの個数は登録データの個数以下ならばいくつでもよい。
【００４０】
また、本発明では、登録データを引数とする複数の任意の関数によって算出される実数値の相互相関テーブルを用いてもよい。
【００４１】
図６の左側にある行列が相互相関テーブルである。行列の縦は登録データに対応し、行列の横は参照データに対応する。行列の要素の値は対応する登録データと参照データの照合度である。この相互相関テーブルの各行に注目して、その要素の値をプロットすると、右列のような一次元の波形になる。照合データについても、参照データとの照合度を計算して照合データベクトルを生成し、それから一次元の波形を作ることができる。重要なことは、照合データとある登録データが似ていれば、それぞれの一次元の波形も似ているということである。したがって、早い段階で一次元の波形の似ている登録データを探し出せば、照合が速くできる。そこで、次の1対N認証のアルゴリズムが考えられる。
【００４２】
(1) 左端の部分波形を切り出して、マッチングを行い、最もマッチしている登録データを選び出して、それと照合データとを照合する。
【００４３】
(2) もし照合が成功しなかったなら、部分波形を右方向に拡張して、部分波形のマッチングを行い、最もマッチしている登録データを選び出して、それと照合データとを照合するということを照合が成功するまで繰り返す。
【００４４】
図７は実施例２のブロック図である。参照データ部７０１は登録データや照合データと比較される複数の参照データを蓄える。登録データ部７０２は参照データや照合データと比較される複数の登録データを蓄える。照合処理Ａ部７０３は参照データ部７０１から参照データを、登録データ部７０２から登録データをそれぞれ一つずつ読み込み、それらの照合度を計算する。照合処理Ｂ部７０４は参照データ部７０１から参照データを一つ読み込み、入力された照合データとの照合度を計算する。照合処理Ｃ部７０５は登録データ部７０２から登録データを一つ読み込み、入力された照合データとの照合度を計算する。相互相関テーブル部７０６は照合処理Ａ部で計算された照合度を行列の形式で蓄える。照合判定部７０７は照合処理Ｃ部７０５で計算された照合度をしきい値と比較して、照合データがどの登録データに対応するかを判定する。登録データ読み出し部７０８は照合処理B部７０４で計算された照合度と相互相関テーブル部７０８に蓄えられている相互相関テーブルから、登録データ部７０２から次に照合べき登録データを決定する。
【００４５】
１対Ｎ認証の処理の前に、以下のようにして、あらかじめ相互相関テーブルを生成しておく。照合処理Ａ部７０３は、すべてのn1とn2について参照データ部７０１からn1番目の参照データRn1を、登録データ部７０２からn2番目の登録データEn2をそれぞれ一つずつ読み込み、それらの照合度M(Rn1, En2)を計算して、相互相関テーブル部７０６に渡し、相互相関テーブルを生成する。
【００４６】
図８は本発明の1対N認証の一実施例のアルゴリズムを示すフローチャートである。まずステップ８０１でカウンタnを１にする。次にステップ８０２でカウンタnが参照データの総数nmax以内か判定する。以内でなければ、照合は不成功となって処理を終了する。以内であれば、照合処理Ｂ部８０４で照合データVuとn番目の参照データRnの照合度M(Vu, Rn)を計算する（ステップ８０３）。次に登録データ読み出し部７０８で、すべてのiについてこの照合度と相互相関テーブルからi番目の登録データに対応する部分波形と照合データベクトルに対応する部分波形間の部分相関度z(i, n)を計算し、部分相関度を最大にするiの値imaxを求める（ステップ８０４・ステップ８０５）。部分相関度z(i, n)はn要素からなる部分波形同士が似ているほど大きな値を持つような関数である。登録データ読み出し部７０８で得られた登録データの番号imaxを登録データ部７０２に送り、登録データ部７０２は登録データEimaxを照合処理Ｃ部７０５に渡す。照合処理Ｃ部２０５は照合データVuと登録データEimaxの照合度M(Vu, Eimax)を計算する（ステップ８０６）。次に照合判定部７０７でこの照合度がしきい値Tを越えているか判定する（ステップ８０７）。越えていれば、照合は成功し、処理は終了する。越えていなければ、ステップ８０８でカウンタnの値を一つ増やし、部分波形を拡張して、ステップ８０２に戻ってループする。なお、ステップ８０５で過去においてimaxとなったことのあるiを、最大化の対象から除外する。
【００４７】
上記のアルゴリズムは最大nmax回のループの実行で終了するので、nmax、すなわち、参照データの総数を調節することにより、処理時間を制御できる。
【００４８】
部分相関度z(i, n)は部分波形をn次元のベクトルと考えて、以下のように二つのベクトルのなす角度のコサインとして定義できる。
【００４９】
【数７】
2010244511.tif 000009
【００５０】
ここで、x(i, k) = M(Ei, Rk)、y(u, k) = M(Vu, Rk)である。すなわち、x(i, k)は相互相関テーブルの要素であり、y(u, k)は照合データベクトルの要素である。
【００５１】
また、部分相関度z(i, n)は以下のように部分波形間の差の絶対値の総和としても定義できる。
【００５２】
【数８】
2010244511.tif 000010
【００５３】
部分相関度z(i, n)が部分波形間の差の絶対値の総和で定義されている場合、その計算が簡単になるので、高速な認証処理が可能である。
【００５４】
図９は、この定義に基づいている場合の図８のステップ８０３・ステップ８０４・ステップ８０５の詳細を示すフローチャートである。このフローに入る前に、配列z[ ]と配列flag[ ]の各要素はそれぞれ0とFALSEという値に初期設定しておく。ステップ９０１で照合データVuと参照データRnの照合度M(Vu, Rn)を計算し、yv[n]に代入する。ステップ９０２で変数zmaxを小さい数で初期設定する。ステップ９０３以下は変数iに関するループを形成している。ステップ９０３で変数iを1に初期設定する。ステップ９０４でiが登録データの総数Ｎ以下か判定する。以下でなければ、すべての登録データに関する処理を終えたのでループから脱出し、imaxとなったことのあるiを最大化の対象から除外するために、ステップ９１２でflag[imax]に値TRUEを代入した後、抜ける。以下であれば、ステップ９０５でflag[i]がTRUEか判定し、TRUEならば、既にimaxがこのiになったことがあったので、ステップ９１１に移る。TRUEでなければ、ステップ９０６でxv[n]に相互相関テーブルの要素x[i][n]の値を代入する。ステップ９０７でz[i]からxv[n]とyv[n]の差の絶対値を引く。ステップ９０８からステップ９１０まででz[i]がzmaxより大きければ、z[i]の値をzmaxに代入し、その時のiの値をimaxに代入して記憶する。次にステップ９１１で変数iの値を一つ増やして、ループする。
【００５５】
実施例１と実施例２とが共通部分が多いことは、図１から図４までと、図６から図９までとを比べることでわかるが、これらの違いについて概念の対応関係を中心に説明すると、次の通りである。実施例１の「特徴」は、実施例２では「参照データ」に対応する。実施例１の「特徴量テーブル」は、実施例２では「相互相関テーブル」に対応する。実施例１の「特徴量」は、実施例２の「参照データとの照合度」に対応する。実施例１の「登録データの特徴量」は、実施例２の「登録データと参照データとの照合度」に対応する。実施例１の「照合データの特徴量」は、実施例２の「照合データと参照データとの照合度」に対応する。実施例１の「特徴部」は、実施例２の「参照データ部」に対応する。実施例１の「特徴量計算Ａ部」は、実施例２の「照合処理Ａ部」に対応する。実施例１の「特徴量計算Ｂ部」は、実施例２の「照合処理Ｂ部」に対応する。実施例１の「照合処理部」は、実施例２の「照合処理Ｃ部」に対応する。
【実施例３】
【００５６】
一方、他人受入率の悪化（他人受け入れ率が上がってしまうこと）を防ぐために、照合が成功するまで最もマッチしている登録データとの照合を繰り返すのではなく、成功する可能性の高い登録データを選択してから照合することで、繰返し回数を減らす方法が考えられる。具体的には、部分波形ではなく、全参照データと照合データとの照合度を計算、参照データ数の長さの一次元波形の類似度が高い登録データとのみ繰返し照合する。照合に成功しなかったら、別の指で照合、その指で照合に成功すれば、第一の指で照合に成功するか試し、成功すれば本人と認証する。
【００５７】
実施例２では、照合データに類似した登録データを高速に探し出す手法を説明した。実施例３として、データとして指紋や静脈など指にある生体情報を用いた利用者の認証にかかわり、複数部位（複数の指）を用いて他人受入率を改善する実施例を説明する。
【００５８】
実施例２では、一人の利用者が一つの指を登録して認証する、ないしは複数指を登録したとしても、どの指かに照合成功すれば、その人を認証したことになった。実施例３では、一本目の指で照合に成功すれば、その人と認証する。一本目では失敗し二本目の指で照合成功した時には、一本目で再照合して成功して初めて本人の認証に成功する。一本目でも二本目でも失敗、三本目の指で照合成功した時には、一本目と二本目で再照合して成功して初めて本人の認証に成功する。なお、ここでは一人が三本登録しているとしているが、2本でも、10本でも同様に認証できる。ここで、二本目又は三本目で認証を成功してから、再照合を行う場合には、認証を成功して得た利用者識別子（ＩＤ）を頼りに登録データを取得し、それとの照合をすればよいので、ＩＤを知らずに照合するのとは大きく異なり、成功率が高まる。
【００５９】
準備として各利用者iが3本の指E1i、E2i、E3iを登録、先の実施例と同様に参照データとの相関テーブルであるM(E1i, Rk)、M(E2i, Rk)、M(E3i, Rk)を作成する。
【００６０】
以下、図１０を参照しつつ説明する。
ステップ１００１において、スキャナから利用者の第一に登録した指（第一部位）の静脈を読み取り、この画像をV1 とする。このV1から第一に登録した指との相関度Z1(i) 
【００６１】
【数９】
2010244511.tif 000011
【００６２】
を計算する。ここでnmaxは参照データ数である。ギリシャ文字の大文字シグマはkについての総和である。
ステップ１００２において、相関度Z1(i)が高い上位10の登録データE1iを抜き出し、高い方から順にM(E1i,V1)＜Tとなるiを探す。
ステップ１００３において、ステップ１００２のiが見つかればステップ１００４に進み、見つからなければステップ１００５に進む。
ステップ１００４において、i番目の登録者と認証、処理を終える。
ステップ１００５において、スキャナから利用者の第二に登録した指（第二部位）の静脈を読み取り、この画像をV2 とする。このV2から第二に登録した指との相関度Z2(i) 
【００６３】
【数１０】
2010244511.tif 000012
【００６４】
を計算する。
ステップ１００６において、相関度Z2(i)が高い上位10の登録データE2iを抜き出し、高い方から順にM(E2i,V2)＜Tとなるiを探す。
ステップ１００７において、iが見つかればステップ１００８に進み、見つからなければステップ１０９に進む。
【００６５】
ステップ１００８において、M(E1i,V1)＜Tとなればステップ１００４に、そうでなければステップ１００９に進む。
ステップ１００９において、スキャナから利用者の第三に登録した指（第三部位）の静脈を読み取り、この画像をV3 とする。このV3から第三に登録した指との相関度Z3(i) 
【００６６】
【数１１】
2010244511.tif 000013
【００６７】
を計算する。
ステップ１０１０において、相関度Z3(i)が高い上位10の登録データE3iを抜き出し、高い方から順にM(E3i,V3)＜Tとなるiを探す。
ステップ１０１１において、iが見つかればステップ１０１２に進み、見つからなければステップ１０１３に進む。
ステップ１０１２において、M(E1i,V1)＜T かつM(E2i,V2)＜Tとなればステップ１００４に、そうでなければステップ１０１３に進む。
ステップ１０１３において、認証失敗として、処理を終える。
【００６８】
上記処理のステップ１００２、１００６、１０１０において相関度Z1(i)、Z2(i)、Z3(i)が高い上位10の登録データと比較していた。これは10に限らず、5でも20でも、他の数でも構わない。また、比較する登録データ数を固定するのではなく、一定の相関度以上となった登録データ全てと比較する方法やこれらを組合わせる方法もある。なお、比較する数が多いほど、照合回数が増し、認証に成功する確率が高まるが同時に間違って他人として受入れて認証する確率も高まる。逆に比較する数が少ないと、他人受入率は下がるが同時に認証に成功する確率も下がる。
【００６９】
また上記の実施例では、指の静脈を対象としていたが、指紋でも全く同様に可能なことは明らかである。また指にある生体情報だけではなく、複数ある生体情報でも可能なことは明らかである。さらに、同種の生体情報ではなく、顔、虹彩、指紋、手の平の静脈など複数種類の生体情報を混在させて認証するシステムに対しても適用可能である。
【００７０】
また、ステップ１０１２においてはM(E1i,V1)＜T かつM(E2i,V2)＜Tを判断していたが、どちらか一方が成り立つだけで本人と認証する方法も考えられる。
【実施例４】
【００７１】
上に述べた実施例３では、一番目の指、二番目の指、三番目の指と照合する指の順序が固定されていた。固定しない方法もある。準備として各登録者iが3本の指Ei、Ei’、Ei’’を登録、参照データとの相関テーブルを一つ作成する。ここで、実施例３では、一番目に登録した指の相関テーブル、二番目に登録した指の相関テーブル、三番目に登録した指の相関テーブルと三つのテーブルを作成していたが、ここでは一つのテーブルにまとめる代わりに図１２に示す一人の登録者が相関テーブルの何番目に登録しているかわかるテーブルと逆に図１３に示す相関テーブルのインデックスから登録者が識別できるテーブルを用意する。図１２と図１３とでは、IDが343の登録者が登録した3本の指の相関テーブルでのインデックスが1433、1434、1435であることを示す。以下、図１１を参照しつつ説明する。
【００７２】
ステップ１１０１において、スキャナから登録した指の静脈を読み取り、この画像をV1 とする。先のステップ１００１と異なり、登録した順序を気にすることなく登録した指のうち利用者が任意に選んだどれかの指をスキャンすれば良い。このV1から登録した全指での相関度Z(i) 
【００７３】
【数１２】
2010244511.tif 000014
【００７４】
を計算する。ここでnmaxは参照データ数であり、ギリシャ文字の大文字シグマはkについての総和である。
ステップ１１０２において、相関度Z(i)が高い上位10の登録データEiを抜き出し、高い方から順にM(Ei,V1)＜Tとなるiを探す。
ステップ１１０３において、ステップ１１０２のiが見つかればステップ１１０４に進み、見つからなければステップ１１０５に進む。
ステップ１１０４において、図１３から相関テーブルでのi番目の指がどの登録者に当たるか決定、その登録者と認証、処理を終える。
ステップ１１０５において、スキャナから別の指（登録した指のうち、利用者が任意に選んだ別の指）の静脈を読み取り、この画像をV2 とする。先のステップ１００５と異なり、登録した順序（複数部位の違い）を気にすることなくステップ１１０１でスキャンした指でない登録したどれかの指をスキャンすれば良い。このV2から登録した全指での相関度Z(i) 
【００７５】
【数１３】
2010244511.tif 000015
【００７６】
を計算する。
ステップ１１０６において、相関度Z(i)が高い上位10の登録データEiを抜き出し、高い方から順にM(Ei,V2)＜Tとなるiを探す。
ステップ１１０７において、iが見つかればステップ１１０８に進み、見つからなければステップ１１０９に進む。
【００７７】
ステップ１１０８において、M(Ei’,V1)＜Tとなればステップ１１０４に、そうでなければステップ１１０９に進む。ここでEi’のインデックスのi’は、ステップ１１０７で見つかった相関テーブルのインデックスのiから図１３を使って登録者を特定、次に図１２を使ってこの登録者の別の指の相関テーブルでのインデックスを求めた結果である。三本の指を登録した場合には、二つのi’の候補があり、どちらかでM(Ei’,V1)＜Tとなればステップ１１０４に、そうでなければステップ１１０９に進む。
ステップ１１０９において、スキャナから登録した先の二つとは別の指の静脈を読み取り、この画像をV3 とする。このV3から登録した全指での相関度Z(i)
【００７８】
【数１４】
2010244511.tif 000016
【００７９】
を計算する。
ステップ１１１０において、相関度Z(i)が高い上位10の登録データEiを抜き出し、高い方から順にM(Ei,V3)＜Tとなるiを探す。
ステップ１１１１において、iが見つかればステップ１１１２に進み、見つからなければステップ１１１３に進む。
ステップ１１１２において、M(Ei’,V1)＜T かつM(Ei’’,V2)＜Tとなればステップ１１０４に、そうでなければステップ１１１３に進む。ここでEi’とEi’’のインデックスのi’とi’’は、１１１１で見つかった相関テーブルのインデックスのiから図１３を使って登録者を特定、次に図１２を使ってこの登録者の別の指の相関テーブルでのインデックスを求めた結果である。三本の指を登録した場合には、二つのi’とi’’の組合せの候補があり、どちらかの組合せでM(Ei’,V1)＜TかつM(Ei’’,V2)＜Tとなればステップ１１０４に、そうでなければステップ１１１３に進む。
ステップ１１１３において、認証失敗として、処理を終える。
ステップ１１１２ではM(Ei’,V1)＜TかつM(Ei’’,V2)＜Tとしていたが、いずれか一方のみで認証成功とする方法もある。
【産業上の利用可能性】
【００８０】
指静脈、指紋認証、虹彩認証、声紋認証などの生体認証に利用可能である。特に、ＩＤ入力を要しない認証装置に利用できる。
【符号の説明】
【００８１】
２０１  特徴
２０２  登録データ
２０３  特徴量計算A
２０４  特徴量計算B
２０５  照合処理
２０６  特徴量テーブル
２０７，７０７  照合判定
２０８，７０８  登録データ読み出し
７０１  参照データ
７０２  登録データ
７０３  照合処理A
７０４  照合処理B
７０５  照合処理C
７０６  相互相関テーブル
【図１】
2010244511.tif 000017
【図２】
2010244511.tif 000018
【図３】
2010244511.tif 000019
【図４】
2010244511.tif 000020
【図５】
2010244511.tif 000021
【図６】
2010244511.tif 000022
【図７】
2010244511.tif 000023
【図８】
2010244511.tif 000024
【図９】
2010244511.tif 000025
【図１０】
2010244511.tif 000026
【図１１】
2010244511.tif 000027
【図１２】
2010244511.tif 000028
【図１３】
2010244511.tif 000029