A Sequence-Based Object-Oriented Model for Video Databases.
Structuration, annotation and composition are amidst the most crucial modeling issues that video editing and querying in the context of a database entail. In this paper, we propose a sequence-based, object-oriented data model that addresses them in an unified, yet orthogonal way. Thanks to this orthogonality, the interactions between these three aspects are properly captured, i.e., annotations may be attached to any level of video structuration, and all the composition operators preserve the structurations and annotations of the argument videos. We also propose to query both the structuration and the annotations of videos using an extension of ODMG's OQL which integrates a set of algebraic operators on sequences. The overall proposal is formalized and implemented on top of an object-oriented DBMS.
Introduction
For a long time, videos were managed by specific environments due to their huge size and
demanding hardware requirements. Improvements in data compression (such as MPEG-2),
continuously increasing network transfer rates and processing capacity, and advances in operating
systems, now allow conventional computing systems to handle videos, thereby opening
new application areas such as video-on-demand, video conferencing and home video editing.
The specificities of these applications have been addressed from several perspectives by a
large body of research works, prototypes and commercial tools (see [EJA + 97] for a survey).
Many of these efforts have focused on important performance issues related to storage, real-time
transfer in distributed environments, quality of service, synchronization, etc. However, as
the needs of these applications evolve, other issues such as content-based retrieval, summary
extraction, interactive editing and browsing, etc. become increasingly important. In particu-
lar, advances in automatic indexing techniques, together with video metadata standardization
efforts (such as MPEG-7), have accentuated the need for high-level representation models and
querying tools for video annotations.
In this setting, we believe that database technology is likely to play an increasingly important
role in video management, provided that it offers high-level concepts and interfaces for storing,
retrieving and editing video data. Our work is intended to be a contribution in this direction.
Video modeling in the context of a database entail numerous issues which have been addressed
separately in several works. In this paper we focus on three of them, namely structuration
(also known as segmentation), annotation, and composition, and we address them in
a comprehensive framework. This framework is essentially based on ideas developed in the
context of Temporal Databases [TCG assumes an underlying object-oriented
data model (e.g. the ODMG [CB97] one). However, modulo some restrictions, the
basic concepts can be adapted to an object-relational setting.
Since the proposed data model is based on concepts stemming from temporal databases, it
is possible to query it using operators defined in this context. Accordingly, in this paper we
propose to query video annotations using a variant of a temporal extension of ODMG's OQL
previously proposed by the authors [FDS99]. This is an important feature, since it entails that
most of the evaluation techniques developed in the context of temporal query languages may
be adapted to efficiently evaluate queries on videos.
Perhaps, the main originality of the proposed approach is that it properly captures the
interactions between the three addressed aspects of video modeling. In particular, annotations
may be independently attached to any level of video structuration, and video composition
operators are defined so as to preserve the structurations and annotations of the argument
videos.
s
The next four sections successively deal with structuration, annotation, querying and composition
of videos. Throughout these sections, the proposed data model and query language
are formally defined and illustrated through several examples. Next, in section 6, we describe
the current state of the prototype that we are developing to validate the proposal, and include
several implementation notes. Finally, a comparison with related works is included in section 7
and conclusions are drawn in section 8.
structuration
Video structuration is the process of grouping the frames of a video according to their semantical
correlations. For instance, a video can be structured into shots, scenes, and video sequences 1 .
The structure of a video is analogue to the table of contents of a text document. As such,
it can be used as a guide for browsing, as the entry point for building video abstracts, or as a
mean to retrieve the context of a particular piece of video.
There is a strong similarity between the structuration of a video and the structuration of
time in calendars. Accordingly, we propose a video structuration model based on the concept
of granularity. This concept has been extensively studied in several contexts such as temporal
reasoning in artificial intelligence, and temporal databases. The definition of granularity that
we adopt here is not completely novel, but rather generalizes the one developed in [WJS95].
It is important to note that in this work, the concept of granularity is merely used to model
structuration levels, and not as an absolute temporal metric system, as it is the case in many
other contexts. Indeed, when time is structured into "regular" granularities such as minutes
and hours, these granularities may then be used to express distances between time points.
2.1 Time-lines and granularities
The basic concept of the video data model that we consider is that of time-line. At an abstract
level, a time-line TL is a pair (D, ! of a finite set of time-marks D, and a binary
set defining a total linear order.
Time-lines model independent time-coordinate systems, with respect to which data and
meta-data may be temporally anchored. Each video has its own time-line, which captures the
temporal relations between its elementary components (i.e. its frames).
A granularity over a time-line TL is defined as a partition of sets: each
of these convex sets is then seen as an atomic granule and every time-mark of the time-line
is approximated by the granule which contains it. A granularity is intrinsically attached to a
1 The term "video sequence" as used here is not to be mistaken with the datatype "sequence" introduced in
section 3.1.
s
unique time-line. The function that maps a granularity into a time-line is subsequently denoted
TimeLine. Thus, the expression TimeLine(G) denotes the time-line that granularity G partitions.
A hierarchical structure is defined over the set of granularities of a time-line through the
definition of the following relation.
Definition 1 (Finer-than relation). A granularity G1 is finer-than another granularity G2
(noted G1 OE G2) if each granule of G2 may be associated to a set of
consecutive granules of G1. Formally, G1 OE G2 iff:

For any two granularities G1 and G2 such that G1 OE G2, two mapping functions are defined:
one for expanding a granule of G2 into a set of granules of G1 (noted ffl G2,G1 ), and the other
for approximating a granule of G1 by a granule of G2 (noted ff G1,G2 ), as shown in figure 1.
x
Approximation of x
Expansion of x
e
a (x)

Figure

1: Granule expansion and approximation
2.2 Using granularities to model video structuration
Any level of structuration of a video is naturally modeled by a granularity over its time-line.
Indeed, the set of shots of a video may be seen as a set of disjoint intervals of time-marks covering
the whole time-line of the video. Notice that it is also possible to view the set of frames as a
"degenerated" partitioning of a video time-line, in which each partition is composed of a single
time-mark. The advantage of this modeling is that the notion of frame is seen as a structuration
level of a video in the same way as shots or scenes. This allows to attach annotations to shots
or scenes in the same way as they are attached to frames, as detailed in the next section.
In the general case, the finer-than relation over the granularities defining the structuration
levels of a video is not necessarily a total order [WJS95]. In other words, it is possible to define
s
two non-comparable structuration levels over a single video. This feature is not supported by
most previous video models (e.g. [HMS95]).
The following ODMG interface shows how granularities can be used to define an ODMG
interface for videos that integrates the classical levels of video structuration (i.e. video se-
quences, scenes and shots). This interface may be specialized (through inheritance), so as to
handle situations where other structuration levels are needed. For instance, in the context of a
video about a tennis match, structuration levels such as point, game and set may be defined.
interface TimeLine; /* not detailed here */
interface Granularity f
bool finerThan(Granularity other);
interface Video f
attribute TimeLine VTL; /* standing for Video Time-Line */
attribute Granularity sequences; /* Granularity modeling video sequences */
attribute Granularity scenes; /* Granularity modeling scenes */
attribute Granularity shots; /* Granularity modeling shots */
attribute Granularity frames; /* Granularity corresponding to frames */
Other attributes described in section 3 */
For a given object V belonging to a class which implements the above interface, the following
constraints apply:
denotes the function which retrieves
the finest granularity of a time-line (this is the granularity whose granules are all
singletons). Such granularity is usually called the chronon of a time-line in the temporal
database literature [TCG
ffl V.shots OE V.scenes OE V.sequences
Notice that it is the responsibility of the application programs to ensure the above con-
straints, since ODMG does not support general-purpose integrity constraints.
3 Video annotation
Given the current state of image processing technology, it is not reasonable to dynamically
extract semantical information from a video during query evaluation over a video database. As
a result, in order to formulate content-based queries over videos, their semantical content must
be previously described as annotations.
s
These annotations are generally stored separately from the "raw" video data. This approach
is quite natural, since video annotations are normally only needed during video querying 2 , while
access to raw video data is only required during video playing. In addition, this approach allows
to share the "raw" video data among several "virtual" videos, without necessarily sharing all
the corresponding annotations.
Our approach to video annotation is based on a single parametric type, namely Sequence
(see 3.1). By instantiating this type with some adequate parameters, it is possible to model the
temporal relationships between the annotations attached to a video (see 3.2), as well as those
between the references to the raw video frames composing a virtual video (see 3.3).
3.1 Basic abstract datatypes
On the basis of the granularity model introduced in the previous section, the following ADTs
are introduced to model temporal values and sequences.
ffl Instant: An instant is as an approximation of a connected region of a time-line by a
granule. It is represented by a pair made up of a natural number (the position of the
denoted granule) and a granularity.
ffl Duration: a duration is a number of granules of a granularity. Durations are signed so
as to differentiate forward from backward motion in time. A duration is described by a
pair composed of an integer (the size) and a granularity.
ffl ISet: an ISet (standing for Instant Set) models a collection of instants with no assumption
on its representation. The Interval ADT is defined as a restriction of the type ISet which
includes all convex instant sets.
ffl Sequence: a sequence is a function from a set of instants observed at some common
granularity, to a set of values sharing a common structure. The domain of a sequence
is not necessarily an interval. The Sequence ADT is parameterized by the type of the
range of the sequence. In the sequel, we will use the notation Sequence!T? to denote
the instantiation of the parametric type Sequence with type T.
Notice that in order to integrate the sequence datatype into an object-oriented data model,
this latter should support parametric polymorphism. Unfortunately, this is not the case of
ODMG. In section 6, we will discuss how this limitation can be circumvented at the implementation
level.
Close captions are an exception, since they are annotations that must be displayed during video playing.
3.2 Using sequences to model annotations
One of our main objectives is to provide a video annotation model fulfilling the following
requirements: (1) the structure of the annotations is not constrained, and (2) annotations may
be independently attached to each level of structuration.
The first of these requirements is essential since video annotations are generally domain-
dependent. Indeed, in the context of a movie, annotations may deal with the characters or
actors appearing on it, while in a news TV program, they may deal with the events being
reported. In addition, as we will see later, videos may be obtained by composition of several
videos, whose annotations may have heterogeneous structures.
The second requirement on the other hand, increases the expressive power of the video data
model. Indeed, in most previous proposals (e.g. [OT93, GR94, ACC annotations
are only attached to the video frames 3 . This withholds the user from expressing properties which
are true of a scene, without being true at each frame in this scene. For instance, saying that in
a given scene two characters talk to each other, is something that is true at the granularity of
that scene, without being true of each frame in this scene.
To achieve the first requirement, we allow any object of a database to be used as a video
annotation. It is not until the definition of the database schema, that the database designer
may impose type restrictions on the annotations so as to model the specificities of a particular
application. Therefore, in some context, an annotation may have a simple textual structure,
while in another context it may be structured into sets of keywords, or other arbitrarily complex
structure or object. We have studied in a previous work [LM98], how such heterogeneous
annotations may be queried using generalized path expressions [CACS94].
Finally, to achieve the second requirement, we attach to each video, as many sequences of
annotations as there are levels of structuration defined over it, as depicted in figure 2.
3.3 Using sequences to share raw video data
Up to now, we have modeled what is traditionnally called the meta-data of a video, and have
omitted to discuss about the images and sound samples that appear during video playing. Since
this is generally the most bulky part of a video, any effort to compress or share it is extremely
important. Video compression is a subject that has been thouroughly studied and most of the
video formats (e.g. MPEG-2), are based on some compression technique. Sharing video data
on the other hand, has received much less attention. In the context of an object database, this
is relatively easy to achieve, since videos can be modeled as objects and object identifiers can
be used to refer to them.
3 In [ACC + 96, LGOS97] annotations are attached to intervals of frames, but the underlying semantics is that
the annotation is valid at each frame in this interval.
<subtitle: - Hi Tom
- Hi .
Perhaps.
Scenes
Shots
Video sequences
Frames
<actors: {Ed}> <actors: {Ed, Tom}> <actors: {Ed, Tom, Mike}> {Al, Hans}>
<actors:
sh1
<place
parking>
<place
<place
house>
<place
<place
sh2 sh3 sh7 sh8 sh9
<action: a
sh4 sh5 sh6

Figure

2: Sequences of annotations attached to a video
It is at this point that the distinction between raw videos and virtual appears. A raw video
is a low-level concept modeling an image dataflow without any structuration nor indexing
information (i.e. without meta-data). Virtual videos are then built from segments of raw
videos, and may have some meta-data attached to them. Virtual videos do not "copy" the data
contained in the raw videos, but rather reference them. Therefore, a given segment of a raw
video may be shared by several virtual videos. This issue will be illustrated in section 5, where
the creation and composition of virtual videos is discussed.
To model references to raw video data, we introduce the interface RVRef (standing for Raw
Video Reference). An object of a class implementing this interface is composed of an instance
of the RawVideo class (not described here), and a positive integer denoting the position of the
referenced frame inside this raw video.
interface
attribute RawVideo source;
attribute short frameNumber;
The following ODMG interface (which completes the one given in section 2) summarizes
the above discussion. This interface is not intended to be used "as is". Instead, the user
may specialize it to account for particular kinds of videos. For example, to model movies, an
interface inheriting from the above one may be introduced, adding some attributes such as the
title, director, casting, etc.
interface Video f /* Models virtual videos */
attribute TimeLine VTL;
attributes described in section 2 */
attribute Sequence!Object? sequencesAnnotations;
attribute Sequence!Object? scenesAnnotations;
attribute Sequence!Object? shotsAnnotations;
attribute Sequence!Object? framesAnnotations;
attribute Sequence!RVRef? rawDataRef;
For a given object V belonging to a class which implements the above interface, the following
constraints apply:
stands for the
granularity of the domain of sequence S.
ffl The domain of V.rawDataRef is an interval, i.e. discontinuities are not allowed between
the successive images of a video. Notice that this restriction is not imposed over the
sequences of annotations V.framesAnnotations, V.shotsAnnotations, etc. This means that
it is optional to attach an annotation to a given frame (or shot) of a video, while it
imperative to attach an image to each frame of a video.
4 VideOQL: a query language for video databases
In this section, we formally define an extension of ODMG's Object Query Language (OQL)
that integrates the datatypes defined in the previous sections as well as a set of operators over
them. We also illustrate through some significant examples, how this extension can be used to
formulate structure-based and content-based queries on videos.
The following notations are used throughout this section:
denotes the type of all functions with domain T1 and codomain T2.
ffl fTg denotes the type of sets of T.
stands for the type of tuples whose i th component is of type
n). Tuple components may be labeled using the notation hL1: T1, L2:
denotes a tuple value whose i th component is vi. If the tuple attributes
are labeled then the notation hL1: v1, L2: used instead.
4.1 Operators on temporal values
Constructors The instant constructor, noted P @ G, builds an instant from a natural number
(the position with respect to the origin) and a granularity G. The duration constructor is
defined similarly and noted #. There are two interval constructors: [I1.I2] which builds an
interval with lower bound I1 and upper bound I2, and [I j D] which yields an interval with lower
bound I and duration D.
Selectors Two elementary selectors are defined on durations, namely Granularity and Size,
such that Granularity(N # Similarly, two selectors are defined on
instants: Granularity and Position. The function Duration(IS) (IS being an ISet) yields a duration
whose size is equal to the number of instants in IS.
Conversions Conversion operators on instants are defined on the basis of the approximation
and expansion operators described in section 2.1. For instance, given two granularities G1
and G2 such that G1 OE G2, it is possible to expand an instant with granularity G2 into an
interval with granularity G1, or to approximate an instant with granularity G1 by an instant
with granularity G2. These conversions are performed by the following operators
expand: Instant, Granularity ! Interval
approx: Instant, Granularity ! Instant
4.2 Operators on sequences
The following functional specification introduces the selectors over the Sequence ADT.
domain of the sequence seen as a function */
Range: range of the sequence seen as a function */
value of S at I; precondition: I 2 Domain(S) */
Duration /*
A set of algebraic operators is defined on sequences. These operators are divided into
five groups: pointwise mapping, join, restriction, partitioning and splitting. The first three
correspond to the classical projection, join and selection operators of the relational algebra,
while the latter two are proper to sequences. In fact, partitioning and splitting are tightly
connected to two important characteristics of sequences: granularity and order.
4 In this specification, a granule is represented by its position among the other granules of its granularity.
s
The pointwise mapping operator map, applies a function to each element in the range of a
sequence while leaving the domain of the sequence intact. The join operator on the other side,
merges two sequences into a single one by combining synchronous values.
There are two restriction operators on sequences. The first one (noted during) restricts the
domain of a sequence to the instants lying in a given set of instants. The second one (noted
restricts a sequence to those instants at which its value satisfies a given predicate. Such
predicate is given as a boolean function whose parameter denotes a value of the sequence's
range. Syntactically, the operator when is coupled with map, in the same way as OQL's select
operator on collections is coupled with the where operator. The exact syntax of the constructs
of the language is discussed below.
The partitioning operator, namely partitioned by, allows to change the granularity at which
a sequence is observed. More precisely, S partitioned by G2, S being at granularity G1 (G1 OE
G2), makes a partition of S according to granularity G2. The result is a sequence, at granularity
G2, of sequences at granularity G1, such that the value of the main sequence at any instant I
(at granularity G2) is the restriction of S to the interval expand(I, G1). This is illustrated in
figure 3.
Assumptions:
<f2, a1>,
<f1001, a3>,
<f1002, a3>,
<f2552, a2>,
[<f1, a1>,
<f3, a1>,
[<s1, [<f1, a1>,
[<s2, [<f1001, a3>,
<f2, a1>,
<f3, a1>,
<f1002, a3>,
. <f2552, a2>]>,
<f2551, a2>,
S partitioned by scenes
frames finer than scenes
- .
Note:

Figure

3: Sequence partitioning operator. Instants at the granularity called frames (respectively
scenes) are denoted as f1, The condition frames OE scenes should hold.
To reason about successive values of sequences, four "splitting" operators are provided,
namely afterfirst, beforefirst, afterlast and beforelast. S as x afterfirst P(x) yields the tail of S
starting at the first instant at which the value of S satisfies predicate P, or the empty sequence
if such instant does not exist. S as x beforefirst P(x), on the other hand, restricts S to those
instants preceding the first instant at which the value of S satisfies P, or S if such instant does
not exist. For any sequence S and any predicate P, S is equal to the union of S as x beforefirst
P(x) with S as x afterfirst P(x) (which are disjoint). Similar remarks apply to afterlast and
beforelast.
s
Syntax: !query? ::= map !query? on !query? as !identifier?
Typing:
Semantics:
Syntax: !query? ::= !query? during !query?
Typing:
during
Semantics: during q 2
Syntax: !query? ::= map !query? on !query? as !identifier? when !query?.
Typing:
Semantics:
Typing:
Semantics:
Syntax: !query? ::= !query? partitioned by !query?
Typing:
Semantics: partitioned by q 2
during expand(I, granularity([[ q 1
Syntax: !query? ::= !query? as !identifier? afterfirst !query?
Typing:
afterfirst
Semantics: afterfirst q 2
Syntax: !query? ::= !query? as !identifier? beforefirst !query?
Typing:
beforefirst
Semantics: beforefirst q 2
Note: Operators beforelast and afterlast are defined symmetrically to afterfirst and beforefirst.

Figure

4: Syntax and semantics of VideOQL's algebraic operators on sequences
s

Figure

4 provides a complete formalization of the above operators. the formalization of each
language operator is made up of three parts:
ffl Syntax: in a BNF-like notation with terminal symbols typeset in boldface.
ffl Typing: a typing rule for the operator using the notation premise
implication
. The notation q::t
means that the query q has type t, while q[x::t']::t means that query q has type t assuming
that variable x has type t'.
ffl Semantics: the semantics of the operator in terms of a first-order calculus-like expression
defining the graph of the resulting sequence (which is a set of pairs hinstant, valuei) in
terms of that of the argument(s). The semantics of each operator is parametrized by a
valuation function which fixes the values of free symbols in the corresponding query. For
instance, denotes the result of evaluating q under valuation . Finally, the notation
[x / v] denotes the valuation equal to  except that it assigns value v to symbol x.
In addition, the following macros are introduced as a syntactical sugar; they combine up the
map and the partitioned by operators and introduce a having operator on partitioned histories.
map q1 on q2 partitioned by q3 j map q1 on (q2 partitioned by q3) as partition
map q1 on q2 as x when q3 partitioned by q4 j
map q1 on ((map x on q2 as x when q3) partitioned by q4) as partition
map q1 on q2 partitioned by q3 having q4 j
map q1 on ((q2 partitioned by q3) as partition when q4) as partition
map q1 on q2 as x when q3 partitioned by q4 having q5 j
map q1 on (((map x on q2 as x when q3) partitioned by q4) as partition when q5) as partition
Notice that in all these macro definitions, the variable partition is used in the map and having
clauses to refer to the sub-sequences generated by the partitioning phase. This convention is
analogue to that adopted in OQL's ``group by'' clause [CB97].
For further details on the language, the reader may refer to [FDS99], where we define a
temporal extension of OQL whose syntax and semantics are close to those of VideOQL, and
to [DFS98], where an operator similar to partitioned by is introduced.
Notice also that in this section, we do not consider any modification operator on variables
of type Sequence. This is because VideOQL, as well as OQL, is not intended to be a complete
data manipulation language (as does SQL), but just a data retrieval one.
4.3 Queries
To illustrate the ease of use and the expressive power of VideOQL, we consider a database
managing a collection of movies. Each movie is identified by its title. The frames of each movie
are annotated with the names of the actors appearing on them, while the scenes are annotated
s
with the location where they take place. The following extended ODL statements describe the
class Movie, which implements the Video interface described in section 3.2. Notice that the
attribute framesAnnotations "inherited" from this interface, is specialized to account for the
structure of the annotations managed in this context. A similar remark applies to attribute
scenesAnnotations.
class Movie : Video (extent TheMovies, key title) f
attribute string title;
attribute sequence!Location? scenesAnnotations;
attribute sequence!Set!string?? framesAnnotations;
The first two queries that we consider, illustrate the restriction operators on sequences. In
the first one, a sequence of annotations attached to the frames of a video is restricted to a
given interval. The annotations appearing in this portion of the sequence are then extracted
and furtherly processed using standard OQL operators. In the second query, a sequence of
annotations is restricted based on a condition on the values that it takes, and the result is
aggregated using the Duration selector on sequences (see section 4.2).
Restriction (based on the domain)
Retrieve the names of actors that are present at least once during the first 20 seconds of the
movie "Hopes" (assuming a constant presentation rate of
flatten(select anActorSet
from TheMovies as F,
range(F.framesAnnotations during [ 0 @ F.frames j (20 * 30) # F.frames ]) as anActorSet
Operators @, # and j were introduced in section 4.1 */
Restriction (based on the range) and sequence aggregation
In which movies, is John present during more that 15 minutes (assuming the same presentation
rate as above).
select Fmax from TheMovies as FMax
where duration(FMax.framesAnnotations as anActorSet when "John" in anActorSet)
Notice that these two queries, we assumed a constant presentation rate when converting
a number of seconds into a number of frames. However, virtual videos may involve several
raw videos possibly recorded (and therefore presented) under different frame rates. In these
situations, the conversion function between "seconds" and "frames" becomes far more complex.
To our knowledge, this problem has not been addressed by any of the existing video data mod-
els. Indeed, the models which offer conversion functions between metric temporal values (e.g.
s
durations expressed in terms of seconds) and frame numbers, assume a constant presentation
rate (see for instance [DC98]). We believe that this is an interesting perspective to our work.
Perhaps one of the most important characteristics of videos is their sequenced structure.
Therefore, queries dealing with this structure are expected to be frequent. To some extent,
these queries may be expressed using the splitting operators on sequences (see section 4.2) as
in the following expression.
splitting sequences
In which movies does John appear for the first time before Tom does so.
select F from TheMovies as F
where exists actorSet2 in range(F.framesAnnotations as actorSet1 beforefirst "Tom" in actorSet1) :
"John" in actorSet2
/* i.e. there is an actor set containing "John", within the range of the original sequence restricted to
the instants before the first time when "Tom" appears. */
However, these splitting operators (even combined with the other operators of the model)
are not sufficient to express all queries involving succession. In particular, they cannot express
the query "For each actor appearing in a given movie, how many times does he/she appears
in this movie", where "an actor appears" means that she/he is present in one frame, without
being present in the previous one. The same is true of queries involving maximal intervals
during which a fact is uninterruptedly true, e.g. "Who is present uninterruptedly in Freedom
during a longest interval of time than Tom does".
Two approaches are possible to cope with these limitations. The first is to introduce new
operators addressing these kinds of queries, and to study the expressive power of the resulting
language. The alternative is to define a selector on the Sequence ADT which retrieves an
interval-based representation of a sequence, i.e. a collection of pairs h Interval, Object i. For
instance, given the sequence whose graph is: fh1, v1i, h2, v1i, h4, v1i, h5, v2i, h6, v2i, h7, v2i,
h8, v3i, h9, v1i, h10, v1i g , its interval-based representation is: f h[1.2], v1i, h[4.4], v1i,
h[5.7], v2i, h[8.8], v3i, h[9.10], v1i g. Once a sequence represented in this form, standard
OQL operators on collections combined with an adequate set of operators on intervals, could
be used to express the above two queries. The expressive power of the language regarding
sequences, would then exactly match the expressive power of OQL for handling collections of
intervals. Exploring and comparing the above alternatives is an interesting perspective to the
work developed in this paper.
Since in our model, annotations may be independently attached to each level of video
structuration, it is necessary to provide a mechanism for switching between these levels. The
partitioned by operator provides this mechanism in our OQL extension.
sequence partitioning
Retrieve the scenes of "Freedom" in which John is in at least half of the frames of the scene.
s
select domain(map partition
on F.framesAnnotations
partitioned by F.scenes
having duration(partition as anActorSet when "John" in anActorSet)
from TheMovies as F where F.title = "Freedom"
In combination with the join operator, the sequence partitioning operator allows to answer
queries which simultaneously involve annotations at the granularity of the scene and at the
granularity of the frame, as in : "Retrieve those scenes in film Freedom, which take place in
Paris, and in which John is present in at least half of the frames of the scene.
5 Video composition
5.1 Building elementary virtual videos
The duality between raw and virtual videos introduced in section 3.3 enforces a separation
between the data related to the images composing a video (which are encapsulated into raw
videos) and its meta-data (i.e. its structuration and annotations). The former is shared among
several virtual videos, thereby avoiding its expensive duplication, while the latter is mainly
duplicated, so that the user can edit it depending on a particular context.
A question that remains to be answered is: how virtual videos are created? Actually,
this is performed in two steps. First, "elementary" virtual videos are obtained by extracting
"segments" of raw videos. These elementary virtual videos are then combined into complex
ones through the set of algebraic composition operators presented below.
The creation of elementary virtual videos is conducted through a method extractSegment,
defined over the RawVideo interface. This method takes as parameter two integers, denoting the
begining and the end of the extracted segment. The result is a virtual video (i.e. an instance
of the Video class), whose attributes are all undefined (i.e. equal to nil), except for the VTL
and the rawDataRef ones, which respectively contain a time-line of the size of the extracted
segment, and a sequence of references to the raw video. This newly created virtual video may
then structured and annotated using some creation and update operators on granularities and
sequences that we do not describe in this paper.
5.2 Virtual video composition operators
Five algebraic operators are defined on videos: extraction, concatenation, intersection, union
and difference. Operators similar to these ones have been previously proposed in e.g. [WDG95,
s
HMS95, LM98]. However, none of these proposals defines them in such a way as to preserve
the structuration of the argument videos.
Extraction. This operator takes as parameters a virtual video V and an instant set IS, defined
at lowest granularity of V (i.e. V.frames). It creates a new video by restricting V to the instants
in IS. As the other operators of the algebra, the structuration and annotations of the operand
is preserved in the result, as shown in figure 5.
. scenes
shots
frames
scenes
shots
frames
Extract(V, {f2,f3,f4,f8,f9})
a f2 f3 f4 f5 f6 f7 f8 f9
a
a b c c a b
a
a
b a b
A

Figure

5: The video extraction operator. Characters a, b and c denote annotations attached
to the frames, while A, B and C are annotations attached to the scenes.
The derivation of the granularities of the resulting video is essentially carried out by the
operator Restrict on granularities defined in appendix A. Intuitively, Restrict(G, IS) derives a
new granularity by restricting granularity G to the granules referenced in IS.
The derivation of the annotations, on the other hand, is performed in two steps. First each
of the sequences of annotations of the argument video are restricted through the operator during
on sequences. Then, the resulting sequences are transformed into equivalent sequences over the
new time-line, using the operator Compact defined in appendix A. Intuitively, this operator
maps a sequence with a non-convex domain, into one with a convex domain. For example,
Compact(fh3, v1i, h5, v2i, h6, v2i, h9,
The overall definition of the operator is given below.
a time-line is represented as an interval of integers */
.framesAnnotations during IS)
.shotsAnnotations during expand(IS, V
/* see section 4.1 for the definition of "expand" */
.scenesAnnotations during expand(IS, V
Concatenation \Phi V . This operator takes two videos as parameters. The resulting video is
composed of all frames belonging to the first video, followed by all frames in the second one.
The definition of this operator involves two auxiliary operators: Translate and Shift, both
described in appendix A.
The operator Translate on granularities, corresponds to a translation of the origin of a time-
line. Intuitively, it shifts the time-marks contained in the granules of a granularity, by the
number given as parameter. E.g.
g.
The operator Shift on sequences, forwardly "shifts" the domain of a sequence by the number
of granules given as a parameter. For instance,
Shift(fh3, v1i, h5, v2i, h6, v2i, h9, v1ig,
the remaining granularities are defined in a similar way */
The remaining sequences of annotations are obtained similarly */
Intersection. This operation creates a new video where only common footage of both videos
is captured.
.rawData as x when x in range(V 2 .rawData)) in
Difference. This operation creates a new video which is composed of the frames of the first
operand without the common frames of the second operand.
.frames as x when not (x in range(V 2 .frames))) in
s
Union This operation has the same features as the concatenation one, but common footage
is not repeated. Formally:

Figure

6 illustrates some of the above operators. This figure puts forward the raw video
data sharing resulting from virtual video composition.

Figure

Virtual video composition and raw video data sharing: RV1 and RV2 denote raw
videos, while VV1 through VV4 denote virtual videos.
5.3 Video composition and querying
Embedded into the query language, the composition operators allow to build new videos by
retrieving and combining segments of existing ones. Typically, the retrieval phase of this process
involves a "select/from/where" query expression (which returns a collection of videos). To
combine all the videos of the resulting collection into a single one, it is necessary to extend the
composition operators so as to apply to lists of videos. The following operator generalizes the
binary \Phi V operator to deal with lists of videos.
Operators IntersectAll and UnionAll are defined similarly.
Using these operators, most of the queries presented in section 4.3 can the be easily rewritten
so as to generate a new video from the videos or video segments that they retrieve.
Create a new video by concatenating all the movies where John appears for the first time before
Tom does so.
s
select F from TheFilms as F
where exists actorSet2 in range(F.framesAnnotations as actorSet1 beforefirst "Tom" in actorSet1) :
"John" in actorSet2
order by F.title)
6 Implementation
The video model presented has been implemented as a prototype on top of the O 2 DBMS. In
this section, we present the overall architecture of the prototype, and detail its components.
6.1 Overall architecture
The overall architecture of the prototype is shown in figure 7. It is composed of seven mod-
ules. Four of them, namely the schema definition language preprocessor, the query language
preprocessor, the video editing user interface and the video player, operate as front-ends to the
DBMS. The other three modules (the schema manager, the video meta-data manager and the
raw video repository) directly operate within the DBMS.
query language
preprocessor
extended
extended schema
definition language
preprocessor
Video player
Video meta-data manager
Sequence interface Video interface
Schema manager
DBMS
editing
user interface
MPEG files
repository
Other related interfaces
ODMG-compliant

Figure

7: Overall prototype architecture
The schema definition and the query languages preprocessors are adapted from those developed
in the context of the Tempos temporal database system [FDS99]. In the current state
of the implementation, we have not yet considered any optimization issue: the query language
preprocessor simply translates queries formulated in VideOQL, into OQL queries containing
invocations to the methods implementing the operators of the Sequence ADT. However, in a
future work, we plan to explore how temporal query evaluation techniques could be adapted to
efficiently evaluate queries written in VideOQL.
s
The video editing user interface and the video player (which we detail in section 6.2), are
also adapted from previous work done by the authors in the context of the VSTORM video
database model [LM98]. Together, these two modules provide an interactive environment for
editing, browsing and playing videos stored in the database.
The screen shot in figure 8 illustrates the edition of a video sequence using the video editing
interface. The box entitled "current level" lists all the existing scenes of the video sequence.
When a scene is selected, all the data attached to it are displayed in the rest of the canvas, so
that the user may browse or edit them. A new scene can be added by clicking on the "NEW"
button. The shots composing the new scene are entered through the "Control panel" or directly
by giving the cardinal numbers of the first and last shots of the scene. The "Browse" button is
used to link objects with this scene (i.e. to annotate the scene). The "KEYFRAME" button
allows to select a representative frame of the scene (i.e. a key-frame). The set of key-frames of a
given structuration level may subsequently be viewed by selecting the "keyframes only" button.
This functionality is extremely useful for video browsing. Finally, the "relevance factor" entry
is intended to measure the current scene's relevance with respect to all other scenes in the
current video sequence. This factor is subsequently used for summary extraction as discussed
in [LM99].

Figure

8: Screen shot from the video editing user interface
The schema manager has two functionalities. First, it acts as a mediator between the
external preprocessors and the DBMS catalog. This mediation ensures some independence
between the preprocessors' design and the underlying DBMS. Indeed, the ODMG standard
does not define an interface to update the DBMS catalog, although it defines an interface to
access it (which, by the way, is currently not implemented by the object DBMS vendors).
Second, this module keeps track of the instantiations of the parametric class Sequence used
s
within a given database. This is necessary to simulate parametric polymorphism on top of the
ODMG object model as discussed later in section 6.3.
The video meta-data manager is a library of classes providing an interface to the data related
to video structuration, annotation, and composition, stored within the DBMS. These classes
implement the ADT (or interfaces) described throughout the paper.
Finally, the raw video repository contains the compressed files containing the images and
sound samples of each physical video. In the current implementation, these data are partially
managed outside the DBMS due to some limitations of the O 2 DBMS.
6.2 Implementation notes related to the video player
In the current state of the prototype, the video player module is implemented as an extended
version of an MPEG player developed at the University of California 5 . The features that we
have integrated into the original MPEG player concern three main aspects:
ffl The original video player was designed to read its input from a single physical file, while
virtual videos may stem from several raw videos stored in separate files. To avoid generating
the entire MPEG data corresponding to a virtual video, and dumping it into
a physical file before starting its presentation, we modified the original player so as to
accept reading data from a dynamically generated file (i.e. a pipe). Several bufferization
problems were tackled at this point.
ffl A virtual video may stem from several physical videos having different window sizes. The
player was therefore modified so as to dynamically resize the video presentation window
in such situations. An alternative approach that we considered, is to fix a window size for
the whole virtual video presentation, and to dynamically rescale each involved physical
video so as to fit on it. However, we did not implemented this latter solution since it
involves complex modifications into the video player.
ffl Similarly, several physical videos involved in a single virtual video may have been recorded
with different frame rates. The original video player was therefore modified so as to accept
changing the frame displaying rate on the fly. Otherwise, the user would perceive some
portions of the virtual video as going faster or slower than the others.
In the future, we plan to decompose the video player into two subcomponents: one which
video data, and another that displays it under some presentation parameters
(e.g. window size and speed). In this way, it will be quite straightforward to consider other
compression formats than MPEG (e.g. M-JPEG, AVI and H.261), and even to play virtual
videos composed of physical videos stored under different formats.
5 Downloadable at ftp://mm-ftp.cs.berkeley.edu/pub/multimedia/mpeg. This video player only plays images.
6.3 Implementation notes related to the Sequence ADT
Perhaps, the major problems that we faced during the design of the prototype, were those
related to the lack of parametric classes in the O 2 model (which is true of the ODMG object
model as well). Indeed, the Sequence ADT could be naturally mapped into a parametric class.
A first solution that we envisaged, is to generate a class for each kind of sequence involved
in an application. In our example database, this implies generating a class for sequences of
Location, another for sequences of Set!string?, etc. We believe that in realistic situations,
these would rapidly lead to an undesirable proliferation of classes. In addition, some operators,
such as the sequence joins, cannot be satisfactorily implemented using this approach, since the
type of the resulting sequence intrinsically depends on that of the argument sequences.
Instead, we decided to partially simulate parametric classes by exploiting the preprocessors
included in the architecture. In this approach, a single non-parametric class Sequence,
corresponding to sequences whose values are of type Object (the top of the ODMG's class hi-
erarchy), is first implemented. Then, during schema definition, each sequence-valued attribute
is declared as being of type Sequence by the data definition languages preprocessor, while its
exact type specification is stored in the schema manager. Since the schema manager is accessed
by the VideOQL preprocessor, this latter knows the exact type of the sequences involved in
a query. With this knowledge, the VideOQL preprocessor adds explicit downcastings in the
translated query expression, whenever a value of a sequence is extracted. In this way, the user
of VideOQL manipulates sequences as if they were parametrically typed.
The above solution has several drawbacks. First, adding explicit downcastings in the translated
queries introduces a burden during query evaluation, since the OQL interpreter performs
a dynamic type checking whenever an object is downcasted. Second and foremost, the above
solution does not take into account that the database objects are not only accessible through the
query language, but also, through any of the programming language bindings (e.g. the C++
and Java bindings defined in the ODMG standard). An outcome of this limitation is that,
in the current implementation of the prototype, the application programmer must introduce
downcastings and explicit dynamic type checkings when manipulating sequences.
7 Related works
There is a wealth of works dealing with semi-structured formats for representing semantical
video contents (i.e. annotations). The results of these works are currently being exploited
by ongoing standardization efforts, such as MPEG-7 [ISO98] and the Dublin core metadata
proposal [WKLW98]. In both of these approaches, annotations are represented as "segment
descriptors", i.e. hierarchically structured entities attached to a particular segment of a docu-
sment, or possibly to an entire document. MPEG-7 is intended to be flexible, in the sense that
user-defined annotation types are allowed in addition to the ones provided by the standard.
Our proposal is complementary to the above ones, since it is not intended to define a
low-level format for video storage, but rather a high-level data model for browsing, editing,
composing and querying videos using the functionalities of an object DBMS. The choice of
an object-oriented approach has several important advantages. Indeed, inheritance can be
exploited to provide a flexible schema annotation, while the concept of object identity allows
to easily share video segments among several "virtual videos".
The idea of using DBMS functionalities to store, browse, and query video contents is not
novel; it has been applied in many prototype systems and data model proposals (see [EJA
for a survey). The main innovation of our approach, lies on the orthogonality with which
the different aspects of video modeling are tackled. For instance, in our proposal annotations
may be independently attached to each level of the video structuration, whereas in most of
the existing video data models (e.g. AVIS [ACC + 96] and CVOT [LGOS97]), annotations may
only be attached to the frames. Moreover, in most existing approaches, the structure of the
annotations is restricted (generally to full-text keywords), while in our proposal, any database
object may be used to annotate any video segment.
[HMS95] is perhaps one of the closest works to ours. This paper describes a framework for
modeling video and audio through the notion of media stream. Annotations are attached to
intervals over these streams, and temporal queries are formulated by using comparison operators
on the lower and upper bounds of these intervals. This work does not address the issue of
defining high-level temporal query operators. In addition, the proposed query language uses an
ad hoc syntax, and is not integrated into a general-purpose query language. This remark also
applies to other related proposals such as VideoSQL [OT93] and VIQS [HS95]. In contrast, the
query language that we propose is a fully compliant extension of OQL, therefore allowing to
formulate both video and "conventional" queries in the same framework.
The idea of using temporal database concepts to model video data has been explored in
[LGOS97]. In this work, the authors suggest to handle videos using histories as defined in
the TIGUKAT object model [GO93]. Queries on videos are then expressed using high-level
operators on histories. Unfortunately, some important features of video annotations are not
taken into account. For instance, it is not possible to attach different kinds of annotations
to different levels of video structuration as discussed above. Furthermore, the authors assume
that video annotations are located with respect to a global time-line (i.e. each annotation
is conceptually attached to an anchored date such as "14/8/1999 at 5:00 a.m."), so that the
modeling issues arising from the unanchored nature of time in videos are skirted.
In some respect, the work reported here is close to that of [SLR96], which proposes an
ADT-driven model for sequences and an associated query language. This latter work focuses
on discretely-varying data such as time-series, and the authors do not discuss how it may be
extended to deal with stepwisely varying data such as video annotations.
Most of the video composition operators that we considered in this paper are inspired from
those studied in [WDG95]. These operators also appear, with slightly different semantics, in
other related proposals such as [OT93] and [HMS95]. However, none of these works discusses
how the logical structuration of the composed videos is reflected in the resulting one, nor how
these composition operators can be integrated into a query language.
Finally, other related works include the numerous data model proposals for multimedia
presentations (e.g. [Adi96]). These works however, are not directly relevant to our proposal,
since they do not attempt to model the internal contents of videos, but rather to provide
support for building interactive presentations by composition of multimedia documents.
8 Conclusion
We have detailedly presented a data model providing high-level support for storing, browsing,
querying and composing videos on top of an object-oriented DBMS.
Through a detailed analysis of related works, we have shown that the proposed data model
includes several important novelties that ensure an increased user-friendliness, flexibility and
expressive power. In addition, the soundness of the data model and its associated query language
have been validated through a complete formalization and a prototype implementation
on top of an industrial object-oriented DBMS.
An important feature of our proposal is that it is based on concepts stemming from Temporal
This leads us to believe that many of the techniques
developed in this latter setting may be adapted to design an efficient and scalable implementation
of our model. Validating this claim is one of the main perspectives to the work reported
in this paper.
There are several other research directions that we would like to explore in the future:
Summary extraction. In section 6.1, we mentioned the possibility of annotating a
video segment with a measure of its relevance with respect to other video segments (i.e. a
relevance factor). A practical application of this kind of annotations may be to extract a
"condensed" version of a video fitting some given duration constraints. We have started
to examine this issue in [LM99].
ffl Database-driven collaborative video edition, i.e. studying how the distribution,
concurrency, and security facilities provided by current DBMS may be exploited to support
collaborative edition of structured video documents.
For a long time, videos have been managed as unstructured entities. Recent works, such as
s
one reported in this paper, show that accurately and formally modeling this media significantly
improves the user-friendliness and the expressive power of the tools used to handle it. This fact
demonstrates that it is not because a media is complex that it should be modeled fuzzyly. On
the contrary, it is in such situations that the structuration efforts are of greater concern.



--R

The Advanced Video Information System: data structures and query processing.
From structured documents to novel query facilities.
The Object Database Standard: ODMG 2.0.

A unified data model for representing multimedia
Handling temporal grouping and pattern-matching queries in a temporal object model
Video Database Systems: Issues
A representation independent temporal extension of ODMG's Object Query Language.
Temporal extensions to a uniform behavioral object model.
A data model for audio-video data
A temporal foundation of video databases.
Querying video libraries.
International Standards Organization - Coding of moving pictures and audio working group (ISO/IEC JTC1/SC29/WG11)
Modeling video temporal relationships in an object database management system.
Querying virtual videos with path and temporal expres- sions
Int'egration de donn'ees vid'eo dans un SGBD 'a objets. L'Objet
The Definition of Standard ML - Revised
implementation of a video-object database system
The design and implementation of a sequence database system.
Temporal Databases.
Composition and search with a video algebra.
Temporal modules
Dublin core metadata for resource dis- covery
--TR

--CTR
Marlon Dumas , Marie-Christine Fauvet , Pierre-Claude Scholl, TEMPOS: A Platform for Developing Temporal Applications on Top of Object DBMS, IEEE Transactions on Knowledge and Data Engineering, v.16 n.3, p.354-374, March 2004
temporal databases;object-oriented databases;video databases;ODMG