基于稀疏解組合優(yōu)化的廣義重心坐標(biāo)

彭豐富，方 明

?

基于稀疏解組合優(yōu)化的廣義重心坐標(biāo)

彭豐富，方 明

(桂林電子科技大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林 541004)

根據(jù)廣義重心坐標(biāo)線性運(yùn)算的性質(zhì)與特點(diǎn)，運(yùn)用廣義重心坐標(biāo)的稀疏解權(quán)函數(shù)的調(diào)和平均組合方法，對(duì)空間凸多面體頂點(diǎn)設(shè)計(jì)了一種求解廣義重心坐標(biāo)的算法，且權(quán)函數(shù)是帶有保形參數(shù)的一元函數(shù)，因而具有保形優(yōu)化的特點(diǎn)。構(gòu)造了2種不同類(lèi)型的帶形參權(quán)函數(shù)，運(yùn)用不同權(quán)函數(shù)及其參數(shù)的廣義重心坐標(biāo)將平面圖形映射到空間曲面的實(shí)例進(jìn)行了分析，并應(yīng)用重心坐標(biāo)常用的等值線工具對(duì)保形性進(jìn)行了比較。

廣義重心坐標(biāo)；稀疏解；組合優(yōu)化；權(quán)函數(shù)

M?BIUS[1]于1827年首先提出了位于三角形內(nèi)任一點(diǎn)的重心坐標(biāo)的概念，即該點(diǎn)表示為相應(yīng)3個(gè)頂點(diǎn)的加權(quán)系數(shù)為該點(diǎn)的重心坐標(biāo)。通過(guò)對(duì)頂點(diǎn)加權(quán)方法可以推廣到任意多邊形，稱(chēng)之為廣義重心坐標(biāo)(generalized barycentric coordinate，GBC)。GBC在有限元計(jì)算、網(wǎng)格編輯、計(jì)算機(jī)圖形學(xué)等有著廣泛的應(yīng)用，由于GBC的不唯一性，從而不同的方法所計(jì)算的重心坐標(biāo)有差異。目前，主要有多種基于平面多邊形提出的方法，并一直在發(fā)展、應(yīng)用這些理論，同時(shí)也有一些新的方法在不斷提出。

1976年WACHSPRESS[2]首次提出了第一種建立在任意凸多邊形的GBC：Wachspress coordinates (W坐標(biāo))，其計(jì)算量較小，得到了如仿射不變形、光滑性等較好的性質(zhì)，其不足是不能處理非凸多邊形。1995年ECK等[3]基于能量最小原理提出了離散調(diào)和(discrete harmonic)的GBC，其與W坐標(biāo)有許多相似性質(zhì)，但不要求坐標(biāo)的非負(fù)性。2003年FLOATER[4]提出了均值廣義重心坐標(biāo)，其可以對(duì)任意多邊形計(jì)算重心坐標(biāo)，可以為非凸的，且不要求坐標(biāo)非負(fù)。2004年馮結(jié)青和趙豫紅[5]分析和比較了各種重心坐標(biāo)的定義方法，提出一種魯棒的均值重心坐標(biāo)計(jì)算方法，并從理論和實(shí)驗(yàn)兩方面證明了均值重心坐標(biāo)在多邊形邊界上的拉格朗日性質(zhì)和線性性質(zhì)。2005年谷留新和劉克軒[6]將改進(jìn)的均值坐標(biāo)應(yīng)用于平面多邊形的變形，提出一種基于多邊形星形分解的同構(gòu)三角網(wǎng)格剖分算法，選用較少的額外點(diǎn)降低了算法復(fù)雜度。2015年DENG等[7]對(duì)于Floater提出的四邊形的廣義重心坐標(biāo)族的極限給出了證明。2016年CHEN和GOTSMAN[8]提出由于調(diào)和坐標(biāo)一般沒(méi)有封閉的形式，因此必須通過(guò)求解一個(gè)關(guān)于域的離散化的大型線性方程進(jìn)行數(shù)值逼近。2016年FLOATER[9]又研究了凸多邊形中常見(jiàn)的幾種廣義重心坐標(biāo)的單調(diào)性，并發(fā)現(xiàn)這些GBC有共同的簡(jiǎn)單的單調(diào)性：與一個(gè)頂點(diǎn)相關(guān)的坐標(biāo)函數(shù)沿著多邊形邊界到此頂點(diǎn)的任意直線遞增。áKOS[10]對(duì)W坐標(biāo)、調(diào)和坐標(biāo)及均值坐標(biāo)3種GBC方法做了詳細(xì)地闡述，并運(yùn)用等值線作為工具進(jìn)行了比較。

