📐Registration

A reappear of the article :Surface Registration with Eigenvalues and Eigenvectors

frame

项目简介

复现基于特征值和特征向量的曲面配准方法，运用基于能量方程的优化计算方法使计算效果达到论文实现的效果。

本项目仍在测试二次线性规划步骤，该步骤设计编码完成后将会开源分享。

usage

Visualization over the first non-zero eigen vector

关键部分代码框架

目前程序大部分编码工作已经完成，仅差二次线性规划问题还未复现。最终代码会包装成一个Surface类。对当前编码结果进行黑盒分析，使用方法仅需构造该Surface类，输入两个Mesh格式变量，系统会自动判断两流形采样点数，边界条件等是否满足配准条件，因此目前的程序已经具有较为优秀的可靠性。调用其中的Registration()方法即可实现流形配准，通过模拟计算可知，对eight.m这一相对简单的流形进行配准，在本报告所给出的实验环境下，耗时可以控制在20分钟以内，基本达到论文所要求的运行效果。

但通过白盒分析发现，当前代码模块内部耦合性相当糟糕，各个组件之间共用一个数据存储空间，且并非通过参数形式进入模块，达到了内容耦合的程度。这是为了实现大数据传输下保证空间资源和时间资源重复占用而作出的妥协，如果其他功能对Surface类内部模块有调用需求的话，可复用程度很低。

Surface类重要方法及变量功能说明：

  • Surface(M* pMesh_N,M* pMesh_M,int k):构造函数，输入三个变量，前两个代表需要被配准的两个流形，最后一个代表配准中利用前k个特征值进行配准。

  • void buildLBM_N():对第一个流形构造 Laplace-Beltrami 矩阵，该方法中L_N,S_N,W_N会根据论文中的定义赋值。

  • void buildLBM_M():对第二个流形构造 Laplace-Beltrami 矩阵，该方法中L_M,S_M,W_M会根据论文中的定义赋值。

  • void EmBedding_N()：根据k计算前k个特征向量，根据论文中的定义，将利用特征向量和特征值计算出I_N;

  • void EmBedding_M():根据k计算前k个特征向量，根据论文中的定义，将利用特征向量和特征值计算出I_M;

  • void Registeration(int K);执行配准操作，进行K次迭代，每次迭代开始时会调用EmBedding_N()，根据compute所得结果迭代N的Laplace-Beltrami 矩阵特征值特征向量，随后将对compute进行下一步调用，每次迭代实现一次二次规划问题。

  • void updateOMEGA(): 该步骤会通过Registeration被调用，将一个对角矩阵更新为具有位置对应信息的矩阵以实现配准效果。

  • void compute()：实现二次规划，目前还在开发设计，难点在于处理大型稀疏矩阵，广泛使用的二次规划问题解决方法都涉及到参数矩阵求逆，而在此处稀疏大矩阵所求逆矩阵往往不可逆，因此需要重新查找可复用的计算方法并复现。

以下为毕设相关内容：

研究内容与目标

  1. 复现基于特征值和特征向量的曲面配准方法，运用基于能量方程的优化计算方法使计算效果达到论文实现的效果。

  2. 探索曲面配准在四面体网格生成领域的应用，尝试利用曲面配准技术优化Morse-sample function，通过映射配准找到更高质量的critical point。

  3. 与其他研究方向的成员合作，降低代码耦合性，将功能复现嵌入现有的CAE系统。

采取的研究方案

需求调研

分析现有的曲面配准应用场景，针对该场景对原算法优化。建立简易的应用规格说明书并迅速构建软件原型，随着文献所提及方法的进一步理解逐步完善代码框架并实现软件功能需求

平台条件

开发硬件条件：

  • CPU：Apple M1 Pro (cores: 2E+8P+16GPU)
  • 内存：16GB(Samsung LPDDR5)
  • 硬盘：994.66 GB（994,662,584,320字节）

开发软件条件：Visual Studio code, cmake

二次线性规划的实现

这一部分在原论文中没有详细阐明，甚至在参考文献里都鲜有记载，这对代码复现的最后一步提供了偌大的阻碍，现在的思路是使用牛顿迭代法，首先是能量函数的最小值，通过矩阵求导的方式即可将原本的二次规划问题转化为一次函数求根的问题。但这一步里有很多想当然的情节，首先是xWxTxWx^T的处理，目前的矩阵方程教材只提供了两个列向量点乘的求导法则，这里使用原文提过的一个“圈乘”的方法逆运算来实现，没有严格的证明，估计复现完效果也不会很好，此外是等式约束问题，这其实很难处理因为要解决k个等式对结果的限制条件，而由于点数庞大而稀疏，这个方程在机器上几乎是不可解的，就算解出来，点数-k个基底也是完全没法储存的。幸运的是这几个等式约束都是由对称矩阵的特征向量运算而来，两两正交，因此分别使用牛顿迭代法得出来的根是可以作为共同根的。结合以上这些思路，即可开始尝试二次线性规划的复现。

思路再转化一下，根据矩阵方程求导法则，原来的最小值同样可以化成ax+bax+b的形式，综上考虑，原本的方程就变成了一个N个未知量加上N+k个方程的情况，若有解则是可作为非条件极值，无解则需要作为条件极值处理，确保等式约束的情况下使原方程最小。经过多次实验发现单纯的使用牛顿迭代法很难收敛，因此需要在判断0点和学习率方面设置阈值和经验值，目前依然在探索中。

目前已实现等式约束，同时等式约束应用到能量方程导数上依然可以用，也实现了迭代的收敛，不会出现inf，但是特征值在迭代中没有趋近。可能处理能量方程的过程没有处理好（2023.9.11）

🤡,刚发现牛津的一个二次求解库，叫做Osqp，不仅支持二次线性规划还完美兼容稀疏矩阵，可能卡了快快两个月的东西是因为调研没做好，纯纯🤡了。

配准技术的应用

网格划分步骤

在四边形网格生成的过程中,奇异点是需要被克服的一大难点，因此需要对原有网格进行划分。涉及到Morse函数以及拉普拉斯算子的处理。配准技术的一个应用思路就是将简单流形与复杂流形配准之后，将简单流形的鞍点和极值点映射到复杂流形里。只需要保证同亏格且无边界，理论上可以保证映射过去的点具有和critical point一样的拓扑性质，但由于目前已有一套相对成熟的critical point查找方法，配准技术在这方面能否带来速度上的优势将会是一个唯一课题。

工业应用

本人认为可能的一大工业应用就是对三维运动模型的插值补帧。首先最为基础的在工业软件领域,物体碰撞形变后将各点配准并且映射回去以追踪物体的形变状态。而在游戏引擎领域可以用于游戏动作的捕捉并补全动作内容。

本博客将持续更新，敬请期待……