Transcript v 1

OVID: Design and Implementation
of Video-Object Database System
E. Oomoto and K. Tanaka
IEEE Transactions on Knolwedge and Data Engineering, 5(4),
August 1993.
Modified from a presentation by Fahd Al-Qaddaa
Outline
Video-Object Data Model






Introduction
Motivating Problems
Basic Ideas
Video Object Data Model
OVID: A Video-Object Database System
2
Introduction


OO concept is considered suitable for
describing the structure and semantic of
multimedia data
Major features provided by OODB systems:




Representation and management of complex type
Handling object identity
Encapsulation of data and procedures
Inheritance of attribute structure and methods
based on class hierarchy
3
Introduction


Is the modeling power offered by OODB
features enough for MM data, especially
video?
New data modeling for video database
management is needed because



Video itself is raw data and independent from the
content and the database structure
Meaningful scenes in video are identified and
described incrementally
Meaningful scenes may be overlapped or included
by others and may share some descriptional data.
4
Introduction

The authors introduced a new data model
called Video Object Data Model




They introduce video objects
The model is schemaless
The inheritance is based on interval inclusion
relationships
A collection of composition operations for video
objects are also provided
5
Motivating Problems

Difficulties in defining attributes:

To describe a video in conventional OODBMS’s




We should decide what basic objects are
Each frame (still image) could be a single object
However, semantically a scene is a sequence of frames
Objects could be defined as semantically
meaningful sequences of frame (Can be done
using OODBMS’s)

Each object is defined by the tuple: (starting frame#,
ending frame#, and other attributes to describe the
scene)
6
Motivating Problems

The attributes are difficult to be defined in
advance:


Different catalogers/taggers may give the same scene
different descriptions
The whole content of a video is difficult to describe as a
whole.


It should be done incrementally
A scene may contain another scene as its subinterval,
so descriptional data may be shared among scenes
based on time interval inclusion relationship.
7
Motivating Problems

Difficulties in querying

In a conventional DBMS query,



a database schema (tables, or class hierarchy) must be
known
Users must know the attribute structures of class
hierarchy in order to retrieve desired objects
When each object has a different attribute
structure, the following problem appears:


Users should inspect each object to know its attributes
When there is no schema, users must describe all
definitions of attributes and their values
8
Motivating Problems

Treatment of composed objects



Video data stored may be used for several
editorial works
Video data are often cut and/or concatenated for
multimedia presentation
In order to do this, the system should allow:


Retrieving Video data and composing the result into a
new video objects
Different editorial operations
9
Basic Ideas



Consider any portion of a video frame
sequence as an independent entity
A video objects corresponds to a certain set
of video frame sequence
An object has its own attributes and their
values to represent the content (meaning) of
the corresponding video scene
10
Basic Ideas

The features of the video object model:

Schemaless description of database


It does not assume a specific database schema such as
class hierarchy, so users can specify any attribute
structure for video object
For example, broadcast stations have many varieties of
video libraries such as news, movies, documentaries,
and so on


It is very difficult to offer common attribute structure for all
of them
Users may have different viewpoint to describe and/or
retrieve video scenes
11
Basic Ideas

Schemaless description …




It is difficult to decide rigidly the attribute structures
They should be extensible freely and incrementally
As new object are defined, new attributes may be needed
Interval Inclusion inheritance


Descriptional data can be inherited to other video objects
For example


Consider a night scene A and another object B is defined over
some portion of A. B is also a night scene.
If A has an attribute situation with value night, then B
must have the same attribute and value by interval inclusion
inheritance
12
Basic Ideas

Composition of video objects based on is-a
hierarchy

For example, in broadcast stations:




In order to do this, new operations is defined




video scene are edited from source video
They are chopped in order to remove redundant scenes
They are concatenated with each other to make TV programs
Interval projection
Merge
Overlap
These operations produce new video objects and based
on is-a hierarchy inherit attributes and their values to the
new one.
13
Video Object Data Model
Video Object

A video-object is a descriptional data of
meaningful scene (motion picture)
It consists of:






Its object identifier
An interval
A collection of attribute/value pairs
Each video object corresponds to a video-frame
sequence
14
Video Object Data Model

Video Object …

An interval is represented by a pair of



