基于半球形鄰域的激光雷達(dá)點云局部特征提取

蔣 博 馬燕新 萬建偉 何 峰 許 可 陳沛鉑

（1.中國人民解放軍國防科技大學(xué)電子科學(xué)學(xué)院，湖南長沙 410073；2.中國人民解放軍國防科技大學(xué)氣象海洋學(xué)院，湖南長沙 410073；3.海洋探測技術(shù)湖南省重點實驗室，湖南長沙 410073；4.中國人民解放軍75833部隊，廣東廣州 510000）

1 引言

三維點云是通過激光雷達(dá)等掃描設(shè)備對物體表面進(jìn)行掃描，所采集到的一系列三維坐標(biāo)的集合。相比于二維數(shù)據(jù)，三維數(shù)據(jù)提供了更為豐富的空間、距離、顏色、強度等信息，使得基于三維數(shù)據(jù)的目標(biāo)識別精度更高。在三維目標(biāo)識別過程中，特征描述是其中最為關(guān)鍵的一步，一個好的特征描述子能夠以極少的特征維度來最大限度的表征目標(biāo)，為后續(xù)高效準(zhǔn)確的特征匹配奠定基礎(chǔ)。

基于手工特征的方法主要通過分析提取物體的特征點的幾何屬性［1］、形狀屬性［2］、結(jié)構(gòu)屬性［3］或者多種屬性組合等特征進(jìn)行對比、學(xué)習(xí)，從而完成目標(biāo)的識別與分類［4］。在現(xiàn)有的手工特征描述算法中基于直方圖的方法得到了最為廣泛地研究。這類方法首先利用點云的某些信息（如點坐標(biāo)、幾何屬性）定義直方圖的一個或多個維度，然后采用鄰域點的幾何或拓?fù)錅y量值（如點數(shù)、網(wǎng)格面積）對直方圖中的相應(yīng)單元格進(jìn)行累加從而獲得直方圖統(tǒng)計以實現(xiàn)對局部表面的描述。Zhong［5］首先對鄰域點的協(xié)方差矩陣進(jìn)行特征值分解來構(gòu)建局部參考坐標(biāo)系（Local Reference Frame，LRF），進(jìn)而采用離散球面網(wǎng)格將球形鄰域空間劃分成均勻分布的柵格，并通過統(tǒng)計每個柵格單元內(nèi)的點密度加權(quán)和從而獲得內(nèi)蘊形狀特征描述子（Intrinsic Shape Signatures，ISS）。Frome 等［6］采用關(guān)鍵點p的法向量n作為局部參考坐標(biāo)軸，并將球形鄰域空間劃分成一系列單元格從而獲得三維形狀上下文特征描述子（3D Shape Context，3DSC），由于只采用關(guān)鍵點的表面法向量作為參考坐標(biāo)軸，所以在繞法向量的旋轉(zhuǎn)方向上具有模糊性，因此需要在每個關(guān)鍵點處計算多次特征，使得該特征描述子占用內(nèi)存大，且特征匹配性能較低。Tombari 等［7］對3DSC 進(jìn)行了改進(jìn)，通過給每個關(guān)鍵點賦予一個可重復(fù)且唯一確定的LRF以獲得單值形狀上下文特征描述子（Unique Shape Context，USC），大幅提升了3DSC 特征描述子的效率。Tombari等［8］通過將球形鄰域空間進(jìn)行柵格化，在每個柵格單元上，依據(jù)落入該單元的點的法向量與關(guān)鍵點法向量的夾角將這些點累加到一個直方圖中，最后將所有柵格單元內(nèi)的直方圖串聯(lián)起來以獲得總的方向直方圖簽名特征描述子（Signature of Histograms of Orientations，SHOT）。

上述方法通過使用唯一的LRF、不同的鄰域劃分方法、不同的特征統(tǒng)計量等方式提出了不同的特征描述子。但對于鄰域的選取卻始終單純采用以關(guān)鍵點為圓心，一定距離為半徑的球形作為鄰域。而實際中關(guān)鍵點附近的鄰域點僅分布在球形鄰域中的少部分區(qū)域，這使得在將整個球形進(jìn)行柵格劃分后，其中的柵格會產(chǎn)生許多空置。而這些多余的空置柵格會增加特征描述子的長度和占用內(nèi)存，此外在特征匹配階段還會花費更多的時間。

