7.2.1Variational models with gradient regularization

The optical flow constraint constitutes in every point x one equation, but in the contextof motion estimation from images we usually have two or three spatial dimensions. Consequently, the problem is massively underdetermined. However, it is possible to estimate the motion using a variational model

where ?(u, υ) represents the so-called data term and incorporates the optical flow constraint in a suitable norm. The second part ℛ(υ) models additional a priori knowledge on υ and is denoted as a regularizer. The parameter α regulates between data term and regularizer.

Possible choices for the data term are

or

The quadratic L2 norm can be interpreted as solving the optical flow constraint in a least-squares sense inside the image domain Ω. Conversely, taking the L1 norm enforces the optical flow constraint linearly and is able to handle outliers more robustly.

The regularizer ℛ(υ) has to be chosen such that the a priori knowledge is modeled in a reasonable way. If the solution is expected to be smooth, a quadratic L2 norm on the gradient of υ is chosen and we have

Another possible approach is to choose the total variation (TV) of υ if we expect piecewise constant parts of motion. In the finite-dimensional setting this can be written as

Taking

results in the very well known model of Horn and Schunck [18], 1981. With efficient primal-dual schemes to minimize L1 norms [12], L1-TV optical flow models with

became very popular [25, 36]. This model was further improved by Werlberger et al. [35], where the classical TV regularizer was replaced with a Huber norm. In this context, let us refer to a recent survey by Becker, Petra and Schnörr [5].

7.2.2Extension of the regularizer

The previously described regularizations are able to produce either smooth velocity fields (L2 regularization) or sharp edges (TV regularization). However, in realistic applications we often need a combination of both characteristics. To calculate velocity fields that combine smoothness and sharp edges, we need to extend the regularization term.

In the following approach we want to make use of the potential of TV regularization to calculate sharp edges. To incorporate the possibility to get smooth parts, we need an additional primal variable w: ℝ2 → ℝ2, which will be required for a second regularization term that allows for smooth transitions. We link the variables υ and w by forcing

Ifwe penalize this difference with an L1 norm and minimize it for υ, we get a simple TV regularization, which is shifted by w. This way we make sure we keep characteristics of a TV regularization for our results. To combine this with the characteristics of another regularization technique, we apply a second regularizer to w and also minimize everything for w. This procedure leads us to the following extended regularizer:

The term ?(w) is the additional term, which should be chosen in a way that it produces smooth flow fields. The weighting parameters α0 ∈ ℝ+ and α1 ∈ [0, 1] on the one hand determine the relation between the regularization parts and the optical flow constraints. On the other hand, they also determine the relation between the two regularization parts and in this way adjust the proportion of smooth parts and edges in the result. If is large, the constant parts and edges outweigh the smooth parts; if it is small, the smooth parts outweigh the constant parts and edges. Note that a functional of the form (2.4) leads to a regularization of υ via

Similar to the TV term in a standard model, we can choose between different evaluations of the norm ‖∇υi − w‖1 in the above formulation. Since this is a shifted TV norm, we once more have the possibility to use the anisotropic variant.

L1-TV/L2 optical flow model

As we have already seen, a regularization with the L2 norm leads to smooth approximations of a flow field. In the following approach, we use L2 of w as a norm for the additional regularization term ?(w), which leads us to

Together with

we get an L1-TV/L2 model. This model is a combination between the previously described Horn–Schunck model and the L1-TV model and thus contains characteristics of both kinds of flow fields. The regularizer in this model is very similar to the Huber function [19], which is defined as

The anisotropic variant of an optical flow model with Huber regularization has also been discussed in [35]. For another formulation of a related regularizer see for example [33] or [8].

Even if the Huber function can be solved directly, we want to be able to compare the different models by using the same algorithm. Therefore, later on we will use the same the algorithm as for the other approaches.

L1-TV/TV optical flow model

Another possibility to consider smoothness in a flow estimation is to incorporate a higher order derivative. In the setting of (2.4), we can choose ?(w) as the TV of w, which leads us to

Since the first term of the regularization leads to w being close to the gradient of w, the last term considers a term, which is close to the second gradient of υ. For the additional TV term in this model, we can again choose between the isotropic and the anisotropic variant, that is equivalently to those in Section 7.2.1. Overall, this leads to a huge variety of possible evaluations for this model.

By using

as a data term we get an L1-TV/TV model, which we will later use for the numerical realization.

The regularizer we get with the described approach is a primal realization of a specific case of a Total Generalized Variation (TGV) regularizer [7]. See [27, 28] for further analysis of the TGV regularizer applied to motion estimation models.

7.2.3Bregman iterations

A well-known drawback of TV regularization in combination with L2 data fidelity is the loss of contrast, which means that the difference between intensities in the result is lowered. However, edges are well recovered. Concerning optical flow, this shows up in a reduced velocity of motion. A possibility to overcome this drawback is to apply contrast-enhancing Bregman iterations [23]. For the case of a higher order regularization term additional systematic bias, for example related to slopes, is corrected in the same way (cf. [6]). For this sake, we need the Bregman Distance of the regularizer ℛ, which is defined as

for υ, υ∗ ∈ dom(ℛ). This distance replaces the former regularization term ℛ in the respective models. In this way it is possible to re-enhance the contrast. Thanks to the condition that b is in the subgradient of ℛ(υ∗), it is ensured, that the edges stay at the correct positions. The Bregman iteration iteratively computes υn+1 as a solution of

Afterwards, the Bregman variable is updated by setting

Applying Bregman iterations to the optical flow problem with L2 data fidelity can bewritten equivalently by adding the Bregman variable bn to the data. For the n-th Bregman iteration we can use the extended data term whichresults in an additive constant for the optimality condition. So far Bregman iterations have not been investigated as an iterative regularization method for optical flow. A previous investigation [17] only considered (split) Bregman methods as a minimization method for the original variational model, and did not investigate the possibility of reducing systematic bias. As we shall see below (Figure 3) the Bregman iteration can yield improvements in parts where other variational methods underestimate motion (see e.g., the right block in the rubber whale data set below) and produce competitive results (Table 2). It might thus nicely complement other approaches.

In the case of an L1 data fidelity, a simple modification of the data term is not possible and the iteration needs to be carried out via the original form (2.8). Because of the additional linear term ⟨bn, υ⟩ in comparison to the other linear terms in the functional, it is not guaranteed that the functional is coercive, hence the well-posedness of the iteration is not guaranteed in the infinite-dimensional setting. In any case, one is not sure that the Bregman iteration actually yields additional benefit, since the L1 data fidelity does not introduce systematic bias. We leave this issue to future research.

7.3.1Existence of minimizers

The basic issue of the existence of minimizers for optical flow problems has been considered by various authors (cf. e.g., [1, 16]) using methods of calculus of variations. With the assumption ut ∈ L2(Ω) and ∇u ∈ L∞(Ω) it is straightforward to see that the operator A and data g defined in (2.3) are bounded for p = 1, 2 and with standard convexity arguments lower semicontinuity of the data fidelities follow (for p = 1 assumptions can even be relaxed). The associated data terms can all be shown to be L2-coercive on subspaces of H1(Ω)2 in the case of the Horn–Schunck model and of BV(Ω) for the other models. The subspaces are given by functions with mean value zero for standard models, while they are given by functions of vanishing mean and first moments in the case of the TV-TV and TV-L2 regularizer. Hence, in order to obtain coercivity and thus existence of minimizers it is a natural question whether the data term yields coercivity on the whole space, that is boundedness of the data fidelity further implies bounds on the mean (and potentially the first moments) of υ. Obviously this cannot be true without further assumptions on ∇u (which is seen immediately for constant u). In the case of the Horn–Schunck model this question was answered in [30], who showed coercivity for the original Horn–Schunck model (see also [20] for a detailed discussion). His proof heavily uses the quadratic structure of the data fidelity as well as the fact that functions in the kernel of the regularization term are constant, hence it can be generalized to the L2-TV model, but neither to extensions of the TV regularization nor to L1-fidelities. However, the result can easily be generalized as we show in the following:

