论文标题
评论计算机视觉的串行和平行最小/最大流量算法
Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision
论文作者
论文摘要
最小切割/最大流量（最小速度/最大流）算法解决了计算机视觉中的各种问题，因此已经为开发快速的最小/最大流量算法所付出了重大努力。结果，很难为给定问题选择理想的算法。此外，尚未对平行算法进行比较。在本文中，我们评估了最大的一组计算机视觉问题集，评估了最先进的串行和平行的最低点/最大流量算法。我们专注于通用算法，即用于非结构化图，但也与专门的GridCut实现进行了比较。如果适用，GridCut的性能最好。否则，两种伪流算法，Hochbaum pseudoflow and earthe bractth thertth首次搜索，可以实现总体最佳性能。测试的最有效的内存有效实现是Boykov-Kolmogorov算法。在通用的平行算法中，我们发现Liu和Sun的自下而上的合并方法是最好的，但没有任何方法是主导的。在通用并行方法中，只有平行的prefly推送标签算法才能在问题尺寸的许多处理器上有效地扩展，并且没有一般的并行方法始终优于串行算法。最后，我们提供并评估算法选择的策略，以获得良好的预期性能。我们将数据集和实施公开用于进一步研究。
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 ideal 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 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.
