TOP > 国内特許検索 > 画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラム > 明細書

明細書 :画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5247481号 (P5247481)
公開番号 特開2010-165104 (P2010-165104A)
登録日 平成25年4月19日(2013.4.19)
発行日 平成25年7月24日(2013.7.24)
公開日 平成22年7月29日(2010.7.29)
発明の名称または考案の名称 画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラム
国際特許分類 G06T   7/00        (2006.01)
FI G06T 7/00 300E
請求項の数または発明の数 6
全頁数 26
出願番号 特願2009-005682 (P2009-005682)
出願日 平成21年1月14日(2009.1.14)
新規性喪失の例外の表示 特許法第30条第1項適用 平成20年7月29日 画像情報学フォーラム発行の「MIRU 2008 Proceedings(第11回 画像の認識・理解シンポジウム論文集)」、平成20年11月20日 社団法人電子情報通信学会発行の「電子情報通信学会技術研究報告 信学技報 Vol.108 No.327」、平成20年12月11日 社団法人電子情報通信学会発行の「電子情報通信学会技術研究報告 信学技報 Vol.108 No.363」、平成20年12月18日 Springer-Verlag Berlin Heidelberg発行の「Advances in Image and Video Technology,Third Pacific Rim Symposium,PSIVT 2009 Tokyo,Japan,January 13-16,2009 Proceedings(Lecture Notes in Computer Science(LNCS)Vol.5414)」
審査請求日 平成24年1月11日(2012.1.11)
特許権者または実用新案権者 【識別番号】506301140
【氏名又は名称】公立大学法人会津大学
発明者または考案者 【氏名】岡 嶐一
【氏名】矢口 勇一
【氏名】井関 健太
個別代理人の代理人 【識別番号】100118094、【弁理士】、【氏名又は名称】殿元 基城
審査官 【審査官】佐藤 実
参考文献・文献 特開2006-277575(JP,A)
岩佐有弥 外1名,2次元連続DPを用いた動画像における変形物体のスポッティング認識と追跡,電子情報通信学会技術研究報告 MVE2004-21~25 マルチメディア・仮想環境基礎,社団法人電子情報通信学会,2004年 7月 8日,第104巻 第195号,第19~24頁
調査した分野 G06T 7/00
特許請求の範囲 【請求項1】
互いに類似する画像パターンを含み得る一の画像と他の画像との画素毎の対応関係を求める画像パターンマッチング装置であって
前記一の画像と前記他の画像とにおける類似する画像パターンの画素毎の対応関係を求める画像処理手段とを有し、
該画像処理手段は、
前記一の画像を構成する画素の画素位置をi座標およびj座標を用いて特定するとともに、前記他の画像を構成する画素の画素位置をm座標およびn座標を用いて特定し、
前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記i座標、前記j座標、前記m座標および前記n座標からなる4次元空間座標において、累積的に前記画素間距離を積み上げ計算することにより算出し、
算出された前記最小累積距離に基づいて、類似した画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求め、
前記積み上げ計算を行う場合には、前記m座標および前記n座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、
前記最小累積距離の算出処理を行う場合には、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うこと
を特徴とする画像パターンマッチング装置。

【請求項2】
前記画像処理手段は、
前記最小累積距離の算出処理を行う場合に、前記最小累積距離の計算を、前記m座標方向に関する最小累積距離の計算と前記n座標方向に関する最小累積距離の計算とに要素分割を行った上で、前記m座標方向に関する最小累積距離の計算および前記n座標方向に関する最小累積距離の計算のそれぞれの計算において、前記i座標方向および前記j座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±45度回転、2倍、2倍±45度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う
ことを特徴とする請求項1に記載の画像パターンマッチング装置。
【請求項3】
画素位置をi座標およびj座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をm座標およびn座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング方法であって、
画像処理手段が、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記i座標、前記j座標、前記m座標および前記n座標からなる4次元空間座標において、累積的に前記画像間距離を積み上げ計算することにより算出する最小累積距離算出ステップと、
前記画像処理手段が、該最小累積距離算出ステップにおいて算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求める対応画素算出ステップとを有し、
前記最小累積距離算出ステップにおいて、
前記積み上げ計算を行う場合には、前記画像処理手段が、前記m座標および前記n座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、
前記最小累積距離の算出処理を行う場合には、前記画像処理手段が、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うこと
を特徴とする画像パターンマッチング方法。
【請求項4】
前記最小累積距離算出ステップは、前記最小累積距離の算出処理を行う場合において、
前記最小累積距離の計算を、前記画像処理手段が、前記m座標方向に関する最小累積距離の計算と、前記n座標方向に関する最小累積距離の計算とに要素分割を行う分割ステップと、
前記m座標方向に関する最小累積距離の計算および前記n座標方向に関する最小累積距離の計算のそれぞれの計算において、前記i座標方向および前記j座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±45度回転、2倍、2倍±45度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う積み上げ計算ステップと
を有することを特徴とする請求項3に記載の画像パターンマッチング方法。
【請求項5】
画素位置をi座標およびj座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をm座標およびn座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング用プログラムであって、
コンピュータに、
前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記i座標、前記j座標、前記m座標および前記n座標からなる4次元空間座標において、累積的に前記画像間距離を積み上げ計算させることにより算出させる最小累積距離算出機能と、
該最小累積距離算出機能により算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求めさせる対応画素算出機能と
を実現させ、
前記最小累積距離算出機能には、
前記m座標および前記n座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行させる積み上げ計算順番機能と、
累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行わせる累積座標間距離算出機能とが含まれること
を特徴とする画像パターンマッチング用プログラム。
【請求項6】
前記積み上げ計算順番機能は、
前記最小累積距離の計算を、前記m座標方向に関する最小累積距離の計算と、前記n座標方向に関する最小累積距離の計算とに要素分割させる分割機能と、
前記m座標方向に関する最小累積距離の計算および前記n座標方向に関する最小累積距離の計算のそれぞれの計算において、前記i座標方向および前記j座標方向に対する前記遷移パターンを、等倍、等倍±45度回転、2倍、2倍±45度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行わせる積み上げ計算機能と
を有することを特徴とする請求項5に記載の画像パターンマッチング用プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムに関し、より詳細には、類似するパターン画像が記録された複数の画像(例えば、一の画像を参照画像、他の画像を対象画像とする)において、類似する画像パターンの各画素をそれぞれの画像より抽出することによって、画素毎の対応関係を求めることが可能な画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムに関する。
【背景技術】
【0002】
従来より、類似する画像パターンが示された異なる画像において、対応する画像間のピクセル(画素)の対応関係を求めたり、対応する特徴抽出点を求めたりする方法が考えられている。このような対応するピクセルの抽出処理は、画像応用処理分野における画像認識手法、特徴点トラッキング手法、対象物の平面画像に基づいて対象物を3次元的に復元する手法などのさまざまなコンピュータサイエンスに応用することが可能となっている。しかしながら、コンピュータサイエンスにおける応用範囲が広いにもかかわらず、画像パターンの認識処理技術に関する決定的な手法が未だに確立されていないという問題があった。
【0003】
例えば、画像間のピクセル対応問題を扱った手法として、動的計画法を利用する方法が提案されている(例えば、非特許文献1~非特許文献3参照)。ここで、動的計画法とは、多変数の最適化を求める問題を解くための手法であって、最短経路問題などに利用される方法である。動的計画法では、「最適経路中の部分経路も、その部分経路における最適な経路により構成されている」という最適性の原理を利用する。このように最適性の原理を利用することにより、問題全体を部分問題における最適な解(決定)の積み重ねによって求めることができる。
【0004】
このような動的計画法を応用した事例として、例えば、マッチングされる2つの画像の双方について領域を固定することにより、手書き文字認識を2次元非線形問題として求める研究が行われている(例えば、非特許文献4参照)。
【0005】
また、今日では、入力時系列中の検索区間を事前に定めることなく、マッチング区間の抽出を行う連続動的計画法(1次元パターンでのセグメンテーションフリーの非線形マッチングを行う手法)が提案され(例えば、非特許文献5参照)、さらに1次元の連続動的計画法を2次元に拡張した2次元連続動的計画法が提案されている(例えば、非特許文献6参照)。2次元連続動的計画法を用いることにより、複数の画像から対象となる画像パターンの認識と抽出とを同時に行うことが可能となっている。
【0006】
一方で、動画像において特徴点を抽出する処理や、特徴点などに基づいて対象物の3次元形状を復元する処理に関する研究が行われている。特徴点などに基づいて対象物の3次元形状を復元する処理では、動画を構成する画像間での適切な対応関係を求めることが重要となっており、この対応関係を求めることにより特徴点の追跡が可能となる。従来より数多く用いられる特徴点の追跡方法として、KLT方法が知られている(例えば、非特許文献7参照)。
【0007】
また、異なる特徴点の追跡方法として、SIFT特徴量を用いた手法も提案されている(例えば、特許文献8参照)。SIFT特徴量を用いた手法は、物体のスケール変化、物体の回転、物体の平行移動に対して影響を受けない(不変となる)特徴点を抽出することを特徴としており、その特徴点の抽出は128次元のベクトルにより構成されている。
【先行技術文献】
【0008】

