Efficient Schemes for Total Variation Minimization Under Constraints in Image Processing
Efficient Schemes for Total Variation Minimization Under Constraints in Image Processing
复制标题
DOI：
10.1137/070696143
复制
发表时间：
2009-02
期刊：
影响因子：
--
通讯作者：
P. Weiss;L. Blanc-Féraud;G. Aubert
中科院分区：
文献类型：
--
作者：
P. Weiss;L. Blanc-Féraud;G. Aubert
本文给出了在一般凸约束下最小化全变差和更一般的$L^1范数的新的快速算法。这样的问题是图像处理的标准。这些算法是基于尤里·内斯特罗夫提出的凸优化的最新进展。根据数据保真项的正则性，我们可以解决原始问题或对偶问题。首先，我们证明了标准一阶格式在最坏的情况下可以在$O(FRAC{1}{\epsilon^2})$迭代中得到精度为$\epsilon$的解。对于一般的凸约束，我们提出了一个在$O(FRAC{1}{\epsilon})$迭代中得到精度为$\epsilon$的方案。对于强凸约束，我们用一个需要$O(FRAC{1}{\Sqrt{\epsilon})$迭代得到精度$\epsilon$的格式来解决一个对偶问题。最后，我们对图像处理中的各种问题进行了数值实验，验证了理论结果。
This paper presents new fast algorithms to minimize total variation and more generally $l^1$-norms under a general convex constraint. Such problems are standards of image processing. The algorithms are based on a recent advance in convex optimization proposed by Yurii Nesterov. Depending on the regularity of the data fidelity term, we solve either a primal problem or a dual problem. First we show that standard first-order schemes allow one to get solutions of precision $\epsilon$ in $O(\frac{1}{\epsilon^2})$ iterations at worst. We propose a scheme that allows one to obtain a solution of precision $\epsilon$ in $O(\frac{1}{\epsilon})$ iterations for a general convex constraint. For a strongly convex constraint, we solve a dual problem with a scheme that requires $O(\frac{1}{\sqrt{\epsilon}})$ iterations to get a solution of precision $\epsilon$. Finally we perform some numerical experiments which confirm the theoretical results on various problems of image processing.