matlab低差异序列的图，低差异序列（⼀）-常见序列的定义及
性质
是啊，poison disk能⽣成低差异分布的样本。但不属于低差异序列。主要区别还是定义上不是deterministic的，所以之前提到的那些性质也都不满⾜了，⽽且⽣成的时候需要把所有⽣成过的样本储存起来。实现上也没法做到和这些序列⼀样那么⾼效，通常都要rejection sampling啥的。。
低差异序列(⼀)- 常见序列的定义及性质
⾼效的⽣成在⾼维空间分布均匀的随机数是在计算机程序中⾮常常见的组成部分。对于⼀切需要采样的算法来说，分布均匀的随机数就意味着更加优秀的样本分布。光线传递的模拟(渲染)基于蒙特卡洛积分(Monte Carlo Integration)，这个过程中采样⽆处不在，所以好的样本分布直接影响积分过程的收敛速度。与常见的伪随机数对⽐，低差异序列(Low Discrepancy Sequence)⾮常⼴泛的被⽤在图形，甚⾄于⾦融领域。它们除了在⾼维空间中的分布更加均匀以外还有许多其他的性质更利于渲染程序的执⾏。本⽂标题图⽚的左右两边分别⽤32个Sobol 序列和伪随机数作为样本分布渲染，可以看出左边的噪点⽐右边少许多。这篇专栏会介绍⼏种常见的低差异序列的定义(Van der Corput，Halton，Hammersley，Sobol，Rank-1 lattice)，下⼀篇专栏(低差异序列(⼆)- ⾼效实现以及应⽤ )则会专注于它们⾼效的实现，以及在渲染程序应⽤时候的⼀些问题。
什么是Discrepancy
⾸先说说这⾥均匀分布⾥的“均匀”指的是什么。⼀个直观的理解可以看下⾯的图⽚，左边为伪随机数组成的⼆维点集，右边则是由低差异序列点集的对整个空间的覆盖更加完整。
更加严谨的定义则要引⼊Discrepancy(Definition of Discrepancy)的概念
公式看的眼花缭乱，⽤普通话描述⼀下就是，对于⼀个在空间中的点集，任意选取⼀个空间中的区域，此区域内点的数量和点集个数的总量的⽐值和此区域的体积的差的绝对值的最⼤值，就是这个点集的Discrepancy。分布越均匀的点集，任意区域内的点集数量占点总数量的⽐例也会越接近于这个区
域的体积。
Radical Inversion与Van der Corput序列
接下来在介绍这些序列定义之前，先介绍⼀个基本的运算，Radical Inversion。这篇专栏将会介绍的所有序列都会⽤到这个运算过程。
这个操作⾮常直观，是⼀个正整数，则任何⼀个整数如果先将表⽰成进制的数，然后把得到的数中的每⼀个位上的数字排成⼀个向量，和⼀个⽣成矩阵(generator matrix)相乘得到⼀个新的向量，最后再把这个新向量中镜像到⼩数点右边去就能得到这个数以为底数，以为⽣成矩阵的radical inversion。
上⾯的描述可能略微有些复杂，但如果矩阵是单位矩阵(Identity Matrix)的时候，这个过程会简化很多，既是直接把这个进制的数镜像到⼩数点右边去即可。同时这也是Van der Corput序列的定义。
举个例⼦，正整数8以2为底数的radical inverse的计算过程如下。⾸先算出8的2进制表⽰，1000。此处假设为单位矩阵，所以直接将1000镜像到⼩数点右边，0.0001。这个⼆进制数的值就是最终结果，把它转换回10进制就得到1/16, 既。下⾯的表给出了更多的以2为底数的Van der Corput序列的例⼦。
Van der Corput序列有⼏个属性：1)每⼀个样本点都会落在当前已经有的点⾥“最没有被覆盖”的区域。例如是刚好落在了区间中被覆盖最少的区域()。2)样本个数到达个点时对 会形成uniform的划分。例如。3)很多时候并不能够代替伪随机数，因为点的位置和索引有很强的关系，例如在以2为底的Van der Corput序列中，索引为基数时候序列的值⼤于等于0.5，偶数时则⼩于0.5
Halton序列与Hammersley点集
介绍完Van der Corput之后，Halton和Hammersley就⾮常简单了。Halton和Hammersley可以⽣成在⽆穷维度上分布均匀的点集。它们都基于Van der Corput序列。
Halton序列的定义很简单：
既是每⼀个维度都是⼀个基于不同底数的Van der Corput序列，其中互为质数(例如第到第个质数)。
Hammersley点集的定义和Halton⾮常类似。
唯⼀不同的就是将第⼀个维度变成，其中为样本点的索引，为样本点集中点的个数。根据定义，Hammersley点集只能⽣成固定数⽬个样本，⽽Halton序列则可以⽣成⽆穷个样本(当然在计算机⾥我们只有有限的bit去表⽰有限个样本点)。
上⾯左边的图为第1-100个Halton序列中的⼆维的样本点，，右边则为数量为100的⼆维Hammersley样本点集，。可以看出来他们的分布都远⽐⼀般的伪随机数更加均匀。Hammersley的Discrepancy⽐Halton更稍低⼀些，但是代价是必须预先知道点的数量，并且⼀旦固定没法更改。虚幻引擎4中对环境贴图的Filter采样就是⽤的点集⼤⼩固定为1024的Hammersley点集。Halton虽然Discrepancy稍⾼但可以不受限制的⽣成⽆穷多个点，更适合于没有固定样本个数的应⽤，例如任何progressive或者adaptive的过程。
modulate基于radical inversion的序列还都具有Stratified样本的性质。因为每⼀个维度都是⼀个radical inversion，所以每⼀维度都具有所有之前提到的radical inversion的性质。其中之⼀就是点集个数到达个点时对 会形成uniform的划分。下图是第1-12个Halton序列的⼆维点集，可以看出点0-7在X轴的投影和0-8在Y轴的投影都是均匀覆盖。这也意味着在样本数量等于每个维度底数的公倍数的时候，样本会⾃然在每个维度上底数的倍数的strata中⾃然的形成stratified采样。例如下图中的第0-5个点，刚好在图中落在2x3的strata中。
Halton序列的⼀个缺点是，在⽤⼀些⽐较⼤的质数作为底数时，序列的分布在点的数量不那么多的时候并不会均匀的分布，只有当点的数量接近底数的幂的时候分布才会逐渐均匀。例如下图中以29和31为底的序列，⼀开始的点会分别是1/29,2/29,所以造成了点都集中落在了⼀条直线上⾯。解决这
个问题的⽅法也很简单，Scrambling。Scrambling的⽅法有许多种，例如最简单的XOR Scrambling适⽤于以2为底数的序列。对于Halton来说，⼀个⽐较常⽤的⽅法是Faure Scrambling。
如上⾯的公式所写，Faure Scrambling的做法就是在做radical inverse的时候不直接将数字镜像到⼩数点右边，⽽在镜像前先把每个数字通过⼀个permutation转换成另⼀个数字。不同的底数有不同的permutation。例如。⾄于如何具体计算这⾥不再展开，下⼀篇专栏在讲实现时会给出参考链接。这⾥值得⼀提的是Scrambling完全不会影响radical inversion序列分布的随机性，因为radical inversion会⾃然的将空间均等划分成底数的整数次幂个部分，scrambling本质上就是在交换这些均等划分的部分，所以Scrambled后的序列依然具有radical inversion的性质。
Sobol序列
与Halton和Hammersley不同，Sobol序列的每⼀个维度都是由底数为2的radical inversion组成，但每⼀个维度的radical inversion都有各⾃不同的矩阵。
因为完全以2为底数，所以Sobol序列的⽣成可以直接使⽤bit位操作实现radical inversion，⾮常⾼效。Sobol序列的分布具有不仅均匀，⽽且当样本的个数为2的整数次幂时，在区间中以2为底的每个Elementary Interval中都有且只会有⼀个点，这意味着它可以⽣成和Stratified Sampling和Latin Hypercube同样⾼质量分布的样本(见下图)，同时⼜不需要预先确定样本的数量或者将样本储存起来，并可以根据需要⽣成⽆限个样本，⾮常适合progressive的采样。这些性质也使得Sobol在需要⼀切对⾼维空间采样的应⽤中，例如图形，渲染以及⾦融领域，都⾮常流⾏，
因为Sobol序列需要⼀个⽣成矩阵，⽽且所有维度都以2为底，所以没有Halton那样在以⽐较⼤的数为
底时需要⽤Scrambling来消除分布间的correlation这个问题。那么如何计算出能⽣成如此⾼质量分布的矩阵呢？Quasi Monte Carlo的学者们已经花了数10年的时间搜索这种矩阵，现在我们可以在这个⽹页(Sobol sequence generator )到可以⽣成21201维度的Sobol序列的矩阵。
Rank-1 Lattices
最后再简单提⼀下Rank-1 Lattices。类似于Sobol序列，Rank-1 Lattices依赖于⼀个⽣成向量(Generator Vector)。⽣成向量的质量直接影响到最终样本的分布。给定⼀个⽣产向量后，产⽣⼀个点集的做法⾮常简单：
既每个样本都是⽤乘以⽣成向量，为样本的索引，为样本总数，得到的乘积如果⼤于1，则对1求余数(modulate)映射回范围。
这种做法类似Hammersley也只能⽤于预先知道样本数量并且样本数量固定的应⽤，如果需要可持续的⽣成⽆线个样本，也很简单，只需将换成⼀个radical inverse的序列即可：
<
这篇专栏⽂章介绍了⼏个常见低差异序列的定义以及性质，下⼀篇⽂章(低差异序列(⼆)- ⾼效实现以及应⽤ )会抛开理论着重谈它如何⾼效的实现它们，以及在图形程序中使⽤它们时会遇到的⼀些实际问题。
例如如何将有限的序列⽤于所有的像素，如何多线程并⾏，如何利⽤这些性质并结合到⼀些光线传递的算法中去。
编辑于 2015-12-05
计算机图形学
算法
蒙特卡洛⽅法
⽂章被以下专栏收录
Behind the Pixels
图形学爱好者的专栏。涉及内容包括⽤于电影特效的离线渲染技术，⽤于游戏的实时渲染技术，图形学相关的软件系统如游戏引擎、渲染器的开发以及优化，物理模拟，GPU开发技术等。
进⼊专栏
推荐阅读
低差异序列(⼆)- ⾼效实现以及应⽤
⽂⼑秋⼆发表于
⼿把⼿教你深度学习强⼤算法进⾏序列学习(附Python代码)
本⽂共3200字，建议阅读10分钟。 本⽂将教你使⽤做紧致预测树的算法来进⾏序列学习。 概述 序列学习是近年来深度学习的热点之⼀。从推荐系统到语⾳识别再到⾃然语⾔处理，它的潜⼒似乎⽆穷…
清华⼤学数据科学研究院
序列的算法(⼀·a)隐马尔可夫模型
DarkScope
天天算法 | Hard | 1.最长连续序列
Mark
12 条评论
写下你的评论...
葛亮昇2 年前
最近正好对pbrt和Mitsuba⾥⾯的低差异采样有点疑惑，⼤神的⽂章来的太及时了。希望下⼀篇能多讲⼀些Scrambling的内容。感谢⼤神~
HackerKO2 年前
⼤神
空明流转2 年前
POISON DISK 也算是低差异吧。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。