Image analysis – Applications – 3-d or stereo imaging analysis
Reexamination Certificate
1996-12-03
2001-06-05
Couso, Yon (Department: 2616)
Image analysis
Applications
3-d or stereo imaging analysis
C382S285000
Reexamination Certificate
active
06243488
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method of image processing and an image processing apparatus.
In particular, the present invention relates to rendering a two dimensional image from three dimensional image data, wherein a polygon defined in three dimensional space is projected into two dimensional space and pixel values from a two dimensional image are mapped onto pixel positions within said projected two dimensional polygon.
Computer graphics systems are known in which two dimensional video images or two dimensional textures appear wrapped around a solid three dimensional object. A three dimensional object is represented as three dimensional image data, in which the vertices of polyhedra are defined as three dimensional co-ordinate locations within a virtual three dimensional world, commonly referred to as world-space. The object is viewed by producing a two dimensional projection from the three dimensional data, so as to produce a still two-dimensional image, or a sequence of images, which may be recorded onto the photographic film or a video carrying medium.
The position of objects, along with viewing position and orientation, may be adjusted within the three dimensional world-space, resulting in a sequence of projections being calculated. These projections may be calculated on a frame-by-frame basis, possibly in real time, thereby facilitating the creation of a virtual interactive environment.
In order to effect the rendering of three dimensional objects, each surface of a polyhedron may be considered individually, thereby reducing the object to a net of polygons. Thus, it is possible to project the object on a polygon-by-polygon basis and to calculate lighting values for each polygon, so that displayable pixel values may be determined for the pixel positions which lie within the projected polygon boundaries.
In addition to identifying solid colours for each polygon surface, it is also possible to map an existing video frame onto the polygon surfaces, so that it appears as if a flat two dimensional image has been wrapped around the three dimensional object. The video frame may consist of a single image, thereby creating the effect of a texture being mapped onto the three dimensional object. Alternatively, the video image may consist of a video sequence, thereby creating the effect of a moving video image being wrapped around the solid object.
In the three dimensional world-space, polygons have orientations in the x, y and the z dimensions. However, once projected onto a two dimensional plane, the polygons are defined with only two dimensions which, in order to distinguish these from the x, y and z dimensions of the three dimensional world, will be identified herein as X and Y dimensions. Thus, within a video frame, lines are scanned from the top left corner, in which traversing across a line is achieved by increasing values of X and advancing to the next line is achieved by increasing values of Y.
In order to create the illusion of a three dimensional object being viewed, it is necessary to take account of perspective, when projecting the three dimensional polygons onto the two dimensional plane. This is a non-linear process and, consequently, computationally demanding. It is therefore preferable to project the vertices of the three dimensional polygons onto positions within the two dimensional plane and thereafter perform further operations, such as shading and rendering, on the two dimensional polygons, such that it is only necessary to perform calculations with respect to two dimensions, rather than three.
It is also conventional to perform manipulations on the two dimensional polygon by processes of linear interpolation. Thus, in preference to allocating a single colour to each polygon surface, thereby resulting in a clear identification of the polygon boundaries, it is possible to perform Gouraud shading on the polygons by identifying a polygon colour for each of the vertices. Thereafter, pixel positions along the edges of the polygon are calculated by linearly interpolating along said edges and pixel values within the polygon are allocated values by linearly interpolating across the horizontal scan-line.
Although this process works adequately well when performing solid shading on an object, it has a major disadvantage when performing texture or video mapping.
As previously stated, the purpose of performing texture mapping or video mapping is to create the illusion of a texture or video image being wrapped around a solid three dimensional object. Thus, the desired result will be achieved if the calculations are performed in the three dimensional world-space. However, as previously stated, this is computationally demanding and would not, therefore, be realised in most practical embodiments. However, performing the mapping operation on the two dimensional polygon by a process of linear interpolation fails to take account of the non-linear nature of the perspective, resulting in incorrectly calculated values and clear errors in the final output image.
SUMMARY OF THE INVENTION
According to a first aspect of the present invention, there is provided an image processing method for rendering a two dimensional image from three dimensional image data, wherein a polygon defined in three dimensional space is projected into two dimensional space and pixel values from a two dimensional image are mapped onto pixels within said projected two dimensional polygon, characterised in that: positions within said two dimensional images are identified along a locus to be interpolated by addressing values from a look-up table to obtain a substantially perspectively correct mapping.
Thus, the present invention allows mapping values to be calculated, initially, by a process of linear interpolation. The values calculated by this method may then be perspectively corrected by addressing the look-up table.
According to a second aspect of the invention, there is provided an image processing apparatus arranged to render a two dimensional image from three dimensional image data, such that a polygon defined in three dimensional space is projected into two dimensional space and pixel values from a two dimensional image are mapped onto pixels within the projected polygon, characterised by: storage means arranged to store look up tables of values defining perspective-correcting functions, and processing means arranged to interpolate a locus of positions within the input image by addressing values from a look up table so as to perspectively correct the interpolated positions.
Thus, the present invention provides an advantage of allowing perspectively correct video and texture mapping, but with minimal additional computational requirements.
REFERENCES:
patent: 4661986 (1987-04-01), Adelson
patent: 4812988 (1989-03-01), Duthuit et al.
patent: 4817005 (1989-03-01), Kubota et al.
patent: 4858149 (1989-08-01), Quarendon
patent: 4882683 (1989-11-01), Rupp et al.
patent: 5056045 (1991-10-01), Ohsawa
patent: 5107444 (1992-04-01), Wu
patent: 5175806 (1992-12-01), Muskovitz et al.
patent: 5222896 (1993-06-01), Smith, Jr.
patent: 5245700 (1993-09-01), Fossum
patent: 5454068 (1995-09-01), Ramanujam
patent: 5537228 (1996-07-01), Dillinger
patent: 5544292 (1996-08-01), Wilsner
patent: 5579454 (1996-11-01), Billyard et al.
patent: 5614961 (1997-03-01), Gibeau et al.
patent: 5659671 (1997-08-01), Tannenbaum et al.
“Survey of Texture Mapping”, by P.S. Heckbert, IEEE Computer Graphics and Applications, Nov. 6, 1986, No. 11, pp. 56-67.
Couso Yon
Patel Jayanit K.
U.S. Philips Corporation
Wieghaus Brian
LandOfFree
Method and apparatus for rendering a two dimensional image... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for rendering a two dimensional image..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for rendering a two dimensional image... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2546284