Segmentation is the problem of partitioning an image into a small number of regions, each of which is uniform or homogeneous in some sense. Although traditional approaches produce an optimal (or near-optimal) segmentation with respect to the chosen models, the problem is generally considered under-constrained. Consequently, the segmentation may not contain the best homogeneous regions needed by some higher-level process (i.e. a recognition system cannot exert complex model-based influences directly on the selection of an optimal segmentation). We develop a method for probabilistically maintaining sets of alternative homogeneous regions, and segmentations. Depending on the image sise and complexity, and on the application, a probability distribution can be constructed over the entire image, or a distribution over partial segmentations can be formed. We develop an efficient representation structure, and a probabilistic mechanism for applying Bayesian, model-based evidence to guide the construction of the representation and influence the resulting posterior distribution over the space of alternatives. Our formalism is applied to range images using a piecewise-planar model with additive Gaussian noise.