論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――

地図の 3 次元グリッド表現に基づくユーザの相対的位置検索法
A User’s Location Identification Method
using Relative Position Information basedon a 3-D Grid Representation of Map

佐藤 玲奈♥

増永 良文♠

Reina SATO

Yoshifumi MASUNAGA

本論文では，＜前に何々が見える＞というような間接的表現である“相対的な位置情報”を用い 3 次元位置検索を考案した．相対的位置情報から位置を推定することは空間インデックス作成(R-Tree，四分木，等)，空間演算など通常であれば多くの計算を必要とする．そこで，連続空間を近似した 3次元グリッドを導入することで，道路と建物を簡素にモデル化して，さらに建物を構成する各グリッドに対し，視点となるべきグリッドからの可視・不可視判定を事前計算しておき，事前計算結果と相対的位置情報を用いた簡便な計算による位置推定法を提案する．
This paper proposes a novel 3-dimensional location
identification method that uses "relative location
information" like “I can see a department store front.”
Most of the traditional methods of identifying theposition use spatial indices such as R-Tree and QuadTreeor spatial operations which tend to need tremendous
amount of computing resources. Instead, we propose a
simple position presumption method that uses a
pre-computed city map and relative position information.
The pre-computation includes both the simple 3D grid
representation of the real world and the result of thevisibility of buildings from each viewpoint on the grid.

1. はじめに
近年，モバイルコンピューティング技術やコンピュータの高性能化，小型化が進み，コンピュータを持ち歩き様々な情報を享受する環境が普及してきた．位置情報をGPSにて取得できる携帯端末も一般的になり，位置情報は企業活動や市民生活に不可欠な存在となりつつある．しかし，ヒトとヒトの間の意思疎通はいまだ曖昧表現で位置情報を伝達しており，自分の位置を伝える際に緯度経度や住所などの直接的位置表現ではなく，「前に何々が見える，右に何々が見える」のような間接的表現を用いている．このような建物名と方向関係[1,2]を組み合わせた表現を相対的位置情報と定義する．
相対的位置情報を用いてヒトの位置が推定可能になると日常の様々なシーンで活用できうる．
本論文では，相対的位置情報を用いた3次元位置検索法を考察する．相対的位置情報から位置を推定することは空間インデックス作成(R-Tree，四分木)や空間演算など通常であれ♥学生会員 お茶の水女子大学大学院人間文化研究科博士前期課程 reina@db.is.ocha.ac.jp♠正会員 お茶の水女子大学理学部情報科学科
masunaga@is.ocha.ac.jp

1

ば多くの計算を必要とするが，新たに提案する方法では，道路や建物オブジェクトの3次元グリッドを用いることで簡便な計算により位置推定を可能とする．また3次元グリッドを活用することは，2次元グリッドを用いた位置推定よりも現実世界の投影能力が高い．ある地点から建物オブジェクトが「見える，見えない」は通常多くの計算を要するが，3次元グリッドを用いて道路・建物オブジェクトを簡素モデル化することで事前計算を可能とし，その結果を用い瞬時に位置推定を行う．3次元グリッドを用いた簡便な表現は現実世界の投影であり，非力なコンピューティング環境でも実用性が高いため，モバイル携帯端末などでも応用可能であろう．

2. 位置検索システム概要
相対的位置情報を用いた位置検索システムの概要を図1に示す．地図ＤＢを用いて3次元グリッドから道路・建物オブジェクトを構成する内部の3次元グリッドを抽出する（以下，道路・建物オブジェクトグリッドという）．抽出したオブジェクトグリッドを用い可視・不可視判定をすることで，地図データを事前計算により索引付けする．ユーザ入力（KeyboardもしくはVoice）による相対的位置情報と索引を用い瞬時に位置検索を行い，結果を地図上に表示して推定したユーザの位置を表示する．

図1
Fig.1

位置検索システム構成の概要

An Overview of Location Identification System

3. オブジェクトグリッド可視・不可視判定法
3.1

3 次元グリッド近似法

