Rule-based spatiotemporal query processing for video databases

In our earlier work, we proposed an architecture for a Web-based video database management system (VDBMS) providing an integrated support for spatiotemporal and semantic queries. In this paper, we focus on the task of spatiotemporal query processing and also propose an SQL-like video query language that has the capability to handle a broad range of spatiotemporal queries. The language is rule-based in that it allows users to express spatial conditions in terms of Prolog-type predicates. Spatiotemporal query processing is carried out in three main stages: query recognition, query decomposition, and query execution.Received: 11 October 2001, Accepted: 3 October 2003, Published online: 12 December 2003Edited by: A. Buchmann Correspondence to: Özgür UlusoyThis work is supported by the Scientific and Research Council of Turkey (TÜBITAK) under Project Code 199E025. This work was done while the first author was at Bilkent University.     

Smart VideoText: a video data model based on conceptual graphs

An intelligent annotation-based video data model called Smart VideoText is introduced. It utilizes the conceptual graph knowledge representation formalism to capture the semantic associations among the concepts described in text annotations of video data. The aim is to achieve more effective query, retrieval, and browsing capabilities based on the semantic content of video data. Finally, a generic and modular video database architecture based on the Smart VideoText data model is described.     

Scalable multi-feature index structure for music databases

The management of large collections of music data in a multimedia database has received much attention in the past few years. In the majority of current work, researchers extract the features, such as melodies, rhythms, and chords, from the music data and develop indices that will help to retrieve the relevant music quickly. Several reports have pointed out that these music features can be transformed and represented in forms of music feature strings or numeric values so that indices can be created for music retrieval. However, there are only a small number of existing approaches which introduce multi-feature index structures for music queries while most of the others are for developing single feature indices. The existing music multi-feature index structures are memory consuming and have lack of scalability. In this paper, we will propose a two-tier music index structure which is an efficient and scalable approach for multi-feature music indexing. Our experimental results show that this new approach outperforms existing multi-feature index schemes.     

An efficient query optimization strategy for spatio-temporal queries in video databases

The interest for multimedia database management systems has grown rapidly due to the need for the storage of huge volumes of multimedia data in computer systems. An important building block of a multimedia database system is the query processor, and a query optimizer embedded to the query processor is needed to answer user queries efficiently. Query optimization problem has been widely studied for conventional database systems; however it is a new research area for multimedia database systems. Due to the differences in query processing strategies, query optimization techniques used in multimedia database systems are different from those used in traditional databases. In this paper, a query optimization strategy is proposed for processing spatio-temporal queries in video database systems. The proposed strategy includes reordering algorithms to be applied on query execution tree. The performance results obtained by testing the reordering algorithms on different query sets are also presented.     

Handling temporal heterogeneous data for content-based management of large video collections

Video document retrieval is now an active part of the domain of multimedia retrieval. However, unlike for other media, the management of a collection of video documents adds the problem of efficiently handling an overwhelming volume of temporal data. Challenges include balancing efficient content modeling and storage against fast access at various levels. In this paper, we detail the framework we have built to accommodate our developments in content-based multimedia retrieval. We show that not only our framework facilitates the development of processing and indexing algorithms but it also opens the way to several other possibilities such as rapid interface prototyping or retrieval algorithm benchmarking. Here, we discuss our developments in relation to wider contexts such as MPEG-7 and the TREC Video Track.This work is funded by EU-FP6 IST-NoE SIMILAR () and the Swiss NCCR IM2 (Interactive Multimodal Information Management).     

An efficient approach for continuous density queries

In location-based services, a density query returns the regions with high concentrations of moving objects (MOs). The use of density queries can help users identify crowded regions so as to avoid congestion. Most of the existing methods try very hard to improve the accuracy of query results, but ignore query efficiency. However, response time is also an important concern in query processing and may have an impact on user experience. In order to address this issue, we present a new definition of continuous density queries. Our approach for processing continuous density queries is based on the new notion of a safe interval, using which the states of both dense and sparse regions are dynamically maintained. Two indexing structures are also used to index candidate regions for accelerating query processing and improving the quality of results. The efficiency and accuracy of our approach are shown through an experimental comparison with snapshot density queries.     