Starting frame number
Ending frame number
Assume the following mutually disjoint sets




D: a set of atomic values (numbers, strings, symbols Τ
and  )
ID: a set of object identifiers
I: a set of intervals
A: a set of attribute names
15
Video Object Data Model

Video Object …

Definition. A video-object is a triple (oid,I,v),
where:



oid is an object identifier and oid  ID
I is a finite subset of I
v is an n-tupe [a1 : v1, ….., an : vn], where each ai (1  i 
n) is an attribute name in A and vi is a value defined in
the following manner:




Each element x  D is a value
Each interval i  I is a vlaue
For v1, … , vn (0  n), {v1, … , vn} is a value called a set
value
Each video-object is also a value
16
Video Object Data Model

Video Object …
17
Video Object Data Model

Generalization Hierarchy for Values and
Objects

A generalization (is-a) hierarchy for atomic values
is assumed to be G = (A, , Τ, ), where:





A is a set of atomic values
 is an is-a relationship among values
Τ denotes unknown
 denotes undefined
The binary relation  denotes more informative
18
Video Object Data Model

Generalization Hierarchy …


This is-a relationship can be extended to general
values and also to video-objects
Suppose we have two video-objects o1 = (oid1, I1,
v1) and o2 = (oid2, I2, v2)



If v1 and v2 are set-type values, then v1 is-a v2 if for
each element y in v2, there exists an element x in v1
such that x is-a y
If v1 and v2 are tuple-type values, then v1 is-a v2 if v1.a
is-a v2.a for each attribute a in v2
For video object o1 and o2 if v1 is-a v2 then o1 is-a o2
19
Video Object Data Model

Generalization Hierarchy …

Definition. Least Upper Bound of Values

For two values v1 and v2, v = v1  v2 is the least upper
bound of v1 and v2, if the following conditions hold:




v1 is-a v,
v2 is-a v , and
There does not exists v’ such that v  v’, v’ is-a v, v1 is-a v’,
and v2 is-a v’
v1  v2 represents the maximum information that is
common to both of values v1 and v2
20
Video Object Data Model

Generalization Hierarchy …

Definition. Greatest Lower Bound of Values

For two values v1 and v2, v = v1  v2 is the greatest lower
bound of v1 and v2, if the following conditions hold:




v is-a v1,
v is-a v2,
There does not exists v’ such that v  v’, v is-a v’, v’ is-a v1,
and v’ is-a v2
v1  v2 represents the minimum information that
contains both of values v1 and v2
21
Video Object Data Model

Inheritance Based on Interval Inclusion
Relationship

For a given two intervals I1 and I2, the inclusion
relationship between them is defined as:


For each i  I1, there exists i’  I2, such that i  i’, then I1
is said to be included by the set interval I2, denoted by
I1 I2
Consider the two objects o1 = (oid1, I1, v1) and o2 =
(oid2, I2, v2), such that I1 I2 holds, then some
attribute/value pairs of v2 are inherited by the
object o1
22
Video Object Data Model

Inheritance …

Definition. Evaluation of Interval Inclusion
Inheritance by a Single Object


Suppose we have video-objects o1 = (oid1, I1, v1) and o2
= (oid2, I2, v2), such that I1 I2 holds, and a set A of
inheritable attributes
The result of applying the interval inclusion inheritance is
called evaluation
23
Video Object Data Model

Inheritance …

The evaluation of o1 by o2 and A, denoted by eval(o1, o2,
A) is a video object o’ = (oid1, I1, v’1) such that




attr(v’) = attr(v1)  (attr(v2)  A)
v’1.a = v1.a , if a is in attr(v1), and
v’1.a = v2.a , if a is in (attr(v2)  A), but not in attr(v1)
Note that identifier of o1 and o’ are the same, which
means the evaluation is not physically stored in the
database and is calculated dynamically
24
Video Object Data Model

Inheritance …

Definition. Evaluation of Interval Inclusion Inheritance by a
Multiple Objects


Suppose we have video-objects o1 = (oid1, I1, v1). Let O = {o21,…,
o2m} be the set of all video-objects in the database, such that I1
I2 holds for each o2i = (oid2i, I2i, v2i)
The evaluation of o1 by O – {o1}and a set A of inheritable
attributes, denoted by eval(o1, O, A), is a video-object o’1 = (oid1,
I1, v’1) such that:




attr(v’1) = attr(v1)  (attr(v21)  A) …  (attr(v2m)  A)
v’1.a = v1.a , if a is in attr(v1),
For each a in A, let Va = {v’2i.a | a  attr(v2i), a  attr(v1), and 1 i 
m}
For each nonempty set Va , v’1.a = glb(Va ), where glb(Va ) denotes
the greatest lower bound of all elements in Va
25
Video Object Data Model

Composition Operations for Video-Objects

Interval Projection Operation

Definition. Interval Projection Operation


Let o = (oid, I, v), and I’ I holds, and let A be a set of
inheritable attributes. The interval projection on o onto I’ is
a video-object o’ = (oid’, I’, v’) such that oid’ is a new
identifier, and v’ satisfies the following:
 attr(v’) = attr(v)  A, and
 v’.a = v.a for each attribute a in attr(v’)
This operation is useful when defining a new videoobject for a certain portion of an already existing one
26
Video Object Data Model

Composition Operations …

Merge and Overlap of Interval Sets

Definition. Merge and Overlap. For two intervals I1 and
I2 the merge and overlap if I1 and I2, denoted by I1 I2
and I1 I2, respectively, are defined as:

I1



I2 is the minimal set of intervals such that:
For each interval i in I1 there exists an interval i’ in I1 I2
such that i’  i
For each interval i in I2 there exists an interval i’ in I1 I2
such that i’  i
For every interval i1 and i2 in I1 I2 such that i1  i2, i1 
i2 and i2  i1
27
Video Object Data Model

Composition Operations …



I1 I2 is the maximal subset of {i1  i2 | i1  I1 and i2  I2
} such that i’1  i’2 and i’2  i’1 for arbitrary intervals i’1
and i’2 in I1 I2
The merge operation creates a new video-objects
o form existing objects o1 and o2 such that some
descriptional data common to both is inherited by
o
The overlap extracts the scene described by both
of two existing video objects as new video-objet.
28
Video Object Data Model

Composition Operations …

Merge of Video-objects

The merge of two objects o1 = (oid1, I1, v1) and o2 =
(oid2, I2, v2) denoted by o1 o2, is the video object o =
(oid, I1 I2, v) such that v = [a1 : v1, … ai : vi ..., an : vn]
where each ai (1  i n) is in attr(v1)  attr(v2), and for
each ai:


If both o1.ai and o2.ai are values, then vi = o1.ai  o2.ai
If both o1.ai and o2.ai are video-objects, then vi = o1.ai
o2.ai
29
Video Object Data Model

Composition Operations …

Overlap of Video-objects

For two video objects o1 = (oid1, I1, v1) and o2 = (oid2, I2,
v2) such that I1 I2 is nonempty, the overlap of o1 and o2,
denoted by o1 o2, in a new video object o = (oid, I1
I2, v) such that oid is a new identifier and v = [a1 : v1, …
ai : vi ..., an : vn] where



Each ai is in attr(v1)  attr(v2),
If both v1.ai and v2.ai are values, then v.ai = v1.ai  v2.ai
If both v1.ai and v2.ai are video-objects, then vi = v1.ai
v2.ai
30
OVID


OVID is a video-object database system which
developed based on the video object data model
The features of OVID:

Video Object as Central Units:


The video-objects are the central units of OVID system.
Each video-object consists of:




The oid of the video-object
a set of pairs of starting video frame# and an ending frame# of the
video scene
a set of attribute/value pairs which describe the content of the
corresponding video frame sequence
Basic methods such as Play, Inspect, and Disaggregate
operations.
31
OVID

Features of OVID …

Dynamic and Incremental Object Identification
and Definition:


Users can identify a meaningful scene at any time and
define this scene with its descriptional data as a videoobject
Users can add necessary attributes as well as use
attributes of predefined video-objects
32
OVID

Features of OVID …

Video Object Composition:



OVID allows definition of a video-object which
corresponds to more than one consecutive sequence of
video frames.
This operation corresponds to the merge operation
described.
It also supports creation of a video-object by applying
the overlap operation to predefined video-objects.
33
OVID

Features of OVID …

Browsing by Video Object Disaggregation:





