Apparatus and method for non-uniform image scaling

• US 6,016,152 A
• Filed: 08/01/1997
• Issued: 01/18/2000
• Est. Priority Date: 08/01/1997
• Status: Expired due to Fees

• Current Assignee: Avid Technology Incorporated
• Original Assignee: Avid Technology Incorporated
• Inventors: Dickie, Garth A.
• Primary Examiner(s): Luu, Matthew
• Assistant Examiner(s): PIZIALI, JEFFREY J
• Application Number:
  US08/904,470
• Time in Patent Office: 900 Days
• Field of Search: 345/126, 345/425, 345/427, 345/430-431, 345/433, 345/436, 345/439, 358/183, 395/86, 395/127, 395/130
• US Class Current: 345/648
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 3/18 Image warping, e.g. rearranging pixels individually

Abstract

A source image may be manipulated by a computer to include special graphics effects. The source image may be used for still pictures or motion video applications and may include a single image or a sequence of images. The special graphics effects applied to the source image to create a desired destination image include various non-uniform scaling or arbitrary distortion functions. The effect has a corresponding affine transformation that approximates the non-uniform scaling function. This affine transformation is used to define an ellipse in the source image. A linear transformation from a unit circle in the source image to the ellipse in the source image is calculated. The linear transformation is used to modify a reconstruction filter in the source image. A pixel value in the destination image is determined by identifying pixels included in a support of the modified reconstruction filter in the source image in order to reduce artifacts in non-uniform scaling applications.

Claims

1. A process for obtaining a value for a pixel in a destination image produced by non-uniform transformation of a source image, comprising the steps of:

selecting a reconstruction filter;

applying an affine transformation determined by the non-uniform transformation on an area centered on the pixel in the destination image to define at least two axes in a source image space;

determining a linear transformation between an area in the source image space and the at least two axes, wherein the linear transformation corresponds to the non-uniform transformation and represents the shape of the area in the destination image transformed by a transformation defined according to the inverse of the non-uniform transformation, wherein the area is centered around a center of the at least two axes;

modifying the selected reconstruction filter using the linear transformation to create a modified reconstruction filter with a support region;

identifying which pixels from the source image are included in the support region of the modified reconstruction filter; and

determining the value for the pixel in the destination image from pixel centers of the source image included in the support of the modified reconstruction filter.

2. A process as claimed in claim 1, wherein the identifying step further includes:

creating a rectangular bounding box which includes the support of the modified filter;

applying an inverse transformation to coordinates of each pixel with a center inside the bounding box; and

determining whether the coordinates are included in the support of the unmodified selected reconstruction filter.

3. A process as claimed in claim 1, wherein the determining a value step includes:

multiplying a color value of each pixel included in the support of the modified filter by the value from the untransformed selected reconstruction filter;

determining a weighted average of the pixel values included in the modified filter.

4. A process as claimed in claim 1, wherein the identifying step further includes:

determining pixels with centers in the support of the modified filter by treating the support of the transformed filter as a polygon; and

using a polygon rasterizing technique.

5. A process as claimed in claim 1, wherein the affine transformation step is performed for a plurality of pixels.

6. A process as claimed in claim 1, wherein the performing an affine transformation step includes approximating the non-uniform transformation for implementing two-dimensional special effects by a function.

7. A process as claimed in claim 1, wherein the performing an affine transformation step includes approximating the non-uniform transformation for implementing three-dimensional effects by a function.

8. A process as claimed in claim 1, wherein the determining a linear transformation step includes removing a skew component.

9. A process as claimed in claim 1, wherein the determining a linear transformation step includes removing a skew and a rotational component.

10. A process as claimed in claim 1, wherein the performing an affine transformation step is followed by performing a perspective projection.

25. A process as claimed in claim 1, wherein the selected reconstruction filter is a quadrilateral.

32. A process as claimed in claim 1, where the at least two axes determined by the affine transformation step are eigenvectors.

