Digital Signal Processing Reference
In-Depth Information
DOT-Compare(DOT-Major-Node A,B)
{
1
if (Empty(A)= =0 and Empty(B)= =0)
//
Basis #1
2
3
return 1.0
if (Empty(A)= =0 or Empty(B)= =0)
//
Basis #2
4
5
return 0.0
if (GetDAG(A),GetDAG(B) have been compared before
{
6
7
return (saved value)
}
else
{
8
9
return (DAG-Compare
DOT
(GetDAG(A),GetDAG(B)));
}
10
11
}
Figure 6.13.
DOT-Compare compares two DOTs against each other.
GetDAG
returns
the
DAG
o
of
the
given
DAG-major
node.
There
are
two
sets
of recur-
sion:
one
that
is
present
in the code
above,
and the other in
the function
call
to
DAG-Compare
DOT
,
that
uses
a
helper
function
in
Eq.
6.2
that
recursively
calls
DOT-Compare only
on
the
DOTs
lower
in
the
DOT
hierarchy,
using
the
dynamic
programming
principle
for
efficient
computation.
first DOT, and
n
is the similar value for the second DOT, since we
can construct an equivalent representation for the DOT structure as a
single flattened DAG. This construction is constant factor larger than
the original DOT, so the running time are equivalent in the O notation.
ROTATIONAL INVARIANCE
A rotationally invariant shape descriptor can be created by coding
in representations of rotated versions of the contour. To derive these
rotated version, we start the topological order of the DAG
o
in the DOT-
major root node at every line segment that comes off of the VOS root.
In this process, since the DOT structure below the root node remains
the same and we add DAG-minor edges to the only top-level DOT-major
node, the added complexity is proportional to the number of DOT-minor
edges that we add. Thus, a comparison with rotational invariance can
be computed with the complexity of
O
((
m
+
v
2
)(
n
)) where v is number
of DOT-minor edges at the top level DOT-major node.
6. RESULTS AND ANALYSIS
Results from first small database demonstrate the functionality of our
VOS-DOT similarity measure; results from the second large database
Search WWH ::
Custom Search