梁士超，韓永國，吳亞東

（西南科技大學 計算機科學與技術(shù)學院，四川 綿陽621000）

0 引 言

近年來，眾多學者提出了多種點云模型去噪算法。常用的去噪技術(shù)主要是通過濾波實現(xiàn)的，如高斯濾波、Wiener濾波、Laplace濾波和雙邊濾波等［2－4］。其它還有基于投影、聚類以及局部幾何信息擬合的去噪方法。依據(jù)參數(shù)設(shè)定的不同及迭代次數(shù)的增加，Laplace濾波和Wiener濾波會使模型產(chǎn)生不同程度的收縮或擴張，導致模型變形［5］。Huang等［6］提出了一種原始點云增強的方法，采用加權(quán)局部最優(yōu)投影來消除噪聲、刪除外點；孫正林等［7］利用改進的Mean Shift算法將散亂點云沿矢量方向快速移動到核密度估計函數(shù)的最大值點，從而達到提高點云數(shù)據(jù)質(zhì)量的目的。

本文在文獻 ［5，8］的基礎(chǔ)上，結(jié)合統(tǒng)計分析學中的協(xié)方差分析法和數(shù)據(jù)挖掘中的聚類算法，提出了一種基于K－近鄰的去噪算法。基于K－近鄰的協(xié)方差分析可得當前點在局部空間上的主成分分布，其最小特征值對應(yīng)的特征向量可作為當前點的法向量。當前點法向量與其鄰域內(nèi)其它點的法向量差別越大，當前點所在區(qū)域的表面特征越豐富，在去噪過程中就愈要加以保留；而法向量的差別越大，由法向量構(gòu)造的差向量的模就越大。本文算法正是以當前點法向量與其鄰域點的法向量構(gòu)造的差向量作為高斯核函數(shù)參數(shù)，同時引入面積權(quán)重因子加以光順，從而計算點云中鄰域點對當前點的影響值，進而判斷該點是否為噪聲點。改進后的算法充分考慮點云的局部空間特征，能夠在有效去除噪聲的同時，保持模型的尖銳及平滑特征。

1 空間單元格劃分及離群點濾除

散亂點云離群點識別和濾除是重建高質(zhì)量曲面的前提，也是散亂點云預(yù)處理的重要步驟［9］。本文基于點云模型的空間單元格劃分，通過構(gòu)造單元格的最大連通域，可在完全去除距離較遠離群點的同時，有效去除模型表面的部分噪聲點。

1.1 單元格劃分

本文使用文獻 ［8］中用到的空間單元格劃分法，詳細的劃分過程可參見文獻［8］，假定輸入點云模型為M，模型數(shù)據(jù)為P＝ ｛pi｝i∈I，pi∈R3。本文主要工作是建立基于結(jié)構(gòu)體的數(shù)據(jù)結(jié)構(gòu)，并為小立方體創(chuàng)建基于該類型的動態(tài)存儲器變量cub＿vector。遍歷點云數(shù)組，計算各點所在小立方體，并將點的下標和小立方體的索引添加到對應(yīng)的變量中。

設(shè)X、Y、Z 為3 個方向上數(shù)據(jù)點的最小坐標為：cubmin＿x，cubmin＿y，cubmin＿z； 最大坐標為：cubmax＿x，cubmax＿y，cubmax＿z；小立方體的長度為：cub＿size；當前點的坐標為：pc＿x，pc＿y，pc＿z，則小立方體在3個坐標軸方向上的個數(shù)m、n、l分別為

當前點所在小立方體的坐標索引分別是

空間小立方體如圖1所示。

圖1 空間小立方體

1.2 最大連通域

本文改進文獻 ［10］中所用區(qū)域增長法，構(gòu)造基于小立方體的最大連通域。其主要思想是：循環(huán)遍歷cub＿vector，將所有相鄰立方體歸并到同一連通域，最后求出包含立方體數(shù)目最多的連通域，即為最大連通域。