相対的位置情報を用いた位置検索の計算方法として，建物オブジェクトの多様な形状を考慮した計算を行う場合，本来，空間は連続空間であるためユーザの位置は「点」では求まらず，ある「範囲」に決定される[3,4]．またユーザが指定する相対的方向関係は時として大雑把であり，“前”に見えるといっても正面ではないこともあるため，方向指定に曖昧性を許容できるモデル化が望ましい．そこで，本論文では連続空間を 3 次元グリッド近似するモデル化を考えた．それによりユーザの尤もらしい位置をピンポイントで特定でき，計算コストの削減にも繋がる．
3 次元グリッド生成法は，経度幅 1/8 度，緯度幅 2/3 度の約 10ｋｍ×10ｋｍである 2 次メッシュ（国土地理院）ごとに，x，y 方向に各々N 等分でメッシュ化し，さらに z 方向にメッシュ化することで 3 次メッシュを作成し，連続空間を生成された 6 面体の 3 次元グリッドとする．より計算量を削減するために生成した各 3 次元グリッドを ID(x，y，z)で表す．ここに x，y，z は分割された 2 次メッシュの左下を原点とし非負整数で表すとする．各 2 次メッシュの経度，緯度幅が各々1/8 度，2/3/8 度であることから，各 3 次元グリッドの日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
経度，緯度幅は 1/8/N 度，2/3/8/N 度となり，2 次メッシュ
コード，ID(x，y，z)，分割数より 3 次元グリッドの左下頂点の緯度経度は，計算可能である．逆も同様に計算可能である．

3.2

・

衝突した場合，y-z 平面にて可視判定対象の建物オブジェクトグリッド B へ線分を引き，同様の衝突判定を行い，他の建物オブジェクトグリッド B と衝突しなかった可視判定対象の建物オブジェクトグリッド B を，可視オブジェクトグリッドとする．

オブジェクトグリッド簡素モデル化

上記方法で生成した 3 次元グリッドと地図データの道路・建物データとの衝突判定により道路・建物オブジェクトを構成するオブジェクトグリッドを抽出する．建物オブジェ
クトの場合，地図データの建物オブジェクトのレイヤと 3 次
元グリッドを衝突判定し，接しているが含まないグリッドを側面とし，接するグリッドを天井とし建物を構成する建物オブジェクトグリッドとする．道路の場合，道路のレイヤと衝突判定し接するグリッドで，標高を考慮して，ｚ方向が最も高いグリッドを道路オブジェクトグリッドとする．抽出されたオブジェクトグリッドをオブジェクトグリッドテーブルに格納する．テーブルのカラムは GeometryID，Layercode，
2 次メッシュコード，ID(x，y，z)とする．ここで GeometryID
は地図データで各道路や建物オブジェクトに一意に与えられている ID，Layercode は各レイヤに与えられている番号（例えば公共建物の番号：497）である．
ここで， B , R ,G を次のように定義する．

図 2 可視オブジェクトグリッド抽出アルゴリズム
Fig.2 Visible Object Grid Extraction Algorithm

・抽出した建物オブジェクトグリッド集合

B = {B | i = 1,..., m}i・抽出した道路オブジェクトグリッド集合

R = {R | i = 1,..., n}i・抽出した道路と建物オブジェクトグリッド集合

G = B U R = {G | i = 1,..., m + n}i

3.3

可視オブジェクトグリッド抽出アルゴリズム
次に視点となるオブジェクトグリッド G から可視建物

例えば図 3 で視点となる道路オブジェクトグリッド R から建物オブジェクトグリッド B に引いた線分で，x-y 平面では建物オブジェクトグリッド B に線分が衝突するため，y-z
平面での衝突判定を行い，上２つの建物オブジェクトグリッ
ド B が可視オブジェクトグリッドとなる．

オブジェクトグリッドを自動抽出するアルゴリズムを述べる（図 2）．計算量削減のため，視点となるオブジェクトグリ
ッド G から x-y 平面にて任意の範囲（例えば 2 次メッシュを 2000 分割した際のグリッド数 20 以内）を視野とし，範囲内にある建物オブジェクトグリッド B を可視判定計算対象とする．視点が道路オブジェクトグリッド R とは，ユーザが道路上にいる場合を想定(身長はグリッドの一辺の長さに比べると小さいと仮定)，それが建物オブジェクトグリッド

B とは，ユーザが建物の窓から対象を見ている場合である．
視点となる各オブジェクトグリッド G に対して以下を行う．
1.

視点となるオブジェクトグリッド G から x-y 平面にて任意の範囲内にある建物オブジェクトグリッド Bを抽出する．

2.

視点となるオブジェクトグリッド G の重心から各建3.

物オブジェクトグリッド B へ線分を引く．
x-y 平面にて，線分を含む MBR 内（視点となるオブジFig.3

抽出した可視オブジェクトグリッドをテーブルに格納する．視点となる道路，建物オブジェクトグリッドの 2 次メッ
シュ番号と ID（x，y，z），それに対する可視オブジェクト
グリッドの 2 次メッシュコードと ID（x，y，z）, GeometryIDをカラムとする．

Vis , VisGを次のように定義する．
ここで，・ 視点 1 点からの可視オブジェクトグリッド集合

Vis = { vis i i = 1 , L , l }ェクトグリッド G と可視判定対象の建物オブジェク
トグリッド B は除く）にて，線分と他の建物オブジェ
・

