In this paper the issue of image segmentation within the framework of nonlinear multiscale watersheds in combination with graph theory based techniques is addressed. First, a graph is created which decomposes the image in scale and space using the concept of multiscale watersheds. In the subsequent step the obtained graph is partitioned using recursive graph cuts in a coarse to fine manner. In this way, we are able to combine scale and feature measures in a flexible way: the feature-set that is used to measure the dissimilarities may change as we progress in scale. We employ the Earth Mover?s Distance on a featureset that combines color, scale and contrast features to measure the dissimilarity between the nodes in the graph. Experimental results demonstrate the efficiency of the proposed method for natural scene images.