JP6802129B2 - 情報処理装置、方法及びプログラム - Google Patents

Description

本発明は、並列処理に適しており且つ高速に処理可能なオクルージョン判定を行うことのできる情報処理装置、方法及びプログラムに関する。

3Dモデルのオブジェクト間における可視領域の判定は、CG（コンピュータグラフィックス）分野一般において、また、特に、ボリュームレンダリングや自由視点映像生成における注目トピックである。その典型的手法として、レイキャスティング法は図１にその模式例（3次元空間の断面を構成する2次元での模式例）を示すように、光線と表面の交差テストを行うことで対象シーンの点が可視領域にあるか否かを決定する。レイキャスティング法は概略的には、各光線に関して以下の手順を行うというものである。

（手順１）ターゲット点とカメラの光学中心とを結ぶことで光線方向を決定する。図１では当該決定された光線方向の一例が示されている。
（手順２）当該光線と対象シーンのバウンディングボックス（bounding box）（空間内に設定する直方体の所定領域であって判定用のボクセル分割が施されているもの）に対する交差点として、入射点（光線の入る交差点）及び出射点（光線の出る交差点）を決定する。図１ではバウンディングボックスが模式的に碁盤目状に描かれると共に、一例の光線における入射点及び出射点が示されている。
（手順３）当該光線上でボクセル境界にある各点に関して、入射点から順次、出射点側の隣接点をスキャンしていくことで、最初に3Dモデル（すなわちオブジェクト）に交差する点を可視領域の点と判定し、当該点よりも先にある各点はオクルージョンが発生していると判定する。図１では一例の光線及びグレーで示すオブジェクトに対して、可視領域判定された点とその先のオクルージョン判定された点とが示されている。

レイキャスティング法における基本的な問題として、（手順３）のスキャン幅（図１にもその一例を示すストライド）に関して、適切な値をどのように設定すればよいかという問題がある。すなわち、ストライドを小さくすれば精度は上がるものの計算量が増えてしまい、逆にストライドを大きくすれば計算量は減るものの精度が下がってしまう。

当該トレードオフ関係にある精度及び計算量の問題に関して、非特許文献１では、コーンステップマッピングと呼ばれる手法を提案し、予め処理された円錐（コーン）を用いてストライドの幅を調整している。また、非特許文献２では最大ミップマップ法を提案し、ミップマップ状のデータ構造の利用することで何もない空の空間をスキップしてスキャン速度を高速化している。

また、可視領域決定のその他の手法として非特許文献３，４等に開示されるZバッファ法（深度バッファ法）がある。概略的には、対象シーンのレンダリング画像の各画素に関して、あるオブジェクトの表面に該当するものである場合にはその深度を保存しておき、このような画素が同時に別のオブジェクトの表面にも該当する場合は、深度の値をより小さい方（すなわちよりカメラに近いオブジェクトの深度）で上書きしていくようにするという手法である。

Dummer, J. "Cone Step Mapping: An Iterative Ray-Heightfield Intersection Algorithm (2006)." URL: http://www. lonesock. net/files/ConeStepMapping. pdf 2.3: 4. Tevs, Art, Ivo Ihrke, and Hans-Peter Seidel. "Maximum mipmaps for fast, accurate, and scalable dynamic height field rendering." Proceedings of the 2008 symposium on Interactive 3D graphics and games. ACM, 2008. Z-buffering from Wikipedia, https://en.wikipedia.org/wiki/Z-buffering. コンピューターグラフィクス基礎（筑波大学）P-19 http://www.npal.cs.tsukuba.ac.jp/~endo/lecture/2016/cgbasics/08/08_slides.pdf.

しかしながら、以上のような2手法（非特許文献１，２のような高速化を考慮したレイキャスティング法及び非特許文献３，４のようなZバッファ法）は、依然として課題を有するものであった。

まず、高速化考慮のレイキャスティング法は、予め計算しておいた何らかの結果を記憶しておく必要があることで、記憶装置の容量及び帯域を大量消費してしまうという課題があった。また、交差判定を繰り返し行う計算負荷が大きくなるため、高解像度の3Dモデルを扱うことが困難であった。また、潜在的なリスクとして交差判定の繰り返し回数が対象とする光線によって変動しうることから、GPU等を用いた並列処理に不向きであるという課題もあった。