具體算法流程如下：

（1）創(chuàng)建保存連通域的結(jié)構(gòu)體及相應(yīng)的動態(tài)存儲器變量cub＿connected；創(chuàng)建動態(tài)隊列變量cub＿queue存儲當前連通域中未被遍歷的小立方體；將cub＿vector中第一個小立方體存入cub＿queue；

（2）取cub＿queue隊首元素，在cub＿vector中遍歷其上、下、左、右、前、后共26個相鄰立方體，若相鄰立方體有效，則將相應(yīng)立方體存入cub＿queue；彈出cub＿queue的隊首元素，標記已遍歷并存入cub＿connected；

（3）重復(fù)步驟 （2），直至隊列為空；若cub＿vector中所有小立方體均已遍歷則轉(zhuǎn)入步驟 （4），否則遍歷cub＿vector找到第一個未被遍歷的小立方體，存入cub＿queue，并轉(zhuǎn)入步驟 （2）；

（4）計算cub＿connected 中各個連通域包含的小立方體數(shù)目，保留最大的連通域，將其它連通域中的小立方體及相應(yīng)數(shù)據(jù)點標記無效。

圖2為含噪Y 模型基于空間單元格最大連通域濾除離群點的效果。

圖2 含噪Y 模型基于單元格最大連通域濾除離群點效果

2 K－近鄰搜索和鄰域協(xié)方差分析

2.1 K－近鄰搜索

對于點云模型M 中的數(shù)據(jù)P ＝ ｛pi｝i∈I，pi∈R3，距離點pi最近的k 個點稱為Pi的K－近鄰，記作Nb（p）［11］。目前空間單元格法、八叉樹法和K－d 樹法［11］常用于計算K－近鄰，而前兩種適用基于包圍盒的方法實現(xiàn)。這些算法雖然簡單直觀、易于實現(xiàn)，但是如果點云數(shù)量達到十萬級以上，則會耗費相當?shù)臅r間，本文采用改進的空間單元格法可有效縮短計算時間，具體實驗數(shù)據(jù)見 “實驗結(jié)果與分析”部分。

為縮減計算時間，本文創(chuàng)建基于K－近鄰的結(jié)構(gòu)體類型變量vert＿knn，用于存儲當前點索引、鄰域點索引、鄰域點距離、鄰域特征值和特征向量等相關(guān)信息。在K－近鄰搜索過程中，首先記錄小立方體的相鄰立方體在cub＿vector中的索引。然后遍歷存儲數(shù)據(jù)點的一維數(shù)組，計算當前點與所在立方體及相鄰立方體內(nèi)其它點的距離，將距離最小的k個數(shù)據(jù)點索引及距離存入當前點的vert＿knn 變量中。最后，檢查當前點的鄰域點個數(shù)，若已達到k 個，則繼續(xù)下一個點，否則再次遍歷相鄰立方體的相鄰立方體，直至達到k個。

2.2 協(xié)方差分析

基于點的表示中一個必不可少的屬性是法向量信息［1］。不僅高質(zhì)量的基于點的繪制方法依賴于法向量，許多表面重建算法［12］也需要在擁有精確的法向量信息的條件下得到精確的重建效果。目前點的法向量估計算法主要是基于點的局部協(xié)方差分析的方法［13］。給定任意一點pi∈P，可以構(gòu)造如下3×3的半正定協(xié)方差矩陣C

式中：Np——2.1節(jié)所述點pi的鄰域點集，pc——鄰域點集Np的質(zhì)心。協(xié)方差分析如圖3所示。

圖3 點云局部K－近鄰選取和協(xié)方差分析二維圖

