Reconstruction of missing data point from sparse samples during graphics processing using cubic spline polynomials

• US 9,589,367 B2
• Filed: 06/18/2015
• Issued: 03/07/2017
• Est. Priority Date: 06/27/2014
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Golas, Abhinav, Ramani, Karthik, Brothers, John W.
• Primary Examiner(s): Sajous, Wesner
• Application Number:
  US14/743,746
• Publication Number:
  US 20150379692A1
• Time in Patent Office: 628 Days
• US Class Current: 1/1
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 2200/12 involving antialiasing
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/20192 Edge enhancement; Edge preservation
• CPC Class Codes: G06T 5/00 Image enhancement or restoration
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: G06T 7/337 involving reference images or patches
• CPC Class Codes: G09G 5/363 Graphics controllers

Abstract

A graphics system includes a reconstruction unit that utilizes higher order polynomials, such as cubic splines, to reconstruct missing pixel data. The computational work to perform interpolation with higher order polynomials, such as cubic splines, is reduced by pre-calculating weights for each sparse sample pattern. The pre-calculated weights may be stored as stencils and used during runtime to perform interpolation.

Claims

1. A method of performing graphics processing, comprising:

selecting at least one tile of a graphics image to be sampled;

selecting a sample pattern to sample the at least one tile of a graphics image;

rendering pixel data of the sampled at least one tile; and

performing, at runtime, reconstruction of missing pixel data in the sampled at least one tile using cubic spline interpolation;

wherein the cubic spline interpolation is performed using pre-computed weights to compute pixel color values as a weighted sum of known pixel color values including accumulating products of the pre-computed weights and color values with a multiplier/adder and normalizing the accumulated product.

5. The method of claim 1, wherein the sample pattern is selected from a set of pre-defined sample patterns having the same sample rate and each pre-defined sample pattern has an associated set of pre-computed weights to perform cubic spline interpolation for the selected sample pattern.

6. The method of claim 1, wherein the selecting at least one tile of the graphics image to be sampled comprises analyzing a scene and determining required sample rates in different tiles of the image and selecting tiles requiring a lower sampling rate to be sparsely sampled.

2. A method of performing graphics processing, comprising:

selecting at least one tile of a graphics image to be sampled;

selecting a sample pattern to sample the at least one tile of a graphics image;

rendering pixel data of the sampled at least one tile; and

performing, at runtime in a graphics processing unit, reconstruction of missing pixel data in the sampled at least one tile using cubic spline interpolation;

wherein the cubic spline interpolation is performed using pre-computed weights to compute pixel color values as a weighted sum of known pixel color values and the pre-computed weights of the sample pattern are stored in a set of pre-computed stencils.

3. The method of claim 2, wherein the set of pre-computed stencils includes all of the pre-computed weights for each location of missing pixel data in the sample pattern.

4. The method of claim 2, further comprising providing an index into the pre-computed stencil.

7. A method of performing graphics processing, comprising:

providing a set of pre-computed weights to perform cubic spline interpolation of missing pixel data;

selecting at least one tile of a graphics image to be sampled;

selecting the sample pattern to sample the at least one tile of the graphics image;

rendering pixel data of the sampled at least one tile; and

performing, at runtime in a graphics processing unit, reconstruction of missing pixel data in the sampled at least one tile using the pre-computed weights to perform cubic spline interpolation of pixel color values as a weighted sum of known pixel color values;

wherein the performing comprises accumulating products of the pre-computed weights and samples color values with a multiplier/adder and normalizing the accumulated product.

8. A method of performing graphics processing, comprising:

providing a set of pre-computed weights to perform cubic spline interpolation of missing pixel data;

selecting at least one tile of a graphics image to be sampled;

selecting the sample pattern to sample the at least one tile of the graphics image;

rendering pixel data of the sampled at least one tile; and

performing, at runtime in a graphics processing unit, reconstruction of missing pixel data in the sampled at least one tile using the pre-computed weights to perform cubic spline interpolation of pixel color values as a weighted sum of known pixel color values;

