FIT2005(第4回情報科学技術フォーラム)J-026

多次元データ管理構造を用いた可視性による画像検索
Visibility Search for Pictures Using Multidimensional Data Structure
岩永 洋輔
Yousuke Iwanaga

金子 裕良
Yasuyoshi Kaneko

１． まえがき阿部 茂
Shigeru AbeFirst splity

近年、ディジタルカメラで写真を大量に撮影・蓄積することが可能となり、必要な写真を高速検索することが重要となっている。写真をキーワード (手動あるいは自動で入力する)で検索するシステムは多いが、検索目標が写っている写真をカメラデータ（撮影位置、方向、視野角）と地図から可視性を利用して検索するシステムは見られない。
我々は、地図上で目標物を指定すると、これが写っている写真を優先順に検索表示する手法を考案し、知的な道案
内システムの実現をめざしている。膨大な写真は多次元データ管理構造 k-d tree を用いて管理する。k-d tree では最近
接検索や範囲検索が一般的であるが、可視検索のために点検索、建物検索のアルゴリズムを開発した。またプロトタイプシステムを作成し、基本機能と動作を確認した。

A
1C・

5・

Secondsplit
8・D

3 ・・76 ・

4・2E・
Fx

Third split(a)2 ．多次元データ管理構造 k-d tree
多次元データ構造の k-d tree を用いて、カメラデータと地図データを管理する。Fig.1 に座標とデータ構造を示す。
座標軸は左上を原点とし、カメラデータは撮影位置を頂点、視野角を頂角とする二等辺三角形、建物等を表わす地図データは長方形とする。カメラデータと地図データはそれぞれ別の k-d tree に蓄積し管理する。
Fig.2 に k-d tree の概略を示す。Fig.2 (a) のように分布する点データは Fig.2 (c) の k-d tree によって管理される。領域は再帰的に分割され、各領域が葉やノードに相当する。
各ノードは下に二つの子ノードを持つことができる。葉には、バケット容量 B のデータを含むことができる（Fig.2
では B=3）。各ノードは子ノード全ての領域を包含する外接長方形を持っており、その各辺は座標軸に平行である。

Bデータ分布RootAABCD
153

413E2 6 7データ 8 投入前

456(b)B

DC(c)F
827(a)の k-d tree

Fig.2 k-d tree の例
同様に、葉はカメラデータや地図データのような葉のオブジェクト全てを包括する外接長方形を持っている。外接長方形は範囲検索や最近接検索において、根ノードからどのノードを順にたどれば良いかを決めるために使われる。

y(sx,sy)

3．可視性による画像検索

sx sy ex eycx cy

map data(x1,y1)(ex,ey)(x3,y3)

camera datar(tx,ty)x

写真データはカメラデータと画像データとから成る。画像データは k-d tree とは別の記憶領域に格納し、k-d tree からポインタで指し示す。各写真のカメラデータ（撮影位置、方向、視野角）が k-d tree に入力されると、その撮影範囲の二等辺三角形が作成され適当な葉に蓄積される。プロト
タイプシステムでは、撮影範囲三角形の高さは、写真でその対象物を認識できる距離とし、適当に決めた。将来、GPS をカメラに付加できれば、写真撮影と同時にそのカメラデータを記録し、k-d tree に蓄積することが可能となる。
本論文では２つの可視検索方法を紹介する。一つは点検索でもう一つは建物検索である。点検索は、Fig.3 に示すように、画面上の地図上でユーザーが目標点Ｐ（x,y）を示したとき、その撮影範囲三角形に点Ｐが含まれる写真を検索し CRT 画面上に表示する。建物検索は、ユーザーが画面

x1 y1 x2 y2 x3 y3
tx ty
cx cy(x2,y2)

Fig.1 データ構造

埼玉大学工学部電気電子システム工学科

235

FIT2005(第4回情報科学技術フォーラム)O

2

大きく写っている場合に優先度を高く、建物検索の場合は、目標建物全体を大きく含んでいる場合に優先度を高くした。
P
道案内システムなどでは、建物の入口が重要であり、これが適当な大きさで写っているQ写真が重要である。優先度はアプリケーションによって変×Pわるべきものである。
R（４） 撮影範囲
撮影範囲三角形の高さをどのように決めるかは重要である。本システムでは三角形のFig. 4 点検索と建物検索
Fig. 3 可視性による画像検索
頂角の二等分線が最初に建物と交差するまでの長さを三角上で建物の内部をクリックした場合に実行され、建物を含形の高さ（撮影範囲）とした。撮影範囲が広すぎる（高さむ写真を全て検索し、表示する。
が長すぎる）と、検索目標が写真で小さすぎて認識できな
Fig.4 に点検索と建物検索の方法と相違を示す。点検索はくなる可能性が高くなる。このため撮影範囲の限界距離は指定した点 P が建物の外部だった場合に実行され、建物検決めておく。
索は指定した点 Q が建物内部だった場合に、その建物を目（５） 道案内システムへの応用標物とし実行される。
現在位置と目標地点を指定すると、適切な道順を決定し、その道順にそって分かりやすい写真を順に表示する道案内（１） 点検索システムに応用していく予定である。
目標点 P が建物の外部に存在する場合、点 P を内部に含1

