李耀輝，武志峰，宣兆成

（天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院，天津300222）

基于二次曲面的點云數(shù)據(jù)三維重構(gòu)

李耀輝，武志峰，宣兆成

（天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院，天津300222）

針對傳統(tǒng)三維重構(gòu)依賴三角網(wǎng)格且難于有效分割含缺陷的點云數(shù)據(jù)的問題，將點云數(shù)據(jù)的三維重構(gòu)轉(zhuǎn)化為曲面片的光滑拼接問題。本文定義一個二次曲面片的模板方程并采用待定系數(shù)法構(gòu)造曲面片，利用結(jié)式方法實現(xiàn)不同曲面片的光滑拼接使三維造型光滑逼真。為了克服二次曲面不易作圖的缺點，討論了采用一次平面方程近似處理的方法。該方法可得到曲面片以及拼接曲面的解析表達(dá)式，具體重構(gòu)時直接代入點云數(shù)據(jù)即可得到相應(yīng)的方程，具有高效實用的特點。

三維重構(gòu)；點云數(shù)據(jù)；曲面拼接；結(jié)式

三維掃描實現(xiàn)了三維物體的數(shù)字化，但獲取三維點云數(shù)據(jù)后，如何實現(xiàn)高效逼真的三維重構(gòu)是人們研究的問題之一［1-3］。很多學(xué)者提出了不同方法。一般方法是采用Delaunay三角剖分方法，根據(jù)點云數(shù)據(jù)對三維物體進行重構(gòu)。該方法的最大優(yōu)點是簡單，且只要三角形足夠小就可達(dá)到要求的精度。文獻(xiàn)［4］提出采用possion方程重構(gòu)三維造型的方法，但該方法涉及指數(shù)函數(shù)的計算，因此復(fù)雜度較高。另外傳統(tǒng)點云分割方法往往依賴點云的三角網(wǎng)格，很難有效分割含缺陷的點云，需借助復(fù)雜的數(shù)據(jù)結(jié)構(gòu)或算法［5］。因此，人們對于點云數(shù)據(jù)的處理提出了各種不同的方法［6-7］。隨著計算機性能的提高，人們不再局限于使用一次函數(shù)擬合或分段擬合實現(xiàn)三維造型。目前，人們在計算機輔助設(shè)計中可使用不高于10次的多項式函數(shù)來表示幾何造型或三維重構(gòu)中物體的數(shù)學(xué)模型。從選擇曲面片的角度考慮，曲面的次數(shù)越高，其拐點可能越多，也可能產(chǎn)生奇異點。為此，將符號消元的結(jié)式方法用于點云數(shù)據(jù)的三維重構(gòu)［8］，提出采用二次函數(shù)結(jié)合曲面拼接的方法實現(xiàn)三維重構(gòu)。重構(gòu)過程中，所有曲面片均采用正則曲面片去重構(gòu)物體的幾何造型。若實際的幾何造型存在奇異點，則將造型中的曲面片進行分解直至正則為止。然后，用二次曲面去重構(gòu)幾何物體。該方法通過選擇n個點云數(shù)據(jù)并擬合成曲面片，當(dāng)多個曲面片能夠相互覆蓋不產(chǎn)生孔洞時即可構(gòu)成三維重構(gòu)的曲面。同時，由于點云數(shù)據(jù)中相互關(guān)聯(lián)點之間的歐氏距離比較小，因此精度可滿足三維曲面重構(gòu)的要求。

1　曲面片的構(gòu)造

1.1擬合點組的選擇

