<p>Segmenting an image into multiple meaningful regions is a fundamental but challenging problem in computer vision. Dominant sets clustering, which is a graph-partitioning algorithm, was recently shown to be effective in image segmentation and many other applications. This paper focuses on the problem of efficiently computing a faithful affinity matrix for dominant sets based segmentation. We first construct a graph over spatially adjacent superpixels integrating region and boundary cues. By applying path-based similarity to this graph, we are able to capture the inherent manifolds in unsupervised and nonparametric manner. These affinities are then applied to dominant sets algorithm to yield a segmentation. Our algorithm provides high-quality segmentations by considering local grouping cues and full-range connections. Moreover, since the initial graph is sparse the path-based similarity can be efficiently computed. The experimental results on multiple datasets demonstrate the effectiveness of our segmentation algorithm in combining region and boundary cues, achieving significantly better performance compared with state-of-the-art methods.</p>