Total variation on a tree
This work addresses efficient optimization for total variation-based tasks in image processing, offering incremental improvements in speed and memory usage.
The authors tackled the problem of minimizing continuous-valued total variation on trees for image processing and computer vision, proposing fast dynamic programming algorithms that achieve equal or better worst-case complexities than existing methods and are highly efficient with memory requirements proportional to image pixels.
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.