JPS6334508B2 - - Google Patents

Description

【発明の詳細な説明】 発明の属する技術分野 本発明は指紋の照合方法に関する。本発明にお
ける“指紋”とは指紋、足紋、その他しま状パタ
ーン等のいわゆる紋様パターンの代表として定義
する。また“照合”とは探索すべき１つの指紋
と、予め登録されている指紋との同一性を判別す
ることを意味する。

従来の技術 通常照合する指紋を探索指紋と称し照合対象と
なる予め登録された指紋をフアイル指紋と称す
る。各々の指紋は、隆線紋様の特殊な点、すなわ
ち、第１図において隆線Ｋのとぎれる点Ｍ（端点）
および分岐または合流する点ｍ（分岐点）を持つ
ており一般にこれらの点は特徴点と呼ばれる。

従来、指紋照合は、上記探索およびフアイル指
紋のそれぞれに対し特徴点の種別、ある基準座標
系に対するその特徴点の位置Ｘ，Ｙおよびその方
向Ｄの情報をコード化して記憶し、このコード化
された指紋特徴を用いて行なわれている。

例えば、事件現場等に残された探索指紋特徴点
の位置および方向を記述する座標系の選び方には
任意性があり照合されるべきフアイル指紋の特徴
点を表わす座標系とは一般に一致しない。従つ
て、照合に際しては探索指紋の座標系を照合する
相手フアイル指紋ごとに最も確からしい量だけ回
転及び平行移動の座標変換を行なつてから比較検
定する必要がある。

一般に照合する場合、照合すべき相手フアイル
指紋は莫大な数によるので照合の高速性および確
実性（信頼性）が重要視される。

以下に従来の指紋照合方法を述べる。

一般に探索指紋の特徴点と照合すべきフアイル
指紋の特徴点とではその数も異なりまたその対応
も不明である。これらを対応づけるために各特徴
点に対し、座標変換により左右されない局所的特
徴を表わす量を導入している。

例えば、各特徴点の種別（端点および分岐点）
もその一つであり、またある特徴点から特定の半
径以内に存在ある他の特徴点の数も局所的特徴を
表わす量となる。さらに、これらの量をもとの特
徴点を原点とし方向Ｄを、例えば、Ｙ軸とする局
所座標系を作り、この座標系の各象限に分布する
他の特徴点の数という形に分割すれば一層情報量
の多い局所的特徴を表わす量となる。

これらの局所的特徴量を導入すると、探索指紋
の各特徴点に対し各フアイル指紋の特徴点をこの
局所的特徴量を用いて比較することにより座標系
の選び方とは無関係にそれぞれの近似度の強さを
決定することができる。そこで上述の局所的に近
似度の強さの順に各特徴点間の対候補を決定し、
これらの対候補となる特徴点の持つ局所的近似度
を最もよく整合させる座標整合量を求め最終的な
照合値を決定させることができる。

しかしながら従来の照合方法及び照合装置では
上述の照合における高速性および信頼性という点
で必ずしも充分でないという欠点を有している。

発明の目的 本発明の目的は、探索指紋とフアイル指紋の照
合において、高信頼性を持ちかつ高速な照合を可
能とする指紋照合方法を提供することにある。

発明の構成 従来の指紋照合装置は、照合対象となる探索指
紋とフアイル指紋に対し各々予め定めた基準座標
系における各特徴点の位置、角度及び座標系とは
独立なリレーシヨンデータを示す特徴点リストを
記憶する特徴点リスト記憶手段、前記２つの指紋
の各々に対し各特徴点が明領域か不明領域かを示
す指紋領域を記憶する指紋領域記憶手段、および
前記２つの指紋の各特徴点に対し前記特徴点の位
置、角度、およびリレーシヨンデータの一致性を
検査することにより、前記２つの指紋の特徴点か
ら対となる特徴点を選択する手段から構成されて
いる。

本発明の指紋照合装置は、対候補として上述の
対特徴点を示す対候補リストを記憶する対候補リ
スト記憶手段、前記２つの指紋の基準座標系を合
わせるために、前記対候補特徴点の位置ずれおよ
び角度のずれから最適座標整合量を生成する最適
座標整合量生成手段、前記２つの指紋の基準座標
系のどちらかを前記最適座標整合量により整合さ
れた座標系に変換する座標変換手段、前記座標整
合された各特徴点の位置、角度、およびリレーシ
ヨンデータの一致性を検査することにより決定さ
れる真の特徴点と対値を示す対リストを生成する
対リスト生成手段、および前記真の特徴点及び対
値から照合値を決定する照合値決定手段から構成
されることを特徴とする。

発明の実施例 以下、本発明に関して、図面を参照して詳細に
説明する。

第２Ａ図参照すると、本発明の指紋照合装置の
適用されるシステムは、照合データ入力処理装置
１，照合データ管理処理装置２，データ貯蔵装置
３，照合制御装置４，および４個の照合装置５，
６，７および８から構成されている。ただし、照
合装置は４個に限定するものではない。第２Ｂ図
を参照すると、前記照合装置５，６，７および８
のそれぞれは、制御ユニツト１０，第１次照合プ
ロセツサ２０，第２次照合プロセツサ５０，およ
びユニツト１０とプロセツサ２０，プロセツサ２
０とプロセツサ５０，およびプロセツサ５０とユ
ニツト１０の間でデータ伝送するためのデータ線
１０ａ，２０ａ，５０ａおよび制御線１０ｂ，２
０ｂ，５０ｂから構成されている。

第３図を参照すると、第２Ｂ図に示す制御ユニ
ツト１０は、照合制御装置４からのデータおよび
２次照合プロセツサ５０からのデータを格納する
緩衝記憶３００，照合制御装置４とのデータのや
りとりを行なうインタフエース回路、プロセツサ
２０，５０とのデータのやりとりを行なうプロセ
ツサインタフエース回路３０２，制御回路３０３
および転送先決定回路３０４から構成されてい
る。

次に指紋照合時のシステムの動きを第２Ａ図に
より以下に説明する。照合データ管理処理装置２
から照合制御装置４に対し照合指示及び照合対象
となる探索指紋及びフアイル指紋のデータ貯蔵装
置３の中の位置情報を与える。照合指示を受けた
照具制御装置４は、まずデータ貯蔵装置３から探
索指数１指を読出し照合装置５，６，７，８にす
べて共通に送り込み次にデータ貯蔵装置３から順
次フアイル指紋を読出し照合装置５，６，７，８
に送り込み照合を開始させる。即ち照合装置５，
６，７，８は、探索指紋１指と、各々異なるフア
イル指紋と並列照合を行ない照合値を算出する。
探索指紋１指と大量のフアイル指紋との照合が終
了すると照合制御装置４は、各照合装置５，６，
７，８から照合結果を読出し照合値に従つて配列
し直し照合データ管理処理装置２に報告する。照
合データ管理処理装置２は照合結果を編集し信号
線１２を介して出力する。

第４図を参照すると、第２図に示す第１次照合
プロセツサ２０，３０および４０のそれぞれは、
シーケンス制御回路２１０、第１次特徴点リスト
メモリ２１１、座標変換回路２１２、最近傍特徹
点復元回路２１３、「対」検査回路２１４、「対」
候補リストメモリ２１５、作業エリア２１６、座
標整合量決定回路２１７、および制御記憶２１８
から構成されている、第１次特徴点リストメモリ
２１１は探索指紋特徴点リストメモリ２１１ａと
フアイル指紋特徴点リストメモリ２１１ｂで構成
される。

第５図を参照すると、第２図の前記第２次プロ
セツサ５０および６０のそれぞれは、シーケンス
制御回路５１０，第２次特徴点リストメモ５１
１，座標変換回路５１２，対候補リストメモリ５
１３，作業エリアメモリ５１４，対リストメモリ
５１５，領域パターンリストメモリ５１６，候補
リストメモリ５１７，制御記憶５１８および演算
回路５１９から構成されている。

次に本発明の一実施例の動作を第６図に示すフ
ローに従い以下の順に詳細に説明する。

(1) 指紋特徴点データの読出し動作 (2) 座標変換動作 (3) 最近傍特徴点復元動作 (4) 対検査動作の一例 (5) 対検査動作の変形例 (6) 座標整合量の生成及び整合動作 (7) ２次照合プロセツサによる精密照合動作 (8) 転送先プロセツサ決定動作 (1) 指紋特徴点データの読出し動作 第７図に本発明の指紋照合で使用される特徴点
データの構成を示す。特徴点データは、識別情
報、領域パターンリスト及び特徴点リストから成
り立つている。識別情報は、指紋個別に付けられ
た指紋識別番号、生年月日、性別、指種、及び紋
様分類等の情報が格納されている。領域パターン
リストとは、入力データ処理装置１における特徴
点抽出時の指紋領域が明領域か不明領域かを示す
情報である。特徴点リストとは、指紋領域内にあ
る特徴点M₀，M₁，……，M_f……M_i，……M_zの
特性を示した情報を格納しており第８図に示すデ
ータ構造を有している。

第８Ａ図を参照すると、一般に番目の特徴点
は情報としてその特徴点が分岐点か端点かを示す
種別コードQ位置を示す情報X，Y，隆線方向
を示すD，その特徴点の周囲の集密度を示すC
及び特徴点Mとその最近傍特徴点との間の隆線
数を示すR₀，R₁，R₂，R₃を有している。特
徴点リスト上の位置及び方向は、指紋領域の適宜
に定められた点を原点とする直交座標系を基準座
標系としてすべて表わされている。一般にこれら
の基準座標系は指紋により異なつたものである。
なお上述の特徴点抽出方式に関しては特願昭54−
39648の中で詳細に記載されている。

第８Ｂ図は、特徴点Mの方向Dをｙ軸とする
局所座標系における４つの象限の各々に対し特徴
点Mに最も近い特徴点（最近傍特徴点と称す）
M₀，M₁，M₂，M₃と特徴点Mと、前記
各々の最近傍特徴点との間の隆線数R₀，R₁，
R₂，R₃との関係を示している。

上述の入力特徴点データが第２Ａ図のデータ入
力処理装置１，および照合データ管理処理装置２
を介してデータ貯蔵装置３に格納される。次に照
合データ管理処理装置２は探索指紋をデータ貯蔵
装置３から読出すように照合制御装置４に指示す
る。この装置４はこの指示に応答してデータ貯蔵
装置３から照合制御装置４，第２図の制御ユニツ
ト１０，第４図のシーケンス制御回路２１０を介
して入力特徴点リストを探索特徴点リストメモリ
２１１ａに入力する。探索指数の特徴点リストが
データ貯蔵装置３から読出されるとき読出される
アドレスで指定される位置からフアイル指紋の特
徴点リストが読出される。この読出されたフアイ
ル指紋の特徴点リストは上述の経路と同じ経路を
介して第４図のフアイル特徴点リストメモリ２１
１ｂに格納される。

第４図の特徴点リストメモリ２１１には探索お
よびフアイル指紋の入力特徴点リストが第８Ａ図
の形式で格納されている。各特徴点Mで示され
るアドレスに、種別コードQ，位置を示す情報
X、およびY，方向を示す情報D，集密量を示
す情報C，および隆線数R₁−R₄が格納されて
いる。

特徴点リストメモリ２１１から読出されたデー
タは第４図の座標変換回路２１２で座標変換され
る。

(2) 座標変換動作 次に本発明の指紋照合装置において使用される
座標変換動作を詳述する。

フアイル指紋データと探索指紋データとは採取
時点，採取条件および採取環境が異なるため、両
指紋データの突合せに先行して若干の補正作業が
必要になる。すなわち、特徴点はパターン認識の
立場からは、指紋紋様の途切れ点の位置と方向と
が重要視されるが、フアイル指紋データと探索指
紋データとは上述のような理由により、多くの場
合には途切れ点の位置を表現する座標系が異なる
ため、探索指紋データの座標系からフアイル指紋
データの座標系への座標変換を行なつて座標整合
する必要がある。

また、指紋データには特徴点リスト以外に、指
紋採取の際の指紋の不明領域等を表現する領域パ
ターンリストが含まれるが、この領域パターンリ
ストは変換の対象とはならない。探索指紋データ
に対する変換を行ない、フアイル指紋データとの
特徴点比較処理中に、領域パターンリストを参照
する必要性が生じるが、探索指紋データの領域パ
ターンリストは変換前の値であるため、このとき
はフアイル指紋データの座標系から探索指紋デー
タの座標系への逆変換を行なわねばならない。

第９図を参照すると、直交座標系（X_p−Q_p−
Y_p）上の点Ｐの座標位置（x_p，y_p）が新しい直
交座標系（X_q−O_q−Y_q）上の座標位置（x_q，y_q）
に変換された状態が示されている。両直交座標系
の原点O_pをO_qの間は間隔（ｘ，ｙ）だけ変位し、
かつ両直交座標系は角度θだけ回転している。変
換前の座標位置（x_p，y_p）と変換後の座標位置
（x_q，y_q）との間には次式の関係が成立すること
が幾何学的手法により容易にわかる。

x_q＝（x_q−ｘ）・cosθ＋（y_p−ｙ）・sinθ y_q＝（y_p−ｙ）・cosθ−（x_p−ｘ）・sinθ …… 第１０図を参照すると、式にしたがつて、座
標位置（x_q，y_p）から変換後の座標位置（x_q，
y_q）を得るためのプロセスが示されている。すな
わち、両直交座標系の変位（ｘ，ｙ）と回転角θ
ならびに変換すべき座標位置（x_p，y_p）が与えら
れると、cosθおよびsinθを求める処理（フエーズ
）、（x_p−ｘ）および（y_p−ｙ）を求める処理
（フエーズ）、フエーズの処理結果とフエーズ
の処理結果との乗算を行ない中間結果を求める
処理（フエーズ）および中間結果の加算または
減算により最終結果を求める処理（フエーズ）
により変換された座標位置（x_q，y_q）が求められ
る。

なお、上述の変換方向とは逆に、座標位置
（x_q，y_q）を座標位置（x_p，y_p）に変換（逆変換）
するための式は、以下に示す式のようになる。

x_p＝x_q・cosθ−y_q・sinθ＋ｘ y_p＝y_q・cosθ＋x_q・sinθ＋ｙ …… 従来、式および式により表現される変換は
すべてソフトウエア的手法により行なわれている
ため、高速処理が困難であるという欠点がある。
とりわけ、フエーズととの処理は高速乗除算
機能などの特別な機能を有する計算機を使用しな
いかぎりその高速化はむずかしい。

第１１図を参照すると、前記座標変換回路２１
２は、３個のレジスタ１１１０，１１１１および
１１１２，６個の選択回路１１２０，１１２１，
１１４０，１１４１，１１７０および１１７１，
５個の加減算器１１３０，１１３１，１１３２，
１１６０および１１６１と、４個の乗算器１１５
０，１１５１，１１５２および１１５３および読
出し専用メモリ（ROM）１１８０から構成され
ている。

ROM１１８０は、２個の直交座標系（X_p−O_p
−Y_P）と（X_q−O_q−Yq）との間の回転角θに対
する円関数値を予め格納している。

選択回路１１２０および１１２１は、変換モー
ド指示信号（モード信号）INVが順変換を指示
しているときはそれぞれ入力端子ＸとＹの各出
力、モード信号INVが逆変換を指示していると
きはそれぞれ加減算器１１６０および１１６１の
各出力を選択するように動作する。同様にして、
選択回路１１４０および１１４１は順変換時には
それぞれ加減算器１１３０および１１３１、逆変
換時にはそろぞれ入力端子ＸとＹの各出力を選択
し、選択回路１１７０および１１７１は順変換時
にはそれぞれ加減算器１１６０および１１６１、
逆変換時にはそれぞれ加減算器１１３０および１
１３１の各出力を選択し、加減算器１１３０，１
１３１，１１３２，１１６０および１１６１は順
変換時にはそれぞれ減算、減算、減算、加算およ
び減算、逆変換時にはそれぞれ加算、加算、加
算、減算および加算を行なうように動作する。

先ず、入力端子Ｘ，ＹおよびＤにそれぞれ変位
ｘ，ｙおよび回転角θを与え、かつ前置信号
PALを印加すると、変位ｘ，ｙおよび回転角θ
がそれぞれレジスタ１１１０，１１１１および１
１１２に入力される。レジスタ１１１２に入力さ
れた回転角θはROM１１８０をアクセスするた
めのアドレスになり、ROM１１８０から正弦値
sinθと余弦値cosθとを読み出す（第１０図におけ
るフエーズ）。

