Scrambled后的序列依然具有radical inversion的性质

2021-09-26 17:48:41 浏览数 (2)

原文中陈述了很多具体的例子,而缺乏了一些Halton序列本身的说明,使用场景、以及与其他序列使用对比的差异,故在此处进行补充

HaltonHammersley可以生成在无穷维度上分布均匀的点集,它们都基于Van der Corput序列 Halton序列的定义很简单:

Xi:=(Φb1(i),...,Φbn(i))Xi:=(Φb1(i),...,Φbn(i))

既是每一个维度都是一个基于不同底数bnbn的Van der Corput序列,其中b1...bnb1...bn互为质数(例如第11到第nn个质数) Hammersley点集的定义和Halton非常相似 以下是Hammersley点集的定义

Xi:=(iN,Φb1(i),...,Φbn−1(i))Xi:=(iN,Φb1(i),...,Φbn−1(i))

唯一不同的就是把第一个维度变成iNiN,其中ii为样本点的索引,NN为样本点集中点的个数。根据定义,Hammersley点集只能生成固定数目个样本,而Halton序列则可以生成无穷个样本(当然在计算机里我们只有有限的bit去表示有限个样本点)

上面左边的图为第1-100个Halton序列中的二维的样本点,(Φ2(i),Φ3(i))99i=0(Φ2(i),Φ3(i))i=099,右边则为数量为100的二维Hammersley样本点集,(i100,Φ2(i))99i=0(i100,Φ2(i))i=099。可以看出来它们的分布都远比一般的伪随机数更加均匀。Hammersley的差异性比Halton更稍低一些,但是代价是必须预先知道点的数量,并且一旦固定无法更改虚幻引擎4中对环境贴图的Filter采样就是用的点集大小固定为1024的Hammersley点集。Halton虽然差异性稍高,但可以不受限制的生成无穷多个点,更适合于没有固定样本个数的应用,例如任何progressive或者adaptive的过程。 基于radical inversion的序列还都具有Stratified样本的性质。因为每一个维度都是一个radical inversion,所以每一维度都具有所有之前提到的radical inversion的性质。其中之一就是点集个数到达bmbm个点时对[0,1)[0,1)会形成uniform的划分。下图是第1-12个Halton序列的二维点集,可以看出点0-7在X轴的投影和0-8在Y轴的投影都是均匀覆盖。这也意味着在样本数量等于每个维度底数的公倍数的适合,样本会自然在每个维度上底数的倍数的strata中自然的形成stratified采样。例如下图中的第0-5个点,刚好在图中落在2x3的strata中。

`Halton`序列的一个缺点是,在用一些比较大的质数作为底数时,序列的分布在点的数量不那么多的时候并不会均匀的分布,只有当点的数量接近底数的幂的时候分布才会逐渐均匀。例如下图中以29和31为底的序列,一开始的点会分别是

129,229,329...129,229,329...所以造成了点都集中落在了一条直线上面。解决这个问题的方法也很简单,Scrambling。Scrambling的方法有许多种,例如最简单的XOR Scrambling适用于以2为底数的序列。对于Halton来说,一个比较常用的方法是Faure Scrambling

Φb(i)=∑l=0M−1σb(al(i))b−l−1Φb(i)=∑l=0M−1σb(al(i))b−l−1

如上面的公式所写,Faure Scrambling的做法就是在做radical inverse的时候不直接将数字镜像到小数点右边,而在镜像前先把每个数字通过一个permutationσbσb转换成另一个数字。不同的底数bb有不同的permutationσσ。例如σ4=[0,2,1,3]σ4=[0,2,1,3]。至于σbσb如何具体计算这里不再展开,下一篇专栏在讲实现时会给出参考链接。这里值得一提的时Scrambling完全不会影响radical inversion序列分布的随机性,因为radical inversion会自然的将空间均等划分成底数bb的整数次幂个部分,scrambling本质上就是在交换这些均等划分的部分,所以Scrambled后的序列依然具有radical inversion的性质。

0 人点赞