在本文中，我提出了一个新的低散度准随机序列，该序列比Sable，Niederreiter等现代序列有了显着改进。


图1.低散度的各种准随机序列的比较。 注意我提出的 $$$R$ -序列比所有其他方法创建的点分布更均匀。 此外，所有其他方法都需要仔细选择基本参数，如果选择不正确，则会导致简并性（例如，在右上方）

本文涵盖的主题

• 一维低散度序列
• 二维低散度方法
• 装箱距离
• 多类低差异集
• 球体表面上的准随机序列
• 准周期平铺
• 计算机图形学中的抖动蒙版

前一段时间，此帖子已发布在Hacker News主页上。 您可以在那里阅读他的讨论 。

简介：随机与准随机

在图1中，您可以注意到，通过对单位正方形内的点进行简单均匀的随机采样，可以观察到点的累积，并且还会出现没有点的区域（“白噪声”）。 低散度准随机序列是一种以确定性方式构造（无限）连续点的方法，该方法可以减少累积（散度）的可能性，同时确保整个空间的均匀覆盖（“蓝噪声”）。

一维拟随机序列

一般而言，很好地研究和解决了创建一维低散度的完全确定的准随机序列的方法。 在本文中，我将主要考虑开放（无限）序列，首先在一个维度上，然后再进入更高维度。 开放序列的基本优势（即可扩展 $$$n$ ）在于以下事实：如果基于有限数量的成员的总误差太大，则可以在不丢弃所有先前计算点的情况下扩展序列。 建立开放序列的方法有很多。 您可以通过构造其基本（超级）参数的方法将不同类型分为几类：

• 非理性分数：Kronecker，Richtmayer，Ramshaw
• （相互）素数：Van der Corpute，Holton，Foret
• 不可约多项式：Niederreiter
• 基本多项式：Sable

为了简洁起见，在本文中，我将主要比较新的加性递归 $$$R$ -属于第一类的序列，即基于无理数的递归方法（通常称为Kronecker， Weil或Richtmeier序列）和Holton序列，该无理数是秩为1的晶格，而Holton序列基于规范的一维van der Corpute序列。 Kronecker规范递归序列定义为：

$$

$$R_1（\ alpha）：\; \; t_n = \ {s_0 + n \ alpha \}，\ quad n = 1,2,3，...$$

在哪里 $$$\ alpha$ -任何非理性数字。 注意条目 $$$\ {x \}$ 表示小数部分 $$$x$ 。 在计算中，此函数通常表示为

$$

$$R_1（\ alpha）：\; \; t_n = s_0 + n \ alpha \; （\ textrm {mod} \; 1）; \ quad n = 1,2,3，...$$

在 $$$s_0 = 0$ 序列的前几个成员 $$$R（\ phi）$ 等于：

$$

$$t_n = 0.618，\; 0.236，\； 0.854，\； 0.472，\； 0.090，\； 0.708，\； 0.327，\； 0.944，\； 0.562，\； 0.180，\； 798; 416; \; 0.034，\； 0.652，\； 0.271，\； 0.888，...$$

重要的是要注意 $$$s_0$ 不会影响序列的一般特性，并且几乎在所有情况下都等于零。 但是，在计算期权时 $$$s \ neq 0$ 提供了额外的自由度，这通常是有用的。 如果 $$$s \ neq 0$ ，则该序列通常称为“移位晶格序列”。 尽管默认情况下 $$$s = 0$ 我认为该值应为标准的理论和实践考虑 $$$s = 1/2$ 。 价值 $$$\ alpha$ 如果可能，给出最小的差异 $$$\ alpha = 1 / \ phi$ 在哪里 $$$\ phi$ -这是黄金分割率。 那是

$$

$$\ phi \ equiv \ frac {\ sqrt {5} +1} {2} \ simeq 1.61803398875 ...;$$

有趣的是，还有无数其他值。 $$$\ alpha$ ，这也使我们能够获得最佳差异，并且它们都通过Mobius变换相互关联

$$

$$\ alpha’= \ frac {p \ alpha + q} {r \ alpha + s} \ quad \ textrm {对于所有整数} \; p，q，r，s \ quad \ textrm {such that} | ps-qr | = 1$$

现在，我们将该递归方法与众所周知的具有相反放电顺序的van der Korput序列进行比较[ van der Korput，1935年 ]。 Van der Corpute序列实际上是一个序列家族，每个序列都由唯一的超参数定义 $$$b$ 。 b = 2的序列的前几个成员相等：

$$

$$t_n ^ {[2]} = \ frac {1} {2}，\ frac {1} {4}，\ frac {3} {4}，\ frac {1} {8}，\ frac {5} {8}，\ frac {3} {8}，\ frac {7} {8}，\ frac {1} {16}，\ frac {9} {16}，\ frac {5} {16}，\ frac {13} {16}，\ frac {3} {16}，\ frac {11} {16}，\ frac {7} {16}，\ frac {15} {16}，...$$

