Hanan Samet

Prof. Samet's research is concerned with many aspects of spatial databases and image databases. The applications are in geographic information systems (GIS). computer graphics, and image processing.

The representation of spatial information is important for applications in geographic information systems, computer graphics, computer vision, and image processing. Research is being performed on the use of hierarchical data structures such as quadtrees and octrees in the representation of spatial data including points, lines, rectangles, regions, surfaces, and volumes. The QUILT geographic information system is based on these ideas.

Originally the QUILT system was designed to represent two-dimensional region information. Subsequently, it was extended to enable handling three-dimensional data and a primitive solid modeler was implemented using it. It supports operations such as rotation, translation, and views from a number of viewpoints. The QUILT system was also extended to enable modeling surface data such as that found in a digital terrain model.

The QUILT system was reimplemented using object-oriented methods so that it can be used with data of arbitrary dimensionality as well as enable the use of spatial data structures besides variants of the quadtree. The QUILT system has been used as a testbed for measuring the performance of quadtree-like data structures for large data sets. One such data set consists of Census Bureau TIGER files to record road network data for the entire US. A polygon data type was added to the QUILT system in support of this work.

One of our goals is to build a spatial database that enables attribute queries, as well as spatial location queries, to be answered efficiently. This is part of ongoing research on the problem of how to combine spatial and non-spatial data. Quadtree-like representations are good for answering location-based queries such as ìwhat feature is at location x?î However, users are frequently also interested in feature-based queries such as ìdoes feature x exist?î This query normally requires that each location in the space be queried individually. An architecture called SAND has been developed for combining spatial and non-spatial databases to deal with such queries. At present, we are using a home-grown relational database system that handles line segment data as well as the higher-level polygon data type. The spatial index is based on the PMR quadtree although an R-tree spatial index is also currently being developed.

More recent work on SAND has resulted in the construction of a relational browser (called the SAND Browser) which enables users to browse through a relational database that contains spatial data as well with the appropriate spatial indices. The result is an ability to perform what we term ranking. This means that we can rank spatial objects in the database based on their distances from another object. This ranking process can be restricted in terms of the region which is being searched using restrictions such as overlap and being within some distance of another object. The process is incremental so that as soon as an item is found that satisfies the query, the search ceases. For example, suppose we wish to find the nearest city to Buffalo with population greater than 1 million. In this case, we may search the cities around Buffalo in an incremental manner examining them in increasing order of distance and stopping the search once a city is found whose population exceeds 1 million. The technique we have developed for ranking is independent of the type of spatial index that is used (i.e., it works for quadtrees, R-trees, etc.). It is also independent of the data type (e.g., points, lines, regions, etc.).

Figure 1 illustrates a more concrete example of the use of the SAND Browser where we seek to retrieve the names and locations of all cities which are no further from Paris than Madrid. Notice that we do not use the naive way of constructing the answer to this query which is to first locate "Paris" and "Madrid" in the data set, compute the distance between them, say r, draw a circle of radius r around ìParisî and then select all cities lying within that circle. Instead, our solution proceeds in an incremental manner as follows:

Figure 1. Steps taken when using the SAND Browser to answer the query ìWhich cities are no further from Paris than Madridî. (a) Specification of a scan sorted by cityname starting with ìParisî; (b) the location of ìParisî; (c) specification of an incremental search of cities according to their distances from ìParisî; (d) the resulting group when ìMadridî is encountered.

The first step consists of obtaining the location of ìParisî. This is done by specifying that the relation should be scanned by name starting from ìParisî (Figure 1a). Once the location of ìParisî is known (Figure 1b), we start an incremental search where tuples are reported in order of distance from "Paris" (Figure 1c). In other words, they are ranked. By pressing the Next button, all cities which answer the query are displayed in succession until "Madrid" is found (Figure 1d), at which time we stop.

We have also found other applications of ranking. For example, we have used ranking as the basis of an algorithm to compute clusters in a spatial database. In particular, suppose we are given a set of locations of nuclear facilities N and a set of locations of monitoring stations F. We wish to calculate the following:

• For each nuclear facility, find the closest monitoring   station.
• For each monitoring station, find the closest nuclear   facility.

The SAND system has been used as the basis of a number of other projects. A project was also started to investigate interoperability issues in geographic information systems (GIS). We used the SAND spatial data base system and the OpenMap TM system which is a distributed mapping system that allows displaying together geographic data acquired from disparate data sources. We built a SAND Specialist that makes data stored in SAND accessible to the OpenMap user interface client. DLG data from the U.S. Geological Survey was used to demonstrate the combined system.

The SAND system makes use of a spatial index that represents the various spatial data types using the PMR quadtree. Preliminary work has been done in implementing an R-tree spatial index and incorporating it into the SAND system. We have also been studying the applicability of the various algorithms used to answer queries in the SAND Browser to other spatial data structures.

