Methods and apparatus for rendering images using 3D warping techniques

• US 6,756,993 B2
• Filed: 01/17/2002
• Issued: 06/29/2004
• Est. Priority Date: 01/17/2001
• Status: Expired due to Fees

• Current Assignee: University of South Carolina
• Original Assignee: University of North Carolina At Chapel Hill (University of North Carolina System)
• Inventors: Eyles, John, Popescu, Voicu, Lastra, Anselmo
• Primary Examiner(s): Bella, Matthew C.
• Assistant Examiner(s): Caschera, Antonio A
• Application Number:
  US10/052,189
• Publication Number:
  US 20020180748A1
• Time in Patent Office: 894 Days
• Field of Search: 382/300, 345/609, 345/646, 345/647
• US Class Current: 345/646
• CPC Class Codes: G06T 15/205 Image-based rendering

Abstract

Methods and apparatus for rendering images are presented. The method includes the step of segmenting at least one reference image in a reference image space into a plurality of tiles, each tile defined by a corresponding set of image samples. The connectivity of each of the samples is determined based on the relative curvature of a surface of the corresponding tile at the sample coordinates. Color and depth information between adjacent, connected samples is bi-linearly interpolated to form a corresponding set of sub-samples. The set of sub-samples are warped from the reference image space to a destination image space. A final pixel color for each of a plurality of groups of sub-samples in the destination image space is computed as a weighted average of the color information of the sub-samples for each respective group. The final pixel colors are combined to render a final image in the destination image space from the at least one reference image.

Claims

1. A method of rendering images, the method comprising the steps of:

segmenting at least one reference image in a reference image space into a plurality of tiles, each tile defined by a corresponding set of image samples;

determining the connectivity of each of the samples based on the relative curvature of a surface of the corresponding tile at the sample coordinates;

bi-linearly interpolating color and depth information between adjacent, connected samples to form a corresponding set of sub-samples;

warping the set of sub-samples from the reference image space to a destination image space; and

computing a final pixel color for each of a plurality of groups of sub-samples in the destination image space as a weighted average of the color information of the sub-samples for each respective group;

wherein the final pixel colors are combined to render a final image in the destination image space from the at least one reference image.

2. The method of claim 1, further comprising the step of:

Z-buffering the set of sub-samples in the destination image space prior to computing a final pixel color.

3. The method of claim 1, wherein the relative curvature of the corresponding segment at the sample coordinates is calculated by computing a second derivative of a generalized disparity of the sample defined as the ratio of the distance between a viewing position of the at least one reference image and the plane of the at least one reference image and the distance perpendicular to the plane of the at least one reference image between the viewing position and the sample.

4. The method of claim 3, wherein the second derivative of the generalized disparity of the sample is computed along four directions in the plane of the at least one reference image at the sample coordinates, the four directions including an E-W, a SE-NW, a N-S, and a SW-NE direction.

5. The method of claim 3, wherein when the computed second derivative of the generalized disparity of the sample exceeds a predetermined threshold, the sample is not connected to form the final image in the destination image space.

6. The method of claim 1, wherein the step of bi-linearly interpolating between adjacent, connected samples comprises the steps of:

selecting a connected sample;

dividing a linear segment between the connected sample and an adjacent, connected sample to obtain at least one sub-sample;

repeatedly dividing linear segments between connected samples and adjacent connected samples, between connected samples and adjacent sub-samples, and between sub-samples and adjacent sub-samples to obtain sub-samples until a desired interpolation distance between sub-samples is achieved;

wherein sub-samples are obtained at coordinates at or near the connected samples.

7. The method of claim 6, wherein each respective tile includes a plurality of quads, each quad defined by four adjacent, connected image samples.

8. The method of claim 7, wherein the desired interpolation distance between sub-samples is defined by an interpolation factor given by the equations:

9. The method of claim 1, wherein the set of sub-samples are warped from the reference image space to the destination image space according to the equation:

$u_2=\frac{w_{11}+w_{12}+u_1+w_{13}+v_1+w_{14}·<br><br>\mathrm{\delta <br><br>}<br><br>\left(u_1,v_1\right)}{w_{31}+w_{32}+u_1+w_{33}+v_1+w_{34}·<br><br>\mathrm{\delta <br><br>}<br><br>\left(u_1,v_1\right)},<br><br>v_2=\frac{w_{21}+w_{22}+u_1+w_{23}+v_1+w_{24}·<br><br>\mathrm{\delta <br><br>}<br><br>\left(u_1,v_1\right)}{w_{31}+w_{32}+u_1+w_{33}+v_1+w_{34}·<br><br>\mathrm{\delta <br><br>}<br><br>\left(u_1,v_1\right)}$

where;

u₂, v₂ are coordinates of a sub-sample in the destination image space;

u₁, v₁ are coordinates of the sub-sample in the reference image space;

w_xy are transformation constants between the reference image space and the destination image space; and

δ

(u₁, v₁) is a generalized disparity at sub-sample (u₁, v₁), defined as the ratio of the distance between a viewing position of the at least one reference image and the plane of the at least one reference image and the distance perpendicular to the plane of the at least one reference image between the viewing position and the sub-sample.

10. The method of claim 1, wherein the set of sub-samples are warped from the reference image space to the destination image space into a warp buffer having at least two sub-sample locations for each of the two directions defining the destination image plane for each final image pixel.

11. The method of claim 10, wherein each of the warped sub-samples is stored in a respective location of the warp buffer with a pair of offset values of at least two bits each to further define the location of a sub-sample within the warp buffer location.

12. The method of claim 11, wherein the weighted average is computed by the equation:

$\frac{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>S_i·<br><br>w_i}{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_i}$

where;

S_i define the color information for each sub-sample of a respective group of sub-samples; and

w_i are weights used to define the relative contribution of the color information of each sub-sample to the final computed pixel color based on the offset values stored with the sub-sample.

13. The method of claim 12, wherein sub-samples having offset values defining locations closer to the center of a final image pixel are assigned weights that provide a greater relative contribution of the sub-sample'"'"'s color information to the final computed pixel color.

14. The method of claim 13, wherein each of the plurality of groups of sub-samples includes sub-samples located in the warp buffer within at least one pixel of a respective final image pixel.

15. The method of claim 13, wherein the weights used to define the relative contribution of the color information are defined by a function having a relatively smaller value at the corner of a two-by-two pixel neighborhood centered at a respective final image pixel, and increasing in value to reach a maximum value at the center of the respective final image pixel.

16. The method of claim 15, wherein the function is a raised cosine function having zeroes placed at the corner of a two-by-two pixel neighborhood.

17. A method of rendering images, the method comprising the steps of:

segmenting at least one reference image in a reference image space into a plurality of tiles, each tile defined by a corresponding set of image samples;

determining the connectivity of each of the samples based on the relative curvature of a surface of the corresponding tile at the sample coordinates;

warping the set of samples from the reference image space to a destination image space;

bi-linearly interpolating color and depth information between adjacent, connected warped samples to form a corresponding set of sub-samples; and

computing a final pixel color for each of a plurality of groups of sub-samples in the destination image space as a weighted average of the color information of the sub-samples for each respective group;

wherein the final pixel colors are combined to render a final image in the destination image space from the at least one reference image.

18. The method of claim 17, further comprising the step of:

Z-buffering the set of sub-samples prior to computing a final pixel color.

19. The method of claim 17, wherein the relative curvature of the corresponding segment at the sample coordinates is calculated by computing a second derivative of a generalized disparity of the sample defined as the ratio of the a distance between a viewing position of the at least one reference image and the plane of the at least one reference image and the distance perpendicular to the plane of the at least one reference image between the viewing position and the sample.

20. The method of claim 19, wherein the second derivative of the generalized disparity of the sample is computed along four directions in the plane of the at least one reference image at the sample coordinates, the four directions including an E-W, a SE-NW, a N-S, and a SW-NE direction.

21. The method of claim 19, wherein when the computed second derivative of the generalized disparity of the sample exceeds a predetermined threshold, the sample is not connected to form the final image in the destination image space.

22. The method of claim 17, wherein the step of bi-linearly interpolating between adjacent, connected samples comprises the steps of:

selecting a connected sample;

dividing a linear segment between the connected sample and an adjacent, connected sample to obtain at least one sub-sample;

repeatedly dividing linear segments between connected samples and adjacent connected samples, between connected samples and adjacent sub-samples, and between sub-samples and adjacent sub-samples to obtain sub-samples until an optimal interpolation distance between sub-samples is achieved;

