Method, apparatus, and computer program product for providing motion estimator for video encoding

Patent metadata

Field	Value
Publication number	US-10820012-B2
Application number	US-201615370127-A
Country	US
Kind code	B2
Filing date	Dec 6, 2016
Priority date	Sep 27, 2006
Publication date	Oct 27, 2020
Grant date	Oct 27, 2020

Abstract

An apparatus for providing motion estimation for video encoding includes a selection element and a processing element. The selection element is configured to select a subset including less than all of candidate pixel locations from among a plurality of candidate pixel locations used for motion vector determination based on a relationship between a best candidate pixel location of a first level of accuracy and a best candidate pixel location of a second level of accuracy. The processing element is configured to process an input video sequence to determine a motion vector at the first level of accuracy, to refine the motion vector at the second level of accuracy, and to determine the motion vector at a third level of accuracy using only the subset of candidate pixel locations.

First claim

What is claimed is:

1. A method of performing motion estimation for video encoding, comprising:
processing an input video sequence to determine a motion vector between a first video frame and a reference frame, comprising determining a best candidate pixel location in the reference frame at a first level of accuracy;
refining the motion vector at a second level of accuracy higher than the first level of accuracy, comprising determining a best candidate pixel location at the second level of accuracy among a plurality of pixel locations including the best candidate pixel location at the first level of accuracy;
selecting, with a selection element, a subset of candidate pixel locations proximate to the better of the best candidate pixel location at the first level of accuracy and the best candidate pixel location at the second level of accuracy other than the best candidate pixel location at the first level of accuracy, and between:
the best candidate pixel location at the first level of accuracy, and
the best candidate pixel location at the second level of accuracy other than the best candidate pixel location at the first level of accuracy; and

determining the motion vector at a third level of accuracy using only the subset of candidate pixel locations.

2. The method of claim 1 , wherein the determining of a best candidate pixel location comprises determining a block in the reference frame most closely matching the original block based on minimization of a distortion measure.

3. The method of claim 1 , wherein the determining of a best candidate pixel location comprises determining a block in the reference frame most closely matching the original block based on minimization of a sum of absolute difference.

4. The method of claim 1 , wherein the determining of a best candidate pixel location comprises determining a block in the reference frame most closely matching the original block based on minimization of a difference between the block in the reference frame and the original block.

5. The method of claim 1 , wherein a candidate block has a size of less than or equal to 16×16 pixels.

6. The method of claim 1 , wherein the first level of accuracy is integer pixel level of accuracy, the second level of accuracy is half pixel level of accuracy, and the third level of accuracy is quarter pixel level of accuracy.

7. The method of claim 1 , wherein the selected subset of candidate pixel locations numbers fewer than all of the candidate pixel locations.

8. An encoder for encoding video frames based on a motion vector describing the motion from a location of an original block in an original frame to a reference block location in a reference frame, comprising a motion estimation element configured to:
determine a best candidate block location at a first level of accuracy corresponding to a candidate block in the reference frame most closely matching the original block at the first level of accuracy;
determine, from among a plurality of block locations including the best candidate block location at the first level of accuracy, a best candidate block location at a second level of accuracy, higher than the first level of accuracy, corresponding to a candidate block in the reference frame most closely matching the original block at the second level of accuracy;
select candidate block locations, at a third level of accuracy, that are proximate to the better of the best candidate pixel location at the first level of accuracy and the best candidate block location at the second level of accuracy other than the best candidate block location at the first level of accuracy, and between:
the best candidate block location at the first level of accuracy, and
the best candidate block location at the second level of accuracy other than the best candidate block location at the first level of accuracy; and

determine, from among the selected candidate block locations at the third level of accuracy, a reference block location corresponding to a candidate block in the reference frame most closely matching the original block.

9. The encoder of claim 8 , wherein the motion estimation element is configured to determine a block in the reference frame most closely matching the original block based on minimization of a distortion measure.

10. The encoder of claim 8 , wherein the motion estimation element is configured to determine a block in the reference frame most closely matching the original block based on minimization of a sum of absolute difference.

11. The encoder of claim 8 , wherein the motion estimation element is configured to determine a block in the reference frame most closely matching the original block based on minimization of a difference between the block in the reference frame and the original block.

12. The encoder of claim 8 , wherein a candidate block has a size of less than or equal to 16×16 pixels.

13. The encoder of claim 8 , wherein the first level of accuracy is integer pixel level of accuracy, the second level of accuracy is half pixel level of accuracy, and the third level of accuracy is quarter pixel level of accuracy.

14. The encoder of claim 8 , wherein the motion estimation element is configured to select fewer than all of the candidate block locations at the third level of accuracy.

Assignees

• Conversant Wireless Licensing Sarl

Inventors

• Ugur Kemal
• Lainema Jani
• Hallapuro Antti

Classifications

• G06T7/238

  using non-full search, e.g. three-step search · CPC title

• H04N19/53 Primary

  Multi-resolution motion estimation; Hierarchical motion estimation · CPC title

• H04N19/533

  Motion estimation using multistep search, e.g. two-dimensional [2D]-log search or one-at-a-time search [OTS] · CPC title

• H04N19/523

  with sub-pixel accuracy · CPC title

• H04N19/176

  the region being a block, e.g. a macroblock · CPC title