Replica Exchange Light Transport on Relaxed Distributions
Hisanari Otsu1
Yonghao Yue2
Qiming Hou3
Kei Iwasaki4
Yoshinori Dobashi5
Tomoyuki Nishita6123
The University of Tokyo / UEI Research
Columbia University / JSPS
Zhejiang University
456
Wakayama University
Hokkaido University / CREST
Hiroshima Shudo University / UEI Researchprobability…

Level 2mutationprobability sample spacemutationexchange…

Level 1mutation

(a)

(b)

(c)

probability sample space(d)exchange

Level 0Figure 1: (a) Reference image. (d): An enlarged view of the region
marked red in (a). (b) and (c) show the enlarged rendered results
for the same region, using [Kelemen et al. 2002] and our method,respectively. (b) and (c) are rendered with the same computation
time.

1Introduction

Developing a robust method for computing global illumination isa challenging problem. A Markov chain Monte Carlo (MCMC)
method, like [Jakob and Marschner 2012], samples the light pathspace with a probability proportional to the per-path contribution,
by successively mutating path samples (e.g., perturbing a reflection direction). In practice, a path sample could get stuck in a highenergy peak for multiple mutations, resulting in a bright spot artifact. To resolve this problem, we present a new unbiased rendering
framework based on a replica exchange technique [Kitaoka et al.
2009], a variant of MCMC technique. A replica exchange technique incorporates a set of different distributions. We propose tointroduce a set of relaxed distributions, which are beneficial for reducing the chance of getting stuck.

2Our Framework

We use multiple distributions fk (Figure 2), where k is a level, andassign a path sample Xk to each of these distributions. Each pathsample Xk (a random variable in the sample space corresponding
to a light path x̄) is successively mutated to obtain a sequence of the(i)(i)
sample {Xk }, so that the distribution of {Xk } is proportional tofk . The replica exchange technique can be viewed as a Metropolis
technique working on a product sample space X = X0 × X1 × · · ·with a distribution F = f0 f1 · · · .
For the distributions, we choose f0 to be proportional to the contribution I(x̄) of light path x̄. For higher levels, we propose to choose
fk to be proportional to I(x̄)+εk , where εk is a relaxation constantand is larger for higher level k. As the sample space for the lightpaths, we consider primary sample space (a high dimensional unit
cube defining the parameters of a path) introduced by [Kelemenet al. 2002]. Distributions in higher levels are more relaxed, in thesense that when we consider the normalized versions of I(x̄) + εk ,a higher level distribution is closer to the uniform distribution.
We utilize two kinds of mutations: (1) mutating a path sample
in each level independently, and (2) exchanging path samples between two successive levels. For (1), the mutation and the acceptance probability are defined similarly to [Kelemen et al. 2002].
For (2), the acceptance probability for exchanging two samples(i)(i)
Xk and Xk+1 in successive levels k and k + 1 is defined as(i)a(Xk(i)↔ Xk+1 ) = min(1,(i)(i)

fk (Xk+1 )fk+1 (Xk )(i)(i)
fk (Xk )fk+1 (Xk+1 )). Since thepeaks in higher levels are more smoothed, the acceptance proba-mutation…

mutationsample space

Figure 2: Illustration of our framework.
bility for (1) becomes higher for a higher level. Hence, the samples
can be more easily mutated across the whole space, through therelaxed distributions.
As X0 is proportionally distributed according to I(x̄), it can be directly used for rendering the image similar to a Metropolis framework. A sample in any higher level k, can also be used to provide
an unbiased estimate of the final image, by multiplying a factor of∫
ck I(x̄), where ck = P (I(x̄) + εk )dx̄ is a normalizing factor
I(x̄)+εk
computed from a uniform sampling of the space (i.e., via large step
mutations), and P is the light path space. (We can regard that estimate as a result of performing importance sampling according toI(x̄) + εk .) Additionally, we combine the estimates from different
levels using multiple importance sampling for variance reduction.

3 Results and Future WorkWe show the rendered results in Figure 1, together with a comparison against previous method [Kelemen et al. 2002]. With the same
computation time, our method can significantly reduce the brightspots. An interesting remark is that although the relaxed distribution is different from the distribution of contributions hence seems
to be less efficient in terms of importance sampling, they indeed
help improve the overall computation efficiency. Moreover, since
the values of a relaxed distribution are always larger than 0, ergodicity is guaranteed even if we only use local perturbations, which
is not the case in previous MCMC based rendering techniques. As
future work, we would like to theoretically analyze the efficiencyof our framework, and to seek for a spatial subdivision structure,
where each region has an individual relaxation constant, for further
improvement of the efficiency. We also plan to combine our methodwith [Jakob and Marschner 2012].

References
JAKOB , W., AND M ARSCHNER , S. 2012. Manifold exploration:a markov chain monte carlo technique for rendering scenes withdifficult specular transport. ACM Trans. Graph. (SIGGRAPH
2012) 31, 4, 58:1–58:13.
K ELEMEN , C., S ZIRMAY-K ALOS , L., A NTAL , G., AND
C SONKA , F. 2002. A simple and robust mutation strategy for themetropolis light transport algorithm. Computer Graphics Forum(EUROGRAPHICS 2002) 21, 3, 531–540.
K ITAOKA , S., K ITAMURA , Y., AND K ISHINO , F. 2009. Replica
exchange light transport. Computer Graphics Forum 28, 8,2330–2342.