Francoise J.-P., Naber G.L., Tsun T.S. (editors) Encyclopedia of Mathematical Physics

Подождите немного. Документ загружается.

sequence of symbols, namely ( ..., a

1

, a

, ...),

where a

2 {1, 2, ..., k} is the name of the partition

element containing f

(x), that is, f

(x) 2 R

for

each i. In general, not all sequences are realized by

orbits of f. Markov partitions are designed so that

the set of symbol sequences that correspond to real

orbits has Markovian properties; it is called a shift of

finite type.

The ergodic theory of Axiom-A systems has its

origins in statistical mechanics. In a 1D lattice model in

statistical mechanics, one has an infinite array of sites

indexed by the integers; at each site, the system can be

in any one of a finite number of states. Thus, the

configuration space for a 1D lattice model is the set of

bi-infinite sequences on a finite alphabet. Identifying

this symbol space with the one coming from Markov

partitions, Sinai and Ruelle were able to transport

some of the basic ideas from statistical mechanics,

including the notions of Gibbs states and equilibrium

states, to the ergodic theory of Axiom-A systems.

The notion of equilibrium states, which is

equivalent to Gibbs states for Axiom-A systems,

has the following meaning in dynamical systems in

general: given a potential funct ion ’, an invariant

measure is said to be an equilibrium state if it

maximizes the quantity



ðf Þ

’d

where h



(f ) denotes the Kolmogorov–Sinai entropy of

f and the supremum is taken over all f-invariant

probability measures . In particular, when ’ = 0, this

measure is the measure that maximizes entropy; and

when ’ = log jdet (df j

)j, it is the Sinai–Ruelle–

Bowen (SRB) measure. From the physical or observa-

tional point of view, SRB measures are the most

important invariant measures for dissipative dynami-

cal systems because if f is a diffeomorphism of a

compact manifold M and  a transitive Axiom-A

attractor with basin U, for example, =U = M,then

for Lebesgue-a.e. x 2 U and for every ’ 2 C

(M)

lim

n!1

n1

i¼0

’ðf

ðxÞÞ ¼

’d

that is, Lebesgue-a.e. point is -typical. Thus, while

Axiom-A attractors will have chaotic motions, they are

statistically coherent in that the asymptotic distribution

of any typical orbit is given by the SRB measure.

Periodic Points and Their

Growth Properties

We discuss briefly some further results related to the

abundance of periodic points in Axiom-A systems.

For an Axiom-A diffeomorphism f,ifP(n) is the

number of periodic points of period n, then P(n) 

, where h is the topological entropy of f. That is

to say, the dynamical complexity of f is reflected in

its periodic behavior. An analogous result holds for

Axiom-A flows. This asymptotic behavior is known

to remarkably fine accuracy (Margulis 2004), and

these developments used the dynamical zeta func-

tion, which sums up the periodic information of a

system. In the discrete-time case, (z):= exp

n = 1

P(n)z

=n has been shown to be a rational function

analytic on jzj < e

h

. In the continuous-time case,

the zeta function is given by (z):=



(1  exp(zl()))

1

, where the product is taken

over all (nonstationary) periodic orbits  and l()

is the smallest positive period of . This function is

known to be meromorphic on a certain domain,

but the location of its poles, which are intimately

related to correlation decay properties of the

system, remains one of the yet unresolved issues in

Axiom-A theory.

Partial Hyperbolicity and

Dominated Splitting

There are various ways in which the notion of

hyperbolicity described above, which we will hence-

forth refer to as ‘‘uniform hyperbolicity,’’ can be

extended beyond the one presented so far. This can

be done with a view to weakening the conditions

under which some of the salient properties of

hyperbolic dynamical systems appear. The study of

partially hyperbolic dynamical systems and that

of dynamical systems possessing a dominated split-

ting is of this type. Further below, we describe a

different extension motivated more by a desire to

bring the results and methods of hyperbolic

dynamics to bear on systems that are closer to

some physical situations. This led to the study of

nonuniformly hyperbolic dynamical systems.

If one views hyperbolicity as requiring that the

spectrum of expansion and contraction rate s is

separated into two components by the unit circle,

then one can consider systems where this separati on

is provided by a circle centered at 0 whose radius

may not be 1 (partial hyperbolicity in the broad

sense), or by two circles centered at 0 of which one

has radius less than 1 and the other has radius

greater than 1, with possibly a third component of

the spectrum in the annulus between these (absolute

partial hyperbolicity). Further weakenings are

obtained by controlling not the whole spectrum in

this absolute way, but rather ratios of expansion and

contraction rates along orbits (dominated splitting

726 Hyperbolic Dynamical Systems

and relative partial hyperbolicity, respectively).

Among the motivations for these weakenings are

the desire to understand which systems are topolo-

gically transitive and robustly so (stable transitivity),

and to understand which ergodic volume-preserving

systems remain ergodic if perturbed within the space

of volume-preserving systems (stable ergodicity).

Pseudohyperbolicity

Let f be a smooth inver tible map. A compact

invariant set of f is said to be partially hyperbolic

in the broad sense if at every point in this set, the

tangent space splits into a direct sum of two

subspaces E

and E

with the property that these