因此本文提出了半球形鄰域選取方法并在估計LRF 時，對互相關(guān)矩陣增加了密度權(quán)重以提升點密度較大區(qū)域的權(quán)重，以此將注意力放在描述性更強的區(qū)域，使描述子鑒別力得到提升。此外，本文基于半球形鄰域提出一種新的特征描述子半球單值形狀上下文特征描述子（Hemispheric Unique Shape Context，HUSC）描述子。通過在公開數(shù)據(jù)集上的一系列對比試驗表明，HUSC 特征描述子在準(zhǔn)確率與其他描述子接近的情況下，計算特征的時間花費和特征的大小，均遠(yuǎn)遠(yuǎn)小于其他特征描述子。大幅度降低的特征描述子的維度，使得其在建立特征庫時的內(nèi)存占用大大減少，同時也可減少在后續(xù)的特征匹配、識別等任務(wù)中花費的時間。

2 半球形鄰域方法

本文所提特征描述子計算過程主要包含兩部分：LRF 構(gòu)建和局部特征描述子計算。首先通過隨機采樣或者關(guān)鍵點檢測方法以獲得關(guān)鍵點并得到其局部鄰域點，再通過計算關(guān)鍵點局部鄰域的互相關(guān)矩陣的特征值構(gòu)建出LRF。特征描述子的實質(zhì)是對關(guān)鍵點鄰域信息的編碼［9］。一個好的特征描述子不僅應(yīng)該具有較高的分辨能力，還應(yīng)對噪聲、網(wǎng)格分辨率變化等魯棒。本文所提算法構(gòu)建的關(guān)鍵點的LRF，其z軸為關(guān)鍵點的法向量，xy 平面為關(guān)鍵點的切平面，以此切平面為界，選取包含點較多的一半球形作為鄰域，再將該半球按照方位角、極角、徑向三個維度劃分為多個柵格，統(tǒng)計落入每個柵格中的點數(shù)加權(quán)和就得到了該關(guān)鍵點處的HUSC特征。

2.1 局部參考坐標(biāo)系

局部參考坐標(biāo)系（LRF）是局部表面姿態(tài)歸一化的核心，它具有可重復(fù)性和唯一性［10］。通過將局部表面的點變換到該局部參考坐標(biāo)系下，可實現(xiàn)旋轉(zhuǎn)不變性。本文在Tombari［8］等人所提出的局部參考系構(gòu)建方法的基礎(chǔ)上，增加了鄰域點附近的點密度加權(quán)，提升了算法對點云分辨率變化時的魯棒性。具體而言，通過對關(guān)鍵點局部鄰域的互相關(guān)矩陣M進(jìn)行特征值分解，得到LRF 的總體最小二乘估計，其中M可表示為：

式中，k為鄰域中點的個數(shù)，pi為第i個鄰域點的位置坐標(biāo)，為鄰域內(nèi)所有點的坐標(biāo)均值。為了增強LRF 在雜亂環(huán)境中的可重復(fù)性和魯棒性，根據(jù)鄰域點相對于關(guān)鍵點的距離進(jìn)行加權(quán)，越遠(yuǎn)的點分配較小的權(quán)重，近的點則分配較大的權(quán)重。因此式（1）可改寫為：

式中，R為局部鄰域半徑，p為關(guān)鍵點坐標(biāo)，di=‖pi-p‖2為鄰域點到關(guān)鍵點的歐式距離。Z為權(quán)重，可表示為：

由于在實際應(yīng)用中，相同目標(biāo)點云的分辨率會因為掃描角度和掃描精度不同而變化，同時在點云密度較大的地方，往往包含更多的信息，因此根據(jù)鄰域點附近的相對密度進(jìn)行加權(quán)。密度越大的點分配較大的權(quán)重，密度越小的點分配較小的權(quán)重。這樣不僅可以保留更多有用的信息，當(dāng)分辨率變化時，也可使算法更加穩(wěn)健，因此式（2）可改寫為：

