Systems and methods for estimating pixel intensity

• US 8,538,204 B1
• Filed: 09/07/2011
• Issued: 09/17/2013
• Est. Priority Date: 09/07/2011
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Pantaleoni, Jacopo
• Primary Examiner(s): Allison, Andrae S
• Application Number:
  US13/227,298
• Time in Patent Office: 741 Days
• Field of Search: 382298-300, 345/426, 345/419, 345/420, 345/421, 345/422, 345/423, 345/424, 345/425, 345/427
• US Class Current: 382/300
• CPC Class Codes: G06T 15/506 Illumination models
• CPC Class Codes: G06V 10/60 relating to illumination properties, e.g. using a reflectance or lighting model

Abstract

A method for estimating pixel intensity includes generating a plurality of bidirectional paths extending between a light source and a measurement point, whereby the measurement point represents a pixel within the image. Each bidirectional path includes a light subpath portion extending from the light source and an eye subpath portion extending from the view point and coupled to the light subpath. Each light subpath is characterized by a number of vertices included therein, and similarly, each eye subpath is characterized by a number of vertices included therein. The plurality of bidirectional paths are sorted into separation populations, whereby each population includes bidirectional paths constructed from eye subpaths having a common number of vertices, and light subpaths having a common number of vertices. An intensity contribution is computed for each of the individual populations, and the intensity contributions are summed over all populations to estimate the intensity of the pixel.

Claims

1. A method for estimating the intensity of a pixel included within an image, the method comprising:

(i) generating a plurality of bidirectional paths extending between a light source and a set of measurement points, each bidirectional path comprising a light subpath extending from the light source and an eye subpath extending from the view point and coupled to the light subpath,

wherein each light subpath is characterized by a number of vertices included within said light subpath, and

wherein each eye subpath is characterized by a number of vertices included within said eye subpath;

(ii) sorting the plurality of bidirectional paths into separation populations, wherein each population includes bidirectional paths constructed from eye subpaths having a common number of vertices, and light subpaths having a common number of vertices;

(iii) computing an intensity contribution of each population, and

(iv) summing the intensity contributions over a plurality of populations to estimate the intensity of the pixel.

2. The method of claim 1, wherein (ii) further comprises resampling a subset of the plurality of generated bidirectional paths with a distribution proportional to a global contribution function of the image.

3. The method of claim 1, wherein (iii) comprises:

evolving one or more bidirectional paths of a population to generate a respective one or more evolved bidirectional paths; and

computing an intensity contribution for said population based upon the one or more evolved bidirectional paths included therein.

4. The method of claim 3, wherein evolving the bidirectional paths comprises evolving the bidirectional paths through a plurality of Differential Evolution Metropolis-Hasting steps.

5. The method of claim 3, wherein evolving the bidirectional paths comprises:

for each bidirectional subpath within the population,

(a) evolving a selected bidirectional path;

(b) computing an acceptance probability for the evolved bidirectional path; and

(c) replacing the selected bidirectional path with the evolved bidirectional path based upon the computed acceptance probability; and

(d) repeating (a)-(c), wherein the evolved bidirectional path operates as the selected bidirectional path, and a new bidirectional path is evolved therefrom in (a).

6. The method of claim 5, wherein (a) comprises evolving a selected bidirectional path according to the equation:

u′

=u_i+g(u_ki−

u_k2)+e,

wherein;

u_i is the selected bidirectional path,

u′

is the evolved bidirectional path,

g and e are predefined parameters, and

k₁, k₂ are random indices, such that k₁≠

i, k₂≠

i, k₁≠

k₂.

7. The method of claim 5, wherein (b) comprises computing an acceptance ratio of the evolved bidirectional path according to the equation:

8. The method of claim 5, wherein (c) comprises:

comparing the acceptance probability to a random number occurring within an interval of [0, 1];

determining that the acceptance probability is greater than the random number; and

replacing the selected bidirectional path with the evolved bidirectional path.

9. The method of claim 3, wherein computing an intensity contribution for the population comprises computing an intensity contribution of one or more evolved bidirectional paths included within the population according to the equation:

I_j^new,evolved=I_j^old,evolved+a_y×

c×

h_j(u′

)

wherein

I_j^new,evolved represents an updated accumulated intensity contribution of the evolved bidirectional paths of the population,

I_j^old,evolved represents a previously accumulated intensity contribution of the evolved bidirectional paths of the population, and

the quantity;

a_y×

c×

h_j(u′

)

represents the intensity contribution provided by an evolved bidirectional path, wherein;

a_y is the acceptance ratio of said evolved bidirectional path,

c is a predefined value, and

the quantity h_j(u′

) is predefined) and represents the intensity of a filtering kernel associated to the measurement point j applied at the evolved path u′

.

10. The method of claim 3,

wherein said population further includes one or more bidirectional paths which remain unevolved,

wherein computing an intensity contribution for the population further comprises computing an intensity contribution for the respective one or more unevolved bidirectional paths according to the equation:

