This paper presents GeoS, a new algorithm for the eﬃcient segmentation of n-dimensional image and video data. The segmentation problem is cast as approximate energy minimization in a conditional random ﬁeld. A new, parallel ﬁltering operator built upon eﬃcient geodesic distance computation is used to propose a set of spatially smooth, contrast-sensitive segmentation hypotheses. An economical search algorithm ﬁnds the solution with minimum energy within a sensible and highly restricted subset of all possible labellings. Advantages include: i) computational eﬃciency with high segmentation accuracy; ii) the ability to estimate an approximation to the posterior over segmentations; iii) the ability to handle generally complex energy models. Comparison with max-ﬂowindicates upto60 times greater computational eﬃciency as well as greater memory eﬃciency. GeoS is validated quantitatively and qualitatively by thorough comparative experiments on existing and novel ground-truth data. Numerous results on interactive and automatic segmentation of photographs, video and volumetric medical image data are presented.