如前所述，通過接觸式或非接觸式方法可以很容易得到物體的三維點點云數(shù)據(jù)，點云數(shù)據(jù)及三維重構(gòu)如圖1所示。圖1（a）為奶牛模型的點云數(shù)據(jù)，整個點云由2 903個點構(gòu)成。采用Delaunay三角形網(wǎng)格對點云數(shù)據(jù)重構(gòu)得到的結(jié)果如圖1（b）所示，該圖由5 804個三角形網(wǎng)格構(gòu)成。在本文中，為實現(xiàn)物體二次曲面片的三維重構(gòu)，首先確定一個點，然后以此點為左上點并搜尋與其相鄰的其他3個點，這樣4個點構(gòu)成一組。最直接的方法是將所有點云數(shù)據(jù)按某一坐標(biāo)從小到大排列，然后4個點為一組，分別將各點的坐標(biāo)值代入模板方程得到含有4個線性方程的方程組。計算出方程各個系數(shù)的值，得到一個次數(shù)為2的曲面片方程，最后得到797個曲面片。之后，從4個點中分別選取三維坐標(biāo)的最小值和最大值畫圖，由此得到的奶牛造型如圖1（c）所示。撇開造型的完整性，該造型需要的曲面片更少。另外，每個面片是二次曲面，通過二次曲面在不增加面片個數(shù)的情況下可以減小誤差，提高造型的光順程度。但該方法得到的點組太少，不能構(gòu)造出連續(xù)的曲面。

圖1　奶牛的點云數(shù)據(jù)及三維重構(gòu)

該造型中所有曲面片沒有連接起來構(gòu)成一個完整的造型，因此并不理想。最直接的想法是計算出二次曲面后直接增大曲面片的覆蓋范圍，這樣會增大擬合的誤差，從而使造型不光滑。因此，如何在保證光滑程度的情況下將斷續(xù)的曲面片連接起來得到理想結(jié)果是算法研究的關(guān)鍵。

1.2曲面片構(gòu)造的具體方法

利用所有的點云數(shù)據(jù)擬合出一個多項式方程描述物體的三維造型方法雖然直觀，但不現(xiàn)實。主要原因是點云的數(shù)據(jù)量通常很多，從幾千到幾萬甚至幾十萬個，這樣擬合出的多項式的次數(shù)很高，且計算復(fù)雜。為此，利用點云數(shù)據(jù)中的少量數(shù)據(jù)擬合曲面片，將曲面片拼接起來構(gòu)造物體的三維造型。

考慮二次曲面的一般形式為f（x，y，z）=ax2+by2+ cz2+dxy+exz+fyz+gx+hy+iz+j。該方程有10個系數(shù)，可以選擇點云中的10個點確定一個二次曲面。如果一個曲面片中盡可能包含多個點，作圖時可以采用更少的曲面片，從而增加擬合的速度和作圖的效率。然而，直接采用該形式且將10個點分為一組代入方程，用待定系數(shù)法求解，會遇到許多問題。第一，得到的線性方程組可能會無解。從造型的角度考慮點云數(shù)據(jù)具有很強的關(guān)聯(lián)性，但是從數(shù)據(jù)本身考慮，則具有很大的隨機性，選擇的點不在一個二次曲面上。如果代入f（x，y，z）之后并求解，所求的各項系數(shù)均為0，即方程只存在零解。但是，此結(jié)果對于擬合曲面片無意義。第二，二次曲面包括雙曲面、橢球面、拋物面等不同的類型。特別是當(dāng)擬合出雙曲面時，雖然曲面由一個方程表示，但擬合時采用的點可能出現(xiàn)在2個分支上。此時，這樣的面片重構(gòu)出來的幾何物體也是不連續(xù)的。另外，考慮采用球面片而沒有采用拋物面等其他二次曲面，是因為球面片各個方向同性。如果采用拋物面，當(dāng)擬合曲面的軸線與坐標(biāo)軸不平行時需要考慮旋轉(zhuǎn)等問題。這樣會導(dǎo)致曲面片的方程復(fù)雜，降低算法的效率。第三，擬合結(jié)果可能會分解為2個一次函數(shù)。從點云中選擇點的位置具有一般性，在有些情況下得到的二次函數(shù)能夠進行因式分解，從而生成2個一次因式。特殊情況下，9個點的擬合結(jié)果如圖2所示，圖中的9個點擬合出的曲面分解為交叉的2個平面。

圖2　特殊情況下9個點的擬合結(jié)果