subspaces are invariant under the differential df ,

that is, df (x)E

(x) = E

(f (x)), df (x)E

(x) = E

(f (x)),

and that there are con stants 0 <<, c > 0 such

that if v 2 E

(x) for some x then kdf

vkc

kvk

for n = 1, 2, ... and if v 2 E

(x) for some x

then kdf

n

vkc

n

kvk for n = 1, 2, .... This is

sometimes also referred to as the existence of a

(, )-splitting or pseudohyperbolicity.

Dominated Splitting

A further weakening of this condition replaces these

absolute estimates by relative ones. Let f be a

smooth invertible map. A compact invariant set of

f is said to admit a dominated splitting if at every

point in this set, the tangent space splits into a direct

sum of two subspaces E

and E

with the property

that these subspaces are invariant under the differ-

ential and there are constants  2 (0, 1), c > 0 such

that if u 2 E

(x)andv 2 E

(x) for some x then

kdf

vk=kdf

ukc

for n = 1, 2, ....

The presence of a dominated splitting has been

found to yield substantial information pertinent to

stability of such systems, and it plays a significant

role in a program of research aiming at a classifica-

tion of generic diffeomorphisms up to topological

conjugacy and specifically motivated by the ‘‘Palis

conjecture,’’ which aim s to describe that classifica-

tion. With respect to inferring topological and

ergodic (i.e., statistical) properties of the orbit

structure, the stricter notion of partial hyperbolicity

(in the narrow sense below) is more commo nly used,

but in this respect the presence of a dominated

splitting is also of interest because there is evidence

in supp ort of the conjecture that stable ergodicity

implies the presence of a dominated splitting.

Partial Hyperbolicity

Let f be a smooth inver tible map. A compact

invariant set of f is said to be (absolutely) partially

hyperbolic if at every point in this set, the tangent

space splits into a direct sum of unstable, central,

and stable directions E

, E

, and E

with the

property that these subspaces are invariant under

the differential df and that there exist numbers

C > 0,

0 <

 

<

 

<

 

with 

< 1 <

½1

such that if v 2 E

(x), w 2 E

(x), u 2 E

(x),

n = 1, 2, ..., then

1



kvkkd

ðvÞk  C

kvk

1



kwkkd

ðwÞk  C

kwk

1



kukkd

ðuÞk  C

kuk

In this case, we set E

:= E

 E

and E

:= E

 E

Following Burns–Wilkinson, we say that f is ‘‘center-

bunched’’ if max {

, 

1

} <

=

As in the case of (uniformly) hyperbolic dynami-

cal systems, the sub-bundles E

and E

are integrable

to stable and unstable foliations W

and W

.Itis

not automatic that the center-stable sub-bundle E

and the center-unstable sub-bundle E

are tangent

to foliations W

and W

; if this happens to be the

case, the partially hyperbolic system is said to be

‘‘dynamically coherent.’’

Partial hyperbolicity can also be defined by a cone

criterion, with suitable adaptations.

Stable Ergodicity and Transitivity

Partial hyperbolicity was introduced as a means of

providing just enough hyperbolicity to render a

dynamical system ergodic or topologically transitive.

These are both irreducibility conditions, and to

obtain these, one rules out a Cartesian product

situation by assuming somethi ng like essential

accessibility: almost every two points (in the sense

of volume viewed as a measure) can be connected by

a curve consisting of a finite concatenation of arcs,

each of which lies entirely in one stable or unstable

leaf. A celebrated result in this field is in its original

form (with a much stronger center-bunching

assumption) due to Pugh and Shub: suppose a

volume-preserving diffeomorphism is partially

hyperbolic on the entire manifold. If it is dynami-

cally coherent and center bunched and has essential

accessibility, then it is ergodic (Hasselblatt and Pesin

2006).

One of the motivating aims of this theory was to

obtain nonhyperbolic volume-preserving systems

that are stably ergodic, that is, for which all

volume-preserving C

-small perturbations are also

ergodic. If, in addition to the above, one assumes

that essential accessibility also persists under such

Hyperbolic Dynamical Systems 727

perturbations and that the center bundle E

integrable to a center foliation W

that is smooth

(or ‘‘plaque-expansive’’), then ergodicity is indeed

stable (Hasselblatt and Pesin). There are quite a few

natural examples where these assumptions hold.

While essential accessibility does not always hold,

it is fairly common. The stronger property of

accessibility (that any two points can be connected,

not only almost every two points) is conjectured to

be stable under C

-perturbations and has been

shown to hold for an open dense set of partially

hyperbolic systems with respect to the C

-topology.

Ergodicity is a measure-theoretic irreducibility

notion, and topological transitivity is the topological

counterpart. It can also be obtained from accessi-

bility: a partially hyperbolic volume-preserving

diffeomorphism with the accessibility property is

topologically transitive (in fact, almost every orbit is

dense).

There are interesting converse results as well. Any

stably transitive diffeomorphism exhibits a domi-

nated splitting. Moreover, in dimension 2 it is

hyperbolic and in dimension 3 it is partially

hyperbolic in the broad sense.

Nonuniform Hyperbolicity

Applications have motivated weakening assump-

