任意多邊形上基于ADMM的最小二乘坐標(biāo)

范俠麗，王偉娜，鄧重陽，李亞娟

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

0 引 言

重心坐標(biāo)是計(jì)算機(jī)圖形學(xué)和數(shù)學(xué)領(lǐng)域的一個重要研究方向，由A.F.Mobius于1827年首次提出，應(yīng)用于圖像和幾何處理以及其他相關(guān)領(lǐng)域，如網(wǎng)格參數(shù)化[1]、網(wǎng)格變形[2]、形狀變形[3]和合成[4]等。近年來，眾多學(xué)者提出了許多不同的重心坐標(biāo)構(gòu)造方法。E.L.Wachspress[5]在廣義有限元方法的背景下，提出一種有理重心坐標(biāo)函數(shù)的構(gòu)造方法，在凸多邊形上，有效計(jì)算Wachspress坐標(biāo)，但在任意簡單多邊形上并沒有明確的定義。M.S.Floater[6]在網(wǎng)格參數(shù)化的背景下，提出均值坐標(biāo)，在任意簡單多邊形上都有明確的定義，但在凹多邊形內(nèi)部的部分點(diǎn)會產(chǎn)生負(fù)均值坐標(biāo)，不滿足非負(fù)性。隨后，為了使得到的坐標(biāo)滿足非負(fù)性，基于優(yōu)化方法的重心坐標(biāo)得到了很大的發(fā)展。P.Joshi等[7]基于帶有特定邊界條件的Laplace方程的標(biāo)準(zhǔn)有限元離散化方法，提出了調(diào)和坐標(biāo)。Zhang J.Y.等[8]基于最小化全變差模型，提出了局部重心坐標(biāo)。相對于調(diào)和坐標(biāo)，局部坐標(biāo)具有更好的局部支撐性。調(diào)和坐標(biāo)和局部重心坐標(biāo)雖然能夠很好地保證非負(fù)性，但均涉及到區(qū)域的三角剖分，不同的三角剖分結(jié)果往往會產(chǎn)生不同的重心坐標(biāo)[9]。為了克服上述局限性，本文提出一種適用于任意簡單多邊形的廣義重心坐標(biāo)，通過最小化基于2正則化模型的最小二乘目標(biāo)函數(shù)來計(jì)算，得到的坐標(biāo)是非負(fù)的、光滑的。更重要的是，本文提出的最小二乘坐標(biāo)不依賴于三角剖分。

1 最小二乘坐標(biāo)

設(shè)Ω?R2是一個以v1,v2,…,vn,n≥3為頂點(diǎn)的多邊形。若對任意v∈Ω，存在函數(shù)λi:Ω→R,i=1,…,n滿足

(3)非負(fù)性：λi(v)≥0。

則稱λi(v)為定義在Ω上的廣義重心坐標(biāo)。

此外，為了保證插值的效果和實(shí)際應(yīng)用的需要，坐標(biāo)函數(shù)λi還需要具備以下性質(zhì)：

(2)線性：λi(v)在邊上是線性的；

(3)光滑性：λi(v)在Ω上平滑變化。

在以上性質(zhì)中，非負(fù)性保證插值函數(shù)可表示為原始數(shù)據(jù)的凸組合，從而避免出現(xiàn)與拖曳方向反方向的變形；拉格朗日性和線性保證插值函數(shù)有效地插值邊界；坐標(biāo)的光滑性保證了插值效果的光滑性。

1.1 模型提出

令vi,i=1,…,n為n邊多邊形的頂點(diǎn)，v為多邊形內(nèi)部任意一點(diǎn)。對所有的坐標(biāo)函數(shù)而言，最小化2-范數(shù)的和，并且該坐標(biāo)函數(shù)滿足線性重構(gòu)性、單位性、非負(fù)性：

(1)

1.2 角平分線法

為了使求得的坐標(biāo)滿足拉格朗日性和線性，首先對多邊形的頂點(diǎn)vi,i=1,…,n作一系列的線性變化，這個變換方法稱為角平分線法。

由于對式(1)中的頂點(diǎn)vi進(jìn)行了一系列的線性變換，故與式(1)等價的模型如下：

滿足：

(2)

由于模型(2)是一個帶有線性約束和不等式約束的凸優(yōu)化問題，可以使用ADMM算法去求解。

在此，引入輔助變量y和聲明變量δ(yi)：

所以，模型(2)等價于

滿足：

(3)

1.3 模型實(shí)現(xiàn)

由于模型(3)具有可分離的目標(biāo)函數(shù)和線性約束，而ADMM算法可用于處理帶有線性和不等式約束的凸問題，所以，用ADMM算法進(jìn)行求解。對于模型(3)，定義下面的增廣拉格朗日函數(shù)：

(4)

(5)

等價于

(6)

(7)

給出。

2 實(shí)驗(yàn)和分析

一般情況下，局部重心坐標(biāo)需要對區(qū)域進(jìn)行三角剖分，使得三角剖分頂點(diǎn)包括域內(nèi)部的采樣點(diǎn)以及所有的控制頂點(diǎn)。計(jì)算調(diào)和坐標(biāo)也需要對區(qū)域構(gòu)造一個密集的三角剖分。與局部重心坐標(biāo)和調(diào)和坐標(biāo)不同，本文提出的最小二乘坐標(biāo)不需要對區(qū)域進(jìn)行三角化，這使得對重心坐標(biāo)的求解更加容易。另一方面，最小二乘坐標(biāo)是非負(fù)的，保證了重心插值的凸包性。

最小二乘坐標(biāo)、均值坐標(biāo)、調(diào)和坐標(biāo)在凸、凹頂點(diǎn)坐標(biāo)函數(shù)的比較如圖1、圖2所示。從圖1、圖2可以看出：圖1凸頂點(diǎn)的均值坐標(biāo)在L型多邊形的灰色區(qū)域內(nèi)為負(fù)值，最小二乘坐標(biāo)和調(diào)和坐標(biāo)一樣，是非負(fù)且光滑的。另外，在計(jì)算時間方面，調(diào)和坐標(biāo)的運(yùn)行效率相對較快，但它需要預(yù)先進(jìn)行三角剖分，所以其結(jié)果受到不同剖分方法的影響；而最小二乘坐標(biāo)不需要進(jìn)行剖分，結(jié)果比較穩(wěn)定。

圖1 L型多邊形凸頂點(diǎn)的重心坐標(biāo)

圖2 L型多邊形凹頂點(diǎn)的重心坐標(biāo)

圖3、圖4進(jìn)一步展示了在十邊形、十三邊形上所得到的最小二乘坐標(biāo)例子。從圖中可以看出，最小二乘坐標(biāo)滿足非負(fù)性、光滑性、拉格朗日性、線性等性質(zhì)。圖5展示了在圖像變形中，通過改變多邊形的頂點(diǎn)坐標(biāo)來實(shí)現(xiàn)最小二乘坐標(biāo)變換的應(yīng)用實(shí)例。圖5中，4個黑色實(shí)心點(diǎn)為四邊形的控制頂點(diǎn)，通過改變四邊形頂點(diǎn)的位置，來實(shí)現(xiàn)花朵的變形。

圖3 十邊形中個別頂點(diǎn)的最小二乘坐標(biāo)實(shí)例

圖4 十三邊形中個別頂點(diǎn)的最小二乘坐標(biāo)實(shí)例

圖5 最小二乘坐標(biāo)的圖像變形

3 結(jié)束語