ROBUST REPRESENTATION OF SHAPE WITH DAGS - Video Object Extraction and Representation: Theory and Applications - page 117

only one macro-structure exists between the two breaks. A path from
source to sink corresponds to a sequence of macro-structures that is
equivalent to a simple partitioning. A DAG o expresses a set of simple

part it ions.
For a robust recognition process, we wish to compare all simple par-
titionings of two datastreams against each other. By using DAG o as a
compact expression of this set of simple partitionings, we can efficiently
compare two complex partitionings and the sets of simple partitionings
that they encode.

APPLICABILITY OF DAG-CODING
Although any datastream can be DAG-Coded, this section lists the
characteristics that a datastream must have to benefit from representa-
tion in DAGs:

1. Existence of Macro-Structures

The partitioning process attempts to break up the datastream with
respect to macro-structures. If there are no such macro-structures
within the datastream, partitioning has no meaning.

2. Determination of Break Locations without Datastream Con-

tent
We assume we can locate the breaks without knowledge the datas-
tream content. As in most content-based segmentation problems, we
cannot truly identify the content without correct partitioning, and
we cannot partition the datastream without knowing the content.
To break this cyclic dependence, we require the position of breaks
can be inferred directly from the datastream with good accuracy.

3. 1-D Ordering within the Datastream
DAGs require the datastream to be ordered. This ordering allows
a path within the DAG to compactly represent a simple partition
of a datastream. If there is no ordering of the macro-structures,
the paths within DAGs no longer correspond to simple partitionings,
invalidating the representation. Most datastreams have this ordering
enforced through time indexing, although any 1-D ordering of the
data is satisfactory.

4. Partitioning Granularity

Efficiency and quality of the partitioning is directly related the re-
duction of data granularity in its extraction. If the partitioning is too
fine, DAG-Coding will have little advantage over the original data-
stream, since the number and ordering of elements are similar. If the