Fast semi-supervised image segmentation by novelty selection

The goal of semi-supervised image segmentation is to obtain the segmentation from a partially labeled image. By utilizing the image manifold structure in labeled and unlabeled pixels, semi-supervised methods propagate the user labeling to the unlabeled data, thus minimizing the need for user labeling. Several semi-supervised learning methods have been proposed in the literature. Although results have been promising, these methods are very computationally intensive. In this paper, we propose novelty selection as a pre-processing step to reduce the number of data points while retaining the fundamental structure of the data. Since the computational complexity is a power of the number of points, it is possible to significantly reduce the overall computation requirements. Results in several images show that the computation time is greatly reduced without sacrifice in segmentation accuracy.