李海鵬，徐 丹，付宇婷，柳雁安，張婷婷

基于FPFH特征提取的散亂點(diǎn)云精簡(jiǎn)算法

李海鵬，徐 丹，付宇婷，柳雁安，張婷婷

(云南大學(xué)信息學(xué)院，云南 昆明 650500)

針對(duì)原始點(diǎn)云模型中存在大量冗余數(shù)據(jù)問(wèn)題，提出一種基于快速點(diǎn)特征直方圖(FPFH)特征提取的點(diǎn)云精簡(jiǎn)算法，有效兼顧了特征信息保留和整體完整性。算法首先查找并保留原始模型的邊緣點(diǎn)；然后計(jì)算非邊緣點(diǎn)的FPFH值，由此得到點(diǎn)云的特征值，并進(jìn)行排序且劃分出特征區(qū)域和非特征區(qū)域，保留特征區(qū)域內(nèi)的點(diǎn)；最后將非特征區(qū)域劃分為個(gè)子區(qū)間，對(duì)每個(gè)子區(qū)間用改進(jìn)的最遠(yuǎn)點(diǎn)采樣算法進(jìn)行采樣。將該算法與最遠(yuǎn)點(diǎn)采樣算法、非均勻網(wǎng)格法、k-means算法和自適應(yīng)曲率熵算法進(jìn)行對(duì)比實(shí)驗(yàn)，并用標(biāo)準(zhǔn)化信息熵評(píng)價(jià)方法對(duì)精簡(jiǎn)后的點(diǎn)云進(jìn)行評(píng)價(jià)，實(shí)驗(yàn)表明其優(yōu)于其他精簡(jiǎn)算法。此外，可視化結(jié)果也表明，該算法能夠在保證精簡(jiǎn)模型完整性的同時(shí)，較好地保留住點(diǎn)云大部分特征信息。

點(diǎn)云精簡(jiǎn)；快速點(diǎn)特征直方圖；最遠(yuǎn)點(diǎn)采樣；邊界保留；標(biāo)準(zhǔn)化信息熵

相比于二維圖像，點(diǎn)云包含著更多的幾何信息，被廣泛應(yīng)用于文物保護(hù)、測(cè)繪、自動(dòng)駕駛等領(lǐng)域。隨著激光掃描技術(shù)的不斷發(fā)展，點(diǎn)云獲取的速度越來(lái)越快，數(shù)據(jù)量也越來(lái)越大。點(diǎn)云數(shù)據(jù)中有著豐富的細(xì)節(jié)特征，也包含著大量的冗余數(shù)據(jù)點(diǎn)，如果不進(jìn)行數(shù)據(jù)精簡(jiǎn)預(yù)處理，不僅不能給后續(xù)的處理和模型重建帶來(lái)很高的精度和收益，反而會(huì)降低數(shù)據(jù)處理效率。因此，在盡可能保留模型細(xì)節(jié)特征與保證模型完整無(wú)空洞的前提下，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行精簡(jiǎn)處理是必不可少的。

國(guó)內(nèi)外研究學(xué)者針對(duì)點(diǎn)云精簡(jiǎn)問(wèn)題作了很多研究，傳統(tǒng)的點(diǎn)云精簡(jiǎn)算法主要有：隨機(jī)采樣法[1]、均勻網(wǎng)格法[2]、包圍盒法[3-4]、非均勻網(wǎng)格法[5]、曲率采樣法[6]和最遠(yuǎn)點(diǎn)采樣法(farthest point sampling，F(xiàn)PS)[7]等。其中有代表性的均勻網(wǎng)格法首先查找點(diǎn)云模型的最小包圍盒，然后將包圍盒劃分為一定大小的立方體，計(jì)算立方體的中值點(diǎn)，用該中值點(diǎn)來(lái)表示落在其內(nèi)的所有點(diǎn)。該方法采樣效率較高，采樣點(diǎn)分布均勻，但未考慮點(diǎn)云的特征信息。非均勻網(wǎng)格法是均勻網(wǎng)格法的改進(jìn)，首先查找點(diǎn)云模型的最小包圍盒，然后進(jìn)行非均勻細(xì)化，劃分為多個(gè)小立方體，并計(jì)算其中值點(diǎn)，用以代表包含在其內(nèi)的所有點(diǎn)。該方法能夠在一定程度上保留模型的特征信息，但能夠保留的特征信息有限。

近年來(lái)，很多學(xué)者基于k-means聚類、信息熵等方法進(jìn)行點(diǎn)云精簡(jiǎn)處理研究。文獻(xiàn)[8-11]均分別基于k-means聚類算法設(shè)計(jì)了相關(guān)的點(diǎn)云精簡(jiǎn)方法。其基本思想是利用k-means算法對(duì)點(diǎn)云進(jìn)行聚類，然后再對(duì)每個(gè)簇進(jìn)行精簡(jiǎn)，保留特征強(qiáng)度大的點(diǎn)，如文獻(xiàn)[8]利用k-means聚類將點(diǎn)云模型劃分為多個(gè)簇，并計(jì)算每個(gè)簇中的均方根曲率及均方根曲率平均值，刪去低于平均值的曲率點(diǎn)。此類方法對(duì)特征點(diǎn)的保留效果較好，但算法的時(shí)間復(fù)雜度較高，而且對(duì)特征強(qiáng)度小的點(diǎn)采樣不足，精簡(jiǎn)后的模型也容易出現(xiàn)一些小的孔洞。WANG等[12]提出一種基于自適應(yīng)曲率熵的點(diǎn)云簡(jiǎn)化方法，先按一定比例提取曲率較大的點(diǎn)構(gòu)造初始點(diǎn)云邊界，再使用二分聚類算法對(duì)點(diǎn)云進(jìn)行聚類；然后基于自適應(yīng)隨機(jī)算法對(duì)每個(gè)聚類點(diǎn)云進(jìn)行初步精簡(jiǎn)，再計(jì)算每個(gè)聚類點(diǎn)云的曲率熵，并進(jìn)行二次精簡(jiǎn)；最后，將提取到的點(diǎn)云邊界和精簡(jiǎn)后的點(diǎn)云組成最終的精簡(jiǎn)結(jié)果。該算法能夠保證模型邊緣較為完整，保留較多特征點(diǎn)，但仍易出現(xiàn)孔洞，且計(jì)算曲率熵的時(shí)間成本較大。ZHANG等[13]定義了3種簡(jiǎn)化熵：尺度保持熵、輪廓保持熵和曲線保持熵，并根據(jù)熵值來(lái)進(jìn)行精簡(jiǎn)。XUAN等[14]利用法向角度和局部熵來(lái)評(píng)價(jià)點(diǎn)的重要性，通過(guò)移除最不重要的點(diǎn)并逐步更新法向量和重要性值來(lái)進(jìn)行點(diǎn)云精簡(jiǎn)處理。此外，SHOAIB等[15]利用分形氣泡算法進(jìn)行點(diǎn)云簡(jiǎn)化。QI等[16]采用圖信號(hào)處理的點(diǎn)云精簡(jiǎn)算法，較好地保留了特征信息。

