A deterministic algorithm for optical flow estimation based on directed graphs and the shortest path problem

In this paper we propose a new deterministic approach to optical flow estimation which consists of reformulating the problem as a shortest path (SP) problem in a directed graph. The method only requIres that the energy function is a sum of local functions. In the reduction to SP these local functions become the weights of the arcs. The length of each possible path from the source node to the terminal node may be seen as a different value of the energy function. Thus finding the shortest path means finding the mmimurn of the energy function. In particular it exists an algorithm for SP that converges to the optimum in a polynomial time. Since for 2-D Images the total number of nodes needed IS exponential in the size of the images, we adopt an approximation that consists of neglecting, during the execution, the paths and the related nodes which have an excessive high value. Although sub-optimal in this case, the algorithm gives results which are similar to those of stochastic relaxation algorithms, but with a large saving of time. Moreover, with respect to other 1 deterministic approaches, including GNC algorithms, this approach is more flexible to include different constraints derived from all possible prior information on the problem.