JP5031641B2

JP5031641B2 - パターンの位置合わせ方法、照合方法及び照合装置

Info

Publication number: JP5031641B2
Application number: JP2008093476A
Authority: JP
Inventors: 智晴鈴木; 真一江口
Original assignee: Fujitsu Ltd; Fujitsu Frontech Ltd
Current assignee: Fujitsu Ltd; Fujitsu Frontech Ltd
Priority date: 2008-03-31
Filing date: 2008-03-31
Publication date: 2012-09-19
Anticipated expiration: 2028-03-31
Also published as: EP2107507B1; JP2009245347A; US20090245593A1; US8229250B2; EP2107507A1; DE602009000816D1

Description

本発明は、照合のため、線状パターン同士を位置合わせするパターンの位置合わせ方法、照合方法及び照合装置に関し、特に、多数の登録された線状パターンに対し、照合用線状パターンを高速に照合するのに好適なパターンの位置合わせ方法、照合方法及び照合装置に関する。

自動認識の分野において、登録されたパターンと照合用パターンとの照合により、自動認識することが行われている。近年のパターンの多様化に伴い、高速に位置合わせできる技術が要求されている。例えば、近年のバイオメトリックス技術の進展に伴い、人間の体の一部である生体の特徴を認識して、個人認証する装置が種々提供されている。このような装置では、登録されたテンプレートに対し、照合用パターンを位置合わせした後、照合している。例えば、手足の指紋、目の網膜、顔面、血管などのパターンを、登録パターンと照合することにより、個人認証する。

このような照合処理において、位置合わせの処理時間、精度は、照合処理の処理時間や精度に大きく影響する。

従来、パターンの位置合わせ技術として、テンプレートマッチング法が種々提案されている（例えば、非特許文献１、特許文献１，２参照）。テンプレートマッチング法は、比較元パターンをテンプレートとし、比較先パターンをテンプレートに当てはめる演算を行うものであり、アフィン変換等が利用される。

又、他のパターン位置合わせ技術として、対応関係と最小二乗法による方法も提案されている（例えば、非特許文献２参照）。この方法は、パターンの対応関係に、ハンガリアンメソッドなどを使用し、予測に基づき最適な位置合わせを決定する方法である。
W.Rucklidge、"Efficient Visual Recognition Using the Hausdrff Distance", Lecture Notes in Computer Science 1173, Springer-Verlag, 1996 特開２００３−３０６６２号公報特開平５−２３３７９６号公報 S. Belongie, J. Malik, J.Puzicha、"Shape Matching and Object Recognition Using Shape Contexts", IEEE, Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 24, PP 509-522, April, 2002

しかしながら、従来のテンプレートに基づく方法では、パターンをそのままテンプレートマッチングするため、位置あわせの幾何変換パラメータ数が多い。この幾何変換パラメータが増えるほど、処理時間が指数関数的に増加して、処理時間が長くなるという問題がある。又、大域的な誤差が大きいという問題がある。

一方、対応関係と最小２乗法による方法では、対応関係の算出に、例えば、ハンガリアン法などを要し、処理時間が長くなり、且つ局所的な誤差が大きいという問題がある。

従って、本発明の目的は、線状パターンを高速に位置合わせするためのパターンの位置合わせ方法、照合方法及び照合装置を提供することにある。

又、本発明の他の目的は、多数の線状パターンを高速の位置合わせするためのパターンの位置合わせ方法、照合方法及び照合装置を提供することにある。

更に、本発明の更に他の目的は、多数の線状パターンを高速且つ高精度に位置合わせするためのパターンの位置合わせ方法、照合方法及び照合装置を提供することにある。

この目的の達成のため、本発明のパターン位置合わせ方法は、比較元の第１の曲線と比較先の第２の曲線との各々を、複数の線分データに分割するステップと、前記第１の曲線の線分データと前記第２の曲線の線分データとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算する第１のステップと、前記第１の曲線の線分データと前記第２の曲線の線分データとの角度とスケールとから、前記第１の曲線と前記第２の曲線との角度ずれを計算する第２のステップと、前記第１の曲線の線分データと前記第２の曲線の線分データとの中点Ｘ座標と中点Ｙ座標とから、前記第１の曲線と前記第２の曲線とのスケールの比率を計算する第３のステップと、前記第１の曲線又は前記第２の曲線のいずれか一方を、前記角度と比率とで、角度・スケール変換する第４のステップと、前記角度・スケール変換された前記第１の曲線又は前記第２の曲線と、角度・スケール変換されていない前記第１の曲線又は前記第２の曲線とをテンプレートマッチングにより、位置合わせする第５のステップとを有し、前記第２のステップは、前記第１の曲線の線分データのスケールを角度の度数とした第１の角度分布と、前記第２の曲線の線分データのスケールを角度の度数とした第２の角度分布とを生成するステップと、前記第１及び第２の角度分布から前記角度ずれを計算するステップとを有し、前記第３のステップは、前記第１の曲線の線分データと前記第２の曲線の線分データとの中点Ｘ座標と中点Ｙ座標とから、前記第１の曲線と前記第２の曲線との各々のスケールシェイプコンテクストを計算するステップと、前記各々のスケールシェイプコンテクストの各要素の平均値の比から前記スケールの比率を計算するステップとを有する。

又、本発明のパターン照合方法は、比較元の第１の曲線と比較先の第２の曲線との各々を、複数の線分データに分割するステップと、前記第１の曲線の線分データと前記第２の曲線の線分データとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算する第１のステップと、前記第１の曲線の線分データと前記第２の曲線の線分データとの角度とスケールとから、前記第１の曲線と前記第２の曲線との角度ずれを計算する第２のステップと、前記第１の曲線の線分データと前記第２の曲線の線分データとの中点Ｘ座標と中点Ｙ座標とから、前記第１の曲線と前記第２の曲線とのスケールの比率を計算する第３のステップと、前記第１の曲線又は前記第２の曲線のいずれか一方を、前記角度と比率とで、角度・スケール変換する第４のステップと、前記角度・スケール変換された前記第１の曲線又は前記第２の曲線と、角度・スケール変換されていない前記第１の曲線又は前記第２の曲線とをテンプレートマッチングにより、位置合わせする第５のステップと、前記位置合わせした前記第１の曲線と前記第２の曲線との類似度を計算して、照合するステップとを有し、前記第２のステップは、前記第１の曲線の線分データのスケールを角度の度数とした第１の角度分布と、前記第２の曲線の線分データのスケールを角度の度数とした第２の角度分布とを生成するステップと、前記第１及び第２の角度分布から前記角度ずれを計算するステップとを有し、前記第３のステップは、前記第１の曲線の線分データと前記第２の曲線の線分データとの中点Ｘ座標と中点Ｙ座標とから、前記第１の曲線と前記第２の曲線との各々のスケールシェイプコンテクストを計算するステップと、前記各々のスケールシェイプコンテクストの各要素の平均値の比から前記スケールの比率を計算するステップとを有する。

又、本発明のパターン照合装置は、比較先パターンを取得する取得ユニットと、比較元パターンと前記比較先パターンとを照合する照合ユニットとを有し、前記照合ユニットは、前記比較元パターンの第１の曲線と前記比較先パターンの第２の曲線との各々を、複数の線分データに分割し、前記第１の曲線の線分データと前記第２の曲線の線分データとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算し、前記第１の曲線の線分データと前記第２の曲線の線分データとの角度とスケールとから、前記第１の曲線の線分データのスケールを角度の度数とした第１の角度分布と、前記第２の曲線の線分データのスケールを角度の度数とした第２の角度分布とを生成し、前記第１及び第２の角度分布から、前記第１の曲線と前記第２の曲線との角度ずれを計算し、前記第１の曲線の線分データと前記第２の曲線の線分データとの中点Ｘ座標と中点Ｙ座標とから、前記第１の曲線と前記第２の曲線との各々のスケールシェイプコンテクストを計算し、前記各々のスケールシェイプコンテクストの各要素の平均値の比から、前記第１の曲線と前記第２の曲線とのスケールの比率を計算し、前記第１の曲線又は前記第２の曲線のいずれか一方を、前記角度と比率とで、角度・スケール変換し、前記角度・スケール変換された前記第１の曲線又は前記第２の曲線と、角度・スケール変換されていない前記第１の曲線又は前記第２の曲線とをテンプレートマッチングにより、位置合わせし、前記位置合わせした前記第１の曲線と前記第２の曲線との類似度を計算して、照合する。

更に、本発明は、好ましくは、前記第１のステップは、複数の前記比較元パターンと複数の前記比較先パターンとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算するステップを有し、前記第２のステップは、複数の前記比較元パターンと複数の前記比較先パターンとの各々の角度と、スケールから、前記角度ずれを計算するステップを有し、前記第３のステップは、複数の前記比較元パターンと複数の前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比率を計算するステップを有する。

更に、本発明は、好ましくは、比較元曲線パターンを線状の前記比較元パターンに変換するステップと、比較先曲線パターンを線状の前記比較先パターンに変換するステップを更に有する。

更に、本発明は、好ましくは、前記第２のステップは、前記比較元パターンのスケールを角度の度数とした第１の角度分布と、前記比較先パターンのスケールを角度の度数とした第２の角度分布とを作成するステップと、前記第１及び第２の角度分布から、前記角度ずれを計算するステップとを有する。

更に、本発明は、好ましくは、前記角度分布を作成するステップは、前記比較元パターン及び前記比較先パターンのスケールを、重み付け関数で重み付けして、前記度数に変換するステップを有する。

更に、本発明は、好ましくは、前記第３のステップは、前記比較元パターンと前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比較元パターンと前記比較先パターンの各々のスケールシェイプコンテクストを計算するステップと、前記各々のスケールシェイプコンテクストの各要素の平均値の比から前記スケールの比率を計算するステップとを有する。

更に、本発明は、好ましくは、前記第５のステップは、前記角度・スケール変換された前記比較元パターン又は前記比較先パターンを、前記角度・スケール変換されていない前記比較元パターン又は前記比較先パターンに平行移動位置合わせするステップを有する。

比較元パターンと比較先パターンの角度ずれ、スケールの比率を別々に演算し、角度・スケール変換した後、実測テンプレートマッチングを行うため、テンプレートマッチング処理を最小限とでき、高精度及び高速な位置合わせが可能となる。又、比較元及び比較先パターンの曲線を複数の線分データに分割するため、曲線を線分データの特徴に置き換えるため、その角度、スケール、中点Ｘ，Ｙ座標を容易に計算できる。更に、線分データの角度とスケールから、各曲線の角度分布を計算するため、曲線間の角度ずれを容易に計算できる。しかも、線分データの中点Ｘ，Ｙ座標からスケールシェイプコンテクストを計算し、スケールシェイプコンテクストの各要素の平均値の比から、第１の曲線と第２の曲線とのスケールの比率を計算するため、角度ずれと別にスケール比率を計算できる。

以下、本発明の実施の形態を、認証システム、位置合わせ処理、特徴変換処理、最適アフィン変換処理、他の実施の形態の順で説明する。

（認証システム）
図１は、本発明の一実施の形態の認証システムの構成図である。図１は、認証システムとして、血管パターン認証システムを例に示す。

