Primal-dual Algorithm for Convex Markov Random Fields

Computing maximum a posteriori configuration in a first-order Markov Random Field has become a routinely used approach in computer vision. It is equivalent to minimizing an energy function of discrete variables. In this paper we consider a subclass of minimization problems in which unary and pairwise terms of the energy function are convex. Such problems arise in many vision applications including image restoration, total variation minimization, phase unwrapping in SAR images and panoramic image stitching. We give a new algorithm for computing an exact solution. Its complexity is K · T(n,m) where K is the number of labels and T(n,m) is the time needed to compute a maximum flow in a graph with n nodes and m edges. This is the fastest maxflow-based algorithm for this problem: previously best known technique takes T(nK,mK²) time for general convex functions. Our approach also needs much less memory (O(n+m) instead of O(nK+mK²)). Experimental results show for the panoramic stitching problem our method outperforms other techniques.