基于特征顯著性的點云自適應精簡

張亦芳，李 立，劉光帥

(西南交通大學 機械工程學院，四川 成都 610031)

0 引 言

點云精簡是將密集的點云數據在保留模型特征的前提下進行簡化，以提高計算機處理的速度和后續重建曲面的光順性。目前，常用的點云精簡算法為基于傳統特征的點云精簡算法，例如曲率精簡法[1]、法向矢量精簡法[2]。該類算法以曲率或法向矢量作為來衡量局部細節特征和復雜度的標準，能夠很好保持點云的細節特征。但這類方法通常需要以人工設定閾值參數的方式進行特征識別，所設定的閾值對不同的點云模型難以達到同樣的理想精簡效果，導致這類算法適用性不廣。

與依賴于曲率、法向等底層特征方法不同，模擬人類視覺注意機制的顯著性檢測能夠自動捕捉不同場景中的重要信息。顯著性概念被廣泛應用于計算機視覺和圖形學任務中[3]。受二維顯著性檢測的啟發，三維顯著性檢測通?；谌诛@著性計算，即對全體點云或網格頂點特征聚類成簇，由簇的顯著性來計算得到全局顯著性。例如，Wu等[4]利用K-means聚類和近似最近鄰搜索將頂點分組成簇求解簇的顯著性，然后根據簇的顯著性插值得到單個頂點的全局顯著性。Tasse等[5]利用模糊聚類將點集分解成小簇，將每個簇的唯一性和空間分布定義一個點簇概率矩陣來計算每個點的全局顯著性。Ding等[6]利用體素連通性分割算法將點云分解為小簇計算簇的顯著性值后，利用隨機游走排序法計算簇中的每個點全局顯著性。這些全局顯著性的計算方法在保持簡單高效的同時，能夠得到穩定的顯著性映射，有效捕捉模型中大部分重要的視覺區域。已經被應用在三維數據處理視點選擇[6]、分割[7]和點云縮放[8]等各個方面。但全局顯著性不足之處在于丟失了簇內信息，降低了顯著性區分不同性質點云的能力，若直接應用在點云精簡上容易造成細節特征的丟失。

因此，針對現有點云數據精簡算法適應性不強，通過對全局顯著性算法的改進，提出一種基于特征顯著性的點云自適應精簡算法，算法在計算特征單詞全局顯著性基礎上融合了單詞類內顯著性生成顯著性詞典，并根據點云的顯著性值，通過配置不同的采樣率，實現對不同尺寸、形狀點云的自適應精簡。

1 FPFH特征提取

傳統的點云特征描述僅利用中心點的法向量、曲率等幾何屬性，未考慮與鄰域點的相對關系，難以準確反映物體幾何形狀和特性。而快速點特征直方圖(fast point feature histograms，FPFH)三維特征描述子，通過計算關鍵點及鄰域點的多個幾何屬性關系構建直方圖，能夠較好反映物體幾何形狀和特性[9]。因此，本文選用FPFH 作為點云特征描述子。提取方法如下：

首先，為每一個點對構建Darboux框架。如圖1所示，給定關鍵點pi及其法向量ni，領域點pj及其法向量nj。則Darboux框架的3個坐標軸(u,v,w)可通過這兩個點及它們的法向量構建得到，即

圖1 Darboux框架

u=ni

(1)

(2)

w=u×v

(3)

然后，基于上述所建立的Darboux框架，計算以下3個參數表達兩點之間幾何關系

α=v·nj

(4)

(5)

(6)

其中，α是點pj的法向量nj和坐標軸v的夾角，φ是向量ni和pij的夾角，θ是向量nj在wpju平面上的投影和坐標軸u的夾角。計算pi的k近鄰中所有點對之間的(α,φ,θ)，以統計的方式放進直方圖中，就得到了點的直方圖特征(simple point feature histograms，SPFH)。

最后，對點pi鄰域內的各點分別計算其鄰域內點的SPFH，得到最終的直方圖(FPFH)

(7)

式中：wj是pi到點鄰域內任意點pj的距離，作為計算權重。

本文采用FPFH 作為點云特征描述子時，將每個參數劃分為11個子區間，最終形成33維的統計直方圖作為點云特征描述，生成特征集合F={fi|i=1～N}。

2 特征顯著性計算

獲取點云FPFH特征集合后,特征顯著性計算的主要步驟為：首先對特征進行k均值聚類，每類作為一種單詞。然后由單詞全局顯著性和類內顯著性計算單詞顯著性，形成顯著性詞典。最后根據顯著性詞典軟編碼單點特征，獲得點云特征顯著性。

2.1 單詞全局顯著性計算