認証システムは、血管パターン撮像装置１と、これに接続された処理装置２とから構成される。このシステムの動作を説明する。血管パターン認証を依頼した利用者は、血管パターン撮像装置（以下、撮像装置という）１に手をかざす。撮像装置１は、血管パターンを読み取り、処理装置２の血管像抽出処理により、その血管パターンが抽出され、血管パターンデータとして、生体データベースファイル（比較元データファイル）に登録（記憶）する。

利用者が、個人認証するため、撮像装置１に手をかざす。撮像装置１は、血管パターンを読み取り、処理装置２の血管像抽出処理により、その血管パターンが抽出される。処理装置２は、照合処理により、その血管パターンを血管パターンデータとして、生体データベースファイルに登録された血管パターンデータと照合し、本人確認する。

図１に示すように、処理装置２は、比較元データ取得処理１０と、比較元モデル処理１２，１４を行い、比較元データから曲線特徴を抽出する。又、処理装置２は、撮像装置１の撮像画像を取得する比較先データ取得処理２０と、比較先イメージ処理２２，２４を行い、比較先データから曲線特徴を抽出する。

血管パターン認証装置では、撮像装置１から血管画像を、データ取得処理２０で取得し、前処理２２で、その画像の関心領域（ＲＯＩ：ＲｅｇｉｏｎＯｆＩｎｔｅｒｅｓｔ）を抽出し、特徴抽出処理２４で、関心領域の画像のエッジ抽出を行い、エッジ抽出した画像を細線化処理し、細線化した画像から曲線特徴（図３参照）を抽出する。即ち、血管パターンは、曲線が大半であるため、血管パターンの曲線特徴（曲線）を抽出する。

同様に、処理装置２は、比較元血管画像を、データ取得処理１０で取得し、前処理１２で、その画像の関心領域を抽出し、特徴抽出処理１４で、関心領域の画像のエッジ抽出を行い、エッジ抽出した画像を細線化処理し、細線化した画像から曲線特徴（図３参照）を抽出する。尚、生体データベースには、この曲線特徴が登録され、ここでは、生体データベースへの登録処理を示す。

次に、処理装置２は、比較元曲線と比較先曲線の位置合わせ探索処理３を行う。探索処理３では、比較元特徴変換処理３０が、生体データベースの比較元曲線特徴から線分データを生成し、更に生成した線分データから線分特徴（角度、長さ、中点Ｘ座標，中点Ｙ座標）を抽出する。同様に、比較先特徴変換処理３２が、比較先曲線特徴から線分データを生成し、更に生成した線分データから線分特徴（角度、長さ、中点Ｘ座標，中点Ｙ座標）を抽出する。

次に、探索処理３では、最適アフィン変換の探索処理３４を行う。この探索処理３４では、比較元線分特徴と比較先線分特徴とから、２つの線分間の角度推定を角度ヒストグラムマッチングにより行い、次に、２つの線分間のスケール推定をＳｈａｐｅＣｏｎｔｅｘｔ法により行う。この角度θ、スケールＣを用いて、一方の曲線特徴の角度とスケール変換処理を行う。この角度・スケール変換された一方の曲線と、他方の曲線との並行移動位置合わせを、アフィン変換で行う。更に、最小二乗法により、アフィン変換のパラメータを微調整処理する。

更に、認証装置２は、認証処理４を実行する。即ち、位置合わせ処理４０で、位置合わせ探索処理３からのアフィン変換パラメータからパターンの重ね合わせを行う位置合わせ処理４０を行い、類似度の計算処理４２を実行し、類似度判定処理４４を実行する。類似度判定処理４４では、計算した類似度が、閾値以上なら、認証ＯＫ（成功）と、類似度が閾値より小さい場合には、認証ＮＧ（不成功）と判定する。

この平行移動位置合わせ処理とアフィン変換の微調整処理は、所謂、実測テンプレートマッチングに相当するが、この実施の形態では、直線の角度、スケールを演算し、角度・スケール変換した後、実測テンプレートマッチングを行う。このため、テンプレートマッチング処理を最小限とでき、高精度及び高速な位置合わせが可能となる。即ち、アフィン変換のパラメータを、６パラメータとすることができ、幾何変換パラメータを大幅に削減して、テンプレートマッチング処理できる。

又、対象直線を、角度、長さ、中点Ｘ座標，中点Ｙ座標という線分特徴に変換しているため、角度、スケール演算を別々に実行できる。このため、低次元の演算にばらして実行できる。このため、より高速化演算できる。更に、対象が曲線である場合には、曲線を直線近似して、直線間で、スケール、角度を推定しているため、低次元の演算ですむ。

（位置合わせ処理）
図２は、図１の位置合わせ探索処理フロー図、図３は、図２の処理の説明図である。図３を参照して、図２の位置合わせ探索処理を説明する。

（Ｓ１０）入力された図３の曲線特徴１００，２００を、線分近似により、線分データ１０２，２０２を生成する。ここでは、１つの曲線を２つの線分データに分割する。この処理は、図４、図５で詳しく説明する。

（Ｓ１２）次に、線分データから線分特徴を生成する。図３に示すように、線分データ１０２，２０２から、線分のスケール（長さ）ｌ，角度θ、各線分の中点のＸ座標、Ｙ座標という４次元データを生成し、スケール、角度１０４，２０４と、中点のＸ座標、Ｙ座標１０３，２０３に分類する。この処理は、図６で詳しく説明する。

