Variance Minimization Light Probe Sampling  
SIGGRAPH 2009 Poster 

Kuntee Viriyothai Paul Debevec  
USC Institute for Creative Technologies 
Introduction:
We present a technique for sampling light probe images using variance minimization. The technique modifies the median cut algorithm for light probe sampling [Debevec 2005] so that the variance within each region is minimized. Figure 1 shows 4, 16, 64 and 256 lights sampled from the Grace Cathedral lighting environment using the proposed variance minimization algorithm. The median cut algorithm tends to compute partitions which cut right through the brightest light sources, so these sampled lights are not placed in the optimal positions. Figure 2 shows a simple case highlighting how the variance minimization technique improves on the median cut approach.
Algorithm:
The algorithm recursively divides the entire light probe image into 2^n regions as follows:
 1. Add the entire light probe image to the region list as a single region.
 2. For each region in the list, subdivide such that the maximum of the two subregions' variances is minimized.
 3. If the number of iterations is less than n, return to step 2.
 4. Place a light source at the centroid of each region, and set the light source color to the sum of the pixel values within the region.
The variance of each region r can be calculated from the following equation:
Where Lp is the light energy weighting factor of p,
and dp is the distance from p to the centroid of r.
The calculation of the variance of each region is accelerated using summed area tables.
Results:
Figure 3 illustrates the differences in sample placement between the Median Cut algorithm and the proposed Variance Minimization algorithm. Figure 4 shows a scene rendered with 64 sampled lights from the Grace Cathedral light probe which is a close match to the ground truth MonteCarlo solution. 

Material:
SIGGRAPH 2009 Poster:
 VarianceMinimization_SIG09.pdf, 366 KB. ( Adobe Acrobat )
 VarianceMinimization_4ftx3ft_Poster.png, 18.9 MB.
Related Projects:
 ImageBased Lighting:
 Median Cut Algorithm for Light Probe Sampling, SIGGRAPH 2005 Poster