SimpleFlow: A non-iterative, sublinear optical flow algorithm

Figure 1: The figure shows a pair of 4K video frames (a,b) and the corresponding optical flow result (d). Our new SimpleFlow algorithm computes the optical flow using only local operations that can be efficiently implemented on parallel architectures such as GPUs. Further, it concentrates computation where motion actually occurs, in black in (c), and uses linearly interpolation to estimate the flow in other regions, in gray in (c). This enables the computation of accurate optical maps in a reasonable amount of time (d). We show that this strategy makes the running time grow sublinearly with the frame resolution (e). This enables the processing of high-definition videos up to the 4K movie resolution in which each frame has 9 megapixels. Optical flow is a critical component of video editing applications, e.g. for tasks such as object tracking, segmen-tation, and selection. In this paper, we propose an optical flow algorithm called SimpleFlow whose running times increase sublinearly in the number of pixels. Central to our approach is a probabilistic representation of the mo-tion flow that is computed using only local evidence and without resorting to global optimization. To estimate the flow in image regions where the motion is smooth, we use a sparse set of samples only, thereby avoiding the expensive computation inherent in traditional dense algorithms. We show that our results can be used as is for a variety of video editing tasks. For applications where accuracy is paramount, we use our result to bootstrap a global optimization. This significantly reduces the running times of such methods without sacrificing accuracy. We also demonstrate that the SimpleFlow algorithm can process HD and 4K footage in reasonable times. 1