王 瑞， 肖 任， 陳俊麗， 余宗鑫， 萬旺根

1.上海大學(xué)通信與信息工程學(xué)院，上海200444

2.上海大學(xué)智慧城市研究院，上海200444

三維掃描技術(shù)的發(fā)展，使得獲取具有豐富幾何細(xì)節(jié)的數(shù)字模型成為現(xiàn)實(shí).用點(diǎn)云來表示具有復(fù)雜表面幾何的三維物體與傳統(tǒng)的三角面片表示方法相比，具有存儲(chǔ)簡(jiǎn)單、無需維護(hù)拓?fù)浣Y(jié)構(gòu)以及顯示高效等優(yōu)點(diǎn).隨著大規(guī)模采樣點(diǎn)模型在圖形學(xué)和幾何信息處理中的廣泛應(yīng)用，3D點(diǎn)云的變形方法在幾何建模、3D動(dòng)畫生成、動(dòng)態(tài)場(chǎng)景繪制及動(dòng)態(tài)模擬等方面有著獨(dú)特的優(yōu)勢(shì)及廣泛的應(yīng)用價(jià)值，是點(diǎn)云研究領(lǐng)域的一個(gè)熱點(diǎn)[1].

目前，關(guān)于三維物體變形的算法主要有自由變形法[2]、基于廣義球元(metaball)的約束變形[3]、多分辨率下的網(wǎng)格技術(shù)變形[4]、基于泊松梯度場(chǎng)的幾何變形技術(shù)[5]等.與上述方法相比，移動(dòng)最小二乘法在變形結(jié)果上呈現(xiàn)出更精確、更能保留原始信息等優(yōu)勢(shì)，尤其是三維剛性變換[6].文獻(xiàn)[7]將2D移動(dòng)最小二乘法有效地延伸到3D上，通過設(shè)置控制點(diǎn)實(shí)現(xiàn)了大量網(wǎng)格頂點(diǎn)的3D變形.文獻(xiàn)[8]基于權(quán)重定義了新的測(cè)地線度量，并根據(jù)移動(dòng)最小二乘法在使用平滑與完整的數(shù)據(jù)基礎(chǔ)上實(shí)現(xiàn)了較好的3D變形.文獻(xiàn)[9]基于3D移動(dòng)最小二乘法提出了紋理引導(dǎo)下的體變形與可視化方法.

在控制點(diǎn)不足等諸多因素的影響下，基于移動(dòng)最小二乘法的變形不流暢，甚至發(fā)生畸變，可能無法得到理想的效果.為此，本文提出了基于控制曲線的3D點(diǎn)云變形方法，用空間曲線表示3D點(diǎn)云模型的形狀拓?fù)潢P(guān)系或輪廓信息，可方便操作控制曲線變化，得到更精確且更真實(shí)的變形效果.

1 基于控制點(diǎn)的3D點(diǎn)云變形

將3D點(diǎn)云變形看成在變形函數(shù)f作用下由未變形點(diǎn)云映射到變形點(diǎn)云的過程，將f作用于未變形點(diǎn)云頂點(diǎn)，可以得到變形后的3D點(diǎn)云模型[8].設(shè)pi表示變形前的控制點(diǎn)(xi,yi,zi)，qi表示變形后控制點(diǎn)的(ˉxi,ˉyi,ˉzi).根據(jù)移動(dòng)最小二乘理論模型[10]對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行三維變形，對(duì)于空間中的任一點(diǎn)v，需要求出變形函數(shù)f(x)，使式(1)取最小值

式中，pi和qi為控制點(diǎn)坐標(biāo)向量，wi為權(quán)重，其計(jì)算公式為，α為調(diào)節(jié)變形效果的參數(shù).

權(quán)重wi的取值隨著頂點(diǎn)v在3D點(diǎn)云中取點(diǎn)位置的不同而變化.當(dāng)v取值為控制點(diǎn)si時(shí)，wi將趨向無窮大，此時(shí)定義T(pi)=qi；若控制點(diǎn)坐標(biāo)值不變，則定義f(si)=si.一般地，將變形函數(shù)設(shè)為f(v)=M x+T，其中M表示線性變換項(xiàng)，T表示平移變換項(xiàng).在式(1)取最小值的情況下可求得

圖1 基于控制點(diǎn)的3D移動(dòng)最小二乘變形Figur e 1 3D least-squares deformation of horse leg based on control points

將T代入變形函數(shù)可得

令

則式(1)等效于

從而得到了基于控制點(diǎn)集的3D點(diǎn)云移動(dòng)最小二乘法變形.矩陣M可視為仿射變換，包含了縮放、錯(cuò)切、旋轉(zhuǎn)等變換成分.通過對(duì)這些成分進(jìn)行組合分析，可以獲得仿射變換、相似變換以及剛性變換的變形函數(shù)f(v).

