Most practical image segmentation algorithms optimize some mathematical similarity criterion derived from several low-level image features. One possible way of combining different types of features, e.g. color- and texture features on different scales and/or different orientations, is to simply stack all the individual measurements into one high-dimensional feature vector. Due to the nature of such stacked vectors, however, only very few components (e.g. those which are defined on a suitable scale) will carry information that is relevant for the actual segmentation task. We present a novel approach to combining segmentation and feature selection that is capable of overcoming this relevance determination problem. It implements a wrapper strategy for feature selection, in the sense that the features are directly selected by optimizing thediscriminative power of the used partitioning algorithm. On the technical side, we present an efficient optimization algorithm with guaranteed local convergence property. All free model parameters of this method are selected by a resampling-based stability analysis. Experiments for both toy examples and real-world images demonstrate that the built-in feature selection mechanism leads to stable and meaningful partitions of the images.