【非特許文献1】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
【非特許文献2】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
【非特許文献3】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
【非特許文献4】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
【非特許文献5】R.Oka, “Spotting method for classification of real world data”, The Computer Journal, (イギリス), Oxford Journal, 1998年,Vol. 41, No.8, p.559-565
【非特許文献6】T. Nishimura, R. Oka, ”Spotting Image Recognition using Two-Dimensional Continuous Dynamic Programming”, IEICE Technical Report (PRMU), 1997年7月, p.1-7
【非特許文献7】C. Tomasi, T. Kanade, “Detection and Tracking of Point Features”, Carnegie Mellon University Techinical Report, 1991年4月, CMU-CS-91-132
【非特許文献8】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
【発明の概要】
【発明が解決しようとする課題】
【0009】
しかしながら、上述した、2次元連続動的計画法を用いる方法では、参照画像の各行方向パターンのマッチング結果に基づいて列方向の累積を求める方法を用いているため、次述するピクセル間の単調連続性を保証することができなかった。このため、従来の2次元連続動的計画法を用いる方法では、2次元的に最適な対応関係を求めることが容易ではないという問題があった。
【0010】
ここで、ピクセル間の単調性とは、マッチングの結果において、隣接するピクセル同士の相対的な位置関係場(上下左右の関係)が双方の画像の間において保持されている性質を意味し、連続性とは、マッチングの結果について対応点全体が自然なピクセル間の距離を保つ性質を意味している。この単調連続性を保つことにより、画像における基本的な特性を保持することが可能となり、画像間での適切な対応関係を求める処理において必要不可欠な要素となっている。
【0011】
また、上述したKLT法は、動画像中の特徴点の対応に基づく追跡に用いられるトラッキング手法であり、微小時間でのピクセルの動きは平行移動だけしかせず、また、照明の変化に伴う輝度値の変化が生じないことを仮定して特徴点の追跡を行うことを特徴としている。このように、KLT法では、微小時間中での特徴点の平行移動を仮定しているため、連続的に観測された画像系列でのトラッキングのみを対象とし、連続観測されたものでない異なる画像間における特徴点の抽出処理では、十分な機能を発揮することが困難であるという問題があった。
【0012】
一方で、上述したSIFT特徴量を用いた手法では、特徴点の対応を扱っているが、ベクトル要素で構成された特徴点を、異なる画像毎に求め、それぞれの画像において求められた特徴点に最も近い特徴点を対応付けることにより、特徴点の追跡を行う方法を採用する。このため、特徴点同士の対応付けは可能であっても、ピクセル単位で1対1の対応付けを行うことができず、また、対応付けられた特徴点もそれらしい点の対応に留まってしまうという問題があった。
【0013】
さらに、SIFT特徴量を用いた特徴点の追跡手法では、対応付けられた特徴点において上述した単調性が保証されないという問題があった。SIFT特徴量を用いた手法により求められる特徴点の対応関係は、特徴点に関する類似性のみに基づいて求められているため、位置関係を求める手法として使えるまでには至っていなかった。
【0014】
また、SIFT特徴量を用いた特徴点の追跡手法では、対象物以外の領域が含まれた状態で特徴点が求められるため、背景が変化するシーンなどにおいては追跡精度が低下し、追跡処理に失敗してしまうことがあるという問題があった。
【0015】
本発明は、上記問題に鑑みてなされたものであり、動画に限定されることなく、異なる任意の画像中における対象物画像(画像パターン)の対応を、ピクセル間の単調連続性を確保しつつ画素毎に求めることが可能な画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチングプログラムを提供することを課題とする。
【課題を解決するための手段】
【0016】
上記課題を解決するために、本発明に係る画像パターンマッチング装置は、互いに類似する画像パターンを含み得る一の画像と他の画像との画素毎の対応関係を求める画像パターンマッチング装置であって前記一の画像と前記他の画像とにおける類似する画像パターンの画素毎の対応関係を求める画像処理手段とを有し、該画像処理手段は、前記一の画像を構成する画素の画素位置をi座標およびj座標を用いて特定するとともに、前記他の画像を構成する画素の画素位置をm座標およびn座標を用いて特定し、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記i座標、前記j座標、前記m座標および前記n座標からなる4次元空間座標において、累積的に前記画素間距離を積み上げ計算することにより算出し、算出された前記最小累積距離に基づいて、類似した画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求め、前記積み上げ計算を行う場合には、前記m座標および前記n座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、前記最小累積距離の算出処理を行う場合には、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うことを特徴とする。


