Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation

Highlights

• Area-preserving parameterization handles genus 0 surfaces with multiple boundaries.

• The mapping is diffeomorphic and unique under normalization.

• The mapping is invariant under conformal transformations.

• The number of unknown variables is reduced from $O(n^2)$ to $O(n)$.

Abstract

This work proposes a novel method for computing area-preserving parameterization for genus zero surfaces with multiple boundaries (poly-annuli), which is based on discrete optimal mass transportation and surface Ricci Flow. We first begin with a conformal mapping (which may greatly distort area) by Ricci Flow and then correct the area distortion using the mass transport procedure via a convex optimization. The method is intrinsic and stable, and the resulting parameterization preserves area element and minimizes angle distortion. Comparing with existing algorithms, our method is more general and flexible. It can handle surfaces with more complicated topology, and gives users full control of the target measure, such as the areas of the holes. We have tested the method for applications in various fields. Our experimental results demonstrate the efficiency and efficacy of the proposed method.

Introduction

Surface parameterization (Hormann et al., 2008, Sheffer et al., 2007) refers to the process of mapping a surface embedded in ${\mathbb{R}}^3$ to a canonical planar domain with minimal distortions, which has been utilized for a wide variety of applications (Sheffer et al., 2006) like remeshing (Floater and Reimers, 2001, Floater et al., 2002, Zhang et al., 2010), texture mapping (Dominitz and Tannenbaum, 2010, Lévy and Mallet, 1998, Lévy et al., 2002), morphing (Liu et al., 2008), and shape modeling (Sheffer et al., 2005, Floater, 1997, Floater and Hormann, 2005, Sheffer and Sturler, 2000).

In general, distortions can be classified to angle distortion and area distortion. If a parameterization has neither angle distortion nor area distortion, then it must be an isometric mapping, hence preserves Gaussian curvatures. In general, isometric mapping between a 3D surface and a planar domain doesn't exist. Therefore, in practice, research efforts focus on pursuing either angle-preserving parameterizations or area-preserving parameterizations.

Angle-preserving parameterizations preserve local shapes, therefore they are highly desirable for practical applications, such as texture mapping, visualization. Therefore, most existing algorithms emphasize on angle-preserving parameterizations. Many prominent approaches, such as conformal mapping, harmonic mapping and Ricci Flow that attempt to rigorously minimize the angular distortion have been introduced into the computer graphics community.

The angle-preserving mapping may bring huge area distortions in certain surfaces, for example, Fig. 2(b) shows large shrinkage of the lid of the world cup model. In fact, if one wants to conformally map a cylinder onto a planar annulus, the area distortion on the top is exponential with respect to the height of the cylinder. In turn, such distortions usually introduce much difficulty for the down streaming texture mapping and model processing. The exponential shrinkage makes the surface registration highly inaccurate, the geometric computation numerically unstable. In order to enlarge the insufficient texture area caused by the parameterization, topological surgeries need to be introduced, which makes the algorithm more complicated and less automatic.

Another surface parameterization approach is to minimize the area distortion. The most popular methods include quasi-area parameterization, Lie advection method and optimal mass transportation map method.

Quasi-area parameterization  A simple and fast method for generating low-stretch mesh parameterizations is shown in Yoshizawa et al. (2004).

Given a parameterized triangle mesh $M\in {\mathbf{R}}^3$, consider a mesh triangle $T\in M$ and its corresponding triangle U in the parametric plane ${\mathbf{R}}^2$. The correspondence between the vertices of T and U uniquely defines an affine mapping $P:U\to T$.

Define, quantity $\sigma (U)=\sqrt{({\mathrm{\Gamma }}^2+{\gamma }^2)/2}$ characterizes the stretch of mapping P, where Γ and γ are the maximal and minimal eigenvalues of the metric tensor induced by the mapping P. For each vertex $u_i$ in the parameter domain, its stretch $\sigma (u_i)$ is defined by

$$\sigma (u_i)=\sqrt{\sum A(T_j)\sigma {(U_j)}^2/\sum A(T_j)},$$