傳統(tǒng)方法大多更側(cè)重于對(duì)整體完整性的處理，計(jì)算效率高，但對(duì)特征點(diǎn)的保留不足；基于k-means的方法能夠較好地保留特征點(diǎn)，但對(duì)整體的完整性處理不足，在特征區(qū)域附近容易出現(xiàn)許多孔洞，尤其是處理大規(guī)模點(diǎn)云時(shí)精簡(jiǎn)效果并不佳，而且計(jì)算效率較低。針對(duì)上述問(wèn)題，本文提出了一種基于FPFH特征保持的點(diǎn)云精簡(jiǎn)算法，首先對(duì)點(diǎn)云模型進(jìn)行邊界查找，并保留模型的邊界點(diǎn)；對(duì)非分界點(diǎn)利用快速點(diǎn)特征直方圖進(jìn)行特征值計(jì)算，并進(jìn)行排序和劃分，劃分出特征點(diǎn)和非特征點(diǎn)；對(duì)非特征點(diǎn)利用改進(jìn)的最遠(yuǎn)點(diǎn)采樣算法進(jìn)行采樣。

1 本文方法

1.1 邊界查找

對(duì)點(diǎn)云來(lái)說(shuō)，邊界輪廓是非常重要的一類特征。對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行邊界查找和保留就是為了使邊緣特征能夠得到最大程度地保留，保證邊界的完整性。

對(duì)點(diǎn)云模型邊界的查找，首先要構(gòu)建k-d樹(shù)，然后搜索k-d樹(shù)并尋找鄰近點(diǎn)[17]。采用最小二乘法對(duì)提取的近鄰點(diǎn)進(jìn)行平面擬合，將鄰域點(diǎn)集中的點(diǎn)投影到擬合平面上。再對(duì)擬合平面上的投影點(diǎn)進(jìn)行向量構(gòu)建，找出2個(gè)相鄰向量之間的夾角。最后根據(jù)夾角的大小確定邊界點(diǎn)。k-d樹(shù)的構(gòu)建是一個(gè)遞歸的過(guò)程，首先計(jì)算每個(gè)維度的方差，根據(jù)方差最大維度的中值將數(shù)據(jù)劃分為2個(gè)子集，以該中值為根節(jié)點(diǎn)構(gòu)建出左右子樹(shù)，重復(fù)該過(guò)程直至不能劃分為止。對(duì)于每個(gè)采樣點(diǎn)，用最近鄰搜索算法搜索k-d樹(shù)，找到該采樣點(diǎn)的近鄰點(diǎn)。以最小二乘法擬合切平面，并將采樣點(diǎn)和近鄰點(diǎn)投影到切平面上，以采樣點(diǎn)的投影點(diǎn)為起點(diǎn)，近鄰點(diǎn)的投影點(diǎn)為終點(diǎn)定義向量，并任選一個(gè)向量作為參考向量，將參考向量與切平面法線作外積得到向量，再分別求其他向量與參考向量和向量的夾角，根據(jù)這些夾角值求解得到最大夾角，當(dāng)最大夾角大于角度閾值時(shí)即可認(rèn)為該點(diǎn)為邊界點(diǎn)[18]，角度閾值一般取π/2。圖1為在不同閾值下兔子模型的邊界查找結(jié)果。

圖1 邊界查找示意圖(紅色點(diǎn)為查找到的邊界點(diǎn))

1.2 快速點(diǎn)特征直方圖

點(diǎn)云的曲率和法線可以較好描述點(diǎn)云的幾何特征，但僅能表示單點(diǎn)特征，無(wú)法從中獲取太多信息。相比之下，點(diǎn)特征直方圖(point feature histograms，PFH)[19-20]就能較好描述采樣點(diǎn)與其鄰域內(nèi)點(diǎn)之間的關(guān)系。要得到采樣點(diǎn)p的特征直方圖，首先要找到該點(diǎn)鄰域內(nèi)的其余點(diǎn)，如圖2(a)所示，計(jì)算這些點(diǎn)兩兩之間的關(guān)系(圖中黑色實(shí)線表示所連接的2點(diǎn)需要進(jìn)行一次法線偏差關(guān)系計(jì)算)。要計(jì)算圖2(b)的點(diǎn)p和p，首先以點(diǎn)p的法線作為坐標(biāo)軸，然后用坐標(biāo)軸與點(diǎn)p到點(diǎn)p方向的單位向量作外積得到坐標(biāo)軸，再將坐標(biāo)軸與作外積得到坐標(biāo)軸，由此完成以點(diǎn)p為原點(diǎn)定義一個(gè)局部坐標(biāo)系。