式中，σi為鄰域點附近的局部點密度，σ為關(guān)鍵點鄰域內(nèi)的點密度，其中點密度被估計為以鄰域點pi為球心一定距離為半徑為的球內(nèi)點的數(shù)量。則模糊的LRF 的三個單位向量分別對應(yīng)M3的三個特征向量，而法向量對應(yīng)著M3矩陣的最小特征值。為得到唯一的LRF，需要進(jìn)行符號消歧。具體而言，令LRF的正方向始終指向點數(shù)較多的方向。

式中，x+為對M3矩陣進(jìn)行特征值分解所得到的特征向量，x-為該特征值的相反向量，∧為并邏輯運算。代表對應(yīng)方向上鄰域內(nèi)點的個數(shù)。若大于等于，代表鄰域范圍內(nèi)與x+同向的點更多，則取x+的方向為局部參考坐標(biāo)的正方向，反之取x-的方向為局部參考坐標(biāo)的正方向。

2.2 半球形鄰域

點云是由激光雷達(dá)等掃描設(shè)備獲取的物體表面一系列點的集合，由于光無法穿透物體，其內(nèi)部并不包含數(shù)據(jù)點。因此點云可以形容為反映物體表面形狀的“空殼”。將球形鄰域看作一個球形空殼，讓它的球心與點云的某一點重合，以模擬關(guān)鍵點處的球形鄰域。由于點云內(nèi)部沒有數(shù)據(jù)點，因此點云中的每個點都可以視為邊緣點，無論該點是處于凹面還是凸面，該點處的切平面總能將該球形空殼劃分為兩個半球：其中的一個半球在大多數(shù)情況下幾乎不包含任何鄰域點。如圖1為球形鄰域和半球形鄰域的二維示意圖。這些空置的柵格不包含任何有效的鄰域信息，對特征描述子的識別率幾乎無影響，但卻會增加計算特征描述子時的時間和特征的內(nèi)存占用大小，同時也會使得特征匹配的速度大大降低，影響識別效率。而采用切平面劃分的半球形鄰域，在最大限度保留描述性的同時，可大幅度降低特征的冗余并提高目標(biāo)識別的效率。

本文所提的半球形鄰域計算過程如下，首先，使用上一節(jié)所提的方法計算關(guān)鍵點P的LRF，而后將局部鄰域內(nèi)點的坐標(biāo)變化到該局部參考坐標(biāo)系中。根據(jù)局部參考坐標(biāo)系的建立過程可以分析得出，在以關(guān)鍵點P為原點的局部參考坐標(biāo)系中，z軸對應(yīng)著以總體最小二乘估計所得的法向量，而x軸和y軸在以z軸為法線經(jīng)過關(guān)鍵點P的切平面內(nèi)，因此無需額外再計算關(guān)鍵點的切平面。又因為z軸的正方向始終指向點多的方向，所以絕大部分鄰域點均在切平面以上，因此丟掉那些位于切平面以下的點，對描述子的準(zhǔn)確率影響并不大。而后采用方位角、極角、徑向半徑將該半球形鄰域劃分為多個柵格：其中方位角[0，360°]被Φ={φ1···φL}均勻劃分為L份、極角[0，90°]被Θ={θ1···θK}均勻劃分為K份、徑向被R={R1···RJ}按照對數(shù)距離劃分為J份，總共被劃分為J×K×L個柵格。其中第一個徑向劃分刻度R0是最小的徑向半徑rmin，RJ是最大的徑向半徑rmax。半徑的邊界由下面公式求得：

使用對數(shù)距離，使得描述子對于距離的變化更加魯棒。由于越靠近球心的柵格越小，因此采用最小徑向半徑（rmin＞0）來避免在距離球心較近的地方描述子對于細(xì)微的變化過度敏感。此外，對半徑區(qū)間[Rj，Rj+1]、方位角區(qū)間[φj，φj+1]和仰角區(qū)間[θj，θj+1]內(nèi)與P有關(guān)的每一點Pi計算一個權(quán)重ω(pi)。點Pi的權(quán)重由下面公式計算得出：

