JPH09508739A

JPH09508739A - 指紋一致装置

Info

Publication number: JPH09508739A
Application number: JP8513428A
Authority: JP
Inventors: エシェラ、モハメド・エイ; サンダース、ラッセル・イー
Original assignee: ロッキード・マーチン・コーポレーション
Priority date: 1994-10-12
Filing date: 1995-10-05
Publication date: 1997-09-02
Anticipated expiration: 2015-10-05
Also published as: WO1996012246A1; KR960706662A; DE69529210T2; EP0733240B1; DE69529210D1; CN1136848A; EP0733240A1; JP3065104B2; AU4002395A; US5613014A

Abstract

(57)【要約】電子計算機を用いて未知の指紋の組の指紋のデジタル化された指紋の詳細点マップとメモリに記憶されている参照指紋の組の対応マップとを比較して未知の指紋を特定または一致させる。一致はすべての指紋を特性関連図（ＡＲＧ）に変換することによって実行する。ＡＲＧはノード及び枝を含み、それらに対し特性が追加される。比較予定の各指紋ごとに距離マトリクスが発生され、その要素は星の類似点となる。最高のランクの星対が比較の木の開始点として選択され、それによって一致コアを一致星を表す要素に満たすことが試みられる。比較は各星のノード及び枝の様々な特性に基づく。星の最大一致数が各指紋の組内で一致すると、次の参照指紋が未知の指紋と比較されるが、それはすべての関連する参照指紋が比較されるまで行われる。一致コア内の要素の数は各参照指紋に対する未知のものの一致の程度を表す。

Description

