Divergence-Free Wavelets and High Order Regularization

Abstract

Expanding on a wavelet basis the solution of an inverse problem provides several advantages. First of all, wavelet bases yield a natural and efficient multiresolution analysis which allows defining clear optimization strategies on nested subspaces of the solution space. Besides, the continuous representation of the solution with wavelets enables analytical calculation of regularization integrals over the spatial domain. By choosing differentiable wavelets, accurate high-order derivative regularizers can be efficiently designed via the basis’s mass and stiffness matrices. More importantly, differential constraints on vector solutions, such as the divergence-free constraint in physics, can be nicely handled with biorthogonal wavelet bases. This paper illustrates these advantages in the particular case of fluid flow motion estimation. Numerical results on synthetic and real images of incompressible turbulence show that divergence-free wavelets and high-order regularizers are particularly relevant in this context.

1 Introduction

Prior models used to solve ill-posed inverse problems such as image restoration, surface reconstruction or optic-flow estimation often involve differential constraints or smoothing term incorporating high-order derivatives (Terzopoulos 1986). In particular in the context of optic-flow estimation, numerous regularization models (Horn and Schunck 1981; Suter 1994) involving penalization of first or second order derivatives of the estimated velocity have been proposed in order to make this estimation problem well-defined, beginning with the original work of Horn and Schunck (1981). However, although estimation of optical flow is an old and well-known problem, it still remains very challenging for deformations metrological issues or for the measurement of fluid flows Heitz et al. (2010). Indeed, optical flow standards are in general designed from almost rigid motions consideration and do not include physical considerations on the observed phenomenon occurring eventually at different spatial scales. Several attempts have been carried out in order to introduce some physical constraints, such as incompressibility (Heas et al. 2012; Yuan et al. 2007) or second order regularization functional preserving blobs of curl and divergence (Heitz et al. 2010).

In addition, inverse problems often involve non-linear models relating the data term to the unknown. Dealing with non-linearities and the multi-scale structure of motion is particularly challenging for the estimation of deformation fields generated by physical processes. Gaussian multiresolution frameworks Bergen et al. (1992) or combined integrated/variational formulations Steinbruecker et al. (2009) have been proposed to circumvent non-linearity and achieve long range displacement estimation from consecutive images. However, the former solutions suffer from a non nested minimization formulation that may impact estimation accuracy, while the latter provide poor results for non-textured images such as images visualizing the transport of a passive scalar. Even worth, as these optic-flow multiresolution schemes work only at very few distinct scales without any explicit connection between scales, estimation of erroneous large scale motions affects severely the whole estimation process. The divergence free constraint ensuing from a volume preserving transformation is in general quite problematic to impose as it comes to solve a Poisson equation which is intrinsically a non local problem. Let us note that the combination of local non linear advection diffusion equation with a global divergence free constraint constitutes one of the major difficulties of Navier-Stokes equations numerical simulation. This constraint is imposed through the pressure field which acts as a Lagrangian penalty variable and requires advanced discretization schemes on staggered grid to prevent oscillations (Girault and Raviart 1986).

In order to circumvent some of the difficulties associated to traditional optical flow multiresolution approaches, and to enable a relevant multi-scale motion estimation, an optical flow scheme based on the wavelet expansion of the motion field has been introduced by Wu et al. (2000). This technique has however a prohibitive computational cost in $O(N^6)$, where $N$ is the number of wavelet coefficients. An extension of this work reducing the algorithm complexity has recently been proposed Dérian et al. (2011). Besides, considering the introduction of a mass preserving constraint, divergence-free wavelets define natural bases for the solutions of the incompressible Navier-Stokes equations. By the localization of basis functions both in scale and space and by their implicit representation in term of divergence-free motions, these wavelets perfectly describe the vortex structures appearing at various scales of the incompressible flow. These bases have been already used in the simulations of the Navier-Stokes equations and for the analyses of incompressible fluid flows, with good results (Deriaz and Perrier 2006). Additionally, expanding the solution on regular wavelet bases enables the easy computation of high-order derivatives and regularization integrals. That have to be mandatory included to cope with the so called aperture problem, which prevents any parametric motion estimation onto too small spatial support.

Gathering these ingredients and constraints, this work aims at proposing a wavelet-based motion estimator that incorporates a high-order smoothing term and a divergence-free condition. Such estimator which extends the approaches of Dérian et al. (2011), Wu et al. (2000) is particularly relevant for the estimation of an incompressible fluid flow from two consecutive images. The divergence free constraint, characterizing the physics of incompressible fluid flows, is imposed by directly estimating coefficients of the optical flow projection onto a divergence-free wavelet basis. The methodology takes also benefits from the wavelet continuous formulation to approach or compute exactly high-order regularization integrals, and avoid unstable discrete approximations of the derivatives. In addition, in order to lower the algorithm complexity, efficient quasi-Newton optimization techniques based on wavelets filter banks and the tensor structure of the separable bases are proposed.

The paper is organized as follows. Section 2 gives a brief overview of the concerned problems and highlights the paper contribution. In Sects. 3 and 4, we recall the basic ingredients of optic-flow computation and wavelets basis construction. In Sect. 5, we perform the biorthogonal wavelet expansion of the motion field which, as we shall see, is necessary to constrain the solution to live in the divergence-free vectorial space. Two approaches for wavelet-based high-order regularization are then introduced in Sect. 6. Numerical results performed on synthetic and real images of 2D and 3D turbulent flows are finally presented and analyzed in Sect. 7.

2 Problematic and Contributions

From a more general point of view, this paper concerns regularized solution $\mathbf{u}^*$ of inverse problem written in variational form as

$$\begin{aligned} \mathbf{u}^*\in \mathop {\text{ arg} \text{ min}}\limits _{\mathbf{u}\in E} F_d(\mathbf{u})+\gamma F_r(\mathbf{u}), \end{aligned}$$

(1)

where $E$ denotes the space of feasible solutions, $F_d$ is a data model adequation term, $F_r$ incorporates some regularization constraints on the solution (smoothness, Sobolev norm, differentiation operators norm) and $\gamma >0$. In this paper, the solution of (1) is searched in terms of its wavelet serie discrete coefficients.

Wavelet bases have the great advantage of providing algorithms for the fast computation of derivative operators. In this context, this paper proposes two simple yet efficient approaches to implement high-order differential constraints on the solution appearing in $F_r$: a discrete intuitive approximation method and a continuous and exact approach, which is theoretically more accurate but requires wavelet basis connection coefficients computation. The former has the advantage to yield a linear computational complexity, but is restricted to isotropic regularization operators, whereas the latter can be used to encode any differential smoothing functional. In this paper we apply the method to the case of optical flow estimation and show that this methodology improves state of the art results.

This paper also provides an elegant wavelet-based framework for implementing optimization problem subject to differential constraints. The latter, which are often imposed by the physic, are of particular importance in image-based fluid flow or medical images analysis (Sass-Hansen et al. 2009). Among them, well-known constraints are the divergence free condition for incompressible flows or the curl free condition for irrotational flows. The originality of the contribution is to propose an efficient and effective framework incorporating those differential constraints directly in the wavelet basis construction. Such a methodology is not restricted only to motion estimation. It could be as well applied to surface reconstruction, tensor field denoising or other computer vision applications that necessitate the respect of differential constraints.

3 Basic Principles of Optical Flow Techniques

This section describes briefly the motion estimation problem, and in particular how it is solved on the canonical basis or on a truncated wavelet basis. The purpose here is not to compare the various approaches proposed so far but rather to introduce general ingredients of wavelets representations and how a motion estimation issue may be handled within such a framework.

3.1 Problem Formulation

Given two images denoted $I_1(\varvec{x})$ and $I_0(\varvec{x})$, motion estimation aims at recovering a velocity field $\mathbf{u}=(u_1,u_2)^T$ minimizing the displaced frame difference (DFD) equation¹:

$$\begin{aligned} I_{1}(\varvec{x}+\mathbf{u}(\varvec{x}))-I_0(\varvec{x})=0, \end{aligned}$$

(2)

hypothesizing a brightness conservation along the trajectory of a 2D image point. Most often, the solution is obtained by minimizing a data adequation term of the form:

$$\begin{aligned} F_d(\mathbf{u})=\frac{1}{2}\int _{{\mathbb{R }}^{2}}\rho \left(I_{1}(\varvec{x}+\mathbf{u}(\varvec{x}))-I_0(\varvec{x})\right)d\varvec{x}, \end{aligned}$$

(3)

where $\rho$ may be a robust penalty function. However, for the clarity of the presentation, we will only consider in the following a standard quadratic cost function. Such a functional is not convex because of the non-linearity of the image function $I_1$. It is in addition ill-posed as it relies on a scalar constraint for a 2D vector field unknown. To cope with this strong limitation either a reduced dimensional parametric representation of the solution or an additional global smoothing constraint is included in the functional. Let us note that in the former case the support of the parametric representation must be sufficiently large in order to circumvent homogeneous photometric areas or step regions with a unique gradient direction for which motion estimation remains ill-posed (the so-called aperture problem).

For small displacements and smooth intensity gradient the DFD may be replaced by its linear differential counterpart, the so-called optical flow constraint equation:

$$\begin{aligned} \partial _t I(\varvec{x},t)+\nabla I(\varvec{x},t)\cdot \mathbf{u}(\varvec{x},t)=0. \end{aligned}$$

We present hereafter strategies to deal with cases that depart significantly from such a linear assumption (large displacements for instance). This problem occurs particularly within the context of fluid flows, where large velocity fluctuations may be observed under condition of low time-sampling frequency.

3.2 Estimation on Standard Basis

An incremental multiresolution strategy stemming from Gauss Newton non-linear least squares is the common method used in optical flow estimation to deal with large displacements (Bergen et al. 1992). This scheme consists to settle an incremental estimation based on the DFD linearization around the current estimation. This approach is in general coupled with a multiresolution pyramidal representation of the image data obtained by successive low pass filtering and subsampling. At a given resolution level, the motion field obtained at coarser level is refined considering a linearization of the DFD around the coarse estimate. This scheme is applied within a coarse-to-fine strategy until the finest resolution level. A severe drawback of the method is that the incremental estimation is thus driven at each resolution level on slightly different data (due to low pass filtering and subsampling), resulting theoretically to different minimization problems at each level. This multiresolution construction hence does not generate a family of nested subspaces of solutions.

4 Standard Wavelet-Based Method

As opposed to the previous strategy, the wavelet-based optical flow approach first introduced by Wu et al. (2000) provides a natural and mathematically consistent multiresolution estimation framework that does not face the theoretical limitations mentioned in Sect. 3. This approach performs the joint estimation of the coefficients of each scalar component of optical flow $\mathbf{u}$ decomposed on a wavelet basis. This decomposition is coherent with the idea used in standard optical flow multiresolution strategy: the inner products with scaling functions are somehow analogous to low-pass filtering operations used for a pyramidal representation. Indeed, wavelet multiresolution analysis is defined by projections onto approximation spaces related to the different scaling functions. The main drawback of the method described in Wu et al. (2000) lies in its high computational cost, caused by the necessity to explicitly evaluate the functional Hessian. Recently, a new wavelet-based method that overcomes this computational burden was proposed by Dérian et al. (2011). The objective in this section is to briefly introduce this method and the principles that underlies the construction of wavelet bases.

