Multilevel Representation and Query Processing in Multimedia Database Systems

Arif Ghafoor (PI), Rangasami L. Kashyap (Co-PI), Shankar Moni (Co-PI)
Purdue University, West Lafayette, IN, 47907

Contact Information

Arif Ghafoor
School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, 47907
Phone: (765) 494-0638    Fax: (765) 494-3371    Email: ghafoor@ecn.purdue.edu

WWW PAGE

Distributed Multimedia Systems Laboratory (URL: http://shay.ecn.purdue.edu/~dmultlab/nsf_proj/)

Supported Students

Keywords

multimedia data representation, fuzzy queries, spatio-temporal modeling, content-based retrieval, image processing

Project Award Information

Project Summary

The goal of this project is to develop a multimedia database system with capabilities to handle heterogeneous media queries. This system caters to the computational and storage requirements while accommodating and exploiting the inevitable semantic and representational imprecisions. The design of this system is based on multilevel data models and search mechanisms. These methodologies facilitate the users for posing various types of queries, including: (i) low-level, such as finding objects in a multimedia database, (ii) mid-level, based on spatio-temporal semantics, such as locating events associated with multimedia data, and (iii) high-level, targeted towards searching pre-composed multimedia documents, based on constituent mono-media data, their spatio-temporal dimensions, and logical structure. The multi-level search mechanisms are tightly interlinked. Imprecision in the search results is modeled using a set of fuzzy parameters. The results of this research are helping develop a comprehensive framework for building wide variety of multimedia applications in commercial, educational, governmental and military sectors.

Goals, Objectives, and Targeted Activities

Our long term goals include the development of a generic multi-level representation of multimedia data that can overcome several challenges faced by the database community. In particular, for low-level data modeling our research will focus on evaluating the unsupervised classification approach for image segmentation using a log-likelihood function. Two image segmentation models, namely the facet model and the texture model, are being evaluated in terms of computation and exactness of match. We are also planning to develop and evaluate other models. For mid-level multimedia data representation, we are planning to develop indexing, Petri-net and neighborhood graph models for semantic modeling and managing fuzziness in query formulation.

Indication of Success

So far the stated objectives for this project have been met quite well, as demonstrated by the concrete research results produced to date. Success of this project in terms of quality research results has been aided by the collaboration between two researchers with backgrounds in image processing and multimedia databases. This collaboration has been instrumental in providing a sharp understanding of research challenges astride these areas. As a result of this unique collaboration, several research ideas and publications are being produced. The following research results has been obtained:
  1. We have developed a formulation for video segmentation and object tracking. This formulation does not require the supervision of a human user. Each frame in the video is partitioned into different segments and the segments are combined to form object traces. We have provided an algorithm that simultaneously partitions a video frame and obtains the parameters of the underlying classes. The problem of partitioning each frame is posed as a joint estimation of the partition and class parameter variables. By incorporating the partition information of the previous frame into the segmentation process of the current frame, our method implicitly uses the temporal information. Experimental results have shown that our method succeeds in capturing the object classes even when the objects undergo translations and rotations not in the plane of the image.
  2. We have proposed methods that serve as such spatio-temporal models for event-based retrieval of video. We have presented description of characteristics and identification of requirements for motion-based video retrieval. Based on this discussion, we have proposed two alternative and complementary schemes, trajectory and trail-based models for representing the motion in video. Trail-based models are proposed to handle temporal scale (speed) invariant searches. A Mellin transform based scale invariant pattern recognition technique has been used in our proposed algorithm to perform scale invariant searches. Trajectory based models handle most other types of motion-based searches in video data. Two algorithms for handling spatial translation-absolute Match has been proposed: A Fourier transform-based distance algorithm and a Two-stage algorithm that reduces the complexity of the first algorithm. We support the proposed motion representation models with effective and efficient searching techniques. In addition to general requirements such as flexibility and efficiency, these techniques categorically address the invariance features in spatial and temporal domain.
  3. For the search case that does not require any invariance feature, we have proposed computationally efficient searching techniques based on common statistical methods and carried out an extensive analysis. In addition to computational efficiency, these methods provide flexibility to the user in determining the right search parameters for optimum accuracy/performance tradeoff.
  4. User interface implementation: The proposed technique alleviates the limitations of keyword-based search techniques and provides an effective example-based query entry mechanism as part of the implementation. A video motion indexing tool has been developed to perform object tracking using a semi-automatic tracking tool for capturing MBR's. A query tool has been developed to facilitate the input of motion-based queries by sketch.
The project is expected to provide viable solutions for developing a general framework for developing multimedia databases needed for a broad range of applications. The NSF funding has provided an opportunity for this collaboration which would have been difficult, otherwise.

Project Impact and Output

Two students are currently pursuing their doctoral studies as part of this project. One student has completed his doctoral thesis in this area. The research results of this project have been incorporated in a graduate level course on multimedia systems (EE 624), which is taught by the PI. The project and its planned implementation is a cornerstone of the cutting-edge research being carried out in our lab. We anticipate interest from industrial organizations as the project matures and implementation-worthy results are produced.

Project References


[1] Shu-Ching Chen and R. L. Kashyap, "A Spatial-Temporal Semantic Model for Multimedia Presentations and Multimedia Database Systems" to appear in IEEE Trans. on Knowledge and Data Engineering.
[2] S. Dagtas, W. Al-Khatib, A. Ghafoor, and R. Kashyap, ``Models for Motion-based Video Indexing and Retrieval'', Submitted to IEEE Transactions on Image Processing
[3] S. Dagtas, W. Al-Khatib, A. Khokhar, and A. Ghafoor, ``Trail-Based Approach for Video Data Indexing and Retrieval'', Submitted to IEEE International Conference on Multimedia Computing and Systems (ICMCS)
[4] Y. F. Day, A. Khokhar, S. Dagtas, and A. Ghafoor, ``A Multi-level Abstraction and Modeling in Video Databases'', to appear in ACM Journal on Multimedia Systems.
[5] S. Sista and R. L. Kashyap, "Unsupervised Video Segmentation and Object Tracking," submitted to IEEE International Conference on Image Processing, Kobe, Japan, October 1999.
[6] Shu-Ching Chen and R. L. Kashyap, "Empirical Studies of Multimedia Semantic Models for Multimedia Presentations," 13th International Conference on Computer and Their Applications, Honolulu, Hawaii, USA, March 25-27, 1998.
[7] Shu-Ching Chen and R. L. Kashyap, "Temporal and Spatial Semantic Models for Multimedia Presentations," 1997 International Symposium on Multimedia Information Processing, Dec. 11-13, 1997.

Area Background

Our project is concerned with data management and information retrieval technologies essential for developing future multimedia systems. The emphasis of our research is on developing an automated system to allow multi-level data representation to assist query processing at different levels of abstraction. It will allow users to access images and video data based on appearance of objects as well as events surrounding these objects. The key tradeoff for users is between the accuracy of matching and the computational cost of the query. The framework developed for this project will provide solutions for challenging problems in multimedia data organization and integration, indexing and retrieval mechanisms, intelligent searching techniques, information browsing, content-based query processing and so forth. A large variety of potential applications will benefit from this framework.

Area References

There are several journals and conferences which have excellent coverage of issues in this area. They include: IEEE Multimedia; ACM Journal on Multimedia Systems; IEEE Trans. on Knowledge and Data Engineering; ACM Multimedia Conference; IEEE Int. Conf. on Multimedia Computing and Systems. Several special issues from IEEE Computer and ACM Journal on Multimedia Systems have been specifically devoted to this topic. Several industrial projects undertaken by IBM, Siemens, NEC, Oracle, Fuji Electric Co., etc., are focused on this topic.

Potential Related Projects

Within the NSF IDM program, several projects related to multimedia data modeling and management are being conducted in UCLA, Case Western Reserve University, University of Maryland, University of Nevada, University of Illinois at Chicago, University of California at Santa Barbara, University of Pittsburgh, University of Maine, and University of Washington.