A SYSTEM FOR IMAGE/VIDEO OBJECT QUERY BY SHAPE - Video Object Extraction and Representation: Theory and Applications - page 146

Figure 6.12. Problems of extraction and our solution in DOT S . a) the extra joint
problem, the protrusions in the grayed area lead to ambiguously ordered tree extrac-
tion. Both ordered trees are coded as one DOT. b) the extra branch problem, the
branch in the gray area may be inconsequential. Both ordered tree representations
are coded as one DOT. Note that these problems happen at all levels of the ordered
tree representation

and the transformation applies to internal subgraphs as well near

the leafs.

COMPARISON OF DOTS: DOT-COMPARE
To compare the DOT representations of our VOS, we use a dynamic
programming algorithm called DOT-Compare, a recursive algorithm
that uses the DAG-Compare algorithm of Chapter 5 in its inductive step.
The DAG-Compare algorithm applies to partitioned linear datastreams
and uses only the topological order among elements in the same DAG. In
contrast, the DOT-Compare algorithm applies to partitioned hierarchies
and, in addition to topological order of the DAG, uses the topological or-