三維激光點(diǎn)云數(shù)據(jù)精簡(jiǎn)算法*

黃曉銘，楊 劍，陳 輝

(上海電力學(xué)院自動(dòng)化工程學(xué)院，上海 200090)

隨著科學(xué)技術(shù)的發(fā)展，三維激光掃描設(shè)備的精度逐漸得到提升，通過掃描幾乎能夠采集到原始模型表面完整的數(shù)據(jù).[1-2]但是，由于采集到的點(diǎn)云數(shù)據(jù)量大且密度高，如果直接對(duì)其進(jìn)行處理，必將降低后續(xù)三維重建的效率，影響重構(gòu)目標(biāo)表面的光滑性，致使重建效果欠佳.與此同時(shí)，龐大的數(shù)據(jù)量在存儲(chǔ)、顯示方面也會(huì)對(duì)計(jì)算機(jī)提出很高的要求，導(dǎo)致數(shù)據(jù)處理效率不高.因此，在保留點(diǎn)云數(shù)據(jù)細(xì)節(jié)特征和不影響模型重建精度的前提下，需要對(duì)海量數(shù)據(jù)進(jìn)行點(diǎn)云精簡(jiǎn)[3-4]，以達(dá)到去除冗余點(diǎn)和提高重建效率的目的.

1 激光點(diǎn)云數(shù)據(jù)精簡(jiǎn)算法的研究現(xiàn)狀

目前，國(guó)內(nèi)外學(xué)者對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行了大量的研究，提出了許多可行的點(diǎn)云精簡(jiǎn)算法.對(duì)于空間散亂點(diǎn)云，由于散亂點(diǎn)云數(shù)據(jù)之間沒有明顯的拓?fù)潢P(guān)系，如果對(duì)海量點(diǎn)云直接進(jìn)行處理，就會(huì)嚴(yán)重影響算法的運(yùn)行效率；因此應(yīng)先對(duì)采集到的點(diǎn)云數(shù)據(jù)建立合適的幾何拓?fù)潢P(guān)系以縮短精簡(jiǎn)時(shí)間.建立點(diǎn)云拓?fù)潢P(guān)系的方法主要有八叉樹法、空間均勻柵格劃分法和k-d樹法等[5-6]，流行的散亂點(diǎn)云數(shù)據(jù)精簡(jiǎn)算法有三角網(wǎng)格法、隨機(jī)采樣法、聚類法、迭代法、均勻網(wǎng)格法、非均勻網(wǎng)格法和曲率采樣法等[7-9].

1996年，D J Weir等[10]提出了包圍盒法，將所有的點(diǎn)云數(shù)據(jù)包含在最小空間長(zhǎng)方體中，根據(jù)設(shè)定的小包圍盒將長(zhǎng)方體劃分為大小相同的包圍盒，保留小包圍盒的中心點(diǎn)，刪除其余點(diǎn).該算法原理簡(jiǎn)單，易于實(shí)現(xiàn)，適用于均勻分布點(diǎn)云數(shù)據(jù)的精簡(jiǎn)，但中心點(diǎn)有可能并非原始點(diǎn)云數(shù)據(jù)，易造成細(xì)節(jié)特征的丟失.1997年，R R Martin等[11]提出了均勻網(wǎng)格法，將點(diǎn)云空間進(jìn)行了均勻網(wǎng)格劃分，只保留各網(wǎng)格的中值點(diǎn).該方法與包圍盒法類似，容易丟失特征點(diǎn)，不能保持原始模型的特征信息.2001年，K H Lee等[12]采用非均勻網(wǎng)格精簡(jiǎn)點(diǎn)云數(shù)據(jù)，在均勻網(wǎng)格劃分的基礎(chǔ)上，根據(jù)點(diǎn)云的法矢偏差值對(duì)均勻網(wǎng)格進(jìn)一步細(xì)分，即在特征區(qū)域劃分更多的網(wǎng)格，而非特征區(qū)域則相反.這使得特征區(qū)域能保留相對(duì)多的點(diǎn)，而非特征區(qū)域則保留較少的點(diǎn)，因此，與均勻網(wǎng)格法相比，該算法能較好地保留細(xì)節(jié)特征.2008年，N Dyn 等[13]通過構(gòu)造非負(fù)函數(shù)來衡量每一個(gè)點(diǎn)云數(shù)據(jù)的重要性，并用迭代的方法對(duì)點(diǎn)云進(jìn)行精簡(jiǎn).該方法取得了不錯(cuò)的精簡(jiǎn)效果，準(zhǔn)確度高，但計(jì)算量較大.2013年，H Benhabiles等[14]將聚類分析法和由粗到細(xì)策略相結(jié)合，提出了一種可以保留銳利邊緣點(diǎn)的快速點(diǎn)云精簡(jiǎn)算法.該算法與其他簡(jiǎn)化算法相比，很好地處理了銳利邊緣點(diǎn)的問題.

