The document mpeg7video.xml we used for the query is a MPEG-7 XML document for describing the content of a turbine inspection videoFigure 1. This video has been processed and video objects are extracted for generating this MPEG-7 description.

Figure 1. An Industrial Turbine Inspection Video

This MPEG-7 document consists of an AudioVisualContent of type "VideoType" named "TurbineVideo". The video is segmented into scenes and the scenes are described by using the "SegmentDecomposition" tag with the decomposition type "SpatioTemporal". Each segment or scene can have several objects of interest and they are described here as well. In particular, let's take a look at the second segment which has an id "BurnerScene" and is of type "MovingRegionType". We use the "MovingRegionType" tag because there are multiple objects that move over time. The detailed descriptions are as follows.

Figure 2. mpeg7video.xml document

The video segments (scenes) can be further broken up using the same "SegmentDecomposition" tag and is again of type "SpatioTemporal". Taking a closer look, we find that the first object has an id "MR001", and it moves over time, the trajectory of which is given here. The tag "MediaTime" provides the duration of the object. The location of the object is defined temporally using the tag "ParameterTrajectory". At the first frame or instance where the object first appears, the location is given by a 4x2 matrix defining the four coordinates of the object boundary. Any number of coordinates can be used to define the boundary. The complete interval, defined using "WholeInterval" tag, consists of 300 secs. The base time unit is 1 sec (P1S). There are 25 node points which determine the "KeyPointNum". The "InterpolatedValue" tag is used to define the corresponding coordinates of the object of interest at each of these nodes. Each KeyValue gives the coordinate location for a single vertex. This is done for all four vertices that constitute the boundary in this case. Since the value of attribute "MotionModel" is 0, it means a linear model. For frames that lie within these nodes, a simple linear interpolation is used to determine the actual location on that frame. The rest of the example follows the above format to describe other objects and scenes in the video.

We have developed a tool based on the scene change technique[Chakraborty 99]to generate such a description from a video as follows. At first, the video is broken down temporally into scenes or shots using scene change detection algorithms that can detect both, abrupt as well as gradual changes. Next, the users identify objects of interest within these scenes and outlines them. These are then tracked over time in a semi-automatic way. Wherever there is a significant motion change and a linear mode is inadequate, a node point is created. To make things simpler as described in the above example, one can also divide the interval into equal segments. At these boundaries, node points are created and the object outline is described.

In previous work[Liu1 00] [Liu2 00] [Liu3 01], we have shown that multimedia objects can be described as spatial, temporal and visual datatypes by using abstract datatype technique (ADT). The composite datatypes can be constructed from more primitive ones. These datatypes can be formalized as XML element datatypes within W3C XML Schema [XML Schema Part 1: Structures] framework, particularly the datatype part [XML Schema Part 2: Datatypes]. The relationships of multimedia objects are often derived from element datatypes rather than from element hierarchical relationships. The relationships can be even predefined as another complex datatypes for multimedia XML documents. A similar technique for specifying moving objects was proposed by [Erwig 99] [Manolopoulos 00] in relational databases.

At 51th MPEG meeting in March 2000, MPEG committee has decided to adopt XML Schema Language as MPEG-7 Description Definition Language (DDL) for describing multimedia content. Since then, a comprehensive set of audio and visual datatypes is being developed based on XML datatype mechanisms. The main components of the MPEG-7 standard are: Descriptors (Ds) for describing audio and visual features, Description Schemes(DSs) for describing the structure and semantics of the relationships between components. The components can be either Ds or DSs. There is also a description definition language for allowing the creation of a new D or DS and for allowing extension of existing Ds or DSs.

MPEG-7 datatype hierarchy can be viewed as follows. The base level datatypes are: Mpeg7Type, basic datatypes, reference datatypes, unique identifier datatypes, and time datatypes. Mpeg7Type provides the main basic abstract type of MPEG-7 type hierarchy. From Mpeg7Type, DSType (Description Scheme Type) and DType (Descriptor Type) are derived. From DSType, SegmentType, RelationType, GraphType, VisualDSType and AudioDSType are derived. From DType, VisualDType and AudioDType are derived. From SegmentType, StillRegionType, VideoSegmentType, MovingRegionType, AudioSegmentType AudioVisualSegmentType, and SegmentDecompositionType are derived. Some of the temporal, audio and visual datatypes are described as follows.

