Abstract | ||
---|---|---|
Normalized cut is a widely used technique for solving a variety of problems. Although finding the optimal normalized cut has proven to be NP-hard, spectral relaxations can be applied and the problem of minimizing the normalized cut can be approximately solved using eigen-computations. However, it is a challenge to incorporate prior information in this approach. In this paper, we express prior knowledge by linear constraints on the solution, with the goal of minimizing the normalized cut criterion with respect to these constraints. We develop a fast and effective algorithm that is guaranteed to converge. Convincing results are achieved on image segmentation tasks, where the prior knowledge is given as the grouping information of features. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1109/CVPR.2009.5206561 | CVPR |
Keywords | Field | DocType |
eigencomputations,fast normalized cut,spectral relaxations,image segmentation,computational complexity,graph theory,eigenvalues and eigenfunctions,np-hard problems,linear constraints,algorithm design and analysis,np hard problems,optimization,biomedical imaging,labeling,data mining,kernel,convergence,clustering algorithms,constraint optimization | Graph theory,Convergence (routing),Mathematical optimization,Algorithm design,Normalization (statistics),Computer science,Image segmentation,Maximum cut,Computational complexity theory | Conference |
Volume | Issue | ISSN |
2009 | 1 | 1063-6919 |
ISBN | Citations | PageRank |
978-1-4244-3992-8 | 37 | 1.32 |
References | Authors | |
11 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Linli Xu | 1 | 790 | 42.51 |
Wenye Li | 2 | 100 | 11.55 |
Dale Schuurmans | 3 | 2760 | 317.49 |