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 non-convex case and derive worst case complexities that are equal or better than existing methods. We show applications to total variation based 2D image processing and computer vision problems based on a Lagrangian decomposition approach. The resulting algorithms are very efficient, offer a high degree of parallelism and come along with memory requirements which are only in the order of the number of image pixels.
Specializing Hochbaum's method to trees yields the following complexities: (i) @math for problems with quadratic unaries, assuming that the values of @math are chosen as in @cite_2 ; (ii) @math for piecewise-linear unaries with @math breakpoints, assuming that the values of @math are computed by a linear-time median algorithm (as discussed in Sec. for chains). Instead of using a linear-time median algorithm, it is also possible to sort all breakpoints in @math time in a preprocessing step.
@cite_2
1490240535
In this paper tube methods for reconstructing discontinuous data from noisy and blurred observation data are considered. It is shown that discrete bounded variation (BV)-regularization (commonly used in inverse problems and image processing) and the taut-string algorithm (commonly used in statistics) select reconstructions in a tube. A version of the taut-string algorithm applicable for higher dimensional data is proposed. This formulation results in a bilateral contact problem which can be solved very efficiently using an active set strategy. As a by-product it is shown that the Lagrange multiplier of the active set strategy is an efficient parameter for edge detection.