(57)【要約】【課題】指紋照合の処理速度を速く、かつ、データ量を少なくできるようにする。【解決手段】ＣＰＵは、指紋画像の中心点Ｃ、分岐点Ｐ１乃至Ｐ８、および端点Ｑ１乃至Ｑ１０を検出し、中心点Ｃに最も近接する分岐点Ｐ１と、分岐点Ｐ１に近接する２つの分岐点Ｐ２、Ｐ３を結んで３角形Ｗ１を作成し、３角形の面積Ｓ１と３辺の長さをフラッシュメモリに記憶する。また、ＣＰＵは、分岐点Ｐ１と分岐点Ｐ１に近接する端点Ｑ１、分岐点Ｐ２と分岐点Ｐ２に近接する端点Ｑ３、および分岐点Ｐ３と分岐点Ｐ３に近接する端点Ｑ３の位置をそれぞれ計算し、フラッシュメモリに登録テンプレートとして記憶する。照合時、ＣＰＵは、照合画像から同様に求めた３角形の面積と辺の長さ、端点との位置に基づいて、登録テンプレートと一致するか否かを判定する。本発明は、指紋照合装置に適用できる。【選択図】      図１３
2004213395.tif 000002
【特許請求の範囲】
【請求項１】
指紋画像を処理する情報処理装置において、
前記指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出手段と、
複数の前記第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成手段と、
前記第１の作成手段により作成された前記３角形の面積と辺の長さを計算する第１の計算手段と、
前記第１の計算手段により計算された前記３角形の面積と辺の長さを記憶する記憶手段と
を備えることを特徴とする情報処理装置。
【請求項２】
前記指紋画像の中心である中心点を検出する第２の検出手段と、
前記第２の検出手段により検出された前記中心点と複数の前記第１の特徴点の間の距離に基づいて、前記第１の特徴点をソートするソート手段と
をさらに備え、
前記第１の作成手段は、ソートされた前記第１の特徴点を利用して、近接する任意の３個を結ぶ３角形を作成する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記第１の検出手段は、前記分岐点と前記端点のうちの他方である第２の特徴点をさらに検出し、
１つの前記３角形を構成する３つの前記第１の特徴点をそれぞれ第１の点、第２の点、および第３の点とするとき、前記第１の点と前記第１の点に最も近い前記第２の特徴点である第４の点、前記第２の点と前記第２の点に最も近い前記第２の特徴点である第５の点、および、前記第３の点と前記第３の点に最も近い前記第２の特徴点である第６の点の、それぞれの距離と方向の少なくともいずれか一方を計算する第２の計算手段をさらに備え、
前記記憶手段は、前記第２の計算手段により計算された、前記第１の点と前記第４の点、前記第２の点と前記第５の点、および前記第３の点と前記第６の点のそれぞれの距離と方向の少なくともいずれか一方をさらに記憶する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記指紋画像の中心である中心点を検出する第２の検出手段と、
前記第２の検出手段により検出された前記中心点と複数の前記第１の特徴点の間の距離に基づいて、前記第２の特徴点をソートするソート手段と
をさらに備え、
前記第２の計算手段は、ソートされた前記第２の特徴点を利用して、前記第１の点乃至前記第３の点に対応する前記第４の点乃至前記第６の点の距離と方向の少なくともいずれか一方を計算する
ことを特徴とする請求項３に記載の情報処理装置。
【請求項５】
照合対象の指紋画像から指紋の前記第１の特徴点を検出する第２の検出手段と、
前記照合対象の指紋画像の指紋の複数前記第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第２の作成手段と、
前記第２の作成手段により作成された前記３角形の面積と辺の長さを計算する第２の計算手段と、
前記記憶手段により記憶された、前記３角形の面積と辺の長さ、並びに、前記第２の計算手段により計算された、前記照合対象の指紋画像の前記３角形の面積と辺の長さを比較する比較手段と
をさらに備えることを特徴とする請求項１に記載の情報処理装置。
【請求項６】
指紋画像を処理する情報処理装置の情報処理方法において、
前記指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、
複数の前記第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、
前記第１の作成ステップの処理により作成された前記３角形の面積と辺の長さを計算する第１の計算ステップと、
前記第１の計算ステップの処理により計算された前記３角形の面積と辺の長さの記憶を制御する記憶制御ステップと
を含むことを特徴とする情報処理方法。
【請求項７】
指紋画像を処理するプログラムであって、
前記指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、
複数の前記第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、
前記第１の作成ステップの処理により作成された前記３角形の面積と辺の長さを計算する第１の計算ステップと、
前記第１の計算ステップの処理により計算された前記３角形の面積と辺の長さの記憶を制御する記憶制御ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項８】
指紋画像を処理するプログラムであって、
前記指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、
複数の前記第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、
前記第１の作成ステップの処理により作成された前記３角形の面積と辺の長さを計算する第１の計算ステップと、
前記第１の計算ステップの処理により計算された前記３角形の面積と辺の長さの記憶を制御する記憶制御ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【請求項９】
指紋画像を処理する情報処理装置において、
照合対象の前記指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出手段と、
複数の前記第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成手段と、
前記第１の作成手段により作成された前記３角形の面積と辺の長さを計算する第１の計算手段と、
前記第１の計算手段により計算された照合対象の前記指紋画像の前記３角形の面積と辺の長さを、予め記憶されている前記指紋画像の３角形の面積と辺の長さと比較する比較手段と
を備えることを特徴とする情報処理装置。
【請求項１０】
前記第１の検出手段は、前記分岐点と前記端点のうちの他方である第２の特徴点をさらに検出し、１つの前記３角形を構成する３つの前記第１の特徴点をそれぞれ第１の点、第２の点、および第３の点とするとき、前記第１の点と前記第１の点に最も近い第２の特徴点である第４の点、前記第２の点と前記第２の点に最も近い第２の特徴点である第５の点、および、前記第３の点と前記第３の点に最も近い第２の特徴点である第６の点のそれぞれの距離と方向の少なくともいずれか一方を計算する第２の計算手段をさらに備え、
前記比較手段は、前記第１の計算手段と前記第２の計算手段により計算された照合対象の前記指紋画像の前記３角形の面積と辺の長さ、並びに前記第１の点に対する前記第４の点、前記第２の点に対する前記第５の点、および前記第３の点に対する前記第６の点のそれぞれの距離と方向の少なくともいずれか一方と、記憶されている前記指紋画像の３角形の面積と辺の長さ、並びに照合対象の指紋画像の前記第１の点に対する前記第４の点、前記第２の点に対する前記第５の点、および前記第３の点に対する前記第６の点のそれぞれの距離と方向の少なくともいずれか一方を比較する
ことを特徴とする請求項９に記載の情報処理装置。
【請求項１１】
指紋画像を処理する情報処理装置の情報処理方法において、
照合対象の前記指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、
複数の前記第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、
前記第１の作成ステップの処理により作成された前記３角形の面積と辺の長さを計算する第１の計算ステップと、
前記第１の計算ステップの処理により計算された照合対象の前記指紋画像の前記３角形の面積と辺の長さを、予め記憶されている前記指紋画像の３角形の面積と辺の長さと比較する比較ステップと
を含むことを特徴とする情報処理方法。
【請求項１２】
指紋画像を処理するプログラムであって、
照合対象の前記指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、
複数の前記第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、
前記第１の作成ステップの処理により作成された前記３角形の面積と辺の長さを計算する第１の計算ステップと、
前記第１の計算ステップの処理により計算された照合対象の前記指紋画像の前記３角形の面積と辺の長さを、予め記憶されている前記指紋画像の３角形の面積と辺の長さと比較する比較ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項１３】
指紋画像を処理するプログラムであって、
照合対象の前記指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、
複数の前記第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、
前記第１の作成ステップの処理により作成された前記３角形の面積と辺の長さを計算する第１の計算ステップと、
前記第１の計算ステップの処理により計算された照合対象の前記指紋画像の前記３角形の面積と辺の長さを、予め記憶されている前記指紋画像の３角形の面積と辺の長さと比較する比較ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、指紋照合装置および方法、記録媒体、並びに、プログラムに関し、特に、記憶するデータ量を少なくする指紋照合装置および方法、記録媒体、並びに、プログラムに関する。
【０００２】
【従来の技術】
使用者の指の指紋を読み取り、指紋を照合し、使用者であることを認証する指紋照合装置が各種の装置に応用されている。
【０００３】
指の指紋を読み取り、指紋を登録する技術には、例えば、マニューシャ法やパターンマッチング法と呼ばれているものがある。
【０００４】
マニューシャ法における読み取りの対象となる指紋の登録では、例えば、最初に、指紋画像を２値化して細線化が行なわれ、細線化像から端点や分岐点のような特徴点が抽出される。そして、特徴点から細線に沿って一定数の画素だけ遡り、この部分が部分細線として抽出され、この部分細線が近似する線分列に変換される。この操作が所定数の特徴点について繰り返されて、複数個の線分の繋がりからなる線分列が抽出される。このようにして、指紋画像が線分列化され、その線分の両端の点の座標、線分が変わる位置の座標が登録される。また、特徴点が分岐点の時は、３本に枝分かれした細線について同様の作業が繰り返される。さらに、部分細線、細線化像、特徴点の種類および座標から、異なる部分細線の両端の点同士を結んだ線と交差する隆線の数が算出され、登録される（例えば、特許文献１参照）。
【０００５】
また、マニューシャ法における指紋の照合では、最初に、指紋画像が２値化、細線化された後、特徴量が抽出される。そして、求めた細線化像の中で、登録された部分細線の１つと位置の近いものが選択され、両者のパターンが比較され、不一致度がある閾値以下であれば、両者は同じものであるとされる。また、この位置合わせが照合画像中の特徴点について順次実行され、一致するものが検出されたら両者の位置合わせが行なわれ、このときの移動量だけ、他の部分細線が移動され、それぞれの部分細線について同様の比較が行なわれる。さらに、照合対象細線画像から交差隆線数が算出され、これと登録されている交差隆線数とが比較され、一致率が所定値以上であれば合格とみなされる（例えば、特許文献１参照）。
【０００６】
また、パターンマッチング法においては、指紋画像の全て、または、その一部が登録テンプレートとされる。
【０００７】
【特許文献１】
特開平１−５０１７５号公報
【０００８】
【発明が解決しようとする課題】
しかしながら、パターンマッチング法は、指紋画像の全て、または、その一部を登録テンプレートとしているために、登録するテンプレートのサイズが大きなものとなり、その分、メモリの容量が必要となり、処理速度が遅くなるという課題があった。
【０００９】
また、取得した指紋画像が回転していた場合（例えば、上下が逆となっていた場合）、照合が容易ではなく、精度が十分でないという課題があった。
【００１０】
さらに、マニューシャ法（例えば、特許文献１参照）は、各特徴点の位置、方向、および種類（例えば、分岐点および端点）の情報に加えて、特徴点間の隆線数の情報を利用しており、特徴点間の隆線数の数により認証精度をあげている。すなわち、この方法においても、認証精度を上げるためには、ある程度の大きさのテンプレートサイズが必要になる。このように、処理速度がまだ遅い、データ量がまだ大きい、および、精度が充分ではないという課題があった。
【００１１】
本発明は、このような状況に鑑みてなされたものであり、処理速度を速く、データ量を少なく、かつ、精度をあげることができるようにするものである。
【００１２】
【課題を解決するための手段】
本発明の第１の情報処理装置は、指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出手段と、複数の第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成手段と、第１の作成手段により作成された３角形の面積と辺の長さを計算する第１の計算手段と、第１の計算手段により計算された３角形の面積と辺の長さを記憶する記憶手段とを備えることを特徴とする。
【００１３】
前記指紋画像の中心である中心点を検出する第２の検出手段と、第２の検出手段により検出された中心点と複数の第１の特徴点の間の距離に基づいて、第１の特徴点をソートするソート手段とをさらに備え、第１の作成手段は、ソートされた第１の特徴点を利用して、近接する任意の３個を結ぶ３角形を作成するようにすることができる。
【００１４】
前記第１の検出手段は、分岐点と端点のうちの他方である第２の特徴点をさらに検出し、１つの３角形を構成する３つの第１の特徴点をそれぞれ第１の点、第２の点、および第３の点とするとき、第１の点と第１の点に最も近い第２の特徴点である第４の点、第２の点と第２の点に最も近い第２の特徴点である第５の点、および、第３の点と第３の点に最も近い第２の特徴点である第６の点の、それぞれの距離と方向の少なくともいずれか一方を計算する第２の計算手段をさらに備え、記憶手段は、第２の計算手段により計算された、第１の点と第４の点、第２の点と第５の点、および第３の点と第６の点のそれぞれの距離と方向の少なくともいずれか一方をさらに記憶するようにすることができる。
【００１５】
前記指紋画像の中心である中心点を検出する第２の検出手段と、第２の検出手段により検出された中心点と複数の第１の特徴点の間の距離に基づいて、第２の特徴点をソートするソート手段とをさらに備え、第２の計算手段は、ソートされた第２の特徴点を利用して、第１の点乃至第３の点に対応する第４の点乃至第６の点の距離と方向の少なくともいずれか一方を計算するようにすることができる。
【００１６】
前記照合対象の指紋画像から指紋の第１の特徴点を検出する第２の検出手段と、照合対象の指紋画像の指紋の複数第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第２の作成手段と、第２の作成手段により作成された３角形の面積と辺の長さを計算する第２の計算手段と、記憶手段により記憶された、３角形の面積と辺の長さ、並びに、第２の計算手段により計算された、照合対象の指紋画像の３角形の面積と辺の長さを比較する比較手段とをさらに備えるようにすることができる。
【００１７】
本発明の第１の情報処理方法は、指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、複数の第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、第１の作成ステップの処理により作成された３角形の面積と辺の長さを計算する第１の計算ステップと、第１の計算ステップの処理により計算された３角形の面積と辺の長さの記憶を制御する記憶制御ステップとを含むことを特徴とする。
【００１８】
本発明の第１の記録媒体に記録されているプログラムは、指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、複数の第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、第１の作成ステップの処理により作成された３角形の面積と辺の長さを計算する第１の計算ステップと、第１の計算ステップの処理により計算された３角形の面積と辺の長さの記憶を制御する記憶制御ステップとを含むことを特徴とする。
【００１９】
本発明の第１のプログラムは、指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、複数の第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、第１の作成ステップの処理により作成された３角形の面積と辺の長さを計算する第１の計算ステップと、第１の計算ステップの処理により計算された３角形の面積と辺の長さの記憶を制御する記憶制御ステップとを含む処理をコンピュータに実行させることを特徴とする。
【００２０】
本発明の第２の情報処理装置は、照合対象の指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出手段と、複数の第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成手段と、第１の作成手段により作成された３角形の面積と辺の長さを計算する第１の計算手段と、第１の計算手段により計算された照合対象の指紋画像の３角形の面積と辺の長さを、予め記憶されている指紋画像の３角形の面積と辺の長さと比較する比較手段とを備えることを特徴とする。
【００２１】
前記第１の検出手段は、分岐点と端点のうちの他方である第２の特徴点をさらに検出し、１つの３角形を構成する３つの第１の特徴点をそれぞれ第１の点、第２の点、および第３の点とするとき、第１の点と第１の点に最も近い第２の特徴点である第４の点、第２の点と第２の点に最も近い第２の特徴点である第５の点、および、第３の点と第３の点に最も近い第２の特徴点である第６の点のそれぞれの距離と方向の少なくともいずれか一方を計算する第２の計算手段をさらに備え、比較手段は、第１の計算手段と第２の計算手段により計算された照合対象の指紋画像の３角形の面積と辺の長さ、並びに第１の点に対する第４の点、第２の点に対する第５の点、および第３の点に対する第６の点のそれぞれの距離と方向の少なくともいずれか一方と、記憶されている指紋画像の３角形の面積と辺の長さ、並びに照合対象の指紋画像の第１の点に対する第４の点、第２の点に対する第５の点、および第３の点に対する第６の点のそれぞれの距離と方向の少なくともいずれか一方を比較するようにすることができる。
【００２２】
本発明の第２の情報処理方法は、照合対象の指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、複数の第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、第１の作成ステップの処理により作成された３角形の面積と辺の長さを計算する第１の計算ステップと、第１の計算ステップの処理により計算された照合対象の指紋画像の３角形の面積と辺の長さを、予め記憶されている指紋画像の３角形の面積と辺の長さと比較する比較ステップとを含むことを特徴とする。
【００２３】
本発明の第２の記録媒体に記録されているプログラムは、照合対象の指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、複数の第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、第１の作成ステップの処理により作成された３角形の面積と辺の長さを計算する第１の計算ステップと、第１の計算ステップの処理により計算された照合対象の指紋画像の３角形の面積と辺の長さを、予め記憶されている指紋画像の３角形の面積と辺の長さと比較する比較ステップとを含むことを特徴とする。
【００２４】
本発明の第２のプログラムは、照合対象の指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点を検出する第１の検出ステップと、複数の第１の特徴点のうち、近接する任意の３個を結ぶ３角形を作成する第１の作成ステップと、第１の作成ステップの処理により作成された３角形の面積と辺の長さを計算する第１の計算ステップと、第１の計算ステップの処理により計算された照合対象の指紋画像の３角形の面積と辺の長さを、予め記憶されている指紋画像の３角形の面積と辺の長さと比較する比較ステップとを含む処理をコンピュータに実行させることを特徴とする。
【００２５】
第１の本願発明においては、指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点が検出され、複数の第１の特徴点のうち、近接する任意の３個を結ぶ３角形が作成され、作成された３角形の面積と辺の長さが計算され、計算された３角形の面積と辺の長さが記憶される。
【００２６】
第２の本願発明においては、照合対象の指紋画像から指紋の分岐点と端点のうち一方である第１の特徴点が検出され、複数の第１の特徴点のうち、近接する任意の３個を結ぶ３角形が作成され、作成された３角形の面積と辺の長さが計算され、計算された照合対象の指紋画像の３角形の面積と辺の長さが、予め記憶されている指紋画像の３角形の面積と辺の長さと比較される。
【００２７】
【発明の実施の形態】
図１は、本発明を適用した指紋照合装置の一実施の形態の外観の構成を示す図である。
【００２８】
指紋照合装置１は、装置の筐体をなす本体部１１、および閉じた状態において本体部１１の上面を物理的に保護する、本体部１１に対して開閉自在に設けられている保護カバー１２からなる。図１においては、指紋照合装置１の保護カバー１２は、本体部１１に対して開かれた状態とされている。
【００２９】
本体部１１の上面には、指紋読み取りセンサ２１、並びに指紋の照合の結果を表示するランプ２２およびランプ２３が設けられている。
【００３０】
指紋読み取りセンサ２１は、指紋読み取りセンサ２１に押圧され、接触された指の指紋を画像として読み取る。
【００３１】
図１に示す状態において、図２に示すように、指紋読み取りセンサ２１を、指紋が読み取られる指４１で軽く押圧することにより、指４１の指紋が画像として読み取られる。
【００３２】
ランプ２２およびランプ２３は、排他的に点灯し、即ち、これにより、指紋照合の可否を表示する。ランプ２２およびランプ２３は、いずれも消灯することにより、指紋読み取りセンサ２１に指４１が接触されていない状態であることを表示する。
【００３３】
指紋照合装置１は、図２に示すように、指紋の照合の結果を示すデータを、端子４２に接続されているケーブル４３を介して、図示せぬ他の機器に供給する。ケーブル４３は、例えば、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）の規格に基づいたケーブルとすることができる。ケーブル４３の規格は、例えば、ＲＳ２３２Ｃなど、他の規格であってもよいことは勿論である。
【００３４】
この指紋照合装置１を持ち運びするとき、保護カバー１２は閉じられる。これにより、本体部１１、表示用のランプ２２、およびランプ２３、特に、指紋読み取りセンサ２１が、外部からの異常な圧力から保護されるとともに、静電気から保護される。その結果、指紋照合装置１の破損または破壊が抑制される。
【００３５】
図３は、指紋照合装置１の内部の構成を示すブロック図である。
【００３６】
指紋読み取り用ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔ）５１は、指紋読み取りセンサ２１から供給された信号から、指紋の画像を生成して、生成した指紋の画像をＣＰＵ５２に供給する。
【００３７】
ＣＰＵ５２は、指紋照合装置１全体の動作を制御する。また、ＣＰＵ５２は、指紋読み取り用ＬＳＩ５１から供給された指紋の画像を登録したり、既に登録されている指紋と照合する。
【００３８】
プログラム用ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）／ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）５３は、ＲＡＭおよびＲＯＭからなり、ＣＰＵ５２が実行するコントロールファームウェアである、指紋照合プログラムを記憶する。プログラム用ＲＡＭ／ＲＯＭ５３のＲＯＭ部分には、基本的に固定のプログラムおよびパラメータが記憶される。プログラム用ＲＡＭ／ＲＯＭ５３のＲＡＭ部分には、指紋照合プログラムの実行に伴って変化するパラメータまたはデータが記憶される。
【００３９】
フラッシュメモリ５４は、使用者の指紋を登録するとき、使用者の指紋の画像から抽出された特徴量を表わすデータを登録テンプレートとして記憶する。すなわち、ＣＰＵ５２は、指紋を登録するとき、指紋読み取り用ＬＳＩ５１から供給された、指紋の画像から抽出された登録テンプレートをフラッシュメモリ５４に記憶させる。また、ＣＰＵ５２は、指紋を照合するとき、フラッシュメモリ５４に記憶されている登録テンプレートと、指紋読み取り用ＬＳＩ５１から供給された指紋の画像とを照合する。
【００４０】
ＵＳＢコントローラ５５は、ＵＳＢの規格に基づいて、端子４２を介して接続されている、図示せぬ外部の機器に、ＣＰＵ５２から供給された、指紋照合の結果を出力すると共に、外部の機器から供給された、指紋を読み取っている使用者のＩＤ（Ｉｄｅｎｔｉｆｉｅｒ）を取得する。ＵＳＢコントローラ５５は、取得した使用者のＩＤをＣＰＵ５２に供給する。ユーザＩＤは、フラッシュメモリ５４に、登録テンプレートとして記憶される。
【００４１】
指紋読み取り用ＬＳＩ５１、フラッシュメモリ５４，プログラム用ＲＡＭ／ＲＯＭ５３、ＣＰＵ５２、およびＵＳＢコントローラ５５は、バス５６により相互に接続されている。
【００４２】
バス５６には、必要に応じてドライブ５７が接続される。ドライブ５７は、必要に応じて装着される磁気ディスク７１、光ディスク７２、光磁気ディスク７３、または半導体メモリ７４に記録されているデータまたはプログラムを読み出して、そのデータまたはプログラムを、バス５６を介してプログラム用ＲＡＭ／ＲＯＭ５３に供給する。
【００４３】
次に、指紋読み取りセンサ２１について説明する。指紋読み取りセンサ２１は、上述したように、指４１をセンサ面に直接触れさせることで指紋画像を読み取るものであり、例えば、ソニー社製ＣＸＡ３２７１ＧＥを用いることができる。
【００４４】
指紋読み取りセンサ２１においては、金属電極をアレイ状に並べた上面に絶縁膜を設けてセンサ面が構成される。指紋読み取りセンサ２１のセンサ面に指を置いたとき、金属電極、絶縁膜、および指４１の３つでコンデンサが形成される。この場合、指４１は、電極として機能する。
【００４５】
指４１の指紋の隆起部（電極）から指紋読み取りセンサ２１の金属電極までの距離は、指４１の指紋の谷部（電極）から指紋読み取りセンサ２１の金属電極までの距離より短い。また、指４１の指紋の隆起部が絶縁膜に接するので、指４１の指紋の隆起部で形成されるコンデンサの容量値は、ほぼ、絶縁膜の誘電率で決まる。
【００４６】
これに対して、指４１の指紋の谷部においては、電極である指４１と絶縁膜との間に空気層が入るので、指４１の指紋の谷部で形成されるコンデンサの容量値は、指４１の指紋の隆起部で形成されるコンデンサの容量値と大きく異なる。
【００４７】
そこで、指紋読み取りセンサ２１は、金属電極、絶縁膜、および指４１の指紋の隆起部、並びに、金属電極、絶縁膜、および指４１の指紋の谷部でそれぞれ形成されるコンデンサに蓄積される電荷を電圧に変換することで、指紋の凹凸を電気信号として出力する。
【００４８】
図４は、指紋読み取りセンサ２１の原理的な構成を示す図である。
【００４９】
図４に示すように、指紋読み取りセンサ２１は、シリコン（Ｓｉ）基板１０１上に層間膜１０２を介して金属電極１０３（サンプリング点）を８０μｍのピッチでアレイ状に配置し、その上面を絶縁膜（Ｏｖｅｒ  Ｃｏａｔ）１０４で覆った構成を有する。指紋読み取りセンサ２１は、絶縁膜１０４の上面に直接置かれた指４１の指紋の凹凸を検出する。
【００５０】
すなわち、指４１は導体なので、指４１が絶縁膜１０４の上面に置かれたとき、金属電極１０３、絶縁膜１０４、および指４１でコンデンサ１０６が形成される。そして、指紋の隆起部４１Ａおよび谷部４１Ｂの凹凸により、電極である指４１から金属電極１０３までの距離の異なるコンデンサ１０６が形成されることになり、指紋の隆起部４１Ａおよび谷部４１Ｂの凹凸は、コンデンサ１０６の容量値の違いとなって現れる。
【００５１】
また、指紋の隆起部４１Ａは、絶縁膜１０４に接触しているので、隆起部４１Ａにより形成されるコンデンサ１０６の容量値は、絶縁膜１０４の誘電率および絶縁膜１０４の厚さで決まる。これに対して、指紋の谷部４１Ｂにおいては、電極である指４１と金属電極１０３との間に、絶縁膜１０４に加えて空気層が入るので、谷部４１Ｂにより形成されるコンデンサ１０６の容量値は、絶縁膜１０４の誘電率および絶縁膜１０４の厚さ、並びに空気の誘電率およびその厚さで決まる。
【００５２】
すなわち、指４１の指紋の谷部４１Ｂで形成されるコンデンサ１０６の容量値と、指４１の指紋の隆起部４１Ａで形成されるコンデンサ１０６の容量値とは、大きく異なる。
【００５３】
従って、指４１が指紋読み取りセンサ２１の上面（センサ面）に接触しているとき、金属電極１０３に一定電圧を印加すれば、指４１の指紋の隆起部４１Ａのコンデンサ１０６に蓄積される電荷の量と、谷部４１Ｂのコンデンサ１０６に蓄積される電荷の量は異なる。指紋読み取りセンサ２１は、コンデンサ１０６に蓄積された電荷を電圧に変換して、指紋の凹凸を電気信号として出力する。
【００５４】
次に、指紋読み取りセンサ２１の、指紋の凹凸を電気信号に変換する動作について説明する。図５は、指紋読み取りセンサ２１の内部回路を示す回路図である。
【００５５】
指紋読み取りセンサ２１は、指紋の凹凸による容量値を電荷として検出するセンサ部２１Ａ、センサ部２１Ａから出力された電荷を電圧信号に変換するセンスアンプ部２１Ｂ、およびセンスアンプ部２１Ｂから出力された電圧信号を増幅し、出力する出力部２１Ｃから構成される。
【００５６】
指紋読み取りセンサ２１は、センスアンプ部２１Ｂに、電荷を電圧信号に変換するための差動アンプ１２１を有し、出力部２１Ｃに、電圧信号を増幅するための差動アンプ１２２、および出力インピーダンスを調整するための差動アンプ１２３を有する。
【００５７】
なお、図５において、コンデンサＣｓは、指４１と金属電極１０３との間で形成されるコンデンサ１０６を示す。以下、コンデンサＣｓの容量は、単に、Ｃｓと記述する。
【００５８】
センサ部２１ＡのコンデンサＣｐは、金属電極１０３とシリコン基板１０１との間で形成される寄生容量に等価なコンデンサである。以下、コンデンサＣｐの容量は、単に、Ｃｐと記述する。センサ部２１ＡのコンデンサＣｓおよびコンデンサＣｐは、直列に接続される。コンデンサＣｓおよびコンデンサＣｐの接続点の電圧を、Ｖｃｅｌと記述する。
【００５９】
また、センスアンプ部２１ＢのコンデンサＣｐ’は、寄生容量によるコンデンサＣｐの容量をキャンセルする目的のコンデンサである。コンデンサＣｐ’の一方の端子は接地され、コンデンサＣｐ’の他方の端子は、スイッチＳｗ３を介して、差動アンプ１２１の反転入力端子に接続されている。以下、コンデンサＣｐ’の容量は、単に、ＣＰ’と記述する。コンデンサＣＰ’の容量は、コンデンサＣｐの容量にほぼ等しい。
【００６０】
センスアンプ部２１ＢのコンデンサＣｈ１の一方の端子は接地され、コンデンサＣｈ１の他方の端子は、スイッチＳｗ５を介して差動アンプ１２１の出力端子に接続されると共に、スイッチＳｗｅを介して差動アンプ１２２の反転入力端子に接続されている。出力部２１ＣのコンデンサＣｈ２の一方の端子は接地され、コンデンサＣｈ２の他方の端子は、スイッチＳｗ７を介して、差動アンプ１２２の出力端子に接続されると共に、差動アンプ１２３の非反転入力端子に接続されている。センスアンプ部２１ＢのコンデンサＣｈ１および出力部２１ＣのコンデンサＣｈ２は、電圧を保持するための、いわゆるホールド容量である。
【００６１】
以下、コンデンサＣｈ１の容量は、単に、Ｃｈ１と記述する。コンデンサＣｈ２の容量は、単に、Ｃｈ２と記述する。
【００６２】
また、センスアンプ部２１ＢのコンデンサＣｆ１の一方の端子は、差動アンプ１２１の反転入力端子に接続され、コンデンサＣｆ１の他方の端子は、差動アンプ１２１の出力端子に接続されている。コンデンサＣｆ１の容量は、差動アンプ１２１のゲインを決める帰還容量である。
【００６３】
以下、コンデンサＣｆ１の容量は、単に、Ｃｆ１と記述する。
【００６４】
出力部２１ＣのコンデンサＣｆ２の一方の端子は、差動アンプ１２２の反転入力端子に接続され、コンデンサＣｆ２の他方の端子は、差動アンプ１２２の出力端子に接続されている。コンデンサＣｆ２の容量は、差動アンプ１２２のゲインを決める帰還容量である。以下、コンデンサＣｆ２の容量は、単に、Ｃｆ２と記述する。
【００６５】
センスアンプ部２１ＢのスイッチＳｗｒは、コンデンサＣｓおよびコンデンサＣｐの接続点と、差動アンプ１２１の反転入力端子とを接続するか、または切断する。センスアンプ部２１ＢのスイッチＳｗｅは、コンデンサＣｈ１の接地されていない端子と、差動アンプ１２２の反転入力端子とを接続するか、または切断する。
【００６６】
センスアンプ部２１Ｂにおいて、スイッチＳｗ１の一方の端子には、電圧ＶＨが印加され、他方の端子は、差動アンプ１２１の非反転入力端子に接続される。スイッチＳｗ２の一方の端子には、電圧ＶＭが印加され、他方の端子は、差動アンプ１２１の非反転入力端子に接続される。スイッチＳｗ１１の一方の端子には、電圧ＶＬが印加され、他方の端子は、差動アンプ１２１の非反転入力端子に接続される。
【００６７】
電圧ＶＨは、電圧ＶＭより高く、電圧ＶＭは、電圧ＶＬより高い。また電圧ＶＨと電圧ＶＭとの差は、電圧ＶＭと電圧ＶＬとの差にほぼ等しい。
【００６８】
スイッチＳｗ３の一方の端子は、コンデンサＣｐ’の接地されていない端子に接続され、スイッチＳｗ３の他方の端子は、差動アンプ１２１の反転入力端子に接続されている。
【００６９】
スイッチＳｗ４の一方の端子は、コンデンサＣｆ１の一方の端子に接続され、スイッチＳｗ４の他方の端子は、コンデンサＣｆ１の他方の端子に接続されている。すなわち、スイッチＳｗ４は、コンデンサＣｆ１に並列に接続されている。
【００７０】
スイッチＳｗ５の一方の端子は、差動アンプ１２１の出力端子に接続され、スイッチＳｗ５の他方の端子は、コンデンサＣｈ１の接地されていない端子に接続されるとともに、スイッチＳｗｅを介して差動アンプ１２２の反転入力端子に接続されている。
【００７１】
出力部２１ＣのスイッチＳｗ６の一方の端子は、コンデンサＣｆ２の一方の端子に接続され、スイッチＳｗ６の他方の端子は、コンデンサＣｆ２の他方の端子に接続されている。すなわち、スイッチＳｗ６は、コンデンサＣｆ２に並列に接続されている。
【００７２】
出力部２１ＣのスイッチＳｗ７の一方の端子は、差動アンプ１２２の出力端子に接続され、スイッチＳｗ７の他方の端子は、コンデンサＣｈ２の接地されていない端子に接続されると共に、差動アンプ１２３の非反転入力端子に接続されている。
【００７３】
差動アンプ１２２の非反転入力端子には、電圧ＶＯＳが印加されている。
【００７４】
次に、指紋読み取りセンサ２１の内部回路の動作について説明する。
【００７５】
なお、スイッチＳｗｒ、スイッチＳｗｅ、スイッチＳｗ１乃至スイッチＳｗ７、並びにスイッチＳｗ１１が、切断している状態、すなわちオフしている状態から、指紋読み取りセンサ２１の動作が開始される。
【００７６】
（１）初期状態、すなわち、スイッチＳｗｒ、スイッチＳｗｅ、スイッチＳｗ１乃至スイッチＳｗ７、並びにスイッチＳｗ１１が、オフしている状態から、まず、スイッチＳｗ１、スイッチＳｗ４、およびスイッチＳｗｒが、接続、すなわちオンされる。従って、コンデンサＣｓとコンデンサＣｐとの接続点の電圧Ｖｃｅｌは、ＶＨとされる。このとき、コンデンサＣｓおよびコンデンサＣｐに蓄積される電荷は、（Ｃｓ＋Ｃｐ）ＶＨとなる。
（２）その後、スイッチＳｗ１、およびスイッチＳｗｒがオフされる。
（３）次に、スイッチＳｗ１１、およびスイッチＳｗ３がオンされ、コンデンサＣｐ’とスイッチＳｗ３の接続点の電圧ＶｄｍｙをＶＬとする。ここで、コンデンサＣｐ’に蓄積される電荷は、Ｃｐ’ＶＬとなる。
（４）その後、スイッチＳｗ３、およびスイッチＳｗ１１がオフされる。
（５）次に、スイッチＳｗ２がオンされ、差動アンプ１２１の反転入力端子に印加される電圧ＶｓｌをＶＭとする。
（６）その後、スイッチＳｗ４がオフされる。
（７）次に、スイッチＳｗｒ、スイッチＳｗ３、およびスイッチＳｗ５がオンされる。このとき、電圧ＶｃｅｌはＶＨであり、電圧ＶｄｍｙはＶＬであり、差動アンプ１２１の反転入力端子に印加される電圧ＶｓｌはＶＭなので、コンデンサＣｓ、コンデンサＣｐ、およびコンデンサＣｐ’間で、式（１）で示される電荷が移動する。
【００７７】
（Ｃｓ＋Ｃｐ）（ＶＨ−ＶＭ）−Ｃｐ  ’（ＶＭ−ＶＬ）
≒Ｃｓ（ＶＨ−ＶＭ）      （１）
【００７８】
従って、差動アンプ１２１の出力電圧Ｖｓｎｓは、式（２）で示される。
【００７９】
Ｖｓｎｓ＝ＶＭ−Ｃｓ（ＶＨ−ＶＭ）／Ｃｆ１                （２）
【００８０】
このように、センスアンプ部２１Ｂのゲインは、金属電極１０３とシリコン基板１０１との間で形成される寄生容量Ｃｐに依存することなく決まるので、ダイナミックレンジを大きくすることができる。
【００８１】
そして、コンデンサＣｈ１には、式（２）で求められる電圧Ｖｓｎｓが印加される。
【００８２】
（８）その後、スイッチＳｗ５がオフされる。
（９）次に、スイッチＳｗ６がオンされ、コンデンサＣｆ２の入力側（差動アンプ１２２の反転入力端子側）の電圧ＶｏｉがＶＯＳとされる。
（１０）その後、スイッチＳｗ６がオフされる。
（１１）次に、スイッチＳｗｅおよびスイッチＳｗ７がオンされる。このとき、コンデンサＣｈ１からコンデンサＣｆ２に移動する電荷は、（ＶＯＳ−Ｖｓｎｓ）Ｃｈ１である。これにより、コンデンサＣｆ２の出力側（差動アンプ１２２の出力端子側）の電圧Ｖｏｏが決定し、コンデンサＣｈ２に電荷が蓄積される。
【００８３】
そして、この電圧Ｖｏｏがバッファアンプである差動アンプ１２３を介して、出力端子Ａｏｕｔに出力される。
【００８４】
次に、図６と図７のフローチャートを参照して、図２の指紋照合装置１における指紋登録処理を説明する。なお、この処理は、ユーザにより、指紋登録処理を開始する指令が行なわれ、かつ、指紋読み取りセンサ２１に、ユーザの指が押圧されたとき開始される。
【００８５】
ステップＳ１において、指紋読み取りセンサ２１は、指紋読み取りセンサ２１に押圧され、接触された指の指紋の画像を読み取る。そして、読み取った指紋に対応する信号が、指紋読み取り用ＬＳＩ５１に供給される。
【００８６】
ステップＳ２において、指紋読み取り用ＬＳＩ５１は、指紋読み取りセンサ２１から供給された指紋に対応する信号から、指紋の画像データを生成する。
【００８７】
ステップＳ３において、指紋読み取り用ＬＳＩ５１は、生成した指紋の画像データを、２５６階調のグレー画像データに変換し、変換した２５６階調のグレー画像データをＣＰＵ５２に供給する。具体的には、図８に示されるような、１２８画素×１２８画素のグレー画像２００のデータが取得される。画像２０１は、画像２００の中の９６画素×９６画素の画像である。
【００８８】
ステップＳ４において、ＣＰＵ５２は、変換されたグレー画像データに対して、ノイズ除去や指紋隆線内の微少な傷を埋めるなどの前処理を実行する。前処理が行なわれた画像は、図９に示されるように、ノイズが除去された画像となる。
【００８９】
ステップＳ５において、ＣＰＵ５２は、前処理されたグレー画像データを、所定の閾値で２値化し、２値化画像データに変換する。図１０は、２値化画像を表わしている。
【００９０】
ステップＳ６において、ＣＰＵ５２は、細線化処理を行なう。具体的には、ステップＳ５の処理により得られた２値化画像のデータのうち、値が１である部分から線幅が１画素分の幅になるような中心線を抽出する処理が行なわれる。これにより、線幅が１画素分の幅となり、かつ、連結性が保持されるため、この後の指紋隆線の分岐点や端点を検出するのが容易になる。ステップＳ６の処理により細線化処理が行なわれた画像は、図１１に示されるようになる。
【００９１】
ステップＳ７において、ＣＰＵ５２は、細線化処理された画像から、分岐点と端点をそれぞれ最大１０個まで検出する。ステップＳ７の処理により検出された分岐点と端点は、図１２に示されるようになる。検出される分岐点と端点は、実際には、図１２の１２８画素×１２８画素の画像２００のうち、９６画素×９６画素で示される画像２０１が対象となる。これにより抽出する分岐点と端点を減らすことができる。図１２において、分岐点は、Ｐ１乃至Ｐ８（８個）とされ、分岐点Ｐ１乃至Ｐ８における座標は、それぞれ、Ｐ１（ｘｐ１，ｙｐ１），Ｐ２（ｘｐ２，ｙｐ２），Ｐ３（ｘｐ３，ｙｐ３），Ｐ４（ｘｐ４，ｙｐ４），Ｐ５（ｘｐ５，ｙｐ５），Ｐ６（ｘｐ６，ｙｐ６），Ｐ７（ｘｐ７，ｙｐ７），およびＰ８（ｘｐ８，ｙｐ８）とされる。また、端点は、Ｑ１乃至Ｑ１０（１０個）とされ、端点Ｑ１乃至Ｑ１０における座標は、それぞれ、Ｑ１（ｘｑ１，ｙｑ１），Ｑ２（ｘｑ２，ｙｑ２），Ｑ３（ｘｑ３，ｙｑ３），Ｑ４（ｘｑ４，ｙｑ４），Ｑ５（ｘｑ５，ｙｑ５），Ｑ６（ｘｑ６，ｙｑ６），Ｑ７（ｘｑ７，ｙｑ７），Ｑ８（ｘｑ８，ｙｑ８），Ｑ９（ｘｑ９，ｙｑ９）およびＱ８（ｘｑ１０，ｙｑ１０）とされる。
【００９２】
なお、いまの例の場合、ＣＰＵ５２は、検出する分岐点と端点を最大１０個としたが、これに限らず、例えば、前もって決められた最大数のリミットとしてもよいし、１０個以上と設定してもよい。また、ＣＰＵ５２は、検出する分岐点と端点の対象を、９６画素×９６画素で示される画像２０１としたが、これに限らず、例えば、１１２画素×１１２画素で構成される画像とすることもできる。
【００９３】
ステップＳ８において、ＣＰＵ５２は、プログラム用ＲＡＭ／ＲＯＭ５３のＲＡＭ部分に、検出した分岐点と端点の座標（ｘ，ｙ）（すなわち、Ｐｉ（ｘｐｉ，ｙｐｉ）（ただし、ｉ＝１，２，・・・，，８）、およびＱｉ（ｘｑｉ，ｙｑｉ）（ただし、ｉ＝１，２，・・・，，１０））を記憶させる。なお、この記憶は一時的なものであるので、（フラッシュメモリ５４ではなく）プログラム用ＲＡＭ／ＲＯＭ５３のＲＡＭ部分に記憶される。
【００９４】
ステップＳ９において、ＣＰＵ５２は、登録画像の中心である中心点Ｃ（ｉｎ，ｊｎ）を検出する。具体的には、図１２に示されるように、画像２０１の縦軸の中心線と横軸の中心線が交差する点が登録画像の中心点とされる。ここで求める中心は、登録画像の中心であって、指紋の中心ではないので、迅速かつ簡単に求めることができる。なお、いまの例の場合、画像２００は１２８画素×１２８画素とされているので、ＣＰＵ５２は、あらかじめ設定されている点（６４，６４）（または、（６３，６３））を中心点Ｃとして検出する。
【００９５】
ステップＳ１０において、ＣＰＵ５２は、ステップＳ９の処理により求めた登録画像の中心である中心点Ｃ（ｉｎ，ｊｎ）と、ステップＳ７の処理により検出した複数の分岐点の距離をそれぞれ演算する。いまの例の場合、中心点Ｃと分岐点Ｐ１乃至Ｐ８の間の距離がそれぞれ演算される。中心点Ｃと分岐点Ｐ１の間の距離をＬｐ１とすると、中心点Ｃと分岐点Ｐ２の間の距離はＬｐ２とされ、中心点Ｃと分岐点Ｐ３の間の距離はＬｐ３とされる。以下、順次、中心点ＣとＰ４，Ｐ５，・・・，Ｐ８間の距離が、Ｌｐ４，Ｌｐ５，・・・，Ｌｐ８とされる。
【００９６】
ステップＳ１１において、ＣＰＵ５２は、ステップＳ１０の処理により演算した距離（中心点Ｃと分岐点Ｐ１乃至Ｐ８の間の距離）を短いものの順にソートする。いまの例の場合、中心からの距離は、Ｌｐ１＜Ｌｐ２＜Ｌｐ３＜Ｌｐ４＜Ｌｐ５＜Ｌｐ６＜Ｌｐ７＜Ｌｐ８とされる。
【００９７】
ステップＳ１２において、ＣＰＵ５２は、中心点Ｃ（ｉｎ，ｊｎ）と、ステップＳ７の処理により検出した複数の端点の距離をそれぞれ演算する。いまの例の場合、中心点Ｃと端点Ｑ１乃至Ｑ１０の間の距離がそれぞれ演算される。中心点Ｃと端点Ｑ１間の距離をＬｑ１とすると、中心点Ｃと端点Ｑ２の間の距離はＬｑ２とされ、中心点Ｃと端点Ｑ３の間の距離はＬｑ３とされる。以下、順次、中心点ＣとＱ４，Ｑ５，・・・，Ｑ１０間の距離がＬｑ４，Ｌｑ５，・・・，Ｌｑ１０とされる。
【００９８】
ステップＳ１３において、ＣＰＵ５２は、ステップＳ１２の処理により演算した距離（中心点Ｃと端点Ｑ１乃至Ｑ１０の間の距離）を短いものの順にソートする。いまの例の場合、中心からの距離は、Ｌｑ１＜Ｌｑ２＜Ｌｑ３＜Ｌｑ４＜Ｌｑ５＜Ｌｑ６＜Ｌｑ７＜Ｌｑ８＜Ｌｑ９＜Ｌｑ１０とされる。
【００９９】
ステップＳ１４において、ＣＰＵ５２は、指紋の中心点Ｃ（ｉｎ，ｊｎ）（ステップＳ９の処理により求めた中心点）に近い（いまの例の場合、最大１０個までの）分岐点において、互いに最も近い３点を結ぶ３角形を全て作成する。なお、上述したように、いまの例の場合、ＣＰＵ５２は、指紋の中心点に近い最大１０個までの分岐点において、互いに最も近い３点を結ぶ３角形を全て作成するとしているが、これに限らず、ステップＳ７の処理により検出された分岐点の個数と対応して、変更させることもできる。
【０１００】
具体的には、ＣＰＵ５２は、中心点Ｃ（ｉｎ，ｊｎ）に最も近い分岐点Ｐ１（ｘｐ１，ｙｐ１）（中心点Ｃからの距離Ｌｐ１が最も小さいため、分岐点Ｐ１が選択される）と、分岐点Ｐ１に最も近い２つの分岐点Ｐ２（ｘｐ２，ｙｐ２）およびＰ３（ｘｐ３，ｙｐ３）を結んで、図１３に示されるような３角形Ｗ１を作成する。
【０１０１】
その後、ＣＰＵ５２は、中心点Ｃに２番目に近い分岐点Ｐ２（ｘｐ２，ｙｐ２）（中心点Ｃからの距離Ｌｐ２が２番目に小さいため、分岐点Ｐ２が選択される）と、分岐点Ｐ２に最も近い２つの分岐点Ｐ１（ｘｐ１，ｙｐ１）および分岐点Ｐ３（ｘｐ３，ｙｐ３）を結んで、３角形を作成する。いまの場合、上述した３角形Ｗ１と全く同じである。以下、全く同じ３角形が作成される場合、その記載は省略する。
【０１０２】
これを順次繰り返すことにより、中心点Ｃに３番目に近い分岐点Ｐ３と、分岐点Ｐ３に最も近い２つの分岐点Ｐ２，Ｐ４を結んだ３角形Ｗ２、中心点Ｃに４番目に近い分岐点Ｐ４と、分岐点Ｐ４に最も近い２つの分岐点Ｐ３，Ｐ７を結んだ３角形Ｗ３、および、中心点Ｃに５番目に近い分岐点Ｐ５と、分岐点Ｐ５に最も近い２つの分岐点Ｐ６，Ｐ８を結んだ３角形Ｗ４の４個の３角形が作成される（中心点Ｃに６番目に近い分岐点Ｐ６、中心点Ｃに７番目に近い分岐点Ｐ７、および中心点Ｃに８番目に近い分岐点Ｐ８に基づいて作成される３角形は、それぞれ、上述した３角形Ｗ１，Ｗ２，Ｗ３，またはＷ４のいずれかと重複するため、省略している）。
【０１０３】
このように、中心から近い順番に、各分岐点と、それに最も近い２つの分岐点により３角形を作成すると、例えば、１つ目の３角形と２つ目の３角形、または３つ目の３角形が全く同じ分岐点により構成される場合も生じる。このことは、中心に近い分岐点から順番に、漏れることなく、各分岐点とそれに最も近い２つの分岐点において３角形を作成していることを示している。具体的には、中心点Ｃ（ｉｎ，ｊｎ）に最も近い分岐点Ｐ１（ｘｐ１，ｙｐ１）と、分岐点Ｐ１に最も近い２つの分岐点Ｐ２（ｘｐ２，ｙｐ２）およびＰ３（ｘｐ３，ｙｐ３）を結んで作成された３角形Ｗ１と、中心点Ｃに２番目に近い分岐点Ｐ２（ｘｐ２，ｙｐ２）と、分岐点Ｐ２に最も近い２つの分岐点Ｐ１（ｘｐ１，ｙｐ１）および分岐点Ｐ３（ｘｐ３，ｙｐ３）を結んで作成された３角形は、３角形Ｗ１と全く同じであるが、このような３角形も、漏れることなく作成される。
【０１０４】
ステップＳ１５において、ＣＰＵ５２は、作成した複数の３角形の面積と辺の長さを計算する。いまの例の場合、作成された３角形は４個（３角形Ｗ１，Ｗ２，Ｗ３，およびＷ４）である（実際には、重複する３角形が作成されているため、４個以上の３角形が作成されているが、いまの例の場合では、異なる３角形は４個とされる）ので、４個のそれぞれについて、面積と各辺の長さが計算される。これにより、３角形Ｗ１については、３角形Ｗ１の面積Ｓ１、分岐点Ｐ１と分岐点Ｐ２（以下、このような場合、Ｐ１Ｐ２のように記載する）間の距離、Ｐ２Ｐ３間の距離、およびＰ３Ｐ１間の距離が計算され、３角形Ｗ２については、３角形Ｗ２の面積Ｓ２、Ｐ２Ｐ３，Ｐ３Ｐ４，およびＰ４Ｐ２間の距離が計算され、３角形Ｗ３については、３角形Ｗ３の面積Ｓ３、Ｐ３Ｐ４間の距離、Ｐ４Ｐ７間の距離、およびＰ７Ｐ３間の距離が計算され、３角形Ｗ４については、３角形Ｗ４の面積Ｓ４、Ｐ５Ｐ６間の距離、Ｐ６Ｐ８間の距離、およびＰ８Ｐ５間の距離（辺の長さ）が求められる。
【０１０５】
ステップＳ１６において、ＣＰＵ５２は、フラッシュメモリ５４に、それぞれの３角形の面積と各辺の長さを登録テンプレートに記憶させる。このように面積と辺の長さの集合に過ぎないので、そのデータ量は少ない。
【０１０６】
ステップＳ１７において、ＣＰＵ５２は、それぞれの３角形の３点に最も近い端点の位置を計算する。具体的には、図１３の例の場合、３角形Ｗ１を構成する分岐点は、分岐点Ｐ１，Ｐ２およびＰ３とされるので、ＣＰＵ５２は、分岐点Ｐ１に最も近い端点Ｑ２（ｘｑ２，ｙｑ２）、分岐点Ｐ２に最も近い端点Ｑ１（ｘｑ１，ｙｑ１）、および分岐点Ｐ３に最も近い端点Ｑ１（ｘｑ１，ｙｑ１）を検出し、それぞれの方向と距離（Ｐ１Ｑ２間の方向と距離、Ｐ２Ｑ１間の方向と距離、Ｐ３Ｑ１間の方向と距離）を計算する。なお、いまの例の場合、位置として、方向と距離を求めるようにしたが、少なくともいずれか１つとしてもよい。この処理が繰り返され、３角形Ｗ２についてＰ３Ｑ１間、Ｐ２Ｑ１間、Ｐ４Ｑ７間の方向と距離（以下、これを、位置とも称する）が求められ、３角形Ｗ３についてＰ３Ｑ１間、Ｐ４Ｑ７間、および、Ｐ７Ｑ７間の位置が求められ、３角形Ｗ４についてＰ５Ｑ６間、Ｐ６Ｑ６間、およびＰ８Ｑ６間の位置が求められる。
【０１０７】
ステップＳ１８において、ＣＰＵ５２は、ステップＳ１７の処理により求めた端点の位置をそれぞれの３角形の面積と各辺の長さ（ステップＳ１６の処理により記憶した３角形の面積と各辺の長さ）に関連付し、登録テンプレートとして記憶させる。いまの例の場合、３角形Ｗ１，Ｗ２，Ｗ３およびＷ４の面積Ｓ１，Ｓ２，Ｓ３，Ｓ４、各辺（３辺）の長さ（例えば、Ｗ１の場合、Ｐ１Ｐ２間の長さ、Ｐ２Ｐ３間の長さ、Ｐ３Ｐ１間の長さ）、端点の位置（３角形Ｗ１の場合、Ｐ１Ｑ２間の位置、Ｐ２Ｑ１間の位置、Ｐ３Ｑ１間の位置）がそれぞれ記憶される。なお、いまの例の場合、３角形Ｗ１においてＰ３Ｑ１の位置が求められ、３角形Ｗ２においてもＰ３Ｑ１の位置が求められる（同じ分岐点に対応する同じ端点との間の位置が求められる）ようになっているが、同じ点の位置については、計算を省略するようにしてもよい。
【０１０８】
ステップＳ１９において、ＣＰＵ５２は、ＵＳＢコントローラ５５を介して、図示せぬ外部の機器から供給された、指紋を読み取っている使用者のＩＤを取得し、フラッシュメモリ５４に記憶されている登録テンプレート（ステップＳ１６とステップＳ１８の処理によりフラッシュメモリ５４に記憶された登録テンプレート）に関連付けして記憶させる。
【０１０９】
図６と図７の処理により、使用者のＩＤとともに、指紋画像から抽出した複数の３角形の面積、各辺の長さ、特定の分岐点（３角形を構成する分岐点）に対応する（に最も近接する）端点の位置（方向または距離）をその指紋の特徴として記憶させることができる。
【０１１０】
なお、ステップＳ１９の使用者のＩＤを記憶させる処理は、認証登録処理を開始するとき、予め（ステップＳ１の前に）行なわれていてもよい。
【０１１１】
次に、図１４乃至図１７のフローチャートを参照して、図２の指紋照合装置１における指紋照合処理を説明する。なお、この処理は、図６と図７の指紋登録処理が行なわれた後に実行される処理であり、指紋読み取りセンサ２１に、ユーザの指が押圧されたとき開始される。なお、ステップＳ１０１乃至ステップＳ１１３の処理は、上述した図６のステップＳ１乃至ステップＳ１３と殆ど同様であるので、簡単に説明する。
【０１１２】
ステップＳ１０１において、指読み取りセンサ２１は、指紋読み取りセンサ２１に押圧され、接触された指の指紋の画像を読み取り、読み取った指紋の画像に対応する信号を、指紋読み取り用ＬＳＩ５１に供給する。
【０１１３】
ステップＳ１０２において、指紋読み取り用ＬＳＩ５１は、指紋読み取りセンサ２１から供給された指紋に対応する信号から、指紋の画像データを生成する。
【０１１４】
ステップＳ１０３において、指紋読み取り用ＬＳＩ５１は、生成した指紋の画像データを、２５６階調のグレー画像データに変換し、変換した２５６階調のグレー画像データをＣＰＵ５２に供給する。
【０１１５】
ステップＳ１０４において、ＣＰＵ５２は、変換されたグレー画像データに対して、ノイズ除去や指紋隆線内の微少な傷を埋めるなどの前処理を実行する。具体的には、図１８に示されるような、１２８画素×１２８画素のグレー画像３００のデータが生成される。画像３０１は、９６画素×９６画素の画像である。図１８に示されるグレー画像と、図９のグレー画像２００を比較すると、図９の画像に比べて指紋の位置が右上にずれている。
【０１１６】
ステップＳ１０５において、ＣＰＵ５２は、前処理されたグレー画像データを、所定の閾値で２値化し、２値化画像データに変換する。図１９は、２値化画像を表わしている。
【０１１７】
ステップＳ１０６において、ＣＰＵ５２は、細線化処理を行なう。これにより、図２０に示されるような画像に変換される。
【０１１８】
ステップＳ１０７において、ＣＰＵ５２は、細線化処理された画像から、分岐点と端点をそれぞれ最大１０個まで検出する。この処理により検出された分岐点と端点は、図２１に示されるようになる。このとき、検出される分岐点と端点は、実際には、図２１の１２８画素×１２８画素の画像３００のうち、９６画素×９６の画素で示される画像３０１が対象となる。図２１において、分岐点は、Ｐｂ１乃至Ｐｂ７（７個）とされ、端点は、Ｑｂ１乃至Ｑｂ１０（１０個）とされる。
【０１１９】
なお、いまの例の場合、ＣＰＵ５２は、検出する分岐点と端点を最大１０個としたが、上述した図６および図７の処理と同様に、これに限らず、例えば、前もって決められた最大数のリミットとしてもよいし、１０個以上と設定してもよい。また、ＣＰＵ５２は、検出する分岐点と端点の対象を、９６画素×９６画素で示される画像３０１としたが、これに限らず、例えば、１１２画素×１１２画素で示される画像とすることもできる。
【０１２０】
図１３と図２１を比較するに、図１３の分岐点Ｐ１は図２１の分岐点Ｐｂ１に対応しており、分岐点Ｐ２は分岐点Ｐｂ２に対応しており、分岐点Ｐ３は分岐点Ｐｂ５に対応しており、分岐点Ｐ４は分岐点Ｐｂ７に対応しており、分岐点Ｐ５は分岐点Ｐｂ３に対応しており、分岐点Ｐ６は分岐点Ｐｂ４に対応しており、分岐点Ｐ８は分岐点Ｐｂ６に対応している。すなわち、図１３と図２１では、取り込まれた画像の位置が異なるため（ユーザが指を置く位置は、その都度変化するため）、図１３において検出された分岐点Ｐ７は、図２１では検出されていない。また、分岐点Ｐｂｉの座標は、分岐点Ｐｂｉ（ｘｐｂｉ，ｙｐｂｉ）（ただし、ｉ＝１，２，・・・，７）とされ、端点Ｑｂｉの座標は端点Ｑｂｉ（ｘｑｂｉ，ｙｑｂｉ）（ただし、ｉ＝１，２，・・・，１０）とされる。
【０１２１】
ステップＳ１０８において、ＣＰＵ５２は、プログラム用ＲＡＭ／ＲＯＭ５３のＲＡＭ部分に、検出した分岐点と端点の座標（ｘ，ｙ）（すなわち、Ｐｂｉ（ｘｐｂｉ，ｙｐｂｉ）（ただし、ｉ＝１，２，・・・，７）、およびＱｂｉ（ｘｑｂｉ，ｙｑｂｉ）（ただし、ｉ＝１，２，・・・，１０））を記憶させる。なお、この記憶は一時的なものであるので、（フラッシュメモリ５４ではなく）プログラム用ＲＡＭ／ＲＯＭ５３のＲＡＭ部分に記憶される。
【０１２２】
ステップＳ１０９において、ＣＰＵ５２は、指紋画像の中心点Ｃｂ（ｉｎ，ｊｎ）を検出する。なお、画像３００は１２８画素×１２８画素とされているので、上述した図６のステップＳ９における場合と同様に、ＣＰＵ５２は、あらかじめ設定されている点（６４，６４）（または、（６３，６３））を、中心点として検出するようにしてもよい。
【０１２３】
ステップＳ１１０において、ＣＰＵ５２は、ステップＳ１０９の処理により求めた指紋画像の中心点Ｃｂ（ｉｎ，ｊｎ）とステップＳ１０７の処理により検出した複数の分岐点の距離をそれぞれ演算する。いまの例の場合、中心点Ｃｂと分岐点Ｐｂ１乃至Ｐｂ７の間の距離がそれぞれ演算される。中心点Ｃｂと分岐点Ｐｂ１の間の距離をＬｐｂ１とすると、中心点Ｃｂと分岐点Ｐｂ２の間の距離はＬｐ２とされ、中心点Ｃｂと分岐点Ｐｂ３の間の距離はＬｐｂ３とされる。以下、順次、中心点ＣｂとＰｂ４，Ｐｂ５，・・・，Ｐｂ７間の距離が、Ｌｐｂ４，Ｌｐｂ５，・・・，Ｌｐｂ７とされる。
【０１２４】
ステップＳ１１１において、ＣＰＵ５２は、ステップＳ１１０の処理により演算した距離（中心点Ｃｂと分岐点Ｐｂ１乃至Ｐｂ７の間の距離）を短いものの順にソートする。いまの例の場合、中心からの距離は、Ｌｐｂ１＜Ｌｐｂ２＜Ｌｐｂ３＜Ｌｐｂ４＜Ｌｐｂ５＜Ｌｐｂ６＜Ｌｐｂ７とされる。
【０１２５】
ステップＳ１１２において、ＣＰＵ５２は、中心点Ｃｂ（ｉｎ，ｊｎ）と、ステップＳ１０７の処理により検出した複数の端点の距離をそれぞれ演算する。いまの例の場合、中心点Ｃｂと端点Ｑｂ１乃至Ｑｂ１０の間の距離がそれぞれ演算される。中心点Ｃｂと端点Ｑｂ１間の距離をＬｑｂ１とすると、中心点Ｃｂと端点Ｑｂ２の間の距離はＬｑｂ２とされ、中心点Ｃｂと端点Ｑｂ３の間の距離はＬｑｂ３とされる。以下、順次、中心点ＣｂとＱｂ４，Ｑｂ５，・・・，Ｑｂ１０間の距離がＬｑｂ４，Ｌｑｂ５，・・・，Ｌｑｂ１０とされる。
【０１２６】
ステップＳ１１３において、ＣＰＵ５２は、ステップＳ１２の処理により演算した距離（中心点Ｃと端点Ｑ１乃至Ｑ８の間の距離）を短いものの順にソートする。いまの例の場合、中心からの距離は、Ｌｑｂ１＜Ｌｑｂ２＜Ｌｑｂ３＜Ｌｑｂ４＜Ｌｑｂ５＜Ｌｑｂ６＜Ｌｑｂ７＜Ｌｑｂ８＜Ｌｑｂ９＜Ｌｑｂ１０とされる。
【０１２７】
ステップＳ１１４において、ＣＰＵ５２は、指紋の中心点Ｃｂ（ｉｎ，ｊｎ）（ステップＳ１０９の処理により求めた中心点）に最も近い分岐点と、その分岐点から最も近い分岐点を２点検出し、その３点を結ぶ３角形を作成する。具体的には、図２１の例の場合、ＣＰＵ５２は、中心点Ｃｂに最も近い分岐点Ｐｂ１と、分岐点Ｐｂ１から最も近い分岐点Ｐｂ２，および分岐点Ｐｂ５を結ぶ３角形Ｗｂ１を作成する。すなわち、ＣＰＵ５２は、中心点Ｃｂ（ｉｎ，ｊｎ）に最も近い分岐点Ｐｂ１（ｘｐｂ１，ｙｐｂ１）（中心点Ｃｂからの距離Ｌｐｂ１が最も小さいため、分岐点Ｐｂ１が選択される）と、分岐点Ｐｂ１に最も近い２つの分岐点Ｐｂ２（ｘｐｂ２，ｙｐｂ２）および分岐点Ｐｂ５（ｘｐｂ５，ｙｐｂ５）の３点を結んで、３角形Ｗｂ１を作成する。
【０１２８】
なお、図２１の例の場合、３角形Ｗ１は３角形Ｗｂ１に対応しており、３角形Ｗ２は３角形Ｗｂ３（このフローチャートでは作成されないが、３角形を全て作成した場合、３角形Ｗｂ３が作成される）に対応しており、３角形Ｗ４は後述する３角形Ｗｂ２に対応している。すなわち、図１３の３角形Ｗ３は図２１では作成されない。
【０１２９】
ステップＳ１１５において、ＣＰＵ５２は、ステップＳ１１４の処理により作成した３角形Ｗｂ１（分岐点Ｐｂ１，Ｐｂ２およびＰｂ５からなる３角形Ｗｂ１）の面積Ｓｂ１を計算する。
【０１３０】
ステップＳ１１６において、ＣＰＵ５２は、フラッシュメモリ５４に記憶されている登録テンプレートを読み出す。
【０１３１】
ステップＳ１１７において、ＣＰＵ５２は、登録テンプレート（指紋登録処理（図６と図７の処理）によりフラッシュメモリ５４に記憶された登録テンプレート）に、いま計算した３角形Ｗｂ１の面積Ｓｂ１と一致する面積を有する登録テンプレートがあるか否かを判定する。指紋は、周辺環境、または体調などによりある程度変形するため、ＣＰＵ５２は、許容範囲を設け、完全に一致しない場合においても、許容範囲内の（すなわち、照合閾値より小さい）値であれば、一致するように判定する。いまの例の場合、図２１の３角形Ｗｂ１は、図７のステップＳ１５の処理において求められた図１３の３角形Ｗ１と対応しているので、その面積Ｓｂ１とＳ１は一致すると判定される。
【０１３２】
ステップＳ１１７において、３角形Ｗｂ１の面積Ｓｂ１と一致する（面積が一致する３角形が、登録テンプレートにある）と判定された場合、ステップＳ１１８において、ＣＰＵ５２は、３角形Ｗｂ１の辺の長さを計算する。具体的には、Ｐｂ１Ｐｂ２間の長さ、Ｐｂ２Ｐｂ５間の長さ、Ｐｂ５Ｐｂ１間の長さが計算される。なお、この長さは、ステップＳ１１４において、面積と同時に計算するようにしてもよい。
【０１３３】
ステップＳ１１９において、ＣＰＵ５２は、ステップＳ１１７の処理により一致すると判定された、登録テンプレートに登録されている３角形（いまの例の場合、３角形Ｗ１）を構成する３辺の長さと、ステップＳ１１８の処理により計算した３辺の長さ（いまの例の場合、３角形Ｗｂ１の３辺の長さ）が一致するか否かを判定する。いまの例の場合、３角形Ｗ１に対応するＰ１Ｐ２間の長さ，Ｐ２Ｐ３間の長さ，およびＰ３Ｐ１間の長さ（図７のステップＳ１６の処理により記憶された辺の長さ）と、ステップＳ１１８の処理により計算した３辺の長さＰｂ１Ｐｂ２間、Ｐｂ２Ｐｂ５間、およびＰｂ５Ｐｂ１間の長さが一致するか否かが判定される。勿論、ＣＰＵ５２は、許容範囲を設け、完全に一致しない場合においても、許容範囲内の（すなわち、照合閾値より小さい）値であれば、一致するように判定する。３角形Ｗ１と３角形Ｗｂ１を構成するそれぞれの分岐点Ｐ１と分岐点Ｐｂ１、分岐点Ｐ２と分岐点Ｐｂ２、および分岐点Ｐ３と分岐点Ｐｂ５は対応しているので、勿論、一致すると判定される。
【０１３４】
ステップＳ１１９において、３辺の長さが一致すると判定された場合、ステップＳ１２０において、ＣＰＵ５２は、その３角形（いまの場合、ステップＳ１１４の処理により作成した３角形Ｗｂ１）を構成する３個の分岐点（分岐点Ｐｂ１，分岐点Ｐｂ２，および分岐点Ｐｂ５）のそれぞれに最も近い端点を検索する。いまの例の場合、分岐点Ｐｂ１に最も近い端点Ｑｂ３（ｘｑｂ３，ｙｑｂ３）、分岐点Ｐｂ２に最も近い端点Ｑｂ７（ｘｑｂ７，ｙｑｂ７）、および分岐点Ｐｂ５に最も近い端点Ｑｂ７（ｘｑｂ７，ｙｑｂ７）が検索される。
【０１３５】
ステップＳ１２１において、ＣＰＵ５２は、ステップＳ１２０の処理により検索した端点の位置を計算する。具体的には、Ｐｂ１Ｑｂ３間の位置、Ｐｂ２Ｑｂ７間の位置、Ｐｂ５Ｑｂ７間の位置が計算される。
【０１３６】
ステップＳ１１８の辺の長さの計算とステップＳ１２０，Ｓ１２１の端点の検索と位置の計算は、ステップＳ１１５において、面積の計算時にまとめて行なうこともできる。ただし、面積が一致しなければ、後の２つの計算は不要となり、辺の長さが一致しなければ、端点の検索と位置の計算は不要となるので、前の条件の判定後、順次計算した方が、計算量が少なくて済み、結果的に迅速な判定が可能になる。
【０１３７】
ステップＳ１２２において、ＣＰＵ５２は、ステップＳ１１７の処理により一致すると判定された３角形を構成する３点の分岐点と、それぞれの分岐点に最も近い端点との位置と、ステップＳ１２１の処理により計算したＰｂ１Ｑｂ３間の位置、Ｐｂ２Ｑｂ７間の位置、および、Ｐｂ５Ｑｂ７間の位置を比較する。いまの例の場合、３角形Ｗ１を構成する３点の分岐点Ｐ１，Ｐ２およびＰ３と、それぞれの分岐点に最も近い端点との位置、すなわち、図７のステップＳ１８の処理により記憶されたＰ１Ｑ２間の位置、Ｐ２Ｑ１間の位置、および、Ｐ３Ｑ１間の位置）と、ステップＳ１２１の処理により計算したＰｂ１Ｑｂ３間の位置、Ｐｂ２Ｑｂ７間の位置、および、Ｐｂ５Ｑｂ７間の位置が比較される。
【０１３８】
ステップＳ１２３において、ＣＰＵ５２は、ステップＳ１２２の処理により比較した、３角形を構成する３個の分岐点と、３個の分岐点にそれぞれ最も近い端点との位置が一致するか否かを判定する。いまの例の場合、Ｐ１Ｑ２間、Ｐ２Ｑ１間、およびＰ３Ｑ１間の位置と、Ｐｂ１Ｑｂ３間の位置、Ｐｂ２Ｑｂ７間の位置、および、Ｐｂ５Ｑｂ７間の位置が一致するか否かが判定される。３角形Ｗｂ１により求められるＰｂ１Ｑｂ３、Ｐｂ２Ｑｂ７、およびＰｂ５Ｑｂ７は、それぞれ、３角形Ｗ１により求められるＰ１Ｑ２、Ｐ２Ｑ１、およびＰ３Ｑ１に対応しているので、一致すると判定される。なお、勿論、所定の範囲内の（すなわち、照合閾値より小さい）誤差は、一致すると判定される。一致すると判定された場合、処理はステップＳ１２４に進み、ＣＰＵ５２は、カウンタに１を加える（１だけインクリメントされる）。いまの例の場合、カウンタの値（初期値は０とされている）は１とされる。
【０１３９】
ステップＳ１２５において、ＣＰＵ５２は、カウンタの値が２であるか否かを判定する。カウンタの値は、作成された１つの３角形の面積、辺の長さ、それぞれの分岐点と端点との間の位置が全て一致した場合に加えられる。いまの例の場合、カウンタの値は１とされる（１つの３角形について認証ができたとされる）ので、ステップＳ１２６において、ＣＰＵ５２は、次の３角形が作成できるか否かを判定する。すなわち、次に中心点Ｃｂに近い分岐点と、その分岐点に最も近い２つの分岐点を結んで、いままでに作成した３角形と異なる３角形が作成できるか否かが判定される。いまの例の場合、２番目（分岐点Ｐ１の次）に中心点Ｃｂに近い分岐点はＰ２であり、分岐点Ｐ２により作成される３角形は、３角形Ｗｂ１と同じであるため新しい３角形は作成できないが、３番目に中心点Ｃｂに近い分岐点Ｐ３を用いて作成する３角形Ｗｂ２が作成できるため、次の３角形は作成できると判定される。
【０１４０】
ステップＳ１２６において、次の３角形が作成できると判定された場合、ステップＳ１２７に進み、ＣＰＵ５２は、次の３角形を作成する。すなわち、ステップＳ１０７の処理により、図２１から分岐点Ｐｂ１乃至Ｐｂ７と端点Ｑｂ１乃至Ｑｂ１０が検出されているので、ＣＰＵ５２は、図６のステップＳ１４の処理と同様にして、３番目に中心点Ｃｂに距離が近い分岐点Ｐｂ３と、分岐点Ｐｂ３に最も近い２個の分岐点Ｐｂ４，および分岐点Ｐｂ６を結ぶ３角形Ｗｂ２を作成する。上述したように、ステップＳ１２６の処理では、２番目に中心点Ｃｂに距離が近い分岐点Ｐｂ２により構成される３角形も作成されるが、分岐点Ｐｂ２と、分岐点Ｐｂ２に最も近い２点の分岐点は、分岐点Ｐｂ１とＰｂ５とされ、３角形Ｗｂ１と同じとなるので、その後、３番目に中心点Ｃｂに近い分岐点Ｐｂ３により構成される３角形が作成される。
【０１４１】
その後、処理はステップＳ１１５に戻り、ＣＰＵ５２は、ステップＳ１２７の処理により作成した３角形（いまの例の場合、Ｗｂ２）の面積を計算する。以下、同様の処理が繰り返され、いまの例の場合、３角形Ｗｂ２と登録テンプレートに登録されている図１３の３角形Ｗ４が対応しているので、ステップＳ１１７、ステップＳ１１９、およびステップＳ１２３の処理は、全て、ＹＥＳ（一致する）と判定される。
【０１４２】
その結果、ステップＳ１２４において、カウンタに１が加えられる。いまの例の場合、カウンタの値は２とされる。
【０１４３】
ステップＳ１２５において、ＣＰＵ５２は、カウンタの値が２であるか否かを判定する。いまの例の場合、カウンタの値は２である（３角形Ｗｂ１が３角形Ｗ１と一致し、３角形Ｗｂ２と３角形Ｗ４が一致するため）と判定される。カウンタの値が２ということは、指紋画像の分岐点により作成される異なる２つの３角形において、３角形の面積、辺の長さ、それぞれの分岐点と端点との間の位置が登録テンプレートと全て一致していることを示している。カウンタの値が２であると判定された場合、ステップＳ１２９に進み、ＣＰＵ５２は、認証できた（すなわち、登録した使用者といま照合している使用者が一致する）ことを表わす信号を出力し、処理を終了する。照合の結果は、本体部１１のランプ２２とランプ２３により点灯される。
【０１４４】
ステップＳ１１７において面積が一致しないと判定された場合、ステップＳ１１９において長さが一致しないと判定された場合、ステップＳ１２３において端点の位置が一致しないと判定された場合、または、ステップＳ１２５においてカウンタの値が２ではないと判定された場合（すなわち、１つの３角形について、３角形の面積、辺の長さ、およびそれぞれの分岐点と端点との間の位置のうち、少なくともいずれか１つが一致しないと判定された場合）、ステップＳ１２６に進み、次の３角形が作成できるか否かが判定される。次の３角形が作成できないことは、ステップＳ１０７の処理により検出された分岐点Ｐｂ１乃至Ｐｂ７を全て使用して、過去に作成した３角形と重複しない３角形を作成し終えたことを意味する。次の３角形が作成できないと判定された場合、ステップＳ１２８に進み、ＣＰＵ５２は、認証できなかった（すなわち、登録した使用者といま照合している使用者が一致しない）ことを表わす信号を出力し、処理を終了する。照合の結果は、本体部１１のランプ２２とランプ２３により点灯される。
【０１４５】
図１４乃至図１７の処理により、分岐点により求められる３角形の面積、３辺の長さ、３個の分岐点に最も近接するそれぞれの端点の位置により、指紋の照合を行なうことができる。また、取得した指紋画像の中心を求めて、中心に近い分岐点から３角形を順次生成することにより、一致する登録テンプレートを早く検索することができる。
【０１４６】
ユーザは、指を指紋読み取りセンサ２１上に置くとき、指の中心を指紋読み取り用センサ２１の中心に合わせようとする。そして、指の向きはその都度異なるので、中心から遠い位置の画像程、登録画像と異なる画像となる可能性が高くなる。従って、一致する画像であれば、中心から判定を進めていくことにより、一致するとの判定結果を早く得ることができる。
【０１４７】
また、異なる３角形の場合、辺の長さと端点の位置に較べて、面積が一致する可能性の方が低い。従って、面積を先に判定した方が、無駄な判定の回数が減り、迅速な判断ができる。
【０１４８】
２つの３角形において全て一致する場合（ステップＳ１２５においてＹＥＳと判定される場合）に、認証できたことにするのは（全ての３角形において一致する場合に、認証できたことにしないのは）、指紋読み取り用センサ２１に押圧され、取得される指紋画像に、最大約３ミリのずれが生じるためである（指を置く毎に変化し易いためである）。すなわち、指紋画像にずれが生じることにより、作成される３角形が一部異なるためである（例えば、図２１の例の場合、図１３の３角形Ｗ３に対応する３角形は作成されない）。
【０１４９】
例えば、図１４のステップＳ１０４の処理により得られた、前処理されたグレー画像が、図２２に示されるような画像である場合（勿論、同一の指から取得された指紋画像データとされる）、図９の登録画像（図６のステップＳ４の処理により取得された前処理されたグレー画像）と比較して、大幅に左下にずれている。
【０１５０】
図２２に示されるグレー画像は、２値化処理（ステップＳ１０５の処理）により、図２３に示されるように変換され、さらに、細線化処理（ステップＳ１０６の処理）により、図２４に示されるように変換される。そして、分岐点と端点の検出（ステップＳ１０７の処理）により、図２５に示されるようになる。図２５においては、図２１の場合と同様に分岐点をそれぞれＰｂ１乃至Ｐｂ７（図２５の例の場合は、分岐点は７個しか検出されない）、端点がそれぞれＱｂ１乃至Ｑｂ１０、中心点がＣｂとそれぞれ設定される。
【０１５１】
図１３と図２５を比較するに、図１３の分岐点Ｐ１は図２５の分岐点Ｐｂ３に対応しており、分岐点Ｐ２は分岐点Ｐｂ２に対応しており、分岐点Ｐ３は分岐点Ｐｂ１に対応しており、分岐点Ｐ４は分岐点Ｐｂ６に対応しており、分岐点Ｐ７は分岐点Ｐｂ５に対応している。すなわち、図１３と図２５では、取り込まれた画像の位置が異なるため、図１３において検出された分岐点Ｐ５，分岐点Ｐ６および分岐点Ｐ８は、図２５において検出されない。その代わり、図２５においては、図１３において検出されなかった分岐点である分岐点Ｐｂ４および分岐点Ｐｂ７が検出される。
【０１５２】
ＣＰＵ５２は、指紋画像の中心点Ｃｂを求めた後（ステップＳ１０９の処理の後）、または、予め設定されている中心点Ｃｂを読み出した後、中心点Ｃｂと分岐点Ｐｂ１乃至Ｐｂ７の距離を短いものの順にソートし（ステップＳ１１１）、さらに、中心点Ｃｂと端点Ｑｂ１乃至Ｑｂ１０の距離を短いものの順にソートし（ステップＳ１１３）、３角形を作成する（ステップＳ１１４の処理）。図２５の例の場合、ステップＳ１１４またはステップＳ１２７により、２個の３角形（３角形Ｗｂ１と３角形Ｗｂ２）が順次作成される。もし、順次、作成可能な全ての３角形が作成されるとしたら、図２５の例の場合、作成される３角形は、順番に、分岐点Ｐｂ１，分岐点Ｐｂ２、および分岐点Ｐｂ６の３個を結ぶ３角形Ｗｂ１、分岐点Ｐｂ２，分岐点Ｐｂ１、および分岐点Ｐｂ３の３個を結ぶ３角形Ｗｂ２、分岐点Ｐｂ４，分岐点Ｐｂ５、および分岐点Ｐｂ７の３個を結ぶ３角形Ｗｂ３、分岐点Ｐｂ６，分岐点Ｐｂ１、および分岐点Ｐｂ５の３個を結ぶＷｂ４、並びに、分岐点ｐｂ７，分岐点Ｐｂ５、および分岐点Ｐｂ６の３個を結ぶＷｂ５の５個の３角形が作成される（勿論、この５個の３角形と重複する３角形も作成されている）。すなわち、図２１の３角形Ｗｂ３と３角形Ｗｂ５に対応する３角形は、図１３に示される指紋画像では作成されない（すなわち、登録テンプレートにも登録されていないため、３角形Ｗｂ３とＷｂ５においては、一致しないと判定される）。
【０１５３】
そこで、図１４乃至２０に示されるように、全てではなく、そのうちの複数個としての２個の３角形が一致する場合に、認証できたと判定するような処理にすることにより、正確に照合することができる。逆に、その数を１個としてしまうと、第３者の指が誤認証される恐れが高くなる。
【０１５４】
登録された指紋画像が本人のものであるにもかかわらず、正しく照合されない確率をＦＲＲ（Ｆａｌｓｅ  Ｒｅｊｅｃｔｉｏｎ  Ｒａｔｅ：本人拒否率）といい、登録された指紋画像が任意の他人のものであっても、照合されてしまう確率をＦＡＲ（Ｆａｌｓｅ  Ａｃｃｅｐｔａｎｃｅ  Ｒａｔｅ；他人受け入れ率）という。ＦＡＲが高い指紋照合装置は、他人が本人に成りすますことが容易となり、セキュリティの質が低い指紋照合装置である。
【０１５５】
照合閾値を高くする（一致するとみなす誤差の範囲を大きくしたり、一致する３角形の数の基準値（２個）をもっと大きくする）ことにより、ＦＡＲを下げることが可能となる。しかしながら、その場合、照合の可否は、照合時の環境（例えば、取得した指紋画像に混入されてしまうノイズなど）の変化の影響などを強く受けてしまい、本人であるのにもかかわらず照合されない場合が増えてしまう（すなわち、ＦＲＲが高くなる）ため、ユーザの利便性が失われてしまう。そこで、照合閾値は、ＦＲＲとＦＡＲの両方のバランスを図る値に設定する必要がある。
【０１５６】
以上の処理により、指紋画像の分岐点と端点を検出し、指紋画像の中心点からの距離に基づいて、分岐点（または端点）から近接する３個を結ぶ３角形を作成し、作成した３角形の面積、３辺の長さ、および３つの分岐点にそれぞれ最も近い端点との位置（距離または方向）を登録することにより指紋の照合を行なうようにしたので、保存する情報量（登録テンプレートサイズ）を従来より大幅に小さくすることができ、もって、メモリの容量を減らすことが可能となる。
【０１５７】
また、簡単な登録データ（３角形の面積、３辺の長さ、および３つの分岐点にそれぞれ最も近い端点との位置）を用いるため、照合画像の位置や回転補正をする必要もなく、簡単な処理により、容易に照合を行なうことができ、もって処理速度を速くすることができる。
【０１５８】
さらに、指紋照合の精度を向上させることができる。
【０１５９】
また、中心点との距離に基づいて、分岐点と端点をソートし、そのソートした結果から順番に、分岐点または端点を検索するようにしたので、最も近い他の分岐点や端点を迅速に特定することができる。
【０１６０】
なお、以上の例においては、３個の分岐点の最も近いそれぞれの端点の距離と方向を位置として登録し、指紋の照合をするようにしたが、距離と方向の少なくとも一方でよい。
【０１６１】
なお、指紋画像の分岐点および端点の位置は、取得された指紋画像の左上からソートするようにしてもよいが、指紋読み取り用センサ２１に押圧され、取得される指紋画像は、最大約３ミリのずれが生じる（指を置く毎に変化し易い）。このため、指紋画像の中心点を求め、中心点に対する分岐点と端点の位置を求めることにより一致する登録テンプレートを検索し易くすることが可能となる。
【０１６２】
なお、以上の例においては、３つの分岐点により３角形を作成するようにしたが、端点により３角形を作成するようにしてもよい。この場合、端点により３角形が作成され、３角形を構成する辺の距離、および３角形を構成する３つの端点にそれぞれ最も近い分岐点との間の位置が求められる。
【０１６３】
なお、以上の例においては、３つの分岐点により３角形を作成し、記憶するようにしたが、これに限らず、４角形以上の多角形とすることも可能である。ただし、３角形にする場合の方が、ＦＡＲとＦＲＲを低くすることができ、最も正確、かつ迅速な判定が可能となる。
【０１６４】
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【０１６５】
この記録媒体は、図３に示すように、コンピュータとは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク７１（フレキシブルディスクを含む）、光ディスク７２（ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）を含む）、光磁気ディスク７３（ＭＤ（Ｍｉｎｉ−Ｄｉｓｃ）（商標）を含む）、若しくは半導体メモリ７４などよりなるパッケージメディアにより構成されるだけでなく、コンピュータに予め組み込まれた状態でユーザに提供される、プログラムが記録されているプログラム用ＲＡＭ／ＲＯＭ５３や、ハードディスクなどで構成される。
【０１６６】
なお、上述した一連の処理を実行させるプログラムは、必要に応じてルータ、モデムなどのインタフェースを介して、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の通信媒体を介してコンピュータにインストールされるようにしてもよい。
【０１６７】
また、本明細書において、記録媒体に格納されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１６８】
【発明の効果】
以上の如く、第１の本発明によれば、指紋照合に使用される情報量を小さくすることができる。記憶装置を小型化し、低コスト化することができる。従って、小型の装置への適用が可能となる。
【０１６９】
第２の本発明によれば、指紋照合を行なうことができる。特に、小さい情報量で指紋照合することができる。また、指紋照合の処理速度を速くすることができる。さらに、指紋照合の精度を向上させることができる。
【図面の簡単な説明】
【図１】本発明を適用した指紋照合装置の一実施の形態の外観の構成を示す斜視図である。
【図２】指紋読み取りセンサが、指紋が読み取られる指で押圧されている状態を説明する平面図である。
【図３】指紋照合装置の構成を示すブロック図である。
【図４】指紋読み取りセンサの原理的な構成を示す断面図である。
【図５】指紋読み取りセンサの内部回路の構成を示す回路図である。
【図６】図３の指紋照合装置における指紋登録処理を説明するフローチャートである。
【図７】図３の指紋照合装置における指紋登録処理を説明するフローチャートである。
【図８】図６のステップＳ３における画像例を示す図である。
【図９】図６のステップＳ４における画像例を示す図である。
【図１０】図６のステップＳ５における画像例を示す図である。
【図１１】図６のステップＳ６における画像例を示す図である。
【図１２】図６のステップＳ７における画像例を示す図である。
【図１３】図７のステップＳ１４における画像例を示す図である。
【図１４】図３の指紋照合装置における指紋照合処理を説明するフローチャートである。
【図１５】図３の指紋照合装置における指紋照合処理を説明するフローチャートである。
【図１６】図３の指紋照合装置における指紋照合処理を説明するフローチャートである。
【図１７】図３の指紋照合装置における指紋照合処理を説明するフローチャートである。
【図１８】図１４のステップＳ１０４における画像例を示す図である。
【図１９】図１４のステップＳ１０５における画像例を示す図である。
【図２０】図１４のステップＳ１０６における画像例を示す図である。
【図２１】図１４のステップＳ１０７における画像例を示す図である。
【図２２】図１４のステップＳ１０４における他の画像例を示す図である。
【図２３】図１４のステップＳ１０５における他の画像例を示す図である。
【図２４】図１４のステップＳ１０６における他の画像例を示す図である。
【図２５】図１４のステップＳ１０７における他の画像例を示す図である。
【符号の説明】
１  指紋照合装置，  １１  本体部，  ２１  指紋読み取りセンサ，  ５１  指紋読み取り用ＬＳＩ，  ５２  ＣＰＵ，  ５３  プログラム用ＲＡＭ／ＲＯＭ，  ５４  フラッシュメモリ，  ７１  磁気ディスク，  ７２  光ディスク，  ７３  光磁気ディスク，  ７４  半導体メモリ
【図１】
2004213395.tif 000003
【図２】
2004213395.tif 000004
【図３】
2004213395.tif 000005
【図４】
2004213395.tif 000006
【図５】
2004213395.tif 000007
【図６】
2004213395.tif 000008
【図７】
2004213395.tif 000009
【図８】
2004213395.tif 000010
【図９】
2004213395.tif 000011
【図１０】
2004213395.tif 000012
【図１１】
2004213395.tif 000013
【図１２】
2004213395.tif 000014
【図１３】
2004213395.tif 000015
【図１４】
2004213395.tif 000016
【図１５】
2004213395.tif 000017
【図１６】
2004213395.tif 000018
【図１７】
2004213395.tif 000019
【図１８】
2004213395.tif 000020
【図１９】
2004213395.tif 000021
【図２０】
2004213395.tif 000022
【図２１】
2004213395.tif 000023
【図２２】
2004213395.tif 000024
【図２３】
2004213395.tif 000025
【図２４】
2004213395.tif 000026
【図２５】
2004213395.tif 000027