次に、前置信号PALの印加を差し止め、かつ
入力端子Ｘ，ＹおよびＤにそれぞれ変換すべき座
標位置および変換すべき直交座標系における特徴
点の向きを与える。このときモード信号INVが
“０”か“１”かに応答してそれぞれ順変換指示
か逆変換指示かになり、各選択回路と各加減算器
は前述のように動作する。

いま、モード信号INVが“０”であると、加
減算器１１３０および１１３１は第１０図に示す
フエーズ、乗算器１１５０，１１５１，１１５
２および１１５３はフエーズ、そして加減算器
１１６０および１１６１はフエーズの各処理を
行ない、出力端子X_TとY_Tとから順変換後の座標
位置x_qとy_qが得られる。加減算器３２は順変換す
べき直交座標系における特徴点の向きから回転角
θを減じ、この値を順変換後の直交座標系におけ
る特徴点の向きとして、出力端子D_Tから出力さ
せる。

次に、モード信号INVが“１”であると、乗
算器１１５０，１１５１，１１５２，および１１
５３はそれぞれ式におけるx_q・cosθ，y_q・
sinθ，y_q・cosθおよびx_q・sinθの乗算，加減算器
１１６０および１１６１はそれぞれx_q・cosθ−
y_q・sinθの減算とy_q・cosθ＋x_q・sinθの加算、加
減算器１１３０および１１３１はそれぞれ（x_q・
cosθ−y_q・sinθ）＋ｘと（y_q・cosθ＋x_q・sinθ）＋
ｙの各加算を行ない、出力端子X_TとY_Tとから逆
変換後の座標位置x_pとy_pが得られる。加減算器１
１３２は逆変換すべき直交座標系における特徴点
の向きに回転角θを加え、この値を逆変換後の直
交座標系における特徴点の向きとして、出力端子
D_Tから出力させる。

以上のような構成の採用により、順・逆いずれ
への変換に対する座標位置も一挙動で得られるよ
うになるため、両方向性の高速座標変換ができる
ようになる。特徴点メモリ２１１に第１３図で示
される特徴点リストが格納される場合には以下に
示す最近傍特徴点の復元動作は不要である。しか
しデータ貯蔵装置の容量を減小させようとすると
きには、第８Ａ図に示される特徴点リストが特徴
点リストメモリ２１１に格納されなければならな
い。この場合には以下に示す最近傍特徴点の復元
動作が必ず必要となる。

(3)最近傍特徴点の復元動作 第４図の座標変換回路２１２および最近傍特徴
点復元回路２１３を用いて最近傍特徴点が第１３
図に示す様に特徴点リスト上にMf₀，Mf₁，Mf₂，
Mf₃として付加される。これを詳述すると、探索
およびフアイル特徴点の間の近似度を定量的に表
すものとして、各特徴点の局所的特徴、すなわ
ち、中心座標系の選び方に左右されない各特徴点
の局所的特徴による近似度を用いる。

例えば、前述の種別を表わすＱもその一つにな
る。また、対象とする特徴点から予め定めた一定
の距離以内にある他の特徴点の数も局所的特徴と
して用いることができる。

とくに、以下に示す局所的特徴は、対候補リス
トを作るのに極めて有力な材料を提供する。

今、あるパターンの任意の番目の特徴点を
Mとするとき、この特徴点Mの位置X，Yを
その座標原点とし、方向DをＸ軸の方向とする
直交座標系をこの特徴点Miで定まる局所座標系
と定義する。

この局所座標系の各象限（第１象限、第２象
限、第４象限および第３象限）において、この座
標原点（つまり対象となつているもとの特徴点
M）に最も近い位置にある他の特徴点の番号を
それぞれ0，1，2および3とすると、もとの特
徴点Mは、このMによつて定まる局所座標系の
各象限内にそれぞれ他の最近特徴点M₀，M₁，
M，₂およびM₃をもつという局所的特徴を有し
ていることになる。勿論この局所的特徴は中心座
標系の選び方とは無関係である。

そこで今、探索指紋の任意の番目の特徴点
Mについて上述のような0，1，2および3が
得られており、また、照合すべきフアイル指紋の
任意のｊ番目の特徴点Mjについても同様にMjに
よつて定まる局所座標系の各象限内に特徴点番号
k0，k1，k2およびk3をもつ最近特徴点が得られ
ていたとすると、この両方の特徴点MとMjとの
局所的近似度は、それぞれの局所座標系上で、対
応する象限内にある最近特徴点同志の相互関係
が、ある一定のしきい値近傍内にあるか否かを判
定することで容易に定量化することができる。例
えば、対応する象限内における最近特徴点同志
の、それぞれの局所座標系におけるＸ座標の差お
よびＹ座標の差を求め、この差があるしきい値以
内にある場合には、各象限の最近特徴点ごとに近
似度の重みに１を加算するという形で定量化する
ことができる。

このように、各特徴点に対し、この特徴点で定
まる局所座標系の各象限内における最近特徴点を
見出し、これをもとの特徴点と対応づけるという
処理（以下リレーシヨン生成処理）は、上述のよ
うに、パターンの同一性の照合を行なう場合の重
要な一つのステツプとなる。

とくに、指紋照合等の処理においては、一つの
探索指紋に対しこれと照合して同一性を判定すべ
きフアイル指紋の数が厖大な量となるので、この
ようなリレーシヨン生成処理を高速かつ確実に実
行する必要がある。

第１２図を参照すると、第４図の最近傍特徴点
復元回路２１３は特徴点レジスタ１２０１（Ｑ），
１２０２（Ｘ），１２０３（Ｙ）および１２０４
（Ｄ）、アドレスレジスタ１２０５（Ａ），１２０
５（Ｂ），１２０６（Ｅ）および１２０６（Ｆ）、
定数加算器１２０７、入力選択器１２０８、２乗
計算器１２０９（X²）および１２１０（Y²）、加
算器１２１１、レジスタフアイル１２１２、比較
器１２１３、制御器１２１４、一致検出器１２１
５および禁止ゲート１２１６を有している。

さて、本実施例に用いられる特徴点リストメモ
リ２１１は下記のように構成されている。

第１３図に示すように、８ビツトの２進数で指
定される256個のロウアドレスと、３ビツトの２
進数で指定される８個のコラムアドレスとよりな
る全部で２０４８個のメモリアドレスを有してい
る。この各ロウアドレスは、一つの紋様パターン
の各特徴点に対応し、特定の番目の特徴点の各
情報は、対応する番目のロウアドレスをもつ各
コラムアドレスに以下に述べるように格納されて
いる。

まず、０番目のコラムアドレスには、番目の
特徴点の種別（端点分岐点特異点等の別）を表わ
す情報（以後Qで表示）が格納され、１番目の
コラムアドレスには番目の特徴点のＸ座標（以
後Xで表示）が、２番目のコラムアドレスには
番目の特徴点のＹ座標（以後Yで表示）が、
３番目のコラムアドレスには番目の特徴点の方
向Ｄ（以後Dで表示）がそれぞれ格納されてい
る。

これらのX，YおよびDの値は、この紋様パ
ターンのほゞ中心を座標原点とする特定のXY座
標系（以後必要の場合には中心座標系と呼称して
区別）で記述されているが、座標系抽出の際の誤
差が一般的にはかなり大きくなつてしまう。

また、ある紋様パターンの各Q，X，Yおよ
びDのすべての値が、この処理に先だち、すで
に上位装置によつて各メモリアドレスに上述のよ
うに書き込まれている。この場合に、書き込まれ
たこの紋様パターンの最後の特徴点の次のロウア
ドレスには、その０番目のコラムアドレス（Ｑを
格納するアドレス）に特定の終了マーク（E0D）
を格納し、処理の終了を指示するのに用いる。

まて、９番目から12番目までの４個のコラムア
ドレスは、本実施例が生成する最近傍特徴点を格
納すべきメモリアドレスで、この最近傍特徴点と
は以下に述べるようにものである。

今、特定の番目の特徴点をとり、第１４図に
示すように、この特徴点の位置X，Yを座標原
点とし、方向DをＸ軸方向とする局所座標系
（以後XY局所座標系）を作つたとする。この
XY局所座標系の各象限ごとに、この局所座標
系の原点（つまり番目の特徴点の位置）に最も
近い位置にある他の特徴点を１個ずつとり、それ
らの各特徴点の番号を象限の順番にM0，M1，
M3およびM2とすると、これが最近傍特徴点と
なる。

すなわち、本実施例は、任意の特徴点に対し、
その特徴点の近傍の状態を把握するため、この特
徴点で一義的に定まる局所座標系上の各象限にお
ける最近特徴点を探し、それらともとの特徴点と
を関連ずける動作を示している。こうして得られ
た最近傍特徴点は、X，YおよびDのデータと
異なつて、中心座標系の選び方とは無関係である
という特徴を有している。

さて、これらの最近傍特徴点は、もとの特徴点
に対応する番目のロウアドレスの、以下に示す
各コラムアドレスに格納される。

この局所座標系の第１象限にある最近傍特徴点
の番号M0を第９番目のコラムアドレスに格納す
る。第２象限にある最近傍特徴点番号M1を第10
番目のコラムアドレスに、第４象限にある最近傍
特徴点の番号M2を第11番目のコラムアドレス
に、第３象限にある最近傍特徴点の番号M3を第
12番目のコラムアドレスにそれぞれ格納する。な
お象限の順序と格納するコラムアドレスの順序が
ずれているのは後述するハードウエアを簡単にす
るためである。

さてつぎに、上述の最近傍特徴点の生成処理を
各回路の動作と関連づけて詳述する。

最近傍特徴点生成回路の中を制御部１２１４
（第１２図）はマイクロプログラムを格納する制
御記憶（図示せず）を含み、このマイクロプログ
ラムを逐次読み出して実行することにより処理を
進行させる。この処理の進行を第１５図にフロー
チヤートとして示す。

まず、開始指示がライン２９９（STRT）を
介してシーケンス制御回路２１０から供給され、
最近傍特徴点生成処理が開始されると（第１５
図）、制御部１２１４はアドレスレジスタ１２０
５（Ａ）および１２０５（Ｂ）を初期値設定す
る。アドレスレジスタ１２０５は最近傍特徴点を
求めるべきもとになる特徴点を指示するレジスタ
でロウアドレス指定部分１２０５（Ａ）とコラム
アドレス指定部分１２０５（Ｂ）とを有し、初期
値設定によつていずれも０にクリアされ、それぞ
れ最初のメモリアドレスを指示するようにセツト
される。（第１５図イ）。

次に、制御部１２１４は、レジスタ１２０５
（Ａ）の内容Ａで指定される特徴点リストメモリ
２１１のロウアドレスから特徴点のQ_A，X_A，Y_A
およびD_Aを読み出し、X_A，Y_AおよびD_Aを第１１
図に示す座標変換回路２１２のパラメータレジス
タ１１１０，１１１１および１１１２にそれぞれ
変換パラメータとしてロードする。このために第
１２図の制御部１２１４は、アドレスレジスタ１
２０５（Ａ）および１２０５（Ｂ）の内容をライ
ン１２０５６（AD）を介して特徴点リストメモ
リ２１１に供給することにより、アドレスレジス
タ１２０５（Ａ）で指定される特徴点リストメモ
リ２１１のロウアドレスからアドレスレジスタ１
２０５（Ｂ）で指定される４バイト分すなわち
Q_A，X_A，Y_AおよびD_Aを読み出す。この読み出し
たX_A，Y_AおよびD_Aの値をそれぞれ第１１図のラ
イン１０１０（Ｘ），２０２０（Ｙ）および１０
３０（Ｄ）を介して各パラメータレジスタに供給
し、ライン１０００（PL）にラツチパルスを供
給することにより、これらの値を各レジスタに設
定する（第１５図ウ）。

次に、第１２図の制御部１２１４は上で読み出
したQ_Aが終了マークであるか否かを判定し、も
し終了マークである場合にはこれで処理を終了
（第１５図オ）し、そうでない場合には下記に進
む（第１５図エ）。

次に、第１２図の制御部１２１４はアドレスレ
ジスタ１２０６（Ｅ），１２０６（Ｆ）およびレ
ジスタフアイル１２１２の初期値設定を行なう
（第１５図カ）。

アドレスレジスタ１２０６は、アドレスレジス
タ１２０５と同様に、ロウアドレス指定部分１２
０６（Ｅ）とコラムアドレス指定部分１２０６
（Ｆ）とを有し、これは比較すべき特徴点番号を
指示するためのレジスタで、初期値設定によつて
いずれも０にクリアされる。

また、レジスタフアイル１２１２は４個のレジ
スタ１２１２−０〜１２１２−３からなり、この
各レジスタはそれぞれのアドレスフイールドＭ
０，Ｍ１，Ｍ２およびＭ３と、それぞれの距離フ
イールドＲ０，Ｒ１，Ｒ２およびＲ３とからなつ
ている。

このアドレスフイールドＭ０〜Ｍ３は、現在ア
ドレスレジスタ１２０５（Ａ）で指定されるもの
との特徴点に対し、処理の現段階でみつかつた最
も近い位置にある他の特徴点の番号を前述の局所
座標系の各象限ごとに別別に格納するためのフイ
ールドで、第１象限の点の番号をＭ０に、第２象
限の点の番号をＭ１に、第３象限の点の番号をＭ
３に、第４象限の点の番号をＭ２にそれぞれ格納
する。

また、距離フイールドＲ０〜Ｒ３は前記局所座
標系の原点（つまりアドレスレジスタ１２０５
（Ａ）で指定されるものとの特徴点の位置）から
これら各特徴点Ｍ０〜Ｍ３までの距離の２乗値を
それぞれ格納するフイールドである。

上述の初期値設定において、レジスタフアイル
１２１２のこれらの各レジスタのすべてのビツト
には“１”がセツトされ、それぞれ、アドレスフ
イールドＭ０〜Ｍ３は対応する特徴点が存在しな
いことを表わし、距離フイールドＲ０〜Ｒ３は表
わし得る最も遠い距離に設定される。

さて次に、制御部１２１４は、アドレスレジス
タ１２０６（Ｅ）と１２０６（Ｆ）との内容をラ
イン１２０５６（AD）を介して特徴点リストメ
モリ２１１に供給することにより、アドレスレジ
スタ１２０６（Ｅ）で指定される４バイトすなわ
ち、Q_E，X_E，Y_EおよびD_Eを読み出し、Q_Eを特徴
点レジスタ１２０１（Ｑ）に格納する。

また、X_E，Y_EおよびD_Eを、座標変換回路２１
２（第１１図）のライン１０１０（Ｘ），１０２
０（Ｙ）および１０３０（Ｄ）のそれぞれを介し
て供給することにより、X_AY_A局所座標系（X_A，
Y_AおよびD_Aにより定まる局所座標系）で表わさ
れたそれぞれの値X_EA，Y_EAおよびD_EAに座標変換
し、こうして得られたそれぞれの値をライン２１
２０（X′），２１３０（Y′）および１０６０
（D′）を介し特徴点レジスタ１２０２（Ｘ），１
２０３（Ｙ）および１２０４（Ｄ）に格納する
（第１５図キ）。

さて次に、制御部１２１４は、特徴点レジスタ
１２０１（Ｑ）に読み出された前述のQ_Eが終了
マークを示すまで、以下に述べる第１５図ケ側の
処理を実行し（第１５図ク，Ｎ）、終了マークが
現われると第１５図シ側の処理に入る（第１５図
ク，Ｙ）。

第１５図ケの実行に入ると、下記のような処理
が行なわれる。

すなわち、特徴点レジスタ１２０２（Ｘ）およ
び１２０３（Ｙ）に格納された前述のそれぞれの
内容X_EAおよびY_EAは２乗計算器１２０９（X²）
および１２１０（Y²）でそれぞれ２乗され、加
算器１２１１で加算され、ライン１２１１０に
X² _EA＋Y² _EAの出力を生じこれは比較器１２１３
の一方の入力に加えられる。一方、特徴点レジス
タ１２０２（Ｘ）および１２０３（Ｙ）に格納さ
れている内容X_EAおよびY_EAのそれぞれの符号ビ
ツト（これをそれぞれSXおよびSYで表わす）が
２ビツトのデータ（SY，SX）としてライン１２
０２３を介して読し出される。この２ビツトのデ
ータ（SY，SX）で表わされる２進数はX_EA，
Y_EAで指示される特徴点の位置が、局所座標系の
それぞれ第１象限、第２象限、第３象限および第
４象限にある場合には、それぞれ（０，０）＝０，
（０，１）＝１，（１，１）＝３および（１，０）＝
２という値をとることになる。制御部１２１４は
ライン１２１４０を介して入力選択器１２０８に
制御信号を送り、上述の２ビツトデータ（SY，
SX）を選択し、これをライン１２０８０を介し
てレジスタフアイルに１２１２のフアイルアドレ
ス指定信号として供給する。

