Convergence Analysis of Volumetric Stretch Energy Minimization and its Associated Optimal Mass Transport Tsung-Ming Huangy Wei-Hung Liaoz Wen-Wei Linx Mei-Heng YuehandShing-Tung

2025-05-06 0 0 3.29MB 26 页 10玖币

侵权投诉

Convergence Analysis of Volumetric Stretch Energy Minimization and its

Associated Optimal Mass Transport ∗

Tsung-Ming Huang†, Wei-Hung Liao‡, Wen-Wei Lin§, Mei-Heng Yueh¶,and Shing-Tung

Yauk

Abstract. The volumetric stretch energy has been widely applied to the computation of volume-/mass-

preserving parameterizations of simply connected tetrahedral mesh models. However, this approach

still lacks theoretical support. In this paper, we provide the theoretical foundation for volumetric

stretch energy minimization (VSEM) to compute volume-/mass-preserving parameterizations. In

addition, we develop an associated eﬃcient VSEM algorithm with guaranteed asymptotic R-linear

convergence. Furthermore, based on the VSEM algorithm, we propose a projected gradient method

for the computation of the volume/mass-preserving optimal mass transport map with a guaranteed

convergence rate of O(1/m), and combined with Nesterov-based acceleration, the guaranteed con-

vergence rate becomes O(1/m2). Numerical experiments are presented to justify the theoretical

convergence behavior for various examples drawn from known benchmark models. Moreover, these

numerical experiments show the eﬀectiveness and accuracy of the proposed algorithm, particularly

in the processing of 3D medical MRI brain images.

Key word. volume-/mass-preserving parameterization, optimal mass transport, R-linear convergence, projected

gradient method, Nesterov-based acceleration, O(1/m) convergence

MSC codes. 68U05, 65D18, 52C35, 33F05, 65E10

1. Introduction. Volume-/mass-preserving parameterization of a 3-manifold Mwith a

single closed genus-zero boundary by a unit ball B3, as well as its associated optimal mass

transport (OMT), has been widely applied to computer graphics [11], digital geometry [15],

medical image segmentation [24,25], image retrieval [23,27], image representation and reg-

istration [14,18,19,29] and generative adversarial networks [22]. In calculus, we learn that

a 2-manifold or 3-manifold can be represented by a given 2D or 3D coordinate system, and

then the related curvatures, singularities, maxima, minima, local areas or volume can be com-

puted. In contrast, in practical applications, irregular manifold domains are usually obtained

by scanning or sampling data from physical objects. For instance, CT, MRI and PET images

are the most common in medical diagnosis, real-time scanning images by satellite for space

engineering and weather forecasting, photomicrography in physical and biological engineering,

∗Submitted to the editors October 19, 2022.

Funding: The work of the authors was partially supported by the National Science and Technology Council, the

National Center for Theoretical Sciences, and the ST Yau Center in Taiwan. T.-M. Huang, W.-W. Lin, and M.-H.

Yueh was partially supported by NSTC 110-2115-M-003-012-MY3, 110-2115-M-A49-004- and 111-2115-M-003-016-,

respectively.

†Department of Mathematics, National Taiwan Normal University, Taipei, 116, Taiwan (min@ntnu.edu.tw).

‡Department of Applied Mathematics, National Yang Ming Chiao Tung University, Hsinchu, 300, Taiwan

(roger2300245@gmail.com).

§Department of Applied Mathematics, National Yang Ming Chiao Tung University, Hsinchu, 300, Taiwan

(wwlin@math.nctu.edu.tw).

¶Department of Mathematics, National Taiwan Normal University, Taipei, 116, Taiwan (yue@ntnu.edu.tw).

kYau Mathematical Sciences Center, Tsinghua University, Beijing, 100084, China (styau@tsinghua.edu.cn).

arXiv:2210.09654v1 [math.NA] 18 Oct 2022

2 T.-M. HUANG, W.-H. LIAO, W.-W. LIN, M.-H. YUEH, AND S.-T. YAU

target or obstacle detection for autonomous driving systems and missile navigation, etc. One

intuitive idea is to directly calculate numerical solutions for complex problems on irregular

manifolds. If the irregular manifold domain is too technically challenging to produce solutions

