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

PDF
3746.pdf Download (436kB) 
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 primaldual algorithm for the dual of the convex cost network flow problem. The primaldual 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 primaldual 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/00255610/ 
Language:  English 
UCL classification:  UCL > School of BEAMS > Faculty of Engineering Science > Adastral Park 
URI:  http://discovery.ucl.ac.uk/id/eprint/3746 
Archive Staff Only
View Item 