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

DOT. Problems in the ordered tree occur when a small perturbation in
the contour may cause a large change in the hierarchy. An extra joint
problem occurs in Fig. 6.12a where the existence of a joint is question-
able. An extra inserted branch problem occurs when the existence of
a line segment is questionable, but not its children. As shown in Fig-
ure 6.12b, if small line segment exists, then instead of having all branches
hang off the same point, the branches are split in the hierarchy. Once
again, a small perturbation has caused large change in the hierarchy.
Although these problems may occur infrequently, the problems can oc-
cur at any node in the ordered tree. To add robustness into the ordered
tree, we merely code both ordered tree representations into our DOT
at every place where we recognize the possibility for extra joint and ex-
tra inserted branch problem. As shown in Figure 6.11, the steps are as
follows:
7.

Transform the Ordered Tree into a DAG-Ordered Tree
This

straightforward transformation converts each node in the tree

to a DAG-Major node that contains a linear DAG o .

8. Add extra graph structure to DOT for robustness.

A robust DOT representation can be created by encoding both possi-
bilities of each problematic case: with and without the extra inserted
branch (as shown in Figure 6.12a), with and without the extra joint
(as shown in Figure 6.12b). Since we are not concerned with running
time, we take a particularly aggressive approach, coding each joint
as a possible extra joint and each branch as a possible extra inserted
branch.

9. Extract an edge value from each line segment.

After our hierarchy is expressed robustly as DOT, we derive a edge
values for every DOT-minor edge to represent the line segment and
integrate other relevant information along with support structure into
the shape descriptor.

1engt h
curvature
thickness
VOSpercentage
DOTMajorRe f

e =

(6.1)

Where e is the edge value of one DOT-minor edge, and the components
of e are the length of the line segment, the curvature of the line
segment, the thickness of the contour at that point, the percentage
of the total VOS that the line segment contains, and a DOT-major
node reference, respectively.