對(duì)于馬的3D點(diǎn)云模型，如果只有一個(gè)控制點(diǎn)，就會(huì)使整個(gè)點(diǎn)云模型產(chǎn)生平移，不能充分展現(xiàn)馬蹄提起的變形效果.本文主要研究點(diǎn)云模型的剛性變形，設(shè)置多個(gè)控制點(diǎn)(包括固定控制點(diǎn)和移動(dòng)控制點(diǎn))進(jìn)行變形.通過移動(dòng)多個(gè)控制點(diǎn)對(duì)點(diǎn)云模型變形，實(shí)現(xiàn)馬蹄抬起效果，如圖1所示.基于控制點(diǎn)的3D點(diǎn)云剛性變換變形后的效果如圖1中的(b)所示，可以看到馬蹄發(fā)生畸形，點(diǎn)云模型的真實(shí)感較差.針對(duì)基于控制點(diǎn)變形時(shí)表現(xiàn)出的弊端，本文將討論基于控制曲線集的變形.

2 基于控制曲線的3D點(diǎn)云變形

針對(duì)控制點(diǎn)變形的不足，本文提出一種基于控制曲線的3D點(diǎn)云變形算法，用曲線描述3D點(diǎn)云數(shù)據(jù)的形狀和輪廓信息，獲得了更精確的變形效果.為較好地控制曲線路徑，本文使用三次樣條曲線擬合方法生成控制曲線，即對(duì)控制點(diǎn)采用分段擬合，使擬合結(jié)果更加精確.

2.1 三次樣條曲線擬合

為了擬合點(diǎn)云數(shù)據(jù)空間的一條曲線，首先將待求的曲線投影到兩個(gè)平面，然后分別對(duì)這兩個(gè)平面進(jìn)行三次樣條插值擬合，最后將擬合好的二維曲線組合成三維曲線.下面給出理論分析.

在三維空間中，曲線有兩個(gè)方向的斜率，一個(gè)是關(guān)于x軸方向的斜率，另一個(gè)則是關(guān)于y軸方向的斜率.故設(shè)曲線表達(dá)式為

式(4)分別為該曲線在xoy和xoz平面上的投影.令Sy(x)=S(x)，設(shè)x1＜x2＜x3＜···＜xn-1＜xn共n插值節(jié)點(diǎn)，則經(jīng)過數(shù)據(jù)點(diǎn)(x1,y1),(x2,y2),···,(xn,yn)的三次樣條S(x)是一級(jí)三次多項(xiàng)式

由節(jié)點(diǎn)處的連續(xù)性可知

由節(jié)點(diǎn)處的一階與二階光滑性可知

由式(6)可得

將式(8)和(9)代入式(7)，可得

結(jié)合式(10)以及所給的邊界條件即可解出{ci}.聯(lián)立式(4)～(6)、(8)、(9)、(11)可得

根據(jù)式(12)可以得到由p點(diǎn)擬合的曲線lp(xp,yp(xp),zp(xp))，進(jìn)一步可知曲線上的點(diǎn)滿足p(x)=(x,yp(x),zp(x)).

同理可得lp(xp,yp(xp),zp(xp))和q(x)=(x,yq(x),zq(x))，易知式(2)所得到的變形函數(shù)是通過幾個(gè)離散點(diǎn)計(jì)算得來的，所得函數(shù)的準(zhǔn)確度受控制點(diǎn)數(shù)目的限制.現(xiàn)已獲得擬合好的控制曲線lp和lq，可對(duì)其進(jìn)行推廣

式(1)可推廣為

式中，xj可取(x1,xn)中的任何數(shù)，所取點(diǎn)數(shù)不受限制;k為擬合時(shí)所需要的所有點(diǎn)數(shù)，k值越大控制點(diǎn)的數(shù)目就越多，擬合效果越平滑.

2.2 基于控制曲線的3D點(diǎn)云變形

使用三次樣條曲線擬合方法對(duì)控制點(diǎn)集進(jìn)行分段擬合，生成控制曲線lp.擬合的曲線lq可精確地通過控制點(diǎn)實(shí)現(xiàn)變形，其具體步驟如下：

步驟1 設(shè)置關(guān)鍵點(diǎn)，通過三次樣條插值擬合成曲線集Lp.

步驟2 移動(dòng)Lp上的點(diǎn)，改變樣條曲線的位置和方向生成曲線集Lq.

步驟3 更改起點(diǎn)斜率u1和末端斜率un，改變Lp和Lq的邊界條件和線上的插值點(diǎn)數(shù)，擬合模型的表面輪廓和目標(biāo)形狀.

步驟4 根據(jù)曲線上Lp和Lq兩條曲線計(jì)算變形后的模型.

3 實(shí)驗(yàn)分析