4.1 Wavelet-Based Multiresolution Analysis

The wavelet multi-scale analysis of $f\in L^2(\mathbb{R })$ consists in its decomposition in a coarse approximation $\mathcal{P }_0(f)$ and the sum of details $\mathcal{Q }_j(f)$:

$$\begin{aligned} f\!=\!\mathcal{P }_0(f)\!+\!\sum _{j\ge 0}\mathcal{Q }_j(f), \quad \mathcal{Q }_j(f)\!=\!\mathcal{P }_{j\!+\!1}(f)\!-\!\mathcal{P }_j(f),\quad \end{aligned}$$

(4)

where each approximation $\mathcal{P }_j(f)$ corresponds to a projection onto a multiresolution space $V_j$:

$$\begin{aligned} \{0\}\subset \cdots \subset V_j\subset V_{j+1}\subset \cdots \subset L^2(\mathbb{R }), \end{aligned}$$

(5)

and

$$\begin{aligned} V_j=\text{ span}\{\varphi _{j,k}=2^{j/2}\varphi (2^j.-k)\}_{j,k\in \mathbb{Z }}, \end{aligned}$$

(6)

with $\varphi \in L^2(\mathbb{R })$ the multiresolution analysis scaling function, $j$ and $k$ are the scale and position indices respectively.

In the following, we will consider the context of biorthogonal multiresolution analyses (Cohen et al. 1992), which is more general than the orthogonal one (Mallat 2008). Then, there exists another multiresolution analysis denoted $\{{\tilde{V}}_j\}_{j\in \mathbb{Z }}$ with a scaling function ${\tilde{\varphi }}$ such that:

$$\begin{aligned} \mathcal{P }_j(f):=\sum _{k\in \mathbb{Z }} c_{j,k}\varphi _{j,k}\quad \text{ and}\quad c_{j,k} =\langle {\tilde{\varphi }}_{j,k},f\rangle . \end{aligned}$$

(7)

The wavelet basis $\{\psi _{j,k}\}_{k\in \mathbb{Z }}$ is defined as an unconditional basis of detail space $W_j$:

$$\begin{aligned} V_{j+1}=V_j\oplus W_j,\quad \quad W_j=V_{j+1}\cap ({\tilde{V}}_j)^\perp . \end{aligned}$$

(8)

Similarly, we have $W_j=\text{ span}\{\psi _{j,k}\,:\,k\in \mathbb{Z }\}$ and the projection $\mathcal{Q }_j(f)$ is computed using the dual wavelet basis:

$$\begin{aligned} \mathcal{Q }_j(f):=\sum _{k\in \mathbb{Z }}d_{j,k}\psi _{j,k} \quad \text{ and}\quad d_{j,k}=\langle {\tilde{\psi }}_{j,k},f\rangle , \end{aligned}$$

(9)

where ${\tilde{\psi }}_{j,k}$ corresponds to dual wavelet basis.

This construction of wavelet bases can be extended easily to $L^2(\mathbb{R }^d) (d>1$) in higher dimension, using tensor product of the one-dimensional wavelet basis (Mallat 2008). Precisely, for any pair of vectors $\mathbf{u}$ and $\mathbf{v}$ of $\mathbb{R }^d$, we define the matrix of tensor product $\mathbf{u}\otimes \mathbf{v}$ by:

$$\begin{aligned}{}[\mathbf{u}\otimes \mathbf{v}]_{i,j}:=u_iv_j, \;1\le i,j\le d. \end{aligned}$$

(10)

Then, using (10) and from a multiresolution analysis $\{V_j\}_{j\in \mathbb{Z }}$ of $L^2(\mathbb{R })$, with scaling function $\varphi$, we define the space $V_j\otimes V_j$ by:

$$\begin{aligned} V_j\otimes V_j=\text{ span}\left\{ \varphi _{j,k_1}\otimes \varphi _{j,k_2} :\,k_1,\,k_2\in \mathbb{Z }\right\} ,\,j\in \mathbb{Z }, \end{aligned}$$

(11)

with

$$\begin{aligned} \varphi _{j,k_1}\otimes \varphi _{j,k_2}(x,y) :=\varphi _{j,k_1}(x)\varphi _{j,k_2}(y). \end{aligned}$$

(12)

Thus, the spaces $(V_j\otimes V_j)_{j\in \mathbb{Z }}$ constitute a multiresolution analysis of $L^2(\mathbb{R }^2)$. In this case, to construct the associated wavelet basis we can proceed in two ways: isotropic construction or anisotropic construction. The isotropic construction is the most used and it leads to $(2^d-1)$ types of wavelet generators in $L^2(\mathbb{R }^d)$, see Mallat (2008) for details. The anisotropic construction is less used and leads to a single wavelet generator with $d$ parameters of scale and position respectively. Indeed, in the two dimensional case ($d=2$) for example, from (8), it is easy to see that the spaces $V_j$ verify:

$$\begin{aligned} V_{j}=V_0\oplus W_1\oplus \cdots \oplus W_{j-1},\quad \quad j>0. \end{aligned}$$

Then, the space $V_j\otimes V_j$ can be decomposed as:

$$\begin{aligned}&V_{j}\otimes V_{j}=\left(V_0\otimes V_{0}\right) \bigoplus _{j_1,j_2=0}^{j-1}\left(W_{j_1}\otimes W_{j_2}\right)\nonumber \\&=\left(V_0\oplus W_1\oplus \cdots \oplus W_{j-1}\right) \otimes \left(V_0\oplus W_1\oplus \cdots \oplus W_{j-1}\right)\nonumber \\&=\left(V_{0}\otimes V_{0}\right)\oplus \left(V_{0} \otimes W_{0}\right)\oplus \left(W_{0}\otimes V_{0}\right)\oplus \cdots \end{aligned}$$

The corresponding wavelet basis is thus constituted by:

$$\begin{aligned} \left\{ \varPsi _{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}(x,y):=\psi _{j_1,k_1}(x)\psi _{j_2,k_2}(y) :j_1,j_2,k_1,k_2\in \mathbb{Z }\right\} . \end{aligned}$$

For vector space $(L^2(\mathbb{R }^d))^d$, the construction is done in accordance for each component. For example, a multiresolution analysis of $(L^2(\mathbb{R }^2))^2$ is provided by:

$$\begin{aligned} \mathbf{V}_j=\left(V_j\otimes V_j\right)\times \left(V_j\otimes V_j\right):=\left(\begin{array}{ll} V_j\otimes V_j\\ \;\\ V_j\otimes V_j \end{array}\right). \end{aligned}$$

(13)

4.2 Standard Wavelet-Based Flow Estimation

Let us introduce some shorthand notations: the 2D scaling function basis of $V_j\otimes V_j$ is denoted $\varPhi _j$, and $\varPsi _{{{{{\varvec{j}}}}}}$, $|{{{{{\varvec{j}}}}}} |\le j$ the corresponding anisotropic wavelets basis. Similarly for the dual space ${\tilde{V}}_j\otimes {\tilde{V}}_j$ with ${\tilde{\varPhi }}_j$ and ${\tilde{\varPsi }}_{{{{{\varvec{j}}}}}}$. For $f\in L^2(\mathbb{R }^2)$, the associated multi-scale projectors are denoted:

$$\begin{aligned} \mathcal{P }_j(f)=\left\langle {\tilde{\varPhi }}_j,f\right\rangle {\varPhi }_j,\quad \quad \mathcal{Q }_{{{{{\varvec{j}}}}}}(f)=\langle {\tilde{\varPsi }}_{{{{{\varvec{j}}}}}}, f\rangle {\varPsi }_{{{{{\varvec{j}}}}}},\quad |{{{{{\varvec{j}}}}}}|\le j, \end{aligned}$$

and we make the same conventions in $(L^2(\mathbb{R }^2))^2$ with:

$$\begin{aligned} \mathbf{P}_j(\mathbf{f})=\langle {\varvec{\tilde{\Phi }}}_j,\mathbf{f}\rangle {\varvec{\Phi }}_j,\quad \quad \mathbf{Q}_{{{{{\varvec{j}}}}}}(\mathbf{f})=\langle {\tilde{\varvec{\Psi }}}_{{{{{\varvec{j}}}}}},\mathbf{f}\rangle {\varvec{\Psi }}_{{{{{\varvec{j}}}}}},\;|{{{{{\varvec{j}}}}}} |\le j. \end{aligned}$$

With the previous shorthand notations, the method of Dérian et al. (2011) consists in searching, at each scale $j$, motion field $\mathbf{u}_j$ represented on a wavelet basis at scale j:

$$\begin{aligned} \mathbf{u}_j(\varvec{x})=\mathbf{d}_j{\varvec{\Psi }}_{{{{{\varvec{j}}}}}}(\varvec{x}),\quad \mathbf{d}_j=\langle {\varvec{\tilde{\Psi }}}_{{{{{\varvec{j}}}}}},{\mathbf{u}}\rangle ,\quad |{{{{{\varvec{j}}}}}} |\le j, \end{aligned}$$

(14)

where ${\varvec{\Psi }}_{{{{{\varvec{j}}}}}}$ is the selected 2D wavelet basis and $\mathbf{d}_j$ the vector of unknown coefficients that have to be estimated to represent the sought motion components. Incorporating (14) in the (DFD) equation and setting $I_1(\varvec{x},\mathbf{d}_j)=I_1(\varvec{x}+\mathbf{d}_j{\varvec{\Psi }}_{{{{{\varvec{j}}}}}}(\varvec{x}))$, the gradient of $F_d$ according to the unknown coefficients reads:

$$\begin{aligned} \nabla F_d(\mathbf{d}_j)=\int \left[I_1(\varvec{x}, \mathbf{d}_j)-I_0(\varvec{x})\right]\nabla I_1(\varvec{x}, \mathbf{d}_j)\cdot {\varvec{\Psi }}_{{{{{\varvec{j}}}}}}(\varvec{x}) d\varvec{x}. \end{aligned}$$

As a consequence, components of the gradient $\nabla F_d(\mathbf{d}_j)$ of the functional are simply given by the coefficients of the wavelet decomposition of the two gradient components:

$$\begin{aligned} \left[I_1(\varvec{x}, \mathbf{d}_j)-I_0(\varvec{x})\right]\nabla I_1(\varvec{x}, \mathbf{d}_j), \end{aligned}$$

(15)

on the considered dual wavelet basis. For a given motion field, they can be easily computed using a 2D fast wavelet transform (Mallat 2008), with the filter bank associated to ${\varvec{\Psi }}_{{{{{\varvec{j}}}}}}$. At a given scale, an estimation of the gradient functional from the previous scale is thus immediately accessible. This gives rise to a straightforward gradient descent process, in which the previous iteration $\mathbf{d}_{j+1}$ is fixed from the preceding scale $\mathbf{d}_{j}$. This proposed coarse-to-fine estimation strategy enables to capture large displacements: at large scales, the decomposition of (15) is obtained by convolutions with the atoms of the wavelet basis having the largest support. A gradient descent method is used then to minimize efficiently the functional $F_d$. The aperture problem can be here jointly addressed by reducing the problem dimension with a simple basis truncation: coefficients associated to smallest scales are not estimated, assuming the finest wavelet support is large enough to cope with homogeneous areas or gradients unique direction (linear step in-between two homogeneous regions). Obviously, the choice of this finest scale is not an easy issue in general. It constitutes the pitfall of local estimation procedure and should be handled with sound adaptive strategy. The other solution consists in adjoining an additional smoothing constraint to the functional. This will be further detailed in Sect. 6.