この結果、レジスタフアイル１２１２の中の、
（SY，SX）で指定されるレジスタ（つまり、特
徴点レジスタに格納された特徴点が存在する象限
に対応するレジスタ）の距離フイールドの内容Ｒ
（SY，SX）がライン１２１２０を介して読み出
され、比較器１２１３のもう一方の入力に供給さ
れる。

これにより、比較器１２１３は上述の、Ｒ
（SY，SX）の値と前述のX² _EA＋Y² _EAの値とを比
較し、現在までに得られている値Ｒ（SY，SX）
よりも同じ象限内に、今回座標原点により近い特
徴点が現われた場合、つまり Ｒ（SY，SX）＞X² _EA＋Y² _EA が成立した場合にはライン１２１３０に“１”を
出力する。

一方、アドレスレジスタ１２０５（Ａ）の内容
と、アドレスレジスタ１２０６（Ｅ）の内容とは
一致検出器１２１５において比較されており、両
者が一致している場合、つまり、もとの特徴点と
比較すべき特徴点とが同りものである場合にはラ
イン１２１５０に“１”を出力して禁止ゲート１
２１６の通過を禁止する。

この結果、 Ｒ（SY，SX）＞X² _EA＋Y² _EA Ａ≠Ｅ (1) の両方の条件が成立するときにかぎりライン１２
１６０が“１”になる（第１５図ケ，Ｙ側）。

ライン１２１６０に“１”が出力されると、レ
ジスタフアイル１２１２が書込み状態に制御さ
れ、レジスタフアイル１２１２の中の前述の２ビ
ツトデータ（SY，SX）で指定されるレジスタの
内容が更新される。すなわち、新らしい特徴点を
指定するアドレスレジスタ１２０６（Ｅ）の内容
Ｅがライン１２０６０を介してアドレスフイール
ドＭ（SY，SX）に格納され、また、加算器３１
１の出力X² _EA＋Y² _EAの値がライン１２１１０を
介して距離フイールドＲ（SY，SX）に格納され
る（第１５図コ）。

これがすむと制御部１２１４は、定数加算器１
２０７を用いたアドレスレジスタ１２０６（Ｅ）
の内容を１だけ増加し次の比較すべき特徴点を指
示するように更新し（第１５図サ）、再び次の特
徴点を読み出す処理（第１５図キ）に戻る。

また、前述の(1)式の条件が成立しない場合、つ
まり、今回読み出した比較すべき特徴点の位置
が、すでに得られている同じ象限内の特徴点の位
置よりも原点（もとの特徴点）に近くない場合
か、またはこの比較すべき特徴点がもとの特徴点
と同じものである場合にはレジスタフアイル１２
１２の内容を更新することなく（第１５図ケ，
Ｎ）、アドレスレジスタ１２０６（Ｅ）の内容を
１だけ増加して次の比較すべき特徴点を指示する
ように更新し（第１５図サ）、再び次の特徴点を
読み出す処理（第１５図キ）に戻る。

かくして、第１５図のキ，ク，ケ，コ，サの処
理を繰り返すことにより、制御部１２１４は比較
すべき新らしい特徴点をつぎつぎに読み出し、も
との特徴点できまる局所座標系の各象限ごとに、
もとの特徴点により近い他の特徴点が現われるた
びに、この特徴点のデータを用いてフアイル１２
１２の内容を更新する。この処理を、第４図の特
徴点リストメモリ２１１に貯わえられている特徴
点の終りが現れるまで（読み出されたQ_Eに終了
マークが現われるまで）繰り返す。

以上の処理が終ると、レジスタフアイル１２１
２のアドレスフイールドＭ０〜Ｍ３の中には、ア
ドレスレジスタ１２０５（Ａ）で指定されるもと
の特徴点に対し、最も近い位置にある他の特徴点
の番号（ロウアドレス）が各象限ごとに別々に求
められたことになる。

そこで次に、こうして求められたフアイル１２
１２のアドレスフイールドＭ０〜Ｍ３の内容を、
アドレスレジスタ１２０５（Ａ）で指定される、
特徴点リストメモリ２１の最近傍特徴点格納位置
M_A0〜M_A3に格納する。

この最近傍特徴点格納処理にうつると、制御部
１２１４は、もとの特徴点のコラムアドレスを指
示するアドレスレジスタ１２０５（Ｂ）の内容
を、最近傍特徴点格納位置の最初を指示する値と
して４に初期値設定する（第１５図シ）。

また、これとともにライン１２１４０の出力を
入力選択器１２０８がライン１２０６０を選択す
るように切替える。この１２０６０にはアドレス
レジスタ１２０５（Ｂ）の下位２ビツト分が供給
されているため、これにより、レジスタフアイル
１２１２の中の各レジスタからの読み出しは、ア
ドレスレジスタ１２０５（Ｂ）の下位２ビツト分
（つまりＢから４を引いた値）で指定される。

さて、レジスタフアイル１２１２の上述のよう
にして指定されるアドレスフイールドＭ（Ｂ−４）
の内容は、読み出され、ライン１２１２１
（WD）を介して特徴点リストメモリ２１１の書
き込みデータとして供給される。一方、アドレス
レジスタ１２０５（Ａ）の内容および１２０５
（Ｂ）の内容はライン１２０５６（AD）を介し
て第４図の特徴点リストメモリ２１１のそれぞれ
ロウアドレスおよびコラムアドレス指定データと
して供給されている。このため制御部１２１４は
書き込みパルスをライン１２１４１（Ｗ）を介し
て特徴点リストメモリ２１１に供給することによ
り、上述のフアイル１２１２のＭ（Ｂ−４）のデ
ータを特徴点リストメモリ２１１の最近傍特徴点
格納位置M_ABに転送格納することができる（第１
５図ス）。

この転送がすむと、制御部１２１４は、定数加
算器１２０７を用いてアドレスレジスタ１２０５
（Ｂ）の内容を１だけ増加し、次のフアイルアド
レスおよびコラムアドレスを指示するように更新
する（第１５図ス）。

以上の処理を１２０５（Ｂ）の値がオーバフロ
ーして０になるまで繰り返すと（第１５図セ，
Ｙ）、アドレスレジスタ１２０５（Ａ）で指定さ
れるもとの特徴点に対するすべての最近傍特徴点
の格納が終了するので、制御部１２１４は、定数
加算器１２０７を用いてアドレスレジスタ１２０
５（Ａ）の内容に１を加えて、次のリレーシヨン
データを求めるべきもとになる特徴点を指示する
ように更新する（第１５図ソ）。

かくして、この新らしいもとになる特徴点の各
データが読み出され、第１１図の座標変換回路２
１２のパラメータレジスタ１１１０〜１１１２に
格納され、この新しい特徴点に対する局所座標系
を構成する処理（第１５図ウ）に戻る。

こうして、レジスタ１２０５（Ａ）の内容が更
新され、もとになる特徴点を新らしく指定するご
とに、その特徴点に対する局所座標系が構成さ
れ、第１５図のキ，ク，ケ，コ，サのループによ
り、他の全部の特徴点が順番に検査され、これら
の中からこの局所座標系の各象限における最近傍
点を指示するデータがレジスタフアイル１２１２
中に生成される。これがすむと第１５図のス，セ
のループで、これらをもとの特徴点に対する最近
傍特徴点として特徴点リストメモリ２１１の最近
傍特徴点格納位置に転送される。

以上のような形で制御部１２１４により処理が
繰り返えされるが、こうして、すべての特徴点に
対するレジスタ１２０５（Ａ）の指定がすむと、
特徴点リストメモリ２１１のすべての最近傍特徴
点の生成が完了され、レジスタ１２０５（Ａ）の
つぎの更新により、終了マークが読み出され（第
１５図エ，Ｙ）、処理が終了する（第１５図オ）。

以上述べたように、一つの紋様パターンの各特
徴点の位置と方向とが与えられた場合に、これら
各特徴点の近傍の状態を把握するための情報とし
て、各特徴点ごとに定まる局所座標系を用い、こ
の各象限における他の最近傍特徴点を見出すこと
により、もとの特徴点に対する最近傍特徴点を比
較的簡単なアルゴリズムにより高速で生成するこ
とができる。

こうして生成された最近傍特徴点は、各特徴点
の位置方向を表わすもとのデータと異つて、中心
座標系の選び方と無関係な量であるため、中心座
標系が整合されていない二つの紋様パターンの照
合を行なう場合にまず必要となる対候補リストを
作成するための有力な材料を提供する。

(4) 対検査動作の一例 第１６図を参照すると、第４図の対検査回路２
１４の一例は、リレーシヨン連結部２１４１、特
徴点記憶部２１４２および対検査部２１４３から
構成されている。

以下１個の特徴点に対する特徴点データとその
特徴点に関する最近傍特徴点の特徴点番号および
そのリレーシヨンからなる基本リレーシヨンデー
タとを総称するときはこれを総特徴点データと
いゝ、１個の指紋に対するすべての総特徴点デー
タまたは後述の総連結データを総称するときはこ
れを指紋データという。

リレーシヨン連結部２１４１は、特徴点リスト
メモリ２１１に格納された指紋データの各特徴点
の基本リレーシヨンデータ中の最近傍特徴点の特
徴点番号をその特徴点に関する局所座標の位置デ
ータおよび方向データに変換してリレーシヨン連
結データを生成し、これを特徴点記憶部２１４２
に送つて格納するように結合されている。

特徴点記憶部２１４２に格納される総連結デー
タは、第１７図に示すように各特徴点について特
徴点データとリレーシヨン連結データ（リレーシ
ヨンrij，位置データxij・yij，方向データdij）と
からなつている。

「対」検出部２１４３は特徴点記憶部２１４２
から探索指紋およびフアイル指紋のそれぞれ１個
の特徴点の総連結データを取出して「対」となる
べき特徴点を検出する役割を荷つており、この
「対」検出部で検出された「対」の特徴点に関す
る総連結データの組合せは第４図の対候補リスト
メモリ２１５に送られて格納される。

ここで、「対」とは、探索指紋のすべての特徴
点のおのおのに対して、それらの総特徴点データ
または総連結データとフアイル指紋の各特徴点の
総特徴点データまたは総連結データが一致する特
徴点の組合せをいう。当初の比較一致判断のとき
は探索指紋の１個の特徴点に対してフアイル指紋
の複数の特徴点が比較一致と判断されて１：ｎ
（ｎ≧２）の組合せとなる場合がある。この１：
ｎの組合せは更に処理を施されて１：１の「対」
となるが、以下の説明では１：ｎの組合せについ
ても「対」という。

第４図の特徴点リストメモリ２１１に格納され
るデータは、１個の特徴点に関してその特徴点種
別Ｑ１，集密量（Ci），位置データ（Xi，Yi），
方向データ（Di）および最近傍特徴点のすべて
の基本リレーシヨンデータ（rij，Mj）を１組と
した総特徴点データの１指紋分の集りであり、こ
れらはリレーシヨン連結部２１４１からアドレス
信号２１４６をうけてデータ信号２１４４によつ
てリレーシヨン連結部２１４１に順次出力され
る。

リレーシヨン連結部２１４１は、アドレス信号
２１４６によつて特徴点リストメモリ２１１ａか
ら最近傍特徴点の基本リレーシヨンの順次読出す
と、この基本リレーシヨンデータ中に含まれる特
徴点番号（Mj）をその特徴点に関する局所座標
による位置データ（xij，yij）および方向データ
（dij）に変換してリレーシヨン（rij）と共にデー
タ信号２１４１１によつて特徴点記憶部２１４２
に順次送出する。特徴点記憶部２１４２はこのデ
ータ信号２１４１１によつて順次送られてくるリ
レーシヨン連結データを貯えて特徴点データと共
に第１７図に示す形成で総連結データを構成し、
第１８図の探索特徴点メモリ１８０２に格納す
る。

探索指紋の１個の特徴点に関する上述のリレー
シヨン連結動作が終了すると、リレーシヨン連結
部２１４１は特徴点リストメモリ２１１ｂからフ
アイル指紋の１個の特徴点の総特徴点データを読
出し前述の探索指紋の場合と同様に総連結データ
を構成して第１８図のフアイル特徴点メモリ１８
０３に格納する。

特徴点記憶部２１４２の探索特徴点メモリ１８
０２およびフアイル特徴点メモリ１８０３にそれ
ぞれ１個の特徴点の総連結データが格納し終る
と、リレーシヨン連結部２１４１は指令信号２１
４１０によつてそのことを「対」検出部２１４３
に知らせるので、「対」検出部２１４３はアドレ
ス信号２１４３１を送つてそれらをデータ信号２
１４２１によつて読出す。

一方リレーシヨン連結部２１４１はこの間にフ
アイル指紋の２番目の総特徴点データを読出し、
特徴点記憶部２１４２のバツフアメモリの空きを
利用してリレーシヨン連結動作を行い、フアイル
特徴点メモリ１８０３のデータが「対」検出部２
１４３に読出されたあとにそれを格納する。

特徴点記憶部２１４２に格納されて「対」検出
部２１４３に読出された探索指紋およびフアイル
指紋の特徴点の総連結データは、「対」検出部２
１４３において「対」関係の有無が検査され、探
索指紋の特徴点の総連結データとフアイル指紋の
特徴点の総連結データとが所定のしきい値内で一
致するとき、これらの総連結データの組合せはデ
ータ信号２１４７によつて第４図の対候補リスト
メモリ２１５に送られ、アドレス信号２１４５に
指定された番地に格納される。

上述のリレーシヨン連結動作と「対」検出動作
は、先づ探索指紋の第１番目の特徴点に対してフ
アイル指紋のすべての特徴点について行われ、こ
れが終ると探索指紋の第２番目の特徴点に対して
同様にフアイル指紋の全特徴点について行われ、
以下これを繰返して探索指紋とフアイル指紋のす
べての特徴点の組合せについて行われる。

探索指紋とフアイル指紋のすべての特徴点の組
合せについての上記「対」検出動作が終了してす
べての「対」が対候補リストメモリ２１５に格納
されると、シーケンス制御回路２１０は「対」検
出部２１４３から指令信号２１４８によつてその
ことが知らされる。

第１９図を参照すると、リレーシヨン連結部２
１４１は制御回路４０１０によつて制御されるシ
フトレジスタ４０１，Ｘレジスタ４０２Ｘ，Ｙレ
ジスタ４０２Ｙ，Ｄレジスタ４０２Ｄと、Ｘレジ
スタ４０２Ｘ，Ｙレジスタ４０２Ｙ，Ｄレジスタ
４０２Ｄに保存されている位置データまたは方向
データとデータ信号２１４４により直接入力され
る位置データまたは方向データとの減算処理を行
う減算器４０３Ｘ，４０３Ｙおよび４０３Ｄと、
Ｄレジスタの出力を受けて円関数を発生する円関
数発生器４０４と、減算器４０３Ｘ，４０３Ｙの
出力と円関数発出器４０４の出力とを受けてそれ
らの乗算処理を行う乗算器４０５Ｘ，４０５Ｙ，
４０６Ｘ，４０６Ｙと乗算器４０５Ｘおよび４０
６Ｘならびに乗算器４０５Ｙおよび４０６Ｙの出
力を受けてそれらの加算または減算処理を行う加
算器４０７Ｘおよび減算器４０７Ｙとから構成さ
れている。

このリレーシヨン連結部２１４１は、特徴点リ
ストメモリ２１１からデータ信号２１４４によつ
て送られてくる例えば特徴点Maの総特徴点デー
タを受けると、制御回路４０１０１からの指令信
号４００１によつてシフトレジスタ４０１に基本
リレーシヨンデータra，M〜rak，Mkを格納
すると共にＸレジスタ４０２Ｘ，Ｙレジスタ４０
２ＹおよびＤレジスタ４０２Ｄに位置データX_a，
位置データY_aおよび方向データD_aを格納する。
なおこのとき特徴点データQa，Ca，Xa，Ya，
Daはデータ信号２１４１１およびアドレス信号
２１４１２によつて特徴点記憶部２１４２のバツ
フアメモリ１８０１Ａにも格納される。

