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
``shrinking bias''. 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.