國(guó)內(nèi)研究學(xué)者也對(duì)精簡(jiǎn)算法進(jìn)行了大量研究.1999年，Chen Y H等[15]采用基于三角網(wǎng)格的點(diǎn)云精簡(jiǎn)算法，對(duì)采集到的點(diǎn)云數(shù)據(jù)進(jìn)行三角化處理，利用向量加權(quán)算法對(duì)三角網(wǎng)絡(luò)進(jìn)行冗余判定，并刪除冗余的網(wǎng)格以達(dá)到精簡(jiǎn)的目的.2004年，萬(wàn)軍等[16]根據(jù)平均點(diǎn)距對(duì)點(diǎn)云進(jìn)行精簡(jiǎn).該方法對(duì)特征點(diǎn)的識(shí)別度較差，容易丟失復(fù)雜區(qū)域的幾何特征.2007年，王宏濤等[17]采用八叉樹法對(duì)點(diǎn)云空間進(jìn)行劃分，只保留葉節(jié)點(diǎn)中最靠近重心的點(diǎn).該方法處理速度較快，但不能充分保留點(diǎn)云的特征點(diǎn).2008年，周波等[18]研究了基于八叉樹的非均勻網(wǎng)格法，但該算法不能完整保留邊界點(diǎn)和細(xì)節(jié)特征.2011年，Shi B Q等[19]提出了基于K均值聚類的自適應(yīng)點(diǎn)云精簡(jiǎn)算法.該算法能夠保證原始模型邊界的完整性且點(diǎn)云分布較為合理，但是對(duì)噪聲比較敏感.2015年，袁小翠等[20]根據(jù)點(diǎn)云的微分信息對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行K均值聚類，然后對(duì)點(diǎn)云空間進(jìn)行全局聚類，進(jìn)而以聚類中心點(diǎn)代替該類數(shù)據(jù)點(diǎn)來達(dá)到精簡(jiǎn)的目的.

