1. A method for performing a motion-based, multi-stage segmentation of a video frame, the method comprising: identifying motion boundaries in a plurality of sub-blocks of the video frame in a first segmentation stage, the motion boundaries identified by computing an occlusion-insensitive localized motion cost and minimizing a MAP-MRF energy based on the localized motion cost; and refining the motion boundaries in a second segmentation stage by adding a color cost to the localized motion cost.