Spatio-temporal composition of video objects: representation andquerying in video database systems

A key characteristic of video data is the associated spatial and temporal semantics. It is important that a video model models the characteristics of objects and their relationships in time and space. J.F. Allen's (1983) 13 temporal relationships are often used in formulating queries that contain the temporal relationships among video frames. For the spatial relationships, most of the approaches are based on projecting objects on a two or three-dimensional coordinate system. However, very few attempts have been made formally to represent the spatio-temporal relationships of objects contained in the video data and to formulate queries with spatio-temporal constraints. The purpose of the work is to design a model representation for the specification of the spatio-temporal relationships among objects in video sequences. The model describes the spatial relationships among objects for each frame in a given video scene and the temporal relationships (for this frame) of the temporal intervals measuring the duration of these spatial relationships. It also models the temporal composition of an object, which reflects the evolution of object's spatial relationships over the subsequent frames in the video scene and in the entire video sequence. Our model representation also provides an effective and expressive way for the complete and precise specification of distances among objects in digital video. This model is a basis for the annotation of raw video     

演员模型：一种多媒体数据表达模型

本文提出一种多媒体数据表达模型：演员模型，该模型建立在多媒体数据库概念模型基础之上，基于库所—时间Ｐｅｔｒｉ网，描述多媒体对象之间的时态关系，同时引入与变迁相关联的场景表达式，描述多媒体对象之间的空间关系，从而模拟多媒体数据的时空编组，文中形式化地定义了演员模型的抽象模型和实现模型，提出多媒体对象的表达算法以及多媒体数据库的查询模型．     

Checking consistency in multimedia synchronization constraints

Constraint-based design is often used to correctly author a multimedia scenario due to its flexibility and efficiency. However, such a system must provide a mechanism with which users can easily manipulate the underlying structures to meet the application requirements. This paper proposes a novel method for analyzing multimedia synchronization constraints based on the constraint graph and classification, which is essential in developing efficient system support tools for constraint-based authoring systems. We specify temporal and spatial relations between multimedia objects, and use a directed graph to represent the constraints among the objects in a multimedia scenario. Moreover, we develop a method for analyzing temporal and spatial synchronization constraints based on graph theory, solving the problems of completeness checking, consistency checking, constraints relaxation and automatic spatio-temporal layout generation in a unified theoretical framework. We also discuss the effects of user interactive authoring. Compared with other methods, the proposed approach is simpler, more efficient, and easier to implement.     

Spatio-Temporal Modeling in Video and Multimedia Geographic Information Systems

The geographic application domain includes important information such as design plans, record drawings, photographs, and video data records. The corresponding geographic information systems (GISs) should maintain a specific model for each geographic data modality such as geographic video model for video records. Real-time 3-D geographic information systems provide comprehensive interface to complex and dynamic databases and truly immersive capability for visualizing geographic data. In cases, where information about location of geographic objects is needed at different moments of time, a GIS should process video data that is directly manipulated and retrieved through representation of its spatio-temporal characteristics. In this context, the most advanced multimedia form—digital video, finds an efficient application in GIS for versatile specification of geographic data. In this paper, a model for spatial data evolving with time is introduced in the context of video data manipulation. We designed a model that represents the spatio-temporal continuum among geographic objects in geographic video sequences, or digital video. The model developed here was motivated by the requirements for manipulating, managing, and analyzing geographic data for the necessities of infrastructure management, urban and regional planning, hazard prevention and management, transportation networks, vehicles routing, etc. This model allows the important issues for GIS such as conditions of adjacency (what is next to what), containment (what is enclosed by what), and proximity (how close one geographic object is to another) to be determined. Our model describes the spatial relationships among objects for each key frame in a given video scene, and the temporal relationships of the temporal intervals measuring the validity duration of the spatial relationships spanning over the given key frame. One of the main GIS issues—distance estimation, is solved as quantitative metrics of geographic objects in digital video are easily and precisely specified. This model is a basis for annotation of raw video for subsequent use in geographic video databases and digital libraries that provide access to and efficient storage of large volume of geographic data.     

A cost model for spatio-temporal queries using the TPR-tree

A query optimizer requires cost models to calculate the costs of various access plans for a query. An effective method to estimate the number of disk (or page) accesses for spatio-temporal queries has not yet been proposed. The TPR-tree is an efficient index that supports spatio-temporal queries for moving objects. Existing cost models for the spatial index such as the R-tree do not accurately estimate the number of disk accesses for spatio-temporal queries using the TPR-tree, because they do not consider the future locations of moving objects, which change continuously as time passes.In this paper, we propose an efficient cost model for spatio-temporal queries to solve this problem. We present analytical formulas which accurately calculate the number of disk accesses for spatio-temporal queries. Extensive experimental results show that our proposed method accurately estimates the number of disk accesses over various queries to spatio-temporal data combining real-life spatial data and synthetic temporal data. To evaluate the effectiveness of our method, we compared our spatio-temporal cost model (STCM) with an existing spatial cost model (SCM). The application of the existing SCM has the average error ratio from 52% to 93%, whereas our STCM has the average error ratio from 11% to 32%.     