然而，上述方法對(duì)點(diǎn)云進(jìn)行精簡(jiǎn)時(shí)未考慮點(diǎn)云特征問題，對(duì)點(diǎn)云的細(xì)節(jié)特征保留得不夠完整，無法很好地逼近點(diǎn)云原型，不適合具有復(fù)雜特征和多樣曲率的高密度散亂點(diǎn)云的數(shù)據(jù)精簡(jiǎn).[21]因此，近年來保持特征的精簡(jiǎn)算法較為流行.目前，對(duì)特征信息的判別主要依據(jù)曲率變化的趨勢(shì)，通過點(diǎn)云微分信息將點(diǎn)云數(shù)據(jù)劃分為特征區(qū)域和非特征區(qū)域[22-23]，根據(jù)不同區(qū)域的特點(diǎn)采用不同策略進(jìn)行精簡(jiǎn)，確保在精簡(jiǎn)的同時(shí)保留更多的模型細(xì)節(jié)特征.2006年，孫肖霞等[24]通過擬合最小二乘球來估算曲率，但該算法較為復(fù)雜,而且精簡(jiǎn)后的點(diǎn)云在曲率較小處易出現(xiàn)空白.2009年，劉濤等[25]在包圍盒法的基礎(chǔ)上提出一種曲率精簡(jiǎn)算法，該方法能很好地保留特征點(diǎn)，但在平坦區(qū)域容易產(chǎn)生空洞，不利于模型的三維重建.2010年，周煜等[21]結(jié)合八叉樹空間劃分法和平均曲率法，將點(diǎn)云模型包含在空間包圍盒內(nèi)并設(shè)定閾值，當(dāng)小包圍盒平均曲率大于閾值時(shí)細(xì)分包圍盒，反之保留曲率值最接近平均曲率值的點(diǎn)并刪除其余點(diǎn).該算法能很好地保留數(shù)據(jù)的細(xì)節(jié)特征，但計(jì)算量大，效率有待提高.2011年，P F Lee等[26]利用離散形態(tài)算子對(duì)點(diǎn)云模型進(jìn)行特征提取，可有效保留特征點(diǎn)，但易受噪聲干擾.2012年，朱煜等[27]根據(jù)點(diǎn)的空間主曲率對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行精簡(jiǎn)，取得了較好的精簡(jiǎn)效果，但主曲率的獲得需要對(duì)各點(diǎn)進(jìn)行二次曲面擬合，運(yùn)算過程耗時(shí)長(zhǎng)，且難以實(shí)現(xiàn)海量點(diǎn)云的精簡(jiǎn).葛源坤等[28]提出一種曲率精簡(jiǎn)算法，對(duì)空間進(jìn)行劃分并搜索各點(diǎn)的K鄰域，然后計(jì)算各點(diǎn)的曲率值，合理設(shè)置曲率閾值.該算法雖然能獲得較好的精簡(jiǎn)率，但是二次曲面擬合過程并不理想，不適用于包含豐富細(xì)節(jié)信息的點(diǎn)云模型.李鳳霞等[29]利用法向量夾角精簡(jiǎn)點(diǎn)云數(shù)據(jù)，得到了較好的精簡(jiǎn)效果，但該方法需要對(duì)點(diǎn)云中每個(gè)點(diǎn)進(jìn)行最小二乘擬合，計(jì)算效率低.2013年，陳璋雯等[30]采用模糊熵迭代法精簡(jiǎn)點(diǎn)云數(shù)據(jù)，有效地保留點(diǎn)云的細(xì)節(jié)特征，但涉及大量的曲率計(jì)算，耗時(shí)較大.2015年，Li H等[31]提出以點(diǎn)到局部平面的投影殘差來判定點(diǎn)云數(shù)據(jù)的保留與否，但該算法受噪聲的影響大，容易丟失點(diǎn)云模型中平滑區(qū)域的細(xì)節(jié)信息.2016年，楊秋翔等[32]以數(shù)據(jù)點(diǎn)主曲率的Hausdorff距離為依據(jù)提取點(diǎn)云數(shù)據(jù)特征點(diǎn)，該方法提高了簡(jiǎn)化效率，但數(shù)據(jù)點(diǎn)主曲率的Hausdorff距離不一定都相等，導(dǎo)致精簡(jiǎn)結(jié)果不均勻.此外，激光點(diǎn)云數(shù)據(jù)的精簡(jiǎn)算法還有很多種且各具優(yōu)缺點(diǎn).不同的精簡(jiǎn)算法適用于不同的場(chǎng)景，在工程實(shí)際中，應(yīng)根據(jù)需求來選擇合適的精簡(jiǎn)算法，以期得到符合工程要求的結(jié)果.

總結(jié)上述精簡(jiǎn)算法，將點(diǎn)云精簡(jiǎn)算法歸納為3類：一類是基于概率的精簡(jiǎn)法，如隨機(jī)采樣法等；二類是基于網(wǎng)格的精簡(jiǎn)法，如包圍盒法、三角網(wǎng)格法和均勻網(wǎng)格法等；三類是基于特征信息的精簡(jiǎn)法，如最小距離法、曲率精簡(jiǎn)法等.點(diǎn)云精簡(jiǎn)算法眾多，控制量不統(tǒng)一，缺乏定性和定量的比較.筆者在眾多方法中篩選出3種常用的方法，即包圍盒法、隨機(jī)采樣法和曲率精簡(jiǎn)法進(jìn)行性能比較.首先選取斯坦福大學(xué)提供的Bunny模型和三維重構(gòu)中常用的椅子模型為實(shí)驗(yàn)對(duì)象，然后在MATLAB中編程并控制其中的變量因素，最后對(duì)原始點(diǎn)云進(jìn)行精簡(jiǎn)處理，直觀比較輸出的精簡(jiǎn)結(jié)果，分析各種算法的優(yōu)劣性和適用性.

2 幾種典型的點(diǎn)云數(shù)據(jù)精簡(jiǎn)算法

2.1 包圍盒法

