Analyzing skin cancer automatically by using image processing techniques has attracted enormous attention recently. The first step in analyzing skin cancer is usually isolating suspicious lesions from normal skin. In this paper, a novel segmentation framework capable of segmenting large clinical lesion images is presented. This algorithm proceeds in a coarse-to-fine approach. Firstly, it builds a down-sampled version of the original image after lower-pass filtering. Then it partitions the down-sampled image by normalized cut. Furthermore, this segmentation result can be adapted to the original image by using a histogram based Bayesian classifier. We also discuss the robustness of this segmentation algorithm with respect to the size of the down-sampled images. Experimental study on synthetic and real images illustrate that this algorithm gives promising results for segmenting clinical lesion images.