【0017】
また、本発明に係る画像パターンマッチング方法は、画素位置をi座標およびj座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をm座標およびn座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング方法であって、画像処理手段が、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記i座標、前記j座標、前記m座標および前記n座標からなる4次元空間座標において、累積的に前記画像間距離を積み上げ計算することにより算出する最小累積距離算出ステップと、前記画像処理手段が、該最小累積距離算出ステップにおいて算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求める対応画素算出ステップとを有し、前記最小累積距離算出ステップにおいて、前記積み上げ計算を行う場合には、前記画像処理手段が、前記m座標および前記n座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、前記最小累積距離の算出処理を行う場合には、前記画像処理手段が、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うことを特徴とする。
【0018】
さらに、本発明に係る画像パターンマッチング用プログラムは、画素位置をi座標およびj座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をm座標およびn座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング用プログラムであって、コンピュータに、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記i座標、前記j座標、前記m座標および前記n座標からなる4次元空間座標において、累積的に前記画像間距離を積み上げ計算させることにより算出させる最小累積距離算出機能と、該最小累積距離算出機能により算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求めさせる対応画素算出機能とを実現させ、前記最小累積距離算出機能には、前記m座標および前記n座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行させる積み上げ計算順番機能と、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行わせる累積座標間距離算出機能とが含まれることを特徴とする。
【0019】
ここで、一の画像と他の画像は、互いに類似する画像パターンを含み得る画像であればよい。このため、類似する画像パターンが、一の画像および他の画像の両方の画像に含まれる場合はもちろんのこと、いずれか一方の画像にしか含まれない場合(つまり、類似する画像パターンが両方の画像に含まれない場合)であっても、互いに類似する画像パターンを含み得る場合に該当する。
【0020】
このように、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムでは、積み上げ計算を行う場合において、m座標およびn座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行する。このため、積み上げ計算の値(解)が、現在の決定値(決定解)の直前の2つあるいは1つの決定値(決定解)に基づいて求められることになり、(m,n)平面における2次元の単調連続性を累積時に確保することが可能となる。
【0021】
なお、単調連続性における単調性とは、マッチングの結果において、隣接する画素同士の相対的な位置関係場(上下左右の関係)が双方の画像の間において保持されている性質を意味し、単調連続性における連続性とは、マッチングの結果について対応点全体が自然なピクセル間の距離を保つ性質を意味している。
【0022】
また、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムでは、最小累積距離の算出処理を行う場合において、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行う。このように、直前の座標位置からの遷移状態を所定の遷移パターンに制限することにより、直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出が行われるので、算出された前記最小累積距離に基づいて、類似する画像パターンに対応する一の画像の画素位置と他の画像の画素位置との対応関係を求める処理(バックトレース処理)において単調連続性を保証することが可能となる。
【0023】
さらに、上述した画像パターンマッチング装置において、前記画像処理手段は、前記最小累積距離の算出処理を行う場合に、前記最小累積距離の計算を、前記m座標方向に関する最小累積距離の計算と前記n座標方向に関する最小累積距離の計算とに要素分割を行った上で、前記m座標方向に関する最小累積距離の計算および前記n座標方向に関する最小累積距離の計算のそれぞれの計算において、前記i座標方向および前記j座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±45度回転、2倍、2倍±45度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行うものであってもよい。
【0024】
また、上述した画像パターンマッチング方法の前記最小累積距離算出ステップは、前記画像処理手段が、前記最小累積距離の算出処理を行う場合に、前記最小累積距離の計算を、前記m座標方向に関する最小累積距離の計算と、前記n座標方向に関する最小累積距離の計算とに要素分割を行う分割ステップと、前記m座標方向に関する最小累積距離の計算および前記n座標方向に関する最小累積距離の計算のそれぞれの計算において、前記i座標方向および前記j座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±45度回転、2倍、2倍±45度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う積み上げ計算ステップとを有するものであってもよい。
【0025】
さらに、上述した画像パターンマッチング用プログラムにおいて、前記積み上げ計算順番機能は、前記最小累積距離の計算を、前記m座標方向に関する最小累積距離の計算と、前記n座標方向に関する最小累積距離の計算とに要素分割させる分割機能と、前記m座標方向に関する最小累積距離の計算および前記n座標方向に関する最小累積距離の計算のそれぞれの計算において、前記i座標方向および前記j座標方向に対する前記遷移パターンを、等倍、等倍±45度回転、2倍、2倍±45度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行わせる積み上げ計算機能とを有するものであってもよい。
【0026】
このように、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムでは、最小累積距離の計算を、m座標方向に関する最小累積距離の計算と、n座標方向に関する最小累積距離の計算とに要素分割した上で、m座標方向に関する最小累積距離の計算およびn座標方向に関する最小累積距離の計算のそれぞれの計算において、前記i座標方向およびj座標方向のそれぞれの方向に対する遷移パターンを、等倍、等倍±45度回転、2倍、2倍±45度回転および縮小により構成される遷移パターンに制限して積み上げ計算を行うため、画素間の非線形対応関係を確保することが可能となる。また、算出された最小累積距離に基づいて、類似する画像パターンに対応する一の画像の画素位置と他の画像の画素位置との対応関係を求める処理(バックトレース処理)において、単調連続性をより確実に確保することが可能となる。
【発明の効果】
【0027】
本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムによれば、積み上げ計算を行う場合において、m座標およびn座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行する。このため、積み上げ計算の値(解)が、現在の決定値(決定解)の直前の2つあるいは1つの決定値(決定解)に基づいて求められることになり、(m,n)平面における2次元の単調連続性を累積時に確保することが可能となる。
【0028】
また、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムによれば、最小累積距離の算出処理を行う場合において、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行う。このように、直前の座標位置からの遷移状態を所定の遷移パターンに制限することにより、直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出が行われるので、画素間の非線形対応関係を確保することが可能となり、さらに、算出された前記最小累積距離に基づいて、類似する画像パターンに対応する一の画像の画素位置と他の画像の画素位置との対応関係を求める処理(バックトレース処理)において単調連続性を保証することが可能となる。
【図面の簡単な説明】
【0029】
【図1】実施の形態に係る画像パターンマッチング装置の概略構成を示したブロック図である。
【図2】実施の形態に示されたi,j,m,nの4つの要素からなる4次元空間に基づいて、対象画像Sと参照画像Rとのピクセル(画素)毎の対応関係を示した図である。
【図3】(a)は、実施の形態に示されたランクLの決定方法を説明するための図であり、(b)は、各データ点における累積方向を示した図である。
【図4】実施の形態に示された画像復元における4点メッシュの制約条件を説明するための図である。
【図5】参照画像Rでの対応点がメッシュ構造を成すために、対象画像S上で(ξ(m,n),η(m,n))に至る出発点が取り得る点の候補を示した図である。
【図6】(a)は、実施の形態に示されたi方向への7パターンの遷移状態を示した図であり、(b)は、j方向への7パターンの遷移状態を示した図である。
【図7】局所距離D(i,j,m,n)=D(ξ(m,n),η(m,n),m,n)が、4次元空間から対象画像Sの(i,j)平面に射影された状態を、(a)に示すm方向と、(b)に示すn方向とに要素分割して示した図である。
【図8】(a)(b)は、実施の形態に係るdxx(i,j,m,n)の構成を示した図であり、(c)(d)は、dyy(i,j,m,n)の構成を示した図である。
【図9】(a)(b)は、実施の形態に係るdxy(i,j,m,n)の構成を示した図であり、(c)(d)は、dyx(i,j,m,n)の構成を示した図である。
【図10】実施の形態に示した参照画像Rから対象物以外の画像を取り除くことにより、対象物だけの画像を抽出する過程を説明するための図である。
【図11】実施の形態に係るCPUが、プログラムに基づいて実行する画像パターンのマッチング処理を示したフローチャートである。
【図12】実施の形態に示した画像パターンのマッチング方法を用いることにより、子供の顔が含まれる参照画像Rに基づいて、対応する子供の顔の画像パターンを、対象画像Sから抽出する処理を説明するための図である。
【図13】実施の形態に示した画像パターンのマッチング方法を応用して用いることにより、対象物が示された少ない枚数の画像に基づいて、対象物の3次元形状を復元することが可能となる旨を示した図である。
【発明を実施するための形態】
【0030】
以下、本発明に係る画像パターンマッチング装置について、図面を用いて詳細に説明する。

