Page 296 - 《软件学报》2020年第10期

3272 Journal of Software 软件学报 Vol.31, No.10, October 2020

4: repeat
5: 整体:计算公式(7)的梯度 g 与 Hessian 矩阵 H;
−1
6: 计算迭代方向 s=−H g;
7: 运用线性回溯法计算迭代步长α;
8: 更新点集,q=q+ωs;
9: 局部:将新点集{q j }投影到曲面并得到 {}.q ′ j
10: n=n+1.
2
11: until ||g|| <ε或 max{| q n − q n− 1 |} ε< 或 n≥N.
j j
′ ′
12: 将所有未处于曲面上的折线段{ } 投影到曲面.
qq
j j+ 1
3 实验结果与讨论
本文用 C++语言实现了上述算法,并在 8 核 Intel i7-7700U 处理器、8G 内存的 Linux 虚拟机环境下运行.其中,
算法所涉及的线性方程组的求解采用 Eigen 库 [39] 提供的稀疏 Cholesky 分解法——LLT 算法.下面,本文通过一系列
实验展示该算法的特点.
3.1 算法的收敛性实验
本文在人脸模型上设计了一条经过 3 个插值点的开曲线.该曲线在迭代 20 次后收敛,图 3 给出了迭代的中间结
果.由图可见:随着迭代次数的增加,曲线在曲面上滑动而趋于光滑,最终收敛并达到稳定状态.大量实验结果表明:本
算法在步长控制策略的作用下均能稳定地收敛,且在绝大多数情况下均在梯度条件下收敛.

(a) 初始曲线 (b) 2 次迭代 (c) 4 次迭代 (d) 6 次迭代 (e) 8 次迭代

(f) 10 次迭代 (g) 12 次迭代 (h) 14 次迭代 (i) 16 次迭代 (j) 20 次迭代
Fig.3 Sampled curves on the face model generated during the iterations (λ=0.1)
图 3 人脸模型上插值曲线的迭代序列(λ=0.1)

图 4 所示为 3 个迭代曲线图,分别为能量函数值(公式(10))、对应的梯度模长的平方(施加了 log 函数)以及平
均距离的变化.随着迭代的进行,能量函数值逐步下降;其梯度值尽管在局部跳动,但总体亦呈现下降趋势;曲线到网
格的平均距离值也较为稳定地下降,且当算法收敛时,其平均距离也达到较小值.此时利用投影法将其映射到曲面
上,对曲线光滑度的影响较小.
本文算法较为耗时部分为迭代中局部阶段的投影点计算.该算法在前次迭代的投影点所在面片的 r-环拓扑邻
域搜索投影点.为加速起见,本文采用法向与邻域的交点替代最近点以过滤部分面片方式,并比较了两种策略(r=2),
实验结果如图 5(a)所示.由图可见:两者所设计的曲线形状较为相似,几乎重合,但法向交点策略迭代 88 次,耗时