A new algorithm, named Connected Oriented Image Foresting Transform (COIFT), is proposed, which provides global optimum solutions according to a graph-cut measure, subject to high-level boundary constraints. COIFT incorporates the connectivity constraint in the Oriented Image Foresting Transform (OIFT), ensuring the generation of connected objects, and can also handle simultaneously the boundary polarity. While the connectivity constraint usually leads to NP-hard problems in other frameworks, such as the min-cut/max-flow algorithm, COIFT conserves the low complexity of the OIFT algorithm. Experiments show that COIFT can improve the segmentation of thin and elongated objects, for the same amount of user interaction.