上述GBC方法的提出主要針對(duì)平面多邊形，并且都是基于點(diǎn)線面之間的距離、面積、角度等尺度關(guān)系來(lái)構(gòu)造權(quán)系數(shù)，優(yōu)點(diǎn)是其幾何意義明顯，缺點(diǎn)是難以做到保形及形狀調(diào)配和優(yōu)化。近二十年，該方法又被推廣到空間多面體領(lǐng)域。2007年JU等[11]對(duì)Mean value坐標(biāo)進(jìn)行了拓展，推廣應(yīng)用于3D四面體及高維單形多面體的研究。2011年WACHSPRESS[12]對(duì)運(yùn)用W坐標(biāo)構(gòu)造有理基函數(shù)應(yīng)用于多邊形和四面體做了相應(yīng)的研究和總結(jié)。2013年GUESSAB[13]對(duì)任意凸多面體應(yīng)用重心坐標(biāo)得到的一元凸函數(shù)進(jìn)行了逼近分析。本文基于四面體的仿射變換應(yīng)用重心坐標(biāo)對(duì)曲線曲面的構(gòu)造也得到了一些結(jié)論[14-16]。

本文基于GBC本身的代數(shù)性質(zhì)來(lái)構(gòu)造其計(jì)算方法，使得重心坐標(biāo)的計(jì)算回到其向量運(yùn)算的本源，并對(duì)該方法進(jìn)行算法優(yōu)化，同時(shí)考慮基于保形的坐標(biāo)優(yōu)化。

1 稀疏解組合廣義重心坐標(biāo)

1.1 單形的稀疏解

其中，≥0，由于重心坐標(biāo)的規(guī)范性，其可以等價(jià)于[n]=(0,1,···,–1,+1,···,)T。因而式(1)等價(jià)于

1.2 單形的選取準(zhǔn)則

在R3中設(shè)計(jì)了如下的最簡(jiǎn)單形取法和求解稀疏解：

輸入：空間數(shù)據(jù)點(diǎn){}，；

輸出：最簡(jiǎn)單形{}，稀疏解。

步驟1.=0={}(=1,2,···,)；

步驟2.3. 若步驟2.2中的假設(shè)不成立，擴(kuò)充到0中尋找，找到可能重復(fù)的2，3，同樣得到非零數(shù)為4的稀疏解；

步驟2.4. 否則為邊界面上的內(nèi)點(diǎn)，由={,1,2,3}確定非零數(shù)不超過(guò)3的稀疏解；

步驟3.={}，重復(fù)步驟2。

圖1 R3中最簡(jiǎn)單形選取方法

2 稀疏解的組合

對(duì)于GBC的連續(xù)性有如下定理。

權(quán)函數(shù)u()的選取目標(biāo)是使得GBC變換對(duì)曲線具有保形性，譬如將一條平面線段通過(guò)GBC描述到一個(gè)曲面上，理想的保形是確保映射到曲面的是一條測(cè)地線，由于其優(yōu)化計(jì)算過(guò)于復(fù)雜，一般也可以通過(guò)能量最小的方法進(jìn)行優(yōu)化處理。對(duì)單形()的u()計(jì)算時(shí)，選取()的幾何重心與的距離d(V())作為參數(shù)來(lái)進(jìn)行優(yōu)化，直觀地理解是u()應(yīng)該隨d的增大而減少，也就是單形的重心與越近，該單形占有權(quán)重越大。其函數(shù)關(guān)系如一些文獻(xiàn)選取概率密度函數(shù)或其他的遞減函數(shù)?？蓮挠?jì)算的角度及重心坐標(biāo)的性質(zhì)出發(fā)，構(gòu)造二者的2個(gè)實(shí)驗(yàn)函數(shù)

3 實(shí)例分析

從圖中可以看出，前者參數(shù)具有較好的保形性和等值曲線的光順性，而后者保形性和光順性都比較差，其原因是權(quán)重函數(shù)的遞減速度太快，導(dǎo)致圖形某些方向的收縮過(guò)大，從而導(dǎo)致等值曲線的曲率急速增大。

圖2 式(4)參數(shù)(x,y)=(2,0)將平面圖形映射到曲面

圖3 式(4)參數(shù)(x,y)=(1,2)把平面圖形映射到曲面

圖4 式(5)中z=1的平面圖形映射及等值線

圖5描述的是不同權(quán)函數(shù)關(guān)于d的變化情況。

圖5 不同權(quán)函數(shù)ui (P)關(guān)于di的變化情況

4 結(jié)束語(yǔ)

為了求解空間廣義重心坐標(biāo)，根據(jù)廣義重心坐標(biāo)本源的線性運(yùn)算性質(zhì)，運(yùn)用稀疏解權(quán)函數(shù)組合的方法，對(duì)空間凸多面體頂點(diǎn)構(gòu)造了一種求解重心坐標(biāo)的方法，且能選擇參數(shù)對(duì)保形效果進(jìn)行優(yōu)化調(diào)配。在實(shí)例中的等值線均為離散的點(diǎn)，所以未考慮先插值再計(jì)算曲率進(jìn)行對(duì)比，從實(shí)例的計(jì)算結(jié)果也驗(yàn)證了方法的可行性。對(duì)非凸情形本文未考慮，若是取消重心坐標(biāo)的非負(fù)性，方法應(yīng)該可以推廣。

