Some code available here:
TVdyadic.tgz: an (approximate) implementation of Dorit Hochbaum's algorithm, see:
- D. S. Hochbaum: An efficient algorithm for image segmentation,
Markov random fields and related problems. J. ACM, 48(4):686--701,
2001.
- A. Chambolle and J. Darbon: On total variation minimization and
surface evolution using parametric maximum flows,
International
Journal of Computer Vision Vol. 84, Nr. 3, Sept. 2009.
This is based on the source maxflow-v2.2.src available at
Vladimir Kolmogorov's
page
and which we also make available
here.
It is a very elementary modification of the original
algorithm described in:
- An Experimental Comparison of Min-Cut/Max-Flow Algorithms
for Energy Minimization in Vision.
Yuri Boykov and Vladimir Kolmogorov.
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI),
September 2004.
TVexact.tgz:
The algorithm of D. Hochbaum for minimizing exactly the Total
Variation plus a quadratic penalization (in other words, computing the
proximity operator of the anisotropic TV), based on the graph-cut code
of Boykov and Kolmogorov, runs under Matlab.
I warmly thank
Jalal Fadili for
having provided this package. Please read the enclosed README file:
This is a Matlab implementation of the fast exact (anisotropic)
TV minimization algorithm by Chambolle and Darbon.
It has been tested under Linux/Unix/MACOSX/Windows(CygWin).
To compile:
./configure
make
Antonin Chambolle, Jérôme Darbon, Jalal Fadili
Note: in fact the original idea of the
algorithm is due to D. Hochbaum (ref. above), and M. J. Eisner,
D. G. Severance: Mathematical techniques for efficient record segmentation in large shared databases, J. Assoc. Comput. Mach., 23(4):619--635, 1976.