Fast Normalized Cut with Linear Constraints
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.
Cite
Text
Xu et al. "Fast Normalized Cut with Linear Constraints." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2009. doi:10.1109/CVPR.2009.5206561Markdown
[Xu et al. "Fast Normalized Cut with Linear Constraints." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2009.](https://mlanthology.org/cvpr/2009/xu2009cvpr-fast/) doi:10.1109/CVPR.2009.5206561BibTeX
@inproceedings{xu2009cvpr-fast,
title = {{Fast Normalized Cut with Linear Constraints}},
author = {Xu, Linli and Li, Wenye and Schuurmans, Dale},
booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
year = {2009},
pages = {2866-2873},
doi = {10.1109/CVPR.2009.5206561},
url = {https://mlanthology.org/cvpr/2009/xu2009cvpr-fast/}
}