where $A(T)$ denotes the area of triangle T and the sums are taken over all triangles $T_j$ surrounding mesh vertex $p_i$ corresponding to $u_i$.

For each inner vertex $p_i\in M$ its corresponding vertex $u_i\in {\mathbf{R}}^2$, minimizes the local quadratic energy

$$E(u_i)=\sum _j{w}_{ij}{(u_j-u_i)}^2,$$

where $u_j$ are vertices corresponding to the mesh one-link neighbors of $p_i$ and $w_{ij}$ are positive weights. The optimal positions for $u_i$ are found by solving a sparse system of linear equations

$$\sum _j{w}_{ij}(u_j-u_i)=0.$$

Use the local stretch $\sigma (u_i)$ for each inner vertex $u_i$ in the parametric plane to estimate the weight $w_{ij}$ by assigning

$$w_{ij}^{\mathit{new}}=w_{ij}^{\mathit{old}}/\sigma (u_j).$$

The optimization is achieved by minimizing a weighted quadratic energy with positive weights chosen to minimize the parameterization stretch. The quasi-area parameter is fast since it is based on solving a sparse system of linear equations. In contrast, our method has solid mathematical foundation. Our experimental results demonstrate that our method outperforms this method.

Lie advection  The method in Zou et al. (2011) is based on Lie derivative and Cartan's formula. Given a surface S, the Lie advection method designs a time-variant tangent vector field on the surface $\mathbf{v}(t)$, each point $p\in S$ moves on the surface, at the time t the velocity vector of p is $\mathbf{v}(p,t)$. Therefore, we obtain a single-parameter family of diffeomorphisms ${\phi }_t:S\to S$, such that

$$\frac{d}{dt}{\phi }_t(p)=\mathbf{v}(p,t).$$

Suppose the area element on the surface is ω, the mapping ${\phi }_t$ induces the pull-back area element, denoted as ${\phi }_t^{⁎}\omega$, then by Cartan's formula, the Lie derivative of ω

$${\mathcal{L}}_{\mathbf{v}}\omega =\frac{d}{dt}{\phi }_t^{⁎}\omega =i_{\mathbf{v}}d\omega +d(i_{\mathbf{v}}\omega )=d(i_{\mathbf{v}}\omega ),$$

where the inner product of v and the 2-form ω is a 1-form, $i_{\mathbf{v}}\omega =\omega (\mathbf{v},\cdot )$. One can design the Lie derivative of ω to deform the current area element to the desired one, which is controlled by the vector field $\mathbf{v}(t)$. Therefore, by designing the vector field, one can manipulate the evolution of the area element. This method can handle surfaces with complicated topologies, incorporating landmark constraints. The method has some disadvantages: the solution is not unique, and the iterative procedure of designing time variant vector field is indirect and less efficient.

Optimal mass transportation (OMT)  Another approach to area-preserving parameterization is based on optimal mass transportation, which is also known as the “earth mover's problem” (Gu et al., 2016, Dominitz and Tannenbaum, 2010). Suppose $(X,\mu )$ and $(Y,\nu )$ are two domains in the Euclidean space with measures μ and ν respectively, $\phi :X\to Y$ is a diffeomorphism. We say φ is measure preserving, if for any Borel set $B\subset Y$, we have

$$\underset{B}{\int }\nu =\underset{{\phi }^{-1}(B)}{\int }\mu ,$$

equivalently, the PDE is given by

$$\mu =J_{\phi }\nu \circ \phi$$

where $J_{\phi }$ is the Jacobian of the mapping φ. The Optimal Mass Transportation map is a measure-preserving mapping, that minimizes the total transportation cost, namely,

$$\begin{array}{c}\hfill {\min }_{\phi }{\int }_{S}c(p,\phi (p))\mu (p)dp\hfill \\ \hfill s.t.\hfill \\ \hfill \mu =J_{\phi }\nu \circ \phi \hfill \end{array}$$

where $c(p,q)$ is the transportation cost for moving one unit mass from p to q. There are mainly two approaches to solve OMT problem: one is Kantorovich's approach (Kantorovich, 1948), and the other is Brenier's approach (Brenier, 1991).

