改進貪婪投影三角化算法的激光點云快速三維重建

劉翔宇,王 健,常清法,王效蓋

(1.山東科技大學測繪與空間信息學院,山東 青島 266590;2.山東黃金礦業(萊州)有限公司焦家金礦,山東 煙臺 261441)

1 引 言

三維重建技術在逆向工程、數據可視化、計算機視覺、醫療技術等領域得到了廣泛的應用[1]。該技術發展至今,已經取得了一定的研究成果。根據點云三維重建的方式不同,將三維重建技術分為[2]:參數曲面重建、隱式曲面重建[3]和網格曲面重建。基于參數曲面重建的方法主要包括B樣條曲面重建[4]和NURBS曲面重建[5],因為該類方法在進行重建時需要對點云數據進行參數化,而散亂點云數據的參數化效果非常差,所以在對該類數據進行重建時就會造成重構出的模型存在孔洞問題,因此該類方法只適用于表面光滑、變化較小的物體重建。張丹丹等人在傳統的NURBS曲面重建基礎上提出一種基于點云的整體參數曲面重構方法,該算法采用八叉樹建立點云間拓撲關系,然后基于法矢和曲率進行點云精簡,該方法提高了整體重建效率并且重建效果較好,但是對于數量較少的點云重建效果不佳[6]。隱式曲面重建的方法主要有泊松算法[7]和移動立方體算法[8],該類算法可以很好的將結構簡單的物體擬合成光滑的曲面,但是對于外表結構復雜的物體不能達到理想的重建效果,并且該類算法在進行重建時耗時較長。劉濤等人提出一種基于點云增強優化的泊松重建算法,該算法首先對點云進行降噪處理,然后使用雙三次樣條插值擬合曲面,該方法有效的減少了模型孔洞的生成,但是在耗時上有所增加[9]。網格曲面重建在點云三維重建中應用最為廣泛,經常用于重建具有復雜結構的物體,貪婪投影三角化算法[10](以下簡稱貪婪投影算法)是網格曲面重建算法的主要代表算法之一,它是基于三維Delaunay三角形的曲面重建方法,貪婪投影算法能夠很好的重建出具有復雜拓撲結構的物體,但存在耗時長且對大量點云數據進行重建時模型會出現孔洞的問題。

針對貪婪投影算法的缺點,許多科研工作者做了一些相應的研究。李學兵等人提出一種廣度優先搜索算法來調整點云法向量方向,并在此基礎上對點云進行重建,該方法得出的模型效果要高于傳統貪婪投影算法,但在耗時上有所增加[11]。楊玉澤等提出一種基于KD樹紋理映射的貪婪投影算法的點云重建方法,該方法重建出的模型在細節表達上效果較好,但存在點云缺失與孔洞的問題[12]。張津銘等人提出使用移動最小二乘算法對點云數據進行平滑處理,該方法雖然可以去除噪聲點的干擾,但也丟失了物體一部分細節特征,導致重建后的模型出現了孔洞[13]。

針對以上問題,本文提出一種改進的貪婪投影算法,期望解決重建后的物體表面粗糙和孔洞問題,并且減少物體重建的時間,提高重建的效率。

2 貪婪投影算法

貪婪投影算法的基本思想是:首先計算輸入點云的法向量并在計算完成后投影到某一平面上,然后對投影后的點云作平面內的三角化,從而得到各個點的連接關系。該三角化的過程是基于生長法的曲面重建,該方法通過選取一個樣本三角片作為初始曲面,通過對該曲面邊界進行延伸,直到形成一張完整的三角網格曲面后結束,然后通過某一平面上的投影點云的連接關系,并以此為基礎形成原始點云間的拓撲連接,最后得到重建后的曲面模型。但是貪婪投影算法在進行重建的過程中,如果遇到的點云存在表面不夠光滑、密度不均勻的情況,使用該算法得到的重建模型達不到預期效果。貪婪投影算法流程:

1)針對輸入點云中的任一點q,采用KD樹的近鄰域搜索算法確定其含有k個近鄰點的鄰域。根據搜索的結果,點云會根據其狀態分為自由點、完成點、邊緣點及邊界點。

2)確定任一點q及其k個鄰域點的投影切平面,并將這k個鄰域點投影到該二維平面中。