（Ｓ１４）生成した線分の角度及びスケール（長さ）から、角度ヒストグラム１０５，２０５を生成する。即ち、各角度において、同一角度の線分の長さを累積し、角度ヒストグラム１０５，２０５を生成する。そして、２つの角度ヒストグラムのずれを角度推定処理３００で計算する。これにより、線分群の角度のずれが得られる。この処理は、図７、図８で詳しく説明する。

（Ｓ１６）生成した線分の中点のＸ座標、Ｙ座標とのユークリッド距離を計算し、比較元、比較先のスケールＳｈａｐｅＣｏｎｔｅｘｔ（行列）１０６，２０６を計算する。そして、スケール推定処理３０２が、比較元、比較先のＳｈａｐｅＣｏｎｔｅｘｔ（行列）１０６，２０６の各要素の平均値を計算し、比較先の平均値を比較元の平均値で割り、推定スケール値を計算する。この処理は、図９、図１０で詳しく説明する。

（Ｓ１８）角度・スケール変換処理２０７が、比較元の曲線特性を、計算した角度とスケールで、角度及びスケール変換する。この処理は、図１１、図１２で詳しく説明する。

（Ｓ２０）図３に示すように、比較元曲線２０８を、並行移動して、比較先曲線１０７に合わせる。この時の平行移動のアフィン変換の幾何変換パラメータは、４パラメータである。この処理は、図１３、図１４で詳しく説明する。

（Ｓ２２）図３に示すように、最小二乗法を用いて、アフィン変換パラメータを最適化（微修正）する。このアフィン変換パラメータが、重ね合わせの幾何変換パラメータであり、６パラメータで済む。この処理は、図１５、図１６で詳しく説明する。

このように、直線の角度、スケールを演算し、角度・スケール変換した後、実測テンプレートマッチングを行うため、テンプレートマッチング処理を最小限とでき、高精度及び高速な位置合わせが可能となる。

（特徴変換処理）
図２の特徴変換処理を、図４乃至図６で説明する。

図４は、図２の線分データ作成処理フロー図、図５は、図４の動作説明図である。図４は、曲線セグメントからなる集合Σに対して、各Ｓ∈Σに近似する線分を求め、それらの線分の総体としてΣ‘’を求める処理である。

（Ｓ１００）曲線セグメントＳの始点を“ｓ”、終点を、“ｅ”とし、始点ｓ、終点ｅを通る直線を、“ｌ”とする（図５参照）。そして、以下の条件式（１）を満たす場合に、中点ｐ’を下記（２）式で定め、曲線セグメントＳを、始点ｓ，終点ｐ’の曲線セグメントＳ’と、始点ｐ’、終点ｅの曲線セグメントＳ’ ’とに分割する（図５参照）。

ｍａｘｄ（ｐ，Ｌ）＞閾値Ｄ（１）
但し、ｐ∈Ｓである。

ｐ’＝ａｒｇｍａｘｄ（ｐ，Ｌ）（２）
但し、ｐ∈Ｓである。

（Ｓ１０２）曲線セグメントＳを、Ｓ’，Ｓ’ ’で置き換え、ステップＳ１００の処理を繰り返す。ステップＳ１００，Ｓ１０２を再帰的に処理し、式（１）が成立しなくなるまで、繰り返す。

（Ｓ１０４）ステップＳ１０２で得られた全ての曲線セグメントΣに対して、Ｌ（Ｓ）を、曲線セグメントＳの始点を、始点として、曲線セグメントＳの終点を、終点を持つ線分として、以下の式（３）で、線分からなる集団Σ’ ’を定める。

Σ’ ’＝｛Ｌ（Ｓ）｜Ｓ∈Σ’｝（３）
図６は、図２の線分特徴抽出処理フロー図である。この処理は、線分からなる集合Σ‘’を元に、４次元の線分特徴ｌ、θ、ｃｘ、ｃｙからなる集合Σ’ ’ ’を求める。即ち、線分毎に、長さｌ、角度θ、中点Ｘ座標ｃｘ，中点Ｙ座標ｃｙを計算する。線分特徴（ｌ、θ）１０４、線分特徴（ｃｘ、ｃｙ）を、線分特徴Σ’ ’ ’として出力する。

（最適アフィン変換処理）
図７は、図２の角度推定処理フロー図、図８は、図７の動作説明図である。

（Ｓ１４０）比較元、比較先の各々の（ｌ、θ、ｃｘ、ｃｙ）∈Σ’ ’ ’に対して、角度θの属する角度区分に対するｗ（ｌ）投票した重み付け度数分布を作成する。但し、重み関数は、非負単調増加関数である。図８に示すように、長さｌに対する重み関数ｗ（ｌ）を、長さｌが、０〜小さい領域では、「０」の度数、一定値より長い領域では、飽和値の度数、その間では、比例値の度数となるように設定する。この重み関数は、極端に短い線分は、角度推定から、カットし、極端に長い線分は、度数を制限するためである。その理由は、比較先線分は、撮像等の画像の読み取りから得られたものであり、極端に短い線分は、信頼性が少ない。同様に、極端に長い線分は、読み取り条件で、左右され、長さの信頼性が少ないからである。そして、線分の度数を、角度分布の対応角度θの度数に加算していく。

（Ｓ１４２）比較元度数分布（ヒストグラム）を、比較先度数分布（ヒストグラム）に対し、ずらしながら、相関を計算し、最も相関が高いときのずらし幅を、角度のずれθと推定する。

図９は、図２のスケール推定処理フロー図、図１０は、図９の動作説明図である。

（Ｓ１６０）図１０に示すように、中点Ｘ座標、中点Ｙ座標群から、比較元、比較先のＳＳＣ（Scale Shape Context）を、以下の式（４）、（５）により求める。

