CONTENT-BASED IMAGE AND VIDEO RETRIEVAL USING SPATIAL AND TEMPORAL RELATIONS

Abstract

Interest in the area of multimedia databases is growing rapidly with the continuous evolution of telecommunication and computing technologies. A number of applications in digital libraries, telemedicine, GIS, tourism etc. are expected to use general purpose multimedia database systems. In order to make use of this vast information, efficient and effective techniques to analyze and retrieve multimedia information based on its content are required to be developed. This thesis is dedicated to the content-based retrieval of two of most important media types: images and video. New approaches to image representation, indexing and retrieval of images by content and video retrieval using spatial and temporal relations are presented. As regards to image data types a technique for logical representation of image objects based on Regulated Morphological Skeleton Transform (RMST) is introduced. RMST preserves the skeleton properties including information preservation and progressive visualization. To maintain consistency of object names throughout the database, a compact logical shape representation and recognition scheme, which adopts RMST as shape representation formalism is presented. A shape recognition algorithm, the Regulated Skeleton Matching Algorithm (RSMA) is proposed that renders the similarity between two shapes represented by RMST as a distance measure. The RSMA is based on similar concepts as that of the Skeleton Matching Algorithm (SMA) but it is less sensitive to noise and deformed shape boundaries. The RSMA has been tested using the original Trademark shape database of size 1,100. Results show that the RSMA achieves better object recognition rate than the SMA for sample noisy Trademark shapes while maintaining the same time complexity. A new approach for content-based image retrieval by spatial similarity is presented. This approach is based on the number of domain objects common to the query and database images, and directional relations and topological relations between domain objects in the images as perceived by humans. Linguistic definitions of spatial relations between image objects using histogram of forces are presented. An algorithm, SIMfspa, for processing spatial similarity queries is proposed. SIMfspa recognizes images even after they undergo translation, scaling, rotation, or any arbitrary combination of these transformations. The effectiveness of SIMfSpa was tested on TESSA image collection and intuition test database and is found to be robust with respect to human perception of spatial relations. The algorithm has quadratic time complexity in terms of the total number of objects in the query image. To facilitate efficient processing of spatial similarity queries by SIMfspa algorithm, an indexing scheme based on bitmap indexes is presented. The indexing scheme acts as a filter and spatial similarity computation is performed only on those images that pass through the filter. The proposed scheme ensures "no false positives' and 'no false negatives' and it recognizes translation, scaling and rotation variant images of the query image as relevant to the query. The TESSA image database was used to test the robustness of the proposed scheme. The results show that the task of similarity computation was reduced to 1/10th for the example queries and the database used implying the effectiveness of the proposed indexing scheme. The ranking obtained by SIMfipa algorithm after indexing was similar to the one obtained without using any indexing scheme. Lastly, a new approach for video content description is presented that supports spatio-temporal queries. Afuzzy spatio-temporal model is introduced which a based on fuzzy directional relations, topological relation and fuzzy temporal relation. Fuzzy definitions of temporal relations are proposed in order to minimize errors in segmentation, event and object detection in a video due to use of precise spatial relations and the noise in the data. In addition, the second order temporal relations are also presented that are more informative and provide global information about the video sequence. A video sequence representation scheme is presented using the proposed model that represents fuzzy spatio-temporal relationships among the objects in video sequences in the database and ranks the database sequences based on the query for effective content-based retrieval. The experimental results on MPEG-7 video dataset have validated the proposed approach.