(57)【要約】【課題】運動方程式の計算量を軽減する画像マッチング方法を提供する。【解決手段】対象画像に対象格子点及び参照画像に対象格子点と１対１で参照格子点を設定し、対象画像をクラスタに分割して各クラスタの代表対象格子点を決定し、これに対応する参照格子点(y)である代表参照格子点の画素情報、代表対象格子点の画素情報、代表参照格子点と代表対象格子点との位置関係により求まる画像相関ポテンシャルエネルギーの勾配により代表参照格子点が受ける画像相関力を算出し、各クラスタに属する各対象格子点(x)に対応する参照格子点(y)に作用する画像相関力を算出画像相関力に設定し、各参照格子点に作用する画像相関力、参照格子点と隣接参照格子点との間の弾性エネルギーにより参照格子点が受ける弾性力、参照格子点に作用する摩擦力を用いて、参照格子点に関する運動方程式を構築し、運動方程式を数値解析して各参照格子点(y)の平衡状態を求める。【選択図】      図７
2006227828.tif 000002
【特許請求の範囲】
【請求項１】
対象画像と参照画像間の対応関係を求める画像マッチング方法において、
前記対象画像に複数の対象格子点を設定するとともに、前記参照画像に前記対象画像上の対象格子点の各々と１対１に対応する参照格子点を設定するステップと、
前記対象画像を少なくとも一つの対象格子点を含む複数のクラスタに分割し、各クラスタの代表対象格子点を決定するステップと、
前記参照画像上で前記代表対象格子点に対応する参照格子点である代表参照格子点の画素情報、前記代表対象格子点の画素情報、および、前記代表参照格子点と前記代表対象格子点との位置関係によって求まる画像相関ポテンシャルエネルギーの勾配によって前記代表参照格子点が受ける画像相関力を計算するステップと、
前記各クラスタに属する対象格子点の各々に対応する参照格子点に作用する前記画像相関力を、当該クラスタの代表対象格子点に対応する代表参照格子点について算出された前記画像相関力に設定するステップと、
前記参照画像上の参照格子点の各々に関して、当該参照格子点に作用する前記画像相関力、当該参照格子点と当該参照格子点に隣接する他の参照格子点との間の弾性エネルギーによって当該参照格子点が受ける弾性力、および、当該参照格子点に作用する摩擦力を用いて、当該参照格子点に関する運動方程式を構築するモデル生成ステップと、
前記運動方程式を数値解析することによって前記参照格子点の各々の平衡状態を求める数値解析ステップと、
を有することを特徴とする画像マッチング方法。
【請求項２】
前記代表対象格子点を決定するステップにおいて、前記クラスタは画面全体で一様なブロックとすることを特徴とする請求項１に記載の画像マッチング方法。
【請求項３】
前記代表対象格子点を決定するステップは、前記対象画像の前記画像情報に基づき領域分割し、その領域分割の結果をクラスタとするステップを含むことを特徴とする請求項１に記載の画像マッチング方法。
【請求項４】
前記代表対象格子点を決定するステップは、前記対象画像の輝度情報に基づき領域分割をおこなうステップを含むことを特徴とする請求項１又は３に記載の画像マッチング方法。
【請求項５】
前記代表対象格子点を決定するステップは、前記対象画像の色の類似度に基づき領域分割をおこなうステップを含むことを特徴とする請求項１又は３に記載の画像マッチング方法。
【請求項６】
前記計算ステップは、前記代表対象格子点と前記対象格子点との間の距離と、前記代表対象格子点を写像した前記参照画像上の前記代表参照格子点と前記参照格子点との距離の比がある値より大きい場合には、前記代表対象格子点における前記画像相関ポテンシャルエネルギーの勾配によって受ける力ではなく、前記対象格子点と前記参照格子点の位置関係によって求まる画像相関ポテンシャルエネルギーの勾配によって受ける力を計算することを特徴とする請求項１、３又は４に記載の画像マッチング方法。
【請求項７】
前記代表対象格子点を決定するステップは前記クラスタの大きさに応じて複数の代表対象格子点を決定し、前記計算ステップは代表対象格子点毎に前記画像相関ポテンシャルエネルギーの勾配によって受ける力を計算し、複数の計算結果の平均を前記クラスタの代表力とする請求項１又は３に記載の画像マッチング方法。
【請求項８】
対象画像と参照画像間の対応関係を求める画像マッチング装置において、
前記対象画像に複数の対象格子点を設定するとともに、前記参照画像に前記対象画像上の対象格子点の各々と１対１に対応する参照格子点を設定する設定手段と、
前記対象画像を少なくとも一つの対象格子点を含む複数のクラスタに分割し、各クラスタの代表対象格子点を決定する決定手段と、
前記参照画像上で前記代表対象格子点に対応する参照格子点である代表参照格子点の画素情報、前記代表対象格子点の画素情報、および、前記代表参照格子点と前記代表対象格子点との位置関係によって求まる画像相関ポテンシャルエネルギーの勾配によって前記代表参照格子点が受ける画像相関力を計算する計算手段と、
前記各クラスタに属する対象格子点の各々に対応する参照格子点に作用する前記画像相関力を、当該クラスタの代表対象格子点に対応する代表参照格子点について算出された前記画像相関力に設定する設定手段と、
前記参照画像上の参照格子点の各々に関して、当該参照格子点に作用する前記画像相関力、当該参照格子点と当該参照格子点に隣接する他の参照格子点との間の弾性エネルギーによって当該参照格子点が受ける弾性力、および、当該参照格子点に作用する摩擦力を用いて、当該参照格子点に関する運動方程式を構築するモデル生成手段と、
前記運動方程式を数値解析することによって前記参照格子点の各々の平衡状態を求める数値解析手段と、
を具備することを特徴とする画像マッチング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、２つの画像から対応点を検出し画像マッチングをおこなう画像マッチング方法及び装置に関する。
【背景技術】
【０００２】
動き検出、ステレオマッチング、画像モーフィング、画像認識、動画像符号化、など多くの技術分野において、一つの画像から他方の画像への対応関係を求める画像マッチングの技術は基本的な問題である。
【０００３】
「非特許文献１」によれば、画像マッチングの技術は大きく分けて４つに分類できる。オプティカルフロー手法、ブロックベース手法、勾配法、ベイジアンメソッドである。オプティカルフロー手法は、「輝度の変化は一定である」というオプティカルフロー式を導出しそのオプティカルフロー式を拘束条件としてフローを求めるものである。ブロックベースの手法はブロック毎のテンプレートマッチングによって動きを求める手法である。勾配法は画像の輝度勾配が減少する方向にマッチングをおこなう手法である。ベイジアンメソッドは確率的にもっともらしいマッチングを求める手法である。
【０００４】
「特許文献１」には上記の分類には属さない技術として多重解像度フィルタを用いた画像マッチングの方法が開示されている。この手法は複数の多重解像度フィルタによって複数の多重解像度画像ピラミッドを生成し、画像ピラミッドを上から順にマッチング処理をおこなうことによって大きな動きから小さな動きまでマッチング可能なロバスト性の高いマッチング技術である。
【特許文献１】特許第２９２７３５０号公報
【非特許文献１】A. Murat Tekalp, “Digital Video Processing”, Prentice Hall, 1995
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、このような従来の画像マッチング技術には次のような問題がある。オプティカルフロー手法では、ノイズに敏感で速い動きに対応することが本質的に困難であるという問題があり、ブロックベースの手法では、画像の中のブロック毎に画像マッチングを行っているので、画像中のオブジェクトの平行移動などの動きには高い信頼性を有するが、画像中のオブジェクトが変形したり、回転したりする等の動きに対して本質的に対応することが難しいという問題がある。勾配法では、画像の輝度勾配が減少する方向にマッチングを行うため、安定してオブジェクトの動きを探索することが困難であるという問題がある。ベイジアンメソッドでは、大域的最適点の求め方が困難であるという問題がある。
【０００６】
一方、特許文献１に開示された技術では、原理的に複数の多重解像度フィルタを必要とする。また静的な拘束条件を加えた静的な最適化を各画素毎に局所的におこなうため画面全体のエネルギーが必ずしも最適になるとは限らない。
【０００７】
一般的な従来手法ではフレーム間の相関が低くなるほどマッチングが困難になる傾向にある。よって画像が大きく変形したり、速い動きのオブジェクトが含まれる画像などではマッチングが困難である。特許文献１の技術はよりロバストであるが、本質的には静的な局所最適化であるので、生成される写像が画面全体として最適である保証はない。運動方程式を用いて対象画像と参照画像との画像マッチングを行う場合、全格子点について画像相関ポテンシャルエネルギーの勾配によって受ける力を求めるので計算が重くなる。
【０００８】
本発明は、対象画像と参照画像間の対応関係を求める画像マッチングにおいて運動方程式の計算量を軽減する画像マッチング方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の第１局面は、対象画像と参照画像間の対応関係を求める画像マッチングにおいて、前記対象画像に複数の対象格子点を設定するとともに、前記参照画像に前記対象画像上の対象格子点の各々と１対１に対応する参照格子点を設定するステップと、前記対象画像を少なくとも一つの対象格子点を含む複数のクラスタに分割し、各クラスタの代表対象格子点を決定するステップと、前記参照画像上で前記代表対象格子点に対応する参照格子点である代表参照格子点の画素情報、前記代表対象格子点の画素情報、および、前記代表参照格子点と前記代表対象格子点との位置関係によって求まる画像相関ポテンシャルエネルギーの勾配によって前記代表参照格子点が受ける画像相関力を計算するステップと、前記各クラスタに属する対象格子点の各々に対応する参照格子点に作用する前記画像相関力を、当該クラスタの代表対象格子点に対応する代表参照格子点について算出された前記画像相関力に設定するステップと、前記参照画像上の参照格子点の各々に関して、当該参照格子点に作用する前記画像相関力、当該参照格子点と当該参照格子点に隣接する他の参照格子点との間の弾性エネルギーによって当該参照格子点が受ける弾性力、および、当該参照格子点に作用する摩擦力を用いて、当該参照格子点に関する運動方程式を構築するモデル生成ステップと、前記運動方程式を数値解析することによって前記参照格子点の各々の平衡状態を求める数値解析ステップとを有することを特徴とする画像マッチング方法を提供する。
【００１０】
本発明の第２局面は、対象画像と参照画像間の対応関係を求める画像マッチング装置において、前記対象画像に複数の対象格子点を設定するとともに、前記参照画像に前記対象画像上の対象格子点の各々と１対１に対応する参照格子点を設定する設定手段と、前記対象画像を少なくとも一つの対象格子点を含む複数のクラスタに分割し、各クラスタの代表対象格子点を決定する決定手段と、前記参照画像上で前記代表対象格子点に対応する参照格子点(y)である代表参照格子点の画素情報、前記代表対象格子点の画素情報、および、前記代表参照格子点と前記代表対象格子点との位置関係によって求まる画像相関ポテンシャルエネルギーの勾配によって前記代表参照格子点が受ける画像相関力を計算する計算手段と、前記各クラスタに属する対象格子点の各々に対応する参照格子点に作用する前記画像相関力を、当該クラスタの代表対象格子点に対応する代表参照格子点について算出された前記画像相関力に設定する設定手段と、前記参照画像上の参照格子点の各々に関して、当該参照格子点に作用する前記画像相関力、当該参照格子点と当該参照格子点に隣接する他の参照格子点との間の弾性エネルギーによって当該参照格子点が受ける弾性力、および、当該参照格子点に作用する摩擦力を用いて、当該参照格子点に関する運動方程式を構築するモデル生成手段と、前記運動方程式を数値解析することによって前記参照格子点の各々の平衡状態を求める数値解析手段とを有することを特徴とする画像マッチング装置を提供する。
【発明の効果】
【００１１】
各クラスタ内で画像相関ポテンシャルエネルギーによる力Fuを計算する代表対象格子点を決定し、各代表対象格子点における力Fuをクラスタ内の他の点の力として割り当てるので、計算量が重くなる画像相関ポテンシャルエネルギーによる力Fuの計算が、全格子点に関して実行する必要がなく、計算時間が短縮される。
【発明を実施するための最良の形態】
【００１２】
［第１の実施の形態］
第１の実施の形態を図１のブロック図に従って説明する。  
図１によると、例えば、メモリなどを含むプロセッサにより構成される画像マッチング部１１がモデル生成モジュール１２と数値解析モジュール１３とを有する。画像マッチング部１１に対象画像と参照画像の２枚の画像が入力されたときに、フレームメモリの両画像の同じ部分、例えば３Ｄ画像の同じ部分をマッチングする。即ち、２つの画像が入ってきたときに力学的な概念を用いて動的なモデルを生成する。この動的モデルが常微分方程式の形でモデル生成モジュール１２から出力されるので、数値解析モジュール１３はその出力を一般の数値解法により反復的に解いていく。反復計算の最終回に得られる結果の画像がマッチングの最終状態となり、写像として出力される。本実施形態では、例えば、プロセッサにより構成される代表対象格子点決定モジュール１４及び画像相関ポテンシャルエネルギー計算モジュール１５が設けられており、後述するように画像を複数のクラスタに分割し、各クラスタの画素の少なくとも１つを代表対象格子点として画像相関ポテンシャルエネルギーによる力を算出し、この算出値を同クラスタ内の各画素についての運動方程式に適用する。
【００１３】
本実施の形態では、対象画像と参照画像が入力され、それらの画像間の写像関係を求める。本実施の形態では従来技術の困難を、画面全体を動的システムとして捉えることによって、画面全体が系の自然な最適状態に収束する特徴を用いて解決する。まずは、基本となる画像マッチングステップについて説明する。対象とする画像として以下のようなモデルを考える。
【００１４】
連続画像モデル
【数１】
2006227828.tif 000003
【００１５】
これは実数ベースの連続な画像モデルである。ここではデジタル画像を対象と考えているので、上記のモデルをサンプリングした以下のモデルを用いる。
【００１６】
サンプリング画像モデル
【数２】
2006227828.tif 000004
【００１７】
（ただしこの定式化の場合、暗に同じ対象物の画像値は時間変化をしないと仮定している）。また、動きベクトルdが実数なので、右辺は連続画像モデル（数式（１））の表記を用いていることに注意が必要である。ここでは対象画像と参照画像、２枚の画像間の画像マッチングを考えているので、等価な以下の問題を考える。
【数３】
2006227828.tif 000005
【００１８】
画像マッチング問題
【数４】
2006227828.tif 000006
【００１９】
x=Vnであるからxは格子空間上の点nに一意に対応する。写像gは一意写像であるからyもxに一意に対応する。故に、yはnに一意に対応する。このことを図で表すと図２のようになる。つまりここで取り扱いたい空間は格子空間上の点nによって１対１に対応する変形格子空間である。
【００２０】
以上のようにy=g(x)=g(Vn)なので、nに１対１に対応することを分かりやすくするために、これを次式（８）と再定義する。
【数５】
2006227828.tif 000007
【００２１】
画像マッチング問題
【数６】
2006227828.tif 000008
【００２２】
数式（９）を解くためにここでは点ynに対してダイナミクスを導入する。つまり画像マッチング問題を点ynに関する動的システムを解く問題に帰着させる。このイメージ図を図３に示した。点ynは周りの点との関係も考慮しつつ数式（９）を満たす状態に移動していき平衡状態に収束する。その平衡状態をもって画像マッチング問題が完了したとする。
【００２３】
点yに対して新たな時間軸τ∈Rを導入し関数yn(τ)を定義する。ここで初期値は次式（１０）のように正方格子xと同一であるとする。
【数７】
2006227828.tif 000009
【００２４】
新たな時間軸を導入したので、時間に関する微分が次式（１２）のように定義できる。
【数８】
2006227828.tif 000010
【００２５】
通常ダイナミクスは次式（１３）のような常微分方程式によって記述される。
【数９】
2006227828.tif 000011
【００２６】
ここでF∈R2は力の総和である。これは運動方程式とも呼ばれる。
【００２７】
次に、yn(τ)にかかる力について考える。まずは、ダイナミクスを駆動させる力となるポテンシャルエネルギーによる力を考える。これはyn(τ)が数式（９）を満たす状態に移動するための力である。数式を変形すると数式（１４）となる。
【数１０】
2006227828.tif 000012
【００２８】
しかし、通常数式（１４）を厳密に満たす点を探すことは、画像に含まれるノイズ成分などにより困難である。そこで次式（１５）で示すようなエネルギー関数を考え、このエネルギー関数Euが最小となる点を探すようにする。
【数１１】
2006227828.tif 000013
【００２９】
最急降下法の原理を用いれば、yn(τ)の周りでエネルギー関数Euの最急降下の方向に下っていくことによりローカルミニマムに行き着くことができる。よってこの最急降下の方向への勾配をyn(τ)に対する力として定義する。エネルギー関数Euは画像の相関とも考えられるので、この力を画像相関ポテンシャルエネルギーによる力Fuとする。
【００３０】
最急降下の方向への勾配を計算する方法は色々考えられるが、ここでは次のような方法を採用する。図４（ｂ）に示すように、最急降下方向への勾配は局所最適化によって直接求める。画像モデルScは連続の画像モデルだが、実際にはサンプリングされた画像モデルSpしか利用できない。そこで局所最適化もサンプリングされた画像モデルをベースにおこなう。yn(τ)にもっとも近いサンプリング点を局所空間中心ycとしたいので、次式（１６）のように求める。
【数１２】
2006227828.tif 000014
【００３１】
局所最適化をしてその方向へのベクトルを求め、それを正規化し勾配の大きさをかけると次式が得られる。
【００３２】
画像相関ポテンシャルエネルギーによる力（二乗誤差エネルギー）式（１９）  
【数１３】
2006227828.tif 000015
【００３３】
実装上の扱いやすさ等からエネルギー関数を次式（２０）と定義した画像相関ポテンシャルエネルギーによる力（絶対値差分誤差エネルギー）（式（２１））を用いることもできる。
【数１４】
2006227828.tif 000016
【００３４】
次に、周辺の点との関係を記述する力について考える。マッチング対象の画像は３次元空間を２次元に投影したものだとする。３次元空間上のオブジェクトが剛体とすると、２次元画像では剛体のサーフェスがオブジェクトとして観測されることになる。３次元空間上のオブジェクトが対象画像と参照画像で観測されるとすると、このときそれぞれの画像上で観測されるオブジェクトの位相は保たれる確率が高い。図５に示すように、対象画像オブジェクト上の点xの位置関係は参照画像オブジェクト上の点yn(τ)でも保たれるはずである。この性質は点yn(τ)の間をバネで接続することによってシミュレーションできる。周辺との関係はバネの力Fkによって記述する。次のように、まずは対象点周辺の格子点空間Nnを定義する。周囲４点であれば次式（２２）のようになる。
【数１５】
2006227828.tif 000017
【００３５】
バネ定数（弾性定数）をkとすれば、点yn(τ)にかかるバネの復元力は数式（２３）で表されるバネ力（弾性力）となる。なお、弾性定数は画像相関エネルギーと弾性エネルギーのバランサーであり、弾性定数が大きければ変形がしにくくなり結果が安定する。しかし画像への適合性が悪くなる。弾性定数が小さければ変形がしやすくなるので画像の適合性が良くなる。ただし結果が柔軟になりすぎる。そこで、現在のところ、このパラメータは経験的に与えられる。挙動はこのパラメータの値にそれほど敏感ではではないので、基本的にはある一定値を固定的に与えられる。
【００３６】
バネの力
【数１６】
2006227828.tif 000018
【００３７】
周囲４点を接続すると具体的には次式（２４）のようになる。
【００３８】
４点接続バネモデル
【数１７】
2006227828.tif 000019
【００３９】
最後に保存されたエネルギーを散逸させる力について考える。yn(τ)にかかる力がFu, Fkのみではエネルギーが保存されてしまうために系が振動する定常状態となってしまう。そこで保存されているエネルギーを散逸させる力を導入する。これには摩擦力が利用できる。速度が一定と近似できる場合には摩擦力は次式（２５）で記述できる。
【００４０】
摩擦力
【数１８】
2006227828.tif 000020
【００４１】
以上の力をまとめると運動方程式は次式（２６）のようになる。
【００４２】
運動方程式
【数１９】
2006227828.tif 000021
【００４３】
画像相関ポテンシャルエネルギーによる力Fuが解析的には解けないため常微分方程式（２６）は解析的には解けない。故に、システムのτ→∞における極限を取ることは困難である。そこでシステムが収束するのに十分大きな時間Tを考え、数値解析によってt=(0,T)区間を計算することによってシステムの収束状態を推定する。
【００４４】
常微分方程式は初期値が決まれば、数値解析によって一意に解が求まる。一般には常微分方程式の初期値問題といわれるものである。この問題の数値解法は数多く存在するが、有名なものではオイラー法、ルンゲクッタ法、ブリルシュ・ストア法、予測子・修正子法、隠的ルンゲクッタ法などがある。ルンゲクッタ法がもっとも有名かつ使用頻度が高い。しかし式（２６）は画像のサイズ分の次元を持つため複雑な数値解法は適合しにくい。そこでここでは実現が最も簡単なオイラー法を応用することを考える。
【００４５】
オイラー法は一階の常微分方程式に対する数値解法なので、まずは、式（２７）を式（２６）に施して式（２６）を一階の常微分方程式に変換する。これにより変換された運動方程式（２８）が得られる。
【００４６】
変数変換
【数２０】
2006227828.tif 000022
【００４７】
変換された運動方程式
【数２１】
2006227828.tif 000023
【００４８】
常微分方程式（２９）に対するオイラー法のスキームは式（３０）により表される。  
【数２２】
2006227828.tif 000024
【００４９】
これはt(n)からt(n+1)≡t(n+1)+hへと解を進展させるものである。ここでx(n)はnステップであることを示しており、hはステップ幅である。オイラー法のスキームを数式（２８）に適用すると次式（３１）の更新式が得られる。
【００５０】
オイラー法による更新式
【数２３】
2006227828.tif 000025
【００５１】
そこでこれらの計算の無駄を省くために、図６に示すように画面全体を任意の形状のクラスタ（分割片）に分割し、各クラスタ内で画像相関ポテンシャルエネルギーによる力Fuを計算する代表対象格子点●を決定し、各代表対象格子点における力Fuをクラスタ内の他の点の力として割り当てる。即ち、次式（３２）のように最初の画素y5を代表対象格子点と決めた場合、この代表対象格子点(y5)における力Fuを求め、他の画素y1-y4, y6-ynに対しては代表対象格子点(y5)のFuを代入する。
【数２４】
2006227828.tif 000026
【００５２】
代表対象格子点をステップ毎にずらせばある周期ではすべての点に関して力Fuを計算したことに近似できる。任意形状のクラスタは正方ブロックを用いることができる。例えば、２×２正方ブロックまたは４×４正方ブロックなどを用いることができる。また、クラスタは正方ではなく長方形でも構わない。
【００５３】
代表対象格子点の決定は代表対象格子点決定ステップでおこなう。クラスタを２×２正方ブロックとして各クラスタ内の格子点のインデックスを次式（３３）のようにつける。
【数２５】
2006227828.tif 000027
【００５４】
代表対象格子点の決定法を例えば図７のように時間のステップに合わせて周期的に変化させる方法が考えられる。具体的には代表対象格子点を次式（３４）により決定する。
【００５５】
代表対象格子点決定方法１
【数２６】
2006227828.tif 000028
【００５６】
ここでmod(.)は余りを計算するものである。
【００５７】
また、一様乱数を使って次式（３５）により決定しても良い。
【００５８】
代表対象格子点決定方法２
【数２７】
2006227828.tif 000029
【００５９】
ここでuni_rand(.,.)は引数の範囲の一様整数乱数を生成するオペレータとする。
【００６０】
以上、画像マッチングをアルゴリズムとしてまとめると代表対象格子点決定方法２は図８のフローに示すようになる。
【００６１】
画像マッチングアルゴリズム：
【数２８】
2006227828.tif 000030
【００６２】
本実施の形態では従来技術の困難を、画面全体を動的システムとして捉えることによって、画面全体が系の自然な最適状態に収束する特徴を用いて解決した。
【００６３】
［第２の実施の形態］（領域分割利用）
本実施の形態を図９のブロック図に従って説明する。本実施の形態では、第１の実施の形態と同様、従来技術の困難を、画面全体を動的システムとして捉えることによって、画面全体が系の自然な最適状態に収束する特徴を用いて解決する。第１の実施の形態ではブロックを用いてクラスタを記述したのに対して、本実施の形態では領域分割の技術を用いて、より絵に適合したクラスタを利用する。
【００６４】
基本的な構成は第１の実施の形態と同様であるが、第１の実施の形態に領域分割モジュール１６が付加されている。即ち、画像マッチングステップ内に領域分割ステップが加わっている。第１の実施の形態では任意形状のクラスタとして２ｘ２の正方ブロックなどのブロックを用いたが、本実施の形態では領域分割の分割片を元にして絵に適合したクラスタを構築する。
【００６５】
ブロック型クラスタの場合にはひとつ問題点がある。図１０にオブジェクトと背景の境界に存在するブロック型クラスタの例が示されている。これは、オブジェクトが左に移動し、背景が右に移動している画像だとする。そのときオブジェクト上の格子点は左方向にポテンシャルエネルギーが発生し、背景上の格子点は右方向にポテンシャルエネルギーが発生する。また、代表対象格子点の決定方法は数式（３４）の方法を用いている。このときクラスタに発生するポテンシャルエネルギーによる力は図１０のように周期的に右方向、左方向を繰り返すことになる。時間方向に積算して考えるとクラスタとしては左方向への少しの力がかかっていることと等価になる。これは境界の挙動としては相応しいとはいえない。
【００６６】
この問題は動きの境界部分にまたがるようなクラスタが存在するから発生する。画面で一様なブロック型クラスタの場合にはこの境界にまたがるクラスタが発生する可能性が高い確率で存在する。
【００６７】
撮影された動画などのような通常の動画を考えると、動きの境界は多くの場合、画像のエッジと重なることが多くなる。画像のエッジ領域であることが動きの境界になることの必要条件となっていると考えることができる。そこで、図１１に示すように画像のエッジに沿った領域分割をすることが領域分割手段の必要条件となる。
【００６８】
上記の条件を満たす領域分割手段としてFast Watersheds法［L. Vincent and P. Soille; “Watersheds in Digital Spaces: An Efficient Algorithm Based on Immersion Simulations”, IEEE Trans. on Pattern Analysis and Machine Intell., Vol.13, No.6, 1991］があげられる。これは、差分オペレータによって処理対象の輝度画像から輝度勾配画像（エッジ抽出画像）を求め、そこで求まった輝度勾配の尾根によって囲まれる閉領域を一つの領域として分割する手法である。Fast Watershed法は、輝度勾配画像、つまりエッジを基準として、そのエッジの尾根によって囲まれる閉領域を一つの領域として分割する手法であるため、クラスタとエッジが正確に一致しやすい手法である。Fast Watersheds法は計算速度も考慮されており、画像マッチングステップ全体に比べれば計算量のインパクトは小さい。
【００６９】
次に、代表対象格子点決定ステップについて述べる。領域分割によって分割されたクラスタはサイズも形状もまちまちになるため、周期的にインデックスを変える第１の実施の形態（数式（３４））のような方法は取りにくい。そこで数式（３５）のようにランダムにインデックスを変更する決定方法を用いる。
【００７０】
クラスタ内の各格子点のインデックスを、図１２に示すように左上の点から右下方向に順番につけることとする。あるクラスタをciとすると代表対象格子点決定方法は次式（３６）のように記述できる。
【００７１】
代表対象格子点決定方法３
【数２９】
2006227828.tif 000031
【００７２】
ここでN(.)はクラスタ内の格子点数を計算するオペレータとする。
【００７３】
テストパターンにおいて実験をすると図１３のような成功例と失敗例が得られた。代表対象格子点を乱数によって生成しているが、この乱数の生成のされ方によって上手く行ったり行かなかったりする。これは代表対象格子点におけるポテンシャルがきちんと出る部分と出ない部分が存在するためと考えられる。よって上手くポテンシャルが計算できる部分が代表対象格子点に選ばれると結果がうまくいき、そうでないと失敗する。これはクラスタ内の代表対象格子点を増やすことによって改善できると考えられる。
【００７４】
クラスタには大きい物も小さい物も存在する。そこで代表対象格子点の数をクラスタ内の割合から求めるようにする。こうすればクラスタの数、サイズによらず画面全体の計算量を見積もることも可能である。クラスタ内で代代表対象表点とする格子点の割合をαとすると、代表対象格子点の数は次式（３７）と記述できる。
【００７５】
代表対象格子点の数
【数３０】
2006227828.tif 000032
【００７６】
例えば、次式（３８）に従って各代表対象格子点毎に画像相関ポテンシャルエネルギーによる力Fuを計算し、それらを平均してクラスタciの代表力Fuとする。
【００７７】
代表画像相関ポテンシャルエネルギーによる力Fu
【数３１】
2006227828.tif 000033
【００７８】
図１４にα＝０．２として４回の実験をおこなった結果を示した。安定して写像が計算できていることが分かる。
【００７９】
以上、画像マッチングをアルゴリズムとしてまとめると代表対象格子点決定方法２は図１５のフローに示すようになる。
【００８０】
画像マッチングアルゴリズム：
【数３２】
2006227828.tif 000034
【００８１】
本実施の形態では従来技術の困難を、画面全体を動的システムとして捉えることによって、画面全体が系の自然な最適状態に収束する特徴を用いて解決した。
【００８２】
［第３の実施の形態］（距離が離れていたら再計算）
本実施の形態を図１６のブロック図に従って説明する。本実施の形態では、第１の実施の形態と同様、従来技術の困難を、画面全体を動的システムとして捉えることによって、画面全体が系の自然な最適状態に収束する特徴を用いて解決する。第１の実施の形態ではブロック内の代表対象格子点をひとつに固定した構成であったが、本実施の形態では格子点間の状態によって代表対象格子点を適応的に選択する。即ち、代表対象格子点決定モジュール１１４が追加代表対象格子点を決定する機能を有する。
【００８３】
図１７に示すように、右下のパターンなどではクラスタ内の格子点が離れた位置に存在することがある。このような状況にもかかわらず、クラスタ内にひとつの代表対象格子点だけで計算していると結果が歪んでしまう。そこで、本実施の形態ではこのパターンのようにクラスタ内の格子点で距離が離れているものに関しては、それも代表対象格子点とするという方法を用いる。
【００８４】
代表対象格子点決定ステップに関して述べる。まず、代表対象格子点決定モジュール１４によって初期代表対象格子点を数式（３４）や数式（３５）の方法に従って決定する。この代表対象格子点をxd=Vndとする。このとき写像点はynd=g(xd)である。このときポテンシャル力を割り当てられる対象点をx=Vnとすると、その写像点はyn=g(x)である。ポテンシャルを割り当てずに追加で代表対象格子点にした方が良い不連続な点というのは図１７内の点線で接続された点である（割り当てはせずに再計算するということである）。このような点の定義を例えば次式（３９）のようにおこなう。
【００８５】
追加代表対象格子点決定
【数３３】
2006227828.tif 000035
【００８６】
これは格子点間の距離比が定数αを超えた点としたものである。
【００８７】
以上、画像マッチングをアルゴリズムとしてまとめると代表対象格子点決定方法２は図１８のフローに示すようになる。
【００８８】
画像マッチングアルゴリズム：
【数３４】
2006227828.tif 000036
【００８９】
本実施の形態では従来技術の困難を、画面全体を動的システムとして捉えることによって、画面全体が系の自然な最適状態に収束する特徴を用いて解決した。
【００９０】
上記実施形態において、代表対象格子点と対象格子点との間の距離と、代表対象格子点を写像した参照画像上の代表参照格子点と参照格子点の距離の比がある値より大きい場合には、代表対象格子点における画像相関ポテンシャルエネルギーの勾配によって受ける力ではなく、対象格子点と参照格子点の位置関係によって求まる画像相関ポテンシャルエネルギーの勾配によって受ける力を計算する。
【図面の簡単な説明】
【００９１】
【図１】本発明の第１の実施の形態に従った画像マッチング装置のブロック図
【図２】画像における各空間の繋がりを示す図
【図３】画像マッチング問題ｙｎに対するダイナミクスを示す図
【図４】画像相関ポテンシャルエネルギーによる力をイメージで示す図
【図５】対象画像上のオブジェクトと参照画像のオブジェクトの位相が保たれる状態を示す図
【図６】クラスタに分割した画像を示す図
【図７】代表対象格子点を選択する方法を説明する図
【図８】第１の実施の形態による画像マッチングアルゴリズムのフローチャート図
【図９】本発明の第２の実施の形態に従った画像マッチング装置のブロック図
【図１０】ブロック型クラスタの問題点を説明するための図
【図１１】クラスタ内ポテンシャル代表モデルを説明するための図
【図１２】クラスタ内のインデックスを示す図
【図１３】画像マッチングの成功例と失敗例を示す図
【図１４】αを０．２に設定したときの画像マッチング結果を示す図
【図１５】第２の実施の形態による画像マッチングアルゴリズムのフローチャート図
【図１６】本発明の第３の実施の形態に従った画像マッチング装置のブロック図
【図１７】第３の実施の形態を概念的に示す図
【図１８】第３の実施の形態による画像マッチングアルゴリズムのフローチャート図
【符号の説明】
【００９２】
１１…画像マッチング部、１２…モデル生成モジュール、１３…数値解析モジュール、
１４…代表対象格子点決定モジュール、１５…画像相関ポテンシャルエネルギー計算モジュール、１６…領域分割モジュール、１１４…代表対象格子点決定モジュール
【図１】
2006227828.tif 000037
【図２】
2006227828.tif 000038
【図３】
2006227828.tif 000039
【図４】
2006227828.tif 000040
【図５】
2006227828.tif 000041
【図６】
2006227828.tif 000042
【図７】
2006227828.tif 000043
【図８】
2006227828.tif 000044
【図９】
2006227828.tif 000045
【図１０】
2006227828.tif 000046
【図１１】
2006227828.tif 000047
【図１２】
2006227828.tif 000048
【図１３】
2006227828.tif 000049
【図１４】
2006227828.tif 000050
【図１５】
2006227828.tif 000051
【図１６】
2006227828.tif 000052
【図１７】
2006227828.tif 000053
【図１８】
2006227828.tif 000054