2.2 Improving Efficiency
通过上一篇博客，我们已经找到了在蒙特卡洛方法中采样数量与方差之间的关系。如果在渲染中，我们得到了一个噪点过多的图像，增加采样数量就可以以一种可预测的方式减少误差，从而在足够的时间内生成质量足够高的图像。但是计算通常也会需要大量的时间，这同样是一种成本。
所以，在样本数量有限的情况下，减少方差的唯一方法就是充分利用已经采集到的样本。接下来，我们来讨论一下在pbrt中运用到的重要技术。
2.2.1 Stratified Sampling
在蒙特卡洛方法中，适当地调整采样策略可以更好地捕捉被积函数的特征，或者更准确的来说，是可以减少错过重要特征的可能性。其中一种重要的策略就是分层采样。分层采样将积分域分为若干区域，并且在每个区域内放置采样点，从而更好地覆盖整个采样空间，提高近似的精度。在本小节中，我们将从方差减少的角度来分析这种方法。
分层采样将积分域$\Lambda$细分为$n$个不重叠的区域$\Lambda_1, \Lambda_2,…,\Lambda_n$，我们将每个区域称为一个层stratum，并且所有层必须可以完全覆盖原始积分域：
\[\bigcup_{i=1}^n \Lambda_i=\Lambda\]为了从积分域$\Lambda$中采样，我们将该区域划分为若干个分层$\Lambda_i$，并且在每个分层内根据密度$p_i$抽取$n_i$个样本。一个简单的例子是对像素进行超采样。当对一个像素使用分层采样时，像素的面积会被划分为$k \times k$个网格，然后我们会在每个网格单元内均匀抽取一个样本。这种做法比直接从整个像素面积上随机抽取$k^2$个样本更好，因为分层采样会让样本位置不容易聚集在一起。
对于一个单一分层$\Lambda_i$，蒙特卡洛估值器的定义如下：
\[F_i=\frac{1}{n_i}\sum_{j=1}^{n_i}\frac{f(X_{i,j})}{p(X_{i,j})}\]其中，$X_{i,j}$是从分层$\Lambda_i$中抽取的第$j$个样本，$f(X_{i,j})$是我们需要近似的函数值，而$p_i(X_{i,j})$是采样点的概率密度。
对于整个区域的蒙特卡洛估值器自然是所有分层的近似的加权和：
\[F=\sum_i v_iF_i\]之所以是加权和，是因为对于每个分层的近似值，我们还需要乘以对应分层的体积占比，即$v_i$
接下来，我们来考虑分层采样的方差问题。首先，分层$\Lambda_i$内的真实值为：
\[\mu_i=E[f(X_{i,j})]=\frac{1}{v_i}\int_{\Lambda_i}f(x)dx\]则我们可以表示出分层$\Lambda_i$的方差为：
\[\sigma_i^2=\frac{1}{v_i}\int_{\Lambda_i}(f(x)-\mu_i)^2dx\]也就是说，在每个分层中抽取$n_i$个样本时，分层估值器的方差为$\sigma_i^2 / n$，则整个域上的估值器的方差为：
\[\begin{aligned} V[F] & = V\Big[\sum v_i F_i\Big] \\ & = \sum V[v_iF_i] \\ & = \sum v_i^2V[F_i] \\ & = \sum \frac{v_i^2\sigma_i^2}{n_i} \end{aligned}\]如果我们做出合理的假设，即样本数$n_i$与体积$v_i$成正比，那么我们有$n_i=v_in$，其中$n$是总样本数。那么方差就可以进一步推导为：
\[V[F] = \sum \frac{v_i^2\sigma_i^2}{n_i} = \frac{1}{n}\sum_iv_i\sigma_i^2\]当我们选择不分层采样时，我们直接从整个积分域$\Lambda$中抽取样本，这意味着每个样本都可能来自于$\Lambda$的任何部分，而非特定的分层。
为了理解不分层采样的方差，我们可以将不分层的采样视为分层采样中的一种特殊情况。根据分层的体积$v_i$定义的离散概率分布选择一个随机分层$I$，然后从该分层的域$\Lambda_I$中选择一个随机样本$X$。这种情况下，抽样可以理解为在条件$I$下选择样本。
所以，我们可以通过条件概率来表示总体方差：
\[V[F]=\frac{1}{n}\Big[ \sum_i v_i\sigma_i^2 + \sum_i v_i(\mu_i-Q)^2 \Big]\]其中，$Q$是整个域$\Lambda$上$f$的均值。我们可以分两部分来理解这个方差公式：
- 第一部分：$\frac{1}{n}\sum_i v_i\sigma_i^2$
- 这一部分是分成采样下每个分层的方差加权和
- 它描述了分层内的方差对于整体方差的贡献
- 第二部分：$\frac{1}{n}\sum_i v_i(\mu_i-Q)^2$
- 这一部分是每个分层均值与总体均值的偏差平方和
- 它描述了分层之间的差异对于整体方差的影响
我们通过分析方差公式可以得到如下结论：
- 分层采样总是减少方差，除非第二部分（即分层间差异的影响）为零。这种情况仅在$f$在每个分层$\Lambda_i$的均值相同时出现
- 为了使得分层效果最佳，我们希望尽可能最大化公式右侧第二项的值。因此，在理想情况下，分层应该尽量使得每个分层内的均值尽可能不同。
- 这也是为什么紧凑的分层（即均匀且具有较小内部变异的分层）是理想的。如果分层较宽，则它们会包含更多的变异，分层均值会更接近于总体均值$Q$
最终我们可以得到一个结论，分层采样不仅可以有效减少估计结果的方差，还可以提高收敛速度。只是，这种优势会随着维度的提升而减小。这是因为高维空间中的样本均匀分布变得更加困难，且采样的复杂度显著增加。网格数量会随着维度的增加呈指数级增长，这显著增加了计算和存储的负载度。
2.2.2 Importance Sampling
重要性采样是另一种有效的降低方差的技术。我们首先来回顾一下蒙特卡洛估值器的定义：
\[F_n=\frac{1}{n}\sum_{i=1}^n\frac{f(X_i)}{p(X_i)}\]其中，$f(x)$是被积函数，$p(x)$是我们从中抽样的PDF。我们从定义中可知，如果我们从一个与$f(x)$相似的$p(x)$中进行抽样，则估值器会以更快的速度收敛。以一种不严谨的方式解释的话，当被积函数的值相对较大时，则更可能抽到样本。
我们来思考下面这个例子。我们使用$p(x)\propto f(x)$，即$p(x) = cf(x)$作为PDF，其中$c$是一个归一化常数，它的计算公式为：
\[c=\frac{1}{\int f(x)dx}\]如果我们从这样的PDF中进行采样，则估值器中的每一项的值为：
\[\frac{f(X_i)}{p(X_i)}=\frac {f(X_i)}{cf(X_i)} = \frac{1}{c} = \int f(x)dx\]也就是说，这样的估值器的误差为$0$。当然，如果我们能计算$c$，就代表我们可以直接积分$f(x)$，那又何必使用蒙特卡洛呢？所以，我们只是需要与$f(x)$形似的$p(x)$即可。
2.2.3 Multiple Importance Sampling
在渲染领域中，我们经常会遇到涉及多个函数乘积的积分，例如$\int f_a(x) f_b(x)dx$。通常，我们可以分别为每个因子进行重要性采样，但是这个方法的效果不一定好，特别应用在渲染方程中。我们可以试着用这种思路解决$\int f_a(x) f_b(x)dx$，假设我们有两个采样分布$p_a(x)$和$p_b(x)$，它们完全匹配$f_a$和$f_b$的分布
如果我们使用$p_a$做重要性采样，则估值器为：
\[\frac{f(X)}{p_a(X)}=\frac{f_a(X)f_b(X)}{p_a(X)}=cf_b(X)\]其中，$c$是$f_a$的积分的常数。那么这个估值器的方差将和$f_b$成正比，而$f_b$本身的方差可能很高。相反的，使用$p_b$进行采样也可能会得到类似的结果。
不幸的是，从每个分布中抽取一些样本并对两个估计量求平均值的显而易见的解决方案并没有好多少。因为方差是可加的，一旦方差进入估计量，我们就无法通过将其添加到另一个低方差估计量中来消除它。
多重重要性采样可以解决这个问题，它的基本思路是，在近似积分时，我们应该从多个采样分布中采样，并希望至少有一个分布能够很好地匹配被积函数的形状。MIS提供了一种方法来加权每个技术的样本，从而消除由于被积函数和采样密度之间的不匹配带来的较大方差峰值。
对于两个采样分布$p_a$和$p_b$，从每个分布中各抽取一个样本，分别为$X \sim p_a$和$Y \sim p_b$。则蒙特卡洛估值器的定义如下：
\[w_a(X)\frac{f(X)}{p_a(X)} +w_b(Y)\frac{f(Y)}{p_b(Y)}\]其中$w_a$和$w_b$是加权函数，这两个加权函数使得估值器的期望值是$f(x)$的积分值。
接下来，我们来看看MIS蒙特卡洛估值器的一般形式：当给定$n$个采样分布$p_i$和每个分布中的样本数$n_i$，那么MIS蒙特卡洛估值器的定义为：
\[F_n=\sum_{i=1}^n\frac{1}{n_i}\sum_{j=1}^{n_i}w_i(X_{i,j})\frac{f(X_{i,j})}{p(X_{i,j})}\]其中，$w_i(X)$是加权函数，满足特定条件，从而保证估值器的无偏性。
在实践中，一个好的加权函数是平衡启发式balance heuristic。每个样本都会根据所有采样密度之和进行权衡，而非单个采样密度。这种方法减少了单个分布生成样本的方差贡献。
平衡启发式的定义为：
\[w_i(x)=\frac{n_ip_i(x)}{\sum_jn_jp_j(x)}\]让我们再次结合有两个采样分布的例子，即从每个分布中各抽取一个样本，分别为$X \sim p_a$和$Y \sim p_b$，此时的加权函数分别为：
\[\displaylines{w_a(X)=\frac{p_a(X)}{p_a(X)+p_b(X)} \\ w_b(Y)=\frac{p_b(Y)}{p_a(Y)+p_b(Y)}}\]另一种常用的方法是幂启发式，其加权函数为：
\[w_i(x)=\frac{(n_ip_i(x))^{\beta}}{\sum_j(n_jp_j(x))^{\beta}}\]其中，参数$\beta$通常取2。
幂启发式通常会比平衡启发式更有效，主要有以下原因：
- 减少低概率样本的影响：
- 幂启发式通过对低概率样本施加更大的惩罚，有效减少了这些样本对估计值的影响。这对于减少方差尤其重要，因为低概率样本通常与高方差相关。
- 增加高概率样本的权重：
- 相比平衡启发式，幂启发式增加了高概率样本的权重，从而更好地利用这些样本对估计值的贡献。这意味着在重要区域（即函数值较大的区域）内的样本对最终估计的贡献更大。
- 适应性更强：
- 在实际应用中，函数$f(x)$可能具有复杂的形状和高变化区域。幂启发式能够更好地适应这些变化，通过增加高概率区域的样本权重来提高估计精度。
单样本模型是一种多重重要性采样（MIS）的变体，其中我们不从所有可能的采样分布中抽样，而是从多个采样技术中随机选择一个进行采样。这种方法的目标是利用不同采样技术的优势，减少估计方差。
多重重要性采样也有缺点，包括实现复杂度增加、计算开销增大、对参数选择敏感以及对采样分布的依赖等。在实际应用中，需要根据具体情况权衡这些缺点和其带来的方差减小效果，以确定是否使用 MIS 以及如何最佳地实现它。
2.2.4 Russian Roulette
在渲染中，我们经常会使用以下形式的估计器：
\[\frac{f(X)v(X)}{p(X)}\]其中，被积函数由一些容易计算的因子$f(X)$和一些计算复杂的因子$f(X)$组成。在这种情况下，大部分的计算开销都用于计算$v(X)$。
如果$f(X)$为零，显然我们可以跳过$f(X)$的计算，因为它不会影响估计器的值。然而，如果我们跳过评估那些 $f(X)$较小但非零的估计器，会引入偏差并系统地低估被积函数的值。
所以，我们可以引入一种叫做“俄罗斯转盘”的技术，它可以通过跳过对最终结果贡献较小的样本的评估来提高蒙特卡罗估计的效率。
当使用俄罗斯转盘时，我们需要选择一个终止概率$q$，合理选择$q$能够有效地跳过对结果贡献较小的样本，从而提高蒙特卡罗估计的效率，同时保持估计的无偏性。
终止概率的选择方式有很多，常见的方法是根据被积函数值动态调整$q$，以达到最佳效果。
当计算时，我们以概率$q$跳过估值器的计算，并在其位置上使用某个常数值$c$，通常情况下$c=0$。对应地，仍然计算当前估值器的概率为$1 -q$，但权重为$1/(1-q)$，这样可以有效地补偿被跳过的样本。
这样一来，我们得到的新估值器为：
\[F'= \begin{cases} \frac{F-qc}{1-q} \quad \xi > q \\ c \quad\quad\;\; otherwise \end{cases}\]我们可以推导出，新的估值器的期望值没有改变。实际上，俄罗斯轮盘并不会减少方差，但是它提高了蒙特卡罗估计的效率，因为如果概率选择得当，跳过的样本通常对最终结果的贡献较小。
2.2.4 Splitting
splitting技术通过增加某些维度上的样本数量来提高蒙特卡罗估计的效率。例如，考虑一个一般形式的积分：
\[\int_A\int_Bf(x,y)dxdy\]当使用标准的重要性采样估值器时，我们可能从独立分布的$p_a$和$p_b$