Shape Analysis课程笔记21-Consistent Correspondence

Created in February 16, 2023

2023 · CG Geometry-Processing · Shape-Analysis

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

Cycle Consistency

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

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

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

Consistent Correspondence

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

Spanning Tree

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

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

Inconsistent Loop Detection

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

Fuzzy Correspondence

Consistent Segmentation

Convex Optimization

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

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

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

Angular Synchronization

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

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

e^{i θ_{j}} \cdot e^{i δ_{i j}} \approx e^{i θ_{i}}

z_{j} \cdot H_{i j} \approx z_{i}

其中 $z_{j} = e^{i θ_{j}}$ ， $H_{i j} = e^{i δ_{i j}}$ 。对上式两边乘以 $z_{i}$ 的共轭可以得到：

\bar{z_{i}} \cdot H_{i j} \cdot z_{j} \approx 1

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

min \sum_{i j} | \bar{z_{i}} \cdot H_{i j} \cdot z_{j} - 1 |^{2} = max \sum_{i j} Re [\bar{z_{i}} \cdot H_{i j} \cdot z_{j}]

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

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

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

Reference