This paper describes efficient video coding schemes based on arbitrary shaped-region motion estimation technique. The effect of the object based motion estimation on the video compression quality is introduced in this work. The approach is based on new arbitrary shaped-region motion estimation technique (ASRA). In the motion estimation process, the frames are segmented into moving regions and non-moving regions using four steps predictive procedure. To reduce the required operations for motion estimation, the searching technique will be performed for the moving regions only. Moreover, to ensure the robustness against the additive noise as well as reducing the computation time, the ASRA algorithm will be performed in the first level of the wavelet domain. It does not need to send any segmentation information to the decoder. The proposed video coding methods are applied on videos containing a variety of scenarios such as multiple objects undergoing occlusion, splitting, merging, entering and exiting, as well as a changing background. For all videos, the proposed approach displays higher Peak Signal to Noise Ratio (PSNR) compared to MPEG-4 methods, and provides comparable or better compression than most of the recent video coding techniques.