MaxFlow Revisited: An Empirical Comparison of Maxflow Algorithms for Dense Vision Problems

Abstract

Algorithms for finding the maximum amount of flow possible in a network (or maxflow) play a central role in computer vision problems. We present an empirical comparison of different max-flow algorithms on modern problems. Our problem instances arise from energy minimization problems in Object Category Segmentation, Image Deconvolution, Super Resolution, Texture Restoration, Character Completion and 3D Segmentation. We compare 14 different implementations and find that the most popularly used implementation of Kolmogorov [5] is no longer the fastest algorithm available, especially for dense graphs.