用于曲线和曲面逼近的动量加速随机几何迭代方法
《Computer-Aided Design》:Momentum-accelerated randomized geometric iterative methods for curve and surface approximation
【字体:
大
中
小
】
时间:2026年01月30日
来源:Computer-Aided Design 3.2
编辑推荐:
吴念慈|曹红红|刘成志
中国武汉中南民族大学数学与统计学院,邮编430074
摘要
几何迭代方法是一类独特的数据拟合技术,其特点在于采用逐步迭代的方式,并具有清晰的几何意义。最小二乘逐步迭代逼近法作为这类方法中的重要成员,能够高效处理大规模点集数据。在本研究中,我们
吴念慈|曹红红|刘成志
中国武汉中南民族大学数学与统计学院,邮编430074
摘要
几何迭代方法是一类独特的数据拟合技术,其特点在于采用逐步迭代的方式,并具有清晰的几何意义。最小二乘逐步迭代逼近法作为这类方法中的重要成员,能够高效处理大规模点集数据。在本研究中,我们通过结合Polyak动量法和Nesterov动量法以及随机采样策略来加速LSPIA算法。所提出的算法通过随机选择索引来自适应更新控制点,同时利用控制点及其梯度的历史信息。我们证明了这些算法在期望意义上能够收敛到给定数据点的最小二乘拟合结果,并给出了动量参数的显式表达式。数值实验表明,与传统方法相比,所提方法在效率和精度上均有提升。
引言
随着数字硬件的快速发展,CAD和CAM工作流如今通常需要处理大量的3D点云和高分辨率三角形网格。这些数据集不仅体积庞大,还往往存在噪声,给后续的几何处理带来了巨大挑战。一种常用的解决方法就是曲线和表面拟合,即通过优化标准参数化表示形式(如B样条或细分曲面)的控制点,来近似或插值输入数据。这样得到的简洁平滑的曲线和表面有助于后续的任务,包括纹理映射、等几何分析以及几何微分算子的计算[1]、[2]。
几何迭代方法属于专门用于数据拟合的技术类别。这类方法的特点在于其逐步迭代的性质,同时具备清晰的几何解释。与传统方法依赖求解全局线性方程组不同[3],几何迭代方法允许在每次迭代中引入局部几何约束。在过去二十年里,这种灵活性使其应用范围不断扩大,涵盖了从几何设计[4]、逆向工程[5]到数据拟合[6],以及网格和NURBS实体生成[7]等相关领域[1]。然而,面对大规模数据集时,这些方法往往会出现过长的计算时间,甚至在极端情况下导致内存不足。在加速计算拉普拉斯-贝尔特拉米特征问题时,未优化的密集网格表面拟合就成为了严重的瓶颈[8]。因此,进一步改进几何迭代算法对于充分发挥其在大规模数据拟合中的潜力至关重要[9]。
几何迭代方法通常分为两类:插值型和近似型[1]。经典的逐步迭代逼近法就是插值型算法的典型代表[10]。它要求控制点的数量与数据点的数量相等。而在许多应用中,我们拥有的数据点数量超过了多项式曲线和表面所能处理的限度,这时就需要使用近似型曲线和表面。这样的曲线和表面不会恰好经过所有数据点,该方法也被称为最小二乘逼近法。
以曲线拟合为例,设{qj}j=1m为一组目标点。考虑在[0,1]上定义的基函数{μi(x)}i=1n,以及相应的递增参数序列{xj}j=1m。拟合曲线可以表示为C(x)=∑i=1nμi(x)pi,其中pi是对应于?i∈[n]?{1,2,…,n}的控制点。曲线拟合的目标是最小化平方距离之和,即min12∑j=1m‖qj?C(xj)‖2。传统处理该问题的方法是通过求解全局方程组来更新控制点,例如可参考[11]、[12]。
几何迭代方法则基于每个数据点对应的误差向量等几何信息来更新每个控制点,采用逐步迭代的方式。在[13]中,邓和林提出了结合最小二乘法的逐步迭代逼近法。初始曲线由C(0)(x)=∑i=1nμi(x)pi(0)生成,其中pi(0)=pi,i∈[n]。经过k次(k≥0)迭代后,新的LSPIA曲线定义为C(k+1)(x)=∑i=1nμi(x)pi(k+1),其中第i个控制点pi(k)通过pi(k+1)=pi(k)+δi(k)来更新,而δi(k)=α∑j=1mμi(xj)rj(k),δi(k)为调整向量,α为影响算法收敛速度的固定步长,rj(k)=qj?C(k)(xj)为对应于?j∈[m]?{1,2,…,m}的差分向量。该方法继承了传统逐步迭代逼近法的优点[10],在形状建模领域产生了深远影响。
在[14]中,Ebrahimi和Loghmani提出了基于Schulz方法的LSPIA算法,采用了复合迭代过程来计算控制点。Sajavic?ius在[15]中又提出了超幂LSPIA方法,该方法利用其他高阶迭代方法来近似矩阵逆。黄和王利用以往差分向量的信息,提出了带有记忆功能的逐步迭代逼近法,即MLSPIA[16]。在后续研究中,王简化了计算流程,提出了扩展的LSPIA算法,即ELSPIA[17]。该算法通过辅助向量r?j(k+1)来更新控制顶点,具体形式为pi(k+1)=pi(k)+α∑j=1mμi(xj)r?j(k+1),其中r?j(k+1)=(1?ω)r?j(k)+ωrj(k),ω为松弛参数。ELSPIA和MLSPIA框架也可以通过将预处理过的逐步迭代逼近技术应用于底层鞍点系统来得到,相关内容可见[18]、[19]。胡等人利用辅助迭代方案计算摩尔-彭若斯广义逆,构建了一系列用于曲线拟合的加速LSPIA方法[20]。在[21]中,控制点通过LSPIA方法进行调整,而权重和节点则通过基于目标函数解析梯度的LBFGS方法进行优化。
如[22]所示,方程(1)的解满足正交投影条件〈qj?C(xj),C′(xj)〉=0,j∈[m],这意味着第j个梯度分量为零。Rios和Jüttler指出,梯度下降法的经典收敛条件已经包含了LSPIA法允许的步长范围,他们还在[23]中提出了随机梯度下降变体。动量加速通过积累历史梯度来减少振荡和平坦区域,类似惯性下坡运动[24]、[25]、[26]。根据[27],控制点可通过Polyak动量法更新,即pi(k+1)=pi(k)+α∑j=1mμi(xj)rj(k)+β(pi(k)?pi(k?1)),其中标量β用于调节动量项的贡献程度。这种方法简称为PmLSPIA。定义中间变量si(k)=pi(k)+β(pi(k)?pi(k?1))。结合Nesterov动量的LSPIA方法,即NmLSPIA,会利用梯度历史信息,通过pi(k+1)=si(k)+α∑j=1mμi(xj)r?j(k)来更新控制点,其中r?j(k)=qj?∑i=1nμi(xj)si(k)。更多实现细节可见[27]。此外,还有其他基于参数的加速逐步迭代逼近方法,相关研究可见[28]、[29]、[30]。
传统的逐步迭代逼近法及其最小二乘变体将整个控制网络视为一个整体,同时更新所有顶点。后续的发展成果,如MLSPIA[16]、ELSPIA[17]、PmLSPIA[27]和NmLSPIA[27],都延续了这种全局策略。虽然这种策略在概念上较为简单,但随着控制点数量的增加,每次迭代的成本也会迅速上升。另一种极端方法是局部逐步迭代逼近法[31],它每一步只修改少量控制点,从而降低计算负荷;但由于其基于插值原理,因此不适用于当前应用中常见的过定或含噪声的数据集。
在处理一系列线性系统时,重新利用从一个线性系统解中获得的信息是非常有价值的。潜在的方法包括构建智能初始猜测值(有时称为温启动)、从上一次迭代中提取解空间(即循环利用与扩展方法),或在构建替代模型时采用随机化策略[32]、[33]。最近,吴和刘[34]提出了一种随机逐步迭代逼近法,它融合了这两种思路。该方法在每次迭代中随机选择一部分索引,更新对应的控制点,而其余控制点保持不变。这样一来,RPIA既保留了LSPIA的最小二乘形式,又具备了细分方案所具有的局部性。这种随机性与简约更新的结合不仅降低了每次迭代的复杂度,还使得其收敛理论具有类似随机逼近的特征。
设ei为n阶单位矩阵In的第i列。将配置矩阵A=μi(xj)j=1,i=1m,n按列分割为A=[A:,1A:,2?A:,n],则PmLSPIA算法中的迭代步骤可以改写为p(k+1)=p(k)+αA?(q?Ap(k))+β(p(k)?p(k?1))=p(k)+α∑i=1neiA:,i?(q?Ap(k))+β(p(k)?p(k?1)),其中q和p(k)分别是由数据点和控制点按自然顺序排列而成的序列。在NmLSPIA方法中,有p(k+1)=s(k)+αA?(q?As(k))=s(k)+α∑i=1neiA:,i?(q?As(k)),其中s(k)=p(k)+β(p(k)?p(k?1)),s(k)由si(k)组成,i∈[n]。为了降低每次迭代的计算量,我们可以考虑从集合[n]中随机选取一个元素来进行迭代。将这种随机化策略应用于PmLSPIA和NmLSPIA的迭代过程中,就可以得到用于解决大规模数据拟合问题的动量加速随机逐步迭代逼近法,我们将其分别命名为PmRPIA和NmRPIA。
本研究的主要贡献如下:
•加速框架:我们提出了两种改进版的LSPIA算法[13],它们将Polyak动量法和Nesterov动量法与随机采样策略有机结合。这些算法能够利用控制点及其梯度的历史信息,在每次迭代中生成新的控制点。严格的收敛性分析证明了这些算法具有更快的收敛速度,同时我们也给出了最优参数选择的明确规则。
•通用统一框架:所提出的算法属于近似逐步迭代逼近法,允许数据点数量超过控制点数量,最终可在极限情况下得到最小二乘解。它们遵循一种通用的迭代框架,通过合理选择步长、动量参数和索引集合,可以转化为传统的LSPIA[13]、RPIA[29]、PmLSPIA[27]和NmLSPIA[27]算法。
本文的其余结构如下:第一节1.4部分将介绍文中会用到的各种符号。第二节介绍用于曲线拟合的PmRPIA和NmRPIA算法。第三节分析这两种算法的收敛性,并讨论相应的参数选择问题。第四节将这些方法扩展到表面拟合领域。第五节通过数值实验验证理论结果。第六节为结论性论述。
表1.1中列出了部分常用符号。
**曲线拟合部分**
首先将基函数索引划分为∪i=1tUi=[n],且当i≠j时,Ui∩Uj=?,同时令pi(1)=pi(0)=pi,i∈[n]。曲线拟合用的PmRPIA算法详见算法1。
**备注2.1**
PmRPIA算法中包含动量项γ(k),用以加速收敛。该方法仍采用随机选择策略来更新向量,并利用先前的方向信息。其中αk控制步长大小,β则决定动量权重。该算法的第k次迭代在矩阵形式下可表示为p(k+1)=p(k)+αkδ(k)+βγ(k),其中δ(k)=[δ1(k)δ…δk]。
**收敛性分析**
在本节中,我们将为PmRPIA和NmRPIA算法建立收敛性保证,并确定其最优参数。设p?=A?q表示方程(1)的最小范数最小二乘解,?表示摩尔-彭若斯伪逆。无论矩阵A是否欠秩,或者系统是过定还是欠定,这种广义逆都非常适合用于最小二乘问题,而且最便捷的计算方式是通过奇异值分解来实现。当A为满秩矩阵时……
**表面拟合部分**
设{qh,l}h=1,l=1m1,m2为一组目标点,{μi(x)}i=1n1和{νj(y)}j=1n1为在[0,1]×[0,1]上定义的两组基函数,它们分别对应递增的参数序列{xh}h=1m1和{yl}l=1m2。拟合表面可以表示为S(x,y)=∑i=1n1∑j=1n2μi(x)νj(y)pi,j,其中pi,j是待确定的第(i,j)个控制点,i∈[n1],j∈[n2]。在初始化pi,j(1)=pi,j(0)=pi,j,i∈[n1],j∈[n2]之后,还对[n1]进行划分,得到Uii=1t和Vjj=1s……
**数值实验部分**
我们介绍了这些算法的实现细节及性能评估情况,所有实验均在MATLAB R2022a环境下,使用Intel(R) Core(TM) i7处理器完成。共分析了六个数据集:四个来自曲线数据,两个来自表面数据。图5.1展示了四个具有代表性的曲线数据集,其中m=400。
**示例5.1**:极坐标形式为r(t)=sin(θ/4),0≤θ≤8π的玫瑰形曲线。
**示例5.2**:极坐标形式为r(t)=1+2cos(2θ+1/2)+2cos(3θ+1/2),0≤θ≤2π的团状曲线。
**示例5.3**:坐标形式为x(t)=……的螺旋曲线。
**结论与未来工作**
几何迭代方法为大规模数据拟合提供了高效且具有清晰几何解释性的解决方案。在本研究中,通过结合Polyak动量法、Nesterov动量法以及随机采样策略,显著提升了LSPIA[13]、RPIA[29]、PmLSPIA和NmLSPIA[27]算法的运行效率。所提出的方法能够通过自适应更新动态优化控制点,同时充分利用控制点及其梯度的历史信息,从而确保……
**CRediT作者贡献说明**
吴念慈:撰写原文初稿、提供资源、确定研究方法、负责资金申请。曹红红:提供资源、协助研究方法设计。刘成志:参与文章审阅与编辑、负责研究指导、提供资源支持。
**资金支持**
作者感谢国家自然科学基金会的支持,相关项目编号为12201651,对此我们深表感激。
**利益冲突声明**
作者声明存在以下可能构成利益冲突的财务利益/个人关系:吴念慈表示获得了国家自然科学基金会的财政资助。如果有其他作者,他们声明自己不存在任何可能影响本文所述研究的已知利益冲突或个人关系。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号