Convergent Authalic Energy Minimization for Disk Area-Preserving Parameterizations

An area-preserving parameterization of a surface is a bijective mapping that maps the surface onto a specified domain and preserves the local area. This paper formulates the computation of disk area-preserving parameterization as an improved optimization problem and develops a preconditioned nonlinear conjugate gradient method with guaranteed theoretical convergence for solving the problem. Numerical experiments indicate that our new approach has significantly improved area-preserving accuracy and computational efficiency compared to other state-of-the-art algorithms. Furthermore, we present an application of surface registration to illustrate the practical utility of area-preserving mappings as parameterizations of surfaces.

The MATLAB executable with a user-friendly interface for the preconditioned nonlinear CG method of the AEM (Algorithm 1) can be found at http://tiny.cc/DiskAEM. Other data are available from the corresponding author on request.

1. https://www.math.cuhk.edu.hk/~ptchoi/files/densityequalizingmap.zip.

2. https://www.cs.stonybrook.edu/~gu/software/omt/omt-binary.rar.

This work was supported by the National Science and Technology Council grant 112-2115-M-003-015 and the National Center for Theoretical Sciences in Taiwan.

Authors and Affiliations

1. Department of Mathematics, National Taiwan Normal University, Taipei, Taiwan

   Shu-Yung Liu & Mei-Heng Yueh

Corresponding author

Correspondence to Mei-Heng Yueh.

Conflict of interest

The authors declare that they have no Conflict of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Proof for Convergence

In this section, we establish the global convergence of Algorithm 1. The proofs are inspired by the convergence of the nonlinear CG method presented in [15, Chapter 5]. Our proofs extend this framework to the nonlinear CG method with preconditioners.

The proof is under the assumption that each step length \(\alpha _k\) in the algorithm is appropriately chosen to satisfy the strong Wolfe conditions (22). The existence of such step length \(\alpha _k\) is guaranteed by the following lemma based on the fact that \({E}_A(f)\ge 0\) is bounded below.

Lemma 1

([15, Lemma 3.1]) Let \(\textbf{p}^{(k)}\) be a descent direction at \(\widehat{\textbf{f}}^{(k)}\). Intervals of step lengths satisfying the strong Wolfe conditions (22) always exist.

In practice, to guarantee that the preconditioner-dependent vector \(\textbf{p}^{(k)}\) in (19) is always a descent direction at \(\widehat{\textbf{f}}^{(k)}\), we require a vital inequality stated in the following lemma, a variant of [15, Lemma 5.6].

Lemma 2

Given a preconditioner M with a symmetric positive definite inverse. Suppose the step size \(\alpha _k\) satisfies the strong Wolfe conditions (22). Then, the vector \(\textbf{p}^{(k)}\) satisfies

for all \(k \ge 0\), where \(\Vert \cdot \Vert _{M^{-1}}\) denotes the \(M^{-1}\)-norm defined as \( \Vert \textbf{v}\Vert _{M^{-1}} = \sqrt{\textbf{v}^\top M^{-1}\textbf{v}}. \)

Proof

We prove (32) by induction on k. For \(k = 0\), from (19a), we have

Next, we assume (32) holds for some \(k=n\). Then, from (19b), we have

By (22b), we have \( |\nabla {E}_A(\widehat{\textbf{f}}^{(n+1)})^{\top } \textbf{p}^{(n)}| \le -c_2 \nabla {E}_A(\widehat{\textbf{f}}^{(n)})^{\top } \textbf{p}^{(n)}, \) i.e.,

As a result, from (33) and (34), we have

Then, from the induction hypothesis, we have

which shows that (32) holds for \(k=n+1\). \(\square \)

The second inequality of (32) in Lemma 2 guarantees the vector \(\textbf{p}^{(k)}\) being a descent direction at \(\textbf{f}^{(k)}\). When \(c_2\) in (22b) satisfies \(0<c_2<\frac{1}{2}\), we obtain the following corollary.

Corollary 2

Suppose the step size \(\alpha _k\) satisfies the strong Wolfe conditions (22) with \(0<c_2<\frac{1}{2}\). Then, \(\textbf{p}^{(k)}\) is a descent direction at \(\widehat{\textbf{f}}^{(k)}\).

Proof

