A deterministic algorithm for optical flow estimation

Motion computation is a fundamental and difficult problem of Computer Vision which regards either the computation of 3-D motion in the image space or the computation of 2-D motion in the image plane. In this paper, we deal with the latter problem, which is also called optical flow. We propose a new deterministic algorithm for determining optical flow through regular- ization techniques so that the solution of the problem is defined as the minimum of an appropriate energy function. We also assume that the displacements are piecewise continu- ous and that the discontinuities are variable to be estimated. More precisely, we introduce a hierarchical three-step optimization strategy to minimize the constructed energy function, which is not convex. In the first step we find a suitable initial guess of the displacements field by a gradient-based GNC algorithm. In the second step we define the local energy of a displacement field as the energy function obtained by fixing all the field with the exception of a row or of a column. Then, through an application of the shortest path technique we minimize iteratively each local energy function restricted to a row or to a column until we arrive at a fixed point. In the last step we use again a GNC algorithm to recover a sub-pixel accuracy. The experimental results confirm the goodness of this technique.