Computer graphics processing and selective visual display system – Computer graphics processing – Adjusting level of detail
Reexamination Certificate
1999-06-14
2004-01-13
Tung, Kee M. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Adjusting level of detail
Reexamination Certificate
active
06677948
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention is directed to defocusing a simulated image. More particularly, this invention is directed to simulating defocusing in synthetic images using multiple resolutions.
2. Description of Related Art
Depths of focus calculations are rarely performed in real-time graphics applications even though they can be quite valuable. This occurs because the computational cost of a depth of focus calculation can be exceedingly high. Conventionally, a single defocused frame can take several minutes to generate. To make matters worse, simple depth of focus control usually requires a long sequence of related frames.
“A Lens and Aperture Camera Model for Synthetic Image Generation”, Potmesil et al, Computer Graphics, ACM Press (1981) describes a method for simulating depth of field effects caused by a lens and aperture in a computer graphics system. The method is a two-pass post-filtering process. The first pass computes an image and a corresponding z-depth map. The second pass computes depth of field effects to generate a defocused image.
Given the color of each pixel and its distance from the camera plane, the size of the image, the position of each pixel and an illumination distribution, a circle of confusion may be computed for each pixel. The circle of confusion of a pixel defines how that pixel will contribute to the output image. A defocused image is then generated by calculating the size and properties of the circle of confusion formed by each input pixel and combining the contribution of each circle of confusion to form the defocused image. In other words, the intensity of a pixel in the defocused image is determined by summing the intensity distributions of overlapping circles of confusion for each pixel in the original image.
There are three key steps that are repeated for each input pixel according to Potmesil's method. These three steps occur after a rendering engine has produced a two-dimensional image and a z depth map from a camera viewpoint. The first step includes determining the radius of a circle of confusion for a pixel. This radius is determined using the distance of the pixel from the camera and the optical parameters of the camera system that is being modeled using the following equation:
r
=
&LeftBracketingBar;
V
u
-
V
p
&RightBracketingBar;
F
nV
u
(
1
)
where:
r is the radius of the circle of confusion;
V
p
is the distance from the image plane to a lens element;
V
u
is the image distance;
F is the focal length; and
n is the aperture number.
The second step determines the illumination distribution within the determined circle of confusion given the color values of the original pixel. Potmesil discloses using precalculated lookup tables to reduce the processing cost of this operation. Lastly, Potmesil combines the illumination distribution information for each circle of confusion that overlaps each pixel into an output image in accordance with the following formula:
Q
(
X
,
X
+
Δ
X
)
,
(
Y
,
Y
+
Δ
Y
)
=
∑
p
=
1
A
f
(
x
p
,
y
p
,
z
p
)
q
p
z
p
2
∑
p
=
1
A
f
(
x
p
,
y
p
,
z
p
)
z
p
2
(
2
)
where:
Q is the final intensity at pixel area (X,X+&Dgr;X)(Y,Y+&Dgr;Y);
A is the number of point samples in the image;
q
p
is the intensity of point sample p;
X
p
is the x coordinate of the sample pixel p in the image plane;
y
p
is the y coordinate of the sample pixel p in the image plane; and
z
p
is the z depth of the sample pixel p; and
f
(
x
p
,
y
p
,
z
p
)
=
∫
x
x
+
Δ
x
∫
y
y
+
Δ
y
I
(
z
p
,
(
x
-
x
p
)
2
+
(
y
-
y
p
)
2
)
ⅆ
y
ⅆ
x
(
3
)
where I is an intensity-distribution function, and with the condition that:
∫
-
∞
∞
∫
-
∞
∞
I
(
z
p
,
(
x
-
x
p
)
2
+
(
y
-
y
p
)
2
)
ⅆ
y
ⅆ
x
=
1.
(
4
)
Potmesil also simulates diffraction effects of lenses by modifying the intensity distribution across the circle of confusion. If a flat intensity distribution model for each circle of confusion is assumed, then the contribution of out of focus pixels can be considered low-resolution details in the final image. The radius of the circle of confusion determines how low the resolution of each contribution is. The traditional computational expense for combining the contributions of each pixel, using standard hardware, is proportional to the square of the radius of the circle of confusion.
In Potmesil's method, the complexity of the processing increases exponentially as the radius of the circle of confusion of each pixel increases. As an image becomes increasingly defocused, the circle of confusion of each pixel increases. As a significant number of pixels become out of focus, the processing time for each frame increases rapidly. Therefore, Potmesil's method can be extremely slow for significantly defocused images.
Some recent work has sought to address this problem by performing importance-based rendering only on pixels that are modified, while exploiting interframe coherence. “Importance Ordering for Real-Time Depth of Field,” P. Fearing, Proceedings of the 3rd International Conference on Computer Science, pp. 372-380, 1996, teaches ranking the pixels according to the degree of change in defocus and/or distance. The ranking is then used to prioritize the pixels. Only those pixels with a change above a threshold are modified. The pixels are then modified according to their ranked order of importance and the available processing resources. However, processing times for the first frame after the coherence is lost can still be significant.
Humans focus cameras by trial and error, i.e., experimentation. A human points a camera at a subject and manually changes the focus until a desired affect is achieved. Because focusing calculations take such a long time, defocus experimentation using computer generated images has been impractical.
SUMMARY OF THE INVENTION
If defocusing computations were fast enough to allow near real time computation of sequences of related frames, rendering systems could allow trial and error adjusting of focusing affects.
The systems and methods of this invention improve upon Potmesil's method by combining an area of confusion generated for each pixel using a multi-resolution method.
The systems and methods of this invention improve upon the system and method taught in Potmesil by simplifying the determination of the contribution of each pixel in the input image to the output image.
The systems and methods of this invention determine a region of confusion for each pixel, and a plurality of sets of image elements. Each set of image elements has a different resolution. The systems and methods of this invention then determine the contribution of the pixel to each element in the sets of image elements. The region of confusion includes the contributions from the sets of image elements.
In an exemplary embodiment of the systems and methods of this invention, the area of the region of confusion of each pixel is decomposed into a set of image elements on a pyramidal basis. Given the specific region of confusion for a given pixel, it is possible to compute a minimal and complete representation in a pyramid basis. A complete representation is one in which the basis elements are set in the pyramid structure such that when an image is reconstructed, the exact illumination and extent of the original signal is reproduced. A minimal representation is one in which the pyramid elements used to reproduce a signal are chosen so as to modify as few elements as possible.
The systems and methods of this invention exploit the fact that it is more efficient to fill large low-resolution areas in a multi-resolution structure than it is to fill low-resolution areas in an original high-resolution image. The systems and methods of this invention couple the efficient decomposition of each region of c
Wasserman Richard M.
Yu Dahai
Cao Huedung X.
Mitutoyo Corporation
Oliff & Berridg,e PLC
Tung Kee M.
LandOfFree
Systems and methods for multi-resolution image defocusing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for multi-resolution image defocusing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for multi-resolution image defocusing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3255116