弱同步及其在WWW上的应用

在当今世界,WWW已经成为新颖而强大的媒体,但是,现在运行于Web上的应用仍然不是完全多媒体化的.这主要是因为Internet网络是不可靠、尽力型的,无法提供数据实时传输的保证,尤其对那些大数据量的连续媒体(如视频与音频数据).因此,在Web环境中多媒体对象间的同步就变得格外复杂.该文提出了一种新颖的同步模型：弱同步.它使多媒体文档即使在多变的环境下也能获得最佳效果.在弱同步中,不仅可以定义对象间确定的时间关系,也可以定义非确定的时间关系.此外,媒体间的同步关系,如严格同步和松散同步,也可以在文档的同步描述中定义.     

A Multimedia Data Mining Framework: Mining Information from Traffic Video Sequences

The analysis and mining of traffic video sequences to discover important but previously unknown knowledge such as vehicle identification, traffic flow, queue detection, incident detection, and the spatio-temporal relations of the vehicles at intersections, provide an economic approach for daily traffic monitoring operations. To meet such demands, a multimedia data mining framework is proposed in this paper. The proposed multimedia data mining framework analyzes the traffic video sequences using background subtraction, image/video segmentation, vehicle tracking, and modeling with the multimedia augmented transition network (MATN) model and multimedia input strings, in the domain of traffic monitoring over traffic intersections. The spatio-temporal relationships of the vehicle objects in each frame are discovered and accurately captured and modeled. Such an additional level of sophistication enabled by the proposed multimedia data mining framework in terms of spatio-temporal tracking generates a capability for automation. This capability alone can significantly influence and enhance current data processing and implementation strategies for several problems vis-à-vis traffic operations. Three real-life traffic video sequences obtained from different sources and with different weather conditions are used to illustrate the effectiveness and robustness of the proposed multimedia data mining framework by demonstrating how the proposed framework can be applied to traffic applications to answer the spatio-temporal queries.     

Collaborative Multimedia Presentations in Mobile Environments

Distributed multimedia documents systems, distributed video servers are examples of multimedia presentations involving collaboration among multiple information sources. In such applications, objects have to be retrieved from their sources and presented to users according to specified temporal relationships. Objects retrieval in these collaborative applications is influenced by their presentation times, durations, and network throughput available to their sources. Replication of objects amongst the set of collaborating systems gives a choice for object retrieval. Client going through a multimedia presentation can be in a mobile environment. Here, object retrievals from collaborating servers are carried out by base stations to which the client is attached. Mobile client then downloads objects from the base station.In this paper, we present a graph-search based algorithm for computing and negotiating throughput requirements of collaborating multimedia presentations with replicated objects in a mobile environment. This algorithm maximizes the number of cached objects (that have already been played) for handling operations such as reverse presentation.     

A spatio-temporal semantic model for multimedia database systemsand multimedia information systems

As more information sources become available in multimedia systems, the development of abstract semantic models for video, audio, text, and image data is becoming very important. An abstract semantic model has two requirements: it should be rich enough to provide a friendly interface of multimedia presentation synchronization schedules to the users and it should be a good programming data structure for implementation in order to control multimedia playback. An abstract semantic model based on an augmented transition network (ATN) is presented. The inputs for ATNs are modeled by multimedia input strings. Multimedia input strings provide an efficient means for iconic indexing of the temporal/spatial relations of media streams and semantic objects. An ATN and its subnetworks are used to represent the appearing sequence of media streams and semantic objects. The arc label is a substring of a multimedia input string. In this design, a presentation is driven by a multimedia input string. Each subnetwork has its own multimedia input string. Database queries relative to text, image, and video can be answered via substring matching at subnetworks. Multimedia browsing allows users the flexibility to select any part of the presentation they prefer to see. This means that the ATN and its subnetworks can be included in multimedia database systems which are controlled by a database management system (DBMS). User interactions and loops are also provided in an ATN. Therefore, ATNs provide three major capabilities: multimedia presentations, temporal/spatial multimedia database searching, and multimedia browsing     

Adaptive and incremental processing for distance join queries

A spatial distance join is a relatively new type of operation introduced for spatial and multimedia database applications. Additional requirements for ranking and stopping cardinality are often combined with the spatial distance join in online query processing or Internet search environments. These requirements pose new challenges as well as opportunities for more efficient processing of spatial distance join queries. In this paper, we first present an efficient k-distance join algorithm that uses spatial indexes such as R-trees. Bidirectional node expansion and plane-sweeping techniques are used for fast pruning of distant pairs, and the plane-sweeping is further optimized by novel strategies for selecting a sweeping axis and direction. Furthermore, we propose adaptive multistage algorithms for k-distance join and incremental distance join operations. Our performance study shows that the proposed adaptive multistage algorithms outperform previous work by up to an order of magnitude for both k-distance, join and incremental distance join queries, under various operational conditions.     

