JPS60134385A - 指紋照合装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

発明の属する技術分野 不発明は指紋の照合方法に関する。本発明に２ける“指
紋”とは指紋、定紋、七の他しま状パターン等のいわゆ
る紋様パターンの代表として冗戎する。また“照合″と
は探索すべき１つの指紋と。 予め登録されている指紋との同一性を判別することを意
味する。 従来技術 通常照合する指紋を探索指紋と称し照合対象となる予め
登録された指紋を７アイル指紋と称する。 各々の指紋は、隆線紋様の特殊な点、すなわち。 第１図において隆線にのとぎれる点Ｍ（端点）および分
岐または合流する点ｍ（分岐点）を待って２シ一般にこ
れらの点は特徴点と呼ばれる。 従来、指紋照合は、上記探索２よびファイル指紋のそれ
ぞれに対し特徴点の種別、ある基準座標系に対するその
特徴点の位置Ｘ、Ｙおよびその方間りの情報をコード化
して記憶し、このコード化されｆｃ指紋特徴を用いて行
なわれている。 例えば、事件現場等に残された探索指紋特徴点の位置２
よび方向を記述する座標系の選び方には任意性がめシ照
せされるべきファイル指紋の特徴点を表わす座標系とは
一般に一致しない。従って。 照せに際しては探索指紋の座標系を照合する相手ファイ
ル指紋ごとに最も確からしい瀘だけ回転及び平行移動の
座標変換を行なってから比較検足する必要がある。 一般に照付する場合、照会すべき相手ファイル指紋は菓
太な数によるので照合の高速性および確実性（信頼性）
がｌ要視される。 以下に従来の指紋照合方法を述べる。 一般に探索指紋の特徴点と照合すべきファイル指紋の特
徴点とでほその数も異なＶま１ｃその対応も不明である
。これらを対応づける７こめに各％微意に対し、座標変
換により左右されない局ル［的籍徴を表わす量を導入し
ている。 例えば、各特徴点の種別（端点２よび分岐点）もその一
つで必シ、’ｉ：ｆｃらる特徴点η１ら特定の半径以Ｐ
コに存在ある他の特徴点の数も局所的特徴を表わす量と
なる。さらに、これらの量をもとの特徴点を原点とし方
向りを、例えば、Ｙ軸とする局所座標系全作シ、この座
標系の各象限に分布する他の特徴点の数という形に分割
すれば一層清報被の多い局所的特徴を表わす量となる。 これらの周所的＝ｗ徴ｍτ導入すると、探索指紋の各特
徴点に対し各ファイル指紋の特徴点をこの局所的特徴量
を用いて比較することに↓り座標系の選び万とは魚関係
にそれぞれの近似度の頒さを決定することができる。そ
こで上述の局所的に近似度の強さの順に各特徴点間の対
候補を決定し、これらの対候補となる特徴点の待つ局所
的近似度を紋もよく整＠させる座標量＠−童をめ最終的
な照せ１直を決定させることができる。 しかしながら従来の照会方法及び照合装置では上述の照
合に２ける高速性２工び信頼性という点で必ずしも元弁
でないという欠点ヲ令している。 発明の目的 本発明の目的は、探索掲載とフッ・イル指紋の照会ＶＣ
ｓｐいて、＾細粗性を持ちかつ重連な照合τ可能とする
指紋照合方式を提供することにるる。 発明の構成 従来の指紋照せ装置は、照＠対象となる採索指紋とファ
イル指紋に対し各々予め足りた示準座悔系に２ける各特
徴点の位置、角度及び座標系とは独立なりレーションデ
ータを示す特徴点リストをｔ記憶する指紋饋域記憶手段
、２よひＡｉｌ記２つの指紋の各特徴点に対し前記特倣
点の位置、角度、ｈ−よびリレーションデータの一致性
を検査することにより、前記２つの掲載の特徴点から対
となる特徴点を選択する手段から構成されている。 本発明の指紋照合装置は、対候補として上述の対特徴点
を示す対朕袖すストｔ−記憶する対候補リスト記憶手段
、前記２つの指紋の基準座標系を合わせるために、前記
対候補特徴点の位置づ“れおよび角度のずれから最適腸
標整＠量を生成する最適座標整合量生成手段、前記２つ
の指紋の基準座標系のどちらかを前記板：ｌａ座標螢曾
量によジ整合された座標系に変換する座標変換手段、前
記座標歴合された各特徴点の位置、角波およびリレーシ
ョンデータの一致性を検査することにより決定される真
の特徴点と対値を示す対リストを生成する対リスト生成
手段、２よび前記真の特徴点及び対値から照合値を決定
する照＠値決定手段から構成されることを特徴とする。 発明の実施例 以下、本発明に関して、図面を参照して詳細に祝明する
。 第２八図を参照するとｈ本発明の指紋照合装置の適用さ
れるシステムは、照合データ入力処理装置ｌ、照合デー
タ管理処理装置２．データ貯Ｈ，装＃３．照合制御装置
４．および４個の照合装置５゜６．７および８から構成
されている。ただし、照合装置は４個に限定するもので
はない。第２Ｂ図を参照すると、前記照合装置５，６．
７お工び８のそれぞれは、制御ユニット１０．Ｍ１１次
照プロセッｆ２０．’第２仄照合プロセッサ５Ｑ、′Ｊ
？よびユニット１０とプロセッサ２０．プロセラｖ２０
とプロセラｖ５０お工びプロセッサ５０とユニット１Ｏ
の間でデータ伝送するためのデータ線１０８゜２（ｌａ
、５０ａおよび制０１１線１０ｂ、２０ｂ、５０ｂから
構成されている。 嘱３図を参照すると、第２Ｂ図に示す制御ユニッ）１０
は、照会制御装置４からのデータおよび２次照せプロセ
ラｖ５０からのデータを格納する緩衝記憶３００．照会
側ｍ装置４とのデータのや９と９を行なうインタフェー
ス回路、プロセッサ２０．５０とのデータのやシと９を
行なうプロセッサインタフェース回路３Ｏ２，側働回路
３０３および転送先決定回路３０４炉ら構成されている
。 次に指紋照合時のシステムの動きをｆＺＡ図によシ以下
ＶＣ＝明する。照合データ管理処理装置２から照会制御
装置４に対し照合指示及び照せ対象となる探索指紋及び
ファイル指紋のデータ貯ｇ装置３の甲の位置１肯報を与
える。照合指不全受けた魚具制御装置４は、まずデータ
貯蔵装置３から探索指数１指を読出し照合装置５，６，
７．ＢＶこすべて共通に送９込魯次にデータ貯蔵装置３
から順次ファイル指紋を読出し照合装置５，６．７．８
に辺り込み照会を開始させる。即ち照合装置５゜６．７
．８は、探索指紋１指と、各々異なるファイル指紋との
並列照＠全行ない照付１＠を算出する。 探索指紋１指と大量のファイル指紋との照付が終了する
と照会開側１装置４は、各照合装置５，６゜７．８から
照会結果τ読出し照＠値に従って配列し直し照合データ
管理処理装置２に報告する。照合データ管理処理装置２
は照合結果を編集し信号線１２を介して出力する。 第４図を参照すると、第２図に示す第１次照合プロセッ
サ２０，３０７？よび４０のそれぞれは。 シーケンス制御回路２１０、第１次特徴点りストメモ！
Ｊ２１１．座標俊挾回路２１２、最近傍特徴点復元回路
２１３、「対」検査回路２１４．ｒ対」候補リストメモ
リ２１５、作業エリア２１６．座標整せ量決定回路２１
７，２よび制＠１記憶２１８から構成されている。第１
次特徴点リストメモリ２１１は探索指紋特徴点りストメ
モ！Ｊ２１１ａとファイル指紋特徴点りストメモ！Ｊ２
１１ｂで構成される。 第５図を参照すると、第２図の前記第２次プロセッサ５
０および６０のそれぞ牡は、シーケンス制御回路５１０
．ｉ２次特徴点りストメモ’）　５１１゜座標変換回路
５１２．対候補リストメモＩＪ５１３゜作業エリアメモ
リ５１４．対リストメモリ５１５゜領域パターンリスト
メモリ５１６ｊ候補リストメモ！Ｊ５１７．制＃記憶５
１８および演算回路５１９から構成されている。 次に本発明の一実施例の動作ｔ−ｉ６図に示すフローに
従かい以下の順に詳細に枳明する。 （１）指紋特徴点データの読出し動作 （２）座標変換動作 （３）最近傍特徴点復元動作 （４）対検査動作の一例 （５）対検査動作の変形例 （６）跪標整合量の生成及び整合動作 （７）２次照合プロセッサによる鞘密照台動作（８）転
送先プロセッサ決定動作 （１）指紋特徴点データの読出し動作 第７図に本発明の指紋照せで使用される特徴点データの
構成を示す、、特徴点データは、識別ｆ＃報、領域パタ
ーンリスト及び特徴点リストから成り立っている。鑵別
１に報は、指紋個別に伺けられた指紋識別着分、生年月
日、性別、拮柚、及び叙様分類等の情報が格納されてい
る。穎域パターンリストとは、入力データ処理装置１に
２ける特徴点抽出時の指紋領域が明領域か不明領域かで
示す情報でめる。特徴点リストとは、指紋鴇域内にある
特徴点Ｍｇ、　Ｍ４．・・・・・・、　Ｍ４．・・・・
・・ＭＩ、・−・・・・Ｍ２の特性全示した情報ｔ−裕
納しで逅−り第８図に下すデータ構造を有している。 第８Ａ図を参照すると、一般にｆ着目の特徴点は情報と
してその特徴点が分岐点か端点かを示す種別コードＱｆ
位−を示す情報Ｘｆ、−Ｙｆ、隆線方向を示すＤｆ、そ
の％微意の周囲の実密度を示すＣｆ及び特徴点Ｍｆとそ
の最近傍特徴点との間の隆線数を示すＲ７ｏ、Ｒｆｂ几
ｆム几ｆ３を有している・特徴点リスト上の位置及び方
向は、指紋領域の適宜に定められた点を原点とする直交
座標系を基準座標系としてすべて表わされている。一般
にこれらの３９６４８の中で詳細に記載されている。 第８Ｂ図は、特徴点Ｍｆの方向Ｄｌｆｙ軸とする局所座
標系における４つの象限の各々に対し特徴点Ｍｆに最も
近い特徴点（域近傍％微意と称す）Ｍｆｏｈ　Ｍｆｌｍ
　ＭＩ２うＭ　ｆ３と特徴点Ｍｆと、自Ｕ自己各々の敢
近傍特徴点との間の隆線数ｋＬ、ｆ、、几ｆ１　＊　Ｒ
ｆ２　＊几ｆ３との関係を示している。 上述の人力特徴点データが第２Ａ図の照合データ入力処
理装置１，２よび照合データ管理処理装置２を介してデ
ータ貯蔵装置３に格納される。仄に照合データ管理処理
装置２は探索指紋をデータ貯蔵装置３から読出すように
照合制御装置４に指示する。この装置４はこの指示に応
答してデータ貯蔵装置３から照合ｔｌｉｌＪ御装匝４．
第２図の制御ユニット１０．第４図の７−ケンス匍り卸
回路２１０を弁して入力特徴点リストを探索特徴点りス
トメモＩＪ　２１１　ａに入力する。探索指数の特徴点
リストがデータ貯蔵装置３から読出されるときに読出さ
れるアドレスで指定される位置からファイル指紋の特徴
点リストが読出される。この読出されたファイル指紋の
特徴点リストは上述の経路と同じ経路合弁して第４図の
ファイル特徴点リストメモリ２１１ｂに格納される。 化４図の特徴点りストメモ１７２１１には探索およびフ
ァイル指紋の入力特徴点リストが第８Ａ図の形式で格納
されている。各特徴点Ｍｆで／バされるアドレスに、種
別ヨー１９１１位置を小丁情報ＸｆおよびＹｆ、方向を
示す悄＠１）ｆ　、果暫重會示す悄１Ｉ４ｆｔＣ１，−
Ｊ？よび隆線数ｇ７ｉ−凡ｆ４が格納さ扛ている。 特徴点リストメモリ２１１から読出されたデータは第４
図の座標変換回路２１２で座標変換される。 （２）腸標変換動作 次に不発明の指紋照＠装置において使用さｎる座標変換
動作を詳述する。 ファイル指紋データと探索指紋データとは、採取時点、
採取栄件および採取環境が異なるため、両指紋データの
突合せに先行して君子の補正作業が必要になる。すなわ
ち、特徴点はパターン認識の立場からは、指紋紋様の途
切れ点の位置と方向とが重要視されるが、ファイル指紋
データと探索指紋データとは上述の工うな理由により、
多くの場付には途切れ点の位置を表現する座標系が異な
るため、探索指紋データの座標系刀為らファイル指紋デ
ータの座標系への座標変換を行なって座標整合する必要
がある。 また、指紋データには特徴点リスト以外に、指紋採取の
際の指紋の不明領域等を表現する領域パターイリストが
含まれるが、この領域パターンリストは変換の対象とは
なしない。探索指紋データに対する変換を行ない、ファ
イル指紋データとの特徴点比較処理中に、領域パターン
リストを参照する必要性が生じるが、探索指紋データの
領域パターンリストは変換前の１１ｉＬでめるたａ）、
このときはファイル指紋データＶ座標系から探究指紋デ
ータの座標系への逆変侯七行なわねばｌよらない。 第９図を参照すると、直５１．座標系（Ｘｐ−Ｑｐ−Ｙ
ｐ）上の点Ｐの座停位置（Ｘｐ、ｙｐ）が新しい直焚座
標系（ｘｑ−Ｏｑ−Ｙｑ）上の座標位置（ｘｑ、ｙｑ）
に変換された状態が示されている。両＠父幽標系の原点
（Ｊｐと０ｑ　の間は間隔（ｘ、　ｙ）だけ食位し、か
つ両直交座標系は肉就θだけ回転している。ｌ＆快前の
座標位置（Ｘｐ、　ｙｐ）と変換後の座標位置（Ｘ　ｑ
　＊ｙｑ）との間には次式の関係が成立することが幾何
学的手法によシ容易にわかる。 第１０図を参照すると、弐〇にしたがって、座標位置（
ｘｙ）から変換後の座標位置（Ｘｑ＊　ｙｑ　）Ｉ　ｐ を得るためのプロセスが示されている。すなわち。 両直又座標系の変位（ｘ、ｙ）と回転角θならびに変換
すべき座標位置（Ｘｐ、　Ｙｐ）が与えらｎると、ＣＯ
Ｓθおよびｓｉｎθをめる処理（フェーズ■）、（Ｘｐ
　−Ｘ　）　ｓｒよび０’ｐ−ｙ）をめる処理（フェー
ズ■）、フェーズ■の処理結果とフェーズ■の処理結果
との乗算を行ない中間結果をめる処理（フェーズ■）２
よび中間結果の加算まｆｃは減算により環路結果をめる
処理（フェーズ■）によシ変換されｆｃ淡標位ｎ　（Ｘ
ｑ、　ｙｑ）がめられる。 な２．上述の変換方向とは逆に、座標位置（Ｘｑ。 ｙｑ）を座標位置（ｘｐ、ｙｐ）に変換（逆変換）する
ための式は、以下に示す式■のようになる。 従来、式■２よび式■に、ｌニジ表現される変換はすべ
てソフトウェア的手法により行なわれているため、高速
処理が困離であるという欠点かめる。 とシわけ、フェーズ■と■との処理は尚速来除算愼Ｉｆ
目などの特別なＩＩ残能を有する計算イ炊を使用しない
かぎりその尚速比はむずかしい。 第１１図を参照すると、前記座標変換回路２１２は、３
個のレジスタ１１１０．１１１１２？よび１１１２゜６
個の選択回路１１２０．１１２１．１１４０．１１４１
．１１７０およびｘ１７ｔ、５１１Ｉ￥］の加減＄Ｋｔ
ｌ１３０．１１３１．１１３２゜１１６０′Ｊ？よび１
１６１と、４個の乗算器１１５０，１１５１゜１１５２
２よび１１５３　および読出し専用メモリ（１（、ＯＭ
）１１８０から構成されている。 ＲＯＭ１１８０は、２個の直焚農機系（ｘｐ−ｏｐ−Ｙ
ｐ）と（Ｘｑ−Ｏｑ−Ｙｑ）との間の回転角θに対する
円関数１直を予め格納している。 選択回路１１２０２よび１１２１は、変換モード指示信
号（モード信号）ＬＮＶが順変換を指示しているときは
それぞれ入力端子ＸとＹの各出力、モード１ｇ号ＩＮＶ
が逆変換を指示しているときはそれぞＡ７Ｊ０減算器１
１６０２よび１１６１の各出力を選択するＬうに動作す
る。同様にして、選択回路１１４０′Ｊ？よひ１１４１
は＋１変換時にはそれぞれ加減算器１１３０ｊ？よび１
１３１％１３１％逆変換れぞれ入力端子ＸとＹの各出力
を選択し、選択回路１１．７０２よび１１７１は順変換
時にはそｎぞれ加減算器１１６０および１１６１．逆変
換時にはそｎ、それ加減算器１１３０２よび１１３１の
各出力を選択し、加減算器１１３０゜１１３１．１１３
２ｉ１１６（１−よび１１６１は順変換時にはそ几ぞれ
減算、ｄＪｊ、其、減算、加算寂よび減算、逆変換時に
はそｎぞｎ７Ｊｌ］見ニ、加ｎ１加算、減算および加算
を行なうように動作する。 先ず、入力端子Ｘ、ＹｙよびＤにそｎぞれ変位ｘ、ｙ２
よび回転角θを与え、かつ前置１６号ＰＡＬｔ印加する
と、変位ｘ、ｙυよび回転角θがそれぞ扛しジスク１１
１０．１１１１ｙよび１１１２に入力される。レジスタ
１１１２に入力さＡた回転角θは几０Ｍ１１８０をアク
でスするためのアドレスになり、ル０Ｍ１１８０から正
弦１直ｓｉｎθと余弦１直ＣＯ８θとを読み出す（第１
０図に２けるフェーズ■）。 仄に、前置１ｇ号ＰＡＬの印加τ走し止め、かつ入力端
子Ｘ、Ｙ２よびＤにそれぞｆ″ＬＬ変換き座標位置υよ
び変換すべき直焚座標系に２ける特徴点の向きを与える
。このときモード信号ＩＮＶが１０＃か＠１”　かに尾
Ｎ答してそれぞｎ順変換指示か逆変換指示かになシ、各
選択回路と各加減′Ｊ４−益は前述のように動作する。 いま、モード信号■〜Ｖが”Ｏ＃でｂると、〃Ｄ減算器
１１３０ｈ−よび１１３１は第１０図に示すフェーズ■
、乗算器１１５０，１１５１，１１５２ｊ？工び１１５
３はフェーズ■、そして加減算器１１６０ｙ工び１１６
１はフェーズ■の各処理を行ない、出力端子ＸＴとＹＴ
　とたら順変換後の座標位置Ｘｑとｙｑ　が得られる。 加減算器３２は＋１１４俊換すべき直９：、座標系に−
一ける特徴点の回さから回転用θを減じ、この魁を順変
換後の直９．脹標系に２ける狩像点の回さとしＣ５出力
端子ＤＴから出力させる。 次に、モード信号１〜■が″　１＃でｉりると、乗Ｉｇ
Ｌ器１１５０．１１５１．１１５２．　ｗよび１１５３
はそれぞ扛式■に２けるＸｑ’ＣＯ８θ、ｙｑ＠５Ｌｎ
ｏ、　ｙｑ’ＣＯ８θおよびＸｑ−８ｉｎθの釆其、加
減算器１１６０２↓び１１６１はそｎぞれＸｑ’ＣＯ８
θ−’ｆ　ｑ　’　Ｓ　ｌ　ｎθの減算とｙｑ１１ＣＯ
３θ＋ｘｑ＠ｓｉｎθの加算、加減＠器１１３０２、Ｃ
び１１３１はそれぞれ（Ｘｑ−Ｃ０Ｓ０−ｙｑ＠Ｓｉｎ
θ）十ｘと（ｙｑ　弓ｏｓθ＋ｘｑ＠５ｊｎ０）＋ｙの
各加算を行ない、出力端子ＸＴとＹＴ　とから逆変換後
の座標位置ＸｐとＹｐが得られる。加減算器１１３２は
逆変換すべ＠直交淡標系における特徴点の同きに回転角
θを加え、この値を逆変換後の直焚座標系に２ける特徴
点の向きとして、出力端子り、から出力させる。 以上のような構成の採用によシ、順・逆いずれへの変換
に対する座標位置も一挙動で得られるようになるため、
両刀同性の高速脱標変換ができるようになる。特徴点メ
モリ２１１に第１３図で示される！＃徴像点ストが格納
さ扛る場せには以下に示す最近＠特徴点の復元動作は不
要でろる。しかしデータ貯蔵装置の容量を減小きせよう
とするときには、第８八図に示される狩像点リストが特
徴点リストメモリ２１１に格納されなけｎばならない。 この場会には以下に示す最近傍特徴点の復元動作が必ず
必要となる。 （３）最近傍特徴点の復元動作 第４図の座標変換回路２１２２工び成近傍将像点復元回
路２１３を用いて最近傍特徴点が第１３図に下す様に特
徴点リスト上にＭｆ　、、　Ｍｆ　ｌ、　Ｍｆ　２゜Ｍ
ｆａとして付加さｎる。こｎを詳述すると、採糸２工ひ
ファイル特徴点の間の近似度を定量的に表すものとして
、各特徴点の局所的特徴、すなわち、甲心農標系の選び
方に左右す扛ない各％像点の局所的特徴による近似度を
用いる。 例えば、前述の種別を表わすＱもその一つになる。ま・
た、対象とする％像点から予め定めた一定の距離以内に
わる他の特徴点の数も局虜的特徴として用いることがで
きる− とくＶこ、以下に示す局所的特徴は、対候桶リストを作
るのＶＣ極めて有力な材料を提供する。 今、ろるパターンの任意のｆ金目の！＃徴像点Ｍｆとす
るとき、この特徴点Ｍ　ｆの位置Ｘｆ、Ｙｆをその座標
原点とし、方向ｉｆｆをＸ軸の方向とする直焚麗椋系を
この特徴点Ｍｉで定よる部所座標系と定義する。 この局所昆標系の各象限（第１象限、第２象限１第″４
象限２よび纂３象限）ＶＣおいて、この座標原点（つま
り対象となっているもとの特徴点Ｍｆ　）に最も近い位
置Ｖこある他の特徴点の番号をそれぞれｆｏ、ｆｌ、ｆ
２＆よびｆ３とすると、もとの特徴点Ｍｆは、このＭｆ
　Ｋよって定まる局所座標系の各象限内にそれぞれ他の
最近特徴点ＭｆＯｓ　Ｍｆ　１＃Ｍｆ２．ｈよびＭｆ　
３をもつという局所的特徴を有していることになる。勿
論この局所的特徴は中心座標系の選び万とは無関係でわ
る。 そこで今、探索指紋の任意の１沓目の！＋！ｆ徴点Ｍ像
点ついて上述のようなｆｏ、　ｆｌ、　ｆ２およびｆ３
が侍ら扛て２シ、まｆｃ１照付すべきファイル指紋の任
意のＪ管口のを像点Ｍｊ　についても同様にＭｊによっ
て定まる局所座標系の各碌限内に特徴点番号に０．ｋｌ
、に２寂よびに３　をもつ最近特徴点が得られていたと
すると、この両刀の特徴点ＭｆとＭ」との局所的近似度
は、それぞれの局所座標系上で、対応する象限内にある
填近特徴点同志の相互関係が、ある一定のしきい値近傍
内にりるか否かを判定することで容易に定量化すること
ができる。例えは、対応する象限内に２ける最近特徴点
同志の、そ２’Ｌぞ扛の局所座標系にυけるＸ至襟の差
？よびＹ座標の差をめ、この差がめるしぎい埴以内にあ
る場合には、各象限の最近特徴点ごとに近似度の■みに
１を加算するという形で定量化することができる。 このように、各特徴点に対し、この喘−像点で足まる局
所座標系の各象限内に２ける埴近％似点を見出し、こし
をもとの特徴点と対応つけるという処理（以下りンーシ
ョン生成処理）は、上述のように、パターンの同一性の
照合を行なう場合の軍装な一つのステップとなる。 とくに、掲載照合等の処理に２いては、一つの探索指紋
に対しこれと照付して同一性を判定すべきファイル指紋
の数が厖大な童となるので、このようなりレーンヨン生
成処理を高速かつ確芙に央行する必要かめる。 第１２図を参照すると、第４図の近傍特徴点復元回路２
１３は特徴点レジスタ１２０１　（Ｑ）、　１２０２（
Ｘ）、１２０３（Ｙ）ｉ−よび１２０４（１）ハ　アド
レスレジ、ｌ’　１２０５（Ａ）、１２０５（Ｂ、）、
１２０６（Ｅ）＄−ｊび１２０６　（Ｆ）、定数加算器
１２０７．人ヵ迅択器１２０８、２乗計算器１２０９（
Ｘ２）おｊび１２１０（Ｙ２）、加算器１２１１、レジ
スタファイル１２１２、比較器１２１３、制何器１２１
４、一致検出器１２１５　および県止ゲート１２１６’
ｊｉ＝有している。 さて、木芙施例に用いられる特徴点リストメモリ２１１
は′Ｆ′記のように構成されている。 第１３図に示すように、８ビツトの２進数で指定さルる
２５６１固のロウアドレスと、３ビツトの２進数で指定
される８個のコラムアドレスと工夛なる全部で２０４８
個のメモリアドレスを有している。この各ロウアドレス
は、一つの紋様パｌ　−ｙの各特徴点に対応し、特定の
１沓目の特徴点の各情報は、対応するｆ合口のロウアド
レスをもつ各コラムアドレスに以下に述べるように格納
されている。 まず、０査目のコラムアドレスには、１沓目の特徴点の
種別（端点分岐点特異点等の別）を表わす情報（以後Ｑ
ｆで表示）が格納され、１査目のコラムアドレスには１
番目の特徴点のＸ座標（以後Ｘｆで表示）が、２査目の
コラムアドレスにはｆ査目の％像点のＹ座像（以後Ｙｆ
で表ボッが、３沓目のコラムアドレスには１４目の特徴
点の方向Ｄ（以後Ｄｆで表示）がそ扛ぞｔ″ＬＬ格稍て
いる。 こ扛らのＸｆ、Ｙｆｙ工びＪＪｆの１児は、この紋様パ
ターンのＱ１ソ中心を座標原点とする暫定のＸＹ座標系
（以後必要の場合には中心淡襟系と１１′ｉ−称して区
別）で記述ざ扛でいるが、臣椋糸抽出の際の誤差が一般
的にばかな９大きくなってしまう。 また、ある紋様パターンの各Ｑ、ｆ、　Ｘｆ、　Ｙｆｈ
−よび１）ｆのすべでの値が、この処理に元７ヒち、す
でに上位装置Ｖこよって各メモリアドレスに上述のよう
に書き込ま扛ている。この場合に、薔き込まれたこの紋
付パターンの最後の特徴点の次のロウアドレスには、そ
の０査目のコラムアドレス（Ｑを俗稍するアドレス）に
％足の終了マーク（Ｅ　０　Ｄ）を格納し、処理の終了
を指示するのに用いる。 さて、９合口ρλら１２２沓目での４１１１！ｉｌのコ
ラムアドレスは、本実施例が生成する最近値特徴点を格
納丁べきメモリアドレスで、この最近傍％像点とは以下
に述べるようなものである。 今５％足の１４ｆ目の特徴点をとハ第１４図に示″ｊよ
うに、この特徴点の位置Ｘｆ、Ｙｆを腔椋涼点とし、方
向ＤｆをＸ軸方向とする局所座標系（以後Ｘｆ’Ｙｆ局
所座標系）を作ったとする。このＸｆＹｆ局所座標系の
各象限ごとに、この局所座標系の原点（つまシｆ番目の
特徴点の位は）［紋も近い位−にある他の特徴点を１個
ずつとシ、そｔらの各特徴点の番号を象限の順番にＭｆ
ｏ、Ｍｆｌ。 Ｍｆ３Ｌ”よびＸｆ２とすると、こｔが最近値特徴点と
なる。 すなわち、本実施例は、任意の特徴点に対し。 その％徴点の近傍の状態を把握するため、この特徴点で
一義的に定まる局所座標系上の各象限における最近特徴
点金探し、七ｎらともとの特徴点とを関連ずける動作を
示している。こうして得らｆた最近値特徴点は、Ｘｆ、
Ｙｆ＞工びＤｆのデータと異なって、中心座標系の選び
方とは無関係でめるという特徴を有している。 さて、これらの最近値特徴点は、もとの特徴点に対応す
るｆ番目のロクアドレスの、以下に示す各コラムアドレ
スに格納さする。 この局所座標系の第ｌ象眠にるる厳近傍特徴点の荀号Ｍ
ｆＯｔ−第９否目のコラムアドレスに格納する。第２象
限にろる最近傍特像点沓号Ｍｆｌを第１０番目のコラム
アドレスに、第４象限にめる最近傍％像点の番号Ｍｆ２
’を第１１番目のコラムアドレスに、第３象限にめる最
近値特徴点の査号Ｍｆ３を第１２４目のコラムアドレス
にそしそれ格納する。なお象限の順序と格納するコラム
アドレスの順序がずｔているのは後述するハードウェア
を簡単にするためでろる。 最近傍特徴点生成回路の甲の制御部１２１４（第１２図
ンはマイクログログラムを格納する制御記憶（図示せず
）金言み、このマイクロプログラムを逐次読み出して央
行することにより処理を進）行させる。この処理の進行
を第１５図にフローチャートとして示す。 まず、開始指示が２イン２９９　（ＳＴＲＴ）を弁して
シーケンス制何回路２１０から供給さｎ１最近傍特徴点
生成処理が開始されると（第１５図）、制御部１２１４
はアドレスレジスタ１２０５　（Ａ）ｐよび１２０５　
（Ｂ）を初期１直設駕する。アドレスレジスタ１２０５
は最近傍％像点金求めるべきもとになる特徴点全指示す
るレジスタでロクアドレス指定部分１２０５（Ａ）とコ
ラムアドレス指定部分１２０５　（Ｂ）とを有し、初期
値設定によってい′ずれもＯにクリアさｎｂそ扛ぞｎ最
初のメモリアドレスを指示するようにセットさ扛る。（
第１５図イ）。 次に、制御部１２１４は、レジスタＩ　２０５　（Ａ）
の内容人で指７り扛る特徴点リストメモリ２１１のロウ
アドン′スから特徴点のＱＡＩ　ＸＡＩ　ＹＡ　＞よび
ＤＡを読み出し、ＸＡ、ＹＡ毅よびＤＡを第１１図に示
す座標変換回路２１２のパラメータレジスタ１１１０．
１ｉ１１２よび１１１２にそｎぞ−ｎｉ換パラメータと
してロードする。このために第１２図の制御部１２１４
は、アドレスレジスタｌ　２０５　（Ａ）ｐよび１２０
５　（Ｂ）の内容全ライン１２０５６（Ａｉ））を介し
て％像点りストメモリ２１１に供給する仁とにより、ア
ドレスレジスタ１２０５　（Ａ）で指定される特徴点リ
ストメモリ２１１のロクアドレスカラアドレスレジスタ
１ｚ０５（Ｂ）で指定さ扛る４バイト分すなわらＱＡ、
ＸＡ、ＹＡａよびＤＡを読み出す。この読み出したＸＡ
、ＹＡＧよびＤＡの値をそ庇ぞれ第１１図のライン１０
１０　（Ｘハ　２０２０（Ｙ）′Ｊ？よび１０３０　（
１））τ介して各パラメータレジスタに供給し、ライン
１０００　（ＰＬ）にラッチパルスを供給することによ
り、これらの埴τ各レジスタに設定する（＠１５１５図
ラ フに、第１２図の制御部１２１４は上で院か出したＱＡ
が終了マークでろるか否か判定し、もし終了マークでめ
る場８にはこｎで処理を終了（第１５図才）シ、そうで
ない場合には下記に進む（第１５図工）。 次に、第１２図のｆｉ＋１１帥部１２１４はγドレスレ
ジスタ１２０６（Ｅ）、１２０６（Ｆ）およびレジスタ
ファイル１２１２の初期値設定を行なう（第１５図力）
。 アドレスレジスタ１２０６は、アドレスレジスタ１２Ｏ
５と同様に、ロウアドレス指定部分１２０６　（Ｅ）と
コラムアドレス指定部分１２０６　（Ｆ）とを有し、こ
れは比較器べ＠特徴点舎号全指示するためのレジスタで
、初期値設定によっていずｎもＯにクリアさｎる。 また、レジスタファイル１２１２は４１固のレジスタ１
２１２−０〜１２１２−３からなシ、この各レジスタは
七ｎぞ扛のアドレスフィールドＭＱ。 Ｍｌ、Ｍ２２よびＭ３と、そｎぞ扛の距離フィールド几
０．　ｋＬｌ、几２ｈ−よび几３とからなっている。 このアドレスフィールドＭＯ−Ｍ３は、現任アドレスレ
ジスタ１２０５　（Ａ）で指定す７″Ｌゐものとの特徴
点に対し、処理の現段階でみつかった最も近い位置にあ
る他の特徴点の番号を前述の局所座標系の各象限ごとに
別紙に格納する丸めのフィールドで、第１．象限の点の
否号をＭＯＩＩ？：、第２家限の点の食号をＭｌに、第
３象限の点の全号をＭ３に、第４象限の点の蕾号をＭ２
にそ扛ぞｎ格納する。 また、距離フィールド几０〜几３は前ム己局所股標系の
原点（つまりアドレスレジスタ１２０５　（Ａ）で指定
さｎるものとの特徴点の位置ノからこれら各特徴点Ｍ０
〜Ｍ３までの距離の２乗値＊−ｔｒｂぞｎ格納するフィ
ールドである。 上述の初期値設定ｖｃνいて、レジスタファイル１２１
２のこれらの各レジスタのすべてのビットには″　１”
がセットｓｎ、そｎぞれ、アドレスフィールドＭ０〜Ｍ
３は対応する特徴点が存在しないこと金表わし、距離フ
ィールド几０〜Ｒ３に表わし得る最も遠い距離に設定さ
しる。 さて次に、制［６１２１４は、アドレスレジスタ１２０
６　（Ｅ）と１２０６　ＣＦ）との内存を２イン１２０
５６　（ＡＤ）を介して特徴点リストメモリ２１１に供
給することにより、アドレスレジスタ１２０６（Ｅ＞テ
指定さｎる４バイトすなわｓ、Ｑ　ｇ−Ｘ　ｇ、ＹＥ２
、Ｊ、びＤＢを睨み出し＞　Ｑｍを特徴点レジスタ１２
０１　（Ｑ）に格納する。 また＞　ＸＢ＃　ＹｌｌおよびＤｉを、座標変換回路２
１２（第１１図）のライン１０１０（Ｘ）、１０２０（
Ｙ）２よびｌ　Ｏ３０（Ｄ）のそれぞｎを介して供給す
ることによシ、ＸＡＹＡ局所座標系（ＸＡ、　ＹＡ＞よ
びＤＡにより定まる局所座標系）で表わざｎたそれぞれ
の値ＸＢｈＹＥＡ　９よび１）ｌ！Ａ　Ｋ座標変換し、
こうして得られπそｎぞれの値をライン２１２０（Ｘ’
）。 ２１３０　（Ｙ’）、！３−ｊび１０６０（１））’に
弁り、％ＲＡレジスタ１２０２　（Ｘ）、　１２０３　
（Ｙ）　＄−よび１２０４（Ｄ）に格納する（第１５図
キ）。 さて仄に、制御部１２１４は、特徴点レジスタ１２０１
　（Ｑ）に読み出された前述のＱｇが終了マークを示す
まで、以下に述べる第１５図７側の処理を実行しく第１
５図り、Ｎ）、終了マークが現われると第１５図７側の
処理に入る（第１５図り。 Ｙ）、。 第１５図ケの実行に入ると、下６己のような処理が行な
わｎる。 すなわち、特徴点レジスタ１２０２（Ｘ）９よび１２０
３（−￥）に格納さ′ｎた前述のそれぞｎの内容ＸＥＡ
および１８人は２乗計ｐ−器１２０９（Ｘ２）ｓ−よび
１２１０　（Ｙ２）でそノｔぞれ２乗さＧ１刀１ＪＪ−
器１２１１で力負算さ几、ライン１２１１０にＸ２　、
Ａ　十Ｙ２Ｂムの出力を生じこ７ｔは比較器１２１３の
−万の入力に那えらする。−万、％像点レジスタ１２Ｏ
２（Ｘ）　ｗ　ヨび１２０３　（Ｙ）に格納さｒしてい
る内存ＸｇＡ−よｒｊ　Ｙ　ｉｕのそれぞＣ（１）符号
ビットに０τそｎぞｎｓＸ＆よびＳＹで表わ丁）が２ビ
ツトのｆ−タ（ＳＹ、ＳＸ）としてライン１２０２３　
’ｒ介して読み出さ扛る。この２ビツトのデータ（ｓｙ
、ｓｘ）で表わさする２進数はＸ　ＢＡＩ　Ｙｇ人で指
示さｎる特徴点の位置が、局所虫標系のそｎぞれ第１家
限、第２象限５ｇ３象限２よび第４象限にりる場せに鵬
それぞｆ′Ｌ（０，０）＝０．　（０，１）＝１．　（
１，１）＝３２よび（１，０）＝２　という１直をとる
ことになる。市１」御部１２１４はライン１２１４０會
介して人力選択蕗１２０８に制御信号を送り、上述の２
ビツトデー１　（ＳＹ、　５ｘ）ｔ−迷択し、こｎｆ　
ラ（７１２０８０（１：弁してレジスタファイルに１２
１２のファイルレアビレス指定侶号として供給する。 この結果、レジスタファイル１２１２の中の。 （ＳＹ、ＳＸ）で指定されるレジスタ（つまり、特徴点
レジスタに格納され′ｆｃｔ￥ｆ徴点が存在像点象限に
刈応するレジスタ）の距離フィールドの内容几（ＳＹ、
ＳＸ）　が１ｙ１２１２０　ｋ弁して読み出さｎ１比較
器１２１３のもう両万の人力に供給さ扛る。 こｔによシ、比較器１２１３は上述の、Ｒ（ＳＹ。 ＳＸ）の１直と前述のＸ　２　ｌＡ十Ｙ２”Ａの愼とを
比較し、現在萱でに得らｎている値、ａ（ｓＹ、ｓＸ）
よりも同じ象限内に、今回座標原点により近い特徴点が
現わｆした４ｈ台、つまり Ｒ（ＳＹ、　８Ｘ）＞Ｘ２ｍＡ＋ＹｚｇＡが成立した場
合にはライン１２１３０に１１”を出力する。 両万、アドレスレジスタ１２０５　（Ａ）の内容と、ア
ドレスレジスタ１２０６　（Ｅ）の内容とは一致検出器
１２１５において比較されて２＃）、両者が一致してい
る場合、つまり、もとの特徴点と比較すべき特徴点とが
同じものでめる場合にはライン１２１５０に１１′を出
力して禁止ゲート１２１６の通過１ｃ禁止する。 この結果、 Ａ、＋Ｅ の両方の条件が成立するときにかぎクライン１２１６０
が１＃になる（第１５図ケ、Ｙ側）。 ライン１２１６０に１”が出力さｎると、レジスタファ
イル１２１２が書込み状態に制御さｎｌ　レジスタファ
イル１２１２の中の前述の２ビツトデータ（ｓ’ｙ、　
ｓｘ）で指定さｎ；ｂｖレジスタ内容が更新される。す
なわち、新らしい特徴点を指定するアドレスレジスタ１
２０６（Ｅ）の内容Ｅがライン１２０６０を介してアド
レスフィールドＭ（ＭＹ、ＳＸ）に格納され、また、加
算器３１１の出力ｘ２．Ａ十Ｙ”ｌｌＡの値がライン１
２１１０を介して距離フィールド１も（ｓｙ、ｓｘ）に
格納さｎる（第１５図コ）。 こｎがすむと制＃部１２１４は、定数加算器１２０７ｔ
−用いてアドレスレジスタ１２０６（Ｅ）の内容を１だ
け増加し仄の比戟丁べ＠特徴点を指がするように史新し
く第１５図す）、再び仄の特徴点を読み出す処理（第１
５図キ）に戻る。 また、前述の（１）式の条件が成立しない場合、つまシ
、今回読み出した比較すべき特徴点の位置が、すでに得
られている同じ象限内の特徴点の位置よＪも原点（もと
の特徴点）に近くない場合が、またはこの比較すべき％
像点かもとのｔｐ＞微意と同じものである場合にはレジ
スタファイル１２１２の内容を更新することなく（第１
５図ケ、Ｎ）、アドレスレジスタ１２０６　（Ｅ）の内
容を１だけ増加して次の比較すべき特徴点を指示するよ
うに史新しく第１５図す）、再び次の軸像点を読与出す
処理（第１５図キ）ＩＣ戻る。 ７１１＜シて、第１５図のキ、り、ケ、コ、すの処理を
蘇り返すことにより、制＠部１２１４は比較すべき新ら
しい％像点をつぎつき゛に読み出し、もとの特徴点でき
まる局ｒａｍ標系の各象限ごとに、もとの特徴点により
近い他の特徴点が現わ几るたびに、この特徴点のデータ
を用いてファイル１２１２の内容を更新する。この処理
を、第４図の特徴点リストメモリ２１１に貯わえらｒし
ている％ａ点の終シが現しるまで（読み出さルたＱｇに
終了マークが現われるまで）繰り返す。 以上の処理が終ると、レジスタファイル１２１２のアド
レスフィールドＭＯ−Ｍ３の中には、アドレスレジスタ
１２０５　（Ａ）で指定さ往るもとの特徴点に苅し、最
も近い位１直にめる他の特徴点の前号（ロワアドレス）
が各象限ごとに別々にめらしたことになる。 そこで仄に、こうしてめらまたファイル１２１２のアド
レスフィールドＭ叶招３の内容を、アドレスレジスタ１
２０５　（Ａ）で指定さｎる、特徴点リストメモリ２１
の最近傍特像点格納位１ｔＭＡｏ〜ＭＡ３に格納する。 この最近傍特徴点格納処理に９つると、制御部１２１４
は、もとの％像点のコラムアドレスを指示するアドレス
レジスタ１２０５　（Ｂ）の（ハ）谷を、最近傍特徴点
格納位置の最初を指示する値として４に初期値設定する
（第１５図ン）。 また、こオＬとともにライン１２１４０の出力全入力選
択器１２０８がライン１２０６０を選択するように切替
える。このライン１２０６０にはアドレスレジスタ１２
０５　（Ｂ）の下位２ビット分が供給され一〇いるため
、こ扛によジ、レジスタファイル１２１２の中の各レジ
スタからの読み出しは、アドレスレジスタ１２０５　（
Ｂ）の下位２ビット分（つま）Ｂから４を引いた１ｉｉ
ｉ）で指定さγしる。 さて、レジスタファイル１２１２の上述のようにして指
定さ

