Digital Signal Processing Reference
In-Depth Information
DAG-Compare(DAG
o
R,T)
1
{
2
3
(
r
1
,
r
2
, . . . ,
r
||
Nodes
(
R
)
||
) ← Topo
l
og
i
ca
l
Sor
t
(
R
);
(
t
1
,
t
2
, . . . ,
t
||
Nodes
(
T
)
||
) ←TopologicalSort(
T
);
{
4
5
for
(
r
Nodes(
R
),
t
Node(
T
))
δ[
r,t
] ← -∞;
#
Initialize scores
6
p
[
r,t
] ← -∞ ;
#
Initialize scores
}
δ[
r
1
,t
l
] ← 1.0; # Set b basis of induction at (source,source)
for i ← 1to
||
(Nodes(
R
)
||
{
for j ← 1 to ||Nodes(
T
)||
{
for
7
8
9
10
11
12
13
InEdges
(
r
i
)
{
e
r
InEdges
(
t
j
)
{
for
e
t
a
← Prev(
e
r
);
14
b ← Prev(
e
t
);
15
16
17
18
if
(δ[
r
i
,
t
j
]<
MatchEdge
(
e
r
,
e
t
, δ[
a
,
b
]))
{
δ[
r
i
,
t
j
] ←
MatchEdge
(
e
r
,
e
t
, δ[
a
,
b
]);
p
[
r
i
,
t
j
] ← (
a
,
b
);
}
}
19
}
20
}
21
}
22
||Nodes
(
R
)
||
,
return
δ[
r
2
3
||
Nodes
(
T
)
||
],
P
;
t
24
}
Figure 5.10.
DAG-Compare: an algorithm for Path Matching between two DAGs.
The function Prev returns the node that given edge leaving, InEdges returns the set
of edges that coming into a given node, Nodes returns the nodes associated with a
DAG
o
,
the
function
TopologicalSort
returns
an
topologically
ordered
list
of nodes
from a given DAG and MatchEdge is the function defined in Section 5..
6. RECURSIVE STRUCTURE OF DAGS
The DAGs and the DAG-compare operation are a divide and conquer
method that creates a recursive system architecture. When used recur-
sively to extract the edge value in a DAG-Coding, a DAG-Coder and its
DAG-Compare operation can be considered as the inductive step within
a recognition system architecture. Although DAG-Coded representation
varies at each level of recursion, DAGos and their DAG-Compare oper-
Search WWH ::
Custom Search