画像処理装置及びプログラム
【課題】変換係数を算出するための計算量を削減することができる画像処理装置を提供する。
【解決手段】画像処理装置は、画像Ａ（第１の画像）及び画像Ｂ（第２の画像）から抽出される特徴点に基づいて、画像の変換手法を決定する特徴点ペア選択部２２２及び変換係数算出部２２４と、前記決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下となる特徴点の組に基づいて、特徴点ペア選択部２２２及び変換係数算出部２２４が変換手法の決定を繰り返し行うように制御する有効特徴点ペア探索部２２６とを有する。
【解決手段】画像処理装置は、画像Ａ（第１の画像）及び画像Ｂ（第２の画像）から抽出される特徴点に基づいて、画像の変換手法を決定する特徴点ペア選択部２２２及び変換係数算出部２２４と、前記決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下となる特徴点の組に基づいて、特徴点ペア選択部２２２及び変換係数算出部２２４が変換手法の決定を繰り返し行うように制御する有効特徴点ペア探索部２２６とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２枚以上の画像の位置合わせを行う画像処理装置及びそのプログラムに関する。
【背景技術】
【０００２】
この種の画像処理装置は、２枚の画像から特徴点を抽出し、抽出された特徴点から例えば４個の特徴点をランダムに選択し、４個の特徴点の組（特徴点ペア）を形成する。画像処理装置は、特徴点ペアに基づいて変換手法を決定し、決定された変換手法を用いて一方の画像を変換して、他方の画像と位置を合わせる。この変換が所望の品質を満足する場合、決定された変換手法が採用される。
【０００３】
非特許文献１では、特徴点ペアを用いて射影変換行列を求める手法が開示されている。
非特許文献２では、ＲＡＮＳＡＣと呼ばれるアルゴリズムを用いて、正しい特徴点ペアを決定する手法が開示されている。
非特許文献３では、特徴点を抽出する代表的な手法である画像コーナー点抽出アルゴリズムが開示されている。
【０００４】
また、特許文献１では、対象物の平行・回転のずれ量を検出する手法が開示されている。
さらに、特許文献２では、分割画像を合成する際に、合成すべき分割画像を人手により大まかに重ね合わせて置くだけで、マッチング精度が高く、かつ処理量の少ない手法が開示されている。
【０００５】
【非特許文献１】I.Zoghlami, O.Faugeras, and R.Deriche, "Using geometric coeners to build a 2D mosaic from a set of images", CVPR'97, p.420-425, 1997.
【非特許文献２】R.Hartley and A. Zisserman, "Multiple View Geometry", Cambridge University Press p.116-127
【非特許文献３】C.Harris and M.Stephens, "A combined corner and edge detector", Proc. Alvey Vision Conf., p.147-151, 1988.
【特許文献１】特開平１０−２７２５３号公報
【特許文献２】特開平１０−１０８００３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１及び非特許文献２に開示された手法は、処理負荷が増大してしまうことがある。また、特許文献１に開示された手法は、平行移動及び回転のみを行うものであり、特許文献２に開示された手法は、平行移動のみを行うものである。
【０００７】
本発明は、上述した背景からなされたものであり、変換係数を算出するための計算量を削減することができる画像処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る第１の画像処理装置は、第１の画像及び第２の画像から抽出される特徴点に基づいて、画像の変換手法を決定する変換手法決定手段と、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下となる特徴点の組に基づいて、前記変換手法決定手段が変換手法の決定を繰り返し行うように制御する制御手段とを有する。本発明によれば、変換係数を算出するための計算量を削減することができる。
【０００９】
好適には、前記変換手法決定手段は、射影変換で用いられる変換係数を決定する。本発明によれば、変換が、例えば平行移動等に、制限されることを防止することができる。
【００１０】
好適には、前記変換手法決定手段は、第１の画像及び第２の画像から抽出される特徴点の周辺画素の画素値にさらに基づいて、画像の変換手法を決定する。本発明によれば、変換手法の決定が繰り返される回数が削減されるので、計算量をさらに削減することができる。
【００１１】
好適には、前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が、予め決められた値以上となるように制御する。本発明によれば、変換の精度がより良い変換係数を求めることができる。
【００１２】
好適には、前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が、予め決められた値未満である場合、前記変換手法決定手段が、当該特徴点の組とは異なる組を選択するように制御する。本発明によれば、少なくとも一定の精度以上の変換係数を求めることができる。
【００１３】
好適には、前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が収束した場合、当該収束した状態における変換手法に関する情報を出力する。本発明によれば、変換係数を算出する回数を所定値以下に抑えることができる。
【００１４】
好適には、前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点の周辺画素の画素値と、第２の画像の特徴点の周辺画素の画素値とにさらに基づいて、記変換手法決定手段が変換手法の決定を繰り返し行うように制御する。本発明によれば、変換手法の決定が繰り返されるように制御する回数が削減されるので、計算量をさらに削減することができる。
【００１５】
本発明に係る第２の画像処理装置は、特徴点に関する閾値及び割合に基づいて、第１の画像及び第２の画像から抽出される特徴点の数を算出する特徴点数算出手段と、第１の画像及び第２の画像から抽出された前記特徴点数算出手段により算出された数の特徴点から選択される特徴点の組のうち有効とされる組の数が特徴点に関する閾値以上となるように画像の変換手法を決定する変換手法決定手段とを有する。本発明によれば、適切な特徴点数が設定されるので、変換係数の算出の際に、処理負荷の増大を防止することができる。
【００１６】
好適には、前記特徴点数算出手段は、特徴点に関する閾値を割合で乗じた値に所定値が加算された値を特徴点の数とする。本発明によれば、有効特徴点数が、特徴点に関する閾値より高くなる確率が大きくなるので、試行回数が減少され、処理負荷を低減することができる。
【００１７】
好適には、前記変換手法決定手段は、変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が所定値以下である場合、当該特徴点の組は有効であると判定する。本発明によれば、特徴点の組が有効であるか否かの判定を簡易に行うことができる。
【００１８】
好適には、前記特徴点数算出手段により算出された数に基づいて試行回数の上限を算出する試行回数算出手段をさらに有し、前記変換手法決定手段は、前記試行回数算出手段により算出された試行回数の上限を超えない範囲で、変換手法を決定するための試行を繰り返す。本発明によれば、試行が終わることなく継続することを防止することができる。
【００１９】
好適には、前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、有効である特徴点の組が最大となる変換手法を選択する。
【００２０】
好適には、前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、第１の画像と第２の画像との間で重畳する画像部分がない旨の情報を出力する。
【００２１】
好適には、前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、減少された特徴点に関する割合を用いて試行を行う。
【００２２】
また、本発明に係る第１のプログラムは、コンピュータを含む画像処理装置において、第１の画像及び第２の画像から抽出される特徴点に基づいて、画像の変換手法を決定する変換手法決定ステップと、前記決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下となる特徴点の組に基づいて、前記変換手法の決定を繰り返し行うように制御する制御ステップとを前記画像処理装置のコンピュータに実行させる。
【００２３】
また、本発明に係る第２のプログラムは、コンピュータを含む画像処理装置において、特徴点に関する閾値及び割合に基づいて、第１の画像及び第２の画像から抽出される特徴点の数を算出する特徴点数算出ステップと、第１の画像及び第２の画像から抽出された前記算出された数の特徴点から選択される特徴点の組のうち有効とされる組の数が特徴点に関する閾値以上となるように画像の変換手法を決定する変換手法決定ステップとを前記画像処理装置のコンピュータに実行させる。
【発明の効果】
【００２４】
本発明の画像処理装置によれば、変換係数を算出するための計算量を削減することができる。
【発明を実施するための最良の形態】
【００２５】
まず、本発明の理解を容易にするため、本発明の背景を説明する。
画像内の物体が同一平面上にある場合又はカメラ運動が水平面での回転に制限されている場合、２枚の画像間の変換は、射影変換を用いて規定される。物体が複数平面の組み合わせで近似される場合、同一平面上にあるという制限は外されてもよい。
【００２６】
図１は、射影変換を説明する図である。
図１（Ａ）は、画像Ａ内の点(ｘＡ，ｙＡ)を、画像Ｂ内の点(ｘＢ，ｙＢ)に写す射影変換を示す。図１（Ａ）において、画像Ａは、平面ＸＹを視点ＯＡから見て平面ｘＡｙＡに投影した結果であり、画像Ｂは、平面ＸＹを視点ＯＢから見て平面ｘＢｙＢに投影した結果である。この場合、平面ｘＡｙＡ上の座標(ｘＡ，ｙＡ)と、平面ｘＢｙＢ上の座標(ｘＢ，ｙＢ) との関係は、射影変換で表される。
【００２７】
図１（Ｂ）は、同様の関係を見方を変えて説明する図である。図１（Ｂ）に示される３次元空間ＸＹＺにおいて、視点を原点Ｏとして、平面ｘＡｙＡ上の座標点(ｘＡ，ｙＡ)が、平面ｘＢｙＢ上の座標点(ｘＢ，ｙＢ) と重なって見える場合、座標(ｘＡ，ｙＡ)と、座標(ｘＢ，ｙＢ)との関係は、射影変換で表される。
【００２８】
この射影変換により、平面ｘＡｙＡ上の四角形は、平面ｘＢｙＢ上の四角形に変換される。なお、射影変換後の線分間の角度や長さ比等は、必ずしも保存されない。例えば、図１（Ｃ）に示されるように、平面ｘＡｙＡ上の正方形は、平面ｘＢｙＢ上では、変形した四角形に変換される。
このような射影変換は、同次座標系(homogeneous coordinates)における次式で表される。
【００２９】
【数１】
【００３０】
上式の３×３の行列を、射影変換行列（homography行列）と呼ぶ。以下、次式に示されるように、射影変換行列をＨとする。また、ｈｉｊを射影変換係数と呼ぶ。
【００３１】
【数２】
【００３２】
ここで、（１）式は、同次座標系における式であり、等号にはスケール因子が残る(定数倍が未定である)。即ち、（１）式の右辺又は左辺に、実数ｃを乗じても成り立つ。例えば、同次座標ではない(非同次座標の)変換式として、次式を考える。
【００３３】
【数３】
【００３４】
上式の変数ｃを、この式の第３行
【数４】
の関係式を用いて消去すると、次式が得られる。
【００３５】
【数５】
【００３６】
この式が、２次元平面上の点（ｘＡ，ｙＡ）を、点（ｘＢ，ｙＢ）に写す非同次座標系上の射影変換である。上式では、分母及び分子の全てに、係数ｈｉｊが、乗じられている。したがって、射影変換係数ｈｉｊの全てが定数倍された場合においても、結果の(ｘＢ, ｙＢ)は影響を受けない。つまり、射影変換係数の未知数は９個であるが、実際の自由度は８である。よって、８つの式が得られれば、射影変換は求められる。そこで、ｈ３３＝１とすると、次式が得られる。
【００３７】
【数６】
【００３８】
さらに、分母を両辺にかけると、（６）式は、次式のように変形される。
【００３９】
【数７】
【００４０】
（７）式は、ｈｉｊの連立一次方程式であるので、線形演算により解くことが可能である。８個の式を求めるためには、４個の特徴点のペアが与えられればよい。即ち、４個の特徴点ペアの２次元座標があれば、８個（特徴点ペア数４×次元数２）の式が得られる。なお、特徴点ペア数が５以上である場合には、式の数が未知数より多くなるので、連立方程式は、最小二乗法などを用いて解かれる。また、射影変換行列を求める手法は、数多く存在するので、どのような方法が用いられてもよい。
【００４１】
平行移動、剛体変換、拡縮変換、相似変換及びアフィン変換等のその他の幾何変換は、射影変換の一種として表現される。
変換が平行移動により実現される場合、平行移動ベクトルをｔ＝（ｔｘ，ｔｙ）Ｔとすると、変換式及び変換行列Ｈは、次のように表される。
【００４２】
【数８】
【００４３】
【数９】
【００４４】
この場合、自由度は、１である。したがって、平行移動は、１ペアの特徴点があれば算出されることができる。
【００４５】
剛体変換は、平行移動に回転が加えられた変換であり、形状や長さを変化させない等倍変換である。回転角θの回転行列をＲ（θ）とすると、変換式及び変換行列Ｈは、次のように表される。
【００４６】
【数１０】
【００４７】
【数１１】
【００４８】
この場合、自由度は、３である。したがって、剛体変換は、２ペアの特徴点があれば算出されることができる。
【００４９】
拡縮変換は、平行移動に拡大縮小が加えられた変換である。拡大縮小率をαとすると、変換式及び変換行列は、次のように表される。
【００５０】
【数１２】
【００５１】
【数１３】
【００５２】
この場合、自由度は、３である。したがって、拡縮変換は、２ペアの特徴点があれば算出されることができる。なお、拡縮倍率が縦方向と横方向とで異なる場合の変換は、後述するアフィン変換に含めるものとする。
【００５３】
相似変換は、平行移動に回転及び拡大縮小が加えられた変換であり、物体の形状を変化させない変換である。変換式及び変換行列Ｈは、次のように表される。
【００５４】
【数１４】
【００５５】
【数１５】
【００５６】
この場合、自由度は、４である。したがって、相似変換は、２ペアの特徴点があれば算出されることができる。
【００５７】
アフィン変換は、平行線を平行線に写す変換である。変換式及び変換行列Ｈは、次のように表される。
【００５８】
【数１６】
【００５９】
【数１７】
【００６０】
図２は、２枚の画像が入力された場合、この２枚の画像を重ね合わせるための射影変換係数を求める手法を例示する図である。
図２（Ａ）は、入力された２枚の画像（画像Ａ及び画像Ｂ）を例示し、図２（Ｂ）は、重ね合わされた画像Ａ及び画像Ｂを例示する。図２（Ａ）及び図２（Ｂ）に例示するように、平行移動、回転、拡大縮小等が、例えば画像Ａに対して施されると、画像Ａ及び画像Ｂに含まれる物体や模様などができるだけ同じ位置になるように、画像Ａと画像Ｂとは重ね合わされることができる。
【００６１】
図２（Ｃ）は、特徴点ペアを用いて射影変換行列を求める手法を示す図である。図２（Ｃ）に示すように、画像Ａの特徴点を、ａ１，ａ２，…，ａｉ，…とし、画像Ｂの特徴点を、ｂ１，ｂ２，…，ｂｉ，…とする場合、まず、４個の特徴点（ｐ１，ｐ２，ｐ３，ｐ４）が画像Ａから抽出され、４個の特徴点（ｑ１，ｑ２，ｑ３，ｑ４）が画像Ｂからも抽出される。次に、特徴点ペアが、（ｐ１−ｑ１），（ｐ２−ｑ２），（ｐ３−ｑ３），（ｐ４−ｑ４）のように決定される。この４個の特徴点ペアを用いて、射影変換行列が算出され、この射影変換行列を用いて、画像Ａが変換される。さらに、変換後の画像Ａと画像Ｂとの画素値の相互相関係数が算出される。このようにして、全ての特徴点ペアの組み合わせのうち、相互相関係数を最大とする射影変換行列が選択される。
【００６２】
上記のような手法においては、特徴点の数が多い場合、組み合わせの数が膨大になってしまう。例えば、画像Ａ内の特徴点の数をｎＡ、画像Ｂ内の特徴点の数をｎＢとする。この場合、画像Ａから４個、画像Ｂから４個の特徴点を抽出する組み合わせの数は、ｎＡ（ｎＡ−１）（ｎＡ−２）（ｎＡ−３）ｎＢ（ｎＢ−１）（ｎＢ−２）（ｎＢ−３）となる。例えば、ｎＡ＝ｎＢ＝１００とすると、組み合わせの数は、１０６となってしまう。
【００６３】
図２（Ｄ）は、ＲＡＮＳＡＣと呼ばれるアルゴリズムを用いて、正しい特徴点ペアを決定する方式を示す図である。まず、特徴点が、画像Ａ及び画像Ｂから抽出される。画像Ａの特徴点と、画像Ｂの特徴点のうち周囲の画素値が当該画像Ａの特徴点のものと似ている特徴点とが選択され、図２（Ｄ）に示されるａ１とｂ１、ａ２とｂ２及びａ３とｂ５のように、特徴点がペア化される。ここでペア化された特徴点は、正しい場合もあるし、間違っている場合もある。例えば、（ａ１−ｂ１）及び（ａ２−ｂ２）の特徴点ペアは正しいが、（ａ３−ｂ５）の特徴点ペアは間違っている。なお、図中では、特徴点ペアの数は３であるが、実際には、さらに多くの特徴点ペアが存在する。
【００６４】
４個の特徴点ペアが、複数の特徴点ペアからランダムに抜き出され、射影変換行列が算出される。この射影変換行列を用いて、画像Ａの特徴点の座標が変換される。変換後の画像Ａの特徴点の座標と、当該特徴点とペア化されている画像Ｂの特徴点の座標との距離が算出され、この距離が閾値以下となる特徴点ペアの数が算出される。このような特徴点ペアは、有効特徴点ペアと呼ばれ、その数は、有効特徴点ペア数と呼ばれる。このようにして、特徴点ペアのランダム抽出から有効特徴点ペア数の算出までの試行が、所定回数繰り返され、有効特徴点ペア数を最大とする射影変換行列が選択される。
【００６５】
また、上記のような手法において、試行回数Ｔには、正しい４個の特徴点ペアを選択することができる確率がＺとなる回数が設定される。より具体的には、試行回数Ｔは、以下のように設定される。
【００６６】
例えば４個の特徴点ペアが選択される場合、全ての特徴点ペアのうち、正しい特徴点ペアの割合をβとすると、その全てが正しい特徴点ペアである確率は、β４である。ここで、Ｔ回の試行以下で全てが正しい特徴点ペアとなる確率をＺ（例えば、０．９９）とすると、Ｔ回の試行で正解にたどり着かない確率は１−Ｚである。したがって、１−Ｚ＝（１−β４）Ｔ が成立する。この式を変形すると、次式となる。
【００６７】
【数１８】
【００６８】
また、試行回数Ｔは、次のように、適応的に決定されてもよい。まず、全特徴点ペア数をｎβとし、試行番号をＣ（初期値は、例えば０）とする。さらに、Ｃ≧Ｔとなるまで、以下の（ア）〜（ウ）の処理を繰り返す。これにより、正しい特徴点ペアの割合βが求められ、試行回数Ｔが設定される。
【００６９】
（ア）特徴点ペアをランダムに抽出し、射影変換行列を算出し、有効特徴点ペア数を求める。
（イ）β＝Ｋ／ｎβを求め、試行回数Ｔを（８）式を用いて求める。
（ウ）Ｃに１を加算する。
【００７０】
以上説明した処理においては、特徴点数又は特徴点ペア数が少ないほど、処理負荷は小さくなる。しかしながら、上記の手法では、特徴点数及び特徴点ペア数は、適切な値に設定されることができない。また、試行回数が少ないほど、処理負荷は小さくなる。しかしながら、試行回数は、処理負荷を小さくするように設定されることは困難である。特に、２つの画像が重なりを全く持たない場合、試行が、終わることなく続いてしまうことがある。
【００７１】
以下、本発明に係る画像処理装置を詳細に説明する。
図３は、本発明の実施形態に係る画像処理装置１０のハードウェア構成を示す図である。
図３に示すように、画像処理装置１０は、ＣＰＵ１０２及びメモリ１０４などを含む制御装置１００と、ネットワークを介して外部のコンピュータなどとデータの通信を行う通信装置１０６と、ハードディスク駆動装置などの記憶装置１０８と、液晶ディスプレイなどの表示装置並びにキーボード及びポインティングデバイスを含むユーザインタフェース（ＵＩ）装置１１０とを有する。画像処理装置１０は、例えば、後述する画像処理プログラム２０などがインストールされた汎用コンピュータであり、通信装置１０６、記憶装置１０８又はＦＤ、ＣＤ、ＤＶＤ等の記録媒体１１２を介して複数の画像のデータを取得し、取得された画像に対して画像処理を行う。
【００７２】
図４は、本発明の第１の実施形態に係る画像処理装置１０により実行される画像処理プログラム２０の機能構成を示す図である。
図４に示すように、画像処理プログラム２０は、画像位置合わせ部２２、画像変換部２４及び画像重ね合わせ部２６を有する。画像処理プログラム２０は、例えば、通信装置１０６を介して制御装置１００に供給され、メモリ１０４にロードされて、制御装置１００上で動作する図示しないＯＳ上で、ハードウェアを具体的に利用して実行される。画像処理プログラム２０は、記録媒体１１２に格納されて、画像処理装置１０に供給されてもよい。なお、画像処理プログラム２０の全部又は一部の機能は、画像処理装置１０に設けられた例えばＡＳＩＣ（Application Specific Integrated Circuit）などのハードウェアにより実現されてもよい。
【００７３】
画像処理プログラム２０において、画像位置合わせ部２２は、画像Ａ及び画像Ｂを入力し、画像Ａ及び画像Ｂの間の変換係数を算出して画像変換部２４に対して出力する。なお、画像位置合わせ部２２については、後で詳述する。
【００７４】
画像変換部２４は、画像位置合わせ部２２により算出された変換係数を用いて、画像Ａを変換し、変換後の画像Ａを画像重ね合わせ部２６に対して出力する。なお、画像変換部２４は、画像位置合わせ部２２に含まれてもよい。例えば、変換係数を求めるために、画像位置合わせ部２２において変換後の画像Ａが既に求められている場合、変換後の画像Ａが、画像位置合わせ部２２から画像重ね合わせ部２６に対して出力されてもよい。
【００７５】
画像重ね合わせ部２６は、変換後の画像Ａと、画像Ｂとを入力し、これらの画像を重ね合わせて合成画像を生成する。この合成画像は、画像Ａと画像Ｂとが組み合わせて作成された、画像Ａ及び画像Ｂよりも大きな画像である。なお、このような合成画像を、モザイク合成画像とも呼ぶ。
【００７６】
次に、画像位置合わせ部２２について、より詳細に説明する。
図５は、画像位置合わせ部２２による画像位置合わせ処理の概要を説明する図である。
図５（Ａ）は、画像位置合わせ部２２に入力される画像Ａ及び画像Ｂを例示する。図５（Ａ）に例示するように、画像Ａには、特徴点ａ１〜ａ４が含まれ、画像Ｂには、特徴点ｂ１〜ｂ４が含まれている。ここで、特徴点ａ１とｂ１、ａ２とｂ２、ａ３とｂ３、ａ４とｂ４は、ペアとなるべき組み合わせであるとする。なお、画像Ａの特徴点数と画像Ｂの特徴点数とは異なってもよい。
【００７７】
まず、画像位置合わせ部２２は、画像Ａの特徴点及び画像Ｂの特徴点から１つずつの特徴点を選択する。画像位置合わせ部２２は、特徴点ペアの数が１であるので、平行移動における変換係数を算出する。例えば、画像位置合わせ部２２は、ａ１とｂ４を選択したとする。
【００７８】
図５（Ｂ）は、特徴点ａ１とｂ４とから算出された変換係数を用いて変換された画像Ａと、画像Ｂとを示す。画像位置合わせ部２２は、特徴点ａ２との距離が閾値Ｔｈ１以下である画像Ｂの特徴点を探索する。同様に、画像位置合わせ部２２は、特徴点ａ３，ａ４との距離が閾値Ｔｈ１以下である画像Ｂの特徴点を探索する。その結果、画像位置合わせ部２２は、有効特徴点ペア数が閾値Ｔｈ２（例えば、４）未満である場合、再度、特徴点ペアを選択する。例えば、画像位置合わせ部２２は、ａ１とｂ１を選択したとする。
【００７９】
図５（Ｃ）は、特徴点ａ１とｂ１とから算出された変換係数を用いて変換された画像Ａと、画像Ｂとを示す。画像位置合わせ部２２は、特徴点ａ２との距離が閾値Ｔｈ１以下である画像Ｂの特徴点としてｂ２を検出したとする。同様に、画像位置合わせ部２２は、特徴点ａ３，ａ４との距離が閾値Ｔｈ１以下である画像Ｂの特徴点として、それぞれｂ３，ｂ４を検出したとする。その結果、画像位置合わせ部２２は、有効特徴点ペア数が閾値Ｔｈ２以上であるので、ａ１とｂ１のペアは正しいと判定する。
【００８０】
さらに、画像位置合わせ部２２は、有効特徴点ペア（ａ１−ｂ１），（ａ２−ｂ２），（ａ３−ｂ３），（ａ４−ｂ４）を用いて、新たな変換係数（射影変換行列）を算出して、再度、画像Ａを変換する。画像位置合わせ部２２は、このような処理を、特徴点ペアのパターンが変化しなくなるまで繰り返す。
【００８１】
図５（Ｄ）は、得られた変換係数を用いて変換された画像Ａと、画像Ｂとを示す。このようにして、最適な変換係数が、画像位置合わせ部２２により求められる。
【００８２】
図６は、変換行列Ｈが平行移動では近似できない場合における画像位置合わせ部２２による画像位置合わせ処理の概要を説明する図である。
画像Ａと画像Ｂの回転角が大きい場合等、変換行列Ｈが平行移動では近似できない場合、画像位置合わせ部２２は、最初に選択する特徴点ペアの数を２として、相似変換における変換係数を求める。
【００８３】
図６（Ａ）は、画像位置合わせ部２２に入力される画像Ａ及び画像Ｂを例示する。本例においても、図５に示される場合と同様に、特徴点ａ１とｂ１、ａ２とｂ２、ａ３とｂ３、ａ４とｂ４は、ペアとなるべき組み合わせであるとする。
【００８４】
まず、画像位置合わせ部２２は、特徴点ペアの数を２として、相似変換における変換係数を算出する。例えば、画像位置合わせ部２２は、特徴点ペア（ａ１−ｂ１）及び特徴点ペア（ａ２−ｂ２）を選択したとする。
【００８５】
図６（Ｂ）は、特徴点ペア（ａ１−ｂ１）及び特徴点ペア（ａ２−ｂ２）から算出された変換係数を用いて変換された画像Ａと、画像Ｂとを示す。画像位置合わせ部２２は、特徴点ａ３との距離が閾値Ｔｈ１以下である画像Ｂの特徴点としてｂ３を検出したとする。同様に、画像位置合わせ部２２は、特徴点ａ４との距離が閾値Ｔｈ１以下である画像Ｂの特徴点として、ｂ４を検出したとする。その結果、画像位置合わせ部２２は、有効特徴点ペア数が閾値Ｔｈ２以上であるので、特徴点ペア（ａ１−ｂ１）及び特徴点ペア（ａ２−ｂ２）は正しいと判定する。
【００８６】
さらに、画像位置合わせ部２２は、有効特徴点ペア（ａ１−ｂ１），（ａ２−ｂ２），（ａ３−ｂ３），（ａ４−ｂ４）を用いて、新たな変換係数（射影変換行列）を算出して、再度、画像Ａを変換する。画像位置合わせ部２２は、このような処理を、特徴点ペアのパターンが変化しなくなるまで繰り返し、図６（Ｄ）に示される様な変換を行う変換係数を求める。
【００８７】
図７は、本発明の第１の実施形態に係る画像位置合わせ部２２の機能構成を示す図である。
図７に示すように、画像位置合わせ部２２は、特徴点抽出部２２０、特徴点ペア選択部２２２、変換係数算出部２２４及び有効特徴点ペア探索部２２６を有する。
【００８８】
画像位置合わせ部２２において、特徴点抽出部２２０は、画像Ａ（第１の画像）及び画像Ｂ（第２の画像）を入力し、画像Ａ及び画像Ｂから特徴点を抽出し、抽出された特徴点の座標を特徴点ペア選択部２２２及び有効特徴点ペア探索部２２６に対して出力する。特徴点抽出部２２０は、例えば非特許文献３に開示されているＨａｒｒｉｓオペレータ等の画像コーナー点抽出アルゴリズムを用いて、特徴点を抽出する。なお、コーナー点は、２方向以上のエッジを有する点を意味する。また、コーナー点抽出アルゴリズムは、本例に限定されず、特徴点抽出部２２０は、その他様々なアルゴリズムを用いてもよい。
【００８９】
特徴点ペア選択部２２２は、特徴点抽出部２２０により抽出された画像Ａ及び画像Ｂの特徴点から１個ずつ特徴点を選択し、特徴点ペアを決定する。より具体的には、画像のＡの特徴点を、ａ１，ａ２，…，ａｉ，…とし、画像のＢの特徴点を、ｂ１，ｂ２，…，ｂｉ，…とすると、特徴点ペア選択部２２２は、特徴点ａ１，ａ２，…，ａｉ，…から１個の特徴点を選択し、特徴点ｂ１，ｂ２，…，ｂｉ，…から１個の特徴点を選択し、画像Ａの特徴点と画像Ｂの特徴点とが対になるようにして特徴点ペアを決定する。
【００９０】
変換係数算出部２２４は、特徴点ペア選択部２２２により決定された特徴点ペアを用いて変換係数を算出し、この変換係数を有効特徴点ペア探索部２２６に対して出力する。したがって、特徴点ペア選択部２２２及び変換係数算出部２２４は、画像の変換手法を決定する変換手法決定手段を構成する。なお、変換係数は、例えば、平行移動変換における変換係数である。
【００９１】
有効特徴点ペア探索部２２６は、変換係数算出部２２４により決定される変換手法を適用されて変換された画像Ａの特徴点と、画像Ｂの特徴点との距離が閾値以下となる特徴点の組に基づいて、特徴点ペア選択部２２２及び変換係数算出部２２４が変換手法の決定を繰り返し行うように制御する制御手段を構成する。
【００９２】
より具体的には、まず、有効特徴点ペア探索部２２６は、特徴点抽出部２２０により抽出された画像Ａの特徴点のうち、特徴点ペア選択部２２２により選択された特徴点以外の特徴点を、変換係数算出部２２４により算出された変換係数を含む変換式を用いて変換する。次に、有効特徴点ペア探索部２２６は、変換された画像Ａの特徴点と、画像Ｂの特徴点のうち特徴点ペア選択部２２２により選択された特徴点以外の特徴点との距離を算出する。ここで、有効特徴点ペア探索部２２６は、変換された画像Ａの特徴点に最も近い画像Ｂの特徴点を検出し、画像Ａの当該特徴点と画像Ｂの当該特徴点との例えばユークリッド距離を算出する。
【００９３】
有効特徴点ペア探索部２２６は、算出された距離が予め決められた閾値Ｔｈ１以下であるか否かを判定する。有効特徴点ペア探索部２２６は、算出された距離が閾値Ｔｈ１以下である場合、この特徴点ペアは有効特徴点ペアであると判定する。有効特徴点ペア探索部２２６は、特徴点ペア選択部２２２により選択された特徴点以外の特徴点の全てに対してこのような判定を行い、有効特徴点ペア数を算出する。なお、有効特徴点ペア探索部２２６は、変換された画像Ａの特徴点との距離が閾値Ｔｈ１以下である画像Ｂの特徴点を検出してもよい。
【００９４】
有効特徴点ペア探索部２２６は、有効特徴点ペア数が、予め決められた閾値Ｔｈ２（例えば、４以上の整数）以上となるように制御する。具体的には、有効特徴点ペア探索部２２６は、有効特徴点ペア数が閾値Ｔｈ２未満である場合、特徴点ペア選択部２２２及び変換係数算出部２２４が、当該特徴点ペアとは異なる特徴点ペアを選択するように制御する。この場合、特徴点ペア選択部２２２は、前回とは異なる特徴点ペアを選択する。
【００９５】
有効特徴点ペア探索部２２６は、有効特徴点ペア数が閾値Ｔｈ２以上である場合、再度、変換係数算出部２２４が変換係数を算出するように制御する。この場合、変換係数算出部２２４は、有効特徴点ペア探索部２２６により算出された距離が閾値Ｔｈ１以下である特徴点ペアを用いて、変換係数を算出し、この変換係数を有効特徴点ペア探索部２２６に対して、再度、出力する。例えば、変換係数算出部２２４は、有効特徴点ペア数が２である場合には相似変換における変換係数を算出し、有効特徴点ペア数が３である場合にはアフィン変換における変換係数を算出し、有効特徴点ペア数が４以上である場合には射影変換における変換係数を算出する。
【００９６】
有効特徴点ペア探索部２２６は、有効特徴点ペア数が収束するまで上記の制御を繰り返し、収束した状態における変換係数（変換手法に関する情報）を出力する。また、特徴点ペア選択部２２２は、全ての特徴点の組み合わせを選択したにもかからず有効特徴点ペア数が閾値Ｔｈ２未満である場合、画像Ａと画像Ｂとの間で重畳する画像部分がないとして、終了信号を出力する。
【００９７】
図８は、画像位置合わせ部２２による画像位置合わせ処理（Ｓ１０）のフローチャートを示す。
図８に示すように、ステップ１００（Ｓ１００）において、画像位置合わせ部２２の特徴点抽出部２２０は、画像Ａ及び画像Ｂから特徴点を抽出する。
ステップ１０２（Ｓ１０２）において、特徴点ペア選択部２２２は、抽出された特徴点から特徴点ペアを選択する。
【００９８】
ステップ１０４（Ｓ１０４）において、変換係数算出部２２４は、選択された特徴点ペアに基づいて変換係数を算出する。
ステップ１０６（Ｓ１０６）において、有効特徴点ペア探索部２２６は、変換係数を用いて、画像Ａの特徴点を変換する。
【００９９】
ステップ１０８（Ｓ１０８）において、有効特徴点ペア探索部２２６は、変換後の画像Ａの特徴点と、画像Ｂの特徴点との距離を算出する。
ステップ１１０（Ｓ１１０）において、有効特徴点ペア探索部２２６は、算出された距離が閾値Ｔｈ１以下である有効特徴点ペアの数を算出する。
【０１００】
ステップ１１２（Ｓ１１２）において、有効特徴点ペア探索部２２６は、有効特徴点ペア数が閾値Ｔｈ２以上であるか否かを判定する。有効特徴点ペア探索部２２６は、有効特徴点ペア数が閾値Ｔｈ２以上である場合にはＳ１１４の処理に進み、そうでない場合にはＳ１１８の処理に進む。
【０１０１】
ステップ１１４（Ｓ１１４）において、有効特徴点ペア探索部２２６は、算出された有効特徴点ペア数が収束しているか否かを判定する。例えば、有効特徴点ペア探索部２２６は、算出された有効特徴点ペア数が前回算出された値と同じか否かを判定する。有効特徴点ペア探索部２２６は、算出された有効特徴点ペア数が前回算出された値と同じである場合、有効特徴点ペア数が収束していると判定し、Ｓ１１６の処理に進み、そうでない場合にはＳ１０４の処理に戻って、再度、変換係数を算出する。
【０１０２】
ステップ１１６（Ｓ１１６）において、有効特徴点ペア探索部２２６は、変換係数を画像変換部２４に対して出力する。
【０１０３】
一方、ステップ１１８（Ｓ１１８）においては、特徴点ペア選択部２２２は、全ての特徴点の組み合わせについて終了したか否かを判定する。特徴点ペア選択部２２２は、全ての特徴点の組み合わせについて終了した場合には終了信号を出力して処理を終了し、そうでない場合にはＳ１００の処理に戻る。
【０１０４】
このように、ペア化される特徴点は、最初、狭い領域内に存在する一方、変換係数の算出が繰り返されるに従って、広い領域内に存在するようになる。したがって、ペア化される特徴点が存在する領域が次第に広がることにより、変換係数は、画像全体に渡って誤差のないものとなる。これにより、画像処理装置１０は、変換精度の良い変換行列を求めることができる。
【０１０５】
また、例えば、画像Ａの特徴点の数ｎＡ及び画像Ｂの特徴点の数ｎＢが１００であるとすると、特徴点ペアの数が１である場合、画像Ａ及び画像Ｂから特徴点を選択する組み合わせの数は、ｎＡｎＢより１０４であり、特徴点ペアの数が２である場合、前記組み合わせの数は、ｎＡ（ｎＡ−１）ｎＢ（ｎＢ−１）より１０８であり、特徴点ペアの数が３である場合、前記組み合わせの数は、ｎＡ（ｎＡ−１）（ｎＡ−２）ｎＢ（ｎＢ−１）（ｎＢ−２）より１０１２である。したがって、組み合わせ回数を大幅に削減することができる。これにより、計算量が削減されることができる。
【０１０６】
なお、画像位置合わせ部２２の特徴点ペア選択部２２２により最初に選択される特徴点ペアの数は、１、２及び３のいずれであってもよい。例えば、この特徴点ペアの数が３である場合、変換係数算出部２２４は、アフィン変換における変換係数を算出する。
【０１０７】
また、特徴点ペアの数が２である場合、有効特徴点ペア探索部２２６は、選択された特徴点ペアが拡縮変換を満たしているか否かを判定してもよい。例えば選択された特徴点ペアを（ａ１，ｂ１）及び（ａ２，ｂ２）であるとすると、有効特徴点ペア探索部２２６は、線分ａ１ａ２の傾きと、線分ｂ１ｂ２の傾きとが略等しい場合、選択された特徴点ペアは拡縮変換を満たしていると判定する。有効特徴点ペア探索部２２６は、選択された特徴点ペアが拡縮変換を満たしている場合には次の処理に移り、そうでない場合には、再度、特徴点ペアが選択されるように制御する。これにより、拡縮変換に限定される場合には、処理の高速化が可能となる。
【０１０８】
また、特徴点ペアの数が２である場合、有効特徴点ペア探索部２２６は、選択された特徴点ペアが剛体変換を満たしているか否かを判定してもよい。例えば選択された特徴点ペアを（ａ１，ｂ１）及び（ａ２，ｂ２）であるとすると、有効特徴点ペア探索部２２６は、線分ａ１ａ２の長さと、線分ｂ１ｂ２の長さとが略等しい場合、択された特徴点ペアは剛体変換を満たしていると判定する。有効特徴点ペア探索部２２６は、選択された特徴点ペアが剛体変換を満たしている場合には次の処理に移り、そうでない場合には、再度、特徴点ペアが選択されるように制御する。これにより、剛体変換に限定される場合には、処理の高速化が可能となる。
【０１０９】
図９は、本発明の第１の実施形態に係る画像処理装置１０の全体動作（Ｓ２０）を示すフローチャートである。
図９に示すように、画像処理装置１０が画像Ａ及び画像Ｂを受け付けると、画像処理プログラム２０の画像位置合わせ部２２は、画像位置合わせ処理（Ｓ１０）を実行し、画像Ａと画像Ｂとの間の変換係数を画像変換部２４に対して出力する。
【０１１０】
ステップ２００（Ｓ２００）において、画像変換部２４は、算出された変換係数を用いて、画像Ａを変換し、変換後の画像Ａを画像重ね合わせ部２６に対して出力する。
ステップ２０２（Ｓ２０２）において、画像重ね合わせ部２６は、変換後の画像Ａと、画像Ｂとを重ね合わせて合成画像を生成して出力する。
【０１１１】
図１０は、本発明の実施形態に係る画像処理装置１０により生成された合成画像を例示する図である。
図１０に例示するように、画像Ａが変換され、変換後の画像Ａと、画像Ｂとが組み合わされて、より大きなモザイク合成画像が生成される。
【０１１２】
図１１は、画像から抽出される特徴点数と試行回数との関係を示す図である。
図１１に示すように、例えば特徴点ペアの数が２である場合、本発明の実施形態に係る画像処理装置１０は、１０８回の試行回数で、探索することができる。したがって、画像処理装置１０は、従来手法における試行回数（１０１６）より、試行回数を削減することが出来る。このため、計算量が削減され、処理負荷が、低減されることができる。
【０１１３】
次に、本発明の第２の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、平行移動近似処理、拡縮変換近似処理、剛体変換近似処理、相似変換近似処理及びアフィン変換近似処理の少なくとも２以上の処理が、順次行われる点で、第１の実施形態に係る画像処理装置１０とは異なる。
【０１１４】
図１２は、本発明の第２の実施形態に係る画像位置合わせ部２８の機能構成を示す図である。なお、図１２に示された各構成のうち、図７に示された構成と実質的に同一のものには同一の符号が付されている。
図１２に示すように、画像位置合わせ部２８は、特徴点抽出部２２０、平行移動近似部２３０、拡縮変換近似部２８０、剛体変換近似部２８２、相似変換近似部２８４及びアフィン変換近似部２８６を有する。ここで、平行移動近似部２３０、拡縮変換近似部２８０、剛体変換近似部２８２、相似変換近似部２８４及びアフィン変換近似部２８６には、図７に示される特徴点ペア選択部２２２、変換係数算出部２２４及び有効特徴点ペア探索部２２６が含まれる。
【０１１５】
平行移動近似部２３０は、１組の特徴点ペアを選択し、平行移動における変換係数を算出する。拡縮変換近似部２８０は、平行移動近似部２３０から終了信号を受け付けた場合、２組の特徴点ペアを選択し、拡縮変換における変換係数を算出する。剛体変換近似部２８２は、拡縮変換近似部２８０から終了信号を受け付けた場合、２組の特徴点ペアを選択し、剛体変換における変換係数を算出する。相似変換近似部２８４は、剛体変換近似部２８２から終了信号を受け付けた場合、２組の特徴点ペアを選択し、相似変換における変換係数を算出する。アフィン変換近似部２８６は、相似変換近似部２８４から終了信号を受け付けた場合、３組の特徴点ペアを選択し、アフィン変換における変換係数を算出する。
【０１１６】
図１３は、本実施形態に係る画像処理装置１０における画像位置合わせ部２２による画像位置合わせ処理（Ｓ３０）のフローチャートを示す。
図１３に示すように、ステップ３００（Ｓ３００）において、画像位置合わせ部２２は、近似処理を平行移動近似処理とする。具体的には、画像位置合わせ部２２の特徴点抽出部２２０は、画像Ａ及び画像Ｂから特徴点を抽出して、平行移動近似部２３０に対して出力する。
【０１１７】
ステップ３０２（Ｓ３０２）において、平行移動近似部２３０は、位置合わせ処理を行う。具体的には、平行移動近似部２３０は、画像位置合わせ処理（Ｓ１０）と同様にして、変換係数を求める。
【０１１８】
ステップ３０４（Ｓ３０４）において、平行移動近似部２３０は、Ｓ３０２の処理で、変換係数が求まったか否かを判定する。平行移動近似部２３０は、変換係数が求まった場合にはＳ３０６の処理に進み、そうでない場合にはＳ３０８の処理に進む。
ステップ３０６（Ｓ３０６）において、平行移動近似部２３０は、変換係数を出力する。
【０１１９】
一方、ステップ３０８（Ｓ３０８）においては、平行移動近似部２３０は、終了信号を、拡縮変換近似部２８０に対して出力する。この場合、画像位置合わせ部２８は、平行移動近似部２３０による平行移動近似処理の次の処理として、拡散変換近似処理を選択する。具体的には、拡縮変換近似部２８０は、特徴点抽出部２２０により抽出された特徴点に関する情報を受け付け、Ｓ３０２の処理に戻る。
【０１２０】
以降、拡縮変換近似部２８０は、平行移動近似部２３０と同様に、Ｓ３０２及びＳ３０４の処理を行って、変換係数が求まった場合にはＳ３０６の処理で変換係数を出力する。変換係数が求まらなかった場合、剛体変換近似部２８２、相似変換近似部２８４及びアフィン変換近似部２８６が、順に、処理を行う。
【０１２１】
なお、画像位置合わせ部２８には、平行移動近似部２３０、拡縮変換近似部２８０、剛体変換近似部２８２、相似変換近似部２８４及びアフィン変換近似部２８６のうち、少なくとも２つの構成要素が含まれていればよい。また、画像位置合わせ部２８において、これらの構成要素の順序は、本例に限定されない。例えば、画像位置合わせ部２８には、平行移動近似部２３０及び拡縮変換近似部２８０がこの順序で配置されてもよいし、平行移動近似部２３０、相似変換近似部２８４及びアフィン変換近似部２８６がこの順序で配置されてもよい。
【０１２２】
次に、本発明の第３の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、変換後の画像Ａの特徴点の周辺画素の画素値と、画像Ｂの特徴点の周辺画素の画素値とにさらに基づいて、画像の変換手法を決定する点で、第１の実施形態に係る画像処理装置１０とは異なる。
【０１２３】
本実施形態では、画像位置合わせ部２２の変換係数算出部２２４は、算出した変換係数を用いて、画像Ａの特徴点ｐｉの周辺画素を変換し、変換された画像Ａの特徴点ｐｉの周辺画素の画素値と、画像Ｂの特徴点ｑｊの周辺画素の画素値とに基づいて、特徴点ペア（ｐｉ，ｑｊ）が有効特徴点ペアであるか否かを判定する。例えば、変換係数算出部２２４は、これらの画素値の正規化相関、２乗誤差又は絶対誤差を用いて判定する。変換係数算出部２２４は、例えば、２乗誤差等が所定値以下である場合、特徴点ペアが有効特徴点ペアであると判定する。
【０１２４】
変換係数算出部２２４は、選択された特徴点ペアが有効特徴点ペアであると判定した場合、変換係数を有効特徴点ペア探索部２２６に対して出力し、そうでない場合、特徴点ペア選択部２２２が特徴点ペアを再び選択するように制御する。
【０１２５】
なお、画像位置合わせ部２２において、有効特徴点ペア探索部２２６が、変換後の画像Ａの特徴点の周辺画素の画素値と、画像Ｂの特徴点の周辺画素の画素値とにさらに基づいて、画像の変換手法の決定を繰り返し行うように制御してもよい。例えば、有効特徴点ペア探索部２２６は、変換された特徴点ｐｉと特徴点ｑｊとの距離が予め決められた閾値Ｔｈ１以下であり、かつ、変換された特徴点ｐｉの周辺画素の画素値と特徴点ｑｊの周辺画素の画素値とが類似する場合、この特徴点ペアは有効特徴点ペアであると判定する。
【０１２６】
次に、本発明の第４の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、適切な試行回数を設定することにより計算量を削減する点で、第１の実施形態〜第３の実施形態に係る画像処理装置１０とは異なる。
【０１２７】
図１４は、本発明の実施形態に係る画像処理装置１０により実行される画像処理プログラム３０の機能構成を示す図である。
図１４に示すように、画像処理プログラム３０は、画像処理プログラム２０（図４）に有効特徴点割合出力部３２が追加され、さらに、画像位置合わせ部２２が画像位置合わせ部４０に置換された構成を有する。なお、図１４に示された各構成のうち、図４に示された構成と実質的に同一のものには同一の符号が付されている。
【０１２８】
画像処理プログラム３０において、画像位置合わせ部４０は、画像Ａ及び画像Ｂを入力し、ＲＡＮＳＡＣアルゴリズムを用いて画像Ａ及び画像Ｂの間の変換係数を算出して画像変換部２４に対して出力する。なお、画像位置合わせ部４０については、後で詳述する。
【０１２９】
有効特徴点割合出力部３２は、後述する有効特徴点割合αを、画像位置合わせ部４０に対して出力する。また、有効特徴点割合出力部３２は、試行回数に応じて、有効特徴点割合αを変化させる。なお、有効特徴点割合αについては、後で詳述する。
【０１３０】
次に、画像位置合わせ部４０について、より詳細に説明する。
図１５は、本発明の第４の実施形態に係る画像位置合わせ部４０の機能構成を示す図である。
図１５に示すように、画像位置合わせ部４０は、条件決定部４００、特徴点抽出部４０２、特徴点ペア選択部４０４、変換係数算出部４０６、距離算出部４０８及び判定部４１０を有し、条件決定部４００は、特徴点数算出部４１２及び試行回数算出部４１４を有する。
【０１３１】
画像位置合わせ部４０は、これらの構成要素により、画像Ａ及び画像Ｂから抽出される特徴点の数及び試行回数の上限を算出し、画像Ａ及び画像Ｂから当該数の特徴点を選択し、選択された特徴点をペア化し、当該試行回数の上限を超えない範囲で、有効特徴点ペア数が閾値を超えるように試行を繰り返し、有効特徴点ペア数が閾値を超える変換における変換係数を出力する。
【０１３２】
画像位置合わせ部４０において、条件決定部４００は、特徴点に関する閾値及び割合（即ち、ＲＡＮＳＡＣの閾値ＫＲ及び有効特徴点割合出力部３２から出力される有効特徴点割合α）を入力し、特徴点数及び試行回数を決定する。条件決定部４００は、決定された特徴点数を特徴点抽出部４０２に対して出力し、試行回数を判定部４１０に対して出力する。
【０１３３】
条件決定部４００において、特徴点数算出部４１２は、ＲＡＮＳＡＣの閾値ＫＲ及び有効特徴点割合αに基づいて、画像Ａ及び画像Ｂから抽出される特徴点数を算出する。また、試行回数算出部４１４は、特徴点数算出部４１２により算出された特徴点数に基づいて試行回数の上限を算出する。なお、特徴点数算出部４１２による特徴点数算出処理及び試行回数算出部４１４による試行回数算出処理については、後で詳述する。
【０１３４】
特徴点抽出部４０２は、画像Ａ、画像Ｂ及び条件決定部４００から出力される特徴点数を入力し、画像Ａ及び画像Ｂから当該特徴点数の特徴点を抽出し、抽出された特徴点の座標を特徴点ペア選択部４０４及び距離算出部４０８に対して出力する。
【０１３５】
特徴点ペア選択部４０４は、特徴点抽出部４０２により抽出された画像Ａ及び画像Ｂの特徴点からＮ個の特徴点を選択し、Ｎ組の特徴点ペアを決定する。より具体的には、画像のＡの特徴点を、ａ１，ａ２，…，ａｉ，…とし、画像のＢの特徴点を、ｂ１，ｂ２，…，ｂｉ，…とすると、特徴点ペア選択部４０４は、特徴点ａ１，ａ２，…，ａｉ，…からＮ個の特徴点を選択し、特徴点ｂ１，ｂ２，…，ｂｉ，…からＮ個の特徴点を選択し、画像Ａの特徴点と画像Ｂの特徴点とが対になるようにしてＮ個の特徴点ペアを決定する。
【０１３６】
変換係数算出部４０６は、特徴点ペア選択部４０４により決定された特徴点ペアを用いて変換係数を算出し、この変換係数を距離算出部４０８に対して出力する。
【０１３７】
距離算出部４０８は、特徴点抽出部４０２により抽出された画像Ａの特徴点のうち、特徴点ペア選択部４０４により選択された特徴点以外の特徴点を、変換係数算出部４０６により算出された変換係数を含む変換式を用いて変換する。次に、距離算出部４０８は、変換された画像Ａの特徴点と、画像Ｂの特徴点のうち特徴点ペア選択部４０４により選択された特徴点以外の特徴点との距離を算出する。より具体的には、距離算出部４０８は、変換された画像Ａの特徴点に最も近い画像Ｂの特徴点を検出し、画像Ａの当該特徴点と画像Ｂの当該特徴点との例えばユークリッド距離を算出する。
【０１３８】
さらに、距離算出部４０８は、算出された距離が予め決められた閾値Ｔ０以下であるか否かを判定する。距離算出部４０８は、算出された距離が閾値Ｔ０以下である場合、この特徴点ペアは有効特徴点ペアであると判定する。距離算出部４０８は、特徴点ペア選択部４０４により選択された特徴点以外の特徴点の全てに対してこのような判定を行い、有効特徴点ペアの数を算出する。以降、算出された数を、有効特徴点数Ｋとする。
【０１３９】
判定部４１０は、距離算出部４０８により算出された有効特徴点数Ｋが、入力されたＲＡＮＳＡＣの閾値ＫＲ以上であるか否かを判定する。有効特徴点数Ｋが閾値ＫＲ以上である場合、判定部４１０は、この有効特徴点数Ｋが算出される際の変換において用いられた変換係数を、画像変換部２４に対して出力する。有効特徴点数Ｋが閾値ＫＲ未満である場合、判定部４１０は、特徴点ペア選択部４０４に対して、特徴点の選択及び特徴点ペアの決定を再度行う旨の出力を行う。この場合、再度、特徴点ペアが決定され、変換係数が算出され、有効特徴点数Ｋが算出され、判定処理が行われる。
【０１４０】
また、判定部４１０は、試行回数算出部４１４により算出された試行回数の上限を超えない範囲で、変換手法を決定するための試行を繰り返す。即ち、特徴点ペアの選択処理から判定処理までが繰り返し実行され、特徴点ペアの選択回数が、算出された試行回数を超えた場合、判定部４１０は、処理を終了する。なお、特徴点ペアの選択回数が、算出された試行回数を超えた場合の詳細については、後で詳述する。
【０１４１】
このように、画像位置合わせ部４０において、特徴点ペア選択部４０４、変換係数算出部４０６、距離算出部４０８及び判定部４１０は、画像Ａ及び画像Ｂ抽出された特徴点から選択される特徴点ペアのうち有効とされる組の数が特徴点に関する閾値（ＲＡＮＳＡＣの閾値）以上となるように画像の変換手法を決定する変換手法決定手段を構成する。
【０１４２】
なお、特徴点間の距離は、ユークリッド距離に限定されず、他の距離であってもよい。例えば、距離は、マンハッタン距離、その他のノルムＬ１，Ｌ２，Ｌ３，Ｌ４，…，Ｌ∞ノルム等であってもよい。また、距離算出部４０８は、画像Ａの特徴点の周囲の画素を変換し、変換後の画素値と、この変換後の画素と同じ位置の画像Ｂの画素値との相関係数を算出し、この相関係数を予め決められた閾値と比較してもよい。また、距離算出部４０８は、画像Ａの特徴点の周囲の画素を変換し、変換後の画素値と、この変換後の画素と同じ位置の画像Ｂの画素値との差分の２乗を算出し、この算出された値と予め決められた閾値とを比較してもよい。
【０１４３】
次に、画像位置合わせ部４０の特徴点数算出部４１２による特徴点数算出処理及び試行回数算出部４１４による試行回数算出処理を、より詳細に説明する。
ここで、画像Ａ及び画像Ｂ内の特徴点数をｎ、有効特徴点の数をｎｘ、特徴点のうち有効特徴点の割合をα（＝ｎｘ／ｎ）、特徴点ペア数をＮ、正しい特徴点ペアを選択する確率をｗ、Ｔ回の試行以下で正解に辿り着く確率をＺとする。
【０１４４】
試行回数算出部４１４は、画像Ａの特徴点数と画像Ｂの特徴点数とが一致する場合、次式を用いて、試行回数を算出する。
【０１４５】
【数１９】
【０１４６】
また、試行回数算出部４１４は、画像Ａの特徴点数と画像Ｂの特徴点数が異なる場合、次式を用いて、試行回数を算出する。
【０１４７】
【数２０】
【０１４８】
試行回数の算出には、特徴点数ｎを設定する必要がある。したがって、特徴点数算出部４１２は、次式を用いて、特徴点数を算出する。
【０１４９】
【数２１】
【０１５０】
以下、試行回数及び特徴点数を算出する式の導出方法を説明する。
画像Ａの特徴点数と画像Ｂの特徴点数が一致する場合、画像Ａのｎ個の特徴点からＮ個の特徴点を選択する組み合わせは、重複も許すと、ｎＮ通りであり、画像Ｂのｎ個の特徴点からＮ個の特徴点を選択する組み合わせも、同様に、ｎＮ通りである。したがって、画像Ａ及び画像ＢのそれぞれからＮ個の特徴点を選択する組み合わせは、ｎ２Ｎ通りである。この中で、正しい特徴点ペアとなる組み合わせは、ｎｘ（ｎｘ−１）…（ｎｘ−（Ｎ−１））通りである。この値を、ｎｘＮで近似すると、正しい特徴点ペアを選択する確率ｗは、次式で表される。
【０１５１】
【数２２】
【０１５２】
また、「Ｔ回の試行で正解に辿り着かない確率」は、１−Ｚであるので、１−Ｚ＝（１−Ｗ）Ｔが、成り立つ。よって、（１９）式が求められる。なお、正しい特徴点ペアとなる組み合わせは、ｎｘＮで近似されたが、近似されなくてもよい。また、画像ＡからＮ個の特徴点を選択する組み合わせは、重複を許して選択される場合を示したが、重複を許さないように選択されてもよい。
【０１５３】
画像Ａの特徴点数と画像Ｂの特徴点数が異なる場合、まず、試行回数算出部４１４は、特徴点数は等しいものとして、又は特徴点数密度は等しいものとして、一方の特徴点数から、他方の特徴点数を換算する。例えば、試行回数算出部４１４は、画像のＡの特徴点数ｎＡを求めてから、画像Ｂの特徴点数ｎＢを求める。より具体的には、画像Ａ及び画像Ｂの面積をそれぞれＳＡ，ＳＢとすると、特徴点数が等しいと換算される場合、試行回数算出部４１４は、ｎＢ＝ｎＡより、ｎＢを求める。また、特徴点密度が等しいと換算される場合、試行回数算出部４１４は、ｎＢ＝（ＳＢ／ＳＡ）ｎＡより、ｎＢを求める。
【０１５４】
さらに、画像Ａ内の有効特徴点割合をαＡ（＝ｎｘ／ｎＡ）、画像Ｂ内の有効特徴点割合をαＢ（＝ｎｘ／ｎＢ）とすると、画像Ａ及び画像Ｂの特徴点からＮ個の特徴点を選択する組み合わせは、（ｎＡｎＢ）Ｎ通りである。この中で、正しい特徴点ペアとなる組み合わせを、ｎｘＮとすると、確率ｗは、次式で表される。
【０１５５】
【数２３】
【０１５６】
よって、（２０）式が求められる。
【０１５７】
次に、特徴点数ｎの算出式について、詳述する。処理負荷は、特徴点数ｎが小さいほど小さい。一方、特徴点数ｎが小さすぎると、有効特徴点数Ｋが、ＲＡＮＳＡＣの閾値ＫＲより少なくなってしまう。したがって、有効特徴点数Ｋが閾値ＫＲとなるような特徴点数ｎが設定されればよい。
【０１５８】
即ち、特徴点数ｎの条件として、α×ｎが、ＲＡＮＳＡＣの閾値ＫＲより大きいことが挙げられる。よって、ｎの最小値は、ｎ＝ＫＲ／αである。マージンを考慮すると、特徴点数ｎは、ＫＲ／αにマージンが加えられた値として求められる。マージンは、次のように算出される。
【０１５９】
例えば、１つのコインを投げ、表が出る確率をα、裏が出る確率を１−αとすると、コインをｎ回投げた場合、表が出る回数Ｋ（ｎ）は、次の分布（二項分布）を持つ。
【０１６０】
【数２４】
【０１６１】
ここで、Ｋ（ｎ）≧ＫＲとなる確率Ｐは、次式で与えられる。
【０１６２】
【数２５】
【０１６３】
特徴点数ｎは、確率Ｐが所定値以上となるように設定されればよい。ここでは、分布Ｋ（ｎ）を、正規分布で近似する。即ち、二項分布Ｋ（ｎ）は、正規分布Ｎ（ｎα，ｎα（１−α））で近似される。したがって、特徴点数ｎは、中心μ、標準偏差σの正規分布を持つ確率変数が、ある確率で、ＫＲよりも大となるように設定される。ここで、マージンを、ｕσ（ｕは、正の実数）とすると、次式が成り立つ。
【０１６４】
【数２６】
【０１６５】
この式を解くと、（２１）式が求められる。なお、正規分布の±３σ内には、９９．７４％が含まれるので、例えばｕ＝３として、特徴点数ｎは求められる。
【０１６６】
また、画像Ａ及び画像Ｂのサイズが異なっており、かつ、特徴点密度が一定である場合、画像Ａ及び画像Ｂそれぞれの特徴点数ｎＡ及びｎＢは、次式で与えられる。
【０１６７】
【数２７】
【０１６８】
【数２８】
【０１６９】
図１６は、有効特徴点割合αと、ｕと、特徴点数ｎとの関係を示す図である。なお、図１６において、ＫＲは、６である。
図１６に示すように、特徴点数ｎは、αの大きさによって変化する。より具体的には、特徴点数ｎは、αが小さい場合には大きい値を設定され、αが大きい場合には小さい値を設定される。このように、特徴点数ｎには、有効特徴点割合αの値に応じて、適切な値が設定される。
【０１７０】
次に、上記のような画像処理プログラム３０の画像位置合わせ部４０による位置合わせ処理を説明する。なお、画像Ａ及び画像Ｂの特徴点数は一致する場合を例として示す。
図１７は、画像位置合わせ部４０による画像位置合わせ処理（Ｓ４０）のフローチャートを示す図である。
【０１７１】
図１７に示すように、ステップ４００（Ｓ４００）において、条件決定部４００は、入力されるＲＡＮＳＡＣの閾値ＫＲ及び有効特徴点割合αを受け付ける。条件決定部４００が閾値ＫＲ及び有効特徴点割合αを受け付けると、特徴点数算出部４１２は、閾値ＫＲ及び有効特徴点割合αに基づいて、画像Ａ及び画像Ｂの特徴点数ｎを算出する。
ステップ４０２（Ｓ４０２）において、試行回数算出部４１４は、有効特徴点割合α及び算出された特徴点数ｎに基づいて、試行回数Ｔを算出する。
【０１７２】
ステップ４０４（Ｓ４０４）において、特徴点抽出部４０２は、画像Ａ及び画像Ｂから、算出された特徴点数の特徴点を抽出する。
ステップ４０６（Ｓ４０６）において、特徴点ペア選択部４０４は、画像Ａ及び画像Ｂから抽出された特徴点からそれぞれＮ個の特徴点を選択し、Ｎ組の特徴点ペアを決定する。なお、Ｎの値は、特に限定されない。
【０１７３】
ステップ４０８（Ｓ４０８）において、変換係数算出部４０６は、決定された特徴点ペアを用いて変換係数を算出する。
ステップ４１０（Ｓ４１０）において、距離算出部４０８は、算出された変換式を用いて、画像のＡの所定の特徴点を変換する。
【０１７４】
ステップ４１２（Ｓ４１２）において、距離算出部４０８は、画像Ｂの特徴点と、変換後の画像Ａの特徴点との距離を算出し、この変換における有効特徴点数Ｋを算出する。
ステップ４１４（Ｓ４１４）において、判定部４１０は、算出された有効特徴点数Ｋが入力された閾値ＫＲ以上であるか否かを判定する。有効特徴点数Ｋが閾値ＫＲ以上である場合、判定部４１０は、変換係数を出力し、画像位置合わせ処理は終了する。
【０１７５】
有効特徴点Ｋが閾値ＫＲ未満である場合、ステップ４１６（Ｓ４１６）において、判定部４１０は、特徴点ペアの算出から有効特徴点数Ｋの判定までの試行が、算出された試行回数Ｔ回実施されたか否かを判定する。この試行がＴ回実施された場合、画像位置合わせ部４０は、処理を終了し、この試行がまだＴ回実施されていない場合、画像位置合わせ部４０は、Ｓ４０４の処理に戻る。
【０１７６】
試行回数がＴ回を超えて、画像位置合わせ処理が終了した場合、有効特徴点割合αの値が有効特徴点割合出力部３２により変更され、再度、画像位置合わせ処理（Ｓ４０）が実行される。この場合、新たな有効特徴点割合αに基づいて、特徴点数ｎ及び試行回数Ｔが、再度、算出される。
【０１７７】
図１８は、有効特徴点割合αと試行回数Ｔとの関係を示す図である。
図１８に示すように、本発明の実施形態に係る画像処理装置１０は、有効特徴点割合αに応じて、適切な試行回数Ｔを設定することができる。なお、図１８に示される結果及び非特許文献１に開示された手法における試行回数は、特徴点数ｎ＝１００、Ｎ＝２の条件で算出されたものである。
【０１７８】
図１９は、画像位置合わせ処理の実行回数と有効特徴点割合αとの関係を示す図である。
図１９に示すように、有効特徴点割合αは、実行回数が増えるごとに、小さくなる。図１９に示されるテーブルは、予め決められており、例えば、メモリ１０４及び記憶装置１０８の少なくともいずれかに記憶されている。有効特徴点割合出力部３２は、このテーブルに基づいて、有効特徴点割合αを、画像位置合わせ部４０に出力する。
【０１７９】
したがって、試行回数がＴ回を超えた場合、画像位置合わせ部４０の特徴点数算出部４１２及び試行回数算出部４１４は、減少された有効特徴点割合αを用いて算出を行う。予め決められた実行回数の上限（本例では、９回）が実行されたにもかかわらず、変換係数が求められなかった場合、画像位置合わせ部４０の判定部４１０は、画像Ａと画像Ｂとの間で重畳する画像部分がない旨の情報を出力する。なお、各実行回数における有効特徴点割合αの値及び上限回数は、本例に限定されない。
【０１８０】
図２０は、本発明の第４の実施形態に係る実施形態に係る画像処理装置１０の全体動作（Ｓ５０）を示すフローチャートである。なお、図２０に示された各処理のうち、図９に示された処理と実質的に同一のものには同一の符号が付されている。
図２０に示すように、画像処理装置１０が画像Ａ及び画像Ｂを受け付けると、ステップ５００（Ｓ５００）において、画像処理プログラム３０の有効特徴点割合出力部３２は、図１８に示されるテーブルに基づいて有効特徴点割合αの値を決定し、画像位置合わせ部４０に対して出力する。例えば、α＝０．５である。
【０１８１】
画像位置合わせ部４０は、有効特徴点割合αを受け付けると、画像位置合わせ処理（Ｓ４０）を実行する。
ステップ５０２（Ｓ５０２）において、画像位置合わせ部４０は、試行回数がＴ回を超えて画像位置合わせ処理を終了したか否かを判定する。画像位置合わせ部４０は、試行回数がＴ回を超えて画像位置合わせ処理を終了した場合にはＳ５０４の処理に進み、そうでない場合には、画像Ａと画像Ｂとの間の変換係数を、画像変換部２４に対して出力し、Ｓ２００の処理に進む。
【０１８２】
ステップ５０４（Ｓ５０４）において、有効特徴点割合出力部３２は、テーブルに基づいて、有効特徴点割合αの値を減少し、像位置合わせ部４０に対して出力する。画像位置合わせ部４０は、有効特徴点割合αを受け付けると、この有効特徴点割合αを用いて、画像位置合わせ処理（Ｓ４０）を、再度、実行する。
【０１８３】
Ｓ２００の処理では、画像変換部２４が、算出された変換係数を用いて画像Ａを変換し、Ｓ２０２の処理では、画像重ね合わせ部２６が、変換後の画像Ａと、画像Ｂとを重ね合わせて合成画像を生成して出力する。
【０１８４】
次に、本発明の第５の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、画像Ａの特徴点と画像Ｂの特徴点とをペア化して特徴点ペアを抽出し、抽出された特徴点ペアからＮ個の特徴点ペアを選択する点で、第４の実施形態に係る画像処理装置１０とは異なる。
【０１８５】
図２１は、本発明の第５の実施形態に係る画像位置合わせ部４２の機能構成を示す図である。なお、図２１に示された各構成のうち、図１５に示された構成と実質的に同一のものには同一の符号が付されている。
図２１に示すように、本実施形態に係る画像処理装置１０は、画像位置合わせ部４０が画像位置合わせ部４２に置き換えられた構成を有し、画像位置合わせ部４２は、条件決定部４００、特徴点抽出部４０２及び特徴点ペア選択部４０４が、それぞれ条件決定部４２０、特徴点ペア抽出部４２２及び特徴点ペア選択部４２４に置き換えられた構成を有する。また、条件決定部４２０は、特徴点ペア数算出部４２６及び試行回数算出部４２８を有する。
【０１８６】
画像位置合わせ部４２において、条件決定部４２０は、特徴点に関する閾値及び割合、即ちＲＡＮＳＡＣの閾値ＫＲ及び有効特徴点ペア割合βを入力し、画像Ａ及び画像Ｂから抽出される特徴点ペア数及び試行回数を決定する。
【０１８７】
条件決定部４２０において、特徴点ペア数算出部４２６は、特徴点ペア数を算出する。より具体的には、特徴点ペア数算出部４２６は、（２１）式を用いて、特徴点ペア数を算出する。なお、特徴点ペア数算出部４２６は、（２１）式に含まれるαを有効特徴点ペア割合βに置き換えて（２１）式を用いる。また、有効特徴点ペア割合βは、αと同様に、図１９に示されるように記憶されており、実行回数に応じて変化される。
【０１８８】
試行回数算出部４２８は、試行回数を算出する。より具体的には、試行回数算出部４２８は、次式を用いて、試行回数を算出する。
【０１８９】
【数２９】
【０１９０】
特徴点ペア抽出部４２２は、画像Ａ、画像Ｂ及び条件決定部４２０から出力される特徴点ペア数を入力し、画像Ａ及び画像Ｂから当該特徴点ペア数の特徴点ペアを抽出する。より具体的には、特徴点ペア抽出部４２２は、画像Ａ及び画像Ｂから特徴点を抽出し、画像Ａの特徴点の周辺領域の画素と、画像Ｂの特徴点の周辺領域の画素とを比較し、周辺領域の画素が互いに似ている特徴点を選択し、特徴点ペアとして抽出する。
【０１９１】
特徴点ペア選択部４２４は、特徴点ペア抽出部４２２により抽出された特徴点ペアからＮ個の特徴点ペアを選択する。
【０１９２】
図２２は、画像位置合わせ部４２による画像位置合わせ処理（Ｓ６０）のフローチャートを示す図である。なお、図２２に示された各処理のうち、図１７に示された処理と実質的に同一のものには同一の符号が付されている。また、画像位置合わせ部４２においては、画像位置合わせ部４０における有効特徴点数Ｋは、有効特徴点ペア数Ｋとして扱われる。
【０１９３】
図２２に示すように、ステップ６００（Ｓ６００）において、条件決定部４２０は、入力されるＲＡＮＳＡＣの閾値ＫＲ及び有効特徴点ペア割合βを受け付ける。条件決定部４２０が閾値ＫＲ及び有効特徴点ペア割合βを受け付けると、特徴点ペア数算出部４２６は、閾値ＫＲ及び有効特徴点ペア割合βに基づいて特徴点ペア数ｎを算出する。
ステップ６０２（Ｓ６０２）において、試行回数算出部４２８は、有効特徴点ペア割合βに基づいて試行回数Ｔを算出する。
【０１９４】
ステップ６０４（Ｓ６０４）において、特徴点ペア抽出部４２２は、画像Ａ及び画像Ｂから、算出された特徴点ペア数の特徴点ペアを抽出する。
ステップ６０６（Ｓ６０６）において、特徴点ペア選択部４２４は、抽出された特徴点ペアからＮ個の特徴点ペアを選択する。
さらに、Ｓ４０８〜Ｓ４１６の処理で、有効特徴点ペア数Ｋが算出及び判定され、変換係数が決定される。
【０１９５】
次に、本発明の第６の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、算出されたＴ回の試行を繰り返し、有効特徴点数Ｋを最大とする変換における変換係数を用いる点で、第４の実施形態に係る画像処理装置１０とは異なる。
【０１９６】
図２３は、本発明の第６の実施形態に係る画像位置合わせ部４４の機能構成を示す図である。なお、図２３に示された各構成のうち、図１５に示された構成と実質的に同一のものには同一の符号が付されている。
図２３に示すように、本実施形態に係る画像処理装置１０は、画像位置合わせ部４０が画像位置合わせ部４４に置き換えられた構成を有し、画像位置合わせ部４４は、判定部４１０が試行回数判定部４４２及び有効特徴点数判定部４４４に置き換えられた構成を有する。
【０１９７】
画像位置合わせ部４４において、試行回数判定部４４２は、特徴点ペアの選択回数が、試行回数算出部４１４により算出された試行回数Ｔを超えたか否かを判定し、特徴点ペアの選択回数が試行回数Ｔを超えた場合、その旨を有効特徴点数判定部４４４に対して出力し、そうでない場合、特徴点ペアの選択を再度実行する旨を特徴点ペア選択部４０４に対して出力する。
【０１９８】
有効特徴点数判定部４４４は、Ｔ回の試行における有効特徴点数Ｋを判定する。より具体的には、有効特徴点数判定部４４４は、Ｔ回の試行のうち、有効特徴点数Ｋを最大とする変換において用いられた変換係数を、画像変換部２４に対して出力する。
【０１９９】
図２４は、画像位置合わせ部４４による画像位置合わせ処理（Ｓ７０）のフローチャートを示す図である。なお、図２４に示された各処理のうち、図１７に示された処理と実質的に同一のものには同一の符号が付されている。
【０２００】
図２４に示すように、Ｓ４００〜Ｓ４１２の処理で、有効特徴点数Ｋが算出される。
ステップ７００（Ｓ７００）において、試行回数判定部４４２は、特徴点の選択が、試行回数算出部４１４により算出された試行回数Ｔを超えたか否かを判定する。特徴点の選択が試行回数Ｔを超えた場合、画像位置合わせ部４４はＳ７００の処理に進み、そうでない場合、画像位置合わせ部４４は、Ｓ４０４の処理に戻る。
【０２０１】
ステップ７０２（Ｓ７０２）において、試行回数判定部４４２は、特徴点の選択が試行回数Ｔを超えた旨を、有効特徴点数判定部４４４に対して出力する。有効特徴点数判定部４４４は、Ｔ回の試行のうち、有効特徴点数Ｋを最大とする変換において用いられた変換係数を出力する。
【０２０２】
次に、本発明の第７の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、算出されたＴ回の試行を繰り返し、有効特徴点ペア数Ｋを最大とする変換における変換係数を用いる点で、第５の実施形態に係る画像処理装置１０とは異なる。
【０２０３】
図２５は、本発明の第７の実施形態に係る画像位置合わせ部４６の機能構成を示す図である。なお、図２５に示された各構成のうち、図２１又は図２３に示された構成と実質的に同一のものには同一の符号が付されている。
図２５に示すように、本実施形態に係る画像処理装置１０は、画像位置合わせ部４２が画像位置合わせ部４６に置き換えられた構成を有し、画像位置合わせ部４６は、判定部４１０が試行回数判定部４４２及び有効特徴点数判定部４４４に置き換えられた構成を有する。
【０２０４】
図２６は、画像位置合わせ部４６による画像位置合わせ処理（Ｓ８０）のフローチャートを示す図である。なお、図２６に示された各処理のうち、図１７、図２２又は図２４に示された処理と実質的に同一のものには同一の符号が付されている。
【０２０５】
図２６に示すように、Ｓ６００〜Ｓ４１２の処理で、有効特徴点ペア数Ｋが算出される。さらに、Ｓ７００の処理で、特徴点の選択が試行回数Ｔを超えたか否かが判定される。特徴点の選択が試行回数Ｔを超えた場合、ステップ８００（Ｓ８００）において、有効特徴点数判定部４４４は、Ｔ回の試行のうち、有効特徴点ペア数Ｋを最大とする変換において用いられた変換係数を出力する。
【図面の簡単な説明】
【０２０６】
【図１】射影変換を説明する図である。
【図２】２枚の画像が入力された場合、この２枚の画像を重ね合わせるための射影変換係数を求める手法を例示する図である。
【図３】本発明の実施形態に係る画像処理装置１０のハードウェア構成を示す図である。
【図４】本発明の第１の実施形態に係る画像処理装置１０により実行される画像処理プログラム２０の機能構成を示す図である。
【図５】画像位置合わせ部２２による画像位置合わせ処理の概要を説明する図である。
【図６】変換行列Ｈが平行移動では近似できない場合における画像位置合わせ部２２による画像位置合わせ処理の概要を説明する図である。
【図７】、本発明の第１の実施形態に係る画像処理装置１０における画像位置合わせ部２２の機能構成を示す図である。
【図８】本発明の第１の実施形態に係る画像処理装置１０における画像位置合わせ部２２による画像位置合わせ処理（Ｓ１０）のフローチャートを示す。
【図９】本発明の第１の実施形態に係る画像処理装置１０の全体動作（Ｓ２０）を示すフローチャートである。
【図１０】本発明の実施形態に係る画像処理装置１０により生成された合成画像を例示する図である。
【図１１】画像から抽出される特徴点数と試行回数との関係を示す図である。
【図１２】本発明の第２の実施形態に係る画像処理装置１０における画像位置合わせ部２８の機能構成を示す図である。
【図１３】本発明の第２の実施形態に係る画像処理装置１０における画像位置合わせ部２２による画像位置合わせ処理（Ｓ３０）のフローチャートを示す。
【図１４】本発明の第４の実施形態に係る画像処理装置１０により実行される画像処理プログラム３０の機能構成を示す図である。
【図１５】本発明の第４の実施形態に係る画像処理装置１０における画像位置合わせ部４０の機能構成を示す図である。
【図１６】有効特徴点割合αと、ｕと、特徴点数ｎとの関係を示す図である。
【図１７】本発明の第４の実施形態に係る画像処理装置１０における画像位置合わせ部４０による画像位置合わせ処理（Ｓ４０）のフローチャートを示す図である。
【図１８】有効特徴点割合αと試行回数Ｔとの関係を示す図である。
【図１９】画像位置合わせ処理の実行回数と有効特徴点割合αとの関係を示す図である。
【図２０】本発明の第４の実施形態に係る画像処理装置１０の全体動作（Ｓ５０）を示すフローチャートである。
【図２１】本発明の第５の実施形態に係る画像処理装置１０における画像位置合わせ部４２の機能構成を示す図である。
【図２２】本発明の第５の実施形態に係る画像処理装置１０における画像位置合わせ部４２による画像位置合わせ処理（Ｓ６０）のフローチャートを示す図である。
【図２３】本発明の第６の実施形態に係る画像処理装置１０における画像位置合わせ部４４の機能構成を示す図である。
【図２４】本発明の第６の実施形態に係る画像処理装置１０における画像位置合わせ部４４による画像位置合わせ処理（Ｓ７０）のフローチャートを示す図である。
【図２５】本発明の第７の実施形態に係る画像処理装置１０における画像位置合わせ部４６の機能構成を示す図である。
【図２６】本発明の第７の実施形態に係る画像処理装置１０における画像位置合わせ部４６による画像位置合わせ処理（Ｓ８０）のフローチャートを示す図である。
【符号の説明】
【０２０７】
１０ 画像処理装置
２０，３０ 画像処理プログラム
２２，４０，４２，４４，４６ 画像位置合わせ部
２４ 画像変換部
２６ 画像重ね合わせ部
３２ 有効特徴点割合出力部
１００ 制御装置
１０２ ＣＰＵ
１０４ メモリ
１０６ 通信装置
１０８ 記憶装置
１１０ ＵＩ装置
２２０ 特徴点抽出部
２２２ 特徴点ペア選択部
２２４ 変換係数算出部
２２６ 有効特徴点ペア探索部
２３０ 平行移動近似部
２８０ 拡縮変換近似部
２８２ 剛体変換近似部
２８４ 相似変換近似部
２８６ アフィン変換近似部
４００ 条件決定部
４０２ 特徴点抽出部
４０４ 特徴点ペア選択部
４０６ 変換係数算出部
４０８ 距離算出部
４１０ 判定部
４１２ 特徴点数算出部
４１４ 試行回数算出部
４２０ 条件決定部
４２２ 特徴点ペア抽出部
４２４ 特徴点ペア選択部
４２６ 特徴点ペア数算出部
４２８ 試行回数算出部
４４２ 試行回数判定部
４４４ 有効特徴点数判定部
【技術分野】
【０００１】
本発明は、２枚以上の画像の位置合わせを行う画像処理装置及びそのプログラムに関する。
【背景技術】
【０００２】
この種の画像処理装置は、２枚の画像から特徴点を抽出し、抽出された特徴点から例えば４個の特徴点をランダムに選択し、４個の特徴点の組（特徴点ペア）を形成する。画像処理装置は、特徴点ペアに基づいて変換手法を決定し、決定された変換手法を用いて一方の画像を変換して、他方の画像と位置を合わせる。この変換が所望の品質を満足する場合、決定された変換手法が採用される。
【０００３】
非特許文献１では、特徴点ペアを用いて射影変換行列を求める手法が開示されている。
非特許文献２では、ＲＡＮＳＡＣと呼ばれるアルゴリズムを用いて、正しい特徴点ペアを決定する手法が開示されている。
非特許文献３では、特徴点を抽出する代表的な手法である画像コーナー点抽出アルゴリズムが開示されている。
【０００４】
また、特許文献１では、対象物の平行・回転のずれ量を検出する手法が開示されている。
さらに、特許文献２では、分割画像を合成する際に、合成すべき分割画像を人手により大まかに重ね合わせて置くだけで、マッチング精度が高く、かつ処理量の少ない手法が開示されている。
【０００５】
【非特許文献１】I.Zoghlami, O.Faugeras, and R.Deriche, "Using geometric coeners to build a 2D mosaic from a set of images", CVPR'97, p.420-425, 1997.
【非特許文献２】R.Hartley and A. Zisserman, "Multiple View Geometry", Cambridge University Press p.116-127
【非特許文献３】C.Harris and M.Stephens, "A combined corner and edge detector", Proc. Alvey Vision Conf., p.147-151, 1988.
【特許文献１】特開平１０−２７２５３号公報
【特許文献２】特開平１０−１０８００３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１及び非特許文献２に開示された手法は、処理負荷が増大してしまうことがある。また、特許文献１に開示された手法は、平行移動及び回転のみを行うものであり、特許文献２に開示された手法は、平行移動のみを行うものである。
【０００７】
本発明は、上述した背景からなされたものであり、変換係数を算出するための計算量を削減することができる画像処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る第１の画像処理装置は、第１の画像及び第２の画像から抽出される特徴点に基づいて、画像の変換手法を決定する変換手法決定手段と、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下となる特徴点の組に基づいて、前記変換手法決定手段が変換手法の決定を繰り返し行うように制御する制御手段とを有する。本発明によれば、変換係数を算出するための計算量を削減することができる。
【０００９】
好適には、前記変換手法決定手段は、射影変換で用いられる変換係数を決定する。本発明によれば、変換が、例えば平行移動等に、制限されることを防止することができる。
【００１０】
好適には、前記変換手法決定手段は、第１の画像及び第２の画像から抽出される特徴点の周辺画素の画素値にさらに基づいて、画像の変換手法を決定する。本発明によれば、変換手法の決定が繰り返される回数が削減されるので、計算量をさらに削減することができる。
【００１１】
好適には、前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が、予め決められた値以上となるように制御する。本発明によれば、変換の精度がより良い変換係数を求めることができる。
【００１２】
好適には、前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が、予め決められた値未満である場合、前記変換手法決定手段が、当該特徴点の組とは異なる組を選択するように制御する。本発明によれば、少なくとも一定の精度以上の変換係数を求めることができる。
【００１３】
好適には、前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が収束した場合、当該収束した状態における変換手法に関する情報を出力する。本発明によれば、変換係数を算出する回数を所定値以下に抑えることができる。
【００１４】
好適には、前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点の周辺画素の画素値と、第２の画像の特徴点の周辺画素の画素値とにさらに基づいて、記変換手法決定手段が変換手法の決定を繰り返し行うように制御する。本発明によれば、変換手法の決定が繰り返されるように制御する回数が削減されるので、計算量をさらに削減することができる。
【００１５】
本発明に係る第２の画像処理装置は、特徴点に関する閾値及び割合に基づいて、第１の画像及び第２の画像から抽出される特徴点の数を算出する特徴点数算出手段と、第１の画像及び第２の画像から抽出された前記特徴点数算出手段により算出された数の特徴点から選択される特徴点の組のうち有効とされる組の数が特徴点に関する閾値以上となるように画像の変換手法を決定する変換手法決定手段とを有する。本発明によれば、適切な特徴点数が設定されるので、変換係数の算出の際に、処理負荷の増大を防止することができる。
【００１６】
好適には、前記特徴点数算出手段は、特徴点に関する閾値を割合で乗じた値に所定値が加算された値を特徴点の数とする。本発明によれば、有効特徴点数が、特徴点に関する閾値より高くなる確率が大きくなるので、試行回数が減少され、処理負荷を低減することができる。
【００１７】
好適には、前記変換手法決定手段は、変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が所定値以下である場合、当該特徴点の組は有効であると判定する。本発明によれば、特徴点の組が有効であるか否かの判定を簡易に行うことができる。
【００１８】
好適には、前記特徴点数算出手段により算出された数に基づいて試行回数の上限を算出する試行回数算出手段をさらに有し、前記変換手法決定手段は、前記試行回数算出手段により算出された試行回数の上限を超えない範囲で、変換手法を決定するための試行を繰り返す。本発明によれば、試行が終わることなく継続することを防止することができる。
【００１９】
好適には、前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、有効である特徴点の組が最大となる変換手法を選択する。
【００２０】
好適には、前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、第１の画像と第２の画像との間で重畳する画像部分がない旨の情報を出力する。
【００２１】
好適には、前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、減少された特徴点に関する割合を用いて試行を行う。
【００２２】
また、本発明に係る第１のプログラムは、コンピュータを含む画像処理装置において、第１の画像及び第２の画像から抽出される特徴点に基づいて、画像の変換手法を決定する変換手法決定ステップと、前記決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下となる特徴点の組に基づいて、前記変換手法の決定を繰り返し行うように制御する制御ステップとを前記画像処理装置のコンピュータに実行させる。
【００２３】
また、本発明に係る第２のプログラムは、コンピュータを含む画像処理装置において、特徴点に関する閾値及び割合に基づいて、第１の画像及び第２の画像から抽出される特徴点の数を算出する特徴点数算出ステップと、第１の画像及び第２の画像から抽出された前記算出された数の特徴点から選択される特徴点の組のうち有効とされる組の数が特徴点に関する閾値以上となるように画像の変換手法を決定する変換手法決定ステップとを前記画像処理装置のコンピュータに実行させる。
【発明の効果】
【００２４】
本発明の画像処理装置によれば、変換係数を算出するための計算量を削減することができる。
【発明を実施するための最良の形態】
【００２５】
まず、本発明の理解を容易にするため、本発明の背景を説明する。
画像内の物体が同一平面上にある場合又はカメラ運動が水平面での回転に制限されている場合、２枚の画像間の変換は、射影変換を用いて規定される。物体が複数平面の組み合わせで近似される場合、同一平面上にあるという制限は外されてもよい。
【００２６】
図１は、射影変換を説明する図である。
図１（Ａ）は、画像Ａ内の点(ｘＡ，ｙＡ)を、画像Ｂ内の点(ｘＢ，ｙＢ)に写す射影変換を示す。図１（Ａ）において、画像Ａは、平面ＸＹを視点ＯＡから見て平面ｘＡｙＡに投影した結果であり、画像Ｂは、平面ＸＹを視点ＯＢから見て平面ｘＢｙＢに投影した結果である。この場合、平面ｘＡｙＡ上の座標(ｘＡ，ｙＡ)と、平面ｘＢｙＢ上の座標(ｘＢ，ｙＢ) との関係は、射影変換で表される。
【００２７】
図１（Ｂ）は、同様の関係を見方を変えて説明する図である。図１（Ｂ）に示される３次元空間ＸＹＺにおいて、視点を原点Ｏとして、平面ｘＡｙＡ上の座標点(ｘＡ，ｙＡ)が、平面ｘＢｙＢ上の座標点(ｘＢ，ｙＢ) と重なって見える場合、座標(ｘＡ，ｙＡ)と、座標(ｘＢ，ｙＢ)との関係は、射影変換で表される。
【００２８】
この射影変換により、平面ｘＡｙＡ上の四角形は、平面ｘＢｙＢ上の四角形に変換される。なお、射影変換後の線分間の角度や長さ比等は、必ずしも保存されない。例えば、図１（Ｃ）に示されるように、平面ｘＡｙＡ上の正方形は、平面ｘＢｙＢ上では、変形した四角形に変換される。
このような射影変換は、同次座標系(homogeneous coordinates)における次式で表される。
【００２９】
【数１】
【００３０】
上式の３×３の行列を、射影変換行列（homography行列）と呼ぶ。以下、次式に示されるように、射影変換行列をＨとする。また、ｈｉｊを射影変換係数と呼ぶ。
【００３１】
【数２】
【００３２】
ここで、（１）式は、同次座標系における式であり、等号にはスケール因子が残る(定数倍が未定である)。即ち、（１）式の右辺又は左辺に、実数ｃを乗じても成り立つ。例えば、同次座標ではない(非同次座標の)変換式として、次式を考える。
【００３３】
【数３】
【００３４】
上式の変数ｃを、この式の第３行
【数４】
の関係式を用いて消去すると、次式が得られる。
【００３５】
【数５】
【００３６】
この式が、２次元平面上の点（ｘＡ，ｙＡ）を、点（ｘＢ，ｙＢ）に写す非同次座標系上の射影変換である。上式では、分母及び分子の全てに、係数ｈｉｊが、乗じられている。したがって、射影変換係数ｈｉｊの全てが定数倍された場合においても、結果の(ｘＢ, ｙＢ)は影響を受けない。つまり、射影変換係数の未知数は９個であるが、実際の自由度は８である。よって、８つの式が得られれば、射影変換は求められる。そこで、ｈ３３＝１とすると、次式が得られる。
【００３７】
【数６】
【００３８】
さらに、分母を両辺にかけると、（６）式は、次式のように変形される。
【００３９】
【数７】
【００４０】
（７）式は、ｈｉｊの連立一次方程式であるので、線形演算により解くことが可能である。８個の式を求めるためには、４個の特徴点のペアが与えられればよい。即ち、４個の特徴点ペアの２次元座標があれば、８個（特徴点ペア数４×次元数２）の式が得られる。なお、特徴点ペア数が５以上である場合には、式の数が未知数より多くなるので、連立方程式は、最小二乗法などを用いて解かれる。また、射影変換行列を求める手法は、数多く存在するので、どのような方法が用いられてもよい。
【００４１】
平行移動、剛体変換、拡縮変換、相似変換及びアフィン変換等のその他の幾何変換は、射影変換の一種として表現される。
変換が平行移動により実現される場合、平行移動ベクトルをｔ＝（ｔｘ，ｔｙ）Ｔとすると、変換式及び変換行列Ｈは、次のように表される。
【００４２】
【数８】
【００４３】
【数９】
【００４４】
この場合、自由度は、１である。したがって、平行移動は、１ペアの特徴点があれば算出されることができる。
【００４５】
剛体変換は、平行移動に回転が加えられた変換であり、形状や長さを変化させない等倍変換である。回転角θの回転行列をＲ（θ）とすると、変換式及び変換行列Ｈは、次のように表される。
【００４６】
【数１０】
【００４７】
【数１１】
【００４８】
この場合、自由度は、３である。したがって、剛体変換は、２ペアの特徴点があれば算出されることができる。
【００４９】
拡縮変換は、平行移動に拡大縮小が加えられた変換である。拡大縮小率をαとすると、変換式及び変換行列は、次のように表される。
【００５０】
【数１２】
【００５１】
【数１３】
【００５２】
この場合、自由度は、３である。したがって、拡縮変換は、２ペアの特徴点があれば算出されることができる。なお、拡縮倍率が縦方向と横方向とで異なる場合の変換は、後述するアフィン変換に含めるものとする。
【００５３】
相似変換は、平行移動に回転及び拡大縮小が加えられた変換であり、物体の形状を変化させない変換である。変換式及び変換行列Ｈは、次のように表される。
【００５４】
【数１４】
【００５５】
【数１５】
【００５６】
この場合、自由度は、４である。したがって、相似変換は、２ペアの特徴点があれば算出されることができる。
【００５７】
アフィン変換は、平行線を平行線に写す変換である。変換式及び変換行列Ｈは、次のように表される。
【００５８】
【数１６】
【００５９】
【数１７】
【００６０】
図２は、２枚の画像が入力された場合、この２枚の画像を重ね合わせるための射影変換係数を求める手法を例示する図である。
図２（Ａ）は、入力された２枚の画像（画像Ａ及び画像Ｂ）を例示し、図２（Ｂ）は、重ね合わされた画像Ａ及び画像Ｂを例示する。図２（Ａ）及び図２（Ｂ）に例示するように、平行移動、回転、拡大縮小等が、例えば画像Ａに対して施されると、画像Ａ及び画像Ｂに含まれる物体や模様などができるだけ同じ位置になるように、画像Ａと画像Ｂとは重ね合わされることができる。
【００６１】
図２（Ｃ）は、特徴点ペアを用いて射影変換行列を求める手法を示す図である。図２（Ｃ）に示すように、画像Ａの特徴点を、ａ１，ａ２，…，ａｉ，…とし、画像Ｂの特徴点を、ｂ１，ｂ２，…，ｂｉ，…とする場合、まず、４個の特徴点（ｐ１，ｐ２，ｐ３，ｐ４）が画像Ａから抽出され、４個の特徴点（ｑ１，ｑ２，ｑ３，ｑ４）が画像Ｂからも抽出される。次に、特徴点ペアが、（ｐ１−ｑ１），（ｐ２−ｑ２），（ｐ３−ｑ３），（ｐ４−ｑ４）のように決定される。この４個の特徴点ペアを用いて、射影変換行列が算出され、この射影変換行列を用いて、画像Ａが変換される。さらに、変換後の画像Ａと画像Ｂとの画素値の相互相関係数が算出される。このようにして、全ての特徴点ペアの組み合わせのうち、相互相関係数を最大とする射影変換行列が選択される。
【００６２】
上記のような手法においては、特徴点の数が多い場合、組み合わせの数が膨大になってしまう。例えば、画像Ａ内の特徴点の数をｎＡ、画像Ｂ内の特徴点の数をｎＢとする。この場合、画像Ａから４個、画像Ｂから４個の特徴点を抽出する組み合わせの数は、ｎＡ（ｎＡ−１）（ｎＡ−２）（ｎＡ−３）ｎＢ（ｎＢ−１）（ｎＢ−２）（ｎＢ−３）となる。例えば、ｎＡ＝ｎＢ＝１００とすると、組み合わせの数は、１０６となってしまう。
【００６３】
図２（Ｄ）は、ＲＡＮＳＡＣと呼ばれるアルゴリズムを用いて、正しい特徴点ペアを決定する方式を示す図である。まず、特徴点が、画像Ａ及び画像Ｂから抽出される。画像Ａの特徴点と、画像Ｂの特徴点のうち周囲の画素値が当該画像Ａの特徴点のものと似ている特徴点とが選択され、図２（Ｄ）に示されるａ１とｂ１、ａ２とｂ２及びａ３とｂ５のように、特徴点がペア化される。ここでペア化された特徴点は、正しい場合もあるし、間違っている場合もある。例えば、（ａ１−ｂ１）及び（ａ２−ｂ２）の特徴点ペアは正しいが、（ａ３−ｂ５）の特徴点ペアは間違っている。なお、図中では、特徴点ペアの数は３であるが、実際には、さらに多くの特徴点ペアが存在する。
【００６４】
４個の特徴点ペアが、複数の特徴点ペアからランダムに抜き出され、射影変換行列が算出される。この射影変換行列を用いて、画像Ａの特徴点の座標が変換される。変換後の画像Ａの特徴点の座標と、当該特徴点とペア化されている画像Ｂの特徴点の座標との距離が算出され、この距離が閾値以下となる特徴点ペアの数が算出される。このような特徴点ペアは、有効特徴点ペアと呼ばれ、その数は、有効特徴点ペア数と呼ばれる。このようにして、特徴点ペアのランダム抽出から有効特徴点ペア数の算出までの試行が、所定回数繰り返され、有効特徴点ペア数を最大とする射影変換行列が選択される。
【００６５】
また、上記のような手法において、試行回数Ｔには、正しい４個の特徴点ペアを選択することができる確率がＺとなる回数が設定される。より具体的には、試行回数Ｔは、以下のように設定される。
【００６６】
例えば４個の特徴点ペアが選択される場合、全ての特徴点ペアのうち、正しい特徴点ペアの割合をβとすると、その全てが正しい特徴点ペアである確率は、β４である。ここで、Ｔ回の試行以下で全てが正しい特徴点ペアとなる確率をＺ（例えば、０．９９）とすると、Ｔ回の試行で正解にたどり着かない確率は１−Ｚである。したがって、１−Ｚ＝（１−β４）Ｔ が成立する。この式を変形すると、次式となる。
【００６７】
【数１８】
【００６８】
また、試行回数Ｔは、次のように、適応的に決定されてもよい。まず、全特徴点ペア数をｎβとし、試行番号をＣ（初期値は、例えば０）とする。さらに、Ｃ≧Ｔとなるまで、以下の（ア）〜（ウ）の処理を繰り返す。これにより、正しい特徴点ペアの割合βが求められ、試行回数Ｔが設定される。
【００６９】
（ア）特徴点ペアをランダムに抽出し、射影変換行列を算出し、有効特徴点ペア数を求める。
（イ）β＝Ｋ／ｎβを求め、試行回数Ｔを（８）式を用いて求める。
（ウ）Ｃに１を加算する。
【００７０】
以上説明した処理においては、特徴点数又は特徴点ペア数が少ないほど、処理負荷は小さくなる。しかしながら、上記の手法では、特徴点数及び特徴点ペア数は、適切な値に設定されることができない。また、試行回数が少ないほど、処理負荷は小さくなる。しかしながら、試行回数は、処理負荷を小さくするように設定されることは困難である。特に、２つの画像が重なりを全く持たない場合、試行が、終わることなく続いてしまうことがある。
【００７１】
以下、本発明に係る画像処理装置を詳細に説明する。
図３は、本発明の実施形態に係る画像処理装置１０のハードウェア構成を示す図である。
図３に示すように、画像処理装置１０は、ＣＰＵ１０２及びメモリ１０４などを含む制御装置１００と、ネットワークを介して外部のコンピュータなどとデータの通信を行う通信装置１０６と、ハードディスク駆動装置などの記憶装置１０８と、液晶ディスプレイなどの表示装置並びにキーボード及びポインティングデバイスを含むユーザインタフェース（ＵＩ）装置１１０とを有する。画像処理装置１０は、例えば、後述する画像処理プログラム２０などがインストールされた汎用コンピュータであり、通信装置１０６、記憶装置１０８又はＦＤ、ＣＤ、ＤＶＤ等の記録媒体１１２を介して複数の画像のデータを取得し、取得された画像に対して画像処理を行う。
【００７２】
図４は、本発明の第１の実施形態に係る画像処理装置１０により実行される画像処理プログラム２０の機能構成を示す図である。
図４に示すように、画像処理プログラム２０は、画像位置合わせ部２２、画像変換部２４及び画像重ね合わせ部２６を有する。画像処理プログラム２０は、例えば、通信装置１０６を介して制御装置１００に供給され、メモリ１０４にロードされて、制御装置１００上で動作する図示しないＯＳ上で、ハードウェアを具体的に利用して実行される。画像処理プログラム２０は、記録媒体１１２に格納されて、画像処理装置１０に供給されてもよい。なお、画像処理プログラム２０の全部又は一部の機能は、画像処理装置１０に設けられた例えばＡＳＩＣ（Application Specific Integrated Circuit）などのハードウェアにより実現されてもよい。
【００７３】
画像処理プログラム２０において、画像位置合わせ部２２は、画像Ａ及び画像Ｂを入力し、画像Ａ及び画像Ｂの間の変換係数を算出して画像変換部２４に対して出力する。なお、画像位置合わせ部２２については、後で詳述する。
【００７４】
画像変換部２４は、画像位置合わせ部２２により算出された変換係数を用いて、画像Ａを変換し、変換後の画像Ａを画像重ね合わせ部２６に対して出力する。なお、画像変換部２４は、画像位置合わせ部２２に含まれてもよい。例えば、変換係数を求めるために、画像位置合わせ部２２において変換後の画像Ａが既に求められている場合、変換後の画像Ａが、画像位置合わせ部２２から画像重ね合わせ部２６に対して出力されてもよい。
【００７５】
画像重ね合わせ部２６は、変換後の画像Ａと、画像Ｂとを入力し、これらの画像を重ね合わせて合成画像を生成する。この合成画像は、画像Ａと画像Ｂとが組み合わせて作成された、画像Ａ及び画像Ｂよりも大きな画像である。なお、このような合成画像を、モザイク合成画像とも呼ぶ。
【００７６】
次に、画像位置合わせ部２２について、より詳細に説明する。
図５は、画像位置合わせ部２２による画像位置合わせ処理の概要を説明する図である。
図５（Ａ）は、画像位置合わせ部２２に入力される画像Ａ及び画像Ｂを例示する。図５（Ａ）に例示するように、画像Ａには、特徴点ａ１〜ａ４が含まれ、画像Ｂには、特徴点ｂ１〜ｂ４が含まれている。ここで、特徴点ａ１とｂ１、ａ２とｂ２、ａ３とｂ３、ａ４とｂ４は、ペアとなるべき組み合わせであるとする。なお、画像Ａの特徴点数と画像Ｂの特徴点数とは異なってもよい。
【００７７】
まず、画像位置合わせ部２２は、画像Ａの特徴点及び画像Ｂの特徴点から１つずつの特徴点を選択する。画像位置合わせ部２２は、特徴点ペアの数が１であるので、平行移動における変換係数を算出する。例えば、画像位置合わせ部２２は、ａ１とｂ４を選択したとする。
【００７８】
図５（Ｂ）は、特徴点ａ１とｂ４とから算出された変換係数を用いて変換された画像Ａと、画像Ｂとを示す。画像位置合わせ部２２は、特徴点ａ２との距離が閾値Ｔｈ１以下である画像Ｂの特徴点を探索する。同様に、画像位置合わせ部２２は、特徴点ａ３，ａ４との距離が閾値Ｔｈ１以下である画像Ｂの特徴点を探索する。その結果、画像位置合わせ部２２は、有効特徴点ペア数が閾値Ｔｈ２（例えば、４）未満である場合、再度、特徴点ペアを選択する。例えば、画像位置合わせ部２２は、ａ１とｂ１を選択したとする。
【００７９】
図５（Ｃ）は、特徴点ａ１とｂ１とから算出された変換係数を用いて変換された画像Ａと、画像Ｂとを示す。画像位置合わせ部２２は、特徴点ａ２との距離が閾値Ｔｈ１以下である画像Ｂの特徴点としてｂ２を検出したとする。同様に、画像位置合わせ部２２は、特徴点ａ３，ａ４との距離が閾値Ｔｈ１以下である画像Ｂの特徴点として、それぞれｂ３，ｂ４を検出したとする。その結果、画像位置合わせ部２２は、有効特徴点ペア数が閾値Ｔｈ２以上であるので、ａ１とｂ１のペアは正しいと判定する。
【００８０】
さらに、画像位置合わせ部２２は、有効特徴点ペア（ａ１−ｂ１），（ａ２−ｂ２），（ａ３−ｂ３），（ａ４−ｂ４）を用いて、新たな変換係数（射影変換行列）を算出して、再度、画像Ａを変換する。画像位置合わせ部２２は、このような処理を、特徴点ペアのパターンが変化しなくなるまで繰り返す。
【００８１】
図５（Ｄ）は、得られた変換係数を用いて変換された画像Ａと、画像Ｂとを示す。このようにして、最適な変換係数が、画像位置合わせ部２２により求められる。
【００８２】
図６は、変換行列Ｈが平行移動では近似できない場合における画像位置合わせ部２２による画像位置合わせ処理の概要を説明する図である。
画像Ａと画像Ｂの回転角が大きい場合等、変換行列Ｈが平行移動では近似できない場合、画像位置合わせ部２２は、最初に選択する特徴点ペアの数を２として、相似変換における変換係数を求める。
【００８３】
図６（Ａ）は、画像位置合わせ部２２に入力される画像Ａ及び画像Ｂを例示する。本例においても、図５に示される場合と同様に、特徴点ａ１とｂ１、ａ２とｂ２、ａ３とｂ３、ａ４とｂ４は、ペアとなるべき組み合わせであるとする。
【００８４】
まず、画像位置合わせ部２２は、特徴点ペアの数を２として、相似変換における変換係数を算出する。例えば、画像位置合わせ部２２は、特徴点ペア（ａ１−ｂ１）及び特徴点ペア（ａ２−ｂ２）を選択したとする。
【００８５】
図６（Ｂ）は、特徴点ペア（ａ１−ｂ１）及び特徴点ペア（ａ２−ｂ２）から算出された変換係数を用いて変換された画像Ａと、画像Ｂとを示す。画像位置合わせ部２２は、特徴点ａ３との距離が閾値Ｔｈ１以下である画像Ｂの特徴点としてｂ３を検出したとする。同様に、画像位置合わせ部２２は、特徴点ａ４との距離が閾値Ｔｈ１以下である画像Ｂの特徴点として、ｂ４を検出したとする。その結果、画像位置合わせ部２２は、有効特徴点ペア数が閾値Ｔｈ２以上であるので、特徴点ペア（ａ１−ｂ１）及び特徴点ペア（ａ２−ｂ２）は正しいと判定する。
【００８６】
さらに、画像位置合わせ部２２は、有効特徴点ペア（ａ１−ｂ１），（ａ２−ｂ２），（ａ３−ｂ３），（ａ４−ｂ４）を用いて、新たな変換係数（射影変換行列）を算出して、再度、画像Ａを変換する。画像位置合わせ部２２は、このような処理を、特徴点ペアのパターンが変化しなくなるまで繰り返し、図６（Ｄ）に示される様な変換を行う変換係数を求める。
【００８７】
図７は、本発明の第１の実施形態に係る画像位置合わせ部２２の機能構成を示す図である。
図７に示すように、画像位置合わせ部２２は、特徴点抽出部２２０、特徴点ペア選択部２２２、変換係数算出部２２４及び有効特徴点ペア探索部２２６を有する。
【００８８】
画像位置合わせ部２２において、特徴点抽出部２２０は、画像Ａ（第１の画像）及び画像Ｂ（第２の画像）を入力し、画像Ａ及び画像Ｂから特徴点を抽出し、抽出された特徴点の座標を特徴点ペア選択部２２２及び有効特徴点ペア探索部２２６に対して出力する。特徴点抽出部２２０は、例えば非特許文献３に開示されているＨａｒｒｉｓオペレータ等の画像コーナー点抽出アルゴリズムを用いて、特徴点を抽出する。なお、コーナー点は、２方向以上のエッジを有する点を意味する。また、コーナー点抽出アルゴリズムは、本例に限定されず、特徴点抽出部２２０は、その他様々なアルゴリズムを用いてもよい。
【００８９】
特徴点ペア選択部２２２は、特徴点抽出部２２０により抽出された画像Ａ及び画像Ｂの特徴点から１個ずつ特徴点を選択し、特徴点ペアを決定する。より具体的には、画像のＡの特徴点を、ａ１，ａ２，…，ａｉ，…とし、画像のＢの特徴点を、ｂ１，ｂ２，…，ｂｉ，…とすると、特徴点ペア選択部２２２は、特徴点ａ１，ａ２，…，ａｉ，…から１個の特徴点を選択し、特徴点ｂ１，ｂ２，…，ｂｉ，…から１個の特徴点を選択し、画像Ａの特徴点と画像Ｂの特徴点とが対になるようにして特徴点ペアを決定する。
【００９０】
変換係数算出部２２４は、特徴点ペア選択部２２２により決定された特徴点ペアを用いて変換係数を算出し、この変換係数を有効特徴点ペア探索部２２６に対して出力する。したがって、特徴点ペア選択部２２２及び変換係数算出部２２４は、画像の変換手法を決定する変換手法決定手段を構成する。なお、変換係数は、例えば、平行移動変換における変換係数である。
【００９１】
有効特徴点ペア探索部２２６は、変換係数算出部２２４により決定される変換手法を適用されて変換された画像Ａの特徴点と、画像Ｂの特徴点との距離が閾値以下となる特徴点の組に基づいて、特徴点ペア選択部２２２及び変換係数算出部２２４が変換手法の決定を繰り返し行うように制御する制御手段を構成する。
【００９２】
より具体的には、まず、有効特徴点ペア探索部２２６は、特徴点抽出部２２０により抽出された画像Ａの特徴点のうち、特徴点ペア選択部２２２により選択された特徴点以外の特徴点を、変換係数算出部２２４により算出された変換係数を含む変換式を用いて変換する。次に、有効特徴点ペア探索部２２６は、変換された画像Ａの特徴点と、画像Ｂの特徴点のうち特徴点ペア選択部２２２により選択された特徴点以外の特徴点との距離を算出する。ここで、有効特徴点ペア探索部２２６は、変換された画像Ａの特徴点に最も近い画像Ｂの特徴点を検出し、画像Ａの当該特徴点と画像Ｂの当該特徴点との例えばユークリッド距離を算出する。
【００９３】
有効特徴点ペア探索部２２６は、算出された距離が予め決められた閾値Ｔｈ１以下であるか否かを判定する。有効特徴点ペア探索部２２６は、算出された距離が閾値Ｔｈ１以下である場合、この特徴点ペアは有効特徴点ペアであると判定する。有効特徴点ペア探索部２２６は、特徴点ペア選択部２２２により選択された特徴点以外の特徴点の全てに対してこのような判定を行い、有効特徴点ペア数を算出する。なお、有効特徴点ペア探索部２２６は、変換された画像Ａの特徴点との距離が閾値Ｔｈ１以下である画像Ｂの特徴点を検出してもよい。
【００９４】
有効特徴点ペア探索部２２６は、有効特徴点ペア数が、予め決められた閾値Ｔｈ２（例えば、４以上の整数）以上となるように制御する。具体的には、有効特徴点ペア探索部２２６は、有効特徴点ペア数が閾値Ｔｈ２未満である場合、特徴点ペア選択部２２２及び変換係数算出部２２４が、当該特徴点ペアとは異なる特徴点ペアを選択するように制御する。この場合、特徴点ペア選択部２２２は、前回とは異なる特徴点ペアを選択する。
【００９５】
有効特徴点ペア探索部２２６は、有効特徴点ペア数が閾値Ｔｈ２以上である場合、再度、変換係数算出部２２４が変換係数を算出するように制御する。この場合、変換係数算出部２２４は、有効特徴点ペア探索部２２６により算出された距離が閾値Ｔｈ１以下である特徴点ペアを用いて、変換係数を算出し、この変換係数を有効特徴点ペア探索部２２６に対して、再度、出力する。例えば、変換係数算出部２２４は、有効特徴点ペア数が２である場合には相似変換における変換係数を算出し、有効特徴点ペア数が３である場合にはアフィン変換における変換係数を算出し、有効特徴点ペア数が４以上である場合には射影変換における変換係数を算出する。
【００９６】
有効特徴点ペア探索部２２６は、有効特徴点ペア数が収束するまで上記の制御を繰り返し、収束した状態における変換係数（変換手法に関する情報）を出力する。また、特徴点ペア選択部２２２は、全ての特徴点の組み合わせを選択したにもかからず有効特徴点ペア数が閾値Ｔｈ２未満である場合、画像Ａと画像Ｂとの間で重畳する画像部分がないとして、終了信号を出力する。
【００９７】
図８は、画像位置合わせ部２２による画像位置合わせ処理（Ｓ１０）のフローチャートを示す。
図８に示すように、ステップ１００（Ｓ１００）において、画像位置合わせ部２２の特徴点抽出部２２０は、画像Ａ及び画像Ｂから特徴点を抽出する。
ステップ１０２（Ｓ１０２）において、特徴点ペア選択部２２２は、抽出された特徴点から特徴点ペアを選択する。
【００９８】
ステップ１０４（Ｓ１０４）において、変換係数算出部２２４は、選択された特徴点ペアに基づいて変換係数を算出する。
ステップ１０６（Ｓ１０６）において、有効特徴点ペア探索部２２６は、変換係数を用いて、画像Ａの特徴点を変換する。
【００９９】
ステップ１０８（Ｓ１０８）において、有効特徴点ペア探索部２２６は、変換後の画像Ａの特徴点と、画像Ｂの特徴点との距離を算出する。
ステップ１１０（Ｓ１１０）において、有効特徴点ペア探索部２２６は、算出された距離が閾値Ｔｈ１以下である有効特徴点ペアの数を算出する。
【０１００】
ステップ１１２（Ｓ１１２）において、有効特徴点ペア探索部２２６は、有効特徴点ペア数が閾値Ｔｈ２以上であるか否かを判定する。有効特徴点ペア探索部２２６は、有効特徴点ペア数が閾値Ｔｈ２以上である場合にはＳ１１４の処理に進み、そうでない場合にはＳ１１８の処理に進む。
【０１０１】
ステップ１１４（Ｓ１１４）において、有効特徴点ペア探索部２２６は、算出された有効特徴点ペア数が収束しているか否かを判定する。例えば、有効特徴点ペア探索部２２６は、算出された有効特徴点ペア数が前回算出された値と同じか否かを判定する。有効特徴点ペア探索部２２６は、算出された有効特徴点ペア数が前回算出された値と同じである場合、有効特徴点ペア数が収束していると判定し、Ｓ１１６の処理に進み、そうでない場合にはＳ１０４の処理に戻って、再度、変換係数を算出する。
【０１０２】
ステップ１１６（Ｓ１１６）において、有効特徴点ペア探索部２２６は、変換係数を画像変換部２４に対して出力する。
【０１０３】
一方、ステップ１１８（Ｓ１１８）においては、特徴点ペア選択部２２２は、全ての特徴点の組み合わせについて終了したか否かを判定する。特徴点ペア選択部２２２は、全ての特徴点の組み合わせについて終了した場合には終了信号を出力して処理を終了し、そうでない場合にはＳ１００の処理に戻る。
【０１０４】
このように、ペア化される特徴点は、最初、狭い領域内に存在する一方、変換係数の算出が繰り返されるに従って、広い領域内に存在するようになる。したがって、ペア化される特徴点が存在する領域が次第に広がることにより、変換係数は、画像全体に渡って誤差のないものとなる。これにより、画像処理装置１０は、変換精度の良い変換行列を求めることができる。
【０１０５】
また、例えば、画像Ａの特徴点の数ｎＡ及び画像Ｂの特徴点の数ｎＢが１００であるとすると、特徴点ペアの数が１である場合、画像Ａ及び画像Ｂから特徴点を選択する組み合わせの数は、ｎＡｎＢより１０４であり、特徴点ペアの数が２である場合、前記組み合わせの数は、ｎＡ（ｎＡ−１）ｎＢ（ｎＢ−１）より１０８であり、特徴点ペアの数が３である場合、前記組み合わせの数は、ｎＡ（ｎＡ−１）（ｎＡ−２）ｎＢ（ｎＢ−１）（ｎＢ−２）より１０１２である。したがって、組み合わせ回数を大幅に削減することができる。これにより、計算量が削減されることができる。
【０１０６】
なお、画像位置合わせ部２２の特徴点ペア選択部２２２により最初に選択される特徴点ペアの数は、１、２及び３のいずれであってもよい。例えば、この特徴点ペアの数が３である場合、変換係数算出部２２４は、アフィン変換における変換係数を算出する。
【０１０７】
また、特徴点ペアの数が２である場合、有効特徴点ペア探索部２２６は、選択された特徴点ペアが拡縮変換を満たしているか否かを判定してもよい。例えば選択された特徴点ペアを（ａ１，ｂ１）及び（ａ２，ｂ２）であるとすると、有効特徴点ペア探索部２２６は、線分ａ１ａ２の傾きと、線分ｂ１ｂ２の傾きとが略等しい場合、選択された特徴点ペアは拡縮変換を満たしていると判定する。有効特徴点ペア探索部２２６は、選択された特徴点ペアが拡縮変換を満たしている場合には次の処理に移り、そうでない場合には、再度、特徴点ペアが選択されるように制御する。これにより、拡縮変換に限定される場合には、処理の高速化が可能となる。
【０１０８】
また、特徴点ペアの数が２である場合、有効特徴点ペア探索部２２６は、選択された特徴点ペアが剛体変換を満たしているか否かを判定してもよい。例えば選択された特徴点ペアを（ａ１，ｂ１）及び（ａ２，ｂ２）であるとすると、有効特徴点ペア探索部２２６は、線分ａ１ａ２の長さと、線分ｂ１ｂ２の長さとが略等しい場合、択された特徴点ペアは剛体変換を満たしていると判定する。有効特徴点ペア探索部２２６は、選択された特徴点ペアが剛体変換を満たしている場合には次の処理に移り、そうでない場合には、再度、特徴点ペアが選択されるように制御する。これにより、剛体変換に限定される場合には、処理の高速化が可能となる。
【０１０９】
図９は、本発明の第１の実施形態に係る画像処理装置１０の全体動作（Ｓ２０）を示すフローチャートである。
図９に示すように、画像処理装置１０が画像Ａ及び画像Ｂを受け付けると、画像処理プログラム２０の画像位置合わせ部２２は、画像位置合わせ処理（Ｓ１０）を実行し、画像Ａと画像Ｂとの間の変換係数を画像変換部２４に対して出力する。
【０１１０】
ステップ２００（Ｓ２００）において、画像変換部２４は、算出された変換係数を用いて、画像Ａを変換し、変換後の画像Ａを画像重ね合わせ部２６に対して出力する。
ステップ２０２（Ｓ２０２）において、画像重ね合わせ部２６は、変換後の画像Ａと、画像Ｂとを重ね合わせて合成画像を生成して出力する。
【０１１１】
図１０は、本発明の実施形態に係る画像処理装置１０により生成された合成画像を例示する図である。
図１０に例示するように、画像Ａが変換され、変換後の画像Ａと、画像Ｂとが組み合わされて、より大きなモザイク合成画像が生成される。
【０１１２】
図１１は、画像から抽出される特徴点数と試行回数との関係を示す図である。
図１１に示すように、例えば特徴点ペアの数が２である場合、本発明の実施形態に係る画像処理装置１０は、１０８回の試行回数で、探索することができる。したがって、画像処理装置１０は、従来手法における試行回数（１０１６）より、試行回数を削減することが出来る。このため、計算量が削減され、処理負荷が、低減されることができる。
【０１１３】
次に、本発明の第２の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、平行移動近似処理、拡縮変換近似処理、剛体変換近似処理、相似変換近似処理及びアフィン変換近似処理の少なくとも２以上の処理が、順次行われる点で、第１の実施形態に係る画像処理装置１０とは異なる。
【０１１４】
図１２は、本発明の第２の実施形態に係る画像位置合わせ部２８の機能構成を示す図である。なお、図１２に示された各構成のうち、図７に示された構成と実質的に同一のものには同一の符号が付されている。
図１２に示すように、画像位置合わせ部２８は、特徴点抽出部２２０、平行移動近似部２３０、拡縮変換近似部２８０、剛体変換近似部２８２、相似変換近似部２８４及びアフィン変換近似部２８６を有する。ここで、平行移動近似部２３０、拡縮変換近似部２８０、剛体変換近似部２８２、相似変換近似部２８４及びアフィン変換近似部２８６には、図７に示される特徴点ペア選択部２２２、変換係数算出部２２４及び有効特徴点ペア探索部２２６が含まれる。
【０１１５】
平行移動近似部２３０は、１組の特徴点ペアを選択し、平行移動における変換係数を算出する。拡縮変換近似部２８０は、平行移動近似部２３０から終了信号を受け付けた場合、２組の特徴点ペアを選択し、拡縮変換における変換係数を算出する。剛体変換近似部２８２は、拡縮変換近似部２８０から終了信号を受け付けた場合、２組の特徴点ペアを選択し、剛体変換における変換係数を算出する。相似変換近似部２８４は、剛体変換近似部２８２から終了信号を受け付けた場合、２組の特徴点ペアを選択し、相似変換における変換係数を算出する。アフィン変換近似部２８６は、相似変換近似部２８４から終了信号を受け付けた場合、３組の特徴点ペアを選択し、アフィン変換における変換係数を算出する。
【０１１６】
図１３は、本実施形態に係る画像処理装置１０における画像位置合わせ部２２による画像位置合わせ処理（Ｓ３０）のフローチャートを示す。
図１３に示すように、ステップ３００（Ｓ３００）において、画像位置合わせ部２２は、近似処理を平行移動近似処理とする。具体的には、画像位置合わせ部２２の特徴点抽出部２２０は、画像Ａ及び画像Ｂから特徴点を抽出して、平行移動近似部２３０に対して出力する。
【０１１７】
ステップ３０２（Ｓ３０２）において、平行移動近似部２３０は、位置合わせ処理を行う。具体的には、平行移動近似部２３０は、画像位置合わせ処理（Ｓ１０）と同様にして、変換係数を求める。
【０１１８】
ステップ３０４（Ｓ３０４）において、平行移動近似部２３０は、Ｓ３０２の処理で、変換係数が求まったか否かを判定する。平行移動近似部２３０は、変換係数が求まった場合にはＳ３０６の処理に進み、そうでない場合にはＳ３０８の処理に進む。
ステップ３０６（Ｓ３０６）において、平行移動近似部２３０は、変換係数を出力する。
【０１１９】
一方、ステップ３０８（Ｓ３０８）においては、平行移動近似部２３０は、終了信号を、拡縮変換近似部２８０に対して出力する。この場合、画像位置合わせ部２８は、平行移動近似部２３０による平行移動近似処理の次の処理として、拡散変換近似処理を選択する。具体的には、拡縮変換近似部２８０は、特徴点抽出部２２０により抽出された特徴点に関する情報を受け付け、Ｓ３０２の処理に戻る。
【０１２０】
以降、拡縮変換近似部２８０は、平行移動近似部２３０と同様に、Ｓ３０２及びＳ３０４の処理を行って、変換係数が求まった場合にはＳ３０６の処理で変換係数を出力する。変換係数が求まらなかった場合、剛体変換近似部２８２、相似変換近似部２８４及びアフィン変換近似部２８６が、順に、処理を行う。
【０１２１】
なお、画像位置合わせ部２８には、平行移動近似部２３０、拡縮変換近似部２８０、剛体変換近似部２８２、相似変換近似部２８４及びアフィン変換近似部２８６のうち、少なくとも２つの構成要素が含まれていればよい。また、画像位置合わせ部２８において、これらの構成要素の順序は、本例に限定されない。例えば、画像位置合わせ部２８には、平行移動近似部２３０及び拡縮変換近似部２８０がこの順序で配置されてもよいし、平行移動近似部２３０、相似変換近似部２８４及びアフィン変換近似部２８６がこの順序で配置されてもよい。
【０１２２】
次に、本発明の第３の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、変換後の画像Ａの特徴点の周辺画素の画素値と、画像Ｂの特徴点の周辺画素の画素値とにさらに基づいて、画像の変換手法を決定する点で、第１の実施形態に係る画像処理装置１０とは異なる。
【０１２３】
本実施形態では、画像位置合わせ部２２の変換係数算出部２２４は、算出した変換係数を用いて、画像Ａの特徴点ｐｉの周辺画素を変換し、変換された画像Ａの特徴点ｐｉの周辺画素の画素値と、画像Ｂの特徴点ｑｊの周辺画素の画素値とに基づいて、特徴点ペア（ｐｉ，ｑｊ）が有効特徴点ペアであるか否かを判定する。例えば、変換係数算出部２２４は、これらの画素値の正規化相関、２乗誤差又は絶対誤差を用いて判定する。変換係数算出部２２４は、例えば、２乗誤差等が所定値以下である場合、特徴点ペアが有効特徴点ペアであると判定する。
【０１２４】
変換係数算出部２２４は、選択された特徴点ペアが有効特徴点ペアであると判定した場合、変換係数を有効特徴点ペア探索部２２６に対して出力し、そうでない場合、特徴点ペア選択部２２２が特徴点ペアを再び選択するように制御する。
【０１２５】
なお、画像位置合わせ部２２において、有効特徴点ペア探索部２２６が、変換後の画像Ａの特徴点の周辺画素の画素値と、画像Ｂの特徴点の周辺画素の画素値とにさらに基づいて、画像の変換手法の決定を繰り返し行うように制御してもよい。例えば、有効特徴点ペア探索部２２６は、変換された特徴点ｐｉと特徴点ｑｊとの距離が予め決められた閾値Ｔｈ１以下であり、かつ、変換された特徴点ｐｉの周辺画素の画素値と特徴点ｑｊの周辺画素の画素値とが類似する場合、この特徴点ペアは有効特徴点ペアであると判定する。
【０１２６】
次に、本発明の第４の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、適切な試行回数を設定することにより計算量を削減する点で、第１の実施形態〜第３の実施形態に係る画像処理装置１０とは異なる。
【０１２７】
図１４は、本発明の実施形態に係る画像処理装置１０により実行される画像処理プログラム３０の機能構成を示す図である。
図１４に示すように、画像処理プログラム３０は、画像処理プログラム２０（図４）に有効特徴点割合出力部３２が追加され、さらに、画像位置合わせ部２２が画像位置合わせ部４０に置換された構成を有する。なお、図１４に示された各構成のうち、図４に示された構成と実質的に同一のものには同一の符号が付されている。
【０１２８】
画像処理プログラム３０において、画像位置合わせ部４０は、画像Ａ及び画像Ｂを入力し、ＲＡＮＳＡＣアルゴリズムを用いて画像Ａ及び画像Ｂの間の変換係数を算出して画像変換部２４に対して出力する。なお、画像位置合わせ部４０については、後で詳述する。
【０１２９】
有効特徴点割合出力部３２は、後述する有効特徴点割合αを、画像位置合わせ部４０に対して出力する。また、有効特徴点割合出力部３２は、試行回数に応じて、有効特徴点割合αを変化させる。なお、有効特徴点割合αについては、後で詳述する。
【０１３０】
次に、画像位置合わせ部４０について、より詳細に説明する。
図１５は、本発明の第４の実施形態に係る画像位置合わせ部４０の機能構成を示す図である。
図１５に示すように、画像位置合わせ部４０は、条件決定部４００、特徴点抽出部４０２、特徴点ペア選択部４０４、変換係数算出部４０６、距離算出部４０８及び判定部４１０を有し、条件決定部４００は、特徴点数算出部４１２及び試行回数算出部４１４を有する。
【０１３１】
画像位置合わせ部４０は、これらの構成要素により、画像Ａ及び画像Ｂから抽出される特徴点の数及び試行回数の上限を算出し、画像Ａ及び画像Ｂから当該数の特徴点を選択し、選択された特徴点をペア化し、当該試行回数の上限を超えない範囲で、有効特徴点ペア数が閾値を超えるように試行を繰り返し、有効特徴点ペア数が閾値を超える変換における変換係数を出力する。
【０１３２】
画像位置合わせ部４０において、条件決定部４００は、特徴点に関する閾値及び割合（即ち、ＲＡＮＳＡＣの閾値ＫＲ及び有効特徴点割合出力部３２から出力される有効特徴点割合α）を入力し、特徴点数及び試行回数を決定する。条件決定部４００は、決定された特徴点数を特徴点抽出部４０２に対して出力し、試行回数を判定部４１０に対して出力する。
【０１３３】
条件決定部４００において、特徴点数算出部４１２は、ＲＡＮＳＡＣの閾値ＫＲ及び有効特徴点割合αに基づいて、画像Ａ及び画像Ｂから抽出される特徴点数を算出する。また、試行回数算出部４１４は、特徴点数算出部４１２により算出された特徴点数に基づいて試行回数の上限を算出する。なお、特徴点数算出部４１２による特徴点数算出処理及び試行回数算出部４１４による試行回数算出処理については、後で詳述する。
【０１３４】
特徴点抽出部４０２は、画像Ａ、画像Ｂ及び条件決定部４００から出力される特徴点数を入力し、画像Ａ及び画像Ｂから当該特徴点数の特徴点を抽出し、抽出された特徴点の座標を特徴点ペア選択部４０４及び距離算出部４０８に対して出力する。
【０１３５】
特徴点ペア選択部４０４は、特徴点抽出部４０２により抽出された画像Ａ及び画像Ｂの特徴点からＮ個の特徴点を選択し、Ｎ組の特徴点ペアを決定する。より具体的には、画像のＡの特徴点を、ａ１，ａ２，…，ａｉ，…とし、画像のＢの特徴点を、ｂ１，ｂ２，…，ｂｉ，…とすると、特徴点ペア選択部４０４は、特徴点ａ１，ａ２，…，ａｉ，…からＮ個の特徴点を選択し、特徴点ｂ１，ｂ２，…，ｂｉ，…からＮ個の特徴点を選択し、画像Ａの特徴点と画像Ｂの特徴点とが対になるようにしてＮ個の特徴点ペアを決定する。
【０１３６】
変換係数算出部４０６は、特徴点ペア選択部４０４により決定された特徴点ペアを用いて変換係数を算出し、この変換係数を距離算出部４０８に対して出力する。
【０１３７】
距離算出部４０８は、特徴点抽出部４０２により抽出された画像Ａの特徴点のうち、特徴点ペア選択部４０４により選択された特徴点以外の特徴点を、変換係数算出部４０６により算出された変換係数を含む変換式を用いて変換する。次に、距離算出部４０８は、変換された画像Ａの特徴点と、画像Ｂの特徴点のうち特徴点ペア選択部４０４により選択された特徴点以外の特徴点との距離を算出する。より具体的には、距離算出部４０８は、変換された画像Ａの特徴点に最も近い画像Ｂの特徴点を検出し、画像Ａの当該特徴点と画像Ｂの当該特徴点との例えばユークリッド距離を算出する。
【０１３８】
さらに、距離算出部４０８は、算出された距離が予め決められた閾値Ｔ０以下であるか否かを判定する。距離算出部４０８は、算出された距離が閾値Ｔ０以下である場合、この特徴点ペアは有効特徴点ペアであると判定する。距離算出部４０８は、特徴点ペア選択部４０４により選択された特徴点以外の特徴点の全てに対してこのような判定を行い、有効特徴点ペアの数を算出する。以降、算出された数を、有効特徴点数Ｋとする。
【０１３９】
判定部４１０は、距離算出部４０８により算出された有効特徴点数Ｋが、入力されたＲＡＮＳＡＣの閾値ＫＲ以上であるか否かを判定する。有効特徴点数Ｋが閾値ＫＲ以上である場合、判定部４１０は、この有効特徴点数Ｋが算出される際の変換において用いられた変換係数を、画像変換部２４に対して出力する。有効特徴点数Ｋが閾値ＫＲ未満である場合、判定部４１０は、特徴点ペア選択部４０４に対して、特徴点の選択及び特徴点ペアの決定を再度行う旨の出力を行う。この場合、再度、特徴点ペアが決定され、変換係数が算出され、有効特徴点数Ｋが算出され、判定処理が行われる。
【０１４０】
また、判定部４１０は、試行回数算出部４１４により算出された試行回数の上限を超えない範囲で、変換手法を決定するための試行を繰り返す。即ち、特徴点ペアの選択処理から判定処理までが繰り返し実行され、特徴点ペアの選択回数が、算出された試行回数を超えた場合、判定部４１０は、処理を終了する。なお、特徴点ペアの選択回数が、算出された試行回数を超えた場合の詳細については、後で詳述する。
【０１４１】
このように、画像位置合わせ部４０において、特徴点ペア選択部４０４、変換係数算出部４０６、距離算出部４０８及び判定部４１０は、画像Ａ及び画像Ｂ抽出された特徴点から選択される特徴点ペアのうち有効とされる組の数が特徴点に関する閾値（ＲＡＮＳＡＣの閾値）以上となるように画像の変換手法を決定する変換手法決定手段を構成する。
【０１４２】
なお、特徴点間の距離は、ユークリッド距離に限定されず、他の距離であってもよい。例えば、距離は、マンハッタン距離、その他のノルムＬ１，Ｌ２，Ｌ３，Ｌ４，…，Ｌ∞ノルム等であってもよい。また、距離算出部４０８は、画像Ａの特徴点の周囲の画素を変換し、変換後の画素値と、この変換後の画素と同じ位置の画像Ｂの画素値との相関係数を算出し、この相関係数を予め決められた閾値と比較してもよい。また、距離算出部４０８は、画像Ａの特徴点の周囲の画素を変換し、変換後の画素値と、この変換後の画素と同じ位置の画像Ｂの画素値との差分の２乗を算出し、この算出された値と予め決められた閾値とを比較してもよい。
【０１４３】
次に、画像位置合わせ部４０の特徴点数算出部４１２による特徴点数算出処理及び試行回数算出部４１４による試行回数算出処理を、より詳細に説明する。
ここで、画像Ａ及び画像Ｂ内の特徴点数をｎ、有効特徴点の数をｎｘ、特徴点のうち有効特徴点の割合をα（＝ｎｘ／ｎ）、特徴点ペア数をＮ、正しい特徴点ペアを選択する確率をｗ、Ｔ回の試行以下で正解に辿り着く確率をＺとする。
【０１４４】
試行回数算出部４１４は、画像Ａの特徴点数と画像Ｂの特徴点数とが一致する場合、次式を用いて、試行回数を算出する。
【０１４５】
【数１９】
【０１４６】
また、試行回数算出部４１４は、画像Ａの特徴点数と画像Ｂの特徴点数が異なる場合、次式を用いて、試行回数を算出する。
【０１４７】
【数２０】
【０１４８】
試行回数の算出には、特徴点数ｎを設定する必要がある。したがって、特徴点数算出部４１２は、次式を用いて、特徴点数を算出する。
【０１４９】
【数２１】
【０１５０】
以下、試行回数及び特徴点数を算出する式の導出方法を説明する。
画像Ａの特徴点数と画像Ｂの特徴点数が一致する場合、画像Ａのｎ個の特徴点からＮ個の特徴点を選択する組み合わせは、重複も許すと、ｎＮ通りであり、画像Ｂのｎ個の特徴点からＮ個の特徴点を選択する組み合わせも、同様に、ｎＮ通りである。したがって、画像Ａ及び画像ＢのそれぞれからＮ個の特徴点を選択する組み合わせは、ｎ２Ｎ通りである。この中で、正しい特徴点ペアとなる組み合わせは、ｎｘ（ｎｘ−１）…（ｎｘ−（Ｎ−１））通りである。この値を、ｎｘＮで近似すると、正しい特徴点ペアを選択する確率ｗは、次式で表される。
【０１５１】
【数２２】
【０１５２】
また、「Ｔ回の試行で正解に辿り着かない確率」は、１−Ｚであるので、１−Ｚ＝（１−Ｗ）Ｔが、成り立つ。よって、（１９）式が求められる。なお、正しい特徴点ペアとなる組み合わせは、ｎｘＮで近似されたが、近似されなくてもよい。また、画像ＡからＮ個の特徴点を選択する組み合わせは、重複を許して選択される場合を示したが、重複を許さないように選択されてもよい。
【０１５３】
画像Ａの特徴点数と画像Ｂの特徴点数が異なる場合、まず、試行回数算出部４１４は、特徴点数は等しいものとして、又は特徴点数密度は等しいものとして、一方の特徴点数から、他方の特徴点数を換算する。例えば、試行回数算出部４１４は、画像のＡの特徴点数ｎＡを求めてから、画像Ｂの特徴点数ｎＢを求める。より具体的には、画像Ａ及び画像Ｂの面積をそれぞれＳＡ，ＳＢとすると、特徴点数が等しいと換算される場合、試行回数算出部４１４は、ｎＢ＝ｎＡより、ｎＢを求める。また、特徴点密度が等しいと換算される場合、試行回数算出部４１４は、ｎＢ＝（ＳＢ／ＳＡ）ｎＡより、ｎＢを求める。
【０１５４】
さらに、画像Ａ内の有効特徴点割合をαＡ（＝ｎｘ／ｎＡ）、画像Ｂ内の有効特徴点割合をαＢ（＝ｎｘ／ｎＢ）とすると、画像Ａ及び画像Ｂの特徴点からＮ個の特徴点を選択する組み合わせは、（ｎＡｎＢ）Ｎ通りである。この中で、正しい特徴点ペアとなる組み合わせを、ｎｘＮとすると、確率ｗは、次式で表される。
【０１５５】
【数２３】
【０１５６】
よって、（２０）式が求められる。
【０１５７】
次に、特徴点数ｎの算出式について、詳述する。処理負荷は、特徴点数ｎが小さいほど小さい。一方、特徴点数ｎが小さすぎると、有効特徴点数Ｋが、ＲＡＮＳＡＣの閾値ＫＲより少なくなってしまう。したがって、有効特徴点数Ｋが閾値ＫＲとなるような特徴点数ｎが設定されればよい。
【０１５８】
即ち、特徴点数ｎの条件として、α×ｎが、ＲＡＮＳＡＣの閾値ＫＲより大きいことが挙げられる。よって、ｎの最小値は、ｎ＝ＫＲ／αである。マージンを考慮すると、特徴点数ｎは、ＫＲ／αにマージンが加えられた値として求められる。マージンは、次のように算出される。
【０１５９】
例えば、１つのコインを投げ、表が出る確率をα、裏が出る確率を１−αとすると、コインをｎ回投げた場合、表が出る回数Ｋ（ｎ）は、次の分布（二項分布）を持つ。
【０１６０】
【数２４】
【０１６１】
ここで、Ｋ（ｎ）≧ＫＲとなる確率Ｐは、次式で与えられる。
【０１６２】
【数２５】
【０１６３】
特徴点数ｎは、確率Ｐが所定値以上となるように設定されればよい。ここでは、分布Ｋ（ｎ）を、正規分布で近似する。即ち、二項分布Ｋ（ｎ）は、正規分布Ｎ（ｎα，ｎα（１−α））で近似される。したがって、特徴点数ｎは、中心μ、標準偏差σの正規分布を持つ確率変数が、ある確率で、ＫＲよりも大となるように設定される。ここで、マージンを、ｕσ（ｕは、正の実数）とすると、次式が成り立つ。
【０１６４】
【数２６】
【０１６５】
この式を解くと、（２１）式が求められる。なお、正規分布の±３σ内には、９９．７４％が含まれるので、例えばｕ＝３として、特徴点数ｎは求められる。
【０１６６】
また、画像Ａ及び画像Ｂのサイズが異なっており、かつ、特徴点密度が一定である場合、画像Ａ及び画像Ｂそれぞれの特徴点数ｎＡ及びｎＢは、次式で与えられる。
【０１６７】
【数２７】
【０１６８】
【数２８】
【０１６９】
図１６は、有効特徴点割合αと、ｕと、特徴点数ｎとの関係を示す図である。なお、図１６において、ＫＲは、６である。
図１６に示すように、特徴点数ｎは、αの大きさによって変化する。より具体的には、特徴点数ｎは、αが小さい場合には大きい値を設定され、αが大きい場合には小さい値を設定される。このように、特徴点数ｎには、有効特徴点割合αの値に応じて、適切な値が設定される。
【０１７０】
次に、上記のような画像処理プログラム３０の画像位置合わせ部４０による位置合わせ処理を説明する。なお、画像Ａ及び画像Ｂの特徴点数は一致する場合を例として示す。
図１７は、画像位置合わせ部４０による画像位置合わせ処理（Ｓ４０）のフローチャートを示す図である。
【０１７１】
図１７に示すように、ステップ４００（Ｓ４００）において、条件決定部４００は、入力されるＲＡＮＳＡＣの閾値ＫＲ及び有効特徴点割合αを受け付ける。条件決定部４００が閾値ＫＲ及び有効特徴点割合αを受け付けると、特徴点数算出部４１２は、閾値ＫＲ及び有効特徴点割合αに基づいて、画像Ａ及び画像Ｂの特徴点数ｎを算出する。
ステップ４０２（Ｓ４０２）において、試行回数算出部４１４は、有効特徴点割合α及び算出された特徴点数ｎに基づいて、試行回数Ｔを算出する。
【０１７２】
ステップ４０４（Ｓ４０４）において、特徴点抽出部４０２は、画像Ａ及び画像Ｂから、算出された特徴点数の特徴点を抽出する。
ステップ４０６（Ｓ４０６）において、特徴点ペア選択部４０４は、画像Ａ及び画像Ｂから抽出された特徴点からそれぞれＮ個の特徴点を選択し、Ｎ組の特徴点ペアを決定する。なお、Ｎの値は、特に限定されない。
【０１７３】
ステップ４０８（Ｓ４０８）において、変換係数算出部４０６は、決定された特徴点ペアを用いて変換係数を算出する。
ステップ４１０（Ｓ４１０）において、距離算出部４０８は、算出された変換式を用いて、画像のＡの所定の特徴点を変換する。
【０１７４】
ステップ４１２（Ｓ４１２）において、距離算出部４０８は、画像Ｂの特徴点と、変換後の画像Ａの特徴点との距離を算出し、この変換における有効特徴点数Ｋを算出する。
ステップ４１４（Ｓ４１４）において、判定部４１０は、算出された有効特徴点数Ｋが入力された閾値ＫＲ以上であるか否かを判定する。有効特徴点数Ｋが閾値ＫＲ以上である場合、判定部４１０は、変換係数を出力し、画像位置合わせ処理は終了する。
【０１７５】
有効特徴点Ｋが閾値ＫＲ未満である場合、ステップ４１６（Ｓ４１６）において、判定部４１０は、特徴点ペアの算出から有効特徴点数Ｋの判定までの試行が、算出された試行回数Ｔ回実施されたか否かを判定する。この試行がＴ回実施された場合、画像位置合わせ部４０は、処理を終了し、この試行がまだＴ回実施されていない場合、画像位置合わせ部４０は、Ｓ４０４の処理に戻る。
【０１７６】
試行回数がＴ回を超えて、画像位置合わせ処理が終了した場合、有効特徴点割合αの値が有効特徴点割合出力部３２により変更され、再度、画像位置合わせ処理（Ｓ４０）が実行される。この場合、新たな有効特徴点割合αに基づいて、特徴点数ｎ及び試行回数Ｔが、再度、算出される。
【０１７７】
図１８は、有効特徴点割合αと試行回数Ｔとの関係を示す図である。
図１８に示すように、本発明の実施形態に係る画像処理装置１０は、有効特徴点割合αに応じて、適切な試行回数Ｔを設定することができる。なお、図１８に示される結果及び非特許文献１に開示された手法における試行回数は、特徴点数ｎ＝１００、Ｎ＝２の条件で算出されたものである。
【０１７８】
図１９は、画像位置合わせ処理の実行回数と有効特徴点割合αとの関係を示す図である。
図１９に示すように、有効特徴点割合αは、実行回数が増えるごとに、小さくなる。図１９に示されるテーブルは、予め決められており、例えば、メモリ１０４及び記憶装置１０８の少なくともいずれかに記憶されている。有効特徴点割合出力部３２は、このテーブルに基づいて、有効特徴点割合αを、画像位置合わせ部４０に出力する。
【０１７９】
したがって、試行回数がＴ回を超えた場合、画像位置合わせ部４０の特徴点数算出部４１２及び試行回数算出部４１４は、減少された有効特徴点割合αを用いて算出を行う。予め決められた実行回数の上限（本例では、９回）が実行されたにもかかわらず、変換係数が求められなかった場合、画像位置合わせ部４０の判定部４１０は、画像Ａと画像Ｂとの間で重畳する画像部分がない旨の情報を出力する。なお、各実行回数における有効特徴点割合αの値及び上限回数は、本例に限定されない。
【０１８０】
図２０は、本発明の第４の実施形態に係る実施形態に係る画像処理装置１０の全体動作（Ｓ５０）を示すフローチャートである。なお、図２０に示された各処理のうち、図９に示された処理と実質的に同一のものには同一の符号が付されている。
図２０に示すように、画像処理装置１０が画像Ａ及び画像Ｂを受け付けると、ステップ５００（Ｓ５００）において、画像処理プログラム３０の有効特徴点割合出力部３２は、図１８に示されるテーブルに基づいて有効特徴点割合αの値を決定し、画像位置合わせ部４０に対して出力する。例えば、α＝０．５である。
【０１８１】
画像位置合わせ部４０は、有効特徴点割合αを受け付けると、画像位置合わせ処理（Ｓ４０）を実行する。
ステップ５０２（Ｓ５０２）において、画像位置合わせ部４０は、試行回数がＴ回を超えて画像位置合わせ処理を終了したか否かを判定する。画像位置合わせ部４０は、試行回数がＴ回を超えて画像位置合わせ処理を終了した場合にはＳ５０４の処理に進み、そうでない場合には、画像Ａと画像Ｂとの間の変換係数を、画像変換部２４に対して出力し、Ｓ２００の処理に進む。
【０１８２】
ステップ５０４（Ｓ５０４）において、有効特徴点割合出力部３２は、テーブルに基づいて、有効特徴点割合αの値を減少し、像位置合わせ部４０に対して出力する。画像位置合わせ部４０は、有効特徴点割合αを受け付けると、この有効特徴点割合αを用いて、画像位置合わせ処理（Ｓ４０）を、再度、実行する。
【０１８３】
Ｓ２００の処理では、画像変換部２４が、算出された変換係数を用いて画像Ａを変換し、Ｓ２０２の処理では、画像重ね合わせ部２６が、変換後の画像Ａと、画像Ｂとを重ね合わせて合成画像を生成して出力する。
【０１８４】
次に、本発明の第５の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、画像Ａの特徴点と画像Ｂの特徴点とをペア化して特徴点ペアを抽出し、抽出された特徴点ペアからＮ個の特徴点ペアを選択する点で、第４の実施形態に係る画像処理装置１０とは異なる。
【０１８５】
図２１は、本発明の第５の実施形態に係る画像位置合わせ部４２の機能構成を示す図である。なお、図２１に示された各構成のうち、図１５に示された構成と実質的に同一のものには同一の符号が付されている。
図２１に示すように、本実施形態に係る画像処理装置１０は、画像位置合わせ部４０が画像位置合わせ部４２に置き換えられた構成を有し、画像位置合わせ部４２は、条件決定部４００、特徴点抽出部４０２及び特徴点ペア選択部４０４が、それぞれ条件決定部４２０、特徴点ペア抽出部４２２及び特徴点ペア選択部４２４に置き換えられた構成を有する。また、条件決定部４２０は、特徴点ペア数算出部４２６及び試行回数算出部４２８を有する。
【０１８６】
画像位置合わせ部４２において、条件決定部４２０は、特徴点に関する閾値及び割合、即ちＲＡＮＳＡＣの閾値ＫＲ及び有効特徴点ペア割合βを入力し、画像Ａ及び画像Ｂから抽出される特徴点ペア数及び試行回数を決定する。
【０１８７】
条件決定部４２０において、特徴点ペア数算出部４２６は、特徴点ペア数を算出する。より具体的には、特徴点ペア数算出部４２６は、（２１）式を用いて、特徴点ペア数を算出する。なお、特徴点ペア数算出部４２６は、（２１）式に含まれるαを有効特徴点ペア割合βに置き換えて（２１）式を用いる。また、有効特徴点ペア割合βは、αと同様に、図１９に示されるように記憶されており、実行回数に応じて変化される。
【０１８８】
試行回数算出部４２８は、試行回数を算出する。より具体的には、試行回数算出部４２８は、次式を用いて、試行回数を算出する。
【０１８９】
【数２９】
【０１９０】
特徴点ペア抽出部４２２は、画像Ａ、画像Ｂ及び条件決定部４２０から出力される特徴点ペア数を入力し、画像Ａ及び画像Ｂから当該特徴点ペア数の特徴点ペアを抽出する。より具体的には、特徴点ペア抽出部４２２は、画像Ａ及び画像Ｂから特徴点を抽出し、画像Ａの特徴点の周辺領域の画素と、画像Ｂの特徴点の周辺領域の画素とを比較し、周辺領域の画素が互いに似ている特徴点を選択し、特徴点ペアとして抽出する。
【０１９１】
特徴点ペア選択部４２４は、特徴点ペア抽出部４２２により抽出された特徴点ペアからＮ個の特徴点ペアを選択する。
【０１９２】
図２２は、画像位置合わせ部４２による画像位置合わせ処理（Ｓ６０）のフローチャートを示す図である。なお、図２２に示された各処理のうち、図１７に示された処理と実質的に同一のものには同一の符号が付されている。また、画像位置合わせ部４２においては、画像位置合わせ部４０における有効特徴点数Ｋは、有効特徴点ペア数Ｋとして扱われる。
【０１９３】
図２２に示すように、ステップ６００（Ｓ６００）において、条件決定部４２０は、入力されるＲＡＮＳＡＣの閾値ＫＲ及び有効特徴点ペア割合βを受け付ける。条件決定部４２０が閾値ＫＲ及び有効特徴点ペア割合βを受け付けると、特徴点ペア数算出部４２６は、閾値ＫＲ及び有効特徴点ペア割合βに基づいて特徴点ペア数ｎを算出する。
ステップ６０２（Ｓ６０２）において、試行回数算出部４２８は、有効特徴点ペア割合βに基づいて試行回数Ｔを算出する。
【０１９４】
ステップ６０４（Ｓ６０４）において、特徴点ペア抽出部４２２は、画像Ａ及び画像Ｂから、算出された特徴点ペア数の特徴点ペアを抽出する。
ステップ６０６（Ｓ６０６）において、特徴点ペア選択部４２４は、抽出された特徴点ペアからＮ個の特徴点ペアを選択する。
さらに、Ｓ４０８〜Ｓ４１６の処理で、有効特徴点ペア数Ｋが算出及び判定され、変換係数が決定される。
【０１９５】
次に、本発明の第６の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、算出されたＴ回の試行を繰り返し、有効特徴点数Ｋを最大とする変換における変換係数を用いる点で、第４の実施形態に係る画像処理装置１０とは異なる。
【０１９６】
図２３は、本発明の第６の実施形態に係る画像位置合わせ部４４の機能構成を示す図である。なお、図２３に示された各構成のうち、図１５に示された構成と実質的に同一のものには同一の符号が付されている。
図２３に示すように、本実施形態に係る画像処理装置１０は、画像位置合わせ部４０が画像位置合わせ部４４に置き換えられた構成を有し、画像位置合わせ部４４は、判定部４１０が試行回数判定部４４２及び有効特徴点数判定部４４４に置き換えられた構成を有する。
【０１９７】
画像位置合わせ部４４において、試行回数判定部４４２は、特徴点ペアの選択回数が、試行回数算出部４１４により算出された試行回数Ｔを超えたか否かを判定し、特徴点ペアの選択回数が試行回数Ｔを超えた場合、その旨を有効特徴点数判定部４４４に対して出力し、そうでない場合、特徴点ペアの選択を再度実行する旨を特徴点ペア選択部４０４に対して出力する。
【０１９８】
有効特徴点数判定部４４４は、Ｔ回の試行における有効特徴点数Ｋを判定する。より具体的には、有効特徴点数判定部４４４は、Ｔ回の試行のうち、有効特徴点数Ｋを最大とする変換において用いられた変換係数を、画像変換部２４に対して出力する。
【０１９９】
図２４は、画像位置合わせ部４４による画像位置合わせ処理（Ｓ７０）のフローチャートを示す図である。なお、図２４に示された各処理のうち、図１７に示された処理と実質的に同一のものには同一の符号が付されている。
【０２００】
図２４に示すように、Ｓ４００〜Ｓ４１２の処理で、有効特徴点数Ｋが算出される。
ステップ７００（Ｓ７００）において、試行回数判定部４４２は、特徴点の選択が、試行回数算出部４１４により算出された試行回数Ｔを超えたか否かを判定する。特徴点の選択が試行回数Ｔを超えた場合、画像位置合わせ部４４はＳ７００の処理に進み、そうでない場合、画像位置合わせ部４４は、Ｓ４０４の処理に戻る。
【０２０１】
ステップ７０２（Ｓ７０２）において、試行回数判定部４４２は、特徴点の選択が試行回数Ｔを超えた旨を、有効特徴点数判定部４４４に対して出力する。有効特徴点数判定部４４４は、Ｔ回の試行のうち、有効特徴点数Ｋを最大とする変換において用いられた変換係数を出力する。
【０２０２】
次に、本発明の第７の実施形態に係る画像処理装置１０を説明する。
本実施形態に係る画像処理装置１０は、算出されたＴ回の試行を繰り返し、有効特徴点ペア数Ｋを最大とする変換における変換係数を用いる点で、第５の実施形態に係る画像処理装置１０とは異なる。
【０２０３】
図２５は、本発明の第７の実施形態に係る画像位置合わせ部４６の機能構成を示す図である。なお、図２５に示された各構成のうち、図２１又は図２３に示された構成と実質的に同一のものには同一の符号が付されている。
図２５に示すように、本実施形態に係る画像処理装置１０は、画像位置合わせ部４２が画像位置合わせ部４６に置き換えられた構成を有し、画像位置合わせ部４６は、判定部４１０が試行回数判定部４４２及び有効特徴点数判定部４４４に置き換えられた構成を有する。
【０２０４】
図２６は、画像位置合わせ部４６による画像位置合わせ処理（Ｓ８０）のフローチャートを示す図である。なお、図２６に示された各処理のうち、図１７、図２２又は図２４に示された処理と実質的に同一のものには同一の符号が付されている。
【０２０５】
図２６に示すように、Ｓ６００〜Ｓ４１２の処理で、有効特徴点ペア数Ｋが算出される。さらに、Ｓ７００の処理で、特徴点の選択が試行回数Ｔを超えたか否かが判定される。特徴点の選択が試行回数Ｔを超えた場合、ステップ８００（Ｓ８００）において、有効特徴点数判定部４４４は、Ｔ回の試行のうち、有効特徴点ペア数Ｋを最大とする変換において用いられた変換係数を出力する。
【図面の簡単な説明】
【０２０６】
【図１】射影変換を説明する図である。
【図２】２枚の画像が入力された場合、この２枚の画像を重ね合わせるための射影変換係数を求める手法を例示する図である。
【図３】本発明の実施形態に係る画像処理装置１０のハードウェア構成を示す図である。
【図４】本発明の第１の実施形態に係る画像処理装置１０により実行される画像処理プログラム２０の機能構成を示す図である。
【図５】画像位置合わせ部２２による画像位置合わせ処理の概要を説明する図である。
【図６】変換行列Ｈが平行移動では近似できない場合における画像位置合わせ部２２による画像位置合わせ処理の概要を説明する図である。
【図７】、本発明の第１の実施形態に係る画像処理装置１０における画像位置合わせ部２２の機能構成を示す図である。
【図８】本発明の第１の実施形態に係る画像処理装置１０における画像位置合わせ部２２による画像位置合わせ処理（Ｓ１０）のフローチャートを示す。
【図９】本発明の第１の実施形態に係る画像処理装置１０の全体動作（Ｓ２０）を示すフローチャートである。
【図１０】本発明の実施形態に係る画像処理装置１０により生成された合成画像を例示する図である。
【図１１】画像から抽出される特徴点数と試行回数との関係を示す図である。
【図１２】本発明の第２の実施形態に係る画像処理装置１０における画像位置合わせ部２８の機能構成を示す図である。
【図１３】本発明の第２の実施形態に係る画像処理装置１０における画像位置合わせ部２２による画像位置合わせ処理（Ｓ３０）のフローチャートを示す。
【図１４】本発明の第４の実施形態に係る画像処理装置１０により実行される画像処理プログラム３０の機能構成を示す図である。
【図１５】本発明の第４の実施形態に係る画像処理装置１０における画像位置合わせ部４０の機能構成を示す図である。
【図１６】有効特徴点割合αと、ｕと、特徴点数ｎとの関係を示す図である。
【図１７】本発明の第４の実施形態に係る画像処理装置１０における画像位置合わせ部４０による画像位置合わせ処理（Ｓ４０）のフローチャートを示す図である。
【図１８】有効特徴点割合αと試行回数Ｔとの関係を示す図である。
【図１９】画像位置合わせ処理の実行回数と有効特徴点割合αとの関係を示す図である。
【図２０】本発明の第４の実施形態に係る画像処理装置１０の全体動作（Ｓ５０）を示すフローチャートである。
【図２１】本発明の第５の実施形態に係る画像処理装置１０における画像位置合わせ部４２の機能構成を示す図である。
【図２２】本発明の第５の実施形態に係る画像処理装置１０における画像位置合わせ部４２による画像位置合わせ処理（Ｓ６０）のフローチャートを示す図である。
【図２３】本発明の第６の実施形態に係る画像処理装置１０における画像位置合わせ部４４の機能構成を示す図である。
【図２４】本発明の第６の実施形態に係る画像処理装置１０における画像位置合わせ部４４による画像位置合わせ処理（Ｓ７０）のフローチャートを示す図である。
【図２５】本発明の第７の実施形態に係る画像処理装置１０における画像位置合わせ部４６の機能構成を示す図である。
【図２６】本発明の第７の実施形態に係る画像処理装置１０における画像位置合わせ部４６による画像位置合わせ処理（Ｓ８０）のフローチャートを示す図である。
【符号の説明】
【０２０７】
１０ 画像処理装置
２０，３０ 画像処理プログラム
２２，４０，４２，４４，４６ 画像位置合わせ部
２４ 画像変換部
２６ 画像重ね合わせ部
３２ 有効特徴点割合出力部
１００ 制御装置
１０２ ＣＰＵ
１０４ メモリ
１０６ 通信装置
１０８ 記憶装置
１１０ ＵＩ装置
２２０ 特徴点抽出部
２２２ 特徴点ペア選択部
２２４ 変換係数算出部
２２６ 有効特徴点ペア探索部
２３０ 平行移動近似部
２８０ 拡縮変換近似部
２８２ 剛体変換近似部
２８４ 相似変換近似部
２８６ アフィン変換近似部
４００ 条件決定部
４０２ 特徴点抽出部
４０４ 特徴点ペア選択部
４０６ 変換係数算出部
４０８ 距離算出部
４１０ 判定部
４１２ 特徴点数算出部
４１４ 試行回数算出部
４２０ 条件決定部
４２２ 特徴点ペア抽出部
４２４ 特徴点ペア選択部
４２６ 特徴点ペア数算出部
４２８ 試行回数算出部
４４２ 試行回数判定部
４４４ 有効特徴点数判定部
【特許請求の範囲】
【請求項１】
第１の画像及び第２の画像から抽出される特徴点に基づいて、画像の変換手法を決定する変換手法決定手段と、
前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下となる特徴点の組に基づいて、前記変換手法決定手段が変換手法の決定を繰り返し行うように制御する制御手段と
を有する画像処理装置。
【請求項２】
前記変換手法決定手段は、射影変換で用いられる変換係数を決定する
請求項１に記載の画像処理装置。
【請求項３】
前記変換手法決定手段は、第１の画像及び第２の画像から抽出される特徴点の周辺画素の画素値にさらに基づいて、画像の変換手法を決定する
請求項１又は２に記載の画像処理装置。
【請求項４】
前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が、予め決められた値以上となるように制御する
請求項１乃至３のいずれかに記載の画像処理装置。
【請求項５】
前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が、予め決められた値未満である場合、前記変換手法決定手段が、当該特徴点の組とは異なる組を選択するように制御する
請求項４に記載の画像処理装置。
【請求項６】
前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が収束した場合、当該収束した状態における変換手法に関する情報を出力する
請求項１乃至５のいずれかに記載の画像処理装置。
【請求項７】
前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点の周辺画素の画素値と、第２の画像の特徴点の周辺画素の画素値とにさらに基づいて、記変換手法決定手段が変換手法の決定を繰り返し行うように制御する
請求項１乃至６のいずれかに記載の画像処理装置。
【請求項８】
特徴点に関する閾値及び割合に基づいて、第１の画像及び第２の画像から抽出される特徴点の数を算出する特徴点数算出手段と、
第１の画像及び第２の画像から抽出された前記特徴点数算出手段により算出された数の特徴点から選択される特徴点の組のうち有効とされる組の数が特徴点に関する閾値以上となるように画像の変換手法を決定する変換手法決定手段と
を有する画像処理装置。
【請求項９】
前記特徴点数算出手段は、特徴点に関する閾値を割合で乗じた値に所定値が加算された値を特徴点の数とする
請求項８に記載の画像処理装置。
【請求項１０】
前記変換手法決定手段は、変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が所定値以下である場合、当該特徴点の組は有効であると判定する
請求項８又は９に記載の画像処理装置。
【請求項１１】
前記特徴点数算出手段により算出された数に基づいて試行回数の上限を算出する試行回数算出手段をさらに有し、
前記変換手法決定手段は、前記試行回数算出手段により算出された試行回数の上限を超えない範囲で、変換手法を決定するための試行を繰り返す
請求項８乃至１０のいずれかに記載の画像処理装置。
【請求項１２】
前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、有効である特徴点の組が最大となる変換手法を選択する
請求項１１に記載の画像処理装置。
【請求項１３】
前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、第１の画像と第２の画像との間で重畳する画像部分がない旨の情報を出力する
請求項１１に記載の画像処理装置。
【請求項１４】
前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、減少された特徴点に関する割合を用いて試行を行う
請求項１１に記載の画像処理装置。
【請求項１５】
コンピュータを含む画像処理装置において、
第１の画像及び第２の画像から抽出される特徴点に基づいて、画像の変換手法を決定する変換手法決定ステップと、
前記決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下となる特徴点の組に基づいて、前記変換手法の決定を繰り返し行うように制御する制御ステップと
を前記画像処理装置のコンピュータに実行させるプログラム。
【請求項１６】
コンピュータを含む画像処理装置において、
特徴点に関する閾値及び割合に基づいて、第１の画像及び第２の画像から抽出される特徴点の数を算出する特徴点数算出ステップと、
第１の画像及び第２の画像から抽出された前記算出された数の特徴点から選択される特徴点の組のうち有効とされる組の数が特徴点に関する閾値以上となるように画像の変換手法を決定する変換手法決定ステップと
を前記画像処理装置のコンピュータに実行させるプログラム。
【請求項１】
第１の画像及び第２の画像から抽出される特徴点に基づいて、画像の変換手法を決定する変換手法決定手段と、
前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下となる特徴点の組に基づいて、前記変換手法決定手段が変換手法の決定を繰り返し行うように制御する制御手段と
を有する画像処理装置。
【請求項２】
前記変換手法決定手段は、射影変換で用いられる変換係数を決定する
請求項１に記載の画像処理装置。
【請求項３】
前記変換手法決定手段は、第１の画像及び第２の画像から抽出される特徴点の周辺画素の画素値にさらに基づいて、画像の変換手法を決定する
請求項１又は２に記載の画像処理装置。
【請求項４】
前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が、予め決められた値以上となるように制御する
請求項１乃至３のいずれかに記載の画像処理装置。
【請求項５】
前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が、予め決められた値未満である場合、前記変換手法決定手段が、当該特徴点の組とは異なる組を選択するように制御する
請求項４に記載の画像処理装置。
【請求項６】
前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下である特徴点の組の数が収束した場合、当該収束した状態における変換手法に関する情報を出力する
請求項１乃至５のいずれかに記載の画像処理装置。
【請求項７】
前記制御手段は、前記変換手法決定手段により決定される変換手法を適用されて変換された第１の画像の特徴点の周辺画素の画素値と、第２の画像の特徴点の周辺画素の画素値とにさらに基づいて、記変換手法決定手段が変換手法の決定を繰り返し行うように制御する
請求項１乃至６のいずれかに記載の画像処理装置。
【請求項８】
特徴点に関する閾値及び割合に基づいて、第１の画像及び第２の画像から抽出される特徴点の数を算出する特徴点数算出手段と、
第１の画像及び第２の画像から抽出された前記特徴点数算出手段により算出された数の特徴点から選択される特徴点の組のうち有効とされる組の数が特徴点に関する閾値以上となるように画像の変換手法を決定する変換手法決定手段と
を有する画像処理装置。
【請求項９】
前記特徴点数算出手段は、特徴点に関する閾値を割合で乗じた値に所定値が加算された値を特徴点の数とする
請求項８に記載の画像処理装置。
【請求項１０】
前記変換手法決定手段は、変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が所定値以下である場合、当該特徴点の組は有効であると判定する
請求項８又は９に記載の画像処理装置。
【請求項１１】
前記特徴点数算出手段により算出された数に基づいて試行回数の上限を算出する試行回数算出手段をさらに有し、
前記変換手法決定手段は、前記試行回数算出手段により算出された試行回数の上限を超えない範囲で、変換手法を決定するための試行を繰り返す
請求項８乃至１０のいずれかに記載の画像処理装置。
【請求項１２】
前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、有効である特徴点の組が最大となる変換手法を選択する
請求項１１に記載の画像処理装置。
【請求項１３】
前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、第１の画像と第２の画像との間で重畳する画像部分がない旨の情報を出力する
請求項１１に記載の画像処理装置。
【請求項１４】
前記変換手法決定手段は、試行回数が前記試行回数算出手段により算出された試行回数の上限を超えた場合、減少された特徴点に関する割合を用いて試行を行う
請求項１１に記載の画像処理装置。
【請求項１５】
コンピュータを含む画像処理装置において、
第１の画像及び第２の画像から抽出される特徴点に基づいて、画像の変換手法を決定する変換手法決定ステップと、
前記決定される変換手法を適用されて変換された第１の画像の特徴点と、第２の画像の特徴点との距離が閾値以下となる特徴点の組に基づいて、前記変換手法の決定を繰り返し行うように制御する制御ステップと
を前記画像処理装置のコンピュータに実行させるプログラム。
【請求項１６】
コンピュータを含む画像処理装置において、
特徴点に関する閾値及び割合に基づいて、第１の画像及び第２の画像から抽出される特徴点の数を算出する特徴点数算出ステップと、
第１の画像及び第２の画像から抽出された前記算出された数の特徴点から選択される特徴点の組のうち有効とされる組の数が特徴点に関する閾値以上となるように画像の変換手法を決定する変換手法決定ステップと
を前記画像処理装置のコンピュータに実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【公開番号】特開２００９−１２２８４３（Ｐ２００９−１２２８４３Ａ）
【公開日】平成２１年６月４日（２００９．６．４）
【国際特許分類】
【出願番号】特願２００７−２９４４９１（Ｐ２００７−２９４４９１）
【出願日】平成１９年１１月１３日（２００７．１１．１３）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２１年６月４日（２００９．６．４）
【国際特許分類】
【出願日】平成１９年１１月１３日（２００７．１１．１３）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]