Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-11-25
2002-04-09
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06369818
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field computer technology for mapping one data space to another data space.
2. Background
Computers are often used to map data that exists in a source data space to a destination data space. This type of mapping is often used in “virtual reality” and “telepresence” applications. The data in the source data space can represent a warped image that is obtained by a distorting lens such as a fisheye lens or a catadioptric lens. The data in the destination data space can be presented by a presentation device such as a video screen, computer monitor or printer. The problem is how to rapidly generate the data for the destination data space from the source data space.
One approach is to backward map the coordinates of a point in the destination data space to coordinates in the source data space and to obtain the value for the point in the destination data space from the mapped point in the source data space. Precisely mapping each point (for example, by using floating point calculations to perform the mapping) is expensive in either memory or computation, or both.
Another approach is to precisely map a grid of points from the destination data space to the source data space. These grid points bound regions (patches) that contain pixels that have similar mapping as the grid points that bound the region. Thus, the precisely mapped grid points are used to determine coefficients for a mapping that can be applied to each point in the region. Each of the grid points in the destination data space has a corresponding grid point in the source data space. Thus, the destination grid point and the corresponding source grid point are referred to as a “point pair.”
By using all four of the destination and source point pairs that bound a region, a perspective transformation can be computed and used to find the corresponding pixel in the source data space. Thus,
x
s
=
ax
d
+
by
d
+
t
x
ex
d
+
fy
d
+
1
y
s
=
cx
d
+
dy
d
+
t
y
ex
d
+
fy
d
+
1
Can be used to perform the mapping where (x
s
, y
s
) is the is the resulting coordinate in the source data space, (x
d
, y
d
) is the coordinates of the pixel in the destination data space, and a, b, c, d, e, f t
x
and t
y
are the perspective transform coefficients. This calculation includes at least six multiply operations, two division operations, and six add operations. The multiply and division operations are computationally expensive., Although this equation does not generate mapping artifacts between the regions, the additional computational overhead is often prohibitive.
Another approach is to generate a look-up table that provides the x
s
and y
s
coordinates when given the x
d
and y
d
coordinates. With high resolution images and high-resolution presentation devices, these look-up tables become unwieldy even with modem computers.
Another approach is to approximately map the region using a less computationally expensive formula. For example, an affine transformation can be used to perform this mapping. In this circumstance, three of the four sets of destination and source point pairs are used to compute the affine coefficients for the transformation. Then coordinates that specify a pixel that in the destination data space can be used to find the corresponding pixel in the source data space. Thus,
x
s
=ax
d
+b
y
+c
y
s
=dx
d
+ey
d
+f
Where (x
s
, y
s
) is the resulting coordinate in the source data space, (x
d
, y
d
) is the coordinates of the pixel in the destination data space, and a, b, c, d, e and f are the affine coefficients for the grid region bounded by the precisely mapped grid points. This calculation includes four multiply operations and four add operations for each pixel in the patch and so is still computationally expensive. An additional problem with this approach is that an affine transformation often generates a very poor approximation to the perspective transformation. The affine transformation only uses three of the four point pairs that bound the region. Thus, the affine transformation can generate mapping artifacts (such as discontinuities) along edges of the quadralateral defining the region in the source space.
FIG. 1A
illustrates a quadralateral patch in source space, indicated by general reference character
100
, used to show mapping artifacts generated by the affine transformation. The quadralateral patch in source space
100
is bounded by grid points (such as a point A
101
, a point B
103
, a point C
105
, and a point D
107
). Applying an affine transformation to this region (using the points
101
,
103
, and
105
and the corresponding points in the destination space) would generate the patch bounded by the point A
101
, the point B
103
, the point C
105
and a point D′
109
instead of approximating the original patch.
FIG. 1B
illustrates a presentation of a correctly mapped image, indicated by general reference character
150
, that represents a magnified image presented on a presentation device. This image does not have any mapping artifacts. It can be generated by precisely mapping each point in the destination data space to the source data space. It can also be generated by precisely mapping grid points, and using the perspective transformation previously discussed to map the points in each region defined by the grid. Compare
FIG. 1B
with FIG.
1
C.
FIG. 1C
illustrates a presentation of an incorrectly mapped image, indicated by general reference character
160
, that shows mapping artifacts
161
that can result from the use of the affine transformation. As can be seen, these mapping artifacts include discontinuities in lines. Other mapping artifacts include (without limitation) texture discontinuities and color discontinuities.
It would be advantageous to use a fast mapping algorithm that also provides a good approximation for a precise perspective-correct transformation that maintains continuity across patch boundaries without the computational or memory overheads associated with the prior art. Devices and computers that use these methods will operate more efficiently than those that use prior art methods will.
SUMMARY OF THE INVENTION
The invention provides a fast and accurate means of mapping one data space into another by precisely mapping grid points between the data spaces and then by performing a bilateral-bilinear interpolation to map the points bounded by the precisely mapped grid points.
One aspect of the invention is a computer-controlled method that includes the step of determining a region in a destination data space. The region is bounded by a plurality of grid points. It defines a first plurality of data points in the destination data space. The method precisely maps the plurality of grid points in the destination data space to a plurality of mapped grid points in a source data space. The source data space contains, or is associated with, a second plurality of data points. The plurality of mapped grid points define a plurality of boundary lines that represent the boundary of the region as mapped into the source data space. The method also applies a bilateral-bilinear interpolation algorithm to approximately map the first plurality of data points to the second plurality of data points.
Another aspect of the invention is an apparatus that includes a central processing unit (CPU) and a memory coupled to the CPU. The apparatus also includes a region determination mechanism that is configured to determine a region in a destination data space. The region is bounded by a plurality of grid points. The region defines a first plurality of data points within the destination data space. The apparatus also includes a precise mapping mechanism that is configured to precisely map the plurality of grid points determined by the region determination mechanism to a plurality of mapped grid points in a source data space. The source data space contains (or associates) a second plurality of data points. The plurality of mapped grid points define a plurality of boundary lines that represe
Furlan John Louis Warpakowski
Hoffman Robert G.
Be Here Corporation
Curtis Daniel B.
Nguyen Phu K.
LandOfFree
Method, apparatus and computer program product for... 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, apparatus and computer program product for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, apparatus and computer program product for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2923588