李明磊，李廣云，宗文鵬

(1. 信息工程大學(xué)導(dǎo)航與空天目標(biāo)工程學(xué)院，河南 鄭州 450001； 2. 現(xiàn)代城市測(cè)繪國(guó)家測(cè)繪地理

信息局重點(diǎn)實(shí)驗(yàn)室，北京 100001)

Accurate and Fast Denoising Method of Laser-Scanned Point Clouds

LI Minglei，LI Guangyun，ZONG Wenpeng

?

激光掃描點(diǎn)云準(zhǔn)確快速去噪方法

李明磊1,2，李廣云1，宗文鵬1

(1. 信息工程大學(xué)導(dǎo)航與空天目標(biāo)工程學(xué)院，河南 鄭州 450001； 2. 現(xiàn)代城市測(cè)繪國(guó)家測(cè)繪地理

信息局重點(diǎn)實(shí)驗(yàn)室，北京 100001)

Accurate and Fast Denoising Method of Laser-Scanned Point Clouds

LI Minglei，LI Guangyun，ZONG Wenpeng

摘要：激光點(diǎn)云數(shù)據(jù)中孤點(diǎn)和離群點(diǎn)等噪聲的自動(dòng)去除方法是激光點(diǎn)云數(shù)據(jù)處理的研究熱點(diǎn)。本文針對(duì)現(xiàn)有孤點(diǎn)的平均點(diǎn)間距閾值探測(cè)法存在遠(yuǎn)距離點(diǎn)云誤判的問(wèn)題，對(duì)平均點(diǎn)間距附加距離權(quán)重后再根據(jù)閾值進(jìn)行了判斷；針對(duì)離群點(diǎn)的生長(zhǎng)探測(cè)法存在效率低的問(wèn)題，采用均勻八叉樹(shù)結(jié)構(gòu)以格網(wǎng)為單位進(jìn)行了生長(zhǎng)探測(cè)。試驗(yàn)證明了改進(jìn)方法的自適應(yīng)性和高效性。

關(guān)鍵詞：點(diǎn)云去噪；加權(quán)；區(qū)域生長(zhǎng)；八叉樹(shù)；格網(wǎng)探測(cè)

一、引言

測(cè)繪中也有“測(cè)不準(zhǔn)”的概念，指的即為測(cè)量中不可避免地包含誤差。地面三維激光掃描儀作為一種測(cè)量設(shè)備，測(cè)量結(jié)果中也不可避免地包含各種誤差[1]，其中一部分誤差表現(xiàn)出噪聲特性，它的存在影響整個(gè)點(diǎn)云數(shù)據(jù)的分析效率和精度，因此需要對(duì)其按照分布大小進(jìn)行針對(duì)性的去除或調(diào)整。三維激光掃描測(cè)量產(chǎn)生的噪聲具有多樣性[2-3]：主動(dòng)無(wú)接觸覆蓋式測(cè)量受環(huán)境干擾可能產(chǎn)生非測(cè)量目標(biāo)物體表面的無(wú)用數(shù)據(jù)和離群噪聲；物體表面的尖銳特征等使激光入射角劇變可能導(dǎo)致測(cè)量產(chǎn)生毛刺噪聲；無(wú)合作目標(biāo)的激光測(cè)距方式必然產(chǎn)生細(xì)小的隨機(jī)噪聲。

