This paper describes an extension to the graph cut interactive image segmentation algorithm based on a novel approach to addressing the well known small cut problem. The approach uses a generative contrast model to weight interaction potentials. The model attempts to capture the expected changes in color between adjacent pixels in the unlabeled area of the image using the adjacent pixels in the user interactions as training data. We compare our approach to the standard graph cuts algorithm and show that the contrast model allows a user to achieve a more accurate segmentation with fewer interactions. We additionally introduce a variant of the approach based on superpixels that further enhances performance but reduces computational complexity to ensure instant feedback for optimal user experience.