We summarize below the coarse-to-fine wavelet estimation strategy for images of size $2^J\times 2^J$. To estimate the motion at scale $j<J$, starting with an initial coefficients $\mathbf{d}_j$ of length $2\times 2^j\times 2^j$, one step of the optimization procedure requires to:

• 1. Compute ${\mathbf{u}}_j$  it at fine grid points by extrapolation.

• 2. Compute $I_1(\varvec{x}+{\mathbf{u}}_j)$  using interpolation.

• 3. Evaluate $F_d$ on ${\mathbf{u}}_j$  using quadrature formula.

• 4. Compute $\nabla I_1(\varvec{x}+{\mathbf{u}}_j)$  it with finite difference method.

• 5. Compute the gradient $\nabla F_d(\mathbf{d}_j)$  to implement a gradient descent method.

• 6. Update the coefficients:  $\mathbf{d}_{j+1}=\mathbf{d}_j+\alpha \nabla F_d(\mathbf{d}_j)$ ².

Wavelet bases are used only in Step 1 and Step 5. Precisely, Step 1 corresponds to an inverse fast wavelet transform on coefficients $\mathbf{d}_j$ and Step 5 corresponds to the fast wavelet transform of $\left[I_1(\varvec{x}+{\mathbf{u}}_j)-I_0(\varvec{x})\right]\nabla I_1(\varvec{x}+{\mathbf{u}}_j)$. Thus, the theoretical complexity of these steps is $O(N)$, with $N=2^J\times 2^J$.

Additionally to the necessity of adjoining a regularization term to reach the finest scale levels it is also in some situation mandatory to consider additional physical constraints in the estimation process. This is the case when one aims for instance at estimating volume preserving or diffeomorphic transformation. Such constraints are generally imposed through differential constraints. Wavelet bases specifically designed to satisfy theses relations may be advantageous. In the following, we show how the estimation of a volume preserving transformation may be taken into account in the wavelet design.

5 Divergence-Free Wavelet-Based Method

Vector field analysis is ubiquitous in almost all the scientific domains. The Helmholtz decomposition theorem, sometimes referred as the fundamental theorem of vector calculus, states that any sufficiently smooth vector field $\mathbf{u}\in (L^2(\mathbb{R }^d))^d$ can be decomposed uniquely in the form:

$$\begin{aligned} \mathbf{u}=\mathbf{u}^\mathrm{div }+\mathbf{u}^\mathrm{curl }, \end{aligned}$$

(16)

with

$$\begin{aligned} \mathbf{div}(\mathbf{u}^\mathrm{div })=0\quad \quad \text{ and}\quad \quad \mathbf{curl}(\mathbf{u}^\mathrm{curl })=0. \end{aligned}$$

(17)

Constraints like (17) appear in many computer vision problems (for example in medical image registration Kohlberger et al. 2003, image restoration Simard and Mailloux 1998, optical flow estimation Papadakis et al. 2007; Ruhnau and Schnörr 2007, or in engineering problems (incompressible turbulence flow simulation).

In the case of optical flow estimation, since the cost function defined in (3) is under constrained, to make its minimization mathematically well-posed, it is important to introduce some prior knowledge on the kind of typical flow one expects to estimate. The estimation of diffeomorphic transformation (Simard and Mailloux 1998) or of mass preserving fluid flow (Papadakis et al. 2007; Ruhnau and Schnörr 2007) leads to consider divergence-free motion field. To achieve this, the minimization is coupled with a resolution of incompressible Stokes system of partial differential equations, which requires discretization on staggered grids to get stable solution (Yuan et al. 2007).

Wavelet bases can be designed to implicitly represent divergence-free or curl-free motions (Deriaz and Perrier 2006). Without loss of generality, we will focus on the divergence-free constraint. The curl-free constraint or harmonic constraint (i.e, both divergence-free and curl-free) can be treated similarly. Then, the purpose of this section is to introduce the construction of anisotropic divergence-free wavelet bases in $(L^2(\mathbb{R }^2))^2$ that are used to define a divergence-free wavelet based method for optical flow estimation. For more detail on divergence-free wavelet bases construction see “Appendix” and references Deriaz and Perrier (2006), Lemarié-Rieusset (1992).

5.1 Divergence-Free Wavelet Basis

The objective in this section is to recall briefly the anisotropic divergence-free wavelet basis construction (Deriaz and Perrier 2006; Lemarié-Rieusset 1992) for the divergence-free functions space $\mathcal{H }_{div}(\mathbb{R }^2)$:

$$\begin{aligned} \mathcal{H }_{div}({\mathbb{R }}^{2})=\{\mathbf{u}\in (L^2(\mathbb{R }^2))^2\,:\,\nabla \cdot \mathbf{u}=0\}. \end{aligned}$$

(18)

Alternatively, the space $\mathcal{H }_{div}(\mathbb{R }^2)$ can also be seen as the curl ³ vector potential space (Girault and Raviart 1986)⁴:

$$\begin{aligned} \mathcal{H }_{div}(\mathbb{R }^2)=\{\mathbf{u}=\mathbf{curl}(\chi )\,:\,\chi \in H^1(\mathbb{R }^2)\}. \end{aligned}$$

(19)

Let us recall the following formal identities, valid for $d=2$ and $d=3$:

$$\begin{aligned} \mathbf{div}(\mathbf{curl})=0\quad \quad \text{ and}\quad \quad \mathbf{curl}(\nabla )=0. \end{aligned}$$

From (19), to construct a multiresolution analysis of $\mathcal{H }_{div}(\mathbb{R }^2)$, it is natural to take the curl of a “regular” scalar multiresolution analysis of $H^1(\mathbb{R }^2)$. For this purpose, let $\varphi ^1$ be a scaling function associated to the wavelet $\psi ^1$, with $\varphi ^1\in \mathcal{C }^{1+\epsilon }(\mathbb{R })$, $\epsilon >0$. Since we use tensor product, the divergence-free scaling functions spaces defined by:

$$\begin{aligned} \mathbb V ^{div}_j=\text{ span}\left\{ {{\varvec{\Phi }}} ^{div}_{j,{{{{{\varvec{k}}}}}}};\,{{{{{\varvec{k}}}}}}\in \,\mathbb{Z }^2,\,j\in \,\mathbb{Z }\right\} , \end{aligned}$$

(20)

where

$$\begin{aligned} {{\varvec{\Phi }}}^{div}_{j,{{{{{\varvec{k}}}}}}}=\mathbf{curl} \left[\varphi ^1_{j,k_1}\otimes \varphi ^1_{j,k_2}\right] = \left( \begin{array}{ll} \;\varphi ^1_{j,k_1}\otimes {(\varphi ^1_{j,k_2})}^{\prime }\\ \, \\ - {(\varphi ^1_{j,k_1})}^{\prime }\otimes \varphi ^1_{j,k_2} \end{array} \right), \end{aligned}$$

constitute a multiresolution analysis for $\mathcal{H }_{div}(\mathbb{R }^2)$ (Deriaz and Perrier 2006; Lemarié-Rieusset 1992). Similarly, for ${{{{{\varvec{j}}}}}}, {{{{{\varvec{k}}}}}}\in \mathbb{Z }^2$, the associated anisotropic divergence-free wavelet spaces are defined by:

$$\begin{aligned} \mathbb W ^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}} =\text{ span}\left\{ {\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}};\,{{{{{\varvec{j}}}}}},\,{{{{{\varvec{k}}}}}} \in \,\mathbb{Z }^2\right\} , \end{aligned}$$

(21)

with

$$\begin{aligned} {\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}} =\mathbf{curl} \left[\psi ^1_{j_1,k_1}\otimes \psi ^1_{j_1,k_2}\right]= \left( \begin{array}{ll} \psi ^1_{j_1,k_1}\otimes (\psi ^1_{j_2,k_2})^{\prime }\\ \, \\ - (\psi ^1_{j_1,k_1})^{\prime }\otimes \psi ^1_{j_2,k_2} \end{array} \right). \end{aligned}$$

Where $\psi ^0$ is another wavelet linked to $\psi ^1$ by differentiation, see “Appendix”:

$$\begin{aligned} (\psi ^1(x))^{\prime }=4\psi ^0(x), \end{aligned}$$

(22)

thus,

$$\begin{aligned} {\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}} =\left( \begin{array}{ll} 2^{j_2+2}\psi ^1_{j_1,k_1}\otimes \psi ^0_{j_2,k_2}\\ \, \\ - 2^{j_1+2}\psi ^0_{j_1,k_1}\otimes \psi ^1_{j_2,k_2} \end{array} \right). \end{aligned}$$

These wavelets are biorthogonal (Deriaz and Perrier 2006) and every vector field $\mathbf{u}\in \mathcal{H }_{div}(\mathbb{R }^2)$ can be decomposed uniquely as:

$$\begin{aligned} \mathbf{u}=\sum _{{{{{{\varvec{j}}}}}},\mathbf{k}\in \mathbb{Z }^2}\left\langle \mathbf{u}, \tilde{\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}} \right\rangle {\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}=\sum _{{{{{{\varvec{j}}}}}},\mathbf{k } \in \mathbb{Z }^2}\mathbf{d}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}{\varvec{\Psi }} ^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}, \end{aligned}$$

(23)

where $\langle .,.\rangle$ denotes the $(L^2(\mathbb{R }^2))^2$—inner product between two vector functions. In Fig. 1, we plot an example of vector fields and corresponding vorticities of the divergence-free scaling function generator and wavelet generator, constructed from Coifflet $\varphi ^1$ and $\psi ^1$ with ten vanishing moments.

Fig. 1

Vector fields and vorticity of divergence-free scaling functions and wavelets generators constructed from Coifflet $\varphi ^1$ and $\psi ^1$ with ten vanishing moments

Remark 1

In practice, as mentioned earlier two types of divergence-free wavelet can be built: the isotropic construction (Lemarié-Rieusset 1992) and the anisotropic one (Deriaz and Perrier 2006). The isotropic divergence-free wavelet construction on $\mathbb{R }^d$ uses $(d-1)(2^d-1)$ types of wavelet generators with one parameter of dilatation and $d$ parameters of translation, while the anisotropic one uses only $(d-1)$ types of wavelet generators with $d$ parameters of dilation and translation. Thus, for $d=2$, we have one divergence-free wavelet generator in the anisotropic construction.

5.2 Divergence-Free Wavelet-Based Flow Estimation

The estimation method developed in this section provides a solution to the optical flow estimation problem subject to a divergence-free constraint. The proposed approach falls within the context of wavelet-based multiresolution methods (Dérian et al. 2011) sketched in the previous section. Then, the velocity field $\mathbf{u}$ is searched in terms of its divergence-free wavelet projection (23)

$$\begin{aligned} \mathbf{u}(\varvec{x})=\sum _{{{{{{\varvec{j}}}}}},\mathbf{k }\in \mathbb{Z }^2}\mathbf{d}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}{\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}(\varvec{x}), \end{aligned}$$

