Image Segmentation: Region and Boundary Cue Integration Using Semi-Supervised Learning

Abstract

In this dissertation, we propose a new segmentation framework to efficiently integrate region and boundary cues using semi-supervised learning (SSL). Following this concept, we present two generative models for interactive segmentation and one spectral segmentation for unsupervised segmentation. In this dissertation, we propose a new segmentation framework to efficiently integrate region and boundary cues using semi-supervised learning (SSL). Following this concept, we present two generative models for interactive segmentation and one spectral segmentation for unsupervised segmentation. We first consider the problem of multi-label, interactive segmentation when a set of scribbles labeling the pixels is given. In contrast to most existing algorithms which deal with the inter-label discrimination, we address the problem of finding the generative model for each label. Particularly, in the generative image segmentation, two likelihood models based on SSL are introduced. In Chapter 2, the likelihood that an unlabeled pixel has a specific label is defined as the relevance score of the unlabeled pixel with respect to the seeded pixels in the scribbles with that label. Here, this relevance score corresponds to the steady-state probability that a particle starting from the seeded pixels stays at the unlabeled pixel until convergence, computed by Random Walks with Restart (RWR), one of the SSL techniques. Since the steady-state probability considers the whole relationship between the unlabeled pixel and the seeded pixels, our RWR-based segmentation algorithm produces very good results under two difficult problems: the weak boundary problem and the texture problem. To improve the performance under the weak boundary problem, data-driven RWR (dRWR) that incorporates the edgeness of each pixel into its restarting probability is designed. The consistency of relevance scores in the edge-bounded areas can be more emphasized by dRWR. Additionally, in order to reduce the dependency on the seed quantity and placement, we devise higher-order RWR (hRWR) that computes the steady-state probabilities in a bilayer graph whose nodes consists of the pixels and the over-segmented regions, generated by a unsupervised image segmentation algorithm such as Mean Shift. We can achieve the higher-order constraint that the pixels in the regions tend to have similar relevance scores by hRWR. By combining the ideas of dRWR and hRWR, we finally complete global RWR (gRWR). Experimental results with synthetic and natural images demonstrate the relevance and accuracy of our RWR-based segmentation algorithm. In Chapter 3, we propose a novel likelihood model to strengthen the higher-order constraint in the segmentation algorithm. Although we can conceptually add the higher-order constraint in the RWR-based segmentation algorithm, it is difficult to prove the higher-order effect theoretically. And the higher-order effect is actually limited for segmentation of natural images. Therefore, to learn the likelihoods from labeled and unlabeled pixels, we design a new higher-order formulation additionally imposing the soft label consistency constraint whereby the pixels in the over-segmented regions tend to have the same label. In contrast with previous works which focus on the parametric model of the higher-order cliques for adding this soft constraint, we address a nonparametric learning technique to recursively estimate the region likelihoods as higher-order cues from the resulting likelihoods of pixels included in the regions. Therefore, the main idea of our algorithm is to design several quadratic cost functions of pixel and region likelihoods, that are supplementary to each other, in a proposed multilayer graph and to estimate them simultaneously by a simple optimization technique. In this manner, we consider long-range connections between the regions that facilitate propagation of local grouping cues across larger image areas. Also, as abundant region candidates extracted by multiple oversegmentations are used, boundary cue can be implicitly imposed. The experiments on challenging data sets show that integration of higher-order cues in the multilayer graph quantitatively and qualitatively improves the segmentation results with detailed boundaries and reduces sensitivity with respect to seed quantity and placement. We then consider a new unsupervised segmentation algorithm without user interaction. Spectral segmentation which uses the global information embedded in the spectrum of a given images affinity matrix is a major trend in image segmentation. Its overall quality mainly depends on how the affinity matrix is designed. Here, a novel affinity model based on SSL is introduced. In Chapter 4, we address the problem of efficiently learning a full range of pairwise affinities gained by integrating region and boundary cues for spectral segmentation. We first construct a sparse multilayer graph whose nodes are both the pixels and the over-segmented regions. By applying the SSL strategy to this graph, the intra and interlayer affinities between all pairs of nodes can be estimated without iteration. These pairwise affinities are then applied into the spectral segmentation algorithms. In this work, two types of spectral segmentation algorithms are introduced: K-way segmentation and hierarchical segmentation. The former is to cluster all pixels and regions simultaneously into the K visually coherent groups across all layers in a single multilayer framework of Normalized Cuts. The latter is to generate a hierarchy of regions from contour information, obtained from spectral analysis of our affinity matrix, using a sequence of two transformations: Oriented Watershed Transform and Ultrametric Contour Map. Our algorithms provide high-quality segmentations which preserve object details by directly incorporating the full-range connections. Moreover, since our full affinity matrix is defined by the inverse of a sparse matrix, its eigen-decomposition can be efficiently computed. The experimental results on the BSDS and MSRC image databases demonstrate the superiority of our segmentation algorithms in terms of relevance and accuracy compared with existing popular methods.