【0031】
図1は、画像パターンマッチング装置の概略構成を示したブロック図である。画像パターンマッチング装置1は、一般的なコンピュータにより構成することができ、図1に示すように、CPU(Central Processing Unit)(画像処理手段)2と、ROM(Read Only Memory)3と、RAM(Random Access Memory)4と、記録部(記録手段)5と、ディスプレイ部6と、操作部7とにより概略構成されている。

【0032】
CPU2は、後述する画像パターンのマッチング処理を行う機能を有している。CPU2は、後述する処理プログラム(例えば、図11に示すフローチャートに基づくプログラム)に従って、画像パターンのマッチング処理を行う。RAM4は、CPU2の処理に利用されるワークエリアとして用いられる。ROM3には、上述した画像パターンのマッチング処理に関するプログラム等が記録されている。CPU2は、ROM3より読み込んだプログラムに従って、画像パターンのマッチング処理を行う。

【0033】
記録部5には、画像パターンのマッチング処理に用いられる画像データなどが記録されている。本実施の形態に係る記録部5は、一般的はハードディスクにより構成されている。なお、記録部5の構成は、ハードディスクだけに限定されるものではなく、フラッシュメモリ、SSD(Solid State Drive / Solid State Disk)、CD—ROMドライブ、DVDドライブなどのように、画像パターンマッチング処理に用いられる複数の画像データをCPU2が読み出し可能な状態で記録することが可能なものであるならば、具体的な構成は特に限定されるものではない。

【0034】
なお、本実施の形態に係る画像パターンマッチング装置1では、CPU2において実行される画像パターンマッチング処理に関するプログラムを、ROM3に記録する構成として説明を行うが、これらのプログラムは、記録部5に記録されるものであってもよい。

【0035】
ディスプレイ部6は、記録部5に記録される画像データをユーザに対して視認可能に表示させ、また、CPU2による画像パターンのマッチング処理結果を表示させる役割を有している。ディスプレイ部6には、液晶ディスプレイや、CRTディスプレイなどの一般的な表示装置が用いられる。

【0036】
操作部7は、ユーザが画像パターンマッチング装置1を操作するために必要なデータの入力や、画像パターンマッチング装置1の具体的な操作などを行う場合に用いられる装置であって、一般的なキーボードやマウスなどにより構成される。

【0037】
CPU2は、ROM3より演算処理に必要なプログラムを読み取り、読み取ったプログラムに従って、記録部5に記録される複数の画像データより類似する画像パターンの抽出を行う処理、より詳細には、異なる画像データに含まれる類似する画像パターンの全てのピクセル(画素)の対応関係を求める処理を行う。以下に、CPU2が行う処理の内容を具体的に説明し、その後、CPU2の具体的な処理手順を、フローチャートを示して説明する。

【0038】
まず、CPU2が行う処理内容を具体的に説明する。例えば、相異なる2つの画像データのうち、一方の画像データを対象画像S、他方の画像データを参照画像Rとして、対象画像Sに含まれている画像パターンから、参照画像Rに表される画像パターンの対応をピクセル単位で抽出する処理について説明する。

【0039】
CPU2は、対象画像Sを構成するピクセル位置と参照画像Rを構成するピクセル位置とを、それぞれ座標点を用いて特定する。具体的に、CPU2は、対象画像Sをi要素とj要素とを備える(i,j)平面における座標点のピクセルの集合として捉える。
【数1】
JP0005247481B2_000002t.gif
但し、対象画像Sのピクセル位置は、1≦i≦I(定数)、1≦j≦J(定数)の範囲で特定されるものとする。

【0040】
一方で、CPU2は、参照画像Rをm要素とn要素とを備える(m,n)平面における座標点のピクセルの集合として捉える。
【数2】
JP0005247481B2_000003t.gif
但し、参照画像Rのピクセル位置は、1≦m≦M(定数)、1≦n≦N(定数)の範囲で特定されるものとする。

【0041】
さらに、CPU2は、対象画像Sの各ピクセルの値をSp(i,j)=(r,g,b)として記録部5に記録し、また、参照画像Rの各ピクセルの値をRp(m,n)=(r,g,b)として記録する。なお、(r,g,b)は、対応するピクセルの色彩データ(r:赤、g:緑、b:青)を示している。

【0042】
このように、CPU2は、対象画像Sのi要素,j要素と、参照画像Rのm要素,n要素とに基づいて、i,j,m,nの4つの要素からなる4次元の空間(局地距離累積空間)を構成し、対象画像Sと参照画像Rとの画像パターンのマッチングを、それぞれの画像(対象画像Sおよび参照画像R)におけるピクセル(画素)毎の対応関係式(後述する)を用いることにより判断する。