其中V(j，k，l)表示柵格的體積，ρi表示柵格鄰域點的密度。用柵格體積進(jìn)行歸一化降低了柵格尺寸在隨著徑向和極角方向的變化對算法穩(wěn)健性的影響。而使用體積的立方根可保留顯著的鑒別能力，同時使描述子對噪聲具有魯棒性。局部點密度ρi被估計為以Pi為球心在半徑為δ的球內(nèi)點的數(shù)量。最后統(tǒng)計每個柵格中點數(shù)的加權(quán)和以提取特征直方圖并得到HUSC特征。

3 實驗結(jié)果

為驗證所提半球形鄰域的有效性和密度加權(quán)對描述子鑒別力的提升，本文將半球形鄰域應(yīng)用于傳統(tǒng)方法中識別效果較好的USC 描述子中，并稱采用半球鄰域的描述子為HUSC 描述子。為驗證密度加權(quán)對描述子魯棒性的提升，本節(jié)將在計算LRF 時將添加密度加權(quán)的描述子稱為HUSC-W描述子。而后在Bologna 數(shù)據(jù)集［11］和3DMatch［12］數(shù)據(jù)集上進(jìn)行對比實驗，并用Precision-Recall 曲線（Precision Recall Curve，PRC）作為局部特征描述子鑒別力的評價標(biāo)準(zhǔn)，其平均精度可通過計算PRC曲線線下面積（AUC）得到［13］，PRC 計算過程如圖2。

式中，Nr表示正確的匹配點數(shù)，Nm表示匹配點數(shù)，NT表示特征總數(shù)。

3.1 半球形鄰域?qū)υ肼暤聂敯粜?/h3>

為分析半球形鄰域?qū)υ肼暤姆€(wěn)健性，本文在Bologna［11］和3DMatch［12］數(shù)據(jù)集上按照［7］中實驗所用參數(shù)，在模型上分別添加方差為0.1、0.2、0.3 倍點云網(wǎng)格分辨率的高斯噪聲對USC、HUSC 和HUSC-W 特征描述子的PRC 曲線進(jìn)行對比，驗證了半球形鄰域?qū)υ肼暤聂敯粜?。實驗環(huán)境為：CPU 為2.2 GHz 的Core i7-8750H，RAM 為16 GB，計算機系統(tǒng)為Ubuntu18.04，軟件為Python和open3d開源庫。

Bologna 數(shù)據(jù)集由六個Stanford 3D Scanning Repository 中的物品模型（Armadillo、Asia Dragon、Bunny、Dragon、Happy Buddha、Thai Statue）以及由原始模型進(jìn)行旋轉(zhuǎn)、平移等剛性變換后的得到的45個場景組成。場景中包含了背景干擾以及物體的姿態(tài)變化。模型與場景之間的真是旋轉(zhuǎn)和平移關(guān)系已知。3DMatch 數(shù)據(jù)集收集了來自于62 個場景的數(shù)據(jù)，包含8 組由RGB-D 相機重建的室內(nèi)場景模型，常用于3D 點云的關(guān)鍵點檢測、特征描述、點云配準(zhǔn)等任務(wù)。以上數(shù)據(jù)集均包含多個不同角度得到的同一物體或場景的數(shù)據(jù)。

在上述數(shù)據(jù)集上，三種描述子的PRC 如圖3、圖4所示。

由圖3、圖4，可得到以下結(jié)論：

（1）在無噪聲的情況下，三種特征描述子性能相當(dāng)，均具有較高的召回率和精度，如圖3（a）和圖4（a）所示。

（2）在噪聲環(huán)境下，三種特征描述子的精度均出現(xiàn)了下降，其平均精度如表1、表2 所示，三種描述子對噪聲均非常穩(wěn)健。HUSC 特征描述子在采用半球形鄰域仍然對噪聲穩(wěn)健是因為它所去掉的鄰域基本為不包含信息的空置部分，而包含信息的鄰域卻完整地保留了下來，因此其鑒別力幾乎未受影響。需要指出的是：當(dāng)關(guān)鍵點位于某些特殊的復(fù)雜曲面上時，半球形鄰域會出現(xiàn)模糊的情況，如當(dāng)切平面兩邊的點數(shù)相近時。此外，由于LRF 的估計不可避免存在一定偏差，也會導(dǎo)致半球形鄰域在某些關(guān)鍵點處會丟失部分信息，這也是基于半球形鄰域的描述子精度有所下降的主要原因，但在一副點云中這樣的特殊關(guān)鍵點相對較少，且單個特征點的失效不會影響整個情況，因此對精度的影響有限。

