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

基于FPFH特征提取的散亂點云精簡算法

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

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

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

點云精簡；快速點特征直方圖；最遠點采樣；邊界保留；標準化信息熵

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

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

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

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

1 本文方法

1.1 邊界查找

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

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

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

1.2 快速點特征直方圖

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

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

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

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

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

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

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

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

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

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

1.3 最遠點采樣算法(FPS)

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

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

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

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

圖5 FPS算法示意圖

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

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

1.4 標準化信息熵

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

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

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

最后，計算得到信息熵值，即

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

2 算法流程

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

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

輸出：精簡后的點集。

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

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

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

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

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

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

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

3 實驗結(jié)果分析

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

3.1 視覺效果分析

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

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

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

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

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

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

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

3.2 信息熵分析

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

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

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

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

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

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

表2 Dragon模型的標準化信息熵熵值計算結(jié)果

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

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

3.3 運行時間分析

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

表3 5種算法的運行時間(s)

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

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

4 結(jié)束語

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

[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聚類的點云精簡方法[J]. 激光與光電子學(xué)進展, 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ù)點云邊界特征自動提取算法[J]. 華中科技大學(xué)學(xué)報: 自然科學(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ò)的三維點云細粒度分割算法研究[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] 馬益飛. 基于特征線的兵馬俑點云簡化方法研究[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)? 基于曲率特征的點云去噪及定量評價方法研究[J]. 測繪通報, 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] 俞立平, 宋夏云, 王作功. 評價型指標標準化與評價方法對學(xué)術(shù)評價影響研究: 以TOPSIS評價方法為例[J]. 情報理論與實踐, 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

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

李海鵬(1997-)，男，碩士研究生。主要研究方向為圖像處理和計算機視覺。E-mail：lihaipeng@mail.ynu.edu.cn

徐 丹(1968-)，女，教授，博士。主要研究方向為計算機圖形圖像、視覺及人工智能、文化計算等。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