論文――――――――――――――――――――――――――――――――――――

空間的関係に基づく視点位置可視化機構の実現方式
Classification
andVisualization
Viewpoints by Using a Function
Recognizing Spatial Relationships

木村 直希♥

細川 宜秀♦

offor高橋 直久♦

Naoki KIMURA Yoshihide HOSOKAWA
Naohisa TAKAHASHI
ある時点における検索者の状況を再現する機能は，その時点における空間上に配置されたオブジェクト群からの獲得要求に適合するオブジェクト検索の本質的機能として位置づけられる．
本稿では，再現する検索者の状況として検索者の視点位置を設定し，与えられた空間的関係が視認できる視点位置を可視化する方式について述べる．本方式の実現にあたり，2 つのオブジェクト間の空間的関係が，検索者の注視対象と視点位置に応じて動的に変化することに着眼する．
本方式の主要な特徴は，注視対象を中心とし，注視対象から視点位置までの距離を半径とする球体を空間的関係毎に色分けすることによって，視点位置から視認される空間的関係を可視化する点にある．本方式の実現によって，たとえば，2 つのオブジェクトが重なって見えていたという記憶から，それを視認できる視点位置を特定することが可能になる．すなわち，検索者の記憶から，検索者がその空間的関係を視認した状況を再現することが可能になる．
本稿では，本方式を実装した実験システムを介して，検索者の状況が再現されることを明らかにする．
It is essential to realize functions for finding a location
to enhance location-based services. A function forclassifying locations is designed as one of such functions.
In this paper, we present a method for classifying andvisualizing
viewpoints
byrecognizing
spatialrelationships. A spatial relationship between two objectsdynamically changes according to a location where a userviews the objects. That is, it is possible to classify user'sviewpoints (locations) by spatial relationships which theuser recognizes.
The main feature of our method is to compute spatial
relationships in some viewpoints and to estimate spatial
relationships which the user views around the viewpoints.
By this strategy, our method makes it possible to classify
all user’s viewpoints in a continuous space.
We clarify the feasibility and effectiveness of ourmethod by several experiments.

1. はじめに近年のモバイル・コンピューティング技術の発展にとも♥

学生会員 名古屋工業大学大学院工学研究科博士前期課程
kimura@moss.elcom.nitech.ac.jp♦
正会員 名古屋工業大学大学院工学研究科{hosokawa,nahohisa}@elcom.nitech.ac.jp

1

DBSJ Letters Vol.2, No.2

ない，検索者の状況（位置）に応じた空間情報検索システム(LBS:Location Based Service)に注目が集まっている．
しかし，LBSにおいては，検索者から位置を入力されることを前提にシステムが構築されており，検索者から位置が与えられない状況には適用困難であるといえる．検索者は常に位置を提供できる状況にはないので，検索者から位置を提供できるようにするためのシステムの実現は，その情報検索システムの利用価値を増大させる．
このことから，検索者の状況を再現する機能は，検索者が提供したい位置を特定するための本質的機能の1つとして位置づけられる．
本稿では，視点位置に応じて視認される空間的関係が異なることに着目し，視認される空間的関係毎に視点位置を分類可視化するためのシステムの実現方式を提案する．
これによって，検索者が位置を与えられない状況において，その位置を特定するための1手段を検索者に提供可能になる．
提案方式は，次の2つの特徴を持つ．
特徴‑1 連続空間において2つのオブジェクト間の空間的関係を視認する状況の再現機能の実現
連続空間において取り得る視点位置は無限に存在し，すべての視点位置から2つのオブジェクトが視認できる空間的関係の計算は困難である．このため，提案方式では次の機能の実現により，連続空間において取り得るすべての状況を近似して再現することを可能にする．
この機能は次の3つの機能から構成される．
機能‑1 連続空間に属する視点位置から有限個の視点位置(代表点)をサンプリングする機能
機能‑2 各代表点から視認される2つのオブジェクトの空間的関係を計算する機能
機能‑3 隣接する代表点の間から視認される空間的関係の推定機能
特徴‑2 多様な形状を持つオブジェクト群を対象とした状
況再現機能の実現提案方式では，先に述べた(機能‑1,3)はオブジェクトの形状に依存しないように実現する．また，(機能‑2)は既存方式を用いて，各代表点から視認される空間的関係を計算する．
ここで，(機能‑2)において利用する既存方式は多様な形状のオブジェクトを評価対象とする．
これらの機能により，提案方式は多様な形状を評価対象とすることが可能になる．これによって，多様な形状を持つオブジェクト群から検索者の状況を再現可能にする．