また、Zバッファ法ではある頂点（オブジェクトの頂点）が可視領域にあるか否かの判定が、別の頂点の状態に依存することとなり、逐次処理に向いたCPU等では高速化が可能だが、並列処理に向いたGPU等では必ずしも容易に利用することはできないという課題があった。さらに、Zバッファ法においては各頂点からカメラへの距離を計算する際に、頂点のうち一部分のみにオクルージョンが発生しているという前提を置いていた。

以上のような従来技術の課題に鑑み、本発明は、並列処理に適しており且つ高速に処理可能なオクルージョン判定を行うことのできる情報処理装置（並びに方法及びプログラム）を提供することを目的とする。

上記目的を達成するため、本発明は情報処理装置であって、３Ｄオブジェクトのモデルデータを所定のカメラ配置における画像領域に逆投影し、画像領域の各点における３Ｄオブジェクトが投影されている数である重複度を与えた重複マップを得る投影部と、前記重複マップの重複度が２以上となる領域をそれぞれ重複領域として抽出する抽出部と、前記重複領域に対応する２以上の３Ｄオブジェクト毎の領域を特定し、当該領域の中からカメラ中心との位置関係に基づいて前記所定カメラ配置においてオクルージョンを発生させるものを判定する判定部と、を備えることを特徴とする。

本発明によれば、並列処理に適した手法によって高速に処理可能なオクルージョン判定を行うことができる。

従来手法としてのレイキャスティング法の概略及び問題点を説明するための模式例を示す図である。 一実施形態に係る情報処理装置の機能ブロック図である。 主として投影部及び抽出部の処理を説明するための模式例を示す図である。 主として判定部の処理を説明するための模式例を示す図である。

図２は、一実施形態に係る情報処理装置の機能ブロック図である。図示するように情報処理装置10は、投影部1、抽出部2及び判定部3を備え、判定部3はさらに特定部31、計算部32及び遮蔽判定部33を備える。図示される通り、各部の機能概要は次の通りである。

投影部1では入力として予め用意されている複数の3Dオブジェクトのモデルデータを受け取り、当該複数の3Dオブジェクトを所定のカメラ配置でレンダリングする場合の画像領域に逆投影することで、当該画像領域の各画素位置において３Dオブジェクトの重複度をカウントして与えた重複マップを得て、当該重複マップを抽出部2へと出力する。

抽出部2では、投影部1から得られた重複マップにおいて重複度が２以上となっている領域をそれぞれ重複領域として抽出し、当該重複領域の情報を判定部3（特定部31）へと出力する。

判定部3では、抽出部2から得られた重複領域に基づいて、投影部1において重複マップを作成した際の所定のカメラ配置において、複数の３Dオブジェクトのうちオクルージョンを発生させているもの及びその3Dオブジェクト内での領域を判定する。当該判定するための要素処理として、各部31〜33は以下のような処理を行なう。

特定部31は、抽出部2から得られる重複領域のそれぞれに対して、重複領域に対応している（すなわち、当該重複領域へと逆投影されている）3Dオブジェクト及びその領域（3Dオブジェクト内における部分領域）を特定し、当該特定結果を計算部32へと出力する。なお、当該対応する3Dオブジェクト及びその領域は、各重複領域に対して２個以上存在することとなる。

計算部32では、特定部31で各重複領域について得られた対応する3Dオブジェクト及びその領域に関して、逆投影の際のカメラ中心からの位置関係を計算し、当該位置関係を遮蔽判定部33へと出力する。

遮蔽判定部33は、特定部31で各重複領域について得られた2個以上の対応する3Dオブジェクト及びその領域の中から、計算部32で計算された位置関係に基づいて、オクルージョンを発生させているものがいずれであるかを判定し、判定部3の出力となす。なお、遮蔽判定部33では、当該出力と同等の情報（オクルージョンを発生させていないものがいずれであるかを特定する情報）として、投影部1で複数の3Dオブジェクトを所定のカメラ配置でレンダリングする場合の画像領域に逆投影する場合に、可視領域を構成することとなる3Dオブジェクト及びその領域を出力するようにしてもよい。