根據(jù)本文提出的算法以及推導(dǎo)的變形公式對(duì)3D點(diǎn)云模型進(jìn)行控制點(diǎn)和控制曲線的變形實(shí)驗(yàn).實(shí)驗(yàn)所用微機(jī)配置如下：Intel i3處理器、內(nèi)存4 GB、顯卡GeForce 9300 GS.為改善圖1中基于控制點(diǎn)的馬腿變形效果，利用三次樣條擬合的方式生成控制曲線，以實(shí)現(xiàn)3D點(diǎn)云模型的變形.控制曲線擬合后選取5個(gè)、10個(gè)、40個(gè)插值點(diǎn)的變形效果如圖2所示，其中紅線為曲線擬合的軌跡.通過改變曲線兩端的斜率可以改變擬合曲線的彎曲度，獲得滿意的變形效果.

為了對(duì)比不同情況下的變形效果，分別對(duì)馬的模型進(jìn)行仿射變換和剛性變換，結(jié)果表明剛性變換下具備更好的變形效果.此外，圖3還對(duì)馬模型進(jìn)行了基于控制曲線集的移動(dòng)最小二乘的變形，使得馬尾巴和馬腿同時(shí)變形，表明了擬合效果較理想.

如果變形效果還不夠理想，可以通過改變曲線端點(diǎn)處的一階導(dǎo)數(shù)來實(shí)現(xiàn)調(diào)節(jié)，故在下面實(shí)驗(yàn)中令u1=

圖4所示的實(shí)驗(yàn)結(jié)果表明，通過調(diào)節(jié)u1和un可以使曲線擬合出較好的變形效果.

圖2 基于控制曲線的3D移動(dòng)最小二乘變形Figure 2 3D move least-squares deformation based on control curve

圖3 基于控制曲線集的同時(shí)變形(馬尾和馬腿)Figur e 3 Simultaneous deformation based on the control curves(horsetail and horse leg)

圖4 改變曲線兩端的一階導(dǎo)數(shù)后的變形效果Figure 4 Effect of deformation after change first derivative of the ends the curve

4 結(jié)語

以曲線的方式擬合3D點(diǎn)云模型的輪廓信息，同時(shí)結(jié)合移動(dòng)最小二乘方法提出了一種新的3D點(diǎn)云變形算法.根據(jù)點(diǎn)云數(shù)據(jù)的形狀信息或變形需要，使用三次樣條插值擬合關(guān)鍵點(diǎn)的方式生成控制曲線，結(jié)合移動(dòng)最小二乘法實(shí)現(xiàn)3D點(diǎn)云模型的剛性變形，通過輪廓擬合準(zhǔn)確定位變形后的物體輪廓，利用控制曲線可實(shí)現(xiàn)多個(gè)點(diǎn)云區(qū)域的準(zhǔn)確變形.實(shí)驗(yàn)分析驗(yàn)證了該方法的合理性與有效性.下一步工作將研究大規(guī)模點(diǎn)云數(shù)據(jù)的變形及交互技術(shù).

[1]譚光華，許秋兒，吳雙卿，張三元，張引.特征保持的大規(guī)模點(diǎn)云曲面自由變形[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2010,44(1):34-40.TAN Guanghua,XU Qiuer,WU Shuangqing,ZHANG Sanyuan,ZHANG Yin.Features preserved massive point cloud surfaces freeform[J].Journal of Zhejiang University:Engineering Science,2010,44(1):34-40.(in Chinese)

[2]SEDERBERG T W,PARRY S R.Free-form deformation of solid geometric models[C]//Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press,1986,20(4):151-160.

[3]金小剛，彭群生.基于廣義元球的一般約束變形[J].軟件學(xué)報(bào)，1998,9(9):677-682.

JIN Xiaogang,PENG Qunsheng.Generalized constraints deformed based on the general dollar ball[J].Journal of Software,1998,9(9):677-682.(in Chinese)

[4]KOBBELT L,CAMPAGNA S,VORSATZ J,SEIDEL H.Interactive multi-resolution modeling on arbitrary meshes[C]//Proceedings of SIGGRAPH,Orlando,Florida,1998:105-114.

[5]YUY,ZHOUK,XUD,SHIX,BAOH,GUOB,SHUM H.Mesh editing with Poisson-based gradient field manipulation[J].ACM Transactions on Graphics,2004,23(3):644-651.

[6]ALEXA M,COHENOR D,LEVIN D.As-rigid-aspossible shape interpolation[C]//SIGGRAPH Conference on Computer Graphics and Interactive Techniques,2000:157-164.

[7]CUNO A,ESPERANCA C,OLIVEIRA A,CAVALVANTI R.3D As-rigid-as-possible deformation using MLS[C]//Computer Graphics International Conference,2007:1-8.

[8]ZHU Y,GORLER S J.3D deformation using moving least squares[R].Harvard Computer Science Technical report:TR-10-07,Cambridge,2007:1-5.

[9]ZHAO X,LI B,WANG L,KAUFMAN A.Textureguided volumetric deformation and visualization using 3D moving least square[J].IET Compute Vision,2012,28:193-204.DOI 10.1007/s00371-011-0635-2.

[10]SCHAEFER S,MCPHAIL T,WARREN J.Image deformation using moving least squares[J].ACM Transactions on Graphics,2006,25(3):533-540.