COMPUTATIONALLY EFFICIENT MOTION ESTIMATION

• US 20160191946A1
• Filed: 12/31/2014
• Published: 06/30/2016
• Est. Priority Date: 12/31/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Li, Binlong, Zhou, You, Lin, Chih-Lung, Lee, Ming-Chieh
• Granted Patent: US 10,462,480 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04N 19/117 Filters, e.g. for pre-processing or post-processing sub-band filter banks H04N19/635
• CPC Class Codes: H04N 19/137 Motion inside a coding unit, e.g. average field, frame or block difference
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/523 with sub-pixel accuracy
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/82 involving filtering within a prediction loop

Abstract

The detailed description presents innovations in performing motion estimation during digital video media encoding. In one example embodiment, motion estimation is performed using a lower-complexity sub-pixel interpolation filter configured to compute sub-pixel values for two or more candidate prediction regions at a sub-pixel offset, the two or more candidate prediction regions being located in one or more reference frames. For a selected one of the candidate prediction regions at the sub-pixel offset, motion compensation is performed using a higher-complexity sub-pixel interpolation filter.

Claims

1. A video encoder, comprising:

one or more computing devices programmed or configured to perform a video encoding method, the video encoding method comprising;

adaptively selecting one sub-pixel interpolation scheme from among multiple available sub-pixel interpolation schemes for use during a motion estimation process for a block of video media data in a video frame; and

performing the motion estimation process using the selected sub-pixel interpolation scheme, the motion estimation process comprising (a) computing multiple candidate prediction regions from one or more reference frames, the candidate prediction regions predicting motion of a block of video media data in a video frame being encoded, at least some of the candidate prediction regions being computed using the adaptively selected sub-pixel interpolation scheme, and (b) selecting one of the candidate prediction regions for the block of video media data from among the multiple candidate prediction regions.

2. The video encoder of claim 1, wherein the adaptively selected sub-pixel interpolation scheme uses a first sub-pixel interpolation filter,

wherein the selected one of the candidate prediction regions is at a sub-pixel offset, and

wherein the video encoding method further comprises performing motion compensation for the selected one of the candidate prediction regions, the motion compensation comprising computing the selected one of the candidate prediction regions using a second sub-pixel interpolation filer, the second sub-pixel interpolation filter having higher computational complexity than the first sub-pixel interpolation filter.

3. The video encoder of claim 1, wherein the multiple available sub-pixel interpolation schemes include a first sub-pixel interpolation scheme and a second sub-pixel interpolation scheme, and

wherein the first sub-pixel interpolation scheme uses a sub-pixel interpolation filter having a higher numbers of taps than any sub-pixel interpolation filter used in the second sub-pixel interpolation scheme.

4. The video encoder of claim 1, wherein the multiple available sub-pixel interpolation schemes include a first sub-pixel interpolation scheme and a second sub-pixel interpolation scheme, and

wherein the first sub-pixel interpolation scheme pre-interpolates a higher number of sub-pixel values for a frame than the second sub-pixel interpolation scheme.

5. The video encoder of claim 1, wherein the multiple available sub-pixel interpolation schemes include a first sub-pixel interpolation scheme and a second sub-pixel interpolation scheme, and

wherein the second sub-pixel interpolation scheme omits pre-interpolation of any sub-pixel value for the frame.

6. The video encoder of claim 1, wherein the adaptively selecting comprises:

computing a metric indicating a predicted degree of object movement in the video frame being encoded;

comparing the metric to a threshold; and

selecting one of the multiple available sub-pixel interpolation schemes based at least in part on the comparison.

7. The video encoder of claim 1, wherein the metric indicating a predicted degree of object movement in the video frame being encoded is a skip block ratio indicating a number of blocks in the adjacent previous frame that were encoded in a skip mode relative to a total number of blocks in the adjacent previous frame.

8. A video encoder, comprising:

one or more computing devices programmed or configured to perform a video encoding method, the video encoding method including a motion estimation process comprising;

computing first candidate sub-pixel prediction regions for blocks of video media data in one or more regions of a video frame using a first sub-pixel interpolation scheme; and

computing second candidate prediction regions for blocks of video media data that are in the video frame but outside of the regions using a second sub-pixel interpolation scheme,

the first sub-pixel interpolation scheme having a higher computational complexity than the second sub-pixel interpolation scheme.

9. The video encoder of claim 8, wherein the first sub-pixel interpolation scheme uses a sub-pixel interpolation filter having higher numbers of taps than a sub-pixel interpolation filter used in the second sub-pixel interpolation scheme.

10. The video encoder of claim 8, wherein the first sub-pixel interpolation scheme pre-interpolates a higher number of sub-pixel values for a frame than the second sub-pixel interpolation scheme.

11. The video encoder of claim 8, wherein the second sub-pixel interpolation scheme uses no more than two taps in computing sub-pixel values.

12. The video encoder of claim 8, wherein the one or more regions of the video frame to which the first sub-pixel interpolation scheme is applied comprise one or more persons in the video frame, and wherein the video encoder is employed as part of a video conferencing system.

13. The video encoder of claim 8, wherein the motion estimation process further comprises identifying the one or more regions of the video frame to which the first sub-pixel interpolation scheme is applied by iteratively computing a skip block ratio for blocks of video data along multiple directional lines across a previous video frame and trimming those blocks of video data from the region whose skip block ratio exceeds a threshold.

14. The video encoder of claim 8, wherein the motion estimation process further comprises identifying the one or more regions of the video frame to which the first sub-pixel interpolation scheme is applied by grouping together portions of a previous video frame that have motion vectors that exceed a motion threshold and that neighbor one another by a distance threshold.

15. The video encoder of claim 14, wherein the motion estimation process further comprises evaluating the grouped together portions of the previous video frame to remove groups that do not meet a size threshold for treatment as a region to which the first sub-pixel interpolation scheme is applied during motion estimation.

16. A method, comprising:

during encoding of a frame of digital video media by a video encoder;

performing motion estimation using a first sub-pixel interpolation filter configured to compute sub-pixel values for two or more candidate prediction regions at a sub-pixel offset, the two or more candidate prediction regions being located in one or more reference frames; and

for a selected one of the candidate prediction regions at the sub-pixel offset, performing motion compensation using a second sub-pixel interpolation filter,

the first sub-pixel interpolation filter used during motion estimation having a lower computational complexity than the second sub-pixel interpolation filter used during motion compensation.

17. The method of claim 16, wherein the first sub-pixel interpolation filter is adaptively selected for use during motion estimation from among multiple available interpolation filters, the adaptively selecting being based on a metric indicating a degree of object movement in the frame of the digital video media.

18. The method of claim 16, wherein the performing motion estimation further comprises omitting any pre-interpolation of sub-pixel values in the one or more reference frames.

19. The method of claim 16, wherein the performing motion estimation further comprises using two-tap sub-pixel interpolation filters for motion estimation and using seven-tap or eight-tap sub-pixel interpolation filters for motion compensation.

20. The method of claim 16, wherein the performing motion estimation further comprises performing pre-interpolation in one or more reference frames for a first set of sub-pixel values but not performing pre-interpolation in the one or more reference frames for a second set of sub-pixel values, the first and second sets of sub-pixel values being sub-pixel values that are available and supported for motion estimation, the first set of sub-pixel values having a lower resolution than the second set of sub-pixel values.