Image segmentation is often considered a deterministic process with a single ground truth. Nevertheless, in practice, and in particular, when medical imaging analysis is considered, the extraction of regions of interest (ROIs) is ill-posed and the concept of most probable' segmentation is model-dependent. In this paper, a measure for segmentation uncertainty in the form of segmentation error margins is introduced. This measure provides a goodness quantity and allows a fully informed’ comparison between extracted boundaries of related ROIs as well as more meaningful statistical analysis. The tool we present is based on a novel technique for segmentation sampling in the Fourier domain and Markov Chain Monte Carlo (MCMC). The method was applied to cortical and sub-cortical structure segmentation in MRI. Since the accuracy of segmentation error margins cannot be validated, we use receiver operating characteristic (ROC) curves to support the proposed method. Precision and recall scores with respect to expert annotation suggest this method as a promising tool for a variety of medical imaging applications including user-interactive segmentation, patient follow-up, and cross-sectional analysis.