Natural language querying for video databases

The video databases have become popular in various areas due to the recent advances in technology. Video archive systems need user-friendly interfaces to retrieve video frames. In this paper, a user interface based on natural language processing (NLP) to a video database system is described. The video database is based on a content-based spatio-temporal video data model. The data model is focused on the semantic content which includes objects, activities, and spatial properties of objects. Spatio-temporal relationships between video objects and also trajectories of moving objects can be queried with this data model. In this video database system, a natural language interface enables flexible querying. The queries, which are given as English sentences, are parsed using link parser. The semantic representations of the queries are extracted from their syntactic structures using information extraction techniques. The extracted semantic representations are used to call the related parts of the underlying video database system to return the results of the queries. Not only exact matches but similar objects and activities are also returned from the database with the help of the conceptual ontology module. This module is implemented using a distance-based method of semantic similarity search on the semantic domain-independent ontology, WordNet.     

An indexing scheme for energy-efficient processing of content-based retrieval queries on a wireless data stream

Wireless data broadcasting is a popular data delivery approach in mobile computing environments, where the broadcasting servers usually adopt indexing schemes for mobile clients to energy-efficiently access data on a wireless broadcast stream. However, conventional indexing schemes use primary key attribute values to construct tree structures. Therefore, these schemes do not support content-based retrieval queries such as partial-match queries and range-queries. This paper proposes an indexing method that supports content-based retrieval queries on a wireless data stream. The method uses a tree-structured index, called B2V-Tree, which is composed of bit-vectors that are generated from data records through multi-attribute hashing. Through analysis and experiments, the effectiveness of the proposed method is shown.     

A multi-level abstraction and modeling in video databases

In this paper, we propose a multi-level abstraction mechanism for capturing the spatial and temporal semantics associated with various objects in an input image or in a sequence of video frames. This abstraction can manifest itself effectively in conceptualizing events and views in multimedia data as perceived by individual users. The objective is to provide an efficient mechanism for handling content-based queries, with the minimum amount of processing performed on raw data during query evaluation. We introduce a multi-level architecture for video data management at different levels of abstraction. The architecture facilitates a multi-level indexing/searching mechanism. At the finest level of granularity, video data can be indexed based on mere appearance of objects and faces. For management of information at higher levels of abstractions, an object-oriented paradigm is proposed which is capable of supporting domain specific views.     

A compact multi-resolution index for variable length queries in time series databases

We study the problem of searching similar patterns in time series data for variable length queries. Recently, a multi-resolution indexing technique (MRI) was proposed in (Kahveci and Singh, in proceedings of the international conference on data engineering, pp. 273–282, 2001; Kahveci and Singh, IEEE Trans Knowl Data Eng 16(4):418–433, 2004) to address this problem, which uses compression as an additional step to reduce the index size. In this paper, we propose an alternative technique, called compact MRI (CMRI), which uses adaptive piecewise constant approximation (APCA) representation as dimensionality reduction technique, and which occupies much less space without requiring compression. We implemented both MRI and CMRI, and conducted extensive experiments to evaluate and compare their performance on real stock data as well as synthetic. Our results indicate that CMRI provides a much better precision ranging from 0.75 to 0.89 on real data, and from 0.80 to 0.95 on synthetic data, while for MRI, these ranges are from 0.16 to 0.34, and from 0.03 to 0.65, respectively. Compared to sequential scan, we found that CMRI is 4–30 times faster and the number of disk I/Os it required is close to minimal. In terms of storage utilization, CMRI occupies 1% of the memory occupied by MRI. These results and analysis show CMRI to be an efficient and scalable indexing technique for large time series databases.     

An Efficient Algorithm for Processing Multi-Relation Queries in Relational Databases

