The LP model assumes piecewise smoothness whereby the smoothness
constraint is switched off at points where the magnitude of the
signal derivative exceeds certain threshold. It is defined on a lattice
rather than on a continuous domain. Quantize the continuous interval
into m uniformly spaced points 
so that 
, 
and 
. Introduce a set of
binary line process variables 
into the smoothness
term. If 
in (3.5) also takes on a
value in 
, then 
is related it by 
. The
on-state, 
, of the line process variable indicates that a
discontinuity is detected between neighboring points i-1 and i; the
off-state, 
, indicates that the signal between the two points is
continuous. Each turn-on of a line process variable is penalized by a
quantity 
. These give the LP regularizer
The energy for the LP model is
This is the weak string model and its extension to 2D the weak membrane model [Blake and Zisserman 1987]. Eq.(3.7) corresponds to the energy in the posterior distribution of the surface field f and the line process field l, the distribution being of the Gibbs form
where Z is a normalizing constant called the partition function.
The line process variables are determined as follows: If 
, then it is cheaper to pay the price 
and set 
; otherwise it is more economical to turn
on the variable 
to insert a discontinuity with the cost of
. This is an interpretation of the LP model based on the
concept of the weak continuity constraint introduced by Blake
[Blake 1983] for edge labeling. An earlier idea of weak constraints
is seen in Hinton's thesis work [Hinton 1978]. In the LP
model, the interaction is piecewise constant (1 or 0) and the
smoothing strength at i is either proportional to 
or zero -- see the next section. The concept of discontinuities can be
extended to model-based recognition of overlapping objects
[Li 1994a]. There, the relational bond between any two
features in the scene should be broken if the features are ascribed to
two different objects.
Finding 
and 
such that 
is minimized is a mixture of real and combinatorial optimization.
Algorithms for this can be classified as categories: stochastic
[Geman and Geman 1984 ; Marroquin 1985] and deterministic
[Koch et al. 1986 ; Yuille 1987 ; Blake and Zisserman 1987 ; Geiger and Girosi 1991]. Some annealing
techniques are often combined into them to obtain global solutions.
In stochastic approaches, f and l are updated according to some probability distribution parameterized by a temperature parameter. For example, Geman and Geman propose to use simulated annealing with the Gibbs sampler [Geman and Geman 1984] to find the global MAP solution. Marroquin (1985) minimizes the energy by a stochastic update in l together with a deterministic update in f using gradient descent.
Deterministic approaches often use some classical gradient based methods. Before these can be applied, the combinatorial minimization problem has to be converted into one of real minimization. By eliminating the line process, Blake and Zisserman (1987) convert the previous minimization problem into one which minimizes the following function containing only real variables
where the truncated quadratic potential function ( cf.
Equ.(2.17))
shall be referred to as the line process potential function.
Blake and Zisserman introduce a
parameter p into 
to control the convexity of E,
obtaining 
. The parameter p varies from 1 to
0, which corresponds to the variation from a convex approximation of the
function to its original form.
Koch et al.
(1986) and Yuille (1987)
perform the conversion using the Hopfield approach [Hopfield 1984].
Continuous variables 
in the range
are introduced to replace the binary line process variables
in 
. Each 
is related to an internal variable
by a sigmoid function
with 
as the parameter whereby 
.
The energy with this treatment is
It is shown that at stationary points where 
, there are
and hence the approximated
line process variables [Yuille 1987]
This gives the effective potential function as
As the temperature decreases toward zero, 
approaches 
:
.
Geiger and Girosi (1991) approximate the line
process using mean field theory. They
introduce a parameter 
into (3.8), giving an
approximated posterior probability
Using the saddle point approximation
method, they derive mean field equations which yield the approximated
line process variables which are identical to (3.13). The
solution is in the limit
.
Li (1990) proposes a continuous adaptive regularizer model. There, the smoothness constraint is applied without the switch-off as the LP model. Its effect is decreased as the derivative magnitude becomes larger and is completely off only at the true discontinuities where the derivative is infinite. This is an earlier form of the DA model in this work.
