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.
  • NEW *EXACT* IMPLEMENTATION (Jan. 2024): download and unzip this file and maxflow-v3.04.src.zip from V. Kolmogorov's software page. Please see instructions in the header of the graphTV.cpp file.
  • A networkx-based python implementation is found here but it is very slow (just unzip the file, this dummy site does not allow to share python code).
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.