To perform motion estimation for a video frame block to be encoded, a difference measure is determined for each of a plurality of reference frame block positions at a first, coarser resolution. The determined difference measures are then used estimate difference measures for reference frame blocks at positions at a second resolution that is finer than the first resolution. The estimated second, finer position resolution difference measures are then used to select a set of reference frame block positions for which to determine “full” difference measures. The determined “full” difference measures for each of the selected reference frame block positions are then used to select the reference frame block position to use when encoding the frame block and a motion vector corresponding to that reference frame block position is associated with and encoded for the frame block being encoded.