激光點(diǎn)云數(shù)據(jù)中的噪聲一般不能明確地知道是由哪種因素引起的，只能從直觀上予以區(qū)分。對(duì)于點(diǎn)云中一點(diǎn)Pg，如果其與最近點(diǎn)之間的距離遠(yuǎn)大于點(diǎn)云的平均點(diǎn)間距，則Pg點(diǎn)稱(chēng)為孤點(diǎn)；對(duì)于點(diǎn)云中一點(diǎn)Pl，如果按照某一距離閾值尋找其鄰近點(diǎn)時(shí)只能找到k個(gè)，而第k+1個(gè)最近點(diǎn)與Pl及其前k個(gè)最近點(diǎn)之間的距離都遠(yuǎn)大于距離閾值，則Pl及其k個(gè)最近點(diǎn)稱(chēng)為離群點(diǎn)，離群點(diǎn)與孤點(diǎn)的區(qū)別是離群點(diǎn)成簇出現(xiàn)，單個(gè)離群點(diǎn)即為孤點(diǎn)；對(duì)于點(diǎn)云中一點(diǎn)Ps，如果Ps距離其所在位置的點(diǎn)云表面并無(wú)孤立現(xiàn)象，但Ps的存在影響其所在局部表面的光滑性，則Ps稱(chēng)為毛刺點(diǎn)(不光順點(diǎn))。

在激光點(diǎn)云中，由于孤點(diǎn)和離群點(diǎn)等大噪聲點(diǎn)存在離群特性，一般作為去噪的研究對(duì)象比較容易去除。去噪原用于一維信號(hào)數(shù)據(jù)和二維圖像數(shù)據(jù)中對(duì)噪聲的處理，本文將點(diǎn)云中因?yàn)檎趽趸蚣す鈷呙璧娜采w性獲取的非測(cè)量目標(biāo)上的無(wú)用點(diǎn)等離群點(diǎn)、孤點(diǎn)等大噪聲的去除作為去噪的主要研究對(duì)象。

對(duì)于孤點(diǎn)的自動(dòng)去除，由于激光點(diǎn)云具有遠(yuǎn)近疏密程度不一致的特點(diǎn)，直接利用單個(gè)距離閾值不具有自適應(yīng)性；針對(duì)離群點(diǎn)的自動(dòng)剔除，基于點(diǎn)的生長(zhǎng)方式在離群點(diǎn)塊數(shù)較多時(shí)會(huì)因?yàn)橹匦逻x取種子點(diǎn)的次數(shù)過(guò)多而導(dǎo)致算法的效率過(guò)低。本文主要工作將針對(duì)上述問(wèn)題進(jìn)行展開(kāi)。

二、孤點(diǎn)的加權(quán)平均距離去除法

已有的孤點(diǎn)去除方法是將距離鄰近點(diǎn)之間的距離大于根據(jù)點(diǎn)云平均點(diǎn)間距設(shè)定的閾值的點(diǎn)作為孤點(diǎn)。這種方式可以通過(guò)閾值的有效設(shè)定識(shí)別孤點(diǎn)，但由于單站激光點(diǎn)云距離測(cè)站近處分布稠密而距離測(cè)站遠(yuǎn)處分布稀疏的特點(diǎn)，這種根據(jù)點(diǎn)云平均點(diǎn)間距設(shè)定閾值的方式可能會(huì)導(dǎo)致距離測(cè)站近的位置孤點(diǎn)不能被有效檢測(cè)出來(lái)，而距離測(cè)站遠(yuǎn)的位置被測(cè)物表面點(diǎn)云也被誤作為孤點(diǎn)。

為解決上述問(wèn)題，本文在計(jì)算點(diǎn)云加權(quán)平均點(diǎn)間距時(shí)將各點(diǎn)距離其k個(gè)鄰近點(diǎn)的平均距離(點(diǎn)間距)除以點(diǎn)距離坐標(biāo)原點(diǎn)(測(cè)站點(diǎn))的距離，相當(dāng)于將所有點(diǎn)的點(diǎn)間距歸算到單位距離(距測(cè)站點(diǎn)距離為1)處的點(diǎn)間距；在孤點(diǎn)判定時(shí)根據(jù)極限誤差定義[9]以3倍加權(quán)平均點(diǎn)間距為閾值，將加權(quán)點(diǎn)間距大于閾值的點(diǎn)作為孤點(diǎn)去除。

三、離群點(diǎn)的格網(wǎng)探測(cè)法

