A Quantitative Analysis of Current Practices in Optical Flow Estimation and the Principles Behind Them

The global formulation of optical flow introduced by Horn and Schunck (1981) relies on both brightness constancy and spatial smoothness assumptions, but suffers from the fact that their quadratic formulation is not robust to outliers. Shulman and Herve (1989) use an L1 penalty instead to preserve flow discontinuities. Black and Anandan (1996) introduce a robust framework to deal with outliers in both the data and the spatial terms. Subsequently, many different robust functions have been explored (Brox et al. 2004; Lempitsky et al. 2008; Sun et al. 2008) and it remains unclear which is best. We refer to all these spatially-discrete formulations derived from HS as “classical.” We systematically explore variations in the formulation and optimization of these approaches. The surprise is that the classical model, appropriately implemented, remains fairly competitive.

There are many formulations beyond the classical ones that we do not consider here. Significant ones use oriented smoothness (Nagel and Enkelmann 1986; Sun et al. 2008; Wedel et al. 2009; Zimmer et al. 2011, 2009), rigidity constraints (Wedel et al. 2008a, 2009), an over-parameterized smoothness term (Nir et al. 2008), or image segmentation (Black and Jepson 1996; Lei and Yang 2009; Xu et al. 2008; Zitnick et al. 2005). While they deserve similar careful consideration, we expect many of our conclusions to carry forward. Note that one can select among a set of models or methods for a given sequence (Mac Aodha et al. 2010), instead of finding a “best” model for all the sequences.

Many of the implementation details that are thought to be important date back to the early days of optical flow. Current best practices include coarse-to-fine estimation to deal with large motions (Bergen et al. 1992; Brox et al. 2004), texture decomposition (Wedel et al. 2008a, b) or high-order filter constancy (Adelson et al. 1984; Brox et al. 2004; Glaer et al. 1983; Lempitsky et al. 2010; Zimmer et al. 2009) to reduce the influence of lighting changes, incremental warping (Bergen et al. 1992), warping with bicubic interpolation (Lempitsky et al. 2008; Wedel et al. 2008b), temporal averaging of image derivatives (Horn 1986; Wedel et al. 2008b), graduated non-convexity (Blake and Zisserman 1987) to minimize non-convex energies (Black and Anandan 1996; Sun et al. 2008), and median filtering after each incremental estimation step to remove outliers (Wedel et al. 2008b).

This median filtering heuristic is of particular interest as it makes non-robust methods more robust and improves the accuracy of all methods we tested. The effect on the objective function and the underlying reason for its success have not previously been analyzed. Least median squares estimation can be used to robustly reject outliers in flow estimation (Bab-Hadiashar and Suter 1998), but previous work has focused on the data term.

Related to median filtering, and our new non-local term, is the use of bilateral filtering to prevent smoothing across motion boundaries (Xiao et al. 2006). This approach separates a variational method into two filtering update stages, and replaces the original anisotropic diffusion process with multi-cue driven bilateral filtering. As with median filtering, the bilateral filtering step changes the original energy function.

Models that are formulated with an L1 robust penalty are often coupled with specialized total variation (TV) optimization methods (Zach et al. 2007). Here we focus on generic optimization methods that can apply to most models and find that the estimated flow fields are as accurate as the reported results for specialized methods.

