JP2003271959A

JP2003271959A - 試験レコードの特徴を参照レコードの特徴と比較する方法

Info

Publication number: JP2003271959A
Application number: JP2002304873A
Authority: JP
Inventors: Baback Moghaddam; ババック・モグハッダム
Original assignee: Mitsubishi Electric Research Laboratories Inc
Current assignee: Mitsubishi Electric Research Laboratories Inc
Priority date: 2001-10-19
Filing date: 2002-10-18
Publication date: 2003-09-26
Also published as: US7986820B2; US20030076985A1

Abstract

(57)【要約】【課題】テストおよび基準画像から特徴を抽出して、
テストおよび参照レコードを作成する。【解決手段】各特徴は位置および方位を有し、さら
に、参照レコードの特徴は関連づけられた重みも有す
る。試験レコードの特徴を、参照レコードの特徴とほぼ
整列させる。そして、参照レコードの特徴の位置および
方位と試験レコードの特徴の位置および方位との相違を
測定し、試験レコードの特徴と比較したときに、所定の
相違未満である参照レコードの全ての特徴の重みを合計
して、試験レコードが参照レコードに整合する類似性ス
コアを求める。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、一般的に画像か
ら抽出された特徴を比較する方法に関し、特に、未知の
指紋を既知の指紋と比較する方法に関するものである。

【０００２】

