Max-flow problem instances in vision

From Computer Vision at Western

Jump to: navigation, search
permanent link  
http://vision.cs.uwaterloo.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>.

Dynamic problem instances

Many applications in vision require solving max-flow problem of similar graphs. For example, this happens when an image changes from frame to frame in a video sequence or when solutions are computed for a sequence of nearby locations in an image. Many standard max-flow algorithms can have a "hot start" when solving each new instance by reusing internal data structures. Typically, this significantly speeds up the algorithms compared to independent solution of all instances. Examples of existing dynamic max-flow algorithms are:

  • [KT05] Efficiently solving dynamic markov random fields using graph cuts. P. Kohli and P. Torr. In International Conference on Computer Vision (ICCV), 2005.

Below we posted several examples of dynamic applications. For each download, the starting graph and flow are given by the .max and .sol files outside the folder 'dynamic'. These files 'dynamic+index.max'(.sol) in the 'dynamic' folder specifies consecutive graph change (flow change) over 'dynamic+index-1.max'(.sol). Notice that we give new arc capacities for changed arcs, not incremental capacities.

Part 1 Shape matching

These dynamic maxflow graph instances are based on the shape matching application described in [TGVB13].

Car side view shape matching
Car side view shape matching

Extract download with tar -xvjf <file>.

  • TGVB-car – shape matching with a car template.
Figure shape matching
Figure shape matching

An example of timing for solving these dynamic instances with dynamic max-flow [KT05] and 'static' max-flow [BK04] can be found here. The number of graphs vs time plot is generated for TGVB_person_64bins instance.

Part 2 Video segmentation

These graphs are constructed based on image and video segmentation described in [BJ01] and [KT05].

Video segmentation with known appearance models
Video segmentation with known appearance models
  • VideoSeg – video segmentation with fixed appearance models

An example of timing for solving these dynamic instances with dynamic max-flow [KT05] and 'static' max-flow [BK04] can be found here. The number of frames vs time plot is generated for VideoSegB2 instance.

Video credit: youtube source

Part 3 One-Cut Video segmentation

These dynamic max-flow graph instances render energy consisting of spacial regularization term, L1 color separation term [TGVB13] and L2 temporal consistency term between two consecutive video frames. Appearance model prior is not provided for these instances.

Not only are edge capacities changing in these instances, but also graph structures vary over time. These challenging dynamic graphs benefit from more powerful dynamic maxflow algorithms.

For each download, if new arc capacity is zero, then it means the two vertexes adjacent to the arc are disconnected.

horse video
horse video
giraffe video
giraffe video

video credit: Freiburg-Berkeley Motion Segmentation Dataset

Retrieved from "http://mouse.cs.uwaterloo.ca/viki/Max-flow_problem_instances_in_vision"