將局部坐標(biāo)系平移到點(diǎn)p，設(shè)p的法線與坐標(biāo)軸的夾角的余弦值為，與點(diǎn)p和p連線的夾角余弦值為，在平面的投影?與坐標(biāo)軸的夾角為，2點(diǎn)的歐氏距離為，則四元組<,,,>的計(jì)算式[21]為

用坐標(biāo)軸與作內(nèi)積得到夾角余弦值，用坐標(biāo)軸與點(diǎn)p到點(diǎn)p方向的單位向量作內(nèi)積得到夾角余弦值。對(duì)于的計(jì)算，有如下定義[21]

將四元組中的每個(gè)特征值都劃分成個(gè)子區(qū)間，統(tǒng)計(jì)落在每個(gè)子區(qū)間內(nèi)的點(diǎn)的個(gè)數(shù)并進(jìn)行歸一化處理，即可得到點(diǎn)特征直方圖PFH。

由于PFH的時(shí)間復(fù)雜度為(2)，無(wú)法滿足實(shí)時(shí)性要求，RUSU等[22]提出了快速點(diǎn)特征直方圖(fast point feature histograms, FPFH)，將時(shí)間復(fù)雜度降為()。圖3為FPFH的計(jì)算區(qū)域，首先計(jì)算點(diǎn)p與其鄰域內(nèi)其他點(diǎn)之間的一個(gè)三元組<,,>，將該步計(jì)算記為簡(jiǎn)單點(diǎn)特征直方圖(simplified point feature histogram, SPFH)，然后重新確定每個(gè)點(diǎn)的鄰域，對(duì)每個(gè)點(diǎn)均計(jì)算一次SPFH值，最后根據(jù)這些的SPFH值來(lái)計(jì)算p的FPFH，即

其中，(p)為點(diǎn)p的FPFH值；(p)和(p)分別為點(diǎn)p和p的SPFH值；ω為權(quán)重，一般取點(diǎn)p到點(diǎn)p之間的距離值。FPFH只計(jì)算點(diǎn)p與其鄰域內(nèi)其他點(diǎn)的對(duì)應(yīng)關(guān)系，如圖3所示，只有一些重要的點(diǎn)對(duì)被計(jì)算了2次(圖中黑色粗實(shí)線)，其余的點(diǎn)對(duì)只計(jì)算一次(圖中黑色細(xì)實(shí)線)。

點(diǎn)云的特征點(diǎn)是指能夠反映點(diǎn)云基本幾何形狀，對(duì)于描述點(diǎn)云的外觀具有關(guān)鍵性作用的點(diǎn)，而這些特征點(diǎn)一般位于模型邊緣或模型幾何形狀突變的區(qū)域，這些區(qū)域內(nèi)點(diǎn)的法線朝向均比較散亂。如圖4所示，在平緩部分(左側(cè)框點(diǎn))，鄰域內(nèi)的點(diǎn)的法線方向基本一致，故直方圖集中在同一個(gè)子區(qū)間內(nèi)；在特征明顯部位(右側(cè)框點(diǎn))，鄰域點(diǎn)的法線朝向散亂，直方圖統(tǒng)計(jì)數(shù)據(jù)較為分散。

圖3 FPFH計(jì)算區(qū)域示意圖

圖4 FPFH計(jì)算結(jié)果示意圖((a)非特征點(diǎn)FPFH計(jì)算結(jié)果結(jié)果；(b)特征點(diǎn)FPFH計(jì)算結(jié)果)

若直接用直方圖來(lái)進(jìn)行點(diǎn)云分類難以操作，每個(gè)點(diǎn)的直方圖均包含3個(gè)特征元素的總計(jì)33個(gè)統(tǒng)計(jì)值(Point Cloud Library默認(rèn)將每個(gè)特征元素劃分為11個(gè)子區(qū)間進(jìn)行統(tǒng)計(jì))。故本文首先將該直方圖逆向拆分為3個(gè)子直方圖，再分別計(jì)算每個(gè)子直方圖的標(biāo)準(zhǔn)差，以最大標(biāo)準(zhǔn)差來(lái)描述直方圖分布情況，這樣既能夠較好地描述直方圖的統(tǒng)計(jì)信息，又便于對(duì)點(diǎn)的特征強(qiáng)度進(jìn)行評(píng)價(jià)，從而有效判別特征點(diǎn)和非特征點(diǎn)。

1.3 最遠(yuǎn)點(diǎn)采樣算法(FPS)

FPS[7]是一種較為常見(jiàn)的采樣算法，其計(jì)算流程如圖5所示，具體步驟為：

步驟1.從原始數(shù)據(jù)中隨機(jī)選取一個(gè)點(diǎn)0作為起始點(diǎn)，依次與剩余的–1個(gè)點(diǎn)計(jì)算距離并存入數(shù)組中，選取距離最遠(yuǎn)的點(diǎn)1加入到采樣點(diǎn)集={-0,1}中。

步驟2.選取第個(gè)點(diǎn)時(shí)，計(jì)算采樣點(diǎn)集中每一個(gè)點(diǎn)到所有點(diǎn)(非點(diǎn))的距離，選取距離最小值作為非點(diǎn)到點(diǎn)集的距離存入數(shù)組中。

步驟3.從中選取距離值最大的點(diǎn)加入到采樣點(diǎn)集中。

圖5 FPS算法示意圖

步驟4.=+1，重復(fù)步驟2和步驟3，直到采集到的點(diǎn)云數(shù)達(dá)到目標(biāo)數(shù)量為止。