for a complex problem, we should consider the inverse problem of the above problem; that

is, the irregular manifold should be parameterized by a regular domain. The most common

3D parametric shapes are a cube or a ball B3. To this end, eﬃcient algorithms, namely, the

volumetric stretch energy minimization (VSEM) method [31] and OMT methods [13] for the

computation of volume-preserving parameterizations, have recently been highly developed and

utilized in applications. In practice, in terms of the eﬀectiveness and accuracy, the VSEM

algorithm is much improved compared to the other state-of-the-art algorithms (see [31] for

details). However, VSEM still lacks rigorously mathematical and theoretical support.

In this paper, we ﬁrst introduce the volumetric stretch energy functional on Mand propose

the VSEM algorithm for the computation of the spherical volume-/mass-preserving parame-

terization between Mand B3. We show that a minimal solution for the volumetric stretch

energy functional must be a volume-/mass-preserving map, and vice versa, which successfully

supports the setting for our modiﬁed volume stretch energy functional. Then, we prove that

the VSEM algorithm converges R-linearly under some mild conditions. Next, we consider an

early but important OMT problem proposed by Monge in 1781 (see, e.g., [4]) in which a pile

of soil is moved from one place to another while preserving the local volume and minimizing

the transport cost. Although the set of volume-/mass-preserving maps between Mand B3

may not be convex, for the discrete OMT problem we still prefer to adopt the projected gra-

dient method to minimize the transport cost for preserving the minimal deformation between

Mand B3. Then, we accelerate the convergence by the Nesterov method [26]. Under mild

assumptions of nonexpensiveness and projection properties, the convergence of the projected

gradient method can be proven to be a rate of O(1/m), and with the acceleration, it has a

convergence rate of O(1/m2). This numerical algorithm is called the volume-/mass-preserving

OMT (VOMT) algorithm. It is eﬀective, reliable and robust.

The main contributions of this paper are threefold.

1. We prove a fundamental theorem that f∗is the minimal solution of the discrete volu-

metric stretch energy functional if and only if f∗is volume-/mass-preserving between

Mand B3. Based on this mathematical foundation, we develop a VSEM for the

computation of the minimal solution f∗and show the R-linear convergence of VSEM.

2. For the discrete OMT problem, we use the gradient method combined with VSEM as a

projector to develop an eﬃcient numerical algorithm, VOMT, for solving the spherical

VOMT problem from Mto B3with a convergence rate of O(1/m) and, accelerated

by the Nesterov method, with a convergence rate of O(1/m2).

3. In practical applications on various benchmarks, numerical experiments conﬁrm that

the assumption for R-linear convergence is satisﬁed, and the related means and stan-

dard deviation of the ratios of local volume distortions show the eﬀectiveness and

exactness of the proposed VOMT algorithm.

The remaining part of this paper is organized as follows: In Section 2, we introduce the

discrete 3-manifold and the volumetric stretch energy. In Section 3, we propose a rigorous

derivation for the equivalence relationship between the volume-/mass-preserving map and the

minimizer of the volumetric stretch energy. In Section 4, we prove the convergence of the

CONVERGENCE ANALYSIS OF VSEM AND ASSOCIATED OMT 3

VSEM algorithm in [31] for the computation of volume-/mass-preserving parameterizations,

which provides theoretical support for the VSEM. Then, we introduce the associated VOMT

algorithm as well as its convergence analysis in Section 5. Numerical experiments for the

VSEM and VOMT are demonstrated in Section 6to validate the consistency between the

theoretical and numerical results. Concluding remarks are given in Section 7.

In this paper, we use the following notations:

•Bold letters, e.g., f, denote real-valued vectors or matrices.

•Capital letters, e.g., L, denote real-valued matrices.

•Typewriter letters, e.g., Iand B, denote ordered sets of indices.

•fidenotes the ith row of the matrix f.

•fsdenotes the sth column of the matrix f.

•fIdenotes the submatrix of fcomposed of fi, for i∈I.

•Li,j denotes the (i, j)th entry of the matrix L.

•LI,Jdenotes the submatrix of Lcomposed of Li,j for i∈Iand j∈J.

•Rdenotes the set of real numbers.

