Technical Reports Related to DISIMA Project

Abstract: The DISIMA project addresses the development of a distributed, interoperable image database management system enabling content-based querying. The aim of this thesis project is to add an interoperability feature to the existing prototype.

As object-oriented distributed computing platforms, OMA and, in particular, CORBA, can be helpful for database interoperability in terms of managing heterogeneity of
platform and communication levels. The complete distributed architecture will involve homogeneous systems and heterogeneous systems. In this project, the goal is to
develop a middleware on top of CORBA for homogeneous systems. In the simplest scenario, we can assume all the systems involved are DISIMA sites, and that they have
the same schema with different database instances.

This thesis thus describes the development of such simpler (but not trivial) scenario. We also highlight and justify some design decisions made as the project was
developed.

Abstract: Image similarity search is employed to retrieve similar images from a database. Colour features, particularly colour histograms, are extensively utilized to compute the image similarity. This thesis presents a multi-scale representation of image colour histograms that allows queries at different precision levels as well as queries on part of an image instead of an entire image.

Because image databases usually store a large number of images, sequential scanning of the database is not feasible; an index scheme is needed to speed up the similarity search. A new index structure --- three-dimensional extendible hash --- is designed to index image average colours. The average colours are used in a two-step colour similarity search: the index is searched first to filter the database before colour histogram comparisons are applied. Experiments have been made to test the performance of the three-dimensional extendible hash, and the results are discussed in this thesis.

Image Databases: A Content-Based Type System and Query By Similarity Match, Irene Lin-Oi Cheng, TR99-03, May 1999

Abstract: The use of on-line image repositories is growing and becoming commonplace. Due to the inadequacy of traditional databases in handling complex images and voluminous data, new designs and techniques are needed to efficiently organize, store, manage and retrieve images. It is felt that the Structural Query Language (SQL) and Object Query Language (OQL) lack the expressive power to describe image queries. Recently the Multimedia Object Query Language (MOQL) which is an extended version of OQL was defined in a PhD thesis at the University of Alberta. As part of the DISIMA (Distributed Image Database Management System) project, one goal of this report is to design and implement a content-based generic type system to support the storage and retrieval of images. The other goal is to design and implement a query parser and engine for the MOQL extension.

There has been research conducted in this area but most of it is application specific, focusing on selected features. The type system, discussed in this report, integrates all the features into a framework, which can be customized to meet the specific needs of applications.

Keywords: DISIMA, image database, image query, MOQL, Multimedia Object Query Language, content-based, similarity match.

Modeling and Querying Multimedia Data, John Zhong Li, TR98-05, March 1998

Abstract: Amidst the dramatic developments of computer technology in the last decades, we have seen a growing interest in supporting multimedia data. Compared with traditional data, the most noticeable features of multimedia data are their spatiality (the spatial layout of objects and their relationships), temporality (time-dependence in media such as video and audio), and presentation} requirements (imposed in response to user queries, such as synchronization of different media). Developing database management support for multimedia data poses interesting challenges.

Many multimedia database management systems have been developed to deal with these multimedia features. However, they suffer some common problems: lack of generality in media modeling, lack of precise knowledge of spatial information, limited spatio-temporal functionality, ineffective query languages, and inefficient query processing. The main purpose of this work is to investigate these problems and provide solutions. The first step of the research is to derive a multimedia data model which is built upon and extends existing models. The proposed model is based on a temporal interval algebra. The establishment of a multimedia data model provides a theoretical foundation that is used to investigate multimedia query languages. The result is a general-purpose, object-oriented multimedia query language which supports content-based information retrieval. A prototype has been built to validate the proposed concepts.

Keywords: multimedia, database, spatial, temporal, presentation, query language, object oriented, video, image, content-based retrieval

Modeling of Moving Objects in a Video Objectbase Management System, J. Z. Li, M.T. Ozsu, D. Szafron, TR96-12, April 1996.

Abstract: Modeling moving objects has become a topic of increasing interest in the area of video databases. Two key aspects of such modeling are object spatial and temporal relationships. In this paper we introduce an innovative way to represent the trajectory of a single moving object and the relative spatio-temporal relations between multiple moving objects. The representation supports a rich set of spatial topological and directional relations. It also supports both quantitative and qualitative user queries about moving objects. Algorithms for matching trajectories and spatio-temporal relations of moving objects are designed to facilitate query processing. These algorithms can handle both exact and similarity matches. We also discuss the integration of our moving object model, based on a video model, in an object-oriented system. Some query examples are provided to further validate the expressiveness of our model.