and its estimation is reduced to the estimation of its divergence-free wavelet coefficients.

At a scale $j$, let us adopt the notation:

$$\begin{aligned} I_1(\varvec{x},\mathbf{d}_j^{div})=I_{1}\left(\varvec{x}+\sum _{|{{{{{\varvec{j}}}}}}|\le j,{{{{{\varvec{k}}}}}}\in \mathbb{Z }^2}\mathbf{d}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}{\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}(\varvec{x})\right). \end{aligned}$$

The $\mathbf{d}_j^{div}$ coefficients are hence defined as the minimizers of the objective function:

$$\begin{aligned} F_d(\mathbf{d}_j^{div})=\frac{1}{2}\int _{{\mathbb{R }}^{2}}\left[ I_1(\varvec{x},\mathbf{d}_j^{div})-I_0(\varvec{x})\right]^2d\varvec{x}, \end{aligned}$$

(24)

where $\mathbf{d}_j^{div}$ is now defined as the set of the divergence-free wavelets coefficients $\{\mathbf{d}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}\}$. Optimization is carried out by a quasi-Newton method (LBFGS), where a BFGS approximation of the Hessian relying solely on the current gradient is handled. The optimal gradient step is in addition given in the sense of the strong Wolf conditions (Nocedal and Wright 1999). Obviously, besides the evaluation of the functional $F_d$, the descent optimization algorithm requires the computation of its gradient at each iteration step. These computations also are facilitated by the wavelet formulation. As a matter of fact, the gradient $\nabla F_d(\mathbf{d}_j^{div})$ corresponds to:

$$\begin{aligned} \nabla F_d\!=\!\int _{{\mathbb{R }}^{2}}\left[I_{1}\left(\varvec{x}\!,\mathbf{d}_j^{div}\right)\!-\!I_0(\varvec{x})\right]\nabla I_{1}\left(\varvec{x}\!,\mathbf{d}_j^{div}\right)\!\cdot \!{\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}}, {{{{{\varvec{k}}}}}}}(\varvec{x})d\varvec{x}, \end{aligned}$$

Let $\nabla I_{x_1}(\varvec{x},\mathbf{d}_j^{div})$ and $\nabla I_{x_2}(\varvec{x},\mathbf{d}_j^{div})$ denote the scalar components of vector $\left[I_{1}\left(\varvec{x},\mathbf{d}_j^{div}\right)\!-\!I_0(\varvec{x})\right]\nabla I_{1}\left(\varvec{x},\mathbf{d}_j^{div}\right)$:

$$\begin{aligned} \nabla I_{x_1}\left(\varvec{x},\mathbf{d}_j^{div}\right)\!=\!\left[I_{1}\left(\varvec{x},\mathbf{d}_j^{div}\right)\!-\!I_0(\varvec{x})\right]\partial _{x_1} I_{1}\left(\varvec{x},\mathbf{d}_j^{div}\right),\nonumber \\ \end{aligned}$$

(25)

and

$$\begin{aligned} \nabla I_{x_2}\left(\varvec{x},\mathbf{d}_j^{div}\right)\!=\!\left[I_{1}\left(\varvec{x},\mathbf{d}_j^{div}\right)\!-\!I_0(\varvec{x})\right]\partial _{x_2} I_{1}\left(\varvec{x},\mathbf{d}_j^{div}\right).\nonumber \\ \end{aligned}$$

(26)

Since,

$$\begin{aligned} \nabla I_{1}\left(\varvec{x},\mathbf{d}_j^{div}\right)\!\cdot \!{\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}(\varvec{x})\;=\;\partial _{x_1} I_{1}\left(\varvec{x},\mathbf{d}_j^{div}\right)\psi ^1_{j_1,k_1}\!\otimes \!\left(\psi ^1_{j_2,k_2}\right)^{\prime }\\&\!-\!\partial _{x_2} I_{1}\left(\varvec{x}\!,\mathbf{d}_j^{div}\right)\left(\psi ^1_{j_1\!,k_1}\right)^{\prime }\!\otimes \!\psi ^1_{j_2,k_2} \end{aligned}$$

and

$$\begin{aligned} \left(\psi ^1_{j,k}\right)^{\prime }=2^{j+2}\psi ^0_{j,k}, \end{aligned}$$

the computation of $\nabla F_d(\mathbf{d}_j^{div})$ thus reduces to a simple linear combination of two sets of scalar coefficients obtained by a two dimensional fast wavelet transforms (Mallat 2008): the scalar wavelet coefficients of $\nabla I_{x_1}(\varvec{x},\mathbf{d}_j^{div})$, in the wavelet basis generated by $\psi ^1_{j_1,k_1}\otimes \psi ^0_{j_2,k_2}$, and those of $\nabla I_{x_2}(\varvec{x},\mathbf{d}_j^{div})$, in the wavelet basis generated by $\psi ^0_{j_1,k_1}\otimes \psi ^1_{j_2,k_2}$.

Precisely, let ${\tilde{\mathbf{d }}}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^{1}$ and ${\tilde{\mathbf{d }}}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^{2}$ be the set of these coefficients:

$$\begin{aligned} {\tilde{\mathbf{d }}}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^{1}&= \int _{{\mathbb{R }}^{2}}\nabla I_{x_1}\left(\varvec{x},\mathbf{d}_j^{div}\right)\psi ^1_{j_1,k_1}\otimes \psi ^0_{j_2,k_2}d\varvec{x},\nonumber \\ {\tilde{\mathbf{d }}}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^{2}&= \int _{{\mathbb{R }}^{2}}\nabla I_{x_2}\left(\varvec{x},\mathbf{d}_j^{div}\right)\psi ^0_{j_1,k_1}\otimes \psi ^1_{j_2,k_2}d\varvec{x}, \end{aligned}$$

we get:

$$\begin{aligned} \nabla F_d\left(\mathbf{d}_j^{div}\right)=\left[2^{j_2+2} {\tilde{\mathbf{d }}}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^{1}-2^{j_1+2} {\tilde{\mathbf{d }}}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^{2}\right]. \end{aligned}$$

(27)

Remark 2

The coefficients used in the computation of $\nabla F_d(\mathbf{d}_j^{div})$ correspond to the dual scalar wavelet bases. To be more precise, according to (7), by definition coefficients ${\tilde{\mathbf{d }}}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^{1}$ correspond to the decomposition of $\nabla I_{x_1}(\varvec{x},\mathbf{d}_j^{div})$ on the scalar basis generated by $\{{\tilde{\psi }}^1_{j_1,k_1}\otimes \tilde{\psi }^0_{j_2,k_2}\}$ and ${\tilde{\mathbf{d }}}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^{2}$ correspond to the decomposition of $\nabla I_{x_2}(\varvec{x},\mathbf{d}_j^{div})$ on the scalar basis generated by $\{{\tilde{\psi }}^0_{j_1,k_1}\otimes {\tilde{\psi }}^{1}_{j_2,k_2}\}$.

As in the standard wavelet method, to estimate the motion at scale $j<J$, starting with initialization coefficients $\mathbf{d}^{div}_j$ of length $2^j\times 2^j$, one step of the optimization procedure requires to:

• 1c. Compute ${\mathbf{u}}_j$  it at fine grid points by extrapolation.

• 2c. Compute $I_1(\varvec{x}+{\mathbf{u}}_j)$ using spline interpolation.

• 3c. Evaluate $F_d(\mathbf{d}^{div}_j)$ on ${\mathbf{u}}_j$ using quadrature formula.

• 4c. Compute $\nabla I_1(\varvec{x}+{\mathbf{u}}_j)$ with finite difference method.

• 5c. Compute the gradient $\nabla F_d(\mathbf{d}^{div}_j)$.

• 6c. Update the coefficients: $\mathbf{d}^{div}_{j+1}=\mathbf{d}^{div}_j+\alpha \nabla F_d(\mathbf{d}^{div}_j)$.

Step 1c uses the inverse fast divergence-free wavelet transform, to compute $\mathbf{u}_j$ at fine grid points, from its divergence-free wavelets coefficients (see “Appendix”). Step 5c uses (27). Thus, the theoretical complexity of the algorithm is also $O(N)$.

The main advantage of this divergence-free wavelet method, compared to the standard wavelet method, is that it reduces the solution space to a specific subspace respecting the imposed constraint. In addition, the number of degrees of freedom is divided by two: the length of $[\mathbf{d}^{div}_j]$ is $2^j\times 2^j$, instead of $2\times 2^j\times 2^j$. Nevertheless, although the divergence-free constraint is in theory sufficient to close the optic flow problem, due to weak gradients, estimation in practice remains generally poorly conditioned. Consequently, at fine resolution this method faces limitation similar to any basis with respect to the aperture problem.

6 High-Order Regularization

The resolution of inverse problems is complicated by the fact that these problems are generally ill-conditioned. It is therefore necessary to add constraints that reduce the space of possibilities to achieve a unique solution. In this section, we are interested by constraints on the regularity of the solution, expressed through high-order differentiation operators. Without loss of generality, we describe methods for computing these operators effectively using wavelet bases, in the case of optical flow estimation.

Optical flow estimation is one class of inverse problem. Morever, as mentioned earlier Eq. (2) is a scalar constraint involving two unknowns $u_1$ and $u_2$. Following Dérian et al. (2011), in Sects. 4 and 5, we have shown that truncating at small scales the wavelet expansion of the solution $\mathbf{u}$ yields to interesting coarse scale polynomial approximations of the solution. Nevertheless, in the context of optical flow and especially in the context of fluid motion, the accurate estimation at small scales constitutes a crucial issue. A common approach is to introduce some prior knowledge on the solution regularity (Horn and Schunck 1981; Yuan et al. 2007). Subsequently, the objective is to investigate this technique in the advantageous context of standard wavelet-based method or divergence-free wavelet-based method.

To make well-conditioned the minimization problem defined in (3), one classically adds a convex regularization term $F_r$. The objective function $F_d$ given by (3) is then replaced by:

$$\begin{aligned} F(\mathbf{u})=F_d(\mathbf{u})+\gamma F_r(\mathbf{u}), \end{aligned}$$

(28)

with the parameter $\gamma >0$ that balances data and regularization terms. The value of this weight needs to be adapted, which might be a non-trivial task in practice.

In the following, we focus on three different high-order regularizers terms $F_r(\mathbf{u})$. Some of them have proven to be particularly adapted to fluid flows (Heitz et al. 2010). They are all based on the quadratic penalization of high-order derivatives.

A first possibility is to penalize discrepancies of the velocity field in each direction from a polynomial of degree $n$ (i.e, penalize derivative of order $n\in \mathbb{N }^*$):

$$\begin{aligned} F_r(\mathbf{u})=\int _{{\mathbb{R }}^{2}}\sum \limits _{\mathop {1 \le i\le 2}\limits _{1\le \ell \le 2}} \left|\partial ^n_{x_i}u_\ell (\varvec{x})\right|^2 d\varvec{x}. \end{aligned}$$

(29)

Other approaches consist in favoring coherent vortex blobs by a second-order curl regularization:

$$\begin{aligned} F_r(\mathbf{u})=\int _{{\mathbb{R }}^{2}} \left|\nabla (\partial _{x_2} u_1(\varvec{x})-\partial _{x_1} u_2(\varvec{x}))\right|^2 d\varvec{x}, \end{aligned}$$