采樣FPS算法后的點(diǎn)分布較為均勻，但每次選點(diǎn)都要計(jì)算一次與所有點(diǎn)的距離，時(shí)間復(fù)雜度接近于(2)，因此大多數(shù)學(xué)者采用FPS的改進(jìn)算法來(lái)進(jìn)行研究學(xué)習(xí)[23-26]。本文提出的改進(jìn)算法，每次采樣前先采個(gè)點(diǎn)，從中選出最遠(yuǎn)的點(diǎn)作為采樣點(diǎn)，這樣既能夠選出位置相對(duì)較遠(yuǎn)的點(diǎn)，同時(shí)也提高了算法的計(jì)算效率。

1.4 標(biāo)準(zhǔn)化信息熵

信息熵[27]是一個(gè)重要的熵概念，含義非常豐富。其可用于描述點(diǎn)云的特征信息，某點(diǎn)的熵值越大，表明該點(diǎn)的信息量越大，整體的信息熵值越高，包含的信息越多，對(duì)物體的特征表達(dá)就越準(zhǔn)確[28]。某點(diǎn)的信息熵為

其中，E為點(diǎn)的熵值；p和p分別為和點(diǎn)的曲率概率分布，點(diǎn)是點(diǎn)的鄰域內(nèi)的點(diǎn)；C為點(diǎn)的平均曲率；為點(diǎn)鄰域內(nèi)點(diǎn)的個(gè)數(shù)。則整體的熵值為

為了消除量綱的影響，本文對(duì)每個(gè)點(diǎn)的熵值進(jìn)行了標(biāo)準(zhǔn)化處理。俞立平等[29]通過(guò)研究表明，現(xiàn)有的標(biāo)準(zhǔn)化方法，如極大值標(biāo)準(zhǔn)化、極差標(biāo)準(zhǔn)化、功效系數(shù)法等，均不具備評(píng)價(jià)功能，而sigmoid標(biāo)準(zhǔn)化方法具有評(píng)價(jià)功能，故對(duì)式(7)進(jìn)行了標(biāo)準(zhǔn)化處理后可得

最后，計(jì)算得到信息熵值，即

其中，為整體熵值；為點(diǎn)云數(shù)。

2 算法流程

本文算法得到的采樣點(diǎn)集由邊界點(diǎn)、特征點(diǎn)和非特征點(diǎn)3部分組成，具體步驟如下：

輸入：點(diǎn)集={(1,1,1), (2,2,2),···, (x,y,z)}；鄰域；精簡(jiǎn)率；閾值；子區(qū)間數(shù)。

輸出：精簡(jiǎn)后的點(diǎn)集。

步驟1.邊界保留。輸入點(diǎn)云數(shù)據(jù)，計(jì)算每個(gè)點(diǎn)的法線，根據(jù)法線和鄰域?qū)ふ疫吔琰c(diǎn)，將邊界點(diǎn)存入點(diǎn)集中。

步驟2.特征值計(jì)算。對(duì)于非邊界點(diǎn)，根據(jù)式(6)計(jì)算其FPFH值。將得到的直方圖按特征元素<,,>劃分為3個(gè)子直方圖，對(duì)每一個(gè)子直方圖分別計(jì)算其標(biāo)準(zhǔn)差，取3個(gè)標(biāo)準(zhǔn)差中最大值作為該點(diǎn)的特征值。根據(jù)計(jì)算得到的特征值對(duì)點(diǎn)集進(jìn)行升序排序。根據(jù)閾值將點(diǎn)集分為2部分，標(biāo)準(zhǔn)差小于閾值的點(diǎn)不需要精簡(jiǎn)，直接存入點(diǎn)集中，標(biāo)準(zhǔn)差大于閾值的點(diǎn)加入到點(diǎn)集中。

步驟3.改進(jìn)的FPS算法采樣。根據(jù)精簡(jiǎn)率、點(diǎn)云總數(shù)以及點(diǎn)集中的點(diǎn)云數(shù)計(jì)算得到需要采樣的點(diǎn)云數(shù)，將點(diǎn)集劃分為個(gè)子區(qū)間，根據(jù)需要采樣的點(diǎn)云數(shù)和子區(qū)間數(shù)計(jì)算得到每個(gè)子區(qū)間需要采樣的點(diǎn)云數(shù)。根據(jù)改進(jìn)的FPS算法從每個(gè)子區(qū)間等間隔采個(gè)點(diǎn)，并將采樣點(diǎn)加入到點(diǎn)集中。最后輸出精簡(jiǎn)后的點(diǎn)集。

步驟1中，通過(guò)設(shè)置鄰域搜索閾值可以調(diào)節(jié)查詢的邊界精度(即查詢到的邊界數(shù))。并根據(jù)實(shí)際應(yīng)用需要進(jìn)行設(shè)置，經(jīng)過(guò)實(shí)驗(yàn)分析，當(dāng)查找到的邊界點(diǎn)數(shù)占精簡(jiǎn)后點(diǎn)云總數(shù)的10%左右時(shí)，精簡(jiǎn)后的點(diǎn)云模型邊緣較為完整，又能夠在非邊界區(qū)域采集更多的點(diǎn)。本文實(shí)驗(yàn)保留的邊界點(diǎn)云數(shù)占精簡(jiǎn)后的5%～20%。

步驟2中，閾值的大小決定著最終精簡(jiǎn)后模型中非特征區(qū)域最終所能夠保留的點(diǎn)云數(shù)量，當(dāng)閾值很大時(shí)，精簡(jiǎn)后的模型特征點(diǎn)居多，在非特征區(qū)域容易出現(xiàn)較大的孔洞，而當(dāng)閾值很小時(shí)，精簡(jiǎn)后的模型中點(diǎn)的分布較為均勻，整體保留較好，但特征點(diǎn)較少。需根據(jù)實(shí)際設(shè)置閾值大小，因?yàn)槲磳?duì)特征值進(jìn)行歸一化處理，所以閾值的取值較大，一般為[1, 20]。

