三維點云自適應(yīng)稀疏優(yōu)化重構(gòu)

馮肖維，胡海云，莊睿卿，何 敏

（上海海事大學(xué) 電氣自動化系，上海201306）

1 引 言

點云作為計算機圖形學(xué)中的基本形狀表示法，被廣泛用于虛擬現(xiàn)實、環(huán)境感知、機器人導(dǎo)航和文物保護等領(lǐng)域［1］。

由于采集設(shè)備本身的測量精度和存在的各種外界因素，如光照、反射率和拼接誤差等，原始點云數(shù)據(jù)會受到噪聲和離群點的破壞。特別是當(dāng)點云同時包含尖銳特征和較強幅度噪聲的情況下，去噪過程變得越發(fā)困難，因為在某些復(fù)雜情況下特征很難與噪聲進行有效區(qū)分；同時，原始點云數(shù)據(jù)不包含幾何拓撲信息，所以沒有先驗信息來指導(dǎo)重構(gòu)過程。因此，點云的重構(gòu)是一項具有挑戰(zhàn)性的任務(wù)，關(guān)鍵是如何在抑制噪聲的同時恢復(fù)特征［2］。

近年來，針對三維點云重構(gòu)出現(xiàn)了大量優(yōu)秀算法。Alexa等［3］定義了點集的隱式曲面（Point Set Surfaces，PSS），利用移動最小二乘（Moving Least Squares，MLS［4］）將鄰域點投影至局部擬合平面。為了避免MLS中的多項式擬合，Amenta等［5］直接利用質(zhì)心的加權(quán)和光滑的梯度場來定義和計算曲面，在局部加權(quán)法向的基礎(chǔ)上，通過鄰域內(nèi)樣本的加權(quán)平均來實現(xiàn)點云的投影操作。但是MLS假設(shè)隱含面分段光滑，不可避免地導(dǎo)致幾何特征變模糊。Guennebaud等［6］在PSS基礎(chǔ) 上 提 出 了APSS（Algebraic Point Set Surfac?es），使用具有法向約束的球擬合，更好地適應(yīng)不同曲率特征，當(dāng)點云稀疏時也具有較好的處理效果，但是無法恢復(fù)拐角和棱邊等尖銳特征。為了克服MLS對離群點的敏感性以及平滑尖銳特征的缺點，?ztireli等［7］結(jié)合移動最小二乘和局部核回歸提出RIMLS（Robust Implicit MLS）方法，使其對噪聲、異常值甚至稀疏采樣具有魯棒性。前述方法都是在局部鄰域內(nèi)進行的，當(dāng)存在強噪聲和離群點時，無法有效辨識噪聲和尖銳特征。

近年來，全變分方法受到廣泛關(guān)注，其思想來自于信號處理領(lǐng)域，通過度量與解的稀疏性相關(guān)的范數(shù)誤差構(gòu)建能量函數(shù)，實現(xiàn)信號的稀疏優(yōu)化［8］。這類方法具有典型的全局特性，可以更好地在含噪信號中辨識尖銳特征?；诙鄶?shù)點云數(shù)據(jù)是分段光順以及構(gòu)成尖銳特征的點只占少數(shù)的事實，Avron等［9］將L 1稀疏表示引入點集的去噪過程中，通過直接使用一個重加權(quán)的L 1最小化過程對點集進行濾波重構(gòu)，并實現(xiàn)特征的保持。此外，L 0優(yōu)化同樣是一種全變分方法，比起L 1具有更強的稀疏性，因此可以處理更高級別的噪聲，如離群點等。受到Xu等［10］在圖像去噪以及He等［7］在網(wǎng)格濾波研究的啟發(fā)，Sun等［11］利用L 0最小化實現(xiàn)點云的降噪，雖然很好地保持了銳利的特征，但過度追求特征稀疏性導(dǎo)致平滑的曲面特征容易退化成分段平面。

