基于特征空間值篩選的點云關鍵點提取

陳 強

（1.上海市測繪院，上海 200063；2.自然資源部超大城市自然資源時空大數據分析應用重點實驗室，上海 200063）

激光掃描技術得到的點云數據是對物體的真實表達，具有比二維圖像更豐富、層次更深的信息。豐富的信息也為點云數據處理帶來了很多問題，激光掃描得到的原始數據量巨大，組織或搜索這樣的大數據都是極其耗時的，因此從原始數據中高效提取出穩(wěn)定且具有代表性的關鍵點是目前三維點云研究的熱點之一[1-3]。提取關鍵點可大大減少原始數據量，對于后續(xù)的點云搜索效率、配準精度和三維物體識別[4-5]等具有重要意義。直接對點云進行下采樣，得到精簡點云作為關鍵點，該方式效率高，但通常不包含或包含很少的局部特征信息，如李仁忠[6]等提出了一種點云均勻精簡算法，通過建立三維點云的體素柵格對原始點云進行下采樣，該算法效率較高但未考慮關鍵點的局部特征；李琪琪[7]和李國遠[8]等采用曲率約束的方式對點云進行精簡，該類算法在大曲率位置點云分布較密集，相反則較稀疏，曲率的計算相對復雜且對噪聲敏感。考慮局部特征的關鍵點檢測算法能較好地保留原始點云特征，計算效率較低，但得到的關鍵點可重復性較高，位置分布具有一定特性，如Allaire S[9]等將二維尺度不變特征變換（SIFT）算法拓展至三維點云，可有效得到局部特征明顯的關鍵點，但計算效率非常低；周坤[10]等將三維SIFT算法應用于地形重建中，對SIFT算法進行了拓展；Zhong Y[11]提出了內在形狀描述（ISS）關鍵點檢測算法，根據每個點與其鄰域點的協(xié)方差矩陣特征值比值篩選關鍵點，該算法在局部特征上保留較好，但對噪聲敏感；Sipiran I[12]等將二維Har?ris算法拓展至三維，根據每個點與其鄰域點的法向量生成局部曲面表達形式，再從中選取極值點作為關鍵點，該算法對于點云表面特征明顯的區(qū)域具有較好的提取效果，但對于多樣性場景提取效果較差。

針對上述問題，本文提出了一種基于特征空間值篩選的關鍵點提取算法，首先計算所有點的法向量，求出各點與其鄰域點的法向量夾角；然后建立特征提取網絡架構模型，以法向量夾角為模型輸入，將每個點的輸入映射至一維的特征空間值，對特征空間值進行排序，篩選得到關鍵點。實驗結果表明，該算法得到的關鍵點位置主要分布于特征變化明顯區(qū)域，具有更高的可重復性和運行效率，對于噪聲的魯棒性也更好。

1 算法原理

1.1 法向量夾角的計算

法向量夾角從幾何意義上能近似反映局部曲率，相較于直接計算曲率，法向量夾角包含更豐富的表面變化信息且計算量更小，因此計算法向量夾角對于最終確定關鍵點非常重要。法向量計算方式較多，本文選取主成分分析法求解[13]。首先創(chuàng)建每個點與其鄰域點的協(xié)方差矩陣，即

式中，Pi為鄰域點；Pˉ為鄰域點的質心。

求出協(xié)方差矩陣的特征值和特征向量后，選取最小特征值對應的特征向量作為法向量，完成法向量定向[14]。法向量夾角越大意味著曲率越大，這樣的輸入不僅涵蓋了點云的表面變化信息且較大程度地剔除了冗余信息。兩點間的法向量夾角計算公式為：

式中，n1、n2分別為兩點的法向量。

將法向量夾角拓展至單個點與k鄰域的點，得到含有k個法向量夾角的向量，如第r個點為：

F即為下一步模型的輸入，對于該過程中涉及的法向量夾角鄰域點數將在參數實驗中分析。

