(57)【要約】  【課題】  本発明は，画像処理，特異点抽出，特異点照合からなる指紋照合工程の中で，作業メモリが少なく，迅速かつ精度の良い特異点照合が可能な指紋照合システムの実装法などを提供することを目的とする。    【解決手段】  本発明は，基本的には，登録指紋と入力指紋との特異点をトレースするとともに，特異点対の位置差に応じたメモリ番地に照合スコアを累積して記憶させることで，登録指紋と入力指紋との位置及び回転のずれを把握し，適切な指紋対スコアを得て，指紋照合を行うシステムに関する。さらに本発明の好ましい態様では，大まかな検索を行うグローバル検索を行って位置及び回転のずれを大まかに把握して，それらの周辺について詳細な検索を行うローカル検索を行うことにより，メモリコストを抑えることができるとともに，指紋照合の正確さや速度が高まるという知見に基づく。【選択図】  図１
2008165445.tif 000002
【特許請求の範囲】
【請求項１】
登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む“登録指紋の特徴情報”を記憶する登録指紋情報記憶手段と，
入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む“入力指紋の特徴情報”を記憶する入力指紋情報記憶手段と，
前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する2次元累積スコア記憶手段と，
前記登録指紋情報記憶手段から読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶手段から読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算手段と，
前記登録指紋情報記憶手段から読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶手段から読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の距離を計算するトレース点間距離計算手段と，
前記トレース点間距離計算手段が計算したトレース点間の距離を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算手段と，
前記2次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する累積スコア計算手段と，
を具備し，
前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間距離計算手段によるトレース点間距離計算，前記照合スコア計算手段による照合スコア計算，及び前記累積スコア計算手段による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
指紋照合システム。
【請求項２】
前記“登録指紋の特徴情報”及び前記“入力指紋の特徴情報”は，
分岐点であるか端点であるかを識別するための特異点のタイプに関する情報，
特異点がいくつのトレース点を含むかに関するトレース点数に関する情報，
特異点の始点の水平位置に関する情報である水平座標Ｘに関する情報，
特異点の始点の垂直位置に関する情報である垂直座標Ｙに関する情報，
特異点の始点での水平軸に対する隆線方向の角度θに関する情報，
特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１に関する情報，
第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２に関する情報，及び，
第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３に関する情報，
を含む３２ビットの情報である
請求項１に記載の指紋照合システム。
【請求項３】
第１の回転角についての前記照合スコア計算手段による照合スコア計算工程が行われる間に，第2の回転角についての前記トレース点間距離計算手段によるトレース点間距離計算工程が行われ，
前記第1の回転角についての前記累積スコア計算手段による累積スコア計算工程の間に，前記第2の回転角についての照合スコア計算工程が行われると共に，第3の回転角についてのトレース点間距離計算工程が行われ，
以後も同様にして並列処理を行うように，各処理の工程時間を調整する工程時間調整手段を具備する
請求項1に記載の指紋照合システム。
【請求項４】
前記トレース点間距離計算手段は，
前記入力指紋又は前記登録指紋の一方の特異点について，
特異点の始点の水平位置に関する情報であるＸ，
特異点の始点の垂直位置に関する情報であるＹ，
特異点の始点での水平軸に対する隆線方向の角度θ，
特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１，
第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２，及び，
第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３，とし，
前記入力指紋又は前記登録指紋の残りの特異点について，
特異点の始点の水平位置に関する情報であるＸ’，
特異点の始点の垂直位置に関する情報であるＹ’，
特異点の始点での水平軸に対する隆線方向の角度θ’，
特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１’，
第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２’，及び，
第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３’，とした場合に，
θ及びθ’が入力され，入力されたθ及びθ’を用いてΔθに相当するθ−θ’を求めて出力する第1の減算器(161)と，
φ１及びφ１’ が入力され，入力されたφ１及びφ１’を用いてΔφ１に相当するφ１−φ１’を求めて出力する第2の減算器(162)と，
φ２及びφ２’ が入力され，入力されたφ２及びφ２’を用いてΔφ２に相当するφ２−φ２’を求めて出力する第3の減算器(163)と，
φ３及びφ３’ が入力され，入力されたφ３及びφ３’を用いてΔφ３に相当するφ３−φ３’を求めて出力する第4の減算器(164)と，
前記第1の減算器(161)からの出力であるΔθと前記第2の減算器(162)からの出力であるΔφ１とが入力され，入力されたΔθ及びΔφ１を用いてΔθ＋Δφ１を求めて出力する第1の加算器(165)と，
前記第1の減算器(161)からの出力であるΔθと前記第1の加算器(165）からの出力であるΔθ＋Δφ１とが入力され，入力されたΔθ及びΔθ＋Δφ１を用いて２Δθ＋Δφ１を求めて出力する第2の加算器(166)と，
前記第1の加算器(165）からの出力であるΔθ＋Δφ１と前記第3の減算器(163)からの出力であるΔφ２とが入力され，入力されたΔθ＋Δφ１及びΔφ２を用いてΔθ＋Δφ１＋Δφ２を求めて出力する第3の加算器(167)と，
前記第1の減算器(161)からの出力であるΔθが入力され，入力されたΔθを記憶するための第1のレジスタ(168)と，
第2の加算器(166)からの出力である２Δθ＋Δφ１が入力され，入力された２Δθ＋Δφ１を記憶するための第2のレジスタ(169)と，
第3の加算器(167)からの出力であるΔθ＋Δφ１＋Δφ２が入力され，入力されたΔθ＋Δφ１＋Δφ２を記憶するための第3のレジスタ(170)と，
前記第4の減算器(164)からの出力であるΔφ３が入力され，入力されたΔφ３を記憶するための第4のレジスタ(171)と，
前記第2のレジスタ(169)が記憶した２Δθ＋Δφ１と前記第3のレジスタ(170)が記憶したΔθ＋Δφ１＋Δφ２とが入力され，入力された２Δθ＋Δφ１及びΔθ＋Δφ１＋Δφ２を用いて３Δθ＋２Δφ１＋Δφ２を求めて出力する第4の加算器(172)と，
前記第3のレジスタ(170)が記憶したΔθ＋Δφ１＋Δφ２と前記第4のレジスタ(171)が記憶したΔφ３とが入力され，入力されたΔθ＋Δφ１＋Δφ２及びΔφ３を用いて，Δθ＋Δφ１＋Δφ２＋Δφ３を求めて出力する第5の加算器(173)と，
前記第4の加算器(172)からの出力である３Δθ＋２Δφ１＋Δφ２と前記第5の加算器(173)からの出力であるΔθ＋Δφ１＋Δφ２＋Δφ３とが入力され，入力された３Δθ＋２Δφ１＋Δφ２及びΔθ＋Δφ１＋Δφ２＋Δφ３を用いて４Δθ＋３Δφ１＋２Δφ２＋Δφ３を求めて出力する第6の加算器(174)と，
前記第1のレジスタ(168)からの出力であるΔθが入力され，入力されたΔθを記憶するための第5のレジスタ(175)と，
前記第2のレジスタ(169)からの出力である２Δθ＋Δφ１が入力され，入力された２Δθ＋Δφ１を記憶するための第6のレジスタ(176)と，
前記第4の加算器(172)からの出力である３Δθ＋２Δφ１＋Δφ２が入力され，入力された３Δθ＋２Δφ１＋Δφ２を記憶するための第7のレジスタ(177)と，
前記第6の加算器(174)からの出力である４Δθ＋３Δφ１＋２Δφ２＋Δφ３が入力され，入力された４Δθ＋３Δφ１＋２Δφ２＋Δφ３を記憶するための第8のレジスタ(178)と，
前記第5のレジスタ（175）に格納されたΔθが入力され，入力値の絶対値である｜Δθ｜を求め，出力する第1の絶対値回路(181)と，前記第6のレジスタ(176)に格納された２Δθ＋Δφ１が入力され，入力値の絶対値である｜２Δθ＋Δφ１｜を求め，出力する第2の絶対値回路(182)と，前記第7のレジスタ(177)に格納された３Δθ＋２Δφ１＋Δφ２が入力され，入力値の絶対値である｜３Δθ＋２Δφ１＋Δφ２｜を求め，出力する第3の絶対値回路(183)と，前記第8のレジスタ(178)に格納された４Δθ＋３Δφ１＋２Δφ２＋Δφ３が入力され，入力値の絶対値である｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め，出力する第4の絶対値回路(184)と，を含む絶対値算出部と，
を具備する，
請求項３に記載の指紋照合システム。
【請求項５】
前記照合スコア計算手段は，
前記絶対値算出部で算出された各トレース点間距離の総和を求めるトレース点間距離の総和算出部と，及び前記トレース点間距離の総和算出部で算出されたトレース点間距離の総和を用いて照合スコアを算出する照合スコア算出部とを具備し，
前記トレース点間距離の総和算出部は，
前記第1の絶対値回路(181)及び前記第2の絶対値回路(182)で求められた｜Δθ｜及び｜２Δθ＋Δφ１｜がそれぞれ入力され，入力された前記｜Δθ｜及び前記｜２Δθ＋Δφ１｜を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜を求め出力する第7の加算器(185)と，
前記第3の絶対値回路(183)，及び前記第4の絶対値回路(184)で求められた｜３Δθ＋２Δφ１＋Δφ２｜及び｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜がそれぞれ入力され，入力された前記｜３Δθ＋２Δφ１＋Δφ２｜及び前記｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を加算して，｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め出力する第8の加算器(186)と，
前記第7の加算器(185)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜と，前記第8の加算器(186)が出力した｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜とが入力され，入力された前記（｜Δθ｜＋｜２Δθ＋Δφ１｜）及び前記（｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜）を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求めて出力する第9の加算器（187）と，
前記第9の加算器(187)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜が入力され，入力されたトレース点間距離の総和Ｄｔｒａｃｅである前記｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を記憶する第9のレジスタ(188)と，
を具備し，
照合スコア算出部は，
特異点のトレース点の数であるトレース点の数Ｎｔｒａｃｅが入力されると，前記Ｎｔｒａｃｅに所定の係数を乗じた値であるトレース点間個数関連値を出力するトレース点間個数関連値出力部(190)と，
前記第9のレジスタ(188)に格納されたトレース点間距離の総和Ｄｔｒａｃｅ及びトレース点間個数関連値出力部(190)から出力されるトレース点間個数関連値が入力され，これらの入力値の減算演算を行う第5の減算器(189)と，
前記第5の減算器(189)の演算結果が入力され，入力された値である照合スコアを記憶する第10のレジスタ(191)とを具備する
請求項４に記載の指紋照合システム。
【請求項６】
登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む“登録指紋の特徴情報”を記憶する登録指紋情報記憶手段と，
入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む“入力指紋の特徴情報”を記憶する入力指紋情報記憶手段と，
前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する水平位置差用の1次元累積スコア記憶手段と，
前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の垂直位置差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する垂直位置差用の1次元累積スコア記憶手段と，
前記登録指紋情報記憶手段から読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶手段から読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算手段と，
前記登録指紋情報記憶手段から読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶手段から読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の距離を計算するトレース点間距離計算手段と，
前記トレース点間距離計算手段が計算したトレース点間の距離を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算手段と，
前記水平位置差用の１次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する水平位置差用の累積スコア計算手段と，
前記垂直位置差用の１次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する垂直位置差用の累積スコア計算手段と，
を具備し，
前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間距離計算手段によるトレース点間距離計算，前記照合スコア計算手段による照合スコア計算，及び前記累積スコア計算手段による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
指紋照合システム。
【請求項７】
請求項１に記載の指紋照合システムをローカル検索システムとして，請求項６に記載の指紋照合システムをグローバル検索システムとして具備する指紋照合システムであって，
前記グローバル検索システムは，
最終照合スコアを与える前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差と垂直位置差を，前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差と垂直位置差の概略値として出力する概略値出力手段を具備し，
前記ローカル検索システムは，
前記グローバル検索システムから出力された水平位置差と垂直位置差の概略値を受取る概略値受信手段と，
前記概略値受信手段が受取った概略値から所定の量変動する範囲を前記概略値の周辺範囲として求める概略値の周辺範囲計算手段と，
前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差が前記周辺範囲に含まれるかどうか判断する特異点位置差判定手段と，
前記特異点位置差判定手段が前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差が前記周辺範囲に含まれると判断した場合にのみ，前記照合スコアを計算するように制御する照合スコア演算制御手段と,
を具備する，
指紋照合システム。
【請求項８】
前記２次元累積スコア記憶手段は，前記概略値の周辺範囲に対応したアドレスを有する，
請求項７に記載の指紋照合システム。
【請求項９】
コンピュータを，
登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む“登録指紋の特徴情報”を記憶する登録指紋情報記憶手段と，
入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む“入力指紋の特徴情報”を記憶する入力指紋情報記憶手段と，
前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する2次元累積スコア記憶手段と，
前記登録指紋情報記憶手段から読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶手段から読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算手段と，
前記登録指紋情報記憶手段から読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶手段から読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の距離を計算するトレース点間距離計算手段と，
前記トレース点間距離計算手段が計算したトレース点間の距離を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算手段と，
前記2次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する累積スコア計算手段と，
を具備し，
前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間距離計算手段によるトレース点間距離計算，前記照合スコア計算手段による照合スコア計算，及び前記累積スコア計算手段による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
ように機能させる指紋照合システム用プログラム。
【請求項１０】
請求項９に記載されるプログラムを記憶したコンピュータ読取可能な情報記録媒体。
【請求項１１】
登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む登録指紋の特徴情報を記憶する登録指紋情報記憶手段と，
入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む入力指紋の特徴情報を記憶する入力指紋情報記憶手段と，
前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する2次元累積スコア記憶手段と，
前記登録指紋情報記憶手段から読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶手段から読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算手段と，
前記登録指紋情報記憶手段から読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶手段から読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の位置差を計算するトレース点間の位置差計算手段と，
前記トレース点間の位置差計算手段が計算したトレース点間の位置差を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算手段と，
前記2次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する累積スコア計算手段と，
前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間の位置差計算手段によるトレース点間の位置差計算，前記照合スコア計算手段による照合スコア計算，及び前記累積スコア計算手段による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
指紋照合システム。
【請求項１２】
前記“登録指紋の特徴情報”及び前記“入力指紋の特徴情報”は，
分岐点であるか端点であるかを識別するための特異点のタイプに関する情報，
特異点がいくつのトレース点を含むかに関するトレース点数に関する情報，
特異点の始点の水平位置に関する情報である水平座標Ｘに関する情報，
特異点の始点の垂直位置に関する情報である垂直座標Ｙに関する情報，
特異点の始点での水平軸に対する隆線方向の角度θに関する情報，
特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１に関する情報，
第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２に関する情報，及び，
第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３に関する情報，
を含む３２ビットの情報である
請求項１１に記載の指紋照合システム。
【請求項１３】
第１の回転角についての前記照合スコア計算手段による照合スコア計算工程が行われる間に，第2の回転角についての前記トレース点間の位置差計算手段によるトレース点間の位置差計算工程が行われ，
前記第1の回転角についての前記累積スコア計算手段による累積スコア計算工程の間に，前記第2の回転角についての照合スコア計算工程が行われると共に，第3の回転角についてのトレース点間の位置差計算工程が行われ，
以後も同様にして並列処理を行うように，各処理の工程時間を調整する工程時間調整手段を具備する
請求項1に記載の指紋照合システム。
【請求項１４】
前記トレース点間の位置差計算手段は，
前記入力指紋又は前記登録指紋の一方の特異点について，
特異点の始点の水平位置に関する情報であるＸ，
特異点の始点の垂直位置に関する情報であるＹ，
特異点の始点での水平軸に対する隆線方向の角度θ，
特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１，
第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２，及び，
第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３，とし，
前記入力指紋又は前記登録指紋の残りの特異点について，
特異点の始点の水平位置に関する情報であるＸ’，
特異点の始点の垂直位置に関する情報であるＹ’，
特異点の始点での水平軸に対する隆線方向の角度θ’，
特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１’，
第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２’，及び，
第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３’，とした場合に，
θ及びθ’が入力され，入力されたθ及びθ’を用いてΔθに相当するθ−θ’を求めて出力する第1の減算器(161)と，
φ１及びφ１’ が入力され，入力されたφ１及びφ１’を用いてΔφ１に相当するφ１−φ１’を求めて出力する第2の減算器(162)と，
φ２及びφ２’ が入力され，入力されたφ２及びφ２’を用いてΔφ２に相当するφ２−φ２’を求めて出力する第3の減算器(163)と，
φ３及びφ３’ が入力され，入力されたφ３及びφ３’を用いてΔφ３に相当するφ３−φ３’を求めて出力する第4の減算器(164)と，
前記第1の減算器(161)からの出力であるΔθと前記第2の減算器(162)からの出力であるΔφ１とが入力され，入力されたΔθ及びΔφ１を用いてΔθ＋Δφ１を求めて出力する第1の加算器(165)と，
前記第1の減算器(161)からの出力であるΔθと前記第1の加算器(165）からの出力であるΔθ＋Δφ１とが入力され，入力されたΔθ及びΔθ＋Δφ１を用いて２Δθ＋Δφ１を求めて出力する第2の加算器(166)と，
前記第1の加算器(165）からの出力であるΔθ＋Δφ１と前記第3の減算器(163)からの出力であるΔφ２とが入力され，入力されたΔθ＋Δφ１及びΔφ２を用いてΔθ＋Δφ１＋Δφ２を求めて出力する第3の加算器(167)と，
前記第1の減算器(161)からの出力であるΔθが入力され，入力されたΔθを記憶するための第1のレジスタ(168)と，
第2の加算器(166)からの出力である２Δθ＋Δφ１が入力され，入力された２Δθ＋Δφ１を記憶するための第2のレジスタ(169)と，
第3の加算器(167)からの出力であるΔθ＋Δφ１＋Δφ２が入力され，入力されたΔθ＋Δφ１＋Δφ２を記憶するための第3のレジスタ(170)と，
前記第4の減算器(164)からの出力であるΔφ３が入力され，入力されたΔφ３を記憶するための第4のレジスタ(171)と，
前記第2のレジスタ(169)が記憶した２Δθ＋Δφ１と前記第3のレジスタ(170)が記憶したΔθ＋Δφ１＋Δφ２とが入力され，入力された２Δθ＋Δφ１及びΔθ＋Δφ１＋Δφ２を用いて３Δθ＋２Δφ１＋Δφ２を求めて出力する第4の加算器(172)と，
前記第3のレジスタ(170)が記憶したΔθ＋Δφ１＋Δφ２と前記第4のレジスタ(171)が記憶したΔφ３とが入力され，入力されたΔθ＋Δφ１＋Δφ２及びΔφ３を用いて，Δθ＋Δφ１＋Δφ２＋Δφ３を求めて出力する第5の加算器(173)と，
前記第4の加算器(172)からの出力である３Δθ＋２Δφ１＋Δφ２と前記第5の加算器(173)からの出力であるΔθ＋Δφ１＋Δφ２＋Δφ３とが入力され，入力された３Δθ＋２Δφ１＋Δφ２及びΔθ＋Δφ１＋Δφ２＋Δφ３を用いて４Δθ＋３Δφ１＋２Δφ２＋Δφ３を求めて出力する第6の加算器(174)と，
前記第1のレジスタ(168)からの出力であるΔθが入力され，入力されたΔθを記憶するための第5のレジスタ(175)と，
前記第2のレジスタ(169)からの出力である２Δθ＋Δφ１が入力され，入力された２Δθ＋Δφ１を記憶するための第6のレジスタ(176)と，
前記第4の加算器(172)からの出力である３Δθ＋２Δφ１＋Δφ２が入力され，入力された３Δθ＋２Δφ１＋Δφ２を記憶するための第7のレジスタ(177)と，
前記第6の加算器(174)からの出力である４Δθ＋３Δφ１＋２Δφ２＋Δφ３が入力され，入力された４Δθ＋３Δφ１＋２Δφ２＋Δφ３を記憶するための第8のレジスタ(178)と，
を具備する，
請求項３に記載の指紋照合システム。
【請求項１５】
前記照合スコア計算手段は，
前記第５のレジスタ(175)，前記第6のレジスタ(176)，前記第7のレジスタ(177)及び前記第8のレジスタ(178)に記憶された各トレース点間の位置差から，各トレース点間の距離を求める絶対値算出部と,前記絶対値算出部で算出された各トレース点間距離の総和を求めるトレース点間距離の総和算出部と，及び前記トレース点間距離の総和算出部で算出されたトレース点間距離の総和を用いて照合スコアを算出する照合スコア算出部とを具備し，
前記絶対値算出部は，
前記第5のレジスタ（175）に格納されたΔθが入力され，入力値の絶対値である｜Δθ｜を求め，出力する第1の絶対値回路(181)と，
前記第6のレジスタ(176)に格納された２Δθ＋Δφ１が入力され，入力値の絶対値である｜２Δθ＋Δφ１｜を求め，出力する第2の絶対値回路(182)と，
前記第7のレジスタ(177)に格納された３Δθ＋２Δφ１＋Δφ２が入力され，入力値の絶対値である｜３Δθ＋２Δφ１＋Δφ２｜を求め，出力する第3の絶対値回路(183)と，
前記第8のレジスタ(178)に格納された４Δθ＋３Δφ１＋２Δφ２＋Δφ３が入力され，入力値の絶対値である｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め，出力する第4の絶対値回路(184)と，
を具備し，    
前記トレース点間距離の総和算出部は，
前記第1の絶対値回路(181)及び前記第2の絶対値回路(182)で求められた｜Δθ｜及び｜２Δθ＋Δφ１｜がそれぞれ入力され，入力された前記｜Δθ｜及び前記｜２Δθ＋Δφ１｜を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜を求め出力する第7の加算器(185)と，
前記第3の絶対値回路(183)，及び前記第4の絶対値回路(184)で求められた｜３Δθ＋２Δφ１＋Δφ２｜及び｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜がそれぞれ入力され，入力された前記｜３Δθ＋２Δφ１＋Δφ２｜及び前記｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を加算して，｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め出力する第8の加算器(186)と，
前記第7の加算器(185)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜と，前記第8の加算器(186)が出力した｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜とが入力され，入力された前記（｜Δθ｜＋｜２Δθ＋Δφ１｜）及び前記（｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜）を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求めて出力する第9の加算器（187）と，
前記第9の加算器(187)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜が入力され，入力されたトレース点間距離の総和Ｄｔｒａｃｅである前記｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を記憶する第9のレジスタ(188)と，
を具備し，
照合スコア算出部は，
特異点のトレース点の数であるトレース点の数Ｎｔｒａｃｅが入力されると，前記Ｎｔｒａｃｅに所定の係数を乗じた値であるトレース点間個数関連値を出力するトレース点間個数関連値出力部(190)と，
前記第9のレジスタ(188)に格納されたトレース点間距離の総和Ｄｔｒａｃｅ及びトレース点間個数関連値出力部(190)から出力されるトレース点間個数関連値が入力され，これらの入力値の減算演算を行う第5の減算器(189)と，
前記第5の減算器(189)の演算結果が入力され，入力された値である照合スコアを記憶する第10のレジスタ(191)とを具備する
請求項４に記載の指紋照合システム。
【請求項１６】
登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む“登録指紋の特徴情報”を記憶する登録指紋情報記憶手段と，
入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む“入力指紋の特徴情報”を記憶する入力指紋情報記憶手段と，
前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する水平位置差用の1次元累積スコア記憶手段と，
前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の垂直位置差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する垂直位置差用の1次元累積スコア記憶手段と，
前記登録指紋情報記憶手段から読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶手段から読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算手段と，
前記登録指紋情報記憶手段から読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶手段から読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の位置差を計算するトレース点間の位置差計算手段と，
前記トレース点間の位置差計算手段が計算したトレース点間の位置差を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算手段と，
前記水平位置差用の１次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する水平位置差用の累積スコア計算手段と，
前記垂直位置差用の１次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する垂直位置差用の累積スコア計算手段と，
を具備し，
前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間距離計算手段によるトレース点間距離計算，前記照合スコア計算手段による照合スコア計算，及び前記累積スコア計算手段による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
指紋照合システム。
【請求項１７】
請求項１１に記載の指紋照合システムをローカル検索システムとして，請求項１６に記載の指紋照合システムをグローバル検索システムとして具備する指紋照合システムであって，
前記グローバル検索システムは，
最終照合スコアを与える前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差と垂直位置差を，前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差と垂直位置差の概略値として出力する概略値出力手段を具備し，
前記ローカル検索システムは，
前記グローバル検索システムから出力された水平位置差と垂直位置差の概略値を受取る概略値受信手段と，
前記概略値受信手段が受取った概略値から所定の量変動する範囲を前記概略値の周辺範囲として求める概略値の周辺範囲計算手段と，
前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差が前記周辺範囲に含まれるかどうか判断する特異点位置差判定手段と，
前記特異点位置差判定手段が前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差が前記周辺範囲に含まれると判断した場合にのみ，前記照合スコアを計算するように制御する照合スコア演算制御手段と，
を具備する， 
指紋照合システム。
【請求項１８】
前記２次元累積スコア記憶手段は，前記概略値の周辺範囲に対応したアドレスを有する，
請求項１７に記載の指紋照合システム。
【請求項１９】
登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む登録指紋の特徴情報を記憶する登録指紋情報記憶データベースと，
入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む入力指紋の特徴情報を記憶する入力指紋情報記憶データベースと，
前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する2次元累積スコアメモリと，
前記登録指紋情報記憶データベースから読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶データベースから読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算回路と，
前記登録指紋情報記憶データベースから読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶データベースから読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の位置差を計算するトレース点間の位置差計算回路と，
前記トレース点間の位置差計算回路が計算したトレース点間の位置差を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算回路と，
前記2次元累積スコアメモリのうち，前記特異点位置差計算回路が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算回路が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する累積スコア計算回路と，
前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間の位置差計算回路によるトレース点間の位置差計算，前記照合スコア計算回路による照合スコア計算，及び前記累積スコア計算回路による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
ハードウェアにより実装された指紋照合システム。
【請求項２０】
第１の回転角についての前記照合スコア計算回路による照合スコア計算工程が行われる間に，第2の回転角についての前記トレース点間の位置差計算回路によるトレース点間の位置差計算工程が行われ，
前記第1の回転角についての前記累積スコア計算回路による累積スコア計算工程の間に，前記第2の回転角についての照合スコア計算工程が行われると共に，第3の回転角についてのトレース点間の位置差計算工程が行われ，
以後も同様にして並列処理を行い，前記トレース点間の位置差計算工程，前記照合スコア計算工程，及び前記累積スコア計算工程が同一周期となるように，各処理の工程時間を調整する工程時間調整回路を具備する
請求項1９に記載の指紋照合システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，指紋照合のための指紋照合システムなどに関する。より詳しく説明すると，本発明は，実際に実装できる指紋照合システムや，登録指紋と，入力指紋の位置の差と回転量の差を求める際に，まずそれらの概略値を求め，その後に詳細な移動量の差と回転量の差とを求めることにより，小メモリ化を達成した指紋照合のための指紋照合システムなどに関する。
【背景技術】
【０００２】
指紋照合システムは，人間の持つ指紋がそれぞれ異なることを利用して個人を識別するシステムである。指紋照合システムは，より詳しく説明すると，センサなどの指紋読み取り手段で，照合者の指紋情報を読み取り，予め登録され，加工された指紋情報と，読み取った指紋情報とを照合することにより個人認識を行うシステムである。
【０００３】
例えば，特開2005-149353号公報（特許文献１）には，指紋照合システムが開示されている。図１は，特開2005-149353号公報に開示された指紋照合システムの例を示す図である。図１に示すように，この指紋照合システムは，指紋センサ(1)と，前処理部(2)と，特徴抽出部(3)と，複数個のテンプレート(4)を記憶するデータベース部(5)と，テンプレートを用いて登録指紋と照合のために入力された指紋との照合を行う照合部(6)と，照合部で行われた照合結果を出力する外部表示部(7)とを具備する。
【０００４】
この公報に開示された指紋照合システムは，登録指紋と入力指紋との位置及び回転のずれを二段階補正して，位置及び回転を補正した後に登録指紋の特異点と入力指紋の特異点とから類似度を測定し，登録指紋の所有者と，入力指紋の所有者が同一人であるかどうか判定するものである。しかしながら，このシステムを実装するための具体的な回路構成は必ずしも明らかではない。
【０００５】
従来の指紋照合システムのために，様々な回路からなる指紋照合システムが開発されたが，指紋の特徴情報を正確に照合するためには，上記のような様々な補正などを施さなければならなかった。このため，指紋照合システムに大きな作業メモリを必要とするという問題があった。
【０００６】
【特許文献１】特開2005-149353号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は，指紋照合システムのための具体的なブロック構成や回路図を提供することを目的とする。
【０００８】
本発明は，指紋の照合を，大きな作業メモリを必要とせずにハードウェアにより実装できるブロック構成や回路図を提供することを目的とする。
【０００９】
本発明は，従来の指紋照合システムに比べて，少ない手数で指紋照合を達成できる指紋照合システムを提供することを目的とする。
【００１０】
本発明は，指紋を迅速に精度よく照合でき，作業メモリが少なくて済む指紋照合システムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は，基本的には，登録指紋と入力指紋との特異点をトレースするとともに，特異点対の位置差に応じたメモリ番地に照合スコアを累積して記憶させることで，登録指紋と入力指紋との位置及び回転のずれを把握し，適切な指紋対スコアを得て，指紋照合を行うシステムに関する。さらに本発明の好ましい態様では，大まかな検索を行うグローバル検索を行って位置及び回転のずれを大まかに把握して，それらの周辺について詳細な検索を行うローカル検索を行うことにより，メモリコストを抑えることができるとともに，指紋照合の正確さや速度が高まるという知見に基づく。
【００１２】
本発明の第１の側面は，
Ａ．  登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む“登録指紋の特徴情報”を記憶する登録指紋情報記憶手段と，
Ｂ．  入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む“入力指紋の特徴情報”を記憶する入力指紋情報記憶手段と，
Ｃ．  前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する2次元累積スコア記憶手段と，
Ｄ．  前記登録指紋情報記憶手段から読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶手段から読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算手段と，
Ｅ．  前記登録指紋情報記憶手段から読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶手段から読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の距離を計算するトレース点間距離計算手段と，
Ｆ．  前記トレース点間距離計算手段が計算したトレース点間の距離を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算手段と，
Ｇ．  前記2次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する累積スコア計算手段と，
を具備し，
Ｈ．  前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間距離計算手段によるトレース点間距離計算，前記照合スコア計算手段による照合スコア計算，及び前記累積スコア計算手段による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
Ｉ．  指紋照合システムに関する。
【００１３】
上記の指紋照合システムは，好ましくは１：Ｎ指紋照合システムとして用いることができる。「１：Ｎ指紋照合システム」とは，入力されたひとつの指紋と，登録されたＮ個（Ｎは整数）との照合を行うための指紋照合システムを意味する。Ｎは，１であってもよいが，好ましくは２以上１×１０７以下の整数である。
【００１４】
図２は，特異点を説明するための図である。図２（ａ）は分岐点(10)，図２（ｂ）は端点(11)を特異点の始点とする指紋の一部を示す図である。なお，図２（ｃ）は，特異点を含む指紋を表す図面に代わる写真である。指紋における「特異点」とは，指紋において図２に示されるような分岐点(10)や端点(11)を含む部位である。なお，分岐点(10)有する特異点については，例えば，Ｙ字型のうち一本道となっている方を特異点として認識するものが好ましい。
【００１５】
「各特異点を所定距離ごとに所定数トレースして得られる」トレース点における所定距離Ｄは，指紋の大きさを考慮して，指紋照合においてふさわしい値を適宜採用できる。具体的な「所定距離」として，１ｍｍ，１×１０−１ｍｍ，１×１０ｍｍなど，１×１０−１ｍｍ以上１×１０ｍｍ以下の値があげられる。「所定数」ｍも１以上の任意の整数があげられる。トレースする数が少ないと正確さが小さくなり，トレース数が多いと計算が多くなり多くのメモリを必要とするほか処理に時間がかかる。本発明では，正確さと，メモリコストを抑え，処理時間を高速にすることを目的のひとつとするので，「所定数」として２個以上１０個以下があげられ，３個以上５個以下が好ましい。
【００１６】
「指紋のトレース角」とは，例えば，図５（ｂ）に描画されるように，端点や分岐点については，端点又は分岐点などの始点と第１のトレース点とを結んでできる線分と，水平方向とのなす角θ，上記線分と，第１のトレース点と第２のトレース点を結んでできる線分とのなす角φ１，以後，第（ｎ−１）番目のトレース点とｎ番目のトレース点を結んでできる線分と，第ｎ番目のトレース点と（ｎ＋１）番目のトレース点を結んでできる線分とのなす角φｎがあげられる。ただし，ｎは，ｍをトレースする数として（ｍ−１）以下の整数があげられる。
【００１７】
「登録指紋情報記憶手段」と「入力指紋情報記憶手段」とは，一つのデータベースを構築していても良いし，別のデータベースであっても良い。また，「登録指紋情報記憶手段」は，入力指紋を得る指紋センサ等とは別のサーバに設けられており，適宜ダウンロードされるものであっても良い。また，「登録指紋情報記憶手段」と「入力指紋情報記憶手段」には，特徴情報の他に，特異点に関する情報が適宜記憶されていても良い。「特異点に関する情報」とは，基本的には，特異点の始点位置などの特異点の位置に関する情報，及び特異点を含む指紋画像情報などがあげられる。その他，特異点の整理番号や，登録指紋の指紋保持者のＩＤ，特異点の整理番号などの情報，又は求められた各トレース点とそのトレース点と関連したトレース角に関する情報が含まれていてもよい。
【００１８】
「特異点対についてのトレース点間の距離」は，照合スコアを算出しようとする特異点対について，それぞれの端点又は分岐点などの始点を同じ位置になるようにした場合における，登録指紋の特異点における第ｎ番目のトレース点と，入力指紋の特異点における第ｎ番目のトレース点との距離を意味する。例えば，図８に示される各対応するトレース間の距離があげられる。図８における具体的な「特異点対についてのトレース点間の距離」は，線分（51，61）の長さｄ１，線分（52，62）の長さｄ２，線分（53，63）の長さｄ３，及び線分（54，64）の長さｄ４である。
【００１９】
「照合スコアを計算する」とは，「特異点対についてのトレース点間の距離」の総和が小さいほど特異点対が一致する可能性が高いので，好ましくは所定の設定値から前記総和を減算するなど，総和が小さいほど照合スコアが高くなるように設定するものである。所定の設定値は，トレースする数や所定距離Ｄなどに応じて適宜修正すればよい。
【００２０】
「特異点対の位置差」は，例えば，特異点対における端点又は分岐点などの始点同士の位置の差があげられる。その他，特異点のうちトレースされた部位の重心同士など，登録指紋の特異点と入力指紋の特異点の対応する任意の点同士の座標差であってもよい。これらは，“登録指紋の特異点の位置情報”と“入力指紋の特異点の位置情報”とから，減算器を用いるなどして容易に求めることができる。
【００２１】
2次元累積スコア記憶手段前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差に対応したアドレスは，2次元メモリ番地ともよばれるものである。２次元メモリ番地は，ｘ座標及びｙ座標が所定の範囲内にあるものを所定の区画に含まれる情報として記憶する記憶装置における仮想的な記録位置を意味する。例えば，メモリが１０×１０個の領域を有する場合であり，入力された指紋が１×１０２×１×１０２ピクセルであれば縦横１０ピクセル合計１００ピクセルごとに，ひとつのメモリ番地とするものがあげられる。そして，例えば，位置のずれが，横（ｘ）２５ピクセル，縦−３２ピクセルであれば，ｘ方向に＋３番目ｙ方向に−４番目の記録番地に情報を記録すればよい。
【００２２】
「所定角度回転」における所定角度は，これが大きければ照合精度が低くなり，これが小さければ処理に大きなメモリコストや処理時間を要することとなる。そこで，所定角度として，５度以上２０度以下があげられる。より好ましい回転角として，３６０度を整数で割って得られる角度（ｎｒを正の整数として，３６０度をｎｒで割った角度）があげられる。様々な角度を用いて実際に研究を進めた結果，所定角度として１１．２５度を採用し，３１回回転させるものが最も好ましいことがわかった。なお，この場合，回転角が０度のものも合わせると，３２通りの最大照合スコアを求めることとなる。
【００２３】
次に，上記のシステムの動作例について説明する。例えばデータベースとして構成される指紋情報記憶手段は，登録指紋に含まれる各特異点について“登録指紋の特異点の位置情報”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む情報を記憶する。登録指紋については，図１に示されるように，指紋センサ１を用いてシステムに指紋情報を入力し，前処理部(2)で２値化，及び細線化などの処理を施し，従来のものとは改良した特徴抽出部(3)よって，特異点の位置情報やトレース角を求め，テンプレート(4)としてデータベース(5)に記憶すればよい。この動作は，入力指紋についても同様である。
【００２４】
トレース点間距離計算手段では，指紋センサ１で入力され，前処理部(2)などで所定の処理が施された指紋情報から“入力指紋の特異点の位置情報”を含む“特異点に関する情報”を抽出する。その特異点に関する情報には，端点又は分岐点を含む特異点に関する情報が含まれているので，それら特異点について，始点から所定距離にある点を第１のトレース点とし，次に第１のトレース点と所定の距離にある始点以外の点を第２の点とするような作業を所定回数繰返して，各トレース点を得る。その後，公知の角度計算回路を用いてトレース角を求める。このようにして，“入力指紋のトレース角”が求められ，例えば，特異点の整理番号，及びトレース点の番号と関連して“入力指紋のトレース角”が記憶される。
【００２５】
次に，照合スコアを求めようとしている特異点対について，“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”の差を求める。具体的には，各特異点について，始点位置のみならず，各トレース点のトレース点の番号と関連してトレース角が記憶されているので，登録指紋のある特異点の第ｎ番目のトレース点におけるトレース角の値から，入力指紋のある特異点の第ｎ番目のトレース点におけるトレース角の値を，減算することで，“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”の差を求める。そして，トレース点間距離は，図８に示されるような式で求めることができるので，予め記憶した係数である２，３，及び４などの整数と，それぞれのトレース角の差に関する情報を用いて，例えば加算器，乗算器，及び絶対値回路を具備する装置により，トレース点間の位置差及びトレース点間距離（例えば，ｄ１，ｄ２，ｄ３，及びｄ４）を求めることができる。
【００２６】
次に，例えば，加算器を用いることにより，トレース点間距離の総和を求めることができる（トレース点間距離の総和の例は，ｄ１+ｄ２+ｄ３+ｄ４である）。そして，例えば，予め設定値を記憶しておくとともに，前記したトレース点間距離の総和の符号を符号転換装置で逆符号とし，前記設定値と，逆符号となった総和を加算器で加算することにより照合スコアを求めることができる。このようにすれば，トレース点間距離の総和に基づいて，照合スコアを計算できる。
【００２７】
上記工程の先でも後でも構わないが，特異点対の２次元座標差を求める。具体的には，前記照合スコア計算手段が照合スコアを計算した（又は計算する）特異点対について，前記“登録指紋の特異点の位置情報”と前記“入力指紋の特異点の位置情報”とから，前記特異点対の２次元座標差を求める。具体的には，例えば，特異点対の始点同士の座標差を求めればよい。この作業は，ｘ座標同士，及びｙ座標同士を減算することで求めることができる。
【００２８】
記憶装置には，座標差に対応した２次元メモリ番地が設けられている。ｘ座標差が，所定の範囲であれば，２次元メモリ番地のあるｘ座標番地に相当し，ｙ座標差が所定の範囲であれば，２次元メモリ番地のあるｙ座標番地に相当する。このようにして，得られた2次元座標差を量子化して２次元メモリ番地を特定する。その特定された２次元メモリ番地に，先に説明した照合スコアを記憶する。ただし，その２次元メモリ番地に，既に照合スコアが記憶されている場合には，既に記憶されている値と新たに求められた照合スコアとを加算して，累積された照合スコアを求め，更新する。このようにして累積スコアが更新される。上記の作業を前記登録指紋に含まれる全ての特異点及び前記入力指紋に含まれる全ての特異点の組合せである全ての特異点対について繰返し，求められた前記照合スコアを対応する２次元メモリ番地に累積的に加算して記憶する。
【００２９】
次に，２次元累積スコア計算手段が記憶する累積された照合スコアのうち最大のものである最大照合スコアを抽出し，記憶する。
【００３０】
これまで説明した一連の作業を，前記入力指紋の指紋情報を所定角度回転させて得られる回転後の“入力指紋の特異点に関する情報”についても行い，それぞれの回転角度における最大照合スコアを抽出し，記憶する。例えば，１１．２５度ずらして最大照合スコアを求めるとともに，回転角の情報と関連させて記憶する。
【００３１】
次に，求められた回転量ごとの最大照合スコアの中で最大のものを指紋対スコアとして求める。その後，前記指紋対スコアを用いて指紋照合を行う。例えば，指紋対スコアが最大のものを本人として判定してもよい。また，指紋対スコアが最大のものが，所定のしきい値以上だった場合に，その指紋対スコアを与えた登録指紋の持ち主を本人として判定してもよい。さらに，Ｎが１の場合は，指紋対スコアが所定の値以上である場合に，本人であるとして判定してもよい。
【００３２】
本発明の第１の側面の好ましい態様は，前記“登録指紋の特徴情報”及び前記“入力指紋の特徴情報”は，分岐点であるか端点であるかを識別するための特異点のタイプに関する情報，特異点がいくつのトレース点を含むかに関するトレース点数に関する情報，特異点の始点の水平位置に関する情報である水平座標Ｘに関する情報，特異点の始点の垂直位置に関する情報である垂直座標Ｙに関する情報，特異点の始点での水平軸に対する隆線方向の角度θに関する情報，特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１に関する情報，第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２に関する情報，及び，第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３に関する情報，を含む３２ビットの情報である上記に記載の指紋照合システムに関する。
【００３３】
特異点に関する情報を32ビット形式のテンプレートとしたので，迅速かつ十分な指紋照合を行うことができる。すなわち，指紋照合を行うに当たり，特異点をどのように求めるかは，またどの程度の容量とするかは，慎重に設計しなければならない事項である。この態様では，トレース点角を，特異点の始点に関する角度θと，第３のトレース点における角度まで（φ１，φ２，φ３）として，更に32ビットにまとめたので，迅速かつ十分な指紋照合を行うことができることとなった。
【００３４】
本発明の第１の側面の好ましい態様は，第１の回転角についての前記照合スコア計算手段による照合スコア計算工程が行われる間に，第2の回転角についての前記トレース点間距離計算手段によるトレース点間距離計算工程が行われ，前記第1の回転角についての前記累積スコア計算手段による累積スコア計算工程の間に，前記第2の回転角についての照合スコア計算工程が行われると共に，第3の回転角についてのトレース点間距離計算工程が行われ，以後も同様にして並列処理を行うように，各処理の工程時間を調整する工程時間調整手段を具備する上記いずれかに記載の指紋照合システムである。
【００３５】
このように並列処理を行うので，効率よく指紋照合を行うことができることとなる。
【００３６】
本発明の第１の側面の好ましい態様は，前記トレース点間距離計算手段は，前記入力指紋又は前記登録指紋の一方の特異点について，特異点の始点の水平位置に関する情報であるＸ，特異点の始点の垂直位置に関する情報であるＹ，特異点の始点での水平軸に対する隆線方向の角度θ，特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１，第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２，及び，第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３，とし，前記入力指紋又は前記登録指紋の残りの特異点について，特異点の始点の水平位置に関する情報であるＸ’，特異点の始点の垂直位置に関する情報であるＹ’，特異点の始点での水平軸に対する隆線方向の角度θ’，特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１’，第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２’，及び，第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３’，とした場合に，θ及びθ’が入力され，入力されたθ及びθ’を用いてΔθに相当するθ−θ’を求めて出力する第1の減算器(161)と，φ１及びφ１’が入力され，入力されたφ１及びφ１’を用いてΔφ１に相当するφ１−φ１’を求めて出力する第2の減算器(162)と，φ２及びφ２’が入力され，入力されたφ２及びφ２’を用いてΔφ２に相当するφ２−φ２’を求めて出力する第3の減算器(163)と，φ３及びφ３’が入力され，入力されたφ３及びφ３’を用いてΔφ３に相当するφ３−φ３’を求めて出力する第4の減算器(164)と，前記第1の減算器(161)からの出力であるΔθと前記第2の減算器(162)からの出力であるΔφ１とが入力され，入力されたΔθ及びΔφ１を用いてΔθ＋Δφ１を求めて出力する第1の加算器(165)と，前記第1の減算器(161)からの出力であるΔθと前記第1の加算器(165）からの出力であるΔθ＋Δφ１とが入力され，入力されたΔθ及びΔθ＋Δφ１を用いて２Δθ＋Δφ１を求めて出力する第2の加算器(166)と，前記第1の加算器(165）からの出力であるΔθ＋Δφ１と前記第3の減算器(163)からの出力であるΔφ２とが入力され，入力されたΔθ＋Δφ１及びΔφ２を用いてΔθ＋Δφ１＋Δφ２を求めて出力する第3の加算器(167)と，前記第1の減算器(161)からの出力であるΔθが入力され，入力されたΔθを記憶するための第1のレジスタ(168)と，第2の加算器(166)からの出力である２Δθ＋Δφ１が入力され，入力された２Δθ＋Δφ１を記憶するための第2のレジスタ(169)と，第3の加算器(167)からの出力であるΔθ＋Δφ１＋Δφ２が入力され，入力されたΔθ＋Δφ１＋Δφ２を記憶するための第3のレジスタ(170)と，前記第4の減算器(164)からの出力���あるΔφ３が入力され，入力されたΔφ３を記憶するための第4のレジスタ(171)と，前記第2のレジスタ(169)が記憶した２Δθ＋Δφ１と前記第3のレジスタ(170)が記憶したΔθ＋Δφ１＋Δφ２とが入力され，入力された２Δθ＋Δφ１及びΔθ＋Δφ１＋Δφ２を用いて３Δθ＋２Δφ１＋Δφ２を求めて出力する第4の加算器(172)と，前記第3のレジスタ(170)が記憶したΔθ＋Δφ１＋Δφ２と前記第4のレジスタ(171)が記憶したΔφ３とが入力され，入力されたΔθ＋Δφ１＋Δφ２及びΔφ３を用いて，Δθ＋Δφ１＋Δφ２＋Δφ３を求めて出力する第5の加算器(173)と，前記第4の加算器(172)からの出力である３Δθ＋２Δφ１＋Δφ２と前記第5の加算器(173)からの出力であるΔθ＋Δφ１＋Δφ２＋Δφ３とが入力され，入力された３Δθ＋２Δφ１＋Δφ２及びΔθ＋Δφ１＋Δφ２＋Δφ３を用いて４Δθ＋３Δφ１＋２Δφ２＋Δφ３を求めて出力する第6の加算器(174)と，前記第1のレジスタ(168)からの出力であるΔθが入力され，入力されたΔθを記憶するための第5のレジスタ(175)と，前記第2のレジスタ(169)からの出力である２Δθ＋Δφ１が入力され，入力された２Δθ＋Δφ１を記憶するための第6のレジスタ(176)と，前記第4の加算器(172)からの出力である３Δθ＋２Δφ１＋Δφ２が入力され，入力された３Δθ＋２Δφ１＋Δφ２を記憶するための第7のレジスタ(177)と，前記第6の加算器(174)からの出力である４Δθ＋３Δφ１＋２Δφ２＋Δφ３が入力され，入力された４Δθ＋３Δφ１＋２Δφ２＋Δφ３を記憶するための第8のレジスタ(178)と，前記第5のレジスタ（175）に格納されたΔθが入力され，入力値の絶対値である｜Δθ｜を求め，出力する第1の絶対値回路(181)と，前記第6のレジスタ(176)に格納された２Δθ＋Δφ１が入力され，入力値の絶対値である｜２Δθ＋Δφ１｜を求め，出力する第2の絶対値回路(182)と，前記第7のレジスタ(177)に格納された３Δθ＋２Δφ１＋Δφ２が入力され，入力値の絶対値である｜３Δθ＋２Δφ１＋Δφ２｜を求め，出力する第3の絶対値回路(183)と，前記第8のレジスタ(178)に格納された４Δθ＋３Δφ１＋２Δφ２＋Δφ３が入力され，入力値の絶対値である｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め，出力する第4の絶対値回路(184)と，を含む絶対値算出部と，を具備する，上記いずれかに記載の指紋照合システムに関する。
【００３７】
実際にシステムを実装する際には，具体的な回路を設計し，適切な処理を行うことができるようにすることが望まれる。上記の回路であれば，周期的に各工程の動作を行うことができるので，並列処理を行うことができる。これにより，効率的に演算処理を行うことができることとなる。
【００３８】
本発明の第１の側面の好ましい態様は，前記照合スコア計算手段は，前記絶対値算出部で算出された各トレース点間距離の総和を求めるトレース点間距離の総和算出部と，及び前記トレース点間距離の総和算出部で算出されたトレース点間距離の総和を用いて照合スコアを算出する照合スコア算出部とを具備し，前記トレース点間距離の総和算出部は，前記第1の絶対値回路(181)及び前記第2の絶対値回路(182)で求められた｜Δθ｜及び｜２Δθ＋Δφ１｜がそれぞれ入力され，入力された前記｜Δθ｜及び前記｜２Δθ＋Δφ１｜を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜を求め出力する第7の加算器(185)と，前記第3の絶対値回路(183)，及び前記第4の絶対値回路(184)で求められた｜３Δθ＋２Δφ１＋Δφ２｜及び｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜がそれぞれ入力され，入力された前記｜３Δθ＋２Δφ１＋Δφ２｜及び前記｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を加算して，｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め出力する第8の加算器(186)と，前記第7の加算器(185)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜と，前記第8の加算器(186)が出力した｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜とが入力され，入力された前記（｜Δθ｜＋｜２Δθ＋Δφ１｜）及び前記（｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜）を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求めて出力する第9の加算器（187）と，前記第9の加算器(187)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜が入力され，入力されたトレース点間距離の総和Ｄｔｒａｃｅである前記｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を記憶する第9のレジスタ(188)と，を具備し，照合スコア算出部は，特異点のトレース点の数であるトレース点の数Ｎｔｒａｃｅが入力されると，前記Ｎｔｒａｃｅに所定の係数を乗じた値であるトレース点間個数関連値を出力するトレース点間個数関連値出力部(190)と，前記第9のレジスタ(188)に格納されたトレース点間距離の総和Ｄｔｒａｃｅ及びトレース点間個数関連値出力部(190)から出力されるトレース点間個数関連値が入力され，これらの入力値の減算演算を行う第5の減算器(189)と，前記第5の減算器(189)の演算結果が入力され，入力された値である照合スコアを記憶する第10のレジスタ(191)とを具備する上記いずれかに記載の指紋照合システムに関する。
【００３９】
実際にシステムを実装する際には，具体的な回路を設計し，適切な処理を行うことができるようにすることが望まれる。上記の回路であれば，周期的に各工程の動作を行うことができるので，並列処理を行うことができる。これにより，効率的に演算処理を行うことができることとなる。
【００４０】
本発明の第２の側面は，
Ａ．登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む“登録指紋の特徴情報”を記憶する登録指紋情報記憶手段と，
Ｂ．入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む“入力指紋の特徴情報”を記憶する入力指紋情報記憶手段と，
Ｃ’−１．前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する水平位置差用の1次元累積スコア記憶手段と，
Ｃ’−２．前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の垂直位置差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する垂直位置差用の1次元累積スコア記憶手段と，
Ｄ．前記登録指紋情報記憶手段から読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶手段から読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算手段と，
Ｅ．前記登録指紋情報記憶手段から読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶手段から読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の距離を計算するトレース点間距離計算手段と，
Ｆ．前記トレース点間距離計算手段が計算したトレース点間の距離を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算手段と，
Ｇ’−１.前記水平位置差用の１次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する水平位置差用の累積スコア計算手段と，
Ｇ’−２．前記垂直位置差用の１次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する垂直位置差用の累積スコア計算手段と，
を具備し，
Ｈ．前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間距離計算手段によるトレース点間距離計算，前記照合スコア計算手段による照合スコア計算，及び前記累積スコア計算手段による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
Ｉ．指紋照合システムに関する。
【００４１】
この側面に係る指紋照合システムは，少ないメモリを用いて指紋照合を行うことができる。ただし，2次元累積メモリの代わりに1次元累積メモリを用いているので，精度はそれほど高くない可能性がある。そこで，第2の側面に係る指紋照合システムは，おおよその“めぼし”をつけるシステムとして効果的に利用されうる。なお，第2の側面に係る指紋照合システムも，上記した第1の側面に係る指紋照合システムにおける好ましい態様のものを適宜取り入れることができる。
【００４２】
本発明の第３の側面は，第１の側面に係るいずれかの指紋照合システムをローカル検索システムとして，前記第２の側面に係る指紋照合システムをグローバル検索システムとして具備する指紋照合システムであって，前記グローバル検索システムは，最終照合スコアを与える前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差と垂直位置差を，前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差と垂直位置差の概略値として出力する概略値出力手段を具備し，前記ローカル検索システムは，前記グローバル検索システムから出力された水平位置差と垂直位置差の概略値を受取る概略値受信手段と，前記概略値受信手段が受取った概略値から所定の量変動する範囲を前記概略値の周辺範囲として求める概略値の周辺範囲計算手段と，前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差が前記周辺範囲に含まれるかどうか判断する特異点位置差判定手段と，前記特異点位置差判定手段が前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差が前記周辺範囲に含まれると判断した場合にのみ，前記照合スコアを計算するように制御する照合スコア演算制御手段と，を具備する，指紋照合システムである。
【００４３】
グローバル検索を行って概略値を求めた後に，詳細な検索であるローカル検索を行うので，小さなメモリを用いて極めて精度よくしかも迅速に指紋照合を行うことができることとなる。しかも，上記した並列処理を用いれば，無駄なく指紋照合を行うことができることとなる。
【００４４】
本発明の第３の側面の好ましい態様は，前記２次元累積スコア記憶手段は，前記概略値の周辺範囲に対応したアドレスを有する，上記に記載の指紋照合システムである。
【００４５】
２次元累積スコア記憶手段が，特異点対の位置差全体ではなく，前記概略値の周辺範囲に対応したアドレスを有するので，少ないメモリを用いても，極めて詳細なアドレスを設定することができ，指紋照合の精度が高まることとなる。
【００４６】
本発明の第４の側面は，コンピュータを，
Ａ．登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む“登録指紋の特徴情報”を記憶する登録指紋情報記憶手段と，
Ｂ．入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む“入力指紋の特徴情報”を記憶する入力指紋情報記憶手段と，
Ｃ．前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する2次元累積スコア記憶手段と，
Ｄ．前記登録指紋情報記憶手段から読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶手段から読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算手段と，
Ｅ．前記登録指紋情報記憶手段から読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶手段から読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の距離を計算するトレース点間距離計算手段と，
Ｆ．前記トレース点間距離計算手段が計算したトレース点間の距離を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算手段と，
Ｇ．前記2次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する累積スコア計算手段と，
を具備し，
Ｈ．前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間距離計算手段によるトレース点間距離計算，前記照合スコア計算手段による照合スコア計算，及び前記累積スコア計算手段による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
Ｉ．ように機能させる指紋照合システム用プログラムに関する。
【００４７】
本発明の第５の側面は，上記のプログラムを記憶したコンピュータ読取可能な情報記録媒体に関する。
【００４８】
本発明の第６の側面は，
Ａ．登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む登録指紋の特徴情報を記憶する登録指紋情報記憶手段と，
Ｂ．入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む入力指紋の特徴情報を記憶する入力指紋情報記憶手段と，
Ｃ．前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する2次元累積スコア記憶手段と，
Ｄ．前記登録指紋情報記憶手段から読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶手段から読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算手段と，
Ｅ”．前記登録指紋情報記憶手段から読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶手段から読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の位置差を計算するトレース点間の位置差計算手段と，
Ｆ”．前記トレース点間の位置差計算手段が計算したトレース点間の位置差を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算手段と，
Ｇ．前記2次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する累積スコア計算手段と，
Ｈ．前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間の位置差計算手段によるトレース点間の位置差計算，前記照合スコア計算手段による照合スコア計算，及び前記累積スコア計算手段による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
Ｉ．指紋照合システムに関する。
【００４９】
本発明の第６の側面の好ましい態様は，
前記“登録指紋の特徴情報”及び前記“入力指紋の特徴情報”は，
分岐点であるか端点であるかを識別するための特異点のタイプに関する情報，
特異点がいくつのトレース点を含むかに関するトレース点数に関する情報，
特異点の始点の水平位置に関する情報である水平座標Ｘに関する情報，
特異点の始点の垂直位置に関する情報である垂直座標Ｙに関する情報，
特異点の始点での水平軸に対する隆線方向の角度θに関する情報，
特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１に関する情報，
第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２に関する情報，及び，
第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３に関する情報，
を含む３２ビットの情報である
上記いずれかに記載の指紋照合システムに関する。
【００５０】
本発明の第６の側面の好ましい態様は，第１の回転角についての前記照合スコア計算手段による照合スコア計算工程が行われる間に，第2の回転角についての前記トレース点間の位置差計算手段によるトレース点間の位置差計算工程が行われ，前記第1の回転角についての前記累積スコア計算手段による累積スコア計算工程の間に，前記第2の回転角についての照合スコア計算工程が行われると共に，第3の回転角についてのトレース点間の位置差計算工程が行われ，以後も同様にして並列処理を行うように，各処理の工程時間を調整する工程時間調整手段を具備する
上記いずれかに記載の指紋照合システムに関する。
【００５１】
本発明の第６の側面の好ましい態様は，前記トレース点間の位置差計算手段は，前記入力指紋又は前記登録指紋の一方の特異点について，特異点の始点の水平位置に関する情報であるＸ，特異点の始点の垂直位置に関する情報であるＹ，特異点の始点での水平軸に対する隆線方向の角度θ，特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１，第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２，及び，第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３，とし，前記入力指紋又は前記登録指紋の残りの特異点について，特異点の始点の水平位置に関する情報であるＸ’，特異点の始点の垂直位置に関する情報であるＹ’，特異点の始点での水平軸に対する隆線方向の角度θ’，特異点の始点と第１のトレース点とを結ぶ線分と，第１のトレース点と第２のトレース点とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１’，第１のトレース点と第２のトレース点とを結ぶ線分と，第２のトレース点と第３のトレース点とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２’，及び，第２のトレース点と第３のトレース点とを結ぶ線分と，第３のトレース点と第４のトレース点とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３’，とした場合に，θ及びθ’が入力され，入力されたθ及びθ’を用いてΔθに相当するθ−θ’を求めて出力する第1の減算器(161)と，φ１及びφ１’が入力され，入力されたφ１及びφ１’を用いてΔφ１に相当するφ１−φ１’を求めて出力する第2の減算器(162)と，φ２及びφ２’が入力され，入力されたφ２及びφ２’を用いてΔφ２に相当するφ２−φ２’を求めて出力する第3の減算器(163)と，φ３及びφ３’が入力され，入力されたφ３及びφ３’を用いてΔφ３に相当するφ３−φ３’を求めて出力する第4の減算器(164)と，前記第1の減算器(161)からの出力であるΔθと前記第2の減算器(162)からの出力であるΔφ１とが入力され，入力されたΔθ及びΔφ１を用いてΔθ＋Δφ１を求めて出力する第1の加算器(165)と，前記第1の減算器(161)からの出力であるΔθと前記第1の加算器(165）からの出力であるΔθ＋Δφ１とが入力され，入力されたΔθ及びΔθ＋Δφ１を用いて２Δθ＋Δφ１を求めて出力する第2の加算器(166)と，前記第1の加算器(165）からの出力であるΔθ＋Δφ１と前記第3の減算器(163)からの出力であるΔφ２とが入力され，入力されたΔθ＋Δφ１及びΔφ２を用いてΔθ＋Δφ１＋Δφ２を求めて出力する第3の加算器(167)と，前記第1の減算器(161)からの出力であるΔθが入力され，入力されたΔθを記憶するための第1のレジスタ(168)と，第2の加算器(166)からの出力である２Δθ＋Δφ１が入力され，入力された２Δθ＋Δφ１を記憶するための第2のレジスタ(169)と，第3の加算器(167)からの出力であるΔθ＋Δφ１＋Δφ２が入力され，入力されたΔθ＋Δφ１＋Δφ２を記憶するための第3のレジスタ(170)と，前記第4の減算器(164)からの���力であるΔφ３が入力され，入力されたΔφ３を記憶するための第4のレジスタ(171)と，前記第2のレジスタ(169)が記憶した２Δθ＋Δφ１と前記第3のレジスタ(170)が記憶したΔθ＋Δφ１＋Δφ２とが入力され，入力された２Δθ＋Δφ１及びΔθ＋Δφ１＋Δφ２を用いて３Δθ＋２Δφ１＋Δφ２を求めて出力する第4の加算器(172)と，前記第3のレジスタ(170)が記憶したΔθ＋Δφ１＋Δφ２と前記第4のレジスタ(171)が記憶したΔφ３とが入力され，入力されたΔθ＋Δφ１＋Δφ２及びΔφ３を用いて，Δθ＋Δφ１＋Δφ２＋Δφ３を求めて出力する第5の加算器(173)と，前記第4の加算器(172)からの出力である３Δθ＋２Δφ１＋Δφ２と前記第5の加算器(173)からの出力であるΔθ＋Δφ１＋Δφ２＋Δφ３とが入力され，入力された３Δθ＋２Δφ１＋Δφ２及びΔθ＋Δφ１＋Δφ２＋Δφ３を用いて４Δθ＋３Δφ１＋２Δφ２＋Δφ３を求めて出力する第6の加算器(165)と，前記第1のレジスタ(168)からの出力であるΔθが入力され，入力されたΔθを記憶するための第5のレジスタ(175)と，前記第2のレジスタ(169)からの出力である２Δθ＋Δφ１が入力され，入力された２Δθ＋Δφ１を記憶するための第6のレジスタ(176)と，前記第4の加算器(172)からの出力である３Δθ＋２Δφ１＋Δφ２が入力され，入力された３Δθ＋２Δφ１＋Δφ２を記憶するための第7のレジスタ(177)と，前記第6の加算器(174)からの出力である４Δθ＋３Δφ１＋２Δφ２＋Δφ３が入力され，入力された４Δθ＋３Δφ１＋２Δφ２＋Δφ３を記憶するための第8のレジスタ(178)と，を具備する，上記いずれかに記載の指紋照合システムに関する。
【００５２】
本発明の第６の側面の好ましい態様は，前記照合スコア計算手段は，前記第５のレジスタ(175)，前記第6のレジスタ(176)，前記第7のレジスタ(177)及び前記第8のレジスタ(178)に記憶された各トレース点間の位置差から，各トレース点間の距離を求める絶対値算出部と,前記絶対値算出部で算出された各トレース点間距離の総和を求めるトレース点間距離の総和算出部と，及び前記トレース点間距離の総和算出部で算出されたトレース点間距離の総和を用いて照合スコアを算出する照合スコア算出部とを具備し，前記絶対値算出部は，前記第5のレジスタ（175）に格納されたΔθが入力され，入力値の絶対値である｜Δθ｜を求め，出力する第1の絶対値回路(181)と，前記第6のレジスタ(176)に格納された２Δθ＋Δφ１が入力され，入力値の絶対値である｜２Δθ＋Δφ１｜を求め，出力する第2の絶対値回路(182)と，前記第7のレジスタ(177)に格納された３Δθ＋２Δφ１＋Δφ２が入力され，入力値の絶対値である｜３Δθ＋２Δφ１＋Δφ２｜を求め，出力する第3の絶対値回路(183)と，前記第8のレジスタ(178)に格納された４Δθ＋３Δφ１＋２Δφ２＋Δφ３が入力され，入力値の絶対値である｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め，出力する第4の絶対値回路(184)と，を具備し，前記トレース点間距離の総和算出部は，前記第1の絶対値回路(181)及び前記第2の絶対値回路(182)で求められた｜Δθ｜及び｜２Δθ＋Δφ１｜がそれぞれ入力され，入力された前記｜Δθ｜及び前記｜２Δθ＋Δφ１｜を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜を求め出力する第7の加算器(185)と，前記第3の絶対値回路(183)，及び前記第4の絶対値回路(184)で求められた｜３Δθ＋２Δφ１＋Δφ２｜及び｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜がそれぞれ入力され，入力された前記｜３Δθ＋２Δφ１＋Δφ２｜及び前記｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を加算して，｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め出力する第8の加算器(186)と，前記第7の加算器(185)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜と，前記第8の加算器(186)が出力した｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜とが入力され，入力された前記（｜Δθ｜＋｜２Δθ＋Δφ１｜）及び前記（｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜）を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求めて出力する第9の加算器（187）と，前記第9の加算器(187)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜が入力され，入力されたトレース点間距離の総和Ｄｔｒａｃｅである前記｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を記憶する第9のレジスタ(188)と，を具備し，照合スコア算出部は，特異点のトレース点の数であるトレース点の数Ｎｔｒａｃｅが入力されると，前記Ｎｔｒａｃｅに所定の係数を乗じた値であるトレース点間個数関連値を出力するトレース点間個数関連値出力部(190)と，前記第9のレジスタ(188)に格納されたトレース点間距離の総和Ｄｔｒａｃｅ及びトレース点間個数関連値出力部(190)から出力されるトレース点間個数関連値が入力され，これらの入力値の減算演算を行う第5の減算器(189)と，前記第5の減算���(189)の演算結果が入力され，入力された値である照合スコアを記憶する第10のレジスタ(191)とを具備する上記いずれかに記載の指紋照合システムに関する。
【００５３】
本発明の第７の側面は，
Ａ．登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む“登録指紋の特徴情報”を記憶する登録指紋情報記憶手段と，
Ｂ．入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む“入力指紋の特徴情報”を記憶する入力指紋情報記憶手段と，
Ｃ’−１．前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する水平位置差用の1次元累積スコア記憶手段と，
Ｃ’−２．前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の垂直位置差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する垂直位置差用の1次元累積スコア記憶手段と，
Ｄ．前記登録指紋情報記憶手段から読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶手段から読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算手段と，
Ｅ”．前記登録指紋情報記憶手段から読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶手段から読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の位置差を計算するトレース点間の位置差計算手段と，
Ｆ”．前記トレース点間の位置差計算手段が計算したトレース点間の位置差を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算手段と，
Ｇ’−１．前記水平位置差用の１次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する水平位置差用の累積スコア計算手段と，
Ｇ’−２．前記垂直位置差用の１次元累積スコア記憶手段のうち，前記特異点位置差計算手段が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算手段が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する垂直位置差用の累積スコア計算手段と，
を具備し，
Ｈ．前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間距離計算手段によるトレース点間距離計算，前記照合スコア計算手段による照合スコア計算，及び前記累積スコア計算手段による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
上記いずれかに記載の指紋照合システムに関する。
【００５４】
本発明の第８の側面は，本発明の第７の側面に係る指紋照合システムをローカル検索システムとして，本発明の第６の側面に係る指紋照合システムとグローバル検索システムとして具備する指紋照合システムであって，前記グローバル検索システムは，最終照合スコアを与える前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差と垂直位置差を，前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の水平位置差と垂直位置差の概略値として出力する概略値出力手段を具備し，前記ローカル検索システムは，前記グローバル検索システムから出力された水平位置差と垂直位置差の概略値を受取る概略値受信手段と，前記概略値受信手段が受取った概略値から所定の量変動する範囲を前記概略値の周辺範囲として求める概略値の周辺範囲計算手段と，前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差が前記周辺範囲に含まれるかどうか判断する特異点位置差判定手段と，前記特異点位置差判定手段が前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差が前記周辺範囲に含まれると判断した場合にのみ，前記照合スコアを計算するように制御する照合スコア演算制御手段と，を具備する，指紋照合システムに関する。
【００５５】
本発明の第８の側面の好ましい態様は，前記２次元累積スコア記憶手段は，前記概略値の周辺範囲に対応したアドレスを有する，上記いずれかに記載の指紋照合システムに関する。
【００５６】
本発明の第９の側面は，
Ａ．登録指紋に含まれる各特異点について“登録指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる登録指紋の各トレース点についての“登録指紋のトレース角”を含む登録指紋の特徴情報を記憶する登録指紋情報記憶データベースと，
Ｂ．入力指紋に含まれる各特異点について“入力指紋の特異点の位置”，及び各特異点を所定距離ごとに所定数トレースして得られる入力指紋の各トレース点についての“入力指紋のトレース角”を含む入力指紋の特徴情報を記憶する入力指紋情報記憶データベースと，
Ｃ．前記“登録指紋の特異点の位置”と前記“入力指紋の特異点の位置”の差に対応したアドレスを有し，照合スコアを，累積スコアとして累積的に蓄積する2次元累積スコアメモリと，
Ｄ．前記登録指紋情報記憶データベースから読み出された“登録指紋の特異点の位置”及び前記入力指紋情報記憶データベースから読み出された“入力指紋の特異点の位置”が入力され，前記“登録指紋の特異点の位置”と，それに対応する前記“入力指紋の特異点の位置”とを用いて，照合される特異点対の位置差を計算する特異点位置差計算回路と，
Ｅ”．前記登録指紋情報記憶データベースから読み出された“登録指紋のトレース角”及び前記入力指紋情報記憶データベースから読み出された“入力指紋のトレース角”が入力され，前記“登録指紋のトレース角”と，それに対応する前記“入力指紋のトレース角”とを用いて，照合される特異点対についてのトレース点間の位置差を計算するトレース点間の位置差計算回路と，
Ｆ”．前記トレース点間の位置差計算回路が計算したトレース点間の位置差を用いて，照合される特異点対についての照合スコアを計算する照合スコア計算回路と，
Ｇ．前記2次元累積スコアメモリのうち，前記特異点位置差計算回路が算出した照合される特異点対の位置差に対応するアドレスに記憶される前記累積スコアが入力され，前記照合スコア計算回路が計算した照合スコアと前記累積スコアとを加算して新たな累積スコアを計算する累積スコア計算回路と，
Ｈ．前記登録指紋又は入力指紋のうちいずれかを所定角度回転させて得られる“登録指紋の特徴情報”及び“入力指紋の特徴情報”を用いて，前記トレース点間の位置差計算回路によるトレース点間の位置差計算，前記照合スコア計算回路による照合スコア計算，及び前記累積スコア計算回路による累積スコア計算を，複数の回転角について繰り返し行い，得られた累積スコアのうち最大の値を最終照合スコアとして用いて，照合される特異点対の照合を行う，
Ｉ．ハードウェアにより実装された指紋照合システムに関する。
【００５７】
本発明の第９の側面の好ましい態様は，第１の回転角についての前記照合スコア計算回路による照合スコア計算工程が行われる間に，第2の回転角についての前記トレース点間の位置差計算回路によるトレース点間の位置差計算工程が行われ，前記第1の回転角についての前記累積スコア計算回路による累積スコア計算工程の間に，前記第2の回転角についての照合スコア計算工程が行われると共に，第3の回転角についてのトレース点間の位置差計算工程が行われ，以後も同様にして並列処理を行い，前記トレース点間の位置差計算工程，前記照合スコア計算工程，及び前記累積スコア計算工程が同一周期となるように，各処理の工程時間を調整する工程時間調整回路を具備する上記いずれかに記載の指紋照合システムに関する。
【００５８】
なお，上記のシステムは，四則演算など，ハードウェア処理により実装できるものは，ハードウェアにより実装されることが好ましい。また，処理の修正は，プログラマブルロジック回路などを用いて，適宜修正を行ってもよい。一方，所定のアルゴリズムを実行するためには，その様なアルゴリズムを実現するプログラムをメインメモリなどに格納しておき，ＣＰＵなどの制御部が所定の情報を受取ると，メインメモリなどに格納されたプログラムを読み出して，読み出したプログラムに従って，所定の情報をメモリなどから読み出して所定の演算を行うようにしてもよい。
【発明の効果】
【００５９】
本発明の指紋照合システムは，登録指紋と，入力指紋の移動量の差と回転量の差を求める際に，まずそれらの概略値を求め，その後に詳細な移動量の差と回転量の差とを求める効果的かつこれまでにないアルゴリズムに基づくために，従来に比べ少ないメモリで精度の高い指紋照合を達成できる。
【００６０】
また，本発明の指紋照合システムは，登録指紋と，入力指紋の移動量の差と回転量の差を求める際に，まずそれらの概略値を求め，その後に詳細な移動量の差と回転量の差とを求めるための効果的なアルゴリズムに基づく回路を具備するために，従来に比べ迅速に精度の高い指紋照合を達成できる。
【００６１】
本発明の指紋照合システムは，上記のような指紋照合システムを具備するので，指紋を迅速に精度よく照合でき，作業メモリが少なくて済む。
【００６２】
本発明の指紋照合システムは，所定の前処理を施し，上記のような指紋照合システムを具備するので，複数の登録指紋画像に繰り返し適用することにより１：Ｎの指紋照合システムを提供することができる。
【発明を実施するための最良の形態】
【００６３】
（１．指紋照合システムの概要）
本発明の指紋照合システムは，基本的には，従来の指紋照合システムを改良したものである。よって，以下，図１を用いて指紋照合システムの基本動作例を説明する。指紋照合は，登録と照合の２つの工程からなる。指紋情報を登録する場合は，指紋を指紋センサ(1)に読み取らせる。指紋センサ(1)が読み取った指紋情報は，特異点を抽出される前に前処理部(2)において，所定の前処理が施される。例えば，指紋情報は，Ａ／Ｄ変換回路でデジタル情報に変換され，フィルタ回路でノイズを減らされ，二値化回路で二値化され，細線化回路で細線化される。特徴抽出部(3)が，前処理を施された指紋情報から，隆線の分岐点や端点などの特徴情報である特徴情報を抽出する。抽出された特徴情報は，テンプレート(4)として，指紋照合システム内のデータベース部(5)に記憶される。
【００６４】
先に説明した特異点は，図２を参照することにより理解できる。図２（ａ）は分岐点(10)，図２（ｂ）は端点(11)を特異点の始点とする指紋の一部を示す図である。なお，図２（ｃ）は，特異点を含む指紋を表す図面に代わる写真である。図２（ｃ）に示されるように，指紋は，隆線と呼ばれる様々なパターンで流れる隆起したラインと，隆線の間の谷間とからなる。分岐点(10)は，Ｙ接合部において，隆線がひとつの経路から２つの経路に分かれる特異点である。一方，端点(11)は，端点において隆線が終る特異点である。
【００６５】
指紋の照合を行う場合は，先に説明した登録工程と同様に指紋を指紋センサ(1)に読み取らせる。指紋センサ(1)が読み取った指紋情報は，特異点を抽出される前に前処理部(2)において，所定の前処理が施される。例えば，指紋情報は，Ａ／Ｄ変換回路でデジタル情報に変換され，フィルタ回路でノイズを減らされ，二値化回路で二値化され，細線化回路で細線化される。特徴抽出部(3)が，前処理を施された指紋情報から，分岐点(10)や端点(11)などの特異点に関する特徴情報を抽出する。
【００６６】
図３は，指紋照合の各過程における指紋画像を示す図面に代わる写真である。図3(a)は，原画像を示し，図3(b)は2値化画像を示し，図3(c)は細線化画像を示す。照合部(6)は，照合のために入力された指紋の特徴情報（In）と，予め登録された指紋の特徴情報（Tem）とを照合し，照合結果を出力する。
【００６７】
図４は，照合の工程例を示す図である。なお，図中Ｓはステップを意味する。図４を用いて，特異点照合工程を含む指紋照合システム全体について説明する。本発明の指紋照合システムは，例えば，以下の工程により指紋照合を行う。すなわち，グレーレベル画像取得工程（ステップ１）と，予備ろ過工程（ステップ２）と，第一の二値化工程（ステップ３）と，方向検出工程（ステップ４）と，グレーレベル画像の方向フィルタ工程（ステップ５）と，第二の二値化工程（ステップ６）と，細線化工程（ステップ７）と，特異点抽出工程（ステップ８）と，特異点照合工程（ステップ９）を含む。図４には，各部分の画像の中で(a)原画像と(b)第二の二値化工程画像と(c)細線化工程画像を示している。
【００６８】
（１．１  画像処理工程）
グレーレベル画像取得工程では，指紋センサが指紋を読み取ることにより，指紋のグレーレベル画像を取得する。予備ろ過工程では，指紋センサにより読み込まれ，Ａ／Ｄ変換回路がデジタル情報に変換したグレーレベルの指紋画像からノイズを取り除く。第一の二値化工程では，二値化回路が，前記予備ろ過工程で，ノイズが除去されたグレーレベル画像を，所定の閾値を基準として，黒（「０」）と白（「１」）の二値に変換する処理を行う。方向検出工程では，二値化画像のブロックから隆線の最大方向などを計算する。グレーレベル画像の方向フィルタ工程は，上記の方向検出で検出された最大方向に従って，方向フィルタをマスキングすることにより，グレーレベル画像のノイズを軽減する。第二の二値化工程は，二値化回路が，例えば，グレーレベル画像の方向フィルタ工程などを経てノイズが軽減されたグレーレベル画像を，所定の閾値を基準として，黒（「０」）と白（「１」）の二値に変換する処理を行う工程である。二値化により指紋画像を強調することは，ノイズを減らすことや，隆線を鮮明にすることになる。細線化工程では，細線化回路が，第二の二値化工程で得られた二値化画像を細線化する処理を行う工程である。このようにして細線化処理を施すことで，指紋の隆線パターンの骨格が明確になる。特異点抽出工程は，例えば，細線化された二値化画像から，特異点に関する特徴情報を抽出する工程である。特徴抽出部(4)が，指紋画像から，図２（ａ）に示されるような分岐点(10)や，図２（ｂ）に示されるような端点(11)を検索する。
【００６９】
（１．２  特異点照合工程）
特異点照合工程は，登録指紋の特徴情報と，入力指紋の特徴情報を用いて，登録指紋と入力指紋の位置・回転の相違を補正し，補正後の登録指紋と入力指紋の類似度を計算し，登録指紋の所有者と入力指紋の所有者が同一人かどうか判定する工程である。特異点照合工程は，例えば，特異点パラメータ計算工程と最終照合スコア計算工程を含む。
【００７０】
（１．２．１．特異点パラメータ計算工程）
図５は，パラメータを説明するための図である。図5(a)は，特異点と特異点上に設定されたトレース点を示す図である。図5(b)は特異点と特異点上に設定されたトレース点により形成される角を示す図である。図５（a）に示されるように，パラメータ計算工程では，特異点を始点として特定された距離Ｄにある隆線上の点を次々にトレース点(22，23，24，25)に選定する。これは，特異点の隆線形状を，隣接するトレース点を接続する線分（21-22，22-23，23-24，及び24-25）で表現することを意味している。ここで，特異点の始点(21)での水平軸に対する隆線方向の角度θ，線分（21-22）と線分（22-23）のなす角度φ１，線分（22-23）と線分（23-24）のなす角度φ２，線分（23-24）と線分（24-25）のなす角度φ３とすると，図５（ｂ）に示されるように，特徴抽出部(3)が特異点の端の始点(21)の位置（Ｘ，Ｙ），θ及び各線分のなす角（φ１，φ２，φ３）を計算する。定義にしたがって，これらの角度は正負の符号をもつ。図５（ｂ）に示される特異点の始点位置及び各トレース点におけるトレース角度に関する特徴情報（ＭＳ）は，例えば，次式のようにパラメータ化できる。このパラメータにより表現されたものが，各特異点のテンプレートである。特徴情報（ＭＳ）：ｓ＝（Ｘ，Ｙ，θ，φ１，φ２，φ３）
【００７１】
（１．２．２．指紋対照合スコア計算工程）
図６は，特異点の位置シフトと回転を説明するための図である。図6に示されるように，登録指紋画像は，入力指紋画像をある基準点についてある回転角だけ回転させ，ある方向へシフトしたものと考えられる。この回転角とシフトは登録指紋画像毎に異なり，これを補正して初めて両指紋画像の類似度を判定することができる。例えば，この補正操作は，以下のように行ってもよい。
【００７２】
１）対象とする回転角について位置補正を考慮した類似度をすべて求め，その最大値を与える回転角を解とする。図６に示すようにある特異点（Ｘ，Ｙ，θ）と別の特異点（Ｘ’，Ｙ’，θ’）が，照合される特異点対であるとき，位置差（ΔＸ＝Ｘ−Ｘ’，ΔＹ＝Ｙ−Ｙ’）だけ移動し，特異点を（Δθ＝θ−θ‘）回転移動した点（Ｘ”，Ｙ”）は以下のようにして計算できる。
Ｘ”＝Ｘ’cos（Δθ）−Ｙ’sin（Δθ）＋ΔＸ
Ｙ”＝Ｘ’sin（Δθ）＋Ｙ’cos（Δθ）＋ΔＹ
なお，特異点を平行移動や，回転移動しても，特徴情報のうち，（φ１，φ２，φ３）は，不変である。したがって，これらの角度情報から，類似度を求めることもできる。
【００７３】
２）次に，登録指紋と入力指紋の特異点のすべての組み合わせについて，位置差と特異点対照合スコアを求め，位置差ごとに特異点対照合スコアを累積していき，最終的に最大の累積特異点対照合スコアを二つの指紋画像の指紋対照合スコアとしてもよい。
【００７４】
（２．特異点フォーマットと類似スコア）
前述のように特異点抽出工程では，特異点に関する特徴情報（ＭＳ）は，例えば，次式のようにパラメータ化できる。特徴情報：ｓ＝（Ｘ，Ｙ，θ，φ１，φ２，φ３）。図７は，本発明の一実施態様に係る特異点フォーマットを説明する図である。すなわち，この態様では，入力指紋及び登録指紋は，図７に示されるような形式のデータ情報に変換された後，比較される。図７に示すフォーマットは，３２ビット形式のものであり，入力指紋及び登録指紋を，分岐点であるか端点であるかを識別するための特異点のタイプに関する情報（１ビット），いくつのトレース点を含むかに関する形状角数に関する情報（２ビット），特異点の始点の水平位置に関する情報である水平座標Ｘに関する情報（６ビット），特異点の始点の垂直位置に関する情報である垂直座標Ｙに関する情報（５ビット），特異点の始点(21)での水平軸に対する隆線方向の角度θに関する情報（５ビット），特異点の始点(21)と第１のトレース点(22)とを結ぶ線分と，第１のトレース点(22)と第２のトレース点(23)とを結ぶ線分とがなす角をφ１とした場合，前記φ１に関する隆線形状角φ１に関する情報（４ビット），第１のトレース点(22)と第２のトレース点(23)とを結ぶ線分と，第２のトレース点(23)と第３のトレース点(24)とを結ぶ線分とがなす角をφ２とした場合，前記φ２に関する隆線形状角φ２に関する情報（４ビット），及び，第２のトレース点(23)と第３のトレース点(24)とを結ぶ線分と，第３のトレース点(24)と第４のトレース点(25)とを結ぶ線分とがなす角をφ３とした場合，前記φ３に関する隆線形状角φ３に関する情報（４ビット），を含む情報に変換する。なお，図７中“１”は，任意要素としての識別子である。本発明では，入力指紋及び登録指紋をそれぞれ３２ビット形式のものとしたので，後述するサイクルにより連続的に演算することができた。なお，トレース点の数に関する情報が3の場合は，φ１，φ２，及びφ３として数値が記憶される。一方，例えばトレース点の数に関する情報が2の場合は，例えば照合スコア計算においてφ３に関する演算が行われないようにすればよい。
【００７５】
なお，テンプレートのフォーマットは，図7に示すものに限定されない。例えば，トレース点の数が3個以下（例えば，1個又は2個）であっても良いし，トレース点の数が4個以上（例えば，4個，又は5個）であってもよい。さらに，φ１，φ２，及びφ３のそれぞれに比べて，θの情報量を多くしても良い。これは，後述するトレース点間距離計算において，θに係る係数が，φ１，φ２，及びφ３のそれぞれに比べて大きいからである。同様の理由で，φ１，φ２，及びφ３の順に情報量を同じか小さくなるようにしてもよい。このようにすることで，少ないメモリを用いて，精度の高い指紋照合を行うことができる。
【００７６】
図８は，本発明のトレース点間距離を説明するための図である。即ち特異点の隆線形状は，特異点の位置と回転角には依存しない。図８では，特異点およびその隆線形状を１つの特異点の特徴情報（ＭＳ）：ｓ＝（Ｘ，Ｙ，θ，φ１，φ２，φ３）と他の特異点の特徴情報（ＭＳ）：ｓ’＝（Ｘ’，Ｙ’，θ’，φ１’，φ２’，φ３’）とすれば，隆線形状の類似度は，二つの特異点の始点が重なるよう移動シフトし，特異点を除く他のトレース点間の距離を利用して類似度とすることができる。図８に示すように，2つの特異点の始点を符号50の位置にあわせ，残りのトレース点を（51，52，53，54）及び（61，62，63，64）とすると，トレース点間距離ｄ１（51，61），ｄ２（52，62），ｄ３(53，63)，ｄ４（54，64）の総和をもって，特異点対の類似度を計算することもできる。簡単な計算により，それぞれの値は，
ｄ１（51，61）の距離＝Ｄ｜Δθ｜，
ｄ２（52，62）の距離＝Ｄ｜２Δθ＋Δφ１｜，
ｄ３（53，63）の距離＝Ｄ｜３Δθ＋２Δφ１＋Δφ２｜，
ｄ４（54，64）の距離＝Ｄ｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜，
で求めることができる。ただし，Δθ＝θ−θ’，Δφ１＝φ１−φ１’，Δφ２＝φ２−φ２’，Δφ３＝φ３−φ３’，である。これよりトレース点間距離の総和Ｄｔｒａｃｅは，共通のトレース点選定のための距離Ｄを省いてＤｔｒａｃｅ＝｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜として求められる。また，特異点毎にトレース点の数は０の場合も，１つの場合も，２つの場合も，３つの場合もある。そこで，特異点対の照合スコアScoreは，例えば，Score＝５×Ｎｔｒａｃｅ−Ｄｔｒａｃｅの計算式により得ることができる。ただし，Ｎｔｒａｃｅは特異点のトレース点の個数で，例えば２，３，又は４などの値を取る。Ｎｔｒａｃｅは，特異点を除いた個数が通常の値であるが，特異点が指紋画像の端にある場合にはＮｔｒａｃｅ＝３または２とするものが好ましい。
【００７７】
（３．指紋照合工程の計算アルゴリズム）
図９は，指紋の特異点の位置，回転量，隆線形状を特異点として利用する指紋照合工程の処理フローの例を示す図である。図９に示されるように，指紋照合システムは，累積スコア計算が全ての回転角について行われたかどうかを判断する(71)。全ての回転角について累積スコア計算が行われていない場合，全ての特異点対について累積スコア計算が行われたかどうかを判断する(72)。全ての特異点対について累積スコア計算が行われていない場合，次の順番の特異点対についてトレース点間距離計算が行われる(73)。続いて，トレース点間距離を用いてトレース点間距離の総和を求め，この値を用いて特異点対の照合スコアを計算する(74)。その後，その特異点対の位置差に相当する2次元メモリ番地に，求めた照合スコアを累積して加算する。そして，その加算した値と，以前に算出した最大累積スコアとを比較し，以前に算出した最大累積スコアよりも，今回得られた累積スコアが大きい場合は，累積スコアを更新する(75)。累積スコア計算が終わると，全ての特異点について累積スコア計算が行われたかが判断する（72）。そして，全ての特異点対について累積スコア計算が行われている場合，全ての回転角について累積スコア計算が行われているか判断する(71)。そして，全ての回転角について累積スコア計算が行われている場合は，最大照合スコアを与える指紋対照合スコアを求める(77)。すべての組み合わせについて，特異点対の照合スコアと累積スコアの計算を行うと，その中の最大累積スコアが自動的に保存される。ある回転角についての最大累積スコアを，特定されたすべての回転角について求め，その中の最大値をもって指紋対照合スコア（最大照合スコア）とする(77)。最大値を与える回転角と位置差が，２つの指紋の回転と位置の相違点又はその近傍であると推定できる。
【００７８】
図10は，２次元累積スコアの位置差による分布例を示すグラフである。図９に示される例は，任意の特異点の組み合わせについて，その特異点の位置差に対応してスコアを累積したもので，同じ指紋の登録指紋と入力指紋の場合は，同一の位置差のメモリに得点のピークが現れる。
【００７９】
（４．指紋照合工程回路）
図11は，指紋照合工程の計算アルゴリズムを実現する回路の例を示すブロック図である。図11に示されるように，この回路（装置）は，入力指紋の特徴情報を記憶する記憶回路(81)と，登録指紋の特徴情報を記憶する記憶回路(82)と，指紋照合エンジン回路（83）と指紋対照合スコア回路（84）と制御回路(85)とを具備する。制御回路の制御信号により，記憶回路(81)及び記憶回路(82)から，入力指紋の特徴情報及び登録指紋の特徴情報とが読み出され，指紋照合エンジン回路(83)へと伝えられる。制御回路(85)は，指紋照合エンジン回路(83)を駆動し，所定量ずつずれた回転角ごとの照合スコアが指紋対照合スコア回路(84)に送られる。指紋対照合スコア回路(84)では，回転角ごとの照合スコアを比較し，最大のスコアを特定された閾値と比較することにより，照合結果の最終的な結果とする。
【００８０】
（５．指紋照合エンジン回路）
図12は，本発明の指紋照合エンジン回路(83)の例を示すブロック図である。図12に示されるように，指紋照合エンジンは，回転角をある値に固定し，特異点毎に，トレース点間距離（Sim(ti,sj)）を計算するトレース点間距離計算回路(91)と，トレース点間距離計算回路が算出したトレース点間距離を用いて照合スコア（Score(ti,sj)）を算出する照合スコア計算回路(92)と，特異点対の始点差に相当するアドレスに記憶される累積スコア（ACC_score（ΔＸ，ΔＹ））と照合スコアとを用いて新たな累積スコアを求める2次元累積スコア計算回路(93)とを具備する。この２次元累積スコア計算のために，指紋照合エンジンは，特異点の始点間の位置差及びそれに対応する累積スコアメモリにおけるアドレスなどを求める累積スコアメモリアドレス計算回路（94）と，照合スコアを累積的に記憶する２次元累積スコアメモリ(95)とを具備する。
【００８１】
図13は，図12のハードウェア回路の動作タイミングを示すタイムチャートである。図13に示されるように，本発明の装置は，好ましくはシステム周期で繰り返し動作している。そして，各システム周期は第１クロックと第２クロックから成り立っている。登録指紋データ入力１，登録指紋データ入力２，累積スコアメモリアドレス計算，トレース点間距離計算，（照合）スコア計算，累積スコア計算がそれぞれ１システム周期（第１クロック，第２クロック）で実行され，灰色のブロックで示すように登録指紋データ入力に対応して逐次的に実行される。そして，好ましくは，各ブロックは実行を終了すると次の登録指紋データに対する処理の実行を行うパイプライン処理になっている。このパイプライン処理によって，１つの登録入力データの処理が４システム周期，すなわち８クロックの時間を要するが，多数の登録入力データに対して次々に実行することにより，１システム周期毎につぎつぎと照合結果が得られる。
【００８２】
なお，各入力及び計算等の周期は若干ずれて他の周期内に行われても良い。例えば，トレース点間距離計算が，照合スコア計算期間の第1クロックにおいても行われても良い。また，トレース点間距離計算の代わりに，トレース点間の位置差が求められてもよい。具体的には，第１システム周期で，登録指紋のある特異点の特徴情報が読み出され，演算回路に入力されるとともに，入力指紋のある特異点の特徴情報が読み出され，演算回路に入力される。次のシステム周期では，入力された特徴情報をもとに，始点の位置差（ΔＸ，ΔＹ）が求められ，累積スコアメモリのどのアドレスに累積スコアが格納されるかが求められる。この累積スコアメモリアドレス計算と並行して，トレース点間の位置差が求められる。このトレース点間の位置差の絶対値がトレース点間距離である。そして，次のシステム周期では，求められたトレース点間距離を用いて，照合スコアが算出される。そして，次のシステム周期では，先の累積スコアメモリアドレス計算により求められたアドレスに，照合スコアが累積的に記憶される。
【００８３】
すなわち，入力指紋の特異点情報は前述のデータフォーマットに従って指紋対照合スコア計算回路に入力されている。登録指紋の特異点は１システム周期でデータフォーマット１とデータフォーマット２が１クロック毎に次々に入力される。特異点対照合スコア計算回路は，これら特異点対の情報から４つのトレース点間距離またはそのための符号付データを計算する。特異点対照合スコア計算回路は，４つのトレース点間距離から絶対値とそれらの総和を計算する。この照合スコア計算回路と同時に，特異点対の位置差を求め，その位置差に対応する番地の2次元メモリのデータを読み出す。累積スコア回路では，特異点対照合スコアと累積スコアを入力し，加算して累積スコアを更新し，2次元メモリの同じ番地に書きこむ。このとき，累積スコアと現在までの最大値とを比較し，最大値の方が小さい場合は最大値を更新する。入力指紋と登録指紋との特異点対の位置差の2次元情報から累積スコアを保存する2次元メモリのアドレスを生成する。このアドレス生成回路は登録指紋特異点情報の入力の後，累積照合スコア回路の動作前のトレース点間距離回路と照合スコア回路の動作と同時に実行される。
【００８４】
図14は，図13と比べてさらに多くのクロックについて，図12の指紋照合エンジン回路(83)の動作を示すタイムチャートである。すなわち，１つの入力指紋データの特異点情報入力に対して，登録指紋データの特異点情報（特異点番号１からＮｒ）を次々に読み込み，図13の一連の処理をパイプライン処理として，すべての登録指紋の特異点対について実行する。次に，同じ入力指紋データの別の特異点情報について同様な読み込みから始まって，登録指紋の特異点すべてとの間で同様な処理を繰り返す。これらを入力指紋データのすべての特異点について繰り返し，その中のスコアの最大のものを入力指紋と登録指紋データとの照合スコアとし，この照合スコアが特定された閾値より大きい場合は，最大スコアとなった登録指紋に照合すると結果する。
【００８５】
（７．小メモリ指紋対照合スコアの計算アルゴリズム）
本発明の指紋対照合スコア計算の別の態様としては，前記指紋対照合スコア計算を修正して，修正した指紋対照合スコア計算を２段階に分けて実行する。第一段階では前記指紋対照合スコア計算の２次元位置差の探索の代わりに，水平および垂直の位置差という２つの１次元平面での探索によって2次元位置差の概略値を求めるグローバル探索を行う。すなわち，2次元メモリの代わりに，ΔＸに対応するアドレスを有する一次元メモリ（一次元累積スコアメモリ）と，ΔＹに対応するアドレスを有する1次元メモリ（一次元累積スコアメモリ）の2つを用いる。そして，第二段階では前記２次元位置差の探索を，前記グローバル探索で得られた２次元位置差の概略値の周辺のローカル探索を行う。この指紋照合システムは，登録指紋と入力指紋との位置の相違の概略値をまず求めるので，少ない作業メモリで実用的な回路を提供できる。
【００８６】
図15は，小メモリ指紋対照合スコアの計算アルゴリズムの例を示す図である。前記の指紋照合エンジン回路を概略値計算のためのグローバル探索と，詳細値計算のためのローカル探索に分けたものであり，必要なメモリ量を大幅に軽減することを目的としている。
【００８７】
なお，グローバル検索及びローカル検索とも図11及び図12に示される回路構成としても良いし，いずれか一方のみについて，2次元累積スコアメモリ(95)の代わりに，2つの一次元累積スコアメモリ（ΔＸ及びΔＹ）を用いても良い。更には，グローバル検索回路及びローカル検索回路の両方について，2次元累積スコアメモリ(95)の代わりに，2つの一次元累積スコアメモリ（ΔＸ及びΔＹ）を用いても良い。
【００８８】
（７．１  グローバル探索）
図16は，グローバル探索の例を示すフローチャートである。すなわち，2次元累積スコアメモリ(95)の代わりに，2つの一次元累積スコアメモリ（ΔＸ及びΔＹ）を用いる場合は，以下のようにして照合を行えばよい。すなわち，前記した指紋対照合スコア計算を２回繰り返す。第一段階では，二次元累積スコアメモリの代わりに，２つの１次元累積スコアメモリを利用して，位置差の水平成分に対応した累積特異点対照合スコアと，位置差の垂直成分に対応した累積特異点対照合スコアに，計算された特異点対照合スコアを加算する。それと同時に，水平方向の累積特異点対照合スコアと垂直方向の累積特異点対照合スコアの最大値を別々に保存する。すべての回転角および特異点対で得られる最終的な水平，垂直方向の累積スコアの最大値を与える位置差の水平座標と垂直座標を，登録指紋と入力指紋の位置差の概略値とする。
【００８９】
図17は，1次元メモリを用いた場合の照合スコア分布例を示すグラフである。２次元メモリ空間は実際には用意せず，Ｘ方向，Ｙ方向の１次元メモリを２つ用意し，累積スコアを位置差のＸ方向に対応するアドレスをもつメモリと，累積スコアを位置差のＹ方向に対応するアドレスをもつメモリに累積する操作を同時に別々のメモリに行う。図17からも明らかなように，２次元メモリ空間における最大値は，１次元メモリ空間におけるものとは必ずしも一致しない。このため，2つの1次元累積スコアメモリを用いた場合，2次元累積スコアメモリを用いた場合に比べて正確な最大値は得られないが，概略的な最大値と最大照合スコアを与える特異点対の始点の位置差の概略値を求めることができる。
【００９０】
（７．２  ローカル探索）
図18は，ローカル探索の工程例を示すフローチャートである。図18においては，全ての特異点対について累積スコア計算を行ったかどうかを判断する(121)。そして，全ての特異点対について，累積スコア計算を行っていなければ，特異点対について位置差を計算する(122)。そして，求められた位置差が，グローバル検索で求められた位置差の概略地の周辺であるか（例えば，ΔＸ及びΔＹが同じアドレスに属するか，又は最大値を与えたΔＸ及びΔＹから所定のずれの範囲内にあるか）を判定する(123)。求められた位置差が，概略値の周辺でなければ，その特異点対についての累積スコア計算を終了し，全ての特異点について累積スコア計算を行ったか判断する(121)。そして，求められた位置差が概略値の周辺であれば，特異点対のトレース点間距離を計算し（124），求められたトレース点間距離を用いて，照合スコアを計算する（125）。そして，その位置差に対応する累積スコアに照合スコアを累積的に記憶させる(126)。この累積スコア計算が終わった後，全ての特異点について累積スコア計算が行われたかどうか判断する(121)。そして，全ての特異点について累積スコア計算が行われた場合，ローカル検索を終了する(127)。すなわち，前記のグローバル探索で得られた水平と垂直方向の位置差を概略値としてその周辺を詳細に探索して，真に最大の累積スコアを計算し，これを最終的な累積スコアとする。実際には，選択された特異点対毎に，その位置差が概略値の周辺の値だけに関して，特異点対スコア計算，累積スコア計算を実行し，それ以外の特異点対については計算を打ち切ればよい。
【００９１】
（小メモリ指紋対照合スコアの計算回路）  
図19は，本発明のある実施態様に係る指紋照合システムのブロック図である。すなわち，図19は，先に説明した指紋照合エンジン回路を２つ設置し，電気的に接続したものである。すなわち，この態様の小メモリ指紋対照合スコアの計算回路は，入力指紋の特徴情報を記憶する記憶回路(131)と，登録指紋の特徴情報を記憶する記憶回路(132)と，グローバル検索を行う指紋照合エンジン１(133)とローカル検索を行う指紋照合エンジン２(134)と，最終的な指紋照合点を出力する指紋照合スコア回路(135)と，これら回路の動作を制御する制御回路（136）とを具備する。そして，これらの回路は，バスなどにより接続されており，情報の授受を行うことができるものとされている。
【００９２】
図20は，グローバル検索を行う指紋照合エンジン１の例を示すブロック図である。図20に示されるように，この指紋照合エンジンは，ある特異点対のトレース点間距離を求めるためのトレース点間距離計算回路(141)と，前記トレース点間距離計算回路(141)により求められたトレース点間距離を用いてある特異点対の照合スコアを求める照合スコア計算回路(142)と，照合スコア計算回路が求めた照合スコアを累積するための1次元累積スコア計算回路(143)と，特異点対の始点位置の水平位置差（ΔＸ）及び垂直位置差（ΔＹ）を求め，その水平位置差及び垂直位置差に対応する２つの累積スコアメモリとしての１次元メモリのアドレスを計算する累積スコアメモリアドレス計算回路(144)と，２つの累積スコアメモリである2つの1次元累積スコアメモリ(145)とを具備する。そして，各回路やメモリの動作は，図示しない制御回路などの制御部により制御されている。
【００９３】
特異点対についての特徴情報が入力されると，累積スコアメモリアドレス計算回路(144)が特異点対の始点位置の水平位置差（ΔＸ）及び垂直位置差（ΔＹ）を求め，その水平位置差及び垂直位置差に対応する２つの累積スコアメモリ(145)における2つのアドレスを計算する。一方，トレース点間距離計算回路(141) には，θ，φ１，φ２，φ３，θ’，φ１’，φ２’，及びφ３’などの角度情報が入力され，特異点対のトレース点間距離（Sim(ti,sj)）が求められる。そして，照合スコア計算回路(142)は，前記トレース点間距離計算回路(141)により求められたトレース点間距離を用いてある特異点対の照合スコア（Score(ti,sj)）を求める。そして，累積スコアメモリアドレス計算回路(144)により求められた，特異点対の始点位置の水平位置差及び垂直位置差に対応する2つの1次元累積スコアメモリ(145)のアドレスに格納された累積スコアが読み出され，1次元累積スコア計算回路(143)へと伝えられる。1次元累積スコア計算回路(143)は，1次元累積スコアメモリ(145)から読み出された累積スコア（ACC_score1(ΔX)，ACC_score2(ΔY)，）に，照合スコア計算回路(142)で求められた照合スコアを加算する。そして，加算した値を新たな累積スコアとして，1次元累積スコアメモリ(145)に伝え，1次元累積スコアメモリ(145)はその値を累積スコアとして記録する。このようにして累積スコアが更新される。図２０に示す指紋照合エンジン１では，すべての特異点対について照合スコアの計算を行う。しかし，指紋照合エンジン１は，累積スコアの計算をX方向とY方向について別々に実行するため，メモリ量が大幅に軽減される。
【００９４】
図21は，ローカル検索を行う指紋照合エンジン２を示すブロック図である。図21に示されるように，この指紋照合エンジンは，ある特異点対のトレース点間距離を求めるためのトレース点間距離計算回路(151)と，前記トレース点間距離計算回路(151)により求められたトレース点間距離を用いてある特異点対の照合スコアを求める照合スコア計算回路(152)と，照合スコア計算回路が求めた照合スコアを累積するための２次元累積スコア計算回路(153)と，特異点対の始点位置の水平位置差（ΔＸ）及び垂直位置差（ΔＹ）を求め，その水平位置差及び垂直位置差に対応する累積スコアメモリとしての２次元メモリのアドレスを計算する累積スコアメモリアドレス計算回路(154)と，累積スコアメモリである２次元累積スコアメモリ(155)とを具備する。そして，各回路やメモリの動作は，図示しない制御部により制御されている。また，累積スコアメモリアドレス計算回路(154)は，求められた特異点の始点位置の水平位置差（ΔＸ）及び垂直位置差（ΔＹ）が所定の範囲に属しているかどうかを判断し，それにより動作を制御する制御機能を有している。
【００９５】
図20に示すエンジンにより，特異点の始点位置の水平位置差（ΔＸ）及び垂直位置差（ΔＹ）の概略値が求められ，その概略値は累積スコアメモリアドレス計算回路(154)に入力される。すると，累積スコアメモリアドレス計算回路(154)は，入力された概略値に基づいて，特異点の始点位置の水平位置差（ΔＸ）及び垂直位置差（ΔＹ）が所定の範囲に入るかどうかで制御信号を変える範囲を変更する。指紋照合エンジン２に，特異点対についての特徴情報が入力されると，累積スコアメモリアドレス計算回路(154)が特異点対の始点位置の水平位置差（ΔＸ）及び垂直位置差（ΔＹ）を求め，その水平位置差及び垂直位置差に対応する累積スコアメモリのアドレスを計算する。この際，水平位置差（ΔＸ）及び垂直位置差（ΔＹ）が先に設定した所定の範囲内になければ，この特異点対についての累積スコア演算を終了するように指令を出力する。一方，水平位置差（ΔＸ）及び垂直位置差（ΔＹ）が所定の範囲内であれば，この特異点対の水平位置差（ΔＸ）及び垂直位置差（ΔＹ）に対応するアドレス情報を２次元累積スコアメモリ(155)へと伝える。また，図示しない制御部へも演算を進めるよう指令を出しても良い。すると，トレース点間距離計算回路(151) には，θ，φ１，φ２，φ３，θ’，φ１’，φ２’，及びφ３’などの角度情報が入力され，特異点対のトレース点間距離が求められる。そして，照合スコア計算回路(152)は，前記トレース点間距離計算回路(151)により求められたトレース点間距離を用いてある特異点対の照合スコアを求める。そして，累積スコアメモリアドレス計算回路(154)により求められた，特異点対の始点位置の水平位置差及び垂直位置差に対応する２次元累積スコアメモリ(155)のアドレスに格納された累積スコアが読み出され，２次元累積スコア計算回路(153)へと伝えられる。２次元累積スコア計算回路(153)は，２次元累積スコアメモリ(155)から読み出された累積スコアに照合スコア計算回路(142)で求められた照合スコアを累積的に加算する。そして，加算した値を新たな累積スコアとして，２次元累積スコアメモリ(155)に伝え，２次元累積スコアメモリ(155)はその値を更新する。図２１に示す次の指紋照合エンジン２ではすべての特異点対について探索するが，指紋照合エンジン１で得られた概略値の周辺の位置差であるものについてのみ累積スコアに考慮されるように累積スコアメモリアドレス計算回路が判定して制御信号を出力する。
【実施例１】
【００９６】
（１．指紋照合のための回路）
この実施例では，図12に示されたトレース点間距離計算回路(91)と，照合スコア計算回路(92)と，２次元累積スコア計算回路(93)を具備する回路を用いた。
【００９７】
図22は，トレース点間距離計算回路の具体的な回路例を示すブロック図である。このトレース点間距離計算回路(91)は特異点対に対して，符号付トレース点間距離Δθ，２Δθ＋Δφ１，３Δθ＋２Δφ１＋Δφ２，４Δθ＋３Δφ１＋２Δφ２＋Δφ３をそれぞれ2クロックで並列に計算する回路である。特異点対トレース点間距離計算回路が，図22に示されるような回路構成を有するので，２クロック間に特異点対トレース点間距離を計算することができる。この計算を行う前提として，先に説明したように，入力指紋及び登録指紋が３２ビットのフォーマットに変換されている。特異点対トレース点間距離の計算を２クロックで行うことができるので，図１３に示されるように，効率的に指紋照合を行うことができることとなる。登録指紋のある特異点の特徴情報（ＭＳ）をｓ＝（Ｘ，Ｙ，θ，φ１，φ２，φ３）とし，入力指紋のある特異点の特徴情報（ＭＳ）をｓ’＝（Ｘ’，Ｙ’，θ’，φ１’，φ２’，φ３’）とする。図２２に示される回路は，θ及びθ’が入力され，入力されたθ及びθ’を用いてΔθに相当するθ−θ’を求めて出力する第1の減算器(161)と，φ１及びφ１’が入力され，入力されたφ１及びφ１’を用いてΔφ１に相当するφ１−φ１’を求めて出力する第2の減算器(162)と，φ２及びφ２’が入力され，入力されたφ２及びφ２’を用いてΔφ２に相当するφ２−φ２’を求めて出力する第3の減算器(163)と，φ３及びφ３’が入力され，入力されたφ３及びφ３’を用いてΔφ３に相当するφ３−φ３’を求めて出力する第4の減算器(164)と，前記第1の減算器(161)からの出力であるΔθと前記第2の減算器(162)からの出力であるΔφ１とが入力され，入力されたΔθ及びΔφ１を用いてΔθ＋Δφ１を求めて出力する第1の加算器(165)と，前記第1の減算器(161)からの出力であるΔθと前記第1の加算器(165）からの出力であるΔθ＋Δφ１とが入力され，入力されたΔθ及びΔθ＋Δφ１を用いて２Δθ＋Δφ１を求めて出力する第2の加算器(166)と，前記第1の加算器(165）からの出力であるΔθ＋Δφ１と前記第3の減算器(163)からの出力であるΔφ２とが入力され，入力されたΔθ＋Δφ１及びΔφ２を用いてΔθ＋Δφ１＋Δφ２を求めて出力する第3の加算器(167)と，前記第1の減算器(161)からの出力であるΔθが入力され，入力されたΔθを記憶するための第1のレジスタ(168)と，第2の加算器(166)からの出力である２Δθ＋Δφ１が入力され，入力された２Δθ＋Δφ１を記憶するための第2のレジスタ(169)と，第3の加算器(167)からの出力であるΔθ＋Δφ１＋Δφ２が入力され，入力されたΔθ＋Δφ１＋Δφ２を記憶するための第3のレジスタ(170)と，前記第4の減算器(164)からの出力であるΔφ３が入力され，入力されたΔφ３を記憶するための第4のレジスタ(171)と，前記      第2のレジスタ(169)が記憶した２Δθ＋Δφ１と前記第3のレジスタ(170)が記憶したΔθ＋Δφ１＋Δφ２とが入力され，入力された２Δθ＋Δφ１及びΔθ＋Δφ１＋Δφ２を用いて３Δθ＋２Δφ１＋Δφ２を求めて出力する第4の加算器(172)と，前記第3のレジスタ(170)が記憶したΔθ＋Δφ１＋Δφ２と前記第4のレジスタ(171)が記憶したΔφ３とが入力され，入力されたΔθ＋Δφ１＋Δφ２及びΔφ３を用いて，Δθ＋Δφ１＋Δφ２＋Δφ３を求めて出力する第5の加算器(173)と，前記第4の加算器(172)からの出力である３Δθ＋２Δφ１＋Δφ２と前記第5の加算器(173)からの出力であるΔθ＋Δφ１＋Δφ２＋Δφ３とが入力され，入力された３Δθ＋２Δφ１＋Δφ２及びΔθ＋Δφ１＋Δφ２＋Δφ３を用いて４Δθ＋３Δφ１＋２Δφ２＋Δφ３を求めて出力する第6の加算器(174)と，前記第1のレジスタ(168)からの出力であるΔθが入力され，入力されたΔθを記憶するための第5のレジスタ(175)と，前記第2のレジスタ(169)からの出力である２Δθ＋Δφ１が入力され，入力された２Δθ＋Δφ１を記憶するための第6のレジスタ(176)と，前記第4の加算器(172)からの出力である３Δθ＋２Δφ１＋Δφ２が入力され，入力された３Δθ＋２Δφ１＋Δφ２を記憶するための第7のレジスタ(177)と，前記第6の加算器(174)からの出力である４Δθ＋３Δφ１＋２Δφ２＋Δφ３が入力され，入力された４Δθ＋３Δφ１＋２Δφ２＋Δφ３を記憶するための第8のレジスタ(178)と，を具備する。
【００９８】
本発明におけるトレース点間距離計算手段としてのトレース点間距離計算回路(91)は，図22に示される回路に限定されることはなく，適宜改良を加えてよい。一方，図22に示される回路であれば，第1のレジスタ〜第4のレジスタに到達するまでの最大の経由回路（経由する加算器及び減算器の数）が3つ（第1の減算器(161)，第1の加算器(165)及び第3の加算器(167)を経て第3のレジスタ(170)へと到達するルート）となる。これにより，第1のレジスタ〜第4のレジスタに到達するまでの計算を１クロックの間に行うことができる。また，第1のレジスタ〜第4のレジスタから，第5のレジスタ〜第8のレジスタに到達するまでの最大の経由回路が3つ（第2及び第3のレジスタから情報を読み出し，第4の加算器(172)及び第6の加算器(174)を経て第8のレジスタへと到達するルート）となる。このように，第1のレジスタ〜第4のレジスタから，第5のレジスタ〜第8のレジスタに到達するまでに，最大の経由回路（経由する加算器及び減算器の数）が2つとなるので，第1のレジスタ〜第4のレジスタから，第5のレジスタ〜第8のレジスタに到達するまでの計算を1クロックの間に行うことができる。
【００９９】
第1クロックでは，特異点の４つの角度（θ，φ１，φ２，φ３）の差を求める演算が，それぞれ４つの減算器(161-164)により並列して行われる。次に，Δθ＋Δφ１の加算と，その結果を利用したΔθ＋Δφ１とΔθ，Δθ＋Δφ１とΔφ２の加算を実行する。そして，４つのレジスタ１６８−１７１にそれぞれ，Δθ，２Δθ＋Δφ１，Δθ＋Δφ１＋Δφ２，Δφ３の値を記憶させる。この回路では１クロックで演算を行うために，減算器と２段の加算器における演算時間クリティカルパスとなる。
【０１００】
第２クロックでは，加算器(172)より２Δθ＋Δφ１とΔθ＋Δφ１＋Δφ２の加算が行われ，３Δθ＋２Δφ１＋Δφ２が算出される。それと並列して，加算器（173）により，レジスタ(170)からのΔθ＋Δφ１＋Δφ２とレジスタ(171)からのΔφ３の加算が行われ，Δθ＋Δφ１＋Δφ２＋Δφ３が算出される。更に，加算器(174)が，加算器(172)の演算結果である３Δθ＋２Δφ１＋Δφ２と，加算器(173)の演算結果であるΔθ＋Δφ１＋Δφ２＋Δφ３を加えて４Δθ＋３Δφ１＋２Δφ２＋Δφ３を求める。このようにして，2クロックでレジスタ(175-178)には，Δθ，２Δθ＋Δφ１，３Δθ＋２Δφ１＋Δφ２，及び４Δθ＋３Δφ１＋２Δφ２＋Δφ３が記憶されることとなる。なお，先に説明したとおり，トレース点間の距離は，これらの値の絶対値である。したがって，図22に示す回路は，正確には，トレース点間距離を求めるための，トレース点間の位置の差を求める回路ともいえる。
【０１０１】
図23は，特異点対照合スコア計算回路の例を示すブロック図である。なお，トレース点間の距離は，図23の絶対値回路によって求められるため，正確に説明すると，図23は，トレース点間距離計算回路の一部と，照合スコア計算回路の具体的な例を示すブロック図である。
【０１０２】
図23に示されるように，このトレース点間距離計算回路の一部と，照合スコア計算回路は，3つの部分を具備する。すなわち,図23に示される装置は，各トレース点間の位置差から，各トレース点間の距離を求める絶対値算出部と,前記絶対値算出部で算出された各トレース点間距離の総和を求めるトレース点間距離の総和算出部と，及び前記トレース点間距離の総和算出部で算出されたトレース点間距離の総和を用いて照合スコアを算出する照合スコア算出部とを具備する。具体的には図23に示される装置は，上記の各部を具備する回路である。
【０１０３】
図23に示されるように，絶対値算出部は，前記第5のレジスタ（175）に格納されたΔθが入力され，入力値の絶対値である｜Δθ｜を求め，出力する第1の絶対値回路(181)と，前記第6のレジスタ(176)に格納された２Δθ＋Δφ１が入力され，入力値の絶対値である｜２Δθ＋Δφ１｜を求め，出力する第2の絶対値回路(182)と，前記第7のレジスタ(177)に格納された３Δθ＋２Δφ１＋Δφ２が入力され，入力値の絶対値である｜３Δθ＋２Δφ１＋Δφ２｜を求め，出力する第3の絶対値回路(183)と，前記第8のレジスタ(178)に格納された４Δθ＋３Δφ１＋２Δφ２＋Δφ３が入力され，入力値の絶対値である｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め，出力する第4の絶対値回路(184)と，を具備する。
【０１０４】
そして，図22に示される回路の第5のレジスタ（175），第6のレジスタ(176)，第7のレジスタ(177)及び第8のレジスタ(178)にそれぞれ格納された，Δθ，２Δθ＋Δφ１，３Δθ＋２Δφ１＋Δφ２，及び４Δθ＋３Δφ１＋２Δφ２＋Δφ３（各トレース点間の位置差）の値が，それぞれ第1の絶対値回路(181)，第2の絶対値回路(182)，第3の絶対値回路(183)，及び第4の絶対値回路(184)など絶対値算出部に入力され，それらの絶対値が各絶対値回路(181-184)によって算出されて出力される。
【０１０５】
図23に示されるように，トレース点間距離の総和算出部は，前記絶対値算出部で算出された各トレース点間距離の総和を求めるものである。そして，トレース点間距離の総和算出部は，前記第1の絶対値回路(181)及び前記第2の絶対値回路(182)で求められた｜Δθ｜及び｜２Δθ＋Δφ１｜がそれぞれ入力され，入力された前記｜Δθ｜及び前記｜２Δθ＋Δφ１｜を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜を求め出力する第7の加算器(185)と，前記第3の絶対値回路(183)，及び前記第4の絶対値回路(184)で求められた｜３Δθ＋２Δφ１＋Δφ２｜及び｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜がそれぞれ入力され，入力された前記｜３Δθ＋２Δφ１＋Δφ２｜及び前記｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を加算して，｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め出力する第8の加算器(186)と，前記第7の加算器(185)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜と，前記第8の加算器(186)が出力した｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜とが入力され，入力された前記（｜Δθ｜＋｜２Δθ＋Δφ１｜）及び前記（｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜）を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求めて出力する第9の加算器（187）と，前記第9の加算器(187)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜が入力され，入力された前記｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を記憶する第9のレジスタ(188)と，を具備する。
【０１０６】
このトレース点間距離の総和算出部は，第7の加算器(185)に，前記第1の絶対値回路(181)及び前記第2の絶対値回路(182)で求められた｜Δθ｜及び｜２Δθ＋Δφ１｜がそれぞれ入力される。そして，第7の加算器(185)は，入力された前記｜Δθ｜及び前記｜２Δθ＋Δφ１｜を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜を求め出力する。この動作と並行して，第8の加算器(186)には，前記第3の絶対値回路(183)，及び前記第4の絶対値回路(184)で求められた｜３Δθ＋２Δφ１＋Δφ２｜及び｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜がそれぞれ入力される。そして，第8の加算器(186)は，入力された前記｜３Δθ＋２Δφ１＋Δφ２｜及び前記｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を加算して，｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求め出力する。
【０１０７】
次に，第9の加算器（187）には，前記第7の加算器(185)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜と，前記第8の加算器(186)が出力した｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜とが入力される。そして，第9の加算器（187）は，入力された前記（｜Δθ｜＋｜２Δθ＋Δφ１｜）及び前記（｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜）を加算して，｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を求めて出力する。この出力がトレース点間距離の総和Ｄｔｒａｃｅ（Dist(ti,sj)）である。このようにして，トレース点間距離の総和であるＤｔｒａｃｅ＝｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜が求められる。本発明においては，上記をトレース点間距離の総和としたが，別の式に基づいてトレース点間距離の総和としても構わない。また,本発明は，当業者にとって自明な範囲で適宜設計変更することができる。
【０１０８】
第9のレジスタ(188)に，前記第9の加算器(187)が出力した｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜が入力される。そして，第9のレジスタ(188)は，入力された前記｜Δθ｜＋｜２Δθ＋Δφ１｜＋｜３Δθ＋２Δφ１＋Δφ２｜＋｜４Δθ＋３Δφ１＋２Δφ２＋Δφ３｜を記憶する。このようにして，トレース点間距離の総和Ｄｔｒａｃｅが記憶される。
【０１０９】
図23に示されるように，照合スコア算出部は，特異点のトレース点の数であるトレース点の個数Ｎｔｒａｃｅ(Ｎｔｒａｃｅ=2，3，4・・・，ただし，本実施例ではＮｔｒａｃｅの最大は3である)が入力されると，前記Ｎｔｒａｃｅに所定の係数を乗じた値であるトレース点間個数関連値（例えば，５Ｎｔｒａｃｅ）を出力するマルチプレクサなどのトレース点間個数関連値出力部(190)と，前記第9のレジスタ(188)に格納されたトレース点間距離の総和Ｄｔｒａｃｅ及びトレース点間個数関連値出力部(190)から出力されるトレース点間個数関連値とが入力され，これらの入力値の減算演算を行う第5の減算器(189)と，前記第5の減算器(189)の演算結果が入力され，入力された値である照合スコアを記憶する第10のレジスタ(191)とを具備する。
【０１１０】
照合スコア算出部は，トレース点間個数関連値出力部(190)に，特異点のトレース点の数であるトレース点の個数Ｎｔｒａｃｅが入力される。すると，トレース点間個数関連値出力部(190)は，例えば，前記Ｎｔｒａｃｅに対応したトレース点間個数関連値（例えば，５Ｎｔｒａｃｅ）を記憶しておき，入力された前記Ｎｔｒａｃｅに対応したトレース点間個数関連値を読み出して出力する。この読み出されたトレース点間個数関連値は，第5の減算器(189)に入力される。この動作と並行して，前記第9のレジスタ(188)に格納されたトレース点間距離の総和Ｄｔｒａｃｅが読み出され，第5の減算器(189)に入力される。第5の減算器(189)では，入力されたトレース点間距離の総和Ｄｔｒａｃｅ及びトレース点間個数関連値（例えば５Ｎｔｒａｃｅ）の減算演算を行い，照合スコア（例えば，Score=５Ｎｔｒａｃｅ−Ｄｔｒａｃｅ）を求めて，出力する。出力値は，第10のレジスタ(191)へと伝えられ，記憶される。
【０１１１】
図23に示される回路も１システム周期（すなわち，2クロック）で動作する。第１クロックでは，まず，図22の特異点対トレース点間距離計算回路(91)のレジスタ(175-178)に格納されているΔθ，２Δθ＋Δφ１，３Δθ＋２Δφ１＋Δφ２，及び４Δθ＋３Δφ１＋２Δφ２＋Δφ３データを読み出す。そして，読み出された各値を，絶対値回路(181-184)に入力し，各値の絶対値を求める。絶対値回路は図示しないが，データの正負を判定し，正の場合はそのまま，負の場合は符号を反転した対応する正の数に変換する回路である。これらの４つの正の数は3つの加算操作で，すなわち，最初の２つの数の加算と，残り２つの数の加算を同時に行い，それらの結果同士を再び加算する。本実施例において，これらの合計値は，特異点対のトレース点間距離の総和Ｄｔｒａｃｅとして，レジスタ(188)に格納される。
【０１１２】
第２クロックでは，トレース点の個数Ｎｔｒａｃｅ(Ｎｔｒａｃｅ=2，3，4，---)とトレース点間距離の総和Ｄｔｒａｃｅとから，特異点対の照合スコアScoreを，Score＝５＊Ｎｔｒａｃｅ−Ｄｔｒａｃｅの計算で求める。そのためにマルチプレクサ(190)を用意し，トレース点の数Ｎｔｒａｃｅをマルチプレクサ(190)の制御入力にして，予め用意された５Ｎｔｒａｃｅデータを選べるようにする。減算器(189)を用いて上記計算を行い，その結果をレジスタ(191)に格納する。
【０１１３】
図24は，２次元累積スコア計算回路の例を示すブロック図である。図24に示されるように，この２次元累積スコア計算回路は，ある特異点対について計算された累積スコアの最大値が記憶される第11のレジスタ(201)と，前記照合スコア又は前記照合スコアに所定の係数が乗算された値及び，2次元累積メモリのうち前記照合スコアが算出された特異点対の始点の位置差に対応するアドレスに格納された累積スコアが入力され，入力された値を加算し更新された累積スコアを計算する第10の加算器（202）と，前記第11のレジスタ(201)に記憶される累積スコアの最大値と，前記第10の加算器(202)により求められた更新された累積スコアと，を比較する第1の比較回路(203)と，前記第10の加算器(202)により求められた更新された累積スコアを格納するための第12のレジスタ(204)とを具備する。
【０１１４】
第10の加算器（202）に，前記照合スコアが算出された特異点対の始点の位置差に対応するアドレスに対応する2次元累積メモリに格納された累積スコアが読み出されて入力されるともに，前記照合スコア又は前記照合スコアに所定の係数が乗算された値が入力される。すると，第10の加算器（202）は，入力された値を加算し更新された累積スコアを計算し，出力する。第10の加算器（202）が出力した更新された累積スコアは第12のレジスタ(204)に格納される。そして，メモリのうち特異点対の始点の位置差に対応するアドレスにおける累積スコアが更新される。次に，第11のレジスタ(201)に記憶される前記特異点対について計算された累積スコアの最大値が読み出され，第1の比較回路(203)に入力される。この動作と並行して，第10の加算器（202）が出力した更新された累積スコアが第1の比較回路(203)に入力される。そして，第1の比較回路(203)は，前記第11のレジスタ(201)に記憶された累積スコアの最大値と，前記第10の加算器(202)により求められた更新された累積スコアとを比較する。比較した結果，前記第10の加算器(202)により求められた更新された累積スコアが，前記第11のレジスタ(201)に記憶された累積スコアの最大値より大きい場合は，前記第12のレジスタ(204)に格納された更新された累積スコアを読み出して，第11のレジスタ(201)に累積スコアの最大値として記録される。このようにして累積スコアの最大値が更新される。一方，第12のレジスタ（204）に格納された，更新された累積スコアは，特異点対の始点の位置差に対応するアドレスに対応する2次元累積メモリに格納され，累積スコアが更新される。
【０１１５】
図24に示される回路は，2クロックで動作する。第１クロックでは，特異点対の照合スコアScoreをこの特異点対の位置差に対応する累積スコアに加算(202)し，更新された累積スコアをレジスタ(204)へ格納する。これと同時に更新された累積スコアと現在までの累積スコアの中の最大値との比較（203）を行い，現在の最大値が累積スコアより小さい場合は，累積スコアをレジスタ(201)に上書きして自動的に更新する。
【実施例２】
【０１１６】
（２．小メモリの指紋照合のための回路）
実施例1に示す指紋照合システムは，一般に多くの作業用メモリが必要である。その主な原因は，作業用メモリとして2次元の領域が必要であることである。そこで，実施例2では，前記照合回路を２つ用意して，１つを特異点の２次元位置の差の代わりに，１次元水平位置の差および1次元垂直位置の差に対応する２つの1次元メモリ番地（概略値）を求めるグローバル探索システムに置き換えると共に，もう１つを，２次元領域を使う探索であるが，得られた概略値の周辺だけの探索を行うローカル探索システムに置き換える。
【０１１７】
図19に示す回路では，指紋照合エンジン回路１（図20）と指紋照合エンジン回路２(図21)が，前記図12の指紋照合エンジンに置き換えられている。図20の指紋照合エンジン回路１は，図12の指紋照合エンジン回路の累積スコア計算回路が一次元累積スコア計算回路に変更されたものである。図21の指紋照合回路２は，図12の指紋照合エンジン回路の累積スコアメモリアドレス計算回路を変更されたものである。
【０１１８】
（２．１  １次元累積スコア計算回路―グローバル探索）
図25は，方向別１次元累積スコア計算回路の例を示すブロック図である。図25に示されるように方向別1次元累積スコア計算回路は，水平方向の1次元累積スコア計算回路部分と垂直方向の1次元累積スコア計算回路部分とを具備する。
【０１１９】
そして，水平方向の1次元累積スコア計算回路部分は，累積スコアの最大値が格納される第13のレジスタ(211)と，特異点対の照合スコアScore，及び1次元メモリのうち特異点対の水平位置差（ΔＸ）に対応するアドレスに格納された累積スコアが入力され，これらの加算値を計算し，出力する第11の加算器(212)と，前記累積スコアの最大値と前記第11の加算器(212)の出力値とを比較する第2の比較回路（213）と，累積スコア（Acc_score（ΔX））及び照合スコアScoreの和が，入力される第14のレジスタ(214)と，前記第11の加算器(212)の出力値を記憶し，水平方向の位置差(ΔＸ)に対応するアドレスを有し，当該アドレスごとの照合スコアを累積的に加算した累積スコアが記憶される図示しない1次元メモリを具備する。
【０１２０】
水平方向に関する1次元累積メモリから，特異点対の水平位置差（ΔＸ）に対応するアドレスに格納された累積スコア（Acc_score（ΔX））が読み出され第11の加算器(212)に入力される。これと並行して，特異点対の照合スコアScoreが第11の加算器(212)に入力される。第11の加算器(212)は，入力された累積スコア（Acc_score（ΔX））及び照合スコアScoreを加算し，出力する。第11の加算器(212)が出力した，累積スコア（Acc_score（ΔX））及び照合スコアScoreの和が，第14のレジスタ(214)に入力され，記憶される。この累積スコア（Acc_score（ΔX））及び照合スコアScoreの和は，特異点対の水平位置差（ΔＸ）に対応するアドレスに格納される新たな累積スコアとなる。
【０１２１】
すなわち，第14のレジスタ(214)が記憶した累積スコア（Acc_score（ΔX））及び照合スコアScoreの和は，水平方向に関する1次元累積メモリにおける特異点対の水平位置差（ΔＸ）に対応するアドレスの累積スコアとして水平方向に関する1次元累積メモリに伝えられ，当該アドレスにおける累積スコアが更新される。一方，第13のレジスタ(211)から累積スコアの最大値が読み出され，第2の比較回路(213)へと入力される。これと並行して，累積スコア（Acc_score（ΔX））及び照合スコアScoreの和が，第2の比較回路(213)へと入力される。第2の比較回路(213)は，入力された累積スコアの最大値と，累積スコア（Acc_score（ΔX））及び照合スコアScoreの和とを比較する。比較した結果，累積スコア（Acc_score（ΔX））及び照合スコアScoreの和が，前記累積スコアの最大値より大きい場合は，累積スコア（Acc_score（ΔX））及び照合スコアScoreの和を第13のレジスタ(211)へと伝える。第13のレジスタ(211)は，累積スコア（Acc_score（ΔX））及び照合スコアScoreの和を累積スコアの最大値として記憶する。このようにして，累積スコアの最大値が更新される。
【０１２２】
そして，垂直方向の1次元累積スコア計算回路部分は，累積スコアの最大値が格納される第15のレジスタ(215)と，特異点対の照合スコアScore，及び1次元メモリのうち特異点対の垂直位置差（ΔY）に対応するアドレスに格納された累積スコアが入力され，これらの加算値を計算し，出力する第12の加算器(216)と，前記累積スコアの最大値と前記第12の加算器(216)の出力値とを比較する第3の比較回路（217）と，累積スコア（Acc_score（ΔY））及び照合スコアScoreの和が，入力される第16のレジスタ(218)と，前記第12の加算器(216)の出力値を記憶し，垂直方向の位置差(ΔY)に対応するアドレスを有し，当該アドレスごとの照合スコアを累積的に加算した累積スコアが記憶される図示しない1次元メモリを具備する。
【０１２３】
垂直方向に関する1次元累積メモリから，特異点対の垂直位置差（ΔY）に対応するアドレスに格納された累積スコア（Acc_score（ΔY））が読み出され第12の加算器(216)に入力される。これと並行して，特異点対の照合スコアScoreが第12の加算器(216)に入力される。第12の加算器(216)は，入力された累積スコア（Acc_score（ΔY））及び照合スコアScoreを加算し，出力する。第12の加算器(216)が出力した，累積スコア（Acc_score（ΔY））及び照合スコアScoreの和が，第16のレジスタ(218)に入力され，記憶される。この累積スコア（Acc_score（ΔY））及び照合スコアScoreの和は，特異点対の垂直位置差（ΔY）に対応するアドレスに格納される新たな累積スコアとなる。
【０１２４】
すなわち，第16のレジスタ(218)が記憶した累積スコア（Acc_score（ΔY））及び照合スコアScoreの和は，垂直方向に関する1次元累積メモリにおける特異点対の垂直位置差（ΔY）に対応するアドレスの累積スコアとして垂直方向に関する1次元累積メモリに伝えられ，当該アドレスにおける累積スコアが更新される。一方，第15のレジスタ(215)から累積スコアの最大値が読み出され，第3の比較回路（217）へと入力される。これと並行して，累積スコア（Acc_score（ΔY））及び照合スコアScoreの和が，第3の比較回路（217）へと入力される。第3の比較回路（217）は，入力された累積スコアの最大値と，累積スコア（Acc_score（ΔY））及び照合スコアScoreの和とを比較する。比較した結果，累積スコア（Acc_score（ΔY））及び照合スコアScoreの和が，前記累積スコアの最大値より大きい場合は，累積スコア（Acc_score（ΔY））及び照合スコアScoreの和を第15のレジスタ(215)へと伝える。第15のレジスタは，累積スコア（Acc_score（ΔY））及び照合スコアScoreの和を累積スコアの最大値として記憶する。このようにして，累積スコアの最大値が更新される。
【０１２５】
図25に示す回路では，照合スコアが得られたときに2次元メモリ領域に二つの特異点の位置差に対応する場所に累積加算する代わりに，２つの1次元メモリに二つの特異点の位置差の水平成分と垂直成分に対応する場所に別々に累積加算する。回路には，特異点対照合スコアScoreが入力され，位置差の水平方向成分に対応するメモリ番地の水平方向累積スコアと加算(212)され，レジスタ(214)に格納され，その後同じメモリ番地に格納される。これと同時に更新された累積スコアと現在までの累積スコアの中の最大値(211)との比較(213)を行い，現在の最大値が累積スコアより小さい場合は，累積スコアをレジスタ(211)に上書きして自動的に更新する。
【０１２６】
これと同時に，特異点対照合スコアScoreが入力されると，位置差の垂直方向成分に対応するメモリ番地の垂直方向累積スコアと加算(216)され，レジスタ(218)に格納され，その後同じメモリ番地に格納される。これと同時に更新された累積スコアと現在までの累積スコアの中の最大値(215)との比較(217)を行い，現在の最大値が累積スコアより小さい場合は，累積スコアをレジスタ(217)に上書きして自動的に更新する。
【０１２７】
水平方向累積照合スコアと垂直方向累積照合スコアがそれぞれ最大になる水平および垂直方向の値は，必ずしも前記の2次元メモリ領域を利用した累積照合スコアの最大値から得られる位置差の水平および垂直成分とは一致しない。しかし，その性格から正しい位置差からの概略値を与えることができる。しかも，メモリ領域は大幅に減少されている。
【０１２８】
（３．２  累積スコアメモリアドレス計算回路(ローカル探索)）
図26は，ローカル探索のための累積スコアメモリアドレス計算回路の例を示すブロック図である。この回路は，図18の符号123で示される概略値の周辺か否かを判断する機能を実装する回路である。グローバル探索の指紋照合エンジン１で得られた位置差の概略値(ΔXapp，ΔYapp，)に対して，その周辺の範囲として，
ΔXapp−ΔXlow≦ΔX≦ΔXapp＋ΔXhigh，
ΔYapp−ΔXlow≦ΔY≦ΔYapp＋ΔYhigh，
を考える。
【０１２９】
すなわち，この回路において，ΔXの上限値がΔXapp＋ΔXhighであり，ΔXの下限値がΔXapp−ΔXlowであり，ΔYの上限値がΔYapp＋ΔYhighであり，ΔYの下限値がΔYapp−ΔYlowである。図26に示されるように，特異点対の始点間の位置差が概略値の周辺かどうか判断する回路は，ΔXの上限値（ΔXapp＋ΔXhigh）及びΔXが入力され，入力値を比較し，前者が後者以上である場合に1を出力し，それ以外は0を出力する第4の比較回路(221)と，ΔX及びΔXの下限値（ΔXapp−ΔXlow）が入力され，入力値を比較し，前者が後者以上である場合に1を出力し，それ以外は0を出力する第5の比較回路(222)と，ΔYの上限値（ΔYapp＋ΔYhigh）及びΔYが入力され，入力値を比較し，前者が後者以上である場合に1を出力し，それ以外は0を出力する第6の比較回路(223)と，ΔY及びΔYの下限値（ΔYapp−ΔYlow）が入力され，入力値を比較し，前者が後者以上である場合に1を出力し，それ以外は0を出力する第7の比較回路(224)と，前記第4の比較回路(221)，第5の比較回路(222)，第6の比較回路(223)及び第7の比較回路(224)の出力を受取り，それらが何れも1の場合は1を出力し，それ以外の場合は0を出力する4入力AND回路(225)と，前記4入力AND回路(225)からの出力が入力され記憶される第17のレジスタ（好ましくは1ビットレジスタ（226））と，を具備する。
【０１３０】
図26に示される特異点対の始点間の位置差が概略値の周辺かどうか判断する回路は，例えば，以下のように動作する。第4の比較回路(221)に，ΔXの上限値（ΔXapp＋ΔXhigh）及びΔXが入力される。すると，第4の比較回路(221)は，入力値を比較し，ΔXの上限値（ΔXapp＋ΔXhigh）がΔX以上である場合に1を出力し，それ以外は0を出力する。これと並行して，第5の比較回路(222)に，ΔX及びΔXの下限値（ΔXapp−ΔXlow）が入力される。すると，第5の比較回路(222)は入力値を比較し，ΔXがXの下限値（ΔXapp−ΔXlow）以上である場合に1を出力し，それ以外は0を出力する。これと並行して，第6の比較回路(223)にΔYの上限値（ΔYapp＋ΔYhigh）及びΔYが入力される。すると，第6の比較回路(223)は，入力値を比較し，ΔYの上限値（ΔYapp＋ΔYhigh）がΔY以上である場合に1を出力し，それ以外は0を出力する。これと並行して，第7の比較回路(224)にΔY及びΔYの下限値（ΔYapp−ΔYlow）が入力される。すると，第7の比較回路(224)は，入力値を比較し，ΔYがΔYの下限値（ΔYapp−ΔYlow）以上である場合に1を出力し，それ以外は0を出力する。4入力AND回路(225)（これは3つのAND回路によって構成されていても良い）に，前記第4の比較回路(221)，第5の比較回路(222)，第6の比較回路(223)及び第7の比較回路(224)からの出力が入力される。すると，4入力AND回路(225)は，入力値が何れも1の場合は1を出力し，それ以外の場合は0を出力する。第17のレジスタ(226)には，前記4入力AND回路(225)からの出力が入力され，第17のレジスタ(226)はこの値を記憶する。なお，第17のレジスタ（226）が記憶する値は，例えば，0又は1の場合，第17のレジスタとして，1ビットレジスタであっても良い。第17のレジスタ(226)に記憶された値は，読み出されて動作の制御に用いられる。すなわち，第17のレジスタ(226)に記憶された値が1である場合は，特異点対の始点間距離が概略値の周辺であることを意味するので，照合スコアの計算が行われる。一方，第17のレジスタ(226)に記憶された値が0である場合は，特異点対の始点間距離が概略値の周辺でないことを意味するので，照合スコアの計算が行われない。
【０１３１】
例えば，センサーの画素領域が２００×３００であるとき，正確な位置差を計算する２次元メモリ領域は６０，０００番地が必要である。一方，概略値を計算する１次元メモリ領域は２００番地と３００番地とを合わせた５００番地で済むのでメモリを軽減できる。
【実施例３】
【０１３２】
（実際の数値例）
以下では，指紋画像のサイズを，３００×３００画素とした。小メモリ照合アルゴリズムでは，△Ｘと△Ｙは，それぞれ８画素へ量子化されることとした。小メモリ照合アルゴリズムでは，△θを３２方向へ量子化した。入力指紋の特異点と登録指紋のテンプレートの数を２５個とした。小メモリ照合アルゴリズムのＸ軸，Ｙ軸方向に，それぞれ１１個に分割した。指紋照合システムの周波数を１００ＭＨｚとし，１回転角の処理時間を２００クロック周期，メモリ算出を別のものに更新する処理時間を１４０クロック周期，ピーク値を捜すときに１アイテムを点検する処理時間を１５クロック周期で実行可能とする。上記のような前提に基づき，基本アルゴリズムと，小メモリ照合アルゴリズムとの性能を比較したものを以下の表３に示す。
【０１３３】
【表１】
2008165445.tif 000003
【０１３４】
概略値が判明しているため，概略値の周辺だけを探索すれば良く，そのためのメモリ領域は少ない領域を用意しておけば十分である。表１から，本発明の指紋照合システムに採用されるアルゴリズムである小メモリ照合アルゴリズムによれば，少ない作業メモリですみ，かつ作業時間も短縮できることがわかる。
【０１３５】
本発明では，任意の特異点対についてすべて特異点対照合スコアを計算し，位置差に対応するメモリ領域に累積して加えている。同じ指紋を照合するときに照合スコアは大きくなり，同じ位置差に対応するメモリ番地に大きなピークが出現する。そのときの累積されたスコアの数は最大でも特異点の数だけである。すなわち，任意の特異点対についてメモリ領域に累積する操作は多くの無駄を含んでいる。
【産業上の利用可能性】
【０１３６】
本発明の指紋照合のための指紋照合システムは，少ないメモリですみ，しかも高速に精度よく指紋を照合できるので，指紋照合つきICチップ，カード，コンピュータネットワーク，銀行用カード，住宅へのアクセス装置など指紋照合を用いる様々なものに用いることができる。
【図面の簡単な説明】
【０１３７】
【図１】図１は，特開2005-149353号公報に開示された指紋照合システムの例を示す図である。
【図２】図２は，特異点を説明するための図である。図２（ａ）は分岐点(10)，図２（ｂ）は端点(11)を特異点の始点とする指紋の一部を示す図である。なお，図２（ｃ）は，特異点を含む指紋を表す図面に代わる写真である。
【図３】図３は，指紋照合の各過程における指紋画像を示す図面に代わる写真である。図3(a)は，原画像を示し，図3(b)は2値化画像を示し，図3(c)は細線化画像を示す。
【図４】図４は，照合の工程例を示す図である。
【図５】図５は，パラメータを説明するための図である。図5(a)は，特異点と特異点上に設定されたトレース点を示す図である。図5(b)は特異点と特異点上に設定されたトレース点により形成される角を示す図である。
【図６】図６は，特異点の位置シフトと回転を説明するための図である。
【図７】図７は，本発明の一実施態様に係る特異点フォーマットを説明する図である。
【図８】図８は，本発明のトレース点間距離を説明するための図である。
【図９】図９は，指紋の特異点の位置，回転量，隆線形状を特異点として利用する指紋照合工程の処理フローの例を示す図である。
【図１０】図10は，２次元累積スコアの位置差による分布例を示すグラフである。
【図１１】図11は，指紋照合工程の計算アルゴリズムを実現する回路の例を示すブロック図である。
【図１２】図12は，本発明の指紋照合エンジン回路の例を示すブロック図である。
【図１３】図13は，図12のハードウェア回路の動作タイミングを示すタイムチャートである。
【図１４】図14は，図13と比べてさらに多くのクロックについて，図12の指紋照合エンジン回路の動作を示すタイムチャートである。
【図１５】図15は，小メモリ指紋対照合スコアの計算アルゴリズムの例を示す図である。
【図１６】図16は，グローバル探索の例を示すフローチャートである。
【図１７】図17は，1次元メモリを用いた場合の照合スコア分布例を示すグラフである。
【図１８】図18は，ローカル探索の工程例を示すフローチャートである。
【図１９】図19は，本発明のある実施態様に係る指紋照合システムのブロック図である。
【図２０】図20は，グローバル検索を行う指紋照合エンジン１の例を示すブロック図である。
【図２１】図21は，ローカル検索を行う指紋照合エンジン２を示すブロック図である。
【図２２】図22は，トレース点間距離計算回路の具体的な回路例を示すブロック図である。
【図２３】図23は，照合スコア計算回路の例を示すブロック図である。
【図２４】図24は，２次元累積スコア計算回路の例を示すブロック図である。
【図２５】図25は，方向別１次元累積スコア計算回路の例を示すブロック図である。
【図２６】図26は，ローカル探索のための累積スコアメモリアドレス計算回路の例を示すブロック図である。
【符号の説明】
【０１３８】
１  指紋センサ
２  前処理部
３  特徴抽出部
４  テンプレート
５  データベース部
６  照合部
７  外部表示部
１０  指紋の分岐点
１１  指紋の端点
２１  特異点の始点
２２―２５  トレース点
３１  登録指紋の特異点の始点（トレース点）
３２−３５  登録指紋のトレース点
４１  入力指紋の特異点の始点（トレース点）
４２−４５  入力指紋のトレース点
５０  特異点の始点
５１−５４  １つの指紋のトレース点
６１−６４  １つの指紋のトレース点
７１  すべての回転角について実行したか判定する分岐
７２  すべての特異点対について実行したか判定する分岐
７３  トレース点間距離計算工程
７４  照合スコア計算工程
７５  累積スコア計算回路
７６  指紋照合エンジン
７７  指紋対照合スコア出力工程
８１  入力指紋メモリ
８２  登録指紋メモリ
８３  指紋照合エンジン回路
８４  指紋対照合スコア回路
８５  制御回路
９１  トレース点間距離計算回路
９２  照合スコア計算回路
９３  ２次元累積スコア計算回路
９４  ２次元累積スコアメモリアドレス計算回路
９５  ２次元累積スコアメモリ
１０１  すべての回転角について実行したか判定する分岐
１０２  指紋照合エンジン回路１（グローバル探索工程）
１０３  指紋照合エンジン回路２（ローカル探索工程）
１０４  指紋対照合スコア出力工程
１１１  すべての特異点対について実行したか判定する分岐
１１２  トレース点間距離計算工程（回路）
１１３  特異点対照合スコア計算工程（回路）
１１４  Ｘ方向およびＹ方向累積スコア計算工程（回路）
１２１  すべての特異点対について実行したか判定する分岐
１２２  位置差計算工程
１２３  概略値周辺か判定する分岐
１２４  トレース点間距離計算工程（回路）
１２５  特異点対照合スコア計算工程（回路）
１２６  累積スコア計算工程（回路）
１３１  入力指紋メモリ
１３２  登録指紋メモリ
１３３  指紋照合エンジン回路１（概略移動量グローバル探索）
１３４  指紋照合エンジン回路２（詳細移動量ローカル探索）
１３５  指紋照合スコア回路
１３６  制御回路
１４１  特異点対トレース点間距離計算回路
１４２  特異点対照合スコア計算回路
１４３  １次元累積スコア計算回路（グローバル探索）
１４４  累積スコアメモリアドレス計算回路
１４５  １次元累積スコアメモリ
１５１  トレース点間距離計算回路
１５２  照合スコア計算回路
１５３  ２次元累積スコア計算回路（ローカル探索）
１５４  累積スコアメモリアドレス計算回路（累積スコア計算制御付き）
１５５  ２次元累積スコアメモリ
１６１−１６４  減算器
１６５−１６７  加算器
１６８−１７１  レジスタ
１７２−１７４  加算器
１７５−１７８  レジスタ
１８１−１８４  絶対値器
１８５−１８７  加算器
１８８  レジスタ
１８９  減算器
１９０  マルチプレクサ（選択器）
１９１  レジスタ
２０１，２０４  レジスタ
２０２  加算器
２０３  比較器
２１１，２１４，２１５，２１８  レジスタ
２１２，２１６  加算器
２１３，２１７  比較器
２２１−２２４  比較器
２２５  ４入力論理積（ＡＮＤ）回路
２２６  レジスタ（１ビット）
【図１】
2008165445.tif 000004
【図２】
2008165445.tif 000005
【図３】
2008165445.tif 000006
【図４】
2008165445.tif 000007
【図５】
2008165445.tif 000008
【図６】
2008165445.tif 000009
【図７】
2008165445.tif 000010
【図８】
2008165445.tif 000011
【図９】
2008165445.tif 000012
【図１０】
2008165445.tif 000013
【図１１】
2008165445.tif 000014
【図１２】
2008165445.tif 000015
【図１３】
2008165445.tif 000016
【図１４】
2008165445.tif 000017
【図１５】
2008165445.tif 000018
【図１６】
2008165445.tif 000019
【図１７】
2008165445.tif 000020
【図１８】
2008165445.tif 000021
【図１９】
2008165445.tif 000022
【図２０】
2008165445.tif 000023
【図２１】
2008165445.tif 000024
【図２２】
2008165445.tif 000025
【図２３】
2008165445.tif 000026
【図２４】
2008165445.tif 000027
【図２５】
2008165445.tif 000028
【図２６】
2008165445.tif 000029