步驟3中，子區(qū)間數(shù)的設(shè)置可影響算法的計(jì)算時(shí)間，在實(shí)驗(yàn)中根據(jù)模型點(diǎn)云規(guī)模不同將其大小一般設(shè)置為1 000～5 000。

邊界查找部分的時(shí)間復(fù)雜度為()[17]。特征值部分主要是對(duì)直方圖進(jìn)行統(tǒng)計(jì)計(jì)算，其時(shí)間復(fù)雜度是()，為非邊界點(diǎn)的點(diǎn)云數(shù)，為采樣點(diǎn)鄰域內(nèi)的點(diǎn)數(shù)，計(jì)算標(biāo)準(zhǔn)差并找出最大標(biāo)準(zhǔn)差的時(shí)間復(fù)雜度為()。邊界點(diǎn)的數(shù)量占總點(diǎn)云數(shù)的比值很小，趨近于點(diǎn)云總數(shù)，因此()≈()。對(duì)于采樣部分，采樣每個(gè)子區(qū)間需要計(jì)算次距離，為子區(qū)間內(nèi)等間隔采樣的點(diǎn)數(shù)，則采樣完個(gè)子區(qū)間需要計(jì)算次距離，則采樣部分的時(shí)間復(fù)雜度為()，子區(qū)間數(shù)乘以每個(gè)子區(qū)間內(nèi)的點(diǎn)云數(shù)為非特征點(diǎn)的點(diǎn)云數(shù)，而非特征點(diǎn)的點(diǎn)云數(shù)也是趨近于點(diǎn)云總數(shù)的。故在最壞情況下，當(dāng)每個(gè)子區(qū)間的采樣點(diǎn)數(shù)的取值接近于時(shí)，采樣部分的時(shí)間復(fù)雜度接近于()，即當(dāng)精簡(jiǎn)率很低時(shí)，采樣的時(shí)間復(fù)雜度約為()。故最壞情況下算法的時(shí)間復(fù)雜度為()，為等間隔采樣的采樣點(diǎn)數(shù)。

3 實(shí)驗(yàn)結(jié)果分析

以斯坦福大學(xué)三維掃描庫(kù)中的點(diǎn)云數(shù)據(jù)作為測(cè)試數(shù)據(jù)，將本文算法與 FPS、非均勻網(wǎng)格法(Non-uniform)、基于k-means聚類的精簡(jiǎn)算法[8](K-means)以及基于自適應(yīng)曲率熵的精簡(jiǎn)算法[12](Curvature entropy))進(jìn)行對(duì)比分析，從可視化、信息熵和運(yùn)行時(shí)間3個(gè)方面對(duì)算法進(jìn)行評(píng)價(jià)。所有實(shí)驗(yàn)在Windows 10，64位操作系統(tǒng)中進(jìn)行，基于Intel Core i5-10400F CPU，16 G內(nèi)存，采用Visual Studio 2019編程實(shí)現(xiàn)。

3.1 視覺(jué)效果分析

為測(cè)試本文算法對(duì)不同規(guī)模和形狀的點(diǎn)云模型的精簡(jiǎn)效果，在多個(gè)模型上測(cè)試了精簡(jiǎn)率(精簡(jiǎn)率=刪減點(diǎn)云數(shù)/原始點(diǎn)云數(shù)×100%)為90%下的精簡(jiǎn)效果，實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同模型精簡(jiǎn)結(jié)果((a)原始模型；(b)最遠(yuǎn)點(diǎn)采樣法；(c)非均勻網(wǎng)格法；(d) k-means聚類法；(e)自適應(yīng)曲率熵；(f)本文算法)

圖6模型括號(hào)內(nèi)數(shù)字為該模型的原始點(diǎn)云數(shù)，圖中顏色代表點(diǎn)云的深度信息，黃色和紅色框圖為模型局部放大圖。由圖6可知，對(duì)于較小規(guī)模和特征信息較少的點(diǎn)云模型Happy buddha，5種算法的精簡(jiǎn)效果相近，均能保證模型整體的完整。相對(duì)而言，F(xiàn)PS算法和Non-uniform算法的整體性更好，而K-means算法、Curvature entropy算法和本文算法對(duì)特征信息的保留效果更好。

Manuscript為一張較為平整的牛皮紙，在中部寫(xiě)有文字，文字區(qū)域較紙面有一定的凹陷，特征信息主要為中部的文字書(shū)寫(xiě)痕跡。由圖6可知，F(xiàn)PS算法和Non-uniform算法精簡(jiǎn)后的模型幾乎無(wú)法看出中間的文字內(nèi)容，K-means算法和Curvature entropy算法雖然對(duì)文字部分的保留效果較好，但在非文字區(qū)域容易出現(xiàn)大的孔洞，整體可視化效果較差。本文算法整體可視化效果最好，能夠明顯地識(shí)別出文字區(qū)域和非文字區(qū)域，模型表面也未出現(xiàn)明顯孔洞。

對(duì)于結(jié)構(gòu)復(fù)雜和數(shù)據(jù)量大的點(diǎn)云模型(Statuette和Lucy模型)，本文算法的精簡(jiǎn)效果也較好，可兼顧細(xì)節(jié)特征信息保留和保證精簡(jiǎn)模型的整體完整性。