ＳＳＣ（Ｍｏｄｅｌ）＝［ｄ（Ｐ_ｉ，Ｐ_ｊ）］_ｉ，j （４）
ＳＳＣ（Ｉｍａｇｅ）＝［ｄ（Ｐ’_ｉ，Ｐ’_ｊ）］_ｉ，j （５）
但し、ｄは、ユークリッド距離である。

図１０で説明すると、比較元（Ｍｏｄｅｌ）の中点全体を、｛ｐ１、ｐ２、ｐ３、ｐ４｝とすると、行列ＳＳＣ（Ｍｏｄｅｌ）は、各点間のユークリッド距離を、行列化して、得る。同様に、比較先（Ｉｍａｇｅ）の中点全体を、｛ｑ１、ｑ２、ｑ３、ｑ４｝とすると、行列ＳＳＣ（Ｉｍａｇｅ）は、各点間のユークリッド距離を、行列化して、得る。

（Ｓ１６２）スケールＣを、行列Ａの各要素の平均値（ｍｅａｎ）を計算し、比較元で比較先を割り、下記式（６）で計算する。

Ｃ＝ｍｅａｎ（ＳＳＣ（Ｉｍａｇｅ））／ｍｅａｎ（ＳＳＣ（Ｍｏｄｅｌ））（６）
図１１は、図２の角度・スケール変換処理フロー図、図１２は、図１１の動作説明図である。角度推定値θ、スケール推定値Ｃを用いて、比較元の曲線パターンについて、スケール（拡大、縮小）、回転変換を行う。即ち、曲線パターンの各点ｘ、ｙを、下記式（７）、（８）で、変換後の点（ｘ‘、ｙ’）を計算する。

ｘ’＝（Ｃ・ｃｏｓθ）・ｘ＋（−Ｃ・ｓｉｎθ）・ｙ（７）
ｙ’＝（Ｃ・ｓｉｎθ）・ｘ＋（Ｃ・ｃｏｓθ）・ｙ（８）
図１２に示すように、原点を中心に、θ回転、Ｃ倍を行う。この時、アフィン変換のパラメータは、式（７）、（８）の４つである。

図１３は、図２の平行移動位置合わせ処理フロー図、図１４は、図１３の動作説明図である。

（Ｓ２００）探査路生成を行う。即ち、図１４に示すように、螺旋状に順序づけられた集合（Spiral Movement Vectors）Ｓ（＝｛Ｓｉ｝ｉ∈Ｎ ⊂ Ｒ＊Ｒ）を求める。

（Ｓ２０２）粗探査を行う。即ち、図１４に示すように、Ｎ（自然数全体）の部分集合Ｎ０を作成し、集合Ｓの部分列Ｓ０＝｛Ｓｉ｝ｉ∈Ｎ０をとる。図１４では、黒丸でＳ０構成点を示す。そして、各ｉに対し、回転・スケール変換後の比較元曲線２０７に対する比較先曲線１００の誤差評価関数値ｄｉｓｔ（曲線（Ｍｏｄｅｌ）＋ｓｉ，曲線（Ｉｍａｇｅ））を評価する。

評価関数値が、一定値未満の時は、早期受け入れ（Early Acceptance）として、処理を中断し、その時のＳｉ＝（ｄｘ，ｄｙ）を、平行移動量として、処理を終了する。

（Ｓ２０４）密探索を行う。誤差評価関数により一定閾値内の見込みのある、若しくは、粗い探査での最良の添え字Ｓｉの付近（見込みのある区間）で、密に添え字Ｓｉを移動させる。最も誤差評価関数ｄｉｓｔを最小とするｓｉ（ｄｘ，ｄｙ）を平行移動量とする。

このように、螺旋状に走査するととともに、粗いステップで探査（走査）し、見込みのある区間について、密に走査を行う。十分近いと判定した場合には、途中で処理を打ち切る。これにより、平行移動位置合わせを高速化できる。

図１５は、図２のファイン変換パラメータ最適化処理フロー図、図１６は、図１５の動作説明図である。比較元曲線特徴（回転変換、スケール変換、平行移動後）と比較先曲線特徴を入力し、変換後の比較元曲線パターンを、比較先曲線パターン上に重ね、誤差評価関数（重み付け誤差の累積）を最小とするアフィン変換パラメータを、最小二乗法で求める。ここでは、重みは、例えば、距離の逆数に比例する定数とする。

これにより、アフィン変換パラメータは、ｐ、ｑ、ｒ、ｓ、ｔ、ｕの６パラメータとなる。

このように、直線の角度、スケールを別々に、演算し、角度・スケール変換した後、実測テンプレートマッチングを行うため、テンプレートマッチング処理を最小限とでき、高速な位置合わせが可能となる。又、テンプレートマッチングを粗い走査を行い、見込みのある区間について、密に走査を行う。十分近いと判定した場合には、途中で処理を打ち切る。これにより、平行移動位置合わせを高速化できる。

更に、極端に短い線分をカットし、且つ極端に長い線分の度数を飽和値とするため、角度推定を正確にできる。このため、高精度に位置合わせできる。

（他の実施の形態）
前述の実施の形態では、認証システムを、血管パターン認証システムで説明したが、手のひらや甲や指の血管パターンや、手の掌紋等他の血管パターンの特徴を認証することや、指紋、顔面等の他の生体認証にも、適用できる。又、生体認証に限らず、他の線状パターンの位置合わせ、照合に適用できる。更に、曲線で説明したが、直線のみにも適用できる。

以上、本発明を実施の形態により説明したが、本発明の趣旨の範囲内において、本発明は、種々の変形が可能であり、本発明の範囲からこれらを排除するものではない。

尚、本発明は、以下の付記の事項を包含する。

