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

1.上海大學通信與信息工程學院，上海200444

2.上海大學智慧城市研究院，上海200444

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

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

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

1 基于控制點的3D點云變形

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

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

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

圖1 基于控制點的3D移動最小二乘變形Figur e 1 3D least-squares deformation of horse leg based on control points

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

令

則式(1)等效于

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

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

2 基于控制曲線的3D點云變形

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

2.1 三次樣條曲線擬合

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

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

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

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

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

由式(6)可得

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

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

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

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

式(1)可推廣為

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

2.2 基于控制曲線的3D點云變形

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

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

步驟2 移動Lp上的點，改變樣條曲線的位置和方向生成曲線集Lq.

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

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

3 實驗分析

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

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

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

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

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

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

[1]譚光華，許秋兒，吳雙卿，張三元，張引.特征保持的大規(guī)模點云曲面自由變形[J].浙江大學學報：工學版，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].軟件學報，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.