2. 状況再現機能の実現方式
提案する状況再現機能は，2 つのオブジェクト間の空間的関係を視認するすべての視点位置を分類し，提示するものである．
具体的には，我々は，空間上における 2 つのオブジェクト間の空間的関係が，それを視認する位置（視点位置）に応じて変化することに着眼し，2 つのオブジェクト間の空間的関係を全方位から計算し，色分けして提示する機能を実現する．
提案方式では，まず，連続空間に存在する視点集合から有限個の視点位置をサンプリングし，その視点位置から視認される空間的関係を計算する．次に，隣接する視点位置間から視認される空間的関係を推定する．そのため，次の 5 項目を入力としてとる．ここで，サンプリングした視点位置を代表点

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――
Step‑1(a)(b)Z
2π注視点 FN

注視点から視点までの距離 R

θ=Pj+1i

空間的関係
推定面
ji+1Pj+1i+1Pj

Z

Overlap Step3 (d)ZContain

Overlap

YX

X

代表点 Pj

Disjoint

Y

Disjoint

Overlap

図1Pi

Step‑2 (c)

Z

Y

X

DBSJ Letters Vol.2, No.2

Y
X

Disjoint

提案方式の実行手順例
Pij
P0

注視点 F

jPi+1j+1Pi

P j+1i+1(a)代表点が全て同じ空間的関係である場合の推定例

注視点から視点までの距離 RPijP ij+1jPi+1

P j+1i+1(b)代表点が全て異なる空間的関係である場合の推定例
図 2 代表点と空間的関係推定面
Overlap

視点の位置

接平面
注視している方向
接平面
Disjoint
図 3 代表点において視認される 2 つのオブジェクト間の空間的関係の算出例と定義する．図 2 では具体的な代表点を表している．
オブジェクト O-1
オブジェクト O-2
検索者の注視点 F
注視点から視点位置までの距離 R
詳細度 N
詳細度 N は，隣接する代表点の間隔を決定するための入力値である．この値が大きいほど，代表点の間隔が小さくなり，空間上にとりうるすべての状況がより正確に再現される．
提案方式は，次の手順によって，与えられた 2 つのオブジェクト（O-1，O-2）を視認する検索者の状況を再現する．
Step-1 代表点の決定
F を中心とし，半径 R の球体表面において，Ｚ軸方向ならびに，ＸＹ軸方向に隣接する代表点の間隔が等間隔になるような代表点の集合を求める．
ここで，本稿では代表点を Pi j と表記し添え字 i，j によって代表点を識別する．添え字 i はＺ軸方向に隣接する代表点の識別子を表し，添え字 j はＸＹ軸方向に隣接する代表点の識別子を表す．
Step-2 各代表点における 2 つのオブジェクト間の空間的関係の算出
Step-1 で求めた各代表点について，その代表点から注視点を注視するときに視認されるオブジェクト O-1，O-2 間の空間的関係を計算する．
Step-3 隣接する代表点間で視認される空間的関係の推定

2

図 4 空間的関係推定面での空間的関係の推定例
図で表されているような，代表点 Pi j ， Pi +j 1 ， Pi j +1 ， Pi +j1+1 によって囲まれた 4 角形部分球面内(空間的関係推定面)において視認される空間的関係を推定し，配色を行う．図 1 は，提案する状況再現機能の実行例を図示している．
図 1(a)では，F を中心とし，半径 R の球体表面から，円柱と直方体が取り得るすべての空間的関係を計算する．また，
図 1(a)(b)では，代表点の位置を中心 F，半径 R，詳細度 N から求める．図 1(d) では，隣接する代表点間の視認される空間的関係を補完している．この手順によって，視点位置が，円柱と直方体間の空間的関係に応じて分類される．そして，検索者はこの分類にしたがい，欲する視点位置の特定を行う．

2.1 各代表点における 2 つのオブジェクト間の空間的関係の算出方式
ここでは，各代表点における 2 つのオブジェクト間の空間的関係の算出方式について述べる．
ある 1 つの代表点における 2 つのオブジェクト間の空間的関係は，次の実行手順によって算出する．
Step-2.1.1 その代表点を含み，中心 F 半径 R の球体の接平面にオブジェクト O-1，O-2 を投影する．
ここでは，一点透視投影法にしたがい，それらのオブジェクトをその接平面に投影する．一点透視投影法を採用した理由は，この手法が，人間が視認するオブジェクト間の関係をほぼ再現できるためである．
Step-2.1.2 オブジェクト O-1，O-2 の投影像間の空間的関係を算出する．
ここで，提案方式が算出対象とする空間的関係をオブジェクト間の位相関係[1]とする．具体的には，Disjoint, Overlap,Contain, Cover, CoveredBy, Inside, Cover, Meet, Equalのうちの 1 つの空間的関係が算出される．
Step-2.1.3 代表点に割り当てる色を決定する．
提案方式では，あらかじめ各空間的関係に対する色の割り当て表を作成しておく．そして，Step-2.2 で算出された空間的関係に該当する色をその表から検索し，その代表点の色を決定する．ここで，図 3 は，2 つの代表点で視認される円柱と直方体間の空間的関係の算出例を表す．それぞれの視点位

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――
表12 つのオブジェクトの配置関係

DBSJ Letters Vol.2, No.2

提案方式による視点位置の可視化結果
立方体と立方体離れている

接している

離れている

円錐と円柱接している

詳細度 8jPi
45jPi+1

詳細度 36

10jPijPi+1

詳細度 360

1jPijPi+1

置から視認される空間的関係は異なるため，それら 2 つの視位置には異なる色が割り当てられる．
このように，代表点は，空間的関係に応じて分類される．

2.2 隣接する代表点間において視認される空間的関係推定
ここでは，隣接する代表点間で視認される空間的関係の推定方式ついて述べる
提案方式では，次の手順によって空間的関係の推定を行う．
Step-2.1.1 すべての空間的関係推定面の抽出
Step-2.1.2 各空間的関係推定面内において視認される空間的関係の推定
まず，Step-3.1 によって抽出された各空間的関係推定面を各辺の中点を頂点に持つ 4 つの球面に分割し，各面に代表点の色を割り当てる．
次に，図 4(a)のように隣接する代表点に割り当てられた色が同一色の場合は，この空間的関係面を代表点と同一色で塗る．隣接する代表点に割り当てられた色が異なる場合，色の違いを吸収するために，連続的な色の変化を施す．これは，連続空間において，視認される空間的関係が切り替わる地点を厳密に求めることは困難なので，代表点間の色の変化が連続的になるように配色することによって，空間的関係内で視認される空間的関係が厳密に計算できなかったことを提示するための処理である．たとえば，4 つの代表点すべてが異なる場合，図 4(b)のように塗られる．
もし，空間的関係推定面内において視認される空間的関係をより正確に求める場合には，詳細度を大きくすればよい．
このことにより，球面上における代表点の数の増大が可能となる．その結果，空間的関係推定面が縮小するため，その面内において視認される空間的関係をより正確に推定可能になる．

3. 実験
本節では，可視化結果の制御パラメータである詳細度を導入することよって，検索者の要求に対応した可視化が可能に

3

