分層取樣（stratified sampling）、霍爾頓取樣（Halton sampling）、泊松盤取樣（Poisson disk sampling）

在繪製圖像時，定義在像平面空間上的入射輻射度是一個連續函式，而生成的數字影象卻是一組離散的、在矩形網格上對齊的畫素值。從連續函式取樣，計算離散的畫素值，取樣的方式能明顯地影響繪製圖像的質量。

目標是取樣得到的樣本能較好地覆蓋整個樣本空間，而且各個樣本之間不要太相似。

1 分層取樣（stratified sampling）

在繪製圖像取樣畫素時，可能對單個畫素取樣不止一次，根據多個樣本計算得到最終的畫素值。

一個簡單的做法是，若需要對單個畫素取樣

次，則直接獨立重複地隨機取樣

次，得到

個樣本。但是，如果運氣不好，樣本可能會聚集在樣本空間的某個區域性，此時取樣的效果相對糟糕。

隨機取樣，樣本可能在區域性聚集，效果較差

為了避免這種糟糕的情況，

分層取樣（stratified sampling）

把樣本空間分割成互不重疊的子域，一個子域稱為一個

層（stratum）

，在每層單獨地取樣一次，這樣便確保了每個樣本不會靠得太近。

分層取樣，各個樣本位於各自的層，不會在區域性聚集

在取樣每層時，透過給該層中心點加上一個不超過該層範圍的隨機偏移量，抖動（jitter）中心點，得到一個隨機點作為樣本。這種隨機的抖動有助於把取樣頻率不足導致的圖形走樣轉化成噪聲。

如果在取樣每層時不抖動，直接取該層中心點作為樣本，則當分層取樣使用這種不抖動的模式時，雖然生成影象的質量不是最好的，但在比較不同取樣技術的效果時很有用。

雖然分層取樣確保了在單個畫素內部取樣多次時，得到的樣本不會太相似，但是實際上，在繪製圖像時，同時也希望在同一佈局區域中這些畫素的樣本也不要太相似，這樣才能更好地覆蓋整個像平面空間上對應的樣本空間。

而且，雖然分層取樣透過分層操作在一定程度上避免了各個樣本靠得太近，但是，如果運氣不好，相鄰層的樣本可能恰好靠近兩層共同的邊界，此時取樣的效果就沒有那麼好了。

此外，當對單個畫素取樣某些特殊的次數時，可能難以進行分層操作。例如，當需要對單個畫素取樣

次時，因為

是一個質數，所以分層模式只能是

$1 \times 17$

或

$17 \times 1$

，那麼，只在一個維度上能得到分層帶來的好處，而另一個維度上取樣的質量不能得到基本的保證。

2 拉丁超立方體取樣（Latin hypercube sampling）

拉丁超立方體取樣（Latin hypercube sampling，LHS）

可以在任意數量的維度上生成任意數量的樣本。

取樣

次時，LHS 把每個維度平均分成

個區域，然後在對角線上的

個區域中，每個區域單獨取樣得到一個樣本，最後在每個維度上把樣本隨機排序。

例如，在

