Shape Analysis课程笔记21-Consistent Correspondence

这个系列是MIT 6.838: Shape Analysis的同步课程笔记。本课程会介绍几何方法在图形学、机器学习、计算机视觉、医疗图像以及建筑设计等相关领域的原理和应用。本节介绍曲面对应中的一致性问题。

Cycle Consistency

上一节课我们介绍了曲面对应问题，它可以理解为寻找连接两个曲面之间的映射\(\phi\)。

如果把这样的映射复合起来，我们就需要考虑一致性(consistency)的问题。以下图为例，如果我们把所有的映射复合到一起应该得到一个恒等映射，但遗憾的是我们在构造每一个单独的映射时都没有考虑这样的约束。

一致性约束在表达形式上非常简单，但求解带有这样约束的优化问题往往是非常困难的。

本节课我们会介绍构造和求解一致性约束的常见方法。

生成树(spanning tree)在三维重建的配准问题中有着大量的应用。具体来说我们会在不同的位置以不同的角度拍摄同一个物体，每个相机都只能得到该物体的一部分投影，配准的目标是把这些有限的局部信息组合起来得到完整的三维模型。

相机的位姿之间构成了一张位姿图，其中每一个生成树都可以实现完整模型的配准。然而遗憾的是寻找具有最大一致性的生成树是NP-hard，目前工程中一般都是使用一些启发式算法来构造生成树。

为了避免匹配不一致的问题人们还提出了inconsistent loop detection这样的技术来检测位姿图上的不一致环(边)。

我们可以把映射看做是一个由0和1构成的矩阵，它的每一行每一列都只有一个1表示对应关系。这样的矩阵称为permutation matrix。

直接对permutation matrix进行优化往往比较困难，更为常见的形式是对其进行放松使得每一行以及每一列的和为1。此时的矩阵称为doubly-stochastic matrix。

在图像生成领域中著名的CycleGAN就利用了一致性的思想来训练一对生成器。

本节课的extra content介绍了angular synchronization问题以及相关的求解方法。在angular synchronization问题中，我们需要计算不同含噪声信号之间的「角度」差异从而将这些信号进行对齐。

angular synchronization问题的一个特点在于角度会根据\(2 \pi\)发生混淆，这种现象称为\(2 \pi\) ambiguity。不过利用复数我们可以避免角度在表示上的各种问题：

\[e^{i \ \theta_j} \cdot e^{i \ \delta_{ij}} \approx e^{i \ \theta_i}\] \[z_j \cdot H_{ij} \approx z_i\]

其中\(z_j = e^{i \ \theta_j}\)，\(H_{ij} = e^{i \ \delta_{ij}}\)。对上式两边乘以\(z_i\)的共轭可以得到：

\[\bar{z_i} \cdot H_{ij} \cdot z_j \approx 1\]

这样，angular synchronization可以表示为最小二乘问题：

\[\min \sum_{ij} \vert \bar{z_i} \cdot H_{ij} \cdot z_j - 1 \vert^2 = \max \sum_{ij} \text{Re} [\bar{z_i} \cdot H_{ij} \cdot z_j]\]

显然这样的优化问题非常难以进行处理。为了方便进行求解，作者提出了两种relaxation方式。其一是转换为最大特征值问题：

第二种relaxation方法是利用半正定规划(semi-definite programming, SDP)：

在标准angular synchronization问题的基础上我们还可以进行拓展。