在下一节中，我们将比较每个序列的一般特征和有效性。 考虑计算某个积分的问题

$$

$$A = \ int_0 ^ 1 f（x）\ textrm {d} x$$

我们可以将其近似为：

$$

$$A \ simeq A_n = \ frac {1} {n} \ sum_ {i = 1} ^ {n} f（x_i），\ quad x_i \在[0,1]$$

• 如果 $$$\ {x_i \}$ 相等 $$$i / n$ ，这是矩形的公式;
• 如果 $$$\ {x_i \}$ 随机选择，这就是蒙特卡罗方法 ； 但是
• 如果 $$$\ {x_i \}$ 是具有低散度的序列的元素，那么这就是准蒙特卡罗方法 。

下图显示了典型的误差曲线。 $$$s_n = | A-A_n |$ 近似与此函数相关的某个积分， $$$f（x）= \ textrm {exp}（\ frac {-x ^ 2} {2}），\; x \在[0,1] $$ 对于：（i）来自加性递归的准随机点，其中 $$$\ alpha = 1 / \ phi$ ，（蓝色）; （ii）van der Corput序列的准随机点（橙色）； （iii）随机选择的点（绿色）； （iv）黑貂序列（红色）。

这表明 $$$n = 10 ^ 6$ 随机抽样的点解会导致错误 $$$\ simeq 10 ^ {-4}$ ，van der Corput序列导致错误 $$$\ simeq 10 ^ {-6}$ ，而 $$$R（\ phi）$ -顺序导致错误 $$$\ simeq 10 ^ {-7}$ 那在 $$$\ sim$ 比van der Corput的误差好10倍 $$$\ sim$ 比（均匀）随机抽样好1000倍。


图2.使用各种准随机蒙特卡洛方法进行的一维数值积分的比较。 值越低越好。 新品 $$$R_2$ -序列（蓝色）和黑貂序列（红色）显然是最好的。

这里值得一提的是：

• 这对应于以下知识：均匀随机抽样的误差渐近地减小到 $$$1 / \ sqrt {n}$ ，并且两个准随机序列的误差都倾向于 $$$1 / n$ 。
• 的结果 $$$R_1（\ phi）$ -序列（蓝色）和黑貂序列（红色）是最好的。
• 该图表明，范德科珀特序列为集成任务提供了良好但令人难以置信的一致结果！
• 可以看出，对于所有值 $$$n$ 顺序 $$$R_1（\ phi）$ 比范德科普特序列产生更好的结果。

新序列 $$$R_1$ 是使用黄金比率的Kronecker序列，是一维拟随机蒙特卡洛积分方法（Quasirandom Monte Carlo，QMC）的最佳选择之一。

还值得注意的是，尽管 $$$\ alpha = \ phi$ 理论上提供了最佳的选择， $$$\ sqrt {2}$ 非常接近最佳值，以及几乎任何其他非理性值 $$$\ alpha$ 为一维集成提供了卓越的误差曲线。 这就是为什么它经常使用 $$$\ alpha = \ sqrt {p}$ 对于任何质数。 此外，从计算的角度来看，间隔中的选定随机值 $$$\ alpha \ in [0,1]$ （在机器精度的范围内）几乎可以肯定是一个无理数，因此对于低发散序列是一个不错的选择。 从视觉上看，上图未显示Niederreiter序列的结果，因为它们实际上与Sobol序列和 $$$R$ 。 本文中使用的Niederreiter和Sable序列（以及优化的参数选择）是在Mathematica中使用文档中所谓的“来自Intel MKL库的封闭式专有和完全优化的生成器”进行计算的。

二维准随机序列

在高维上构造低方差的大多数现代方法都简单地组合在一起（逐个分量） $$$d$ 一维序列。 为简便起见，在本文中，我们将主要考虑Holton序列[ Holton，1960 ]，Sable序列和 $$$d$ 维克罗内克序列。

Holton序列使用简单的方法构建 $$$d$ 各种一维范德科珀特序列，其基础对于其他所有序列都非常简单。 也就是说，它们是成对的互质数。 毫无疑问，由于其明显的简单性和逻辑性，最常见的选择是选择第一个 $$$d$ 质数。 由（2,3）Holton序列定义的前625个点的分布如图1所示。尽管许多二维Holton序列是具有低散度的出色序列来源，但众所周知，其中许多问题非常棘手且没有低散度。 例如，图3显示Holton（11,13）序列生成非常明显的线条。 致力于开发用于选择模型和问题对的方法。 $$$（p_1，p_2）$ 。 在更高的尺寸下，问题变得更加复杂。

当推广到更高的维度时，Kronecker递归方法会遇到更大的困难。 虽然使用 $$$\ alpha = \ sqrt {p}$ 创建了出色的一维序列，甚至很难找到可以用作无问题二维案例基础的素数对！ 建议使用其他众所周知的无理数作为解决方法，例如 $$$\ phi，\ pi，e，...$ 。 它们提供适度可接受的结果，但通常不使用，因为它们通常不如正确选择的Holton序列好。 为了解决这些退化问题，正在做出巨大的努力。

