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.