由圖3可知，點云在局部空間上的主成分方向由協(xié)方差矩陣C 的特征向量表示，而各主成分方向上的變化量則由相應(yīng)的特征值衡量。最小特征值對應(yīng)的特征向量可以作為點云局部空間法向量的近似估計。協(xié)方差分析作為一種統(tǒng)計方法本身有一定的抗噪作用［13］。但是當點云中存在距離模型較遠的離群點時，該方法通常不能得到較為精確的結(jié)果，而本文上述基于最大連通域的去噪操作可以去除較大的噪聲，同時部分距離模型主體稍遠的噪點也能被去除，有效地提高了協(xié)方差分析算法計算點云局部特征信息時的精確度。

3 參數(shù)改進的加權(quán)核密度估計

基于核密度估計的點云去噪算法主要存在容易丟失尖銳特征、去除稀疏分布數(shù)據(jù)等問題，而這些問題都和核函數(shù)及其參數(shù)以及核密度閾值Dσ的選取有直接的關(guān)系。如果沒有恰當選擇核函數(shù)及其參數(shù)，則計算出的核密度值無法有效體現(xiàn)點云的表面特征；至于核密度閾值Dσ，若取值過小，則只有很少一部分點被視為噪聲點，若Dσ取值過大，模型中均勻分布的稀疏點云會被視為噪聲點。

針對上述問題，許多學者將聚類算法引入去噪技術(shù)中［14］。文獻 ［7］利用改進的Mean Shift算法迭代計算所有點在三維空間中x、y 方向上投影值，若某一點與另一點在迭代過程中的軌跡點重合或者差值小于給定的閾值，則停止迭代，并標記二者的收斂點相同。該算法能有一定程度的平滑噪聲，但是核函數(shù)的窗口寬度及閾值的選取需要多次實驗才能獲得相對較好的效果。文獻 ［8］選取高斯核函數(shù)估計點云中每個點對鄰域點的影響，并在此基礎(chǔ)上對窗口寬度參數(shù)的選取進行了改進。該算法以鄰域點的歐式距離為核函數(shù)參數(shù)，而歐式距離并不包含方向信息，即歐式距離相等時法向量可以有很大差別，甚至完全相反，這在模型尖銳特征處及均勻分布的稀疏區(qū)域尤其明顯。因此該算法并不能有效保留模型的細節(jié)特征。

3.1 參數(shù)改進的核密度函數(shù)

基于以上表述，為了充分體現(xiàn)點云的局部空間特征，本文提出了一種改進方法，即將法向量的差向量引入高斯核函數(shù)。差向量越大則當前點與鄰域點的差別越大，局部特征信息越豐富；反之，差向量越小，則特征越不明顯。算法主要思想是：基于2.2節(jié)中的協(xié)方差分析，計算所有點的特征值和特征向量，存入對應(yīng)的vert＿knn 變量；遍歷vert＿knn，計算并存儲當前點與鄰域點法向量的差向量；以每個點的差向量的模的均值作為核函數(shù)窗口的自適應(yīng)帶寬，計算各數(shù)據(jù)點的核密度值。則核密度函數(shù)如式 （4）所示，算法原理二維如圖4所示

式中：ni——點pi的法向量，nj——pi鄰域內(nèi)點的法向量，σi——核函數(shù)的自適應(yīng)窗口寬度。與聚類方法相同，本算法也是基于局部密度函數(shù)來逼近全局密度函數(shù)。最后，設(shè)定閾值ζ，通過與閾值的比較過濾噪聲點［15］。

圖4 基于鄰域法向量之差的核密度估計二維圖

3.2 加權(quán)因子

雖然利用本文改進的核函數(shù)可以有效檢測點云尖銳特征，但是到目前為止并沒有考慮均勻分布的稀疏點云。為了能充分保持模型特征，本文加入了面積權(quán)重因子［5］。如2.2節(jié)所述，點云局部空間上相應(yīng)的特征值衡量了各主成分方向上的變化量，因此可以利用上文所求的最大特征值與次特征值的乘積來近似代替面積，以達到保留模型中稀疏分布點云數(shù)據(jù)的目的，有效提高算法的特征保持精度。則加權(quán)后的核密度函數(shù)為

式中：λi2、λi3——pi的次特征值和最大特征值。

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

