Code

Some (possibly obsolete) 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: the idea of the algorithm seems to be due originally 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.