為解決以點(diǎn)為單位的按照平均點(diǎn)間距生長(zhǎng)的方式在離群點(diǎn)塊數(shù)較多時(shí)效率低的問(wèn)題，本文利用均勻八叉樹(shù)[10-11]采用格網(wǎng)生長(zhǎng)代替點(diǎn)生長(zhǎng)，以八叉樹(shù)節(jié)點(diǎn)為單位進(jìn)行生長(zhǎng)尋找數(shù)據(jù)塊的邊界，從而確定每個(gè)數(shù)據(jù)塊的點(diǎn)的個(gè)數(shù)，最終將點(diǎn)數(shù)少于某一閾值的數(shù)據(jù)塊作為離群點(diǎn)。具體思路如下：

1) 設(shè)定距離閾值(可根據(jù)平均點(diǎn)間距設(shè)定，也可根據(jù)需要按照掃描點(diǎn)間距設(shè)定)，利用均勻八叉樹(shù)以距離閾值為劃分終止條件將點(diǎn)云分割。

2) 由于均勻八叉樹(shù)的特點(diǎn)，距離測(cè)站過(guò)遠(yuǎn)的位置如果點(diǎn)間距大于距離閾值(一般為非關(guān)注區(qū)域)，會(huì)產(chǎn)生大量?jī)H包含一個(gè)點(diǎn)的節(jié)點(diǎn)，因此為了提高節(jié)點(diǎn)生長(zhǎng)效率，先對(duì)僅包含一個(gè)點(diǎn)的節(jié)點(diǎn)進(jìn)行處理，如果節(jié)點(diǎn)僅包含一個(gè)點(diǎn)并且節(jié)點(diǎn)孤立(鄰近26個(gè)節(jié)點(diǎn)都為空節(jié)點(diǎn))，則直接標(biāo)記此節(jié)點(diǎn)包含的點(diǎn)為離群點(diǎn)，標(biāo)記此節(jié)點(diǎn)為已探測(cè)過(guò)節(jié)點(diǎn)。

3) 以第1個(gè)未被標(biāo)記的點(diǎn)所在節(jié)點(diǎn)(或者編號(hào)最接近0的節(jié)點(diǎn))為種子節(jié)點(diǎn)，逐層生長(zhǎng)并標(biāo)記被生長(zhǎng)節(jié)點(diǎn)，以各層被生長(zhǎng)節(jié)點(diǎn)為新的種子節(jié)點(diǎn)繼續(xù)生長(zhǎng)，直至生長(zhǎng)過(guò)程遇到被生長(zhǎng)節(jié)點(diǎn)都為空節(jié)點(diǎn)時(shí)(圖1中兩塊有色區(qū)域的隔離方式，無(wú)色區(qū)域表示空格網(wǎng))，當(dāng)次生長(zhǎng)過(guò)程終止，記錄此次生長(zhǎng)過(guò)程中被生長(zhǎng)的節(jié)點(diǎn)所包含的點(diǎn)為同一個(gè)數(shù)據(jù)塊。如果當(dāng)前數(shù)據(jù)塊生長(zhǎng)結(jié)束后點(diǎn)的個(gè)數(shù)小于閾值，將當(dāng)前數(shù)據(jù)塊標(biāo)記為離群點(diǎn)。

圖1　格網(wǎng)分塊生長(zhǎng)示意圖

4) 尋找下一個(gè)尚未被標(biāo)記的節(jié)點(diǎn)作為種子節(jié)點(diǎn)繼續(xù)生長(zhǎng)，探測(cè)其所在的整個(gè)數(shù)據(jù)塊，至所有節(jié)點(diǎn)都被標(biāo)記時(shí)整個(gè)離群點(diǎn)探測(cè)過(guò)程終止。

從以上過(guò)程可知，格網(wǎng)探測(cè)法可以避免以點(diǎn)為單位的生長(zhǎng)探測(cè)過(guò)程中點(diǎn)間距離的計(jì)算，并且以格網(wǎng)節(jié)點(diǎn)為單位的生長(zhǎng)可以大大減少生長(zhǎng)次數(shù)，提高離群點(diǎn)的探測(cè)效率。