表2提案方式による視点位置の可視化に要する時間
立方体と立方体
円錐と円柱
2 つのオブ 離れてい 接してい 離れてい 接していジェクトの る
る
る
る
配置関係
詳細度 80.037[秒] 0.068[秒] 0.266[秒] 0.234[秒]
詳細度 360.330[秒] 0.574[秒] 4.153[秒] 4.375[秒]
詳細度 360 25.68[秒] 48.25[秒] 387.4[秒] 406.9[秒]
なることを明らかにする．

3.1 実験方法
本実験においては２つのオブジェクトを配置した４つの三次元空間を考える．
3 次元空間-1: 2 つの立方体を離して配置
3 次元空間-2: 2 つの立方体を接するように配置
3 次元空間-3: 円柱と円錐を離して配置
3 次元空間-4: 円柱と円錐を接するように配置
ここで，提案方式において導入した詳細度は，球面上にとる代表点数を決定するパラメータであり，提案システムによる可視化結果生成時間を制御するのに使用できる．すなわち，詳細度は，可視化結果の正確さと生成時間のバランスを検索者が決定できる重要なパラメータとして位置付けられる．
そこで，3 つの詳細度（N = 8, 36, 360）を上記 4 つの 3次元空間に適用し，検索者が要求する生成時間に対して妥当な可視化結果が生成されることを検証する．
さらに，この検証から詳細度導入の妥当性を明らかにする．
本実験において，実験システムを Java 言語によって実装した．具体的には，可視化結果を表現するためのデータ構造として VRML2.0[2]形式を使用し，VRML によって記述された可視化結果を Java3D[3]によって表示するシステムを構築した．さらに，JTS[4]を用いて，Step-2 において空間的関係を算出するための機構を実装した．この実験システムを，視点位置の分類だけでなく，評価対象となるオブジェクトも視認できるように構築した．
なお，実験システムの実行環境は次のとおりである．
CPU : Intel Celeron 2.0GHz

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――
RAM : PC2100 512MByte
OS : WindowsXP Professional

3.2 実験結果と考察
表 1 は，4 つの 3 次元空間に提案方式を適用して可視化した視点位置を表す．これらの結果より，提案方式がオブジェクトの形状・配置間隔を変化させた場合，オブジェクトの形状・配置間隔に応じて視点位置が分類されることを確認した．
なお，表 1 において，空間的関係が成り立つ部分の配色が淡い配色となっている．このため，モノクロ印刷では各空間的関係が成り立つ部分が識別しにくいが，カラー印刷では分類されている様子が明瞭に表示される．
可視化結果の正確さと生成時間のトレードオフを制御するためのパラメータである詳細度を導入することの妥当性について検証する．ここで，表 2 は，提案方式による視点位置の可視化結果生成時間を示している．
本実験において詳細度 8，36，360 における代表点の数が64，1024，102400 となることから，代表点数の増大に比例して可視化結果生成時間が増大することを確認した．
また，詳細度 36 と詳細度 360 の可視化結果において，視認される空間的関係が切り替わる境界がほぼ同じであった．
この結果より，短い時間で可視化結果を生成しなければならない状況において，提案方式がほぼ正確な可視化結果を生成することを確認した．一方，生成時間を問わずに，より正確な可視化結果を生成しなければならない状況において，提案方式がより正確な可視化結果を生成することを確認した．
これらの結果より，詳細度は，可視化結果の正確さと生成時間のバランスを検索者が決定できる重要なパラメータとして有効であることを確認した．これより，詳細度導入の妥当性を明らかにした．
以上より，提案方式が状況再現機能の実現方式として妥当であることを明らかにした．

4. 関連研究
本節では，関連研究と，本研究の比較により，提案方式の位置づけを明らかにする．
まず，LSB の具体例に対する提案方式の位置づけについて述べる．
LBS は利用者の位置を入力として検索者の獲得要求に適合する情報を提供するシステムである．具体的なシステムとして[5],[6],[7]などが提案されている．
提案方式は，検索者の位置を検索者が入力困難な状況において，その入力を支援する方式として位置づけられる．これ
より，提案方式は検索方式が利用可能な状況を増加させるので LBS の利用価値を増大させる．
次に，現在までに提案されている空間におけるナビゲーションシステムに対する提案方式の位置づけについて述べる．
仮想三次元空間のナビゲーションシステム[9],[10]が提案されている．
提案方式において，利用者のそのときの状況，すなわち検索者の視認できる 2 つのオブジェクト間の空間的関係から位置を計算することが可能となる．提案方式の実現により，視認される空間的関係を使用しながら，検索者の位置を決定し，それに応じた空間のナビゲーションを可能にする．このことにより，提案方式はナビゲーションシステムの利用価値を増大させる．