一方特徴点種別Qaはデータ信号４０００によ
つて制御回路４０１０に入力され、制御回路４０
１０はこれによつて特徴点であることを確認して
シフトレジスタ４０１に指令を与え、シフトレジ
スタ４０１はこの指令を受けて第一番目の最近傍
特徴点の特徴点番号Mをデータ信号４０１１に
よつて制御回路４０１０に送出する。制御回路４
０１０はこれによつてアドレス信号２１４６を特
徴点リストメモリ２１１に送出して該メモリ２１
１に格納してある１次最近傍特徴点Mの総特徴
点データのうち位置データX，Yおよび方向デ
ータDを読み出す。

前記メモリ２１１からデータ信号２１４４によ
つて読出された位置データX，Yおよび方向デ
ータDは、たゞちに減算器４０３Ｘ，４０３Ｙ
および４０３Ｄに入力されるので、減算器４０３
Ｘ，４０３Ｙおよび４０３Ｄはこのとき制御回路
４０１０からの指令によつてＸレジスタ４０２
Ｘ，Ｙレジスタ４０２ＹおよびＤレジスタ４０２
Ｄから入力される特徴点Maの位置データX_a，Y_a
および方向データD_aとによつてその差ΔX_a，
ΔY_a，ΔD_aを算出し、減算器４０３Ｘおよび４
０３Ｙの出力は、それぞれ乗算器４０５Ｘ，４０
６Ｘおよび乗算器４０５Ｙ，４０６Ｘに送られ
る。

一方Ｄレジスタ４０２Ｄからの方向データD_a
は並行して円関数発生器４０４に入力され、円関
数発生器４０４において計算された円関数値
cosD_aおよびsinD_aはデータ信号４０４１および
４０４２によつて乗算器４０５Ｘ，４０５Ｙおよ
び乗算器４０６Ｘ，４０６Ｙに送出される。

４個の乗算器４０５Ｘ，４０５Ｙ，４０６Ｘお
よび４０６Ｙは上記のように減算器４０３Ｘ，４
０３Ｙおよび円関数発生器４０４からの出力を受
け、それぞれΔX_acosD_a，ΔY_acosD_a，ΔY_a
sinD_a，およびΔX_asinD_aの演算を行つてそれら
の出力を加算器４０７Ｘおよび減算器４０７Ｙに
送出するので、加算器４０７Ｘおよび減算器４０
７Ｙはこれらを入力して x_a＝ΔX_acosD_a＋YX_asinD_a y_a＝ΔY_acosD_a−ΔX_asinD_a の演算を行つてそれらの結果を減算４０３Ｄの出
力である方向データd_aとこのときシフトレジス
タ４０１から出力されるリレーシヨンr_aとをリ
レーシヨン連結データとしてデータ信号２１４１
１によつて特徴点記憶部２１４２のバツフアメモ
リ１８０１Ａに送つて格納する。

第一の最近傍特徴点Mに関する上述のリレー
シヨン連結動作およびその格納動作を終了する
と、制御回路４０１０はシフトレジスタ４０１に
指令信号４００２を送出して第二の最近傍特徴点
の特徴点番号Mgの送出を受け、以下上述の動作
を繰返してすべての最近傍特徴点に対してリレー
シヨン連結動作とその格納動作を実行する。

すべての最近傍特徴点に対する上述のリレーシ
ヨン連結動作とその格納動作が終了すると、リレ
ーシヨン連結部２１４１は引続き特徴点リストメ
モリ２１１からフアイル指紋の第一番目の特徴点
の総特徴点データを読出し、前述のリレーシヨン
連結動作を行つてバツフアメモリ１８０１Ｂに格
納する。

特徴点記憶部２１４７は、上述のフアイル指紋
の第一番目の特徴点のリレーシヨン連結データの
格納動作の間に、制御回路４０１０からの指令信
号２１４９による指令によつてバツフアメモリ１
８０１Ａに格納した探索指紋の第一番目の特徴点
の総連結データを探索特徴点メモリ１８０２に移
す。

リレーシヨン連結部２１４１におけるフアイル
指紋の第一番目の特徴点に関するリレーシヨン連
結動作が完了してバツフアメモリ１８０１Ｂに格
納し終るとこの総連結データは制御回路４０１０
の指令によつてフアイル特徴点メモリ１８０３に
移され、この間にフアイル連結動作が行われてそ
のデータはバツフアメモリ１８０１Ａに格納され
る。

探索指紋およびフアイル指紋の総連結データを
それぞれ探索特徴点メモリ１８０２およびフアイ
ル特徴点メモリ１８０３に格納し終ると制御回路
４０１０から指令信号２１４１０が「対」検出部
２１４３に送られるので、「対」検出部２１４３
はこの指令信号２１４１０を受けて探索特徴点メ
モリ１８０２およびフアイル特徴点メモリ１４０
３にアドレス信号２１４３１を送つてこれらに格
納されている総連結データを読出し「対」検出動
作を行う。

「対」検出部２１４３による探索特徴点メモリ
１８５０２およびフアイル特徴点メモリ１８５０
３からの読出しが完了すると、特徴点記憶部２１
４２は制御回路４０１０の指令によつてバツフア
メモリ１８０１Ａに格納されているフアイル指紋
の第二番目の特徴点の総連結データをフアイル特
徴点メモリ１８０３に移すと共にバツフアメモリ
１８０１Ｂにフアイル指紋の第三番目の特徴点の
総連結データを格納する。

以下上述のリレーシヨン連結動作とその格納動
作および総連結データの読出しとそれによる
「対」検出動作を２個のバツフアメモリ１８０１
Ａおよび１８０１Ｂを交互に使つて繰返し行い、
探索指紋の１個の特徴点に対してフアイル指紋の
すべての特徴点が検査されると、バツフアメモリ
１８０１Ａまたは１８０１Ｂの空いている方を使
つて探索指紋の第二番目の特徴点に関するリレー
シヨン連結動作とその探索特徴点メモリへの格納
動作を行う。

上述の動作を探索指紋およびフアイル指紋のす
べての特徴点に対して行うことによつて１個の探
索指紋と１個のフアイル指紋の「対」検出動作が
完了する。

第２０図を参照すると、第１６図に「対」検出
部２１４３は、探索特徴点メモリ１８０２および
フアイル特徴点メモリ１８０３から比較判定すで
き特徴点の総連結データを入力して集密量または
リレーシヨンと位置データおよび方向データとの
減算処理を行う減算器７０１Ｒ，７０１Ｘ，７０
１Ｙ，７０１Ｄと、これらの減算器７０１Ｒ，７
０１Ｘ，７０１Ｙ，７０１Ｄからの出力とを入力
してそれらの値を比較する比較器７０２Ｒ，７０
２Ｘ，７０２Ｙ，７０２Ｄと、これらの比較器７
０２Ｒ，７０２Ｘ，７０２Ｙ，７０２Ｄの出力を
入力するアンド回路７０６と、このアンド回路７
０６の出力を入力して計数し制御回路７００の指
令によつてリセツトされるカウンタ７０７と、探
索指紋およびフアイル指紋のリレーシヨンを入力
して、それらが最近傍特徴点が存在しないとき付
与される特定のコードであるか否かを判別するリ
レーシヨンコード検出部７０４と、このリレーシ
ヨンコード検出器の出力を入力して計数し、制御
回路７００によつてリセツトされるカウンタ７０
５と、カウンタ７０５の出力を入力することによ
つて送出されるしきい値発生器７０３からの出力
とカウンタ７０７からの出力とを入力してそれら
の値を比較判定する比較器７０８とを備えて構成
されている。

上述のように構成された「対」検出部２１４３
は以下のように動作する。すなわち、制御回路７
００がリレーシヨン連結部２１４１からの指令信
号２１４１０を受けると、アドレス信号２１４３
１を探索特徴点メモリ１８０２およびフアイル特
徴点メモリ１８５０３に送出し、比較すべき探索
指紋およびフアイル指紋のそれぞれの特徴点、例
えばM^S _a，M^F _aの特徴点データのうち集密量（C^S _a，
C^F _a），位置データ（X^S _a，X^F _a；Y^S _a，Y^F _a），方向デー
タ（D^S _a，D^F _a）をそれぞれ減算器７０１Ｒ，７０
１Ｘ，７０１Ｙ，７０１Ｄに入力し（M^S _a，M^F _a等
の添字Ｓは探索指紋、添字Ｆはフアイル指紋に関
する特徴点番号またはデータを示す）、減算器７
０１Ｒ，７０１Ｘ，７０１Ｙ，７０１Ｄはそれら
の差の絶対値｜C^S _a−C^F _a｜，｜X^S _a−X^F _a｜，｜Y^S _a−Y^F _a
｜，｜D^S _a−D^F _a｜を算出してその値をれぞれ比較器
７０２Ｒ，７０２Ｘ，７０２Ｙ，７０２Ｄに送出
する。

比較器７０２Ｒ，７０２Ｘ，７０２Ｙ，７０２
Ｄは、これらの減算器７０１Ｒ，７０１Ｘ，７０
１Ｙ，７０１Ｄからの出力と、制御回路７００か
らの指令信号７００３によつてしきい値発生器７
０３から送出されるしきい値データ（T_C，T_X，
T_Y，T_D）を入力してそれぞれ ｜C^S _a−C^F _a｜T_C，｜X^S _a−X^F _a｜T_X ｜Y^S _a−Y^F _a｜T_Y，｜D^S _a−D^F _a｜T_D を比較判定し、その結果をアンド回路７０６に出
力し、アンド回路７０６は上記の比較器７０２
Ｒ，７０２Ｘ，７０２Ｙ，７０２Ｄからの出力が
すべてオンのとき、その出力を制御回路７００に
送出する。

制御回路７００はこのアンド回路７０６からの
出力を受けると、指令信号７００１および７００
２に送出してカウンタ７０５および７０７をリセ
ツトすると共に、アドレス信号２１４３１を送つ
て探索特徴点メモリ１８０２およびフアイル特徴
点メモリ１８０３なら第１のリレーシヨン連結デ
ータ（r^S _af，x^S _af，y^S _af，d^S _afおよびr^F _af，x^F _af，y^S _af
，d^S _af）
を読出し、上記の特徴点データの場合と同様に減
算器７０１Ｒ，７０１Ｘ，７０１Ｙ，７０１Ｄお
よび比比較７０２Ｒ，７０２Ｘ，７０２Ｙ，７０
２Ｄによつて ｜r^S _af−r^F _af｜Tr，｜x^S _af−x^F _af｜Tx， ｜y^S _af−y^F _af｜Ty，｜d^S _af−d^F _af｜Td （Tr，Tx，Ty，Tdはそれぞれリレーシヨン，
位置データｘ，位置データｙ，方向データｄに関
するしきい値） を算出しその結果をアンド回路７０６に送出し、
アンド回路７０６は比較器７０２Ｒ，７０２Ｘ，
７０２Ｙ，７０２Ｄからの出力がすべてオンのと
きその出力を制御回路７００に送出する。制御回
路７００はこの出力を受けて指令信号７０２を送
出してカウンタ７０７の内容を更新する。

上記の動作に先立つて、リレーシヨンr^S _af，r^F _af
が読出されたとき、これらはリレーシヨンコード
検出器７０４に入力されるので、リレーシヨンコ
ード検出器７０４は、リレーシヨンr^S _af，r^F _afのコ
ードを判定してそれらのコードの少くとも１方が
最近倣特徴点が存在しないときに付与される特定
のコードである場合は指令信号７０４０を制御回
路７００に出力すると共にカウンタ７０５を更新
し、制御回路７００は先に説明したアンド回路７
０６からの出力の有無に無関係に指令信号７００
２を出力しない。

リレーシヨン連結データ（r^S _af〜d^S _af，r^F _af〜d^F _af）
に関する上記の動作が終了すると、制御回路７０
０はアドレス信号２１４３１を探索特徴点メモリ
１８０２およびフアイル特徴点１８０３に送つて
第二のリレーシヨン連結データを読出し、これら
について前述と同一の比較判定動作を行い、以下
継続して探索指紋およびフアイル指紋の特徴点の
すべてのリレーシヨン連結データの比較判定動作
を行う。

リレーシヨン連結データに関する上記の比較判
定動作を終了すると、制御回路７００はカウンタ
７０５に指令を与えてその内容をしきい値発生器
７０３に出力させ、しきい値発生器７０３はこの
カウンタ７０５からの出力を受けて不在最近傍特
徴点の数に対応するしきい値を比較器７０８に出
力する。

比較器７０８はこのしきい値発生器７０３から
の出力と、制御回路７００の指令によつて出力さ
れるカウンタ７０７からの出力とを受けて比較
し、カウンタ７０７の値がしきい値以上であると
きは指令信号７０８０を制御回路７００に送出
し、制御回路７００はこの指令信号７０８０を受
けて内部保持している探索特徴点番号M^S _aおよび
フアイル特徴点番号M^F _aを第４図の対修捕リスト
メモリ２１５に送り、アドレス信号２１４５によ
つて指定される番地に格納する。

上記の動作を探索指紋のすべての特徴点とフア
イル指紋のすべての特徴点のすべての組合せにつ
いて行うことによつて探索指紋とフアイル指紋と
の「対」となる特徴点をしらべて「対候補リスト
メモリ２１５１の内容が完成する。

なお上記の実施例では、特徴点記憶部２１４２
がリレーシヨン連結部２１４１および「対」検出
部２１４３に対して独立な装置である場合である
が、これは必ずしも独立である必要はなく、リレ
ーシヨン連結部２１４１または「対」検出部２１
４３の構成要素の一部として組込まれていてもよ
い。

(5) 対検査動作の変形例 第２１図を参照すると、第４図の対検査回路の
変形側２１４′は複合リレーシヨン連結部２１４
１′探索特徴点記憶部１８０２，フアイル特徴点
記憶部１８０３および複合対検出部２１４３′か
ら構成されている。

複合リレーシヨン連結部２１４１′は、第４図
の特徴点リストメモリ２１１に格納された指紋デ
ータの各特徴点の基本リレーシヨンデータを、そ
の中に含まれる１次最近傍特徴点の特徴点番号を
その特徴点に関する局所座標の位置データおよび
方向データに変換した１次リレーシヨンデータに
変換し、更に１次最近傍特徴点に関す総特徴点デ
ータから２次最近傍特徴点に関する２次リレーシ
ヨンデータを構成して各特徴点毎に特徴点データ
および１次リレーシヨンデータならびに２次リレ
ーシヨンデータ（これらを総称して総連結データ
という）を探索特徴点記憶部１８０２またはフア
イル特徴点記憶部１８０３へ送つて格納するよう
に結合されている。

探索特徴点記憶部１８０２またはフアイル特徴
点記憶部１８０３に格納される総連結データは、
第２２図に示すように各特徴点について特徴点デ
ータと１次リレーシヨンデータ（リレーシヨン
rij，位置データxij，yij、方向データdij）と２次
リレーシヨンデータ（２次リレーシヨンrik，位
置データxik・yik，方向データdik）とからなつ
ている。

複合「対」検出部２１４３′は探索特徴点記憶
部１８０２およびフアイル特徴点記憶部１８０３
からそれぞれ１個の総連結データを取出して
「対」となるべき特徴点を検出する役割を荷つて
おり、この複合「対」検出部で検出された「対」
の特徴点番号の組合せは、対候補リストメモリ２
１５に送られて格納される。

特徴点リストメモリ２１１に格納されるデータ
は、１個の特徴点に関してその特徴点種別
（Qi）、集密度（Ci）、位置データ（Xi，Yi）、方
向データ（Di）および１次最近傍特徴点のすべ
ての基本リレーシヨンデータ（rij，Mj）を１組
とした総特徴点データの１指紋文の集りであり、
これらはデータ信号２１４６によつて複合リレー
シヨン連結部２１４１′に順次出力される。