む撮影範囲三角形（以後三角形と記す）を全て検索する。
k-d tree では全ての図形はその外接長方形で管理されるので、 4．可視検索アルゴリズム
まず点 P を含む外接長方形を検索し、次に点 P が三角形のFig.5 を用いて、可視検索のアルゴリズムを記述する。
内部に含まれるか否かをチェックする。
葉ノード L は３つの要素から構成される。
可視検索では障害物による隠れの問題を解決する必要がL = {RL , M ,*Object[3]}ある。Fig.4 で点 R はカメラデータ１の三角形の内部であRL ：葉 L の外接長方形るが、建物 A に遮られてて O 点からは見えない。
M ：葉 L に含まれるオブジェクトの数
隠れ対策として、撮影位置 O と目標点 R を結ぶ線分が、*Object ：オブジェクト O へのポインタの配列。 M の他の建物と交差しているかをチRoot
ェックする。交差している場合
Oはそのカメラデータを検索対象から除外する。
（２） 建物検索
RN
点 Q を指定すると、建物検索
Buildingが実行され、建物 A を含む全ての写真を検索する。建物検索でRLは、検索目標は点 Q を含む建物Lとなるので、まず目標長方形とP交差する三角形の外接長方形がRO検索される。次に検索された三Camera Data(d) Blind Check
角形が建物 A と交差するか否か(a) A k-d treeを厳密にチェックする。例えばRO
Building = RS
Fig.4 で点 Q を指定すると、写R
真 1 だけでなく写真 2 も検索さ×れる。
R（３） 表示写真優先順位×
本システムでは、写真の数が膨大な量になるので、一度に多くの写真が表示される可能性がRROある。そこで写真表示に優先順位をつけて、最も重要な写真かT
B=3(c) Enclosure R of Object(e) Intersection checkら順に表示する。点検索の場合 (b) Enclosure R of Leaf
は、目標点が写真の中心に近く
Fig.5 可視検索の木構造と外接長方形N

LO236

FIT2005(第4回情報科学技術フォーラム)形 RS と交わるかどうかを調べる。
（５） RangeSearch( N , R )R1. N をノードとしてセットする。
R2. N が葉でない場合、 R4へ。
R3.（ N が葉の場合） N の中で、 R と交わるデータを集め、その値を返す。
R4. ２つの子(i=1,2)の R N がR と交わっていた場合、RangeSearch( Child [i ], R ) を呼び出す。

Fig. 6 可視検索の実行結果

5．プロトタイプシステム
埼玉大学の構内ガイドを想定した可視検索のプロトタイ
プシステムを開発した。 Fig.6 にその実行例を示す。画面上に実線で表示されている長方形は、キャンパスの建物であり、点線で表示されているのは、道路などその他の地図情報である。目標点をマウスでクリックすると、目標点を含んだカメラデータの写真がウィンドウの右側に表示され、撮影範囲の三角形も地図上に表示される。

最大容量はＢである。
内部ノード N には２つの要素が記録される。
N = {R N ,*Child [2]}R N ：ノード N の外接長方形*Child ：子ノードへのポインタの配列。
オブジェクト O は３つの要素が記録される。
O = {RO , data ( x1 , y1 ).....( x i , y i ),*image}
RO ：オブジェクト O の外接長方形

6．あとがきdata ：カメラデータと地図データ*image ：写真へのポインタ（１） VisibilitySeach アルゴリズム
V1.目標点 P(x,y)を決定
V2.[点検索または建物検索]もし、目標点 P が建物データの内部に存在するなら、建物検索を呼び出し、含まない場合は点検索を呼び出す。
（２） PointSearch アルゴリズム( N , P )P1. R N の範囲内に点 P を含むノードをたどり、 RL が点 Pを含む葉を列挙する。（Fig.5(a)参照）
P2.点 P が RO に含まれているかどうか、それぞれのオブジ
ェクト O について調べる。
P3.実際に点 P がオブジェクト O の三角形内部に存在するかどうかを調べる。
（３） BlindCheck アルゴリズム
B1.撮影位置 O と目標点 P を結ぶ線分 OP を描く。
B2.線分 OP がオブジェクト O （たいていは建物）のいずれかと交差していたときは、そのカメラデータを表示候補から除外し、そうでない場合はそのカメラデータを候補に加える。(Fig.5(d))（４） ObjectSearch アルゴリズム( N , R S )O1.

RS を 目 標 建 物 長 方 形 と し て セ ッ ト す る 。

RangeSearch( N , R S )を呼び出して、 RO が RS と交わるオブジ
ェクトを候補として含める。
O2.それぞれの候補の三角形（カメラデータ）が検索長方

237

多次元データ管理構造 k-d tree を用いた可視性による画像検索法を示した。点検索と建物検索のアルゴリズムを紹介した。プロトタイプシステムでその有用性と、基本機能を確認した。

参考文献[1] J. L. Bently, “Multidimensional Binary Search Trees Used
for Associative Searching,” Communications of the ACM, Vol.
18, No. 9, pp. 509-517, 1975.
[2] 阿部茂、中村泰明、亀井克之 , “画像データ検索方法 ,”特許 2981520, 1992.
[3] 中村泰明、阿部茂、大沢裕、坂内正夫, "多次元データの平衡木による管理 MD 木の提案", 電子情報通信学会論
文誌 D, Vol.J.71-D, No.9, pp.1745-1752, 1988