Lemma 3.1. Let Ω ⊂ ℝd, d ≥ 1 arbitrary, be a bounded domain and let (υn) be a sequence in Lp(Ω), 1 ≤ p ≤ ∞. Let ut ∈ Lp(Ω) and ∇u ∈ L∞(Ω)2 such that the functions ∂xi u are linearly independent. If there exists a sequence of vectors cn ∈ ℝd such that cn + υn is bounded in Lp(Ω) and

then υn is bounded in Lp(Ω) .

Proof. Under the above assumptions it obviously suffices to prove that the sequence cn is bounded in ℝd.We have

The boundedness of ‖ut+∇u⋅υn‖Lp of cn+υn imply that ∇u⋅cn is bounded in Lp(Ω). Now assume that cn is unbounded, then there exists a subsequence (again denoted by cn) with |cn| growing to infinity in a monotone way. Then is well defined and bounded, moreover tends to zero in Lp(Ω). Hence, has a convergent subsequence dn with limit d satisfying |d| = 1, in particular d ≠ 0. By continuity of the norm we find

which contradicts the linear independence of the functions ∂xi u and thus yields theassertion.

With the Poincare–Wirtinger inequality and the embedding of BV(Ω) into L2(Ω) for d ≤ 2 and L1(Ω) in arbitrary dimension, we obtain the coercivity of the total variation on functions of mean value zero. Now we choose cn equal to the mean value of υn and obtain coercivity of the respective Lp-TV model in BV(Ω). With a standard (weak) lower semicontinuity argument for the convex functionals we thus deduce the following existence result:

Theorem 3.2. Let Ω ⊂ ℝd be a bounded domain and let either p = 1 or p = 2. Let ut ∈ Lp(Ω) and ∇u ∈ L∞(Ω)d such that the functions ∂xi u are linearly independent. Then there exists a minimizer υ ∈ BV(Ω)d for the Lp-TV model in the cases p = 1 for arbitrary d and p = 2 for d ≤ 2.

Lemma 3.3. Let Ω ⊂ ℝd, d ≥ 1 arbitrary, be a bounded domain and let (υn) be a sequence in Lp(Ω), 1 ≤ p ≤ ∞. Let ut ∈ Lp(Ω) and ∇u ∈ L∞(Ω)2 such that the functions {∂xi u, xj∂xi u}i,j=1,...,d are linearly independent. If there exists a sequence of vectors cn ∈ ℝd and matrices An ∈ ℝd×dsuch that cn + Anx + υn is bounded in Lp(Ω) and

then υn is bounded in Lp(Ω) .

Proof. Under the above assumptions it obviously suffices to prove that the sequence cn is bounded in ℝd and the sequence An is bounded in ℝd×d. We have

The boundedness of ‖ut+∇u⋅υn‖Lp of cn +Anx+υυn imply that ∇u⋅(cn +Anx) is bounded in Lp(Ω). A limiting procedure as in the proof of Lemma 3.1 yields a nontrivial limit d respectively B such that

which contradicts the linear independence assumption and thus yields the assertion.

Using the coercivity of the effective functionals ℛ̃ on the space of BV-functions with vanishing mean and first moments (cf. [6] in the TV/ TVcase and [11] in the TV/L2 case) and a similar proof as above we obtain the following result:

Theorem 3.4. Let Ω ⊂ ℝd be a bounded domain and let either p = 1 or p = 2. Let ut ∈ Lp(Ω) and ∇u ∈ L∞(Ω)d such that the functions {∂xi u, xj∂xi u}i,j=1,...,d are linearly independent. Then there exists a minimizer υ ∈ BV(Ω)d for the Lp-TV/TV model and the Lp-TV/L2 model in the cases p = 1 for arbitrary d and p = 2 for d ≤ 2.

