Methods for motion estimation with adaptive motion accuracy

An adaptive motion accuracy search method for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said method comprising the steps of:

• (a) searching a first set of motion vector candidates in a grid centered on V1 using a first criteria to find a best motion vector V2 using a first filter to do a first interpolation;
• (b) searching a second set of motion vector candidates in a grid centered on V2 using a second criteria to find a best motion vector V3 using a second filter to do a second interpolation;
• and
• (c) searching a third set of motion vector candidates in a grid centered on V3 using a third criteria to find said best motion vector of said macroblock using a third filter to do a third interpolation;
• (d) wherein at least one of said first criteria, said second criteria, and said third criteria is a rate-distortion criteria.

An adaptive motion accuracy search method for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said method comprising the steps of:

• (a) searching at a first motion accuracy for a first best motion vector of said macroblock;
• (b) encoding said first best motion vector and said first motion accuracy;
• (c) searching for at least one second best motion vector of said macroblock at an at least one second motion accuracy;
• (d) encoding said at least one second best motion vector and said at least one second motion accuracy;
• and
• (e) selecting the best motion vector of said first and at least one second best motion vectors using rate-distortion criteria.

An adaptive motion accuracy search method for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said method comprising the steps of:

• (a) searching at a motion accuracy for a best motion vector of said macroblock using rate-distortion criteria;
• (b) encoding said motion accuracy using a code from a VLC table that is interpreted differently at different coding units according to the associated motion vector accuracy;
• and
• (c) encoding said best motion vector in the respective accuracy space.

A system for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said system comprising:

• (a) a first encoder for searching a first set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V1 using a first criteria to find a best motion vector V2;
• (b) a second encoder for searching a second set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V2 using a second criteria to find a best motion vector V3;
• and (c) a third encoder for searching a third set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V3 using a third criteria to find said best motion vector of said macroblock;
• (d) wherein at least one of said first criteria, said second criteria, and said third criteria is a rate-distortion criteria.

A fast-search adaptive motion accuracy search method for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said method comprising the steps of:

• (a) searching a first set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V1 to find a best motion vector V2;
• (b) searching a second set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V2 to find a best motion vector V3;
• (c) searching a third set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V3 to find said best motion vector of said macroblock, and
• (d) using V2 as the motion vector for the macroblock if V2 has the smallest rate-distortion cost and skipping step (c).

A method of performing, at a video encoder, motion-compensated video encoding of an input image having respective frames each of which is decomposed into blocks, comprising:

• searching, block by block, for a motion vector that represents an amount of movement from a corresponding position of a reference frame in an objective current block for each of the blocks decomposed from a frame of the input image,
• compensating a motion using the motion vector, the motion vector having fractional accuracy expressed by 1/N pel (where N is an integer ≧2),
• encoding the accuracy of the motion vector and the motion vector, wherein encoding the accuracy is performed separately from encoding the motion vector,
• said encoding the motion vector step encoding the motion vector for each block on a block-by-block basis,
• said searching and said compensating steps are performed by selecting a filter from a plurality of interpolation filters according to the accuracy, wherein the accuracy is set on a frame basis such that the same accuracy is used for every motion vector in a frame but a different accuracy can be used for a different frame.

A method of decoding, at a video decoder, motion-compensated coded data obtained by encoding an image frame block-by-block, comprising:

• decoding a motion vector that represents an amount of movement from a corresponding position of a reference frame in an objective current block for each of the blocks included in the coded data obtained,
• decoding an accuracy of the motion vector, the motion vector having fractional accuracy expressed by 1/N pel (where N is an integer ≧2),
• compensating a motion using the accuracy and the motion vector,
• said decoding the accuracy step being performed separately from said decoding the motion vector step,
• said decoding the motion vector step being performed on a block-by-block basis,
• said motion compensation step being performed by selecting a filter from a plurality of interpolation filters according to the accuracy,
• wherein the accuracy is set on a frame basis such that the same accuracy is used for every motion vector in a frame but a different accuracy can be used for a different frame.