①針對第一步中輸入的任一點q的鄰域,此鄰域內的點與過q點的切平面投影存在一一對應的關系。根據貪婪投影算法的PCA(Principal Component Analysis)法線估計方式計算每一點的近似法向量,通過平面方程式來解算出該點的切平面。假設點N0(x0,y0,z0)的法向量m=(A,B,C),點N(x,y,z)過N0的切平面可以表示為:

A(x-x0)+B(y-y0)+C(z-z0)=0

(1)

②為了將空間中的點投影到二維切平面∏中,一般采用投影矩陣的方法,通過平移和旋轉等一系列操作得到三維點在切平面上的投影(如圖1所示)。投影矩陣ΤM∏的公式如下:

圖1 三維k鄰近點的局部投影圖Fig.1 Local projection of three dimensional k-nearest points

ΤM∏=Tc·Rx·Ry

(2)

其中,Tc為平移變換矩陣:

Rx為圍繞x軸旋轉α度:

Ry為圍繞y軸旋轉θ度:

通過式(1)和式(2)可以求出任一點q(xi,yi,zi)在其切平面∏上的投影:

(3)

3)對該二維平面上的點使用貪婪投影算法進行三角剖分,并且每次都選擇局部最優點作為擴展點,再通過投影關系,將其擴展的點映射回空間,不斷重復這一過程,最終完成物體的表面重構。

步驟一:在點云數據中選擇任一點qi作為初始生長點,使用KD樹算法搜索其近鄰點,在其鄰域內找到距離qi最近的點qj并使用直線進行連接,得到線段qiqj,并將其作為三角形的一條生長邊。

步驟二:計算距離邊qiqj最近的點qk,然后構造出第一個三角形Δqiqjqk。如圖2(a)所示。

圖2 貪婪投影三角化流程圖Fig.2 Greedy projection triangulation process

步驟三:在步驟二的基礎上,繼續尋找距離三角形Δqiqjqk任一邊最近的點,構成新的三角形。如圖2(c)所示。

步驟四:重復步驟三,直到所有點被選擇完畢并構建出完整的拓撲結構,則算法結束。如圖2(d)所示。

該算法的原理并不復雜,但是在實現過程中存在一些問題:①使用KD樹鄰域搜索算法需要耗費大量的時間進行回溯,延長了重建的時間;②當需要重建的物體表面點云密度不均勻時,使用該算法會產生錯誤的拓撲結構,從而導致重建效果不理想;③當重建物體表面過于復雜時,該算法難以確定投影點與三維空間中的點對應的位置關系,所以會丟失一部分物體信息,造成曲面重疊并使重構后的模型出現孔洞。

3 改進的貪婪投影算法

3.1 體像素(Voxel Grid)網格濾波

體像素網格濾波的基本原理是:根據輸入的點云數據建立三維體素柵格,三維體素柵格是一種微小的空間三維立方體的集合,通過設定采樣距離的參數大小,可以將這些三維立方體等距劃分為a·b·c個立方體,并將輸入的點云數據劃分到立方體中,將這些包含點云的立方體看成是子包圍盒,剔除掉主體之外的所有立方體,最后計算這些主體中所有點的重心,并使用該重心近似代替這些點。該方法在思想上簡單并且易于實現,對于散亂無序的點云不需要再次建立點云間的拓撲關系,減少了計算量,加快了算法的重建速度。

3.2 八叉樹優化

八叉樹最初由Hunter博士提出,該方法被廣泛用來表示三維空間,是四叉樹在空間范圍內的推廣[14]。八叉樹在對點云進行管理時所采取的思想是:八叉樹根據全部點云的最小外接包圍盒建立根節點。然后根據等分原理將外接包圍盒等分為8個小立方體,也就是子節點。在對點云進行歸類的過程中,根據位置關系將其劃分到對應的子節點中。至此,三維點云數據已經按照各自特性剖分完畢。八叉樹算法在搜索大規模點云時,效率要高于KD樹,并且自動化程度較高,可以對點云三維重建的時間進行優化。圖3為八叉樹的結構示意圖。

圖3 八叉樹結構圖Fig.3 Octree structure diagram

3.3 移動最小二乘算法(Moving Least Squares,MLS)基本原理

3.3.1 擬合函數的建立

在擬合區域的局部子域上,擬合函數f(x)表示為:

=pT(x)a(x)f(x)

(4)