【0043】
図2は、i,j,m,nの4つの要素からなる4次元の空間に基づいて、対象画像Sと参照画像Rとのピクセル(画素)毎の対応関係を図示したものである。対象画像Sの各ピクセル(i,j)に対して、参照画像Rのm要素、n要素からなる平面の存在を考えることにより、4次元の空間を構築する。

【0044】
CPU2は、類似する画像パターンを含む画像同士で画像パターンのマッチング処理を行う場合に、対応する参照画像Rの画素の座標点に対応する座標点を、対象画像Sの画素より求めて、対応する参照画像Rから対象画像Sへの写像を、写像R→Sとして定義する。つまり、
(m,n)∈Rについて(参照画像Rに属する座標点(m,n)について)
(m,n)⇒(ξ(m,n),η(m,n)) ・・・式3
となるξとηの2つの関数が考えられている。

【0045】
ここで、
ξ(M,N)=i、 η(M,N)=j ・・・式4
となる対応点を累積の終点として考える(但し、Mは、参照画像Rにおける最大値となるm要素の値、Nは、参照画像Rにおける最大値となるn要素の値を示している)。

【0046】
累積時に与えられる各点に対する重みをw(i,j,m,n)とし、また、対応するピクセルの対象画像Sの座標(i,j)と参照画像Rの座標(m,n)との距離(ピクセル間距離)をd(i,j,m,n)として、2次元連続動的計画法を用いることにより最小累積距離を示す積み上げ空間を求める。この積み上げ空間の最終累積値における最小値をスポッティング点という。このようにして求められる2次元連続動的計画法による最小累積距離の積み上げ空間J(i,j)は、以下の評価式で実現される。
【数3】
JP0005247481B2_000004t.gif

【0047】
なお、この累積値を求める場合には、図3(a)に示すように、(m+n)に基づいてランクLを決定し、参照画像Rの対角方向に対して、下から順番に累積値を積み上げて計算を行う。このようにして積み上げ計算を行うことにより、各データ点(m,n)に与えられる累積方向は、図3(b)に示すように、2入力方向(m方向およびn方向)および2出力方向(m方向およびn方向)となる。また、この積み上げ計算により現在の座標における累積値が、その直前の2つ(あるいは1つ)の累積値に基づいて求められることになる。

【0048】
式5に示すξ(m,n)において最適となる解をξ(m,n)と定義し、また、η(m,n)において最適となる解をη(m,n)と定義すると、式5に示すWは、最適な累積の重みを示すものとして以下のように定義することができる。
【数4】
JP0005247481B2_000005t.gif

【0049】
このようにして4次元空間に基づいて対応点を求めると、図2に示すように4次元空間において参照画像Rのピクセル(画素)と対象画像Sのピクセル(画素)とが対応する座標D(i,j,m,n)を求めることができる。この座標D(i,j,m,n)を(i,j)平面に射影することにより、対応する対象画像Sの座標を求めることができ、また、(m,n)平面に射影することにより、対応する参照画像Rの座標を求めることができる。従って、この参照画像Rと対象画像Sとにおける座標の対応を求めることによって、参照画像Rの画像パターンの座標(m,n)に対応する対象画像Sの画像パターンの座標(i,j)を求めることができ、ピクセル単位で対応関係を示すことが可能となる。

【0050】
なお、上述したように、参照画像Rと対象画像Sとの対応点(ピクセル、画素)を求めることができる場合には、対応点(ピクセル、画素)が変形しても、また、それぞれの対応点(ピクセル、画素)が画像上で変形しても、メッシュ構造として(物体の形状を表現するために使われるデータとして)それぞれが保たれている必要がある。このように、双方でメッシュ構造が保たれていることを、本実施の形態に係る説明では、「単調連続性の保証」という言葉で表現する。

【0051】
ここで、単調性とは、画像パターンのマッチング前後で隣接するピクセル同士の相対的な位置関係(上下左右の関係)が保持される性質を意味し、連続性とは、マッチングの前後で対応点において自然なピクセル間の距離を保つ性質を意味している。なお、上述した積み上げ計算処理では、ランクLを定義することにより参照画像Rの対角方向に対して累積値の積み上げ計算を行うので、参照画像Rにおける2次元的な単調連続性が累積時に反映されることになり、「単調連続性の保証」が確保されることになる。

【0052】
次に、i要素およびj要素を含めた全体としての「単調連続性の保証」を確保するための条件を説明する。

【0053】
図4は、画像復元における4点メッシュの制約条件を説明するための図である。図4は、説明を簡単にするために線形の場合(つまり、拡大縮小回転のない場合)における説明図を示している。なお、実際の適用段階においては、拡大縮小回転を行うことにより、最適なマッチング処理を行うことが可能になる場合もある。

【0054】
図4は、図2に示したように、対象画像Sの各ピクセルにおいて参照画像Rの座標平面を考えることにより構成された4次元の空間を示している。また、図4には、参照画像Rの座標(m,n)に対応する対象画像Sの座標(i,j)=(ξ(m,n),η(m,n))が示されており、また、対象画像S上で(i,j)=(ξ(m,n),η(m,n))へと対応点が変化する場合において、参照画像Rにおける対象点のメッシュ構造を確保しつつ、その対象点に至ることが可能な出発点(座標)の集合が表されている。図4に示す場合では、参照画像Rにおける点(m-1,n-1)に対応可能な出発点は、点(m,n)、点(m,n-1)および点(m-1,n)によって決定されることになる。

【0055】
2次元的な単調性および連続性を保証するために、参照画像Rのm方向に対応する対象画像Sの移動可能な点(局所パス:遷移状態)の集合を
K(m,n)={(ξ(m-1,n),η(m-1,n))}とし、
参照画像Rのn方向に対応する対象画像Sの移動可能な点(局所パス:遷移状態)の集合を
L(m,n)={(ξ(m,n-1),η(m,n-1))}とすると、
点(m-1,n-1)に対応する点(ξ(m-1,n-1),η(m-1,n-1))は、
【数5】
JP0005247481B2_000006t.gif
を満たす必要がある。

【0056】
式7において、K(m,n)は、(ξ(m,n),η(m,n))にm方向から1回の遷移で至る4次元空間の点集合を、対象画像Sに射影した点の候補(集合)を示すことになり、L(m,n)は、(ξ(m,n),η(m,n))にn方向から1回の遷移で至る4次元空間の点集合を、対象画像Sに射影した点の候補(集合)を示すことになる。

【0057】
また、式7における
【数6】
JP0005247481B2_000007t.gif
は、式の左辺に示す点から右辺に示す式の集合を接合する意味(テンソル積)を示している。

【0058】
この式7を満たす場合には、局所的に単調性および連続性を保証した4点(m,n)、(m,n-1)、(m-1,n)、(m-1,n-1)を用いたメッシュが、図4に示すように作成される。なお、図4は、上述したように線形の場合(つまり、拡大縮小回転のない場合)を示している。

