Electrical Flow Algorithms for Total Variation Minimization
Aleksander Mądry, Gary Lee Miller, Richard Peng · arXiv (Cornell University) · 2011
The total variation (TV) minimization framework is a very popular method for a wide variety of image restoration problems. This framework comes in two variants: anisotropic, where the “smoothness” of the denoised image is measured by L1-difference of neighboring pixel; and isotropic, where the measure of “smoothness” is based on computing localized L2-differences and thus is rotationally invariant. There was a lot of work on obtaining efficient algorithms for computingTV denoising. Most of this effort was focused on anisotropic variant as it was possible to exploit its connection to the maximum flow problem. In case of the isotropic variant, this connection no longer holds and the algorithms in this context rely on convex programming techniques, which results in much slower running time. In this paper we develop an approach to TV minimization that is based on computing electrical flows and builds upon the framework introduced in [CKM + 11]. This approach encompasses in a natural way both variants of TV minimization and obtains running times for both versions that are essentially the same. On an image with n pixels and m neighboring relations, our algorithm produces a solution that’s within 1 + ǫ of the optimum solution in time ˜