表1 不同噪聲中3種特征提取算法平均精度比較（Bologna）Tab.1 The comparison of average precision of 3 feature extraction methods in different noise(Bologna)

表2 不同噪聲中3種特征提取算法平均精度比較（3DMatch）Tab.2 The comparison of average precision of 3 feature extraction methods in different noise(3DMatch)

（3）具有密度加權(quán)的HUSC-W 特征描述子比HUSC 特征描述子擁有更高的精度和召回率。這是因為密度加權(quán)會為密度較大的區(qū)域分配更高的權(quán)重，而密度較大的部分往往包含更多信息，可以對局部鄰域進(jìn)行更為細(xì)致的描述，因此密度加權(quán)會提升描述子的鑒別力。

3.2 半球形鄰域?qū)?shù)據(jù)分辨率變換的穩(wěn)健性

為測試特征描述子在數(shù)據(jù)分辨率變化下的穩(wěn)健性，將Bologna和3DMatch數(shù)據(jù)集中的無噪聲場景點云降采樣至原分辨率的1/2、1/4、1/6 和1/8，得到特征描述子在不同數(shù)據(jù)分辨率下的RPC 曲線如圖5、圖6 所示，平均精度如表3、表4 所示。可以看出隨著分辨率下降，三種特征描述子精度均保持在較高的水平，這是因為兩種描述子在特征計算時均根據(jù)鄰域點密度進(jìn)行了加權(quán)和歸一化處理。此外，HUSC-W 描述子由于在計算LRF 階段時對互相關(guān)矩陣加入了密度加權(quán)，使得包含信息更豐富的大密度區(qū)域更多地被計入互相關(guān)矩陣中，使得其鑒別力更強。同時，當(dāng)點云分辨率變化時，該密度加權(quán)也會相應(yīng)的變化，因此HUSC-W 描述子較HUSC 描述子更為穩(wěn)健。

表4 不同數(shù)據(jù)分辨率下2種特征提取算法平均精度比較（3DMatch）Tab.4 The comparison of average precision of 2 feature extraction methods in different mesh resolutions（3DMatch）

表3 不同數(shù)據(jù)分辨率下2種特征提取算法平均精度比較（Bologna）Tab.3 The comparison of average precision of 2 feature extraction methods in different mesh resolutions（Bologna）

3.3 半球形鄰域的高效性

為驗證半球形鄰域?qū)\算效率和存儲空間的優(yōu)化，本文對Bologna 數(shù)據(jù)集中的六個原始模型建立特征庫，分別測試USC 和HUSC 兩種特征描述子建立特征庫所占用的內(nèi)存，而后再利用該模型庫進(jìn)行特征匹配比較兩種描述子所花費的時間。具體而言，對于一個模型，首先對該模型點云進(jìn)行均勻采樣以獲得一系列種子點，由于空間上鄰近的關(guān)鍵點具有相似的特征描述子，因此采用分辨率控制策略對種子點做進(jìn)一步篩選以獲得最終的關(guān)鍵點［14］。對于每一個關(guān)鍵點Pm，計算其LRF 以及特征描述子fm。最后，將所有模型特征描述子fm存儲在模型庫中。該模型庫的內(nèi)存占用大小便可反應(yīng)特征描述子的大小。而后，將噪聲、旋轉(zhuǎn)分別加入原始模型后再次按照上述步驟計算得到場景特征描述子fs，并進(jìn)行局部特征匹配。用六個模型完成特征匹配的平均時間來反應(yīng)特征描述子的效率。兩種特征描述子分別建立的模型特征庫大小以及特征匹配花費時間如表5所示。