A major restriction of the existing existence analysis is the fact that some regularity of u t and ∇u needs to be assumed, whichmight not be met by solutions of transport equations, in particular for noisy versions of the images (note however that many results in the literature assume even stronger regularity, e.g., images of class C2 as in [16]). A detailed analysis of such issues remains a relevant question for future work. The case of stochastic noise in the image data might even enforce different approaches, e.g., Bayesian models (cf. [31]).

Let us finally mention that uniqueness of minimizers cannot be expected for total variation models, since neither the regularization nor the data term are strictly convex (due to the nullspace of the map υ ↦ ∇u ⋅ υ). In the case of an L2 data fidelity one can at least derive uniqueness of the component ∇u ⋅ υ normal to the image level sets.

7.3.2Quantitative estimates

Quantitative estimates have hardly been investigated for optical flow models in the past, which is probably due to the nonuniqueness of the flow reconstruction. Hence, an estimate to a ground truth seems out of reach in most cases. Nonetheless, it seems interesting to take a look at the optical flow problem from the perspective of error estimation for inverse problems (cf. [10]). Let us consider the case of L2 data fidelities for simplicity, we start from the optimality condition

The obvious first question to ask is the robustness of solutions for errors in the data u, a second question is related to the behavior as α tends to zero. Let us first sketch the derivation of quantitative error estimates in the case of data perturbations, for this sake let υ̃ be the solution of the variational model with data ũ t and ∇ũ. Then we have

A duality product with υ − υ̃ and an elementary calculation yields

Using appropriate duality estimates on the right-hand side one immediately obtains estimates for the Bregman distances and the error in the velocity component parallel to ∇u in terms of errors in the data. To do so, let us further rewrite the right-hand side to obtain

and with Young’s inequality we find

The two error terms on the right-hand side can be interpreted well. The first term measures the difference of the image data in a norm related to the optical flow model, it can further be related to the consistency in the optical flow constraint with estimated velocity υ.̃ The second term creates more trouble, since due to ∇ũ it can contain terms in the direction perpendicular to ∇u, in which case it cannot be related to the first term on the left-hand side. Note that when viewing the optical flow estimation as an inverse problem this term is indeed related to the model error, that is the error in the forward operator υ ↦ υ⋅∇u. Even if this term can be estimated somehow by the Bregman distances on the left-hand side (e.g., in the case of the Horn–Schunck functional simply by Young’s inequality), it will lead to an error term of order With the inherent smallness of α we hence conclude that errors in the image gradient will strongly influence the result. This can for example be interpreted in terms of the accuracy in the discrete approximation of the image gradient. The quality in the estimated flow indeed depends heavily on the gradient approximation in numerical results. This is illustrated in Table 3 via an evaluation of errors for different choices of difference quotients for ∇u.

In the case of negligible error in the image gradient we can give an improved estimate:

Proposition 3.5. Let u and u ̃ be weakly differentiable image data such that ∂tu, ∂tũ ∈ L2(Ω) and ∇u = ∇ũ. Then the estimate

holds for υ and υ̃ being the solution of

with data u respectively ũ.

Note that we see in any estimate that the velocity parallel to the image gradient (normal to level lines) can be estimated robustly from the image error (with constants independent of α), while we obtain hardly any information perpendicular to the gradient. This is just a mathematical consequence of the aperture problem in motion estimation. In the perpendicular direction we obtain some stability of the velocity via the Bregman distance terms, but note that the error will grow inversely proportional to α. We mention that to leading order in a small time step τ we have

Hence, the error measure is strongly related to the end-point error frequently used in practical evaluations of motion estimation, an issue we will discuss in detail below.

The limit α → 0 is the one usually studied in inverse problems with strong emphasis on the appropriate treatment of instabilities. In the case of motion estimation the underdeterminedness is the more crucial issue. Thus, the key question is to understand what solutions are obtained in the limit, respectively which kind of flows can be reconstructed well. The limiting solutions are determined by the constrained problem