Kantorovich's approach discretizes both the source and the target as point sets with Dirac measures, $\{(p_1,{\mu }_1),\cdots ,(p_m,{\mu }_m)\}$ and $\{(q_1,{\nu }_1),\cdots ,(q_n,{\nu }_n)\}$ respectively, such that ${\sum }_{i=1}^m{\mu }_i={\sum }_{j=1}^n{\nu }_j$, a transportation plan can be represented as $\{{\lambda }_{ij}\}$, which means the mass ${\lambda }_{ij}$ is moved from $p_i$ to $q_j$, then the optimal mass transportation plan is a linear programming problem:

$$\begin{array}{c}\hfill {\min }_{\lambda }{\sum }_{i=1}^m{\sum }_{j=1}^n{\lambda }_{ij}c(p_i,p_j),\hfill \\ \hfill s.t.\hfill \\ \hfill {\sum }_i{\lambda }_{ij}={\mu }_i,{\sum }_j{\lambda }_{ij}={\nu }_j.\hfill \end{array}$$

This method has $O(mn)$ unknowns, and the solution mapping is not as smooth as those obtained by the alternative methods.

Brenier (1991) observes that if the cost function $c(p,q)$ is the quadratic Euclidean distance $c(p,q)=|p-q{|}^2$, then there exists a convex function $u:S\to \mathbb{R}$, such that the optimal mass transportation map is given by the gradient map of u, $p\to \mathrm{\nabla }u(p)$. In this case, the measure-preserving condition in Eqn. (1) becomes Monge–Ampère equation,

$$det\left(\frac{{\partial }^{2}u}{\partial x_i\partial x_j}\right)\nu \circ \mathrm{\nabla }u=\mu .$$

The discrete OMT method discretizes the target as a point set with Dirac measures with only $O(n)$ unknowns. This method is equivalent to a convex optimization process, which can be achieved using more efficient Newton's method, and the solution is unique.

Our approach  Most existing optimal mass transportation method can only handle simply connected surfaces. An efficient method to compute area-preserving parameterizations for surfaces with complex topologies is highly advantageous for texture mapping and visualization in research area. In our current work, we propose a novel area-preserving parameterization algorithm, which is based on discrete optimal mass transportation (Gu et al., 2016) theory, and therefore it is equivalent to a convex optimization, with a unique solution. Furthermore, it is capable of handling genus zero surfaces with multiple boundaries (topological annuli).

Our method is as follows: first, the input topological annulus $(S,\mathbf{g})$ is conformally mapped onto a circle domain $\phi :(S,\mathbf{g})\to (\mathrm{\Omega },dzd\overline{z})$ using discrete Ricci flow method (Chow and Luo, 2003), where

$$\mathrm{\Omega }=\mathbb{D}\setminus \bigcup _{i=1}^{k}B(p_i,r_i),$$

and $B(p_i,r_i)$ is the disk centered at $p_i$ with radius $r_i$. Because φ is conformal, the original Riemannian metric on the surface $\mathbf{g}=e^{2\lambda }(d{x}^2+d{y}^2)$. On the unit disk, we define a measure $\mu :\mathbb{D}\to \mathbb{R}$,