【発明の詳細な説明】指紋一致装置発明の分野本願発明は指紋の同一性の確認あるいは他の個人的特徴の適合に関し、特に、一組の指紋を多くの指紋を含む参照ファイルと適合させ、２または３以上の指紋の型が同一の指または異なる指であるかを確認することに関する。従来技術パターン一致または比較方法には、製造工程における機械部品の同一性の確認や郵便分類の段階におけるアドレスの読取りのような多くの応用がある。上述の応用は、機械部品の場合には異なる部品の数は限られており、それらの形状は一般的に単純であるので、簡単な比較の利用に入る。つまり、機械印刷の置換え数は膨大であるが同一性の確認のための２６文字及び１０の数字のみを持つ。比較のより複雑な種類としては、画像が作られる条件が同一でない場合に、特に似ているが同一ではないようなものの間での識別がある。画像が生物標本である場合には画像の変わりやすさが非常に大きいときがある。画像一致の一面として同定のための対象物のレチナールパターンの一致のようなものがある。他の利用としては指紋をファイル指紋と比較することによる同一性の確認がある。指紋は情報の内容として非常に貴重なものである。指紋には主として２つの種類の情報が存在する。だい１には隆起線の流れ情報であり、第２には指紋の特定の特徴または詳細点である。ここでは、用語「詳細点」とは単数及び複数の両方を意味するものとして用いる。指紋はそれらの情報内容に基づいて個人を唯一なものとして特定する。情報は指紋における詳細点及びそれらの相対的形態上の関係によって表される。指紋の詳細点の数は指ごとに異なるが、平均的には指紋ごとに約８０から１５０までの間にある。指紋の内容には、非情に多くの記憶された指紋が国中の法律執行事務所に存在する。それらの指紋には既知の個人の指紋のファイルが含まれており、それらはインクが付いた指をカードの上で転がすことによって、逮捕に関連しまたは人物証明調査または入国審査書類を得るための人物証明等の他の理由のために作られたもので、また、それはさまざまな方法により犯罪現場から採取された肉眼では見えないような犯罪現場の指紋の写しも含む。それらの参考指紋は不完全になりやすいが、それはインク過剰のように指紋の谷間をふさいでしまうことがある場合や、インク不足のように隆起の終端が不鮮明になる場合であり、また、同一の指紋の像の異なる領域内にインク過剰やインク不足の両方ともが生じることがある。指が望ましくない動きをしたり、指を転がす際にその指に加える圧力が均一ではない場合には、指紋の別々の位置において輪郭が不鮮明になったりにじんだりすることがある。保管されている指紋はまた保管されている間に劣化することがあり、それは例えば古い画像の色があせたりしみがついたりするために生じることがある。さらに、指紋を取る作業のあいだの経験の程度に大きな差がありまた指紋を得るときの条件により、指紋の画像の質に大きな差が生じる。同様な状況が実際の指紋の走査の際の走査装置の違いによっても生じる。多くの現在の装置における指紋の一致は大部分を全体的な登録点のようにコアおよびデルタを比較することに基づいており、それは上述の歪みや変化の多くの要因により比較に誤差を生じさせることがあり、それらのほとんどは、通常、遭遇することがあるようなさまざまな別々のインキ塗布、保管および予備処理条件により生じる。１９９１年にエルスバイヤー(Elsevier)によって発行されたヘンリー・シー・リー(Henry C．Lee)およびアール・イー・ゲステン(Guessten)の「指紋技術の進歩」(Advances in Fingerprint Technology)の１６４乃至１９１頁に説明されているように、手による調査は参照ファイルが非常に膨大であるためもはや不可能であるので指紋の同定の自動化の努力が長い間にわたって行われている。そのような指紋の同定の努力には２つの別々の分野が含まれる。つまり、(a)指紋走査および詳細点同定の分野および(b)一致する指紋を特定するために別々指紋に関する詳細点のリストの比較である。参照指紋の膨大なファイルが走査され、それからデジタル型の詳細点ファイルが得られるが、それらは完全な自動機械または人間の補助を必要とする半自動機械を用いて行われる。指紋の走査および詳細点の検出におけるすべての問題が解消されたというわけではないが一致に関する問題はより強調されるものであると思われる。適合または調査のサブシステムはいずれかの自動化された指紋特定装置(Autom ated Fingerprint Identification System)(AFIS)の最も重要な構成要素を備える。その作動は装置全体の適合の信頼性（データベースに存在するときには正しい一致を立証する可能性）、適合選択性（各調査の試みにおいて立証された誤り候補の平均数）および膨大なデータベース装置においては特に十分な処理数を確立する。指紋の唯一の特定は通常各指紋に含まれた１組の詳細点を用いて実行される。各指紋に対しそれらの詳細点は詳細点マップを形成する。図１ａは標準規格および技術国立機関(National Institute of standards and Technology)(NIST)のデータベース４から得た紙にインクをつける手続きによって現れた特定の概略化した指紋の表示を表しており、図１ｂは同一の概略化した指紋であるが、潜在的な表示において不足インキおよびしみにより現されたものである。図１ａおよび１ｂの表示が作られたように異なる条件の結果、図１ａおよび１ｂにおいて点で表された詳細点の少なくともいくつかのものは異なり、さらに、異なる位置に配置されている。このような相違により、適合方法は、過度の数の誤りの決定を発生させないように、未知のまたは調査の指紋と参照指紋とを確実に特定しなければならないときにはとくに確固たるものでなければならないことは明らかである。改良された調査または適合装置が望まれており、それは高い信頼性のある適合、低い適合選択性および多数のデータベースの内容における高い装置処理量を提供しなければならない。発明の概要指紋のような像は参考指紋と比較されるが、それは、第１に、参考指紋のファイルを発生し、その参考指紋をデジタル化して参考指紋のデジタル表示を発生させ、そして、その情報をデジタルメモリ、例えば、読取り専用メモリ、磁気テープ等のようなものに記憶する。そのようなファイルはすでに存在し、ＦＢＩのような機関によって維持されまた更新されている。デジタル化された参照指紋データは電子計算処理装置によって特性関連図（ＡＲＧ）の態様に変換されるが、その図は(a)ノードおよびノード特性並びに (b)ノード間の枝および枝特性を含んでおり、それらは参照指紋の組の抽出されたデジタル詳細点マップから導き出される。特性関連図は詳細点の位置および方向性のような形態情報を含む様々なノードおよび枝特性を含む。１組の未特定の指紋（その組は１つだけの指紋を含むことができる）を特定するためにはその組の未特定の指紋は保管されている参照指紋の組と比較する必要がある。この場合、１組の指紋に適用されている用語「未特定」はその指紋が未特定の者からのものであることを意味する必要はなく、それより、それらの指紋が参照指紋と一致しなかったことを意味する。１組の未特定の指紋の比較は、まず、未特定の指紋の組の各指紋の特性関連図を発生することにより行い、その特性関連図の各々は (a)ノードおよびノード特性並びに(b)ノード間の枝および枝特性を含み、それらのすべては未特定の指紋の組の抽出されたデジタル詳細点マップから導き出されるが、それは最初に参照指紋ファイルに対し行われたものである。特性関連図の発生は各ノードの中心に暗に星を発生させる。星は中心ノードと、その中心ノードに直接に結合された枝であるその中心ノードの枝と、その枝の端部にある枝とを含む。未特定の指紋の組の特定つまり比較における第２の段階は、電子計算処理装置を用いて、(a)未知の指紋の組の指紋の１つのＡＲＧ内の星と、(b)参照指紋の組の１つの中の指紋の１つのＡＲＧの星との間の距離マトリクスを発生する。その距離マトリクスは比較予定の各対に関連するマトリクス要素を含む。本願発明の望ましい実施例においては、距離マトリクスの要素はその要素の値にしたがって各指紋対ごとに記憶されて星対適合の順序を確立する。一貫した星対の適合コアが、比較予定の各指紋ごとに距離マトリクスおよびＡＲＧを用いて発生される。望ましい実施例においては、適合コアの発生は記憶された距離マトリクスによって確立された順序で実行される。比較予定の各指紋対ごとに、適合コアは、適合コアと一致する星対が追加できなくなるまで、適合コア内に含まれた星対と一致する星を追加することによって拡大される。これは、比較予定の指紋の間には一致がないので発生することがあるが、それは指紋対の得られるすべての星対は一致してしまっているからであり、または、一致した星対の所定の制限数に到達してしまっているからである。未特定の指紋を参考ファイルの各指紋と連続的に比較する手続きは繰り返される。調査を付帯的な知識、例えば、特定の指の確定（例えば人差し指）または手（左または右）によって簡略化することができるときには、調査つまり比較は参照指紋ファイルの対応指紋に限定することができる。最も高い得点を持つ一致コアは、未特定指紋と参照指紋ファイルの指紋との間の最も近い対一致を確定する。本願発明に係る方法の別の面によると、特性関連図を発生する工程が、(a)ＡＲＧの特定のノードを抽出デジタル詳細点マップの各詳細点に割当てる工程と、 (b)ＡＲＧの特定のノードにその対応する詳細点の位置を割当てる工程と、(c)ＡＲＧの特定のノードにその対応する詳細点の方向に割当てる工程と、(d)特定ノードの方向によって確立されたように、特定ノードと、特定ノードの周りの四分円の各々内の最も近い他のノードとの間に枝を構成し、「最も近い」ことはノード間のユークリッド距離によって決定される工程と、(e)枝に、ユークリッド距離(i)および他のノードが存在する四分円(ii)の少なくとも特性を割当てる工程とを含む。本願発明のある面によると、距離マトリクスの計算を実行する工程が、詳細点の対の間のユークリッド距離を決定する工程と、詳細点の対の間のユークリッド距離を前記対の詳細点の間の局部的隆起幅の平均値で割って各対ごとに標準化した隆起幅距離を発生し、これにより、形態上の関連リストが標準化した隆起幅距離を含む工程とを備える。本願発明の別の面によると、詳細点の種類及び局部隆起幅のいずれか一方または両方が特性関連図のノードに割当てられる。特性関連図の枝は隆起数、標準化隆起幅及び又は「同一隆起」特性の特性に割当てられる。本願発明によると、距離マトリクスの発生は２つの工程によって実行される。その内の１つは、未知及び参照指紋のＡＲＧ表示の星の特性の値を比較する。それには、未知の指紋の星の各枝と参照指紋の星の各枝との比較を含む。枝の各対ごとに点数を発生する。距離マトリクスの要素の発生に関する第２の工程には、各星対語との枝対の点数の最大一致合計を計算する工程を含む。一致コアは以下の工程によって形成される。つまり、一致コアの第１の要素を特定する、最高の距離マトリクス要素に、関連した又は対応した星対を選択する工程と、そのような第１の要素を一致コアに追加する工程と、距離マトリクスから一致コアの第１の要素に関連する要素を削除して減少された距離マトリクスを発生する工程と、一致コアの第１の要素内の星対の中心ノードに隣接するノードに中心を置く星の候補対の中から候補星対を選択する工程であって、候補星対が、(a)一致コアと一致するとともに、(b)減少距離マトリクス内の最高の距離マトリクス要素に関連する一致コアに一致するすべての候補星対の中にあり、これにより、一致コアに対する第２の要素を発生する工程と、第２の要素を一致コアに別の要素として追加する工程と、減少距離マトリクスから一致コアに第２の要素として追加された候補星対に関連する距離マトリクスの要素の内の１つを削除して別の減少距離マトリクスを形成する工程と、別の星対を選択する工程、追加する工程、及び前記減少距離マトリクスから削除する工程を、少なくとも一致コアに一致する候補星対の残りがなくなるまで繰り返す工程とからなる。上述の通り、一致コア内の要素の所定数は、一致コアの別の発生を呈すると判断することができ、それは「不変性」と呼ばれ、さらにその数より大きな追加の要素が「不変性」と呼ばれる。一致コア内の要素の数が特定数より小さく、一致コアと一致する星対が残っていないときには、調査方法は「バックアップ」することができ、そして他の調査経路を試みることができ、それは、一致コアから最も新しく追加した要素を削除し、それにより、最後から２番目も、つまり他の要素が前記一致コアに追加された最後の要素となる。一致コアの要素に関連するいずれかの星の中心ノードの隣接ノードに中心を置く星の候補対の中から候他の星の候補対を選択する。その星の対は、(a)一致コアと一致するとともに、(b)減少距離マトリクス内の最高の距離マトリクス要素に関連する一致コアに一致するすべての候補星対の中にある。これにより一致コアに追加される一致コアに対する第２の候補要素を発生する。候補星対に関連する距離マトリクスの要素の内の１つを削除してさらに別の減少距離マトリクスを形成する。別の星対を選択する工程、追加する工程、及び減少距離マトリクスから削除する工程を、少なくとも一致コアに一致する候補星対の残りがなくなるまで繰り返す。図面の説明図１ａおよび１ｂは一本の指の簡略印刷像を表示したもので、合成詳細点に関する型の異なるインク条件の影響を図示する。図２は本願発明に係る指紋適合装置またはシステムの全体的な図で、画像操作、特徴抽出、参考情報のメモリへの記憶および一般的な目的でプログラムされまたは特定の目的の概観を図示する。図３ａは指紋の詳細点の特性関連図（ＡＲＧ）であり、図３ｂはノード特性ベクトルの可能性のあるビット構造の表現であり、図３ｃは枝特性ベクトルのビット構造の可能性のある表現である。図４ａは比較予定の２つの指紋の特性関連図からの一対の星を図示したもので、各星は中心ノード、その中心ノードからの枝および隣接ノードから作られている。図４ｂは指紋の一部を図示するもので、隆起の端部および隆起の分岐点の詳細点を示し、また、隣り合う詳細点間の隆起の数の測定も示す。図５ａ、５ｂ、５ｃおよび５ｄは、特定の詳細点を中心とする局所的座標系と、特定の指紋の詳細点の間から１つの詳細点まで適用される座標系の定義と、時計回りに回転した座標系を持つ図５ｂに似たファジー四分円定義と、反時計回りに回転した図５ｂに似たファシー四分円定義とを表す。図６ａおよび６ｂはともに本願発明に係る特定の指紋を他のものと一致させる方法の距離マトリクス発生部分を表す簡略化したフローチャートである。図７は本願発明に係る２つの指紋の類似点の決定の一致コア発生部分を表す簡略化したフローチャートである。図８ａおよび８ｂはともに図７の候補ノード選択の詳細点を示す簡略化したフローチャートを構成する。本願発明の説明図２では個人の指にインクをつけて転がすことによって得た指紋カード１０を光学スキャナ１２によって走査して、詳細点が特定できるような十分な精密なレベルで画像を表すデジタル信号を発生する。上述の通り、図示のスキャナを用いる代わりに実際のものの走査装置を用いて板の上に置かれた指の走査から直接にデジタル信号を発生することができる。ここで用いるように、本分が他のことを示さない場合には用語「指紋」または「指紋像」はインクを付けて転がす指を自動的にまたは手で走査することから、または実際の走査装置を通じて指紋を捕捉することから得たデジタル像を意味する。デジタル信号は従来の特徴抽出装置１４に供給され、その装置は詳細点の位置および方向性の少なくとも１つのリストを抽出し、また像の概略を生成することができる。詳細点の型や局部的な隆起の幅のような他の情報を抽出できることが望ましい。スケルトン（骨組）は指紋の型であり、そこではコントラストが強調されていて２値情報（１および０）のみが残っている。そのスケルトン化は光学的に、走査およびデジタル化によって実行することができ、または、像の走査によりグレースケールを表すデジタル情報を得ることができ、それに続いてデジタル情報は処理されてグレースケールを２値に圧縮することができる。そのスケルトンを特徴抽出装置で用いて、以下に述べるように、他の特性、つまり隆起数を抽出することができる。特徴抽出装置１４は調査プリントの詳細点リストをプロセッサ１６に接続する。プロセッサ１６は図３ａに関連して以下に説明するようにデジタル詳細点リストの特性関連図（ＡＲＧ）への変換を実行する。概略、ＡＲＧは指紋の型の記号的な表示であり、それはカード上の詳細点の位置、詳細点の方向およびその他の入手可能な特性のような関連情報を含む。像上の詳細点は、インクによる印影が作られるごとにまたは実際のものの走査が行われるごとに像の詳細点の位置は変わることがあるが、それは、例え同一の指であっても、カードウインドウ上の指の配置が変わるためであり、また、その配置が偶然にも同一であったとしても、指の転がしおよび指の圧力の変化により他の詳細点に対するいくつかの詳細点の位置が移動することがあるからである。未知のつまり調査指紋のＡＲＧは経路１８を経由してプロセッサ２０に接続される。この状況ではプロセッサ１６および２０は同一の汎用プロセッサを用いることができ、それらは所定時間のＡＲＧ発生ソフトウエア部分および他の時間の調査ソフトウエアを備え、またはそれらは各々が特定の機能のためにプログラムされている別々のハードウエア装置を備えることができる。メモリ２２はテープ記録、光学ディスクメモリ等のような電子的メモリを用いることができ、それには、未特定の指紋ＡＲＧに関連して上述したように作られた参照指紋情報の組の特性関連図表示が既に記憶されている。メモリは様々なロードされなければならないので、ラインによって図示した別のデータ経路２４は、調査が行われる前に、メモリ２２に参照指紋情報のＡＲＧ表示をプロセッサ１６から読み込ませる状態を示す。読取装置、２３で示すものはそれに結合された制御信号の命令の下で参照指紋に関連する情報を読み取る。本願発明に係る一致方法に用いる詳細点は概略２つの基本的な型、つまり、(a )隆起の結合点（分岐点）および(b)分岐または結合しない隆起の端部（隆起端部）であるが、それらの２種類の型には限定されない。各詳細点に関連して得なければならない詳細点情報は位置であり、それは概略Ｘ−Ｙデカルト座標(Cartesi an coordinates)で与えられるが、円または他の座標および方向で得ることもできる。詳細点の方向は上述のリーおよびゲンステンのテキスト(LeeGuenssten te xt)で定義されているが、概略隆起終端位置における隆起方向および分岐点脈絡の分岐の共通部分の方向とは反対の方向となるということができる。図２のメモリ２２に参照指紋特性関連図の情報が読み込まれ、プロセッサ１６が未知の指紋のＡＲＧを発生すると、ともにプロセッサ２０で入手できるようになって調査を行えることができるようになる。特定は、特定予定の指紋を連続して参照指紋メモリ内の各関連する指紋と比較することによって実行される。従って、一組を構成する２つの指紋が常に比較されている。つまり、未知のまたは調査指紋の１つと参照メモリからの指紋の１つとである。概略、各指紋対の比較は、未知の指紋のＡＲＧおよび参照指紋の１つのＡＲＧの両方に計算を行って距離マトリクスを発生することによって開始される。図２において、距離マトリクスの計算はプロセッサ２０のモジュール２６において実行される。プロセッサ２０はプログラムされた汎用コンピュータであってよく、その場合にはそれ自体が制御信号を生成し、それはメモリ２２からの読み出しのためにメモリ読取装置２３を制御し、またそれはそのなかの様々なモジュール２６、２８および３０を制御する。つまり、プロセッサ２０が専用プロセッサの場合には、それはそれらの様々な部分の作動の同期をとるためにタイムコントローラつまりシーケンサ３９を必要とする場合がある。距離マトリクスの計算は１つの指紋ＡＲＧの星と他の指紋ＡＲＧの星とを比較することによって、つまり、より詳しく述べると、未知の指紋の星と参照指紋の内の最新の１つのものの星とを比較することによって実行される。星は以下に定義する。距離マトリクスが図２のモジュール２６で実行されると、未知の指紋および参照指紋の特性関連図の各対の星に対する要素を持つマトリクスを得る。本願発明の望ましい実施においては、距離マトリクスはモジュール２６からブロック２８に結合され、それは距離マトリクスの要素の大きさまたは値に応じてそれらを分類することを表す。その分類はどの様な方法でも実行することができる。プロセッサ２０のブロック３０はグラフ一致モジュールを表しており、それは、星対ごとに一致星対の内から最も一致した組を作り上げるために、星対の一致の可能性のあるすべての組み合わせを試みる。実質的な一致を生成する見込みのない処理の量を減少させるために、最も似ている星対から開始するように、処理が望ましくは分類モジュール２８で実行される分類によって確立される順番でグラフ一致モジュール３０において実行される。グラフ一致がモジュール３０で実行されると、一致の結果は値の形態で経路３２を経由して一時的記憶つまりメモリ３４に伝達され、そこでは、最も大きな数の一致した星対を含んだ少なくともそのグラフの値が、その一致に関連する参照指紋の同一性とともに記憶される。未知の指紋が参照指紋と比較され、その一致値が記録されると、次の参照指紋に関連する情報がメモリ２２から距離マトリクス発生装置２６に読み出され、一致手続きが再び開始される。そのシーケンスは、少なくとも一致がいくつかのしきい値基準によって確立されたときに発見されるまで、または関連する参照指紋の供給が終了するまで、継続される。記憶装置３４に記憶された情報は最も良い一致を表しており、つまり、１より多くの一致が記憶されたときに、一致の値または比較上の質を、一致が関連する参照指紋の同一性とともに表す。ブロック３６は記憶されたものの中から最も一致するものの選択を表し、ブロック４０は表示を表し、それには未知の指紋に最も一致した少なくともその参照指紋の組の同一性が表示される。図３ａは指紋の簡略化した特性関連図を示す。図３ａにおいては円または楕円はノード（結節点）を示しており、それらの各々は抽出された指紋情報の１つの詳細点と関連する。１つのその様なノードを３１０で示し、また隣接するノードを３１２で示す。各ノードは以下に説明するように星の中心ノードである。線つまり「枝」３１４はノード３１０と３１２との間に延在し、互いに関連付けられ、つまり、２つのノード形態的関係を「表示」する。図３ａの各ノードはそれから延びる複数の枝を持つが、単一のノードに関連する枝の最小数は１である。「星」は選択された中心ノードと、そこで終端する枝と、それらの枝の他方の端部にある「隣接」ノードとからなる。つまり、ノード３１０が星の中心ノードとして選択されると星全体は中心ノード３１０と、枝３１４、３２４、３２６、３２８および３３０と、ノード３１２、３１６、３１８、３２０および３２２とからなる。用語「隣接」はノード３１２、３１６、３１８、３２０および３２２が中心ノード３１０に関連するときにそれらに割り当てられる。図３ａにおいては、各ノードは詳細点の種類の図形表現に関連する。例えば、ノード３１０は３４０で示された図形に関連し、それは分岐点の形状であるが、ノード３１２は図形３４２に関連するが、それは隆起終端を表す。図形の方向は詳細点方向も示す。図３ａに図形で表現された詳細点の種類および詳細点の方向情報はノードに関連するデジタルワードにコード化される。図３ｂは図３ａのノードを特定するデジタルワードのフォーマットを表す。図３ｂにおいて、ワードの１８ビットはノードによって表された詳細点のＸ、Ｙ位置に関連し、１８ビットの次の組は詳細点の方向を表し、さらに次の８ビットは詳細点に限定する隆起の幅を特定し（得られる場合には）、１または２以上のさらに別なビットは詳細点の種類を示すために割り当てられる（得られる場合には）。実際には１ビットだけが２つの上記の特定された詳細点の種類を明確にするために必要とされるが、追加のビットを得てその様な詳細が得られる場合には追加の情報に関連する情報をコード化する。図３ｃは枝特性または特定ごとのビット割り当てを示す。図３ｃにおいて、８ビットは枝が終端する２つのノードの各々を特定するもので合計で１６ビットである。４つの追加のビットはノードによって表された２つの詳細点の間の隆起数を特定する。８つの追加ビットは「ファジー四分円割当て」のために用いられ、４ビットは四分円内の端部ノードの第１のノードの位置を特定するもので、それは第２ノードの詳細点の方向に基づくものであり、また、追加の４ビットは四分円内の端部ノードの第２のノードの位置を特定するものであり、それは第１ノードの詳細点の方向に基づくものである。４ビットが四分円を特定するために必要とする理由は特定四分円は「ファジー」だからであり、基本的四分円は特定されるからであり、また、その基本的四分円内の位置も３つの領域にさらに分割されて特定される。つまり、結果として、１２の可能性のあるファジー四分円割当てが存在することになる。隆起割当ては図３ａのワードにおいて２ビットを必要とする。その隆起割当ては、隣接する詳細点を表す２つの隣接ノード（同一の枝に結合されているもの）に対し、それらが同一の隆起の上に存在するか否かまたは異なる隆起の上に存在するか否かを確認する。同一の隆起の特性は図４ｂに関連して以下に説明する。図３ｃはここまでで説明を完了したので、枝ベクトルビットは図２のメモリ２２にＡＲＧの一部として記憶されることが予定されている。２つのさらに別の組のビットが図２の距離マトリクスモジュール２６で算出されるが、メモリ２２に記憶する必要はない。隣接するノードによって表された２つの詳細点の間にはユークリッド距離が存在し、それらの同一の詳細点の間には標準化した隆起幅の距離が存在する。ユークリッド距離は図３ｃのワードのビット割当て内の３２ビットのブロックであるが、標準化された隆起幅は３２ビットのブロックである。標準化された隆起幅の距離は隣り合うノードの２つの局部的隆起幅の合計の半分によって分割されるユークリッド距離である。指の隆起は均等に離れている必要はない。標準化された隆起幅の距離は、指の弾力性のために、指自体のおよび・またはインクによる印影の異なる隆起幅を修正する。図４ａは未知の指紋の特性関連図から星４１０を示すとともに、最新に比較された参照指紋のＡＲＧからの他の星４３０を示す。星４１０はＡＲＧ抽出装置１６から図２の距離マトリクス計算モジュール２６に最も新しく結合された未知の指紋のＡＲＧの星の中の星であると考えることができるが、星４３０は比較のためにメモリ２２から距離マトリクス計算モジュール２６に最も新しく結合された参照指紋のＡＲＧの星の中の星であると考えることができる。図４ａの星４１０の中心ノードは４１２で示されており、星４３０の中心ノードは４３２で示されている。比較予定の特定の組の指紋の第１の星に対しては、ノード方向はどの様な方向でも良い、つまり３６０度の回転方向とすることができると推測される。実際的な問題としては指はインクがつけられて転がされるときにはカード上を概略同一方向を向き、潜在的な指紋でさえも望ましい方向を持つので、調査しなければならない角度的位置の範囲を限定することができる。特に、詳細点の方向の一致を、像の６０度の時計回りおよび反時計回りへの回転に相当する１２０度内に限定して十分であると思われる。一致の限定を３６１度に変更すると、試験は処理から本質的に排除され、それにより、すべての可能性のある回転に対する処理となり、その結果、一致工程における回転上の不変性を保護することができ、それにより、印影の相対的な回転量にもかかわらず一致を発生することができる。指紋のその組の星の特定の対（１つの未知の指紋と１つの参照指紋）に対する図２のプロセッサ２６における距離マトリクスの発生の第１工程は処理を開始するもので、図６のフローチャートの開始ブロック６１０によって示されているように、未知の指紋のＡＲＧを局部メモリ（ブロック６１２）に読み込ませ、そして、参照指紋の第１のもののＡＲＧを読み取る（ブロック６１４）。ブロック６１４からは、図６の論理はブロック６１６に流れ、それは未知の指紋のＡＲＧ内のすべての星の組をＳＵにセットする状態を示す。図６ａおよび６ｂの論理は結局その指紋のＳＵのすべての要素に対し繰り返される。ブロック６１６からは論理は決定ブロック６１８に流れ、それはセットＳＵを検査してそれが要素を含んでいるかまたはそれが空であるかを決定する。セットＳＵが空のときには、距離マトリクス計算はその指紋に対しては終了し、論理は経路６２０を経由して図６ａおよび６ｂのフローチャートを離れ、図２の記憶モジュール２８に流れる。距離マトリクス計算が完了しなかったときには、しかし、論理はＮＯ経路を経由して決定ブロック６１８を離れ、ブロック６２２に到達する。ブロック６２２はセットＳＵからの星ｕの取り除きを示しており、それにより、それは参照指紋のすべての星と比較することができる。ブロック６２４は、ブロック６１６が未知の指紋の星に対し行ったとしても、他のセットＳＶに参照指紋のＡＲＧのすべての星を割当てる。ブロック６２４からは論理は決定ブロック６２６に流れ、それはセットＳＶを検査する。セットＳＶが空で、最新のｕが参照指紋のすべての星と比較されてしまうと、論理は論理経路６２８を経由して決定ブロック６１８に戻る。ＳＶが空でない場合には論理はＮＯ経路を経由して決定ブロック６２６を離れブロック６３０に流れ、それはｕとの比較のためにセットＳＶから星ｖの１つを取り除くことを示す。図６ａおよび６ｂのフローチャートの残りは星ｕと星ｖとの比較を示す。ブロック６３２はｕおよびｖの中心ノードをｕ_cおよびｖ_cとして特定することを示す。論理は連続して決定ブロック６３４、６３６および６３８を経由して流れ、それらは中心ノードの３つの可能性のある特性要因（ノード記載語に追加されるもの）を比較する。それらの要因の第１のものはノード方向と同様なもので（ブロック６３４）、第２のものは詳細点の種類と同様なもので（ブロック６３６）、また、第３のものは像内の指紋に関連する詳細点の位置と同様なものである（ブロック６３８）。星対の距離マトリクス要素値を評価する際における、要因の第１のもの、つまり、ノード方向の要因の決定は、しきい値とノード方向の間の違いの絶対値と比較することによる。それは以下の式にしたがってブロック６３４で実行される。ここで、しきい値Ｔ_θは上述の１２０度とすることができる。これによりｙｅｓ−ｎｏの結果を得ることができる。上述の通り、しきい値は回転の不安定性を保持するために３６１度にセットすることができる。その星対に対する距離マトリクス要素の値を評価する際に要因の第２のもの、つまり、詳細点の種類の類似性の要因の決定は、詳細点の種類の同一性を評価することである。詳細点４１２が種類４３２に等しいか？この比較は図６の決定ブロック６３６で実行され、ｙｅｓ−ｎｏの結果を得ることができる。詳細点の情報が得られない場合には、そのステップの結果は常にｙｅｓであり、それにより論理は常に次の論理ブロックに流れる。この星対の中心ノードに対する距離マトリクス要素値を評価する際に要因の第３のもの、つまり、像内の指紋に関連する詳細点の位置の類似性を決定することは、図４ａのノード４１２及び４３２の標準化された位置を評価することである。位置の標準化を実行するために像面内の指紋の位置を記録する。特に、その記録は詳細点の位置が像内で発生する位置であるＸ及びＹの最小値を確立するとともに、評価すべき各ノードの位置からそのＸ及びＹの最小値を引くことによって達成することができる。これは指紋を効果的に像内の同一の位置に配置する。図４ａのノード４１２及び４３２の位置が標準化されると、ノードの標準化された位置間の差の絶対値が図６のブロック６３８内のしきい値と比較される。像面に５１２のピクセルを持つ特定の実施例においてＸ及びＹの両方の約１５０ピクセルのしきい値が発見されて良好な結果を得ることができた。ＴX が像の幅より大きく設定され、さらにＴY が像の高さより大きく設定されると、変換上の不変性が保持され、ブロック６３８の応答が常にＹＥＳになる。その星対の距離マトリクス要素値を評価する際の要因の最初の３つの決定は値をその３つの決定の結果に割り当てることによって達成される。つまり、３つの条件のいずれも一致しないときにはゼロの値がその指紋対の星対の距離マトリクスの要素の値として割り当てられるが、すべての条件が一致するときにはどの値も割り当てられず、値を確立するためにさらに評価が実行される。決定ブロック６３４、６３６及び６３８によって確立されたすべての条件が一致することがない場合には論理はブロック６４０に達する。すべてのｖが評価されてしまっていないときにはブロック６４０は決定ブロック６２６に戻るように導かれ、それにより論理が評価のために他のｖを選択する。図４ａを参照すると、上述の３つの条件のすべてが一致した場合にはノード４１２及び４３２が中心となる星の比較が継続され、論理は決定ブロック６３８のＹＥＳ出力からノード６０２に流れ、それは図６ｂの論理につながる。図６ｂの論理はノード４１２及び４３２を中心とする星の比較を続け、それは、 (a)枝特性ベクトル及び(b)その枝の端部にあるノードの特性ベクトルを含み、ノード４１２から出る枝の各々のベクトルの組み合わせを、ノード４３２から出る枝特性ベクトル（及び関連するノード特性ベクトル）と連続的に比較することによって行う。最新の中心ノード u_cに結合されたすべての枝はブロック６４２内で１つのセットＢＲＵに結合される。決定ブロック６４４はセットＢＲＵを評価し、そのセットが空であるときには、ノード６０４の経路を経由して論理を図６ａの論理に戻す。セットＢＲＵが空でないときには論理はＮＯ経路を経由して決定ブロック６４４を離れ、ブロック６４６に達する。ブロック６４６は１つの枝ｂｕをさらに処理するためにセットＢＲＵから選択することとセットＢＲＵからのその取り除きを示す。また、ブロック６４６では、中心ノード u_cから選択枝ｂｕの他方の端部にあるノードが「隣接」ノード uN として示されている。ブロック６４８は参照指紋星のすべての枝のセットＢＲＶへの割り当てを示す。決定ブロック６５０はセットＢＲＶを検査し、その組が空のときには論理をブロック６４４に戻す。これは、セットＢＲＶ内のすべての枝がセットＢＲＶの最新の枝ｂｕと比較されたという事実を示す。セットＢＲＶが空でないときには論理はＮＯ経路を通ってブロック６５０を離れブロック６５２に到達する。ブロック６５２はｂｕと比較するための参照指紋の星ｖの枝ｂｖの選択とセットＢＲＶからの枝ｂｖの取りのぞきを示す。ブロック６５２は中心ノード v_cから選択枝の他方の端部にあるノードを「隣接」ノード vN と指定することを示す。図６ｂの論理の他の部分は参照星の最新の枝と未知の星の最新の枝ｂｕとの比較と、参照星の最新の隣接ノード vN と未知の星の最新の隣接ノード uN との比較を示す。枝及び隣接ノードの比較は例えば図４ａにおいて理解できるであろう。そこでは、比較はまず(a)枝４１４及び隣接ノード４１６を示す結合ベクトルと(b)枝４３４及び隣接ノード４３６を表す結合ベクトルとの間で行われる。その比較は５枝特性から行うことができ、それらは(1)隆起数特性、(2)ファジー四分円特性、(3)隆起割り当て特性、(4)ユークリッド距離特性及び(5)標準化された隆起幅距離特性であり、それらは図３ｃのワードで発見された情報の断片のすべてである。比較は隣接ノード特性、方向及び詳細点の種類の内の２つを用いて行うことができ、それらは図３ｂのワード内に見つけられるものである。それらの比較はより詳細に以下に説明する。隆起数特性を理解するためには図４ｂがスケルトン化した指紋の印影の簡略化した部分を図示している点に注目しなければならない。図４ｂにおいては複数の隆起４５０、４５２、４５４は２つの詳細点４５６及び４５８を分ける。詳細点４５６と４５８との間に延びる概念線つまりダッシュ線４６０はそれらの３つの隆起を横切るのでこの場合の隆起数は３である。２つの枝ｂｕ及びｂｖ（それぞれの星からのもの）の隆起数は等しいかまたは許容しきい値内になければならない。２つの枝ｂｕ及びｂｖの隆起数特性は図６ｂの決定ブロック６５４内で比較される。それらの２つの枝の隆起数が等しいかまたは許容基準内にあるときには図６ｂの論理はそのＹＥＳ出力を経てブロック６５４から別のブロック６５６に流れ、そこではファジー四分円が評価される。ファジー四分円の評価には局部的座標系の理解が必要である。図５ａ、５ｂ、５ｃ及び５ｄは局部的座標の理解を助ける。図５ａにおいては中心詳細点５１２が矢印５１４で示された詳細点方向を持つ。矢印５１４は第１の四分円つまり四分円I を二分割し、他の四分円II、III 及びIVを中心ノードの周りに反時計周りに順番に配置する。矢印５１４の方向は詳細点方向としてデジタル的にコード化され、ＡＲＧ内の詳細点に対応するノードに関連する特性の１つとなる。図５ｂにおいて、軸線５０２及び５０４はスケルトン化された指紋の印影の詳細点（黒点）と一致する位置で交差し、その詳細点の方向は線５０２及び５０４によって特定された第１(I)四分円を二分割する。図５ｂの座標系の０，０にある詳細点に関しては、第１、第２、第３及び第４四分円にある最も近い詳細点（それらが存在するときには）は隣接として定義する。必要な場合には、各四分円にある次に最も近い詳細点を隣接の定義に含めることができる。各四分円内の最も近い詳細点のみを隣接と定義するときには、特性関連図内の星の中心として選択されたノードの４つのノードより多くのものは存在しない。各四分円内の２つの最も近い詳細点を隣接として定義したときには各星の中心ノードの８つのノードより多くのものは存在することができず、各四分円内の３つの隣接詳細点に対し１２が隣接ノードの最大数となる。詳細点の方向を完全に確立できたとしても、指紋が転がると、一致した指紋の同一の詳細点は、未知及び参照指紋における図５ｂの軸線５０２及び５０４のような軸線の両側に落ちる。しかし、いくぶんか誤差なしで詳細点の方向を定義することは不可能であり、その上、四分円の境界の近くに落ちる詳細点は未知の及び参照印影のいずれかの側にも任意に落ちることができる。隣接詳細点が２つの指紋内の異なる四分円に落ちることとなるわずかな差異の存在において調査をより確固たるものにするために、「ファジー」四分円手段を用いる。その「ファジー」手段においては各隣接する詳細点またはノードは、特定の四分円内では「強く」ように定義され、２つの隣り合う四分円では「弱く」と定義される。図５ｃは図５ｂと同一の指紋の印影を持つが１５度だけ時計方向に回転された軸線５０２´及び５０４´を持つ。その結果、図５ｂの第１の四分円内にある詳細点５５０は図５ｃでは第２四分円内にあるが、図５ｂでは第４四分園内にある詳細点５５２は図５ｃの第１四分円内にある。他の四分円内にある他の詳細点は同様に隣の四分円に移動することがある。図５ｄは図５ｃに似ているが、元の位置から反時計方向に１５度回転された軸線５０２´´及び５０４´´を持つ。この結果当然ながらいくつかの詳細点は元占めていた四分円とは異なる四分円に移動することになる。ファジー四分円特性は１２に値付けられており、それら値の内の４つは基本四分円内で「強く」であり、それらの値のうちの他の８つは２つの相互に隣り合う四分円内で「弱く」である。ファジー四分円値の評価は中心ノードの各隣接する詳細点ごとに、それが上述の軸線の時計回り及び反時計回りのシフトにかかわらず四分円内に残るか否かに注目することによって達成される。つまり、それがそのように残るときにはその四分円に強く存在するというように言われる。満足するように見つけられた数字で表した値は、それぞれ、第１四分円に対しゼロ、第２四分円に対し３及び第３及び第４四分円に対し６及び９となる。図５ｃに示すように、軸線の時計回りのシフトの間に、隣り合う詳細点が異なる四分円に落ちるときには、元の四分円内では弱くなり、それが軸線の回転の結果として移動する四分円内では弱くなるように示される。特に、詳細点が四分円I から四分円II に、IIからIIIへ、IIIからIVへ、またはIVからI へ移動すると、１、４、７及び１０の値がそれぞれ割り当てられる。同様に、軸線の反時計回りのシフトに対しては、図５ｄに示すように、詳細点が四分円IIから四分円I に、IIIからI Iに、IVからIIIに、またはI からIVに移動するときには、２、５、８及び１１の値がそれぞれ割り当てられる。その値は４ビットにコード化され、図３ｃに示された８ビットの「ファジー四分円」ワード部分の一部における図１のメモリ２２に記憶される情報の一部となる。最も新たに評価されたノード対に関連する等しく重要な他の四分円が存在し、それは隣接ノードの座標系内の中心ノードのファジー四分円である。つまり、それは図３ｃの８ビットファジー四分円ワード部分の内の残りの４ビットに記憶されている。参照指紋の場合にはメモリから得られる情報を用い、未特定の四問の場合には新たに発生されたＡＲＧから得られる情報を用いることによって特定の星対に対するファジー四分円を評価するときには、４ビットファジー四分円値の両方を用いる。つまり、(a)中心ノード座標における隣り合うものの位置を特定するもの及び(b)隣接座標系における中心ノードの位置を特定するものである。最新に評価された２つの枝の間に関しては、１つの星の隣接ノードのファジー四分円は第２星のものの１つの数値内になければならない。そのことは２つの隣接する相対位置が２つの星内で似ていることを保証する。数の値０の「１内で」１１の数の値を作る必要性に適合するために、決定は１２を法とするように行われる。同様に、隣り合うノードに関する中心ノードのファジー四分円は１２を法とするように評価される。ファジー四分円の評価は図６ｂの論理流れの決定ブロック６５６内で実行される。枝ｂｕ及びｂｖの枝特性の評価における次の段階は図６ｂの決定ブロック６５８において実行され、そこでは隆起割り当てまたは「同一隆起」特性の比較の値が作られる。図４ｂを参照すると詳細点４５６及び４６２が同一の隆起４６４上にあるが詳細点４５６及び４５８は同一の隆起上にはない。２つの枝が３つの先行する評価に従って対応するときには図６ｂｎの論理はＹＥＳ経路を経て決定ブロック６５８を離れ決定ブロック６６０及び６６２に達し、そこでは、枝の対に関する比較予定の次の特性、つまり、ユークリッド距離特性及び標準化された隆起幅距離特性が評価される。それらは以下のように表される。ここで、α及びβは数字であり、それは１．２から１．３までの範囲の値に都合よく割り当てられたものである。その数字は可能性のある換算係数変数を表す。つまり、式は同一であるとみなされる指紋の場合においては詳細点間の距離が２つのプリントのように３０％より多くまでは変化しない。当然であるが適当なときには他の値も用いることができる。それはインク付着の変化およびまたは詳細点抽出変化に基づく詳細点の位置の変化に対する許容も提供する。図６ｂのブロック６５４乃至６６２における論理流れは絵だｂｕおよびｂｖの第１の対の評価を完了するが、関連する隣接ノード uN および vN の第１の対の評価ではない。枝自体が対応すると考えられる場合には関連するノードはブロック６６４、６６６および６６８においてそれらのノードの個々の方向および詳細点の種類を比較することによって評価される。詳細点の種類の比較は最初に決定ブロック６６４において行われる。データが入手できるときには詳細点の同一性が要求される。詳細点が同一であるときには、隣接ノードに関連する詳細点の方向が、２つの異なる方法における図６ｂの論理ブロック６６６および６６８による比較に結合される。中心ノードの方向の違いの比較を用いるときに関しては、隣接ノードの方向の違いに関する回転の制限は以下の式によって定義することができる。しきい値の値を３６１度に設定することは特にその基準を排除して、一致を回転の不変量とともに発見することができるようにする。その比較は図６ｂのブロック６６６内で行われる。他の方向制限は方向の違いの差の限定であり、それは回転の不変性と矛盾しない。そのテストはブロック６６８で実行され、以下の式によって定義される。その式は中心ノードの方向に対する隣接ノードの方向の向きを特定する。決定ブロック６５４−６６８（ここでハイフンは「乃至」を意味する）によって実行されたテストのいずれもが否定の場合には、論理は論理経路６７２の経路を通って決定ブロック６５０に戻るが、それは、ｂｕ及びｂｖの特性が対応しなかったから、または uN 及び vN の特性が一致しなかったからであり、また、他の対の枝及び隣接ノードが存在するときにはそれらを評価しなければならない。しかし、枝／隣接が、図６ｂの論理流れに説明されている比較のすべての限定に一致する場合には、それは図４ａの星４１０の枝４１４及び隣接ノード４１６が星４３０の枝４３４及び隣接ノード４３６に一致することと等価であるというように理解することができる。星４１０は未知の指紋からの星であり、星４３０は参照指紋からのものであるということを思い出すべきである。論理流れは図６ｂのブロック６６８からブロック６７０に進行し、それは枝対ｂｕ及びｂｖを星対ｕ及びｖに対する一致枝のＢで示されたセットに加える点を示す。それはその枝／隣接ノード対に対する評価を完了し、論理は決定ブロック６５０に戻って評価を継続する。この枝／隣接比較工程は最も新しく比較予定の星対の枝の各対ごとに実行される。従って、図４ａの星４１０における枝／隣接ノードベクトルの各々は星４３０の枝．隣接ノードのすべてと比較される。星４１０のいずれかの１つのまたはいくつかの枝／隣接ノードは星４３０のいずれか１つのまたはいくつかの枝／隣接ノードと一致することができる。結局、すべての枝／隣接ノードの一致が評価され、セットＢＲＵが空となり、そして、論理はそれからＵＥＳ経路を通って決定ブロック６４４を離れてノード６０４の経路を通って図６ａのフローチャートに戻る。図６ａにおいては、論理はノード６０４からブロック６７４に流れ、それはＢ、つまり、最も新しく比較予定の星対ｕ、ｖのすべての枝／隣接ノード対の評価によって導き出されたすべての枝／隣接ノードの一致の組（セット）から最高のまたは最大の一致した部分集合を選択することを示す。一致するためには、単一の枝／隣接ノードがその部分集合内の１対より多くの枝／隣接ノード内に現れることがないことが必要である。この一致の必要性により参照星内の２つの（または３以上）枝を未知の星の１つの枝に割り当てる、またはその逆のものに関する論理上の問題を排除することができる。その星対に対する距離マトリクスの要素の値はブロック６７４において以下のように設定される。ここで、ＭＣＳは枝／隣接ノード対のすべての一致した対の組の最高の一致部分集合である。従って、星対の星の一方の星の３つの唯一の枝／隣接ノードがその対の他方の星の３つの唯一の枝／隣接ノードに一致するときには、その星対に対する距離マトリクス要素の値は１プラス３または４である。論理ブロック６７４から論理流れは決定ブロック６２６に戻る。上述したように、未知指紋の１つの星は参照指紋の１つの星と比較された。距離マトリクス計算は未知のＡＲＧの各星を参照星のＡＲＧの各星と比較することが必要である。決定ブロック６１８及び６２６によって決定されたように、比較されていない星対が残る限り、論理はブロック６３０に戻って星対の評価を継続する。上述のステップがすべての星対に対し実行され、それにより距離マトリクスの要素に値を書き入れる。結局、評価されていない星対が使い果たされたときには論理はＹＥＳ経路によって決定ブロック６１８を離れて論理経路６２０によって図２のモジュールつまりブロック２８に進む。距離マトリクス内の要素の数は指紋対内で比較された星の数に従属する。つまり、既知の指紋における星の数がＭで、参照指紋の星の数がＮの場合には、距離マトリクスはＭ×Ｎの要素を含む。星の数は抽出された指紋の詳細点の数に等しいが、それは各星の中心ノードがＡＲＧ内のノードであり、各ノードが１つの詳細点に関連するからである。距離マトリクスの要素の決定の間には、情報の欠如のために所定のテストを排除するにとができ、これにより、所定の不変性を保持または比較工程を早める。詳細点の種類、局部的隆起幅、隆起数及びまたは隆起割当て情報は必要ではなく、また、省くことができる。距離マトリクスの要素が指紋の１対ごとに書き込まれると、図６ａ及び６ｂの論理によって表されているように、距離マトリクスの要素は図２のプロセッサ２０のモジュール２８に結合され、そして、論理流れが（つまりシーケンス３９が）分類プロセッサ２０の作動を開始する。プロセッサ２０は距離マトリクスの要素をそれらの値に応じてその指紋対に対して分類する。どの様な標準的な分類ルーチンであっても満足できるであろう。分類の結果は距離リストであり、そこでは要素寸法が表にされている。そのリストの発生は図７のフローチャート内のブロック７１０として示されている。図２の分類モジュール２０によって発生された距離リストは図一致モジュール３０まで通過する。図一致モジュール３０は分類された距離マトリクス要素リスト内の星対を開始点、つまり、ネットワークまたはセット（以下「部分図」と称す）内の星に対応する「位置」として得て、一致星のネットワークまたはセットを指紋対のすべての星を含む方向に拡張するようにする。当然ではあるが、参照及び未知のＡＲＧが同等数の星を持たない場合には、それらのすべては完全にはまた十分には一致できない。インク及び他の変化のために、２つの同一の指の印影のＡＲＧのすべての星が一致する必要はない。その結果、プロセッサ３０は図７のフローチャートに関連して説明したように、一致星対の最大の部分図を作るようにする。他の制限条件点を以下に説明する。指紋対の一致に関する部分図の発生の論理は星対（１つは未知のものからであり、１つは参照のものからである）を選択することによって開始し、それは以下に説明する基準に一致し、また、図７の論理ブロック７１０の出力に生成された距離マトリクスの要素の分類されたリストの中で、２以上のものが最高値を持つときには、その星対は最高値を持つ。最高値の星対（Ｕ１、Ｖ１）の選択は、図７において、最新の距離マトリクスの要素が存在するか否かを決定する決定ブロック７１２と他のブロック７１４の組み合わせによって示されている。その選択は最も一致しそうな対を、リンクされた星の部分図の構造に関する開始点として指定し、次に良好な結果を達成しそうにない処理を除くようにする。以下に説明するように、それらの最初の２つの星の特定ｕ、ｖはブロック７１４において「一致コア」と称され、また「Ｍ」として知られているセットに加えられ、対応が決定されている指紋の対の星対からなる部分図を説明するセットにすぎない。従って、一致コアは部分図の定義にすぎない。一致コアＭは従って最初はセット｛（ｕ１、ｖ１）｝にすぎない。星の第１の対は常に一致コアに加えられるが、後の星対が実際に一致する対応を形成し、それが、一致コアに関する１組の制限条件を一致させることによって確立されるときだけに、その後の星対が追加される。第１組の星の追加はブロック７１４に示されている。また、ブロック７１４は距離マトリクスの最新の値を距離マトリクスのスタックに「近付ける」。上述の通り、一致コアにおける包含のための最初の星の選択は所定の基準に一致しなければならない。その距離マトリクス値はしきい値を越えなければならない。本願発明の特定の実施例においては、しきい値は５である。加えて最初の星対の数はＫに限定され、それは図７のフローチャートが呼び出される回数を制限する効果を持つ。さまざまな値が試され、４の値がその後の利用に対して選択された。一致コアＭの最新の値または一致コアＳは以下のように定義される。Ｓ＝（Ｍ内の星対の数）＊（Ｍ内のすべての星対のすべての距離マトリクス値から得られた中央値）＋（Ｍ内のいずれかの星対の中の星の中心ノード間における未知の指紋のＡＲＧ内の枝の数）＋（Ｍ内のいずれかの星対の中の星の中心ノード間における参照指紋のＡＲＧ内の枝の数）ここで、＊は掛け算である。一致コアＭ´は、遠くで接近する一致スコアの最高値を持つ１つの一致コアを表す。最新のＭの一致スコアＳはＭ´の一致スコアＳ´と比較される。ＳがＳ´ より大きな場合には、Ｍ´はＭと置き換えられる。この比較は図７の決定ブロック７１６の組み合わせによって実行され、さらにブロック７１８はその置き換えを実行する。論理はその後別の決定ブロック７６０に達する。特定の指紋の比較は、一致コアに結び付けられる星の数が特定数に到達したときには完了すると考えられるが、それは、部分図内の星の数の一致は明白に指紋の適合対に一致するものと推測されるからである。図７の決定ブロック７６０は最新の一致コアの寸法を要素の選択されたしきい値数と比較する。都合よく用いられた数は１５である。従って、１５の星対が一致コアＭに追加されたときには、その一致はブロック７６０によって宣言される。当然ではあるが、１５以外のしきい数をその代わりに用いることができる。論理はそれからブロック７２０に流れる。第１要素が一致コアに加えられると、隣接対の候補リストが発生される。図７のブロック７２０は候補リストＣの発生を表す。候補リストを発生するためのブロック７２０の機能の詳細は図８ａ及び８ｂを参照しながら以下に説明する。ブロック７２０から論理は経路７２２によって決定ブロック７２４に流れ、それは候補リストＣがからであるかまたは依然として候補を含んでいるのか否かを決定するためにその候補リストＣを検査する。その候補リストがメンバーを含んでいる場合には、論理はＮＯ経路によって決定ブロック７２４を離れ、そしてブロック７２６に達する。図７のブロック７２６は最高の距離マトリクス値を持つＣから星対（ｕ´´、ｖ´´）を選択することと、それを候補リストＣから取り除くことを示す。論理はその糊ブロック７１４に戻り、そこで丁度ブロック７２６において選択された要素、つまり、最高値要素（ｕ´´、ｖ´´）を一致コアに加える。一致コアはここではセット｛（ｕ１、ｖ１）（ｕ２、ｖ２）｝である。残された候補対が存在する限り、論理流れは、ブロック７１６、７１８、７６０、７２０、７２４、７２６及び７１４を含み候補を各繰り返しごとに一致セットに追加する経路を循環する。その一致セットは｛（ｕ１、ｖ１）（ｕ２、ｖ２）．．．（ｕN 、ｖN ）｝である。一致コアに追加するための候補は非ゼロ距離マトリクス要素値を持ち、それらはブロック７２０において他の制限条件を通過させたので、以下に説明するように、その候補星対は常に一致コアに追加することができる。その結果、ブロック７２０、７２４、７２６及び７１４を含むループは候補が得られる限り動作し続けなければならない。結局、候補の供給が尽きた時には論理はＹＥＳの経路７２８を通ってブロック７２４を離れ、ブロック７３０に流れる。図７のブロック７３０は一致コアＭの最後に追加した要素（ｕN 、ｖN ）の取りのぞきを示す。それは「袋小路」経路が選ばれてしまったとき、つまり、所定の構成の一致コアまたは部分図をもはや拡大できないときの「後退」または「撤回」を意味する。一致コアの構造は、撤回をし新たな調査経路に進み、一致コア｛（ｕ１、ｖ１）（ｕ２、ｖ２）．．．（ｕ_N-1、ｖ_N-1）｝を開始することによって変えられる。一致コアが空のときには、調査が新たな星対をその基本として再度開始し、その次の星対は距離マトリクス内の第２の最高なものとして選択され、または２以上のものが同一の最高値を持つ場合には最高値の対の他のものとして選択される。ブロック７３０は、スタックのトップにある距離マトリクスをそのスタックから取り除く（動かす）ことによって最新の距離マトリクスとして選択する点も示す。新たな距離マトリクスにおいては、星対（ｕN 、ｖN ）の要素の値がゼロにセットされる。ブロック７３０から論理は決定ブロック７３２に流れ、そこは一致コアの内容を評価して一致コアが空か否かを見る。その一致コアは第１の要素のみがそこに含まれており、包含用の候補がもう発見されないときには空となることができる。図７のブロック７１４−７２６によって実行された調査が指紋内の一位した星対の選択された数を発見しないときには、そのコアは結局空となるが、それは、以下に説明する制限条件を受けるような、一致コア（ｕ１、ｖ１）に基づいて部分図の隣接星のすべての組み合わせを探求することを撤回したからである。一致コアＭが空の場合には、論理はＹＥＳ経路によってブロック７３２を離れ、経路７３４によってブロック７１２に戻るよう流れて他の星対用の論理を経由する他の経路を開始する。決定ブロック７１２によって確立されたように他の一致コアを開始することができる他の星対が存在する場合には、ブロック７１４は他の星対（ｕ１、´ｖ１´）を新たな一致コアの最初のメンバーとして選択する。一方、一致コアが空ではない場合には、論理は経路７３６によって決定ブロック７３２から戻ってブロック７２０に流れる。候補セットは、ブロック７２０内で削除された一致コアのために構成され、また、経路７２２及びブロック７２４、７３０、７３２を含む論理経路を横切ることによって、一致コアを再び拡張することを試みる。結局、Ｍ内の星対の数がブロック７６０に関連して説明した所定の最大数に近付くかまたは一致コアの最初のメンバーとして振る舞うことができる星対が残っていないかのいずれかとなる。最初の例においては、決定ブロック７６０が、論理がブロック７３８及び６１４を経由して図７のフローチャートを離れるようにするが、第２の例においては、決定ブロック７１２が、論理が経路７４０及び同一のブロック７３８、６１４を経由して離れるようにする。論理ブロック７３８は一致コアＭ´に対する一致コアＳ´を再計算する。このＳ´の値は図２のブロック３４に記憶されているものである。図７のブロック６１４は図６ａ内の同一のブロックに対応する次の参照指紋の選択を表す。図８ａ及び８ｂはともに図７の論理ブロック７２０内の論理流れを表すフローチャートを構成する。ブロック７２０の論理は、想起するであろうが、一致コア内に包含するための候補のリストＣ内に包含される星対を決定する目的のためのものである。図８ａ及び８ｂにおいては、論理は図７のブロック７６０からブロック８１０に到達する。ブロック８１０は隣接ノードに中心を置くすべての星のセットＸの選択を表しており、その隣接ノードはＭによって表された最新の部分図内の未知のプリントのＡＲＧの星の一部である。候補の星はすべて部分図のノードのすでに一部であるものの隣のものでなければならず、それは例えば１４星と同じ数のものを含むことができる。ブロック８１０によって生成されたセットＸはすべてその様な星を含む。論理ブロック８１０から論理は決定ブロック８１２に流れ、そこではＸ内の要素の数を検査する。Ｘが空の場合にはＣつまり候補の星対のセットの発生が完了し、決定ブロック８１２が論理をノード７０１を経由して図７のブロック７２４に向ける。Ｘが空でない限り、星ｕ´はセットＸから取り除くことができ、論理はＮＯ経路によって決定ブロック８１２を離れてブロック８１４に達し、そこでは、星ｕ´がセットＸから取り除かれる。ブロック８１４から論理はブロック８１６に流れ、そこでは隣接するノードに中心を置くすべての星のセットＹの選択を表しており、その隣接ノードはＭによって表された最新の部分図内の参照プリントのＡＲＧの星の一部である。候補の星はすべて部分図のノードのすでに一部であるものの隣のものでなければならず、それは例えば１４星と同じ数のものを含むことができる。ブロック８１６によって生成されたセットＹはすべてその様な星を含む。論理ブロック８１６から論理は決定ブロック８１８に流れ、そこではＹ内の要素の数を検査する。Ｙが空の場合にはＣの発生は完了し、論理流れはブロック８１２に戻る。Ｙが空でない限り、星ｖ´はセットＹから取り除くことができ、論理はＮＯ経路によって決定ブロック８１８を離れてブロック８２０に達し、そこでは、星ｖ´がセットＹから取り除かれる。テストが図８ａ及び８ｂのフローチャートの残りにおいて実行されて、星対（ｕ´、ｖ´）を候補の星対のセットＣに加えることができるか否かを決定する。特に、決定ブロック８２２及び８２４は、それぞれ、（ｕ´、ｖ´）がすでに一致コア内にあるか否か及び（ｕ´、ｖ´）用の距離マトリクスがゼロに等しいか否かを決定する。それぞれの条件の双方が否の場合には、論理はノード８０１を通って図８ｂに流れる。いずれかの条件が一致した場合には、（ｕ´、ｖ´）はセットＣに追加することはできず、論理はブロック８１８に戻って他の星対を検査する。図８ｂのノード８０１から論理はブロック８２６に流れ、そこでは、ｕ´がｕの隣接で、ｖ´がｖの隣接となるように、一致コアＭ内のすべての星対（ｕ、ｖ）のセットをゼロに一致させる点を示す。決定ブロック８２８はＺを検査し、Ｚが空でない場合には論理流れをブロック８３０に向ける。ブロック８３０はＺから１つの（ｕ、ｖ）を取り除くことを示す。決定ブロック８３２は、ｕ´の座標系に関するｕの四分円がｖ´の座標に関するｖの四分円の１つ（１２を法とする）内に存在するか否かを決定する。決定ブロック８３２は、ｕに関連するｕ´の四分円の値がＶの座標に関するｖ´の四分円の１つ（１２を法とする）内に存在するか否かも決定する。それらの両方の条件が満たされると、論理流れは決定ブロック８３４に行く。決定ブロック８３４は、ｕからｕ´までの隆起数がｖからｖ´までの隆起数に等しいかまたはその許容範囲内にあることを保証する。その条件が満たされると、論理は決定ブロック８３６に流れる。ブロック８３６はｕ及びｕ´の並びにｖ及びｖ´の隆起の割当てが同一であるか否かを決定する。その条件が一致すると、論理流れは経路８３８によって決定ブロック８２８に戻る。ブロック８２８−８３６及び経路８３８を含むループはＺ内のすべての星対に関する可能性のある候補の星対（ｕ´、ｖ´）を評価する。ブロック８３２、８３４及び８３６によって確立された条件のいずれ化が否である場合には、星対（ｕ´、ｖ´）は候補セットＣに入ることはできず、論理流れはノード８０３を経由して図８ａのブロック８１８に戻る。すべての要素Ｚが決定ブロック８２８−８３６によって評価されたときには、論理はブロック８２８を離れて経路８４０を経由してブロック８４２に流れ、そこでセットＭに等しいセットＡを作ることを示す。これにより、一致コアＭ内の各星対を可能性のある候補の星対（ｕ´、ｖ´）に関連して評価することができる。ブロック８４２から論理は決定ブロック８４４に流れ、それはＡを評価する。要素がＡに残っている場合には、論理はブロック８４６に流れ、そこで後続の決定ブロック内で用いるためにＡから星対（ｕ、ｖ）を取り除くことを示す。決定ブロック８４８、８５０及び８５２は可能性のある候補の星対（ｕ´、ｖ´）を用いて星対（ｕ、ｖ）を評価する。決定ブロック８４８は詳細点の方向の違いの差を評価する。その値が許容範囲内にある場合には論理流れは決定ブロック８５０に進む。決定ブロック８５０及び８５２はユークリッド距離と標準化された隆起幅の距離とを比較するが、その際の方法は図６ｂのブロック６６０及び６６２に関連して説明したものと似たものである。いずれかの条件が否の場合には、論理流れはノード８０３を経由して図８ａのブロック８１８に戻り、星対（ｕ´、ｖ´）は候補セットＣに追加されない。一方、決定ブロック８４８、８５０及び８５２によって確立された条件が一致する場合には、論理流れは決定ブロック８４４に戻る。ブロック８４４− ８５２を含むループはセットＡ内のすべての星対に対する繰り返しを示す。セットＡが空になったときには、（ｕ´、ｖ´）は一致コアＭ内のすべての星対と都合よく繰り返された。論理流れはその後ＹＥＳ経路を経て決定ブロック８４４に戻り、ブロック８５４に達する。ブロック８５４は（ｕ´、ｖ´）を候補セットＣに追加する。ブロック８５４から論理はノード８０３を経由して図８ｂのフローチャートを離れ、図８ａの決定ブロック８１８に戻って他の可能性のある候補星対をテストする。要約すると、本願の装置は指紋の詳細点マップ及び相対的形態情報を特性関連図の形状で捕捉するものである。その指紋マップの情報の内容は、１１０から１３０までの詳細点を含む詳細点マップに対し２、０００バイトより少ないものを用いて非常にコンパクトな形態で記憶される。調査は指紋のＡＲＧ表示の部分図の不正確な一致に基づいて実行される。その調査はＡＲＧ表現の部分図を一致させるために帰納的に決定された「高性能の」方法を用いるので、それは効率的である。その技術は、一致した詳細点の部分集合をそれらに対応する形態上の関連とともに特定することによって、詳細点マップ内で得られる情報を通じてじゃまなものを取り除く。その調査の方法は回転、移行、比例及び変形不変性であり、それにより、それは、ノイズ、変形及びしみや汚れや部分的な疑似情報のような不確実な様々な主るのものが原因となるような品質不良の指紋に対抗することができる。説明した装置の特定の利点は従来の装置のような全体的な座標は必要なく、コア及びデルタのような指紋全体の特性の検出は必要がない点にある。本願発明に係る装置は予備的な形状で市販の在庫ハードウエア、標準的なＵＮＩＸワークステーションで実行される「Ｃ」高レベルプログラム言語によって組み立てられている。９６％の一致の正確さが、ＮＩＳＴスペシャルデータベース４内のすべての親指、すべての人差し指及びすべての中指の指紋に関して達成できた。本願発明の他の実施例は当業者には明白であろう。例えば、未知の及び参照指紋の比較を実行する電子計算装置は参照指紋が記憶されたメモリから離れた距離にあり、データをデジタルデータ経路を介してそれらの間で送信することができる。参照指紋はＡＲＧ形態で、または画像形態で電子メモリに記憶することができ、その場合には、ＡＲＧ形態への変換は比較の前に参照指紋に対し実行されなければならない。本願発明に係るステップは他がいに十分に分離された時間で実行することができ、データは介入時間の間にメモリに記憶される。指紋は比較できる個人の物理的な特性として説明したが、手のひらのプリント、足の指のプリント及び赤ん坊を特定するために病院で用いられる（素足の）足のプリントのような他の特性を含む。説明した構成は単一の指紋読取装置用のものであり、多数の参照指紋ファイルを得ることができるときには未特定の指紋の処理量を多くする必要があることがわかる。その場合には説明したもの及び請求の範囲に記載したものと似た複数のプロセッサを同時に同一の参照指紋から処理し、または異なるが関連する参照指紋ファイルから処理することができ、その結果、１つのプロセッサが未知の指紋と１からＮ1 までの範囲のファイル番号を持つ参照指紋指紋とを比較し、第２のプロセッサが同時に同一の未知の指紋とＮ2 からＮ3 までの範囲のファイル番号を持つ参照指紋とを比較し、第３のプロセッサが同時に同様に比較することができる。本願発明の原理は場面または画像ないの対象／目標の認識及びまたは特定に用いることができることがわかる。