包圍盒法是一種傳統(tǒng)的點(diǎn)云數(shù)據(jù)精簡(jiǎn)算法，它的工作原理為：構(gòu)建一個(gè)包含所有點(diǎn)云數(shù)據(jù)的包圍盒，并將其分解成若干均勻大小的小包圍盒，選取最靠近中心的點(diǎn)來代替小包圍盒所有的點(diǎn)以達(dá)到精簡(jiǎn)點(diǎn)云數(shù)據(jù)的目的，并通過控制小包圍盒的大小來控制精簡(jiǎn)結(jié)果.該方法簡(jiǎn)單高效且容易實(shí)現(xiàn)，是一種簡(jiǎn)單的基于空間準(zhǔn)則的精簡(jiǎn)算法，對(duì)表面不復(fù)雜和曲率變化不大的物體的點(diǎn)云數(shù)據(jù)的精簡(jiǎn)很有效.精簡(jiǎn)后的點(diǎn)云比較均勻，能夠反映簡(jiǎn)單模型的輪廓特征，但是當(dāng)物體表面有大曲率曲面時(shí)，精簡(jiǎn)曲面將不能很好地保持原有的模型特征，也無法確保精簡(jiǎn)的精度，主要適用于模型表面的形狀相對(duì)簡(jiǎn)單且對(duì)精度要求不高的場(chǎng)合.

2.2 隨機(jī)采樣法

隨機(jī)采樣法的基本思路是：針對(duì)散亂的點(diǎn)云數(shù)據(jù)設(shè)計(jì)一個(gè)隨機(jī)函數(shù)，使其產(chǎn)生的隨機(jī)數(shù)能夠覆蓋點(diǎn)云分布的所有范圍，然后依據(jù)隨機(jī)數(shù)將點(diǎn)云數(shù)據(jù)中與之對(duì)應(yīng)的數(shù)據(jù)點(diǎn)以相等的概率予以刪除，直到點(diǎn)云數(shù)據(jù)中剩余的點(diǎn)數(shù)達(dá)到精簡(jiǎn)要求.該方法對(duì)于海量點(diǎn)云數(shù)據(jù)有較高的精簡(jiǎn)效率，實(shí)現(xiàn)過程簡(jiǎn)單高效，運(yùn)行速度快，但是沒有考慮到點(diǎn)云空間的具體特征和細(xì)節(jié)，容易丟失原始模型的空間幾何特征，而且隨機(jī)函數(shù)的隨機(jī)性導(dǎo)致每次運(yùn)行后的精簡(jiǎn)效果都不一致，從而點(diǎn)云數(shù)據(jù)的精簡(jiǎn)結(jié)果無法控制.因此，該方法在點(diǎn)云模型要求較高的實(shí)際應(yīng)用中有很大局限性，主要作為其他精簡(jiǎn)算法的補(bǔ)充方法，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行后續(xù)的精簡(jiǎn)操作.

2.3 曲率精簡(jiǎn)法

曲率精簡(jiǎn)法以數(shù)據(jù)點(diǎn)的曲率為依據(jù)，在曲率大的區(qū)域精簡(jiǎn)少量點(diǎn)，以保留足夠多的點(diǎn)來表達(dá)模型的幾何特征，而在曲率相對(duì)較小的區(qū)域精簡(jiǎn)較多點(diǎn)以減少數(shù)據(jù)點(diǎn)的冗余.這是因?yàn)辄c(diǎn)云模型的曲率大小對(duì)應(yīng)模型的幾何特征分布，表示點(diǎn)云模型的內(nèi)部屬性：對(duì)于曲率大的區(qū)域，模型表面的變化相對(duì)劇烈，特征比較明顯；而在曲率較小的區(qū)域，模型表面的變化相對(duì)平緩，特征相對(duì)不明顯.因此，該方法在刪除冗余數(shù)據(jù)的同時(shí)，能盡量保留點(diǎn)云模型的細(xì)節(jié)特征，實(shí)際應(yīng)用中可以采用反映曲率變化的曲面特征參數(shù)作為點(diǎn)云精簡(jiǎn)的判別準(zhǔn)則.相比其他點(diǎn)云精簡(jiǎn)算法，曲率精簡(jiǎn)法的優(yōu)點(diǎn)在于既能夠準(zhǔn)確地保留原始模型的細(xì)節(jié)特征信息，又能有效地減少冗余的數(shù)據(jù)點(diǎn)，但是該方法存在曲率計(jì)算過程較為復(fù)雜、算法運(yùn)行耗時(shí)長(zhǎng)和對(duì)計(jì)算機(jī)的性能要求高等缺點(diǎn).此外，在曲率較小的區(qū)域，該方法會(huì)刪除較多的數(shù)據(jù)點(diǎn)；在待刪除的數(shù)據(jù)點(diǎn)的選擇上，該方法并沒有遵循均勻精簡(jiǎn)的規(guī)則，會(huì)造成局部空洞現(xiàn)象.

