这个系列是Physically Based Rendering: From Theory To Implementation的读书笔记，本节主要介绍采样理论的相关内容。
Sampling Theory
在渲染的过程中我们需要对连续的函数进行采样来获得离散的数字图像。对连续信号进行采样的相关理论可以参考在CV课程中介绍过的频域分析的相关内容，这里主要介绍图像渲染时的反走样(anti-aliasing)相关技术。
反走样最直接的方法是提高采样的频率。根据采样定律，只要采样的频率大于信号最大频率的2倍就可以避免走样的问题。然而这种方法在实践中一般是行不通的，这是因为图形学中连续信号都不是有限带宽(band limited)的，理论上需要无限的采样率才能够重建出原始信号。因此需要一些其它的方法来解决渲染时的走样问题。
Sources of Aliasing in Rendering
在渲染中，走样的主要原因是场景中的几何元素。当场景中的物体投影到成像平面上时，物体的边缘会引入阶跃函数(step function)，使得我们无法通过有限的采样率来重建出这样的突变。除此之外，场景中的小物体也会导致整体图像的走样：如果物体小到低于采样的间隔，那在物体运动的情况下它会反复地在图像上消失又出现。走样的另一个常见原因是物体的材质和纹理，如果采样频率低于纹理变化的频率同样会导致走样的问题。
显然我们无法从根源上去除这些导致走样的因素，因此各种反走样技术的核心在于减轻走样在视觉上的影响。
Antialiasing Techniques
在渲染中常用的反走样计算可以分为三类：非均匀采样(nonuniform sampling)、自适应采样(adaptive sampling)和预滤波(prefiltering)。
Nonuniform Sampling
尽管原始信号是无限带宽的，理论上任意有限的采样率都无法完美解决走样的问题，但我们可以通过合理地设置采样率来减轻走样对视觉的影响。非均匀采样的思想是使用一个随机数来对采样频率进行扰动：
\[\sum_{i=-\infty}^\infty \delta \bigg(x - (i + \frac{1}{2} - \xi) T \bigg)\]其中$\xi$为(0, 1)区间上的随机数。显然这样仍然无法避免走样的问题，但使用非均匀采样可以把规则的伪影(artifacts)转换成人眼不敏感的噪声。这样尽管走样的问题仍然存在，渲染出的图像却更加符合人的认知。
Adaptive Sampling
自适应采样的思想是对图像中不同的区域采用不同的采样频率：对于信号变化剧烈的区域，我们可以使用更高的采样频率从而减轻走样的问题。显然自适应采样的难点在于如何识别出图像中哪些区域有高频的信号，因此在实践中直接使用自适应采样的方法比较少见。
Prefiltering
预滤波的思想是在对信号进行重建前首先进行滤波来去除高频成分，这样就可以保证对滤波后的信号进行采样不会出现走样的问题。尽管对图像进行滤波往往会造成图像的模糊，但对人眼来说模糊的图像也要比走样要容易接受得多。
Low-Discrepancy Sequence
在渲染中我们往往需要对[0, 1)n区间进行采样，其中最基本的采样方法是生成[0, 1)区间上的随机数。显然随机数的”质量”对于渲染后的最终结果有着重要的影响，实际上如果使用”高质量”的随机数我们只需要少量的样本就可以渲染出不错的图像，从而大大提升了渲染的效率。要描述随机数的”质量”则需要引入差异(discrepancy)的概念。
discrepancy可以理解为样本在[0, 1)n空间中分布的均匀程度。我们可以在空间中划分出一个区域，然后比较区域中样本占总体的比例与区域体积的大小，它们的差值作为该区域中随机样本的discrepancy。以下图为例，在灰色区域中的样本比例为0.25，区域面积为0.09，因此该区域的discrepancy为0.16。
整个[0, 1)n空间上的discrepancy可以定义为所有可行划分的discrepancy的最大值：
\[D_N (B, P) = \sup_{b \in B} \bigg\vert \frac{ \# \{ x_i \in b \} }{N} - V(b) \bigg\vert\]discrepancy越小，样本在空间中的分布越均匀。同时不难发现discrepancy实际上描述了使用概率估计区域$b$的体积与它实际体积的差值，因此discrepancy也可以理解为区域$b$体积估计值与真实值的最大误差。除此之外，我们还可以把区域$b$的一角固定在原点，这种情况下的discrepancy记为$D_N^* (B, P)$。
在很多情况下我们可以解析地计算样本分布的discrepancy。以一维情况为例，假设$N$个样本均匀分布在区间[0, 1)上：
\[x_i = \frac{i}{N}\]此时这些样本的”差异”为：
\[D_N^* (B, P) = \frac{1}{N}\]我们可以将这些样本稍加移动，从而得到更低的discrepancy：
\[x_i = \frac{i - \frac{1}{2}}{N}\] \[D_N^* (B, P) = \frac{1}{2 N}\]实际上对于一维的情况，任意分布样本discrepancy的理论下界为：
\[D_N^* (B, P) = \frac{1}{2N} + \max_{1 \leq i \leq N} \bigg\vert x_i - \frac{2i-1}{N} \bigg\vert\]因此均匀分布的样本具有最小的discrepancy，这与我们直观的认知是一致的。这样看来只要使用均匀分布的样本来进行采样就应该能够得到好的渲染结果，但实际上使用均匀分布的样本进行采样会将渲染时产生的走样替换成噪声，在这种情况下均匀分布的样本并不是最优的选择。同时需要注意的是在某些情况下discrepancy本身也不是一个很好的度量，某些低差异序列容易导致样本聚团的问题，这会降低采样的效率。
Stratified Sampling
PBRT中介绍的第一种采样算法是分层抽样(stratified sampling)。它的基本思想是把整个空间均匀划分成若干个互不重叠的区域，然后在每个区域中随机采样出一个样本，这样就可以保证任意两个样本点都不会过于接近。
分层抽样的一个缺陷在于维数灾难(curse of dimensionality)：当需要对多维空间进行采样时，均匀划分空间所需的区域数量会随着维度的数量按指数函数增长。我们可以减少那些不太重要维度上进行划分的数目，但这样的话容易导致生成的样本不是那么的均匀。为了解决这样的问题，在PBRT中使用了随机关联(random association)的方式来进行处理：我们可以在不同的维度上独立地进行分层抽样，然后按照随机的顺序将它们组合起来形成多维的样本点。
分层抽样的另一个难点在于样本的数目是任意的，有时可能无法将样本均匀地分散在空间中(比如说在2维平面上无法直接分层采样出7个样本)。在PBRT中使用Latin超立方抽样(Latin hypercube sampling, LHS)来解决这个问题：LHS会对每个维度均匀划分成$n$个区域并在对角线方向的每个小超立方体中生成随机样本，然后LHS会在每个维度上对这些样本点进行随机重排来获得均匀分布的样本。
LHS可以避免生成的样本发生聚团的问题，但是LHS采样的结果不一定会比分层抽样要好。实际上随着样本数$n$的增加，LHS的效果会越来越差。
The Halton Sampler
Halton序列(Halton sequence)是一种常用的低差异序列，它不仅可以保证生成的样本不会发生聚团而且还能够生成任意维度的均匀分布样本而不仅仅适用于低维空间。Halton序列使用了逆序基数(radical inverse)的方式来生成随机样本，对于任意正数$a$我们可以用基数$b$的和来表示：
\[a = \sum_{i=1}^m d_i(a) \ b^{i-1}\]其中$d_i(a)$表示$b$进制下第$i$位的值，$0 \leq d_i(a) \leq b-1$。而所谓逆序基数则是将$a$的每一位逆序排放并把小数点放在最前面从而得到一个$b$进制下[0, 1)区间上的数：
\[\Phi_b(a) = 0. d_{m}(a) \ d_{m-1}(a) \ ... \ d_1(a)\]这样每一位数字对逆序后的贡献为$d_i(a) \ b^{-i}$。使用逆序基数来生成随机数最基本的方式是以2作为底数，这样生成的序列称为van der Corput序列(van der Corput sequence)：
\[x_a = \Phi_2 (a)\]van der Corput序列生成的随机数可见下表：
这样生成的一维随机数序列的discrepancy为$D_N^* (P) = O(\frac{\log{N}}{N})$，满足$n$维序列的最优discrepancy：
\[D_N^* (P) = O \bigg( \frac{(\log{N})^n}{N} \bigg)\]想要生成$n$维的Halton序列只需要取前$n$个质数作为基即可：
\[x_a = (\Phi_2 (a), \Phi_3 (a), \Phi_5 (a), ..., \Phi_{p_n} (a))\]可以证明这样生成的$n$维随机序列具有渐进最优的discrepancy：
\[D_N^* (x_a) = O \bigg( \frac{(\log{N})^n}{N} \bigg)\]另一种常用的$n$维随机序列是Hammersley序列(Hammersley sequence)：
\[x_a = (\frac{a}{N}, \Phi_{b_1} (a), \Phi_{b_2} (a), ..., \Phi_{b_n} (a))\]其中$N$为所生成的样本总数，$b_i$则均为质数。二维平面上的Halton序列和Hammersley序列可见下图：
不难发现Halton序列可以生成任意数量的随机样本，而Hammersley序列则只能生成$N$个随机样本。
Halton序列和Hammersley序列的一个缺陷在于当基数$b$比较大时会产生过于均匀的样本，如下图中的(a)所示。解决这个问题的一种方法是对数字$(0, 1, …, b-1)$进行重新排列，从而得到一个新的随机数：
\[\Phi_b(a) = 0. p(d_{m}(a)) \ p(d_{m-1}(a)) \ ... \ p(d_1(a))\]重新排列后的样本点如(b)图所示。
除了Halton序列和Hammersley序列外，PBRT中还介绍了其他的采样方法如(0, 2)序列、Sobol序列等。在大多数情况下使用Halton序列已经能够得到足够好的渲染结果，因此其它的采样方法等以后有时间再写吧。