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

Partitioning is the process that identifies the breaks and induces
the macro-structures from the position of the breaks. By finding the
breaks in the datastream, we can distinguish this composition of macro-
structures more readily than the datastream. As shown in Figure 5.2,
if we can partition with only one macro-structure between two consec-
utive breaks, partitioning can aid in recognition by raising the level of
represent at ion of the datast ream.
A simple partitioning inserts a series of breaks into the datastream
and macro-structures are assumed to occur only between two consecutive
breaks. A simple partitioning is the divide step in a traditional divide
and conquer approach. A simple partitioning and its order may be
expressed as a list of macro-structures. We generalize simple partitioning
while maintaining the concept of ordering.
As shown in Figure 5.3, complex partitioning inserts a series of breaks
into the datastream, but allows macro-structures to occur between any
two breaks. If we are trying to recognize a unknown datastream, the
location and existence of breaks may be uncertain and the definition of
macro-structures may also be ambiguous. To be explained in Section 4.,
a complex partitioning can address these problems by expressing mul-
tiple simple partitions in a single data structure. To express complex
partitioning in a data structure, we generalize the list that represents
a simple partitioning to a DAG that represents a complex partitioning.
This complex partitioning is the divide step in a robust divide and con-

quer approach that generalizes the divide step to complex partitioning.

4. DAG-CODING
DAG-Coding transforms a datastream to its DAG representation via
complex partitioning. We explain how complex partitioning can be used
for robust recognition, how complex partitioning maps to a specific type
of DAG, DAG o , and what characteristics of a datastream make DAG-
Coded representation advantageous.

COMPLEX PARTITIONING FOR
RECOGNITION
For recognition, complex partitioning supports a graphical represen-
tation that is robust to errors with the partitioning process and ex-
presses some of the inherent complexity of the datastream. Partitioning
locates breaks within the datastream without prior knowledge of the
macro-structure. Ideally, a simple partitioning can locate all breaks in a
datastream, but, either due to 1) the errors in the break location heuris-