System, method, and software for estimation of motion vectors

A method of estimating a motion vector for a target block of pixels in a target frame relative to a reference frame, the method comprising:

• determining a first plurality of partial distortion measures, each based only on a first row or column of pixels of the target block and a corresponding first row or column in a respective one of a first plurality of blocks in the reference frame, the first plurality of blocks including a first minimum block associated with a minimum of the first plurality of distortion measures;
• determining a second plurality of partial distortion measures, each based only on a second row or column of pixels of the target block and a corresponding second row in a respective one of a second plurality of blocks in the reference frame, with the second plurality of blocks including a second minimum block associated with a minimum of the second plurality of distortion measures;
• determining a first distortion measure based at least on pixels of the target block and the first minimum block that are outside the first row or column of the target block and the first minimum block;
• determining a second distortion measure based at least on pixels of the target block and the second minimum block that are outside the second row or column of the target block;
• and
• determining the motion vector based on the target block and the one of the first and second minimum blocks associated with the lesser of the first and second distortion measures.

An image encoder including a motion estimator for estimating a motion vector for a target block of pixels in a target frame relative to a reference frame, the motion estimator comprising:

• means for defining a search area of the reference frame.
• means for defining a plurality of K search sets S1 . . . SK within the search area, each search set Si, for i=1 to K, identifying pixels from an i-th column of the search area, with each pixel in each search set associated with a block of pixels;
• means for determining a set of K candidate blocks B1 . . . BK, with each block B1, for i=1 to K, corresponding to one block of pixels associated with a pixel of search set Si and minimizing a first distortion function relative to the target block, the first distortion function based only on a set of two or more collinear pixels from the target block and a set of two or more collinear pixels from block Bi;
• means for determining which one of the K candidate blocks B1 . . . BK minimizes a second distortion function relative to the target block;
• and
• means for estimating the motion vector based on the target block and the one of the K candidate blocks that minimizes the second distortion function.

A machine-readable medium for facilitating estimation of a motion vector for a target block of pixels in a target frame relative to a reference frame, the medium comprising instructions for:

• defining a search area of the reference frame;
• defining a plurality of K search sets S1 . . . SK within the search area, each search set Si, for i=1 to K, identifying pixels from an i-th column of the search area, with each pixel in each search set Si associated with a block of pixels;
• determining a set of K candidate blocks B1 . . . BK, with each block Bi, for i=1 to K, corresponding to one block of pixels associated with a pixel of search set Si and minimizing a first distortion function relative to the target block, the first distortion function based only on a set of two or more collinear pixels from the target block and a set of two or more collinear pixels from block Bi;
• determining which one of the K candidate blocks B1 . . . BK minimizes a second distortion function relative to the target block;
• and
• estimating the motion vector based on the target block and the one of the K candidate blocks that minimizes the second distortion function.

A system comprising:

• at least one processor;
• an image decoder coupled to the processor;
• and
• an image encoder coupled to the processor, with the image encoder including a motion estimator for estimating a motion vector for a target block of pixels in a target frame relative to a reference frame, the motion estimator comprising:
• means for defining a search area of the reference frame.
• means for defining a plurality of K search sets S1 . . . SK within the search area, each search set Si, for i=1 to K, identifying pixels from every i-th column of the search area, with each pixel in each search set Si identifying a block of pixels;
• means for determining a set of K candidate blocks B1 . . . BK, with each block Bi, for i=1 to K, corresponding to one block of pixels identified by a pixel of search set Si and minimizing a first distortion function relative to the target block, the first distortion function based only on a set of two or more collinear pixels from the target block and a set of two or more collinear pixels from block Bi;
• means for determining which one of the K candidate blocks B1 . . . BK minimizes a second distortion function relative to the target block;
• and
• means for estimating the motion vector based on the target block and the one of the K candidate blocks that minimizes the second distortion function.

An image encoder including a motion estimator for estimating a motion vector for a target block of pixels in a target frame relative to a reference frame, the motion estimator comprising:

• a first minimization module that determines a set of K candidate blocks B1 . . . BK, with each block Bi, for i=1 to K, minimizing a respective first distortion function relative to the target block, the respective distortion function based only on a set of two or more collinear pixels from the i-th row or column of the target block and a set of two or more collinear pixels from the i-th row or column of block Bi;
• a second minimization module that determines which of the K candidate blocks B1 . . . BK minimizes a second distortion function based at least on pixels outside the i-th row or column of the target block;
• and
• an estimation module that estimates the motion vector based on the target block and one of the K candidate blocks that minimizes the second distortion function.

A method of estimating a motion vector for a target block of pixels in a target frame relative to a reference frame, with the target block having two or more lines of pixels, the method comprising:

• identifying a set of two or more candidate blocks in the reference frame, with each candidate block minimizing a first distortion function based on only one respective line of pixels of the target block and a corresponding line of pixels in the candidate block, the one respective line being different for each candidate block;
• determining which one or more of the candidate blocks minimizes a second distortion function based on pixels from more than two lines of the target block;
• and
• determining the motion vector based on one of the candidate blocks that minimizes the second distortion function.