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

partitioning is too coarse, conventional feature extraction methods
through single functional mapping are a simpler solution than DAG-
Coding. In general, DAG-Coding needs to balance order with the
complexity of edge value.

5. Cost of Redundant Information

The complex partitioning tends to represent the same part of the
datastream on different edge values. The price of redundancy is hope-
fully compensated by improved recognition performance.

5. COMPARING DAG REPRESENTATIONS
This section presents an efficient algorithm (DAG-Compare) to mea-
sure similarity between two DAG-coded representations. The DAG-
Compare algorithm can be used for classification by comparing DAG-
Coded an unknown input to DAG-Coded examples that have previously
classified. Given two DAG-Coded representations, the DAG-Compare
operation finds the optimal match (to be defined in the next section)
between any simple partition represented in one DAG and any other
simple partition represented in another DAG. In terms of the graph, this
operation finds the optimal match between any path in one DAG, and
any path in another DAG o . After deriving a sequence of edge values (the
representations of the macro-structures) for each path, we can describe
a path matching as a Longest Common Subsequence problem [Cormen
et al., 1990] on these two sequences. For those readers familiar with the
dynamic programming, this operation is computationally equivalent to
finding a shortest path route through the crossproduct of two DAG, s
that have had null self-loops added [Ramadge and Wonham, 1989] [Tsit-
siklis, 1989] and this section is optional. However, since this operation
is integral to understand the applications of the DAG-coded represen-
tation, we provide the complete analysis to aid those less familiar with
dynamic programming.

COMPARING PATHS
If we describe a path as a sequence of edge values, we match two
sequences, A and B, through a function η called Pathscore, defined
below:

(5.2)