(57)【要約】【課題】指紋照合において、特徴点間の外れ値や誤対応による影響を低減する。【解決手段】  照合システムが、第１および第２の指紋の特徴点情報を取得するようにされた第１の特徴点取得ユニットおよび第２の特徴点取得ユニットを含んでいる。その第１の指紋の特徴点に対して、メッシュ形成ユニットにより、変形可能なメッシュが形成されると、メッシュ変換ユニットが用いられて、その変形可能なメッシュの状態を変換することにより、歪み補正後の第１の指紋を取得できるようになっている。その歪み補正後の第１の指紋に基づき、照合決定ユニットが、第１の指紋が第２の指紋と一致するかどうかを決定する。【選択図】図８
2008310814.tif 000002
【特許請求の範囲】
【請求項１】
第１の指紋に含まれる第１の特徴点情報を取得するようにされた第１の特徴点取得ユニットと、
第２の指紋に含まれる第２の特徴点情報を取得するようにされた第２の特徴点取得ユニットと、
前記第１の特徴点に基づいて、変形可能なメッシュを形成するように構成されたメッシュ形成ユニットと、
前記変形可能なメッシュの状態を変換して歪み補正後の第１の指紋を取得するように構成されたメッシュ変換ユニットと、
前記歪み補正後の第１の指紋に基づいて、前記第１の指紋が前記第２の指紋と一致するかどうかを決定するように構成された照合決定ユニットと、
を含む、指紋照合システム。
【請求項２】
前記メッシュ変換ユニットがさらに、前記変形可能なメッシュの前記変換後の状態にしたがって前記第１の特徴点を歪ませるように構成されている、請求項１に記載の指紋照合システム。
【請求項３】
前記第１の特徴点と前記第２の特徴点との間の対応を決定するように構成された対応決定ユニットをさらに含み、
前記メッシュ変換ユニットが、前記対応に基づいて、前記変形可能なメッシュの前記状態を変換するように構成されている、
請求項１に記載の指紋照合システム。
【請求項４】
前記メッシュ形成ユニットが、前記変形可能なメッシュが前記第１の特徴点をカバーするように、前記変形可能なメッシュ内の頂点の位置を決定するようにされた頂点位置決定ユニットを含む、請求項１に記載の指紋照合システム。
【請求項５】
前記メッシュ形成ユニットがさらに、前記頂点を結ぶ辺の長さを取得するように構成された辺長さ取得ユニットを含み、
前記頂点位置決定ユニットが、前記取得された辺の長さに基づいて、前記頂点の前記位置を決定するようにされている、
請求項４に記載の指紋照合システム。
【請求項６】
前記変形可能なメッシュの前記状態が、前記頂点の前記位置に基づいて画定される、請求項４に記載の指紋照合システム。
【請求項７】
前記変形可能なメッシュが、六角形状に結ばれる頂点を有する三角形状の２次元（２Ｄ）メッシュである、請求項１に記載の指紋照合システム。
【請求項８】
前記第１の特徴点および前記第２の特徴点が、隆線端点および隆線分岐点の少なくとも１つを含む、請求項１に記載の指紋照合システム。
【請求項９】
入力された指紋の入力特徴点情報を取得するようにされた入力特徴点取得ユニットと、
前記入力特徴点に対して、変形可能なメッシュを形成するように構成されたメッシュ形成ユニットと、
前記変形可能なメッシュの状態を変換して前記入力された指紋の表面歪みを補正するように構成されたメッシュ変換ユニットと、
を含む、入力された指紋の表面歪みを補正するシステム。
【請求項１０】
指紋テンプレートのテンプレート特徴点情報を取得するように構成されたテンプレート特徴点取得ユニットと、
前記入力特徴点と前記テンプレート特徴点との間の対応を決定するように構成された対応決定ユニットと、をさらに含み、
前記メッシュ変換ユニットがさらに、前記対応に基づいて、前記変形可能なメッシュの前記状態を変換するように構成されている、請求項９に記載のシステム。
【請求項１１】
（ａ）第１の指紋の特徴点および第２の指紋の特徴点を取得するステップと、
（ｂ）前記第１の指紋の前記特徴点と前記第２の指紋の前記特徴点との間の対応を見つけるステップと、
（ｃ）前記第１の指紋の前記特徴点に対して、変形可能なメッシュを形成するステップと、
（ｄ）前記変形可能なメッシュを変換して、前記対応に基づいて、歪み補正後の第１の指紋を取得するステップと、
（ｅ）前記歪み補正後の第１の指紋に基づいて、前記第１の指紋が前記第２の指紋と一致するかどうかを決定するステップと、
を含む、指紋照合方法。
【請求項１２】
前記ステップ（ｄ）が、
（ｄ１）前記変形可能なメッシュを変形して、前記変形可能なメッシュの変形にしたがって増加し、対応する特徴点が前記変換により近づくにつれて減少するものとして定義されるエネルギを最小限に抑えるステップを含む、請求項１１に記載の指紋照合方法。
【請求項１３】
前記ステップ（ｄ１）が、
（ｄ１１）前記エネルギの一次微分値を解析的に計算するステップと、
（ｄ１２）前記エネルギの二次微分値を解析的に計算するステップと、
（ｄ１３）前記一次微分値および前記二次微分値に基づいて、前記変形可能なメッシュを変換するステップと
を含む、請求項１２に記載の指紋照合方法。
【請求項１４】
前記一次微分値が、前記変換の方向に関し、前記二次微分値が前記変換の量に関する、請求項１３に記載の指紋照合方法。
【請求項１５】
前記エネルギが、信頼半径を上回る距離を有する対応を無視し、
前記ステップ（ｄ）がさらに、
（ｄ２）前記信頼半径を減衰するステップと、
（ｄ３）前記減衰後の信頼半径が、所定の終了条件を満たしているかどうかを決定するステップと、
（ｄ４）前記減衰後の信頼半径が前記所定の終了条件を満たしていないと判断した場合、前記ステップ（ｄ１）から（ｄ３）を繰り返すステップと、
を含む、請求項１２に記載の指紋照合方法。
【請求項１６】
前記減衰後の信頼半径が所定の閾値を下回っているとき、前記所定の終了条件が満たされる、請求項１５に記載の指紋照合方法。
【請求項１７】
第１の指紋の特徴点および第２の指紋の特徴点を取得する手段と、
前記第１の指紋の前記特徴点と前記第２の指紋の前記特徴点との間の対応を見つける手段と、
前記第１の指紋の前記特徴点に対して、変形可能なメッシュを形成する手段と、
前記対応に基づいて、前記変形可能なメッシュを変換して歪み補正後の第１の指紋を取得する手段と、
前記歪み補正後の第１の指紋に基づいて、前記第１の指紋が前記第２の指紋と一致するかどうかを決定する手段と、
を含む、指紋照合装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は概して、バイオメトリクス技術に関し、特に、指紋照合システムおよび指紋照合方法に関する。
【背景技術】
【０００２】
指紋は、バイオメトリック認証および証明において最も広汎に用いられている身体的特徴の１つである。最近、指紋認証はバイオメトリクス技術としてますます普及してきている。というのも、その性能や信頼性といった面からみて望ましい性能をバランスよく備えているからである。そのため、近年では、自動指紋認証システム（ＡＦＩＳ）、すなわち１つまたは複数の未知の指紋を既知指紋のデータベースに自動的に照合するシステムの分野において、多大な研究開発が行われている。ＡＦＩＳのステージの１つが指紋照合ステージであり、このステージでは、入力された指紋データが、１つまたは複数の指紋テンプレートと照合される。
【０００３】
指紋照合アルゴリズムの中でも、特徴点（マニューシャ：minutia）方式は、最も広汎に用いられ、信頼性の高い方法の１つである。特徴点とは、指紋隆線の端点や分岐点などの、指紋の詳細部分のことである。図１Ａは、特徴点を含むスキャンした指紋画像を示しており、黒い線が指紋隆線を示している。この指紋には、隆線端点１０２および隆線分岐点１０４が含まれている。図１Ｂおよび図１Ｃはそれぞれ、隆線端点および隆線分岐点をさらに詳細に示している。
【０００４】
図１Ｂおよび図１Ｃを参照すると、各特徴点を、その位置（黒丸１０６で示す）および方向（線分１０８で示す）で表すことができる。ＡＮＳＩ−ＮＩＳＴ規格との互換性を得るため、特徴点方式では、その特徴点に関する位置および方向の情報のみを使用しなければならない。ただし、この方式は、他システムの既抽出特徴点のテンプレートを使用することができるため、計算資源に限界があるシステムには適している。位置および方向の情報のみを使用する場合、指紋照合を、対応するポイント対を見つけるというポイントパターン照合課題であると見なすことができる。ところが、この方式には少なくとも２つの問題がある。まず、照合精度が、皮膚の状態に何らかの変化があった場合に生じる特徴点抽出段階での偽の特徴点や欠落した特徴点に影響されてしまう。もう１つの問題は、例えば皮膚の弾力性および／または指紋取得中に起こる指による（センサ表面上への）圧力やその移動などにより、指紋画像に非線形歪みができることである。
【０００５】
上記問題点の解決へ向けて、これまでさまざまな方法が提案されてきており、最近では、クォンらが、特徴点のクラスタリングおよびワーピング（歪み変形：warping）を用いた指紋照合案を提案している（非特許文献１参照。）。クォンらの方法では、指紋照合に局所近傍構造およびシンプレートスプライン（ＴＰＳ）モデルを用いている。
【非特許文献１】「特徴点のクラスタリングおよびワーピングを用いた指紋照合方法」パターン認識国際会議、第４巻、５２５〜５２８ページ、２００６年
【非特許文献２】「オンライン指紋検査」、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  Ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、１９（４）：３０２−３１４ページ、１９９７年
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、ＴＰＳモデルが基本的に、無限応答の基本関数を有する表面補間式であるため、特徴点間に外れ値（outliers）や誤対応があると指紋表面を誤って歪めてしまい、これが大域に影響を及ぼす結果となる。これは、ＴＰＳモデルが指紋照合に用いられた場合の根本的かつ共通する問題である。
【課題を解決するための手段】
【０００７】
本開示は、指紋照合システムおよび指紋照合方法について記載する。一実施形態において、システムは、第１の指紋の特徴点情報および第２の指紋の特徴点情報を取得するための第１の特徴点取得ユニットおよび第２の特徴点取得ユニットを備えている。第１の指紋の特徴点に対して、メッシュ形成ユニットにより変形可能なメッシュを形成することができ、メッシュ変換ユニットを用いて、その変形可能なメッシュの状態を変換して、歪み補正をした第１の指紋を得ることができる。この歪み補正後の第１の指紋に基づいて、照合決定ユニットが、第１の指紋が第２の指紋と一致するかどうかを決定する。
【０００８】
別の実施形態において、システムは、入力された指紋に関して入力された特徴点情報を得る入力特徴点取得ユニットと、その入力された特徴点に対する変形可能なメッシュを形成するメッシュ形成ユニットとを備えることができる。このシステムはさらに、変形可能なメッシュの状態を変換して、入力された指紋の表面歪みを補正するメッシュ変換ユニットを備えることができる。
【０００９】
さらに別の実施形態において、指紋照合方法は、第１の指紋の特徴点および第２の指紋の特徴点を得るステップを含むことができる。この方法はまた、第１の指紋の特徴点と第２の指紋の特徴点との対応を見出すステップと、第１の指紋の特徴点に対して、変形可能なメッシュを形成するステップとを含むことができる。この方法はまた、その対応に基づいて、その変形可能なメッシュを変換して、歪み補正後の第１の指紋を得るステップと、歪み補正後の第１の指紋に基づいて、第１の指紋が第２の指紋と一致するかどうかを決定するステップとを含むことができる。
【００１０】
添付の図面は、本発明による典型的な実施形態を示すものであり、したがって、本開示の範囲を何ら制限するものと解釈してはならない。以下、本開示を、添付の図面を用いてさらに具体的かつ詳細に説明する。
【発明を実施するための最良の形態】
【００１１】
本発明の構成要素は、本明細書内に概略を記載し、図に例示しているが、種々に異なる構成に配置および設計可能であることが、容易に理解できるであろう。したがって、本発明によるシステムおよび方法の実施形態をさらに詳しく説明する以下の記載は、本請求内容を何ら制限するものではなく、本発明により現時点で考えられる実施形態について特定の例を単に挙げたに過ぎない。ここに記載する実施形態は、添付の図面を参照すると理解できるはずであり、この図面では、全図面を通して、同様の部分に同様の参照符号を付している。
【００１２】
図２を参照すると、指紋認識を目的とするシステム２００の一実施形態が図示されている。システム２００は、指紋入力ユニット２０２、指紋データベース２０４、および指紋照合システム２０６を含む。指紋入力ユニット２０２は、指紋を取得するために一般に利用可能な機構を含むことができる。例えば、指紋入力ユニット２０２は、指紋を走査するための光学指紋スキャナを含んでもよい。指紋データベース２０４は、事前に記録された指紋の情報を格納することができる。例えば、指紋データベース２０４に、指紋の特徴点に関する位置および方向などの特徴点情報を格納しておくことが可能である。指紋照合ユニット２０６は、メッシュベース・ワーピングユニット２０８を含むことができる。
【００１３】
指紋照合システム２０６は概して、指紋入力ユニット２０２から指紋を受信し（以下、本明細書ではこれを入力された指紋と称する）、指紋データベース２０４から事前に記録された指紋の情報を受信する（以下、本明細書ではこれを指紋テンプレートと称する）。特定の実施形態において、指紋照合システム２０６は、入力された指紋および指紋テンプレートを受信すると、入力された指紋が指紋テンプレートと一致するかどうかを決定する。この決定のため、指紋照合システム２０６は、メッシュベース・ワーピングユニット２０８を用いてもよい。さらに、例示していないが、他の実施形態において、指紋照合システム２０６を１つまたは複数の他のシステムと連結しても、１つまたは複数の他のシステム内に内蔵してもよい。こうした他のシステムは、指紋照合システム２０６からの照合結果をさまざまな目的で使用することができる。例えば、指紋照合システム２０６をコンピュータ、ロック、その他の電子デバイスに連結して、入力された指紋が指紋テンプレートと一致すると決定された際に動作させることができる。
【００１４】
図３を参照すると、指紋照合システム２０６の一実施形態が図示されている。例示した実施形態において、指紋照合システム２０６は、第１の特徴点取得ユニット３０２、第２の特徴点取得ユニット３０４、対応決定ユニット３０６、メッシュベース・ワーピングユニット２０８、照合決定ユニット３１０を含む。第１の特徴点取得ユニット３０２は、一般に、入力された指紋である、第１の指紋の特徴点情報を取得する。例えば、第１の特徴点取得ユニット３０２は、指紋入力ユニット２０２から、入力された指紋について走査画像を受信すると、一般に既知である方法を用いてその画像から特徴点情報を抽出する。以下、本明細書では、この第１の特徴点取得ユニット３０２が取得した特徴点情報を第１の特徴点情報とする。
【００１５】
第２の特徴点取得ユニット３０４は、一般に指紋テンプレートである第２の指紋の特徴点情報を取得する。例えば指紋データベース２０４が第２の特徴点取得ユニット３０４に特徴点情報を提供すると、第２の特徴点取得ユニット３０４は、受信したその特徴点情報を何ら変更を加えずに対応決定ユニット３０６に提供することができる。以下、本明細書では、この第２の特徴点取得ユニット３０４が取得した情報を、第２の特徴点情報とする。
【００１６】
対応決定ユニット３０６は概して、第１の特徴点情報および第２の特徴点情報を受信し、その第１の特徴点と第２の特徴点との間の対応を決定する。対応決定ユニット３０６では、既存の方法を含むいずれの方法を用いて（例えば、ジェインらにより開示された調整可能なバウンディングボックスを用いた方法（非特許文献２参照。）、およびクォンらにより開示された局所近傍構造を用いた方法（非特許文献１参照。））、この特徴点対応を取得してもよい。一実施形態において、対応決定ユニット３０６は、上述したクォンらの方法による局所近傍構造を用いている。この場合、局所構造は、特徴点の近傍情報を使って形成される。形成後、第１の特徴点の局所構造情報と第２の特徴点の局所構造情報とを比較して、特徴点の対応を取得する。次いで、任意に、剛体変換（regid transformation）による形状確認操作（geometric verification operation）で外れ値を除去し、入力された指紋を整合位置から繰り返し変換して、照合特徴点クラスタを得る。ただし、本発明の特定実施形態によっては許容範囲内となる外れ値もあるため、こうした実施形態では、形状確認をしないままの対応が特徴点の対応結果として提供される場合もあることに留意されたい。
【００１７】
特徴点の対応結果は大抵、複数対の特徴点のセットを含んでおり、その各対に、第１の特徴点と第２の特徴点との間での対応が含まれている。実施形態によっては、特徴点の対応を、ｃ＝（ｃ０，ｃ１）で表すことができ、このとき、ｃ０およびｃ１はそれぞれ、第１および第２の指紋における対応特徴点の位置である。対応決定ユニット２０８の出力内容にはさらに、追加情報を含めることが可能である。例えば、一実施形態において、一致決定ユニット２０８はさらに、各対応の重みを決定することができる。この重みは、０から１まで可変であり、重みが大きいほど、対応の信頼性が高いことを意味する。
【００１８】
メッシュベース・ワーピングユニット２０８は概して、第１および第２の特徴点を含む特徴点の対応を受信し、その受信情報に基づいて指紋表面ワーピング操作を行う。表面のワーピングを行うことにより、メッシュベース・ワーピングユニット２０８は、歪んでいた可能性のある第１の指紋から歪み補正後の第１の指紋を回復することができる。メッシュベース・ワーピングユニット２０８の実施形態については、以下でさらに詳しく説明する。
【００１９】
照合決定ユニット３１０が、その歪み補正後の第１の指紋に基づき、第１の指紋が第２の指紋と一致するかどうかを決定する。この決定に際し、照合決定ユニット３１０は、適した照合方法のいずれも用いることができ、その例として、グローバル照合および評価方式などの周知の方法が挙げられる。一実施形態において、照合決定ユニット３１０を、クォンらの方法で用いられているグローバル照合および評価方式を用いるように構成することができる。
【００２０】
ここで図４を参照すると、メッシュベース・ワーピングユニット２０８の一実施形態が図示されている。図４を参照すると、メッシュベース・ワーピングユニット２０８は、メッシュ形成ユニット４０２およびメッシュ変換ユニット４０４を含む。メッシュ形成ユニット４０２は、例えば第１の特徴点に対して、変形可能なメッシュを形成するものである。図６Ａに、第１の特徴点に対して形成された変形可能なメッシュの例が示されている。この例では、変形可能なメッシュは、六角形状に結ばれる頂点を有する三角形状の２次元（２Ｄ）メッシュモデル（triangulated 2-dimensional (2-D) mesh model having hexagonally connected vertices）である。図６Ａを参照すると、第１の特徴点情報内の特徴点の位置が黒い四角６０２で示され、その四角６０２から延びる線分６０４で、その特徴点の方向を示されている。さらに、丸い頂点６０６とその頂点を結ぶ辺６０８で、第１の特徴点に対して形成された変形可能なメッシュが示されている。第１の特徴点に対して変形可能なメッシュを形成した後、メッシュ変換ユニット４０４が、第１の特徴点に対する変形可能なメッシュを変形し、これにより、変形可能なメッシュで表される第１の指紋表面を第２の指紋表面に近づける。この第２の指紋表面は、第２の特徴点が抽出された指紋表面に相当する。言い換えれば、変形可能なメッシュを変形することで第１の指紋の表面歪みを補正して、より精度がに高い第１の指紋を回復する。
【００２１】
図５を参照すると、メッシュ形成ユニット４０２の一実施形態が図示されている。本実施形態では、メッシュ形成ユニット４０２は、バウンディングボックス設定ユニット５０２、頂点位置決定ユニット５０４、および辺長さ取得ユニット５０６を含む。メッシュ形成ユニット４０２が第１の特徴点に対して変形可能なメッシュを形成すると、これに応答して、バウンディングボックス設定ユニット５０２が、第１の特徴点情報内の特徴点がボックス内部に入るようにその大きさおよび位置を決定して、仮想のバウンディング２次元ボックス（図示せず）を設定する。すると、頂点位置決定ユニット５０４が、形成されたメッシュがバウンディングボックスをカバーするように、メッシュ頂点６０６それぞれの位置（すなわちｘｙ座標）を決定する。一実施形態において、メッシュ頂点６０６の位置を、メッシュ頂点６０６間の辺６０８の長さに基づいて決定する。この場合、辺長さ取得ユニット５０６を用いて辺の長さを求めることができる。この辺の長さを、指紋照合システムにおいてハードコード化してもよいし、書き換え型記憶装置に記録してもよい。後者の場合、システム２００にさらに、辺の長さを調節する制御ユニットを含めることができる。また、辺長さ取得ユニット５０６により、辺の長さを実行時間内で動的に決定してもよい。例えばメッシュの目が細かくなるなど、辺の長さが短いほど、指紋照合の精度は高くなることに留意されたい。ただし、辺の長さが短いほど、指紋照合処理の実行時間は長くなる。したがって、辺の長さを指紋照合の目的や要求内容によって決定してもよい。例えば、指紋照合をきわめて重要な情報にアクセスするために使用する場合には、それより重要性の低い情報にアクセスするために用いる場合よりも、辺の長さを短く選択することができる。本明細書では挙げていないが、本発明の観点から、当業者であれば、上記以外のさまざまな状況や変数に基づいて辺の長さを決定できることが、明らかであろう。
【００２２】
ここで、メッシュ変換ユニット４０４の一実施形態について、さらに詳しく説明する。本実施形態では、メッシュ変換ユニット４０４は概して、第１および第２の特徴点情報を含む特徴点の対応と、第１の特徴点情報に対して形成された変形可能なメッシュとを受信する。その後、上述したように、メッシュ変換ユニット４０４は、第１の特徴点情報に対して形成された変形可能なメッシュを変形して、変形可能なメッシュで表された第１の指紋表面を、第２の特徴点が抽出された指紋表面に相当する第２の指紋表面に近づける。図６Ｃは、変形後のメッシュの例を示している。この変換により、メッシュの頂点の位置が新たな位置に移動して、メッシュの新たな状態を構成していることがわかるであろう。また、メッシュ頂点がこのように新たな位置に移動したことにより、メッシュ頂点に囲まれていた特徴点も新たな位置にワープしている。この新たな位置を、以下、本明細書ではワープ位置と呼ぶ。例えば、図６Ａの特徴点ｐは、図６Ａの頂点ｖｉ、ｖｊ、ｖｋが図６Ｃで新たな位置ｖｉ´、ｖｊ´、ｖｋ´にそれぞれ移動したのに伴って、新たな位置ｐ´へとワープしている。
【００２３】
図６Ａ〜図６Ｃを参照しながら、特徴点のワーピングについてさらに詳細に記載する。頂点ｖｉを、特徴点ｐを含む三角形の頂点の１つとする。すると、図６Ｂに示すように、ｖｉに対向する下位三角形の面積から重心座標Ｂi（ｐ）を算出することができる。つまり、特徴点ｐと頂点ｖｊおよびｖｋとが下位三角形の頂点となり、ここから重心座標Ｂi（ｐ）が導きだされる。３つの頂点ｖｉ、ｖｊ、ｖｋに対する重心座標をそれぞれ算出すると、メッシュ頂点の状態Ｓにおける特徴点ｐの位置ＴＳ（ｐ）は、以下のように表される。
ＴＳ（ｐ）＝Ｂi（ｐ）ｖｉ＋Ｂj（ｐ）ｖｊ＋Ｂk（ｐ）ｖｋ
すなわち、メッシュが変換され、メッシュ頂点が新たな状態Ｓ´に変換されると、変換後の特徴点ｐのワープ位置を、重心座標と３つの頂点の新たな位置とを用いて算出することができる。例えば、図６Ｃのワープ位置ｐ´は、Ｓ´がメッシュ頂点の変換後状態を表すものとすると、以下のように算出可能である。
ｐ´＝ＴＳ´（ｐ）＝Ｂi（ｐ）ｖｉ´＋Ｂj（ｐ）ｖｊ´＋Ｂk（ｐ）ｖｋ´
【００２４】
この実施形態で用いる変換のために、メッシュ変換ユニット４０４はエネルギ関数を用いてもよい。言い換えれば、メッシュ変換ユニット４０４は、エネルギ関数を用いて、メッシュの新たな状態を決定することができる。一実施形態において、このエネルギ関数を、メッシュの変形量が増えるほどエネルギも増え、対応する特徴点が近いほどエネルギが小さくなるように定義することができる。例えば、所与状態Ｓと対応Ｃ、エネルギＥを以下のように定義することができる。
Ｅ（Ｓ，Ｃ，ｒ）＝λＤＥＤ（Ｓ）＋ＥＣ（Ｓ，Ｃ，ｒ）
このとき、ＥＤは変形エネルギ、ＥＣは対応エネルギ、λＤは、メッシュの規則性に対する制御パラメータ、ｒは信頼半径（confidence radius）である。この場合、ＥＤは、メッシュが変形するほど増加する正の数、ＥＣは、対応する特徴点が近いほどに絶対値が増加する負の数である。こうすると、エネルギを最小化にすることで、変換によるメッシュの変形が特徴点間の接近を圧迫しない限り、対応する特徴点が近くなるようにメッシュが変換される。したがって、エネルギの最小化を、第１の指紋を第２の指紋に近づけるための変換と捉えることができる。
【００２５】
別の実施形態において、変形エネルギＥＤを、メッシュ頂点のｘ座標およびｙ座標の二次微分値をそれぞれ二乗して足した和の概算値として定義することができる。つまり、連続して一直線上にある３つの頂点の添数集合（an index set of successive collinear three vertices）をＬとすると、変形エネルギＥＤは、以下のように定義できる。
【数１】
2008310814.tif 000003
これは、以下のようにも定義できる。
【数２】
2008310814.tif 000004
このとき、ＸおよびＹはそれぞれ、メッシュ頂点のｘ座標およびｙ座標の行順序によるマトリクスである。ＥＤは、不規則な間隔で位置する頂点には不利となる。Ｋは、Ｋ´ＴＫ´から形成可能である。ここで、Ｋ´は、Ｌ内の３頂点ごとの一行とメッシュ頂点ごとの一列とを含むマトリクスである。詳細には、３頂点（ｉ，ｊ，ｋ）に相当するＫ´のｒ番目の行は、以下のように定義できる。
Ｋ´ｒｉ＝−１，  Ｋ´ｒｊ＝２，  Ｋ´ｒｋ＝−１，  Ｋ´ｒｃ＝０  （ｃ≠ｉ，ｊ，ｋ）
状態ＳはＸおよびＹを含意することに留意されたい。
【００２６】
さらに、対応エネルギＥＣは次のように定義できる。
【数３】
2008310814.tif 000005
この式において、ｄ＝||ｃ１−ＴＳ（ｃ０）||であり、ｃ１は、第１の指紋の特徴点ｃ０に対応する第２の指紋の特徴点である。つまり、ｄは、特徴点ｃ０のワープ位置と特徴点ｃ１の位置との間の距離を示す。さらに、ωｃは、対応の重みである。対応の重みがまだ決定されていない場合、ωｃを１などの定数に設定することができる。ρはロバスト推定量である。一実施形態において、ロバスト推定量ρを以下のように定義できる。
【数４】
2008310814.tif 000006
このロバスト推定量は次のような性質を持っている。信頼半径ｒが大きいと、大半の対応の重みがエネルギ内で総和され、信頼半径ｒが小さいと、選択された対応のみの重みが用いられる。本発明の観点から、当業者であれば、ロバスト推定量の性質を利用すると、信頼半径ｒが小さくなるにしたがって表面のワーピングから外れ値を除外しやすくなることが明白であろう。
【００２７】
メッシュ変換ユニット４０４は、固定の信頼半径ｒに対するエネルギＥを最小限に抑える。これを最適化と呼ぶこともできる。この最適化の一実施形態の擬似コード表示（pseudo code representation）を図７Ａに示す。図７Ａに示した最適化は、一般のライン探索（１１〜１６行目）用にニュートン・ラプソン法を、収束促進用にポラック・リビエール方式（２２行目）を用いている。ここで、図７Ａは擬似コード表示の形態における最適化を示しているが、最適化はソフトウェアのみで実施可能なのではなく、ハードウェア、ファームウェアなどや、これらの組み合わせを含むものでも実施可能であることに留意されたい。
【００２８】
図７Ａに示す最適化において、エネルギ関数の一次偏微分値は、変換の方向に関するものであり、ｄとして表される。また、二次微分値は、変換量の決定に用いられ、αとして表される。この一次および二次微分値は解析的に算出可能であるため、最適化を効率的に実施しやすくなる。ｘ座標の一次微分値については、以下の式を使用することができる。
【数５】
2008310814.tif 000007
このとき、対応エネルギＥＣの微分値は、以下の式を使用して算出できる。
【数６】
2008310814.tif 000008
このとき、Ｃｉは、対応の一組であり、ｃ０は、ｖｉを頂点とする三角形に含まれる。さらにｘ座標の二次微分値について、以下の式を使用できる。
【数７】
2008310814.tif 000009
【数８】
2008310814.tif 000010
この一次および二次微分値の式において、ｃ０を含む三角形の頂点インデックスのセットをＶ（ｃ０）とした場合、総和は、ｄ＜ｒかつ（ｉ，ｊ，ｋ）＝Ｖ（ｃ０）の条件でとられるものである。ｙ座標の微分値も同様に算出できる。プレコンディショナマトリクスＭは、以下の式を用いる。
【数９】
2008310814.tif 000011
一実施形態において、Ｍ−１（４、２０行目）をＬＵ分解を用いて効率よく算出できる。また、一実施形態において、変数ε（８、１６行目）を、例えば１０−６に設定し、ループ終了変数ｉmax（８行目）およびｊmax（１６行目）を小さい数に固定することができる。
【００２９】
さらに、実施形態によっては、メッシュ変換ユニット４０４で最適化を反復することができる。この反復の一実施形態を、図７Ｂに擬似コードとして表す。図７Ｂを参照すると、信頼半径ｒは、所定の閾値ｒｅを下回るまで、最適化が反復されるに従って減衰する。信頼半径ｒが大きい場合、ＥＤの影響はＥＣより大きいため、メッシュの変形は硬直的である。しかし、信頼半径ｒが減少するにつれ、ＥＣが次第にＥＤより影響を及ぼすようになるため、メッシュは正確に一致するまで変形する。これにより、信頼半径ｒが減少するにつれて外れ値の影響は少なくなる。一例において、入力された特徴点のバウンディングボックスの幅をｒ０として用い、ｒｅ＝０．５、η＝０.５とすることができる。
【００３０】
ここで図８を参照すると、指紋照合方法の一実施形態が図示されている。まず、ステップ８０２において、方法８００は、一般に、入力された指紋の特徴点情報である第１の特徴点情報と、一般に指紋テンプレートの特徴点情報である第２の特徴点情報とを取得する。次いで、方法８００は、ステップ８０４において、第１の特徴点と第２の特徴点との間の対応を見つける。対応を見つけるために、方法８００は、周知の方法、または他の適した方法のいずれを用いてもよい。また方法８００は、ステップ８０６において、第１の特徴点に対して変形可能なメッシュを形成する。一実施形態において、この変形可能なメッシュは、上述したように、メッシュ形成ユニット４０２（図４）などのメッシュ形成ユニットを用いて形成される。次いで、ステップ８０８において、方法８００は、第１の特徴点に対して形成された変形可能なメッシュを変換して、第１の特徴点をワープさせる。一実施形態において、このワーピングステップは、メッシュ変換ユニット４０４（図４）などのメッシュ変換ユニットにより行われる。ワーピングステップ８０８により、第１の指紋の表面歪みを補正し、歪み補正後の第１の指紋、すなわち、より精度が高い第１の指紋を得ることができる。このより精度が高い第１の指紋に基づき、方法８００は、ステップ８１０において、第１の指紋が第２の指紋と一致するかどうかを決定する。
【００３１】
図９を参照しながら、ワーピング操作の一実施形態についてさらに詳細に記載する。この実施形態は、エネルギ関数を用いている。エネルギ関数の詳細については上述した通りである。エネルギ関数の一次微分値をステップ９０２において算出し、エネルギ関数の二次微分値をステップ９０４において算出する。この微分値を、上述したように解析的に算出してもよい。次いで、この一次微分値および二次微分値に基づき、ステップ９０６において、エネルギ関数で定義されるエネルギを固定の信頼半径について最適化する。例えば、図７Ａに示したような手順を用いて、このエネルギ関数を最適化することができる。次いで、ステップ９０８において、信頼半径を減衰させる。この減衰の例として、特に限定されないが、所定の減衰定数を現時点の信頼半径に掛け合わせることが挙げられる。減衰後の信頼半径は、ステップ９１０において、所定の閾値と比較される。減衰後の信頼半径が所定の閾値を上回っている場合、減衰後の信頼半径を用いて上記ステップが繰り返される。減衰後の信頼半径を用いて最適化を反復することにより、ワーピングステップ８０８で、指紋照合における外れ値の影響を減らすことができる。
【００３２】
本明細書に記載した実施形態では、第１の指紋を、入力された指紋、第２の指紋を指紋テンプレートとして想定しているが、本発明はこれに限定されるものではなく、これにさまざまな変更が適用可能である。また、本明細書に記載のワーピングユニットおよびワーピングステップは、そのワーピング操作にエネルギ関数を用いているが、ワーピングユニットおよびワーピングステップでは他のさまざまな方法でワーピングを行うことができる。さらに、上述の実施形態では、解析的に計算した第１および第２の偏微分値に基づいてエネルギ関数を最適化しているが、本発明の観点から、当業者には、他の方法や変更をこれに追加して、またはこれに代わって使用可能であることが明白であろう。
【００３３】
本開示の観点から、当業者には、本明細書に記載したシステムおよび方法を、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、またはこれらの組み合わせで実施可能であり、そのシステム、サブシステム、コンポーネント、サブコンポーネントで使用可能であることを理解されたい。例えば、方法をソフトウェアで実行する例として、該方法のステップを行うためのコンピュータコードが挙げられる。このコンピュータコードをプロセッサ可読媒体やコンピュータプログラム製品などの機械可読媒体に格納し、伝送媒体や通信リンクを通じて、搬送波に乗せたコンピュータデータ信号、またはキャリアで変調した信号として送信することができる。この機械可読媒体やプロセッサ可読媒体には、機械で読込み可能かつ実行可能な形態で情報を格納したり転送したりできるあらゆる媒体（例えば、プロセッサ、コンピュータ、携帯デバイス、メディアプレーヤーなど）を含めることができる。
【００３４】
ここに開示したシステムおよび方法は、その基本的な特性や特徴から逸脱することなく、他の具体的な形態で具体化することができる。よって、上記実施形態は、あらゆる点で例示のみを目的としたものであり、何ら制限するものではない。したがって、本発明の範囲は、上記記載ではなく添付の請求の範囲により示されるものである。この請求の範囲と等価である意味および範囲内で加えられる変更のすべてが、この範囲に含まれるものとする。
【図面の簡単な説明】
【００３５】
【図１Ａ】指紋とその特徴点の一例である。
【図１Ｂ】指紋とその特徴点の一例である。
【図１Ｃ】指紋とその特徴点の一例である。
【図２】指紋認識システムの一例である。
【図３】本発明による指紋照合システムの一実施形態である。
【図４】ワーピングユニットの一実施形態である。
【図５】メッシュ形成ユニットの一実施形態である。
【図６Ａ】変形可能なメッシュとその変換である。
【図６Ｂ】変形可能なメッシュとその変換である。
【図６Ｃ】変形可能なメッシュとその変換である。
【図７Ａ】本発明による最適化および反復の一実施形態である。
【図７Ｂ】本発明による最適化および反復の一実施形態である。
【図８】本発明による指紋照合方法の一実施形態である。
【図９】ワーピング操作の一実施形態である。
【図２】
2008310814.tif 000012
【図３】
2008310814.tif 000013
【図４】
2008310814.tif 000014
【図５】
2008310814.tif 000015
【図６Ａ】
2008310814.tif 000016
【図６Ｂ】
2008310814.tif 000017
【図６Ｃ】
2008310814.tif 000018
【図７Ａ】
2008310814.tif 000019
【図７Ｂ】
2008310814.tif 000020
【図８】
2008310814.tif 000021
【図９】
2008310814.tif 000022
【図１Ａ】
2008310814.tif 000023
【図１Ｂ】
2008310814.tif 000024
【図１Ｃ】
2008310814.tif 000025
【外国語明細書】
2008310814000001.pdf