Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision

Area of Science:

• Computer Vision
• Graph Algorithms
• Computational Imaging

Background:

• Minimum cut/maximum flow (min-cut/max-flow) algorithms are crucial for diverse computer vision tasks.
• A wide array of serial and parallel algorithms exist, making selection difficult.
• Comprehensive comparisons, especially for parallel algorithms on unstructured graphs, are lacking.

Purpose of the Study:

• To systematically evaluate state-of-the-art serial and parallel min-cut/max-flow algorithms.
• To compare generic algorithms against specialized implementations like GridCut.
• To provide guidance for algorithm selection in computer vision applications.

Main Methods:

• Benchmarking of leading serial and parallel min-cut/max-flow algorithms on an extensive dataset of computer vision problems.
• Inclusion of generic algorithms for unstructured graphs and specialized methods like GridCut.
• Evaluation of algorithm performance, memory efficiency, and scalability.

Main Results:

• GridCut demonstrated superior performance when applicable.
• Hochbaum pseudoflow and excesses incremental breadth-first search algorithms showed the best overall performance among generic methods.
• The Boykov-Kolmogorov algorithm was the most memory-efficient.
• Among parallel generic algorithms, Liu and Sun's bottom-up merging approach was effective, but no single method dominated.
• The parallel preflow push-relabel algorithm exhibited strong scalability with multiple processors.
• No generic parallel method consistently outperformed serial algorithms.

Conclusions:

• Pseudoflow algorithms are highly competitive for general computer vision problems.
• Specialized algorithms like GridCut offer significant advantages where applicable.
• Parallel algorithms show promise for scalability, but generic methods do not consistently surpass serial performance.
• Strategies for algorithm selection are proposed to optimize performance.
• Publicly releasing the dataset and implementations facilitates future research.