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

V. Kolmogorov, A. Shioura, Discrete Optimization 6 (2009) 378–393.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
;
Abstract
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 {dot operator} 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.
Publishing Year
Date Published
2009-11-01
Journal Title
Discrete Optimization
Volume
6
Issue
4
Page
378 - 393
IST-REx-ID

Cite this

Kolmogorov V, Shioura A. New algorithms for convex cost tension problem with application to computer vision. Discrete Optimization. 2009;6(4):378-393. doi:10.1016/j.disopt.2009.04.006
Kolmogorov, V., & Shioura, A. (2009). New algorithms for convex cost tension problem with application to computer vision. Discrete Optimization, 6(4), 378–393. https://doi.org/10.1016/j.disopt.2009.04.006
Kolmogorov, Vladimir, and Akiyoshi Shioura. “New Algorithms for Convex Cost Tension Problem with Application to Computer Vision.” Discrete Optimization 6, no. 4 (2009): 378–93. https://doi.org/10.1016/j.disopt.2009.04.006.
V. Kolmogorov and A. Shioura, “New algorithms for convex cost tension problem with application to computer vision,” Discrete Optimization, vol. 6, no. 4, pp. 378–393, 2009.
Kolmogorov V, Shioura A. 2009. New algorithms for convex cost tension problem with application to computer vision. Discrete Optimization. 6(4), 378–393.
Kolmogorov, Vladimir, and Akiyoshi Shioura. “New Algorithms for Convex Cost Tension Problem with Application to Computer Vision.” Discrete Optimization, vol. 6, no. 4, Elsevier, 2009, pp. 378–93, doi:10.1016/j.disopt.2009.04.006.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar