基于FPFH特征和模糊聚類(lèi)的自適應(yīng)點(diǎn)云壓縮

王藝楠，郝礦榮,2，楊煥宇,3

(1.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620；2.數(shù)字化紡織服裝技術(shù)教育部工程研究中心，上海 201620；3.上海開(kāi)放大學(xué)，上海 200233)

基于FPFH特征和模糊聚類(lèi)的自適應(yīng)點(diǎn)云壓縮

王藝楠1，郝礦榮1,2，楊煥宇1,3

(1.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620；2.數(shù)字化紡織服裝技術(shù)教育部工程研究中心，上海 201620；3.上海開(kāi)放大學(xué)，上海 200233)

針對(duì)三維激光掃描技術(shù)獲取的點(diǎn)云數(shù)據(jù)存在大量冗余問(wèn)題，文中提出了一種基于快速點(diǎn)特征直方圖和模糊C均值聚類(lèi)(FPFH-FCM)的點(diǎn)云壓縮算法。利用FPFH特征在點(diǎn)云模型不同幾何位置的分布差異，基于FCM算法自適應(yīng)地將點(diǎn)云集合分為特征點(diǎn)集和非特征點(diǎn)集。并建立壓縮準(zhǔn)則：對(duì)非特征點(diǎn)集進(jìn)行較大比例的壓縮，去除冗余點(diǎn)；對(duì)特征點(diǎn)集進(jìn)行較小比例的壓縮，盡量保留更多的特征點(diǎn)，以實(shí)現(xiàn)點(diǎn)云壓縮。在對(duì)比試驗(yàn)中，分別使用提出的基于FPFH特征的點(diǎn)云壓縮算法與基于曲率特征的點(diǎn)云壓縮算法，對(duì)人體點(diǎn)云數(shù)據(jù)進(jìn)行壓縮，對(duì)比壓縮后點(diǎn)云的曲面重建效果，同時(shí)使用原始點(diǎn)云與壓縮后點(diǎn)云之間的Hausdorff距離作為壓縮誤差評(píng)價(jià)指標(biāo)，結(jié)果證明，該壓縮算法能夠更好地保留重建模型的細(xì)節(jié)特征，具有更高的壓縮精度。

點(diǎn)云壓縮；快速點(diǎn)特征直方圖；模糊C均值聚類(lèi)；泊松曲面重建；Hausdorff距離

三維激光掃描技術(shù)以其非接觸、高精度等特點(diǎn)廣泛應(yīng)用于空間信息獲取，但掃描得到的海量點(diǎn)云數(shù)據(jù)通常在幾十萬(wàn)，甚至上百萬(wàn)的數(shù)量級(jí)，且存在大量冗余，這就增加了點(diǎn)云數(shù)據(jù)存儲(chǔ)、傳輸、運(yùn)算負(fù)擔(dān)和后續(xù)處理工作的難度[1]。

點(diǎn)云數(shù)據(jù)在虛擬現(xiàn)實(shí)、逆向工程、模式識(shí)別和機(jī)器視覺(jué)領(lǐng)域廣泛應(yīng)用。例如即時(shí)定位與地圖構(gòu)建技術(shù)(SLAM)是目前實(shí)現(xiàn)真正全自主移動(dòng)機(jī)器人的關(guān)鍵，這項(xiàng)技術(shù)在實(shí)際應(yīng)用中需要對(duì)獲取的點(diǎn)云數(shù)據(jù)進(jìn)行去噪、壓縮等預(yù)處理。近年的熱門(mén)技術(shù)-虛擬現(xiàn)實(shí)也需要在三維重建前對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行去噪、壓縮、網(wǎng)格化等處理。因此，對(duì)三維點(diǎn)云數(shù)據(jù)的壓縮研究是當(dāng)前的一個(gè)研究熱點(diǎn)。

不同應(yīng)用場(chǎng)景中，對(duì)壓縮后點(diǎn)云數(shù)據(jù)的要求也有很大差別。例如用于SLAM的點(diǎn)云數(shù)據(jù)[2]，壓縮后只需保留可完成點(diǎn)云拼接[1]的幾何特征點(diǎn)，使得經(jīng)過(guò)點(diǎn)云拼接、信息融合后重構(gòu)出的點(diǎn)集能夠刻畫(huà)出實(shí)際場(chǎng)景的輪廓，無(wú)需保留大量表面細(xì)節(jié)信息。而在虛擬現(xiàn)實(shí)[3]應(yīng)用中的點(diǎn)云數(shù)據(jù)則需要保留更多的細(xì)節(jié)特征，使其通過(guò)三維重建獲得逼近真實(shí)的場(chǎng)景模型，帶來(lái)更好的虛擬現(xiàn)實(shí)體驗(yàn)。

點(diǎn)云壓縮不僅要有較高的壓縮比，還需要保留足夠多的特征點(diǎn)。因而點(diǎn)云壓縮問(wèn)題可定義為：k時(shí)刻從視點(diǎn)Vk獲取的點(diǎn)云集合為Mk，求取Mk的一個(gè)子集Pk，在滿(mǎn)足預(yù)設(shè)壓縮比ρ的情況下

(1)

使壓縮后的子集Pk保留足夠多的特征點(diǎn)，即

(2)

其中， 為特征點(diǎn)數(shù)量度量函數(shù)； 為設(shè)定的特征點(diǎn)保留率。

現(xiàn)有的壓縮算法可以分為兩類(lèi)：(1)基于距離的壓縮算法。如包圍盒法[4]、均勻/非均勻網(wǎng)格法[5]、自適應(yīng)距離法[6]等。這類(lèi)方法簡(jiǎn)單、高效，對(duì)均勻的點(diǎn)云能夠取得一定效果，但只適應(yīng)于表面不復(fù)雜、曲率變化不大的物體的數(shù)據(jù)壓縮；(2)基于特征[7]的壓縮算法。如曲率采樣法[8]、曲線(xiàn)擬合法[9]等。這類(lèi)方法雖然計(jì)算快速、容易，但是無(wú)法獲得太多信息，因?yàn)檫@類(lèi)方法只使用很少的幾個(gè)參數(shù)值來(lái)近似的表示一個(gè)點(diǎn)的k鄰域的幾何特征，僅能表征某些相同或者相近的特征值，無(wú)法獲得太多信息，而對(duì)于包含大量特征信息的復(fù)雜模型，無(wú)法保留其全局特征信息。

作者引入一種新的復(fù)合特征—點(diǎn)特征直方圖(Point Feature Histogram，PFH)[10]，該特征經(jīng)過(guò)多年的發(fā)展和實(shí)踐，被證明是一種非常有效的點(diǎn)云描述特征，并廣泛應(yīng)用于點(diǎn)云處理[11]。由于快速點(diǎn)特征直方圖(Fast Point Feature Histogram，F(xiàn)PFH)[12]在仍保留PFH大部分識(shí)別特性的基礎(chǔ)上將PFH的理論計(jì)算復(fù)雜度從O(n·k2)降至O(n·k)，因而作者選用FPFH特征。利用點(diǎn)云的FPFH特征在模型不同幾何位置的顯著分布差別，有選擇的剔除冗余點(diǎn)，盡可能多的保留特征點(diǎn)，使得壓縮后的點(diǎn)云模型在一定壓縮率下，可以保留更多用于曲面重建、物體識(shí)別的幾何特征，獲得更好的壓縮效果，同時(shí)保證算法的計(jì)算速度在可接受范圍內(nèi)。

1 計(jì)算快速點(diǎn)特征直方圖

1.1 PFH特征描述子

點(diǎn)特征直方圖(PFH)[10]的計(jì)算方式是通過(guò)參數(shù)化查詢(xún)點(diǎn)與鄰域點(diǎn)之間的空間差異，形成一個(gè)多維直方圖對(duì)點(diǎn)的 鄰域幾何屬性進(jìn)行描述。具有3個(gè)優(yōu)勢(shì)：(1)剛體變換不變性；(2)采樣一致性，改變采樣密度，特征保持不變；(3)輕微噪聲不變性。具有這些不同優(yōu)勢(shì)的特征描述子往往能在實(shí)際應(yīng)用中帶來(lái)更好的效果[13-14]。

圖1所示為查詢(xún)點(diǎn)Pq及其PFH計(jì)算的影響區(qū)域，Pq位于半徑為 的圓球中心位置，Pq的所有k鄰元素(即與點(diǎn)Pq的距離小于半徑r的所有點(diǎn))全部互相連接在一個(gè)網(wǎng)絡(luò)中。PFH描述子通過(guò)計(jì)算k鄰域內(nèi)所有兩點(diǎn)之間的法線(xiàn)偏差而得到直方圖。如圖2所示，為了計(jì)算k鄰域內(nèi)任意兩點(diǎn)Ps和Pt對(duì)應(yīng)的法線(xiàn)ns和nt之間的相對(duì)偏差，在Ps點(diǎn)上定義一個(gè)固定的三維直角坐標(biāo)系uvw，并將這一uvw坐標(biāo)系平移至Pt點(diǎn)處。

圖1 查詢(xún)點(diǎn) 及其 鄰域

圖2 定義一個(gè)固定的局部坐標(biāo)系

使用圖2中定義的uvw坐標(biāo)系，法線(xiàn)ns和nt之間的偏差可以通過(guò)式(3)和式(4)的計(jì)算后使用4組值(α,φ,θ,d)來(lái)表示

(3)

(4)

式(4)中，d是Ps和Pt兩點(diǎn)之間的歐氏距離，d=‖Ps-Pt‖。

按照上述計(jì)算方式，Pd的k鄰域內(nèi)任意兩點(diǎn)的法線(xiàn)偏差都可以用4組值(α,φ,θ,d)來(lái)表示。將鄰域內(nèi)所有的4組值以某種統(tǒng)計(jì)的方式放進(jìn)直方圖中，就得到了Pq點(diǎn)的特征直方圖。

PFH的理論計(jì)算復(fù)雜度是O(n·k2)，n是點(diǎn)的數(shù)量，k是最近鄰的個(gè)數(shù)。對(duì)于實(shí)時(shí)應(yīng)用或接近實(shí)時(shí)的應(yīng)用，密集點(diǎn)云的PFH計(jì)算存在性能瓶頸。因而提出了PFH的簡(jiǎn)化版-快速點(diǎn)特征直方圖(FPFH)[12]，其計(jì)算復(fù)雜度減少至O(n·k)，并保持了較好的和PFH接近的特征區(qū)分能力。

1.2 FPFH特征描述子

快速點(diǎn)特征直方圖(FPFH)[12]是由PFH改進(jìn)而來(lái)，其計(jì)算原理如圖3所示。

圖3 FPFH計(jì)算原理

FPFH的計(jì)算過(guò)程如下：

(1)對(duì)于每一個(gè)查詢(xún)點(diǎn)(Pq)，計(jì)算該點(diǎn)和灰色區(qū)域內(nèi)鄰域點(diǎn)之間的元組(α,φ,θ)，第一步結(jié)果稱(chēng)為簡(jiǎn)化的點(diǎn)特征直方圖(Simplified Point Feature Histograms，SPFH)；

(2)確定查詢(xún)點(diǎn)(Pq)的每個(gè)鄰域點(diǎn)的k鄰域，分別計(jì)算每個(gè)鄰域點(diǎn)的SPFH；

(3)使用Pq點(diǎn)的SPFH值和它鄰域點(diǎn)Pk的SPFH值按式(5)計(jì)算獲得 FPFH。

式(5)中，以Pq和其鄰近點(diǎn)Pk之間的距離作為權(quán)重wk。FPFH利用三元組(α,φ,θ)描述查詢(xún)點(diǎn)與鄰域點(diǎn)之間法向量的偏差，將三元組中每個(gè)分量的統(tǒng)計(jì)值歸一化為[0,100]，并劃分11個(gè)區(qū)間，這樣共形成33個(gè)角度區(qū)間用于元組值的數(shù)量統(tǒng)計(jì)，由此獲得一個(gè)33維的特征向量。

1.3 FPFH特征分析

圖4和圖5分別是實(shí)際平面上的點(diǎn)和角點(diǎn)的FPFH直方圖。在平坦的表面上，由于查詢(xún)點(diǎn)與周?chē)c(diǎn)的法線(xiàn)方向差異比較小，描述法線(xiàn)差異的各個(gè)角度分量都集中在特定的區(qū)間，因而FPFH統(tǒng)計(jì)直方圖的分布比較集中。

圖4 實(shí)際平面點(diǎn)的FPFH圖

而位于邊緣、角點(diǎn)處，由于查詢(xún)點(diǎn)與周?chē)c(diǎn)的法線(xiàn)方向差異較大，描述法線(xiàn)差異的各個(gè)角度分量會(huì)在整個(gè)區(qū)間上出現(xiàn)，因而FPFH統(tǒng)計(jì)直方圖的分布比較均勻。

圖5 實(shí)際角點(diǎn)的FPFH圖

2 模糊C均值(FCM)聚類(lèi)算法

模糊C均值(FCM)聚類(lèi)算法[15]在眾多模糊聚類(lèi)算法中應(yīng)用最廣泛且較成功，它通過(guò)優(yōu)化目標(biāo)函數(shù)得到每個(gè)樣本點(diǎn)對(duì)所有類(lèi)中心的隸屬度，從而確定樣本點(diǎn)的類(lèi)屬，以實(shí)現(xiàn)樣本的自動(dòng)分類(lèi)。對(duì)給定的樣本集X={x1,x2,…,xn}?Rd，在FCM算法中，設(shè)U=(uij)n·c為隸屬度矩陣，V=[v1,v2,…,vc]為c個(gè)類(lèi)中心點(diǎn)組成的矩陣，式(6)定義了類(lèi)內(nèi)平均誤差函數(shù)J(X,U,V)

(6)

其中，m∈[1,+∞)是模糊指數(shù)；c是樣本集聚類(lèi)的類(lèi)別；uij(1≤i≤n,1≤j≤c)表示xi在第j個(gè)類(lèi)的隸屬度值，并滿(mǎn)足以下3個(gè)約束條件

(7)

1≥uij≥0,1≤i≤n,1≤j≤c

(8)

(9)

此外，vj表示第j類(lèi)的類(lèi)中心；d2(xi,vj)表示樣本xi和類(lèi)中心vj的相似度量，一般用歐式距離表示。

FCM的實(shí)現(xiàn)包含下列步驟：

(1)選定聚類(lèi)數(shù)目c、模糊指數(shù)m、最大迭代次數(shù)T和閾值ε，并令迭代計(jì)數(shù)器t=0，初始化隸屬度矩陣；

(2)利用拉格朗日乘法計(jì)算聚類(lèi)中心V和隸屬度矩陣U；

(3)根據(jù)當(dāng)前V和U，計(jì)算目標(biāo)函數(shù)式(6)中類(lèi)內(nèi)平均誤差函數(shù)J(X,U,V)的值，若迭代次數(shù)>T或者相鄰兩次目標(biāo)函數(shù)值的絕對(duì)值小于閾值ε，則算法停止；否則，令t=t+1轉(zhuǎn)步驟(2)。

3 基于FPFH-FCM的點(diǎn)云壓縮算法

3.1 問(wèn)題描述

作者提出的壓縮算法的基本思路是，利用點(diǎn)云的FPFH特征在不同幾何位置的顯著分布差別，選擇性地剔除一些點(diǎn)。剔除的基本原則是：位于平坦表面的點(diǎn)應(yīng)盡可能剔除，因?yàn)檫@種類(lèi)型的點(diǎn)數(shù)量龐大，包含的幾何特征較少；而位于幾何體邊緣、角點(diǎn)位置的點(diǎn)應(yīng)盡可能保留，因?yàn)檫@些點(diǎn)能夠定義幾何體的形狀，具有較大的幾何區(qū)分度，點(diǎn)云的后續(xù)處理(如點(diǎn)云拼接)經(jīng)常需要利用這些特征關(guān)鍵點(diǎn)做進(jìn)一步處理。

為了能夠自適應(yīng)地將點(diǎn)云數(shù)據(jù)按照上述準(zhǔn)則進(jìn)行壓縮，需要一種智能算法實(shí)現(xiàn)點(diǎn)云的自動(dòng)分類(lèi)。選取FCM( Fuzzy C-Means)[15]對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行聚類(lèi)，將每個(gè)點(diǎn)云數(shù)據(jù)的FPFH(33維特征直方圖)轉(zhuǎn)化為數(shù)值向量作為訓(xùn)練樣本，參數(shù)聚類(lèi)數(shù)目C和加權(quán)指數(shù)m均設(shè)為2，使用這種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)算法可將點(diǎn)云數(shù)據(jù)自動(dòng)聚類(lèi)為特征點(diǎn)集和非特征點(diǎn)集。

3.2 算法流程

作者提出了一種基于FPFH和FCM的點(diǎn)云壓縮算法，具體的算法流程如下

(1)在 時(shí)刻.通過(guò)掃描儀獲取點(diǎn)云集合Mk={pi|i=1,…,m}，并構(gòu)建集合Mk的索引樹(shù)。其中m為集合包含的掃描點(diǎn)數(shù)量；

(2)計(jì)算Mk集合中每個(gè)點(diǎn)Pi的法向量ni，得到法向量集合Nk={ni|i=1,…,m}，并構(gòu)建集合Nk的索引樹(shù)；

(3)根據(jù)式(1)和式(2)計(jì)算集合中每個(gè)點(diǎn)的特征直方圖hi，得到直方H={hi|i=1,…,m}；

(4)基于模糊C均值聚類(lèi)算法對(duì)FPFH特征進(jìn)行無(wú)監(jiān)督聚類(lèi)，獲得特征點(diǎn)集和非特征點(diǎn)集；

(5)通過(guò)設(shè)置參數(shù)K(兩類(lèi)點(diǎn)集壓縮率的比=非特征點(diǎn)集壓縮比例：特征點(diǎn)集壓縮比例)，給予非特征點(diǎn)集較高的壓縮率，特征點(diǎn)集較低的壓縮率(默認(rèn)情況下：K=1.5:1)；

(6)合并壓縮后的兩類(lèi)點(diǎn)集，獲取壓縮點(diǎn)云模型。

4 實(shí)例應(yīng)用與分析

為驗(yàn)證算法的有效性，采用C++語(yǔ)言在Microsoft Visual Studio 2010上實(shí)現(xiàn)點(diǎn)云壓縮算法，同時(shí)調(diào)用OpenGL庫(kù)函數(shù)顯示點(diǎn)云。作者使用包含復(fù)雜曲面的人體點(diǎn)云模型進(jìn)行壓縮實(shí)驗(yàn)，從不同壓縮率下的壓縮結(jié)果、壓縮后模型的曲面重建效果、壓縮誤差3個(gè)方面對(duì)FPFH-FCM算法進(jìn)行評(píng)價(jià)與分析，并與文獻(xiàn)[16]中的算法進(jìn)行對(duì)比。

4.1 不同壓縮率下的壓縮結(jié)果

作者提出的點(diǎn)云壓縮算法中有兩個(gè)參數(shù)需要設(shè)置，分別是K和ratio，其中K默認(rèn)取值為1.5；ratio是整體點(diǎn)云的壓縮比(剔除點(diǎn)數(shù)/輸入點(diǎn)數(shù))，可根據(jù)用戶(hù)需求設(shè)定，這里分別選取ratio為0.7、0.8、0.9進(jìn)行實(shí)驗(yàn)。

圖6 不同壓縮率下的壓縮結(jié)果

圖6為人體點(diǎn)云模型在不同壓縮率下的壓縮結(jié)果。其中圖6(a)為人體模型的原始點(diǎn)云，共包含52 565個(gè)點(diǎn)；圖6(b)為壓縮至70%的點(diǎn)云模型，共包含15 770個(gè)點(diǎn)，其中保留11 174個(gè)特征點(diǎn)，4 596個(gè)非特征點(diǎn)；圖6(c)為壓縮至80%的點(diǎn)云模型，共包含10 513個(gè)點(diǎn)，其中保留7 453個(gè)特征點(diǎn)，3 060個(gè)非特征點(diǎn)；圖6(d)為壓縮至90%的點(diǎn)云模型，共包含5 257個(gè)點(diǎn)，其中保留3 727個(gè)特征點(diǎn)，1 530個(gè)非特征點(diǎn)。

從圖6的點(diǎn)云壓縮結(jié)果可以看出，F(xiàn)PFH-FCM算法自適應(yīng)地在高曲率區(qū)域保留較多點(diǎn)，在平坦區(qū)域保留少數(shù)點(diǎn)，使得在不同壓縮率下都具有較好的壓縮效果，壓縮后的點(diǎn)云模型特征信息保留較為完好，輪廓信息依然清晰可見(jiàn)。同時(shí)該算法可根據(jù)實(shí)際情況對(duì)參數(shù)K(兩類(lèi)點(diǎn)集的壓縮比)進(jìn)行調(diào)整，改變特征點(diǎn)的保留比例，大幅提高算法的靈活度。

4.2 壓縮算法對(duì)比

為驗(yàn)證壓縮算法的有效性，將FPFH-FCM點(diǎn)云壓縮算法與基于曲率特征的點(diǎn)云壓縮算法[16]對(duì)比，分別使用兩種算法在同一實(shí)驗(yàn)數(shù)據(jù)、相同壓縮率下進(jìn)行實(shí)驗(yàn)，并從曲面重建效果和壓縮誤差兩個(gè)方面對(duì)比兩種算法的壓縮效果。

4.2.1 曲面重建效果對(duì)比

為了更加形象地描述點(diǎn)云模型的壓縮效果，常常需要進(jìn)行點(diǎn)云曲面重建。選取Poisson曲面重建算法，具體實(shí)現(xiàn)過(guò)程如下：(1)輸入有向點(diǎn)云數(shù)據(jù)；(2)建立八叉樹(shù)空間；(3)計(jì)算向量場(chǎng)；(4)解泊松方程求指示函數(shù)；(5)提取等值面。

圖7 基于曲率特征進(jìn)行70%的點(diǎn)云壓縮

圖8 兩種算法壓縮后曲面重建模型的細(xì)節(jié)對(duì)比

使用基于FPFH和FCM的點(diǎn)云壓縮算法將點(diǎn)云壓縮至15 272個(gè)點(diǎn)(ratio=70%)，壓縮后的曲面重建模型如圖7(a)所示；使用基于曲率特征的點(diǎn)云壓縮算法進(jìn)行同樣比例的壓縮，壓縮后的曲面重建模型如圖7(b)所示；兩種算法壓縮后曲面重建模型的細(xì)節(jié)對(duì)比如圖8(a)和圖8(b)所示，文中所提算法的重建模型可以完好地保留模型細(xì)節(jié)特征，而對(duì)比算法的重建模型有部分細(xì)節(jié)缺失。綜上所述，F(xiàn)PFH-FCM算法壓縮后的點(diǎn)云模型可在高曲率區(qū)域保留更多的特征信息，壓縮后的曲面重建模型可以更好的展現(xiàn)人體細(xì)節(jié)部位。

4.2.2 壓縮精度對(duì)比

為評(píng)估點(diǎn)云壓縮算法的質(zhì)量，需要衡量壓縮后點(diǎn)云與原始點(diǎn)云之間的壓縮精度。作者使用壓縮后點(diǎn)云與原始點(diǎn)云之間的Hausdorff距離作為壓縮精度的評(píng)價(jià)指標(biāo)。Hausdorff距離是描述兩組點(diǎn)集之間相似程度的一種量度，給定兩個(gè)有限集合A=a1,a2,…,an和B=b1,b2,…,bn，則這兩個(gè)點(diǎn)集合之間的Hausdorff距離定義為

H(A,B)=max(h(A,B),h(B,A))

(10)

在相同壓縮率下，分別比較兩種算法[17]獲得的壓縮后點(diǎn)云集合與原始點(diǎn)云集合之間的Hausdorff距離，結(jié)果如表1所示。

表1 Hausdorff距離對(duì)比

如表1所示，在不同壓縮率下，基于FPFH-FCM壓縮算法計(jì)算獲得的Hausdorff距離均小于對(duì)比算法計(jì)算獲得的Hausdorff距離，表明FPFH-FCM算法具有更好的壓縮精度。

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

作者提出一種基于FPFH-FCM的點(diǎn)云壓縮算法，利用點(diǎn)云FPFH特征在模型不同幾何位置的顯著分布差異，基于模糊C均值聚類(lèi)算法自適應(yīng)地將點(diǎn)云數(shù)據(jù)分為特征點(diǎn)集和非特征點(diǎn)集，然后建立壓縮準(zhǔn)則：對(duì)非特征點(diǎn)集進(jìn)行較大比例的壓縮，去除冗余點(diǎn)；對(duì)特征點(diǎn)集進(jìn)行較小比例的壓縮，盡量保留更多的特征點(diǎn)，以實(shí)現(xiàn)點(diǎn)云壓縮。同時(shí)，該算法可通過(guò)調(diào)整參數(shù)壓縮率ratio，自動(dòng)實(shí)現(xiàn)不同點(diǎn)云壓縮率的要求。

在實(shí)驗(yàn)仿真部分，分別從不同壓縮率下的壓縮結(jié)果、壓縮后模型的曲面重建效果、壓縮誤差3個(gè)方面對(duì)FPFH-FCM算法進(jìn)行評(píng)價(jià)與分析，并與文獻(xiàn)[17]中的算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果證明提出的FPFH-FCM壓縮算法能夠更好的保留重建模型的細(xì)節(jié)特征，具有更高的壓縮精度。

[1] 王英男,戴曙光.基于單位四元數(shù)法的激光點(diǎn)云拼接算法研究[J].電子科技,2015,28(6):202-204.

[2] 李玉.基于3D激光點(diǎn)云的無(wú)人車(chē)城市環(huán)境SLAM問(wèn)題研究[D].北京:北京理工大學(xué),2016.

[3] 劉軍,耿國(guó)華.文化遺址的三維真實(shí)感建模與虛擬展示技術(shù)[J].計(jì)算機(jī)工程,2010,36(20):286-290.

[4] 劉濤,徐錚,沙成梅,等.基于包圍盒法的散亂點(diǎn)云數(shù)據(jù)的曲率壓縮[J].科學(xué)技術(shù)與工程,2009,9(12):3333-3336.

[5] 姚頑強(qiáng),鄭俊良,陳鵬,等.八叉樹(shù)索引的三維點(diǎn)云數(shù)據(jù)壓縮算法[J].測(cè)繪科學(xué),2016,41(7):18-22.

[6] 吳祿慎,俞濤,陳華偉.基于自適應(yīng)橢圓距離的點(diǎn)云分區(qū)精簡(jiǎn)算法[J].計(jì)算機(jī)應(yīng)用與軟件,2016,11(2):42-45.

[7] 史寶全,梁晉,張曉強(qiáng),等.特征保持的點(diǎn)云精簡(jiǎn)技術(shù)研究[J].西安交通大學(xué)學(xué)報(bào),2010,44(11):37-40.

[8] 代星,崔漢國(guó),胡懷宇.基于曲率特征的點(diǎn)云快速簡(jiǎn)化算法[J].計(jì)算機(jī)應(yīng)用,2009,12(11):3030-3032.

[9] 韓江,江本赤,夏鏈,等.基于輪廓關(guān)鍵點(diǎn)的B樣條曲線(xiàn)擬合算法[J].應(yīng)用數(shù)學(xué)和力學(xué),2015,36(4):423-431.

[10] Rusu R B,Blodow N,Marton Z C,et al. Aligning point cloud data views using persistent feature histograms[C].CA,USA:IEEE/RSJ International Conference on Intelligent Robots and Systems,2008.

[11] 陸軍,彭仲濤.基于快速點(diǎn)特征直方圖的特征點(diǎn)云迭代插值配準(zhǔn)算法[J].國(guó)防科技大學(xué)學(xué)報(bào),2014,23(6):12-17.

[12] Rusu R B,Blodow N,Beetz M.Fast point feature histograms (FPFH) for 3D registration[C].PF,USA:IEEE International Conference on Robotics and Automation,IEEE Press,2009.

[13] Liu H,Hao K R,Ding Y S.New anti-blur and illumination-robust combined invariant for stereo vision in human belly reconstruction[J].Imaging Science Journal,2014,62(5):251-264.

[14] 劉歡,郝礦榮,丁永生,等.光照魯棒的抗模糊新組合不變矩圖像匹配方法[J].傳感技術(shù)學(xué)報(bào),2013,26(9):1258-1264.

[15] Pal N R,Pal K,Keller J M,et al.A possibilistic fuzzy C-means clustering algorithm[J].IEEE Transactions on Fuzzy Systems,2005,13(4):517-530.

[16] Song H,Feng H Y.A global clustering approach to point cloud simplification with a specified data reduction ratio[J].Computer-Aided Design,2008,40(3):281-292.

A Self-adaptive Simplification Algorithm for Point Cloud based on Fast Point Feature Histogram and Fuzzy Clustering

WANG Yinan1，HAO Kuangrong1,2，YANG Huanyu1,3

(1. School of Information Sciences and Technology,Donghua University,Shanghai 201602,China;2. Engineering Research Center of Digitized Textile &Fashion Technology,Ministry of Education,Shanghai 201620,China; 3.Shanghai Open University,Shanghai 200233,China)

Due to data redundancy in point cloud obtained by 3D scanning technology,this paper proposes a simplification algorithm for point cloud based on Fast Point Feature Histogram and Fuzzy C-Means(FPFH-FCM).Using the different distribution of FPFH in different geometric location of model,point cloud data is divided adaptively into feature point set and unfeature point set based on the FCM clustering algorithm. Then the two types of point set are compressed in different proportions,in order that the compressed point cloud can retain enough geometrical characteristics. For comparison experiments,we compress body point cloud model by our algorithm based on FPFH feature and comparing algorithm based on curvature feature respectively,then compare the effect of surface reconstruction of compressed point cloud，meanwhile，we evaluate the compression precision by Hausdorff distance of original point cloud and compressed point cloud,It is proved that our compression algorithm can preserve the details of the reconstruction model and get higher compression precision.

point cloud simplification;fast point feature histogram;fuzzy C-means algorithm;possion surface reconstruction; Hausdorff distance

TN911.73;TP391.41

A

1007-7820(2017)11-073-06

2016- 12- 24

國(guó)家自然科學(xué)基金(60775052)

王藝楠(1992)，女，碩士研究生。研究方向：計(jì)算機(jī)圖形學(xué)。郝礦榮(1964)，女，博士，教授，博士生導(dǎo)師。研究方向：圖像處理等。楊煥宇(1985-)，女，博士，講師。研究方向：三維點(diǎn)云數(shù)據(jù)處理。

10.16180/j.cnki.issn1007-7820.2017.11.020