提取點云FPFH特征集合F={fi|i=1～N}后，首先對特征集合進行K-means聚類，將每個聚類中心作為一個單詞，得到特征詞典W={wi|i=1～k},詞典中不同單詞的顯著性不同。文獻[4]通過計算每個類別與其它類別的差異定義全局顯著性，這種顯著性的計算方法在保持簡單高效的同時，能夠有效捕捉點云模型中大部分重要的視覺區域。故參考此方法計算單詞全局顯著性，公式如下

(8)

式中：wi和wj分別表示特征詞典W={wi|i=1～k}中兩個不同的單詞,nj表示被編碼到wj下的點云的數量，d表示卡方距離。文獻[4]公式中的d采用的歐式距離，容易受點云模型中噪聲和采樣密度不均的影響。而文獻[6]中采用的卡方距離受噪聲影響較小，更適用于點云模型，故本文采用卡方距離度量單詞之間的距離d。定義如下

(9)

由此所得的全局顯著性的意義在于：一方面，通過對比度刻畫單詞間的差異，如果單詞wi與其它單詞wj區別較大，則代表此單詞具有較強的顯著性。另一方面，通過稀有性來刻畫單詞間的差異，如果其它單詞內部點云數量較多，則此單詞內的點云數量較少，內部點云數量較少的單詞具有較強的顯著性。

2.2 單詞類內顯著性計算

全局顯著性僅考慮了不同單詞間的區別，并未考慮單詞內部點云特征的分布情況。單詞內部分布如果分散，則表示包含的信息豐富，顯著性強。反之，分布如果集中，則表示包含的信息少，顯著性弱。而VLAD[10](vector of locally aggregated descriptors)可以描述單詞內部分布情況。在Bow(bag-of-words)基礎上改進而來的VLAD計算了每個局部特征與它對應的聚類中心的殘差，能夠有效解決類內的信息缺失問題。因此，利用VLAD特征來定義單詞內部的顯著性。

根據單詞詞典及點云的單詞編碼第k個單詞的VLAD特征作為類內顯著性

(10)

將VLAD(k)記為Sck,融合全局顯著性特征Sgk，構成最終特征顯著性

Sk=Sgk+λSck

(11)

由此構成顯著性詞典S={sk|k=1～K}。

式中，λ為組合權重，考慮到在顯著性計算中，全局顯著相比于類內顯著性仍是主要影響因素，故用λ來調節單詞內部顯著性對最終顯著度的貢獻比時應取小值，本文λ取0.2。

從式(11)可看出，最終的特征顯著性既考慮了單詞間的差異，也綜合了單詞內部點云特征分布情況。相比于只考慮全局顯著性的特征顯著度計算方式，這種融合了類內差異的方法，能夠提高顯著性區分不同性質點云的能力，增強顯著性描述相似區域點云的區分性。

2.3 特征顯著性

獲得單詞顯著性詞典S后，根據點云特征fi與單詞wk的距離，編碼特征顯著性。編碼方法中傳統的硬性表決編碼方法只選擇完全激活與其最相似的一個視覺單詞來表達特征，忽略了與其它單詞的相似性，容易丟失部分點云的特征信息。而局部軟編碼法[10]選擇激活與鄰近內k個相似的視覺單詞來表達特征，能夠更充分地保留點云特征信息。故本文采用局部軟編碼方式，選擇激活與點云特征相似的Ni個單詞編碼特征顯著性，表示如下

(12)

(13)

綜上，點云特征顯著性算法步驟具體如下：

算法1：點云特征顯著性計算

輸入：點云模型每個點的FPFH特征向量fi

輸出：點云模型每個點的特征顯著性Sfi

(1)輸入點云的FPFH特征向量集，K-means聚類生成碼本詞典：W={wk|i=1～k}；

(2)根據單詞間的差異，由式(8)計算單詞全局顯著性Sgk；

(3)考慮單詞內點云的分布，由式(10)計算單詞類內顯著性Sck；

(4)融合全局顯著性和類內顯著性由式(11)得到顯著度詞典S={sk|k=1～K}；

(5)采用局部軟編碼方式，由式(12)計算所有點云的特征顯著性Sfi。

3 點云自適應精簡

在點云模型中存在平緩和變化復雜的不同區域，如果采用同一個策略對整個點云數據進行精簡，則很有可能造成特征信息的缺失。因此，為了保證精簡后特征的完整性，在不同區域應采用不同的精簡策略。傳統的點云精簡算法采用的精簡策略一般是根據曲率、法矢等幾何屬性，通過設定某個固定的閾值對點云進行精簡，這樣人為選取一個閾值會導致算法魯棒性較差，選取的閾值可能對于某一種點云模型處理得比較理想，換了另一種點云后可能難以達到理想的精簡效果。針對此類問題，本文提出基于特征顯著性的自適應精簡算法。精簡原則是對點云均勻網格化后，根據每個網格內的特征顯著性的不同進行不同程度的精簡，特征顯著性高代表此網格內的點位于特征明顯區域的可能性越大，采樣率應高，反之，顯著性越低，采樣率應小。算法的優勢是能自適應計算每個網格內的采樣率，無需設定相關的參數。具體過程如下：

