一種自適應點云特征點提取算法

韓磊，陳宇，王春陽，于艷鑫

（長春理工大學電子信息工程學院，長春 130022）

0 引言

三維激光掃描技術現已在考古研究、生物醫學、汽車工業、水利工程地形測繪等工程領域有了廣泛的應用[1-2]，但其測得的點云數據密度高、數量大，存在大量的冗余點[3]。因此針對這類點云數據首先要進行簡化即去除冗余點，為保證模型最基本的幾何形狀保留完整，需要先提取出點云特征點，進而對點云數據進行簡化和三維曲面重建等。另外，特征點檢測對于點云配準也具有重要意義。所以模型的特征點提取是處理三維散亂點云數據的關鍵步驟之一[4]。

Charlie等采用雙邊濾波來檢測和重建特征,需要優化給定模型的網格連通性，否則尖銳的邊緣區域頂點坐標會發生漂移和擁擠[5]。Mian等人通過構造一個品質因數Qk，該品質因數Qk包括高斯曲率和主曲率，特征點為其品質因數Qk大于某閾值的點[6]。王小超等提出基于局部重建的點云特征點提取方法，該方法可以處理分片光滑曲面上采集的點云數據，但對于兩個彎曲程度較大的曲面相交形成的特征點該方法不適用[7]。王晉疆等提出一種基于點簽名的特征點檢測方法，根據具有正態分布特性的點簽名的均值與方差設制曲率閾值，該方法抗噪性能佳但時間復雜度高[8]。

針對現有算法存在的效率低、特征點提取不準確等問題，本文提出一種改進的自適應點云特征點提取算法，通過計算數據點到k鄰域點（k可以根據數據密度進行改變）的平均距離、該點的曲率以及該點的法向與k鄰域點法向夾角的和，設定一個特征參數，根據特征參數正態分布規律，利用均值與方差的和自適應地設置閾值來提取特征點。該方法適用于復雜的模型數據，能夠準確高效地提取出點云特征點。

1 特征點提取方法

1.1 散亂點云空間劃分

本文采用Hash法劃分點云P，建立空間長方體包圍盒，將空間等間距切割成體積相同的若干個立方體柵格（示意圖如圖1），確定離散點所在的子立方體，標記索引號，便于查找k鄰域點[9]。求出X,Y,Z三個坐標軸上的最大值與最小值Xmax,Xmin,Ymax,Ymin,Zmax,Zmin。

長方體包圍盒的邊長為：

定義小立方體邊長：

其中，N為點云數目，根據經驗k一般取值為15-25。通過下式對數據點進行定位，求出任一點在小立方體的索引號m,n,l：

求每個數據點的歐氏距離最近的k個鄰域點時，搜索范圍限定在其本身所在小立方體及其上下左右前后的27個立方體。

圖1 立方體柵格示意圖

1.2 基于曲率和密度的特征點檢測算法

一般模型的特征區域數據點比較密集，曲率較大，該算法綜合考慮數據點與鄰域點的平均距離、數據點曲率，以及數據點與鄰域點法向夾角的和。利用八叉樹法對點云進行細分求點云密度，再結合模型整體信息確定特征檢測閾值[10]。鄰域點的平均距離計算公式如下：

其中M(pi)為數據點pi的鄰近點集。

點云數據的法向和曲率也是判斷是否為特征點的重要因素，采用基于最小二乘平面擬合法求pi法向量ni，如下所示：

其中n為平面P(n,d)的法向量，d為平面P(n,d)到坐標原點的距離。利用主元分析法求解，最小特征值對應的特征向量即為點云法向量。

，設λ1＜λ2＜λ3，e1可近似曲面在點pi的法向量ni，即ni≈e1。

τi近似為點云模型在數據點pi的平均曲率。數據點與鄰域點的法向夾角也是衡量曲面彎曲程度的標準，定義法向夾角參數wa(pi)為數據點與所有鄰域點的法向夾角的和：

θpipj可由下式求得：

特征區域內的點比較密集，數據點與鄰域點距離小，所以數據點到k鄰域點（k可以根據數據密度進行改變）的平均距離與特征參數成反比，曲率越大模型特征越明顯，所以曲率與特征參數成正比，特征點與鄰近點的法向量夾角較大，所以法向夾角參數與特征參數成正比，定義特征參數：

其中λn曲率系數和λd是距離系數。

用八叉樹計算特征檢測閾值，子節點中包含的數據點個數小于8，計算所有葉子節點的平均對角線長度，作為點云密度ξ。由點云模型邊到中心點的最大距離dc表示模型的尺寸，定義特征檢測閾值為σ=ξ/dc。特征參數大于檢測閾值σ的數據點為特征點。

1.3 自適應點云特征點提取算法

由于基于曲率和密度的特征點檢測算法的特征參數需要人為輸入和調整曲率系數和距離系數，這兩個系數僅作為控制特征點數量，且計算點云密度和模型邊到中心點的最大距離較耗時。因此本文將曲率系數與距離系數去掉，重新定義特征參數如下：

選取斯坦福兔子模型、Horse模型和椅子模型三個在形狀上具有代表性的模型計算其特征參數，特征參數分布如圖2。

圖2 特征參數分布圖