前述方法要么無法有效保持銳利特征，要么可能在去噪過程中產(chǎn)生不自然的偽特征。為了克服這些局限性，本文提出了一種基于L 0稀疏優(yōu)化的點云重構(gòu)方法。整個過程大致分為3個步驟：首先，利用點的局部張量估計隱含面的幾何屬性，并通過成對一致性投票（Pair Consistency Voting，PCV）辨識特征點的局部最優(yōu)鄰域，在此基礎(chǔ)上進行特征點法向的回歸估計；然后，在L 0最小化的基礎(chǔ)上引入自適應(yīng)微分算子和投影正則項，實現(xiàn)不同特征區(qū)域點云的自適應(yīng)降噪；最后，根據(jù)優(yōu)化后的法向場對尖銳特征點進行投影恢復(fù)。本文所述算法的稀疏性介于L 0和L 1之間［12］，因此既可以處理具有明顯尖銳特征的工件模型，也可以處理如雕像這類曲面特征占多數(shù)的模型。

2 特征點法向估計

法向蘊含曲面流型的局部幾何信息，因此法向?qū)c云的重構(gòu)至關(guān)重要。原始點云不具有法向信息，需要進行可靠估計。

2.1 特征點識別

2.2 鄰域魯棒辨識

對于點云平坦區(qū)域的非特征點，基于各向同性采樣的法向回歸估計，如PCA（Principal Com?ponents Analysis）及其派生方法，可以獲得穩(wěn)定的計算結(jié)果。但是對于多個光滑流形面交界處，如拐角或棱邊等特征，各向同性選擇擬合數(shù)據(jù)區(qū)域?qū)е路ㄏ蚬烙嬍艿蕉鄠€不同鄰近流形面上點的影響，法向估計并不穩(wěn)定。為此，通常的策略是利用區(qū)域分割［15］或各向異性權(quán)重［16-17］找到具有相近法向點的局部鄰域，或排除屬于其他鄰域面的點，從而獲得更為可靠的法向估計。但是特征處點云可能伴隨非均勻采樣和大噪聲，特征附近初始法向估計誤差較大，因此選擇離特征較遠點的法向辨識鄰域更加可靠。然而直接構(gòu)造這樣一個鄰域并不容易，因為原始點云是無結(jié)構(gòu)的。

為了選擇一個最有可能不包含特征的鄰域，本文首先利用成對一致性投票［15］進行特征點pfi∈Pf處隱含流形面的最大似然平面估計：

2.3 法向回歸估計

3 點云稀疏優(yōu)化重構(gòu)

3.1 點云L 0稀疏降噪

通常點云隱含的流形面是分段光滑的，即除了形成尖銳特征的少數(shù)點，大部分點屬于光滑區(qū)域。因此，可以利用尖銳特征點的稀疏性進行點云濾波，即稀疏低秩建模。Sun等［11］利用L 0最小化去除原始點云?中包含的噪聲：

上述表達式關(guān)于{pi}是二次的，因此可以通過稀疏最小二乘相關(guān)技術(shù)來求解。前述兩步優(yōu)化交替進行直到收斂，δ初始設(shè)置為0.02，在每次迭代中δ將被放大2倍，當(dāng)δ接近無窮時，D(pi)j逼近θij。

前述點云L 0優(yōu)化濾波在構(gòu)建微分算子D(pi)j時假設(shè)局部鄰域是平坦的，即某點及其鄰域點應(yīng)該在一個平面π(n?i，pi)上，當(dāng)點云中隱含曲面時，由于平面對曲面的非緊致估計，使得構(gòu)建的微分算子會將曲率較小的曲面誤認為是平面，從而對該曲面進行調(diào)整，使其逐漸退化成多個平面的組合，并在此過程中形成虛假邊界特征，導(dǎo)致濾波后的點云發(fā)生畸變，參見圖3（d）。本文通過自適應(yīng)權(quán)重降低L 0優(yōu)化的稀疏性，從而避免特征誤判的發(fā)生，并依靠投影算子正則項來避免曲面特征退化成平面。

3.2 正則化濾波模型

為了更好地保持原始點云中的曲面特征，本文利用投影算子R(pi)j正則項和特征權(quán)重ωfij防止曲面特征在L 0最小化交替求解過程中發(fā)生退化：

其中，R(pi)j=n?j?(pj-pi)，即利用鄰域點的微切平面將特征點投影到由各鄰域面所決定的隱含流形面上。如果點云局部區(qū)域是外凸的，該算子具有將點pi往外凸的方向調(diào)整的作用，從而防止曲面在微分算子D(pi)j作用下發(fā)生內(nèi)凹退化成平面，參見圖1。隨著優(yōu)化迭代的進行，點云中的噪聲逐漸減小，特征變得光順而無需過多調(diào)整，因此在每次迭代中，根據(jù)經(jīng)驗將正則項權(quán)重β乘以0.5，從而快速減小正則項在優(yōu)化過程中的影響，在優(yōu)化開始時賦予正則項較高的權(quán)重，并在優(yōu)化后期將其效果降低，文中β初值取經(jīng)驗值0.1。

圖1 不同算子作用下曲面調(diào)整Fig.1 Surface adjustment of different operator

此外，特征權(quán)重?。?/p>

其中，參數(shù)φ為法向變化尺度，文中取經(jīng)驗值45°。該特征權(quán)重反映了點云局部彎曲程度，使其既可以在特征分類中增加平面、曲面與拐角等特征的區(qū)分度；又可以在實際二次優(yōu)化降噪中避免由于噪聲的非均勻性或調(diào)整時的非同步性而產(chǎn)生的偽特征點被保留，抑制虛假輪廓特征的產(chǎn)生。

3.3 尖銳特征恢復(fù)

其中：nfi和nj分別是點pfi及其鄰域點的單位法向，τ為夾角閾值，取經(jīng)驗值0.5～1。

特征邊界上的點應(yīng)該受到至少兩個鄰域面的約束，但是尖銳特征點在前述濾波過程中僅沿單一鄰域面的法向進行調(diào)整，約束不足導(dǎo)致調(diào)整后的特征點不在各鄰域面的交線或頂角上，故呈現(xiàn)鋸齒狀分布，如圖3（d）和4（d）所示。為了更好地恢復(fù)尖銳特征，本文使用投影算子將尖銳特征點psi∈Ps進一步投影到隱含的特征邊界上：

相較于文獻［11］，本文所述尖銳特征恢復(fù)過程忽略了點psi處的法向約束，使得該點不限于在其切平面上調(diào)整，可以更好地恢復(fù)尖銳特征。

4 實驗結(jié)果與分析

利用本文所述算法對測量和仿真的點云數(shù)據(jù)進行了濾波重構(gòu)實驗，并與現(xiàn)有主流算法進行了比較。實驗程序采用C++語言編寫，運行于Intel core i5-3.4GHz筆記本電腦上的Ubuntu 14.04 LTS操作系統(tǒng)。

4.1 鄰域辨識與法向估計對比

圖2展示了不同法向估計算法對圖2（a）所示點云模型中頂角特征處鄰域點的辨識與法向估計的結(jié)果。如圖2（b），PCA法由于鄰域是各向同性的，因此噪聲和離群點影響了法向估計的精度和一致性。圖2（c）為使用雙邊法向濾波［16］得到的結(jié)果，可以發(fā)現(xiàn)由于鄰域點分布于多個鄰域面上，且權(quán)重考慮了初始法向，導(dǎo)致特征處的法向估計不穩(wěn)定，存在較大方差。Wang等［17］提出的加權(quán)迭代回歸法同時考慮法向、距離與離差3個因素，保證只有來自于同一個流形面的鄰域點對于法向的估計產(chǎn)生重要影響，但依然會對離群點分配小的權(quán)重，且為了得到良好的法向估計結(jié)果需要考慮多個帶寬參數(shù)，當(dāng)噪聲較強時，帶寬難以確定，如圖2（d）。圖2（e）是本文所述方法得到的鄰域和估計的法向，可以發(fā)現(xiàn)加權(quán)回歸估計配合正確的鄰域得到了更加一致的法向分布，且能夠有效估計尖銳拐角特征處的法向。

圖2 鄰域點辨識與法向估計比較Fig.2 Comparison of neighbor points identification and normal estimation

為了進一步對法向估計的準(zhǔn)確性進行量化評價，首先對理想點云模型進行三角網(wǎng)格劃分，然后利用去噪點云模型P?和理想網(wǎng)格模型M法向間的平均角度誤差（Mean angular deviation，MAD［1］）作為評價指標(biāo)：

4.2 典型算法處理效果對比

圖3和圖4顯示了本文所述方法與APSS［5］，RIMLS［6］，L0［11］3種 典 型 算 法 間 的 重 構(gòu) 效 果 對比。為了便于觀察，對點云進行了渲染處理。由于APSS使用移動最小二乘法擬合球面進行投影重構(gòu)，因此在圓弧特征部分都實現(xiàn)了比較精確的還原，但是無法恢復(fù)尖銳的特征。RIMLS使用核回歸進行曲面魯棒重建并考慮到特征的保持，因此在圖3（d）中模型的邊緣輪廓部分恢復(fù)效果較好。但是當(dāng)噪聲較強時，光滑區(qū)域依然存在缺陷。由于L 0的稀疏特性，尖銳特征被有效保留，但是曲面特征被抑制，如圖3（e）在兩端圓柱部分以及圓孔部分都產(chǎn)生較大的畸變。本文方法不僅保留了精確的尖銳特征信息，對于曲面特征濾波效果良好，具有較好的特征保持能力，如圖3（f）所示。

圖3 真實點云重構(gòu)效果對比Fig.3 Comparison of reconstruction effects of real point clouds

4.3 重構(gòu)誤差與耗時定量分析

為了量化比較各種算法的處理效果，本文利用圖4所示仿真二面角和圓柱體的理想點云模型，與加噪濾波后的重構(gòu)點云模型進行定量誤差分析［1］。加噪點云模型是在理想點云模型上加入沿法向方差為0.4倍一環(huán)鄰域點平均距離的高斯噪聲。

圖4 仿真點云重構(gòu)效果對比Fig.4 Comparison of reconstruction effects of synthetic point clouds

為了量化點重構(gòu)的位置誤差，通過網(wǎng)格模型M和去噪點云模型P?之間的離差作為評價指標(biāo)：

其中：A i是三角網(wǎng)格M中某個三角面的面積，dist(p*i，Tc)是某個重構(gòu)的點p?i∈P?到網(wǎng)格模型中最近三角形Tc∈M的垂直投影距離，M1-ring(i)為點p?i的一環(huán)鄰域面集合。

針對二面角和圓柱體兩個模型進行Ep和MAD兩種誤差分析，圖5顯示了圖4各種濾波重構(gòu)算法迭代過程中Ep和MAD的變化情況?？梢园l(fā)現(xiàn)隨著迭代次數(shù)的增加，Ep和MAD的誤差逐漸減小，無論是具有尖銳特征的二面角模型還是具有曲面的圓柱體模型，本文所述方法的重構(gòu)誤差是最小的。與傳統(tǒng)的L 0點云濾波重構(gòu)算法［11］相比，經(jīng)過本文所述算法處理后點云模型的重構(gòu)誤差Ep平均減小10.2%，法向誤差MAD平均減小29.7%。

表1顯示了圖4各種算法濾波重構(gòu)的耗時統(tǒng)計。由于APSS與RIMLS為局部優(yōu)化法，因此在時效性上要優(yōu)于基于全局優(yōu)化的L 0與本文所述方法，本文所述方法耗時略高于3種典型方法中重構(gòu)精度最高的L 0法。

表1 算法耗時統(tǒng)計Tab.1 Time consumption statistics of different algo?rithms

5 結(jié) 論

本文提出了一種基于L 0稀疏優(yōu)化的點云重構(gòu)方法。引入魯棒統(tǒng)計的思想實現(xiàn)特征處鄰域的有效辨識，增加法向估計的準(zhǔn)確性。為了解決平面微分算子對于曲面特征的非緊致估計，通過投影算子正則項解決L 0優(yōu)化交替求解過程中曲面特征過度調(diào)整而產(chǎn)生的畸變，并利用考慮點云局部幾何特性的自適應(yīng)微分算子，避免L 0優(yōu)化過度追求稀疏性，而產(chǎn)生虛假邊界輪廓。根據(jù)優(yōu)化后的法向場對點云中尖銳特征進行辨識，憑借投影算子對尖銳特征點進行優(yōu)化恢復(fù)。本文所述方法可以有效提高點云的質(zhì)量，相比傳統(tǒng)L 0點云濾波重構(gòu)算法，重構(gòu)后點云的誤差平均減小10.2%，法向誤差平均減少29.7%，同時視覺效果優(yōu)于現(xiàn)有典型算法，為基于點云的計算機三維測量與逆向建模提供一種有效預(yù)處理方法。

在今后的研究中，可以考慮引入基于曲面模型的微分算子，更加準(zhǔn)確判斷特征邊界，在提高曲面特征恢復(fù)能力的同時增加算法的收斂速度。