Electronic Thesis and Dissertation Repository


Master of Science


Computer Science


Boykov, Yuri Y.


Image segmentation is a fundamental problem in Computer Vision which involves segmenting an image into two or more segments. These segments usually correspond to objects of interest in the image, i.e. liver, kidney’s etc. The classic approach to this problem segments the image into mutually exclusive segments. However, this approach is not well-suited when segmenting overlapping objects, e.g. cells, or when segmenting a single object into multiple parts that are not necessarily mutually exclusive. Moreover, we show that optimization methods for multi-part object segmentation with different priors/constraints may better avoid local minima in case of a relaxation allowing parts to overlap.

We propose a novel segmentation model, i.e. Segmentation with Overlapping Labels (SOL), which allows for the objects’ multiple parts to overlap. This aids in overcoming the aforementioned issue of local minima with standard optimization approaches. We prove that SOL is an NP-hard problem, as well as introduce a novel move-making optimization framework to find an approximate solution to SOL. Our qualitative and quantitative results show that our proposed method outperforms state-of-the-art algorithms for multi-part segmentation.