In the video encoding process, the motion estimation usually consumes a large part of the encoder computations. This paper presents motion estimation techniques, targeted mainly for MPEG-4 video encoding but also applicable for other video codecs e.g. H.264. A high quality adaptive algorithm with adjustable complexity, based on partially blind prediction for motion estimation, is proposed.The computational complexity of motion estimation is reduced with minor loss in the video quality. In the paper, the quality metrics PSNR, BD PSNR and PEVQ are used, and the possible trade off between complexity and visual quality is studied.