(57)【特許請求の範囲】
【請求項１】
指紋の表現を作成する方法であって、前記指紋の中で識別された特徴点のユニークなペアの集合を形成し、特徴点のそれぞれのユニークなペアは、前記ペアに含まれる前記それぞれの特徴点の向きを表す角度及び前記特徴点の間の距離により表現され、前記特徴点のユニークなペアの集合は、２次元の行列のセルから成るデータ構造体として表現され、該セルは前記距離の値を保持し、前記データ構造体は２次元のインデックスを与えられ、
第１の次元は、特徴点の前記ペアに含まれる第１の特徴点の向きを表す、第１の角度に基づいてインデックスを与えられ、
第２の次元は、特徴点の前記ペアに含まれる第２の特徴点の向きを表す、第２の角度に基づいてインデックスを与えられることを特徴とする方法。
【請求項２】
特徴点の前記ユニークなペアは、前記距離及び前記角度によってのみ表されることを特徴とする請求項１に記載の方法。
【請求項３】
前記ペアは、さらに、前記それぞれの特徴点のタイプを示すデータにより表されることを特徴とする請求項１又は２項に記載の方法。
【請求項４】
前記角度は、前記ペアに含まれる両方の特徴点を通って延びる直線に関して表されることを特徴とする請求項１から３までのいずれか一項に記載の方法。
【請求項５】
前記角度は、所定の座標系に関して表されることを特徴とする請求項１又は２に記載の方法。
【請求項６】
個人のアイデンティティをチェックする際に使用する方法であって、
指紋の電子的表現において第１及び第２の特徴点を識別することと、
前記第１の特徴点と第２の特徴点との間の距離を決定することと、
前記第１及び第２の特徴点の向きを表す第１及び第２の角度を決定することと、
エンロール行列を受け取り、前記エンロール行列と請求項１から５までのいずれか一項に記載の前記データ構造体を比較することを含み、
前記指紋の前記電子的表現は現在の指紋を表すことを特徴とする方法。
【請求項７】
前記エンロール行列内の所定の値と前記データ構造体内の所定の値とを比較することを特徴とする請求項６に記載の方法。
【請求項８】
前記エンロール行列内の前記所定の値と前記データ構造体内の前記所定の値との差を作成することを特徴とする請求項７に記載の方法。
【請求項９】
スマート・カード上で実行されることを特徴とする請求項１から８までのいずれか一項に記載の方法。
【請求項１０】
データ処理ユニット内で実行する命令を含むコンピュータ・プログラムを記録したコンピュータ読み取り可能な記録媒体であって、実行中の前記命令により前記データ処理ユニットは請求項１から９までのいずれか一項に記載の方法を実行することを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１１】
前記命令は、スマート・カード上で実行可能であることを特徴とする請求項１０に記載のコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、指紋の表現を作成し、個人のアイデンティティをチェックする際に使用し、個人のアイデンティティをチェックするための基準データを作成する方法、コンピュータ・プログラム製品、及びデバイスに関する。
【背景技術】
【０００２】
指紋の中で特徴点と呼ばれるものを識別し、指紋の中の複数のそのような特徴点の位置、タイプ、及び向きを使用して個人のアイデンティティを識別又は検証することが知られている。個人の指紋の第１の記録では、個人のアイデンティティに関連付けられている基準データを構成するテンプレートが作成される。このプロセスは、通常、エンロールと呼ばれる。テンプレートは、複数の人々のアイデンティティのデータベース内に、又は個人が携帯するスマート・カードなどのデータ記憶媒体上に電子的に格納できる。記録された指紋は、通常、例えば使用する前に２値化により前処理される、イメージ・ファイルとして頻繁に格納され処理される。個人のアイデンティティが検証されるか、又は判別される場合、個人の指紋のイメージが、従来技術により、通常シリコン・センサを使用して記録される。記録されたイメージは、ここでは、「現在の指紋」と呼ばれる。
【０００３】
個人のアイデンティティの「検証」では、現在の指紋を有する個人が、その個人が見せかけようとしている人物であるかどうか、つまりスマート・カードが関連付けられている人であるかどうかを決定することを目的として現在の指紋とテンプレートとが比較される。
【０００４】
個人のアイデンティティの「識別」では、現在の指紋と通常データベース内に格納されている複数のテンプレートとが比較される。
【０００５】
以下で使用する表現「個人のアイデンティティをチェックする」は、識別と検証の両方を含む。
【０００６】
指紋を電子的に表現する複数の手法が知られている。上述のイメージ・ファイルは、特徴点の識別のため処理できる。特徴点を使用することが知られており、個人の指紋の中のその位置と向きは、その個人のユニークな特徴を構成する。また、特徴点を識別し、座標系内でそのタイプ、位置、及び向きを決定することも知られている。検証又は識別では、現在の指紋の特徴点は、１つ又は複数のテンプレートからの特徴点と比較できる。
【０００７】
この方法の変更形態は、基準特徴点を選択し、この基準点に関して残りの特徴点を表現することを含む。これにより、現在の指紋の向きがテンプレートの向きと異なる状況を比較的容易に処理することができる。
【０００８】
ＵＳ−４、１３５、１４７では、特徴点が特徴点近傍に関して記述される方法を開示している。ＵＳ−４、１３５、１４７による方法では、特徴点近傍に関する距離及び角度に関してそれぞれの特徴点を記述するベクトルが作成される。複数のそのようなベクトルからなるテンプレートは、アイデンティティ・チェックで、未知の指紋を表す複数のベクトルと比較することができる。それぞれの特徴点は、特徴点近傍に関して記述されるため、それぞれのそのようなベクトルは、個人のアイデンティティをチェックする場合に比較することが必要な比較的大量の情報を含む。
【０００９】
指紋の中には、２５〜３０個の特徴点が見つかるのがふつうで、最大２００個に達することもときにはある。基準特徴点が使用される場合、これは、たいてい、テンプレート内で任意に選択される。これは、一致を見つけるために、特徴点のペアが他のすべての点のそれぞれとともに形成され、現在の指紋の中のすべての点が基準特徴点としてテストされなければならないことを意味することがある。
【００１０】
しかし、指紋を表現するこの方法は、比較的大きな記憶領域を必要とし、スマート・カードなどの記憶容量の限られている記憶媒体上に指紋を格納するのが望ましい場合には不利である。
【００１１】
それに加えて、現在の指紋とテンプレートとの間で行われなければならない比較はかなり込み入っており、長時間を要する。そのため、これらは、現在の指紋が多数の他の以前に記録されている指紋と比較される個人のアイデンティティをチェックする方法で使用するのにはあまり適していない。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明の目的は、従来技術に関連する問題を全部又は一部解消することである。他の目的は、以下の説明から明白になる。
【課題を解決するための手段】
【００１３】
この目的は、独立の請求項による方法、デバイス、及びコンピュータ・プログラム製品により全部又は一部達成される。本発明のいくつかの実施例は、従属請求項及び以下の説明により定義される。
【００１４】
第１の態様では、指紋の表現を作成する方法が提示される。この方法は、指紋の中で識別された特徴点のユニークなペアを作成することを含み、特徴点のそれぞれのユニークなペアは、前記特徴点の間の距離及びそのペアに含まれるそれぞれの特徴点に関連する角度により表現される。
【００１５】
「ユニークなペア」とは、ペアに含まれる２つの特徴点はペアとして１回だけ出現することを意味する。
【００１６】
この方法により、バイオメトリック・データのコンパクトな格納形式を実現することが可能である。この記憶領域を使用することで、基準データと現在の指紋からの対応するデータとをすばやく比較することができる。
【００１７】
この角度は、それぞれの特徴点の向きを表すことができ、本発明の一実施例は、特徴点のユニークなペアは距離及び２つの角度でのみ表されることを特徴とする。
【００１８】
本発明の他の実施例では、このペアは、それぞれの特徴点のタイプを示すデータにより表すこともできる。タイプの実施例として、隆線の端又は隆線の分岐がある。また、他のタイプも考えられる。
【００１９】
一実施例では、これらの角度は、ペアに含まれる両方の特徴点を通って延びる直線に関して表される。特徴点の各ペアは互いに関係し、所定の座標系に応じて調整しなくてよいため、このことで、ますます、表現は指紋の向きとは無関係になる。
【００２０】
しかし、他の実施例では、これらの角度は、所定の座標系に関して表すことができる。
【００２１】
一実施例では、指紋は、特徴点のユニークなペアの集合により表される。ユニークなペアの集合は、データ構造体、つまり、ベクトル又は行列に関係し、指紋に関連付けられた特徴点のすべてのユニークなペアを表す。
【００２２】
一実施例では、そのような集合は、データ構造体として表すことができ、ペアに含まれるそれぞれの特徴点に関連付けられた角度に基づいてインデックスが作成される。例えば、ペアに含まれる特徴点の間の距離は、角度に基づいてインデックスが作成されたデータ構造体内に配置できる。したがって、それぞれのセル内に距離値を含む、２次元行列構造などが得られる。それぞれのセルは、特徴点に関連付けられた角度がインデックスを構成するようにすることにより一意的に指すことができる。
【００２３】
この結果、２次元インデックスが付けられたデータ構造が得られ、第１の次元は、特徴点の前記ペアに含まれる第１の特徴点に関連付けられている第１の角度に基づいてインデックスが作成され、第２の次元は、特徴点の前記ペアに含まれる第２の特徴点に関連付けられている、第２の角度に基づいてインデックスが作成される。
【００２４】
本発明の第２の態様では、個人のアイデンティティをチェックする際に使用する方法が提示される。この方法は、指紋の電子的表現において、第１及び第２の特徴点を識別すること、前記第１と第２の特徴点の間の前記距離を決定すること、及び前記第１及び第２の特徴点に関連付けられている第１及び第２の角度を決定することを含む。この方法は、さらに、上述のステップのうちの１つを含む。
【００２５】
第３の態様では、データ処理ユニットを含む個人のアイデンティティをチェックする際に使用するデバイスが提示される。このデバイスは、前記データ処理ユニットが指紋の中の識別された特徴点のユニークなペアを作成するように配列され、特徴点のそれぞれのユニークなペアは前記特徴点の間の距離及びそのペアに含まれるそれぞれの特徴点に関連付けられた角度により表現されることを特徴とする。このようなデバイスは、指紋がこの方法に従って処理される指紋読取装置とすることができる。
【００２６】
第４の態様では、データ処理ユニットを含む個人のアイデンティティをチェックする際に使用するデバイスが提示される。このデバイスは、前記データ処理ユニットが現在の指紋の表現を基準指紋データと比較するように配列され、現在の指紋の前記表現は現在の指紋で識別された特徴点のユニークなペアを含み、前記基準指紋データは基準指紋で識別された特徴点のユニークなペアを含み、特徴点のそれぞれのユニークなペアは前記特徴点同士の間の距離及びペアに含まれるそれぞれの特徴点に関連付けられた角度により表されることを特徴とする。このようなデバイスはスマート・カードとすることができ、そのカード上で、現在の指紋と基準指紋データとの比較が実行される。
【００２７】
第５の態様では、個人のアイデンティティをチェックするための基準データを作成する方法が提示される。この方法は、指紋の電子的表現において、第１及び第２の特徴点を識別すること、前記第１と第２の特徴点の間の距離を決定すること、及び前記第１及び第２の特徴点に関連付けられている第１及び第２の角度を決定することを含む。この方法は、さらに、上述の方法による複数のステップを含む。
【００２８】
本発明の他の態様では、これらの方法は、方法を実行するように適合された、コンピュータ・プログラム製品又は特定用途向け集積回路（ＡＳＩＣ）の形態で実装することができる。
【００２９】
本発明は、本発明の実施例の限定されない実施例を示す付属の略図を参照しつつ説明される。
【実施例】
【００３０】
図１を参照すると、そこには指紋１の一部のイメージ略図が示され、複数の特徴点Ｍ１〜Ｍ８が従来技術の方法で識別されており、点線の輪のマークで示されている。マークされている特徴点Ｍ１〜Ｍ８は、端Ｍ１〜Ｍ５及び分岐Ｍ６〜Ｍ８のタイプのものである。また、他のタイプの特徴点もありえ、同様に処理される。
【００３１】
図２は、図１で識別されている複数の特徴点がどのようにイメージから従来技術の方法で抽出され、座標系に従って配列されるかを概略図で示している。特徴点毎に、有向ベクトルは従来技術の方法で識別されている。表１は、点毎に、有向ベクトル、ｘ座標、ｙ座標、及びタイプ、つまり端（「Ｅ」）又は分岐（「Ｂ」）を示すことにより８つの点をどのように表現し格納できるかを示す限定されない実施例をまとめたものである。
【００３２】
【表１】
0004575356.tif 000002
【００３３】
これらｎ個の特徴点から、特徴点の
【数１】
0004575356.tif 000003
個の異なるペアを作成できることは理解されるであろう。したがって、特徴点の２８個の異なるペアを８つの点から作成できる。
【００３４】
そこで、説明は、図３ａを参照すると、指紋のイメージ内で識別されると仮定されている、特徴点Ｍ１、Ｍ２、Ｍ３のペア毎の処理に向けられる。説明されている方法は、エンロール、識別、及び検証において適用することができる。この説明されている方法では、互いに関して特徴点の位置及び向きのみを使用するが、タイプ、絶対位置などの他の特徴も、説明されている方法を補足するために使用できることは理解されるであろう。
【００３５】
図３ａは、例えば、図１のイメージ内で識別された３つの特徴点Ｍ１、Ｍ２、Ｍ３を示している。特徴点はそれぞれ、座標（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）、並びに角度θ１、θ２、及びθ３のペアで表される。角度θ１、θ２、θ３は、ここでは、図３ａで破線により示されているように、イメージの座標系内のｘ軸に関して計算される。さらに、図３ａは、特徴点のそれぞれのペアの間の距離線Ｄ１２、Ｄ１３、及びＤ２３を示す。
【００３６】
図３ｂは、図３ａからの２つの特徴点Ｍ１、Ｍ２のペアを示す。座標（ｘ１，ｘ２）、（ｙ１，ｙ２）、及び角度θ１、θ２のペアに加えて、さらに、破線で特徴点の有向ベクトル間の角度Ｖ１２及びＶ２１がそれぞれ示され、特徴点Ｍ１、Ｍ２の間の距離線Ｄ１２も示されている。さらに、ｘ方向の特徴点とｙ方向の特徴点との間の距離がそれぞれどのように計算されるかが破線により示されている。
【００３７】
次に、図４を参照しつつ、基準指紋データ（テンプレート）を作成する方法、つまり、エンロール方法について説明する。
【００３８】
従来技術の方法により、ステップＳ１で、指紋はイメージの形態で入力され、前処理される。ステップＳ２で、イメージからの特徴点Ｍ１、Ｍ２、Ｍ３が識別され、上の表１の実施例に従ってリストの形態で格納される。
【００３９】
図１及び図２を参照しつつ上で説明したように、点のリストが作成され、そのリストは、特徴点毎に、イメージの座標系に関する少なくとも１つのｘ座標、ｙ座標、及び絶対角度を含む。表２は、図３に示されている特徴点のリストである。
【００４０】
【表２】
0004575356.tif 000004
【００４１】
図３ａの特徴点に基づき、ステップＳ３で、表３に示されているように、特徴点の３つの異なるペアを作成できる。表３に示されている特徴点のペアの座標及び向きは、指紋のイメージの座標系に関して示される。
【００４２】
【表３】
0004575356.tif 000005
【００４３】
ステップＳ４で、特徴点のペアは、特徴点のそれぞれのペアがペアに含まれる点の間の距離及びそれぞれの特徴点の有向ベクトルの間の角度及び特徴点の間の直線を使って記述されるように変換される。
【００４４】
図３ｂに示されているように、２つの点Ｍ１、Ｍ２の間の距離Ｄ１２は、式１に従ってピタゴラスの定理により計算することができる。
【００４５】
【数２】
0004575356.tif 000006
【００４６】
次に、Ｍ１とＭ２の間の距離線に対する角度φ１２は、例えば、式２を使って決定することができる。
【００４７】
【数３】
0004575356.tif 000007
【００４８】
図３ｂに示されているように、特徴点Ｍ１とＭ２との間の距離線に関する第１の特徴点Ｍ１の角度Ｖ１２は、式３により決定することができる。
Ｖ１２＝θ１−φ１２    （３）
【００４９】
ペアに含まれる第２の特徴点は、それに応じて決定され、特徴点のペアは、表４に従って表現することができる。角度は、２桁のインデックスでマークされており、第１の桁は、どの特徴点の角度であるかを示し、第２の桁は、角度の計算に関わる特徴点を示す。
【００５０】
【表４】
0004575356.tif 000008
【００５１】
角度の表現は、適当な方法で表現することができ値でサンプリングすることができる。上述の実施例では、角度は３ビット、つまり、０から７の間の数値でサンプリングされており、分解能は４５°となる。しかし、実際のアプリケーションでは、分解能は高い方が都合がよく、それぞれの角度は、例えば、４、５、６、８、１６、又は３２ビットで表されることは理解されるであろう。
【００５２】
表４の角度のサンプリングでは、以下の表５から明らかな値が得られる。
【００５３】
【表５】
0004575356.tif 000009
【００５４】
その後、以下の表６から明らかになるであろうが、２次元記憶構造、例えば、行列Ｐが作成される。この行列では、ステップＳ５において、Ｄ１２、Ｄ１３、及びＤ２３の値が、それぞれ、表６に示されるように、第１のＶ１角度及び第２のＶ２角度をインデックスとするセル内に配列される。行列内の他のセルは、例えば、０又は他の所望の値で埋めることができる。
【００５５】
【表６】
0004575356.tif 000010
【００５６】
一実施例では、サンプリングは、ステップＳ５に関して実行できる。それとは別に、例えば、ステップＳ３及びＳ４の１つでサンプリングが以前に実行できる。
【００５７】
特徴点の２つのペアが同じインデックスを受け取る、つまり、表６の行列Ｐ内の同じセルに配置されなければならない場合、どれをそこに配置すべきかを選択することが可能である。例えば、互いに最も近い、つまり、Ｄの値で最低である特徴点のペアを保持することが可能である。
【００５８】
このようにして、行列Ｐは、特徴点のすべての、又は所定の量のペアを含むまで埋められる。行列Ｐは、従来技術の方法で、数列として表すことができる。
【００５９】
そこで、指紋のエンロールでは、テンプレートとして使用することができるエンロール行列ＰＥが作成される。エンロール行列は、例えば、スマート・カード上に空間効率を配慮して格納できる。
【００６０】
次に、図５を参照しつつ、検証又は識別の方法について説明する。指紋が検証又は識別と関連して記録される場合、検証行列ＰＶ又は識別行列ＰＩは、それぞれ、相応して作成することができる。以下の説明では、簡単のため検証の場合のみ説明する。識別における方法も同様であることは理解されるであろう。
【００６１】
指紋１を、例えば、指紋読取装置（図に示されていない）からステップＳ１１で受け取る。ステップＳ１２で、図４を参照しつつ説明される方法に対応する方法で指紋が前処理され、それによって、検証行列ＰＶが作成される。
【００６２】
エンロール行列ＰＥは、識別の場合のように、スマート・カードなどのデータ記憶媒体から、又は複数のエンロール行列を含むデータベースから取得することができる。エンロール行列ＰＥは、図４を参照しつつ説明されている方法に従って決定することができる。ステップＳ１２は、指紋読取装置内で実行することができ、検証行列は、スマート・カードに送られ、そこでさらに処理される。
【００６３】
ステップＳ１３では、検証行列及びエンロール行列の比較が実行される。このような比較は、位置同士について実行することができ、各位置について絶対差が計算される。
【００６４】
Ｓ１３の比較結果に基づいて、Ｓ１４で、検証行列ＰＶ及びエンロール行列ＰＥが互いにどれだけ一致するかを表すスコアを計算することができる。スコアは、その値が他の識別技術からの対応するスコアと両立するように適宜スケーリングできる。
【００６５】
本発明の他の実施例では、指紋のイメージから得られる特徴点に関連する角度は、共通座標系に関して表し、上述の方法に類似の方法でデータ構造内に配列することができる。照合に際して、上述の方法により検証行列を表すデータ構造体とエンロール行列を表すデータ構造体とを比較できる。一致度が所定のしきい値よりも低い場合、エンロール行列で表される角度を所定の値だけ増減し、それによって、２つの角度をそれぞれインデックスとする距離値を含む新しい検証行列を取得することができ、比較をもう１度繰り返す。
【００６６】
次に、所定の回転回数がテストされるまで、又は十分に高い一致が得られるまで、この方法を繰り返すことができる。
【００６７】
図６は、本発明による方法を実行できるデバイス３０を示している。このデバイスは、マイクロプロセッサ又はデジタル・シグナル・プロセッサなどの少なくとも１つのデータ処理ユニット３３を備える。デバイスは、指紋読取装置３１に接続されるか、又は一体化できる。さらに、デバイスは、実行されるとデバイスに本発明による方法を実行させる命令を格納するためのメモリ３４を備えることができる。このデバイスは、さらに、ユーザ用の基準データを取り出せるデータ記憶媒体用の読取装置３２に接続するか、又は一体化するか、或いは１人又は複数のユーザからの基準データを取り出せるデータ記憶ユニット３５に接続することができる。
【００６８】
上述のように、特徴点のペアの間の距離に加えて、各特徴点のタイプ又は指紋に関するその絶対角度の指示を格納することにより、上述の格納を補うことが可能である。
【００６９】
行列ＰＥ、ＰＶは、多くの場合、主に（例えば、５０％超の）ゼロを含むので、占有する記憶領域が少なくて済むように従来技術の方法で圧縮することができる。適当な圧縮方法の実施例として、ハフマン符号化及びランレングス符号化がある。
【００７０】
また、より信頼性の高いアイデンティティ・チェックを行うことを目的として上述の方法と他の検証又は識別方法とを組み合わせることも可能である。例えば、異なる検証方法によるスコアを、平均を計算する際に組み合わせることができる。
【００７１】
上述の方法を、詳しく分析されなければならない１つ又は複数の指紋をすばやく見つけるためのスクリーニング方法として使用することも考えられる。これは、多数のテンプレートを含むデータベースに基づいて識別を行う際に特に都合がよい。
【００７２】
本発明は、上述の複数の実施例に限定されず、付属の請求項の範囲内で変更できることは理解されるであろう。また、説明されている実施例を組み合わせることができることも理解されるであろう。
【図面の簡単な説明】
【００７３】
【図１】複数の特徴点が識別されている、指紋の一部のイメージ略図である。
【図２】イメージから抽出されたときの図１の特徴点の概略を例示する図である。
【図３ａ】３つの特徴点のイメージ略図である。
【図３ｂ】特徴点のペアのイメージ略図である。
【図４】本発明による第１の方法の概略流れ図である。
【図５】本発明による第２の方法の概略流れ図である。
【図６】本発明の一態様によるデバイスを示す概略ブロック図である。
【図１】
0004575356.tif 000011
【図２】
0004575356.tif 000012
【図３ａ】
0004575356.tif 000013
【図３ｂ】
0004575356.tif 000014
【図４】
0004575356.tif 000015
【図５】
0004575356.tif 000016
【図６】
0004575356.tif 000017