I_j^{new,unevolved}=I_j^{old,unevolved}+(1−

a_y)×

c×

h_j(u_i)

wherein

I_j^{new,unevolved} represents an updated accumulated intensity contribution of the unenvolved bidirectional paths of the population,

I_j^{old,unevolved} represents a previously accumulated intensity contribution of the unevolved bidirectional paths of the population, and

the quantity;

(1−

a_y)×

c×

h_j(u_i)

represents the intensity contribution of an unevolved bidirectional path, wherein;

a_y is the acceptance ratio of said unevolved bidirectional path,

c is a predefined value, and

the quantity h_j(u_i) is predefined and represents an intensity of a filtering kernel associated to the measurement point j applied at the unevolved path u_i.

11. The method of claim 10, wherein computing an intensity contribution for the population comprises computing a sum of the updated intensity contribution for the one or more evolved bidirectional paths and the updated intensity contribution for the one of more unevolved bidirectional paths, said sum provided according to the equation:

I_j^new,evolved+I_j^{new,unevolved}=I_j^new,total

wherein;

I_j^new,evolved is the collective intensity contribution of the evolved bidirectional paths;

I_j^{new,unevolved} is the collective intensity contribution of the unevolved bidirectional paths; and

I_j^new,total is the collective intensity contribution of the population of the evolved and unevolved bidirectional paths.

12. The method of claim 1, wherein (vi) comprises computing a collective intensity estimate for the pixel according to the equation:

13. A system operable for estimating the intensity of a pixel included within an image, the system including a processor operable for:

(i) generating a plurality of bidirectional paths extending between a light source and a set of measurement points, each bidirectional path comprising a light subpath extending from the light source and an eye subpath extending from the view point and coupled to the light subpath,

wherein each light subpath is characterized by a number of vertices included within said light subpath, and

wherein each eye subpath is characterized by a number of vertices included within said eye subpath;

(ii) sorting the plurality of bidirectional paths into separation populations, wherein each population includes bidirectional paths constructed from eye subpaths having a common number of vertices, and light subpaths having a common number of vertices;

(iii) computing an intensity contribution of each population, and

(iv) summing the intensity contributions over a plurality of populations to estimate the intensity of the pixel.

14. The system of claim 13, wherein the processor'"'"'s operation (ii) further comprises resampling a subset of the plurality of generated bidirectional paths with a distribution proportional to a global contribution function of the image.

15. The system of claim 13, wherein the processor'"'"'s operation (iii) further comprises:

evolving one or more bidirectional paths of a population to generate a respective one or more evolved bidirectional paths; and

computing an intensity contribution for said population based upon the one or more evolved bidirectional paths included therein.

16. The method of claim 15, wherein the processor'"'"'s operation of evolving the bidirectional paths comprises:

for each bidirectional subpath within the population,

(a) evolving a selected bidirectional path;

(b) computing an acceptance probability for the evolved bidirectional path; and

(c) replacing the selected bidirectional path with the evolved bidirectional path based upon the computed acceptance probability; and

(d) repeating (a)-(c), wherein the evolved bidirectional path operates as the selected bidirectional path, and a new bidirectional path is evolved therefrom in (a).

17. A computer program product, resident on a non-transitory computer readable medium, storing instruction code for estimating the intensity of a pixel included within an image, the computer program product comprising:

(i) instruction code for generating a plurality of bidirectional paths extending between a light source and a set of measurement points, each bidirectional path comprising a light subpath extending from the light source and an eye subpath extending from the view point and coupled to the light subpath,

wherein each light subpath is characterized by a number of vertices included within said light subpath, and

wherein each eye subpath is characterized by a number of vertices included within said eye subpath;

(ii) instruction code for sorting the plurality of bidirectional paths into separation populations, wherein each population includes bidirectional paths constructed from eye subpaths having a common number of vertices, and light subpaths having a common number of vertices;

(iii) instruction code for computing an intensity contribution of each population, and

(iv) instruction code for summing the intensity contributions over a plurality of populations to estimate the intensity of the pixel.

18. The computer program product of claim 17, wherein the instruction code (ii) further comprises instruction code for resampling a subset of the plurality of generated bidirectional paths with a distribution proportional to a global contribution function of the image.

19. The computer program product of claim 17, wherein the instruction code (iii) further comprises:

instruction code for evolving one or more bidirectional paths of a population to generate a respective one or more evolved bidirectional paths; and

instruction code for computing an intensity contribution for said population based upon the one or more evolved bidirectional paths included therein.

20. The computer program product of claim 19, wherein the instruction code for evolving the bidirectional paths comprises:

for each bidirectional subpath within the population,

(a) instruction code for evolving a selected bidirectional path;

(b) instruction code for computing an acceptance probability for the evolved bidirectional path; and

(c) instruction code for replacing the selected bidirectional path with the evolved bidirectional path based upon the computed acceptance probability; and

(d) instruction code for repeating (a)-(c), wherein the evolved bidirectional path operates as the selected bidirectional path, and a new bidirectional path is evolved therefrom in (a).