【0059】
従って、図4に示すように、点(m-1,n-1)から点(m,n)に至る場合において、2つの局所パスが点(m,n-1)と(m-1,n)とを通るときに、参照画像R上でメッシュ構造を作ることが可能となる。そして、これに対応するようにして非線形の変形が行われた場合には、対象画像S上でもメッシュ構造を作ることが可能であるため、2つのパスのそれぞれが、2回の遷移で変化可能な出発点の集合である
【数7】
JP0005247481B2_000008t.gif

【数8】
JP0005247481B2_000009t.gif

に重なる範囲内において(ξ(m-1,n-1),η(m-1,n-1))が存在すれば良いことになる。

【0060】
図5は、参照画像Rでの対応点がメッシュ構造を成すために、対象画像S上で(ξ(m,n),η(m,n))に至る出発点が取り得る点の集合(候補)を太い点(●:黒丸)で示した図である。図5では、対象画像Sにおける(ξ(m,n),η(m,n))に至る出発点として、K(m,n)で示される出発点(ξ(m-1,n),η(m-1,n))と、L(m,n)で示される出発点(ξ(m,n-1),η(m,n-1))とを取ることが可能であり、さらに、
【数9】
JP0005247481B2_000010t.gif
で示される出発点(ξ(m-1,n-1),η(m-1,n-1))を取ることが可能であることが示されている。

【0061】
また、2次元連続動的計画法では、累積時に局所パス(上述した移動可能な出発点から遷移状態)に対して幾何学的な制約を与えることによって、それぞれピクセル間の非線形変形度合いを決めることができる。

【0062】
図6(a)および図6(b)は、局所パスにおける遷移の状態(方向)の制限を示した図であり、具体的に図6(a)の上段図には、i方向への移動を基本とした遷移状態が7パターン示されており、図6(b)の上段図には、j方向への移動を基本とした遷移状態が7パターン示されている。また、図6(a)の下段図には、図6(a)の上段図に示した7パターンの遷移状態に基づいて、黒丸で示された座標へ遷移が行われる直前に位置し得る座標位置が白丸で示されており、図6(b)の下段図には、図6(b)の上段図に示した7パターンの遷移状態に基づいて、黒丸で示された座標において遷移が行われる直前に位置し得る座標位置が白丸で示されている。

【0063】
図6(a)(b)に示すように、累積値の積み上げ処理において、移動方向を示す局所パスに対してそれぞれ7パターンのパス制約を加えることにより、(パターン1)等倍、(パターン2)等倍+45度回転、(パターン3)等倍-45度回転、(パターン4)2倍、(パターン5)2倍+45度回転、(パターン6)2倍-45度回転、(パターン7)縮小を許容したピクセル間の非線形変形を実現することが可能となる。なお、縮小は、累積時および後述するバックトラック時における制約として、連続縮小に関する制限を与えることにより実現される。

【0064】
このように、CPU2において局所パスに対して図6(a)(b)に示すような遷移パターンを設定することにより、単調連続性の保証を確保することが可能となる。

【0065】
次に、画像パターンのマッチング処理に用いられる局所距離について説明する。画像パターンのマッチング処理における計算は、局所距離と呼ばれる値を累積することにより実行される。局所距離は、対象画像Sの(i,j)点でのピクセル(カラー画像の場合には、r(赤:),g(緑:),b(青:)の3要素を備えている)と、参照画像Rの(m,n)点でのピクセル(同様に、カラー画像の場合には、r(赤:),g(緑:),b(青:)の3要素を備えている)との間で、以下のように定義される。
【数10】
JP0005247481B2_000011t.gif

【0066】
ここで、kの値は、参照画像R(i,j)および対象画像S(i,j)がカラー画像である場合における各色彩を示しており、k=1は、参照画像R(i,j)および対象画像S(i,j)のr(赤:)に該当し、k=2は、参照画像R(i,j)および対象画像S(i,j)のg(緑:)に該当し、k=3は、参照画像R(i,j)および対象画像S(i,j)のb(青:)に該当する。なお、d(i,j,m,n)の値は、0≦d(i,j,m,n)≦1となる。

【0067】
また、2次元連続動的計画法では、上述したように2種類の局所パスを選択するように設計されており、この局所パスは、上述した4つのポイント(m,n)、(m-1,n)、(m,n-1)、(m-1,n-1)のつながりに基づいて求められる。これらの4ポイントのつながりを変数として表すと、上述した局所距離d(i,j,m,n)における4ポイントの関係から、dxx(i,j,m,n)、dxy(i,j,m,n)、dyy(i,j,m,n)、dyx(i,j,m,n)の4つの変数を用いて示すことができる。

