In this paper, an image representation method based on arbitrary shaped regions, and execute the motion estimation of the image sequence according to this representation of the image is proposed. In order to avoid over-segmentation, the initial frame in the image sequence is smoothed while edge of the image is preserved. The smoothing algorithm is the modification version of Alvarez's method. Then, the smoothed frame is segmented by the watershed method. According to the label image, the image is stored in the form of region adjacency graph. To further solve the problem of the over-segmentation, the merging criterions based on average region intensity and edge strength and region size are given. The affine transformation is used as motion model for each region, and the nonlinear least square method is used for the optimization. Compared with the method based on pixel, the result shows that the motion vectors produced by our algorithm are more consistent and the PSNR is improved.