Note that the function \(\varphi (x) = \frac{2x-1}{1-x}\) is monotonically increasing on \([0, \frac{1}{2}]\) with \(\varphi (0) = -1\) and \(\varphi (\frac{1}{2}) = 0\). From the assumption \(0<c_2<\frac{1}{2}\) and Lemma 2, we have

Hence \(\nabla {E}_A(\widehat{\textbf{f}}^{(k)})^{\top } \textbf{p}^{(k)}<0\), and therefore, \(\textbf{p}^{(k)}\) is a descent direction at \(\widehat{\textbf{f}}^{(k)}\). \(\square \)

The authalic energy for simplicial mapping can be regarded as a function of 2n variables as

provided that n is the number of vertices of the triangular mesh model. To prove the global convergence theorem, \(E_A\) and its gradient are essential to be Lipschitz continuous. Here, we prove the Lipschitz continuities in the following lemma.

Lemma 3

Let \(E_A:[-1,1]^{2n}\rightarrow \mathbb {R}\) be the authalic energy (2) represented in the form (35). Then, \(E_A\) and its gradient \(\nabla E_A\) are Lipschitz continuous.

Proof

For every pair of disk-shaped simplicial mappings \(\textbf{x}\) and \(\textbf{y}\in [-1,1]^{2n}\), we define \(g(t) = E_A((1-t)\textbf{x}+ t\textbf{y})\). Since \(E_A\) is smooth, by the mean value theorem, there is a value \(\xi \in (0,1)\) such that \(\textbf{z}= (1-\xi ) \textbf{x}+ \xi \textbf{y}\) and

Since the domain of \(E_A\) is compact, we obtain

where the Lipschitz constant \(C_1 = \max _{\textbf{f}\in [-1,1]^{2n}} \Vert \nabla E(\textbf{f})\Vert \).

Similarly, to prove the Lipschitz continuity of the gradient of \(E_A\), we define \(\phi (t) = (\nabla E_A(\textbf{y}) - \nabla E_A(\textbf{x}))^\top \nabla E_A((1-t)\textbf{x}+ t\textbf{y})\). Since \(\nabla E_A\) is smooth, by the mean value theorem, there is a value \(\eta \in (0,1)\) such that \(\textbf{w}= (1-\eta ) \textbf{x}+ \eta \textbf{y}\) and

Since the domain of \(E_A\) is compact, we obtain

where the Lipschitz constant \(C_2 = \max _{\textbf{f}\in [-1,1]^{2n}} \Vert \nabla ^2 E(\textbf{f})\Vert \). \(\square \)

To extend the Lipschitz continuity in M-norm, we provide the following lemma.

Lemma 4

Let M be a symmetric positive definite matrix and \(f: \mathbb {R}^n \rightarrow \mathbb {R}^n\) be Lipschitz continuous with respect to the Euclidean norm, i.e.,

for some constant \(c_f \ge 0\). Then it also satisfies Lipschitz continuity in the M-norm, i.e.,

for some constant \(m_f\ge 0\).

Proof

Since M is symmetric positive definite, M is invertible and there exist symmetric positive definite matrices \(M^{1/2}\) and \(M^{-1/2}\) that satisfies \(M = M^{1/2} M^{1/2}\) and \(M^{-1} = M^{-1/2} M^{-1/2}\). It follows that

and

Therefore,

The constant \(m_f = c_f \,\Vert M^{1/2} \Vert \, \Vert M^{-1/2}\Vert _M \ge 0\). \(\square \)

Under the assumptions that step length \(\alpha _k\) satisfies the Wolfe conditions (22) with \(0<c_2<\frac{1}{2}\), and that \(\nabla E_A\) is Lipschitz continuous, the \(M^{-1}\)-norm of the gradient vector is constrained by the modified Zoutendijk’s condition stated in the following lemma.

Lemma 5

(modified Zoutendijk’s condition) Suppose the step size \(\alpha _k\) satisfies the strong Wolfe conditions (22) with \(0<c_2<\frac{1}{2}\). Given a matrix M with \(M^{-1}\) being symmetric positive definite. Then, the vector \(\textbf{p}^{(k)}\) in (19) satisfies

where \(\cos \theta ^{(k)}_M\) is defined as

Proof

