(57)【要約】【課題】指紋照合等における照合精度を改善する。【解決手段】サーチ側およびファイル側の芯線データ等を読み込んだならば、処理対象の順序付ける際に基準となる対特徴点ＢＰＭを決定する。続いて、ＢＰＭに基づいて定められる順番に従って、ファイル側の芯線データを修正していく。その後、サーチ側の芯線データに含まれる芯線を一本ずつ選択し、その芯線上の各芯線点について、ファイル側の対応点を定めて対応付けを行っていく。サーチ側とファイル側とで対応付けられた芯線点を合致芯線点という。対応付けを行った後、連続する合致芯線点の長さをサーチ側の各芯線毎に計算し、その計算結果に基づいて芯線の合致度合いを表すスコアを計算する。【選択図】　図９
2004078433.tif 000002
【特許請求の範囲】
【請求項１】
第一の縞模様画像と第二の縞模様画像とを照合する縞模様画像照合装置であって、
各縞模様画像の縞を細線化した線である芯線を示す芯線画素のデータを抽出する芯線抽出手段と、
第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定することによって芯線画素同士の対応付け処理を行う対応付け手段と、
前記対応付け手段による対応付け処理が行われた第一の縞模様画像の芯線画素に基づいて第一の縞模様画像と第二の縞模様画像の合致の度合いを評価する評価手段とを備えた
ことを特徴とする縞模様画像照合装置。
【請求項２】
評価手段は、対応付け処理が行われた第一の縞模様画像の芯線画素が連続する長さを芯線毎に計測し、計測した長さに基づいて合致の度合いを評価する請求項１に記載の縞模様画像照合装置。
【請求項３】
評価手段は、第一の縞模様画像の画素のうち、対応付け処理が行われた第一の縞模様画像の芯線画素との間に所定の関係を有する画素の数に基づいて、合致の度合いを評価する請求項１または請求項２に記載の縞模様画像照合装置。
【請求項４】
芯線上の特徴点のうち、第一の縞模様画像側と第二の縞模様画像側とで対応付けられる対特徴点を特定する特徴点照合手段を備え、
対応付け手段は、対応付け処理の対象となる芯線上に、第一の縞模様画像側と第二の縞模様画像側とで種別が合致する対特徴点が存在する場合に、前記対特徴点の画素を起点として第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定していく
請求項１から請求項３のうちのいずれか１項に記載の縞模様画像照合装置。
【請求項５】
対応付け手段は、既に対応付けられている対特徴点の画素または芯線画素と、これから対応付け処理を行う第一の縞模様画像の芯線画素および第二の縞模様画像の芯線画素との位置関係に基づいて、第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定する請求項４に記載の縞模様画像照合装置。
【請求項６】
特徴点照合手段が特定した対特徴点の種別が第一の縞模様画像側と第二の縞模様画像側とで合致するようにいずれか一方の縞模様画像の芯線データを修正する芯線データ修正手段を備え、
対応付け手段は、芯線データ修正手段が修正した芯線データを用いて第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定する
請求項４または請求項５に記載の縞模様画像照合装置。
【請求項７】
芯線データ修正手段は、対向関係にある二つの特徴点の組を排除するように少なくとも第二の縞模様画像の芯線データを修正する請求項６に記載の縞模様画像照合装置。
【請求項８】
特徴点照合手段は、芯線データ修正手段が修正した芯線データに基づいて再び対特徴点を特定する請求項６または請求項７に記載の縞模様画像照合装置。
【請求項９】
特徴点照合手段が特定した対特徴点の中から、対応付け処理を行う芯線の順番を定める際の基準となるベース対特徴点を決定するベース対特徴点決定手段を備え、
対応付け手段は、各芯線とベース対特徴点との位置関係に基づいて芯線の順番を定め、前記順番に従って各芯線毎に対応付け処理を行う
請求項４から請求項８のうちのいずれか１項に記載の縞模様画像照合装置。
【請求項１０】
対応付け手段は、第一の縞模様画像上の点と第二の縞模様画像上の点とが指定された場合に、第一の縞模様画像側と第二の縞模様画像側とで対になる点を、指定された点に基づいて定め、定めた点を含む芯線における芯線画素同士の対応付け処理を行う際には、定めた点を起点として第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定していく請求項１から請求項９のうちのいずれか１項に記載の縞模様画像照合装置。
【請求項１１】
第一の縞模様画像と第二の縞模様画像とを照合する縞模様画像照合方法であって、
各縞模様画像の縞を細線化した線である芯線を示す芯線画素のデータを抽出し、
第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定することによって芯線画素同士の対応付け処理を行い、
対応付け処理が行われた第一の縞模様画像の芯線画素に基づいて第一の縞模様画像と第二の縞模様画像の合致の度合いを評価する
ことを特徴とする縞模様画像照合方法。
【請求項１２】
対応付け処理が行われた第一の縞模様画像の芯線画素が連続する長さを芯線毎に計測し、計測した長さに基づいて第一の縞模様画像と第二の縞模様画像の合致の度合いを評価する請求項１１に記載の縞模様画像照合方法。
【請求項１３】
第一の縞模様画像の画素のうち、対応付け処理が行われた第一の縞模様画像の芯線画素との間に所定の関係を有する画素の数に基づいて、第一の縞模様画像と第二の縞模様画像の合致の度合いを評価する請求項１１または請求項１２に記載の縞模様画像照合方法。
【請求項１４】
芯線上の特徴点のうち、第一の縞模様画像側と第二の縞模様画像側とで対応付けられる対特徴点を特定し、
対応付け処理の対象となる芯線上に、第一の縞模様画像側と第二の縞模様画像側とで種別が合致する対特徴点が存在する場合に、前記対特徴点の画素を起点として第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定していく
請求項１１から請求項１３のうちのいずれか１項に記載の縞模様画像照合方法。
【請求項１５】
既に対応付けられている対特徴点の画素または芯線画素と、これから対応付け処理を行う第一の縞模様画像の芯線画素および第二の縞模様画像の芯線画素との位置関係に基づいて、第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定する請求項１４に記載の縞模様画像照合方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、縞模様画像照合装置および縞模様画像照合方法に関し、特に、指紋隆線の端点や分岐点が少ない指紋についても高い精度で照合することができる縞模様画像照合装置および縞模様画像照合方法に関する。
【０００２】
【従来の技術】
これまでに様々な指紋照合方法等が提案されている。例えば、特開昭５９−７７８号公報には、指紋隆線の端点や分岐点を用いた照合方法が記載されている。なお、端点および分岐点をあわせて特徴点と呼ぶ。また、特開平２−２２４０７６号公報およびその米国特許第４９４７４４２号には、特徴点と非特徴点とを合わせて照合する方法が記載されている。この照合方法では、ある一定面積の小領域に特徴点が存在しないとき、その小領域の中心座標を非特徴点として用いる。また、特徴点が存在しない領域の面積を用いて照合を行う方法が、本出願の出願人によって出願されている。
【０００３】
また、米国特許第５６３１９７１号には、特徴点の位置や方向データだけではなく、特徴点近傍の芯線データをトレースし、その性質をコーディングすることで、照合に利用できる情報を増やして照合を行う方法が記載されている。
【０００４】
また、「細線化画像のパターンマッチングによる指紋照合；電子通信学会論文誌　Ｄ−ＩＩ　Ｖｏｌ．Ｊ７９−Ｄ−ＩＩ　Ｎｏ．３　ｐｐ．３３０−３４０　１９９６年３月」（小林哲二）には、芯線による指紋の照合方法が記載されている。芯線は、指紋の隆線等の縞を細線化した線である。また、米国特許第４５８１７６０号には、画像の歪みを考慮して、複数個の部分領域のみに限定して照合する照合方法が記載されている。
【０００５】
【発明が解決しようとする課題】
一般的に、照合する指紋における特徴点の数が少なくなると、照合が困難になる。例えば、米国特許第５６３１９７１号に記載された照合方法では、ある程度の数の特徴点が存在することと、その特徴点が誤抽出されたものでないことが前提になる。従って、特徴点の数が少なくなると、照合が困難になる。
【０００６】
また、照合すべき遺留指紋には、歪みが生じていたり、照合に用いることができる面積が小さい場合が多い。しかし、一般的に、歪みが生じたり、照合に用いることができる面積が小さい場合にも、照合は困難になる。例えば、「細線化画像のパターンマッチングによる指紋照合；電子通信学会論文誌　Ｄ−ＩＩ　Ｖｏｌ．Ｊ７９−Ｄ−ＩＩ　Ｎｏ．３　ｐｐ．３３０−３４０　１９９６年３月」に記載の照合方法では、照合される二つの指紋にほとんど歪みがない場合には照合可能である。しかし、歪みがある場合には照合は困難になる。また、米国特許第４５８１７６０号に記載の照合方法は、遺留指紋の面積が小さい場合には適用しにくくなる。
【０００７】
そこで、本発明は、特徴点の数が少ない場合、指紋に歪みが生じている場合あるいは照合に用いることができる面積が小さい場合等であっても照合精度を改善できるようにすることを目的とする。
【０００８】
【課題を解決するための手段】
本発明による縞模様画像照合装置は、第一の縞模様画像と第二の縞模様画像とを照合する縞模様画像照合装置であって、各縞模様画像の縞を細線化した線である芯線を示す芯線画素のデータを抽出する芯線抽出手段と、第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定することによって芯線画素同士の対応付け処理を行う対応付け手段と、対応付け手段による対応付け処理が行われた第一の縞模様画像の芯線画素に基づいて第一の縞模様画像と第二の縞模様画像の合致の度合いを評価する評価手段とを備えたことを特徴とする。
【０００９】
評価手段は、例えば、対応付け処理が行われた第一の縞模様画像の芯線画素が連続する長さを芯線毎に計測し、計測した長さに基づいて合致の度合いを評価する。
【００１０】
また、評価手段は、例えば、第一の縞模様画像の画素のうち、対応付け処理が行われた第一の縞模様画像の芯線画素との間に所定の関係を有する画素の数に基づいて、合致の度合いを評価する。
【００１１】
芯線上の特徴点のうち、第一の縞模様画像側と第二の縞模様画像側とで対応付けられる対特徴点を特定する特徴点照合手段を備え、対応付け手段は、対応付け処理の対象となる芯線上に、第一の縞模様画像側と第二の縞模様画像側とで種別が合致する対特徴点が存在する場合に、その対特徴点の画素を起点として第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定していく構成であってもよい。
【００１２】
対応付け手段は、既に対応付けられている対特徴点の画素または芯線画素と、これから対応付け処理を行う第一の縞模様画像の芯線画素および第二の縞模様画像の芯線画素との位置関係に基づいて、第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定することが好ましい。そのような構成によれば、歪みの影響を受けやすい座標値ではなく、他の対特徴点等との位置関係に基づいて対応付け処理を行うので、歪みの影響を少なくすることができる。
【００１３】
また、特徴点照合手段が特定した対特徴点の種別が第一の縞模様画像側と第二の縞模様画像側とで合致するようにいずれか一方の縞模様画像の芯線データを修正する芯線データ修正手段を備え、対応付け手段は、芯線データ修正手段が修正した芯線データを用いて第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定することが好ましい。そのような構成によれば、芯線画素のデータを誤抽出した場合であっても、照合精度を向上させることができる。
【００１４】
芯線データ修正手段は、対向関係にある二つの特徴点の組を排除するように少なくとも第二の縞模様画像の芯線データを修正することが好ましい。そのような構成によれば、対向関係にある二つの特徴点の組を除去できるように芯線を修正するので、照合精度を向上させることができる。
【００１５】
特徴点照合手段は、芯線データ修正手段が修正した芯線データに基づいて再び対特徴点を特定してもよい。
【００１６】
特徴点照合手段が特定した対特徴点の中から、対応付け処理を行う芯線の順番を定める際の基準となるベース対特徴点を決定するベース対特徴点決定手段を備え、対応付け手段は、各芯線とベース対特徴点との位置関係に基づいて芯線の順番を定め、その順番に従って各芯線毎に対応付け処理を行ってもよい。
【００１７】
対応付け手段は、第一の縞模様画像上の点と第二の縞模様画像上の点とが指定された場合に、第一の縞模様画像側と第二の縞模様画像側とで対になる点を、指定された点に基づいて定め、定めた点を含む芯線における芯線画素同士の対応付け処理を行う際には、定めた点を起点として第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定していく構成であってもよい。そのような構成によれば、芯線画素同士の対応付けの精度を向上させることができる。
【００１８】
また、本発明による縞模様画像照合方法は、第一の縞模様画像と第二の縞模様画像とを照合する縞模様画像照合方法であって、各縞模様画像の縞を細線化した線である芯線を示す芯線画素のデータを抽出し、第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定することによって芯線画素同士の対応付け処理を行い、対応付け処理が行われた第一の縞模様画像の芯線画素に基づいて第一の縞模様画像と第二の縞模様画像の合致の度合いを評価することを特徴とする。
【００１９】
例えば、対応付け処理が行われた第一の縞模様画像の芯線画素が連続する長さを芯線毎に計測し、計測した長さに基づいて第一の縞模様画像と第二の縞模様画像の合致の度合いを評価する。
【００２０】
また、例えば、第一の縞模様画像の画素のうち、対応付け処理が行われた第一の縞模様画像の芯線画素との間に所定の関係を有する画素の数に基づいて、第一の縞模様画像と第二の縞模様画像の合致の度合いを評価する。
【００２１】
芯線上の特徴点のうち、第一の縞模様画像側と第二の縞模様画像側とで対応付けられる対特徴点を特定し、対応付け処理の対象となる芯線上に、第一の縞模様画像側と第二の縞模様画像側とで種別が合致する対特徴点が存在する場合に、その対特徴点の画素を起点として第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定していく方法であってもよい。
【００２２】
既に対応付けられている対特徴点の画素または芯線画素と、これから対応付け処理を行う第一の縞模様画像の芯線画素および第二の縞模様画像の芯線画素との位置関係に基づいて、第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定することが好ましい。そのような構成によれば、歪みの影響を受けやすい座標値ではなく、他の対特徴点等との位置関係に基づいて対応付け処理を行うので、歪みの影響を少なくすることができる。
【００２３】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。図１は、本発明による縞模様画像照合装置の例を示すブロック図である。ここでは指紋を照合対象とする場合を例に説明するので、指紋照合装置と記す。本実施の形態の指紋照合装置は、指紋画像入力手段１１と、指紋画像記憶手段１２と、芯線抽出手段１３と、芯線データ記憶手段１４と、特徴点抽出手段１５と、特徴点データ記憶手段１６と、データベース登録手段１７と、データベース記憶手段１８と、特徴点照合手段１９と、対特徴点リスト記憶手段２０と、芯線データ照合手段２１と、照合スコア融合手段２２と、照合結果出力手段２３とを備える。
【００２４】
指紋画像入力手段１１は、指紋センサやスキャナで読み取られた指紋画像をデジタル化して入力する。指紋画像記憶手段１２は、指紋画像入力手段１１から入力された指紋画像を一時記憶する。芯線抽出手段１３は、指紋画像記憶手段１２が記憶する指紋画像に対して二値化処理や細線化処理を行い、芯線データを抽出する。芯線データ記憶手段１４は、芯線抽出手段１３が抽出した芯線データを一時記憶する。特徴点抽出手段１５は、芯線データ記憶手段１４が記憶する芯線データから特徴点のデータを抽出する。特徴点データ記憶手段１６は、特徴点抽出手段１５が抽出した特徴点データを記憶する。
【００２５】
データベース記憶手段１８は、芯線データや特徴点データを記憶する。データベース記憶手段１８は、一時的にデータを記憶するのではなく、データの削除の指示等がない限りデータを保持し続ける。データベース記憶手段１８が記憶する各種データは、新たに照会用の指紋画像が指紋照合装置に入力されたときにその照会用指紋画像の照合に用いられる。以下の説明では、データベース記憶手段１８が記憶する各種データを「ファイル側」または「Ｆ側」と記し、照会用の指紋画像から抽出された各種データを「サーチ側」または「Ｓ側」と記すことにより両者を区別する。
【００２６】
データベース登録手段１７は、芯線データ記憶手段１４が記憶する芯線データや特徴点データ記憶手段１６が記憶する特徴点データをデータベース記憶手段１８に登録する。特徴点照合手段１９は、照会用に入力された指紋画像から抽出されたＳ側特徴点データを特徴点データ記憶手段１６から読み出し、データベース記憶手段１８に登録されているＦ側特徴点データと比較照合し、その類似の度合い（特徴点の照合スコア）を計算する。特徴点照合手段１９によって、一対一に対応付けられた一組のサーチ側特徴点とファイル側特徴点を対特徴点と記す。対特徴点リスト記憶手段２０は、特徴点照合手段１９が計算した対特徴点リストを記憶する。対特徴点リストは、サーチ側とファイル側とで対応付けられた対特徴点の情報の集合である。
【００２７】
芯線データ照合手段２１は、芯線データ記憶手段１４が記憶するサーチ側芯線データと、データベース記憶手段１８が記憶するファイル側芯線データと、対特徴点リスト記憶手段２０が記憶する対特徴点リストとを用いて、サーチ側芯線とファイル側芯線とを比較照合し、芯線の合致の度合い（芯線の照合スコア）を計算する。照合スコア融合手段２２は、特徴点照合手段１９が計算した特徴点の照合スコアと、芯線データ照合手段２１が計算した芯線の照合スコアとを用いて、特徴点と芯線の双方を考慮した類似の度合いを計算する。照合結果出力手段２３は、照合スコア融合手段２２の計算結果を出力する。
【００２８】
また、本発明による指紋照合装置は、入力された指紋画像を鑑識官が修正できるようにしたものであってもよい。図２は、鑑識官がデータの修正を行うことを前提にした場合の指紋照合装置の構成例を示すブロック図である。図１と共通の構成部分については、図１と共通の符号を付して説明を省略する。遺留指紋入力手段３１は、指紋センサやスキャナで読み取られた遺留指紋画像をデジタル化して入力する。遺留画像記憶手段３２は、遺留指紋入力手段３１から入力された指紋画像を一時記憶する。また、遺留トレース入力手段３５は、スキャナで読み取られた遺留指紋トレーシングペーパの情報をデジタル化して入力する。遺留トレース画像記憶手段３６は、遺留トレース入力手段から入力された遺留指紋画像を一時記憶する。
【００２９】
遺留芯線抽出手段３３は、遺留画像記憶手段３２や遺留トレース画像記憶手段３６が記憶する指紋画像に対して二値化処理や細線化処理を行い、芯線データを抽出する。遺留芯線修正手段３４は、遺留芯線抽出手段３３が抽出した芯線データに対する鑑識官の修正作業を支援する。
【００３０】
次に、動作について説明する。
図１に示す指紋画像入力手段１１は、指紋センサやスキャナで読み取られた指紋画像をデジタル化して指紋画像記憶手段１２に一時的に記憶させる。このデジタル化された指紋画像の例を図３（ａ）に示す。図３（ａ）は、５００ｄｐｉの解像度でデジタル化した指紋画像の例であり、米国Ｎａｔｉｏｎａｌ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｓｔａｎｄａｒｄｓ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙで標準化されたＡＮＳＩ／ＮＩＳＴ−ＣＳＬ−１−１９９３　Ｄａｔａ　Ｆｏｒｍａｔ　ｆｏｒ　ｔｈｅ　Ｉｎｔｅｒｃｈａｎｇｅ　ｏｆ　Ｆｉｎｇｅｒｐｒｉｎｔ，　Ｆａｃｉａｌ　＆　ＳＭＴ　Ｉｎｆｏｒｍａｔｉｏｎに従ってデジタル化したものである。以下の実施の形態では、このようにしてデジタル化された指紋画像を例として説明する。
【００３１】
芯線抽出手段１３は、デジタル化された指紋画像に対して二値化処理後、細線化処理を行って芯線データを抽出し、芯線データ記憶手段１４に一時的に記憶させる。この二値化処理や細線化処理は、例えば、特公昭６０−１２６７４号公報およびその米国特許第４３１０８２７号に記載されているような公知の技術によって実現できる。図４（ａ）は、図３（ａ）に示す指紋画像から抽出された芯線データの例である。図４（ａ）に例示する芯線データでは、１６×１６画素の矩形領域毎にデータの信頼度が高いか低いかを示している。この１６×１６画素の矩形領域をゾーン領域または単にゾーンと記す。図４（ａ）では、データ信頼度の低いゾーンが存在する領域（不明領域）を斜線で示している。なお、芯線は個々の黒画素が縦方向、横方向または斜め方向に連続的に並ぶことによって表されるが、図４では滑らかな曲線として示す。図４以降の図面で表した芯線も同様である。
【００３２】
また、図２に示す遺留指紋入力手段３１は、スキャナで読み取られた遺留指紋画像をデジタル化して遺留画像記憶手段３２に一時的に記憶させる。このデジタル化された指紋画像の例を図３（ｂ）に示す。図３（ｂ）は、図３（ａ）と同様に、５００ｄｐｉの解像度でデジタル化した遺留指紋の画像の例である。
【００３３】
また、特に質の低い遺留指紋は、予め鑑識官によって５倍程度に拡大されトレーシングペーパ上にトレースされる。遺留トレース入力手段３５は、このトレーシングペーパ上にトレースされた情報（遺留トレース画像）をスキャンし、その画像をデジタル化して遺留トレース画像記憶手段３６に一時的に記憶させる。
【００３４】
遺留芯線抽出手段３３は、芯線抽出手段１３と同様に、デジタル化された遺留指紋画像や遺留トレース画像に対して二値化処理後、細線化処理を行って芯線データを抽出し、遺留芯線修正手段３４に一時的に記憶させる。図４（ｂ）は、図３（ｂ）に示す指紋画像から抽出された芯線データの例である。
【００３５】
一般に、遺留指紋画像は質が低く、自動抽出できる芯線の範囲は限定される。遺留芯線修正手段３４は、遺留指紋画像等の芯線データに対する鑑識官の修正作業を支援する。この修正方法は、例えば、特開２００２−０７４３８１号に記載されているような公知の技術によって実現される。遺留芯線修正手段３４は、修正後の芯線データを芯線データ記憶手段１４に記憶させる。
【００３６】
芯線データ記憶手段１４が芯線データを記憶した後の動作は、図１，２に示す各構成例で共通である。特徴点抽出手段１５は、芯線データ記憶手段１４から芯線データを読み出し、その芯線データから特徴点（端点および分岐点）のデータを抽出する。この特徴点抽出処理は、例えば、特公昭６０−１２６７４号公報に記載されているような公知の技術によって実現することができる。ただし、不明領域からは特徴点データを抽出しない。
【００３７】
芯線抽出手段１３が抽出した芯線データがファイル側芯線データとして登録すべきデータである場合、データベース登録手段１７は、その芯線データを芯線データ記憶手段１４から読み出しデータベース記憶手段１８に登録する。また、特徴点抽出手段１５が抽出した特徴点データがファイル側特徴点データとして登録すべきデータである場合、データベース登録手段１７は、その特徴点データを特徴点データ記憶手段１６から読み出しデータベース記憶手段１８に登録する。特徴点抽出手段１５が抽出した特徴点データがサーチ側特徴点データである場合、特徴点照合手段１９がその特徴点データを特徴点データ記憶手段１６から読み込む。
【００３８】
特徴点照合手段１９は、サーチ側特徴点データと、予めデータベース記憶手段１８が記憶しているファイル側特徴点データとを照合する。具体的には、対になるべき特徴点同士を対応付け、Ｓ側特徴点とＦ側特徴点との対応関係を示す対特徴点リストを作成する。また、特徴点の照合スコアを算出する。この照合処理は、例えば、特開昭５９−７７８号公報やその米国特許第４６４６３５２号に記載されているような公知の技術によって実現することができる。特徴点照合手段１９は、作成した対特徴点リストを対特徴点リスト２０に記憶させる。
【００３９】
芯線データ照合手段２１は、サーチ側芯線データとファイル側芯線データとを比較照合し、芯線の照合スコアを算出する。まず、芯線データ照合手段２１による芯線データ照合処理の前提事項や処理対象データ等について説明する。
【００４０】
芯線データ照合処理は、対特徴点リストに少なくとも３組の対特徴点が含まれていることを前提とする。芯線データ照合手段２１は、対特徴点リスト記憶手段２１が記憶する対特徴点リストに含まれる対特徴点が２組以下である場合、芯線データ照合処理を中止する。
【００４１】
本実施の形態では、８近傍連結定義の芯線データを処理対象とする。このデータは、芯線上の各点（以下、芯線点と記す。）が存在する画素を黒画素で表し、その画素の８近傍の画素の状況によって点の種別を判別できるようにした芯線データである。芯線点の画素およびその８近傍を示すマスクパターンを図５（ａ）に示す。図５（ａ）に示すマスクパターンにおいて、黒画素となる画素は「１」で表され、白画素となる画素は「０」で表される。すなわち、ｎ＝０〜８としたときに、Ｘｎ＝１となる画素が芯線点となる黒画素であり、Ｘｎ＝０となる画素は芯線点以外の画素である。また、芯線点（Ｘ０）の８近傍（Ｘ１〜Ｘ８）において、黒画素が４画素以上になることはない。すなわち、Ｘ１〜Ｘ８までの画素の値の総和は３以下である。また、このデータにおいて、ある黒画素の８近傍画素の中では、黒画素同士が隣接することはない。例えば、Ｘ１とＸ２の値がともに「１（黒画素）」になることはない。
【００４２】
このマスクパターンによって表される芯線点は、端点、分岐点、連続点および延伸性終点の４つの種別に分類できる。端点（以下、「Ｅ」と表す。）は、図５（ｂ）に示すように、８近傍画素中に黒画素が一個しかない芯線点である。分岐点（以下、「Ｂ」と表す。）は、図５（ｃ）に示すように、８近傍画素中に黒画素が三個あり、かつ、その三個の黒画素から取り出した任意の二個の画素の間には必ず白画素が存在する芯線点である。連続点（以下、「Ｃ」と表す。）は、図５（ｄ）に示すように、８近傍画素中に黒画素が二個あり、かつ、その二個の画素の間に白画素が存在する芯線点である。また、延伸性終点（以下、「Ｘ」と表す。）は、本来芯線が延伸していると考えられる連続点である。このうち、端点Ｅおよび分岐点Ｂが特徴点である。連続点Ｃは、特徴点でもなく延伸性終点Ｘでもない全ての芯線点である。
【００４３】
指紋隆線の交差が発現することは極めてまれである。芯線データを抽出する際には、芯線の交差を示すマスクパターンを取り除く。例えば、図６（ａ）の左側に示すようなマスクパターンが生じた場合、芯線抽出手段１３は、そのマスクパターンを図６（ａ）の中央または右側に示すようなマスクパターンに修正する。すなわち、交差箇所を二つの分岐点Ｂに修正する。図６（ｂ）に示すように、Ｘ１，Ｘ３，Ｘ５およびＸ７が「１」となっている場合には、二つの分岐点に修正できないものとして照合範囲から除外する。すなわち、図６（ｂ）に示す交差箇所を含むゾーン領域を不明領域とする。
【００４４】
また、本来延伸している隆線が押捺されなかった結果、一見端点のように見える点を印象端という。芯線抽出手段１３は、印象端や、印象端と同様にある地点から先の芯線構造が判別できなくなる画素を含むゾーン領域も不明領域とする。延伸性終点Ｘは、「不明領域に進入する直前の芯線点」として定義される。
【００４５】
個々の画素の８近傍の状況は、１バイトのデータで表す。すなわち、マスクパターンのＸ１を０ビット目としＸ８までの値を順に並べたものを１バイトのデータで表す。図７（ａ）は、このようにして表した１バイトのデータの例を示す。また、１バイトのデータとして表された８近傍のデータをＣｏｄｅ８またはＣ８と呼ぶ。図７（ｂ）は、Ｃ８の例を示す。例えば、８近傍のうちＸ１のみが「１」である場合、Ｃ８は「０００００００１」であるので、Ｃ８の値は１となる。
【００４６】
図８は、芯線データの表現例を示す説明図である。芯線データは、ユニットの集合として表す。ユニットとは、端点Ｅ、分岐点Ｂまたは延伸性終点Ｘのいずれかを開始点及び終点とする芯線の最小単位である。例えば、図８に示すユニット１は、延伸性終点Ｘを開始点とし、端点Ｂを終点として、その間に連続点Ｃが存在する芯線の単位である。図８に示すＸ，Ｙは各芯線点の画素の座標を表す。図８に示すように芯線データでは、芯線点の種別（Ｔｙｐｅ）と座標とＣｏｄｅ８とが画素毎に対応付けられている。
【００４７】
次に、芯線データ照合処理の概要を説明する。図９は、芯線データ照合処理の概要を示す流れ図である。芯線データ照合手段２１は、最初に対特徴点リスト、Ｓ側芯線データおよびＦ側芯線データを読み込んで、芯線データ照合手段２１が用いる内部メモリ上に展開する。また、必要なメモリ領域（例えばワークテーブルとして用いるメモリ領域等）を確保する（ステップＡ０）。ステップＡ０は、芯線データ照合処理の準備段階である。
【００４８】
なお、芯線データ照合手段２１は、特徴点照合手段１９が作成した対特徴点リストを対特徴点リスト記憶手段２０から読み込む。この対特徴点リストにおいて、対をなすＳ側対特徴点とＦ側対特徴点の種別が合致しているとは限らない。以下の説明では、対特徴点であって、Ｓ側の種別とＦ側の種別が合致しているものを合致特徴点と定義する。一般に「合致特徴点」という用語を「対特徴点」と同義としてとらえ、種別が合致していなくても「合致特徴点」という語を用いる場合もある。しかし、以下の説明では、対特徴点のうち種別が合致したものを「合致特徴点」と呼ぶ。
【００４９】
以下に示すステップＡ１〜Ａ４において、複数のデータから適切なデータを選別するときには、個々のデータについて不適切さの度合いを示す数値を割り当てる。この数値をペナルティと記す。
【００５０】
ステップＡ０の後、芯線データ照合手段２１は、ベース対特徴点（以下、ＢＰＭと記す。）を決定する（ステップＡ１）。ＢＰＭは、各芯線点や各ユニット等を選択するときに、選択順序を定めるための基準となる対特徴点である。
【００５１】
ステップＡ１の後、芯線データ照合手段２１は、サーチ側とファイル側とで、個々の対特徴点の種別が合致するようにファイル側芯線データを修正する。同時に、対特徴点リストに含まれるファイル側特徴点の種別情報も修正する（ステップＡ２）。芯線データ照合手段２１は、芯線データ等の修正の度合いに応じたペナルティをカウントする。ファイル側のデータの修正ができないような大きな食い違いが生じている対特徴点が存在する場合、芯線データ照合手段２１は、その対特徴点を対特徴点リストから削除する。また、後述するように、ステップＡ１では、Ｆ側の芯線データとして複数種類の芯線データを作成する場合がある。このような場合、ステップＡ２では、ペナルティに基づいて、修正の度合いが少ない方のデータを選別する。
【００５２】
また、Ｓ側とＦ側とで対になっていない特徴点がいわゆる「ひげ」や「切断」等の芯線状態を生じさせている場合がある。芯線データ照合手段２１は、その芯線状態を除去するように芯線データを修正する。
【００５３】
続いて、芯線データ照合手段２１は、サーチ側の各芯線点について、対応する芯線点がファイル側に存在するか否かを判断する。そして、対応する芯線点があれば、サーチ側の芯線点とファイル側の芯線点とを対応付ける（ステップＡ３）。ステップＡ３の結果、特徴点だけでなく、連続点Ｃや延伸性終点Ｘについても対応付けが行われる。なお、サーチ側とファイル側とで対応付けられた対になる芯線点の情報の集合を芯線点対応リストと記す。
【００５４】
次に、芯線データ照合手段２１は、対応付けられた芯線点が連続する長さ（芯線距離）を測る。芯線データ照合手段２１は、Ｓ側とＦ側とで対応付けられた芯線（以下、合致芯線と記す。）毎に、芯線距離を測り、その総和を求める。そして、その総和と、ステップＡ１以降にカウントしたペナルティとに基づいて芯線の照合スコアを算出する。
【００５５】
なお、縦または横方向に隣接する画素１個分が距離単位になる。従って、斜め方向に隣接する画素への距離は約１．４画素（√２画素）である。
【００５６】
芯線データ照合処理のステップＡ１〜Ａ４毎に、各ステップにおける処理を詳しく説明する。図１０は、ステップＡ１（ＢＰＭ決定処理）の処理経過を示す流れ図である。芯線データ照合手段２１は、対特徴点の種別が合致することを重要な判断基準として、以下のようにＢＰＭを決定する。芯線データ照合手段２１は、対特徴点の中から合致特徴点を全て取り出し、番号を割り当てる（ステップＡ１０１）。番号が割り当てられた合致特徴点をマーク対特徴点と呼び、ＭＰＭ（ｎ）と表すことにする。ＭＰＭ（ｎ）における「ｎ」は、割り当てられた番号である。なお、割り当てた番号の最大値はＮであるとする。また、芯線データ照合手段２１はｋ＝１という初期値を設定する。ｋは、全てのＭＰＭ（ｎ）中から各マーク対特徴点を順番に選択していくための変数であり、選択したマーク対特徴点（注目マーク対特徴点）はＭＰＭ（ｋ）として表される。一つのマーク対特徴点を選択し終えた場合、ｋを１増加させる。また、芯線データ照合手段２１は、ｍ＝１およびＰ（ｍ）＝１００という初期値を設定する。ｍは、ペナルティが最小のマーク対特徴点を特定するための変数である。Ｐ（ｍ）は、マーク対特徴点毎のペナルティの最小値である。ここではＰ（ｍ）の初期値を１００としたが、Ｐ（ｍ）の初期値はＰ（ｋ）に比べ十分に大きな値であればよい。なお、選択された対特徴点等であることを「注目」という語によって表すものとする。
【００５７】
芯線データ照合手段２１は、ステップＡ１０１の後、全てのＭＰＭ（ｎ）に対する選択を終えたか否かを判断する（ステップＡ１０２）。ｋ＞Ｎを満足する場合、全てのＭＰＭ（ｎ）を選択し終えたと判断する。ｋ＞Ｎを満足していない場合、芯線データ照合手段２１は、Ｐ（ｋ）＝０という初期値を設定する（ステップＡ１０３）。Ｐ（ｋ）は、注目マーク対特徴点ＭＰＭ（ｋ）に対応するペナルティである。
【００５８】
続いて、芯線データ照合手段２１はｊ＝１という初期値を設定する（ステップＡ１０４）。ｊは、ＭＰＭ（ｋ）の近傍のマーク対特徴点を順番に選択していくための変数であり、選択した近傍のマーク対特徴点（注目近傍対特徴点）はＭＰＭ（ｊ）として表される。なお、ｋ＝１である場合には、ｊの初期値を２とする。ｋ＝１の場合、ｊの初期値を２とすることで、ＭＰＭ（ｋ）とＭＰＭ（ｊ）とが同一の対特徴点になってしまうことを防ぐことができる。
【００５９】
芯線データ照合手段２１は、ステップＡ１０４の後、近傍の各マーク対特徴点に対する選択を終えたか否かを判断する（ステップＡ１０５）。ｊ＞Ｎを満足する場合、近傍の各対特徴点に対する選択を終えたと判断する。ｊ＞Ｎを満足しない場合、芯線データ照合手段２１は、サーチ側芯線データに基づいて、注目マーク対特徴点ＭＰＭ（ｋ）と注目近傍対特徴点ＭＰＭ（ｊ）とを結ぶ線分（サーチ側における線分）が隆線と交差する数ｒＳを求める（ステップＡ１０６）。また、芯線データ照合手段２１は、ファイル側芯線データに基づいて、注目マーク対特徴点ＭＰＭ（ｋ）と注目近傍対特徴点ＭＰＭ（ｊ）とを結ぶ線分（ファイル側における線分）が隆線と交差する数ｒＦを求める（ステップＡ１０７）。
【００６０】
ステップＡ１０７の後、芯線データ照合手段２１は、隆線との交差数ｒＳおよびｒＦに差があるか否かを判断する（ステップＡ１０８）。ｒＳ＝ｒＦであれば、ｊの値を１増加させる（ステップＡ１１０）。ただし、ｊ＝ｋとなるのであれば、ｊの値をさらに１増加させる。
【００６１】
ステップＡ１０８において、隆線との交差数に差がある場合（ｒＳ≠ｒＦの場合）、注目近傍対特徴点ＭＰＭ（ｊ）に応じたペナルティを求め、そのペナルティをＰ（ｋ）に加算する（ステップＡ１０９）。注目近傍対特徴点ＭＰＭ（ｊ）に応じたペナルティは、｜ｒＳ−ｒＦ｜／ｍａｘ（ｍｉｎ（ｒＳ，ｒＦ），１）という計算式によって算出する。この式において、ｍａｘおよびｍｉｎはそれぞれ括弧内の数値の最大値および最長値を指定するものとする。Ｐ（ｋ）を更新後、芯線データ照合手段２１はステップＡ１１０の処理（ｊの増加）を行い、ステップＡ１０５以降の動作を繰り返す。
【００６２】
また、ステップＡ１０５において、近傍の各マーク対特徴点に対する選択を終えたと判断した場合、芯線データ照合手段２１は、それまでのペナルティの最小値Ｐ（ｍ）と、注目マーク対特徴点ＭＰＭ（ｋ）のペナルティＰ（ｋ）とを比較する（ステップＡ１１１）。Ｐ（ｋ）＜Ｐ（ｍ）ならば、Ｐ（ｍ）をＰ（ｋ）の値で更新し、ｍをｋの値で更新する。また、Ｐ（ｋ）＝Ｐ（ｍ）ならば、ｍによって特定されるＭＰＭ（ｍ）と注目マーク対特徴点ＭＰＭ（ｋ）とついて、どちらがサーチ側対特徴点群の重心座標に近いかを判断する。ＭＰＭ（ｋ）の方が近いならば、Ｐ（ｍ）およびｍをそれぞれＰ（ｋ）およびｋの値で更新する。Ｐ（ｋ）＞Ｐ（ｍ）であれば更新しない。芯線データ照合手段２１は、ステップＡ１１１の後、ｋの値を１増加させ、次のマーク対特徴点を選択する（ステップＡ１１２）。その後のステップＡ１０２において、ｋ＞Ｎと判断したならば、全てのマーク対特徴点を選択したことになる。この時点におけるｍは、最もペナルティが少ないマーク対特徴点を特定する番号である。従って、芯線データ照合手段２１は、このｍによって特定されるＭＰＭ（ｍ）をＢＰＭとして決定する（ステップＡ１１３）。
【００６３】
図１０に示したＢＰＭ決定処理は、対特徴点の中に合致特徴点が存在しない場合、適用することができない。従って、そのような場合には以下に示す例外処理によってＢＰＭを決定する。全ての対特徴点で、Ｓ側の種別とＦ側の種別とが異なっている場合、Ｓ側対特徴点群の重心座標に最も近い対特徴点をＢＰＭ候補に選ぶ。このＢＰＭ候補は、Ｓ側とＦ側とで種別が異なるため、種別に応じた処理を行う。
【００６４】
ＢＰＭ候補となるＳ側対特徴点の種別が端点Ｅであり、Ｆ側対特徴点の種別が分岐点Ｂである場合、Ｆ側の分岐点Ｂを端点Ｅに変化させる。そして、この端点ＥをＳ側の端点Ｅと対にしてＢＰＭとする。図１１は、Ｆ側の分岐点（ＢＰＭ候補となる分岐点）を端点に変化させる状況を示す説明図である。図１１に示すように、左右に分岐する芯線のどちらを分離するかによって二種類の芯線データと二種類の対特徴点リストができる。芯線データ照合手段２１は、この二種類の芯線データそれぞれを作成して保持する。二種類の芯線データのどちらにおいても端点をＢＰＭとして定める。なお、特徴点方向をＹ軸正方向とした場合に、Ｘ軸正方向を向く側が右、Ｘ軸負方向を向く側が左と定義している。また、特徴点方向は、ＮＩＳＴデータ交換標準定義（サブセクション１６．１．４）において定義されている。分岐点の場合、その分岐点から、分岐する二本のユニットの中間に向かう方向が特徴点方向になる。端点の場合、端点から伸びる芯線の方向が特徴点方向になる。
【００６５】
ＢＰＭ候補となるＳ側対特徴点の種別が分岐点Ｂであり、Ｆ側対特徴点の種別が端点Ｅである場合、Ｆ側の端点Ｅを分岐点Ｂに変化させる。そして、この分岐点ＢとＳ側の分岐点Ｂとを対にしてＢＰＭとする。この場合、端点を形成する芯線を左右どちら側の芯線に接合させて分岐点を形成するかによって、二種類の芯線データと二種類の対特徴点リストができる。芯線データ照合手段２１は、この二種類の芯線データそれぞれを作成して保持する。二種類の芯線データのどちらにおいても分岐点をＢＰＭとして定める。
【００６６】
この例外処理によって二種類の芯線データが作成された場合、その芯線データをそれぞれＦ−Ｓｋｅｌ（１）、Ｆ−Ｓｋｅｌ（２）と記すことにする。
【００６７】
次に、図９に示すステップＡ２の処理について説明する。このステップＡ２の処理は、３つのサブステップに分かれる。最初のサブステップＡ２−１は、対特徴点のうち合致特徴点でないものについて、種別を合わせるようにファイル側芯線データおよび対特徴点リストを修正する処理である。二番目のサブステップＡ２−２は、Ｓ側とＦ側とで対にならない特徴点であって、対向関係にある特徴点をＦ側芯線データから削除する処理である。対向関係とは、特徴点方向が互いに逆方向を向き、指紋照合上好ましくない芯線状態を生じさせる関係にあることをいう。対向関係にある対特徴点の例を図１２（ａ）に示す。図１２（ａ）において、丸く示した部分が特徴点であり、特徴点から伸びる太線の方向が特徴点方向である。特徴点から伸びる細線は芯線を示す。三番目のサブステップＡ２−３は、Ｓ側とＦ側とで対にならない特徴点であって、対向関係にある特徴点をＳ側芯線データから削除する処理である。
【００６８】
図１３は、サブステップＡ２−１の処理経過を示す流れ図である。サブステップＡ２−１は、ＢＰＭが合致特徴点であることを前提とする。Ｆ側芯線データが二種類存在する場合、芯線データ照合手段２１はｋ＝１という初期値を設定する（ステップＡ２０１）。サブステップＡ２−１で用いるｋは、Ｆ−Ｓｋｅｌ（１）およびＦ−Ｓｋｅｌ（２）を順番に選択していくための変数であり、選択している芯線データは、Ｆ−Ｓｋｅｌ（ｋ）として表される。また、芯線データ照合手段２１は、ｍ＝１およびＰ（ｍ）＝１００という初期値を設定する。ｍは、ペナルティが最小のＦ−Ｓｋｅｌ（ｋ）を特定するための変数である。Ｐ（ｍ）は、Ｆ−Ｓｋｅｌ（ｋ）毎のペナルティの最小値である。ここではＰ（ｍ）の初期値を１００としたが、Ｐ（ｍ）の初期値はＰ（ｋ）に比べ十分に大きな値であればよい。
【００６９】
芯線データ照合手段２１は、ステップＡ２０１の後、Ｆ−Ｓｋｅｌ（１）およびＦ−Ｓｋｅｌ（２）に対する選択を終えたか否かを判断する（ステップＡ２０２）。ｋ＞２を満足する場合、Ｆ−Ｓｋｅｌ（１）およびＦ−Ｓｋｅｌ（２）を選択し終えたと判断する。ｋ＞２を満足していない場合、芯線データ照合手段２１は、Ｐ（ｋ）＝０という初期値を設定する（ステップＡ２０３）。Ｐ（ｋ）は、注目しているＦ−Ｓｋｅｌ（ｋ）に対応するペナルティである。
【００７０】
ステップＡ２０３に続いて、芯線データ照合手段２１は、これから順番に各対特徴点を選択していくときの順位付けを行う（ステップＡ２０４）。また、ｊ＝１という初期値を設定する。ｊは、各対特徴点を順番に選択していくための変数であり、選択した対特徴点（注目対特徴点）はＰＭ（ｊ）として表すことにする。
【００７１】
芯線データ照合手段２１は、ステップＡ２０４の後、各対特徴点に対する選択を終えたか否かを判断する（ステップＡ２０５）。ｊ＞Ｎを満足する場合、各対特徴点に対する選択を終えたと判断する。ｊ＞Ｎを満足しない場合、芯線データ照合手段２１は、サーチ側において、ＢＰＭと注目対特徴点ＰＭ（ｊ）とを結ぶ線分（サーチ側における線分）が隆線と交差する数ｒＳを求める（ステップＡ２０６）。また、芯線データ照合手段２１は、ファイル側において、ＢＰＭと注目対特徴点ＰＭ（ｊ）とを結ぶ線分が（ファイル側における線分）隆線と交差する数ｒＦを求める（ステップＡ２０７）。
【００７２】
ステップＡ２０７の後、芯線データ照合手段２１は、ステップＡ２０６，Ａ２０７で求めたｒＳ，ｒＦに差が生じているかを判断し、また、注目対特徴点のＳ側とＦ側とで種別が異なっているか否かを判断する（ステップＡ２０８）。ｒＳとｒＦに差がなく、かつ、注目対特徴点のＳ側とＦ側とで種別が一致している場合には、ｊの値を１増加させる（ステップＡ２１０）。
【００７３】
ステップＡ２０８において、ｒＳ≠ｒＦであると判断したり、または、注目対特徴点のＳ側とＦ側とで種別が異なると判断した場合、芯線データ照合手段２１は、ファイル側芯線データを修正し、修正内容に応じてペナルティＰ（ｋ）をカウントする（ステップＡ２０９）。このとき、芯線データ照合手段２１は、注目対特徴点のＳ側とＦ側とで種別が一致し、ＢＰＭと注目対特徴点ＰＭ（ｊ）との間に存在する隆線の数がＳ側とＦ側とで等しくなるようにファイル側芯線データを修正する。また、芯線データ照合手段２１は、ファイル側芯線データだけでなく対特徴点リストに含まれるファイル側の特徴点のデータも修正する。
【００７４】
図１４は、ステップＡ２０９における修正内容を規定するルールの一覧表である。芯線データ照合手段２１は、図１４に示すルールに従い、ファイル側芯線データ等を修正し、ペナルティＰ（ｋ）をカウントする。図１４に示すように、修正内容およびペナルティの値は、ｒＦとｒＳの差、Ｓ側注目対特徴点の種別およびＦ側注目対特徴点の種別によって定められる。例えば、Ｓ側の注目対特徴点の種別が端点Ｅであり、Ｆ側の注目対特徴点の種別が分岐点Ｂであるとする。この場合、ｒＦ−ｒＳ＝０であるなら、Ｆ側注目対特徴点（分岐点）について「ＢＰＭに近い方の芯線を分離する」ように修正を行い、Ｐ（ｋ）に１を加算する。また、ｒＦ−ｒＳ＝−１であるならば、Ｆ側注目対特徴点（分岐点）について「ＢＰＭに遠い方の芯線を分離する」ように修正を行い、Ｐ（ｋ）に１を加算する。また、ｒＦ−ｒＦ＝１であるならば、注目対特徴点ＰＭ（ｊ）のデータを「対特徴点リストから削除する」修正を行い、Ｐ（ｋ）に５を加算する。
【００７５】
ここでは、図１４に示すルールのうち、Ｓ側注目対特徴点の種別が端点Ｅであり、Ｆ側注目対特徴点の種別が分岐点Ｂである場合を例に説明したが、他の場合であっても、同様に修正内容とペナルティとが定められる。なお、ＢＰＭと注目対特徴点間の隆線数がＳ側とＦ側とで一致するように修正できる場合には、ペナルティが小さくなるように定めている。
【００７６】
図１５は（ａ）は、Ｆ側の注目対特徴点が分岐点である場合に、この分岐点を端点に修正する状況を示している。分岐点から分かれる二本の芯線のうち、ＢＰＭに近い方の芯線またはＢＰＭから遠い方の芯線を分離することにより、分岐点を端点に変化させることができる。どちらに分離するかによって、ＢＰＭとＦ側注目対特徴点とを結ぶ線分が隆線に交差する数が異なる。どのように芯線を分離するのかは、図１４に示すルールに従って決定される。
【００７７】
図１５（ｂ）は、Ｆ側の注目対特徴点が端点である場合に、この端点を分岐点に修正する状況を示す。端点を形成する芯線を、ＢＰＭに近い方の芯線またはＢＰＭから遠い方の芯線に接合することにより、端点を分岐点に変化させることができる。どちらに接合するかによって、ＢＰＭとＦ側注目対特徴点とを結ぶ線分が隆線に交差する数が異なる。どのように接合するのかは、図１４に示すルールに従って決定される。
【００７８】
図１６は、Ｓ側、Ｆ側ともに注目対特徴点の種別が端点であるが、ｒＳ≠ｒＦであるためにＦ側の注目対特徴点を修正する状況を示す。図１６（ａ）は、ＢＰＭとＦ側注目対特徴点との間に存在する隆線がＳ側より一本少ないため、隆線を一本増加させるように修正する例を示す。図１６（ａ）に示すように、ＢＰＭに遠い方の芯線に端点を接合し、その後、分岐する芯線のうちＢＰＭから遠い方の芯線を分離すれば、隆線を一本増加させることができる。図１６（ｂ）は、ＢＰＭとＦ側注目対特徴点との間に存在する隆線がＳ側より一本多いため、隆線を一本減少させるように修正する例を示す。図１６（ｂ）に示すように、ＢＰＭに近い方の芯線に端点を接合し、その後、分岐する芯線のうちＢＰＭに近い方の芯線を分離すれば、隆線を一本減少させることができる。
【００７９】
図１７は、Ｓ側、Ｆ側ともに注目対特徴点の種別が分岐点であるが、ｒＳ≠ｒＦであるためにＦ側の注目対特徴点を修正する状況を示す。図１７（ａ）は、ＢＰＭとＦ側注目対特徴点との間に存在する隆線がＳ側より一本少ないため、隆線を一本増加させるように修正する例を示す。図１７（ａ）に示すように、分岐する芯線のうちＢＰＭから遠い方の芯線を分離し、その結果得られた端点をＢＰＭから遠い方の芯線に接合すれば、隆線を一本増加させることができる。図１７（ｂ）は、ＢＰＭとＦ側注目対特徴点との間に存在する隆線がＳ側より一本多いため、隆線を一本減少させるように修正する例を示す。図１７（ｂ）に示すように、分岐する芯線のうちＢＰＭに近い方の芯線を分離し、その結果得られた端点をＢＰＭに近い方の芯線に接合すれば、隆線を一本減少させることができる。
【００８０】
芯線データ照合手段２１は、図１４に示すルールに従って、図１５〜１７に示すような修正を行う。そして、修正に応じたペナルティをＰ（ｋ）に加算し、ステップＡ２０９の処理を終了する。ステップＡ２０９の後、芯線データ照合手段２１はステップＡ２１０の処理（ｊの増加）を行い、ステップＡ２０５以降の動作を繰り返す。
【００８１】
また、ステップＡ２０５において、各対特徴点の選択を終えたと判断した場合、芯線データ照合手段２１は、それまでのペナルティの最小値Ｐ（ｍ）と、選択したＦ−Ｓｋｅｌ（ｋ）のペナルティＰ（ｋ）とを比較する（ステップＡ２１１）。Ｐ（ｋ）＜Ｐ（ｍ）ならば、Ｐ（ｍ）をＰ（ｋ）の値で更新し、ｍをｋの値で更新する。Ｐ（ｋ）≧Ｐ（ｍ）であれば更新しない。その後、芯線データ照合手段２１は、ｋの値を１増加させ、次のＦ−Ｓｋｅｌ（ｋ）を選択する（ステップＡ２１２）。その後のステップＡ２０２において、ｋ＞２と判断したならば、Ｆ−Ｓｋｅｌ（１）およびＦ−Ｓｋｅｌ（２）のどちらについても選択を完了したことになる。この時点におけるｍが、ペナルティの少ない方の芯線データを特定する番号である。芯線データ照合手段２１は、このｍによって芯線データＦ−Ｓｋｅｌ（ｍ）を特定し、また、このＦ−Ｓｋｅｌ（ｍ）に対応する対特徴点リストを特定する（ステップＡ２１３）。ステップＡ２１３で、サブステップＡ２−１の処理は終了する。以降の処理では、ステップＡ２１３で特定したＦ−Ｓｋｅｌ（ｍ）および対特徴点リストを処理対象とする。
【００８２】
次に、サブステップＡ２−２，Ａ２−３について説明する。図１８は、サブステップＡ２−２，Ａ２−３の処理経過を示す流れ図である。サブステップＡ２−２では、Ｓ側と対にならない特徴点であって、対向関係にある特徴点をＦ側の芯線データの中から削除する。まず、芯線データ照合手段２１は、サブステップＡ２−１によって特定したＦ側の芯線データの中から、図１２（ａ）に例示するような対向関係をなす特徴点（対向特徴点）の組を抽出し、抽出した各対向特徴点の組を順番付ける（ステップＡ２２１）。ステップＡ２２１において、対向特徴点の組を全て抽出するのは非効率的である。そこで、対向特徴点の組のうち、合致特徴点から所定の範囲内（例えば６４画素以内）に存在するもののみを抽出すればよい。
【００８３】
続いて、芯線データ照合手段２１は、抽出した全ての対向特徴点に対する処理が終了したか否かを判断する（ステップＡ２２２）。修正処理が終了していなければ、順番に従って、一つの対向特徴点の組を選び、その組に対する処理を行う（ステップＡ２２３）。ステップＡ２２３では、選ばれた対向特徴点と対になる特徴点がＳ側に存在するかを判断する。そして、対になる特徴点がＳ側になければ、対向特徴点を削除するように修正する（ステップＡ２２３）。図１２（ｂ）は、対向特徴点を削除するための修正策をまとめた一覧表である。また、対向特徴点を削除する修正を行った場合、サブステップＡ２−１において最終的に得られたＰ（ｍ）に、修正内容に応じたペナルティを加算していく。例えば、「ひげ」の場合には、図１２（ｂ）に示すように「ひげ」となる芯線を削除する。そして、削除した芯線長に所定の係数を乗じた値をペナルティとしてＰ（ｍ）に加算する。
【００８４】
滑らかに接続する修正は、例えば、特開２００２−７４３８１公報に記載されているような公知の技術によって実現することができる。「短区間接触」や「ねじれ切断」や「ねじれ接触」等において、滑らかな芯線接続を行うためには、対向特徴点間の芯線を削除するだけではなく、隆線幅程度の長さで端点の部分を短縮する方策が有効である。
【００８５】
なお、対向特徴点を排除するための方策としては様々な方策が知られている。例えば、米国特許第６０７２８９５号に芯線データ抽出後に特徴点を削除する方策が提案されている。また、米国特許第４６４６３５２号では、特徴点照合時に対向特徴点を無視する方策が記載されている。
【００８６】
ステップＡ２２３の後、芯線データ照合手段２１は、次の芯線修正候補となる対向特徴点の組を選び（ステップＡ２２４）、ステップＡ２２２以降の動作を繰り返す。抽出した全ての対向特徴点に対して修正処理が終了した場合（ステップＡ２２２）、サブステップＡ２−２は終了する。
【００８７】
サブステップＡ２−２の後、芯線データ照合手段２１は、サブステップＡ２−３を開始する。サブステップＡ２−３では、Ｆ側と対にならない特徴点であって、対向関係にある特徴点をＳ側の芯線データの中から削除する。サブステップＡ２−３の処理内容は、サブステップＡ２−２と同様である。図１８に示すステップＡ２３１，Ａ２３２，Ａ２３３，Ａ２３４は、それぞれステップＡ２２１，Ａ２２２，Ａ２２３，Ａ２２４と同様の処理である。
【００８８】
サブステップＡ２−３でステップＡ２の処理は終了する。図１９は、ステップＡ２の処理によるＦ側芯線の変化を示す。ステップＡ２の終了時には、対特徴点リストにのっている対特徴点は、全てＳ側の種別とＦ側の種別が一致する。以上でステップＡ２に関する説明を終える。
【００８９】
次に、図９に示すステップＡ３の処理について説明する。ステップＡ３では、Ｓ側の各芯線点について、Ｆ側に対応する芯線点があるか否かを調査する。既述のように、サーチ側とファイル側とで対応付けられた対になる芯線点の情報の集合を芯線点対応リストという。図２０は、芯線点対応リストの例を示す。芯線データ照合手段２１は、芯線点対応リストを作成し、芯線点の対応関係の調査を進めながら芯線点対応リストを更新していく。
【００９０】
芯線データ照合手段２１は、Ｓ側のユニット（芯線の最小単位）を一つ一つ選択し、さらに選択したユニット上の一つ一つの芯線点を選択する。そして、選択した芯線点からＦ側への対応を調べる。Ｓ側からユニット等を選択するのは、一般にサーチ側とする遺留指紋は領域面積が小さく、特徴点が少ないからである。以下の説明では、Ｓ側において選択したユニット（Ｆ側との対応を調査しているユニット）を注目芯線と記す。また、注目芯線上の芯線点であって、Ｆ側との対応関係を調べるために選択している芯線点を注目芯線点あるいは単に注目点と記す。注目点に対応するＦ側の対応点が存在した場合、その注目点と対応点とを合致芯線点と記す。注目芯線上にない合致特徴点や合致芯線点を参照点と記す。参照点は、注目点の対応関係を調べる際に利用される。
【００９１】
図２１は、ステップＡ３（芯線点の対応付け処理）の処理経過の例を示す流れ図である。Ｓ側の各ユニットをＳ−Ｕｎｉｔ（ｎ）と表すことにする。Ｓ−Ｕｎｉｔ（ｎ）における「ｎ」は、Ｓ側のユニットを選択するときの順位を表す番号である。Ｓ側のユニットの総数をＮ本とすれば、１≦ｎ≦Ｎが成立する。芯線データ照合手段２１は、ステップＡ３を開始すると、Ｓ側の各ユニットの順位付けを行う（ステップＡ３０１）。また、ｋ＝１という初期値を設定する。ステップＡ３におけるｋは、Ｓ側の各ユニットを順番に選択していくための変数であり、選択したユニットはＳ−Ｕｎｉｔ（ｋ）と表される。
【００９２】
Ｓ側の各ユニットの順位を定めるときの基準について説明する。ＢＰＭに接続しているユニットが先に選択されるように順位を決定する。ＢＰＭが端点のときは、ＢＰＭに接続しているユニットの順位を１位として定める。
【００９３】
ＢＰＭが分岐点のときは、その分岐点を端点とみなし、その端点に接続する三つのユニットの順位を決定する。このとき、（１）もう片方に合致特徴点があるユニット、（２）特徴点方向と反対方向に伸びるユニット、（３）特徴点方向のすぐ右側に位置するユニット、（４）特徴点方向のすぐ左側に位置するユニットの順番に順位が低くなるように定める。なお、「右」、「左」の方向は既に説明した通りである。
【００９４】
図２２は、分岐点となるＢＰＭに接続するユニットの順位付けの例を示す説明図である。図２２（ａ）に示す例では、「優先順１位」のユニットは、もう片方に合致特徴点があるため上記（１）に該当し１位となる。図２２（ａ）における「優先順２位」のユニットは、ＢＰＭにおける特徴点方向（ＢＰＭから、分岐する二本のユニットの中間に向かう方向）の反対方向に伸びるため上記（２）に該当し２位となる。
【００９５】
図２２（ｂ）に示す例では、上記（１）に該当するユニットは存在しない。従って、ＢＰＭにおける特徴点方向の反対方向に伸びるユニットを「優先順１位」として示している。また、ＢＰＭにおける特徴点方向のすぐ右側に位置するユニットを「優先順位２」として示している。
【００９６】
ＢＰＭに接続しているユニットについて順位を付けたならば、ＢＰＭに近い順に合致特徴点を選んでいく。そして、ＢＰＭに近い合致特徴点から順番に、その合致特徴点に接続するユニットについて順位を定める。ＢＰＭ以外の合致特徴点に接続するユニットに対する順位付けは、ＢＰＭに接続するユニットに対する順位付けと同様である。すなわち、合致特徴点が端点のときは、その端点に接続しているユニットに順位を付ける。合致特徴点が分岐点のときは、その分岐点を端点とみなし、その端点に接続する三つのユニットに対して、上記（１）〜（４）の順番に順位が低くなるように順位を定める。図２３は、ＢＰＭ以外の合致特徴点に対する順位付けの例を示す。図２３に示すように、ＢＰＭ以外の合致特徴点に対して、ＢＰＭに近い順に順位を定める。この例では分岐点がないため、合致特徴点の順序がそのまま合致特徴点に接続するユニットの順位となる。
【００９７】
続いて、合致特徴点に接続しないユニットについて順位を定める。合致特徴点に接続しないユニットに対しては、ＢＰＭに近いほど順位が高くなるように順位を定める。図２４は、合致特徴点に接続しないユニットに対する順位付けの例を示す。図２４に示すように、ＢＰＭに近いほど順位が高くなる。合致特徴点に接続しないユニットについては、ファイル側に対応するユニットが存在するとは限らない。あるいは、ファイル側の複数のユニットが対応する場合もある。なお、図２４では、優先順４位までのユニットのみを例示している。
【００９８】
芯線データ照合手段２１は、Ｓ側の各ユニットに対する順位付けを行ったならば、順位を定めた各ユニットの芯線点について、Ｆ側との対応付け処理を終えたか否かを判断する（ステップＡ３０２）。ｋ＞Ｎであるならば、Ｆ側との対応付け処理が終了したと判断し、ステップＡ４に進む。ｋ≦Ｎであれば、注目芯線Ｓ−Ｕｎｉｔ（ｋ）に合致特徴点が存在するか否かを判断する（ステップＡ３０３）。この判断結果は、次の三つのケースに分類される。第一のケースは、注目芯線Ｓ−Ｕｎｉｔ（ｋ）の片端のみが合致特徴点（ＢＰＭ含む）となっているケースである。第二のケースは、Ｓ−Ｕｎｉｔ（ｋ）の両端が合致特徴点（ＢＰＭ含む）となっているケースである。第三のケースは、Ｓ−Ｕｎｉｔ（ｋ）に合致特徴点が存在しないケースである。
【００９９】
芯線データ照合手段２１は、第一のケースの場合、後述するサブステップＡ３−１の処理を行う。第一のケースでは、注目芯線Ｓ−Ｕｎｉｔ（ｋ）の片端のみが合致特徴点（ＢＰＭ含む）である。サブステップＡ３−１では、この合致特徴点に近い順に各芯線点を選択し、選択した芯線点（注目点）に対応する芯線点がＦ側に存在するか否かを調査する。なお、サブステップＡ３−１において、注目点となるのは、Ｓ側の連続点（ＳＣと記す。）あるいはＳ側の延伸性終点（ＳＸと記す。）である。種別を表す「Ｃ」や「Ｘ」等の各種記号の前に「Ｓ」や「Ｆ」を付した場合、その「Ｓ」や「Ｆ」はサーチ側あるいはファイル側であることを表すものとする。
【０１００】
芯線データ照合手段２１は、第二のケースの場合、後述するサブステップＡ３−２の処理を行う。第二のケースでは、注目芯線Ｓ−Ｕｎｉｔ（ｋ）の両端が合致特徴点（ＢＰＭ含む）である。サブステップＡ３−２では、ＢＰＭに近い方の合致特徴点に近い順に各芯線点を選択し、選択した芯線点（注目点）に対応する芯線点がＦ側に存在するか否かを調査する。この場合、注目点から両端までの芯線距離の比率に基づいてＦ側の芯線点を判断する。なお、サブステップＡ３−２において、注目点となるのは、Ｓ側の連続点ＳＣと記すだけである。
【０１０１】
芯線データ照合手段２１は、第三のケースの場合、後述するサブステップＡ３−３の処理を行う。第三のケースでは、注目芯線Ｓ−Ｕｎｉｔ（ｋ）上に合致特徴点は存在しない。第三のケースに該当するユニットの優先順位は低いため、サブステップＡ３−３の実行時には、既にサブステップＡ３−１，Ａ３−２が終了している。サブステップＡ３−３において、Ｆ側の芯線点との対応関係を調査するときには、サブステップＡ３−１，Ａ３−２において合致芯線点と判断された芯線点を参照点として用いる。
【０１０２】
サブステップＡ３−１，Ａ３−２またはＡ３−３が終了した場合、芯線データ照合手段２１は、ｋを１増加し、新たな注目芯線を選択する（ステップＡ３０７）。
【０１０３】
以下、サブステップＡ３−１からサブステップＡ３−３の処理について説明する。サブステップＡ３−１からサブステップＡ３−３では、多くの用語が登場する。Ｓ側のデータについて用いる用語と、Ｆ側のデータについて用いる用語との対応表を図２５に示す。
【０１０４】
図２６はサブステップＡ３−１の処理経過の一例を示す流れ図である。図２７サブステップＡ３−１において、注目点と対応点とを対応付ける状況を示す説明図である。サブステップＡ３−１の処理対象は、図２７に示す注目芯線のように片端のみが合致特徴点となっている注目芯線である。図２７では、この合致特徴点が端点である場合を示したが、分岐点となる場合もある。分岐点であっても芯線を分離して端点とみなすことができる。従って、以下の説明ではこの合致特徴点を、「Ｅ」を用いて合致端点ＳＥと表現する。Ｓ側の合致端点ＳＥとＦ側の合致端点ＦＥとの対応付けは既に完了している。芯線データ照合手段２１は、サブステップＡ３−１を開始すると、注目芯線上の合致端点ＳＥの隣接点を最初の注目点として設定（選択）する（ステップＡ３１１）。この注目点はＳ側の連続点ＳＣである。図２８の左側の図に示すように、合致端点ＳＥに隣接する連続点ＳＣが最初の注目点となる。
【０１０５】
芯線データ照合手段２１は、ステップＡ３１１の後、サブステップＡ３−１を終了するか否かを判断する（ステップＡ３１２）。サブステップＡ３−１の終了条件については後述する。終了条件を満たしていなければ、芯線データ照合手段２１は、合致端点ＳＥと注目点ＳＣとを結ぶ線分の両側から、それぞれ最近傍の参照点を一つずつ選ぶ（ステップＡ３１３）。この参照点をそれぞれＳＲ１，ＳＲ２と記す（図２７参照）。なお、参照点を３個以上選ぶと、対応付けの精度を向上させることができるが、処理時間が増加する。ここでは二個の参照点ＳＲ１，ＳＲ２を選ぶ場合を例に説明する。芯線データ照合手段２１は、参照点ＳＲ１および注目点ＳＣを結ぶ線分と、注目点ＳＣおよび参照点ＳＲ２を結ぶ線分とがなす内角ＳＡを計測する（ステップＡ３１４）。この内角ＳＡは、ＳＡ＝∠（ＳＲ１，ＳＣ、ＳＲ２）と表現できる。
【０１０６】
次に、芯線データ照合手段２１は、注目点ＳＣに対応する対応点の候補を選ぶ（ステップＡ３１５）。注目芯線上の芯線点と対応することが既に明らかになっているＦ側の芯線点を既合致点ＦＣ（０）とする。芯線データ照合手段２１は、ＦＣ（０）の３個の外側隣接点を対応点候補ＦＣ（１）〜ＦＣ（３）として選ぶ。また、既合致点ＦＣ（０）も対応点候補に含める。ある芯線点の外側隣接点とは、合致端点ＦＥから遠ざかるようにその芯線点から並んでいく芯線点をいう。例えば、図２８に示すように、注目点ＳＣが合致端点ＳＥの隣接点であるとする。この場合、既合致点はＳＥに対応するＦＥである。ＦＥから遠ざかるように延伸する３個の芯線点が既合致点ＦＥの外側隣接点になる。ＦＥおよびこの３点を対応点候補ＦＣ（０）〜ＦＣ（３）として選ぶ。
【０１０７】
ＦＣ（０）以外の対応点候補の数は３個でなくてもよい。しかし、隣接芯線点との最大距離（√２）や画像の歪みや伸縮等を考慮すると、Ｆ（０）以外の対応点候補の数は３個とすることが好ましい。
【０１０８】
また、外側隣接点ＦＣ（１）〜ＦＣ（３）の中に、非合致特徴点（Ｓ側とＦ側とで種別が一致しない対特徴点）が存在する場合、非合致特徴点以降の外側隣接点は対応点候補から除外する。
【０１０９】
芯線データ照合手段２１は、対応点候補ＦＣ（０）〜ＦＣ（３）の中から対応点を決定する（ステップＡ３１６）。既合致点ＦＣ（０）に隣接するＦＣ（１）を注目点ＳＣの対応点として単純に定めると、位置関係に矛盾が生じる場合がある。そこで、「注目点と近傍参照点群との位置関係」を考慮して対応点を決定する。芯線データ照合手段２１は、参照点ＳＲ１，ＳＲ２に対応するＦ側の参照点ＦＲ１，ＦＲ２を定める（図２７参照）。そして、各候補毎に、参照点ＦＲ１および対応点候補を結ぶ線分と、対応点候補および参照点ＦＲ２を結ぶ線分とがなす内角ＦＡを計測する。内角ＦＡは、ＦＡ＝∠（ＦＲ１，ＦＣ（ｎ），ＦＲ２）と表現できる。ＦＣ（ｎ）において、０≦ｎ≦３である。
【０１１０】
そして、芯線データ照合手段２１は、各対応点候補（各内角）を以下の式１によって評価を行う。
【０１１１】
ｙ１＝ｋ１＋ｋ２×｜ＳＡ−ＦＡ｜　（式１）
【０１１２】
すなわち、各ＦＡについてｙ１を算出し、ｙ１を最小とする対応点候補を対応点として決定する。ただし、式１において、ｋ１は対応点候補毎に定める。ＦＣ（０）の評価時にはｋ１＝１とする。ＦＣ（１）の場合、ｋ１＝０とする。ＦＣ（２）の場合、ｋ１＝１とする。ＦＣ（３）の場合、ｋ１＝３とする。また、式１で用いるｋ２は、角度差に対する係数で、本実施の形態ではｋ２＝０．２とした。決定された対応点ＦＣ（ｎ）と注目点ＳＣとが合致芯線点となる。芯線データ照合手段２１は、決定した対応点ＦＣ（ｎ）と、注目点ＳＣとが対応する旨の情報を芯線点対応リストに追加する。新たに対応付けられたＦＣ（ｎ）は、次にステップＡ３１５を実行する際に既合致点として用いられる。
【０１１３】
芯線データ照合手段２１は、最後に対応付けされた合致芯線点の隣接点を新たな注目点ＳＣとして設定する（ステップＡ３１７）。すなわち、それまで注目していた注目点の隣接点を新たな注目点ＳＣとする。その後、ステップＡ３１２以降の動作を繰り返す。
【０１１４】
ステップＡ３１２では、以下の第一から第四の条件のいずれかを満足する場合に、サブステップＡ３−１を終了すると判断する。第一の条件は、Ｓ側の延伸性終点ＳＸについての対応付け処理が完了したことである。第二の条件は、ある注目点ＳＣについて対応付けを行った場合に、Ｆ側の延伸性終点ＦＸが対応点として定められたことである。第三の条件は、ステップＡ３１７で非合致特徴点（種別が一致しない対特徴点）を新たな注目点ＳＣとしたことである。第四の条件は、Ｆ側の最終対応点の隣接点が非合致特徴点であることである。第一の条件または第二の条件でサブステップＡ３−１を終了する場合、最後に対応付けられたＳ側の注目点をＳＴと記し、ＳＴに対応するＦ側の芯線点をＦＴと記す。例えば、第一の条件で終了する場合、Ｓ側の延伸性終点ＳＸがＳＴとなり、その対応点がＦＴとなる（図２７参照）。
【０１１５】
図２９はサブステップＡ３−２の処理経過の一例を示す流れ図である。サブステップＡ３−２の処理対象は、両端が合致特徴点（ＢＰＭ含む）となっている注目芯線である。サブステップＡ３−１と同様に、合致特徴点を合致端点とみなし、「Ｅ」の記号を用いて表す。サブステップＡ３−２では、両端の合致端点のうち、ＢＰＭである合致端点あるいはＢＰＭに近い合致端点から処理を進める。この合致端点（Ｓ側）をＳＥ１とする。また、もう一方の合致端点をＳＥ２とする。芯線データ照合手段２１は、サブステップＡ３−２を開始すると、注目芯線上の合致端点ＳＥ１の隣接点を最初の注目点として設定（選択）する（ステップＡ３２１）。最初の注目点は、図２８に示す例示と同様に定められる。なお、サブステップＡ３−２では、連続点ＳＣのみが注目点となる。
【０１１６】
芯線データ照合手段２１は、ステップＡ３２１の後、サブステップＡ３−２を終了するか否かを判断する（ステップＡ３２２）。サブステップＡ３−２の終了条件については後述する。終了条件を満足していなければ、注目点ＳＣと開始側の合致端点ＳＥ１との芯線距離を計測する（ステップＡ３２３）。ＳＣとＳＥ１との芯線距離をＳＤ１と記す。芯線距離ＳＤ１は、直線距離ではなく、注目芯線に沿った曲線距離であることが好ましい。直線距離は、画像の歪み等の影響を受けやすいためである。本実施例では、注目芯線に沿ってＳＣからＳＥ１に移動するときに、上下左右の画素に１回移動する度に距離単位（１画素）を累積し、斜め方向の画素に１回移動する度に１．４画素（√２画素）を累積して距離を求める。また、芯線データ照合手段２１は、もう一方の合致端点ＳＥ２と注目点ＳＣとの芯線距離（ＳＤ２と記す。）も同様に計測する。
【０１１７】
次に、芯線データ照合手段２１は、芯線距離ＳＤ１，ＳＤ２の総和に対するＳＤ１の比率Ｒｓを算出する（ステップＡ３２４）。すなわち、Ｒｓ＝ＳＤ１／（ＳＤ１＋ＳＤ２）として、Ｒｓを算出する。
【０１１８】
次に、芯線データ照合手段２１は、既に説明したステップＡ３１５と同様に、注目点ＳＣに対応する対応点の候補を選ぶ（ステップＡ３２５）。本実施の形態では、４個の対応点候補ＦＣ（０）〜ＦＣ（４）を選ぶ。ＦＣ（０）は、最後に対応付けされた既合致点である。
【０１１９】
芯線データ照合手段２１は、対応点候補ＦＣ（０）〜ＦＣ（３）の中から対応点を決定する（ステップＡ３２６）。既合致点ＦＣ（０）に隣接するＦＣ（１）を注目点ＳＣの対応点として単純に定めると、位置関係に矛盾が生じる場合がある。そこで、「両端の非合致点と注目点との距離の比率」を考慮して対応点を決定する。芯線データ照合手段２１は、各対応点候補ＦＣ（０）〜ＦＣ（３）から合致端点ＦＥ１，ＦＥ２までの芯線距離を計測する。ＦＥ１，ＦＥ２は、それぞれＳＥ１，ＳＥ２に対応するＦ側の合致端点である。また、対応点候補からＦＥ１，ＦＥ２までの芯線距離をそれぞれＦＤ１（ｎ）、ＦＤ２（ｎ）と表す。ただし、ｎ＝０〜３であり、各候補に対応する。
【０１２０】
次に、ｎ＝０〜３のそれぞれの場合について、ＦＤ１（ｎ）とＦＤ２（ｎ）の総和に対するＦＤ１（ｎ）の比率Ｒｆを算出する。すなわち、Ｒｆ＝ＦＤ１（ｎ）／（ＦＤ１（ｎ）＋ＦＤ２（ｎ））として、Ｒｆを算出する。そして、｜Ｒｆ−Ｒｓ｜が最小となる対応点候補を対応点として決定する。この対応点と注目点ＳＣは合致芯線点となる。芯線データ照合手段２１は、決定した対応点と注目点ＳＣとが対応する旨の情報を芯線点対応リストに追加する。注目点ＳＣと対応付けられたＦ側の対応点は、次にステップＡ３２５を実行する際に既合致点として用いられる。
【０１２１】
芯線データ照合手段２１は、最後に対応付けされた合致芯線点の隣接点を新たな注目点ＳＣとして設定する（ステップＡ３２７）。すなわち、それまで注目していた注目点の隣接点を新たな注目点ＳＣとする。その後、ステップＡ３２２以降の動作を繰り返す。ステップＡ３２２では、新たに設定した注目点ＳＣが合致端点ＳＥ２と同一点となっていることを終了条件とする。
【０１２２】
図３０はサブステップＡ３−３の処理経過の一例を示す流れ図である。サブステップＡ３−３の処理対象は、合致特徴点が存在しない注目芯線である。サブステップＡ３−３を実行するときには、既にサブステップＡ３−１，Ａ３−２が行われている。従って、注目芯線以外の芯線には合致芯線点や合致特徴点が存在する。サブステップＡ３−３では、これらの点を参照点として、芯線点の対応付け処理を行う。
【０１２３】
芯線データ照合手段２１は、サブステップＡ３−３を開始すると、注目芯線の隣接芯線を全て検索する（ステップＡ３３１）。さらに、検索した隣接芯線から合致特徴点を検索する。隣接芯線とは、その芯線上の点から注目芯線に垂線を下ろしたときに他の芯線に交わることなく注目芯線に達することが可能な芯線であると定義する。注目芯線に直接垂線を下ろせる部分が一部分でも存在すれば、隣接芯線に該当する。注目芯線の片側に存在する隣接芯線は一本のみとは限らず、二本以上の隣接芯線が存在する場合もある。図３１（ａ）に示す注目芯線を例に説明すると、ＢＰＭが存在する側には二本の隣接芯線が存在する。その反対側には、一本の隣接芯線が存在する。
【０１２４】
ステップＡ３３１の後、芯線データ照合手段２１は、隣接芯線から合致特徴点を検索できたか否かを判断する（ステップＡ３３２）。合致特徴点を見つけることができた場合、芯線データ照合手段２１は、その合致特徴点を参照点として、Ｓ側注目点を定め、その注目点とＦ側の芯線点とを対応付ける（ステップＡ３３３）。
【０１２５】
ステップＡ３３３では、隣接芯線上の合致特徴点から注目芯線に垂線を下ろしたときの垂線の足をＳ側注目点とする。例えば、図３１（ａ）では、隣接芯線２，１にそれぞれ合致特徴点１，２が存在する。その合致特徴点１，２から下ろした垂線の足をそれぞれ注目点１，２としている。図３１（ａ）では、合致特徴点等から注目芯線に下ろした垂線を矢印で示している。なお、合致特徴点から下ろした垂線が注目芯線に達しない場合、その合致特徴点を無視して、次の合致特徴点から垂線を下ろす。
【０１２６】
次に、隣接芯線上の合致特徴点に対応するＦ側の合致特徴点から、対応芯線（注目芯線に対応するＦ側の芯線）に垂線を下ろす。その垂線と対応芯線との交点が存在すれば、その交点（垂線の足）をＳ側注目点に対応する対応点として定める。図３１（ｂ）に示す例では、Ｓ側の隣接芯線に対応する対応隣接芯線２，１上に合致特徴点１，２が存在する。この合致特徴点１，２から対応芯線に下ろした垂線の足をそれぞれ対応点１，２としている。この対応点は、図３１（ａ）に示す注目点１，２に対応する。なお、Ｆ側においても、合致特徴点から下ろした垂線が対応芯線に達しない場合、その合致特徴点を無視して、次の合致特徴点から垂線を下ろす。
【０１２７】
また、Ｓ側，Ｆ側の合致特徴点から垂線を下ろすときに、その垂線の長さが所定の値（例えば、平均隆線間隔の２倍）以上となるならば、その合致特徴点は無視して、次の合致特徴点から垂線を下ろす。
【０１２８】
続いて、芯線データ照合手段２１は、隣接芯線上の各合致特徴点に基づいてＦ側に対応点を見つけることができたか否かを判断する（ステップＡ３３４）。
【０１２９】
隣接芯線から合致特徴点を検索できなかったとステップＡ３３２で判断した場合、芯線データ照合手段２１は、注目芯線の中点を定め、その中点とＦ側の芯線点とを対応付ける（ステップＡ３３５）。また、Ｆ側に対応点を見つけることができなかったとステップＡ３３４で判断した場合にも同じ処理を行う。芯線データ照合手段２１は、ステップＡ３３５において、注目芯線の両端からの芯線距離が等しくなる芯線点を注目芯線の中点と定める。図３２（ａ）に示す例では中点を丸印で表している。なお、注目芯線の両端は、延伸性終点あるいは非合致特徴点である。
【０１３０】
芯線データ照合手段２１は、この中点から、ＢＰＭ側に存在する隣接芯線に対して垂線を下ろし、その垂線の足が参照点となり得るか否かを判断する。具体的には、隣接芯線に下ろした垂線の足が合致芯線点であり、その垂線の足の対応点がＦ側に存在していれば、その垂線の足を参照点とする。図３２（ａ）に示す例では、中点から隣接芯線に下ろした垂線の足を参照点１としている。垂線の足が参照点とならなければ、注目芯線上の芯線点とＦ側との対応付けができない。この場合、ステップＡ３３５においてサブステップＡ３−３を終了し、次の注目芯線を選択する。
【０１３１】
次に、その参照点から注目芯線に垂線を下ろし、その垂線と注目芯線との交点（垂線の足）が存在すれば、その交点を注目点とする。この注目点は、既に定めた中点と一致する場合もあるし、わずかにずれる場合もある。垂線と注目芯線との交点が存在ない場合、ステップＡ３３５においてサブステップＡ３−３を終了し、次の注目芯線を選択する。
【０１３２】
次に、芯線データ照合手段２１は、参照点に対応するＦ側の対応参照点からＦ側の対応芯線に垂線を下ろし、その垂線と対応芯線との交点（垂線の足）が存在すれば、その交点を対応点として決定する。交点が存在しなければ、ステップＡ３３５においてサブステップＡ３−３を終了し、次の注目芯線を選択する。
【０１３３】
また、ステップＡ３３５において垂線の長さが所定の値（例えば、平均隆線間隔の２倍）以上となった場合にも、その時点でサブステップＡ３−３を終了し、次の注目芯線を選択する。
【０１３４】
ステップＡ３３４またはステップＡ３３５までに、対応点を定めることができたならば、注目点を追加する（ステップＡ３３６）。ステップＡ３３６開始時には、通常注目点と対応点との組み合わせが１組以上存在する。ある注目点から見て、その外側（注目芯線の端に向かう側）に注目点がない場合、その注目点から一定距離だけ外側に進み、その芯線点を外側検査点とする。図３１（ａ）では一つの外側検査点を示し、図３２（ａ）では二つの外側検査点を示す。
【０１３５】
外側検査点を定めたならば、外側検査点から隣接芯線（注目芯線から見てＢＰＭ側）に垂線を下ろし、その垂線と隣接芯線の交点（垂線の足）があれば、その交点が参照点となり得るかを調べる。具体的には、垂線の足が合致芯線点であり、Ｆ側への対応点が存在していれば、その垂線の足を参照点とする。続いて、その参照点から注目芯線に垂線を下ろし、その垂線と注目芯線の交点（垂線の足）が存在すれば、その交点を注目点とする。この注目点は、外側検査点と一致する場合もあるし、わずかにずれる場合もある。次に、ファイル側の対応参照点から、ファイル側の対応芯線に垂線を下ろし、その垂線の足を対応点として決定する。
【０１３６】
新たに注目点を決定したならば、さらに一定距離だけ外側に進み、新たな外側検査点を定め、同様に注目点と対応点とを定めていく。また、注目芯線の外端が延伸性終点ＳＸの場合、には、この延伸性終点を外側検査点とみなして、同様に注目点と対応点を定める。また、外側検査点について参照点、注目点あるいは対応点を定められなくなった場合や、垂線の長さが所定の値以上になった場合には、その外側検査点についての処理を終了する。以上でステップＡ３３６の説明を終える。
【０１３７】
ステップＡ３３６の後、芯線データ照合手段２１は、注目点と注目点とに挟まれた部分に存在する芯線点について、Ｆ側との対応付け処理を行う（ステップＡ３３７）。ステップＡ３３６終了時に、注目点と対応点との組が複数存在する場合、その注目点と注目点とに挟まれた部分の各芯線点について、Ｆ側と対応付け処理を行う。この対応付けは、二つの注目点をいずれも合致特徴点とみなして、サブステップＡ３−２と同様に行う。
【０１３８】
注目芯線の最も外側に存在する注目点（Ｆ側に対応点が存在する注目点）の外側にさらに芯線点が存在する場合がある。また、ステップＡ３３６終了時までに、注目点が１つしか存在しない場合がある。この場合、それらの注目点より外側に存在する芯線点について、Ｆ側と対応付け処理を行う（ステップＡ３３８）。この対応付けは、注目点を合致特徴点とみなし、かつ、注目点より外側に存在する芯線点の並びをユニットとみなして、サブステップＡ３−１と同様に行う。以上でステップＡ３の処理の説明を終える。
【０１３９】
次にステップＡ４の処理について説明する。ステップＡ４開始時には、Ｓ側とＦ側の芯線点の対応付けは終了している。ステップＡ４では、Ｓ側の各芯線に関して、連続する合致芯線点の長さを計算する。
【０１４０】
個々の芯線について、並んでいる合致芯線点の長さＬＭＳを求めたならば、その長さに修正係数Ｋ（Ｌ）を乗じて積を求める。Ｋ（Ｌ）は、合致芯線点の長さＬＭＳに応じて定められている。ＬＭＳ≦１０であれば、Ｋ（Ｌ）＝０．５である。
【０１４１】
１０＜ＬＭＳ≦５０であれば、下記式２によってＫ（Ｌ）が定まる。
【０１４２】
Ｋ（Ｌ）＝０．０１２５×（ＬＭＳ−１０）＋０．５　（式２）
【０１４３】
５０＜ＬＭＳ≦１００であれば、下記式３によってＫ（Ｌ）が定まる。
【０１４４】
Ｋ（Ｌ）＝０．０１×（ＬＭＳ−５０）＋１．０　（式３）
【０１４５】
１００＜ＬＭＳ≦２００であれば、下記式４によってＫ（Ｌ）が定まる。
【０１４６】
Ｋ（Ｌ）＝０．００５×（ＬＭＳ−１００）＋１．５　（式４）
【０１４７】
２００＜ＬＭＳであれば、下記式５によってＫ（Ｌ）が定まる。
【０１４８】
Ｋ（Ｌ）＝０．００３×（ＬＭＳ−１００）＋２．０　（式５）
【０１４９】
個々のＳ側芯線毎に長さＬＭＳと修正係数Ｋ（Ｌ）の積を求めたら、その積の総和を求める。この総和をΣ（ＬＭＳ×Ｋ（Ｌ））と表す。
【０１５０】
また、ステップＡ１〜Ａ３までに生じたペナルティの総和を求める。この総和は、ステップＡ１終了時のＰ（ｍ）と、ステップＡ２終了時のＰ（ｍ）と、ステップＡ３で生じるペナルティｋ１の総和である。このペナルティの総和をΣ（Ｐ）と表す。そして、下記式６によって、芯線の照合スコアＳｋｅｌＳｃｏｒｅを算出する。
【０１５１】
ＳｋｅｌＳｃｏｒｅ＝Σ（ＬＭＳ×Ｋ（Ｌ））−Σ（Ｐ）×ＫＰ　（式６）
【０１５２】
ただし、係数ＫＰは、Σ（Ｐ）に対する修正係数であり、本実施の形態では例えば１とする。ＳｋｅｌＳｃｏｒｅを算出することによって、ステップＡ４が終了する。以上で、図９の流れ図の各ステップの説明を終了する。
【０１５３】
照合スコア融合手段２２は、ＳｋｅｌＳｃｏｒｅと、特徴点照合手段１９が計算した特徴点の照合スコアとを融合し、特徴点と芯線の双方を考慮した照合スコアを計算する。例えば、特徴点の照合スコアとＳｋｅｌＳｃｏｒｅとの相加平均あるいは相乗平均を照合スコアとして計算する。このとき、特徴点照合手段１９や芯線データ照合手段の識別性能（照合性能）を数値化し、その値を荷重した上で相加平均あるいは相乗平均を計算してもよい。照合結果出力手段２３は、照合スコア融合手段２２の計算結果を外部に出力する。
【０１５４】
本発明によれば、特徴点だけでなく連続点Ｃ等の芯線点についてもＳ側とＦ側とで対応付ける。従って、特徴点の数が少なくても、指紋照合を行うことができる。その結果、面積の小さい遺留指紋等についても照合を行えるようになる。
【０１５５】
また、ステップＡ２において、芯線データの修正を行うので、芯線データを正確に抽出できなかった場合であっても照合精度を改善することができる。すなわち、本来、端点である点を分岐点として芯線データを作成してしまったような場合であっても、Ｓ側とＦ側とで芯線構造が同じになるように芯線データを修正した上で照合を行うので、照合精度を改善することができる。
【０１５６】
また、一般に、各点の座標は歪みによって影響を受けやすい。しかし、本発明では、合致芯線点を判定する際には、Ｓ側およびＦ側の座標を照合するのではなく、合致端点等を起点として、既合致点との位置関係を基準に合致芯線点を判定していく。したがって、指紋画像に歪みが生じていても、歪みの影響を受けにくくすることができる。
【０１５７】
本実施の形態において、対応付け手段、評価手段、芯線データ修正手段およびベース対特徴点決定手段は、いずれも芯線データ照合手段によって実現される。
【０１５８】
次に、他の実施の形態について説明する。
図１，２に示す構成例では、特徴点抽出手段１５や特徴点照合手段１９や芯線データ照合手段２１を別々の構成要素としている。これらを別個の構成要素とするのではなく、一つの構成要素が特徴点抽出手段１５、特徴点照合手段１９および芯線データ照合手段２１の機能を実現する構成であってもよい。
【０１５９】
また、特徴点抽出手段１５は、芯線抽出手段１３が抽出した芯線データから特徴点を抽出するのではなく、芯線データ照合手段２１が修正を加えた芯線データから再度特徴点を抽出してもよい。そして、再抽出された特徴点を用いて、特徴点照合手段１９による特徴点照合処理や、芯線データ照合手段２１による芯線データ照合処理を行ってもよい。
【０１６０】
また、ステップＡ４において、芯線の照合スコアＳｋｅｌＳｃｏｒｅを算出する場合、連続する合致芯線点の長さＬＭＳではなく、合致芯線に囲まれた面積に基づいてＳｋｅｌＳｃｏｒｅを算出してもよい。この場合、芯線データ照合手段２１は、ステップＡ４として以下の処理を実行する。なお、ステップＡ３までの処理は、既に説明した処理と同様の処理である。
【０１６１】
芯線データ照合手段２１は、ステップＡ４を開始すると、Ｓ側の全画素（黒画素だけでなく白画素も含む）の一つ一つについて、個々の画素から水平、垂直および二種類の斜め方向に一定距離だけ直線を伸ばす。この距離は、例えば、平均隆線幅の２倍程度（約２０画素）でよい。一つの画素から伸ばした直線のうち、少なくとも一本の直線が、その画素を挟むように存在する二本の隣接芯線にぶつかり、かつ、直線と二本の隣接芯線との交点が合致芯線点であるならば、その画素は合致芯線に囲まれた画素であると判断する。
【０１６２】
また、一つの画素から水平、垂直および二種類の斜め方向に伸ばした全ての直線が、以下の三つの条件のいずれかに該当する場合、その画素は合致芯線に囲まれた画素ではないと判断する。第一の条件は、一定距離（約２０画素）だけ直線を伸ばしても隣接芯線にぶつからないことである。第二の条件は、隣接芯線にぶつかる前に不明領域にぶつかることである。第三の条件は、隣接芯線との交点が合致芯線点でないことである。ただし、合致芯線点については、これらの条件を満たしていても、合致芯線に囲まれた画素であると判断することが好ましい。
【０１６３】
図３３は、合致芯線に囲まれた画素とそうでない画素の具体例を示す説明図である。図３３（ａ）において斜線で示した領域は不明領域であるとする。また、不明領域内に存在する芯線点は全て非合致芯線点であり、不明領域以外に存在する芯線点は全て合致芯線点であるとする。図３３（ａ）に示す注目画素１から水平方向に伸ばした直線は、一方が隣接芯線にぶつかるが、もう一方が不明領域にぶつかってしまう。垂直方向や斜め方向に伸ばした直線についても同様である。従って、注目画素１から伸ばした直線は全て第二の条件に該当するので、注目画素１は合致芯線に囲まれていないことになる。また、注目画素２は斜め方向に伸ばした直線が、注目画素２を挟む二本の隣接芯線にぶつかり、かつ、その交点は合致芯線点である。従って、注目画素２は合致芯線に囲まれていることになる。注目画素３も同様である。
【０１６４】
このようにして全画素について、合致芯線に囲まれているか否かを判断する。図３３（ｂ）は、合致芯線に囲まれたと判断された画素が存在する領域と、合致芯線に囲まれていないと判断された画素が存在する領域とを区別して表したものである。図３３（ｂ）では、合致芯線に囲まれたと判断された画素が存在する領域を「合致芯線内領域」として示している。合致芯線に囲まれていると判断した画素の個数を合致芯線に囲まれた領域の面積Ｑとみなす。この面積Ｑに基づいて、下記式７によってＳｋｅｌＳｃｏｒｅを算出する。
【０１６５】
ＳｋｅｌＳｃｏｒｅ＝Ｑ−Σ（Ｐ）×ＫＰ　（式７）
【０１６６】
既に説明したように、Σ（Ｐ）はステップＡ１〜Ａ３までに生じたペナルティの総和であり、ＫＰはΣ（Ｐ）に対する修正係数である。ＫＰの値は、例えば１とする。
【０１６７】
細長い領域について芯線照合を行う場合、合致芯線の長さに基づいてＳｋｅｌＳｃｏｒｅを算出すると、比較的大きな値となってしまうことがある。面積に基づいてＳｋｅｌＳｃｏｒｅを算出するときには、このような弊害は少ない。ただし、合致芯線の長さに基づく方法と、面積に基づく方法のどちらが優れるとは一概にいえない。そこで、合致芯線の長さと面積のそれぞれからＳｋｅｌＳｃｏｒｅを算出し、加重付けを行った上でＳｋｅｌＣｏｒｅの平均をとってもよい。
【０１６８】
これまでに説明した各実施の形態における芯線データ照合処理（芯線点同士の対応付け処理）は、対特徴点リストに少なくとも３組の対特徴点が含まれていることを前提としていた。そして、芯線データ照合手段２１は、対特徴点リストに含まれる対特徴点が２組以下であるならば、芯線データ照合処理を中止していた。芯線照合の精度を向上させることができるのであれば、対特徴点が２組以下であるときに芯線データ照合処理を中止しなくてよい。以下、芯線照合の精度を向上させることができる実施の形態について説明する。
【０１６９】
この実施の形態では、芯線データ照合手段２１は、Ｓ側とＦ側とで対になる点の組を、入力装置（例えばマウス等）を介して指定される。芯線データ照合手段２１は、指定された点の組に基づいて合致芯線点の組を定め、その合致芯線点の組を対特徴点の組とみなして、図９に示すステップＡ０以降の処理を実行すればよい。
【０１７０】
指定された点の組から、合致特徴点の組を定める場合の例を以下に示す。芯線データ照合手段２１は、Ｓ側の画像とＦ側の画像とを表示させ、対になる点の組の指定を鑑識官に促す。例えば、図３４（ａ），（ｂ）に示す画像を表示する。図３４（ｂ）に示すような隆線のみの画像ではなく、図３４（ｃ）に示すような芯線を重畳させた画像を表示してもよい。ただし、図３４に示す円は便宜上示したものであり、実際には表示されない。図３４に示す例では、特徴点の抽出や照合の際には無視される点（短い隆線）７００ａ，７００ｂが存在する。
【０１７１】
鑑識官は、Ｓ側の点（短い隆線）７００ａとＦ側の点７００ｂとをマウス等で指定する。芯線データ照合処理２１は、マウス等によって点７００ａ，７００ｂが指定されると、Ｓ側の点７００ａから、隣接する芯線に垂線を下ろし、垂線の足となる点を特定する。同様に、Ｆ側の点７００ｂから、隣接する芯線に垂線を下ろし、垂線の足となる点を特定する。芯線データ照合処理２１は、垂線の足となった点同士を合致芯線点とし、対特徴点の組とみなす。そして、ステップＡ０以降の処理を進めればよい。なお、ステップＡ３では、その合致芯線点を含むユニット上の芯線点の対応付け処理を行う場合、合致芯線点として定めた点を起点として対応付け処理を行っていけばよい。また、この合致芯線点を起点とするユニットについて芯線点の対応付け処理を行う場合、ステップＡ３の処理過程では、サブステップＡ３−１が適用される。
【０１７２】
点７００ａ，７００ｂの組が指定された場合、芯線データ照合処理２１は、点７００ａ，７００ｂに隣接する芯線上に合致特徴点を定めた。マウス等を介して指定された点の組をそのまま合致芯線点の組とする場合もある。例えば、Ｓ側の中核蹄状線の頂点およびＦ側の中核蹄状線の頂点の組が入力された場合、入力されたＳ側の頂点とＦ側の頂点との組を、そのまま合致芯線点の組として定めてもよい。中核蹄状線とは、指紋の最も内側に存在する隆線である。中核蹄状線の頂点は、図３５に示すように、中核蹄状線上で最も張り出した位置に存在する点である。なお、図３４に示す例では、Ｓ側の画像で中核蹄状線の頂点が確認されない。仮に、Ｓ側の画像で中核蹄状線の頂点が確認されるのであれば、その点とＦ側の中核蹄状線の頂点とを対にして指定することができる。Ｆ側の中核蹄状線の頂点は、破線で示した領域内で確認することができる。
【０１７３】
点（短い隆線）や中核蹄状線の頂点の組だけでなく、図１２に示す「島」を形成する点や、隆線の膨らみ部分に存在する点の組が入力され、芯線データ照合処理２１がそれらの組に基づいて合致芯線点の組を特定してもよい。
【０１７４】
このように、鑑識官が指定した点の組から合致芯線点の組を特定し、その合致芯線点を起点として芯線点の対応付けを行うようにすれば、照合精度を向上させることができる。その結果、対特徴点リストに含まれる対特徴点の組が２組以下でも、十分な精度で芯線照合を行うことができる。
【０１７５】
また、図１８では、サブステップＡ２−２を行った後にサブステップＡ２−３を行う場合の例を示したが、サブステップＡ２−３の処理は行わなくてもよい。すなわち、対向関係にある二つの特徴点の組を排除するように、少なくともＦ側の芯線データを修正すればよい。この場合、ステップＡ３において、対向関係にある特徴点が存在するＳ芯線は、Ｆ側との対応付けの対象から外せばよい。
【０１７６】
また、ステップＡ３では、Ｓ側の芯線点に対応するＦ側の対応点を特定していく場合を示した。ステップＡ３では、Ｓ側の芯線点に対応するＦ側の対応点を特定するだけでなく、Ｆ側の芯線点に対応するＳ側の対応点も特定して照合精度を向上させるようにしてもよい。
【０１７７】
本発明の適用範囲は、指紋照合に限定されない。例えば、掌紋照合等のように、縞模様となる曲線等の照合であれば、本発明を適用することができる。
【０１７８】
【発明の効果】
本発明によれば、各縞模様画像の縞を細線化した線である芯線を示す芯線画素のデータを抽出し、第二の縞模様画像の芯線画素の中から第一の縞模様画像の芯線画素に対応する画素を特定することによって芯線画素同士の対応付け処理を行い、対応付け処理が行われた第一の縞模様画像の芯線画素に基づいて第一の縞模様画像と第二の縞模様画像の合致の度合いを評価する。従って、対特徴点の数が少なくても、芯線画素同士の対応関係が明らかになり、縞模様画像同士の照合を行うことができる。その結果、縞模様画像の面積が小さい場合であっても照合が可能になる。
【図面の簡単な説明】
【図１】本発明による縞模様画像照合装置の例を示すブロック図である。
【図２】本発明による縞模様画像照合装置の例を示すブロック図である。
【図３】デジタル化された指紋画像の例を示す説明図である。
【図４】指紋画像から抽出された芯線データの例を示す説明図である。
【図５】芯線点の画素の近傍を示すマスクパターンの説明図である。
【図６】マスクパターンの修正例を示す説明図である。
【図７】Ｃｏｄｅ８の説明図である。
【図８】芯線データの表現例を示す説明図である。
【図９】芯線データ照合処理の概要を示す流れ図である。
【図１０】ＢＰＭ決定処理の処理経過を示す流れ図である。
【図１１】分岐点を端点に変化させる状況を示す説明図である。
【図１２】対向関係にある対特徴点の例を示す説明図である。
【図１３】Ｆ側芯線データ修正処理の処理経過を示す流れ図である。
【図１４】Ｆ側芯線データの修正内容を規定するルールの一覧表である。
【図１５】分岐点を端点に修正する状況を示す説明図である。
【図１６】Ｆ側の注目対特徴点を修正する状況を示す説明図である。
【図１７】Ｆ側の注目対特徴点を修正する状況を示す説明図である。
【図１８】対向特徴点の削除処理の処理経過を示す流れ図である。
【図１９】修正に伴うＦ側芯線の変化の例を示す説明図である。
【図２０】芯線点対応リストの例を示す説明図である。
【図２１】芯線点の対応付け処理の処理経過の例を示す流れ図である。
【図２２】ＢＰＭに接続するユニットの順位付けの例を示す説明図である。
【図２３】ＢＰＭ以外の合致特徴点に対する順位付けの例を示す説明図である。
【図２４】合致特徴点に接続しないユニットに対する順位付けの例を示す説明図である。
【図２５】Ｓ側のデータについて用いる用語とＦ側のデータについて用いる用語との対応表である。
【図２６】芯線点の対応付け処理の処理経過の例を示す流れ図である。
【図２７】注目点と対応点とを対応付ける状況を示す説明図である。
【図２８】注目点および対応点候補の例を示す説明図である。
【図２９】芯線点の対応付け処理の処理経過の例を示す流れ図である。
【図３０】芯線点の対応付け処理の処理経過の例を示す流れ図である。
【図３１】注目点および対応点を定める状況を示す説明図である。
【図３２】注目点および対応点を定める状況を示す説明図である。
【図３３】合致芯線に囲まれた画素とそうでない画素の具体例を示す説明図である。
【図３４】対になる点の指定を促す画面の例を示す説明図である。
【図３５】中核蹄状線の頂点の例を示す説明図である。
【符号の説明】
１３　芯線抽出手段
１４　芯線データ記憶手段
１５　特徴点抽出手段
１６　特徴点データ記憶手段
１７　データベース登録手段
１８　データベース記憶手段
１９　特徴点照合手段
１８　データベース記憶手段
２０　対特徴点リスト記憶手段
２１　芯線データ照合手段
２２　照合スコア融合手段
【図１】
2004078433.tif 000003
【図２】
2004078433.tif 000004
【図３】
2004078433.tif 000005
【図４】
2004078433.tif 000006
【図５】
2004078433.tif 000007
【図６】
2004078433.tif 000008
【図７】
2004078433.tif 000009
【図８】
2004078433.tif 000010
【図９】
2004078433.tif 000011
【図１０】
2004078433.tif 000012
【図１１】
2004078433.tif 000013
【図１２】
2004078433.tif 000014
【図１３】
2004078433.tif 000015
【図１４】
2004078433.tif 000016
【図１５】
2004078433.tif 000017
【図１６】
2004078433.tif 000018
【図１７】
2004078433.tif 000019
【図１８】
2004078433.tif 000020
【図１９】
2004078433.tif 000021
【図２０】
2004078433.tif 000022
【図２１】
2004078433.tif 000023
【図２２】
2004078433.tif 000024
【図２３】
2004078433.tif 000025
【図２４】
2004078433.tif 000026
【図２５】
2004078433.tif 000027
【図２６】
2004078433.tif 000028
【図２７】
2004078433.tif 000029
【図２８】
2004078433.tif 000030
【図２９】
2004078433.tif 000031
【図３０】
2004078433.tif 000032
【図３１】
2004078433.tif 000033
【図３２】
2004078433.tif 000034
【図３３】
2004078433.tif 000035
【図３４】
2004078433.tif 000036
【図３５】
2004078433.tif 000037