（付記１）比較元パターンと比較先パターンとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算する第１のステップと、前記比較元パターンと前記比較先パターンとの角度とスケールとから、前記比較元パターンと前記比較先パターンとの角度ずれを計算する第２のステップと、前記比較元パターンと前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比較元パターンと前記比較先パターンのスケールの比率を計算する第３のステップと、前記比較元パターン又は前記比較先パターンを、前記角度と比率とで、角度・スケール変換する第４のステップと、前記角度・スケール変換された前記比較元パターン又は前記比較先パターンと、角度・スケール変換されていない前記比較元パターン又は前記比較先パターンとをテンプレートマッチングにより、位置合わせする第５のステップとを有することを特徴とパターンの位置合わせ方法。

（付記２）前記第１のステップは、複数の前記比較元パターンと複数の前記比較先パターンとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算するステップを有し、前記第２のステップは、複数の前記比較元パターンと複数の前記比較先パターンとの各々の角度と、スケールから、前記角度ずれを計算するステップを有し、前記第３のステップは、複数の前記比較元パターンと複数の前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比率を計算するステップを有することを特徴とする付記１のパターンの位置合わせ方法。

（付記３）比較元曲線パターンを線状の前記比較元パターンに変換するステップと、比較先曲線パターンを線状の前記比較先パターンに変換するステップを更に有することを特徴とする付記１のパターンの位置合わせ方法。

（付記４）前記第２のステップは、前記比較元パターンのスケールを角度の度数とした第１の角度分布と、前記比較先パターンのスケールを角度の度数とした第２の角度分布とを作成するステップと、前記第１及び第２の角度分布から、前記角度ずれを計算するステップとを有することを特徴とする付記１のパターンの位置合わせ方法。

（付記５）前記角度分布を作成するステップは、前記比較元パターン及び前記比較先パターンのスケールを、重み付け関数で重み付けして、前記度数に変換するステップを有することを特徴とする付記４のパターンの位置合わせ方法。

（付記６）前記第３のステップは、前記比較元パターンと前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比較元パターンと前記比較先パターンの各々のスケールシェイプコンテクストを計算するステップと、前記各々のスケールシェイプコンテクストの各要素の平均値の比から前記スケールの比率を計算するステップとを有することを特徴とする付記１のパターンの位置合わせ方法。

（付記７）前記第５のステップは、前記角度・スケール変換された前記比較元パターン又は前記比較先パターンを、前記角度・スケール変換されていない前記比較元パターン又は前記比較先パターンに平行移動位置合わせするステップを有することを特徴とする付記１のパターンの位置合わせ方法。

（付記８）比較元パターンと比較先パターンとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算する第１のステップと、前記比較元パターンと前記比較先パターンとの角度とスケールとから、前記比較元パターンと前記比較先パターンとの角度ずれを計算する第２のステップと、前記比較元パターンと前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比較元パターンと前記比較先パターンのスケールの比率を計算する第３のステップと、前記比較元パターン又は前記比較先パターンを、前記角度と比率とで、角度・スケール変換する第４のステップと、前記角度・スケール変換された前記比較元パターン又は前記比較先パターンと、角度・スケール変換されていない前記比較元パターン又は前記比較先パターンとをテンプレートマッチングにより、位置合わせする第５のステップと、前記位置合わせした前記比較元パターンと前記比較先パターンとの類似度を計算して、照合するステップとを有することを特徴とパターン照合方法。

（付記９）前記第１のステップは、複数の前記比較元パターンと複数の前記比較先パターンとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算するステップを有し、前記第２のステップは、複数の前記比較元パターンと複数の前記比較先パターンとの各々の角度と、スケールから、前記角度ずれを計算するステップを有し、前記第３のステップは、複数の前記比較元パターンと複数の前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比率を計算するステップを有することを特徴とする付記８のパターン照合方法。

（付記１０）比較元曲線パターンを線状の前記比較元パターンに変換するステップと、比較先曲線パターンを線状の前記比較先パターンに変換するステップを更に有することを特徴とする付記８のパターン照合方法。

（付記１１）前記第２のステップは、前記比較元パターンのスケールを角度の度数とした第１の角度分布と、前記比較先パターンのスケールを角度の度数とした第２の角度分布とを作成するステップと、前記第１及び第２の角度分布から、前記角度ずれを計算するステップとを有することを特徴とする付記８のパターン照合方法。

（付記１２）前記角度分布を作成するステップは、前記比較元パターン及び前記比較先パターンのスケールを、重み付け関数で重み付けして、前記度数に変換するステップを有することを特徴とする付記１１のパターン照合方法。

（付記１３）前記第３のステップは、前記比較元パターンと前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比較元パターンと前記比較先パターンの各々のスケールシェイプコンテクストを計算するステップと、前記各々のスケールシェイプコンテクストの各要素の平均値の比から前記スケールの比率を計算するステップとを有することを特徴とする付記８のパターン照合方法。

（付記１４）前記第５のステップは、前記角度・スケール変換された前記比較元パターン又は前記比較先パターンを、前記角度・スケール変換されていない前記比較元パターン又は前記比較先パターンに平行移動位置合わせするステップを有することを特徴とする付記８のパターン照合方法。

（付記１５）比較先パターンを取得する取得ユニットと、比較元パターンと前記比較先パターンとを照合する照合ユニットとを有し、前記照合ユニットは、前記比較元パターンと前記比較先パターンの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算し、前記比較元パターンと前記比較先パターンとの角度とスケールとから、前記比較元パターンと前記比較先パターンとの角度ずれを計算し、前記比較元パターンと前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比較元パターンと前記比較先パターンのスケールの比率を計算し、前記比較元パターン又は前記比較先パターンを、前記角度と比率とで、角度・スケール変換し、前記角度・スケール変換された前記比較元パターン又は前記比較先パターンと、角度・スケール変換されていない前記比較元パターン又は前記比較先パターンとをテンプレートマッチングにより、位置合わせし、前記位置合わせした前記比較元パターンと前記比較先パターンとの類似度を計算して、照合することを特徴とパターン照合装置。

