超斐波那契螺旋：快速、低差异采样SO(3)

82910超斐波那契螺旋：快速、低差异采样SO(3)0Marc AlexaTU Berlin0marc.alexa@tu-berlin.de0摘要0超斐波那契螺旋是斐波那契螺旋的扩展，能够快速生成任意但固定数量的三维方向。该算法简单且快速。与其他方法进行的综合评估表明，生成的方向集具有低差异性，在功率谱中几乎没有杂散分量，并且几乎具有相同的Voronoi体积。这使它们在各种应用中非常有用，特别是在蒙特卡罗采样中。01. 引言0生成方向或旋转样本的方法是科学和工程的基本构建模块。它们在蛋白质对接[27]、晶体学[31]、电子冷冻显微镜[8,48]或增材制造[39]等各个领域中被使用。在视觉、机器人和学习中，它们已经被用于路径规划[24,46]等方面。这项工作主要是受到在机器学习方法中使用方向样本来估计姿态或建立旋转等变性的影响。例如，卷积神经网络是线性的，并且已经发现与离散旋转（CNN）[32,53]很好地配合使用。姿态估计的一个最新趋势是学习姿态分布，需要一组方向样本[38,41]。更广泛地说，马尔可夫链蒙特卡罗（MCMC）方法在各种估计和优化任务中表现良好，并且现在在学习中被广泛使用。它们也适用于涉及方向的问题[5]，并且可以从使用低差异样本集来驱动蒙特卡罗采样器[43]中受益。使用方向进行计算需要一种表示。在这项工作中，我们使用单位3-球S3�R4，它是SO(3)的双覆盖。每个单位四元数q∈R4，∥q∥=1表示一个方向，而-q表示相同的方向。在这种表示中对方向进行采样意味着创建一对与原点之间距离为单位距离的点在R4中。0我们不专注于特定的应用，而是试图通过对S3上的几何度量来评估集合的质量。有各种方法来衡量球面和接近最优的集合的“良好分布”。在某种意义上最优的分布在另一种意义上可能远非最优。用于生成球面上“最优”装箱[9]或球面设计/码[52]的经典质量标准是基于局部度量，即任意两个方向之间的最近距离或空心圆盘的半径，即所谓的“离散度”。在第4节中，我们讨论了几种更适合度量方向样本质量的度量方法，并解释了如何计算它们。特别地，集合的差异与Koksma-Hlawka不等式[40]中准蒙特卡罗积分的误差直接相关。样本集分析的另一个经典工具是功率谱，描述了集合的谱特性并揭示了分布中的不良模式。我们还介绍了将S3投影到克利福德环面上以可视化混叠伪影的想法。使用这些方法，我们将现有方法与基于超斐波那契螺旋的采样（一种基于斐波那契采样思想的新方法）进行比较。我们在第3节中提供了背景，并开发和描述了该方法的细节。所得到的实现非常简单，支持样本细化，比所有现有方法都快，并且所得到的方向集非常适合采样。总之，我们认为在视觉、机器人、学习以及更广泛的科学和工程中，生成SO(3)上的样本集是一个基本构建模块，我们通过以下方式做出了贡献：0•我们提供了一套工具，用于分析用于采样应用的方向集合的属性。•我们引入了超斐波那契采样，一种在S 3上生成任意数量样本的方法。它简单且非常快速，并生成表示为四元数的高质量方向样本。103104105106100102104106829202.快速采样方向的方法0对于大多数用途，我们认为以下属性是有用的：（1）快速采样（2）任意数量n的样本（3）可以可能细化为任意kn个样本。文献中有各种方法在不同程度上满足这些要求。0均匀。最直接的方法是在S 3上使用伪随机均匀分布。可以通过从R 4中的任何径向对称分布中抽取点，然后对向量进行归一化来生成点。通常使用高斯分布[34]。生成样本所需的时间和空间是恒定的，常数由映射均匀分布到正态分布所需的Box-Muller变换[6]主导。均匀分布可以很容易地细化。0细分3多面体。在球面设计的背景下，常见的方法是细分正规3多面体[25]。Karney分析了这种集合的属性，并提供了一种近乎最优的离散选择（在github上可用[26]，根据MIT许可证）。计算细分很快，并提供自然细化，但严重限制了样本数量n的选择。我们在第4节中将比较Karney选择的集合，因为这足以说明细分引入的规则性不适合采样。0SOI。连续正交图像（SOI）[35]提供了一种SO（3）的采样方法，归结为对S 1 进行采样0定期和均匀地在S 2 上采样，使得两个采样密度选择得尽可能均匀，以便在S 1上的点之间的距离0和S 2的数量大致相同。样本数量n受限，因为它必须是导致两个样本空间上的类似间距的两个整数的乘积。这也严重限制了细化。方法的性质在计算复杂性和结果分布方面取决于选择用于采样S 2的方法。我们考虑在公开提供的代码中实现的两个版本（各自的许可条款：“版权但可用于商业用途”）。第一个变体使用正二十面体的细分。这导致快速采样，但引入了一些不需要的规则性。第二个变体使用优化过程。这使得方法在样本数量上的复杂度超线性增长。计算时间取决于如何检测优化的收敛细节。我们使用提供的代码，这限制了最大迭代次数，这意味着它可能更倾向于较小的计算时间而不是大样本集的分布质量。第4节的结果表明，即使对于大样本集，质量也没有显著影响。0n0毫秒0均匀SOI正二十面体SOI优化Hopf纤维超斐波那契0图1.以四元数表示生成n个方向样本的墙钟时间。只有在S 2 上进行优化的SOI0显示超线性时间复杂度。0Hopf纤维。SOI方法已经使用基于Hopf纤维的坐标进行修改，以允许逐步构建良好的方向样本[58]。这意味着n和n +1个样本集仅在一个额外点上有所不同。该方法每个样本具有恒定的计算复杂度，并且可以使用任意数量的样本。逐步构建对分布的质量产生不利影响。代码可在GNU公共许可证下获得。0SO(3)中的优化。优化SO(3)或S3中的分布的方法未包含在比较中，因为它们耗时太长：Gr¨af和Potts[18]以及Larsen和Schmidt[29]报告了数天的计算时间。这是由于涉及到的优化与收敛缓慢以及从许多不同的配置开始以避免坏的局部最小值的组合。0计时。图1显示了具有源代码的方法的墙钟计时。对于n �10^6，我们使用：(1)2、3和5的幂来采样足够数量的值；(2)具有大量不同除数的优秀高复合数n = {60, 120, 360, 2520, 5040, 55440,720720}；(3) Fibonacci素数n = {89, 233, 1597, 28657,514229}。后两组值被包含在内是为了看看不同方法的性质(在下面进一步讨论)是否取决于n的可除性。对于SOI方法，我们仅使用靠近该集合的推荐值-n的这一点解释了图1中散点图中的不同间距。分析表明，使用优化的SOI方法由于其超线性时间复杂性而仅限于较小的样本集。��.(1)�.(2)−z sin hy0z cos hy1z cos hz c�(7)829303. 在S3上的Fibonacci采样0优化低偏差集是困难的。此外，由于底层几何结构，优化SO(3)是麻烦的。我们展示了如何基于扩展Fibonacci采样的思想生成方向的低偏差集。0平面上的Fibonacci采样。设ti是[0,1)中等间距的n个值，则样本给出如下：0xi = x(ti)，x(t) = � nt0ϕ - � nt0ϕ0采样的质量，即偏差，取决于常数ϕ。观察到将ϕ设置为(1 +√05) /2，即黄金比例，在实践中可以得到最佳结果，因此得名。黄金比例的出现可以被认为是自然的，因为它是有理近似收敛最慢的无理数。虽然可以根据ϕ的连分数表示导出偏差的上界[40，Thm.3.3]，但为什么黄金比例对于有限样本是最优的或紧密相关的仍然不清楚。Fibonacci采样已被用于生成二维域的低偏差集。采样曲线(x(t),t)导致单位正方形的非周期性采样。面积保持映射从[0,1]2到参数化的极坐标单位圆盘[0, 2π] × [0, 1]，由(θ, r) =(2πx0, √x1)将其转换为单位圆盘的笛卡尔坐标采样：0y(t) = � √0t sin 20ϕ，√0t cos 2πnt0ϕ0这里，正弦和余弦函数的周期性使得floor函数消失。插图显示了100个样本的结果点分布。单位圆盘的采样可以映射到2-球上，从而在球面上产生无处不在的Fibonacci(或黄金)螺旋[17，19，45，54]。0提升到S3。在S3上使用Fibonacci采样的主要工具是从实心圆柱到3-球的体积保持映射。考虑圆柱{ (h, y = (y0, y1)) |-π < h ≤ π, yTy ≤ 1 }。然后0x(h, y) =0z cosh zsinhhy0y10� � � ，z 01 - yTy (3)0将圆柱中的点映射到四维单位球中。逆映射 x = (x0.x1, x2,x3) 给出如下：0(h, y0, y1) = (arctan2(x1, x0), x3, x4). (4)0这表明映射是圆柱体的内部与没有'赤道'x0 = x1 =0的球之间的双射。圆柱体表面上的线{−π < h ≤ π，yTy =1}被映射到球的赤道上的点(0, 0, y0,y1)。在圆柱体的内部yTy <1，即映射是双射的地方，我们可以计算雅可比矩阵为0Jh, y =0�0� � 0z sin h 0 1 0 0 0 10�0� � �, (5)0其中我们使用了0∂z/∂y0 = -y00z, ∂z/∂y1 = -y10z. (6)0使用雅可比矩阵，我们现在可以分析体积的变化并得到以下结果：0声明1 映射0x(h, y): {(h, y) | -π < h ≤ π, yTy < 1} → S3 � R40保体积。0体积元素可以计算为雅可比矩阵的奇异值的乘积。注意到Jh,y的三列都是x(h, y)上的切线，我们可以计算为det(x(h, y),Jh, y)，因为x(h,y)与切平面正交且长度为1。通过第一列展开，我们得到0nh)0+y0�y0 sin2h + y0 cos2h�0-y1�-y1 cos2h -y1 sin2h�0= �1 - yTy� �cos2h + sin2h� + yTy = 1，0正如所述。□给定映射，主要思想是使用斐波那契采样两次在圆柱体上生成点：（1）沿着圆柱体的主轴h和（2）在与主轴正交的单位圆盘（y0，y1）。使用两个不同的常数ϕ和ψ进行两次采样，我们得到：0z(t) = �n0ψ - �nt0ψ0�, √0t sin 20ϕ, √0t cos 2πnt0ϕ0�T. (8)0将这个采样模式插入到映射到3-球的中，我们得到以下简单曲线，展示了预期的对称性：0w(t) =0�0� 0√0ϕ0ϕ√1 - t sin 2πnt0ψ√1 - t cos 2πnt0ψ0�0� � � �. (9)ϕ2 = 2,ψ4 = ψ + 4,ϕ, ψ ∈ R+.(10)ψ = 1.533751168755204288118041 . . .(11)Discrepancy measures the error being made when es-timating the volume of a (convex) region by consideringonly the number of samples in the region [28]. Each sam-ple represents the expected measure, i.e. the total measureof the domain divided by the number of samples. For theD(Q) =supp3,r[0,π[82940在规则值ti上对这条曲线进行采样是生成方向样本的一种自然方法。为了方便复制，算法1提供了实现这种方法的详细信息。0算法1：在SO(3)上生成n个样本作为单位四元数0函数Super-Fibonacci(n, ϕ, ψ)0对于i∈{0, ..., n-1}做0s ← i + 10t, R ← √1 - t α ← d0ϕ, β ← d0ψ_q_i ← (r sin α, r cos α, R sin β, R cosβ,)0这个算法明显具有恒定的每个样本的复杂度。此外，它在实践中比我们测试过的所有替代方法都要快（参见图1）。该算法还直接显示了一个包含kn个样本的集合包含了生成n个样本的集合，或者更一般地说，包含了m个和n个样本的集合共享每个第k个样本，其中k是m和n的最大公约数，即很容易对已经用于计算的集合进行细化。0参数。样本集质量的一个重要因素是常数ϕ和ψ。我们不仅需要ψ和ϕ是无理数，它们之间的关系也很重要：如果它们是彼此的有理倍数，得到的集合将是次优的。由于缺乏将这些数字的属性与生成的样本集之间联系起来的数学理论，启发式搜索和实验探索是唯一剩下的选择。为此，我们使用了可以从Voronoi图（参见第4.3节和补充材料）确定计算的质量标准。将其中一个常数设置为黄金比例似乎是很自然的选择。在这种情况下，提供良好结果的另一个常数选择是超黄金比例，它是方程ψ^3 = ψ^2 +1的唯一实数解。这个观察结果导致了“超斐波那契”这个名称。然而，对小次数多项式的根进行更详尽的探索揭示了稍微更好的选择。建议的选择是正实根：02 ， ψ的解没有简单的表达式，尽管作为一个降阶四次方程，它可以用（嵌套的）平方根和立方根表示。为了参考和方便复制，其小数展开足够达到双精度的是：0有趣的是，ψ 不是一个 Pisot 数 [ 4 ]，因为 ψ 4 −  ψ  −  4的所有根的模大于 1 。Pisot 数与无周期的铺砖 [ 36 ]以及特定实例（如黄金比例、银比例、超黄金比例以及特定于二维网格的塑料数 [ 21 , 50]）在（Fibonacci）采样的背景下被提出。上述定义的 ψ 和ϕ 的值用于所有评估。04. 分析和比较0通过在球体上诱导的自然度量来测量两个方向之间的距离0d ( p ,  q ) = arccos  |� p ,  q �|  。 (12)0等效于 SO (3) 的自然 Riemann 度量中的测地距离 [ 22]，或者直观地说，将一个方向转变为另一个方向所需的最小旋转角度（取绝对值是因为 q 和 − q表示相同的方向）。我们更普遍地使用 S 3来测量几何量。特别地，我们需要半径为 θ（以弧度表示）的球冠的体积 V ◦ ( θ ) =  π (2 θ  −  sin^2θ ) 。 (13)0以及包围此球冠的球体的面积：0A ◦ ( θ ) = 4 π  sin^2 θ. (14)0用于在 S 3 上计算的导出和其他几何工具0以及下文所描述的方法的数据和代码都在补充材料中提供。04.1. 差异0对于每个 SO (3) 的样本 q ，将 n 分配到 S 3 上，因为 S 3的总体积为 2 π^2 ，每个样本由对  ± q的对表示。对于欧几里得域，通常考虑星形差异，它基于一个盒子的度量 [ 59 ]。适当的类比是 S 3上的超球冠，确保与蒙特卡洛技术的强连接保持 [ 12 ,9.1.5]。因此，对于大小为 n = |Q| 的集合 Q = { q i ∈ R^4,  ∥ q i ∥ = 1 } ，四元数球冠差异为0V ◦ ( r )  −  π^0n # { d ( p ,  q i )  ≤r } 。0(15) 仅考虑小于半球的球冠，因为单位四元数是双覆盖。100101D(Q)(r)̸̸2⇐⇒r =�3π �1/3(17)8295010^2 10^3 10^4 10^5 10^6 10^(-3)010^(-2)010^(-1)0均匀 Karney数据 SOI二十面体 SOI优化 Hopf纤维化Super-Fibonacci0图2. 球冠差异的近似。0计算此值时，请注意改变球冠的体积而不改变球冠中的样本数量也会改变差异。这意味着当球冠的边界球包含一个或多个样本时，D ( Q )的临界点就会实现。如果是这种情况，球冠的微小变化将包括或排除边界上的点。然而，即使对于中等规模的 n，探索所有具有边界点的配置也是不可行的，因为其复杂度为 O ( n^4 )。对于欧几里得空间，扫描技术和特定的矩形分解将复杂度降低到 O ( n^3 ) [ 13 ,  42]。目前尚不清楚如何将这些技术应用于球体，而立方体复杂度仍然无法处理。因此，我们选择了一种采样技术，仍然利用了关键球冠在其边界上具有样本的观察结果。其思想是固定 m 个均匀随机的中心 c_j ∈ S 3 。对于每个中心 c_j，我们考虑由 n 个半径 d ( c_j ,  q_i )定义的球冠。注意，这些球冠的边界上有 q_i。这些球冠按照半径排序，即根据距离 d ( c ,  q_i ) 对 q_i进行排序。对于合理分布的样本，这可以在线性时间内完成[ 11]。遍历排序列表可以提供球冠内部的点数，而无需任何额外开销。此过程的总体复杂度是线性的，对于不同的中心 c_j可以轻松并行执行。补充材料展示了小规模 n的收敛行为。在比较不同的分布时，我们使用相同的中心集合。图 2展示了这种比较的结果，以差异与样本大小的散点图形式呈现。我们发现，在所有样本大小上，使用在 S 2上进行优化的 SOI 和 Super-Fibonacci采样的差异至少比其他所有方法低一个数量级。规则的多面体细分（Karney 的数据或基于细分的SOI）的表现不如均匀采样。04.2.径向分布函数0常见的分析平稳过程是基于一阶统计的。径向分布函数或成对相关函数描述了样本的密度与成对样本的相对位置有关[23]。如果生成样本的过程被假设为各向同性，或者没有首选方向，那么相对位置可以简化为样本之间的距离。通过与通常为高斯函数的核函数κ进行卷积，计算出成对距离的密度函数。对于距离为r（以弧度表示）的每个样本，我们需要通过该距离上的预期样本数量进行归一化，该数量与半径为r的球冠边界上的球面积成比例。这导致以下密度函数，除了常数因子：0g_Q(r) = 10q_i , q_j ∈Q ,i � = j κ  ( r  −  d ( q_i ,q_j ))  . (16)0对于Dirac δ函数为κ，g(r)与功率谱[20]密切相关，描述了空间频率的功率分布，在这种情况下是球谐函数。这两个函数包含完全相同的信息。虽然径向分布函数在统计力学中经常使用，但功率谱在工程中更常见[56]。具有良好采样特性的分布通常与蓝噪声[30]相关联。计算径向分布函数相当于为每对不同样本i ≠ j的核函数 κ(r - d(q_i, q_j)) 添加到函数 g_Q(r)中。由于二次复杂度导致无法处理的运行时间，我们随机选择了m个样本的子集，然后计算与所有其他n个样本的距离，导致复杂度为O(mn)。密度函数 g(r) 可以使用等间距的r_i 在[0, π/2]上离散表示，使得 g(r_i)形成一个向量。对于核函数，我们使用高斯函数。我们根据球体的半径调整方差，其体积是S^3的总体积的1/n：0n = 4πr^302 n0然后我们将高斯分布的方差设置为半径的一半，即 σ 2 = r2 / 4（也可以选择其他因子）。为了避免为每对样本的每个r i迭代，我们计算了这个高斯分布的宽度，使得其贡献大于单精度机器epsilon。图3显示了对于约2×10^4个点的样本集进行此计算的结果 - 对于其他 n的曲线是类似的。均匀分布导致几乎平坦的径向分布，这是预期的，因为所有成对距离都以相等的概率出现。使用细分的多面体的方法，如Karney的方法00.20.40.6 rg00.20.40.6 rg00.20.40.6 rg00.20.40.6 rg00.20.40.6 rg00.20.40.6 rg̸82960均匀分布0Karney的数据0SOI二十面体0SOI优化0Hopf纤维化0超级斐波那契0图3.对于n ≈ 2×10^4的径向分布函数。0基于对二十面体进行细分的数据和SOI方法在小和大的成对距离上都会出现不希望的峰值。在S2上使用优化的SOI方法没有小距离的成对，但是会产生典型的振铃效果，因为要避免这样的成对。Hopf纤维化和Super-Fibonacci采样显示出所期望的行为，没有小距离的成对，并且对于较大距离的成对有快速衰减的变化 -参见Singh等人的例子和关于样本集的性质与其径向分布函数之间关系的讨论[51]。04.3. 球面Voronoi图和面积0与站点相关联的Voronoi单元Ωi是给定域中离站点最近的点的集合，即对于四元数站点{qi}在S3上0Ωi = {x ∈ S3: d(x, qi) ≤ d(x, qj), i ≠ j}. (18)0Voronoi单元由两个相等的对偶区域组成。Voronoi单元的边界由平面组成，这些平面通过原点（R4中两个点距离相等的点的轨迹）与单位球面S3相交。换句话说，Voronoi单元是（对偶的）球形多面体。可以通过Voronoi单元的性质来考虑样本集的质量，通常考虑的是体积[3]，希望在样本之间保持相同。Voronoi图是Delaunay三角剖分的对偶[2]。在温和条件下，Delaunay三角剖分在球面上的组合与点的凸包相同，即没有半球是空的。为了使用标准软件计算凸包，我们为每个样本qi添加其对偶点−qi，这也保证了没有半球是空的。00 0.5 1 1.5 0 0.2 0.4 0.6 0.8 1∙10^40面0均匀00 0.5 1 1.5 0 0.2 0.4 0.6 0.8 1∙10^40面积0Karney的数据00 0.5 1 1.5 0 0.2 0.4 0.6 0.8 1∙10^40面0SOI二十面体00 0.5 1 1.5 0 0.2 0.4 0.6 0.8 1∙10^40面积0SOI优化00 0.5 1 1.5 0 0.2 0.4 0.6 0.8 1∙10^40面0Hopf纤维00 0.5 1 1.5 0 0.2 0.4 0.6 0.8 1∙10^40面积0超级斐波那契0图4.相对于等面积分割2π^2/n的Voronoi面积的直方图，其中n≈2∙10^4。0凸包，对于每个样本qi，我们添加其对偶点−qi，这也保证了没有半球是空的。为了计算凸包，我们使用CGAL的dD三角剖分代码[10]（虽然可以直接计算球面Voronoi图[7]，但没有公开可用的稳定实现）。一个重要的技巧是在球体内部添加一个点。这对凸包没有影响，但避免了处理所有单纯形共享相同外接球的退化情况的计算成本高昂的情况。如果样本分布良好，则可以在O(n)时间内计算Delaunay三角剖分[1]。我们将Voronoi顶点找到作为（球形）Delaunay四面体的外接球心（见补充材料）。对于给定的样本qi，由于与qi相交的Delaunay四面体产生的Voronoi顶点形成一个球形多面体，即Voronoi单元Ωi。Ωi的面是与从qi发出的Delaunay边正交的球面多边形。为了计算Voronoi单元的体积，我们将其分解为球形四面体，其体积可以使用超几何级数计算[37,47]。图4显示了相对于等面积体积分割2π^2/n的体积的直方图，其中n≈2∙10^4。均匀分布的体积具有预期的平滑和大的变化。基于细分多面体的分布，如Karney的数据或基于二十面体的SOI方法，具有一组离散的体积，变化很大。有趣的是，Hopf纤维显示出两种模式，体积都有适度的变化。基于S2上优化的SOI方法和超级斐波那契采样都具有非常窄的峰值。.(19)x23.(23)82970均匀 Hopf纤维 SOI二十面体 SOI优化在S2上 超级斐波那契0图5.使用以n≈5∙10^5个样本为中心的高斯核重建的Clifford环上的区域板。上排基于环和样本的规范方向，下排基于（相同的）样本相对于环的随机方向。0Delaunay三角剖分直接得到了覆盖半径或离散度（点集中最大空球的半径）和打包距离（在样本处放置的不重叠球的最大半径）。这些度量在采样应用的上下文中不太相关，并在补充材料中讨论。04.4. Clifford环面可视化0样本分布的质量通常通过可视化来展示，利用人类视觉系统对（不）规则性的敏感性。除了显示样本外，另一种方法是通过从点样本中的值重建具有不同频率内容的函数，展示伪影伪像。为了适应在S3上的样本，我们考虑Clifford环面，它是在规范方向上给出的S3的一个切片，如下所示：0x20 + x21 = x22 + x23 =10Clifford环面本质上是平坦的，意味着它可以等距地映射到（标准的欧几里得）平面上。常见的参数化形式是0x(θ, ϕ) = 1√02(cosθ, sinθ, cosϕ, sinϕ). (20)0点x∈S3\{x0=x1=0, x2=x3=0}的正交投影为0x' = 1√0� x0x20 + x2x1√0x20 + x2x2√0x22 + x23,x3√0� (21)0显示平面上正交投影的图像为0(arctan2(x0, x1), arctan2(x2, x3)). (22)0为了可视化伪影伪像，我们使用区域板函数的重建，其中仅沿着环面测量到固定点q的距离，以避免切片引入的伪影：0z(x) = 1 + cos � kd(x', q)2 �0该函数在S3上进行采样，并使用高斯核在Clifford环面上进行重建。在[-π，π]2范围内的图像在m×m网格上离散表示。高斯核的方差设置为网格单元的对角线，即σ = m−1√02π。平面图像与R4中的嵌入之间的等距映射允许在S3上使用相同的方差。图5显示了区域板的重建结果。选择了样本数量n≈5∙105，以确保每个环面上的网格点足够接近一个样本（对于S3上的理想样本分布）。上排图像基于样本集的规范方向。由于样本集中存在潜在的方向偏好，下排重建基于将样本集相对于环面旋转，使用相同的（随机）旋转角度对所有方法。基于SOI方法和超级斐波那契采样的重建明显优于Hopf纤维化和均匀采样。规则伪影在规范方向上较轻微，并且对于超级斐波那契采样最不明显。829805. 讨论0超级斐波那契采样提供了一种简单快速的方法来计算任意数量的均匀分布的方向。这些样本的差异性明显低于其他类似快速方法，并且与基于优化的技术相当。为了说明分布的质量与生成样本所需的时间之间的关系，我们比较了在25毫秒内生成的样本数量基于区域板的重建结果。结果如图6所示。在这个比较中，超级斐波那契采样明显优于其他所有方法。Voronoi单元的分析表明，单元的体积几乎相同 -这种等体积特性已被观察到，以避免优化算法中的不必要的规则性。良好的体积分布的原因可能是从完整圆柱体到S3的体积保持映射，将Fibonacci采样的良好特性传递到区间和单位圆盘上。超级斐波那契采样比单位球面上的简单均匀随机采样更快，这是由于更少且更易于实现的非基本函数的使用。总体上只有两个平方根，以及具有相同参数的两对正弦和余弦函数由现代编译器优化以利用并行sincos硬件实现。对于大小为n和m的两组集合，每个第k个点将是相同的，其中k是n和m的最大公约数，这使得通过生成n个点的倍数（然后跳过原始点）来简化序列的过程变得容易。0限制。使用超级斐波那契生成的集合的分散性比基于优化的SOI方法生成的集合差 -详见补充材料。这在某些应用中可能是相关的[15]。对于标准球面斐波那契采样，观察到最小的空球出现在序列的开头和结尾。这个问题可以很容易地缓解[49]。我们尚未尝试对超级斐波那契采样进行这种修改以改善分散性。还应注意，我们仅考虑对于那些能够将n因子分解为在S1和S2上具有相似间距的采样的SOI方法。强制任何复合值n是可能的，但会导致在S3上非常不均匀的采样。常数ϕ和ψ会影响分布的特性。它们已经通过考虑不同质量度量的样本大小为n≈105进行了实验确定。将这些常数与结果分布连接起来的理论分析尚缺乏，这是需要的。此外，对于更大的样本大小和/或特定的用例，可能需要使用不同的常数。0均匀Hopf纤维。SOI Icosa SOI Opt  S 2 Super Fib0图6.根据在大约25毫秒的总运行时间内由采样方法生成的样本数量，重建了Clifford环面上区域板的右半部分。0与其他工作的关系和在其他情境中的使用。高速生成样本可能对准蒙特卡洛技术有用，因为样本集可以即时生成。优化技术可能受益于确定性的起始点，比随机均匀样本更接近最优解。分析技术通常旨在优化局部度量，如装箱距离或分散度。直接优化差异很困难，但优化样本集以满足指定的径向分布函数可能是可能的[55]。一般策略是最小化到样本的平方距离之和，即Lloyd方法[33]，对于连续域导致质心Voronoi图[14]。在这个背景下，已经观察到强制样本集具有相等的Voronoi体积可以避免此类优化方法引入不需要的规则性[16]。请记住，超级斐波那契采样生成具有几乎相同体积的Voronoi单元，这正是这些优化方法的目标。Balzer等人[3]建议在离散容量约束下优化分布，这使得优化对底层几何形状无感知。这需要一个“背景”样本集来强制相等的容量，这个样本集需要是所需样本数量的大倍数。超级斐波那契采样非常适合生成这个背景集。由于其自然的细化特性，使用超级斐波那契采样生成的一组kn个样本包含m个不同但分布良好的k个方向集。这可以用于拒绝密度函数的采样：将密度函数量化为k个级别，然后与样本的索引对k取模进行比较。超级斐波那契采样中的样本可以根据索引i和总数n独立计算，这使得在分布式计算中可以使用而无需消息传递。82990参考文献0[1] Nina Amenta, Dominique Attali, and Olivier Devillers.低维多面体上的Delaunay三角剖分的复杂性.《第十八届ACM-SIAM离散算法年会论文集》, SODA '07,2007年, 美国. 工业和应用数学学会.  60[2] Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee.Voronoi图和Delaunay三角剖分. 世界科学出版社, 2013.  60[3] Michael Balzer，Thomas Schl¨omer和Oliver Deussen.容量受限的点分布：Lloyd方法的变体. 《ACM Trans.Graph.》，28(3)，2009年7月.  6 ,  80[4] Marie J. Bertin，Annette Decomps-Guilloux，MartheGrandet-Hugot，Martine Pathiaux-Delefosse和JeanSchreiber. Pisot和Salem数. Birkh¨auser，巴塞尔，1992年.  40[5] Tolga Birdal，Umut S¸ims¸ekli，M. Onur Eken和SlobodanIlic. 基于Bingham分布和温和测地线MCMC的贝叶斯姿态图优化.在《第32届国际神经信息处理系统会议论文集》，NIPS’18，页306–317，Red Hook，NY，USA，2018年. Curran AssociatesInc.  10[6] G. E. P. Box和Mervin E. Muller.关于生成随机正态偏差的注记. 《数学统计学年鉴》，29(2):610 –611, 1958年.  20[7] Manuel Caroli，Pedro M. M. de Castro，S´ebastienLoriot，Olivier Rouiller，Monique Teillaud和CamilleWormser. 球面上点的稳健高效的Delaunay三角剖分. 在PaolaFesta编辑，《实验算法》，页462–473，柏林，Heidelberg，2010年. Springer Berlin Heidelberg.  60[8] Yu H Chen，Se Un Park，Dennis Wei，GregNewstadt，Michael A Jackson，Jeff P Simmons，Marc DeGraef和Alfred O Hero. 电子背散射衍射索引的词典方法.《显微镜与显微分析》，21(3):739, 2015年.  10[9] John Horton Conway和Neil James Alexander Sloane.球填充，格子和群，第290卷. Springer Science & BusinessMedia，2013年.  10[10] Olivier Devillers，Samuel Hornus和Cl´ement Jamin.dD三角剖分.在《CGAL用户和参考手册》，CGAL编辑委员会，5.2.1版，2021年.  60[11] L. Devroye和T. Klincsek. 分布式排序算法的平均时间行为.《计算》，26(1):1–7, 1981年.  50[12] Josef Dick和Friedrich Pillichshammer.差异理论和准蒙特卡罗积分. 在William Chen，AnandSrivastav和GiancarloTravaglini编辑，《差异理论全景》，页539–619. SpringerInternational Publishing，Cham，2014年.  40[13] Carola Doerr, Michael Gnewuch和Magnus Wahlstr¨om.差异度量的计算和应用. 在William Chen，AnandSrivastav和GiancarloTravaglini编辑，《差异理论全景》，页621–678. SpringerInternational Publishing，Cham，2014年.  50[14] Qiang Du，Vance Faber和Max Gunzburger.重心Voronoi镶嵌：应用和算法. 《SIAM评论》，41(4):637–676,1999年.  80[15] Benoˆıt Gandar, Ga¨elle Loosli和Guillaume Deffuant.采样离散度对于分类来说比采样差异性更好.技术报告，2010年10月.  80[16] Fernando de Goes，Katherine Breeden，Victor Ostro-moukhov和Mathieu Desbrun. 通过最优输运实现蓝噪声. 《ACMTrans. Graph.》，31(6)，2012年11月.  80[17] Alvaro Gonz´ales.使用Fibonacci和纬度-经度格子测量球面上的面积.《数学地理科学》，42(1):49–64, 2009年11月.  30[18] Manuel Gr¨af和Daniel Potts.通过基于快速球面傅里叶变换的新优化方法计算球面设计.《数值数学》，119:699–724, 2011年.  20[19] J H Hannay和J F Nye. 在球面上的Fibonacci数值积分.《物理学杂志A: 数学和一般》，37(48):11591–11601,2004年11月.  30[20] Daniel Heck，Thomas Schl¨omer和Oliver Deussen.具有受控混叠的蓝噪声采样. 《ACM Trans.Graph.》，32(3)，2013年7月.  50[21] Doug Hensley和Francis Edward Su.带有坏逼近数的随机游走.《离散数学和理论计算机科学DIMACS系列》，64:95–102, 2004.40[22] Du Q. Huynh. 3D旋转度量: 比较和分析.《数学成像与视觉杂志》, 35:155–164, 2009.  40[23] Janine Illian, Antti Penttinen, Helga Stoyan和DietrichStoyan. 空间点模式的统计分析和建模, 卷70. 约翰∙威利和儿子,2008.  50[24] Lucas Janson, Brian Ichter和Marco Pavone.确定性采样式运动规划: 最优性, 复杂性和性能.《国际机器人研究杂志》, 37(1):46–61, 2018.  10[25] Charles F.F. Karney. 分子建模中的四元数.《分子图形与建模杂志》, 25(5):