本文算法在主頻3.40GHz，內(nèi)存4.0GB的Inter（R）Core（TM）32位PC機上基于MFC 與Open GL 進行仿真實驗。文獻 ［8］采用原有空間單元格法，本文采用改進的單元格法分別在Shutter模型、含噪Y 模型和Mimosa模型上運行，用于比較兩種算法在不同量級的點云模型上K－近鄰搜索耗費的時間，同時以含噪Y 模型和Mimosa模型的運行結(jié)果比較兩種算法的去噪和特征保持效果。文獻 ［8］認為閾值最為合適，其中為點云的全局核密度平均值。若Dp（pi）＞ζ，則認為鄰域點對pi的影響較大，也即說明pi與其鄰域點關(guān)系 “親密”，可將pi視為模型上的點［11］而非噪聲點。反之，視為噪聲點，并予以濾除。含噪Y 模型在上下分界處有一定的弧度，這使得模型上點的分布在呈現(xiàn)出一定規(guī)律的同時也有一定的不規(guī)則性，而模型邊界附近的噪聲點則進一步加劇了這種不規(guī)則性，這些分布特點可以用來驗證算法對噪聲點的識別效果。Mimosa模型有很多均勻分布的稀疏區(qū)域，如枝、葉等，同時模型中若干部分分布較近，這些相鄰分布的區(qū)域彼此產(chǎn)生類似噪聲的效果，因此Mimosa模型可用于驗證算法的特征保持效果。圖5和圖6分別為兩種算法在兩個模型上的去噪效果。由圖5 可知兩種算法在模型的非特征區(qū)域（如Y 模型的下半部分）去噪效果幾乎相同，都能有效識別距離模型較近的噪聲點。然而在特征區(qū)域 （如圖5中方框處）文獻 ［8］所用算法并不能有效識別噪聲點，可以看出此時模型表面仍有大量分布密集的噪聲點，但是本文算法能識別出附著在表面的噪聲點，并在去除噪聲的同時，有效地保持了模型邊界特征的完整性。圖6則進一步驗證了兩種算法的特征保持效果。通過放大圖可以看出，在Mimosa模型的枝、葉等均勻分布的稀疏區(qū)域文獻 ［8］所用算法產(chǎn)生了嚴重的誤刪除操作，在枝丫區(qū)域、枝葉與枝干相鄰區(qū)域出現(xiàn)整段枝干丟失現(xiàn)象，而本文算法則保留了枝丫，同時并未出現(xiàn)枝干丟失現(xiàn)象，有效保持了模型的特征。表1統(tǒng)計了兩種算法的相關(guān)去噪信息。

表1 最優(yōu)條件下兩種算法的去噪效果比較

圖5 文獻 ［8］算法與本文算法在含噪Y 模型上的去噪效果比較

圖6 文獻 ［8］算法與本文算法在含噪Mimosa模型上的去噪效果比較

5 結(jié)束語

本文參考統(tǒng)計分析中的協(xié)方差分析和數(shù)據(jù)挖掘中的聚類算法等相關(guān)知識，將鄰域法向量的差向量及面積權(quán)重因子引入高斯核函數(shù)，改進了基于K－近鄰的點云去噪算法。實驗結(jié)果表明本文算法在檢測出離群點的同時，有效地保留了模型的特征信息。對于本文引入的兩個參數(shù)，從實驗結(jié)果可以看出，仍有一小部分離散的噪聲點未被識別出來，并且還不能完全保留模型所有分布比較稀薄的區(qū)域，這些都是本文算法今后改進的核心。

［1］LI Bao.Survey on normal estimation for 3Dpoint clouds［J］.Computer Engineering and Applications，2010，46 （23）：1－7（in Chinese）.［李寶.三維點云法向量估計綜述 ［J］.計算機工程與應(yīng)用，2010，46 （23）：1－7.］

［2］ZHANG Fan.On geometry pressing of point cloud data ［D］.Xi’an：Northwest University，2013 （in Chinese）.［張帆.點云數(shù)據(jù)幾何處理方法研究 ［D］.西安：西北大學，2013.］

［3］LIU Bin.Denoising of point model based on orthogonal projection constraint［J］.Computer Engineering，2012，38 （20）：264－267 （in Chinese）.［劉彬.基于正交投影約束的點模型去噪 ［J］.計算機工程，2012，38 （20）：264－267.］

［4］LI Jinjiang.Point cloud denoising algorithm based on swarm intelligent［J］.Computer Integrated Manufacturing Systems，2011，17（5）：935－945（in Chinese）.［李晉江.群體智能點云光順去噪算法［J］.計算機集成制造系統(tǒng)，2011，17 （5）：935－945.］

［5］XU Bo.CUDA－based point cloud denoising algorithm ［J］.Computer Engineering，2011，37 （2）：224－226 （in Chinese）.［徐波.基于CUDA 的點云去噪算法 ［J］.計算機工程，2011，37 （2）：224－226.］

［6］Huang H，Li D，Zhang H，et al.Consolidation of unorganized point clouds for surface reconstruction ［J］.ACM Trans Graph，2009，28 （5）：176：1－176：7.

［7］SUN Zhenglin.An improved Mean Shift algorithm used for point cloud data filtering ［J］.Engineering of Surveying and Mapping，2011，20 （5）：57－59 （in Chinese）. ［孫正林.一種改進的Mean Shift點云數(shù)據(jù)濾波 ［J］.測繪工程，2011，20（5）：57－59.］

［8］ZHANG Yi.Research and improvement of denoising method based on K－neighbors［J］.Journal of Computer Applications，2009，29 （4）：1011－1014 （in Chinese）.［張毅.基于K－近鄰點云去噪算法的研究與改進 ［J］.計算機應(yīng)用，2009，29（4）：1011－1014.］

［9］NIE Jianhui.Outlier detection of scattered point cloud by clas－sification ［J］.Journal of Computer－Aided Design ＆Computer Graphics，2011，23 （9）：1526－1532 （in Chinese）.［聶建輝.散亂點云離群點的分類識別算法 ［J］.計算機輔助設(shè)計與圖形學學報，2011，23 （9）：1526－1532.］

［10］HAN Li.Discrete curvature constrained triangle mesh model segmenting technique［J］.Journal of Computer－Aided Design＆ Computer Graphics，2009，21 （6）：831－835 （in Chinese）.［韓麗.離散曲率約束的三角網(wǎng)格模型拓撲分割算法［J］.計算機輔助設(shè)計與圖形學學報，2009，21 （6）：831－835.］

［11］ZHANG Yi.Density－based detection for outliers and noises［J］.Journal of Computer Applicatioins，2010，30 （3）：802－805 （in Chinese）.［張毅.基于密度的離群噪聲點監(jiān)測 ［J］.計算機應(yīng)用，2010，30 （3）：802－805.］

［12］Ztireli AC，Guennebaud G，Gross M.Feature preserving point set surfaces based on non－linear kernel regression ［J］.Compute Graph Forum，2009，28 （2）：493－501.

［13］SU Zhixun.Denoising of point－sampled model based on normal mollification and median filtering ［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2010，22 （11）：1892－1898 （in Chinese）.［蘇志勛.基于法向修正及中值濾波的點云平滑 ［J］.計算機輔助設(shè)計與圖形學學報，2010，22（11）：1892－1898.］

［14］Weber C，Hahmann S，Hagen H.Sharp feature detection in point clouds［C］//Shape Modeling International Conference，2010：175－186.

［15］WANG Xiaochao.Feature detection on point cloud via local reconstruction ［J］.Journal of Computer－Aided Design ＆Computer Graphics，2013，25 （5）：659－665 （in Chinese）.［王小超.基于局部重建的點云特征點提取 ［J］.計算機輔助設(shè)計與圖形學學報，2013，25 （5）：659－665.］