8.2.4
Dynamic programming (DP) [Bellman and Dreyfuss 1962] is an optimization technique for problems where not all variables (labels in MRFs) are interrelated simultaneously. This is useful for the computation of MRFs because contextual constraints therein, causal or non-causal, are localized. The technique is based on the principle of optimality. Bellman states it as follows: ``An optimal policy has the property that whatever the initial state and the initial decision are, the remaining decisions must constitute an optimal policy with regards to the state resulting from the first decision.''
Suppose that the global energy can be decomposed into the following form
DP generates a sequence of functions of one variable
The first function is obtained as follows: for each 
value, choose
the minimum of 
over all 
values. The sequence can be
written in the recursive form: for 
,
with 
. The minimal energy solution is
obtained by
This is a valid formula if the problem can really be decomposed into the form of (8.42).
With regards the validity, we have the following relationship
If the equality holds, it means the DP algorithm gives the true minimum
of E. The condition for the equality to hold is that 
is
independent of 
. If this is not true, then the DP solution is not a
global one. This conclusion can be generalized to situations with more
variables.
If each 
takes on M discrete values in 
, then to compute
for each 
value, one must evaluate the minimand
for the M different
values in order to determine the minimal value of the minimand.
Therefore, the overall minimization involves 
evaluations of
the minimands. This is an enormous reduction from the exhaustive
minimization; for the latter case, 
evaluations of
have to be made where 
denotes the number
of elements in the set.
Applications of DP in vision include curve detection [Ballard and Brown 1982], matching [Fischler and Elschlager 1973], energy minimization for MRF-based image segmentation [Derin and Elliot 1987] and for active contours [Amini et al. 1990]. The Derin-Elliot algorithm is described below.
The algorithm is designed for the MLL region model with
additive white Gaussian noise. The MRF is defined on an image lattice
. Each true label 
takes a
value in 
. The posterior energy is
expressed as
where 
are the MLL clique potentials on the 8-neighborhood system
given in Fig.1.4, 
is the set of sites whose labels take the value
and 
is the noise variance. Similar to
(8.42), a decomposition of energy is done as
where 
denotes the k-th row. Function 
concerns only the two rows,
where
In this decomposed form, 
can be minimized using the DP technique
just described. Because (8.49) is a valid
formula for the MLL model on the 8-neighborhood system, the DP solution
should give exact MAP estimate.
When the observation model is due to textures, the likelihood function cannot be decomposed into independent terms for the application of DP. Derin and Elliott (1987) made some assumptions to simplify the involved conditional probabilities before applying the DP algorithm. This gives sub-optimal solution.
