(57)【特許請求の範囲】
【請求項１】
第１画像、第１画像と重なり合う部分を有する第２画像、ならびに第１画像および第２画像の両方に重なり合う部分を有する第３画像を用いて、第２画像と第３画像とが重なり合う部分を、第１画像に合成する画像合成方法であって、
第１画像、第２画像および第３画像の重なり合う部分内において、複数の特徴点に対する３画像間の対応点の座標値を求めるとともに、第２画像と第３画像とが重なり合う部分内において、複数の特徴点に対する２画像間の対応点の座標値を求める第１ステップ、
第１ステップで求められた複数組の３画像間の対応点の座標値に基づいて、３画像間の関係を示すtrifocalテンソルを算出する第２ステップ、
第１ステップで求められた複数組の２画像間の対応点の座標値と、第２ステップで求められたtrifocalテンソルとに基づいて、上記２画像間の各対応点に対応する第１画像での座標値を求める第３ステップ、ならびに
上記２画像間の各対応点に対応する第１画像での座標値に基づいて、第２画像と第３画像とが重なり合う部分を、第１画像に合成する第４ステップ、
を備えていることを特徴とする画像合成方法。
【請求項２】
第１ステップは、
第１画像と第２画像との重なり部を抽出するステップ、
第２画像と第３画像との重なり部を抽出するステップ、
第２画像における第１画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第１特徴点として抽出するステップ、
第２画像における第３画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第２特徴点として抽出するステップ、
第２画像上の各第１特徴点に対応する第１画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第１特徴点に対応する第１画像上の点の座標値を求めるステップ、
第２画像上の各第２特徴点に対応する第３画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第２特徴点に対応する第３画像上の点の座標値を求めるステップ、ならびに
第２画像上の各第１特徴点に対応する第１画像上の点の座標値と、第２画像上の各第２特徴点に対応する第３画像上の点の座標値とに基づいて、上記複数組の３画像間の対応点の座標値を求めるとともに、上記複数組の２画像間の対応点の座標値を求めるステップ、
を備えていることを特徴とする請求項１に記載の画像合成方法。
【請求項３】
第４ステップは、
第２画像内の第３画像と重なり合う部分および第３画像内の第２画像と重なり合う部分のうちから任意に選択された一方の部分の画像を第４画像とすると、第４画像を隣接する３つの特徴点を頂点とする３角パッチ毎に分割し、各３角パッチ毎に第４画像上の点に対応する第１画像上の位置を求めるための変換式を求めるステップ、
第４画像における各３角パッチ内の各画素に対応する第１画像上の座標値を、当該３角パッチに対して算出された変換式を用いて求めるステップ、ならびに
第４画像の各画素に対応する第１画像上の座標値を用いて、第４画像を第１画像に合成するステップ、
を備えていることを特徴とする請求項１および２のいずれかに記載の画像合成方法。
【請求項４】
３角パッチ毎に求められる変換式は平面射影変換行列であり、平面射影変換行列は、３角パッチにおける３つの頂点の対応点と、第１画像と第４画像との間のエピポーラ拘束条件を示す基礎行列とに基づいて求められることを特徴とする請求項３に記載の画像合成方法。
【請求項５】
３角パッチ毎に求められる変換式は平面射影変換行列であり、平面射影変換行列は、３角パッチにおける３つの頂点の対応点と、第１画像と第４画像との間のエピポーラ拘束条件を示すエピポールの対応とに基づいて求められることを特徴とする請求項３に記載の画像合成方法。
【請求項６】
３角パッチ毎に求められる変換式はアフィン変換行列であり、アフィン変換行列は、３角パッチにおける３つの頂点の対応点に基づいて求められることを特徴とする請求項３に記載の画像合成方法。
【請求項７】
第１画像、第１画像と重なり合う部分を有する第２画像、ならびに第１画像および第２画像の両方に重なり合う部分を有する第３画像を用いて、第２画像と第３画像とが重なり合う部分を、第１画像に合成する画像合成装置であって、
第１画像、第２画像および第３画像の重なり合う部分内において、複数の特徴点に対する３画像間の対応点の座標値を求めるとともに、第２画像と第３画像とが重なり合う部分内において、複数の特徴点に対する２画像間の対応点の座標値を求める第１手段、
第１手段で求められた複数組の３画像間の対応点の座標値に基づいて、３画像間の関係を示すtrifocalテンソルを算出する第２手段、
第１手段で求められた複数組の２画像間の対応点の座標値と、第２手段で求められたtrifocalテンソルとに基づいて、上記２画像間の各対応点に対応する第１画像での座標値を求める第３手段、ならびに
上記２画像間の各対応点に対応する第１画像での座標値に基づいて、第２画像と第３画像とが重なり合う部分を、第１画像に合成する第４手段、
を備えていることを特徴とする画像合成装置。
【請求項８】
第１手段は、
第１画像と第２画像との重なり部を抽出する手段、
第２画像と第３画像との重なり部を抽出する手段、
第２画像における第１画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第１特徴点として抽出する手段、
第２画像における第３画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第２特徴点として抽出する手段、
第２画像上の各第１特徴点に対応する第１画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第１特徴点に対応する第１画像上の点の座標値を求める手段、
第２画像上の各第２特徴点に対応する第３画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第２特徴点に対応する第３画像上の点の座標値を求める手段、ならびに
第２画像上の各第１特徴点に対応する第１画像上の点の座標値と、第２画像上の各第２特徴点に対応する第３画像上の点の座標値とに基づいて、上記複数組の３画像間の対応点の座標値を求めるとともに、上記複数組の２画像間の対応点の座標値を求める手段、
を備えていることを特徴とする請求項７に記載の画像合成装置。
【請求項９】
第４手段は、
第２画像内の第３画像と重なり合う部分および第３画像内の第２画像と重なり合う部分のうちから任意に選択された一方の部分の画像を第４画像とすると、第４画像を隣接する３つの特徴点を頂点とする３角パッチ毎に分割し、各３角パッチ毎に第４画像上の点に対応する第１画像上の位置を求めるための変換式を求める手段、
第４画像における各３角パッチ内の各画素に対応する第１画像上の座標値を、当該３角パッチに対して算出された変換式を用いて求める手段、ならびに
第４画像の各画素に対応する第１画像上の座標値を用いて、第４画像を第１画像に合成する手段、
を備えていることを特徴とする請求項７および８のいずれかに記載の画像合成装置。
【請求項１０】
３角パッチ毎に求められる変換式は平面射影変換行列であり、平面射影変換行列は、３角パッチにおける３つの頂点の対応点と、第１画像と第２画像との間のエピポーラ拘束条件を示す基礎行列とに基づいて求められることを特徴とする請求項９に記載の画像合成装置。
【請求項１１】
３角パッチ毎に求められる変換式は平面射影変換行列であり、平面射影変換行列は、３角パッチにおける３つの頂点の対応点と、第１画像と第２画像との間のエピポーラ拘束条件を示すエピポールの対応とに基づいて求められることを特徴とする請求項９に記載の画像合成装置。
【請求項１２】
３角パッチ毎に求められる変換式はアフィン変換行列であり、アフィン変換行列は、３角パッチにおける３つの頂点の対応点に基づいて求められることを特徴とする請求項９に記載の画像合成装置。
【請求項１３】
第１画像、第１画像と重なり合う部分を有する第２画像、ならびに第１画像および第２画像の両方に重なり合う部分を有する第３画像を用いて、第１画像の外側にありかつ第２画像と第３画像とが重なり合う部分を、第１画像に合成する画像合成プログラムを記録したコンピュータ読み取り可能な記録媒体であって、
第１画像、第２画像および第３画像の重なり合う部分内において、複数の特徴点に対する３画像間の対応点の座標値を求めるとともに、第２画像と第３画像とが重なり合う部分内において、複数の特徴点に対する２画像間の対応点の座標値を求める第１ステップ、
第１ステップで求められた複数組の３画像間の対応点の座標値に基づいて、３画像間の関係を示すtrifocalテンソルを算出する第２ステップ、
第１ステップで求められた複数組の２画像間の対応点の座標値と、第２ステップで求められたtrifocalテンソルとに基づいて、上記２画像間の各対応点に対応する第１画像での座標値を求める第３ステップ、ならびに
上記２画像間の各対応点に対応する第１画像での座標値に基づいて、第１画像の外側にありかつ第２画像と第３画像とが重なり合う部分を、第１画像に合成する第４ステップ、
を備えた画像合成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１４】
第１ステップは、
第１画像と第２画像との重なり部を抽出するステップ、
第２画像と第３画像との重なり部を抽出するステップ、
第２画像における第１画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第１特徴点として抽出するステップ、
第２画像における第３画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第２特徴点として抽出するステップ、
第２画像上の各第１特徴点に対応する第１画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第１特徴点に対応する第１画像上の点の座標値を求めるステップ、
第２画像上の各第２特徴点に対応する第３画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第２特徴点に対応する第３画像上の点の座標値を求めるステップ、ならびに
第２画像上の各第１特徴点に対応する第１画像上の点の座標値と、第２画像上の各第２特徴点に対応する第３画像上の点の座標値とに基づいて、上記複数組の３画像間の対応点の座標値を求めるとともに、上記複数組の２画像間の対応点の座標値を求めるステップ、                                                を備えていることを特徴とする請求項１３に記載の画像合成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１５】
第４ステップは、
第２画像内の第３画像と重なり合う部分および第３画像内の第２画像と重なり合う部分のうちから任意に選択された一方の部分の画像を第４画像とすると、第４画像を隣接する３つの特徴点を頂点とする３角パッチ毎に分割し、各３角パッチ毎に第４画像上の点に対応する第１画像上の位置を求めるための変換式を求めるステップ、
第４画像における各３角パッチ内の各画素に対応する第１画像上の座標値を、当該３角パッチに対して算出された変換式を用いて求めるステップ、ならびに
第４画像の各画素に対応する第１画像上の座標値を用いて、第４画像を第１画像に合成するステップ、
を備えていることを特徴とする請求項１３および１４のいずれかに記載の画像合成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１６】
３角パッチ毎に求められる変換式は平面射影変換行列であり、平面射影変換行列は、３角パッチにおける３つの頂点の対応点と、第１画像と第４画像との間のエピポーラ拘束条件を示す基礎行列とに基づいて求められることを特徴とする請求項１５に記載の画像合成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１７】
３角パッチ毎に求められる変換式は平面射影変換行列であり、平面射影変換行列は、３角パッチにおける３つの頂点の対応点と、第１画像と第４画像との間のエピポーラ拘束条件を示すエピポールの対応とに基づいて求められることを特徴とする請求項１５に記載の画像合成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１８】
３角パッチ毎に求められる変換式はアフィン変換行列であり、アフィン変換行列は、３角パッチにおける３つの頂点の対応点に基づいて求められることを特徴とする請求項１５に記載の画像合成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、画像合成方法、画像合成装置、画像合成プログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
２枚の画像からオプティカルフローを計算し、得られたオプティカルフローに基づいて、２枚の画像間での位置合わせを行う技術が知られている。従来のオプテカルフローの算出方法について説明する。
【０００３】
（１）Lucas-Kanade法
従来から、動画像における運動物体の見かけの速度場（オプティカルフロー）を計算する手法が数多く提案されている。中でも局所勾配法であるLucas-Kanade法は、最も良い手法の一つである。その理由は、処理が高速、実装が容易、結果が信頼度を持つことである。
【０００４】
Lucas-Kanade法の詳細については、文献： B.Lucas and T.Kanade,"An Iterative Image Registration Technique with an Application to Stereo Vision,"In Seventh International Joint Conference on Artificial Intelligence(IJCAI-81), pp. 674-979, 1981を参照のこと。
【０００５】
以下に、Lucas-Kanade法の概要を述べる。
ある時刻ｔの画像座標ｐ＝（ｘ，ｙ）の濃淡パターンＩ（ｘ，ｙ，ｔ）が、ある微小時間後（δｔ）に座標（ｘ＋δｘ，ｙ＋δｙ）に、その濃淡分布を一定に保ったまま移動した時、次のオプティカルフロー拘束式１が成り立つ。
【０００６】
【数１】
0003540696.tif 000002
【０００７】
２次元画像でオプティカルフロー｛ｖ＝（δｘ／δｔ，δｙ／δｔ）＝（ｕ，ｖ）｝を計算するには、未知パラメータ数が２個であるので、もう一個拘束式が必要である。Lucas とKanade( 金出) は、同一物体の局所領域では、同一のオプティカルフローを持つと仮定した。
【０００８】
例えば、画像上の局所領域ω内で、オプティカルフローが一定であるとすると、最小化したい濃淡パターンの二乗誤差Ｅは、
Ｉ0 （ｐ）＝Ｉ（ｘ，ｙ，ｔ），
Ｉ1 （ｐ＋ｖ）＝Ｉ（ｘ＋ｕ，ｙ＋ｖ，ｔ＋δｔ）
と書き改めると、次式２で定義できる。
【０００９】
【数２】
0003540696.tif 000003
【００１０】
ここで、ｖが微少な場合には、テーラー展開の２次以上の項を無視できるので、次式３の関係が成り立つ。
【００１１】
【数３】
0003540696.tif 000004
【００１２】
ここで、ｇ（ｐ）は、Ｉ1 （ｐ）の一次微分である。
【００１３】
誤差Ｅが最小になるのは、Ｅのｖに対する微分値が０の時であるので、次式４の関係が成り立つ。
【００１４】
【数４】
0003540696.tif 000005
【００１５】
故にオプティカルフローｖは次式５で求められる。
【００１６】
【数５】
0003540696.tif 000006
【００１７】
更に、次式６に示すように、ニュートン・ラフソン的な反復演算によって精度良く求めることができる。
【００１８】
【数６】
0003540696.tif 000007
【００１９】
（２）階層的推定法
Lucas-Kanade法を含む勾配法の最も大きな問題点は、良好な初期値が必要なために、大きな動きに対しては適用できないことである。そこで、従来からピラミッド階層構造型に数段回の解像度の異なる画像を作成して解決する方法が提案されている。
【００２０】
これは、まず、２枚の連続した画像から、予めそれぞれの画像の数段階の解像度の異なる画像を作成する。次に、最も解像度の低い画像間において、おおまかなオプティカルフローを計算する。そして、この結果を参考にして、一段解像度の高い画像間においてより精密なオプティカルフローを計算する。この処理を最も解像度の高い画像間まで順次繰り返す。
【００２１】
図４は原画像を、図３は図４の原画像より解像度の低い画像を、図２は図３の低解像度画像より解像度の低い画像を、図１は図２の低解像度画像より解像度の低い画像を、それぞれ示している。図１〜図４において、Ｓは、１つのパッチを示している。
【００２２】
図１の画像（階層１の画像）、図２の画像（階層２の画像）、図３の画像（階層３の画像）および図４の画像（階層４の画像）の順番で段階的にオプティカルフローが求められる。図１〜図４において矢印は、パッチ毎に求められたオプティカルフローベクトルを示している。
【００２３】
しかしながら、ここでの問題点は、実画像では、十分な模様（テクスチャ）を含む領域が少なく、信頼性のあるオプティカルフローが得られないことにある。
【００２４】
ところで、複数の画像を貼り合わせて、視野が広く解像度の高い画像を継目なく合成する技術（イメージモザイキング）が従来から活発に研究されている。古典的な応用には、航空写真、衛星写真の合成がある。最近では、複数枚のデジタル画像から継目のないパノラマ画像を合成し、臨場感の高い仮想現実環境を構築する手法が注目されている。
【００２５】
パノラマ画像を合成する技術としては、次の２つの方法が知られている。
第１の方法は、まず、カメラを並進移動させて複数枚の画像を予め撮像しておく。得られた複数枚の画像をパーソナルコンピュータによって同時にモニタに表示させる。２つの画像間において対応点をユーザが指定することにより、２つの画像が合成される。
【００２６】
第１の方法では、カメラの運動が並進運動に限定される。また、第１の方法では、ユーザが対応点を指定する必要がある。
【００２７】
第２の方法は、カメラを三脚に固定し、カメラの動きを水平面での回転だけに制限して、複数枚の画像を撮像する。得られた複数枚の画像を円筒面に投影して、合成する（USP 5,396,583 参照) 。
【００２８】
第２の方法では、カメラの動きを水平面での回転だけに制限する必要がある。また、カメラの焦点距離または画角を測定する必要がある。
【００２９】
【発明が解決しようとする課題】
この発明の目的は、奥行きの深いシーンを合成する際においても、精度の高い位置合わせが行える画像合成方法、画像合成装置、画像合成プログラムを記録した記録媒体を提供することにある。
【００３０】
この発明の他の目的は、複数の画像から継目のないパノラマ画像を得ることができ、しかも複数の画像を撮像するためのカメラに自由な運動を許容し、焦点距離の測定が不要な画像合成方法、画像合成装置、画像合成プログラムを記録した記録媒体を提供することにある。
【００３１】
【課題を解決するための手段】
この発明による画像合成方法は、第１画像、第１画像と重なり合う部分を有する第２画像、ならびに第１画像および第２画像の両方に重なり合う部分を有する第３画像を用いて、第２画像と第３画像とが重なり合う部分を、第１画像に合成する画像合成方法であって、第１画像、第２画像および第３画像の重なり合う部分内において、複数の特徴点に対する３画像間の対応点の座標値を求めるとともに、第２画像と第３画像とが重なり合う部分内において、複数の特徴点に対する２画像間の対応点の座標値を求める第１ステップ、第１ステップで求められた複数組の３画像間の対応点の座標値に基づいて、３画像間の関係を示すtrifocalテンソルを算出する第２ステップ、第１ステップで求められた複数組の２画像間の対応点の座標値と、第２ステップで求められたtrifocalテンソルとに基づいて、上記２画像間の各対応点に対応する第１画像での座標値を求める第３ステップ、ならびに上記２画像間の各対応点に対応する第１画像での座標値に基づいて、第２画像と第３画像とが重なり合う部分を、第１画像に合成する第４ステップを備えていることを特徴とする。
【００３２】
第１ステップは、たとえば、第１画像と第２画像との重なり部を抽出するステップ、第２画像と第３画像との重なり部を抽出するステップ、第２画像における第１画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第１特徴点として抽出するステップ、第２画像における第３画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第２特徴点として抽出するステップ、第２画像上の各第１特徴点に対応する第１画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第１特徴点に対応する第１画像上の点の座標値を求めるステップ、第２画像上の各第２特徴点に対応する第３画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第２特徴点に対応する第３画像上の点の座標値を求めるステップ、ならびに第２画像上の各第１特徴点に対応する第１画像上の点の座標値と、第２画像上の各第２特徴点に対応する第３画像上の点の座標値とに基づいて、上記複数組の３画像間の対応点の座標値を求めるとともに、上記複数組の２画像間の対応点の座標値を求めるステップを備えている。
【００３３】
第４ステップは、たとえば、第２画像内の第３画像と重なり合う部分および第３画像内の第２画像と重なり合う部分のうちから任意に選択された一方の部分の画像を第４画像とすると、第４画像を隣接する３つの特徴点を頂点とする３角パッチ毎に分割し、各３角パッチ毎に第４画像上の点に対応する第１画像上の位置を求めるための変換式を求めるステップ、第４画像における各３角パッチ内の各画素に対応する第１画像上の座標値を、当該３角パッチに対して算出された変換式を用いて求めるステップ、ならびに第４画像の各画素に対応する第１画像上の座標値を用いて、第４画像を第１画像に合成するステップを備えている。
【００３４】
３角パッチ毎に求められる変換式としては、たとえば、平面射影変換行列が用いられる。平面射影変換行列は、たとえば、３角パッチにおける３つの頂点の対応点と、第１画像と第４画像との間のエピポーラ拘束条件を示す基礎行列とに基づいて求められる。平面射影変換行列を、３角パッチにおける３つの頂点の対応点と、第１画像と第４画像との間のエピポーラ拘束条件を示すエピポールの対応とに基づいて求めてもよい。
【００３５】
３角パッチ毎に求められる変換式として、アフィン変換行列を用いてもよい。アフィン変換行列は、３角パッチにおける３つの頂点の対応点に基づいて求められる。
【００３６】
この発明による画像合成装置は、第１画像、第１画像と重なり合う部分を有する第２画像、ならびに第１画像および第２画像の両方に重なり合う部分を有する第３画像を用いて、第２画像と第３画像とが重なり合う部分を、第１画像に合成する画像合成装置であって、第１画像、第２画像および第３画像の重なり合う部分内において、複数の特徴点に対する３画像間の対応点の座標値を求めるとともに、第２画像と第３画像とが重なり合う部分内において、複数の特徴点に対する２画像間の対応点の座標値を求める第１手段、第１手段で求められた複数組の３画像間の対応点の座標値に基づいて、３画像間の関係を示すtrifocalテンソルを算出する第２手段、第１手段で求められた複数組の２画像間の対応点の座標値と、第２手段で求められたtrifocalテンソルとに基づいて、上記２画像間の各対応点に対応する第１画像での座標値を求める第３手段、ならびに上記２画像間の各対応点に対応する第１画像での座標値に基づいて、第２画像と第３画像とが重なり合う部分を、第１画像に合成する第４手段を備えていることを特徴とする。
【００３７】
第１手段としては、たとえば、第１画像と第２画像との重なり部を抽出する手段、第２画像と第３画像との重なり部を抽出する手段、第２画像における第１画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第１特徴点として抽出する手段、第２画像における第３画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第２特徴点として抽出する手段、第２画像上の各第１特徴点に対応する第１画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第１特徴点に対応する第１画像上の点の座標値を求める手段、第２画像上の各第２特徴点に対応する第３画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第２特徴点に対応する第３画像上の点の座標値を求める手段、ならびに第２画像上の各第１特徴点に対応する第１画像上の点の座標値と、第２画像上の各第２特徴点に対応する第３画像上の点の座標値とに基づいて、上記複数組の３画像間の対応点の座標値を求めるとともに、上記複数組の２画像間の対応点の座標値を求める手段を備えているものが用いられる。
【００３８】
第４手段としては、たとえば、第２画像内の第３画像と重なり合う部分および第３画像内の第２画像と重なり合う部分のうちから任意に選択された一方の部分の画像を第４画像とすると、第４画像を隣接する３つの特徴点を頂点とする３角パッチ毎に分割し、各３角パッチ毎に第４画像上の点に対応する第１画像上の位置を求めるための変換式を求める手段、第４画像における各３角パッチ内の各画素に対応する第１画像上の座標値を、当該３角パッチに対して算出された変換式を用いて求める手段、ならびに第４画像の各画素に対応する第１画像上の座標値を用いて、第４画像を第１画像に合成する手段を備えているものが用いられる。
【００３９】
３角パッチ毎に求められる変換式としては、たとえば、平面射影変換行列が用いられる。平面射影変換行列は、たとえば、３角パッチにおける３つの頂点の対応点と、第１画像と第４画像との間のエピポーラ拘束条件を示す基礎行列とに基づいて求められる。平面射影変換行列を、３角パッチにおける３つの頂点の対応点と、第１画像と第４画像との間のエピポーラ拘束条件を示すエピポールの対応とに基づいて求めてもよい。
【００４０】
３角パッチ毎に求められる変換式として、アフィン変換行列を用いてもよい。アフィン変換行列は、３角パッチにおける３つの頂点の対応点に基づいて求められる。
【００４１】
この発明による画像合成プログラムを記録したコンピュータ読み取り可能な記録媒体は、第１画像、第１画像と重なり合う部分を有する第２画像、ならびに第１画像および第２画像の両方に重なり合う部分を有する第３画像を用いて、第２画像と第３画像とが重なり合う部分を、第１画像に合成する画像合成プログラムを記録したコンピュータ読み取り可能な記録媒体であって、第１画像、第２画像および第３画像の重なり合う部分内において、複数の特徴点に対する３画像間の対応点の座標値を求めるとともに、第２画像と第３画像とが重なり合う部分内において、複数の特徴点に対する２画像間の対応点の座標値を求める第１ステップ、第１ステップで求められた複数組の３画像間の対応点の座標値に基づいて、３画像間の関係を示すtrifocalテンソルを算出する第２ステップ、第１ステップで求められた複数組の２画像間の対応点の座標値と、第２ステップで求められたtrifocalテンソルとに基づいて、上記２画像間の各対応点に対応する第１画像での座標値を求める第３ステップ、ならびに上記２画像間の各対応点に対応する第１画像での座標値に基づいて、第２画像と第３画像とが重なり合う部分を、第１画像に合成する第４ステップを備えた画像合成プログラムを記録していることを特徴とする。
【００４２】
第１ステップは、たとえば、第１画像と第２画像との重なり部を抽出するステップ、第２画像と第３画像との重なり部を抽出するステップ、第２画像における第１画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第１特徴点として抽出するステップ、第２画像における第３画像との重なり部分から、両画像間のオプティカルフローによる追跡に有効な複数の部分画像を第２特徴点として抽出するステップ、第２画像上の各第１特徴点に対応する第１画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第１特徴点に対応する第１画像上の点の座標値を求めるステップ、第２画像上の各第２特徴点に対応する第３画像上の点を、両画像間のオプティカルフローに基づいて追跡することにより、第２画像上の各第２特徴点に対応する第３画像上の点の座標値を求めるステップ、ならびに第２画像上の各第１特徴点に対応する第１画像上の点の座標値と、第２画像上の各第２特徴点に対応する第３画像上の点の座標値とに基づいて、上記複数組の３画像間の対応点の座標値を求めるとともに、上記複数組の２画像間の対応点の座標値を求めるステップを備えている。
【００４３】
第４ステップは、たとえば、第２画像内の第３画像と重なり合う部分および第３画像内の第２画像と重なり合う部分のうちから任意に選択された一方の部分の画像を第４画像とすると、第４画像を隣接する３つの特徴点を頂点とする３角パッチ毎に分割し、各３角パッチ毎に第４画像上の点に対応する第１画像上の位置を求めるための変換式を求めるステップ、第４画像における各３角パッチ内の各画素に対応する第１画像上の座標値を、当該３角パッチに対して算出された変換式を用いて求めるステップ、ならびに第４画像の各画素に対応する第１画像上の座標値を用いて、第４画像を第１画像に合成するステップを備えている。
【００４４】
３角パッチ毎に求められる変換式としては、たとえば、平面射影変換行列が用いられる。平面射影変換行列は、たとえば、３角パッチにおける３つの頂点の対応点と、第１画像と第４画像との間のエピポーラ拘束条件を示す基礎行列とに基づいて求められる。平面射影変換行列を、３角パッチにおける３つの頂点の対応点と、第１画像と第４画像との間のエピポーラ拘束条件を示すエピポールの対応とに基づいて求めてもよい。
【００４５】
３角パッチ毎に求められる変換式として、アフィン変換行列を用いてもよい。アフィン変換行列は、３角パッチにおける３つの頂点の対応点に基づいて求められる。
【００４６】
【発明の実施の形態】
以下、この発明をパノラマ画像合成装置に適用した場合の実施の形態について説明する。
【００４７】
パノラマ画像合成装置を説明する前に、パノラマ画像合成装置において採用されるオプティカルフロー推定方法について説明しておく。
【００４８】
〔１〕オプティカルフロー推定方法についての説明。
この実施例で採用されるオプティカルフロー推定方法は、ピラミッド階層型に数段回の解像度の異なる画像を作成して、オプティカルフローを段階的に計算する階層的推定を前提としている。オプティカルフローの計算方法は、Lucas-Kanade法等の勾配法に従う。つまり、階層構造化した勾配法によるオプティカルフロー推定法を前提としている。ここでは、勾配法としてLucas-Kanade法が用いられている。
【００４９】
この実施例で採用されるオプティカルフロー推定方法の特徴は、階層構造化したLucas-Kanade法によるオプティカルフロー推定法の各段階において得られたオプティカルフローを、膨張処理によって補完することにある。以下、これについて詳しく説明する。
【００５０】
Lucas-Kanade法の長所の一つは、追跡結果が信頼性を持つことである。Tomasiと Kanade とは、ある領域の追跡可能性が、以下のように微分画像から算出できることを示した(C.Tomasi and T.Kanade,"Shape and Motion from Image Streams: a Factorization method-Part 3 Detection and Tracking of Point Features ,"CMU-CS-91-132, Carnegie Mellon University, 1991.) 。
【００５１】
ある領域画像ωの垂直・水平方向の微分の２乗を要素に持つ次式７の２×２の係数行列Ｇから、その固有値を計算することで、その領域の追跡可能性を決定することができる。
【００５２】
【数７】
0003540696.tif 000008
【００５３】
この行列Ｇの固有値が両方とも大きい場合には、その領域は直交方向に変化を持ち、一意の位置決めが可能である。従って、小さい方の固有値λmin と、追跡後の領域間の濃淡残差Ｅから、追跡結果の信頼度γを次式８によって得ることができる。
【００５４】
【数８】
0003540696.tif 000009
【００５５】
本発明者らは、オプティカルフローの同一階層内で信頼度の高い結果を用いて、信頼度の低い領域を補間する方法を開発した。これは、一段階粗い階層での結果を、追跡の初期値だけに用いて、着目している現段階の階層の結果には何も利用しない。代わりに、テクスチャの少ない領域のオプティカルフローはその周囲のオプティカルフローに近い値を持つと仮定し、モルフォロジー処理によりフロー場を補完するものである。
【００５６】
図５にフローベクトルの膨張処理の様子を示す。
【００５７】
左図は、フローベクトルの信頼度のマップを濃淡で表したものである。ここで、黒ければ黒い程信頼度が高いとする。
【００５８】
まず、得られたフローをしきい値処理する。白い部分は、結果の信頼度が低いために、しきい値処理されたものである。
【００５９】
次に、２値画像でのモルフォロジー演算による穴埋め処理を模して、フロー場において結果の膨張処理を次のように行う。ある領域ｉ，ｊのフローベクトルｕ（ｉ，ｊ）は、その４近傍のフローベクトルから信頼度γに応じて重み付けを行って次式９のように計算できる。
【００６０】
【数９】
0003540696.tif 000010
【００６１】
この処理を、しきい値処理されたすべての信頼度の低い領域が埋まるまで、繰り返す。この補完処理を、各階層において行う。なお、ある領域ｉ，ｊのフローベクトルｕ（ｉ，ｊ）を、その８近傍のフローベクトルから信頼度γに応じて重み付けを行って算出するようにしてもよい。
【００６２】
図６（ａ）は、ある階層の画像に対してしきい値処理されたオプティカルフローを示し、図６（ｂ）は補完後のオプティカルフローを示している。図６（ａ）において、矢印はしきい値処理によって信頼度が高いと判定されたオプティカルフローベクトルであり、×印は信頼度が低いとされた部分を示している。
【００６３】
〔２〕パノラマ画像合成装置の説明
【００６４】
以下、図７に示すように、互いに重なり合う部分を有する３枚の画像Ａ１、Ａ２、Ａ３を用いて、第２画像Ａ２と第３画像Ａ３とが重なり合っている部分を、第１画像Ａ１に合成するためのパノラマ画像合成装置について説明する。
【００６５】
第２画像Ａ２と第３画像Ａ３とが重なり合っている部分を、第１画像Ａ１に合成する際には、第２画像Ａ２における第３画像Ａ３と重なっている部分を第１画像に合成してもよいし、第３画像Ａ３における第２画像Ａ２と重なっている部分を第１画像に合成してもよいが、ここでは、第２画像Ａ２における第３画像Ａ３と重なっている部分を第１画像に合成する場合について説明する。
【００６６】
図８は、パノラマ画像合成装置の構成を示している。
【００６７】
パーソナルコンピュータ１０には、ディスプレイ２１、マウス２２およびキーボード２３が接続されている。パーソナルコンピュータ１０は、ＣＰＵ１１、メモリ１２、ハードディスク１３、ＣＤ−ＲＯＭのようなリムーバブルディスクのドライブ（ディスクドライブ）１４を備えている。
【００６８】
ハードディスク１３には、ＯＳ（オペレーティングシステム）等の他、パノラマ画像合成プログラムが格納されている。パノラマ画像合成プログラムは、それが格納されたＣＤ−ＲＯＭ２０を用いて、ハードディスク１３にインストールされる。また、ハードディスク１３には、デジタルカメラによって撮像された複数の画像が予め格納されているものとする。
【００６９】
図９は、パノラマ画像合成ソフトが起動せしめられた場合にＣＰＵ１１によって行われるパノラマ画像合成処理手順を示している。
【００７０】
(I) まず、ユーザによって指定された３枚の画像（第１画像Ａ１、第２画像Ａ２及び第３画像Ａ３）がメモリ１２に読み込まれる（ステップ１）。
【００７１】
(II)次に、第１画像Ａ１と第２画像Ａ２との重なり部および第２画像Ａ２と第３画像Ａ３との重なり部の抽出処理が行われる（ステップ２）。この重なり部の抽出処理は、たとえば、ＳＳＤ法（Sum of Squared Difference)、正規化相互相関法に基づいて行われる。
【００７２】
（ａ）ＳＳＤ法の説明
ＳＳＤ法では、まず、重なり部を抽出すべき２枚の画像それぞれについて、原画像より解像度の低い画像Ｉ1 ，Ｉ2 が生成される。２枚の低解像度画像Ｉ1 ，Ｉ2 の重なり部分ω（サイズ：Ｍ×Ｎ）が、次式１０に示すように画素あたりの２乗誤差Ｅを用いて求められる。画像間の移動量（ｄ）が可能な範囲で変化せしめられ、Ｅが最も小さい移動量（ｄ）から、重なり部が抽出される。
【００７３】
【数１０】
0003540696.tif 000011
【００７４】
（ｂ）正規化相互相関法の説明
正規化相互相関法では、まず、重なり部を抽出すべき２枚の画像それぞれについて、原画像より解像度の低い画像Ｉ1 ，Ｉ2 が生成される。２枚の低解像度画像Ｉ1 ，Ｉ2 の重なり部分ω（サイズ：Ｍ×Ｎ）が、次式１１に示すように正規化相互相関係数Ｃを用いて求められる。画像間の移動量（ｄ）が可能な範囲で変化せしめられ、Ｃが最も大きな移動量（ｄ）から、重なり部が抽出される。
【００７５】
【数１１】
0003540696.tif 000012
【００７６】
式１１において、Ｉ1 ￣、Ｉ2 ￣は、第１画像を固定させ、第２画像をｄだけ移動させたときの、両画像の重なり部における各画像それぞれの濃淡値の平均である。また、σ1 、σ2 は、第１画像Ｉ1 を固定させ、第２画像Ｉ2 をｄだけ移動させたときの、両画像の重なり部における各画像それぞれの濃淡値の分散である。
【００７７】
(III) 次に、特徴点抽出が行われる（ステップ３）。つまり、まず、第２画像Ａ２における第１画像Ａ１との重なり部分から、追跡に有効な複数の部分画像（矩形領域）が第１特徴点として抽出される。ただし、各特徴点は互いに重ならないように抽出される。具体的には、上述した固有値λmin （式８参照）の高い部分が特徴点として抽出される。
【００７８】
次に、第２画像Ａ２における第３画像Ａ３との重なり部分から、追跡に有効な複数の部分画像（矩形領域）が第２特徴点として抽出される。この際、第２画像Ａ２における第１画像Ａ１との重なり部分から抽出された第１特徴点のうち、第２画像Ａ２と第３画像Ａ３とが重なっている部分に存在する第１特徴点は、第２特徴点としても用いられる。
【００７９】
(IV)次に、特徴点追跡処理が行われる（ステップ４）。つまり、抽出された第２画像Ａ２上の第１特徴点に対する第１画像Ａ１上の位置が追跡されるとともに、抽出された第２画像Ａ２上の第２特徴点に対する第３画像Ａ３上の位置が追跡される。
【００８０】
具体的には、まず、〔１〕で説明したオプティカルフロー推定方法で、適当なサイズ（例えば、１３×１３）のパッチ毎のオプティカルフローベクトルが求められる。第２画像Ａ２上の第１特徴点に対応する第１画像Ａ１上の位置は、第２画像Ａ２上の第１特徴点の４近傍のパッチのフローベクトルから線形補間により画素単位以下で求められる。同様に、第２画像Ａ２上の第２特徴点に対応する第３画像Ａ３上の位置は、第２画像Ａ２上の第２特徴点の４近傍のパッチのフローベクトルから線形補間により画素単位以下で求められる。
【００８１】
これにより、第１画像Ａ１と第２画像Ａ２との重なり部において、両画像の対応点の座標が得られる。また、第２画像Ａ２と第３画像Ａ３との重なり部において、両画像の対応点の座標が得られる。この結果、第１画像Ａ１、第２画像Ａ２および第３画像Ａ３の重なり部において、３つの画像の対応点の座標が得られる。
【００８２】
(V) 次に、trifocalテンソルの算出処理が行なわれる（ステップ５）。まず、trifocalテンソルの算出方法の概要について説明する。
【００８３】
shashua は、静止物体を異なる３視点から撮像した透視投影の３画像ψ1 、ψ2 およびψ3 の間には、次式１２のような線形な関係があることを示した（A.Shashua,"Algebraic functions for recognition," IEEE PAMI, Vol.17, No.8, pp.779-789, 1995参照) 。この関係は、Trilinearityと呼ばれている。
【００８４】
【数１２】
0003540696.tif 000013
【００８５】
すなわち、ある３次元空間上の点Ｘを撮像した各画像での座標を（ｘ，ｙ）∈ψ1 、（ｘ’，ｙ’）∈ψ2 および（ｘ”，ｙ”）∈ψ3 とすると、これらの座標値は、数式１３〜数式１６を満足する。
【００８６】
【数１３】
0003540696.tif 000014
【００８７】
【数１４】
0003540696.tif 000015
【００８８】
【数１５】
0003540696.tif 000016
【００８９】
【数１６】
0003540696.tif 000017
【００９０】
ただし、係数αj は全ての点で固定であり、これらの比は唯一に定まる。これらの係数は、共通して観察している特徴点の対応関係から導出することが可能である。そして、この関係は、テンソルを用いて、コンパクトに記述され、trifocalテンソルと呼ばれる（R.Hartley," Lines and points in three views and the trifocal tensor, "Int'l J. Computer Vision, vol.22, no.2, pp. 125-140,
1997.  参照）。
【００９１】
このように、Trilinearityを用いると、ある３次元空間上の点が２視点から撮像でき、その点の各画像での座標値がわかれば、もう一方の視点から観察した場合の座標を算出できる。すなわち、２画像の点の座標をそれぞれｕ’、ｕ”およびtrifocalテンソルをＴとすると、もう一つの画像での座標ｕは、次式１７によって求められる。
【００９２】
【数１７】
0003540696.tif 000018
【００９３】
これを用いると、図１０に示すように、視点Ｃ1 から観察できない部分であっても、他の２視点Ｃ2 およびＣ3 から観察され、それらの各画像での座標値が求まるなら、視点Ｃ1 から観察されたときの座標を計算することができる。この操作を他の画素についても繰り返すと、図１０の点線のように仮想的にＣ1 の撮像面を拡大することができる。
【００９４】
次に、trifocalテンソルの算出方法をより具体的に説明する。
trifocalテンソルは、第１画像Ａ１、第２画像Ａ２および第３画像Ａ３が互いに重なる部分における３画像での特徴点（対応点）の組から算出される。そこで、まず、第１画像Ａ１、第２画像Ａ２および第３画像Ａ３が互いに重なる部分における３画像の対応点の座標値を、数値演算を安定化させるために正規化する。そして、正規化された座標値と、数式１３〜１６とに基づいて、数式１３〜１６中の各係数αj （trifocalテンソル）を求める。
【００９５】
trifocalテンソルは、少なくとも７組の特徴点の対応があれば、解くことができる。しかしながら、実画像では誤差を含むので、より多くの対応点の組を用いて最小２乗的に解くのが一般的である。ここでの問題は、特徴点の対応づけの正確さが完全でないことである。
【００９６】
全ての特徴点を自動に正確に対応づけることは困難である。そこで、ロバスト推定を用いてこの問題を解決する。
【００９７】
ロバスト推定法は、次の２つに分類できる。第１は、Ｍ推定と呼ばれ、誤差の大きさに従って重みを決定する重み付き最小２乗法である。第２は、ランダムサブサンプリングを繰り返し、外れ値を除去しながら、あらかじめ指定したコストが減少した場合に解を更新する方法である。
【００９８】
何れのロバスト推定法を用いてtrifocalテンソルを算出してもよい。ここでは、ランダムサンプリングを繰り返す方法をさらに改良した方法を用いることにする。ランダムサンプリングを繰り返す方法では、中間値を最小化するように係数を更新するＬＭＳ(Least Median of Squares) が代表的であるが、ここでは、ＲＡＮＳＡＣ(Randam Sample Consensus) と呼ばれる方法を改良して用いる。
【００９９】
ＲＡＮＳＡＣについては、M.A.Fishler and R.C.Bolles,"Randam sample consensus: A pradigm for model fitting with applications to image nalysis and automated cartography," Communications of the ACM, vol.24, no.6, pp.381-395.1981. を参照のこと。
【０１００】
ＲＡＮＳＡＣは、まず、サンプルの一部Ｊを用いて最小２乗法で係数αJ を求める。そして、予め設定したしきい値θ（たとえば３画素）以上に誤差がある対応点の組を外れ値（誤対応）として、しきい値以下の対応点の組の個数を求める。この個数が前の結果よりも多くなった場合、係数（trifocalテンソル）を更新する。ここで、しきい値以下の対応点の組の個数が同じ場合でも、しきい値以下の対応点の組の２乗誤差が少なくなった場合は、更新するように改良する。
【０１０１】
(VI)このようにして、trifocalテンソル（係数αj ）が求められると、図１１に示すように、第２画像Ａ２のうち、第３画像Ａ３と重なっている部分を、特徴点を頂点とする３角パッチに分割する（ステップ６）。
【０１０２】
(VII) 次に、第２画像Ａ２上の３角パッチの各頂点それぞれに対応する、第２画像Ａ２と第３画像Ａ３の座標の組と、trifocalテンソルとに基づいて、第２画像Ａ２の３角パッチの各頂点（特徴点）に対応する第１画像Ａ１上の点の座標を求める（ステップ７）。
【０１０３】
つまり、上記ステップ５で求められたtrifocalテンソル（係数αj ）を、数式１３、１４に代入することによって、第１画像Ａ１、第２画像Ａ２および第３画像Ａ３との間の対応関係を示す関係式を得る。
【０１０４】
得られた関係式に、第２画像Ａ２上の３角パッチの各頂点それぞれに対応する、第２画像Ａ２と第３画像Ａ３の座標の組をそれぞれ代入していくことにより、第２画像Ａ２の３角パッチの各頂点（特徴点）に対応する第１画像Ａ１上の座標を求める。
【０１０５】
(VIII)次に、第２画像Ａ２上の各３角パッチ毎に、３角パッチ内の画素を第１画像Ａ１に変換するための平面射影変換行列を算出する（ステップ８）。
【０１０６】
まず、シーンを単一平面と仮定した場合の平面射影変換行列の求め方について述べる。
【０１０７】
図１２に示すように３次元空間中の単一平面の点Ｍを２つの異なる視点Ｃ１、Ｃ２から観察した時、これらの各画像面での座標ｍ、ｍ’の間の変換は、線形であることが射影幾何学において知られており、homography  と呼ばれている(O.Faugeras,"Three-Dimentional Computer Vision: A Geometric Viewpoint",MIT Press, 1993.)。
【０１０８】
すなわち、画像座標を斉次座標で表した第２画像の点ｍ’＝（ｘ’, ｙ’, １）t は、第１画像上で対応する点ｍ＝（ｘ ,ｙ, １）t を持ち、それらの関係は次式１８、より詳しくは次式１９で定義される。
【０１０９】
【数１８】
0003540696.tif 000019
【０１１０】
【数１９】
0003540696.tif 000020
【０１１１】
この変換行列は、次式２０のように書き換えることができる。
【０１１２】
【数２０】
0003540696.tif 000021
【０１１３】
また、式２０は、次式２１のように書き換えることができる。
【０１１４】
【数２１】
0003540696.tif 000022
【０１１５】
平面射影変換行列Ｈの未知パラメータ数は、８個であり、一組の対応点は、数式２１に示すように、２つの式を与える。したがって、４組以上の対応点があれば、最小２乗法によりこの行列Ｈを求めることができる。
【０１１６】
上記は、シーンを単一平面と仮定した場合の平面射影変換行列Ｈの求め方について説明したが、室内などのシーンの場合には、シーンを単一平面で近似するには誤差が大きすぎる。なぜなら、カメラから対象物までの距離に対して、シーンの奥行きの方が深いからである。この結果、第１画像と第２画像とを合成した場合に、両画像の重なり部分において、重なるべき線が２重になったり、ぼけたりするという問題がある。
【０１１７】
そこで、この実施の形態では、奥行きの深いシーンを合成する場合に適した平面射影変換行列Ｈを獲得するために、図１１を用いて既に説明したように、第２画像Ａ２内の第３画像Ａ３と重なる部分を、特徴点に基づいて３角パッチに分割し、各パッチ毎に平面射影変換行列を算出するようにした。
【０１１８】
各パッチ毎に平面射影変換行列を算出するには、エピポーラ拘束条件が利用される。各パッチ毎に平面射影変換行列を算出方法には、エピポーラ拘束条件を示す基礎行列を利用する方法と、エピポーラ拘束条件を示すエピポール（エピ極）の対応を利用する方法とがある。
【０１１９】
（ａ）基礎行列を利用する方法
カメラ間のエピポーラ拘束条件を示す基礎行列を利用する方法について説明する。平面射影変換行列の自由度は８であるので、４組の対応点の組が必要である。しかし、３角パッチの頂点は３つしかないので、一般では解けない。
【０１２０】
そこで、本発明者は、カメラ間のエピポーラ拘束を示す基礎行列Ｆと、３組の対応点を用いて、各３角パッチ毎の平面射影変換行列を算出することを開発した。
【０１２１】
以下、３角パッチ毎の平面射影変換行列を算出する方法について詳述する。
【０１２２】
図１３は、エピポーラ拘束条件を示している。
【０１２３】
３次元の空間の点Ｍを異なる視点Ｃ1 およびＣ2 から観察したとき、それぞれのカメラの撮像面Ｓ1 、Ｓ2 上の座標ｍ1 およびｍ2 は、Ｍ、Ｃ1 およびＣ2 で構成される平面上にある必要がある。これは、エピポーラ拘束条件と呼ばれる。また、視点Ｃ1 とＣ2 とを結ぶ直線と、各撮像面Ｓ1 、Ｓ2 との交点はｅ1 、ｅ2 は、エピポールと呼ばれる。このエピポーラ拘束条件を示す基礎行列Ｆおよび対応するエピポールｅ1 、ｅ2 は、２画像間で７組以上の対応点があれば、計算することができることが知られている。
【０１２４】
２画像間のエピポーラ拘束条件は、基礎行列Ｆと、対応点ｍ、ｍ’を用いて次式２２で表される。
【０１２５】
【数２２】
0003540696.tif 000023
【０１２６】
この基礎行列Ｆを７組以上、たとえば、８組の対応点から求める。基礎行列Ｆの求め方は、良く知られているのでその説明を省略する（たとえば、１９９８年４月２０日  共立出版発行の「３次元ビジョン」参照）。なお、最近では、キャリブレーションされていないステレオカメラの基礎行列を、対応づけられた特徴点対から、良好に獲得する手法が提案されているので、その手法を用いることが好ましい（Z.Zhang, "Determining the Epipolar Geometry and its Uncertainty; A Review", Int. Journal of Comuter Vision, Vol.27, No.2, pp. 161-195.,1988 ) 。
【０１２７】
上記式１８に示すように、ｍ＝Ｈｍ’であるので、式１８を式２２に代入することにより、次式２３が得られる。
【０１２８】
【数２３】
0003540696.tif 000024
【０１２９】
上記式２３における行列ＨT Ｆは、ベクトルｍ’の外積であることを表すので、次式２４に示すように非対称行列である必要がある。
【０１３０】
【数２４】
0003540696.tif 000025
【０１３１】
３組の対応点に基づいて上記式２１から６個の方程式が得られる。また、上記式２４から６個の方程式が得られる。つまり、１２個の方程式が得られる。平面射影変換行列Ｈの未知数は、８個であるので、これらを連立させた最小２乗法により、３角パッチ毎の平面射影変換行列Ｈを算出することができる。
【０１３２】
つまり、３組の対応点を｛（ｍ1 ，ｍ1 ’）、（ｍ2 ，ｍ2 ’）、（ｍ3 ，ｍ3 ’）とすると、上記式２１に基づいて、次式２５で表されるように、６個の方程式が得られる。
【０１３３】
【数２５】
0003540696.tif 000026
【０１３４】
上記式２４は、次式２６で表される。
【０１３５】
【数２６】
0003540696.tif 000027
【０１３６】
対角要素は０であるという条件から、次式２７で表されるように３つの方程式が得られる。
【０１３７】
【数２７】
0003540696.tif 000028
【０１３８】
また、上記式２６における非対称行列の−ａ１＋ａ１＝０であるという条件から、次式２８で表されるように１つの方程式が得られる。
【０１３９】
【数２８】
0003540696.tif 000029
【０１４０】
また、上記式２６における非対称行列のａ２−ａ２＝０であるという条件から、次式２９で表されるように１つの方程式が得られる。
【０１４１】
【数２９】
0003540696.tif 000030
【０１４２】
また、上記式２６における非対称行列の−ａ３＋ａ３＝０であるという条件から、次式３０で表されるように１つの方程式が得られる。
【０１４３】
【数３０】
0003540696.tif 000031
【０１４４】
上記式２７〜３０から、次式３１で表されるように、６個の方程式が得られる。
【０１４５】
【数３１】
0003540696.tif 000032
【０１４６】
上記式２５と上記式３１とを連立させると、次式３２で表されるように、１２個の方程式が得られる。
【０１４７】
【数３２】
0003540696.tif 000033
【０１４８】
平面射影変換行列Ｈの未知数は８個であるので、最小２乗法を用いて、３角パッチに対する平面射影変換行列Ｈが算出される。
【０１４９】
（ｂ）エピポールの対応を利用する方法
エピポールの対応を利用する方法について説明する。エピポールの対応は、基礎行列Ｆから求められる。この方法は、２画像間における３角パッチの３頂点の対応点の組と、２画像間のエピポールの対応点から、３角パッチ毎の平面射影行列を求める方法である。
【０１５０】
図１４は、Ｎ、Ｍ、Ｐを頂点とする３角パッチと、エピポールｅ1 、ｅ2 とを示している。
【０１５１】
エピポールｅ1 、ｅ2 は、３角パッチの位置および姿勢にかかわらず、常に同じである。２画像間における３角パッチの３頂点の対応点の組（３組の対応点）と、２画像間におけるエピポールの対応点（１組の対応点）とから合計４組の対応点が求まる。
【０１５２】
この４組の対応点（ｘi ，ｙi ）、（ｘi ’，ｙi ’）（ｉ＝１，２，３，ｅ）と、上記式２１とに基づいて、次式３３で表されるように、８個の方程式が得られる。
【０１５３】
【数３３】
0003540696.tif 000034
【０１５４】
平面射影行列の要素（ｈ1 〜ｈ8 ）は８つであるので、８個の方程式から、これらの要素ｈ1 〜ｈ8 が求められる。
【０１５５】
(IX)  求められた各３パッチ毎の平面射影変換行列に基づいて、第２画像Ａ２の各３角パッチ内の画像を第１画像に合成する（ステップ９）。
【０１５６】
つまり、第２画像Ａ２における各３角パッチ内の各画素に対応する第１画像上の座標値が、当該３角パッチに対して算出された平面射影変換行列Ｈを用いて求められる。そして、第２画像Ａ２の各３角パッチ内の各画素に対応する第１画像上の座標値を用いて、第２画像Ａ２の各３角パッチ内の画像が第１画像に合成される。
【０１５７】
(X) この後、第１画像Ａ１と第２画像Ａ２とが互いに重なり合っている部分（以下、重合部という）に対して画素値調合が行われる（ステップ１０）。つまり、第１画像Ａ１と第２画像Ａ２とは、撮影条件が同じでないので、一方に比べて他方が暗い場合がある。そこで、両画像の重合部において、両画像の画素値が調合せしめられる。
【０１５８】
画素値調合方法の一例について説明する。図１５は、ステップ１０において生成された画像を示している。図１５の斜線部分は、第１画像Ａ１と第２画像Ａ２とが重なり合っている部分（重合部）である。図１５において、Ｇ１は第１画像Ａ１の重心位置を、Ｇ２は第３画像Ａ２の重心位置をそれぞれ示している。
【０１５９】
重合部内の任意の点Ｐの第１画像Ａ１の画素値をＩ1 とし、点Ｐの第２画像Ａ２の画素値をＩ2 とし、点Ｐと第１画像Ａ１の重心位置Ｇ1 との距離をｄ1 とし、点Ｐと第２画像Ａ２の重心位置Ｇ2 との距離をｄ2 とすると、点Ｐの調合後の画素値Blenは、次式３４で表される。
【０１６０】
【数３４】
0003540696.tif 000035
【０１６１】
上記実施の形態では、第２画像Ａ２の各３角パッチ毎に平面射影変換行列Ｈを求め、第２画像Ａ２の各３角パッチ内の各画素に対応する第１画像Ａ２上の座標値を、当該３角パッチに対して算出された平面射影変換行列Ｈを用いて求めているが、各３角パッチ毎にアフィン変換行列Ａを求め、第２画像Ａ２における各３角パッチ内の各画素に対応する第１画像Ａ１上の座標値を、当該３角パッチに対して算出されたアフィン変換行列Ａを用いて求めるようにしてもよい。
【０１６２】
アフィン変換行列Ａは、次式３５で表される。アフィン変換行列Ａの要素ｈ1 〜ｈ6 は６つであるので、２画像間における３角パッチの３頂点の対応点のみから、要素ｈ1 〜ｈ6 を算出することができる。
【０１６３】
【数３５】
0003540696.tif 000036
【０１６４】
アフィン変換行列Ａの要素ｈ1 〜ｈ6 と、２画像間における３角パッチの３頂点の対応点（ｘi ，ｙi ）、（ｘi ’，ｙi ’）（ｉ＝１，２，３）との関係は、次式３６で表される。
【０１６５】
【数３６】
0003540696.tif 000037
【０１６６】
【発明の効果】
この発明によれば、奥行きの深いシーンを合成する際においても、精度の高い位置合わせが行えるようになる。
【０１６７】
この発明によれば、複数の画像から継目のないパノラマ画像を得ることができ、しかも複数の画像を撮像するためのカメラに自由な運動を許容し、焦点距離の測定が不要となる。
【図面の簡単な説明】
【図１】図１は、階層的推定法を説明するための図であって、階層１の画像を示す模式図である。
【図２】図２は、階層的推定法を説明するための図であって、階層２の画像を示す模式図である。
【図３】図３は、階層的推定法を説明するための図であって、階層３の画像を示す模式図である。
【図４】図４は、階層的推定法を説明するための図であって、階層４の画像を示す模式図である。
【図５】図５は、実施例で採用されたオプティカルフロー推定方法において行われる膨張処理を説明するための模式図である。
【図６】図６（ａ）は、ある階層の画像に対してしきい値処理されたオプティカルフローの例を示す模式図であり、図６（ｂ）は、補完後のオプティカルフローを示す模式図である。
【図７】図７は、パノラマ画像合成に用いられる３枚の画像を示す模式図である。
【図８】図８は、パノラマ画像合成装置の構成を示すブロック図である。
【図９】図９は、パノラマ画像合成処理手順を示すフローチャートである。
【図１０】図１０は、Trilinearityを用いたパノラマ画像合成方法を示す模式図である。
【図１１】図１１は、第２画像のうち、第３画像とのみ重なり合う部分を３角パッチによって分割した様子を示す模式図である。
【図１２】図１２は、平面射影変換行列を説明するための説明図である。
【図１３】図１３は、エピポーラ拘束条件を示す模式図である。
【図１４】図１４は、Ｎ、Ｍ、Ｐを頂点とする３角パッチと、エピポールｅ1 、ｅ2 とを示す模式図である。
【図１５】図１５は、画素値調合方法の一例を説明するための説明図である。
【符号の説明】
１０  パーソナルコンピュータ
１１  ＣＰＵ
１２  メモリ
１３  ハードディスク
１４  ディスクドライブ
【図１】
0003540696.tif 000038
【図２】
0003540696.tif 000039
【図３】
0003540696.tif 000040
【図４】
0003540696.tif 000041
【図５】
0003540696.tif 000042
【図６】
0003540696.tif 000043
【図７】
0003540696.tif 000044
【図８】
0003540696.tif 000045
【図９】
0003540696.tif 000046
【図１０】
0003540696.tif 000047
【図１１】
0003540696.tif 000048
【図１２】
0003540696.tif 000049
【図１３】
0003540696.tif 000050
【図１４】
0003540696.tif 000051
【図１５】
0003540696.tif 000052