(57)【特許請求の範囲】
【請求項１】
撮像手段から得たビデオにおける連続するフレーム間のブレ量を求める情報処理装置であって、
前記撮像手段から得た、時間的に前後する第１のフレーム画像と第２のフレーム画像とを格納するためのメモリと、
前記メモリに格納された前記第１のフレーム画像と前記第２のフレーム画像に基づき、前記第１のフレーム画像に対する前記第２のフレーム画像のブレ量を検出する検出手段とを有し、
前記検出手段は、
前記第１及び第２のフレーム画像のそれぞれにおいて、４個の特徴点中の３個の特徴点を頂点とする三角形の面積を算出する面積算出手段と、
前記第１及び第２のフレーム画像のそれぞれにおいて、４個の基準特徴点を前記４個の特徴点へ変換する第１及び第２の変換行列を、当該４個の特徴点中の３個の特徴点を頂点とする複数の三角形同士の面積の比を用いて算出する第１の行列算出手段と、
前記第１及び第２の変換行列を用いて、前記第１のフレーム画像の４個の特徴点を前記第２のフレーム画像の４個の特徴点へ変換する第３の変換行列を算出する第２の行列算出手段と
を有することを特徴とする情報処理装置。
【請求項２】
前記３個の特徴点の配置が同一直線上にあるか否かを判定する判定手段をさらに有し、
該判定手段により前記３個の特徴点の配置が同一直線上にあると判定された場合に、前記第１の行列算出手段は、当該３個の特徴点を頂点とする三角形同士の面積の比を用いた計算を中止することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記判定手段は、前記３個の特徴点を頂点とする三角形の面積と所定の閾値とを比較することで、当該３個の特徴点の配置が同一直線上にあるか否かを判定することを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記第２の行列算出手段は、前記第２の変換行列に、前記第１の変換行列の逆行列を乗算することで、前記第３の変換行列を算出することを特徴とする請求項１に記載の情報処理装置。
【請求項５】
前記４個の基準特徴点は、原点を１頂点とする単位正方形の各頂点であることを特徴とする請求項１に記載の情報処理装置。
【請求項６】
撮像手段から得たビデオにおける連続するフレーム間のブレ量を求める情報処理装置の制御方法であって、
格納手段が、前記撮像手段から得た、時間的に前後する第１のフレーム画像と第２のフレーム画像とをメモリに格納する格納工程と、
検出手段が、前記メモリに格納された前記第１のフレーム画像と前記第２のフレーム画像に基づき、前記第１のフレーム画像と前記第２のフレーム画像の間のブレ量を検出する検出工程とを有し、
前記検出工程は、
面積算出手段が、第１及び第２のフレーム画像のそれぞれにおいて、４個の特徴点中の３個の特徴点を頂点とする三角形の面積を算出する面積算出工程と、
第１の行列算出手段が、前記第１及び第２のフレーム画像のそれぞれにおいて、４個の基準特徴点を前記４個の特徴点へ変換する第１及び第２の変換行列を、当該４個の特徴点中の３個の特徴点を頂点とする複数の三角形同士の面積の比を用いて算出する第１の行列算出工程と、
第２の行列算出手段が、前記第１及び第２の変換行列を用いて、前記第１のフレーム画像の４個の特徴点を前記第２のフレーム画像の４個の特徴点へ変換する第３の変換行列を算出する第２の行列算出工程と
を有する
ことを特徴とする情報処理装置の制御方法。
【請求項７】
コンピュータに読み込ませ実行させることで、前記コンピュータに請求項６の方法に記載の各工程を実行させるためのプログラム。
【請求項８】
請求項７に記載のプログラムを格納したコンピュータが読み取り可能な記憶媒体。
【請求項９】
複数のフレーム画像を含む動画像を撮像する撮像手段と、
前記動画像中の第１のフレーム画像に対して、該第１のフレーム画像に後続する第２のフレーム画像のブレ量を検出する検出手段とを有し、
前記検出手段が、
前記第１及び第２のフレーム画像のそれぞれにおいて、４個の特徴点中の３個の特徴点を頂点とする三角形の面積を算出する面積算出手段と、
前記第１及び第２のフレーム画像のそれぞれにおいて、４個の基準特徴点を前記４個の特徴点へ変換する第１及び第２の変換行列を、当該４個の特徴点中の３個の特徴点を頂点とする複数の三角形同士の面積の比を用いて算出する第１の行列算出手段と、
前記第１及び第２の変換行列を用いて、前記第１のフレーム画像の４個の特徴点を前記第２のフレーム画像の４個の特徴点へ変換する第３の変換行列を算出する第２の行列算出手段とを有することを特徴とするビデオカメラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２次元又は３次元座標データを２次元座標データに変換するための座標変換行列の演算技術に関するものである。
【背景技術】
【０００２】
射影変換には２次元空間から２次元空間への変換であるホモグラフィ変換や、３次元空間から３次元空間への変換などがある。２つの空間の対応点の座標データから前記ホモグラフィ変換行列や３次元射影変換行列を計算することはコンピュータビジョンにおいて基本的な処理である。これらの行列は、パノラマ画像の生成、プロジェクタの投影位置の補正、平面パターンを用いるカメラ校正、対象物の３次元形状推定・復元、道路面上の障害物検出など幅広い用途で利用することが出来る。
【０００３】
以下、ホモグラフィ行列を利用して実現する動画撮影カメラの防振機能の原理、ホモグラフィ行列の求め方を説明した後、その課題について言及する。
【０００４】
動画撮影して得られる連続フレームのフレーム間のブレを幾何変換行列として検出し、該幾何変換行列を十数フレームに渡って平滑化した行列で、画像を逆補正することにより、フレーム間のブレを平滑化でき、動画撮影時の手ぶれ防振機能を実現できる。
【０００５】
カメラから被写体までの距離が十分に離れており、被写体の各注目点が同一平面上に存在すると見なしても問題無い場合、フレーム間のブレを表現する幾何変換行列はホモグラフィ行列で表すことができ、フレーム間の画素の座標は式（１）で対応付けられる。
【数１】
0006581359.tif 000002
【０００６】
式（１）における右辺の３行３列の行列がホモグラフィ行列であり、前のフレームの（ｕ，ｖ）座標の画素は、（ｘ，ｙ）座標に変換される。また、式（１）は、同次座標を用いることにより、非線形な射影変換を線形演算で表現できるようにしたものである。
【０００７】
式（１）の３行３列の右下の９番目の要素を規格化と称し、１に設定すると、他の８つの要素が自由な値をとることが可能であり、自由度８の行列となる。一方、式（１）の関係で表される２画像間の座標を展開すると、次の式（２）に示す２つの方程式が得られる。
【数２】
0006581359.tif 000003
【０００８】
４組の対応点から８つの方程式、すなわち、８元連立方程式を立てることができ、この連立方程式を解くことによりホモグラフィ行列を１つ求めることができる。ただし、この４点の座標のうち任意の３点が直線上にない事が前提となる。
【０００９】
このような方法を用い、画像中の４つの特徴点の組合せに対して、ホモグラフィ行列を求めて評価を行い、その中で評価結果の一番良い行列を選出し、画像間の関係を表すホモグラフィ行列とするといった推定方法が、ＲＡＮＳＡＣ推定として知られている。評価の高い行列を得るには、なるべく多くの特徴点の組合せに対してホモグラフィ行列を求めて評価を行う必要があり、その回数は画像毎に数百〜数千という数になる。
【００１０】
該連立方程式を解く手法としてガウス法、ガウスジョルダン法などがよく知られているが、演算量が多い上に、数値計算上の演算誤差が大きくなることがある。もちろん、その対策としてピボットという手法も考えられているが、それを実行するとさらに処理量が増える。
【００１１】
一方、非特許文献１には、上記手法とは全く異なるアプローチで画像間のホモグラフィ行列を推定する手法が述べられている。該手法について簡単に説明する。
【００１２】
画像１から画像２へのホモグラフィ行列を推定する際に、それらの画像とは別の空間に、単位正方形を定め、該単位正方形から画像１への第１のホモグラフィ行列Ｈ１と、該単位正方形から画像２への第２のホモグラフィ行列Ｈ２とを推定する。その後に、第１のホモグラフィ行列Ｈ１の逆行列Ｈ１-1に第２のホモグラフィ行列Ｈ２を乗算し、Ｈ２・Ｈ１-1を画像１から画像２へのホモグラフィ行列として算出する、というものである。
【００１３】
この手法では、２つのホモグラフィ行列を推定し、一方のホモグラフィ行列の逆行列を計算し、該ホモグラフィ行列の逆行列ともう一方のホモグラフィ行列とを乗算するといった処理が必要となる。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Ｐａｕｌ  Ｓ．Ｈｅｃｋｂｅｒｔ．“Ｆｕｎｄａｍｅｎｔａｌｓ  ｏｆ  Ｔｅｘｔｕｒｅ  Ｍａｐｐｉｎｇ  ａｎｄ  Ｉｍａｇｅ  Ｗａｒｐｉｎｇ”，Ｍａｓｔｅｒ  Ｔｈｅｓｉｓ，Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  Ｅｎｇｉｎｅｅｒｉｎｇ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｃａｌｉｆｏｒｎｉａ，Ｂｅｒｋｅｌｅｙ，Ｊｕｎｅ，１９８９．
【発明の概要】
【発明が解決しようとする課題】
【００１５】
ビデオカメラなどの撮像装置における防振機能等の用途では、１フレーム中から何百〜何千もの特徴点を抽出し、フレーム間で対応点を探索する。そして、１フレーム時間内に該対応点の種々の組合せに対して、可能な限り多くのホモグラフィ行列を推定計算する事で、より評価の高いホモグラフィ行列を求める事ができる。このため、それぞれの行列推定は高速に行う必要がある。また、４点の特徴点が直線性を有する場合には行列推定処理を中断する事で、より多くの特徴点の組合せに対して行列推定を行えるが、そのためには既存の行列推定処理に直線判定処理を追加する必要があった。
【課題を解決するための手段】
【００１６】
この課題を解決するため、例えば本発明の情報処理装置は以下の構成を備える。すなわち、
撮像手段から得たビデオにおける連続するフレーム間のブレ量を求める情報処理装置であって、
前記撮像手段から得た、時間的に前後する第１のフレーム画像と第２のフレーム画像とを格納するためのメモリと、
前記メモリに格納された前記第１のフレーム画像と前記第２のフレーム画像に基づき、前記第１のフレーム画像に対する前記第２のフレーム画像のブレ量を検出する検出手段とを有し、
前記検出手段は、
前記第１及び第２のフレーム画像のそれぞれにおいて、４個の特徴点中の３個の特徴点を頂点とする三角形の面積を算出する面積算出手段と、
前記第１及び第２のフレーム画像のそれぞれにおいて、４個の基準特徴点を前記４個の特徴点へ変換する第１及び第２の変換行列を、当該４個の特徴点中の３個の特徴点を頂点とする複数の三角形同士の面積の比を用いて算出する第１の行列算出手段と、
前記第１及び第２の変換行列を用いて、前記第１のフレーム画像の４個の特徴点を前記第２のフレーム画像の４個の特徴点へ変換する第３の変換行列を算出する第２の行列算出手段とを有する。
【発明の効果】
【００１７】
本発明によれば、ｎ次元（ｎ＝２、又は、３）の第１の空間から第２の空間への射影変換行列を高速に得ることができる。
【図面の簡単な説明】
【００１８】
【図１】画像１内の４つの特徴点とそれに対応付ける基準座標および画像２内の４つの特徴点を表す図。
【図２】基準座標の単位正方形から画像２内の特徴点群への写像、画像２内の４つの特徴点内の３点が成す４つの三角形を表す図。
【図３】第１の実施形態の処理フローを表す図。
【図４】第２の実施形態の処理フローを表す図。
【図５】基準座標の四面体から空間２内の特徴点群への写像を表す図。
【図６】第３の実施形態の処理フローを表す図。
【図７】第４の実施形態の処理フローを表す図。
【図８】実施形態が適用するビデオカメラのブロック構成図。
【発明を実施するための形態】
【００１９】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。詳細は以下の説明から明らかにするが、本実施形態ではｎ次元（ｎ＝２又は３）の第１の空間の特徴点から第２の空間の特徴点への射影変換行列の推定を行う情報処理装置を開示するものである。具体的には、この装置は、ｎ次元の空間におけるｎ＋２個の特徴点中のｎ＋１個で形成されるｎ＋１種の面積もしくは体積を、第１、第２の空間毎に算出し、その面積もしくは体積の比から第１のｎ個のパラメータを、第１、第２の空間毎に算出する。そして、基準座標と第１、第２の空間の特徴点座標とを対応付ける第２のパラメータ群を第１、第２の空間毎に抽出する。そして、第１のｎ個のパラメータと第２のパラメータ群から、第１の空間から第２の空間への射影変換行列を生成する。
【００２０】
［第１の実施形態］
以下ではホモグラフィ行列を推定する情報処理装置として、防振機能を有するビデオカメラに適用した例を説明する。図８は実施形態におけるビデオカメラの主要部分のブロック構成図である。以下、同図を参照し、構成要素とその機能を説明する。
【００２１】
制御部８０１は装置全体の制御を司るものであり、ＣＰＵ等のプロセッサを含む。また、制御部８０１は、その処理手順（プログラム）を格納するメモリ８０１ａを有する。そして、制御部８０１には、操作者からの指示を受け付けるための操作部８０２が接続されている。撮像部８０３は、光学レンズ、撮像素子で構成され、例えば１秒当たり３０フレームの画像データを取得し、スイッチ８０４を介してフレームメモリ８０５，８０６に、フレーム単位に交互にフレーム画像を格納する。この結果、フレームメモリ８０５，８０６には時間的に前後する２個のフレーム画像が保持されることになる。ブレ検出部８０８は、フレームメモリ８０５，８０６に格納された連続する２つのフレーム（先行するフレームと後続するフレーム）の画像からホモグラフィ変換行列を推定することで、ブレ量を検出する。そして、ブレ検出部８０８は推定したホモグラフィ変換行列に基づくスキャン順を決定し、その情報をスキャン部８０９に提供する。スイッチ８０７は、フレームメモリ８０５，８０６のうち、後続する側のフレーム画像を格納している方をスキャン部８０９と接続する。スキャン部８０９は、ブレ検出部８０８からの情報に基づき、スイッチ８０７が選択中のフレームメモリから画像データを読み出し、ブレ量を相殺したフレーム画像（ブレ補正後の画像）を符号化部８１０に出力する。符号化部８１０は、スキャン部８０９から出力されたフレーム画像を符号化し、符号化データを記録部８１１に出力する。記録部８１１は、符号化データを、メモリカード（例えばＳＤカード）等の記憶媒体８１２に動画像ファイルとして記録する。ブレ検出部８０８、スキャン部８０９、符号化部８１０、記録部８１１は、それぞれ独立の回路で構成してもよいし、制御部８０１と同一のプロセッサが、メモリ８０１ａに格納されたそれぞれ別の処理手順（プログラム）を実行することで、実現してもよい。
【００２２】
次に上記実施形態におけるブレ検出部５０８におけるホモグラフィ変換行列の推定処理を説明する。本実施形態はホモグラフィ行列および３次元から３次元への射影変換行列を画像および空間間の対応特徴点から推定する処理に関するものである。なお、以下では、連続する２つのフレーム画像のうち、時間的に前のフレーム画像を画像１、後のそれを画像２と表現する。
【００２３】
図１において、画像１内の４点の特徴点座標Ｐ０，Ｐ１，Ｐ２，Ｐ３から、前記特徴点座標に対応する画像２内の４点の特徴点座標Ｑ０，Ｑ１，Ｑ２，Ｑ３へのホモグラフィ行列Ｈ２１の推定処理の詳細を以下に説明する。
【００２４】
始めに、本実施形態におけるホモグラフィ行列Ｈ21分解と、分解した各行列Ｈ1^1，Ｈ2との関係について説明する。前記ホモグラフィ行列Ｈ21が表す画像１内の特徴点群から画像２内の特徴点群への写像に関して、その中間に単位正方形の基準座標の存在を考える。この時、ホモグラフィ行列Ｈ21は下記の式（３）のように、画像１内の特徴点群から単位正方形への写像を表すホモグラフィ行列Ｈ1-1と、単位正方形から前記画像２内の特徴点群への写像を表すホモグラフィ行列Ｈ2とに分解することができる。このように分解すると、後述するようにホモグラフィ行列Ｈ21を直接求めるのに比較して、各行列の推定や逆行列の計算を簡略化することが出来るようになる。
【数３】
0006581359.tif 000004
【００２５】
そこでまず、図２に示すように基準座標の単位正方形から画像２内の特徴点群への写像を表すホモグラフィ行列Ｈ2の算出について説明する。このホモグラフィ行列Ｈ2を求めるための８元連立方程式は下記の式（４）のようになり、ここから得られるホモグラフィ行列Ｈ2パラメータの関係式は下記式（５）のようになる。
【数４】
0006581359.tif 000005
【数５】
0006581359.tif 000006
【００２６】
本実施形態におけるホモグラフィ行列推定処理の最大の特徴は、関係式（５）を用いてパラメータを算出する際に、パラメータｇおよびｈを直接求めるのではなく、幾何学的に意味のあるパラメータｇ＋１，ｈ＋１を算出することにある。
【００２７】
該パラメータｇ＋１，ｈ＋１の値は、式（５）の最後の２つの方程式より得られ、式（６）のようになる。各々の分子と分母は、特徴点（ｘ2，ｙ2）を原点とした各座標の位置ベクトルの外積演算になっている。
【００２８】
また、点１、点２、点３の３つの点から形成される三角形の面積を『△点１点２点３』と表現すると、前記パラメータは、それぞれ特徴点が形成する三角形の面積比△Ｑ０Ｑ２Ｑ３／△Ｑ１Ｑ２Ｑ３，△Ｑ１Ｑ２Ｑ０／△Ｑ１Ｑ２Ｑ３としても計算できる事がわかる。
【数６】
0006581359.tif 000007
【００２９】
上記パラメータｇ＋１，ｈ＋１を算出する事により、演算を簡素化する事が可能になり算出処理の演算量が削減できる。
【００３０】
また、上記三角形の面積は、４つの特徴点で形成される四角形の隣接する辺ベクトルの外積からも計算でき、ハードウェア処理に適した演算が可能になる。それを簡単に説明する。
【００３１】
まず、特徴点の座標データ（ｘ0，ｙ0）、（ｘ1，ｙ1）、（ｘ2，ｙ2）、（ｘ3，ｙ3）、（ｘ0，ｙ0）を順に入力する。第１ステージで隣接座標の差分を計算し、４つの辺ベクトルを連続生成する。第２ステージでは、連続する２つの辺ベクトル間で外積を計算する。
【００３２】
その結果、△Ｑ０Ｑ１Ｑ２、△Ｑ１Ｑ２Ｑ３、△Ｑ２Ｑ３Ｑ０の順に面積が算出される。正確には三角形の面積の２倍の値になるが、除算によって取り除かれるため無視できる。得られる３つの面積の１番目と３番目を２番目で割れば、ｈ＋１，ｇ＋１が得られる。
【００３３】
上記の計算で得られたパラメータｇ＋１，ｈ＋１と、特徴点の座標データを、式（５）に代入すれば、他のパラメータａ，ｂ，ｃ，ｄ，ｅ，ｆも直ぐに計算できる。それ故、基準座標の単位正方形から画像２内の特徴点群への写像を表すホモグラフィ行列Ｈ2を得ることができる。
【００３４】
画像１の特徴点を用いて同様の処理を行えば、基準座標の単位正方形から画像１内の特徴点群への写像を表すホモグラフィ行列Ｈ1を得ることができる。このホモグラフィ行列Ｈ1の逆行列を計算すれば、逆変換用のホモグラフィ行列Ｈ1-1が得られる。
【００３５】
最後に、このようにして求めた２つのホモグラフィ行列Ｈ1-1、Ｈ2から、式（３）に基づいて、Ｈ2をＨ1で逆変換することにより、最終的に求めたいホモグラフィ行列Ｈ21を算出する。
【００３６】
これまでに説明した諸性質を利用し、ブレ検出部８０８による画像１から画像２へのホモグラフィ行列の推定処理を、図３に示す処理フローを用いて説明する。
【００３７】
ステップＳ３０１にて、画像１および画像２の４組の特徴点の座標からそれぞれ辺ベクトルおよび対角線ベクトルを算出する。これは後段のｇ＋１、ｈ＋１の算出に使用される。ステップＳ３０２にて、式（６）の計算式に基づき、ｇ＋１、ｈ＋１を算出する。この値は前述の通り、特徴点が成す三角形の面積比に相当する。ステップＳ３０３にて、前記式（５）に基づき、ホモグラフィ行列Ｈ1，Ｈ2の成分をそれぞれ算出する。
【００３８】
ステップＳ３０４にて、ホモグラフィ行列Ｈ1の逆行列Ｈ1-1を算出する。ステップＳ３０５にて、前記ホモグラフィ行列Ｈ1の逆行列Ｈ1-1を用いて、ステップＳ３０３で算出したホモグラフィ行列Ｈ2を逆変換して、画像１から画像２に対するホモグラフィ行列Ｈ21を計算する。
【００３９】
以上の説明のように、本第１の実施形態によれば、４点の特徴点中の３頂点が成す三角形の面積を利用する事により、従来処理よりも演算量を削減することが可能になる。従って、１フレーム時間内により多くの対応点の組合せに対して行列推定を行う事ができる。すなわち、より評価の高いホモグラフィ行列を推定する事が可能となる。さらに、本実施形態の考え方を用いれば３次元空間の射影変換に対しても極めてシンプルな計算で実現できる。
【００４０】
［第２の実施形態］
４点の特徴点座標のうち任意の３点が直線上に配置されている場合、ホモグラフィ行列はその性質上、正しく推定する事ができなくなる。このため、選択した特徴点群の直線性を判定し、その結果直線性を有していると判断した場合にはホモグラフィ行列推定を中断する事により、その後の推定処理の時間分を有効に利用する事が出来る。本第２の実施形態では、追加処理をほとんど必要とせずに、この直線性判定を実現できる方法を示す。
【００４１】
第１の実施形態で示したように、上記式（６）から、ｇ＋１およびｈ＋１はそれぞれ特徴点が形成する三角形の面積比△Ｑ０Ｑ２Ｑ３／△Ｑ１Ｑ２Ｑ３，△Ｑ１Ｑ２Ｑ０／△Ｑ１Ｑ２Ｑ３となっている事を示した。この性質から、上記の面積比を求める過程で算出される各三角形の面積値を利用する事により、容易に特徴点群の直線性の判定が行えるようになる。すわなち、３点が直線上に配置されているか否かは、その３点で規定される三角形の面積が所定の閾値未満（十分に小さい値とする）であるか否かを判定すれば良い。そして、閾値未満であった場合、その三角形を形成する３点が直線性を有していると判断し、その後の行列推定処理を中断する。
【００４２】
この演算フローを、図４に示す処理フローを用いて説明する。なお、装置構成は第１の実施形態と同じであり、また、画像１、画像２の関係も第１の実施形態と同じであるものとする。
【００４３】
ステップＳ４０１にて、画像１および画像２の４組の特徴点の座標からそれぞれ辺ベクトルおよび対角線ベクトルを算出する。これは三角形の面積算出に使用される。ステップＳ４０２にて、特徴点群が形成する三角形の面積を算出する。
【００４４】
そして、ステップＳ４０３にて、算出した全ての三角形の面積が所定の閾値以上であるかを判定する。面積が閾値未満である三角形が存在する場合には、行列推定処理を中断する。
【００４５】
ステップＳ４０４にて、算出した三角形の面積比を算出する。これはｇ＋１，ｈ＋１を求める事に相当する。ステップＳ４０５にて、前記式（５）に基づき、ホモグラフィ行列Ｈ1，Ｈ2の成分をそれぞれ算出する。ステップＳ４０６にて、ホモグラフィ行列Ｈ1の逆行列Ｈ1-1を算出する。ステップＳ４０７にて、前記ホモグラフィ行列Ｈ1の逆行列Ｈ1-1を用いて、ステップＳ４０５で算出したホモグラフィ行列Ｈ2を逆変換して、画像１から画像２に対するホモグラフィ行列Ｈ21を計算する。
【００４６】
以上のように、特徴点の座標の幾何学的な特徴量である面積を計算し、該面積比から、ホモグラフィ行列の主要なパラメータを算出する事により、特徴点の直線性の判定を容易に行う事が可能となる。結果として、より評価の高いホモグラフィ行列の推定が可能となる。また、第２の実施形態では、三角形の面積を利用する事により、容易に直線性の判定が行えるようになり、第１の実施形態と比較して、行列推定処理を早い段階で中断することができ、結果的に、１フレーム時間内に更に多くの対応点の組合せに対して行列推定を行う事ができる。
【００４７】
［第３の実施形態］
本第３の実施形態では、３次元空間に適用し、空間１から空間２への射影変換行列Ｐを求める例を示す。
【００４８】
３次元射影変換行列Ｐは第１の実施形態と同様に、前記空間１内の特徴点群から基準座標への写像を表す射影変換行列Ｐ1-1と、基準座標から前記空間２内の特徴点群への写像を表す射影変換行列Ｐ2とに分解することができる。３次元射影変換行列を求める際の基準座標として、３次元座標中の単位立方体の５頂点となる。
【００４９】
そこでまず、図５に示すように単位立方体の５頂点から空間２内の特徴点群への写像を表す射影変換行列Ｐ２の算出について説明する。
【００５０】
基準空間において原点（０，０，０）及び４つの単位座標（１，０，０），（０，１，０），（０，０，１），（１，１，１）を定め、それらに対応付けする空間２の５つの特徴点と座標を次のように表現する。
Ｑ000（ｘ000，ｙ000，ｚ000）
Ｑ100（ｘ100，ｙ100，ｚ100）
Ｑ010（ｘ010，ｙ010，ｚ010）
Ｑ001（ｘ001，ｙ001，ｚ001）
Ｑ111（ｘ111，ｙ111，ｚ111）
このとき、射影変換行列Ｐを求めるための１５元連立方程式は下記の式（７）のようになり、ここから得られる射影変換行列の行列成分の関係式は式（８）のようになる。
【数７】
0006581359.tif 000008
【数８】
0006581359.tif 000009
【００５１】
本第３の実施形態における射影変換行列推定処理の最大の特徴は、関係式（８）を用いてパラメータを算出する際に、パラメータｐ41、ｐ42およびｐ43を直接求めるのではなく、関係式（８）の変形から得られる下記の式（９）のようにｐ41＋１，ｐ42＋１およびｐ43＋１として算出することにある。この変形により、算出式を簡素化する事が可能になり算出処理の演算量が削減できる。ここで、ｐ41＋１，ｐ42＋１，ｐ43＋１の値はそれぞれ４点の特徴点が形成する四面体の体積比となっている事がわかる。
【数９】
0006581359.tif 000010
【００５２】
以降は第１の実施形態と同様に、単位立方形から空間１への射影変換行列Ｐ1を求め、その逆行列Ｐ1-1と射影変換行列Ｐ2との行列積を算出すれば、空間１から空間２への３次元射影変換行列Ｐが得られる。
【００５３】
これまでに説明した、空間１から空間２への３次元射影変換行列を推定する演算を図６に示す処理フローを用いて説明する。
【００５４】
ステップＳ６０１にて、空間１および空間２の５組の特徴点の座標からそれぞれ辺ベクトルおよび対角線ベクトルを算出する。これは後段のｐ41＋１、ｐ42＋１、ｐ43＋１の算出に使用される。
【００５５】
ステップＳ６０２にて、式（９）の計算式に基づき、ｐ41＋１、ｐ42＋１、ｐ43＋１を算出する。この値は前述の通り、特徴点が成す四面体の体積比に相当する。ステップＳ６０３にて、式（８）に基づき、射影変換行列Ｐ1，Ｐ2の成分をそれぞれ算出する。
【００５６】
ステップＳ６０４にて、射影変換行列Ｐ1の逆行列Ｐ1-1を算出する。ステップＳ６０５にて、前記射影変換行列Ｐ1の逆行列Ｐ1-1を用いて、ステップ６０３で算出した射影変換行列Ｐ2を逆変換して、空間１から空間２に対する射影変換行列Ｐを計算する。
【００５７】
従来は幾何学的な意味の無い演算を数多く行って、３次元の射影変換行列を計算する必要があったが、本実施形態によれば、特徴点の座標情報から体積特徴量を計算して射影成分パラメータを算出し、それと特徴点座標を用いて射影変換行列を計算できる。
【００５８】
本第３の実施形態は３次元空間から３次元空間への射影変換行列を算出するものであるが、空間の次元に応じて基準空間の単位座標と特徴空間の特徴点を追加すれば、４次元以上の空間の射影変換行列の算出にも容易に応用できる。
【００５９】
［第４の実施形態］
５点の特徴点座標のうち任意の４点が同一平面上に存在する場合、３次元射影変換行列はその性質上、正しく推定する事ができなくなる。このため、選択した特徴点群の平面性を判定し、その結果平面性を有している場合には射影変換行列推定を中断する事により、その後の推定処理の時間分を有効に利用する事が出来る。本第４の実施形態では、この平面性判定のために追加処理をほとんど必要とせずに実現できる事を示す。
【００６０】
第３の実施形態で示したように、式（９）から、ｐ41＋１，ｐ42＋１およびｐ43＋１はそれぞれ特徴点が形成する四面体の体積比となっている事を示した。この性質から、上記の体積比を求める過程で算出される各四面体の体積値を利用する事により、容易に特徴点群の平面性の判定が行えるようになる。すわなち、四面体の体積が所定の閾値未満である場合、その四面体を形成する４点が平面性を有していると判定し、その後の行列推定処理を中断することができる。
【００６１】
この演算フローを、図７に示す処理フローを用いて説明する。
【００６２】
ステップＳ７０１にて、空間１および空間２の５組の特徴点の座標からそれぞれ辺ベクトルおよび対角線ベクトルを算出する。これは四面体の体積算出に使用される。
【００６３】
ステップＳ７０２にて、特徴点群が形成する四面体の体積を算出する。ステップＳ７０３にて、算出した全ての四面体の体積が所定の閾値以上であるかを判定する。体積が閾値未満である四面体が存在する場合には、行列推定処理を中断する。
【００６４】
ステップＳ７０４にて、算出した四面体の体積比を算出する。これはｐ41＋１，ｐ42＋１およびｐ43＋１を求める事に相当する。ステップＳ７０５にて、式（８）に基づき、射影変換行列Ｐ1，Ｐ2の成分をそれぞれ算出する。ステップＳ７０６にて、射影変換行列Ｐ1の逆行列Ｐ1-1を算出する。ステップＳ７０７にて、前記射影変換行列Ｐ1の逆行列Ｐ1-1を用いて、ステップＳ７０５で算出した射影変換行列Ｐ2を逆変換して、空間１から空間２に対する３次元射影変換行列Ｐを計算する。
【００６５】
以上のように、該パラメータ行列の主要なパラメータが、特徴点の座標から得られる幾何学的な特徴量である体積と密接な関係があることを見出した事により、平面性の判定を容易に実現する事が可能となる。結果として、より評価の高い３次元射影変換行列の推定が可能となる。
【００６６】
最後に、各実施形態で説明を省略した正規化処理について記す。各実施形態で算出したホモグラフィ行列や３次元射影変換行列の右下の要素の値は一般的には“１”では無い。該要素の値を“１”にするため、行列全体を該右下の要素の値で割る、もしくは、逆数を乗算する。これが正規化処理であり、必要に応じて行えばよい。
【００６７】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【００６８】
８０１…制御部、８０２…操作部、８０３…撮像部、８０４、８０７…スイッチ、８０５、８０６…フレームバッファ、８０８…ブレ検出部、８０９…スキャン部、８１０…符号化部、８１１…記録部、８１２…記憶媒体
【図１】
0006581359.tif 000011
【図２】
0006581359.tif 000012
【図３】
0006581359.tif 000013
【図４】
0006581359.tif 000014
【図５】
0006581359.tif 000015
【図６】
0006581359.tif 000016
【図７】
0006581359.tif 000017
【図８】
0006581359.tif 000018