未來(lái)工作的展望主要包括：①對(duì)GBC變換的保形性可以用直線映射到測(cè)地線為目標(biāo)的優(yōu)化方法來(lái)研究，但是計(jì)算量可能會(huì)相當(dāng)大；②對(duì)光滑曲面的映射保形可以選用連續(xù)的帶參數(shù)的概率密度函數(shù)作保形優(yōu)化處理，已有文獻(xiàn)對(duì)連續(xù)閉合曲線的情形給予了討論，但是對(duì)空間閉合曲面還有一定的挑戰(zhàn)；③設(shè)計(jì)自適應(yīng)的方法來(lái)保形優(yōu)化，而不是對(duì)全局進(jìn)行參數(shù)優(yōu)化，雖然會(huì)增加計(jì)算量，但是在細(xì)節(jié)上可以得到更好的效果。

[1] M?BIUS A F. Derbarycentrischecalcul [D]. Leipzig: Nabu Press, 2010.

[2] WACHSPRESS E L. A rational finite element basis [J]. Journal of Tribology, 1976, 98(4): 635.

[3] ECK M, DEROSC T, DUCHAMP, et al. Multiresolution analysis of arbitrary meshes [C]//In SIGGRAPH ’95: Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1995: 173-182.

[4] FLOATER M S. Mean value coordinates [J]. Computer Aided Geometric Design, 2003, 20(1): 19-27.

[5] 馮結(jié)青, 趙豫紅. 均值重心坐標(biāo)的魯棒算法及其幾何性質(zhì)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2004, 16(6): 772-776.

[6] 谷留新, 劉克軒. 改進(jìn)的基于Mean value重心坐標(biāo)的多邊形變形[J]. 計(jì)算機(jī)工程與應(yīng)用, 2005, 41(29): 74-76.

[7] DENG C Y, SHI F F, LIU J Z. The limit of barycentric coordinates for quadrilaterals [J]. Computer Aided Geometric Design, 2015, 38(C): 38-39.

[8] CHEN R J, GOTSMAN C. On pseudo-harmonic barycentric coordinates [J]. Computer Aided Geometric Design, 2016, 44(15): 15-35.

[9] FLOATER M S. On the monotonicity of generalized barycentric coordinates on convex polygons [J]. Computer Aided Geometric Design, 2016, 42: 34-39.

[10] áKOS T. Comparison and affine combination of generalized barycentric coordinates for convex polygons [J]. Annales Mathematicaeet Informaticae, 2017, 47: 185-200.

[11] JU T, LIEPO P, WARREN J. A general geometric construction of coordinates in a convex simplicial polytope [J]. Computer Aided Geometric Design, 2007, 24(3): 161-178.

[12] WACHSPRESS E L. Barycentric coordinates for polytopes [J]. Computers and Mathematics with Applications, 2011, 61(11): 3319-3321.

[13] GUESSAB A. Generalized barycentric coordinates and approximations of convex functions on arbitrary convex polytopes [J]. Computers and Mathematics with Applications, 2013, 66(6): 1120-1136.

[14] CHEN J J, PENG F F. Approximate spline of G2-continuity on a generalized hyperbolic paraboloid [J]. Journal of Computational and Applied Mathematics, 2013, 248(2): 99-117.

[15] PENG F F, HAN X L. Parametric splines on a hyperbolic paraboloid [J]. Journal of Computational and Applied Mathematics, 2009, 229(1): 183-191.

[16] PENG F F, CHEN J J. Spline on a generalized hyperbolic paraboloid [J]. Journal of Computational and Applied Mathematics, 2011, 235(8): 2451-2458.

Generalized Barycentric Coordinates Based on Combinatorial Optimization of Sparse Solutions

PENG Feng-fu, FANG Ming

(School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China)

According to the nature and characteristic of the linear operation of generalized barycentric coordinates, by means of a combination of weighted harmonic mean funcitons, an algorithm for solving generalized barycentric coordinates is designed to meet the demands of the vertexes of spatial convex polyhedron, in which the weighted function is a unary function with conformal parameters, thus it is characterized with conformal optimization. Two different types of weighted functions are constructed in this paper, and they are both used to calculate the generalized barycentric coordinates. An example of a plane figure is mapped into a space surface by the means, which is to be described and analyzed with different weighted functions and parameters. By means of their contours, the generalized barycentric coordinates for the example are analyzed and compared.

generalized barycentric coordinates; sparse solution; combinatorial optimization; weighted functions

TP 391

10.11996/JG.j.2095-302X.2019010054

A

2095-302X(2019)01-0054-05

2018-06-18；

2018-06-28

國(guó)家自然科學(xué)基金項(xiàng)目(1170119)；廣西高校數(shù)據(jù)分析與計(jì)算重點(diǎn)實(shí)驗(yàn)室項(xiàng)目

彭豐富(1972-)，男，湖南婁底人，博士，副教授。主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)。E-mail：pengfengfu@aliyun.com