A method, for use in a segmentation-based coding system, for detecting motion vectors between a current frame and a previous frame of digital video signal comprises the steps of (a) generating segmentation data for each of the segmented regions, the segmentation data including contour information representing the shape and location for each segmented region and texture information representing a mean gray level of all pixels contained in each segmented region, (b) generating candidate segmentation data for each of the candidate regions, (c) producing a minimum-sized predetermined geometric pattern for encompassing a segmented region, (d) producing a minimum-sized predetermined geometric pattern for encompassing each of the candidate regions, (e) calculating an error value between the segmented region and each of the candidate regions, (f) selecting a candidate region yielding a smallest error value as a search region, (g) detecting one or more motion vectors between the segmented region and the search region; and (h) repeating said steps (c) to (g) for all the segmented regions.