wherein sub-samples are obtained at coordinates at or near the connected samples.

23. The method of claim 22, wherein each respective tile includes a plurality of quads, each quad defined by four adjacent, connected image samples.

24. The method of claim 23, wherein the optimal interpolation distance between sub-samples is defined by an interpolation factor given by the equations:

25. The method of claim 17, wherein the set of samples are warped from the reference image space to the destination image space according to the equation:

$u_2=\frac{w_{11}+w_{12}+u_1+w_{13}+v_1+w_{14}·<br><br>\mathrm{\delta <br><br>}<br><br>\left(u_1,v_1\right)}{w_{31}+w_{32}+u_1+w_{33}+v_1+w_{34}·<br><br>\mathrm{\delta <br><br>}<br><br>\left(u_1,v_1\right)},<br><br>v_2=\frac{w_{21}+w_{22}+u_1+w_{23}+v_1+w_{24}·<br><br>\mathrm{\delta <br><br>}<br><br>\left(u_1,v_1\right)}{w_{31}+w_{32}+u_1+w_{33}+v_1+w_{34}·<br><br>\mathrm{\delta <br><br>}<br><br>\left(u_1,v_1\right)}$

where;

u₂, v₂ are coordinates of a sub-sample in the destination image space;

u₁, v₁ are coordinates of the sub-sample in the reference image space;

w_xy are transformation constants between the reference image space and the destination image space; and

δ

(u₁, v₁) is a generalized disparity at sample (u₁, v₁), defined as the ratio of the distance between a viewing position of the at least one reference image and the plane of the at least one reference image and the distance perpendicular to the plane of the at least one reference image between the viewing position and the sub-sample.

26. The method of claim 17, wherein the set of sub-samples are stored into a warp buffer having at least two sub-sample locations for each of the two directions defining the destination image plane for each final image pixel.

27. The method of claim 26, wherein each of the sub-samples is stored in a respective location of the warp buffer with a pair of offset values of at least two bits each to further define the location of a sub-sample within the warp buffer.

28. The method of claim 27, wherein the weighted average is computed by the equation:

$\frac{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>S_i·<br><br>w_i}{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_i}$

where;

S_i define the color information for each sub-sample of a respective group of sub-samples; and

w_i are weights used to define the relative contribution of the color information of each sub-sample to the final computed pixel color based on the offset values stored with the sub-sample.

29. The method of claim 28, wherein sub-samples having offset values defining locations closer to the center of a final image pixel are assigned weights that provide a greater relative contribution of the sub-sample'"'"'s color information to the final computed pixel color.

30. The method of claim 29, wherein each of the plurality of groups of sub-samples includes sub-samples located in the warp buffer within at least one pixel of a respective final image pixel.

31. The method of claim 29, wherein the weights used to define the relative contribution of the color information are defined by a function having a relatively smaller value at the corner of a two-by-two pixel neighborhood centered at a respective final image pixel, and increasing in value to reach a maximum value at the center of the respective final image pixel.

32. The method of claim 31, wherein the function is a raised cosine function having zeroes placed at the corner of a two-by-two pixel neighborhood.

33. An apparatus for rendering images, the apparatus comprising:

at least one node having an ASIC and a tile cache;

the ASIC including

a warp array for warping and interpolating reference image samples;

a region accumulator having a double-buffered warp buffer for resolving visibility;

a reconstruction buffer for computing final pixel values; and

a network interface capable of connecting the at least one node to other nodes in a high-bandwidth ring;

wherein the least one node computes final pixel values of an image from the image samples of a respective tile of at least one reference image.

34. The apparatus of claim 33, wherein the warp array comprises:

a plurality of processing elements arranged as a pixel array;

each processing element including;

a simple byte-wide arithmetic logic unit (ALU); and

memory partitioned into main memory, an I/O buffer, and a sample buffer; and

a distributed linear expression for computing a linear portion of a set of 3D warping equations.

35. The apparatus of claim 33, wherein the region accumulator comprises:

an SRAM warp buffer;

a set of four sample processors that combine warped samples into the warp buffer memory; and

a pair of double-buffered fields for storing RGB values and offsets used for reconstruction.