(14)

然后，計算每種單詞下點云數量的占比hk

(15)

式中：nk表示被分配到k類單詞的點的數量，N表示點云總數。

(16)

此外，在對點云進行精簡的過程中為確保特征信息的完整性，考慮到僅單獨根據顯著性精簡可能會丟失部分特征細節區域。而利用點云的曲率能夠快速檢測到這些細節區域，故將點云曲率作為采樣率設置的補充條件。在計算網格采樣率后，若檢測到網格內存在曲率較大的點，說明網格內點云位于特征區域的可能性大，則將網格采樣率置為百分百，以保留此區域的特征信息。由于在計算點云特征FPFH階段，利用(principal component analysis，PCA)算法計算點的法向量時可同時得到曲率，故此過程并不增加時間。

綜上，點云自適應精簡算法具體步驟如下：

算法2：點云自適應精簡

輸入：點云模型每個點的特征顯著性Sfi

輸出：精簡點云

(1)將點云均勻網格化；

(3)由式(15)計算單詞內點云占比hk；

(4)由式(16)計算網格采樣率p_sample；

(5)檢測點云的曲率，若存在大于0.1的點，將此網格采樣率p_sample置為百分之百；若無則采用p_sample對網格點云數據進行精簡；

(6)循環(3)到(5)，直至精簡完所有網格，輸出精簡點云。

經過以上計算，算法以特征顯著性指導點云精簡，在特征顯著性高的特征區域保留更多的點，在特征顯著性低的平坦區域精簡更多的點，無需設定相關閾值，實現了點云的自適應精簡。該算法完整流程如圖2所示。

圖2 本文算法流程

4 實驗結果與分析

使用Matlab對算法進行編程，計算機配置為Win 10小系統，Intel Corei5、8 G內存和NVDIA GeForece GTX960M顯卡。實驗用到的點云數據來自斯坦福大學建立的3D點云數據庫，均為PLY格式。

實驗分為兩部分。首先，為驗證類內顯著性算法的有效性，在不同類型模型下應用本文方法和文獻[4]的方法，對比顯著性檢測的效果。然后，為驗證自適應精簡的有效性，在不同類型模型下應用包圍盒法、文獻[11]法、文獻[12]法以及本文算法，對比精簡效果并分析精簡誤差及效率。

4.1 特征顯著性實驗

圖3和圖4中的圖(a)是原始點云數據，圖(b)是僅利用全局顯著性算法計算每個點的特征顯著性的效果，圖(c)是融合全局和類內顯著性算法每個點的特征顯著性效果。圖中灰度值從低到高代表特征顯著性依次升高。從圖3Skull模型可看出，圖3(b)中僅利用全局顯著性計算點的特征顯著性時，眼眶、鼻骨和牙齒等區域顯著性相似，且與顴骨及下顎骨區分度不高，而圖3(c)中融合了類內顯著性時，額骨的裂痕、牙齒、顴骨及下顎骨等不同區域的顯著性區分明顯，基本無混合。圖4(a)中可看出Cow模型顯著性高的特征區域主要集中在面部，而圖4(c)中面部中的眼睛和嘴巴的區分度和顯著性明顯高于圖4(b)。由此可驗證本文融合全局顯著性和類內顯著性的算法能夠提高顯著性區分不同性質點云的能力，增強顯著性描述相似區域點云的區分性。

圖3 Skull模型顯著性效果

圖4 Cow模型顯著性效果

4.2 自適應精簡效果對比實驗

為驗證本文算法的自適應精簡效果，在不同類型模型下應用包圍盒法、文獻[1]法、文獻[11]法、文獻[12]法和本文精簡算法對比精簡結果，并分析精簡誤差及效率。文獻[1]屬于曲率閾值法，該算法將點云聚類后，將數據點之間的最大曲率差大于設定閾值不斷的迭代細分以保留特征點。文獻[11]和文獻[12]都是基于顯著性的點云精簡，其中文獻[11]的顯著性檢測是基于無向加權圖，文獻[12]的顯著性檢測是基于法向量。將這5種算法應用于3種不同類型的模型進行精簡：一種為Chair模型，原始點云數據為49 960，該模型數據量較小,實際尺寸大，特征細節較少；一種為Hand模型，原始點云數據為327 323，數據量密集，實際尺寸較小，特征細節較多；一種為Dragon模型，原始點云數據為437 645，數據量大,實際尺寸小，細節特征豐富。為了增強顯著性的區分性，聚類參數k取20，其它參數與4.1相同。將文獻[1]方法閾值設置為1。定義精簡比為精簡掉的點數與原始點數的比值，將其保持在90%左右。圖5、圖6和圖7為實驗結果。

