Shape Analysis课程笔记20-Correspondence Problems

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

Surface Correspondence Problems

曲面对应(surface correspondence)是指寻找两个曲面的对应关系。以人脑MRI为例，我们知道大脑皮层的不同区域有着相应的功能，很多时候我们需要将两个大脑具有相同功能的区域进行匹配。从几何的角度来看，这样的任务本质是计算两个曲面的对应关系。

与曲面对应类似的一个常见任务是配准(registration)。二者的主要区别在于配准一般是计算同一物体不同表示之间的对应关系，它的输出一般是不同表示之间的刚性变换；而曲面对应则不仅仅考虑同一个物体的情况，实际上即使是不同类型的物体在很多时候也存在一定的对应关系。

Applications

曲面对应在各种实际工程中都有着大量的应用。在图形学中我们可能会希望把一个模型的纹理变换到另一个模型上，这样的任务需要就需要计算两个不同模型之间的对应关系，称为纹理迁移(texture transfer)。

类似地，网格的分割也可以考虑使用曲面对应来进行处理：我们可以先在一个相对简单的模型上进行精细的分割，然后利用曲面对应把分割结果映射到新的模型上。

计算网格的骨架也可以使用类似的方法。

基于曲面对应的思想，我们可以把人脸的不同表情对应到一个基准模型上，然后通过插值来实现表情的混合。

当然曲面对应也可以用来进行形状分析。实际上很多形状分析算法都会使用曲面对应技术作为分析前的预处理，这样可以去除各种曲面扫描产生的误差。

Geometric Quality

从数学的角度来看，曲面对应的本质是计算两个(或多个)曲面之间的映射\(f\)。当然我们希望\(f\)比较易于计算，同时具有双射、低扭曲以及保持原有曲面几何特征等优良性质。

实际上低扭曲是一个相当高的要求，很多全局看上去正确的映射在局部可能会有过大的几何扭曲。

在比较不同的映射时，一种常见做法是统计曲面不同位置映射后与ground truth之间的累计误差。不过需要注意的是几何扭曲大的映射有时反而会有更小的累计误差，因此在设计和比较算法时往往还需要在映射的误差和光滑性上进行权衡。

在一些更现代的工作中人们常常会使用共形扭曲来衡量映射的质量，其描述了映射保持曲面上角度的能力。

Strategies

接下来我们开始介绍曲面对应的一些常见策略。

Co-Parameterization

Co-Parameterization是计算曲面对应的经典方法。它的思路是首先在不同的网格上选取相互对应的landmark，然后利用landmark之间的连接关系将网格划分为相互对应的patch，相互对应的patch具有相同的拓扑关系。

这样在对应的patch上就可以利用参数化这样的技术将它们映射到相同的参数域上，进而得到分片网格的对应关系。

Co-Parameterization的优势在于它比较容易实现，而且基于Tutte’s embedding可以保证计算得到的曲面对应函数\(f\)是一个双射；而其缺陷则在于它需要手动选取曲面上相互对应的landmark，而且往往具有比较大的几何扭曲。

近几年有一些针对传统Co-Parameterization方法的改进，通过自动选取landmark来减少几何扭曲。

而一些对于Tutte’s embedding的改进还可以让我们处理具有不同拓扑的网格和区域。

值得说明的是Co-Parameterization的思想不仅仅局限于图形学相关的应用中，在神经科学和脑科学中常用的FreeSurfer实际上也使用了类似的技术。

另外需要注意的是Co-Parameterization的质量在很大程度上依赖于选择的参数化算法，除了Tutte’s embedding之外还可以考虑很多更现代的算法。

这里我们简单介绍一些SLIM算法，它是最近几年比较有代表性的工作。首先来考虑平面三角形的变形，变形函数\(\phi_t\)可以表示为一个线性变换：

\[\phi_t (x) = J_t x + c\]

其中\(c\)为三角形的平移，因此\(\phi_t\)的几何扭曲完全由Jacobian矩阵\(J_t\)控制。这样整个三角形网格上的扭曲可以描述为：

\[\sum_{t \in T} A_t \ \mathcal{D}(J_t)\]

其中\(A_t\)为每个小三角形的面积，而\(\mathcal{D}(J_t)\)为扭曲的度量函数。

这样整个参数化问题就可以转换为针对三角形Jacobian矩阵的优化问题，我们就可以利用各种优化器来进行求解。一些常用的扭曲度量函数可参考如下：

Generalized MDS

在经典Co-Parameterization的基础上，一些近期的研究指出通过保持曲面上的一些长距关系可以得到更稳定的结果。

这里我们需要引入Gromov-Hausdorff距离(Gromov-Hausdorff distance)的概念，它描述了两个度量空间\(X\)和\(Y\)之间的距离。

Generalized MDS(GMDS)算法可以理解为在两个曲面上对Gromov-Hausdorff距离进行优化。

从更通用的形式来看，GMDS等价于求解quadratic assignment。不过遗憾的是直接求解quadratic assignment是NP-hard。

同时还需要注意在求解时可能会出现各种局部极值。

总之，GMDS相关方法的难点在于我们很难进行求解。很多情况下需要使用各种技巧才能进行处理。

一些近期的研究还指出GMDS可以结合最优传输理论进行理解。

除此之外GMDS也可以结合convex relaxation这样的技巧来进行加速。

Heat Kernel Map

如果两个曲面之间仅相差一个等距变换，我们则可以使用heat kernel signature来计算曲面对应。此时只需要分别计算曲面上每个顶点的descriptor然后进行匹配即可。

当然，如果两个曲面之间偏离了等距变换这种方法可能无法得到正确的结果。

Möbius Voting

在很多情况下曲面之间等距变换的约束可能过强，因此一种常见的策略是将等距变换放松为共形映射(conformal mapping)。和等距变换相比，共形映射仅能保持角度不变而不再保证距离不变。

使用共形映射计算曲面对应的基本思路是首先将两个曲面分别共形参数化到(复)平面上，然后再寻找这两个(复)平面之间的共形映射。

而平面之间的共形映射可以使用Möbius变换(Möbius transform)进行描述。

把这些步骤组合到一起就得到了Möbius voting算法：它会在(复)平面上不断选取triplet来计算Möbius变换，而其中具有最小几何扭曲的那个构成了所需的曲面对应。

显然Möbius voting算法非常高效，但它无法保证一定能找到最优的对应，而且仅适用于亏格为0的曲面。

Blended Intrinsic Map

在Möbius voting的基础上人们还提出了blended intrinsic map的技术，它会利用不同的triplet来计算曲面对应，然后把它们组合起来作为最终的对应。

Functional Maps

Reversible Harmonic Maps

本节课的extra content介绍了reversible harmonic maps这种技术。reversible harmonic maps可以用来处理dense correspondence的问题，此时我们已知两个曲面上几对landmark之间的对应关系，而目标是计算网格上其它顶点之间的对应关系。