由圖 2（a）（c）（e）可以看出斯坦福兔子模型表面較平坦，數據點較緊湊；Horse模型四條腿相對身體較凸出且分散；椅子模型有鏤空部分，數據點不完全連續。這三個模型的特征參數分布如圖 2（b）（d）（f），圖上曲線為正態分布曲線，橫坐標為參數值，縱坐標為點云數。可以看出特征參數近似服從正態分布，因此，可以認為散亂點云的特征參數具有正態分布的特點，根據這一特點來確定特征點提取閾值。閾值改進如下，取特征參數的均值與方差：

確定閾值：

若某個數據點的特征參數w(pi)大于閾值δ，那么這個點pi為特征點qi。若特征參數w(pi)小于閾值δ，pi為非特征點。

2 實驗結果分析

本文實驗在MATLAB 2016a環境下進行特征點提取，操作系統為Windows 10，主頻2.5GHz，處理器為Intel Core i7-6500U。圖3、圖4為本文方法提取特征點效果。

圖3 特征點提取

圖3 （a）為斯坦福兔子模型，共35947個點，提取出的特征點個數為4797。特征點云顏色與原始點云相對應。可以看出，模型的耳朵、頭部、腿部和尾部等紋理信息可以提取出來。圖3（b）為椅子模型，共49960個點，提取出的特征點個數為7290。椅子的靠背、凳腿及座板邊框特征可以有效的提取出來，座板內部為非特征信息被過濾掉。

圖4 Skull模型及特征點提取

圖4 為Skull模型，原始點云共有20002個點，提取特征點個數為3830。可以看出模型頭部的字母很好地保留下來，模型的牙齒信息也基本保留，以及模型的棱角紋理較好地提取出來。

圖5為本文方法取k=15與文獻[8]方法取k=20,e=1和文獻[10]方法取λn=400，λd=100在無噪聲干擾下和隨機添加3000個噪聲點的情況下，對Horse模型的特征點提取效果。

如圖5所示，可以看出模型頭部、腹部和腿部等是特征點密集區域，文獻[8]（圖5（a））、文獻[10]（圖5（c））和本文方法（圖5（e））在無噪聲干擾下都能比較好的提取出特征點。但文獻[8]（圖5（b））和文獻[10]（圖5（d））在噪聲的干擾下，可以明顯看出將很多噪聲點識別為特征點，影響后續重建效果。本文方法（圖5（f））對噪聲敏感度更低，可以保持相對穩定的特征提取效果。

圖5 文獻[8]方法、文獻[10]方法與本文方法特征點提取結果

表1 未加噪特征點提取對比

表2 加噪特征點提取對比

表1為在無噪聲情況下文獻[8]方法、文獻[10]方法與本文方法對Horse模型（48485個點）特征點提取對比，表2為加3000個噪聲點的情況下特征點提取對比結果。文獻[8]方法由于要經過兩次篩選：先根據散亂點云具有正態分布規律的點簽名設定曲率閾值進行篩選，然后再對候選特征點在其主曲率方向上投影，進行進一步篩選，時間復雜度較高。該方法提取出特征點1621個，耗時 16.5s；加噪后特征點為 2120，耗時16.8s。文獻[10]方法根據點云法向夾角、數據點平均距離和曲率計算特征參數，選取數據點密度與模型到中心點最大距離的比值作為閾值，提取出特征點1128個，耗時10.6s；加噪后特征點為10334，耗時13.2s。該方法需人為根據經驗設定系數。本文方法根據特征參數的正態分布特點選取閾值，提取出7025個特征點，耗時8.2s；加噪后特征點為7382，耗時8.3s。可以看出加噪后識別出的特征點與未加噪相差不大。由此得出本算法能夠較完整地保留模型的特征信息，耗時短，效率較高。

3 結語

本文采用Hash函數法求出數據點鄰域點，通過計算數據點到k鄰域點距離的平均、該點曲率、該點的法向與k鄰域點法向夾角的和，設定點云特征參數，根據特征參數的均值與方差自適應地設置閾值來提取特征點，不需要輸入系數。實驗結果表明，本文的方法準確提取出點云模型特征點，提取出的點少而精，不會遺漏特征點，是一種有效的特征點提取算法。

參考文獻：

[1]高艷芳,豆賀,佟晗,韓勝松.反求工程的研究現狀與發展趨勢[J].現代化農業,2017,09,58-60

[2]劉曉芳,田蘭芬.三維激光掃描技術在水利工程地形測繪中的應用[J].科技創新與應用，2017,27,141-143

[3]解則曉,劉靜曉,潘成成等.一種散亂分層點云的有序化精簡方法[J].幾何設計與計算,2016,37（3）：359-366

[4]楊斌杰,魯鐵定.點云數據特征點提取方法的比較[J].江西科學,2015,33（1）：10-14

[5]Charlie C L.Wang.Bilateral Recovering of Sharp Edges on Feature-insensitive Sampled Meshes[J].IEEE Transactions on Visuallization and Computer Graphics,2006,12（4）.

[6]Mian A,Bennamoun M,Oture-based 3D Object Retrieval from Cluttered Scenes[J].International Journal of Computer Vision,2010,89（2）：348-36.

[7]王小超,劉秀平,李寶軍等.基于局部重建的點云特征點提取[J].計算機輔助設計與圖形學學報,2013,25（5）：659-665.

[8]王晉疆，陳陽，田慶國等.一種基于點簽名的散亂點云特征點檢測方法[J].計算機工程,2014,40（7）：174-178.

[9]王楠.基于三維散亂點云的網格重構技術研究[D].大連：大連大學,2013.

[10]王麗輝,袁保宗.三維散亂點云模型的特征點檢測[J].Signal Processing,2011,27（6）：932-938.