A spatio-temporal geometry-based model for digital documentation of historical living systems

Representations used in digital documentation applications today usually assume a world that only exists in the present. Information contained within a database may be added-to or modified over time, but change through time is seldom maintained. This limitation of current IT has recently received attention, given the increasingly urgent need to understand geographical processes and cause-and-effect inter-relationships between human activities and the environment. Models proposed for the representation of spatio-temporal data are extensions of traditional raster and vector representations that can be seen as location- or feature-based, respectively, and are therefore best organized for performing, either location- or feature-based queries. In this paper, a new spatio-temporal data model suitable for digital documentation of historical living systems (artefacts, monuments and sites) is defined: it is based on 3D geometry and intended to facilitate analysis of temporal relationships and patterns of 3D modeling changes through time. This is particularly useful to both IT and IS managers, researchers and practitioners. It is shown that time-based queries related to 3D models of objects can be processed in an efficient and straightforward manner using the model. Finally, analytical time efficiency estimations are given, showing that the model is also an efficient and compact representation of spatio-temporal information.     

Indexing moving objects for directions and velocities queries

Moving object databases are required to support different types of queries with a large number of moving objects. New types of queries namely directions and velocity queries (DV queries), are to be supported and covered. The TPR-tree and its successors are efficient indexes that support spatio-temporal queries for moving objects. However, neither of them support the new DV queries. In this paper, we propose a new index for moving objects based on the TPR*-tree, named Direction and Velocity of TPR*-tree or DV-TPR*-tree, in order to build data a structure based on the spatial, direction and velocity domains. DV-TPR*-tree obtains an ideal distribution that supports and fulfils the new query types (DV queries). Extensive performance studies show that the query performance of DV-TPR*-tree outperforms the TPR-tree and its successors.     

Reconfigurable media processing

Multimedia processing is becoming increasingly important with wide variety of applications ranging from multimedia cell phones to high definition interactive television. Media processing techniques typically involve the capture, storage, manipulation and transmission of multimedia objects such as text, handwritten data, audio objects, still images, 2D/3D graphics, animation and full-motion video. A number of implementation strategies have been proposed for processing multimedia data. These approaches can be broadly classified into two major categories, namely (i) general purpose processors with programmable media processing capabilities, and (ii) dedicated implementations (ASICs). We have performed a detailed complexity analysis of the recent multimedia standard (MPEG-4) which has shown the potential for reconfigurable computing, that adapts the underlying hardware dynamically in response to changes in the input data or processing environment. We therefore propose a methodology for designing a reconfigurable media processor. This involves hardware–software co-design implemented in the form of a parser, profiler, recurring pattern analyzer, spatial and temporal partitioner. The proposed methodology enables efficient partitioning of resources for complex and time critical multimedia applications.     

Spatio-temporal predicates

Investigates temporal changes of topological relationships and thereby integrates two important research areas: first, 2D topological relationships that have been investigated quite intensively, and second, the change of spatial information over time. We investigate spatio-temporal predicates, which describe developments of well-known spatial topological relationships. A framework is developed in which spatio-temporal predicates can be obtained by temporal aggregation of elementary spatial predicates and sequential composition. We compare our framework with two other possible approaches: one is based on the observation that spatio-temporal objects correspond to 3D spatial objects for which existing topological predicates can be exploited. The other approach is to consider possible transitions between spatial configurations. These considerations help to identify a canonical set of spatio-temporal predicates     

一种预测性连续时空区域查询处理方法

预测性连续时空区域查询在用户指定的时间范围期间持续地返回给定未来查询时间范围期间将出现在查询区域的移动对象。论文提出了一种预测性连续时空区域查询处理方法,设计了支持连续查询处理的两种索引结构。移动对象索引用于记录移动对象不断更新的位置信息,它用于支持查询的首次处理。连续查询索引结构用于记录所有查询结果可能受到移动对象位置变化影响的连续查询,它用于支持连续查询处理。实验表明,论文提出的方法能够有效地提高处理大量连续查询的效率。     

Moving GeoPQL: a pictorial language towards spatio-temporal queries

