Learning full pairwise affinities for spectral segmentation

Segmenting a single image into multiple coherent groups remains a challenging task in the field of computer vision. Particularly, spectral segmentation which uses the global information embedded in the spectrum of a given image's affinity matrix is a major trend in image segmentation. This paper focuses on the problem of efficiently learning a full range of pairwise affinities gained by integrating local grouping cues for spectral segmentation. We first construct a sparse multilayer graph whose nodes are both the pixels and the oversegmented regions obtained by an unsupervised segmentation algorithm. By applying the semi-supervised learning 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 paper, two types of spectral segmentation algorithms are introduced: $(K)$-way segmentation and hierarchical segmentation. 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 eigendecomposition 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.