クトグリッド B との衝突判定する．
衝突しなかった場合，可視判定対象の建物オブジェクト
グリッド B のｚ方向分を含めたすべてを可視オブジェクトグリッドとする．

2

図 3 可視オブジェクトグリッド判別例
Example of Distinguishing Visible Object Grids

オブジェクトグリッド G からの可視オブジェクトグ
リッド集合

・VisG
3.4

= { visgiGi = 1, L , k }地図データの索引付けの有効性検証

空間演算は通常の場合多くの計算が必要とされるが， 3

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

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――次元グリッドを利用し地図データを索引付けすることで，索引から取得可能な，視認した建物オブジェクトがすべて見えるオブジェクトグリッド G と相対的方向関係に基づき，建物オブジェクトの可視部分のみを対象とした瞬時なユーザ位置推定が可能である．
実際に，索引付けの有効性を定量的に検証する実験として，ある視点から可視オブジェクトグリッドを衝突判定により自動抽出する時間と，すでに可視オブジェクトグリッドを格納したテーブルから，ある視点からの可視オブジェクトグリッドを検索する時間を測定した．
実験方法は，まず 2 次メッシュ（国土地理院）を x，ｙ方向に各 2000 分割し 3 次メッシュを生成し，3 次元グリッド

VisG

O = VisGi = 1, L , k B B }BAI VisG

BB= {o j}( j = 1, L , k )以下の 2，3 を視認した建物オブジェクト A，B に対して繰り返す．
2.

O の各候補グリッドからの B A 中の可視オブジェクト
グリッド Vis (グリッド数： l )を可視オブジェクト
グリッドテーブルより抽出し，O の各候補グリッドから可視オブジェクトグリッド ( l )に対するベクトルr
V Ai を計算する．大きさは常に１でベクトルの向きはッド B との x-y 平面での衝突判定を行い，可視オブジェクは 0.01sec であった．複合索引のためテーブルのタップル数が膨大になっても瞬時に検索可能なため，本論文の提案手法
は事前処理に多少時間がかかっても 1sec あたりに対応できるトランザクション量が多くなり商用のサービスにおいても有効と考えられる．

iBB

ド集合 O を求める．

道路オブジェクトグリッド R から任意の範囲内（ここでは視点からグリッド数 20 以内）にある建物オブジェクトグリ

