3.2.1
We focus on the models which involve only the first order derivative
and consider the general string model
where
Solutions 
minimizing 
must satisfy the following
associated Euler-Lagrange differential equation or simply the Euler
equation [Courant and Hilbert 1953]
with the boundary conditions
where 
and 
are prescribed constants. In the following
discussion of solutions to the differential equation, the following
assumptions are made: Both 
and 
are continuous and
is continuously differentiable ( In this work, the continuity of x(x) and d(x) and differentiability of f(x) are assumed for the variational problems defined on continuous domains [Courant and Hilbert 1953 ;Cesari 1983]. However, they are not necessary for discrete problems where [a,b] is quantized into discrete points. for example, in the discrete case, 
is available or not.). Writing the Euler equation out yields
A potential function g is usually chosen to be (a) even such that
and (b) the derivative of g can be expressed as
the following form
where h is called an interaction function. Obviously, h thus defined is also even. With these assumptions, the Euler equation can be expressed as
The magnitude 
relates to the
strength with which a regularizer performs smoothing; and 
determines the interaction between neighboring pixels.
Let 
. A necessary condition for any
regularization model to be adaptive to discontinuities is
where 
is a constant. The above condition with C=0
entirely prohibits smoothing at discontinuities where 
whereas with C>0 allows limited (bounded) smoothing. In any case,
however, the interaction 
must be small for large 
and
approaches 0 as 
goes to 
. This is an important
guideline for selecting g and h for the purpose of the adaptation.
Definition 1. An adaptive interaction function (AIF)
parameterized by 
is a function that
satisfies:
The class of AIFs, denoted by 
, is defined as the
collection of all such 
. 
The continuity requirement (i) guarantees the twice differentiability
of the integrand 
in (3.20) with respect
to 
, a condition for the solution f to exist
[Courant and Hilbert 1953]. However, this can be relaxed to
for discrete problems. The evenness of (ii) is
usually assumed for spatially unbiased smoothing. The positive
definiteness of (iii) keeps the interaction positive such that the sign
of 
will not be altered by 
. The
monotony of (iv) leads to decreasing interaction as the magnitude of the
derivative increases. The bounded asymptote property of (v) provides
the adaptive discontinuity control as stated earlier. Other properties
follow:
, \
and
, the last meaning zero
interaction at discontinuities.
The above definition characterizes the properties AIFs should possess
rather than instantiates some particular functions. Therefore, the
following definition of the DA model is rather broad.
Definition 2.
The DA solution f is defined by the Euler equation (3.25) constrained by
. 
The DA solution is 
continuous (See [Cesari 1983] for a comprehensive discussion about th econtinuity of solutions of the class of problems to which the DA belongs). Therefore the DA solution
and its derivative never have discontinuities in them. The DA overcomes
oversmoothing by allowing its solution to be steep, but 
continuous, at point x where data 
is steep. With every possible
data configuration d, every 
is possible.
There are two reasons for defining the DA in terms of the constrained
Euler equation: First, it captures the essence of the DA problem; the DA
model should be defined based on the 
therein. Second, some
satisfying 
may not have their corresponding 
(and
hence the energy) in closed-form, where 
is defined below.
Definition 3. The adaptive potential function (APF)
corresponding to an 
is defined by
The energy function (3.19) with 
is called an
adaptive string. The following are some properties of 
:
Basically, 
is one order higher than 
in
continuity; it is even, 
; its derivative
function is odd, 
; however, it is not
necessary for 
to be bounded. Furthermore, 
is strictly monotonically increasing as 
increases because
and 
for 
. This means larger 
leads to
larger penalty 
. It conforms to the original spirit of
the standard quadratic regularizers determined by 
. The line
process potential function 
does not have such a property: Its
penalty is fixed and does not increase as 
increases beyond
. The idea that large values of 
are equally
penalized is questionable [Shulman and Herve 1989].
In practice, it is not always necessary to know the explicit definition
of 
. The most important factors are the Euler equation and the
constraining function 
. Nonetheless, knowing 
is
helpful for analyzing the convexity of 
.
For a given 
, there exists a region of 
within
which the smoothing strength 
increases monotonically as 
increases and the
function 
is convex:
The region 
is referred to as the band of convexity.
because 
is convex in this region.
The lower and upper bounds 
correspond to the two extrema of
, which can be obtained by solving 
, and we have 
when g is even. When
, 
and thus 
is
strictly convex. For 
defined with C>0, the bounds are
and 
.
Table 3.1: Four choices of AIFs, the corresponding APFs and bands.
Figure 3.1: The qualitative shapes of the four DA functions.
From (Li 1995b) with permission; © 1995 IEEE.
Table 3.2.1 instantiates four possible choices of AIFs, the
corresponding APFs and the bands. Fig.3.1 shows their
qualitative shapes (a trivial constant may be added to
). Fig.3.2 gives a graphical comparison of
the 
's for the quadratic, the LP model and the first three DA
models listed in Table 3.2.1 and their derivatives,
.
The fourth AIF, 
allows bounded
but non-zero smoothing at discontinuities: 
. It is interesting because 
for all 
(except at 
) and leads to strictly convex minimization. In fact,
a positive number C in (3.27) leads to a convex AIF and
hence energy function (This is due to the following theorem: If 
, a real-valued energy function 
is convex w.r.t f for all 
and fixed 
.).
The convex subset of models for discontinuity adaptivity and M
estimation is appealing because they have some inherent advantages over
nonconvex models, both in stability and computational efficiency. A
discussion on convex models will be given in
Section 4.1.5; see also [Li et al. 1995].
Figure 3.2: Comparison of different potential functions 
(top)
and their first derivatives 
(bottom).
From (Li 1995b) with permission; © 1995 IEEE.
Fig.3.2 also helps us visualize how the DA performs
smoothing. Like the quadratic 
, the DA allows
the smoothing strength 
to increase monotonically
as 
increases within the band 
. Outside the band, the
smoothing decreases as 
increases and becomes zero as 
. This differs from the quadratic regularizer which allows
boundless smoothing when 
. Also unlike the LP model
which shuts down smoothing abruptly just beyond its band 
, the DA decreases smoothing
continuously towards zero.
