基于梯度场的高效几何优化算法

发布时间：2024-05-13 19:31

　　在计算机图形学所涉及的诸多问题中,求解线性系统一直扮演着重要的角色,是求解算法中必不可缺少的一部分。尽管大部分问题求解的都是稀疏方程,但是随着数据维度的不断增加,求解大型稀疏线性系统仍然是一个难题,尤其是在运行内存和运行时间方面。在求解关于梯度的优化问题时,其优化变量通常是函数值,而不是梯度值,这就使得在求解的过程中不具有可扩展性,因为在求解过程中要涉及到梯度变量到函数变量的转化。本文提出了一种新的基于梯度场求解方法,其在求解的过程中不需要求解线性方程而是直接得到对应函数的梯度值。最后根据求解出来的梯度值恢复出原来的函数值,可以达到与直接求解线性方程组同样的精度。因为不需要求大型稀疏线性方程,所以此算法具有高效性和可扩展性。本文从两个问题出发,应用此算法。一是二维或者三维区域内局部重心坐标的求解;局部重心坐标要求最小化重心坐标函数的全变差,同时要满足重心坐标的单位剖分性和线性插值性以及其他重心坐标函数的性质。二是二维或三维流形中测地距离的计算;测地线距离的计算即是求解相应的Eikonal Equation。这两个问题所涉及到的目标函数都是和梯度相关,因此这两个问题都可以转化为关于梯度变...

【文章页数】：63 页

【学位级别】：硕士

【部分图文】：

图2.4对于两个三维模型而言，使用我们算法得到的结果可视化展示

图２．Ｓ我ｔｆ】的新方法与传统方法的对比。随着迭代的进行，运行时问和结果精度的变化趋??势。我么将ＭＯＳＥＫ库计兑出来的结果作为真解ｔ??得到的。一个很自然的想法就是去拓展我们的算法到其他基于优化求解的重心??坐标问题上。这里主要的难点就是如何将约束转化为仅仅只有梯度变量表示的，....

图２．Ｓ我ｔｆ】的新方法与传统方法的对比

表２．２展示了两个求解方式下对于不同模型的计算时间和精度。在所有的??情况下，我们提出的方法都是使用更少的时间，但是却得到误差更小的结果。??图２．４展示了两个三维模型的最后计算结果。??图２．５展示了两个求解方式下对于两个模型时间和误差的变化关系，从图中??我们可以看出，我们的....

图11在不同尺度的模型上，使用我们的算法计算求得侧地线距离场的可视化表示

然后通过该向量场去恢复最后的测地线距离值。在计算热流方程的时候，我??们也提出了一个可并行的Ｇａｕｓｓ－Ｓｅｉｄｅｌ方法，该方法是更加高效和鲁邦的对于大??型网格来说。在计算梯度的过程中，我们把该问题可以转化为一个凸优化问题，??该优化问题可以通过ＡＤＭＭ１１８１快速高效的求解。....

图3J热流方程的计算示意图

集合：??：＝?｛＾５｝．??Ｚ）丨：＝＿Ｖ（Ｄ０）＼Ｄ０，??Ｄ２?＾＾（Ｄ＾ＸＣＤｏＵＤ，），／－Ｉ??ｄ，?＾＾（Ｄ＾ｘｘＩＪｄ，．??ｋ＝０??顶点的一邻域的点的并集，直观上来看，就的移动才能够到达源点ＩＶ所有的这样的集合先搜索的算法得到。于是在我们Ｇａｕｓｓ－Ｓｅｉｄｅ....

本文编号：3972605