為此，考慮二次曲面特性的一致性且保證在任何情況下待定系數(shù)法非零解的存在，采用球面片作為所要擬合的曲面，選擇二次方程T=a1（x2+y2+z2）+a2x+ a3y+a4z+a5作為模板。T中有5個參數(shù)，擬合二次曲面時采用待定系數(shù)法確定參數(shù)ai（1≤i≤5）的值。通過這5個參數(shù)可以確定曲面片的球心坐標(biāo)、半徑等。重構(gòu)時，不同位置可以用不同的球面片表示。具體擬合時，將點云的每4個點做為一組。這樣，將4個點的坐標(biāo)值代入模板方程后，生成由4個方程構(gòu)成的關(guān)于ai的線性方程組。由于方程組有5個未知數(shù)，因此方程組的解表示為其中一個系數(shù)ai的解析式。

造型時需要得到具體的數(shù)值解，因此對解析解中保留的ai進行歸一化處理得到所表示的曲面片。計算曲面片時，之所以選用4個點而沒有選擇5個點，主要是保證每次計算時能夠計算出方程的解，可以得到曲面片。另外，選擇4個點可以保證得到的是球心位置和半徑不同的球面片，從而保證各個球面片連接的連續(xù)性。

2　造型中曲面片的光滑拼接

幾何造型是由二次曲面片組成，奶牛蹄部的2個曲面片的連接效果如圖3所示。從圖3中可以看出，每個曲面片各有4個點擬合而成且它們擁有共同的2個點。采用三角網(wǎng)格進行拼接，構(gòu)造出的三角形中至少有1條公共邊即可。當(dāng)采用二次曲面時，2個曲面片在邊界處的效果如圖3中的中間造型所示，它們并沒有光滑地連接在一起。因此，這些曲面片在邊界處的拼接是接下來要處理的問題。

圖3　幾何造型中部分曲面放大后的效果

只有2個在邊界處連接的曲面才需要光滑拼接，因此需要判斷2個曲面拼接的必要性。從圖3可知，2個曲面中至少有2個交點，每1個曲面由4個點擬合而成。設(shè)Pi為擬合曲面Si的點集，當(dāng)#（Si∨Sj）=6時才需要進行拼接，其中#（）表示集合中的元素數(shù)。

為提高拼接的效率且降低拼接的復(fù)雜度，實現(xiàn)拼接有幾種方法。實際造型中有多種曲面片連接的情況，如圖4所示。

如果一個曲面片連接4個曲面片，則在拼接時將中間曲面轉(zhuǎn)換為過渡曲面且過渡曲面在邊界處過渡為其余4個曲面的方程。更多情況類似于圖4（a）點1~4擬合出第1個曲面片，點3~6擬合出第2個曲面，點5~8擬合出第3個曲面片，這些曲面之間的連接，被稱為級聯(lián)式連接。在級聯(lián)式拼接中將中間固定，即在第一節(jié)得到的曲面方程不變，通過選擇合適的參數(shù)使連接它的曲面稍微改變，便可保證邊界處實現(xiàn)光滑拼接。具體方法是：對于第1、2個曲面片，點3和點4是它們共有的點，因此認(rèn)為整個曲面從點1和點2生成的邊界沿著與邊界垂直的方向逐漸過渡，當(dāng)?shù)竭_(dá)點3和點4生成的邊界時變成曲面片2。這樣，將2個曲面片的方程做為主曲面方程s1和s2。計算拼接曲面時，為了實現(xiàn)較好的光照效果，選擇的輔助曲面應(yīng)是拼接處曲面的法向方向。然而，因為點1和點2生成的邊界方向的垂直方向難于計算，且精確計算會增大計算量。因此，采用近似的方法確定法向分量。

比較從點1到點3或點2到點4變化過程中，判斷坐標(biāo)x、y、z中哪一個分量變化最大。為盡可能準(zhǔn)確地確定拼接的方向，計算曲面s1的中心坐標(biāo)，即

圖4　多個曲面的光滑拼接

其中：u分別取x、y、z。然后，計算s2的中心坐標(biāo)v2u并得到每個坐標(biāo)方向的差值vs=|v2u－v1u|。最后，確定連接方向u為vs值最大的方向。進一步選擇該分量構(gòu)造輔助曲面h1=u-v1u和h2=u-v2u。這樣，可以構(gòu)造一組方程