其中,a(x)=[a1(x),a2(x),…,am(x)]T為待求系數;p(x)=[p1(x),p2(x),…,pm(x)]T為基函數；它是一個k階完全多項式；m是基函數的項數。對于一維問題,它的基函數為p(x)=[1,x,x2,…,xm]T,對于二維問題,線性基為p(x)=[1,x,y]T,m=6,二次基通常為[1,x,y,x2,y2,xy]T,m=6,為了盡可能獲得更精確的局部逼近,有必要將f(xi)與節點值yi的局部逼近之差的平方權值最小化。因此,離散加權范式為:

(5)

其中,n是影響區域的節點數;f(x)是擬合函數;w(x-xi)是節點xi的權函數。為了確定系數a(x),式(2)中pT(xi)a(x)-yi應取極小值,從而得:

a=(BWBT)-1BWy

(6)

通過式(6)可以計算出式(4)中的各項系數,將未知點代入式(4)中,就能求得該未知點的擬合函數值。

3.3.2 確定權函數

權函數作為移動最小二乘法中最重要的部分,權函數w(x-xi)在移動最小二乘法中具有緊支性,即權函數在x的子域內不為0,這個子域外全是0,這個子域為x的影響域(即權函數的支持域),其半徑記為Smax。選擇權函數時應遵循以下原則:

①權值函數的緊支決定了各節點在支持域中的權值大于0,在支撐區域外或邊界處的權值等于0。

②必須有單位分解。

③權函數要光滑連續,可以推導出函數。

④在支撐域中,隨著‖x-xi‖的增加,權值減小。

(ⅰ)點云平滑處理

常用的權函數是三次樣條權函數,其表達式為:

(7)

(ⅱ)點云重采樣

在空間點云數據重采樣中,重采樣點的位置會相對于起始采樣點發生變化,因此權因子w(x-xi)也應隨著待求點位置的變化而變化,針對這種情況,本文使用如下權函數:

(8)

式中,di(x)表示第i個原始采樣點pi與重采樣點p之間的距離；u表示影響區域中的特征與重采樣間的影響因子。

通過式(8)權函數對式(6)進行計算,求得該擬合函數的系數矩陣。

α(x)=(BW(x)BT)-1BW(x)y

(9)

式中,W(x)為高斯權函數的對角矩陣。

3.4 基于改進的貪婪投影三角化的重建流程

傳統的貪婪投影算法在估計法向量時采用的是PCA算法,該算法在估計法向量時的正確率不高,造成重建時出現錯誤的拓撲結構；在處理大規模點云時,KD樹的搜索效率要低于八叉樹。因此本文的改進算法采用基于MLS法向量估計算法來進行法向量計算并進行重建,并且使用八叉樹來代替KD樹進行近鄰域搜索(如圖4所示)。具體的步驟流程如下:

圖4 本文算法流程Fig.4 The Algorithm Flow of This Paper

步驟一:對原始點云采用體像素網格濾波算法進行下采樣,實現點云的簡化并保持密度均勻。

步驟二:針對步驟一中得到的點云表面粗糙,傳統貪婪投影算法不能很好地進行平滑處理,所以采用MLS算法對點云進行平滑及重采樣處理,得到表面更加平滑的點云數據。

步驟三:對步驟二生成的點云,采用基于MLS算法的點云法線估計的貪婪投影算法對點云進行重建,并且使用八叉樹來代替KD樹進行近鄰域搜索,最終得到效果較好的曲面模型。

4 實驗驗證與精度分析

為了驗證本文算法的有效性和可行性,在本次實驗中,實驗平臺的軟件開發工具為Windows10操作系統、vs2019、pcl1.11.0,以及處理點云所需的CMAKE、VTK、boost庫等。實驗數據選用兩種數據源:分別為斯坦福大學的標準數據集horse和通過Trimble TX8三維激光掃描儀獲取的雕塑數據。如圖5所示。

圖5 實驗數據Fig.5 Experimental Data

為了體現出改進算法的性能,對比了泊松算法、傳統貪婪投影算法和本文算法的重建時間和不同點云數據預處理前后的點云數量變化,如表1和表2所示。從表1可以看出泊松算法的重建時間要長于傳統貪婪投影算法和改進算法,由于泊松算法需要使用移動立方體算法原理來提取等值面,所以耗時更長。本文算法的重建時間比傳統貪婪投影算法減少了約30 %、比泊松算法減少了約45 %,效率提升明顯。

表1 三種算法耗時對比Tab.1 Time consuming comparison of three algorithms

表2 點云預處理前后的數量變化Tab.2 Comparison of the number of point clouds before and after pretreatment

