三維點云自適應稀疏優化重構

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

（上海海事大學 電氣自動化系，上海201306）

1 引 言

點云作為計算機圖形學中的基本形狀表示法，被廣泛用于虛擬現實、環境感知、機器人導航和文物保護等領域［1］。

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

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

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

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

2 特征點法向估計

法向蘊含曲面流型的局部幾何信息，因此法向對點云的重構至關重要。原始點云不具有法向信息，需要進行可靠估計。

2.1 特征點識別

2.2 鄰域魯棒辨識

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

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

2.3 法向回歸估計

3 點云稀疏優化重構

3.1 點云L 0稀疏降噪

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

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

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

3.2 正則化濾波模型

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

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

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

此外，特征權重取：

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

3.3 尖銳特征恢復

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

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

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

4 實驗結果與分析

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

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

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

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

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

4.2 典型算法處理效果對比

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

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

4.3 重構誤差與耗時定量分析

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

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

為了量化點重構的位置誤差，通過網格模型M和去噪點云模型P?之間的離差作為評價指標：

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

針對二面角和圓柱體兩個模型進行Ep和MAD兩種誤差分析，圖5顯示了圖4各種濾波重構算法迭代過程中Ep和MAD的變化情況。可以發現隨著迭代次數的增加，Ep和MAD的誤差逐漸減小，無論是具有尖銳特征的二面角模型還是具有曲面的圓柱體模型，本文所述方法的重構誤差是最小的。與傳統的L 0點云濾波重構算法［11］相比，經過本文所述算法處理后點云模型的重構誤差Ep平均減小10.2%，法向誤差MAD平均減小29.7%。

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

表1 算法耗時統計Tab.1 Time consumption statistics of different algo?rithms

5 結 論

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

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