Patent ID: 6876703

Claim:
A method for obtaining an estimated motion vector for use in block-based video encoding, the method comprising: refining a predicted motion vector for a current block to obtain an estimated motion vector in a sequence comprising a plurality of steps; and, before each of a plurality of the steps in the sequence, computing a similarity value between the block and another block indicated by the current estimated motion vector, comparing the similarity value to a threshold, and not performing subsequent steps in the sequence if the comparison indicates that the current estimated motion vector provides a match between the current block and the another block which is better than a match corresponding to the threshold wherein; refining the predicted motion vector comprises performing one or more frame motion estimation steps and, before the frame motion estimation steps, computing a first similarity value between the current block and a block identified by the predicted motion vector, comparing the first similarity value to a first threshold, and using the predicted motion vector as the estimated motion vector if the comparison indicates that the block identified by the predicted motion vector provides a better match than the first threshold; the frame motion estimation steps comprise a low resolution frame motion estimation step and a full pel frame motion estimation step and the method comprises computing a second similarity value between the current block and a block identified by the estimated motion vector of the low resolution frame motion estimation step, comparing the second similarity value to a second threshold, and not performing the full pel frame motion estimation step if the comparison indicates that the block identified by estimated motion vector of the low resolution frame motion estimation step provides a better match than the second threshold; and, the frame motion estimation steps comprise a half pel frame motion estimation step and the method comprises computing a third similarity value between the current block and a block identified by the estimated motion vector of the full pel frame motion estimation step, comparing the third similarity value to a third threshold, and not performing the half pel frame motion estimation step if the comparison indicates that the block identified by estimated motion vector of the full pel frame motion estimation step provides a better match than the third threshold.