In maximizing 
under the feasibility and unambiguity constraints,
an RL algorithm iteratively updates p based on the gradient 
. The gradient components are
given by
for symmetric 
. Let 
represent the labeling
state at time t.
The initial assignment is set to 
.
A current 
is updated into a new state 
based on the
information in 
and 
where 
is an updating operator. RL algorithms differ from one
another in the choice of 
. Various update equations are described
in the following.
Rosenfeld et al. (1976) propose to use the following fixed-point iteration
Obviously, the feasibility constraints (8.19) are
satisfied by the normalization. The above iteration equation is only
one of many choices. For example, when the compatibility coefficients
are non-negative, we have 
; in this case, the
following updating scheme also maintains the feasibility while
performing gradient ascent
In the continuous RL algorithms by [Faugeras and Berthod 1981] and
[Hummel and Zucker 1983], the feasibility is maintained using a technique
called gradient projection (GP) [Rosen 1960]. GP is an extended
steepest descent procedure for solving programming problems under linear
constraints. It finds a feasible direction u, from the gradient q
and the current 
, for the following updating scheme
where 
is a scalar factor. The vector
must satisfy the condition
in order to maintain the feasibility constraints. If 
,
then there must be 
so that 
would not be
negative. For convenience, a normalization of u may be imposed so that
. Then, the feasible space for u is defined by
The maximum value for 
is chosen so that the updated vector
still lies in the space 
. A detailed implementation
of such a projection operator used in [Hummel and Zucker 1983] is
described in [Mohammed et al. 1983]. A discussion on parallel distributed
implementation of the Hummel-Zucker algorithm in multiprocessor
architecture environment is given in [McMillin and Ni 1989].