tions of uniform hyperbolicity to require only that

‘‘many’’ individual orbits exhibi t hyperbolic beha-

vior, without assuming that there are any uniform

estimates on the degree of hyperbolicity.

To measure the asymptotic contraction or expan-

sion of a vector on an exponential scale, one defines

the Lyapunov exponent of a (nonzero) tangent

vector v at x for the map f to be

ðx; vÞ:¼ lim

n!1

ð1=nÞlog kDf

ðvÞk ½2

whenever this limit exists. Note that being positive

indicates asymptotic expansion of the vector,

whereas negative exponents correspond to contract-

ing vectors. This defines a measurable but, save for

exceptional circumstances, discontinuous function

of x and v. It is relatively easy to see that for a given

point x the function (x,  ) can only take finitely

many values, so it is natural to define nonuniform

hyperbolicity as the property of having all of these

finitely many values nonzero for ‘‘most’’ points.

Given that  is measurable, it is natural to define

‘‘most’’ by using a measure that is invariant under

the map f. Therefore, the theory of nonuniformly

hyperbolic dynamical systems , much of which is due

to Pesin, is based on measure theory throughout.

The fundamental fact on which this theory is

based is the ‘‘Oseledets multi plicative ergodic theo-

rem,’’ which says that for a C

-diffeomorphism of a

compact Riem annian manifold the set of Lyapunov-

regular points has full measure with respect to any

f-invariant Borel probability measure.

For a Lyapunov-regular point the limit [2] exists

for all v, so this theorem tells us that no matter

which invariant measure we consider, the limit [2]

makes sense for all tangent vectors at points x

outside a null set. (One should add that this small

‘‘bad’’ set can be somewhat substantial; for example,

its Hausdorff dimension is usually that of the whole

space.)

Accordingly, one then defines a measure to be

hyperbolic if at almost every point the limit [2] is

nonzero for all vectors. In this case, one says that

‘‘f has nonzero Lyapunov exponents.’’ This property

can also be obtained from a cone criterion, but here

the fam ily of cones may only be invariant and

eventually strictly invariant, that is, there is a cone

field such that cones are mapped to cones (but not

necessarily into the interior of cones), and for almost

every point there is an iterate that maps a cone

strictly inside the cone at the image point (i.e., into

the interior). Which iterate is needed is allowed to

depend on the point (see Hyperbolic Billiards).

It is good to keep in mind that a hyperbolic

measure may be concentrated on a single point, say,

in which case there is not much gained by this

approach. The theory is of great interest, however, if

the measure is equivalent to volume or is the

‘‘physical measure’’ on an attractor.

Examples of this sort are fairly common, indeed

any smooth compact Riemannian manifold other

than the unit circle admits a volume-preserving

Bernoulli diffeomorphism with nonzero Lyapunov

exponents (Dolgopyat and Pesin 2002) (and every

compact smooth Riemannian manifold of dimension

at least 3 carries a volume-preserving Bernoulli flow

for which at almost every point the only zero

Lyapunov exponent is the one in the flow direction

(Hu et al. 2004)).

Structurally, these systems exhibit many of the

features seen in uniformly hyperbolic ones (e.g.,

stable manifolds), but instead of being continuous

these are now measurable. There are, however,

(noninvariant) sets of arbitrarily large measure on

which these structures are continuous. This provides

a handle for pushing some of the uniform theory to

this context.

There are some topological results in this area, of

which one of the more remarkable ones is that any

surface diffeomorphism with positive entropy con-

tains a horseshoe. Much of the current research is

728 Hyperbolic Dynamical Systems

directed at the ergodic theory of these systems. A

central result from the initial development of the

theory is that while these systems may not be

ergodic, the ergodic components are (a.e. equal to)

open sets, so in particular there are at most

countably many of them.

One natural question is whether nonuniformly

hyperbolic systems have SRB measures, and it is

answered on a case-by-case basis. There are even

benign examples where this fails to be the case, but

for some realis tic systems, such as the Lorenz and

He´non attractors, this has been established.

Because they preserve volume, this is not an issue

for billiard systems, (see Hyperbolic Billiards), that

is, the free motion of a point mass in a cavity with

elastic boundary collisions. This describes not just a

toy model, but also the phase space and dynamics of

a gas of convex rigid bodies. Such a gas of hard

spheres in a rectangular box is semidispersing and

has been studied intensely. It is now known to be

hyperbolic and hoped to be ergodic. (The latter

would provide a solid foundation for statistical

mechanics, at least for the case of spherical

molecules.) A gas of nonspherical convex rigid

bodies is also a point billiard, but it is not

semidispersing, which puts it beyond the range of

readily available techniques for establishing

ergodicity.

Further Remarks

The historical remarks made here are significantly

expanded in Hasselblatt (2002), which contains

some references to yet more detailed sources as

well as more detail about uniformly hyperbolic

dynamical systems in a concise form. A concise but

reasonably comprehensive and current account of

partially hyperbolic dynamics is in Hasselblatt and

Pesin, and an authoritative full presentation is in

Pesin (2004). A survey of nonuniformly hyperbolic

dynamics is given in Barreira and Pesin (2006), and

the definitive treatment is given by Barreira et al..A