1.2 模型建立與關鍵點確定

算法需要建立一個特征提取模型，參考文獻[15]的實驗表明，卷積層+全連接層的編碼器網絡架構模型可將點云和點云衍生信息轉換至特定的特征空間，從而量化輸入的信息。因此，本文針對已有的法向量夾角信息和關鍵點提取的特點，建立網絡架構模型（圖1），輸入設置為所有點與其鄰域點的法向量夾角F，輸出映射為一維特征空間向量。F對應圖中的單個k維輸入向量，將所有點的信息合并再輸入卷積層，輸出維度分別為64、128、1 024，卷積層對輸入的不規(guī)則特征進行再編碼，得到規(guī)則的升維的特征向量；然后輸入歸一化層對特征向量做歸一化處理，使得值的范圍不會溢出，得到升維且歸一化的特征空間信息；再將上述結果作為全連接層的輸入，輸出維度分別為1 024、512、256、1；最終得到一維特征空間向量。特征空間向量每個值的大小反映的是對應點處表面特征變化大小，因此算法按特征空間向量值大小排序，根據關鍵點數從中取出最大n個值的對應點，即需要的關鍵點。

圖1 特征提取模型架構圖

算法輸入的法向量夾角信息經過模型映射，最終得到的特征空間向量反映的是點云局部表面變化程度，而篩選后的最大n個點具有最大的變化信息，因此具有最明顯的表面變化特征，得到的關鍵點具有一定的代表性；同時由于法向量夾角信息對于點云空間變換具有不變性，且該輸入經網絡模型映射為一維向量后成了量化值，不同站點的同名點間應當具有近似的特征空間值，因此不同站點提取的關鍵點具有高度的可重復性。

2 實驗結果與分析

2.1 實驗環(huán)境與數據來源

實驗電腦內存為8 GB，算法由Python語言和Ten?sorflow2.0 實現，對照組的Harris3D 和SIFT 算法由PCL1.8[16]實現。實驗選取Stanford 3D Scanning Reposi?tory 的斯坦福雕像掃描儀獲取的Lucy 雕像點云和Ro?botic 3D Scan Repository 的Riegl VZ-400 掃描儀獲取的大規(guī)模城市數據（命名為City）兩組數據。

2.2 評價指標

關鍵點提取得到的點通常具有代表性和可重復性，代表性是指反映原始點云主要特征的程度；可重復性是指同場景不同站點點云經過關鍵點提取后，應當具有較高的重復性。重復性通常用最近點距離閾值內的點數占總點數的比例表示，即重復率[17]。

對照算法選取ISS（ISS 關鍵點）算法、Voxel 算法、Uniform 算法、Sift 算法、Curvature 算法和Harris算法。參考點位偏差閾值選取，首先選取一個點云密度n倍的常數作為標準，再從0～2 之間均勻選取若干數，以這組數作為圖表的橫坐標，然后將這組數與標準數相乘得到一系列閾值，預先求出兩幅實驗點云的真實轉換矩陣并配準，若同名點間的誤差小于閾值則認為滿足重復的條件。

2.3 關鍵點可重復性和穩(wěn)健性評估

對Lucy數據進行實驗，分析鄰域點參數對可重復性的影響，添加10 db 強度的高斯白噪聲，設置參考點位偏差閾值的標準為5 mm。由圖2可知，當鄰域點數由20遞增至100時，整體重復率呈增長趨勢，但當鄰域點數增加到40時，重復率幾乎不再增長，且鄰域點增加將導致計算時間顯著增加，綜合可重復性與效率因素可知40個鄰域點較優(yōu)。

圖2 鄰域點參數實驗圖

在Lucy數據中分別添加10 db、8 db、6 db和4 db強度的噪聲，驗證算法對不同強度噪聲的穩(wěn)健性。設置參考點位偏差閾值的標準為45 mm。由圖3 可知，各算法間重復率相對關系基本不變，即本文算法>Sift>Harris>ISS>Voxel>Uniform>Curvature，隨著參考點位偏差閾值的增大，算法間的重復率差距減小，因此本文算法具有比傳統(tǒng)算法更高的可重復性和更強的穩(wěn)健性。

