Intelligent Image Database Systems

The following sections are included:

• PREFACE

• CONTENTS

This book covers the principles and recent research results in intelligent image database systems design. As the title indicates, the book places special emphasis on spatial reasoning and the techniques for image indexing and retrieval, mainly based upon the Theory of Symbolic Projection. In addition, applications of the theory and techniques to intelligent image database systems design are also discussed.

In this chapter, we describe a new way of representing a symbolic picture by a two-dimensional string. A picture query can also be specified as a 2D string. The problem of pictorial information retrieval then becomes a problem of 2D subsequence matching. We present algorithms for encoding a symbolic picture into its 2D string representation, reconstructing a picture from its 2D string representation, and matching a 2D string with another 2D string. We also prove the necessary and sufficient conditions to characterize ambiguous pictures for reduced 2D strings as well as normal 2D strings. This approach thus allows an efficient and natural way to construct iconic indexes for pictures.

The use of picture icons as picture indexes is the basic issue of the iconic indexing methodologies developed for advanced visual database applications. Most of the pictorial indexing methodologies developed so far describe images with meaningful orientation. However, in many cases, more freedom in the filing of images with respect to the orientation is required since the visual information contained in them is independent of any orientation or simply should not be affected by possible erroneous storing, for example in the reverse direction. The conventional methodologies based on orthogonal projections do not allow recognition of the identity between two indexes corresponding to an image and its reverse, even though their visual content is essentially the same.

We define a mapping between images and indexes that satisfies the property of normalization. In particular, we deal with the problems of reversing and rotation of images, which represent the two fundamental manipulations in the 2D space. An indexing methodology based on the Indexed 2D C-string is presented to overcome the limitation of the first problem. The transformation law called TX-6 allows us to obtain the index of a reverse image starting from the index of the original one.

Then, to obtain the rotation invariance, we introduce a system of polar axes that substitutes the Cartesian one, and totally inherits all the properties of orthogonal indexes. Finally, we define a structured index which represents the second level of normalization of an IDBS, because it describes an image considering its visual information rather than its external characteristics.

A new way of representing three dimensional pictures, called 3D string, is defined in this chapter. The ambiguity of this representation is discussed with respect to the properties of pictures. Algorithms are presented for reconstructing a 3D binary picture from its 3D string. As an extension to Chang's earlier chapter about 2D string, a procedure is given in this chapter to calculate the number of binary 2D functions with a given 2D string as their 2D string. Picture matching can be carried out by means of 3D string matching, for which algorithms are presented. This representation is efficient and can be applied to construct iconic indexes for 3D pictures. However, problems about the ambiguity of 3D string remain to be solved.

The preception of spatial relationships among objects in a picture is one important criterion to discriminate and retrieve images in an image database system. The data structure, called 2D string, to represent symbolic pictures was proposed by Chang et al. It allows a natural way of constructing iconic indexes for pictures. Jungert has extended 2D string to represent more types of spatial relationships, but the operators and the derived knowledge cannot be stored in a unified structure. Lee and Hsu proposed 2D C-string representation with a set of spatial operators and a more efficient cutting mechanism. 2D C-string is more characteristic of spatial knowledge and is more efficient in representation and manipulation of images. Since each symbolic picture can be represented by a 2D C-string, a picture query can also be specified by a 2D C-string. The problem of pictorial information retrieval then becomes the problem of 2D subsequence matching. Spatial relationship is a fuzzy concept. The capability of similarity retrieval for pictures is essential. Similarity measure and similarity retrieval of iconic images to different extents of precision is also presented.

Two types of ordering information about a finite set of points are studied in discrete and computational geometry. Some properties of ordering information are reviewed which help to analyze the symbolic projection approach to spatial reasoning. Then the problem of rotation invariance is addressed. Bounds are given on the number of different symbolic projections that may arise from rotating a configuration of n points. Consequences of this result on the design of rotation-invariant extensions of symbolic projection are discussed. Finally the panorama is introduced as a representation of ordering information which can be used as an rotation invariant index to symbolic descriptions of point configurations.

In this chapter, two approaches concerned with object relations seen from a moving object (agent) that is moving in a space of fixed landmarks, will be discussed. Both approaches are complementary to each other from certain aspects. In the first approach the agent itself is of no concern when reasoning about the view as it is seen by the agent. Furthermore, in this approach only some simple aspects of symbolic projection are used, while most other aspects are based on novel concepts. The second approach, on the other hand, is entirely based on symbolic slope projection which is a generalization of the original approach to symbolic projection. Contrary to the first approach, the landmark-agent relations play a more fundamental role since they can easily be determined. Common to both approaches are that they are based on qualitative reasoning techniques.

The joint representation of spatial and temporal phenomena is relevant in many research areas, including spatio-temporal reasoning, video sequence representation and querying by-contents. In this chapter, an original language for the symbolic representation of the contents of dynamic scenes is presented. This language incorporates and extends concepts of Temporal Logic to deal in an uniform way with both time and space, and supports metric qualifiers for distance and speed.

2D strings are one of a few representation structures originally designed for use in an IDB environment. In this chapter, a generalized approach for 2D string based indexing, which avoids an exhaustive search through the entire database of previous 2D string based techniques, is proposed. The classical framework of representation of 2D strings is also specialized to the cases of scaled and unscaled images. Index structures for supporting retrieval by content, utilizing the 2D string representation framework, are also discussed. The performance of the proposed method is evaluated using a database of simulated images and compared with the performance of existing techniques of 2D string indexing and retrieval. The results demonstrate a very significant improvement in retrieval performance.

We now consider the problem of how to efficiently retrieve pictures from a large database. A query should retrieve all input pictures which satisfy a given pattern expression, where this pattern expression may involve Boolean operators applied to a given set of permissible subpatterns. The number of permissible subpatterns determine whether a simple linear search, hashing, or a decision tree would give the best performance. For on the order of 1,000,000 patterns or more, the decision tree algorithm which we present here has the advantage of being able to rule out most nonmatching patterns without performing any disk accesses. Similar to the trie-hashing algorithm [8], this decision tree indexing method stores only those subpatterns which are needed to distinguish a set of input pictures, and the decision tree does not need to store the whole patterns. The whole indexing structure can thus be usually stored in the main memory, making it possible to access the needed data with a single disk access. We describe in detail how the decision tree algorithm works on 2D strings [6], which are short representations of the spatial relationships between the elements of a given symbolic picture is corresponding to a real image.

The 2D string, proposed by Chang et al. is a spatial index structure which preserves the information of spatial relationships in a spatial database. In this paper, two new image retrieval algorithms for 2D string are proposed. The first one improves the retrieval efficiency, while the second reduces the space requirement. The performance analysis shows that the two methods perform much better than previous works especially when the spatial database is large.

A multimedia database is a database of multimedia documents and their constituent components (images, video, audio, and text). Efficient storage of the virious media aided by specialized indexing techniques and fast retrieval describes the essential functionality required of a multimedia database system. A prototype multimedia database system is described here. The prototype system incorporates iconic indexing for each of the major multimedia data types: image; audio; video; and document. The indexes provide a method for user-oriented, content-based retrieval of data. The indexes are based on spatial and/or temporal relationships between pairs of objects in the item being indexed.

This chapter describes a prototype system for querying ship data through a graphical user interface. The queries use symbolic descriptions of component objects of the ships and the objects' relative locations. The basic approach is to encode 3D structure via pairwise spatial relations in a standard relational database. This allows one to take advantage of efficient searches based on standard SQL queries.