【るアドレスフィールドＭ（Ｂ−４）の内容は、読
み出さｎｌ　ライン１２１２１（ＷＤ）を弁して特徴点
リストメモリ２１１の香き込みデータとして供給さｎる
。−万、アドレスレジスタ１２０５（Ａ）の内容２よび
１２０５　（Ｂ）の内容ｔよライン１２０５６（ＡＤ）
を介して第４図の特徴点リストメモリ２１１のそれぞｎ
ロウアドレスおよびコラムアドレス指定データとして供
給さｎている。このため制御部１２１４は書き込みパル
スをライン１２１４１（Ｗ）を介して特徴点リストメモ
リ２１１に供給することによυ、上述のファイル１２１
２のＭ（Ｂ−４）のブータラ特徴点りストメモ！Ｊ２１
１の最近傍特徴点格納位置ＭＡＢに転送格納することが
できる（第１５図ス）。 この転送がすむと％ｆｌｔｌＪ　８部１２１４は、定数
加算器１２０７を用いてアドレスレジスタ１２０５（Ｂ
）の内容ヲ１１どけ増加し、矢のファイルアドレスおよ
びコラムアドレスを指示するように更新する（第１５図
ス）。 以上の処理を１２０５　ＣＢ）の憩がオーバフローして
０になる１で繰９返丁と（第１５図セ、Ｙ）。 アドレスレジスタｌ　２０５　（Ａ）で指定さ几るもと
の特徴点に対するすべての最近傍特徴点の格納が終了す
るので、開側１ｆｌｉｌ　２１４は、定’ａ　７Ｊ０Ｊ
ｌｌ　器１２０７を用＼ハてアドレスレジスタ１２０５
　（Ａ）の内容に１を加えて、仄のりレーンヨンデータ
をめるべきもとになる特徴点を指示するように更新する
（第１５図））。 〃・くして、この新ししいもとりこなる％微意の各デー
タが読み出さｎ１第１１図の座梯裳換回路２１２のパラ
メータレジスタ１１１０〜１１１２に格納１もこの新ら
しい％微意に対する局所画像系を構成する処理（第１５
図り）に戻る。 こうして、レジスタ１２０５　（Ａ）の内容が更油さ′
ｎ、もとになる特徴点ｋｌｉらしく指定するごとに、そ
の特徴点に対する局所座標系が＋１／７成され、第１５
図のキ、り、ケ１、り、すのループによシ、他の全部の
％微意が順番に４’Ａ　ｚ＜さｆＬ５　こ２ｔらの中か
らこの局所座標系の各象限に２ける取返傍点を相承する
データがレジスタファイル１２１２甲に生成さｎる。こ
Ｇが丁ひと第１５図のス、セのループで、こびらをもと
の特徴点に対する最近傍特慎点として特徴点リストメモ
リ２１１のＪ伎近悔特徴点格納位置に転送さｎる。 以上のような形で制御部１２１４にニジ処理が餘９返え
さｎるが、こうして、すべての特徴点に対丁ゐレジスタ
１２０５　（Ａ）の指定／Ｊｉ丁“むと、特徴点リスト
メモリ２１１のすべての最近傍％像点の生成が完了さｔ
ｌ　レジスタ１２０５　（Ａ）のつぎの更新により、終
了マークが読み出さｎ（第１５図工、Ｙ）、処理が終了
する（第１５図才）。 以上述べ罠ようＶＣ１一つの紋様パターンの各特偵点の
位置と方向とが与えらｎた場合に、こｎら各特徴点の近
傍の状態を把握する７こめの情報として、各特徴点ごと
に定まる局所脱係系を用い、この各象限に２ける他の最
近傍％像点を見出すことによシ、もとの特徴点に対する
工ｌ近傍特徴点を比較的ｒａｓ単なアルゴリズムにより
高速で生成することができる。 こうして生成さＱ７こ最近傍特徴点は、各１ザ徴点の位
置方向を表わ丁もとのデータと異って、甲ノひ座標系の
選び刀と燕関係な量であゐため、中心麗欅系が整合され
ていない二つの紋様パターンの照＠を行なう場合にまず
必要となる対候補すスト’４作成するための有力な材料
を提供する。 （４）対使食動作の一例 第１６図を参照すると、第４図の対４莢食回路２１４の
一例は、リレーション連結部２１４１．爵像点記憶部２
１４２υよび対検査都２１４３から構成さｎている。 以下１個の特徴点に対する％憚点データとその特徴点に
関する破近籾特徴点の特家点蕾号３よびそのリレーショ
ンからなる基不リレーションデータとを総称するときは
こｎを総特像点データとい＼、１個の指紋に対するすべ
ての総特像点データまたは後述の総連結データを総称す
るときはこｎを指紋データという。 リレーション連結部ｚ１４１は、特徴点リストメモリ２
１１に格納さｒた指紋データの各特徴点の羞奉りレーシ
ョンデータ中の最近傍特徴点の特徴点舎号をその特徴点
に関する局所座標の位置データ２よび方向データに変換
してリレーション連結データを生成し、こｎを特徴点記
憶部２１４２に送って格納するように結＠さしている。 特徴点記憶部２１４２に格納＝ｒする総連結デー”Ｕ、
第’ｌＪ７ｍ、に示すように各０倣点について特徴点デ
ータとすＶ−ンヨン述鮎データ（リレー／−Ｉ７ｒｊｊ
、位置データｘｉｊ＊ｙｉｊ、方向データｄｉｊ）とか
らなっている。 「対」検出部２１４３は特徴点記憶部２１４２から探索
指紋２よびファイル指紋のそＡ−ｔＴＬ　１個の特徴点
の総迩鮎データを取出して「対」となるべき特徴点を検
出子ゐ役割を荷って２９、この「対」検出部で検出さｎ
た「対」の特徴点に関する総連結データの組付せは第４
図の対候抽リストメモリ２１５に送らｎて格納さ扛る。 ここで、「対」とは、探索指紋の丁べての特徴点の２の
２のに対して、そｎらの総特像点データまたは総江結デ
ータとファイル指紋の各特徴点の総特像点データまｌこ
は総連結データが一致する特徴点の組合せをいう。当初
の比較一致刊断のときは探索指紋の１個の特徴点に苅し
てファイル指紋の仮数の％像点が比較一致と判断きｎて
１：ｎ（ｎ≧２）の組合せとなる場脅がめる。この１：
ｎの組付せば更に処理を施きＥて１：ｌの「対」となる
が、以下の説明ではｌ：ｎの組合せについても「対」と
いう。 第４図の特徴点リストメモリ２１１に格納さｎるデータ
は、１個の％像点に関してその時像点独別（Ｑｉ）、集
密量（Ｃ１）、位置データ（Ｘｉ、　Ｙｉ）。 方間データ（Ｄｉ）ｖよび最近坊特徴点の丁べての　′
Ａ不’）　Ｖ　’／　ａ　：／データ（ｒｉｊ、　Ｍｊ
　）　？ｉ　１　ｔｆｉとした酩特像点データの１指紋
分の集シでａり、こＧらはリレーション連結９２１４１
からのアドレス１６号２１４６をうけてデータ信号２１
４４によってリレー７−Ｊン連鮎部２１４１に１畝次出
力さｎる。 リレーション遅結８２１４１は、アドレス信号２１４６
によって特徴点りストメモ’Ｊ２１１ａから最近傍特徴
点の基奉りレーションデータを順次胱出丁と、この屑不
すレーショ／データ中に言まｎる符像点食号（Ｍｊ）を
その特徴点に門する局Ｐｉｆ座標による位置データ（Ｘ
ＩＪＩ　ｙ＋Ｊ）ｊ？よび方向データ（ｄｉｊ）に変換
してリレーション（ｒｉｊ）と共にデータ信号２１４１
１によって特徴点記゛１．は部２１４２に＋：ｍ仄送出
する。特徴点■己１意都２１４２はこのデータ信号２１
４１１によって嗣仄送らγしてくるりレーンヨン述紹デ
ータを貯えて軸像点データと共に第１９■に示す形成で
総、１！８紹データを構成しＣ第１８ωの探索特徴点メ
モＩＪ　１８０２に格納する。 探索指紋の１個の特徴点に関する上述のりレーション連
結動作が終了すると、リレーション連結部２１４１は％
像点りストメモリ２１　ｌｂからファイル指紋の１個の
％像点の総符像点データを読出し前述の探索指紋の場曾
と同様に総連結データを構成して第１８図のファイル％
像点メモリ１８０３に格納する。 ％像点記憶部２１４２の探索符憾点メモＩＪ１８ｔＪ２
２よびファイル％像点メモ！ｊ１８０３ｒζそ扛ぞｎ１
個の特徴点の認連結データが格納し終ると、リレ−７ヨ
ン迎結部２１４１は指令１ｇ号２１４１０によってその
こと１ｃ「対」検出部２１４３に知らせるので、「対」
検出部２１４３はｒドンス１Ｈ号２１４３１を送ってそ
ルらをデータ信号２１４２１によって読出す。 一万すレーンヨノ連結部２１４１はこの間にファイル指
紋の２企目の耗％徴点データを胱出し、特徴点記憶部２
１４２のバッファメモリの空きを利用してリレーション
連結動作全行い、ファイル特徴点メモＩＪ　１８０３の
データが「対」検出部２１４３に抗出さｎためとにそれ
を格納する。 ！１徴点記憶部２１４２に格納さ２ｔて［対］検出部２
１４３に抗出さｎた探索指紋２よびファイル指紋の特徴
点の総連紹データは、「対」検出部２１４３に２いて「
対」関係の有無が検食さ扛。 探索指紋の特徴点の総連結データとファイル指紋の特徴
点の総連結データとが所定のしきい値内で一致するとき
、こｎらの総連結データの組合せはデータ信号２１４７
によって第４図の対訣補リストメモリ２１５に送らｎ１
アドレス信号２１４５に指定さ扛た査地に格納さｎる。 上述のりレーション連結動作と「対」検出動作は、先づ
探索指紋の第１番目の特徴点に対してファイル指紋のす
べての特徴点について行わし、こしが終ると探索指紋の
第２査目の特徴点に対して同様にファイル指紋の全特徴
点について行わｎ１以下こｎを牒返して探索指紋とファ
イル指紋の丁べての特徴点の組付せについて行わ７′Ｌ
る。 探索指紋とファイル指紋のすべての特徴点の組合せにつ
いての上記の「対」検出動作が終了してすべての１対」
が対候補リストメモリ２１５に格納さ扛ると、シーケン
ス制御回路２１０は「対」検出ｔＪ２１４３から指令信
号２１４８によってそのことが知らさｎる。 第１９図を参照すると、リレーンヨン遅紘部２１４１は
制御回路４０１０によって−」碑さｎるシフトレジスタ
４０１．Ｘレジスタ４０２Ｘ、’Ｙレジスタ４０２Ｙ、
Ｄレジスタ４０２Ｄと、Ｘレジスタ４０２Ｘ、Ｙレジス
タ４０２Ｙ、Ｄレジスタ４０２Ｄに保存さｎている位ば
データまたは方向データとデータ信号２１４４ｖＣより
直接入力さｎる位置データまたは方向データとの減算処
理を行う減算器４０３Ｘ、４０３Ｙｓ”よび４０３Ｄと
、Ｄレジスタの出力を受けて円関数全発生する円関数発
生器４０４と、減算器（１０３Ｘ、ｊＯ３Ｙの出力と円
関数発生器４０４の出力とｔ受けて七Ｃらの乗算処理を
行う乗算器４０５Ｘ、４０５Ｙ、４０６Ｘ。 ４０６Ｙと乗算器４０５ＸＬ−よび４０６Ｘならびに乗
算器４０５ＹＪ、−よび４０６Ｙの出力を受けてそ２ｔ
らの加算”ｆｆＣは減算処理を行う加算器４０７Ｘ２よ
び減算器４０７Ｙとから構成ざｎている。 このリレーション赴結部２１４１は、％像点りストメモ
リ２１１からデータ信号２１４４１Ｃよって送らＧてく
る例えばｌ侍像点Ｍａの総特像点デークを受けると、制
御回路４０１０１からの指令１ｇ号４００１によってシ
フトレジスタ４０１ＦＣ，４不りレーションデータｒａ
ｔ、　ＭｊＮｒａｋ、　Ｍｋを格納丁ゐと共にＸレジス
タ４０２Ｘ、Ｙレジスタ４０２ＹおよびＤレジスタ４０
２Ｄに位置データＸａ、位社データＹａｙよび方向デー
タＤａ　を格納する。な２ＣＯとき特徴点デー１　Ｑａ
、　Ｃａ、　Ｘａ、　Ｙａ、　Ｄａはデータ信号２１４
１１＆−よびアドレス１ｇ号２１４１２によって特徴点
記憶部２１４２のバッファメモリ１８０１Ａにも格納さ
ｎる。 一万特像点種別Ｑａ　ｖ′ｉデータ＜＝＠４ｏｏｏｖｃ
ｘって制御回路４０１０に人力さｌｒＬ、１Ｉ７１Ｊ＠
１回路４０１０はこれによって特徴点であることを確認
してシフトレジスタ４０１に指令を与え−、シフトレジ
スタ４０１はこの指令を受けて第一番目の最近傍特徴点
の特徴点全骨Ｍｆをデータ１百号４ｏ１１によって制御
回路４０１０に送出する。制御回路４０１０はこＣに工
ってアドレス１ｇ号２４４６　ｆｒ：特徴点リストメモ
リ２１１に送出して該メモリ２１１に格納しである１次
最近傍特徴点Ｍｆの総置像点データのうち位置データＸ
ｌｆ、Ｙｆｖよび方向データＤＩをｌとみ出す。 ｆｌｔＨ４己メモリ２１１からデータｌＩ百号２１４４
によって読出さＣｍ位置データＸｆ、　Ｙｆ　：ｓよび
方向データＤｆＶｉ、πｇＢに減算器４０３に、−４０
３Ｙ２よび４０３ＤＫ人力ｇＡるので、減ｊＡ−にｍ　
４０３　Ｘ。 ４０３Ｙおよび４０３１）はこのとき制御回路４０１０
からの指令によってＸレジスタ４０２Ｘ、Ｙレジスタ４
０２ＹおよびＤレジスタ４０２Ｄから入力される特徴点
Ｍａ　の位置データＸａ、ｙａＢよび方向データＤａと
によってその差ΔＸａｆ、ΔＹａｆ、ΔＤａｆ全算出し
、減算５４０３Ｘυ工び４０３Ｙの出力は、そｎぞｎ乗
算器４０５Ｘ、４０６Ｘ＆−４び乗算器４０５Ｙ、４０
６Ｘに送らｎる。 −万Ｄレジスタ４０２Ｄからの方間データ１）ａは並行
して円関数発生器４０４に人力さ扛、円関数発生器４０
４に寂いてａｉ算さｎた円関数値Ｃ０５Ｄａおよび５ｉ
ｎＤ、Ｊ：データ信号４０４１２工び４０４２Ｋｆって
乗算器４０５　Ｘ、４０５　Ｙオ、Ｊ：び乗算器４０６
Ｘ、４０６Ｙに送出さＣる。 ４個の乗算器４０５Ｘ、４０５Ｙ、４０６Ｘおよび４０
６Ｙは上Ｍ己（７）　Ｊ：うに減算器４０３Ｘ、　４０
３Ｙ２よび円関数発生器４０４がらの出方全党け、そｎ
ぞＣΔＸａｆＣＯ８Ｄａ、ΔＹａｆＣ０ＳＤａｊΔＹＢ
ｆｓｉｎＤａ。 ２よびΔＸａｆｓｉｎＤａの演算を行って七Ｃらの出力
を加算器４０７Ｘおよび減算器４０７ＹＫ送出するので
、加算器４０７Ｘｈよび減算器４０７ＹはこｎＬ：）を
入力して ｘＢ１＝ΔＸ　ａｆ’ｃｏｓ　Ｄ　ａ十ΔＹａｆＳ１ｎ
ＤａＹａｆ＝ΔＹａ１ｃｏｓＤ；１−ΔＸａｆｓｉｎ　
Ｄ　ａの演算を行ってそｎらの結果を減算器４Ｏ３Ｄの
出力でろる方向データｄＢ１とこのとき７７トレジスタ
４０１から出力さｒるリレーションｒａｆト’にリレー
ション連結データとしてデータ１ｇ号２１４１１によっ
て特徴点ｄ己憶部２１４２のバッファメモリ１８０１Ａ
に送って格納する。 第一の最近値特徴点Ｍｆに関する上述のりレーンヨン連
結動作およびその格納動作を終了すると、制御回路４０
１０はシフトレジスフ４０１に指令１呂号４００２を送
出して第二の最近値特徴点の特徴点食号Ｍｇの送出全党
け、以下上述の動作を繰返してすべての最近＋ｙｊ特徴
点に対してリレーション連結動作とその格納動作を天性
する。 すべての最近値特徴点に対する上述のりレーション連結
動作とその格納動作が終了すると、リレーション連結部
２１４１は引続き特徴点りストメモＩＪ　２１１からフ
ァイル指紋の第−合口の特徴点の総特像点データを読出
し、前述のりレーション連結動作を行ってバッファメモ
’Ｊ　１８０１　Ｅに格λ０１−る。 特徴点記憶部２１４７は、上述のファイル指紋の第−金
目の特徴点のりレーンヨン連結データの格納動作の間に
、制御回路４Ｏ１０からの指令信号２１４９による指令
によってバッファメモリ１８０１ＡＫ格稍した探索指紋
の第−金目の特徴点の総遅結デークを作索符像点メモＩ
Ｊ　１８０２に移す。 リレーション連結部２１４１に２けるファイル）旨紋の
第一少目の特徴点ｆ（関するリン−ジョン４結動作が完
了してバッファメモ”ＪｌＢｏｌＢに格納し終るとこの
総迎結データは制御回路４０１０の指令によってファイ
ル特徴点メモリ１８０３に移さ店この間にファイル連結
動作が行ゎｎてそのデータはバッファメモリ１８ＱｌＡ
Ｋ格網さｎる。 探索指紋２よびファイル指紋の総連結データ全そｎぞれ
検素特徴点メモ！ｊ１８０２ｙよびファイル特徴点メモ
！Ｊ　１８０３に格納し終ると制＠１回路４Ｑ１０７）
−ら指令１ぎ号２１４工ｏが「対」検出部２１４３に送
らｎるので、「対」検出部２１４３Ｉｄ、　コ（７）　
４ｇ　Ｇ　１’ｇ　号２１４１０を受けて探素待依点メ
モリ１８０２およびファイル特徴点メモリ１４ｏ３にア
ドレス信号２１４３１を送ってこｎらに格納さ往ている
総浬結データを続出し１一対」恢出動作「対」検出部２
１４３による探索特徴点メモリ１８５０２およびファイ
ル特徴点メモリ１８５０３からの読出しが完了すると、
特徴点記憶部２１４２は制御回路４０１０の指令によっ
てバッファメモ！Ｊ１８０１Ａ　に格納されているファ
イル指紋の第二番目の特徴点の総連結データをファイル
特徴点メモ’）１８０３　に移すと共にバッファメモ１
Ｊ１８０１Ｂにファイル指紋の第三番目の％像点の総連
結データを格納する。 以下上述のりレーション連結動作とその格納動作および
総連結データの読出しとそれによる「対」検出動作を２
個のバッファメモ１Ｊ１８０１Ａおよび１８０１Ｂ　を
交互に使って繰返し行い、探索指紋の１個の傷像点に対
してファイル指紋のすべての％像点が検査されると、バ
ッファメモＩＪ１８０１Ａまだは１８０１Ｂの空いてい
る方を使って探索指紋の第二番目の特徴点に関するリレ
ーション連結動作とその探索特徴点メモリへの格納動作
を行う。 上述の動作を探索指紋およびファイル指紋のすべての特
徴点に対して行うことによって１個の探索指紋と１個の
ファイル指紋のｒ対」検出動作が完了する。 第２０図を参照すると、第１６図の［対」、検出部２１
４３は、探索特徴点メモ１Ｊ１８０２およびファイル特
徴点メモ！７１８０３　から比較判定すべき特徴点の総
連績データを入力して集密量１だはりレーションと位置
データおよび方向データとの減算処理を行う減算器７０
１Ｊ７０ＬＸ、７０１Ｙ、７０１Ｄと、これらの減算器
７０１Ｒ，７０１Ｘ、７０１Ｙ、７０１Ｄからの出力と
を入力してそれらの値を比較する比較器７０２Ｊ７０２
Ｘ、７０２Ｙ、７０２Ｄと、これらの比較器７０２Ｉｚ
　７０２Ｘ、７．０２Ｙ。 ７０２Ｄの出力を入力するアンド回路７０６と、このア
ンド回路７０６の出力を入力して計数し制御回路７００
の指令によってリセットされるカウンタ７０７と、探索
指紋およびファイル指紋のりレーションを入力して、そ
れらが最近傍特徴点が存在しないとき付与される特定の
コードであるか否かを判別するりレーションコード検出
部７０４と、このリレーションコード検出器の出力を入
力して計数し、制御回路７００によってリセットされる
カウンタ７０５と、カウンタ７０５の出力を入力するこ
とによって送出されるしきい値発生器７０３からの出力
とカウンタ７０７からの出力とを入力してそれらの仙を
比較判定する比較器７０８とを備えて構成されている。 上述のように搗゛成された「対」検出部２１４３は以下
のように動作する。すなわち、制御回路７００がリレー
ション連結部２１４１からの指令信号２１４１０を受け
ると、アドレス信号２１４３１を探索特徴点メモ！Ｊ１
８０２　およびファイル特徴点メモＩＪ１８５０３に送
出し、比較すべき探索指紋およびファイル指紋のそれぞ
れの特集密ｉ″（Ｃ、Ｃ）、位置デ・−タ（Ｘ、Ｘ；ａ
　ａ　ａａ Ｙ　、Ｙ　）、方向データ（Ｄ　、Ｄ　）をそａａ　ａ
ａ れぞれ減算器７０１Ｊ　７０１Ｘ、７０１Ｙ。 ７０１Ｄに入力しく　Ｍ　ａ　、　Ｍ　ａ　等の添字Ｓ
は探索指紋、添字Ｆはファイル指紋に関する特徴点番号
またはデータを示す）、減算器７０１Ｒ。 ７０１Ｘ、７０１Ｙ、７０１Ｄはそれらの差の絶対値１
ｃ、”−ｃ：＋　、ＩＸニーＸ：Ｉ　、ＩＹニーＹａｌ
　、ＩＤａ−Ｄａｌを算出してそのｆ直をそれぞれ比較
器７０２Ｒ，７０２Ｘ、７０２Ｙ。 ７０２Ｄに送出する。 比較器７０２Ｊ　７０２Ｘ、７０２Ｙ、７０２Ｄは、こ
れらの減ｑ−器７０１　Ｉｌｌ　、　７０１　Ｘ　。 ７０１Ｙ、７０１Ｄからの出力と、制御回路７ＯＯから
の指令信号７００３によってしきい値発生器７０３から
送出されるしきい値データ（Ｔ　ｃ　、　Ｔ　ｘ　、　
Ｔ　ｙ　、　Ｔ　Ｄ）を入力してそれぞれＩｃ５　ＣＦ
ｌ！Ｔｃ　、ＩＸ’　ＸＦｌ≦Ｔｘａａ　ａＢ ＩＹａ−ＹａＩ≦Ｔ　ｙ　＋　Ｉ　”　ａ　−Ｄａ　Ｉ
　’　”Ｄを比較判定し、その結果をアンド回路７０６
に出力し、アンド回路７０６は上記の比較器７゜２Ｊ７
０２Ｘ、７０２Ｙ、７０２Ｄがらの出力がすべてオンの
とき、その出力を制御回路７００に送出する。 制御回路７００はこのアンド回路７０６がらの出力を受
けると、指令信号７００１および７００２に送出してカ
ウンタ７０５および７０７をリセットすると共に、アド
レス信号２１４３１を送って探索特徴点メモＩＪ１８０
２およびファイル特徴点メモリ１８０３なら第１のりレ
ーション連結データ（ｒａ　ｆ’　Ｘａｆ　、ｙａｆ　
、ｄａｆおよびｒａｆ、Ｘａｆ、ｙａｆ、ｄａｆ）を読
出し、上記の特徴点データの場合と同様に減算器７０１
Ｒ，７０１Ｘ、７０１Ｙ、７０１Ｄおよび比較７０２Ｂ
、７０２Ｘ、７０２Ｙ、７０２Ｄによってｌｒ、ｆ−ｒ
ａｆｌ！Ｔｒ　、　１ｘａｆ−ｘａｆｌ、６Ｔｘ。 １ｙａｆ−ｙａｆ１６Ｔｙ、Ｉｄ、、ｆ−ｄａｆｌ’Ｉ
’ｄ（Ｔｒ　、Ｔｘ、Ｔｙ、Ｔｄはそれぞれリレーショ
ン。 位置データＸ１位ｆＩ！ｔデータｙ、方向データｄに関
するしきい値） 全算出しその結果をアンド回路７０６に送出し、アント
回路７０６は比較器７０２Ｊ７０２Ｘ。 ７０２Ｙ、７０２Ｄからの出力がすべてオンのときその
出力を制御回路７００に送出する。制御回路７００はこ
の出力を受けて指令信号７゜０２を送出してカウンタ７
０７の内容を更新する。 上記の動作に先立って、リレーションｒａｆ’ｒａｆが
読出されたとき、これらはりレージロンコード検出器７
０４に入力されるので、リレーションコート検出ｉ　７
０４は、リレーションｒ−ａｆ、ｒａｆ　のコードを判
定してそれらのコードの少くとも１方が最近倣特徴点が
存在しないときに付与される特定のコードである場合は
指令信号７０４０を制御回路７００に出力すると共にカ
ウンタ７０５を更新し、制御回路７００は先に説明し、
だアンド回路７０６からの出力の有無に無関係に指令信
号７００２を出力しない。 リレーション連結データ（ｒａｆ”’−ｄａｆ、ｒａｆ
〜ｄａρに関する上記の動作が終了すると、制御回路７
００はアドレス信号２１４３１を探索特徴点メモ’）１
８０２　およびファイル特徴点１８０３に送って第二の
りレーション連結データヲ読出し、これらについて前述
と同一の比較判定動作を行い、以下継続して探索指紋お
よびファイル指紋の特徴点のすべてのりレーション連結
データの比較判定ルυ作を行う。 リレーション連結データに関する上記の比較判定動作を
終了すると、制御回路７００はカウンタ７０５に指令を
与えてその内容をしきい値発生器７０３に出力させ、し
きい値発生器７０３はこのカウンタ７０５からの出力を
受けて不在最近値特徴点の数に対応するしきい値を比較
器７０８に出力する。 比較器７０８はこのしきい値発生器７０３からの出力と
、制御回路７００の指令によって出力されるカウンタ７
０７からの出力とを受けて比較し、カウンタ７０７の値
がしきい値以上であるときは指令信号７０８０を制御回
路７００に送出し、制御回路７００はこの指令信号７０
８０を受けて内部保持している探索％像点番号Ｍ　υよ
びファイル特徴点番号Ｍ　を第４図のａ　ａ 対修捕リストメモリ２１５に送シ、アドレス信号２１４
５によって指定される番地に格納する。 上記の動作を探索指紋のずべての特徴点とファイル指紋
のすべての特徴点のすべての組合せなお上記の実施例で
は、特徴点記憶部２１４２がリレーション連結部２１４
１および「対」検出部２１４３に対して独立な装置であ
る場合であるが、こねは必ずしも独立である必吸はなく
、リレーション連結部２１４１または「対」検出部２１
４３の構成要素の一部として組込捷れていてもよい。 （５）対検査動作の変形例 第２１図を＃照すると、第４図の対検査回路の変形側２
１４′は複合リレーション連結部２１４１′探索特徴点
記憶部１８０２ンアイル特徴点記憶部１８０３および複
合対検出部２１４３’から構成でれている。 複合リレーション連結部２１４１’は、第４図の特徴点
リストメモリ２１１に格納された指紋データの各特徴点
の基本リレーションデータを、その中に含まれる１次最
近傍特徴点の特徴点番号をその特徴点に関する局／１５
Ｔ座標の位置データおよび方向データに変換した１次リ
レーションデータに変換し、更に１次最近房ＩＰｆ徽点
に関するａ％徴像点デーから２次最近傍特徴点に関する
２次リレーションデータを構成して各特徴点毎に％像点
データおよび１次リレーションデータならひに２次リレ
ーションデータ（これらを総称して総連結データという
）を探索特命点記憶部１８０２またはファイル％像点記
憶部１８Ｏ３へ送って格納するように結合きれている。 探紫ｌＦ″ｆ像点記憶部１８ｏ２またはファイル特徴点
記憶部１８ｏ３に格納される総連結データは、第２２図
に示すように名４ｆ徴点について特徴点データと１次リ
レーションデータ（リレーションｒｉ」２位１１ソテー
タｘｉｊ　−ｙｉｊ　＋方向データｄｉｊ）と２次リレ
ーションデータ（２次リレ−シｖンｒｊｋ、位置データ
ｘｉｋ−ｙｊｋ、方向データｄｉｋ）とからなっている
。 複合「対」検出部２１４３’は探索特徴点記憶部１８ｏ
２およびファイル特徴点記憶部１８０３からそれぞれ１
個の総１連結データを取出して「対」となるべき特徴点
を検出する役割を荷メモリ２１５に送られて整糸１・Ｊ
され、？、。 特蕾点リストメモリ２１１に格納されるデータは、１倫
：の特徴点に関してその特徴点細別（Ｑｉ　）、集密度
（Ｃｉ）、位置データ（Ｘｉ、Ｙｊ）、方向データ（Ｄ
ｉ）および１火報近傍４．）像点のすべての基本リレー
ションデータ（”Ｊ　１ＭＪ　）ｔ　１和とした総勢像
点データの１指紋文の集りであり、とれらはデータ信号
２１４６によって複合リレーション連結部２．１４１’
にｊ「１次出力される。 複合リレーション連結部２１４１’は、アドレス信号２
１４４によって％徴点りストメモリ２１１から基本リレ
ーションデータを読出すと、この基本リレーションデー
タ中に含まれる１次最近傍特徴点の特徴点番号（Ｍｊ　
）をその特徴点に関する局所座標による位置データ（ｘ
ｉｊ、ｙｉｊ）および方向データ（ｄｉｊ）に変換して
リレーション（ｒｉＤと共に１次リレーションデータを
構成し、史にアドレス信号２１４４によって特徴点リス
トメモリ２１１から１次最近傍特徴点（Ｍ」）の総％像
点データを読出して２次最近傍特徴点の１次最近傍特徴
点の局所座標に関する位置データ（ｘｉｋ、ｙｉｋ）お
よび方向性データ（ｄｉｋ）と２次リレーション（ｒｉ
ｋ）を生成して２次リレーションデータを構成して、こ
れらを特徴点データと共に総連結データとしてデータ信
号２１４１１によって探索特徴記憶部１８ｏ２に送出し
、探索特徴記憶部１８０２は、このデータ信号２１４１
１を受けてアドレス信号２１４２によって第２２図に示
す形式で指定された番地に格納する。 上記の動作を繰返して１個の探索指紋に関するすべての
特徴点の総連結データの格納が終了すると、複合リレー
ション連結部２１４１’はファイル指紋の指紋データを
順次読出し探索指紋の場合と同様にリレーション連結動
作を行って総連結データをデータ信号２１４１１によっ
てファイル特徴点記憶部１８０３に出力する。 ファイル特徴点記憶部１８０３はアドレス信号２１４１
３の指定に従ってこの総連結データを指定の番地に格納
し、この動作を繰返してファイル指紋のすべての特徴点
の総連結データを格納する。 探索特徴点記憶部１８Ｏ２およびファイル特徴点記憶部
１８０３に格納された指紋データは、その詳細を後述す
る複合Ｆ対」検出部２１４３’においてそれらの特徴点
のすべての組合せについて「対」関係の有無が検査され
、探索指紋の特徴点の総連結データとファイル指紋の特
徴点の総連結データとが所定のしきい領内で一致す１５
１に送られ、アドレス信号２１４８に指定された番地に
格納される。 第２１Ａ図は、基準となる特徴点Ｍａに対する第１火報
近傍特徴点Ｍｆ、へｖｇ　、Ｍｌｉ　、λ）ｋと、前記
第１火報近傍４＋徴点のぞｉｔだれに対する第２火遊近
傍特徴点の１ゲ１係を示してし・る。例えは、Ｎａｆ：
原点とする座標糸における第１象限の最近傍特徴点はＭ
ｆでありＭｆを原点とする局所座４ＲＡ系におけるふ１
象限の最近傍７ｉ￥部（点はＭｎであり、この特徴点Ｍ
ｕは、特徴点１ｖｌａに対する第２火遊近傍特徴点の１
つである。 一般の第１次リレーゾヨンデータによるｈ（ｉ合に対し
て、さらに々゛１２次リレーすョンテータデーいて照合
するととＶｉ、４＠＃ｌＩ性の筒い工１α合を行なう上
で極めて府力な方法となる。なぜ〃ら基準座標又は局所
座標の座標の中心及び方向は設定作業上多少の誤差、が
生ずるのは赴けることはできない。との場合、例えば第
２１〕ν図に示すように特徴点Ｍａに関する局所座標Ｘ
ａ、Ｙａ　が局ｒ９ｒ座標Ｘａ’、Ｙａ’に設定される
と、第１次最近傍特像点Ｍｆ、Ｍｇ、Ｍｈ、Ｍｋのうち
特徴点Ｍｋは、座標軸Ｘａ’　、Ｙａ’に対しては、第
１次近傍特徴点Ｍｆ　と同一象限となるため第１火報近
傍特徴点とはならず代りに特徴点Ｍｕが第１火報近傍特
徴点となってしまうという整置が生じる。こ−の点上記
第２火報近傍特徴点を加えて、第１次リレーションデー
タ間及び第１次リレーションデータと第２次リレーショ
ンデータ相互間を比較すれは上記整置を除くことが可能
となる。 前記複合リレーション回路部２１４１’の構成は第１９
図に示した前記リレーション連結部２１４１の構成と同
一である。 この動作は次のようにして行なわれる。 第１９図を参照すると、複合リレーション連結部２１４
１’は特徴点リストメモリ２１１からデータ信号２１４
４によって送られてくる例えは特徴点Ｍａの約物像点デ
ータを受けると、制御回路４０１０からの指令信号４０
０１によってシフトレジスタ４０１に基本リレーション
データｒａｆ　、Ｍｆ−ｒａｋ　、Ｍｋを格納すると共
にＸレジスタ４０２Ｘ、Ｙレジスフ４０２ＹおよびＤレ
ジスタ４０２Ｄに位置データＸａ、位置データＹａおよ
び方向データＤａを格納する。なおこのとき特徴点デー
タＱａ　、Ｃａ　、Ｘａ　、Ｙａ　、Ｄａはデータ信号
２１４１１およびアドレス信号２１４１２によって探索
特徴点記憶部８０２またはファイル特徴点記憶部１８０
３に書込まれる。 （第２２図参照）。 一方、特徴点細別Ｑａはデータ信号４０００によって制
御回路４０１０に入力され、制御回路４０１０はこれに
よって特徴点であることを確認してシフトレジスタ４０
１に指令を与え、シフトレジスタ４０１はこの指令を受
けて第一番目の１次最近傍特徴点の特徴点番号Ｍｆ′ｆ
ｔデータ信号４０１１によって制御回路４０１０に送出
する。制御回路４０１０はこれによってアドレス信号２
１４６を特徴点リストメモリ２１１に送出して特徴点リ
ストメモリ２１１に格納しである１次最近傍％徴点Ｍｆ
の約物像点データを読み出し、このうちの基本リレーシ
ョンデークをシフトレジスタ４０１に格納する。 一方、特徴点リストメモリ２１１からのデータ信号２１
４４によって読出された約物像点データのうち位置デー
タＸｆ　、Ｙｆおよび方向データＤｆは、たｙちに減算
器４０３Ｘ、４０３Ｙおよび４０３Ｄに入力されるので
、減算器４０３Ｘ、４０３Ｙおよび４０３Ｄはこのとき
制御回路４０１０からの指令によってＸレジスタ４０２
Ｘ、Ｙレジスタ４０２ＹおよびＤレジスタ４０２Ｄから
入力される特徴点Ｍａの位置データＸａ、Ｙａおよび方
向データＤａとによってその差ΔＸａｆ、ΔＹａｆ、Δ
Ｄａｆを算出し、減算器４０３Ｘおよび４０３Ｙの出力
はそれぞれ乗算器４０５Ｘ、４０６Ｙおよび乗算器４０
５Ｙ、４０６Ｙに送られ、減η器４０３Ｄの出力はデー
タ信号２１４６によって探索特徴点記憶部１８０２また
はファイル特徴点記憶部１８０３へ送られる。 一方ｓ　Ｄレジスタ４０２Ｄからの方向データｎ　−ｓ
　＋、−＋うＬ仁ｌイ田阻１碧ＩカルシテＡ凸Ｊ　Ｉｙ
ス寸藏者り円関数発生器４０４において計算されだ円関
数値ｃｏｓＤａおよび５ｉｎＤａはデータ信号４０４１
および４０４２によって乗算器４０５Ｘ。 ４０５Ｙおよび乗算器４０６Ｘ、４０６Ｙに送出される
。 ４個の乗ｇ器４０５Ｘ、４０５Ｙ、４０６Ｘおよび４０
６Ｙは上記のように減算器４０３Ｘ。 ４０３ＹおよびＨ関数発生器４０４からの出力を受け、
それぞれΔＸａｆ　ｃｏｓＤａ、ΔＹａｆｃｏｓＤａ、
ΔＹａ　ｆ　ｓ　ｊｎＤａ　、およびΔＸａｆＳｌｎＤ
ａの演語−を行ってそれらの出力を加★器４０７Ｘおよ
び減算器４０７Ｙに送出するので、加詣器４０７Ｘおよ
び減算器４０７Ｙｉはこれらを入力して ｘａｆ＝ΔＸａｆ　ｅｏｓＤａ＋ΔＹａｆｓｉｎＤａｙ
ａｆ＝ΔＹａｆ　ｃｏｓＤａ−ΔＸａ　ｆ　ｓ　１ｎＤ
ａの演算を行ってそれらの結果をデータ信号２１４１１
によって探索特徴点記憶部１８０２４たはファイル特徴
点記憶部１８Ｏ３へ送出し、探索％微意記憶部１８０２
’！、たはファイル特徴点記憶部１８０３はこれらのデ
ータと減算器４Ｏ３Ｄからの出力である方向データｄａ
ｆおよびシフトレジスタ４０１から送らｔてくるリレー
ションｒａｆ　とを全近傍特徴点Ｍｆに関する１次リレ
ーションデータとしてアドレス２１４１２または２１４
１９によって指定される番地に格納する。（第２２図参
照） 蕗−の１次最近傍特徴点Ｍｆに関する上述のりレーショ
ン連結動作を終了すると、制御回路４０１０はシフトレ
ジスタ４０１に指令信号４００２を送出して第二の全近
傍特徴点の特徴点番号Ｍ　ｇの送出を受け、以下上述の
動作を繰返してすべての１火報近傍％徴点に対して実行
する。 １次ル゛近傍特徴点に対応する上述のりレーション連結
動作を終了すると、複合リレーション連結部２１４１’
は、既にシフトレジスタ４０１に格納しである第１の２
次最近傍特徴点の特徴点番号Ｍｆｌによってその位置デ
ータＸβ、ＹＡおよび方向データＤ２を耽出し、既述の
手順と全く同一の手順で２次リレーションデータを構成
する位置データｒａｉ、、ｙａβと方向データｄ」を演
算して送出すると共に、シフトレジスタ４Ｏ１からリレ
ーションｒｆ１１．を送出して２次リレーション演算器
（図示せず）に入力し、別途１次すレーシミンレジスタ
（図示せず）に格納しである１次すレーションｒａｆと
によって所定の演算方法による演算を行って（演算方法
は通常の加減算の組合せであるので詳細説明は省略する
）その結果を出力し特徴点ＭＡに関する２次リレーショ
ンとして探索特徴点記憶部１８Ｏ２またはファイル特徴
点記憶部１８０３に格納する。（第２２図参照） 以下この動作をすべての２次最近傍特徴点について行う
ことにより特徴点Ｍａに関するリレーション連結動作を
完了する。 以上の動作を１個の指紋のすべての特徴点について完了
すると、制御回路４０１Ｏは指令信号２１４５を複合「
対コ検用部２１４３’に出力してすべての動作が終了し
たことを知らせる。 第２３図を参照すると、複合対検出部２１４３′の構成
は、第２０図に示した対検出部２１４３の構成とを１と
んど同一である。 相違点は制御回路７００からアドレス信号２１４３の他
にアドレス指定を変更したアドレス信号７４を出力する
とともにアドレス信号２１４８の他にデータ信号２１４
５を出力することにある。以下この回路の動作を詳述す
る。 制御回路７００が複合リレーション連結部２１４１′か
らの指令信号２１４１０を受けると、アドレス信号２１
４３１および２１４３２を探索特徴点記憶部１８０２お
よびファイル特徴点記憶部１８０３に送出し、比較すべ
き探索指紋およびファイル指紋のそれぞれの％像点例え
は方向データ（Ｄ　、Ｄ　）をそれぞれ減算器７ａ　ａ ０１Ｊ　７０１Ｘ、７０１Ｙ’、７０１Ｄに入力し減算
器７０１Ｒ，７０１Ｘ、７０１Ｙ、７０１　’ｎ＋、＋
ンシＪｑｌ’−ｉ） 差の絶対値１ｃａ−Ｃａｌ　、ＩＸａ−Ｘａｌ　、ＩＹ
ａ−Ｙ　１．ＩＤ　−Ｄ　Ｉ ａ　ａ　ａ を算出してその値をそれぞれ比較器７０２Ｊ７０２Ｘ、
７０２Ｙ、７０２Ｄに送出する。 比較器７０２Ｊ７０２Ｘ、７０２Ｙ、７０２Ｄは、これ
らの減算器７０１　Ｒ、７０１Ｘ、　。 ７０１Ｙ、７０１Ｄからの出力と、制御回路７００から
の指令信号７００３によってしきい値発生器７０３から
送出されるしきい値データσＣ７Ｔχ１　ＴＹ　、ＴＤ
　）を入力してそれぞれＩＹ−Ｙｌ≦ＴＹ、Ｉｆ）−Ｄ
　Ｉ≦ＴＤａａ　ａａ を比較判定し、その結果をアンド回路７０６に出力し、
アンド回路７０６は上記の比＆器７０２■も、７０２Ｘ
、７．０２Ｙ、７０２Ｄからの出力がすべてオンのとき
、その出力を制御回路７００に送出する１、 制御回路７００はこのアンド回路７０６からの出力を受
けると、指令信号７００１および７００２に送出してカ
フ／り７０５および７０７をリセットすると共に、アド
レス信号２１４３１および２１４３２を変更して探索特
徴点記憶部１８Ｏ２およびファイル％像点記憶部１８０
３から第１の１次リレーションデータ（ｒａｆ、Ｘａｆ
’Ｖｃｌ　およびｒａｆ　、Ｘａｆ　、ｙａｆ　、ｄａ
ｆ）を読ａｆ’　ａｆ’ 出し、上記の特徴点データの場合と同様に減算器７０１
Ｊ７０１Ｘ、７０１Ｙ、７０１Ｄおよび比Ｍａ７０２几
、７０２Ｘ、７０２Ｙ、７０２Ｄによりて ｌｒ　−ｒ　１＝Ｔｒ、、ｌｘａ、−ｘａｆｌ≦Ｔｘ。 ａｆ　ａｆ １ｙａｆ−ｙａｆ　”Ｔｙ、Ｉｄａｆ　’ａｆ　”Ｔｄ
（Ｔｒ、Ｔｘ、Ｔｙ、Ｔｄはそれぞれリレーシ、７、位
置データＸ２位置データｙ、方向データｄに関するしき
い値） を算出しその結果をアンド回路７０６に送出し、アンド
回路７０６は比較器７０２Ｊ７０２Ｘ。 ７０２Ｙ、７０２Ｄからの出力がすべてオンのときその
出力を制御回路７００に送出する。制御回路７００はこ
の出力を受けて指令信号７゜０２を送出してカウンタ７
０７の内容＆ＫＮ−ｆ２）。 上記の動作に先立って、リレーションｒａｆ’ｒａｆが
前出されたとき、これらはりレーションコード槓出器７
０４に入力されるので、リレーションコード検出器７０
４は、リレーションｒ−□ｆ、ｒａｆ　のコードを判定
してそれらのコードの少くとも１方が最近傍特命点が存
在しないと１！に付与される特定のコードでちる場合は
指令信号７０４Ｏを制御回路７００に出力すると共にカ
ウンタ７０５を更新し、制御回路７００は先に説明した
アンド回路７０６からの出力の有無に無関係に指令信号
７００２を出力しない。 ？ｌｚｘの１次すレーションｆ−タ”ａｆ−ｄａｆ’ｒ
ａｆ〜ｄ８ｆ）に関する上記の動作が終了すると、制御
回路７００はアドレス信愕２１４３１およびアドレス指
定を変更したアドレス信号２１４３２を探索特徴点記憶
部１８０２およびファイル勃像点記憶部１８０３に送ジ
、探索特徴点記憶部１８０２からは再び第１の１次リレ
ーションデータ（ｒａｆ”ａｆ、ｙａｆ、ｄａｆ）を訪
、出すと共に、ファイル特徴点記憶部１８０３からは第
２の１次リレーションデータ（ｒａ　ｇ　ｒ　Ｘ２　ｇ
　）　ｙａ　ｇ　ｒ　ｄａ　ｇ　）を読出し、これらに
ついて前述と同一の比較判定動作を行い、以下継続して
探索指紋の特徴点の１次および２次リレーションデータ
とファイル指紋の特徴点の１次および２次リレーション
データの組合せについて前述と同一の比較判定動作を行
う。 探索およびファイル両指紋の特徴点に関する１次および
２次リレーションデータの組合せの比較判定動作は、１
次および２次リレーションデータのすべての組合せにつ
いて行ってもよいが、照合の効率を高めるだめ１次リレ
ーションデータ相互間の組合せと１次リレーションデー
タと２次リレーションデータとの間の組合せについて行
うようにしてもよい。 １次リレーションデータおよび２次リレーションデータ
間の所定の組合せのすべてについて上記の比較判定動作
を終了すると、制御回路７０Ｏはカウンタ７０５に指令
を与えてその内容をしきい値発生器７０３に出力させ、
しきい値発生器７０３はこのカウンタ７０５からの出力
を受けて不在最近傍特徴点の数に対応するしきい値を比
較器７０８に出力する。 比較器７０８はとのしきい値発生器７０３からの出力と
、制御回路７００の指令によって出力されるカウンタ７
０７からの出力とをうけて比較しカウンタ７０７の値が
しきい値以上であると指令信号７０８０を制御回路７０
０に送出し、制御回路７００はこの指令信号７０８０を
受けて内部に保持している探索指紋とファイル指紋の特
徴点番号の組合せ（Ｍ　、Ｍ　）を「対」ａ　ａ としてデータイ６号２１４５およびアドレス信号２１４
８によって「対」侯補リストメモリ２１５に送って記憶
させる。 上記の動作を探索指紋のすべての％微意とファイル指紋
のすべての特徴点のすべての組合せについて行うことに
よって探索指紋とファイル指紋との「対」となる特徴点
をしらべて対候袖メモリ２１５の内容が完成する。 対候補リストメモリ 上述の対検査動作の結果として作成される対御補リスト
メモリについて一実施例を以下に説明する。 第２４図を参照すると、全部で６４個の異なるロウアド
レスと１６個の異なるコラムアドレスから成っている。 任意のロウアドレスｉおよびコラムアドレスｊで指示さ
れる各エントリは、ペア候補指示フィールド■ｉｊと近
似度重み格納フィールドＷｉｊの二つのフィールドに分
けられ、これらの各フィールドには次のような形でデー
タが格納されている。 まず、各ロウアドレスはそれと同じ番号をもつ探索指紋
特徴点に対応している。すなわち、ｉ番目の探索指紋特
徴点に対し、最も高い局所的近似度をもつファイル指紋
の特徴点が、このｉ番目の探索指紋特徴点に対する最初
の対候補として、この対ペダ候補の番号（つまシ候補と
ｒ候補のもつ近似度の強さが重みとしてフィールドＷｊ
Ｑに格納されている。つぎに、同じ１番目の探索指紋特
徴点に対し次に強い局所的近似度をもつファイル指紋特
徴点の番号が２番目の対候補として、フィールドＭｉｊ
に格納され、それとともにその近似度の強さが重みとし
てＷｉｊに格納されている。このようにしてｉ番目の探
索指紋特徴点に対するファイル指紋特徴点の対候補が局
所的近似度の強さの順番に次々のコア２ムアドレスに格
納されている。局所的近似度の強さがある一定のスレー
シホールド値よｐも低くなると、このロウアドレスｉに
対する対候補リストはそこで打切られ、処理の打切りを
示すために重みフィールドに特定の終了マークが格納さ
れる。 （６）座椋瞥合址の生成および整合動作第２５図を参照
すると、前記座標整合回路２１７の一回路例は、差平面
表示メモＩＪ　６０１（Ｉ）ＩＦ）、レジスタファイル
６０２（ＲＦＩ）および６０３（ＲＦ２）、加算器６０
４，６０５および６０６．１加算器６０７および６０８
、レジスタ６０ｇ　（ＤＸ）、６１０　（ＤＹ）、６１
１（ＲＫＯ）、６１２（Ｒ，Ｋｌ）、６１３（Ｒ，に、
２）、６１４（八４Ｄ１Ｆ）、６１５（ＸＭ）および６
１６（ｙＭ）、入力選択器６１７゜６１８．６１９．６
２０および６２１、比較器６２２およびアンドゲート６
２３を含んでいへでて、本英施例の動作は、上述の特徴
点リストメモリ２１１の内容、および対ｆ補すストメモ
リ２１５の内容を用い、探索指紋の座標系をγΔθだけ
回転し、Ｘ座標をΔＸＴ、またはＸ座標をΔＹＴ　だけ
それぞれ平行移動したときに、探索指紋の特徴点とファ
イル指紋の特徴点とが最もよく整合がとれるような７・
Δθ、ΔＸＴ、およびΔＹＴ　の値を見出すことを目的
としている。但しγは正まノこは負の整数、ま／こΔθ
はめるべきオ１一度に応じて予め特定の値に設定烙れる
ものとする。（例えばΔθ＝５．６°） このような目的の動作ｔ６うために、制御記憶メモリ（
図示せず）にはマイクロプログラム（マイクロコード）
が格納されており、制御記憶２１８の制御部（図示せず
）は仁のマイクロプログ２ムをその特定の開始番地から
つぎつぎに読み出し、これを実行することにより以下に
述べる処理を進行させる。 最初にこの処理の荒節について説明する。 まず、前記制御部は、特徴点リストメモリ２１１と対候
補リストメモリ２１５の中に格納きれている上述の情報
を読み出し、これを処理することにより、座標整合回路
２１７に含まれている差平面表示メモ！Ｊ６０１（ＤＩ
Ｆ）に差平面重みマツプを生成する。 この差平面重みマツプとは次のようなものである。 探索指紋％像点に対し、その座標系をある角度γΔθだ
け回転し、回転した後の特定のｉ番目の探索指紋％像点
のＸ座標およびＸ座標の値をそれぞれＸＳ１およびＹＳ
ｉとする。つぎに。 この探索指紋特徴点に対する特定のｊ番目の対候補であ
るファイル指紋％像点（このファイル指紋特徴点を指示
する番号は対候補リストメモリ２１５の対候補指示フィ
ールドＭｉｊに登録されている）のＸ座標およびＸ座標
の値をそれぞれＸｍ１ｊおよびＹｍｉｊとすると、 というΔχ軸座標（横軸座標）およびΔγ軸軸座標差画
面表示メモリ６０．１１）ＩＦ）のメモリアドレスに、
対候補リストメモリ２１５の重み格納フィールドＷｉｊ
に登録されている重みを加算する。これを該メモリ２１
５中のすべての有効なｉ、ｊについて積算したものが差
平面重みマツプでおる。 こうして生成されだ差平面重みマツプは、量子化された
任意のΔＸおよびΔＹで指定される、差平面上の位置に
相当するメモ’）　６０１　（ｆ）ＩＦ）のメモリアド
レスに、その位置によって定める上述のようにして積算
された重みが格納された形で重みパタンを形成している
。なお、このマツプの重みバタンは、上述の、探索指紋
座標系の回転角γΔθによって異なることになる。 さて、次に、こうして生成された重みマツプ上で、積算
された１みが最大になっているΔＸ座標値ＸＭおよびΔ
ＹＸ座標値ＹＭを、このマツプの全肉をサーチすること
によって見出す。 但しこのサーチを行なうに箔って後に詳述するように、
サーチすべきＸＭおよびＹＭの位置にある重み、および
その前後の隣接する位置にある重みにそれぞれ特定の荷
重係数を括１け、それらを合計してできる荷重重みが最
大になるような形の荷重プ゛−チを行なう。こうして狗
重重みが最大になるΔＸ座標およびΔＹＸ座標値ＸＭお
よびＹＭが見出されると、そのＸＭおよびＹＭの値と、
そのときめられた最大荷重重みＭＤＩＦの値とをそれぞ
れ記録しておく。 つぎに、探索指紋座標系の回転角γΔθのγの値を前よ
シも少し変化してから、前と同様にして、差平面重みマ
ツプを住成し、この差平面重みマツプから上述のように
して荷重重みが最大になるΔＸ、ΔＹ座標の値Ｘ　Ｍお
よびＹＭ　とそのときの最大荷重重みＭＤＩＦとをめ、
今回求めたこの最大荷重重みＭ　Ｄ　Ｉ　Ｆと、　＝ｉ
Ｊ回から残されている最大荷重重みＭＩＪ　ｉ　ｌ”と
を比較し前よりも大きいか否かを判定する。もし前より
も大きい場合には、Ｘ、、ＹＭおよびＭＤＩＦの値を今
回求めたそれぞれの値で更新する。 このような操作を綜シ返すことで、探索指紋の座標系を
、予めきめた細かさΔθを単位として、予め定めた角度
範囲内で振り廻すことにより、上述の最大荷重重み１〜
ｉＤ］■ｉ″が最大になる角度γΔθの値とそのときの
ＸＭおよびＮＭをめるとこれが前述のめるべき座標整合
量γΔθ。 ΔＸＴおよびΔＹＴになるのである。 一一 （以下余′１３） 一二、・′ さてつぎに、これを各回路の動作と関連づけて詳述する
。 最初に上述の差平面重みマツプ全生成するための重みマ
ツプ生成処理について述べる。 第４図の制御記憶２１８の制御部は、メモリに格納され
たマイクロプログラムの制御により。 特徴点りストメモＩＪ　２１　］の特定のｉ番目の探索
指紋特徴点のＸ、ＹおよびＤのデータ全座標変換回路２
１２全介して読み出し、これ全制御記憶２１８の制御の
中に含まれるレジスタ（図示せず）にそれぞれＸａｉ、
ＹｓｉおよびＤ８ｉとして格納する。 この座標変換回路２１２は第１１図に示すように変換パ
ラメータΔＸＡ、ΔＹＡおよびΔθえ全格納するための
それぞれのパラメータレジスタ１１１０（ΔＸＡ）、１
１１１（ΔＹＡ）および１１１２（ΔθＡ）をもち、こ
れらのレジスタには、この重みマツプ生成処理が開始さ
れる前に制御記憶２１８の制御部によりそれぞれ。 ΔＸＡ＝０１ΔＹＡ＝０およびΔθえ＝γΔθ　の値が
すでに格納されている。 この座標変換回路２１２の機能は、メモリ２１１から読
み出したＸ、ＹおよびＤ′の値を、座標原点をノ（、Δ
ＹＡの位置にうつし、かつ各座標軸をΔへだけ反時計方
向に回転したときに生ずる新らしい座標系で表示した値
Ｘ′、　Ｙ’およびＤ′に変換する回路である。すなわ
ちＸ、Ｙ、Ｄよシ、ｘ’＝（ｘ−ΔＸＡ）ｃｏｓΔ６．
＋（Ｙ−ΔＹＡ）ｓｉｎΔθ。 Ｙ’＝（Ｙ−ΔＹＡ）ｃｏｓΔθ、−（Ｘ−ΔＸＡ）ｓ
ｉｎΔθ、　、（２）Ｄ’　＝Ｄ−Δθ□ で表わされる。現在の例ではこの回路２１２は座標系を
単にΔθ□＝γΔθ回転させるだけの作腫する。 さて、つぎに制御記憶２１８の制御部は、対候補リスト
メモリ２１５の特定のロウアドレスｉおよび特定のコツ
アイル指紋の特徴点のＸ、ＹおよびＤの値を、特徴点リ
ストメモリ２１１から今度は座標変換回路２１２を通さ
ずに直接読み出す。この値をそれぞれＸｍ１ｊ、Ｙｍｉ
ｊおよび］）ｍｉｊ　で表わすことにする。 次に制御記憶２１８の制御部にシーケンス制御回路２１
０の演鈎回路を用いて、前述のＸｓｉ。 Ｙ８ｉ　および］）ｓｉ　と今回読、み出した）（ｍｉ
ｊ。 Ｙｎｌｉｊ　およびＤｍｉｊ　とから、ΔＸ＝ＸｌＴｌ
　ｉ　ｊ　−Ｘ　ｓ　ｉΔＹ＝Ｙｍ　ｉ　ｊ　−Ｘ　ｓ
　ｉ Δｐ　＝ｐｍｉ　ｊ　−１）　ｓ　ｉ なるΔＸ、ΔＹおよびΔＤｉｅ算出する。次にこうして
められたΔＸ、ΔＹおよびΔＤのそれぞれの絶対値を、
予め定められている特定のスレシュホールド値Ｔｘ、Ｔ
ｙおよびＴｄ（比較的大きな値、例えばＴｄ＝４５°）
と比較し、これらの丁べてか、それぞれのスレシュホー
ルド値よりも小さいときにかぎり、対候袖リストメモリ
２１５のロウアドレスｌおよびコラムアドレスｊの重み
格納フィールドＷｉｊ’ｚ読み出し、これ全回路２１７
の差平面表示メモリ６０１（ＤＩＦ）の、前記ΔＸおよ
び、ΔＹで指定されるメモリアドレスの現在の内容に加
算する。 これを行なうためには、制御記憶２１８の制御部は、第
２５図に示す座標整合回路２１７のライン６１γＯ（Δ
Ｘ）ＶＣΔＸの値を、またライ７６１８０（ΔＹ）にΔ
Ｙの信金供給し、かつライン６１８１　（ＣＴ月ビ１”
にすることにより、入力選択器６１７．および６１８が
それぞれライン６１７０および６１８（ｌ介して供給さ
れたΔＸおよびΔＹの値全選択するようにし、これを差
平面表示メモＩＪ６０１（ＤＩＦ）のそれぞれロウアド
レスおよびコラムアドレスとして（Ｊｔ給する。 この結果、メモ！Ｊ６ｏ１（ＤＩｐ）の差平面座標位鵬
ΔＸおよびΔＹに相当するメモリアドレスの現在の内容
がライン６０１ｏを介してｄ〔み出される。これ全加算
器６０４の一方の入力とじて供給し、もう一方の入力と
して、ライン６０４０を介して前記重み格納フィールド
ｗｉｊから読み出されたｆｉｇを供給することにより両
者の和合作り、この和を再びΔＸおよびΔＹで指定され
るもとのメモリアドレスに格納する。これにより、メモ
リ６０１（ＤＩＦ）が表示する差平面にＷｉｊの内容を
積算する重み積算処理全容易に行なうことができる。 さて、これを用いて前述の差平面重みマツプを生成する
には、１ず最初に差平面表示メモリ００１（ＤＩＦ）の
内容をすべて０に初期値化し。 また、前記ｉおよびｊの値をそれぞれ最初に０に初期値
化する。但しこのｉおよびｊの値は制御記憶内のＦｆｆ
ｆＪ御部内に設けられたパラメータレジスタ（図示せず
）に格納されている。こうして該制御部はｓ　ｉ””　
ｊ＝０から上述の重み柁努−処理を開始し、ｊの値をつ
ぎつぎに１ずつ増し、重み格納フィールドに前述の終了
マークが現われるまで続け、終了マークが現われたらｉ
の信金１だけ増し、ｊの値を再ひ０に戻してそこから処
理を続行し、最後に、探索指紋特徴点のＱフィールドに
終了マークが現われたらそこでこの処理を終了する。 以上に述べた一ｔ］ｒみマツプ生成処胛をフローチャー
トとして第２６図に示す。 また第２７図に生成された差千面１みマツプの一例を示
す。 なお、第２７図に示すように、本実施例の差平面重みマ
ツプはＡＸおよびΔＹの値として−８から７までの１６
レベルであり、比較的粗く知＝子化されている。従って
ＡＸおよびΔＹＶｃけ前述の計算によってめられた値の
上位４ビット分を用いる。 さて次に、こうして生成された差平面ル］みマッグ上で
１重みの最大年中位置をサーチしその位置の座標ＸＭお
よびＹＭの値を見出す軍み集中位置サーチ処理について
述べる。 この処理は１例えば第２７図に示すような差平面重みマ
ツプ上の恵みの最大隼中位□□□１を見出すことである
が、特定の点に確率的に不当に？Ａい重みが集中し判定
に悪影響を与えるのを避けるために５本実施例において
は　Ｊ、、量子化された差平面の個々の座標位置に格納
されている重みを、そのまま比較してサーチするかわり
に、下記のような荷重サーチを行なう。すなわち、サー
チ点を中心にしてそれに隣接する点を含む全部で９個の
量子化された差平面座標位置の重みに、それぞれ第２８
図に示すような特定の荷重係数を掛け、それらを合計し
たものを比較しながらサーチする荷７１［サーチを行な
う。 このような荷重サーチを冒速で行なうため、本実施例に
おいては専用の第２５図に示す彫椋整合回路２１７をイ
ｊ゛シている。 さて、メモリ６０１（ＤＩＦ）に第２７図に示すような
差平面Ｍ１みマツプが光取し、サーチ動作が開始される
と、以下のように処理が進行する。 まず最初に、サーチ処理に対する座標整合回路２１７の
初期イ１（１化が行なわれ、回路２１７のメモリ６０１
　（ＤＩＦ）’ｔ−除くすべてのメモリおよびレジスタ
に対し、それぞれの初期（１（ｉが設定される。ｆなわ
ち、レジヌタファイル６Ｏ２（ＲＦｌ）および６０３　
（ＲＦ２）、レジスタ６１１（ＲＫＯ）、６１２（１？
に１）、６１３（ｆ（Ｋ２）および６１４（ＭＤＩＦ）
はすべてＯにクリアされる。 またレジスタ６０９（ＤＸ）および６１０（ＤＹ）には
サーチ開始位置として、それぞれ−８がセットされる。 本実施例においては、差千面表示メモリ６０１（ＤＩＦ
）は第２７図に示すように、量子化されたＡＸの値とし
て−８から７までと、ΔＹの値として−８から７までの
値で指定できるが、サーチｂｉ」始位置をこの差平面の
ΔＸ＝−８゜ΔＹ−−８に選ぶ。なお、レジスタ６０９
（ＤＸ）の内容は差平面表示メモ１Ｊ６０１（ＤＩＦ）
のＡＸに対応するアドレス全指定し、レジスタ６１０■
Ｙ）の内容はΔＹに対応するアドレスを指定するのに用
いられる。またサーチ処理においてはライン６１８１（
ＣＴ）Ｕ”Ｏ”　Ｋ設定サレ、コ（７）　ｆｃめ選択器
６１７および６１８は、それぞれレジスタ６０９　（Ｄ
Ｘ）および６１０（ＤＹ）側の入力を選択してメモリ６
０１（Ｌ）ＩＦ）のアドレス指定全行なうよｃ）ＶＣ制
御される。また同様に、サーチ処理においてはライン６
１８１（ＣＴ）の制御によりメモリ６０１（Ｄ１．Ｆ）
は常に抗出し状態にセットされる。 さて、座標整合回路２１７は、制御記憶２１８の制御回
路からライン６１１０（ＴＯ）を介して供給される制御
情報によって制御される二つのタイミングＴｏおよびＴ
１を有している。 ライン６１１０（Ｔｏ）が１”の場合のタイミング’ｋ
Ｔ０どし、このタイミングにおいては下記の動作を行な
う。 まず２選択器６１９，６２０．および６２１は左側の入
力すなわち、それぞれ、メモリ６０１（ＤＩＦ）、ファ
イル６０２（１＜Ｆｌ）およびファイル６０２（ＲＦＩ
）およびファイル６０３（ＲＦ２）の出力全選択するよ
うに制御され、それとともにレジスタ６１１（ＲＫＯ）
、６１２（ＲＫＩ）および６１３（ＲＫ２）の入力仰］
がイネーブルされる。 この結果、第２５図から明らかなように、次の動作が行
なわれる。 ■ＲＫＯＤＩＦＣＤＸ、ＤＹ）＋２ＲＦ１ＣＤＹ）＋Ｒ
Ｆ２（ＤＹ） ■ＲＫＩ　ＲＫＯ ■ＲＫ２　１（Ｋｌ ■　ＲＦＩ（ＤＹ）　ＤＩＦ（ＤＸ、ＤＹ）■　ＲＦ２
（ＤＹ）、ＲＦＩ（ＤＹ） 但し、上のすべての動作表示において、矢印の右側は更
新前のそれぞれの内８に表わし、矢印の左側は更新後の
それぞれの内容を表わす。 （つまり同じ記号であっても右側と左側とでその内容が
異なる）なお、これらの更新は一斉に行なわれるものと
する。 例えば、■■によると、レジスタ６１２　ＣＲＫｌ）の
更新前の内容が更新によりレジスタ６１３ＣＲ，に２）
　に転送されレジスタ６１３ＣＲＫ２）の更新後の同各
となり、また、レジスタ６１１（ＲＫＯ）の更新前の内
容が更新によりレジスタ６１２（ＲＫＩ）に転送されレ
ジスタ６１２（ＲＫｌ）の更新後の内容となること全示
している。 また、ＤＩＦ（ＤＸ、ＤＹ）は、レジスタ６０９（ＤＸ
）およびレジスタ６１０　（ＤＹ）の内容で指定される
メモリアドレスをもつ斧平面表示メモリ６０１（ＤＩＦ
）の内容を表わし、同様にＲＦＩ（ＤＹ）およびＲＦ２
（ＤＹ）はレジスタ６１０（ＤＹ）の内容で指定される
メモリアドレスをもつそれぞれファイル６０２（ＲＦＩ
）およびファイル６０３（ＲＦ２）の内容を表わす。例
えば■の動作表示は、レジスタ６１０（ＤＹ）の内容で
指定されるアドレスをもつファイル６０３（ＲＦ２）の
更新後の内容は、レジスタ６１０（ＤＹ）の内容で指定
されるアドレスをもつファイル６０２（ＲＦＩ）の更１
１前の内容によって書き替えられることを表わす。 さらにまた、■の動作表示で示されているように、加規
、器６０５は選択器６２０倶１からの出力全２倍して達
択器６２１側からの出力に加算するような加算器である
。 さて次に、タイミングＴ１においてはライン６１１０（
Ｔｏ）７）”０”Ｋ＆、０．ライン６２３０（Ｔ１）が
１”になる。この結果タイミングＴ１においては下記の
り力作を行なう。 捷ず、レジスタ６１１（Ｒ，ＫＯ）、６１２（ＲＫＩ）
および６１３（ＲＫ２）の入力端はディセーブルされる
。この結果これらのレジスタの内容はこのタイミングＴ
１期間中そのままの値に保持される。 つぎに１選択器６１９．６２０および６２１は右側の入
力すなわち、それぞれ、レジスタ６】１（ＲＫＯ）、６
１２（ｆ（Ｋｌ）および６１３（ＲＫ２）からの出力全
選択するように制御される。またライン６２３０（Ｔｌ
バじ１′”が供給され、アンドゲート６２３がイネーブ
ルされる。 この結果、第２５図から明らかなように１次の動作が行
なわれる。すなわち、加算器６０６の出力に−は、 ＲＫＯ＋２ＲＫ１＋ＲＫ２ のイレが現われるが、これとレジスタ６１４（ＭＤＩＦ
）の更新前の内容とが、比較器６２２で比較され、もし
、 ■　ＭＤＩＦ≦ＲＫ　０　＋　２　ＨＫ　１−１−　Ｒ
Ｋ　２が成立すると、ライン６２３１がＩＩ　１　ＩＩ
となる結果、レジスタ６１４（ＭＤＩＩｉ’）、６１５
（ＸＭ）および６１６（ＹＭ）の入力１則がイネーブル
され、 ■　ＭＤ　Ｉ　Ｆ　ＲＫＯ〒２　ＲＫ　１　＋　Ｌ（Ｋ
　２■　ＸＭ　ＤＸ ■　ＹＭ　ＤＹ の処理が行なわれる。つまジ■の条件が満足したときに
限ジレジスタ６１４　（ＭＤＩＦ）。 ６１５（ＸＭ）および６１６（ＹＭ）の内容は上の■■
および■の動作表示で示されるように更新され、そうで
ない場合には影響全党けない。 さて、以上につづいて制御記憶２１８の制御ＫＩＳＵラ
イン６０７０（ＴＩ’　）にタイミング情報を送りレジ
スタ６１０（ＤＹ）および６０９（ＤＸ）を更新する。 これらのレジスタの更新は次のように行なわれる。 一般の場合Ｖこは、ライン６０７０（ＴＩ’　）のタイ
ミング情報によりレジスタ６１０（ＤＹ）の更新前の内
ｙｖｃｘが加３°１．されるように更新される。 但し、レジスタ６１０　（ＤＹ）の更新前の内容が上限
の７である場合には、このタイミング情報によりレジス
タ６１０（ＤＹ）の内容は−８に更新され、これととも
に回路６０７からのキャリイが回路６０８に加えられる
。その結果。 さらにレジスタ６０９（ＤＸ）がその更新前の内容に１
が加算されるように更新される。但し。 回路６０７からのキャリイが出ない一般の場合にはレジ
スタ６０９（ＤＸ）の内容は更新によって不変に保たれ
る。 また、レジスタ６０９（ＤＸ）の更新前の内容が上限の
７であるときに１回路６０７からのキャリイが回路６０
８に加えられると１回路６０８がキャリイを発生し、こ
れはライン６０８０’に介して制御記憶２１８の制御部
に供給され、サーチ処理終了の情報として用いられる。 さて、上述のライ７６０７０、（ＴＩ’）のタイミング
情報によるレジスタ６１０（ＤＹ）および６０９（ＤＸ
）の更新がすむと、これでＴ１タイミングが終了し、制
御記憶２１８の制御回路は再び前述のＴｏタイミングの
制御に戻り、更新された各レジスタおよびメモリの内Ｗ
ｋ用いて前述の■〜■の動作を行なう。 こうして、制御部は、座標整合回路２１７へのＴｏタイ
ミングおよびＴ１タイミングの情報をつぎつぎに交替す
ることによりサーチ処理をテアめる。そして、前述のラ
イン６０８０からのサーチ終了情報を受けると、そこで
交替を停止し、そのときのレジスタ６１５　（ＸＭ）　
、　６１６（ＹＭ）および６１４（ＭＤＩＦ’）の内容
ｋｍ；み出す。これで荷重サーチによるサーチ処理が終
了する。なお、この市み集中位置サーチ処理をフローチ
ャートの形で示したのが第２９図である。 以上の動作により座標整合回路２１７は、第２７図に示
すような差平面重みマツプを、第２８図に示す荷重係数
を用いて荷重サーチし、荷重重みＭＤＩＦが最大になる
点の差平面座標の値Ｘ　ＭおよびＹＭとこのＩＶＩＤＩ
Ｆの値とをめたことになるが、この理由は以下に示す通
りである。 上述の説明から明らかなように、サーチ走査は、第２７
図に示す差平面の左下隅から開始し垂直に上方に向って
（ΔＹが増す方向に）走査し、上限に達するとΔＸが１
だけ増して１列右側の縦列に移り、これを同様に下から
上方に向って走査する。これ金繰り返すことにより全面
をカバーする。 今、このよりな走査が、例えば、ΔＸ−３゜ΔＹ＝５の
点まで進んだ状態を巧絡する。このとき、レジスタ６０
８（ＤＸ）、および６１０　（ＤＹ）。 ファイル６０２＜ＲＦＩ）および６０３　（ＲＦ２　）
の各内容は次に示すようになっている。 ＤＸ＝３　、ＤＹ＝５．ＲＦＩ（５Ｊ−ＤＩＦ（２，５
）。 ＲＦ２（５）＝ＤＩＦ（１，５）。 つまり、ファイル６０２（１４Ｉｉ’ｌ）の内容は、現
在走亘中のΔＸ＝３の縦列よりも一つ手前のΔＸ−２の
縦列に対応するメモリ６０１（ＤＩＦ）の内容を格納し
ており、またファイル６０３（ＲＦ２）の内容は、現在
走丘中の縦列よりも二つ手前のΔＸ　、＝＝　１の縦列
に対応するメモリ６０１（ＩＪＩＦ）の内容を格納して
いる。以上により、このときのタイミングＴｏにおける
ｉ’＋ｉｌ述の■のか０作は、ＲＫＯＤＩＦＣ３，５）
＋２ＤＩＦ（２，５）＋ＤＩＦ（１゜５）となる。 一方、ＲＫＩには一つ前の走査時点（ＤＹ＝４のとき）
ＲＫＯの値が、またＲ　Ｋ　２には二つ前の走査時点（
ＤＹ＝３のとき）のＲＫＯの値が更新によって入ってく
るので、上式から明らかなように更新後のＲＫＩおよび
ＲＫ２の値はそれぞれ、 ＲＫ１＝ＤＩＦ（３，４）＋２ＤＩＦ（２，４）＋ＤＩ
Ｆ”（１，４）ＲＫ２＝ＤＩＦ（３，３）＋２ＤＩＦ（
２，３）＋ＤＩＦ（１，３）となる。 従ってタイミングＴ１における加算器７０６の出力の（
ＲＫＯ＋２ＲＫ１＋ＲＫ２）の内容は。 ＤＩＦＣ３，５）＋２ＤＩＦ（２，５）＋ＤＩＦ（１，
５）＋２ＤＩＦ（３、４）＋４ＤＩＦ（２、４）＋２Ｄ
ＩＦ（１，４）十ＤＩＦ（３，３）＋２ＤＩＦＣ２，３
）＋ＤＩＦ（１，３，）となる。これより、上述の処理
ニ°、差平面重みマツプに第２８図に示す荷重係数を掛
けて私算したもの’ｔＭＤ１１ｉ’の候補とし、その最
大なものをめるというサーチをしていることが明らかで
ある。 但し、荷重の中心位置は、現在のＤＸ、ＤＹの指定する
位置ではなくて、それよりもそれぞれ１だけ小さい所に
ある（上の例ではＤＩＦ（３，５）ではなくてＤＩＦ（
２，４）にある）ので最大重み集中位置は上述の処理で
得られたＸＭおよびＹＭの値からそれぞれ１を引いた値
となる。 さて１本実施例は、探紫指紋特徴点の座標系ヲ、判定の
微小角Δθを単位として振Ｖまわし、特定の角度範囲内
の各ｒΔθごとに、上述の差平面重カマツブ生成処理と
、これに対する重み集中位置サーチ処理とを実行し、前
述の荷１重みＭＤＩＦが最も大きくなるよりなγΔθの
値と、そのときのＸＭ−１およびＹＭ−１の値をめるこ
とによりて最適の座標整合量決定する。 このための総合の処理は以下のように進行する。制御記
憶２１８の制御部には作業記憶エリア２１６が含まれる
ているが、この領域の中に次の各バラメータを格＆３す
るレジスタが設けられている（図示せず）。 すなわち、振り廻しの単位となる角Δθ、振り廻し角度
を指定するための倍数ｒ、ｒの最大値γｍ　ａ　ｘ　、
回転角θい回路２１７から読み出し；ｅＭＤＩＦ（この
レジスタに格納された値をＭＤＩＦ’とする）、ＸＭ−
１（このレジスタに格納された値をＸＭとする）、ＹＭ
−１（このレジスタに格納された値をＹＭ″ｊる）。 さて、座標整合量決定の処理が開始されると制御記憶２
１８の制御部は、上述の対応する各レジスタに予め定め
られているΔθおよびγｍａｘを設定し％ＭＤ　Ｉ　Ｆ
’およびｒｈｏに初期値化する。 次に、シーケンス制御回路２１０の演算回路を用いて稼
ｒΔθを作りこれを座標変換回路２１２のパラメールレ
ジスタ１１１２（ΔθＡ）Ｋ格納する。 以上がすむと制御記憶２１８の制御部は前述の差平面重
みマツプ生成処理と、富み集中位置サーチ処理を実行し
％読み出し＊ＭＤＩＦと上述のＭＤＩＦ’とを比較する
。もしＭＤＩＦがＭＤＩＦ’よりも大きい場合にはＭＤ
ＩＦ’　をこの読み出したＭＤＩＦで置き替え、かつＸ
ＭをＸＭ−１およびＹＭ全ＹＭ−１で、また、０Ｍをγ
Δ０で置き替える。 次にγ全変化して上述の処理を繰り返し、ＩγＩ≦γｍ
ａｘのすべてγの値について以上を実行して処理を終了
する。 この処理をフローチャートとして第３０図に示す。 以上に述べた処理が終了したときのθッ、ＸＭおよびＹ
Ｍの値が所望の座標読合はγΔθ、ΔＸＴおよびΔＹＴ
となっている。 最終結果のＭＤＩＦの値があるスレッショルドレベル以
下の時は、座標整合がうまくいかないと判断する。すな
わち、対象の２つの指紋の類似性がないものとして処理
が中断される。座標整合量があるスレッショルドレベル
以下の時には、さらに精密な照合を行なうため、処理が
２次照合プロセッザに引継がれる。 第２次亜合プロセッサには、第１広照合プロセッサから
特徴点リスト、領域パターンリスト、識別情報及び対候
補リストの各情報が共通バスを介して送られてくる。こ
の場合、第２次％徴点メモリ５１１には座標整合量によ
り座標変換された特電点リストが格納される。また領域
パターンリストは領域パターンリストメモリ５１Ｇに７
」候ネ山リストは文Ｊ（ｌ’へ翁１ｊリストメモリにそ
れぞれ格納される。 以上に述べたように１本実施例を用いると。 しかも１両者の座標系が必らずしも整合していない場合
に、特別な差平面重みマツプを作りこのマツプ上で重み
の集中位置を荷重サーチするという独特の手段を用いる
ことにより、座標系の回転に対する試行を行なうだけで
、平行移動に対する試行を行なうことなく、両座＃系を
整合させるために必要な座標整合量を高速且つ高信頼性
をもって決定することができる。 なお、本実施例においては指紋照合の場合について詳述
したが１本発明は何も指紋に限ることなく、特定の複数
の特徴点を有する紋様パターン照合に適用することがで
きる。 また１本実施例においては、特徴点メモ）ハベアリスト
メモリおよび差平面表示メモリに対してそれぞれ特定の
構成および容量を用いたがこれは一例を示したもので伺
もこれに駆足されるものではない。 また、重みの集中位置を荷重サーチするための荷重係数
についても特定の構成を用いたが、これも−例を示した
ものでこれに限るものではない。この荷重係数の構成が
変わるとそれに応じて座標整合回路の構成も変わるが１
本実施例を応用することにより容易に実現可能である。 （７）２次照合プロセッサによる精密照合動作法に、第
５図を参照すると、制御回路５１０は。 座標変換回路５１２を無変換状態にセットし直した後、
対候補リストメモリ５１３の全てのＮｓ：Ｍｓｉ’ｆｒ
再度読出し、その特徴点データＸ、Ｙ。 Ｄを対候補リスト生成時より厳しい閾値’　ｅ　ＴＬＴ
ｄで検査する。なぜなら、探索指紋とイアイル指紋とは
座標整合を完了しているため１本来すでに特徴点は指紋
押捺の歪みを除いてその配位は一致しているはずだから
である。この対検査で否定された候補対Ｎｓ＋Ｍｓｉは
その候補対価Ｗ・とともに対候補リストから削除される
。こ１ れが候補対の精選過程である。 さらに精選された対候補リストについてその全ての候補
対Ｎｓ　ａ　Ｍｆに対して、次のような候補対価の修飾
を行う。即ち、第３１図を参照して２つの候補対Ｎ　ｓ
　：　Ｍ　ｆに対して、各々Ｎ８１Ｍ、をアドレス線５
１１０に供給し、第２次特徴、　点メモリ５１１から各
々の最近傍特徴点（Ｎｓｒ。 Ｍｆｒ：ｒ＝０〜３）を読出し、対候補リストメモＩＪ
　５１３のＮ行にＭｆｒが登録されているか否か全検査
する。もしＭｆ　’　−Ｍｆ　ｒとして登録されていれ
ばその候補対価Ｗｂ’ｋ、基になったＮｓ２Ｍｆの候補
対価Ｗ８に加える。候補対価の修飾が完了すると、新し
い候補対価の大きさに従って対候補リストメモリ５１３
の内容はＮ８行毎にソートされる。以上で最終的な対候
補リストが完成する。この対候補リストを元にして対リ
スト５１５ａ１５１５ｂ　が対リストメモリ５１５に生
成される。 対リストメモリ５１５（ハ）にある２つの対リスト５１
５ａ、５１５ｂは相似の構造であって、第３２図に示さ
れるようにＮ、（８＝１〜Ｓ）及びＲ４４（ｆ＝１〜Ｆ
）でアドレス線５１５０を介してアドレスが指足され、
特徴点番号と対価Ｍ１　、Ｖ。 及びＮ８．Ｖｆ　’ｆｒ保持できる２組のメモリである
。 対リスト５１５ａ、５１５ｂの生成は、当初対価として
負の定数で初期化された後、対候補リストのＮ８（Ｓ＝
１〜Ｓ）の順に複数回走査しながら、その最圧端ｉ　＝
　ｌ即ち最大の候補対価を有する候補対Ｎ、：Ｍ、１を
その候補対価Ｗｓ１自身及び第２の候補対価Ｗ８□との
差によって信頼性の高いものから対リス）５１５ａ、５
１５ｂにその候補対価を対価として移す。対リストに登
録した候補対は全対候補リスト中から抹消される。全て
の対候補リストメモリ５１３の内容が対リストメモリ５
１５に移された時点での対Ｎｓ：Ｍｆの対価はυ８＝υ
ｆ＝ｃＮ８：Ｍｆ）　の候補対価となっている。又、候
補対価によって移されなかった対リスト中の特徴点の対
価は負の初期値がそのま＼残る。 次に対価の決定は、対価の修飾と、非対値の緩和の２つ
の処理によって成される。 対リス）　５１５　ａ　、　５１５　ｂ　ｆｆ１ｌｌ１
次調べその対価υが正であるときは対価の修飾を行う。 即ち第３３図′に示すように１例えば対リス）５１５ａ
中のＮ８の対価υ８が正であるときは、その対特徴点Ｍ
ｆを基にして候補対価の修飾と同様に第２次特徴点リス
トメモリ５１１をアクセスしてその最近傍特徴点（Ｎ８
ｒ、Ｍｓｒ：ｒ−θ〜３）全読出し、対リス）５１５ａ
のＮ　の対がＭ８ｒ　でかつ対価υｓｒｒ が正であるか否かを検査する。もし正なら対価υ　が対
価υ８に加えられる。相似な処理が対ｒ リスト５１５ｂ　側でも対リスト５１５ａ側と独立に行
われる。一方第３４図の如く対リストに正の対価が格納
されていないとき２例えば対リス）５１５ｂに於けるあ
るＭ４　／が負の対値υｆ′全もっているときは、この
Ｍｆをアドレス線５１１０にｌｆし。 Ｍｆ′の特徴点データを線５１２０を介して断ルし、そ
のＣＸｆ’　、Ｙｆ’　）　’ｆｆｉ領域パターンリス
ト５１６ａの２次元アドレスとして線５１６０に供給す
る。その結果出力５１６１から読出された領域値が０”
であれば、上記特徴点Ｍｆ／は探索指紋側の不明領域内
であったこととなり対価υｆ′はｄｏｎ’ｔ　ｃａｒｅ
　ｆ意味する値１０″に畳換見られる。一方領域値が１
″なら対１１〃υｆ′はそのま＼となる。逆に対リスト
５１５ａで上記の処理を行うときは座標変換回路５１２
に逆変換量（ξ＝△Ｘ苦、η＝−ΔＹ牙、θ＝−△１憤
をセットし、領域パターンリストメモリ５１６の内ｇｋ
調べる。 対価υｆ’　７Ｊｒｌｖ　８’が負値のま＼保存された
特徴点Ｍｆ′又はＮｓ′については１次のような検査全
行う。例えばＭｆ′については、最近傍特徴点（”ｆｒ
’　；　ｒ＝ｏ〜３）の内隆線数Ｒ１；＝０となるもの
でその配置が近く、方向が正反対を向いているものがな
いかを演算回線５１９での対向検査処理により探す。も
しあればその特徴点Ｍｆ／。 を対リスト５１５ｂで検査しその対価υｆ’ｒが負の値
であれば、この対価υｆ’ｒと上記Ｍｆ′ヲともにｄｏ
ｎｔ　ｃａｒｅ　とし対価″０”に変更する。これは、
第３５図に示す如く、対向する近接％微意を検査するも
ので、このような２組の特徴点は指紋押捺の具合いや機
械的な自動特徴点描出時に描出されたりされなかっｆｃ
！ｌｌする不安定な特徴点である。 第３６図は対向検査回路の一実施例を示すブロック図で
ある。１２１ｊち、差絶対値器１６３Ｘ、ｙ。 ｄ、　ＭＩＮ１６３　ｃ比較器１６４ＸＩｙ１ｄ、方向
ＲＯＭ１６５、　ム對※１６６　ａ　、　ｂ、比較器１
６７ａ、ｂ。 ＡＮＤゲート１６８及び閾値ＲＯＭ１６９から構成され
る。 「対向」検査されるべき２組の特徴点データ（Ｘ、Ｙ、
Ｄ）と（Ｘ’　、Ｙ’　、Ｄ’　）がそれぞれ入力信号
１６１Ｘ、ｙ、ｄ及び１６１　Ｘ’　＋３”　ｌｄに供
給されると、補数値１６３Ｃで方向Ｄ′のみが方向補数
即ち、πラジアンだけ反転式れた後差絶対値器１６３　
ｘ、ｙ、ｄで差の絶対値が演算され。 閾値ＲＯＭ１６９の出力である閾値と比較器１６４Ｘ、
ｙ、ｄで比較される。即ち ＩＸ−Ｘ’　ｌ≦隻、ＩＹ−Ｙ’　ｌ≦Ｔｙ、ＩＤ−Ｄ
’＋π１≦Ｔｄ が検査され、その出力がＡＮＤゲート１６８に入力され
る。ここで方向成分ではπラジアンが差絶対値器１６３
ｄの最上位ピッ）（ＭＳＢ）に相対する様に接続され、
方向演算に於ける周期性に対する正しい演算が保証され
る。一方、差絶対値器１６３Ｘ、ｙの差絶対値出力と差
符号（減算時の符号）は方向ＲＯＭ１６５にアドレスと
して入力され、その指定する方向△Ｄを出力し差絶対値
器１６６ａ、ｂに供給する。即ちなる△Ｄが近接してい
るという条件から比較的小さいｘ−ｘ’及びＹ−Ｙ’の
全ての組合せを入力として、ＲＯＭ化されている。−力
方向Ｄ−Ｄ’と上記ΔＤは差絶対値器１６６ａ、ｂでそ
の差の絶対値が演算され比較器１６７ａ、ｂで閾値ＲＯ
Ｍ１６９からの別の予じめ定められた値と比較され、そ
の結果がＡＮＤゲート１６８に供給される。ＡＮＤゲ−
）１６８ｔ−ｊ全ての入力が肯定されたとき「対向」検
査肯足信号を出力信号１６２を介してシーケンス制御回
路５１０に戻す。 上記の差絶対値器１６６ａ、ｂに於いては方向りとΔＤ
及びＤ′と△Ｄとはπラジアンの差異は０ラジアンに相
当するので減算の最上位ビット上記の差絶対値器１６６
ａ、ｂに於いては方向りとΔＤ及びＤ′とΔＤ、！：は
πラジアンの差異は０ラジアンに相当するので減算の銀
上位ピット（ＭＳＢ）は−となるよう配線されている。 以上で、対向検査回路の一例を説明した。なおこの対向
検査回路は汎用プロセッサで代替できる。負の対価を有
する対リスト中の検査に於いて、上述の「対向」特徴点
でないときは、最終的にその特徴点の集密量Ｃを検介し
１価比較でそれが非常に大きいときはやけジ対価″Ｏ”
又は負の０”に近い値にセットし直す。以上をまとめて
、第３７図に模式的に示したように非対価の緩和は、探
索指紋とファイル指紋との座標整合後の領域パターン５
１６ａ、５１６ｂの非共通領域に存在する非対特徴点及
び共通領域内で点線で示しｆｃ「対向」特徴点及び集密
ｈＦの大きい特徴点についてその非対価’１ｄｏｎ’ｔ
ｃａｒｅ又はそれに近い負の対１１ηに緩和しようとす
るものである。 以上で対リストの対値が完成すると、制御部回路５１０
は対リス）５１５’＆順次読出しながら照合値ｑとして ｘＦ を演算回路５１９および作業エリア５１４から算出する
。ここにＳ及びＦは探索指紋及びファイル指紋の領域パ
ターン５１６の共通領域内の特徴点数を示す。これらの
演算については、一般的な四則演算回路で実施できるの
で詳細は省略する。 説、明を簡明にするため、対候補リストの候補対値修飾
及び対リストの対値の修飾に於いて最近傍特徴点で対応
する（Ｎ８．＋Ｍｆｒ；　ｒ＝Ｑ〜３）の対応検査につ
いてのみ咋明したが、一般的には指紋の特徴点の配位の
歪みから必ずしも同じｒ’ｔ’Ｎ、ｒとＭｆｒの対応を
期待できるものではなく、Ｎｓｒに対し異なるｒ′　で
あるＭｆｒ′　が対応する場合もあるので、（Ｎ８ｒ、
Ｍｆｒ；　ｒ＝０〜３）は象限ｒ単位で比較するのでは
なく（Ｎ８ｒ；ｒ＝０〜３）と（Ｍｆｒ′；ｒ＝θ〜３
）の１６回総当り的に対応を検査するのが精密である。 この場合の対応検査は各々ＮｓＩＭｆを基準とした局所
座標系による ＜　Ｎ８＞＜Ｍｆ＞　＜Ｎ、）　＜Ｍｆ＞　＜Ｎ５）１
Ｘｓｒ−Ｘｆｒ′Ｉ≦ＴＸ　ｌ　ｌ　Ｙｓｒ　−Ｙｆｒ
　’　ｌ≦ＴｙｌｌＤ８．−＜Ｍｆ＞ Ｄｆｒ制≦Ｔｄ により行われる。これらは座標変換回路５１２及び対検
査処理により対候補リスト生成時の処理と同様に可能で
ある。 ２次照合プロセッサにより最終時ＫＷ出された照合値８
があるスレッショルドレベル以上の時には、ファイル指
紋識別番号及び照合値　があるスレッシタルトレベル未
満の時は類似性がないものと判断され％候補リストへは
登録されず照合が終了される。 （８）転送先プロセッサ決定動作 本発明の一実施例では、第２Ｂ図に示す構成を基にして
いるが、第２Ｃ図に示す装置構成を採ることによりさら
に照合性能（１対１の照合時間）を向上させる効釆があ
る。 第２Ｃ図に示す指紋照合装腸は、制御ユニット１０、同
一構成の１次照合プロセッサｍ台（ｍ〉１）、２次照合
プロセッサｎ台（ｎ〉１）および制御ユニッ）１０．１
次照合プロセッサおよび２次照合プロセッサ間でデータ
を伝送する共通バス７０から構成されている。実施例で
はｍ＝３．すなわち１次照合プロセッサ２０゜３０　、
４０　、およびｎ＝２．すなわち２次照合プロセッサ５
０，６．０の場合を示している。この様な装置では各プ
ロセッサは共通の探索指紋と各々異なるファイル指紋と
の１対１の照合全行なっているため、プロセッサ間並列
処理となり高速照合が可能となる。 第３Ｂ図は第２Ｃｌネ１の照合装置における制御ユニッ
ト１０内の転送先決足回路３０４の詳細な構成を示す図
である。 照合装置５が照合制御装置４から照合の指示を受けると
、制御ユニット１０は、第３Ｂ１ン１に示すようにデー
タ転送要求１１を内部の第１決定回路１００に出力する
。第１決定１０回路１００は１次照合プロセッザ２０．
３０および４ｏが指紋照合中であることを示す各ビジー
信号２１゜３１および４１を入力とし次式により１表わ
される論理動作を行ない、信号２２，３２および４２を
出力して、ファイル指紋データの転送先１次照合プロセ
ッザの第１決定１０なう。 信号２２＝（データ転送要求１１）ＡＮＤ（？’シ１１
２１＞ 信号３２＝（データ転送要求１１）ＡＮＤ（ｆｆジー信
号２１）ＡＮＤ（ビジー化 号３１） 信号４２＝（データ転送要求１１）ＡＮＤ（ビジー信号
２１）ＡＮＤ（ビジー化 号３１ンＡＮＤ（ビジー信号４１） 第２決定回路２００は、１次照合プロセッサ２０．３０
および４０からの２次照合プロセッサベの各データ転送
要求２５．３５および４５と、２次照合プロセッサ５０
および６０が処理中であること金示す各ビジー信号５１
および６１とを入力とし次式により表わされる論理動作
を行ない、信号２６，３６．４６．５２および６２と抑
止信号７１とを出力して、１次照合終了のファイル指紋
データの転送先２次照合プロセッサの第１次決定と、２
次照合プロセッサへのデータ転送があるときの１次照合
プロセッサへのデータ転送抑止信号発生とを行なう。 信号２６−（データ転送要求２５） 信号３６＝（データ転送要求２５）ＡＮＤ（データ転送
要求３５） 信号４６＝（データ転送要求２５　）ＡＮＤげ一夕転送
要求３５）ＡＮＤ（デー タ転送要求４５） 信号５２＝（：（データ転送要求２５）ＯＲＣデータ転
送要求３５）ＯＲ（デー タ転送要求４５））ＡＮＤ（ビジ 一信号５１） 信号６２＝（：（データ転送要求２５）ＯＲ＜データ転
送要求３５）ＯＲ（デー タ転送豐求４５））ＡＮＤ（ビジ ー信号６１　） 抑止信号７１＝［：（データ転送要求２５）０Ｒ（デー
タ転送要求３５）Ｏ Ｒ（データ転送要求４５）〕 ＡＮＤ（ビジー信号５１）Ａ ＮＤ（ビジー信号６１）ＯＲ 〔（データ転送袂ｙＲ，！２５ンＡ ＮＤ（データ転送要求３５） ＡＮＤ（データ転送要求４５）〕 第３決定回路３００は、信号２２．３２および４２と抑
止信号７１との各論理積である信号２３．３３および４
３と、上述のようにしてまる信号２６．３６．４６．５
２および６２と。 ビジー信号５１および６１と全入力とし次式により表わ
される論理動作全行ない、ファイル指紋データの転送の
ために共通バス７０の使用を許可する１次照合プロセッ
サあるいは２次照合プロセッサの１台を決定する。 １次照合プロセッサ２０へのバス使用決定信号２４＝ｃ
ｍ号２３）ＯＲ（信号２６）１次照合プロセッサ３Ｏへ
のバス使用決定信号３４−（信号３３）ＯＲ（信号３６
）１次照合プロセッサ４０へのバス使用決定信号４４＝
（信号４３）ＯＲ（信号４６）２次照合プロセッサ５０
へのバス使用決定信号５３，２１，３１，４１．５１お
よび６１が変数になっており、各グロセッザは相異なる
ファイル指紋データに対して並列し１ＣＣ指紋台ができ
ることを示唆している。 本発明の災施例については、その動作説明から明らかな
ように製品化されているマイクロコンビニ−タを用いて
、処理装置で対検査回路、対向検査回路及び制御部を、
又メモリによって領域パターン、特徴点リスト、多平面
、対候補リスト及び対リストｅ割当ることによって等価
な出力を得ることがｉｆＪ’能である。