(30)

or approaching solutions of the heat equation:

$$\begin{aligned} F_r(\mathbf{u})=\int _{{\mathbb{R }}^{2}} \sum \limits _{1 \le \ell \le 2}\left|\varDelta u_\ell (\varvec{x})\right|^2 d\varvec{x}. \end{aligned}$$

(31)

One can notice that regularizers (30) and (31) become identical in the case of divergence-free flows. Indeed, there exist a stream function $\chi$ such as:

$$\begin{aligned} \mathbf{u}=\mathbf{curl} \chi ,\quad \text{ with}\quad \chi \in H^1(\mathbb{R }^2). \end{aligned}$$

(32)

From the definition of curl operator in 2D, one can prove that:

$$\begin{aligned} -\varDelta \chi =\mathbf{curl} (\mathbf{u}), \end{aligned}$$

(33)

and this implies:

$$\begin{aligned} \left|\nabla \mathbf{curl} (\mathbf{u})\right|^2 \!=\!\left|-\!\nabla \varDelta \chi \right|^2 \!=\!\left|\partial _{x_1}\varDelta \chi \right|^2 \!+\!\left|\partial _{x_2}\varDelta \chi \right|^2. \end{aligned}$$

(34)

Using again Eq. (32), we obtain:

$$\begin{aligned} \left|\varDelta (\mathbf{u})\right|^2=\left|\varDelta (\mathbf{curl} \chi )\right|^2=\left|\partial _{x_1}\varDelta \chi \right|^2 +\left|\partial _{x_2}\varDelta \chi \right|^2. \end{aligned}$$

(35)

In most classical methods, the operators of differentiation that appear in the previous regularizers (29), (30) and (31) are evaluated using finite difference methods. This leads to complex advanced discrete schemes that must be carefully designed to avoid numerical instabilities or oscillations.

The wavelet context offers an ideal setting to make such computation accurately with less effort. In this paper, we present two different wavelet-based schemes for high-order regularization of inverse problems. Both regularization schemes do not rely on any finite difference discrete approximation of spatial derivatives. The first approach, which is described in Sect. 6.1, is a discrete approximation of regularization integrals. It presents the advantage to be intrinsically very simple since regularization is achieved by penalization of a subset of wavelet coefficients. The second scheme, which is described in Sect.  6.2, constitutes a very interesting approach since it enables the exact computation of continuous regularization integrals without much more effort. In the two cases, the underlying algorithms have the same theoretical complexity.

6.1 Operator Discrete Approximation Method

In this section we describe an intuitive discrete approximation of the high-order regularization integral (29). The method is based upon differentiation properties of wavelets.

The derivative of a regular wavelet basis is another wavelet basis, see (53) of “Appendix”, with analogous properties of $L^2(\mathbb{R })$ signal decomposition and reconstruction. Then, for $n\in \mathbb{N }^*$ and sufficiently smooth biorthogonal wavelet generators $(\psi ,\tilde{\psi })$, let $(\theta ,\tilde{\theta })$ be the biorthogonal wavelet generators obtained by applying successively $n$ times the relations of (53):

$$\begin{aligned} \frac{d^n}{dx^n}\psi =4^n\theta \quad \quad \text{ and}\quad \quad \frac{d^n}{dx^n}\tilde{\theta }=(-4)^n\tilde{\psi }. \end{aligned}$$

(36)

For any smooth function $f\in L^2(\mathbb{R })$, we have:

$$\begin{aligned} \frac{d^n}{dx^n}f(x)=\sum _{j,k\in \mathbb{Z }}{\bar{d}}_{j,k}\theta _{j,k}(x), \quad {\bar{d}}_{j,k}=\left\langle \frac{d^n}{dx^n}f, {\tilde{\theta }}_{j,k}\right\rangle . \end{aligned}$$

Since $\{\theta _{j,k}\}_{j,k\in \mathbb{Z }}$ is a Riesz basis of $L^2(\mathbb{R })$, we have:

$$\begin{aligned} \left\Vert\frac{d^n}{dx^n}f\right\Vert_{L^2(\mathbb{R })}\sim \left\Vert\bar{d}_{j,k}\right\Vert_{\ell ^2(\mathbb{Z }^2)}. \end{aligned}$$

Formally, using integration by part and relation (36), we get:

$$\begin{aligned} \int _{\mathbb{R }}\frac{d^n}{dx^n}f(x){\tilde{\theta }}_{j,k}(x)dx =(-4)^n2^{nj}\int _{\mathbb{R }}f(x){\tilde{\psi }}_{j,k}(x)dx. \end{aligned}$$

Setting $d_{j,k}=\langle f,{\tilde{\psi }}_{j,k}\rangle$, one obtains:

$$\begin{aligned} \bar{d}_{j,k}=(-4)^n2^{nj}d_{j,k}, \end{aligned}$$

thus

$$\begin{aligned} \left\Vert\frac{d^n}{dx^n}f\right\Vert_{L^2(\mathbb{R })}\sim \left\Vert(-4)^n2^{nj} d_{j,k}\right\Vert_{\ell ^2(\mathbb{Z }^2)}. \end{aligned}$$

(37)

Since the computation of coefficient $d_{j,k}=\langle f,{\tilde{\psi }}_{j,k}\rangle$ involves only $f$ instead of $\frac{d^n}{dx^n}f$, the penalization of wavelet coefficients’ amplitude thus enables to control the amplitude of the derivative of the estimated signal.

A proof of previous formal calculations can be found in Kahane and Lemarié-Rieusset (1995) and the results can be extended easily to the case of 2D signals.

To control derivatives of motion components in the neighborhood of points in $\varOmega \subset \mathbb{R }^2$, which is defined as the set of translation at the finest scale of the dyadic discrete wavelet decomposition, one can use (37):

$$\begin{aligned} F_r(\mathbf{u})\sim \sum _{j,k}4^{nj}\left|d_{j,{{{{{\varvec{k}}}}}}}^\ell \right|^2,\quad \ell =1,2, \end{aligned}$$

(38)

where $d_{j,{{{{{\varvec{k}}}}}}}^\ell$ denotes the set of wavelet coefficients of $u_\ell : \langle u_\ell (\varvec{x}),{\tilde{\varphi }}_{j,k_1} \otimes {\tilde{\psi }}_{j,k_2}(\varvec{x}) \rangle , \langle u_\ell (\varvec{x}),{\tilde{\psi }}_{j,k_1} \otimes {\tilde{\varphi }}_{j,k_2}(\varvec{x}) \rangle$ and $\langle u_\ell (\varvec{x}),\psi _{j,k_1} \otimes \psi _{j,k_2}(\varvec{x}) \rangle$.

Since each coeff icient is weighted by $4^{nj}$ in (38), the term $F_r(\mathbf{u})$ can be thus expressed in quadratic form:

$$\begin{aligned} F_r(\mathbf{u})\sim \mathbf{d}^T \varLambda _{j} \mathbf{d}, \end{aligned}$$

(39)

where $\varLambda _{j}$ is a diagonal matrix, whose entries are $4^{nj}$ and $\mathbf{d}$ the vector of wavelet coefficients $\{d^\ell _{j,{{{{{\varvec{k}}}}}}}\}_{\ell =1,2}$. Then, the gradient of $F_r(\mathbf{u})$ according to $\mathbf{d}$ corresponds to:

$$\begin{aligned} \nabla F_r(\mathbf{d})\sim \varLambda _{j} \mathbf{d}. \end{aligned}$$

6.2 Operator Continuous Approximation Method

The great advantage brought by the continuous optical flow representation with a finite set of coefficients of sufficiently “regular” wavelets, is that computation is done on the basis functions. More precisely, it enables the exact calculation of continuous spatial derivatives appearing in $F_r$, and the exact computation of the integrals and their gradients. This becomes possible since one knows how to compute exactly the elements of mass and stiffness matrices of compactly supported wavelet basis, see (Beylkin 1992). In practice, these terms are computed by solving an eigenvalue problem. Specifically, let $\varphi \in L^2(\mathbb{R })$ be a compactly supported scaling function and let $I_\varphi$ be its autocorrelation at a point $x$ defined by:

$$\begin{aligned} I_\varphi (x)=\int _\mathbb{R }\varphi (y)\varphi (y-x)dy. \end{aligned}$$

(40)

Since $\varphi$ satisfies a two scale relation, see Beylkin (1992), the function $I_\varphi (x)$ verifies:

$$\begin{aligned} I_\varphi (x)=\sum _{k\in \mathbb{Z }}i_kI_\varphi (2x-k), \end{aligned}$$

(41)

with the mask $i_k\in \mathbb{R }$ and compactly supported.

Similarly, the function $J_\varphi$ of the correlation of $\varphi$ and its derivative of order $n$ at a point $x$, defined by:

$$\begin{aligned} J_\varphi (x)=\int _\mathbb{R }\varphi (y)\varphi ^{(n)}(y-x)dy, \end{aligned}$$

(42)

also satisfies a two scales relation Beylkin (1992):

$$\begin{aligned} J_\varphi (x)=\sum _{k\in \mathbb{Z }}j_kJ_\varphi (2x-k),\quad \text{ with}\quad j_k=2^ni_k. \end{aligned}$$

(43)

In addition, values of $J_\varphi$ on integer points verify:

$$\begin{aligned} \sum _{\ell \in \mathbb{Z }}\ell ^nJ_\varphi (\ell )=(-1)^nn!. \end{aligned}$$

(44)

Then, the inner products of the form $\langle \varphi _{j,k},\varphi _{j,k^{\prime }}\rangle$ and $\langle \varphi ^{(n)}_{j,k},\varphi ^{(n)}_{j,k^{\prime }}\rangle$ are eigenvectors of the matrices of terms $i_k$ and $j_k$ respectively.To get the wavelet inner products $\langle \psi _{j,k},\psi _{j,k^{\prime }}\rangle$ or $\langle \psi ^{(n)}_{j,k},\psi ^{(n)}_{j,k^{\prime }}\rangle$, it suffices to use the two scales relation satisfied by the wavelet $\psi$ to return to the scaling function basis.

Once we can compute the mass matrix and stiffness matrix of a wavelet basis, the computation of the regularization term $F_r$ becomes easy. In order to clarify these points, let us explicit the computation of the term $\int _{{\mathbb{R }}^{2}}\left|\partial ^n_{x_1}u_1\right|^2 dx$ in the case of anisotropic divergence-free wavelet-based method, the other terms being treated similarly.

From the definition of the divergence-free wavelets, we obtain:

$$\begin{aligned} u_1=\sum _{\mathbf{j,k}\in \mathbb{Z }^\mathbf{2}} 2^{j_2+2}\mathbf{d}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^{div}\psi ^1_{j_1,k_1}\otimes \psi ^0_{j_2,k_2}. \end{aligned}$$

(45)

Thus:

$$\begin{aligned} \partial ^n_{x_1}u_1=\sum _{\mathbf{j,k}\in \mathbb{Z }^2}2^{j_2+2}\mathbf{d}^{div}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}\partial ^n_{x_1}\psi ^1_{j_1,k_1} \otimes \psi ^0_{j_2,k_2}, \end{aligned}$$

(46)

and

