(57)【要約】【課題】  高速に照合処理する。【解決手段】  画像ＡとＢを画像入力部１０１から入力すると、部分画像特徴値計算部１０４５は両画像の各部分画像の特徴値を求める。最大一致度位置探索部１０５は、画像Ａ内の各部分画像について、画像Ｂ内の最大一致度となる部分画像の位置を探索する。この探索範囲は特徴値に応じて選択された部分画像に絞られる。移動ベクトルに基づく類似度計算部１０６は各部分画像毎の、画像Ａ内での該部分画像の位置を測るための基準位置と最大一致度位置探索部１０５により探索された該部分画像に対応の最大一致度位置との位置関係を示す移動ベクトルのうち、該移動ベクトルの方向や長さが所定レンジに該当する部分画像に関する情報から画像ＡとＢの類似度を計算する。照合対象の画像は特徴値に基づいて分類された同一カテゴリに属するものであってもよい。【選択図】        図１
2005149455.tif 000002
【特許請求の範囲】
【請求項１】
画像内に設定された複数の部分領域の画像のそれぞれについて、部分領域の画像の模様に応じた値を計算して部分画像特徴値として出力する部分画像特徴値計算手段と、
２つの画像のうちの一方の画像内に設定された複数の部分領域の画像のそれぞれに対応して、他方の画像において最大の一致度となる部分領域の画像の位置である最大一致度位置を探索する最大一致度位置探索手段と、
前記複数部分領域毎の、前記一方の画像内での該部分領域の位置を測るための基準位置と前記最大一致度位置探索手段により探索された該部分領域に対応の前記最大一致度位置との位置関係を示す位置関係量のうち、該位置関係量が所定レンジに該当する前記部分領域に関する情報から２つの画像の類似度を計算して画像類似度として出力する類似度計算手段と、
与えられる前記画像類似度に基づいて前記２つの画像が一致するか否か判定する判定手段とを備え、
前記最大一致度位置探索手段により探索する他方の画像の範囲は、一方の画像内に設定された部分領域の画像の前記部分画像特徴値に応じて他方の画像内に設定された複数の部分領域の中から選択して決定されることを特徴とする、画像照合装置。
【請求項２】
前記一方の画像について前記部分画像特徴値計算手段により出力される部分画像特徴値に基づいて、該一方の画像が属するカテゴリを判定するカテゴリ判定手段をさらに備え、
前記他方の画像は、前記カテゴリ判定手段により判定された前記一方の画像のカテゴリに基づいて選択されることを特徴とする、請求項１に記載の画像照合装置。
【請求項３】
画像内に設定された複数の部分領域の画像のそれぞれについて、部分領域の画像の模様に応じた値を計算して部分画像特徴値として出力する部分画像特徴値計算手段と、
２つの画像のうちの一方の画像について前記部分画像特徴値計算手段により出力される部分画像特徴値に基づいて、該一方の画像が属するカテゴリを判定するカテゴリ判定手段と、
２つの画像のうちの一方の画像内に設定された複数の部分領域の画像のそれぞれに対応して、前記カテゴリ判定手段により判定された前記一方の画像のカテゴリに基づいて選択された他方の画像において最大の一致度となる部分領域の画像の位置である最大一致度位置を探索する最大一致度位置探索手段と、
前記複数部分領域毎の、前記一方の画像内での該部分領域の位置を測るための基準位置と前記最大一致度位置探索手段により探索された該部分領域に対応の前記最大一致度位置との位置関係を示す位置関係量のうち、該位置関係量が所定レンジに該当する前記部分領域に関する情報から２つの画像の類似度を計算して画像類似度として出力する類似度計算手段と、
与えられる前記画像類似度に基づいて前記２つの画像が一致するか否か判定する判定手段とを備え、
前記最大一致度位置探索手段により探索する他方の画像の範囲は、一方の画像内に設定された部分領域の画像の前記部分画像特徴値に応じて他方の画像内に設定された複数の部分領域の中から選択して決定されることを特徴とする、画像照合装置。
【請求項４】
前記他方の画像は、前記一方の画像と同一のカテゴリに属することを特徴とする、請求項２または３に記載の画像照合装置。
【請求項５】
前記他方の画像が複数個準備される場合には、前記複数個の他方の画像のうち、前記一方の画像と同一のカテゴリに属するものが優先して選択されることを特徴とする、請求項２または３に記載の画像照合装置。
【請求項６】
前記部分画像特徴値計算手段は、
前記部分領域の画像毎に、水平方向の画素が連続する最大長と垂直方向の画素が連続する最大長を各々求め、その最大長を示す値に基づいて、前記部分画像特徴値を出力することを特徴とする、請求項１から５のいずれか１項に記載の画像照合装置。
【請求項７】
前記部分画像特徴値計算手段は、
前記部分領域の画像毎に、水平方向および垂直方向を代表する画素列をそれぞれ抽出し、抽出されたそれぞれの画素列における画素値の変化の回数に基づいて、部分画像特徴値を出力することを特徴とする、請求項１から５のいずれか１項に記載の画像照合装置。
【請求項８】
前記部分画像特徴値計算手段は、
前記部分領域の画像毎に、左右に所定数の画素ずつずらして重ねた画像と、上下に所定数の画素ずつずらして重ねた画像を各々求め、さらに、その左右に所定数の画素ずつずらして重ねた画像と該部分領域の画像との画素値の差分と、その上下に所定数の画素ずつずらして重ねた画像と該部分領域の画像との画素値の差分とを各々求め、求められた差分に基づいて、部分画像特徴値を出力することを特徴とする、請求項１から５のいずれか１項に記載の画像照合装置。
【請求項９】
前記部分画像特徴値は３種類の値のいずれかであることを特徴とする、請求項１から８のいずれかに記載の画像照合装置。
【請求項１０】
前記３種類の値それぞれは、前記部分領域の画像の模様が縦方向に従っていることを示す、横方向に従っていることを示す、およびその他であることを示すのいずれかであることを特徴とする、請求項９に記載の画像照合装置。
【請求項１１】
前記最大一致度位置探索手段は、
前記一方の画像内に設定された部分領域の画像の前記部分画像特徴値の種類と一致する前記部分画像特徴値である前記他方の画像内に設定された部分領域を探索範囲とすることを特徴とする、請求項９または１０に記載の画像照合装置。
【請求項１２】
前記最大一致度位置探索手段は、
一方の画像内に設定された部分領域の画像の前記部分画像特徴値が前記模様が前記縦方向および前記横方向のうちの一方向に従っていることを示すとき、他方の画像内に設定された部分領域のうち前記部分画像特徴値が前記模様が前記一方向に従っていることを示す画像の部分領域および前記その他であることを示す画像の部分領域を探索範囲とすることを特徴とする、請求項１０に記載の画像照合装置。
【請求項１３】
前記部分画像特徴値が前記その他を示す前記部分領域は前記最大一致度位置検索手段による探索範囲から除かれることを特徴とする、請求項１０に記載の画像照合装置。
【請求項１４】
画像内にそれぞれ設定された複数の部分領域の画像のそれぞれについて、部分領域の画像の模様に応じた値を計算して部分画像特徴値として出力する部分画像特徴値計算ステップと、
２つの画像のうちの一方の画像内に設定された複数の部分領域の画像のそれぞれに対応して、他方の画像において最大の一致度となる部分領域の画像の位置である最大一致度位置を探索する最大一致度位置探索ステップと、
前記複数部分領域毎の、前記一方の画像内での該部分領域の位置を測るための基準位置と前記最大一致度位置探索ステップにより探索された該部分領域に対応の前記最大一致度位置との位置関係を示す位置関係量のうち、該位置関係量が所定レンジに該当する前記部分領域に関する情報から２つの画像の類似度を計算して画像類似度として出力する類似度計算ステップと、
与えられる前記画像類似度に基づいて前記２つの画像が一致するか否か判定する判定ステップとを備え、
前記最大一致度位置探索ステップにより探索する他方の画像の範囲は、一方の画像内に設定された部分領域の画像の前記部分画像特徴値に応じて他方の画像内に設定された複数の部分領域の中から選択して決定されることを特徴とする、画像照合方法。
【請求項１５】
請求項１４に記載の前記画像照合方法をコンピュータに実行させるための画像照合プログラム。
【請求項１６】
請求項１５に記載の前記画像照合をプログラムを記録したコンピュータ読取可能な記録媒体。
【請求項１７】
画像内に設定された複数の部分領域の画像のそれぞれについて、部分領域の画像の模様に応じた値を計算して部分画像特徴値として出力する部分画像特徴値計算ステップと、
２つの画像のうちの一方の画像について前記部分画像特徴値計算ステップにより出力される部分画像特徴値に基づいて、該一方の画像が属するカテゴリを判定するカテゴリ判定ステップと、
２つの画像のうちの一方の画像内に設定された複数の部分領域の画像のそれぞれに対応して、前記カテゴリ判定ステップにより判定された前記一方の画像のカテゴリに基づいて選択された他方の画像において最大の一致度となる部分領域の画像の位置である最大一致度位置を探索する最大一致度位置探索ステップと、
前記複数部分領域毎の、前記一方の画像内での該部分領域の位置を測るための基準位置と前記最大一致度位置探索ステップにより探索された該部分領域に対応の前記最大一致度位置との位置関係を示す位置関係量のうち、該位置関係量が所定レンジに該当する前記部分領域に関する情報から２つの画像の類似度を計算して画像類似度として出力する類似度計算ステップと、
与えられる前記画像類似度に基づいて前記２つの画像が一致するか否か判定する判定ステップとを備え、
前記最大一致度位置探索ステップにより探索する他方の画像の範囲は、一方の画像内に設定された部分領域の画像の前記部分画像特徴値に応じて他方の画像内に設定された複数の部分領域の中から選択して決定されることを特徴とする、画像照合方法。
【請求項１８】
請求項１７に記載の前記画像照合方法をコンピュータに実行させるための画像照合プログラム。
【請求項１９】
請求項１８に記載の前記画像照合をプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像照合装置、画像照合方法、画像照合プログラムおよび画像照合プログラムを記録したコンピュータ読取り可能な記録媒体に関し、特に、２つの画像を照合する画像照合装置、画像照合方法、画像照合プログラムおよび画像照合プログラムを記録したコンピュータ読取り可能な記録媒体に関する。
【背景技術】
【０００２】
従来の指紋画像に関する照合方法は、大きく分けて画像特徴量マッチング方式と画像間マッチング方式とに大別できる。前者の画像特徴量マッチングは、「これで分かったバイオメトリクス」（日本自動認識システム協会編、オーム社：Ｐ４２〜Ｐ４４）では、画像を直接比較するのではなく、画像内に含まれる特徴量を抽出した後、抽出した画像特徴量同士を比較する方法である。該方法では指紋画像における照合においては、図２９（Ａ）と（Ｂ）のようなマニューシャ（指紋隆線の端点と分岐点であり、指紋画像内に数個から数十個存在する）が画像特徴量となる。該方法では、図３０のようにそれぞれの画像から画像処理により抽出したマニューシャの位置や種類や隆線などの情報を基に画像間で相対的な位置や方向が一致するマニューシャ数を類似度とし、マニューシャ間を横切る隆線数などの一致・不一致により類似度を増減し、その類似度と予め定めた閾値と比較し照合・識別を行なう。
【０００３】
後者の画像間マッチングは、図３１のように照合する画像αとβ間で全領域もしくは部分領域に対応の部分画像α１とβ１を抽出し、部分画像α１とβ１間の一致度を、差分値の総和、相関係数、位相相関法や郡遅延ベクトル法などにより画像αとβ間の類似度として計算し、算出された類似度と予め定めた閾値と比較し照合・識別を行なう。
【０００４】
画像間マッチングの手法を利用した発明としては、特許文献１や２などが挙げられる。特許文献１では、画像間マッチングを行なったのち部分領域をさらに４分割し、それぞれの分割領域の周辺領域での一致度最大となる位置を求め、平均一致度を改めて類似度とする。これにより、指紋画像内に指紋採取の時に生じた指紋の歪みに対処できる。特許文献２では、一方の指紋画像中の特徴を含む複数の部分領域の位置関係の拘束をある程度保持して他方の指紋画像の各部分領域との一致度の総和を計算して、類似度として算出する。
【０００５】
一般的には画像間マッチング方式はノイズや指の状態（乾燥・汗・傷）などに対処しやすく、画像特徴量マッチング方式は、画像間マッチングに比べ比較するデータ量が少ないため画像間マッチングに比べ処理の高速化可能である。
【特許文献１】特許第２５４９１０７号公報
【特許文献２】特開昭６３−７８２８６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
現在、指紋認証をはじめとするバイオメトリクス技術を適用した個人認証技術の民生機器への普及が始まりつつあり、これら普及段階においては、個人認証処理時間を少しでも短時間化することが求められている。更に、このような認証機能を個人が携帯する携帯電話やＰＤＡ(Personal Digital Assistants)へ搭載する場合では、搭載されている電池容量が潤沢でないことから認証時間に加え、認証処理時に使用される消費電力の低減も求められる。
【０００７】
それゆえに、この発明の目的は、高速な照合処理を可能とする画像照合装置、画像照合方法、画像照合プログラムおよび画像照合プログラムを記録したコンピュータ読取り可能な記録媒体を提供することである。
【課題を解決するための手段】
【０００８】
この発明のある局面に従う画像照合装置は、画像内に設定された複数の部分領域の画像のそれぞれについて、部分領域の画像の模様に応じた値を計算して部分画像特徴値として出力する部分画像特徴値計算手段と、
２つの画像のうちの一方の画像内に設定された複数の部分領域の画像のそれぞれに対応して、他方の画像において最大の一致度となる部分領域の画像の位置である最大一致度位置を探索する最大一致度位置探索手段と、
複数部分領域毎の、一方の画像内での該部分領域の位置を測るための基準位置と最大一致度位置探索手段により探索された該部分領域に対応の最大一致度位置との位置関係を示す位置関係量のうち、該位置関係量が所定レンジに該当する部分領域に関する情報から２つの画像の類似度を計算して画像類似度として出力する類似度計算手段と、
与えられる画像類似度に基づいて２つの画像が一致するか否か判定する判定手段とを備え、
最大一致度位置探索手段により探索する他方の画像の範囲は、一方の画像内に設定された部分領域の画像の前記画像特徴値に応じて他方の画像内に設定された複数の部分領域の中から選択して決定される。
【０００９】
したがって、部分画像特徴値に応じて探索範囲を限定的に絞ったうえで（探索範囲を削減してから）、一方の画像中の複数の部分領域の他方の画像内で最も一致度の高い位置を探索できる。そして探索結果、得られる部分領域の位置関係量のうち、該位置関係量が所定レンジに該当する部分領域に関する情報から２つの画像の類似度が計算される。
【００１０】
それゆえに、画像照合のために探索される範囲は予め限定されたものとなるから、照合時間が短く、装置の消費電力の低減も可能となる。
【００１１】
好ましくは、上述の画像照合装置は、一方の画像について部分画像特徴値計算手段により出力される部分画像特徴値に基づいて、該一方の画像が属するカテゴリを判定するカテゴリ判定手段をさらに備え、他方の画像は、カテゴリ判定手段により判定された一方の画像のカテゴリに基づいて選択される。
【００１２】
したがって、カテゴリ判定手段により判定された一方の画像が属するカテゴリに基づいて、照合の対象となる他方の画像を選択することができる。それゆえに、他方の画像が多数あったとしても、照合対象となる他方の画像を一方の画像が属するカテゴリに基づき限定できるから、照合処理に要する時間を短縮できる。また、装置の消費電力も低減できる。
【００１３】
この発明の他の局面に従う画像照合装置は、画像内に設定された複数の部分領域の画像のそれぞれについて、部分領域の画像の模様に応じた値を計算して部分画像特徴値として出力する部分画像特徴値計算手段と、
２つの画像のうちの一方の画像について部分画像特徴値計算手段により出力される部分画像特徴値に基づいて、該一方の画像が属するカテゴリを判定するカテゴリ判定手段と、
２つの画像のうちの一方の画像内に設定された複数の部分領域の画像のそれぞれに対応して、カテゴリ判定手段により判定された一方の画像のカテゴリに基づいて選択された他方の画像において最大の一致度となる部分領域の画像の位置である最大一致度位置を探索する最大一致度位置探索手段と、
複数部分領域毎の、一方の画像内での該部分領域の位置を測るための基準位置と最大一致度位置探索手段により探索された該部分領域に対応の前記最大一致度位置との位置関係を示す位置関係量のうち、該位置関係量が所定レンジに該当する部分領域に関する情報から２つの画像の類似度を計算して画像類似度として出力する類似度計算手段と、
与えられる画像類似度に基づいて２つの画像が一致するか否か判定する判定手段とを備え、
最大一致度位置探索手段により探索する他方の画像の範囲は、一方の画像内に設定された部分領域の画像の部分画像特徴値に応じて他方の画像内に設定された複数の部分領域の中から選択して決定される。
【００１４】
したがって、カテゴリ判定手段により判定されたカテゴリに基づいて選択された照合対象の画像について、部分画像特徴値に応じて探索範囲を限定的に絞ったうえで（探索範囲を削減してから）、一方の画像中の複数の部分領域の他方の画像内で最も一致度の高い位置を探索できる。そして探索結果、得られる部分領域の位置関係量のうち、該位置関係量が所定レンジに該当する部分領域に関する情報から２つの画像の類似度が計算される。
【００１５】
それゆえに、照合対象画像を選択し、選択した画像における画像照合のための探索範囲を予め限定しているから、照合処理に要する時間をより短くでき、装置の消費電力のさらなる低減も可能となる。
【００１６】
好ましくは、他方の画像は一方の画像と同一のカテゴリに属する。したがって、同一カテゴリに属する画像同士が照合されることになるので、照合処理に要する時間をより短くでき、また装置の消費電力のさらなる低減も可能となる。
【００１７】
好ましくは、他方の画像が複数個準備される場合には、複数個の他方の画像のうち、一方の画像と同一のカテゴリに属するものが優先して選択される。したがって、同一カテゴリに属する画像同士が優先的に照合されることになるので、照合処理に要する時間をより短くでき、また装置の消費電力のさらなる低減も可能となる。
【００１８】
好ましくは、カテゴリ判定手段は、部分画像特徴値計算手段により計算された、画像の複数の特定位置の部分画像の部分画像特徴値の組合わせに基づいて該画像のカテゴリを判定するようにしてよい。
【００１９】
好ましくは、複数個の他方の画像は予め異なるカテゴリに分類されて、最大一致度位置探索手段は、一方の画像についてカテゴリ判定手段により判定されたカテゴリに基づいて選択されたカテゴリに属する他方の画像において最大一致度位置を探索する。
【００２０】
ここで、位置関係量は好ましくは移動ベクトルである。この場合には、移動ベクトルが所定レンジに該当する、たとえば同一移動ベクトルを持つと判断される部分領域に関する情報を用いた類似度計算がなされる。
【００２１】
ここで、２つの画像は、指紋画像であってよい。この場合には、指紋画像は画像中の任意の部分領域がその指紋を特徴付ける隆線数・方向・幅やその変動などの情報を含んでおり、同一指紋から採取された別の指紋画像中でも部分領域が多くの場合同じ位置にマッチングするという特性が利用されることになる。
【００２２】
好ましくは、部分画像特徴値計算手段は、部分領域の画像毎に、水平方向の画素が連続する最大長と垂直方向の画素が連続する最大長を各々求め、その最大長を示す値に基づいて、部分画像特徴値を出力する。
【００２３】
したがって、部分画像特徴値を、水平方向の画素が連続する最大長と垂直方向の画素が連続する最大長のうちの最大長を求めるという簡単な手順で算出できる。
【００２４】
好ましくは、部分画像特徴値計算手段は、部分領域の画像毎に、水平方向および垂直方向を代表する画素列をそれぞれ抽出し、抽出されたそれぞれの画素列における画素値の変化の回数に基づいて、部分画像特徴値を出力する。
【００２５】
したがって、部分画像特徴値を、水平方向および垂直方向を代表する画素列それぞれの
画素値の変化の回数を求めることで簡単に算出できる。
【００２６】
好ましくは、部分画像特徴値計算手段は、部分領域の画像毎に、左右に所定数の画素ずつずらして重ねた画像と、上下に所定数の画素ずつずらして重ねた画像を各々求め、さらに、その左右に所定数の画素ずつずらして重ねた画像と該部分領域の画像との画素値の差分と、その上下に所定数の画素ずつずらして重ねた画像と該部分領域の画像との画素値の差分とを各々求め、求められた差分に基づいて、部分画像特徴値を出力する。
【００２７】
したがって、部分画像特徴値を、部分領域の元の画像と上下にずらした画像とを重ねて得られる画素値の差分、同様に部分領域の元の画像と左右にずらした画像とを重ねて得られる画素値の差分を求めることで簡単に算出できる。
【００２８】
好ましくは、部分画像特徴値は３種類の値のいずれかである。したがって、部分画像特徴値の種類は３種類のいずれかに限定されるから、これらを用いた照合処理が複雑になるのを回避できる。
【００２９】
好ましくは、３種類の値それぞれは、部分領域の画像の模様が縦方向に従っていることを示す、横方向に従っていることを示す、およびその他であることを示すのいずれかである。
【００３０】
なお、部分画像特徴値は好ましくは３種類であるが、これに限定されるものではなく、４種類など他の種類数であってもよい。
【００３１】
したがって、部分画像特徴値により、対応する部分領域の画像の模様が縦方向に従うものであるのか、横方向に従うものであるか、どちらとも特定できないものかを指示することができる。
【００３２】
好ましくは、縦方向に従う模様は縦縞であり、横方向に従う模様は横縞である。したがって、例えば画像が指紋である場合には指紋の縦縞または横縞を部分画像特徴値で示すことができる。
【００３３】
好ましくは、最大一致度位置探索手段は、一方の画像内に設定された部分領域の画像の部分画像特徴値の種類と一致する部分画像特徴値である他方の画像内に設定された部分領域を探索範囲とする。
【００３４】
したがって、部分画像特徴値が一致する画像の部分領域を探索範囲として特定できる。
【００３５】
好ましくは、最大一致度位置探索手段は、一方の画像内に設定された部分領域の画像の部分画像特徴値が模様が縦方向および横方向のうちの一方向に従っていることを示すとき、他方の画像内に設定された部分領域のうち画像特徴値が模様が一方向に従っていることを示す画像の部分領域およびその他であることを示す画像の部分領域を探索範囲とする。
【００３６】
したがって、部分画像特徴値が一致する画像の部分領域とその他を示す部分領域とを探索範囲として特定することができる。
【００３７】
好ましくは、部分画像特徴値がその他を示す部分領域は最大一致度位置検索手段による探索範囲から除かれる。
【００３８】
したがって、縦方向および横方向のいずれにも特定できない曖昧な方向に従う模様の画像領域は探索範囲から除くようにしているから、曖昧な部分画像特徴値が用いられることによる照合精度の低下を防止できる。
【００３９】
この発明のさらに他の局面に従う画像照合方法は、画像内に設定された複数の部分領域の画像のそれぞれについて、部分領域の画像の模様に応じた値を計算して部分画像特徴値として出力する部分画像特徴値計算ステップと、
２つの画像のうちの一方の画像内に設定された複数の部分領域の画像のそれぞれに対応して、他方の画像において最大の一致度となる部分領域の画像の位置である最大一致度位置を探索する最大一致度位置探索ステップと、
複数部分領域毎の、一方の画像内での該部分領域の位置を測るための基準位置と最大一致度位置探索ステップにより探索された該部分領域に対応の前記最大一致度位置との位置関係を示す位置関係量のうち、該位置関係量が所定レンジに該当する部分領域に関する情報から２つの画像の類似度を計算して画像類似度として出力する類似度計算ステップと、
与えられる前記画像類似度に基づいて前記２つの画像が一致するか否か判定する判定ステップとを備え、
最大一致度位置探索ステップにより探索する他方の画像の範囲は、一方の画像内に設定された部分領域の画像の画像特徴値に応じて他方の画像内に設定された複数の部分領域の中から選択して決定される。
【００４０】
したがって、部分画像特徴値に応じて探索範囲を限定的に絞ったうえで（探索範囲を削減してから）、一方の画像中の複数の部分領域の他方の画像内で最も一致度の高い位置を探索できる。そして探索結果、得られる部分領域の位置関係量のうち、該位置関係量が所定レンジに該当する部分領域に関する情報から２つの画像の類似度が計算される。
【００４１】
それゆえに、画像照合のために探索される範囲は予め限定されたものとなるから、照合時間が短く、該方法を装置で実行する場合には装置の消費電力の低減も可能となる。
【００４２】
この発明のさらに他の局面に従う画像照合方法は、画像内に設定された複数の部分領域の画像のそれぞれについて、部分領域の画像の模様に応じた値を計算して部分画像特徴値として出力する部分画像特徴値計算ステップと、
２つの画像のうちの一方の画像について部分画像特徴値計算ステップにより出力される部分画像特徴値に基づいて、該一方の画像が属するカテゴリを判定するカテゴリ判定ステップと、
２つの画像のうちの一方の画像内に設定された複数の部分領域の画像のそれぞれに対応して、カテゴリ判定ステップにより判定された一方の画像のカテゴリに基づいて選択された他方の画像において最大の一致度となる部分領域の画像の位置である最大一致度位置を探索する最大一致度位置探索ステップと、
複数部分領域毎の、一方の画像内での該部分領域の位置を測るための基準位置と最大一致度位置探索ステップにより探索された該部分領域に対応の前記最大一致度位置との位置関係を示す位置関係量のうち、該位置関係量が所定レンジに該当する前記部分領域に関する情報から２つの画像の類似度を計算して画像類似度として出力する類似度計算ステップと、
与えられる画像類似度に基づいて２つの画像が一致するか否か判定する判定ステップとを備え、
最大一致度位置探索ステップにより探索する他方の画像の範囲は、一方の画像内に設定された部分領域の画像の部分画像特徴値に応じて他方の画像内に設定された複数の部分領域の中から選択して決定される。
【００４３】
したがって、カテゴリ判定ステップにより判定されたカテゴリに基づいて選択された照合対象の画像について、部分画像特徴値に応じて探索範囲を限定的に絞ったうえで（探索範囲を削減してから）、一方の画像中の複数の部分領域の他方の画像内で最も一致度の高い位置を探索できる。そして探索結果、得られる部分領域の位置関係量のうち、該位置関係量が所定レンジに該当する部分領域に関する情報から２つの画像の類似度が計算される。
【００４４】
それゆえに、照合対象画像を選択し、選択した画像における画像照合のための探索範囲を限定しているから、照合処理に要する時間がより短く、装置の消費電力のさらなる低減も可能となる。
【００４５】
この発明のさらに他の局面に従うと、上述の画像照合方法をコンピュータに実行させるための画像照合プログラムが提供される。
【００４６】
この発明のさらに他の局面に従うと、上述の画像照合プログラムを記録したコンピュータ読取可能な記録媒体が提供される。
【発明を実施するための最良の形態】
【００４７】
以下、本発明の各実施の形態について図面を参照しながら説明する。ここでは、２つの画像データを照合する。照合の対象となる画像データとして指紋画像データを例示しているが、これに限定されず、個体（個人）毎に似ているが一致することはない生体の他の特徴による画像データであっても、あるいは、線状模様の画像データであってもよい。
【００４８】
（実施の形態１）
図１は実施の形態１に係る画像照合装置１のブロック図である。図２は各実施の形態に係る画像照合装置が搭載されるコンピュータの構成図である。図２を参照してコンピュータは、画像入力部１０１、ＣＲＴ（陰極線管）や液晶などからなるディスプレイ６１０、該コンピュータ自体を集中的に管理し制御するためのＣＰＵ（中央処理装置の略）６２２、ＲＯＭ（Read Only Memory）またはＲＡＭ（ランダムアクセスメモリの略）を含んで構成されるメモリ６２４、固定ディスク６２６、ＦＤ（フレキシブルディスク）６３２が着脱自在に装着されて、装着されたＦＤ６３２をアクセスするＦＤ駆動装置６３０、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）６４２が着脱自在に装着されて、装着されたＣＤ−ＲＯＭ６４２をアクセスするＣＤ−ＲＯＭ駆動装置６４０、通信ネットワーク３００と、該コンピュータとを通信接続するための通信インターフェィス６８０、プリンタ６９０およびキーボード６５０およびマウス６６０を有する入力部７００を含む。これらの各部はバスを介して通信接続される。
【００４９】
コンピュータには、カセット形式の磁気テープが着脱自在に装着されて磁気テープをアクセスする磁気テープ装置が設けられてもよい。
【００５０】
図１を参照して画像照合装置は、画像入力部１０１、図２のメモリ６２４または固定ディスク６２６に対応のメモリ１０２、バス１０３、照合処理部１１を備える。メモリ１０２は参照用メモリ１０２１、計算用メモリ１０２２、取込画像用メモリ１０２３、参照用部分画像特徴値計算結果メモリ１０２４、および取込画像用部分画像特徴値計算結果メモリ１０２５を含む。照合処理部１１は画像補正部１０４、部分画像特徴値計算部１０４５、最大一致度位置探索部１０５、移動ベクトルに基づく類似度計算部（以下、類似度計算部と呼ぶ）１０６、照合判定部１０７および制御部１０８を含む。照合処理部１１の各部は対応のプログラムが実行されることによりその機能が実現される。
【００５１】
画像入力部１０１は指紋センサを含み、該指紋センサにより読込まれた指紋に対応の指紋画像データを出力する。指紋センサには光学式、圧力式、静電容量方式などのいずれを適用してもよい。メモリ１０２には画像データや各種の計算結果などが格納され、参照用メモリ１０２１にはテンプレート用指紋画像の複数の部分領域が格納され、計算用メモリ１０２２には各種の計算結果などが格納され、取込画像用メモリ１０２３には該画像入力部１０１から出力された指紋画像データが格納され、参照用部分画像特徴値計算結果メモリ１０２４ならびに取込画像用部分画像特徴値計算結果メモリ１０２５には後述の部分画像特徴値計算部１０４５での計算結果が格納されている。バス１０３は各部間の制御信号やデータ信号を転送するために用いられる。
【００５２】
画像補正部１０４は画像入力部１０１から入力された指紋画像データについての濃淡補正を行なう。部分画像特徴値計算部１０４５は画像内に設定された複数の部分領域の画像のそれぞれについて、部分画像の模様に応じた値を計算して部分画像特徴値として参照用メモリに対応した計算結果を参照用部分画像特徴値計算結果メモリ１０２４に、取込画像用メモリに対応した計算結果を取込画像用部分画像特徴値計算結果メモリ１０２５にそれぞれ出力する。
【００５３】
最大一致度位置探索部１０５は部分画像特徴値計算部１０４５で計算された部分画像特徴値に応じて探索範囲を削減した上で、一方の指紋画像の複数の部分領域をテンプレートとし、該テンプレートと他方の指紋画像内で最も一致度の高い位置を探索する、いわゆるテンプレートマッチング部のようなものである。
【００５４】
類似度計算部１０６はメモリ１０２に格納された最大一致度位置探索部１０５の結果情報を用いて、後述の移動ベクトルに基づく類似度を計算する。類似度判定部１０７は類似度計算部１０６が算出した類似度により一致・不一致を判定する。制御部１０８は照合処理部１１の各部の処理を制御する。
【００５５】
図１の画像照合装置１において、２つの指紋画像を照合するために、２つの指紋画像に対応の画像Ａと画像Ｂを照合する手順について図３のフローチャートに従い説明する。
【００５６】
初めに制御部１０８は、画像入力部１０１へ画像入力開始の信号を送り、その後、画像入力終了信号を受信するまで待機する。画像入力部１０１は照合を行なう画像Ａを入力し、バス１０３を通してメモリ１０２の所定アドレスへ格納する（ステップＴ１）。本実施の形態においては、参照用メモリ１０２１の所定のアドレスへ格納するものとする。画像入力部１０１は、画像Ａの入力が完了した後、制御部１０８に画像入力終了信号を送る。
【００５７】
制御部１０８は、画像入力終了信号を受信すると、再度、画像入力部１０１へ画像入力開始の信号を送り、その後、画像入力終了信号を受信するまで待機する。画像入力部１０１は照合を行なう画像Ｂを入力し、バス１０３を通してメモリ１０２の所定アドレスへ格納する（ステップＴ１）。本実施の形態においては、取込画像用メモリ１０２３の所定のアドレスへ格納するものとする。画像入力部１０１は画像Ｂの入力が完了した後、制御部１０８に画像入力終了信号を送る。
【００５８】
次に制御部１０８は画像補正部１０４に画像補正開始信号を送り、その後、画像補正終了信号を受信するまで待機する。多くの場合、入力画像は画像入力部１０１の特性や指紋自体の乾燥度合いや指を押し付ける圧力に対して各画素の濃淡値や全体の濃度分布が変化するので画質が一様ではないから、入力画像データをそのまま照合に用いることは適当でない。画像補正部１０４は、画像入力時の条件の変動を抑制するように入力画像の画質を補正する（ステップＴ２）。具体的には、入力画像データに対応の画像全体もしくは画像を分割した小領域ごとに、ヒストグラムの平坦化（「コンピュータ画像処理入門」総研出版Ｐ９８）や画像の二値化処理（「コンピュータ画像処理入門」総研出版Ｐ６６−６９）などを、メモリ１０２に格納された即ち、参照用メモリ１０２１、取込画像用メモリ１０２３に格納された画像ＡとＢに施す。
【００５９】
画像補正部１０４は画像Ａと画像Ｂに対する画像補正処理の終了後、制御部１０８に画像補正処理終了信号を送る。
【００６０】
以降で、画像補正部１０４により画像補正処理を施された画像に対して、部分画像特徴値計算処理（ステップＴ２ａ）が行われる。
【００６１】
この部分画像特徴値計算の概略を図４に従って説明する。図４は、画像の部分画像に対し、水平・垂直方向の画素数の最大値などを記載した図である。この図での部分画像は、水平方向、垂直方向ともに画素数１６である１６画素×１６画素の部分領域で構成されている。
【００６２】
本実施の形態１による部分画像特徴値計算は計算対象部分画像につきその模様に応じた値を部分画像特徴値として算出する。つまり、水平方向の最大連続黒画素数maxhlenと垂直方向の最大連続黒画素数maxvlenとを求め、求めた水平方向の最大連続黒画素数maxhlen（模様が水平方向に従う模様である傾向（たとえば横縞である傾向）の大きさを示す値）と垂直方向の最大連続黒画素数maxvlen（模様が垂直方向に従う模様である傾向（たとえば縦縞である傾向）の大きさを示す値）とを比較し、相対的に大きい方向が水平方向ならば、水平（横縞）を意味する値“Ｈ”を、垂直方向ならば垂直（縦縞）を意味する値“Ｖ”を、その他の場合には“Ｘ”を出力する。但し、上記で“Ｈ”あるいは“Ｖ”と判定された場合でも、最大連続黒画素数があらかじめ両方向に対して設定している下限値hlen0ないしvlen0以上でないならば“Ｘ”を出力する。これら条件を数式として表現すると、maxhlen＞maxvlenかつmaxhlen≧hlen0ならば“Ｈ”を出力し、maxvlen＞maxhlenかつmaxvlen≧vlen0ならば“Ｖ”を出力し、その他ならば“Ｘ”を出力するとなる。
【００６３】
図５には、本発明の実施の形態１による部分画像特徴値計算処理のフローチャートが示される。このフローチャートは計算対象となる参照用メモリ１０２１の参照画像のｎ個の部分領域の画像である部分画像Ｒｉについてそれぞれ繰返されて、計算結果値は各部分画像Ｒｉ毎に対応付けて参照用部分画像特徴値計算結果メモリ１０２４に格納される。同様に取込み画像用メモリ１０２４の取込画像のｎ個の部分画像Ｒｉについてそれぞれ繰返されて、計算結果値は各部分画像Ｒｉ毎に対応付けて取込画像用部分画像特徴値計算結果メモリ１０２５に格納される。この部分画像特徴値計算処理の詳細を図５のフローチャートに従って説明する。
【００６４】
制御部１０８は、部分画像特徴値計算部１０４５に部分画像特徴値計算開始信号を送り、その後、部分画像特徴値計算終了信号を受信するまで待機する。部分画像特徴値計算部１０４５は、計算対象画像の部分画像Ｒiを参照用メモリ１０２１ないしは取込画像用メモリ１０２３から読出し、計算用メモリ１０２２に一旦格納する（ステップＳ１）。部分画像特徴値計算部１０４５は格納された部分画像Ｒｉを読出し、水平方向の最大連続黒画素数maxhlenと垂直方向の最大連続黒画素数maxvlenとを求める(ステップＳ２)。ここで、水平方向の最大連続黒画素数maxhlenと垂直方向の最大連続黒画素数maxvlenとを求める処理を、図６、図７に基づいて説明する。
【００６５】
図６は、本発明の実施の形態１による部分画像特徴値計算処理(ステップＴ２ａ)内の水平方向の最大連続黒画素数maxhlenを求める処理(ステップＳ２)のフローチャートである。部分画像特徴値計算部１０４５は、計算用メモリ１０２２から部分画像Ｒｉを読出すとともに、水平方向の最大連続黒画素数maxhlenと垂直方向の画素カウンタjとを初期化、即ち、maxhlen＝０、j＝０とする(ステップSH001）。
【００６６】
次に、垂直方向の画素カウンタjと垂直方向の最大画素数nとを比較し（ステップSH002）、j≧nならば、次にステップSH016を実行しその他ならば、次にステップSH003を実行する。本実施の形態１ではn=15であり、かつ、処理開始時には、j=0であるため、ステップSH003に進む。
【００６７】
ステップSH003では、水平方向の画素カウンタi、前の画素値ｃ、現在の画素連続数len、現在の行での最大黒画素連続数maxの初期化、即ち、i＝0、ｃ＝0、len＝0、max＝0とする(ステップSH003)。次に、水平方向の画素カウンタiと水平方向の最大画素数mとを比較（ステップSH004）し、i≧mならば次にステップSH011を実行し、その他ならば次にステップSH005を実行する。本実施の形態１ではm=15であり、かつ、処理開始時にはi=0であるため、ステップSH005に進む。
【００６８】
ステップSH005では、前の画素値ｃと現在比較対象となっている座標（i、j)の画素値pixel(i、j)とを比較し、c＝pixel(i、j)ならばステップSH006を実行し、その他ならばステップSH007を実行する。本実施の形態１では、cは初期化されていて0(白画素）、pixel(0、0)は、図４を参照して、0(白画素)であるため、c＝pixel(i、j)であり、ステップSH006へ進む。
【００６９】
ステップSH006では、len=len+1を実行する。本実施の形態１では、初期化によりlen=0となっており、1を付加されて、len=1となる。次に、ステップSH010へ進む。
【００７０】
ステップSH010では、i=i+1、即ち、水平方向の画素カウンタをiを増加させる。本実施の形態１では、初期化によりi=0となっており、1を付加されて、i=1となる。次にステップSH004に戻る。以降、０行目の画素値、即ち、pixel(i、0)は、図４を参照して、すべて白画素で0であるため、i=15となるまで、ステップSH004〜SH010を繰返すこととなり、ステップSH010処理後にi=15となった時点での各々の値は、i=15、 c=0、 len=15となっている。この状態で次にステップSH004に進む。m=15、i=15であるので、さらにステップSH011に進む。
【００７１】
ステップSH011では、c=1かつmax＜lenならばステップSH012を実行し、その他ならばステップSH013を実行する。現時点では、c=0、len=15、max＝0であるので、次に、ステップSH013に進む。
【００７２】
ステップSH013では、これまでの行での水平方向の最大連続黒画素数maxhlenと現在の行での最大連続黒画素数maxとを比較し、maxhlen＜maxならばステップSH014を実行し、その他ならばステップSH015を実行する。現時点では、maxhlen=0、max＝0であるので、次に、ステップSH015に進む。
【００７３】
ステップSH015では、ｊ＝ｊ＋1、即ち、垂直方向の画素カウンタｊを１増加させる。現時点では、ｊ＝０であるので、ｊ＝１となり、SH002に戻ることになる。
【００７４】
以降、ｊ＝１〜１4について同様にステップSH002〜SH015の処理を繰返し、ステップSH015処理後、ｊ＝15となった時点で、次にステップSH002で、垂直方向の画素カウンタjと垂直方向の最大画素数nとを比較する。比較結果、j≧nならば次にステップSH016を実行し、その他ならば次にステップSH003を実行すると、現時点では、ｊ＝１５、n=15であるので、次に、ステップSH016に進む。
【００７５】
ステップSH016では、maxhlenを出力することになるが、上述の説明、および、図４を参照して、maxhlenには、水平方向の最大連続黒画素数である、ｙ＝2行目のmax値の１５が格納されていることが分かり、maxhlen＝１５が出力される。
【００７６】
次に、図７の、本発明の実施の形態１による部分画像特徴値計算処理(ステップＴ２ａ)内の垂直方向の最大連続黒画素数maxvlenを求める処理(ステップＳ２)のフローチャートについて説明するが、図７は、上記に説明した図６のフローチャートと基本的に同じ処理を行うことが明らかであり、詳細な説明は省略する。図７のフローチャートに従う処理が実行される結果、出力される垂直方向の最大連続黒画素数maxvlenは、図４のｘ方向に対するmax値である4を示す。
【００７７】
上述の手順で出力されたmaxhlenとmaxvlenとが以降処理される内容を図５のステップＳ３以降に戻って説明する。
【００７８】
ステップＳ３では、maxhlenとmaxvlen、および、所定の最大連続黒画素数下限値hlen0とを比較し、maxhlen＞maxvlenかつmaxhlen≧hlen0ならば、次にステップＳ７を実行し、その他ならば次にステップＳ４を実行する。現時点では、maxhlen=１５、maxvlen=4であり、hlen0を2と設定すれば、次にステップＳ７に進み、参照用部分画像特徴値計算結果メモリ１０２４、あるいは、取込画像用部分画像特徴値計算結果メモリ１０２５の元画像に対する部分画像Ｒｉの特徴値格納領域に“Ｈ”を出力して、制御部１０８に部分画像特徴値計算終了信号を送る。
【００７９】
仮に、上記で、hlen0を５と設定していれば、次にステップＳ４に進み、maxｖlen＞maxhlenかつmaxvlen≧vlen0ならば次にステップＳ５を実行し、その他ならば次にステップＳ６を実行する。この場合、maxhlen=15、maxvlen=4、hlen0=5であるので、次にステップＳ６に進み、参照用部分画像特徴値計算結果メモリ１０２４、あるいは、取込画像用部分画像特徴値計算結果メモリ１０２５の元画像に対する部分画像Ｒｉの特徴値格納領域に“Ｘ”を出力し、制御部１０８に部分画像特徴値計算終了信号を送る。
【００８０】
さらに、仮にステップＳ２の出力値が、maxhlen=4、maxvlen=15、hlen0=2と想定すると、ステップＳ３でmaxhlen＞maxvlenかつmaxhlen≧hlen0ならば次にステップＳ７を実行しその他ならば次にステップＳ４を実行する。
【００８１】
次にステップＳ４に進んだ場合には、maxvlen＞maxhlenかつmaxvlen≧vlen0ならば次にステップＳ５を実行し、その他ならば次にステップＳ６を実行する。
【００８２】
次にステップＳ５に進んだ場合には、参照用部分画像特徴値計算結果メモリ１０２４、あるいは、取込画像用部分画像特徴値計算結果メモリ１０２５の元画像に対する部分画像Ｒｉの特徴値格納領域に“Ｖ”を出力し、制御部１０８に部分画像特徴値計算終了信号を送る。
【００８３】
以上のように本実施の形態１による部分画像特徴値計算部１０４５は、計算対象画像の部分画像Ｒｉ（図４参照）について、水平方向および垂直方向を各画素列を抽出（特定）して、抽出された画素列それぞれにおける黒画素の個数に基づいて、該部分画像の模様が水平方向に従う模様である傾向（たとえば横縞である傾向）、または垂直方向に従う模様である傾向（たとえば縦縞である傾向）またはそのどちらでもないことを判別して、その判別結果に応じた値（“Ｈ”、“Ｖ”および“Ｘ”のいずれか）を出力する。この出力値が該部分画像の特徴値を示す。ここでは連続黒画素の個数に基づき特徴値を求めているが、連続白画素の個数に基づいても同様にして特徴値を求めることができる。
【００８４】
上述のようにして画像補正部１０４により画像補正処理を施され、かつ、部分画像特徴値計算部１０４５により部分画像の特徴値を計算された画像Ａ、画像Ｂに対して、次に照合処理（ステップＴ３）が行われる。この処理を図８のフローチャートに従って説明する。
【００８５】
制御部１０８は最大一致度位置探索部１０５へテンプレートマッチング開始信号を送り、テンプレートマッチング終了信号を受信するまで待機する。最大一致度位置探索部１０５では、ステップＳ００１からステップＳ００７に示されるようなテンプレートマッチング処理が開始される。ステップＳ００１ではカウンタの変数ｉを１に初期化する。ステップＳ００２では画像Ａから部分画像Ｒｉとして規定される部分領域の画像をテンプレートマッチングに用いるテンプレートとして設定する。ここでは、部分画像Ｒｉは計算を簡単にするために矩形状としているが、これに特定されない。
【００８６】
ステップＳ００２５では部分画像Ｒｉに対応する参照部分画像特徴値計算結果ＣＲｉをメモリ１０２４から読出す。
【００８７】
ステップＳ００３ではステップＳ００２で設定したテンプレートに対し、画像Ｂ内で最も一致度の高い、つまり画像内のデータが最も一致する場所を探索するが、探索処理量の削減のために、画像Ａの部分画像Ｒｉに対応する参照部分画像特徴値計算結果ＣＲｉと同じ値を持つ画像Ｂに対する取込画像用部分画像特徴値計算結果ＣＭを持つ部分領域に限定して次の計算を行う。テンプレートとして用いる部分画像Ｒｉの左上の角を基準とした座標（ｘ、ｙ）の画素濃度をＲｉ（ｘ、ｙ）とし、画像Ｂの左上の角を基準とした座標（ｓ、ｔ）の画素濃度をＢ（ｓ、ｔ）とし、部分画像Ｒｉの幅をｗ、高さをｈとし、また、画像ＡとＢの各画素の取りうる最大濃度をＶ０とし、画像Ｂにおける座標（ｓ、ｔ）での一致度Ｃｉ（ｓ、ｔ）をたとえば以下の（式１）に従い各画素の濃度差を元に計算する。
【００８８】
【数１】
2005149455.tif 000003
【００８９】
画像Ｂ内において座標（ｓ、ｔ）を順次更新して座標（ｓ、ｔ）における一致度Ｃ（ｓ、ｔ）を計算し、その中で最も大きい値を取る位置が最も一致度が高いとし、その位置での部分領域の画像を部分領域Ｍｉとし、その位置での一致度を最大一致度Ｃｉｍａｘとする。ステップＳ００４ではステップＳ００３で算出した部分画像Ｒｉの画像Ｂ内における最大一致度Ｃｉｍａｘをメモリ１０２の所定アドレスに記憶する。ステップＳ００５では、移動ベクトルＶｉを以下の（式２）に従い計算して求めて、メモリ１０２の所定アドレスに記憶する。
【００９０】
ここで、上述のように、画像Ａに設定された位置Ｐに対応の部分画像Ｒｉに基づいて、画像Ｂ内をスキャンして部分画像Ｒｉと最も一致度が高い位置Ｍの部分領域Ｍｉが特定されたとき、位置Ｐから位置Ｍへの方向ベクトルを、移動ベクトルと呼ぶ。これは、指紋センサにおける指の置かれ方は一様でないことから、一方の画像、たとえば画像Ａを基準にすると他方の画像Ｂは移動したように見えることによる。
【００９１】
Ｖｉ＝（Ｖｉｘ、Ｖｉｙ）＝（Ｍｉｘ−Ｒｉｘ、Ｍｉｙ−Ｒｉｙ）…（式２）
（式２）で、変数ＲｉｘとＲｉｙは部分画像Ｒｉの基準位置のｘ座標とｙ座標であり、たとえば画像Ａ内における部分画像Ｒｉの左上角の座標に対応する。また変数ＭｉｘとＭｉｙは部分領域Ｍｉの探索結果である最大一致度Ｃｉｍａｘの位置でのｘ座標とｙ座標であり、たとえば画像Ｂ内におけるマッチングした位置での部分領域Ｍｉの左上角の座標に対応する。
【００９２】
ステップ００６ではカウンタ変数ｉが部分領域の総個数ｎ以下か否かを判定し、変数ｉの値が部分領域の総個数ｎ以下であれば処理をＳ００７に移し、そうでなければ処理をＳ００８に移す。ステップＳ００７では変数ｉの値に１加える。以降変数ｉの値が部分領域の総個数ｎ以下の間はステップＳ００２からＳ００７を繰返し行ない、すべての部分画像Ｒｉに関し画像Ａの部分画像Ｒｉに対応する参照部分画像特徴値計算結果ＣＲｉと同じ値を持つ画像Ｂに対する取込画像用部分画像特徴値計算結果ＣＭを持つ部分領域に限定してテンプレートマッチングを行ない、それぞれの部分画像Ｒｉの最大一致度Ｃｉｍａｘと、移動ベクトルＶｉとを計算していく。
【００９３】
最大一致度位置探索部１０５は上記のように順次計算されるすべての部分画像Ｒｉに関する最大一致度Ｃｉｍａｘと移動ベクトルＶｉとをメモリ１０２の所定アドレスに格納したのち、テンプレートマッチング終了信号を制御部１０８に送り、処理を終了する。
【００９４】
続いて制御部１０８は類似度計算部１０６に類似度計算開始信号を送り、類似度計算終了信号を受信するまで待機する。類似度計算部１０６は、メモリ１０２に格納されているテンプレートマッチングで得られた各部分画像Ｒｉの移動ベクトルＶｉや最大一致度Ｃｉｍａｘなどの情報を用いて、図８のステップＳ００８からステップＳ０２０に示される処理を行ない類似度計算を行なう。
【００９５】
ステップＳ００８では類似度Ｐ（Ａ、Ｂ）を０に初期化する。ここで類似度Ｐ（Ａ、Ｂ）とは、画像Ａと画像Ｂの類似度を格納する変数とする。ステップＳ００９では基準とする移動ベクトルＶｉのインデックスｉを１に初期化する。ステップＳ０１０では、基準となる移動ベクトルＶｉに関する類似度Ｐｉを０に初期化する。ステップＳ０１１では、移動ベクトルＶｊのインデックスｊを１に初期化する。ステップＳ０１２では、基準移動ベクトルＶｉと移動ベクトルＶｊとのベクトル差ｄＶｉｊを以下の（式３）に従い計算する。
【００９６】
ｄＶｉｊ＝｜Ｖｉ−Ｖｊ｜＝ｓｑｒｔ（（Ｖｉｘ−Ｖｊｘ）＾２＋（Ｖｉｙ−Ｖｊｙ）＾２）…（式３）
ここで、変数ＶｉｘとＶｉｙは移動ベクトルＶｉのｘ方向成分とｙ方向成分を示し、変数ＶｊｘとＶｊｙは移動ベクトルＶｊのｘ方向成分とｙ方向成分を示し、変数ｓｑｒｔ（Ｘ）はＸの平方根、Ｘ＾２はＸの二乗を計算する計算式である。
【００９７】
ステップＳ０１３では、移動ベクトルＶｉとＶｊのベクトル差ｄＶｉｊに関し所定の定数εと比較し、移動ベクトルＶｉと移動ベクトルＶｊが実質的に同一の移動ベクトルとみなすことが可能かを判断する。ベクトル差ｄＶｉｊが定数εより小さければ、移動ベクトルＶｉと移動ベクトルＶｊが実質的に同一と見なして処理をステップＳ０１４に移し、逆に大きければ実質的に同一とは見なさず処理をステップＳ０１５に移す。ステップＳ０１４では類似度Ｐｉを以下の（式４）〜（式６）で増加させる。
【００９８】
Ｐｉ＝Ｐｉ＋α…（式４）
α＝１…（式５）
α＝Ｃｊｍａｘ…（式６）
（式４）における変数αは類似度Ｐｉを増加させる値である。（式５）のようにα＝１とした場合には、類似度Ｐｉは基準とした移動ベクトルＶｉと同一の移動ベクトルを持つ部分領域の個数となる。また、（式６）のようにα＝Ｃｊｍａｘとした場合には、類似度Ｐｉは基準とした移動ベクトルＶｉと同一の移動ベクトルを持つ部分領域に関するテンプレートマッチング時の最大一致度の総和となる。またベクトル差ｄＶｉｊの大きさに応じて変数αの値を小さくするなどしても構わない。
【００９９】
ステップＳ０１５はインデックスｊが部分領域の総個数ｎより小さいかどうかを判定し、インデックスｊが部分領域の総個数ｎより小さい場合は処理をステップＳ０１６に移し、大きい場合には処理をステップＳ０１７に移す。ステップＳ０１６ではインデックスｊの値を１増加させる。ステップＳ０１０からステップＳ０１６の処理により、基準とした移動ベクトルＶｉに関して、同じ移動ベクトルを持つと判定される部分領域の情報を用いた類似度Ｐｉが計算される。ステップＳ０１７では移動ベクトルＶｉを基準とした場合の類似度Ｐｉと変数Ｐ（Ａ、Ｂ）と比較を行ない、類似度Ｐｉが現在までの最大の類似度（変数Ｐ（Ａ、Ｂ）の値）より大きければ処理をＳ０１８に移し、小さければ処理をＳ０１９に移す。
【０１００】
ステップＳ０１８では、変数Ｐ（Ａ、Ｂ）に移動ベクトルＶｉを基準とした場合の類似度Ｐｉの値を設定する。ステップＳ０１７、Ｓ０１８では、移動ベクトルＶｉを基準とした場合の類似度Ｐｉが、この時点までに計算された他の移動ベクトルを基準にした場合の類似度の最大値（変数Ｐ（Ａ、Ｂ）の値）と比べ大きい場合には、基準としている移動ベクトルＶｉが現在までのインデックスｉの中で最も基準として正当であるとしている。
【０１０１】
ステップＳ０１９では基準とする移動ベクトルＶｉのインデックスｉの値と部分領域の個数（変数ｎの値）を比較する。インデックスｉが部分領域の個数より小さければ処理をステップＳ０２０に移す。ステップＳ０２０ではインデックスｉを１増加させる。
【０１０２】
ステップＳ００８からステップＳ０２０により、画像Ａと画像Ｂにおける類似度が変数Ｐ（Ａ、Ｂ）の値として計算される。類似度計算部１０６は上記のように計算した変数Ｐ（Ａ、Ｂ）の値をメモリ１０２の所定アドレスに格納し、制御部１０８へ類似度計算終了信号を送り、処理を終了する。
【０１０３】
続いて制御部１０８は照合判定部１０７に照合判定開始信号を送り、照合判定終了信号を受信するまで待機する。照合判定部１０７は照合し判定する（ステップＴ４）。具体的には、メモリ１０２に格納された変数Ｐ（Ａ、Ｂ）の値で示される類似度と予め定められた照合閾値Ｔとを比較する。比較結果、変数Ｐ（Ａ、Ｂ）≧Ｔならば画像Ａと画像Ｂは同一指紋から採取されたものと判定しメモリ１０２の所定アドレスへ照合結果として‘一致’を示す値、たとえば‘１’を書込み、そうでなければ異なる指紋から採取されたものと判定し、メモリ１０２、即ち、計算用メモリ１０２２の所定アドレスへ照合結果として‘不一致’を示す値、たとえば‘０’を書込む。その後、制御部１０８へ照合判定終了信号を送り処理を終了する。
【０１０４】
最後に制御部１０８がメモリ１０２に格納された照合結果をディスプレイ６１０またはプリンタ６９０を介して出力して（ステップＴ５）、画像照合を終了する。
【０１０５】
本実施の形態において、画像補正部１０４、部分画像特徴値計算部１０４５、最大一致度位置探索部１０５、類似度計算部１０６、照合判定部１０７および制御部１０８のすべてあるいは一部は処理手順をプログラムとして記憶させたメモリ６２４などのＲＯＭとそれを実行するためのＣＰＵ６２２などの演算処理装置を用いて構成してもよい。
【０１０６】
ここで、本実施の形態１による照合処理の具体例ならびにそれによる効果を示す。
【０１０７】
上述の通り、本実施の形態での特徴となる照合処理は、図３のフローチャートの部分画像特徴値計算処理(Ｔ２ａ）、および、類似度計算処理（Ｔ３）であるため、以降、画像入力（Ｔ１）、画質補正（Ｔ２）が施された画像などについて、部分画像ならびに画像特徴値の入力順に記述する。
【０１０８】
図９（Ｂ）は、画像入力（Ｔ１）、画質補正（Ｔ２）が施され、取込画像用メモリ１０２３に格納されている画像Ａ、図９（Ｃ）は、画像入力（Ｔ１）、画質補正（Ｔ２）が施され、参照用メモリ１０２１に格納されている画像Ｂである。上述の照合処理を２つの画像ＡとＢを例にして説明する。
【０１０９】
まず、図９(Ａ)を参照して画像内の部分画像位置をいかに特定するかについて説明する。図９（Ａ）の画像の形状（形、サイズ）は図９（Ｂ）と図９（Ｃ）の画像ＡとＢに一致している。図９（Ａ）の画像内にはメッシュ状に区切られて６４個の同じ形状（矩形状）の部分画像が準備される。これら６４個の部分画像は図９（Ａ）の画像の右上から左下方向に数値１〜６４を順に当てて、画像内の６４個の部分画像の位置を示す。ここでは画像内の６４個の部分画像それぞれは、対応の位置を示す数値を用いて部分画像ｇ１、部分画像ｇ２、…、部分画像ｇ６４として特定される。図９（Ｂ）、図９（Ｃ）および図９（Ａ）の画像は同一の形状を有するので、図９（Ｂ）と（Ｃ）の画像ＡとＢにおいても図９（Ａ）に示すような６４個の部分画像が設けられて部分画像ｇ１、部分画像ｇ２、…、部分画像ｇ６４としてその位置を特定できる。
【０１１０】
図１０（Ａ）〜（Ｃ）は画像ＡとＢの照合手順を説明する図である。上述の通り、本実施の形態１においては、画像Ａの“Ｈ”ないし“Ｖ”の部分画像特徴値を持つ部分画像について、対応する部分画像特徴値を持つ部分画像を画像Ｂ内で探索する。従って、画像Ａ内の部分画像について、最初に“Ｈ”ないし“Ｖ”の部分画像特徴値を持つ部分画像が最初の対象部分画像となる。図１０（Ａ）の画像（Ａ）-Ｓ１は、画像Ａの部分画像につき、部分画像特徴値を示し、かつ、最初に“Ｈ”ないし“Ｖ”の部分画像特徴値を持つ部分画像ｇ２７、即ち“Ｖ１”につき、ハッチングを施した画像である。
【０１１１】
この画像（Ａ）-Ｓ１の通り、最初の部分画像特徴値は、“Ｖ”である。このため、画像Ｂ内で部分画像特徴値が“Ｖ”である部分画像が探索対象となる。画像Ｂ内で、最初に部分画像特徴値“Ｖ”を持つ部分画像ｇ１１、即ち“Ｖ１”につきハッチングを施した画像が図１０（Ａ）の画像（Ｂ）-Ｓ１−１である。この部分画像に対し、図８のステップＳ００２〜Ｓ００７で示される処理が行われる。次に、画像Ｂ内で、部分画像ｇ１１の次に部分画像特徴値“Ｖ”を持つ部分画像ｇ１４、即ち“Ｖ１”（図１０（Ａ）の画像(Ｂ)-Ｓ１-２)につき、処理が行われ、以降部分画像ｇ１９、ｇ２２、ｇ２６、ｇ２７、ｇ３０、ｇ３１(図１０（Ａ）の画像(Ｂ)-Ｓ１-８)につき、処理が行われる。画像Ａの最初に“Ｈ”ないし“Ｖ”の部分画像特徴値を持つ部分画像ｇ２７につき一通り処理されたため、次に“Ｈ”ないし“Ｖ”の部分画像特徴値を持つ部分画像ｇ２８（図１０（Ｂ）の画像(Ａ)-Ｓ２)について、同様に図８のステップＳ００２〜Ｓ００７で示される処理が行われ、部分画像ｇ２８の部分画像特徴値が“Ｈ”であるため、画像Ｂの部分画像特徴値が“Ｈ”である部分画像ｇ１２（図１０（Ｂ）の画像(Ｂ)-Ｓ２-１)、画像ｇ１３（図１０（Ｂ
）の画像(Ｂ)-Ｓ２-２)、ｇ３３、ｇ３４、ｇ３９、ｇ４０、ｇ４２〜ｇ４６、ｇ４７(図１０（Ｂ）の画像(Ｂ)-Ｓ２-１２)について一通り処理が行われる。以降、画像Ａで“Ｈ”ないし“Ｖ”の部分画像特徴値を持つ部分画像ｇ２９、ｇ３０、ｇ３５、ｇ３８、ｇ４２、ｇ４３、ｇ４６、ｇ４７、ｇ４９、ｇ５０、ｇ５５、ｇ５６、ｇ５８〜６２、ｇ６３(図１０（Ｃ）の画像（Ａ）-Ｓ２０)についても同様に処理が行われる。
【０１１２】
本実施の形態による画像Ａと画像Ｂとにおいて探索される部分画像の数は、（部分画像特徴値“Ｖ”である画像Ａの部分画像数×部分画像特徴値“Ｖ”である画像Ｂの部分画像数＋部分画像特徴値“Ｈ”である画像Ａの部分画像数×部分画像特徴値“Ｈ”である画像Ｂの部分画像数）である。
【０１１３】
図１０（Ａ）〜（Ｃ）の場合の探索される部分画像の数は、探索部分画像数(本実施の形態１)＝８×８＋１２×１２＝２０８である。
【０１１４】
尚、本実施の形態による部分画像特徴値は、図形の模様にも依存するため、図９（Ｂ）と（Ｃ）の模様とは別の模様の場合を示す。図１１（Ａ）と（Ｂ）は取込画像Ａと参照画像Ｂとを示し、図９（Ｂ）と（Ｃ）の画像Ａと画像Ｂとは別の図形模様を示すものであり、図１１(Ｃ)は、図９（Ｃ)の参照画像Ｂとは異なる参照画像Ｃを示すものである。
【０１１５】
図１１（Ｄ）、図１１（Ｅ）および図１１（Ｆ）各々は、図１１（Ａ）、図１１（Ｂ）および図１１（Ｃ）の画像Ａ、ＢおよびＣそれぞれの部分画像特徴値を示すものである。
【０１１６】
図１１（Ａ）の取込画像Ａに対する図１１（Ｃ）の参照画像Ｃに対する探索部分画像数についても、上記と同様に、（部分画像特徴値“Ｖ”である画像Ａの部分画像数×部分画像特徴値“Ｖ”である画像Ｃの部分画像数＋部分画像特徴値“Ｈ”である画像Ａの部分画像数×部分画像特徴値“Ｈ”である画像Ｃの部分画像数）で計算できる。図１１（Ｄ）と図１１（Ｆ）を参照すると、探索部分画像数(本実施の形態１)＝８×１２＋１２×１６＝２８８である。
【０１１７】
尚、本説明では、部分画像特徴値が同じ領域を探索対象としているが、必ずしもそうする必要はなく、照合精度の向上などを意図して、参照用部分画像特徴値が“Ｈ”の場合に取込画像用部分画像特徴値が“Ｈ”だけでなく“Ｘ”の領域、あるいは、参照用部分画像特徴値が“Ｖ”の場合に取込画像用部分画像特徴値が“Ｖ”だけでなく“Ｘ”の領域も探索対象としても良いことはいうまでもない。
【０１１８】
また、部分画像特徴値が“Ｘ”であることは対応の部分画像が縦縞とも横縞とも特定できない模様を呈しているといえ、照合速度の向上を図る場合には、最大一致度位置検索部１０５による探索範囲からは“Ｘ”を示す部分領域は除くようにしてもよい。
【０１１９】
（実施の形態２）
本実施の形態２では、取込画像と照合されるべき参照画像が多数準備されていた場合に、より速やかに照合処理することができる技術が示される。つまり、多数の参照画像を予め複数のカテゴリに分類しておく。そして、取込画像が入力されると、該取込画像はいずれのカテゴリに該当するかを判定して、判定結果が示す取込画像のカテゴリに基づいて選択されたカテゴリに属する参照画像のそれぞれと該取込画像とを照合する手順が採用される。
【０１２０】
本実施の形態２に係る画像照合装置１Ａの構成が図１２に示される。図１２の画像照合装置１Ａと図１の画像照合装置１とを比較して異なる点は、照合処理部１１は図１の構成に加えて画像カテゴリ判定部１０４７を有し、メモリ１０２には図１の参照用部分画像特徴値計算結果メモリ１０２４および取込画像用部分画像特徴値計算結果メモリ１０２５に代替して参照用部分画像特徴値計算結果および画像カテゴリ計算結果メモリ１０２４Ａ（以下、単にメモリ１０２４Ａと称す）および取込画像用部分画像特徴値計算結果および画像カテゴリ計算結果メモリ１０２５Ａ（以下、単にメモリ１０２５Ａと称す）を有する点にある。メモリ１０２の他の部分は図１に示すものと同様である。部分画像特徴値計算部１０４５、画像カテゴリ判定部１０４７および最大一致度位置探索部１０５の機能は次のようであるが、照合処理部１１の他の部分は実施の形態１と同様である。
【０１２１】
部分画像特徴値計算部１０４５は画像内に設定された複数の部分領域の画像のそれぞれについて、部分画像の模様に応じた値を計算して部分画像特徴値として参照用メモリに対応した計算結果をメモリ１０２４Ａに、取込画像用メモリに対応した計算結果をメモリ１０２５Ａにそれぞれ出力する。
【０１２２】
画像カテゴリ判定部１０４７は、予め次の処理を行う。つまり、複数の参照用画像をカテゴリに分類する計算をする。その際には、メモリ１０２４Ａを参照して、各参照画像の特定箇所の部分画像の特徴値の組合わせによりカテゴリ分けを行い、その分類結果をメモリ１０２４Ａに画像情報とともに登録する。
【０１２３】
照合のための画像が入力された際には、画像カテゴリ判定部１０４７は、メモリ１０２５Ａを参照して部分画像特徴値を読出し、特定箇所の部分画像の部分画像特徴値の組合わせを求め、当該部分画像特徴値の組合わせが、上記のどのカテゴリに属するかを判定する。判定結果が示すカテゴリと同じカテゴリに属する参照画像のみを最大一致度位置探索部１０５による探索の対象とするか、または同一カテゴリに属する参照画像から優先的に最大一致度位置探索部１０５による探索の対象とすることを指示する判定結果の情報を出力する。
【０１２４】
最大一致度位置探索部１０５は、画像カテゴリ判定部１０４７により出力された判定情報に基づき照合対象となる参照画像を特定する。そして、入力した取込画像と特定した参照画像それぞれとについて、部分画像特徴値計算部１０４５で計算された部分画像特徴値に応じて探索範囲を削減した上で、前述と同様にテンプレートマッチングの処理を実施する。
【０１２５】
本実施の形態２による照合処理の手順が図１３のフローチャートに示される。図１３と図３を参照して異なる点は、図３の類似度計算処理（Ｔ３）と照合し判定の処理（Ｔ４）に代替して、画像カテゴリ判定計算の処理（Ｔ２ｂ）と類似度計算と照合・判定の処理（Ｔ３ｂ）とを設けた点にある。図１３の他の処理は図３のそれと同じである。図１４には類似度計算と照合・判定の処理（Ｔ３ｂ）のフローチャートが示されて、図１５には画像カテゴリ判定計算の処理（Ｔ２ｂ）のフローチャートが示される。
【０１２６】
画像照合処理において、実施の形態１と同様にして画像補正部１０４により取込画像について画像補正処理が施されて（Ｔ２）、その後、部分画像特徴値計算部１０４５により取込画像と参照画像について部分画像の特徴値が計算される。このような計算が施された取込画像と参照画像に対して画像カテゴリ判定計算処理（Ｔ２ｂ）が画像カテゴリ判定部１０４７により実行される。この手順を図１５のフローチャートに従い、図１６〜図１９を参照しながらに説明する。
【０１２７】
まず、メモリ１０２５Ａから各マクロ部分画像の部分画像特徴値を読出す（ステップＳＪ（以下、単にＳＪと略す）０１）。具体的には次のようである。
【０１２８】
取扱う画像が指紋であると想定した場合、既に知られている様に、指紋の紋様は図１６に示される様な例えば５通りのカテゴリに分類される。図１６のテーブルＴＢ１では、指紋について知られている画像例３１を示すデータのそれぞれに対応して、部分画像群（マクロ部分画像）の配置、画像カテゴリ名およびカテゴリ番号を示すデータ３２から３４がそれぞれ登録されている。テーブルＴＢ１はメモリ６２４に予め格納されて画像カテゴリ判定部１０４７によりカテゴリ判定のために適宜参照される。データ３２は後述の図１８（Ｄ）および図１９（Ｄ）にも示されている。
【０１２９】
テーブルＴＢ１には指紋の画像例のデータ３１として示す渦状紋の画像データ３１Ａ、弓状紋の画像データ３１Ｂ、突起弓状紋の画像データ３１Ｃ、右蹄状紋の画像データ３１Ｄ、左蹄状紋の画像データ３１Ｅおよびこれらに該当しない画像データ３１Ｆが登録されている。これら画像データの特徴を利用して、画像の照合対象を参照画像、取込画像ともに同一カテゴリに絞れば、照合に必要な処理量が低減されるものと考えられる。このカテゴリ分けに、画像の部分画像の特徴値を利用することが可能であれば、少ない処理量で分類が可能であると期待できる。
【０１３０】
図１７（Ａ）から（Ｆ）を参照して、図１６の登録内容を説明する。図１７（Ｂ）と（Ｃ）は、入力（取込）画像と参照画像とそれぞれ模式的に示したものであり、縦と横の両方向につきそれぞれ８分割、即ち、６４個の部分画像からなる画像として示される。図１７（Ａ）には、前述の図９（Ａ）と同様に図１７（Ｂ）と（Ｃ）各々の部分画像について位置ｇ１〜ｇ６４が規定して示される。
【０１３１】
図１７（Ｄ）には、本実施の形態の画像におけるマクロ部分画像Ｍ１〜Ｍ９が規定して示される。本実施の形態においてマクロ部分画像とは、取込画像または参照画像の位置ｇ１〜ｇ６４で示される複数の特定の部分画像の組を指す。本実施の形態では、図１７（Ｄ）のマクロ部分画像Ｍ１中の数値１−４で示す様に４つの部分画像で１つのマクロ部分画像を構成している。本実施の形態では、１画像当たり９つのマクロ部分画像Ｍ１〜Ｍ９を有するとしているが、１画像当たりのマクロ部分画像の個数は９個に限定されず、また１マクロ部分画像を構成する部分画像の個数も４個に限定されない。マクロ部分画像Ｍ１〜Ｍ９を構成する部分画像は対応の位置（ｇ１〜ｇ６４）を用いて示すと下記の通りである。
【０１３２】
マクロ部分画像Ｍ１∋ｇ４、ｇ５、ｇ１２、ｇ１３
マクロ部分画像Ｍ２∋ｇ２５、ｇ２６、ｇ３３、ｇ３４
マクロ部分画像Ｍ３∋ｇ２７、ｇ２８、ｇ３５、ｇ３６
マクロ部分画像Ｍ４∋ｇ２８、ｇ２９、ｇ３６、ｇ３７
マクロ部分画像Ｍ５∋ｇ２９、ｇ３０、ｇ３７、ｇ３８
マクロ部分画像Ｍ６∋ｇ３１、ｇ３２、ｇ３９、ｇ４０
マクロ部分画像Ｍ７∋ｇ４９、ｇ５０、ｇ５７、ｇ５８
マクロ部分画像Ｍ８∋ｇ５２、ｇ５３、ｇ６０、ｇ６１
マクロ部分画像Ｍ９∋ｇ５５、ｇ５６、ｇ６３、ｇ６４
従って、これらマクロ部分画像Ｍ１〜Ｍ９それぞれについて、その部分画像の特徴値をメモリ１０２５Ａから読出す(ＳＪ０１)。図１７（Ｂ）と（Ｃ）の画像に対する部分画像特徴値が図１７（Ｅ）と（Ｆ）にそれぞれ示されている。図１８（Ａ）は、図１７（Ｂ）と（Ｅ）に対応する画像に対する各マクロ部分画像Ｍ１〜Ｍ９に対し読出した部分画像特徴値を示している。
【０１３３】
次に、これらマクロ部分画像毎に特徴値、すなわち「Ｈ」、「Ｖ」、「Ｘ」を判定する(ＳＪ０２)。この判定手順について説明する。
【０１３４】
本実施の形態では、各マクロ部分画像を構成する４個の部分画像の内、３個または４個の部分画像の特徴値がすべて「Ｈ」またはすべて「Ｖ」である場合には、該マクロ部分画像の特徴値は「Ｈ」または「Ｖ」であると判定し、その他の場合には「Ｘ」と判定する。
【０１３５】
具体例を説明する。図１７（Ｂ）の画像の場合には、マクロ部分画像Ｍ１を構成する４個の部分画像の特徴値は、「Ｈ」、「Ｈ」、「Ｈ」、「Ｈ」であり、「Ｖ」または「Ｘ」である部分画像は０個である（図１８（Ｂ）を参照）。そのため、マクロ部分画像Ｍ１の特徴値は「Ｈ」と判定される(図１８（Ｃ）を参照）。同様にして、マクロ部分画像Ｍ２〜Ｍ９そそれぞれについて判定すると、順に、特徴値は「Ｖ」、「Ｘ」、「Ｘ」、「Ｘ」、「Ｖ」、「Ｘ」、「Ｈ」、「Ｘ」と判定される(図１８（Ｃ）を参照）。
【０１３６】
次に、上記各マクロ部分画像毎の判定結果を参照して、画像のカテゴリ判定を行う(ＳＪ０３）。この判定手順を説明する。まず、図１６の画像データ３１Ａ〜３１Ｆに示す指紋紋様の画像の特徴による部分画像群の配置との比較を行う。図１８（Ｄ）には、画像データ３１Ａ〜３１Ｆのマクロ部分画像Ｍ１〜Ｍ９の特徴値がカテゴリ番号のデータ３４に対応付けて示される。
【０１３７】
図１８（Ｃ）と図１８（Ｄ）とを比較して、図１８（Ｃ）のマクロ部分画像Ｍ１〜Ｍ９の特徴値と一致するマクロ部分画像Ｍ１〜Ｍ９の特徴値を有するのは、カテゴリ番号のデータ３４が‘１’である画像データ３１Ａであると分かる。従って、取込み画像（入力画像）の図１７（Ｂ）に対応する画像は‘１’のカテゴリに属する、言換えると渦状紋の指紋画像であると判定される。
【０１３８】
同様に、例えば図１７（Ｃ）に対応する画像については、図１９（Ａ）〜（Ｅ）に示される如く処理されて、‘２’のカテゴリに属する、言換えると弓状紋の指紋画像であると判定される。
【０１３９】
次に、図１３に戻り、上述のような画像カテゴリの判定結果を考慮した類似度計算及び照合判定処理（Ｔ３）が行われる。この処理を図１４のフローチャートに従って説明する。
【０１４０】
制御部１０８は最大一致度位置探索部１０５へテンプレートマッチング開始信号を送り、テンプレートマッチング終了信号を受信するまで待機する。最大一致度位置探索部１０５では、ステップＳ００１ａ〜Ｓ００１ｃ、Ｓ００２ａ〜Ｓ００２ｂおよびＳ００３〜Ｓ００７に示されるようなテンプレートマッチング処理が開始される。
【０１４１】
まず、カウンタの変数ｋ（ここで変数ｋは、同一カテゴリに属する参照画像数をカウントする変数）を１に初期化する（Ｓ００１ａ）。次に、上述の画像カテゴリ判定計算(Ｔ２５ｂ)により出力された判定結果が示す入力画像のカテゴリと同一のカテゴリに属する参照画像Ａkを参照する。次にカウンタの変数ｉを１に初期化する（Ｓ００１ｃ）。そして、参照画像Ａkから部分画像Ｒｉとして規定される部分領域の画像をテンプレートマッチングに用いるテンプレートとして設定する（Ｓ００２ｂ）。以降は、前述の図８と同様な手順が参照画像Ａｋと入力画像について実行される。
【０１４２】
その後、制御部１０８は照合判定部１０７に照合判定開始信号を送り、照合判定終了信号を受信するまで待機する。照合判定部１０７は照合し判定する。具体的には、メモリ１０２に格納された変数Ｐ（Ａk、Ｂ）の値で示される類似度と予め定められた照合閾値Ｔとを比較する(ステップＳ０２１)。比較結果、変数Ｐ（Ａk、Ｂ）≧Ｔならば参照画像Ａkと入力画像Ｂは同一指紋から採取されたものと判定しメモリ１０２の所定アドレスへ照合結果として‘一致’を示す値、たとえば‘１’を書込む（Ｓ０２４）。そうでなければ異なる指紋から採取されたものと判定し、変数ｋ＜ｐ（ここでｐは同一カテゴリ内の参照画像の総個数)ならば（Ｓ０２２でＹＥＳ）、即ち同一カテゴリの参照画像Ａkに未照合の画像があるならば、ｋを１増加させ（Ｓ０２３）、ステップＳ００１ｂに戻り、同一カテゴリの別の参照画像を用いて再度、以降の類似度計算および照合処理を行う。
【０１４３】
別の参照画像による照合処理後、メモリ１０２に格納された変数Ｐ（Ａk、Ｂ）の値で示される類似度と予め定められた照合閾値Ｔとを比較した結果、変数Ｐ（Ａk、Ｂ）≧Ｔならば（Ｓ０２１でＹＥＳ）、画像Ａkと画像Ｂは同一指紋から採取されたものと判定しメモリ１０２の所定アドレスへ照合結果として‘一致’を示す値、たとえば‘１’を書込み（Ｓ０２４）、制御部１０８へ照合判定終了信号を送り処理を終了する。一方、変数Ｐ（Ａk、Ｂ）≧Ｔでないならば（Ｓ０２１でＮＯ）、変数ｋ＜ｐでない（Ｓ０２２でＮＯ）即ち、同一カテゴリの参照画像Ａkに未照合画像がないならば、メモリ１０２、即ち、計算用メモリ１０２２の所定アドレスへ照合結果として‘不一致’を示す値、たとえば‘０’を書込む。その後、制御部１０８へ照合判定終了信号を送り処理を終了する。以上で類似度計算及び照合判定処理は終了する。
【０１４４】
図１３に戻り、最後に制御部１０８がメモリ１０２に格納された照合結果をディスプレイ６１０またはプリンタ６９０を介して出力して（ステップＴ５）、画像照合を終了する。
【０１４５】
本実施の形態において、画像補正部１０４、部分画像特徴値計算部１０４５、画像カテゴリ判定部１０４７、最大一致度位置探索部１０５、類似度計算部１０６、照合判定部１０７および制御部１０８のすべてあるいは一部は処理手順をプログラムとして記憶させたメモリ６２４などのＲＯＭとそれを実行するためのＣＰＵ６２２などの演算処理装置を用いて構成してもよい。
【０１４６】
ここで、本実施の形態２による照合処理の具体例ならびにそれによる効果を示す。
【０１４７】
上述の通り、本実施の形態での特徴となる照合処理は、図１３のフローチャートの画像カテゴリ判定計算処理(Ｔ２ｂ)および類似度計算及び照合判定処理(Ｔ３ｂ)であるため、以降、画像入力（Ｔ１）、画質補正（Ｔ２）、部分画像特徴値計算処理(Ｔ２ａ）が施された画像などについて記述する。
【０１４８】
ここで、画像照合処理システムにおいて１００個の参照画像のデータが登録されており、参照画像の紋様に、即ち、本実施の形態でいうところの画像カテゴリに特定の偏りのない場合を想定する。この想定のもと、本実施の形態２の各カテゴリに属する参照画像は２０個となる。
【０１４９】
実施の形態１においては、ある入力画像に対して、平均的には１００個の参照画像に対し、約半分の５０個の参照画像と照合することにより、判定結果として‘一致’を得ることが期待できるであろう。一方、本実施の形態２においては、照合処理に先立って画像カテゴリ判定計算（Ｔ２ｂ）により、照合対象となる参照画像が１つのカテゴリに属するものに限定されるので、本実施の形態２では、各カテゴリに属する参照画像の総数の約半分の１０個の参照画像と照合することにより判定結果として‘一致’を得ることが期待できるであろう。
【０１５０】
したがって、本実施の形態２の類似度判定及び照合判定の処理量／実施の形態１の類似度判定及び照合判定の処理量≒（１／カテゴリ数）と考えられる。但し、実施の形態２では照合処理の前に画像カテゴリ判定計算(Ｔ２ｂ)分の処理量が必要であるが、この計算のために使用される元情報である各マクロ部分画像に属す部分画像の特徴値(図１８（Ａ）と図１９（Ａ））は実施の形態１にも使用するものであるから、実施の形態２は実施の形態１に比べて処理量の増加はないといえる。
【０１５１】
各マクロ部分画像単位での特徴値判定(図１８（Ｃ）と図１９（Ｃ）)及び画像のカテゴリ判定(図１８（Ｅ）と図１９（Ｅ）)は、図１８（Ｄ）と図１８（Ｅ）との比較（または、図１９（Ｄ）と図１９との比較）で示す様に処理量の少ない比較処理を多数の参照画像との照合処理の前に１度のみ行うものであり、実質的に無視できる程度の処理量であることは明らかである。
【０１５２】
なお、本実施の形態２においては、参照画像については、予めメモリ１０２４Ａに取り込んでいる場合を記載しているが、スナップショット画像を使用して参照画像を構成しても良い。
【０１５３】
（実施の形態３）
部分画像特徴値計算は実施の形態１とは異なる次の手順で実施されてもよい。
【０１５４】
本実施の形態３の部分画像特徴値計算の概略を図２０に従って説明する。図２０は、画像の部分画像に対し、水平方向および垂直方向を代表する画素列、即ち、本実施の形態では、水平方向についてはｙ＝７の画素列、垂直方向についてはｘ＝７の画素列についての画素値の変化の回数などを示す図である。この図での部分画像は、水平方向、垂直方向ともに画素数１６である１６画素×１６画素の部分領域で構成されている。
【０１５５】
本実施の形態３による部分画像特徴値計算は、計算対象部分画像につき、水平方向の画素値の変化数hcntと垂直方向の画素値の変化数vcntとを求め、求めた水平方向の画素値の変化数hcntと垂直方向の画素値の変化数vcntとを比較し、相対的に画素値の変化数が大きい方向が垂直方向ならば、水平を意味する値“Ｈ”を、水平方向ならば垂直を意味する値“Ｖ”を、その他の場合には“Ｘ”を出力する。
【０１５６】
但し、上記で“Ｈ”あるいは“Ｖ”と判定された場合でも、画素値の変化数があらかじめ両方向に対して設定している画素値変化判定の下限値cnt0未満であれば “Ｘ”を出力する。尚、画素値変化判定の下限値cnt0が少ない場合は、部分画像内の模様の変化の絶対値が小さいことを示し、最も極端な場合であるcnt0=0の場合とは、部分領域全体に値があるか無いかいずれかであり、水平・垂直の判断を行わないことが現実的である。これら条件を数式を用いて表現すると、hcnt＜vcntかつmax(hcnt、vcnt)≧cnt0ならば“Ｈ”を出力し、hcnt＞vcntかつmax(hcnt、vcnt)≧cnt0ならば“Ｖ”を出力し、その他ならば“Ｘ”を出力するとなる。
【０１５７】
図２１には実施の形態３による部分画像特徴値計算処理のフローチャートが示される。このフローチャートは計算対象となる参照用メモリ１０２１の参照画像のｎ個の部分画像Ｒｉについてそれぞれ繰返されて、計算結果値は各部分画像Ｒｉ毎に対応付けて参照用部分画像特徴値計算結果メモリ１０２４に格納される。同様に取込み画像用メモリ１０２４の取込画像のｎ個の部分画像Ｒｉについてそれぞれ繰返されて、計算結果値は各部分画像Ｒｉ毎に対応付けて取込画像用部分画像特徴値計算結果メモリ１０２５に格納される。次に、この部分画像特徴値計算処理の詳細を図２１のフローチャートに従って説明する。
【０１５８】
制御部１０８は、部分画像特徴値計算部１０４５に部分画像特徴値計算開始信号を送り、その後、部分画像特徴値計算終了信号を受信するまで待機する。部分画像特徴値計算部１０４５は、計算対象画像の部分画像Ｒiを参照用メモリ１０２１ないしは取込画像用メモリ１０２３から読出し、計算用メモリ１０２２に一旦格納する（ステップＳＳ１）。
【０１５９】
部分画像特徴値計算部１０４５は格納された部分画像Ｒｉを読出し、水平方向の画素値の変化数hcntと垂直方向の画素値の変化数vcntとを求める(ステップＳＳ２)。ここで、水平方向の画素値の変化数hcntと垂直方向の画素値の変化数vcntとを求める処理を、図２２、図２３に基づいて説明する。
【０１６０】
図２２は、本発明の実施の形態３による部分画像特徴値計算処理(ステップＴ２ａ)内の水平方向の画素値の変化数hcntを求める処理(ステップＳＳ２)のフローチャートである。図２２を参照して、部分画像特徴値計算部１０４５は、計算用メモリ１０２２から部分画像Ｒｉを読出すとともに、水平方向の画素値の変化数hcntを初期化、即ちhcnt＝０とするとともに、水平方向を代表する画素列の座標ｊ、即ち本実施の形態では、y軸上の最大座標値nの2分の１を小数点以下切り捨てたｊ＝TRUNC(n/2)とする。具体的な値は、TRUNC(15/2)＝７とする(ステップSH101）。
【０１６１】
次に、ｘ軸方向の座標値を表現するパラメータiと画素値を表現するパラメータcを初期化、即ちi＝０、ｃ＝０とする(ステップSH102）。
【０１６２】
次に、ｘ軸方向の座標値を表現するパラメータiとｘ軸方向の最大座標値ｍとを比較（ステップSH103）し、i≧mならば次にステップSH108を実行し、その他ならば次にステップSH104を実行する。本実施の形態３ではm=15であり、かつ処理開始時にはi=0であるためステップSH104に進む。
【０１６３】
次に、pixel(i、j)と画素値を表現するパラメータcとを比較し、c＝pixel(i、j)ならば次にステップSH107を実行し、その他ならば次にステップSH105を実行する。現在、i=0、j=7であり、図２０を参照して、この座標でのpixel(0、7)=0であるので、cと等しく次にステップSH107に進む。
【０１６４】
ステップSH107では、ｘ軸方向の座標値を表現するパラメータiの座標値が1増加され、ステップSH103に進む。以降上記と同様の処理がi=1〜4の間行われた上で、i=5の状態で再度ステップSH103に進む。この状態では、i≧mであるのでステップSH104に進む。
【０１６５】
次に、pixel(i、j)と画素値を表現するパラメータcとを比較し、c＝pixel(i、j)ならば次にステップSH107を実行し、その他ならば次にステップSH105を実行する。現在、i=5、j=7、c＝0であり、図２０を参照して、この座標でのpixel(5、7)=１であるので、次にステップSH105に進む。
【０１６６】
次に、ステップSH105で、水平方向の画素値が変化したことに伴い、hcntを１増加させた上で、更に画素値の変化を検知するために、現在の画素値pixel(5、7)=１を画素値を表現するパラメータcに入力する（ステップSH106)。
【０１６７】
次に、ステップSH107では、ｘ軸方向の座標値を表現するパラメータiの座標値が1増加され、i=6とされた上で、ステップSH103に進む。
【０１６８】
以降、i=6〜15の間は、上記ステップSH103→SH104→SH107の処理が同様に行われ、i=16となった時点で、ステップSH103でi≧mとなるため、次にステップSH108、即ち、hcnt=1が出力される。
【０１６９】
次に、図２３の本発明の実施の形態３による部分画像特徴値計算処理(ステップＴ２ａ)内の垂直方向の画素値の変化数vcntを求める処理(ステップＳＳ２)のフローチャートについて説明するが、図２３は、上記に説明した図２２のフローチャートと基本的に同じ処理を行うことが明らかであり、詳細な説明は省略する。
【０１７０】
出力される水平方向の画素値の変化数hcnt、垂直方向の画素値の変化数vcntは、図２０の通り、hcnt＝1、vcnt＝7である。出力されたhcntとvcntとが以降処理される内容を図２１のステップＳＳ３以降に戻って説明する。
【０１７１】
ステップＳＳ３では、hcntとvcnt、および、cnt0とから、max(hcnt、vcnt)≧cnt0かつhcnt≠vcntであるか比較する。現時点では、hcnt＝1、vcnt＝7であり、cnt0を2と設定すれば、次にステップＳＳ４に進み、ステップＳＳ４のhcnt＜vcntを満たすため、次にステップＳＳ７に進み、参照用部分画像特徴値計算結果メモリ１０２４、あるいは、取込画像用部分画像特徴値計算結果メモリ１０２５の元画像に対する部分画像Ｒｉの特徴値格納領域に“Ｈ”を出力して、制御部１０８に部分画像特徴値計算終了信号を送る。
【０１７２】
仮にステップＳＳ２の出力値が、hcnt＝7、vcnt＝1、cnt0＝2であるならば、ステップＳＳ３の条件を満たし、ステップＳＳ４の条件を満たさないため、次にステップＳＳ６に進み、参照用部分画像特徴値計算結果メモリ１０２４、あるいは、取込画像用部分画像特徴値計算結果メモリ１０２５の元画像に対する部分画像Ｒｉの特徴値格納領域に“Ｖ”を出力して、制御部１０８に部分画像特徴値計算終了信号を送る。
【０１７３】
さらに、仮にステップＳＳ２の出力値が、hcnt＝7、vcnt＝７、cnt0＝2や、hcnt＝2、vcnt＝1、cnt0＝5であるならば、ステップＳＳ３の条件を満たさないため、次にステップＳＳ５に進み、参照用部分画像特徴値計算結果メモリ１０２４、あるいは、取込画像用部分画像特徴値計算結果メモリ１０２５の元画像に対する部分画像Ｒｉの特徴値格納領域に“Ｘ”を出力して、制御部１０８に部分画像特徴値計算終了信号を送る。
【０１７４】
以上のように本実施の形態３による部分画像特徴値計算部１０４５は、計算対象画像の部分画像Ｒｉ（図２０参照）について、水平方向および垂直方向を代表する画素列（図２０の破線矢印で示す画素列）を抽出（特定）して、抽出された画素列それぞれにおける画素値の変化（1→0、0→1）の回数に基づいて、該部分画像の模様が水平方向に従う模様である傾向（たとえば横縞である傾向）、または垂直方向に従う模様である傾向（たとえば縦縞である傾向）またはそのどちらでもないことを判別して、その判別結果に応じた値（“Ｈ”、“Ｖ”および“Ｘ”のいずれか）を出力する。この出力値が該部分画像の特徴値を示す。
【０１７５】
（実施の形態４）
部分画像特徴値計算の手順は上述の実施の形態１および２に従うものに限定されず、本実施の形態４のようであってもよい。
【０１７６】
本実施の形態４に係る部分画像特徴値計算の概略を図２４（Ａ）〜（Ｆ）に従って説明する。図２４（Ａ）〜（Ｆ）は、画像の部分画像Ｒｉに対し、黒画素と白画素の総数などを記載して示す図である。これらの図での部分画像Ｒｉは、水平方向、垂直方向ともに画素数１６である１６画素×１６画素の部分領域で構成されている。本実施の形態４による部分画像特徴値計算は、図２４（Ａ）の計算対象部分画像Ｒｉにつき、計算対象部分画像を左右に１画素ずつずらして重ねたときの黒画素数の増加量hcnt（すなわち図２４（Ｂ）の画像ＷＨｉのハッチング部分）と、計算対象部分画像を上下に１画素ずつずらして重ねたときの黒画素数の増加量vcnt（すなわち図２４（Ｃ）の画像ＷＶiのハッチング部分）とを求め、求めた左右にずらしたときの増加量hcntと上下にずらしたときの増加量vcntとを比較し、上下にずらしたときの増加量が左右にずらしたときの増加量の２倍より大きければ、水平を意味する値“Ｈ”を、左右にずらしたときの増加量が上下にずらしたときの増加量の２倍よりも大きければ、垂直を意味する値“Ｖ”を、その他の場合には“Ｘ”を出力する。ただし、上記で“Ｈ”あるいは“Ｖ”と判定された場合でも、黒画素数の増加量があらかじめ両方向に対して設定している下限値vcnt0ないしhcnt0以上でないならば“Ｘ”を出力する。これら条件を数式として表現すると、（１）vcnt＞2×hcntかつ（２）vcnt≧vcnt0ならば“Ｈ”を出力し、（３）hcnt＞2×vcntかつ（４）hcnt≧hcnt0ならば“Ｖ”を出力し、その他ならば“Ｘ”を出力するとなる。
【０１７７】
尚、本実施の形態４では、上下にずらしたときの増加量が左右にずらしたときの増加量の２倍より大きければ水平を意味する値“Ｈ”を出力しているが、この２倍という値を別の値に変更しても良い。左右方向についても同様である。さらに、部分領域の中で黒画素数がある範囲（例えば部分画像Ｒｉの全体画素数に対して３０％以上７０％以下など）にあり、照合処理に適する画像であることが予めわかっているような場合は、上記（２）と（４）の条件式については削除しても良い。
【０１７８】
図２５（Ａ）は、本発明の実施の形態４による部分画像特徴値計算処理のフローチャートである。このフローチャートは計算対象となる参照用メモリ１０２１の参照画像のｎ個の部分画像Ｒｉについてそれぞれ繰返されて、計算結果値は各部分画像Ｒｉ毎に対応付けて参照用部分画像特徴値計算結果メモリ１０２４に格納される。同様に取込み画像用メモリ１０２４の取込画像のｎ個の部分画像Ｒｉについてそれぞれ繰返されて、計算結果値は各部分画像Ｒｉ毎に対応付けて取込画像用部分画像特徴値計算結果メモリ１０２５に格納される。次に、この部分画像特徴値計算処理の詳細を図２５（Ａ）のフローチャートに従って説明する。
【０１７９】
制御部１０８は、部分画像特徴値計算部１０４５に部分画像特徴値計算開始信号を送り、その後、部分画像特徴値計算終了信号を受信するまで待機する。
【０１８０】
部分画像特徴値計算部１０４５は、計算対象画像の部分画像Ｒｉ（図２４（Ａ）参照）を参照用メモリ１０２１ないしは取込画像用メモリ１０２３から読出し、計算用メモリ１０２２に一旦格納する（ステップＳＴ１）。部分画像特徴値計算部１０４５は格納された部分画像Ｒｉを読出し、図２４（Ｂ）のように左右にずらしたときの増加量hcntと図２４（Ｃ）のように上下にずらしたときの増加量vcntとを求める（ステップＳＴ２）。
【０１８１】
左右にずらしたときの増加量hcntと上下にずらしたときの増加量vcntとを求める処理を、図２６と図２７に基づき説明する。図２６は、本発明の実施形態３による部分画像特徴値計算処理（ステップＴ２ａ）内の左右にずらしたときの増加量hcntを求める処理（ステップＳＴ２）のフローチャートである。
【０１８２】
図２６を参照して、部分画像特徴値計算部１０４５は、計算用メモリ１０２２から部分画像Ｒｉを読出すとともに、垂直方向の画素カウンタjを初期化、すなわち、j=0とする（ステップＳＨＴ０１）。次に、垂直方向の画素カウンタjと垂直方向の最大画素数nとを比較（ステップＳＨＴ０２）し、j＞nならば次にステップＳＨＴ１０を実行、その他ならば次にステップＳＨＴ０３を実行する。本実施の形態４ではn=15であり、かつ、処理開始時には、j=0であるためステップＳＨＴ０３に進む。
【０１８３】
ステップＳＨＴ０３では、水平方向の画素カウンタiの初期化、すなわち、i=0とする（ステップＳＨＴ０３）。次に、水平方向の画素カウンタiと水平方向の最大画素数mとを比較（ステップＳＨＴ０４）し、i＞mならば次にステップＳＨＴ０５を実行し、その他ならば次にステップＳＨＴ０６を実行する。本実施の形態１ではm=15であり、かつ、処理開始時には、i=0であるため、ステップＳＨＴ０６に進む。
【０１８４】
ステップＳＨＴ０６では、現在比較対象となっている座標(i、j)の画素値pixel(i、j)が１（黒画素）であるか、あるいは、座標(i、j)よりも水平方向に一つ左の座標(i-1、j)の画素値pixel(i-1、j)が１であるか、あるいは、座標(i、j)よりも水平方向に一つ右の座標(i+1、j)の画素値pixel(i+1、j)が１であるかを比較する。pixel(i、j)=１あるいはpixel(i-1、j)=１あるいはpixel(i+1、j)=１ならば、次にステップＳＨＴ０８を実行し、その他ならば次にステップＳＨＴ０７を実行する。
【０１８５】
ここで、部分画像Ｒｉの上下左右の1画素分の範囲、すなわち、Ri(-1〜m+1、-1)、Ri(-1、-1〜n+1)、Ri(m+1、-1〜n+1)、Ri(-1〜m+1、n+1)の範囲の画素値は、図２５（Ｂ）に示すように0（白画素）とする。本実施の形態４では、図２４（Ａ）を参照して、pixel(0、0)=0、pixel(-1、0)=0、pixel(1、0)=0であるため、ステップＳＨＴ０７へ進む。
【０１８６】
ステップＳＨＴ０７では、計算用メモリ１０２２に格納する左右に１画素ずつずらして重ねた画像WHiの座標(i、j)の画素値work(i、j)（図２５（Ｃ）参照）に0を格納する。すなわち、work(0、0)=0とする。次に、ステップＳＨＴ０９に進む。
【０１８７】
ステップＳＨＴ０９では、i=i+1、すなわち、水平方向の画素カウンタiを1増加させる。本実施の形態４では、初期化によりi=0となっており、1を付加されてi=1となる。次にステップＳＨＴ０４に戻る。以降、０行目の画素値、すなわち、pixel(i、0)は、図２４（Ａ）を参照して、すべて白画素で0であるため、i=15となるまで、ステップＳＨＴ０４〜ＳＨＴ０９を繰返すこととなり、ステップＳＨＴ０９処理後にi=15となる。この状態でＳＨＴ０４に進む。m=15、i=15であるのでステップＳＨＴ０５に進む。
【０１８８】
ステップＳＨＴ０５では、j=j+1、すなわち、垂直方向の画素カウンタjを1増加させる。現時点では、j=0であるので、j=1となり、ＳＨＴ０２に戻ることになる。ここで、新しい行の始まりであるので、０行目と同様に、ステップＳＨＴ０３、ステップＳＨＴ０４と進む。以降、pixel(i+1、j)=1となる１行目の１４列目の画素、すなわち、i=14、 j=1になるまでステップＳＨＴ０４〜ＳＨＴ０９を繰返すこととなり、ステップＳＨＴ０９処理後にi=14となる。m=15、i=14であるのでＳＨＴ０６に進む。
【０１８９】
ステップＳＨＴ０６では、pixel(i+1、j)=1、すなわち、pixel(14+1、1)=1であるので、ステップＳＨＴ０８に進む。
【０１９０】
ステップＳＨＴ０８では、計算用メモリ１０２２に格納する左右に１画素ずつずらして重ねた画像WHi（図２４（Ｂ）参照）の座標(i、j)の画素値work(i、j)に1を格納する。すなわち、work(14、1)=1とする。
【０１９１】
次に、ステップＳＨＴ０９に進み、i=15となって、ステップＳＨＴ０４へ進む。m=15、i=15であるので、ステップＳＨＴ０５に進み、j=2となって、ステップＳＨＴ０２へ進む。以降、j=2〜15について同様にステップＳＨＴ０２〜ＳＨＴ０９の処理を繰返し、ステップＳＨＴ０９の処理後、j=15となった時点で、次にステップＳＨＴ０２で、垂直方向の画素カウンタjと垂直方向の最大画素数nとを比較し、j＞nならば次にステップＳＨＴ１０を実行、その他ならば次にステップＳＨＴ０３を実行すると、現時点ではj=15、n=15であるので、次にステップＳＨＴ１０に進む。この時点で計算用メモリ１０２２には、現在比較対照を行っている部分画像Ｒｉを元に、図２４（Ｂ）に示すような左右に１画素ずつずらして重ねた画像WHiが格納されている。
【０１９２】
ステップＳＨＴ１０では、計算用メモリ１０２２に格納した左右に１画素ずつずらして重ねた画像WHiの画素値work(i、j)と現在比較対照を行っている部分画像Ｒｉの画素値pixel(i、j)の差分cntを計算する。このworkとpixelの差分cntを計算する処理を図２７に基づいて説明する。
【０１９３】
図２８は、現在比較対照を行っている部分画像Ｒｉの画素値pixel (i、j)と、部分画像Ｒｉを左右、あるいは上下に１画素ずつずらして重ねた画像WHiの画素値work(i、j)との差分cntを計算するフローチャートである。部分画像特徴値計算部１０４５は、計算用メモリ１０２２から部分画像Ｒｉと１画素ずつずらして重ねた画像WHiを読出すとともに、差分カウンタcntと垂直方向の画素カウンタjとを初期化、すなわちcnt=0、j=0とする（ステップＳＣ００１）。次に、垂直方向の画素カウンタjと垂直方向の最大画素数nとを比較し（ステップＳＣ００２）、j＞nならば次に図２６のフローチャートに戻り、ステップＳＨＴ１１を実行し、その他ならば次にステップＳＣ００３を実行する。
【０１９４】
本実施の形態４ではn=15であり、かつ、処理開始時には、j=0であるためステップＳＣ００３に進む。ステップＳＣ００３では、水平方向の画素カウンタiの初期化、すなわち、i=0とする（ステップＳＣ００３）。次に、水平方向の画素カウンタiと水平方向の最大画素数mとを比較し（ステップＳＣ００４）、i＞mならば次にステップＳＣ００５を実行し、その他ならば次にステップＳＣ００６を実行する。本実施の形態１ではm=15であり、かつ、処理開始時には、i=0であるため、ステップＳＣ００６に進む。
【０１９５】
ステップＳＣ００６では、現在比較対象となっている座標(i、j)の部分画像Ｒｉの画素値pixel(i、j)が0（白画素）であり、かつ、１画素ずつずらして重ねた画像WHiの画素値work(i、j)が1（黒画素）であるかを判別し、pixel(i、j)=0かつwork(i、j)=1ならば次にステップＳＣ００７を実行し、その他ならば次にステップＳＣ００８を実行する。本実施の形態４では、図２４（Ａ）と図２４（Ｂ）を参照して、pixel(0、0)=0、work(0、0)=0であるため、ステップＳＣ００９へ進む。
【０１９６】
ステップＳＣ００８では、i=i+1、すなわち、水平方向の画素カウンタiを1増加させる。本実施の形態４では、初期化によりi=0となっており、1を付加されてi=1となる。次にステップＳＣ００４に戻る。以降、０行目の画素値、すなわちpixel(i、0)とwork(i、0)は、図２４（Ａ）と図２４（Ｂ）を参照して、すべて白画素で0であるため、i=15となるまで、ステップＳＣ００４〜ＳＣ００８を繰返すこととなり、ステップＳＣ００８処理後にi=15となった時点での各々の値は、cnt=0、i=15となっている。この状態でＳＣ００４に進む。m=15、i=15であるので、ステップＳＣ００５に進む。
【０１９７】
ステップＳＣ００５ではj=j+1、すなわち、垂直方向の画素カウンタjを1増加させる。現時点では、j=0であるので、j=1となり、ＳＣ００２に戻ることになる。ここで、新しい行の始まりであるので、０行目と同様に、ステップＳＣ００３、ステップＳＣ００４と進む。以降、pixel(i、j)=0、かつ、work(i、j)=1となる１行目の１４列目の画素、すなわち、i=14、j=1になるまでステップＳＣ００４〜ＳＣ００８を繰返すこととなり、ステップＳＣ００８処理後にi=14となる。m=15、i=14であるのでＳＣ００６に進む。
【０１９８】
ステップＳＣ００６では、pixel(i、j)=0かつwork(i、j)=1、すなわち、pixel(14、1)=0かつwork(14、1)=1であるので、ステップＳＣ００７に進む。
【０１９９】
ステップＳＣ００７では、cnt=cnt+1、すなわち差分カウンタcntを1増加させる。本実施の形態３では、初期化によりcnt=0となっており、1を付加されてcnt=1となる。次に、ステップＳＣ００８に進み、i=15となってステップＳＣ００４へ進む。m=15、i=15であるので、ステップＳＣ００５に進み、j=2となってステップＳＣ００２へ進む。
【０２００】
以降、j=2〜15について同様にステップＳＣ００２〜ＳＣ００９の処理を繰返し、ステップＳＣ００８処理後、j=15となった時点で、次にステップＳＣ００２で、垂直方向の画素カウンタjと垂直方向の最大画素数nとを比較し、j＞nならば次に図２６のフローチャートに戻り、ステップＳＨＴ１１を実行し、その他ならば次にステップＳＣ００３を実行すると、現時点では、j=15、n=15であるので、図２８のフローチャートを終了し、次に図２６のフローチャートに戻り、ステップＳＨＴ１１に進む。現時点では、差分カウンタcnt=21となっている。
【０２０１】
ステップＳＨＴ１１では、hcnt=cnt、すなわち左右にずらしたときの増加量hcntに図２８のフローチャートで計算した差分cntの値を代入する。次にステップＳＨＴ１２に進む。ステップＳＨＴ１２では、左右にずらしたときの増加量hcnt=21を出力する。
【０２０２】
次に、図２７の、本発明の実施の形態４による部分画像特徴値計算処理（ステップＴ２ａ）内の上下にずらしたときの増加量vcntを求める処理（ステップＳＴ２）のフローチャートについて説明するが、図２７は、上記に説明した図２６のフローチャートと基本的に同じ処理を行うことが明らかであり、詳細な説明は省略する。
【０２０３】
出力される上下にずらしたときの増加量vcntは、図２４（Ｃ）の上下に１画素ずつずらして重ねた画像WViと図２４（Ａ）の部分画像Ｒｉとの差分である96が出力される。
【０２０４】
出力されたhcntとvcntとが以降処理される内容を図２５のステップＳＴ３以降に戻って説明する。
【０２０５】
ステップＳＴ３では、hcntとvcnt、および、上下方向の最大黒画素数増加量下限値vcnt0とを比較し、vcnt＞2×hcntかつvcnt≧vcnt0ならば次にステップＳＴ７を実行し、その他ならば次にステップＳＴ４を実行する。現時点では、vcnt=96、hcnt=21であり、vcnt0=4と設定すれば、次にステップＳＴ７に進み、参照用部分画像特徴値計算結果メモリ１０２４、あるいは、取込画像用部分画像特徴値計算結果メモリ１０２５の元の画像に対する部分画像Ｒｉの特徴値格納領域に“Ｈ”を出力して、制御部１０８に部分画像特徴値計算終了信号を送る。
【０２０６】
仮に、ステップＳＴ２の出力値が、vcnt=30、hcnt=20であり、vcnt0=4であるならば、次にステップＳＴ４に進み、hcnt＞2×vcntかつhcnt≧hcnt0ならば次にステップＳＴ５を実行し、その他ならば、次にステップＳＴ６を実行する。
【０２０７】
ここでは次にステップＳＴ６に進み、参照用部分画像特徴値計算結果メモリ１０２４、あるいは、取込画像用部分画像特徴値計算結果メモリ１０２５の元の画像に対する部分画像Ｒｉの特徴値格納領域に“Ｘ”を出力し、制御部１０８に部分画像特徴値計算終了信号を送る。
【０２０８】
さらに、仮にステップＳＴ２の出力値が、vcnt=30、hcnt=70であり、hcnt0=4であるならば、ステップＳＴ３で、vcnt＞2×hcntかつvcnt≧vcnt0ならば、次にステップＳＴ７を実行し、その他ならば、次にステップＳＴ４を実行する。
【０２０９】
ここでは、次にステップＳＴ４に進み、hcnt＞2×vcntかつhcnt≧hcnt0ならば次にステップＳＴ５を実行し、その他ならば次にステップＳＴ６を実行する。
【０２１０】
ここでは次にステップＳＴ５に進み、参照用部分画像特徴値計算結果メモリ１０２４、あるいは、取込画像用部分画像特徴値計算結果メモリ１０２５の元の画像に対する部分画像Ｒｉの特徴値格納領域に“Ｖ”を出力し、制御部１０８に部分画像特徴値計算終了信号を送る。
【０２１１】
本実施の形態４における部分画像特徴値計算は、参照画像、あるいは、取込画像にノイズがある場合、例えば、参照画像あるいは取込画像が指紋である場合、指のしわ等によって画像の一部が欠けているために、図２４（Ｄ）に示すように部分画像Ｒｉの中央に垂直にしわが入っているような画像であっても、図２４（Ｅ）、図２４（Ｆ）に示すように、hcnt=31、vcnt=91となって、vcnt0=4と設定すれば、図２５のステップＳＴ３で、vcnt＞2×hcntかつvcnt≧vcnt0ならば次にステップＳＴ７を実行し、水平を意味する値“Ｈ”を出力する。このように本実施の形態４における部分画像特徴値計算は、画像に含まれるノイズ成分に対して計算精度を維持できるという特徴を持つ。
【０２１２】
上述のように本実施の形態４に係る部分画像特徴値計算部１０４５は、部分画像Ｒｉについて、左右に所定の画素ずつずらして重ねた画像ＷＨｉと、上下に所定の画素ずつずらして重ねた画像ＷＶｉとを各々求め、さらに、その左右に１画素ずつずらして重ねた画像ＷＨｉと部分画像Ｒｉとの差分である黒画素数の増加量hcntと、上下に１画素ずつずらして重ねた画像ＷＶｉと部分画像Ｒｉとの差分である黒画素数の増加量vcntとを各々求め、それら増加量に基づいて、該部分画像Ｒｉの模様が水平方向に従う模様である傾向（たとえば横縞である傾向）、または垂直方向に従う模様である傾向（たとえば縦縞である傾向）またはそのどちらでもないことを判別して、その判別結果に応じた値（“Ｈ”、“Ｖ”および“Ｘ”のいずれか）を出力する。この出力値が該部分画像Ｒｉの特徴値を示す。
【０２１３】
（実施の形態５）
以上説明した画像照合のための処理機能は、プログラムで実現される。本実施の形態５では、このプログラムはコンピュータで読取可能な記録媒体に格納される。
【０２１４】
本実施の形態５では、この記録媒体として、図２に示されているコンピュータで処理が行なわれるために必要なメモリ、たとえばメモリ６２４のようなそのものがプログラムメディアであってもよいし、また該コンピュータの外部記憶装置に着脱自在に装着されて、そこに記録されたプログラムが該外部記憶装置を介して読取り可能な記録媒体であってもよい。このような外部記憶装置としては、磁気テープ装置（図示せず）、ＦＤ駆動装置６３０およびＣＤ−ＲＯＭ駆動装置６４０などであり、該記録媒体としては磁気テープ（図示せず）、ＦＤ６３２およびＣＤ−ＲＯＭ６４２などである。いずれの場合においても、各記録媒体に記録されているプログラムはＣＰＵ６２２がアクセスして実行させる構成であってもよいし、あるいはいずれの場合もプログラムが該記録媒体から一旦読出されて図２の所定のプログラム記憶エリア、たとえばメモリ６２４のプログラム記憶エリアにロードされて、ＣＰＵ６２２により読出されて実行される方式であってもよい。このロード用のプログラムは、予め当該コンピュータに格納されているものとする。
【０２１５】
ここで、上述の記録媒体はコンピュータ本体と分離可能に構成される。このような記録媒体としては、固定的にプログラムを担持する媒体が適用可能である。具体的には、磁気テープやカセットテープなどのテープ系、ＦＤ６３２や固定ディスク６２６などの磁気ディスク、ＣＤ−ＲＯＭ６４２／ＭＯ（Magnetic  Optical Disc）／ＭＤ（Mini  Disc）／ＤＶＤ（Digital Versatile  Disc）などの光ディスクのディスク系、ＩＣカード（メモリカードを含む）／光カードなどのカード系、マスクＲＯＭ、ＥＰＲＯＭ（Erasable  and Programmable ＲＯＭ）、ＥＥＰＲＯＭ(Electrically ＥＰＲＯＭ)、フラッシュＲＯＭなどによる半導体メモリが適用可能である。
【０２１６】
また、図２のコンピュータはインターネットを含む通信ネットワーク３００と通信接続可能な構成が採用されているから、通信ネットワーク３００からプログラムがダウンロードされて流動的にプログラムを担持する記録媒体であってもよい。なお、通信ネットワーク３００からプログラムがダウンロードされる場合には、ダウンロード用プログラムは予め当該コンピュータ本体に格納されていてもよく、あるいは別の記録媒体から予め当該コンピュータ本体にインストールされてもよい。
【０２１７】
なお記録媒体に格納されている内容としてはプログラムに限定されず、データであってもよい。
【０２１８】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【０２１９】
【図１】本発明の各実施の形態に係る画像照合装置のブロック図である。
【図２】本発明の画像照合装置が搭載されるコンピュータの構成図である。
【図３】本発明による画像照合装置で２つの画像を照合する手順のフローチャートである。
【図４】本発明の実施の形態１による部分画像特徴値計算の概要を説明する図である。
【図５】本発明の実施の形態１による部分画像特徴値計算処理のフローチャートである。
【図６】本発明の実施の形態１による部分画像の水平方向の最大連続黒画素数を求める処理のフローチャートである。
【図７】本発明の実施の形態１による部分画像の垂直方向の最大連続黒画素数を求める処理のフローチャートである。
【図８】本発明の実施の形態１による類似度計算処理のフローチャートである。
【図９】（Ａ）〜（Ｃ）は本発明による実施の形態１による照合処理の具体例を説明するための図である。
【図１０】（Ａ）〜（Ｃ）は本発明による実施の形態１による照合処理の具体例を説明するための図である。
【図１１】（Ａ）〜（Ｆ）は本発明による実施の形態１による照合処理の具体例を説明するための図である。
【図１２】本発明の実施の形態２による画像照合装置の構成図である。
【図１３】本発明の実施の形態２による画像照合処理のフローチャートである。
【図１４】本発明の実施の形態２による類似度計算・照合・判定の処理フローチャートである。
【図１５】本発明の実施の形態２による画像カテゴリ判定計算処理のフローチャートである。
【図１６】本発明の実施の形態２によるテーブルＴＢ１の内容例を示す図である。
【図１７】（Ａ）〜（Ｆ）は本発明の実施の形態２によるマクロ部分画像を用いたカテゴリ判定を説明するための図である。
【図１８】（Ａ）〜（Ｅ）は本発明の実施の形態２によるカテゴリ判定計算の一例を説明するための図である。
【図１９】（Ａ）〜（Ｅ）は本発明の実施の形態２によるカテゴリ判定計算の他の例を説明するための図である。
【図２０】本発明の実施の形態３による画像特徴値計算処理の概要を示す図である。
【図２１】本発明の実施の形態３による部分画像特徴値計算処理のフローチャートである。
【図２２】本発明の実施の形態３による部分画像の水平方向の画素値の変化数を求める処理のフローチャートである。
【図２３】本発明の実施の形態３による部分画像の垂直方向の画素値の変化数を求める処理のフローチャートである。
【図２４】（Ａ）〜（Ｆ）は本発明の実施の形態４による画像特徴値計算処理の概要を示す図である。
【図２５】（Ａ）〜（Ｃ）本発明の実施の形態４による部分画像特徴値計算処理のフローチャートと参照する部分画像を示す図である。
【図２６】本発明の実施の形態４による部分画像の左右にずらしたときの増加量を求める処理のフローチャートである。
【図２７】本発明の実施の形態４による部分画像の上下にずらしたときの増加量を求める処理のフローチャートである。
【図２８】本発明の実施の形態４による部分画像を元に上下、左右にずらした画像と元の部分画像との画素値の差分を求める処理のフローチャートである。
【図２９】（Ａ）と（Ｂ）は従来技術である画像間マッチング方法を示す図である。
【図３０】従来技術である画像特徴量マッチング方法を示す図である。
【図３１】従来技術に用いられる画像特徴であるマニューシャを示す模式図である。
【符号の説明】
【０２２０】
１  画像照合装置、１１  照合処理部、１０１  画像入力部、１０２  メモリ、１０３
バス、１０４  画像補正部、１０４７  画像カテゴリ判定部、１０５  最大一致度位置探索部、１０６  移動ベクトルに基づく類似度計算部、１０７  照合判定部、１０８  制御部、１０４５  部分画像特徴値計算部、Ｒｉ  部分画像。
【図１】
2005149455.tif 000004
【図２】
2005149455.tif 000005
【図３】
2005149455.tif 000006
【図４】
2005149455.tif 000007
【図５】
2005149455.tif 000008
【図６】
2005149455.tif 000009
【図７】
2005149455.tif 000010
【図８】
2005149455.tif 000011
【図９】
2005149455.tif 000012
【図１０】
2005149455.tif 000013
【図１１】
2005149455.tif 000014
【図１２】
2005149455.tif 000015
【図１３】
2005149455.tif 000016
【図１４】
2005149455.tif 000017
【図１５】
2005149455.tif 000018
【図１６】
2005149455.tif 000019
【図１７】
2005149455.tif 000020
【図１８】
2005149455.tif 000021
【図１９】
2005149455.tif 000022
【図２０】
2005149455.tif 000023
【図２１】
2005149455.tif 000024
【図２２】
2005149455.tif 000025
【図２３】
2005149455.tif 000026
【図２４】
2005149455.tif 000027
【図２５】
2005149455.tif 000028
【図２６】
2005149455.tif 000029
【図２７】
2005149455.tif 000030
【図２８】
2005149455.tif 000031
【図２９】
2005149455.tif 000032
【図３０】
2005149455.tif 000033
【図３１】
2005149455.tif 000034