Dinkelbach NCUT: An efficient framework for solving normalized cuts problems with priors and convex constraints

Bernard Ghanem, Narendra Ahuja

Research output: Contribution to journalArticlepeer-review


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).

Original languageEnglish (US)
Pages (from-to)40-55
Number of pages16
JournalInternational Journal of Computer Vision
Issue number1
StatePublished - Aug 2010


  • Conjugate gradient method
  • Dinkelbach method for fractional programming
  • Eigen-decomposition
  • Graph cuts
  • Graph theory
  • Graph-based image segmentation
  • Interactive segmentation
  • Multi-way segmentation
  • Normalized graph cuts
  • Quadratic programming

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Dinkelbach NCUT: An efficient framework for solving normalized cuts problems with priors and convex constraints'. Together they form a unique fingerprint.

Cite this