A motion-based, multi-stage segmentation of a video frame is provided. A first segmentation stage identifies motion boundaries in a plurality of sub-blocks of the video frame. The motion boundaries are identified by computing an occlusion-insensitive localized motion cost and minimizing a MAP-MRF energy based on the localized motion cost. A second segmentation stage refines the motion boundaries by adding a color cost to the localized motion cost in the MAP-MRF energy.