TY - JOUR

T1 - Dinkelbach NCUT

T2 - An efficient framework for solving normalized cuts problems with priors and convex constraints

AU - Ghanem, Bernard

AU - Ahuja, Narendra

N1 - Funding Information:
Acknowledgement The support of the Office of Naval Research under grant N00014-09-1-0017 and the National Science Foundation under grant IIS 08-12188 are gratefully acknowledged.

PY - 2010/8

Y1 - 2010/8

N2 - In this paper, we propose a novel framework, called Dinkelbach NCUT (DNCUT), which efficiently solves the normalized graph cut (NCUT) problem under general, convex constraints, as well as, under given priors on the nodes of the graph. Current NCUT methods use generalized eigen-decomposition, which poses computational issues especially for large graphs, and can only handle linear equality constraints. By using an augmented graph and the iterative Dinkelbach method for fractional programming (FP), we formulate the DNCUT framework to efficiently solve the NCUT problem under general convex constraints and given data priors. In this framework, the initial problem is converted into a sequence of simpler sub-problems (i.e. convex, quadratic programs (QP's) subject to convex constraints). The complexity of finding a global solution for each sub-problem depends on the complexity of the constraints, the convexity of the cost function, and the chosen initialization. However, we derive an initialization, which guarantees that each sub-problem is a convex QP that can be solved by available convex programming techniques. We apply this framework to the special case of linear constraints, where the solution is obtained by solving a sequence of sparse linear systems using the conjugate gradient method. We validate DNCUT by performing binary segmentation on real images both with and without linear/nonlinear constraints, as well as, multi-class segmentation. When possible, we compare DNCUT to other NCUT methods, in terms of segmentation performance and computational efficiency. Even though the new formulation is applied to the problem of spectral graph-based, low-level image segmentation, it can be directly applied to other applications (e.g. clustering).

AB - In this paper, we propose a novel framework, called Dinkelbach NCUT (DNCUT), which efficiently solves the normalized graph cut (NCUT) problem under general, convex constraints, as well as, under given priors on the nodes of the graph. Current NCUT methods use generalized eigen-decomposition, which poses computational issues especially for large graphs, and can only handle linear equality constraints. By using an augmented graph and the iterative Dinkelbach method for fractional programming (FP), we formulate the DNCUT framework to efficiently solve the NCUT problem under general convex constraints and given data priors. In this framework, the initial problem is converted into a sequence of simpler sub-problems (i.e. convex, quadratic programs (QP's) subject to convex constraints). The complexity of finding a global solution for each sub-problem depends on the complexity of the constraints, the convexity of the cost function, and the chosen initialization. However, we derive an initialization, which guarantees that each sub-problem is a convex QP that can be solved by available convex programming techniques. We apply this framework to the special case of linear constraints, where the solution is obtained by solving a sequence of sparse linear systems using the conjugate gradient method. We validate DNCUT by performing binary segmentation on real images both with and without linear/nonlinear constraints, as well as, multi-class segmentation. When possible, we compare DNCUT to other NCUT methods, in terms of segmentation performance and computational efficiency. Even though the new formulation is applied to the problem of spectral graph-based, low-level image segmentation, it can be directly applied to other applications (e.g. clustering).

KW - Conjugate gradient method

KW - Dinkelbach method for fractional programming

KW - Eigen-decomposition

KW - Graph cuts

KW - Graph theory

KW - Graph-based image segmentation

KW - Interactive segmentation

KW - Multi-way segmentation

KW - Normalized graph cuts

KW - Quadratic programming

UR - http://www.scopus.com/inward/record.url?scp=77951295401&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951295401&partnerID=8YFLogxK

U2 - 10.1007/s11263-010-0321-2

DO - 10.1007/s11263-010-0321-2

M3 - Article

AN - SCOPUS:77951295401

SN - 0920-5691

VL - 89

SP - 40

EP - 55

JO - International Journal of Computer Vision

JF - International Journal of Computer Vision

IS - 1

ER -