Digital Signal Processing Reference
In-Depth Information
Figure 5.9.
Valid Orders of Computation
can be finished before traversing another pair of edges. In fact, there
are many orders of solving the subproblems that preserve these depen-
dencies (See Figure 5.8b and 5.9). Since both graphs are DAGs, we can
topologically sort [Cormen et al., 1990] the nodes in each graph such
that all edges leave from one node and lead to another of higher order.
Thus, a subproblem is only dependent on other subproblems that are
contained within the rectangular area between the problem and the ori-
gin. Graphically speaking, the inductive process of solving subproblems
can be pictorially viewed as growing an area along the axes such that
any point to be added to the area is supported both horizontally and
vertically from each axis.
If we calculate the subproblems in an order as described in the pre-
vious paragraph, we find the maximum PathScore of all paths encoded
between two DAGs with MatchEdge as defined in Eq. 5.2. To find
the correspondence between edges of the two DAGs actual paths, we
keep track of which optimal solutions were used in optimal final solu-
tion and follow its predecessors from the final solution at to the initial
solution. The pseudocode for this algorithm is shown in Figure 5.10. If
MatchEdge is an O(1)
operation, the running time of our algorithm is:
O
((|
V
1
| + |
E
1
|)(|
V
2
| + |
E
2
|)) (5.6)
where (
V
1
,
E
1
) and (
V
2
,
E
2
) are the sets of nodes and edges of the two
DAG
o
s to be compared.
APPLICATION: CURSIVE HANDWRITING
LETTER RECOGNITION
In our own work, we have applied complex partitioning and DAG-
Coded representations to the recognition of on-line cursive handwriting
letter recognition [Lin and Kung, 1997a]. Using loops and curved line
segments as our macro-structures, we implemented a cursive handwriting
letter recognizer.
Search WWH ::
Custom Search