We have constructed the VASCO system which provides a general mechanism for visualizing these data structures and algorithms. The VASCO system is a set of JAVA spatial index applets that enable users on the World Wide Web to experiment with different spatial data structures. This includes many variants of the quadtree for different data types including points, line segments, and rectangles, as well as R-trees which can be built using different splitting rules and include the R*-tree.

The applets enable users to see in an animated manner how a number of basic spatial database search operations are executed. The spatial operations are spatial selection (i.e., a window or spatial range query) and a nearest neighbor query that enables ranking spatial objects in the order of their distances from a given query object. The results of the different splitting rules and the algorithms are visualized and animated in a consistent manner using the same primitives and colors so that the differences between the effects of the rules can be easily understood. The applets can be used to monitor the performance of spatial databases that use these representations as well as tune them by observing their behavior for different distributions of data. Users are provided a public file server for storing data as well as exchanging data sets with other users.

The most recent addition to the VASCO system has been a capability of dynamically moving data and seeing the effect of this on the various data structures. We have also expanded its functionality substantially by adding a general window query and a corridor computation. This enables the applets to have capabilities similar to those of the SAND Browser with the exception of the interaction with a formal database. The applets can be found at http://www.cs.umd.edu/~hjs/ quadtrees/index.html and have been used throughout the world as well as in classes at a number of universities.

Figure 2 shows a sample applet window for quadtree representations of point objects. The applet window contains a drawing canvas and a control panel. The drawing canvas is of size 512 ¥ 512 with the origin at the upper-left corner. The x and y coordinate values increase rightward and downward, respectively. At any instant, users may zoom in and zoom out for a closer and more detailed examination of the data. In Figure 2, the drawing canvas is overlaid with a window listing the various quadtree representations for point data with the bucket PR quadtree being selected (where a block is decomposed into four equal-sized blocks when it contains more points than its bucket capacity, which can be set by the user and is 3 in this example). The window is created when the user activates the Data Structures button. Data can be inserted dynamically by user input or by loading data from a file (data can also be saved to a file). A similar control panel is used for the quadtree representations of rectangle objects and line segment objects.

Figure 2. A sample applet window. The drawing canvas is deliberately left empty. It is overlaid with a window containing a check box group listing the various quadtree representations for point data (with the bucket PR quadtree having a bucket capacity of 3 selected) and a close button.

Another research project is in the Grand Challenge area. It is being conducted in collaboration with researchers at Lawrence Berkeley and Lawrence Livermore National Laboratories. This project focuses on the need of researchers working with large spatial datasets, such as seismic studies, oil reservoir modeling, fluid turbulence, hazardous waste management, and climate modeling, to efficiently access relevant small data subsets contained within much larger datasets for interactive analysis and visualization purposes. This is an important aspect of data management for other kinds of multi-dimensional simulations and applications as well. To address this need, an attempt is being made to develop data allocation techniques based on analysis of data access patterns and storage device characteristics, and to develop data reduction methods based on uniform data transformations and multi-dimensional index construction. In the past year we have also extended the SAND Browser to deal with this data by giving it the ability to handle three-dimensional data such as surfaces so that queries can be run on temperature data over different time periods.

Work is also proceeding on image databases. Such databases are conceptually much harder to deal with than conventional databases because the information that they contain consists of images, rather than alphanumeric entities. Our main project in this area deals with the symbolic data found in maps. In this case the goal is to build a database of the objects on the map (e.g., hotels, campsites, etc.) based on the legend of the map. This work makes use of the fact that the map can be decomposed into layers. The focus is on utilizing statistical pattern recognition along with spatial indexing to classify objects in raw images. The approach makes heavy use of spatial data structures. These techniques were originally used in the design and implementation of a system that automatically interprets binary images of floor plans. The task is one of locating architectural and structural features (e.g., doors, sinks, bathtubs, etc.). The system is given a training set containing samples of feature vectors describing the objects that may be identified in the image. This training set is stored in a library. Various data structures have been tested for storing this library.

The methodology developed for the interpretation of floor plans was adapted to automatically extract objects from raster images of maps. The data set being used consists of the separate layers of the map. The emphasis
is on identifying tourism symbols. These include symbols for scenic areas, post offices, hospitals, hotels, hostels, beaches, recreation areas, etc. These symbols are found in the legends of the maps and are then used to
indicate the locations of these sites on the maps. The data set of possible symbols on the map is much richer than the set of symbols on the floor plan. Moreover, the symbols are not as distinct as in the case of the floor plan. Thus, additional features must be computed for each object. We have developed a new technique for representing symbols which we term a negative symbol. The idea is to take advantage of the fact that most of the symbols are embedded in a circle or a box. Thus the feature vector corresponding to each symbol makes use of the background of the symbol rather than the actual symbol. We have developed a system named MAGELLAN (denoting Map Acquisition of GEographic Labels by Legend Analysis using Negative symbols) that utilizes the symbolic knowledge found in the legend of the map to drive geographic symbol (or label) recognition. The negative symbol method has also been applied to logo recognition. This problem is more complex than the recognition of the map symbols as the symbols often contain more than one component.