【0068】
図7は、4つの変数に基づいてそれぞれ累積された局所距離D(i,j,m,n)=D(ξ(m,n),η(m,n),m,n)が、4次元空間から対象画像Sの(i,j)平面に射影された状態を示している。図7に示すように局所距離D(i,j,m,n)を、m方向要素とn方向要素とに要素分割することにより、2方向から対象画像Sに対応させて局所距離Dの累積計算を行うことができる。図7では、累積距離D(ξ(m,n),η(m,n),m,n)が、m方向(K(ξ(m,n),η(m,n))の累積距離D(Kx(ξ(m,n),η(m,n)),Ky(ξ(m,n),η(m,n)),m-1,n)と、n方向(L(ξ(m,n),η(m,n))の累積距離D(Lx(ξ(m,n),η(m,n)),Ly(ξ(m,n),η(m,n)),m,n-1)とにより算出される場合が示されている。

【0069】
次に、上述したdxx(i,j,m,n)、dxy(i,j,m,n)、dyy(i,j,m,n)、dyx(i,j,m,n)の4つ値の決定方法について説明する。

【0070】
まず、dxx(i,j,m,n)は、4次元空間から(m,n)平面へと射影された局所距離計算点群の最上点(i,j,m,n)に割り当てられる4つの変数(座標点)の1つである。図8(a)は、dxx(i,j,m,n)を示しており、dxx(i,j,m,n)は、図8(b)に示すように、射影点(i’,j’,m,n)に割り当てられる変数であるdxx(i’,j’,m-1,n)と、d(i,j,m,n)の値との和によって算出される。なお、局所距離dxx(i’,j’,m-1,n)は、図8(b)の長方形部分に射影された4つの局所距離の加算により求められる値である。

【0071】
次に、dyy(i,j,m,n)は、図8(c)のように示される。dyy(i,j,m,n)は、図8(d)に示すように、射影点(i”,j”,m,n-1)に割り当てられる変数であるdyy(i”,j”,m,n-1)と、局所距離d(i,j,m,n)の値との和によって算出される。なお、dyy(i”,j”,m,n-1)は、図8(d)の長方形部分に射影された4つの局所距離の加算により求められる値である。

【0072】
また、dxy(i,j,m,n)は、点(i’,j’,m-1,n)に割り当てられた2つの値であるdyy(i’,j’,m-1,n)とdxy(i’,j’,m-1,n)との加算により求められる。図9(a)は、dxy(i,j,m,n)を示しており、dxy(i,j,m,n)は、図9(b)に示すように、図面上の大きな長方形内に示される射影された局所距離計算点を示すdxy(i’,j’,m-1,n)と、図面上の小さな長方形内に示される射影された局所距離計算点を示すdyy(i’,j’,m-1,n)とにより構成される。

【0073】
さらに、dyx(i,j,m,n)は、点(i”,j”,m,n-1)に割り当てられた2つの値であるdxx(i”,j”,m,n-1)とdyx(i”,j”,m,n-1)との加算により求められる。図9(c)は、dyx(i,j,m,n)を示しており、dyx(i,j,m,n)は、図9(d)に示すように、図面上の大きな長方形内の射影局所距離計算点を示すdyx(i”,j”,m,n-1)と、図面上の小さな長方形内の射影局所距離計算点を示すdxx(i”,j”,m,n-1)とにより構成される。

【0074】
上述した説明より、4つの変数の値は、
【数11】
JP0005247481B2_000012t.gif
【数12】
JP0005247481B2_000013t.gif
【数13】
JP0005247481B2_000014t.gif
【数14】
JP0005247481B2_000015t.gif
で示すことができ、点(i,j,m,n)における最小累積値(最小累積距離)D(i,j,m,n)は、
【数15】
JP0005247481B2_000016t.gif
により求めることができる。

【0075】
なお、上述した(i’,j’,m-1,n)および(i”,j”,m,n-1)は
【数16】
JP0005247481B2_000017t.gif
【数17】
JP0005247481B2_000018t.gif
の2式を用いて求めることができる。

【0076】
式17および式18の{}内には、図6(a)および図6(b)に示した7パターンの局所パス(遷移状態(方向)を制限した局所パス)を示す式が記載されている。CPU2は、これらの7パターンの関係式を計算して、式の値が最小となるときの(i’,j’,m-1,n)の各要素の値と(i’,j’,m,n-1)の各要素の値とを抽出する。そして、CPU2は、抽出された値を式12~式15に代入することにより、dxx(i,j,m,n)、dxy(i,j,m,n)、dyy(i,j,m,n)、dyx(i,j,m,n)の4つ値を算出する。

【0077】
そして、CPU2は、算出されたdxx(i,j,m,n)、dxy(i,j,m,n)、dyy(i,j,m,n)およびdyx(i,j,m,n)の4つ値を用いて、式16により点(i,j,m,n)の最適累積値であるD(i,j,m,n)を求める。

【0078】
なお、CPU2は、初期値としてm=1、n=1が与えられている状態において、mが1以上M以下となる条件を満たす間だけmを1ずつ増加させるとともに、各mにおいて、nが1以上N以下となる条件を満たす間だけnを1ずつ増加させることにより、全てのmおよびnにおいて(i’,j’,m-1,n)と(i’,j’,m,n-1)を求める。

【0079】
さらに、CPU2は、累積値の積み上げ計算を行うために、ランクLの値に初期値としてL=2を代入し、Lが2以上M+N以下となる条件を満たす間だけLを1ずつ増加させる処理を行うことによって、(m,n)平面における各座標(m,n)の値についての累積処理を行う。

【0080】
このようにして求められる最適累積値D(i,j,m,n)は、上述した式17および式18に示すように、D(i’,j’,m-1,n)とD(i”,j”,m,n-1)とにより求められる値を用いて計算される。従って、最終的にCPU2は、対象画像Sの各(i,j)座標において上述した最適な累積値D(i,j,M,N)の値を、次の式19に基づいて計算することができる。
【数18】
JP0005247481B2_000019t.gif

【0081】
このようにして求められる累積最適値D(i,j,M,N)は、上述したように、点(i,j)において2次元的に分布するパターンとして求められる。ここで、この2次元分布において局所的に最小となる点が、上述したスポッティング点である。つまり、対象画像Sの(i,j)に対応するスポッティング点は、D(i,j,M,N)における最小となる点であり、
【数19】
JP0005247481B2_000020t.gif
により求められることになる。(i,j)平面上で、局所的な領域で最小点の値が閾値よりも小さい場合には、その局所領域の点において、参照画像Rに類似する対象画像Sの部分画像が最適にマッチングしていると判断することができる。したがって、そのような局所領域が複数ある場合は、複数個の類似の参照画像Rが存在することを意味することになる。

【0082】
このため、スポッティング点において、累積最適値D(i,j,M,N)を出発点としてバックトレース処理を行うことにより、参照画像Rの部分領域を示す
(ξ(m,n),η(m,n)) 但し、1≦m≦M,1≦n≦N
を、以下のアルゴリズムに基づいて得ることができる。ここで、(ξ(m,n),η(m,n))は、対象画像Sの座標点(i,j)に対応している。

【0083】
まず、m,nは、それぞれ固定された値であると仮定する。すると
(i,j)は、
【数20】
JP0005247481B2_000021t.gif
で示すことができ、(i**,j**)は、
【数21】
JP0005247481B2_000022t.gif
で求めることができる。このため、(ξ(m,n),η(m,n))は、
(ξ(m,n),η(m,n))
=(i**(m,n),j**(m,n)) ・・・式23
により求めることができる。

【0084】
この式21~式23に基づいて、mの値をM≧m≧1の範囲内でMから1まで1ずつ減少させると共に、nの値をN≧n≧1の範囲内でNから1まで1ずつ減少させることにより、全てのmおよびnに対応する(ξ(m,n),η(m,n))を求めることができる。
このように、式21~式23を繰り返し計算してバックトレース処理を行うことにより、参照画像Rに最適に対応する対象画像Sの部分画像を取り出すことが可能となる。

【0085】
なお、通常、参照画像Rには特定の対象物の画像が示されているが、その画像の外縁形状はさまざまである。例えば、背景画像のように画像パターンのマッチング処理の対象とならない画像(対象物以外の画像)が含まれている場合には、適切に対象画像のみを抽出しないと、精度良く画像パターンのマッチング処理を行うことができない。このため、例えば図10に示すように、対象物となる画像以外の領域の局所距離の値を1に設定することにより、背景部分を取り除くことが可能となり、参照画像Rにおいて対象物だけの画像をマッチング処理の対象とすることが可能となる。

【0086】
次に、上述した処理内容を、図11に示すフローチャートを示すことによって、CPU2がプログラムに基づいて実行する画像パターンのマッチング処理について説明する。

【0087】
まずCPU2は、まず、変数lに2を設定(l=2)する(ステップS.1)。次に、CPU2は、変数mに1を設定(m=1)すると共に、変数nに1を設定(n=1)する(ステップS.2)。そして、CPU2は、式17に基づいて、(i’,j’,m-1,n)を求めると共に、式18に基づいて、(i”,j”,m,n-1)を求める(ステップS.3)。

【0088】
そして、CPU2は、求められた(i’,j’,m-1,n)および(i”,j”,m,n-1)に基づいて、dxx(i,j,m,n)、dxy(i,j,m,n)、dyy(i,j,m,n)、dyx(i,j,m,n)の4つ値を算出する(ステップS.4)。

【0089】
その後、CPU2は、求められたdxx(i,j,m,n)、dxy(i,j,m,n)、dyy(i,j,m,n)、dyx(i,j,m,n)の4つ値を用いて、式16によりD(i,j,m,n)を求める(ステップS.5)。そして、CPU2は、mおよびnの値が、1≦m≦Mおよび1≦n≦Nの条件を満たすか否かの判断を行う(ステップS.6)。

【0090】
mおよびnの値が、1≦m≦Mおよび1≦n≦Nの条件を満たす場合(ステップS.6においてYesの場合)、CPU2は、mおよびnの値に1を加算し(m=m+1、n=n+1)(ステップS.7)、処理をステップS.3に移行する。

【0091】
一方で、mおよびnの値が、1≦m≦Mおよび1≦n≦Nの条件を満たさない場合(ステップS.6においてNoの場合)、CPU2は、lの値が、2≦l≦M+Nの条件を満たすか否かの判断を行う(ステップS.8)。

【0092】
lの値が、2≦l≦M+Nの条件を満たす場合(ステップS.8においてYesの場合)、CPU2は、lの値に1を加算し(l=l+1)(ステップS.9)、処理をステップS.2に移行する。

【0093】
一方で、lの値が、2≦l≦M+Nの条件を満たさない場合(ステップS.8においてNoの場合)、CPU2は、求められた累積最適値D(i,j,M,N)に基づいて、バックトレース処理を行うことにより、対象画像Sのピクセルと参照画像Rのピクセルとの対応関係を求め(ステップS.10)、画像パターンのマッチング処理を終了する。

【0094】
このように、画像パターンのマッチング処理を行うことにより、非線形に対応する画像パターンの対応をピクセル毎に求めることが可能となる。さらに、このピクセル毎の対応を求める過程において、ランクLという概念を採用し、(m,n)平面において画像の対角方向の累積値を積み上げることにより累積最適値Dを求めるので、累積時において局所的な単調連続性を確保することが可能となる。さらに、図6(a)および図6(b)に示すように、局所パスに対して、遷移パターンを制限することにより累積最適値Dを求めるので、単調連続性の保証を確保することが可能となる。

【0095】
従って、本実施の形態に示した画像パターンのマッチング方法を用いて求められる対象画像Sのピクセルと参照画像Rのピクセルとの対応関係は、非線形対応を許容しつつ、かつ、単調連続性の保証を確保することができ、さらに、動画のように連続した画像ではなく、類似する画像パターンが示された異なる少数の画像に基づいて、ピクセル毎の対応関係を求めることが可能となる。

【0096】
図12は、上述した画像パターンのマッチング方法を用いて子供の顔が含まれる参照画像Rに基づいて、対象画像Sより対応する画像を抽出する処理を説明するための図である。図12(a)には、子供の顔が含まれる参照画像Rが示されており、(b)には、背景画像などが取り除かれた対象物(子供の顔)だけの画像が示されている。

【0097】
一方で、(c)には、子供の顔の画像だけでなく、その背景画像や、他の人物の顔画像などが含まれる対象画像Sが示されている。CPU2が上述した画像パターンのマッチング方法を用いてマッチング処理を行うことにより、対象画像S(図12(c))と参照画像Rにおける対象物だけの画像(図12(b))とに基づいてスポッティング点を求めることができ、求められたスポッティング点に基づいて、図12(c)に示される対象画像Sから、図12(d)に示すように、参照画像Rに示された類似する画像パターンである子供の顔の画像だけを抽出することが可能となる。

【0098】
以上、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムについて図面を用いて説明を行ったが、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムは、上述した実施の形態に示した例に限定されるものではない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものである。

【0099】
また、本発明に係る画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムを、さまざまコンピュータサイエンスに応用することが可能である。

【0100】
例えば、本実施の形態に示した2次元連続動的計画法を用いて画像パターンのマッチング処理を行うと共に、この画像パターンのマッチング処理に因子分解法を組み合わせることによって、図13に示すように、対象物が示された少ない枚数の画像に基づいて、対象物の3次元形状を復元することも可能となる。このため、数枚の画像に基づいて、対象物を3次元的な視点で、さらに、自由な視点角度(視点方向)で表示させることが可能となる。

【0101】
さらに、本実施の形態に示した2次元連続動的計画法を用いた画像パターンのマッチング処理を応用することにより、医療用の撮影画像(例えば、CT(Computed Tomography:コンピュータ断層撮影)画像)における病変患部の検出処理に利用することが可能である。

【0102】
一般的に、CT画像などを用いて診断を行う場合には、医師が、撮影されたCT画像と正常な人間のCT画像とを比較して、撮影されたCT画像に疑わしい部位が含まれていないかどうかを判断することにより、患部の特定が行われる。この判断において重要な点は、正常な画像と疑わしい部位が含まれる画像との違いを計算機で判断することは、困難であるということである。人間が2つの画像における類似・非類似を判断することは比較的簡単であるが、このような判断の簡単さは、人間が非線形の画像変形を容易に判断する能力を備えているためである。一方で、計算機を用いてこの非線形の変形を検出することは容易ではなかった。

【0103】
本実施の形態に示した画像パターンのマッチング処理を用いることにより、非線形の変動を考慮したマッチング処理を行うことが可能となるため、画像における正常な部位と疑わしい部位との差異を容易に検出することが可能となる。

【0104】
さらに、本実施の形態に示した画像パターンのマッチング処理を、CT画像のスライス画像群に適用することにより、ピクセル単位でスライス画像全体を通じた対応関係を求めることができる。このため、器官の部位を指定することにより、その部位に対応するピクセル対応を求めることができ、その器官のみの3D画像を容易に抽出することが可能となる。
【符号の説明】
【0105】
1 …画像パターンマッチング装置
2 …CPU(画像処理手段)
3 …ROM
4 …RAM
5 …記録部(記録手段)
6 …ディスプレイ部
7 …操作部
R …参照画像
S …対象画像
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12