MPEG-7 temporal, audio and visual datatypes can be further composed into more complex MPEG-7 datatypes by using XML datatype definition mechanism, predefined MPEG-7 Ds, or predefined MPEG-7 DSs. The common used DSs for composing the content are: SegmentDecomposition DS,Segment DS (e.g. MovingRegion DS, StillRegion DS, etc),Graph DSand Relation DS. Each DS or D itself is a MPEG-7 datatype. For example, MPEG-7 ParameterTrajectory datatype, SpatioTemporalLocator DS and MovingRegion DS are all spatio-temporal composite datatypes, called ParameterTrajectoryType,SpatioTemporalLocatorType and MovingRegionType, respectively for specifying spatial data changing over time. These spatio-temporal datatypes are constructed from primitive temporal datatypes (e.g., MediaTime) with spatial datatypes (e.g., RegionLocatorType) or previously defined spatio-temporal datatypes. In addition to content description DSs in MPEG-7, there are many other DSs that facilitate content navigation, content organization, content management, and user interaction. MPEG-7 DSs are used to support varieties of multimedia content retrievals such as semantics-based retrievals, structured-based retrievals, model-based retrievals, and navigation/browsing (e.g., content summary). Thus, MPEG-7 content access requires an expressive query language to support the intended information retrievals from XML-based multimedia content descriptions.

MPEG-21 committee has also decided to use a uniform and interoperable XML schema to declare digital items. A Digital Item is a structured and hierarchical digital object containing several multimedia elements (e.g., sounds and video clips) and meta data. In order to declare the structure of such a Digital Item to users for interacting with the content, MPEG-21 is developing an XML-based language called the Digital Item Declaration Language (DIDL) for expressing the relationships of different objects within a particular Digital item. In MPEG-21 Part 4: Digital Item Identification and Description (DII&D), XML schema is used for identification and description of any digital items regardless of its nature, type or granularity. For content identification, the DII&D provides the ability to associate Uniform Resource Identifiers (URIs) with an entire Digital Item or its parts. For content description, the DII&D framework provides the ability to include meta data from various sources and in various formats including XML or plain text. DII&D allows the binding of existing Description Schemes to meta data to allow the correct processing of such meta data. This enables to include MPEG-7 or other descriptions. Example of DIDL XML document is shown Figure 3 below.

Figure 3. Example of MPEG-21 XML document

In this example, we declare the digital item of our inspection video in a MPEG-21 XML form. This digital item declaration consists of several subitems of video scenes such as overview, opener, etc. Each digital subitem has two kinds of digital item components: mpeg7 XML form or mpeg1 video form. Choice and Selection elements are used to specify the proper configuration of user-desired digital items. The select_idattribute value of Selection identifies a predicate such as “burner”, “overview”, etc. In general, this predicate is related to one or more Condition elements somewhere within an Item or a Component. The set of Condition elements defines a Boolean combination of predicate tests. For simplifying the issue, we only use one Condition for each Component in this example. The require attribute value of Condition defines an AND logic combination of predicates. The multiple Condition elements within a given parent are combined as an OR logic combination. The set of Condition elements denotes the parent element as being conditionally selected upon the truth of the Boolean combination of predicate tests. The Digital item identification and descriptions (DIID) associated with digital items are contained in Statement element of any descriptor element as shown in Figure 4 below

Figure 4. Structural Hierarchy in Digital Item Declaration Documents

A digital item could be a complex structured XML document. A digital item should not be considered just as a single entity since it can hierarchically consist of multiple subitems and components. Each subitem and component could be used to declare a form of digital item representation such as file format, media type, or individual part, etc. A DIDL XML document can be viewed as a structured catalog document to declare and package multimedia information items with logic-based selection descriptions for exchange. DIDL documents queries can be viewed as structured catalog search based on the semantics of selection logic in the documents.

