---
_id: '3195'
abstract:
- lang: eng
text: 'Graph cut is a popular technique for interactive image segmentation. However,
it has certain shortcomings. In particular, graph cut has problems with segmenting
thin elongated objects due to the ldquoshrinking biasrdquo. To overcome this problem,
we propose to impose an additional connectivity prior, which is a very natural
assumption about objects. We formulate several versions of the connectivity constraint
and show that the corresponding optimization problems are all NP-hard. For some
of these versions we propose two optimization algorithms: (i) a practical heuristic
technique which we call DijkstraGC, and (ii) a slow method based on problem decomposition
which provides a lower bound on the problem. We use the second technique to verify
that for some practical examples DijkstraGC is able to find the global minimum.'
author:
- first_name: Sara
full_name: Vicente, Sara
last_name: Vicente
- first_name: Vladimir
full_name: Vladimir Kolmogorov
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
citation:
ama: 'Vicente S, Kolmogorov V, Rother C. Graph cut based image segmentation with
connectivity priors. In: IEEE; 2008. doi:10.1109/CVPR.2008.4587440'
apa: 'Vicente, S., Kolmogorov, V., & Rother, C. (2008). Graph cut based image
segmentation with connectivity priors. Presented at the CVPR: Computer Vision
and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2008.4587440'
chicago: Vicente, Sara, Vladimir Kolmogorov, and Carsten Rother. “Graph Cut Based
Image Segmentation with Connectivity Priors.” IEEE, 2008. https://doi.org/10.1109/CVPR.2008.4587440.
ieee: 'S. Vicente, V. Kolmogorov, and C. Rother, “Graph cut based image segmentation
with connectivity priors,” presented at the CVPR: Computer Vision and Pattern
Recognition, 2008.'
ista: 'Vicente S, Kolmogorov V, Rother C. 2008. Graph cut based image segmentation
with connectivity priors. CVPR: Computer Vision and Pattern Recognition.'
mla: Vicente, Sara, et al. Graph Cut Based Image Segmentation with Connectivity
Priors. IEEE, 2008, doi:10.1109/CVPR.2008.4587440.
short: S. Vicente, V. Kolmogorov, C. Rother, in:, IEEE, 2008.
conference:
name: 'CVPR: Computer Vision and Pattern Recognition'
date_created: 2018-12-11T12:01:57Z
date_published: 2008-08-05T00:00:00Z
date_updated: 2021-01-12T07:41:43Z
day: '05'
doi: 10.1109/CVPR.2008.4587440
extern: 1
main_file_link:
- open_access: '0'
url: http://research.microsoft.com/pubs/80485/CVPR08-ConnectedGC.pdf
month: '08'
publication_status: published
publisher: IEEE
publist_id: '3487'
quality_controlled: 0
status: public
title: Graph cut based image segmentation with connectivity priors
type: conference
year: '2008'
...