Graph Cuts via $\ell_1$ Norm Minimization

10 June 2008

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE)

Vol. 30 (10) , 1866-1871
https://doi.org/10.1109/tpami.2008.82

Abstract

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 l₁ norm minimization that can be solved effectively using interior point methods. This reformulation exposes connections between graph cuts and other related continuous optimization problems. Eventually, the problem is reduced to solving a sequence of sparse linear systems involving the Laplacian of the underlying graph. The proposed procedure exploits the structure of these linear systems in a manner that is easily amenable to parallel implementations. Experimental results obtained by applying the procedure to graphs derived from image processing problems are provided.

Keywords

This publication has 13 references indexed in Scilit:

An Interior-Point Method for Large-Scale -Regularized Least Squares
IEEE Journal of Selected Topics in Signal Processing, 2007
Random Walks for Image Segmentation
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006
Multi-view reconstruction using photo-consistency and exact silhouette constraints: a maximum-flow formulation
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2005
"GrabCut"
Published by Association for Computing Machinery (ACM) ,2004
An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2004
What energy functions can be minimized via graph cuts?
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2004
Linear algebra operators for GPU implementation of numerical algorithms
ACM Transactions on Graphics, 2003
Sparse matrix solvers on the GPU
ACM Transactions on Graphics, 2003
Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
Block Preconditioning for the Conjugate Gradient Method
SIAM Journal on Scientific and Statistical Computing, 1985