The solutions to be reconstructed well are those satisfying a source condition (cf. [10]), that is the optimality condition for the constrained problem in a Lagrangian duality setting. This is equivalent to

for some w ∈ L2(Ω). Under this condition one can construct data ũt = ũt + αw, such that the constrained solution also satisfies the unconstrained variational problem with regularization parameter α > 0, thus error estimation reduces to the above case. From(3.4) we can give a mathematical reason why it is useful to have images with a large gradient, which corresponds to the usual intuition. The data perturbation is a multiple of w, hence error estimates depend on the norm of w, which is however inversely proportional to the norm of ∇u. A more detailed study of (3.4) depends on the specific regularization terms and is an interesting question for further research.

7.4.1Primal–dual algorithm

The concept of duality offers an efficient way of minimizing the introduced variational models. Let us for the numerical application consider two finite-dimensional vector spaces ? and ? equipped with a scalar product ⟨⋅, ⋅⟩ and a norm ‖⋅‖2. We furthermore consider a continuous linear operator K : ? → ?. Now, the class of variational problems in this section can be written as

where F, G: ? → ℝ are proper, convex and lower semi-continuous functionals. In our application, G(υ) usually incorporates the data term, whereas F (Kυ) denotes the regularizer. In the following, we denote Equation (4.1) as the primal problem. The primal problem is often hard to minimize or yields very slow algorithms. Instead of the primal problem, we can equivalently optimize the so-called primal-dual problem:

Here F ∗ refers to the convex conjugate of F, which can be easily calculated for the observed regularizers. The very well-known algorithm of Chambolle and Pock is dedicated to this class of problems [12]. For τ, σ > 0, a pair (υ0, y0) ∈ ? × ? and initial value ῡ0 = 0 we obtain the following iterative scheme to solve the saddle-point problem (4.2):

Here, proxτG denotes the proximal or resolvent operator

which can be interpreted as a compromise between minimizing G and being close to the input argument y. Suitable choices of τ and σ were chosen according to [26] and are given in Section 7.4.2 for each algorithm. The primal-dual methods are efficient if the proximal problem can be solved efficiently. In [12] the authors demonstrated an application of the primal–dual algorithm to a L1-TV optical flow problem. In the following we will extend this application to each of the introduced models and provide solutions to the occurring proximal problems.

In Table 1 we transferred our models to the notation of the primal problem (4.1). Let us begin with the proximal problems for the primal part G(υ), for a more detailed description we refer to [13].

L2 data term

For the L2 data term we have to solve for υ̃k+1 := υk − τK∗yk+1 the following proximalproblem:

This yields a linear optimality system, which can be directly calculated. The solution is given by υ = f(ῦ̃k), where f is a linear function also incorporating the scalar terms ut , ∇u and τ.

L1 data term

In case of the L1 optical flow term, the proximal problem reads

Table 1: Overview of splitting for different models.

Defining the affine linear function ρ(υ) := υ⋅∇u + u t, the problem above represents an affine-linear L1 optimization problem. It can be shown that the solution is given by

L2 regularization

Denoting the proximal problems for the dual part requires calculating the convex conjugate F ∗ of the dual part F first. For the L2 regularization term wecalculate and obtain the proximal problem

Consequently, the proximal problem can be solved straightaway.

TV regularization

In case of the total variation and the higher order regularization we always have L1 norms involved. Similar to the standard TV regularization (F(Kυ) = α ‖∇υ‖1) we have F ∗(y) = αδB(L∞)(y/α), where δB(L∞) denotes the indicator function of the L∞ unit ball. The corresponding proximal problem then reads

The solution is given by a point-wise projection of ỹk+1 onto the unit ball corresponding to the chosen vector norm. The solution will be discussed in more detail in Section 7.4.2.

7.4.2Discretization and parameters

In the context of discretization we have to consider two different aspects. On the one hand we have to approximate the image derivatives ut, ux and uy, which are passed to the algorithm as static variables afterwards. On the other hand, we have to discretize the operators K and K ∗ coming from the primal-dual iteration.

