Maximum flow for vision

Last week, I decided to try out the IBFS maximum flow algorithm for vision applications for the first time. The algorithm is due to A.V. Goldberg, S.Hed, H. Kaplan, R.E. Tarjan, and R.F. Werneck, who have released an implementation which uses the same interface as the commonly used algorithm by Boykov and Kolmogorov.

My test was very simple, I generated a 128×128 8-connected grid graph, with source and sink arcs computed from the ‘cameraman’ image. I then let the weights of the arcs between the nodes vary several orders of magnitude. The result is quite telling:

The BK algorithm takes over 100 seconds to compute the maximum flow when the regularization is high. By contrast, the IBFS algorithm always uses less than 1 second. Here is the logarithmic plot:


5 Responses to Maximum flow for vision

  1. Curious. By “let the weights of the arcs vary” do you mean you scaled them all by the same amount (w’_ij = scale * w_ij)?

    If edge weights are based on greyscale contrasts, there should be only 256*256 << 10^5 unique values for the w_ij so why would the behaviour start diverging *after* this maximal granularity has been surpassed? Is it floating point craziness or is it really a sort of 'phase transition' in BK's capacity-scale behaviour?

    Anyway, pretty interesting.

  2. Petter says:

    The x-axis show the actual value for all weights (they are all the same).

    The source and sink capacities were computed as the squared difference to two different mean values. These capacities are always the same.

    The post also lack more crucial information: for the second half of the graph there really is no ‘segmentation’; all nodes are assigned to the source or all to the sink.

  3. Petter says:

    I just reran the experiments with long long instead of double and got the same graphs.

  4. Wow, good to know since that should be an easy case in a sense (very few grid arcs saturated, if any).

  5. […] briefly tried the GridCut code ( and performed the same experiments as in the previous post. Below are the updated graphs. #gallery-2 { margin: auto; } #gallery-2 .gallery-item { float: […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s