從表5 可知，HUSC 和USC 特征描述子在分別對相同目標(biāo)進(jìn)行特征提取建立模型庫，HUSC 特征描述子所需空間為8.6 MB，較USC 特征描述子的17.3 MB 節(jié)省50.3%的內(nèi)存。且在特征匹配時，HUSC 特征描述子花費時間比USC 特征描述子縮短48.3%。另外，在建立模型特征庫時，HUSC 特征描述子花費時間71.86 s，USC 特征描述子花費時間91.54 s。HUSC 特征描述子之所以如此高效，是因為半球形鄰域較球形鄰域減少了一半幾乎不包含信息的空間，使得它的冗余柵格較USC描述子大幅度減少，并讓特征維度得以降低。更低的特征維度意味著更快的特征運算和匹配速度，同時內(nèi)存占用也相應(yīng)減少。而隨著三維數(shù)據(jù)采集設(shè)備的精度的提高和場景的不斷擴大，點云的數(shù)據(jù)量也會劇增，本文所提方法將節(jié)省巨大的內(nèi)存和算力資源。

表5 2種特征提取算法建立模型特征庫占用內(nèi)存、特征匹配花費時間Tab.5 The runtime of feature matching and memory occupied by feature library of 2 feature extraction methods

3.4 HUSC與PCA特征壓縮算法對比

為比較改進(jìn)鄰域的HUSC算法與直接對特征進(jìn)行壓縮的經(jīng)典特征壓縮算法的性能，本文將原始USC描述子通過PCA 算法進(jìn)行降維，并繪制PRC曲線。其在不同噪聲和點云分辨率的條件下與HUSC描述子的實驗對比結(jié)果如圖7、圖8所示。

由圖可知：

（1）HUSC 與PCA 兩種算法隨著噪聲增加和點云分辨率的下降，精度均呈下降趨勢，但HUSC的精度始終比PCA更高。

（2）PCA 算法在有噪聲的環(huán)境中，精度出現(xiàn)劣化較之分辨率變化的情況更為嚴(yán)重，這是由于PCA算法采用l2范數(shù)平方作為距離度量準(zhǔn)則，導(dǎo)致算法的魯棒性差，對噪聲敏感。

HUSC 和經(jīng)過PCA 降維后的特征占用內(nèi)存，以及特征匹配時間如表6 所示，由該表可以看到PCA算法能夠?qū)μ卣鬟M(jìn)行有效的降維，其特征內(nèi)存降至6.4 MB。同時特征匹配的時間較HUSC 有進(jìn)一步降低，這是由于PCA 降低了特征維度，使得特征匹配的總量減少。

表6 2種算法建立模型特征庫占用內(nèi)存、特征匹配花費時間Tab.6 The runtime of feature matching and memory occupied by feature library of 2 methods

4 結(jié)論

本文通過將半球形鄰域應(yīng)用在USC 描述子中提出了更具效率的HUSC 特征描述子。在Bologna數(shù)據(jù)集上進(jìn)行的實驗結(jié)果為：在有噪聲干擾時，HUSC 特征描述子的平均精度為92.2%，USC 特征描述子的平均精度為94.9%。在分辨率變化時，HUSC 特征描述子的平均精度為93.0%，USC 特征描述子的平均精度為94.8%。在3DMatch數(shù)據(jù)集上的實驗結(jié)果為：在有噪聲干擾時，HUSC 特征描述子的平均精度為92.4%，USC 特征描述子的平均精度為95.4%。在分辨率變化時，HUSC 特征描述子的平均精度為92.8%，USC 特征描述子的平均精度為94.3%。而在建立特征庫時，HUSC 特征描述子內(nèi)存占用為8.6 MB，USC 特征描述子內(nèi)存占用為17.3 MB，HUSC 較USC 特征描述子內(nèi)存占用減少50.3%。在進(jìn)行特征匹配時，HUSC 特征描述子所用時間為257.26 s，USC 特征描述子所用時間為497.76 s，HUSC 較USC 特征描述子花費時間減少48.3%。由此可知基于半球形鄰域的HUSC 特征描述子具有與USC 描述子相當(dāng)?shù)蔫b別力，同時特征匹配的速度更快，占用內(nèi)存更小。隨著三維數(shù)據(jù)采集設(shè)備精度不斷增加，三維點云的數(shù)據(jù)量也大幅增加。本文所提算法為三維目標(biāo)檢測、識別、重建等任務(wù)提供了一種更高效的特征描述子，也為特征描述子開發(fā)，提供了新的鄰域選取思路。