Multidimensional Scaling（MDS多维缩放）算法及其应用

在这篇博客中，我将与大家分享在流形分析领域的一个非常重要的方法，即多维缩放MDS。整体来说，该方法提供了一种将内蕴距离映射到显性欧氏空间的计算，为非刚性形状分析提供了一种解决方案。当初就是因为读了Bronstein的相关工作【1】，才下定决心在人脸数据分析中使用内蕴度量来建立特征分析方法，可以说MDS对我的学术之路起到了很大的影响作用。

---

1. 前言

在非刚性形状匹配中，我们希望找到两个曲面的对应关系。由于受到非刚性形变影响，使得我们不能直接建立基于类似ICP一样的方法来实现对准。提到非刚性分析，很自然的就会让人联想到使用基于曲面第一基本形式的内蕴几何特征来建立分析方法。对于人脸人体这种非刚性形变分析对象，由于受到骨架的约束，使得其非刚性形变满足近似等距的特性，这里的等距指测地线。曲面第一基本形式对应曲面曲线，刚好可以使用测地线作为表示。那么，我们只要基于测地线来建立几何特征表达，就能够实现近似等距条件下的形状分析，进而满足非刚性形状分析要求。

关于测地线的计算，我在之前的博客已经有所介绍，有兴趣的同学可以翻看：

Fast Marching算法及其在点云测地线计算中的应用-CSDN博客

Geodesic in Heat: 一种测地线计算方法-CSDN博客

在有了测地线作为内蕴几何特征的显性表示后，我们希望对原始曲面建立一种形状度量，这种度量由测地线定义，能够反映形状之间的相似程度，进而推出点的对应关系。一个最直接的想法是利用参数化的方法。通过参数化，我们能够对原始的曲面进行“摊平”，进而在摊平后的参数域建立对应。然而，参数化需要指定边界和控制点，其本身的计算也相对复杂。如果对于拓扑相对复杂的形状建立参数化，其对原始测地线距离将会产生严重扭曲，即不再是可控的近似等距变换。我们希望使用类似ICP那样的直接距离对应方法，对基于测地线表示的曲面进行匹配。一个理想的方案是将点对间的测地距离，变换到一个m维的欧氏空间。在该欧氏空间中，点与点的欧氏距离与未变换前的点对测地距离存在一种对应关系。这样，我们只需要在变换后的形状进行刚性配准，点对的结果就对应了原始数据的非刚性对应结果。这就是使用MDS方法实现非刚性形状分析的初始想法。

---

2. MDS介绍

如前所述，MDS的目的就是将点间的测地距离嵌入到一个新的欧氏空间中，使得内蕴距离获得显性化的表达。在相关工作【2】中，这种嵌入后的曲面表达被称为bending-invariant canonical forms。具体过程如下：

首先我们给出一个测地线的表示δij，表示两点pi和pj的测地距离。我们把所有点的行列组成矩阵形式，使用δij填满，ij相等为0。然后，我们对δij求平方，重写矩阵里的项：

Δ所表达的矩阵在等距变换下是不变的，但是其形式会因为点序号的变化而变化。我们希望获得一个测地距离不变的表示，且具有唯一性。这时，就可以利用MDS将其嵌入到一个低维的欧氏空间中，该过程等价于：

嵌入误差可以写为：

MDS方法也包含很多类别，Bronstein在论文【3】中提到一种称为classical scaling【4】的方法来实现MDS：

首先对Δ进行中心化操作，即double-centering。J=I-1/2U，I是单位矩阵，U是一个完全由1组成的矩阵。之后对B进行主成分分析，获得对应的m个特征值和特征向量：

i对应点的序号，j对应m的维度，一般m取3，即将原始形状基于测地距离映射会三维欧氏空间。这样经过特征向量e表达的新坐标x在欧氏空间组成一个新的形状，在工作【1】中被称为Canonical form，以我的观点来看，即内蕴型。

---

3. 应用

Bronstein在最开始设计算法的时候，目标就是解决三维人脸识别中的表情鲁棒问题。他在论文中已经提到了一般性非刚性形状分析可以转换为对内蕴距离向欧氏空间的嵌入，如下图：

上面的例子充分说明将测地线嵌入回欧氏空间，对应的形状所具备的近似等距特性。原来手指的欧氏距离，一定会因为非刚性形变发生变化，但是对应的测地距离是稳定的。将测地距离嵌入回欧氏空间，得到右边的Canonical form，其点的欧氏距离就具备了原来点的测地距离特性。这时我们再使用类似ICP的方法，就能够非常方便的建立对应关系。

表情即被认为是一种近似等距的非刚性形变，如果我们对人脸数据进行类似Canonical form的变换，那么变换的结果自然会获得对表情不变的结果。原论文中给出了示意图：

可以看到第一行的人脸是具有多种不同的表情的。但是这些人脸的Canonical form具有极其相近的几何表示。在Canonical form的基础上，设计三维人脸识别算法，自然能获得表情鲁棒特性。论文中还给了一个系统界面：

整个算法流程还是非常清晰的。但是求Δ需要的庞大计算量，限制了该算法的效率。

Reference

[1] Bronstein AM, Bronstein MM, Kimmel R. Three-dimensional face recognition[J]. International Journal of Computer Vision, 2005, 64: 5-30.

[2] Elad A, Kimmel R. Bending Invariant Representations for Surfaces[C]. Proceedings of the Conference on Computer Vision and Pattern Recognition, 2001, 2: 168-168.

[3] Bronstein AM, Bronstein MM, Kimmel R. Expression-invariant 3D face recognition[C]. International conference on Audio-and video-based biometric person authentication, 2003: 62-70.

[4] Young G, Householder A S. Discussion of a set of points in terms of their mutual distances[J]. Psychometrika, 1938, 3(1): 19-22.