重要性采样
\[ \newcommand{\d}{\mathrm{d}} \]
蒙特卡洛积分
首先来看我们常用的蒙特卡洛积分（按照Wikipedia这已经算是重要性采样的形式了），注意所有的\(X_i\)都是独立同分布的： \[ I \approx I_{MC}=\frac{1}{N} \sum \frac{f(X_i)}{p(X_i)} \tag{1} \] 当\(f(x) \neq 0\)的时候\(p(x)>0\)的话，这个估计就是无偏的。证明也很简单，直接在(1)式两端求期望即可。由于\(X_i\)之间是独立的，因此可以计算出蒙特卡洛估计器的方差为： \[ \mathbb{V}[I_{MC}]=\mathbb{V}[\frac{1}{N} \sum \frac{f(X_i)}{p(X_i)}]=\frac{1}{N^2}\mathbb{V}[\sum \frac{f(X_i)}{p(X_i)}]=\frac{1}{N^2} \cdot N \cdot \mathbb{V}[\frac{f(X_i)}{p(X_i)}]=\frac{1}{N}\mathbb{V}[\frac{f(X_i)}{p(X_i)}] \tag{2} \] 标准差即为： \[ \sigma = \frac{1}{\sqrt{N}}\sigma[\frac{f(X_i)}{p(X_i)}] \tag{3} \] 等式右边的方差项是常数，因此积分器的误差随着样本数量增加的衰减速度是\(O(n^{-1/2})\)的，并不是很快。
要注意的是，在路径追踪中我们一般用的是单点的蒙特卡洛采样，也就是认为： \[ I_{MC}=\frac{f(X_i)}{p(X_i)} \tag{4} \]
重要性采样
积分器中的\(p(x)\)是可以任选的，而如果它恰好是\(f(x)\)的常数倍的即\(p(x)=Cf(x)\)的话，(2)和(3)式的误差就变为0了！然而简单计算一下我们会发现这是一个悖论： \[ 1=\int \limits_\Omega p(x)\d x=\int \limits_\Omega Cf(x)\d x=C\int \limits_\Omega f(x)\d x=CI \] 上式说明\(C=I^{-1}\)，也就是我们需要提前得知\(I\)的值才能得到理想的\(p(x)\)，但是\(I\)的值正是我们想要计算的目标！
即便没法把采样的方差降为0，上面的分析也能作为选择\(p(x)\)的指导方针：让\(p(x)\)的形状尽可能地接近\(f(x)\)，从而尽可能多采样重要也就是f(x)的值更大的区域。
常用的重要性采样比如漫反射表面的余弦采样，还有直接光源采样等等，都符合这个原则。
多重重要性采样
如何组合多个不同的采样策略？一些简单的策略是，固定使用其中的一个分布来采样，或者是从每一个分布都采样，使用这些采样估计积分后对结果进行平均。很遗憾这些都是行不通的，不仅无法减少方差甚至可能得到错误的结果，具体的说明可以参考[5]。[1]中也给出了一个例子用于证明这些简单策略是有误的，对于Cornell Box场景，如果我们分别以\(1/2\)的使用\(p_1(x)\)（余弦采样）和\(p_2(x)\)（直接光源采样），渲染出的图像如下：
整体的图像显得偏暗，原因是直接光源采样在这个场景中不满足\(f(x)\neq 0\)处\(p(x)\neq 0\)因此是有偏的，上面的方法无异于在一张正确和一张错误的图像之间做了混合。正确的思路是，如果要以\(1/2\)的概率在两个分布之间做选择，根据全概率公式，选中某条光线的概率是： \[ p(X)=\frac{1}{2}p_1(X)+\frac{1}{2}p_2(X) \tag{5} \] 将(5)式带入到蒙特卡洛积分中可得单点估计值为： \[ \frac{f(X)}{\frac{1}{2}p_1(X)+\frac{1}{2}p_2(X)} \tag{6} \] 这就是最简单的多重重要性采样(Multiple Importance Sampling也称MIS)，使用这个方法渲染出来Cornell Box长下面这样：
Veach在97年的博士论文[2]中给出了MIS的一般形式，假设有\(n\)个采样策略（分布）\(p_i\)，每个策略\(p_i\)采样\(n_i\)个样本\(X_{i,j}\)，那么积分的估计值为： \[ I_{MC}=\sum\limits_{i=1}^{n}\frac{1}{n_i}\sum\limits_{i=1}^{n_i}w_i(X_{i,j})\frac{f(X_{i,j})}{p_i(X_{i,j})} \tag{7} \] \(w_i(X_{i,j})\)为权重函数，理想情况下它应该满足，当\(p_i\)与真实的采样分布越相似时\(w_i\)越大，反之则越小。从数学上来说，\(w_i\)要满足两个条件才能保证估计是无偏的，分别是：
- 当\(f(x) \neq 0\)时，\(\sum_{i=1}^{n}w_i(x)=1\)
- 当\(p_i(x)=0\)时，\(w_i(x)=0\)
这就能说明为什么上面的例子可以得到正确的画面了，虽然单独使用直接光源采样是有偏的，但是由于\(1/2\)作为恒定的权重函数满足这两个条件（虽然不一定能减小方差）。实践中有两种常用的权重函数，分别是Balance Heuristic和Power Heuristic。
Balance Heuristic
Balance Heuristic的定义为： \[ w_i(x)=\dfrac{n_i p_i(x)}{\sum_j{n_j p_j(x)}} \tag{8} \] 假如从两个分布\(p_1\)和\(p_2\)中分别只采样一个样本\(X\)和\(Y\)，那么(7)式可以简化为： \[ \frac{f(X)}{p_1(X)+p_2(X)}+\frac{f(Y)}{p_1(Y)+p_2(Y)} \tag{9} \] 一个直观的理解[5]是，比如\(p_1(X)\)很小，但是\(p_2(X)\)较大，认为此时\(p_2\)策略更加有效，那么\(p_2(X)\)在分母上就能有效削弱\(f(X)\)的贡献从而减小方差。所以Balance Heuristic能够自动识别并且惩罚那些“极其罕见但恰好发生”的高方差样本，只要\(p_i\)中至少有一个分布的形状与真实分布类似那么Balance Heuristic就有助于减小方差。
Power Heuristic
Power Heuristic相当于是Balance Heuristic的一般形式： \[ w_i(x)=\dfrac{(n_i p_i(x))^\beta}{\sum_j{((n_j p_j(x))^\beta}} \tag{10} \] 这里就不再展开说明。
One-Sample Model
(7)式要求在每个分布中都进行采样，对于路径追踪来说样本数量很快就会爆炸。Veach给出了更适合路径追踪的One-Sample Model，根据一个确定的离散概率分布以\(q_i\)的概率选中策略\(p_i\)并只在\(p_i\)中采样，那么易得无偏的积分估计值为： \[ I_{MC}=\frac{w_i(X)}{q_i}\frac{f(X)}{p_i(X)} \tag{11} \]
分层采样
TODO