基于APOCS的點(diǎn)云去噪算法

李剛森　程遠(yuǎn)志

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

關(guān)鍵詞：點(diǎn)云； 去噪； 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

引言

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

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

1 相關(guān)技術(shù)

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

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

2 算法詳述

2.1 算法概況

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

2.2 法向量的濾波算法

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

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

這里N是參考點(diǎn)的數(shù)量。閾值的選取依據(jù)計(jì)算得到的相關(guān)性自適應(yīng)選擇，一般會選擇相關(guān)性分布的一個(gè)斷層作為閾值，也就是閾值分開的兩個(gè)集合中的點(diǎn)相關(guān)性差距較大。

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

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

4 結(jié)束語

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

參考文獻(xiàn)

[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.