3 實(shí)例分析

筆者對(duì)同一目標(biāo)點(diǎn)云分別使用包圍盒法、隨機(jī)采樣法和曲率精簡(jiǎn)法進(jìn)行精簡(jiǎn)，在MATLAB平臺(tái)上實(shí)現(xiàn)編程.椅子模型和Bunny模型的原始點(diǎn)云及其經(jīng)不同精簡(jiǎn)算法處理后的圖像如圖1所示，各種算法的結(jié)果比較列于表1.

圖1 2個(gè)模型的原始點(diǎn)云及其精簡(jiǎn)后的圖像Fig. 1 Original Point Cloud and Reduction Results of Two Models

模型組別點(diǎn)云個(gè)數(shù)精簡(jiǎn)率/%精簡(jiǎn)速度精簡(jiǎn)效果椅子原始點(diǎn)云 49 960包圍盒法 16 94466.08一般可作初步精簡(jiǎn)隨機(jī)采樣法16 98666.00快 需要解決特征點(diǎn)丟失問題曲率精簡(jiǎn)法16 36967.24慢 需要控制時(shí)間模型組別點(diǎn)云個(gè)數(shù)精簡(jiǎn)率/%精簡(jiǎn)速度精簡(jiǎn)效果Bunny原始點(diǎn)云 35 947包圍盒法 11 32568.50一般可作初步精簡(jiǎn)隨機(jī)采樣法11 50368.00快 需要解決特征點(diǎn)丟失問題曲率精簡(jiǎn)法12 09566.35慢 需要控制時(shí)間

從表1可以看出，在以上算法中，隨機(jī)采樣法速度最快而基于曲率的精簡(jiǎn)算法速度最慢，包圍盒法從時(shí)間效率來說介于兩者之間.在精簡(jiǎn)率相近的情況下，各算法都可以保持模型的整體樣貌，但有的喪失了一些重要的細(xì)節(jié)點(diǎn).從圖1可以看出：經(jīng)包圍盒法精簡(jiǎn)后，點(diǎn)云分布比較均勻，但在平坦區(qū)域還是存在很多的冗余信息，在曲率變化較大的區(qū)域表面特征丟失比較嚴(yán)重；經(jīng)隨機(jī)采樣法精簡(jiǎn)后，點(diǎn)云分布比較均勻，但不能很好地突出模型的幾何特征，細(xì)節(jié)丟失嚴(yán)重，精簡(jiǎn)效果的隨機(jī)性較大，不能很好地保留細(xì)節(jié)特征；經(jīng)曲率精簡(jiǎn)法精簡(jiǎn)后，在曲率大的地方點(diǎn)云比較密集，說明較好地去除了點(diǎn)云的冗余數(shù)據(jù)并有效地保留了點(diǎn)云細(xì)節(jié)特征，但因分布不均勻，點(diǎn)云在曲率較小處出現(xiàn)了空洞現(xiàn)象.

4 結(jié)語(yǔ)

筆者重點(diǎn)綜述了激光點(diǎn)云數(shù)據(jù)模型的精簡(jiǎn)算法，分析了點(diǎn)云精簡(jiǎn)算法的國(guó)內(nèi)外研究現(xiàn)狀，并對(duì)最常用的3種算法進(jìn)行了簡(jiǎn)單介紹及實(shí)驗(yàn)驗(yàn)證，分析了它們的優(yōu)缺點(diǎn).點(diǎn)云精簡(jiǎn)結(jié)果質(zhì)量的好壞決定著后續(xù)配準(zhǔn)及三維重建的效果，對(duì)點(diǎn)云精簡(jiǎn)算法質(zhì)量的衡量要綜合考慮精度、簡(jiǎn)度、速度和適用性4個(gè)方面.理想的點(diǎn)云精簡(jiǎn)算法是用最少的數(shù)據(jù)點(diǎn)表達(dá)出最重要的特征信息，并在這個(gè)過程中有較快的運(yùn)行速度.在實(shí)際應(yīng)用中，要求一個(gè)精簡(jiǎn)算法同時(shí)滿足所有要求是十分困難的，而且單純使用一種方法一般無法取得滿足實(shí)際要求的精簡(jiǎn)效果，因此對(duì)現(xiàn)有方法的改進(jìn)和融合是將來的研究方向.