textbook presentation of (not only) hyperbolic

dynamics is in Katok and Hasselblatt (1995) as

well as Hasselblatt and Katok (2003), and much

current research, including on all subjects discussed

here, is surveyed in Handbook.

See also: Ergodic Theory; Fractal Dimensions in

Dynamics; Generic Properties of Dynamical Systems;

Homoclinic Phenomena; Hyperbolic Billiards; Inviscid

Flows; Lyapunov Exponents and Strange Attractors;

Regularization for Dynamical Zeta Functions; Singularity

and Bifurcation Theory; Symmetry and Symmetry

Breaking in Dynamical Systems.

Further Reading

Barreira L, Katok A, and Pesin Y Smooth ergodic theory and

nonuniformly hyperbolic dynamics (in preparation).

Barreira L and Pesin Y (2006) Smooth ergodic theory and

nonuniformly hyperbolic dynamics. In: Hasselblatt B and

Katok A (eds.) Handbook of Dynamical Systems, vol. 1B,

pp. 57–263. Amsterdam: Elsevier.

Bowen R (1975) Equilibrium States and the Ergodic Theory of

Anosov Diffeomorphisms. Lecture Notes in Mathematics,

vol. 470. Berlin–New York: Springer.

Dolgopyat D and Pesin Y (2002) Every compact manifold carries

a completely hyperbolic diffeomorphism. Ergodic Theory and

Dynamical Systems 22(2): 409–435.

Hasselblatt B and Kotak A (eds.) (2002) Handbook of Dynamical

Systems, 1B: 2006, Hasselblatt B and Kotak A (eds.); 2: 2002,

Fiedler B (ed.); 3: in preparation, Broer H, Hasselblatt B, and

Takens F (eds.).

Hasselblatt B (2002) Hyperbolic dynamics. In: Hasselblatt B and

Katok A (eds.) Handbook of Dynamical Systems, vol. 1A,

pp. 239–319. Amsterdam: Elsevier.

Hasselblatt B and Katok A (2003) Dynamics: A First Course.

New York: Cambridge University Press.

Hasselblatt B and Katok A (2002) Principal structures. In:

Hasselblatt B and Katok A (eds.) Handbook of Dynamical

Systems, vol. 1A, pp. 1–203. Amsterdam: Elsevier.

Hasselblatt B and Pesin Y (2006) Partially hyperbolic dynamical

systems. In: Hasselblatt B and Kotak A (eds.) Handbook of

Dynamical Systems, vol. 1B, pp. 1–55. Amsterdam: Elsevier.

Hu H, Pesin Y, and Talitskaya A (2004) Every compact manifold

carries a hyperbolic Bernoulli flow. In: Brin M, Hasselblatt B,

and Pesin Y (eds.) Modern Dynamical Systems and Applica-

tions, pp. 347–358. Cambridge: Cambridge University Press.

Katok A and Hasselblatt B (1995) Introduction to the Modern

Theory of Dynamical Systems. New York: Cambridge

University Press.

Margulis G (2004) On some aspects of the theory of Anosov

systems. With a survey by Ricbard Sharp: Periodic orbits of

hyperbolic flows. Translated from the Russian by Valentina

Vladimirovna Szulikowska. Springer Monographs in Mathe-

matics. Berlin: Springer.

Pesin Y (2004) Lectures on Partial Hyperbolicity and Stable

Ergodicity. Zurich Lectures in Advanced Mathematics. Zu¨r-

ich: European Mathematical Society.

Smale S (1967) Differentiable dynamical systems. Bulletin of the

American Mathematical Society 73: 747–817.

Hyperbolic Dynamical Systems 729

Image Processing: Mathematics

G Aubert, Universite

de Nice Sophia Antipolis,

Nice, France

P Kornprobst, INRIA, Sophia Antipolis, France

Our society is often designated as being an ‘‘infor-

mation society.’’ It could also be defined as an

‘‘image society.’’ This is not only because image is a

powerful and widely used medium of communica-

tion, but also because it is an easy, compact, and

widespread way to represent the physical world. If

we think about it, it is indeed striking to realize just

how much images are omnipresent in our lives

through numerous applications such as medical and

satellite imaging, videosurveillance, cinema,

robotics, etc.

Many approaches have been developed to process

these digital images, and it is diffic ult to say which

one is more natural than the other. Image processing

has a long history. Maybe the oldest methods come

from 1D signa l proces sing techniques. They rely on

filter theory (linear or not), on spectral analysis, or

on some basic concepts of probability and statistics.

For an overview, we refer the interested reader to

the book by Gonzalez and Woods (1992).

In this article, some recent mathematical concepts

will be revisited and illustrated by the image

restoration problem, which is presented below. We

first discuss stochastic modeling which is widely

based on Markov random field theory and deals

directly with digital images. This is followed by a

discussion of variational approaches where the

general idea is to define some cost functions in a

continuous setting. Next we show how the scale

space theory is connected with partial differential

equations (PDEs). Finally, we present the wavelet

theory, which is inherited from signal processing

and relies on decomposition techniques.

Introduction

As in the real world, a digital image is composed of

a wide variety of structures. Figure 1 shows different

