(57)【要約】【課題】空間におけるある視点から見て他のオブジェクトによって遮られているオブジェクトを高速に検索する。【解決手段】本発明の一態様としてのオブジェクト検索装置は、データベースと、レンダリング部と、算出部と、オブジェクト探索部とを備える。前記データベースは、空間における複数のオブジェクトの配置情報を記憶する。前記レンダリング部は、前記空間内に設定した視点から前記複数のオブジェクトを描画する。前記算出部は、前記レンダリング部を用いて描画を行い、少なくとも一部の画像が他のオブジェクトの画像によって隠されるオブジェクトの個数を算出する。前記オブジェクト探索部は、前記算出部により算出された個数を検索結果数の上限値として、前記空間内において前記視点から見て少なくとも一部が他のオブジェクトによって遮られているオブジェクトを検索する探索演算を前記データベースに基づき実行する。【選択図】図１
2014059839.tif 000002
【特許請求の範囲】
【請求項１】
空間における複数のオブジェクトの配置情報を記憶するデータベースと、
前記空間内に設定した視点から前記複数のオブジェクトを描画するレンダリング部と、
前記レンダリング部を用いて描画を行い、少なくとも一部の画像が他のオブジェクトの画像によって隠されるオブジェクトの個数を算出する算出部と、
前記算出部により算出された個数を検索結果数の上限値として、前記空間内において前記視点から見て少なくとも一部が他のオブジェクトによって遮られているオブジェクトを検索する探索演算を前記データベースに基づき実行するオブジェクト探索部と、
を備えたオブジェクト検索装置。
【請求項２】
前記オブジェクト探索部は、前記上限値の個数のオブジェクトが検索された場合は、前記探索演算を終了する
請求項1に記載のオブジェクト検索装置。
【請求項３】
前記オブジェクト探索部は、前記上限値に基づき複数の探索戦略の中から探索戦略を選択し、選択した探索戦略にしたがって探索演算を実行する
請求項1または2に記載のオブジェクト検索装置。
【請求項４】
前記算出部は、前記レンダリング部を用いて、
前記複数のオブジェクトのすべてを描画した第1描画像データを生成し、
前記複数のオブジェクトの個々の1つを独立して描画した第2描画象データをそれぞれ生成し、
前記第1描画像データに示される個々のオブジェクトの画像と、前記個々のオブジェクトに対応する前記第2描画像データの画像が一致しないとき、前記個々のオブジェクトの画像は他のオブジェクトの画像によって隠されていると決定する
請求項1に記載のオブジェクト検索装置。
【請求項５】
前記算出部は、前記レンダリング部を用いて、
前記複数のオブジェクトをそれぞれ順番にピクセル毎に描画し、描こうとするピクセルに、既に別のオブジェクトが描かれているときは、描いているオブジェクトと前記別のオブジェクトの前後関係を判定することにより、前記描いているオブジェクトと前記別のオブジェクトのどちらが隠されるかを決定する
請求項1に記載のオブジェクト検索装置。
【請求項６】
前記記憶部は、各葉ノードに前記オブジェクトのうちの異なる1つをそれぞれ割り当て、親ノードに前記親ノードの各子ノードのオブジェクトを包含する外包体を割り当てた階層オブジェクト構造を記憶し、
前記オブジェクト探索部は、第1探索戦略として、
（A）前記親ノードの各子ノードのそれぞれに対応する外包体内に他のオブジェクトによって遮られているオブジェクトが含まれる可能性があるかの判定を行い、
（B）存在する可能性があると判定された子ノードについて前記（A）と同様の判定を行うことを繰り返し、
（C）到達した葉ノードについて、当該葉ノードに対応するオブジェクトが他のオブジェクトによって遮られているかを判定する、
請求項1ないし5のいずれか一項に記載のオブジェクト検索装置。
【請求項７】
前記記憶部は、各葉ノードに前記オブジェクトのうちの異なる1つを割り当て、親ノードに各子ノードのオブジェクトを包含する外包体を割り当てた階層オブジェクト構造を記憶し、
前記オブジェクト探索部は、第2探索戦略として、
（A）前記親ノードの各子ノードのうちの一方の子ノードを選択し、
（B）選択したノードに対応する外包体内に、他のオブジェクトによって遮られているオブジェクトが含まれる可能性があるかの判定を行い、
（C）含まれる可能性がないと判定したときは、前記各子ノードのうち他方のノードを選択し、選択したノードについて前記（B）の判定を行い、
（D）前記（B）または（C）で含まれる可能性があると判定したとき、当該選択したノードの子ノードを対象に、前記（A）以降の処理を再帰的に行い、到達した葉ノードについて、当該葉ノードのオブジェクトが他のオブジェクトによって遮られているかを判定する、
請求項1ないし4のいずれか一項に記載のオブジェクト検索装置。
【請求項８】
空間における複数のオブジェクトの配置情報を記憶するデータベースと、
前記空間内に設定した視点から前記複数のオブジェクトを描画するレンダリング部と、
前記レンダリング部を用いて描画を行い、少なくとも一部の画像が他のオブジェクトの画像によって隠されるオブジェクトを識別する算出部と、
前記算出部により識別されたオブジェクトについて、前記空間内において前記視点から見て前記オブジェクトの少なくとも一部が他のオブジェクトによって遮られているかを判定するオブジェクト探索部と、
を備えたオブジェクト検索装置。
【請求項９】
空間における複数のオブジェクトの配置情報を記憶するデータベースにアクセスするステップと、
前記空間内に設定した視点から前記複数のオブジェクトを描画するレンダリングステップと、
前記レンダリングステップによる描画に基づき、少なくとも一部の画像が他のオブジェクトの画像によって隠されるオブジェクトの個数を算出する算出ステップと、
前記算出ステップにより算出された個数を検索結果数の上限値として、前記空間内において前記視点から見て少なくとも一部が他のオブジェクトによって遮られているオブジェクトを検索する探索演算を前記データベースに基づき実行するオブジェクト探索ステップと、
を備えたオブジェクト検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、オブジェクト検索装置およびその方法に関し、たとえばGISやCAD等のアプリケーションの3次元（3D）オブジェクトを管理する方法に関する。
【背景技術】
【０００２】
3Dデータベースは、時空間上に配置されたオブジェクトの集合を管理する。範囲を指定したクエリを受け取り、その範囲にあるオブジェクト一覧を返す機能を持つ。ベースとなるデータ構造・インデクスとしては、R-tree、Quad-treeやその拡張が用いられている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】R-tree (Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57. ISBN 0-89791-128-8)
【非特許文献２】Quad-tree (Raphael Finkel and J.L. Bentley (1974年). “Quad Trees: A Data Structure for Retrieval on Composite Keys”. Acta Informatica 4 (1): 1?9. doi:10.1007/BF00288933)
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ある視点からあるオブジェクトまでの間に、他の任意のオブジェクトがある場合、そのオブジェクトは遮られていると言う。オブジェクト群と視点を指定し、遮られているオブジェクトの一覧を得る方法が知られている。オブジェクトから視点の方向に向かう半直線的な範囲に存在するオブジェクトを求めるクエリをオブジェクトごとに実行し、その範囲内に自分自身以外のオブジェクトが一つでも存在すれば、そのオブジェクトは遮られていると判断する。
【０００５】
この各処理はR-treeやQuad-treeに基づいて行うため、単発の検索では高性能である。しかしながら、全オブジェクトに対して行うため、検索が遅くなる問題があった。
【０００６】
このような多数の一様な検索は、太陽光発電（PV：Photovoltaic power generation）装置の配置を管理する3Dデータベースでは、ビルの影に入るオブジェクト（PV装置）一覧や、ある視点からの視界内に入るオブジェクト一覧などを求めるクエリが頻繁に発生する。
【０００７】
一方、3D描画を行う技術は、CADやゲームなどで研究開発・活用されている。この処理はGPUなど専用ハードウェアを使うことで非常に高速に実行可能であり、このハードウェアは広く使われているため安価である。そこで視点の方向から3D描画によって描画データを生成して、描画データをもとに、遮られているオブジェクトを検索することが考えられる。しかしながら、この検索は高速であるが、その精度は高くない。
【０００８】
本発明の一側面は、空間におけるある視点から見て他のオブジェクトによって遮られているオブジェクトを高速に検索することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一態様としてのオブジェクト検索装置は、データベースと、レンダリング部と、算出部と、オブジェクト探索部とを備える。
【００１０】
前記データベースは、空間における複数のオブジェクトの配置情報を記憶する。
【００１１】
前記レンダリング部は、前記空間内に設定した視点から前記複数のオブジェクトを描画する。
【００１２】
前記算出部は、前記レンダリング部を用いて描画を行い、少なくとも一部の画像が他のオブジェクトの画像によって隠されるオブジェクトの個数を算出する。
【００１３】
前記オブジェクト探索部は、前記算出部により算出された個数を検索結果数の上限値として、前記空間内において前記視点から見て少なくとも一部が他のオブジェクトによって遮られているオブジェクトを検索する探索演算を前記データベースに基づき実行する。
【図面の簡単な説明】
【００１４】
【図１】本実施形態にかかるオブジェクト検索装置のブロック図。
【図２】オンライン検索結果見積もり処理のフローチャート。
【図３】オブジェクト検索装置の全体のフローチャート。
【図４】実施例Aにおけるオブジェクト配置の図。
【図５】実施例Aにおけるオブジェクト配置を表す木構造を示す図。
【図６】比較回数削減探索処理のフローチャート。
【図７】実施例Aにおける比較回数・キャッシュミス回数の表を示す図。
【図８】実施例Bにおけるオブジェクト配置を示す図。
【図９】実施例Bにおけるオブジェクト配置を表す木構造を示す図。
【図１０】キャッシュミス削減探索処理のフローチャート。
【図１１】実施例Bにおける比較回数・キャッシュミス回数の表を示す図。
【発明を実施するための形態】
【００１５】
以下、図面を参照しながら、本実施形態を詳細に説明する。
【００１６】
図1に、本発明の実施形態にかかる3Dデータベースのオブジェクト検索装置を示す。
【００１７】
オブジェクト階層構造構成部101は、空間に配置された複数のオブジェクトについてそれぞれの最小外包直方体 (Minimum Bounded Box; MBB)を計算する。計算される最小外包直方体の各辺はx軸、y軸、z軸のいずれかに平行である。そして、MBBが近接するオブジェクト同士を1かたまりとし（グループ化し）、そのかたまりのMBBを計算する。個々のオブジェクトのMBBを葉として、かたまりをノードとし、さらにかたまり同士をノードとして、バランスされた木構造で表現される階層構造を表現していく。また、オブジェクトの挿入や削除が発生した場合にも、特性を維持するように木構造を変更していく。木構造は、各ノードの親子関係、および各オブジェクトのMBBの空間における配置位置の情報を含んでいる。
【００１８】
ここで述べた木構造の生成手法はR-tree (Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57. ISBN 0-89791-128-8) や Quad-tree と同じ手法であるため、詳しくは当該文献を参照されたい。
【００１９】
オブジェクトMBBツリー格納部102は、オブジェクト階層構造構成部101が生成した階層構造を記憶するデータベースである。なお、本実施形態では、入力されたオブジェクトのMBBおよびグループ化したオブジェクトのMBBを計算したが、入力されたオブジェクトが直方体の各辺x軸、y軸、z軸に平行の場合は、当該オブジェクトのMBBの計算処理は不要である。また本実施形態では、オブジェクトをそのMBBによって扱うが、本実施形態はこれに制限されるものではない。
【００２０】
以下に説明するレンダリング部104、検索結果数見積もり部（算出部）103、オブジェクト探索部105の処理では、オブジェクトの処理は、特段の説明が無い限り、オブジェクトのMBBにより行うものとする。
【００２１】
レンダリング部104は、オブジェクトMBBツリー格納部102から3D空間に配置されたオブジェクト一覧を読み出す。レンダリング部104は、クエリにより与えられる視点の方向から、空間における各オブジェクトの3Dレンダリング処理を行う。レンダリング処理の途中で得られる情報、またはレンダリング処理の結果（描画データ）は、検索結果数見積もり部103で利用する。当該処理の途中で得られる情報やレンダリング処理の結果を表示装置で実際に表示する必要はない。
【００２２】
検索結果数見積もり部103は、視点を表すクエリを受け取り、レンダリング部104を用いて、クエリにより示される視点から、各オブジェクトを3Dレンダリングする。レンダリングの途中で得られる情報、またはレンダリングの処理結果を利用することで、他のオブジェクトによって遮られているオブジェクト数の上限値（検索結果数の上限値）を見積もる。
【００２３】
ここで、視点を表すクエリとしては、位置を表す3D座標(透視投影のカメラ位置)、または、視線方向を表す3Dベクトル(視点が無限遠にあると考える。平行投影の視線方向)、または同等の情報を持つデータ構造を用いる。ここでは視点の主体は、全方位カメラのようなものを想定する。本実施形態の用途の一例は、当該位置に点光源を置いて、影が出来てしまうオブジェクト（他のオブジェクトによって遮られるオブジェクトの）の一覧を得るものである。
【００２４】
レンダリングの処理結果を利用して、検索結果数の上限値を見積もることを、“オフライン検索結果見積もり処理”と呼ぶ。一方、レンダリング処理の途中で得られる情報を利用して検索結果数の上限値を見積もることを、“オンライン検索結果見積もり処理”と呼ぶ。どちらの処理でも、同じ結果が得られる。
【００２５】
“オフライン検索結果見積もり処理”では、レンダリング結果の描画データを利用して、完全な形で描かれているオブジェクトのみを判定により抽出する。すなわち他のオブジェクトの画像によって隠されていない（他のオブジェクトの画像と重なっていない）オブジェクトをすべて特定する。特定したオブジェクトの集合は、他のオブジェクトの画像によって隠されていないオブジェクトの集合である。他のオブジェクトの画像によって隠されているオブジェクトの集合が欲しい場合は、全集合から当該集合の補集合をとることで得られる。本実施形態では後者の、他のオブジェクトの画像によって隠されているオブジェクトの集合を取得する。他のオブジェクトの画像によって隠されているオブジェクトは、3D空間で実際に他のオブジェクトによって遮られているオブジェクトの候補となり得るものである。
【００２６】
ここで具体的な判定の方法としては、個々のオブジェクトを単独で独立してレンダリングし、個々のレンダリング結果の画像と、前述のすべてのオブジェクトのレンダリング結果に含まれる個々のオブジェクトの画像が同じかを判定する。同じであれば、当該オブジェクトは隠されていないオブジェクトと判定し、そうでなければ、隠されているオブジェクトと判定することができる。
【００２７】
次に、“オンライン検索結果見積もり処理”について説明する。
【００２８】
図2に、オンライン検索結果見積もり処理の動作のフローチャートを示す。
【００２９】
最初に、リストを初期化する（S201）。3D空間に配置されたオブジェクトの集合を順次描画する。この際、各オブジェクトを1つずつ順番に描画する（S202）。また、オブジェクトの描画では、ピクセルごとに以下の処理を行う（S203）。
【００３０】
すなわち、描画しようとしたピクセルにすでに他のオブジェクトが描かれていた場合（S204のYES）、今描画しようとしているオブジェクト（現在のオブジェクト）が、すでに描画されているオブジェクトより手前にあるかを判断する（S205）。手前にある場合は（S205のNO）、既にあるオブジェクトは、現在描画されているオブジェクトにより隠されていると判定し、当該既にあるオブジェクトの識別子をリストに追加し（S206）、現在のピクセルのデータで、既にあるオブジェクトを対応するピクセルを上書きする（S207）。そうでない場合（S205のYES）、すなわち、現在のオブジェクトがすでに描画されているオブジェクトより後ろにある場合は、現在のオブジェクトがすでに描画されているオブジェクトに隠されていると判定し、当該現在のオブジェクトの識別子をリストに追加し（S208）、描画をスキップする。描画しようとしたピクセルに、何も描かれていない場合は（S204のNO）、オブジェクトを描画する（S207）。
【００３１】
最後にリストを出力する（S209）。リストに含まれているオブジェクトの個数が、他のオブジェクトによって遮られているオブジェクトの個数の上限値の見積もり結果となる。
【００３２】
ここで、“オフライン検索結果見積もり”でも“オンライン検索結果見積もり”でも、描画の解像度（ここでは、実際よりもどの程度大きく描くか、あるいはどの程度小さく描くかを意味する）に依存するため、完全な精度は得られない。解像度に応じて、実際は遮られていないのに描画では隠されていると判定されたり、実際には遮られているのに描画では隠されていないと判定されたりするが、描画の解像度を調整することで、これはどちらかに調整できる。
【００３３】
本実施形態では、解像度を低くめに設定することで（オブジェクトを実際よりも大き目に描くことで）、実際の空間では他のオブジェクトに遮られていなくても、描画において他のオブジェクトの画像により隠されていると判定されることを許容する。ただし実際の空間では他のオブジェクトにより遮られているのに、描画において他のオブジェクトの画像により隠されていないと判定されることはない。このように実際よりも大きく描くことで上記の“オフライン検索結果見積もり”もしくは“オンライン検索結果見積もり”では、実際に遮られているオブジェクトを検索する際の検索結果数の上限値を得ることができる。上限値を利用した探索を行うことで、後述するように効率的な検索が可能となる。
【００３４】
オブジェクト探索部105は、検索結果数見積もり部103の見積もり結果（上限値）に基づいて、あらかじめ与えられた複数の探索戦略の中から適切な探索戦略を選択する。そして、選択した探索戦略に従って、オブジェクトMBBツリー格納部102からツリーを読み出して探索を行う。
【００３５】
具体的な探索戦略は多数考えられ、特定のものに限定されない。本実施形態では、一例として、比較回数削減戦略（第2探索戦略）とキャッシュミス削減戦略（第1探索戦略）を紹介する。比較回数削減戦略は、必要に応じて再帰判定を行うことで、比較回数（判定回数）の削減を目指す探索戦略である。キャッシュミス削減戦略は、探索中にノード到達時に一括してすべての再帰判定を行うことで、オブジェクトMBBツリー格納部102からの読み込み回数（キャッシュミスの回数）の削減を目指す探索戦略である。
【００３６】
図3は、全体の動作の流れを示すフローチャートである。
【００３７】
検索結果数見積もり部103は、レンダリング部104を用いて、他のオブジェクトに遮られているオブジェクト数の上限値を見積もる（S101）。レンダリング部104では、オフラインおよびオンラインのうち、どちらの検索結果見積もり処理を行ってもかまわない。
【００３８】
オブジェクト探索部105は、見積もり数（上限値）を閾値と比較し(S102)、上限値が閾値以下か、閾値より大きいかで、それぞれに応じた異なる探索戦略（探索戦略1、探索戦略2）を選択し、選択した探索戦略で、空間（ツリー）を探索する（S103,S104）。探索により、他のオブジェクトに実際に遮られているオブジェクトを検出する。検索結果出力部106は、当該オブジェクトの一覧を出力する（S105）。
【００３９】
以下、具体的な事例をもとに、実施例A,Bとして、本実施形態の動作を詳細に説明する。
【００４０】
（実施例A）
本実施例では、図4に示すようなオブジェクトの集合に対し、ある視点から見たときに、他のオブジェクトによって遮られているオブジェクトを検索したいとする。
【００４１】
検索結果数見積もり部103では、オフライン検索結果見積もりを行うものとする。
【００４２】
オブジェクト探索部105は、比較回数削減戦略及びキャッシュミス削減戦略のうちのいずれかを選択して実行する。具体的に、検索結果見積もり部103の見積もり結果が3以下の場合は比較回数削減戦略を、3より大きい場合は、キャッシュミス削減戦略を選択するとする。ここの3という数字はあくまで一例であり、実施の値な任意に設定できる。
【００４３】
（実施例Aにおけるオブジェクト階層構造構成部101の動作）
オブジェクト群を入力し、近いオブジェクトを階層的にグループ化することで木構造を構築する。本実施例では、図5に示す木構造が得られたものとする。木構造の葉ノードは、オブジェクトのMBB、それ以外のノードは、グループ化したオブジェクトのMBBを表すノードである。
【００４４】
細かいピッチのハッチングの施された葉ノードは、クエリにマッチするオブジェクト（すなわち、他のオブジェクトによって遮られているオブジェクト）を表す葉ノードである。
【００４５】
また、粗いピッチのハッチングの施された枠は、オブジェクトMBBツリー格納部102からの読み出し単位を表す。たとえばノードaとノードbとは同時に読み出される。ノード4とノード5は同時に読み出される。説明のため、キャッシュメモリには、この読み出し単位のデータを1つのみを格納可能とし、他の読み出し単位のデータが読み出されたときは、既に存在する読み出し単位は上書きされるものとする。たとえばノード4とノード5がキャッシュに存在する状態で、ノード10とノード11が読み出されると、ノード4とノード5は上書きされるものとする。実際には、キャッシュのサイズが大きければ、他のデータを読み出しても前のデータはキャッシュに残っている可能性が高い。しかしながら、この実施例では簡単のため、同時の1つの読み出し単位分のデータしかキャッシュに乗らないという簡単なモデルで説明する。
【００４６】
（実施例AにおけるオブジェクトMBBツリー格納部102の動作）
オブジェクトMBBツリー格納部102は、図5に示すような木構造を記憶する。
【００４７】
（実施例Aにおけるレンダリング部104の動作）
レンダリング部104は、図4に示すような画像を描画（レンダリング）して出力する。
【００４８】
（実施例Aにおけるオフライン検索結果数見積もり部103の動作）
オフライン検索結果数見積もり部103は、視点を表すクエリを受け取り、レンダリング部104を用いてレンダリングを行う。これにより、図4のようなレンダリング結果（描画データ）を得る。図4では、オブジェクトfの画像のみが一部隠されており、オブジェクトf以外のオブジェクトの画像は、すべて完全に見えている。つまり、遮られているオブジェクトは高々1個であると見積もることができる。
【００４９】
（実施例Aにおけるオブジェクト探索部105の動作）
オフライン検索結果数見積もり部103の見積もり結果（上限値）と、閾値を比較する。ここでは閾値を3とする。見積もり結果が3以下であれば、比較回数削減戦略、3より大きければキャッシュミス削減戦略を用いる。見積もり結果は1であり、これは3以下であるため、ここでは比較回数削減探索戦略を採用する。
【００５０】
図6に、比較回数削減探索処理のフローチャートを示す。
【００５１】
探索開始時には、簡単のため、全ノードがキャッシュに存在しないとする。
【００５２】
オブジェクト探索部105は、まずノード1をキャッシュにロードし（S301）、ノード1がクエリを満たす可能性があるか、すなわち、ノード1のMBBが、他のオブジェクトによって遮られているオブジェクトを包含している可能性があるかどうかを、比較・判定する（S303）。なおステップS302は根ノードであるノード1については省略するものとする。ここでは、ノード1のMBBは、他のオブジェクトによって遮られているオブジェクトを含んでいると可能性があると判断される（ステップS303のYES）。ノード1のロード時には、キャッシュミスが発生し、オブジェクトMBBツリー格納部102からの読み込みが発生する。ここで、比較・判定の方法の一例を示す。
【００５３】
一般に、オブジェクトから視点（太陽等）を結ぶ線分の間に他のオブジェクトがあるかどうかを空間探索木によって判定するという技術が既に存在する（他のオブジェクトが存在すれば、上記オブジェクトは影になると判定される）。つまり、そのノードの MBB の各頂点から太陽までを結ぶ線分の間に、他のオブジェクトが存在するかどうかを部分的に検索して判定することができる。他のオブジェクトが1つでも発見されたら、そのノードは影になる可能性があるという事で、「クエリを満たす可能性がある」と判定される。逆に1 つもオブジェクトが発見されなければ、「クエリを満たす可能性はない」と判定される。本実施例では、まず、ノード1のMBBの8個の頂点と、視点（太陽等）を結んで得られる線分のうちの少なくとも1つが、オブジェクトa〜hのいずれかに衝突すれば、ノード1は、クエリを満たす可能性がある（他のオブジェクトに遮られているオブジェクトを包含している可能性がある）と判定する。ここで述べた以外の方法を用いて比較・判定を行ってもよい。
【００５４】
次に、本フローを再帰的に行う再帰探索（S304）に進み、ノード1の子ノードであるノード2とノード3をキャッシュにロードする（S301）。つまり、キャッシュミスが発生し、オブジェクトMBBツリー格納部102からノード2，3の読み込みが発生する。ノード2とノード3がクエリを満たす可能性があるかどうかを比較・判定する。ここでは、比較回数削減探索のため、2つのノードの両方を同時に比較・判定するのではなく、これらのうち任意に選択した片方のみ、比較・判定のみを行う（S302、S303）。ここでは、ノード3が選ばれるとする。ここでは、ノード3は、クエリを満たす可能性があると判定される（S303のYES）。ノード2については、この時点では、比較・判定を行わず、比較・判定を行っていないという情報のみを記憶しておく。
【００５５】
次に、再帰探索（S304）に進み、ノード6とノード7をキャッシュにロードする（S301）。つまり、キャッシュミスが発生し、ノード6，7がオブジェクトMBBツリー格納部102から読み込まれる。ここでは、ノード6が選ばれる。ここでは、ノード6は、クエリを満たす可能性があると判定される（S302、S303のYES）。ノード7については、この時点では、比較・判定を行わず、比較・判定を行っていないという情報のみを記憶しておく。
【００５６】
次に、再帰探索（S304）に進み、ノード12とノード13を、キャッシュにロードする（S301）つまり、キャッシュミスが発生し、ノード12，13がオブジェクトMBBツリー格納部102から読み込まれる。ここでは、ノード12が選ばれたとする。ノード12は葉ノードである。ノード12のオブジェクトｆが、他のオブジェクトによって遮られているかを判定する。つまり、オブジェクトｆのMBBの各頂点と、視点（太陽等）とを結ぶ線分上に他のオブジェクトが存在するか判定される。ここではオブジェクトeが存在すると判定される。つまり、オブジェクトfはオブジェクトeによって遮られていると判定される。ここで、見積もり結果の値（上限値）は1である。1個の遮られたオブジェクトが発見されたので、これ以上遮られたオブジェクトが見つかることはないとわかる。よって探索は終了する。なお、もし、ノード12より先にノード13が選択されたときは、ノード13がクエリを満たさないと判定され、次に兄弟ノードであるノード12が選択され、上記のようにクエリを満たすと判定され、探索が終了する。
【００５７】
（実施例Aの効果）
図7に示すように、本実施例の比較回数削減探索では、比較回数は4回、キャッシュミスは4回であった。
【００５８】
もし仮に、比較回数削減探索ではなく、キャッシュミス削減探索を採用していた場合を考えると、ノード1、ノード2、ノード3、ノード6、ノード7、ノード12、ノード13と、合計7回の比較が行われ、キャッシュミスの回数は同じ4回となる（図7参照）。キャッシュミスの回数が同じであれば、比較回数が少ないほうが効率的である。このように本実施例は、少ない比較回数で探索を終えることができる。なお、キャッシュミス削減探索の動作は後述する。
【００５９】
もっとも、これは、ノードの非決定的な選択(ノード2とノード3の選択など)において、すべて最適な選択が可能であった場合の評価であるため、実際には比較回数は4回より多くなる可能性がある。しかしそれでもキャッシュミス削減探索と同じ7回が上限であり、キャッシュミス削減探索では常に7回の比較が行われるので、ほぼ常に効率的な選択をすることができる。
【００６０】
（実施例B）
本実施例では、図8に示すようなオブジェクトの集合に対し、他のオブジェクトによって遮られているオブジェクトを検索したとする。
【００６１】
検索結果数見積もり部103では、オンライン検索結果見積もりを行うものとする。
【００６２】
オブジェクト探索部105では、比較回数削減戦略及びキャッシュミス削減戦略のうちのいずれかを選択して実行する。具体的に、検索結果見積もり部103の見積もり結果が3以下の場合は比較回数削減戦略を、3より大きいの場合は、キャッシュミス削減戦略を選択するとする。
【００６３】
（実施例Bにおけるオブジェクト階層構造構成部101の動作）
オブジェクト群を入力し、近いオブジェクトを階層的にグループ化することで木構造を構築する。木構造の葉ノードはオブジェクトのMBB、それ以外のノードはグループ化したオブジェクトのMBBを表すノードである。本実施例では、図9に示す木構造が得られたものとする。細かいピッチのハッチングが施された葉ノードは、クエリにマッチするオブジェクトを表す葉ノードである。
【００６４】
また、粗いピッチのハッチングの施された枠は、オブジェクトMBBツリー格納部102からの読み出し単位を表す。実施例Aと同様、キャッシュメモリには、この読み出し単位のデータを1つのみを格納可能という簡単なモデルで説明する。
【００６５】
（実施例BにおけるオブジェクトMBBツリー格納部102の動作）
オブジェクトMBBツリー格納部102は、図9に示すような木構造を記憶する。
【００６６】
（実施例Bにおけるレンダリング部104およびオンライン検索結果数見積もり部103の動作）
オンライン検索結果数見積もり部103は、視点を表すクエリを受け取り、レンダリング部104により描画（レンダリング）を行う。
【００６７】
レンダリング部104は、図2に示した動作フローに従って、全オブジェクトを順次描画していく。ここでは、オブジェクトaからhをこの順に描画したとする。最終的な描画結果は図8のようになる。
【００６８】
まず、他のオブジェクトの画像によって隠されているオブジェクトの識別子を保存するためのリストを空として初期化する（S201）。
【００６９】
空の背景に対してオブジェクトaを描画する。描画領域に他のオブジェクトは存在しないので、そのままオブジェクトaを描画する（S204のNO、S207）。
【００７０】
同様にオブジェクトbも描画する（S204のNO、S207）。
【００７１】
次にオブジェクトcを描画するが、これを描画しようとした一部のピクセルに、オブジェクトbが描画済みである。そして、現在描画しようとしているオブジェクトcの方が手前にある。よって描画済のオブジェクトbの識別子をリストに追加する（S204のNO、S206、S207）。
【００７２】
次にオブジェクトd、eを描画する。共に他にオブジェクトが描かれていない領域に描画しようとするため、そのまま描画する（S204のNO、S207）。
【００７３】
次にオブジェクトfを描画するが、これを描画しようとした一部のピクセルに、オブジェクトeが描画済みである。そして、すでに描画されているeの方が手前にある。よって現在描画しようとしているオブジェクトeをリストに追加する（S204のYES、S205のYES、S208）。
【００７４】
同様に、オブジェクトg、hも、他のオブジェクトが手前にあることがわかる。よって現在描画しようとしているオブジェクトg,hをリストに追加する（S204のYES、S205のYES、S208）。
【００７５】
以上を終えると、リストを出力する（S209）。リストの長さは4である。よって見積り数(上限値)は4である。
【００７６】
（実施例Bにおけるオブジェクト探索部105の動作）
オフライン検索結果数見積もりの結果が3以下ではないため、ここではキャッシュミス回数削減探索を採用する。
【００７７】
図10にキャッシュミス削減探索処理のフローチャートを示す。
【００７８】
探索開始時には、簡単のため、全ノードがキャッシュに存在しないという前提とする。
【００７９】
比較回数削減探索処理では、まずノード1をキャッシュする（S401）。つまり、キャッシュミスが発生し、ノード1のデータをオブジェクトMBBツリー格納部102からCPUに読み込む。判定結果を格納する配列を初期化する（S402）。ステップS403は、根ノードであるノード1についてはスキップする。ノード1がクエリを満たす可能性があるかどうかを比較・判定する（S404）。ここでは可能性があり（再帰すべき）と判定され、判定結果を上記配列に保存する（S404）。ステップS405は根ノードであるノード1についてはスキップする。ステップS406では、ノード1について再帰すべきとの判定結果が上記配列に記録されているため、本フローを再帰する再帰探索（S407）へ進む。
【００８０】
次に、ノード1の子ノードであるノード2とノード3をキャッシュにロードし、ノード2，3に対する配列を初期化する（S401,S402）。つまり、キャッシュミスが発生し、オブジェクトMBBツリー格納部102からの読み込みが発生する。ノード2，3がクエリを満たす可能性があるかどうかを比較・判定する(S403、S404)。前述した比較回数削減探索では、片方のノードについてのみ比較・判定だけ行うが、本キャッシュミス回数削減探索では、両方の比較・判定を行う。ノード2，3ともクエリを満たす可能性がありと判定され、判定結果を配列に格納する（S404）。ステップS406では、ノード2，3とも再帰すべきとの判定結果が記録されているため、いずれか一方のノードを選択し、再帰探索する。ここでは、ノード2を選択し、ノード2について再帰探索を行う（つまり、ノード2の方から木を降りるとする）（S405、S406、S407）。
【００８１】
次に、ノード4とノード5についても、ノード2，3と同様の処理を行う（S401、S402、S403、S404、S405、S406）。この場合も、キャッシュミスが発生し、オブジェクトMBBツリー格納部102から読み込みが発生する。ノード4，5とも再帰すべきとの判定結果が、ノード4，5に対する配列に記録される。ここではノード4を選択し、再帰探索する。
【００８２】
次に、ノード4の子ノードであるノード8とノード9をキャッシュにロードし、ノード8，9に対する配列を初期化する（S401,S402）。つまり、キャッシュミスが発生し、オブジェクトMBBツリー格納部102からの読み込みが発生する。ノード8，9がクエリを満たす可能性があるかどうかを比較・判定する(S403、S404)。ノード8とノード9は葉ノードである。ノード9がクエリを満たし、これによりオブジェクトbが発見される。ノード9はクエリを満たさないと判定される。ノード8、9はいずれも葉ノードであるため、再帰すべきでないとの判定結果が配列に記録される。これで葉ノードまで探索が完了したが、まだ見積もり数（上限値）に至っていない。このため、探索を続行しなければならない。このため、ノード4とノード5に戻る（ステップS406のNO）。
【００８３】
ノード4，5では、先とは別の子ノードを選択する (つまりノード5の方から木を降りる)。この時、比較回数削減探索であったら、この時にノード5から降りるべきか(再帰すべきか)どうかを判定するため、キャッシュミスが発生して、再度、オブジェクトMBBツリー格納部102からノード4，5を読み出す必要がある。これに対し、本実施例のキャッシュミス回数削減探索では、すでにノード5について再帰すべきかは判定済み(再帰すべきという判定)なので、キャッシュへのアクセスは行われない。したがって、キャッシュミス（オブジェクトMBBツリー格納部102からの読み出し）は発生しない。これにより、比較回数削減探索に比べてキャッシュミスの回数が減る。ここでは、ノード5から木を降りる（S407）。
【００８４】
次に、ノード5の子ノードであるノード10とノード11についても、ノード8、9と同様の処理を行う（S401〜S405のS406のNO）。このとき、キャッシュミスが発生し、ノード10，11の読み込みが行われる。ノード10、11はいずれも葉ノードであるため、再帰すべきでないとの判定結果が、配列に記録される。ノード10とノード11は葉ノードであるが、いずれのノードもクエリを満たさない。
【００８５】
次に、ノード4とノード5に戻るが、これ以上降りるべき子ノードはないので、さらにノード2とノード3に戻る。ノード3については、ノード2，3に対する配列に、再帰すべきとの判定結果が記録されており、今度はノード3を選択する（ノード3から木を降りる）。
【００８６】
次に、ノード3の子ノードであるノード6とノード7についても、ノード4，5と同様の処理を行う（S401〜S405のS406のYES）。このとき、キャッシュミスが発生し、オブジェクトMBBツリー格納部102からの読み込みが発生する。ノード6，7に対する配列には、いずれも再帰すべきとの判定結果が記録される。ここでは、ノード6の方から木を降りるとする（S407）。
【００８７】
次に、ノード12とノード13について、ノード8，9と同様の処理を行う（S401〜S405、S406のNO）。キャッシュミスが発生し、ノード12，13の読み込みが行われる。ノード12、13はいずれも葉ノードであるため、再帰すべきでないとの判定結果が、配列に記録される。ノード12とノード13は葉ノードである。ノード13がクエリを満たすので、オブジェクトfが発見される。なお、ノード12はクエリを満たさない。ノード6とノード7に戻り、ノード7の方から木を降りる（S407）。
【００８８】
次に、ノード7の子ノードであるノード14とノード15について、ノード12，13と同様の処理を行う（S401〜S405、S406のNO）。キャッシュミスが発生し、ノード14，15の読み込みが行われる。ノード14とノード15は葉ノードである。共にクエリを満たすので、オブジェクトgとhが発見される。これで見積もり数（上限値）と同じ数が発見されたので探索を終了する。
【００８９】
（実施例Bの効果）
本実施例では、図11に示すように、比較回数は15回、キャッシュミスは8回であった。
【００９０】
もし仮に、キャッシュミス削減探索ではなく、比較回数削減探索を採用していた場合を考えると、上位のノードに戻るたびにキャッシュミスが発生する(前述したように、この実施例では簡単のため、同時の1つの読み出し単位（兄弟ノード群）しかキャッシュに乗らないという簡単なモデルで説明している)ので、合計15回の比較が行われ、キャッシュミスの回数は11回となる（図11参照）。比較回数が同じであれば、キャッシュミスの回数が少ないほうが効率的である。
【００９１】
このように本実施例は、少ないキャッシュミス（読み出し回数）で探索を終えられる。
【００９２】
（変形例）
上記実施形態では、レンダリング部を用いて、他のオブジェクトの画像によって隠されているオブジェクト数を算出し、当該オブジェクト数を上限値として、探索を行うことで、他のオブジェクトによって遮られているオブジェクトを検出した。別の方法として、以下に示す方法を用いても良い。検索結果数見積もり部（算出部）では、レンダリング部を用いて、少なくとも一部の画像の他のオブジェクトの画像によって隠されているオブジェクトを識別する。オブジェクト探索部では、当該識別されたオブジェクトについてのみ、当該オブジェクトが他のオブジェクトによって遮られているかを検査する。識別されるオブジェクトの個数が少ない場合などは、この方法によっても効率的な探索が可能となる。図4および図5の例では、検索結果数見積もり部が、他のオブジェクトeの画像によって一部の画像が隠されているとして、オブジェクトfを識別する。そして、オブジェクト探索部が、オブジェクトfが空間において他のオブジェクトによって実際に遮られているかを判定する。ここでは、オブジェクトfはオブジェクトeによって遮られていると判定される。
【００９３】
以上、本実施形態によれば、他のオブジェクトによって遮られているオブジェクトを効率よく検索することができる。たとえば、PV（PV：Photovoltaic power generation）装置やビルをオブジェクトとし、ビル等の建物の陰になっているPV装置を検索できる。これにより、物陰になるかどうかを考慮したPV配置の検討が可能となる。また、高速な3Dレンダリングが可能になる。機械の部品配置や建物の設計等、CAD一般への応用も可能である。
【００９４】
なお、以上に説明した本実施形態におけるオブジェクト検索装置は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることで実現することが可能である。すなわち、オブジェクト検索装置の各処理部は、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、オブジェクト検索装置は、上記のプログラムをコンピュータ装置にあらかじめインストールすることで実現してもよいし、CD-ROMなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現してもよい。また、オブジェクト検索装置内の格納部102は、装置内もしくは外付けのメモリ装置およびハードディスク、あるいは、CD-R, CD-RW, DVD-RAM, DVD-R 等の記録媒体によって構成されてもよい。
【図１】
2014059839.tif 000003
【図２】
2014059839.tif 000004
【図３】
2014059839.tif 000005
【図４】
2014059839.tif 000006
【図５】
2014059839.tif 000007
【図６】
2014059839.tif 000008
【図７】
2014059839.tif 000009
【図８】
2014059839.tif 000010
【図９】
2014059839.tif 000011
【図１０】
2014059839.tif 000012
【図１１】
2014059839.tif 000013