Min-Cut/Max-Flow Problem Instances for Benchmarking

Min-Cut/Max-Flow Problem Instances for Benchmarking

This is a collection of min-cut/max-flow problem instances that can be used for benchmarking min-cut/max-flow algorithms. The collection is released in companionship with the paper:

• Jensen et al., “Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision”.

The problem instances are collected from a wide selection of sources to be as representative as possible. Specifically, this collection contains:

• Many of the problem instances (some are unavailable due to dead links) published by the University of Waterloo at https://vision.cs.uwaterloo.ca/data/maxflow :

  • Stereo problems based on [B98] and [K01].

  • 3D Segmentation problems based on [B01], [B06a], [B03].

  • Multi-view reconstruction problems based on [L06] and [B06b].

  • Surface fitting problems based on [L07].

• Problem instances from from Verma’s & Batra’s review paper [V12]:

  • Super resolution based on [F00] and [R07].

  • Texture restoration based on [R07].

  • Deconvolution based on [R07].

  • Decision tree field (DTF) based on [N11].

  • Automatic labelling environment (ALE) based on [E10], [ALE], [L09], and [L10].

• Sparse Layered Graph (SLG) problems from [J20a].

• Multi object surface fitting problems from [J20b].

• Deep LOGISMOS surface fitting problem based on [G18].

• Oriented MRF segmentation based on [B04], [R21], [E14].

• U-Net segmentation cleaning with MRFs based on [B04] “An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision”, 2004, PAMI:

  • Cleaning of V-Net segmentations based on [R21], [M16], [E14].

  • Cleaning of U-Net segmentations based on [S19], [C16].

• Mesh segmentation problems based on [L15].

• Graph matching problems from [H21]. The orignal matching problems can be found at https://vislearn.github.io/libmpopt/iccv2021/. Here, we publish the QPBO subproblems for each matching problem to be used for benchmarking:

  • Wide baseline matching based on [T08] and [C09].

  • Key point matching based on [E10] and [L12].

  • Large displacement flow based on [A15], [S17].

  • OpenGM matching based on [K08], [K15].

  • Worm atlas matching based on [K14].

  • Worm-to-worm matching based on [H12].

The reason for releasing this collection is to provide a single place download all datasets used in our paper (and various previous paper) instead of having to scavenge from multiple sources. Furthermore, several of the problem instances typically used for benchmarking min-cut/max-flow algorithms are no longer available at their original locations and may be difficult to find. By storing the data with a dedicated DOI we hope to avoid this. For license information, please see the README.

Files and formats

We provide all problem instances in two file formats: DIMACS and a costum binary format. Each file has been zipped, and similar files have then been grouped into their own zip file (i.e., it is a zip of zips). DIMACS files have been prefixed with dimacs_ and binary files have been prefixed with bin_.

For additional information on the file formats, please the see the README file.

References

Please see the README file.