Total variation on a tree Journal Article


Author(s): Kolmogorov, Vladimir N; Pock, Thomas; Rolinek, Michal
Article Title: Total variation on a tree
Affiliation IST Austria
Abstract: We consider the problem of minimizing the continuous valued total variation subject to different unary terms on trees and propose fast direct algorithms based on dynamic programming to solve these problems. We treat both the convex and the nonconvex case and derive worst-case complexities that are equal to or better than existing methods. We show applications to total variation based two dimensional image processing and computer vision problems based on a Lagrangian decomposition approach. The resulting algorithms are very effcient, offer a high degree of parallelism, and come along with memory requirements which are only in the order of the number of image pixels.
Keywords: Dynamic programming; Primal-dual optimization; Total variation
Journal Title: SIAM Journal on Imaging Sciences
Volume: 9
Issue 2
ISSN: 1936-4954
Publisher: Society for Industrial and Applied Mathematics  
Date Published: 2016-05-03
Start Page: 605
End Page: 636
URL:
DOI: 10.1137/15M1010257
Notes: The research of these authors was supported by the European Research Council under the European Union Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement 616160. The research of this author was supported by the European Research Council under the Horizon 2020 program, ERC starting grant agreement 640156.
Open access: yes (repository)