───────────────────────────────────────────────────── フロントページの続き (81)指定国ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ，ＤＫ，ＥＳ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＭＷ，ＳＤ，ＳＺ，ＵＧ)，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＥ，ＨＵ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＫ，ＬＲ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＴＪ，ＴＭ，ＴＴ，ＵＡ，ＵＧ，ＵＺ，ＶＮ

Claims

【特許請求の範囲】１少なくとも１つの未特定の指紋を含む１セットの未特定の指紋と、指紋ファイルからの複数のセットの参照指紋とを一致させる方法であって、ノード及びノード特性(a)と該ノード間の枝及び枝特性(b)とを含む特性関連図（ＡＲＧ）を、前記未特定の指紋のセットの抽出デジタル詳細点マップから発生して前記ノードの各々に中心がある星を暗黙的に発生する工程と、前記未知の指紋のセットの前記指紋の１つの前記ＡＲＧ内の星(a)と、前記参照指紋のセットの１つの内の指紋の１つのＡＲＧの星(b)との間の距離マトリクスであって、星の各対に関連するマトリクス要素を含む距離マトリクスを発生する工程と、前記距離マトリクス及び前記ＡＲＧから星対の一致するセットの一致コアを発生する工程とを含む方法。２請求項１の方法において、さらに、一致スコアを前記一致コアに割当て、前記参照ファイルからの他の指紋に対し特性関連図の発生(a)、距離マトリクスの発生(b)、一致コアの発生(c)の工程を繰り返す工程と、一致の値を前記一致スコアの内の最も大きな１つに割当て、それにより、前記参照指紋のうちの前記未知の指紋と最も一致した１つを特定する工程とを含む方法。３請求項１の方法において、距離マトリクス計算を実行する前記工程が、前記詳細点の対の間のユークリッド距離を決定する工程と、前記詳細点の対の間のユークリッド距離を前記対の前記詳細点の間の局部的隆起幅の平均値で割って前記各対ごとに標準化した隆起幅距離を発生し、これにより、前記形態上の関連リストが前記標準化した隆起幅距離を含む工程とを備える方法。４請求項１の方法において、さらに、前記未知の指紋のセットの前記特性関連図を発生する工程を含む方法。５請求項１の方法において、前記特性関連図を発生する工程が、前記ＡＲＧの特定のノードを前記抽出デジタル詳細点マップに割当てる工程と、前記ＡＲＧの特定のノードにその対応する詳細点の位置を割当てる工程と、前記ＡＲＧの特定のノードにその対応する詳細点の方向を割当てる工程と、前記特定のノードと、該特定ノードの周りの四分円の各々内の最も近い他のノードとの間に、前記特定のノードの前記方向によって確立されたように枝を構成する工程であって、前記最も近いものは前記ノード間のユークリッド距離によって決定される構成工程と、前記枝に、前記ユークリッド距離(a)および他のノードが存在する四分円(b)の少なくとも特性を割当てる工程とを含む方法。６請求項５の方法において、前記ノードに詳細点の種類の特性を割当てる工程と、前記ノードに局部幅の特性を割当てる工程との内の少なくとも１つを含む方法。７請求項５の方法において、前記枝に隆起数の特性を割当てる工程と、前記枝に標準化された隆起幅距離の特性を割当てる工程と、前記枝に同一隆起の特性を割当てる工程との内の少なくとも１つを含む方法。８請求項１の方法において、前記距離マトリクスを発生する工程が、前記未知のおよび参照指紋の前記ＡＲＧ表現の各星の前記枝の各々の特性の値を比較し、それにより、前記未知の指紋の星の各枝と前記参照指紋の星の各枝との間で比較を行い、これにより、枝の各対ごとに点数を発生する工程と、各星対ごとの枝対の点数の最大一致合計を計算することによって前記距離マトリクスの要素を発生する工程とを含む方法。９請求項１の方法において、さらに、各指紋対ごとに前記距離マトリクスの前記要素を該要素の値に応じて分類して、星対一致の順番を確立する分類された距離マトリクスを形成する工程とを含み、前記一致コアを発生する工程が前記分類された距離マトリクスによって確立された順番で実行される方法。 10 請求項９の方法において、前記一致コアを発生する工程が、前記記憶された距離マトリクスの内の最高の要素に関連する星対を選択して一致コアの第１の要素を画定する工程と、前記距離マトリクスから前記一致コアの前記第１の要素に関連する要素を削除して減少された距離マトリクスを発生する工程と、前記一致コアの前記第１の要素内の前記星対の中心ノードに隣接するノードに中心を置く星の候補対の中から候補星対を選択する工程であって、前記候補星対が、(a)前記一致コアと一致するとともに、(b)前記減少距離マトリクス内の最高の距離マトリクス要素に関連する前記一致コアに一致するすべての前記候補星対の中にあり、これにより、前記一致コアに対する第２の要素を発生する工程と、前記第２の要素を前記一致コアに別の要素として追加する工程と、前記減少距離マトリクスから前記一致コアに追加された前記候補星対に関連する前記距離マトリクスの前記要素の内の１つを削除して別の減少距離マトリクスを形成する工程と、前記別の星対を選択する工程、追加する工程、及び前記減少距離マトリクスから削除する工程を、少なくとも前記一致コアに一致する候補星対の残りがなくなるまで繰り返す工程とを含む方法。 11 請求項１０の方法において、前記一致コアに一致する候補星対が残らなくなるまで繰り返す工程が、前記一致コア内の要素の特定の数が一致すると判断する工程を含む方法。 12 請求項１０の方法において、さらに、前記一致コア内の要素の数が特定数より小さく、前記一致コアと一致する星対が残っていないときには、前記一致コアから最も新しく追加した要素を削除し、それにより、他の要素が前記一致コアに追加された最後の要素となる工程と、前記一致コアの要素に関連するいずれかの星の中心ノードの隣接ノードに中心を置く星の候補対の中から、候補星対を選択する工程であって、前記候補星対が、(a)前記一致コアと一致するとともに、(b)前記減少距離マトリクス内の最高の距離マトリクス要素に関連する前記一致コアに一致するすべての前記候補星対の中にあり、これにより、前記一致コアに対する第２の要素を発生する工程と、前記一致コアに前記次の要素を追加する工程と、前記減少距離マトリクスから前記一致コアに前記次の要素として追加された前記候補星対に関連する前記距離マトリクスの前記要素の内の１つを削除してさらに別の減少距離マトリクスを形成する工程と、前記別の星対を選択する工程、追加する工程、及び前記減少距離マトリクスから削除する工程を、少なくとも前記一致コアに一致する候補星対の残りがなくなるまで繰り返す工程とを含む方法。 13 請求項１の方法において、一致コアを発生する工程が、さらに、各指紋対ごとに、前記距離マトリクスの前記要素を、該要素の値に応じて分類して星対一致の順番を確立する工程と、前記分類された距離マトリクスによって確立された順番で、さらに、 (a)最高の距離マトリクス要素に関連する星対を選択して一致コアの第１の要素を特定する工程と、 (b)前記距離マトリクスから前記一致コアの前記第１の要素に関連する要素を削除して減少された距離マトリクスを発生する工程と、 (c)前記一致コアの前記第１の要素内の前記星の中心ノードの隣接ノードに中心を置く星の候補対の中から、候補星対を選択する工程であって、前記候補星対が、(i)前記一致コアと一致するとともに、(ii)前記減少距離マトリクス内の最高の距離マトリクス要素に関連する前記一致コアに一致するすべての前記候補星対の中にあり、これにより、前記一致コアに対する第２の要素を発生する工程と、 (d)前記次の要素を前記一致コアに別の要素として追加する工程と、 (d)前記減少距離マトリクスから前記一致コアに追加された前記候補星対に関連する前記距離マトリクスの前記要素の内の１つを削除して別の減少距離マトリクスを形成する工程と、 (f) 前記別の星対を選択する工程、追加する工程、及び前記減少距離マトリクスから削除する工程を、少なくとも前記一致コアに一致する候補星対の残りがなくなるまで繰り返す工程とを含む方法。 14 少なくとも１つの未特定指紋を含む１セットの未特定の指紋と、データ記載の複数のセットの参照指紋とを一致させる方法であって、ノード及びノード特性(a)と該ノード間の枝及び枝特性(b)とを含む特性関連図（ＡＲＧ）を、前記未特定の指紋のセットの抽出デジタル詳細点マップから発生して前記ノードの各々に中心がある星を暗黙的に発生する工程と、デジタル的に記憶された参照指紋情報が予備プログラムされたメモリから複数の特性関連図を読み取り、これにより、前記参照指紋のセット内で指紋の少なくとも１つの抽出ＡＲＧを入手できるようにする工程と、プログラムされた電子計算装置を用いて、前記未知の指紋のセットの前記指紋の１つの前記ＡＲＧ内の星(a)と、前記抽出ＡＲＧの星(b)とを比較する距離マトリクスであって、星の各対に関連するマトリクス要素を含む距離マトリクスを発生する工程と、プログラムされた電子計算装置を用いて、前記前記マトリクス及び前記ＡＲＧから星対の一致するセットの一致コアを発生する工程と、前記一致コアの値を用いて前記参照指紋の内の１つが前記未知の指紋に最も近い場合にそれを選択する工程とを含む方法。 15 請求項１４の方法において、さらに、前記プログラムされた電子計算装置を用いて各指紋対ごとに前記距離マトリクスの前記要素を該要素の値に応じて分類して、星対一致の順番を確立する工程と、一致コアを発生する前記工程が前記分類された距離マトリクスによって確立された順番で実行される方法。 16 指紋を比較する装置であって、ノード及びノード特性(a)と該ノード間の枝及び枝特性(b)とを含む特性関連図を、前記未特定の指紋のセットの抽出デジタル詳細点マップから発生して前記ノードの各々に中心がある星を暗黙的に発生するＡＲＧ発生手段と、複数の参照指紋のＡＲＧが前プログラムされたデジタルメモリと、該メモリに接続されていて制御信号の制御下で前記メモリから前記ＡＲＧを連続して読取る手段と、前記ＡＲＧ発生手段と前記読取り手段とに接続された距離マトリクス発生手段であって、前記制御信号の制御下で、前記未知の指紋のセットの前記指紋の１つの前記ＡＲＧ内の星(a)と、前記参照指紋のセットの１つの内の指紋の１つのＡＲＧの星(b)との間の距離マトリクスであって、星の各対に関連するマトリクス要素を含む距離マトリクスを発生する距離マトリクス発生手段と、前記分類手段に接続された一致コア発生手段であって、前記制御信号の制御下で、前記距離マトリクス及び前記ＡＲＧから星対の一致するセットの一致コアを発生する一致コア発生手段と、該一致コア発生手段に接続されていて、前記制御信号の制御下で、前記一致コアの値を記憶する記憶手段と、該記憶手段に接続された一致コア分類手段であって、前記制御信号の制御下で、最大値を持つ前記一致コアの内の１つを選択し、さらに、前記最大値に関連する前記参照指紋の内の１つを特定する表示を発生する一致コア分離手段と、前記距離マトリクス発生手段と、前記一致コア発生手段と、前記記憶手段と、前記一致コア分類手段とに接続されたシーケンサであって、(a)前記距離マトリクス発生手段が前記未知の指紋の前記星と前記参照指紋の各々の星との比較を連続的に実行するようにし、(b)前記参照指紋の内の１つのＡＲＧの星のすべてが前記距離マトリクスの要素まで減少されたときに、前記一致コア発生手段が前記一致コアを発生するようにし、(d)前記一致コアの各々が発生するときに、前記記憶手段が前記一致コアを記憶するようにし、(e)複数の一致コアが記憶された後に、前記一致コア分類手段が最高値を持つ少なくとも１つの前記一致コアを選択するようにするシーケンサとを備える装置。 17 請求項１６の方法において、さらに、前記距離マトリクス発生手段に接続された距離マトリクス分類手段であって、前記制御信号の制御下で、各指紋対ごとに前記前記距離マトリクスの前記要素を該要素の値に応じて分類して星対一致の順番を確立する距離マトリクス分類手段と、前記距離マトリクス分類手段と前記シーケンサとに接続されたシーケンサ接続手段であって、前記参照指紋の内の１つのＡＲＧの星のすべてが前記距離マトリクスの要素まで減少されたときに、前記距離マトリクス分類手段が前記距離マトリクスの前記要素をそれらの値に応じて分類して順番を発生するようにし、さらに、前記距離マトリクス分類手段が前記順番を確立したときに、前記一致コア発生手段が前記順番によって決定された順序で前記一致コアを発生するシーケンサ接続手段とを備える装置。 18 請求項１６の装置において、さらに、前記一致コア分類手段と前記シーケンサとに接続されていて、最高値を持つ前記１つの一致コアに対応する前記参照指紋の１つの特定を表示する表示装置を備える装置。 19 少なくとも１つの未特定の個人の身体的特徴を含む１セットの未特定の個人の身体的特徴と、個人の身体的特徴ファイルからの複数のセットの参照個人の身体的特徴とを一致させる方法であって、ノード及びノード特性(a)と該ノード間の枝及び枝特性(b)とを含む特性関連図を、前記未特定の個人の身体的特徴のセットの抽出デジタル詳細点マップから発生して前記ノードの各々に中心がある星を暗黙的に発生する工程と、前記未知の個人の身体的特徴のセットの前記個人の身体的特徴の１つの前記ＡＲＧ内の星(a)と、前記参照個人の身体的特徴のセットの内の１つの個人の身体的特徴の１つのＡＲＧの星(b)との間の距離マトリクスであって、星の各対に関連するマトリクス要素を含む距離マトリクスを発生する工程と、前記距離マトリクス及び前記ＡＲＧから星対の一致するセットの一致コアを発生する工程とを含む方法。 20 請求項１９の方法において、前記個人の身体的特徴が指紋である方法。 21 請求項１９の方法において、さらに、各個人の身体的特徴対ごとに前記距離マトリクスの前記要素を該要素の値に応じて分類して、星対一致の順番を確立するとを含み、前記距離マトリクス及び前記ＡＲＧから前記星対の一致セットの一致コアを発生する工程が前記分類された距離マトリクスによって確立された順番で実行される方法。 22 少なくとも１つの未特定の指紋を少なくとも１つの参照指紋と一致させる方法であって、ノード及びノード特性(a)と該ノード間の枝及び枝特性(b)とを含む特性関連図（ＡＲＧ）を、前記未特定の指紋の抽出デジタル詳細点マップから発生して前記ノードの各々に中心がある星を暗黙的に発生する工程と、前記未知の指紋の前記ＡＲＧ内の星(a)と、前記参照指紋の前記１つのＡＲＧの星(b)との間の距離マトリクスであって、星の各対に関連するマトリクス要素を含む距離マトリクスを発生する工程と、前記距離マトリクス及び前記ＡＲＧから星対の一致するセットの一致コアを発生する工程とを含む方法。