Keywords: multimedia, temporal, spatial, moving object, database, video.

Spatial Reasoning Rules in Multimedia Management Systems, J.Z. Li, M.T. Özsu and D. Szafron, TR96-05, March 1996

Abstract: In this paper we consider various spatial relationships that are of general interest for retrieving data from multimedia databases. We present a unified representation of spatial objects for both topological and directional relations. Such a representation is based on Allen's temporal interval algebra. We also present a set of spatial inference rules, which allow us to make heterogeneous spatial relation deductions from existing directional and topological relations. For example, if we know A north of B, B overlap with C, and C north of D, then we derive A above D. Since all the rules are propositional Horn clauses, they can be easily integrated into any multimedia database by using either a simple inference engine or a lookup table.

Keywords: spatial relation, topology, direction, interval, inference rule

Modeling Video Spatial Relationships in an Object Model, J.Z. Li, M.T. Özsu and D. Szafron, TR96-06, March 1996

Abstract: Video modeling has become a topic of increasing interest in the area of multimedia research. One of the key aspects in the video medium is spatial relationships. In this paper we propose a spatial representation, based on the temporal interval algebra, for specifying the spatial semantics of video data. Based on such a representation, a set of comprehensive spatial relationships for salient objects are defined in supporting qualrelationships for salient objects are defined in supporting qualitative and quantitative spatial properties. Further, both topological and directional spatial relationships are captured within the proposed model. We present a novel way of incorporating the spatial model into a video model, called a common video object tree, and integrating the abstract video model into an objectbase management system which has rich multimedia temporal operations. The integrated video objectbase management system supports a broad range of spatial queries and is extensible, thus allowing the easy incorporation of new features into the system. Our focus here is in supporting different types of spatial queries including direct spatial queries, hybrid spatial queries, complex spatial queries, computational spatial queries, and temporal spatial queries. The integrated model is further enhanced by a spatial inference engine. The powerful expressiveness of our video model are validated by many concrete query examples.

Keywords: multimedia, spatial, object-oriented, database, video model, query, clips

Video Modeling and Its Integration in a Temporal Object Model, J.Z. Li, I. Goralwalla, M.T. Özsu and D. Szafron, TR 96-02, January 1996

Abstract: Video modeling has become a topic of increasing interest in the area of multimedia research. One of the key aspects in the video medium is the temporal relationship between video frames. In this paper we propose a tree-based model for specifying spatial and temporal semantics of video data. Our focus here is on the temporal issues. We present a unique way of integrating our video model into an objectbase management system which has rich multimedia temporal operations. We further show how temporal histories are used to model video data. Using histories to model video data is both simple and natural. It also can lead to a uniform behavioral model. A user can then explore the video objectbase using object-oriented techniques. Such a seamless integration gives a uniform interface to end users. The integrated video objectbase management system supports a broad range of temporal queries and is extensible, thus allowing the easy incorporation of new features into the system.

Keywords: multimedia, temporal, object-oriented, database, video model, query, clips

Query Languages in Multimedia Database Systems J.Z. Li, M.T. Özsu and D. Szafron, TR 95-25, December 1995.

Abstract: Declarative query languages are an important feature of database management systems and have played an important role in their success. As database management technology enters the multimedia information system area, the availability of special-purpose query languages for multimedia applications will be equally important. In this report, we survey multimedia query languages and query models. Particularly, we look at those systems from the point of view of well-defined queries, fuzzy queries, visual queries, and query presentations. Several research issues, such as generic multimedia query languages, incremental queries, fuzzy queries, spatio-temporal queries, feature storage and organization, are also identified. In our opinion these are vital issues for the success and development of a multimedia query language.

A Study of Image Indexing Techniques for Multimedia Database Systems, Y. Niu, M.T. Özsu, and X. Li, TR 95-19, July 1995.

Abstract: The role of indexing in query optimization is well-understood in the database community. Indexes enable efficient access to a subset of a database. There have been many studies on indexing within the context of relational database management systems (RDBMS). The most popular indexing techniques are based on B-trees. However, these index structures do not apply for images in Multimedia Database Systems (MMDBS). Some novel index structures to retrieve images have been proposed. In this report, we discuss some issues concerning these advanced indexing techniques, and report the results.

University of Waterloo

Computer Science

M.T. Özsu