【図面の簡単な説明】

第１図は、指紋パターン上の特徴点リストした図、第２
Ａ図は指紋１ｆ（を合システムの一例を示す図。 第２Ｂ図は第２Ａ図に示される本発明の一実施例である
指紋照合装置の（１４成を示す図、第２Ｃ図はさらに拡
張させた指紋照合装置の輛成金示す図、第３図は第２Ｂ
および２０図で示した装置、内の制御ユニットの構成を
示す図、第４（図は本発明の装置における第１送台合プ
ロセッサの一実施ｐＨヲ示す図、第５図は本発明の装置
における第２次照合プロセッサの一実施例を示す図、第
６図は本発明の指紋照合方法を示すフローチャート、第
７図は指紋照合において使用される一指分の特徴点デー
タを示す図、第８Ａ図は指紋照合において使用される特
徴点リストの一例を示す図、第８Ｂ図に最近特徴点を説
明するための図、第９図は一般的な座標変換動作′ｆ：
説明するための座標系を示す図、第１０図は一般的な座
標変換動作を説明するフローチャート、第１１図は第１
火照合プロセッサ及び第２広照合プロセッサで使用する
本発明の一実施例を示す座標変換回路の構成を示す図、
第１２図は本発明の一実施例を示す最近傍特徴点復元回
路の構成を示す図、第１３図は最近幼時像点復元後の特
徴点リスト全示す図、第１４図は最近傍特徴点を示す図
、第１５図は最近傍特徴点復元動作を示すフローチャー
ト、第１６図は本発明の一実施例である対検査回路を示
す図、第１７図は対検査回路で使用する特徴点リストの
一実施例を示す図、第１８図は対検査回路内の特徴点メ
モリ部を示す図、第１９図は対検査回路内のりレーショ
ン連結部を示す図、第２０図は対検査回路内の対検査部
を示す図、第２１Ａ図は本発明に用いる２次リレーショ
ンデータを説明するだめの指紋パターンの簡易化した詳
細拡大図、第２１Ｂ図は本発明の一実施例である２次リ
レーションデータを用いた対検査回路を示す図％第２２
図は第２１Ｂ図で示す対検査回路で使用する特徴点リス
トの一実施例を示す図、第２３図Ｖｉ第２１図で示す対
検査回路内の複合リレーション連結部を示す図、第２４
図は対候補リストメモリの一実施例を示す図、第２５図
は本発明の座標整合量決定回路の一実施例を示す図、第
２６図第２９２図および第３０図は座標整合量決定動作
を説明したフローチャート、第２７図は座標整合量決定
回路で生成する重みマツプの一例を示す図、第２８図は
座標整合量決定動作で使用する荷重係数を示す図、第３
１図は対候補の強調処理を説明するための図、第３２図
は本発明に用いる対リストメモリの一実施例を示す図、
第３３図は対リストと対特徴点の関係を示す図、第３４
図は、対リストの同各の一例を示す図、第３５図は２つ
の特徴点が対向特徴点となる例を示した図、第３６図は
対向検査回路の一実施を示す図、第３７図は探索及びフ
ァイル指紋と領域ノくターンとの関係を示す図、および
第３８図は制御ユニット内の転送先決定回路の一実施例
を示すフ。 ロック図である。 ・−＼、 め／図 尊　２Ａ　回 茶２Ｃ咽 Ｙ２Ｂ図 入〃醪Ｅ錠に妃リスト ｌ ＄３β　団 肇　ｉｔ　Ｉ！ｌ 茶　１７　図 第１ｇ　図 暇／り図 第　２θ　図 第２ｉＡ　図 第　２１Ｂ　図 第　２２　閉 第　２３　図 θ　／　ｚ　−一−−−ｊ−−−−−−ｙｓ第　２４　
図 △Ｘ 第　２７　図 第２δ図 第　２タ　良 第　３１　図 第　３２　図 第　３３　図 第　３４　刺 第　３５　図 第　３〆　図 第　３７　図

Claims (1)

1. 【特許請求の範囲】 １、　探索指紋とファイル指紋の同一性を判別する指紋
   照合装置Ｋｈ−いて。 適宜に定めた点を原点とする直焚座標系に基づく前記探
   索及びファイル指紋の特徴点の位置、角度、およびリレ
   ーションデータを保持する特徴点リスト記憶手段と。 前記各特徴点を原点とする局所座標系に座標変換を行な
   い、前記２つの指紋の各特徴点間の位置、角度、２よび
   リレーションデータの一致性を検査することによｐ対候
   補リストを保持する対候補リスト記憶手段と、 前記特徴点リスト記憶手段２よび対候補リスト記憶手段
   によシ前記２つの指紋に対する最適座標整合量を生成す
   る最適座標整合量生成手段前記最適座標整合量によシ整
   台ちれｆｃ座標系下で前記２つの指紋の各特徴点間に対
   し、脱せされた位置、角度２よびリレーションデータの
   一致性を横歪することにより前記対候補リストから真の
   対特徴点２よび対値を決定して保愕する対リスト記憶手
   段と、 前記対特徴点と対憾から前記２つの指紋の照合値を決定
   し、保持する欣補指紋記憶手段とを含むことを特徴とす
   る指紋照せ装置。 ２、探索指紋とファイル指紋の同一性を判別する指紋照
   会装置に２いて、 指紋の特徴点を原点とした局ＰＪｒ座像系に２いて、該
   原点に最も近い第１次近傍符徴点の位置、角度、および
   リレーションデータを含む４１次リレーションデータ（
   Ｉ：記憶する第１の記憶手段と、 前記第１次Ｍ近傍％徴点を原点とし九局欣座標系におい
   て該ｙＡ点に最も近い第２仄ポ近傍特徴点の位置、角度
   、およびリレーションデータを含む第２次リレーショｙ
   データを記憶する第２の記憶手段とを含むことを特徴と
   する特許請求範囲第１項６ｄ載の指紋照合装置。 ３、　探索指紋とファイル指紋を照せする指紋照会装置
   において。 基準座標系における各特徴点の位置、Ｎ度、およびリレ
   ーションデータを格納する第１の特徴点リスト記憶手段
   と。 前記対候補リスト記憶手段および前記座標変換手段によ
   シ対候補特徴点を別の座標系で座標変換してまる特徴点
   の位置、角度、およびリレーションデータを格納する第
   ２の特徴点リスト記憶手段とを有する特徴点リスト記憶
   手段と、前記第１の特徴点リスト記憶手段と対候補リス
   ト記憶手段から最適座標整合量を生成する最適座標整合
   量生成手段と。 前記第１の特徴点リスト記憶手段、対候補リスト記憶手
   段、および最適座標整合量生成手段′に連結した座標変
   換手段と、 前記第２の特徴点リスト記憶手段、対候補リスト記憶手
   段、２よび指紋領域ｇｄ憶手段に連結され前記２つの指
   紋の第２の特徴点リスト上の座標整合された各等微意の
   位置、角度、およびリレーションデータの一致性を横置
   することによル生成される対リストを生成する前記対リ
   スト記憶手段とを含むこと全特徴とする前記特許請求範
   囲第１項記幅の指紋照合装置。