$$\begin{aligned} \int _{{\mathbb{R }}^{2}}\left|\partial ^n_{x_1}u_1\right|^2dx&= \int _{{\mathbb{R }}^{2}}\partial ^n_{x_1}u_1\cdot \partial ^n_{x_1}u_1dx\end{aligned}$$

(47)

$$\begin{aligned}&= \sum \mathbf{d}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^{div}\mathbf{d}^{div}_\mathbf{j^{\prime },k^{\prime }} \mathbf{R}^{j_1,j_1^{\prime }}_{k_1,k_1^{\prime }}\mathbf{M}^{j_2,j_2^{\prime }}_{k_2,k_2^{\prime }}, \end{aligned}$$

(48)

where $\mathbf{M}$ and $\mathbf{R}$ are respectively the one dimensional mass and stiffness matrices of the basis $\{\psi ^0_{j,k}\}$ and $\{\psi ^1_{j,k}\}$. Accordingly, their coefficients are given by:

$$\begin{aligned}&\mathbf{M}^{j_2,j_2^{\prime }}_{k_2,k_2^{\prime }}=2^{j_2+j_2^{\prime }+4} \left\langle \psi ^0_{j_2,k_2},\psi ^0_{j_2^{\prime },k_2^{\prime }}\right\rangle ,\nonumber \\&\mathbf{R}^{j_1,j_1^{\prime }}_{k_1,k_1^{\prime }}=\left\langle \frac{d^n}{dx^n}\psi ^1_{j_1,k_1},\frac{d^n}{dx^n} \psi ^1_{j_1^{\prime },k_1^{\prime }}\right\rangle . \end{aligned}$$

As (47) is a quadratic form, its gradient is simply given by:

$$\begin{aligned} \partial _ {\mathbf{d}^{div}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}} \int _{{\mathbb{R }}^{2}}\left|\partial ^n_{x_1}u_1\right|^2dx =\sum _{\mathbf{j^{\prime },k^{\prime }}\in \mathbb{Z }^\mathbf{2}}\mathbf{d}^{div}_\mathbf{j^{\prime },k^{\prime }}\mathbf{R}^{j_1,j_1^{\prime }}_{k_1,k_1^{\prime }}\mathbf{M}^{j_2,j_2^{\prime }}_{k_2,k_2^{\prime }}. \end{aligned}$$

(49)

To compute the regularization term, we use the tensor structure of the basis, unlike Wu et al. (2000) where the two-dimensional basis functions are used. This allows us avoiding the calculation and storage of a large matrix, hence reducing greatly the complexity of the algorithm:

$$\begin{aligned} \left[\partial _ {\mathbf{d}^{div}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}} \int _{{\mathbb{R }}^{2}}\left|\partial ^n_{x_1}u_1\right|^2dx\right]=\mathbf{R}\left[\mathbf{d}^{div}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}\right]\mathbf{M}. \end{aligned}$$

In addition, the computation of these matrices is done once for all on the scaling functions basis. To come back to the wavelet basis it suffices to use one-dimensional fast wavelet transform (FWT) on each row and column. Thus the theoretical complexity of this gradient computation is at most $O(N^3)$, which is much lower than the $O(N^6)$ complexity of Wu et al. (2000).

Remark 3

Since $\frac{d^n}{dx^n}\psi _{j,k}(x)=4^n2^{jn}\psi ^{(n)}_{j,k}(x)$, the entries of the matrix R defined by (49) are proportional to $16^n4^{nj}$. Thus, the parameter $\gamma >0$ which matches the effect of the regularization term $F_r$ must be small enough to attenuate this weighting.

7 Numerical Results

The main contributions highlighted in this paper is the use of wavelet bases for optical flow estimation, particularly divergence-free wavelet bases in the incompressible case. Moreover, we showed that regularizations term expressed as the norm of differentiation operator can be encoded effectively using wavelet bases properties. Then, the objective of the present section is to evaluate the performance of these methods. Firstly, in Sects. 7.1 and 7.2, we evaluate the advantage of the use of divergence-free wavelet bases combined with the different regularization techniques in the case of incompressible flow. In Sects. 7.3 and 7.4, we evaluate the use of these regularization techniques in the general case of not divergence-free flow, on standard wavelet bases.

7.1 Synthetic Images of 2D Divergence-Free Turbulence

In this section, the quality of optical flow estimation is evaluated on two different synthetic image sequences: a sequence of particle image velocimetry (PIV) (referred subsequently as “particle images”) and images of an advected and diffused passive scalar (referred subsequently as “scalar images”). Both sequences depict the same bi-dimensional incompressible turbulent flow. The dynamic of the fluid flow is given by a direct numerical simulation of 2D incompressible Navier-Stokes equations at $Re=3000$, using the vorticity conservation equation and the Lagrangian equation for non-heavy particles transported by the flow [simulation details can be found in Heitz et al. (2007)]. Since this simulated flow is divergence-free by construction, we can evaluate the efficiency of introducing this constraint in the wavelet bases. Image size is $256 \times 256$ pixels and the pixel grey levels have been normalized; examples of input images $I_0(x)$ from PIV and scalar sequences are displayed in Fig. 5, together with their associated ground truth motion vorticity. Estimated velocity and vorticity fields are evaluated based on the root mean squared end-point error (RMSE) and the Mean Barron Angular Error (MBAE):

$$\begin{aligned} \text{ RMSE}= \frac{1}{|\varOmega |}\left( \sum _{\varvec{x}\in \varOmega } \left| \mathbf{u}(\varvec{x}) - \mathbf{u}_\mathrm{ref }(\varvec{x}) \right|^2 \right)^{\frac{1}{2}} , \end{aligned}$$

and

$$\begin{aligned} \text{ MBAE} = \frac{1}{|\varOmega |} \sum _{\varvec{x}\in \varOmega } \text{ arcos}\left(\frac{\mathbf{u}(\varvec{x}) \cdot \mathbf{u}_\mathrm{ref }(\varvec{x})}{|\mathbf{u}_\mathrm{ref } (\varvec{x})|^2}\right). \end{aligned}$$

For the two image sequences, the different realized experiments correspond to:

• Case (i), estimation on a truncated standard wavelet basis Dérian et al. (2011), without any regularization.

• Case (ii), estimation on a truncated divergence-free wavelet basis, without any regularization.

• Case (iii), estimation on a divergence-free wavelet basis using discrete approximation of the regularization term.

• Case (iv), estimation on a divergence-free wavelet basis using continuous approximation of the regularization term.

In Fig.2, we show the plot of a time-sequence of the RMSE on the velocity field $\mathbf{u}$ obtained by some state-of-the-art estimators and compare it to the velocity obtained with the proposed methods. Only the method of Yuan et al. (2007) encodes the same regularizer operators (divergence-free and gradient of curl penalization), which are approached by high-order schemes using finite-difference method. The other results are used to compare the capacity and effectiveness of the proposed methods over existing state-of-the-art estimators. Let us note that state-of-the-art PIV techniques based on correlation are largely above these results in term of RMSE (mean value around $0.1$). For indication, also an advanced implementation of the Horn and Schunck (1981) techniques is of the same order accuracy as state-of-the-art PIV method. Figure 3 shows the plot of a time-sequence of RMSE on the vorticity $\omega =\mathbf{curl}(\mathbf{u})$ obtained by the proposed methods, compared to the results of Heas et al. (2012), Horn and Schunck (1981), Yuan et al. (2007).

Fig. 2

Comparison of the RMSE on $\mathbf{u}$ between the proposed methods (bold lines) and some works of the literature (Heas et al. 2012; Horn and Schunck 1981; Yuan et al. 2007). Top from particle images, using truncated basis with usual (case (i), red) or divergence-free (case (ii), orange) wavelets, divergence-free basis with discrete (case (iii), dark blue) or continuous (case (iv), greenish-blue) regularization operators. Bottom from scalar imagery, using divergence-free basis with discrete (case (iii), dark blue) or continuous (case (iv), greenish-blue) regularization operators

Fig. 3

Comparison of the RMSE on $\omega =\mathbf{curl}(\mathbf{u})$ between the proposed methods (bold lines) and some works of the literature (Heas et al. 2012; Horn and Schunck 1981; Yuan et al. 2007). The plot legend is the same as Fig. 2

The divergence-free wavelet generator $\psi ^1$ [cases (ii), (iii), (iv)] was the Coiflet Mallat (2008) with $10$ vanishing moments. This same Coiflet-10 was used for the standard estimation on truncated basis, case (i), for comparison. For the operator discrete approximation method, case (iii), we used the second order derivative penalization corresponding to:

$$\begin{aligned} F_r(\mathbf{u})=\int _{\varOmega } \sum \limits _{\mathop {1 \le i\le 2} \limits _{1 \le \ell \le 2}}\left|\partial ^2_{x_i}u_\ell (\varvec{x})\right|^2 d\varvec{x}. \end{aligned}$$

(50)

The regularization parameters are $\gamma =2.3\times 10^{-8}$ for the particle images and $\gamma =2.1\times 10^{-10}$ for the scalar images. For the operator continuous approximation method, case (iv), we used Laplacian regularization (31), approximated as in Sect. 6.2. The regularization parameters are $\gamma =2\times 10^{-7}$ for the particle images and $\gamma =10^{-6}$ for the scalar images.

Figures 2, 3 and 4 show that the use of a divergence-free wavelet basis yields a significant improvement, compared to standard wavelet basis or other state-of-the-art estimators. The addition of, either the discrete or the continuous proposed regularization, enables to further outperform state-of-the-art results. Results on scalar imagery (Fig. 2b) show that the combination of a divergence-free wavelet basis and continuous operator regularization is necessary, in order to obtain results comparable to those of the state-of-the-art. Let us note that the regularization approach proposed in Heas et al. (2012) is accurate here since it takes advantage of an additional physical constraint (turbulence power laws parameters, whose estimation increases significantly the computational cost of the method). This type of regularization is perfectly suited to homogeneous isotropic turbulent flows as the one of this test sequence. It is however not adapted to flow showing different regimes in the same domain (laminar, transition toward turbulence, turbulent). The other estimators are from that point of view more general (Fig. 5).

Fig. 4

Comparison of the MBE on $\mathbf{u}$ between the proposed methods (bold lines) and some works of the literature (Heas et al. 2012; Horn and Schunck 1981; Yuan et al. 2007). The plot legend is the same as Fig. 2

Fig. 5

Top first particle image used (a) (corresponding to instant $t=0$ in sequence of Fig. 2a) and first scalar image used (b) (corresponding to instant $t=20$ in sequence of Fig. 2b). Bottom first reference vorticity (c) (associated to particle images) and first reference vorticity (d) (associated to scalar images)

Figures 6 and 7 present vorticity fields computed from estimated motion fields, as well as vorticity end-point error maps. On particle imagery, improvements brought by divergence-free bases [cases (i), (ii)] are visible on error maps (Fig. 6b, d), only smallest structures remain unestimated. The benefit of a continuous implementation of the Laplacian regularization instead of discrete derivative penalization [cases (iii), (iv)] can be clearly noted looking a vorticity maps (Fig. 6e, g). This is at the more true in the scalar case where the discrete approximation yields clearly some block artifacts. This is confirmed by results on scalar imagery Fig. 7.

Fig. 6

Left column vorticity computed from velocity fields estimated from particle imagery (Fig. 5a) with the 4 presented cases, to be compared with the reference Fig. 5c. Right column corresponding vorticity RMSE

