--- _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' ...