Algorithms for Computer Vision

IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022

Patrick M. Jensen,
Niels Jeppesen,
Anders B. Dahl,
Vedrana A. Dahl

Department of Applied Mathematics and Computer Science

Technical University of Denmark

Minimum cut/maximum flow (min-cut/max-flow) algorithms solve a variety of problems in computer vision and thus significant effort has been put into developing fast min-cut/max-flow algorithms. As a result, it is difficult to choose an optimal algorithm for a given problem. Furthermore, parallel algorithms have not been thoroughly compared. In this paper, we evaluate the state-of-the-art serial and parallel min-cut/max-flow algorithms on the largest set of computer vision problems yet. We focus on generic algorithms , i.e., for unstructured graphs, but also compare with the specialized GridCut implementation. When applicable, GridCut performs best. Otherwise, the two pseudoflow algorithms, Hochbaum pseudoflow and excesses incremental breadth first search, achieves the overall best performance. The most memory efficient implementation tested is of the Boykov-Kolmogorov algorithm. Amongst generic parallel algorithms, we find the bottom-up merging approach by Liu and Sun to be best, but no method is dominant. Of the generic parallel methods, only the parallel preflow push-relabel algorithm is able to efficiently scale with many processors across problem sizes, and no generic parallel method consistently outperforms serial algorithms. Finally, we provide and evaluate strategies for algorithm selection to obtain good expected performance. We make our dataset and implementations publicly available for further research

We compare the main serial algorithms used in computer vision. We measure the *relative performance (RP)* w.r.t. the fastest algorithm for each min-cut/max-flow problem. Distributions close to one means an algorithm was often the fastest. EIBFS and HPF have the best performance.

Comparison on total times (init. + solve)

Comparison on solve times

We also compare variations of each algorithm w.r.t. a reference (see paper for details) to show the effects of implementation details. **Blue** shows total time speed-up and **red** shows solve time speed-up.

Comparison of BK variants

Comparison of EIBFS variants

Comparison of HPF variants

We compare the state-of-the-art parallel algorithms for min-cut/max-flow in computer vision. We measure the speed-up on solve time w.r.t. the best serial algorithm for each min-cut/max-flow problem. All parallel algorithms have median speed-ups less than one.

Speed-up of parallel algorithms compared to best serial algorithm.

We also measure the speed-up of each algorithm w.r.t. their single threaded performance. Only P-PPR shows consistent improvements with more threads.

Speed-up of Liu-Sun

Speed-up of Strandmark-Kahl

Speed-up of P-PPR

Speed-up of P-ARD

We evalute different strategies for selecting a min-cut/max-flow algorithm depending on graph knowledge. Each strategy is evaluated on the mean relative performance (RP). A value of one means the strategy always selects the fastest algorithm.

**Scenario 1: No Graph Knowledge:** Here, we select the overall best algorithm. No generic algorithm dominates.

*Only counting grid graphs.

Algorithm | Mean RP ± Std. RP | Min RP | Max RP |
---|---|---|---|

EIBFS-I | 0.59 ± 0.28 | 0.1309 | 1.00 |

EIBFS-I-NR | 0.56 ± 0.32 | 0.0535 | 1.00 |

EIBFS | 0.47 ± 0.23 | 0.1288 | 0.94 |

HI-PR | 0.16 ± 0.17 | 0.0046 | 1.00 |

HPF-H-F | 0.59 ± 0.33 | 0.0279 | 1.00 |

HPF-H-L | 0.64 ± 0.36 | 0.0393 | 1.00 |

HPF-L-F | 0.49 ± 0.29 | 0.0313 | 1.00 |

HPF-L-L | 0.53 ± 0.31 | 0.0312 | 1.00 |

MBK-R | 0.27 ± 0.20 | 0.0006 | 1.00 |

BK | 0.27 ± 0.24 | 0.0005 | 1.00 |

MBK | 0.28 ± 0.22 | 0.0005 | 1.00 |

GridCut* | 0.99 ± 0.03 | 0.6419 | 1.00 |

Algorithm | Mean RP ± Std. RP | Min RP | Max RP |
---|---|---|---|

Liu-Sun | 0.48 ± 0.30 | 0.0667 | 1.00 |

P-PPR | 0.46 ± 0.38 | 0.0133 | 1.00 |

Strandmark-Kahl | 0.23 ± 0.16 | 0.0667 | 0.85 |

P-ARD | 0.35 ± 0.32 | 0.0028 | 1.00 |

GridCut* | 1.00 ± 0.00 | 1.0000 | 1.00 |

Best serial | 0.59 ± 0.33 | 0.1365 | 1.00 |

**Scenario 2: Known Problem Family:** Here, we select the overall best algorithm for each problem family. This gives a high mean RP and for serial algorithms it is a near-optimal strategy.

Problem family | Algorithm | Mean RP |
---|---|---|

3D segmentation: SLG | HPF-H-L | 0.81 |

Multi-view | HPF-H-L | 1.00 |

Surface fitting | GridCut | 1.00 |

3D segmentation: voxel-based | GridCut | 0.98 |

Mesh segmentation | EIBFS-I | 0.95 |

3D segmentation: sep. surfaces | EIBFS-I | 0.92 |

3D MRF | GridCut | 1.00 |

Deep LOGISMOS | EIBFS-I-NR | 0.96 |

Deconvolution | HPF-H-L | 0.96 |

DTF | HPF-H-L | 1.00 |

Super resolution | EIBFS-I | 0.87 |

Stereo 1 | EIBFS-I | 0.99 |

Stereo 2 | EIBFS-I | 1.00 |

ALE | EIBFS-I-NR | 1.00 |

Graph matching: small | HPF-L-L | 1.00 |

Graph matching: small | EIBFS-I-NR | 0.91 |

Graph matching: small | HPF-L-F | 1.00 |

Graph matching: small | HPF-L-L | 1.00 |

Graph matching: small | HPF-L-F | 1.00 |

Graph matching: big | HPF-H | 1.00 |

Mean ± stdev. | 0.97 ± 0.05 |

Problem family | Algorithm | Mean RP |
---|---|---|

3D segmentation: SLG | Liu-Sun | 0.63 |

Multi-view | Serial | 1.00 |

Surface fitting | GridCut | 1.00 |

3D seg.: voxel-based (26-conn.) | Serial | 0.86 |

3D seg.: voxel-based (6-conn.) | GridCut | 1.00 |

Mesh segmentation | P-ARD | 0.88 |

3D segmentation: sep. surfaces | P-PPR | 0.74 |

3D MRF | GridCut | 1.00 |

Mean ± stdev. | 0.89 ± 0.14 |

**Scenario 3: Known Graph:** Here, we train a simple decision tree to predict the best algorithm from summary graph statistics (see paper for details). This works well for serial algorithms but struggles for parallel algorithms.

Decision tree for serial algorithms. Mean RP: 0.82.

Decision tree for parallel algorithms. Mean RP: 0.56.