Starting with the image discretization, we consider the image domain to consist of the regular grid:

Since we are interested in the velocity field between t = 0 and t = 1 we have to evaluate the derivatives of ut,i,j at t = 0. In our observation, a mixed scheme consisting of a forward difference for the time derivative and central differences for the spatial derivatives turned out to give the best results. Stability in terms of u is not required, because of the fact that they act as constants in the model. Consequently, we obtain the following scheme:

For the sake of simplicity, we omitted the time-dependency in the derivatives.

The operators in our model only consist of gradients for the spatial regularization and the corresponding divergences. We propose a forward discretization with Neumann boundary conditions for the gradient and consequently obtain a backward difference for the divergence to keep a discrete adjoint structure. The resulting scheme reads

The primal-dual algorithms moreover requires suitable parameters σ and τ such that στ ≤ ‖K‖. It has been shown in [26] that a diagonal preconditioning technique can be used to find τ, σ without calculating ‖K‖. According to [26], Lemma 2, we choose for the gradient models from Section 7.2.1 and for the extended models from Section 7.2.2.

In the previous section, the solution of a proximal problem involving an indicator function of the L∞ unit ball of y was given as a point-wise projection. To conceive this, let us begin by writing down the convex set corresponding to δB(L∞)(y/α):

Here, ‖y/α‖∞ refers to the discrete maximum over all elements (i, j) in the image domain:

An interesting aspect is how to evaluate the vector norm yi,j= (y1, y2, y3, y4)i,j. Choosing

results in the so-called anisotropic variant, whereas

is denoted as the fully isotropic one. The anisotropic total variation is more suitable when dealing with quadratic structures, the isotropic variant better fits to circular structures. Depending on the chosen vector norm for υ (anisotropic, fully isotropic), we obtain a different dual inner norm yi,j/α. For the anisotropic case, that refers to the vectorial L1 norm, we get the maximum norm for the dual variable:

Since the fully isotropic case refers to the self-dual Euclidean norm, we get in this case

Transferring this to the optimization problem above, we get in the anisotropic case a the point-wise projection of ỹk+1 onto [−α, α]:

and for the isotropic case a point-wise projection of ỹk+1 onto the L2 unit ball:

For isotropic and anisotropic variants of the extended models, the norms are achieved equivalently. However, it has to be considered that for the L1-TV/TV model there are independent norms for both parts of the regularization. Using the partially isotropic variant also results in independent norms for the different components of υ. For the sake of simplicity we will restrict ourselves to the fully isotropic cases for all appearing total variations in the numerical realizations.

7.5.1Error measures for velocity fields

Finding error measures for velocity fields is a delicate problem which can be motivated by the following simple example. Consider two images, each consisting of only 3 × 3 pixels of the following form:

From our point of view we seek for a velocity field υ = (υ1, υ2) that transforms u1 into u2. Unfortunately, it is unclear which velocity field underlies this motion. Examples of possible solutions are

1.Just move the pixels at position (1, 1) and (1, 2) by 1 to the bottom, hence

2.Move the pixels at position (1, 1) and (1, 2) by 1 to the bottom and change their position:

3.Move the whole image by 1 to the bottom which gives

4.Move the pixels at position (1, 1) and (1, 2) by 1 to the bottom and exchange some pixels in the third column

All these velocity fields produce the same result, that is they all fulfill the optical flow constraint ut+∇u⋅υ = 0. This results from the fact that for given images the optical flow constraint states for every point x ∈ Ω only one equation for a 2-dimensional velocity field υ. The solution is unique iff there exists a unique bijection between u1 and u2. This requires both images to consist of the same intensity values, which furthermore have to be unique. Unfortunately, this assumption is far from reality, since regions of constant intensity are characteristic for background or objects. Hence, for practical problems we have a highly underdetermined system and consequently a huge variety of possible underlying velocity fields υ.