複合リレーシヨン連結部２１４１′は、アドレ
ス信号２１４４によつて特徴点リストメモリ２１
１から基本リレーシヨンデータを読出すと、この
基本リレーシヨンデータ中に含まれる１次最近傍
特徴点の特徴点番号Mjをその特徴点に関する局
所座標による位置データxij，yijおよび方向デー
タdijに変換してリレーシヨンrijと共に１次リレ
ーシヨンデータを構成し、更にアドレス信号２１
４４によつて特徴点リストメモリ２１１から１次
最近傍特徴点Mjの総特徴点データを読出して２
次最近傍特徴点の１次最近傍特徴点の局所座標に
関する位置データxik，yikおよび方向性データ
dikと２次リレーシヨンrikを生成して２次リレー
シヨンデータを構成して、これらを特徴点データ
と共に総連結データとしてデータ信号２１４１１
によつて探索特徴記憶部１８０２に送出し、探索
特徴記憶部１８０２は、このデータ信号２１４１
１を受けてアドレス信号２１４２によつて第２２
図に示す形式で指定された番地に格納する。

上記の動作を繰返して１個の探索指紋に関する
すべての特徴点の総連結データの格納が終了する
と、複合リレーシヨン連結部２１４１′はフアイ
ル指紋の指紋データを順次読出し探索指紋の場合
と同様にリレーシヨン連結動作を行つて総連結デ
ータをデータ信号２１４１１によつてフアイル特
徴点記憶部１８０３に出力する。フアイル特徴点
記憶部１８０３はアドレス信号２１４１３の指定
に従つてこの総連結データを指定の番地に格納
し、この動作を繰返してフアイル指紋のすべての
特徴点の総連結データを格納する。

探索特徴点記憶部１８０２およびフアイル特徴
点記憶部１８０３に格納された指紋データは、そ
の詳細を後述する複合「対」検出部２１４３′に
おいてそれらの特徴点のすべての組合せについて
「対」関係の有無が検査され、探索指紋の特徴点
の総連結データとフアイル指紋の特徴点の総連結
データとが所定のしきい値内で一致するとき、そ
れらの特徴点番号の組合せは、データ信号２１４
５によつて対候補リストメモリ２１５１に送ら
れ、アドレス信号２１４８に指定された番地に格
納される。

第２１Ａ図は、基準となる特徴点Maに対する
第１次最近傍特徴点Mf，Mg，Mh，Mkと、前
記第１次最近傍特徴点のそれだけに対する第２次
最近傍特徴点の関係を示している。例えば、Ma
を原点とする座標系における第１象限の最近傍特
徴点MfでありMfを原点とする局所座標系におけ
る第１象限の最近傍特徴点はMlであり、この特
徴点Mlは、特徴点Maに対する第２次最近傍特徴
点の１つである。

一般の第１次リレーシヨンデータによる照合に
対して、さらに第２次リレーシヨンデータを用い
て照合することは、信頼性の高い照合を行なう上
で極めて有力な方法となる。なぜなら基準座標又
は局所座標の座標の中心及び方向は設定作業上多
少の誤差が生ずるのは避けることはできない。こ
の場合、例えば第２１Ａ図に示すように特徴点
Maに関する局所座標Xa，Yaが局所座標Xa′，
Ya′に設定されると、第１次最近傍特徴点Mf，
Mg，Mh，Mkのうち特徴点Mkは、座標軸Xa′，
Ya′に対しては、第１次近傍特徴点Mfと同一象
限となるため第１次最近傍特徴点とはならず代り
に特徴点Muが第１次最近傍特徴点となつてしま
うという幣害が生じる。この点上記第２次最近傍
特徴点を加えて、第１次リレーシヨンデータ間及
び第１次リレーシヨンデータと第２次リレーシヨ
ンデータ相互間を比較すれば上記幣害を除くこと
が可能となる。

前記複合リレーシヨン回路部２１４１′の構成
は第１９図に示した前記リレーシヨン連結部２１
４１の構成と同一である。

この動作は次のようにして行なわれる。

第１９図は参照すると、複合リレーシヨン連結
部２１４１′は特徴点リストメモリ２１１からデ
ータ信号２１４４によつて送られてくる例えば特
徴点Maの総特徴点データを受けると、制御回路
４０１０からの指令信号４００１によつてシフト
レジスタ４０１に基本リレーシヨンデータraf，
Mf〜rak，Mkを格納すると共にＸレジスタ４０
２Ｘ、Ｙレジスタ４０２ＹおよびＤレジスタ４０
２Ｄに位置データX_a、位置データY_aおよび方向
データD_aを格納する。なおこのとき特徴点デー
タQa，Ca，Xa，Ya，Daはデータ信号２１４１
１およびアドレス信号２１４１２によつて探索特
徴点記憶部８０２またはフアイル特徴点記憶部１
８０３に書込まれる。（第２２図参照）。

一方、特徴点種類Qaはデータ信号４０００に
よつて制御回路４０１０に入力され、制御回路４
０１０はこれによつて特徴点であることを確認し
てシフトレジスタ４０１に指令を与え、シフトレ
ジスタ４０１はこの指令を受けて第一番地の１次
最近傍特徴点の特徴点番地Mfをデータ信号４０
１１によつて制御回路４０１０に送出する。制御
回路４０１０はこれによつてアドレス信号２１４
６を特徴点リストメモリ２１１に送出して特徴点
リストメモリ２１１に格納してある１次最近傍特
徴点Mfの総特徴点データを読み出し、このうち
の基本リレーシヨンデータをシフトレジスタ４０
１に格納する。

一方、特徴点リストメモリ２１１からのデータ
信号２１４４によつて読出された総特徴点データ
のうち位置データXf，Yfおよび方向データDf
は、たゞちに減算器４０３Ｘ，４０３Ｙおよび４
０３Ｄに入力されるので、減算器４０３Ｘ，４０
３Ｙおよび４０３Ｄはこのとき制御回路４０１０
からの指令によつてＸレジスタ４０２Ｘ，Ｙレジ
スタ４０２ＹおよびＤレジスタ４０２Ｄから入力
される特徴点Maの位置データX_a，Y_aおよび方向
データDaとによつてその差ΔXaf，ΔYaf，ΔDaf
を算出し、減算器４０３Ｘおよび４０３Ｙの出力
はそれぞれ乗算器４０５Ｘ，４０６Ｙおよび乗算
器４０５Ｙ，４０６Ｙに送られ、減算器４０３Ｄ
の出力はデータ信号２１４６によつて探索特徴点
記憶部１８０２またはフアイル特徴点記憶部１８
０３へ送られる。

一方、Ｄレジスタ４０２Ｄからの方向データ
D_aは並行して円関数発生器４０４に入力され、
円関数発生器４０４において計算された円関数値
cosDaおよびsinDaはデータ信号４０４１および
４０４２によつて乗算器４０５Ｘ，４０５Ｙおよ
び乗算器４０６Ｘ，４０６Ｙに送出される。

４個の乗算器４０５Ｘ，４０５Ｙ，４０６Ｘお
よび４０６Ｙは上記のように減算器４０３Ｘ，４
０３Ｙおよび円関数発生器４０４からの出力を受
け、それぞれΔXafcosDa，ΔYafcosDa，
ΔYafsinDa、およびΔXafsinDaの演算を行つて
それらの出力を乗算器４０７Ｘおよび減算器４０
７Ｙに送出すので加算器４０７Ｘよび減算４０７
Ｙはこれらを入力して xaf＝ΔXafcosDa＋ΔYafsinDa yaf＝ΔYafcosDa−ΔXafsinDa の演算を行つてそれらの結果をデータ信号２１４
１１によつて探索特徴点記憶部１８０２またはフ
アイル特徴点記憶部１８０３へ送出し、探索特徴
点記憶部１８０２またはフアイル特徴点記憶部１
８０３はこれらのデータと減算器４０３Ｄからの
出力である方向データdafおよびシフトレジスタ
４０１から送られてくるリレーシヨンrafとを最
近傍特徴点Mfに関する１次リレーシヨンデータ
としてアドレス２１４１２または２１４１９によ
つて指定される番地に格納する。（第２２図参照） 第一の１次最近傍特徴点Mfに関する上述のリ
レーシヨン連結動作を終了すると、制御回路４０
１０はシフトレジスタ４０１に指令信号４００２
を送出して第二の最近傍特徴点の特徴点番号Mg
の送出を受け、以下上述の動作を繰返してすべて
の１次最近傍特徴点に対して実行する。

１次最近傍特徴点に対応する上述のリレーシヨ
ン連結動作を終了すると、複合リレーシヨン連結
部２１４１′は、既にシフトレジスタ４０１に格
納してある第１の２次最近傍特徴点の特徴点番号
Mlによつてその位置データXl，Ylおよび方向デ
ータDlを読出し、既述の手順と全く同一の手順
で２次リレーシヨンデータを構成する位置データ
xal，yalと方向データdalを演算して送出すると
共に、シフトレジスタ４０１からリレーシヨン
rflを送出して２次リレーシヨン演算器（図示せ
ず）に入力し、別途１次リレーシヨンレジスタ
（図示せず）に格納してある１次リレーシヨンraf
とによつて所定の演算方法による演算を行つて
（演算方法は通常の加減算の組合せであるので詳
細説明は省略する）その結果を出力し特徴点Ml
に関する２次リレーシヨンとして探索特徴点記憶
部１８０２またはフアイル特徴点記憶部１８０３
に格納する。（第２２図参照） 以下この動作をすべての２次最近傍特徴点につ
いて行うことにより特徴点Maに関するリレーシ
ヨン連結動作を完了する。

以上の動作を１個の指紋のすべての特徴点につ
いて完了すると、制御回路４０１０は指令信号２
１４５を複合「対」検出部２１４３′に出力して
すべての動作が終了したことを知らせる。

第２３図を参照すると、複合対検出部２１４
３′の構成は、第２０図に示した対検出部２１４
３の構成とほとんど同一である。

相違点は制御回路７００からアドレス信号２１
４３の他にアドレス指定を変更したアドレス信号
７４を出力するとともにアドレス信号２１４８の
他にデータ信号２１４５を出力することにある。
以下この回路の動作を詳述する。

制御回路７００が複合リレーシヨン連結部２１
４１′から指令信号２１４１０を受けると、アド
レス信号２１４３１および２１４３２を探索特徴
点記憶部１８０２およびフアイル特徴点記憶部１
８０３に送出し、比較すべき探索指紋およびフア
イル指紋のそれぞれの特徴点例えばM^S _a，M^F _aの特
徴点データのうち集密量（C^S _a，C^F _a）、位置データ
（X^S _a，X^F _a，Y^S _a，Y^F _a）、方向データ（D^S _a，D^F _a）を
それぞれ減算器７０１Ｒ，７０１Ｘ，７０１Ｙ，
７０１Ｄに入力し減算器７０１Ｒ，７０１Ｘ，７
０１Ｙ，７０１Ｄはそれらの 差の絶対値｜C^S _a−C^F _a｜，｜X^S _a−X^F _a｜，｜Y^S _a−Y^F _a
｜，｜D^S _a−D^F _a｜ を算出してその値をそれぞれ比較器７０２Ｒ，７
０２Ｘ，７０２Ｙ，７０２Ｄに送出する。

比較器７０２Ｒ，７０２Ｘ，７０２Ｙ，７０２
Ｄは、これらの減算器７０１Ｒ，７０１Ｘ，７０
１Ｙ，７０１Ｄからの出力と、制御回路７００か
らの指令信号７００３によつてしきい値発生器７
０３から送出されるしきい値データ（T_C，T_X，
T_Y，T_D）を入力してそれぞれ ｜C^S _a−C^F _a｜T_C，｜X^S _a−X^F _a｜T_X， ｜Y^S _a−Y^F _a｜T_Y，｜D^S _a−D^F _a｜T_D を比較判定し、その結果をアンド回路７０６に出
力し、アンド回路７０６は上記の比較器７０２
Ｒ，７０２Ｘ，７０２Ｙ，７０２Ｄからの出力が
すべてオンのとき、その出力を制御回路７００に
送出する。

制御回路７００はこのアンド回路７０６からの
出力を受けると、指令信号７００１および７００
２に送出してカウンタ７０５および７０７をリセ
ツトすると共に、アドレス信号２１４３１および
２１４３２を変更して探索特徴点記憶部１８０２
およびフアイル特徴点記憶部１８０３から第１の
１次リレーシヨンデータ（r^S _af，x^S _af，y^S _af，d^S _af，お
よびr^F _af，x^F _af，y^F _af，d^F _af）を読出し、上記の特徴点
データの場合と同様に減算器７０１Ｒ，７０１
Ｘ，７０１Ｙ，７０１Ｄおよび比較器７０２Ｒ，
７０２Ｘ，７０２Ｙ，７０２Ｄによつて ｜r^S _af−r^F _af｜Tr，｜x^S _af−x^F _af｜Tx， ｜y^S _af−y^F _af｜Ty，｜d^S _af−d^F _af｜Td （Tr，Tx，Ty，Tdはそれぞれリレーシヨン、
位置データｘ、位置データｙ、方向データｄに関
するしきい値） を算出しその結果をアンド回路７０６に送出し、
アンド回路７０６は比較器７０２Ｒ，７０２Ｘ，
７０２Ｙ，７０２Ｄからの出力がすべてオンのと
きその出力を制御回路７００に送出する。制御回
路７００はこの出力を受けて指令信号７０２を送
出してカウンタ７０７の内容を更新する。

上記の動作に先立つて、リレーシヨンr^S _af，r^F _af
が読出されたとき、これらはリレーシヨンコード
検出器７０４に入力されるので、リレーシヨンコ
ード検出器７０４は、リレーシヨンr^S _af，r^F _afのコ
ードを判定してそれらのコードの少くとも１方が
最近傍特徴点が存在しないときに付与される特定
のコードである場合は指令信号７０４０を制御回
路７００に出力すると共にカウンタ７０５を更新
し、制御回路７００は先に説明したアンド回路７
０６からの出力の有無に無関係に指令信号７００
２を出力しない。

第１の１次リレーシヨンデータｒ（^S _af〜d^S _af，r^F _af
〜d^F _af）に関する上記の動作が終了すると、制御
回路７００はアドレス信号２１４３１およびアド
レス指定を変更したアドレス信号２１４３２を探
索特徴点記憶部１８０２およびフアイル特徴点記
憶部１８０３に送り、探索特徴点記憶部１８０２
からは再び第１の１次リレーシヨンデータ（r^S _af，
x^S _af，y^S _af，d^S _afを読出すと共に、フアイル特徴点記
憶部１８０３からは第２の１次リレーシヨンデー
タ（r^F _ag，x^F _ag，y^F _ag，d^F _ag）を読出し、これらにつ
いて前述と同一の比較判定動作を行い、以下継続
して探索指紋の特徴点の１次および２次リレーシ
ヨンデータとフアイル指紋の特徴点の１次および
２次リレーシヨンデータの組合せについて前述と
同一の比較判定動作を行う。

探索およびフアイル両指紋の特徴点に関する１
次および２次リレーシヨンデータの組合せの比較
判定動作は、１次および２次リレーシヨンデータ
のすべての組合せについて行つてもよいが、照合
の効率を高めるため１次リレーシヨンデータ相互
間の組合せと１次リレーシヨンデータと２次リレ
ーシヨンデータとの間の組合せについて行うよう
にしてもよい。

１次リレーシヨンデータおよび２次リレーシヨ
ンデータ間の所定の組合せのすべてについて上記
の比較判定動作を終了すると、制御回路７００は
カウンタ７０５に指令を与えてその内容をしきい
値発生器７０３に出力させ、しきい値発生器７０
３はこのカウンタ７０５からの出力を受けて不在
最近傍特徴点の数に対応するしきい値を比較器７
０８に出力する。

比較器７０８はこのしきい値発生器７０３から
の出力と、制御回路７００の指令によつて出力さ
れるカウンタ７０７からの出力とをうけて比較し
カウンタ７０７の値がしきい値以上であると指令
信号７０８０を制御回路７００に送出し、制御回
路７００はこの指令信号７０８０を受けて内部に
保持している探索指紋とフアイル指紋の特徴点番
号の組合せ（M^S _a，M^F _a）を「対」としてデータ信
号２１４５およびアドレス信号２１４８によつて
「対」候補リストメモリ２１５に送つて記憶させ
る。

上記の動作を探索指紋のすべての特徴点とフア
イル指紋のすべての特徴点のすべての組合せにつ
いて行うことによつて探索指紋とフアイル指紋と
の「対」となる特徴点をしらべて対候補メモリ２
１５の内容が完成する。

対候補リストメモリ 上述の対検査動作の結果として作成される対御
補リストメモリについて一実施例を以下に説明す
る。

