Motion vectors for encoding a predicted frame relative to a reference frame are determined from a phase correlation of corresponding regions of the predicted frame and reference frame. Peaks in the phase correlation are identified, and the location of the peaks are used as candidate motion vectors. From this limited set of candidate motion vectors, the best motion vectors for predicting blocks within each region can be readily identified.