$$\mu (p)=\{\begin{array}{cc}a{e}^{2\lambda (p)},\hfill & p\in \mathrm{\Omega }\hfill \\ b,\hfill & p\notin \mathrm{\Omega }\hfill \end{array},$$

where $a,b$ are two adjustable constants, such that ${\int }_{\mathbb{D}}\mu dxdy=\pi$. Then we compute the unique optimal mass transportation map $\tau :(\mathbb{D},\mu dx\wedge dy)\to (\mathbb{D},dx\wedge dy)$. The composition $\tau \circ \varphi :(S,\mathbf{g})\to \mathbb{D}$ is the desired area-preserving parameterization. Fig. 1 illustrates the pipeline of our approach.

Conformal parameterization  The literature for conformal mesh parameterization is vast, and a complete review is beyond the scope of the current work. We refer readers to the thorough surveys Floater and Hormann (2005), Sheffer et al. (2006) and Sheffer et al. (2007). Many existing parameterizations focus on minimizing angle distortion, such as the method based on Riemann–Cauchy equation (Lévy et al., 2002), harmonic energy minimization (Desbrun et al., 2002), holomorphic differentials (Gu and Yau, 2003), most isometric parameterizations (MIPS) (Hormann et al., 1999), angle-based flattening (Sheffer and de Sturler, 2001), conformal equivalence meshes (Springborn et al., 2008), curvature flows (Jin et al., 2008), conformal equivalence (Springborn et al., 2008), spin transformation (Crane et al., 2011) and so on.

Locally injective and bounded distortion mappings  Schüller et al. (2013) modify any deformation energy to guarantee a locally injective mapping. Levi and Zorin prioritize higher distortion for minimization and provide a minimal $L_{\infty }$-norm solution for distortion control (Levi and Zorin, 2014). Fu et al. introduce an advanced MIPS method that inherits the local injectivity of MIPS, achieves as low as possible distortions with high efficiency. Their method depends on an enhanced MIPS energy function that penalizes the maximal distortion and distributes the distortion evenly, and the inexact block coordinate descent method that avoids local optima.

Lipman (2012), Aigerman and Lipman (2013), Kovalsky et al., 2014, Kovalsky et al., 2015 propose to construct a maximal convex subspace, which is the continuous piecewise linear mapping space for bounding the maximal distortion and ensuring no inverted mesh elements. Locally injective mapping with bounded distortion is guaranteed when the algorithms converge. The algorithm is iterative, a quadratic programming or semidefinite programming problem needs to solve at each step. A feasible solution space may not exist if the convex subspace is empty or the upper bound of distortion is too small. In contrast, our method has theoretical advantages that the solution exists and is unique, the algorithm converges to the unique global optimum.

Optimal mass transport 

(a) Monge–Kantorovich  For optimal mass transport, some approaches based on Monge–Kantorovich theory have been proposed. Zhu et al. (2003) applied optimal mass transport for flattening blood vessel in an area preserving mapping for medical visualization. Haker et al. (2004) proposed to use optimal mass transport for image registration and warping, the method is parameter free and has the unique global optimum. Dominitz and Tannenbaum (2010) proposed to use optimal mass transport for texture mapping. The method first starts with an angle-preserving mapping and then refines the mapping using the mass transport procedure derived via gradient flow. Rehman et al. (2009) presented a method for 3D image registration based on optimal mass transport problem. Meanwhile, they stress the fact that the optimization of OMT is computationally expensive and emphasize that it is important to find efficient numerical methods to solve this issue, and it is crucial to extend the results to 3D surfaces.

(b) Monge–Brenier  There are also some works based on Monge–Brenier theory. Su et al. proposed an area-preserving mapping method for brain morphological study. Zhao et al. proposed an OMT based method for visualization in Zhao et al. (2013). But these methods can only compute the maps from the unit disk domain with Euclidean measure to another disk with general measure.

Mérigot (2011) has proposed a multi-scale approach to solve optimal transport problem. De Goes et al. (2011) have provided an optimal-transport driven approach for 2D shape reconstruction and simplification. Recently they have presented a formulation of capacity-constrained Voronoi tessellation as an optimal transport problem for image processing (de Goes et al., 2012). This method produces high-quality blue noise point sets with improved spectral and spatial properties.

In summary, the current work has the following contributions:

• This work offers an area-preserving surface parameterization method that is able to handle complicated topologies, such as genus zero surfaces with multiple boundaries.

• The mapping is diffeomorphic and unique under normalization. Moreover, the mapping is invariant under conformal transformations.

• Comparing to existing approaches based on Monge–Kantorovich theory, our method reduces the number of unknown variables from $O(n^2)$ to $O(n)$.

The outline of the remainder of this paper is as follows: In Section 2, we demonstrate the theoretical foundation of Ricci Flow and optimal mass transportation. In Section 3, we discuss some relevant implementation issues. In Section 4, we give some illustrative examples of our scheme, and present an evaluation of the running time and distortion measures of our method, compare with stretch minimization method (Yoshizawa et al., 2004). Finally, in Section 5, we summarize our work and give some possible future research directions.