(57)【要約】【課題】撮像装置によって撮影された画像内において物体の存在範囲を表す線分の座標データを削減する。【解決手段】生成部１０１１は、３次元空間内における撮像装置の投影中心と、その撮像装置の投影面内において物体を表す点とを通る第１直線を、複数の画像各々に写像した第２直線上において、物体の存在範囲を表す線分を生成する。複数の画像は、上記撮像装置以外の複数の撮像装置それぞれによって撮影される。変換部１０１２は、複数の画像それぞれから生成された複数の線分各々について、線分の一方の端点の座標を、その端点の座標と他方の端点の座標との差分に変換し、記憶部１０１３は、他方の端点の座標と差分とを記憶する。復元部１０１４は、他方の端点の座標と差分とから、一方の端点の座標を復元する。判定部１０１５は、他方の端点の座標と一方の端点の座標とを、上記投影面の奥行き方向に写像した結果に基づいて、複数の線分の間における重複判定を行う。【選択図】図１０
2019114201.tif 000002
【特許請求の範囲】
【請求項１】
３次元空間内における撮像装置の投影中心と、前記撮像装置の投影面内において物体を表す点とを通る第１直線を、前記撮像装置以外の複数の撮像装置それぞれによって撮影された複数の画像各々に写像した第２直線上において、前記物体の存在範囲を表す線分を生成する生成部と、
前記複数の画像それぞれから生成された複数の線分各々について、前記画像内における前記線分の一方の端点の座標を、前記一方の端点の座標と他方の端点の座標との差分に変換する変換部と、
前記他方の端点の座標と前記差分とを記憶する記憶部と、
前記記憶部が記憶する前記他方の端点の座標と前記差分とから、前記一方の端点の座標を復元する復元部と、
前記他方の端点の座標と前記復元部が復元した前記一方の端点の座標とを、前記投影面の奥行き方向に写像した結果に基づいて、前記複数の線分の間における前記奥行き方向の重複判定を行う判定部と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記生成部は、前記３次元空間内の点を前記複数の画像各々に写像する写像情報を用いて、前記画像の水平方向の座標と前記画像の垂直方向の座標とによって記述される前記第２直線の方程式を求め、
前記記憶部が記憶する前記他方の端点の座標は、前記水平方向の座標又は前記垂直方向の座標のうちいずれか一方に対応する第１座標であり、前記記憶部が記憶する前記差分は、前記第１座標の差分であり、
前記復元部は、前記記憶部が記憶する前記他方の端点の前記第１座標と前記第１座標の差分とから、前記一方の端点の前記第１座標を復元し、前記第２直線の方程式を用いて、前記他方の端点の前記第１座標から、前記水平方向の座標又は前記垂直方向の座標のうち前記第１座標とは異なる第２座標を求め、前記第２直線の方程式を用いて、前記一方の端点の前記第１座標から前記一方の端点の前記第２座標を求め、前記他方の端点の前記第１座標及び前記第２座標と、前記一方の端点の前記第１座標及び前記第２座標とを、前記奥行き方向に写像することを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記一方の端点と前記他方の端点との間における前記第１座標の差分は、前記一方の端点と前記他方の端点との間における前記第２座標の差分よりも大きく、前記他方の端点の前記第１座標は整数型変数であり、前記第１座標の差分は整数型変数であることを特徴とする請求項１又は２記載の情報処理装置。
【請求項４】
前記変換部は、前記他方の端点の前記第１座標を表す整数型変数のビット幅を、前記他方の端点の前記第１座標の値に基づいて決定し、前記第１座標の差分を表す整数型変数のビット幅を、前記第１座標の差分の値に基づいて決定することを特徴とする請求項３記載の情報処理装置。
【請求項５】
前記生成部は、前記第２直線上において、前記物体の存在範囲を表す線分である第１線分を生成するとともに、前記物体を含む１つ又は複数の物体の存在範囲を表す複数の第２線分を生成し、
前記変換部は、前記複数の第２線分各々の端点の座標を、前記複数の第２線分各々の端点の座標と、前記複数の第２線分各々の他の端点の座標又は他の第２線分の端点の座標又は前記第１線分の一方の端点の座標との差分に変換し、
前記記憶部は、前記複数の線分各々の端点の座標から生成された差分をさらに記憶し、
前記復元部は、前記複数の線分各々の端点の座標から生成された差分から、前記複数の線分各々の端点の座標を復元し、復元した前記複数の線分各々の端点の座標を、前記奥行き方向に写像し、
前記判定部は、前記複数の画像それぞれから生成された複数の線分の間における前記奥行き方向の重複判定を行うことを特徴とする請求項１乃至４のいずれか１項に記載の情報処理装置。
【請求項６】
３次元空間内における撮像装置の投影中心と、前記撮像装置の投影面内において物体を表す点とを通る第１直線を、前記撮像装置以外の複数の撮像装置それぞれによって撮影された複数の画像各々に写像した第２直線上において、物体の存在範囲を表す線分を生成し、
前記複数の画像それぞれから生成された複数の線分各々について、前記画像内における前記線分の一方の端点の座標を、前記一方の端点の座標と他方の端点の座標との差分に変換し、
前記他方の端点の座標と前記差分とを記憶部に記憶させ、
前記記憶部が記憶する前記他方の端点の座標と前記差分とから、前記一方の端点の座標を復元し、
前記他方の端点の座標と復元した前記一方の端点の座標とを、前記投影面の奥行き方向に写像した結果に基づいて、前記複数の線分の間における前記奥行き方向の重複判定を行う、
処理をコンピュータに実行させるためのプログラム。
【請求項７】
コンピュータが、
３次元空間内における撮像装置の投影中心と、前記撮像装置の投影面内において物体を表す点とを通る第１直線を、前記撮像装置以外の複数の撮像装置それぞれによって撮影された複数の画像各々に写像した第２直線上において、物体の存在範囲を表す線分を生成し、
前記複数の画像それぞれから生成された複数の線分各々について、前記画像内における前記線分の一方の端点の座標を、前記一方の端点の座標と他方の端点の座標との差分に変換し、
前記他方の端点の座標と前記差分とを記憶部に記憶させ、
前記記憶部が記憶する前記他方の端点の座標と前記差分とから、前記一方の端点の座標を復元し、
前記他方の端点の座標と復元した前記一方の端点の座標とを、前記投影面の奥行き方向に写像した結果に基づいて、前記複数の線分の間における前記奥行き方向の重複判定を行う、
ことを特徴とする情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、及びプログラムに関する。
【背景技術】
【０００２】
近年、視体積交差法により、多視点映像に含まれる物体のシルエット画像から、その物体の３次元形状を復元するために、VisualHullと呼ばれる技術が用いられている。視体積交差法によれば、多視点からの複数のシルエットコーンの交差積が、物体の３次元形状として認識される。
【０００３】
サーバからクライアントへ描画差分情報を送信する技術、複数の２次元イメージから３次元イメージを構築する技術、及び複数の画像間のマッチングを行って３次元情報の再構成処理を行う技術も知られている（例えば、特許文献１〜特許文献３を参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−２３６３３４号公報
【特許文献２】特表平１１−５１２８５６号公報
【特許文献３】特開２０００−３３１１６０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
VisualHullでは、３次元空間内の物体をカメラの画面上に投影した点（シルエット）が、エピポーラ線上に存在するか否かを確認するために、物体の存在範囲を表す線分を探索する線分探索（交点探索）が行われる。そして、複数のカメラそれぞれの画面内で探索された複数の線分の座標がメモリに格納され、それらの線分の座標を用いて、３次元空間内における複数の線分の間の重複判定が行われる。しかしながら、線分探索によって探索される線分の本数が多くなると、メモリアクセスのオーバヘッドが大きくなる。
【０００６】
なお、かかる問題は、VisualHullにおいてエピポーラ線上の線分を探索する場合に限らず、撮像装置によって撮影された画像内において、他の方法により物体の存在範囲を表す線分を生成する場合においても生ずるものである。
【０００７】
１つの側面において、本発明は、撮像装置によって撮影された画像内において物体の存在範囲を表す線分の座標データを削減することを目的とする。
【課題を解決するための手段】
【０００８】
１つの案では、情報処理装置（コンピュータ）は、生成部、変換部、記憶部、復元部、及び判定部を含む。
【０００９】
生成部は、３次元空間内における撮像装置の投影中心と、その撮像装置の投影面内において物体を表す点とを通る第１直線を、複数の画像各々に写像した第２直線上において、物体の存在範囲を表す線分を生成する。複数の画像は、上記投影中心及び上記投影面を有する撮像装置以外の複数の撮像装置それぞれによって撮影された画像である。
【００１０】
変換部は、複数の画像それぞれから生成された複数の線分各々について、画像内における線分の一方の端点の座標を、一方の端点の座標と他方の端点の座標との差分に変換し、記憶部は、他方の端点の座標と差分とを記憶する。
【００１１】
復元部は、記憶部が記憶する他方の端点の座標と差分とから、一方の端点の座標を復元する。判定部は、他方の端点の座標と復元部が復元した一方の端点の座標とを、上記投影面の奥行き方向に写像した結果に基づいて、複数の線分の間における奥行き方向の重複判定を行う。
【発明の効果】
【００１２】
実施形態によれば、撮像装置によって撮影された画像内において物体の存在範囲を表す線分の座標データを削減することができる。
【図面の簡単な説明】
【００１３】
【図１】エピポーラ幾何を示す図である。
【図２】線分探索の探索範囲を示す図である。
【図３】物体の視体積を示す図である。
【図４】多視点から見たシルエットコーンを示す図である。
【図５】重複判定処理を示す図である。
【図６】マスク画像を示す図である。
【図７】５本の線分の間における重複判定処理を示す図である。
【図８】３次元形状構築部の機能的構成図である。
【図９】３次元形状構築部のハードウェア構成図である。
【図１０】情報処理装置の機能的構成図である。
【図１１】画像処理のフローチャートである。
【図１２】従来の線分探索処理における線分端座標を示す図である。
【図１３】実施形態の線分探索処理における線分端座標を示す図である。
【図１４】線分端座標の選択方法を示す図である。
【図１５】符号の決定方法を示す図である。
【図１６】各参照画像から複数の線分が探索された場合の重複判定処理を示す図である。
【図１７】情報処理装置の具体例を示す機能的構成図である。
【図１８】VisualHull処理のフローチャートである。
【図１９】エピポーラ線情報生成処理及び線分探索処理のフローチャートである。
【図２０】基準座標をＸ座標とする端点探索処理のフローチャートである。
【図２１】基準座標をＹ座標とする端点探索処理のフローチャートである。
【図２２】重複判定処理のフローチャートである。
【図２３Ａ】重複判定コア処理のフローチャート（その１）である。
【図２３Ｂ】重複判定コア処理のフローチャート（その２）である。
【図２４】並列化したVisualHull処理のフローチャートである。
【図２５】線分探索処理の探索結果を示す図である。
【図２６】探索結果を記憶する記憶領域を示す図である。
【図２７】自由視点映像生成処理を示す図である。
【図２８】自由視点画像を示す図である。
【図２９】自由視点映像装置の機能的構成図である。
【図３０】前景分離処理のフローチャートである。
【図３１】VisualHull部が行うVisualHull処理のフローチャートである。
【図３２】レンダリング処理のフローチャートである。
【図３３】情報処理装置のハードウェア構成図である。
【図３４】ローカルメモリを示す図である。
【図３５】演算部の第１の構成図である。
【図３６】演算部の第２の構成図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照しながら、実施形態を詳細に説明する。
図１は、エピポーラ幾何の例を示している。エピポーラ幾何は、２つの異なる視点の画像から３次元の奥行き情報を復元するための幾何である。２つのカメラのうち、基準カメラをＬカメラとし、参照カメラをＲカメラとする。Ｌカメラの投影中心ＯＬは、Ｌカメラの視点に対応し、Ｒカメラの投影中心ＯＲは、Ｒカメラの視点に対応する。投影中心ＯＲをＬカメラの投影面１０１上に投影した点ｅＬと、投影中心ＯＬをＲカメラの投影面１０２上に投影した点ｅＲは、エピポールと呼ばれる。
【００１５】
投影中心ＯＬと、３次元空間内の点Ｘを投影面１０１上に投影した点ＸＬとを通る直線１１１を、投影面１０２上に投影することで、エピポーラ線１１２が得られる。直線１１１上の点Ｘは、エピポーラ線１１２上の点ＸＲに投影され、直線１１１上の点Ｘ１〜点Ｘ３もエピポーラ線１１２上に投影される。投影面１０１上において、直線１１１は点ＸＬに投影される。
【００１６】
Ｌカメラ及びＲカメラのうち一方のカメラからは、他方のカメラを見ることができ、Ｒカメラの投影中心ＯＲはエピポールｅＬに投影され、Ｌカメラの投影中心ＯＬはエピポールｅＲに投影される。したがって、エピポールｅＬ及びエピポールｅＲは、３次元空間内において、投影中心ＯＬと投影中心ＯＲを通る直線１１３上に存在する。
【００１７】
エピポーラ線１１２は、３次元空間内における点Ｘの位置によって一意に定まり、３次元空間内の複数の点に対応するすべてのエピポーラ線は、エピポールｅＲを通る。言い換えれば、投影面１０２上においてエピポールｅＲを通るすべての直線は、エピポーラ線である。エピポーラ面１０３は、投影中心ＯＬ、投影中心ＯＲ、及び点Ｘを含む平面であり、エピポーラ面１０３と投影面１０２の交線は、エピポーラ線１１２に一致する。
【００１８】
ＬカメラとＲカメラの間の位置関係が既知である場合、以下のようなエピポーラ制約が成り立つ。
（１）点Ｘを投影面１０１上に投影した点ＸＬが与えられると、投影面１０２上のエピポーラ線１１２が定義される。
（２）点Ｘを投影面１０２上に投影した点ＸＲは、エピポーラ線１１２上のどこかに存在する。
【００１９】
したがって、Ｌカメラ及びＲカメラが同じ点Ｘを捕捉している場合、その点Ｘは必ず互いのエピポーラ線上に投影される。一方、点Ｘがエピポーラ線上に投影されていない場合は、同じ点Ｘを捕捉していないと言える。言い換えれば、エピポーラ線同士の対応付けが正しくない。一方のカメラから見ている点Ｘが他方のカメラの投影面上のどこに写っているかは、エピポーラ線上を調べれば十分である。対応づけが正しく、点ＸＬ及び点ＸＲの位置が分かっていれば、３次元空間内における点Ｘの位置を、三角法によって決定することができる。
【００２０】
VisualHullでは、３次元空間内の物体を投影面１０２上に投影した点が、エピポーラ線１１２上に存在するか否かを確認するために、線分探索が行われる。この場合、直線１１１上における物体の探索範囲が設定され、その探索範囲をエピポーラ線１１２上に投影することで、線分探索の探索範囲が決定される。直線１１１上における物体の探索範囲は、物理的に物体が存在する範囲であってもよく、それよりも狭い範囲であってもよい。
【００２１】
図２は、エピポーラ線１１２上における線分探索の探索範囲の例を示している。ｚＮｅａｒＲは、直線１１１上における物体の探索範囲のうち投影中心ＯＬに最も近い点を、投影面１０２上に投影した点である。また、ｚＦａｒＲは、物体の探索範囲のうち投影中心ＯＬから最も遠い点を、投影面１０２上に投影した点である。したがって、ｚＮｅａｒＲは、直線１１１上における物体の探索範囲を投影面１０２上に投影した点のうち、エピポールｅＲに最も近い点であり、ｚＦａｒＲは、物体の探索範囲を投影面１０２上に投影した点のうち、エピポールｅＲから最も遠い点である。
【００２２】
一方、投影面１０２上には、Ｒカメラの視野範囲に対応する画面が設定される。ＢＮｅａｒは、エピポーラ線１１２と投影面１０２上の画面端との２つの交点のうち、エピポールｅＲに近い方の点であり、ＢＦａｒは、それらの交点のうち、エピポールｅＲから遠い方の点である。
【００２３】
エピポーラ線１１２上における線分探索の探索範囲としては、例えば、Ｍａｘ（ｚＮｅａｒＲ，ＢＮｅａｒ）〜Ｍｉｎ（ｚＦａｒＲ，ＢＦａｒ）の範囲が設定される。Ｍａｘ（ｚＮｅａｒＲ，ＢＮｅａｒ）は、ｚＮｅａｒＲ及びＢＮｅａｒのうち、エピポールｅＲから遠い方の点であり、Ｍｉｎ（ｚＦａｒＲ，ＢＦａｒ）は、ｚＦａｒＲ及びＢＦａｒのうち、エピポールｅＲに近い方の点である。
【００２４】
図３は、物体の視体積（シルエットコーン）の例を示している。シルエット３０１及びシルエット３０２は、３次元空間内の２つの物体を投影面１０２上にそれぞれ投影した領域を表す。線分３１１は、シルエット３０１内に含まれるエピポーラ線１１２の一部であり、線分３１２は、シルエット３０２内に含まれるエピポーラ線１１２の一部である。投影中心ＯＲを基準として、線分３１１を３次元空間に投影することでシルエットコーン３２１が得られ、線分３１２を３次元空間に投影することでシルエットコーン３２２が得られる。
【００２５】
視体積交差法では、複数の参照カメラ（Ｒカメラ）それぞれから物体を見た複数のシルエットコーンを用いて、物体の３次元形状が生成される。そこで、各参照カメラが撮影した画像内で線分探索を行うことで、シルエットとエピポーラ線との重複範囲を表す線分が探索される。
【００２６】
探索された線分の２つの端点のうち、エピポールｅＲに近い方の端点は、基準カメラ（Ｌカメラ）から見た物体の表面の位置の候補であり、エピポールｅＲから遠い方の端点は、その物体の裏面の位置の候補である。各線分の２つの端点を図１の直線１１１上に投影した２つの点のうち、投影中心ＯＬに近い方の点が、投影中心ＯＬから見た物体表面の位置を表す。
【００２７】
図４は、多視点から見たシルエットコーンの例を示している。まず、複数の視点それぞれに対応する複数のカメラのうち、１台のカメラが基準カメラに指定され、それ以外のカメラは参照カメラに指定される。
【００２８】
次に、基準カメラの画面内のシルエットに含まれる各点（画素）について、複数の参照カメラそれぞれから物体４０１を見た複数のシルエットコーンを求めることで、その画素に対応する物体表面の位置が特定される。そして、各カメラを順番に基準カメラに指定することで、複数の視点から見た物体表面の位置が特定され、その物体の３次元形状を抽出することができる。
【００２９】
基準カメラの画面内の各画素に対応する物体表面の位置を特定する際、複数の参照カメラそれぞれの画面内で探索された複数の線分の間における、奥行き方向の重複判定が行われる。
【００３０】
図５は、複数の線分の間における重複判定処理の例を示している。この例では、Ｍ＋１台（Ｍは１以上の整数）の参照カメラが用いられ、参照画像ＲＧｉ（ｉ＝０〜Ｍ）は、ｉ番目の参照カメラによって撮影された画像を表す。ｚ軸は、基準カメラによって撮影された対象画像内の対象画素を通る奥行き方向の直線を表し、基準カメラの投影面と垂直に交わる。基準カメラの視点から離れるほど、ｚ座標の座標値は大きくなる。
【００３１】
線分５０１−ｉは、図１の直線１１１を参照画像ＲＧｉ上に投影したエピポーラ線上において探索された線分を、ｚ軸上に投影することで得られる線分である。ｚ軸上において、線分５０１−０〜線分５０１−Ｍが重複している範囲５０２が、３次元空間内の物体の存在範囲に決定される。ただし、物体が参照カメラの視野外に存在する場合、その参照カメラによって撮影された参照画像は、重複判定処理の対象から除外される。
【００３２】
図６は、参照画像ＲＧｉから生成されるマスク画像の例を示している。参照画像ＲＧｉ内から物体が写っている物体領域を抽出し、物体領域とそれ以外の背景領域とを区別する画素値を設定することで、マスク画像６０１−ｉが生成される。そして、参照画像ＲＧｉ内のエピポーラ線６０２−ｉ上で、マスク画像６０１−ｉに含まれる物体領域の境界とエピポーラ線６０２−ｉとの交点を探索することで、物体の存在範囲を表す線分の端点が求められる。
【００３３】
例えば、（ｘ１，ｙ１）及び（ｘ２，ｙ２）は、マスク画像６０１−０とエピポーラ線６０２−０から求められた線分の端点の座標である。（ｘ３，ｙ３）及び（ｘ４，ｙ４）は、マスク画像６０１−１とエピポーラ線６０２−１から求められた線分の端点の座標であり、（ｘ５，ｙ５）及び（ｘ６，ｙ６）は、マスク画像６０１−２とエピポーラ線６０２−２から求められた線分の端点の座標である。
【００３４】
図７は、参照画像ＲＧ０〜参照画像ＲＧ４から生成された５本の線分の間における重複判定処理の例を示している。これらの線分をｚ軸上に投影することで得られる５本の線分が重複している範囲７０１が、３次元空間内の物体の存在範囲に決定される。
【００３５】
図８は、VisualHullによって物体の３次元形状を求める３次元形状構築部の機能的構成例を示している。図８の３次元形状構築部８０１は、線分探索部８１１、重複判定部８１２、及び記憶部８１３を含む。
【００３６】
線分探索部８１１は、各参照画像から生成されたマスク画像と、各参照画像内のエピポーラ線を示すエピポーラ線情報とを用いて、エピポーラ線上の線分を探索する線分探索処理を行う。そして、線分探索部８１１は、探索した線分の端点の座標（線分端座標）を記憶部８１３に格納する。重複判定部８１２は、記憶部８１３から線分端座標を読み出して重複判定処理を行い、ｚ軸上における物体の存在範囲を求める。そして、重複判定部８１２は、求めた存在範囲のｚ座標を示す距離情報を出力する。
【００３７】
しかしながら、図８の３次元形状構築部８０１の構成では、重複判定処理の対象となる線分の本数が多い場合、線分端座標の格納及び読み出しの性能が劣化することがある。
【００３８】
図９は、図８の３次元形状構築部８０１のハードウェア構成例を示している。図９の３次元形状構築部８０１は、演算回路９０１、ローカルメモリ９０２、及びオフチップメモリ９０３を含む。演算回路９０１は、線分探索部８１１及び重複判定部８１２として動作し、線分探索処理及び重複判定処理を行う。
【００３９】
ローカルメモリ９０２及びオフチップメモリ９０３は、記憶部８１３として用いられ、線分端座標を記憶する。ローカルメモリ９０２は、シェアードメモリ又はキャッシュメモリのように、サイズが小さく、かつ、レイテンシが小さなメモリである。一方、オフチップメモリ９０３は、メインメモリのように、サイズが大きく、かつ、レイテンシが大きなメモリである。
【００４０】
線分探索処理によって探索された線分の本数が多く、ローカルメモリ９０２に線分端座標が格納しきれない場合、オフチップメモリ９０３にも線分端座標が格納される。この場合、オフチップメモリ９０３からローカルメモリ９０２へ線分端座標をロードするロード時間が長くなり、オフチップメモリ９０３に対する読み書きのオーバヘッドが大きくなる。
【００４１】
例えば、重複判定処理では、各参照画像内の線分端座標が、すべての参照画像に共通の３次元空間の座標系に変換される。そして、すべての線分の変換後のｚ座標に対してソート処理又は比較処理を行うことで、それらの線分の位置関係が確定され、線分間の重複が判定される。この場合、ワーク領域を利用した各処理ステップ間におけるデータ転送が多く発生するため、演算回路９０１は、高い頻度でローカルメモリ９０２にアクセスする。
【００４２】
そこで、オフチップメモリ９０３からデータを一度だけローカルメモリ９０２に読み込んでキャッシュしておき、高頻度なアクセスをローカルメモリ９０２内に閉じて行うことで、重複判定処理を効率化することができる。しかし、処理中のデータをローカルメモリ９０２に格納しきれない場合、オフチップメモリ９０３からデータを読み込むオーバヘッドが大きくなる。
【００４３】
さらに、演算回路９０１内で並列に動作する複数のスレッドからローカルメモリ９０２又はオフチップメモリ９０３へのアクセスによって、ボトルネックが発生することがある。
【００４４】
VisualHullの線分探索処理及び重複判定処理は、高い並列度で行うことが可能なため、線分探索処理の１つの演算ステップ（処理時間）と重複判定処理の１つの演算ステップは短い。
【００４５】
線分探索処理は、各参照画像のマスク画像に含まれるシルエット画素毎に独立して行うことができ、さらに、参照画像毎に独立して行うことができる。例えば、解像度５Ｋ（５１２０×３８４０）の２１台の参照カメラを用いて物体を撮影し、各参照画像の３０％がシルエットである場合、線分探索処理の最大並列度ＰＳは、次式により計算される。
【００４６】
ＰＳ＝５１２０×３８４０×０．３×２１＝１２３，８６３，０４０      （１）
【００４７】
しかし、実際には、各参照画像に対する線分探索処理は逐次的に行われ、演算回路９０１の同時並列数による制約が存在するため、アクティブな並列度は数千程度になる。
【００４８】
また、重複判定処理は、対象画像のマスク画像に含まれるシルエット画素毎に独立して行うことができる。例えば、解像度５Ｋの対象画像の３０％がシルエットである場合、重複判定処理の最大並列度ＰＤは、次式により計算される。
【００４９】
ＰＤ＝５１２０×３８４０×０．３＝５，８９８，２４０      （２）
【００５０】
しかし、実際には、演算回路９０１の同時並列数による制約が存在するため、アクティブな並列度は数千程度になる。
【００５１】
このように、線分探索処理又は重複判定処理では、演算回路９０１内で並列に動作する数千個のスレッドからローカルメモリ９０２又はオフチップメモリ９０３へのアクセスが発生する。このため、並列に動作するスレッドの個数に比例して、探索される線分の本数が増大するとともに、ハードウェアのメモリアクセス機構の性能限界によって、ボトルネックが発生する。
【００５２】
オフチップメモリ９０３に対する読み書きのオーバヘッドを削減し、メモリアクセスのボトルネックを抑制するためには、線分端座標のデータ量を削減すること、そして、線分端座標をできるだけローカルメモリ９０２内に収めることが有効である。
【００５３】
図１０は、実施形態の情報処理装置の機能的構成例を示している。図１０の情報処理装置１００１は、生成部１０１１、変換部１０１２、記憶部１０１３、復元部１０１４、及び判定部１０１５を含む。
【００５４】
図１１は、図１０の情報処理装置１００１が行う画像処理の例を示すフローチャートである。まず、生成部１０１１は、３次元空間内における撮像装置の投影中心と、その撮像装置の投影面内において物体を表す点とを通る第１直線を、複数の画像各々に写像した第２直線上において、物体の存在範囲を表す線分を生成する（ステップ１１０１）。複数の画像は、上記投影中心及び上記投影面を有する撮像装置以外の複数の撮像装置それぞれによって撮影された画像である。
【００５５】
変換部１０１２は、複数の画像それぞれから生成された複数の線分各々について、画像内における線分の一方の端点の座標を、一方の端点の座標と他方の端点の座標との差分に変換する（ステップ１１０２）。そして、記憶部１０１３は、他方の端点の座標と差分とを記憶する。
【００５６】
復元部１０１４は、記憶部が記憶する他方の端点の座標と差分とから、一方の端点の座標を復元する（ステップ１１０３）。判定部１０１５は、他方の端点の座標と復元部が復元した一方の端点の座標とを、上記投影面の奥行き方向に写像した結果に基づいて、複数の線分の間における奥行き方向の重複判定を行う（ステップ１１０４）。
【００５７】
図１０の情報処理装置１００１によれば、撮像装置によって撮影された画像内において物体の存在範囲を表す線分の座標データを削減することができる。
【００５８】
上記投影中心及び上記投影面を有する撮像装置は、基準カメラに対応し、複数の画像を撮影する複数の撮像装置は、複数の参照カメラに対応し、複数の画像は、複数の参照画像に対応する。
【００５９】
図１２は、従来の線分探索処理における線分端座標の例を示している。エピポーラ線１２０１上の線分１２０２の２つの端点と線分１２０３の２つの端点と含む、４個の端点のうち、ｎ番目（ｎ＝１〜４）の端点の座標は、（ｘｎ，ｙｎ）と記述される。ｘｎは、参照画像の水平方向の座標であり、ｙｎは、参照画像の垂直方向の座標である。ｘｎ及びｙｎは、それぞれ３２ビットの浮動小数点数型変数ｆｐ３２により表され、記憶部１２１１に格納される。したがって、４個の端点の線分端座標のデータ量は２５６ビットである。
【００６０】
一方、図１３は、実施形態の線分探索処理における線分端座標の例を示している。この例では、エピポーラ線１２０１上の各端点のｘ座標及びｙ座標のうち、ｘ座標のみが記憶部１０１３に格納され、重複判定処理を行う際に、エピポーラ線１２０１の方程式を用いて、記憶部１０１３に格納されたｘ座標からｙ座標が計算される。
【００６１】
さらに、ｘ１〜ｘ４のうち、ｘ１を除く残りのｘ座標は、エピポーラ線１２０１上で左下に存在する別の端点のｘ座標との差分ｄｎ（ｎ＝２〜４）に変換される。差分ｄｎは、次式により計算される。
【００６２】
ｄｎ＝ｘｎ−ｘ（ｎ−１）      （３）
【００６３】
ｘ１は、１６ビットの整数型変数ＩＮＴ１６により表され、ｄ２〜ｄ４は、８ビットの整数型変数ＩＮＴ８により表されて、記憶部１０１３に格納される。したがって、４個の端点の線分端座標のデータ量は４０ビットであり、図１２の線分端座標のデータ量よりも大幅に減少している。
【００６４】
このように、各端点のｘ座標及びｙ座標のうち、一方の座標のみを記憶部１０１３に格納することで、線分端座標のデータ量が半減する。また、線分端座標を、その線分端座標と他の端点の座標との差分に変換することで、線分端座標がより小さな値になり、線分端座標のデータ量がさらに圧縮される。これにより、線分端座標を記憶する記憶部１０１３の記憶領域が削減され、記憶部１０１３に対するメモリアクセスサイズも減少する。
【００６５】
図１４は、記憶部１０１３が記憶する線分端座標の選択方法の例を示している。参照画像内の点をｘｙ座標系で記述する場合、エピポーラ線の方程式は、次式のようになる。
【００６６】
ｙ＝ａ＊ｘ＋ｂ      （４）
【００６７】
式（４）のａは、エピポーラ線の傾きを表し、ｂは、エピポーラ線とｙ軸との交点のｙ座標を表す。
【００６８】
線分探索処理では、エピポーラ線上で探索点を移動させながら、シルエットを表す線分の端点が探索される。そこで、ｘ座標及びｙ座標のうち、例えば、エピポーラ線上の２つの端点の間における座標差分（移動量）が大きい方の座標を、記憶部１０１３に記憶させる座標（基準座標）として選択することができる。基準座標は、整数型変数を用いて記憶部１０１３に格納される。いずれの座標の移動量が大きいかは、エピポーラ線の傾きａの値から判定することができる。
【００６９】
基準座標をｃ座標（ｃ＝ｘ又はｙ）とすると、エピポーラ線上で探索されたｎ番目（ｎ＞１）の端点のｃ座標であるｃｎは、ｃｎとｎ−１番目の端点のｃ座標であるｃ（ｎ−１）との差分ｄｎに変換されて、記憶部１０１３に格納される。ただし、最初のｃ座標であるｃ１については、そのまま記憶部１０１３に格納される。
【００７０】
重複判定処理では、復元されたｃ（ｎ−１）と記憶部１０１３が記憶するｄｎとを用いて、ｃｎを復元することができ、式（４）を用いて、ｃ座標とは異なる他方の座標（ｙ又はｘ）を計算することができる。この場合、計算された他方の座標は、浮動小数点数型変数によって表される。
【００７１】
図１４（ａ）は、０＜ａ＜１である場合のエピポーラ線の例を示している。この場合、エピポーラ線１４０１の傾きａが０＜ａ＜１の範囲であるため、移動量が大きい方の座標はｘ座標となり、探索された各端点のｘ座標が座標差分に変換される。線分１４１１の端点１４２１のｘ座標がｘ（ｎ−１）であり、線分１４１２の端点１４２２のｘ座標がｘｎである場合、ｘｎは、式（３）により差分ｄｎに変換される。
【００７２】
図１４（ｂ）は、１＜ａである場合のエピポーラ線の例を示している。この場合、エピポーラ線１４０２の傾きａが１よりも大きいため、移動量が大きい方の座標はｙ座標となり、探索された各端点のｙ座標が座標差分に変換される。線分１４３１の端点１４４１のｙ座標がｙ（ｎ−１）であり、線分１４３２の端点１４４２のｙ座標がｙｎである場合、ｙｎは、次式により差分ｄｎに変換される。
【００７３】
ｄｎ＝ｙｎ−ｙ（ｎ−１）      （５）
【００７４】
エピポーラ線上の探索点を移動させる際の基準座標の刻み（インクリメント値）は、必ずしも１である必要はなく、所望の精度が満たされるように、１よりも小さな値に変更することが可能である。この場合、図５のｚ軸上における物体の存在範囲を表すｚ座標に対して所定の分解能を設定し、設定した分解能を所望の精度として用いることができる。
【００７５】
例えば、基準座標を１ずつインクリメントすることで分解能が満たされる場合、基準座標の整数値がそのまま記憶部１０１３に格納され、基準座標を０．５ずつインクリメントすることで分解能が満たされる場合、基準座標の整数値の２倍の整数値が、記憶部１０１３に格納される。また、基準座標を０．２５ずつインクリメントすることで分解能が満たされる場合、基準座標の整数値の４倍の整数値が、記憶部１０１３に格納される。
【００７６】
移動量が大きい方の座標を基準座標として選択し、基準座標を整数値として記憶部１０１３に格納することで、式（４）を用いて他方の座標を復元する際に、基準座標の移動量よりも細かい刻みの小数を用いて、他方の座標を表すことができる。したがって、基準座標のインクリメント値が所望の精度を満たしている場合、復元された他方の座標も所望の精度を満たすことが保証される。
【００７７】
ただし、移動量が小さい方の座標のインクリメント値を調整することで、他方の座標が所望の精度を満たす場合は、移動量が小さい方の座標を基準座標として選択しても構わない。
【００７８】
線分探索処理は、エピポーラ線上に探索開始点及び探索終了点を設定して、探索開始点から探索終了点まで探索点を所定刻みで移動させながら行われる。例えば、探索開始点は、探索終了点よりもエピポールに近い位置に設定される。
【００７９】
この場合、エピポーラ線上における探索点の移動方向が１方向に固定されているため、差分ｄｎの符号は一定である。そこで、差分ｄｎの絶対値を記憶部１０１３に格納しておき、基準座標を復元する際に、実際の端点の座標（ｘｎ，ｙｎ）の符号と整合するように、差分ｄｎの符号を決定することが可能である。
【００８０】
浮動小数点数は、基数部及び仮数部を含み、値によって小数点以下の精度が変化する。このため、基準座標が浮動小数点数である場合、２つの座標の差分を生成すると、小数点以下の表現可能な精度は上がるが、データ量を圧縮するという目的は必ずしも満たされない。つまり、小数点以下を切れるからといって、浮動小数点数型変数のフォーマットを変更できるわけではない。一方、基準座標が整数であれば、２つの座標の差分を生成することで値が小さくなり、整数型変数のビット幅を削減することができる。
【００８１】
最初の基準座標ｃ１及び基準座標の差分ｄｎの各々を表す整数型変数のビット幅は、基準座標ｃ１又は差分ｄｎの整数値に基づいて決定される。例えば、基準座標ｃ１又は差分ｄｎの整数値を格納可能な最小ビット幅を、整数型変数のビット幅として用いてもよい。このように、整数型変数に格納される整数値に基づいてビット幅を決定することで、記憶部１０１３の記憶領域を最小化することが可能になる。
【００８２】
例えば、エピポーラ線上で探索された複数の端点の基準座標が、ＩＮＴ１６又はＩＮＴ８のいずれかに格納される場合、各整数型変数がＩＮＴ１６又はＩＮＴ８のいずれであるかは、最初のビット（フォーマットビット）によって区別することができる。整数型変数がＩＮＴ１６である場合、最初のビットを“１”に設定し、整数型変数がＩＮＴ８である場合、最初のビットを“０”に設定してもよい。２つの端点が離れていて、差分ｄｎの絶対値が大きい場合は、ＩＮＴ１６が用いられ、２つの端点が近接していて、差分ｄｎの絶対値が小さい場合は、ＩＮＴ８が用いられる。
【００８３】
図１５は、差分ｄｎの符号の決定方法の例を示している。差分ｄｎの符号は、探索開始点と探索終了点の位置関係から決定することができる。探索開始点から探索終了点へ向かう探索点の移動方向が座標値が大きくなる方向（正方向）である場合、符号は“＋”になり、探索点の移動方向が座標値が小さくなる方向（負方向）である場合、符号は“−”になる。
【００８４】
重複判定処理では、記憶部１０１３から読み出したｄｎの絶対値に、図１５の方法で決定した符号を付加して、ｄｎを復元し、復元されたｃ（ｎ−１）にｄｎを加算することで、ｃｎを復元することができる。
【００８５】
図１６は、参照画像ＲＧ０〜参照画像ＲＧ４の各々から複数の線分が探索された場合の重複判定処理の例を示している。ｚ軸上で矢印１６０１の向きに物体の表面を探索し、ｚ軸上の位置１６０２において、参照画像ＲＧ０〜参照画像ＲＧ４の間で重複している線分の本数が閾値以上になれば、重複判定処理を打ち切ることができる。この場合、破線で囲まれた範囲１６０３内の線分の端点のｚ座標は不要になる。
【００８６】
基準座標の差分ｄｎを生成する差分演算の演算量は、座標変換の演算量よりも小さいため、差分ｄｎを記憶部１０１３に格納する場合の方が、ｚ座標を記憶部１０１３に格納する場合よりも、演算効率が高くなる。
【００８７】
図１７は、図１０の情報処理装置１００１の具体例を示している。図１７の情報処理装置１００１は、変換部１０１２、記憶部１０１３、復元部１０１４、判定部１０１５、写像情報生成部１７０１、及び線分探索部１７０２を含み、多視点映像から物体の３次元形状を復元するVisualHull処理を行う。写像情報生成部１７０１及び線分探索部１７０２は、図１の生成部１０１１に対応する。
【００８８】
図１７の情報処理装置１００１が行うVisualHull処理では、以下のようなパラメータが用いられる。
【００８９】
ＲＩＤ：参照カメラによって撮影された参照画像を識別する識別情報
Ｉｄｘ：参照画像内のエピポーラ線を識別する識別情報
ｎ：エピポーラ線上で探索された線分の端点を識別する識別情報
参照画像のマスク画像［ＲＩＤ］：ＲＩＤが示す参照画像から生成されたマスク画像
対象画像のマスク画像：基準カメラによって撮影された対象画像から生成されたマスク画像
カメラ光学情報［ＲＩＤ］：ＲＩＤが示す参照画像を撮影した参照カメラの光学情報
カメラ光学情報（対象画像）：基準カメラの光学情報
カメラ位置情報［ＲＩＤ］：ＲＩＤが示す参照画像を撮影した参照カメラの位置情報
カメラ位置情報（対象画像）：基準カメラの位置情報
写像情報Ｍ１［ＲＩＤ］：３次元空間内の点を、ＲＩＤが示す参照画像上に写像する座標変換の変換行列
写像情報Ｍ２［ＲＩＤ］：ＲＩＤが示す参照画像内の点を、対象画像の奥行き方向の直線（ｚ軸）上に写像する座標変換の変換行列
エピポーラ線情報［ＲＩＤ］［Ｉｄｘ］：ＲＩＤが示す参照画像内における、Ｉｄｘが示すエピポーラ線の方程式を表すパラメータ（ａ，ｂ）
ｃ［ＲＩＤ］［Ｉｄｘ］［ｎ］：ＲＩＤが示す参照画像内において、Ｉｄｘが示すエピポーラ線上で探索されたｎ番目の端点の基準座標（ｃはＸ又はＹ）
ｄ［ＲＩＤ］［Ｉｄｘ］［ｎ］：ＲＩＤが示す参照画像内において、Ｉｄｘが示すエピポーラ線上で探索されたｎ番目の端点の基準座標、又はその端点の基準座標の差分の絶対値を表す整数値
ｆｍｔ［ＲＩＤ］［Ｉｄｘ］［ｎ］：ＲＩＤが示す参照画像内において、Ｉｄｘが示すエピポーラ線上で探索されたｎ番目の端点の整数型変数のビット幅を示すフォーマットビットのビット値
記憶領域［ＲＩＤ］［Ｉｄｘ］：ＲＩＤが示す参照画像内において、Ｉｄｘが示すエピポーラ線上で探索された端点の整数値及びフォーマットビットを記憶する記憶領域
ｚ［ＲＩＤ］［Ｉｄｘ］［ｎ］：ＲＩＤが示す参照画像内において、Ｉｄｘが示すエピポーラ線上で探索されたｎ番目の端点を、対象画像のｚ軸上に写像することで得られるｚ座標
距離情報ｚ：重複判定処理によって決定された物体の表面又は裏面のｚ座標
【００９０】
なお、Ｉｄｘは、参照画像内のエピポーラ線を識別する識別情報として用いられるとともに、対象画像のマスク画像内の物体領域の画素を識別する識別情報としても用いられる。
【００９１】
写像情報生成部１７０１は、カメラ光学情報［ＲＩＤ］、カメラ光学情報（対象画像）、カメラ位置情報［ＲＩＤ］、及びカメラ位置情報（対象画像）を用いて、写像情報Ｍ１［ＲＩＤ］及び写像情報Ｍ２［ＲＩＤ］を生成する。
【００９２】
線分探索部１７０２は、参照画像のマスク画像［ＲＩＤ］、対象画像のマスク画像、及び写像情報Ｍ１［ＲＩＤ］を用いて、エピポーラ線情報［ＲＩＤ］［Ｉｄｘ］を生成し、線分探索処理を行って、ｃ［ＲＩＤ］［Ｉｄｘ］［ｎ］を求める。
【００９３】
変換部１０１２は、ｃ［ＲＩＤ］［Ｉｄｘ］［ｎ］をｄ［ＲＩＤ］［Ｉｄｘ］［ｎ］及びｆｍｔ［ＲＩＤ］［Ｉｄｘ］［ｎ］に変換して、記憶部１０１３の記憶領域［ＲＩＤ］［Ｉｄｘ］に格納する。このとき、変換部１０１２は、ｄ［ＲＩＤ］［Ｉｄｘ］［ｎ］の値に基づいて、ｄ［ＲＩＤ］［Ｉｄｘ］［ｎ］を格納する整数型変数のビット幅を決定する。例えば、ｄ［ＲＩＤ］［Ｉｄｘ］［ｎ］を格納可能な最小ビット幅が、整数型変数のビット幅に決定される。
【００９４】
復元部１０１４は、記憶部１０１３の記憶領域［ＲＩＤ］［Ｉｄｘ］からｆｍｔ［ＲＩＤ］［Ｉｄｘ］［ｎ］を読み出し、ｆｍｔ［ＲＩＤ］［Ｉｄｘ］［ｎ］が示すビット幅のｄ［ＲＩＤ］［Ｉｄｘ］［ｎ］を読み出す。そして、復元部１０１４は、ｄ［ＲＩＤ］［Ｉｄｘ］［ｎ］からｃ［ＲＩＤ］［Ｉｄｘ］［ｎ］を復元し、エピポーラ線情報［ＲＩＤ］［Ｉｄｘ］及び写像情報Ｍ２［ＲＩＤ］を用いて、ｃ［ＲＩＤ］［Ｉｄｘ］［ｎ］からｚ［ＲＩＤ］［Ｉｄｘ］［ｎ］を求める。
【００９５】
判定部１０１５は、ｚ［ＲＩＤ］［Ｉｄｘ］［ｎ］を用いて重複判定処理を行い、距離情報ｚを出力する。
【００９６】
図１８は、図１７の情報処理装置１００１が行うVisualHull処理の例を示すフローチャートである。このVisualHull処理は、１時刻における多視点画像に対して行われ、多視点映像の場合は、各時刻の多視点画像に対して図１８のVisualHull処理が繰り返される。（ｘ，ｙ）は、対象画像のマスク画像内における処理対象画素（マスク画素）の座標を表す。
【００９７】
まず、線分探索部１７０２は、ｙ及びＩｄｘに初期値０を設定し（ステップ１８０１）、ｘに初期値０を設定する（ステップ１８０２）。そして、線分探索部１７０２は、対象画像のマスク画像からマスク画素（ｘ，ｙ））の画素値を取得し（ステップ１８０３）、マスク画素（ｘ，ｙ）の画素値が、物体領域を表す画素値ＦＧであるか否かをチェックする（ステップ１８０４）。
【００９８】
マスク画素（ｘ，ｙ）の画素値がＦＧではない場合（ステップ１８０４，ＮＯ）、線分探索部１７０２は、ｘを１だけインクリメントして（ステップ１８１１）、ｘと対象画像の幅とを比較する（ステップ１８１２）。ｘが対象画像の幅よりも小さい場合（ステップ１８１２，ＹＥＳ）、線分探索部１７０２は、ステップ１８０３以降の処理を繰り返す。
【００９９】
一方、マスク画素（ｘ，ｙ）の画素値がＦＧである場合（ステップ１８０４，ＹＥＳ）、線分探索部１７０２は、ＲＩＤに初期値０を設定する（ステップ１８０５）。そして、線分探索部１７０２は、写像情報Ｍ１［ＲＩＤ］を用いて、基準カメラの視点とマスク画素（ｘ，ｙ）とを通る直線を、参照画像のマスク画像［ＲＩＤ］上に写像することで、エピポーラ線情報［ＲＩＤ］［Ｉｄｘ］を生成する（ステップ１８０６）。
【０１００】
次に、線分探索部１７０２は、エピポーラ線情報［ＲＩＤ］［Ｉｄｘ］が示すエピポーラ線上で線分探索処理を行う（ステップ１８０７）。そして、線分探索部１７０２は、ＲＩＤを１だけインクリメントして（ステップ１８０８）、ＲＩＤと参照画像の個数とを比較する（ステップ１８０９）。ＲＩＤが参照画像の個数よりも小さい場合（ステップ１８０９，ＹＥＳ）、線分探索部１７０２は、ステップ１８０６以降の処理を繰り返す。
【０１０１】
そして、ＲＩＤが参照画像の個数に達した場合（ステップ１８０９，ＮＯ）、線分探索部１７０２は、Ｉｄｘを１だけインクリメントして（ステップ１８１０）、ステップ１８１１以降の処理を行う。
【０１０２】
ｘが対象画像の幅に達した場合（ステップ１８１２，ＮＯ）、線分探索部１７０２は、ｙを１だけインクリメントして（ステップ１８１３）、ｘと対象画像の高さとを比較する（ステップ１８１４）。ｙが対象画像の高さよりも小さい場合（ステップ１８１４，ＹＥＳ）、線分探索部１７０２は、ステップ１８０２以降の処理を繰り返す。
【０１０３】
ｙが対象画像の高さに達した場合（ステップ１８１４，ＮＯ）、判定部１０１５は、対象画像のマスク画像内の物体領域の画素数を表す変数ＮＦＧに、Ｉｄｘを設定する（ステップ１８１５）。そして、判定部１０１５は、Ｉｄｘに初期値０を設定し（ステップ１８１６）、対象画像のマスク画像内のＩｄｘが示す物体領域の画素に対する重複判定処理を行う（ステップ１８１７）。
【０１０４】
次に、判定部１０１５は、Ｉｄｘを１だけインクリメントして（ステップ１８１８）、ＩｄｘとＮＦＧとを比較する（ステップ１８１９）。ＩｄｘがＮＦＧよりも小さい場合（ステップ１８１９，ＹＥＳ）、判定部１０１５は、ステップ１８１７以降の処理を繰り返す。そして、ＩｄｘがＮＦＧに達した場合（ステップ１８１９，ＮＯ）、判定部１０１５は、処理を終了する。
【０１０５】
図１９は、図１８のステップ１８０６におけるエピポーラ線情報生成処理とステップ１８０７における線分探索処理の例を示すフローチャートである。図１９の処理では、以下のようなパラメータが用いられる。
【０１０６】
探索開始点［ＲＩＤ］［Ｉｄｘ］：ＲＩＤが示す参照画像内における、Ｉｄｘが示すエピポーラ線上における探索開始点
探索終了点［ＲＩＤ］［Ｉｄｘ］：ＲＩＤが示す参照画像内における、Ｉｄｘが示すエピポーラ線上における探索終了点
（Ｘ，Ｙ）：参照画像のマスク画像［ＲＩＤ］内における画素の座標
【０１０７】
まず、線分探索部１７０２は、写像情報Ｍ１［ＲＩＤ］を用いて、基準カメラの視点、マスク画素（ｘ，ｙ）、及び以下の点Ｐ１〜点Ｐ４を、参照画像のマスク画像［ＲＩＤ］上に写像する（ステップ１９０１）。
【０１０８】
ｚＮｅａｒ：基準カメラの視点とマスク画素（ｘ，ｙ）とを通る直線Ｌ上において、物理的に物体が存在する範囲のうち、基準カメラの視点に最も近い点
ｚＦａｒ：直線Ｌ上において物理的に物体が存在する範囲のうち、基準カメラの視点から最も遠い点
Ｎｅａｒ：直線Ｌ上において、VisualHull処理の目的に応じてユーザにより設定される探索開始点
Ｆａｒ：直線Ｌ上において、VisualHull処理の目的に応じてユーザにより設定される探索終了点
【０１０９】
これらの４つの点を、直線Ｌ上で基準カメラの視点に近い方から順に並べると、ｚＮｅａｒ、Ｎｅａｒ、Ｆａｒ、及びｚＦａｒのようになる。これらの点は、下記の通り、参照画像のマスク画像［ＲＩＤ］内のｚＮｅａｒＲ、ｚＦａｒＲ、ＮｅａｒＲ、及びＦａｒＲに写像される。
【０１１０】
ｚＮｅａｒ→ｚＮｅａｒＲ
ｚＦａｒ→ｚＦａｒＲ
Ｎｅａｒ→ＮｅａｒＲ
Ｆａｒ→ＦａｒＲ
【０１１１】
また、基準カメラの視点及びマスク画素（ｘ，ｙ）は、参照画像のマスク画像［ＲＩＤ］内の点Ｐ１及び点Ｐ２にそれぞれ写像される。このうち、点Ｐ１は、エピポールである。
【０１１２】
次に、線分探索部１７０２は、参照画像のマスク画像［ＲＩＤ］内の点Ｐ１と点Ｐ２を通るエピポーラ線の方程式Ｙ＝ａ＊Ｘ＋ｂを求める（ステップ１９０２）。そして、線分探索部１７０２は、求めた方程式を示すパラメータ（ａ，ｂ）を含むエピポーラ線情報［ＲＩＤ］［Ｉｄｘ］を生成する（ステップ１９０３）。
【０１１３】
次に、線分探索部１７０２は、Ｍａｘ（ｚＮｅａｒＲ，ＮｅａｒＲ）を、探索開始点［ＲＩＤ］［Ｉｄｘ］に設定する（ステップ１９０４）。Ｍａｘ（Ｐ，Ｑ）は、点Ｐ及び点Ｑのうち、エピポールＰ１から遠い方の点を表す。
【０１１４】
次に、線分探索部１７０２は、Ｍｉｎ（ｚＦａｒＲ，ＦａｒＲ）を、探索終了点［ＲＩＤ］［Ｉｄｘ］に設定する（ステップ１９０５）。Ｍｉｎ（Ｐ，Ｑ）は、点Ｐ及び点Ｑのうち、エピポールＰ１に近い方の点を表す。
【０１１５】
次に、線分探索部１７０２は、Ｍａｘ（探索開始点［ＲＩＤ］［Ｉｄｘ］，ＢＮｅａｒ）を、探索開始点［ＲＩＤ］［Ｉｄｘ］に設定する（ステップ１９０６）。ＢＮｅａｒは、エピポーラ線と参照画像のマスク画像［ＲＩＤ］の画面端との２つの交点のうち、エピポールＰ１に近い方の点である。
【０１１６】
次に、線分探索部１７０２は、Ｍｉｎ（探索終了点［ＲＩＤ］［Ｉｄｘ］，ＢＦａｒ）を、探索終了点［ＲＩＤ］［Ｉｄｘ］に設定する（ステップ１９０７）。ＢＦａｒは、エピポーラ線と参照画像のマスク画像［ＲＩＤ］の画面端との２つの交点のうち、エピポールＰ１から遠い方の点である。
【０１１７】
次に、線分探索部１７０２は、エピポーラ線の傾きａをチェックする（ステップ１９０８）。−１＜ａ＜１である場合（ステップ１９０８，ＹＥＳ）、線分探索部１７０２は、変数Ｓｔａｒｔに探索開始点［ＲＩＤ］［Ｉｄｘ］のＸ座標を設定する（ステップ１９０９）。そして、線分探索部１７０２は、変数Ｅｎｄに探索終了点［ＲＩＤ］［Ｉｄｘ］のＸ座標を設定する（ステップ１９１０）。
【０１１８】
次に、線分探索部１７０２は、変数Ｐｏｓ、変数ＦｉｒｓｔＦ、変数ＥｘＣｏｕｎｔ、変数Ｉｎｃ、及び変数ＧＳに、以下のような値をそれぞれ設定する（ステップ１９１１）。
【０１１９】
Ｐｏｓ＝Ｓｔａｒｔ
ＦｉｒｓｔＦ＝１
ＥｘＣｏｕｎｔ＝０
Ｉｎｃ＝基準座標のインクリメント値
ＧＳ＝１／Ｉｎｃ
【０１２０】
そして、線分探索部１７０２は、基準座標をＸ座標とする端点探索処理を行う（ステップ１９１２）。
【０１２１】
一方、ａ≦−１又は１≦ａである場合（ステップ１９０８，ＮＯ）、線分探索部１７０２は、変数Ｓｔａｒｔに探索開始点［ＲＩＤ］［Ｉｄｘ］のＹ座標を設定する（ステップ１９１３）。そして、線分探索部１７０２は、変数Ｅｎｄに探索終了点［ＲＩＤ］［Ｉｄｘ］のＹ座標を設定する（ステップ１９１４）。
【０１２２】
次に、線分探索部１７０２は、変数Ｐｏｓ、変数ＦｉｒｓｔＦ、変数ＥｘＣｏｕｎｔ、変数Ｉｎｃ、及び変数ＧＳに、ステップ１９１１と同様の値をそれぞれ設定する（ステップ１９１５）。そして、線分探索部１７０２は、基準座標をＹ座標とする端点探索処理を行う（ステップ１９１６）。
【０１２３】
図２０は、図１９のステップ１９１２における端点探索処理の例を示すフローチャートである。まず、線分探索部１７０２は、参照画像のマスク画像［ＲＩＤ］からマスク画素（Ｘ，Ｙ）＝（Ｐｏｓ，ａ＊Ｐｏｓ＋ｂ）を取得する（ステップ２００１）。そして、線分探索部１７０２は、取得したマスク画素（Ｘ，Ｙ）の画素値が、物体領域を表す画素値ＦＧであるか否かをチェックする（ステップ２００２）。
【０１２４】
マスク画素（Ｘ，Ｙ）の画素値がＦＧではない場合（ステップ２００２，ＮＯ）、線分探索部１７０２は、ＥｘＣｏｕｎｔと０とを比較する（ステップ２０１１）。ＥｘＣｏｕｎｔが０である場合（ステップ２０１１，ＮＯ）、線分探索部１７０２は、Ｐｏｓ＋ＩｎｃをＰｏｓに設定して（ステップ２０１６）、ＰｏｓとＥｎｄとを比較する（ステップ２０１７）。Ｐｏｓ＜Ｅｎｄである場合（ステップ２０１７，ＹＥＳ）、線分探索部１７０２は、ステップ２００１以降の処理を繰り返す。
【０１２５】
マスク画素（Ｘ，Ｙ）の画素値がＦＧである場合（ステップ２００２，ＹＥＳ）、線分探索部１７０２は、ＦｉｒｓｔＦと１とを比較する（ステップ２００３）。ＦｉｒｓｔＦが１である場合（ステップ２００３，ＹＥＳ）、線分探索部１７０２は、マスク画素（Ｘ，Ｙ）のＸ座標を変換部１０１２へ出力する（ステップ２００４）。そして、変換部１０１２は、Ｘ座標にＧＳを乗算することで、そのＸ座標を整数値化し、得られた整数値ｄを格納可能な最小ビット幅の整数型変数を用いて、整数値ｄとフォーマットビットとを、記憶部１０１３の記憶領域［ＲＩＤ］［Ｉｄｘ］に格納する。
【０１２６】
ステップ２００４において記憶部１０１３に格納される整数値ｄは、エピポーラ線上で最初に見つかった線分の２つの端点のうち、探索開始点に近い方の端点のＸ座標に対応する。
【０１２７】
次に、線分探索部１７０２は、ＦｉｒｓｔＦに０を設定し、ＥｘＣｏｕｎｔを１だけインクリメントし、変数ＬＸにマスク画素（Ｘ，Ｙ）のＸ座標を設定して（ステップ２００５）、ステップ２０１６以降の処理を行う。
【０１２８】
ＦｉｒｓｔＦが０である場合（ステップ２００３，ＮＯ）、線分探索部１７０２は、ＥｘＣｏｕｎｔと０とを比較する（ステップ２００６）。ＥｘＣｏｕｎｔ＞０である場合（ステップ２００６，ＹＥＳ）、線分探索部１７０２は、ＥｘＣｏｕｎｔを１だけインクリメントして（ステップ２００７）、ステップ２０１６以降の処理を行う。
【０１２９】
一方、ＥｘＣｏｕｎｔが０である場合（ステップ２００６，ＮＯ）、線分探索部１７０２は、マスク画素（Ｘ，Ｙ）のＸ座標を変換部１０１２へ出力する（ステップ２００８）。そして、変換部１０１２は、次式により、Ｘ座標を整数値の差分ｄＸに変換する。
【０１３０】
ｄＸ＝｜Ｘ−ＬＸ｜＊ＧＳ      （１１）
【０１３１】
変換部１０１２は、整数値ｄ＝ｄＸを格納可能な最小ビット幅の整数型変数を用いて、整数値ｄとフォーマットビットとを、記憶部１０１３の記憶領域［ＲＩＤ］［Ｉｄｘ］に格納する（ステップ２００９）。
【０１３２】
ステップ２００９において記憶部１０１３に格納される整数値ｄは、エピポーラ線上で２番目以降に見つかった線分の２つの端点のうち、探索開始点に近い方の端点のＸ座標に対応する。
【０１３３】
次に、線分探索部１７０２は、ＥｘＣｏｕｎｔを１だけインクリメントし、ＬＸにマスク画素（Ｘ，Ｙ）のＸ座標を設定して（ステップ２０１０）、ステップ２０１６以降の処理を行う。
【０１３４】
ステップ２０１１において、ＥｘＣｏｕｎｔ＞０である場合（ステップ２０１１，ＹＥＳ）、線分探索部１７０２は、変数ｔｍｐＸにＰｏｓ−Ｉｎｃを設定し（ステップ２０１２）、ｔｍｐＸを変換部１０１２へ出力する（ステップ２０１３）。そして、変換部１０１２は、次式により、ｔｍｐＸを整数値の差分ｄＸに変換する。
【０１３５】
ｄＸ＝｜ｔｍｐＸ−ＬＸ｜＊ＧＳ      （１２）
【０１３６】
変換部１０１２は、整数値ｄ＝ｄＸを格納可能な最小ビット幅の整数型変数を用いて、整数値ｄとフォーマットビットとを、記憶部１０１３の記憶領域［ＲＩＤ］［Ｉｄｘ］に格納する（ステップ２０１４）。
【０１３７】
ステップ２０１４において記憶部１０１３に格納される整数値ｄは、エピポーラ線上で見つかった線分の２つの端点のうち、探索終了点に近い方の端点のＸ座標に対応する。
【０１３８】
次に、線分探索部１７０２は、ＥｘＣｏｕｎｔに０を設定し、ＬＸにｔｍｐＸを設定して（ステップ２０１５）、ステップ２０１６以降の処理を行う。
図２１は、図１９のステップ１９１６における端点探索処理の例を示すフローチャートである。まず、線分探索部１７０２は、参照画像のマスク画像［ＲＩＤ］からマスク画素（Ｘ，Ｙ）＝（Ｐｏｓ／ａ−ｂ／ａ，Ｐｏｓ）を取得する（ステップ２１０１）。そして、線分探索部１７０２は、取得したマスク画素（Ｘ，Ｙ）の画素値が、物体領域を表す画素値ＦＧであるか否かをチェックする（ステップ２１０２）。
【０１３９】
マスク画素（Ｘ，Ｙ）の画素値がＦＧではない場合（ステップ２１０２，ＮＯ）、線分探索部１７０２は、ＥｘＣｏｕｎｔと０とを比較する（ステップ２１１１）。ＥｘＣｏｕｎｔが０である場合（ステップ２１１１，ＮＯ）、線分探索部１７０２は、Ｐｏｓ＋ＩｎｃをＰｏｓに設定して（ステップ２１１６）、ＰｏｓとＥｎｄとを比較する（ステップ２１１７）。Ｐｏｓ＜Ｅｎｄである場合（ステップ２１１７，ＹＥＳ）、線分探索部１７０２は、ステップ２１０１以降の処理を繰り返す。
【０１４０】
マスク画素（Ｘ，Ｙ）の画素値がＦＧである場合（ステップ２１０２，ＹＥＳ）、線分探索部１７０２は、ＦｉｒｓｔＦと１とを比較する（ステップ２１０３）。ＦｉｒｓｔＦが１である場合（ステップ２１０３，ＹＥＳ）、線分探索部１７０２は、マスク画素（Ｘ，Ｙ）のＹ座標を変換部１０１２へ出力する（ステップ２１０４）。そして、変換部１０１２は、Ｙ座標にＧＳを乗算することで、そのＹ座標を整数値化し、得られた整数値ｄを格納可能な最小ビット幅の整数型変数を用いて、整数値ｄとフォーマットビットとを、記憶部１０１３の記憶領域［ＲＩＤ］［Ｉｄｘ］に格納する。
【０１４１】
ステップ２１０４において記憶部１０１３に格納される整数値ｄは、エピポーラ線上で最初に見つかった線分の２つの端点のうち、探索開始点に近い方の端点のＹ座標に対応する。
【０１４２】
次に、線分探索部１７０２は、ＦｉｒｓｔＦに０を設定し、ＥｘＣｏｕｎｔを１だけインクリメントし、変数ＬＹにマスク画素（Ｘ，Ｙ）のＹ座標を設定して（ステップ２１０５）、ステップ２１１６以降の処理を行う。
【０１４３】
ＦｉｒｓｔＦが０である場合（ステップ２１０３，ＮＯ）、線分探索部１７０２は、ＥｘＣｏｕｎｔと０とを比較する（ステップ２１０６）。ＥｘＣｏｕｎｔ＞０である場合（ステップ２１０６，ＹＥＳ）、線分探索部１７０２は、ＥｘＣｏｕｎｔを１だけインクリメントして（ステップ２１０７）、ステップ２１１６以降の処理を行う。
【０１４４】
一方、ＥｘＣｏｕｎｔが０である場合（ステップ２１０６，ＮＯ）、線分探索部１７０２は、マスク画素（Ｘ，Ｙ）のＹ座標を変換部１０１２へ出力する（ステップ２１０８）。そして、変換部１０１２は、次式により、Ｙ座標を整数値の差分ｄＹに変換する。
【０１４５】
ｄＹ＝｜Ｙ−ＬＹ｜＊ＧＳ      （１３）
【０１４６】
変換部１０１２は、整数値ｄ＝ｄＹを格納可能な最小ビット幅の整数型変数を用いて、整数値ｄとフォーマットビットとを、記憶部１０１３の記憶領域［ＲＩＤ］［Ｉｄｘ］に格納する（ステップ２１０９）。
【０１４７】
ステップ２１０９において記憶部１０１３に格納される整数値ｄは、エピポーラ線上で２番目以降に見つかった線分の２つの端点のうち、探索開始点に近い方の端点のＹ座標に対応する。
【０１４８】
次に、線分探索部１７０２は、ＥｘＣｏｕｎｔを１だけインクリメントし、ＬＹにマスク画素（Ｘ，Ｙ）のＹ座標を設定して（ステップ２１１０）、ステップ２１１６以降の処理を行う。
【０１４９】
ステップ２１１１において、ＥｘＣｏｕｎｔ＞０である場合（ステップ２１１１，ＹＥＳ）、線分探索部１７０２は、変数ｔｍｐＹにＰｏｓ−Ｉｎｃを設定し（ステップ２１１２）、ｔｍｐＹを変換部１０１２へ出力する（ステップ２１１３）。そして、変換部１０１２は、次式により、ｔｍｐＹを整数値の差分ｄＹに変換する。
【０１５０】
ｄＹ＝｜ｔｍｐＹ−ＬＹ｜＊ＧＳ      （１４）
変換部１０１２は、整数値ｄ＝ｄＹを格納可能な最小ビット幅の整数型変数を用いて、整数値ｄとフォーマットビットとを、記憶部１０１３の記憶領域［ＲＩＤ］［Ｉｄｘ］に格納する（ステップ２１１４）。
【０１５１】
ステップ２１１４において記憶部１０１３に格納される整数値ｄは、エピポーラ線上で見つかった線分の２つの端点のうち、探索終了点に近い方の端点のＹ座標に対応する。
【０１５２】
次に、線分探索部１７０２は、ＥｘＣｏｕｎｔに０を設定し、ＬＹにｔｍｐＹを設定して（ステップ２１１５）、ステップ２１１６以降の処理を行う。
【０１５３】
図２２は、図１８のステップ１８１７における重複判定処理の例を示すフローチャートである。この重複判定処理では、以下のようなパラメータが用いられる。
【０１５４】
基準座標［ＲＩＤ］［Ｉｄｘ］：ＲＩＤが示す参照画像内における、Ｉｄｘが示すエピポーラ線上の基準座標
符号［ＲＩＤ］［Ｉｄｘ］：ＲＩＤが示す参照画像内における、Ｉｄｘが示すエピポーラ線上の基準座標の差分の符号
まず、復元部１０１４は、ＲＩＤに０を設定し（ステップ２２０１）、エピポーラ線情報［ＲＩＤ］［Ｉｄｘ］から（ａ，ｂ）を取得する（ステップ２２０２）。そして、復元部１０１４は、傾きａと−１とを比較し、傾きａと１とを比較する（ステップ２２０３）。
【０１５５】
−１＜ａ＜１である場合（ステップ２２０３，ＹＥＳ）、復元部１０１４は、基準座標［ＲＩＤ］［Ｉｄｘ］をＸ座標に決定し（ステップ２２０４）、ｚＮｅａｒＲのＸ座標とｚＦａｒＲのＸ座標とを比較する（ステップ２２０５）。
【０１５６】
ｚＮｅａｒＲのＸ座標＜ｚＦａｒＲのＸ座標である場合（ステップ２２０５，ＹＥＳ）、復元部１０１４は、符号［ＲＩＤ］［Ｉｄｘ］に１を設定する（ステップ２２０６）。
【０１５７】
一方、ｚＮｅａｒＲのＸ座標≧ｚＦａｒＲのＸ座標である場合（ステップ２２０５，ＮＯ）、復元部１０１４は、符号［ＲＩＤ］［Ｉｄｘ］に−１を設定する（ステップ２２０７）。
【０１５８】
ａ≦−１又は１≦ａである場合（ステップ２２０３，ＮＯ）、復元部１０１４は、基準座標［ＲＩＤ］［Ｉｄｘ］をＹ座標に決定し（ステップ２２０８）、ｚＮｅａｒＲのＹ座標とｚＦａｒＲのＹ座標とを比較する（ステップ２２０９）。
【０１５９】
ｚＮｅａｒＲのＹ座標＜ｚＦａｒＲのＹ座標である場合（ステップ２２０９，ＹＥＳ）、復元部１０１４は、符号［ＲＩＤ］［Ｉｄｘ］に１を設定する（ステップ２２１０）。一方、ｚＮｅａｒＲのＹ座標≧ｚＦａｒＲのＹ座標である場合（ステップ２２０９，ＮＯ）、復元部１０１４は、符号［ＲＩＤ］［Ｉｄｘ］に−１を設定する（ステップ２２１１）。
【０１６０】
次に、復元部１０１４は、ＲＩＤと参照画像の個数とを比較する（ステップ２２１２）。ＲＩＤが参照画像の個数よりも小さい場合（ステップ２２１２，ＹＥＳ）、復元部１０１４は、ステップ２２０２以降の処理を繰り返す。そして、ＲＩＤが参照画像の個数に達した場合（ステップ２２１２，ＮＯ）、復元部１０１４及び判定部１０１５は、重複判定コア処理を行う（ステップ２２１３）。
【０１６１】
図２３Ａ及び図２３Ｂは、図２２のステップ２２１３における重複判定コア処理の例を示すフローチャートである。この重複判定コア処理では、以下のようなパラメータが用いられる。
【０１６２】
Ｘ［ＲＩＤ］［Ｉｄｘ］：ＲＩＤが示す参照画像内における、Ｉｄｘが示すエピポーラ線上の線分の端点のＸ座標
Ｙ［ＲＩＤ］［Ｉｄｘ］：ＲＩＤが示す参照画像内における、Ｉｄｘが示すエピポーラ線上の線分の端点のＹ座標
まず、判定部１０１５は、ＲＩＤ、変数ＦｉｒｓｔＦ［０］〜ＦｉｒｓｔＦ［参照画像の個数−１］、変数ＡｃｔｉｖｅＣｏｕｎｔ、変数ＲｅａｄＩＤ、変数Ｅｘ［０］〜Ｅｘ［参照画像の個数−１］、ＦｏｕｎｄＮｕｍ、及び変数Ｒａｎｋに、以下のような値をそれぞれ設定する（ステップ２３０１）。
【０１６３】
ＲＩＤ＝０
ＦｉｒｓｔＦ［０］〜ＦｉｒｓｔＦ［参照画像の個数−１］＝１
ＡｃｔｉｖｅＣｏｕｎｔ＝０
ＲｅａｄＩＤ＝０
Ｅｘ［０］〜Ｅｘ［参照画像の個数−１］＝０
ＦｏｕｎｄＮｕｍ＝０
Ｒａｎｋ＝０
【０１６４】
次に、復元部１０１４は、ＡｃｔｉｖｅＣｏｕｎｔと参照画像の個数とを比較する（ステップ２３０２）。ＡｃｔｉｖｅＣｏｕｎｔが参照画像の個数よりも小さい場合（ステップ２３０２，ＹＥＳ）、復元部１０１４は、ＲｅａｄＩＤにＲＩＤを設定する（ステップ２３０３）。一方、ＡｃｔｉｖｅＣｏｕｎｔが参照画像の個数に達している場合（ステップ２３０２，ＮＯ）、復元部１０１４は、ステップ２３０４以降の処理を行う。
【０１６５】
次に、復元部１０１４は、ＲｅａｄＩＤとＲＩＤとを比較する（ステップ２３０４）。ＲｅａｄＩＤがＲＩＤに一致しない場合（ステップ２３０４，ＮＯ）、判定部１０１５は、ステップ２３２９以降の処理を行う。
【０１６６】
一方、ＲｅａｄＩＤがＲＩＤに一致する場合（ステップ２３０４，ＹＥＳ）、復元部１０１４は、記憶部１０１３の記憶領域［ＲＩＤ］［Ｉｄｘ］から、１つの端点のフォーマットビットを読み出す（ステップ２３０５）。次に、復元部１０１４は、記憶部１０１３の記憶領域［ＲＩＤ］［Ｉｄｘ］から、読み出したフォーマットビットが示すビット幅の整数値ｄを読み出す（ステップ２３０６）。そして、復元部１０１４は、基準座標［ＲＩＤ］［Ｉｄｘ］がＸ座標又はＹ座標のいずれであるかをチェックする（ステップ２３０７）。
【０１６７】
基準座標［ＲＩＤ］［Ｉｄｘ］がＸ座標である場合（ステップ２３０７，ＹＥＳ）、復元部１０１４は、ＦｉｒｓｔＦ［ＲＩＤ］と１とを比較する（ステップ２３０８）。ＦｉｒｓｔＦ［ＲＩＤ］が１である場合（ステップ２３０８，ＹＥＳ）、復元部１０１４は、Ｘ［ＲＩＤ］［Ｉｄｘ］にｄ／ＧＳを設定し、変数ＬＸにｄ／ＧＳを設定する（ステップ２３０９）。そして、復元部１０１４は、ＦｉｒｓｔＦ［ＲＩＤ］に０を設定する（ステップ２３１０）。
【０１６８】
一方、ＦｉｒｓｔＦ［ＲＩＤ］が０である場合（ステップ２３０８，ＮＯ）、復元部１０１４は、Ｘ［ＲＩＤ］［Ｉｄｘ］に次式の右辺の値を設定する（ステップ２３１１）。
【０１６９】
Ｘ［ＲＩＤ］［Ｉｄｘ］＝ＬＸ＋ｄ＊符号［ＲＩＤ］［Ｉｄｘ］／ＧＳ      （２１）
【０１７０】
次に、復元部１０１４は、エピポーラ線情報［ＲＩＤ］［Ｉｄｘ］の（ａ，ｂ）を用いて、次式によりＹ［ＲＩＤ］［Ｉｄｘ］を計算する（ステップ２３１２）。
【０１７１】
Ｙ［ＲＩＤ］［Ｉｄｘ］＝ａ＊Ｘ［ＲＩＤ］［Ｉｄｘ］＋ｂ      （２２）
【０１７２】
基準座標［ＲＩＤ］［Ｉｄｘ］がＹ座標である場合（ステップ２３０７，ＮＯ）、復元部１０１４は、ＦｉｒｓｔＦ［ＲＩＤ］と１とを比較する（ステップ２３１３）。ＦｉｒｓｔＦ［ＲＩＤ］が１である場合（ステップ２３１３，ＹＥＳ）、復元部１０１４は、Ｙ［ＲＩＤ］［Ｉｄｘ］にｄ／ＧＳを設定し、変数ＬＹにｄ／ＧＳを設定する（ステップ２３１４）。そして、復元部１０１４は、ＦｉｒｓｔＦ［ＲＩＤ］に０を設定する（ステップ２３１５）。
【０１７３】
一方、ＦｉｒｓｔＦ［ＲＩＤ］が０である場合（ステップ２３１３，ＮＯ）、復元部１０１４は、Ｙ［ＲＩＤ］［Ｉｄｘ］に次式の右辺の値を設定する（ステップ２３１６）。
【０１７４】
Ｙ［ＲＩＤ］［Ｉｄｘ］＝ＬＹ＋ｄ＊符号［ＲＩＤ］［Ｉｄｘ］／ＧＳ      （２３）
【０１７５】
次に、復元部１０１４は、エピポーラ線情報［ＲＩＤ］［Ｉｄｘ］の（ａ，ｂ）を用いて、次式によりＸ［ＲＩＤ］［Ｉｄｘ］を計算する（ステップ２３１７）。
【０１７６】
Ｘ［ＲＩＤ］［Ｉｄｘ］＝Ｙ［ＲＩＤ］［Ｉｄｘ］／ａ−ｂ／ａ      （２４）
【０１７７】
次に、復元部１０１４は、写像情報Ｍ２［ＲＩＤ］を用いて、ＲＩＤが示す参照画像内の点（Ｘ［ＲＩＤ］［Ｉｄｘ］，Ｙ［ＲＩＤ］［Ｉｄｘ］）を、対象画像の奥行き方向の直線上に写像し、ｚ［ＲＩＤ］［Ｉｄｘ］を計算する（ステップ２３１８）。
【０１７８】
次に、復元部１０１４は、ＡｃｔｉｖｅＣｏｕｎｔと参照画像の個数とを比較する（ステップ２３１９）。ＡｃｔｉｖｅＣｏｕｎｔが参照画像の個数よりも小さい場合（ステップ２３１９，ＹＥＳ）、復元部１０１４は、ＡｃｔｉｖｅＣｏｕｎｔを１だけインクリメントして（ステップ２３２０）、ＲＩＤと参照画像の個数とを比較する（ステップ２３２９）。
【０１７９】
ＲＩＤが参照画像の個数よりも小さい場合（ステップ２３２９，ＹＥＳ）、復元部１０１４は、ＲＩＤを１だけインクリメントして（ステップ２３３０）、ステップ２３０２以降の処理を繰り返す。一方、ＲＩＤが参照画像の個数に達している場合（ステップ２３２９，ＮＯ）、復元部１０１４は、ＲＩＤに０を設定して（ステップ２３３１）、ステップ２３０２以降の処理を繰り返す。
【０１８０】
ＡｃｔｉｖｅＣｏｕｎｔが参照画像の個数に達している場合（ステップ２３１９，ＮＯ）、判定部１０１５は、ｚ［０］［Ｉｄｘ］〜ｚ［参照画像の個数−１］［Ｉｄｘ］のうち、最小値ｚ［ＲＩＤ］［Ｉｄｘ］を求める（ステップ２３２１）。例えば、判定部１０１５は、マージソート等を用いて最小値ｚ［ＲＩＤ］［Ｉｄｘ］を求めることができる。
【０１８１】
次に、判定部１０１５は、ＲｅａｄＩＤに、最小値ｚ［ＲＩＤ］［Ｉｄｘ］のＲＩＤを設定して（ステップ２３２２）、Ｅｘ［ＲｅａｄＩＤ］と１とを比較する（ステップ２３２３）。
【０１８２】
Ｅｘ［ＲｅａｄＩＤ］が０である場合（ステップ２３２３，ＮＯ）、判定部１０１５は、Ｅｘ［ＲｅａｄＩＤ］に１を設定し、Ｒａｎｋを１だけインクリメントする（ステップ２３２４）。この場合、ｚ［ＲｅａｄＩＤ］［Ｉｄｘ］は、ｚ軸上の線分の２つの端点のうち、基準カメラに近い方の端点（物体の表面）に対応する。
【０１８３】
一方、Ｅｘ［ＲｅａｄＩＤ］が１である場合（ステップ２３２３，ＹＥＳ）、判定部１０１５は、Ｅｘ［ＲｅａｄＩＤ］に０を設定し、Ｒａｎｋを１だけデクリメントする（ステップ２３２５）。この場合、ｚ［ＲｅａｄＩＤ］［Ｉｄｘ］は、ｚ軸上の線分の２つの端点のうち、基準カメラから遠い方の端点（物体の裏面）に対応する。
【０１８４】
次に、判定部１０１５は、Ｒａｎｋと打ち切りＲａｎｋ数とを比較する（ステップ２３２６）。打ち切りＲａｎｋ数としては、参照画像の個数以下の値を用いることができる。撮影条件又はマスク画像生成処理による誤差を吸収したい場合は、打ち切りＲａｎｋ数として、参照画像の個数よりも小さな値を用いてもよい。
【０１８５】
Ｒａｎｋが打ち切りＲａｎｋ数よりも大きい場合（ステップ２３２６，ＹＥＳ）、判定部１０１５は、ＦｏｕｎｄＮｕｍを１だけインクリメントする（ステップ２３２７）。一方、Ｒａｎｋが打ち切りＲａｎｋ数以下である場合（ステップ２３２６，ＮＯ）、判定部１０１５は、ステップ２３２８以降の処理を行う。
【０１８６】
次に、判定部１０１５は、ＦｏｕｎｄＮｕｍと打ち切り点数とを比較する（ステップ２３２８）。打ち切り点数は、基準カメラから見たｚ軸上の物体の表面又は裏面の個数を表す。例えば、ｚ軸上の最初の表面を求める場合は、打ち切り点数が１に設定され、ｚ軸上の最初の裏面（表→裏）を求める場合は、打ち切り点数が２に設定される。また、ｚ軸上の２番目の表面（表→裏→表）を求める場合は、打ち切り点数が３に設定される。
【０１８７】
ＦｏｕｎｄＮｕｍが打ち切り点数以下である場合（ステップ２３２８，ＮＯ）、判定部１０１５は、ステップ２３２９以降の処理を行う。一方、ＦｏｕｎｄＮｕｍが打ち切り点数を超えた場合（ステップ２３２８，ＹＥＳ）、判定部１０１５は、ｚ［ＲｅａｄＩＤ］［Ｉｄｘ］を距離情報ｚとして出力する（ステップ２３３２）。
【０１８８】
ところで、図１８のVisualHull処理において、１つの参照画像内の各エピポーラ線上での線分探索処理は独立して行うことができるため、複数のエピポーラ線上での線分探索処理を並列に実行することが可能である。同様に、対象画像のマスク画像内の物体領域の各画素に対する重複判定処理も独立して行うことができるため、物体領域の複数の画素に対する重複判定処理も並列に実行することが可能である。
【０１８９】
図２４は、線分探索処理及び重複判定処理を並列化したVisualHull処理の例を示すフローチャートである。まず、線分探索部１７０２は、ＲＩＤに初期値０を設定し（ステップ２４０１）、対象画像のマスク画像内の複数のマスク画素（ｘ，ｙ）に対して、ステップ２４０２〜ステップ２４０４の処理を並列に実行する。
【０１９０】
線分探索部１７０２は、対象画像のマスク画像からマスク画素（ｘ，ｙ）の画素値を取得し（ステップ２４０２）、マスク画素（ｘ，ｙ）の画素値がＦＧであるか否かをチェックする（ステップ２４０３）。マスク画素（ｘ，ｙ）の画素値がＦＧである場合（ステップ２４０３，ＹＥＳ）、線分探索部１７０２は、図１８のステップ１８０６のエピポーラ線情報生成処理及びステップ１８０７の線分探索処理を行う（ステップ２４０４）。一方、マスク画素（ｘ，ｙ）の画素値がＦＧではない場合（ステップ２４０３，ＮＯ）、線分探索部１７０２は、ステップ２４０４の処理をスキップする。
【０１９１】
次に、線分探索部１７０２は、ＲＩＤを１だけインクリメントして（ステップ２４０５）、ＲＩＤと参照画像の個数とを比較する（ステップ２４０６）。ＲＩＤが参照画像の個数よりも小さい場合（ステップ２４０６，ＹＥＳ）、線分探索部１７０２は、ステップ２４０２以降の処理を繰り返す。
【０１９２】
そして、ＲＩＤが参照画像の個数に達した場合（ステップ２４０６，ＮＯ）、判定部１０１５は、対象画像のマスク画像内の複数のマスク画素（ｘ，ｙ）に対して、ステップ２４０７の重複判定処理を並列に実行する。ステップ２４０７において、判定部１０１５は、図１８のステップ１８１７の重複判定処理を行う。
【０１９３】
図２４のVisualHull処理において、ＲＩＤに関するループ処理をさらに並列化してもよい。また、マスク画素（ｘ，ｙ）に関する並列処理をループ処理に変更して、ＲＩＤに関するループ処理を並列化してもよい。
【０１９４】
図１７の情報処理装置１００１によれば、線分探索処理よって探索された線分の端点の基準座標を、その基準座標と他の端点の基準座標との差分に変換することで、線分端座標のデータ量が削減される。
【０１９５】
これにより、レイテンシが大きなメインメモリへのアクセス量が最小化し、レイテンシの影響を最小化することができる。また、サイズが小さく、かつ、レイテンシが小さなローカルメモリを記憶部１０１３として有効に活用することが可能になり、レイテンシが大きなメインメモリへのアクセスによるレイテンシの影響を最小化することができる。ローカルメモリの使用効率が向上し、メインメモリから線分端座標を読み出すことによるオーバヘッドが最小化されることで、重複判定処理の性能が向上する。
【０１９６】
図２５は、エピポーラ線上における線分探索処理の探索結果の例を示している。図２５の参照画像のマスク画像の解像度は４０９６×２１６０であり、エピポーラ線２５０１上には物体領域２５１１〜物体領域２５１３が存在する。
【０１９７】
この例では、物体領域２５１１の境界とエピポーラ線２５０１との２つの交点、物体領域２５１２の境界とエピポーラ線２５０１との２つの交点、及び物体領域２５１３の境界とエピポーラ線２５０１との１つの交点が線分の端点として検出されている。これらの５つの端点のＸ座標は、１０、１５、１９、２５、及び２０００である。
【０１９８】
同じ物体領域の境界上の２つの端点のＸ座標の差分は小さい。また、物体領域２５１１と物体領域２５１２のように、２つの物体領域が近接している場合、一方の物体領域の境界上の端点と他方の物体領域の境界上の端点との間におけるＸ座標の差分は小さい。一方、物体領域２５１２と物体領域２５１３のように、２つの物体領域が離れている場合、一方の物体領域の境界上の端点と他方の物体領域の境界上の端点との間におけるＸ座標の差分は大きい。
【０１９９】
最初の端点（Ｘ＝１０）と２番目の端点（Ｘ＝１５）との間におけるＸ座標の差分は５であり、２番目の端点（Ｘ＝１５）と３番目の端点（Ｘ＝１９）との間におけるＸ座標の差分は４である。３番目の端点（Ｘ＝１９）と４番目の端点（Ｘ＝２５）との間におけるＸ座標の差分は６であり、５番目の端点（Ｘ＝２０００）と４番目の端点（Ｘ＝２５）との間におけるＸ座標の差分は１９７５である。
【０２００】
図２６は、図２５の探索結果を記憶する記憶領域の例を示している。図２６（ａ）は、各端点のＸ座標を半精度浮動小数点数型変数として記憶する、従来の記憶領域の例を示している。この場合、各Ｘ座標が１６ビットの半精度浮動小数点数型変数に格納することができ、総ビット数は、１６ビット×５＝８０ビットになる。
【０２０１】
図２６（ｂ）は、図１７の記憶部１０１３の記憶領域の例を示している。この場合、Ｉｎｃ＝ＧＳ＝１であり、２番目〜５番目の端点のＸ座標が座標差分に変換され、最初の端点のＸ座標と、２番目〜５番目の端点のＸ座標の差分とが、整数型変数に格納される。したがって、記憶領域に格納される整数値は、１０、５、４、６、及び１９７５である。
【０２０２】
このうち、１０、５、４、及び６は、８ビットの整数型変数ＩＮＴ８に格納され、１９７５は、１６ビットの整数型変数ＩＮＴ１６に格納され、各整数型変数の最初の１ビットは、フォーマットビットとして使用される。整数型変数がＩＮＴ８である場合、そのフォーマットビットには“０”が格納され、整数型変数がＩＮＴ１６である場合、そのフォーマットビットには“１”が格納される。
【０２０３】
４つのＩＮＴ８と１つのＩＮＴ１６の総ビット数は、８ビット×４＋１６ビット＝４８ビットになり、図２６（ａ）の記憶領域よりも３２ビットだけ減少している。
【０２０４】
これらの５つの整数値から元のＸ座標を復元する場合、各整数型変数から、そのフォーマットビットが示すビット幅の整数値が読み出される。そして、最初の整数値１０は、そのまま最初の端点のＸ座標として使用され、２番目〜５番目の整数値は、直前の端点のＸ座標に対する差分として使用される。
【０２０５】
したがって、最初の端点のＸ座標１０と２番目の整数値５とを加算することで、２番目の端点のＸ座標１５が復元され、２番目の端点のＸ座標１５と３番目の整数値４とを加算することで、３番目の端点のＸ座標１９が復元される。また、３番目の端点のＸ座標１９と４番目の整数値６とを加算することで、４番目の端点のＸ座標２５が復元され、４番目の端点のＸ座標２５と５番目の整数値１９７５とを加算することで、５番目の端点のＸ座標２０００が復元される。
【０２０６】
基準座標であるＸ座標の精度を上げるために、図２５のエピポーラ線２５０１上において、Ｉｎｃを１よりも小さな値に設定して線分探索処理を行うことも可能である。例えば、Ｉｎｃ＝０．１及びＧＳ＝１０に設定して、Ｘ座標を固定小数点数として扱った場合、記憶部１０１３の記憶領域に格納される５つの整数値は、１００、５０、４０、６０、及び１９７５０となる。この場合も、図２６（ｂ）の場合と同様に、４つのＩＮＴ８と１つのＩＮＴ１６とを用いて、探索結果を格納することができる。
【０２０７】
図１７の情報処理装置１００１は、自由視点映像、仮想現実（Virtual Reality, ＶＲ）、拡張現実（Augmented Reality, ＡＲ）等の様々な映像技術に適用することが可能である。
【０２０８】
図２７は、図１７の情報処理装置１００１を用いて自由視点映像を生成する自由視点映像生成処理の例を示している。撮影対象の３次元領域を囲むように、カメラ２７０１−１〜カメラ２７０１−Ｎ（Ｎは３以上の整数）が配置される。各カメラ２７０１−ｉ（ｉ＝１〜Ｎ）は、例えば、Charged-Coupled Device（ＣＣＤ）、Complementary Metal-Oxide-Semiconductor（ＣＭＯＳ）等の撮像素子を有し、撮影対象の３次元領域に存在する物体の映像を撮影する。各カメラ２７０１−ｉによって撮影された映像は、複数の時刻それぞれにおける複数のカメラ画像を含む。
【０２０９】
前景分離処理２７０２−ｉは、カメラ２７０１−ｉによって撮影された映像に含まれる各カメラ画像から、物体領域である前景を示す画素と、それ以外の背景を示す画素とを含むマスク画像を生成する処理である。VisualHull処理２７０３−ｉは、前景分離処理２７０２−１〜前景分離処理２７０２−Ｎによって生成されたＮ個のマスク画像から、物体の３次元形状を抽出し、カメラ２７０１−ｉの視点から物体までの距離情報ｚを生成する処理である。
【０２１０】
レンダリング処理２７０４は、カメラ２７０１−１〜カメラ２７０１−Ｎの視点のうちいくつかの視点を選択し、選択した視点の距離情報ｚ、カメラ画像、及びマスク画像内の背景領域を示す背景情報を用いて、自由視点画像を生成する処理である。レンダリング処理２７０４では、ユーザが指定した自由視点（任意の視点）から見た各物体の位置関係が決定され、決定された位置関係に合わせて前景及び背景が合成される。そして、カメラ画像から前景の画素値を決定することで、各画素の色が確定される。これにより、自由視点から見た自由視点画像が生成される。
【０２１１】
前景分離処理２７０２−ｉ及びVisualHull処理２７０３−ｉの個数は、カメラ２７０１−ｉの台数と同じであってもよく、カメラ２７０１−ｉの台数とは異なっていてもよい。また、VisualHull処理２７０３−ｉにおいて、視体積交差法により十分な精度で３次元形状が抽出される場合は、必ずしもすべてのカメラ２７０１−ｉのマスク画像を用いる必要はない。
【０２１２】
前景分離処理２７０２−ｉ、VisualHull処理２７０３−ｉ、及びレンダリング処理２７０４は、１台の情報処理装置によって行われてもよく、負荷分散により複数の情報処理装置によって行われてもよい。
【０２１３】
図２８は、図２７のレンダリング処理２７０４によって表示される自由視点画像の例を示している。撮影対象の３次元領域内に物体２８０１及び物体２８０２が存在する場合、指定された視点から見える物体２８０１及び物体２８０２それぞれの表面に対応する色を画面上に描画することで、その視点から見た画像が生成される。
【０２１４】
例えば、視点２８１１から見た画像２８２１では、物体２８０１と物体２８０２とが重なっており、視点２８１２から見た画像２８２２では、物体２８０１と物体２８０２とが離れている。複数の時刻における自由視点画像を時系列に連結することで、自由視点映像が生成される。例えば、自由視点映像の撮影対象は、スポーツの試合、音楽のコンサート等であってもよい。
【０２１５】
図２９は、図２７の自由視点映像生成処理を行う自由視点映像装置の機能的構成例を示している。図２９の自由視点映像装置２９０１は、映像取得部２９１１、前景分離部２９１２、VisualHull部２９１３、及びレンダリング部２９１４を含む。VisualHull部２９１３は、図１７の情報処理装置１００１と同様の構成を有する。
【０２１６】
映像取得部２９１１は、カメラ２７０１−１〜カメラ２７０１−Ｎそれぞれによって撮影された映像を取得し、取得した映像に含まれる各時刻のカメラ画像を、前景分離部２９１２及びレンダリング部２９１４へ出力する。
【０２１７】
前景分離部２９１２は、各カメラ画像に対して前景分離処理を行い、マスク画像を生成する。そして、前景分離部２９１２は、生成したマスク画像をVisualHull部２９１３へ出力し、マスク画像内の背景領域を示す背景情報をレンダリング部２９１４へ出力する。VisualHull部２９１３は、カメラ２７０１−１〜カメラ２７０１−Ｎそれぞれのカメラ光学情報及びカメラ位置情報と、前景分離部２９１２が出力するマスク画像とを用いて、VisualHull処理を行い、距離情報ｚをレンダリング部２９１４へ出力する。
【０２１８】
レンダリング部２９１４は、ユーザによって指定された視点位置、カメラ光学情報、カメラ位置情報、カメラ画像、背景情報、及び距離情報ｚを用いて、レンダリング処理を行い、自由視点画像を生成する。
【０２１９】
図３０は、図２９の前景分離部２９１２が行う前景分離処理の例を示すフローチャートである。まず、映像取得部２９１１は、カメラ２７０１−１〜カメラ２７０１−Ｎそれぞれから、１つの時刻のカメラ画像を取得し（ステップ３００１）、取得したカメラ画像を、前景分離部２９１２及びレンダリング部２９１４へ出力する（ステップ３００２）。
【０２２０】
次に、前景分離部２９１２は、カメラ画像に対するレイヤ分離処理を行って、各レイヤのカメラ画像を生成する（ステップ３００３）。例えば、カメラ２７０１−ｉがステレオカメラである場合、前景分離部２９１２は、視差から距離を求め、求めた距離毎のレイヤのカメラ画像を生成することができる。
【０２２１】
次に、前景分離部２９１２は、VisualHull処理の対象となるレイヤのカメラ画像内において、物体領域の各画素に前景を示す画素値を設定し、背景領域の各画素に背景を示す画素値を設定することで、マスク画像を生成する（ステップ３００４）。そして、前景分離部２９１２は、生成したマスク画像をVisualHull部２９１３へ出力する（ステップ３００５）。カメラ２７０１−ｉがステレオカメラである場合、ステレオカメラの２枚のカメラ画像のうち、一方のカメラ画像に対するマスク画像が生成される。
【０２２２】
次に、前景分離部２９１２は、生成したマスク画像内の背景領域を示す背景情報を、レンダリング部２９１４へ出力する（ステップ３００６）。この背景情報は、カメラ画像に対するレイヤ分離処理によって得られた、背景領域の３次元情報を含む。レイヤ分離処理によって得られた３次元情報の精度は、VisualHull処理によって得られる３次元情報の精度よりも低いが、背景領域の描画には十分である。
【０２２３】
次に、前景分離部２９１２は、ユーザから終了指示が入力された否かをチェックする（ステップ３００７）。終了指示が入力されていない場合（ステップ３００７，ＮＯ）、自由視点映像装置２９０１は、次の時刻のカメラ画像について、ステップ３００１以降の処理を繰り返す。そして、終了指示が入力された場合（ステップ３００７，ＹＥＳ）、自由視点映像装置２９０１は、処理を終了する。
【０２２４】
図３１は、図２９のVisualHull部２９１３が行うVisualHull処理の例を示すフローチャートである。まず、VisualHull部２９１３は、カメラ２７０１−１〜カメラ２７０１−Ｎの中から基準カメラを選択し、それ以外のカメラを参照カメラに指定する（ステップ３１０１）。
【０２２５】
次に、VisualHull部２９１３は、変数Ｃｏｕｎｔに初期値０を設定し（ステップ３１０２）、前景分離部２９１２が出力する、１つの時刻における複数の参照画像のマスク画像のうち、１つのマスク画像を受け取る（ステップ３１０３）。そして、VisualHull部２９１３は、Ｃｏｕｎｔを１だけインクリメントして（ステップ３１０４）、Ｃｏｕｎｔと参照画像の個数とを比較する（ステップ３１０５）。
【０２２６】
Ｃｏｕｎｔが参照画像の個数よりも小さい場合（ステップ３１０５，ＹＥＳ）、VisualHull部２９１３は、ステップ３１０３以降の処理を繰り返す。そして、Ｃｏｕｎｔが参照画像の個数に達した場合（ステップ３１０５，ＮＯ）、VisualHull部２９１３は、図１８のVisualHull処理を行い（ステップ３１０６）、距離情報ｚをレンダリング部２９１４へ出力する（ステップ３１０７）。
【０２２７】
次に、VisualHull部２９１３は、ユーザから終了指示が入力された否かをチェックする（ステップ３１０８）。終了指示が入力されていない場合（ステップ３１０８，ＮＯ）、VisualHull部２９１３は、次の時刻のマスク画像について、ステップ３１０２以降の処理を繰り返す。そして、終了指示が入力された場合（ステップ３１０８，ＹＥＳ）、VisualHull部２９１３は、処理を終了する。
【０２２８】
図３２は、図２９のレンダリング部２９１４が行うレンダリング処理の例を示すフローチャートである。まず、レンダリング部２９１４は、視点位置の初期値を設定し（ステップ３２０１）、ユーザから視点位置が入力された否かをチェックする（ステップ３２０２）。視点位置が入力された場合（ステップ３２０２，ＹＥＳ）、レンダリング部２９１４は、入力された視点位置を設定する（ステップ３２０３）。一方、視点位置が入力されていない場合（ステップ３２０２，ＮＯ）、レンダリング部２９１４は、ステップ３２０４以降の処理を行う。
【０２２９】
次に、レンダリング部２９１４は、背景領域の合成画像を生成する（ステップ３２０４）。ステップ３２０４において、まず、レンダリング部２９１４は、１つの時刻におけるカメラ２７０１−１〜カメラ２７０１−Ｎのカメラ画像の中から、設定された視点位置に応じた複数のカメラ画像を選択し、選択したカメラ画像から背景領域の画像を抽出する。
【０２３０】
次に、レンダリング部２９１４は、カメラ光学情報、カメラ位置情報、設定された視点位置、及び前景分離部２９１２が出力する背景情報を用いて、選択した複数のカメラ画像を視点位置における座標系に変換する。そして、レンダリング部２９１４は、重み付き平均、光補正等により、変換した複数のカメラ画像の画素値を合成することで、背景領域の合成画像を生成する。
【０２３１】
次に、レンダリング部２９１４は、VisualHull部２９１３が出力する距離情報ｚを用いて、物体の３次元形状を確定し、確定した３次元形状を視点位置における座標系に変換することで、物体領域の物体画像を生成する（ステップ３２０５）。例えば、レンダリング部２９１４は、確定した３次元形状に対して回転、拡大、又は縮小等の変換操作を行うことで、３次元形状の位置合わせを行うことができる。
【０２３２】
次に、レンダリング部２９１４は、背景領域の合成画像と物体画像とを合成することで、視点位置から見た自由視点画像を生成し（ステップ３２０６）、生成した自由視点画像を画面上に表示する（ステップ３２０７）。
【０２３３】
次に、レンダリング部２９１４は、ユーザから終了指示が入力された否かをチェックする（ステップ３２０８）。終了指示が入力されていない場合（ステップ３２０８，ＮＯ）、レンダリング部２９１４は、次の時刻のカメラ画像について、ステップ３２０２以降の処理を繰り返す。そして、終了指示が入力された場合（ステップ３２０８，ＹＥＳ）、レンダリング部２９１４は、処理を終了する。
【０２３４】
図３３は、図１０及び図１７の情報処理装置１００１、又は図２９の自由視点映像装置２９０１として用いられる情報処理装置のハードウェア構成例を示している。図３３の情報処理装置３３０１は、メモリ３３１１、ハードディスクドライブ３３１２、ネットワークインタフェース３３１３、演算部３３１４、及び媒体駆動装置３３１５を含む。これらの構成要素はバス３３１６により互いに接続されている。バス３３１６には、カメラ２７０１−ｉ、表示装置３３０２、及び入力装置３３０３が接続されていてもよい。
【０２３５】
メモリ３３１１は、例えば、Read Only Memory（ＲＯＭ）、Random Access Memory（ＲＡＭ）、フラッシュメモリ等の半導体メモリであり、処理に用いられるプログラム及びデータを格納する。メモリ３３１１は、図１０及び図１７の記憶部１０１３として用いることができる。
【０２３６】
演算部３３１４は、Central Processing Unit（ＣＰＵ）、Graphics Processing Unit（ＧＰＵ）、Field-Programmable Gate Array（ＦＰＧＡ）、専用ハードウェア回路等である。演算部３３１４は、図１０の生成部１０１１、図１０及び図１７の変換部１０１２、復元部１０１４、及び判定部１０１５として動作する。演算部３３１４は、図１７の写像情報生成部１７０１、線分探索部１７０２、図２９の映像取得部２９１１、前景分離部２９１２、VisualHull部２９１３、及びレンダリング部２９１４としても動作する。
【０２３７】
例えば、演算部３３１４がＣＰＵ（プロセッサ）である場合、演算部３３１４は、メモリ３３１１を利用してプログラムを実行することにより、画像処理、VisualHull処理、又は自由視点映像生成処理を行う。
【０２３８】
ハードディスクドライブ３３１２は、処理に用いられるプログラム及びデータを記憶する磁気ディスク装置である。情報処理装置３３０１は、ハードディスクドライブ３３１２が記憶するプログラム及びデータを、メモリ３３１１にロードして使用することができる。ハードディスクドライブ３３１２の代わりに、光ディスク装置、光磁気ディスク装置、テープ装置等の補助記憶装置を用いてもよい。
【０２３９】
ネットワークインタフェース３３１３は、Local Area Network、Wide Area Network等の通信ネットワークに接続され、通信に伴うデータ変換を行う通信インタフェース回路である。情報処理装置３３０１は、プログラム及びデータを外部の装置からネットワークインタフェース３３１３を介して受信し、それらをメモリ３３１１にロードして使用することができる。
【０２４０】
媒体駆動装置３３１５は、可搬型記録媒体３３１７を駆動し、その記録内容にアクセスする。可搬型記録媒体３３１７は、メモリデバイス、フレキシブルディスク、光ディスク、光磁気ディスク等である。可搬型記録媒体３３１７は、Compact Disk Read Only Memory（ＣＤ−ＲＯＭ）、Digital Versatile Disk（ＤＶＤ）、Universal Serial Bus（ＵＳＢ）メモリ等であってもよい。オペレータ又はユーザは、可搬型記録媒体３３１７にプログラム及びデータを格納しておき、それらをメモリ３３１１にロードして使用することができる。
【０２４１】
このように、処理に用いられるプログラム及びデータを格納するコンピュータ読み取り可能な記録媒体は、メモリ３３１１、ハードディスクドライブ３３１２、又は可搬型記録媒体３３１７のような、物理的な（非一時的な）記録媒体である。
【０２４２】
入力装置３３０３は、例えば、キーボード、ポインティングデバイス等であり、オペレータ又はユーザからの指示又は情報の入力に用いられる。表示装置３３０２は、オペレータ又はユーザへの問い合わせ又は指示、及び処理結果を画面上に表示する。処理結果は、距離情報ｚであってもよく、自由視点映像であってもよい。
【０２４３】
プログラムで使用される一般的な変数としては、８ビット、１６ビット、３２ビット、及び６４ビットの変数が定義されている。このため、演算部３３１４がＣＰＵ、ＧＰＵ等である場合は、記憶部１０１３の記憶領域のフォーマットとして、これらのビット幅を用いることが便利である。
【０２４４】
しかし、線分端座標のデータ量をより圧縮したい場合、又は演算部３３１４がＦＰＧＡ、専用ハードウェア回路等である場合には、必ずしも８ビット、１６ビット、３２ビット、及び６４ビットのビット幅を用いる必要はない。
【０２４５】
記憶領域のフォーマットとして任意のビット幅を用いた場合であっても、そのビット幅を示す適切なビット数のフォーマットビット列を定義して、線分端座標を記憶領域に格納することが可能である。そして、フォーマットビット列の読み出しと、そのフォーマットビット列が示すビット幅のデータの読み出しとを繰り返すことで、記憶領域から線分端座標を読み出すことができる。
【０２４６】
情報処理装置１００１は、複数の演算部３３１４を含んでいてもよい。この場合、複数の演算部３３１４は、画像処理、VisualHull処理、又は自由視点映像生成処理を並列に実行することができる。
【０２４７】
図３４は、図３３の演算部３３１４内のローカルメモリの例を示している。演算部３３１４は、演算回路３４０１、シェアードメモリ３４０２、及びキャッシュメモリ３４０３を含む。
【０２４８】
シェアードメモリ３４０２及びキャッシュメモリ３４０３は、ローカルメモリに対応し、チップ内バスによって演算回路３４０１と接続されている。一方、メモリ３４０４は、グローバルメモリ（オフチップメモリ）に対応し、チップ間接続バスによって演算回路３４０１と接続されている。図３３のメモリ３３１１は、メモリ３４０４に対応する。チップ間接続バスは、チップ内バスよりも伝送帯域が小さく、チップ内バスよりもレイテンシが大きい。
【０２４９】
シェアードメモリ３４０２及びキャッシュメモリ３４０３の容量は小さく、メモリ３４０４の容量は大きい。ユーザは、シェアードメモリ３４０２及びメモリ３４０４内のデータ配置を制御することが可能である。一方、キャッシュメモリ３４０３内のデータ配置は、キャッシュ管理機構によって制御される。
【０２５０】
シェアードメモリ３４０２、キャッシュメモリ３４０３、及びメモリ３４０４は、図１０及び図１７の記憶部１０１３として用いることができる。線分端座標のデータ量が十分に小さい場合、主としてシェアードメモリ３４０２及びキャッシュメモリ３４０３が記憶部１０１３として用いられる。
【０２５１】
図３５は、図３３の演算部３３１４の第１の構成例を示している。図３５のＣＰＵ３５０１は、演算部３３１４に対応し、演算回路３５１１、レジスタ３５１２、シェアードメモリ３５１３、及びキャッシュメモリ３５１４を含む。シェアードメモリ３５１３及びキャッシュメモリ３５１４は、チップ内バス３５２１によって演算回路３５１１と接続されている。一方、メモリ３３１１は、チップ間接続バス３５２２によってＣＰＵ３５０１と接続されている。
【０２５２】
シェアードメモリ３５１３、キャッシュメモリ３５１４、及びメモリ３３１１は、図１０及び図１７の記憶部１０１３として用いることができる。線分端座標のデータ量が十分に小さい場合、主としてシェアードメモリ３５１３及びキャッシュメモリ３５１４が記憶部１０１３として用いられる。
【０２５３】
図３６は、図３３の演算部３３１４の第２の構成例を示している。図３６のボード３６０１上には、ＧＰＵ３６０２及びメモリ３６０３が実装されている。ＧＰＵ３６０２は、演算部３３１４に対応し、演算回路３６１１、レジスタ３６１２、シェアードメモリ３６１３、及びキャッシュメモリ３６１４を含む。シェアードメモリ３６１３及びキャッシュメモリ３６１４は、チップ内バス３６２１によって演算回路３６１１と接続されている。
【０２５４】
メモリ３６０３は、グローバルメモリに対応し、チップ間接続バス３６２２によってＧＰＵ３６０２と接続されている。メモリ３３１１は、拡張バス３６２３によってボード３６０１上のＧＰＵ３６０２と接続されている。拡張バス３６２３は、例えば、Peripheral Component Interconnect Express（ＰＣＩ  Ｅｘｐｒｅｓｓ）であり、チップ間接続バス３６２２よりもさらに伝送帯域が小さい。
【０２５５】
シェアードメモリ３６１３、キャッシュメモリ３６１４、メモリ３６０３、及びメモリ３３１１は、図１０及び図１７の記憶部１０１３として用いることができる。線分端座標のデータ量が十分に小さい場合、主としてシェアードメモリ３６１３及びキャッシュメモリ３６１４が記憶部１０１３として用いられる。
【０２５６】
図１０及び図１７の情報処理装置１００１の構成は一例に過ぎず、情報処理装置１００１の用途又は条件に応じて一部の構成要素を省略又は変更してもよい。例えば、図１７の情報処理装置１００１において、写像情報Ｍ１［ＲＩＤ］及び写像情報Ｍ２［ＲＩＤ］が外部の装置によって生成される場合は、写像情報生成部１７０１を省略することができる。
【０２５７】
図２９の自由視点映像装置２９０１の構成は一例に過ぎず、自由視点映像装置２９０１の用途又は条件に応じて一部の構成要素を省略又は変更してもよい。例えば、自由視点映像装置２９０１は、レンダリング部２９１４が生成した自由視点映像を表示する表示装置を含んでいてもよい。
【０２５８】
図１１、図１８〜図２４、及び図３０〜図３２のフローチャートは一例に過ぎず、情報処理装置１００１又は自由視点映像装置２９０１の構成又は条件に応じて、一部の処理を省略又は変更してもよい。
【０２５９】
図１〜図３のエピポーラ線と図３及び図４のシルエットコーンは一例に過ぎず、エピポーラ線及びシルエットコーンは、撮影対象の物体と各カメラの位置に応じて変化する。
【０２６０】
図５、図７、及び図１６の重複判定処理は一例に過ぎず、重複判定処理は、線分探索処理の探索結果に応じて変化する。図６のマスク画像は一例に過ぎず、マスク画像は、撮影対象の物体に応じて変化する。
【０２６１】
図８及び図９の３次元形状構築部８０１の構成は一例に過ぎず、３次元形状構築部８０１の用途又は条件に応じて一部の構成要素を省略又は変更してもよい。
【０２６２】
図１２、図１３、図２５、及び図２６の線分端座標は一例に過ぎず、線分端座標は、線分探索処理の探索結果に応じて変化する。図１４の線分端座標の選択方法と図１５の符号の決定方法は一例に過ぎず、別の選択方法及び決定方法を用いてもよい。
【０２６３】
図２７の自由視点映像生成処理は一例に過ぎず、自由視点映像装置２９０１の用途又は条件に応じて一部の処理を省略又は変更してもよい。図２８の自由視点画像は一例に過ぎず、自由視点画像は、撮影対象の物体及び視点位置に応じて変化する。
【０２６４】
図３３の情報処理装置３３０１、図３４のメモリ構成、図３５及び図３６の演算部の構成は一例に過ぎず、情報処理装置３３０１の用途又は条件に応じて一部の構成要素を省略又は変更してもよい。例えば、図３３の情報処理装置３３０１において、通信ネットワーク又は可搬型記録媒体３３１７を使用しない場合は、ネットワークインタフェース３３１３又は媒体駆動装置３３１５を省略してもよい。ハードディスクドライブ３３１２を使用しない場合は、ハードディスクドライブ３３１２を省略してもよい。
【０２６５】
式（１）〜式（２４）の計算式は一例に過ぎず、情報処理装置１００１の構成又は条件に応じて別の計算式を用いてもよい。
【０２６６】
開示の実施形態とその利点について詳しく説明したが、当業者は、特許請求の範囲に明確に記載した本発明の範囲から逸脱することなく、様々な変更、追加、省略をすることができるであろう。
【０２６７】
図１乃至図３６を参照しながら説明した実施形態に関し、さらに以下の付記を開示する。
（付記１）
３次元空間内における撮像装置の投影中心と、前記撮像装置の投影面内において物体を表す点とを通る第１直線を、前記撮像装置以外の複数の撮像装置それぞれによって撮影された複数の画像各々に写像した第２直線上において、前記物体の存在範囲を表す線分を生成する生成部と、
前記複数の画像それぞれから生成された複数の線分各々について、前記画像内における前記線分の一方の端点の座標を、前記一方の端点の座標と他方の端点の座標との差分に変換する変換部と、
前記他方の端点の座標と前記差分とを記憶する記憶部と、
前記記憶部が記憶する前記他方の端点の座標と前記差分とから、前記一方の端点の座標を復元する復元部と、
前記他方の端点の座標と前記復元部が復元した前記一方の端点の座標とを、前記投影面の奥行き方向に写像した結果に基づいて、前記複数の線分の間における前記奥行き方向の重複判定を行う判定部と、
を備えることを特徴とする情報処理装置。
（付記２）
前記生成部は、前記３次元空間内の点を前記複数の画像各々に写像する写像情報を用いて、前記画像の水平方向の座標と前記画像の垂直方向の座標とによって記述される前記第２直線の方程式を求め、
前記記憶部が記憶する前記他方の端点の座標は、前記水平方向の座標又は前記垂直方向の座標のうちいずれか一方に対応する第１座標であり、前記記憶部が記憶する前記差分は、前記第１座標の差分であり、
前記復元部は、前記記憶部が記憶する前記他方の端点の前記第１座標と前記第１座標の差分とから、前記一方の端点の前記第１座標を復元し、前記第２直線の方程式を用いて、前記他方の端点の前記第１座標から、前記水平方向の座標又は前記垂直方向の座標のうち前記第１座標とは異なる第２座標を求め、前記第２直線の方程式を用いて、前記一方の端点の前記第１座標から前記一方の端点の前記第２座標を求め、前記他方の端点の前記第１座標及び前記第２座標と、前記一方の端点の前記第１座標及び前記第２座標とを、前記奥行き方向に写像することを特徴とする付記１記載の情報処理装置。
（付記３）
前記一方の端点と前記他方の端点との間における前記第１座標の差分は、前記一方の端点と前記他方の端点との間における前記第２座標の差分よりも大きく、前記他方の端点の前記第１座標は整数型変数であり、前記第１座標の差分は整数型変数であることを特徴とする付記１又は２記載の情報処理装置。
（付記４）
前記変換部は、前記他方の端点の前記第１座標を表す整数型変数のビット幅を、前記他方の端点の前記第１座標の値に基づいて決定し、前記第１座標の差分を表す整数型変数のビット幅を、前記第１座標の差分の値に基づいて決定することを特徴とする付記３記載の情報処理装置。
（付記５）
前記生成部は、前記第２直線上において、前記物体の存在範囲を表す線分である第１線分を生成するとともに、前記物体を含む１つ又は複数の物体の存在範囲を表す複数の第２線分を生成し、
前記変換部は、前記複数の第２線分各々の端点の座標を、前記複数の第２線分各々の端点の座標と、前記複数の第２線分各々の他の端点の座標又は他の第２線分の端点の座標又は前記第１線分の一方の端点の座標との差分に変換し、
前記記憶部は、前記複数の線分各々の端点の座標から生成された差分をさらに記憶し、
前記復元部は、前記複数の線分各々の端点の座標から生成された差分から、前記複数の線分各々の端点の座標を復元し、復元した前記複数の線分各々の端点の座標を、前記奥行き方向に写像し、
前記判定部は、前記複数の画像それぞれから生成された複数の線分の間における前記奥行き方向の重複判定を行うことを特徴とする付記１乃至４のいずれか１項に記載の情報処理装置。
（付記６）
３次元空間内における撮像装置の投影中心と、前記撮像装置の投影面内において物体を表す点とを通る第１直線を、前記撮像装置以外の複数の撮像装置それぞれによって撮影された複数の画像各々に写像した第２直線上において、前記物体の存在範囲を表す線分を生成し、
前記複数の画像それぞれから生成された複数の線分各々について、前記画像内における前記線分の一方の端点の座標を、前記一方の端点の座標と他方の端点の座標との差分に変換し、
前記他方の端点の座標と前記差分とを記憶部に記憶させ、
前記記憶部が記憶する前記他方の端点の座標と前記差分とから、前記一方の端点の座標を復元し、
前記他方の端点の座標と復元した前記一方の端点の座標とを、前記投影面の奥行き方向に写像した結果に基づいて、前記複数の線分の間における前記奥行き方向の重複判定を行う、
処理をコンピュータに実行させるためのプログラム。
（付記７）
前記コンピュータは、前記３次元空間内の点を前記複数の画像各々に写像する写像情報を用いて、前記画像の水平方向の座標と前記画像の垂直方向の座標とによって記述される前記第２直線の方程式を求め、
前記記憶部が記憶する前記他方の端点の座標は、前記水平方向の座標又は前記垂直方向の座標のうちいずれか一方に対応する第１座標であり、前記記憶部が記憶する前記差分は、前記第１座標の差分であり、
前記コンピュータは、前記記憶部が記憶する前記他方の端点の前記第１座標と前記第１座標の差分とから、前記一方の端点の前記第１座標を復元し、前記第２直線の方程式を用いて、前記他方の端点の前記第１座標から、前記水平方向の座標又は前記垂直方向の座標のうち前記第１座標とは異なる第２座標を求め、前記第２直線の方程式を用いて、前記一方の端点の前記第１座標から前記一方の端点の前記第２座標を求め、前記他方の端点の前記第１座標及び前記第２座標と、前記一方の端点の前記第１座標及び前記第２座標とを、前記奥行き方向に写像することを特徴とする付記６記載のプログラム。
（付記８）
前記一方の端点と前記他方の端点との間における前記第１座標の差分は、前記一方の端点と前記他方の端点との間における前記第２座標の差分よりも大きく、前記他方の端点の前記第１座標は整数型変数であり、前記第１座標の差分は整数型変数であることを特徴とする付記６又は７記載のプログラム。
（付記９）
前記コンピュータは、前記他方の端点の前記第１座標を表す整数型変数のビット幅を、前記他方の端点の前記第１座標の値に基づいて決定し、前記第１座標の差分を表す整数型変数のビット幅を、前記第１座標の差分の値に基づいて決定することを特徴とする付記８記載のプログラム。
（付記１０）
前記コンピュータは、
前記第２直線上において、前記物体の存在範囲を表す線分である第１線分を生成するとともに、前記物体を含む１つ又は複数の物体の存在範囲を表す複数の第２線分を生成し、
前記複数の第２線分各々の端点の座標を、前記複数の第２線分各々の端点の座標と、前記複数の第２線分各々の他の端点の座標又は他の第２線分の端点の座標又は前記第１線分の一方の端点の座標との差分に変換し、
前記複数の線分各々の端点の座標から生成された差分を、前記記憶部にさらに記憶させ、
前記複数の線分各々の端点の座標から生成された差分から、前記複数の線分各々の端点の座標を復元し、
復元した前記複数の線分各々の端点の座標を、前記奥行き方向に写像し、
前記複数の画像それぞれから生成された複数の線分の間における前記奥行き方向の重複判定を行うことを特徴とする付記６乃至９のいずれか１項に記載のプログラム。
（付記１１）
コンピュータが、
３次元空間内における撮像装置の投影中心と、前記撮像装置の投影面内において物体を表す点とを通る第１直線を、前記撮像装置以外の複数の撮像装置それぞれによって撮影された複数の画像各々に写像した第２直線上において、前記物体の存在範囲を表す線分を生成し、
前記複数の画像それぞれから生成された複数の線分各々について、前記画像内における前記線分の一方の端点の座標を、前記一方の端点の座標と他方の端点の座標との差分に変換し、
前記他方の端点の座標と前記差分とを記憶部に記憶させ、
前記記憶部が記憶する前記他方の端点の座標と前記差分とから、前記一方の端点の座標を復元し、
前記他方の端点の座標と復元した前記一方の端点の座標とを、前記投影面の奥行き方向に写像した結果に基づいて、前記複数の線分の間における前記奥行き方向の重複判定を行う、
ことを特徴とする情報処理方法。
（付記１２）
前記コンピュータは、前記３次元空間内の点を前記複数の画像各々に写像する写像情報を用いて、前記画像の水平方向の座標と前記画像の垂直方向の座標とによって記述される前記第２直線の方程式を求め、
前記記憶部が記憶する前記他方の端点の座標は、前記水平方向の座標又は前記垂直方向の座標のうちいずれか一方に対応する第１座標であり、前記記憶部が記憶する前記差分は、前記第１座標の差分であり、
前記コンピュータは、前記記憶部が記憶する前記他方の端点の前記第１座標と前記第１座標の差分とから、前記一方の端点の前記第１座標を復元し、前記第２直線の方程式を用いて、前記他方の端点の前記第１座標から、前記水平方向の座標又は前記垂直方向の座標のうち前記第１座標とは異なる第２座標を求め、前記第２直線の方程式を用いて、前記一方の端点の前記第１座標から前記一方の端点の前記第２座標を求め、前記他方の端点の前記第１座標及び前記第２座標と、前記一方の端点の前記第１座標及び前記第２座標とを、前記奥行き方向に写像することを特徴とする付記１１記載の情報処理方法。
（付記１３）
前記一方の端点と前記他方の端点との間における前記第１座標の差分は、前記一方の端点と前記他方の端点との間における前記第２座標の差分よりも大きく、前記他方の端点の前記第１座標は整数型変数であり、前記第１座標の差分は整数型変数であることを特徴とする付記１１又は１２記載の情報処理方法。
（付記１４）
前記コンピュータは、前記他方の端点の前記第１座標を表す整数型変数のビット幅を、前記他方の端点の前記第１座標の値に基づいて決定し、前記第１座標の差分を表す整数型変数のビット幅を、前記第１座標の差分の値に基づいて決定することを特徴とする付記１３記載の情報処理方法。
（付記１５）
前記コンピュータは、
前記第２直線上において、前記物体の存在範囲を表す線分である第１線分を生成するとともに、前記物体を含む１つ又は複数の物体の存在範囲を表す複数の第２線分を生成し、
前記複数の第２線分各々の端点の座標を、前記複数の第２線分各々の端点の座標と、前記複数の第２線分各々の他の端点の座標又は他の第２線分の端点の座標又は前記第１線分の一方の端点の座標との差分に変換し、
前記複数の線分各々の端点の座標から生成された差分を、前記記憶部にさらに記憶させ、
前記複数の線分各々の端点の座標から生成された差分から、前記複数の線分各々の端点の座標を復元し、
復元した前記複数の線分各々の端点の座標を、前記奥行き方向に写像し、
前記複数の画像それぞれから生成された複数の線分の間における前記奥行き方向の重複判定を行うことを特徴とする付記１１乃至１４のいずれか１項に記載の情報処理方法。
【符号の説明】
【０２６８】
１０１、１０２  投影面
１０３  エピポーラ面
１１１、１１３  直線
１１２、６０２−０〜６０２−２、１２０１、１４０１、１４０２、２５０１  エピポーラ線
３０１、３０２  シルエット
３１１、３１２、５０１−０〜５０１−Ｍ、１２０２、１２０３、１４１１、１４１２、１４３１、１４３２  線分
３２１、３２２  シルエットコーン
４０１、２８０１、２８０２  物体
５０２、７０１、１６０３  範囲
６０１−０〜６０１−２  マスク画像
８０１  ３次元形状構築部
８１１、１７０２  線分探索部
８１２  重複判定部
８１３、１０１３、１２１１  記憶部
９０１、３４０１、３５１１、３６１１  演算回路
９０２  ローカルメモリ
９０３  オフチップメモリ
１００１  情報処理装置
１０１１  生成部
１０１２  変換部
１０１４  復元部
１０１５  判定部
１４２１、１４２２、１４４１、１４４２  端点
１６０１  矢印
１６０２  位置
１７０１  写像情報生成部
２５１１〜２５１３  物体領域
２７０１−１〜２７０１−Ｎ  カメラ
２７０２−１〜２７０２−Ｎ  前景分離処理
２７０３〜２７０３−Ｎ  VisualHull処理
２７０４  レンダリング処理
２８１１、２８１２  視点
２８２１、２８２２  画像
２９０１  自由視点映像装置
２９１１  映像取得部
２９１２  前景分離部
２９１３  VisualHull部
２９１４  レンダリング部
３３０１  情報処理装置
３３０２  表示装置
３３０３  入力装置
３３１１、３４０４、３６０３  メモリ
３３１２  ハードディスクドライブ
３３１３  ネットワークインタフェース
３３１４  演算部
３３１５  媒体駆動装置
３３１６  バス
３３１７  可搬型記録媒体
３４０２、３５１３、３６１３  シェアードメモリ
３４０３、３５１４、３６１４  キャッシュメモリ
３５０１  ＣＰＵ
３５１２、３６１２  レジスタ
３５２１、３６２１  チップ内バス
３５２２、３６２２  チップ間接続バス
３６０１  ボード
３６２３  拡張バス
【図１】
2019114201.tif 000003
【図２】
2019114201.tif 000004
【図３】
2019114201.tif 000005
【図４】
2019114201.tif 000006
【図５】
2019114201.tif 000007
【図６】
2019114201.tif 000008
【図７】
2019114201.tif 000009
【図８】
2019114201.tif 000010
【図９】
2019114201.tif 000011
【図１０】
2019114201.tif 000012
【図１１】
2019114201.tif 000013
【図１２】
2019114201.tif 000014
【図１３】
2019114201.tif 000015
【図１４】
2019114201.tif 000016
【図１５】
2019114201.tif 000017
【図１６】
2019114201.tif 000018
【図１７】
2019114201.tif 000019
【図１８】
2019114201.tif 000020
【図１９】
2019114201.tif 000021
【図２０】
2019114201.tif 000022
【図２１】
2019114201.tif 000023
【図２２】
2019114201.tif 000024
【図２３Ａ】
2019114201.tif 000025
【図２３Ｂ】
2019114201.tif 000026
【図２４】
2019114201.tif 000027
【図２５】
2019114201.tif 000028
【図２６】
2019114201.tif 000029
【図２７】
2019114201.tif 000030
【図２８】
2019114201.tif 000031
【図２９】
2019114201.tif 000032
【図３０】
2019114201.tif 000033
【図３１】
2019114201.tif 000034
【図３２】
2019114201.tif 000035
【図３３】
2019114201.tif 000036
【図３４】
2019114201.tif 000037
【図３５】
2019114201.tif 000038
【図３６】
2019114201.tif 000039