A method for efficient low power motion estimation of a digital video image is provided in which processing requirements are reduced based upon the content being processed. The method performs motion estimation of a current video image using a search window of a previous video image. The method may include forming mean pyramids of a reference macroblock and the search area and a full search at a lowest resolution. A number of candidate motion vectors (CMVs) propagated to lower levels may be dependent on a quantized average deviation estimate (QADE) of a current macroblock and the maximum distortion band obtained during training for that QADE value at that particular level. Training over a sequence may be triggered at the beginning of every sequence. This training technique may be used to determine the value of the maximum distortion band for all QADEs of the macroblocks occurring over the training frames.