UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

New algorithms for the dual of the convex cost network flow problem with application to computer vision

Kolmogorov, V.; Shioura, A.; (2007) New algorithms for the dual of the convex cost network flow problem with application to computer vision. Mathematical Programming Green open access

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
426Kb

Abstract

Motivated by various applications to computer vision, we consider an integer convex optimization problem which is the dual of the convex cost network flow problem. In this paper, we first propose a new primal algorithm for computing an optimal solution of the problem. Our primal algorithm iteratively updates primal variables by solving associated minimum cut problems. The main contribution in this paper is to provide a tight bound for the number of the iterations. We show that the time complexity of the primal algorithm is K ¢ T(n;m) where K is the range of primal variables and T(n;m) is the time needed to compute a minimum cut in a graph with n nodes and m edges. We then propose a primal-dual algorithm for the dual of the convex cost network flow problem. The primal-dual algorithm can be seen as a refined version of the primal algorithm by maintaining dual variables (flow) in addition to primal variables. Although its time complexity is the same as that for the primal algorithm, we can expect a better performance practically. We finally consider an application to a computer vision problem called the panoramic stitching problem. We apply several implementations of our primal-dual algorithm to some instances of the panoramic stitching problem and test their practical performance. We also show that our primal algorithm as well as the proofs can be applied to the L\-convex function minimization problem which is a more general problem than the dual of the convex cost network flow problem.

Type:Article
Title:New algorithms for the dual of the convex cost network flow problem with application to computer vision
Open access status:An open access version is available from UCL Discovery
Publisher version:http://www.springerlink.com/content/0025-5610/
Language:English
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Adastral Park

View download statistics for this item

Archive Staff Only: edit this record