In order to browse a large video-object, OVID provides a
decomposition of a video-object into smaller videoobjects.
This decomposition corresponds to the interval
projection operation described.
In OVID, this operation is called Disaggregation.
Disaggregation can be repeatedly applied.
This operation is useful to find a necessary scene
contained by a large video-object in a navigational
manner.
34
OVID

Features of OVID …

Generalization Hierarchy for Atomic Values:

OVID supports the usage of a generalization is-a
hierarchy, which consists of atomic values that are used
as attribute values of video-objects, in both cases:
creation and retrieval of video-objects.
35
OVID

Features of OVID …

Video Objects as Attribute Values:


OVID allows a video-object to be an attribute value of
another video-object.
This is very useful when it is difficult to describe a
meaningful scene by text.
36
OVID

Features of OVID …

Ad hoc Query Facility for Video Objects:


OVID has an ad hoc query facility, called VideoSQL.
It facilitates retrieval of a collection of video-objects that
satisfy a given condition.
37
OVID

Component of OVD

The OVID system consists of the following
Components
 VideoChart: A bar-chart type, visual interface for
manipulating video-object.
 VideoSQL: An ad hoc query facility to retrieve
video-objects.
 Video Object Definition Tool: A facility for object
definition.
38
OVID

VideoChart

VideoChart has the following facilities:






Browsing video-objects in a bar-chart form
Playing video-object as live video
Inspecting and updating video-objects
Composing (merge and overlap) video-objects
Decomposing (disaggregating) of video-objects
Moving to the video object definition tool and VideoSQL.
39
OVID

Browsing of a Video Database by VideoChar:




VideoChart can view the content of a video
database in a visual form.
A collection of video-objects appearing in a
specified range are displayed in bar-chart form.
Each line denotes a single video-object.
The figure shows the currently displayed range is
from frame# 26 830 to frame# 31 140.
40
OVID

Features of OVID …
41
OVID

Several operations can be applied on the selected
video-object.



Copy: copies the selected object into a buffer for later
use in VideoSQL
Play: replays the selected video-object on the monitor
screen as a live video
Inspect: first it evaluates the specified video-object
based on the interval inclusion inheritance, and displays
the attributes and their values including the inherited
ones.
42
OVID

Merge and Overlap Operations in
VideoChart:


After the user selects two arbitrary video-objects,
he can apply the operations merge and overlap to
those video-objects.
Disaggregate of a Video-Object


When the operation disaggregate is applied on a videoobject, it is automatically divided into ten sub-videoobjects.
The figure shows that Video Disaggregation System as
just launched:
43
OVID

Features of OVID …
44
OVID

VideoSQL




VideoSQL is a query language of OVID for
retrieving video-objects.
Users can formulate VideoSQL query in the fill-inthe-blank manner
The result of VideoSQL is a collection of videoobjects that satisfy the specified condition.
The figure shows an example query formulated by
VideoSQL.
45
OVID

Features of OVID …
46
OVID

A VideoSQL query consists of the following
clauses:

SELECT clause: This is different from ordinary SQL. It
specifies only the category of the resulting video-object
as:




Continuous: objects consisting of a single continuous video
frame sequence.
Incontinuous: objects consisting of more than one
continuous video frame sequence.
AnyObject: all types of objects whether they are continuous
or not.
FROM clause: This clause is used to specify the name
of the video database
47
OVID

WHERE clause: This clause is used to specify the
condition, consisting of attribute/value pairs and
comparison operators.


The user can select necessary attribute names by means
of pop-up menu.
The user can specify the following condition:
 [attribute] is [value | video object]
 [attribute] contains [value | video object], this is
concerned with set-type attributes.
 definedOver [video sequence | video frame], this returns
video-objects that are defined over the specified video
frame sequence of frame.
48
OVID

Video Object Definition Tool


The object definition tool is used to define and
update video-objects.
The object definition is accomplished by filling-inthe-blanks manner


Attribute names are selected by a pull-down menu
Atomic values can be specified by selecting an
appropriate value from the scroll windows of the
generalization browser
49
OVID
50
Conclusion


A video object data model and several
operations for video-objects
The major characteristics of the video object
model:



The notion of video-object
Interval inclusion inheritance
A collection of operations: interval projection,
merge, and overlap
51