圖7為5種算法在不同精簡(jiǎn)率下對(duì)Dragon模型的精簡(jiǎn)可視化結(jié)果。由圖可知，在精簡(jiǎn)率較小時(shí)，5種算法的精簡(jiǎn)效果均很相似，且能保證模型的整體完整；當(dāng)精簡(jiǎn)率增大時(shí)，算法的精簡(jiǎn)差異就越來(lái)越大。Non-uniform算法的精簡(jiǎn)結(jié)果與FPS算法類似，但在細(xì)節(jié)特征上比FPS算法保留效果更好。K-means算法和Curvature entropy算法類似，均對(duì)細(xì)節(jié)特征保留較好，但當(dāng)精簡(jiǎn)率增大時(shí)，精簡(jiǎn)模型表面容易出現(xiàn)較大的孔洞，Curvature entropy算法的整體性要稍好于K-means算法。本文算法的整體可視化效果最好，對(duì)模型的某些局部特征保留效果較佳(如Dragon模型的眼球部位)。

圖7 不同精簡(jiǎn)率下Dragon模型精簡(jiǎn)結(jié)果((a)最遠(yuǎn)點(diǎn)采樣法；(b)非均勻網(wǎng)格法；(c) k-means聚類法；(d)自適應(yīng)曲率熵；(e)本文算法)

3.2 信息熵分析

信息熵評(píng)價(jià)方法能夠?qū)?jiǎn)算法的精簡(jiǎn)質(zhì)量進(jìn)行定量評(píng)價(jià)。在相同的精簡(jiǎn)率下，不同算法精簡(jiǎn)后保留的點(diǎn)云數(shù)量略有差別，故本文在計(jì)算得到精簡(jiǎn)模型的標(biāo)準(zhǔn)化信息熵后，利用式(11)對(duì)熵值進(jìn)行了均值化處理。表1列出了5種算法在精簡(jiǎn)率為90%下對(duì)各點(diǎn)云模型精簡(jiǎn)后的熵值計(jì)算結(jié)果。

由表1可知，在Happy buddha，Manuscript，Lucy和Dragon模型上，本文算法的熵值均是最高的，在Statuette模型上的熵值比Non-uniform算法的精簡(jiǎn)模型稍低一點(diǎn)，但差距很小。值得注意的是，采樣點(diǎn)分布最均勻的FPS算法的熵值和特征信息保留最好的K-means算法和Curvature entropy算法精簡(jiǎn)得到的模型的熵值均不是最高的，在多數(shù)情況下，兼顧特征信息保留和整體完整性的算法的熵值更高。

為了驗(yàn)證本文所提出標(biāo)準(zhǔn)化信息熵的可行性，用本文算法對(duì)Dragon模型在90%精簡(jiǎn)率下進(jìn)行精簡(jiǎn)，精簡(jiǎn)結(jié)果如圖8所示，左側(cè)模型整體性較差，但是細(xì)節(jié)特征保留較好，而右側(cè)模型整體性最好，但特征信息保留較少。熵值計(jì)算結(jié)果見(jiàn)表2。

表1 5種算法的熵值計(jì)算結(jié)果

注：加粗?jǐn)?shù)據(jù)為最優(yōu)值

圖8 90%精簡(jiǎn)率下Dragon模型精簡(jiǎn)結(jié)果

表2 Dragon模型的標(biāo)準(zhǔn)化信息熵熵值計(jì)算結(jié)果

注：加粗?jǐn)?shù)據(jù)為最優(yōu)值

由表2可知，無(wú)論是特征點(diǎn)較多的圖8(a)模型還是特征點(diǎn)少的圖8(d)模型，其標(biāo)準(zhǔn)化信息熵值均不是最高的，而相對(duì)而言，即保留了較多的特征點(diǎn)，又保證模型整體完整性的圖8(c)模型的熵值最高，故本文算法能夠較好地評(píng)價(jià)模型的精簡(jiǎn)效果。

3.3 運(yùn)行時(shí)間分析

根據(jù)分析算法可知，F(xiàn)PS算法的時(shí)間復(fù)雜度為(2)，為點(diǎn)云數(shù)。Non-uniform算法經(jīng)過(guò)不斷優(yōu)化，時(shí)間復(fù)雜度接近于()。K-means算法的主要計(jì)算是進(jìn)行k-means聚類，故時(shí)間復(fù)雜度是()，其中為聚類數(shù)，為迭代次數(shù)。Curvature entropy算法主要時(shí)間花費(fèi)在曲率熵的計(jì)算上，其時(shí)間復(fù)雜度為(log)。本文算法的時(shí)間復(fù)雜度為()，為子區(qū)間內(nèi)等間隔采樣的采樣點(diǎn)數(shù)。表3為5種算法在90%精簡(jiǎn)率下對(duì)上述模型精簡(jiǎn)的運(yùn)行時(shí)間。

表3 5種算法的運(yùn)行時(shí)間(s)

注：加粗?jǐn)?shù)據(jù)為最優(yōu)值

由表3可知，Non-uniform算法的計(jì)算時(shí)間最短，本文算法的運(yùn)行時(shí)間接近于Non-uniform算法。而與本文算法精簡(jiǎn)效果相近的K-means算法和Curvature entropy算法的運(yùn)行時(shí)間花費(fèi)比本文算法高得多，說(shuō)明本文算法不僅能夠保證精簡(jiǎn)質(zhì)量，同時(shí)運(yùn)行時(shí)間較短，可有效縮短點(diǎn)云預(yù)處理的時(shí)間。

4 結(jié)束語(yǔ)

