hits counter
Maxflow revisited

An Empirical Comparison of Maxflow Algorithms for Dense Vision Problems

Algorithms for finding the maximum amount of flow possible in a network (or max-flow) play a central role in computer vision problems. We present an empirical comparison of different max-flow algorithms on modern computer vision problems. Our problem instances arise from energy minimization problems in Object Category Segmentation, Image Deconvolution, Super Resolution, Texture Restoration, Character Completion and 3D Segmentation. We compare 14 different implementations and find that the most popularly used implementation of Kolmogorov is no longer the fastest algorithm available.

Baselines Compared

  1. Augmenting-Path (AP) variants.

  2. Push-Relabel (PRL). For sake of completeness, we used two different C implementations of PRL provided by Andrew Goldberg -- called PRF and HIPR. PRF uses both highest-label first and FIFO push orderings, with and without certain relabeling heuristics, and results in 4 variants H-PRF, M-PRF (highest-label first) and Q-PRF, F-PRF. Within the HIPR implementation, the choice of preflow initialization seems to matter, resulting in three different variants HIPR-New, HIPR-Old and HIPR-Wave.

  3. Pseudoflow: We used the C++ implementation provided by Chandran and Hochbaum, and compared the following variants: highest-label-first (HI) and lowest-label-first (LO) processing of root nodes; and FIFO and LIFO ordering of roots among roots of same label. This resulted in 4 variants: HPF-HI-FIFO, HPF-HI-LIFO, HPF-LO-FIFO and HPF-LO-LIFO.

  4. Back to top

Experimental Data

We used DIMAC graph files as a standard input to all the algorithms. The Boykov-Kolmogorov implementation expects sister edges to appear on adjacent lines in the file. Thus, our DIMAC files have this property. We tested all algorithms on the following problems:

  1. Synthetic Graphs
  2. ALE Graphs
  3. Deconvolution
  4. Super Resolution
  5. Texture Restoration
  6. DTF Graphs
  7. 3D Segmentation


4/1/2015 UPDATE: The files released below contain a corruption. The file content of both superres_graph.txt and texture_graph.txt is identical. And a lot of edges have 0 capacity. Thank you to Daniel Prusa for pointing this out. Daniel was also kind enough to re-process our raw data and provide corrected files for super resolution and texture models.
Corrected files available here: http://cmp.felk.cvut.cz/~prusapa1/maxflow-revisited/QPBO-files.zip

    Synthetic Graphs


    We constructed synthetic 2-label segmentation problems, where we started with a basic grid structure on a 200 x 200 image, and randomly added long-range edges depending on a density parameter. The edge-capacities were sampled from Gaussians.

    All Synthetic Graphs

    Single file too large. Please download in parts.

    Part 1

    rand_sis_1.tar.gz ~600 MB

    Part 2

    rand_sis_2.tar.gz ~600 MB

    Part 3

    rand_sis_3.tar.gz ~600 MB

    Part 4

    rand_sis_4.tar.gz ~600 MB

    Part 5

    rand_sis_5.tar.gz ~600 MB

    Part 6

    rand_sis_6.tar.gz ~600 MB

    Part 7

    rand_sis_7.tar.gz ~600 MB

    Part 8

    rand_sis_8.tar.gz ~600 MB

    Part 9

    rand_sis_9.tar.gz ~600 MB

    Part 10

    rand_sis_10.tar.gz ~600 MB

    ALE Graphs


    The Automatic Labeling Environment (ALE) implements the Associative Hierarchical CRF framework of Ladicky et al., which achieved competitive results in recent years' PASCAL object category segmentation challenges. ALE includes many kinds of potentials: unary potentials based on textonboost features, Pn Potts terms and a global co-occurrence potential. Inference in ALE is performed with graph-cuts-based alpha-expansion. We ran ALE on 10 images from PASCAL VOC 2010 segmentation dataset and modified the code to save max-flow graphs in each iteration of alpha-expansion resulting in 337 graphs.

    Graphs for different Alpha-Expansion iterations

    Combined Folder Part 1 ~1.1 GB
    Combined Folder Part 2 ~1.5 GB

    Graphs with different input images

    Combined Folder Part 1 ~1.6 GB
    Combined Folder Part 2 ~1.5 GB
    Combined Folder Part 3 ~1.5 GB

    Deconvolution


    Given a blurry and noisy (binary) input image the task in image de-convolution is to reconstruct the original sharp image. We use the ``CVPR'' instance from Rother et al. CVPR07. Given an n X n blur-kernel, the MRF connectivity is (2n - 1) X (2n - 1) -1. For a 3x3 blur-kernel, this model contains ~45,000 triplets, and for a 5x5 blur-kernel ~450,000 triplets. This is an extremely dense graph and the problem is not submodular. We saved the QPBO graph to file and ran all methods on this graph.

    deconv.tar.gz ~0.5 MB

    Super Resolution


    The goal in image super resolution is to predict a high-res image given a low-res image. Freeman et al. IJCV00 showed how to formulate this as a labelling problem on patches, where the labels index into a dictionary of patches. We use the models of Rother et al. CVPR07, and saved the QPBO graphs to file.

    superres_graph.txt.tar.gz ~2.3 MB
    Please see 4/1/2015 UPDATE above.

    Texture Restoration


    In this task, the goal is to denoise a noisy texture image. We used the Brodatz texture D103 model from Rother et al. CVPR07 and again saved the QPBO graphs to file.

    texture_graph.txt.tar.gz ~2.3 MB
    Please see 4/1/2015 UPDATE above.

    DTF Graphs


    Decision Tree Field (DTF) is a recently introduced model that combines random forests and conditional random fields. DTF models tend to involve particularly difficult inference problem. We used 99 instances provided by Nowozin et al. ICCV11 and saved the QPBO-graphs to file.

    dtf.tar.gz ~429 MB

    3D Segmentation


    Finally, we also evaluated all algorithms on the standard benchmark for such studies, the binary 3D (medical) segmentation instances from the University of Western Ontario (babyface, liver and bone with 6 and 26 connectivity).

    sis_babyface.n6c10.max.tar.gz ~94 MB
    sis_babyface.n26c10.max.tar.gz ~345 MB
    sis_liver.n6c10.max.tar.gz ~98 MB
    sis_liver.n26c10.max.tar.gz ~268 MB
    sis_bone.n6c10.max.tar.gz ~161 MB
    sis_bone.n26c10.max.tar.gz ~579 MB

People

    Tanmay Verma (tanmay08054@iiitd.ac.in)
    Dhruv Batra

Citation

    Please cite the following paper if you use the data provided on this page.

    MaxFlow Revisited: An Empirical Comparison of Maxflow Algorithms for Dense Vision Problems
    Tanmay Verma, Dhruv Batra
    BMVC 2012

    Back to top