Sub-pixel interpolation and its application in motion compensated encoding of a video signal

• US 9,118,927 B2
• Filed: 06/13/2007
• Issued: 08/25/2015
• Est. Priority Date: 06/13/2007
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Goel, Anurag
• Primary Examiner(s): PYZOCHA, MICHAEL J
• Application Number:
  US11/762,091
• Publication Number:
  US 20080310509A1
• Time in Patent Office: 2,995 Days
• Field of Search: 375/240.17
• 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/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 comprising:

receiving a plurality of source integer pixels and a plurality of reconstructed pixels;

computing an integer motion vector based on said plurality of course integer pixels and said plurality of reconstructed pixels;

determining a search range about an integer pixel position pointed to by said integer motion vector;

computing non-diagonal pixels by applying a first filter on a set of said plurality of course integer pixels with said search range, wherein said first filter has a predetermined complexity;

computing one or more diagonal sub-pixels by applying a second filter on said non-diagonal sub-pixels, wherein said second filter has a complexity less than said predetermined complexity, wherein said one or more diagonal sub-pixels are diagonally half distance from pairs of plurality of integer pixels;

selecting a vector sub-pixel location based on a cost associated with sub-pixel motion vector encoding of each sub-pixel;

determining if said sub-pixel at said selected vector sub-pixel location was computed by a filter having a complexity less than said predetermined complexity;

re-computing one or more sub-pixels including at said selected sub-pixel location using said first filter having said predetermined complexity, if said sub-pixel at said selected sub-pixel location was previously computed by a filter having a complexity less than said predetermined complexity;

re-selecting a vector sub-pixel location based on a cost associated with sub-pixel motion vector encoding for each sub-pixel using any re-computed sub-pixel, if said sub-pixel at said selected sub-pixel location was previously computed by a filter having a complexity less than said predetermined complexity;

iteratively repeating said re-computing one or more sub-pixels and said re-selecting said vector sub-pixel location until a sub-pixel at said re-selected vector sub-pixel location was computed by said first filter having said predetermined complexity; and

computing a motion vector for a final selected vector sub-pixel location, wherein said final selected vector sub-pixel location was computed by said first filter having said predetermined complexity.

2. The method of claim 1, wherein said non-diagonal sub-pixels comprise H1 and H2, and a diagonal sub-pixel (H3) is computed to equal (H1+H2+1)/2.

3. The method of claim 2, wherein both H1 and H2 are located halt pixel distance away on either side of said diagonal sub-pixel.

4. The method of claim 1, wherein said one or more diagonal sub-pixels are further computed by applying said second filter on a pair of said plurality of source integer pixels.

5. The method of claim 1, further comprising generating a plurality of quarter pixels from said one or more diagonal sub-pixels, said non-diagonal sub-pixels and said plurality of source integer pixels.

6. A non-transitory computer readable medium carrying one or more sequences of instructions for causing a receiver 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 received system causes said one or more processors to perform the actions of:

receiving a plurality of source integer pixels and a plurality of reconstructed pixels;

computing an integer motion vector based on said plurality of course integer pixels and said plurality of reconstructed pixels;

determining a search range about an integer pixel position pointed to by said integer motion vector;

computing non-diagonal pixels by applying a first filter on a set of said plurality of course integer pixels with said search range, wherein said first filter has a predetermined complexity;

computing one or more diagonal sub-pixels by applying a second filter on said non-diagonal sub-pixels, wherein said second filter has a complexity less than said predetermined complexity, wherein said one or more diagonal sub-pixels are diagonally half distance from pairs of plurality of integer pixels;

selecting a vector sub-pixel location based on a cost associated with sub-pixel motion vector encoding of each sub-pixel;

determining if said sub-pixel at said selected vector sub-pixel location was computed by a filter having a complexity less than said predetermined complexity;

re-computing one or more sub-pixels including at said selected sub-pixel location using said first filter having said predetermined complexity, if said sub-pixel at said selected sub-pixel location was previously computed by a filter having a complexity less than said predetermined complexity;

re-selecting a vector sub-pixel location based on a cost associated with sub-pixel motion vector encoding for each sub-pixel using any re-computed sub-pixel, if said sub-pixel at said selected sub-pixel location was previously computed by a filter having a complexity less than said predetermined complexity;

iteratively repeating said re-computing one or more sub-pixels and said re-selecting said vector sub-pixel location until a sub-pixel at said re-selected vector sub-pixel location was computed by said first filter having said predetermined complexity; and

computing a motion vector for a final selected vector sub-pixel location, wherein said final selected vector sub-pixel location was computed by said first filter having said predetermined complexity.

7. The non-transitory computer readable medium of claim 6, wherein said non-diagonal sub-pixels include a first half pixel (H1) and a second half pixel (H2), and a first diagonal sub-pixel (H3) is computed to equal (H1+H2+1)/2.

8. The non-transitory computer readable medium of claim 6, wherein said reselecting excludes the costs associated with sub-pixels computed using said second filter.

9. The non-transitory computer readable medium of claim 6, further comprising:

generating a motion compensated block from said plurality of reconstructed pixels at positions corresponding to said motion vector.