Motion estimation and block matching pattern

A motion estimator for performing a block matching search in a video coder, the motion estimator comprising:

• a subtractor for computing differences between pixel values in a source block of a source frame and a target block of a target frame;
• a sum of differences accumulator in communication with the subtractor for accumulating a sum of the differences from the subtractor;
• an adder in communication with the SAD accumulator for adding a sum of the differences with a measure of motion vector overhead for the block to compute a combined measure of motion vector and error signal data for the target block, wherein a quantization factor weights the measure of motion vector overhead;
• and
• a comparator for comparing the combined measure of motion vector and error signal data with a previously computed combined measure of motion vector and error signal data for another target block to find a target block in the target frame with a minimum combined measure of motion vector and error signal data.

A method for performing motion estimation in video coding applications, the method comprising:

• for a source block in a source frame, searching for a matching block among target blocks in a target frame, including:
• computing a difference between pixel values at pixel locations in the source block from the source frame and pixel values at corresponding pixel locations in target blocks in the target frame;
• and
• computing a measure of combined motion data and error signal data for the target blocks, wherein a quantization factor weights the motion data;
• selecting a target block from among the target blocks with a minimum combined measure of motion and error signal data for the target blocks;
• and
• using motion data approximating motion between the pixels of the source block and the selected target block to encode the source block.

A computer readable medium having stored thereon instructions for performing a method of block matching for motion estimation in a video sequence, the method comprising:

• for a source block of a source frame, searching for a matching target block from among plural target blocks of a target frame, wherein for each searched target block the searching includes:
• computing a motion vector cost for encoding the searched target block;
• weighting the motion vector cost by a quantization factor;
• and
• computing a match criterion for the searched target block based at least in part upon the weighted motion vector cost;
• and
• selecting the matching target block based upon the respective match criteria for the searched target blocks.

A method for performing motion estimation for a source block in a source fame of a sequence of video frames, wherein the motion estimation includes a search for a matching block among target blocks in a target frame of the sequence, and wherein the search starts from a starting location in the target frame, the method comprising:

• computing a combined coding overhead measure for a target block at the so location based upon plural factors, wherein the plural factors include motion data and error signal data for the target block;
• initializing a current best coding overhead measure based upon the combined coding overhead measure computed for the target block at the starting location, wherein the current best coding overhead measure is for a current best match target block among the target blocks in the target frame;
• for each of one or more subsequent target blocks in the target frame,
• computing a simplified coding overhead measure for the subsequent target block based upon less than all of the plural factors, thereby simplifying the computing the simplified coding overhead measure;
• and
• terminating the search if a comparison of the current best coding overhead measure with the simplified coding overhead measure for the subsequent target block indicates the subsequent target block is necessarily a worse match than the current best match target block.