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:

Advertisements

Related

This entry was posted on Monday, January 30th, 2012 at 8:10 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

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?

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.

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

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.

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.

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

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

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