Electrical Flow Algorithms for Total Variation Minimization

Details Electrical Flow Algorithms for Total Variation Minimization Electrical Flow Algorithms for Total Variation Minimization

2011-10-06

arxiv.org/abs/1110.1358v1

Computer Science

Computer Vision and Pattern Recognition

Scientific paper

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 L_1-difference of neighboring pixel; and isotropic, where the measure of "smoothness" is based on computing localized L_2-differences and thus is rotationally invariant. There was a lot of work on obtaining efficient algorithms for computing TV 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 [Christiano,Kelner,Madry,Spielman,Teng, STOC 2010]. 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+\epsilon of the optimum solution in time \tilde{O}(m^{4/3} \epsilon^{-8/3}). This bound improves over previous best results for both anisotropic and isotropic total variation.

Affiliated with

Also associated with

No associations

Rating

Electrical Flow Algorithms for Total Variation Minimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Electrical Flow Algorithms for Total Variation Minimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Electrical Flow Algorithms for Total Variation Minimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-182244