第２４図を参照すると、全部で64個の異なるロ
ウアドレスと16個の異なるコラムアドレスから成
つている。任意のロウアドレスｉおよびコラムア
ドレスｊで指示される各エントリは、ペア候補指
示フイールドMijと近似度重み格納フイールド
Wijの二つのフイールドに分けられ、これらの各
フイールドには次のような形でデータが格納され
ている。

まず、各ロウアドレスはそれと同じ番号をもつ
探索指紋特徴点に対応している。すなわち、ｉ番
目の探索指紋特徴点に対し、最も高い局所的近似
度をもつフアイル指紋の特徴点が、このｉ番目の
探索指紋特徴点に対する最初の対候補として、こ
の対候補の番号（つまり候補となるフアイル指紋
特徴点の番号）がフイールドMi０に格納されて
いる。それとともにこの対候補のもつ近似度の強
さが重みとしてフイールドWi０に格納されてい
る。つぎに、同じｉ番目の探索指紋特徴点に対し
次に強い局所的近似度をもつフアイル指紋特徴点
の番号が２番目の対候補として、フイールドMij
に格納され、それとともにその近似度の強さが重
みとしてWijに格納されている。このようにして
ｉ番目の探索指紋特徴点に対するフアイル指紋特
徴点の対候補が局所的近似度の強さの順番に次々
のコラムアドレスに格納されている。局所的近似
度の強さがある一定のスレーシホールド値よりも
低くなると、このロウアドレスｉに対する対候補
リストはそこで打切られ、処理の打切りを示すた
めに重みフイールドに特定の終了マークが格納さ
れる。

(6) 座標整合量の生成および整合動作 第２５図を参照すると、前記座標整合回路２１
７の一回路例は、差平面表示メモリ６０１
（DIF）、レジスタフアイル６０２（RF１）およ
び６０３（RF２）、加算器６０４，６０５および
６０６、１加算器６０７および６０８、レジスタ
６０９（DX），６１０（DY），６１１（RK０），
６１２（RK１），６１３（RK２），６１４（MD
１Ｆ），６１５（XM）および６１６（YM）、入
力選択器６１７，６１８，６１９，６２０および
６２１、比較器６２２およびアンドゲート６２３
を含んでいる。

さて、本実施例の動作は、上述の特徴点リスト
メモリ２１１の内容、および対候補リストメモリ
２１５の内容を用い、探索指紋の座標系をγΔθだ
け回転し、Ｘ座標をΔX_T、またはＹ座標をΔY_Tだ
けそれぞれ平行移動したときに、探索指紋の特徴
点とフアイル指紋の特徴点とが最もよく整合がと
れるようなγΔθ，ΔX_T，およびΔY_Tの値を見出す
ことを目的としている。但しγは正または負の整
数、またΔθは求めるべき精度に応じて予め特定
の値に設定されるものとする。（例えばΔθ＝5.6゜） このような目的の動作を行うために、制御記憶
メモリ（図示せず）にはマイクロプログラム（マ
イクロコード）が格納されており、制御記憶２１
８の制御部（図示せず）はこのマイクロプログラ
ムをその特定の開始番地からつぎつぎに読み出
し、これを実行することにより以下に述べる処理
を進行させる。

最初にこの処理の荒筋について説明する。

まず、前記制御部は、特徴点リストメモリ２１
１と対候補リストメモリ２１５の中に格納されて
いる上述の情報を読み出し、これを処理すること
により、座標整合回路２１７に含まれている差平
面表示メモリ６０１（DIF）に差平面重みマツプ
を生成する。

この差平面重みマツプとは次のようなものであ
る。

探索指紋特徴点に対し、その座標系をある角度
γΔθだけ回転し、回転した後の特定のｉ番目の探
索指紋特徴点のＸ座標およびＹ座標の値をそれぞ
れXsiおよびYsiとする。つぎに、この探索指紋
特徴点に対する特定のｊ番目の対候補であるフア
イル指紋特徴点（このフアイル指紋特徴点を指示
する番号は対候補リストメモリ２１５の対候補指
示フイールドMijに登録されている）のＸ座標お
よびＹ座標の値をそれぞれXmijおよびYmijとす
ると、 ΔX＝Xmij−Xsi ΔY＝Ymij−Ysi ……(1) というΔX軸座標（横軸座標）およびΔY軸座標
差平面表示メモリ６０１（DIF）のメモリアドレ
スに、対候補リストメモリ２１５の重み格納フイ
ールドWijに登録されている重みを加算する。こ
れを該メモリ２１５中のすべてのの有効なｉ，ｊ
について積算したものが差平面重みマツプであ
る。

こうして生成された差平面重みマツプは、量子
化された任意のΔXおよびΔYで指定される、差
平面上の位置に相当するメモリ６０１（DIF）の
メモリアドレスに、その位置によつて定める上述
のようにして積算された重みが格納された形で重
みパタンを形成している。なお、このマツプの重
みパタンは、上述の、探索指紋座標系の回転角
γΔθによつて異なることになる。

さて、次に、こうして生成された重みマツプ上
で、積算された重みが最大になつているΔX座標
値X_MおよびΔY座標の値Y_Mを、このマツプの全
面をサーチすることによつて見出す。但しこのサ
ーチを行なうに当つて後に詳述するように、サー
チすべきX_MおよびY_Mの位置にある重み、および
その前後の隣接する位置にある重みにそれぞれ特
定の荷重係数を掛け、それらを合計してできる荷
重重みが最大になるような形の荷重サーチを行な
う。こうして荷重重みが最大になるΔX座標およ
びΔY座標の値X_MおよびY_Mが見出されると、そ
のX_MおよびY_Mの値と、そのとき求められた最大
荷重重みMDIFの値とをそれぞれ記録しておく。

つぎに、探索指紋座標系の回転角γΔθのγの値
を前よりも少し変化してから、前と同様にして、
差平面重みマツプを生成し、この差平面重みマツ
プから上述のようにして荷重重みが最大になる
ΔX，ΔY座標の値X_MおよびY_Mとそのときの最大
荷重重みMDIFとを求め、今回求めたこの最大荷
重重みMDIFと、前回から残されている最大荷重
重みMDIFとを比較し前よりも大きいか否かを判
定する。もし前よりも大きい場合には、X_M，Y_M
およびMDIFの値を今回求めたそれぞれの値で更
新する。

このような操作を繰り返すことで、探索指紋の
座標系を、予めきめた細かさΔθを単位として、
予め定めた角度範囲内で振り廻すことにより、上
述の最大荷重重みMDIFが最大になる角度γΔθの
値とそのときのX_MおよびY_Mを求めるとこれが前
述の求めるべき座標整合量γΔθ，ΔX_TおよびΔY_T
になるのである。

さてつぎに、これを各回路の動作と関連づけて
詳述する。

最初に上述の差平面重みマツプを生成するため
の重みマツプ生成処理について述べる。

第４図の制御記憶２１８の制御部は、メモリに
格納されたマイクロプログラムの制御により特徴
点リストメモリ２１１の特定のｉ番目の探索指紋
特徴点のＸ，ＹおよびＤのデータを座標変換回路
２１２を介して読み出し、これを制御記憶２１８
の制御の中に含まれるレジスタ（図示せず）にそ
れぞれX_si，Y_siおよびD_siとして格納する。

この座標変換回路２１２は第１１図に示すよう
に変換パラメータΔX_A，ΔY_AおよびΔθ_Aを格納す
るためのそれぞれのパラメータレジスタ１１１０
（ΔX_A），１１１１（ΔY_A）および１１１２
（Δθ_A）をもち、これらのレジスタには、この重
みマツプ生成処理が開始される前に制御記憶２１
８の制御部によりそれぞれ、 ΔX_A＝０，ΔY_A＝０およびΔθ_A＝γΔθの値がすで
に格納されている。

この座標変換回路２１２の機能は、メモリ２１
１から読み出したＸ，ＹおよびＤの値を、座標原
点をΔX_A′，ΔY_Aの位置にうつし、かつ各座標軸
をΔθ_Aだけ反時計方向に回転したときに生ずる新
らしい座標系で表示した値X′，Y′およびD′に変
換する回路である。すなわちＸ，Ｙ，Ｄより、 X′＝（Ｘ−ΔX_A）cosΔθ_A ＋（Ｙ−ΔY_A）sinΔθ_A Y′＝（Ｙ−ΔY_A）cosΔθ_A −（Ｘ−ΔX_A）sinΔθ_A …(2) D′＝Ｄ−Δθ_A で表わされる。現在の例ではこの回路２１２は座
標系を単にΔθ_A＝γΔθ回転させるだけの作用をす
る。

さて、つぎに制御記憶２１８の制御部は、対候
補リストメモリ２１５の特定のロウアドレスｉお
よび特定のコラムアドレスｊをもつ対候補指示フ
イールドMijからｊ番目の対候補の番号を求め、
この番号をもつフアイル指紋の特徴点のＸ，Ｙお
よびＤの値を、特徴点リストメモ暦２１１から今
度は座標変換回路２１２を通さずに直接読み出
す。この値をそれぞれXmij，YmijおよびDmijで
表わすことにする。

次に制御記憶２１８の制御部はシーケンス制御
回路２１０の演算回路を用いて、前述のX_si，Y_si
およびD_siと今回読み出したXmij，Ymijおよび
Dmijとから、 ΔX＝Xmij−X_si ΔY＝Ymij−X_si ΔD＝Dmij−D_si なるΔX，ΔYおよびΔDを算出する。次にこうし
て求められたΔX，ΔYおよびΔDのそれぞれの絶
対値を、予め定められている特定のスレシユホー
ルド値Tx，TyおよびTd（比較的大きな値、例え
ばTd＝45゜）と比較し、これらのすべてが、それ
ぞれのスレシユホールド値よりも小さいときにか
ぎり、対候補リストメモリ２１５のロウアドレス
ｉおよびコラムアドレスｊの重み格納フイールド
Wijを読み出し、これを回路２１７の差平面表示
メモリ６０１（DIF）の、前記ΔXおよび、ΔYで
指定されるメモリアドレスの現在の内容に加算す
る。

これを行なうためには、制御記憶２１８の制御
部は、第２５図に示す座標整合回路２１７のライ
ン６１７０（ΔX）にΔXの値を、またライン６
１８０（ΔY）にΔYの値を供給し、かつライン
６１８１（CT）を“１”にすることにより、入
力選択器６１７、および６１８がそれぞれライン
６１７０および６１８０を介して供給されたΔX
およびΔYの値を選択するようにし、これを差平
面表示メモリ６０１（DIF）のそれぞれロウアド
レスおよびコラムアドレスとして供給する。この
結果、メモリ６０１（DIF）の差平面座標位置
ΔXおよびΔYに相当するメモリアドレスの現在
の内容がライン６０１０を介して読み出される。
これを加算器６０４の一方の入力として供給し、
もう一方の入力として、ライン６０４０を介して
前記重み格納フイールドWijから読み出された値
を供給することにより両者の和を作り、この和を
再びΔXおよびΔYで指定されるもとのメモリア
ドレスに格納する。これにより、メモリ６０１
（DIF）が表示する差平面にWijの内容を積算する
重み積算処理を容易に行なうことができる。

さて、これを用いて前述の差平面重みマツプを
生成するには、まず最初に差平面表示メモリ６０
１（DIF）の内容をすべて０に初期値化し、ま
た、前記ｉおよびｊの値をそれぞれ最初に０に初
期値化する。但しこのｉおよびｊの値は制御記憶
内の制御部内に設けられたパラメータレジスタ
（図示せず）に格納されている。こうして該制御
部は、ｉ＝ｊ＝０から上述の重み積算処理を開始
し、ｊの値をつぎつぎに１ずつ増し、重み格納フ
イールドに前述の終了マークが現われるまで続
け、終了マークが現われたらｉの値を１だけ増
し、ｊの値を再び０に戻してそこから処理を続行
し、最後に、探索指紋特徴点のＱフイールドに終
了マークが現われたらそこでこの処理を終了す
る。

以上の述べた重みマツプ生成処理をフローチヤ
ートとして第２６図に示す。

また第２７図に生成された差平面重みマツプの
一例を示す。

なお、第２７図に示すように、本実施例の差平
面重みマツプはΔXおよびΔYの値として−８か
ら７までの16レベルであり、比較的粗く量子化さ
れている。従つてΔXおよびΔYには前述の計算
によつて求められた値の上位４ビツト分を用い
る。

さて次に、こうして生成された差平面重みマツ
プ上で、重みの最大集中位置をサーチしその位置
の座標X_MおよびY_Mの値を見出す重み集中位置サ
ーチ処理について述べる。

この処理は、例えば第２７図に示すような差平
面重みマツプ上の重みの最大集中位置を見出すこ
とであるが、特定の点に確率的に不当に高い重み
が集中し判定に悪影響を与えるのを避けるため
に、本実施例においては、量子化された差平面の
個々の座標位置に格納されている重みを、そのま
ま比較してサーチするかわりに、下記のような荷
重サーチを行なう。すなわち、サーチ点を中心に
してそれに隣接する点を含む全部で９個の量子化
された差平面座標位置の重みに、それぞれ第２８
図に示すような特定の荷重係数を掛け、それらを
合計したものを比較しながらサーチする荷重サー
チを行なう。

このような荷重サーチを高速で行なうため、本
実施例においては専用の第２５図に示す座標整合
回路２１７を有している。

さて、メモリ６０１（DIF）に第２７図に示す
ような差平面重みマツプが完成し、サーチ動作が
開始されると、以下のように処理が進行する。

まず最初に、サーチ処理に対する座標整合回路
２１７の初期値化が行なわれ、回路２１７のメモ
リ６０１（DIF）を除くすべてのメモリおよびレ
ジスタに対し、それぞれの初期値が設定される。
すなわち、レジスタフアイル６０２（RF1）およ
び６０３（RF2）、レジスタ６１１（RK0），６
１２（RK1），６１３（RK2）および６１４
（MDIF）はすべて０にクリアされる。またレジ
スタ６０９（DX）および６１０（DY）にはサ
ーチ開始位置として、それぞれ−８がセツトされ
る。本実施例においては、差平面表示メモリ６０
１（DIF）は第２７図に示すように、量子化され
たΔXの値として−８から７までと、ΔYの値と
して−８から７までの値で指定できるが、サーチ
開始位置をこの差平面のΔX＝−８，ΔY＝−８
に選ぶ。なお、レジスタ６０９（DX）の内容は
差平面表示メモリ６０１（DIF）のΔXに対応す
るアドレスを指定し、レジスタ６１０（DY）の
内容はΔYに対応するアドレスを指定するのに用
いられる。またサーチ処理においてはライン６１
８１（CT）は“０”に設定され、このため選択
器６１７および６１８は、それぞれレジスタ６０
９（DX）および６１０（DY）側の入力を選択
してメモリ６０１（DIF）のアドレス指定を行な
うように制御される。また同様に、サーチ処理に
おいてはライン６１８１（CT）の制御によりメ
モリ６０１（DIF）は常に読出し状態にセツトさ
れる。

さて、座標整合回路２１７は、制御記憶２１８
の制御回路からライン６１１０（T0）を介して
供給される制御情報によつて制御される二つのタ
イミングT0およびT1を有している。

ライン６１１０（T0）が“１”の場合のタイ
ミングをT0とし、このタイミングにおいては下
記の動作を行なう。

まず、選択器６１９，６２０、および６２１は
左側の入力すなわち、それぞれ、メモリ６０１
（DIF）、フアイル６０２（RF1）およびフアイル
６０２（RF1）およびフアイル６０３（RF2）の
出力を選択するように制御され、それとともにレ
ジスタ６１１（RK0），６１２（RK1）および６
１３（RK2）の入力側がイネーブルされる。

この結果、第２５図から明らかなように、次の
動作が行なわれる。

RK0 DIF（DX，DY）＋2RF1（DY）＋RF2
（DY） RK1 RK0 RK2 RK1 RF1（DY） DIF（DX，DY） RF2（DY） RF1（DY） 但し、上のすべての動作表示において、矢印の
右側は更新前のそれぞれの内容を表わし、矢印の
左側側は更新後のそれぞれの内容を表わす。（つ
まり同じ記号であつても右側と左側とでその内容
が異なる）なお、これらの更新は一斉に行なわれ
るものとする。

例えば、，によると、レジスタ６１２
（RK1）の更新前の内容が更新によりレジスタ６
１３（RK2）に転送されレジスタ６１３（RK2）
の更新後の内容となり、また、レジスタ６１１
（RK0）の更新前の内容が更新によりレジスタ６
１２（RK1）に転送されレジスタ６１２（RK1）
の更新後の内容となることを示している。