Nowadays, two of the main challenges involving spatio-temporal databases concern the integration of their spatial and temporal features to store and query spatial objects changing over time, and the development of a simple and friendly language to query spatio-temporal data. In this paper we gather these two challenges by proposing Moving GeoPQL, a language defined in order to express spatio-temporal queries, extending the Geographical Pictorial Query language (GeoPQL). The proposed evolution is based on the concept of temporal layer that allows specifying the spatial configuration of moving objects in a time interval. More layers allow representing changes in terms of spatial configurations. Some examples of query formulation and system operation are described in the article. Finally, an experiment has been carried out for evaluating the usability of the Moving GeoPQL system. Results of this experiment showed that it facilitates the spatio-temporal query formulation since it is more user-friendly and ease to use compared to textual query languages.     

Intelligent fuzzy queries for multimedia databases

Multimedia databases have emerged to cope up with the huge amount of multimedia data, which comes up as a result of technological advancement. However, more intelligent techniques are required to satisfy different query requirements of multimedia users. This study extends the query capability of a multimedia database through the integration of a fuzzy rule‐based system. In addition to fuzzy semantic rules, which deduce new information from the data stored in the database, fuzzy spatial and temporal relations, which are inherent to multimedia applications, are defined in the rule‐based system. Users can formulate fuzzy semantic, spatial, temporal, and spatiotemporal queries, resulting in the deduction of new information using the rules defined in the rule‐based system. With some practical examples, the paper presents how a fuzzy rule‐based system integrated to a fuzzy multimedia database improves the query capabilities of the database system intelligently. © 2011 Wiley Periodicals, Inc.     

Continuous Query Processing of Spatio-Temporal Data Streams in PLACE

The tremendous increase in the use of cellular phones, GPS-like devices, and RFIDs results in highly dynamic environments where objects as well as queries are continuously moving. In this paper, we present a continuous query processor designed specifically for highly dynamic environments (e.g., location-aware environments). We implemented the proposed continuous query processor inside the PLACE server (Pervasive Location-Aware Computing Environments); a scalable location-aware database server developed at Purdue University. The PLACE server extends data streaming management systems to support location-aware environments. These environments are characterized by the wide variety of continuous spatio-temporal queries and the unbounded spatio-temporal streams. The proposed continuous query processor includes: (1) New incremental spatio-temporal operators to support a wide variety of continuous spatio-temporal queries, (2) Extended semantics of sliding window queries to deal with spatial sliding windows as well as temporal sliding windows, and (3) A shared-execution framework for scalable execution of a set of concurrent continuous spatio-temporal queries. Experimental evaluation shows promising performance of the continuous query processor of the PLACE server. This work was supported in part by the National Science Foundation under Grants IIS-0093116, IIS-0209120, and 0010044-CCR.     

Hair-oriented data model for spatio-temporal data representation

Having an effective data structure regards to fast data changing is one of the most important demands in spatio-temporal data. Spatio-temporal data have special relationships in regard to spatial and temporal values. Both types of data are complex in terms of their numerous attributes and the changes exhibited over time. A data model that is able to increase the performance of data storage and inquiry responses from a spatio-temporal system is demanded. The structure of the relationships between spatio-temporal data mimics the biological structure of the hair, which has a ‘Root’ (spatial values) and a ‘Shaft’ (temporal values) and undergoes growth. This paper aims to show the mathematical formulation of a Hair-Oriented Data Model (HODM) for spatio-temporal data and to demonstrate the model's performance by measuring storage size and query response time. The experiment was conducted by using more than 178,000 records of climate change spatio-temporal data that were implemented in implemented in an object-relational database using nested tables. The data structure and operations are implemented by SQL statements that are related to the concepts of Object-Relational databases. The performances of file storage and execution query are compared using a tabular and normalized entity relationship model that engages various types of queries. The results show that HODM has a lower storage size and a faster query response time for all studied types of spatio-temporal queries. The significances of the work are elaborated by doing comparison with the generic data models. The experimental results showed that the proposed data model is easier to develop and more efficient.     

Indexing of now-relative spatio-bitemporal data

Real-world entities are inherently spatially and temporally referenced, and database applications increasingly exploit databases that record the past, present, and anticipated future locations of entities, e.g., the residences of customers obtained by the geo-coding of addresses. Indices that efficiently support queries on the spatio-temporal extents of such entities are needed. However, past indexing research has progressed in largely separate spatial and temporal streams. Adding time dimensions to spatial indices, as if time were a spatial dimension, neither supports nor exploits the special properties of time. On the other hand, temporal indices are generally not amenable to extension with spatial dimensions. This paper proposes the first efficient and versatile index for a general class of spatio-temporal data: the discretely changing spatial aspect of an object may be a point or may have an extent; both transaction time and valid time are supported, and a generalized notion of the current time, now, is accommodated for both temporal dimensions. The index is based on the R-tree and provides means of prioritizing space versus time, which enables it to adapt to spatially and temporally restrictive queries. Performance experiments are reported that evaluate pertinent aspects of the index. Edited by T. Sellis. Received: 7 December 2000 / Accepted: 1 September 2001 Published online: 18 December 2001