圖6為預處理后的horse數據和雕塑數據分別進行傳統貪婪投影算法的法線估計和MLS算法的法線估計,由于傳統貪婪投影算法與泊松算法的法線估計方法一致,故不加入對比。分析圖6(a)和圖6(b)與圖6(c)和圖6(d)可以發現,在模型的邊緣、角點、horse數據的腿部和雕塑數據的手臂處,傳統貪婪投影算法的法線方向估計一致性較差,MLS算法在這幾處地方的法線估計一致性要優于傳統算法,所以使用MLS算法進行法線估計可以為后期的重建提供一個更加準確的法線輸入,提高重建的精度。

圖6 法線估計可視化Fig.6 Visualization of normal estimation

將兩組點云數據分別應用泊松算法、傳統貪婪投影算法和本文算法進行重建效果比對。重建結果如圖7、8所示。從圖7(a)和圖8(a)可以看出,泊松重建無論是在細節處,還是在模型的完整度上,都不如貪婪投影算法的重建效果好,并且在雕塑數據重建時出現了偽平面,這是由于泊松算法適用于具有封閉性的點云。分析圖7、圖8中的(b)、(c),對于標準horse數據,由于其整體結構簡單,重建的效果差異不大；對于雕塑數據,由于其結構復雜,對點云進行體像素網格濾波重建后,效果要明顯好于直接使用貪婪投影算法進行重建,這是因為原始點云中包含許多冗余點,在進行法線估計時會產生錯誤的結果,從而導致孔洞的產生。分析圖7、圖8中的(c)、(d)可以看出,經過體像素網格濾波和MLS算法的平滑與重采樣后,標準horse數據和雕塑數據生成的模型均在細節處表達出了更好的效果。最后使用本文改進的算法和傳統貪婪投影算法進行重建,對比圖7、圖8的(a)、(e)可以看出,在horse數據的頭部和腿部處保證了細節不丟失,并且孔洞有所減少；雕塑數據在保證手臂和大腿處的衣服褶皺不丟失的基礎上,提高了模型整體的平滑效果,并且有效的減少了孔洞的產生,而且在面部和衣服等位置處保持了較高的網格細節。通過以上分析可以得出本文改進的算法重建出的模型孔洞少、表面更加光滑、細節表達效果也較好。

圖7 Horse重建效果Fig.7 The effect of horse reconstruction

圖8 雕塑重建效果Fig.8 The effect of sculpture reconstruction

采用4個定量分析精度評價指標,即利用Geomagic Studio軟件計算點云到模型實體的最大偏差距離、平均偏差距離、標準差和均方根誤差,并且使用該軟件顯示三種算法生成模型面片的數量,以此對三種算法生成模型的重建結果進行精度評價。如表3、表4和表5所示。由于horse數據結構較為簡單,三種算法重建精度差異不大,在三角面片生成數量上,本文算法也要少于其他兩種算法。對于采集的雕塑數據,由于其結構復雜,本文算法在精度上相比于泊松算法要提升了1.13 mm,相較于傳統貪婪投影算法提升了0.53 mm,在生成三角面片的數量上本文算法也要優于泊松算法和傳統貪婪投影算法,通過分析可以得出本文算法滿足大多數領域中建模的精度要求。

表3 Horse模型重建精度分析Tab.3 Accuracy analysis of horse model reconstruction

表4 雕塑模型重建精度分析Tab.4 Accuracy analysis of sculpture model reconstruction

表5 重建模型面片數量Tab.5 Number of reconstruction model patches

5 結 語

針對目前的點云三維重建的貪婪投影算法存在的重建耗時長,重構的模型存在表面粗糙、孔洞等問題,提出首先采用體像素網格濾波對點云進行下采樣,然后采用移動最小二乘算法來對點云進行平滑及重采樣,并且使用八叉樹代替KD樹進行近鄰域搜索,最后使用基于移動最小二乘算法的點云法線估計的貪婪投影算法對點云進行重建,在保證重建效果的前提下,減少了重建的時間。通過實驗驗證,本文算法相較于泊松算法和傳統的貪婪投影算法,耗時短,在模型表面的光滑度和孔洞修復上顯示了更好的重建效果。但從實驗結果可以看出,雖然改進算法對孔洞修復有了一定的改善,但還存在一些細小的孔洞,未能達到孔洞的完全修復,因此針對三維重建中孔洞完全修復有待進一步深入研究。