As we will see later an error measure always explicitly or implicitly favors one of these possible results over the others. Those error measures, which explicitly prefer one result, expect a given ground truth field and measure a distance d(υGT, υ) from the calculated velocity field to the given ground truth field. This strategy is questionable because in real world examples we usually do not have a ground truth velocity field, and artificial examples can usually be generated by several different ground truth fields. Hence, setting the ground truth υGT directly favors a subjective result. This is at least from the mathematical viewpoint questionable.

Absolute endpoint error

Despite the fact that explicit error measures might be problematic they are often used in the literature and we will also use them to evaluate our algorithms. In [2] two explicit error measures have been presented. The most intuitive one is the average endpoint error (aee), proposed in [24], which is the vector-wise Euclidean norm of the difference vector υ − υGT. The difference is divided by |Ω| and we have

or in a discrete formulation

Here, nPx denotes the number of pixels.

Angular error

A second measure states the angular error (ae) which goes back to the work of Fleet and Jepson [14] and a survey of Barron et al. [3]. Here υ and υGT are projected into the 3D space (to avoid division by zero) and normalized by

The error is then calculated measuring the angle between υ̂ and υ̂GT in the continuous setting as

and in a discrete setting as

Besides the fact that the ae is very popular, we want to emphasize a serious drawback. To illustrate this drawback we took a vector υGT = (υ1, υ2) and denote the Euclidean norm on the x-axis in Figure 1. This vector has been disturbed by an absolute and relative error of 0.01 to create υabs and υrel:

Afterwards we calculated the angular error between υ and υabs resp. υ and υrel and denoted this error on the y-axis of Figure 1. The first obvious property is that the error shrinks for larger velocities. This is critical since larger velocities are usually coupled with the object we are interested in. Conversely, absolute errors in small velocities (e.g., background) are over-penalized. To make this clear, let us consider a simple example: Take an algorithm producing an all-zero velocity field. This result perfectly recovers the background, but causes errors in the region of a moving object. Conversely,consider an algorithm that perfectly recovers the movement in the background, but introduces slight errors in parts of the object. Because of the fact that errors in the background are over-penalized, the first result might be preferred although it yields a worse result.

7.5.2Evaluation

In order to evaluate the introduced models we used the evaluation sequences from the Middlebury optical flow database [22]. First, the given ground-truth flow fields υGT were scaled down to a magnitude of one pixel to overcome the limitations of our algorithms (see Section 7.6.4). Afterwards, the evaluation images were created by keeping the first frame I1 and generating the second frame I 2 by cubic interpolation of I1(x + υGT). The noisy dataset was created with Gaussian noise (σ = 0.002).

The evaluation was performed on the one hand with static parameters along all datasets and on the other hand by manually adapting the parameters to find smaller values in terms of AE and AEE. The static parameters can be found in Table 2. Moreover, Table 2 contains the average rank of each algorithm for static and dynamic parameters over all evaluation datasets. Detailed error plots can be found in Figure 2. An overview of typical results for the individual algorithms is shown in Figure 3.

7.6.1Mass preservation

So far, the optical flow equation was used as a data term in combination regularizers modeling different a priori assumptions to the motion field υ. Another possible approach to this problem is given by the continuity equation. Following the assumptionthat the total mass in the image data stays constant in time, that is ∫Ωu(⋅, t)dx = C ∀t and, furthermore, that mass is moved by a continuous flow υ it can be shown that theflow satisfies the continuity equation ut + ∇⋅ (υu). This equation, referring to the optical flow constraint often denoted as mass-preservation constraint, can be used as a data term in combination with each of the introduced regularizers.

7.6.2Higher dimensions

