画像変換パラメータ算出装置、画像変換パラメータ算出方法およびプログラム
【課題】画像変換を表す変換パラメータとして、適切な自由度の座標変換モデルにおける変換パラメータを求めることができる画像変換パラメータ算出装置を提供する。
【解決手段】パラメータ計算手段５は、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、画像間で対応する特徴点の組を用いて、座標変換を表す変換パラメータを計算する。モデル適切性判定手段６は、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定する。
【解決手段】パラメータ計算手段５は、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、画像間で対応する特徴点の組を用いて、座標変換を表す変換パラメータを計算する。モデル適切性判定手段６は、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像変換パラメータ算出装置、画像変換パラメータ算出方法および画像変換パラメータ算出プログラムに関する。
【背景技術】
【０００２】
同一対象物を撮影した場合であっても、カメラ位置のずれ等の原因により、画像内における物体の位置がずれることがある。このような場合に、一つの画像を変換して、その画像に含まれる物体の位置が他の画像におけるその物体の位置と同じになるようにするには、画像の位置合わせが必要となる。一方の画像を他方の画像に位置合わせする画像変換を表す変換パラメータは、画像間の特徴点の対応関係から求めることができる。
【０００３】
非特許文献１には、画像同士で対応する特徴点を抽出する方法が記載されている。非特許文献１内の「特徴点の追跡」という項目には、「Harrisのインタレストオペレータとテンプレートマッチングにより、前フレームの各特徴点について、現フレームにおける対応点を探索する。更に、ＲＡＮＳＡＣアルゴリズムを用いて、特徴点の誤対応を排除する。」と記載されている。換言すれば、特徴点の対応から画像変換を表す変換パラメータをＲＡＮＳＡＣアルゴリズムで求め、その画像変換に従わない特徴点を排除することが記載されている。
【０００４】
また、Harrisのインタレストオペレータについては、非特許文献２に記載されている。非特許文献２には、Harrisのインタレストオペレータが極値を与える点を、その値の大きい順に、指定した個数だけ特徴点として取り出すことが記載されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】池谷彰彦、外５名、「カメラパラメータ推定による紙面を対象とした超解像ビデオモザイキング」、電子情報通信学会論文誌、社団法人電子情報通信学会、Ｄ−ＩＩ、Ｖｏｌ．Ｊ８８−Ｄ−ＩＩ、Ｎｏ．８、ｐｐ．１４９０−１４９８、２００５年
【非特許文献２】金澤靖、金谷健一、「解説 コンピュータビジョンのための画像の特徴点の抽出」、電子情報通信学会誌、社団法人電子情報通信学会、Ｖｏｌ．８７、Ｎｏ．１２、ｐｐ．１０４３−１０４８、２００４年
【発明の概要】
【発明が解決しようとする課題】
【０００６】
前述のように、非特許文献１には、画像同士の間で対応する特徴点を抽出し、特徴点の対応から画像変換を表す変換パラメータをＲＡＮＳＡＣアルゴリズムで求め、その画像変換に従わない特徴点を排除することが記載されている。このような処理において、画像変換を表す変換パラメータを求める場合に、画像間における座標変換モデルを仮定し、その座標変換モデルにおける変換パラメータを求めることが考えられる。座標変換モデルとは、変換の自由度で分類した座標変換の種類である。
【０００７】
しかし、座標変換モデルとしては、変換の自由度が低いモデルや変換の自由度が高いモデル等、種々の座標変換モデルがある。変換の自由度が低い座標変換モデルの例として、平行移動のみを表すモデルがある。また、変換の自由度が高い座標変換モデルの例として、長方形を任意の四辺形に変換可能なモデル（例えば、ホモグラフィ変換）等がある。
【０００８】
変換パラメータを求める際に仮定する座標変換モデルにおける変換の自由度が実際の座標変換よりも低いと、画像内の特徴点座標を他方の画像の対応点座標に変換する変換パラメータを求めることができない。例えば、実際には、平行移動だけでなく回転変換も行わなければ、特徴点座標を対応点座標に変換できないにも関わらず、平行移動のみを表す座標変換モデルを用いると、正しく座標変換を行う変換パラメータを求めることができない。一方、変換パラメータを求める際に仮定する座標変換モデルにおける変換の自由度が実際の座標変換よりも高いと、特徴点座標を適切な対応点座標に変換できるものの、誤った特徴点の対応付けも許容する変換パラメータが求まってしまう。この場合には、非特許文献１に記載されている、画像変換に従わない特徴点を排除する処理を行おうとしても、排除すべき特徴点が排除されずに残ってしまうことになる。
【０００９】
従って、適切な座標変換モデルを選ばなければ、精度よく画像の位置合わせを行うことができない。しかし、画像のパターンは多様であり、処理対象となる画像に応じて適切な座標変換モデルを選ぶことは困難であった。
【００１０】
また、画像からの特徴点検出に関しては、以下のような問題があった。画像から特徴点を検出する方法として、Harrisのインタレストオペレータのような特徴点検出用オペレータを用いて画素に対する演算を行い、その演算結果に基づいて、特徴点を決定する方法がある。例えば、Harrisのインタレストオペレータを適用した場合では、演算結果が極大になる画素を特徴点とする。このとき、演算結果と閾値とを比較して、演算結果が閾値以上となっている等の条件を満たす画素を、特徴点として決定することが考えられる。例えば、演算結果が極大点となった画素のうち、演算結果が閾値以上となっている画素を特徴点として決定することが考えられる。しかし、このような特徴点の決め方では、十分な数の特徴点が得られず、その結果、画像の位置合わせを精度よく行えない場合が生じ得る。
【００１１】
この問題を解決するためには、非特許文献２に記載されているように、Harrisのインタレストオペレータが極大値を与える点を、その値の大きい順に、指定した個数だけ特徴点として取り出せばよい。しかし、この方法では、値のソーティング処理が必要となるために、特徴点検出処理が非効率的になってしまう。
【００１２】
そこで、本発明は、画像変換を表す変換パラメータとして、適切な自由度の座標変換モデルにおける変換パラメータを求めることができる画像変換パラメータ算出装置、画像変換パラメータ算出方法および画像変換パラメータ算出プログラムを提供することを目的とする。また、効率的な処理によって画像から所望の数の特徴点を検出して画像変換を表す変換パラメータを求めることができる画像変換パラメータ算出装置、画像変換パラメータ算出方法および画像変換パラメータ算出プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明による画像変換パラメータ算出装置は、入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出する特徴点検出手段と、第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定手段と、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算手段と、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定手段とを備え、特徴点検出手段が、画像内の各画素に対して特徴点検出用オペレータの演算を行うオペレータ演算手段と、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類手段と、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択手段を有し、対応特徴点特定手段が、特徴点選択手段が選択した特徴点の中から特徴点の組を特定することを特徴とする。
【００１４】
本発明による画像変換パラメータ算出方法は、入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出し、第１画像および第２画像の間で対応する特徴点の組を特定し、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算し、計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算した変換パラメータを第１画像から第２画像への変換パラメータとして確定し、入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出するときに、画像内の各画素に対して特徴点検出用オペレータの演算を行い、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類し、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数以上となったときに、選択済みの各区間に分類された特徴点を選択することを特徴とする。
【００１５】
本発明による画像変換パラメータ算出プログラムは、コンピュータに、入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出する特徴点検出処理、第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定処理、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算処理、および、パラメータ計算処理で計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定処理を実行させ、特徴点検出処理で、画像内の各画素に対して特徴点検出用オペレータの演算を行うオペレータ演算処理、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類処理、および、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択処理を実行させ、対応特徴点特定処理で、特徴点選択処理で選択された特徴点の中から特徴点の組を特定させることを特徴とする。
【発明の効果】
【００１６】
本発明によれば、画像変換を表す変換パラメータとして、適切な自由度の座標変換モデルにおける変換パラメータを求めることができる。また、効率的な処理によって画像から所望の数の特徴点を検出して画像変換を表す変換パラメータを求めることができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１の実施形態の画像変換パラメータ算出装置の例を示すブロック図である。
【図２】本発明の画像変換パラメータ算出装置の処理経過の例を示すフローチャートである。
【図３】本発明の第２の実施形態の画像変換パラメータ算出装置の例を示すブロック図である。
【図４】画素に対する特徴点検出用オペレータの演算結果を模式的に示す説明図である。
【図５】図４に示す演算結果の変化において演算結果が極大となる箇所を示す説明図である。
【図６】演算結果の値がとり得る範囲を分割した各区間の例を示す。
【図７】特徴点の分類を模式的に示す説明図である。
【図８】特徴点テーブルの例を示す説明図である。
【図９】第２の実施形態における特徴点検出処理の処理経過の例を示すフローチャートである。
【図１０】本発明の第３の実施形態の特徴点検出装置の例を示すブロック図である。
【図１１】本発明の最小構成の例を示すブロック図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施形態を図面を参照して説明する。
【００１９】
実施形態１．
図１は、本発明の第１の実施形態の画像変換パラメータ算出装置の例を示すブロック図である。第１の実施形態の画像変換パラメータ算出装置１は、２つの画像が入力されると、一方の画像（Ａとする。）に含まれる物体の位置が他の画像（Ｂとする。）におけるその物体の位置と同じになるように、画像Ａ内の画素の座標を変換する変換パラメータを算出する。入力される画像Ａ，Ｂは、画像の位置合わせの対象となる画像である。例えば、動画における連続するフレーム等が、画像Ａ，Ｂとして入力される。本発明の画像変換パラメータ算出装置１は、特徴点検出手段２と、対応特徴点特定手段３と、モデル選択手段４と、パラメータ計算手段５と、モデル適切性判定手段６とを備える。
【００２０】
特徴点検出手段２は、入力された画像Ａ，Ｂから、それぞれ特徴点を検出する。すなわち、画像Ａ，Ｂ内において特徴点となる画素を判定する。特徴点検出手段２は、各画像の個々の画素に対して、特徴点検出用オペレータの演算を行い、その演算結果として得られる値に基づいて、特徴点となる画素を判定すればよい。以下、特徴点検出用オペレータとして、Harrisのインタレストオペレータを用いる場合を例にして説明するが、特徴点検出用オペレータは、Harrisのインタレストオペレータに限定されない。Harrisのインタレストオペレータを用いる場合、特徴点検出手段２は、画像内の画素毎に、Harrisのインタレストオペレータの演算を行い、演算結果が極大となる画素を特徴点として判定すればよい。
【００２１】
対応特徴点特定手段３は、画像Ａから検出された特徴点群と、画像Ｂから検出された特徴点群とから、画像Ａ，Ｂ間で対応する特徴点の組を特定する。対応特徴点特定手段３は、例えば、画像Ａから検出された特徴点座標を中心とする局所領域内のパターンと、画像Ｂから検出された特徴点座標を中心とする局所領域内のパターンとの類似度を計算し、類似度が高いと判定される特徴点同士を対応付ければよい。あるいは、他の方法で特徴点同士を対応づけてもよい。
【００２２】
パラメータ計算手段５は、画像Ａの各特徴点の座標を、画像Ｂ内で対応する特徴点座標またはその近傍の点の座標に変換する変換パラメータを計算する。この変換パラメータは、画像Ａを画像Ｂに合わせるように画像Ａの画素の座標を変換するための変換パラメータの候補である。
【００２３】
パラメータ計算手段５は、モデル選択手段４が選択する座標変換モデルにおける変換パラメータを計算することによって、画像Ａの各特徴点の座標を、画像Ｂ内で対応する特徴点座標またはその近傍の点の座標に変換する変換パラメータを計算する。この計算では、パラメータ計算手段５は、選択された座標変換モデルにおける変換パラメータを、対応する特徴点同士の組を用いて、例えば、ＲＡＮＳＡＣ（RANdom SAmple Consensus）アルゴリズムによって計算すればよい。
【００２４】
モデル選択手段４は、パラメータ計算手段５が変換パラメータを計算する際の座標変換モデルを選択する。既に説明したように、座標変換モデルとは、変換の自由度で分類した座標変換の種類である。変換の自由度は、パラメータの数で表される。すなわち、変換の自由度が高くなるほど、変換パラメータの数は多くなり、変換の自由度が低いほど、変換パラメータの数は少なくなる。以下、座標変換モデルの例を示す。以下の説明において、ａｎ（ｎは自然数）は、座標変換モデルにおける変換パラメータを表すものとする。
【００２５】
座標変換モデルの第１の例として、座標を平行移動させる変換（以下、平行移動変換と記す。）が挙げられる。変換前の座標を（ｘ，ｙ）とし、変換後の座標を（ｘ’，ｙ’）とすると、平行移動変換は、以下に示す式（１）および式（２）で表すことができる。
【００２６】
ｘ’＝ｘ＋ａ１ 式（１）
ｙ’＝ｙ＋ａ２ 式（２）
【００２７】
平行移動変換で用いる変換パラメータは、ａ１，ａ２の２個であり、平行移動変換の自由度は２である。
【００２８】
座標変換モデルの第２の例として、アフィン変換が挙げられる。変換前の座標を（ｘ，ｙ）とし、変換後の座標を（ｘ’，ｙ’）とすると、アフィン変換は、以下に示す式（３）および式（４）で表すことができる。
【００２９】
ｘ’＝ａ１ｘ＋ａ２ｙ＋ａ３ 式（３）
ｙ’＝ａ４ｘ＋ａ５ｙ＋ａ６ 式（４）
【００３０】
アフィン変換で用いる変換パラメータは、ａ１〜ａ６の６個であり、アフィン変換の自由度は６である。
【００３１】
座標変換モデルの第３の例として、ホモグラフィ（Homography）変換が挙げられる。ホモグラフィ変換では、長方形を任意の四辺形に変換可能である。変換前の座標を（ｘ，ｙ）とし、変換後の座標を（ｘ’，ｙ’）とすると、ホモグラフィ変換は、以下に示す式（５）および式（６）で表すことができる。
【００３２】
ｘ’＝（ａ１ｘ＋ａ２ｙ＋ａ３）／（ａ７ｘ＋ａ８ｙ＋１） 式（５）
ｙ’＝（ａ４ｘ＋ａ５ｙ＋ａ６）／（ａ７ｘ＋ａ８ｙ＋１） 式（６）
【００３３】
ホモグラフィ変換で用いる変換パラメータは、ａ１〜ａ８の８個であり、ホモグラフィ変換の自由度は８である。
【００３４】
本例では、座標変換モデルの例を３つ挙げたが、モデル選択手段４は、他の座標変換モデルを選択してもよい。
【００３５】
本実施形態では、モデル選択手段４は、変換の自由度が少ない順に、座標変換モデルを選択する。以下の説明では、モデル選択手段４が、自由度２，６，８の順に座標変換モデルを選択する場合を例にして説明する。具体的には、平行移動変換、アフィン変換、ホモグラフィ変換の順に座標変換モデルを選択する場合を例に説明する。
【００３６】
モデル選択手段４が平行移動変換を選択した場合、パラメータ計算手段５は、式（１）および式（２）におけるａ１，ａ２を計算する。また、モデル選択手段４がアフィン変換を選択した場合、パラメータ計算手段５は、式（３）および式（４）におけるａ１〜ａ６を計算する。また、モデル選択手段４がホモグラフィ変換を選択した場合、パラメータ計算手段５は、式（５）および式（６）におけるａ１〜ａ８を計算する。
【００３７】
モデル適切性判定手段６は、モデル選択手段４によって選択された座標変換モデルが適切であるか否かを判定する。モデル適切性判定手段６は、パラメータ計算手段５が計算した変換パラメータを用いて画像Ａ内の特徴点の座標を変換し、その特徴点に対応する画像Ｂ内の特徴点の座標と、変換によって得た座標との差（例えば、後述の平均再投影誤差）を計算する。モデル適切性判定手段６は、その差が大きければ、選択された座標変換モデルは画像Ａから画像Ｂへの変換として適切でないと判定する。また、その差が小さければ、選択された座標変換モデルは画像Ａから画像Ｂへの変換として適切であり、その座標変換モデルに基づいて計算された変換パラメータも画像Ａから画像Ｂへの変換パラメータとして適切であると判定する。なお、画像Ａ内の特徴点に対応する画像Ｂ内の特徴点の座標と、画像Ａ内の特徴点を変換して得た座標との差が大きいか否かは、予め定めた閾値との大小関係に基づいて判定すればよい。
【００３８】
特徴点検出手段２、対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５、およびモデル適切性判定手段６は、例えば、画像変換パラメータ算出プログラムに従って動作するコンピュータのＣＰＵによって実現される。例えば、コンピュータのプログラム記憶手段（図示せず）に記憶された画像変換パラメータ算出プログラムをＣＰＵが読み込み、ＣＰＵがそのプログラムに従って、特徴点検出手段２、対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５、およびモデル適切性判定手段６として動作する。また、特徴点検出手段２、対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５、およびモデル適切性判定手段６がそれぞれ別々の回路として実現されていてもよい。
【００３９】
次に、動作について説明する。
図２は、本発明の画像変換パラメータ算出装置の処理経過の例を示すフローチャートである。なお、初期状態において、モデル選択手段４は、変換の自由度が２である平行移動変換を選択しているものとする。
【００４０】
画像Ａ，Ｂが入力されると、特徴点検出手段２は、入力された画像Ａ，Ｂそれぞれから特徴点を検出する（ステップＳ１）。画像Ａから特徴点を検出する場合、特徴点検出手段２は、画像Ａの各画素に対して、Harrisのインタレストオペレータの演算を行い、演算結果が極大となる画素を特徴点とする。特徴点検出手段２は、画像Ｂからも同様に特徴点を検出する。ここでは、Harrisのインタレストオペレータを用いて特徴点を検出する場合を例示したが、本実施形態では、特徴点検出手段２の特徴点検出方法は、特に限定されない。
【００４１】
次に、対応特徴点特定手段３は、画像Ａから検出された特徴点群と、画像Ｂから検出された特徴点群とから、画像間で対応する特徴点の組を特定する（ステップＳ２）。ステップＳ２において、対応特徴点特定手段３は、一方の画像（画像Ａ）の特徴点を選択し、もう一方の画像（画像Ｂ）からその特徴点に対応する特徴点（以下、対応点と記す。）の候補を選択する。さらに、対応特徴点特定手段３は、画像Ａの特徴点座標を中心とする局所領域内のパターンを画像Ａから抽出し、同様に、画像Ｂからも選択した対応点の候補の座標を中心とする局所領域内のパターンを抽出する。対応特徴点特定手段３は、画像Ａから抽出したパターンと画像Ｂから抽出したパターンの組み合わせにおけるＳＡＤ（Sum of Absolute Difference）値を計算する。ＳＡＤ値とは、２つのパターンの対応する画素毎に、画素値の差の絶対値を計算して、画素毎に計算した画素値の差の絶対値の総和として得られる値である。対応特徴点特定手段３は、画像Ｂの対応点候補を変更しながら、対応点候補毎にＳＡＤ値を計算し、ＳＡＤ値が最小となる対応点を、画像Ａから選択した特徴点に対応する画像Ｂ内の特徴点として決定する。対応特徴点特定手段３は、この動作を繰り返し、画像Ａ内の特徴点と、画像Ｂ内の特徴点とを対応付ければよい。ここではＳＡＤ値に基づいて特徴点を対応付ける場合を例にして説明したが、対応特徴点特定手段３は、他の方法で画像間の特徴点の対応付けを行ってもよい。
【００４２】
次に、パラメータ計算手段５は、ステップＳ２で対応付けられた特徴点同士の組を用いて、選択されている座標変換モデルにおける変換パラメータの値を計算する（ステップＳ３）。本例では、初期状態で、平行移動変換が選択されている。従って、最初にステップＳ３に移行した場合、パラメータ計算手段５は、式（１）および式（２）におけるａ１，ａ２を計算すればよい。
【００４３】
また、パラメータ計算手段５は、ステップＳ３において、例えば、ＲＡＮＳＡＣアルゴリズムにより変換パラメータを計算すればよい。以下、ＲＡＮＳＡＣアルゴリズムによる変換パラメータの計算例を示す。
【００４４】
パラメータ計算手段５は、対応する特徴点同士の組の中から、選択されている座標変換モデルにおける変換パラメータの値を計算可能な特徴点同士の組を任意に選択し、その特徴点同士の組から変換パラメータの値を計算する。パラメータ計算手段５は、この特徴点の組の選択と、変換パラメータの値の計算を複数回繰り返す。選択した特徴点の組から変換パラメータを計算する際には、パラメータ計算手段５は、画像Ａの特徴点の座標を変換前の座標とし、画像Ｂの特徴点の座標を変換後の座標として、選択されている座標変換モデルの変換式にその座標代入し、変換式に含まれる各パラメータａｎについての方程式を解けばよい。
【００４５】
特徴点の組を変えて、変換パラメータの値を計算することを繰り返すことにより、変換パラメータの値が複数得られる。パラメータ計算手段５は、計算した各変換パラメータの値について、対応特徴点特定手段３によって対応付けられた全ての特徴点の組を用いて評価し、選択されている座標変換モデルにおける変換パラメータとして適切なパラメータを決定する。この評価では、パラメータ計算手段５は、対応特徴点特定手段３によって対応付けられた特徴点の各組における画像Ａの特徴点の座標を変換前の座標とし、計算した変換パラメータ毎に、変換後の座標値を計算する。そして、パラメータ計算手段５は、変換パラメータ毎に、計算した変換後の座標群の中から、画像Ａの特徴点に対応する画像Ｂの特徴点の座標との距離が所定の閾値未満となる座標の個数を計数する。パラメータ計算手段５は、その計数結果が最大となる変換パラメータを、選択されている座標変換モデルでの適切なパラメータと決定する。換言すれば、パラメータ計算手段５は、変換パラメータ毎に、ステップＳ２で対応付けられた特徴点の全組に関して、画像Ａの特徴点座標を変換し、変換後の座標と、変換元の特徴点に対応する画像Ｂの特徴点の座標との距離が閾値未満となっている特徴点の組の数を計数し、その計数結果が最大となる変換パラメータを、選択されている座標変換モデルでの適切なパラメータと決定する。
【００４６】
以下、具体例を示す。ここでは、平行移動変換が選択されているものとする。この場合、特徴点同士の一つの組から、平行移動変換の変換式である式（１）および式（２）における変換パラメータａ１，ａ２を計算することができる。よって、パラメータ計算手段５は、特徴点同士の組を任意に１組選択し、選択した１組から式（１）および式（２）における変換パラメータａ１，ａ２を計算する処理を繰り返す。この結果、１つめの組からは“ａ１＝ｐ１，ａ２＝ｑ１”が得られ、２つ目の組からは“ａ１＝ｐ２，ａ２＝ｑ２”が得られるというように、複数の変換パラメータが得られたとする。パラメータ計算手段５は、対応特徴点特定手段３によって対応付けられた全ての特徴点の組における画像Ａの特徴点の座標を、“ａ１＝ｐ１，ａ２＝ｑ１”を用いて変換した場合の変換結果を計算する。そして、パラメータ計算手段５は、特徴点の各組における画像Ａの特徴点の座標を変換パラメータ“ａ１＝ｐ１，ａ２＝ｑ１”で変換して得た座標群の中から、画像Ａの特徴点に対応する画像Ｂの特徴点の座標との距離が所定の閾値未満となる座標の個数を計数する。“ａ１＝ｐ２，ａ２＝ｑ２”等の他の変換パラメータに関しても同様の処理を行う。パラメータ計算手段５は、求めた計数結果が最大となる変換パラメータを、平行移動変換での適切な変換パラメータであると決定する。
【００４７】
なお、上記の例は、ＲＡＮＳＡＣアルゴリズムによる変換パラメータ計算の一例であり、変換パラメータの計算方法は、上記の例に限定されない。
【００４８】
例えば、上記の例では、対応特徴点特定手段３によって対応づけられた特徴点の全組における画像Ａの特徴点の座標の変換結果のうち、変換元の特徴点に対応する画像Ｂの特徴点の座標との距離が閾値未満となっている座標の数を計数し、その計数結果が最大となる変換パラメータを、適切な変換パラメータであると決定する場合を示した。このように変換パラメータを決定するのではなく、計数結果が大きい順に所定数の変換パラメータを選び、その各変換パラメータ導出時に選択していた各特徴点の組を用いて、最小二乗法により変換パラメータを決定してもよい。
【００４９】
また、例えば、特徴点の組を変えて、変換パラメータの値を計算することを繰り返す際にも、変換パラメータの値を計算するために必要な最小限の数よりも多くの数の組を選択し、それらの組から最小二乗法により変換パラメータの値を計算してもよい。
【００５０】
選択されている座標変換モデルでの適切な変換パラメータを計算する処理（ステップＳ３）の後、モデル適切性判定手段６は、ステップＳ３で決定した変換パラメータにおける平均再投影誤差を計算する（ステップＳ４）。
【００５１】
ここで、平均再投影誤差について説明する。ステップＳ２で対応付けられた特徴点の組のうち、画像Ａ側の特徴点の座標を（ｘｉ，ｙｉ）とし、画像Ｂ側の特徴点の座標を（ｘ’ｉ，ｙ’ｉ）とする。また、画像Ａの特徴点の座標（ｘｉ，ｙｉ）を、ステップＳ３で決定された変換パラメータを用いて変換した結果を（Ｘｉ，Ｙｉ）とする。また、テップＳ２で対応付けられた特徴点の組の総数をｍ個とする。このとき、平均再投影誤差をＥとすると、平均再投影誤差Ｅは、以下に示す式（７）として定義される。
【００５２】
【数１】
【００５３】
平均再投影誤差Ｅは、画像Ａ内の特徴点に対応する画像Ｂ内の特徴点の座標と、その画像Ａ内の特徴点の座標を変換パラメータで変換した座標との差を、画像Ａ内の特徴点毎に求め、その平均を計算した結果の値である。平均再投影誤差Ｅは、画像Ａ内の特徴点に対応する画像Ｂ内の特徴点の座標と、その画像Ａ内の特徴点の座標を変換パラメータで変換した座標との差を表した値であるということができる。
【００５４】
ステップＳ４の次に、モデル適切性判定手段６は、選択されている座標変換モデルが画像Ａから画像Ｂへの変換として適切か否かを判定する（ステップＳ５）。ステップＳ５では、モデル適切性判定手段６は、平均再投影誤差Ｅが、予め定められた閾値（以下、誤差閾値と記す。）以下であるか否かを判定することによって、選択されている座標変換モデルが適切か否かを判定する。
【００５５】
平均再投影誤差Ｅが誤差閾値より大きいということは、選択されている座標変換モデルに基づいてステップＳ３で決定した変換パラメータは、画像Ａから画像Ｂへの変換を適切に表現できていないことになる。よって、モデル適切性判定手段６は、平均再投影誤差Ｅが誤差閾値より大きい場合には、選択されている座標変換モデルが適切でないと判定する（ステップＳ５のＮｏ）。逆に、平均再投影誤差Ｅが誤差閾値以下であるということは、画像Ａ内の特徴点に対応する画像Ｂ内の特徴点の座標と、その画像Ａ内の特徴点の座標を変換パラメータで変換した座標との差が十分に小さく、選択されている座標変換モデルが適切であり、その変換モデルに基づいてステップＳ３で計算された変換パラメータも、画像Ａから画像Ｂへの変換を適切に表現できているということができる。よって、モデル適切性判定手段６は、平均再投影誤差Ｅが誤差閾値以下である場合には、選択されている座標変換モデルが適切であると判定する（ステップＳ５のＹｅｓ）。
【００５６】
選択されている座標変換モデルが適切でない場合（すなわち、平均再投影誤差Ｅが誤差閾値より大きい場合）、モデル選択手段４は、選択している座標変換モデルよりも自由度が高い座標変換モデルを新たに選択する（ステップＳ６）。すなわち、選択する座標変換モデルを更新する。例えば、平行移動変換を選択している状態でステップＳ６に移行した場合、モデル選択手段４は、より自由度の高いアフィン変換を選択する。また、アフィン変換を選択している状態でステップＳ６に移行した場合、モデル選択手段４は、より自由度の高いホモグラフィ変換を選択する。
【００５７】
ただし、予め選択順を定めた座標変換モデルで、最も自由度が高い座標変換モデルを既に選択している場合には、より自由度が高い座標変換モデルを選択できない。この場合（ステップＳ７のＮｏ）、ステップＳ８に移行する。
【００５８】
また、ステップＳ６でより自由度が高い変換モデルを選択した場合には（ステップＳ７のＹｅｓ）、画像変換パラメータ算出装置は、画像Ａ，Ｂに対して、ステップＳ１以降の処理を繰り返す。
【００５９】
ステップＳ６でアフィン変換が新たに選択され、ステップＳ１から処理をやり直した場合におけるステップＳ３の処理の例を示す。この場合、特徴点同士の３つの組から、式（３）および式（６）の方程式を６個定め、その方程式から変換パラメータａ１〜ａ６を計算することができる。よって、パラメータ計算手段５は、特徴点同士の組を任意に３組選択し、選択した３組から式（３）および式（４）における変換パラメータａ１〜ａ６を計算することを繰り返す。この結果、１つめの組からは“ａ１＝ｐ１，ａ２＝ｑ１，ａ３＝ｒ１，ａ４＝ｓ１，ａ５＝ｔ１，ａ６＝ｕ１” が得られ、２つ目の組からは“ａ１＝ｐ２，ａ２＝ｑ２，ａ３＝ｒ２，ａ４＝ｓ２，ａ５＝ｔ２，ａ６＝ｕ２” が得られるというように、複数の変換パラメータが得られたとする。パラメータ計算手段５は、対応特徴点特定手段３によって対応付けられた全ての特徴点の組における画像Ａの特徴点の座標を、“ａ１＝ｐ１，ａ２＝ｑ１，ａ３＝ｒ１，ａ４＝ｓ１，ａ５＝ｔ１，ａ６＝ｕ１”を用いて変換した場合の変換結果を計算する。そして、パラメータ計算手段５は、特徴点の各組における画像Ａの特徴点の座標を変換パラメータ“ａ１＝ｐ１，ａ２＝ｑ１，ａ３＝ｒ１，ａ４＝ｓ１，ａ５＝ｔ１，ａ６＝ｕ１”で変換して得た座標群の中から、画像Ａの特徴点に対応する画像Ｂの特徴点の座標との距離が所定の閾値未満となる座標の個数を計数する。“ａ１＝ｐ２，ａ２＝ｑ２，ａ３＝ｒ２，ａ４＝ｓ２，ａ５＝ｔ２，ａ６＝ｕ２” 等の他の変換パラメータに関しても同様の処理を行う。パラメータ計算手段５は、求めた計数結果が最大となる変換パラメータを、アフィン変換での適切な変換パラメータであると決定する。
【００６０】
ステップＳ６でホモグラフィ変換が新たに選択された後に、ステップＳ１から処理をやり直してステップＳ３に移行した場合にも、同様の処理を行って、ホモグラフィ変換での適切な変換パラメータａ１〜ａ８の値を決定すればよい。
【００６１】
なお、既に説明したように、上記の例は、ＲＡＮＳＡＣアルゴリズムによる変換パラメータ計算の一例であり、変換パラメータの計算方法は、上記の例に限定されない。
【００６２】
ステップＳ６で新たに座標変換パラメータを選択し、ステップＳ１以降の処理を繰り返すループ処理において、モデル適正判定手段６が、選択されている座標変換モデルが画像Ａから画像Ｂへの変換として適切と判定したならば（ステップＳ５のＹｅｓ）、モデル適正判定手段６は、その直前のステップＳ４で計算された変換パラメータを、画像Ａから画像Ｂへの変換を表現した変換パラメータとして確定する（ステップＳ８）。
【００６３】
また、予め定めた座標変換モデルのうち、最も自由度が高い座標変換モデルを選択している場合に、ステップＳ６に移行し、ステップＳ６で次の座標変換モデルを選択できない状態となったときにも（ステップＳ７のＮｏ）、モデル適正判定手段６は、その直前のステップＳ４で計算された変換パラメータを、画像Ａから画像Ｂへの変換を表現した変換パラメータとして確定する（ステップＳ８）。
【００６４】
本実施形態によれば、モデル選択手段４が、変換の自由度が低い方から順に座標変換モデルを選択し、その座標変換モデルにおける変換式のパラメータをパラメータ計算手段５が計算する。そして、モデル適切性判定手段６が、画像Ａ内の特徴点に対応する画像Ｂ内の特徴点の座標と、その画像Ａ内の特徴点の座標を変換パラメータで変換した座標との差の大きさに応じて、選択されている座標変換モデルが画像Ａから画像Ｂへの変換として適切か否かを判定し、適切でなければ、モデル選択手段４がより自由度の大きい座標変換モデルを選択する。このような構成により、処理対象とする画像Ａ，Ｂに対して適切かつ必要最小限の自由度を持った座標変換モデルを特定して、その座標変換モデルにおけるパラメータとして、画像Ａから画像Ｂへの適切な変換パラメータを得ることができる。また、その結果、画像Ａから画像Ｂへの画像変換（位置合わせ）の精度を向上させることができる。
【００６５】
なお、図２では、ステップＳ６でより自由度が高い変換モデルを選択した場合に（ステップＳ７のＹｅｓ）、ステップＳ１以降の処理を繰り返す場合を示しているが、ステップＳ３以降の処理を繰り返してもよい。すなわち、ステップＳ１，Ｓ２を再度実行して、特徴点検出および特徴点の対応付けをやり直してもよいし、あるいは、既に対応付けの済んだ特徴点の組を用いてステップＳ３から処理をやり直してもよい。ステップＳ３から処理をやり直す場合には、新たに選択された座標変換モデルに関して変換パラメータを計算するときに、以前に選択された座標変換モデルに関して変換パラメータを計算する際に既に対応付けられていた特徴点の組を用いることになる。
【００６６】
また、上記の実施形態では、平行移動変換、アフィン変換、ホモグラフィ変換の順に選択する場合を示したが、選択対象となる座標変換モデルの組み合わせは、上記の３つの変換の組み合わせに限定されない。例えば、アフィン変換、ホモグラフィ変換の順に選択する構成であってもよい。また、平行移動変換、アフィン変換、ホモグラフィ変換以外の座標変換モデルを選択してもよい。
【００６７】
また、上記の実施形態では、モデル選択手段４が座標変換モデルを１つずつ選択し、選択された座標変換モデル毎にループ処理を実行する場合を示した。このようなループ処理を実行するのではなく、各座標変換モデルに対する処理を並列に行ってもよい。例えば、ステップＳ１，Ｓ２を実行した後、パラメータ計算手段５が、平行移動変換に関する変換パラメータ計算と、アフィン変換に関する変換パラメータ計算と、ホモグラフィ変換に関する変換パラメータ計算とをそれぞれ並列に行ってもよい。すなわち、複数種類の座標変換モデルに対するステップＳ３の処理を並列に行ってもよい。その後、モデル適切性判定手段６が、座標変換モデル毎に、平均再投影誤差の計算を行い（ステップＳ４）、座標変換モデルの適切性の判定（ステップＳ５）を行う。そして、ステップＳ５で、平均再投影誤差が誤差閾値以下となっている座標変換モデルを適切な座標変換モデルと決定し、その座標変換モデルに関して計算した変換パラメータを、画像Ａから画像Ｂへの変換パラメータとして確定する。平均再投影誤差が誤差閾値以下となっている座標変換モデルが複数存在する場合には、その中で自由度が最も低い座標変換モデルを、適切な座標変換モデルとして決定すればよい。また、平均再投影誤差が誤差閾値以下となっている座標変換モデルが存在しない場合には、予め定めた座標変換モデルのうち、自由度が最も高い座標変換モデルを適切な変換モデルとして決定すればよい。
【００６８】
実施形態２．
第２の実施形態の画像変換パラメータ算出装置は、画像から特徴点を検出する際に、予め定められた所定数以上の特徴点を検出することにより、十分な数の特徴点を確保する。
【００６９】
図３は、本発明の第２の実施形態の画像変換パラメータ算出装置の例を示すブロック図である。第１の実施形態と同様の構成要素については、図１と同一の符号を付し、詳細な説明を省略する。第２の実施形態の画像変換パラメータ算出装置１０は、特徴点検出手段２０と、対応特徴点特定手段３と、モデル選択手段４と、パラメータ計算手段５と、モデル適切性判定手段６とを備える。対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５およびモデル適切性判定手段６は、第１の実施形態と同様である。
【００７０】
特徴点検出手段２０は、入力された各画像Ａ，Ｂから特徴点を検出する。第１の実施形態では、特徴点検出方法は特に限定していない。これに対し、第２の実施形態において、特徴点検出手段２０は、画像の個々の画素に対して、特徴点検出用オペレータの演算を行う。そして、特徴点検出手段２０は、画像の画素に対して、ラスタスキャン順に、特徴点検出用オペレータの演算結果が極大になっているかを判定し、極大になっている画素を分類する。この分類処理では、特徴点検出手段２０は、特徴点検出用オペレータの演算結果として計算され得る最小値から最大値までの範囲を分割した各区間のうちのどの区間に、画素に対する演算結果が属するかを判定して、画素をその区間に分類する。特徴点検出手段２０は、演算結果が極大となる各画素に対してこの分類処理を行った後、演算結果のとり得る最大値に近い方の区間から順に区間を選択し、選択した区間に分類した画素を累積加算していく。その累積加算結果が、所定数数以上になった時点で区間の選択を停止する。この結果、特徴点検出手段２０は、演算結果に対するソーティング処理を行うことなく、所定数以上の特徴点を得ることができる。
【００７１】
図４は、画素に対する特徴点検出用オペレータの演算結果を模式的に示す説明図である。図４に示す横軸は、１つの画像内の個々の画素の識別情報（例えば、座標値）を示す。また、縦軸は、各画素に対する特徴点検出用オペレータの演算結果の値を示す。従って、図４では、画素毎の特徴点検出用オペレータの演算結果の変化を模式的に表している。図５は、図４に示す演算結果の変化において演算結果が極大となる箇所を示す説明図である。図５では、演算結果が極大となる箇所を丸印で囲んで示している。特徴点検出手段２０は、ラスタスキャン順に、演算結果がこのような極大となる画素であるかを判定し、演算結果が極大となる画素（特徴点）に対して、上述のように分類処理を行う。そして、特徴点の分類に用いた区間を順に選択していくことによって、演算結果が極大となる画素を演算結果の値の降順に一つ一つ順序づけるソーティング処理は行わずに、特徴点を選択する。なお、本実施形態では、ラスタスキャン順に、演算結果が極大となる画素であるかを判定していく場合を例示するが、このスキャン順は例示であり、特徴点検出手段２０は、ラスタスキャン順以外の順にこの処理を行ってもよい。
【００７２】
特徴点検出手段２０は、具体的には、オペレータ演算手段２１と、特徴点分類手段２２と、分類結果記憶手段２３と、特徴点選択手段２４とを含む。
【００７３】
オペレータ演算手段２１は、画像内の個々の画素に対して、特徴点検出用オペレータの演算を行う。本実施形態では、特徴点検出用オペレータとしてHarrisのインタレストオペレータを用いる場合を例にして説明するが、演算結果が極大となる画素を特徴点として選択することが可能なオペレータであれば、Harrisのインタレストオペレータ以外のオペレータであってもよい。
【００７４】
特徴点分類手段２２は、Harrisのインタレストオペレータの演算結果が極大となる画素である特徴点を、ラスタスキャン順に、その演算結果の値に応じて分類する。この分類を行えるようにするため、Harrisのインタレストオペレータの演算結果の値がとり得る範囲を、予め複数の区間に分割し、各区間の範囲を定めておく。特徴点分類手段２２は、ラスタスキャン順に、Harrisのインタレストオペレータの演算結果が極大となる画素（すなわち特徴点）を、その演算結果がどの区間に属するかを判定し、分類する。
【００７５】
図６は、演算結果の値がとり得る範囲を分割した各区間の例を示す。図６に示す縦軸および横軸は、図４と同様である。Harrisのインタレストオペレータの演算結果の値がとり得る最小値をＨｍｉｎとし、最大値をＨｍａｘとする。Ｈｍｉｎ〜Ｈｍａｘの範囲を分割して、複数の区間を予め定めておけばよい。Ｈｍｉｎ〜Ｈｍａｘの範囲を分割する場合には、例えば、各区間が均等になるように分割を行えばよい。ただし、この分割方法に限定されるわけではなく、各区間の範囲の大きさが異なるように分割してもよい。図６に示す例では、Ｈ３〜Ｈｍａｘの範囲を区間ｈ１と定め、同様に、Ｈ２〜Ｈ３の範囲、Ｈ１〜Ｈ２の範囲、Ｈｍｉｎ〜Ｈ１の範囲をそれぞれ、区間ｈ２，ｈ３，ｈ４と定める場合を例示している。なお、区間の境界となる値（本例ではＨ１，Ｈ２，Ｈ３）は、いずれか一方の区間に振り分ければよい。以下、個々の区間に該当する演算結果の範囲を区間該当範囲と記す。
【００７６】
図７は、特徴点の分類を模式的に示す説明図である。図７に例示する特徴点（極大点）が得られた場合、特徴点分類手段２２は、各特徴点を、Harrisのインタレストオペレータの演算結果の値が属する区間の特徴点として分類する。本例では、区間ｈ２に３つの特徴点が分類され、他の区間ｈ１，ｈ３，ｈ４には１つずつ特徴点が分類されることになる。
【００７７】
分類結果記憶手段２３は、特徴点分類手段２２による特徴点の分類結果を記憶する記憶装置である。分類結果記憶手段２３は、例えば、区間毎に、分類された特徴点の座標値（特徴点識別情報）、および分類された特徴点の総数をまとめたテーブルを記憶する。以下のこのテーブルを特徴点テーブルと記す。図８に特徴点テーブルの例を示す。図８は、図７に示す各区間に特徴点を分類した場合の例を示している。また、図８では、便宜上、特徴点座標を模式的に１，２・・等の番号で図示している。図８に示す例では、区間ｈ１には、１つの特徴点が分類され、その特徴点座標が「１」であることを示している。同様に、区間ｈ２には、１つの特徴点が分類され、その特徴点座標が「２」、「３」、「４」であることを示している。また、区間ｈ３には、１つの特徴点が分類され、その特徴点座標が「５」であることを示している。また、区間ｈ４には、１つの特徴点が分類され、その特徴点座標が「６」であることを示している。
【００７８】
特徴点選択手段２４は、区間該当範囲がＨｍａｘに近い方の区間から、区間を順次選択して、選択した区間に属する特徴点数を累積加算していく。特徴点選択手段２４は、選択した区間に属する特徴点数を、特徴点テーブルから読み込めばよい。Ｈｍａｘは、Harrisのインタレストオペレータの演算結果のとり得る最大値である。そして、その加算結果が所定数以上となったならば、区間の選択を中止し、それまでに選択した各区間に分類されている特徴点を選択する。
【００７９】
上記の構成により、特徴点検出手段２０は、入力された画像Ａから、所定個数以上の特徴点を検出する。また、特徴点検出手段２０は、入力されたもう一方の画像Ｂからも、所定個数以上の特徴点を検出する。
【００８０】
対等特徴点決定手段３は、特徴点検出手段２０によって画像Ａ，Ｂから検出された特徴点を対象にして、第１の実施形態と同様の処理を実行する。
【００８１】
本実施形態における特徴点検出手段２０（オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３、特徴点選択手段２４）は、例えば、画像変換パラメータ算出プログラムに従って動作するコンピュータのＣＰＵによって実現される。例えば、コンピュータのプログラム記憶手段（図示せず）に記憶された画像変換パラメータ算出プログラムをＣＰＵが読み込み、ＣＰＵがそのプログラムに従って、特徴点検出手段２０（オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３、特徴点選択手段２４）、対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５、およびモデル適切性判定手段６として動作する。なお、分類結果記憶手段２３は、例えば、ＣＰＵが備えるメモリによって実現されるが、ＣＰＵとの外部に設けられた記憶装置であってもよい。
【００８２】
また、特徴点検出手段２０、対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５、およびモデル適切性判定手段６がそれぞれ別々の回路として実現されていてもよい。特徴点検出手段２０に関しても、オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３および特徴点選択手段２４がそれぞれ別々の回路として実現されていてもよい。
【００８３】
次に、第２の実施形態の動作について説明する。
第２の実施形態の画像変換パラメータ算出装置１０は、第１の実施形態と同様にステップＳ１〜Ｓ８の動作（図２参照。）を実行することにより、一方の画像Ａから他方の画像Ｂへの変換パラメータを確定する。ただし、画像Ａ，Ｂそれぞれから特徴点を検出する処理（ステップＳ１）において、特徴点検出手段２０は、以下のように動作する。
【００８４】
図９は、第２の実施形態における特徴点検出処理の処理経過の例を示すフローチャートである。特徴点検出手段２０は、入力された画像Ａ，Ｂそれぞれに対して図９に示す処理を行う。以下に示す例では、Harrisのインタレストオペレータの演算結果の値がとり得る範囲を分割した各区間を、区間該当範囲がＨｍａｘに近い方から順番に、１，２，・・・という区間識別番号で識別しているものとする。そして、特徴点選択手段２４が選択している区間の区間識別番号を変数ｍで表すこととする。一つの画像に対して特徴点検出処理を開始するときには、特徴点選択手段２４は、ｍの値を１に初期化するものとする。すなわち、区間該当範囲がＨｍａｘに最も近い区間を最初に選択することになる。
【００８５】
画像Ａから特徴点を検出する場合を例にすると、オペレータ演算手段２１は、画像Ａ内の個々の画素に対して、Harrisのインタレストオペレータの演算を行う（ステップＳ１１）。
【００８６】
次に、特徴点分類手段２２は、ステップＳ１１で計算された演算結果が極大となっているか否かをラスタスキャン順に各画素について判定し、演算結果が極大となっている画素を特徴点として定める。そして、特徴点分類手段２２は、その特徴点をラスタスキャン順に、予め定められた区間のいずれかに分類する。この分類処理では、特徴点をステップＳ１１における演算結果の値に応じて、いずれかの区間に分類すればよい。そして、特徴点分類手段２２は、分類結果を分類結果記憶手段２３に記憶させる（ステップＳ１２）。換言すれば、特徴点分類手段２２は、各区間に分類した特徴点の特徴点識別情報および各区間の特徴点総数を特徴点テーブルに登録する。例えば、特徴点分類手段２２は、特徴点テーブル（図８参照）の各区間の特徴点総数をそれぞれ０に初期化し、特徴点座標に関しても何も格納されていない状態に初期化する。そして、特徴点分類手段２２は、ステップＳ１１の演算結果が極大となっている画素である特徴点に関して、その演算結果の値がどの区間に属するかを判定し、その特徴点をその区間に分類する。そして、特徴点分類手段２２は、特徴点テーブルにおいて、その区間に対応する特徴点総数の値を１加算し、その区間に対応する特徴点座標に、分類した特徴点の座標を格納する。特徴点分類手段２２は、この処理をテップＳ１１の演算結果が極大となっている特徴点毎に実行する。この結果、図８に例示する特徴点テーブルが得られる。
【００８７】
ステップＳ１２の後、特徴点選択手段２４は、選択している区間の特徴点総数を読み取り、それまで選択した各区間の特徴点総数に累積加算する。そして、その累積加算結果が、予め定められた所定数以上になっているか否かを判定する（ステップＳ１３）。すなわち、特徴点選択手段２４は、以下の式（８）で表される条件が満たされているか否かを判定する。
【００８８】
【数２】
【００８９】
式（８）において、ｃｋは、区間識別番号がｋである区間に分類された特徴点の総数である。また、特徴点選択手段２４は、区間該当範囲がＨｍａｘに近い方から順番に区間を選択していく。従って、式（８）の左辺は、それまで選択した各区間の特徴点総数を累積加算した値を意味する。また、式（８）の右辺に示すｔｈｒｅｓｈは、予め定められた所定数を表す定数である。
【００９０】
式（８）に示す条件が成立していないということは、区間該当範囲がＨｍａｘに近い方から順番に選択してきた各区間の特徴点の総和が、所定数に達していないということである。この場合（ステップＳ１３のＮｏ）、特徴点選択手段２４は、選択している区間の区間識別番号を表す変数ｍの値を１インクリメントする（ステップＳ１４）。変数ｍを１インクリメントするということは、それまで選択していた区間に隣接している区間であって、Ｈｍａｘから遠い方の区間を新たに選択することを意味する。従って、特徴点選択手段２４は、区間該当範囲がＨｍａｘに近い方から順番に区間を選択していくことになる。
【００９１】
また、式（８）に示す条件が成立しているということは、区間該当範囲がＨｍａｘに近い方から順番に選択してきた各区間の特徴点の総和が所定数に達したということである。この場合８ステップＳ１３のＹｅｓ）、特徴点選択手段２４は、区間識別番号が１からｍまでの各区間に分類された各特徴点を選択する（ステップＳ１５）。ステップＳ１５で選択された特徴点が、画像Ａから検出された特徴点である。
【００９２】
なお、ステップＳ１３において、特徴点選択手段２４は、それまでに選択した各区間の特徴点総数の累積加算結果を求める際には、その都度、式（８）の左辺の計算を行ってもよい。
【００９３】
あるいは、特徴点選択手段２４は、ｊ番目の区間を選択したときに、１番目からｊ番目までの各区間の特徴点の総和を求め、その総和が、ｔｈｒｅｓｈ未満である場合には、求めた総和を記憶してもよい。そして、ステップＳ１４を経て再度ステップＳ１３に移行したときには、記憶している総和に、ｊ＋１番目の区間の特徴点総数を加算することによって、１番目からｊ＋１番目までの各区間の特徴点の総和を計算してもよい。この計算方法によれば、ステップＳ１３に移行する毎に式（８）の左辺の計算を行う場合よりも、計算量を少なくすることができる。なお、上記のｊは１以上の任意の区間識別番号である。
【００９４】
ステップＳ１３，Ｓ１４のループ処理の具体例を示す。本例では、図８に例示する特徴点テーブルがステップＳ１２で作成されているものとする。また、図８に示す例では、区間ｈ１〜ｈ４の区間識別番号はそれぞれ１〜４である。また、ここでは、ｔｈｒｅｓｈ＝３である場合を例に説明する。最初にステップＳ１３に移行したときには、ｍ＝１である。すなわち、特徴点選択手段２４は、区間ｈ１を選択している。区間ｈ１に分類されている特徴点数は１個であるので（図８参照）、選択した各区間の特徴点累積加算結果は１である。よって、式（８）の条件は満たさないので、特徴点選択手段２４は、変数ｍの値を２に更新し、区間ｈ２を選択する。区間ｈ２に分類されている特徴点数は３個であるので（図８参照）、選択した各区間の特徴点累積加算結果は１＋３＝４となり、ｔｈｒｅｓｈ以上となる。よって、特徴点選択手段２４は、ステップＳ１５に移行し、区間ｈ１，ｈ２に分類された特徴点を選択する。
【００９５】
以上の説明において、特徴点検出手段２０が画像Ａから特徴点を検出する場合を示したが、特徴点検出手段２０は、特徴点Ｂからも同様の処理で特徴点を検出する。特徴点検出手段２０が画像Ａ，Ｂからそれぞれ所定数以上の特徴点を検出したことにより、本実施形態におけるステップＳ１（図２参照）が完了する。ステップＳ１の後、画像変換パラメータ算出出装置１０は、第１の実施形態と同様にステップＳ２以降の処理を実行する。ステップＳ２以降の処理は、第１の実施形態と同様であり、説明を省略する。
【００９６】
本実施形態によれば、入力される画像Ａ，Ｂそれぞれから所定数以上の特徴点を検出することができる。従って、十分な数の特徴点を得ることができ、画像Ａから画像Ｂへの画像変換（位置合わせ）の精度を向上させることができる。
【００９７】
また、本実施形態では、特徴点分類手段２２は、特徴点をその演算結果に応じた区間に分類する。そして、特徴点選択手段２４が、区間該当範囲がＨｍａｘに近い方から区間を選択し、選択した区間における特徴点数の累積加算結果が所定数以上となったときに、それまでに選択した各区間に分類された各特徴点を選択する。従って、演算結果が極大となる特徴点を、演算結果の値の降順に一つ一つ順序づけるソーティング処理が不要となる。その結果、効率的に所定数以上の特徴点を検出することができる。
【００９８】
実施形態３．
第２の実施形態で示した特徴点検出手段２０を、特徴点検出装置として実現してもよい。第３の実施形態として、このような特徴点検出装置を説明する。図１０は、本発明の第３の実施形態の特徴点検出装置の例を示すブロック図である。第２の実施形態における特徴点検出手段２０の構成要素と同様の構成要素は、図３と同一の符号を付して詳細な説明を省略する。本実施形態の特徴点検出装置２７は、オペレータ演算手段２１と、特徴点分類手段２２と、分類結果記憶手段２３と、特徴点選択手段２４とを含む。
【００９９】
特徴点検出装置２７は、入力された画像から特徴点を検出する。本実施形態では、第２の実施形態と同様に、画像Ａ，Ｂのように変換パラメータ算出の対象となる複数の画像が入力されてもよい。あるいは、１つの画像のみが入力されてもよい。特徴点検出装置２７は、入力された個々の画像毎に特徴点を検出する。
【０１００】
本実施形態におけるオペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３および特徴点選択手段２４（図１０参照）は、第２の実施形態における特徴点検出手段２０が備えるオペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３および特徴点選択手段２４（図３参照）と同様である。
【０１０１】
すなわち、オペレータ演算手段２１は、画像内の個々の画素に対して、特徴点検出用オペレータの演算を行う。第２の実施形態と同様に、特徴点検出用オペレータとしてHarrisのインタレストオペレータを用いる場合を例にして説明するが、演算結果が極大となる画素を特徴点として選択することが可能なオペレータであれば、Harrisのインタレストオペレータ以外のオペレータであってもよい。
【０１０２】
特徴点分類手段２２は、Harrisのインタレストオペレータの演算結果が極大となる画素である特徴点を、その演算結果の値に応じて分類する。分類結果記憶手段２３は、特徴点分類手段２２による特徴点の分類結果を記憶する記憶装置である。特徴点分類手段２２は、例えば、図８に例示するような特徴点テーブルを分類結果として分類結果記憶手段２３に記憶させる。
【０１０３】
特徴点選択手段２４は、区間該当範囲がＨｍａｘに近い方の区間から、区間を順次選択して、選択した区間に属する特徴点数を累積加算する。そして、その加算結果が所定数以上となったならば、区間の選択を中止し、それまでに選択した各区間に分類されている特徴点を選択する。
【０１０４】
オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３および特徴点選択手段２４は、例えば、特徴点検出プログラムに従って動作するコンピュータのＣＰＵによって実現される。コンピュータのプログラム記憶手段（図示せず）に記憶された特徴点検出プログラムをＣＰＵが読み込み、ＣＰＵがそのプログラムに従って、オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３、特徴点選択手段２４として動作する。分類結果記憶手段２３は、例えば、ＣＰＵが備えるメモリによって実現されるが、ＣＰＵとの外部に設けられた記憶装置であってもよい。
【０１０５】
また、オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３および特徴点選択手段２４がそれぞれ別々の回路として実現されていてもよい。
【０１０６】
第３の実施形態の特徴点検出装置２７の処理経過は、第２の実施形態で説明したステップＳ１１〜Ｓ１５と同様である。この動作により、特徴点検出装置２７は、入力された画像から所定数以上の特徴点を検出する。
【０１０７】
本実施形態においても、入力された画像から所定数以上の特徴点を検出することができる。また、第２の実施形態と同様に、特徴点検出用オペレータの演算結果が極大となる特徴点を演算結果の値の降順に一つ一つ順序づけるソーティング処理が不要となる。従って、効率的に所定数以上の特徴点を検出することができる。
【０１０８】
第３の実施形態の特徴点検出装置は、第２の実施形態の画像変換パラメータ算出装置の外にも、画像から検出された特徴点を用いて処理を行う種々の画像処理装置で利用可能である。
【０１０９】
次に、本発明の最小構成について説明する。図１１は、本発明の画像変換パラメータ算出装置の最小構成の例を示すブロック図である。本発明の画像変換パラメータ算出装置１０は、特徴点検出手段２０と、対応特徴点特定手段３と、パラメータ計算手段５と、モデル適切性判定手段６とを備える。
【０１１０】
特徴点検出手段２０は、入力される第１画像（例えば、画像Ａ）および第２画像（例えば、画像Ｂ）からそれぞれ所定数以上の特徴点を検出する。
【０１１１】
対応特徴点特定手段３は、第１画像および第２画像の間で対応する特徴点の組を特定する。
【０１１２】
パラメータ計算手段５は、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算する。
【０１１３】
モデル適切性判定手段６は、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定する。
【０１１４】
また、特徴点検出手段２０は、オペレータ演算手段２１と、特徴点分類手段２２と、特徴点選択手段２４とを有する。
【０１１５】
オペレータ演算手段２１は、画像内の各画素に対して特徴点検出用オペレータ（例えば、Harrisのインタレストオペレータ）の演算を行う。
【０１１６】
特徴点分類手段２２は、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する。
【０１１７】
特徴点選択手段２４は、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する。
【０１１８】
そして、対応特徴点特定手段３は、特徴点選択手段２４が選択した特徴点の中から特徴点の組を特定する。
【０１１９】
以上のような構成により、第１画像および第２画像の組み合わせに関して適切な座標変換モデルを特定して、その座標変換モデルにおけるパラメータとして、第１画像から第２画像への適切な変換パラメータを得ることができる。また、その結果、第１画像から第２画像への画像変換（位置合わせ）の精度を向上させることができる。
【０１２０】
また、特徴点検出用オペレータの演算結果が極大となる特徴点を演算結果の値の降順に一つ一つ順序づけるソーティング処理を行うことなく、所定数以上の特徴点を検出することができる。従って、画像から効率的に所定数以上の特徴点を検出できる。
【０１２１】
なお、上記の実施形態には、以下の（１）〜（７）に示すような画像変換パラメータ算出装置が開示されている。
【０１２２】
（１）入力される第１画像（例えば、画像Ａ）および第２画像（例えば、画像Ｂ）からそれぞれ所定数以上の特徴点を検出する特徴点検出手段（例えば、特徴点検出手段２０）と、第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定手段（例えば、対応特徴点特定手段３）と、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算手段（例えば、パラメータ計算手段５）と、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定手段（例えば、モデル適切性判定手段６）とを備え、特徴点検出手段が、画像内の各画素に対して特徴点検出用オペレータ（例えば、Harrisのインタレストオペレータ）の演算を行うオペレータ演算手段（例えば、オペレータ演算手段２１）と、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類手段（例えば、特徴点分類手段２２）と、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数（例えば、定数ｔｈｒｅｓｈ）以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択手段（例えば、特徴点選択手段２４）を有し、対応特徴点特定手段が、特徴点選択手段が選択した特徴点の中から特徴点の組を特定することを特徴とする画像変換パラメータ算出装置。
【０１２３】
（２）モデル適切性判定手段が、対応する特徴点の組毎に、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差を計算し、組毎に計算した差の平均値（例えば、平均再投影誤差Ｅ）が、予め定められた閾値以下である場合に、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であると判定し、その平均値が閾値より大きい場合に、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切でないと判定する画像変換パラメータ算出装置。
【０１２４】
（３）座標変換モデルを選択する座標変換モデル選択手段（例えば、モデル選択手段４）を備え、パラメータ計算手段が、選択された座標変換モデルにおける変換パラメータを計算し、座標変換モデル選択手段が、モデル適切性判定手段によって座標変換モデルが第１画像から第２画像への変換として適切でないと判定された場合に、その座標変換モデルよりも変換の自由度が高い座標変換モデルを新たに選択する画像変換パラメータ算出装置。
【０１２５】
（４）パラメータ計算手段が、新たに選択された座標変換モデルに関して変換パラメータを計算するときに、以前に選択された座標変換モデルに関して変換パラメータを計算する際に既に対応付けられていた特徴点の組を用いる画像変換パラメータ算出装置。
【０１２６】
（５）パラメータ計算手段が、複数の座標変換モデルに関して並列に変換パラメータを計算する画像変換パラメータ算出装置。
【０１２７】
（６）特徴点分類手段による特徴点の分類結果（例えば、図８に例示する特徴点テーブル）を記憶する分類結果記憶手段（例えば、分類結果記憶手段２３）を備え、特徴点分類手段が、複数の区間毎に、分類した特徴点の数、および分類した各特徴点を識別する特徴点識別情報を分類結果記憶手段に記憶させ、特徴点選択手段が、選択した区間に分類された特徴点数を分類結果記憶手段から読み込む画像変換パラメータ算出装置。
【０１２８】
（７）入力される第１画像および第２画像からそれぞれ特徴点を検出する特徴点検出手段と、第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定手段と、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算手段と、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定手段とを備えることを特徴とする画像変換パラメータ算出装置。
【０１２９】
また、上記の実施形態には、以下の（８），（９）に示すような特徴点検出装置が開示されている。
【０１３０】
（８）画像内の各画素に対して特徴点検出用オペレータの演算を行うオペレータ演算手段（例えば、オペレータ演算手段１０）と、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類手段（例えば、特徴点分類手段２２）と、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択手段（例えば、特徴点選択手段２４）とを備えることを特徴とする特徴点検出装置。
【０１３１】
（９）特徴点分類手段による特徴点の分類結果を記憶する分類結果記憶手段（例えば、分類結果記憶手段２３）を備え、特徴点分類手段が、複数の区間毎に、分類した特徴点の数、および分類した各特徴点を識別する特徴点識別情報を分類結果記憶手段に記憶させ、特徴点選択手段が、選択した区間に分類された特徴点数を分類結果記憶手段から読み込む特徴点検出装置。
【産業上の利用可能性】
【０１３２】
本発明は、一つの画像に含まれる物体の位置が他の画像におけるその物体の位置と同じになるように画像を変換するための変換パラメータを算出する画像変換パラメータ算出装置に好適に適用される。
【符号の説明】
【０１３３】
１，１０ 画像変換パラメータ算出装置
２，２０ 特徴点検出手段
３ 対応特徴点特定手段
４ モデル選択手段
５ パラメータ計算手段
６ モデル適切性判定手段
２１ オペレータ演算手段
２２ 特徴点分類手段
２３ 分類結果記憶手段
２４ 特徴点選択手段
２７ 特徴点検出装置
【技術分野】
【０００１】
本発明は、画像変換パラメータ算出装置、画像変換パラメータ算出方法および画像変換パラメータ算出プログラムに関する。
【背景技術】
【０００２】
同一対象物を撮影した場合であっても、カメラ位置のずれ等の原因により、画像内における物体の位置がずれることがある。このような場合に、一つの画像を変換して、その画像に含まれる物体の位置が他の画像におけるその物体の位置と同じになるようにするには、画像の位置合わせが必要となる。一方の画像を他方の画像に位置合わせする画像変換を表す変換パラメータは、画像間の特徴点の対応関係から求めることができる。
【０００３】
非特許文献１には、画像同士で対応する特徴点を抽出する方法が記載されている。非特許文献１内の「特徴点の追跡」という項目には、「Harrisのインタレストオペレータとテンプレートマッチングにより、前フレームの各特徴点について、現フレームにおける対応点を探索する。更に、ＲＡＮＳＡＣアルゴリズムを用いて、特徴点の誤対応を排除する。」と記載されている。換言すれば、特徴点の対応から画像変換を表す変換パラメータをＲＡＮＳＡＣアルゴリズムで求め、その画像変換に従わない特徴点を排除することが記載されている。
【０００４】
また、Harrisのインタレストオペレータについては、非特許文献２に記載されている。非特許文献２には、Harrisのインタレストオペレータが極値を与える点を、その値の大きい順に、指定した個数だけ特徴点として取り出すことが記載されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】池谷彰彦、外５名、「カメラパラメータ推定による紙面を対象とした超解像ビデオモザイキング」、電子情報通信学会論文誌、社団法人電子情報通信学会、Ｄ−ＩＩ、Ｖｏｌ．Ｊ８８−Ｄ−ＩＩ、Ｎｏ．８、ｐｐ．１４９０−１４９８、２００５年
【非特許文献２】金澤靖、金谷健一、「解説 コンピュータビジョンのための画像の特徴点の抽出」、電子情報通信学会誌、社団法人電子情報通信学会、Ｖｏｌ．８７、Ｎｏ．１２、ｐｐ．１０４３−１０４８、２００４年
【発明の概要】
【発明が解決しようとする課題】
【０００６】
前述のように、非特許文献１には、画像同士の間で対応する特徴点を抽出し、特徴点の対応から画像変換を表す変換パラメータをＲＡＮＳＡＣアルゴリズムで求め、その画像変換に従わない特徴点を排除することが記載されている。このような処理において、画像変換を表す変換パラメータを求める場合に、画像間における座標変換モデルを仮定し、その座標変換モデルにおける変換パラメータを求めることが考えられる。座標変換モデルとは、変換の自由度で分類した座標変換の種類である。
【０００７】
しかし、座標変換モデルとしては、変換の自由度が低いモデルや変換の自由度が高いモデル等、種々の座標変換モデルがある。変換の自由度が低い座標変換モデルの例として、平行移動のみを表すモデルがある。また、変換の自由度が高い座標変換モデルの例として、長方形を任意の四辺形に変換可能なモデル（例えば、ホモグラフィ変換）等がある。
【０００８】
変換パラメータを求める際に仮定する座標変換モデルにおける変換の自由度が実際の座標変換よりも低いと、画像内の特徴点座標を他方の画像の対応点座標に変換する変換パラメータを求めることができない。例えば、実際には、平行移動だけでなく回転変換も行わなければ、特徴点座標を対応点座標に変換できないにも関わらず、平行移動のみを表す座標変換モデルを用いると、正しく座標変換を行う変換パラメータを求めることができない。一方、変換パラメータを求める際に仮定する座標変換モデルにおける変換の自由度が実際の座標変換よりも高いと、特徴点座標を適切な対応点座標に変換できるものの、誤った特徴点の対応付けも許容する変換パラメータが求まってしまう。この場合には、非特許文献１に記載されている、画像変換に従わない特徴点を排除する処理を行おうとしても、排除すべき特徴点が排除されずに残ってしまうことになる。
【０００９】
従って、適切な座標変換モデルを選ばなければ、精度よく画像の位置合わせを行うことができない。しかし、画像のパターンは多様であり、処理対象となる画像に応じて適切な座標変換モデルを選ぶことは困難であった。
【００１０】
また、画像からの特徴点検出に関しては、以下のような問題があった。画像から特徴点を検出する方法として、Harrisのインタレストオペレータのような特徴点検出用オペレータを用いて画素に対する演算を行い、その演算結果に基づいて、特徴点を決定する方法がある。例えば、Harrisのインタレストオペレータを適用した場合では、演算結果が極大になる画素を特徴点とする。このとき、演算結果と閾値とを比較して、演算結果が閾値以上となっている等の条件を満たす画素を、特徴点として決定することが考えられる。例えば、演算結果が極大点となった画素のうち、演算結果が閾値以上となっている画素を特徴点として決定することが考えられる。しかし、このような特徴点の決め方では、十分な数の特徴点が得られず、その結果、画像の位置合わせを精度よく行えない場合が生じ得る。
【００１１】
この問題を解決するためには、非特許文献２に記載されているように、Harrisのインタレストオペレータが極大値を与える点を、その値の大きい順に、指定した個数だけ特徴点として取り出せばよい。しかし、この方法では、値のソーティング処理が必要となるために、特徴点検出処理が非効率的になってしまう。
【００１２】
そこで、本発明は、画像変換を表す変換パラメータとして、適切な自由度の座標変換モデルにおける変換パラメータを求めることができる画像変換パラメータ算出装置、画像変換パラメータ算出方法および画像変換パラメータ算出プログラムを提供することを目的とする。また、効率的な処理によって画像から所望の数の特徴点を検出して画像変換を表す変換パラメータを求めることができる画像変換パラメータ算出装置、画像変換パラメータ算出方法および画像変換パラメータ算出プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明による画像変換パラメータ算出装置は、入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出する特徴点検出手段と、第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定手段と、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算手段と、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定手段とを備え、特徴点検出手段が、画像内の各画素に対して特徴点検出用オペレータの演算を行うオペレータ演算手段と、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類手段と、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択手段を有し、対応特徴点特定手段が、特徴点選択手段が選択した特徴点の中から特徴点の組を特定することを特徴とする。
【００１４】
本発明による画像変換パラメータ算出方法は、入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出し、第１画像および第２画像の間で対応する特徴点の組を特定し、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算し、計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算した変換パラメータを第１画像から第２画像への変換パラメータとして確定し、入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出するときに、画像内の各画素に対して特徴点検出用オペレータの演算を行い、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類し、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数以上となったときに、選択済みの各区間に分類された特徴点を選択することを特徴とする。
【００１５】
本発明による画像変換パラメータ算出プログラムは、コンピュータに、入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出する特徴点検出処理、第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定処理、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算処理、および、パラメータ計算処理で計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定処理を実行させ、特徴点検出処理で、画像内の各画素に対して特徴点検出用オペレータの演算を行うオペレータ演算処理、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類処理、および、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択処理を実行させ、対応特徴点特定処理で、特徴点選択処理で選択された特徴点の中から特徴点の組を特定させることを特徴とする。
【発明の効果】
【００１６】
本発明によれば、画像変換を表す変換パラメータとして、適切な自由度の座標変換モデルにおける変換パラメータを求めることができる。また、効率的な処理によって画像から所望の数の特徴点を検出して画像変換を表す変換パラメータを求めることができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１の実施形態の画像変換パラメータ算出装置の例を示すブロック図である。
【図２】本発明の画像変換パラメータ算出装置の処理経過の例を示すフローチャートである。
【図３】本発明の第２の実施形態の画像変換パラメータ算出装置の例を示すブロック図である。
【図４】画素に対する特徴点検出用オペレータの演算結果を模式的に示す説明図である。
【図５】図４に示す演算結果の変化において演算結果が極大となる箇所を示す説明図である。
【図６】演算結果の値がとり得る範囲を分割した各区間の例を示す。
【図７】特徴点の分類を模式的に示す説明図である。
【図８】特徴点テーブルの例を示す説明図である。
【図９】第２の実施形態における特徴点検出処理の処理経過の例を示すフローチャートである。
【図１０】本発明の第３の実施形態の特徴点検出装置の例を示すブロック図である。
【図１１】本発明の最小構成の例を示すブロック図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施形態を図面を参照して説明する。
【００１９】
実施形態１．
図１は、本発明の第１の実施形態の画像変換パラメータ算出装置の例を示すブロック図である。第１の実施形態の画像変換パラメータ算出装置１は、２つの画像が入力されると、一方の画像（Ａとする。）に含まれる物体の位置が他の画像（Ｂとする。）におけるその物体の位置と同じになるように、画像Ａ内の画素の座標を変換する変換パラメータを算出する。入力される画像Ａ，Ｂは、画像の位置合わせの対象となる画像である。例えば、動画における連続するフレーム等が、画像Ａ，Ｂとして入力される。本発明の画像変換パラメータ算出装置１は、特徴点検出手段２と、対応特徴点特定手段３と、モデル選択手段４と、パラメータ計算手段５と、モデル適切性判定手段６とを備える。
【００２０】
特徴点検出手段２は、入力された画像Ａ，Ｂから、それぞれ特徴点を検出する。すなわち、画像Ａ，Ｂ内において特徴点となる画素を判定する。特徴点検出手段２は、各画像の個々の画素に対して、特徴点検出用オペレータの演算を行い、その演算結果として得られる値に基づいて、特徴点となる画素を判定すればよい。以下、特徴点検出用オペレータとして、Harrisのインタレストオペレータを用いる場合を例にして説明するが、特徴点検出用オペレータは、Harrisのインタレストオペレータに限定されない。Harrisのインタレストオペレータを用いる場合、特徴点検出手段２は、画像内の画素毎に、Harrisのインタレストオペレータの演算を行い、演算結果が極大となる画素を特徴点として判定すればよい。
【００２１】
対応特徴点特定手段３は、画像Ａから検出された特徴点群と、画像Ｂから検出された特徴点群とから、画像Ａ，Ｂ間で対応する特徴点の組を特定する。対応特徴点特定手段３は、例えば、画像Ａから検出された特徴点座標を中心とする局所領域内のパターンと、画像Ｂから検出された特徴点座標を中心とする局所領域内のパターンとの類似度を計算し、類似度が高いと判定される特徴点同士を対応付ければよい。あるいは、他の方法で特徴点同士を対応づけてもよい。
【００２２】
パラメータ計算手段５は、画像Ａの各特徴点の座標を、画像Ｂ内で対応する特徴点座標またはその近傍の点の座標に変換する変換パラメータを計算する。この変換パラメータは、画像Ａを画像Ｂに合わせるように画像Ａの画素の座標を変換するための変換パラメータの候補である。
【００２３】
パラメータ計算手段５は、モデル選択手段４が選択する座標変換モデルにおける変換パラメータを計算することによって、画像Ａの各特徴点の座標を、画像Ｂ内で対応する特徴点座標またはその近傍の点の座標に変換する変換パラメータを計算する。この計算では、パラメータ計算手段５は、選択された座標変換モデルにおける変換パラメータを、対応する特徴点同士の組を用いて、例えば、ＲＡＮＳＡＣ（RANdom SAmple Consensus）アルゴリズムによって計算すればよい。
【００２４】
モデル選択手段４は、パラメータ計算手段５が変換パラメータを計算する際の座標変換モデルを選択する。既に説明したように、座標変換モデルとは、変換の自由度で分類した座標変換の種類である。変換の自由度は、パラメータの数で表される。すなわち、変換の自由度が高くなるほど、変換パラメータの数は多くなり、変換の自由度が低いほど、変換パラメータの数は少なくなる。以下、座標変換モデルの例を示す。以下の説明において、ａｎ（ｎは自然数）は、座標変換モデルにおける変換パラメータを表すものとする。
【００２５】
座標変換モデルの第１の例として、座標を平行移動させる変換（以下、平行移動変換と記す。）が挙げられる。変換前の座標を（ｘ，ｙ）とし、変換後の座標を（ｘ’，ｙ’）とすると、平行移動変換は、以下に示す式（１）および式（２）で表すことができる。
【００２６】
ｘ’＝ｘ＋ａ１ 式（１）
ｙ’＝ｙ＋ａ２ 式（２）
【００２７】
平行移動変換で用いる変換パラメータは、ａ１，ａ２の２個であり、平行移動変換の自由度は２である。
【００２８】
座標変換モデルの第２の例として、アフィン変換が挙げられる。変換前の座標を（ｘ，ｙ）とし、変換後の座標を（ｘ’，ｙ’）とすると、アフィン変換は、以下に示す式（３）および式（４）で表すことができる。
【００２９】
ｘ’＝ａ１ｘ＋ａ２ｙ＋ａ３ 式（３）
ｙ’＝ａ４ｘ＋ａ５ｙ＋ａ６ 式（４）
【００３０】
アフィン変換で用いる変換パラメータは、ａ１〜ａ６の６個であり、アフィン変換の自由度は６である。
【００３１】
座標変換モデルの第３の例として、ホモグラフィ（Homography）変換が挙げられる。ホモグラフィ変換では、長方形を任意の四辺形に変換可能である。変換前の座標を（ｘ，ｙ）とし、変換後の座標を（ｘ’，ｙ’）とすると、ホモグラフィ変換は、以下に示す式（５）および式（６）で表すことができる。
【００３２】
ｘ’＝（ａ１ｘ＋ａ２ｙ＋ａ３）／（ａ７ｘ＋ａ８ｙ＋１） 式（５）
ｙ’＝（ａ４ｘ＋ａ５ｙ＋ａ６）／（ａ７ｘ＋ａ８ｙ＋１） 式（６）
【００３３】
ホモグラフィ変換で用いる変換パラメータは、ａ１〜ａ８の８個であり、ホモグラフィ変換の自由度は８である。
【００３４】
本例では、座標変換モデルの例を３つ挙げたが、モデル選択手段４は、他の座標変換モデルを選択してもよい。
【００３５】
本実施形態では、モデル選択手段４は、変換の自由度が少ない順に、座標変換モデルを選択する。以下の説明では、モデル選択手段４が、自由度２，６，８の順に座標変換モデルを選択する場合を例にして説明する。具体的には、平行移動変換、アフィン変換、ホモグラフィ変換の順に座標変換モデルを選択する場合を例に説明する。
【００３６】
モデル選択手段４が平行移動変換を選択した場合、パラメータ計算手段５は、式（１）および式（２）におけるａ１，ａ２を計算する。また、モデル選択手段４がアフィン変換を選択した場合、パラメータ計算手段５は、式（３）および式（４）におけるａ１〜ａ６を計算する。また、モデル選択手段４がホモグラフィ変換を選択した場合、パラメータ計算手段５は、式（５）および式（６）におけるａ１〜ａ８を計算する。
【００３７】
モデル適切性判定手段６は、モデル選択手段４によって選択された座標変換モデルが適切であるか否かを判定する。モデル適切性判定手段６は、パラメータ計算手段５が計算した変換パラメータを用いて画像Ａ内の特徴点の座標を変換し、その特徴点に対応する画像Ｂ内の特徴点の座標と、変換によって得た座標との差（例えば、後述の平均再投影誤差）を計算する。モデル適切性判定手段６は、その差が大きければ、選択された座標変換モデルは画像Ａから画像Ｂへの変換として適切でないと判定する。また、その差が小さければ、選択された座標変換モデルは画像Ａから画像Ｂへの変換として適切であり、その座標変換モデルに基づいて計算された変換パラメータも画像Ａから画像Ｂへの変換パラメータとして適切であると判定する。なお、画像Ａ内の特徴点に対応する画像Ｂ内の特徴点の座標と、画像Ａ内の特徴点を変換して得た座標との差が大きいか否かは、予め定めた閾値との大小関係に基づいて判定すればよい。
【００３８】
特徴点検出手段２、対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５、およびモデル適切性判定手段６は、例えば、画像変換パラメータ算出プログラムに従って動作するコンピュータのＣＰＵによって実現される。例えば、コンピュータのプログラム記憶手段（図示せず）に記憶された画像変換パラメータ算出プログラムをＣＰＵが読み込み、ＣＰＵがそのプログラムに従って、特徴点検出手段２、対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５、およびモデル適切性判定手段６として動作する。また、特徴点検出手段２、対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５、およびモデル適切性判定手段６がそれぞれ別々の回路として実現されていてもよい。
【００３９】
次に、動作について説明する。
図２は、本発明の画像変換パラメータ算出装置の処理経過の例を示すフローチャートである。なお、初期状態において、モデル選択手段４は、変換の自由度が２である平行移動変換を選択しているものとする。
【００４０】
画像Ａ，Ｂが入力されると、特徴点検出手段２は、入力された画像Ａ，Ｂそれぞれから特徴点を検出する（ステップＳ１）。画像Ａから特徴点を検出する場合、特徴点検出手段２は、画像Ａの各画素に対して、Harrisのインタレストオペレータの演算を行い、演算結果が極大となる画素を特徴点とする。特徴点検出手段２は、画像Ｂからも同様に特徴点を検出する。ここでは、Harrisのインタレストオペレータを用いて特徴点を検出する場合を例示したが、本実施形態では、特徴点検出手段２の特徴点検出方法は、特に限定されない。
【００４１】
次に、対応特徴点特定手段３は、画像Ａから検出された特徴点群と、画像Ｂから検出された特徴点群とから、画像間で対応する特徴点の組を特定する（ステップＳ２）。ステップＳ２において、対応特徴点特定手段３は、一方の画像（画像Ａ）の特徴点を選択し、もう一方の画像（画像Ｂ）からその特徴点に対応する特徴点（以下、対応点と記す。）の候補を選択する。さらに、対応特徴点特定手段３は、画像Ａの特徴点座標を中心とする局所領域内のパターンを画像Ａから抽出し、同様に、画像Ｂからも選択した対応点の候補の座標を中心とする局所領域内のパターンを抽出する。対応特徴点特定手段３は、画像Ａから抽出したパターンと画像Ｂから抽出したパターンの組み合わせにおけるＳＡＤ（Sum of Absolute Difference）値を計算する。ＳＡＤ値とは、２つのパターンの対応する画素毎に、画素値の差の絶対値を計算して、画素毎に計算した画素値の差の絶対値の総和として得られる値である。対応特徴点特定手段３は、画像Ｂの対応点候補を変更しながら、対応点候補毎にＳＡＤ値を計算し、ＳＡＤ値が最小となる対応点を、画像Ａから選択した特徴点に対応する画像Ｂ内の特徴点として決定する。対応特徴点特定手段３は、この動作を繰り返し、画像Ａ内の特徴点と、画像Ｂ内の特徴点とを対応付ければよい。ここではＳＡＤ値に基づいて特徴点を対応付ける場合を例にして説明したが、対応特徴点特定手段３は、他の方法で画像間の特徴点の対応付けを行ってもよい。
【００４２】
次に、パラメータ計算手段５は、ステップＳ２で対応付けられた特徴点同士の組を用いて、選択されている座標変換モデルにおける変換パラメータの値を計算する（ステップＳ３）。本例では、初期状態で、平行移動変換が選択されている。従って、最初にステップＳ３に移行した場合、パラメータ計算手段５は、式（１）および式（２）におけるａ１，ａ２を計算すればよい。
【００４３】
また、パラメータ計算手段５は、ステップＳ３において、例えば、ＲＡＮＳＡＣアルゴリズムにより変換パラメータを計算すればよい。以下、ＲＡＮＳＡＣアルゴリズムによる変換パラメータの計算例を示す。
【００４４】
パラメータ計算手段５は、対応する特徴点同士の組の中から、選択されている座標変換モデルにおける変換パラメータの値を計算可能な特徴点同士の組を任意に選択し、その特徴点同士の組から変換パラメータの値を計算する。パラメータ計算手段５は、この特徴点の組の選択と、変換パラメータの値の計算を複数回繰り返す。選択した特徴点の組から変換パラメータを計算する際には、パラメータ計算手段５は、画像Ａの特徴点の座標を変換前の座標とし、画像Ｂの特徴点の座標を変換後の座標として、選択されている座標変換モデルの変換式にその座標代入し、変換式に含まれる各パラメータａｎについての方程式を解けばよい。
【００４５】
特徴点の組を変えて、変換パラメータの値を計算することを繰り返すことにより、変換パラメータの値が複数得られる。パラメータ計算手段５は、計算した各変換パラメータの値について、対応特徴点特定手段３によって対応付けられた全ての特徴点の組を用いて評価し、選択されている座標変換モデルにおける変換パラメータとして適切なパラメータを決定する。この評価では、パラメータ計算手段５は、対応特徴点特定手段３によって対応付けられた特徴点の各組における画像Ａの特徴点の座標を変換前の座標とし、計算した変換パラメータ毎に、変換後の座標値を計算する。そして、パラメータ計算手段５は、変換パラメータ毎に、計算した変換後の座標群の中から、画像Ａの特徴点に対応する画像Ｂの特徴点の座標との距離が所定の閾値未満となる座標の個数を計数する。パラメータ計算手段５は、その計数結果が最大となる変換パラメータを、選択されている座標変換モデルでの適切なパラメータと決定する。換言すれば、パラメータ計算手段５は、変換パラメータ毎に、ステップＳ２で対応付けられた特徴点の全組に関して、画像Ａの特徴点座標を変換し、変換後の座標と、変換元の特徴点に対応する画像Ｂの特徴点の座標との距離が閾値未満となっている特徴点の組の数を計数し、その計数結果が最大となる変換パラメータを、選択されている座標変換モデルでの適切なパラメータと決定する。
【００４６】
以下、具体例を示す。ここでは、平行移動変換が選択されているものとする。この場合、特徴点同士の一つの組から、平行移動変換の変換式である式（１）および式（２）における変換パラメータａ１，ａ２を計算することができる。よって、パラメータ計算手段５は、特徴点同士の組を任意に１組選択し、選択した１組から式（１）および式（２）における変換パラメータａ１，ａ２を計算する処理を繰り返す。この結果、１つめの組からは“ａ１＝ｐ１，ａ２＝ｑ１”が得られ、２つ目の組からは“ａ１＝ｐ２，ａ２＝ｑ２”が得られるというように、複数の変換パラメータが得られたとする。パラメータ計算手段５は、対応特徴点特定手段３によって対応付けられた全ての特徴点の組における画像Ａの特徴点の座標を、“ａ１＝ｐ１，ａ２＝ｑ１”を用いて変換した場合の変換結果を計算する。そして、パラメータ計算手段５は、特徴点の各組における画像Ａの特徴点の座標を変換パラメータ“ａ１＝ｐ１，ａ２＝ｑ１”で変換して得た座標群の中から、画像Ａの特徴点に対応する画像Ｂの特徴点の座標との距離が所定の閾値未満となる座標の個数を計数する。“ａ１＝ｐ２，ａ２＝ｑ２”等の他の変換パラメータに関しても同様の処理を行う。パラメータ計算手段５は、求めた計数結果が最大となる変換パラメータを、平行移動変換での適切な変換パラメータであると決定する。
【００４７】
なお、上記の例は、ＲＡＮＳＡＣアルゴリズムによる変換パラメータ計算の一例であり、変換パラメータの計算方法は、上記の例に限定されない。
【００４８】
例えば、上記の例では、対応特徴点特定手段３によって対応づけられた特徴点の全組における画像Ａの特徴点の座標の変換結果のうち、変換元の特徴点に対応する画像Ｂの特徴点の座標との距離が閾値未満となっている座標の数を計数し、その計数結果が最大となる変換パラメータを、適切な変換パラメータであると決定する場合を示した。このように変換パラメータを決定するのではなく、計数結果が大きい順に所定数の変換パラメータを選び、その各変換パラメータ導出時に選択していた各特徴点の組を用いて、最小二乗法により変換パラメータを決定してもよい。
【００４９】
また、例えば、特徴点の組を変えて、変換パラメータの値を計算することを繰り返す際にも、変換パラメータの値を計算するために必要な最小限の数よりも多くの数の組を選択し、それらの組から最小二乗法により変換パラメータの値を計算してもよい。
【００５０】
選択されている座標変換モデルでの適切な変換パラメータを計算する処理（ステップＳ３）の後、モデル適切性判定手段６は、ステップＳ３で決定した変換パラメータにおける平均再投影誤差を計算する（ステップＳ４）。
【００５１】
ここで、平均再投影誤差について説明する。ステップＳ２で対応付けられた特徴点の組のうち、画像Ａ側の特徴点の座標を（ｘｉ，ｙｉ）とし、画像Ｂ側の特徴点の座標を（ｘ’ｉ，ｙ’ｉ）とする。また、画像Ａの特徴点の座標（ｘｉ，ｙｉ）を、ステップＳ３で決定された変換パラメータを用いて変換した結果を（Ｘｉ，Ｙｉ）とする。また、テップＳ２で対応付けられた特徴点の組の総数をｍ個とする。このとき、平均再投影誤差をＥとすると、平均再投影誤差Ｅは、以下に示す式（７）として定義される。
【００５２】
【数１】
【００５３】
平均再投影誤差Ｅは、画像Ａ内の特徴点に対応する画像Ｂ内の特徴点の座標と、その画像Ａ内の特徴点の座標を変換パラメータで変換した座標との差を、画像Ａ内の特徴点毎に求め、その平均を計算した結果の値である。平均再投影誤差Ｅは、画像Ａ内の特徴点に対応する画像Ｂ内の特徴点の座標と、その画像Ａ内の特徴点の座標を変換パラメータで変換した座標との差を表した値であるということができる。
【００５４】
ステップＳ４の次に、モデル適切性判定手段６は、選択されている座標変換モデルが画像Ａから画像Ｂへの変換として適切か否かを判定する（ステップＳ５）。ステップＳ５では、モデル適切性判定手段６は、平均再投影誤差Ｅが、予め定められた閾値（以下、誤差閾値と記す。）以下であるか否かを判定することによって、選択されている座標変換モデルが適切か否かを判定する。
【００５５】
平均再投影誤差Ｅが誤差閾値より大きいということは、選択されている座標変換モデルに基づいてステップＳ３で決定した変換パラメータは、画像Ａから画像Ｂへの変換を適切に表現できていないことになる。よって、モデル適切性判定手段６は、平均再投影誤差Ｅが誤差閾値より大きい場合には、選択されている座標変換モデルが適切でないと判定する（ステップＳ５のＮｏ）。逆に、平均再投影誤差Ｅが誤差閾値以下であるということは、画像Ａ内の特徴点に対応する画像Ｂ内の特徴点の座標と、その画像Ａ内の特徴点の座標を変換パラメータで変換した座標との差が十分に小さく、選択されている座標変換モデルが適切であり、その変換モデルに基づいてステップＳ３で計算された変換パラメータも、画像Ａから画像Ｂへの変換を適切に表現できているということができる。よって、モデル適切性判定手段６は、平均再投影誤差Ｅが誤差閾値以下である場合には、選択されている座標変換モデルが適切であると判定する（ステップＳ５のＹｅｓ）。
【００５６】
選択されている座標変換モデルが適切でない場合（すなわち、平均再投影誤差Ｅが誤差閾値より大きい場合）、モデル選択手段４は、選択している座標変換モデルよりも自由度が高い座標変換モデルを新たに選択する（ステップＳ６）。すなわち、選択する座標変換モデルを更新する。例えば、平行移動変換を選択している状態でステップＳ６に移行した場合、モデル選択手段４は、より自由度の高いアフィン変換を選択する。また、アフィン変換を選択している状態でステップＳ６に移行した場合、モデル選択手段４は、より自由度の高いホモグラフィ変換を選択する。
【００５７】
ただし、予め選択順を定めた座標変換モデルで、最も自由度が高い座標変換モデルを既に選択している場合には、より自由度が高い座標変換モデルを選択できない。この場合（ステップＳ７のＮｏ）、ステップＳ８に移行する。
【００５８】
また、ステップＳ６でより自由度が高い変換モデルを選択した場合には（ステップＳ７のＹｅｓ）、画像変換パラメータ算出装置は、画像Ａ，Ｂに対して、ステップＳ１以降の処理を繰り返す。
【００５９】
ステップＳ６でアフィン変換が新たに選択され、ステップＳ１から処理をやり直した場合におけるステップＳ３の処理の例を示す。この場合、特徴点同士の３つの組から、式（３）および式（６）の方程式を６個定め、その方程式から変換パラメータａ１〜ａ６を計算することができる。よって、パラメータ計算手段５は、特徴点同士の組を任意に３組選択し、選択した３組から式（３）および式（４）における変換パラメータａ１〜ａ６を計算することを繰り返す。この結果、１つめの組からは“ａ１＝ｐ１，ａ２＝ｑ１，ａ３＝ｒ１，ａ４＝ｓ１，ａ５＝ｔ１，ａ６＝ｕ１” が得られ、２つ目の組からは“ａ１＝ｐ２，ａ２＝ｑ２，ａ３＝ｒ２，ａ４＝ｓ２，ａ５＝ｔ２，ａ６＝ｕ２” が得られるというように、複数の変換パラメータが得られたとする。パラメータ計算手段５は、対応特徴点特定手段３によって対応付けられた全ての特徴点の組における画像Ａの特徴点の座標を、“ａ１＝ｐ１，ａ２＝ｑ１，ａ３＝ｒ１，ａ４＝ｓ１，ａ５＝ｔ１，ａ６＝ｕ１”を用いて変換した場合の変換結果を計算する。そして、パラメータ計算手段５は、特徴点の各組における画像Ａの特徴点の座標を変換パラメータ“ａ１＝ｐ１，ａ２＝ｑ１，ａ３＝ｒ１，ａ４＝ｓ１，ａ５＝ｔ１，ａ６＝ｕ１”で変換して得た座標群の中から、画像Ａの特徴点に対応する画像Ｂの特徴点の座標との距離が所定の閾値未満となる座標の個数を計数する。“ａ１＝ｐ２，ａ２＝ｑ２，ａ３＝ｒ２，ａ４＝ｓ２，ａ５＝ｔ２，ａ６＝ｕ２” 等の他の変換パラメータに関しても同様の処理を行う。パラメータ計算手段５は、求めた計数結果が最大となる変換パラメータを、アフィン変換での適切な変換パラメータであると決定する。
【００６０】
ステップＳ６でホモグラフィ変換が新たに選択された後に、ステップＳ１から処理をやり直してステップＳ３に移行した場合にも、同様の処理を行って、ホモグラフィ変換での適切な変換パラメータａ１〜ａ８の値を決定すればよい。
【００６１】
なお、既に説明したように、上記の例は、ＲＡＮＳＡＣアルゴリズムによる変換パラメータ計算の一例であり、変換パラメータの計算方法は、上記の例に限定されない。
【００６２】
ステップＳ６で新たに座標変換パラメータを選択し、ステップＳ１以降の処理を繰り返すループ処理において、モデル適正判定手段６が、選択されている座標変換モデルが画像Ａから画像Ｂへの変換として適切と判定したならば（ステップＳ５のＹｅｓ）、モデル適正判定手段６は、その直前のステップＳ４で計算された変換パラメータを、画像Ａから画像Ｂへの変換を表現した変換パラメータとして確定する（ステップＳ８）。
【００６３】
また、予め定めた座標変換モデルのうち、最も自由度が高い座標変換モデルを選択している場合に、ステップＳ６に移行し、ステップＳ６で次の座標変換モデルを選択できない状態となったときにも（ステップＳ７のＮｏ）、モデル適正判定手段６は、その直前のステップＳ４で計算された変換パラメータを、画像Ａから画像Ｂへの変換を表現した変換パラメータとして確定する（ステップＳ８）。
【００６４】
本実施形態によれば、モデル選択手段４が、変換の自由度が低い方から順に座標変換モデルを選択し、その座標変換モデルにおける変換式のパラメータをパラメータ計算手段５が計算する。そして、モデル適切性判定手段６が、画像Ａ内の特徴点に対応する画像Ｂ内の特徴点の座標と、その画像Ａ内の特徴点の座標を変換パラメータで変換した座標との差の大きさに応じて、選択されている座標変換モデルが画像Ａから画像Ｂへの変換として適切か否かを判定し、適切でなければ、モデル選択手段４がより自由度の大きい座標変換モデルを選択する。このような構成により、処理対象とする画像Ａ，Ｂに対して適切かつ必要最小限の自由度を持った座標変換モデルを特定して、その座標変換モデルにおけるパラメータとして、画像Ａから画像Ｂへの適切な変換パラメータを得ることができる。また、その結果、画像Ａから画像Ｂへの画像変換（位置合わせ）の精度を向上させることができる。
【００６５】
なお、図２では、ステップＳ６でより自由度が高い変換モデルを選択した場合に（ステップＳ７のＹｅｓ）、ステップＳ１以降の処理を繰り返す場合を示しているが、ステップＳ３以降の処理を繰り返してもよい。すなわち、ステップＳ１，Ｓ２を再度実行して、特徴点検出および特徴点の対応付けをやり直してもよいし、あるいは、既に対応付けの済んだ特徴点の組を用いてステップＳ３から処理をやり直してもよい。ステップＳ３から処理をやり直す場合には、新たに選択された座標変換モデルに関して変換パラメータを計算するときに、以前に選択された座標変換モデルに関して変換パラメータを計算する際に既に対応付けられていた特徴点の組を用いることになる。
【００６６】
また、上記の実施形態では、平行移動変換、アフィン変換、ホモグラフィ変換の順に選択する場合を示したが、選択対象となる座標変換モデルの組み合わせは、上記の３つの変換の組み合わせに限定されない。例えば、アフィン変換、ホモグラフィ変換の順に選択する構成であってもよい。また、平行移動変換、アフィン変換、ホモグラフィ変換以外の座標変換モデルを選択してもよい。
【００６７】
また、上記の実施形態では、モデル選択手段４が座標変換モデルを１つずつ選択し、選択された座標変換モデル毎にループ処理を実行する場合を示した。このようなループ処理を実行するのではなく、各座標変換モデルに対する処理を並列に行ってもよい。例えば、ステップＳ１，Ｓ２を実行した後、パラメータ計算手段５が、平行移動変換に関する変換パラメータ計算と、アフィン変換に関する変換パラメータ計算と、ホモグラフィ変換に関する変換パラメータ計算とをそれぞれ並列に行ってもよい。すなわち、複数種類の座標変換モデルに対するステップＳ３の処理を並列に行ってもよい。その後、モデル適切性判定手段６が、座標変換モデル毎に、平均再投影誤差の計算を行い（ステップＳ４）、座標変換モデルの適切性の判定（ステップＳ５）を行う。そして、ステップＳ５で、平均再投影誤差が誤差閾値以下となっている座標変換モデルを適切な座標変換モデルと決定し、その座標変換モデルに関して計算した変換パラメータを、画像Ａから画像Ｂへの変換パラメータとして確定する。平均再投影誤差が誤差閾値以下となっている座標変換モデルが複数存在する場合には、その中で自由度が最も低い座標変換モデルを、適切な座標変換モデルとして決定すればよい。また、平均再投影誤差が誤差閾値以下となっている座標変換モデルが存在しない場合には、予め定めた座標変換モデルのうち、自由度が最も高い座標変換モデルを適切な変換モデルとして決定すればよい。
【００６８】
実施形態２．
第２の実施形態の画像変換パラメータ算出装置は、画像から特徴点を検出する際に、予め定められた所定数以上の特徴点を検出することにより、十分な数の特徴点を確保する。
【００６９】
図３は、本発明の第２の実施形態の画像変換パラメータ算出装置の例を示すブロック図である。第１の実施形態と同様の構成要素については、図１と同一の符号を付し、詳細な説明を省略する。第２の実施形態の画像変換パラメータ算出装置１０は、特徴点検出手段２０と、対応特徴点特定手段３と、モデル選択手段４と、パラメータ計算手段５と、モデル適切性判定手段６とを備える。対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５およびモデル適切性判定手段６は、第１の実施形態と同様である。
【００７０】
特徴点検出手段２０は、入力された各画像Ａ，Ｂから特徴点を検出する。第１の実施形態では、特徴点検出方法は特に限定していない。これに対し、第２の実施形態において、特徴点検出手段２０は、画像の個々の画素に対して、特徴点検出用オペレータの演算を行う。そして、特徴点検出手段２０は、画像の画素に対して、ラスタスキャン順に、特徴点検出用オペレータの演算結果が極大になっているかを判定し、極大になっている画素を分類する。この分類処理では、特徴点検出手段２０は、特徴点検出用オペレータの演算結果として計算され得る最小値から最大値までの範囲を分割した各区間のうちのどの区間に、画素に対する演算結果が属するかを判定して、画素をその区間に分類する。特徴点検出手段２０は、演算結果が極大となる各画素に対してこの分類処理を行った後、演算結果のとり得る最大値に近い方の区間から順に区間を選択し、選択した区間に分類した画素を累積加算していく。その累積加算結果が、所定数数以上になった時点で区間の選択を停止する。この結果、特徴点検出手段２０は、演算結果に対するソーティング処理を行うことなく、所定数以上の特徴点を得ることができる。
【００７１】
図４は、画素に対する特徴点検出用オペレータの演算結果を模式的に示す説明図である。図４に示す横軸は、１つの画像内の個々の画素の識別情報（例えば、座標値）を示す。また、縦軸は、各画素に対する特徴点検出用オペレータの演算結果の値を示す。従って、図４では、画素毎の特徴点検出用オペレータの演算結果の変化を模式的に表している。図５は、図４に示す演算結果の変化において演算結果が極大となる箇所を示す説明図である。図５では、演算結果が極大となる箇所を丸印で囲んで示している。特徴点検出手段２０は、ラスタスキャン順に、演算結果がこのような極大となる画素であるかを判定し、演算結果が極大となる画素（特徴点）に対して、上述のように分類処理を行う。そして、特徴点の分類に用いた区間を順に選択していくことによって、演算結果が極大となる画素を演算結果の値の降順に一つ一つ順序づけるソーティング処理は行わずに、特徴点を選択する。なお、本実施形態では、ラスタスキャン順に、演算結果が極大となる画素であるかを判定していく場合を例示するが、このスキャン順は例示であり、特徴点検出手段２０は、ラスタスキャン順以外の順にこの処理を行ってもよい。
【００７２】
特徴点検出手段２０は、具体的には、オペレータ演算手段２１と、特徴点分類手段２２と、分類結果記憶手段２３と、特徴点選択手段２４とを含む。
【００７３】
オペレータ演算手段２１は、画像内の個々の画素に対して、特徴点検出用オペレータの演算を行う。本実施形態では、特徴点検出用オペレータとしてHarrisのインタレストオペレータを用いる場合を例にして説明するが、演算結果が極大となる画素を特徴点として選択することが可能なオペレータであれば、Harrisのインタレストオペレータ以外のオペレータであってもよい。
【００７４】
特徴点分類手段２２は、Harrisのインタレストオペレータの演算結果が極大となる画素である特徴点を、ラスタスキャン順に、その演算結果の値に応じて分類する。この分類を行えるようにするため、Harrisのインタレストオペレータの演算結果の値がとり得る範囲を、予め複数の区間に分割し、各区間の範囲を定めておく。特徴点分類手段２２は、ラスタスキャン順に、Harrisのインタレストオペレータの演算結果が極大となる画素（すなわち特徴点）を、その演算結果がどの区間に属するかを判定し、分類する。
【００７５】
図６は、演算結果の値がとり得る範囲を分割した各区間の例を示す。図６に示す縦軸および横軸は、図４と同様である。Harrisのインタレストオペレータの演算結果の値がとり得る最小値をＨｍｉｎとし、最大値をＨｍａｘとする。Ｈｍｉｎ〜Ｈｍａｘの範囲を分割して、複数の区間を予め定めておけばよい。Ｈｍｉｎ〜Ｈｍａｘの範囲を分割する場合には、例えば、各区間が均等になるように分割を行えばよい。ただし、この分割方法に限定されるわけではなく、各区間の範囲の大きさが異なるように分割してもよい。図６に示す例では、Ｈ３〜Ｈｍａｘの範囲を区間ｈ１と定め、同様に、Ｈ２〜Ｈ３の範囲、Ｈ１〜Ｈ２の範囲、Ｈｍｉｎ〜Ｈ１の範囲をそれぞれ、区間ｈ２，ｈ３，ｈ４と定める場合を例示している。なお、区間の境界となる値（本例ではＨ１，Ｈ２，Ｈ３）は、いずれか一方の区間に振り分ければよい。以下、個々の区間に該当する演算結果の範囲を区間該当範囲と記す。
【００７６】
図７は、特徴点の分類を模式的に示す説明図である。図７に例示する特徴点（極大点）が得られた場合、特徴点分類手段２２は、各特徴点を、Harrisのインタレストオペレータの演算結果の値が属する区間の特徴点として分類する。本例では、区間ｈ２に３つの特徴点が分類され、他の区間ｈ１，ｈ３，ｈ４には１つずつ特徴点が分類されることになる。
【００７７】
分類結果記憶手段２３は、特徴点分類手段２２による特徴点の分類結果を記憶する記憶装置である。分類結果記憶手段２３は、例えば、区間毎に、分類された特徴点の座標値（特徴点識別情報）、および分類された特徴点の総数をまとめたテーブルを記憶する。以下のこのテーブルを特徴点テーブルと記す。図８に特徴点テーブルの例を示す。図８は、図７に示す各区間に特徴点を分類した場合の例を示している。また、図８では、便宜上、特徴点座標を模式的に１，２・・等の番号で図示している。図８に示す例では、区間ｈ１には、１つの特徴点が分類され、その特徴点座標が「１」であることを示している。同様に、区間ｈ２には、１つの特徴点が分類され、その特徴点座標が「２」、「３」、「４」であることを示している。また、区間ｈ３には、１つの特徴点が分類され、その特徴点座標が「５」であることを示している。また、区間ｈ４には、１つの特徴点が分類され、その特徴点座標が「６」であることを示している。
【００７８】
特徴点選択手段２４は、区間該当範囲がＨｍａｘに近い方の区間から、区間を順次選択して、選択した区間に属する特徴点数を累積加算していく。特徴点選択手段２４は、選択した区間に属する特徴点数を、特徴点テーブルから読み込めばよい。Ｈｍａｘは、Harrisのインタレストオペレータの演算結果のとり得る最大値である。そして、その加算結果が所定数以上となったならば、区間の選択を中止し、それまでに選択した各区間に分類されている特徴点を選択する。
【００７９】
上記の構成により、特徴点検出手段２０は、入力された画像Ａから、所定個数以上の特徴点を検出する。また、特徴点検出手段２０は、入力されたもう一方の画像Ｂからも、所定個数以上の特徴点を検出する。
【００８０】
対等特徴点決定手段３は、特徴点検出手段２０によって画像Ａ，Ｂから検出された特徴点を対象にして、第１の実施形態と同様の処理を実行する。
【００８１】
本実施形態における特徴点検出手段２０（オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３、特徴点選択手段２４）は、例えば、画像変換パラメータ算出プログラムに従って動作するコンピュータのＣＰＵによって実現される。例えば、コンピュータのプログラム記憶手段（図示せず）に記憶された画像変換パラメータ算出プログラムをＣＰＵが読み込み、ＣＰＵがそのプログラムに従って、特徴点検出手段２０（オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３、特徴点選択手段２４）、対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５、およびモデル適切性判定手段６として動作する。なお、分類結果記憶手段２３は、例えば、ＣＰＵが備えるメモリによって実現されるが、ＣＰＵとの外部に設けられた記憶装置であってもよい。
【００８２】
また、特徴点検出手段２０、対応特徴点特定手段３、モデル選択手段４、パラメータ計算手段５、およびモデル適切性判定手段６がそれぞれ別々の回路として実現されていてもよい。特徴点検出手段２０に関しても、オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３および特徴点選択手段２４がそれぞれ別々の回路として実現されていてもよい。
【００８３】
次に、第２の実施形態の動作について説明する。
第２の実施形態の画像変換パラメータ算出装置１０は、第１の実施形態と同様にステップＳ１〜Ｓ８の動作（図２参照。）を実行することにより、一方の画像Ａから他方の画像Ｂへの変換パラメータを確定する。ただし、画像Ａ，Ｂそれぞれから特徴点を検出する処理（ステップＳ１）において、特徴点検出手段２０は、以下のように動作する。
【００８４】
図９は、第２の実施形態における特徴点検出処理の処理経過の例を示すフローチャートである。特徴点検出手段２０は、入力された画像Ａ，Ｂそれぞれに対して図９に示す処理を行う。以下に示す例では、Harrisのインタレストオペレータの演算結果の値がとり得る範囲を分割した各区間を、区間該当範囲がＨｍａｘに近い方から順番に、１，２，・・・という区間識別番号で識別しているものとする。そして、特徴点選択手段２４が選択している区間の区間識別番号を変数ｍで表すこととする。一つの画像に対して特徴点検出処理を開始するときには、特徴点選択手段２４は、ｍの値を１に初期化するものとする。すなわち、区間該当範囲がＨｍａｘに最も近い区間を最初に選択することになる。
【００８５】
画像Ａから特徴点を検出する場合を例にすると、オペレータ演算手段２１は、画像Ａ内の個々の画素に対して、Harrisのインタレストオペレータの演算を行う（ステップＳ１１）。
【００８６】
次に、特徴点分類手段２２は、ステップＳ１１で計算された演算結果が極大となっているか否かをラスタスキャン順に各画素について判定し、演算結果が極大となっている画素を特徴点として定める。そして、特徴点分類手段２２は、その特徴点をラスタスキャン順に、予め定められた区間のいずれかに分類する。この分類処理では、特徴点をステップＳ１１における演算結果の値に応じて、いずれかの区間に分類すればよい。そして、特徴点分類手段２２は、分類結果を分類結果記憶手段２３に記憶させる（ステップＳ１２）。換言すれば、特徴点分類手段２２は、各区間に分類した特徴点の特徴点識別情報および各区間の特徴点総数を特徴点テーブルに登録する。例えば、特徴点分類手段２２は、特徴点テーブル（図８参照）の各区間の特徴点総数をそれぞれ０に初期化し、特徴点座標に関しても何も格納されていない状態に初期化する。そして、特徴点分類手段２２は、ステップＳ１１の演算結果が極大となっている画素である特徴点に関して、その演算結果の値がどの区間に属するかを判定し、その特徴点をその区間に分類する。そして、特徴点分類手段２２は、特徴点テーブルにおいて、その区間に対応する特徴点総数の値を１加算し、その区間に対応する特徴点座標に、分類した特徴点の座標を格納する。特徴点分類手段２２は、この処理をテップＳ１１の演算結果が極大となっている特徴点毎に実行する。この結果、図８に例示する特徴点テーブルが得られる。
【００８７】
ステップＳ１２の後、特徴点選択手段２４は、選択している区間の特徴点総数を読み取り、それまで選択した各区間の特徴点総数に累積加算する。そして、その累積加算結果が、予め定められた所定数以上になっているか否かを判定する（ステップＳ１３）。すなわち、特徴点選択手段２４は、以下の式（８）で表される条件が満たされているか否かを判定する。
【００８８】
【数２】
【００８９】
式（８）において、ｃｋは、区間識別番号がｋである区間に分類された特徴点の総数である。また、特徴点選択手段２４は、区間該当範囲がＨｍａｘに近い方から順番に区間を選択していく。従って、式（８）の左辺は、それまで選択した各区間の特徴点総数を累積加算した値を意味する。また、式（８）の右辺に示すｔｈｒｅｓｈは、予め定められた所定数を表す定数である。
【００９０】
式（８）に示す条件が成立していないということは、区間該当範囲がＨｍａｘに近い方から順番に選択してきた各区間の特徴点の総和が、所定数に達していないということである。この場合（ステップＳ１３のＮｏ）、特徴点選択手段２４は、選択している区間の区間識別番号を表す変数ｍの値を１インクリメントする（ステップＳ１４）。変数ｍを１インクリメントするということは、それまで選択していた区間に隣接している区間であって、Ｈｍａｘから遠い方の区間を新たに選択することを意味する。従って、特徴点選択手段２４は、区間該当範囲がＨｍａｘに近い方から順番に区間を選択していくことになる。
【００９１】
また、式（８）に示す条件が成立しているということは、区間該当範囲がＨｍａｘに近い方から順番に選択してきた各区間の特徴点の総和が所定数に達したということである。この場合８ステップＳ１３のＹｅｓ）、特徴点選択手段２４は、区間識別番号が１からｍまでの各区間に分類された各特徴点を選択する（ステップＳ１５）。ステップＳ１５で選択された特徴点が、画像Ａから検出された特徴点である。
【００９２】
なお、ステップＳ１３において、特徴点選択手段２４は、それまでに選択した各区間の特徴点総数の累積加算結果を求める際には、その都度、式（８）の左辺の計算を行ってもよい。
【００９３】
あるいは、特徴点選択手段２４は、ｊ番目の区間を選択したときに、１番目からｊ番目までの各区間の特徴点の総和を求め、その総和が、ｔｈｒｅｓｈ未満である場合には、求めた総和を記憶してもよい。そして、ステップＳ１４を経て再度ステップＳ１３に移行したときには、記憶している総和に、ｊ＋１番目の区間の特徴点総数を加算することによって、１番目からｊ＋１番目までの各区間の特徴点の総和を計算してもよい。この計算方法によれば、ステップＳ１３に移行する毎に式（８）の左辺の計算を行う場合よりも、計算量を少なくすることができる。なお、上記のｊは１以上の任意の区間識別番号である。
【００９４】
ステップＳ１３，Ｓ１４のループ処理の具体例を示す。本例では、図８に例示する特徴点テーブルがステップＳ１２で作成されているものとする。また、図８に示す例では、区間ｈ１〜ｈ４の区間識別番号はそれぞれ１〜４である。また、ここでは、ｔｈｒｅｓｈ＝３である場合を例に説明する。最初にステップＳ１３に移行したときには、ｍ＝１である。すなわち、特徴点選択手段２４は、区間ｈ１を選択している。区間ｈ１に分類されている特徴点数は１個であるので（図８参照）、選択した各区間の特徴点累積加算結果は１である。よって、式（８）の条件は満たさないので、特徴点選択手段２４は、変数ｍの値を２に更新し、区間ｈ２を選択する。区間ｈ２に分類されている特徴点数は３個であるので（図８参照）、選択した各区間の特徴点累積加算結果は１＋３＝４となり、ｔｈｒｅｓｈ以上となる。よって、特徴点選択手段２４は、ステップＳ１５に移行し、区間ｈ１，ｈ２に分類された特徴点を選択する。
【００９５】
以上の説明において、特徴点検出手段２０が画像Ａから特徴点を検出する場合を示したが、特徴点検出手段２０は、特徴点Ｂからも同様の処理で特徴点を検出する。特徴点検出手段２０が画像Ａ，Ｂからそれぞれ所定数以上の特徴点を検出したことにより、本実施形態におけるステップＳ１（図２参照）が完了する。ステップＳ１の後、画像変換パラメータ算出出装置１０は、第１の実施形態と同様にステップＳ２以降の処理を実行する。ステップＳ２以降の処理は、第１の実施形態と同様であり、説明を省略する。
【００９６】
本実施形態によれば、入力される画像Ａ，Ｂそれぞれから所定数以上の特徴点を検出することができる。従って、十分な数の特徴点を得ることができ、画像Ａから画像Ｂへの画像変換（位置合わせ）の精度を向上させることができる。
【００９７】
また、本実施形態では、特徴点分類手段２２は、特徴点をその演算結果に応じた区間に分類する。そして、特徴点選択手段２４が、区間該当範囲がＨｍａｘに近い方から区間を選択し、選択した区間における特徴点数の累積加算結果が所定数以上となったときに、それまでに選択した各区間に分類された各特徴点を選択する。従って、演算結果が極大となる特徴点を、演算結果の値の降順に一つ一つ順序づけるソーティング処理が不要となる。その結果、効率的に所定数以上の特徴点を検出することができる。
【００９８】
実施形態３．
第２の実施形態で示した特徴点検出手段２０を、特徴点検出装置として実現してもよい。第３の実施形態として、このような特徴点検出装置を説明する。図１０は、本発明の第３の実施形態の特徴点検出装置の例を示すブロック図である。第２の実施形態における特徴点検出手段２０の構成要素と同様の構成要素は、図３と同一の符号を付して詳細な説明を省略する。本実施形態の特徴点検出装置２７は、オペレータ演算手段２１と、特徴点分類手段２２と、分類結果記憶手段２３と、特徴点選択手段２４とを含む。
【００９９】
特徴点検出装置２７は、入力された画像から特徴点を検出する。本実施形態では、第２の実施形態と同様に、画像Ａ，Ｂのように変換パラメータ算出の対象となる複数の画像が入力されてもよい。あるいは、１つの画像のみが入力されてもよい。特徴点検出装置２７は、入力された個々の画像毎に特徴点を検出する。
【０１００】
本実施形態におけるオペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３および特徴点選択手段２４（図１０参照）は、第２の実施形態における特徴点検出手段２０が備えるオペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３および特徴点選択手段２４（図３参照）と同様である。
【０１０１】
すなわち、オペレータ演算手段２１は、画像内の個々の画素に対して、特徴点検出用オペレータの演算を行う。第２の実施形態と同様に、特徴点検出用オペレータとしてHarrisのインタレストオペレータを用いる場合を例にして説明するが、演算結果が極大となる画素を特徴点として選択することが可能なオペレータであれば、Harrisのインタレストオペレータ以外のオペレータであってもよい。
【０１０２】
特徴点分類手段２２は、Harrisのインタレストオペレータの演算結果が極大となる画素である特徴点を、その演算結果の値に応じて分類する。分類結果記憶手段２３は、特徴点分類手段２２による特徴点の分類結果を記憶する記憶装置である。特徴点分類手段２２は、例えば、図８に例示するような特徴点テーブルを分類結果として分類結果記憶手段２３に記憶させる。
【０１０３】
特徴点選択手段２４は、区間該当範囲がＨｍａｘに近い方の区間から、区間を順次選択して、選択した区間に属する特徴点数を累積加算する。そして、その加算結果が所定数以上となったならば、区間の選択を中止し、それまでに選択した各区間に分類されている特徴点を選択する。
【０１０４】
オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３および特徴点選択手段２４は、例えば、特徴点検出プログラムに従って動作するコンピュータのＣＰＵによって実現される。コンピュータのプログラム記憶手段（図示せず）に記憶された特徴点検出プログラムをＣＰＵが読み込み、ＣＰＵがそのプログラムに従って、オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３、特徴点選択手段２４として動作する。分類結果記憶手段２３は、例えば、ＣＰＵが備えるメモリによって実現されるが、ＣＰＵとの外部に設けられた記憶装置であってもよい。
【０１０５】
また、オペレータ演算手段２１、特徴点分類手段２２、分類結果記憶手段２３および特徴点選択手段２４がそれぞれ別々の回路として実現されていてもよい。
【０１０６】
第３の実施形態の特徴点検出装置２７の処理経過は、第２の実施形態で説明したステップＳ１１〜Ｓ１５と同様である。この動作により、特徴点検出装置２７は、入力された画像から所定数以上の特徴点を検出する。
【０１０７】
本実施形態においても、入力された画像から所定数以上の特徴点を検出することができる。また、第２の実施形態と同様に、特徴点検出用オペレータの演算結果が極大となる特徴点を演算結果の値の降順に一つ一つ順序づけるソーティング処理が不要となる。従って、効率的に所定数以上の特徴点を検出することができる。
【０１０８】
第３の実施形態の特徴点検出装置は、第２の実施形態の画像変換パラメータ算出装置の外にも、画像から検出された特徴点を用いて処理を行う種々の画像処理装置で利用可能である。
【０１０９】
次に、本発明の最小構成について説明する。図１１は、本発明の画像変換パラメータ算出装置の最小構成の例を示すブロック図である。本発明の画像変換パラメータ算出装置１０は、特徴点検出手段２０と、対応特徴点特定手段３と、パラメータ計算手段５と、モデル適切性判定手段６とを備える。
【０１１０】
特徴点検出手段２０は、入力される第１画像（例えば、画像Ａ）および第２画像（例えば、画像Ｂ）からそれぞれ所定数以上の特徴点を検出する。
【０１１１】
対応特徴点特定手段３は、第１画像および第２画像の間で対応する特徴点の組を特定する。
【０１１２】
パラメータ計算手段５は、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算する。
【０１１３】
モデル適切性判定手段６は、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定する。
【０１１４】
また、特徴点検出手段２０は、オペレータ演算手段２１と、特徴点分類手段２２と、特徴点選択手段２４とを有する。
【０１１５】
オペレータ演算手段２１は、画像内の各画素に対して特徴点検出用オペレータ（例えば、Harrisのインタレストオペレータ）の演算を行う。
【０１１６】
特徴点分類手段２２は、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する。
【０１１７】
特徴点選択手段２４は、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する。
【０１１８】
そして、対応特徴点特定手段３は、特徴点選択手段２４が選択した特徴点の中から特徴点の組を特定する。
【０１１９】
以上のような構成により、第１画像および第２画像の組み合わせに関して適切な座標変換モデルを特定して、その座標変換モデルにおけるパラメータとして、第１画像から第２画像への適切な変換パラメータを得ることができる。また、その結果、第１画像から第２画像への画像変換（位置合わせ）の精度を向上させることができる。
【０１２０】
また、特徴点検出用オペレータの演算結果が極大となる特徴点を演算結果の値の降順に一つ一つ順序づけるソーティング処理を行うことなく、所定数以上の特徴点を検出することができる。従って、画像から効率的に所定数以上の特徴点を検出できる。
【０１２１】
なお、上記の実施形態には、以下の（１）〜（７）に示すような画像変換パラメータ算出装置が開示されている。
【０１２２】
（１）入力される第１画像（例えば、画像Ａ）および第２画像（例えば、画像Ｂ）からそれぞれ所定数以上の特徴点を検出する特徴点検出手段（例えば、特徴点検出手段２０）と、第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定手段（例えば、対応特徴点特定手段３）と、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算手段（例えば、パラメータ計算手段５）と、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定手段（例えば、モデル適切性判定手段６）とを備え、特徴点検出手段が、画像内の各画素に対して特徴点検出用オペレータ（例えば、Harrisのインタレストオペレータ）の演算を行うオペレータ演算手段（例えば、オペレータ演算手段２１）と、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類手段（例えば、特徴点分類手段２２）と、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数（例えば、定数ｔｈｒｅｓｈ）以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択手段（例えば、特徴点選択手段２４）を有し、対応特徴点特定手段が、特徴点選択手段が選択した特徴点の中から特徴点の組を特定することを特徴とする画像変換パラメータ算出装置。
【０１２３】
（２）モデル適切性判定手段が、対応する特徴点の組毎に、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差を計算し、組毎に計算した差の平均値（例えば、平均再投影誤差Ｅ）が、予め定められた閾値以下である場合に、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であると判定し、その平均値が閾値より大きい場合に、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切でないと判定する画像変換パラメータ算出装置。
【０１２４】
（３）座標変換モデルを選択する座標変換モデル選択手段（例えば、モデル選択手段４）を備え、パラメータ計算手段が、選択された座標変換モデルにおける変換パラメータを計算し、座標変換モデル選択手段が、モデル適切性判定手段によって座標変換モデルが第１画像から第２画像への変換として適切でないと判定された場合に、その座標変換モデルよりも変換の自由度が高い座標変換モデルを新たに選択する画像変換パラメータ算出装置。
【０１２５】
（４）パラメータ計算手段が、新たに選択された座標変換モデルに関して変換パラメータを計算するときに、以前に選択された座標変換モデルに関して変換パラメータを計算する際に既に対応付けられていた特徴点の組を用いる画像変換パラメータ算出装置。
【０１２６】
（５）パラメータ計算手段が、複数の座標変換モデルに関して並列に変換パラメータを計算する画像変換パラメータ算出装置。
【０１２７】
（６）特徴点分類手段による特徴点の分類結果（例えば、図８に例示する特徴点テーブル）を記憶する分類結果記憶手段（例えば、分類結果記憶手段２３）を備え、特徴点分類手段が、複数の区間毎に、分類した特徴点の数、および分類した各特徴点を識別する特徴点識別情報を分類結果記憶手段に記憶させ、特徴点選択手段が、選択した区間に分類された特徴点数を分類結果記憶手段から読み込む画像変換パラメータ算出装置。
【０１２８】
（７）入力される第１画像および第２画像からそれぞれ特徴点を検出する特徴点検出手段と、第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定手段と、変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算手段と、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、その特徴点に対応する第２画像の特徴点の座標と、変換によって得た座標との差に基づいて、その変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定手段とを備えることを特徴とする画像変換パラメータ算出装置。
【０１２９】
また、上記の実施形態には、以下の（８），（９）に示すような特徴点検出装置が開示されている。
【０１３０】
（８）画像内の各画素に対して特徴点検出用オペレータの演算を行うオペレータ演算手段（例えば、オペレータ演算手段１０）と、特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類手段（例えば、特徴点分類手段２２）と、区間に該当する範囲がその最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択手段（例えば、特徴点選択手段２４）とを備えることを特徴とする特徴点検出装置。
【０１３１】
（９）特徴点分類手段による特徴点の分類結果を記憶する分類結果記憶手段（例えば、分類結果記憶手段２３）を備え、特徴点分類手段が、複数の区間毎に、分類した特徴点の数、および分類した各特徴点を識別する特徴点識別情報を分類結果記憶手段に記憶させ、特徴点選択手段が、選択した区間に分類された特徴点数を分類結果記憶手段から読み込む特徴点検出装置。
【産業上の利用可能性】
【０１３２】
本発明は、一つの画像に含まれる物体の位置が他の画像におけるその物体の位置と同じになるように画像を変換するための変換パラメータを算出する画像変換パラメータ算出装置に好適に適用される。
【符号の説明】
【０１３３】
１，１０ 画像変換パラメータ算出装置
２，２０ 特徴点検出手段
３ 対応特徴点特定手段
４ モデル選択手段
５ パラメータ計算手段
６ モデル適切性判定手段
２１ オペレータ演算手段
２２ 特徴点分類手段
２３ 分類結果記憶手段
２４ 特徴点選択手段
２７ 特徴点検出装置
【特許請求の範囲】
【請求項１】
入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出する特徴点検出手段と、
第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定手段と、
変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、前記特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算手段と、
パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差に基づいて、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定手段とを備え、
前記特徴点検出手段は、
画像内の各画素に対して特徴点検出用オペレータの演算を行うオペレータ演算手段と、
特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類手段と、
区間に該当する範囲が前記最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が前記所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択手段を有し、
前記対応特徴点特定手段は、特徴点選択手段が選択した特徴点の中から特徴点の組を特定する
ことを特徴とする画像変換パラメータ算出装置。
【請求項２】
モデル適切性判定手段は、
対応する特徴点の組毎に、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差を計算し、組毎に計算した差の平均値が、予め定められた閾値以下である場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であると判定し、前記平均値が前記閾値より大きい場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切でないと判定する
請求項１に記載の画像変換パラメータ算出装置。
【請求項３】
座標変換モデルを選択する座標変換モデル選択手段を備え、
パラメータ計算手段は、選択された座標変換モデルにおける変換パラメータを計算し、
前記座標変換モデル選択手段は、モデル適切性判定手段によって前記座標変換モデルが第１画像から第２画像への変換として適切でないと判定された場合に、前記座標変換モデルよりも変換の自由度が高い座標変換モデルを新たに選択する
請求項１または請求項２に記載の画像変換パラメータ算出装置。
【請求項４】
パラメータ計算手段は、新たに選択された座標変換モデルに関して変換パラメータを計算するときに、以前に選択された座標変換モデルに関して変換パラメータを計算する際に既に対応付けられていた特徴点の組を用いる
請求項３に記載の画像変換パラメータ算出装置。
【請求項５】
パラメータ計算手段は、複数の座標変換モデルに関して並列に変換パラメータを計算する請求項１または請求項２に記載の画像変換パラメータ算出装置。
【請求項６】
特徴点分類手段による特徴点の分類結果を記憶する分類結果記憶手段を備え、
特徴点分類手段は、複数の区間毎に、分類した特徴点の数、および分類した各特徴点を識別する特徴点識別情報を前記分類結果記憶手段に記憶させ、
特徴点選択手段は、選択した区間に分類された特徴点数を前記分類結果記憶手段から読み込む
請求項１から請求項５のうちのいずれか１項に記載の画像変換パラメータ算出装置。
【請求項７】
入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出し、
第１画像および第２画像の間で対応する特徴点の組を特定し、
変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、前記特徴点の組を用いて、座標変換を表す変換パラメータを計算し、
計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差に基づいて、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算した変換パラメータを第１画像から第２画像への変換パラメータとして確定し、
入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出するときに、
画像内の各画素に対して特徴点検出用オペレータの演算を行い、
特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類し、
区間に該当する範囲が前記最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が前記所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する
ことを特徴とする画像変換パラメータ算出方法。
【請求項８】
対応する特徴点の組毎に、変換パラメータを用いて第１画像の特徴点の座標を変換し、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差を計算し、組毎に計算した差の平均値が、予め定められた閾値以下である場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であると判定し、前記平均値が前記閾値より大きい場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切でないと判定する
請求項７に記載の画像変換パラメータ算出方法。
【請求項９】
コンピュータに、
入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出する特徴点検出処理、
第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定処理、
変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、前記特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算処理、および、
パラメータ計算処理で計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差に基づいて、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定処理を実行させ、
前記特徴点検出処理で、
画像内の各画素に対して特徴点検出用オペレータの演算を行うオペレータ演算処理、
特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類処理、および、
区間に該当する範囲が前記最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が前記所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択処理を実行させ、
前記対応特徴点特定処理で、前記特徴点選択処理で選択された特徴点の中から特徴点の組を特定させる
ための画像変換パラメータ算出プログラム。
【請求項１０】
コンピュータに、
モデル適切性判定処理で、
対応する特徴点の組毎に、パラメータ計算処理で計算させた変換パラメータを用いて第１画像の特徴点の座標を変換させ、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差を計算させ、組毎に計算した差の平均値が、予め定められた閾値以下である場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であると判定させ、前記平均値が前記閾値より大きい場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切でないと判定させる
請求項９に記載の画像変換パラメータ算出プログラム。
【請求項１】
入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出する特徴点検出手段と、
第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定手段と、
変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、前記特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算手段と、
パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差に基づいて、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定手段とを備え、
前記特徴点検出手段は、
画像内の各画素に対して特徴点検出用オペレータの演算を行うオペレータ演算手段と、
特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類手段と、
区間に該当する範囲が前記最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が前記所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択手段を有し、
前記対応特徴点特定手段は、特徴点選択手段が選択した特徴点の中から特徴点の組を特定する
ことを特徴とする画像変換パラメータ算出装置。
【請求項２】
モデル適切性判定手段は、
対応する特徴点の組毎に、パラメータ計算手段が計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差を計算し、組毎に計算した差の平均値が、予め定められた閾値以下である場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であると判定し、前記平均値が前記閾値より大きい場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切でないと判定する
請求項１に記載の画像変換パラメータ算出装置。
【請求項３】
座標変換モデルを選択する座標変換モデル選択手段を備え、
パラメータ計算手段は、選択された座標変換モデルにおける変換パラメータを計算し、
前記座標変換モデル選択手段は、モデル適切性判定手段によって前記座標変換モデルが第１画像から第２画像への変換として適切でないと判定された場合に、前記座標変換モデルよりも変換の自由度が高い座標変換モデルを新たに選択する
請求項１または請求項２に記載の画像変換パラメータ算出装置。
【請求項４】
パラメータ計算手段は、新たに選択された座標変換モデルに関して変換パラメータを計算するときに、以前に選択された座標変換モデルに関して変換パラメータを計算する際に既に対応付けられていた特徴点の組を用いる
請求項３に記載の画像変換パラメータ算出装置。
【請求項５】
パラメータ計算手段は、複数の座標変換モデルに関して並列に変換パラメータを計算する請求項１または請求項２に記載の画像変換パラメータ算出装置。
【請求項６】
特徴点分類手段による特徴点の分類結果を記憶する分類結果記憶手段を備え、
特徴点分類手段は、複数の区間毎に、分類した特徴点の数、および分類した各特徴点を識別する特徴点識別情報を前記分類結果記憶手段に記憶させ、
特徴点選択手段は、選択した区間に分類された特徴点数を前記分類結果記憶手段から読み込む
請求項１から請求項５のうちのいずれか１項に記載の画像変換パラメータ算出装置。
【請求項７】
入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出し、
第１画像および第２画像の間で対応する特徴点の組を特定し、
変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、前記特徴点の組を用いて、座標変換を表す変換パラメータを計算し、
計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差に基づいて、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算した変換パラメータを第１画像から第２画像への変換パラメータとして確定し、
入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出するときに、
画像内の各画素に対して特徴点検出用オペレータの演算を行い、
特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類し、
区間に該当する範囲が前記最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が前記所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する
ことを特徴とする画像変換パラメータ算出方法。
【請求項８】
対応する特徴点の組毎に、変換パラメータを用いて第１画像の特徴点の座標を変換し、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差を計算し、組毎に計算した差の平均値が、予め定められた閾値以下である場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であると判定し、前記平均値が前記閾値より大きい場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切でないと判定する
請求項７に記載の画像変換パラメータ算出方法。
【請求項９】
コンピュータに、
入力される第１画像および第２画像からそれぞれ所定数以上の特徴点を検出する特徴点検出処理、
第１画像および第２画像の間で対応する特徴点の組を特定する対応特徴点特定処理、
変換の自由度で分類した座標変換の種類を示す座標変換モデル毎に、前記特徴点の組を用いて、座標変換を表す変換パラメータを計算するパラメータ計算処理、および、
パラメータ計算処理で計算した変換パラメータを用いて第１画像の特徴点の座標を変換し、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差に基づいて、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であるか否かを判定し、適切であると判定した座標変換モデルに関して計算された変換パラメータを第１画像から第２画像への変換パラメータとして確定するモデル適切性判定処理を実行させ、
前記特徴点検出処理で、
画像内の各画素に対して特徴点検出用オペレータの演算を行うオペレータ演算処理、
特徴点検出用オペレータの演算結果が極大となる各画素をそれぞれ特徴点とし、各特徴点を特徴点検出用オペレータの演算結果に応じて、特徴点検出用オペレータの演算がとり得る最小値から最大値までの範囲を分割した複数の区間のいずれかに分類する特徴点分類処理、および、
区間に該当する範囲が前記最大値に近い方から区間を選択し、選択した区間に分類された特徴点数を累積加算し、特徴点数の累積加算結果が前記所定数以上となったときに、選択済みの各区間に分類された特徴点を選択する特徴点選択処理を実行させ、
前記対応特徴点特定処理で、前記特徴点選択処理で選択された特徴点の中から特徴点の組を特定させる
ための画像変換パラメータ算出プログラム。
【請求項１０】
コンピュータに、
モデル適切性判定処理で、
対応する特徴点の組毎に、パラメータ計算処理で計算させた変換パラメータを用いて第１画像の特徴点の座標を変換させ、当該特徴点に対応する第２画像の特徴点の座標と、前記変換によって得た座標との差を計算させ、組毎に計算した差の平均値が、予め定められた閾値以下である場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切であると判定させ、前記平均値が前記閾値より大きい場合に、前記変換パラメータに対応する座標変換モデルが第１画像から第２画像への変換として適切でないと判定させる
請求項９に記載の画像変換パラメータ算出プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１１−５３９３７（Ｐ２０１１−５３９３７Ａ）
【公開日】平成２３年３月１７日（２０１１．３．１７）
【国際特許分類】
【出願番号】特願２００９−２０２５９７（Ｐ２００９−２０２５９７）
【出願日】平成２１年９月２日（２００９．９．２）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２３年３月１７日（２０１１．３．１７）
【国際特許分類】
【出願日】平成２１年９月２日（２００９．９．２）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]