11. A destination image produced by the process of non-uniformly transforming a source image performed by a process that includes:

modifying a reconstruction filter according to a linear transformation corresponding to the non-uniform transformation function; and

applying the modified reconstruction filter to the source image by identifying pixels of the source image included in a support of the modified reconstruction filter and using the value of each of the identified pixels to determine the value of a destination pixel to produce the destination image.

12. A destination image as claimed in claim 11, wherein the source image includes a two-dimensional data set.

13. A destination image as claimed in claim 11, wherein the source image includes a three-dimensional volumetric data set.

14. A destination image as claimed in claim 11, wherein the source image includes a single image.

15. A destination image as claimed in claim 11, wherein the source image includes a sequence of images.

16. A destination image as claimed in claim 11, wherein the reconstruction filters include bilinear or bicubic functions.

17. A destination image as claimed in claim 11, wherein the non-uniform transformation function includes a two-dimensional special effect.

18. A destination image as claimed in claim 11, wherein the non-uniform transformation function includes a three-dimensional special effect.

26. A destination image as claimed in claim 11, wherein the reconstruction filter is a quadrilateral.

29. A destination image as claimed in claim 11, wherein the identifying pixels step further includes:

creating a rectangular bounding box which includes the support of the modified filter;

applying an inverse transformation to coordinates of each pixel with a center inside the bounding box; and

determining whether the coordinates are included in the support of the unmodified reconstruction filter.

19. A computer-implemented process for generating a non-uniformly transformed destination image including the steps of:

determining an affine transformation of a source image based on a non-uniform transformation;

defining axes in the source image according to the affine transformation;

calculating a linear transformation from an area in the source image to the axes, wherein the linear transformation corresponds to a non-uniform transformation and represents the shape of an area in the destination image transformed by a transformation defined according to the inverse of the non-uniform transformation;

modifying a reconstruction filter in the source image according to the linear transformation;

identifying pixels of the source image included in a support of the modified reconstruction filter;

calculating the value of a point in the destination image based on the value of each of the identified pixels in the source image; and

displaying the non-uniformly transformed destination image.

27. A computer-implemented process as claimed in claim 19, wherein the reconstruction filter is a quadrilateral.

30. A computer-implemented process as claimed in claim 19, wherein the identifying step further includes:

creating a rectangular bounding box which includes the support of the modified filter;

applying an inverse transformation to coordinates of each pixel with a center inside the bounding box; and

determining whether the coordinates are included in the support of the unmodified reconstruction filter.

33. A computer-implemented process as claimed in claim 19, where the axes defined according to the affine transformation are eigenvectors.

20. A computer system for generating a representation of a non-uniformly transformed source image including a processor and a memory connected to the processor for storing a program, which when executed by the processor performs the steps of:

receiving a source image, a desired special effect, and a reconstruction filter;

modifying the reconstruction filter based on the application of the desired special effect to the source image;

identifying pixels in the source image included in a support of the modified reconstruction filter;

determining the value of a pixel in a destination based on the identified pixels; and

rendering the destination image.

21. A computer system as claimed in claim 20, wherein the source image is a single image.

22. A computer system as claimed in claim 20, wherein the source image is a sequence of images.

23. A computer system as claimed in claim 20, wherein the modified reconstruction filter does not include at least one of a skew or a rotational component.

24. A computer system as claimed in claim 20, wherein the special effect includes two-dimensional or higher dimensional effects.

28. A computer system as claimed in claim 20, wherein the reconstruction filter is a quadrilateral.

31. A computer system as claimed in claim 20, wherein the identifying step further includes:

creating a rectangular bounding box which includes the support of the modified filter;

applying an inverse transformation to coordinates of each pixel with a center inside the bounding box; and

determining whether the coordinates are included in the support of the unmodified reconstruction filter.

34. A process for obtaining a value for a pixel in a destination image produced by non-uniform transformation of a source image, comprising the steps of:

selecting a reconstruction filter;

determining a linear transformation between a unit circle in a source image space and at least two orthogonal axes in the source image space, wherein the linear transformation corresponds to the non-uniform transformation and represents the shape of the unit circle in the destination image transformed by a transformation defined according to the inverse of the non-uniform transformation, wherein the unit circle is centered around a center of the at least two orthogonal axes;

modifying the selected reconstruction filter using the transformation to create a modified reconstruction filter with a support region;

identifying which pixels from the source image are included in the support region of the modified reconstruction filter; and

determining the value for the pixel in the destination image from pixel centers of the source image included in the support of the modified reconstruction filter.

35. A process as claimed in claim 34, wherein the determining a linear transformation step further includes:

applying an affine transformation determined by the non-uniform transformation on a unit circle centered on the pixel in the destination image to define the at least two orthogonal axes.

36. A process as claimed in claim 34, wherein the identifying step further includes:

creating a rectangular bounding box which includes the support of the modified filter;

applying an inverse transformation to coordinates of each pixel with a center inside the bounding box; and

determining whether the coordinates are included in the support of the unmodified selected reconstruction filter.

37. A process as claimed in claim 34, wherein the determining a value step includes:

multiplying a color value of each pixel included in the support of the modified filter by the value from the unmodified selected reconstruction filter;

determining a weighted average of the pixel values included in the modified filter.

38. A process as claimed in claim 34, wherein the identifying step further includes:

determining pixels with centers in the support of the modified filter by treating the support of the transformed filter as a polygon; and

using a polygon rasterizing technique.

39. A process as claimed in claim 34, wherein the linear transformation step is performed for a plurality of pixels.

40. A process as claimed in claim 34, wherein the determining a linear transformation step includes approximating the non-uniform transformation for implementing two-dimensional special effects by a function.

41. A process as claimed in claim 34, wherein the determining a linear transformation step includes approximating the non-uniform transformation for implementing three-dimensional effects by a function.

42. A process as claimed in claim 34, wherein the determining a linear transformation step includes removing a skew component.

43. A process as claimed in claim 34, wherein the determining a linear transformation step includes removing a skew and a rotational component.

44. A process as claimed in claim 35, wherein the applying an affine transformation step is followed by performing a perspective projection.

45. A process as claimed in claim 34, wherein the selected reconstruction filter is a quadrilateral.

46. A process as claimed in claim 34, where the at least two orthogonal axes determined by the linear transformation step are orthogonal eigenvectors.

47. A process for obtaining a value for a pixel in a destination image produced by non-uniform transformation of a source image, comprising the steps of:

selecting a reconstruction filter;

determining a linear transformation between an area in a source image space and at least two axes, wherein the linear transformation corresponds to the non-uniform transformation and represents the shape of the area in the destination image transformed by a transformation defined according to the inverse of the non-uniform transformation, wherein the area is centered around a center of the at least two axes, wherein the at least two axes are at least two units in length, wherein each unit is equal to a distance between two adjacent pixels;

modifying the selected reconstruction filter using the transformation to create a modified reconstruction filter with a support region;

identifying which pixels from the source image are included in the support region of the modified reconstruction filter; and

determining the value for the pixel in the destination image from pixel centers of the source image included in the support of the modified reconstruction filter.

48. A process as claimed in claim 47, wherein the determining a linear transformation step further includes:

applying an affine transformation determined by the non-uniform transformation on an area centered on the pixel in the destination image to define the at least two axes.

49. A process as claimed in claim 47, wherein the identifying step further includes:

creating a rectangular bounding box which includes the support of the modified filter;

applying an inverse transformation to coordinates of each pixel with a center inside the bounding box; and

determining whether the coordinates are included in the support of the unmodified selected reconstruction filter.

50. A process as claimed in claim 47, wherein the determining a value step includes:

multiplying a color value of each pixel included in the support of the modified filter by the value from the unmodified selected reconstruction filter;

determining a weighted average of the pixel values included in the modified filter.

51. A process as claimed in claim 47, wherein the identifying step further includes:

determining pixels with centers in the support of the modified filter by treating the support of the transformed filter as a polygon; and

using a polygon rasterizing technique.

52. A process as claimed in claim 47, wherein the linear transformation step is performed for a plurality of pixels.

53. A process as claimed in claim 47, wherein the determining a linear transformation step includes approximating the non-uniform transformation for implementing two-dimensional special effects by a function.

54. A process as claimed in claim 47, wherein the determining a linear transformation step includes approximating the non-uniform transformation for implementing three-dimensional effects by a function.

55. A process as claimed in claim 47, wherein the determining a linear transformation step includes removing a skew component.

56. A process as claimed in claim 47, wherein the determining a linear transformation step includes removing a skew and a rotational component.

57. A process as claimed in claim 48, wherein the applying an affine transformation step is followed by performing a perspective projection.

58. A process as claimed in claim 47, wherein the selected reconstruction filter is a quadrilateral.

59. A process as claimed in claim 47, where the at least two axes determined by the linear transformation step are eigenvectors.

60. A computer-implemented process for generating a non-uniformly transformed destination image including the steps of:

calculating a linear transformation from a unit circle in a source image to orthogonal axes in the source image, wherein the linear transformation corresponds to a non-uniform transformation and represents the shape of a unit circle in the destination image transformed by a transformation defined according to the inverse of the non-uniform transformation;

modifying a reconstruction filter in the source image according to the linear transformation;

identifying pixels of the source image included in a support of the modified reconstruction filter;

calculating the value of a point in the destination image based on the value of each of the identified pixels in the source image; and

displaying the non-uniformly transformed destination image.

61. A computer-implemented process as claimed in claim 60, wherein the reconstruction filter is a quadrilateral.

62. A computer-implemented process as claimed in claim 60, wherein the identifying step further includes:

creating a rectangular bounding box which includes the support of the modified filter;

applying an inverse transformation to coordinates of each pixel with a center inside the bounding box; and

determining whether the coordinates are included in the support of the unmodified reconstruction filter.

63. A computer-implemented process as claimed in claim 60, where the orthogonal axes defined according to the linear transformation are orthogonal eigenvectors.

64. A computer-implemented process as claimed in claim 60, wherein the calculating a linear transformation step further includes:

determining an affine transformation of the source image based on the non-uniform effect; and

defining the orthogonal axes according to the affine transformation.

65. A computer-implemented process for generating a non-uniformly transformed destination image including the steps of:

calculating a linear transformation from an area in a source image to axes in the source image, wherein the linear transformation corresponds to a non-uniform transformation and represents the shape of the area in the destination image transformed by a transformation defined according to the inverse of the non-uniform transformation, wherein the axes are at least two units in length, wherein each unit is equal to a distance between two adjacent pixels;

modifying a reconstruction filter in the source image according to the linear transformation;

identifying pixels of the source image included in a support of the modified reconstruction filter;

calculating the value of a point in the destination image based on the value of each of the identified pixels in the source image; and

displaying the non-uniformly transformed destination image.

66. A computer-implemented process as claimed in claim 65, wherein the reconstruction filter is a quadrilateral.

67. A computer-implemented process as claimed in claim 65, wherein the identifying step further includes:

creating a rectangular bounding box which includes the support of the modified filter;

applying an inverse transformation to coordinates of each pixel with a center inside the bounding box; and

determining whether the coordinates are included in the support of the unmodified reconstruction filter.

68. A computer-implemented process as claimed in claim 65, where the axes defined according to the transformation are eigenvectors.

69. A computer-implemented process as claimed in claim 65, wherein the calculating a linear transformation step further includes:

determining an affine transformation of the source image based on the non-uniform effect; and

defining the axes according to the affine transformation.