（付記１６）前記照合ユニットは、複数の前記比較元パターンと複数の前記比較先パターンとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算し、複数の前記比較元パターンと複数の前記比較先パターンとの各々の角度と、スケールから、前記角度ずれを計算し、複数の前記比較元パターンと複数の前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比率を計算することを特徴とする付記１５のパターン照合装置。

（付記１７）前記照合ユニットは、比較元曲線パターンを線状の前記比較元パターンに変換し、比較先曲線パターンを線状の前記比較先パターンに変換することを特徴とする付記１５のパターン照合装置。

（付記１８）前記照合ユニットは、前記比較元パターンのスケールを角度の度数とした第１の角度分布と、前記比較先パターンのスケールを角度の度数とした第２の角度分布とを作成し、前記第１及び第２の角度分布から、前記角度ずれを計算することを特徴とする付記１５のパターン照合装置。

（付記１９）前記照合ユニットは、前記比較元パターン及び前記比較先パターンのスケールを、重み付け関数で重み付けして、前記度数に変換することを特徴とする付記１８のパターン照合装置。

（付記２０）前記照合ユニットは、前記比較元パターンと前記比較先パターンとの中点Ｘ座標と中点Ｙ座標とから、前記比較元パターンと前記比較先パターンの各々のスケールシェイプコンテクストを計算し、前記各々のスケールシェイプコンテクストの各要素の平均値の比から前記スケールの比率を計算することを特徴とする付記１５のパターン照合装置。

（付記２１）前記照合ユニットは、前記角度・スケール変換された前記比較元パターン又は前記比較先パターンを、前記角度・スケール変換されていない前記比較元パターン又は前記比較先パターンに平行移動位置合わせすることを特徴とする付記１５のパターン照合装置。

（付記２２）前記比較元パターンと前記比較先パターンとが、生体のパターンであり、前記照合が、生体認証であることを特徴とする付記１５のパターン照合装置。

比較元パターンと比較先パターンの角度ずれ、スケールの比率を別々に演算し、角度・スケール変換した後、実測テンプレートマッチングを行うため、テンプレートマッチング処理を最小限とでき、高精度及び高速な位置合わせが可能となる。特に、多数のパターンを照合する照合速度を向上でき、照合装置の性能向上に有効である。又、比較元及び比較先パターンの曲線を複数の線分データに分割するため、曲線を線分データの特徴に置き換えるため、その角度、スケール、中点Ｘ，Ｙ座標を容易に計算できる。更に、線分データの角度とスケールから、各曲線の角度分布を計算するため、曲線間の角度ずれを容易に計算できる。しかも、線分データの中点Ｘ，Ｙ座標からスケールシェイプコンテクストを計算し、スケールシェイプコンテクストの各要素の平均値の比から、第１の曲線と第２の曲線とのスケールの比率を計算するため、角度ずれと別にスケール比率を計算できる。

本発明の一実施の形態の認証システムの構成図である。図１の位置合わせ処理フロー図である。図２の位置合わせ処理の説明図である。図２の線分データ作成処理フロー図である。図４の線分データ作成処理の説明図である。図２の線分特徴抽出処理の説明図である。図２の角度推定処理フロー図である。図７の角度推定処理の説明図である。図２のスケール推定処理フロー図である。図９のスケール推定処理の説明図である。図２の角度・スケール変換処理フロー図である。図１１の角度・スケール変換処理の説明図である。図２の平行移動位置合わせ処理フロー図である。図１３の平行移動位置合わせ処理の説明図である。図２のアフィン変換パラメータ最適化処理フロー図である。図１５のアフィン変換パラメータ最適化処理の説明図である。

符号の説明

１血管パターン認証用撮像装置（比較先データ取得ユニット）
２処理ユニット（照合ユニット）
３位置合わせ探索処理
４認証処理
１０、２０データ取得処理
１２，２２関心領域抽出処理
１４，２４特徴抽出処理
３０，３２特徴変換処理
３４最適アフィン変換探索処理
４０位置合わせ処理
４２類似度計算処理
４４認証判定処理

Claims

