An optimal first-order solver for the TV-$L_1$ optical flow problem

In this study, we address the problem of computing efficiently a dense optical flow between two images under a total variation (TV) regularization and an $L_1$ norm data fidelity constraint using a variational method. We build upon Nesterov's framework for convex minimization. By keeping in memory the solution estimated at the previous iteration, this framework yields convergence rates of one order of magnitude faster than existing algorithms, hence is computationally more efficient. We show how to adapt this method to the TV-$L_1$ problem by using a smoothed reformulation of the TV norm to make it continuously differentiable. This relaxation is controlled by a single parameter whose effects are also studied in this paper. Finally, we demonstrate how this fast algorithm can be easily implemented on modern graphics hardware (GPU) using the recently proposed OpenCL Application Programming Interface (API) in order to achieve further speedups.