After a relation scheme R is decomposed into the set of schemes ρ={R1，…，Rn},we may pose queries as if Rexisted in the database,taking a join of Ri‘s,when it is necessary to implement the query,Suppos a query involves a set of attributes S R，we want to find the smallest subset of ρ whose union includes.S.We prove that the problem is NP-complete and present a polynomial-bounded approximation algorithm.A subset of ρ whose union includes S and has a decomposition into 3NF with a lossless join and preservation of dependencies in given in the paper.     

海量监控视频快速回放与检索技术

为解决海量监控视频的快速浏览和检索,介绍了一种基于目标索引的视频摘要和检索方法。该方法在光流分析的基础上,在画面的静止区域更新背景,运动的区域利用差分法分割出运动目标图像。经过优化的快速特征匹配和建立运动跟踪模型后,根据目标运动轨迹,按照时空距离进行聚类。在目标图像数据和运动参数进行XML结构化存储为索引的基础上,最后在检索时将符合条件的所有目标图像,按照其原有时间顺序逐帧贴到同一个背景图像中,形成动态的摘要视频。由于该方法剔除了背景中大量的时空冗余信息,可在较短回放时间内浏览全部有用目标,显著提高海量监控视频的查阅效率。     

Exploring video content structure for hierarchical summarization

In this paper, we propose a hierarchical video summarization strategy that explores video content structure to provide the users with a scalable, multilevel video summary. First, video-shot- segmentation and keyframe-extraction algorithms are applied to parse video sequences into physical shots and discrete keyframes. Next, an affinity (self-correlation) matrix is constructed to merge visually similar shots into clusters (supergroups). Since video shots with high similarities do not necessarily imply that they belong to the same story unit, temporal information is adopted by merging temporally adjacent shots (within a specified distance) from the supergroup into each video group. A video-scene-detection algorithm is thus proposed to merge temporally or spatially correlated video groups into scenario units. This is followed by a scene-clustering algorithm that eliminates visual redundancy among the units. A hierarchical video content structure with increasing granularity is constructed from the clustered scenes, video scenes, and video groups to keyframes. Finally, we introduce a hierarchical video summarization scheme by executing various approaches at different levels of the video content hierarchy to statically or dynamically construct the video summary. Extensive experiments based on real-world videos have been performed to validate the effectiveness of the proposed approach.Published online: 15 September 2004 Corespondence to: Xingquan ZhuThis research has been supported by the NSF under grants 9972883-EIA, 9974255-IIS, 9983248-EIA, and 0209120-IIS, a grant from the state of Indiana 21^th Century Fund, and by the U.S. Army Research Laboratory and the U.S. Army Research Office under grant DAAD19-02-1-0178.     

A survey on the use of pattern recognition methods for abstraction, indexing and retrieval of images and video

The need for content-based access to image and video information from media archives has captured the attention of researchers in recent years. Research efforts have led to the development of methods that provide access to image and video data. These methods have their roots in pattern recognition. The methods are used to determine the similarity in the visual information content extracted from low level features. These features are then clustered for generation of database indices. This paper presents a comprehensive survey on the use of these pattern recognition methods which enable image and video retrieval by content.     

An efficient location update mechanism for continuous queries over moving objects

In a moving-object database system that supports continuous queries (CQ), an important problem is to keep the location data consistent with the actual locations of the entities being monitored, in order to produce correct query results. This goal is often difficult to achieve due to limited network resources. However, if an object is not required by any query, its value need not be refreshed. Based on this observation, we redefine the notion of temporal consistency of data items with respect to the query result, where only data items that are relevant to the CQs need to be fresh. To exploit this correctness definition, we develop an adaptive time-based update technique called query-result update (QRU). The advantage of this technique is that it identifies objects with different levels of significance to the correctness of query results. Locations of objects that have more impact to the query result are acquired more frequently than the ones that do not.     

电视台视频资料库管理的关键技术

提出了电视台视频资料库管理的总体框架，并对其中的两个关键技术：存储架构和视频检索技术进行了研究，提出了基于SAN的存储架构，并对一个经典的镜头分割算法进行了改进，以满足实时获取关键帧的需要。