$\left\{ \begin{array}{} x\in \left[0,\,1\right)\\y\in \left[0,\,1\right) \end{array} \right.$

之中取樣

次，LHS的步驟如下：

把

維等分成

$x\in \left[0,\,\frac{1}{5}\right)$

、

$x\in \left[\frac{1}{5},\,\frac{2}{5}\right)$

、

$\cdots$

、

$x\in \left[\frac{4}{5},\,1\right)$

這

份，把

維也等分成相應的

份；

在對角線區域的

$\left\{ \begin{array}{} x\in \left[0,\,\frac{1}{5}\right)\\y\in \left[0,\,\frac{1}{5}\right) \end{array} \right.$

、

$\left\{ \begin{array}{} x\in \left[\frac{1}{5},\,\frac{2}{5}\right)\\y\in \left[\frac{1}{5},\,\frac{2}{5}\right) \end{array} \right.$

、

$\cdots$

、

$\left\{ \begin{array}{} x\in \left[\frac{4}{5},\,1\right)\\y\in \left[\frac{4}{5},\,1\right) \end{array} \right.$

這

個區域之中，每個區域單獨取樣，分別得到樣本

$\left (x_0^{$

、

$\left (x_1^{$

、

$\cdots$

、

$\left (x_4^{$

；

在

維隨機排序樣本，得到

$\left (x_0,\,y_0^{$

、

$\left (x_1,\,y_1^{$

、

$\cdots$

、

$\left (x_4,\,y_4^{$

；

在

維隨機排序樣本，得到最終的

個樣本

$\left (x_0,\,y_0 \right )$

、

$\left (x_1,\,y_1 \right )$

、

$\cdots$

、

$\left (x_4,\,y_4 \right )$

；

使用 LHS 取樣

次生成多維樣本，相當於在每一維上分別進行分層取樣，再隨機排序。這樣一來，也避免了直接使用分層取樣時，可能出現的樣本在某一維度上聚集到區域性的情況。

需要注意的是，LHS 不一定會比分層取樣的效果更好。例如，LHS 生成樣本所在的子域在隨機排序前是在一條對角線上，如果運氣不好，在隨機排序後可能會在另一條對角線上。這樣的話，會有大塊區域內沒有樣本，導致效果比較糟糕。

3 霍爾頓取樣（Halton sampling）

霍爾頓取樣（Halton sampling）

使用一種確定的

低差異序列（low discrepancy sequence）

——霍爾頓序列（Halton squence）來生成樣本，屬於

擬蒙特卡羅方法（quasi-Monte Carlo method）

，與使用隨機數來解決問題的

蒙特卡羅法（Monte Carlo method）

相對應。

3.1 差異（discrepancy）

差異（discrepancy）

表示了取樣得到的樣本在樣本空間中的最大密度相對偏移。

若樣本空間

$\Omega$

的體積是

，取樣得到了

個樣本，樣本空間子域

$\Omega_i$

的體積是

，子域內有

個樣本，則樣本在該子域的密度相對偏移是

$\left|\frac{n_i}{N}-\frac{v_i}{V}\right|$

。於是，差異被定義為：

$D_{N}=\underset{\Omega_i}{\max}\left|\frac{n_i}{N}-\frac{v_i}{V}\right| \\$

可以看出，樣本在樣本空間內分佈得越均勻，則差異

越小。

霍爾頓序列的生成基於 radical inverse 運算。

3.2 radical inverse

對十進位制正整數

進行基數

的

radical inverse

運算

$\Phi_b(i)$

，可分為兩步：

把十進位制正整數

表示成

進位制數，

$(i)_{10}=(d_m \cdots d_1d_0)_b$

，其中

是各位上的數字，在

到

之間；

把表示成

進位制數的

以小數點為軸翻轉，便得到 radical inverse 的運算結果

$\Phi_b(i)=(0 . d_0 d_1 \cdots d_m)_b$

；

例如，計算

$\Phi_2(8)$

，先把

表示成二進位制，

$(8)_{10}=(1000)_2$

，然後把表示成二進位制的

翻轉，便得到

$\Phi_2\left(8\right)=\left(0.0001\right)_2=\left(\frac{1}{16}\right)_{10}$

。

可以看出，運算

$\Phi_b(i)$

把

對映到了

與

之間。

3.3 範德科普序列（Van der Corput sequence）

範德科普序列（Van der Corput sequence）

是一種簡單的一維低差異序列，它由

$\Phi_b(i)$

構成：

$\left\{\Phi_b(1),\,\Phi_b(2),\,\Phi_b(3),\,\cdots\right\} \\$

例如，基數

的範德科普序列

$\left\{\Phi_2(1),\,\Phi_2(2),\,\Phi_2(3),\,\cdots\right\}$

的生成過程如下表：

i（十進位制）

i（二進位制）

i 的基數為 2 的 radical inverse （二進位制）

i 的基數為 2 的 radical inverse （十進位制）

0。1

1/2

0。01

1/4

0。11

3/4

100

0。001

3/8

101

0。101

5/8

……

範德科普序列的差異

$D_N=O\left(\frac{\log N}{N}\right)$

，其中

是序列長度（樣本數量）；

可以看出，序列中第

個點落在最沒有被前

個點“覆蓋”到的區域。

一維的範德科普序列可以生成多維的霍爾頓序列。

3.4 霍爾頓序列（Halton squence）與哈默斯利序列（Hammersley squence）

霍爾頓序列（Halton squence）

又稱霍爾頓點（Halton points）。使用前

個質數作為

$\Phi_b()$

運算的基數，生成

個範德科普序列，共同構成了

維霍爾頓序列：

$\left(\Phi_2(i),\,\Phi_3(i),\,\Phi_5(i),\,\cdots\right) \\$

是樣本的索引；

維霍爾頓序列的差異

$D_N=O\left(\frac{\log^n N}{N}\right)$

，其中

是樣本數量（取樣次數）；

霍爾頓序列的維數不固定，可以根據它生成無窮個樣本，而如果取樣的次數是固定的，則可以使用差異

更小的

哈默斯利序列（Hammersley squence）

：

$\left(\frac{i}{N},\,\Phi_2(i),\,\Phi_3(i),\,\Phi_5(i),\,\cdots\right) \\$

是取樣次數，

是樣本的索引；

維哈默斯利序列的差異

$D_N=O\left(\frac{\log^{(n-1)} N}{N}\right)$

；

維霍爾頓序列生成的樣本在較高維度下會表現出明顯的規律。為了避免這種情況出現，可以在生成霍爾頓序列某一維的

$\Phi_b()$

運算後引入一個額外的加擾（scramble）操作，加擾後記為

$\Psi_b()$

。

一種加擾操作是把表示成

進位制數的

的每一位數字置換成另一個數字。例如，計算

$\Psi_7()$

，先把

$\left\{0,\,1,\,2,\,3,\,4,\,5,\,6\right\}$

隨機交換順序，得到

$\left\{5,\,1,\,6,\,2,\,3,\,4,\,0\right\}$

，然後在生成

$\Psi_{7}(1)$

、

$\Psi_{7}(2)$

、

$\Psi_{7}(3)$

等值時都依照此固定地置換

進位制數每一位的數字（

換成

、

還是

、……、

換成

）。其中，生成

$\Psi_{7}(10)$

的步驟如下：

把

$(10)_{10}$

表示成七進位制，得到

$(13)_{7}$

；

顛倒小數點之前的部分，得到

$(31)_{7}$

；

加擾，置換每一位，得到

$(21.555\cdots)_7$

，此處之所以得到一個無限迴圈小數，是因為加擾前

$(31.000\cdots)_{7}$

的小數點後實際上存在著無限個

；

最後，除以

，其中

是原本七進位制數的長度，此處

，即讓小數點左移兩位，得到

$\Psi_7(10)=(0.21555\cdots)_7$

$\Psi_b()$

中的

$\Phi_b()$

運算和之前介紹的有所差別，是為了處理加擾規則中

被置換成非

數字時的特殊情況。

4 泊松盤取樣（Poisson disk sampling）

泊松盤取樣（Poisson disk sampling）

得到的樣本是

藍噪聲樣本（blue noise samples）

。

根據傅立葉頻譜，可以把噪聲分為白噪聲、藍噪聲等類別。白噪聲擁有平坦的頻譜——在所有頻段上的能量都相等，常被用於生成隨機數。

藍噪聲（blue noise）

的頻譜中，低頻成分最少，且沒有集中的能量尖峰。

泊松盤取樣隨機地選取樣本位置，隨後檢查任何兩個樣本是否太近，最後得到的所有樣本排列緊密，但彼此之間的距離又不超過指定的最小距離，分佈均勻且隨機。

在任意維度下快速地進行泊松盤取樣的方法參見《Fast Poisson Disk Sampling in Arbitrary Dimensions》。

參考資料

《Physically Based Rendering： From Theory To Implementation》

低差異序列（一）- 常見序列的定義及性質 - 文刀秋二的文章 - 知乎

《Fast Poisson Disk Sampling in Arbitrary Dimensions》

小蜜蜂問答

小蜜蜂問答

分層取樣（stratified sampling）、霍爾頓取樣（Halton sampling）、泊松盤取樣（Poisson disk sampling）

推薦文章

小蜜蜂問答

小蜜蜂問答

分層取樣（stratified sampling）、霍爾頓取樣（Halton sampling）、泊松盤取樣（Poisson disk sampling）

相關文章

什麼叫實驗樣本？

c50砼1000方做多少組試塊？

串並變換 通訊原理？

明日之後護佑團隊天賦在哪裡？有何技巧？

推薦文章

串並變換通訊原理？