In an approach for sampling a distribution of segmentations of an image, the segmentations are based on a level set function. For each sample of the distribution, the sampling includes the following, for each of multiple iterations: randomly selecting a set of locations of the level set function, determining a domain of allowed perturbations of the level set function at the selected set of locations, and randomly accepting a perturbation of the level set function according to a criterion corresponding to a biased distribution over the domain of allowed perturbations of the level set function, wherein the bias is selected to increase a probability of accepting the perturbation. The sampling also includes determining the sample of the distribution of segmentations according to a perturbed level set function determined in a final iteration of the multiple iterations for the sample.