Given a video sequence decompressed from a compressed video sequence associated with motion vector information for each image frame, this short note presents an efficient predictive watershed-based video segmentation algorithm using motion vectors. The proposed algorithm has much computation-saving merit since the next frame can inherit the segmented results of the current frame according to the motion vector information of the next frame. Experimental results demonstrate that with little perceptual segmentation degradation, the proposed algorithm has better execution-time performance when compared to the previous Chien et al.’s video segmentation algorithm whose input video sequence is assumed to have no motion vector information. Further, the alleviation of the over-segmentation problem existed in both algorithms is investigated.