(57)【要約】【課題】複数のカメラの視点が一直線上に存在せず、また、当該カメラの向きが一致しない状況において、対応点探索のテンプレートマッチング処理が単純なマルチプルベースラインステレオ法を実施することを可能とする。【解決手段】本発明は、入力された複数の画像からある１枚の画像をベース画像として選択し、ベース画像以外の画像のそれぞれ１枚と、ベース画像とからなる複数のステレオペアを構成し、複数のステレオペアのそれぞれについて平行化を行い、複数のステレオペアの平行化された画像に対してマルチプルベースラインステレオ法を適用し、被写体の世界座標を求めることにより、該被写体の３次元形状を抽出する。【選択図】　　　図１
2004133556.tif 000002
【特許請求の範囲】
【請求項１】
複数のカメラによって同一の被写体を撮影した複数の画像からマルチプルベースライン法を用いて該被写体の３次元形状を抽出する三次元形状抽出方法において、
前記複数のカメラによって同一の被写体を撮影した複数の画像を入力し、
前記複数のカメラの内部カメラパラメータ及び外部カメラパラメータを入力し、
入力された前記複数の画像からある１枚の画像をベース画像として選択し、
前記ベース画像以外の画像のそれぞれ１枚と、前記ベース画像とからなる複数のステレオペアを構成し、
前記複数のステレオペアのそれぞれについて平行化を行い、
前記複数のステレオペアの平行化された画像に対して前記マルチプルベースラインステレオ法を適用し、前記被写体の世界座標を求めることにより、該被写体の３次元形状を抽出することを特徴とする三次元形状抽出方法。
【請求項２】
前記平行化を行う際に、
前記ステレオペアの２画像を撮影した２つのカメラの視点を結ぶ直線の方向ｂを求め、
前記方向ｂに垂直である方向ｈを一つ定め、
前記方向ｂと該方向ｈに垂直である方向ｅを求め、
前記ステレオペアの画像を撮影したカメラの向きを、視点を動かさずに、視軸が前記方向ｅを向き、水平方向が前記方向ｂと平行し、垂直方向が前記方向ｈを向くように回転させ、かつ、前記内部カメラパラメータをある所定の値に変更し、再度撮影した場合に得られるような画像を作成する請求項１記載の三次元形状抽出方法。
【請求項３】
前記平行化を行う際に、
全てのカメラの平均焦点距離ｆ’を求め、
カメラａの変数ａに１を代入し、
前記ベース像Ｉ１　と画像Ｉａ＋１　をステレオペアａとし、該ステレオペアａに対して向きの基準となる直交する単位ベクトルｂ，ｈ，ｅを求め、
前記ベース画像Ｉ１　を変換するための画像変換行列ＭＢａを求め、
前記ベース画像Ｉ１　を前記画像変換行列ＭＢａによって、カメラのｘ軸、ｙ軸、視軸を前記単位ベクトルに沿うように回転し、前記平均焦点距離にして同じ被写体を再度撮影した場合に得られる画像と等価になるように変換し、画像Ｉ’ａ１を求め、
前記画像Ｉａ＋１　について、カメラａ＋１の視線が前記単位ベクトルのベースラインに垂直なベクトルｅを向き、かつスクリーンのＸ軸が、前記ステレオペアのベースカメラの視点から他方のカメラの視点への直線の向きと一致するベクトルｂを向くように回転させ、焦点距離を前記平均焦点距離ｆ’としたとき、像がどのように変化するかを表す変換行列ＭＴａを求め、
前記画像Ｉａ＋１　を前記変換行列ＭＴａによって変換し、画像Ｉ’ａ＋１　を求め、
前記変数ａにａ＋１を代入し、全画像の枚数Ｎになるまで前記単位ベクトルｂ，ｈ，ｅを求める処理以降の処理を繰り返す請求項２記載の三次元形状抽出方法。
【請求項４】
複数のカメラによって同一の被写体を撮影した複数の画像からマルチプルベースライン法を用いて該被写体の３次元形状を抽出する三次元形状抽出プログラムであって、
前記複数のカメラによって同一の被写体を撮影した複数の画像を入力するステップと、
前記複数のカメラの内部カメラパラメータ及び外部カメラパラメータを入力するステップと、
入力された前記複数の画像からある１枚の画像をベース画像として選択するステップと、
前記ベース画像以外の画像のそれぞれ１枚と、前記ベース画像とからなる複数のステレオペアを構成するステップと、
前記複数のステレオペアのそれぞれについて平行化を行うステップと、
前記複数のステレオペアの平行化された画像に対して前記マルチプルベースラインステレオ法を適用し、前記被写体の世界座標を求めることにより、該被写体の３次元形状を抽出するステップと、を有し、
前記平行化を行うステップは、
前記ステレオペアの２画像を撮影した２つのカメラの視点を結ぶ直線の方向ｂを求めるステップと、
前記方向ｂに垂直である方向ｈを一つ定めるステップと、
前記方向ｂと該方向ｈに垂直である方向ｅを求めるステップと、
前記ステレオペアの画像を撮影したカメラの向きを、視点を動かさずに、視軸が前記方向ｅを向き、水平方向が前記方向ｂと平行し、垂直方向が前記方向ｈを向くように回転させ、かつ、前記内部カメラパラメータをある所定の値に変更し、再度撮影した場合に得られるような画像を作成するステップと、を含むことを特徴とする三次元形状抽出プログラム。
【請求項５】
複数のカメラによって同一の被写体を撮影した複数の画像からマルチプルベースライン法を用いて該被写体の３次元形状を抽出する三次元形状抽出プログラムを格納した記憶媒体であって、
前記複数のカメラによって同一の被写体を撮影した複数の画像を入力するステップと、
前記複数のカメラの内部カメラパラメータ及び外部カメラパラメータを入力するステップと、
入力された前記複数の画像からある１枚の画像をベース画像として選択するステップと、
前記ベース画像以外の画像のそれぞれ１枚と、前記ベース画像とからなる複数のステレオペアを構成するステップと、
前記複数のステレオペアのそれぞれについて平行化を行うステップと、
前記複数のステレオペアの平行化された画像に対して前記マルチプルベースラインステレオ法を適用し、前記被写体の世界座標を求めることにより、該被写体の３次元形状を抽出するステップと、を有し、
前記平行化を行うステップは、
前記ステレオペアの２画像を撮影した２つのカメラの視点を結ぶ直線の方向ｂを求めるステップと、
前記方向ｂに垂直である方向ｈを一つ定めるステップと、
前記方向ｂと該方向ｈに垂直である方向ｅを求めるステップと、
前記ステレオペアの画像を撮影したカメラの向きを、視点を動かさずに、視軸が前記方向ｅを向き、水平方向が前記方向ｂと平行し、垂直方向が前記方向ｈを向くように回転させ、かつ、前記内部カメラパラメータをある所定の値に変更し、再度撮影した場合に得られるような画像を作成するステップと、を含むことを特徴とする三次元形状抽出プログラムを格納した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、三次元形状抽出方法及び三次元形状抽出プログラム及び三次元形状抽出プログラムを格納した記憶媒体に係り、特に、物体形状計測システム、仮想現実構築システムなどにおいて、複数のカメラで撮影された画像から、被写体の形状を得るための三次元形状抽出方法及び三次元形状抽出プログラム及び三次元形状抽出プログラムを格納した記憶媒体に関する。
【０００２】
【従来の技術】
物体の３次元形状を測定する方法として、ステレオ法が知られている（例えば、非特許文献１）。
【０００３】
ステレオ法は、２枚の写真を用いて、被写体の像点の位置から、その像点に対応する被写体の点の位置を算出する方法である。
【０００４】
ステレオ法の原理を図１６を用いて説明する。
【０００５】
図１６は、２台のピンホールカメラで同一の物体点Ｐ（ｐｘ　，ｐｙ　，ｐｚ　）１０３を撮影する状況を示したものである。なお、点Ｐの座標（ｐｘ　，ｐｙ　，ｐｚ　）は、カメラ１のカメラ座標で表す。点１０１は、カメラ１の視点を、座標軸１０２は、カメラ１のカメラ座標系を表している。スクリーン１０４は、カメラ１のスクリーンであり、焦点距離はｆである。カメラ１で点Ｐ１０３を撮影すると、点Ｐはスクリーン１０４上の点（Ｘ，Ｙ）１０５に投影される。ここで、カメラ１に対してｘ軸方向に距離Ｌだけ平行移動した位置にカメラ２があるとする。点１０６は、カメラ２の視点を、座標軸１０７は、カメラ２のカメラ座標系を表している。スクリーン１０８は、カメラ２のスクリーンであり、焦点距離はｆである。カメラ１とカメラ２は同一方向を向いており、カメラ座標系は互いに平行である。カメラ２で点Ｐを撮影すると、点Ｐは、スクリーン１０８上の点（Ｘ’，Ｙ’）１０９に投影される。カメラは、ｘ軸方向に平行移動しただけであるので、点１０５と点１０９のＹ座標は、同一である。ここで、点（Ｘ，Ｙ）と点（Ｘ’，Ｙ’）のＸ座標の差ｄを視差という。仮に、スクリーン１０８上の座標（Ｘ，Ｙ）に点１１０をとると、点１１０と点１０９のＸ距離が視差となる。視差は、カメラから見た物体点の奥行きによって変化するので、視差がわかれば、物体点の奥行きを計算することができる。視差をｄとすると、点Ｐの座標を数式１により求めることができる。
【０００６】
数式１　　　…　（ｐｘ　，ｐｙ　，ｐｚ　）＝（ＸＬ／ｄ，ＹＬ／ｄ，ｆＬ／ｄ）ステレオ法は、測定対象物体を計測するための特別な装置を必要としないことや、測定対象物体に接触する必要もないので、物体を傷つける恐れもなく、大きな物体でも計測できるという長所がある。
【０００７】
しかしながら、２枚の写真の間で、同一物体を対応付ける、対応点探索が困難であるという問題がある。対応点探索には、像点の周囲の小領域（ウィンドウと呼ぶ）を比較し、最も良く似ている点同士を同一点と見做す、いわゆるテンプレートマッチングの方法がよく用いられる。例えば、縦２ｗ＋１画素、横２ｗ＋１画素の矩形領域をウィンドウとし、画像Ｉ０　の点（ｘ０　，ｙ０　）と、画像Ｉ１　の点（ｘ１　，ｙ１　）の類似度は、数式２によって求められる。数式２は、点（ｘ０　，ｙ０　）、点（ｘ１　，ｙ１　）の近傍で、点（ｘ０　，ｙ０　），点（ｘ１　，ｙ１　）から同一の値（ｉ，ｊ）だけオフセットさせた点同士を比較することを表している。
【０００８】
【数１】
2004133556.tif 000003
テンプレートマッチングによる同一点探索では、一般に、被写体に周期的な模様がある場合には、誤った点を同一点と認識してしまう可能性があるという問題がある。また、一方のカメラから見えている点がもう一方のカメラから見えていない状態、いわゆるオクルージョンが発生している状態を正しく判定するのは困難である。
【０００９】
これらのステレオ法の問題を解決するために、マルチプルベースラインステレオ法（以下、ＭＢＳと記す）（例えば、非特許文献２）が提案されている。この方法は、３台以上のカメラで撮影した画像を用いて、誤対応の排除と距離計測の精度向上を達成する方法である。この方法は、ある１枚の画像を基準画像とし、基準画像と他の１枚の画像によってステレオペアを複数構成し、ある像点の奥行きを変数とし、各々のステレオペアにおけるテンプレートマッチングの評価値（類似度）の合計値を最小にする奥行きを物体点の奥行きとするものである。
【００１０】
しかしながら、上記のＭＢＳの方法では、複数台のカメラの視点が正確に一直線上にあり、すべてのカメラがその直線と垂直である同一方向を向いていることが前提となっている。このようにカメラを配置するには、設置において精密な調整が必要となる。この制限を緩和し、カメラの配置が前述の条件から外れている場合でも、ＭＢＳを改良して適用可能な方法がある（例えば、非特許文献３）。この方法では、予めカメラの姿勢を測定しておき、ある画像の点の他方の画像における対応点を探索する際に、対応点の存在する可能性のある点の座標を座標変換によって求め（対応点の存在する可能性のある点の集合はエピポーラ線となる）、探索するようにする。
【００１１】
【非特許文献１】
Ｂａｒｎａｒｄ，Ｓ．Ｔ．　ａｎｄ　Ｍ．Ａ．Ｆｉｓｃｈｌｅｒ，”Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｓｔｅｒｏ，”　Ｃｏｍｐｕｔｉｎｇ　Ｓｕｒｖｅｙｓ，　ｖｏｌ．１４．ｎｏ．４，１９８２，ｐｐ．５５３−５７２．
【非特許文献２】
Ｍ．Ｏｋｕｔｏｍｉ　ａｎｄ　Ｔ．Ｋａｎａｄｅ，　”Ａ　ｍｕｌｔｉｐｌｅ−ｂａｓｅｌｉｎｅ　ｓｔｅｒｏ，”　ＩＥＥＥ　ＰＡＭＩ，　ｖｏｌ．１５，ｎｏ．４，ｐｐ．３５３−３６３，１９９３．
【非特許文献３】
Ｒ．Ｙ．Ｔｓａｉ，　”Ａ　Ｖｅｒｓａｔｉｌｅ　Ｃａｍｅｒａ　Ｃａｌｉｂｒａｔｉｏｎ　Ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　Ｈｉｇｈ−Ａｃｃｕｒａｃｙ　３Ｄ　Ｍａｃｈｉｎｅ　Ｖｉｓｉｏｎ　Ｍｅｔｒｏｌｏｇｙ　Ｕｉｎｇ　Ｏｆｆ−ｔｈｅ　Ｓｈｅｌｆ　ＴＶ　Ｃａｍｅｒａｓ　ａｎｄ　Ｌｅｎｓｅｓ，　”ＩＥＥＥ　Ｊｏｕｒｎａｌ　ｏｆ　Ｒｏｂｏｔｉｃｓ　ａｎｄ　Ａｕｔｏｍａｔｉｏｎ，　Ｖｏｌ．ＲＡ−３，Ｎｏ．４，　ｐｐ．３２３−３４４，　１９８７．
【発明が解決しようとする課題】
しかしながら、上記のＭＢＳを改良して適用可能な方法では、テプレートマッチングのウィンドウ内の１画素の比較を行う度に、座標変換を行う必要が生じる。その分テンプレートマッチングの処理が複雑になる。
【００１２】
本発明は、上記の点に鑑みなされたもので、複数のカメラの視点が一直線上に存在せず、また、当該カメラの向きが一致しない状況において、対応点探索のテンプレートマッチング処理が単純なマルチプルベースラインステレオ法を実施することが可能な三次元形状抽出方法及び三次元形状抽出プログラム及び三次元形状抽出プログラムを格納した記憶媒体を提供することを目的とする。
【００１３】
【課題を解決するための手段】
図１は、本発明の原理を説明するための図である。
【００１４】
本発明は、複数のカメラによって同一の被写体を撮影した複数の画像からマルチプルベースライン法を用いて該被写体の３次元形状を抽出する三次元形状抽出方法において、
複数のカメラによって同一の被写体を撮影した複数の画像を入力し（ステップ１）、
複数のカメラの内部カメラパラメータ及び外部カメラパラメータを入力し（ステップ２）、
入力された複数の画像からある１枚の画像をベース画像として選択し（ステップ３）、
ベース画像以外の画像のそれぞれ１枚と、ベース画像とからなる複数のステレオペアを構成し（ステップ４）、
複数のステレオペアのそれぞれについて平行化を行い（ステップ５）
複数のステレオペアの平行化された画像に対してマルチプルベースラインステレオ法を適用し、被写体の世界座標を求めることにより、該被写体の３次元形状を抽出する（ステップ７）。
【００１５】
本発明は、平行化を行う際に、
ステレオペアの２画像を撮影した２つのカメラの視点を結ぶ直線の方向ｂを求め、
方向ｂに垂直である方向ｈを一つ定め、
方向ｂと該方向ｈに垂直である方向ｅを求め、
ステレオペアの画像を撮影したカメラの向きを、視点を動かさずに、視軸が方向ｅを向き、水平方向が方向ｂと平行し、垂直方向が該方向ｈを向くように回転させ、かつ、内部カメラパラメータをある所定の値に変更し、再度撮影した場合に得られるような画像を作成する。
【００１６】
また、本発明は、平行化を行う際に、
全てのカメラの平均焦点距離ｆ’を求め、
カメラａの変数ａに１を代入し、
ベース像Ｉ１　と画像Ｉａ＋１　をステレオペアａとし、該ステレオペアａに対して向きの基準となる直交する単位ベクトルｂ，ｈ，ｅを求め、
ベース画像Ｉ１　を変換するための画像変換行列ＭＢａを求め、
ベース画像Ｉ１　を画像変換行列ＭＢａによって、カメラのｘ軸、ｙ軸、視軸を単位ベクトルに沿うように回転し、平均焦点距離にして同じ被写体を再度撮影した場合に得られる画像と等価になるように変換し、画像Ｉ’ａ１を求め、
画像Ｉａ＋１　について、カメラａ＋１の視線が単位ベクトルのベースラインに垂直なベクトルｅを向き、かつスクリーンのＸ軸が、ステレオペアのベースカメラの視点から他方のカメラの視点への直線の向きと一致するベクトルｂを向くように回転させ、焦点距離を平均焦点距離ｆ’としたとき、像がどのように変化するかを表す変換行列ＭＴａを求め、
画像Ｉａ＋１　を変換行列ＭＴａによって変換し、画像Ｉ’ａ＋１　を求め、
変数ａにａ＋１を代入し、全画像の枚数Ｎになるまで単位ベクトルｂ，ｈ，ｅを求める処理以降の処理を繰り返す。
【００１７】
本発明は、複数のカメラによって同一の被写体を撮影した複数の画像からマルチプルベースライン法を用いて該被写体の３次元形状を抽出する三次元形状抽出プログラムであって、
複数のカメラによって同一の被写体を撮影した複数の画像を入力するステップと、
複数のカメラの内部カメラパラメータ及び外部カメラパラメータを入力するステップと、
入力された複数の画像からある１枚の画像をベース画像として選択するステップと、
ベース画像以外の画像のそれぞれ１枚と、ベース画像とからなる複数のステレオペアを構成するステップと、
複数のステレオペアのそれぞれについて平行化を行うステップと、
複数のステレオペアの平行化された画像に対してマルチプルベースラインステレオ法を適用し、被写体の世界座標を求めることにより、該被写体の３次元形状を抽出するステップと、を有し、
平行化を行うステップは、
ステレオペアの２画像を撮影した２つのカメラの視点を結ぶ直線の方向ｂを求めるステップと、
方向ｂに垂直である方向ｈを一つ定めるステップと、
方向ｂと該方向ｈに垂直である方向ｅを求めるステップと、
ステレオペアの画像を撮影したカメラの向きを、視点を動かさずに、視軸が方向ｅを向き、水平方向が方向ｂと平行し、垂直方向が該方向ｈを向くように回転させ、かつ、内部カメラパラメータをある所定の値に変更し、再度撮影した場合に得られるような画像を作成するステップと、を含む。
【００１８】
本発明は、複数のカメラによって同一の被写体を撮影した複数の画像からマルチプルベースライン法を用いて該被写体の３次元形状を抽出する三次元形状抽出プログラムを格納した記憶媒体であって、
複数のカメラによって同一の被写体を撮影した複数の画像を入力するステップと、
複数のカメラの内部カメラパラメータ及び外部カメラパラメータを入力するステップと、
入力された複数の画像からある１枚の画像をベース画像として選択するステップと、
ベース画像以外の画像のそれぞれ１枚と、ベース画像とからなる複数のステレオペアを構成するステップと、
複数のステレオペアのそれぞれについて平行化を行うステップと、
複数のステレオペアの平行化された画像に対してマルチプルベースラインステレオ法を適用し、被写体の世界座標を求めることにより、該被写体の３次元形状を抽出するステップと、を有し、
平行化を行うステップは、
ステレオペアの２画像を撮影した２つのカメラの視点を結ぶ直線の方向ｂを求めるステップと、
方向ｂに垂直である方向ｈを一つ定めるステップと、
方向ｂと該方向ｈに垂直である方向ｅを求めるステップと、
ステレオペアの画像を撮影したカメラの向きを、視点を動かさずに、視軸が方向ｅを向き、水平方向が方向ｂと平行し、垂直方向が該方向ｈを向くように回転させ、かつ、内部カメラパラメータをある所定の値に変更し、再度撮影した場合に得られるような画像を作成するステップと、を含む。
【００１９】
上記のように、本発明では、画像を平行化し、平行された画像に対してマルチプルベースラインステレオ法を実施することにより、対応点探索のための座標変換の計算量を削減することが可能となる。
【００２０】
【発明の実施の形態】
以下、図面と共に本発明の実施の形態について説明する。
【００２１】
図２は、本発明の一実施の形態における被写体を複数のビデオカメラで撮影する撮影系を示し、図３は、本発明の一実施の形態における撮影された映像から被写体の３次元形状を復元する情報処理系を示す。
【００２２】
図２に示す撮影系は、ビデオカメラ２０１〜２０５と、キャリブレーションパタン２０６から構成される。ビデオカメラ２０１〜２０５は、位置や向きを厳密に揃えて配置しなくともよい。但し、撮影中に動かないように固定する必要がある。各々のビデオカメラは、ビデオテープに映像を記録できるようになっている。キャリブレーションパタン２０６は、模様の描かれた板を用意してもよいし、床に模様を描いて利用してもよい。模様は図の通りでなくとも、３次元座標（位置）が既知である点が複数識別できればよい。点の必要数は条件により異なってくるが、少なくとも５点は必要である。この詳細については、文献『Ｒ．Ｙ．　Ｔｓａｉ，”Ａ　Ｖｅｒｓａｔｉｌｅ　Ｃａｍｅｒａ　Ｃａｌｉｂｒａｔｉｏｎ　Ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　Ｈｉｇｈ−Ａｃｃｕｒａｃｙ　３Ｄ　Ｍａｃｈｉｎｅ　Ｖｉｓｉｏｎ　Ｍｅｔｒｏｌｏｇｙ　Ｕｓｉｎｇ　Ｏｆｆ−ｔｈｅ−Ｓｈｅｌｆ　ＴＶ　Ｃａｍｅｒａｓ　ａｎｄ　Ｌｅｎｓｅｓ，　”ＩＥＥＥ　Ｊｏｕｎａｌｏｆ　Ｒｏｂｏｔｉｃｓ　ａｎｄ　Ａｕｔｏｍａｔｉｏｎ，　Ｖｏｌ．ＲＡ−３，Ｎｏ．４，　ｐｐ．３２３−３４４，　１９８７』（以下文献１）を参照されたい。
【００２３】
本実施の形態では、ビデオカメラ２０３をベースカメラとし、ビデオカメラ２０３で撮影した画像をベース画像とする。本手法では、ベースカメラ以外のカメラは、ベースカメラとの向きの差が９０度以内になるよう設置する必要がある。
なお、ビデオカメラとしてはピンホールカメラモデルを用いる。
【００２４】
図３の情報処理系は、ビデオカメラ再生装置３０１と、映像入力装置３０２と、情報処理装置３０３と、表示装置３０４と、マウスなどの入力装置３０５とからなる。
【００２５】
以下、上記の構成における動作を説明する。
【００２６】
図４は、本発明の一実施の形態における処理のフローチャートである。
【００２７】
ステップ４０１）　まず、カメラキャリブレーションを行う。カメラキャリブレーションは、ビデオカメラの外部パラメータと内部パラメータを得る処理である。外部パラメータとしては、カメラの位置と姿勢がある。内部パラメータとしては、焦点距離やレンズ歪などがある。実際の空間の何処か１点を世界座標の原点に定め、ｘ軸、ｙ軸、ｚ軸の方向を直交するように定め、ビデオカメラ２０１〜２０６から同時に映るようにキャリブレーションパタン２０７を置き、撮影する。それぞれのカメラで撮影された画像から、それぞれのカメラのパラメータを得る。得られるパラメータは、カメラ外部パラメータＲ，Ｔｘ，Ｔｙ，Ｔｚと、内部パラメータの焦点距離ｆ、レンズ歪みｋである。Ｒは、３×３行列であり、その他はスカラーである。実施の詳細については、前述の文献１を参照されたい。なお、本実施の形態では、レンズ歪みが小さく、ｋ＝０と見做せるものとして説明する。
【００２８】
カメラキャリブレーションによって、被写体のある点の世界座標と、カメラによってその点を撮影した像点の画像座標との変換が可能となる。世界座標が（ｘｗ　，ｙｗ　，ｚｗ　）である点をあるカメラによって撮影された画像を図５とする。図５の点５０１が撮影された点の像点であるとする。当該像点の画像座標を（Ｘ，Ｙ）とすると、次の数式４を用いて、世界座標から画像座標を計算することができる。
【００２９】
【数２】
2004133556.tif 000004
ここで、Ｄｘ　，Ｄｙ　は、座標の単位を変換するための定数であり、画像の１画素に相当するＣＣＤ上の矩形の縦、横長を表す定数である。
【００３０】
なお、本実施の形態では、図５に示されているように、画像座標は、原点を画像の中心にとり、右方向にＸ軸、下方向にＹ軸を取り、画素を単位として表すものとする。
【００３１】
ステップ４０２）　図６に示すように、撮影系を用いて被写体の撮影を行う。このとき、カメラキャリブレーションを行った状態と同じ状態で撮影を行うようにする。後の工程で同時刻の映像を選択できるようにするために、すべてのカメラを同期しておく。例えば、同時刻に同一のタイムコードが記録されるようにしておく。複数のカメラから同時に被写体が映るように被写体を配置し、被写体を撮影し、映像をビデオテープに記録する。
【００３２】
ステップ４０３）　ステップ４０２で撮影した映像を情報処理系に入力する。ビデオテープをビデオカメラ２０１〜２０５から取り出し、ビデオ再生装置３０１に装填し、映像入力装置３０２を用いて映像をデジタル化し、情報処理装置３０３に入力する。
【００３３】
ステップ４０４）　入力した画像を平行化する。カメラは厳密には一直線上に並んでおらず、向きも異なる。そこで、入力画像を変形し、カメラの視点が１直線状に並び、カメラの向きがその直線に垂直な同一方向であるような状態で撮影された場合に得られる画像を作成する。これは、カメラの方向を変えて再度撮影して画像を得る代わりに、画像の変形によって同等の画像を得る処理である。この画像変形処理を平行化という。平行化の手順の詳細なフローチャートを図７に示す。
【００３４】
図７のフローチャートに基づいて、平行化の手順を説明する。
【００３５】
入力画像として、図８に示すような画像があるとする。画像Ｉ１　〜Ｉ５　は、被写体を同時刻に異なる位置から撮影した画像である。ここで、Ｉ１　はベースカメラ２０３から撮影したベース画像である。Ｉ２　はビデオカメラ２０１から撮影された画像、Ｉ３　はビデオカメラ２０２から撮影された画像、Ｉ４　はビデオカメラ２０４から撮影された画像、Ｉ５　は、ビデオカメラ２０５から撮影された画像を表している。ビデオカメラと被写体の距離が同一である保証はないので、被写体の像の大きさが同一である保証はなく、カメラが傾いている可能性もあるので、像も傾いている可能性がある。
【００３６】
本実施の形態では、被写体が全ての画像において映っていると仮定して説明する。
【００３７】
カメラの台数をＮとおく。本実施の形態では、図２に示すように、Ｎ＝５である。
【００３８】
以下の説明では、ビデオカメラ２０３をベースカメラまたは、カメラ１と呼ぶ。また、ビデオカメラ２０１をカメラ２と呼ぶ。ビデオカメラ２０２をカメラ３と呼ぶ。ビデオカメラ２０４２をカメラ４と呼ぶ。ビデオカメラ２０５をカメラ５と呼ぶ。ステップ４０１でカメラａについて得られたカメラパラメータをＲａ，Ｔａｘ，Ｔａｙ，Ｔａｚ，ｆａ　とする。
【００３９】
平行化される前のもとの状態では、カメラ毎にスクリーン（ＣＣＤ）の１画素に相当する矩形の大きさが異なる可能性がある。カメラａのこの矩形の幅を定数Ｄｘａ、高さを定数Ｄｙａとする。平行化によって１画素の矩形の大きさが一致するような画像を作成する。その平行化後の１画素の矩形の幅及び高さ共に、Ｄｒ　とする。平行化後は、画素は正方形になるようにする。Ｄｒ　は、任意の正数でよいが、本実施の形態では、ベースカメラの１画素の矩形の幅と一致させる（Ｄｒ　＝Ｄｘ１）。
【００４０】
ステップ７０１）　全カメラの焦点距離の平均ｆ’を求める。
【００４１】
【数３】
2004133556.tif 000005
平行化される前のもとの状態では、カメラ毎に焦点距離が異なるが、平行化後は、焦点距離がｆ’であるように統一する。
【００４２】
ステップ７０２）　変数ａに１を代入する。以下では、ベース画像Ｉ１　と、画像Ｉａ＋１　をステレオペアａとし、これら２枚の画像に対して処理を行う。
【００４３】
ステップ７０３）　ステレオペアａに対してカメラの向きを仮想的に揃えるために、向きの基準となる直交する単位ベクトル
【００４４】
【数４】
2004133556.tif 000006
を定める。
【００４５】
【数５】
2004133556.tif 000007
は、ワールド座標で表記したベクトルである。
【００４６】
【数６】
2004133556.tif 000008
は、ステレオペアのベースカメラの視点から他方のカメラの視点への直線（ベースライン）の向きと一致させる。ベースラインのワールド座標表記を求めるためには、カメラ視点の座標をワールド座標で表記しなければならない。カメラ１のワールド座標
【００４７】
【数７】
2004133556.tif 000009
は、次の数式５によって得られる。
【００４８】
【数８】
2004133556.tif 000010
同様に、カメラａ＋１のワールド座標
【００４９】
【数９】
2004133556.tif 000011
は、次の数式６によって得られる。
【００５０】
【数１０】
2004133556.tif 000012
よって、
【００５１】
【数１１】
2004133556.tif 000013
は、次の数式７によって得られる。
【００５２】
【数１２】
2004133556.tif 000014
【００５３】
【数１３】
2004133556.tif 000015
の決定には、任意性があるが、本実施の形態では、
【００５４】
【数１４】
2004133556.tif 000016
と、ベースカメラの視線とは張る平面の法線ベクトルを
【００５５】
【数１５】
2004133556.tif 000017
とする。具体的には、数式８のように、カメラ１の視線方向と
【００５６】
【数１６】
2004133556.tif 000018
との外積によって定める。
【００５７】
【数１７】
2004133556.tif 000019
これに限らず、
【００５８】
【数１８】
2004133556.tif 000020
【数１９】
2004133556.tif 000021
と、ベースカメラの視線方向とカメラａ＋１の視線方向の線形結合とが張る平面の法線ベクトルによって定めてもよいし、
【００５９】
【数２０】
2004133556.tif 000022
を定数としてもよい。最後に、数式９によって
【００６０】
【数２１】
2004133556.tif 000023
を求める。
【００６１】
【数２２】
2004133556.tif 000024
このようにして求めた
【００６２】
【数２３】
2004133556.tif 000025
は、ベースラインに垂直になっている。
【００６３】
以上述べたステップ７０３の処理について図９を用いて説明する。点Ｃ１　は、ベースカメラの視点、点Ｃａ＋１　９０２はカメラａ＋１の視点、矢印９０５は、ベースカメラの視線方向、矢印９０６はカメラａ＋１の視線方向、ベースカメラの焦点距離はｆ１であり、カメラａ＋１の焦点距離はｆａ＋１　である。点Ｃ１　９０１と、点Ｃａ＋１　９０２を結んだ直線９０３がベースラインであり、ベースラインと同じ向きに単位ベクトル
【００６４】
【数２４】
2004133556.tif 000026
を採る。
【００６５】
【数２５】
2004133556.tif 000027
と矢印９０５に垂直な方向に単位ベクトル
【００６６】
【数２６】
2004133556.tif 000028
をとる。最後に
【００６７】
【数２７】
2004133556.tif 000029
に垂直な向きに
【００６８】
【数２８】
2004133556.tif 000030
をとる。
【００６９】
【数２９】
2004133556.tif 000031
は、ベースライン９０３に垂直になっている。
【００７０】
ステップ７０４）　ベース画像を変換するための変換行列ＭＢａを求める。この変換行列ＭＢａは、ベースカメラの視線が
【００７１】
【数３０】
2004133556.tif 000032
を向き、かつ、スクリーンのＸ軸が
【００７２】
【数３１】
2004133556.tif 000033
を向くように回転させ、焦点距離を平均焦点距離ｆ’としたとき、像がどのように変化するかを表すものである。
【００７３】
図９を用いて説明する。図９の矢印９０４は、ベースカメラの向きを仮想的に回転させた後の方向を表している。スクリーン９０９の回転前のベースカメラのスクリーン、スクリーン９０８は、回転後のベースカメラのスクリーンを表している。矢印９０４は、ベクトル
【００７４】
【数３２】
2004133556.tif 000034
と同じ向きであり、スクリーン９０８のｘ軸は、ベクトル
【００７５】
【数３３】
2004133556.tif 000035
と同じ向きであり、スクリーン９０８のｙ軸は、ベクトル
【００７６】
【数３４】
2004133556.tif 000036
と同じ向きである。
【００７７】
まず、元のベース画像の像点をベースカメラのスクリーン上にある点と対応付ける。画像座標で（Ｘ，Ｙ）ｔ　である点は、ベースカメラのカメラ座標で（Ｄｘ１Ｘ，Ｄｙ１Ｙ，ｆ１　）ｔ　でる点に対応付けられる。なお、ここでは、画像座標の単位は画素であり、カメラ座標の単位はワールド座標単位と同じである（メートルなど）。
【００７８】
カメラのｘ軸、ｙ軸、視軸をベクトル
【００７９】
【数３５】
2004133556.tif 000037
に合わせるような回転行列の逆行列をＱとする。
【００８０】
【数３６】
2004133556.tif 000038
をベースカメラのカメラ座標系で記述すると、
【００８１】
【数３７】
2004133556.tif 000039
であるので、
【００８２】
【数３８】
2004133556.tif 000040
である。
【００８３】
【数３９】
2004133556.tif 000041
は、縦ベクトル
【００８４】
【数４０】
2004133556.tif 000042
を並べて３×３行列を作ることを指す。カメラを回転させる代わりに、カメラを固定して、点が逆に回転すると考えれば、この逆の回転はＱで表される。
【００８５】
最後に、回転後のスクリーン上の点（Ｘ’，Ｙ’，Ｚ’）ｔ　を、焦点距離ｆ’であるスクリーンに投影した点（Ｘ”，Ｙ”）ｔ　は、数式１０により求まる。
【００８６】
【数４１】
2004133556.tif 000043
まとめると、数式１１及び数式１２により、ベース画像の点（Ｘ，Ｙ）ｔ　を、点（Ｘ”，Ｙ”）ｔ　に変換することができる。
【００８７】
【数４２】
2004133556.tif 000044
ここで、ｄｉａｇ（ａ，ｂ，ｃ）は、ａ，ｂ，ｃを対角成分に持つ対角行列を表す。変換行列ＭＢａは、数式１１のように定義する。
【００８８】
また、逆に数式１３及び数式１４により、変換後の画像の点（Ｘ”，Ｙ”）ｔ　を、ベース画像の点（Ｘ，ｙ）ｔ　に逆変換することができる。
【００８９】
【数４３】
2004133556.tif 000045
ステップ７０５）　変換行列ＭＢａによって、ベース画像Ｉ１　を変換し、画像Ｉ’ａ１を作成する。
【００９０】
一般に、この変換により被写体の位置が変わるので、変換後の画像は、変換後の像を含むことが可能な大きさにする必要がある。変換後の画像の大きさを見積もる手順を、図１０を用いて説明する。
【００９１】
図１０の画像１００１はベース画像Ｉ１　を表し、画像１００１は変換後の画像Ｉ’ａ１を表す。点（Ｘｃ１，Ｙｃ１）１００２、点（Ｘｃ２，Ｙｃ２）１００３、点（ＸＣ３，Ｙｃ３）１００４、点（Ｘｃ４，Ｙｃ４）１００５は、ベース画像の四隅を表す。点（Ｘ”ｃ１，Ｙ”ｃ１）１００６は点１００２を数式１１及び数式１２によって変換した点を表す。同様に、点１００７、点１００８、点１００９は、点１００３、点１００４、点１００５を同様に変換した点を表す。なお、ここでは、座標の単位は画素とする。
【００９２】
変換後の画像の縦の長さ（画素数）Ｈ、横の長さ（画素数）Ｗは、元のベース画像の四隅を変換した点が入るように定める。即ち、
Ｗ＝２ＭＡＸｉ　｜Ｘ”ｃｉ｜
Ｈ＝２ＭＡＸｉ　｜Ｙ”ｃｉ｜
とする。ここで、ＭＡＸは、最大値を表す。
【００９３】
画像の変換は、元のベース画像の点を、変換行列ＭＢａを用いた数式１１及び数式１２によって写像することにより行う。実装上は、変換後の画像を隙間無く生成するために、変換後の画像の１画素毎に、元のベース画像から画像の輝度値をサンプリングすることにより画像変換を行う。変換後の画像の全画素（Ｘ”，Ｙ”）について、数式１３及び数式１４によって元のベース画像の対応点（Ｘ，Ｙ）の座標を算出し、（Ｘ，Ｙ）に最も近い画素の輝度値を、画素（Ｘ”，Ｙ”）に設定する。（Ｘ，Ｙ）が元のベース画像の外側である場合には、画素（Ｘ”，Ｙ”）に既定値を設定する。このサンプリング方法は、ｎｅａｒｅｓｔ−ｎｅｉｇｈｂｏｒ法と呼ばれる方法であるが、他のサンプリング法を用いてもよい。
【００９４】
【数４４】
2004133556.tif 000046
に沿うように回転し、焦点距離を平均焦点距離ｆ’にして同じ被写体を再度撮影した場合に得られる画像と等価である。
【００９５】
ステップ７０６）　画像Ｉａ＋１　を変換するための変換行列ＭＴａを求める。この変換行列ＭＴａは、カメラａ＋１の視線が
【００９６】
【数４５】
2004133556.tif 000047
を向き、かつ、スクリーンのＸ軸が
【００９７】
【数４６】
2004133556.tif 000048
を向くように回転させ、焦点距離を平均焦点距離ｆ’としたとき、像がどのように変化するかを表すものである。
【００９８】
図９の矢印９０７は、カメラａ＋１のスクリーン、スクリーン９１１は回転後のカメラａ＋１のスクリーンを表している。矢印９０７はベクトル
【００９９】
【数４７】
2004133556.tif 000049
と同じ向きであり、スクリーン９１１のｘ軸は、ベクトル
【０１００】
【数４８】
2004133556.tif 000050
と同じ向きであり、スクリーン９１１のｙ軸はベクトル
【０１０１】
【数４９】
2004133556.tif 000051
と同じ向きである。
【０１０２】
本ステップの処理は、対象がベースカメラでなく、カメラａ＋１である点を除けば、ステップ７０４と同じであるので、詳細な説明は省略するが、数式１５及び数式１６により、画像Ｉａ＋１　の点（Ｘ，Ｙ）ｔ　を、点（Ｘ”，Ｙ”）に変換することができる。
【０１０３】
【数５０】
2004133556.tif 000052
変換行列ＭＴａは数式１５のように定義する。
【０１０４】
また、逆に数式１７及び数式１８により、変換後の画像の点（Ｘ”，Ｙ”）ｔ　を、画像Ｉａ＋１　の点（Ｘ，Ｙ）ｔ　に逆変換することができる。
【０１０５】
【数５１】
2004133556.tif 000053
ステップ７０７）　変換行列ＭＴａによって、画像Ｉａ＋１　を変換し、画像Ｉ’ａ，ａ＋１　を作成する。
【０１０６】
本ステップの処理は、処理対象がベース画像ではなく画像Ｉａ＋１　であることと、変換に用いる変換行列がＭＢａではなく、ＭＴａであることを除けば、ステップ７０５と同様であるので、手順の説明は省略する。
【０１０７】
得られた画像Ｉ’ａ，ａ＋１　は、カメラａ＋１のｘ軸、ｙ軸、視軸をベクトル
【０１０８】
【数５２】
2004133556.tif 000054
に沿うように回転し、焦点距離を平均焦点距離ｆ’にして同じ被写体を再度撮影した場合に得られる画像と等価である。
【０１０９】
ステップ７０８）　変数ａに１を加える。
【０１１０】
ステップ７０９）　変数ａと、画像の枚数Ｎを比較し、一致していなければステップ７０３へ戻り、次のペアについて同様に処理を行う。一致していれば、本平行化処理を終了する。
【０１１１】
平行化処理が終了すると、平行化されたベース画像Ｉ’１１，Ｉ’２１，…，Ｉ’Ｎ−１，１　と、それらとペアになる平行化された画像Ｉ’１２，Ｉ’２３，…，Ｉ’Ｎ−１，Ｎ　と、平行化のための変換行列ＭＢ１，ＭＢ２，…，　ＭＢＮ−１，ＭＴ１，ＭＴ２，…，ＭＴＮ−１が得られている。図１１に、これらの画像と変換行列との関係を示す。なお、同図では、Ｎ＝６として示している。
【０１１２】
以上でステップ４０４の平行化の処理の詳細の説明を終了する。
【０１１３】
ステップ４０５）　ステップ４０４で作成した変換後の画像に対して、ＭＢＳを適用し、ベース画像Ｉ１　の画素に対応する被写体の点の世界座標を求める。ＭＢＳの手順の詳細なフローチャートを図１２及び図１３に示す。
【０１１４】
以下、図１２及び図１３のフローチャートに基づいてＭＢＳの手順を説明する。
【０１１５】
ステップ１２０１）　ステレオペア毎にベースライン長Ｌａを求める。ステレオペアａのベースライン長Ｌａは、数式５及び数式６及び数式１９によって求めることができる。
【０１１６】
【数５３】
2004133556.tif 000055
ステップ１２０２）　最長ベースライン長Ｌｍａｘ　を求める。Ｌｍａｘ　は、Ｂａの中で最大のものでる。最長ベースライン長を与えるステレオペアをａｍａｘ　とする。
【０１１７】
ステップ１２０３）　変数ｘに−ｗｂ　を代入する。ｗｂ　は、変換前のベース画像の横幅の画素数の１／２である。
【０１１８】
ステップ１２０４）　変数ｙに−ｈｂ　を代入する。ｈｂ　は、変換前のベース画像の高さの画素数の１／２である。
【０１１９】
以下では、ベース画像の画像座標（ｘ，ｙ）の点に着目し、この点の３次元座標を計算する。
ステップ１２０５）　補正ベースライン長比Ｂａを求める。ステレオペアａのベースライン長比を、最大ベースライン長との比Ｌａ／Ｌｍａｘ　で定義する。カメラの向きを変えることにより、同一の点であっても見かけ上、奥行きが変化する。また、焦点距離を変えると、奥行きと視差の関係も変化する。そこで、これらの変化率でベースライン長を補正し、補正ベースライン長比とする。
【０１２０】
ベースライン長の補正方法を図１４を用いて説明する。図１４は、点Ｏを視点とするベースカメラから点Ｐを観測する状況を、平行化前のカメラ座標系１４１３と、平行化後のカメラ座標系１４１４で表したものである。点Ｏ１４０１は、視点、軸１４０２は、平行化前カメラ座標系のｘ軸、軸１４０３は、平行化前カメラ座標系のｚ軸を表す。平行化前カメラ座標系のｙ軸は、紙面に垂直である。点Ｐ１４０４は、ある物体点を表している。スクリーン１４０５は平行化前のベースカメラのスクリーンであり、焦点距離はｆ１　でる。平行化前の状態でベースカメラで点Ｐを撮影すると、点Ｐがスクリーン１４０５上の点１４０６に投影される。点Ｐのｚ座標（奥行き）はｐｚ　でる。ベースライン長をＬとしてステレオ法を用いれば、奥行きがｐｚ　である点に対して視差ｄが生じ、ｐｚ　＝Ｌｆ１　／ｄなる関係が成立する。
【０１２１】
ここで、平行化のためのカメラの視軸をｚ’軸に、ｘ軸をｘ’軸に（仮想的に）なるよう回転させたとする。点Ｏ１４０７は視点、軸１４０８は平行化後カメラ座標系のｘ軸、軸１４０９は平行化後カメラ座標系のｚ軸を表す。点Ｐ１４１０は、点１４０４と同じ物体点であり、動いていない。スクリーン１４１１は、平行化後のベースカメラのスクリーンであり、焦点距離はｆ’である。平行化後の状態でベースカメラで点Ｐ１４１０を撮影すると、点Ｐがスクリーン１４１１上の点１４１２に投影される。点Ｐのｚ’座標（奥行き）はｐ’ｚ　である。平行化後にベースライン長をＬとしてステレオ法を用いれば、奥行きがｐ’ｚ　である点に視差ｄ’ｍ　が生じ、ｐ’ｚ　＝Ｌｆ’／ｄｍ　なる関係が成立する。
【０１２２】
物体点Ｐの平行化前のカメラ座標を（ｐｘ　，ｐｙ　，ｐｚ　）、平行化後のカメラ座標を（ｐ’ｘ　，ｐ’ｙ　，ｐ’ｚ　）とすれば、数式２０の関係が成立する。
【０１２３】
本ステップ１２０５では、ベース画像の点（ｘ，ｙ）に着目しているのであるから、対応する物体点は、ベースカメラの視点と、スクリーン上の点（ｘＤｘ　，ｙＤｙ　，ｆ１　）を結ぶ直線上に存在するはずである。この場合には、平行化前後の物体点の見かけ上の奥行きには、数式２１の関係が成立する。従って、平行化前後の視差ｄｍ　，ｄ’ｍ　の間には、数式２２の関係が成立する。ここで、ｄｍ　，ｄ’ｍ　の単位は実世界の長さ（メートルなど）である。視差の単位を画素で表した平行化前後の視差ｄｐ　，ｄ’ｐ　の間には、数式２３の関係が成立する。
【０１２４】
【数５４】
2004133556.tif 000056
平行化後のステレオペアで得られた視差ｄ’から、ベースカメラの元のカメラ座標で奥行きｐｚ　を計算するためには、視差を数式２３によって補正する必要がある。数式２３の示す比率を予めベースライン長比に算入し、補正ベースライン長Ｂａとする。
【０１２５】
【数５５】
2004133556.tif 000057
ステップ１２０６）　変数Ｓｍｉｎ　に定数ＭＡＸＶＡＬを代入する。定数ＭＡＸＶＡＬは、変数Ｓｍｉｎ　の取り得る値の最大値（可能な限り大きい値）を代入する。視差探索変数ｄは、平行化前のベース画像Ｉ１　に対して、元の向きのままで、ベースライン長をＬｍａｘ　としてステレオ法を行った場合に発生するはずの視差（変移）を画素数で表したものとする。
【０１２６】
最適な視差ｄを探索するとき、視差の可能な定義行きを全て評価すると計算コストがかさむので、探索範囲を限定するようにする。ベースカメラの元のカメラ座標での被写体の奥行きの探索範囲の最大最小値を予め定め、Ｚｍａｘ　，Ｚｍｉｎ　とする。視差ｄの探索範囲の最大値ｄｍａｘ　は数式２５によって、ｄｍｉｎ　は数式２６によって求められる。
【０１２７】
【数５６】
2004133556.tif 000058
ステップ１２０７）　配列Ａｘ　，Ａｙ　に、ベース画像の画像座標を変換行列ＭＢａで変換した座標を格納する。Ａｘ　，Ａｙ　は３次元配列とし、ベース画像の点（ｘ，ｙ）を数式１１及び数式１２を用いてステレオペアａの平行化後ベース画像Ｉ’ａ１の座標（ｘｂ　，ｙｂ　）を計算し、Ａｘ　［ｘ，ｙ，ａ］にｘｂ　を、Ａｙ　［ｘ，ｙ，ａ］にｙｂ　を格納する。ベース画像のすべての画素、全てのステレオペアについてこの計算を行い、配列Ａｘ　，Ａｙ　に値を格納する。画像座標ｘ，ｙは負の値を取り得るが、配列の添字に負の値が使えるかどうかはプログラム処理系に依存する。添字に負の値が使えない場合は、座標値にオフセット値を加えるなどして、添字が０以上になるようにすればよい。
【０１２８】
ステップ１２０８）　変数ｄに値ｄｍｉｎ　を代入する。
【０１２９】
ステップ１２０９）　変数Ｓに０を代入する。
【０１３０】
ステップ１２１０）　変数Ｃｐ　に０を代入する。
【０１３１】
ステップ１２１１）　変数ａに１を代入する。
【０１３２】
ステップ１２１２）　平行化前のベース画像の点の座標（ｘ，ｙ）と変数ａを用いて、配列Ａｘ　，Ａｙ　からステレオペアａの平行化後ベース画像Ｉ’ａ１の座標（ｘｂ　，ｙｂ　）を得る。ｘｂ　＝Ａｘ　［ｘ，ｙ，ａ］，ｙｂ　＝Ａｙ　［ｘ，ｙ，ａ］である。
【０１３３】
図１５は、平行化前のベース画像Ｉ１　１５０１上の点１５０４が、平行化後ベース画像Ｉ’ａ１上の点１５０５に変換されたことを表している。図１５では、ａ＝１の場合について表している。ここで、ベースライン長をＬｍａｘ　としたとき、ベース画像１５０１の点１５０４の視差がＤであるとする。すると、平行化後のステレオペア１の画像Ｉ’１１とＩ’１２では、視差はＢ１　Ｄとなるはずである。即ち、点１５０４が、画像Ｉ’１２１５０３の点（ｘｂ　−Ｂ１　Ｄ，ｙｂ　）（点１５０６）に観測されるはずである。しかしながら、値Ｄは未知数なので、テンプレートマッチングの評価値の最小化によりＤを求める。
【０１３４】
以下のステップ１２１３以降では、視差をｄとした場合のテンプレートマッチングを行う。
【０１３５】
ステップ１２１３）　画像Ｉ’ａ１の点（ｘｂ　，ｙｂ　）の周囲のウィンドウと、画像Ｉ’ａ，ａ＋１　の点（ｘｂ　−Ｂａ　ｄ，ｙｂ　）の周囲のウィンドウがそれぞれの画像の中に収まるかを検査する。ウィンドウの形は通例、矩形領域とし、ウィンドウの大きさは１０×１０画素程度とするが、これに限るものではない。両画像でウィンドウが画像内に収まる場合には、ステップ１２１５に移行し、テンプレートマッチングを行う。収まらない場合には、テンプレートマッチングをスキップし、図１３のステップ１３０２に移行する。
【０１３６】
ステップ１２１４）　変数Ｃｐ　に１を加える。変数Ｃｐ　には、点（ｘ，ｙ）、視差ｄについて、テンプレートマッチングを行ったステレオペアの数が格納される。次に、図１３のステップ１３０１に移行する。
【０１３７】
以下図１３のフローチャートの処理を説明する。
【０１３８】
ステップ１３０１）　テンプレートマッチングの評価値を変数Ｓに加算する。画像Ｉ’ａ１の点（ｘｂ　，ｙｂ　）の周囲のウィンドウと、画像Ｉ’ａ，ａ＋１　の点（ｘｂ　−Ｂａ　ｄ，ｙｂ　）の周囲のウィンドウの対応する画素についての輝度のＳＳＤ（輝度値の差の二乗の合計）を計算し、テンプレートマッチングの評価値とする。ＳＳＤは、ウィンドウ内の画像の類似度を評価する尺度であり、似ているほど小さい値をとる。
【０１３９】
ステップ１３０２）　変数ａに１を加える。
【０１４０】
ステップ１３０３）　変数ａの値と、カメラ台数Ｎを比較し、ａ＝Ｎであれば、ステップ１３０４へ進み、そうでなければ図１２のステップ１２１２に移行し、次のステレオペアについてテンプレートマッチングを行う。
【０１４１】
ステップ１３０４）　変数Ｃｐ　の値を検査し、０より大きければステップ１３０５に移行し、評価値の比較を行う。そうでなければ、テンプレートマッチング実行可能なステレオペアが１組もなかったことを表しているので、評価値の比較をスキップし、ステップ１３０８に移行する。
【０１４２】
ステップ１３０５）　評価値の平均Ｓ／Ｃｐ　と、変数Ｓｍｉｎ　を比較し、Ｓ／Ｃｐ　の方が小さければ、ステップ１３０６へ移行し、変数Ｓｍｉｎ　を更新する。そうでなければ、Ｓｍｉｎ　の値を更新せずに、ステップ１３０８へ移行する。
【０１４３】
ステップ１３０６）　変数Ｓｍｉｎ　にＳ／Ｃｐ　の値を代入する。変数Ｓｍｉｎ　には、現時点での評価値Ｓ／Ｃｐ　の最小値が格納されている。
【０１４４】
ステップ１３０７）　変数Ｄに視差ｄの値を代入する。変数Ｄには、現時点での最小評価値Ｓ／Ｃｐ　を与える視差ｄが格納されている。
【０１４５】
ステップ１３０８）　変数ｄに刻み幅ｄｓｔｅｐを加える。ｄｓｔｅｐは、予め定めた定数で、例えば、１（画素）とする。これに限らず、他の値でもよい。
【０１４６】
ステップ１３０９）　ｄとｄｍａｘ　を比較し、ｄ＞ｄｍａｘ　であれば、ステップ１３１０に移行する。そうでなければ、図１２のステップ１２０９に移行し、次なる視差ｄについて評価を行う。
【０１４７】
ステップ１３１０）　変数Ｓｍｉｎ　の値と定数ＭＡＸＶＡＬを比較し、同値であれば、画素（ｘ，ｙ）について、テンプレートマッチングが１回も行われなかった、即ち、対応点が見つからなかったことを表している。Ｓｍｉｎ　＜ＭＡＸＶＡＬであば、点の奥行きの計算のためのステップ１３１１に移行する。そうでなければ、点の奥行き計算をスキップし、ステップ１３１２に移行する。
【０１４８】
ステップ１３１１）　変数ｘ，ｙ，Ｄの値から数式２７によって被写体の点の世界座標（ｘｗ　，ｙｗ　，ｚｗ　）を計算し、出力する。Ｄには、テプレートマッチングの評価値の最小値を与える視差ｄの値が格納されている。
【０１４９】
【数５７】
2004133556.tif 000059
ステップ１３１２）　変数ｙに１を加える。
【０１５０】
ステップ１３１３）　変数ｙの値とベース画像Ｉ１　の高さｈｂ　を比較し、ｙ＞ｈｂ　であれば、ステップ１３１４に移行する。そうでなければ、図１２のステップ１２０５に移行し、次なる画素についてＭＢＳを行う。
【０１５１】
ステップ１３１４）　変数ｘに１を加える。
【０１５２】
ステップ１３１５）　変数ｘの値とベース画像Ｉ１　の幅ｗｂ　を比較し、ｘ＞ｗｂ　であれば、ＭＢＳ処理を終了する。そうでなければ、図１２の１２０４に移行し、次なる画素についてＭＢＳを行い、奥行きの得られた点については３次元世界座標が出力されている。このようにして、被写体の形状を表す３次元の点群が得られる。
【０１５３】
本実施の形態で得られる物体点の奥行きは、視差Ｄの探索を刻み幅ｄｓｔｅｐで行うため、その刻み幅に応じた粗さでしか求まらないが、前述の文献（Ｍ．Ｏｋｕｔｏｍｉ　ａｎｄ　Ｔ．Ｋａｎａｄｅ，　”Ａ　ｍｕｌｔｉｐｌｅ−ｂａｓｅｌｉｎｅ　ｓｔｅｒｏ，”　ＩＥＥＥ　ＰＡＭＩ，　ｖｏｌ．１５，ｎｏ．４，ｐｐ．３５３−３６３，１９９３．）に示される方法などを用いて、さらに、細かい精度で視差を求め、奥行きを求めてもよい。
【０１５４】
また、ステップ１３０１で行うテンプレートマッチングの処理は、同一サイズの同一形状のウィンドウで、ウィンドウ内で相対的に同一の位置にある画素同士を比較することによって実施できる。この処理は単純であり、ハードウェアによる実装も比較的容易であるので、ハードウェア化による高速化が比較的容易である。
【０１５５】
また、上記のフローチャートで示した処理をプログラムとして構築し、三次元形状抽出装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることも可能である。
【０１５６】
また、構築されたプログラムを三次元形状抽出装置として利用されるコンピュータに接続されるハードディスク装置や、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、本発明を実施する際にインストールすることも可能である。
【０１５７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【０１５８】
【発明の効果】
上述のように、本発明によれば、画像を平行化し、平行化された画像に対してマルチプルベースラインステレオ法を実施すれば、対応点探索のための座標変換の計算量が削減でき、処理が高速化される。
【０１５９】
また、マルチプルベースラインステレオ法を適用する際に、テンプレートマッチングの処理が単純化され、ハードウェアによる計算の実行にも適するようになる。
【図面の簡単な説明】
【図１】本発明の原理を説明するための図である。
【図２】本発明の一実施の形態における被写体を複数のビデオカメラで撮影する撮影系を示す図である。
【図３】本発明の一実施の形態における撮影された映像から被写体の３次元形状を復元する情報処理系を示す図である。
【図４】本発明の一実施の形態における処理のフローチャートである。
【図５】本発明の一実施の形態における画像座標系の定義を示す図である。
【図６】本発明の一実施の形態における撮影系によって被写体の撮影の様子を示す図である。
【図７】本発明の一実施の形態における平行化の処理のフローチャートである。
【図８】本発明の一実施の形態における入力画像の例である。
【図９】本発明の一実施の形態における平行化の説明図である。
【図１０】本発明の一実施の形態における平行化画像の大きさの決定方法を示す図である。
【図１１】本発明の一実施の形態における画像の平行化と座標変換行列とステレオペアの関係を示す図である。
【図１２】本発明の一実施の形態におけるＭＢＳの処理のフローチャート（その１）である。
【図１３】本発明の一実施の形態におけるＭＢＳの処理のフローチャート（その２）である。
【図１４】本発明の一実施の形態におけるベースライン長の補正を説明するための図である。
【図１５】本発明の一実施の形態における平行化後の画像における対応点探索を説明するための図である。
【図１６】ステレオ法の原理を説明するための図である。
【符号の説明】
２０１〜２０５　ビデオカメラ
２０６　キャリブレーションパタン
３０１　ビデオ再生装置
３０２　映像入力装置
３０３　情報処理装置
３０４　表示装置
３０５　入力装置
５０１　点
６０１　被写体
Ｉ１　〜Ｉ５　　ベース画像
９０１　点Ｃ１
９０２　点Ｃａ＋１
９０３　直線（ベースライン）
９０４，９０５，９０６９０７　矢印
９０８，９０９，９１０，９１１　スクリーン
１００１　ベース画像Ｉ１
１００２　点（Ｘｃ１，Ｙｃ１）
１００３　点（Ｘｃ２，Ｙｃ２）
１００４　点（Ｘｃ３，Ｙｃ３）
１００５　点（Ｘｃ４，Ｙｃ４）
１００７，１００８，１００９　変換した点
１４０１，１４０７　視点Ｏ
１４０２，１４０３　軸
１４０４　点Ｐ
１４０５　スクリーン
１４０６　点
１４０８　平行化後カメラ座標系のｘ軸
１４０９　平行化後カメラ座標系のｚ軸
１４１０　点Ｐ
１４１１　平行化後のベースカメラのスクリーン
１４１２　点
１４１３　平行化前のカメラ座標系
１４１４　平行化後のカメラ座標系
１５０１　平行化前のベース画像Ｉ１
１５０３　画像Ｉ’１２の点
１５０４　平行化前のベース画像Ｉ１　上の点
１５０５　平行化後ベース画像Ｉ’１　上の点
１５０６　画像Ｉ’１２の点（ｘｂ　−Ｂ１　Ｄ，ｙｂ　）
【図１】
2004133556.tif 000060
【図２】
2004133556.tif 000061
【図３】
2004133556.tif 000062
【図４】
2004133556.tif 000063
【図５】
2004133556.tif 000064
【図６】
2004133556.tif 000065
【図７】
2004133556.tif 000066
【図８】
2004133556.tif 000067
【図９】
2004133556.tif 000068
【図１０】
2004133556.tif 000069
【図１１】
2004133556.tif 000070
【図１２】
2004133556.tif 000071
【図１３】
2004133556.tif 000072
【図１４】
2004133556.tif 000073
【図１５】
2004133556.tif 000074
【図１６】
2004133556.tif 000075