Digital Signal Processing Reference
In-Depth Information
der in ancestor-descendent relationships to recursively compute a robust
similarity measure.
By induction, we can link our DOT-Compare algorithm to the DAG-
Compare operation. A path from source to sink in the DAG contained
by a DAG-major node is representation of a simple partition of the mul-
tiresolution tree. The DAG-major node is compact representation of
multiple simple partitions of the tree. To compare two DOTs together,
we find the best matching paths between the two DAG
o
s of two DAG-
major nodes. However, in addition to a sequence of feature vectors, every
path within a DAG-major node also contains a sequence of DAG-major
node references. By inductive hypothesis, we assume that all compar-
isons of DOTs in this sequence are solved since DOT references always
point to a DOT-major node lower in the hierarchy. This operation is
exactly the DAG-Compare operation as described in Chapter 5, with an
MatchEdge function recursively calling the DOT-Compare algorithm.
To implement the comparison algorithm, we use the DAG-Compare
algorithm with recursive calls that are short-circuited if they have previ-
ously calculated or have reached our basis (see Figure 6.13). Following
a general form for DAG-Compare in Section 5., we embed a recursive
DOT-Compare call in our MatchEdge operation.
{
x
- NWeight(
e
2
, Get REF(
e
2
)),
e
1
=
λ
x
- NWeight(
e
1
, Get REF(
e
1
)),
e
2
=
λ
MatchEdge
DOT
(
e
1
,e
2
,
x
) =
x
-
γ
(
e
1
,
e
2
), otherwise
(6.2)
(
DOT-Compare(GetREF(
e
l
), Get REF(
e
2
))
)
NWeight(
e
1
,
e
2
).
(
1 - exp
(
-e
2
)
)
+
)
(
e
1
-
e
2
)
T
C
(
e
1
where
γ
(
e
1
,
e
2
)=
,
NWeight
(GetREF(
e
1
),
Get REF(
e
2
)).
where
e
1
and
e
2
are edge values,
is an empty edge value, the function
Get REF returns the DAG-major node reference in the edge value,
C
=
λ
diag(
c
length
, c
curvature
,c
thickness
,c
VOSweight
,
0) ,
NWeight returns the per-
centage of the total VOS value that is contained by two given structures,
and DOT-Compare
DOT
approximately returns the probability that the
two DOTS are similar. We know that, for a given DOT-major node, all
DOT-major node references that point to DOTs lower in the DOT hier-
archy and we can build the comparisons up the DOT hierarchy. We must
only do
a quadratic
number of recursive
DOT-comparisons
to
compare
the two DOTs.
The running time of the algorithm is
O
(
mn
) where
m
is the total
number of edges and nodes (both DAG-major and DAG-minor) in the
Search WWH ::
Custom Search