Background maths

Permutation: 置换（排列）

定义：既是一种排列，也是一种映射

• n 个元素不缺失不重复的不同排列方式；每一种叫做一种置换

• 置换也可以定义成一种集合到自身的映射（一对一满射，双射）（某个置换情况，可以定义为每个元素到置换后的新元素的映射）

置换有几种不同的 notation

• two-line notation

对于集合 S = {1, 2, 3, 4, 5} 的一种置换可以写作：

这也就是说 σ 满足 σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, and σ(5) = 1

• 注意这里的 σ 函数（准确地说是 σ 映射）就是这个置换的定义。
• 粗俗地讲，这个置换就是“把1换成2，把2换成5，把3换成4，把4换成3，把5换成1”

也就是说，在这种 notation 方式下，集合中具体元素的写在第几列是无所谓的，比如上面这个置换也可以记为：

或者也可以记为：

上面这3个记号都是同一个置换，他们都是“把1换成2，把2换成5，…”

• one-line notation

假设集合 S 中的元素有一种“自然顺序”（比如 1 2 3 4 5），那么我们可以把上面这种置换记为 2 5 4 3 1

• cycle notation

每个置换都可以表达成若干个 cycle 的循环。比如前面的 (2 5 4 3 1) 可以记为 (1 2 5)(3 4)

这种记法怎么写出来：