Fig. 7

Left vorticity computed from velocity fields estimated from scalar imagery (Fig. 5b), using Div-free wavelets method and discrete (top) or continuous (bottom) regularization. Right corresponding vorticity RMSE

Figure 8 shows the evolution of the RMS error as the estimation moves forward, representing the motion within finer and finer approximation spaces $V_j$. The corresponding ratio of activated coefficients w.r.t. to the total is displayed as well. This experiment was conducted from particle images, using either usual or divergence-free bases, and the continuous approximation of Laplacian regularization in both cases. The error reduction nearly saturates after level 6, which indicates that very few details remain estimable, at these very small scales, from given images. It also illustrate the well-known ability of wavelet bases to provide sparse representations of signals, should the chosen wavelet be sufficiently regular for the analyzed signal. Judging from the saturation of the error at finer spaces $V_7$ and $V_8$, it is possible to stop the estimation process in $V_6$. The solution is then represented by only 6.25 % atoms of the full wavelet basis, which reduces significantly the numerical complexity and actual computation time of the method. With this particular example, the estimation time drops down from 60s (in $V_8$) to 40s (in $V_6$). It must be kept in mind, however, that this behavior highly depends on the nature on input images, on the underlying motion as well as on the regularity of the chosen basis.

Fig. 8

RMSE on $\mathbf{u}$ according to the multi-resolution approximation space $V_j$ and the ratio of its activated wavelet coefficients. Particle images: divergence-free wavelet basis ($-*-$) and standard wavelet basis ($-\tiny {\nabla }-$), both with continuous approximation of Laplacian regularization

7.2 Real Images of 2D Divergence-Free Turbulence

This section presents results obtained with real images of experimental 2D incompressible turbulent flows. The data set consists in images of dispersion of passive tracers in a forced 2D incompressible turbulence experiment, of size $512\times 512$ pixels (Jullien et al. 2000). The experiments were performed with electromagnetically-forced incompressible flows in stable thin stratified layers of fluid. Figure 9 depicts an image of the sequence. For the divergence-free wavelet based-method, the employed regularizer is the same as in the case of synthetic images: continuous gradient of curl regularizer (34) (or equivalently, in this incompressible case, the Laplacian penalization) with a factor $\gamma =2.5\times 10^{-8}$. In order to make results comparable, we used the same regularizer model and factor for the standard wavelet-based method, followed by a projection onto the divergence-free function space using a spectral method. Inspection of estimates shows that the divergence-free wavelet-based method enables to extract more accurately vortex structures and shear layers with better temporal continuity. This is illustrated by the plot of two consecutive vorticity maps in Fig. 10.

Fig. 9

Experimental image of passive scalar dispersion in a 2D turbulent motion, corresponding to time $t=89$. This image has been normalized so as to enhance visualization

Fig. 10

Details of two successive vorticity fields computed from estimated velocity fields, using experimental 2D scalar image dataset at $t=88$ and $t=89$ (input image Fig. 9). Both cases use continuous Laplacian regularization with $\gamma =2.5\times 10^{-8}$, associated to usual Coiflet-10 wavelet basis (top) and divergence-free basis generated from same Coiflet-10 (bottom). Enhancement brought by the divergence-free basis is clearly visible, with much better-defined structures as well as a better temporal coherence on bottom row vorticity fields

7.3 Experimental Images: Concomitant Jet

In this section we evaluate the introduced regularization methods in the context of quasi-2D compressible turbulence. In order to study quasi-2D or 3D turbulent flows, the use of 2D experimental images is very common in fluid mechanics laboratories. However, traditional motion estimators usually fail or exhibit strong inaccuracy at some places.

The data set consists in a sequence of 128 images of particle transported by a planar concomitant jet flow, of size $1,024\times 1,024$ pixels. The flow is 3D and shows two high-shear regions featuring development of Kelvin-Helmholtz instabilities. Since the flow is not divergent-free, motion components are estimated on a standard scalar wavelet basis with the proposed continuous implementation of wavelet-based gradient of curl regularizer (30), using factor $\gamma =10^{-7}$. Results are shown in Fig. 11. Estimates obtained with discrete second order regularization (50), with parameter $\gamma =10^{-7}$, are given for comparison. Figure 11 also presents image of the sequence and streamlines of the estimated velocity field using either discrete or continuous regularization, along with two consecutive vorticity maps computed from estimated motions. A qualitative evaluation of the results shows a remarkably good agreement with the physics of concomitant jets. A very good temporal coherence is also observed, although no prior dynamic model is considered (i.e successive pairs of images are processed independently). Results obtained using operator continuous approximation regularization however enables visualizing the evolution of finer structures living at much finer scales.

Fig. 11

Results from 2D planar jet PIV dataset. Top detail of input PIV image (a), streamlines (b). Middle vorticity computed from two consecutive estimated motions, using discrete regularization. Bottom vorticity computed from estimations using continuous regularization

7.4 Meteorological Images: Davina Cyclone

These results are obtained from meteorological images that were taken in the infrared channel by Meteosat-5 satellite, of size $400\times 400$ pixels. The sequence depicts Davina cyclone crossing the Indian Ocean on March 6, 1999; it was kindly provided by the Laboratoire de Métérologie Dynamique (LMD). Such flows are not necessarily divergence-free, as it was already the case in Sect. 7.3. The apparent motion is very complex, due to the presence around the cyclone of several cloud layers at different altitudes, having completely independent motions and eventually occulting each other. The motion of the cyclone only is however simpler and quasi-2D. Looking for a solution that would focus on reflecting the cyclone motion, without being altered either by the global transport to which the cyclone is not subjected, or by divergence-alike events caused by the other cloud layers, then the divergence-free estimator is particularly appropriate. Figure 12 shows a motion estimate $\mathbf{u}^\mathrm{div }$ at sample time $t=24$, obtained using a divergence-free basis generated from Coiflet-10 wavelets. The laplacian regularizer (31) was employed (equivalent to curl-gradient penalization) with balance parameter $\gamma =5\times 10^{-2}$. Estimation on a regular Coiflet-10 basis leads to a completely different motion $\mathbf{u}$, shown in Fig. 13. A more complex curl- and divergence-gradient regularizer with parameter $\gamma =2\times 10^{-2}$ was used to deal with divergence-alike motions caused by surrounding clouds. The divergence-free projection of $\mathbf{u}$ (Fig. 13b) however reveals the large vortical structure corresponding to the cyclone.

Fig. 12

Motions estimated from Meteosat-5 infrared channel images of Davina cyclone over the Indian Ocean, in March 1999. (a) superimposes estimated divergence-free motion $\mathbf{u}^\mathrm{div }$ on the first input image $I_0$ at time $t=24$. Its corresponding vorticity map is shown in (b)

Fig. 13

Motions estimated at instant $t=24$ of Davina cyclone image sequence. (a) Superimposes estimated motion $\mathbf{u}$ (using regular basis) on the first input image $I_0$. (b) Displays its divergence-free component $\mathbf{u}^\mathrm{div }$ only, exhibiting the huge vortex corresponding to the cyclone. The associated vorticity map is shown in (c)

7.5 Experimental Images: Wingtip Vortex

This last dataset depicts the time-evolution of a wingtip vortex visualized by smoke. The sequence of $256\times 256$ pixels images was provided by the Onera. In that case, the vortex is highly 3D and affected by gravity, therefore subject to a global transport; hence the divergence-free estimator is not appropriate. Figure 14 presents an input image at sample time $t=44$ and the corresponding estimate. A regular Coiflet-10 basis was used, with the same curl- and divergence-gradient regularizer as in the previous cyclone example, and parameter $\gamma =2\times 10^{-3}$. The structure of the estimated motion matches very well with the smoke pattern.

Fig. 14

Motion estimated from wingtip vortex image sequence at time $t=44$. (a) Superimposes estimated motion $\mathbf{u}$ on the first input image $I_0$ (in false colors). Its corresponding vorticity map is shown in (b)

8 Conclusion

Based on a biorthogonal wavelet expansion of optical flow and particularly divergence-free wavelet in the incompressible case, we have proposed an algorithm dedicated to the estimation of fluid motion. The wavelet-based algorithm is of low-complexity and offers an intrinsic and efficient multiresolution estimation framework. Taking advantage of the continuous representation of optical flow by a finite set of wavelet coefficients, we have proposed a family of high-order regularizers designed for fluid flows. They rely on the approximation or the exact computation (without any discretization approximations in both cases) of differential operators of arbitrary order. The regularizers are approached in the first case by simply constraining wavelet coefficients, while in the second case it is calculated exactly by the simple calculation of one-dimensional wavelet basis mass and stiffness matrices. Numerical results obtained with challenging particle and scalar image sequences of 2D and 3D turbulence show a significant performance enhancement compared to state of the art methods.

Appendices

Appendix

Fast Divergence-Free Wavelet Transform

To implement numerically the divergence-free wavelet based method of Sect. 5.2, it is necessary to have at hand the fast divergence-free wavelet transform algorithm. For this practical reasons, the divergence-free wavelet bases have to be compactly supported. Such wavelet bases exist and can be fortunately easily constructed. They have been introduced first by Lemarié-Rieusset (1992). The objective here is to detail the anisotropic construction of divergence-free wavelet basis introduce in Sect. 5.1 in order to construct the associated fast wavelet transform algorithm.

Before further detailing this construction, we first give some technical precisions. Since the curl operator introduces derivation operators, it is important to answer to the following questions: what is the derivative of a scaling function? What is the derivative of a wavelet? Does differentiation preserve the $L^2(\mathbb{R })$ orthogonality property of a wavelet basis?

Using integration by part, to answer the last question we have:

$$\begin{aligned} \int _{\mathbb{R }}\varphi _k^{\prime }(x)\varphi _{\ell }^{\prime }(x)dx =-\int _{\mathbb{R }}\varphi _k(x)\varphi _{\ell }^{\prime \prime }(x)dx. \end{aligned}$$

Thus, if $\{\varphi _{j,k}:\,k\in \mathbb{Z }\}$ is an orthogonal basis, this property is preserved by differentiation if and only if $\varphi =-\varphi ^{\prime \prime }$: which is for instance true for sinus or cosinus basis.

The answers to the first two questions are supplied by Kahane and Lemarié-Rieusset (1995). Precisely, let $(\varphi ^1,\tilde{\varphi }^1)$ be a pair of biorthogonal scaling functions associated to biorthogonal wavelets $(\psi ^1,\tilde{\psi }^1)$, with $\varphi ^1\in \mathcal{C }^{1+\epsilon }(\mathbb{R })$, $\epsilon >0$. Then there exists another biorthogonal scaling functions $(\varphi ^0, \tilde{\varphi }^0)$ and biorthogonal wavelets $(\psi ^0,\tilde{\psi }^0)$, satisfying Kahane and Lemarié-Rieusset (1995):

$$\begin{aligned} \frac{d}{dx}\varphi ^1(x)=\varphi ^0(x)\,-\,\varphi ^0(x-1), \end{aligned}$$

(51)

and

$$\begin{aligned} \frac{d}{dx}\tilde{\varphi }^0(x)=\tilde{\varphi }^1(x+1) \,-\,\tilde{\varphi }^1(x). \end{aligned}$$

(52)