隨著三維掃描技術(shù)的不斷發(fā)展，點(diǎn)云掃描速度越來(lái)越快，獲取的點(diǎn)云數(shù)量也越來(lái)越大。如果不對(duì)得到的點(diǎn)云模型進(jìn)行精簡(jiǎn)，后續(xù)的點(diǎn)云處理效率將會(huì)大大降低，為此本文提出了基于特征保持的點(diǎn)云精簡(jiǎn)算法。為了更好評(píng)價(jià)點(diǎn)云精簡(jiǎn)效果，還提出一種標(biāo)準(zhǔn)化的信息熵計(jì)算方法，通過(guò)對(duì)斯坦福大學(xué)三維掃描庫(kù)中的點(diǎn)云數(shù)據(jù)實(shí)驗(yàn)表明，該算法的信息熵優(yōu)于其他4種算法，能夠在保證模型完整性的同時(shí)，盡可能地保留模型的特征信息，且算法運(yùn)行效率高，具有較好的適用性。本文算法存在需要預(yù)先設(shè)置的參數(shù)過(guò)多，對(duì)于點(diǎn)數(shù)較少的點(diǎn)云簡(jiǎn)化效果不佳等問(wèn)題。在未來(lái)的研究中，將減少算法的參數(shù)量，并設(shè)計(jì)一個(gè)自適應(yīng)點(diǎn)云精簡(jiǎn)算法。

[1] PAULY M, GROSS M, KOBBELT L P. Efficient simplification of point-sampled surfaces[C]//IEEE Visualization, 2002. New York: IEEE Press, 2002: 163-170.

[2] MARTIN R R, STROUD I A, MARSHALL A D. Data reduction for reverse engineering[J]. The Mathematics of Surfaces, 1997, 10(1): 85-100.

[3] FILIP D, MAGEDSON R, MARKOT R. Surface algorithms using bounds on derivatives[J]. Computer Aided Geometric Design, 1986, 3(4): 295-311.

[4] SUN W, BRADLEY C, ZHANG Y F, et al. Cloud data modelling employing a unified, non-redundant triangular mesh[J]. Computer-Aided Design, 2001, 33(2): 183-193.

[5] LEE K H, WOO H, SUK T. Point data reduction using 3D grids[J]. The International Journal of Advanced Manufacturing Technology, 2001, 18(3): 201-210.

[6] MIAO Y W, PAJAROLA R, FENG J Q. Curvature-aware adaptive re-sampling for point-sampled geometry[J]. Computer-Aided Design, 2009, 41(6): 395-403.

[7] ELDAR Y, LINDENBAUM M, PORAT M, et al. The farthest point strategy for progressive image sampling[J]. IEEE Transactions on Image Processing, 1997, 6(9): 1305-1315.

[8] 賀一波, 陳冉麗, 吳侃, 等. 基于k-means聚類的點(diǎn)云精簡(jiǎn)方法[J]. 激光與光電子學(xué)進(jìn)展, 2019, 56(9): 96-99.

HE Y B, CHEN R L, WU K, et al. Point cloud simplification method based on k-means clustering[J]. Laser & Optoelectronics Progress, 2019, 56(9): 96-99 (in Chinese).

[9] YANG Y, LI M, MA X. A point cloud simplification method based on modified fuzzy C-means clustering algorithm with feature information reserved[EB/OL]. [2021-12-25]. https:// downloads.hindawi.com/journals/mpe/2020/5713137.pdf.

[10] MAHDAOUI A, SBAI E H. 3D point cloud simplification based on-nearest neighbor and clustering[EB/OL]. [2021- 12-25]. https://downloads.hindawi.com/journals/am/2020/882 5205.pdf.

[11] JI C Y, LI Y, FAN J H, et al. A novel simplification method for 3D geometric point cloud based on the importance of point[J]. IEEE Access, 2019, 7: 129029-129042.

[12] WANG G L, WU L S, HU Y, et al. Point cloud simplification algorithm based on the feature of adaptive curvature entropy[J]. Measurement Science and Technology, 2021, 32(6): 065004: 1-065004: 12.

[13] ZHANG K, QIAO S Q, WANG X H, et al. Feature-preserved point cloud simplification based on natural quadric shape models[J]. Applied Sciences, 2019, 9(10): 2130.

[14] XUAN W, HUA X H, CHEN X J, et al. A new progressive simplification method for point cloud using local entropy of normal angle[J]. Journal of the Indian Society of Remote Sensing, 2018, 46(4): 581-589.

[15] SHOAIB M, CHEONG J, KIM Y, et al. Fractal bubble algorithm for simplification of 3D point cloud data[J]. Journal of Intelligent & Fuzzy Systems, 2019, 37(6): 7815-7830.

[16] QI J K, HU W, GUO Z M. Feature preserving and uniformity-controllable point cloud simplification on graph[C]//2019 IEEE International Conference on Multimedia and Expo. New York: IEEE Press, 2019: 284-289.

[17] SILPA-ANAN C, HARTLEY R. Optimised KD-trees for fast image descriptor matching[C]//2008 IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2008: 1-8.

[18] 孫殿柱, 范志先, 李延瑞. 散亂數(shù)據(jù)點(diǎn)云邊界特征自動(dòng)提取算法[J]. 華中科技大學(xué)學(xué)報(bào): 自然科學(xué)版, 2008, 36(8): 82-84.

SUN D Z, FAN Z X, LI Y R. Automatic extraction of boundary characteristic from scatter data[J]. Journal of Huazhong University of Science and Technology: Nature Science Edition, 2008, 36(8): 82-84 (in Chinese).

[19] RUSU R B, MARTON Z C, BLODOW N, et al. Learning informative point classes for the acquisition of object model maps[C]//2008 10th International Conference on Control, Automation, Robotics and Vision. New York: IEEE Press, 2008: 643-650.

[20] RUSU R B, BLODOW N, MARTON Z C, et al. Aligning point cloud views using persistent feature histograms[C]//2008 IEEE/RSJ International Conference on Intelligent Robots and Systems. New York: IEEE Press, 2008: 3384-3391.

[21] WAHL E, HILLENBRAND U, HIRZINGER G. Surflet-pair- relation histograms: a statistical 3D-shape representation for rapid classification[C]//The 4th International Conference on 3-D Digital Imaging and Modeling. New York: IEEE Press, 2003: 474-481.