通過式（1）可以看到，在輔助曲面h1時對應(yīng)主曲面s1，當(dāng)輔助曲面過渡到h2時主曲面也到達(dá)s2。輔助曲面僅表示位置關(guān)系，即在u取最小值時主曲面取s1，u取最大值時主曲面取s2。然后，利用結(jié)式消元法計算過渡曲面，計算完畢后得到過渡曲面bs，用bs代替曲面1實現(xiàn)曲面片的光滑拼接，最后的拼接效果如圖4（b）所示。

但由此引起的問題是，原來擬合出的曲面通過點云中所規(guī)定的點，新生成的曲面片是否能滿足精度要求。通過u1、v1計算得到的過渡曲面為因為bs在初始位置即輔助曲面取h1時，bs與h1相交得到的曲線和s1與h1的相交曲線的方程相同，因此必通過點1和點2。當(dāng)曲面過渡到點3和點4時，曲面方程過渡為s2。因為點3和點4是曲面1和2的公共點，所以過渡曲面bs也一定通過點3和點4。因為通過點1~4的二次曲面不止一個，該方法可以理解為在已知的一個曲面上計算得到與另外一個曲面片在指定位置光滑拼接的另一個曲面片。另外，因h和s分別是一次和二次多項式，由此可知deg（bs）≤4。因此，可采用不高于4次的多項式方程實現(xiàn)所有曲面片的G1階光滑拼接。利用光滑拼接法得到的不同點云數(shù)據(jù)的幾何造型如圖5所示。

圖5　采用曲面拼接的三維重構(gòu)

3　曲面片大小的調(diào)整

由三角網(wǎng)格變?yōu)槎坞[式曲面，并不僅僅是選取4個點并利用待定系數(shù)法得到二次曲面的問題。為保證造型的光滑性，研究希望點云數(shù)據(jù)得到曲面片的邊界如圖3虛線框內(nèi)的二次曲面。由于作圖時取值范圍的限制從而出現(xiàn)多余部分和缺失部分。因此，在作圖時采用近似二次球面的方法。

具體實現(xiàn)時，用多個三角形面片代替二次曲面，三角面片的個數(shù)根據(jù)作圖時的精度確定。最基本的精度是每個二次曲面由4個三角面片逼近。由前面的描述可知，每個面片由4個點構(gòu)成且中心坐標(biāo)為v1u，但該點不一定在球面上。將這4個點用直線連接構(gòu)成的圖形是凸的且中心必在其內(nèi)。因此，中心點在球面片上有一對應(yīng)的實數(shù)點，將中心坐標(biāo)的任意2個代入球面方程T就可計算出另外一個坐標(biāo)的值，即得到球面片的相應(yīng)點v′。

在實際計算中會遇到3個問題：①法線的內(nèi)外問題。因為球面方程的次數(shù)為2，所以中心點映射到球面上有2個點。但是，在實際造型中選擇哪一個點要利用點云的性質(zhì)確定，即點云之間的距離不大，中心點距球面上映射點的距離就不會很大。在造型時，選擇球面上距離中心點v′較近的點構(gòu)造三角面片。②浮點數(shù)計算問題。點云坐標(biāo)都帶有小數(shù)位，其精度達(dá)到10-6甚至更高，在計算過程中會帶來浮點數(shù)的計算問題，即中心點對應(yīng)球面片上的點是實際存在的。理論上，將球面包括范圍內(nèi)任意點的x、y、z坐標(biāo)中的2個代入球面方程計算出的第3個值應(yīng)是一個實數(shù)解。但由于浮點計算問題得到的許多解是復(fù)數(shù)，從而給作圖帶來了困難。為此，當(dāng)?shù)玫綇?fù)數(shù)解時僅取其實數(shù)部分。這樣計算得到的點將不會在球面上。經(jīng)實際作圖和計算，當(dāng)點云中相鄰2點各個方向上的坐標(biāo)差為10-2時，僅取復(fù)數(shù)實部代入方程后的誤差為10-3，精度可以滿足要求。③作圖的精度問題。用三角形面片代替球面片實質(zhì)是用一次方程代替二次方程。為了提高作圖的精度，必須采用盡可能多的三角面片逼近球面片，三角形的個數(shù)需根據(jù)作圖時的精度確定，最基本精度是v′與4個點構(gòu)成4個三角面片。當(dāng)精度要求更高時，可由點云相鄰2點的中點計算出其映射到的球面上點。這樣，可以用8個三角形面片來代替球面片。類似地，還可以繼續(xù)提高精度來逼近球面片。采用該方法得到的實際幾何造型如圖6所示。從圖6中可以看出，奶牛的造型腹部后半部分是鼓起來的。