四、試驗(yàn)驗(yàn)證

為驗(yàn)證本節(jié)去噪方法的有效性，利用實(shí)驗(yàn)室單站掃描的原始點(diǎn)云進(jìn)行去噪試驗(yàn)。點(diǎn)云數(shù)據(jù)包含窗戶(hù)透射得到的室外樹(shù)木建筑等離群噪聲共3 683 546個(gè)點(diǎn)。

圖2為利用平局距離法設(shè)定距離閾值為3倍平均點(diǎn)間距時(shí)孤點(diǎn)探測(cè)的結(jié)果，選框內(nèi)墻角區(qū)域即為固定距離閾值導(dǎo)致的誤判情況，而離測(cè)站較遠(yuǎn)的室外建筑墻面由于數(shù)據(jù)較稀疏被完全識(shí)別為孤點(diǎn)。

圖2　平均距離法孤點(diǎn)檢測(cè)

圖3為利用加權(quán)平均距離法設(shè)定距離閾值為3倍平均點(diǎn)間距時(shí)孤點(diǎn)識(shí)別的結(jié)果。通過(guò)與圖2結(jié)果的對(duì)比可發(fā)現(xiàn)，墻角處孤點(diǎn)的誤判得到一定改善，室外樹(shù)木主要是樹(shù)葉點(diǎn)被識(shí)別為孤點(diǎn)，而室外建筑物也沒(méi)有因?yàn)辄c(diǎn)分布稀疏而被識(shí)別為孤點(diǎn)，由此說(shuō)明根據(jù)入射距離加權(quán)的平均距離閾值具有一定的自適應(yīng)性。

圖3　加權(quán)平均距離法孤點(diǎn)檢測(cè)

圖4為利用生長(zhǎng)方式以5cm點(diǎn)間距為距離閾值(5cm以?xún)?nèi)點(diǎn)間距的點(diǎn)作為同一塊數(shù)據(jù)以?xún)?nèi)的點(diǎn))，以1000個(gè)點(diǎn)為點(diǎn)數(shù)閾值(生長(zhǎng)后數(shù)據(jù)塊中點(diǎn)個(gè)數(shù)小于1000時(shí)將其作為離群點(diǎn))進(jìn)行離群點(diǎn)判別的結(jié)果。

圖4　生長(zhǎng)算法離群點(diǎn)檢測(cè)(用時(shí)109 342 ms)

圖5為同樣閾值的均勻八叉樹(shù)格網(wǎng)探測(cè)結(jié)果。兩種方式得到的離群點(diǎn)判定結(jié)果比較接近，都只保留了室內(nèi)點(diǎn)，但格網(wǎng)探測(cè)法在消耗時(shí)間上比生長(zhǎng)算法有較大優(yōu)勢(shì)。

圖5　格網(wǎng)探測(cè)法離群點(diǎn)檢測(cè)(用時(shí)11 471 ms)

為驗(yàn)證算法對(duì)細(xì)小孤點(diǎn)和離群點(diǎn)的探測(cè)能力，對(duì)如圖6所示的兩站拼接后的正面包含大量邊緣噪聲(掃描測(cè)量時(shí)由于粘貼了攝影測(cè)量回光標(biāo)志)、背面包含大入射角噪聲(單站測(cè)量時(shí)每次主測(cè)一半，另一半為大入射角)的雷達(dá)罩點(diǎn)云進(jìn)行去噪試驗(yàn)。

將圖6所示點(diǎn)云中識(shí)別的噪聲加色顯示，效果如圖7所示，基本可以去除大的邊緣噪聲。

五、結(jié)束語(yǔ)

