US2009153576A1PendingUtilityA1
Image Synthesis Methods and Systems
Est. expiryJun 19, 2020(expired)· nominal 20-yr term from priority
Inventors:Alexander Keller
G06T 11/10G06T 15/506G06F 17/10G06T 15/55G06T 15/06
49
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
The present invention provides systems, devices, computer-implemented methods and computer program code products (software) operable to evaluate integrals using quasi-Monte Carlo methodologies, and in particular embodiments, adaptive quasi-Monte Carlo integration and adaptive integro-approximation in conjunction with techniques including a scrambled Halton Sequence, stratification by radical inversion, stratified samples from the Halton Sequence, deterministic scrambling, bias elimination by randomization, adaptive and deterministic anti-aliasing, anti-aliasing by rank-1 lattices, and trajectory splitting by dependent sampling and rank-1 lattices.
Claims
exact text as granted — not AI-modified1 . A computer-implemented method of generating a pixel value for a pixel in an image displayable via a display device, the pixel value being representative of a point in a scene, the method comprising:
A. generating a set of sample points, at least one sample point being generated using at least one sample, the at least one sample comprising at least one element of a sequence, and wherein the set of sample points comprises quasi-Monte Carlo points; and B. evaluating a selected function at one of the sample points to generate a value, the generated value corresponding to the pixel value, the pixel value being usable to generate a display-controlling electronic output.
2 . The method of claim 1 wherein the sequence comprises a scrambled Halton sequence.
3 . The method of claim 1 wherein, in the sequence, a radical inverse function is replaced with a scrambled radical inverse function to yield a scrambled Halton sequence.
4 . The method of claim 3 wherein the replacement of the radical inverse with the scrambled radical inverse is described by the following equation:
Φ
b
′
:
0
→
⋂
[
0
,
1
)
i
=
∑
l
=
0
∞
a
l
(
i
)
b
l
↦
∑
l
=
0
∞
π
b
(
a
l
(
i
)
)
b
-
l
-
1
,
wherein π b is a scrambling permutation applied to the digits a g (i), and wherein the scrambling permutation is determined by a permutation of the set of integers {0, . . . , b−1}.
5 . A computer-implemented method of generating a pixel value for a pixel in an image display able via a display device, the pixel value being representative of a point in a scene, the method comprising:
A. generating a set of sample points, at least one sample point being generated using at least one sample, the at least one sample comprising at least one element of a low-discrepancy sequence, and wherein the generating includes using an adaptive, interleaved sampling scheme based on a deterministically scrambled Halton sequence to yield a deterministic, low-discrepancy set of sample points; and B. evaluating a selected function at one of the sample points to generate a value, the generated value corresponding to the pixel value, the pixel value being usable to generate a display-controlling electronic output.
6 . A computer-implemented method of generating a pixel value for a pixel in an image displayable via a display device, the pixel value being representative of a point in a scene, the method comprising:
A. generating a set of sample points, at least one sample point being generated using at least one sample, the at least one sample comprising at least one element of a sequence, wherein the set of sample points comprises quasi-Monte Carlo points, and wherein the generating includes adaptively sampling by using radical inversion-based points; and B. evaluating a selected function at one of the sample points to generate a value, the generated value corresponding to the pixel value, the pixel value being usable to generate a display-controlling electronic output.
7 . The method of claim 6 wherein the sequence is a Halton sequence.
8 . The method of claim 6 wherein the sequence is a (t, s) sequence.
9 . The method of claim 6 wherein the generating includes constructing multi-dimensional, substantially uniform deterministic samples using a Halton sequence.
10 . The method of claim 6 wherein the generating includes using sets of points having maximized minimum distance.
11 . The method of claim 6 wherein the generating includes using point sets having maximized minimum distance with respect to low dimensional projections.
12 . The method of claim 6 wherein the sequence is a scrambled Halton sequence, and wherein the generating further comprises extracting stratified sequences of sample points from the scrambled Halton sequence.
13 . The method of claim 6 wherein the sequence is a (t, s) sequence, and wherein the generating further comprises extracting stratified sequences of sample points from the (t, s) sequence.
14 . The method of claim 6 wherein the evaluating comprises evaluating a pixel integral, and further comprising applying a tone mapping function within the pixel integral, so as to improve convergence.
15 . The method of claim 14 wherein applying a tone mapping function comprises applying a tone-mapping function that bounds the integrands, so as to improve convergence.
16 . The method of claim 14 further comprising controlling adaptation by applying image processing operators.
17 . The method of claim 14 further comprising controlling adaptation by applying image processing operators to final pixel values rather than to single samples.
18 . The method of claim 12 further comprising providing bias elimination by randomization, wherein the randomization comprises any of scrambling, or randomly shifting deterministic points of the scrambled Halton sequence modulo one.
19 . The method of claim 7 further comprising providing deterministic anti-aliasing by scaling a first component of a sampling function by a first scaling coefficient, and a second component by a second scaling coefficient, to obtain a stratified sample pattern that can be periodically tiled over an image plane, the stratified sample pattern having a plurality of strata;
identifying each stratum with a given pixel; and after identifying each stratum with a given pixel, obtaining a per-stratum identification value from the pixel coordinates and generating a Halton sequence specific to a corresponding sample based on the corresponding identification value.
20 . The method of claim 7 further comprising providing adaptive anti-aliasing by stratification by the Halton sequence.
21 . The method of claim 19 further comprising determining the number of strata by selecting exponents, for the first and second scaling coefficients, large enough so that strata covered by adjacent pixel reconstruction filters do not contain repeated patterns.
22 . The method of claim 6 wherein a pixel is deemed refined whenever a refinement criterion is met, and wherein the refinement criterion can include comparing the image gradient against a predefined threshold T.
23 . The method of claim 22 further comprising selecting a value, for an exponent for a coefficient to be multiplicatively applied to the threshold T, to enable adaptation to the speed of convergence, wherein the coefficient is the sampling rate.
24 . The method of claim 14 wherein the tone mapping comprises compression of a luminance value L prior to averaging, and wherein the luminance value L is compressed in accordance with the following compression equation:
R
α
:
0
+
→
[
0
,
1
]
L
↦
{
L
L
<
α
α
+
(
1
-
α
)
L
-
α
1
+
L
-
α
else
wherein α is a coefficient selected to be between 0 and 1, and R α is a response curve mapping that can be selected by selection of coefficient α.
25 . A computer-implemented method of generating a pixel value for a pixel in an image displayable via a display device, the pixel value being representative of a point in a scene, the method comprising:
A. generating a set of sample points, at least one sample point being generated using at least one sample, the at least one sample comprising at least one element of a sequence, wherein the generating includes sampling by using rank-1 lattice points; and B. evaluating a selected function at one of the sample points to generate a value, the generated value corresponding to the pixel value, the pixel value being usable to generate a display-controlling electronic output.
26 . The method of claim 25 further comprising selecting a rank-1 lattice such that its mutual minimum distance among sample points is maximal.
27 . The method of claim 25 further wherein the generating includes using lattice sequences.
28 . The method of claim 25 wherein the lattices are lattices in Korobov form.
29 . The method of claim 25 wherein the lattices are rank-1 lattices or higher rank lattices in Korobov or general form.
30 . The method of claim 25 further comprising using lattices with respect to low-dimensional projections of the points.
31 . The method of claim 25 further comprising applying anti-aliasing by lattices, including adding to the lattice points a different random shift to generate a randomly shifted lattice, thereby to attenuate aliasing over the pixels.
32 . The method of claim 31 further comprising de-randomizing the random shifts per pixel by determining a shift per pixel by elements of a low discrepancy point set or a deterministic point set with maximized minimum distance, with stratification that matches the pixels.
33 . The method of claim 32 wherein the stratification is induced by a rank-1 lattice.
34 . The method of claim 32 wherein the stratification is induced by the Voronoi diagram of a rank-1 lattice.
35 . The method of claim 32 further comprising using recursive Korobov filters wherein the points inside a given lattice cell are determined by another set of lattice points transformed into the given lattice cell.
36 . The method of claim 25 further comprising applying trajectory splitting using domain stratification induced by a rank-1 lattice with maximized minimum distance.
37 . The method of claim 25 further comprising providing quasi-Monte Carlo integro-approximation by lattice points, and wherein point sets and sequences are selected by maximum minimum distance.
38 . In a computer graphics system including a processor, a display device, user input elements, and one or more memory elements, the computer graphics system being operable to generate images displayable via a display device, the images representing a scene and comprising a plurality of pixels, a computer-implemented system for generating a pixel value for a pixel in an image displayable via the display device, the pixel value being representative of a point in a scene, the system comprising:
A. means for generating a set of sample points, at least one sample point being generated using at least one sample, the at least one sample comprising at least one element of a sequence, and wherein the set of sample points comprises quasi-Monte Carlo points; and B. means, in communication with the means for generating a set of sample points, for evaluating a selected function at one of the sample points to generate a value, the generated value corresponding to the pixel value, the pixel value being usable to generate a display-controlling electronic output.
39 . A computer program product for use in a computer graphics system, for enabling the computer graphics system to generate a pixel value for a pixel in an image displayable via a display device, the pixel value being representative of a point in a scene, the computer program product comprising a computer-readable medium having encoded thereon:
A. computer-readable program instructions executable to enable the computer graphics system to generate a set of sample points, at least one sample point being generated using at least one sample, the at least one sample comprising at least one element of a sequence, and wherein the set of sample points comprises quasi-Monte Carlo points; and B. computer-readable program instructions executable to enable the computer graphics system to evaluate a selected function at one of the sample points to generate a value, the generated value corresponding to the pixel value, the pixel value being usable to generate a display-controlling electronic output.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.