(57)【要約】指紋内の各特徴点に対して、一組の周囲の「近傍部分」の特徴点が識別される。各近傍部分においては、中央および近傍部分の特徴点の各特徴点ペアが、ペア内の２つの特徴点間のスペース、２つの特徴点の向きの違い、および中央の特徴点の向きと２つの特徴点を結ぶラインの間の角度を含む（しかし、これらに限定されない）いくつかの特徴により記述される。これらの特徴点ペアの特徴から、特徴点ペアの指標が作成される。登録済みの指紋の特徴点ペアの指標が、提供された指紋と比較される。一致の識別は、一致する指標が十分なものであるか否か、一致する指標から識別した一致する近傍部分が十分なものであるか否かにより行うことができ、対応する特徴点ペアの詳細な比較により確認することができる。
2010526361.tif 000002
【特許請求の範囲】
【請求項１】
第１の指紋データおよび第２の指紋データが相互に一致するか否かを判定するための方法であって、
各近傍部分が、中央の特徴点と、前記中央の特徴点と一緒に、特徴点ペアを含む少なくとも第２の特徴点とを含むように、前記第１および第２の各指紋データ内の各特徴点の周囲に特徴点の近傍部分を生成するステップと、
前記第１および第２の指紋データそれぞれに対して、前記特徴点ペアの特徴の指標を作成するステップと、
前記第１の指紋データ内の各指標に対して、もし含んでいる場合には、前記第２の指紋データおよび前記第１および第２の指紋データの両方内の前記指標に関連する前記近傍部分で一致する指標を識別するステップと、
前記識別済みの近傍部分内のすべての前記一致する指標をカウントし、一致する指標の数が閾値と少なくとも等しい場合には、前記第１および第２の指紋データからの前記近傍部分を一致するものとして特徴付けるステップと、
前記第１および第２の指紋データ間の一致する近傍部分の数をカウントし、一致する近傍部分の数が閾値と少なくとも等しい場合には、前記第１および第２の指紋データを一致するものとして特徴付けるステップと、
を含む方法。
【請求項２】
前記指標が、
前記特徴点ペアの前記２つの特徴点間の向きの違い、
前記特徴点のうちの１つの向きと前記２つの特徴点を結ぶラインの間の角度、
前記特徴点ペアの各特徴点間の距離、
からなるグループから選択される特徴を表す少なくとも１つの値を含む、請求項１に記載の方法。
【請求項３】
前記第１および第２の指紋データからの近傍部分間の一致の表示が、一致する近傍部分の数をカウントする前記ステップの前の前記近傍部分に対する前記第１および第２の指紋データの詳細な比較により確認される、請求項１または２に記載の方法。
【請求項４】
提供された指紋が、登録データベース内にすでに登録され、格納されている指紋と一致するか否かを判定するための方法であって、
前記提供された指紋を表すデータから前記指紋内の特徴点の位置を判別するステップと、
各特徴点に対して、中央の特徴点としての前記各特徴点により、前記特徴点の周囲に、特徴点の近傍部分を確立するステップであって、前記特徴点の近傍部分が、特徴点ペアを形成している前記中央の特徴点および少なくとも１つの他の特徴点を含むような大きさであるステップと、
前記特徴点の近傍部分に近傍部分ＩＤを割り当てるステップと、
前記近傍部分内の各特徴点ペアに対して、選択した特徴を判別するステップと、
前記選択した特徴を表す指標を生成するステップと、
前記特徴点ペアを一意に識別するために、前記指標および前記近傍部分ＩＤを関連付けるステップと、
特徴点ペアの選択した特徴を表す各指標に対して、前記登録データベースから、もしある場合、同じ指標を有するこれら特徴点ペアを選択するステップと、
近傍部分ＩＤにより前記登録データベースから前記一致する指標をソートするステップと、
前記登録データベースからの一致する指標の前記数が少なくとも閾値数と等しいか否かを判定し、等しい場合には、前記近傍部分を発見することができる前記登録データベースから前記１つまたは複数の指紋を識別し、前記近傍部分を一致する近傍部分として分類するステップと、
前記登録データベースから識別した各指紋に対して、一致する近傍部分の数をカウントするステップと、
一致する近傍部分の数の少なくともカウントから、前記提供された指紋と前記登録データベース内に含まれている指紋とが一致するか否かを判定するステップと、
をさらに含む方法。
【請求項５】
前記指標が、
前記特徴点ペアの前記２つの特徴点間の向きの違い、
前記特徴点のうちの１つの向きと前記２つの特徴点を結ぶラインの間の角度、および
前記特徴点ペアの各特徴点間の距離、
からなるグループから選択される特徴を表す少なくとも１つの値を含む、請求項４に記載の方法。
【請求項６】
近傍部分間の一致の表示が、前記近傍部分に対する前記提供された指紋データと、一致する近傍部分の数をカウントする前記ステップの前の前記近傍部分に対する前記登録データベースからのデータとの詳細な比較により確認される、請求項４または５に記載の方法。
【請求項７】
前記提供された指紋データを、指紋識別番号を有する少なくとも１つの登録済み指紋に関連する登録データベース内に格納しているデータと比較することにより、提供された指紋データを識別および／または確認するための方法であって、
提供された指紋データにより提供された指紋を表示するステップと、
前記提供された指紋データから、前記提供された指紋内の特徴点の位置および特徴を判別するステップと、
前記提供された指紋内の各特徴点に対して、その近傍部分に対する中央の特徴点である前記各特徴点により近傍部分を判別するステップであって、前記各近傍部分が、前記中央の特徴点を含む少なくとも１つの特徴点ペアを含むステップと、
各近傍部分に近傍部分識別を割り当てるステップと、
各近傍部分内の各特徴点ペアに対して特徴点ペア指標を判別するステップと、
前記登録済み指紋の各特徴点の近傍部分に対して、特徴点ペアの指標の特徴点ペアの指標テーブルを生成するステップと、
前記提供された指紋データから判別したものと同じ特徴点ペアの指標を有する前記登録データベースから特徴点ペアを選択するステップと、
その指紋識別番号およびその特徴点の近傍部分の識別番号により、前記選択した特徴点ペアをグループ分けするステップと、
各グループ内の前記特徴点をカウントするステップと、
前記特徴点のカウントから、前記登録データベース内の登録済みのいずれの指紋が前記提供された指紋と一致するかを識別するステップと、
前記提供された指紋と一致する前記登録データベース内の各識別した指紋に対して、前記提供された指紋内の特徴点の近傍部分と一致する前記識別した各指紋内の特徴点の近傍部分の数をカウントするステップと、
一致する特徴点の近傍部分の数のカウントから、前記提供された指紋が、前記登録データベース内に登録されている指紋と一致するか否かを判定するステップと、
をさらに含む方法。
【請求項８】
前記特徴点の指標が、
前記特徴点ペアの前記２つの特徴点間の向きの違い、
前記特徴点のうちの１つの向きと前記２つの特徴点を結ぶラインの間の角度、
前記特徴点ペアの各特徴点間の距離、
からなるグループから選択される特徴を表す少なくとも１つの値を含む、請求項７に記載の方法。
【請求項９】
対応する特徴点ペアを詳細に比較することにより、前記判別した一致を確認するステップをさらに含む、請求項７または８に記載の方法。
【請求項１０】
前記特徴点カウントから、前記登録データベース内のいずれの登録済みの指紋が前記提供された指紋と一致するのかを識別する前記ステップが、前記特徴点のカウントが少なくとも所定の特徴点ペアの閾値と等しいか否かを判定するステップを含む、請求項８または９に記載の方法。
【請求項１１】
一致する特徴点ペアの近傍部分の数のカウントから、前記提供された指紋が、前記登録データベース内に登録されている指紋と一致するか否かを判定する前記ステップが、一致する特徴点の近傍部分の数の前記カウントが、少なくとも所定の特徴点近傍部分の閾値と等しいか否かを判定するステップを含む、請求項７、８、９または１０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、生体検知および識別に関し、特に、スケーラブルな指紋識別および確認の速度を改善するための方法および装置に関する。
【背景技術】
【０００２】
（関連出願との相互参照）
本発明は、参照により本明細書に組み込むものとする、本明細書により優先権を主張している、２００７年５月３日出願の「Ｆａｓｔ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ａｎｄ  Ｖｅｒｉｆｉｃａｔｉｏｎ  Ｂｙ  Ｍｉｎｕｔｉａｅ  Ｐａｉｒ  Ｉｎｄｅｘｉｎｇ」という名称の米国仮特許出願第６０／９１５，７５６号に関連する。
【０００３】
参照により本明細書に組み込むものとする下記の各文献、「Ｍｅｔｈｏｄ  Ｔｏ  Ｃｏｎｄｕｃｔ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｖｅｒｉｆｉｃａｔｉｏｎ  Ａｎｄ  Ａ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｖｅｒｉｆｉｃａｔｉｏｎ  Ｓｙｓｔｅｍ」という名称のＫｒａｍｅｒ他の米国特許第７，２０６，４３７号；「Ｆｉｎｇｅｒｐｒｉｎｔ  Ｍａｔｃｈｉｎｇ  Ｕｓｉｎｇ  Ｒｉｄｇｅ  Ｆｅａｔｕｒｅ  Ｍａｐｓ」という名称のＲｅｉｓｍａｎ他の米国特許第７，１４２，６９９号；「Ｆｉｎｇｅｒｐｒｉｎｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  Ｖｉａ  Ｓｐａｔｉａｌ  Ｆｒｅｑｕｅｎｃｙ  Ｃｏｍｐｏｎｅｎｔｓ」という名称のＤｙｄｙｋ他の米国特許第６，２２６，３９１号；「Ｅｘｐｅｒｔ  Ｍａｔｃｈｅｒ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｓｙｓｔｅｍ」という名称のＬｏ他の米国特許第５，９６０，１０１号、および「Ｆｉｎｇｅｒｐｒｉｎｔ  Ｒｅｃｏｇｎｉｔｉｏｎ  Ｓｙｓｔｅｍ」という名称のＹａｕ他の米国特許出願公開第２００３／００３９３８２号に、先行技術のいくつかの態様について記載されている。しかし、本明細書に記載するいかなるものも、本発明者らがこれらの先行技術について何らかの調査を行ったことを示唆するものと解釈すべきではない。さらに、本明細書に記載するすべての情報が「先行技術」であるというわけでもなく、別段の指定がない限り、添付の特許請求の範囲に関連して特許性を有する内容であると見なすべきでもない。
【０００４】
２つとして同じ指紋はないと一般に考えられている。そのため、指紋は、ある人と他の人とを区別したり、ある人の同一性等を識別または確認するために使用することができる。そのため、指紋の構造についてのデータ、すなわち、指紋を形成している凹凸部の位置およびパターンを取り込むために種々の方法およびシステムが開発されてきた。このデータは、登録済みまたは認証済みのデータと比較することができ、一致した場合には、指紋の持ち主の同一性を判別することができる。
【０００５】
大局的指紋解析（Ｇｌｏｂａｌ  ｆｉｎｇｅｒｐｒｉｎｔ  ａｎａｌｙｓｉｓ）は、指紋確認の１つの形態である。登録プロセス中に、複数の指紋の画像が収集される。これらの画像は、登録データベース内に格納される。認証のためにユーザが指紋を提供すると、提供された指紋の画像が、登録データベース内の画像と比較される。凹凸部のパターンは、登録済みの指紋との照合を確度の高いものにするために指紋全体と比較することができる。
【０００６】
多くの用途の場合、登録または認証された指紋の数は、非常に多いか、および／または提供された指紋を登録または認証された指紋のデータベースと比較するためにかかる時間を最小限度に短縮することは重要な問題である。この照合プロセスの速度を速くするために種々の指標化技術が開発されてきた。ある指標化技術は、指標化した特徴として、特徴点と呼ぶ識別可能な指紋の特徴を使用している。
【０００７】
種々の実施形態の場合にも、登録プロセス中に、複数の指紋画像が収集される。各登録指紋の凸部のパターンが検出され、例えば、凸部の段階的線形近似を使用し、凸部の交差、分岐、切れ目等のような特徴点を探すことにより、特徴点について解析される。各特徴点の位置が、特徴点のテンプレートの形で指紋に対して記録される。ユーザが照合のために指紋を提供した場合には、提供された指紋について類似の特徴点抽出およびテンプレート形成プロセスが行われ、次に、提供された指紋のテンプレートが、一致するテンプレートを探して登録済みのテンプレートのデータベースと比較される。
【０００８】
しかし、指紋を確認するための先行技術のいずれの方法も以下のような欠点があり、トレードオフを必要とした。
・個々の特徴点の指標化をベースとする従来の指標化方法は、識別力が低く、またロバスト性が低い。
・大局的指紋の特徴（例えば、指紋クラス）をベースとする従来の方法は、（画像取込プロセスからの）少しの画像の重なりおよび（複数のソースからの）画像の歪みに対する感度のような正確な全指紋の構造に関連する問題を抱えている。
・従来のアルゴリズムは、スケーラビリティが小さく、大型データベースの場合には確認に時間がかかり、識別は高価なリソースが必要である。
・従来の方法は、制限がないリソースおよび制約のないリソースの両方の下で稼働する識別および確認を１つのアルゴリズムで行うことができなかった。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許第７，２０６，４３７号公報
【特許文献２】米国特許第７，１４２，６９９号公報
【特許文献３】米国特許第６，２２６，３９１号公報
【特許文献４】米国特許第５，９６０，１０１号公報
【特許文献５】米国特許出願公開第２００３／００３９３８２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従って、本発明の種々の実施形態の目的は、特徴点ペアに指標化することによりこれらの欠点を解決することである。指紋内の各特徴点に対して、一組の周囲の「近傍部分」の特徴点が識別される。各近傍部分においては、中央および近傍部分の特徴点の各特徴点ペアが、ペア内の２つの特徴点間のスペース、２つの特徴点の向きの違い、および中央の特徴点の向きと２つの特徴点を結ぶラインの間の角度を含む（しかし、これらに限定されない）いくつかの特徴により記述される。これらの特徴点ペアの特徴から特徴点ペアの指標が作成される。
【課題を解決するための手段】
【００１１】
本明細書に記載する特徴点ペアの指標化の１つの利点は、個々の特徴点をベースとする方法と比較すると、識別力が高いことである。特徴点ペアは、依然として規模が小さい特徴であり、そのため画像の歪みに対して強く、小さな画像の重なりがあっても画像が小さくても動作する。さらに、指紋識別および確認を１つのアルゴリズムで行うことができ、必要なリソース（メモリ、計算）の点でスケーラブルである。従って、特徴点ペアの指標化を使用すれば、識別および確認の両方の動作の速度が有意に改善される。
【００１２】
上記の記述は、本発明のいくつかの一意の態様、特徴および利点を要約したものである。しかし、この概要は網羅的なものではない。それ故、本発明のこれらおよび他の態様、特徴および利点は、下記の説明を読み、添付の図面を見ればよりよく理解することができるだろう。
【００１３】
添付の図面中、類似の参照番号は、いくつかの図面内の類似の要素を示す。図面は例示としてのものであり、縮尺は正確なものではない。
【図面の簡単な説明】
【００１４】
【図１】特徴点および特徴点の近傍部分を示すサンプル指紋である。
【図２】ペア内の２つの特徴点間の距離、２つの特徴点の向きの違い、および中央の特徴点の向きと２つの特徴点を結ぶラインの間の角度の違いを含む特徴点の特徴セットである。
【図３】元の指紋の近傍部分の高速選択のための識別キーとして使用する特徴点ペアの指標である。
【図４】元の指紋の近傍部分の高速選択のための識別キーとして使用する特徴点ペアの指標である。
【図５】提供された指紋と参照プリントとの間の一致を判別するために特徴点ペアの指標化を使用する方法の一実施形態を示すフローチャートである。
【発明を実施するための形態】
【００１５】
図１は、いくつかの特徴点のポイント２０〜３２が識別され、表示されているサンプル指紋１０である。本発明においては、分岐点２０〜２４および／または切れ目２６〜３２のような多くの異なるタイプの特徴点を識別し、使用することができることをよく理解することができるだろう。例えば、当業者であれば周知の方法により識別されると、各特徴点をその位置および向きにより表示することができる。
【００１６】
図１は、２つ以上の特徴点が位置する「近傍部分」と呼ぶ円形領域３４を示す。各近傍部分の中心は、例えば、図１の特徴点２４のような中央の特徴点の周囲に位置する。近傍部分の形状は重要なものではないが、中央の特徴点の周囲のある有限領域内に、例えば、図１の例示的特徴点２８のような少なくとも１つの追加の特徴点が位置することを示す。中央の特徴点および近傍部分内の追加の特徴点は、以下にさらに詳細に説明する特徴点ペアを生成する。また、図１は、各特徴点ペアを結ぶ形成されたライン３６も示す。ライン３６は、特徴点ペアを特徴付けるための２つの特徴点２４、２８間の距離を測定する際に使用され、以下にさらに詳細に説明する。
【００１７】
図２は、例示としての近傍部分３４、その内部に含まれる多数の特徴点、および特定の特徴点ペア３８の詳細図である。平均的な指紋が、数個から多数の近傍部分および特徴点ペアを含んでいることを理解することができるだろう。１つのこのような近傍部分および特徴点ペアについての本明細書の説明は、このような各特徴点ペアの解析を単に例示するためのものであることも理解することができるだろう。図２を参照すると、各近傍部分においては、中央の特徴点２４および近傍部分の特徴点２８からなる各特徴点ペア３８を、特徴セットにより一意に特徴付けることができる。この特徴セットは、ペア内の２つの特徴点間の距離、２つの特徴点（例えば、α＋β−１８０）の向きの違い、および中央の特徴点の向きと２つの特徴点を結ぶラインの間の角度α（距離、角度１および角度２）を含む（しかし、これらに限定されない）。これらの特徴から、特徴点の指標が作成される。本明細書で使用する場合、「指標」という用語は、ある特徴点ペアの選択した態様を示す一組のデータ要素を意味する。さらに、本明細書で使用する場合、「指標テーブル」という用語は、ある指標を一意の識別子（キー）として使用する特徴点ペアの選択した態様を示すデータを構成し、および格納／入手するために使用するデータ構造を意味する。さらに、本明細書で使用する場合、「指標化」という用語は、特徴点ペアの選択した態様を表すデータを格納し、参照するために指標および指標テーブルを使用することを意味する。
【００１８】
各指紋は、それに対する指標を判別することができる複数の特徴点ペアを有する。各特徴点ペアは、指標を含む複数のデータ要素を有する。従って、指標テーブルは、データ要素、（ペアＩＤにより識別されている）特徴点ペア、および（指紋ＩＤにより識別されている）指紋を構成するのに適している。各特徴点ペアの指標（すなわち、各指紋からの各近傍部分からの各特徴点ペア）に対しては、特徴点ペアのメンバーシップが格納される（例えば近傍部分およびそこから特徴点ペアが生成された指紋ＩＤなど）。特徴点ペアの指標は、元の指紋の近傍部分の高速選択のための識別キーとして使用される。図３および図４は、このような特徴点ペアの指標の多くの可能な実施態様のうちの１つである。
【００１９】
特徴点ペアの指標化は、提供した指紋が登録済みの指紋に対応するか否かを判定するために効果的に使用することができる。このようなプロセスは、施設へのアクセスを許可したり（または禁止したり）、コンピュータまたはネットワーク上に格納しているファイルへのアクセスを許可したり（禁止したり）、携帯電話などの使用を許可したりするために、ユーザの同一性を確認する際に通常使用される。本発明による指紋識別／確認アルゴリズムの一実施形態は、下記の主なステップからなる。
１．指標テーブルの作成。１つまたは複数の指紋から各特徴点の近傍部分内の各特徴点ペアのための特徴点ペアの指標の生成、および指標テーブル内への特徴点のメンバーシップの格納。この場合、テーブルは、登録済みの指紋のための特徴点の指標データ要素を含む。
２．一致する特徴点の近傍部分の選択。指標テーブル内に格納している指紋と比較される提供された指紋に対する、各特徴点の近傍部分内の各特徴点に対する特徴点ペアの指標の生成と、指標テーブルからの同じ指標を含む特徴点ペア（もしあった場合）の選択。各近傍部分毎の選択した一致する特徴点ペアの数の評価、および近傍部分が一致するか否かの判定。
３．一致する特徴点の近傍部分の確認。任意選択として、発見した特徴点の近傍部分を詳細な比較により確認することができる。
４．一致する指紋の選択。指標化された各指紋の確認した一致する特徴点の近傍部分の数の評価、および指紋が一致するか否かの判定。
【００２０】
図５は、上記の一実施形態を表すプロセス５０を示す。プロセス５０は、通常、登録済みの指紋としての働きをする１つまたは複数の指紋の走査から開始する。要するに、提供された指紋は、（本明細書に記載する指標化プロセスにより）登録済みの指紋と比較される。提供された指紋と登録済みの指紋のうちの１つとの一致は、同一性の確認、施設またはコンピュータ・ファイルへのアクセスの許可等のような多くの目的のために使用することができる。ステップ５１において、１つまたは複数の登録済みの指紋からのすべての特徴点の近傍部分からのすべての特徴点ペアの指標が形成され、その指紋識別番号および特徴点の近傍部分の識別番号により表されるこれらのすべての特徴点ペアが、指標テーブル内に格納される。データ構造の例としては、［指紋ＩＤ、近傍部分ＩＤ、指標］等がある。この場合、指標は、データ構造［距離、角度１、角度２］である。しかし、多くの他のこのようなデータ構造を使用することができ、データ構造の実際のフォーマットは、本発明の範囲を制限しない。指紋識別番号は、例えば、１から指標化した指紋の数までの数であってもよいし、特徴点の近傍部分識別番号は、例えば、１から指紋内の特徴点の数までの数であってもよい。提供された特徴点ペアに固有の特徴と高速照合する特徴点ペア選択のために使用する特徴点ペアの指標との間には強い対応が見られる。
【００２１】
ステップ５２において、走査済みの提供された指紋を表すデータが入手される（例えば、指紋走査デバイスから）。指紋データの登録は、通常、１つの指紋に対して１回だけ行われるが、走査済みの提供データは、アクセス等のためにユーザが認証をしたい場合、毎回入手される。
【００２２】
指標テーブル内の指紋と比較される提供された指紋の場合には、各特徴点の近傍部分内の各特徴点に対して特徴点ペアの指標が生成される。次に、ステップ５４において、同じ指標を有する特徴点ペアが指標テーブルから選択される。重要なことは、このプロセスは比較的高速のプロセスであることである。何故なら、指標値の全数は、例えば、指紋画像を表すデータの全数と比較すると比較的少ないからである。
【００２３】
提供された指紋の各特徴点の近傍部分の場合には、選択した特徴点ペアは、ステップ５６において、その指紋の識別番号およびその特徴点の近傍部分識別番号によりグループ分けされる。次に、各グループ内の特徴点がカウントされる。各グループは、そこから指標テーブル内に格納している特徴点ペアを入手した対応する指紋の対応する特徴点の近傍部分からの一致する特徴点ペアを含む。
【００２４】
次に、一致していると考えられる２つの特徴点の近傍部分について、一致する特徴点ペアの数に対して適切な閾値が選択される。ステップ５８において、発見した特徴点ペアの数が選択した閾値より大きい場合には、発見した特徴点の近傍部分がグループとして選択される。
【００２５】
ステップ６０において、提供された指紋の近傍部分および発見した特徴点の近傍部分の対応を、対応する特徴点ペアを詳細に比較することにより確認することができる。オプションではあるが、この確認により、識別／確認プロセスにおいて有意に向上された精度が得られる。確認は、ステップ２において識別した特徴点の近傍部分から新しい詳細な指標テーブルを作成することにより行うことができる。詳細な指標テーブルは、識別した特徴点の近傍部分からの特徴点ペアだけを含んでいて、格納している特徴点ペアは、その特徴点ペアの識別番号によってだけ表示される。特徴点ペアの識別番号は、例えば、１から近傍部分内の隣接する特徴点の数までの数であってもよい。特徴点ペアの指標は、高速照合の特徴点ペアを選択するために使用される。
【００２６】
提供された指紋の近傍部分からの特徴点ペアの指標は、詳細な指標テーブルから一致する特徴点ペアを選択するために使用される。この選択により、具体的な特徴点ペアの対応が分かる。提供され、識別された特徴点の近傍部分の役割は相互に交換することができる。すなわち、詳細な指標テーブルは、提供された特徴点の近傍部分から作成することができる。一方、識別された特徴点の近傍部分からの特徴点ペアの指標は、詳細な指標テーブルから一致する特徴点ペアを選択するために使用される。
【００２７】
新しい詳細な指標テーブルを作成する代わりに、ステップ１中に前もって、格納している特徴点ペアの表示を含む特徴点ペアの識別番号を含む拡張指標テーブルを作成することもできる。次に、特徴点ペアが、その指紋識別番号、特徴点の近傍部分の識別番号、および特徴点ペアの識別番号により表示される。新しい指紋の近傍部分からの特徴点ペアの指標は、拡張指標テーブルから一致する特徴点ペアを選択するために使用される。しかし、ステップ２において発見された近傍部分からのこれらの特徴点ペア（すなわち、ステップ２において発見された特徴点の近傍部分と同じ指紋識別番号および特徴点の近傍部分の識別番号で表される特徴点ペア）だけがカウントされる。この選択により、具体的な特徴点ペアの対応が分かる。（別の方法としては、ステップ２中に、拡張指標テーブルから一致する特徴点ペアを予め選択する方法がある。）
【００２８】
対応する特徴点ペアの類似性は、完全な精度での直接的な特徴点ペアの違いの比較（例えば、特徴点ペアの特徴の違いの直接計算）により確認することができる。次に、確認済みの一致する特徴点ペアの数が、発見した特徴点の近傍部分に対して判別される。選択した閾値より大きい発見および確認した特徴点ペアの数を含む特徴点の近傍部分が選択され、対応する特徴点の近傍部分の識別番号が格納される。
【００２９】
最後に、確認済みの一致する特徴点の近傍部分の数が評価され、提供された指紋がそのデータが、ステップ６２において指標テーブル内に格納された指紋と一致するか否かについての決定が行われる。ステップ３において選択した確認済みの一致する特徴点の近傍部分が、その指紋識別番号によりグループ分けされる。各グループは、そこから指標テーブル内に格納している特徴点ペアを入手した対応する指紋からの確認済みの一致する特徴点の近傍部分を含む。各グループ内の確認済みの一致する特徴点の近傍部分の数が評価される。適切な閾値が、一致していると思われる２つの指紋に対する一致する特徴点の近傍部分の数に対して選択され、一致する指紋が、選択した閾値より大きい確認済みの一致する特徴点の近傍部分を含むグループとして選択される。
【００３０】
上記ステップは、下記のように高速指紋識別および確認の両方に使用することができる。
【００３１】
多くの指紋から作成した指標テーブルによる指紋識別：すべての登録済みの指紋からのすべての特徴点の近傍部分からのすべての特徴点ペアに指標が付けられ、指標テーブル内に格納される。新しい指紋と一致する指紋が、その特徴点ペアの指標により指標テーブルから選択される。
【００３２】
１つの指紋から作成した指標テーブルによる指紋識別：新しい指紋からのすべての特徴点の近傍部分からのすべての特徴点ペアに指標が付けられ、指標テーブル内に格納される。すべての登録済みの指紋が、その特徴点ペアの指標で指標テーブルから選択することにより新しい指紋と比較される。
【００３３】
指紋確認：１つの指紋からのすべての特徴点の近傍部分からのすべての特徴点ペアに指標が付けられ、指標テーブル内に格納される。第２の指紋が、その特徴点ペアの指標で、指標テーブルから選択することにより第１の指紋と比較される。
【００３４】
指標構造の絞り込み：指標テーブルから一致する特徴点ペアを発見するために、指標テーブル内に格納している提供された特徴点ペアおよび一致する特徴点ペアの両方は、等しい特徴点ペアの指標を有していなければならない。このことは、特徴点ペアの特徴の選択した許容範囲内にあるすべての特徴値に対して特徴点ペアの指標を作成することにより行われる。次に、各特徴点ペアは、そのカウントが選択した許容範囲により異なる複数の指標を有することができる。複数の特徴点ペアの指標は、特徴点ペアの表示が、すべてのその異なる指標に対して、複数回指標テーブル内に格納される指標テーブルの作成中に使用することもできるし、または別の方法としては、複数の指標を、すべてのその異なる指標により特徴点ペアを反復して選択することにより、指標テーブルから特徴点ペアを選択している間に使用することもできる。
【００３５】
上記詳細な説明において複数の好ましい例示的実施形態について説明してきたが、本発明は、種々様々に変更することができること、およびこれらの好ましい例示的実施形態は単に代表的な例に過ぎないこと、いかなる方法でも本発明の範囲、適用性または構成を制限するものではないことを理解されたい。それどころか、上記詳細な説明は、通常の当業者に例示として本発明の実施態様の分かりやすい指針を提供するものであり、上記実施形態の機能および配置を、本発明の精神および範囲から逸脱することなしに種々に変更することができる。
【図１】
2010526361.tif 000003
【図２】
2010526361.tif 000004
【図３】
2010526361.tif 000005
【図４】
2010526361.tif 000006
【図５】
2010526361.tif 000007
【国際調査報告】
2010526361.tif 000008
2010526361.tif 000009