Normalized Cuts Revisited: A Reformulation for Segmentation with Linear Grouping Constraints
(2011) In Journal of Mathematical Imaging and Vision 39(1). p.45-61- Abstract
- Indisputably Normalized Cuts is one of the most popular segmentation algorithms in pattern recognition and computer vision. It has been applied to a wide range of segmentation tasks with great success. A number of extensions to this approach have also been proposed, including ones that can deal with multiple classes or that can incorporate a priori information in the form of grouping constraints. However, what is common for all these methods is that they are noticeably limited in the type of constraints that can be incorporated and can only address segmentation problems on a very specific form. In this paper, we present a reformulation of Normalized Cut segmentation that in a unified way can handle linear equality constraints for an... (More)
- Indisputably Normalized Cuts is one of the most popular segmentation algorithms in pattern recognition and computer vision. It has been applied to a wide range of segmentation tasks with great success. A number of extensions to this approach have also been proposed, including ones that can deal with multiple classes or that can incorporate a priori information in the form of grouping constraints. However, what is common for all these methods is that they are noticeably limited in the type of constraints that can be incorporated and can only address segmentation problems on a very specific form. In this paper, we present a reformulation of Normalized Cut segmentation that in a unified way can handle linear equality constraints for an arbitrary number of classes. This is done by restating the problem and showing how linear constraints can be enforced exactly in the optimization scheme through duality. This allows us to add group priors, for example, that certain pixels should belong to a given class. In addition, it provides a principled way to perform multi-class segmentation for tasks like interactive segmentation. The method has been tested on real data showing good performance and improvements compared to standard normalized cuts. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1687606
- author
- Eriksson, Anders P LU ; Olsson, Carl LU and Kahl, Fredrik LU
- organization
- publishing date
- 2011
- type
- Contribution to journal
- publication status
- published
- subject
- in
- Journal of Mathematical Imaging and Vision
- volume
- 39
- issue
- 1
- pages
- 45 - 61
- publisher
- Springer
- external identifiers
-
- wos:000285974800004
- scopus:79952002461
- ISSN
- 0924-9907
- DOI
- 10.1007/s10851-010-0223-5
- language
- English
- LU publication?
- yes
- id
- e427cc05-0af6-400e-84c2-b73b87a86453 (old id 1687606)
- date added to LUP
- 2016-04-01 10:00:38
- date last changed
- 2022-01-25 18:54:53
@article{e427cc05-0af6-400e-84c2-b73b87a86453,
abstract = {{Indisputably Normalized Cuts is one of the most popular segmentation algorithms in pattern recognition and computer vision. It has been applied to a wide range of segmentation tasks with great success. A number of extensions to this approach have also been proposed, including ones that can deal with multiple classes or that can incorporate a priori information in the form of grouping constraints. However, what is common for all these methods is that they are noticeably limited in the type of constraints that can be incorporated and can only address segmentation problems on a very specific form. In this paper, we present a reformulation of Normalized Cut segmentation that in a unified way can handle linear equality constraints for an arbitrary number of classes. This is done by restating the problem and showing how linear constraints can be enforced exactly in the optimization scheme through duality. This allows us to add group priors, for example, that certain pixels should belong to a given class. In addition, it provides a principled way to perform multi-class segmentation for tasks like interactive segmentation. The method has been tested on real data showing good performance and improvements compared to standard normalized cuts.}},
author = {{Eriksson, Anders P and Olsson, Carl and Kahl, Fredrik}},
issn = {{0924-9907}},
language = {{eng}},
number = {{1}},
pages = {{45--61}},
publisher = {{Springer}},
series = {{Journal of Mathematical Imaging and Vision}},
title = {{Normalized Cuts Revisited: A Reformulation for Segmentation with Linear Grouping Constraints}},
url = {{http://dx.doi.org/10.1007/s10851-010-0223-5}},
doi = {{10.1007/s10851-010-0223-5}},
volume = {{39}},
year = {{2011}},
}