A new class of fractional-order variational optical flow models, which generalizes the differential of optical flow from integer order to fractional order, is proposed for motion estimation in this paper. The corresponding Euler–Lagrange equations are derived by solving a typical fractional variational problem, and the numerical implementation based on the Grünwald–Letnikov fractional derivative definition is proposed to solve these complicated fractional partial differential equations. Theoretical analysis reveals that the proposed fractional-order variational optical flow model is the generalization of the typical Horn and Schunck (first-order) variational optical flow model and the second-order variational optical flow model, which provides a new idea for us to study the optical flow model and has an important theoretical implication in optical flow model research. The experiments demonstrate the validity of the generalization of differential order.
Optical flow is a two-dimensional velocity field generated by the moving objects in the scene or the observer motion. By the analysis of optical flow, one can get much useful motion information, such as speed, direction and number of objects. There is no doubt that optical flow estimation is one of the key problems in computer vision, which has been widely applied in many fields, such as automatic driving, medical diagnosis and intelligent monitoring. Ever since the original approaches of Horn & Schunck  and Lucas & Kanade  were proposed, many improved optical flow models have been developed and achieved an impressive level of reliability and accuracy [3–6]. In these studies, some technologies, for example coarse-to-fine and warping technology, have very important roles. The coarse-to-fine technology was proposed to find the global minimum in optical flow estimation [7,8]. The main idea of this technology is that, first, we estimate the optical flow in coarse layers and then make the coarse solution the initial value for solving a refined version until optical flow is calculated. So, it increases the estimation accuracy of the optical flow algorithm. The warping technology is very helpful for dealing with larger displacement problems .
Recently, the variational optical flow models, which compute the optical flow field via variational methods, have obtained much success in the estimation of the optical flow field owing to their advantages in modelling, computation and quality . A modification of these models, which generalizes their differential order, has attracted increasing attention from some scholars. There are two types of generalization of the differentiations in the variational optical flow models. One generalization deals with higher-order differentiations [11,12], and the other deals with fractional-order differentiations [13,14]. In this paper, we focus on the second type of generalization, because the fractional-order differentiations can be seen as the generalized form of the integer-order differentiations.
Fractional differentiation, a mathematical discipline dealing with the differentiation of arbitrary order, was proposed in the seventeenth century and developed mainly in the nineteenth [15–17]. Many definitions of fractional differentiation have been proposed and the most popular definitions among them involve: the Riemann–Liouville definition , the Grünwald–Letnikow definition  and the Caputo definition . The long-term memory is an important characteristic of fractional differentiation and also is a prominent difference between fractional differentiation and integer-order differentiation. Because of the long-term memory, fractional differentiation became an important tool for modelling characteristic phenomena in various application fields [21–24]. Recently, more and more fractional differentiation-based methods were applied in the fields of image processing [25,26]. In this paper, we aim our interests at the optical flow estimation and propose a novel fractional-order variational optical flow (FOVOF) model. Some numerical experiments are presented to analyse the improvement owing to using fractional order instead of the integer order in the variational optical flow model.
This paper is organized as follows: §1 introduces prior work, and we give a simple introduction of the fractional-order derivative and describe the proposed fractional-order variational optical flow model in §2. A numerical implementation of the proposed FOVOF model is introduced in §3. Experimental evaluation is presented in §4, and §5 concludes the paper.
(a) Riemann–Liouville definition
Let and α∈(n−1,n). The left Riemann–Liouville fractional integral of order α, , is defined as 2.1 where the gamma function Γ(z) is defined by the integral 2.2 The right Riemann–Liouville fractional integral of order α, , is defined as 2.3 Suppose f(t) is a continuous function in [a,b], the left Riemann–Liouville fractional derivative of order α, , is given by 2.4 and the right Riemann–Liouville fractional derivative, , is given by 2.5 We have that , where I is the identity map. The main properties are shown as follows:
— when α is an integer, the operation gives the same result as integer-order differentiation;
— when α=0, the operation is the identity operator;
— the fractional differentiation operator and fractional integral operator are linear, 2.6
— the fractional differentiation operator and fractional integral operator satisfy the additive index law (semigroup property), 2.7
(b) Fractional-order variational optical flow model
Let I0(x,y,t) be the given image sequence, where (x,y)T denotes the location with a rectangular image domain and t>0 denotes time. In order to reduce the influence of noise and outliers, I0(x,y,t) is convolved with a Gaussian filter Gσ with mean μ=0 and standard deviation σ, and I(x,y,t)=Gσ*I0(x,y,t). The typical Horn and Schunck (H–S) optical flow problem is defined as 2.8 where w(x,y):=(u(x,y),v(x,y),1)T is the optic flow field which describes the displacement vector field between two frames at time t and t+1, and ∇2:=(∂x,∂y)T denotes the spatial gradient operator. Ix, Iy and It are the gradients of image sequence I(x,y,t) in the direction of the axis x, y and t. The first term (data term) is also known as the optical flow constraint. It assumes that the intensity values do not change during its motion. The second term (regularization term) penalizes high variations in w to obtain smooth optical fields. The weight λ serves as the regularization parameter, which weighs between the data fidelity term and the regularization term.
In this paper, we consider a fractional-order variational optical flow problem defined as 2.9 where denotes the left Riemann–Liouville fractional derivative operator and . When α=1, the fractional-order variational optical flow model can be seen as the H–S (first-order) variational optical flow model proposed by Horn & Schunck . When α=2, the fractional-order variational optical flow model can be seen as the second-order variational optical flow model described by Yuan et al. . When α∈(0,1) or (1,2), the fractional-order variational optical flow model can be seen as the generalization of the integer-order variational optical flow model.
From (2.9), it can be seen that the proposed fractional-order variational optical flow model is a fractional variational problem and we formally compute the Euler–Lagrange equation for this fractional variational problem as follows. Consider an energy function J(u,v) defined by 2.10 Assume that u*(x,y) and v*(x,y) are the desired functions. Take any test functions and and . Define 2.11 and 2.12 Since the Riemann–Liouville fractional derivative operator is a linear operator, it follows that 2.13 2.14 2.15 2.16 Substituting (2.11)–(2.16) into (2.10), we find that for each η(x,y) and ζ(x,y) 2.17 is a function of ϵ only. Note that J(ϵ) is extremum at ϵ=0. Differentiating (2.17) with respect to ϵ, we obtain 2.18 where Dα* is the right Riemann–Liouville fractional derivative, and M=Ixu*+Iyv*+It. Since η(x,y) and ζ(x,y) are arbitrary, we can obtain 2.19 and 2.20 In §3, an effective numerical method will be proposed to solve these equations.
3. Numerical algorithm
(a) Discrete fractional-order differential operator
In practical applications, assume that the estimated optical flow fields u and v are of m×n pixels, and they are sampled from its continuous version at a uniformly spaced grid size of Δh. Thereby, the estimated optical flow fields u(i,j)=u(iΔh,jΔh) and v(i,j)=v(iΔh,jΔh) for i=0,1,…,m−1 and j=0,1,…,n−1. In image-processing applications, the grid size △h is chosen as △h=1. Based on the Grünwald–Letnikov fractional derivative definition, the discrete formula of the left fractional-order derivative of the estimated optical flow field u(i,j) can be defined by the following formula: 3.1 where represent the coefficients of the polynomial (1−z)α. The coefficients can also be obtained recursively from 3.2 From (2.5) and (3.1), we can obtain 3.3 Since , equation (3.3) can be rewritten by a concise formula, 3.4 where ∇u(i−k,j)=u(i−k,j)−u(i,j). For application, we approximate (3.4) using the following formula: 3.5 where L is the mask window’s size. Provided L tends to infinite, the error is near to zero in theoretic analysis. Similarly, we can obtain 3.6
From (3.5) and (3.7), the concise discrete formula of the fractional-order differential operator can be described by the following formula: 3.7 here, χ(i,j) denotes the set of neighbours of pixel (i,j) in the direction of axes x and y, and can be obtained by .
Similarly, the discrete formula of the fractional-order derivative of the estimated optical flow field v(i,j) can be defined by the formula 3.8
Assume that the digital image I is of m×n pixels, and that it is sampled from its continuous version at a uniformly spaced grid size of Δh. Thereby, the digital image I(i,j)=I(iΔh,jΔh) for i=0,1,…,m−1 and j=0,1,…,n−1. The discrete forms of Ix, Iy and It are defined by Ix(i,j)=Ix(iΔh,jΔh), Iy(i,j)=Iy(iΔh,jΔh) and It(i,j)=It(iΔh,jΔh). For easy description, we define the following formulae: 3.9 3.10 3.11 3.12 3.13 Based on (3.7)–(3.13), the discrete formulae for the proposed fractional-order variational optical flow model can finally be written as 3.14 and 3.15 And these equations constitute a linear system of equations with respect to the 2×n×m unknowns u(i,j) and v(i,j), which can be solved by many typical methods such as the Jacobi method, the Gauß–Seidel method, the successive overrelaxation method and the preconditioned conjugate gradient (PCG) method. In addition, from (3.14) and (3.15), it is easy to see that the proposed FOVOF model is equivalent to the typical H–S variational model when α=1. So the typical H–S variational model can be seen as the first-order variational optical flow model and our proposed FOVOF model is its generalization.
In §4, we will show the improvement owing to using the fractional order instead of the integer order in the variational optical flow model by the numerical experiments.
4. Numerical experiments
(a) Evaluation database
The evaluation database has an important role in assessing the performance of the optical flow model. So far, more and more evaluation databases have been proposed. Recently, one of the most popular evaluation databases has been that designed by Simon et al. . In this paper, we use this database to demonstrate the validity of our proposed FOVOF model, which includes six typical grey image sequences, shown in figure 1, including ‘Venus’, ‘Dimetrodon’, ‘Hydrangea’, ‘RubberWhale’, ‘Grove’ and ‘Urban’.
Venus is a 420×380 grey image sequence that is obtained by cropping the stereo datasets Venus . It is good at assessing the state-of-the-art stereo algorithms. Dimetrodon and Hydrangea are the 584×388 grey image sequences that contain non-rigid motion and large areas with little texture. RubberWhale is a 584×388 grey image sequence that contains several objects undergoing independent motion. Grove is a 480×640 grey image sequence that contains substantial motion discontinuities, motion blur and larger motions. Urban is a 480×640 grey image sequence that contains buildings generated with a random shape grammar and cast shadows as well as a few independently moving cars.
(b) Evaluation method
Many methods have been proposed for assessing the performance of the optical flow algorithm, and one of the most popular methods is the angular error (AE), which is the angle between the estimated flow vector (u,v,1) and the ground-truth flow vector (uGT,vGT,1). The AE can be calculated by the following formula: 4.1 where denotes the inverse cosine operator. The AE contains an arbitrary scaling constant 1 to convert the units from pixels to degrees, and its purpose is to avoid the ‘divide by zero’ problem for zero flows. However, it brings the problem that the errors in large flows are penalized less than those in small flows. For this problem, the error in flow endpoint (EE) is proposed, which is defined as 4.2 In addition, statistics is a very effective analysis tool. Combining AE and EE with the statistics, we can obtain the average of AE (AVAE), standard deviations of AE (SDAE) and average of EE (AVEE), all of which can be used to evaluate the optical flow estimation intuitively . In the following numerical experiments, AVAE, SDAE and AVEE are all used to evaluate the proposed FOVOF model for the purpose of obtaining convincing results.
The purpose of these experiments is to analyse the contribution, caused by using the fractional-order derivative instead of the first-order derivative, to improving the accuracy of optical flow estimation algorithms. For this purpose, the typical H–S variational optical flow estimation algorithm is used as a reference. In addition, the coarse-to-fine technology is used to find the global minimum of the original problem, the warping method is used to deal with larger displacement problems and the PCG method is used to solve the system of linear equations. In the experiments, coarse-to-fine technology includes four pyramid levels and the maximum number of warping per pyramid level is three. The regularization coefficient λ is 200. In order to ensure the fairness of the estimation, all the parameters in our proposed FOVOF model are unchanged except for the differential order.
Figure 2 shows the relation between the fractional order α and AVEE for the different image sequences. The smaller the AVEE is, the better the estimation accuracy. In order to facilitate observation, the results of both the first-order derivative and the optimal derivative are marked in the figure. From figure 2a–f, it can be seen that the results are not optimal when the fractional order α=1. The main reason for this is that the first-order derivative cannot describe the discontinuous information, for example edge and texture, in the optical flow field effectively. Recently, it has been proved that the fractional-order derivative has better capability of describing the complex fractal-like texture details than the integer-order derivative. So, the accuracy of optical flow estimation algorithms can be improved by using the fractional-order derivative instead of the first-order derivative.
Table 1 shows the comparison of AVAE, SDAE and AVEE between our proposed FOVOF model and the H–S variational optical flow model for the different image sequences. The smaller AVEE, SDAE and AVEE are, the better the estimation accuracy is. The better results in the table are in bold for easy observation and they are computed by the optimization algorithm. From the table, it can be seen that our model obtains better results than the H–S model for all the image sequences. It demonstrates the validity of the generalization of differential order.
A new class of fractional-order variational optical flow models was proposed in this paper. The models include the following advantages. First, the proposed fractional-order variational optical flow model can be seen as the generalization of the typical H–S optical flow model, which provides a new line for us to study the optical flow model and has an important theoretical implication in optical flow model research. Second, an effective numerical algorithm is proposed to solve the complicated fractional partial differential equations. Third, the proposed FOVOF model can be combined with the coarse-to-fine technology and the warping method, which is helpful for improving the accuracy of the optical flow model. Finally, the experiments demonstrate that the accuracy of the optical flow estimation algorithms can be improved by using the fractional-order derivative instead of the first-order derivative. Future studies involve extending the proposed FOVOF model to other variational models and applying it to the automatic navigation system of an unmanned aerial vehicle.
The work of D.C. was supported by the National Natural Science Foundation of China (nos. 61201378 and 61174145) and the Fundamental Research Funds for the Central Universities (N110304001).
One contribution of 14 to a Theme Issue ‘Fractional calculus and its applications’.
- © 2013 The Author(s) Published by the Royal Society. All rights reserved.