圖6　曲面調(diào)整后的結(jié)果

4　結(jié)束語

為實現(xiàn)點云數(shù)據(jù)曲面片的重構(gòu)，將4個點云數(shù)據(jù)分成一組。一組數(shù)據(jù)的部分?jǐn)?shù)據(jù)可能存在于不同曲面片中，因此點云數(shù)據(jù)可能重用，但是次數(shù)不能超過4次以上。將數(shù)據(jù)代入二次方程并利用待定系數(shù)法求解出二次方程的系數(shù)。此時，得到的曲面片僅能夠?qū)崿F(xiàn)G0階拼接。為了實現(xiàn)不同曲面片之間的G1階光滑拼接，通過結(jié)式消元法得到2個曲面片中一個面片的近似曲面。該近似曲面仍通過原曲面求解時的4個點云數(shù)據(jù)的坐標(biāo)。實例表明，該方法較好地實現(xiàn)了真實物體的幾何造型。另外，符號計算中的所有結(jié)果都是離線完成得到的解析解，具體計算時只需將點云數(shù)據(jù)代入公式便可直接得到結(jié)果，既可滿足精度要求又具有較高的效率。

［1］莫堃.基于隱式函數(shù)的曲面重構(gòu)方法及其應(yīng)用［D］.武漢：華中科技大學(xué)，2010.

［2］NIELSON G，HAGEN H，LEE K.Implicit fitting of point cloud data using radial hermite basis functions［J］.Computing，2007，79（2）：301-307.

［3］YOO D.Rapid surface reconstruction from a point cloud using the least-squares projection［J］.International Journal of Precision Engineering and Manufacturing，2010，11（2）：273-283.

［4］武敬民.三維點云處理及隱式曲面三維重構(gòu)技術(shù)的研究與實現(xiàn)［D］.太原：中北大學(xué)，2014.

［5］鄒萬紅.大規(guī)模點云模型幾何造型技術(shù)研究［D］.杭州：浙江大學(xué)，2007.

［6］EMELYANBOV A，SKALA V.Surface Reconstruction From Problem Point Clouds［P］.Graphicon，2006：239-247.

［7］MOENNING C，DODGSON N.Intrinsic Point Cloud Simplification［P］.Graphicon，2006：110-125.

［8］李耀輝，武志峰，宣兆成.基于結(jié)式的曲面拼接與三維造型［J］.計算機應(yīng)用，2015，35（10）：2950-2955.

Three dimensional reconstruction of point cloud data based on quadratic surface

LI Yao-hui，WU Zhi-feng，XUAN Zhao-cheng
（SchoolofInformationTechnologyandEngineering，TianjinUniversityofTechnologyandEducation，Tianjin300222，China）

As to the problem that traditional 3D reconstruction relies on triangular mesh and it is difficult to effectively segment the point cloud data with defects，the 3D reconstruction of point cloud data is transformed to the smooth blending of curved surface.A quadratic surface patches template equation is defined and the undetermined coefficient method is used to construct the surface，the resultant method is used to realize smooth connection of different patches，which can make 3D modeling smooth and realistic，and overcome the problem that it is not easy to draw the quadratic surface.The ways how to use a plane equation approximation method are discussed.The method can analyze surface and blending expressions，and the specific reconstruction for the point cloud data can be obtained by corresponding equations.The method has high efficient and practical features.

3D reconstruction；point cloud data；surface blending；resultant

TP391.41

A

2095－0926（2015）04－0005－05

2015-10-17

天津市科技支撐計劃項目（14ZLZLZF00031）；天津職業(yè)技術(shù)師范大學(xué)科研發(fā)展基金項目（KJY12-09）；天津職業(yè)技術(shù)師范大學(xué)留學(xué)回國基金項目（RC14-50）.

李耀輝（1968—），男，教授，博士，碩士生導(dǎo)師，研究方向為算法設(shè)計及優(yōu)化、符號計算等.