kinds of ‘‘textures,’’ progressive or sharp contours,

and fine objects. This gives an idea of the complex-

ity of finding an approach that allows to cope with

the different structures at the same time. It also

highlights the discrete nature of images which will

be handled differently dependi ng on the chosen

mathematical tools. For instance, PDEs based

approaches are written in a continu ous setting,

referring to analogous images, and once the exist-

ence and the uniqueness of the solution have been

proved, we need to discretize them in order to find a

numerical solution. On the contrary, stochastic

approaches will directly consider discrete images in

the modeling of the cost functions.

The Image Restoration Problem

It is well known that during formation, transmis-

sion, and recording processes images deteriorate.

Classically, this degradation is the result of two

phenomena. The first one is deterministic and is

related to the image acquisition modality, to possible

defects of the imaging system (e.g., blur created by

an incorrect lens adjustment or by motion). The

second phenomenon is random and corresponds to

the noise coming from any signal transmission. It

can also come from image quantization. It is

important to choose a degradation model as close

as possible to reality. The random noise is usually

modeled by a probabilistic distribution. In many

cases, a Gaussian distribution is assumed. However,

some applications require more specific ones, like

the gamma distribution for radar images (speckle

noise) or the Poisson distribution for tomography.

Unfortunately, it is usually impossible to identify the

kind of noise involved for a given real image.

A commonly used model is the following. Let

u :   R

!R be an original image describing a real

scene, and let f be the observed image of the same

scene (i.e., a degradation of u). We assume that

f ¼ Au þ  ½1

where  stands for a white additive Gaussian noise

and A is a linear operator representing the blur

(usually a convolution). Given f, the problem is

then to reconstruct u knowing [1]. This problem

is ill-posed, and we are able to carry out only an

approximation of u. In this article, we will focus on

the simplified model of pure denoising:

f ¼ u þ  ½2

The Probabilistic Approach

The Bayesian Framework

In this section, we show how the problem of pure

denoising, that is, recovering u from the equation

f = u þ  knowing only some statistical information

on  can be solved by using a probabilistic

approach. In this context, f, u, and  are considered

as random variables. The general idea for recovering

u is to maximize some prior probability. Most

models involve two parts: a prior model of possible

restored images u and a data model expressing

consistency with the observed data.



The prior model is given by a probability space

(

, p), where 

is the set of all values of u. The

model is specified by giving the probability p(u)

on all these values.



The data model is a larger probability space

(

u, f

, p), where 

u, f

is the set of all possible values

of u and all possible values of the observed image

f. This model is completed by giving the condi-

tional probability p(f =u)ofanyimagef given u,

resulting in the joint probabilities p(f , u) =

p(f =u)p(u). Implicitly, we assume that the spaces

(

)and(

u, f

) are finite although huge.

The next step is to use a Bayesian approach

introduced in image processing by Besag (1974)

and Geman and Geman (1984). The probabilities

p(u) and p(f=u) are supposed to be known and,

given an observed image f, we seek the image

u which maximizes the conditional a posteriori

probability p(u=f ) (MAP: Maximum A Posteriori).

Thanks to the Bayes’ rule, we have

pðu=f Þ¼

pðf =uÞ pðuÞ

pðf Þ

½3

Let us explain the meaning of the different terms

in [3]:



The term p(f =u) expresses the probability, the

likelihood, that an image u is realized in f. It also

quantifies the lack of total precision of the model

and the presence of noise.



The term p(u) expresses our incomplete a priori

information about the ideal image u (it is the

probability of the model, i.e., the propensity that

u be realized independently of the observation f ).



The term p(f ) which is the probability to observe f

is a constant and does not play any role when

maximizing the conditional probability p(u=f )

with respect to u.

Let us remark that the problem max

p(u=f )is

equivalent to min

E(u) = log p(f =u)  log p(u).

So Bayesian models lead to a minimization

process.

Then the main question is how to assign these

probabilities? The easiest probability to determine is

p(f =u). If the images u and f consist in a set of values

u = (u

i, j

), i, j = 1, N and f = (f

i, j

), i, j = 1, N, we sup-

pose the conditional independence of (f

i, j

) in any

pixel:

pðf =uÞ¼

i¼1

pðf

i;j

and if the restoration model is of the form f = u þ 

where  is a white Gaussian noise with variance 

then

pðf

i;j

Þ¼

ﬃﬃﬃﬃﬃﬃﬃﬃﬃ

2

exp 

ðf

i;j

 u

i;j

2

and

pðf =uÞ¼

ð2Þ

N=2

exp 

i;j

ðf

i;j

 u

i;j

2

Therefore, at this stage, the MAP reduces to

minimize

EðuÞ¼K



kf  uk

 log pðuÞ½4

where k.k stands for the Euclidean norm on R

and



is a constant. So, it remains now to assign a

probability law p(u). To do that, the most common

way is to use the theory of Markov random fields

(MRFs).

(a)

(b)

(c)

(d)

(e)

Figure 1 Digital image example. 1 the close-ups show

examples of low resolution, low contrasts, graduated shadings,

sharp transitions, and fine elements. (a) low resolution, (b) low

contrasts, (c) graduated shadings, (d) sharp transitions, and