以下、当該概略説明した各部の処理内容の詳細を説明する。図３及び図４は当該詳細説明のための模式例を示す図であり、以下の説明において適宜参照する。なお、図３は主として投影部1及び抽出部2を説明するためのものであり、図４は主として判定部3を説明するためのものであり、当該図３及び４の間では用いる例（対象となる３Dオブジェクトの模式例）が共通している。

＜投影部1について＞
投影部1では、そのモデルデータが入力される複数の3Dオブジェクトに関して、所定カメラ配置での逆投影を行うことで、重複マップを求める。周知のように逆投影とは、与えられた3Dモデルが所定カメラ配置における画像においてどのように分布するかを明らかにする処理である。図３の[1]の例では４つの3DオブジェクトM1〜M4（それぞれIDとしてIdi=1〜4が付与されている）を所定配置にあるカメラCに逆投影することで、その画像領域に重複度マップOMを得ることが示されている。さらに図３の[2]に示すよ
うに、当該得られた重複度マップOMは画像領域内での３Dオブジェクトの重複度（重複している個数）の分布を与えるものとなっている。図３の[2]では当該重複度の具体例が説明のための吹き出しによって示されており、3Dオブジェクトが全く逆投影されない背景領域に関しては「重複度=0」であり、3DオブジェクトM3やM4等が1個だけ逆投影された領域に関して「重複度=1」となり、2個の3DオブジェクトのM3,M4のそれぞれ一部が互いに重複している領域に関して「重複度=2」となることが例として示されている。

具体的な逆投影に関しては、以下の式(1)によって各3Dオブジェクトのモデルデータ（モデルの3D座標系においてM個のオブジェクトの頂点位置（M個のオブジェクト全体で合計N個の頂点）を与えたデータ）{P_i ^x, P_i ^y, P_i ^z}(i=1, 2, ..., N)を画像領域の（正規化された）座標(u,v)へと逆投影することができる。T₃₄は逆投影の行列である。

当該逆投影を、各頂点データ{P_i ^x, P_i ^y, P_i ^z}(i=1, 2, ..., N)に関して行い、各座標(u,v)においてM個の各3Dオブジェクトの頂点が少なくとも１点だけ逆投影された場合に、当該オブジェクトからの重複度の寄与分に「+1」の加算を行うことで、投影部1では重複度マップoverlapMap(u,v)を得ることができる。なお、ある1個の3Dオブジェクトの2個以上の頂点が座標(u,v)に逆投影される場合であっても、当該3Dオブジェクトからの重複度の寄与分は「+1」のみとする。従って、重複度マップoverlapMap(u,v)の各座標(u,v)における値の範囲は0以上M以下となる。

なお、重複度マップの表現に関して、図面中で模式例として参照する場合は符号「OM」を用い、「overlapMap(u,v)」は数式等において参照するために用いる。

ここで、式(1)による逆投影等を実現するにあたっての本発明の一実施形態における前提事項を列挙すると以下の(1)〜(5)の通りである。
(1) 各頂点データ{P_i ^x, P_i ^y, P_i ^z}としての3Dオブジェクトのモデルデータは用意しておく。
(2) 当該モデルデータ内において個別の3Dオブジェクトの区別（セグメント結果）も予め与えておく。すなわち、各頂点データ{P_i ^x, P_i ^y, P_i ^z}に関して、M個のいずれのオブジェクトに属するものかの区別を予め与えておく。
(3) 当該頂点データへの区別を与えておくための個別のオブジェクトに関してもID(式Id_iで表記することとする)を与えておく。
(4) 投影行列T₃₄及び投影するカメラ位置{C^x, C^y, C^z}は既知のものとして定義しておく。
(5) モデルデータとしての3Dオブジェクトの各頂点データ{P_i ^x, P_i ^y, P_i ^z}はその密度が十分に高く、互いに隣接する２つの頂点v1,v2を式(1)で逆投影した場合には、同一の画像座標(u,v)に投影されるか、又は十分に近傍となる座標に投影される。例えば座標(u,v)と、その隣接座標である(u±1,v)又は(u, v±1)のいずれかとに投影される。