また、DIF（DX，DY）は、レジスタ６０９
（DX）およびレジスタ６１０（DY）の内容で指
定されるメモリアドレスをもつ差平面表示メモリ
６０１（DIF）の内容を表わし、同様にRF1
（DY）およびRF2（DY）はレジスタ６１０
（DY）の内容で指定されるメモリアドレスをも
つそれぞれフアイル６０２（RF1）およびフアイ
ル６０３（RF2）の内容を表わす。例えばの動
作表示は、レジスタ６１０（DY）の内容で指定
されるアドレスをもつフアイル６０３（RF2）の
更新後の内容は、レジスタ６１０（DY）の内容
で指定されるアドレスをもつフアイル６０２
（RF1）の更新前の内容によつて書き替えられる
ことを表わす。

さらにまた、の動作表示で示されているよう
に、加算器６０５は選択器６２０側からの出力を
２倍して選択器６２１側からの出力に加算するよ
うな加算器である。

さて次に、タイミングＴ１においてはライン６
１１０（T0）が“０”になり、ライン6230（T1）
が“１”になる。この結果タイミングT1におい
ては下記の動作を行なう。

まず、レジスタ６１１（RK0），６１２
（RK1）および６１３（RK2）の入力側はデイセ
ーブルされる。この結果これらのレジスタの内容
はこのタイミングT1期間中そのままの値に保持
される。つぎに、選択器６１９，６２０および６
２１は右側の入力すなわち、それぞれ、レジスタ
６１１（RK0），６１２（RK1）および６１３
（RK2）からの出力を選択するように制御され
る。またライン６２３０（T1）に“１”が供給
され、アンドゲート６２３がイネーブルされる。

この結果、第２５図から明らかなように、次の
動作が行なわれる。すなわち、加算器６０６の出
力には、 RK0＋2RK1＋RK2 の値が現われるが、これとレジスタ６１２
（MDIF）の更新前の内容とが、比較器４２２で
比較され、もし、 MDIF≦RK0＋2RK1＋RK2 が成立すると、ライン６２３１が“１”となる結
果、レジスタ６１４（PDIF），６１５（XM）お
よび６１６（YM）の入力側がイネーブルされ、 MDIF RK0＋2RK1＋RK2 XM DX YM DY の処理が行なわれる。つまりの条件が満足した
ときに限りレジスタ６１４（MDIF），６１５
（XM）および６１６（YM）の内容は上の，
およびの動作表示で示されるように更新さ
れ、そうでない場合には影響を受けない。

さて、以上につづいて制御記憶２１８の制御部
はライン６０７０（T1′）にタイミング情報を送
りレジスタ６１０（DY）および６０９（DX）
を更新する。これらのレジスタの更新は次のよう
に行なわれる。

一般の場合には、ライン６０７０（T1′）のタ
イミング情報によりレジスタ６１０（DY）の更
新前の内容に１が加算されるように更新される。

但し、レジスタ６１０（DY）の更新前の内容
が上限の７である場合には、このタイミング情報
によりレジスタ６１０（DY）の内容は−８に更
新され、これとともに回路６０７からのキヤリイ
が回路６０８に加えられる。その結果、さらにレ
ジスタ６０９（DX）がその更新前の内容に１が
加算されるように更新される。但し、回路６０７
からのキヤリイが出ない一般の場合にはレジスタ
６０９（DX）の内容は更新によつて不変に保た
れる。

また、レジスタ６０９（DX）の更新前の内容
が上限の７であるときに、回路６０７からのキヤ
リイが回路６０８に加えられると、回路６０８が
キヤリイを発生し、これはライン６０８０を介し
て制御記憶２１８の制御部に供給され、サーチ処
理終了の情報として用いられる。

さて、上述のライン６０７０（T1′）のタイミ
ング情報によるレジスタ６１０（DY）および６
０９（DX）の更新がすむと、これでT1タイミン
グが終了し、制御記憶２１８の制御回路は再び前
述のT0タイミングの制御に戻り、更新された各
レジスタおよびメモリの内容を用いて前述の〜
の動作を行なう。

こうして、制御部は、座標整合回路２１７への
T0タイミングおよびT1タイミングの情報をつぎ
つぎに交替することによりサーチ処理をすすめ
る。そして、前述のライン６０８０からのサーチ
終了情報を受けると、そこで交替を停止し、その
ときのレジスタ６１５（XM），６１６（YM）
および６１４（MDIF）の内容を読み出す。これ
で荷重サーチによるサーチ処理が終了する。な
お、この重み集中位置サーチ処理をフローサヤー
トの形で示したのが第２９図である。

以上の動作により座標整合回路２１７は、第２
７図に示すような差平面重みマツプを、第２８図
に示す荷重係数を用いて荷重サーチし、荷重重み
MDIFが最大になる点の差平面座標の値XMおよ
びYMとこのMDIFの値とを求めたことになる
が、この理由は以下に示す通りである。

上述の説明から明らかなように、サーチ走査
は、第２７図に示す差平面の左下隅から開始し垂
直に上方に向つて（ΔYが増す方向に）走査し、
上限に達するとΔXが１だけ増して１列右側の縦
列に移り、これを同様に下から上方に向つて走査
する。これを繰り返すことにより全面をカバーす
る。

今、このような走査が、例えば、ΔX＝３、
ΔY＝５の点まで進んだ状態を考察する。このと
き、レジスタ６０８（DX）、および６１０
（DY）、フアイル６０２（RF1）および６０３
（RF2）の各内容は次に示すようになつている。

DX＝３，DY＝５，RF1(5)＝DIF（２，５），
RF2(5)＝DIF（１，５）。

つまり、フアイル６０２（RF1）の内容は、現
在走査中のΔX＝３の縦列よりも一つ手前のΔX
＝２の縦列に対応するメモリ６０１（DIF）の内
容を格納しており、またフアイル６０３（RF2）
の内容は、現在走査中の縦列よりも二つ手前の
ΔX＝１の縦列に対応するメモリ６０１（DIF）
の内容を格納している。以上により、このときの
タイミングT0における前述のの動作は、RK0
DIF（３，５）＋2DIF（２，５）＋DIF（１，５）と
なる。

一方、RK1には一つ前の走査時点（DY＝４の
とき）RK0の値が、またRK2には二つ前の走査
算点（DY＝３のとき）のRK0の値が更新によつ
て入つてくるので、上式から明らかなように更新
後のRK1およびRK2の値はそれぞれ、 RK1＝DIF（３，４）＋2DIF（２，４）＋DIF
（１，４） RK2＝DIF（３，３）＋2DIF（２，３）＋DIF
（１，３） となる。

従つてタイミングT1における加算器７０６の
出力の（RK0＋2RK1＋RK2）の内容は、 DIF（３，５）＋2DIF（２，５）＋DIF（１，５）＋
2DIF（３，４）4DIF（２，４）2DIF（１，４）＋
DIF（３，３）＋2DIF（２，３）＋DIF（１，３） となる。これより、上述の処理は、差平面重みマ
ツプに第２８図に示す荷重係数を掛けて積算した
ものをMDIFの候補とし、その最大なものを求め
るというサーチをしていることが明らかである。

但し、荷重の中心位置は、現在のDX，DYの
指定する位置ではなくて、それよりもそれぞれ１
だけ小さい所にある（上の例ではDIF（３，５）
ではなくてDIF（２，４）にある）ので最大重み
集中位置は上述の処理で得られたXMおよびYM
の値からそれぞれ１を引いた値となる。

さて、本実施例は、探索指紋特徴点の座標系
を、特定の微小角Δθを単位として振りまわし、
特定の角度範囲内の各γΔθごとに、上述の差平面
重みマツプ生成処理と、これに対する重み集中位
置サーチ処理とを実行し、前述の荷重重みMDIF
が最も大きくなるようなγΔθの値と、そのときの
XM−１およびYM−１の値を求めることによつ
て最適の座標整合量を決定する。

このための総合の処理は以下のように進行す
る。制御記憶２１８の制御部には作業記憶エリア
２１６が含まれているが、この領域の中に次の各
パラメータを格納するレジスタが設けられている
（図示せず）。

すなわち、振り廻しの単位となるΔθ、振り廻
し角度を指定するための倍数γ，γの最大値
γmax、回転角θ_M、回路２１７から読み出した
MDIF（このレジスタに格納された値をMDIF′と
する）、XM−１（このレジスタに格納された値を
X_Mとする）、YM−１（このレジスタに格納され
た値をY_Mとする）。

さて、座標整合量決定の処理が開始されると制
御記憶２１８の制御部は、上述の対応する各レジ
スタに予め定められているΔθおよびγmaxを設定
し、MDIF′およびγを０に初期値化する。

次に、シーケンス制御回路２１０の演算回路を
用いて積γΔθを作りこれを座標変換回路２１２の
パラメータレジスタ１１１２（γθ_A）に格納する。

以上がすむと制御記憶２１８の制御部は前述の
差平面重みマツプ生成処理と、重み集中位置サー
チ処理を実行し、読み出したMDIFと上述の
MDIF′とを比較する。もしMDIFがMDIF′より
も大きい場合にはMDIF′をこの読み出したMDIF
で置き替え、かつX_MをXM−１およびY_MをYM
−１で、また、θ_MをγΔθで置き替える。

次にγを変化して上述の処理を繰り返し、｜γ
｜≦γmaxのすべてγの値について以上を実行し
て処理を終了する。

この処理をフローチヤートとして第３０図に示
す。

以上に述べた処理が終了したときのθ_M，X_Mお
よびY_Mの値が所望の座標整合量γΔθ，ΔX_Tおよ
びΔY_Tとなつている。

最終結果のMDIFの値があるスレツシヨルドレ
ベル以下の時は、座標整合がうまくいかないと判
断する。すなわち、対象の２つの指紋の類似性が
ないものとして処理が中断される。座標整合量が
あるスレツシヨルドレベル以下の時には、さらに
精密な照合を行なうため、処理が２次照合プロセ
ツサに引継がれる。

第２次照合プロセツサには、第１次照合プロセ
ツサから特徴点リスト、領域パターンリスト、識
別情報及び対候補リストの各情報が共通バスを介
して送られてくる。この場合、第２次特徴点メモ
リ５１１には座標整合量により座標変換された特
徴点リストが格納される。また領域パターンリス
トは領域パターンリストメモリ５１６に対候補リ
ストは対候補リストメモリにそれぞれ格納され
る。

以上に述べたように、本実施例を用いると、照
合すべき二つの紋様パタンの各特徴点の座標と、
各特徴点の局所的近似度にもとずく対候補の重み
を含む対候補リストとが与えられ、しかも、両者
の座標系が必らずしも整合していない場合に、特
別な差平面重みマツプを作りこのマツプ上で重み
の集中位置を荷重サーチするという独特の手段を
用いることにより、座標系の回転に対する試行を
行なうだけで、平行移動に対する試行を行なうこ
となく、両座標系を整合させるために必要な座標
整合量を高速且つ高信頼性をもつて決定すること
ができる。

なお、本実施例においては指紋照合の場合につ
いて詳述したが、本発明は何も指紋に限ることな
く、特定の複数の特徴点を有する紋様パターン照
合に適用することができる。

また、本実施例においては、特徴点メモリ、ペ
アリストメモリおよび差平面表示メモリに対して
それぞれ特定の構成および容量を用いたがこれは
一例を示したもので何もこれに限定されるもので
はない。

また、重みの集中位置を荷重サーチするため荷
重係数についても特定の構成を用いたが、これも
一例を示したものでこれに限るものではない。こ
の荷重係数の構成が変わるとそれに応じて座標整
合回路の構成も変わるが、本実施例を応用するこ
とにより容易に実現可能である。

(7) ２次照合プロセツサによる精密照合動作 次に、第５図を参照すると、制御回路５１０
は、座標変換回路５１２を無変換状態にセツトし
直した後、対候補リストメモリ５１３の全ての
N_s：M_siを再度読出し、その特徴点データＸ，
Ｙ，Ｄを対候補リスト生成時より厳しい閾値T_x，
T_y，Tdで検査する。なぜなら、探索指紋とフア
イル指紋とは座標整合を完了しているため、本来
すでに特徴点は指紋押捺の歪みを除いてその配位
は一致しているはずだからである。この対検査で
否定された候補対N_s，M_siはその候補対値W_siと
ともに対候補リストから削除される。これが候補
対の精選過程である。

さらに精選された対候補リストについてその全
ての候補対N_s：M_fに対して、次のような候補対
値の修飾を行う。即ち、第３１図を参照して２つ
の候補対N_s：M_fに対して、各々N_s，M_fをアドレ
ス線５１１０に供給し、第２次特徴点メモリ５１
１から各々の最近傍特徴点（Nsr，Mfr：ｒ＝０
〜３）を読出し、対候補リストメモリ５１３の
N_s行にMfrが登録されているか否かを検査する。
もしM_f′＝M_frとして登録されていればその候補
対値W_bを、基になつたN_s，M_fの候補対値W_aに
加える。候補対値の修飾が完了すると、新しい候
補対値の大きさに従つて対候補リストメモリ５１
３の内容はN_s行毎にソートされる。以上で最終
的な対候補リストが完成する。この対候補リスト
を元にして対リスト５１５ａ，５１５ｂが対リス
トメモリ５１５に生成される。

対リストメモリ５１５内にある２つの対リスト
５１５ａ，５１５ｂは相似の構造であつて、第３
２図に示されるようにN_s（ｓ＝１〜Ｓ）及びM_f
（ｆ＝１〜Ｆ）でアドレス線５１５０を介してア
ドレスが指定され、特徴点番号と対値M_f，V_s及
びN_s，V_fを保持できる２組のメモリである。

対リスト５１５ａ，５１５ｂの生成は、当初対
値として負の定数で初期化された後、対候補リス
トのN_s（ｓ＝１〜Ｓ）の順に複数回走査しなが
ら、その最圧端ｉ＝１即ち最大の候補対値を有す
る候補対N_s：M_s1をその候補対値W_s1自身及び第
２の候補対値W_s2との差によつて信頼性の高いも
のから対リスト５１５ａ，５１５ｂにその候補対
値を対値として移す。対リストに登録した候補対
は全対候補リスト中から抹消される。全ての対候
補リストメモリ５１３の内容が対リストメモリ５
１５に移された時点での対N_s：M_fの対値はυ_s＝
υ_f＝N_s：M_f）の候補対値となつている。又、候
補対値によつて移されなかつた対リスト中の特徴
点の対値は負の初期値がそのまゝ残る。

次に対値の決定は、対値の修飾と、非対値の緩
和の２つの処理によつて成される。

対リスト５１５ａ，５１５ｂを順次調べその対
値υが正であるときは対値の修飾を行う。即ち第
３３図に示すように、例えば対リスト５１５ａ中
のN_sの対値υ_sが正であるときは、その対特徴点
M_fを基にして候補対値の修飾と同様に第２次特
徴点リストメモリ５１１をアクセスしてその最近
傍特徴点（N_sr，M_sr：ｒ＝０〜３）を読出し、
対リスト５１５ａのN_srの対がM_srでかつ対値υ_sr
が正であるか否かを検査する。もし正なら対値
υ_srが対値υ_sに加えられる。相似な処理が対リス
ト５１５ｂ側でも対リスト５１５ａ側と独立に行
われる。一方第３４図の如く対リストに正の対値
が格納されていないとき、例えば対リスト５１５
ｂに於けるあるM_f′が負の対値υ_f′をもつている
ときは、このM_fをアドレス線５１１０に供給し、
M_f′の特徴点データを線５１２０を介して読出
し、その（X_f′，Y_f′）を領域パターンリスト５
１６ａの２次元アドレスとして線５１６０に供給
する。その結果出力5161から読出された領域値が
“０”であれば、上記特徴点M_f′は探索指紋側の
不明領域内であつたこととなり対値υ_f′はdon′t
careを意味する値“０”に書換えられる。一方領
域値が“１”なら対値υ_f′はそのまゝとなる。逆
に対リスト５１５ａで上記の処理を行うときは座
標変換回路５１２に逆変換量（ε＝△X^*，η＝
−△Y^*，θ＝−△D^*）をセツトし、領域パター
ンリストメモリ５１６の内容を調べる。