(e) fine elements.

2 Image Processing: Mathematics

The Theory of Markov Random Fields

In this approach, an image is described as a finite set

S of sites corresponding to the pixels. For each site,

we associate a descriptor representing the state of

the site, for example, its gray level. In order to take

into account local interaction between sites, one

needs to endow S with a syst em of neighborhoods V.

Definition 1 For each site s, we define its neighbor-

hood V(s) as:

VðsÞ¼ftg such that s =2VðsÞ and t 2VðsÞ)s 2VðtÞ

Then we associate to this neighborhood system the

notion of clique: a clique is either a singleton or a set

of sites which are all neighbors of each other.

Depending on the neighborhood system, the family

of cliques will be different and involve more and less

sites. We will denote by C the set of all the cliques

relative to a neighborhood system V (see Figure 2).

Before introducing the general framework of

MRFs, let us define some notati ons. For a site s,

will stand for a random variable taking its values

in some set E (e.g., E = {0, 1, ..., 255}) and x

will be

a realization of X

and x

= (x

)

t6¼s

will denote an

image configuration where site s has been removed.

Finally, we will denote by X the random variable

X = (X

, X

, ...) with values in =E

jSj

Definition 2 We say that X is an MRF if the local

conditional probability at a site s is only a function

of V(s), that is,

pðX

¼ x

Þ¼pðX

¼ x

; t 2VðsÞÞ

Therefore, the gray level at a site depends only on

gray levels of neighboring pixels. Now we give the

following fundamental theorem due to Hammersley–

Clifford (Besag 1974) which states the equivalence

between MRFs and Gibbs fields.

Theorem 1 Let us suppose that S is finite, E is a

discrete set and for all x 2=E

jSj

, p(X = x) > 0,

then X is an MRF relatively to a system of

neighborhoods V if and only if there exists a family

of potential functions (V

)

c 2C

such that

p(x) = (1=Z) exp(

c 2C

(x)).

The function V(x) =

c 2C

(x) is called the

energy potential or the Gibbs measure and Z is a

normalizing constant: Z = exp(

x 2

V(x)).

If, for example, the collection of neighborhoods is

the set of 4-neighbors, then the theorem says that

V(x) =

c = {s} 2C

) þ

c = {(s, t)} 2C

, x

Application to the Denoising Problem

Now, given this theorem we can reformulate, thanks

to [4], the restoration problem (with the change of

notation u = x and u

= x

): find u minimizing the

global energy

EðuÞ¼K



kf  uk

þ VðuÞ½5

The next step is now to precise the Gibbs

measure. In restoration, the potential V(u) is often

dedicated to impose local regularity constraints, for

example, by penalizing differences between neigh-

bors. This can be modeled using cliques of order 2 in

the following manner:

VðuÞ¼

ðs;tÞ2C

ðu

 u

where  is a given real function. This term penalizes

the difference of intensities between neighbors which

may come from an edge or some noise. This discrete

cost function is very similar to the gradient penalty

terms in the continuous framework (see the next

section). The resulting final energy is (sometimes

E(u) is written E(u=f ))

EðuÞ¼K



s 2S

ðf

 u

þ 

ðs;tÞ2C

ðu

 u

where the constant  is a weight ing parameter

which can be estimated.

The difficulty in choosing the strength of the

penalty term defined by  is to be able to penalize

the noise while keeping the most salient features,

that is, edges. Historicall y, the function  was first

chosen as (z) = z

but this choice is not good since

the resulting regularization is too strong introducing

a blur in the image and loss of the edges. A better

choice is (z) = jzj (Rudin et al. 1992 )ora

regularized version of this function. Of course,

other choic es are possible depending on the con-

sidered application and the desired degree of

smoothness.

In this section, it has been shown how to model

the restoration problem through MRFs and the

Bayesian framework. Numerically, two main types

of algorithms can be used to minimize the energy:

deterministic algorithms and stochasti c algorithms.

The former are generally used when the global

energy is strictly convex (e.g., algorithms based on

Figure 2 Examples of neighborhood system and cliques.

Image Processing: Mathematics 3

gradient descent). The latter are rather used when

E(u) is not convex. There are stochastic minimiza-

tion algorithms mainly based on simulated anneal-

ing. Their main interest is that they always converge

(almost surely) to a minimizer (this is not the case

for deterministic algorithms which give only local

minimizers) but they are often strongly time

consuming.

We refer the reader to Li (1995) for more details

about MRFs and Bayesian framework and

Kirkpatrick et al. (1983) for more information on

stochastic algorithms.

The Variational Approach

Minimizing a Cost Function over a

Functional Space

One important issue in the previous section was the

definition of p(u) which gives some apriorion the

solution. In the variational approach, this idea is

also present but the way to infer it is in fact to

define the more suitable functional space that

describes images and their geometrical properties.

The choice of a functional space sets a norm which

in turn will constrain the solution to a certain

smoothness.

We illustrate this idea in this section on the

denoising problem [2] which can be seen as a

decomposition one. This means that given the

observation f, we look for u and  such that

f = u þ, where  incorporates all oscillations, that

is, noise, and also texture. Let us define a functional

