画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラム
【課題】動画に限定されることなく、異なる任意の画像中における対象物画像（画像パターン）の対応を、ピクセル間の単調連続性を確保しつつ画素毎に求めること。
【解決手段】 画像処理手段２は、一の画像の画素位置と他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、４次元空間座標において累積的に画素間距離を積み上げ計算することにより算出する。画像処理手段２は、積み上げ計算を行う場合に、対角方向を基準としてｍ座標の値とｎ座標の値との和の値が小さくなる順番で計算を実行し、最小累積距離の算出処理を行う場合に、累積計算における直前の座標位置からの遷移状態を制限した上で、直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行う。
【解決手段】 画像処理手段２は、一の画像の画素位置と他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、４次元空間座標において累積的に画素間距離を積み上げ計算することにより算出する。画像処理手段２は、積み上げ計算を行う場合に、対角方向を基準としてｍ座標の値とｎ座標の値との和の値が小さくなる順番で計算を実行し、最小累積距離の算出処理を行う場合に、累積計算における直前の座標位置からの遷移状態を制限した上で、直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムに関し、より詳細には、類似するパターン画像が記録された複数の画像（例えば、一の画像を参照画像、他の画像を対象画像とする）において、類似する画像パターンの各画素をそれぞれの画像より抽出することによって、画素毎の対応関係を求めることが可能な画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムに関する。
【背景技術】
【０００２】
従来より、類似する画像パターンが示された異なる画像において、対応する画像間のピクセル（画素）の対応関係を求めたり、対応する特徴抽出点を求めたりする方法が考えられている。このような対応するピクセルの抽出処理は、画像応用処理分野における画像認識手法、特徴点トラッキング手法、対象物の平面画像に基づいて対象物を３次元的に復元する手法などのさまざまなコンピュータサイエンスに応用することが可能となっている。しかしながら、コンピュータサイエンスにおける応用範囲が広いにもかかわらず、画像パターンの認識処理技術に関する決定的な手法が未だに確立されていないという問題があった。
【０００３】
例えば、画像間のピクセル対応問題を扱った手法として、動的計画法を利用する方法が提案されている（例えば、非特許文献１〜非特許文献３参照）。ここで、動的計画法とは、多変数の最適化を求める問題を解くための手法であって、最短経路問題などに利用される方法である。動的計画法では、「最適経路中の部分経路も、その部分経路における最適な経路により構成されている」という最適性の原理を利用する。このように最適性の原理を利用することにより、問題全体を部分問題における最適な解（決定）の積み重ねによって求めることができる。
【０００４】
このような動的計画法を応用した事例として、例えば、マッチングされる２つの画像の双方について領域を固定することにより、手書き文字認識を２次元非線形問題として求める研究が行われている（例えば、非特許文献４参照）。
【０００５】
また、今日では、入力時系列中の検索区間を事前に定めることなく、マッチング区間の抽出を行う連続動的計画法（１次元パターンでのセグメンテーションフリーの非線形マッチングを行う手法）が提案され（例えば、非特許文献５参照）、さらに１次元の連続動的計画法を２次元に拡張した２次元連続動的計画法が提案されている（例えば、非特許文献６参照）。２次元連続動的計画法を用いることにより、複数の画像から対象となる画像パターンの認識と抽出とを同時に行うことが可能となっている。
【０００６】
一方で、動画像において特徴点を抽出する処理や、特徴点などに基づいて対象物の３次元形状を復元する処理に関する研究が行われている。特徴点などに基づいて対象物の３次元形状を復元する処理では、動画を構成する画像間での適切な対応関係を求めることが重要となっており、この対応関係を求めることにより特徴点の追跡が可能となる。従来より数多く用いられる特徴点の追跡方法として、ＫＬＴ方法が知られている（例えば、非特許文献７参照）。
【０００７】
また、異なる特徴点の追跡方法として、ＳＩＦＴ特徴量を用いた手法も提案されている（例えば、特許文献８参照）。ＳＩＦＴ特徴量を用いた手法は、物体のスケール変化、物体の回転、物体の平行移動に対して影響を受けない（不変となる）特徴点を抽出することを特徴としており、その特徴点の抽出は１２８次元のベクトルにより構成されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】C. Myers, L. Rabiner, A. Rosenberg, “Performance tradeoffs in dynamic time warping algorithms for isolated word recognition”, IEEE Transactions on Acoustics, Speech and Signal Processing, 1980年12月, Vol.28, Issue 6, p.623−635
【非特許文献２】A.A. Amini, T.E. Weymouth, R.C. Jain, “Using dynamic programming for solving variational problems in vision”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990年9月, Vol. 12, No. 9, p.855−867
【非特許文献３】B. Serra, M. Berthod, Project PASTIS, INRIA, Sophia-Antipolis, “Subpixel contour matching using continuous dynamic programming”, Proceedings CVPR ’94 (IEEE Computer Society Conference on Computer Vision and Pattern Recognition), 1994年6月, p.202−207
【非特許文献４】S. Uchida, H. Sakoe, “An Efficient Two-Dimensional Warping Algorithm”, IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 社団法人電子情報通信学会1999年3月, Vol.E82-D, No. 3, p.693−700
【非特許文献５】R.Oka, “Spotting method for classification of real world data”, The Computer Journal, （イギリス）, Oxford Journal, 1998年,Vol. 41, No.8, p.559−565
【非特許文献６】T. Nishimura, R. Oka, ”Spotting Image Recognition using Two-Dimensional Continuous Dynamic Programming”, IEICE Technical Report (PRMU), 1997年7月, p.1−7
【非特許文献７】C. Tomasi, T. Kanade, “Detection and Tracking of Point Features”, Carnegie Mellon University Techinical Report, 1991年4月, CMU-CS-91-132
【非特許文献８】D.G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, Springer Netherlands, 2004年11月, Vol. 60, No.2, p.91−110
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上述した、２次元連続動的計画法を用いる方法では、参照画像の各行方向パターンのマッチング結果に基づいて列方向の累積を求める方法を用いているため、次述するピクセル間の単調連続性を保証することができなかった。このため、従来の２次元連続動的計画法を用いる方法では、２次元的に最適な対応関係を求めることが容易ではないという問題があった。
【００１０】
ここで、ピクセル間の単調性とは、マッチングの結果において、隣接するピクセル同士の相対的な位置関係場（上下左右の関係）が双方の画像の間において保持されている性質を意味し、連続性とは、マッチングの結果について対応点全体が自然なピクセル間の距離を保つ性質を意味している。この単調連続性を保つことにより、画像における基本的な特性を保持することが可能となり、画像間での適切な対応関係を求める処理において必要不可欠な要素となっている。
【００１１】
また、上述したＫＬＴ法は、動画像中の特徴点の対応に基づく追跡に用いられるトラッキング手法であり、微小時間でのピクセルの動きは平行移動だけしかせず、また、照明の変化に伴う輝度値の変化が生じないことを仮定して特徴点の追跡を行うことを特徴としている。このように、ＫＬＴ法では、微小時間中での特徴点の平行移動を仮定しているため、連続的に観測された画像系列でのトラッキングのみを対象とし、連続観測されたものでない異なる画像間における特徴点の抽出処理では、十分な機能を発揮することが困難であるという問題があった。
【００１２】
一方で、上述したＳＩＦＴ特徴量を用いた手法では、特徴点の対応を扱っているが、ベクトル要素で構成された特徴点を、異なる画像毎に求め、それぞれの画像において求められた特徴点に最も近い特徴点を対応付けることにより、特徴点の追跡を行う方法を採用する。このため、特徴点同士の対応付けは可能であっても、ピクセル単位で１対１の対応付けを行うことができず、また、対応付けられた特徴点もそれらしい点の対応に留まってしまうという問題があった。
【００１３】
さらに、ＳＩＦＴ特徴量を用いた特徴点の追跡手法では、対応付けられた特徴点において上述した単調性が保証されないという問題があった。ＳＩＦＴ特徴量を用いた手法により求められる特徴点の対応関係は、特徴点に関する類似性のみに基づいて求められているため、位置関係を求める手法として使えるまでには至っていなかった。
【００１４】
また、ＳＩＦＴ特徴量を用いた特徴点の追跡手法では、対象物以外の領域が含まれた状態で特徴点が求められるため、背景が変化するシーンなどにおいては追跡精度が低下し、追跡処理に失敗してしまうことがあるという問題があった。
【００１５】
本発明は、上記問題に鑑みてなされたものであり、動画に限定されることなく、異なる任意の画像中における対象物画像（画像パターン）の対応を、ピクセル間の単調連続性を確保しつつ画素毎に求めることが可能な画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチングプログラムを提供することを課題とする。
【課題を解決するための手段】
【００１６】
上記課題を解決するために、本発明に係る画像パターンマッチング装置は、互いに類似する画像パターンを含み得る一の画像と他の画像との画素毎の対応関係を求める画像パターンマッチング装置であって、前記一の画像と他の画像とを記録する記録手段と、前記一の画像と前記他の画像とにおける類似する画像パターンの画素毎の対応関係を求める画像処理手段とを有し、該画像処理手段は、前記一の画像を構成する画素の画素位置をｉ座標およびｊ座標を用いて特定するとともに、前記他の画像を構成する画素の画素位置をｍ座標およびｎ座標を用いて特定し、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画素間距離を積み上げ計算することにより算出し、算出された前記最小累積距離に基づいて、類似した画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求め、前記積み上げ計算を行う場合には、前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、前記最小累積距離の算出処理を行う場合には、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うことを特徴とする。
【００１７】
また、本発明に係る画像パターンマッチング方法は、画素位置をｉ座標およびｊ座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をｍ座標およびｎ座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング方法であって、画像処理手段が、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画像間距離を積み上げ計算することにより算出する最小累積距離算出ステップと、前記画像処理手段が、該最小累積距離算出ステップにおいて算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求める対応画素算出ステップとを有し、前記最小累積距離算出ステップにおいて、前記積み上げ計算を行う場合には、前記画像処理手段が、前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、前記最小累積距離の算出処理を行う場合には、前記画像処理手段が、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うことを特徴とする。
【００１８】
さらに、本発明に係る画像パターンマッチング用プログラムは、画素位置をｉ座標およびｊ座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をｍ座標およびｎ座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング用プログラムであって、コンピュータに、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画像間距離を積み上げ計算させることにより算出させる最小累積距離算出機能と、該最小累積距離算出機能により算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求めさせる対応画素算出機能とを実現させ、前記最小累積距離算出機能には、前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行させる積み上げ計算順番機能と、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行わせる累積座標間距離算出機能とが含まれることを特徴とする。
【００１９】
ここで、一の画像と他の画像は、互いに類似する画像パターンを含み得る画像であればよい。このため、類似する画像パターンが、一の画像および他の画像の両方の画像に含まれる場合はもちろんのこと、いずれか一方の画像にしか含まれない場合（つまり、類似する画像パターンが両方の画像に含まれない場合）であっても、互いに類似する画像パターンを含み得る場合に該当する。
【００２０】
このように、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムでは、積み上げ計算を行う場合において、ｍ座標およびｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行する。このため、積み上げ計算の値（解）が、現在の決定値（決定解）の直前の２つあるいは１つの決定値（決定解）に基づいて求められることになり、（ｍ，ｎ）平面における２次元の単調連続性を累積時に確保することが可能となる。
【００２１】
なお、単調連続性における単調性とは、マッチングの結果において、隣接する画素同士の相対的な位置関係場（上下左右の関係）が双方の画像の間において保持されている性質を意味し、単調連続性における連続性とは、マッチングの結果について対応点全体が自然なピクセル間の距離を保つ性質を意味している。
【００２２】
また、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムでは、最小累積距離の算出処理を行う場合において、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行う。このように、直前の座標位置からの遷移状態を所定の遷移パターンに制限することにより、直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出が行われるので、算出された前記最小累積距離に基づいて、類似する画像パターンに対応する一の画像の画素位置と他の画像の画素位置との対応関係を求める処理（バックトレース処理）において単調連続性を保証することが可能となる。
【００２３】
さらに、上述した画像パターンマッチング装置において、前記画像処理手段は、前記最小累積距離の算出処理を行う場合に、前記最小累積距離の計算を、前記ｍ座標方向に関する最小累積距離の計算と前記ｎ座標方向に関する最小累積距離の計算とに要素分割を行った上で、前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行うものであってもよい。
【００２４】
また、上述した画像パターンマッチング方法の前記最小累積距離算出ステップは、前記画像処理手段が、前記最小累積距離の算出処理を行う場合に、前記最小累積距離の計算を、前記ｍ座標方向に関する最小累積距離の計算と、前記ｎ座標方向に関する最小累積距離の計算とに要素分割を行う分割ステップと、前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う積み上げ計算ステップとを有するものであってもよい。
【００２５】
さらに、上述した画像パターンマッチング用プログラムにおいて、前記積み上げ計算順番機能は、前記最小累積距離の計算を、前記ｍ座標方向に関する最小累積距離の計算と、前記ｎ座標方向に関する最小累積距離の計算とに要素分割させる分割機能と、前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行わせる積み上げ計算機能とを有するものであってもよい。
【００２６】
このように、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムでは、最小累積距離の計算を、ｍ座標方向に関する最小累積距離の計算と、ｎ座標方向に関する最小累積距離の計算とに要素分割した上で、ｍ座標方向に関する最小累積距離の計算およびｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向およびｊ座標方向のそれぞれの方向に対する遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限して積み上げ計算を行うため、画素間の非線形対応関係を確保することが可能となる。また、算出された最小累積距離に基づいて、類似する画像パターンに対応する一の画像の画素位置と他の画像の画素位置との対応関係を求める処理（バックトレース処理）において、単調連続性をより確実に確保することが可能となる。
【発明の効果】
【００２７】
本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムによれば、積み上げ計算を行う場合において、ｍ座標およびｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行する。このため、積み上げ計算の値（解）が、現在の決定値（決定解）の直前の２つあるいは１つの決定値（決定解）に基づいて求められることになり、（ｍ，ｎ）平面における２次元の単調連続性を累積時に確保することが可能となる。
【００２８】
また、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムによれば、最小累積距離の算出処理を行う場合において、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行う。このように、直前の座標位置からの遷移状態を所定の遷移パターンに制限することにより、直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出が行われるので、画素間の非線形対応関係を確保することが可能となり、さらに、算出された前記最小累積距離に基づいて、類似する画像パターンに対応する一の画像の画素位置と他の画像の画素位置との対応関係を求める処理（バックトレース処理）において単調連続性を保証することが可能となる。
【図面の簡単な説明】
【００２９】
【図１】実施の形態に係る画像パターンマッチング装置の概略構成を示したブロック図である。
【図２】実施の形態に示されたｉ,ｊ,ｍ,ｎの４つの要素からなる４次元空間に基づいて、対象画像Ｓと参照画像Ｒとのピクセル（画素）毎の対応関係を示した図である。
【図３】（ａ）は、実施の形態に示されたランクＬの決定方法を説明するための図であり、（ｂ）は、各データ点における累積方向を示した図である。
【図４】実施の形態に示された画像復元における４点メッシュの制約条件を説明するための図である。
【図５】参照画像Ｒでの対応点がメッシュ構造を成すために、対象画像Ｓ上で（ξ（ｍ，ｎ），η（ｍ，ｎ））に至る出発点が取り得る点の候補を示した図である。
【図６】（ａ）は、実施の形態に示されたｉ方向への７パターンの遷移状態を示した図であり、（ｂ）は、ｊ方向への７パターンの遷移状態を示した図である。
【図７】局所距離Ｄ（ｉ，ｊ，ｍ，ｎ）＝Ｄ（ξ（ｍ，ｎ），η（ｍ，ｎ），ｍ，ｎ）が、４次元空間から対象画像Ｓの（ｉ，ｊ）平面に射影された状態を、（ａ）に示すｍ方向と、（ｂ）に示すｎ方向とに要素分割して示した図である。
【図８】（ａ）（ｂ）は、実施の形態に係るｄｘｘ（ｉ，ｊ，ｍ，ｎ）の構成を示した図であり、（ｃ）（ｄ）は、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）の構成を示した図である。
【図９】（ａ）（ｂ）は、実施の形態に係るｄｘｙ（ｉ，ｊ，ｍ，ｎ）の構成を示した図であり、（ｃ）（ｄ）は、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の構成を示した図である。
【図１０】実施の形態に示した参照画像Ｒから対象物以外の画像を取り除くことにより、対象物だけの画像を抽出する過程を説明するための図である。
【図１１】実施の形態に係るＣＰＵが、プログラムに基づいて実行する画像パターンのマッチング処理を示したフローチャートである。
【図１２】実施の形態に示した画像パターンのマッチング方法を用いることにより、子供の顔が含まれる参照画像Ｒに基づいて、対応する子供の顔の画像パターンを、対象画像Ｓから抽出する処理を説明するための図である。
【図１３】実施の形態に示した画像パターンのマッチング方法を応用して用いることにより、対象物が示された少ない枚数の画像に基づいて、対象物の３次元形状を復元することが可能となる旨を示した図である。
【発明を実施するための形態】
【００３０】
以下、本発明に係る画像パターンマッチング装置について、図面を用いて詳細に説明する。
【００３１】
図１は、画像パターンマッチング装置の概略構成を示したブロック図である。画像パターンマッチング装置１は、一般的なコンピュータにより構成することができ、図１に示すように、ＣＰＵ（Central Processing Unit）（画像処理手段）２と、ＲＯＭ（Read Only Memory）３と、ＲＡＭ（Random Access Memory）４と、記録部（記録手段）５と、ディスプレイ部６と、操作部７とにより概略構成されている。
【００３２】
ＣＰＵ２は、後述する画像パターンのマッチング処理を行う機能を有している。ＣＰＵ２は、後述する処理プログラム（例えば、図１１に示すフローチャートに基づくプログラム）に従って、画像パターンのマッチング処理を行う。ＲＡＭ４は、ＣＰＵ２の処理に利用されるワークエリアとして用いられる。ＲＯＭ３には、上述した画像パターンのマッチング処理に関するプログラム等が記録されている。ＣＰＵ２は、ＲＯＭ３より読み込んだプログラムに従って、画像パターンのマッチング処理を行う。
【００３３】
記録部５には、画像パターンのマッチング処理に用いられる画像データなどが記録されている。本実施の形態に係る記録部５は、一般的はハードディスクにより構成されている。なお、記録部５の構成は、ハードディスクだけに限定されるものではなく、フラッシュメモリ、ＳＳＤ（Solid State Drive / Solid State Disk）、ＣＤ―ＲＯＭドライブ、ＤＶＤドライブなどのように、画像パターンマッチング処理に用いられる複数の画像データをＣＰＵ２が読み出し可能な状態で記録することが可能なものであるならば、具体的な構成は特に限定されるものではない。
【００３４】
なお、本実施の形態に係る画像パターンマッチング装置１では、ＣＰＵ２において実行される画像パターンマッチング処理に関するプログラムを、ＲＯＭ３に記録する構成として説明を行うが、これらのプログラムは、記録部５に記録されるものであってもよい。
【００３５】
ディスプレイ部６は、記録部５に記録される画像データをユーザに対して視認可能に表示させ、また、ＣＰＵ２による画像パターンのマッチング処理結果を表示させる役割を有している。ディスプレイ部６には、液晶ディスプレイや、ＣＲＴディスプレイなどの一般的な表示装置が用いられる。
【００３６】
操作部７は、ユーザが画像パターンマッチング装置１を操作するために必要なデータの入力や、画像パターンマッチング装置１の具体的な操作などを行う場合に用いられる装置であって、一般的なキーボードやマウスなどにより構成される。
【００３７】
ＣＰＵ２は、ＲＯＭ３より演算処理に必要なプログラムを読み取り、読み取ったプログラムに従って、記録部５に記録される複数の画像データより類似する画像パターンの抽出を行う処理、より詳細には、異なる画像データに含まれる類似する画像パターンの全てのピクセル（画素）の対応関係を求める処理を行う。以下に、ＣＰＵ２が行う処理の内容を具体的に説明し、その後、ＣＰＵ２の具体的な処理手順を、フローチャートを示して説明する。
【００３８】
まず、ＣＰＵ２が行う処理内容を具体的に説明する。例えば、相異なる２つの画像データのうち、一方の画像データを対象画像Ｓ、他方の画像データを参照画像Ｒとして、対象画像Ｓに含まれている画像パターンから、参照画像Ｒに表される画像パターンの対応をピクセル単位で抽出する処理について説明する。
【００３９】
ＣＰＵ２は、対象画像Ｓを構成するピクセル位置と参照画像Ｒを構成するピクセル位置とを、それぞれ座標点を用いて特定する。具体的に、ＣＰＵ２は、対象画像Ｓをｉ要素とｊ要素とを備える（ｉ，ｊ）平面における座標点のピクセルの集合として捉える。
【数１】
但し、対象画像Ｓのピクセル位置は、１≦ｉ≦Ｉ（定数）、１≦ｊ≦Ｊ（定数）の範囲で特定されるものとする。
【００４０】
一方で、ＣＰＵ２は、参照画像Ｒをｍ要素とｎ要素とを備える（ｍ，ｎ）平面における座標点のピクセルの集合として捉える。
【数２】
但し、参照画像Ｒのピクセル位置は、１≦ｍ≦Ｍ（定数）、１≦ｎ≦Ｎ（定数）の範囲で特定されるものとする。
【００４１】
さらに、ＣＰＵ２は、対象画像Ｓの各ピクセルの値をＳｐ（ｉ，ｊ）＝（ｒ，ｇ，ｂ）として記録部５に記録し、また、参照画像Ｒの各ピクセルの値をＲｐ（ｍ，ｎ）＝（ｒ，ｇ，ｂ）として記録する。なお、（ｒ，ｇ，ｂ）は、対応するピクセルの色彩データ（ｒ：赤、ｇ：緑、ｂ：青）を示している。
【００４２】
このように、ＣＰＵ２は、対象画像Ｓのｉ要素，ｊ要素と、参照画像Ｒのｍ要素，ｎ要素とに基づいて、ｉ，ｊ，ｍ，ｎの４つの要素からなる４次元の空間（局地距離累積空間）を構成し、対象画像Ｓと参照画像Ｒとの画像パターンのマッチングを、それぞれの画像（対象画像Ｓおよび参照画像Ｒ）におけるピクセル（画素）毎の対応関係式（後述する）を用いることにより判断する。
【００４３】
図２は、ｉ，ｊ，ｍ，ｎの４つの要素からなる４次元の空間に基づいて、対象画像Ｓと参照画像Ｒとのピクセル（画素）毎の対応関係を図示したものである。対象画像Ｓの各ピクセル（ｉ，ｊ）に対して、参照画像Ｒのｍ要素、ｎ要素からなる平面の存在を考えることにより、４次元の空間を構築する。
【００４４】
ＣＰＵ２は、類似する画像パターンを含む画像同士で画像パターンのマッチング処理を行う場合に、対応する参照画像Ｒの画素の座標点に対応する座標点を、対象画像Ｓの画素より求めて、対応する参照画像Ｒから対象画像Ｓへの写像を、写像Ｒ→Ｓとして定義する。つまり、
（ｍ，ｎ）∈Ｒについて（参照画像Ｒに属する座標点（ｍ，ｎ）について）
（ｍ，ｎ）⇒（ξ（ｍ，ｎ），η（ｍ，ｎ）） ・・・式３
となるξとηの２つの関数が考えられている。
【００４５】
ここで、
ξ（Ｍ，Ｎ）＝ｉ、 η（Ｍ，Ｎ）＝ｊ ・・・式４
となる対応点を累積の終点として考える（但し、Ｍは、参照画像Ｒにおける最大値となるｍ要素の値、Ｎは、参照画像Ｒにおける最大値となるｎ要素の値を示している）。
【００４６】
累積時に与えられる各点に対する重みをｗ（ｉ，ｊ，ｍ，ｎ）とし、また、対応するピクセルの対象画像Ｓの座標（ｉ，ｊ）と参照画像Ｒの座標（ｍ，ｎ）との距離（ピクセル間距離）をｄ（ｉ，ｊ，ｍ，ｎ）として、２次元連続動的計画法を用いることにより最小累積距離を示す積み上げ空間を求める。この積み上げ空間の最終累積値における最小値をスポッティング点という。このようにして求められる２次元連続動的計画法による最小累積距離の積み上げ空間Ｊ（ｉ，ｊ）は、以下の評価式で実現される。
【数３】
【００４７】
なお、この累積値を求める場合には、図３（ａ）に示すように、（ｍ＋ｎ）に基づいてランクＬを決定し、参照画像Ｒの対角方向に対して、下から順番に累積値を積み上げて計算を行う。このようにして積み上げ計算を行うことにより、各データ点（ｍ，ｎ）に与えられる累積方向は、図３（ｂ）に示すように、２入力方向（ｍ方向およびｎ方向）および２出力方向（ｍ方向およびｎ方向）となる。また、この積み上げ計算により現在の座標における累積値が、その直前の２つ（あるいは１つ）の累積値に基づいて求められることになる。
【００４８】
式５に示すξ（ｍ，ｎ）において最適となる解をξ＊（ｍ，ｎ）と定義し、また、η（ｍ，ｎ）において最適となる解をη＊（ｍ，ｎ）と定義すると、式５に示すＷは、最適な累積の重みを示すものとして以下のように定義することができる。
【数４】
【００４９】
このようにして４次元空間に基づいて対応点を求めると、図２に示すように４次元空間において参照画像Ｒのピクセル（画素）と対象画像Ｓのピクセル（画素）とが対応する座標Ｄ（ｉ，ｊ，ｍ，ｎ）を求めることができる。この座標Ｄ（ｉ，ｊ，ｍ，ｎ）を（ｉ，ｊ）平面に射影することにより、対応する対象画像Ｓの座標を求めることができ、また、（ｍ，ｎ）平面に射影することにより、対応する参照画像Ｒの座標を求めることができる。従って、この参照画像Ｒと対象画像Ｓとにおける座標の対応を求めることによって、参照画像Ｒの画像パターンの座標（ｍ，ｎ）に対応する対象画像Ｓの画像パターンの座標（ｉ，ｊ）を求めることができ、ピクセル単位で対応関係を示すことが可能となる。
【００５０】
なお、上述したように、参照画像Ｒと対象画像Ｓとの対応点（ピクセル、画素）を求めることができる場合には、対応点（ピクセル、画素）が変形しても、また、それぞれの対応点（ピクセル、画素）が画像上で変形しても、メッシュ構造として（物体の形状を表現するために使われるデータとして）それぞれが保たれている必要がある。このように、双方でメッシュ構造が保たれていることを、本実施の形態に係る説明では、「単調連続性の保証」という言葉で表現する。
【００５１】
ここで、単調性とは、画像パターンのマッチング前後で隣接するピクセル同士の相対的な位置関係（上下左右の関係）が保持される性質を意味し、連続性とは、マッチングの前後で対応点において自然なピクセル間の距離を保つ性質を意味している。なお、上述した積み上げ計算処理では、ランクＬを定義することにより参照画像Ｒの対角方向に対して累積値の積み上げ計算を行うので、参照画像Ｒにおける２次元的な単調連続性が累積時に反映されることになり、「単調連続性の保証」が確保されることになる。
【００５２】
次に、ｉ要素およびｊ要素を含めた全体としての「単調連続性の保証」を確保するための条件を説明する。
【００５３】
図４は、画像復元における４点メッシュの制約条件を説明するための図である。図４は、説明を簡単にするために線形の場合（つまり、拡大縮小回転のない場合）における説明図を示している。なお、実際の適用段階においては、拡大縮小回転を行うことにより、最適なマッチング処理を行うことが可能になる場合もある。
【００５４】
図４は、図２に示したように、対象画像Ｓの各ピクセルにおいて参照画像Ｒの座標平面を考えることにより構成された４次元の空間を示している。また、図４には、参照画像Ｒの座標（ｍ，ｎ）に対応する対象画像Ｓの座標（ｉ，ｊ）＝（ξ（ｍ，ｎ），η（ｍ，ｎ））が示されており、また、対象画像Ｓ上で（ｉ，ｊ）＝（ξ（ｍ，ｎ），η（ｍ，ｎ））へと対応点が変化する場合において、参照画像Ｒにおける対象点のメッシュ構造を確保しつつ、その対象点に至ることが可能な出発点（座標）の集合が表されている。図４に示す場合では、参照画像Ｒにおける点（ｍ−１，ｎ−１）に対応可能な出発点は、点（ｍ，ｎ）、点（ｍ，ｎ−１）および点（ｍ−１，ｎ）によって決定されることになる。
【００５５】
２次元的な単調性および連続性を保証するために、参照画像Ｒのｍ方向に対応する対象画像Ｓの移動可能な点（局所パス：遷移状態）の集合を
Ｋ（ｍ，ｎ）＝｛(ξ（ｍ−１，ｎ），η（ｍ−１，ｎ）)｝とし、
参照画像Ｒのｎ方向に対応する対象画像Ｓの移動可能な点（局所パス：遷移状態）の集合を
Ｌ（ｍ，ｎ）＝｛（ξ（ｍ，ｎ−１），η（ｍ，ｎ−１））｝とすると、
点（ｍ−１，ｎ−１）に対応する点（ξ（ｍ−１，ｎ−１），η（ｍ−１，ｎ−１））は、
【数５】
を満たす必要がある。
【００５６】
式７において、Ｋ（ｍ，ｎ）は、（ξ（ｍ，ｎ），η（ｍ，ｎ））にｍ方向から１回の遷移で至る４次元空間の点集合を、対象画像Ｓに射影した点の候補（集合）を示すことになり、Ｌ（ｍ，ｎ）は、（ξ（ｍ，ｎ），η（ｍ，ｎ））にｎ方向から１回の遷移で至る４次元空間の点集合を、対象画像Ｓに射影した点の候補（集合）を示すことになる。
【００５７】
また、式７における
【数６】
は、式の左辺に示す点から右辺に示す式の集合を接合する意味（テンソル積）を示している。
【００５８】
この式７を満たす場合には、局所的に単調性および連続性を保証した４点（ｍ，ｎ）、（ｍ，ｎ−１）、（ｍ−１，ｎ）、（ｍ−１，ｎ−１）を用いたメッシュが、図４に示すように作成される。なお、図４は、上述したように線形の場合（つまり、拡大縮小回転のない場合）を示している。
【００５９】
従って、図４に示すように、点（ｍ−１，ｎ−１）から点（ｍ，ｎ）に至る場合において、２つの局所パスが点（ｍ，ｎ−１）と（ｍ−１，ｎ）とを通るときに、参照画像Ｒ上でメッシュ構造を作ることが可能となる。そして、これに対応するようにして非線形の変形が行われた場合には、対象画像Ｓ上でもメッシュ構造を作ることが可能であるため、２つのパスのそれぞれが、２回の遷移で変化可能な出発点の集合である
【数７】
と
【数８】
と
に重なる範囲内において（ξ（ｍ−１，ｎ−１），η（ｍ−１，ｎ−１））が存在すれば良いことになる。
【００６０】
図５は、参照画像Ｒでの対応点がメッシュ構造を成すために、対象画像Ｓ上で（ξ（ｍ，ｎ），η（ｍ，ｎ））に至る出発点が取り得る点の集合（候補）を太い点（●：黒丸）で示した図である。図５では、対象画像Ｓにおける（ξ（ｍ，ｎ），η（ｍ，ｎ））に至る出発点として、Ｋ（ｍ，ｎ）で示される出発点（ξ（ｍ−１，ｎ），η（ｍ−１，ｎ））と、Ｌ（ｍ，ｎ）で示される出発点（ξ（ｍ，ｎ−１），η（ｍ，ｎ−１））とを取ることが可能であり、さらに、
【数９】
で示される出発点（ξ（ｍ−１，ｎ−１），η（ｍ−１，ｎ−１））を取ることが可能であることが示されている。
【００６１】
また、２次元連続動的計画法では、累積時に局所パス（上述した移動可能な出発点から遷移状態）に対して幾何学的な制約を与えることによって、それぞれピクセル間の非線形変形度合いを決めることができる。
【００６２】
図６（ａ）および図６（ｂ）は、局所パスにおける遷移の状態（方向）の制限を示した図であり、具体的に図６（ａ）の上段図には、ｉ方向への移動を基本とした遷移状態が７パターン示されており、図６（ｂ）の上段図には、ｊ方向への移動を基本とした遷移状態が７パターン示されている。また、図６（ａ）の下段図には、図６（ａ）の上段図に示した７パターンの遷移状態に基づいて、黒丸で示された座標へ遷移が行われる直前に位置し得る座標位置が白丸で示されており、図６（ｂ）の下段図には、図６（ｂ）の上段図に示した７パターンの遷移状態に基づいて、黒丸で示された座標において遷移が行われる直前に位置し得る座標位置が白丸で示されている。
【００６３】
図６（ａ）（ｂ）に示すように、累積値の積み上げ処理において、移動方向を示す局所パスに対してそれぞれ７パターンのパス制約を加えることにより、（パターン１）等倍、（パターン２）等倍＋４５度回転、（パターン３）等倍−４５度回転、（パターン４）２倍、（パターン５）２倍＋４５度回転、（パターン６）２倍−４５度回転、（パターン７）縮小を許容したピクセル間の非線形変形を実現することが可能となる。なお、縮小は、累積時および後述するバックトラック時における制約として、連続縮小に関する制限を与えることにより実現される。
【００６４】
このように、ＣＰＵ２において局所パスに対して図６（ａ）（ｂ）に示すような遷移パターンを設定することにより、単調連続性の保証を確保することが可能となる。
【００６５】
次に、画像パターンのマッチング処理に用いられる局所距離について説明する。画像パターンのマッチング処理における計算は、局所距離と呼ばれる値を累積することにより実行される。局所距離は、対象画像Ｓの（ｉ，ｊ）点でのピクセル（カラー画像の場合には、ｒ（赤：），ｇ（緑：），ｂ（青：）の３要素を備えている）と、参照画像Ｒの（ｍ，ｎ）点でのピクセル（同様に、カラー画像の場合には、ｒ（赤：），ｇ（緑：），ｂ（青：）の３要素を備えている）との間で、以下のように定義される。
【数１０】
【００６６】
ここで、ｋの値は、参照画像Ｒ（ｉ,ｊ）および対象画像Ｓ（ｉ,ｊ）がカラー画像である場合における各色彩を示しており、ｋ＝１は、参照画像Ｒ（ｉ,ｊ）および対象画像Ｓ（ｉ,ｊ）のｒ（赤：）に該当し、ｋ＝２は、参照画像Ｒ（ｉ,ｊ）および対象画像Ｓ（ｉ,ｊ）のｇ（緑：）に該当し、ｋ＝３は、参照画像Ｒ（ｉ,ｊ）および対象画像Ｓ（ｉ,ｊ）のｂ（青：）に該当する。なお、ｄ（ｉ，ｊ，ｍ，ｎ）の値は、０≦ｄ（ｉ，ｊ，ｍ，ｎ）≦１となる。
【００６７】
また、２次元連続動的計画法では、上述したように２種類の局所パスを選択するように設計されており、この局所パスは、上述した４つのポイント（ｍ，ｎ）、（ｍ−１，ｎ）、（ｍ，ｎ−１）、（ｍ−１，ｎ−１）のつながりに基づいて求められる。これらの４ポイントのつながりを変数として表すと、上述した局所距離ｄ（ｉ，ｊ，ｍ，ｎ）における４ポイントの関係から、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つの変数を用いて示すことができる。
【００６８】
図７は、４つの変数に基づいてそれぞれ累積された局所距離Ｄ（ｉ，ｊ，ｍ，ｎ）＝Ｄ（ξ（ｍ，ｎ），η（ｍ，ｎ），ｍ，ｎ）が、４次元空間から対象画像Ｓの（ｉ，ｊ）平面に射影された状態を示している。図７に示すように局所距離Ｄ（ｉ，ｊ，ｍ，ｎ）を、ｍ方向要素とｎ方向要素とに要素分割することにより、２方向から対象画像Ｓに対応させて局所距離Ｄの累積計算を行うことができる。図７では、累積距離Ｄ（ξ（ｍ，ｎ），η（ｍ，ｎ），ｍ，ｎ）が、ｍ方向（Ｋ（ξ（ｍ，ｎ），η（ｍ，ｎ））の累積距離Ｄ（Ｋｘ（ξ（ｍ，ｎ），η（ｍ，ｎ）），Ｋｙ（ξ（ｍ，ｎ），η（ｍ，ｎ）），ｍ−１，ｎ）と、ｎ方向（Ｌ（ξ（ｍ，ｎ），η（ｍ，ｎ））の累積距離Ｄ（Ｌｘ（ξ（ｍ，ｎ），η（ｍ，ｎ）），Ｌｙ（ξ（ｍ，ｎ），η（ｍ，ｎ）），ｍ，ｎ−１）とにより算出される場合が示されている。
【００６９】
次に、上述したｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つ値の決定方法について説明する。
【００７０】
まず、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）は、４次元空間から（ｍ，ｎ）平面へと射影された局所距離計算点群の最上点（ｉ，ｊ，ｍ，ｎ）に割り当てられる４つの変数（座標点）の１つである。図８（ａ）は、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）を示しており、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）は、図８（ｂ）に示すように、射影点（ｉ’，ｊ’，ｍ，ｎ）に割り当てられる変数であるｄｘｘ（ｉ’，ｊ’，ｍ−１，ｎ）と、ｄ（ｉ，ｊ，ｍ，ｎ）の値との和によって算出される。なお、局所距離ｄｘｘ（ｉ’，ｊ’，ｍ−１，ｎ）は、図８（ｂ）の長方形部分に射影された４つの局所距離の加算により求められる値である。
【００７１】
次に、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）は、図８（ｃ）のように示される。ｄｙｙ（ｉ，ｊ，ｍ，ｎ）は、図８（ｄ）に示すように、射影点（ｉ”，ｊ”，ｍ，ｎ−１）に割り当てられる変数であるｄｙｙ（ｉ”，ｊ”，ｍ，ｎ−１）と、局所距離ｄ（ｉ，ｊ，ｍ，ｎ）の値との和によって算出される。なお、ｄｙｙ（ｉ”，ｊ”，ｍ，ｎ−１）は、図８（ｄ）の長方形部分に射影された４つの局所距離の加算により求められる値である。
【００７２】
また、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）は、点（ｉ’，ｊ’，ｍ−１，ｎ）に割り当てられた２つの値であるｄｙｙ（ｉ’，ｊ’，ｍ−１，ｎ）とｄｘｙ（ｉ’，ｊ’，ｍ−１，ｎ）との加算により求められる。図９（ａ）は、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）を示しており、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）は、図９（ｂ）に示すように、図面上の大きな長方形内に示される射影された局所距離計算点を示すｄｘｙ（ｉ’，ｊ’，ｍ−１，ｎ）と、図面上の小さな長方形内に示される射影された局所距離計算点を示すｄｙｙ（ｉ’，ｊ’，ｍ−１，ｎ）とにより構成される。
【００７３】
さらに、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）は、点（ｉ”，ｊ”，ｍ，ｎ−１）に割り当てられた２つの値であるｄｘｘ（ｉ”，ｊ”，ｍ，ｎ−１）とｄｙｘ（ｉ”，ｊ”，ｍ，ｎ−１）との加算により求められる。図９（ｃ）は、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）を示しており、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）は、図９（ｄ）に示すように、図面上の大きな長方形内の射影局所距離計算点を示すｄｙｘ（ｉ”，ｊ”，ｍ，ｎ−１）と、図面上の小さな長方形内の射影局所距離計算点を示すｄｘｘ（ｉ”，ｊ”，ｍ，ｎ−１）とにより構成される。
【００７４】
上述した説明より、４つの変数の値は、
【数１１】
【数１２】
【数１３】
【数１４】
で示すことができ、点（ｉ，ｊ，ｍ，ｎ）における最小累積値（最小累積距離）Ｄ（ｉ，ｊ，ｍ，ｎ）は、
【数１５】
により求めることができる。
【００７５】
なお、上述した（ｉ’，ｊ’，ｍ−１，ｎ）および（ｉ”，ｊ”，ｍ，ｎ−１）は
【数１６】
【数１７】
の２式を用いて求めることができる。
【００７６】
式１７および式１８の｛｝内には、図６（ａ）および図６（ｂ）に示した７パターンの局所パス（遷移状態（方向）を制限した局所パス）を示す式が記載されている。ＣＰＵ２は、これらの７パターンの関係式を計算して、式の値が最小となるときの（ｉ’，ｊ’，ｍ−１，ｎ）の各要素の値と（ｉ’，ｊ’，ｍ，ｎ−１）の各要素の値とを抽出する。そして、ＣＰＵ２は、抽出された値を式１２〜式１５に代入することにより、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つ値を算出する。
【００７７】
そして、ＣＰＵ２は、算出されたｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）およびｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つ値を用いて、式１６により点（ｉ，ｊ，ｍ，ｎ）の最適累積値であるＤ（ｉ，ｊ，ｍ，ｎ）を求める。
【００７８】
なお、ＣＰＵ２は、初期値としてｍ＝１、ｎ＝１が与えられている状態において、ｍが１以上Ｍ以下となる条件を満たす間だけｍを１ずつ増加させるとともに、各ｍにおいて、ｎが１以上Ｎ以下となる条件を満たす間だけｎを１ずつ増加させることにより、全てのｍおよびｎにおいて（ｉ’，ｊ’，ｍ−１，ｎ）と（ｉ’，ｊ’，ｍ，ｎ−１）を求める。
【００７９】
さらに、ＣＰＵ２は、累積値の積み上げ計算を行うために、ランクＬの値に初期値としてＬ＝２を代入し、Ｌが２以上Ｍ＋Ｎ以下となる条件を満たす間だけＬを１ずつ増加させる処理を行うことによって、（ｍ，ｎ）平面における各座標（ｍ，ｎ）の値についての累積処理を行う。
【００８０】
このようにして求められる最適累積値Ｄ（ｉ，ｊ，ｍ，ｎ）は、上述した式１７および式１８に示すように、Ｄ（ｉ’，ｊ’，ｍ−１，ｎ）とＤ（ｉ”，ｊ”，ｍ，ｎ−１）とにより求められる値を用いて計算される。従って、最終的にＣＰＵ２は、対象画像Ｓの各（ｉ，ｊ）座標において上述した最適な累積値Ｄ（ｉ，ｊ，Ｍ，Ｎ）の値を、次の式１９に基づいて計算することができる。
【数１８】
【００８１】
このようにして求められる累積最適値Ｄ（ｉ，ｊ，Ｍ，Ｎ）は、上述したように、点（ｉ，ｊ）において２次元的に分布するパターンとして求められる。ここで、この２次元分布において局所的に最小となる点が、上述したスポッティング点である。つまり、対象画像Ｓの（ｉ，ｊ）に対応するスポッティング点は、Ｄ（ｉ，ｊ，Ｍ，Ｎ）における最小となる点であり、
【数１９】
により求められることになる。（ｉ，ｊ)平面上で、局所的な領域で最小点の値が閾値よりも小さい場合には、その局所領域の点において、参照画像Ｒに類似する対象画像Ｓの部分画像が最適にマッチングしていると判断することができる。したがって、そのような局所領域が複数ある場合は、複数個の類似の参照画像Ｒが存在することを意味することになる。
【００８２】
このため、スポッティング点において、累積最適値Ｄ（ｉ，ｊ，Ｍ，Ｎ）を出発点としてバックトレース処理を行うことにより、参照画像Ｒの部分領域を示す
（ξ＊（ｍ，ｎ），η＊（ｍ，ｎ）） 但し、１≦ｍ≦Ｍ，１≦ｎ≦Ｎ
を、以下のアルゴリズムに基づいて得ることができる。ここで、（ξ＊（ｍ，ｎ），η＊（ｍ，ｎ））は、対象画像Ｓの座標点（ｉ，ｊ）に対応している。
【００８３】
まず、ｍ，ｎは、それぞれ固定された値であると仮定する。すると
（ｉ＊，ｊ＊）は、
【数２０】
で示すことができ、（ｉ＊＊，ｊ＊＊）は、
【数２１】
で求めることができる。このため、（ξ＊（ｍ，ｎ），η＊（ｍ，ｎ））は、
（ξ＊（ｍ，ｎ），η＊（ｍ，ｎ））
＝（ｉ＊＊（ｍ，ｎ），ｊ＊＊（ｍ，ｎ）） ・・・式２３
により求めることができる。
【００８４】
この式２１〜式２３に基づいて、ｍの値をＭ≧ｍ≧１の範囲内でＭから１まで１ずつ減少させると共に、ｎの値をＮ≧ｎ≧１の範囲内でＮから１まで１ずつ減少させることにより、全てのｍおよびｎに対応する（ξ＊（ｍ，ｎ），η＊（ｍ，ｎ））を求めることができる。
このように、式２１〜式２３を繰り返し計算してバックトレース処理を行うことにより、参照画像Ｒに最適に対応する対象画像Ｓの部分画像を取り出すことが可能となる。
【００８５】
なお、通常、参照画像Ｒには特定の対象物の画像が示されているが、その画像の外縁形状はさまざまである。例えば、背景画像のように画像パターンのマッチング処理の対象とならない画像（対象物以外の画像）が含まれている場合には、適切に対象画像のみを抽出しないと、精度良く画像パターンのマッチング処理を行うことができない。このため、例えば図１０に示すように、対象物となる画像以外の領域の局所距離の値を１に設定することにより、背景部分を取り除くことが可能となり、参照画像Ｒにおいて対象物だけの画像をマッチング処理の対象とすることが可能となる。
【００８６】
次に、上述した処理内容を、図１１に示すフローチャートを示すことによって、ＣＰＵ２がプログラムに基づいて実行する画像パターンのマッチング処理について説明する。
【００８７】
まずＣＰＵ２は、まず、変数ｌに２を設定（ｌ＝２）する（ステップＳ．１）。次に、ＣＰＵ２は、変数ｍに１を設定（ｍ＝１）すると共に、変数ｎに１を設定（ｎ＝１）する（ステップＳ．２）。そして、ＣＰＵ２は、式１７に基づいて、（ｉ’，ｊ’，ｍ−１，ｎ）を求めると共に、式１８に基づいて、（ｉ”，ｊ”，ｍ，ｎ−１）を求める（ステップＳ．３）。
【００８８】
そして、ＣＰＵ２は、求められた（ｉ’，ｊ’，ｍ−１，ｎ）および（ｉ”，ｊ”，ｍ，ｎ−１）に基づいて、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つ値を算出する（ステップＳ．４）。
【００８９】
その後、ＣＰＵ２は、求められたｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つ値を用いて、式１６によりＤ（ｉ，ｊ，ｍ，ｎ）を求める（ステップＳ．５）。そして、ＣＰＵ２は、ｍおよびｎの値が、１≦ｍ≦Ｍおよび１≦ｎ≦Ｎの条件を満たすか否かの判断を行う（ステップＳ．６）。
【００９０】
ｍおよびｎの値が、１≦ｍ≦Ｍおよび１≦ｎ≦Ｎの条件を満たす場合（ステップＳ．６においてＹｅｓの場合）、ＣＰＵ２は、ｍおよびｎの値に１を加算し（ｍ＝ｍ＋１、ｎ＝ｎ＋１）（ステップＳ．７）、処理をステップＳ．３に移行する。
【００９１】
一方で、ｍおよびｎの値が、１≦ｍ≦Ｍおよび１≦ｎ≦Ｎの条件を満たさない場合（ステップＳ．６においてＮｏの場合）、ＣＰＵ２は、ｌの値が、２≦ｌ≦Ｍ＋Ｎの条件を満たすか否かの判断を行う（ステップＳ．８）。
【００９２】
ｌの値が、２≦ｌ≦Ｍ＋Ｎの条件を満たす場合（ステップＳ．８においてＹｅｓの場合）、ＣＰＵ２は、ｌの値に１を加算し（ｌ＝ｌ＋１）（ステップＳ．９）、処理をステップＳ．２に移行する。
【００９３】
一方で、ｌの値が、２≦ｌ≦Ｍ＋Ｎの条件を満たさない場合（ステップＳ．８においてＮｏの場合）、ＣＰＵ２は、求められた累積最適値Ｄ（ｉ，ｊ，Ｍ，Ｎ）に基づいて、バックトレース処理を行うことにより、対象画像Ｓのピクセルと参照画像Ｒのピクセルとの対応関係を求め（ステップＳ．１０）、画像パターンのマッチング処理を終了する。
【００９４】
このように、画像パターンのマッチング処理を行うことにより、非線形に対応する画像パターンの対応をピクセル毎に求めることが可能となる。さらに、このピクセル毎の対応を求める過程において、ランクＬという概念を採用し、（ｍ，ｎ）平面において画像の対角方向の累積値を積み上げることにより累積最適値Ｄを求めるので、累積時において局所的な単調連続性を確保することが可能となる。さらに、図６（ａ）および図６（ｂ）に示すように、局所パスに対して、遷移パターンを制限することにより累積最適値Ｄを求めるので、単調連続性の保証を確保することが可能となる。
【００９５】
従って、本実施の形態に示した画像パターンのマッチング方法を用いて求められる対象画像Ｓのピクセルと参照画像Ｒのピクセルとの対応関係は、非線形対応を許容しつつ、かつ、単調連続性の保証を確保することができ、さらに、動画のように連続した画像ではなく、類似する画像パターンが示された異なる少数の画像に基づいて、ピクセル毎の対応関係を求めることが可能となる。
【００９６】
図１２は、上述した画像パターンのマッチング方法を用いて子供の顔が含まれる参照画像Ｒに基づいて、対象画像Ｓより対応する画像を抽出する処理を説明するための図である。図１２（ａ）には、子供の顔が含まれる参照画像Ｒが示されており、（ｂ）には、背景画像などが取り除かれた対象物（子供の顔）だけの画像が示されている。
【００９７】
一方で、（ｃ）には、子供の顔の画像だけでなく、その背景画像や、他の人物の顔画像などが含まれる対象画像Ｓが示されている。ＣＰＵ２が上述した画像パターンのマッチング方法を用いてマッチング処理を行うことにより、対象画像Ｓ（図１２（ｃ））と参照画像Ｒにおける対象物だけの画像（図１２（ｂ））とに基づいてスポッティング点を求めることができ、求められたスポッティング点に基づいて、図１２（ｃ）に示される対象画像Ｓから、図１２（ｄ）に示すように、参照画像Ｒに示された類似する画像パターンである子供の顔の画像だけを抽出することが可能となる。
【００９８】
以上、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムについて図面を用いて説明を行ったが、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムは、上述した実施の形態に示した例に限定されるものではない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものである。
【００９９】
また、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムを、さまざまコンピュータサイエンスに応用することが可能である。
【０１００】
例えば、本実施の形態に示した２次元連続動的計画法を用いて画像パターンのマッチング処理を行うと共に、この画像パターンのマッチング処理に因子分解法を組み合わせることによって、図１３に示すように、対象物が示された少ない枚数の画像に基づいて、対象物の３次元形状を復元することも可能となる。このため、数枚の画像に基づいて、対象物を３次元的な視点で、さらに、自由な視点角度（視点方向）で表示させることが可能となる。
【０１０１】
さらに、本実施の形態に示した２次元連続動的計画法を用いた画像パターンのマッチング処理を応用することにより、医療用の撮影画像（例えば、ＣＴ（Computed Tomography：コンピュータ断層撮影）画像）における病変患部の検出処理に利用することが可能である。
【０１０２】
一般的に、ＣＴ画像などを用いて診断を行う場合には、医師が、撮影されたＣＴ画像と正常な人間のＣＴ画像とを比較して、撮影されたＣＴ画像に疑わしい部位が含まれていないかどうかを判断することにより、患部の特定が行われる。この判断において重要な点は、正常な画像と疑わしい部位が含まれる画像との違いを計算機で判断することは、困難であるということである。人間が２つの画像における類似・非類似を判断することは比較的簡単であるが、このような判断の簡単さは、人間が非線形の画像変形を容易に判断する能力を備えているためである。一方で、計算機を用いてこの非線形の変形を検出することは容易ではなかった。
【０１０３】
本実施の形態に示した画像パターンのマッチング処理を用いることにより、非線形の変動を考慮したマッチング処理を行うことが可能となるため、画像における正常な部位と疑わしい部位との差異を容易に検出することが可能となる。
【０１０４】
さらに、本実施の形態に示した画像パターンのマッチング処理を、ＣＴ画像のスライス画像群に適用することにより、ピクセル単位でスライス画像全体を通じた対応関係を求めることができる。このため、器官の部位を指定することにより、その部位に対応するピクセル対応を求めることができ、その器官のみの３Ｄ画像を容易に抽出することが可能となる。
【符号の説明】
【０１０５】
１ …画像パターンマッチング装置
２ …ＣＰＵ（画像処理手段）
３ …ＲＯＭ
４ …ＲＡＭ
５ …記録部（記録手段）
６ …ディスプレイ部
７ …操作部
Ｒ …参照画像
Ｓ …対象画像
【技術分野】
【０００１】
本発明は、画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムに関し、より詳細には、類似するパターン画像が記録された複数の画像（例えば、一の画像を参照画像、他の画像を対象画像とする）において、類似する画像パターンの各画素をそれぞれの画像より抽出することによって、画素毎の対応関係を求めることが可能な画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムに関する。
【背景技術】
【０００２】
従来より、類似する画像パターンが示された異なる画像において、対応する画像間のピクセル（画素）の対応関係を求めたり、対応する特徴抽出点を求めたりする方法が考えられている。このような対応するピクセルの抽出処理は、画像応用処理分野における画像認識手法、特徴点トラッキング手法、対象物の平面画像に基づいて対象物を３次元的に復元する手法などのさまざまなコンピュータサイエンスに応用することが可能となっている。しかしながら、コンピュータサイエンスにおける応用範囲が広いにもかかわらず、画像パターンの認識処理技術に関する決定的な手法が未だに確立されていないという問題があった。
【０００３】
例えば、画像間のピクセル対応問題を扱った手法として、動的計画法を利用する方法が提案されている（例えば、非特許文献１〜非特許文献３参照）。ここで、動的計画法とは、多変数の最適化を求める問題を解くための手法であって、最短経路問題などに利用される方法である。動的計画法では、「最適経路中の部分経路も、その部分経路における最適な経路により構成されている」という最適性の原理を利用する。このように最適性の原理を利用することにより、問題全体を部分問題における最適な解（決定）の積み重ねによって求めることができる。
【０００４】
このような動的計画法を応用した事例として、例えば、マッチングされる２つの画像の双方について領域を固定することにより、手書き文字認識を２次元非線形問題として求める研究が行われている（例えば、非特許文献４参照）。
【０００５】
また、今日では、入力時系列中の検索区間を事前に定めることなく、マッチング区間の抽出を行う連続動的計画法（１次元パターンでのセグメンテーションフリーの非線形マッチングを行う手法）が提案され（例えば、非特許文献５参照）、さらに１次元の連続動的計画法を２次元に拡張した２次元連続動的計画法が提案されている（例えば、非特許文献６参照）。２次元連続動的計画法を用いることにより、複数の画像から対象となる画像パターンの認識と抽出とを同時に行うことが可能となっている。
【０００６】
一方で、動画像において特徴点を抽出する処理や、特徴点などに基づいて対象物の３次元形状を復元する処理に関する研究が行われている。特徴点などに基づいて対象物の３次元形状を復元する処理では、動画を構成する画像間での適切な対応関係を求めることが重要となっており、この対応関係を求めることにより特徴点の追跡が可能となる。従来より数多く用いられる特徴点の追跡方法として、ＫＬＴ方法が知られている（例えば、非特許文献７参照）。
【０００７】
また、異なる特徴点の追跡方法として、ＳＩＦＴ特徴量を用いた手法も提案されている（例えば、特許文献８参照）。ＳＩＦＴ特徴量を用いた手法は、物体のスケール変化、物体の回転、物体の平行移動に対して影響を受けない（不変となる）特徴点を抽出することを特徴としており、その特徴点の抽出は１２８次元のベクトルにより構成されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】C. Myers, L. Rabiner, A. Rosenberg, “Performance tradeoffs in dynamic time warping algorithms for isolated word recognition”, IEEE Transactions on Acoustics, Speech and Signal Processing, 1980年12月, Vol.28, Issue 6, p.623−635
【非特許文献２】A.A. Amini, T.E. Weymouth, R.C. Jain, “Using dynamic programming for solving variational problems in vision”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990年9月, Vol. 12, No. 9, p.855−867
【非特許文献３】B. Serra, M. Berthod, Project PASTIS, INRIA, Sophia-Antipolis, “Subpixel contour matching using continuous dynamic programming”, Proceedings CVPR ’94 (IEEE Computer Society Conference on Computer Vision and Pattern Recognition), 1994年6月, p.202−207
【非特許文献４】S. Uchida, H. Sakoe, “An Efficient Two-Dimensional Warping Algorithm”, IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 社団法人電子情報通信学会1999年3月, Vol.E82-D, No. 3, p.693−700
【非特許文献５】R.Oka, “Spotting method for classification of real world data”, The Computer Journal, （イギリス）, Oxford Journal, 1998年,Vol. 41, No.8, p.559−565
【非特許文献６】T. Nishimura, R. Oka, ”Spotting Image Recognition using Two-Dimensional Continuous Dynamic Programming”, IEICE Technical Report (PRMU), 1997年7月, p.1−7
【非特許文献７】C. Tomasi, T. Kanade, “Detection and Tracking of Point Features”, Carnegie Mellon University Techinical Report, 1991年4月, CMU-CS-91-132
【非特許文献８】D.G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, Springer Netherlands, 2004年11月, Vol. 60, No.2, p.91−110
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上述した、２次元連続動的計画法を用いる方法では、参照画像の各行方向パターンのマッチング結果に基づいて列方向の累積を求める方法を用いているため、次述するピクセル間の単調連続性を保証することができなかった。このため、従来の２次元連続動的計画法を用いる方法では、２次元的に最適な対応関係を求めることが容易ではないという問題があった。
【００１０】
ここで、ピクセル間の単調性とは、マッチングの結果において、隣接するピクセル同士の相対的な位置関係場（上下左右の関係）が双方の画像の間において保持されている性質を意味し、連続性とは、マッチングの結果について対応点全体が自然なピクセル間の距離を保つ性質を意味している。この単調連続性を保つことにより、画像における基本的な特性を保持することが可能となり、画像間での適切な対応関係を求める処理において必要不可欠な要素となっている。
【００１１】
また、上述したＫＬＴ法は、動画像中の特徴点の対応に基づく追跡に用いられるトラッキング手法であり、微小時間でのピクセルの動きは平行移動だけしかせず、また、照明の変化に伴う輝度値の変化が生じないことを仮定して特徴点の追跡を行うことを特徴としている。このように、ＫＬＴ法では、微小時間中での特徴点の平行移動を仮定しているため、連続的に観測された画像系列でのトラッキングのみを対象とし、連続観測されたものでない異なる画像間における特徴点の抽出処理では、十分な機能を発揮することが困難であるという問題があった。
【００１２】
一方で、上述したＳＩＦＴ特徴量を用いた手法では、特徴点の対応を扱っているが、ベクトル要素で構成された特徴点を、異なる画像毎に求め、それぞれの画像において求められた特徴点に最も近い特徴点を対応付けることにより、特徴点の追跡を行う方法を採用する。このため、特徴点同士の対応付けは可能であっても、ピクセル単位で１対１の対応付けを行うことができず、また、対応付けられた特徴点もそれらしい点の対応に留まってしまうという問題があった。
【００１３】
さらに、ＳＩＦＴ特徴量を用いた特徴点の追跡手法では、対応付けられた特徴点において上述した単調性が保証されないという問題があった。ＳＩＦＴ特徴量を用いた手法により求められる特徴点の対応関係は、特徴点に関する類似性のみに基づいて求められているため、位置関係を求める手法として使えるまでには至っていなかった。
【００１４】
また、ＳＩＦＴ特徴量を用いた特徴点の追跡手法では、対象物以外の領域が含まれた状態で特徴点が求められるため、背景が変化するシーンなどにおいては追跡精度が低下し、追跡処理に失敗してしまうことがあるという問題があった。
【００１５】
本発明は、上記問題に鑑みてなされたものであり、動画に限定されることなく、異なる任意の画像中における対象物画像（画像パターン）の対応を、ピクセル間の単調連続性を確保しつつ画素毎に求めることが可能な画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチングプログラムを提供することを課題とする。
【課題を解決するための手段】
【００１６】
上記課題を解決するために、本発明に係る画像パターンマッチング装置は、互いに類似する画像パターンを含み得る一の画像と他の画像との画素毎の対応関係を求める画像パターンマッチング装置であって、前記一の画像と他の画像とを記録する記録手段と、前記一の画像と前記他の画像とにおける類似する画像パターンの画素毎の対応関係を求める画像処理手段とを有し、該画像処理手段は、前記一の画像を構成する画素の画素位置をｉ座標およびｊ座標を用いて特定するとともに、前記他の画像を構成する画素の画素位置をｍ座標およびｎ座標を用いて特定し、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画素間距離を積み上げ計算することにより算出し、算出された前記最小累積距離に基づいて、類似した画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求め、前記積み上げ計算を行う場合には、前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、前記最小累積距離の算出処理を行う場合には、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うことを特徴とする。
【００１７】
また、本発明に係る画像パターンマッチング方法は、画素位置をｉ座標およびｊ座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をｍ座標およびｎ座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング方法であって、画像処理手段が、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画像間距離を積み上げ計算することにより算出する最小累積距離算出ステップと、前記画像処理手段が、該最小累積距離算出ステップにおいて算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求める対応画素算出ステップとを有し、前記最小累積距離算出ステップにおいて、前記積み上げ計算を行う場合には、前記画像処理手段が、前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、前記最小累積距離の算出処理を行う場合には、前記画像処理手段が、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うことを特徴とする。
【００１８】
さらに、本発明に係る画像パターンマッチング用プログラムは、画素位置をｉ座標およびｊ座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をｍ座標およびｎ座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング用プログラムであって、コンピュータに、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画像間距離を積み上げ計算させることにより算出させる最小累積距離算出機能と、該最小累積距離算出機能により算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求めさせる対応画素算出機能とを実現させ、前記最小累積距離算出機能には、前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行させる積み上げ計算順番機能と、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行わせる累積座標間距離算出機能とが含まれることを特徴とする。
【００１９】
ここで、一の画像と他の画像は、互いに類似する画像パターンを含み得る画像であればよい。このため、類似する画像パターンが、一の画像および他の画像の両方の画像に含まれる場合はもちろんのこと、いずれか一方の画像にしか含まれない場合（つまり、類似する画像パターンが両方の画像に含まれない場合）であっても、互いに類似する画像パターンを含み得る場合に該当する。
【００２０】
このように、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムでは、積み上げ計算を行う場合において、ｍ座標およびｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行する。このため、積み上げ計算の値（解）が、現在の決定値（決定解）の直前の２つあるいは１つの決定値（決定解）に基づいて求められることになり、（ｍ，ｎ）平面における２次元の単調連続性を累積時に確保することが可能となる。
【００２１】
なお、単調連続性における単調性とは、マッチングの結果において、隣接する画素同士の相対的な位置関係場（上下左右の関係）が双方の画像の間において保持されている性質を意味し、単調連続性における連続性とは、マッチングの結果について対応点全体が自然なピクセル間の距離を保つ性質を意味している。
【００２２】
また、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムでは、最小累積距離の算出処理を行う場合において、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行う。このように、直前の座標位置からの遷移状態を所定の遷移パターンに制限することにより、直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出が行われるので、算出された前記最小累積距離に基づいて、類似する画像パターンに対応する一の画像の画素位置と他の画像の画素位置との対応関係を求める処理（バックトレース処理）において単調連続性を保証することが可能となる。
【００２３】
さらに、上述した画像パターンマッチング装置において、前記画像処理手段は、前記最小累積距離の算出処理を行う場合に、前記最小累積距離の計算を、前記ｍ座標方向に関する最小累積距離の計算と前記ｎ座標方向に関する最小累積距離の計算とに要素分割を行った上で、前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行うものであってもよい。
【００２４】
また、上述した画像パターンマッチング方法の前記最小累積距離算出ステップは、前記画像処理手段が、前記最小累積距離の算出処理を行う場合に、前記最小累積距離の計算を、前記ｍ座標方向に関する最小累積距離の計算と、前記ｎ座標方向に関する最小累積距離の計算とに要素分割を行う分割ステップと、前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う積み上げ計算ステップとを有するものであってもよい。
【００２５】
さらに、上述した画像パターンマッチング用プログラムにおいて、前記積み上げ計算順番機能は、前記最小累積距離の計算を、前記ｍ座標方向に関する最小累積距離の計算と、前記ｎ座標方向に関する最小累積距離の計算とに要素分割させる分割機能と、前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行わせる積み上げ計算機能とを有するものであってもよい。
【００２６】
このように、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムでは、最小累積距離の計算を、ｍ座標方向に関する最小累積距離の計算と、ｎ座標方向に関する最小累積距離の計算とに要素分割した上で、ｍ座標方向に関する最小累積距離の計算およびｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向およびｊ座標方向のそれぞれの方向に対する遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限して積み上げ計算を行うため、画素間の非線形対応関係を確保することが可能となる。また、算出された最小累積距離に基づいて、類似する画像パターンに対応する一の画像の画素位置と他の画像の画素位置との対応関係を求める処理（バックトレース処理）において、単調連続性をより確実に確保することが可能となる。
【発明の効果】
【００２７】
本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムによれば、積み上げ計算を行う場合において、ｍ座標およびｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行する。このため、積み上げ計算の値（解）が、現在の決定値（決定解）の直前の２つあるいは１つの決定値（決定解）に基づいて求められることになり、（ｍ，ｎ）平面における２次元の単調連続性を累積時に確保することが可能となる。
【００２８】
また、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムによれば、最小累積距離の算出処理を行う場合において、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行う。このように、直前の座標位置からの遷移状態を所定の遷移パターンに制限することにより、直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出が行われるので、画素間の非線形対応関係を確保することが可能となり、さらに、算出された前記最小累積距離に基づいて、類似する画像パターンに対応する一の画像の画素位置と他の画像の画素位置との対応関係を求める処理（バックトレース処理）において単調連続性を保証することが可能となる。
【図面の簡単な説明】
【００２９】
【図１】実施の形態に係る画像パターンマッチング装置の概略構成を示したブロック図である。
【図２】実施の形態に示されたｉ,ｊ,ｍ,ｎの４つの要素からなる４次元空間に基づいて、対象画像Ｓと参照画像Ｒとのピクセル（画素）毎の対応関係を示した図である。
【図３】（ａ）は、実施の形態に示されたランクＬの決定方法を説明するための図であり、（ｂ）は、各データ点における累積方向を示した図である。
【図４】実施の形態に示された画像復元における４点メッシュの制約条件を説明するための図である。
【図５】参照画像Ｒでの対応点がメッシュ構造を成すために、対象画像Ｓ上で（ξ（ｍ，ｎ），η（ｍ，ｎ））に至る出発点が取り得る点の候補を示した図である。
【図６】（ａ）は、実施の形態に示されたｉ方向への７パターンの遷移状態を示した図であり、（ｂ）は、ｊ方向への７パターンの遷移状態を示した図である。
【図７】局所距離Ｄ（ｉ，ｊ，ｍ，ｎ）＝Ｄ（ξ（ｍ，ｎ），η（ｍ，ｎ），ｍ，ｎ）が、４次元空間から対象画像Ｓの（ｉ，ｊ）平面に射影された状態を、（ａ）に示すｍ方向と、（ｂ）に示すｎ方向とに要素分割して示した図である。
【図８】（ａ）（ｂ）は、実施の形態に係るｄｘｘ（ｉ，ｊ，ｍ，ｎ）の構成を示した図であり、（ｃ）（ｄ）は、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）の構成を示した図である。
【図９】（ａ）（ｂ）は、実施の形態に係るｄｘｙ（ｉ，ｊ，ｍ，ｎ）の構成を示した図であり、（ｃ）（ｄ）は、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の構成を示した図である。
【図１０】実施の形態に示した参照画像Ｒから対象物以外の画像を取り除くことにより、対象物だけの画像を抽出する過程を説明するための図である。
【図１１】実施の形態に係るＣＰＵが、プログラムに基づいて実行する画像パターンのマッチング処理を示したフローチャートである。
【図１２】実施の形態に示した画像パターンのマッチング方法を用いることにより、子供の顔が含まれる参照画像Ｒに基づいて、対応する子供の顔の画像パターンを、対象画像Ｓから抽出する処理を説明するための図である。
【図１３】実施の形態に示した画像パターンのマッチング方法を応用して用いることにより、対象物が示された少ない枚数の画像に基づいて、対象物の３次元形状を復元することが可能となる旨を示した図である。
【発明を実施するための形態】
【００３０】
以下、本発明に係る画像パターンマッチング装置について、図面を用いて詳細に説明する。
【００３１】
図１は、画像パターンマッチング装置の概略構成を示したブロック図である。画像パターンマッチング装置１は、一般的なコンピュータにより構成することができ、図１に示すように、ＣＰＵ（Central Processing Unit）（画像処理手段）２と、ＲＯＭ（Read Only Memory）３と、ＲＡＭ（Random Access Memory）４と、記録部（記録手段）５と、ディスプレイ部６と、操作部７とにより概略構成されている。
【００３２】
ＣＰＵ２は、後述する画像パターンのマッチング処理を行う機能を有している。ＣＰＵ２は、後述する処理プログラム（例えば、図１１に示すフローチャートに基づくプログラム）に従って、画像パターンのマッチング処理を行う。ＲＡＭ４は、ＣＰＵ２の処理に利用されるワークエリアとして用いられる。ＲＯＭ３には、上述した画像パターンのマッチング処理に関するプログラム等が記録されている。ＣＰＵ２は、ＲＯＭ３より読み込んだプログラムに従って、画像パターンのマッチング処理を行う。
【００３３】
記録部５には、画像パターンのマッチング処理に用いられる画像データなどが記録されている。本実施の形態に係る記録部５は、一般的はハードディスクにより構成されている。なお、記録部５の構成は、ハードディスクだけに限定されるものではなく、フラッシュメモリ、ＳＳＤ（Solid State Drive / Solid State Disk）、ＣＤ―ＲＯＭドライブ、ＤＶＤドライブなどのように、画像パターンマッチング処理に用いられる複数の画像データをＣＰＵ２が読み出し可能な状態で記録することが可能なものであるならば、具体的な構成は特に限定されるものではない。
【００３４】
なお、本実施の形態に係る画像パターンマッチング装置１では、ＣＰＵ２において実行される画像パターンマッチング処理に関するプログラムを、ＲＯＭ３に記録する構成として説明を行うが、これらのプログラムは、記録部５に記録されるものであってもよい。
【００３５】
ディスプレイ部６は、記録部５に記録される画像データをユーザに対して視認可能に表示させ、また、ＣＰＵ２による画像パターンのマッチング処理結果を表示させる役割を有している。ディスプレイ部６には、液晶ディスプレイや、ＣＲＴディスプレイなどの一般的な表示装置が用いられる。
【００３６】
操作部７は、ユーザが画像パターンマッチング装置１を操作するために必要なデータの入力や、画像パターンマッチング装置１の具体的な操作などを行う場合に用いられる装置であって、一般的なキーボードやマウスなどにより構成される。
【００３７】
ＣＰＵ２は、ＲＯＭ３より演算処理に必要なプログラムを読み取り、読み取ったプログラムに従って、記録部５に記録される複数の画像データより類似する画像パターンの抽出を行う処理、より詳細には、異なる画像データに含まれる類似する画像パターンの全てのピクセル（画素）の対応関係を求める処理を行う。以下に、ＣＰＵ２が行う処理の内容を具体的に説明し、その後、ＣＰＵ２の具体的な処理手順を、フローチャートを示して説明する。
【００３８】
まず、ＣＰＵ２が行う処理内容を具体的に説明する。例えば、相異なる２つの画像データのうち、一方の画像データを対象画像Ｓ、他方の画像データを参照画像Ｒとして、対象画像Ｓに含まれている画像パターンから、参照画像Ｒに表される画像パターンの対応をピクセル単位で抽出する処理について説明する。
【００３９】
ＣＰＵ２は、対象画像Ｓを構成するピクセル位置と参照画像Ｒを構成するピクセル位置とを、それぞれ座標点を用いて特定する。具体的に、ＣＰＵ２は、対象画像Ｓをｉ要素とｊ要素とを備える（ｉ，ｊ）平面における座標点のピクセルの集合として捉える。
【数１】
但し、対象画像Ｓのピクセル位置は、１≦ｉ≦Ｉ（定数）、１≦ｊ≦Ｊ（定数）の範囲で特定されるものとする。
【００４０】
一方で、ＣＰＵ２は、参照画像Ｒをｍ要素とｎ要素とを備える（ｍ，ｎ）平面における座標点のピクセルの集合として捉える。
【数２】
但し、参照画像Ｒのピクセル位置は、１≦ｍ≦Ｍ（定数）、１≦ｎ≦Ｎ（定数）の範囲で特定されるものとする。
【００４１】
さらに、ＣＰＵ２は、対象画像Ｓの各ピクセルの値をＳｐ（ｉ，ｊ）＝（ｒ，ｇ，ｂ）として記録部５に記録し、また、参照画像Ｒの各ピクセルの値をＲｐ（ｍ，ｎ）＝（ｒ，ｇ，ｂ）として記録する。なお、（ｒ，ｇ，ｂ）は、対応するピクセルの色彩データ（ｒ：赤、ｇ：緑、ｂ：青）を示している。
【００４２】
このように、ＣＰＵ２は、対象画像Ｓのｉ要素，ｊ要素と、参照画像Ｒのｍ要素，ｎ要素とに基づいて、ｉ，ｊ，ｍ，ｎの４つの要素からなる４次元の空間（局地距離累積空間）を構成し、対象画像Ｓと参照画像Ｒとの画像パターンのマッチングを、それぞれの画像（対象画像Ｓおよび参照画像Ｒ）におけるピクセル（画素）毎の対応関係式（後述する）を用いることにより判断する。
【００４３】
図２は、ｉ，ｊ，ｍ，ｎの４つの要素からなる４次元の空間に基づいて、対象画像Ｓと参照画像Ｒとのピクセル（画素）毎の対応関係を図示したものである。対象画像Ｓの各ピクセル（ｉ，ｊ）に対して、参照画像Ｒのｍ要素、ｎ要素からなる平面の存在を考えることにより、４次元の空間を構築する。
【００４４】
ＣＰＵ２は、類似する画像パターンを含む画像同士で画像パターンのマッチング処理を行う場合に、対応する参照画像Ｒの画素の座標点に対応する座標点を、対象画像Ｓの画素より求めて、対応する参照画像Ｒから対象画像Ｓへの写像を、写像Ｒ→Ｓとして定義する。つまり、
（ｍ，ｎ）∈Ｒについて（参照画像Ｒに属する座標点（ｍ，ｎ）について）
（ｍ，ｎ）⇒（ξ（ｍ，ｎ），η（ｍ，ｎ）） ・・・式３
となるξとηの２つの関数が考えられている。
【００４５】
ここで、
ξ（Ｍ，Ｎ）＝ｉ、 η（Ｍ，Ｎ）＝ｊ ・・・式４
となる対応点を累積の終点として考える（但し、Ｍは、参照画像Ｒにおける最大値となるｍ要素の値、Ｎは、参照画像Ｒにおける最大値となるｎ要素の値を示している）。
【００４６】
累積時に与えられる各点に対する重みをｗ（ｉ，ｊ，ｍ，ｎ）とし、また、対応するピクセルの対象画像Ｓの座標（ｉ，ｊ）と参照画像Ｒの座標（ｍ，ｎ）との距離（ピクセル間距離）をｄ（ｉ，ｊ，ｍ，ｎ）として、２次元連続動的計画法を用いることにより最小累積距離を示す積み上げ空間を求める。この積み上げ空間の最終累積値における最小値をスポッティング点という。このようにして求められる２次元連続動的計画法による最小累積距離の積み上げ空間Ｊ（ｉ，ｊ）は、以下の評価式で実現される。
【数３】
【００４７】
なお、この累積値を求める場合には、図３（ａ）に示すように、（ｍ＋ｎ）に基づいてランクＬを決定し、参照画像Ｒの対角方向に対して、下から順番に累積値を積み上げて計算を行う。このようにして積み上げ計算を行うことにより、各データ点（ｍ，ｎ）に与えられる累積方向は、図３（ｂ）に示すように、２入力方向（ｍ方向およびｎ方向）および２出力方向（ｍ方向およびｎ方向）となる。また、この積み上げ計算により現在の座標における累積値が、その直前の２つ（あるいは１つ）の累積値に基づいて求められることになる。
【００４８】
式５に示すξ（ｍ，ｎ）において最適となる解をξ＊（ｍ，ｎ）と定義し、また、η（ｍ，ｎ）において最適となる解をη＊（ｍ，ｎ）と定義すると、式５に示すＷは、最適な累積の重みを示すものとして以下のように定義することができる。
【数４】
【００４９】
このようにして４次元空間に基づいて対応点を求めると、図２に示すように４次元空間において参照画像Ｒのピクセル（画素）と対象画像Ｓのピクセル（画素）とが対応する座標Ｄ（ｉ，ｊ，ｍ，ｎ）を求めることができる。この座標Ｄ（ｉ，ｊ，ｍ，ｎ）を（ｉ，ｊ）平面に射影することにより、対応する対象画像Ｓの座標を求めることができ、また、（ｍ，ｎ）平面に射影することにより、対応する参照画像Ｒの座標を求めることができる。従って、この参照画像Ｒと対象画像Ｓとにおける座標の対応を求めることによって、参照画像Ｒの画像パターンの座標（ｍ，ｎ）に対応する対象画像Ｓの画像パターンの座標（ｉ，ｊ）を求めることができ、ピクセル単位で対応関係を示すことが可能となる。
【００５０】
なお、上述したように、参照画像Ｒと対象画像Ｓとの対応点（ピクセル、画素）を求めることができる場合には、対応点（ピクセル、画素）が変形しても、また、それぞれの対応点（ピクセル、画素）が画像上で変形しても、メッシュ構造として（物体の形状を表現するために使われるデータとして）それぞれが保たれている必要がある。このように、双方でメッシュ構造が保たれていることを、本実施の形態に係る説明では、「単調連続性の保証」という言葉で表現する。
【００５１】
ここで、単調性とは、画像パターンのマッチング前後で隣接するピクセル同士の相対的な位置関係（上下左右の関係）が保持される性質を意味し、連続性とは、マッチングの前後で対応点において自然なピクセル間の距離を保つ性質を意味している。なお、上述した積み上げ計算処理では、ランクＬを定義することにより参照画像Ｒの対角方向に対して累積値の積み上げ計算を行うので、参照画像Ｒにおける２次元的な単調連続性が累積時に反映されることになり、「単調連続性の保証」が確保されることになる。
【００５２】
次に、ｉ要素およびｊ要素を含めた全体としての「単調連続性の保証」を確保するための条件を説明する。
【００５３】
図４は、画像復元における４点メッシュの制約条件を説明するための図である。図４は、説明を簡単にするために線形の場合（つまり、拡大縮小回転のない場合）における説明図を示している。なお、実際の適用段階においては、拡大縮小回転を行うことにより、最適なマッチング処理を行うことが可能になる場合もある。
【００５４】
図４は、図２に示したように、対象画像Ｓの各ピクセルにおいて参照画像Ｒの座標平面を考えることにより構成された４次元の空間を示している。また、図４には、参照画像Ｒの座標（ｍ，ｎ）に対応する対象画像Ｓの座標（ｉ，ｊ）＝（ξ（ｍ，ｎ），η（ｍ，ｎ））が示されており、また、対象画像Ｓ上で（ｉ，ｊ）＝（ξ（ｍ，ｎ），η（ｍ，ｎ））へと対応点が変化する場合において、参照画像Ｒにおける対象点のメッシュ構造を確保しつつ、その対象点に至ることが可能な出発点（座標）の集合が表されている。図４に示す場合では、参照画像Ｒにおける点（ｍ−１，ｎ−１）に対応可能な出発点は、点（ｍ，ｎ）、点（ｍ，ｎ−１）および点（ｍ−１，ｎ）によって決定されることになる。
【００５５】
２次元的な単調性および連続性を保証するために、参照画像Ｒのｍ方向に対応する対象画像Ｓの移動可能な点（局所パス：遷移状態）の集合を
Ｋ（ｍ，ｎ）＝｛(ξ（ｍ−１，ｎ），η（ｍ−１，ｎ）)｝とし、
参照画像Ｒのｎ方向に対応する対象画像Ｓの移動可能な点（局所パス：遷移状態）の集合を
Ｌ（ｍ，ｎ）＝｛（ξ（ｍ，ｎ−１），η（ｍ，ｎ−１））｝とすると、
点（ｍ−１，ｎ−１）に対応する点（ξ（ｍ−１，ｎ−１），η（ｍ−１，ｎ−１））は、
【数５】
を満たす必要がある。
【００５６】
式７において、Ｋ（ｍ，ｎ）は、（ξ（ｍ，ｎ），η（ｍ，ｎ））にｍ方向から１回の遷移で至る４次元空間の点集合を、対象画像Ｓに射影した点の候補（集合）を示すことになり、Ｌ（ｍ，ｎ）は、（ξ（ｍ，ｎ），η（ｍ，ｎ））にｎ方向から１回の遷移で至る４次元空間の点集合を、対象画像Ｓに射影した点の候補（集合）を示すことになる。
【００５７】
また、式７における
【数６】
は、式の左辺に示す点から右辺に示す式の集合を接合する意味（テンソル積）を示している。
【００５８】
この式７を満たす場合には、局所的に単調性および連続性を保証した４点（ｍ，ｎ）、（ｍ，ｎ−１）、（ｍ−１，ｎ）、（ｍ−１，ｎ−１）を用いたメッシュが、図４に示すように作成される。なお、図４は、上述したように線形の場合（つまり、拡大縮小回転のない場合）を示している。
【００５９】
従って、図４に示すように、点（ｍ−１，ｎ−１）から点（ｍ，ｎ）に至る場合において、２つの局所パスが点（ｍ，ｎ−１）と（ｍ−１，ｎ）とを通るときに、参照画像Ｒ上でメッシュ構造を作ることが可能となる。そして、これに対応するようにして非線形の変形が行われた場合には、対象画像Ｓ上でもメッシュ構造を作ることが可能であるため、２つのパスのそれぞれが、２回の遷移で変化可能な出発点の集合である
【数７】
と
【数８】
と
に重なる範囲内において（ξ（ｍ−１，ｎ−１），η（ｍ−１，ｎ−１））が存在すれば良いことになる。
【００６０】
図５は、参照画像Ｒでの対応点がメッシュ構造を成すために、対象画像Ｓ上で（ξ（ｍ，ｎ），η（ｍ，ｎ））に至る出発点が取り得る点の集合（候補）を太い点（●：黒丸）で示した図である。図５では、対象画像Ｓにおける（ξ（ｍ，ｎ），η（ｍ，ｎ））に至る出発点として、Ｋ（ｍ，ｎ）で示される出発点（ξ（ｍ−１，ｎ），η（ｍ−１，ｎ））と、Ｌ（ｍ，ｎ）で示される出発点（ξ（ｍ，ｎ−１），η（ｍ，ｎ−１））とを取ることが可能であり、さらに、
【数９】
で示される出発点（ξ（ｍ−１，ｎ−１），η（ｍ−１，ｎ−１））を取ることが可能であることが示されている。
【００６１】
また、２次元連続動的計画法では、累積時に局所パス（上述した移動可能な出発点から遷移状態）に対して幾何学的な制約を与えることによって、それぞれピクセル間の非線形変形度合いを決めることができる。
【００６２】
図６（ａ）および図６（ｂ）は、局所パスにおける遷移の状態（方向）の制限を示した図であり、具体的に図６（ａ）の上段図には、ｉ方向への移動を基本とした遷移状態が７パターン示されており、図６（ｂ）の上段図には、ｊ方向への移動を基本とした遷移状態が７パターン示されている。また、図６（ａ）の下段図には、図６（ａ）の上段図に示した７パターンの遷移状態に基づいて、黒丸で示された座標へ遷移が行われる直前に位置し得る座標位置が白丸で示されており、図６（ｂ）の下段図には、図６（ｂ）の上段図に示した７パターンの遷移状態に基づいて、黒丸で示された座標において遷移が行われる直前に位置し得る座標位置が白丸で示されている。
【００６３】
図６（ａ）（ｂ）に示すように、累積値の積み上げ処理において、移動方向を示す局所パスに対してそれぞれ７パターンのパス制約を加えることにより、（パターン１）等倍、（パターン２）等倍＋４５度回転、（パターン３）等倍−４５度回転、（パターン４）２倍、（パターン５）２倍＋４５度回転、（パターン６）２倍−４５度回転、（パターン７）縮小を許容したピクセル間の非線形変形を実現することが可能となる。なお、縮小は、累積時および後述するバックトラック時における制約として、連続縮小に関する制限を与えることにより実現される。
【００６４】
このように、ＣＰＵ２において局所パスに対して図６（ａ）（ｂ）に示すような遷移パターンを設定することにより、単調連続性の保証を確保することが可能となる。
【００６５】
次に、画像パターンのマッチング処理に用いられる局所距離について説明する。画像パターンのマッチング処理における計算は、局所距離と呼ばれる値を累積することにより実行される。局所距離は、対象画像Ｓの（ｉ，ｊ）点でのピクセル（カラー画像の場合には、ｒ（赤：），ｇ（緑：），ｂ（青：）の３要素を備えている）と、参照画像Ｒの（ｍ，ｎ）点でのピクセル（同様に、カラー画像の場合には、ｒ（赤：），ｇ（緑：），ｂ（青：）の３要素を備えている）との間で、以下のように定義される。
【数１０】
【００６６】
ここで、ｋの値は、参照画像Ｒ（ｉ,ｊ）および対象画像Ｓ（ｉ,ｊ）がカラー画像である場合における各色彩を示しており、ｋ＝１は、参照画像Ｒ（ｉ,ｊ）および対象画像Ｓ（ｉ,ｊ）のｒ（赤：）に該当し、ｋ＝２は、参照画像Ｒ（ｉ,ｊ）および対象画像Ｓ（ｉ,ｊ）のｇ（緑：）に該当し、ｋ＝３は、参照画像Ｒ（ｉ,ｊ）および対象画像Ｓ（ｉ,ｊ）のｂ（青：）に該当する。なお、ｄ（ｉ，ｊ，ｍ，ｎ）の値は、０≦ｄ（ｉ，ｊ，ｍ，ｎ）≦１となる。
【００６７】
また、２次元連続動的計画法では、上述したように２種類の局所パスを選択するように設計されており、この局所パスは、上述した４つのポイント（ｍ，ｎ）、（ｍ−１，ｎ）、（ｍ，ｎ−１）、（ｍ−１，ｎ−１）のつながりに基づいて求められる。これらの４ポイントのつながりを変数として表すと、上述した局所距離ｄ（ｉ，ｊ，ｍ，ｎ）における４ポイントの関係から、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つの変数を用いて示すことができる。
【００６８】
図７は、４つの変数に基づいてそれぞれ累積された局所距離Ｄ（ｉ，ｊ，ｍ，ｎ）＝Ｄ（ξ（ｍ，ｎ），η（ｍ，ｎ），ｍ，ｎ）が、４次元空間から対象画像Ｓの（ｉ，ｊ）平面に射影された状態を示している。図７に示すように局所距離Ｄ（ｉ，ｊ，ｍ，ｎ）を、ｍ方向要素とｎ方向要素とに要素分割することにより、２方向から対象画像Ｓに対応させて局所距離Ｄの累積計算を行うことができる。図７では、累積距離Ｄ（ξ（ｍ，ｎ），η（ｍ，ｎ），ｍ，ｎ）が、ｍ方向（Ｋ（ξ（ｍ，ｎ），η（ｍ，ｎ））の累積距離Ｄ（Ｋｘ（ξ（ｍ，ｎ），η（ｍ，ｎ）），Ｋｙ（ξ（ｍ，ｎ），η（ｍ，ｎ）），ｍ−１，ｎ）と、ｎ方向（Ｌ（ξ（ｍ，ｎ），η（ｍ，ｎ））の累積距離Ｄ（Ｌｘ（ξ（ｍ，ｎ），η（ｍ，ｎ）），Ｌｙ（ξ（ｍ，ｎ），η（ｍ，ｎ）），ｍ，ｎ−１）とにより算出される場合が示されている。
【００６９】
次に、上述したｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つ値の決定方法について説明する。
【００７０】
まず、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）は、４次元空間から（ｍ，ｎ）平面へと射影された局所距離計算点群の最上点（ｉ，ｊ，ｍ，ｎ）に割り当てられる４つの変数（座標点）の１つである。図８（ａ）は、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）を示しており、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）は、図８（ｂ）に示すように、射影点（ｉ’，ｊ’，ｍ，ｎ）に割り当てられる変数であるｄｘｘ（ｉ’，ｊ’，ｍ−１，ｎ）と、ｄ（ｉ，ｊ，ｍ，ｎ）の値との和によって算出される。なお、局所距離ｄｘｘ（ｉ’，ｊ’，ｍ−１，ｎ）は、図８（ｂ）の長方形部分に射影された４つの局所距離の加算により求められる値である。
【００７１】
次に、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）は、図８（ｃ）のように示される。ｄｙｙ（ｉ，ｊ，ｍ，ｎ）は、図８（ｄ）に示すように、射影点（ｉ”，ｊ”，ｍ，ｎ−１）に割り当てられる変数であるｄｙｙ（ｉ”，ｊ”，ｍ，ｎ−１）と、局所距離ｄ（ｉ，ｊ，ｍ，ｎ）の値との和によって算出される。なお、ｄｙｙ（ｉ”，ｊ”，ｍ，ｎ−１）は、図８（ｄ）の長方形部分に射影された４つの局所距離の加算により求められる値である。
【００７２】
また、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）は、点（ｉ’，ｊ’，ｍ−１，ｎ）に割り当てられた２つの値であるｄｙｙ（ｉ’，ｊ’，ｍ−１，ｎ）とｄｘｙ（ｉ’，ｊ’，ｍ−１，ｎ）との加算により求められる。図９（ａ）は、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）を示しており、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）は、図９（ｂ）に示すように、図面上の大きな長方形内に示される射影された局所距離計算点を示すｄｘｙ（ｉ’，ｊ’，ｍ−１，ｎ）と、図面上の小さな長方形内に示される射影された局所距離計算点を示すｄｙｙ（ｉ’，ｊ’，ｍ−１，ｎ）とにより構成される。
【００７３】
さらに、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）は、点（ｉ”，ｊ”，ｍ，ｎ−１）に割り当てられた２つの値であるｄｘｘ（ｉ”，ｊ”，ｍ，ｎ−１）とｄｙｘ（ｉ”，ｊ”，ｍ，ｎ−１）との加算により求められる。図９（ｃ）は、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）を示しており、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）は、図９（ｄ）に示すように、図面上の大きな長方形内の射影局所距離計算点を示すｄｙｘ（ｉ”，ｊ”，ｍ，ｎ−１）と、図面上の小さな長方形内の射影局所距離計算点を示すｄｘｘ（ｉ”，ｊ”，ｍ，ｎ−１）とにより構成される。
【００７４】
上述した説明より、４つの変数の値は、
【数１１】
【数１２】
【数１３】
【数１４】
で示すことができ、点（ｉ，ｊ，ｍ，ｎ）における最小累積値（最小累積距離）Ｄ（ｉ，ｊ，ｍ，ｎ）は、
【数１５】
により求めることができる。
【００７５】
なお、上述した（ｉ’，ｊ’，ｍ−１，ｎ）および（ｉ”，ｊ”，ｍ，ｎ−１）は
【数１６】
【数１７】
の２式を用いて求めることができる。
【００７６】
式１７および式１８の｛｝内には、図６（ａ）および図６（ｂ）に示した７パターンの局所パス（遷移状態（方向）を制限した局所パス）を示す式が記載されている。ＣＰＵ２は、これらの７パターンの関係式を計算して、式の値が最小となるときの（ｉ’，ｊ’，ｍ−１，ｎ）の各要素の値と（ｉ’，ｊ’，ｍ，ｎ−１）の各要素の値とを抽出する。そして、ＣＰＵ２は、抽出された値を式１２〜式１５に代入することにより、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つ値を算出する。
【００７７】
そして、ＣＰＵ２は、算出されたｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）およびｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つ値を用いて、式１６により点（ｉ，ｊ，ｍ，ｎ）の最適累積値であるＤ（ｉ，ｊ，ｍ，ｎ）を求める。
【００７８】
なお、ＣＰＵ２は、初期値としてｍ＝１、ｎ＝１が与えられている状態において、ｍが１以上Ｍ以下となる条件を満たす間だけｍを１ずつ増加させるとともに、各ｍにおいて、ｎが１以上Ｎ以下となる条件を満たす間だけｎを１ずつ増加させることにより、全てのｍおよびｎにおいて（ｉ’，ｊ’，ｍ−１，ｎ）と（ｉ’，ｊ’，ｍ，ｎ−１）を求める。
【００７９】
さらに、ＣＰＵ２は、累積値の積み上げ計算を行うために、ランクＬの値に初期値としてＬ＝２を代入し、Ｌが２以上Ｍ＋Ｎ以下となる条件を満たす間だけＬを１ずつ増加させる処理を行うことによって、（ｍ，ｎ）平面における各座標（ｍ，ｎ）の値についての累積処理を行う。
【００８０】
このようにして求められる最適累積値Ｄ（ｉ，ｊ，ｍ，ｎ）は、上述した式１７および式１８に示すように、Ｄ（ｉ’，ｊ’，ｍ−１，ｎ）とＤ（ｉ”，ｊ”，ｍ，ｎ−１）とにより求められる値を用いて計算される。従って、最終的にＣＰＵ２は、対象画像Ｓの各（ｉ，ｊ）座標において上述した最適な累積値Ｄ（ｉ，ｊ，Ｍ，Ｎ）の値を、次の式１９に基づいて計算することができる。
【数１８】
【００８１】
このようにして求められる累積最適値Ｄ（ｉ，ｊ，Ｍ，Ｎ）は、上述したように、点（ｉ，ｊ）において２次元的に分布するパターンとして求められる。ここで、この２次元分布において局所的に最小となる点が、上述したスポッティング点である。つまり、対象画像Ｓの（ｉ，ｊ）に対応するスポッティング点は、Ｄ（ｉ，ｊ，Ｍ，Ｎ）における最小となる点であり、
【数１９】
により求められることになる。（ｉ，ｊ)平面上で、局所的な領域で最小点の値が閾値よりも小さい場合には、その局所領域の点において、参照画像Ｒに類似する対象画像Ｓの部分画像が最適にマッチングしていると判断することができる。したがって、そのような局所領域が複数ある場合は、複数個の類似の参照画像Ｒが存在することを意味することになる。
【００８２】
このため、スポッティング点において、累積最適値Ｄ（ｉ，ｊ，Ｍ，Ｎ）を出発点としてバックトレース処理を行うことにより、参照画像Ｒの部分領域を示す
（ξ＊（ｍ，ｎ），η＊（ｍ，ｎ）） 但し、１≦ｍ≦Ｍ，１≦ｎ≦Ｎ
を、以下のアルゴリズムに基づいて得ることができる。ここで、（ξ＊（ｍ，ｎ），η＊（ｍ，ｎ））は、対象画像Ｓの座標点（ｉ，ｊ）に対応している。
【００８３】
まず、ｍ，ｎは、それぞれ固定された値であると仮定する。すると
（ｉ＊，ｊ＊）は、
【数２０】
で示すことができ、（ｉ＊＊，ｊ＊＊）は、
【数２１】
で求めることができる。このため、（ξ＊（ｍ，ｎ），η＊（ｍ，ｎ））は、
（ξ＊（ｍ，ｎ），η＊（ｍ，ｎ））
＝（ｉ＊＊（ｍ，ｎ），ｊ＊＊（ｍ，ｎ）） ・・・式２３
により求めることができる。
【００８４】
この式２１〜式２３に基づいて、ｍの値をＭ≧ｍ≧１の範囲内でＭから１まで１ずつ減少させると共に、ｎの値をＮ≧ｎ≧１の範囲内でＮから１まで１ずつ減少させることにより、全てのｍおよびｎに対応する（ξ＊（ｍ，ｎ），η＊（ｍ，ｎ））を求めることができる。
このように、式２１〜式２３を繰り返し計算してバックトレース処理を行うことにより、参照画像Ｒに最適に対応する対象画像Ｓの部分画像を取り出すことが可能となる。
【００８５】
なお、通常、参照画像Ｒには特定の対象物の画像が示されているが、その画像の外縁形状はさまざまである。例えば、背景画像のように画像パターンのマッチング処理の対象とならない画像（対象物以外の画像）が含まれている場合には、適切に対象画像のみを抽出しないと、精度良く画像パターンのマッチング処理を行うことができない。このため、例えば図１０に示すように、対象物となる画像以外の領域の局所距離の値を１に設定することにより、背景部分を取り除くことが可能となり、参照画像Ｒにおいて対象物だけの画像をマッチング処理の対象とすることが可能となる。
【００８６】
次に、上述した処理内容を、図１１に示すフローチャートを示すことによって、ＣＰＵ２がプログラムに基づいて実行する画像パターンのマッチング処理について説明する。
【００８７】
まずＣＰＵ２は、まず、変数ｌに２を設定（ｌ＝２）する（ステップＳ．１）。次に、ＣＰＵ２は、変数ｍに１を設定（ｍ＝１）すると共に、変数ｎに１を設定（ｎ＝１）する（ステップＳ．２）。そして、ＣＰＵ２は、式１７に基づいて、（ｉ’，ｊ’，ｍ−１，ｎ）を求めると共に、式１８に基づいて、（ｉ”，ｊ”，ｍ，ｎ−１）を求める（ステップＳ．３）。
【００８８】
そして、ＣＰＵ２は、求められた（ｉ’，ｊ’，ｍ−１，ｎ）および（ｉ”，ｊ”，ｍ，ｎ−１）に基づいて、ｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つ値を算出する（ステップＳ．４）。
【００８９】
その後、ＣＰＵ２は、求められたｄｘｘ（ｉ，ｊ，ｍ，ｎ）、ｄｘｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｙ（ｉ，ｊ，ｍ，ｎ）、ｄｙｘ（ｉ，ｊ，ｍ，ｎ）の４つ値を用いて、式１６によりＤ（ｉ，ｊ，ｍ，ｎ）を求める（ステップＳ．５）。そして、ＣＰＵ２は、ｍおよびｎの値が、１≦ｍ≦Ｍおよび１≦ｎ≦Ｎの条件を満たすか否かの判断を行う（ステップＳ．６）。
【００９０】
ｍおよびｎの値が、１≦ｍ≦Ｍおよび１≦ｎ≦Ｎの条件を満たす場合（ステップＳ．６においてＹｅｓの場合）、ＣＰＵ２は、ｍおよびｎの値に１を加算し（ｍ＝ｍ＋１、ｎ＝ｎ＋１）（ステップＳ．７）、処理をステップＳ．３に移行する。
【００９１】
一方で、ｍおよびｎの値が、１≦ｍ≦Ｍおよび１≦ｎ≦Ｎの条件を満たさない場合（ステップＳ．６においてＮｏの場合）、ＣＰＵ２は、ｌの値が、２≦ｌ≦Ｍ＋Ｎの条件を満たすか否かの判断を行う（ステップＳ．８）。
【００９２】
ｌの値が、２≦ｌ≦Ｍ＋Ｎの条件を満たす場合（ステップＳ．８においてＹｅｓの場合）、ＣＰＵ２は、ｌの値に１を加算し（ｌ＝ｌ＋１）（ステップＳ．９）、処理をステップＳ．２に移行する。
【００９３】
一方で、ｌの値が、２≦ｌ≦Ｍ＋Ｎの条件を満たさない場合（ステップＳ．８においてＮｏの場合）、ＣＰＵ２は、求められた累積最適値Ｄ（ｉ，ｊ，Ｍ，Ｎ）に基づいて、バックトレース処理を行うことにより、対象画像Ｓのピクセルと参照画像Ｒのピクセルとの対応関係を求め（ステップＳ．１０）、画像パターンのマッチング処理を終了する。
【００９４】
このように、画像パターンのマッチング処理を行うことにより、非線形に対応する画像パターンの対応をピクセル毎に求めることが可能となる。さらに、このピクセル毎の対応を求める過程において、ランクＬという概念を採用し、（ｍ，ｎ）平面において画像の対角方向の累積値を積み上げることにより累積最適値Ｄを求めるので、累積時において局所的な単調連続性を確保することが可能となる。さらに、図６（ａ）および図６（ｂ）に示すように、局所パスに対して、遷移パターンを制限することにより累積最適値Ｄを求めるので、単調連続性の保証を確保することが可能となる。
【００９５】
従って、本実施の形態に示した画像パターンのマッチング方法を用いて求められる対象画像Ｓのピクセルと参照画像Ｒのピクセルとの対応関係は、非線形対応を許容しつつ、かつ、単調連続性の保証を確保することができ、さらに、動画のように連続した画像ではなく、類似する画像パターンが示された異なる少数の画像に基づいて、ピクセル毎の対応関係を求めることが可能となる。
【００９６】
図１２は、上述した画像パターンのマッチング方法を用いて子供の顔が含まれる参照画像Ｒに基づいて、対象画像Ｓより対応する画像を抽出する処理を説明するための図である。図１２（ａ）には、子供の顔が含まれる参照画像Ｒが示されており、（ｂ）には、背景画像などが取り除かれた対象物（子供の顔）だけの画像が示されている。
【００９７】
一方で、（ｃ）には、子供の顔の画像だけでなく、その背景画像や、他の人物の顔画像などが含まれる対象画像Ｓが示されている。ＣＰＵ２が上述した画像パターンのマッチング方法を用いてマッチング処理を行うことにより、対象画像Ｓ（図１２（ｃ））と参照画像Ｒにおける対象物だけの画像（図１２（ｂ））とに基づいてスポッティング点を求めることができ、求められたスポッティング点に基づいて、図１２（ｃ）に示される対象画像Ｓから、図１２（ｄ）に示すように、参照画像Ｒに示された類似する画像パターンである子供の顔の画像だけを抽出することが可能となる。
【００９８】
以上、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムについて図面を用いて説明を行ったが、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムは、上述した実施の形態に示した例に限定されるものではない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものである。
【００９９】
また、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムを、さまざまコンピュータサイエンスに応用することが可能である。
【０１００】
例えば、本実施の形態に示した２次元連続動的計画法を用いて画像パターンのマッチング処理を行うと共に、この画像パターンのマッチング処理に因子分解法を組み合わせることによって、図１３に示すように、対象物が示された少ない枚数の画像に基づいて、対象物の３次元形状を復元することも可能となる。このため、数枚の画像に基づいて、対象物を３次元的な視点で、さらに、自由な視点角度（視点方向）で表示させることが可能となる。
【０１０１】
さらに、本実施の形態に示した２次元連続動的計画法を用いた画像パターンのマッチング処理を応用することにより、医療用の撮影画像（例えば、ＣＴ（Computed Tomography：コンピュータ断層撮影）画像）における病変患部の検出処理に利用することが可能である。
【０１０２】
一般的に、ＣＴ画像などを用いて診断を行う場合には、医師が、撮影されたＣＴ画像と正常な人間のＣＴ画像とを比較して、撮影されたＣＴ画像に疑わしい部位が含まれていないかどうかを判断することにより、患部の特定が行われる。この判断において重要な点は、正常な画像と疑わしい部位が含まれる画像との違いを計算機で判断することは、困難であるということである。人間が２つの画像における類似・非類似を判断することは比較的簡単であるが、このような判断の簡単さは、人間が非線形の画像変形を容易に判断する能力を備えているためである。一方で、計算機を用いてこの非線形の変形を検出することは容易ではなかった。
【０１０３】
本実施の形態に示した画像パターンのマッチング処理を用いることにより、非線形の変動を考慮したマッチング処理を行うことが可能となるため、画像における正常な部位と疑わしい部位との差異を容易に検出することが可能となる。
【０１０４】
さらに、本実施の形態に示した画像パターンのマッチング処理を、ＣＴ画像のスライス画像群に適用することにより、ピクセル単位でスライス画像全体を通じた対応関係を求めることができる。このため、器官の部位を指定することにより、その部位に対応するピクセル対応を求めることができ、その器官のみの３Ｄ画像を容易に抽出することが可能となる。
【符号の説明】
【０１０５】
１ …画像パターンマッチング装置
２ …ＣＰＵ（画像処理手段）
３ …ＲＯＭ
４ …ＲＡＭ
５ …記録部（記録手段）
６ …ディスプレイ部
７ …操作部
Ｒ …参照画像
Ｓ …対象画像
【特許請求の範囲】
【請求項１】
互いに類似する画像パターンを含み得る一の画像と他の画像との画素毎の対応関係を求める画像パターンマッチング装置であって、
前記一の画像と他の画像とを記録する記録手段と、
前記一の画像と前記他の画像とにおける類似する画像パターンの画素毎の対応関係を求める画像処理手段とを有し、
該画像処理手段は、
前記一の画像を構成する画素の画素位置をｉ座標およびｊ座標を用いて特定するとともに、前記他の画像を構成する画素の画素位置をｍ座標およびｎ座標を用いて特定し、
前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画素間距離を積み上げ計算することにより算出し、
算出された前記最小累積距離に基づいて、類似した画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求め、
前記積み上げ計算を行う場合には、前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、
前記最小累積距離の算出処理を行う場合には、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うこと
を特徴とする画像パターンマッチング装置。
【請求項２】
前記画像処理手段は、
前記最小累積距離の算出処理を行う場合に、前記最小累積距離の計算を、前記ｍ座標方向に関する最小累積距離の計算と前記ｎ座標方向に関する最小累積距離の計算とに要素分割を行った上で、前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う
ことを特徴とする請求項１に記載の画像パターンマッチング装置。
【請求項３】
画素位置をｉ座標およびｊ座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をｍ座標およびｎ座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング方法であって、
画像処理手段が、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画像間距離を積み上げ計算することにより算出する最小累積距離算出ステップと、
前記画像処理手段が、該最小累積距離算出ステップにおいて算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求める対応画素算出ステップとを有し、
前記最小累積距離算出ステップにおいて、
前記積み上げ計算を行う場合には、前記画像処理手段が、前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、
前記最小累積距離の算出処理を行う場合には、前記画像処理手段が、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うこと
を特徴とする画像パターンマッチング方法。
【請求項４】
前記最小累積距離算出ステップは、前記最小累積距離の算出処理を行う場合において、
前記最小累積距離の計算を、前記画像処理手段が、前記ｍ座標方向に関する最小累積距離の計算と、前記ｎ座標方向に関する最小累積距離の計算とに要素分割を行う分割ステップと、
前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う積み上げ計算ステップと
を有することを特徴とする請求項３に記載の画像パターンマッチング方法。
【請求項５】
画素位置をｉ座標およびｊ座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をｍ座標およびｎ座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング用プログラムであって、
コンピュータに、
前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画像間距離を積み上げ計算させることにより算出させる最小累積距離算出機能と、
該最小累積距離算出機能により算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求めさせる対応画素算出機能と
を実現させ、
前記最小累積距離算出機能には、
前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行させる積み上げ計算順番機能と、
累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行わせる累積座標間距離算出機能とが含まれること
を特徴とする画像パターンマッチング用プログラム。
【請求項６】
前記積み上げ計算順番機能は、
前記最小累積距離の計算を、前記ｍ座標方向に関する最小累積距離の計算と、前記ｎ座標方向に関する最小累積距離の計算とに要素分割させる分割機能と、
前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行わせる積み上げ計算機能と
を有することを特徴とする請求項５に記載の画像パターンマッチング用プログラム。
【請求項１】
互いに類似する画像パターンを含み得る一の画像と他の画像との画素毎の対応関係を求める画像パターンマッチング装置であって、
前記一の画像と他の画像とを記録する記録手段と、
前記一の画像と前記他の画像とにおける類似する画像パターンの画素毎の対応関係を求める画像処理手段とを有し、
該画像処理手段は、
前記一の画像を構成する画素の画素位置をｉ座標およびｊ座標を用いて特定するとともに、前記他の画像を構成する画素の画素位置をｍ座標およびｎ座標を用いて特定し、
前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画素間距離を積み上げ計算することにより算出し、
算出された前記最小累積距離に基づいて、類似した画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求め、
前記積み上げ計算を行う場合には、前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、
前記最小累積距離の算出処理を行う場合には、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うこと
を特徴とする画像パターンマッチング装置。
【請求項２】
前記画像処理手段は、
前記最小累積距離の算出処理を行う場合に、前記最小累積距離の計算を、前記ｍ座標方向に関する最小累積距離の計算と前記ｎ座標方向に関する最小累積距離の計算とに要素分割を行った上で、前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う
ことを特徴とする請求項１に記載の画像パターンマッチング装置。
【請求項３】
画素位置をｉ座標およびｊ座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をｍ座標およびｎ座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング方法であって、
画像処理手段が、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画像間距離を積み上げ計算することにより算出する最小累積距離算出ステップと、
前記画像処理手段が、該最小累積距離算出ステップにおいて算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求める対応画素算出ステップとを有し、
前記最小累積距離算出ステップにおいて、
前記積み上げ計算を行う場合には、前記画像処理手段が、前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、
前記最小累積距離の算出処理を行う場合には、前記画像処理手段が、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うこと
を特徴とする画像パターンマッチング方法。
【請求項４】
前記最小累積距離算出ステップは、前記最小累積距離の算出処理を行う場合において、
前記最小累積距離の計算を、前記画像処理手段が、前記ｍ座標方向に関する最小累積距離の計算と、前記ｎ座標方向に関する最小累積距離の計算とに要素分割を行う分割ステップと、
前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う積み上げ計算ステップと
を有することを特徴とする請求項３に記載の画像パターンマッチング方法。
【請求項５】
画素位置をｉ座標およびｊ座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をｍ座標およびｎ座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング用プログラムであって、
コンピュータに、
前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記ｉ座標、前記ｊ座標、前記ｍ座標および前記ｎ座標からなる４次元空間座標において、累積的に前記画像間距離を積み上げ計算させることにより算出させる最小累積距離算出機能と、
該最小累積距離算出機能により算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求めさせる対応画素算出機能と
を実現させ、
前記最小累積距離算出機能には、
前記ｍ座標および前記ｎ座標における対角方向を基準として、ｍ座標の値とｎ座標の値との和の値が小さくなる順番で前記積み上げ計算を実行させる積み上げ計算順番機能と、
累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行わせる累積座標間距離算出機能とが含まれること
を特徴とする画像パターンマッチング用プログラム。
【請求項６】
前記積み上げ計算順番機能は、
前記最小累積距離の計算を、前記ｍ座標方向に関する最小累積距離の計算と、前記ｎ座標方向に関する最小累積距離の計算とに要素分割させる分割機能と、
前記ｍ座標方向に関する最小累積距離の計算および前記ｎ座標方向に関する最小累積距離の計算のそれぞれの計算において、前記ｉ座標方向および前記ｊ座標方向に対する前記遷移パターンを、等倍、等倍±４５度回転、２倍、２倍±４５度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行わせる積み上げ計算機能と
を有することを特徴とする請求項５に記載の画像パターンマッチング用プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１０−１６５１０４（Ｐ２０１０−１６５１０４Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−５６８２（Ｐ２００９−５６８２）
【出願日】平成２１年１月１４日（２００９．１．１４）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２０年７月２９日 画像情報学フォーラム発行の「ＭＩＲＵ ２００８ Ｐｒｏｃｅｅｄｉｎｇｓ（第１１回 画像の認識・理解シンポジウム論文集）」、平成２０年１１月２０日 社団法人電子情報通信学会発行の「電子情報通信学会技術研究報告 信学技報 Ｖｏｌ．１０８ Ｎｏ．３２７」、平成２０年１２月１１日 社団法人電子情報通信学会発行の「電子情報通信学会技術研究報告 信学技報 Ｖｏｌ．１０８ Ｎｏ．３６３」、平成２０年１２月１８日 Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ発行の「Ａｄｖａｎｃｅｓ ｉｎ Ｉｍａｇｅ ａｎｄ Ｖｉｄｅｏ Ｔｅｃｈｎｏｌｏｇｙ，Ｔｈｉｒｄ Ｐａｃｉｆｉｃ Ｒｉｍ Ｓｙｍｐｏｓｉｕｍ，ＰＳＩＶＴ ２００９ Ｔｏｋｙｏ，Ｊａｐａｎ，Ｊａｎｕａｒｙ １３−１６，２００９ Ｐｒｏｃｅｅｄｉｎｇｓ（Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ（ＬＮＣＳ）Ｖｏｌ．５４１４）」
【出願人】（５０６３０１１４０）公立大学法人会津大学 (23)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１４日（２００９．１．１４）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２０年７月２９日 画像情報学フォーラム発行の「ＭＩＲＵ ２００８ Ｐｒｏｃｅｅｄｉｎｇｓ（第１１回 画像の認識・理解シンポジウム論文集）」、平成２０年１１月２０日 社団法人電子情報通信学会発行の「電子情報通信学会技術研究報告 信学技報 Ｖｏｌ．１０８ Ｎｏ．３２７」、平成２０年１２月１１日 社団法人電子情報通信学会発行の「電子情報通信学会技術研究報告 信学技報 Ｖｏｌ．１０８ Ｎｏ．３６３」、平成２０年１２月１８日 Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ発行の「Ａｄｖａｎｃｅｓ ｉｎ Ｉｍａｇｅ ａｎｄ Ｖｉｄｅｏ Ｔｅｃｈｎｏｌｏｇｙ，Ｔｈｉｒｄ Ｐａｃｉｆｉｃ Ｒｉｍ Ｓｙｍｐｏｓｉｕｍ，ＰＳＩＶＴ ２００９ Ｔｏｋｙｏ，Ｊａｐａｎ，Ｊａｎｕａｒｙ １３−１６，２００９ Ｐｒｏｃｅｅｄｉｎｇｓ（Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ（ＬＮＣＳ）Ｖｏｌ．５４１４）」
【出願人】（５０６３０１１４０）公立大学法人会津大学 (23)
【Ｆターム（参考）】
[ Back to top ]