A Theoretical Framework for Convex Regularizers in PDE-Based Computation of Image Motion.
Many differential methods for the recovery of the optic flow field from an image sequence can be expressed in terms of a variational problem where the optic flow minimizes some energy. Typically, these energy functionals consist of two terms: a data term, which requires e.g. that a brightness constancy assumption holds, and a regularizer that encourages global or piecewise smoothness of the flow field. In this paper we present a systematic classification of rotation invariant convex regularizers by exploring their connection to diffusion filters for multichannel images. This taxonomy provides a unifying framework for data-driven and flow-driven, isotropic and anisotropic, as well as spatial and spatio-temporal regularizers. While some of these techniques are classic methods from the literature, others are derived here for the first time. We prove that all these methods are well-posed: they posses a unique solution that depends in a continuous way on the initial data. An interesting structural relation between isotropic and anisotropic flow-driven regularizers is identified, and a design criterion is proposed for constructing anisotropic flow-driven regularizers in a simple and direct way from isotropic ones. Its use is illustrated by several examples.
Introduction
Even after two decades of intensive research, robust motion estimation continues to be
a key problem in computer vision. Motion is linked to the notion of optic
ow, the
displacement eld of corresponding pixels in subsequent frames of an image sequence.
Optic
ow provides information that is important for many applications, ranging from
the estimation of motion parameters for robot navigation to the design of second generation
video coding algorithms. Surveys of the state-of-the-art in motion computation
can be found in papers by Mitiche and Bouthemy [32], and Stiller and Konrad [50]. For
a performance evaluation of some of the most popular algorithms we refer to Barron et
al. [5] and Galvin et al. [20].
Bertero et al. [6] pointed out that, depending on its formulation, optic
ow calculations
may be ill-conditioned or even ill-posed. It is therefore common to use implicit or
explicit smoothing steps in order to stabilize or regularize the process.
Implicit smoothing steps appear for instance in the robust calculation of image
derivatives, where one usually applies some amount of spatial or temporal smoothing
(averaging over several frames). It is not rare that these steps are only described as algorithmic
details, but indeed they are often very crucial for the quality of the algorithm.
Thus, it would be consequent to make the role of smoothing more explicit by incorporating
it already in a continuous problem formulation. This way has been pioneered
by Horn and Schunck [25] and improved by Nagel [34] and many others. Approaches of
this type calculate optic
ow as the minimizer of an energy functional, which consists
of a data term and a smoothness term. Formulations in terms of energy functionals allow
a conceptually clear formalism without any hidden model assumptions, and several
evaluations have shown that these methods perform well [5, 20].
The data term in the energy functional involves optic
ow constraints such as the assumption
that corresponding pixels in dierent frames should reveal the same grey value.
The smoothness term usually requires that the optic
ow eld should vary smoothly
in space [25]. Such a term may be modied in an image-driven way in order to suppress
smoothing at or across image boundaries [1, 34]. As an alternative,
ow-driven
modications have been proposed which reduce smoothing across
ow discontinuities
[8, 12, 14, 29, 40, 43, 54]. Most smoothness terms require only spatial smoothness. Spatio-temporal
smoothness terms have been considered to a much smaller extent [7, 33, 36, 56].
Since smoothness terms ll in information from regions where reliable
ow estimates exist
to regions where no estimates are possible, they create dense
ow elds. In many
applications, this is a desirable quality which distinguishes regularization methods from
other optic
ow algorithms. The latter ones create non-dense
ow elds, that have to
be postprocessed by interpolation, if 100 % density is required.
Modeling the optic
ow recovery problem in terms of continuous energy functionals
oers the advantage of having a formulation that is as independent of the pixel grid
as possible. A correct continuous model can be rotation invariant, and the use of well-established
numerical methods shows how this rotation invariance can be approximated
in a mathematically consistent way.
From both a theoretical and practical point of view, it can be attractive to use energy
functionals that are convex. They have a unique minimum, and this global minimum
can be found in a stable way by using standard techniques from convex optimization,
for instance gradient descent methods. Having a unique minimum allows to use globally
convergent algorithms, where every arbitrary
ow initialization leads to the same solu-
tion: the global minimum of the functional. This property is an important quality of
a robust algorithm. Nonconvex energy functionals, on the other hand, may have many
local minima, and it is di-cult to nd algorithms that are both e-cient and converge
to a global minimum. Typical algorithms which converge to a global minimum (such as
simulated annealing [30]) are computationally very expensive, while methods which are
more e-cient (such as graduated non-convexity algorithms [9]) may get trapped in a
local minimum.
Minimizing continuous energy functionals leads in a natural way to partial dierential
equations (PDEs): applying gradient descent, for instance, yields a system of coupled
diusion{reactions equations for the two
ow components. The fastly emerging use
of PDE-based image restoration methods [22, 39], such as nonlinear diusion ltering
and total variation denoising, has motivated many researchers to apply similar ideas
to estimate optic
ow [1, 4, 12, 14, 24, 29, 38, 40, 43, 54]. A systematic framework
that links the diusion and optic
ow paradigms, however, has not been studied so
far. Furthermore, from the framework of diusion ltering it is also well-known that
anisotropic lters with a diusion tensor have more degrees of freedom than isotropic
ones with scalar-valued diusivities. These additional degrees of freedom can be used to
obtain better results in specic situations [53]. However, similar nonlinear anisotropic
regularizers have not been considered in the optic
ow literature so far.
The goal of the present paper is to address these issues. We present a theoretical
framework for a broad class of regularization methods for optic
ow estimation. For
the reasons explained above, we focus on models that allow a formulation in terms of
convex and rotation invariant continuous energy functionals. We consider image-driven
and
ow-driven models, isotropic and anisotropic ones, as well as models with spatial
and spatio-temporal smoothing terms. We prove that all these approaches are well-posed
in the sense of Hadamard: they have a unique solution that depends in a continuous
(and therefore predictable) way on the input data.
We shall see that our taxonomy includes not only many existing models, but also
interesting novel ones. In particular, we will derive novel regularization functionals for
optic
ow estimation that are
ow-driven and anisotropic. They are the optic
ow analogues
of anisotropic diusion lters with a diusion tensor. Many of the spatio-temporal
methods have not been proposed before as well. With the increased computational possibilities
of modern computers it is likely that they will become more important in the
future. In the present paper we also focus on interesting relations between isotropic and
anisotropic
ow-driven methods. They allow us to formulate a general design principle
which explains how one can create anisotropic optic
ow regularizers from isotropic ones.
Our paper is organized as follows. In Section 2 we rst review and classify existing
image-driven and isotropic
ow-driven models, before we derive a novel energy functional
leading to anisotropic
ow driven models. Then we show how one has to modify all
models with a spatial smoothness term in order to obtain methods with spatio-temporal
regularization. A unifying energy functional is derived that incorporates the previous
models as well as novel ones. Its well-posedness is established in Section 3. In Section 4
we take advantage of structural similarities between isotropic and anisotropic approaches
in order to formulate a design principle for anisotropic optic
ow regularizers. The paper
is concluded with a summary in Section 5.
A Framework for Convex Regularizers
2.1 Spatial regularizers
2.1.1 Basic structure
In order to formalize the optic
ow estimation problem, let us consider a real-valued
image sequence f(x; denotes the location within the image domain
and the time parameter  2 [0; T ] species the frame. The optic
ow eld
describes the displacement between two subsequent frames  and
should depict the same
image detail. Frequently it is assumed that image objects keep their grey value over
time:
0: (1)
Such a model assumes that illumination changes do not appear, and that occlusions or
disocclusions do not happen. Numerous generalizations to multiple constraint equations
and/or dierent \conserved quantities" (replacing intensity) exist; see e.g. [18, 51]. How-
ever, since the goal of the present paper is to study dierent regularizers, we restrict
ourselves to (1). If the spatial and temporal sampling is su-ciently ne, we may replace
(1) by its rst order Taylor approximation
where the subscripts x, y and  denote partial derivatives. This so-called optic
ow constraint
forms the basis of many dierential methods for estimating the optic
ow.
Evidently such a single equation is not su-cient to determine the two unknown functions
In order to recover a unique
ow eld, we need an additional
assumption. Regularization-based optic
ow methods use as additional assumption the
requirement that the optic
ow eld should be smooth (or at least piecewise smooth).
The basic idea is to recover the optic
ow as a minimizer of some energy functional of
type
Z
dx dy (3)
where r := (@ x ; @ y ) T denotes the spatial nabla operator, and u := . The rst
term in the energy functional is a data term requiring that the OFC be fullled, while
the second term penalizes deviations from (piecewise) smoothness. The smoothness term
called regularizer, and the positive smoothness weight  is the regularization
parameter. One would expect that the specic choice of the regularizer has
a strong in
uence on the result. Therefore, let us discuss dierent classes of convex
regularizers next.
2.1.2 Homogeneous regularization
In 1981 Horn and Schunck [25] pioneered the eld of regularization methods for optic
ow computations. They used the regularizer
It is a classic result from the calculus of variations [13, 16] that { under mild regularity
conditions { a minimizer
Z
satises necessarily the so-called Euler{Lagrange equations
with homogeneous Neumann boundary conditions:
@
@
Hereby, n is a vector normal to the image boundary @
Applying this framework to the minimization of the Horn and Schunck functional
leads to the PDEs
where  := @ xx denotes the Laplace operator. These equations can be regarded as
the steady state (t !1) of the diusion{reaction system
where t denotes an articial evolution parameter that should not be mixed up with the
time  of the image sequence. These equations also arise when minimizing the Horn and
Schunck functional using steepest descent. Schnorr [41] has established well-posedness
by showing that this functional has a unique minimizer that depends continuously on
the input data f . Recently, Hinterberger [24] proved similar well-posedness results for a
related model with a dierent data term.
We observe that the underlying diusion process in the Horn and Schunck approach
is the linear diusion equation
with 2. This equation is well-known for its regularizing properties
and has been extensively used in the context of Gaussian scale-space; see [48] and the
references therein. It smoothes, however, in a completely homogeneous way, since its
diusivity As a consequence, it also blurs across semantically
important
ow discontinuities. This is the reason why the Horn and Schunck approach
creates rather blurry optic
ow elds. The regularizers described in the sequel are attempts
to overcome this limitation.
2.1.3 Isotropic image-driven regularization
It seems plausible that motion boundaries are a subset of the image boundaries. Thus, a
simple way to prevent smoothing at motion boundaries consists of introducing a weight
function into the Horn and Schunck regularizers that becomes small at image edges.
This modication yields the regularizer
where g is a decreasing, strictly positive function. This regularizer has been proposed
and theoretically analysed by Alvarez et al. [1]. The corresponding diusion{reaction
equations are given by
The underlying diusion process is
It uses a scalar-valued diusivity g that depends on the image gradient. Such a method
can therefore be classied as inhomogeneous, isotropic and image-driven. Isotropic refers
to the fact that a scalar-valued diusivity guarantees a direction-independent smoothing
behaviour, while inhomogeneous means that this behaviour may be space-dependent.
Since the diusivity does not depend on the
ow itself, the diusion process is linear.
For more details on this terminology and diusion ltering in image processing, we refer
to [53]. Homogeneous regularization arises as a special case of (15) when g(jrf
is considered.
2.1.4 Anisotropic image-driven regularization
An early anisotropic modication of the Horn and Schunck functional is due to Nagel
[34]; see also [2, 17, 35, 37, 41, 42, 47]. The basic idea is to reduce smoothing across image
boundaries, while encouraging smoothing along image boundaries. This is achieved by
considering the regularizer
D(rf) is a regularized projection matrix perpendicular to rf :
where I denotes the unit matrix. This methods leads to the diusion{reaction equations
The usage of a diusion tensor D(rf) instead of a scalar-valued diusivity allows a
direction-dependent smoothing behaviour. This method can therefore be classied as
anisotropic. Since the diusion tensor depends on the image f but not on the unknown
ow, it is a purely image-driven process that is linear in its diusion part. Well-posedness
for this model has been established by Schnorr [41].
The eigenvectors of D are v 1 := rf , v 2 := rf ? , and the corresponding eigenvalues
are given by
In the interior of objects we have
ideal edges where jrf 1. Thus, we have isotropic
behaviour within regions, and at image boundaries the process smoothes anisotropically
along the edge. This behaviour is very similar to edge-enhancing anisotropic diusion
ltering [53]. In contrast to edge-enhancing anisotropic diusion, however, Nagel's optic
ow technique is linear. It is interesting to note that only recently it has been pointed out
that the Nagel method may be regarded as an early predecessor of anisotropic diusion
ltering [2].
Homogeneous and isotropic image-driven regularizers are special cases of (19), where
D(rf) := I and D(rf) := g(jrf j 2 )I are chosen.
2.1.5 Isotropic
ow-driven regularization
Image-driven regularization methods may create oversegmentations for strongly textured
objects: in this case we have much more image boundaries than motion boundaries. In
order to reduce smoothing only at motion boundaries, one may consider using a purely
ow-driven regularizer. This, however, is at the expense of refraining from quadratic
optimization problems. In earlier work [43, 54], the authors considered regularizers of
type
dierentiable and increasing function that is convex in s, for instance
Regularizer of type (25) lead to the diusion{reaction system
where 0 denotes the derivative of with respect to its argument. The scalar-valued
diusivity shows that this model is isotropic and
ow-driven. In
general, the diusion process is nonlinear now. For the specic regularizer (26), for
instance, the diusivity is given by
Since this nonlinear diusivity is decreasing in its argument, smoothing at
ow discontinuities
is inhibited. For the specic choice homogeneous
regularization with diusivity 0 recovered again.
The preceding diusion{reaction system uses a common diusivity for both channels.
This avoids that edges are formed at dierent locations in each channel. The same
coupling also appears in isotropic nonlinear diusion lters for vector-valued images
as considered by Gerig et al. [21], and Whitaker and Gerig [57]. Nonlinear
ow-driven
regularizers with dierent diusivities for each channel are discussed in Section 4.
2.1.6 Anisotropic
ow-driven regularization
We have seen that there exist isotropic and anisotropic image-driven regularizers as well
as isotropic
ow-driven ones. Thus, our taxonomy would be incomplete without having
discussed anisotropic
ow-driven regularizers. In the context of nonlinear diusion l-
tering, anisotropic models with a diusion tensor instead of a scalar-valued diusivity
oer advantages for images with noisy edges or interrupted structures [55].
How can one construct related optic
ow methods? Let us rst have a look at diusion
ltering of multichannel images. In the nonlinear anisotropic case, Weickert [52, 55] and
Kimmel et al. [26] proposed to lter a multichannel image by using a joint diusion
tensor that depends on the gradients of all image channels. Our goal is thus to nd an
optic
ow regularizer that leads to a coupled diusion{reaction system where the same
ux-dependent diusion tensor used in each equation.
In order to derive this novel class of regularizers, we have to introduce some deni-
tions rst. As in the previous section, we consider an increasing smooth function
that is convex in s. Let us assume that A is some symmetric n  n matrix with orthonormal
eigenvectors w 1 ,.,w n and corresponding eigenvalues  1 ,., n . Then we may
formally extend the scalar-valued function (z) to a matrix-valued function (A) by
dening (A) as the matrix with eigenvectors w 1 ,.,w n and eigenvalues ( 1 ),., ( n
This denition can be motivated from the case where (z) is represented by a power
series
. Then it is easy to see that the corresponding matrix-valued power
series
A k has the eigenvectors w 1 ,.,w n and eigenvalues ( 1 ),., ( n ). Another
denition that is useful for our considerations below is the trace of a quadratic matrix
It is the sum of its diagonal elements, or { equivalently { the sum of its
eigenvalues:
a
With these notations we consider the regularizer
Its argument
is a symmetric and positive semidenite 22 matrix. Hence, there exist two orthonormal
eigenvectors corresponding nonnegative eigenvalues  1 ,  2 . These eigenvalues
specify the contrast of the vector-valued image in the directions v 1 and v 2 , respec-
tively. This concept has been introduced by Di Zenzo for edge analysis of multichannel
images [15]. It can be regarded as a generalization of the structure tensor [19], and it is
related to the rst fundamental form in dierential geometry [28].
Our result below states that the regularizer (32) leads to the desired nonlinear
anisotropic diusion-reaction system.
Proposition 1 (Anisotropic Flow-Driven Regularization)
For the energy functional (3) with the regularizer (32), the corresponding steepest descent
diusion{reaction system is given by
where the diusion tensor satises
Proof. The Euler{Lagrange equations for minimizing the energy
Z
dx dy (37)
are given by
In order to simplify the evaluation of the rst and second summand in both equations,
we replace (x; y) by the unit vector in x i direction. Together
with the identities
tr (ab T
div
it follows that
@
tr
tr
tr
Plugging this result into the Euler{Lagrange equations concludes the proof.
It should be noted that, in general, the eigenvalues of the diusion
tensor are not equal. Therefore, we have a real anisotropic diusion process with dierent
behaviour in dierent directions. Homogeneous regularization is a special case of the
regularizer (32), if
An interesting similarity between the isotropic regularizer (25) and its anisotropic
counterpart (32) becomes explicit when writing (25) as
This shows that it is su-cient to exchange the role of the trace operator and the penalty
function to switch between both regularization techniques. Another structural similarity
will be discussed in Section 4.
2.2 A unifying framework
Let us now make a synthesis of all previously discussed models. Table 1 gives an overview
of the smoothness terms that we have investigated so far.

Table

1: Classication of regularizers for optic
ow models.
isotropic anisotropic
image-driven
ow-driven
tr
One may regard these regularizers as special cases of two more general models. Using
the compact notation ru := the rst model has the structure
For model comprises pure image-driven models, regardless whether they
are isotropic (D(rf) := g(jrf j 2 )I) or anisotropic. Isotropic
ow-driven models arise for
D := I. In the general case, the model may be both image-driven and
ow-driven.
The second model can be written as
It comprises the anisotropic
ow-driven case and its combinations with image-driven
approaches. Note the large structural similarities between (45) and (46).
Both models can be assembled to the regularizer
where the paramter  2 [0; 1] determines the anisotropy. This regularizer is embedded
into the general optic
ow functional
Z
dx dy: (48)
2.3 Spatio-temporal regularizers
All regularizers that we have discussed so far use only spatial smoothness constraints.
Thus, it would be natural to impose some amount of (piecewise) temporal smoothness
as well. Using our results from the previous section it is straightforward to extend the
smoothness constraint into the temporal domain. Instead of calculating the optic
ow
as the minimizer of the two-dimensional integral (48) for each time frame , we
now minimize a single three-dimensional integral whose solution is the optic
ow for all
frames  2 [0; T ]:
E(u) :=
Z
dx dy d (49)
denotes the spatio-temporal nabla operator.
The corresponding diusion{reaction systems of spatio{temporal energy functionals
have the same structure as the pure spatial ones that we investigated so far. The only
dierence is that the spatial nabla operator r has to be replaced by its spatio-temporal
analogue r  . Thus, one has to solve 3D diusion{reaction systems instead of 2D ones.
Not many spatio-temporal regularizers have been studied in the literature so far. To
the best of our knowledge, there have been no attempts to investigate rotation invariant
spatio-temporal models that use homogeneous, isotropic image-driven, or anisotropic
ow-driven regularizers.
Nagel [36] suggested an extension of his anisotropic image-driven smoothness con-
straint, where the diusion tensor (20) is replaced by
D(r  f) := 1
Its eigenvalues are given by
Isotropic
ow-driven spatio-temporal regularizers have been studied by the authors in
[56]. They showed that it outperforms a corresponding spatial regularizer at low additional
computing time, if an entire image stack is to be processed.
It appears that the limited memory of previous computer architectures prevented
many researchers from studying approaches with spatio-temporal regularizers, since they
require to keep the entire image stack in the computer memory. On contemporary PCs
or workstations, however, this is no longer a problem, if typical stack sizes are used (e.g.
frames with 256  256 pixels). It is thus likely that spatio-temporal regularizers will
become more important in the future.
3 Well-Posedness Properties
In this section we shall prove that the energy functionals (48) and (49), respectively,
admit a unique solution that continuously depends on the initial data. These favourable
properties are the consequence of embedding the optic
ow constraint (2) into a convex
regularization approach.
From the perspective of regularization, Table 1 reveals another useful classication
in this context: while image{driven models correspond to the class of quadratic regularizers
[6],
ow{driven models belong to the more general class of non{quadratic convex
regularizers. This latter class has been suggested in [11, 45, 49] for generalizing the
well-known quadratic regularization approaches (cf. [6]) used for early computational
vision.
3.1 Assumptions
In the following, we do not distinguish between the approaches (48) and (49) since with
our results hold true for arbitrary n. Furthermore, we assume that the function
strictly convex with respect to s, and there exist constants c
such that
We consider only matrices D(rf) that are symmetric and positive denite. We dene
as the space of admissible optic
ow elds the set

endowed with the scalar product
Z
and its induced norm
In what follows, hf; ui denotes the action of some linear continuous functional f 2 H  ,
i.e. some element of the dual space H  , on some vector eld u 2 H.
3.2 Convexity
We wish to show that the functional E(u) is strictly convex over H. To this end, we may
disregard linear and constant terms in E(u) and consider the functional F (u) dened
by
F (u) :=
Z
where
Z
c :=
Z
Strict convexity is a crucial property for the existence of a unique global minimizing
optical
ow eld u of E(u) determined as the root of the equation
for any linear functional b 2 H  . We proceed in several steps. First, we consider the
smoothness terms V 1 (rf; ru) and V 2 (rf; ru) separately. This can be done because
the sum of convex functions is again convex. Then we consider all terms together, that
is the functional F (u).
The term
belongs to the class of smoothness terms which were considered in earlier work on
isotropic nonlinear diusion of multichannel images (e.g. [44]). To see this, let
vec (ru) :=@ ru 1
denote the vector obtained by stacking the columns of ru one upon the other, and let
denote the norm induced by the scalar product
vec (ru); vec (rv)
can be rewritten as
tr ru T D(rf)ru
and the framework in [44] is applicable.
The second anisotropic and
ow{driven smoothness term
is new in the context of optical
ow computation. Note that by contrast to term V 1 , the
function is matrix-valued. The strict convexity of V 2 is stated in
Proposition 2 (Matrix-Valued Convexity)
strictly convex, A and B two positive semidenite symmetric matrices
with A 6= B, and  2 (0; 1). Then
tr
Proof. Put are symmetric, there are orthonormal
systems of eigenvectors fu i and real-valued eigenvalues f i g, f i g, f
i g such
that
Expanding the vectors u with respect to the system fw i g gives
(v T
With this we obtain
(v T
(v T
Comparing the coe-cients shows that
j is a convex combination of f i g and f i g:
(v T
strictly convex and
obtain
tr

(v T
(v T
(v T
This concludes the convexity proof.
So far we have shown the convexity of the smoothness term V (rf; ru) in (57). To
show that F (u) is strictly convex, we may use the equivalent condition that F 0 (u) is
strongly monotone [58]:
Note that the smoothness term fullls this condition because it is convex, as we have
just shown. Concerning the remaining rst term in (57), we have to cope with the small
technical di-culty that the vector eld u is multiplied with rf which may vanish in
homogeneous image regions. In this context, we refer to in [41] where this problem has
been dealt with.
3.3 Existence, uniqueness, and continuous dependence on the
data
It is a well-established result (see, e.g., [58]) that property (73) together with the Lipschitz
continuity of the operator F 0 (which holds true under mild conditions with respect
to the data rf; f  , cf. [41, 46]) ensure the existence of a unique and globally minimizing
optical vector eld u that continuously depends on the data. To understand the latter
property, suppose we are given two image sequences and corresponding functionals
(cf. (57)) and minimizers
By virtue of (73) we have
Thus,
This equation states that, for a slight change of the image sequence data, the corresponding
optical
ow eld cannot arbitrarily jump but gradually changes, too. It is therefore
an important robustness property.
Extensions
All regularizers that we have discussed so far can be motivated from existing nonlinear
diusion methods for multichannel images, where a joint diusivity or diusion tensor
for all channels is used. As one might expect, this is not the only way to construct useful
optic
ow regularizers. In particular, there exists a more general design principle for
anisotropic
ow-driven regularizers which we will discuss next.
Our key observation for deriving this principle is an interesting relation between
anisotropic
ow-driven regularizers and isotropic
ow-driven ones: the anisotropic regularizer
tr (J) can be expressed by means of the eigenvalues  1 ,  2 of J as
while its isotropic counterpart (tr J) can be written as
This observation motivates us to formulate the following design principle for rotationally
invariant anisotropic
ow-driven regularizers:
Design Principle (Rotationally Invariant Anisotropic Regularizers)
Assume that we are given some isotropic regularizer (
function , and a decomposition of its argument
where the  j are rotationally invariant expressions. Then the regularizer
rotationally invariant and anisotropic.
Examples
1. The decomposion that has been used in (78) and (79) to transit from an isotropic
to an anisotropic model was the trace identity
where  1 and  2 are the eigenvalues of proposed the regularizer
with sh u :=
Applying the design principle, one can derive this expression from the identity [27]
Using the regularizer (82) in the functional (3) leads to the highly anisotropic
diusion{reaction system
u 2x
Note that now the coupling between both equations is more complicated than in
the previous cases, where a joint diusivity or a joint diusion tensor has been
used. We are not aware of similar diusion lters for multichannel images. Well-posedness
properties and experimental results for this optic
ow method are presented
in [43, 46].
3. Requiring that the  j in (80) be rotationally invariant ensures the rotation invariance
of the anisotropic regularizer. If we dispense with rotation invariance, the
design principle can still be used. As an example, let us study the
ow-driven regularization
methods that are considered in [4, 12, 14, 29]. They use a regularizer
of type
According to our design principle, we may regard this regularizer as an anisotropic
version of the isotropic regularizer (25). However, the decomposition of its argument
into is not rotationally invariant. The corresponding
diusion{reaction system is given by
which shows that both systems are completely decoupled in their diusion terms.
Thus,
ow discontinuities may be created at dierent locations for each channel.
The same decoupling appears also for some other PDE-based optic
ow methods
such as [40].
While each of the two diusion processes is isotropic, the overall process reveals
some anisotropy: in general, the two diusivities are
not identical. Well-posedness results for this approach with a modied data term
have been established by Aubert et al. [4].
There is also a number of related stochastic methods that lead to discrete models
which are not consistent approximations to rotation invariant processes [7, 8, 10,
23, 31, 33]. Nonconvex regularizers are typically used in these approaches. Discrete
spatio-temporal versions of the regularizer (86) are investigated in [7, 33].
It is a challenging open question whether there exist more useful rotation invariant
convex regularizers than the ones we have just discussed. This is one of our current
research topics.
5 Summary and Conclusions
The goal of this paper was to derive a diusion theory for optic
ow functionals. Minimizing
optic
ow functionals by steepest descent leads to a set of two coupled diusion{
reaction systems. Since similar equations appear for diusion ltering of multi-channel
images, the question arises whether there are optic
ow analogues to the various kinds
of diusion lters.
We saw that image-driven optic
ow regularizers correspond to linear diusion lters,
while
ow-driven regularizers create nonlinear diusion processes. Pure spatial regularizers
can be expressed as 2D diusion{reaction processes, and spatio-temporal regularizers
may be regarded as generalizations to the 3D case. This taxonomy helped us not only to
classify existing methods within a unifying framework, but also to identify gaps, where
no models are available in the current literature. We lled these gaps by deriving suitable
methods with the specied properties, and we proved well-posedness for the class
of convex diusion-based optic
ow regularization methods.
One important novelty along these lines was the derivation of regularizers that can
be related to anisotropic diusion lters with a matrix-valued diusion tensor. This also
enabled us to propose a design principle for anisotropic regularizers, and we discovered an
interesting structural similarity between isotropic and anisotropic models: it is su-cient
to exchange the role of the trace operator and the penalty function in order to switch
between the two models.
We are convinced that these relations are only the starting point for many more
fruitful interactions between the theories of diusion ltering and variational optic
ow
methods. Diusion ltering has progressed very much in recent years, and so it appears
appealing to incorporate recent results from this area into optic
ow methods.
Conversely, it is clear that novel optic
ow regularizers can also be regarded as energy
functionals for suitable diusion lters.
We hope that our systematic taxonomy provides a unifying platform for algorithms
for the entire class of convex variational optic
ow methods. Our future plans are to
use such a platform for a detailed performance evaluation of the dierent methods in
this paper, and for a systematic comparison of dierent numerical algorithms. Another
point on our agenda is an investigation of alternative rotation-invariant decompositions
that can be applied to construct useful anisotropic regularizers.

Acknowledgement

. CS completed his doctoral thesis under the supervision of Prof.
Nagel in 1991. He is grateful to Prof. Nagel who introduced him to the eld of computer
vision.



--R



A computational framework and an algorithm for the measurement of visual motion
Computing optical ow via variational tech- niques
Performance of optical ow techniques

Robust dynamic motion estimation over time
The robust estimation of multiple motions: Parametric and piecewise smooth ow
Cambridge (Mass.


Nonlinear variational method for optical ow computation
Methods of mathematical physics

A note on the gradient of a multi-image
Calculus of variations
Investigation of multigrid algorithms for the estimation of optical ow
Computation of component image velocity from local phase information

Recovering motion


Multimodal estimation of discontinuous optical ow using Markov random
Generierung eines Films zwischen zwei Bildern mit Hilfe des op- tischen Flusses

Images as embedded maps and minimal surfaces: movies
Invariant properties of the motion parallax

a curve evolution approach
theory and applications

Computation and analysis of image motion: a synopsis of current problems and methods
Scene segmentation from visual motion using global optimization
Constraints for the estimation of displacement vector
On the estimation of optical ow: relations between di
Extending the 'oriented smoothness constraint' into the temporal domain and the estimation of derivatives of optical ow
An investigation of smoothness constraints for the estimation of displacement vector
Variational approach to optical ow estimation managing discontinuities

Determination of optical ow and its discontinuities using non-linear diusion






On the mathematical foundations of smoothness constraints for the determination of optical ow and for surface reconstruction
Gaussian scale-space theory
Discontinuity preserving regularization of inverse visual problems
Estimating motion in image sequences
Robust computation of optical ow in a multi-scale dierential framework

Anisotropic di
On discontinuity-preserving optic ow



Nonlinear functional analysis and its applications
--TR

--CTR
El Mostafa Kalmoun , Harald Kstler , Ulrich Rde, 3D optical flow computation using a parallel variational multigrid scheme with application to cardiac C-arm CT motion, Image and Vision Computing, v.25 n.9, p.1482-1494, September, 2007
Luis Alvarez , Rachid Deriche , Tho Papadopoulo , Javier Snchez, Symmetrical Dense Optical Flow Estimation with Occlusions Detection, International Journal of Computer Vision, v.75 n.3, p.371-385, December  2007
Joan Condell , Bryan Scotney , Philip Morrow, Adaptive Grid Refinement Procedures for Efficient Optical Flow Computation, International Journal of Computer Vision, v.61 n.1, p.31-54, January 2005
Nils Papenberg , Andrs Bruhn , Thomas Brox , Stephan Didas , Joachim Weickert, Highly Accurate Optic Flow Computation with Theoretically Justified Warping, International Journal of Computer Vision, v.67 n.2, p.141-158, April 2006
Joachim Weickert , Christoph Schnrr, Variational Optic Flow Computation with a Spatio-Temporal Smoothness Constraint, Journal of Mathematical Imaging and Vision, v.14 n.3, p.245-255, May 2001
Daniel Cremers , Stefano Soatto, Motion Competition: A Variational Approach to Piecewise Parametric Motion Segmentation, International Journal of Computer Vision, v.62 n.3, p.249-265, May 2005
Andrs Bruhn , Joachim Weickert , Timo Kohlberger , Christoph Schnrr, A Multigrid Platform for Real-Time Motion Computation with Discontinuity-Preserving Variational Methods, International Journal of Computer Vision, v.70 n.3, p.257-277, December  2006
Andrs Bruhn , Joachim Weickert , Christoph Schnrr, Lucas/Kanade meets Horn/Schunck: combining local and global optic flow methods, International Journal of Computer Vision, v.61 n.3, p.211-231, February/March 2005
David Tschumperl , Rachid Deriche, Orthonormal Vector Sets Regularization with PDE's and Applications, International Journal of Computer Vision, v.50 n.3, p.237-252, December 2002
differential methods;regularization;diffusion filtering;optic flow;well-posedness