Efficient Threshold Selection for Multivariate Total Variation Denoising

ABSTRACT

Total variation (TV) denoising is still attracting attention with theoretical and computational motivations, for its conceptual simplicity of solving a lasso-like convex problem and its good properties for preserving sharp edges and contours in objects with spatial structures like natural images, although more modern and recent techniques specifically tailored to image processing have been developed. TV induces variation-sparsity in the sense that the reconstruction is piecewise constant with a small number of jumps. A threshold parameter λ controls the number of jumps and the quality of the estimation. Since calculation of the TV estimate in high dimension is computationally intensive for a given λ, we propose to calculate the TV estimate for only two sequential λ’s. Our adaptive procedure is based on large deviation of stochastic processes and extreme value theory. We also show that TV can perform exact segmentation in dimension one, under an alternating sign condition for some prescribed threshold. We apply our procedure to denoise a collection of 1D and 2D test signals verifying empirically the effectiveness of our approach. Codes are given to reproduce our results in a provided PURL.

KEYWORDS:

• Empirical processes
• Image processing
• Segmentation
• Smoothing
• Sup norm minimization

Acknowledgments

The authors are grateful to Jon A. Wellner for his help on a proof regarding the large deviation probabilities of certain empirical processes encountered in this work. The authors also thank Michael Saunders and Jairo Diaz Rodriguez for their helpful comments and discussions, Peyman Milanfar for providing test images, and the Stanford Research Computing Center for providing computational resources and support that have contributed to these research results. The authors thank the reviewers, the associate editor, and the editor for improving the exposition of this article. This work was partially done using R Core Team (2015) and Matlab.

Additional information

Funding

This work was funded by the Swiss National Science Foundation and by the National Science Foundation Grants DMS0906812 (American Reinvestment and Recovery Act) and DMS-1418362 (‘Big-Data’ Asymptotics: Theory and Large-Scale Experiments).