In answering to these specification issues, we have designed an experimental XML query language MMDOC-QL. This language embeds within it a logic formalism, called Path Predicate Calculus, to specify queries. Formulas in path predicate calculus are restricted forms of first-order predicate. For these logic-based queries and manipulations, we have designed two important predicates: element predicatesand path predicates for asserting logical truth statements about document elements in a document tree. This path predicate calculus can adequately support the co-occurrence constraints and document addressing specifications for querying XML documents. To support intensional data and relationships specifications in this logical formalism, certain stereotypical logic operators are incorporated for asserting multimedia object relationships in this query language. Examples of the multimedia logic operators are, OVERLAP(element1: RegionLocatorType, element2: RegionLocatorType), TRAJECTORY(element1: MovingRegionType, element2: MediaTimePoint), etc. Another logic operator MEMBERP is also included for asserting intensional data such as MediaTImePoint in the language constructs.

In the following, we illustrate MMDOC-QL for specifying MPEG-7 XML document queries. An example of query is in the form of "finding all video object ids and show up time over a particular area".

In MMDOC-QL, there are four clauses: OPERATION clause (either GENERATE, INSERT, DELETE, or UPDATE) is used to describe the logic conclusions in the form of allowable element predicates and path predicates. In this paper, we focus on retrieval operation clause by using keyword GENERATE for MPEG-7 XML queries. PATTERN clause is used to describe the domain constraints of free logical variables including tag, attribute, content, address and datatype, by using regular expressions. FROM clause is used to describe source documents for querying. CONTEXT clause is used to describe logic assertions about document elements in allowable logic formulas in path predicate calculus. FROM and CONTEXT clauses are paired together and there could be multiple pairs for describing multiple sources. The logic variables are indicated by "%" such as "%objectid". Queries in MMDOC-QL are equivalent to finding all proofs to existential closure of logical assertions.

In this example, the path logic formula (<Segment> WITH xsi:type="MovingRegionType" ... <MediaTime> AT %x)))in CONTEXT clause asserts that element “Segment” with id equal to %objectid contains element “SpatioTemporalLocator” of which the video objects are located during MediaTime %x.

In general, (<%t> WITH attribute1=%x1, ..., attributen=%xn AT %a CONTAINING %c) is an English-like notation for element predicate E(x1, x2, ..., xn, c, t, a) which stands for a logic assertion that element "t" at address "a" contains "c" with attributes x1, x2, ..., xn in a document tree. For brevity, we can also use short versions with only needed variables in logic queries such as (<%t> WITH attribute1=%x1, ... attributen=%xn), (<%t> CONTAINING %c), etc., if a full version can be implied clearly in the context.

A path logic formula is a composition of element predicates by XPath[XPath 99] “axis-operators” . Examples are (a) parent/child relationship operators such as: INSIDE, DIRECTLY INSIDE, CONTAINING, DIRECTLY CONTAINING, etc. and (b) the sibling relationship operators such as: BEFORE, IMMEDIATELY BEFORE, AFTER, IMMEDIATELY AFTER, SIBLING, IMMEDIATELY SIBLING, etc.such as DIRECTLY CONTAINING, etc. Note that here we use a logic form of axis concepts defined in XPath since path formula in Path Predicate Calculus are logical statements for asserting logical truths. An example of the path predicate is: (<bibref> INSIDE (<gcapaper> CONTAINING (<fname> CONTAINING "Peiya") AND (<surname> CONTAINING "Liu">))))for specifying all bibref elements inside Peiya Liu's paper.

The domain of logical variable %objectid is restricted to be strings beginning with “MR” followed by digits in PATTERN clause. The logic variable “%t” is to used to bind the MediaTimePoint in this MediaTime interval “%x” during logic computation. TRAJECTORY operator is used to assert trajectory region from a moving region %movingregion at MediaTimePoint %t, and OVERLAP is a spatial logic operator for further asserting that the desired object region is also overlapped with the focus area.