wherein the pre-computed weights are stored in a set of pre-computed stencils including all of the pre-computed weights for each pixel location of the sample pattern.

9. The method of claim 8, further comprising providing an index into the set of pre-computed stencils.

10. A method of performing graphics processing, comprising:

providing a set of pre-computed weights to perform cubic spline interpolation of missing pixel data;

selecting at least one tile of a graphics image to be sampled;

selecting the sample pattern to sample the at least one tile of the graphics image;

rendering pixel data of the sampled at least one tile; and

performing, at runtime in a graphics processing unit, reconstruction of missing pixel data in the sampled at least one tile using the pre-computed weights to perform cubic spline interpolation of pixel color values as a weighted sum of known pixel color values;

wherein the sample pattern is selected from a set of pre-defined sample patterns having the same sample rate and further comprising selecting a pre-computed stencil having pre-computed weights stored for the selected sample pattern.

11. A graphics system including a graphics pipeline and a multiplier/adder, comprising:

a memory storing a set of pre-computed weights to compute pixel color values as a weighted sum of known pixel color values using cubic spline interpolation for reconstruction; and

a reconstruction stage to access the pre-computed weights from the memory and perform, at runtime, reconstruction of missing pixel data in sampled tiles using cubic spline interpolation,

wherein the reconstruction stage accumulates products of the pre-computed weights and samples color values with the multiplier/adder and normalizing the accumulated product.

12. The graphics system of claim 11, wherein the reconstruction is performed on a tile basis.

13. The graphics system of claim 12, wherein the pre-computed weights are stored as a set of stencils.

14. The graphics system of claim 13, wherein the set of pre-computed stencils includes all of the pre-computed weights for each pixel location of the sample pattern.

15. The graphics system of claim 11, wherein the graphics system includes a set of sampling patterns having a reduced average sampling rate and each respective sampling pattern has a corresponding set of pre-computed stencils including the pre-computed weights to perform cubic spline interpolation.

16. A method of performing graphics processing, comprising:

providing a set of pre-computed weights to perform higher order polynomial interpolation of missing pixel data, wherein the order of the polynomial is at least three;

selecting at least one tile of a graphics image to be sampled;

selecting the sample pattern to sample the at least one tile of the graphics image;

rendering pixel data of the sampled at least one tile; and

performing, at runtime in a graphics processing unit, reconstruction of missing pixel data in the sampled at least one tile using the pre-computed weights to perform higher order polynomial interpolation of pixel color values as a weighted sum of known pixel color values.

17. A method of performing graphics processing, comprising:

selecting at least one tile of a graphics image to be sampled;

selecting a sample pattern to sample the at least one tile of a graphics image;

rendering, in a graphics processing unit, pixel data of the sampled at least one tile; and

performing, at runtime in the graphics processing unit, reconstruction of missing pixel data in the sampled at least one tile using cubic spline interpolation;

wherein the selecting at least one tile of the graphics image to be sampled comprises analyzing a scene and determining required sample rates in different tiles of the image and selecting tiles requiring a lower sampling rate to be sparsely sampled.

18. A method of performing graphics processing, comprising:

selecting at least one tile of a graphics image to be sampled;

selecting a sample pattern to sample the at least one tile of a graphics image;

rendering, in a graphics processing unit, pixel data of the sampled at least one tile; and

performing, at runtime in the graphics processing unit, reconstruction of missing pixel data in the sampled at least one tile using cubic spline interpolation;

wherein the sample pattern is selected from a set of pre-defined sample patterns having the same sample rate and each pre-defined sample pattern has an associated set of pre-computed weights to perform cubic spline interpolation for the selected sample pattern.

19. A method of performing graphics processing, comprising:

selecting at least one portion of a frame to be sampled at a lower sampling rate than the sampling rate of other portions of the frame;

selecting a sample pattern to sample at least one tile of a graphics image in the at least one portion of the frame;

rendering, in a graphics processing unit, pixel data of the sampled at least one tile; and

performing, at runtime in the graphics processing unit, reconstruction of missing pixel data in the sampled at least one tile using cubic spline interpolation.