対値υ_f′又はυ_s′が負値のまゝ保存された特徴点
M_f′又はN_s′については、次のような検査を行う。
例えばM_f′については、最近傍特徴点（M_fr′；ｒ
＝０〜３）の内隆線数R_f′₁＝０となるものでその
配置が近く、方向が正反対を向いているものがな
いかを演算回線５１９での対向検査処理により探
す。もしあればその特徴点M_f′_rを対リスト５１５
ｂで検査しその対値υ_f′_rが負の値であれば、この
対値υ_f′_rと上記M_f′をともにdont careとし対値
“０”に変更する。これは、第３５図に示す如く、
対向する近接特徴点を検査するもので、このよう
な２組の特徴点は指紋押捺の具合いや機械的な自
動特徴点描出時に描出されたりされなかつたりす
る不安定な特徴点である。

第３６図は対向検査回路の一実施例を示すブロ
ツク図である。即ち、差絶対値器１６３ｘ，ｙ，
ｄ、補数値１６３ｃ比較器１６４ｘ，ｙ，ｄ、方
向ROM１６５、差絶対値器１６６ａ，ｂ、比較
器１６７ａ，ｂ、ANDゲート１６８及び閾値
ROM１６９から構成される。

「対向」検査されるべき２組の特徴点データ
（Ｘ，Ｙ，Ｄ）と（X′，Y′，D′）がそれぞれ入力
信号１６１ｘ，ｙ，ｄ及び１６１x′，y′，ｄに供
給されると、補数値１６３ｃで方向D′ののみが
方向補数即ち、πラジアンだけ反転された後差絶
対値器１６３ｘ，ｙ，ｄで差の絶対値が演算さ
れ、閾値ROM１６９の出力である閾値と比較器
１６４ｘ，ｙ，ｄで比較される。即ち ｜Ｘ−X′｜≦T_x，｜Ｙ−Y′｜≦T_y，｜Ｄ−D′＋
π｜≦Td が検査され、その出力がANDゲート１６８に入
力される。ここで方向成分ではπラジアンが差絶
対値器１６３ｄの最上位ビツト（MSB）に相対
する様に接続され、方向演算に於ける周期性に対
する正しい演算が保証される。一方、差絶対値器
１６３ｘ，ｙの差絶対値出力と差符号（減算時の
符号）は方向ROM１６５にアドレスとして入力
され、その指定する方向△Ｄを出力し差絶対値器
１６６ａ，ｂに供給する。即ち △Ｄ＝T^-1 _ar（Ｙ−Y′）／（Ｘ−X′） なる△Ｄが近接しているという条件から比較的小
さいＸ−X′及びＹ−Y′の全ての組合せを入力と
して、ROM化されている。一方方向Ｄ−D′と上
記△Ｄは差絶対値器１６６ａ，ｂでその差の絶対
値が演算され比較器１６７ａ，ｂで閾値ROM１
６９からの別の予じめ定められた値と比較され、
その結果がANDゲート１６８に供給される。
ANDゲート１６８は全ての入力が肯定されたと
き「対向」検査肯定信号を出力信号１６２を介し
てシーケンス制御回路５１０に戻す。

上記の差絶対値器１６６ａ，ｂに於いては方向
Ｄと△Ｄ及びD′と△Ｄとはπラジアンの差異は
０ラジアンに相当するので減算の最上位ビツト
（MSB）はπ／２となるよう配線されている。

上記の差絶対値器１６６ａ，ｂに於いては方向
Ｄと△Ｄ及びD′と△Ｄとはπラジアンの差異は
０ラジアンに相当するので減算の最上位ビツト
（MSB）はπ／２となるよう配線されている。

以上で、対向検査回路の一例を説明した。なお
この対向検査回路は汎用プロセツサで代替でき
る。負の対値を有する対リスト中の検査に於い
て、上述の「対向」特徴点でないときは、最終的
にその特徴点の集密量Ｃを検査し、値比較でそれ
が非常に大きいときはやはり対値“０”又は負の
“０”に近い値にセツトし直す。以上をまとめて、
第３７図に模式的に示したように非対値の緩和
は、探索指紋とフアイル指紋との座標整合後の領
域パターン５１６ａ，５１６ｂの非共通領域に存
在する非対特徴点及び共通領域内で点線で示した
「対向」特徴点及び集密量の大きい特徴点につい
てその非対値をdon′t care又はそれに近い負の対
値に緩和しようとするものである。

以上で対リストの対値が完成すると、制御部回
路５１０は対リスト５１５を順次読出しながら照
合値ｑとして を演算回路５１９および作業エリア５１４から算
出する。ここにＳ及びＦは探索指紋及びフアイル
指紋の領域パターン５１６の共通領域内の特徴点
数を示す。これらの演算については、一般的な四
則演算回路で実施できるので詳細は省略する。

説明を簡明にするため、対候補リストの候補対
値修飾及び対リストの対値の修飾に於いて最近傍
特徴点で対応する（N_sr，M_fr；ｒ＝０〜３）の
対応検査についてのみ説明したが、一般的には指
紋の特徴点の配位の歪みから必ずしも同じｒで
N_srとM_frの対応を期待できるものではなく、N_sr
に対し異なるr′であるM_fr′が対応する場合もある
ので、（N_sr，M_fr；ｒ＝０〜３）は象限ｒ単位で
比較するのではなく（N_sr；ｒ＝０〜３）と
（M_fr′；ｒ＝０〜３）の16回総当り的に対応を検
査するのが精密である。この場合の対応検査は
各々N_s，M_fを基準とした局所座標系による。

により行われる。これらは座標変換回路５１２及
び対検査処理により対候補リスト生成時の処理と
同様に可能である。

２次照合プロセツサにより最終的に算出された
照合値８があるスレツシヨルドレベル以上の時に
は、フアイル指紋識別番号及び照合値があるスレ
ツシヨルドレベル未満の時は類似性がないものと
判断され、候補リストへは登録される照合が終了
される。

(8) 転送先プロセツサ決定動作 本発明の一実施例では、第２Ｂ図に示す構成を
基にしているが、第２Ｃ図に示す装置構成を採る
ことによりさらに照合性能（１対１の照合時間）
を向上させる効果がある。

第２Ｃ図に示す指没照合装置は、制御ユニツト
１０、同一構成の１次照合プロセツサｍ台（ｍ
１）、２次照合プロセツサｎ台（ｎ１）および
制御ユニツト１０、１次照合プロセツサおよび２
次照合プロセツサ間でデータを伝送する共通バス
７０から構成されている。実施例ではｍ＝３、す
なわち１次照合プロセツサ２０，３０，４０、お
よびｎ＝２、すなわち２次照合フアイル５０，６
０の場合を示している。この様な装置では各プロ
セツサは共通の探索指紋と各々異なるフアイル指
紋との１対１の照合を行なつているため、プロセ
ツサ間並列処理となり高速照合が可能となる。

第３Ｂ図は第２Ｃ図の照合装置における制御ユ
ニツト１０内の転送先決定回路３０４の詳細な構
成を示す図である。

照合装置５が照合制御装置４から照合の指示を
受けると、制御ユニツト１０は、第３Ｂ図に示す
ようにデータ転送要求１１を内部の第１決定回路
１００に出力する。第１決定回路１００は１次照
合プロセツサ２０，３０および４０が指紋照合中
であることを示す各ビジー信号２１，３１および
４１を入力とし次式により、表わされる論理動作
を行ない、信号２２，３２および４２を出力し
て、フアイル指紋データの転送先１次照合プロセ
ツサの第１次決定を行なう。

信号22＝（データ転送要求11）AND（ビジー信
号21） 信号32＝（データ転送要求11）AND（ビジー信
号21）AND（ビジー信号31） 信号42＝（データ転送要求11）AND（ビジー信
号21）AND（ビジー信号31）AND
（ビジー信号41） 第２決定回路２００は、１次照合プロセツサ２
０，３０および４０からの２次照合プロセツサへ
の各データ転送要求２５，３５および４５と、２
次照合プロセツサ５０および６０が処理中である
ことを示す各ビジー信号５１および６１とを入力
とし次式により表わされる論理動作を行ない、信
号２６，３６，４６，５２および62と抑止信号７
１とを出力して、１次照合終了のフアイル指紋デ
ータの転送先２次照合プロセツサの第１次決定
と、２次照合プロセツサへのデータ転送があると
きの１次照合プロセツサへのデータ転送抑止信号
発生とを行なう。

信号26＝（データ転送要求25） 信号36＝（データ転送要求25）AND（データ転
送要求35） 信号46＝（データ転送要求25（AND（データ転
送要求35）AND（データ転送要求
45） 信号52＝〔（データ転送要求25）OR（データ転
送要求35）OR（データ転送要求
45）〕AND（ビジー信号51） 信号62＝〔（データ転送要求25）OR（データ転
送要求35）OR（データ転送要求
45）〕AND（ビジー信号61） 抑止信号71＝〔（データ転送要求25）OR（デー
タ転送要求35）OR（データ転送要
求45）〕AND（ビジー信号51）AND
（ビジー信号61）OR〔（データ転送
要求25）AND（データ転送要求35）
AND（データ転送要求45）〕 第３決定回路３００は、信号２２，３２および
４２と抑止信号７１との各論理積である信号２
３，３３および４３と、上述のようにして求まる
信号２６，３６，４６，５２および６２と、ビジ
ー信号５１および６１とを入力とし次式により表
わされる論理動作を行ない、フアイル指紋データ
の転送のために共通バス７０の使用を許可する１
次照合プロセツサあるいは２次照合プロセツサの
１台を決定する。

１次照合プロセツサ２０へのバス使用決定信号
２４（信号２３）OR（信号２６） １次照合プロセツサ３０へのバス使用決定信号
３４＝（信号３３）OR（信号３６） １次照合プロセツサ４０へのバス使用決定信号
４４＝（信号４３）OR（信号４６） ２次照合プロセツサ５０へのバス使用決定信号
５３，２１，３１，４１，５１および６１が変数
になつており、各プロセツサは相異なるフアイル
指紋データに対して並列した指紋照合ができるこ
とを示唆している。

本発明の実施例については、その動作説明から
明らかなように製品化されているマイクロコンピ
ユータを用いて、処理装置で対検査回路、対向検
査回路及び制御部を、又メモリによつて領域パタ
ーン、特徴点リスト、差平面、対候補リスト及び
対リストを割当ることによつて等価な出力を得る
ことが可能である。

【図面の簡単な説明】

第１図は、指紋パターン上の特徴点を説明した
図、第２Ａ図は指紋照合システムの一例を示す
図、第２Ｂ図は第２Ａ図に示される本発明の一実
施例である指紋照合装置の構成を示す図、第２Ｃ
図はさらに拡張させた指紋照合装置の構成を示す
図、第３図は第２Ｂ図および２Ｃ図で示した装置
内の制御ユニツトの構成を示す図、第４図は本発
明の装置における第１次照合プロセツサの一実施
例を示す図、第５図は本発明の装置における第２
次照合プロセツサの一実施例を示す図、第６図は
本発明の指紋照合方法を示すフローチヤート、第
７図は指紋照合において使用される一指分の特徴
点データを示す図、第８Ａ図は指紋照合において
使用される特徴点リストの一例を示す図、第８Ｂ
図は最近特徴点を説明するための図、第９図は一
般的な座標変換動作を説明するための座標系を示
す図、第１０図は一般的な座標変換動作を説明す
るフローチヤート、第１１図は第１次照合プロセ
ツサ及び第２次照合プロセツサで使用する本発明
の一実施例を示す座標変換回路の構成を示す図、
第１２図は本発明の一実施例を示す最近傍特徴点
復元回路の構成を示す図、第１３図は最近傍特徴
点復元後の特徴点リストを示す図、第１４図は最
近傍特徴点を示す図、第１５図は最近傍特徴点復
元動作を示すフローチヤート、第１６図は本発明
の一実施例である対検査回路を示す図、第１７図
は対検査回路で使用する特徴点リストの一実施例
を示す図、第１８図は対検査回路内の特徴点メモ
リ部を示す図、第１９図は対検査回路内のリレー
シヨン連結部を示す図、第２０図は対検査回路内
の対検査部を示す図、第２１Ａ図は本発明に用い
る２次リレーシヨンデータを説明するための指紋
パターンの簡易化した詳細拡大図、第２１Ｂ図は
本発明の一実施例である２次リレーシヨンデータ
を用いた対検査回路を示す図、第２２図は第２１
Ｂ図で示す対検査回路で使用する特徴点リストの
一実施例を示す図、第２３図は第２１図で示す対
検査回路内の複合リレーシヨン連結部を示す図、
第２４図は対候補リストメモリの一実施例を示す
図、第２５図は本発明の座標整合量決定回路の一
実施例を示す図、第２６図第２９図および第３０
図は座標整合量決定動作を説明したフローチヤー
ト、第２７図は座標整合量決定回路で生成する重
みマツプの一例を示す図、第２８図は座標整合量
決定動作で使用する荷重係数を示す図、第３１図
は対候補の強調処理を説明するための図、第３２
図は本発明に用いる対リストメモリの一実施例を
示す図、第３３図は対リストと対特徴点の関係を
示す図、第３４図は、対リストの内容の一例を示
す図、第３５図は２つの特徴点が対向特徴点とな
る例を示した図、第３６図は対向検査回路の一実
施を示す図、第３７図は探索及びフアイル指紋と
領域パターンとの関係を示す図、および第３８図
は制御ユニツト内の転送先決定回路の一実施例を
示すブロツク図である。

Claims (1)

1. 【特許請求の範囲】 １ 探索指紋とフアイル指紋の同一性を判別する
   指紋照合装置において、 適宜に定めた点を原点とする直交座標系に基づ
   く前記探索及びフアイル指紋の特徴点の位置、角
   度、およびリレーシヨンデータを保持する特徴点
   リスト記憶手段と、 前記各特徴点を原点とする局所座標系に座標変
   換を行ない、前記２つの指紋の各特徴点間の位
   置、角度、およびリレーシヨンデータの一致性を
   検査することにより対候補リストを保持する対候
   補リスト記憶手段と、 前記特徴点リスト記憶手段および対候補リスト
   記憶手段により前記２つの指紋に対する最適座標
   整合量を生成する最適座標整合量生成手段と、 前記最適座標整合量により整合された座標系下
   で前記２つの指紋の各特徴点間に対し、整合され
   た位置、角度およびリレーシヨンデータの一致性
   を検査することにより前記対候補リストから真の
   対特徴点および対値を決定して保持する対リスト
   記憶手段と、 前記対特徴点と対値から前記２つの指紋の照合
   値を決定し、保持する候補指紋記憶手段とを含む
   ことを特徴とする指紋照合装置。 ２ 探索指紋とフアイル指紋の同一性を判別する
   指紋照合装置において、 指紋の特徴点を原点とした局所座標系におい
   て、該原点に最も近い第１次近傍特徴点の位置、
   角度、およびリレーシヨンデータを含む第１次リ
   レーシヨンデータを記憶する第１の記憶手段と、 前記第１次最近傍特徴点を原点とした局所座標
   系において該原点に最も近い第２次最近傍特徴点
   の位置、角度、およびリレーシヨンデータを含む
   第２次リレーシヨンデータを記憶する第２の記憶
   手段とを含むことを特徴とする特許請求範囲第１
   項記載の指紋照合装置。 ３ 探索指紋とフアイル指紋を照合する指紋照合
   装置において、 基準座標系における各特徴点の位置、角度、お
   よびリレーシヨンデータを格納する第１の特徴点
   リスト記憶手段と、 前記対候補リスト記憶手段および前記座標変換
   手段により対候補特徴点を別の座標系で座標変換
   して求まる特徴点の位置、角度、およびリレーシ
   ヨンデータを格納する第２の特徴点リスト記憶手
   段とを有する特徴点リスト記憶手段と、 前記第１の特徴点リスト記憶手段と対候補リス
   ト記憶手段から最適座標整合量を生成する最適座
   標整合量生成手段と、 前記第１の特徴点リスト記憶手段、対候補リス
   ト記憶手段、および最適座標整合量生成手段に連
   結した座標変換手段と、 前記第２の特徴点リスト記憶手段、対候補リス
   ト記憶手段、および指紋領域記憶手段に連結され
   前記２つの指紋の第２の特徴点リスト上の座標整
   合された各等徴点の位置、角度、およびリレーシ
   ヨンデータの一致性を検査することにより生成さ
   れる対リストを生成する前記対リスト記憶手段と
   を含むことを特徴とする前記特許請求範囲第１項
   記載の指紋照合装置。