4

DBSJ Letters Vol.2, No.2

5. おわりに検索者の状況を再現する機能は，検索者が提供したい位置を特定するための本質的な機能の 1 つとして位置づけられる．
本稿では，検索者の再現する状況を視点位置に設定した．
また，2 つのオブジェクト間の視認される空間的関係が視点位置によって変化することに着目し，視点位置を空間的関係毎に分類したうえで可視化する方式を提案した．
提案方式の特徴は次のとおりである．
特徴-1: 連続空間におけるすべての状況の再現機能の実現
特徴-2: 多様な形状を持つオブジェクト群を対象とした状
況再現機能の実現
また，提案方式の妥当性を提案方式を実装した実験システ
ムを介して実験することにより示した．
今後の展望として， 3 つ以上のオブジェクト間の空間的関係や不透明物体への適用，処理の高速化などが挙げられる．

[文献］[1] Egenhofer, M. J.: Spatial Relations Models,Inferences
and their Future Application, Proc. Advanced
DatabaseSymposium ’96, separatevolume (1996).
[2] VRML2.0: http://www.web3d.org/x3d/[3] JTS: http://www.vividsolutions.com/JTS/main.htm[4] Java3D: http://java.sun.com/products/java-media/3D/[5] 寺田努，塚本昌彦，西尾章治郎：アクティブデータベースを用いた地理情報システム, 情報処理学会論文誌，Vol. 41，
No. 11，pp.3103-3113 (2000)．
[6] 森下健, 中尾恵, 垂水浩幸, 上林弥彦：時空間限定オブジェクトシステム: SpaceTag プロトタイプシステムの設計と実装, 情報処理学会論文誌,Vol.41, No.10, pp.2689-2697 (2000).
[7] 藤田秀之，有川正敏，岡村耕二：撮影ベクトル場モデルに基づく空間データとしての写真利用，データベースとＷＥ
Ｂ情報システムに関するシンポジウム，pp.33-39 (2002)．
[9] 宮原伸二, 小川剛史, 塚本昌彦, 西尾章治郎：擬似3 次元空間の背景となる静止画の視点選択方法について, 情報処理学会研究報告, DBS-119-11, pp.61-66 (1999).
[10] 松本尚宏, 小磯健吾, 田中克己：方向依存の3 次元空間内容記述と3次元ガイドツアー，情報処理学会研究報告，DB
S-116-54, pp.209-216 (1998)．

木村 直希

Naoki KIMURA

名古屋工業大学大学院工学研究科博士前期課程在学中．2003
年名古屋工業大学工学部電気情報工学科卒業．地理情報シス
テム，空間データ検索システムの研究に従事．

細川 宜秀

Yoshihide HOSOKAWA

名古屋工業大学大学院工学研究科助手．1999 年筑波大学大学
院博士課程工学研究科電子・情報工学専攻中退，工学博士．
マルチデータベースシステム，ドキュメント・データ検索シ
ステム，地理情報システムの研究に従事．情報処理学会会員．

高橋 直久

Naohisa TAKAHASHI

名古屋工業大学大学院工学研究科教授．1976 年電気通信大学大学院修士課程修了．同年，日本電信電話公社（現 NTT）武蔵野電気通信研究所入所．2001 年より現職．ネットワークコ
ンピューティング，時空間情報処理の研究に従事．工学博士（東工大）．ACM，電子情報通信学会，情報処理学会，日本ソフトウェア科学会各会員．

日本データベース学会 Letters Vol.2, No.2