We introduce a model to evaluate the segmentation quality of a color image. The model parameters were learned from a set of examples. To this aim, we first segmented a set of images using a traditional graph-cut algorithm, for different values of the scale parameter. A human observer classified these images into three classes: under-, well- and over-segmented. We used such classification to learn the parameters of the segmentation quality model, that was then employed to automatically and adaptively optimize the scale parameter of the graph-cut segmentation algorithm. Experimental results show an improved segmentation quality for our algorithm based on the proposed segmentation quality model, which can be easily applied to a wide class of segmentation algorithms.