様の視点からの可視オブジェクトグリッド Vis の検索時間= { visg【アルゴリズム】
1.
建物オブジェクト A，B を共に視認可能な候補グリッからオブジェクトグリッド G を抽出し，視点となる１つのトグリッド Vis を抽出した．この際の可視判定の衝突計算時間は約 0.15sec であった(Intel Pentium4，1.70GHz，512ＭＢ)．視点となるオブジェクトグリッド数は全体のグリッドに対し約１割であったことから， 2 次メッシュを x，y 方向で各々2000 分割したグリッド 2000×2000 の 1 割で 400000個となり，単純計算では x-y 平面での 2 次メッシュごとの可視・不可視判定時間は 0.15sec×400000=60000sec≒16.7hとなる．実際には，相対的位置情報としての建物オブジェク
ト，場所，地域の考慮や，道路，建物オブジェクト毎に分割数を変えることで計算対象となる有効なオブジェクトグリッド数が削減される．また本論文で提案した可視・不可視判
定は視点となるオブジェクトグリッドごとに行うことから，視点ごとに並列処理が行えるため台数効果による大幅な計算時間の短縮が図れる．
一方，可視オブジェクトグリッドテーブルから，図 3 と同BB

建物オブジェクトＡの各オブジェクトグリッドが見えるようなユーザの向きとする．

rr
V Ai = ( v Ai ) ( j = 1 , L , k )3.

O の各候補グリッドが持つ複数のベクトルを加算し，可視オブジェクトグリッド数( l )で割る．これは，各候補グリッドからの建物の可視オブジェクトグリッド数が異なるためである．

rrrr( v A 1 + v A 1 + L + v Al )Sum V Ai =l
4.

O の各候補グリッドについて，候補グリッドが持つ複数のベクトルを加算し，そのベクトルが最大である候補グリッド，またはその集合 W を出力する．

W = {o j o j ∈ O ∧rrrr(∀ h )(( Sum V Aj + Sum V Bj ) ⊇ ( Sum V Ah + Sum V Bh )4. 相対的位置情報を用いたユーザ位置検索
アルゴリズムオブジェクトグリッドテーブル，可視オブジェクトグリッ
ドテーブルを用い，建物オブジェクトＡ，Ｂの相対的位置情報からユーザ位置を推定するグリッドを求めるベクトル計
算のアルゴリズムを示す（図 4）．
B , B , VisG B A , VisG B Bを次のように定義する．
ここで， A B
・ ユーザが視認した建物オブジェクトＡ，Ｂの建物オブジェクトグリッド集合

B A = {bAi | i = 1,..., m A }BB = {bBi | i = 1,..., mB }・

可視オブジェクトグリッドテーブルによる，オブジェクトグリッド集合 {B A , BB } を各々可視可能な可視オブジェクトグリッド集合

VisG

3

BA= { visgi
BAi = 1, L , k B A }Fig.4

図 4 位置検索アルゴリズム
Location Identification Algorithm

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

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
5. 実装と検証
地図データは道路・建物オブジェクトグリッドを抽出するのに必要なポリゴンデータが取得可能な，昭文社製のMAPPLE デジタル地図データ MAPPLE10000 を使用した．
まず 2 次メッシュをｘ，ｙ方向に各 2000 分割し，さらにｚ方向に 5ｍ間隔で分割し，連続空間を 3 次元グリッドを生成し，地図データよりオブジェクトグリッド G を抽出した．
道路，建物オブジェクトは共に ID（X,Y,Z）の Z=0 上に立っていることを前提とし，高さは固定で付与した．図 5 は東京都庁周辺の抽出したオブジェクトグリッドの 3 次元表示である．抽出結果をオブジェクトグリッドテーブルに格納した．
Fig.7

図 5 オブジェクトグリッド抽出結果
Fig. 5
Object Grid Extraction Result
次に，図 6 のように視点となる道路オブジェクトグリッド

R から任意の範囲内（今回は分割数 20 のＭＢＲ内）にある可視オブジェクトグリッド VisG を抽出し，可視オブジェ
クトグリッドテーブルに格納した．

Fig.6

図 6 視点一点からの可視判定結果
Visibility Result of Building Object Grids
from a User’s Standing Position

最後に，ユーザから相対的位置情報（建物名，相対的方向関係）より候補グリッドを抽出し，視認した建物毎に候補グリッドからの視認した建物の可視オブジェクトグリッドへのベクトル計算を行い，図 7 のようにユーザの位置（ドットで表示されている）が推定されることを確認した．

6. まとめと今後の課題
相対的位置情報を用いたユーザ位置検索法として，まず現実世界を 3 次元グリッド化し，オブジェクトグリッド G

4

図 7 ユーザ位置推定結果
User’s Position Estimation Resultを抽出し，可視・不可視判定を行いデータベースへ格納することで地図データを事前計算により索引付けした．以上より，ある視点からの可視可能なオブジェクトグリッドが瞬時に取得可能なため，ユーザからの相対的位置情報を用いて，視認した建物オブジェクトがすべて可視可能な候補グリッドを抽出し，各候補グリッドから可視可能なオブジェクトグリ
ッドを用いた，ユーザ位置推定を行なう位置検索アルゴリズ
ムを提案し構築を行った．
今後の課題として，ｚ方向の曖昧性のモデル化を行い，ユーザから視認した建物に対する上下方向概念を導入することで建物内での位置推定を可能とし，さらにより現実的なモデルにするための標高データの導入，本研究手法の有効性検証のためのモバイル端末などでの実証などが挙げられる．

[謝辞]
本研究を進めるにあたりご助言頂きましたジクー・データ
システムズ株式会社開発部長本丸達也氏に深謝する．

[文献］[1] M. Egenhofer: “Spatial Relation: Models, Interfaces,and their Future Application”, Proceedings ofAdvanced Database Symposium '96, Vol.8,
No.4,
pp.403-424, 1996.
[2] M. Vazirgiannis: “Uncertainty handing in spatialrelationships”, Proceedings of the 2000 ACM
Symposium on Applied Computing, 2000.
[3] 上田道：“ウェアラブル環境におけるユーザの相対的方向関係を用いた位置検索システムの研究”，お茶の水女子大学修士論文，2004 年 3 月．
[4] 上田道，佐藤玲奈，増永良文：“ウェアラブル環境におけるユーザの相対的方向関係を用いた位置検索システムの 提 案 ” ， 情 報 処 理 学 会 研 究 報 告 , Vol.2003, No.71,
2003-DBS-131, pp.351-358, 2003年7月．

佐藤 玲奈

Reina SATO

2003 お茶の水女子大学理学部情報科学科卒業．2005 同大大学院人間文化研究科博士前期課程数理・情報科学専攻修了．
地図データベースの研究・開発に従事．日本データベース学会学生会員．

増永 良文

Yoshifumi MASUNAGA

お茶の水女子大学理学部情報科学科教授．1970 東北大学大学院工学研究科博士課程修了，工学博士．データベースシス
テムの研究・開発に従事．情報処理学会および電子情報通信学会フェロー．日本データベース学会会長．著書に「リレーショナルデータベース入門〔新訂版〕」(サイエンス社)など．

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