A Graph-based Approach For Modeling And Indexing Video Data

With the advances in electronic imaging, storage, networking and computing, the amount of digital video has grown tremendously. The proliferation of video data has led to significant amount of research on techniques and systems for efficient video database management. In particular, extensive research has been done on video data modeling to manage and organize the data that is semantically rich and complicated. However, the enormous amount of data size and its complexity have restricted the progress on video data modeling, indexing and retrieval. In order to get around the problems, we turn to a graph theoretical approach for video database. Since a graph is a powerful tool for pattern representation and classification in various applications, it can represent complicated patterns and relationships of video objects easily. In this dissertation, in order to capture the spatio-temporal characteristics of video object, we first propose a new graph-based video data structure, called Spatio-Temporal Region Graph (STRG), which represents spatio-temporal features and the correlations among the video objects. A Region Adjacency Graph (RAG) is generated from each frame, and an STRG is constructed by connecting RAGs. An STRG is segmented into a number of pieces based on its content for efficient processing. Then, each segmented STRG is decomposed into its subgraphs, called Object Graph (OG) and Background Graph (BG) in which redundant BGs are eliminated to reduce index size and search time. Next, we propose a new indexing of OGs by clustering them using unsupervised learning algorithms for more accurate indexing. In order to perform the clustering, we need a proper distance measure between two OGs. For the distance measure, we propose a new measure, Extended Graph Edit Distance (EGED) because the existing measures are not very suitable for OGs. The EGED is defined in non-metric space for clustering OGs, and it is extended to metric space to compute the key values for indexing. Based on the clusters of OGs and the EGED, we propose a new indexing structure STRG-Index which provides efficient retrieval. Based on the STRG data model and STRG-Index, we propose a graph-based query language named STRG-QL, which is extended from object-oriented language by adding several graph operations. To process the proposed STRG-QL queries, we introduce a rule-based query optimization that considers the hierarchical relationships among video segments. For more efficient query processing, we show how to use STRG-Index during the query processing.