Graphics Reference
In-Depth Information
each energy evaluation takes just 1 microsecond, the exhaustive minimization
would require almost 7
10 30 years—much, much longer than the age of the
universe. Yet with the Viterbi algorithm we can calculate the exact same min-
imal value in just O ( Nm ) time, which is equivalent to just 900 evaluations,
or barely one millisecond!
The Viterbi algorithm is therefore deservedly referred to as a fast algo-
rithm. Along with the more famous family of Fast Fourier Transform algo-
rithms, it is one of the classic fast algorithms of digital signal processing
[28]. The inventor of the algorithm, Andrew Viterbi, was a co-founder of
Qualcomm, a wireless telecommunications research and development company
based in San Diego, California. The algorithm still finds wide application in
communications including the widely-used V32 and V90 telephone modem
standards. It is instrumental in decoding highly ecient trellis and convo-
lutional codes for high-speed data communication. The algorithm also finds
application in pattern recognition, where it forms the basis of the forward and
backward algorithms for learning and recognition via hidden Markov models
for speech and gesture recognition [138].
Returning to the problem at hand, the Viterbi algorithm is used to e-
ciently calculate the optimal configuration of the snake, which minimizes total
energy. This is possible because of the decoupled form of the discrete internal
energy function of (9.5). We observe that the internal energy of each control
point is only dependent on the points immediately preceding and following it.
So the total energy of the snake can be written in the form:
×
E snake = E 1 ( ν 0 1 3 )+ E 2 ( ν 1 2 3 )+ ... + E N− 2 ( ν N− 3 N− 2 N− 1 ) .
(9.11)
Dynamic Programming and the Principle of Optimality
Dynamic programming in general can be applied to any problem that observes
the Principle of Optimality . Bellman [19], the inventor of dynamic program-
ming, states:
An optimal policy has the property that, whatever the initial state
and optimal first decision may be, the remaining decisions constitute
an optimal policy with regard to the state resulting from the first
decision.
If a problem observes the Principle of Optimality it means that optimal solu-
tions of subproblems can be used to find the optimal solutions to the overall
problem.
In the case of the shortest (or equivalently minimum energy) path prob-
lem in a network as addressed by Dijkstra's algorithm [59], this means that all
subpaths A to B, say, of the shortest path from A to Z, must themselves be
shortest paths. In order to explain this seemingly obvious but very powerful
Search WWH ::




Custom Search