Max-flow problem instances in vision

From Computer Vision at Western

Jump to: navigation, search
permanent link  
http://vision.csd.uwo.ca/data/maxflow/

Many optimisation techniques in vision use s-t minimum cuts—either directly or as internal subproblems—and their overall performance relies on efficient maximum flow computation. We host a number of problem instances intended for benchmarking max-flow implementations. The datasets below are representative of typical max-flow problems in computer vision, graphics, and biomedical image analysis.

Illustrates max-flow/min-cut instance on a 2D grid graph
Illustrates max-flow/min-cut instance on a 2D grid graph

Contents

Problem format

A maximum flow problem instance is defined by

  • a capacitated digraph {\mathcal G}=(V,A,c), with non-negative arc capacities c:A \rightarrow {\mathbb R}_{\ge 0}, and
  • distinct vertices s, t \in V designated the source and the sink respectively.

All instances are given in DIMACS format (.max) and maximum flow values are given in corresponding DIMACS solution files (.sol).

Note.When applicable, our DIMACS files contain 'hints' indicating repetitive graph structure. This is for the benefit of specialised max-flow implementations. See our graph regularity DIMACS conventions for details.

Stereo instances

Stereo problem instances below are mirrored from V. Kolmogorov's page. Two types of graphs are constructed based on the papers:

Each download contains a sequence of max-flow instances that must be solved by the α-expansion algorithm [BVZ]. This means that each sequence corresponds to the subproblems generated by the first iteration only of α-expansion. In this application it is possible for instances to have no connections to source or sink. The measure of efficiency should be based on total time for each sequence of cuts (tsukuba, sawtooth, venus). Extract each download with tar -xvjf <file>.

BVZ-tsukuba
BVZ-tsukuba
KZ2-tsukuba
KZ2-tsukuba
  • KZ2 – two 4-connected grids w/ sparse connections between them (each vertex is connected to at most two vertices in the other grid); dense terminal arcs from source or to sink.

The tsukuba photo set provided by Tsukuba University. The sawtooth, venus photo sets are from Middlebury Stereo Benchmark.

Segmentation instances

Segmentation problem instances are provided to compare effects of graph size, neighbourhood size, length of {\color{white}g}\!\!\!s \rightarrow t paths, regional arc consistency (noise), and arc capacity magnitude. The graph construction is described in the papers:

Extract each download with tar -xvjf <file>.

liver
liver
adhead
adhead
babyface
babyface
bone
bone
  • bone – each download comes with 6 versions of different size but with essentially the same seeds/cut and 'difficulty' relative to problem scale.
The sizes scale down by a factor of two at each step, and are called:
bone (256×256×119)bone_subxyz (128×128×60)
bone_subx (128×256×119)bone_subxyz_subx (64×128×60)
bone_subxy (128×128×119)bone_subxyz_subxy (64×64×60)
abdomen
abdomen
  • abdomen_long – 512×512×551, very long {\color{white}g}\!\!\!s \rightarrow t paths, longer on t side of cut. Source is connected to center of object, boundary is connected to sink. Compare abdomen_short.
  • abdomen_short – 512×512×551, same cut as abdomen_long, but short paths on both sides of cut. Voxels just outside the object are connected to sink.

The liver, bone, abdomen, babyface volumetric scans were provided by Siemens Corporate Research; adhead volumetric scan was provided by Robarts Research Institute.

Multiview reconstruction instances

The graph constructions for these multiview datasets are based on a cell complex described in [LB06]. The cut optimises an approximation to the functional described in [BL06].

BL06-camel
BL06-camel
BL06-gargoyle
BL06-gargoyle

Extract each download with tar -xvjf <file>.

  • BL06-camel – 3D volumetric cut based on 17 photos.

The gargoyle photo set provided by Kyros Kutulakos. DIMACS instances and camel photo set provided by Victor Lempitsky.

Surface fitting instances

Shape fitting problem instances are coming soon. The graph construction has particularly short {\color{white}g}\!\!\!s \rightarrow t paths, as described in the paper:

LB07-bunny surface; thin band of s/t capacity.
LB07-bunny surface; thin band of s/t capacity.

Extract each download with tar -xvjf <file>.

Retrieved from "http://vision.csd.uwo.ca/viki/Max-flow_problem_instances_in_vision"
Personal tools
Toolbox
hack to reserve spacing for research logo