＜抽出部2について＞
抽出部2では、重複度マップから重複領域をそれぞれ識別して抽出する。具体的には、重複度マップのうち重複度が2以上となっている点を前景とみなし、それ以外の重複度が1以下となっている点を背景とみなすことで重複度マップを2値画像とみなしたものに対して、任意の領域分割手法を適用することにより、前景として重複度が2以上になっている領域をそれぞれ重複領域として識別して抽出する。例えば、以下の式で模式的に示すように連結領域ラベリングCCLの適用により、前景を構成している各座標(u,v)に関して属する連結領域のIDであるIdaA(u,v)を得るようにしてよい。ここで、CCL{}はプログラミング等の表現における関数等としてCCLを適用する処理を表現している。
IdA(u,v)=CCL{overlapMap(u,v)} (2)

図３の例では[2]に示す重複度マップから[3]に示す領域抽出結果AMとして２つの重複領域A1,A2が識別されたうえで抽出される例が示されている。重複領域A1は[1]の3DオブジェクトM1,M2の重複箇所に該当し、重複領域A2は[1]の3DオブジェクトM3,M4の重複箇所に該当するものである。

＜特定部31について＞
特定部31は、各重複箇所に対して、いずれの3Dオブジェクトのいずれの部分領域が対応しているか、すなわち逆投影されるものであるかをオクルージョン発生原因の候補として特定する。ここで、一実施形態では当該特定を、投影部1で既に逆投影しておいた際の結果（いずれの3Dオブジェクトが(u,v)に逆投影されたかの結果）を各画素位置(u,v)において記憶しておいたものを参照することによって実現するようにしてもよい。

しかしながら、一実施形態では特定部31は、逆投影部1で行ったのと同じ逆投影を再度実行することによって当該候補を特定してもよい。当該実施形態により上記記憶しておくメモリ領域を省略することが可能となる。当該メモリ領域はカメラ数が多い場合、膨大なものとなってしまうが、当該一実施形態ではそのようなメモリ消費を避けることができる。

図４の例は、図３の[3]のものと同じ領域抽出結果AMのうちの重複領域A2に関して特定部31による処理が行われることで、3DオブジェクトM4の部分領域M4-O2と3DオブジェクトM3の部分領域M3-O2との2個の部分領域がオクルージョン発生候補となることが特定される例である。

＜計算部32について＞
計算部32では、特定部31において重複領域ごとに特定されたオクルージョン発生候補となる複数の3Dオブジェクトの部分領域に関して、特定部31（及び投影部1）での逆投影の際のカメラ中心との位置関係を計算する。一実施形態では、カメラ中心と各3Dオブジェクトの部分領域における各点との平均の距離（オイラー距離など）として、当該位置関係を計算してよい。（なお、当該平均距離はカメラ中心（１点）と各3Dオブジェクトの部分領域における各点i=1,2,..., M（Mは当該3Dオブジェクトの部分領域の点の総数）との距離をD(i)(i=1,2, ..., M)として、当該各距離D(i)をM個の点に関して総和したものを当該個数Mで割ったものとして求めればよい。）

＜遮蔽判定部32について＞
遮蔽判定部32では、計算部31で計算された位置関係に基づき、重複領域ごとに特定されたオクルージョン発生候補となる複数の3Dオブジェクトの部分領域のうち、実際にオクルージョンを発生されているものを特定する。具体的には、当該位置関係においてカメラ中心に最も近いと判定されるもの以外をオクルージョンを発生させているものとして特定する。計算部31で式(3),(4)の平均オイラー距離で位置関係を計算したのであれば、当該距離が最小となるもの以外を、オクルージョンを発生させているものとして特定する。