【従来の技術】個人を識別するために、指紋の画像が日
常的に用いられている。人の指紋はそれぞれ一意である
ので、未知の指紋の画像をデータベースに記憶された既
知の指紋の画像と比較することができる。たとえば、Ｆ
ＢＩ公文書館の指紋のデータベースは、３０００万を超
えるテンプリント(ten-print）「カード」を有してい
る。データベースにおいて整合する指紋のセットが発見
されると、人の身元を検証することができる。人の指紋
を、氏名、別名、誕生日、身長、体重、髪の色、目の
色、人種などの付加的情報と共に記録し記憶するため
に、標準的な画像形式が採用されている。

【０００３】先行技術の指紋検証システムは通常、模様
の種類、隆線の形および方向などの、指紋の主要な特徴
を発見し、区分し、識別する技術を含む。隆線の形は、
人の指における隆線の流れの分岐と終端によって定めら
れる。これらの詳細は、コア、デルタ、渦状紋、ルー
プ、アーチ、テント状アーチなどを含む。詳細データ
は、それらの位置の（ｘ，ｙ）座標と配向度（ｑ）とを
含めることができる。

【０００４】よく知られたヘンリーシステムは、指紋識
別のために法施行当局によって用いられる、有力なマニ
ュアルシステムである。しかし、ヘンリーシステムは、
比較的少数の分類特性しか用いていない。そのため、識
別子コードの総数は、総合的データベースにおける数百
万の指紋を一意に説明するには小さすぎる。

【０００５】一般的に、指紋データベースを検索するた
めには、３種類の自動化された比較方法が用いられる。
第１の方法は、各指およびその方位が分かっている場合
の、テンプリント対テンプリント比較を用いる。この場
合に、指紋のセットは完全であり、画像の質はよい。通
常、第１の方法の結果は決定的である。第２の方法は、
潜在指紋対テンプリント比較を用いる。潜在指紋は、多
用な既知の技術を通してある任意の表面から「持ち上げ
る（lifted）」ことができる。テンプリント方法とは対
照的に、通常、潜在指紋は部分的であって質が悪い。ど
の指かも分からず、指の方位も分からないことが多い。
第３の方法は、潜在指紋対潜在指紋比較を用いて、２つ
の別々に採取された指紋が同一人に帰属するかどうかを
判断するが、人の正確な身元は分からない場合がある。

【０００６】一般的に、自動化された比較は、まず未知
の「テスト」指紋を既知または「基準」指紋と整列させ
ることにより行われる。そして、２つの指紋における比
較可能な詳細の、相対的な空間位置および角度位置が重
ね合わされ、評価され、２つの指紋に共通の詳細の数に
応じて採点される。この方法は、未知の指紋が全ての厳
密に整合する既知の指紋と比較されたときに完了する。
高いスコアは、共通の詳細が多いことと整合の見込みが
あることを示す。通常、整合するマニューシャが一対あ
る毎に、スコアは１だけ増加する。いくつかの典型的な
先行技術の照合方法が、米国商務省標準局（ＮＢＳ）Te
chnical Notes 538 and 878およびＮＢＳ Special Pub
lication 500-89に記載されている。

【０００７】先行技術の指紋比較システムは、テンプリ
ントセットの均一で高品質な画像のみで良好に動作す
る。しかし、潜在指紋の画像は部分的でありコントラス
トが低いことが多く、このシステムを信頼性も一貫性も
ないものにしてしまう。また、切り傷、擦り傷、擦過傷
や傷跡などの指紋のアーチファクトは、裂け目、アイラ
ンド（指紋の線の隙間）、短い枝分かれ、レークおよび
接合などの、「誤った」詳細につながり得る。誤った詳
細は、識別の失敗を引き起こし、オペレータの介入を余
儀なくして、コストを上昇させスループットを減少させ
る。

【０００８】Sasakawaらは、「Personal Verification
System with High Tolerance of Poor Quality Image
s」 SPIE Vol. 1386, Machine Vision Systems, pp. 26
5-272,1990において、指向性空間フィルタおよび局所的
閾値化などの画像強調技術を用いて詳細データを抽出す
る、指紋検証システム（ＦＶＳ）を説明している。同氏
らは、詳細データ用に粗いマッチングと密なマッチング
の両方を用いる。２００１年５月８日にSasakawaらに発
行された、米国特許第６，２２９，９２２号「Method a
nd Apparatus for Comparing Incoming Data with Regi
stered Data」も参照されたい。同氏らの類似性スコア
は、整合する詳細の数の正規化された整数カウントに基
づいている。同氏らの方法は、整合する全ての詳細を同
等に採点する。これは、特に、類似する詳細が互いに近
いところに置かれているときに、誤った容認および誤っ
た拒絶につながり得る。

【０００９】

【発明が解決しようとする課題】したがって、画像中の
特徴をより良好に識別することができる指紋比較方法に
対する必要性がある。

【００１０】

【課題を解決するための手段】本発明の方法によれば、
特徴をテストおよび基準画像から抽出して、テストおよ
び参照レコードを生成する。本発明の１つの応用におい
て、画像は指紋の画像であり、特徴は指紋の詳細であ
る。特徴の抽出前に、画像を強調することができる。多
数の参照レコードを指紋識別用のデータベースに記憶す
ることができる。この場合に、試験レコードを参照レコ
ードのそれぞれと比較する。

【００１１】各特徴は位置および方位を有し、さらに、
参照レコードの特徴は、予め計算された、関連づけられ
た重みも有する。まず、試験レコードの特徴を参照レコ
ードの特徴とほぼ整列させる。整列は、大域ＸＹ平行移
動および回転を用いた剛体変換とすることができる。

【００１２】そして、参照レコードの特徴の位置および
方位と試験レコードの特徴の位置および方位との相違を
測定する。試験レコードの特徴と比較したときに、所定
の相違よりも小さい参照レコードの全ての特徴の重みを
合計して、試験レコードが参照レコードに整合する類似
性スコアを求める。

【００１３】本発明の一態様において、特徴は確率密度
関数を用いて表し、座標変換は大域平行移動のみを用い
てレコードをほぼ整列させる。

【００１４】

【発明の実施の形態】方法の概要およびデータ構造

【００１５】図１は、試験レコード１０１の特徴を、デ
ータベース１５０に記憶された参照レコード１０２と比
較する方法１００を示している。特に、試験レコード１
０１は未知の指紋の詳細データを含み、参照レコード１
０２は既知の指紋の詳細データを含む。

【００１６】実用的な用途において、方法１００の目的
は、未知の指紋が既知の指紋の何れにどの程度類似して
いるかを判断することである。図１に示したように、本
発明による方法１００は３つの基本的ステップである、
特徴整列１１０、相違測定１２０および重みづけ１３０
を含み、試験レコード１０１に整合する可能性が最も高
い、採点された候補参照レコードのリスト１０３を作成
する。本発明は、前処理ステップにおいて参照レコード
の特徴について重み１３１も決定する１４０。

【００１７】図２に示すように、試験レコード（Ｔ）１
０１は、未知の指紋の特徴（詳細）２００をＭ個のベク
トル｛ｘ_ｊ，ｙ_ｊ，ｑ_ｊ｝^Ｍ _ｊ＝１として表す。たとえ
ば、ｊ番目の特徴２０１はその位置の座標ｘおよびｙ２
０２とその方位の方向ｑ２０３とを有し、ここでＭはレ
コード中における抽出された特徴の数であり、この例で
は２９である。同様に、データベース１５０に記憶され
た各参照レコード（Ｒ）１０２の特徴は、Ｎ個のベクト
ル｛ｘ_ｉ，ｙ_ｉ，ｑ_ｉ｝^Ｍ _ｉ＝１によって表される。試
験レコードおよび参照レコードにおける特徴の数は、同
一である必要はないことに留意されたい。

【００１８】以下でさらに詳細に説明するように、参照
レコードの特徴は予め計算された、関連づけられた重み
を有し、全ての特徴は確率的密度モデルによって表すこ
とができる。

【００１９】特徴２００は、従来の技術を用いて、実際
の指紋の画像または潜在指紋から抽出することができ
る。たとえば、共に参照することにより本明細書に一体
化した、Sasakawaらの「Personal Verification System
with High Tolerance of PoorQuality Images」 SPIE
Vol. 1386, Machine Vision Systems, pp. 265-272, 19
90および、２０００年５月８日に笹川氏らに発行され
た、米国特許第６，２２９，９２２号「Method and App
aratus for Comparing Incoming Data with Registered
Data」を参照されたい。

【００２０】操作方法

【００２１】方法１００の操作中に、試験レコード１０
１を参照レコード１０２のそれぞれと比較して、可能性
の高い候補参照レコードのリスト１０３を作成する。ま
ず、試験レコードを各参照レコードと整列させる１１
０。整列は、大域ＸＹ平行移動および回転を含めること
ができる、剛体変換である。指紋画像は一般的に標準的
な大きさであるので、通常、スケーリングは必要ではな
い。

【００２２】整列１１０は、上記で参照したSasakawaの
隆線方向変位（ｄＸ，ｄＹ）を用いて、試験レコード１
０１の特徴の（ｘ，ｙ）成分を、各参照レコード１０２
の特徴と近似的に整列させることができる。

【００２３】そして、参照レコードＲにおける特徴の何
れかに整合する試験レコードＴにおけるＭ個の特徴の類
似性スコアＳを、総平均によって次のように求める。Ｓ（Ｔ，Ｒ）＝２／（Ｎ＋Ｍ）（整合の数）ｗこれは、Ｒについて展開すると次の式になる。

【００２４】

【数３】

【００２５】ここで、ｗは重みであり、ｆは試験レコー
ドの特徴および参照レコードの特徴のｘ、ｙおよびｑ成
分の間の相違を測定する関数である。関数ｆ（・）は、
整合がないことまたは整合があることを示す値｛０，
１｝を備えた離散的な階段関数、または整合の確率に基
づく範囲［０．１］における連続的な滑らかな関数とす
ることができる。

【００２６】特定の特徴の対について相違の全てが所定
の閾値未満である場合には、特徴は整合するとみなされ
る。たとえば、｜ｘ_ｊ−ｘ_ｉ｜≦Ｔ_Ｘ、かつ｜ｙ_ｊ−ｙ
_ｉ｜≦Ｔ_Ｙ、かつ｜ｑ_ｊ−ｑ_ｉ｜≦Ｔ_Ｑである。整合す
る特徴の数が多ければ、たとえば、類似性スコアＳ≧Ｔ
_ＭＡＸであれば、試験レコードは参照レコードに整合す
る可能性が高い。整合する特徴の対に関する検索空間
は、ｘ、ｙおよびｑの値により近似的に整列される特徴
の対のみに制限することができることに留意されたい。

【００２７】関連性の重み

【００２８】識別を改善するために、各参照レコード１
０２について関連性の重みｗ_ｉ１３１のセットを設け
る。先行技術とは異なり、特定のセットにおける重みは
必ずしも等しくはない。これは、類似性スコアに寄与す
るときに、全ての特徴が同等に採点されるわけではない
という仮定に基づく。

【００２９】この考えを説明するために、図３Ａおよび
図３Ｂに示した特徴１〜２９を検討する。図３Ａにおい
て、試験レコード３０１からの５個の容認可能な整合
（１６、１９、２２、２４、２６）は開いた円で示され
ており、他の全ての特徴は閉じた円で示されている。同
様に、図３Ｂは、やはりちょうど５個の整合（１、２、
４、６、２１）があるが、ここでは参照レコード３０２
における異なった特徴に対する整合である場合を示して
いる。問題は、これら２つの整合が共に同一の類似性ス
コア値５を有しているとすると、これらの何れがより信
頼性があるか、またはより重要であるかということであ
る。

【００３０】図３Ａにおける整合は、類似の方位を有す
る特徴が密に集められた領域３１０からのものである。
これは、これらの領域における整合が、数個の隣接する
特徴からの「支持（support）」を有していることを意
味し、これらの全てが試験レコードにおける観察された
データを部分的に「説明（explain）」するので、それ
らの持ち分を類似性スコアに提供することができる。

【００３１】一方、図３Ｂにおいて、特徴１および２の
整合は、偶発的な整列の可能性が低い比較的「孤立した
（isolated）」領域３２０にある。同様に、特徴６に対
する整合は、その最も近い隣接する特徴４が完全に逆の
方位を有しているので、可能性が低い。同様に、特徴２
１は逆の方位の特徴によって囲まれており、そのためや
はり「孤立している」。

【００３２】したがって、一意のまたは「孤立した」特
徴の対は整合することがより困難であり、孤立した特徴
の対について容認可能な整合が発見されたときは常に、
部分的に重なる多数の周囲の特徴によって整合が「説
明」できるときよりも、類似性スコアは多くカウントさ
れるべきであると断定できる。これにより、本発明は、
特徴の重みｗ_ｉを、その最も近い隣接する特徴に対する
その一意性または距離に比例させる。

【００３３】したがって、本発明は、局所的近傍のｋ個
の最も近い隣接する特徴を識別し、これらｋ個の距離の
関数に比例する重みを次のように設定する。

【００３４】

【数４】

【００３５】ここで、ｄ^ｎ _ｉは特徴ｉのｎ番目の距離で
ある。これらの重みは合計してＮになるように正規化さ
れることに留意されたい。

【００３６】相加平均

【００３７】

【数５】

【００３８】相乗平均

【００３９】

【数６】

【００４０】および単にｄ^ｋである最大値Ｄ^２を含む、
任意の数の距離関数Ｄを用いて、特定の特徴からその隣
接する特徴までの距離を測定することができる。

【００４１】３つ全ての場合において、各参照レコード
における各特徴のｘ、ｙおよびｑ成分について距離を求
めて、対応する重みｗ_ｉ１３１のセットを導く。重みの
セットは、おそらくオフライン前処理ステップにおい
て、各参照レコードに対して１回判断する１４０必要が
あるだけである。完全な形にすると、参照レコード
（Ｒ）は、ベクトル｛ｘ_ｉ，ｙ_ｉ，ｑ_Ｉ，ｗ_ｉ｝^Ｎ _ｉ＝
１によって表せるであろう。特定の参照レコードにおけ
る重みｗ_ｉは、合計して１になるように正規化すること
ができる。したがって、２つの特徴の間に整合があると
きに、重みづけされた類似性スコアＳ１３２は、先行技
術における１の代わりに、対応する重みだけ増大され
る。

【００４２】確率的特徴のマッチング

【００４３】上記のように、整列ステップ１１０は平行
移動的または回転的な剛体変換を行う。しかし、以下で
さらに詳細に説明するように、確率的モデルを用いるこ
とにより、整列はあまり正確でなくてもよくなり、回転
変換ステップをなくして、計算の数を減らすことができ
る。

【００４４】本発明の中核密度モデル（kernel density
model）によれば、次のように動径ガウス関数を用いて
参照レコードを構築する。

【００４５】

【数７】

【００４６】ここで、

【００４７】

【数８】

【００４８】関数ｆ（０；σ^２）は、分散σ^２を有する
標準的なゼロ平均ガウス関数である。たとえば、

【００４９】

【数９】

【００５０】ｑからｑ_ｉを控除する際に、０°および３
６０°での境界条件は適切に扱われ、たとえば、５°と
３５５°とは１０度離れているものとみなされるという
点を除いて、関数ｆ_ｑ（０；σ^２）もガウス関数であ
る。

【００５１】ここで、類似性スコアＳは次の式によって
求められる。

【００５２】

【数１０】

【００５３】これは、Ｐ_Ｒについて展開すると次の式に
なり、

【００５４】

【数１１】

【００５５】距離は、（ｘ，ｙ，ｑ）に関する個々のσ
項に基づいて、対数確率に類似の方法で求める。換言す
れば、特徴ｉとｊとの間の相互距離は、正規化された
（均衡された）Ｌ_ｐノルムによって次のように与えられ
る。

【００５６】

【数１２】

【００５７】ここで、ユークリッド計量について、ｐ＝
２である。

【００５８】方位ｑを減算する際に、境界条件および０
および３６０度での「ラップアラウンド（wrap-aroun
d）」は、やはり、Ｐ_Ｒにおける変形ガウス関数ｆ_ｑを
求める場合のように、適切に扱わなければならない。
（ｘ，ｙ，ｑ）における分散σ_ｗは、距離の独立した重
みづけを説明し、（ｘ，ｙ）とｑとの間の範囲の差を説
明するために必要とされる。

【００５９】図４Ａおよび図４Ｂは、２つの異なる条件
または「関連性」の仮定の下での「関連性」の重みづけ
を示している。図４Ａは、（ｘ，ｙ）は等しく重みづけ
されているが、方位の類似性の影響を無効にするために
σ_ｗｑを意図的に大きく設定した場合について、これら
の重みを垂直線として示している。これによって、特徴
の空間的形状、すなわち、（ｘ，ｙ）ｋ近傍構造のみを
考慮した重みのセットが得られる。たとえば、図４Ａに
おいて、特徴１および２は、それらの空間的孤立のため
に最大の重みを有し、特徴４および６は、それらの近接
性を所与とすると、比較的低い重みを有する。対照的に
図４Ｂは、方位の相違も包含しているσ _ｗ値のより均衡
したセットを示している。これをよく理解するために図
３Ａおよび図３Ｂを参照されたい。

【００６０】図４Ｂにおいては、特徴１および２はもは
や最大限の重みを有しておらず、その代わりに特徴６
が、その近接性において類似の方位の詳細がないという
事実により、最大の重みを有することに注目されたい。
これを、特徴６および４が共に、単にそれらのＸＹ近接
性のために重視されていない、図４ＡにおけるＸＹのみ
の重みづけスキームと比較されたい。パフォーマンスを
最適化する相対的なσ_ｗ値は、σ_ｗｑの中間値との妥協
である。本発明による方法のパフォーマンスを最適化し
た、上記全てのパラメータの適切な値を以下に示す。

【００６１】調整および結果

【００６２】最高のパフォーマンスのために、特定の用
途についていくつかのパラメータを「微調整」すること
ができる。展開Ｐ_Ｒに用いられる中核パラメータ、主に
ｘ、ｙ、ｑおよびｗの分散が第１に挙げられる。そし
て、誤り率の点から、ガウス混合についての最高のパフ
ォーマンスの中核パラメータおよび、空間（ＸＹのみ）
重みづけと結合された空間対方位の重みづけとの間の最
善の妥協点を選択できる。

【００６３】大域ＸＹ平行移動のみを用いた確率的照合
技術は、先行技術のSasakawaらの方法によって行われる
ような、コストがかかる密な整列検索が省かれているの
で、非常に少ない計算で、同じ誤った拒絶率について、
誤った容認誤り率を６分の１まで低減することができ
る。

【００６４】本発明を好適な実施形態の例を示すことに
より説明してきたが、本発明の趣旨および範囲内で、他
の様々な適合や変更を行えることが理解されるであろ
う。したがって、本発明の真の趣旨および範囲内に入る
ような、全てのかかる変形や変更を包含することが、併
記特許請求の範囲の目的である。

【図面の簡単な説明】

【図１】本発明による、画像の特徴を比較する方法の
ブロック図である。

【図２】抽出された特徴の位置および方位を示す図で
ある。

【図３Ａ】整列された特徴の図である。

【図３Ｂ】整列された特徴の図である。

【図４Ａ】本発明による重みづけされた特徴の図であ
る。

【図４Ｂ】本発明による重みづけされた特徴の図であ
る。

───────────────────────────────────────────────────── フロントページの続き (72)発明者ババック・モグハッダムアメリカ合衆国、マサチューセッツ州、ケンブリッジ、ビゲロー・ストリート 15、ナンバー５Ｆターム(参考） 5B043 BA02 GA02 5B075 ND06 QM05 5L096 BA15 HA07 JA11

Claims

【特許請求の範囲】

【請求項１】試験レコードの特徴を参照レコードの特
徴と比較する方法であって、各特徴は位置と方位とを有
しており、前記参照レコードの各特徴について重みを決定するステ
ップと、前記試験レコードの前記特徴を前記参照レコードの前記
特徴と整列させるステップと、前記参照レコードの前記特徴の位置および方位と前記試
験レコードの前記特徴の位置および方位との間の相違を
測定するステップと、前記試験レコードの前記特徴と比較したときに、所定の
相違よりも小さい前記参照レコードの全ての特徴の重み
を合計して、前記参照レコードの類似性スコアを求める
ステップとを含む試験レコードの特徴を参照レコードの
特徴と比較する方法。
【請求項２】前記試験レコードの前記特徴を複数の参
照レコードと比較して、複数の類似性スコアを求めるス
テップと、対応する類似性スコアが最大閾値よりも大きい場合に、
特定の参照レコードを候補参照レコードとして選択する
ステップとをさらに含む請求項１記載の試験レコードの
特徴を参照レコードの特徴と比較する方法。
【請求項３】指紋の画像から特徴を抽出するステップ
をさらに含む請求項１記載の試験レコードの特徴を参照
レコードの特徴と比較する方法。
【請求項４】前記整列させるステップは、大域的な平
行移動および回転を含む剛体変換である請求項１記載の
試験レコードの特徴を参照レコードの特徴と比較する方
法。
【請求項５】前記整列させるステップは、大域的な平
行移動のみを含み、前記試験レコードの前記特徴を前記
参照レコードの前記特徴とほぼ整列させる剛体変換であ
る請求項１記載の試験レコードの特徴を参照レコードの
特徴と比較する方法。
【請求項６】整合する特徴の確率は、ゼロ平均ガウス
関数ｆ（０；σ^２）によって表され、σ^２は前記ゼロ平
均ガウス関数の分散である請求項５記載の試験レコード
の特徴を参照レコードの特徴と比較する方法。
【請求項７】ほぼ整列された特徴の対の間のみにおけ
る相違を測定するステップをさらに含む請求項１記載の
試験レコードの特徴を参照レコードの特徴と比較する方
法。
【請求項８】前記決定するステップは、前記参照レコードにおける各特徴について、局所近傍の
特徴を識別するステップと、各特徴と前記局所近傍の特徴との間の距離の関数に比例
する各特徴の重みを設定するステップとを含む請求項１
記載の試験レコードの特徴を参照レコードの特徴と比較
する方法。
【請求項９】前記局所近傍における重みｗ_ｉおよびｋ
個の特徴に関する距離関数は、【数１】であり、ここで、ｄ^ｎ _ｉは特徴ｉのｎ番目の距離である
請求項８記載の試験レコードの特徴を参照レコードの特
徴と比較する方法。
【請求項１０】前記距離関数は、相加平均である請求
項８記載の試験レコードの特徴を参照レコードの特徴と
比較する方法。
【請求項１１】前記距離関数は、相乗平均である請求
項８記載の試験レコードの特徴を参照レコードの特徴と
比較する方法。
【請求項１２】前記距離関数は、最大距離である請求
項８記載の試験レコードの特徴を参照レコードの特徴と
比較する方法。
【請求項１３】前記参照レコードの前記特徴の重みの
合計は、１に正規化される請求項１記載の試験レコード
の特徴を参照レコードの特徴と比較する方法。
【請求項１４】Ｍ個の特徴の試験レコードＴおよびＮ
個の特徴の参照レコードＲに関する類似性スコアＳは、【数２】によって求められ、ここで、ｘおよびｙは特徴の位置を
表し、ｑは特徴の方位を表し、ｗは特徴の重みを表し、
ｆは差分関数である請求項６記載の試験レコードの特徴
を参照レコードの特徴と比較する方法。