提出的解决方案使用跳过/刻录，跳跃/细化。 对于最终序列的编码（加扰），使用了另一种技术，通常用于克服该问题。 加扰不能用于创建低散度的开放（无限）序列。


图3.（11,13）-Holton序列显然不是低散度序列（左）。 它也不是累加递归（11,13）序列（在中间）。 一些使用众所周知的无理数的二维加性递归序列非常好（右）。

同样，尽管Sable序列的结果通常更好，但它的复杂性，更重要的是，需要非常仔细地选择超参数，这使其不太友好。

再一次，在 $$$d$ 尺寸：

• 典型的Kronecker序列需要选择 $$$d$ 线性独立的无理数；
• Holton序列要求 $$$d$ 互素的成对整数； 但是
• 黑貂序列需要选择 $$$d$ 指南编号。

新序列 $$$R_d$ -唯一的 $$$d$ 低散度的三维准随机序列，不需要选择基本参数。

黄金分割率的概括

tl; dr在这一部分中，我将讨论如何建立一个新的班级 $$$d$ 低散度的三维开放（无限）序列，不需要选择基本参数，具有低散度的优良特性。

有很多方法可以概括斐波那契数列和/或黄金分割率。 下面提出的概括黄金分割率的方法并不是新的方法[ Krchadinac，2005 ]。 另外，特征多项式与代数的许多领域有关，包括Perron数和Piso-Vijayaraghavan数 。 但是，这种广义形式与具有低散度的高维序列的构造之间的显式联系是新的。 我们定义黄金分割率的广义视图 $$$\ phi_d$ 作为独特的积极根源 $$$x ^ {d + 1} = x + 1$ 。 那就是

对于 $$$d = 1$ ， $$$\ phi_1 = 1.61803398874989484820458683436563 ...$ ，这是规范的黄金比例。

对于 $$$d = 2$ ， $$$\ phi_2 = 1.32471795724474602596090885447809 ...$ 。 该值通常称为塑性常数，并且具有漂亮的特性 （另请参见此处 ）。 假定该值对于相应的二维问题最有可能是最佳的[ Hensley，2002 ]。

对于 $$$d = 3$ ， $$$\ phi_3 = 1.220744084605759475361685349108831 ...$

对于 $$$d> 3$ ，尽管该方程的根不是封闭的代数形式，但我们可以通过标准方法（例如牛顿法）或通过注意以下序列来轻松获得数值近似 $$$R_d（\ phi_d）$ ：

$$

$$t_0 = t_1 = ... = t_ {d} = 1;$$

$$

$$t_ {n + d + 1} \; = \; t_ {n + 1} + t_n，\ quad \ textrm {for} \; n = 1,2,3，..$$

这个特定的常数序列 $$$\ phi_d$ 1928年，建筑师和尚汉斯·范·德·兰（Hans van de Laan）将其命名为“ 谐波数 ”。 这些特殊含义可以非常优雅地表达如下：

$$

$$\ phi_1 = \ sqrt {1+ \ sqrt {1+ \ sqrt {1+ \ sqrt {1+ \ sqrt {1 + ...}}}}}$$

$$

$$\ phi_2 = \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1 + ...}}}}}$$

$$

$$\ phi_3 = \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1 + ...}}}}}$$

我们还具有以下非常优雅的属性：

$$

$$\ phi_d = \ lim_ {n \ to \ infty} \; \; \ frac {t_ {n + 1}} {t_n}$$

这个序列有时被称为广义斐波纳契数列或递延斐波那契数列，已经进行了相当深入的研究[ As，2004 ， Wilson，1993 ]， $$$d = 2$ 通常称为Padovan序列[ Stuart，1996 ， OEIS A000931 ]，该序列 $$$d = 3$ 在[ OEIS A079398 ]中列出。 如上所述，这篇文章的主要任务是描述广义序列与构造之间的明确联系。 $$$d$ 低散度的三维序列。

主要结果：以下非参数 $$$d$ 维开放（无限）序列 $$$R_d（\ phi_d）$ 与其他现有方法相比，具有出色的低差异特性。

$$

$$\ mathbf {t} _n = \ {n \ pmb {\ alpha} \}，\ quad n = 1,2,3，...$$

$$

$$\ textrm {where} \ quad \ pmb {\ alpha} =（\ frac {1} {\ phi_d}，\ frac {1} {\ phi_d ^ 2}，\ frac {1} {\ phi_d ^ 3}， ... \ frac {1} {\ phi_d ^ d}）$$

$$

$$\ textrm {和} \; \ phi_d \ \ textrm {是唯一的正根} x ^ {d + 1} = x + 1$$

对于二维，此广义序列为 $$$n = 150$ 如图1所示。这些点显然在 $$$R_2$ -序列比（2，3）-Holton序列，Kronecker序列基于 $$$（\ sqrt {3}，\ sqrt {7}）$ ，Niederreiter和Sable序列。 （由于Niederreiter和Sable序列的复杂性，它们是使用Intel提供的专有代码在Mathematica中进行计算的。）这是基向量的序列类型 $$$\ pmb {\ alpha}$ 是单个物质值的函数，通常称为Korobov序列[Korobov，1959年]

再次查看图1，比较各种二维，低散度的准随机序列。

代码和演示

在一维中，伪代码用于 $$$n$ 成员（ $$$n$ = 1,2,3，....）定义为

 g = 1.6180339887498948482 a1 = 1.0/g x[n] = (0.5+a1*n) %1 

在二维中，坐标的伪代码 $$$x$ 和 $$$y$$$$n$ 成员（ $$$n$ = 1,2,3，....）定义为

 g = 1.32471795724474602596 a1 = 1.0/g a2 = 1.0/(g*g) x[n] = (0.5+a1*n) %1 y[n] = (0.5+a2*n) %1 

三维伪代码的坐标 $$$x$ ， $$$y$ 和 $$$z$$$$n$ 成员（ $$$n$ = 1,2,3，....）定义为

 g = 1.22074408460575947536 a1 = 1.0/g a2 = 1.0/(g*g) a3 = 1.0/(g*g*g) x[n] = (0.5+a1*n) %1 y[n] = (0.5+a2*n) %1 z[n] = (0.5+a3*n) %1 

Python代码模板。 （请注意，Python数组和循环从头开始！）

 import numpy as np # Using the above nested radical formula for g=phi_d # or you could just hard-code it. # phi(1) = 1.61803398874989484820458683436563 # phi(2) = 1.32471795724474602596090885447809 def phi(d): x=2.0000 for i in range(10): x = pow(1+x,1/(d+1)) return x 

 # Number of dimensions. d=2 # number of required points n=50 g = phi(d) alpha = np.zeros(d) for j in range(d): alpha[j] = pow(1/g,j+1) %1 z = np.zeros((n, d)) # This number can be any real number. # Common default setting is typically seed=0 # But seed = 0.5 is generally better. for i in range(n): z[i] = (seed + alpha*(i+1)) %1 print(z) 

我写的代码与本文中使用的数学符号相对应。 但是，出于编程约定和/或效率的原因，有些修改值得一提。 首先，由于 $$$R_2$ 是加性递归序列，替代公式 $$$z$ 不需要浮点乘法，并且在很大的范围内保持高精度 $$$n$ 具有形式

 z[i+1] = (z[i]+alpha) %1 

其次，在可以向量化的语言中，分数函数的代码可以向量化如下：

 for i in range(n): z[i] = seed + alpha*(i+1) z = z %1 

最后，我们可以通过将所有常量乘以来替换浮点数和整数的这些加法。 $$$2 ^ {32}$ ，然后相应地更改frac（。）函数。 以下是其他人根据此顺序创建的源代码演示：

• beta.observablehq.com/@jrus/plastic-sequence ，由Jake Rus开发：
• www.shadertoy.com/view/4dtBWH ，开发人员@ Stirners Host （XGKICK）：

最小包装距离

新品 $$$R_2$ -sequence是仅有的二维低散度准随机序列，其中最小堆积距离仅减小为 $$$1 / \ sqrt {n}$ 。

尽管差异计算的标准技术分析是为了评估 $$$d ^ *$ -差异，我们将首先提到几种其他的几何方法（也许更直观！），以证明新序列比其他标准方法更可取。 如果我们表示点之间的距离 $$$我$ 和 $$$j$ 为 $$$d_ {ij}$ 和 $$$d_0 = \ textrm {inf} \; d_ {ij}$ 然后下图显示了它如何变化 $$$d_0（n）$ 为 $$$R$ -序列，（2,3）-Holton，Sable，Niederreiter序列和随机序列。 如图6所示。

如上图所示，最小距离值通过系数归一化 $$$1 / \ sqrt {n}$ 。 您可能会注意到 $$$n = 300$ 随机序列中的两个点（绿色）几乎可以肯定出现了两个彼此非常接近的点。 还可以看出，尽管Holton（2,3）序列比随机抽样好得多，但不幸的是，它的渐近性也减小到零。 对于Sable序列，归一化的原因降至零 $$$d_0$ 在于Sable自己表明Sable序列以一定速度下降 $$$/ n$ -不错，但显然比这差得多 $$$R_2$ 仅减少 $$$1 / \ sqrt {n}$ 。

对于序列 $$$R（\ phi_2）$ （蓝色）两点之间的最小距离不断落入 $$$0.549 / \ sqrt {n}$ 之前 $$$0.868 / \ sqrt {n}$ 。 请注意，最佳直径0.868对应于59.2％的堆积系数。 将此与其他圆圈包装进行比较。

