这个系列是MIT 6.838: Shape Analysis的同步课程笔记。本课程会介绍几何方法在图形学、机器学习、计算机视觉、医疗图像以及建筑设计等相关领域的原理和应用。本节主要介绍Laplace算子的性质和应用。
在前面两节课中我们介绍了Laplace算子的概念。从某种意义上讲,我们可以利用Laplace算子来提取函数(形状)的频率。
![](https://search.pstatic.net/common?src=https://i.imgur.com/flgSuTQ.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/v4fxeuy.png)
在三角网格上Laplace算子与对角的正切有关,因此也称为cotangent-Laplacian。而对于点云等其它形式的几何对象,我们同样可以利用离散化的方法来推导相应的Laplace算子。
![](https://search.pstatic.net/common?src=https://i.imgur.com/ow3dEnI.png)
cotangent-Laplacian的一个重要性质是稀疏性(sparsity)。实际上Laplacian算子(矩阵)上每个顶点只在其相邻顶点的位置上有非零元素,而其它形式的Laplacian算子也都具有类似的形式。
![](https://search.pstatic.net/common?src=https://i.imgur.com/23AcLGo.png)
本节课中我们会介绍Laplace算子的一些常用性质,然后讨论它在几何处理、机器学习等领域的应用。
![](https://search.pstatic.net/common?src=https://i.imgur.com/DKH727I.png)
Properties of the Laplacian
Many Interpretations
Laplace算子有很多种理解方式。从图论的角度来看,Laplace算子描述了图上节点与其相邻节点之间的差异。
![](https://search.pstatic.net/common?src=https://i.imgur.com/NwxROEV.png)
从能量的角度来看,Laplace算子与函数的Dirichlet能量密切相关,它描述了函数\(f\)的光滑程度。
![](https://search.pstatic.net/common?src=https://i.imgur.com/bJnFPqz.png)
当然在前面的课程中我们也提到过Laplace算子描述了函数的频率和模态。
![](https://search.pstatic.net/common?src=https://i.imgur.com/8hqUFID.png)
Isometric Invariants
对于三角网格,我们可以发现cotangent-Laplacian算子只与三角形的内角以及面积相关。这说明当网格发生一些变化时Laplace算子可能是不变的。
![](https://search.pstatic.net/common?src=https://i.imgur.com/zSr905K.png)
一些其它形式的Laplacian算子也具有类似的性质。
![](https://search.pstatic.net/common?src=https://i.imgur.com/RCrjaSf.png)
实际上Laplacian算子是内蕴算子(intrinsic operator),它只与测地距离相关而与流形的具体嵌入方式无关。因此当曲面发生等距变换(isometric transformation)时,Laplacian算子保持不变。
![](https://search.pstatic.net/common?src=https://i.imgur.com/AH4xmn2.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/UUHKZ9e.png)
在很多任务中我们都希望曲面关于等距变换保持不变,比如说人体在不同姿态下的形状是不变的。
![](https://search.pstatic.net/common?src=https://i.imgur.com/hZuSy2N.png)
但遗憾的是只有极少数的曲面具有等距不变性,这样的曲面称为可展曲面(developable surface),而大多数曲面在变换前后都或多或少存在一些拉伸。
![](https://search.pstatic.net/common?src=https://i.imgur.com/rQQPxYM.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/vubHzW6.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/lhSasEp.png)
同时需要注意的是我们这里只考虑曲面上的Laplacian算子与等距变换,实体上的Laplacian算子有着完全不同的表达形式。
![](https://search.pstatic.net/common?src=https://i.imgur.com/9mdptML.png)
简单总结一下,Laplacian算子有非常丰富且优雅的数学性质而且与很多物理问题都有着深刻的联系。
![](https://search.pstatic.net/common?src=https://i.imgur.com/a5ZS7jb.png)
Applications in Shape Analysis
Shape Descriptor
Laplacian算子在形状分析中的一个经典应用是作为形状描述子(shape descriptor),将曲面映射到\(\mathbb{R}^n\)空间中。
![](https://search.pstatic.net/common?src=https://i.imgur.com/dqok6KW.png)
利用shape descriptor我们可以寻找曲面上一些具有某些特征的区域,或是对不同的曲面进行匹配。
![](https://search.pstatic.net/common?src=https://i.imgur.com/KwN21Oe.png)
我们在前面课程中介绍过的Gauss曲率和平均曲率都可以作为shape descriptor。
![](https://search.pstatic.net/common?src=https://i.imgur.com/BHAYt53.png)
显然一个好的shape descriptor需要具有可区分性(distinguishable)、稳定性(stable)以及内蕴性(intrinsic)等性质。
![](https://search.pstatic.net/common?src=https://i.imgur.com/mYGhjP3.png)
Intrinsic Descriptor
我们希望shape descriptor是关于刚体变换甚至等距变换的不变量,而利用Laplace算子构造的shape descriptor天然就具有这样的内蕴性。
![](https://search.pstatic.net/common?src=https://i.imgur.com/MMzNcxG.png)
除此之外,Gauss曲率同样是等距变换下的不变量。
![](https://search.pstatic.net/common?src=https://i.imgur.com/JSA1EoZ.png)
不过Gauss曲率在网格上一般会有比较大的噪声,而且无法区分所有的曲面。
![](https://search.pstatic.net/common?src=https://i.imgur.com/AmmRVMV.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/B66fTT8.png)
总之shape descriptor一般会融合曲面局部上的信息从而产生内蕴性,这样能够在一定程度上保证曲面发生比较小的变形时shape descriptor不会有太大的变化。
![](https://search.pstatic.net/common?src=https://i.imgur.com/9lcGFou.png)
Global Point Signature
Global Point Signature(GPS)是使用Laplace算子构造的shape descriptor。我们只需要对网格的Laplace算子进行特征分解,然后在每一点上赋予对应的特征向量即可。
![](https://search.pstatic.net/common?src=https://i.imgur.com/0ODVgJZ.png)
GPS的一个重要性质是当网格没有自相交时,GPS作为shape descriptor也不会出现相同的值。这条结论使得GPS有更好的可区分性。
![](https://search.pstatic.net/common?src=https://i.imgur.com/tgq9bE4.png)
而由于GPS是由Laplace算子构造的,它同样具有Laplace算子的等距不变性。
![](https://search.pstatic.net/common?src=https://i.imgur.com/MElFsx4.png)
Heat Kernel Signature
除了GPS之外,Laplace算子也可以构造出其它形式的shape descriptor。比如说热传导方程(heat equation)和波动方程(wave equation)就都包含了Laplace算子。
![](https://search.pstatic.net/common?src=https://i.imgur.com/KkQM6sh.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/3eJIpZv.png)
以热传导方程为例,当我们已知边界在初始时刻的温度\(u_0\)时温度\(u\)关于位置和时间的变化可以表示为Laplace算子特征值\(\lambda_n\)特征函数\(\phi_n\)的组合。
![](https://search.pstatic.net/common?src=https://i.imgur.com/3lh7IBy.png)
基于这种观察我们可以定义heat kernel signature(HKS),从传热的角度来看它描述了\(t\)时刻\(x\)向自身扩散的热量。
![](https://search.pstatic.net/common?src=https://i.imgur.com/pOwDZCP.png)
在几何处理中我们只需要计算Laplace算子的特征值和特征向量就可以构造HKS。当特征值的阶数比较低时,HKS对应曲面的局部信息;而当阶数比较高时,HKS则会结合一些全局的信息。
![](https://search.pstatic.net/common?src=https://i.imgur.com/do8y9aO.png)
HKS有很多优秀的性质,但需要注意的是当网格具有对称的结构时(Laplace算子具有重复的特征值)HKS会出现无法区分这些区域;同时HKS的不变性高度依赖于等距变换,当网格的变形比较大时HKS可能不再具有不变性。
![](https://search.pstatic.net/common?src=https://i.imgur.com/Hx75FNd.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/qSdf9oC.png)
Wave Kernel Signature
类似于HKS,我们可以利用波动方程来定义wave kernel signature(WKS)。
![](https://search.pstatic.net/common?src=https://i.imgur.com/Bh2TWqT.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/RsKGS3K.png)
一些文章指出WKS会比HKS更加稳定,但可能会过滤掉网格上一些全局的信息。
![](https://search.pstatic.net/common?src=https://i.imgur.com/38B8Fwn.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/0j3DkpZ.png)
当然除了上面介绍过的GPS、HKS以及WKS之外,利用Laplace算子的特征结构还可以构造出其它形式的shape descriptor。
![](https://search.pstatic.net/common?src=https://i.imgur.com/1WTynHz.png)
Combination with Machine Learning
把shape descriptor和机器学习结合起来可以实现各种网格之间的识别和匹配任务。
![](https://search.pstatic.net/common?src=https://i.imgur.com/9m5aqZk.png)
比如说我们可以把HKS在网格上的极大值作为特征点进行不同网格之间的特征对应和匹配。
![](https://search.pstatic.net/common?src=https://i.imgur.com/5eidfbY.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/7xi7kF6.png)
我们甚至可以不经过特征点提取的过程,直接对顶点上的HKS进行匹配。
![](https://search.pstatic.net/common?src=https://i.imgur.com/f6s0ceZ.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/omiWzrt.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/2A5Vrij.png)
使用这种方式我们可以处理一些原本无法区分的对称形状。
![](https://search.pstatic.net/common?src=https://i.imgur.com/ORcC8I5.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/EXPBzSv.png)
Other Applications
总结一下,Laplace算子在几何处理以及形状分析中有着大量的应用。
![](https://search.pstatic.net/common?src=https://i.imgur.com/EXPBzSv.png)
我们可以利用Laplace算子以及热传导方程来计算网格上的测地距离。
![](https://search.pstatic.net/common?src=https://i.imgur.com/1yKJ3R8.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/2DjIoxJ.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/FvF8h9S.png)
前面课程中介绍过的平均曲率流算法可以理解为通过Laplace算子来对网格进行平滑。
![](https://search.pstatic.net/common?src=https://i.imgur.com/EXPBzSv.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/Ppajh90.png)
对于曲面参数化问题,Laplace算子还可以作为Tutte’s embedding的权重。
![](https://search.pstatic.net/common?src=https://i.imgur.com/SIO0S0q.png)
关于Laplace算子在几何处理中的其它应用可以参考相关的文献。
![](https://search.pstatic.net/common?src=https://i.imgur.com/756YQFq.png)
Applications in Machine Learning
Semi-Supervised Learning
在半监督学习(semi-supervised learning)中数据集只有少量的一部分有标签,大部分数据都是无标签的。在这种情况下我们希望模型可以学习数据分布的结构来利用大量的无标签数据。
![](https://search.pstatic.net/common?src=https://i.imgur.com/NduKJEi.png)
很多时候机器学习的数据都分布在高维空间的流形上,此时可以通过最小化Dirichlet能量的方式来对数据进行划分。从形式上来看这种处理方式等价于求解Laplace方程。
![](https://search.pstatic.net/common?src=https://i.imgur.com/iai0BpP.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/R9Kw9o6.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/pxq6s8l.png)
Manifold Regularization
在很多机器学习任务中我们会在目标函数中添加正则项从而避免出现过拟合。把Dirichlet能量作为正则项的方式称为manifold regularization。
![](https://search.pstatic.net/common?src=https://i.imgur.com/4d3Nttw.png)
![](https://search.pstatic.net/common?src=https://i.imgur.com/aS6PR0P.png)
Diffusion Map
对于数据嵌入的任务,我们可以使用类似于GPS的技术将原始数据嵌入到低维空间中。
![](https://search.pstatic.net/common?src=https://i.imgur.com/MkYxODQ.png)
Graph Convolutional Networks
在图深度学习中Laplace算子也有着重要的应用。
![](https://search.pstatic.net/common?src=https://i.imgur.com/ba3QNkl.png)
Laplace算子在机器学习和深度学习的其它应用可以参考如下文献。
![](https://search.pstatic.net/common?src=https://i.imgur.com/q8XpFs8.png)