to be minimized which takes into account the data f

and possibly some statistical informations about :

min

ðu;Þ

ðjuj

Þ such that ðjj

Þ¼



with f ¼u þg

½6

This formulation means that we look, among all

decompositions f = u þ , for the one which mini-

mizes (juj

) under the constraint (jj

) = .

Banach spaces E and G, and functions  and

will be discussed in the next subsection. Since a

minimization problem under constraints can be

expressed with an a dditional term weighted by a

Lagrange multiplier, the formulation [6] can be

rewritten as:

min

ðu;Þ

ðjuj

Þþ ðjj

Þ; f ¼ u þ 



½7

A similar writing consists in replacing  by f  u so

that [7] rewrites

min

ðjuj

Þþ ðjf  uj



½8

which is the classical formulation in image restora-

tion. From a numerical point of view, the minimiza-

tion is usually carried out by solving the associated

Euler equations but this may be a difficult task. The

main concern is the search for E and G and their

norm (or seminorm). It is guided by the choice that

an image u is composed of various geometric

structures (homogeneous regions, edges) while

 = f  u repre sents oscillations (noise and textures).

Examples of Functional Spaces

In this section, we revisit some possible choices of

functional spaces summarized in Table 1.

The first case (a) was inspired by the classical

Tikhonov regularizatio n. The functional space

()(  R

) is the space of functions in L

()

such that the distributional gradient Du is in L

().

Unfortunately, functions in H

() do not admit

discontinuities across curves and this is a major

problem with respect to image analysis since images

are made of smooth patches separated by sharp

variations.

Considering the problem reported in (a), Rudin et al.

(1992) proposed to work on BV(), the space of

bounded variations (BV) Ambrosio et al. (2000)

defined by

BVðÞ¼ u 2L

ðÞ;



< 1



with



¼ sup





udiv’ dx;

’ ¼ð’

;’

; ...;’

Þ2C

ðÞ

;

j’j

ðÞ

 1



½9

Table 1 Examples of functional spaces and their norm (see model [8])

Model E and juj

(t) G and juj

(t)

(a) H

(), juj



jruj



1=2

() with its usual norm t

(b) BV (), juj



jDuj tL

() with its usual norm t



jDuj t fb 2 L

(); b = div, jj

()

2  1,   Nj

@

= 0g t

4 Image Processing: Mathematics

It is equivalent to define BV() as the space of

() functions whose distributional gradient Du is

a bounded measure and [9] is its total variation. The

space BV() has some interesting properties:

1. lower semicontinuity of the total variation



with respect to the L

() topology,

2. if u 2BV(), we can define, for H

almost

everywhere x 2S

, the complement of Lebesgue

points (i.e., the jump set of u), a normal n

(x)

and two approximate ‘‘right’’ and ‘‘left’’ limits

(x) and u



(x), and

3. Du can be decomposed as a sum of a regular

measure, a jump measure, and a Cantor measure:

Du ¼ru dx þðu

 u



Þn

þ C

where ru is the approxima te gradient and H

the

one-dimensional Hausdo rff measure.

This ability to describe functions with disconti-

nuities across a hypersurface S

makes BV() very

convenient to describe images with edges. In this

context, the image restoration problem is well

posed and suitable numerical tools can be proposed

(Chambolle and Lions 1997).

One criticism of the model (b) in Table 1 pointed

out by Meyer (2001) is that if f is a characteristic

function and if f is sufficiently small with respect to

a suitable norm, then the model (Rudin et al. 1992)

gives u = 0 and  = f contrary to what one should

expect (u = f and  = 0). In fact, the main reason of

this phenomenon is that the L

-norm for the 

component is not the right one since very oscillating

functions can have large L

-norm (e.g.,

(x) = cos(nx)). To better describe such oscillating

functions, Meyer (2001) introduced the space of

functions which can be expres sed as a divergence

of L

-fields. This work was developed in R

and

this framework was adapted to bounded 2D

domains by Aubert and Aujol (2005) (see (c) in

Table 1). An example of image decomposition is

shown in Figure 3.

In this section, we have shown how the choic e of

the functional spaces is closely related to the

definition of a v ariational formulation. The

functionals are written in a continuous setting and

they can usually be minimized by solving the

discretized Euler equations iteratively, until conver-

gence. These PDEs and the differential operators are

constrained by the energy definition but it is also

possible to work directly on the equations, forget-

ting the formal link with the energy. Such an

approach has also been much develo ped in the

computer vision community and it is illustrated in

the next section.

We refer the reader to Aubert and Kornprobst

(2002) for a general review of variational

approaches and PDEs as applied to image analysis.

Scale Spaces and PDEs

Another approach to perform nonlinear filtering

is to define a family of image smoothing operators

, depending on a scale parameter t. Given an

image f (x), we can define the image u(t, x) = ( T

f )(x)

which corresponds to the image f analyzed at scale t.

In this section, following Alvarez–Guichard–Lions–

Morel (Alvarez et al. 1993), we show that u(t, x)

is the solution of a PDE provided some suitable

assumptions on T

Basic Principles of a Scale Space

This section describes some natural assumptions to

be fulfilled by scale spaces. We first assume that the