The associated wavelets verify ( Kahane and Lemarié-Rieusset 1995 ):

$$\begin{aligned} \psi ^1(x)=4\int \limits _{-\infty }^x\psi ^0\quad \text{ and}\quad \tilde{\psi }^0(x)=-4\int \limits _{-\infty }^x\tilde{\psi }^1. \end{aligned}$$

(53)

Hence, according to (51), (52) and (53), the derivative of a scaling function is expressed as a finite difference on neighborhoods of another scaling function and the derivative of a wavelet is another wavelet. Figure 15 shows the plot of an example of these scaling functions and wavelets linked by differentiation and integration.

Fig. 15

Example of biorthogonal generators and primal derivatives: case of B-Spline generators $(\varphi ^1,\tilde{\varphi }^1)$ with 3 vanishing moments

Let $(V^1_j)_{j\in \mathbb{Z }}$ and $(V^0_j)_{j\in \mathbb{Z }}$ be one-dimensional multiresolution analyses of $L^2(\mathbb{R })$ provided by $\varphi ^1$ and $\varphi ^0$ respectively, with $\varphi ^1$ and $\varphi ^0$ defined by (51). Since we use tensor product construction in higher dimension, each sequence of space, namely:

$$\begin{aligned} V^1_j\otimes V^0_j=\text{ span}\left\{ \varphi ^1_{j,k_1}(x)\varphi ^0_{j,k_2} (y),\,k_1,k_2\in \mathbb{Z }\right\} ,\quad j\in \mathbb{Z }, \end{aligned}$$

or

$$\begin{aligned} V^0_j\otimes V^1_j=\text{ span}\left\{ \varphi ^0_{j,k_1}(x) \varphi ^1_{j,k_2}(y),\,k_1,k_2\in \mathbb{Z }\right\} ,\quad j\in \mathbb{Z }, \end{aligned}$$

form a multiresolution analysis of $L^2(\mathbb{R }^2)$. Moreover, to compute the fast wavelet decomposition, in the multiresolution generated by $V^1_j\otimes V^0_j$, it suffices to use the filters of $(\tilde{\varphi }^1,\tilde{\psi }^1)$ in the $x$ direction and those of $(\tilde{\varphi }^0,\tilde{\psi }^0)$ in the $y$ direction. The reconstruction is done with the filters of $(\varphi ^1,\psi ^1)$ and $(\varphi ^0,\psi ^0)$ respectively.

From relations (51) and (52), one can derive two interesting properties of biorthogonal multiresolution analyses $(V^1_j,\tilde{V}^1_j)$ and $( V^0_j,\tilde{V}^0_j)$ (Kahane and Lemarié-Rieusset 1995):

$$\begin{aligned} \frac{d}{dx}V^1_j=V^0_j, \quad \quad \quad \quad \tilde{V}^0_j=\int \limits _{-\infty }^x\tilde{V}^1_j. \end{aligned}$$

(54)

The interest of relations (54) appears in the numerical implementation of fast divergence-free wavelet transform. This relation allows to build a multiresolution analysis of $(L^2(\mathbb{R }^2))^2$ that preserves the divergence-free property (Lemarié-Rieusset 1992).

As stated in (19), the space $\mathcal{H }_{div}(\mathbb{R }^2)$ corresponds to the curl of $H^1(\mathbb{R }^2)$ scalar potential. Then, taking the curl of any multiresolution analysis of $H^1(\mathbb{R }^2)$ will provide a multiresolution analysis of $\mathcal{H }_{div}(\mathbb{R }^2)$. However, let us consider a “regular” scalar multiresolution analysis of $H^1(\mathbb{R }^2)$ generated by spaces $V^a_j\otimes V^b_j$, with $V^a_j\ne V^b_j$. Taking the curl of a such multiresolution analysis, we get:

$$\begin{aligned} \mathbf{curl}[V^a_j\otimes V^b_j]=\left( \begin{array}{ll} V^a_{j}\otimes {(V^b_{j})}^{\prime }\\ \, \\ - {(V^a_{j})}^{\prime }\otimes V^b_{j} \end{array} \right). \end{aligned}$$

(55)

Then, to deal with the divergence-free wavelets contained in the spaces $\mathbf{curl}[V^a_j\otimes V^b_j]$, we have to manipulate four different types of biorthogonal wavelet filter banks associated respectively to the one-dimensional BMRAs that appear in (55): $V^a_j, (V^a_j)^{\prime }, V^b_j$ and $(V^b_j)^{\prime }$. To overcome this problem, the two-dimensional scalar multiresolution analysis that we will consider is generated by spaces $V^1_j\otimes V^1_j$ and using Lemarié-Rieusset’s results (54), one can easily prove that:

$$\begin{aligned} \mathbf{curl}\left(V^1_j\otimes V^1_j\right)\subset \left(V^1_j\otimes V^0_j\right)\times \left(V^0_j\otimes V^1_j\right)={\mathbf{V}}_j. \end{aligned}$$

(56)

Accordingly, the divergence-free scaling functions and wavelets of Sect. 5.1 verify:

$$\begin{aligned} {\varvec{\Phi }}^{div}_{j,{{{{{\varvec{k}}}}}}}=\mathbf{curl} [\varphi ^1_{j,k_1}\otimes \varphi ^1_{j,k_2}] =\left( \begin{array}{ll} \varphi ^1_{j,k_1}\otimes {(\varphi ^1_{j,k_2})}^{\prime }\\ \, \\ - {(\varphi ^1_{j,k_1})}^{\prime }\otimes \varphi ^1_{j,k_2} \end{array} \right) \in {\mathbf{V}}_j, \end{aligned}$$

and

$$\begin{aligned} {\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}} \!=\!\left( \begin{array}{ll} 2^{j_2\!+\!2}\psi ^1_{j_1,k_1}\otimes \psi ^0_{j_2,k_2}\\ \, \\ \!-\! 2^{j_1\!+\!2}\psi ^0_{j_1,k_1}\otimes \psi ^1_{j_2,k_2} \end{array} \right) \in \left(W^1_{j_1}\!\otimes \! W^0_{j_2}\right)\\ \times \left(W^0_{j_1}\otimes W^1_{j_2}\right). \end{aligned}$$

1.1 Fast Divergence-Free Wavelet Transform

By construction, we have seen that the vector spaces $\mathbf{V}_j=\left(V^1_j\otimes V^0_j\right)\times \left(V^0_j\otimes V^1_j\right)$ constitute a multiresolution analysis of $(L^2(\mathbb{R }^2))^2$ and this multiresolution analysis preserves the divergence-free constraint (Lemarié-Rieusset 1992). From a standard anisotropic vector wavelet decomposition associated to $\mathbf{V}_j$, the objective of this section is to describe how to compute in practice the anisotropic divergence-free wavelet decomposition of any $\mathbf{u}\in \mathcal{H }_{div}(\mathbb{R }^2)$.

The standard anisotropic vector wavelet associated to $\mathbf{V}_j$ are:

$$\begin{aligned} {\varvec{\Psi }}^{1}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}} =\left( \begin{array}{ll} \psi ^1_{j_1,k_1}\otimes \psi ^0_{j_2,k_2}\\ 0 \end{array} \right), \end{aligned}$$

and

$$\begin{aligned} {\varvec{\Psi }}^{2}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}} =\left( \begin{array}{ll} 0\\ \psi ^0_{j_1,k_1}\otimes \psi ^1_{j_2,k_2} \end{array} \right). \end{aligned}$$

Since $\mathbf{u}\!=\!(u_1,u_2)$ belongs to $(L^2(\mathbb{R }^2))^2$ and $({\varvec{\Psi }}^{1}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}, {\varvec{\Psi }}^{2}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}})_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}\in \mathbb{Z }^2}$ is a wavelet basis of $(L^2(\mathbb{R }^2))^2$, we get:

$$\begin{aligned} \mathbf{u}=\sum _{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}\in \mathbb{Z }^2}\mathbf{d}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^1 {\varvec{\Psi }}^{1}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}} +\sum _{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}\in \mathbb{Z }^2}\mathbf{d}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^2 {\varvec{\Psi }}^{2}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}. \end{aligned}$$

(57)

Through an easy calculation, by identification one can show that:

$$\begin{aligned} u_1=\sum _{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}\in \mathbb{Z }^2}\mathbf{d}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^1\,\psi ^1_{j_1,k_1}\otimes \psi ^0_{j_2,k_2}, \end{aligned}$$

and

$$\begin{aligned} u_2=\sum _{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}\in \mathbb{Z }^2}\mathbf{d}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^2\,\psi ^0_{j_1,k_1}\otimes \psi ^1_{j_2,k_2}. \end{aligned}$$

Following Deriaz and Perrier (2006) and using the relation:

$$\begin{aligned} {\varvec{\Psi }}^{div}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}} =2^{j_2+2}{\varvec{\Psi }}^{1}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}-2^{j_1+2} {\varvec{\Psi }}^{2}_{{{{{{\varvec{j}}}}}},{{{{{\varvec{k}}}}}}}, \end{aligned}$$

(58)

we find:

$$\begin{aligned} \mathbf{d}^{div}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}=\frac{2^{j_2+2}}{4^{j_1+2}+4^{j_2+2}} \mathbf{d}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^1-\frac{2^{j_1+2}}{4^{j_1+2}+4^{j_2+2}} \mathbf{d}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^2, \end{aligned}$$

(59)

and

$$\begin{aligned} \mathbf{d}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^1=2^{j_2+2}\mathbf{d}^{div}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}, \quad \quad \quad \quad \mathbf{d}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}^2=-2^{j_1+2}\mathbf{d}^{div}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}. \end{aligned}$$

(60)

Therefore, decomposition and reconstruction associated to divergence-free wavelets is simply performed using scalar wavelet filter banks. Finally, the algorithm is of low complexity and its structure remains identical to the scalar case.

The algorithm is summarized then as follows. Starting with $\mathbf{u}=(u_1,u_2)$, to get the divergence-free wavelet coefficients $\mathbf{d}^{div}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$:

• 1a. Compute $\mathbf{d}^{1}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$  associated to $u_1$ in $V^1_j\otimes V^0_j$.

• 2a. Compute $\mathbf{d}^{2}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$  associated to $u_2$ in $V^0_j\otimes V^1_j$.

• 3a. Compute $\mathbf{d}^{div}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$  from $\mathbf{d}^{1}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$  and $\mathbf{d}^{2}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$ using (59).

For the reconstruction:

• 1b. Compute $\mathbf{d}^{1}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$ and $\mathbf{d}^{2}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$ from $\mathbf{d}^{div}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$ using (60).

• 2b. Compute $u_1$ from $\mathbf{d}^{1}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$ in $V^1_j\otimes V^0_j$.

• 3b. Compute $u_2$ from $\mathbf{d}^{2}_{{{{{\varvec{j}}}}},{{{{\varvec{k}}}}}}$ in $V^0_j\otimes V^1_j$.

Steps 1a and Step 2a correspond to a two dimensional fast wavelet transform. Step 3a is a change of basis which theoretical complexity is linear, thus the theoretical complexity of the decomposition phase is about $O(N)$. As the same, Step 3b is a change of basis, Steps 2b and Step 3b correspond to an inverse two dimensional fast wavelet transform, the theoretical complexity of recomposition phase is also about $O(N)$.