一、前言

        在文：低差异序列：范德科皮特序列（Van der Corput sequence）中提到范德科皮特序列是低差异序列。

        本文讲用 van der Corput sequences序列构建高维度的低差异序列Halton sequence，以及使用方法。

二、基本概念

        在数学中，低差异序列是具有以下性质的序列：对于 N 的所有值，其子序列 x1，...，xN 具有低差异。

        粗略地说，如果序列中落入任意集合 B 的点的比例接近于与 B 的度量成比例，则序列的差异很小，这在平均情况下会发生（但不是针对特定样本）一个等分布的序列。关于 B 的选择（超球体、超立方体等）以及如何计算每个 B 的差异（通常是标准化）和组合（通常采用最差值），差异的具体定义有所不同。

        低差异序列也称为准随机序列，因为它们通常用作均匀分布随机数的替代品。 “准”修饰符用于更清楚地表示低差异序列的值既不是随机也不是伪随机，但此类序列共享随机变量的某些属性，并且在某些应用中，例如准蒙特卡罗方法，它们的差异较小是一个重要的优势。

低差异序列可以用下图理解：

三、Halton sequence序列

        

        Halton 序列是根据使用互质数作为其基础的确定性方法构建的。举个简单的例子，让我们假设 Halton 序列的一个维度基于 2，而另一个基于 3。要生成 2 的序列，我们首先将区间 (0,1) 分成两半，然后再分成四分之一、八分之一等，从而产生

1⁄2、1⁄4、3⁄4、1⁄8、5⁄8、3⁄8、7⁄8、1⁄16、9⁄16、...

        等效地，这个序列的第 n 个数字是用二进制表示的数字 n，反转并写在小数点后。这适用于任何基地。例如，要找到上述序列的第六个元素，我们可以写 6 = 1*22 + 1*21 + 0*20 = 1102，可以将其取反并放在小数点后得到 0.0112 = 0* 2-1 + 1*2-2 + 1*2-3 = 3⁄8。所以上面的顺序是一样的

0.12, 0.012, 0.112, 0.0012, 0.1012, 0.0112, 0.1112, 0.00012, 0.10012,...
为了生成 3 的序列，我们将区间 (0,1) 分为三等分，然后是九分之九、七分之二等，生成

1⁄3、2⁄3、1⁄9、4⁄9、7⁄9、2⁄9、5⁄9、8⁄9、1⁄27、...
当我们将它们配对时，我们会在一个单位正方形中得到一系列点：

(1⁄2, 1⁄3), (1⁄4, 2⁄3), (3⁄4, 1⁄9), (1⁄8, 4⁄9), (5⁄8, 7⁄9), (3⁄8, 2⁄9), (7⁄8, 5⁄9), (1⁄16, 8⁄9), (9⁄16, 1⁄27)。

         Halton 序列在低维中表现得非常好，但在从较高素数生成的序列之间已经注意到相关问题。例如，如果我们从质数 17 和 19 开始，前 16 对点： (1⁄17, 1⁄19), (2⁄17, 2⁄19), (3⁄17, 3⁄19) 。 .. (16⁄17, 16⁄19) 将具有完美的线性相关性。为避免这种情况，通常会删除前 20 个条目，或根据所选素数删除一些其他预定数量。还提出了几种其他方法。最突出的解决方案之一是加扰 Halton 序列，它使用用于构建标准序列的系数的排列。另一种解决方案是跳跃式 Halton，它会跳过标准序列中的点。例如，仅使用每个第 409 个点（Halton 核心序列中未使用的其他素数也是可能的），可以实现显着的改进。

四、图像处理

4.1 Halton序列生成程序

def halton(b):"""Generator function for Halton sequence."""n, d = 0, 1while True:x = d - nif x == 1:n = 1d *= belse:y = d // bwhile x <= y:y //= bn = (b + 1) * y - xyield n / d

4.2 halton与randon函数的比较

        下图表示用halton序列和计算机内randon函数生成的10、100、1000、10000个点的随机序列，可见，halton对空间的覆盖更匀称高效。

总结

以上是生活随笔为你收集整理的低差别序列：高维序列（Halton sequence）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。