Despite recent algorithmic advances, there is a lack of publicly available, easy to use, and accurate flow estimation software. The GPU4Vision project (http://​gpu4vision.​icg.​tugraz.​at; last accesed 24 July 2013) has made a substantial effort to change this and provides executable files for several accurate methods (Wedel et al. 2008a, b, 2009; Werlberger et al. 2009). The dependence on the GPU and the lack of source code are limitations. Since the publication of our conference paper, our public Matlab code has been used by both researchers to develop new optical flow algorithms (Adato et al. 2011; Chen et al. 2012, 2013; Jia et al. 2011; Krähenbühl and Koltun 2012) and practitioners to use optical flow for different applications (Humayun et al. 2011; Lin and Fisher 2012; Niu et al. 2012). Currently other available optical-flow software includes (http://​lmb.​informatik.​uni-freiburg.​de/​resources/​software.​php; last accessed 24 July 2013 http://​people.​csail.​mit.​edu/​celiu/​OpticalFlow/​; last accessed 24 July 2013 http://​www.​cse.​cuhk.​edu.​hk/​leojia/​projects/​flow/​; last accessed 24 July 2013).

To gain robustness against lighting changes, we follow Wedel et al. (2008b) and apply the Rudin–Osher–Fatemi (ROF; Rudin et al. 1992) structure texture decomposition method to pre-process the input sequences and linearly combine the texture and structure components (in the proportion 20:1). The parameters are set according to Wedel et al. (2008b).

Optimization is performed using a standard incremental multi-resolution technique (e. g., Black and Anandan 1996; Brox et al. 2004) to estimate flow fields with large displacements. The optical flow estimated at a coarse level is used to warp the second image toward the first at the next finer level, and a flow increment is calculated between the first image and the warped second image. The standard deviation of the Gaussian anti-aliasing filter is set to be \(\frac{1}{\sqrt{2 d}}\), where \(d\) denotes the downsampling factor. Each level is recursively downsampled from its nearest lower level. In building the pyramid, the downsampling factor is not critical as pointed out in the next section; here we use the settings of Sun et al. (2008), which uses a factor of 0.8 in the final stages of the optimization. For the basic pyramid scheme, we adaptively determine the number of pyramid levels so that the top level has a width or height of around 20–30 pixels. At each pyramid level, we perform 10 warping steps to compute the flow increment.

At each warping step, we linearize the data term once, which involves computing terms of the type \(\frac{\partial }{ \partial x} I_2(i+u^k_{i,j}, j+v^k_{i,j})\), where \({\partial }/\partial x\) denotes the partial derivative in the horizontal direction, \(u^k\) and \(v^k\) denote the current flow estimate at iteration \(k\). As suggested by Wedel et al. (2008b), we compute the derivatives of the second image using the 5-point derivative filter \(\frac{1}{12}[-1 \ 8 \ 0 \ -8 \ 1]\), and warp the second image and its derivatives toward the first using the current flow estimate by bicubic interpolation. We then compute the spatial derivatives of the first image, compute the average of these and the corresponding warped derivatives of the second image (cf. Álvarez et al. 2007; Horn 1986), and use these in place of \(\frac{\partial I_2}{\partial x}\). For pixels moving out of the image boundaries, we set both their corresponding temporal and spatial derivatives to zero. After each warping step, the flow update is computed, and then we apply a \(5\times 5\) median filter to the newly computed flow field to remove outliers (Wedel et al. 2008b).

For the Charbonnier (Classic-C) and Lorentzian (Classic-L) penalty function, we use a graduated non-convexity scheme (GNC; Blake and Zisserman 1987) as described by Sun et al. (2008). First, we replace the robust penalty functions by quadratic penalty functions and obtain a quadratic formulation of the objective function, \(E_Q(\mathbf{u }, \mathbf{v })\). Then we linearly combine the quadratic penalty function with the desired robust penalty function and gradually change the weighting of the two terms to reach the desired robust penalty function. In practice, we use a three-stage GNC scheme, with the objective functions for the first, second, and third stages being \(E_Q(\mathbf{u }, \mathbf{v })\), \(\frac{1}{2}\big ( E_Q(\mathbf{u }, \mathbf{v }) + E(\mathbf{u }, \mathbf{v }) \big )\), and \(E(\mathbf{u }, \mathbf{v })\) respectively. The output of a previous stage serves as the initialization to the next stage. The standard deviations of the corresponding quadratic penalty function are set to be 1 for the Charbonnier penalty and, for the Lorentzian, are taken to be the same as the \(\sigma \) value used in the Lorentzian function. The same regularization weight \(\lambda \) is used for both the quadratic and the robust objective functions.

The regularization parameter \(\lambda \) is selected among a set of candidate values to achieve the best average end-point error (EPE) on the Middlebury training set. For the Charbonnier penalty function, the candidate set is \([1,3,5,8,10]\) and \(5\) is optimal. The Charbonnier penalty uses \(\epsilon =0.001\) for both the data and the spatial term in Eq.  1. The Lorentzian uses \(\sigma = 1.5\) for the data term, \(\sigma = 0.03\) for the spatial term, and \(\lambda =0.06\). These parameters are fixed throughout the experiments, except where mentioned.

Table 1 summarizes the EPE results of the basic model with three different penalty functions on the Middlebury test set, along with the two top performers at the time of performing the evaluation (considering only published papers when the evaluation table was generated). Table 2 provides detailed results for each sequence. The classic formulations with two non-quadratic penalty functions (Classic-C) and (Classic-L) achieve competitive results despite their simplicity. The baseline optimization of HS and BA (Classic-L) results in significantly better accuracy than previously reported for these models (Sun et al. 2008). Note that the analysis also holds for the training set (Table 3).

Because Classic-C performs quite well despite its simplicity, we set it as the baseline below. Note that our baseline implementation of HS has a lower average EPE than many more sophisticated methods. The HS implementation here incorporates many algorithmic and implementation details not present in the original HS method; the core idea of quadratic data and spatial terms however remains the same. In our naming convention, one can think of the HS method here as Classic-Q, meaning that it is the same as the Classic-C method except that the data and spatial penalty terms are quadratic.

While it is common to talk about the brightness constancy assumption as a core feature of most optical flow algorithms, in practice many other constancy assumptions have been used. It is common, for example, to pre-filter the images in a variety of ways ranging from simple smoothing to edge detection. For each method, we optimize the regularization parameter \(\lambda \) for the training sequences. The results are summarized in Table 3, with details of the methods applied to individual training sequences given in Tables 4 and 5. The baseline uses a non-linear pre-filtering of the images (ROF) to reduce the influence of illumination changes between frames (Wedel et al. 2008b). Table 3 shows the effect of using no pre-processing, resulting in the standard brightness constancy model (*-brightness). Classic-C-brightness actually achieves lower EPE on the training set than does Classic-C but significantly higher error on the test set (Table 1). This disparity suggests overfitting to the training data and leaves open the question as to whether the standard brightness constancy assumption, formulated robustly, may still compete with various types of filter/structure constancy given appropriate training data.

Simpler alternatives, such as filter response (or high-order) constancy (Brox et al. 2004; Bruhn & Weickert 2005; Sun et al. 2008) can serve the same purpose as ROF texture decomposition. A variety of pre-filters have been used in the literature, including derivative filters, Laplacians (Burt et al. 1982; Lempitsky et al. 2010), and Gaussians. Edges have also been emphasized using the Sobel edge magnitude (Vaudrey and Klette 2009).

Gradient only imposes constancy of the gradient vector at each pixel as proposed by Brox et al. (2004); i. e.,  it robustly penalizes the Euclidean distance between image gradients. We use central difference filters (\(Dx = [-0.5 \ 0 \ 0.5]\) and \(Dy = Dx^T\)). Gaussian+Dx+Dy assumes separate brightness, horizontal derivative, and vertical derivative constancy. A weighted combination of robust functions applied to each term is used as by Sun et al. (2008). Neither of these methods differ significantly from the baseline texture decomposition (Classic-C). Two methods are significantly worse: the Sobel edge magnitude (Vaudrey and Klette 2009) and Laplacian pre-filtering (\(5\times 5\)) as used by Lempitsky et al. (2010). Sobel edge magnitude appears to not work well on some of the sequences, particularly the synthetic ones, and may not be suitable for a general flow estimation method. Laplacian pre-filtering (\(5\times 5\)) as used by Lempitsky et al. (2010) produces good results on “RubberWhale”, but poor ones on the synthetic sequences. Note that the parameters for the FusionFlow method (Lempitsky et al. 2010) were mainly tuned using the “RubberWhale” sequence. The evaluation results suggest room for improving the FusionFlow method by a better pre-processing technique. Gaussian pre-filtering (\(\sigma = 0.5\)) performed well on the synthetic sequences, but poorly on real ones. Finally, the texture-structure blending ratio is 20:1 in Wedel et al. (2008b) but 4:1 in Werlberger et al. (2009). We find that (Texture4:1) performs better (but not significantly) on the synthetic sequences with a little degradation on the real ones. By default, the blended result from texture decomposition is normalized to \([-1, 1]\) by Wedel et al. (2008b) and [0, 255] in our experiment. Not doing this normalization (Unnormalized texture) has little effect.

For the Laplacian pre-filtering, we find combining the filtered image with the original image, in the proportion 1:1, improves accuracy significantly (Laplacian1:1). Similar to the ROF texture decomposition, such an approach boosts the high frequency while suppressing the low frequency components that contain the lighting change.

We vary the number of warping steps per pyramid level and find that 3 warping steps gives similar results as using the baseline 10 (Table 6), except on “Urban3”, which is dominated by large motion and occlusions (see Table 7 for sequence-specific results). For the coarse-to-fine pyramid, Sun et al. (2008) use a downsampling factor of 0.8 during non-convex optimization. A traditional downsampling factor of 0.5 (Down- \(0.5\) ), however, has nearly identical performance. Note that a larger factor means that the pyramid levels are more similar in size and, for a pyramid with top bottom levels of the same size, results in more pyramid levels.

Previously, Brox et al. (2004) have reported that a downsampling factor of 0.95 produces much better results than 0.5. Note that for each iterative warping estimation step, Brox et al. use successive over-relaxation (SOR) to iteratively solve their linear system of equations and stop the iteration before convergence. With a downsampling factor of 0.95, they effectively increase the number of iterative warping steps performed by the algorithm, and this likely helps the overall algorithm converge. For our implementation, we solve the linear system of equations using the Matlab built-in backslash function and obtain converged results for each iterative warping estimation step. Under such a setting, we find that the downsampling factor has little influence on the performance.

Removing the GNC procedure for the Charbonnier penalty function (w/o GNC) results in higher EPE on most sequences and higher energy on all sequences (Table 8). This suggests that the GNC method is helpful even for the convex Charbonnier penalty function due to the nonlinearity of the data term.

We find that the baseline bicubic interpolation is more accurate than bilinear (Table 6, Bilinear), as already reported in previous work (Wedel et al. 2008b). Removing temporal averaging of the gradients (w/o TAVG), using a Central difference filter \([-1\ 0\ 1]/2\), or using a 7-point derivative filter \([-1 \ 9 \ -45 \ 0 \ 45 \ -9 \ 1]/60\) (Bruhn et al. 2005) all reduce accuracy compared to the baseline, but not significantly.

The baseline method computes the image derivative by first computing the derivative of the second image, warping the intermediate result toward the first image, and then averaging the warped result with the spatial derivative of the first image. Another approach is to first warp the second image toward the first image, compute the derivatives of the warped image, and then perform the temporal averaging with the spatial derivatives of the first image (Bruhn et al. 2005). We find the second approach produces similar results (Deriv-warp). However, the derivatives computed in either way are inconsistent with those implicitly interpolated by the bicubic interpolation. Bicubic interpolation interpolates not only the image but also the derivatives (Press et al. 2002). Because the Matlab built-in function interp2 is based on cubic convolution (Keys 1981) and does not provide the derivatives used in interpolation, we use the spline-based implementation by Press et al. (2002). With the new implementation (Bicubic-II), the three different ways to compute the derivatives give very similar EPE results, all better than the Matlab built-in function. However, the one with consistent derivatives (Bicubic-II) gives the lowest energy solution, as shown in Table 9.

We find that the convex Charbonnier penalty performs better than the more robust, non-convex Lorentzian on both the training and test sets. We test using the Charbonnier for the data term and Lorentzian for the spatial term (C–L) and vice versa (L–C). The two approaches perform better than using the Lorentzian for both terms but worse than using the Charbonnier for both terms.

One reason might be that non-convex functions are more difficult to optimize, causing the optimization scheme to find a poor local optimum. Another reason might be that the MAP estimator actually favors the “wrong” penalty functions (Nikolova 2007; Schmidt et al. 2010).

We investigate a generalized Charbonnier penalty function \( \rho (x) = (x^2 + \epsilon ^2)^a\) that is equal to the Charbonnier penalty when \(a=0.5\), and non-convex when \(a< 0.5\) (see Fig. 2). We optimize the regularization parameter \(\lambda \) again. We find a slightly non-convex penalty with \(a=0.45\) (GC-0.45) performs consistently better than the Charbonnier penalty, whereas more non-convex penalties (GC-0.25 with \(a=0.25\)) show no improvement.

Good Practices: The less-robust Charbonnier is preferable to the highly non-convex Lorentzian and a slightly non-convex penalty function (GC-0.45) is better still.

Figure 3 illustrates the median filtering step within the coarse-to-fine incremental estimation process. The baseline \(5\times 5\) median filter (MF \(5\times 5\) ) is better than both MF \(3\times 3\) (Wedel et al. 2008b) and MF \(7\times 7\), but the difference is not significant (Table 6). When we perform \(5\times 5\) median filtering twice (\(2\times \) MF) or five times (\(5\times \) MF) per warping step, the results are worse. Finally, removing the median filtering step (w/o MF) makes the computed flow significantly less accurate with larger outliers as shown in Table 6 and Fig. 4.

One interesting result with HS is that repeatedly applying median filtering (20 times) at every warping step improves the HS formulation and the improvement is statistically significant (HS \(20 \times \) MF in Table 10).

Good Practices: Median filtering the intermediate flow results once after every warping iteration is the single most important implementation detail here; \(5\times 5\) is a good filter size.

Combining the analysis above into a single approach means modifying the baseline to use the slightly non-convex generalized Charbonnier and the spline-based bicubic interpolation. This leads to a statistically significant improvement over the baseline (Table 6, Classic++). This method is directly descended from HS and BA, yet updated with the current best optimization practices known to us. This simple method ranks 32th out of 73 methods in both EPE and AAE on the Middlebury test set at the writing of the paper (Sep. 2012). However, as we will see soon, this method is somehow not “simple”. Instead of the original objective, a different objective is being optimized with the median filtering step. The same is true for the reported results of both HS and BA.

Werlberger et al. (2010) independently propose a non-local term for optical flow estimation and the spatial term is similar to our non-local term. They use zero mean normalized cross correlation as the data term to deal with lighting changes. Their work is motivated by the success of the non-local regularization (Buades et al. 2005) in image restoration and stereo. Our work is inspired by the success of the heuristic median filtering step in flow estimation and we formalize the median filtering heuristic as a non-local regularization term. The use of the GPU and C++ makes their implementation faster than our implementation in Matlab. Classic+NL has lower average EPE on the Middlebury test sequences; 0.319 versus 0.388 (cf. Table 2). Readers can visually compare the results of both methods on the Middlebury website.

To test the robustness of these models on other data, we applied HS, Classic-C, and Classic+NL to sequences from the MIT dataset (Liu et al. 2008), and compared the estimated flow fields to the human labeled ground truth. Note only five of the eight test sequences of Liu et al. (2008) are available on-line; these are tested here.

Figure 9 and Table 17 show the results on these sequences, which are very different in nature from the Middlebury set and include an outdoor scene as well as a scene of a fish tank. The results are compared with the CLG method (Bruhn et al. 2005) used by Liu et al. (2008). It is important to point out that the CLG method was tuned to obtain the optimal results on the test sequences. Our method had no such tuning and we used the same parameters as those used in all the other experiments. This suggests that training on the Middlebury data results in a method that generalizes to other sequences. The only place where this fails is on the “fish” sequence where there is transparent motion in a liquid medium; the statistics in this sequence are very different from the Middlebury training data.

We evaluate the methods above (corresponding to our publicly released code) on the MPI Sintel (Butler et al. 2012) and the KITTI (Geiger et al. 2012) datasets using the default parameter settings in our conference paper (Sun et al. 2010a). As summarized by Tables 17 and 19, the conclusions contradict our findings reported above. On the MPI Sintel dataset, HS outperforms Classic++, which in turn outperforms Classic+NL-fast. The only consistent result is Classic+NL, which achieves the best performance. On the KITTI dataset, HS outperforms Classic+NL.

We ask how these datasets differ from both Middlebury and the MIT dataset. What could lead to these inconsistent conclusions? One answer surprisingly lies in the unequal width and height of the images.

Our original implementation downsamples the image equally in the horizontal and vertical dimensions. The method automatically determines the number of pyramid levels using the smaller of the height and width of the input image. This scheme works well when the width-to-height ratio is close to 1, i. e., the Middlebury sequences. In contrast, the MPI Sintel images are \(1,024 \times 436\) and the KITTI images are around \(1,226 \times 370\). The small vertical dimension limits the height of the pyramid, but we find that the large horizontal dimension means that the sequences contain very large horizontal motions. As a result, at the top level of the pyramid, the horizontal motions can be much larger than a pixel.

To address this we can use an unequal downsampling factor in each direction to ensure that the motion at the top pyramid level is small in both directions (or at least similar). For the MPI Sintel and KITTI data sets, we use a downsampling factor of 0.5 in the horizontal direction and determine the downsampling factor in the vertical direction and the pyramid level number, so that the size of top pyramid level is around \(16\times 16\).

For MPI Sintel and KITTI this scheme results in a 7-level pyramid (instead of a 5-level pyramid in the standard symmetric scheme). This results in a significant improvement on both the the MPI Sintel and the KITTI data set, as summarized by Tables 18, 19 and 20. We denote the method with the new asymmetric pyramid by adding an “P” at the end of the name.

On MPI Sintel, the results of the four methods are consistent with those on the Middlebury data set. Note that even Classic++P outperforms the previous Classic+NL. Classic+NLP outperforms MDP-flow2 (Xu et al. 2012) on the final set, but not on the clean set. MDP-flow2 uses feature matching to deal with fast moving objects. Feature matching tends to work well on the clean set, but not the final set due to motion and optical blur in the latter. Figure 10 shows an example visual comparison between results using Classic+NLP and Classic+NL. The asymmetric pyramid leads to significant improvement in areas that undergo large motions.

On the KITTI set, Classic++P performs best among all our tested methods, both in the training and the test sets. Note that the KITTI sequences have been collected on a moving vehicle in an urban environment. The flow fields tend to be smooth with few flow boundaries. The image-independent smoothness assumption in Classic++P is better suited to such data. Figure 11 shows some results for Classic+NL-FastP and Classic+NL-fast; note the dramatic improvement resulting from the asymmetric pyramid.

It is important to note that, apart from the change of pyramid method, all other parameters remain the same and are trained using the Middlebury training sequences.

Table 21 summarizes the running time of the evaluated methods on typical sequences from three different data sets in matlab on a 64-bit Linux desktop with 8GB memory. The additional cost from HS to Classic++ comes from the GNC stage and the non-convex penalty function. The additional cost from Classic++ to Classic+NL comes from the weighted median filtering step for detected motion boundaries. Applying the weighted median operation on all the pixels (Classic+NL-Full) increases the running time by more than three times with little performance gain. Using fewer iterations (Classic+NL-Fast) can significantly reduce the computational cost with little performance loss, especially on sequences with small motion. Note that we solve the weighted median problem at each pixel individually and do not reuse the sorting results from neighboring pixels. Future work should consider reformulating the weighted median filtering so that a convolution-type operation can be used to reduce the computational cost.

Classic+NL produces larger errors in occlusion regions on some sequences, such as “Schefflera” shown in Fig. 12. The classical flow formulation assumes that every pixel at the current frame has a corresponding pixel at the next frame. However, this assumption breaks down in regions of occlusion. Pixels that are occluded by some foreground objects in one frame do not have corresponding pixels in the next, resulting in large errors with classical formulations. In contrast, a layered model (Wang and Adelson 1994) may provide a principled way to reason about occlusions. The motion model developed in this paper has enabled a recent layered approach (Sun et al. 2010b) to achieve a consistent improvement over the Classic+NL method, in particular near occlusion and motion boundary regions.

Small, fast moving objects also cause problems for the classical coarse-to-fine estimation used by Classic+NL, as shown in Fig. 10. The work by Brox and Malik (2011) on large displacement optical flow has inspired recent work (Chen et al. 2013; Steinbrücker et al. 2009; Xu et al. 2012) to embed feature matching into the coarse-to-fine estimation framework. Chen et al. (2013) show that, with proper initialization, Classic+NL can also handle large displacement optical flow on the Middlebury dataset.