1. 随便挑一个集合中元素，写下来 (x；
2. trace the orbit of x （追寻 x 的轨道），也就是不断地应用置换映射直到出现循环 (x, σ(x), σ(σ(x))), ...
3. 再挑一个还没写的集合 s 中元素，重复上述过程；直到所有元素都被写下来为止。

在 cycle notation中，1-cycle 常常被忽略掉。

cycle notation 的一个好处是一个置换的逆等于逆转每个cycle的顺序。

比如 [(1 2 5)(3 4)]^(-1)=[(5 2 1)(4 3)]

对称群：一个集合S的所有置换S_n

• closure: 如果 π 和 σ 在 群中，那么 πσ 也在群中
• associativity: (πσ)τ=π(στ)
• identity: 存在一个 identity 置换 id, id(x)=x for any x in S
• invertibility: 对于群中任何一个置换，都存在一个逆置换；π^{-1}并且 π^{-1}π=ππ^{-1}=id
• 一般不满足 commutative，也就是说 一般 πσ≠σπ

cycle (循环)

定义：如果2个元素发生了两两置换，或者3个元素发生互相置换（a->b, b->c, c->a），或者4个元素，… ；n 个元素的这种循环置换称之为一个 n-cycle (循环)

1-cycle 就是一个固定点(a fixed point)

transposition

一个 2-cycle 就是一个 transposition

polytope (多胞形)

定义：一个有着 flat sides (faces) 的 集合对象；如多边形、多面体、超多面体 …;

n-polytope 是定义在三维空间的 polyhedra (多面体) (i.e. 3-polytope) 对任意维度 n 的扩充广泛定义；

facet (维面) vs. face (面)

一个 n维 polytope 的 n-1 维 的 face(面) 被称为 facet (维面)。

这个 n 维 polytope 还可以有其他维度的 face(面)，比如对于一个 3维cube来说，它有2维面（即其 facets=维面），有1维的面（即其 edges=边），有0维的面（即其 vertices=顶点）

cell (胞)

edges (边)

permutohedron (排列多面体)

定义：一个 n阶 的 permutohedron 是一个 嵌入在 n 维空间中的 (n-1) 维多胞形。

它的顶点坐标（顶点标签）是前 n 个自然数的所有置换。

它的边 代表着 两个相连顶点的最短路径。被一条边相连的两个顶点只在两个位置不同（也就是只有一个 transposition 的不同），并且值只有1的差异

4阶 permutohedron

• 是一个截角八面体（truncated octahedron）（截角八面体：将正八面体的6个顶点切去、并在被切掉的地方建立6个正方形）
• 有6组平行的边，对应着4个元素的6种可能的 transpositions

vertices (顶点), edges (边), facets (维面)

n 阶 permutohedron 有：

• $n!$ 个顶点；每个顶点与 (n-1) 个其他顶点相邻/相连 (adjacent)（因为对于对应某个顶点的某种排列来说, 其中有 (n-1)对值相差为1的元素可以互换）；
• $\frac{(n-1)n!}{2}$ 条边；每条边的长度是 $\sqrt{2}$
• 相连的顶点，只有2个元素相差为1的元素发生置换
• $2^n-2$ 个 facet(维面)，因为他们对应着 前n个自然数构成的集合的非空子集的个数

对于 1个 n 阶 polyhedron，它的 n-k 维的 face(面) 的个数如下图

Tessellation (密铺;堆砌) / tiling

n-1 维的空间(超平面) 可以被 无限多个 n 阶的 permutohedron 的平移副本来密铺；

在这个密铺中，任何两个 permutohedron 之间的坐标差异都处于一个 n-1 维的 lattice 中。

比如说，对于4阶permutohedron 来说，在其堆积中，任何一对permutohedron 的坐标差异 (x1,x2,x3) 都处于一个3维的 lattice 中，在这个 lattice 中的所有点都满足

2阶 permutohedron 的密铺就是 apeirogon (无限边形)

3阶 permutohedron 的密铺就是 hexagonal tiling (正六边形堆积)

hexagonal tiling 的对偶是 Triangular tiling

4阶 permutohedron 的密铺就是 Bitruncated cubic honeycomb (截角八面体堆积)

Bitruncated cubic honeycomb 的 vertex figure (顶点图) 是 disphenoid (楔形四面体, 或楔形体) ，对偶是 Tetragonal disphenoid honeycomb (楔形四面体堆积)

• disphenoid：楔形四面体, 或楔形体：4个面是全等锐角三角形的四面体
• vertex figure：顶点图：大致是一个几何图形的角被切去时露出的形状

lattice (格;格点;点阵)

lattice in group theory: repeating arrangement of points 格点; 点阵

lattice 是无穷多个点的集合；在 n 维空间中，我们首先定义 n 个线性无关（linearly independent）的基向量（比如2维空间中的2个不共线的向量，或者3维空间中3个不共面的向量），那么这 n 个向量的任意整数倍相加组合构成的向量集合就是一个 lattice

可以看到，lattice 中的任意两个点的坐标相加相减得到的点都仍在这个 lattice 中。

Voronoi diagram (沃罗诺伊图)

定义：在数学中，Voronoi 图是将平面划分为各个区域的一种方式，每个区域都接近给定对象集合中的某一个对象。

严谨的定义形式，针对离散数据集合中的某个点，距离这个点比集合中其他点都近的区域就是属于这个点的一个 voronoi cell(胞)，或者成为 Thiessen polygons (泰森多边形)

Simplex; simplicies (单纯形)

k-simplex 的定义：k维空间中是k+1 个仿射不相关的点的凸包。

仿射不相关：k+1 个点的差分 (u1-u0, …, uk-u0) 向量线性不相关；或，没有n-1维的仿射子空间能够包含全部k+1个点；

仿射子空间：一个 n 维空间的所有 n-1维,…,0 维的超平面

Barycentric coordinates (重心坐标)

空间中一点的位置可以被看做是一个单纯形的顶点上放置不同质量大小后的重心(质心)；

当且仅当这些质量均为正时，点位于单纯形内部;

每个点都可以用重心坐标表示，并且其和不为0；当且仅当两个坐标成非零比例时，两个坐标表达的是同一个点；重心坐标是一种齐次坐标；所以一般被认为是归一化到和为1的。

Permutohedral lattice

主要参考：

• [pdf] [2009] Some useful properties of the permutohedral lattice for Gaussian filtering.
  • 这篇也是比较严谨地论述了 permutohedral lattice 的数学性质
• [website] [Eurographics 2010] Fast high-dimensional filtering using the permutohedral lattice.
• [pdf] [Journal of Mathematical Imaging and Vision 46.2 (2013)] Lattice-Based High-Dimensional Gaussian Filtering and the Permutohedral Lattice
  • 这篇是 Fast high-dimensional filtering using the permutohedral lattice. 的延伸；主要是严谨地关注技术底层的数学理论，而不是技术应用本身。一部分图表和文字来自于他们 2009 年的 technical report

背景：高维高斯滤波 (2009~2013年左右)

在图像处理、几何处理和计算机图形学领域中，为了在保持重要特征的同时还能够平滑数据，一族比较受欢迎的技术就是高维高斯滤波 (high-dimensional Gaussian filtering)。比如，双边滤波器 (bilateral filter), 交叉双边滤波器 (cross bilateral filter) 和 非局部均值滤波器 (non-local means filter) 都在这一族中。

2013年左右，一些算法进一步展示了通过依赖于底层空间 (underlying space, 这里指的就是高维表示空间) 中的一种基于采样的表征，相比于传统方法能够获得很多个数量级的速度提升。这种基于采样的表征中最简单的一种就是 lattice，并且成功地在 双边格 (bilateral grid) 和 置换多面体格 (permutohedral lattice) 中得到应用。通过一些针对质量和计算效率的评判准则，能够比较严谨的论证 permutohedral lattice 是最优的。

之所以能取得大幅加速，主要就是在这些离散的、规律的点阵上进行模糊和滤波，索引操作和各种计算都是发生在可预测的已知位置上的，会比直接在原始的连续空间进行操作的计算要快很多。

使用任意 lattice 进行高维高斯滤波的基本框架

• Splatting：把低维的输入信号 splat/embed 在一个更高维的欧式空间。
  • 也就是说，对于每一个数据点中的单点，把单点的数据值累积在一个或多个高维 lattice 点上；如果累积在一个点上，类似于量化；如果累积在多个点上，就类似于插值；
  • 注意如果是多个点，就需要定义某种合适的插值权重；对于 $\mathbb{Z}^d$ 这个regular 点阵，插值权重就是多线性插值的权重；对于一般的 lattice 点阵，可以把数据点的值 splat 到包含数据点的那个 Delaunay cell 上，插值权重很自然地可以使用质心坐标
• Blurring：在已经积累好值的点阵上，每个 lattice 点上的值都被其邻居 lattice 点值所 blur/模糊；blur 权重依据 lattice 点之间的 L2 距离的高斯来衰减
  • 这里比较 tricky 的地方就是某个 lattice 点的“邻居lattice点”应该怎么寻找。对于 $\mathbb{Z}^d$ 这个regular 点阵，因为多个维度是可分的，分开每个维度找邻居即可；但是一般的 lattice 的多个维度不是可分的。
• Slicing：用和 splatting 时相同的权重，把 blur 好值的 lattice 点上的值重新组合到原数据点位置上。

$\mathbb{Z}^2$ 点阵 和 $A^\ast_2$ 点阵的 splat 过程示意

基本定义与结构性质

关于维度

permutodral lattice 是存在于 (d+1) 维空间的一个定义式为 $\vec{x} \cdot \vec{1}=0$ （i.e. $x_0+x_1+\cdots x_d=0$） 的 d 维 超平面 $H_d$ 上的。

后文中的主要讨论、主要坐标操作，本质上是在 (d+1) 维空间的 (d+1) 维 齐次 坐标上操作的；

不过，由于 (d+1) 维空间 $\mathbb{R}^{d+1}$ 的一个 d维超平面本身 和 d 维欧式空间 $\mathbb{R}^d$ 是 isometric (等距) 的，因此后文中许多针对存在于这个 d 维超平面上的几何对象的讨论事实上都是使用的其在 d 维空间下的性质和定义，只不过操作的坐标是 (d+1) 维的。

主要的符号定义

基本定义

• [Definition 1.1] 一个 lattice $L$ 的定义是在一个欧式空间中的 离散的 (discrete) 加法子群 (additive subgroup)。
  • 所谓加法子群，就是指这个群在加法和减法运算下是闭合的，也就是群中的任意两个点互相加减后也仍然在群中
  • 一个离散的点集是一个加法子群，也就意味着集合中的任意一个点可以用 frame 向量（类似于向量空间的基向量）的整数倍权重线性组合表示
  • 通俗地来讲，就是一种离散的规律点阵
• [Definition 1.2] 对于 lattice 中某个点的 Voronoi cell 就是指在连续空间中距离该点比其他lattice点更近的区域（点集）
  • 点阵的 Voronoi cell 是均匀的，并且堆积/密铺 (tesellate) 了这个空间。
• [Definition 1.3] 一个点阵的 Delaunay cell 就是指那些 voronoi cell 有公共顶点的 lattice 点们的凸包
  • Delaunay cell 是 Voronoi cell 的对偶 (dual)
  • Delaunay cell 很自然地找出了对连续空间中任意一个点的“附近”的 lattice 点
  • Delaunay cell 也是 permutohedral lattice 的插值过程的操作关键（使用质心坐标）

	$\mathbb{Z}^2$ lattice	$A^\ast_2$ lattice
Voronoi cell
Delaunay cell

• [Definition 2.1] The root lattice $A_d$: 存在于 d 维超平面 $H_d$ 的 “the root lattice”: $\lbrace \vec{x}=(x_0,x_1,\cdots,x_d)\in \mathbb{Z}^{d+1} \mid \vec{x}\cdot\vec{1}=0\rbrace$

  • 也就是落在 $H_d$ 上的那些整数坐标点集；整数坐标点集和超平面 $H_d$ 的交集

• [Definition 2.2] The permutohedral lattice $A^\ast_d$ : 存在于 d 维超平面 $H_d$ 的与 root lattice $A_d$ 对偶的 lattice: $A_d^\ast:=\left\lbrace \vec{x}\in H_d \mid \forall \vec{y}\in A_d , \vec{x}\cdot\vec{y}\in\mathbb{Z}\right\rbrace$

  • 也就是那些在超平面 $H_d$ 上，与 root lattice $A_d$ 中任意一点的点积都是整数的点的集合，就是 $H_d$ 上的 permutohedral lattice
  • 这里的定义并不常用，因为这样的定义下 $A_d^\ast$ 中有非整数的坐标，（roughly speaking，最小单位是 1/3）
    • 比如，这样定义下的 $A_2^\ast$ (i.e. $d=2$) 点阵的 frame 向量（基向量）可以是 $\left(\frac{1}{3},\frac{1}{3},-\frac{2}{3}\right), \left(\frac{1}{3}, -\frac{2}{3}, \frac{1}{3}\right)$
    • 比如 $\left(\frac{1}{3},\frac{1}{3},-\frac{2}{3}\right)$, $\left(\frac{2}{3},\frac{2}{3},-\frac{4}{3}\right)$, $\left(\frac{3}{3},\frac{3}{3},-\frac{6}{3}\right)$ 都是 $A^\ast_2$ 点阵中的点

• [Definition 2.3] Permutohedral lattice 的最常用的、最能揭示其性质的两种定义，也是与 [Definition 2.2] 把坐标缩放 (d+1) 倍等价的定义

  • 等价定义式2.2: $A^\ast_d:=\lbrace T(\vec{x}) \mid \vec{x} \in (d+1)\mathbb{Z}^{d+1}\rbrace$，其中 T 是 $\mathbb{R}^{d+1}$ 中任意一点到 $H_d$ 的投影函数 $T:\vec{x}\mapsto\vec{x}-\left(\frac{\vec{x}\cdot\vec{1}}{\vec{1}\cdot\vec{1}}\vec{1}\right)$
    • 也就是说，把 (d+1) 倍整数点们投影到超平面 $H_d$ 上的新点的集合
  • 等价定义式2.3: $A^\ast_d:=\bigcup_{k=0}^d \lbrace \vec{x}\in H_d \mid \vec{x} ; \text{is a remainder-k point}\rbrace$
    • 也就是说，在超平面 $H_d$ 上（即需要满足坐标之和为0），从 k=0 到 k=d 的所有那些坐标各个分量除以 (d+1) 同余k 的点的集合。
      • “所有坐标除以 (d+1) 同余 k” 的英文表达：all coordinates are congruent to k modulo d+1
    • 🚀 对于所有k=0到d的余k点的集合这一定义，是后文对 $H_d$ 上任意一连续点寻找其周围的 lattice 顶点的主要依据
    • 这样，$A_d^\ast$ 中任意一点 $\vec{x}$ 都可以写作 $\vec{x}=(d+1)\vec{y}+k\vec{1}$ for some $\vec{y}\in \mathbb{Z}^{d+1}$ 。这个形式是后文中很多证明的基础
      • 这个式子本质上也就是把 $(d+1)\vec{y}$ 这个点沿着 $\vec{1}$ 向量方向的投影（也就会投影到 $H_d$ 上）

root lattice $A_d$ 与 permutohedral lattice $A^\ast_d$ 到底有什么不同？

很遗憾，在我们最容易可视化看到 lattice 顶点的 $d=2$ 的情况下，$A_2$ 事实上只是 $A^\ast_2$ 的一种旋转+缩放，很容易让人产生这两种 lattice 没有差别的误解。

如下图：$d=2$ 的情况下，黑色点（包括所有红色点覆盖的黑色点）即为 root lattice $A_2$，红色点即为 permutohedral lattice $A^\ast_2$，而蓝色点是 permutohedral lattice 缩放 (d+1) 倍前的定义。容易看到，$A^\ast_2$ 其实就是 $A_2$ (在 $H_d$ )旋转60度再缩放一定倍数，Voronoi cell 都是正六边形，Delaunay cell 都是3个顶点的正三角形。

不过，作为读者，我们仍然可以试着观察计算 $d=3$ 时的 $A_3$ 和 $A^\ast_3$ 的 3维多面体 Voronoi cell 和 Delaunay cell 来观察这种区别。

	Root lattice $A_3$	Permutohedral lattice $A^\ast_3$
顶点位置可视化	面心立方格点 - FCC (Face-Centered Cubic) The A3 root lattice is known to crystallographers as the face-centered cubic (or cubic close packed) lattice.	体心立方格点（绿点） - BCC (Body-Centered Cubic) （BCC 其实是 $D^\ast_3$，不过因为有 $D_3=A_3$） 其Voronoi cell 是 截角八面体（图中红框） Entezari, Alireza, Dimitri Van De Ville, and Torsten Moller. “Practical box splines for reconstruction on the body centered cubic lattice.” IEEE Transactions on Visualization and Computer Graphics 14.2 (2008): 313-328.
Voronoi cell 形状	Rhombic dodecahedron (菱形十二面体)	截角八面体 (truncated octahedra / bitruncated cubes / 4-permutohedron)
Voronoi cell 的 tesellation	Rhombic dodecahedral honeycomb (菱形十二面体堆砌) It is the Voronoi diagram of the face-centered cubic sphere-packing	Bitruncated cubic honeycomb (截角八面体堆砌)
Delaunay cell 顶点个数	$\begin{cases} \begin{pmatrix} 4\\1 \end{pmatrix}=4 & k=1 \\ \begin{pmatrix} 4\\2 \end{pmatrix}=6 & k=2 \\ \begin{pmatrix} 4\\3 \end{pmatrix}=4 & k=3 \end{cases}$	$d+1=4$
Delaunay cell		上图红边为下图黑边，长度 1；上图蓝边为下图红边，长度 $\sqrt{3}/2\approx 0.866$

结构性质

$(d+1)-\text{permutohedron} \overset{\text{Voronoi cell}}{\underset{\text{tesellelation的位置}}{\leftrightarrows}} A^\ast_d \overset{\text{Delaunay cell}}{\rightarrow} d-\text{simplex}$

• 正如其他 lattice 一样，$A^\ast_d$ 这个 lattice 的 voronoi cell 也引入了一种在超平面 $H_d$ 上的 tesselation (堆积)。
• [Proposition 2.4] $A_d^\ast$ 的 Voronoi cells 在原点处的那个 cell 是一个带着这样顶点 $\left\lbrace \rho \left( \frac{d}{2}, \frac{d-2}{2}, \dots, \frac{-d+2}{2}, \frac{-d}{2} \right) \right\rbrace$ 的 permutohedron
  • 这也是 permutohedral lattice 的命名由来
  • $\rho$ 是 (d+1) 个元素的对称群；对称群就是所有排列的集合

• [Therorem 2.5] $A^\ast_d$ 的 Delaunay cell 是 d维单纯形，并且通过转置和平移都可以和一个canonical simplex重合
  这个 canonical simplex 带有这 (d+1) 个顶点坐标：
  • $(0,0,\dots,0,0,0)$ （除以(d+1)余0点）
  • $(\underbrace{1,1,\dots,1,1}_{d},-d)$ （除以(d+1)余1点）
  • $\cdots$
  • $\underbrace{k,\dots,k}_{d+1-k}, \underbrace{k-(d+1),\dots,k-(d+1)}_{k}$ （除以(d+1)余k点）
  • $(d,\underbrace{-1,\dots,-1,-1,-1}_{d})$ （除以(d+1)余d点）

NOTE:

• Delaunay cells 的顶点就是距离某点 $\vec{x}$ 最近的 lattice 点们。利用最近求一个 argmin，就可以证明这些原点处的 Delaunay cell 确实就是上面这些坐标。
• 注意这里是在 $H_d$ 超平面视角下的一个 d-simplex，其顶点坐标其实是 (d+1) 维的，只不过在 $H_d$ 上看的话这 (d+1) 个顶点是存在某种仿射不相关的 d 维坐标的，所以还是能够构成一个 $H_d$ 超平面上的 d 维单纯形

d=3时，permutohedral lattice 的 Voronoi cell 和 Delaunay cell 举例

• $A^\ast_d$ 的 Voronoi cell 是一个 d+1-permutohedron
• $A^\ast_d$ 的 Delaunay cell 是一个 d-simplex

$A_3^\ast$ 的 Voronoi cell 是一个3维空间中的正截角八面体 (uniform truncated octahedron)	$A_3^\ast$ 的 Delaynay cell 是一个3维空间中的等腰四面体 (isosceles tetrahedron)
	注意蓝边红边不等长，这只是一个等腰四面体，并不是正四面体

• [Corollary 2.6] $A^\ast_d$ 的每一个 Delaunay cell 对于某个固定的k，只会包含一个 余k 点
• [Corollary 2.7] 🚀 对于超平面 $H_d$ 上任意一点 $\vec{x}\in \mathbb{R}^{d+1} $，包含它的 Delaunay cell 的 (d+1) 个顶点就是距离点 $\vec{x}$ 最近的 (d+1) 个余k点（$k\in\lbrace0,1,\dots,d\rbrace$）
  • 这里就是计算包含点 $\vec{x}$ 的 Delaunay cell 顶点的依据
  • 注意这里的 $\vec{x}$ 还有那 (d+1) 个余k点顶点的坐标都是 (d+1) 维的，只不过他们都存在于(位于) d维超平面 $H_d$ 上，而 $H_d$ 和一个 d 维欧式空间是 isometric 的
• [Lemma 2.9] 对于 $H_d$ 上任意一点 $\vec{x}$，找到最近的余-0点的步骤是
  • 先找到离 $\vec{x}$ 最近的 (d+1) 整数点 $\vec{y}$
  • 计算差分 $\vec{\Delta}=\vec{x}-\vec{y}$， $h=\frac{\sum_{i=0}^d y_i}{d+1}$
  • 如果 $h<0$，那么对属于 $|h|$ 个差距最大的那些 $\Delta_j$，给 $y_j$ 分量加上 (d+1) 如果 $h>0$，那么对属于 $|h|$ 个差距最小的那些 $\Delta_j$，给 $y_j$ 分量减去 (d+1)
    • 比如，假设 d=3，$\vec{\Delta}=\lbrace 1,3,5,2\rbrace$，$h=2$，那么我们要给 $\vec{\Delta}$ 中最大的2个分量对应的 $y_j$ 加上 (d+1)（也就是 3,5 对应的 $y_1$ 和 $y_2$）
• [Theorem 2.10] 对于 $H_d$ 上任意一点 $\vec{x}$，找到包含它的那个 Delaunay cell 顶点的步骤是
  • 先找到最近的余0点 $\vec{y}$
  • 计算差分 $\vec{\Delta}=\vec{x}-\vec{y}$
  • 找到能够把 $\vec{\Delta}$ 从大到小排序的排列方式 $\rho$
  • 对于 k=0 到 d，距离 $\vec{x}$ 最近的余k点的计算方式就是 $\rho^{-1}(\vec{\nu}_k)+\vec{y}$，其中 $\vec{\nu}_k$ 是 canonical simplex 中的余k点

Permutohedral lattice 是各种 lattice 中理论最好的

评估准则 criteria

根据利用 lattice 进行高维高斯滤波的基本框架，我们可以制定这样的一套评判准则来评估怎样是好的 lattice 点阵配置：

• (translational symmetry 平移对称性) 对于空间中的任意一点，splatting, blurring 和 slicing 的基本单元应该是空间不变的。
  • 这条基本只要是 lattice 就能满足，by definition
• (even distribution 均等的分布) lattice 点在空间中的分布要尽可能的 even and isotropic (均等、各向同性)。
  • 毕竟我们是先 splat 到离散的点阵上、在模糊后、重新组装到原连续位置上的，这条要求本质上就是为了让这种离散的滤波过程尽可能接近于(或者说恢复出,resemble) 直接在连续空间上进行滤波的结果。
• (fast splat and slice) 对于空间中任意一点，应该能够快速地、系统性地找到这个点的附近的 lattice 点，而且 lattice 点的个数随着维度d的提升速度越慢越好。
• (fast blur) 对于任意一个 lattice 点，应该能够快速地、系统性地找到它附近的 lattice 点是哪些。
• (generality) 所设计的 lattice 应该在任意维度都是存在的。

总共有哪些可能的 lattice

lattice 总是由一些 root lattice 及其对偶定义的。幸运的是，有限维度的 irreducible root lattices 是能够被完全穷举的。

总共讨论哪些可能的 lattice，及其 Delaunay cell 的顶点个数

最理想的 lattice：permutohedral lattice

• (even distribution 均等的分布) ：一直到d=22维，permutohedral lattice 是目前已知最好的 sphere covering 问题的 lattice
  • sphere covering 问题，就是在每个 lattice 点上放一个正球能 cover 整个空间的前提下，找一种相对密度最小的 lattice
  • 这从直觉上大概证明了 permutohedral lattice 是分布最均匀的
• (fast splat and slice) 在可能的几种 lattice 中，permutohedral lattice 的 Delaunay cell 是 顶点个数最少的，并且是理论上最少的；而且顶点个数随着 维度d 的提升也是最慢的
  • d 维空间中，能够存在的顶点个数最少的 polytope，就是一个单纯形，顶点个数为 d+1
• (fast blur) permutohedra 找邻居不如 $\mathbb{Z}^d$ 快，但也算是很快了

算法

具体如何使用 permutohedral lattice 进行高维高斯滤波；最主要的就是具体如何计算 permutohedral lattice 的插值权重，来进行 splatting 和 slicing 过程

质心坐标计算插值权重

Permutohedra lattice 的 Delaunay cell 就是 d-simplices (d维单纯形)

📌 对于单纯形来说，最自然的插值权重就是质心坐标（barycentric coordinates）

• [Lemma 4.1] canonical simplex 中任意一点的质心坐标计算方式：
  记 canonical simplex 的 remainder-k 顶点为 $\vec{\nu}_k$ ; $\vec{x}$ 是 canonical simplex 中的任意一点; $b_0, \dots, b_d$ 是 $\vec{x}$ 的质心坐标
  • 也就是说: $\vec{x}=\sum^d_{k=0} b_k \vec{\nu}_k \; \text{and} \; \sum^d_{k=0} b_k=1$
  • 那么，$b_k$ 的计算方式是：$b_k= \begin{cases} \frac{x_{d-k} - x_{d+1-k}}{d+1} & k \neq 0 \\ 1-\frac{x_0-x_d}{d+1} & k=0 \end{cases}$
    • 注意到 $b_k$ 的计算来源就是一些 $x_k$ 的坐标
• [Proposition 4.2] 空间中任意一点的质心坐标计算方式：
  $\forall x \in H_d$ ，记其所处的 Delaunay cell 的 余k点顶点为 $\vec{\nu}_k$ ，记 $\rho$ 为让 (d+1) 维向量 $\vec{\Delta}=\vec{x}-\vec{\nu}_0$ 从小到大排序的排列，那么 $\vec{x}$ 的质心坐标权重向量 $\vec{b}$ 的计算方式为：
  • $b_k= \begin{cases} \frac{\rho(\vec{\Delta})_{d-k} - \rho(\vec{\Delta})_{d+1-k}}{d+1} & k \neq 0 \\ 1-\frac{\rho(\vec{\Delta})_0-\rho(\vec{\Delta})_d}{d+1} & k=0 \end{cases}$