In order to provide automatic ontology-based multimedia annotation for producing linked data, scalable high-level media interpretation processes on (video) streams are required. In this paper we shortly describe an abductive media interpretation agent, and based on a Multimedia Content Ontology we introduce partitioning techniques for huge sets of time-related annotation assertions such that interpretation as well as retrieval processes refer to manageable sets of metadata.
A large amount of multimedia content is available on the Web, and these days
appropriate multimedia documents can hardly be systematically found using
keyword-based search. Therefore, the eld of Linked Data has emerged [
To some extent linked data can be automatically derived using existing datadriven media analysis systems. However, there still exists a gap between, for instance, low-level image/video analysis and high-level image/video interpretation, not to mention human-level understanding. Thus, analysis-level results obtained from state-of-the-art tools have to be augmented with more abstract symbolic descriptions. This is accomplished in an automatic process which we call media interpretation. Recent research in the area of ontology-based media interpretation has shown enormous advances, and we assume that media interpretation processes can safely generate linked data, to be used in ontology-oriented media retrieval processes. For brevity, linked-data generation is also called (automatic) annotation in this paper, and we focus on videos as multimedia objects in order to be as concrete as possible.
The sheer amount of assertions for appropriately describing the content of large media objects makes media interpretation as well as annotation-based retrieval increasingly di cult. In this paper we advance the state-of-the-art in several areas by: 1. Proposing a description language for video annotations that supports scalable high-level reasoning about video content (interpretation as well as retrieval). 2. Explaining ontology-based reasoning techniques for an annotation agent, which is used to compute high-level interpretations of videos. 3. Showing how to support decomposition-based scalability for reasoning in the context of long streams of video content.
There already exist various proposals for annotation languages (see, e.g.,
early approaches based on MPEG-7 [
Scalability is a signi cant issue in at least two respects. If we talk about interpretation of a video document, then, on the one hand, there is the time dimension to be considered. On the other hand, another dimension is the interpretation depth. As we have argued above, we can assume that interpretation is based on explicit (symbolic) low-level information for each perceptive unit. A perceptive unit, such as a video shots, is called \segment" in MCO. The aim of interpretation is to compute high-level information for a segment given the knowledge acquired so far. Thus, in our annotation language we need to be able to represent time information as well as to support the ability to draw conclusions on higher levels of interpretation. Hence, the notion of a segment has to be appropriately de ned using an ontology, and assertions representing interpretation results at various levels of detail have to be attached to segments using an appropriate annotation language.
It can easily be seen that this kind of two-dimensional streaming scenario, with multiple streams for multiple modalities, yields a signi cant growth of assertions over time. Although our low-level annotation language is based on a description logic for which e cient typical-case reasoning systems are known, we need to exploit new partitioning techniques to break down the data descriptions used for interpretation into smaller pieces to be handled over time. This is even more important if low-level results become available for time frames in an asynchronous way (maybe with substantial time delays according to the intricacies of certain tools for di erent modalities). In order to improve scalability, we identify and use locality in the video stream. Given an annotation of a video stream, we use split-operations to compute so called \islands," which are sufcient for reasoning with respect to the current state of annotation. Running interpretation tasks on separate islands (instead of the whole set of assertions) improves performance signi cantly.
The remaining part of the paper is structured as follows. Section 2 presents
our motivation for choosing the description logic ALHf R+ (D) as an ontology
language for de nition of an annotation language MCO. In Section 3, we
introduce the Multimedia Content Ontology in detail and explain how ALHf R+ (D)
is used to represent the content of multimedia documents. We discuss scalability
issues and present solutions for partitioning large sets of assertions into
manageable \islands" or \chunks" in Section 4 such that interpretation processes
run e ciently. Several examples demonstrate the e ectiveness of the proposed
techniques. We conclude in Section 5. Due to space constraints, retrieval is not
covered in this paper (We refer to [
In order to describe multimedia documents in terms of annotations (stored as
metadata), the Moving Pictures Experts Group (MPEG) has speci ed the ISO
standard Multimedia Content Description Interface, also denoted as MPEG-7
[
Ontology languages such as RDFS or OWL2 are languages which have a
formal semantics, a feature that is bene cial for formally de ning decision
problems and checking correctness of corresponding decision procedures (aka
inference algorithms). However, speci c ontologies (aka knowledge bases) speci ed
using an expressive ontology language reveal more of the \semantics" of media
documents as mere RDF triples do. Ontologies achieve this by adding (lots of)
implicit content description tuples to the annotations given explicitly as part of
the documents' annotations. Thus, we have \semantics" in the sense of formal
semantics of a representation language and \semantics" in the sense of implicit
tuples added to the explicitly given ones. Many papers in the Semantic Web
literature amalgamate these two kinds of \semantics", suggesting that semantics
in the sense of content descriptions come for free using formal representation
languages. For the latter notion of \semantics," we prefer the name content
description in order not to confuse the reader. Content descriptions do not come
for free but must be derived using media interpretation processes, which require
dedicated knowledge bases for interpretation knowledge [
In MPEG-7, a multimedia document is related to its modality speci c content, composed of, e.g., video, audio, or text, and each of these parts consists of a set of segments specifying \regions" of modality speci c data. At rst, we believe it is necessary to be able to specify more general resp. more speci c concepts and roles (e.g. that video content also is of type multimedia content) for building up a taxonomy. Further, it is important to be able to specify concept disjointness. In order to represent relations (e.g. from content to segments) roles can be speci ed, whose domain and range usually are constrained to a speci c concept (e.g., the role hasMediaDecomposition is constrained to only relate instances of multimedia content to multimedia segments) and which are possibly functional or transitive. In addition, we propose that for modality speci c concepts the range of roles is further restricted to modality speci c concepts (e.g. audio content is only allowed to be related to audio segments). Finally, for representing multimedia content it is usually necessary to be able to specify concrete domains such as integers or strings.
We argue that this expressivity is su cient for the representation and
interpretation of multimedia content for a large range of problems. For example,
we propose to abandon existential restrictions on the right side of inclusion
axioms, since we believe that it is not required to constrain multimedia content
descriptions to consist of \anonymous" individuals of a speci c type (which
cannot be retrieved explicitly [
We now shortly introduce the descripton logic (DL) nomenclature. A DL
signature is a tuple S = (CN; RN; AN; IN), where CN = fA1; :::; Ang is the
set of concept names (we also use A for concept names in the sequel). RN =
fR1; :::; Rmg is the set of role names. Further, AN is a set of concrete domain
attributes (i.e., roles whose range is a concrete domain). The signature also
contains a component IN indicating a set of individuals. A DL knowledge base
OS = (T ; A), de ned with respect to a signature S, is comprised of a
terminological component T (called Tbox ) and an assertional component A (called
Abox ). In the following we just write O if the signature is clear from context.
An ALHf R+ (D) Tbox is a set of axioms A1 v A2 and R1 v R2 (atomic
subsumption), A1 v :A2 (disjointness), 9R:> v A and > v 8R:A (domain and
range restrictions on roles), > v ( 1 R) (functional roles), T rans(R)
(transitive roles) and A1 v 8R:A2 (local range restrictions on roles). An Abox A i is a
set of concept assertions A(a) and role assertions R(a; b), where A is a concept
name, R is a role name, and a; b represent individuals. Aboxes can also contain
equality (a = b) and inequality assertions (a 6= b) as well as attribute assertions
of the form Attr(a; val) where Attr is an attribute and val is either a string
or an integer (with the obvious denotation). For a detailed introduction to the
incorporation of concrete domains into DLs, to the semantics of concepts and
roles, as well as an introduction to the satis ability conditions for axioms and
assertions we refer to [
In this section, the CASAM Multimedia Content Ontology is presented to an
extent that the solution to scalabilitiy problems can be understood. The full MCO
can be found at http://www.sts.tu-harburg.de/casam/mco.owl. In contrast
to approaches transforming the complete MPEG-7 standard to RDFS [
In Fig. 3.1 the concept hierarchy (on the left) and the role hierarchy (on the right) of the multimedia ontology is shown. A complete multimedia document is represented by the concept MultimediaDocument . Only one instance of type MultimediaDocument should be speci ed for a document to be annotated.
Individuals which are instances of (subconcepts of) MultimediaContent represent di erent modalities of the video. The concept VideoContent represents the video modality and holds all video segments. In the same way AudioContent holds all segments from the audio modality.
TextContent represents text paragraphs associated with certain segments or the whole video. Auxiliary text documents that are related with the whole annotated video are represented by the subconcept AuxiliaryContent . During the annotation process, a user can make free text annotations, which describe the whole multimedia document or a single segment (shot) of the video. These free text annotations are represented by GlobalUserAnnotationContent resp. LocalUserAnnotationContent . As speech, recognized in the video, is transformed into text, the concept SpeechRecognitionContent is also subsumed by TextContent .
To represent parts of the content, MultimediaContent instances can be decomposed into MultimediaSegment instances. TextSegment refers to words in the text modality. The concept SegmentLocator is used to specify start and end of segments. The concrete values of start and end represent temporal position information for audio and video, or denote character positions for text. BoundingBox is used to determine the position of a recognized object in a video frame. All concepts within the same hierarchy level are disjoint.
The role hasLogicalDecomposition decomposes the whole media document into the di erent parts by relating instances of type MultimediaDocument with modality speci c content description individuals (that is, instances of the concept M ultimediaContent). An individual of the type MultimediaContent is associated to its segments by the role hasMediaDecomposition. To relate an individual of type MultimediaSegment with its locators, the role hasSegmentLocator is used.
The roles nextTextContent and nextTextSegment are used to specify the
order in the text paragraphs resp. words. Both are transitive roles. Subroles of
correlatesWith can be used to represent associations between content
descriptors. A TextContent instance can be related to a VideoSegment using the role
belongsTo. We also use a small subset of the Allen relations [
The role depicts is used to establish a mapping from individuals of the Multimedia Content Ontology to observations from the domain ontology that were extracted by analysis modules. In a similar way as depicts, hasInterpretation provides a map to individuals that were generated as a part of interpretations of observations. To represent the aggregating characteristic of high-level interpretations, the role associatedWith is used to related high-level interpretations with other interpretations or directly with observations. 3.2
Range restrictions on roles constrain the corresponding role llers to be of a speci c type. For example,
> v 8hasM ediaDecomposition:M ultimediaSegment de nes the range restrictions on the role hasM ediaDecomposition such that the role ller is constrained to be of type M ultimediaSegment.
Local range restrictions constrain the range of roles further when the role is applied to a speci c concept. The local range restriction
speci es that the range of the role hasM ediaDecomposition associated with the concept AudioContent is further restricted to AudioSegment. 3.3
The attributes hasStart and hasEnd are used to specify time information of video or audio segments. For example:
AudioLocator(as1); AudioLocator(al1); hasSegmentLocator(as1; al1) hasStart(al1; \00:43"); hasEnd(al1; \00:52") de nes the starting time of an AudioSegment, e.g., as1 by specifying concrete values to its corresponding AudioLocator al1. Integer values are used to specify character positions to identify words in larger text strings. Also regarding the text modality, the property hasConcreteValue is used to associate strings to instances of speci c types such as CityN ame.
Given quantitative information about start and end time, qualitative
relations between locator instances are computed by the media interpretation agent.
From the potential 13 qualitative relations de ned by Allen [
As we have seen, for improving shot-based video annotation, interpretations are
computed for co-occurrences of locator individuals according to temporal
information. In the course of the video interpretations, Aboxes grow signi cantly.
If, e.g., a particular video segment is focused on because there is a new
assertion coming in, referring to this video segment, only very few other assertions
are relevant. Large parts of Aboxes (e.g., for temporally far away parts of the
video) need not be processed. In this section we formalize the subdivision of large
Aboxes into meaningful parts (partitions) such that reasoning problems are
handled in the same way as with the large Abox. Reasoning on the small partitions,
also called island reasoning, is known to improve reasoning performance
significantly [
In [
Each is added to the Abox that the agent maintains. Subsequently, a set of forward-chaining rules is applied. The general form of these rules is
Q1(Y1); : : : ; Qn(Yn) ! P (X) vc1: VideoContent hasMediaDecomposition
…
vs1: VideoSegment
vs2: VideoSegment
…
vl2: VideoLocator
… …
… …
… as2: AudioSegment
as1: AudioSegment
depicts hasSegmentLocator o
where Q1; : : : ; Qn; P denote concept or role names and underlined letters denote
(possible) tuples of all-quanti ed variables with the condition that each variable
appearing in P (X) does also appear in at least one Qi(Yi). In order to be able
to apply a rule, appropriate individuals have to be substituted for the variables.
Conclusions P (i) are then added to the Abox. For the conclusions P (i) the
M I Agent seeks further explanation using an abduction process. The main idea
is to backward chain a set of rules of the form introduced above. Due to space
restrictions, this process cannot be explained in detail, and we refer to [
Example 1 A car is shown in a video shot, represented by an assertion Car(c1), and there is the sound of a door slam, represented by an assertion DoorSlam(ds1). The car and the door slam are associated to video and audio segments, resp. Those, in turn, are associated with locator objects. Now assume that the car and the door slam co-occur, i.e., the locator objects for the audio segment is located during the video segment. Figure 2 depicts a complete scenario for the example.
Using relations between time points, one might use rules to de ne a during relation as a view based on the quantitative temporal information for the locator objects. However, using relations between time points, in principle, every locator might be associated with every other locator, and thus the agent can hardly partition the large Abox into smaller parts. Therefore, we have designed the agent in such a way that it adds qualitative relations such as overlaps (o), during (d), and meets (m) to make certain temporal information explicit that is hidden in the quantitative locator time speci cations. The motivation for the agent to switch to the more verbose qualitative representation is that the input Abox becomes partitionable.
Qualitative temporal relations are used in forward-chaining rules to compute assertions that are then explained by the agents (see above). For instance, based on the forward-chaining rule
V ideoLocator(xl); AudioSegment(y); hasSegmentLocator(y; yl); AudioLocator(yl); d(yl; xl); depicts(x; w); depicts(y; z);
Car(w); DoorSlam(z) ! CarDoorSlam(w; z)
the role assertion CarDoorSlam(c1; ds1) (marked with an ellipse in Figure 2) is
generated and added to the Abox. This new assertion is seen as a speci c
observation that requires an explanation [
As stated before, the input can be considered as a stream. The information
content derived from a stream is collected over time and stored together with
the interpretations in an Abox or in multiple ones, respectively, if more than one
interpretation is possible. These Aboxes are put to the previously introduced
agenda A. The more knowledge is gathered, the larger those Aboxes become and
the longer it takes to complete all computations such as applying the
forwardchaining rules or arranging the interpretation process itself. Current
state-of-theart DL reasoning systems cannot deal with this amount of information any more,
because they rely on in-memory structures. To overcome this problem, in [
The underlying idea is that only a small subset of concept and role assertions
called island is necessary to perform instance checking for a particular given
individual i and a given (complex) concept C. The approach chosen here is to
identify role assertions which can be used during the application of a tableau
algorithm for instance checking [
A2 = A n fR(a; b)g [ fR(a; b0); R(a0; b)g [ fb0 : Cjb : C 2 Ag [ fa0 : Cja : C 2 Ag; s.t. a0 and b0 are fresh individual names and IN C(O) denotes an inconsistent ontology O.
Example 1 (cont.) Applying the de nition of O-separability to the Abox depicted in Figure 2, islands are computed as shown in Figure 4. Instead of applying all possible substitutions, the forward-chaining rule does only need to be applied to the island with the locators vl1 and al1 in order to add CarDoorSlam(c1; ds1). This enables parallel processing for abduction and retrieval scenarios. However, given the local range restriction for AudioContent, if as1 is not explicitly specied as AudioSegment but rather as M ultimediaSegment, the de nition of Oseparability would be violated for hasM ediaDecomposition(ac1; as1)|so that the respective island would be larger than before.
This general Abox modularization approach has proven well regarding
scalability issues. For more details, in particular regarding a theoretical and practical
underpinning of the island approach, we refer the reader to [
hasLogicalDecomposition vc1‘: VideoContent md1‘‘: MultimediaDocument hasLogicalDecomposition vc1: VideoContent hasMediaDecomposition vs1‘: VideoSegment … … vc1‘‘: VideoContent hasMediaDecomposition vs1: VideoSegment vl2‘: VideoLocator
m
Under the consideration of MPEG-7 and [
Some initial experiments were performed to see how the approach behaves in the CASAM context. The results are very promising and almost all roles were O-separable after qualitative assertions were added to Aboxes such that quantitative information is no longer required. Thus, switching from a quantitative to a qualitative representation provides practical bene ts for the agent.
Our work complements other work on stream reasoning, i.e., for e ciently
maintaining materialized views as described in [