另请注意， Bridson Poisson光盘采样 无法扩展到 $$$n$ 并且通常默认情况下建议使用，它仍然会产生49.4％的打包系数。 值得考虑的是 $$$d_0$ 紧密结合序列 $$$\ phi_d$ 低差异，具有近似差的数字/向量 $$$d$ 测量[ Hensley，2001 ]。 尽管我们对二维近似差的数字知之甚少， $$$\ phi_d$ 可以使我们以更高的维度重新看待可近似的数字。


图4.低散度的各种序列的最小成对距离。 注意 $$$R_2$ -顺序（蓝色）始终是最佳选择； 另外，这是唯一的序列，其中归一化的距离不会趋于零 $$$n \ rightarrow \ infty$ 。 Holton的序列（橙色）排在第二位，Sable（绿色）和Niederreiter（红色）序列虽然不太好，但仍然比随机（紫色）好得多。 越大越好，因为这对应于更长的包装距离。

Voronoi图

可视化点的均匀分布的另一种方法是从第一个创建Voronoi图 $$$n$ 二维序列的点，每个区域的后续着色取决于其区域 。 下图显示了（i）的Voronoi颜色图表 $$$R_2$ -序列； （ii）（2,3）Holton序列，（iii）主递归； （iv）简单随机抽样。 对于所有数字，使用相同的色标。 再一次，很明显 $$$R_2$ 与Holton序列或简单随机抽样相比，该序列提供的分布更加均匀。 图片与上面相同，只是根据每个Voronoi单元中的顶点数进行了着色。 在这里不仅显而易见 $$$R$ -与Holton或简单随机抽样相比，序列提供了更均匀的分布，但关键值更引人注目 $$$n$ 仅由六边形组成！ 如果我们考虑广义斐波那契数列，那么 $$$A_1 = A_2 = A_3 = 1; \ quad A_ {n + 3} = A_ {n + 1} + A {n}$ 。 那是 $$$A_n$ ：

$$$$ display $$ \ begin {array} {r} 1＆1＆1＆2＆2＆3＆4＆5＆7 \\ 9＆\ textbf {12}＆16＆21＆28＆37＆\ textbf {49}＆65＆86 \\ 114＆\ textbf {151 }＆200＆265＆351＆465＆\ textbf {616}＆816＆1081 \\ 1432＆\ textbf {1897}＆2513＆3329＆4410＆5842＆\ textbf {7739}＆10252＆13581 \\ 17991＆\ textbf {23833}＆31572＆41824＆55405＆7 {97229}＆128801＆170625 \\ 226030＆\ textbf {299426}＆396655＆525456＆696081＆922111＆\ textbf {1221537}＆1618192＆2143648 \\ \ end {array} $$显示$$

其中的所有值 $$$n = A_ {9k-2}$ 或 $$$n = A_ {9k + 2}$ 仅由六边形组成。


图4.根据（i）的每个Voronoi多边形的面积可视化Voronoi图的形状 $$$R_2$ -序列； （ii）（2,3）-基于质数的序列； （iii）Holton的（2,3）序列；（iv）Niederraiter； （v）黑貂； （iv）简单随机抽样。 颜色表示每个Voronoi多边形的边数。 我再说一遍：很明显 $$$R（\ phi）$ -序列提供的分布比任何其他具有低散度的序列要均匀得多。

在某些值 $$$n$ Voronoi网格 $$$R_2$ -序列仅包含六边形。

图5.根据（i）的每个Voronoi多边形的边数，可视化Voronoi图的形状 $$$R_2$ -序列； （ii）（2,3）-基于质数的序列； （iii）Holton的（2,3）序列；（iv）Niederraiter； （v）黑貂； （iv）简单随机抽样。 颜色表示每个Voronoi多边形的边数。 我再说一遍：很明显 $$$R（\ phi）$ -序列提供的分布比任何其他具有低散度的序列要均匀得多。

Delaunay准随机平铺

$$$R$ -sequence是唯一可用于创建的低散度准随机序列 $$$d$ 使用其Delaunay网格进行三维拟周期性平铺。

与沃罗诺伊伯爵（Count Voronoi）相似的Delaunay三角剖分提供了机会以不同的方式看待这些分布。 但是，更重要的是，Delaunay三角剖分提供了一种用于创建平面的准周期性平铺（马赛克平铺）的新方法。 德劳内三角剖分 $$$R_2$ -序列提供比Holton序列或随机采样更为均匀的模式。 特别是，如果执行点分布的Delaunay三角剖分，则 $$$n$ 等于任何广义斐波那契数列： $$$A_N = $ 1,1,1,2,3,4,5,7,9,12,16,21,28,37，...$ ，那么Delaunay三角剖分仅由三个相同成对的三角形组成，即平行四边形（菱形）！ （除了具有共同顶点且具有凸包的三角形。）此外，

在值 $$$n = A_k$ Delaunay三角剖分 $$$R_2$ -序列形成准周期性平铺，每个平铺仅由三个基本三角形（红色，黄色，蓝色）组成，它们始终成对连接，并通过三个平行四边形（菱形）形成平面的定义明确的准周期性平铺（平铺）。

图6.（i）的Delaunay三角剖分的可视化 $$$R（\ phi_2）$ -序列； （ii）（2,3）Holton序列，（iii）主递归； （iv）简单随机抽样。 颜色表示每个三角形的面积。 所有四个图使用相同的比例。 再一次，很明显 $$$R（\ phi_2）$ -序列提供的分布比任何其他具有低散度的序列要均匀得多。
注意 $$$R_2$ 根据 $$$\ phi_2 = 1.32471795724474602596$ 是最少的piso，（ $$$\ phi = 1.61803 ...$ 是最大数量的皮索）。 准周期性平铺与Piso的二次方和三次方之间的联系并不是新的[ Elkharrat and Masakova]，但我相信，第一次准正交平铺是基于 $$$\ phi_2 = 1.324719 ...$ 。

下面的动画演示了Delaunay网格如何进行序列化 $$$R_2$ 随着积分的逐渐增加而变化。 请注意，当点数等于广义斐波那契数列的成员时，则整个Delaunay网格仅由红色，蓝色和黄色平行四边形（菱形）组成，以双拟周期形式排列。


图7

尽管红色平行四边形的排列显示出相当大的规律性，但人们可以清楚地看到蓝色和黄色平行四边形以准周期形式放置。 可以在图11中看到该晶格的傅立叶光谱；它表示经典的点光谱。 （请注意，基于质数的递归序列在它是有序的非重复模式的意义上也似乎是拟周期的。但是，在区间 $$$n$ 并不是那么恒定，而且还关键取决于基本参数的选择。 因此，我们将仅关注序列的准周期性平铺 $$$R_2$ 。）它仅由三个三角形组成：红色，黄色，蓝色。 请注意，按此顺序 $$$R（\ phi_2）$ 每种颜色的所有平行四边形具有相同的大小和形状。 这些单独的三角形的纵横比非常优雅。 即

$$

$$\ textrm {面积（红色）：面积（黄色）：面积（蓝色）} = 1：\ phi_2：\ phi_2 ^ 2$$

三角形的相对频率也相同：

$$

$$f（\ textrm {红色}）：f（\ textrm {黄色}）：f（\ textrm {蓝色}）= 1：\ phi_2：1$$

由此可见，空间中这三个三角形所覆盖的总相对面积为：

$$

$$f（\ textrm {红色}）：f（\ textrm {黄色}）：f（\ textrm {蓝色}）= 1：\ phi_2 ^ 2：\ phi_2 ^ 2$$

还可以假设我们可以通过基于序列A的替换来创建此准周期平铺。

$$

$$A \右箭头B; \ quad B \ rightarrow C; \ Quad C \ rightarrow BA$$

对于三个维度，如果我们考虑广义斐波那契数列，则 $$$B_1 = B_2 = B_3 = B_4 = 1; \ quad B_ {n + 4} = B_ {n + 1} + B {n}$ 。 那是

$$

