Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2000-09-29
2003-12-30
Brier, Jeffery (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S604000, C345S645000, C345S557000, C345S558000, C345S646000, C345S647000, C345S648000, C345S667000
Reexamination Certificate
active
06670965
ABSTRACT:
BACKGROUND
This invention is generally related to digital image processing and more particularly to methodologies for warping an input image using affine and perspective transformations.
A digital image is an electronic representation of a scene using a collection of picture elements (“pixels”). In a two-dimensional (2-D) image, each pixel may be identified by a pair of numbers or “coordinates” written in the form (u,v) of a Cartesian coordinate system, and is assigned one or more intensity values for one or more colors (abbreviated here as “color values”).
Spatial transformations, also referred to as warping, can transform an input, 2-D image into an output image, by scaling upwards or downwards, rotating, translating (moving), and/or shearing the input image. These transformations are known as affine transformations. Another type of spatial transform is a perspective transformation in which the image is transformed so that its edges converge to one or both axes of the output image's coordinate system.
Image warping is used to enhance image quality and correct images in a variety of different applications, including computer graphics, computer vision, medical imaging, and remote sensing. In addition, image-based modeling and rendering (IBMR), where three-dimensional (3-D) images are created from 2D images or photographs, makes extensive use of 2-D warping to transform several reference images and then composite them for a desired 3-D view. The use of IBMR in 3-D video applications, such as computer games and computer-animation, calls for fast warping, due to the fast image rendering required for depicting complex and rapidly changing scenes.
Warping may be viewed as a mapping of the input image coordinate system (u,v) into the coordinate system (x,y) of the output image. This may be depicted by a matrix equation [x′,y′,w]
T
=matrixW *[u,v,1]
T
in which the coordinates (u,v) of a pixel in the input image are mapped to coordinates (x=x′/w,y=y′/w) by performing the matrix multiply operation and a perspective divide. The matrix W is a 3×3 matrix known as a concatenated warping matrix whose elements define the affine and perspective transformations.
Some scanline warping methodologies have been developed that operate only along rows and columns of the input image and one or more intermediate images, to exploit simplifications in digital filtering and memory access. See e.g. Catmull, Edwin and Alvy Ray Smith, “3-D Transformations of Images in Scanline Order,”
Computer Graphics
, (SIGGRAPH '80 Proceedings), vol. 14, no. 3, pp. 279-285, July 1980. The latter is a “two-pass” technique in which the first pass through the input image applies a transform to each row to yield an intermediate result, and then a second pass applies another transform to each column of the intermediate result image to yield the output image.
Some of the problems with the two-pass technique referred to above include the provision of a special case for rotations of 90 degrees (due to a singularity in the transform applied in the first pass). This makes the technique more complicated in a hardware-only implementation. In addition, the two passes through the input and intermediate images may not be the most efficient way to utilize hardware parallelism. Finally, reconstruction of aliasing holes require yet another pass through the output image, thereby further increasing the time needed to warp the input image.
REFERENCES:
patent: 5204944 (1993-04-01), Wolberg et al.
patent: 5398117 (1995-03-01), Suzuki et al.
patent: 5568600 (1996-10-01), Kaba
patent: 5977977 (1999-11-01), Kajiya et al.
Blakely , Sokoloff, Taylor & Zafman LLP
Brier Jeffery
Intel Corporation
Tran Tam
LandOfFree
Single-pass warping engine does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Single-pass warping engine, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single-pass warping engine will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3124488