(57)【要約】【課題】  バイオメトリクスを表現するための装置、方法、およびプログラム記憶装置を提供することにある。【解決手段】  この装置はバイオメトリック特徴抽出器と変換器とを含む。バイオメトリック特徴抽出器は、画像内に描かれたバイオメトリクスに対応する特徴を抽出し、その特徴のうちの１つまたは複数により１つまたは複数の幾何学的形状からなる１つまたは複数のセットを定義するためのものである。１つまたは複数の幾何学的形状のそれぞれは、その画像の少なくとも一部分に適用される第１のセットの変換に関して変化しない１つまたは複数の幾何学的特徴を有する。変換器は、１つまたは複数の幾何学的特徴のうちの１つまたは複数を含む１つまたは複数の特徴表現を入手するためにその画像の少なくとも一部分に第１のセットの変換を適用し、１つまたは複数の変換された特徴表現を入手するために１つまたは複数の特徴表現に第２のセットの変換を適用するためのものである。【選択図】  図２３
2008521109.tif 000002
【特許請求の範囲】
【請求項１】
バイオメトリクスを表現するための装置において、
画像内に描かれたバイオメトリクスに対応する特徴を抽出し、前記特徴のうちの少なくともいくつかにより少なくとも１つの幾何学的形状からなる少なくとも１つのセットを定義するためのバイオメトリック特徴抽出器であって、前記少なくとも１つの幾何学的形状のそれぞれが前記画像の少なくとも一部分に適用される第１のセットの変換に関して変化しない少なくとも１つの幾何学的特徴を有する、バイオメトリック特徴抽出器と、
前記少なくとも１つの幾何学的特徴のうちの少なくとも１つを含む少なくとも１つの特徴表現を入手するために前記画像の前記少なくとも一部分に前記第１のセットの変換を適用し、少なくとも１つの変換された特徴表現を入手するために前記少なくとも１つの特徴表現に第２のセットの変換を適用するための変換器と、
を有する装置。
【請求項２】
前記少なくとも１つの変換された特徴表現が、前記少なくとも１つの変換された特徴表現内の他の要素との相関関係のない少なくとも１つの要素を有し、前記少なくとも１つの要素と前記他の要素のうちの少なくとも１つが、互いに相関関係のない要素からなる要素セットを形成し、前記要素セットが前記バイオメトリクスを表現するためのものである、請求項１に記載の装置。
【請求項３】
前記少なくとも１つの変換された特徴表現が、相関関係許容差を超えるほど前記少なくとも１つの変換された特徴表現内の前記他の要素との相関関係のない前記少なくとも１つの要素を有する、請求項２に記載の装置。
【請求項４】
前記他の要素のうち、相関関係のある少なくとも１つが前記要素セットから除外される、請求項２に記載の装置。
【請求項５】
ハッシュ、識別プロセス、および選択プロセスのうちの少なくとも１つのために前記バイオメトリクスおよび前記画像のうちの少なくとも１つを表現するために、前記要素セットが索引として使用される、請求項２に記載の装置。
【請求項６】
前記索引がｎベースの索引であり、前記ｎベースの索引のビット数の規模が少なくとも２つの変換された特徴表現軸間の相関関係の程度によって決定される、請求項５に記載の装置。
【請求項７】
前記少なくとも１つの変換された特徴表現が、相関関係の程度によって降順に配置された少なくとも１つの相関関係のない要素と少なくとも１つの相関関係のある要素とを有し、前記少なくとも１つの相関関係のない要素と前記少なくとも１つの相関関係のある要素のうちの残りの要素が、互いに相関関係のない少なくとも２つの要素からなる要素セットを形成するように、前記少なくとも１つの相関関係のある要素のうちの少なくとも１つが除外され、前記要素セットが前記バイオメトリクスを表現するために使用されるｎビットの索引に量子化される、請求項２に記載の装置。
【請求項８】
前記要素セットの前記量子化が、相関関係しきい値を超える幾何学的形状を削除し、前記少なくとも１つの幾何学的形状のいずれかの最大数のみを許可し、前記少なくとも１つの幾何学的形状のいずれかをより単純な表現に変え、前記少なくとも１つの幾何学的形状のいずれかを単一の固有の識別子に変える、請求項７に記載の装置。
【請求項９】
非幾何学的であり、前記画像の前記一部分に適用される任意の剛性変換に関して変化しない少なくとも１つの測光特徴を前記画像から抽出するための測光特徴抽出器をさらに有し、前記少なくとも１つの測光特徴のそれぞれが前記少なくとも１つの幾何学的特徴のそれぞれに関連する前記画像の一領域に関連付けられ、前記少なくとも１つの特徴表現が前記少なくとも１つの測光特徴のうちの少なくとも１つをさらに含む、請求項１に記載の装置。
【請求項１０】
前記領域が、前記少なくとも１つの幾何学的形状の少なくとも１つ、前記少なくとも１つの幾何学的形状の内部、前記少なくとも１つの幾何学的形状の許容距離内の一領域、前記少なくとも１つの幾何学的形状の少なくとも３つの頂点がその上に存在する境界を有する曲線形状、前記少なくとも１つの幾何学的形状の少なくとも３つの頂点がその上に存在する境界を有する円形領域によって定義される、請求項９に記載の装置。
【請求項１１】
前記少なくとも１つの変換された特徴表現のうちの前記少なくとも１つの要素と他の要素を相関関係の程度によって降順に配置するための順序付け装置をさらに有する、請求項１に記載の装置。
【請求項１２】
前記順序付け装置が順序付けプロセスを実行する前に、前記少なくとも１つの幾何学的特徴のうちの少なくとも１つと前記画像から抽出された前記特徴のうちの少なくとも１つが結合される、請求項１１に記載の装置。
【請求項１３】
前記順序付け装置が、前記少なくとも１つの幾何学的特徴のうちの少なくとも１つについて、その後、前記画像から抽出された前記特徴のうちの少なくとも１つについて、順序付けプロセスを実行し、次に対応する順序付けの結果を結合する、請求項１１に記載の装置。
【請求項１４】
前記第１のセットの変換が相似変換に関して変化しない、請求項１に記載の装置。
【請求項１５】
登録画像が登録テンプレートによって表現され、前記登録テンプレートが前記少なくとも１つの幾何学的形状のうちの前記少なくとも１つに関連する前記少なくとも１つの幾何学的特徴のいずれかの非相関関係の程度によって順序付けられた前記少なくとも１つの幾何学的形状のうちの少なくとも１つである、請求項１に記載装置。
【請求項１６】
そこに登録テンプレートを保管するための少なくとも１つのデータベースと、
照会テンプレートを受け取る照会入力であって、前記照会テンプレートが前記少なくとも１つの幾何学的形状のうちの前記少なくとも１つに関連する前記少なくとも１つの幾何学的特徴のいずれかの非相関関係の程度によって順序付けられた前記少なくとも１つの幾何学的形状のうちの少なくとも１つである照会入力と、
前記照会テンプレートを保管された前記登録テンプレートと比較し、前記照会テンプレートに対応する照会画像に最も類似した少なくとも１つの登録画像を識別するための比較結果を出力する比較器と、
をさらに有する、請求項１に記載の装置。
【請求項１７】
前記照会テンプレートとそれに対応する登録テンプレートに共通するいくつかの索引によって登録画像と前記照会画像との相似性が確認される、請求項１６に記載の装置。
【請求項１８】
前記照会テンプレートとそれに対応する登録テンプレート内の共通索引に索引を付け、共通相似変換によって互いに関連する、複数対の選択され登録された照会幾何学的形状によって登録画像と照会画像との相似性が確認される、請求項１６に記載の装置。
【請求項１９】
バイオメトリクスを表現するための方法において、
画像内に描かれたバイオメトリクスに対応する特徴を抽出するステップと、
前記特徴のうちの少なくともいくつかにより少なくとも１つの幾何学的形状からなる少なくとも１つのセットを定義するステップであって、前記少なくとも１つの幾何学的形状のそれぞれが前記画像の少なくとも一部分に適用される第１のセットの変換に関して変化しない少なくとも１つの幾何学的特徴を有するステップと、
前記少なくとも１つの幾何学的特徴のうちの少なくとも１つを含む少なくとも１つの特徴表現を入手するために前記画像の前記少なくとも一部分に前記第１のセットの変換を適用するステップと、
少なくとも１つの変換された特徴表現を入手するために前記少なくとも１つの特徴表現に第２のセットの変換を適用するステップと、
を含む方法。
【請求項２０】
前記少なくとも１つの変換された特徴表現が、前記少なくとも１つの変換された特徴表現内の他の要素との相関関係のない少なくとも１つの要素を有し、前記少なくとも１つの要素と前記他の要素のうちの少なくとも１つが、互いに相関関係のない要素からなる要素セットを形成し、前記要素セットが前記バイオメトリクスを表現するためのものである、請求項１９に記載の方法。
【請求項２１】
ハッシュ、識別プロセス、および選択プロセスのうちの少なくとも１つのために前記バイオメトリクスおよび前記画像のうちの少なくとも１つを表現するために、前記要素セットが索引として使用される、請求項２０に記載の方法。
【請求項２２】
前記少なくとも１つの変換された特徴表現のうちの少なくとも１つの相関関係のない要素と少なくとも１つの相関関係のある要素を相関関係の程度によって降順に配置するステップと、
前記少なくとも１つの相関関係のない要素と前記少なくとも１つの相関関係のある要素のうちの残りの要素が、互いに相関関係のない少なくとも２つの要素からなる要素セットを形成するように、前記少なくとも１つの相関関係のある要素のうちの少なくとも１つを除外するステップと、
前記要素セットを前記バイオメトリクスを表現するために使用されるｎビットの索引に量子化するステップと、
をさらに含む、請求項２０に記載の方法。
【請求項２３】
非幾何学的であり、前記画像の前記一部分に適用される任意の剛性変換に関して変化しない少なくとも１つの測光特徴を前記画像から抽出するステップをさらに含み、前記少なくとも１つの測光特徴のそれぞれが前記少なくとも１つの幾何学的特徴のそれぞれに関連する前記画像の一領域に関連付けられ、前記少なくとも１つの特徴表現が前記少なくとも１つの測光特徴のうちの少なくとも１つをさらに含む、請求項１９に記載の方法。
【請求項２４】
前記少なくとも１つの変換された特徴表現のうちの前記少なくとも１つの要素と他の要素を相関関係の程度によって降順に配置するステップをさらに含む、請求項１９に記載の方法。
【請求項２５】
登録テンプレートを保管するステップと、
照会テンプレートを受け取るステップであって、前記照会テンプレートが前記少なくとも１つの幾何学的形状のうちの前記少なくとも１つに関連する前記少なくとも１つの幾何学的特徴のいずれかの非相関関係の程度によって順序付けられた前記少なくとも１つの幾何学的形状のうちの少なくとも１つであるステップと、
前記照会テンプレートを保管された前記登録テンプレートと比較するステップと、
前記照会テンプレートに対応する照会画像に最も類似した少なくとも１つの登録画像を識別するための比較結果を出力するステップと、
をさらに含む、請求項１９に記載の方法。
【請求項２６】
請求項１９に記載されたバイオメトリクスを表現するための方法ステップを実行するためにマシンによって実行可能な複数命令からなるプログラムを具体的に実施する、マシンによって読み取り可能なプログラム記憶装置。
【請求項２７】
コンピュータ上で実行されたときに請求項１９ないし請求項２５の前記ステップをすべて実行するために採用されたプログラム・コード手段を有するコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、画像処理の分野に関する。より具体的には、本発明は、三角画像の幾何学的および測光不変性に基づく指紋のマシン表現に関する。さらに、本発明は、三角形に基づく指紋のマシン表現を意図的にひずませ、次に安全でプライバシ保全のトランザクション処理でそのひずみ表現を使用することに関する。
【背景技術】
【０００２】
バイオメトリクスとは、人のＩＤ（identity）を決定または認証するために使用できる、その人の物理的特性または行動特性である。指紋痕跡などのバイオメトリクスは、犯罪者を識別するために何十年も法執行機関（lawenforcement agency）で使用されてきた。最近では、小切手の現金化やＡＴＭの使用などの多くのタイプのトランザクションで人を識別するために、顔、虹彩、および署名など、その他のバイオメトリクスが使用され始めている。自動バイオメトリクス識別システムは、パターン認識技法を使用してバイオメトリクス信号を分析し、照会バイオメトリクス信号がすでにデータベース内に存在するかどうかという判断に到達する。認証システムは、照会バイオメトリクスが請求されたＩＤに関連する保管バイオメトリクスに等しいかどうかまたはそれに類似しているかどうかをテストする。汎用自動バイオメトリクス・システムは、（ｉ）信号獲得、（ｉｉ）信号表現、（ｉｉｉ）パターン照合という３つの段階を有する。
【０００３】
図１、図２、図３、および図４は、従来技術によって使用される模範的なバイオメトリクスを例示する図である。図１には署名１１０が図示されている。図２には指紋痕跡１３０が図示されている。図３には音声（声紋）１２０が図示されている。図４には虹彩パターン１４０が図示されている。
【０００４】
バイオメトリクスは、（人間）対象者の自動認証または識別のために使用することができる。典型的には、たとえば、銀行預金口座を開く場合またはインターネット・サービスを申し込む場合にサンプル・バイオメトリクスを提供することによって対象者が登録される。このサンプル・バイオメトリクスからテンプレートが得られ、そのテンプレートは保管され、ユーザがその口座またはサービスにアクセスしたいときに照合のために使用される。バイオメトリクスは、ある程度一意的に人のＩＤを決定する。すなわち、バイオメトリクス信号を考慮すると、その信号は、一人の固有の人に関連付けられるか、またはこのバイオメトリクスが関連付けられる可能性のある人のリストを著しく狭くする。同じ指紋を有する２人の人が検出されることはないので、指紋は優れたバイオメトリクスである。これに対して、体重または靴のサイズなどの物理的特性は明らかに弁別価値をほとんど備えていないので、このようなバイオメトリクス信号は不十分なバイオメトリクスである。
【０００５】
バイオメトリクスは、行動バイオメトリクス（behavioral biometrics）と生理学的バイオメトリクス（physiological biometrics）に分類することができる。行動バイオメトリクスとしては、署名１１０および声紋１２０を含む（図１〜図４を参照）。行動バイオメトリクスは、人の身体状態および精神状態に依存し、時間の経過につれて変化しやすく、おそらく急速に変化しやすいものである。これに対して、生理学的バイオメトリクスは、あまり変化しやすいものではない。指紋の場合、隆起（ridge）と谷（valley）からなる基本的な流理構造（flowstructure）（図２の指紋１３０を参照）は本質的に人の寿命を通して変化しない。隆起は、たとえすり減っても、同じパターンで再生することになる。他の生理学的バイオメトリクスの一例は、対象者の虹彩の環状構造である（図４の虹彩１４０を参照）。これは、対象者の寿命を通してあまり変化しないと考えられている。要約すると、その外観が影響を受けない（虹彩１４０）かまたはほとんど影響を受けない（指紋１３０）生理学的バイオメトリクスとは対照的に、ある程度まで対象者の制御下にある行動バイオメトリクス（たとえば、署名１１０および音声１２０）が存在する。
【０００６】
次に図５を参照すると、典型的な既存の従来技術の自動指紋認証システム２００は、入力２１０としてバイオメトリクス信号（たとえば、指紋画像）を有する。このシステムは、信号処理段階２１５と、テンプレート抽出段階２２０と、テンプレート照合段階２２５とを含む。信号処理段階２１５は特徴を抽出し、テンプレート抽出段階２２０は抽出された特徴に基づいてテンプレートを生成する。バイオメトリクス信号２１０とともに、対象者の識別子（identifier）２１２がシステム２００に入力される。テンプレート照合段階２２５中に、ＩＤ（識別子）によって索引付けされたテンプレート２３０の何らかのデータベースから、この特定の識別子に関連するテンプレートが検索される。段階２２０で抽出されたテンプレートとデータベース２３０から検索されたテンプレートとの間に一致／一致なしが存在する場合、対応する「Ｙｅｓ／Ｎｏ」２４０という応答がシステム２００の出力になる。照合は典型的には相似性の尺度に基づくものであり、その尺度が著しく大きい場合、応答は「Ｙｅｓ」になり、そうではない場合、応答は「Ｎｏ」になる。
【０００７】
システムに入力されるバイオメトリクス信号２１０は、クライアント上の照合アプリケーションによりローカルで、または何らかのサーバ上で実行される照合アプリケーションによりリモートで獲得することができる。このため、システム２００のアーキテクチャは、ネットワーク化アプリケーションと非ネットワーク化アプリケーションのいずれにも適用される。
【０００８】
以下では、従来技術の例、すなわち、１９９５年１１月発行のＰａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ、第２８巻、第１１号、１６５７〜１６７２ページに掲載されたＲａｔｈａ他による「Ａｄａｐｔｉｖｅ  Ｆｌｏｗ  Ｏｒｉｅｎｔａｔｉｏｎ  Ｂａｓｅｄ  Ｆｅａｔｕｒｅ  Ｅｘｔｒａｃｔｉｏｎ  ｉｎ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｉｍａｇｅｓ」について説明する。
【０００９】
次に図６を参照すると、典型的な既存の従来技術の自動指紋識別システム２５０が図示されている。図６の従来技術のシステム２５０は図５のシステム２００と同様のものであるが、認証システムではなく、識別システムである。典型的な既存の従来技術の自動バイオメトリクス信号識別システム２５０は、入力としてバイオメトリクス信号２１０のみを取る。この場合も、システム２５０は、信号処理段階２１５と、テンプレート抽出段階２２０と、テンプレート照合段階２２５とを含む。信号処理段階２１５は特徴を抽出し、テンプレート抽出段階２２０は抽出された特徴に基づいてテンプレートを生成する。テンプレート照合段階２２５中に、抽出されたテンプレートがデータベース２３０内に保管されたすべての＜テンプレート、識別子＞の対と照合される。段階２２０で抽出されたテンプレートとデータベース２３０内の何らかのＩＤに関連するテンプレートとの間に良好な一致が存在する場合、識別システム２５０の結果２５５としてこの関連ＩＤが出力される。データベース２３０内でいかなる一致も検出できない場合、出力ＩＤ２５５はＮＩＬに設定できるであろう。バイオメトリクス信号２１０は、クライアント・マシン上でローカルで、または何らかのサーバ上で実行される照合アプリケーションによりリモートで獲得することができる。このため、システム２５０のアーキテクチャは、ネットワーク化アプリケーションまたは非ネットワーク化アプリケーションに等しく適用される。
【００１０】
自動バイオメトリクスは、本質的に、特徴を抽出するためのバイオメトリクス信号２１０の信号処理２１５に相当する。バイオメトリクス信号は、ある人の何らかのほぼ固有の特性である。特徴とは、指紋の隆起分岐（ridge bifurcation）または顔面画像内の左目の外観など、全体的な信号の下位特性（subcharacteristic）である。これらの特徴に基づいて、典型的には、よりコンパクトなテンプレート表現が２２０で構築される。このようなテンプレートは、他の同様に獲得され処理されたバイオメトリクス信号との照合または比較２２５に使用される。後述の通り、プライバシ保全で取り消し可能なバイオメトリクスが使用されるときにわずかに異なるのは、バイオメトリクス信号からテンプレートを入手するプロセスである。
【００１１】
細かい点（minutiae）のトリプレットによって形成された三角形による指紋の具体的な信号表現については、２０００年３月２１日に公布され、「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｍａｔｃｈｉｎｇ  Ｕｓｉｎｇ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ  Ｐａｒａｍｅｔｅｒ  Ｃｌｕｓｔｅｒｉｎｇ  Ｂａｓｅｄ  ｏｎ  Ｌｏｃａｌ  Ｆｅａｔｕｒｅ  Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅｓ」という発明の名称の米国特許第６０４１１３３号に開示されている。
【００１２】
登録段階中に、三角形の変化しない幾何学的特性が計算され、登録された指紋のリストを指し示すハッシュ・テーブルに保管される。認証時には、同じく三角形の変化しない幾何学的特性が指紋画像から抽出され、これらの三角形を使用して、可能な一致について承認する（vote）。これにより、大規模な指紋データベースの高速サーチが可能になる。このシステムは、大規模な１対多のサーチのために設計されている。
【００１３】
従来技術の問題
商用トランザクション・システムにおけるバイオメトリック認証の使用を促進する際の障害の１つは、プライバシの侵害に関する国民の認識である。名前、生年月日、およびその他の同様のパラメトリック・データなどの秘密情報以上に、ユーザは、指、顔、および虹彩など、自分の身体の一部の画像を提供するよう要求される。これらの画像またはその他のバイオメトリクス信号は、多くの場合、デジタル形式でデータベースに保管されることになる。このデジタル技術では、バイオメトリクス信号をコピーし、そのデータを他の目的に使用することは非常に容易である可能性がある。たとえば、ハッカは、通信チャネルにスヌープし、バイオメトリクス信号を傍受し、バイオメトリクスの適正な所有者に無断でそれを再利用することができるであろう。もう１つの懸念は、バイオメトリクス信号のデータベースを法執行機関と共用する可能性またはこれらのデータベースを商業組織間で共用する可能性である。当然のことながら、後者は、顧客について収集されたすべてのデータに関する懸念である。このようなプライバシに関する懸念は、以下のように要約することができる。第一に、顧客および顧客の行動について多くのデータが保管される。国民は、自分に関して知られている追加情報のすべてについて心配である。第二に、国民は、一般に、個人に関連する情報を中央で保管することについて警戒心を抱いている。このタイプのデータは医療記録からバイオメトリクスに及ぶ。これらのデータベースは、あらゆる類の目的に使用および乱用することができ、これらのデータベースは、組織間で共用することができる。第三に、バイオメトリクスは法執行機関によって使用されるデータベースとの照合に使用することができるので、国民は、正当にまたは不当に、バイオメトリクスを提供することについて心配している。たとえば、犯罪記録を入手するために、ＦＢＩまたはＩＮＳの指紋データベースと照合することができるであろう。
【００１４】
このため、１つの懸念は、その他の個人用パラメトリック・データと結合されたバイオメトリクスの伝送および保管である。もう１つの懸念は、他のデータベースをサーチするためにこれらのバイオメトリクスを使用する潜在的可能性である。
【００１５】
これらの懸念の多くは、バイオメトリクスを変更できないことにより、さらに悪化する。バイオメトリクスを認証のために非常に魅力的なものにしている特性の１つは、それらの経時的不変性であるが、これはバイオメトリクスの不利な点の１つでもある。クレジット・カード番号がどういうわけか損なわれた場合、発行銀行は顧客に新しいクレジット・カード番号を割り当てることができる。一般に、人工的手段を使用する場合、このような認証問題は、損なわれたトークンを取り消し、新しいトークンをユーザに再発行することにより、容易に修正することができる。しかし、バイオメトリクスが損なわれた場合、ユーザの選択肢はごくわずかである。指紋の場合、ユーザは他に９つの選択肢（自分の他の指）があるが、顔または虹彩の場合、代替物はすぐに使い果たされるかまたは存在しない。
【００１６】
バイオメトリクスのもう１つの不都合は、同じバイオメトリクスをいくつかの無関係の適用例に使用できることである。すなわち、ユーザは、同じバイオメトリクスを使用して、ビルの出入り、コンピュータのログイン、ＡＴＭの使用など、数通りのサービスに登録することができる。１つの適用例でバイオメトリクスが損なわれた場合、そのバイオメトリクスは本質的に、それらすべてについて損なわれており、何とかして変更する必要が生じるであろう。
【００１７】
いくつかの従来技術の方法では、鍵およびその他の認証トークンの取り消しを提案している。鍵および証明書はマシンで生成されるので、概念上、取り消しやすいものである。
【００１８】
ソース・オブジェクトを異なるオブジェクトに変形させるためにシリアルに表示すべき中間画像を作成する従来技術の画像モーフィング技法は、１９９６年１２月３１日に公布され、「Ｆｉｎｉｔｅ−ｅｌｅｍｅｎｔ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｉｍａｇｅ  Ａｌｉｇｎｍｅｎｔ  ａｎｄ  Ｍｏｒｐｈｉｎｇ」という発明の名称の米国特許第５５９０２６１号（以下「２６１号特許」という）に開示されている。
【００１９】
２６１号特許には、ソースおよびターゲット画像内の埋め込みノーダル・ポイントのモーション・モードに基づいて中間画像を決定するための有限要素ベースの方法が記載されている。画像内の特徴ポイントに対応する埋め込みノーダル・ポイントは、汎用特徴ベクトルによって表現される。ソースおよびターゲット画像内の特徴ポイントの対応は、特徴ベクトル空間内のポイント同士の接近によって決定される。この技法は、バイオメトリクスではなく、ビデオ制作の分野に適用され、モーフィングの際に人間の介入が必要になる程度を低減する対応割り当て技法に焦点を合わせている。さらに、この技法を適用可能にするために、ソースおよびターゲット画像は既知のものでなければならない。
【００２０】
また、１９９８年８月１１日に公布され、「Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ  Ｓｙｓｔｅｍ」という発明の名称の米国特許第５７９３８６８号（以下「８６８号特許」という）と、１９９７年９月９日に公布され、「Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ  Ｓｙｓｔｅｍ」という発明の名称の米国特許第５６６６４１６号（以下「４１６号特許」という）と、１９９８年２月１０日に公布され、「Ｗｉｔｎｅｓｓ−ｂａｓｅｄ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ  Ｓｙｓｔｅｍ」という発明の名称の米国特許第５７１７７５８号（以下「７５８号特許」という）が開示されている。
【００２１】
８６８号特許には、認証局（ＣＡ：certification authority）を必要とする証明書管理が開示されている。多くの場合、公開鍵インフラストラクチャ内の鍵が損なわれているかまたはそのユーザがもはや特定のＣＡのクライアントではない場合、その証明書は取り消さなければならない。ＣＡは、非常に長く、全員にブロードキャストする必要がある証明書取り消しリスト（ＣＲＬ：certificaterevocation list）を定期的に発行する。この特許では、証明書の少なくとも一部に関するハッシュを生成することを提案している。そのデータ項目が２つまたはそれ以上の取り消された証明書によって共用される場合、その証明書を識別する最小データがＣＲＬに追加される。したがって、提案された方法は、ＣＲＬのサイズを最適化し、このため、伝送時間を短縮するものである。８６８号特許では、身体の一部に関する信号ではなく、マシンで生成された証明書を扱っている。さらに、それを本当に可能なものにするのではなく、取り消しプロセスをより効率的なものにすることに関するものである。
【００２２】
４１６号特許では、取り消された証明書のリストを明示的に提供しない公開鍵管理を扱っている。ユーザは、公開鍵証明書に関する個々の情報を受け取ることができる。まだ満了していないそれぞれの証明書の有効性状況に関する肯定情報を提供するための方法が記載されている。提案されている方法では、ＣＡは、信頼できるディレクトリを必要とせずに証明書有効性情報を提供することになる。加えて、証明書がまったく発行されなかったかまたはＣＡにすら存在しなかったことを証明するための方式も記載されている。ここに記載した技法は、バイオメトリクスではなく、容易に取り消されるマシン生成鍵にのみ適用可能である。
【００２３】
７５８号特許ではさらに、公開鍵インフラストラクチャを扱っている。提案されている方式では、認証済み証明書情報を受け取り、次にその認証済み情報の一部分を処理して推定された情報を入手することにより、仲介（intermediary）が証明書情報を提供する。推定された情報が認証情報と整合している場合、証人（witness）が推定された情報を構築し、推定された情報を認証する。この特許の主な新規性は、すべてのユーザに長い証明書取り消しリスト（ＣＲＬ）を伝送することを回避し、非標準ＣＲＬの処理が仲介に任される点である。この方法では、バイオメトリクス信号ではなく、マシン生成鍵およびその管理に関連する問題に対処する。この場合も、焦点は、まず第一に取り消しを可能にすることではなく、証明書のプライバシおよび取り消しの効率に当てられている。
【００２４】
１９９３年１１月に公布され、Ｐｅｒｌｍａｎ他による「Ｍｅｔｈｏｄ  ｏｆ  Ｉｓｓｕａｎｃｅ  ａｎｄ  Ｒｅｖｏｃａｔｉｏｎ  ｏｆ  Ｃｅｒｔｉｆｉｃａｔｅ  ｏｆ  Ａｕｔｈｅｎｔｉｃｉｔｙ  Ｕｓｅｄ  ｉｎ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｎｅｔｗｏｒｋｓ  ａｎｄ  Ｏｔｈｅｒ  Ｓｙｓｔｅｍｓ」という発明の名称の米国特許第５２６１００２号（以下「００２号特許」という）が開示されている。
【００２５】
００２号特許には、いかなる満了日も含まないユーザ証明書を発行し、取り消すための技法が記載されている。満了日の欠如は、ルーチン更新に関連するオーバヘッドを最小限にする。提案されている方法では、ブラックリスト開始日と、ブラックリスト満了日と、その証明書がブラックリスト開始日以降に発行されたが、現在無効になっている各ユーザごとの項目とを含む、無効証明書の署名付きリスト（ブラックリストという）を発行する。この方法には、マシン生成証明書の取り消しおよび発行について記載されているが、バイオメトリクスの特別な特性に対処するものではない。
【００２６】
標準的な暗号方法とバイオメトリクス画像または信号は、１９９１年２月１２日に公布され、「Ｕｎｆｏｒｇｅａｂｌｅ  Ｐｅｒｓｏｎａｌ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ｓｙｓｔｅｍ」という発明の名称の米国特許第４９９３０６８号（以下「０６８号特許」という）が開示されている。
【００２７】
０６８号特許では、標準的な暗号方法とバイオメトリクス画像または信号との結合を扱っている。提案されている方式では、ユーザの物理的に変化しない識別資格情報（たとえば、バイオメトリクス）のセットを暗号化し、それをポータブル・メモリ・デバイスに保管する。これは、最新の公開鍵または単方向暗号技法を使用して、資格情報のセットを捏造不能なものにする。この資格情報は、プライバシのためにクレジットカード・サイズのポータブル・メモリ・デバイスに保管される。リモート・サイトでは、ユーザは、サーバによる比較のために身体的バイオメトリクス（すなわち、ユーザ自身またはユーザの身体の一部）とポータブル・メモリ・カードを提示する。この技法は、有用であるが、暗号化方式に対する標準的な攻撃を受けやすく、暗号化が破られた場合に潜在的にバイオメトリクスを露出する可能性がある。さらに、暗号化解除後に、他のデータベースとの比較の可能性のために、真のバイオメトリクス信号がサーバにとって使用可能になり、その結果、個人のプライバシが低減される。
【００２８】
１９９５年７月１８日に公布され、「Ｕｎｆｏｒｇｅａｂｌｅ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ｄｅｖｉｃｅ，  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ｄｅｖｉｃｅ  Ｒｅａｄｅｒ  ａｎｄ  Ｍｅｔｈｏｄ  ｏｆ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ」という発明の名称の米国特許第５４３４９１７号（以下「９１７号特許」という）が開示されている。
【００２９】
９１７号特許では、カード上にプロセッサを備える必要性がなく手ごろな価格の捏造不能なメモリ・カードの設計を扱っている。このカードのプラスチック支持部は、ランダムに分布しているフェライト粒子を含んで製造されている。安全なデジタル署名を作成するために、この固有の粒子分布が標準的なユーザ識別情報と結合される。その後、所有者ＩＤとともにデジタル署名が（磁気ストリップまたは同様の手段の使用により）カード上に保管される。読取装置は、ＩＤを読み取り、フェライト粒子分布も感知することによって、ユーザを認証する。次に読取装置は、保管されたデジタル署名が、所与のＩＤと観測された粒子分布とを結合することによって形成されると思われるものと同じ署名であることをチェックする。この技法の捏造不能な部分は、形成プロセス中のプラスチック基板内のフェライト粒子のランダム分布に関連する。所有者の識別詳細はバイオメトリクスに関連するものではない。
【００３０】
データ隠蔽技法の頑強性の評価を対象とする「Ｓｔｉｒｍａｒｋ」と呼ばれるソフトウェア・システムは、１９９９年６月発行のＰｒｏｃ．  ＩＥＥＥ  Ｍｕｌｔｉｍｅｄｉａ  Ｓｙｓｔｅｍｓ  ９９、第１巻、７〜１１ページおよび５７４〜５７９ページに掲載されたＰｅｔｉｔｃｏｌａｓ他による「Ｅｖａｌｕａｔｉｏｎ  ｏｆ  Ｃｏｐｙｒｉｇｈｔ  Ｍａｒｋｉｎｇ  Ｓｙｓｔｅｍｓ」に記載されている。
【００３１】
Ｓｔｉｒｍａｒｋシステムは、わずかな伸び、ずれ、転位、曲がり、および回転による軽微で目立たない幾何学的ひずみを適用するものである。また、Ｓｔｉｒｍａｒｋは、データ隠蔽技法をテストするためのサンプルに、高周波変位、被変調低周波数偏移、滑らかに分散されたエラーを導入する。この文献は、これらの目立たないひずみの後でも信号内に隠蔽されたウォータマークを回復できるかどうかのテストに関係するものである。このシステムは、プライバシを強化するためまたは許可の取り消しを可能にするために、信号を意図的にひずませるわけではない。
【００３２】
図７および図８は、取り消し可能なバイオメトリック表現をバイオメトリクス信号２１０からどのように構築できるかに関する２通りの手法を使用する２通りのシステムを例示するブロック図である。システム３００（図７）では、変換モジュール３１０によってバイオメトリクスをひずませて、取り消し可能なバイオメトリクス３２０を入手する。次に特徴抽出３３０のための信号処理を使用して、テンプレート３４０を入手する。前に記載した通り、このテンプレートは、照合のために使用されるコンパクトなマシン表現である。対照してみると、システム３５０（図８）では、まず特徴抽出３６０（信号処理）を実行して、よりコンパクトな表現を生成する。次に、テンプレート３７０を抽出し、その後、最終的にコード化３８０を使用して、取り消し可能なテンプレート３９０を構築する。
【００３３】
適用例の観点から見ると、取り消し可能性がどのようにもたらされるかは重要ではないので、いずれの手法も取り消し可能なバイオメトリクスと呼ばれる。いずれの実現例でも重要なポイントは、異なる人について異なるコード化を、あるいは同じ人についても異なる時期および適用例に対して異なるコード化を選択できることである。さらに、同じ人からのバイオメトリクス信号が処理されるたびに同様の結果が得られるように、これらのコード化が再現可能であることは重要なことである。以下の考察には、適切にコード化されたバイオメトリクス信号およびバイオメトリック・テンプレートを入手するために３１０および３８０に関する具体的な方法が記載されている。
【００３４】
２０００年６月１６日に出願され、Ｂｏｌｌｅ他による「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｄｉｓｔｏｒｔｉｎｇ  ａ  Ｂｉｏｍｅｔｒｉｃ  ｆｏｒ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｗｉｔｈ  Ｅｎｈａｎｃｅｄ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ」という発明の名称の米国特許出願第０９／５９５９３５号（以下「９３５号特許出願」という）が開示されている。
【００３５】
９３５号特許出願では、様々なバイオメトリック識別子（画像および信号）に関するバイオメトリック・テンプレートまたはバイオメトリクス信号のひずみを提案している。９３５号特許出願では、三角形による実用的な指紋表現を提案しておらず、三角形の変換による実用的で取り消し可能な指紋表現を提案していない。画像データは、変換された三角形内にそれを納めるためにあるいは１次元またはｍ次元の記述から変換された１次元またはｍ次元の記述に三角形を変換するために、三角画像データをワープすることによって明確に変換されるわけではない。
【特許文献１】米国特許第６０４１１３３号
【特許文献２】米国特許第５５９０２６１号
【特許文献３】米国特許第５７９３８６８号
【特許文献４】米国特許第５６６６４１６号
【特許文献５】米国特許第５７１７７５８号
【特許文献６】米国特許第５２６１００２号
【特許文献７】米国特許第４９９３０６８号
【特許文献８】米国特許第５４３４９１７号
【特許文献９】米国特許出願第０９／５９５９３５号
【特許文献１０】米国特許第６０７２８９５号
【特許文献１１】米国特許第６２６６４３３号
【非特許文献１】１９９５年１１月発行のＰａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ、第２８巻、第１１号、１６５７〜１６７２ページに掲載されたＲａｔｈａ他による「Ａｄａｐｔｉｖｅ  Ｆｌｏｗ  Ｏｒｉｅｎｔａｔｉｏｎ  Ｂａｓｅｄ  Ｆｅａｔｕｒｅ  Ｅｘｔｒａｃｔｉｏｎ  ｉｎ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｉｍａｇｅｓ」
【非特許文献２】１９９９年６月発行のＰｒｏｃ．  ＩＥＥＥ  Ｍｕｌｔｉｍｅｄｉａ  Ｓｙｓｔｅｍｓ  ９９、第１巻、７〜１１ページおよび５７４〜５７９ページに掲載されたＰｅｔｉｔｃｏｌａｓ他による「Ｅｖａｌｕａｔｉｏｎ  ｏｆ  Ｃｏｐｙｒｉｇｈｔ  Ｍａｒｋｉｎｇ  Ｓｙｓｔｅｍｓ」
【非特許文献３】ミシガン州アナーバーのＣＲＣ  Ｐｒｅｓｓから発行され、Ｌｅｅ他によって編集された「Ａｄｖａｎｃｅｓ  ｉｎ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｔｅｃｈｎｏｌｏｇｙ」
【非特許文献４】１９９５年１１月発行のＪｏｕｒｎａｌ  ｏｆ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ、第２８巻、第１１号、１６５７〜１６７２ページに掲載されたＲａｔｈａ他による「Ａｄａｐｔｉｖｅ  Ｆｌｏｗ  Ｏｒｉｅｎｔａｔｉｏｎ  Ｂａｓｅｄ  Ｔｅｘｔｕｒｅ  Ｅｘｔｒａｃｔｉｏｎ  ｉｎ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｉｍａｇｅｓ」
【非特許文献５】ニュージャージー州のＰｒｅｎｔｉｃｅ  Ｈａｌｌから発行されたＢａｌｌａｒｄ他による「Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ」の２５４〜２５９ページ
【非特許文献６】１９９９年４月発行のＪｏｕｒｎａｌ  ｏｆ  Ｖｉｓｕａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ａｎｄ  Ｉｍａｇｅ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ、第１０巻、第４号、３９〜６２ページに掲載されたＲｕｉ他による「Ｉｍａｇｅ  Ｒｅｔｒｉｅｖａｌ：  Ｃｕｒｒｅｎｔ  Ｔｅｃｈｎｉｑｕｅｓ，  Ｐｒｏｍｉｓｉｎｇ  Ｄｉｒｅｃｔｉｏｎｓ  Ａｎｄ  Ｏｐｅｎ  Ｉｓｓｕｅｓ」
【非特許文献７】２０００年にＷｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅから発行されたＤｕｄａ他によるＰａｔｔｅｒｎ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ（第２版）
【発明の開示】
【発明が解決しようとする課題】
【００３６】
従来技術の上記その他の欠点および短所は、三角形に基づく指紋バイオメトリック・マシン表現を対象とする本発明によって対処される。
【課題を解決するための手段】
【００３７】
本発明の一態様により、バイオメトリクスを表現するための装置が提供されている。この装置はバイオメトリック特徴抽出器と変換器とを含む。バイオメトリック特徴抽出器は、画像内に描かれたバイオメトリクスに対応する特徴を抽出し、その特徴のうちの少なくともいくつかにより少なくとも１つの幾何学的形状からなる少なくとも１つのセットを定義するためのものである。少なくとも１つの幾何学的形状のそれぞれは、その画像の少なくとも一部分に適用される第１のセットの変換に関して変化しない少なくとも１つの幾何学的特徴を有する。変換器は、少なくとも１つの幾何学的特徴のうちの少なくとも１つを含む少なくとも１つの特徴表現を入手するためにその画像の少なくとも一部分に第１のセットの変換を適用し、少なくとも１つの変換された特徴表現を入手するために少なくとも１つの特徴表現に第２のセットの変換を適用するためのものである。
【００３８】
本発明の他の態様により、バイオメトリクスを表現するための方法が提供されている。画像内に描かれたバイオメトリクスに対応する特徴が抽出される。その特徴のうちの少なくともいくつかにより、少なくとも１つの幾何学的形状からなる少なくとも１つのセットが定義される。少なくとも１つの幾何学的形状のそれぞれは、その画像の少なくとも一部分に適用される第１のセットの変換に関して変化しない少なくとも１つの幾何学的特徴を有する。少なくとも１つの幾何学的特徴のうちの少なくとも１つを含む少なくとも１つの特徴表現を入手するためにその画像の少なくとも一部分に第１のセットの変換が適用される。少なくとも１つの変換された特徴表現を入手するために少なくとも１つの特徴表現に第２のセットの変換が適用される。
【００３９】
本発明の上記その他の態様、特徴、および利点は、添付図面に併せて読まれる、模範的な諸実施形態に関する以下の詳細な説明から明らかになるであろう。
【００４０】
次に、添付図面に関連して、例証としてのみ、本発明の好ましい諸実施形態について説明する。
【発明を実施するための最良の形態】
【００４１】
多くの適用例の場合、ユーザ認証は重要かつ本質的な構成要素である。自動バイオメトリクスは、正確かつ拒絶不能な認証方法を提供することができる。デジタル界では、同じ利点には、いくつかの重大な短所が付随する。バイオメトリクス信号のデジタル表現は、所有者にとって未知の多くの適用例に使用することができる。第二に、この信号は、法執行機関に容易に伝送することができ、したがって、ユーザのプライバシを侵害する。本発明は、結果として得られる同じ指紋表現を２つの施設が共用しないように元の指紋表現を意図的にひずませるために三角形に基づく指紋表現の変換を使用して、これらの問題を克服するための方法を提供する。
【００４２】
本発明では、本明細書で「匿名バイオメトリクス（anonymous biometrics）」とも呼ばれる取り消し可能なバイオメトリック表現の特定のインスタンスである取り消し可能な指紋表現について記載している。伝統的なバイオメトリック表現とは異なり、これらのバイオメトリック表現は、どういうわけか損なわれたときに変更することができる。取り消し可能なバイオメトリック表現は、元のバイオメトリック表現の変換であり、その結果、元の表現と同じフォーマットの意図的なコード化バイオメトリック表現になる。このひずみは、実世界のバイオメトリクスの記録条件の変動にかかわらず、毎回、同じ（または非常に類似した）コード化バイオメトリック表現を生成するという意味で反復可能である。コード化が不可逆性である場合、元のバイオメトリック表現は、取り消し可能なバイオメトリクスから得ることができず、したがって、ユーザのために余分なプライバシを保証することになる。より具体的には、コード化三角形による指紋表現に焦点が当てられている。しかし、本発明は指紋のみに限定されるわけではなく、したがって、本発明により他のバイオメトリクスも容易に使用できることが分かるであろう。
【００４３】
指紋画像圧縮は取り消し可能な指紋表現と見なすことができるであろうが、本発明はこのような従来技術の技法とは異なるものである。圧縮には、元の信号のすべての細部を保全するわけではない損失の大きい方法が存在する。このような変換は確かに不可逆性である。その圧縮方法次第で、圧縮データについて直接実行可能な画像処理操作がいくつか存在する。しかし、一般に、データは、使用前に圧縮解除される。その上、暗号化とは異なり、これを実行するための方法は、通常、広く知られており、したがって、どのような当事者でも適用することができる。その上、圧縮解除された信号は、構造については元の信号に非常に近いものである。したがって、その信号は、元の信号の代わりにそのまま使用できる場合が多く、この変換によって得られるセキュリティ上の利点はまったくない。さらに、（前のひずみを取り消すために）圧縮エンジンのパラメータを変更すると、その結果、依然として元の信号に非常に類似した圧縮解除された信号が得られることになる。
【００４４】
指紋暗号化も取り消し可能な指紋表現と見なすことができるであろうが、本発明はこのような従来技術の技法とは異なるものである。暗号化では、伝送された信号はその未加工形式では有用ではなく、意味をなすためには受信側で暗号化解除しなければならない。さらに、いずれの暗号化システムも、設計については可逆変換に基づくものであり、不可逆機能では動作しないものである。暗号化システムでは、依然として、所有者に無断で他の機関とその信号を共用することが可能であると思われる。取り消し可能な指紋表現は、コード化ドメイン内で照合可能な指紋のコード化である。暗号化指紋表現とは異なり、２つの指紋の照合には、いかなる暗号化解除鍵も不要である。
【００４５】
指紋などの伝統的なバイオメトリクスは、数十年間、（自動）認証および識別のために使用されてきた。署名は法的拘束力を持つＩＤ証明として受け入れられており、自動署名／認証／検証方法は少なくとも２０年間、使用可能であった。
【００４６】
本発明の好ましい一実施形態は、指紋を表現するために三角形を使用することである。したがって、次に、一般性を失わずに、三角形を指紋に適用することについて説明する。その他の非指紋バイオメトリクスとともにその他の幾何学的形状を使用できることに留意されたい。たとえば、顔面画像は、空間的に隣接する４つの目標顔面特徴ポイント（たとえば、唇の隅、鼻孔、目の隅など）からなる四辺形によって表現することができる。その上、本発明は、チェーン・コード、ポリライン、多角形、正規化多角形、正方形、正規化正方形、長方形、正規化長方形、三角形、および正規化三角形という幾何学的形状を含むことができるが、これらに限定されない。
【００４７】
さらに、主に指紋画像に関して本発明を説明するが、本発明は、完全なバイオメトリクス、部分的なバイオメトリクス、特徴、特徴の位置、特徴の特性、少なくとも２つの特徴間の関係、他の画像の小領域、指紋画像、部分的な指紋画像、虹彩画像、網膜像、耳の画像、手の形状画像、顔面画像、歩行測定値、皮下血管パターン、話し言葉、署名に対応するが、これらに限定されない画像に適用できることが分かるであろう。
【００４８】
図９を参照すると、指紋は、典型的には、指紋４００に関連する特徴ポイント（一般に「細かい点」と呼ばれ、典型的には４１０である）の集合を特徴付けるデータによって表現される。指紋に関連する特徴ポイントは、典型的には、画像処理技法を使用して、指紋の画像から得られる。これらの技法は、上記の通り、周知のものであり、獲得モードと認識モードという２つの別個のモードに区分することができる。
【００４９】
いくつかの好ましい獲得モードでは、指紋画像の１つまたは複数の三角表現について、所与の指紋画像に関する特徴ポイントのサブセット（トリプレット）が決定的に生成される。所与の指紋画像に関する特徴ポイントの１つまたは複数のサブセット（トリプレット）が選択される。選択された各サブセット（トリプレット）について、その選択されたサブセット（トリプレット）の付近の指紋形状（fingerprint geometry）を特徴付けるデータが生成される。選択されたサブセット（トリプレット）に対応するデータは、鍵（または索引）を形成するために使用される。この鍵は、マルチマップからの項目を保管し検索するために使用され、マルチマップは、メモリ内に保管された２つ以上の項目を同じ鍵に関連付けることを可能にする連想メモリの一形式である。好ましくは、この鍵を生成した指紋画像を識別する識別子と、この鍵を生成した特徴ポイントのサブセット（トリプレット）に関する情報（またはこのような情報へのポインタ）とを含む項目が生成される。次に、この鍵によってラベルが付けられた項目がマルチマップに保管される。
【００５０】
いくつかの好ましい認識モードでは、照会（三角表現）指紋画像がシステムに供給される。獲得モードと同様に、照会指紋画像の特徴ポイントのサブセット（トリプレット、たとえば、Ａ、Ｂ、およびＣ）が、好ましくは、一貫して（たとえば、同様に）生成される。照会指紋画像の特徴ポイントの１つまたは複数のサブセット（トリプレット）が選択される。選択された各サブセット（トリプレット）について、その選択されたサブセット（トリプレット）の付近の照会指紋を特徴付けるデータが生成される。選択されたサブセットに対応するデータは、鍵を形成するために使用される。マルチマップ内の項目のうち、この鍵に関連するすべての項目が検索される。上述の通り、この項目は、参照された指紋画像を識別する識別子を含む。検索された各項目について、照会指紋画像と参照指紋画像との間の仮説上の一致（hypothesized match）が構築される。この仮説上の一致は、参照指紋画像の識別子によってラベルが付けられ、任意選択で、照会指紋画像内の特徴のサブセット（トリプレット）を参照指紋画像内の特徴のサブセット（トリプレット）に対して最も緊密に対応させるような座標変換のパラメータによってラベルが付けられる。仮説上の一致は承認テーブル（vote table）に累積される。承認テーブルは、参照指紋画像の識別子および変換パラメータ（使用されている場合）によって鍵が付けられた連想メモリである。承認テーブルは、対応する参照指紋画像の識別子および変換パラメータ（使用されている場合）に関連するスコアを保管する。新たに検索された項目により、連想メモリ内にすでに存在する仮説が生成されると、たとえば、スコアを１だけ増分することにより、検索された項目に対応するスコアが更新される。最後に、承認テーブルに保管されたすべての仮説がそのスコア順にソートされる。仮説およびスコアからなるこのリストは、好ましくは、照会指紋画像との一致がシステムによって保管されているかどうかを判断するために使用される。代わって、仮説およびスコアからなるこのリストは、照会指紋画像を照合するための他のメカニズムへの入力として使用することもできる。したがって、たとえば、本発明の例示的な一実施形態では、登録画像と照会画像との相似性は、照会テンプレートとそれに対応する登録テンプレート内で共通するいくつかの索引によって確認される。本発明の他の例示的な実施形態では、登録画像と照会画像との相似性は、照会テンプレートとそれに対応する登録テンプレート内の共通索引に索引を付けるいくつかの選択された幾何学的形状によって確認される。本発明のさらに他の実施形態では、登録画像と照会画像との相似性は、照会テンプレートとそれに対応する登録テンプレート内の共通索引に索引を付け、共通相似変換によって互いに関連する、複数対の選択され登録された照会幾何学的形状によって確認される。相似性は、ハミング距離、ベクトル比較、接近アルゴリズム（closeness algorithm）、直線的数値間比較（straight number to number comparison）に基づいて決定することができるが、これらに限定されない。登録画像と照会画像との相似性を決定するための前述の手法は単に例示的なものにすぎず、本明細書に提供される本発明の教示を考慮すると、当業者であ���ば、本発明の精神を維持しながら、登録画像と照会画像との相似性を決定するための上記その他の様々な手法を企図することが分かるであろう。
【００５１】
指紋画像の特徴ポイントは、好ましくは、インク・カードのデジタル化、減衰全反射（frustrated total internalreflection）画像処理を使用する指の直接ライブ・スキャン（direct live-scanning）、３次元範囲調整（range-finding）技法、またはその他の技術によって獲得された指紋のグレースケール画像から抽出される。
【００５２】
指紋画像の特徴ポイントは、好ましくは、指紋の隆起パターン内の特異点（singularity）から決定される。図９に図示されている通り、隆起パターンは、隆起終了および隆起分岐などの特異点を含む。ポイントＡは隆起分岐の一例である。ポイントＢおよびＣは隆起終了の例である。
【００５３】
図１０は、図９の特徴ポイントを特徴付ける幾何学的特徴５００を図表現する図である。図１０に図示されている通り、それぞれの局所的特徴は、好ましくは、所与の指紋画像内のすべての局所的特徴に共通する基準系内のその局所的特徴の座標（ｘ，ｙ）によって特徴付けられる。
【００５４】
本発明を適用可能であるかまたは本発明が使用可能である幾何学的特徴としては、線の長さ、辺の長さ、辺の方向、線の交差、線の交差カウント、統計値、画像、角度、頂角、外角、少なくとも１つの幾何学的形状によって制限された領域、少なくとも１つの幾何学的形状によって制限された領域の一部分、少なくとも１つの幾何学的形状の偏心、少なくとも１つの幾何学的形状のオイラー数、少なくとも１つの幾何学的形状のコンパクトさ、少なくとも１つの幾何学的形状の傾斜密度関数（slope density function）、少なくとも１つの幾何学的形状のシグネチャ、少なくとも１つの幾何学的形状の構造的特徴記述、少なくとも１つの幾何学的形状の凹部、少なくとも１つの幾何学的形状を囲む凸形状、少なくとも１つの幾何学的形状を記述する形状番号（shape number）を含むが、これらに限定されない。
【００５５】
詳細に後述する獲得モードおよび認識モードでは、所与の指紋画像の特徴ポイント（たとえば、細かい点）のサブセット（トリプレット）が選択され、選択された各サブセット（トリプレット）について、その選択されたサブセットの特徴ポイントの付近の指紋画像を特徴付けるデータが生成される。好ましくは、このようなデータとしては、選択されたサブセットを構成する特徴ポイントの各対に関連する距離Ｓ、および選択されたサブセット内の各特徴ポイントの座標（ｘ，ｙ）における隆起の局所的方向（ｈ）のような幾何学的データを含む。より具体的には、所与の１対の特徴ポイントに関連する距離Ｓは、好ましくは、対応する特徴ポイント間に引かれた線の距離を表す。加えて、所与の特徴ポイントに関連する局所的方向（ｈ）は、好ましくは、選択されたサブセット内の所与の特徴ポイントから他の特徴ポイントに引かれた線に関する所与の特徴ポイントにおける隆起の方向を表す。たとえば、図９および図１０に例示されている特徴ポイントＡ、Ｂ、Ｃのトリプレットの場合、トリプレットＡ、Ｂ、Ｃの付近の指紋画像を特徴付けるデータは、図１１に図示されているパラメータ（Ｓ1、Ｓ2、Ｓ3、ｈ1、ｈ2、ｈ3）を含むことになるであろう。図１１は、本発明の例示的な一実施形態により、図９の特徴ポイントを特徴付ける幾何学的特徴６００を図表現する図である。
【００５６】
加えて、選択されたサブセットの特徴ポイントの付近の指紋画像を特徴付けるデータとしては、好ましくは、選択されたサブセットを構成する複数対の特徴ポイントに関連する隆起カウントを含む。より具体的には、所与の１対の特徴ポイントに関連する隆起カウントＲＣは、好ましくは、対応する特徴ポイント間に引かれた線が交差する隆起の数を表す。たとえば、図１１に例示されている特徴ポイントＡ、Ｂ、Ｃのトリプレットの場合、トリプレットＡ、Ｂ、Ｃの付近の指紋画像を特徴付けるデータは、隆起カウント・パラメータ（ＲＣAB、ＲＣAC、ＲＣBC）をさらに含むことになり、ＲＣABは特徴ポイントＡおよびＢの間に引かれた線が交差する隆起の数を表し、ＲＣACは特徴ポイントＡおよびＣの間に引かれた線が交差する隆起の数を表し、ＲＣBCは特徴ポイントＢおよびＣの間に引かれた線が交差する隆起の数を表し、これらは図１１にはそれぞれＲＣ1、ＲＣ2、およびＲＣ3として示されている。
【００５７】
変化しない特徴および関連データを抽出するための多種多様な実現例が存在し、そのいずれも本発明で使用可能なものである。たとえば、特徴ポイントおよび関連データは、ミシガン州アナーバーのＣＲＣ  Ｐｒｅｓｓから発行され、Ｌｅｅ他によって編集された「Ａｄｖａｎｃｅｓ  ｉｎ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｔｅｃｈｎｏｌｏｇｙ」および１９９５年１１月発行のＪｏｕｒｎａｌ  ｏｆ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ、第２８巻、第１１号、１６５７〜１６７２ページに掲載されたＲａｔｈａ他による「Ａｄａｐｔｉｖｅ  Ｆｌｏｗ  Ｏｒｉｅｎｔａｔｉｏｎ  Ｂａｓｅｄ  Ｔｅｘｔｕｒｅ  Ｅｘｔｒａｃｔｉｏｎ  ｉｎ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｉｍａｇｅｓ」に記載されている画像処理技法により自動的に抽出することができる。
【００５８】
特に、使用可能な指紋不変特徴抽出技法は、２０００年６月６日に公布され、「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  Ｕｓｉｎｇ  Ｍｉｎｕｔｉａｅ  Ｐｒｕｎｉｎｇ  ｆｏｒ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ」という発明の名称の米国特許第６０７２８９５号および２００１年７月２４日に公布され、「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｄｅｔｅｒｍｉｎｉｎｇ  Ｒｉｄｇｅ  Ｃｏｕｎｔｓ  ｉｎ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ」という発明の名称の米国特許第６２６６４３３号という米国特許に記載されている。
【００５９】
典型的な「指紋（dab）」痕跡は、特徴抽出ソフトウェアによって認識される約４０個の特徴ポイントを有することになるが、特徴ポイントの数は、指の形態および画像処理条件次第で０から１００超まで変動する可能性がある。
【００６０】
特徴ポイントおよび関連データの導出、獲得モード、ならびにデータベースを表現するための構造がハッシュ・テーブルになる認識モードに関するより詳細な説明は、２０００年３月２１日に公布され、「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｍａｔｃｈｉｎｇ  Ｕｓｉｎｇ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ  Ｐａｒａｍｅｔｅｒ  Ｃｌｕｓｔｅｒｉｎｇ  Ｂａｓｅｄ  ｏｎ  Ｌｏｃａｌ  Ｆｅａｔｕｒｅ  Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅｓ」という発明の名称の米国特許第６０４１１３３号に記載されている。
【００６１】
本発明の一実施形態によれば、三角形（および、一般に、多角形）を使用して、指紋（またはその他の画像）を表現することができる。その上、本発明は、（指紋）画像データの多角形（特に三角形）のマシン表現を作成するための方法を提供する。これらの表現はプリント間で特定の量の指紋画像ノイズおよび指紋画像ひずみに関して変化せず、有限の可算数の三角形／多角形が存在する。ポイント特徴に関連する幾何学的情報（たとえば、三角形の辺）に加えて、従来技術では、画像ポイント特徴の直近の空間的近傍にある画像情報（たとえば、細かい点に近い隆起の方向）またはポイント特徴同士を結合する線の近傍にある狭い線形ストリップの画像内の画像情報（たとえば、細かい点間の隆起カウント、長さ）を使用する。これらのタイプの情報は本明細書ではひとまとめにして幾何学的特徴と呼ばれる。三角形／多角形に関する変化しない幾何学的情報が使用されるだけでなく、新規な一態様として、三角形／多角形自体に近い（好ましくはその内部の）画像領域から得られる測光データの変化しない特徴も使用される。すなわち、幾何学的データと指紋画像（たとえば、測光）データの両方が使用されるという点で指紋表現はハイブリッドである。本明細書に記載されている「測光」データは、深さ、反射率、誘電特性、ソナー特性、湿度測定値、磁性などを含むが、これらに限定されない感知画像測定値を含むことに留意されたい。さらに、本明細書で言及されている測光データは、画像ポイント特徴を構成する多角形（たとえば、三角形）に関連する領域に対応する画像情報を指すことに留意されたい。
【００６２】
図２８は、１つまたは複数の画像特徴を単一表現、たとえば、１つの数値またはより一般的には複数数値のベクトルに変換するステップを示す、好ましいコード化プロセス１０００の流れ図である。画像特徴は、好ましくは３つの細かい点に基づいて列挙することができ、数値／ベクトルは制限され、したがって、量子化により、可能な三角形のすべてを列挙することができる。コード化プロセス１０００は、図９のように３つの細かい点の組み合わせからなる指紋領域を包囲する三角画像から入力特徴情報を取り、三角形（多角形）の列挙を構築する。
【００６３】
ステップ１００４は、（この実施形態における）細かい点のトリプレットの幾何学的特徴を入力する。すなわち、トリプレットは、指紋画像から計算された細かい点のセットから選択された３つの細かい点の組み合わせである。この実施形態では、これらの特徴は、図１１に図示されているものなど、多角形／三角形の内部およびそれを包囲する幾何学的隆起構造に関連付けられている。これらの特徴は、上記で参照した米国特許第６０７２８９５号および第６２６６４３３号に概説されている通り、角度、長さ、隆起カウントを含む。特徴はベクトルＸ1＝（Ｓ1，Ｓ2，Ｓ3，ｈ1，ｈ2，ｈ3，ＲＣ1，ＲＣ2，ＲＣ3）で表現され、図１１のように、Ｓは距離を表し、ｈは角度を表す。ＲＣ1、ＲＣ2、ＲＣ3は、それぞれ長さＳ1、Ｓ2、Ｓ3の辺を横切る隆起の数である（図１１を参照）。この例では、辺「Ｓ1、Ｓ2、Ｓ3」および角度「ｈ1、ｈ2、ｈ3」は変化しない幾何学的細かい点のデータである。隆起カウント「ＲＣ1、ＲＣ2、ＲＣ3」は、幾何学的エンティティ、たとえば、三角形の一辺に関連する非常に狭いストリップの画像内で抽出され、実質的な画像領域に関連付けられていないので、やはり（本発明のための）変化しない幾何学的データである。
【００６４】
幾何学的形状の偏心、幾何学的形状のオイラー数、幾何学的形状のコンパクトさ、幾何学的形状の傾斜密度関数、幾何学的形状のシグネチャ、幾何学的形状の構造的特徴記述、幾何学的形状の凹部、幾何学的形状を囲む凸形状、幾何学的形状を記述する形状番号を含むが、これらに限定されない、幾何学的形状から計算された任意の他の幾何学的特徴も本発明に関して使用できることが分かるであろう。これらの形状幾何学的特徴の計算については、ニュージャージー州のＰｒｅｎｔｉｃｅ  Ｈａｌｌから発行されたＢａｌｌａｒｄ他による「Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ」の２５４〜２５９ページに教示されている。
【００６５】
ステップ１００４は、画像または２空間（two-space）内の三角形の回転および変換（すなわち、剛性変換（rigid transformation））に関して変化しない、三角形の幾何学的特徴をさらに選択する。加えて、非常に独特の変化しない指紋特徴（ＲＣ1、ＲＣ2、ＲＣ3）が含まれる。代わって、ステップ１００４は、２空間内の三角形の回転、変換、およびスケーリング（すなわち、相似変換）に関して変化しない、三角形の幾何学的特徴を選択する。
【００６６】
任意選択ステップ１００８は、指紋グレースケール画像領域から計算された変化しない測光特徴を入力する。これらの特徴は、ある領域内、好ましくは、図１１のものなどの多角形／三角形内、より好ましくは、三角形に外接している円形画像（たとえば、図１３の７２６）内の三角形／多角形の周りの指紋画像プロファイルに関連付けられている。図１３は、本発明の好ましい一実施形態により、測光不変量の抽出を例示する図である。図１３については本明細書で以下により詳細に説明する。本発明が測光特徴を抽出するための領域を選択する前述の手法（たとえば、図１３の円形画像領域７２６）に限定されず、したがって、本発明により他の手法も使用可能であることが分かるであろう。たとえば、測光特徴を抽出するために三角形（多角形）領域そのものを選択することができる。領域Ａの包囲演算子（surround operator）は、領域Ｂ内の任意のポイントがＡの周囲上の最も近いポイントから特定の最大距離ｔの範囲内にあるような、より大きい領域Ｂを定義する。図１３に図示されている三角形７２５または円７２６のいずれかを包囲する領域を選択することが可能である。同様に、領域Ａの収縮演算子（shrink operator）は、領域Ｂ内の任意のポイントがＡの周囲上の最も近いポイントから特定の最大距離ｔの範囲内にあるような、より小さい領域Ｂを定義する。三角形７２５または円７２６のいずれかを収縮する領域を選択することが可能である。測光特徴抽出のために円７２６または三角形７２５の１つまたは複数の小領域を選択することが可能である。選択された画像領域からいくつかの測光特徴を計算することができる。
【００６７】
例示として、測光特徴は、輝度、ピクセル輝度、法線ベクトル、カラー、輝度変動、隆起の向き、画像データの変動、画像の少なくとも１つの領域の統計値、画像の少なくとも１つの領域の変換、画像の少なくとも１つの小領域の変換、画像の２つまたはそれ以上の小領域の統計値または変換の統計値を含むことができるが、これらに限定されない。統計値は、平均、分散、ヒストグラム、モーメント、コレログラム、およびピクセル値密度関数を含むことができるが、これらに限定されない。また、測光特徴は、画像領域のガボール変換、フーリエ変換、離散的コサイン変換、アダマール変換、ウェーブレット変換などの画像領域の変換特徴も含む。さらに、所与の画像領域が２つまたはそれ以上の画像小領域に区分される場合、このような各領域の平均または分散は測光特徴を構成することができる。所与の画像領域を２つまたはそれ以上の小領域に区分することにより、２つ以上の測光特徴が計算される場合、このような測光特徴の統計値も測光特徴である。同様に、所与の画像領域を２つまたはそれ以上の小領域に区分することにより、２つ以上の測光特徴が計算される場合、このような測光特徴の空間的勾配も測光特徴である。種々の測光特徴を計算する方法、１つの領域を複数の小領域に分解する方法、画像領域の統計値および変換を計算する方法、ならびにすでに計算された測光特徴からより多くの画像測光特徴を結合し構成する方法は当業者にとって周知のものであり、このような方法は本発明の範囲内に包含される予定である。画像検索および画像特徴に関する文献、すなわち、１９９９年４月発行のＪｏｕｒｎａｌ  ｏｆ  Ｖｉｓｕａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ａｎｄ  Ｉｍａｇｅ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ、第１０巻、第４号、３９〜６２ページに掲載されたＲｕｉ他による「Ｉｍａｇｅ  Ｒｅｔｒｉｅｖａｌ：  Ｃｕｒｒｅｎｔ  Ｔｅｃｈｎｉｑｕｅｓ，  Ｐｒｏｍｉｓｉｎｇ  Ｄｉｒｅｃｔｉｏｎｓ  Ａｎｄ  Ｏｐｅｎ  Ｉｓｓｕｅｓ」に記載されている。
【００６８】
測光特徴の例としては、好ましくは、図１３に図示されている円形画像領域７２６の平均、分散、勾配、平均勾配、分散勾配などの統計値を含むが、これらに限定されない。また、これらの特徴は、画像データのベクトルを変換することにより三角画像データを基底関数に分解することも含むが、これらに限定されない。このような分解は、カルーネン・レーベ変換、およびフーリエ変換、ウォルシュ・アダマール変換などのその他の相関解除（decorrelating）変換を含むが、これらに限定されない。このような変換の出力は、変化しない測光統計値のベクトルＸ2＝（ａ1，ａ2，ａ3，・・・）である。このため、任意選択ステップ１００８は、変化しない測光特徴、すなわち、図１２にさらに記載されている三角形に関連する指紋画像プロファイルＩ（ｘ，ｙ）の変化しない特徴を選択する。図１２は、本発明の他の実施形態により、測光不変量の抽出を例示する図である。図１２については本明細書で以下により詳細に説明する。本発明は、可視パターン／オブジェクトの信頼できる索引付けおよび正確な照合のための測光特徴を抽出するためのプロセスを使用する。
【００６９】
測光特徴は、特徴選択を使用して抽出され選択される。たとえば、特徴選択については、２０００年にＷｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅから発行されたＤｕｄａ他によるＰａｔｔｅｒｎ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ（第２版）に記載されている。
【００７０】
たとえば、代表的な指紋画像データ・セット（トレーニング・データとも呼ばれる）から抽出された多数の既知の測光特徴とこれらの特徴のうちの１つまたは複数が選択される。つまり、既知のグラウンド・トルース（すなわち、どの複数対の指紋が一致しなければならないかは演繹的に把握される）によりトレーニング・データについて最良一致のパフォーマンスが得られる。
【００７１】
ステップ１０１２は、ステップ１００４および１００８からの特徴をコード化／変換する。本明細書では、ステップ１０１２を実行するための２通りの模範的な手法について説明する。しかし、本発明により他の手法も使用できることが分かるであろう。
【００７２】
第１の手法では、ベクトルＸ1およびＸ2が連結されて、Ｘ＝（Ｓ1，Ｓ2，Ｓ3，ｈ1，ｈ2，ｈ3，ＲＣ1，ＲＣ2，ＲＣ3，ａ1，ａ2，ａ3，・・・）になり、ベクトルＹは
Ｙ＝ＫＸ
のように構築され、Ｙ＝（ｙ1，ｙ2，ｙ3，・・・）である。Ｋの説明については以下を参照されたい。
【００７３】
第２の手法では、２つの個別のベクトルＹ1およびＹ2は
Ｙ1＝Ｋ1Ｘ1およびＹ2＝Ｋ2Ｘ2
のように構築され、好ましくは、Ｋ2＝Ｉ（ＩＤ行列）およびＹ2＝Ｘ2である。
【００７４】
ステップ１０１２は、好ましくは、第１の手法を使用して達成される。好ましい一実施形態では、変換Ｋは、新規なやり方で三角形／多角形の幾何学的不変量と測光不変量を結合する。ＫＬＴ変換Ｋの方法は、当業者にとって既知のものであり、たとえば、以下のパターン認識文献、すなわち、２０００年にＷｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅから発行されたＤｕｄａ他によるＰａｔｔｅｒｎ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ（第２版）に記載されている。
【００７５】
ＫＬＴ変換は、指紋のトレーニング・データおよびその特徴（上述のＸ）を使用し、Ｘを直交ベクトルＹのセットに変換し、その結果、相関関係のない成分ｙ1、ｙ2、ｙ3が得られる変換Ｋをシミュレートする。これらの成分ｙ1、ｙ2、ｙ3、・・・も、三角形の回転、変換、（およびスケーリング）に対して変化しない。トレーニング・データＹの要素ｙ1、ｙ2、ｙ3、・・・は相関関係なしであり、トレーニング・データがユーザ母集団（user population）を適切に記述（予測）する場合、確率変数（random variable）ｙ1、ｙ2、ｙ3、・・・は相関関係なしになる。
【００７６】
引き続き、このベクトルＸについて説明する。指紋画像データのうちの所与の三角形／多角形領域の場合、ベクトルＸは、三角形／円の内部（収縮）またはそれを包囲する領域から抽出可能なすべての変化しない（指）特性を表現する。物理的な意味では、不変性とは、ある画像、好ましくは指紋の特性であり、またはより好ましくは個々の指の特性であり、紙の痕跡、ライブスキャンなどからスキャンされたときに、痕跡間で変化せずに存続する特性を意味する。特異な画像処理プロセスであるので、これらの不変量は粗く量子化しなければならない可能性があることに留意されたい。「三角形が左上の四分円内に存在する」ことなどの緩く変化しない特性は、２進の確率変数であり、ベクトルＸの成分として含めることができる。数学的には、これは、これらの特性が剛性変換または相似変換に関して変化しないことを意味する。
【００７７】
図１４および図１５に記載されている通り、ステップ１０１２を実現する好ましい一方法は、トレーニング・データの共分散行列（covariance matrix）の固有ベクトル（eigenvector）によってスキャンされた新しい座標系にベクトルＸをマッピングすることである。行列Ｋは、トレーニング画像（トレーニング三角形のセットを示すもの）の共分散行列ＣXを推定し、固有ベクトルｖ1、ｖ2、ｖ3、・・・、ｖnを決定することによって得られ、ｎはＸの成分の数である。物理的には、これは、新しいＹ座標系が空間Ｘ内に描かれることを意味する。変化しない特徴Ｘは本質的に７３８のようにこの空間内に分散させることができるが、Ｙ空間では、ｙ1に対応する第１の軸が最高分散の方向に沿って指し示し、ｙ2はｙ1に対して垂直であって（７３９として）第２の最高分散の方向にあり、ｙ3は第３の最高分散の方向にあってｙ1およびｙ2に垂直である。この場合も、このプロセスについては図１４および図１５に記載されている。
【００７８】
ユーザ母集団で検出された三角形のタイプを代表する指紋トレーニング・データ三角形からＫが推定された場合、成分Ｙ＝（ｙ1，ｙ2，ｙ3，・・・，ｙn）は独立している（または少なくとも相関関係なしである）。その上、確率変数のセットとしてベクトルＸ内に存在するエネルギまたは分散は、ベクトルＹの下位成分に集中している。任意選択ステップ１０１６は、第１のｍ≦ｎの成分Ｙ′＝（ｙ1，ｙ2，ｙ3，・・・，ｙm）を選択するだけで、これを利用する。このベクトルＹ′またはこのセットの数値は、図１４および図１５にさらに描かれている通り、３つ（またはそれ以上の）細かい点の組み合わせによって形成された三角形内およびその周りの指紋画像データの固有の表現である。ｙ成分は最大分散から最小分散に順序付けられ、最高分散を有する成分のみが選択される。
【００７９】
上記の通り、図１２には、変化しない測光特徴を抽出する新規な好ましい一方法が記載されている。元のｘｙ指紋画像座標系内のある三角形７２９を考慮すると、第１のステップは、７３０で三角形７２９をｘ′ｙ′画像座標系内の正準位置（canonical position）７３１に変換することである。このような変換を決定できる多くの既知の方法が存在する。必要なことは、任意の位置の三角形７２９が必ず７３１としての三角形に変換されること（不変性）である。後者の向きは三角形７２９の元の向きとは無関係である。頑強に抽出可能な三角形の変化しない特徴を選択し、この特徴を正準位置に回転および変換（ならびにスケーリング）することは、好ましい方法である。
【００８０】
本発明の原理により、三角形から変化しない画像特徴を抽出するための好ましい一方法が図１２の最下部に図示されている。三角形７２５の場合、その意図は、指紋画像の（円形）領域７２６内のＩ（ｘ，ｙ）から変化しない特徴（幾何学的および測光）を抽出することである。円の中心７２７は、三角形を形成する３つの細かい点の重心である。三角形が使用される好ましい実施形態では、三角形の３つの頂点の位置によって円を定義することができる。画像関数Ｉ（ｘ，ｙ）は、円によって定義されたｒ（半径座標）およびｈ（角度座標７２８）を有するＩ（ｒ，ｈ）として記述することができる。特定の半径Ｉ（ｒ，ｈ）の円形画像の場合、円形「固有画像（eigen-image）」のセットは、ＫＬＴにより決定することができる。これらは、ある領域、たとえば、円内の測光特徴（好ましい一実施形態では、指紋画像内で検出された画像輝度パターン）を最も良く記述する基本的ビルディング・ブロックを形成する円形基底画像関数ｅ1、ｅ2、ｅ3、・・・のセットである。画像は、何らかのポイントｍで切り捨てられるＩ（ｒ，ｈ）＝ａ1ｅ1＋ａ2ｅ2＋ａ3ｅ3＋・・・である。ａ1、ａ2、ａ3は、（回転および変換に対して）変化しない方法で円形画像内の隆起「テクスチャ」を表す円形画像の新規な不変記述子である。
【００８１】
図１４には、このコード化方式をトレーニングする好ましい一方法、すなわち、カルーネン・レーベ変換（ＫＬＴ）が記載されている。すなわち、図１４には、行列Ｋの入手に係わるものが記載されている。ＫＬＴによって規定されている通り、トレーニング・セットが必要であり、入力ベクトルのセットは｛Ｘ1，Ｘ2，Ｘ3，・・・，Ｘt｝であり、それぞれのＸiは（好ましくは３つの）細かい点の組み合わせによって決定された指紋画像データの三角形領域のトレーニング三角形のｎ通りの不変性（幾何学的不変性または測光不変性あるいはその両方）を表す。このため、このセットの入力ベクトル７３０から、ベクトル平均を決定し（ステップ７３２）、共分散行列ＣXを決定する（ステップ７３４）ことにより、共分散行列が決定される。ステップ７３６で決定されたＣXの固有ベクトルｖ1、ｖ2、ｖ3、・・・、ｖnは変換行列Ｋを示す。ＣXの固有値ｋ1、ｋ2、ｋ3、・・・、ｋnはそれぞれ成分ｙ1、ｙ2、ｙ3、・・・、ｙnの分散を示し、固有値はステップ７３６の切り捨てｍを案内することができる。
【００８２】
図１５は単に、ベクトルのセット｛Ｘ1，Ｘ2，Ｘ3，・・・，Ｘt｝７３８についてトレーニングされたときにＫＬＴが実行すると思われるものの一例を示している。この場合、Ｘベクトルは、２空間内で視覚化できるように２次元（ｘ1，ｘ2）であり、これは、ｔ個のトレーニング三角形のそれぞれから２つの不変量ｘ1およびｘ2のみ、すなわち、三角形の辺、角度、変化しない測光特性などが抽出されることを意味する。Ｘiの共分散行列は、セット７３８から分かるように固有ベクトルｖ1、ｖ2を有する。次に、図１４のステップ７３６のように、２つの固有ベクトルを変換行列Ｋの行として書き込むことにより、行列Ｋが構築される。セット７３８を変換すると、その結果、７３９というセット｛Ｙ1，Ｙ2，Ｙ3，・・・，Ｙt｝が得られる。Ｙの成分ｙ1およびｙ2は相関関係なしであり、さらに、ｘ軸に沿ったセット７３９の分散はｋ1になり、ｙ軸に沿った分散はｋ2になり、ｋ1およびｋ2は共分散行列の固有値を表す。
【００８３】
最後のステップとして、ステップ１０２０でＹ′の要素の量子化および列挙が行われるか、または１０２４で三角形の順序付けおよび量子化が行われる。図１６〜図１８は図２８のステップ１０２０をさらに例示し、図１９および図２０は図２８のステップ１０２４をさらに例示している。図１５には図２８のステップ１０２０（「量子化および列挙」）が詳細に記載されている。変換された成分のそれぞれＹi＝（ｙi1，ｙi2，ｙi3，・・・，ｙim）Tは指紋画像データの三角形に関連する確率変数である。これらの成分は独立してコード化され、ベクトルは以下のように得られる。
Ｙi＝（ｙi1，ｙi2，ｙi3，・・・，ｙim）T
ｍ個の成分のそれぞれは、何らかのプロセスＹ→Ｙにより独立して量子化される。まず、図１６および図１７では、Ｙの１つの成分ｙiだけが調べられ、各成分のそれぞれについて図１４からのｔ個のトレーニング・サンプル｛Ｘ1，Ｘ2，Ｘ3，・・・，Ｘt｝を有する。それぞれの成分の経験的分布（empirical distribution）を入手することができ、ｔ個のサンプルから、それに応じて各成分の量子化戦略を設計することができる。１つの成分、たとえば、Ｙ＝（ｙi）T＝ｙiに集中すると、図１６および図１７には、それぞれ、（ｉ）ｙiの分布が一様分布である（図１６の７４０〜７４４）ケースと、（ｉｉ）ｙiの分布がガウス分布である（図１７の７４６〜７５０）ケースという２通りのケースが記載されている。この量子化は、一様分布およびガウス分布について本明細書で以下に詳細に記載するトレーニング・データの経験的分布に基づく新規なものである。
【００８４】
図１６は、７４０のｙiの一様分布を例示している。この成分をサンプリングする際の精度は、各成分の分布に大きく依存する。７４０のケースでは、ｙiのダイナミック・レンジは小さい［−１／２，１／２］。変換７４２によるように２ビットに量子化することにより、結果として得られる離散確率変数ｙiは値｛０，１，２，３｝を取る。より精密には、コード化７４２では以下のように規定する。
ｙiが［−１／２，−１／４］内であれば、ｙi＝０
ｙiが［−１／４，０］内であれば、ｙi＝１
ｙiが［０，１／４］内であれば、ｙi＝２
ｙiが［−１／４，１／２］内であれば、ｙi＝３
それぞれの値｛０，１，２，３｝に関する事前確率は１／４に等しい（７４４）。
【００８５】
図１７は、７４６のｙiのガウス分布を例示している。この場合も、この成分をサンプリングする際の精度は、このケースではガウス分布である、この成分の分布に大きく依存する。ｙiのダイナミック・レンジおよび分散は、この場合も７４０と同じ範囲内にあり、小さい［−１／２，１／２］。変換７４８によるように２ビットに量子化することにより、結果として得られる離散確率変数ｙiは値｛０，１，２，３｝を取る。ｙi軸を４つの間隔に分割することにより、マッピングが構築される。これは、これらの間隔のそれぞれについてガウス曲線７４６に基づく積分の１／４にすることにより達成される。事前確率は、ｙi（７５０）のそれぞれの値について１／４に等しい。要するに、これにより、幾何学的不変情報と測光不変情報を新規なやり方で結合することが可能になり、トレーニング・データに基づくコード化行列の系統的構築が可能になり、離散確率変数のｙi1，ｙi2，ｙi3，・・・，ｙimというシーケンスとして、三角形内の不変情報が記述され、Ｙの成分は分散に応じて高から低へ順序付けられる。
【００８６】
図１８の座標系７５４は、１つの成分ｙiから３次元のベクトルＹ＝（ｙ1，ｙ2，ｙ3）Tへの拡張を示し、サンプルはＹi＝（ｙi1，ｙi2，ｙi3）Tであり、ｉ＝１，・・・，ｔである。（図１５を参照されたい。）３つの成分のそれぞれについて、Ｙ空間内に組み込まれた座標系７５４の量子化された軸によって図示されている通り、ｉ＝１，・・・，ｔである個々のサンプルｙi1、ｙi2、ｙi3の経験的分布から種々の量子化方式を得ることができる。第１の成分ｙ1は精細にサンプリングされ、第２の成分ｙ2はより粗くサンプリングされ、第３の成分ｙ3はさらに粗くサンプリングされる。ｙ1、ｙ2、ｙ3がいずれも有限かつ限定されている場合、ベクトルＹはアレイＡ（ｙ1，ｙ2，ｙ3）の限定された領域内で量子化され、すなわち、マッピング７５２は、
Ｙ＝（ｙ1，ｙ2，ｙ3）T→Ｙ＝（ｙ1，ｙ2，ｙ3）T
であり、有限数の値のみを取る。経験的分布推定の推定値が正確であり、（ｙ1，ｙ2，ｙ3）空間をサンプリングすることによって得られるＮ通りの三角形が存在する場合、事前確率は１／Ｎに等しくなる。
【００８７】
一般に、ｍ次元のＹ＝（ｙ1，ｙ2，・・・，ｙm）Tというより低次元のＹ空間にＸをマッピングする場合（ｍは任意選択でｎより小さく、Ｘの成分が独立している場合はｍ＝ｎ）、マッピングは上記の通り構築され、種々の成分をＮ1、Ｎ2、・・・、Ｎmレベルで量子化することができる。次に、種々の三角形のそれぞれに関する事前確率は以下の通りである。
１／（Ｎ1，Ｎ2，・・・，Ｎm）＝１／Ｎ
【００８８】
このように成分値を列挙することができ、したがって、指紋画像内で区別可能な三角形／多角形の数はトレーニング・データのセットから決定することができる。このため、固有の三角形／多角形のセットとして指紋を記述するマシン表現を構築することができる。
【００８９】
次に、好ましい一実施形態では、ベクトルＹによって三角形を表現するのではなく、単一のスカラ数によって三角形を表現し、それにより、図２８のステップ１０２４の順序付け、量子化、および列挙を可能にする。図１５に注意を向けると、７３８のポイント｛Ｘ1，Ｘ2，・・・，Ｘt｝と、このため、７３９のポイント｛Ｙ1，Ｙ2，・・・，Ｙt｝は、他の方法で順序付けまたはソートすることができる。すなわち、ポイントＸを共分散行列ＣXの第１の固有ベクトルｖ1に投影することにより、スカラ値ｙ＝ｙ1＝Ｘ・ｖ1（Ｘとｖ1の内積）は、三角形の特定の不変量Ｘに一意的に関連付けられてる数値を示す。
【００９０】
これに関する物理的記述は図１５の右側に示されている。要素Ｘは最大分散の方向に沿ってクラスタと交差する線上に投影される。図１５では、個々のサンプルは、｛Ｙ1，Ｙ2，・・・，Ｙt｝の重心とＣXの第１の固有ベクトルであるベクトルｖ1が及ぶ線上に投影される。図１５で得られる順序付けは、値ｙ1によって決定され、（Ｙ3，Ｙ2，・・・，Ｙt，・・・，Ｙ1）になる。
【００９１】
図１９および図２０には、この多対１のマッピングがより詳細に記載されている。Ｙの第１の成分であるｙ＝ｙ1を設定することにより、７６０の投影矢印によって示される通り、各三角形はｖ1が及ぶ軸上に投影される。データ・セット｛Ｘ1，Ｘ2，Ｘ3，・・・，Ｘt｝によってこのようなマッピングをトレーニングすると、この場合も確率変数ｙの経験的分布を確立することができる。これにより、「小」から「大」の範囲にわたるいくつかのｙ値（７７５）が得られる。次に、このｙ値は、ｙのｔ個の推定値の経験的分布を使用して、構造７７０によって量子化することができる。これは、それぞれの間隔について経験的分布に基づく領域が１／Ｎになるように、ｙの範囲をＮ個の間隔に分割することにより、達成される。次に、その結果は、ｋ、ｋ＝１、・・・、Ｎというラベルが付けられた有限数の三角形への新規な直接マッピングの量子化ｙになり（すなわち、７８０としてのｙ（１）・・・ｙ（Ｎ））、Ｎは別個の三角形または量子化レベルの数を表す。７８０では、ｙは値｛０，１，２，・・・，１１｝を取ることができる。
【００９２】
これは、統計的ＫＬＴによって規定されている通り、ｎ次元の空間から１次元の空間へのマッピングである。Ｙ＝（ｙ1，ｙ2，ｙ3，・・・，ｙm）Tというコンポーネントからスカラ値への（量子化後の）このようなマッピングが構想される他の方法が存在し、これは本発明により使用することができる。
【００９３】
この場合、好ましい一方法は、ｙ1、ｙ2、ｙ3、・・・、ｙmのビットを再配置することによりスカラ値を構築することである。新しいビット・ストリングｙは以下のように構築することができる。すなわち、
ｙ＝１（ｙ1）１（ｙ2）・・・１（ｙm）２（ｙ1）２（ｙ2）・・・２（ｙm-1）・・・ｍ（ｙ1）・・・
であり、関数１（ｙ）２（ｙ）・・・ｍ（ｙ）は量子化された数ｙの１番目、２番目、・・・、ｍ番目のビットである。この場合も、これにより、Ｙから離散数｛０，１，２，・・・，Ｎ｝への多対１のマッピングが形成される。ｍ個のビットを単一の数値にマッピングするための他の方法は本発明の範囲内である。
【００９４】
それぞれの個々の指紋は実世界の三角形／多角形のセットであり、指紋表現は三角形のセットである。指紋のマシン表現は可能なＮ個の三角形のサブセット｛ｔj｝である。当然のことながら、このマシン表現は三角形と同じように良好であり、その不変性を抽出することができる。このマシン表現は、追加の指紋（このため、三角形）を追加することによって洗練することができる。しかし、任意の確率測定システムのように、擬似三角形、欠落三角形、ゆがみすぎの三角形が存在することになり、したがって、三角形の統計的不変量が不完全に推定されることになる。エンコード方式が未知である場合に種々の三角形がどのようになるかは未知であるので、三角形による指紋の表現は特定の量のプライバシを提供する。しかし、頂点、すなわち、細かい点を一致させることによってできるだけ多くがまとまるようにコンピュータ処理により三角形をレイアウトすることにより、何らかの当業者がこのようなマシン指紋表現内のエンコード方式を入手する場合、指紋をデコードすることができる。指紋をさらにコード化または暗号化するために、登録中に三角形を変換することができる。これにより、元の指紋のデコードをコンピュータ処理上不可能なものにする。
【００９５】
図２９は、三角形／多角形に関連する１つまたは複数の画像特徴を、数値の有限セットからの１つの固有の数またはベクトルの有限セットからの１つの固有のベクトルにコード化する諸ステップを示す、好ましい変換および暗号化プロセスの流れ図である。このプロセスは、それにより、そこから指紋画像を構築できる三角形を列挙可能なものにする。しかし、この場合、図１５〜図１８のようなベクトルにまたは図１９および図２０のようなスカラに三角形をコード化する前に、局所的画像変換８０２により画像データが変換される。
【００９６】
図２９を参照すると、コード化プロセスの第１のステップ８０２は、指紋画像データのそれぞれの三角形を画像データの他の三角形に変換する。このため、ステップ８０４への入力は、細かい点のトリプレットの周りの領域から抽出され、変換された変化しない幾何学的特徴および測光特徴である。この場合、トリプレットは、指紋画像から計算された細かい点のセットから選択された３つの細かい点の組み合わせである。これらの特徴は、三角形そのものと、図１１のものなどの多角形／三角形の内部およびそれを包囲する幾何学的隆起構造とに関連付けられている。これらの関連付けを使用して、変換された三角形の不変性と変換された三角形を包囲する隆起構造の不変性が抽出される。これらの特徴は、たとえば、上記で参照した米国特許、すなわち、米国特許第６０７２８９５号および第６２６６４３３号に概説されている通り、角度、距離、隆起カウントを含み、一般に、
Ｘ＝（Ｓ1，Ｓ2，Ｓ3，ｈ1，ｈ2，ｈ3，ＲＣ1，ＲＣ2，ＲＣ3，ａ1，ａ2，ａ3，・・・）
というベクトルになり、Ｓ1、Ｓ2、Ｓ3は剛体幾何学的不変量（長さ）を表し、ｈ1、ｈ2、ｈ3は変化しない角度を表し、ＲＣ1、ＲＣ2、ＲＣ3は隆起カウントを表し、ａ1、ａ2、ａ3は測光不変量を表す。
【００９７】
測光不変量の抽出を伴うステップ８０８は任意選択ステップである。プロセス８０８への入力は、変換された三角画像領域と、画像データの周囲である。画像データは、幾何学的データと同じ規定のコード化によって変換される。変化しない測光特徴は、たとえば、円、多角形／三角形の内部およびそれを包囲する変換された指紋グレースケール画像データに関連付けられている。これらの特徴は、平均、分散、勾配、平均勾配、分散勾配などの統計値を含む。また、これらの特徴は、画像品質の統計的推定値も含む。これらの特徴は、三角形内の画像データのベクトルを変換することにより、変換された三角画像データを基底関数に分解すること、それにより、少数の不変性ａ1，ａ2，ａ3によりトリプレットを包囲する指紋の測光プロファイルを記述することをさらに含む。このような分解は、カルーネン・レーベ変換、ならびにフーリエ変換、ウォルシュ・アダマール変換などのその他の相関解除変換を含む。このようなコード化の出力は、ベクトルＸ2＝（ａ1，ａ2，ａ3，・・・）であるが、この場合の測光不変性は変換された三角形から抽出される。
【００９８】
次に、図２９の流れ図では、ステップ８１０が実行される。ステップ８１０は、図２８のステップ１０１２、１０１６、１０２０、および１０２４を実行する。相違点は、ステップ８１０がステップ８０４および８０８からその入力を、すなわち、変換された三角形の幾何学的／測光特性を取ることである。
【００９９】
図２１には、三角形の幾何学的不変量に対する操作による線形または非線形変換が記載されている。図２１は、１つの指紋画像データの幾何学的および測光特性の局所的変換の一例を示している。図２１は図２９の８０２を実行する模範的な一方法、すなわち、局所的画像特徴の変換を表していることが分かるであろう。マッピング８１７は、入力として指紋データの三角形８１５を取り、線形関数により三角形を変換する。この変換は以下のように記述できるであろう。
「三角形の最も大きい辺を２０％減少する」
または
「最も小さい角度に係数１．５を掛ける」
【０１００】
図２１の場合、具体的には、三角形８１５の最も小さい角度、すなわち、角度８１６を５０％増加し、その結果、角度８１８を有する三角形８１９にすることにより、三角形８１５は８１７で三角形８１９にマッピングされる。これらの変換は、たとえば、以下のように非線形のものにすることができる。
「最も大きい辺の長さｅ1をｅ1の平方根に減少する」
または
「最も小さい角度を取り、それを２乗する」
【０１０１】
いずれの場合も、これは、三角形８１５内の画像データを三角形８１９にマッピングし、データをサンプリングし直すことによって達成される。入力三角形が小さい場合、マッピングが不正確になることは直ちに明らかである。マッピング８１７は、固有の１対１のマッピングとして定義する必要がある。
【０１０２】
図２２には、三角形に対する一連の操作による線形または非線形変換が記載されている。この場合も、三角形８１５が変換への入力である。第１のステップ８２１として、三角形はユークリッド変換により正準位置に配置される。
【０１０３】
この場合、一例として、最も大きい辺がｘ軸と位置合わせされ、ｙ軸は中央で最も大きい辺と交差する。一般に、不変量の１つが推定され、その不変量が正準位置に配置されるように三角形が変換される。
【０１０４】
変換８２１は、ｘｙ座標系８２４に位置決めされた画像データ８２３を提供する。この場合も、変換８２５は以下のように線形にすることができる。
（ｘ′，ｙ′）T＝Ｄｉａｇ（０．８  １）（ｘ  ｙ）T
すなわち、アフィン変換として定義することができる。この場合、ｘ′＝０．８・ｘ；ｙ′＝ｙであるが、一般にこの行列は対角行列である必要はない。この変換は、たとえば、以下のように非線形にすることができる。
ｘ′＝ｓｑｒｔ（ｘ）；  ｙ′＝ｙ
【０１０５】
代わって、これは、三角形８１５を極座標系の何らかの正準位置にマッピングし、続いて、ｒが半径座標であり、ｈが角度座標（極角と呼ばれる場合が多い）である極座標（ｒ，ｈ）のアフィン変換を行うことによって達成することもできる。正準位置は、最も大きい辺とｒ軸との位置合せにすることができるであろう。本質的に、三角形の幾何学的制約または不変量のいずれかを使用して、三角形を正準位置に変換することができる。
【０１０６】
上述の方法は、三角形の変換、本質的に、個々の画像データに対して特定のひずみをもたらすことに依存する。２０００年６月１６日に出願され、「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｄｉｓｔｏｒｔｉｎｇ  ａ  Ｂｉｏｍｅｔｒｉｃ  ｆｏｒ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｗｉｔｈ  Ｅｎｈａｎｃｅｄ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ」という発明の名称の米国特許出願第０９／５９５９３５号では、これらは信号変換と呼ばれている。指紋の三角表現を扱う場合、テンプレート変換と呼ばれる、三角形を変換することによりＩＤを曖昧にするためのより好ましい方法については、図２３および図２４で論じられている。
【０１０７】
図２３には、数値ｙ1、ｙ2、ｙ3、・・・、ｙmという固有のセットによって記述された三角形を固有の量子化された数値ｚ1、ｚ2、ｚ3、・・・、ｚmという異なるセットにマッピングするプロセスが記載されている。入力は、その包囲画像データ８３１を有する指紋画像三角形８３０である。上述の方法を使用して、（図２８のステップ１００４のように）８３０の幾何学的データと８３１の測光データ（図２８のステップ１００８）から、この場合もベクトル（ｙ1，ｙ2，・・・，ｙn）Tが構築され、その成分は（図２８のステップ１０２０のように）相関関係なしである。次に、８３４でベクトル（ｙ1，ｙ2，・・・，ｙn）Tが量子化され、好ましくは図１８に記載されているようにｍ個の成分からなるベクトル（ｙ1，ｙ2，・・・，ｙm）Tに切り捨てられる。この場合、この変換は量子化／切り捨て操作Ｙ＝ＱＹによって示される。このベクトル８３６の各インスタンスＹ＝（ｙ1，ｙ2，・・・，ｙm）Tは、量子化された有限数の可能な三角形の１つである。本質的に、ステップ８３７の任意の変換Ｔは以下の通りである。
（ｚ1，ｚ2，・・・，ｚm）T＝Ｚ＝ＴＹ＝（ｙ1，ｙ2，・・・，ｙm）T
これは、１対１で、固有の三角形ＹをＺ＝（ｚ1，ｚ2，・・・，ｚm）Tによって記述される三角形８３９にマッピングする。好ましくは、この１対１のマッピングは、変換が固有の１対１の逆変換を持たないように非線形である。
【０１０８】
図２４には、数値ｙ1、ｙ2、ｙ3、・・・、ｙmという固有のセットによって記述され変換された三角形８４０を固有の単一の数値ｙ８４２にマッピングするプロセスが記載されている。この数値８４２は、その後、ステップ８４４の変換Ｑにより量子化され、すなわち、ｙ＝Ｑｙになり、三角形８４０に関連する単一の固有の数値８４６になる。これは、図２０に記載されている方法により達成される。次に、本質的に、ステップ８４７の任意の変換Ｔは以下の通りである。
ｚ＝Ｔｙ
これは、Ｎ個の数値のセットからＮ個の数値の他のセットへの１対１のマッピングである。これは、固有の三角形ｙをｚによって記述される三角形８４９にマッピングする。好ましくは、この１対１のマッピングは、変換が固有の１対１の逆変換を持たないように非線形である。
【０１０９】
代わって、図２５で説明されている通り、変数ｙがまず変換され、次に量子化されることは本発明の範囲内である。すなわち、以下の通りである。
ｚ＝Ｔｙ  続いて  ｚ＝Ｑｚ
【０１１０】
これは、本質的に、三角形のランク、番号、順序を付け直し、それにより、指紋表現の表現を私有化することに相当する。
【０１１１】
図２５には、三角形の順序を付け直すプロセスが記載されている。図２０のような指紋を用意し、同じく三角形７６２〜７６５を抽出する。図２０のように、三角形の不変量は８５０で「小」８６４から「大」８６２の範囲で１Ｄ変数ｙ（８５１）にマッピングされる。この固有の数値ｙは８５５として描かれた第２のマッピングＴによって以下のように変換される。
ｚ＝Ｔｙ
【０１１２】
これは、三角形をスケールｚ８６８に合わせて私有化する１対１のマッピングである。テーブルＱ８６５は最終的に、変換され、（図２０のように）０〜１１の番号も付けられた三角形ｚ８７０のセットを割り当て、量子化されたｚは８７５で０〜１１に列挙される。
【０１１３】
図２６および図２７は、１つまたは複数の特徴を順序付けまたは列挙することにより、異なるタイプのデータ構造を使用して指紋データベース表現を設計できることを示している。
【０１１４】
特に、図２６は、左側に量子化テーブル９１５（または順序付けメカニズム）Ｑを示している。特定の三角形に関連する固有の数値ｙ９２５はｙ９３０に量子化される。このため、実数値の数値ｙ９１０は有限数Ｎ個の可能な三角形９２０のうちの１つであるｙに変換される。その結果として、指紋痕跡はＮ個の三角形のサブセットによって表現され、重複する三角形が存在する可能性がある。Ｎのサイズ（指紋のデータベースのサイズＭよりかなり大きくなければならない）に応じて、重複の発現はますます稀になる。その場合、指紋の表現は、ベクトル９４２〜９４６および９４８などのようなベクトルになる。９４０によって示される通り、ベクトルの長さはＮであり、Ｎが大きい場合、ベクトルは疎になる。データ構造９５０も疎であり、メモリ内のストリング照合を不可能なものにする可能性がある。これらの数値のリストの他の表現も本発明の範囲内であることが分かるであろう。
【０１１５】
図２７は、Ｍ個のＩＤであるＩＤ1９８４〜ＩＤM９８６に関連するＭ個の指紋のデータベースを表す稠密ツリー構造９６０を示している。Ｍ個のＩＤのデータベース内の各要素は、Ｙ＝（ｙ1，ｙ2，・・・，ｙm）Tのように量子化された要素の切り捨てられたベクトルＹ９７０によって記述される。このベクトルの第１の成分ｙ1はＮ1通りの値９７２〜９７４を取ることができる。このベクトルの第２の成分ｙ2はＮ2通りの値９７６〜９７８を取ることができる。次に、第３の成分ｙ3はＮ3通りの値９８０〜９８２を取ることができる。このツリーのｍ番目のレベルのリーフ・ノードは、固有のＩＤであるＩＤ1９８４〜ＩＤM９８６を表す。合計Ｎ＝Ｎ1・Ｎ2・・・Ｎm個の可能な指紋が存在する。これらのうち、一部分であるＭのみがデータベース内の要素Ｙによって占有される。
【０１１６】
本発明の上記その他の特徴および利点は、当業者であれば、本明細書の教示に基づいて容易に確認することができる。本発明の教示が様々な形態のハードウェア、ソフトウェア、ファームウェア、特殊目的プロセッサ、またはこれらの組み合わせで実現可能であることは理解されるであろう。最も好ましくは、本発明の教示はハードウェアとソフトウェアの組み合わせとして実現される。その上、ソフトウェアは、好ましくは、プログラム記憶装置上に具体的に実施されるアプリケーション・プログラムとして実現される。このアプリケーション・プログラムは、任意の適切なアーキテクチャを有するマシンにアップロードし、そのマシンによって実行することができる。好ましくは、このマシンは、１つまたは複数の中央演算処理装置（「ＣＰＵ：central processing unit」）、ランダム・アクセス・メモリ（「ＲＡＭ：random access memory」）、および入出力（「Ｉ／Ｏ：input/output」）インターフェースなどのハードウェアを有するコンピュータ・プラットフォーム上に実現される。このコンピュータ・プラットフォームは、オペレーティング・システムおよびマイクロ命令コードも含むことができる。本明細書に記載されている様々なプロセスおよび機能は、マイクロ命令コードの一部またはアプリケーション・プログラムの一部、あるいはこれらの任意の組み合わせにすることができ、ＣＰＵによって実行することができる。加えて、追加のデータ記憶装置および印刷装置などの様々な他の周辺装置をこのコンピュータ・プラットフォームに接続することができる。添付図面に描かれている構成システム・コンポーネントおよび方法のいくつかは好ましくはソフトウェアで実現されるので、システム・コンポーネント間またはプロセス機能ブロック間の実際の接続は、本発明がプログラミングされる方法に応じて様々になる可能性があることがさらに理解されるであろう。本明細書の教示を考慮すると、当業者であれば、本発明の上記および同様の実現例または構成を企図することができるであろう。
【０１１７】
添付図面に関連して例示的な諸実施形態について本明細書で説明してきたが、本発明がこれらの精密な実施形態に限定されず、当業者であれば、本発明の範囲を逸脱せずにそれに対する様々な変更および修正が実施可能であることが理解されるであろう。
【図面の簡単な説明】
【０１１８】
【図１】従来技術によって使用される模範的なバイオメトリクスを例示する図である。
【図２】従来技術によって使用される模範的なバイオメトリクスを例示する図である。
【図３】従来技術によって使用される模範的なバイオメトリクスを例示する図である。
【図４】従来技術によって使用される模範的なバイオメトリクスを例示する図である。
【図５】従来技術による認証のための自動バイオメトリクス・システムを例示するブロック図である。
【図６】従来技術による識別のための自動バイオメトリクス・システムを例示するブロック図である。
【図７】従来技術により、まずバイオメトリクス信号がひずまされ、次にテンプレートが抽出されるシステムを例示する図である。
【図８】従来技術により、まずテンプレートが抽出され、次に意図的にひずまされるシステムを例示する図である。
【図９】本発明の例示的な一実施形態により、指紋およびその特徴ポイントを示す図表現である。
【図１０】本発明の例示的な一実施形態により、図９の特徴ポイントを特徴付ける幾何学的特徴を例示する図である。
【図１１】本発明の例示的な一実施形態により、図９の特徴ポイントを特徴付ける幾何学的特徴を例示する図である。
【図１２】本発明の様々な例示的な諸実施形態により、測光不変量の抽出を例示する図である。
【図１３】本発明の様々な例示的な諸実施形態により、測光不変量の抽出を例示する図である。
【図１４】本発明の例示的な一実施形態により、コード化プロセスをトレーニングする好ましい手法を例示する図である。
【図１５】本発明の例示的な一実施形態により、トレーニング・セットのコード化の一例を例示する図である。
【図１６】本発明の例示的な一実施形態により、「量子化および列挙」コード化オプションを例示する図である。
【図１７】本発明の例示的な一実施形態により、「量子化および列挙」コード化オプションを例示する図である。
【図１８】本発明の例示的な一実施形態により、「量子化および列挙」コード化オプションを例示する図である。
【図１９】本発明の例示的な一実施形態により、「順序付け、量子化、および列挙」コード化オプションを例示する図である。
【図２０】本発明の例示的な一実施形態により、「順序付け、量子化、および列挙」コード化オプションを例示する図である。
【図２１】本発明の例示的な一実施形態により、１つの指紋画像データの幾何学的および測光情報の局所的変換の一例を例示する図である。
【図２２】本発明の例示的な一実施形態により、画像データの線形／非線形局所的変換の特定のクラスを例示する図である。
【図２３】本発明の例示的な一実施形態により、プライバシを増すために固有の可算離散ベクトルを記録するプロセスを例示する図である。
【図２４】本発明の例示的な一実施形態により、プライバシを増すために固有の可算離散スカラを記録するプロセスを例示する図である。
【図２５】本発明の例示的な一実施形態により、プライバシを増すために固有の可算離散スカラの記録の一実現例を例示する図である。
【図２６】本発明の例示的な一実施形態により、疎ビット・シーケンスのセットとして指紋データベースを例示する図である。
【図２７】本発明の例示的な一実施形態により、稠密ツリー構造内の指紋データベースを例示する図である。
【図２８】１つまたは複数の画像特徴を１つの固有の可算離散数または固有の可算離散ベクトルに変換するコード化プロセスの流れ図である。
【図２９】本発明の例示的な一実施形態により、増加したプライバシに関する記録により、１つまたは複数の画像特徴を１つの固有の可算離散スカラまたは固有の可算離散ベクトルに変換する好ましいコード化プロセスの流れ図である。
【図１】
2008521109.tif 000003
【図２】
2008521109.tif 000004
【図３】
2008521109.tif 000005
【図４】
2008521109.tif 000006
【図５】
2008521109.tif 000007
【図６】
2008521109.tif 000008
【図７】
2008521109.tif 000009
【図８】
2008521109.tif 000010
【図９】
2008521109.tif 000011
【図１０】
2008521109.tif 000012
【図１１】
2008521109.tif 000013
【図１２】
2008521109.tif 000014
【図１３】
2008521109.tif 000015
【図１４】
2008521109.tif 000016
【図１５】
2008521109.tif 000017
【図１６】
2008521109.tif 000018
【図１７】
2008521109.tif 000019
【図１８】
2008521109.tif 000020
【図１９】
2008521109.tif 000021
【図２０】
2008521109.tif 000022
【図２１】
2008521109.tif 000023
【図２２】
2008521109.tif 000024
【図２３】
2008521109.tif 000025
【図２４】
2008521109.tif 000026
【図２５】
2008521109.tif 000027
【図２６】
2008521109.tif 000028
【図２７】
2008521109.tif 000029
【図２８】
2008521109.tif 000030
【図２９】
2008521109.tif 000031
【国際調査報告】
2008521109.tif 000032
2008521109.tif 000033
2008521109.tif 000034
2008521109.tif 000035