比較元の第１の曲線と比較先の第２の曲線との各々を、複数の線分データに分割するステップと、
前記第１の曲線の線分データと前記第２の曲線の線分データとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算する第１のステップと、
前記第１の曲線の線分データと前記第２の曲線の線分データとの角度とスケールとから、前記第１の曲線と前記第２の曲線との角度ずれを計算する第２のステップと、
前記第１の曲線の線分データと前記第２の曲線の線分データとの中点Ｘ座標と中点Ｙ座標とから、前記第１の曲線と前記第２の曲線とのスケールの比率を計算する第３のステップと、
前記第１の曲線又は前記第２の曲線のいずれか一方を、前記角度と比率とで、角度・スケール変換する第４のステップと、
前記角度・スケール変換された前記第１の曲線又は前記第２の曲線と、角度・スケール変換されていない前記第１の曲線又は前記第２の曲線とをテンプレートマッチングにより、位置合わせする第５のステップとを有し、
前記第２のステップは、
前記第１の曲線の線分データのスケールを角度の度数とした第１の角度分布と、前記第２の曲線の線分データのスケールを角度の度数とした第２の角度分布とを生成するステップと、
前記第１及び第２の角度分布から前記角度ずれを計算するステップとを有し、
前記第３のステップは、
前記第１の曲線の線分データと前記第２の曲線の線分データとの中点Ｘ座標と中点Ｙ座標とから、前記第１の曲線と前記第２の曲線との各々のスケールシェイプコンテクストを計算するステップと、
前記各々のスケールシェイプコンテクストの各要素の平均値の比から前記スケールの比率を計算するステップとを有する
ことを特徴とするパターンの位置合わせ方法。
前記角度分布を作成するステップは、
前記第１の曲線の線分データのスケールを所定の重み付け関数で重み付けして、前記度数に変換し、前記第２の曲線の線分データのスケールを所定の重み付け関数で重み付けして、前記度数に変換するステップを有する
ことを特徴とする請求項１のパターンの位置合わせ方法。
前記第５のステップは、
前記角度・スケール変換された前記第１の曲線又は前記第２の曲線を、前記角度・スケール変換されていない前記第１の曲線又は前記第２の曲線に平行移動位置合わせするステップを有する
ことを特徴とする請求項１のパターンの位置合わせ方法。
比較元の第１の曲線と比較先の第２の曲線との各々を、複数の線分データに分割するステップと、
前記第１の曲線の線分データと前記第２の曲線の線分データとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算する第１のステップと、
前記第１の曲線の線分データと前記第２の曲線の線分データとの角度とスケールとから、前記第１の曲線と前記第２の曲線との角度ずれを計算する第２のステップと、
前記第１の曲線の線分データと前記第２の曲線の線分データとの中点Ｘ座標と中点Ｙ座標とから、前記第１の曲線と前記第２の曲線とのスケールの比率を計算する第３のステップと、
前記第１の曲線又は前記第２の曲線のいずれか一方を、前記角度と比率とで、角度・スケール変換する第４のステップと、
前記角度・スケール変換された前記第１の曲線又は前記第２の曲線と、角度・スケール変換されていない前記第１の曲線又は前記第２の曲線とをテンプレートマッチングにより、位置合わせする第５のステップと、
前記位置合わせした前記第１の曲線と前記第２の曲線との類似度を計算して、照合するステップとを有し、
前記第２のステップは、
前記第１の曲線の線分データのスケールを角度の度数とした第１の角度分布と、前記第２の曲線の線分データのスケールを角度の度数とした第２の角度分布とを生成するステップと、
前記第１及び第２の角度分布から前記角度ずれを計算するステップとを有し、
前記第３のステップは、
前記第１の曲線の線分データと前記第２の曲線の線分データとの中点Ｘ座標と中点Ｙ座標とから、前記第１の曲線と前記第２の曲線との各々のスケールシェイプコンテクストを計算するステップと、
前記各々のスケールシェイプコンテクストの各要素の平均値の比から前記スケールの比率を計算するステップとを有する
ことを特徴とするパターン照合方法。
前記角度分布を作成するステップは、
前記第１の曲線の線分データのスケールを所定の重み付け関数で重み付けして、前記度数に変換し、前記第２の曲線の線分データのスケールを所定の重み付け関数で重み付けして、前記度数に変換するステップを有する
ことを特徴とする請求項４のパターン照合方法。
前記第５のステップは、
前記角度・スケール変換された前記第１の曲線又は前記第２の曲線を、前記角度・スケール変換されていない前記第１の曲線又は前記第２の曲線に平行移動位置合わせするステップを有する
ことを特徴とする請求項４のパターン照合方法。
比較先パターンを取得する取得ユニットと、
比較元パターンと前記比較先パターンとを照合する照合ユニットとを有し、
前記照合ユニットは、
前記比較元パターンの第１の曲線と前記比較先パターンの第２の曲線との各々を、複数の線分データに分割し、前記第１の曲線の線分データと前記第２の曲線の線分データとの各々の角度と、スケールと、中点Ｘ座標と、中点Ｙ座標とを計算し、前記第１の曲線の線分データと前記第２の曲線の線分データとの角度とスケールとから、前記第１の曲線の線分データのスケールを角度の度数とした第１の角度分布と、前記第２の曲線の線分データのスケールを角度の度数とした第２の角度分布とを生成し、前記第１及び第２の角度分布から、前記第１の曲線と前記第２の曲線との角度ずれを計算し、前記第１の曲線の線分データと前記第２の曲線の線分データとの中点Ｘ座標と中点Ｙ座標とから、前記第１の曲線と前記第２の曲線との各々のスケールシェイプコンテクストを計算し、前記各々のスケールシェイプコンテクストの各要素の平均値の比から、前記第１の曲線と前記第２の曲線とのスケールの比率を計算し、前記第１の曲線又は前記第２の曲線のいずれか一方を、前記角度と比率とで、角度・スケール変換し、前記角度・スケール変換された前記第１の曲線又は前記第２の曲線と、角度・スケール変換されていない前記第１の曲線又は前記第２の曲線とをテンプレートマッチングにより、位置合わせし、前記位置合わせした前記第１の曲線と前記第２の曲線との類似度を計算して、照合する
ことを特徴とするパターン照合装置。
前記照合ユニットは、前記第１の曲線の線分データのスケールを所定の重み付け関数で重み付けして、前記度数に変換し、前記第２の曲線の線分データのスケールを所定の重み付け関数で重み付けして、前記度数に変換する
ことを特徴とする請求項７のパターン照合装置。
前記照合ユニットは、前記角度・スケール変換された前記第１の曲線又は前記第２の曲線を、前記角度・スケール変換されていない前記第１の曲線又は前記第２の曲線に平行移動位置合わせする
ことを特徴とする請求項７のパターン照合装置。