(57)【要約】【課題】シルエットコーンを導出する際のエピポーラ線とシルエットの交わる線分の探索処理を高速化する。【解決手段】情報処理装置は、変換部と、検出部と、探索部とを備える。変換部は、基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づくシルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換する。検出部は、今回取得したシルエット存在位置情報と、前回取得したシルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出する。探索部は、シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う。【選択図】図１
2019117580.tif 000002
【特許請求の範囲】
【請求項１】
基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換する変換部と、
今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出する検出部と、
前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う探索部と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記検出部は、前記シルエット不存在範囲を累積し、累積された前記シルエット不存在範囲と今回取得される前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、前記シルエット不存在範囲を検出し、
前記探索部は、前記シルエット不存在範囲に基づいて、前記シルエットの存在する範囲の探索を行う
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記検出部は、パイプライン処理により、新たに取得したシルエット存在位置情報が既存の前記シルエット不存在範囲に重複しているか否かにより前記シルエット不存在範囲を検出し、検出結果に応じて検出された前記シルエット不存在範囲を該既存の前記シルエット不存在範囲に追加する
ことを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
前記検出部は、複数の前記シルエット存在位置情報のすべてで前記シルエットが存在する範囲のうちの、前記基準撮像装置の視点から最も近い前記範囲の端部よりも前記視点側となる範囲、及び前記基準撮像装置の視点から最も遠い前記範囲の端部よりも前記視点から遠方側となる範囲を、前記シルエット不存在範囲として検出する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項５】
前記検出部は、複数の前記シルエット存在位置情報のすべてで前記シルエットが存在する範囲のうちの、前記基準撮像装置の視点から最も近い前記範囲の端部と前記基準撮像装置の視点から最も遠い前記範囲の端部との間に、前記シルエットが存在しない範囲が含まれる場合に、該シルエットが存在しない範囲を前記シルエット不存在範囲として検出する
ことを特徴とする請求項４に記載の情報処理装置。
【請求項６】
コンピュータに、
基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換し、
今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出し、
前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う、
処理を実行させることを特徴とするプログラム。
【請求項７】
コンピュータが、
基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換し、
今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出し、
前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う、
処理を実行することを特徴とする情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、プログラム、及び情報処理方法に関する。
【背景技術】
【０００２】
計測対象である物体の２次元情報を取得し、その２次元情報に基づいて、物体の３次元情報を推定する画像処理技術がある。
【０００３】
第１の技術として、例えば、計測対象から取得した２つの画像間のマッチング演算を行う際に、高精度のマッチング結果を短時間で得ることができる画像処理技術がある（例えば、特許文献１）。第１の技術では、Dynamic Programming（ＤＰ）マッチングを用いたステレオ計測において、フレーム間で対応する画素の輝度値に変化がない領域については、前のフレームにおける経路探索結果を継承する。また、１つのフレーム処理において、隣接する走査線間で対応する画素の輝度値に変化がない領域については、１つ前の走査線における経路探索結果を継承する。
【０００４】
第２の技術として、例えば、第２画像のエピポーララインの上で対象物の特徴点を探索する際の誤検出の防止を図り、第１カメラから対象物までの距離を精度良く算出する技術がある（例えば、特許文献２）。第２の技術では、画像処理装置は、主カメラによりワークを撮像した第１画像と、主カメラと異なる視線を有する従カメラでワークを撮像した第２画像とを取得する。そして、画像処理装置は、第２画像のエピポーララインの上を探索することで第２画像の上におけるワークの特徴点を特定し、ステレオ法によりワークまでの距離を算出する。この際、画像処理装置は、予め記憶装置に記憶されたワークの特徴量の画素数及びそのワークとの距離に基づき、第１画像におけるワークの特徴量の画素数から主カメラとワークとの距離の概略値を算出する。そして、画像処理装置は、距離の概略値に応じて、第２画像のエピポーララインの上でワークの特徴点を探索する際の探索範囲を狭めるように設定する。
【０００５】
第３の技術として、例えば、道路周辺の地物の位置を計測する技術がある（例えば、特許文献３）。第３の技術では、画像記憶部に道路周辺を撮影した画像が記憶されている。また、３次元点群モデル記憶部には画像の撮影と同時に行われたレーザ計測により得られた３次元座標を示す点群が路面形状モデルとして記憶されている。モデル投影部は点群を画像に投影し、画像表示部は画像と点群とを重ね合わせて表示装置に表示する。画像点入力部は計測対象の地物上の画素を計測画像点として入力する。近傍抽出部は、計測画像点の近傍に位置し、計測対象の地物に重なっている点を点群から抽出する。地物位置算出部は、抽出された点が示す３次元座標を、計測対象の地物の３次元座標として出力する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−３３１１０８号公報
【特許文献２】特開２０１３−２５７２８９号公報
【特許文献３】特開２００９−７５１１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
物体の２次元情報に基づいて該物体の３次元形状を復元する技術として、視体積交差法により多視点映像の物体シルエット画像から物体の３次元形状を復元する技術(VisualHull)がある。この種の技術では、視体積（シルエットコーン）を導出する処理においてエピポーラ線とシルエットの交わる線分を探索する際の演算量が大きい。また、エピポーラ線とシルエットの交わる線分を探索する際に、エピポーラ線のうちのシルエットが交わらない区間も探索範囲に含めているため、探索処理における演算量が大きくなり、処理時間が増大する。
【０００８】
１つの側面では、本発明は、シルエットコーンを導出する際のエピポーラ線とシルエットの交わる線分の探索処理の高速化を目的とする。
【課題を解決するための手段】
【０００９】
１つの態様の情報処理装置は、変換部と、検出部と、探索部とを備える。変換部は、基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づくシルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換する。検出部は、今回取得したシルエット存在位置情報と、前回取得したシルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出する。探索部は、シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う。
【発明の効果】
【００１０】
上述の態様によれば、シルエットコーンを導出する際のエピポーラ線とシルエットの交わる線分の探索処理の高速化が可能となる。
【図面の簡単な説明】
【００１１】
【図１】本実施形態における情報処理装置の一例を示す図である。
【図２】エピポーラ幾何を説明する図である。
【図３】視体積について説明する図である。
【図４】線分探索の範囲について説明するための図である。
【図５】本実施形態における先に処理した参照Viewの線分重複範囲の最大depth,最小depthで後続する参照Viewの線分探索範囲を狭めることを説明する図である。
【図６】本実施形態における３次元形状復元装置の一例を示す図である。
【図７】VisualHull部の構成を示す図である。
【図８】本実施形態における線分探索の処理フローを示す図である。
【図９】線分重複検査部及び座標変換部によるdepth決定及び線分探索範囲制限の処理フローを示す図である。
【図１０Ａ】本実施形態におけるVisualHullの処理フローを示す図（その１）である。
【図１０Ｂ】本実施形態におけるVisualHullの処理フローを示す図（その２）である。
【図１１】パイプライン処理における線分重複検査処理開始タイミングを説明する図である。
【図１２】本実施形態における視野、参照Viewからの見え方、線分端探索範囲を説明するための図である。
【図１３】本実施形態におけるソート後の線分端情報格納領域を説明するための図である。
【図１４】本実施形態における画面端の関係を説明する図である。
【図１５】本実施形態におけるNearサブ線分端情報領域を説明するための図である。
【図１６】本実施形態におけるNearサブ線分端情報領域と、重複度をnear→far用とfar→near用に分けて持つ方法を説明する図である。
【図１７】本実施形態における対象View(tid)のzNear,zFarと各参照Viewの画像端（Ev1(id),Ev2(id)）の関係処理を説明する図である。
【図１８】本実施形態における参照Viewの2D座標におけるエピポーラ線の導出方法について説明する図である。
【図１９】本実施形態における参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換する方法を説明する図である。
【図２０】本実施形態における線分端重複検査処理を説明する図である。
【図２１】本実施形態における不要な線分端探索範囲を説明する図である。
【図２２】線分重複検査処理をnearからfar方向へ実施する処理の内容を説明する図である。
【図２３】線分重複検査処理をfarからnear方向へ実施する処理の内容を説明する図である。
【図２４】本実施形態におけるNearサブ領域処理、Core領域処理, Farサブ領域処理を説明する図である。
【図２５】図２２、図２３のNearサブ領域処理、Core領域処理、Farサブ領域処理のフローを示す図である。
【図２６】対象Viewに対して参照Viewを１つごとに都度処理しつつ線分探索の範囲を削減することにより各性能ネック要因の削減となることを説明する図である。
【図２７】本実施形態におけるすべてのデータがそろってから処理を行う場合と、都度データごと処理を行う場合を説明する図である。
【図２８】本実施形態におけるハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１２】
図１は、本実施形態における情報処理装置の一例を示す図である。図１のように、情報処理装置１０１は、変換部１０２、検出部１０３、探索部１０４、及び記憶部１０５を含む。
【００１３】
変換部１０２は、基準撮像装置（基準カメラ）が撮像するシルエットを該基準撮像装置とは異なる視点から撮影する複数の参照撮像装置（参照カメラ）のそれぞれから、順次、シルエット存在位置情報を取得して共通の座標系に変換する。シルエット存在位置情報は、参照撮像装置に基づくシルエットの存在位置を示す情報である。変換部１０２の一例としては、z座標→参照[F]ローカル座標算出部１６（図７参照）が挙げられる。
【００１４】
検出部１０３は、今回取得したシルエット存在位置情報と、前回取得したシルエット存在位置情報との比較を行う。前回取得したシルエット存在位置情報は、例えば、記憶部１０５に記憶させておく。検出部１０３は、比較の結果に基づいて、シルエットの存在しない範囲を示すシルエット不存在範囲を検出する。検出部１０３の一例としては、線分重複検査部１８（図７参照）が挙げられる。
【００１５】
探索部１０４は、シルエット不存在範囲に基づいて、シルエットの存在する範囲の探索を行う。探索部１０４の一例としては、探索範囲決定部１４及び線分探索部１５（図７参照）が挙げられる。
【００１６】
このように構成することにより、本実施形態の情報処理装置１０１では、視体積交差法により多視点映像から物体の３次元形状を復元するためのシルエットコーンを導出する際の、エピポーラ線とシルエットの交わる線分の探索処理の高速化を図ることが可能となる。
【００１７】
検出部１０３は、シルエット不存在範囲を累積し、累積されたシルエット不存在範囲と今回取得されるシルエット存在位置情報との比較を行い、比較の結果に基づいて、シルエット不存在範囲を検出する。当該処理は、Central Processing unit（ＣＰＵ）２２（図２８参照）に実行されるＳ１１（図８参照），及びＳ２４〜Ｓ２６（図９参照）の処理に該当する。また、探索部１０４は、上記のように、シルエット不存在範囲に基づいて、シルエットの存在する範囲の探索を行う。当該処理は、ＣＰＵ２２に実行されるＳ１０（図８参照）の処理に該当する。
【００１８】
このように構成することにより、本実施形態の情報処理装置１０１が行う線分の探索処理では、求めた線分探索の範囲のうち不要な範囲を、次回他の参照撮像装置より取得したシルエット存在位置情報に基づく線分探索に反映することが可能となる。
【００１９】
検出部１０３は、パイプライン処理により、新たに取得したシルエット存在位置情報が既存のシルエット不存在範囲に重複しているか否かによりシルエット不存在範囲を検出してもよい。この場合、検出部１０３は、検出結果に応じて検出されたシルエット不存在範囲を既存のシルエット不存在範囲に追加する。
【００２０】
このように構成することにより、本実施形態の情報処理装置１では、線分探索については、パイプライン処理により探索不要な範囲を段階的に追加して探索範囲を狭めてゆくことが可能となる。
【００２１】
以下では、本実施形態について詳述する。
図２は、エピポーラ幾何を説明する図である。エピポーラ幾何とは、２つの異なる視点の画像から該画像内の物体についての３次元空間内での奥行情報を復元するための幾何である。
【００２２】
図２の点OL及び点ORは、それぞれ、Lカメラ（基準カメラ）の投影中心、及びRカメラ（参照カメラ）の投影中心である。また、図２の点XL及び点XRは、それぞれ、３次元空間（実空間）内の点Xを、Lカメラの投影面６０及びRカメラの投影面６１に投影した点（シルエット）である。
【００２３】
２つのカメラは異なる３次元位置にあるので、一方のカメラから他方のカメラを見ることができる。図２の点eL及び点eRは、それぞれ、エピポール（epipole）又はエピポーラ点（epipolar point）と呼ばれる点であり、互いのカメラ（投影中心）を自カメラの投影面に投影した点である。すなわち、Lカメラの投影面６０における点eLはRカメラの投影中心ORを投影面６０に投影した点であり、Rカメラの投影面６１における点eRはLカメラの投影中心OLを投影面６１に投影した点である。ここで、投影中心（点OL及び点OR）とエピポール（点eL及び点eR）とは、３次元空間内の同一直線上に存在する。
【００２４】
図２においてRカメラの投影面６１を通る直線５０は、エピポーラ線と呼ばれる直線であり、点OLと点Xとを通る直線をRカメラの投影面６１に投影した直線である。
【００２５】
Lカメラを基準カメラとし、Rカメラを参照カメラとした場合、Lカメラの投影面６０における点XLと対応する３次元空間内の点は、点OLと点Xとを通る直線上に存在する。また、Lカメラの投影面６０における点XLと対応する３次元空間内の点は、Rカメラの投影面６１では、エピポーラ線５０上に存在する。例えば、Lカメラの投影面６０における点XLと対応する３次元空間内の点が点Xである場合、該点Xは、Rカメラの投影面６１のうち、投影中心ORと点Xとを結ぶ線分とエピポーラ線５０との交点に投影される。
【００２６】
２つのカメラの位置関係が既知であれば、エピポーラ制約として以下が成り立つ。すなわち、点XのLカメラの投影面６０における点XLが与えられると、Rカメラの投影面６１における線分eR-XRが定義される。点XのRカメラの投影面６１における点XRはエピポーラ線５０上に存在する。また、例えば、Lカメラの投影面６０における点XLと対応する３次元位置が点X１である場合、Rカメラの投影面６１上で点X１と対応する点は、投影中心OLと点X１とを結ぶ線分と、エピポーラ線５０との交点となる。同様に、Lカメラの投影面６０における点XLと対応する３次元位置が点X２又はX３である場合、Rカメラの投影面６１上で点X２又はX３と対応する点は、それぞれ、投影中心OLと点X２又はX３とを結ぶ線分と、エピポーラ線５０との交点となる。
【００２７】
このように、２つのカメラで同じ点を捕捉している場合、その点は必ず互いのエピポーラ線上に存在する。すなわち、一方の投影面における点が他方の投影面を通るエピポーラ線上に存在しない場合には、同じ点を捕捉していない（対応づけが正しくない）。よって、一方のカメラで見ている点が他方のカメラのどこに映っているかは、エピポーラ線上を調べれば十分である。対応づけが正しく、点XL及び点XRの位置が分かっていれば、点Xの３次元空間での位置を三角法により決定することができる。本実施形態の情報処理装置１では、上記のエピポーラ制約に基づいた視体積交差法により多視点映像から物体の３次元形状を復元する。
【００２８】
図３は、視体積について説明する図である。図３の（ａ）における点zNear及び点zFarは、Rカメラの投影面６１を通るエピポーラ線５０上における視野範囲の両端を示す点である。点zNearはエピポーラ線５０上におけるエピポール（点eR）から一番近い点を示し、点zFarはエピポーラ線５０上におけるエピポール（ここでは点eR）から一番遠い点を示す。また、図３の画面端Nearは、エピポーラ線５０上における点zNear側の投影面６１の端を示す。また、図３の画面端Farは、エピポーラ線５０上における点zFar側の投影面６１の端を示す。
【００２９】
視体積交差法では、エピポーラ線５０上のうちのMax(zNear,画面端Near)〜Min(zFar,画面端Far)の範囲でシルエット(点X)の存在有無を確認する線分探索（交点探索）を行う。ここで、Max(zNear,画面端Near)は点zNearと画面端NearのうちエピポールeRから遠いほうの点を示し、Min(zFar,画面端Far)は、点zFarと画面端FarのうちエピポールeRに近いほうの点を示す。
【００３０】
探索する線分は、Lカメラの視点（投影中心OL）から見た物体表面を示す線分と、その背景を示す線分とを含む。線分探索により得られた線分（２次元シルエット）を投影中心ORに基づいて３次元空間に逆投影すると、図３の（ｂ）のように、投影中心ORを頂点とする錐体（シルエットコーン）が得られる。視体積交差法では、３次元空間内における複数の画像から得た同一物体についてのシルエットコーンの交差積（Visual Hull）に基づいて、物体の３次元形状を復元する。この場合、エピポーラ線５０上における線分端が３次元物体の表面の候補となり得る。
【００３１】
ここで、参照カメラF(F=0...参照カメラ数-1)についてMax(zNear,画面端Near)〜Min(zFar, 画面端Far)の範囲で線分探索をする場合を考えてみる。
【００３２】
図４は、線分探索の範囲について説明するための図である。
図４には、３つの参照View（V0，V1，及びV2）のそれぞれについての線分探索の結果を、ｚ座標を共通化して示している。３つの参照Viewから物体のｚ座標を算出する場合、３つの線分についての論理積において１となる線分範囲に物体が存在するといえる。ここで、図４の線分探索の結果における太い実線が物体の存在する範囲を示している場合、３つの参照View（V0，V1，及びV2）のすべてで太い実線となっている区間Ａ１及びＡ２が、物体のｚ座標の候補となる。すなわち、図４の例では、区間Ａ１及びＡ２を除く他の区間は、参照Viewが増えても線分の論理積は０となるため、物体のｚ座標の候補となることはない。論理積が０となる範囲も探索範囲に含まれる場合、探索処理におけるメモリアクセスの回数及び演算量が大きくなり、線分情報を格納しておくためのメモリサイズが大きくなる。線分端の大小関係を比較する処理はソート処理で行われる。すなわち、すべてのViewの線分で重なる箇所を探したいという目的に対して線分探索処理が過剰といえる。
【００３３】
そこで、本実施形態では、視体積交差法により多視点映像の物体シルエット画像から物体の３次元形状を復元する際の線分探索処理において、線分探索の範囲を少なくすることにより、線分探索のメモリアクセスと演算量を削減する。例えば、図４では、他の参照Viewについての線分探索は、区間Ａ１及びＡ２を含む区間Ａを探索範囲として線分探索を行えば十分であるため、探索範囲を狭めてメモリアクセスの回数及び演算量を削減することが可能である。また、本実施形態では、線分情報を格納するメモリ領域を削減する。更に、本実施形態では、線分重複確認の対象となる線分数を削減して演算量を削減する。
【００３４】
図５は、本実施形態における先に処理した参照Viewの線分重複範囲の最大depth,最小depthで後続する参照Viewの線分探索範囲を狭めることを説明する図である。
【００３５】
図５にあるように、本実施形態では、線分の重なりを確認しなくてもよい範囲を探索範囲から除外する。なお、図５では、論理積が１となる区間Ａ１及びＡ２を含み、かつ探索する範囲が最小となる１個の区間Ａを、探索する意味のある範囲としている。すなわち、図５において探索する意味のある範囲とした区間Ａには、実際には探索しなくてもよい区間が含まれる。このため、例えば、図５の参照View（V0，V1，及びV2）とは異なる参照Viewについての探索範囲を設定する際には、区間Ａの一端（最大depth）と他端（最小depth）との間となる区間のみを探索すればよい。最大depthは区間Ａのうちエピポールから遠いほうの端であり、最小depthは区間Ａのうちエピポールに近いほうの端である。これにより、後続の参照Viewに対する線分探索の範囲を狭めることが可能となり、探索処理におけるメモリアクセスの回数及び演算量を低減すること、並びに線分情報を格納しておくためのメモリサイズを小さくすることが可能となる。
【００３６】
図６は、本実施形態における３次元形状復元装置の一例を示す図である。
図６のように、３次元形状復元装置１は、視点画像生成部２、シルエット画像分離部３、パラメタ（パラメータ）生成部４、VisualHull部５、及びレンダリング部６を含む。
【００３７】
視点画像生成部２は、異なる複数の視点から撮影された画像（視点画像）を生成するか、又は外部から取得する。
【００３８】
シルエット画像分離部３は、視点画像生成部２で生成された視点画像から物体（被写体）のシルエット画像を分離する。
【００３９】
パラメタ生成部４は、カメラパラメタ（光学パラメタ[0..N-1]、位置パラメタ[0..N-1]を含む。）を取得して、各種パラメタ（変換情報）を生成する。
【００４０】
VisualHull部５は、基準カメラ（対象カメラ）で撮影されたシルエット画像と、参照カメラで撮影されたシルエット画像をシルエット画像分離部３から取得する。また、VisualHull部５は、対象カメラを特定するＩＤ（対象カメラＩＤ（ＴＩＤ））と、参照カメラを特定するＩＤ（参照カメラＩＤ（ＲＩＤ））を取得する。また、VisualHull部５は、パラメタ生成部４で生成された変換情報を取得する。VisualHull部５は、TID、RID、変換情報、シルエット画像[TID,RID]からdepth情報を算出する。
【００４１】
レンダリング部６は、カメラパラメタ（光学パラメタ[0..N-1]、位置パラメタ[0..N-1]）、VisualHull部５が算出したdepth情報、シルエット画像分離部３が生成した非シルエット画像情報、及び視点画像生成部２が出力した視点画像[0..N-1]、並びに指定視点位置を取得する。レンダリング部６は、取得した情報に基づいて、指定視点位置から見た物体の３次元画像を生成する。
【００４２】
図７は、VisualHull部の構成を示す図である。
図７のように、VisualHull部５は、ワールド座標→参照ローカル座標部１１、エピポーラ線傾き導出部１２、画面範囲導出部１３、探索範囲決定部１４、線分探索部１５を含む。VisualHull部５は、更に、z座標→参照[F]ローカル座標変換部１６、参照ローカル座標→z座標変換部１７、線分バッファ[n]１８、及び線分重複検査部１９を含む。
【００４３】
図８は、本実施形態における線分探索の処理フローを示す図である。以下では、図７を参照しながら、図８について説明する。
【００４４】
線分探索処理では、まず、対象View(T)が選択される（ステップS1）。ここで、“T”は、複数のカメラのうち対象カメラ（基準カメラ）とするカメラを指定する情報である。
【００４５】
次に、ワールド座標→参照ローカル座標変換部１１が、ワールド座標を参照ローカル座標に変換する。すなわち、ワールド座標→参照ローカル座標変換部１１は、変換情報Aを用いて、エピポール(T)、ZNear(T)、ｚFar(T)の座標を、エピポール(T)[F](x,y)、zNear(T)[F](x,y)、ｚFar(T)[F](x,y)に変換する（ステップS2）。ここで、“F”は、参照カメラを特定する情報である（F=0、１，２、・・・・，参照カメラ数−１）。［ｎ］は対象Viewのシルエット点(x,y)を特定する情報である。
【００４６】
次に、対象View(T)以外のViewのなかから参照View(F)が選択される（ステップS3）。その後、対象Viewのシルエット点（T）[n](X,Y)が選択される（ステップS4）。
【００４７】
次に、エピポーラ線傾き導出部１２が、対象Viewのシルエット点(T)[n](X,Y)と、エピポール(T)[F](x,y)と、変換情報Bから、エピポーラ線の傾き[n][F]を導出する（ステップS5）。
【００４８】
次に、画面範囲導出部１３が、参照Viewの画面範囲情報[F]と、エピポーラ線の傾き[n][F]と、エピポール(T)[F](x,y)から、画面端Near(n)[F](x,y)、画面端Far(n)[F](x,y)を導出する（ステップS6）。
【００４９】
その後、例えば、探索範囲決定部１４が、探索範囲を決定するため、参照Viewが２つ以上処理されているか否かを判定する（ステップS7）。言い換えると、ステップS7では、対象Viewに選択されているViewを除く、他のViewのうちの、２つ以上のViewに対して線分探索の処理が行われたか否かを判定する。
【００５０】
参照Viewが２つ以上処理されていない場合（ステップS7；No）、探索範囲決定部１４は、Max（zNear(T)[F](x,y),画面端Near[n][F](x,y)）を探索開始[n][F](x,y)に代入する。また、探索範囲決定部１４は、Min(zFar(T)[F](x,y),画面端Far[n][F](x,y))を探索終了[n][F](x,y)に代入する（ステップS8）。
【００５１】
一方、参照Viewが２つ以上処理されている場合（ステップS7；Yes）、探索範囲決定部１４は、Max（zNear(T)[F](x,y)、画面端Near[n][F](x,y),最小[F](x,y)）を探索開始[n][F](x,y)に代入する。また、探索範囲決定部１４は、Min(zFar(T)[F](x,y),画面端Far[n][F](x,y),最大[F](x,y))を探索終了[n][F](x,y)に代入する（ステップS9）。
【００５２】
ステップS8又はS9の処理の後、線分探索部１５は、シルエット画像R[F]、探索開始[n][F](x,y)、探索終了[n][F](x,y)、変換情報Cを用いて線分探索を行い、線分[n][F][m]（開始(x,y),終了(x,y)）を得る(ステップS10)。ここで、mは線分探索において検出された線分を識別するインデックスである。
【００５３】
次に、参照ローカル座標→z座標変換部１７が、線分[n][F][m]（開始(x,y),終了(x,y)）を参照ローカル座標からz座標へ変換し、線分[n][F][m]（開始(z),終了(z)）を得て、線分バッファ[n]１８に格納する(ステップS11)。
【００５４】
ステップS11の処理の後、VisualHull部５は、対象View(T)のシルエット画像すべてに対する処理を行ったか否かを判定する（ステップS12）。未処理のシルエット画像がある場合（ステップS12；No）、VisualHull部５は、ステップS4以降の処理を繰り返す。
【００５５】
対象View(T)のシルエット画像すべてに対する処理が済んだ場合（ステップS12；Yes）、VisualHull部５は、次に、参照View(F)のすべてに対する処理を行ったか否かを判定する（ステップS13）。未処理の参照View(F)がある場合（ステップS13；No）、VisualHull部５は、ステップS3以降の処理を繰り返す。
【００５６】
参照View(F)のすべてに対する処理が済んだ場合（ステップS13；Yes）、VisualHull部５は、次に、すべてのViewを対象View（T）としてステップS1以降の処理を行ったか否かを判定する（ステップS14）。対象View(T)に選択していないViewがある場合（ステップS14；No）、VisualHull部５は、ステップS1以降の処理を繰り返す。そして、すべてのViewを対象View（T）としてステップS1以降の処理を行うと、VisualHull部５は、現在処理の対象となっているViewの組に対する線分探索処理を終了する。
【００５７】
このように、本実施形態の３次元形状復元装置１（情報処理装置１０１）では、１個のViewが対象Viewに選択された状態での参照Viewに対する処理が１回目又は２回目である場合と、３回目以降である場合とで異なる探索範囲を設定する。しかも、参照Viewに対する処理が３回目以降である場合、VisualHull部５は、既に処理が済んでいる参照Viewにおける線分探索の結果で論理積が１となる区間を含む最小の区間Ａを、現在処理対象となっている参照Viewにおける探索範囲に設定する。したがって、本実施形態の三次元形状復元装置１（情報処理装置１０１）では、参照Viewに対する３回目以降の処理を効率よく行うことが可能となる。
【００５８】
次に、図９を参照して、線分重複検査部１９及びｚ座標→参照[F]ローカル座標変換部１６が行う処理について説明する。
【００５９】
図９は、線分重複検査部及び座標変換部によるdepth決定及び線分探索範囲制限の処理フローを示す図である。
【００６０】
線分重複検査部１９は、まず、シルエットｎ｜｜参照View（F）が変わったか否かを判定する（ステップS21）。シルエットｎ｜｜参照View（F）が変わっていない場合（ステップS21；No）、線分重複検査部１９は、定期又は不定期にステップS21の判定を繰り返す。そして、シルエットｎ｜｜参照View（F）が変わった場合（ステップS21；Yes）、線分重複検査部１９は、次に、シルエットｎの参照View(F)での線分探索が終了したかを判定する（S22）。線分探索が終了していない場合（ステップS22；No）、線分重複検査部１９は、定期又は不定期にステップS21の判定を繰り返す。そして、シルエットｎの参照View(F)での線分探索が終了した場合（ステップS22；Yes）、線分重複検査部１９は、次に、参照Viewのうちの２つ以上で線分探索処理がされているかを判定する（ステップS23）。２つ以上の参照Viewに対する線分探索処理がされていない場合（ステップS23；No）、線分重複検査部１９は、ステップS21の判定に戻る。一方、２つ以上の参照Viewに対する線分探索処理がされている場合（ステップS23；Yes）、線分重複検査部１９は、線分の重複するｚ座標の区間を導出する（ステップS24）。ステップS24において、線分重複検索１９は、先の導出した線分における重複するｚ座標の区間、線分[n][f-1][m]（開始(z),終了(z)）、線分[n][f-2][m]（開始(z),終了(z)）から、重複するｚ座標の区間を導出する。
【００６１】
次に、線分重複検査部１９は、線分重複するz座標の区間のうち最近線分の最近線端と線分重複するz座標の区間の最遠線端を、重複線端[n](最小(z),最大(z))とする（ステップS25）。
【００６２】
次に、z座標→参照[F]ローカル座標変換部１６が、重複線端[n](最小(z),最大(z))と、zNear(T)[F](x,y)、ｚFar(T)[F](x,y)から、参照View（F）での線分探索の制限値最小[F](x,y)、最大[F](x,y)を導出する（ステップS26）。
【００６３】
その後、線分重複検査部１９は、すべての参照Viewの線分重複検査を行ったか否かを判定する（ステップS27）。未処理の参照Viewがある場合（ステップS27;No）、線分重複検査部１９は、ステップＳ24以降の処理を繰り返す。そして、すべての参照Viewに対する処理を行った場合（ステップS27；Yes）、線分重複検査部１９は、線分重複するｚ座標の区間の最近線端ｚをdepth[n]とし（ステップS28）、処理を終了する。
【００６４】
このように本実施形態のVisualHull部５では、線分探索の処理フローと、depth決定及び線分探索範囲制限の処理フローとが、対象View、参照View、及びシルエット画素nの変化に応じて連動して行われる。VisualHull部５は、複数のViewのうちのある特定のViewを対象Viewとし、その他のViewを参照Viewとする処理を、複数のViewのそれぞれを対象Viewに設定して実行する。
【００６５】
なお、VisualHull部５は、線分重複検査において要求される必要な重複数に応じて、必ずしもすべてのViewを対象View、或いは参照Viewとせずに処理を切り上げてもよい。また、線分重複検査は、Viewの画面外の点を考慮した場合には、すべてのViewの線分の重複を検出する代わりに、閾値以上の線分の重複を検出としてもよい。
【００６６】
以下では、上述した本実施形態を更に詳述する。本実施形態の３次元形状復元装置１（情報処理装置１０１）において線分の探索範囲を狭めていく方法は、下記（１）及び（２）の２通りに大別される。
（１）探索範囲の左右端（両端）をつめていく方法。
（２）１個の探索範囲を、該探索範囲の途中（中間部分）に存在する論理積が０となる領域で分断し、探索範囲の左右端及び分断位置からそれぞれ左右につめていく方法。
【００６７】
なお、上記（１）の方法は（２）の方法のサブセットと捉えることができるため、以下では上記（２）について説明する。
【００６８】
図１０Ａは、本実施形態におけるVisualHullの処理フローを示す図（その１）である。図１０Ｂは、本実施形態におけるVisualHullの処理フローを示す図（その２）である。なお、図１０Ａ及び図１０Ｂの処理フローでは、ViewNumは全View数を表す変数であり、RemViewは残りの参照View数を表す変数であり、numViewは処理した参照View数を表す変数である。
【００６９】
VisualHull部５は、まず、図１０Ａのように、対象View（tid）を設定する（ステップS31）。
【００７０】
次に、VisualHull部５は、対象View(tid)の点ｚNear及び点zFarと各参照Viewの画面端（E1(iｄ)、E2(id)）との関係処理を行う（ステップS32）。次に、VisualHull部５は、id=0及びnumView=0と設定する（ステップS33）。
【００７１】
ステップS33の後、VisualHull部５は、idの値とtidの値とを比較する（ステップS34）。idとtidとが同じ場合（ステップS34；Yes）、VisualHull部５は、idをインクリメントし（ステップS41）、再度ステップS34の判定を行う。
【００７２】
一方、idとtidとが異なる場合（ステップS34；No）、VisualHull部５は、次に、numViewをインクリメントし（ステップS35）、ViewNum−numViewの値をRemViewに代入する（ステップS36）。
【００７３】
次に、VisualHull部５は、参照View[id]を設定し（ステップS37）、該参照View[id]におけるエピポーラ線[id]を導出する（ステップS38）。その後、VisualHull部５は、線分端探索[id]を行い（ステップS39）、線分端マージソートを行う（ステップS40）。
【００７４】
線分端マージソートを行った後、VisualHull部５は、図１０Ｂのように、RankTH-RemViewが0以上であるか否かを判定する（ステップS42）。RankTH-RemViewが0以上の場合（ステップS42；Yes）、VisualHull部５は、次に、RankTH-RemViewをRankTHCurに代入し（ステップS43）、線分重複検査処理を行う（ステップS44）。ステップS44の処理として、VisualHull部５は、例えば、図９のフローチャートに沿った処理（ステップS21〜S28）を行う。
【００７５】
ステップS43及びS44の処理を行うと、VisualHull部５は、次に、RemView!＝０であるか否かを判定する（ステップS45）。なお、ステップS42の判定においてRankTH-RemViewが0未満であった場合（ステップS42；No）、VisualHull部５は、ステップS43及びS44の処理を省略してステップS45の判定を行う。
【００７６】
RemView!＝０の場合（ステップS45；Yes）、VisualHull部５は、図１０ＡのステップS41の処理を行った後、ステップS34以降の処理を行う。一方、RemView!=0ではない場合（ステップS45；No）、VisualHull部５は、次に、前景画素のすべてが処理済みであるか否か判断する(ステップS46)。未処理の前景画素がある場合（ステップS46；No）、VisualHull部５は、次の前景画素に移動し（ステップS47）、ステップS32以降の処理を行う。前景画素のすべてが処理済みである場合（ステップS46；Yes）、VisualHull部５は、depthをDepthマップへ代入し（ステップS48）、処理を終了する。
【００７７】
次に、図１０Ａ及び図１０Ｂのフローチャートに沿った処理をパイプライン処理として行う場合の、線分重複検査処理（ステップS42）の開始タイミングについて説明する。
【００７８】
図１１は、パイプライン処理における線分重複検査処理開始タイミングを説明する図である。線分重複検査処理はRankTH-RemView≧0を満たすときに実行される。RankTH-RemView < 0の時の線分端探索による線分端情報は、線分端マージソートによりソート後の線分端情報格納領域に格納される。
【００７９】
RankTHは線分重複検査時に線分がRankTH分以上重なった線分端を物体の表面として検出するための値である。視体積交差法ではRankTHの値を参照View数とすることが理想である。ただし、カメラの設置条件により参照Viewからの視野に対象Viewのカメラが入らない場合や、VisualHull処理に入力されるシルエット画像（マスク画像）の精度を補正するためにRankTH<参照View数とすることがある。ここで、シルエット画像生成時に本来シルエット画素として検出されなければならない画素を検出できない場合は、シルエット画像の精度が悪くなる。このため、３次元形状復元装置１において図１０Ａ及び図１０Ｂの処理をパイプライン処理として行う場合、図１１のように、マージソート及び線分重複検査処理を開始できるタイミングはRankTH-RemViewとなる。
【００８０】
図１２は、本実施形態における視野、参照Viewからの見え方、線分端探索範囲を説明するための図である。対象Viewの前景画素１つに対してエピポーラ線上のシルエット画素（マスク画素）を探す処理(線分探索)を行った結果、参照View座標での線分端の点の位置x,y座標を得る。これらの点は3D（３次元）ワールド座標を経由して対象Viewの3Dローカル座標に変換される。変換された点はソート後の線分端情報格納領域にマージソートされる。このとき、参照View（id）の光学中心から見た線分端探索範囲は、図１２に例示した４通りのパターンのいずれかとなる。第１のパターンは、点Near，点Farがともに視野８０に入っているパターンである。第２のパターンは、点Nearは視野８０に入っておらず、点Farは視野８０に入っているパターンである。第３のパターンは、点Nearは視野８０に入っており、点Farは視野８０に入っていないパターンである。そして、第４のパターンは、点Near，点Farがともに視野８０に入っていないパターンである。
【００８１】
図１３は、本実施形態におけるソート後の線分端情報格納領域を説明するための図である。ソート後の線分端情報格納領域は、例えば以下のような実装とする。形式は実装によって別の形式でもよい。
【００８２】
Nearサブ線分端情報は、初期時は各Viewの処理を行う前に各Viewのエピポーラ線が交わる画面端Ev1[id]の対象Viewの3Dローカル座標におけるz座標の値E1[id].z、及び、ランクしきい値が格納される。ここで、対象Viewのあるシルエット画素（マスク画素）についてすべての参照View分の線分端探索と線分端重複処理を実行することで1単位となる。ランクしきい値については、後述する「対象View(tid)のzNear,zFarと各参照Viewの画面端(E1(id), E2(id))の関係処理」を参照されたい。
【００８３】
また、参照Viewの線分探索を行った際に得られるエピポーラ線と参照Viewのマスク画素との交点(線分端)のうち、次の情報がランクしきい値に格納される。すなわち、対象Viewの3Dローカル座標に変換した際にE1[id].zの最大値maxE1.z以下に変換される線分端のz座標値と、線分端が線分の開始点か終了点かを表す情報がランクしきい値に格納される。
【００８４】
Farサブ線分端情報は、初期時は各Viewの処理を行う前に各Viewのエピポーラ線が交わる画面端Ev2[id]の対象Viewの3Dローカル座標におけるz座標の値E2[id].z、及び、ランクしきい値が格納される。ランクしきい値については、後述する「対象View(tid)のzNear,zFarと各参照Viewの画面端(E1(id), E2(id))の関係処理」を参照されたい。
【００８５】
また、参照Viewの線分探索を行った際に得られるエピポーラ線と参照Viewのマスク画素との交点(線分端)のうち、次の情報がランクしきい値に格納される。すなわち、対象Viewの3Dローカル座標に変換した際にE2[id].zの最小値minE2.z以上に変換される線分端のz座標値と線分端が線分の開始点か終了点かを表す情報が、ランクしきい値に格納される。
【００８６】
Core線分端情報は、上記以外の参照Viewの線分探索を行った際に得られるエピポーラ線と参照Viewのマスク画素との交点(線分端)の対象Viewの3Dローカル座標に変換したz座標値と線分端が線分の開始点か終了点かを表す情報が、ランクしきい値に格納される。
【００８７】
なお、Near.z ≧maxE1.zの場合にはNearサブ線分端情報は要素数0となる。また、Far.z ≦minE2.zの場合にはNearサブ線分端情報は要素数0となる。
【００８８】
ここで、ランクしきい値に格納する値について、例えば以下のようにする。これは、領域分割時に分割点における現時点のランク値を保持する理由のためである。実装上の事項であり実装により別の方法を選択してもよい。
【００８９】
開始点：-(2*RankTH)
終了点：-(2*RankTH+1)
開始点+Rank保存：-(2*Rank)
終了点+Rank保存：-(2*Rank+1)
【００９０】
この場合、符号から、要素に格納されているものが開始点又は終了点なのか(この場合は負)、画面境界点なのか(この場合は正)を見分ける。また、分割点における現時点のランク値はRankTHを超えないので、負値の絶対値/2≧RankTHであれば開始点又は終了点が格納され、負値の絶対値/2<RankTHであれば開始点+Rank又は終了点+Rankであると見分ける。また、負値の絶対値が偶数であれば開始点、負値の絶対値が奇数であれば終了点と見分ける。
【００９１】
次に、対象View(tid)の点zNear,点zFarと各参照Viewの画面端(Ev1(id), Ev2(id))との関係処理（ステップS32）の内容について説明する。
【００９２】
図１４は、本実施形態における画面端の関係を説明する図である。
対象Viewの3D（３次元）ローカル座標系において、各参照Viewの画面端を対象Viewの3Dローカル座標系に写像した点のzNear.z側をE1.z[id], 各参照Viewの画面端を対象Viewの3Dローカル座標系に写像した点のzFar.z側をE2.z[id]とする。ここで、図１４の各座標系における斜線部分は、該当参照Viewの線分端探索では画面外となるため線分端探索が行われない。
【００９３】
本実施形態では、予めすべての参照ViewのE1.z[id]の最大値maxE1.zを求め、Near.z=max(zNear.z,zNear側制限)からmaxE1.zの範囲をNearサブ範囲と定義する。同様に、本実施形態では、zFar.z側について、予めすべての参照ViewのE2.z[id]の最小値minE2.zを求め、minE2.zからFar.z=min(zFar.z,zFar側制限)の範囲をFarサブ範囲と定義する。
【００９４】
また、予めすべての参照Viewについて、斜線部分をひとつの線分が存在すると考え、Nearサブ範囲では、予めすべての参照ViewのE1.z[id]についてソート処理を行いNearサブ線分端情報領域に格納する。同様に、Farサブ範囲では、予めすべての参照ViewのE2.z[id]についてソート処理を行いFarサブ線分端情報領域に格納する。このとき、zNear.z以下の点は格納しない。また、E1.z[id]が同一になった場合にはE1.z[id]自体は１要素のみ格納され、重複度が図１４の斜線部分の重なりに応じた数となる。
【００９５】
zNear,E1.z[id]格納要素には該当E1.z[id]から隣接のzFar側のE1.z[id]までの斜線部の重複数情報が付加されている。同様に、zFar,E2.z[id]格納要素には該当E2.z[id]から隣接のzNear側のE2.z[id]までの斜線部の重複数情報が付加されている(図１５)。
【００９６】
図１５は、本実施形態におけるNearサブ線分端情報領域を説明するための図である。以下では、Near側のNearサブ線分情報格納領域について説明するが、Far側のFarサブ線分情報格納領域も同様である。
【００９７】
図１５のように、それぞれの区間のランクしきい値RankTH’を定義する。つまり、各区間ではRankTH’を満たすzNearに一番近い点が求めたいエッジである。
【００９８】
各参照Viewの線分探索時に、見つけた線分端情報とNearサブ線分端情報とをマージソートする。見つけた線分端情報とNearサブ線分端情報は、それぞれごとには既にzNear.zからzFar.zへ昇順に並んでいるためである。見つけた線分端情報は画面端の点と区別し、見つけた線分端情報の線分開始点と線分終了点も区別する(例えば重複度に開始点-1、終了点-2を入れる)。参照View(id)の線分探索後のマージソート後におけるNearサブ線分端情報の要素数は、マージソート前のNearサブ線分端情報+線分開始点数(id)+線分終了開始点数(id)となる。
【００９９】
線分重複検査部１９は、線分重複検査処理において各領域のnear側からfar側に検査して条件を満たした際には処理を切り上げる。各領域のfar側からnear側に検査して線分探索のEndの範囲を狭める場合には、実装によるが、例えば重複度をnear→far用とfar→near用に分けて持つ方法も考えられる(図１６及び図１７参照)。ここで、図１６は、本実施形態におけるNearサブ線分端情報領域と、重複度をnear→far用とfar→near用に分けて持つ方法を説明する図である。
【０１００】
線分重複検査部１９が行う線分重複検査処理は、各領域のnear側からfar側に検査して条件を満たした際にも、処理を切り上げずに領域すべてを検査してEndの範囲を狭める方法も考えられる。
【０１０１】
次に、線分重複検査処理の概要について説明する。
対象View(tid)の点zNear,点zFarと各参照Viewの画面端(Ev1(id), Ev2(id))の関係処理を行った後には次のようにランクしきい値RankTH’が格納されている。すなわち、Nearサブ線分端情報格納領域とFarサブ線分端情報格納領域に各参照Viewの画面端の対象Viewの3Dローカル座標変換したz座標と線分探索されず仮に線分があるものとして扱う部分の重複を考慮したランクしきい値RankTH’が格納されている。
【０１０２】
線分探索を行うごとに、上記領域に線分探索の結果を対象Viewの3Dローカル座標に変換してz座標を求め、マージソートを行う。その際に、各領域の開始インデックスと終了インデックスをデータの挿入数に合わせて変更する。
【０１０３】
線分重複検査部１９は、View２つ分の線分探索が終わった段階で動作（線分重複検査処理）を開始し、その後線分探索のView数が増えるごとにマージソートと線分重複検査処理を行う。
【０１０４】
線分重複検査処理ではzNear側から一番近いマスク画素との交点のz座標を求め、それが対象Viewから見た該当画素への距離となる。対象Viewから見た物体の表面までの距離のみを求める場合にはこの段階で線分重複検査処理を切り上げてもよいし、存在する線分すべてに対して重複度の検査を行ってもよい。物体の分離精度を向上するために、表面の距離から数点分(例えば3点まで)求める場合は、開始点-終了点-開始点、で切り上げる。この場合、対象Viewから見て表面までの距離、その表面から突入した物体から抜ける表面までの距離、その裏の次の物体の表面までの距離が求まることになる)求めることを行ってもよい。
【０１０５】
必要な点以外の線分重複検査処理を行うことは必要ない点を求めるための処理がかかることを意味し、この不必要な処理を省くことで演算量の削減となる。
【０１０６】
本実施形態は、不必要な処理を省くために、以下の情報は参照Viewを処理するにつれて制限することを実現する。
・Nearサブ線分端情報格納領域の線分探索開始点(LSMin[0])
・線分探索終了点(LSMax[0])、Core線分端情報格納領域の線分探索開始点(LSMin[1])
・線分探索終了点(LSMax[1])、Farサブ線分端情報格納領域の線分探索開始点(LSMin[2])
・線分探索終了点(LSMax[2])
【０１０７】
LSMin[Z],LSMax[Z]（Z=0,1,2）は対象Viewの3D座標におけるz座標である。線分重複検査処理では、これを対象Viewの3D座標における(x,y,z)からワールド三次元座標、参照Viewの2D（二次元）座標へと、線分端情報の射影と逆方向の射影により線分探索の該当エピポーラ線上に射影する。
【０１０８】
図１７は、本実施形態における対象View(tid)のzNear,zFarと各参照Viewの画像端（Ev1(id),Ev2(id)）の関係処理を説明する図である。
【０１０９】
本実施形態におけるVisualHullの処理では、線分重複検査処理を行うごとに、
Nearサブ線分端情報格納領域に対応する線分探索範囲LSMax[0]〜LSMax[0]
Core線分端情報格納領域に対応する線分探索範囲LSMax[1]〜LSMax[1]
Farサブ線分端情報格納領域に対応する線分探索範囲LSMax[2]〜LSMax[2]
のソート、マージを行い、各領域の先頭インデックスと終了インデックスをデータの挿入に合わせて更新する。
【０１１０】
次に、座標変換関連の行列について説明する。座標変換関連の行列は以下を用いる。
回転行列(3x3)       RMat
並進ベクトル(1x3)     TVec
カメラ内部パラメタ(3x3) AMat
ARMat = AMat*RMat
ATMat = AMat*TVec
invRTMat = RMat^{-1}×TVec
invRMatinvAMat=RMat^{-1}×AMat^{-1}
【０１１１】
次に、参照Viewの2D座標におけるエピポーラ線の導出方法について説明する。
図１８は、本実施形態における参照Viewの2D座標におけるエピポーラ線の導出方法について説明する図である。
【０１１２】
エピポーラ線を導出する際には、VisualHull部５は、まず、図１８のように、対象Viewのカメラ位置（3Dワールド座標系）を参照View(id)の2Dローカル座標系に変換してエピポールを導出する。その後、VisualHull部５は、参照View(id)の投影面におけるエピポールの位置及び対象Viewのカメラ位置及び投影面内のシルエットの位置に基づいて、エピポーラ線を導出する。このとき、VisualHull部５は、例えば、図１８に示したようなアルゴリズムによりエピポーラ線を導出する。
【０１１３】
次に、参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換する方法について説明する。
【０１１４】
図１９は、本実施形態における参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換する方法を説明する図である。
【０１１５】
参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換する処理は、対象Viewの3D座標を参照Viewの2D座標における(x,y)座標に変換する処理の逆変換となる。すなわち、参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換する処理では、図１９のように、まず、参照Viewの2D座標における(x,y)座標をワールド3D座標に変換する。その後、ワールド3D座標を、対象View(tid)のローカル3D座標に変換する。
【０１１６】
例えば、下記アルゴリズムにより3Dワールド座標をローカル2D座標に変換する場合を考える。
【０１１７】
(t0  = ARMat × (world3Dx
t1               world3Dy
t2)               world3Dz)
Pos0 = t0 + ATMat[0]
Pos1 = t1 + ATMat[1]
Pos2 = t2 + ATMat[2]
Pos2!=0.0の場合、z=1にスケーリング
local2Dx = Pos0/Pos2
local2Dy = Pos1/Pos2
Pos2==0.0の場合、
local2Dx = infinite
local2Dy = infinite
Pos2 >= 0 点がスクリーンより前にある
Pos2 < 0   点がスクリーンより手前にある
【０１１８】
この場合、ローカル2D座標をワールド3D座標に変換するアルゴリズムは、下記のようになる。
【０１１９】
(t0  = invRinvAMat × (local2Dx×s
t1                     local2Dy×s
t2)                    s)
(world3Dx   = (t0  -  invRTMat
world3Dy      t1
world3Dz      t2)
s = 1 (3Dワールド座標→2D投影座標(ローカル2D座標)でz=1にスケーリング)
【０１２０】
更に、ワールド3D座標を対象Viewの3D座標（ローカル3D座標）に変換するアルゴリズムは、下記のようになる。
【０１２１】
(t0  = RMat× (world3Dx
t1             world3Dy
t2)            world3Dz)
(local3Dx = (t0 + TVec
local3Dy    t1
local3Dz    t2)
【０１２２】
なお、上記のアルゴリズムは、参照Viewの2D座標における(x,y)座標を対象Viewの3D座標に変換するアルゴリズムの一例である。座標変換のアルゴリズムは、適宜変更可能である。
【０１２３】
次に線分端重複検査処理について説明する。
図２０は、本実施形態における線分端重複検査処理を説明する図である。
【０１２４】
図２０における「初期」は、線分端重複検査処理の開始時に相当する。線分端重複処理における初期段階では、図２０のように、Nearサブ領域、Core領域、Farサブ領域の各領域間にはRankの連続性が存在する。この場合にはNearサブのNear側、FarサブのFar側のみから線分探索の範囲を削減することが可能である。
【０１２５】
その後、処理を進めてViewを重ねると、線分重複検査部１９は、Nearサブ領域-Core領域間のCore領域に存在するNear側に一番近い不要な線分端探索範囲と、Core領域-Farサブ領域のCore領域に存在するFar側に一番近い不要な線分端探索範囲を見つける。不要な線分端探索範囲が見つかった場合、線分重複検査部１９は、そこを基点としてRankの確認ができるため、線分探索の範囲を削減することが可能となる。
【０１２６】
図２１は、本実施形態における不要な線分端探索範囲を説明する図である。
図２１には、サブ領域とCore領域の分割位置を決める例を示している。この位置に参照Viewを重ねてゆき、不要な線分端探索範囲を検出した後にはすべての参照Viewで線分が存在していたとしても、最終的に線分の重複度がRankTHを超えることはなく線分として検出されないからである。
【０１２７】
なお、実装の煩雑さを考慮しなければ、各領域についてRankの非連続箇所を検出したときに、都度領域分割して各領域についてViewを重ねるごとに線分端探索の範囲を削減することも可能である。
【０１２８】
図２２は、線分重複検査処理をnearからfar方向へ実施する処理の内容を説明する図である。図２３は、線分重複検査処理をfarからnear方向へ実施する処理の内容を説明する図である。
【０１２９】
本実施形態のVisualHullの処理では、図２２のフローチャートに沿った処理を行うことにより、領域のnear側の範囲を削減することが可能となる。図２２のnearからfar方向への処理では、線分開始点でRankを+1, 線分終了点でRankを-1する。ここで、開始点のランクは、nearからfar方向に線分端探索するときの範囲において一番near側(線分端探索開始点)のランク値である。
【０１３０】
また、本実施形態のVisualHullの処理では、図２３のフローチャートに沿った処理を行うことにより、領域のfar側の範囲を削減することが可能となる。図２３のfarからnear方向への処理では、線分開始点でRankを-1, 線分終了点でRankを+1する。ここで、終了点のランクはnearからfar方向に線分端探索するときの範囲において一番far側(線分端探索終了点)のランク値である。
【０１３１】
図２２及び図２３の処理フローにおけるstopCntは、線分重複検査処理でRankを満たす線分端を探す数を制御する。不要な線分端探索範囲を決定していない場合にはすべての線分端を検査する必要がある。不要な線分端探索範囲を決定した場合には、必要な数の表面位置(z座標値)を求めれば切り上げてよい。outCntはz座標値の出力数である。stopCnt,outCntはNearサブ領域、Core領域, Farサブ領域を通した処理で必要な表面位置の数を考慮してそれぞれの領域の処理に設定してもよい。
【０１３２】
なお、図２２の処理フローに沿った処理及び図２３の処理フローに沿った処理を連続して行う場合、処理の順序は問わない。すなわち、nearからfar方向へ実施する処理の後でfarからnear方向へ実施する処理を行ってもよいし、逆に、farからnear方向へ実施する処理の後でnearからfar方向へ実施する処理を行ってもよい。
【０１３３】
図２４は、本実施形態におけるNearサブ領域処理、Core領域処理, Farサブ領域処理を説明する図である。図２５は、図２２、図２３のNearサブ領域処理、Core領域処理、Farサブ領域処理のフローを示す図である。図２５におけるElm[n].重複度[a]≧0の処理より左側の分岐は画面端情報を含む領域の処理のみで使われる。Core領域は基本的に右側の分岐の処理のみとなる。
【０１３４】
次に、パイプラインで絞る処理のメリットについて説明する。
図２６は、対象Viewに対して参照Viewを１つごとに都度処理しつつ線分探索の範囲を削減することにより各性能ネック要因の削減となることを説明する図である。図２７は、本実施形態におけるすべてのデータがそろってから処理を行う場合と、都度データごと処理を行う場合を説明する図である。
【０１３５】
対象Viewに対して参照Viewを１つごとに都度処理しつつ線分探索の範囲を削減することにより、図２６に示す各性能ネック要因の削減となる。特に、VisualHullの処理はメモリアクセス要因の性能劣化が大きいため効果がある。
【０１３６】
また、連続的なデータを処理する場合に、対象Viewに対して参照Viewを１つごとに都度処理する利点がある。例えばデータ転送帯域の状況やシルエット画像（マスク画像）生成処理の処理時間の関係でシルエット画像がViewごとに適宜到着する。この場合、図２７のように、必要最小限のシルエット画像(対象Viewと１つの参照View)がそろった段階で処理を進めると(データ投入と処理をパイプライン的に実行すると)、データ転送の時間が処理時間に隠ぺいすることが可能となる。このため、都度データごとに処理を行うことにより、すべてのデータがそろってから処理を行う場合と比べて、トータルの処理時間は短縮される。
【０１３７】
図２８は、本実施形態におけるハードウェア構成の一例を示す図である。
上記の情報処理装置１０１及び３次元形状復元装置１は、例えば、コンピュータ２１である。コンピュータ２１は、図２８のように、中央演算装置（ＣＰＵ）２２，メモリ２３、ハードディスクドライブ（ＨＤＤ）２４、ネットワークインタフェースカード（ＮＩＣ）２５、入力インタフェース２６及びビデオインタフェース２７を含む。以下、インタフェースを「Ｉ／Ｆ」と称する。
【０１３８】
ＣＰＵ２２は、メモリ２３、ＨＤＤ２４、ＮＩＣ２５、入力Ｉ／Ｆ２６及びビデオＩ／Ｆ２７に接続されている。入力Ｉ／Ｆ２６にはキーボード、マウス、カメラ等の入力装置２８が接続されている。ビデオＩ／Ｆ２７には、ディスプレイ２９が接続されている。
【０１３９】
ＣＰＵ２２は、プロセッサの一例であって、コンピュータ２１の全体動作を制御する中央演算装置である。メモリ２３は、ワーキングエリアとして機能する。
【０１４０】
ＨＤＤ２４は、大容量記憶装置の一例であって、オペレーティングシステム（ＯＳ）やシミュレーション用のプログラムが格納されている記憶装置である。ＮＩＣ２５は、インターネット、ローカルエリアネットワーク（ＬＡＮ）等の通信ネットワークと有線又は無線で接続するためのインタフェースである。
【０１４１】
入力Ｉ／Ｆ２６は、入力装置２８から入力された指令をＣＰＵ２２へ伝達するインタフェースである。ビデオＩ／Ｆ２７は、ディスプレイ２９に画像を出力するインタフェースである。
【０１４２】
ＣＰＵ２２は、ＨＤＤ２４に格納されている本実施形態に係るプログラムを読み出し、実行する。基準カメラ（対象カメラ）及び参照カメラからの画像データ及びその他のデータは、予めＨＤＤ２４に格納されているものとする。なお、本実施形態に係るプログラムは、ＨＤＤ２４に限らず、ネットワークを介して接続される外部装置や、メモリカードや光学ディスク等の可搬型記録媒体等の、各種の非一時的な記録媒体に記録しておいてもよい。
【０１４３】
コンピュータ２１が本実施形態に係るプログラムを実行している間、ＣＰＵ２２は、図１の情報処理装置１０１における変換部１０２、検出部１０３、及び探索部１０４として機能する（動作する）。また、コンピュータ２１が本実施形態に係るプログラムを実行している間、メモリ２３及びＨＤＤ２４、或いは他の記憶装置や記録媒体は、図１の情報処理装置１０１における記憶部１０５として機能する。
【０１４４】
更に、別の観点では、本実施形態に係るプログラムを実行している間、ＣＰＵ２２は、例えば、図６の３次元物体復元装置１におけるシルエット画像分離部３、パラメタ生成部４、VisualHull部５、及びレンダリング部６として機能する（動作する）。
【０１４５】
本実施形態によれば、線分重複検査部で先に処理をした参照Viewの線分重複範囲におけるz座標の最小線分端及び最大線分端を後続の参照Viewの線分探索における範囲制限に追加考慮する線分範囲設定部を持つことができる。
【０１４６】
これにより、従来の各参照Viewの線分探索についてMax(zNear,画面端Near)〜Min(zFar, 画面端Far)の範囲を行うことに対して、線分探索部及び線分重複検査部の演算量と線分バッファのメモリ使用量を少なくすることができる。
【０１４７】
なお、本発明は、以上に述べた実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の構成又は実施形態を取ることができる。
【０１４８】
上記の実施形態に関し、更に以下の付記を開示する。
（付記１）
基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換する変換部と、
今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出する検出部と、
前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う探索部と、
を備えることを特徴とする情報処理装置。
（付記２）
前記検出部は、前記シルエット不存在範囲を累積し、累積された前記シルエット不存在範囲と今回取得される前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、前記シルエット不存在範囲を検出し、
前記探索部は、前記シルエット不存在範囲に基づいて、前記シルエットの存在する範囲の探索を行う
ことを特徴とする付記１に記載の情報処理装置。
（付記３）
前記検出部は、パイプライン処理により、新たに取得したシルエット存在位置情報が既存の前記シルエット不存在範囲に重複しているか否かにより前記シルエット不存在範囲を検出し、検出結果に応じて検出された前記シルエット不存在範囲を該既存の前記シルエット不存在範囲に追加する
ことを特徴とする付記１又は２に記載の情報処理装置。
（付記４）
前記検出部は、複数の前記シルエット存在位置情報のすべてで前記シルエットが存在する範囲のうちの、前記基準撮像装置の視点から最も近い前記範囲の端部よりも前記視点側となる範囲、及び前記基準撮像装置の視点から最も遠い前記範囲の端部よりも前記視点から遠方側となる範囲を、前記シルエット不存在範囲として検出する
ことを特徴とする付記１に記載の情報処理装置。
（付記５）
前記検出部は、複数の前記シルエット存在位置情報のすべてで前記シルエットが存在する範囲のうちの、前記基準撮像装置の視点から最も近い前記範囲の端部と、前記基準撮像装置の視点から最も遠い前記範囲の端部との間に、前記シルエットが存在しない範囲が含まれる場合に、該シルエットが存在しない範囲を前記シルエットが存在する範囲に含める
ことを特徴とする付記４に記載の情報処理装置。
（付記６）
前記検出部は、複数の前記シルエット存在位置情報のすべてで前記シルエットが存在する範囲のうちの、前記基準撮像装置の視点から最も近い前記範囲の端部と、前記基準撮像装置の視点から最も遠い前記範囲の端部との間に、前記シルエットが存在しない範囲が含まれる場合に、該シルエットが存在しない範囲を前記シルエット不存在範囲として検出する
ことを特徴とする付記４に記載の情報処理装置。
（付記７）
基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換し、
今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出し、
前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う、
処理をコンピュータに実行させることを特徴とするプログラム。
（付記８）
前記コンピュータに、更に、前記探索後、前記シルエット不存在範囲を累積し、
前記シルエットの検出において、累積された前記シルエット不存在範囲と今回取得される前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、前記シルエット不存在範囲を検出し、
前記探索において、前記シルエット不存在範囲に基づいて、前記シルエットの存在する範囲の探索を行う
処理を実行させることを特徴とする付記７に記載のプログラム。
（付記９）
前記検出において、パイプライン処理により、新たに取得したシルエット存在位置情報が既存の前記シルエット不存在範囲に重複しているか否かにより前記シルエット不存在範囲を検出し、検出結果に応じて検出された前記シルエット不存在範囲を該既存の前記シルエット不存在範囲に追加する
ことを特徴とする付記７又は８に記載のプログラム。
（付記１０）
コンピュータが、
基準撮像装置が撮像するシルエットを該基準撮像装置とは異なる視点から該シルエットを撮影する複数の参照撮像装置から順次、参照撮像装置に基づく前記シルエットの存在位置を示す情報であるシルエット存在位置情報を取得して共通の座標系に変換し、
今回取得した前記シルエット存在位置情報と、前回取得した前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、該シルエットの存在しない範囲を示すシルエット不存在範囲を検出し、
前記シルエット不存在範囲に基づいて、該シルエットの存在する範囲の探索を行う、
処理を実行することを特徴とする情報処理方法。
（付記１１）
前記コンピュータは、更に、前記探索後、前記シルエット不存在範囲を累積し、
前記シルエットの検出において、累積された前記シルエット不存在範囲と今回取得される前記シルエット存在位置情報との比較を行い、該比較の結果に基づいて、前記シルエット不存在範囲を検出し、
前記探索において、前記シルエット不存在範囲に基づいて、前記シルエットの存在する範囲の探索を行う
ことを特徴とする付記１０に記載の情報処理方法。
（付記１２）
前記検出において、パイプライン処理により、新たに取得したシルエット存在位置情報が既存の前記シルエット不存在範囲に重複しているか否かにより前記シルエット不存在範囲を検出し、検出結果に応じて検出された前記シルエット不存在範囲を該既存の前記シルエット不存在範囲に追加する
ことを特徴とする付記１０又は１１に記載の情報処理方法。
【符号の説明】
【０１４９】
１０１  情報処理装置
１０２  変換部
１０３  検出部
１０４  探索部
１０５  記憶部
１  ３次元形状復元装置
２  視点画像生成部
３  シルエット画像分離部
４  パラメタ生成部
５  VisualHull部
６  レンダリング部
１１，１６，１７  座標変換部
１２  エピポーラ線傾き導出部
１３  画面範囲導出部
１４  探索範囲決定部
１５  線分探索部
１８  線分バッファ[n]
１９  線分重複検査部
２１  コンピュータ
２２  中央処理装置（ＣＰＵ）
２３  メモリ
２４  ハードディスクドライブ（ＨＤＤ）
２５  ネットワークインタフェースカード（ＮＩＣ）
２６  入力インタフェース
２７  ビデオインタフェース
２８  入力装置
２９  ディスプレイ
【図１】
2019117580.tif 000003
【図２】
2019117580.tif 000004
【図３】
2019117580.tif 000005
【図４】
2019117580.tif 000006
【図５】
2019117580.tif 000007
【図６】
2019117580.tif 000008
【図７】
2019117580.tif 000009
【図８】
2019117580.tif 000010
【図９】
2019117580.tif 000011
【図１０Ａ】
2019117580.tif 000012
【図１０Ｂ】
2019117580.tif 000013
【図１１】
2019117580.tif 000014
【図１２】
2019117580.tif 000015
【図１３】
2019117580.tif 000016
【図１４】
2019117580.tif 000017
【図１５】
2019117580.tif 000018
【図１６】
2019117580.tif 000019
【図１７】
2019117580.tif 000020
【図１８】
2019117580.tif 000021
【図１９】
2019117580.tif 000022
【図２０】
2019117580.tif 000023
【図２１】
2019117580.tif 000024
【図２２】
2019117580.tif 000025
【図２３】
2019117580.tif 000026
【図２４】
2019117580.tif 000027
【図２５】
2019117580.tif 000028
【図２６】
2019117580.tif 000029
【図２７】
2019117580.tif 000030
【図２８】
2019117580.tif 000031