We present a new approach to the segmentation problem by optimizing a criterion which estimates the quality of a segmentation. Our method offers a general framework for solving a large class of segmentation problem. We use a graph-based description of a partition of an image and a merging strategy based on the optimal use of a sequence of criteria. An efficient data structure enables our implementation to have a low algorithmic complexity. We show how we adapt this method to segment 2-d natural images including color images and how we use results for solving the stereo matching problem.