•B3:= {x∈R3| kxk ≤ 1}denotes the solid ball in R3.

•[v0,...,vk] denotes the k-simplex with vertices v0,...,vk.

• |[v0,...,vk]|denotes the volume of the k-simplex [v0,...,vk].

•0and 1denote the zero and one vectors or matrices of appropriate sizes, respectively.

•Given two vectors xand y,x·ydenotes the inner product x>y.

•Hashtag # of a set, e.g., #(T(M)), denotes the number of elements in T(M).

2. Discrete 3-manifold and volumetric stretch energy. Let M ⊂ R3be a simply con-

nected 3-manifold with a single genus-zero boundary. A discrete 3-manifold model for Mis

a simplicial 3-complex with nvertices

V(M) = {vt= (v1

t, v2

t, v3

t)∈R3}n

t=1,

and tetrahedra

T(M) = {[vi,vj,vk,v`]⊂R3for some vr∈V(M), r=i, j, k, `},

where the bracket [vi,vj,vk,v`] is the 3-simplex (convex hull) of the aﬃnely independent

points {vr|r=i, j, k, `}. Additionally, the triangular faces and edges of Mare denoted by

F(M) = {[vi,vj,vk]|[vi,vj,vk,v`]∈T(M) with some v`∈V(M)}

and

E(M) = {[vi,vj]|[vi,vj,vk]∈F(M) with some vk∈V(M)}.

Because an aﬃne map in R3is determined by four independent point correspondences, a

piecewise aﬃne map f:M → R3on a tetrahedral mesh Mcan be expressed as an n×3

matrix deﬁned by the images f(vt) of vertices vt∈V(M) as

f:= [f>

1,··· ,f>

n]>∈Rn×3,(2.1)

4 T.-M. HUANG, W.-H. LIAO, W.-W. LIN, M.-H. YUEH, AND S.-T. YAU

where ft:= f(vt) = (f1

t, f2

t, f3

t)∈R3, for t= 1, . . . , n. We also denote

f=f1f2f3,fs=fs

1··· fs

n>, s = 1,2,3.

For a point v∈ M,vmust belong to a tetrahedron τ; without loss of generality, let τ=

[v1,v2,v3,v4]. Then, the piecewise aﬃne map f(v) : T(M)→R3can be expressed as a linear

combination of {fi}4

i=1 with barycentric coordinates, i.e.,

f|τ(v) =

i=1

λif(vi), λi=1

|τ||[v1,··· ,b

vi,··· ,v4]|

where b

viis replaced by vfor i= 1,...,4, and |τ|denotes the volume of the 3-simplex τ. The

piecewise aﬃne map f:M → B3is said to be induced by fand is volume-/mass-preserving

if the Jacobian Jf−1= [∂f −1

∂u1,∂f −1

∂u2,∂f −1

∂u3] satisﬁes

(2.2) det(Jf−1|f(τ)) = 1

with f(τ) = [fi,fj,fk,f`] for every τ= [vi,vj,vk,v`]∈T(M). Like the derivation in [31,

Appendix A], f:M → R3is volume-/mass-preserving with respect to the tetrahedral volume

measure µ:T(M)→R+if and only if (2.2) holds for every τ∈T(M). We denote the stretch

factor with respect to µas

σµ,f−1(τ) = µ(τ)/|f(τ)|.(2.3)

The original VSEM [31] computes a spherical volume-preserving parameterization between

Mand B3with µ(τ) = |τ|by minimizing the volumetric stretch energy functional,

EV(f) = 1

2trace(f>LV(f)f)(2.4)

where LV(f) is a volumetric stretch Laplacian matrix with

[LV(f)]ij = [LV(f)]>

ij =









wij(f),if [vi,vj]∈E(M),

−P`6=iwi`(f),if j=i,

0,otherwise,

(2.5a)

in which, like [30], the modiﬁed weight wij(f) is deﬁned by

wij(f) = −1

τ∈T(M)

[vi,vj]∪[vk,v`]⊂τ

[vi,vj]∩[vk,v`]=∅

|f([vi,vk,v`])||f([vj,v`,vk])|cos θk,`

i,j (f)

σµ,f−1(τ)|f(τ)|

=−1

36 X

τ∈T(M)

[vi,vj]∪[vk,v`]⊂τ

[vi,vj]∩[vk,v`]=∅

(2|f([vi,vk,v`])|) (2|f([vj,vk,v`])|) cos θk,`

i,j (f)

µ(τ)

=−1

36 X

τ∈T(M)

[vi,vj]∪[vk,v`]⊂τ

[vi,vj]∩[vk,v`]=∅

[(fk−fi)×(f`−fi)]>[(f`−fj)×(fk−fj)]

µ(τ).(2.5b)

CONVERGENCE ANALYSIS OF VSEM AND ASSOCIATED OMT 5

Here, θk,`

i,j (f) is the dihedral angle between the triangular faces f([vi,vk,v`]) and f([vj,v`,vk])

in tetrahedron f(τ). In Sections 3and 4we will provide the theoretical foundation of SVEM.

Remark 2.1. In practice, the dihedral angle θk,`

i,j (f) is computed by using the identity

cos(π−θk,`

i,j (f)) = ni,k,`(f)>nj,k,`(f),

where ni,j,k(f) denotes the unit normal vector of face f([vi, vj, vk]).

3. Volume-/mass-preserving parameterization vs. volumetric stretch energy mini-

mizer. Let Mbe a simply connected 3-manifold with a genus-zero boundary. We consider

the volumetric stretch energy functional on Mas in (2.4),

EV(f) = 1

2trace f>LV(f)f=1

s=1

fs>LV(f)fs,(3.1)

where LV(f) is the volumetric stretch Laplacian matrix as in (2.5).

In Subsection 3.1, we ﬁrst show the equivalence of volumetric stretch energy minimizers

and volume-/mass-preserving parameterizations. In Subsection 3.2, we provide a neat gradient

formula of EVso that the minimizers of EVwith a ﬁxed spherical boundary constraint can

be conveniently derived in Subsection 3.3.

To simplify the derivations in Subsections 3.1 and 3.2, we denote the volumetric stretch

energy restricted to a tetrahedron τ∈T(M) as Eτ(f(τ)) with Laplacian matrix Lτ(f)≡

LV(f)|τ. Then, the volumetric stretch energy functional EV(f) in (3.1) is equal to the sum-

mation of all Eτ(f(τ)). According to (2.5), we give a new representation of Lτ(f) as follows.

Without loss of generality, let τ= [v1,v2,v3,v4] be a tetrahedron in T(M). Then, the

image of f(τ) is [f1,f2,f3,f4]. By substituting (2.5b) into LV(f)|τof (2.5a), we obtain

Lτ(f) = −1

36µ(τ)[aij]∈R4×4,(3.2a)

where, for [vi,vj]∩[vk,v`] = ∅and i, j, k, ` ∈ {1,2,3,4},

aij = [(fk−fi)×(f`−fi)]>[(f`−fj)×(fk−fj)], aij =aji

(3.2b)

and

aii =−X

j6=i

aij.(3.2c)

Applying the fundamental identity

(a×b)>(x×y)=(a>x)(b>y)−(a>y)(b>x),

aij of (3.2b) can be expanded into the form

aij =−[(fk−fi)>(fk−fj)][(f`−fi)>(f`−fj)](3.3)

+ [(fk−fi)>(f`−fj)][(f`−fi)>(fk−fj)].

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ConvergenceAnalysisofVolumetricStretchEnergyMinimizationanditsAssociatedOptimalMassTransportTsung-MingHuangy,Wei-HungLiaoz,Wen-WeiLinx,Mei-HengYueh{,andShing-TungYaukAbstract.Thevolumetricstretchenergyhasbeenwidelyappliedtothecomputationofvolume-/mass-preservingparameterizationsofsimplyconnectedtet...

展开>> 收起<<

Convergence Analysis of Volumetric Stretch Energy Minimization and its Associated Optimal Mass Transport Tsung-Ming Huangy Wei-Hung Liaoz Wen-Wei Linx Mei-Heng YuehandShing-Tung.pdf

共26页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Convergence Analysis of Volumetric Stretch Energy Minimization and its Associated Optimal Mass Transport Tsung-Ming Huangy Wei-Hung Liaoz Wen-Wei Linx Mei-Heng YuehandShing-Tung

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: