李剛森　程遠志

摘 要：使用3D掃描工具獲取點云數據時常常會伴隨著加性噪聲。本文提出了一個基于凸集平均映射（APOCS）的原創(chuàng)點云去噪算法。首先，使用基于相關性篩選改良過的均值濾波算法對噪聲點云的法向量進行濾波。每個濾波后的法向量都能決定其相對應的局部平面，將這些平面視為凸集，可通過APOCS算法更新點云中各點的位置。在本文的最后將給出該算法在不同強度噪聲點云上與雙邊濾波對比的實驗結果。

關鍵詞：點云； 去噪； APOCS； Graph-cut

Abstract： Point cloud data is often accompanied by additive noise when it is collected by 3D scanning tools. This paper proposes an original method of point cloud denoising based on APOCS （Average Projections Onto Convex Sets）. First，the normal vectors of the noised point cloud is filtered using a mean filter improved by correlation based selection. And some planes are determined by the filtered normal vectors， which can be used to optimize the points ' locations through APOCS. Compared with bilateral filtering， the experiment demonstrates the results on point clouds with different intensity noises.

Key words： point cloud； denoise； APOCS； Graph-cut

引言

點云是計算機視覺領域一個新興方向。隨著近年來掃描技術的快速發(fā)展，大規(guī)模點云數據的獲取成為可能。然而，掃描工具不能像相機那樣精細，掃描獲得的點云往往會包含加性噪聲，嚴重影響了三維表面重構的效果。因此，點云數據的去噪算法將發(fā)揮十分重要的作用?，F存的點云去噪算法主要是通過濾波實現的，包括鄰域濾波和非局部濾波。這些方法在大多數情況下均能取得滿意的效果，但對離異點的效果不佳。

本文提出一種原創(chuàng)的點云數據去噪方法，該方法基于凸集平均映射（APOCS），不僅能夠與以往的點云去噪方法得到相同甚至更好的去噪效果，更關鍵的是對奇異點有極大的抗性。利用點P的鄰域內各點的法向量包含的信息進行去噪，這比利用P鄰域內各點的位置信息穩(wěn)健的多。

1 相關技術

很多點云去噪算法都是從2D圖像拓展到3D圖像的，例如應用十分廣泛的雙邊濾波。（Tomasi and Manduchi， 1998）利用雙邊濾波對噪聲圖像去噪[1]，而（Fleishman et al， 2003）將雙邊濾波應用到3D mesh模型去噪上[2]。此外，針對雙邊濾波不能同時兼顧平滑區(qū)域和紋理豐富區(qū)域的缺點，（Fu， 2015）將雙邊濾波和平面映射算法相結合應用到點云去噪當中[3]。除了雙邊濾波之外，（Taubin， 1995）將Laplace算法從圖像處理領域延伸到點云上面[4]，（Deschaud， 2010）將非局部去噪算法發(fā)展到點云去噪上[5]。（Buades et al， 2005）提出了一種計算像素之間相似度的方法[6]，但此方法并不適用于點云數據，因此Mines提出了一種基于MLS （moving least-squares）的相似度計算方法，可用于點云數據上。無獨有偶，（Mederos et al， 2003）將MLS用于點云去噪[7]，而（Fleishman et al， 2005）和（Oztireli et al， 2009）分別對該方法作出了改進而產生了RMLS（Robust Moving Leas Square） [8]和RIMLS（Robust Implicit Moving Least Square） [9]。有趣的是，這種基于MLS的點云去噪算法并不是通過濾波實現的，而是利用映射，這一點跟本文的方法如出一轍。

另外，還有一些專門針對3D點云數據提出的算法。（Zhu， 2005）提出了一種采用三維小塊算法實現的數據點壓縮方法[10]。（Liu， 2013）提出了一種相對復雜的基于三維重構數據的雙向點云去噪算法[11]。（Zhu， 2015）推出利用密度分析檢測分層奇異點的算法[12]。本文的方法也是直接針對3D點云數據提出的。

2 算法詳述

2.1 算法概況

假設有一含有加性噪聲的點云數據 C0=〖JB（{〗pi〖JB（|〗i∈I〖JB）〗〖JB）}〗，采用的算法是多次迭代的過程。每個迭代過程包含求點云法向量、更新點云頂點坐標兩個步驟。首次得到點云法向量時，由于點云有噪聲，法向量受到噪聲的影響而不準確，此時采用一種經過相關性篩選改良的均值濾波對法向量進行濾波。眾所周知，均值濾波有很強的平滑效果，為了避免點云過度平滑，僅在第1個循環(huán)當中采用這種法向量濾波操作，之后的迭代循環(huán)當中，只通過點云坐標估算法向量，不再對法向量做濾波操作。通常情況下，在迭代3到4次之后就可得到最優(yōu)的去噪結果。算法流程如圖1所示。

2.2 法向量的濾波算法

算法開始對法向量先做一次均值濾波操作。均值濾波器核的大小是決定濾波結果的一個重要參數。核太大，濾波結果會損失紋理信息，過于平滑。核太小，則濾波效果不明顯。這里選取一個相對較小的濾波器核，然后基于核內各點與待濾波點的相關性做一次篩選，剔除噪聲大的部分對濾波的影響。

本文的相關性篩選步驟受啟發(fā)于基于圖分割（graph cut）的聚類算法。將每個點云頂點視為圖的頂點，點云頂點之間的相關性作為圖的邊，這樣就可以構成一個圖。不過與聚類不同的是，人們并不需要知道一共有多少個類別，也不必知道每個點的所屬類別。只想找到與將要濾波的法向量所在點屬于同一類的點，也就是找出哪些點是跟將要濾波的法向量相關性比較大的點。因此，并不需要建立一個完整的圖（graph），或者說計算所有點兩兩之間的相關性，只需要計算待濾波點與其周圍最近的Nf個點之間的相關性。至于Nf個點兩兩之間的相關性，并不需要計算，因而大大減少了算法的復雜度。

這里N是參考點的數量。閾值的選取依據計算得到的相關性自適應選擇，一般會選擇相關性分布的一個斷層作為閾值，也就是閾值分開的兩個集合中的點相關性差距較大。

相關性計算公式中第3項的作用可以從圖3中清楚的看到。如圖3所示，點云中存在一個奇異點（圖中箭頭所指），該點與鄰域內其它點不在同一平面內，這種奇異點將影響做濾波的效果。若僅考慮兩點的位置遠近及法向量方向來計算兩點之間的相似性是不夠的，由于該奇異點與待濾波點pi（位于坐標原點的點）距離很近，法向量方向也差異不大，所以這個想要排除在外不予考慮的點很大程度上會被選作參與均值濾波的參考點。如在圖3（b）中，該奇異點被選為pi的均值濾波參考點，而將兩點在n〖DD（-*2〗→〖DD）〗i方向上的距離加入到相關性計算之后，奇異點就被排除在參考點集之外了。從圖中可直觀看到，奇異點在法向量方向上與其它非奇異點距離相差甚遠，將這個特征作為篩選均值濾波參考點集的參考因素，得到的結果更為理想，如圖3（c）所示。

與雙邊濾波對比的點云去噪的實驗結果見表2，從表2可以看出本文方法處理后的誤差要比雙邊濾波的誤差小很多，尤其是dV。事實上，dV刻畫的就是奇異點的處理結果，可以直觀的理解為最大的誤差，往往這些最大的誤差都是在奇異點上產生的。為了使結果更加生動直觀，將誤差比例的折線在圖6中給出?？梢郧逦髁说乜吹诫p邊濾波對于dV的效果微乎其微，甚至在有些情況會擴大該誤差。在這方面，本文提出的方法有顯著性的提升。圖7中給出一個典型代表的實驗結果。圖中右邊一列出現的點都是與原始無噪聲圖像誤差超過0.05的點，點越多說明結果越不好。圖7（b）中的點明顯多于圖7（c），尤其是耳朵、腳等紋理豐富的部位。這也是算法的優(yōu)勢所在。

4 結束語

本文提出了一個基于APOCS的原創(chuàng)點云去噪算法，該算法通過重復計算法向量、更新點坐標的操作實現。首先，用相關性篩選改良過的均值濾波對法向量進行濾波，然后用基于APOCS的方法更新點云頂點的坐標位置。將本文的算法與雙邊濾波在不同噪聲強度點云上的結果進行比較，印證了方法比雙邊濾波算法好很多，尤其是在處理奇異點的問題上。

參考文獻

[1] TOMASI C， MANDUCHI R. Bilateral filtering for gray and color[LL]

[JP5] images[C]//IEEE Conference on Computer Vision. Bombay， India：IEEE， 1998： 839-846.

[2] FLEISHMAN S， DRORI I， COHEN-OR D. Bilateral mesh denoising[J]//ACM transactions on graphics （TOG）， 2003， 22（3）： 950-953.

[3] YAN Fu， ZHAI Jinlei. Research on scattered points cloud denoising algorithm[C]// 2015 IEEE International Conference on Signal Processing， Communications and Computing （ICSPCC）. NINGBO， CHINA：IEEE， 2015： 1-5.

[4] TAUBIN G. A signal processing approach to fair surface design[C]//Proceedings of the 22nd annual conference on Computer graphics and interactive techniques. NEW YORK， NY， USA ：ACM， 1995： 351-358.

[5] DESCHAUD J E， GOULETTE F. Point cloud non local denoising using local surface descriptor similarity[J]. IAPRS， 2010， 38（3A）： 109-114.

[6] BUADES A， COLL B， MOREL J M. A non-local algorithm for image denoising[C]// IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR '2005） . SAN DIEGO， CA， USA：IEEE， 2005： 60-65.

[7] MEDEROS B， VELHO L， de FIGURIREDO L H. Robust smoothing of noisy point clouds[C]//Proc. SIAM Conference on Geometric Design and Computing. Brentwood， TN：Nashboro Press， 2003： 1-13.

[8] ZTIRELI A C， GUENNEBAUD G， GROSS M. Feature preserving point set surfaces based on non-linear kernel regression[J].Computer Graphics Forum， 2009， 28（2）： 493-501.

[9] ZHU Maomao， FENG Zujun， GUO Jianhua， et al. Data point reduction using a 3-dimensional cube algorithm[J]. Journal of Shanghai University（Natural Science Edition）， 2005，11（3）：242-246.

[10]LIU Hui， WANG Boxiong， REN Huaiyi， et al. Two-way point cloud denoising method based on three-dimensional reconstruction data[J]. Journal of Electronic Measurement & Instrument， 2013， 27（1）：1-7.

[11]ZHU Junfeng， HU Xiangyun， ZHANG Zuxun， et al. Hierarchical outlier detection for point cloud data using a density analysis method[J]. Acta Geodaetica Et Cartographica Sinica， 2015， 44（3）：282-291.

[12]WANG Xianze， LI Zhongke， MAI Yaqi， et al. Robust denoising of unorganized point clouds[C]//IEEE Conference Anthology， China： IEEE， 2013： 1-3.

[13]ZHANG Wangyu， DENG Bailin， ZHANG Juyong， et al. Guided mesh normal filtering[C]//Computer Graphics Forum. 2015， 34（7）： 23-34.