New algorithms for convex cost tension problem with application to computer vision

作     者：Kolmogorov, Vladimir Shioura, Akiyoshi 

作者机构：Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Univ Coll London Martlesham Heath IP5 7RE England 

出 版 物：《DISCRETE OPTIMIZATION》 (离散优化)

年 卷 期：2009年第6卷第4期

页      面：378-393页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：Engineering and Physical Sciences Research Council, EPSRC Ministry of Education, Culture, Sports, Science and Technology, MEXT 

主　　题：Minimum cost tension Minimum cost flow Discrete convex function Submodular function 

摘      要：Motivated by various applications to computer vision, we consider the convex cost tension problem, which is the dual of the convex cost flow problem. In this paper, we first propose a primal algorithm for computing an optimal solution of the problem. Our primal algorithm iteratively updates primal variables by solving associated minimum cut problems. We show that the time complexity of the primal algorithm is O(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 develop an improved version of the primal algorithm, called the primal-dual algorithm, by making good use of dual variables in addition to primal variables. Although its time complexity is the same as that of the primal algorithm, we can expect a better performance in practice. We finally consider an application to a Computer vision problem called the panoramic image stitching. (C) 2009 Elsevier B.V. All rights reserved.