NORMALIZED CUT PROBLEMS WITH GENERALIZED LINEAR CONSTRAINTS
Abstract
Several methods are used to process images in many fields, including clustering, image segmentation and medical imaging. The so-called graph-cut methods in graph theory are widely used for image segmentation. In these methods graphs determining the relation between several objects are divided into one or more pieces in order to solve a variety of problems. Most of these methods are unsupervised, which means there is no information known about the data objects. In some of the applications listed above some prior knowledge may be known. Using this prior knowledge can be the key to designing better methods. A novel algorithm called the projected power method used to solve the constraint eigenvalue problem was published by Xu, Li, and Schuurmans in “Fast Normalized Cut with Linear Constraints” [IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2866-2873, Jun. 2009]. It is a variant of the power method which is known to converge often too slow. We propose new methods that use the subspace iteration and Krylov subspaces in a similar fashion to solve the constraint eigenvalue problem more accurately and faster. The study has shown this algorithm can produce better results to a general class of optimization problems which have a larger number of applications and can impact many fields positively. We also explore generalizations to the problem.