例えば図４の例であれば、重複領域A2に対応する候補としての3DオブジェクトM4の部分領域M4-O2と3DオブジェクトM3の部分領域M3-O2との2個の部分領域のうち、カメラCのカメラ中心に最も近い部分領域M4-O2はオクルージョンを発生させないものとして判定され、これよりも遠い部分領域M3-O2はオクルージョンを発生させるものとして判定される。なお、本発明の一実施形態ではこのようにオクルージョン判定はオブジェクトの部分領域を単位として判定する。（すなわち、当該部分領域内においてさらに区別してオクルージョン判定を行うこと、例えばカメラ中心から見て表（オクルージョンなし）や裏（オクルージョンあり）にあるものを区別するといったことは省略される。）

以上、本発明によれば、GPU等を用いてリアルタイムに可視領域の判定を行う場合等に利用可能なオクルージョン判定を行うことが可能であり、各処理はGPU等の並列処理に適したものとして構成されており、人手による指定作業等が不要な自動処理として実現可能である。ここで特に、従来手法のような繰り返し処理も不要であることから、本発明は並列処理に適したものとして構成されている。

本発明は、コンピュータを情報処理装置10として機能させるプログラムとしても提供可能である。当該コンピュータには、CPU(中央演算装置)、メモリ及び各種I/Fといった周知のハードウェア構成のものを採用することができ、CPUが情報処理装置10の各部の機能に対応する命令を実行することとなる。また、当該コンピュータはさらに、CPUよりも並列処理を高速実施可能なGPU（グラフィック処理装置）を備え、CPUに代えて情報処理装置10の全部又は任意の一部分の機能を当該GPUにおいてプログラムを読み込んで実行するようにしてもよい。

10…情報処理装置、1…投影部、2…抽出部、3…判定部

Claims (6)

1. ３Ｄオブジェクトのモデルデータを所定のカメラ配置における画像領域に逆投影し、画像領域の各点における３Ｄオブジェクトが投影されている数である重複度を与えた重複マップを得る投影部と、
   前記重複マップの重複度が２以上となる領域をそれぞれ重複領域として抽出する抽出部と、
   前記重複領域に対応する２以上の３Ｄオブジェクト毎の領域を特定し、当該領域の中からカメラ中心との位置関係に基づいて前記所定カメラ配置においてオクルージョンを発生させるものを判定する判定部と、
   を備えることを特徴とする情報処理装置。
2. 前記抽出部では、連結領域ラベリング法その他の領域分割法によって抽出することを特徴とする請求項１に記載の情報処理装置。
3. 前記判定部では、前記重複領域のそれぞれに再度、前記複数の３Ｄオブジェクトのモデルデータを前記逆投影することによって、前記特定することを特徴とする請求項１または２に記載の情報処理装置。
4. 前記判定部では、前記領域のうちカメラ中心からの距離が最小となるもの以外を前記所定カメラ配置においてオクルージョンを発生させるものとして判定することを特徴とする請求項１ないし３のいずれかに記載の情報処理装置。
5. ３Ｄオブジェクトのモデルデータを所定のカメラ配置における画像領域に逆投影し、画像領域の各点における３Ｄオブジェクトが投影されている数である重複度を与えた重複マップを得る投影段階と、
   前記重複マップの重複度が２以上となる領域をそれぞれ重複領域として抽出する抽出段階と、
   前記重複領域に対応する２以上の３Ｄオブジェクト毎の領域を特定し、当該領域の中からカメラ中心との位置関係に基づいて前記所定カメラ配置においてオクルージョンを発生させるものを判定する判定段階と、を備えることを特徴とする方法。
6. コンピュータを、
   ３Ｄオブジェクトのモデルデータを所定のカメラ配置における画像領域に逆投影し、画像領域の各点における３Ｄオブジェクトが投影されている数である重複度を与えた重複マップを得る投影部と、
   前記重複マップの重複度が２以上となる領域をそれぞれ重複領域として抽出する抽出部と、
   前記重複領域に対応する２以上の３Ｄオブジェクト毎の領域を特定し、当該領域の中からカメラ中心との位置関係に基づいて前記所定カメラ配置においてオクルージョンを発生させるものを判定する判定部と、を備えることを特徴とする情報処理装置として機能させるプログラム。

Images