Mobile vision systems have attracted a great deal of recent attention. Image segmentation plays an important role in mobile systems as it does in traditional computer vision systems. Interactive image segmentation provides a better quality over a wide range of images than fully automatic segmentation. However, performing interactive image segmentation on camera phones brings new challenges due to their smaller screens, restricted input devices and relatively limited computational power compared to desktops and laptops. We propose three intelligent approaches to address these challenges and make the interactive image segmentation system more robust, efficient and easier to use for camera phones. The first approach includes a novel automatic boundary refinement procedure that requires little user interaction and makes the object cutout process more robust and convenient. It first merges over-segmented regions according to the maximal similarity rule, using a few user-marked strokes as input, and then detects possible erroneous low-contrast object boundaries by analyzing image content. The boundary regions are automatically refined using both local and global information. The second method begins with an initial over-segmentation using the mean shift algorithm followed by discriminative clustering and local neighborhood classification. Its speed is further improved by using an image pyramid and a boundary refinement procedure that performs bilateral filtering of the probabilities that pixels belong to the foreground. The third approach involves the quantitative definition of segmentation difficulty metrics in both automatic and interactive settings. These metrics are later utilized by an active-learning-based interactive image segmentation algorithm that can suggest additional pixels for users to mark.