Dinkelbach NCUT: An Efficient Framework for Solving Normalized Cuts Problems with Priors and Convex Constraints (Preprint)
Journal article preprint
ILLINOIS UNIV AT URBANA-CHAMPAIGN BECKMAN INST FOR ADVANCED SCIENCES AND TECHNOLOGY
Pagination or Media Count:
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 QPs 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 linearnonlinear 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.