針對(duì)孤點(diǎn)的平均距離閾值去除方法存在的不足，采用加權(quán)平均距離方式適應(yīng)激光掃描測(cè)量獲取的點(diǎn)云數(shù)據(jù)的分布特點(diǎn)，可在一定程度上避免遠(yuǎn)距離目標(biāo)表面點(diǎn)云的誤判，具有一定的自適應(yīng)性；對(duì)于以點(diǎn)為單位進(jìn)行生長(zhǎng)探測(cè)離群點(diǎn)方式存在的效率低問(wèn)題，采用基于均勻八叉樹(shù)的格網(wǎng)的離群點(diǎn)探測(cè)法、以格網(wǎng)為單位進(jìn)行生長(zhǎng)，可以提高離群點(diǎn)探測(cè)的效率。

圖6　包含邊緣噪聲的雷達(dá)罩點(diǎn)云

圖7　格網(wǎng)探測(cè)法去噪效果

參考文獻(xiàn)：

[1]GROSSM,DFISTERH.Point-basedGraphics[M].Berlin:MorganKaufmannPublishers, 2007.

[2]李自勤, 李琦, 王騏. 由統(tǒng)計(jì)特性分析激光主動(dòng)成像系統(tǒng)圖像的噪聲性質(zhì)[J]. 中國(guó)激光, 2004, 31(9): 1081-1085.

[3]孫正林. 三維激光掃描點(diǎn)云數(shù)據(jù)濾波方法研究[D].長(zhǎng)沙: 中南大學(xué), 2011.

[4]FRANKY,CHENGSX.AutomaticSeededRegionGrowingforColorImageSegmentation[J].ImageandVisionComputing, 2005, 23(10): 877-886.

[5]郝慧麗, 劉先勇. 含噪點(diǎn)云預(yù)處理技術(shù)研究[J]. 微型機(jī)與應(yīng)用，2012, 31(12): 68-70.

[6]張樹(shù)森, 伏利, 董剛. 離群點(diǎn)刪除算法的研究[J]. 裝備制造技術(shù)，2008(7): 13-15.

[7]聶建輝. 自定位實(shí)物數(shù)字化技術(shù)研究[D]. 大連: 大連海事大學(xué), 2012.

[8]李青蒙. 激光掃描點(diǎn)云處理技術(shù)研究[D]. 大連: 大連海事大學(xué), 2013.

[9]隋立芬, 宋力杰, 柴洪洲. 誤差理論與測(cè)量平差基礎(chǔ)[M]. 北京: 測(cè)繪出版社, 2010.

[10]馬磊, 彭國(guó)華, 耿東芳. 基于八叉樹(shù)的海量測(cè)量數(shù)據(jù)的非均勻簡(jiǎn)化[J]. 計(jì)算機(jī)應(yīng)用，2007, 27(8): 2027-2029.

[11]張會(huì)霞. 基于八叉樹(shù)的點(diǎn)云數(shù)據(jù)的組織與可視化[J]. 太原師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2011, 10(3): 128-132.引文格式： 陳華，鄧喀中，張以文，等. 結(jié)合SIFT和RANSAC算法的InSAR影像配準(zhǔn)[J].測(cè)繪通報(bào)，2015(12)：30-33.DOI:10.13474/j.cnki.11-2246.2015.371

作者簡(jiǎn)介：李明磊(1989—)，男，博士生，主要從事激光點(diǎn)云數(shù)據(jù)處理、精密工程測(cè)量等方面的研究工作。E-mail：mingleili_xd@163.com

基金項(xiàng)目：國(guó)家自然科學(xué)基金(41274014)；航天器精密測(cè)量基金(2014-3；2014-5)；現(xiàn)代城市測(cè)繪國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(20131204WY)

收稿日期：2014-11-22

中圖分類(lèi)號(hào)：P232

文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：0494-0911(2015)12-0027-03

引文格式： 李明磊，李廣云，宗文鵬. 激光掃描點(diǎn)云準(zhǔn)確快速去噪方法[J].測(cè)繪通報(bào)，2015(12)：27-29.DOI:10.13474/j.cnki.11-2246.2015.370