Sub-pixel Interpolation and its Application in Motion Compensated Encoding of a Video Signal

• US 20080310509A1
• Filed: 06/13/2007
• Published: 12/18/2008
• Est. Priority Date: 06/13/2007
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Goel, Anurag
• Granted Patent: US 9,118,927 B2
• Time in Patent Office: Days
• US Class Current: 375/240.16
• 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/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/182 the unit being a pixel
• CPC Class Codes: H04N 19/523 with sub-pixel accuracy
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/82 involving filtering within a prediction loop

Abstract

Reducing computational complexity when generating sub-pixel values for sub-pixel motion estimation from integer pixels. In an embodiment, half pixels in vertical and horizontal directions are computed by a applying a filter of first complexity on integer pixels, and a half pixel in diagonal direction is computed using a filter of lower complexity as compared to the filter of first complexity. Quarter (and other lower resolution pixels) pixels may also be generated using the half pixel in the diagonal direction. Thus, overall computational complexity is reduced in generating sub-pixels for sub-pixel motion estimation.

Claims

1. A method of generating a plurality of sub-pixels from a plurality of integer pixels, said method comprising:

receiving said plurality of integer pixels;

computing a first set of half pixels by applying a first filter with a first complexity on said plurality of integer pixels; and

computing a diagonal pixel by applying a second filter with a second complexity, wherein said second complexity is less than said first complexity, wherein said diagonal pixel is diagonally half distance from a pair of said plurality of integer pixels.

2. The method of claim 1, wherein said second filter is applied to compute a non-diagonal half pixel from said plurality of integer pixels.

3. The method of claim 2, wherein said first set of half pixels comprise H1 and H2, and said diagonal pixel (H3) is computed to equal (H1+H2+1)/2.

4. The method of claim 3, wherein both H1 and H2 are located half pixel distance away on either side of said diagonal pixel.

5. The method of claim 2, wherein said diagonal pixel is computed by applying said second filter on a pair of said plurality of integer pixels.

6. The method of claim 1, further comprising generating a plurality of quarter pixels from said diagonal pixel, said first set of half pixels and said plurality of integer pixels.

7. An article of manufacture to process a sequence of video frames, said article of manufacture comprising:

a motion estimation block to receive a plurality of integer pixels representing a reconstructed frame and computing a first set of half pixels by applying a first filter with a first complexity on said plurality of integer pixels, said motion estimation block then computing a diagonal pixel by applying a second filter with a second complexity, wherein said second complexity is less than said first complexity, wherein said diagonal pixel is diagonally half distance from a pair of said plurality of integer pixels, said motion estimation block computing a motion vector by examining said plurality of integer pixels, said diagonal pixel and said first set of half pixels;

a motion compensation block receiving said motion vector and generating a second plurality of diagonal pixels using a third filter, wherein said third filter has higher complexity compared to said second filter, said motion compensation block forming a predicted block from said reconstructed frame; and

an error block generating a residue block as a difference of a source block presently being encoded and said predicted block,

wherein said residue block is transmitted to a receiving system.

8. The article of manufacture of claim 7, wherein said motion estimation block computes a corresponding cost associated with each of a plurality of positions for said motion vector, wherein said motion estimation block adds a bias to the corresponding cost when at least one pixel computed using said second filter is used, wherein said motion vector is selected as with a position having the least cost.

9. The article of manufacture of claim 8, wherein the cost for each position vector is computed according to:

E=D+Lambda1*R1+Lambda2*R2+Lambda3*R3+Bias

wherein D represents aggregate difference between the pixels of said source block and the interpolated block generated in said motion estimation block, R1 represents bits needed to code said difference, R2 represents bits needed to code the motion vectors for all blocks, R3 represents the size of the source block, and Lambda1, Lambda2 and Lambda3 respectively represent weighting factor for R1, R2 and R3 and Bias represents the correction bias added to cost computed using low complexity filters.

10. The article of manufacture of claim 9, wherein said bias is relatively more if the complexity of sub-pixel interpolation filter is relatively less and vice versa.

11. A computer readable medium carrying one or more sequences of instructions for causing a system to process a sequence of video frames, wherein execution of said one or more sequences of instructions by one or more processors contained in said receiver system causes said one or more processors to perform the actions of:

receiving a plurality of integer pixels;

computing a first set of half pixels by applying a first filter with a first complexity on said plurality of integer pixels; and

computing a diagonal pixel by applying a second filter with a second complexity, wherein said second complexity is less than said first complexity, wherein said diagonal pixel is diagonally half distance from a pair of said plurality of integer pixels.

12. The computer readable medium of claim 11, wherein said second filter is applied to compute a non-diagonal half pixel from said plurality of integer pixels.

13. The computer readable medium of claim 12, wherein said first set of half pixels comprise H1 and H2, and said diagonal pixel (H3) is computed to equal (H1+H2+1)/2.

14. The computer readable medium of claim 11, wherein said receiving and said computing are performed in a motion estimation phase while encoding said sequence of video frames, wherein said plurality of integer pixels are comprised in a reconstructed frame, further comprising:

determining a motion vector for a source block based on said plurality of integer pixels and said diagonal pixel.

15. The computer readable medium of claim 14, wherein a first set of sub-pixels including said diagonal pixel are computed using said second filter, said first set of sub-pixels being included in a search set, wherein said search set includes the integer pixels and sub-pixels surrounding an integer pixel, wherein said determining comprises:

computing a cost of encoding corresponding to each pixel contained in said search set;

selecting the position of the pixel having the lowest cost as one end of an intermediate vector;

if the pixel is not contained in said first set of sub-pixels, providing said intermediate vector as said motion vector;

if the pixel is contained in said first set of sub-pixels;

recomputing the pixel using said first filter and also the revised cost for the recomputed pixel;

reselecting the position of the pixel having the lowest cost as one of end of said motion vector.

16. The computer readable medium of claim 15, wherein said reselecting excludes the costs associated with pixels computed based on pixels computed using said second filter.

17. The computer readable medium of claim 14, further comprising:

generating a motion compensated block from said reconstructed frame at positions corresponding to said motion vector.