Nowadays, estimating the flow for higher dimensional image data is a current field of research. For example, microscopes record 3-dimensional data of moving cells and intracellular flows. Also in a medical context 3-dimensional motion estimation is of great importance, for example in modalities with canonical time resolution like PET and SPECT, or in MR imaging. It is for example possible to exactly map tumors of lung cancer patients despite the respiratory motion based on (3d+t)-CT data. Unfortunately, the aperture problem becomes even worse in higher dimensions. Having in two spatial dimensions one equation (the optical flow constraint) for the two unknowns υ1, υ2 of the velocity field, we have to deal with three unknowns for three spatial dimensions. This missing information has to be caught by the regularizer in the variational model. Consequently, a priori assumptions to the flow field have an even higher impact on the solution. For biological applications we would typically expect an incompressible flow (i.e., ∇⋅υ = 0), which can be used as an additional regularizer. For 3-dimensional computing of optical flow see for example [4].

7.6.3Joint models

Another interesting question in the context of motion estimation is robustness towards noise. It can be shown that already low levels of noise in the image data massively disturb the motion estimation process. Consequently, for many applications the image data gets denoised as a preprocessing step. An alternative approach is given by the joint motion estimation and image reconstruction models,which is even inevitable in the case of missing data, for example partly in space or time. For given image data f , we would typically minimize models of the following structure

where ?(u, f) connects the unknown image data u with f , ℛ(u) (e.g., total variation) and ?(υ) (e.g., total variation or smoothness) act as regularizers for image data u and velocity field υ. The most important last part ?(u, υ) (optical flow or mass preservation constraint) connects image data and underlying motion field. One general benefit of such models is that the underlying motion is directly used for the image reconstruction, hence can be thought of as a motion compensation technique. Conversely, the enhanced image data should generate more reasonable velocity fields (cf. [13])

7.6.4Large displacements

One main drawback of the previously introduced models is their limitation to flows of small magnitude. The reason for this lies in the optical flow constraint, where we assumed a small timestep δt in the modeling part. For large-scale flows this assumption is simply not fulfilled anymore. Moreover, large errors in the discretization of the image gradients ux, uy and u t are introduced when proceeding to longer timesteps.

A common approach to overcome these difficulties is to use a different linearization of the optical flow formulation u2(x + υ) − u1(x) = 0 in combination with a multiscale strategy. The brightness constancy assumption can be linearized using an approximation υ0 to υ, yielding the following modified optical flow constraint:

Acting as a data term in a variational model, approximations υ0 are obtained by performing the flow estimation on different downscaled versions of u1 and u2. Starting on a very coarse scale, an initial υ0 is calculated. This initial υ0 then acts as an approximation in the next finer scale. Following this so-called warping strategy, we finally arrive at the original image.

It should be considered that it might be useful to adapt the regularization parameter in every warping step. Using the same regularization parameter independent of the size of the grid enhances the significance of a small error in an image, for example caused by noise, in a finer grid compared to its significance in a coarser grid. By reducing the influence of the regularization whilst refining the grid circumvents this mismatch.

A requirement for these multiscale approaches is that smaller structures move in a similar way to the larger ones, since the movements found in the coarse grids serve as an initial guess for the movements in finer grids. If small structures move completely independent of large ones, the flow field will not be detected correctly.

Recent approaches overcome these problems by using the idea of descriptor matching for optical flow. Descriptor matching is based on finding identical features in different images and matching them. This way it is possible to find extremely large displacements of discrete regions in between two images. However, since it is not possible to match every single pixel, this approach alone does not yield absolutely precise results. In [9], Brox and Malik combine descriptor matching with a variational approach to be able to estimate large displacements as well as precise results. On the basis of this work, Weinzaepfel at al. propose an algorithm for combined descriptor matching and variational motion estimation that also allows for nonrigid movements [34]. In [29], Revaud et al. assume that edges in images match with edges in the flow field and incorporate an interpolation framework in the model of [34] to avoid error-propagation caused by a warping. For evaluating large-scale motion we may refer to the KITTI Vision Benchmark Suite [15, 21], which contains high-resolution real world datasets.

Acknowledgment: This work was supported by ERC via Grant EU FP 7 – ERC Consolidator Grant 615216 LifeInverse and by the German Science Foundation DFG via BU 2327/6-1 and EXC 1003 Cells in Motion Cluster of Excellence, Münster, Germany.