Snakes and Active Contours - Bezier and Splines in Image Processing and Machine Vision - page 195

Now the cost of a path on the trellis is simply the sum of the costs along
the path. For example, the cost of traveling from ν 0 to ν 3 along the illustrated
path in Figure 9.11 is given by
Total Cost = d (2 , 1 , 0) + d (1 , 2 , 1) + d (2 , 3 , 2) .
Now we wish to determine the shortest path between two nodes on the trellis.
The possible number of paths in a fully-connected 5 trellis equals M N which
can be an enormous number—exhaustive evaluation of all possible paths is out
of the question. The trick that makes the Viterbi algorithm so incredibly fast
is again due to the Principle of Optimality. This tells us that if we maintain
the shortest path to each of the M states as we progress through the trellis,
we can find the overall shortest path by recursively extending these M paths.
Thus the computational load is linear with respect to the length of the trellis,
O ( MN ), rather than exponential, O ( M N ). As for Dijkstra's algorithm, we
maintain a list of backward pointers so that we can eventually recover the
shortest paths.
The pseudocode for the complete Viterbi algorithm is shown in Figure
9.12. The algorithm progresses along the trellis one hop at a time maintaining
a record of the shortest path to each destination node from the starting node.
After a hop, the algorithm extends the shortest paths to the previous set
of destination nodes in all directions to find the shortest paths to each of
the current set of destination nodes, and then it hops again. However, unlike
Dijkstra's algorithm, which can extend known paths in any direction, the
Viterbi algorithm marches through the trellis column by column updating
the paths. If it was useful to visualize the evolution of Dijkstra's algorithm
as an expanding wavefront, perhaps the Viterbi algorithm is more akin to an
electromagnetic wave traveling down a waveguide.
Note that in the Viterbi algorithm pseudocode of Figure 9.12, we have
chosen to initialize the algorithm with the distance to the starting node set
to 0 and the distance to all other nodes set to infinity ( i.e., unreachable) to
force all paths to start at the starting node. Nevertheless, there are situations
where we may not know the best starting node or we may have a choice of
several starting nodes. In these cases, we could initialize the distances to all
possible starting nodes to 0 and the Viterbi algorithm would then calculate the
shortest path to the best choice from the set of starting nodes. If we follow the
backward pointers back from the destination node, we can determine which
of the stating nodes was actually chosen for the particular shortest path at
hand.
Following the same reasoning, when the Viterbi algorithm is used with
discrete hidden Markov models (HMMs) [138] for, say, speech recognition, it
is common practice to assign a particular probability to each of the starting
states based on a priori knowledge. Indeed, when used with HMMs, the costs
of transitioning between the states are actually state transition probabilities
5 For example, where a state can transition to any other state.