Visibility Search for Pictures Using Multidimensional
Data Structure
Yousuke Iwanaga, Yasuyoshi Kaneko, Shigeru Abe
Department of Electrical and Electronic Systems,
Faculty of Engineering, Saitama University
255 Shimo-Okubo Sakura-ku Saitama-shi 338-8570 JAPAN{kaneko, abe}@ees.saitama-u.ac.jp

Abstract. Searching pictures from picture database in a geographic information
system becomes important. A system which search pictures from map data(buildings and streets) and camera data (camera location and direction) byvisibility search has been developed. If a user indicates a target point on a map,then pictures which include the object of the target point are searched anddisplayed in priority order. The k-d tree is used for the management of map dataand camera data. Using photography range triangles and the range search, wehave developed the visibility search algorithm.

1 Introduction
In recent years, we can take a large number of pictures using digital cameras and store
them in a database, therefore it becomes important to search required pictures more
quickly. Systems which search pictures with keywords are widely used. However, asystem which search pictures from map data (buildings and streets) and camera data
(camera location and direction) by visibility search is not appeared.
In our system, if a user indicates a target point on a map, then pictures which
include the object of the target point are searched and displayed in priority order. It iseasy to expand this system to an intelligent navigation system. The multidimensional
data structure k-d tree is used for the management of map data and camera data. In
addition to the nearest neighbor search and the range search, we have developed thevisibility search algorithm. A prototype system shows the usefulness of the visibility
search and good performance.

2 Data Management using the k-d tree
We use the k-d tree of multi- dimensional data structure. Two types of data structures,
one for camera data and the other for map data, are used in the k-d trees. Fig. 1
illustrates coordinates and the data structures. Camera data are represented bytriangles, that is, the vertexes indicate the camera locations and the vertical angles
indicate the viewing angles. Map data such as buildings are represented by rectangles.

2Yousuke Iwanaga, Yasuyoshi Kaneko, Shigeru AbeyA k-d tree is shown in Fig. 2.
(sx,sy)The data in Fig. 2(a) aremanaged by the tree of Fig.
sx sy ex ey
map data2(c). A bucket method iscx cy
commonly used. In the bucket(x1,y1)(ex,ey)k-d tree, a leaf can contain more
(x3,y3)than one data. In Fig.2, thex1 y1 x2 y2 x3 y3rcamera data
bucket capacity is 3. An internaltx ty
node of the k-d tree can have(tx,ty)
cx cy
only two children. In the k-d x(x2,y2)
tree, area is split into sub areas
recursively and each area
Fig.1 Data structures
corresponds to a node or a leaf.
First split
Each node has a minimumyA B
enclosure rectangle that covers all
regions of those of lower nodes.
C1・
The sides of the enclosure
53 ・・
rectangle are parallel to the axes.
SecondThe enclosure rectangle plays an split
important role in handling data.
・7
Namely, a leaf has a minimum
8D・
enclosure rectangle that covers all
objects in the leaf such as camera
6 ・4・data and map data. An internal
2
node has an enclosure rectangle
・which covers their children'sEF
xenclosure rectangles. In range
Third split
search and nearest neighbors
search, the enclosure rectangles(a) Data Location
are used to determine which node
Rootshould visit to search the target object.
AB

3 Visibility Search for Pictures
The picture data consist of image data andcamera data. Image data are stored in thememory not in the k-d tree and the pointerto the image data is stored in the k-d tree.
Many picture data are input to the visibilitysearch system. Each picture's camera datathat is a camera location, a camera direction
and a viewing angle are input and thephotography range triangle is stored in thek-d tree. The height of photography range
triangle is the distance which we canC

D
1

53

42 6 7(b) Before Insert Datum 8ABDC
1

3

45E
6F
8

27(c) k-d tree of (a)Fig.2 An example of a k-d tree

Visibility Search for Pictures Using Multidimensional Data Structure

3

recognize the object in thepicture and is determined
properly in our prototypesystem. If a camera has an
accurate GPS in future, it ispossible to record the camera
data when the picture is taken,
and store them to the k-d tree
automatically. Camera data and×P
map data are stored in the two
k-d trees respectively. The map
data consists of building dataand other obstacles of theFig. 3 Visibility Search for Pictures
visibility search.
We have developed two visibility
2search method. One is the point search O 1
and the other is the object search. In thecase of the point search, if a user
Building Aindicates the target point P( x, y ) in
the map on the screen as shown in Fig.
P3, pictures which include P in theirphotography range are displayed on theCRT screen. In the object search, if auser indicates the target object in theQmap by clicking the inside of the object
rectangle, pictures which include theobject are displayed even if the whole
object is not included.
RFig.4 shows the point search andobject search. When the indicated point
P is outside of buildings, the pointsearch is executed, and when theindicated point Q is inside of abuilding, the building is recognized as
the target object and the object search
Fig. 4 Point Search and Object Searchis executed.
3.1 Point Search
As shown in Fig.4, if the target point P is outside of buildings, the point search is
executed and all the photography range triangles (later refer as triangle shortly) which
include P inside are searched. As every triangle is managed by its minimum enclosure
rectangle in the k-d tree, the rectangle which includes P is searched at first, then thetriangle is examined whether P is inside of the triangle or not.
In the visibility search, we have to resolve the occlusion problem. In Fig. 4, thepoint R is inside of the camera triangle 1, however, the R is occluded by the building4Yousuke Iwanaga, Yasuyoshi Kaneko, Shigeru Abe