圖5 Chair模型點云不同精簡算法精簡結果

圖6 Hand模型不同精簡算法精簡結果

圖7 Dragon模型不同精簡算法精簡結果

從圖5Chair模型點云的精簡結果來看，由于椅子模型本身數據量不大，特征信息不豐富，除了包圍盒法在比較平坦的區域還是存在很多的冗余信息，文獻[1]法、文獻[5]法、文獻[11]法還是本文方法都可以較大程度地去除冗余并有效保留點云特征。但文獻[11]、文獻[12]和本文基于顯著性的點云精簡算法取得的視覺效果更好。

從圖6Hand模型點云的精簡結果來看，包圍盒法精簡效果整體較為均勻，但特征信息丟失嚴重大，精簡效果差。文獻[1]法能夠在一定程度上較好保留手骨模型的特征，但在指尖等細微特征區域信息丟失嚴重，精簡效果一般。文獻[11]法、文獻[12]法和本文算法精簡后的點云在關節等特征區域保留了大量的數據點，在骨頭等非特征區域保留數據點相對較少，特征區分明顯，精簡效果優于包圍盒法和文獻[1]法。但本文算法在手骨關節處保留了更多的特征點，視覺效果優于文獻[11]和文獻[12]。

從圖7Dragon模型點云的精簡結果可看出，當面對數據量大、特征豐富的點云模型時，包圍盒法在精簡時由于沒有考慮點云的特征分布，導致龍爪龍頭等特征信息丟失嚴重，精簡效果差。文獻[1]法雖然考慮了點云的曲率特征，但需設定合適的閾值，從精簡效果看該閾值顯然不適用于此模型，以致冗雜位于曲率高的區域但不是特征的點云，例如龍身；以致丟失對位于特征區域但曲率不高的細節特征，例如龍的面部特征。文獻[11]法、文獻[12]法和本文算法精簡效果明顯優于前兩種算法，但文獻[11]法和文獻[12]法已經開始丟失某些細節和邊緣特征，例如龍眼、龍牙、尾巴的邊緣等細節部位，而本文算法在這細節特征區域均保留完整。故，本文精簡效果優于包圍盒法、文獻[1]法、文獻[11]法和文獻[12]法。

從以上實驗結果可看出，在面對不同類型的模型時，包圍盒法能獲得均勻點云的效果，但容易丟失特征；文獻[1]法需人工調試合適的閾值，才有可能獲取合適的精簡效果；文獻[11]法和文獻[12]在面對細節特征豐富的點云模型時可能會造成細節特征的丟失。而本文算法對不同的模型均獲得良好的精簡結果，驗證了本文基于特征顯著性的點云自適應精簡在能夠保留視覺顯著性高的特征區域的同時，對不同模型均具有適用性。

為了更客觀地評估點云精簡后的物體描述能力,記錄多個不同類型的模型誤差。誤差計算方法為求取精簡點云與原始點云的最大誤差和平均誤差[5]，表達式分別為

(17)

式中：d(g,S*)表示原始曲面S上采樣點g到精簡點云曲面S*上投影點g*的歐式距離。

多個模型精簡誤差見表1，當模型簡單時，包圍盒法、文獻[1]法、文獻[11]法、文獻[12]法和本文方法的精簡誤差相差不大，但當模型復雜時，本文方法的最大誤差和平均誤差遠小于其它4種方法，更好地保留了模型特征，但由于本文算法需進行單詞類內特征顯著性計算等算法流程，計算量較大，所以運行時間要多于其它方法，具體結果詳見表1。

表1 精簡算法結果對比

5 結束語

提出了一種基于特征顯著性的點云自適應精簡算法，算法在計算點云FPTP特征聚類生成單詞后，在生成顯著性詞典的過程中，為避免單詞內部特征信息的缺失，在計算單詞全局顯著性基礎上融合單詞類內顯著性生成最終的顯著性詞典后，采用軟編碼的方式對點云進行特征顯著性計算，并利用點云的特征顯著性實現了特征顯著性越強的區域，采樣率越高的自適應精簡。實驗結果顯示，本文的融合全局和類內顯著性的顯著性檢測算法相比只計算全局顯著性的顯著性檢測算法，提高了顯著性區分不同性質點云的能力，增強了顯著性描述相似區域點云的區分性。利用特征顯著性對點云進行精簡時，與其它4種精簡算法相比，能夠更好保留模型視覺特征明顯區域的同時，對不同類型的點云具有適應性。