Solving the Graph Cut Problem via l1 Norm Minimization

Graph cuts have become an increasingly important tool for solving a number of energy minimization problems in computer vision and other fields. In this paper, the graph cut problem is reformulated as an unconstrained l1 norm minimization. This l1 norm minimization can then be tackled by solving a sequence of sparse linear systems involving the Laplacian of the underlying graph. The proposed procedure exploits the structure of these linear systems and can be implemented effectively on modern parallel architectures. The paper describes an implementation of the algorithm on a GPU and discusses experimental results obtained by applying the procedure to graphs derived from image processing problems.