With rapid development of mobile technology and digital image processing, mobile applications involving image segmentation are emerging in many fields. In this paper, we propose an effective and easy-to-use algorithm for interactive image segmentation (IIS) on mobile phones through integrating a Bayesian Classifier into the Random Walk optimizer. We exploit the user input information to train a Bayesian classifier for determining the posterior probabilities of the image pixels belonging to foreground or background. These probabilities are used to calculate the edge weights and label the seed pixels in the random walk optimizer for image segmentation. The resultant method is called BCRW for short. In this way we improve the segmentation accuracy and alleviate the user burden. The user is only required to draw a rectangle bounding the interested object to get the high-quality segmentation result. We further design an efficient mobile phone version of our BCRW algorithm. The effectiveness and efficiency of the proposed algorithm is confirmed by the comparative experimental results with the Grab Cut and the PIBS algorithms, as well as the experimental results on a mobile phone.