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

Viterbi Algorithm for the Shortest Path on a Trellis

The Viterbi algorithm finds the shortest path on a trellis rather than on a
network. A trellis can be derived from a network by associating a state with
each node of the network and then representing the set of states vertically
as a column. This column of states is then replicated horizontally to indicate
increasing increments of time or equivalently transitions or “hops” between
states. Connecting lines are used to show the allowable state transitions and
possible paths. Note that self-transitions are often permissible on a trellis and
may incur non-zero cost.

Fig. 9.10. Shortest path problem in a trellis.

Figure 9.9 shows the paths available through an air transportation network
between a set of cities represented by a trellis. Each flight from city to city
would be just one leg of an overall itinerary ( cf path) and a self-transition
could be a flight returning to the city of departure. In the above example,
we show direct flights between all cities, but that is not always the case in
a general air transportation network. If there were no direct flights between
two particular cities, a common problem is finding the cheapest itinerary
requiring just N stopovers. This is a problem that can be rapidly solved using
the Viterbi algorithm as follows.
Consider the trellis illustrated in Figure 9.10 with M = 4 states and
length N = 4 hops. We examine paths from the starting node 4

ν 0 in state

x i ∈ [ x 0 ..x M− 1 ]on

the right. Let the distance measure d ( i, j, k ) denote the cost of transitioning
from state x i in node ν k to state x j in node ν k +1 .

[ x 0 ..x M− 1 ] reaching a terminating node ν N− 1 in state x j ∈

4 Here we use the word “node” to refer to a junction in the trellis that corresponds
to a particular state at a particular hop count.