Segmentation is a prevalent research area in medical imaging analysis. Nevertheless, estimation of the uncertainty margins of the extracted anatomical structure or pathology boundaries is seldom considered. This paper studies the concept of segmentation uncertainty of clinical images, acknowledging its great importance to patient follow up, user-interaction guidance, and morphology-based population studies. We propose a novel approach for model-dependent uncertainty estimation for image segmentation. The key contribution is an alternating, iterative algorithm for the generation of an image-specific uncertainty map. This is accomplished by defining a consistency-based measure and applying it to segmentation samples to estimate the uncertainty margins as well as the midline segmentation. We utilize the stochastic active contour framework as our segmentation generator, yet any sampling method can be applied. The method is validated on synthetic data for well-defined objects blurred with known Gaussian kernels. Further assessment of the method is provided by an application of the proposed consistency-based algorithm to ensembles of stochastic segmentations of brain hemorrhage in CT scans.