Connectivity similarity based transductive learning for interactive image segmentation

We propose a novel graph-based transductive learning approach for interactive image segmentation. Here the term ldquotransductiverdquo indicates a process that iteratively propagates information from user-labeled regions to unlabeled image pixels. For the application of interactive image segmentation, transductive approach has several advantages compared with traditional color probabilistic model based approach. However, previous transductive approaches for image segmentation usually utilize an 8-connected neighborhood system, which has low efficacy when transferring local information to remote pixels. The main contribution of this paper is to estimate pairwise pixel similarity based on a novel path-based metric (i.e. connectivity similarity), rather than local comparison with 8-connected neighbors. We further theoretically prove the computing complexity is on a polynomial order and provide convergence guarantee for the extra local smoothing operation that is introduced to further refine the initial results. Especially, the proposed method shows promising performance in the multi-label case. Various experiments are presented to illustrate its effectiveness.