基于特征空間值篩選的點(diǎn)云關(guān)鍵點(diǎn)提取

陳 強(qiáng)

（1.上海市測(cè)繪院，上海 200063；2.自然資源部超大城市自然資源時(shí)空大數(shù)據(jù)分析應(yīng)用重點(diǎn)實(shí)驗(yàn)室，上海 200063）

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

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

1 算法原理

1.1 法向量夾角的計(jì)算

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

式中，Pi為鄰域點(diǎn)；Pˉ為鄰域點(diǎn)的質(zhì)心。

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

式中，n1、n2分別為兩點(diǎn)的法向量。

將法向量夾角拓展至單個(gè)點(diǎn)與k鄰域的點(diǎn)，得到含有k個(gè)法向量夾角的向量，如第r個(gè)點(diǎn)為：

F即為下一步模型的輸入，對(duì)于該過(guò)程中涉及的法向量夾角鄰域點(diǎn)數(shù)將在參數(shù)實(shí)驗(yàn)中分析。

1.2 模型建立與關(guān)鍵點(diǎn)確定

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

圖1 特征提取模型架構(gòu)圖

算法輸入的法向量夾角信息經(jīng)過(guò)模型映射，最終得到的特征空間向量反映的是點(diǎn)云局部表面變化程度，而篩選后的最大n個(gè)點(diǎn)具有最大的變化信息，因此具有最明顯的表面變化特征，得到的關(guān)鍵點(diǎn)具有一定的代表性；同時(shí)由于法向量夾角信息對(duì)于點(diǎn)云空間變換具有不變性，且該輸入經(jīng)網(wǎng)絡(luò)模型映射為一維向量后成了量化值，不同站點(diǎn)的同名點(diǎn)間應(yīng)當(dāng)具有近似的特征空間值，因此不同站點(diǎn)提取的關(guān)鍵點(diǎn)具有高度的可重復(fù)性。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)來(lái)源

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

2.2 評(píng)價(jià)指標(biāo)

關(guān)鍵點(diǎn)提取得到的點(diǎn)通常具有代表性和可重復(fù)性，代表性是指反映原始點(diǎn)云主要特征的程度；可重復(fù)性是指同場(chǎng)景不同站點(diǎn)點(diǎn)云經(jīng)過(guò)關(guān)鍵點(diǎn)提取后，應(yīng)當(dāng)具有較高的重復(fù)性。重復(fù)性通常用最近點(diǎn)距離閾值內(nèi)的點(diǎn)數(shù)占總點(diǎn)數(shù)的比例表示，即重復(fù)率[17]。

對(duì)照算法選取ISS（ISS 關(guān)鍵點(diǎn)）算法、Voxel 算法、Uniform 算法、Sift 算法、Curvature 算法和Harris算法。參考點(diǎn)位偏差閾值選取，首先選取一個(gè)點(diǎn)云密度n倍的常數(shù)作為標(biāo)準(zhǔn)，再?gòu)?～2 之間均勻選取若干數(shù)，以這組數(shù)作為圖表的橫坐標(biāo)，然后將這組數(shù)與標(biāo)準(zhǔn)數(shù)相乘得到一系列閾值，預(yù)先求出兩幅實(shí)驗(yàn)點(diǎn)云的真實(shí)轉(zhuǎn)換矩陣并配準(zhǔn)，若同名點(diǎn)間的誤差小于閾值則認(rèn)為滿足重復(fù)的條件。

2.3 關(guān)鍵點(diǎn)可重復(fù)性和穩(wěn)健性評(píng)估

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

圖2 鄰域點(diǎn)參數(shù)實(shí)驗(yàn)圖

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

圖3 Lucy噪聲數(shù)據(jù)算法對(duì)比圖

為驗(yàn)證不同場(chǎng)景點(diǎn)云數(shù)據(jù)的參數(shù)，利用City數(shù)據(jù)再次進(jìn)行參數(shù)實(shí)驗(yàn)，設(shè)置參考點(diǎn)位偏差閾值的標(biāo)準(zhǔn)為100 mm。由圖4可知，當(dāng)鄰域點(diǎn)數(shù)為30時(shí)重復(fù)率達(dá)到極大值；本文算法在所有實(shí)驗(yàn)組算法中具有最高的重復(fù)率。

圖4 City數(shù)據(jù)算法對(duì)比圖

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

2.4 關(guān)鍵點(diǎn)提取效率與空間位置分析

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

圖5 多分辨率計(jì)算效率對(duì)比

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

圖6 Lucy數(shù)據(jù)關(guān)鍵點(diǎn)位置分布圖

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

圖7 City數(shù)據(jù)關(guān)鍵點(diǎn)位置分布圖

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

3 結(jié) 語(yǔ)

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