Since the step size \(\alpha _k\) satisfies (22), by Corollary 2, \(\textbf{p}^{(k)}\) is a descent direction at \(\widehat{\textbf{f}}^{(k)}\) so that (22b) can be written as

By subtracting \(\nabla {E}_A(\widehat{\textbf{f}}^{(k)})^{\top } \textbf{p}^{(k)}\) in both sides of (38), we obtain

Since \(\nabla E_A\) is Lipschitz continuous, by applying Lemma 4 and (36), we have

As a result,

By substituting \(\alpha _k\) into (22a), we obtain

where \(c=\frac{c_1(1-c_2)}{c_E \, \Vert M^{1/2}\Vert _{M^{-1}}^2}\) and \(\cos \theta _M^{(k)}\) is defined as (37b). The recursive inequality (40) implies

In other words,

Noting that \({E}_A(\widehat{\textbf{f}})\) is bounded below, which implies \({E}_A(\widehat{\textbf{f}}^{(0)}) - {E}_A(\widehat{\textbf{f}}^{(k+1)})\) is bounded above. Therefore, by taking the limit of (41), we obtain (37) as desired. \(\square \)

Lemma 5 implies that \(\cos ^2 \theta _M^{(k)} \Vert \nabla {E}_A(\widehat{\textbf{f}}^{(k)}) \Vert _{M^{-1}}^2\) tends to zero as k tends to infinity. Then, \(\nabla E_A(\widehat{\textbf{f}}^{(k)})\) would tend to \(\textbf{0}\), provided that \(\cos \theta _M^{(k)} = 1\). In the case of the nonlinear preconditioned CG method, \(\textbf{p}^{(k)}\) being a descent direction implies \(\theta _M^{(k)} < \frac{\pi }{2}\) and hence \(\cos \theta _M^{(k)} > 0\). However, it is still possible that \(\cos \theta _M^{(k)}\) approaches zero, and thus that \(\Vert \nabla {E}_A(\widehat{\textbf{f}}^{(k)}) \Vert _{M^{-1}}\) may not converge to zero. Fortunately, we can apply the left inequality of (32) in Lemma 2 to further extend the result of Lemma 5 and thus establish a global convergence theorem for the nonlinear preconditioned CG method as follows.

Theorem 2

Suppose the step size \(\alpha _k\) satisfies the strong Wolfe conditions (22) with \(0<c_1<c_2<\frac{1}{2}\). Then,

provided that \(M^{-1}\) is a symmetric positive definite matrix.

Proof

We prove (42) by contradiction. Assume on the contrary that

i.e., there exist \(N\in \mathbb {N}\) and \(\gamma > 0\) such that

for every \(k>N\). Let \(\theta _M^{(k)}\) be defined as (37b). Then, by Lemma 2 together with (37b), we have

Equivalently,

By Lemma 5, we have

Hence, with (44) and (45), we obtain

By Lemma 2, we have

Then, by (22b) and (47), we obtain

Hence, by (48), we have

Let \(c_3 = (1+c_2) / (1-c_2)\). The recursive inequality (49) with \(\textbf{p}^{(0)} = M^{-1} \nabla {E}_A(\widehat{\textbf{f}}^{(0)})\) implies

Recall that \(\beta _k = \Vert \nabla {E}_A(\widehat{\textbf{f}}^{(k)}) \Vert ^2_{M^{-1}} / \Vert \nabla {E}_A(\widehat{\textbf{f}}^{(k-1)}) \Vert ^2_{M^{-1}}\), the product

By substituting (51) into (50), we obtain

In addition, by (43) and the inequality \(\Vert \nabla {E}_A(\widehat{\textbf{f}}^{(k)}) \Vert ^2_{M^{-1}} \le \Vert \nabla {E}_A(\widehat{\textbf{f}}^{(j)}) \Vert ^2_{M^{-1}}\) for \(j \le k\), we have, for \(k>N\),

From Lemma 3, we know that \(\nabla {E}_A\) is Lipschitz continuous, so there exists \(\overline{\gamma }\) such that \(\Vert \nabla {E}_A(\widehat{\textbf{f}}^{(k)}) \Vert _{M^{-1}} \le \overline{\gamma }\) for all k. As a result, from (52) and (53), for \(k>N\),

This implies that

for some \(\omega >0\). On the other hand, from (43) and (46), we have

which contradicts to (54). \(\square \)

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions