Conference

A Convex Optimization Framework for Regularized Geodesic Distances

Michal Edelstein, Nestor Guillen, Justin Solomon, Mirela Ben-Chen

Technion; Texas State University; MIT

SIGGRAPH 2023Geometry & ModelingGeodesic DistanceConvex OptimizationTriangle MeshShape AnalysisADMM
Paper

一句话总结

本文提出一个统一的凸优化框架，在计算三角网格上”类测地距离”的同时加入可控的正则项（平滑、向量场对齐、边界不变性等），并给出理论保证与高效的 ADMM 求解算法。

研究背景

  • 领域现状：测地距离是形状分析的核心工具，社区已有大量算法——从精确多面体距离（MMP、VTP）到近似方法（Fast Marching、热方法、EMD），近年还出现了把距离计算写成凸优化问题的思路。
  • 核心痛点：很多下游应用（形状对应、描述子、重网格化、编织）并不需要精确测地距离，反而需要一个带有额外性质的”距离样”函数——比如在割迹（cut locus）附近本应不光滑的测地距离需要被平滑。但现有正则化方法（热方法用时间参数、EMD 用谱基投影、图上 Dirichlet/Hessian 正则）各自为政，缺少统一、可控、易标定的框架，也缺少理论支撑。
  • 本文 idea：把”尽可能测地 + 附加正则性质”统一写成一个凸优化问题——最大化函数积分（逼出单位梯度、即测地性），同时加一个关于梯度的凸正则泛函，用权重 \(\alpha\) 直接、直观地控制正则强度。

方法

整体框架：在紧曲面 \(M\) 上，给定源集合 \(E\)（通常是单点 \(x_0\)），求解带梯度约束的凸优化问题：目标是正则项与负积分之和，约束是非源点处梯度范数不超过 1、源点处取值不超过 0。

\[\text{Minimize}_u \quad \alpha E(u) - \int_M u(x)\, dVol(x)\]

\[\text{s.t.} \quad \lvert \nabla u(x) \rvert \le 1 \ \ (x \in M \setminus E), \qquad u(x) \le 0 \ \ (x \in E)\]

其中正则泛函 \(E(u) = \int_M F(\nabla u(x), x)\, dVol(x)\)，且 \(F\) 对第一个参数是凸的。因为最大化积分会把梯度”顶”到约束上限，未被正则项影响的区域自然满足 \(\lvert \nabla u \rvert = 1\)（即精确测地），只有在割迹附近梯度约束不激活的区域才被正则项接管。

flowchart LR
  A["输入：网格 M + 源集合 E"] --> B["选择正则项 F<br/>Dirichlet / 向量场对齐 / Hessian"]
  B --> C["凸优化问题 (带梯度锥约束)"]
  C --> D["ADMM 求解<br/>引入辅助变量 z = 梯度"]
  D --> E["正则化距离 u"]

关键设计：

  1. 理论良定性。在温和条件下证明了：问题对任意 \(\alpha > 0\) 存在唯一极小元，且当 \(\alpha \to 0\) 时极小元在 \(L^\infty\) 意义下一致收敛到精确测地距离 \(d(x, E)\)。解天然是 Lipschitz 连续的，并呈现两个区域：\(\lvert \nabla u \rvert = 1\) 处求解 Eikonal 方程（精确测地），\(\lvert \nabla u \rvert < 1\) 处求解泊松方程（被平滑）。这一结构与经典的”弹塑性扭转问题”/障碍问题同源，作者在圆 \(S^1\) 上给出了闭式解并证明它构成一个度量。

  2. 三种正则项。Dirichlet 能量 \(\tfrac{1}{2}\int_M \lvert \nabla u \rvert^2\) 给出基本平滑，平滑范围由 \(\alpha\) 控制；向量场对齐项 \(\tfrac{1}{2}\int_M \lvert \nabla u \rvert^2 + \beta \langle V, \nabla u \rangle^2\) 让等值线与给定线场对齐（等价于各向异性平滑，度量矩阵 \(A = I + \beta \hat V\)）；曲面 Hessian 能量 \(\tfrac{1}{2}\int_M \lvert \nabla^2 u \rvert^2\) 带来自然（零 Neumann）边界条件，使结果对孔洞与网格边界更鲁棒。

  3. ADMM 高效求解。离散化后（余切 Laplacian \(W_D\)、梯度 \(G\)、散度 \(D\)）问题变成二次目标 + 二阶锥约束。引入辅助变量 \(z = Gu\) 表示梯度，交替执行 \(u\)-最小化（解一个可预分解、复用的固定线性系统）、\(z\)-最小化（把梯度投影到单位球）、对偶变量更新。相比商业求解器 CVX+MOSEK 有至少一个数量级的加速。

  4. 对称全对形式。固定源的公式对 \(x\) 和源 \(y\) 处理不对称。作者把问题搬到乘积流形 \(M \times M\) 上，一次性求解所有点对 \(U(x,y)\)，证明其唯一、对称、且 \(\alpha \to 0\) 时收敛到全测地距离。并设计了第二个可扩展 ADMM（把 \(n^2 \times n^2\) 的巨型线性解降为 \(n\) 次 \(n \times n\) 求解）。

实验结果

在 Figure 8 的一组模型上，对比本文 Dirichlet 正则距离、热方法、EMD 与精确 MMP 距离，报告运行时间 T 与相对 MMP 的最大误差 \(\epsilon\)（占最大距离的百分比）：

模型 ( F ) 热方法 \(t=\hat e^2\) \(\epsilon\) 热方法 \(t=20\hat e^2\) \(\epsilon\) 本文 \(\hat\alpha=0.02\) \(\epsilon\) 本文 \(\hat\alpha=0.1\) \(\epsilon\)
Homer (23K) 2.47% 7.76% 3.40% 11.90%    
Elephant (10K) 4.84% 11.36% 2.00% 5.72%    
Armadillo (29K) 2.83% 9.33% 2.35% 6.78%    
Koala (9K) 2.30% 7.17% 2.35% 8.64%    

本文方法与热方法误差量级相当（都是越平滑误差越大），但关键优势在于稳定性：跨不同网格、不同分辨率、不同重网格与噪声，用同一套参数得到的平滑尺度基本一致，因此正则参数更易标定。此外还验证了：对网格无关性（热方法在 half-half 网格上失效而本文稳定）、对噪声鲁棒、对称性误差低于热方法，以及在较大 \(\hat\alpha\) 下三角不等式违反率显著下降（全对形式违反最少）。求解速度上，本文 ADMM 相比 CVX+MOSEK 快约一个数量级。

亮点与局限

  • 亮点：
    • 用一个凸优化框架统一了正则化测地距离，正则强度由单一权重 \(\alpha\) 直接、直观地控制，且有存在唯一性与收敛性的理论保证。
    • 正则项可插拔（Dirichlet / 向量场对齐 / Hessian / 甚至非二次项），扩展性强；ADMM 系统矩阵固定可预分解，比商业求解器快一个数量级。
    • 对网格质量、分辨率、噪声鲁棒；乘积流形上的全对形式给出对称距离；在编织行生成等实际应用中展示了向量场对齐的价值。
  • 局限：
    • 一般曲面上不保证结果满足三角不等式（构成真正度量），只在较大 \(\hat\alpha\) 下经验成立；乘积流形形式的三角不等式仅有实验鼓励、无证明。
    • Hessian 正则超出了本文理论覆盖范围，其极小元收敛性尚是开放问题。
    • 全对形式复杂度显著更高，即便优化后仍需 \(n\) 次 \(n \times n\) 求解，对超大网格仍有压力。

延伸思考

  • 框架把测地距离计算与障碍问题/自由边界 PDE 联系起来，为后续设计新正则项（如 \(L_1\) 范数、非凸正则）提供了数学基础；作者也指出非凸 ADMM 理论可能让 Algorithm 1 适配非凸正则。
  • “用凸优化 + 可控正则得到光滑距离样函数”的思路，对形状对应、描述子、重网格化等下游任务都可能直接受益——尤其是那些对割迹附近不光滑性敏感的应用。
  • 全对形式能否在一般流形上给出真正的光滑度量（满足三角不等式），是一个有意思且尚未解决的理论问题，也关系到能否用它构造流形上的可微度量。