圖3 Lucy噪聲數據算法對比圖

為驗證不同場景點云數據的參數，利用City數據再次進行參數實驗，設置參考點位偏差閾值的標準為100 mm。由圖4可知，當鄰域點數為30時重復率達到極大值；本文算法在所有實驗組算法中具有最高的重復率。

圖4 City數據算法對比圖

綜上所述，本文算法在鄰域點數為30～40時具有較高的可重復性，與傳統(tǒng)算法相比，具有更高的可重復性和運行效率，且對噪聲的穩(wěn)健性更好，在Lucy噪聲數據中平均重復率約提高23.0%，在City 數據中平均重復率約提高9.3%。

2.4 關鍵點提取效率與空間位置分析

關鍵點提取算法的計算效率決定了算法的實用性，空間位置分布則更直觀地展現了關鍵點分布差異。由于Voxel算法和Uniform算法的提取結果在效率和位置分布上極為近似，因此實驗以Voxel 算法為代表，分別對兩組數據提取10 000、5 000、1 000、100個關鍵點。由圖5 可知，兩組數據中不同算法計算時間的相對關系基本保持一致，即Harris>Sift>ISS>本文算法>Curvature>Voxel，Curvature 和Voxel 算法的計算效率最高，但Curvature 算法的穩(wěn)定性最差，Voxel 算法得到的關鍵點是隨機均勻分布的，完全未考慮到點云特征。因此，綜合計算效率、穩(wěn)定性、局部特征保留程度來看，本文算法最優(yōu)。

圖5 多分辨率計算效率對比

為分析不同算法提取的關鍵點空間位置，分別將兩組數據提取的關鍵點與原始數據進行疊加對比。由圖6 可知，Lucy數據中本文算法關鍵點集中于多個特征變化明顯的區(qū)域，其余算法位置分散，在平坦區(qū)域和其他特征變化不明顯區(qū)域仍有分布。

圖6 Lucy數據關鍵點位置分布圖

由City數據提取的100個關鍵點疊加圖（圖7）可知，本文算法提取的關鍵點幾乎不存在噪聲點，對點云中特征變化明顯區(qū)域的覆蓋率較高，提取的關鍵點具有較高的代表性和可識別性。

圖7 City數據關鍵點位置分布圖

由實驗結果可知，本文算法的計算效率高于ISS、Harris 和Sift 算法，不及Curvature、Voxel 和Uni?form 算法，但是Curvature 算法的穩(wěn)定性最差，Voxel和Uniform 算法完全未考慮點云特征，且根據位置分布，本文算法得到的關鍵點含噪聲點最少，關鍵點位置主要分布在特征變化明顯、邊緣點和角點區(qū)域，比傳統(tǒng)算法分布更集中和穩(wěn)定。

3 結 語

針對傳統(tǒng)關鍵點提取算法計算效率低、可重復性差的問題，提出了一種基于特征空間值篩選的關鍵點提取算法。首先計算所有點的法向量，求取各點與其鄰域點的法向量夾角；再建立特征提取網絡架構模型，以法向量夾角作為模型輸入，將其映射為一維的特征空間值；最后對特征空間值進行排序，篩選得到關鍵點。本文分別在兩組不同規(guī)模場景中進行實驗，與傳統(tǒng)算法相比，本文算法提取的關鍵點具有更高的可重復性和運行效率，且對于噪聲的魯棒性更好，小場景、大場景數據中平均重復率分別約提高23.0%和9.3%，關鍵點位置主要分布于特征變化明顯區(qū)域，可較好地表達點云的整體和局部特征，得到的關鍵點能進一步應用于點云配準、目標識別等任務中。然而，本文算法的參數自適應性還需進一步加強，后續(xù)將對此進行著重研究。