Once the objects in the map are recognized, they are used to build an index on the raster layers of the map. The binary images are stored in an image database that we have developed called MARCO (denoting MAp Retrieval by COntent). The results of the automatic interpretation of these raster images is used to build an index in order to enable retrieval by content of the images stored in the image database. In addition, the locational information about the recognized objects is also inserted into MARCO and enables spatial queries about these objects.

Similar methods can be applied to other maps such as vegetation maps and weather maps, as well as to images, including satellite images and aerial photos. Knowledge about the geographic area covered by the map and the images can then be used to correlate the data and to model changes. The automatic interpretation of the images along with the index built on the images provides a tool for accessing information from various sources. In particular, they may all be integrated into one database that provides access to the raw images, along with the extracted objects and various types of alphanumeric data that pertain to the maps and images.

We have also developed methods of querying a database of images each composed of several objects (or symbols). We want to find all of the images in the database that contain a number of specific objects in a particular spatial configuration with respect to each other. One method to achieve this is by an extension of a standard database query language (e.g., SQL) that provides additional predicates corresponding to spatial relationships. One problem with this method is that the objects in the images must be pre-classified so that the user can specify them by some alphanumeric tag. In addition, if we wish to find more complex images that are composed of several objects that must satisfy a particular spatial configuration, or if we wish to specify a choice among objects that satisfy some spatial configuration, then the corresponding SQL query becomes very complex.

An alternative method, and the one we have chosen to investigate, is to specify the queries graphically. This is a more ìnaturalî method that facilitates the use of more complex constraints based on the implicit characteristics of the graphical query (i.e., the particular objects in the graphical query and their spatial arrangement). There are, however, several difficulties associated with graphical query specifications. First of all, graphical queries are inherently ambiguous, which gives rise to several questions. In particular, what criteria should be used to determine that an object in a database image is the same as a particular object in the query image (termed matching ambiguity)? In addition, when query images are composed of several objects, are we looking for images that contain all of these objects, or would we be satisfied with any subset of these objects (termed contextual ambiguity)? Finally, is the spatial arrangement of the query objects of significance? For example, if one object in the query image is placed above and within 30 units of another object, what database images satisfy this query? One possibility is that only database images with exactly the same spatial configuration satisfy the query. However, the intent may be that only the distance must be the same, or maybe that any configuration may suffice (termed spatial ambiguity).

Another difficulty with graphical queries is that they are not always as expressive as textual queries in terms of specifying combinations of conditions and negative conditions. For example, how do we specify graphically images that contain beaches but do not contain camping sites within three miles of these beaches? What we want is a graphical query specification method that leverages on the expressiveness of graphical queries in terms of describing what objects the target images should contain and their desired spatial configuration, while simultaneously resolving the matching, contextual, and spatial ambiguities as well as the limited expressiveness of graphical query specifications.

Currently we are developing a graphical query specification technique for retrieval of images in an image database that addresses the issues of matching, contextual, and spatial ambiguity in a comprehensive manner. The graphical query specification uses pictorial query trees. The leaves of a pictorial query tree correspond to individual pictorial queries that specify which objects should appear in the target images as well as how many occurrences of each object are required. In addition, the minimum required certainty of matching between query-image objects and database-image objects, as well as spatial constraints that specify bounds on the distance and relative direction between objects, are also specified. Internal nodes in the query tree represent logical operations (AND, OR, XOR) and their negations on the set of pictorial queries (or subtrees) represented by the nodes' children. This work is now being ported to the World Wide Web by the construction of the appropriate JAVA applets. Figure 3 shows the graphical query builder that we have developed. The user has constructed a query to retrieve all database images that contain a hotel within six miles of a beach and do not have an airport within one mile of the beach. Furthermore, the certainty that the database-image symbols are in fact a hotel, beach, and airport must be * 0.5. The symbols are ìdragged and droppedî from the menu of symbols displayed in the bottom of the window. The query builder constructs this menu of symbols directly from the database which stores one example of each symbol relevant to the application at hand. These example symbols are taken from the legend of the map in our example application.

Figure 3. Tool for constructing graphical queries. The user has constructed a query to ìretrieve all database images that contain a hotel within six miles of a beach and that do not have an airport within one mile of the beach.î