$$B_n = \ {1,1,1,1,2,2,2,3,4,4,5,7,8,9,12,15,17,21,27,32,38,48,59 ，70,86,107,129，...$$

在某些值 $$$n = B_k$ 与序列关联的3D Delaunay网格 $$$R_3$ 定义准周期晶格。

离散包装，第2部分

下图显示了第一个 $$$n = 2500$ 每个具有低散度的二维序列的点。 此外，每个单元格50×50 = 2500仅在其正好包含1个点的情况下才涂成绿色。 也就是说，绿色方块越多，则2500个单元中2500个点的分布越均匀。 每个图的绿色单元格百分比如下： $$$R_2$ （75％），霍尔顿（54％），克罗内克（48％），尼德赖特（54％），黑貂（49％）和随机（38％）。

声波

只是出于娱乐目的，应News Hacker读者的请求，我模拟了所有这些准随机点分布的声音 ！ 我使用了Mathematica的Listplay函数：“ ListPlay [{a1，a2，...}]创建了一个对象，该对象将自身再现为声音，其振幅以一系列的水平给出。” 因此，在不加任何评论的情况下，我将让您自己决定一维准随机分布（单声道）和二维准随机分布（立体声）中最喜欢哪一个。

	单声道	立体声
随机的	http://extremelearning.com.au/wp-content/uploads/2018/04/random_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/random_2D.mp3
黑貂	http://extremelearning.com.au/wp-content/uploads/2018/04/Sobol_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Sobol_2D.mp3
Niederreiter	http://extremelearning.com.au/wp-content/uploads/2018/04/Nied_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Nied_2D.mp3
霍尔顿	http://extremelearning.com.au/wp-content/uploads/2018/04/Halton_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Halton_2D.mp3
克罗内克	http://extremelearning.com.au/wp-content/uploads/2018/04/Kronecker_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Kronecker_2D.mp3
[R	http://extremelearning.com.au/wp-content/uploads/2018/04/R1_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/R2_2D.mp3

多类低差异集

一些低散度序列证明了所谓的“多类低散度”。 在此之前，我们假设当我们需要尽可能均匀地分配时 $$$n$ 点，那么所有点都是相同的，并且彼此无法区分。 但是，在许多情况下，存在不同类型的点。 我们考虑均匀分布的问题 $$$n$ 这样，不仅所有点都均匀分布，而且同一类的点也一样。 特别是，假设有 $$$n_k$ 类型点 $$$k$ ，（其中 $$$n_1 + n_2 + n_3 + ... + n_k = n$ ），则具有低分布的多重集的分布是每个 $$$n_k$ 点数均匀分布。 在我们的案例中，我们发现 $$$R$ -Holton序列和序列很容易适应低散度的多集序列，只需将每种类型的点交替放置即可。

下图显示了它们的分布方式 $$$n = 150$ 点，蓝色为75，辣椒为40，绿色为25，红色为10。 对于加性递归序列，这很容易解决：前75个成员仅对应于蓝色，接下来的40个对应于橙色，接下来的25个对应于绿色，最后的10个对应于红色点。 该技术几乎适用于Holton和Kronecker序列，但在Niederreiter和Sable序列中的表现非常差。 此外，还没有已知的技术可以连续生成Niederreiter和Sable序列中的多尺度点分布。 这表明，现在可以使用低散度的序列直接描述和构建多类点的分布 ，例如鸡眼 。

顺序 $$$R_2$ 是低散度准随机序列，可轻松构造多类低散度。

图9.低散度的多尺度序列。 按顺序 $$$R$ 不仅所有点均匀分布，而且每种颜色的点也一样。

球面上的拟随机点

在计算机图形学和物理学领域中，经常需要将点尽可能均匀地分布在三维球体的表面上。 当使用开放（无限）准随机序列时，此问题仅通过使用Lambert等投影将准随机点均匀地分布在球体表面的单位正方形中而减少。 Lambert标准投影变换放置点 $$$（u，v）\在U [0,1] \到（x，y，z）\在S ^ 2$ 具有以下形式：

$$

$$（x，y，z）=（\ cos \ lambda \ cos \ phi，\ cos \ lambda \ sin \ phi，\ sin \ lambda）$$

$$

$$\ textrm {where} \ quad \ cos（\ lambda-\ pi / 2）=（2u-1）; \ quad \ phi = 2 \ pi v$$

由于这 $$$\ phi_2$ -序列是完全开放的，它使您可以将无限的点序列捕捉到球体的表面，一次捕捉一个点。 这与其他方法（例如斐波那契螺旋线的晶格）形成对比，后者需要提前知道点数。 通过目视检查，我们可以再次清楚地看到 $$$n = 1200$ 新的 $$$R（\ phi_2）$ -序列的分布比Holton覆盖或Kronecker采样要好得多，后者比随机采样要均匀得多。


图10

计算机图形抖动

大多数现代抖动技术（例如，Floyd-Steinberg抖动）都是基于误差分布的，它不太适合于GPU中的并行处理和/或直接优化。 在这种情况下，使用静态抖动遮罩进行点抖动（即完全取决于目标图像）会显示出出色的性能特征。 可能最著名和使用最广泛的抖动蒙版是基于拜耳矩阵的，但较新的蒙版则尝试更接近地模拟蓝噪声的特性。 基于低发散序列和/或蓝噪声创建抖动蒙版的主要困难在于，这些低发散序列投影一个整数 $$$Z$ 到间隔中的二维点 $$$[0,1)^2$ 。 但是对于抖动蒙版，需要一个函数，该函数将光栅化蒙版的二维整数坐标投影为间隔中的实际亮度/阈值 $$$[0,1)$ 。 我建议基于以下方法 $$$R$-序列。对于蒙版中的每个像素（x，y），我们分配其亮度值$$$I(x,y)$ 其中：

$$

$$I(x,y) = \alpha_1 x + \alpha_2 y \; ( \textrm{mod} 1);$$

$$

$$\textrm{} \quad \pmb{\alpha} =(\alpha_1,\alpha_2) = (\frac{1}{\phi_2}, \frac{1}{\phi_2^2})$$

$$

$$\textrm{} \; \phi_2\ \textrm{ - } x^3\;=x+1$$

那是 $$$x = 1.32471795724474602596…$ ，这意味着

$$

$$\alpha_1 = 0.75487766624669276; \alpha_2 = 0.569840290998$$

此外，如果添加了三角波函数以消除由每个整数边界上的frac（。）函数引起的不连续性：

$$

$$T(z) =\begin{cases} 2z, & \text{if } 0\leq z <1/2 \\ 2-2z, & \text{if} 1/2 \leq z < 1 \end{cases}$$

$$

$$I(x,y) = T \left[ \alpha_1 x + \alpha_2 y \; ( \textrm{mod} 1) \right];$$

然后进一步改善蒙版及其傅里叶/频率图。我们还注意到，由于

$$

$$\lim_{n \rightarrow \infty} \frac{A_n}{A_{n+1}} = 0.754878 ; \quad \lim_{n \rightarrow \infty} \frac{A_n}{A_{n+2}} = 0.56984$$

则上述表达式的形式与以下等式相关

$$

$$A_n x + A_{n+1} y \; (\textrm{mod} A_{n+2}) \textrm{ for integers } \;\; x,y$$

抖动R蒙版可产生与基于蓝噪声蒙版的现代方法相抗衡的结果。但是，与蓝噪声蒙版不同，它们无需预先计算，因为它们可以实时计算。

值得注意的是，这种结构也是由Mittring提出的，但是他凭经验找到了系数（并且没有再现最终值）。此外，它有助于理解为什么乔治·希门尼斯（Jorge Jimenez）用来创建“使命召唤”（通常称为“交错渐变噪声”）的经验公式如此有效。

$$

$$I(x,y) = (\textrm{FractionalPart}[52.9829189*\textrm{FractionalPart}[0.06711056*x + 0.00583715*y]]$$

但是，它需要3个浮点乘法和2％1运算符，并且先前的公式显示我们可以仅使用2个浮点乘法和1％1运算就可以做到这一点。但更重要的是，这篇文章对为什么这种形式的抖动遮罩如此有效（即使不是最佳选择）如此有效提供了更清晰的数学理解。下面以经典的Lena 256×256测试图像以及国际象棋测试图案为例，显示了该抖动矩阵的结果。它还显示了使用标准拜耳抖动蒙版的结果，以及一个带有蓝噪声的示例。两种最常见的蓝噪声方法是“虚空聚类”和泊松圆盘采样。为简便起见，我仅显示了“虚空和聚类”方法的结果。 [ 彼得斯]。交错的梯度噪声比Bayer和蓝色噪声更好，但不如$$$R$抖动。您会看到拜耳抖动在浅灰色区域显示出明显的白色不谐调。抖动$$$R$-顺序和蓝噪声通常是可比较的，尽管可以做出很小的差异。值得注意的是R抖动的一些方面：

• 他不是各向同性的！傅立叶光谱仅显示单个点和离散点。这是准周期性平铺和准晶体衍射光谱的经典特征。特别是，$$$R$ -掩码对应于这样的事实，即规范R序列的Delaunay三角剖分由三个平行四边形的准周期性平铺组成。
• 与三角波结合使用时，R抖动提供了难以置信的均匀蒙版！
• R- , .
• , , R- , .
• $$$(I(x,y)$ , .

图11.从左到右：（i）原始图像（ii）结合了三角波功能的R序列；（iii）R序列是分开的；（iv）蓝噪声抖动蒙版；以及（v）标准拜耳。R序列抖动蒙版与其他现代蒙版相比具有相当的竞争力。请注意，R2在Lena的脸部和肩膀上显示出最佳质量。此外，与蓝噪声掩膜不同，抖动R掩膜非常简单，无需进行初步计算。

更高尺寸

与上一节类似，但进行五（5）次测量时，下图显示了任意两点之间的（全局）最小距离 $$$R(\phi_5)$-序列，（2,3,5,7,11）-Holton序列和随机序列。这次，最小距离的归一化值被一个因子归一化$$$1/ \sqrt[5]{n}$ 。 您会看到，由于“维数的诅咒”，随机分布比所有具有低散度的序列要好-除了 $$$R_5$-序列。在$$$R(\phi_5)$ -序列甚至 $$$n \simeq 10^6$ 点，两点之间的最小距离仍在不断接近 $$$0.8/\sqrt{n}$ 总是更高 $$$0.631/\sqrt{n}$ 。

顺序 $$$R_2$ -唯一的 $$$d$ 低散度的三维序列，其中包装距离仅随着速度而开始下降 $$$n^{-1/d}$ 。

图12.这表明R序列（蓝色）始终优于Holton（橙色）；黑貂（绿色）；Niederreiter（红色）；和随机（紫色）。请记住，越大越好，因为这对应于更长的包装距离。

数值积分

下图显示了典型的误差曲线。 $$$s_n = |A-A_n|$ 近似与半角高斯函数相关的某个积分 $$$\sigma = \sqrt{d}$ ， $$$f(x) = \textrm{exp}(\frac{-x^2}{2d}), \; x \in [0,1]$ ，而：（i） $$$R_{\phi}$（蓝色）; （ii）Holton序列（橙色）；（iii）随机（绿色）；（iv）黑貂（红色）。该图显示了$$$n=10^6$现在，随机采样和Holton序列之间的差异变小了。但是，如一维情况所示，$$$R$-Sequence和Sable总是比Holton的序列更好。这也让我们知道Sable的顺序要好一些。$$$R$ -序列。


图13. 8维积分的蒙特卡罗准随机方法。值越低越好。新的R序列和Sable序列显示出比Holton序列更好的自我。