[22] RUSU R B, BLODOW N, BEETZ M. Fast point feature histograms (FPFH) for 3D registration[C]//2009 IEEE International Conference on Robotics and Automation. New York: IEEE Press, 2009: 3212-3217.

[23] MOENNING C, DODGSON N. Fast marching farthest point sampling[EB/OL]. [2021-12-15]. http://citeseerx.ist.psu.edu/ viewdoc/download;jsessionid=1A9C100269551371F03B7D91B0B7BDBE?doi=10.1.1.14.1047&rep=rep1&type=pdf.

[24] SCHL?MER T, HECK D, DEUSSEN O. Farthest-point optimized point sets with maximized minimum distance[C]// The ACM SIGGRAPH Symposium on High Performance Graphics – HPG’11. New York: ACM Press, 2011: 135-142.

[25] 陳境煥. 基于深層神經(jīng)網(wǎng)絡(luò)的三維點(diǎn)云細(xì)粒度分割算法研究[D]. 廣州: 廣東工業(yè)大學(xué), 2020.

CHEN J H. Research on fine-grained segmentation algorithm of 3D point cloud based on deep neural network[D]. Guangzhou: Guangdong University of Technology, 2020 (in Chinese).

[26] 馬益飛. 基于特征線的兵馬俑點(diǎn)云簡(jiǎn)化方法研究[D]. 西安: 西北大學(xué), 2021.

MA Y F. Research on simplification method for point cloud of terracotta warriors based on characteristic line[D]. Xi’an: Northwest University, 2021 (in Chinese).

[27] SHANNON C E. A mathematical theory of communication[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2001, 5(1): 3-55.

[28] 朱廣堂, 葉珉?yún)? 基于曲率特征的點(diǎn)云去噪及定量評(píng)價(jià)方法研究[J]. 測(cè)繪通報(bào), 2019(6): 105-108.

ZHU G T, YE M L. Research on the method of point cloud denoising based on curvature characteristics and quantitative evaluation[J]. Bulletin of Surveying and Mapping, 2019(6): 105-108 (in Chinese).

[29] 俞立平, 宋夏云, 王作功. 評(píng)價(jià)型指標(biāo)標(biāo)準(zhǔn)化與評(píng)價(jià)方法對(duì)學(xué)術(shù)評(píng)價(jià)影響研究: 以TOPSIS評(píng)價(jià)方法為例[J]. 情報(bào)理論與實(shí)踐, 2020, 43(2): 15-20, 54.

YU L P, SONG X Y, WANG Z G. Study on the influence of evaluation standardization and evaluation methods on academic evaluation: taking TOPSIS evaluation method as an example[J]. Information Studies: Theory & Application, 2020, 43(2): 15-20, 54 (in Chinese).

A scattered point cloud simplification algorithm based on FPFH feature extraction

LI Hai-peng, XU Dan, FU Yu-ting, LIU Yan-an, ZHANG Ting-ting

(School of Information Science and Engineering, Yunnan University, Kunming Yunnan 650500, China)

To address the large amount of redundant data in the original point cloud, a point cloud simplification algorithm based on fast point feature histograms (FPFH) feature extraction was proposed, effectively taking into account the retention of feature information and overall integrity. Firstly, the algorithm sought and retained the boundary points of the original model. Then, the FPFH value of non-boundary points were calculated, thus producing the feature value of the point cloud. After sorting the feature values, the non-boundary points were divided into the feature region and the non-feature region, retaining the points in the feature region. Finally, the non-feature region was divided intosub-intervals, and the improved farthest point sampling algorithm was employed to sample each sub-interval. The proposed algorithm was compared with the farthest point sampling algorithm, non-uniform grid method, k-means algorithm, and adaptive curvature entropy algorithm, and the simplified point cloud was evaluated by the standardized information entropy evaluation method. Experimental results show that the proposed algorithm outperforms other simplification algorithms. In addition, the visualization results indicate that the proposed algorithm can not only ensure the integrity of the simplified model but also retain most of the feature information of the point cloud.

point cloud simplification; fast point feature histograms; farthest point sampling; boundary reservation; standardized information entropy

25 November，2021；

National Natural Science Foundation of China (61761046, 62061049, 62162068); Yunnan Province “Ten Thousand Talents Program” Yunling Scholars Special Project (YNWR-YLXZ-2018-022); Yunnan Provincial Science and Technology Department-Yunnan University “Double First Class” Construction Joint Fund Project (2019FY003012); Graduate Research and Innovation Foundation of Yunnan University (Y2000211)

LI Hai-peng (1997-), master student. His main research interests cover image processing and computer vision. E-mail：lihaipeng@mail.ynu.edu.cn

TP 391

10.11996/JG.j.2095-302X.2022040599

A

2095-302X(2022)04-0599-09

2021-11-25；

2022-02-25

25 February，2022

國(guó)家自然科學(xué)基金項(xiàng)目(61761046，62061049，62162068)；云南省“萬(wàn)人計(jì)劃”云嶺學(xué)者專項(xiàng)(YNWR-YLXZ-2018-022)；云南省科技廳-云南大學(xué)“雙一流”建設(shè)聯(lián)合基金項(xiàng)目(2019FY003012)；云南大學(xué)研究生科研創(chuàng)新項(xiàng)目(Y2000211)

李海鵬(1997-)，男，碩士研究生。主要研究方向?yàn)閳D像處理和計(jì)算機(jī)視覺(jué)。E-mail：lihaipeng@mail.ynu.edu.cn

徐 丹(1968-)，女，教授，博士。主要研究方向?yàn)橛?jì)算機(jī)圖形圖像、視覺(jué)及人工智能、文化計(jì)算等。E-mail：danxu@ynu.edu.cn

XU Dan (1968-), professor, Ph.D. Her main research interests cover computer graphics, computer vision, artificial intelligence, cultural computing, etc. E-mail：danxu@ynu.edu.cn