output at scale t can be computed from the output at

a scale t  h for very small h. This is natural, since a

coarser scale view of the original picture is likely to

be deduced from a finer one. T

is obtained by

composition of transition filters, denoted by T

tþh, t

So the first axiom is

(A1) T

tþh

= T

tþh, t

= Id

Another assumption is that operators act locally,

that is, (T

tþh, t

f )(x) depends essentially upon the

values of f (y) with y in a small neighborhood of x.

Taking into account the fact that as the scale

increases, no new feature should be created by the

scale space, we have the local comparison principle:

if an image u is locally brighter than another image

v, then this order must be conserved by the analysis.

This is expressed by:

(A2) For all u and v such that u(y) > v(y )ina

neighborhood of x and y 6¼ x, then for h small

enough, we have

ðT

tþh;t

uÞðxÞðT

tþh;t

vÞðxÞ

The third assumption states that a very smooth

image must evolve in a smooth way with the scale

Ori

inal u

Figure 3 Example of image decomposition (see Aubert and

Aujol (2005)).

Image Processing: Mathematics 5

space. Denoting the scalar product of two vectors of

by <x, y>, this assumption can be written as

(A3) Let u(y) = 1=2hA(y x), y xiþhp, y xiþc

be a quadratic form of R

, x fixed

(A = r

u(x) 2S

(2)

the set of 2 2 symmetric

matrices, p = ru(x) a vector of R

, c = u(x)a

constant.). We shall say that a scale space is

regular if there exists a function F(t , x, c, p, A),

continuous with respect to A, such that

ðT

tþh;t

u  uÞðxÞ

!Fðt; x; c; p; AÞ when h !0

Scale Spaces are Governed by PDEs

In the following theorem, it is stated that the former

assumptions are sufficient to prove that scale spaces

are in fact governed by PDEs.

Theorem 2 Under assumptions A1, A2, A3, there

exists a continuous function F : [0, T]  R 

S

(2)

!R satisfying F(t,x,c,p,A) F(t,x,c,p,B)

for all p2R

, AandBinS

(2)

with A Bsuchthat



ðuÞ

tþh;t

u  u

!Fðt; x; u; ru; r

uÞ; h !0

½10

uniformly for x 2R

, uniformly for u.

In eqn [10], the left-hand side term can be

interpreted as the partial temporal derivative with

respect to t so that the notion of PDEs arises. More

precisely, if f is continuous and uniformly bounded,

then it can be established that u(t, x) = (T

f )(x) is the

viscosity solution(see Definition 3)of

þ Hðt; x; u; ru; r

uÞ¼0 ðhere H ¼FÞ

uð0; xÞ¼f ðxÞ

½11

The map H : [0, T]  R R

S

(2)

!R is called

a Hamiltonian and the decre asing property of H

with respect to S is called degenerate ellipticity.

The theory of viscosity solutions was introduced

in the 1980s by Crandall and P L Lions (Crandall

and Lions 1981, Crandall et al. 1992). When strong

solutions of [11] do not exist, this theory allows

to define solutions which are only continuous or

even discontinuous. The definition of viscosity

solutions is

Definition 3 Let H :  R R

S

(2)

!R be con-

tinuous and degenerate elliptic and let u 2C

([0, T]  ). Then u is a viscosity solution of [11]

in [0, T]  if and only if

(i) u is a subsolution, that is, 8 2C

([0, T]  ),

8(t

, x

) a local strict maximum point of (u  )

(t, x), we have

@

ðt

; x

ÞþHðt

; x

; uðt

; x

Þ; rðt

; x

Þ;

ðt

; x

ÞÞ  0

(ii) u is a supersolution, that is, 8 2C

([0, T]  ),

8(t

, x

) a local strict minimum point of (u  )

(t, x), we have

@

ðt

; x

ÞþHðt

; x

; uðt

; x

Þ; rðt

; x

Þ;

ðt

; x

ÞÞ  0

In this definition, it is noticeable that derivatives of

u are replaced by the derivatives of the test functions

. Obviously, it can be verified that this notion of

weak solutions coincides with classical solution

when u has enough regularity.

Diffusion Operators Coming from the Scale Space

A step further is to assume additional properties on

the scale spaces and estimate the corresponding

operator. Invariance propert ies include geome tric

invariance axioms, contrast invariance, or scale

invariance. For example, if we assume the axioms

A1–A3, gray-level shift invariance:

(I1) T

(0) = 0, T

(u þ c) = T

(u) þ c for all u and all

constant c.

and translation invariance:

(I2) T

(

.u) = 

.(T

u) for all h in R

, t  0, where

(

.u)(x) = u(x þ h).

Then it can be established that F in [10] is

independent of (x, u), that is, u(t, x) = (T

f )(x)is

the unique viscosity solution of

¼ Fðru; r

uÞ

uð0; xÞ¼f ðxÞ

With more precise assumptions, one can even

recover explicitly the operator F. As an example, if

we look for a linear scale space which verifies some

isometry assumption:

(I3) T

(R.u)(x) = R.(T

u)(x) for all orthogonal trans-

formation R on R

, where (R.u)(x) = u(Rx).

6 Image Processing: Mathematics