In this paper, we propose a two-stage approach for color image segmentation, which is inspired by minimal surface smoothing. Indeed, the first stage is to find a smooth solution to a convex variational model related to minimal surface smoothing. The classical primal-dual algorithm can be applied to efficiently solve the minimization problem. Once the smoothed image
is obtained, in the second stage, the segmentation is done by thresholding. Here, instead of using the classical K-means to find the thresholds, we propose a hill-climbing procedure to find the peaks on the histogram of
, which can be used to determine the required thresholds. The benefit of such approach is that it is more stable and can find the number of segments automatically. Finally, the experiment results illustrate that the proposed algorithm is very robust to noise and exhibits superior performance for color image segmentation.