A.To avoid the occlusion, we introduce the visibility check. A line segment between
the camera location O and the target point R is drawn and the line segment OR ischecked whether it intersects with other object or not.
3.2 Object Search
When the point Q is specified, the system searches all the pictures which include
building A. In the object search, the target is rectangle A. Therefore, at first all theenclosure rectangles of the triangles which intersect with the target rectangle aresearched. Then these triangles are checked precisely whether they intersect with thetarget rectangle A or not. For example, when the point Q is specified, not only thepicture 1 but also picture 2 can be searched in Fig.4.
3.3 Priority to Display Pictures
The number of pictures is very large in our system. And many pictures may besearched and displayed at once. The priority to display pictures is important. In thecase of point search, the picture which shows the target point (a) bigger and (b) incenter has high priority. In the case of object search, the picture which includes whole
the target building as large as possible has high priority. In navigation systems, theentrances of buildings are also important and we think the priority differs fromapplications.
3.4 Photography Range Adjustment
One method of deciding the height of the triangle is to exptend the bisector of camera
viewing angle (vertical angle) until it reaches to a building (or any obstacles) andconsider the length of the bisector as the height of the triangle. Also, the maximumlength (visibility range) should be decided considering the size of objects in thepicture.
3.5 Application to a Navigation System
A promising application of this system is a navigation system. If a present location
and a target location are specified, the optimum route will be determined, andadvisable pictures along the route can be informed to users in order.

4 Algorithms of Visibility Search
Algorithms of visibility search are described in Fig. 5.
A leaf node L is constructed with three elements:

Visibility Search for Pictures Using Multidimensional Data Structure
RootORN
BuildingRLLPRO(d) Blind Check(a) A k-d tree

RORN

Camera Data

Building = RS

×RL×

RORO
B=3

(b) Enclosure R of Leaf

T(c) Enclosure R of Object(e) Intersection check

Fig.5 Tree and Enclosure Rectangles of Visibility Search

L = {RL , M ,*Object[3]}where, RL : an enclosure rectangle of leaf L ,M : number of object included in leaf L ,* Object : an array of pointers to object O .
Maximum number of M is the bucket capacity B.
An internal node N is a record with two elements:

N = {R N ,*Child [2]}where, R N : an enclosure rectangle of node N ,* Child : an array of pointers to children.
An object O is a record with three elements:
O = {RO , data ( x1 , y1 ).....( xi , yi ),*image}where, RO : an enclosure rectangle of object O .
data : camera data or map data.
* image : a pointer to the picture.

56Yousuke Iwanaga, Yasuyoshi Kaneko, Shigeru Abe

4.1 Algorithm VisibilitySearch
V1. A target point P ( x , y ) is determined.
V2. [PointSsearch or ObjectSearch] If the target point P exists inside of abuilding data, invoke ObjectSearch, else invole PointSesrch.
4.2 Algorithm PointSearch ( N, P )P1. From Root to Leaf visit Node and Leaf which RN or RL include the point P ,and enumerate the leaves which RL include the point P . (See Fig. 5(a))
P2. Examine each object O whether P is included in RO . (Fig. 5(b))
P3. Examine further whether P exists in the triangle of the object O .(Fig. 5(c))
P3. Invoke BlindCheck.
4.3 Algorithm BlindCheck
B1. Draw a line segment OP between the camera location O and the target pointP.
B2. If the line segment OP intersects with any objects O (usually bouildings),
the camera data are deleted from the candidates to display, else the camera data areadded to the candidates. (Fig. 5(d))
4.4 Algorithm ObjectSearch( N, RS )O1. Set Rs to the target building rectangle. Invoke RangeSearch( N, RS ) and theObjects which RO intersect with Rs are obtained as the candidates.
O2. Examine each candidate whether its triangle (camera data) is intersect with thesearch rectangle Rs or not. (Fig. 5(e))
4.5 Algorithm RangeSearch( N, R )R1. Set N as Root.
R2. If N is not a leaf, goto R4.
R3. ( N is a leaf). Collect data in N which intersect with R . Return.
R4. For two children (i=1,2), if the child's RN intersect with R , invoke
RangeSearch( Child [i ], R ).

5 Prototype System
We have developed a prototype system of visibility search, which can be used as acampus guide of Saitama University. Fig.6 shows an example of the execution resultof our prototype system. Many rectangles are buildings of our campus. When a target

Visibility Search for Pictures Using Multidimensional Data Structure

7Fig. 6 Execution Result of Visibility Search
point is clicked with a mouse, pictures of camera data including the target point are
displayed on the right side of the window and photography range triangles are also
shown on the map.

6 Conclusion
We have developed a visibility search method for pictures using multi- dimensional
data structure k-d tree. The k-d tree manages a large amount of picture data and its
background map data hierarchically. Two search algorithms, the point search and theobject search are presented. A prototype system shows the usefulness of the visibility
search and good performance.

References
1. J. L. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,”
Communications of the ACM, Vol. 18, No. 9, pp. 509-517, 1975.
2. S. Abe, Y. Nakamura and K. Kamei, “Image data search method,” Japan Patent 2981520,1992.
3. Y. Nakamura, S. Abe, Y. Ohsawa, M. Sakauchi, “A Balanced Hierarchical Data Structure
for Multidimensional Data with Highly Efficient Dynamic Characteristics”, IEEE Trans. on
Knowledge and Data Engineering, Vol.5, No.4, pp.682-693, 1993.